- * it must not delete (or move) any other rules in 'cls' that are in the same
- * table as the argument rule. Two rules are in the same table if their
- * cls_rule structs have the same table_idx; as a special case, a rule with
- * wildcards and an exact-match rule will never be in the same table. */
-void
-classifier_for_each(const struct classifier *cls, int include,
- void (*callback)(struct cls_rule *, void *aux),
- void *aux)
-{
- if (include & CLS_INC_WILD) {
- const struct hmap *tbl;
-
- for (tbl = &cls->tables[0]; tbl < &cls->tables[CLS_N_FIELDS]; tbl++) {
- struct cls_bucket *bucket, *next_bucket;
-
- HMAP_FOR_EACH_SAFE (bucket, next_bucket,
- struct cls_bucket, hmap_node, tbl) {
- struct cls_rule *prev_rule, *rule;
-
- /* We can't just use LIST_FOR_EACH_SAFE here because, if the
- * callback deletes the last rule in the bucket, then the
- * bucket itself will be destroyed. The bucket contains the
- * list head so that's a use-after-free error. */
- prev_rule = NULL;
- LIST_FOR_EACH (rule, struct cls_rule, node.list,
- &bucket->rules) {
- if (prev_rule) {
- callback(prev_rule, aux);
- }
- prev_rule = rule;
- }
- if (prev_rule) {
- callback(prev_rule, aux);
- }
- }
- }
- }
-
- if (include & CLS_INC_EXACT) {
- struct cls_rule *rule, *next_rule;
-
- HMAP_FOR_EACH_SAFE (rule, next_rule,
- struct cls_rule, node.hmap, &cls->exact_table) {
- callback(rule, aux);
- }
- }
-}
-\f
-static struct cls_bucket *create_bucket(struct hmap *, size_t hash,
- const flow_t *fixed);
-static struct cls_rule *bucket_insert(struct cls_bucket *, struct cls_rule *);
-
-static inline bool equal_bytes(const void *, const void *, size_t n);
-
-/* Returns a hash computed across the fields in 'flow' whose field indexes
- * (CLS_F_IDX_*) are less than 'table_idx'. (If 'table_idx' is
- * CLS_F_IDX_EXACT, hashes all the fields in 'flow'). */
-static uint32_t
-hash_fields(const flow_t *flow, int table_idx)
-{
- /* I just know I'm going to hell for writing code this way.
- *
- * GCC generates pretty good code here, with only a single taken
- * conditional jump per execution. Now the question is, would we be better
- * off marking this function ALWAYS_INLINE and writing a wrapper that
- * switches on the value of 'table_idx' to get rid of all the conditional
- * jumps entirely (except for one in the wrapper)? Honestly I really,
- * really hope that it doesn't matter in practice.
- *
- * We could do better by calculating hashes incrementally, instead of
- * starting over from the top each time. But that would be even uglier. */
- uint32_t a, b, c;
- uint32_t tmp[3];
- size_t n;
-
- a = b = c = 0xdeadbeef + table_idx;
- n = 0;
-
-#define CLS_FIELD(WILDCARDS, MEMBER, NAME) \
- if (table_idx == CLS_F_IDX_##NAME) { \
- /* Done. */ \
- memset((uint8_t *) tmp + n, 0, sizeof tmp - n); \
- goto finish; \
- } else { \
- const size_t size = sizeof flow->MEMBER; \
- const uint8_t *p1 = (const uint8_t *) &flow->MEMBER; \
- const size_t p1_size = MIN(sizeof tmp - n, size); \
- const uint8_t *p2 = p1 + p1_size; \
- const size_t p2_size = size - p1_size; \
- \
- /* Append to 'tmp' as much data as will fit. */ \
- memcpy((uint8_t *) tmp + n, p1, p1_size); \
- n += p1_size; \
- \
- /* If 'tmp' is full, mix. */ \
- if (n == sizeof tmp) { \
- a += tmp[0]; \
- b += tmp[1]; \
- c += tmp[2]; \
- HASH_MIX(a, b, c); \
- n = 0; \
- } \
- \
- /* Append to 'tmp' any data that didn't fit. */ \
- memcpy(tmp, p2, p2_size); \
- n += p2_size; \
- }
- CLS_FIELDS
-#undef CLS_FIELD
-
-finish:
- a += tmp[0];
- b += tmp[1];
- c += tmp[2];
- HASH_FINAL(a, b, c);
- return c;
-}
-
-/* Compares the fields in 'a' and 'b' whose field indexes (CLS_F_IDX_*) are
- * less than 'table_idx'. (If 'table_idx' is CLS_F_IDX_EXACT, compares all the
- * fields in 'a' and 'b').