X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=lib%2Fclassifier.c;h=e5d226ecb883249687dabed0465fce262d41f46f;hb=35b769cb491586718a72dc133509e96b0a2feee8;hp=38a5e2bc9c07194b8ac242fd8252636b32118e4b;hpb=e65dc5c57e4520d838350607d256f251e4d81235;p=sliver-openvswitch.git diff --git a/lib/classifier.c b/lib/classifier.c index 38a5e2bc9..e5d226ecb 100644 --- a/lib/classifier.c +++ b/lib/classifier.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2009, 2010 Nicira Networks. + * Copyright (c) 2009, 2010, 2011, 2012 Nicira, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -19,89 +19,113 @@ #include #include #include +#include "byte-order.h" #include "dynamic-string.h" #include "flow.h" #include "hash.h" +#include "odp-util.h" +#include "ofp-util.h" +#include "packets.h" + +static struct cls_table *find_table(const struct classifier *, + const struct minimask *); +static struct cls_table *insert_table(struct classifier *, + const struct minimask *); + +static void destroy_table(struct classifier *, struct cls_table *); + +static struct cls_rule *find_match(const struct cls_table *, + const struct flow *); +static struct cls_rule *find_equal(struct cls_table *, + const struct miniflow *, uint32_t hash); +static struct cls_rule *insert_rule(struct cls_table *, struct cls_rule *); + +/* Iterates RULE over HEAD and all of the cls_rules on HEAD->list. */ +#define FOR_EACH_RULE_IN_LIST(RULE, HEAD) \ + for ((RULE) = (HEAD); (RULE) != NULL; (RULE) = next_rule_in_list(RULE)) +#define FOR_EACH_RULE_IN_LIST_SAFE(RULE, NEXT, HEAD) \ + for ((RULE) = (HEAD); \ + (RULE) != NULL && ((NEXT) = next_rule_in_list(RULE), true); \ + (RULE) = (NEXT)) + +static struct cls_rule *next_rule_in_list__(struct cls_rule *); +static struct cls_rule *next_rule_in_list(struct cls_rule *); + +/* cls_rule. */ -const struct cls_field cls_fields[CLS_N_FIELDS + 1] = { -#define CLS_FIELD(WILDCARDS, MEMBER, NAME) \ - { offsetof(struct flow, MEMBER), \ - sizeof ((struct flow *)0)->MEMBER, \ - WILDCARDS, \ - #NAME }, - CLS_FIELDS -#undef CLS_FIELD - { sizeof(struct flow), 0, 0, "exact" }, -}; - -static uint32_t hash_fields(const struct flow *, int table_idx); -static bool equal_fields(const struct flow *, const struct flow *, - int table_idx); - -static int table_idx_from_wildcards(uint32_t wildcards); -static struct cls_rule *table_insert(struct hmap *, struct cls_rule *); -static struct cls_rule *insert_exact_rule(struct classifier *, - struct cls_rule *); -static struct cls_bucket *find_bucket(struct hmap *, size_t hash, - const struct cls_rule *); -static struct cls_rule *search_table(const struct hmap *table, int field_idx, - const struct cls_rule *); -static struct cls_rule *search_exact_table(const struct classifier *, - size_t hash, const struct flow *); -static bool rules_match_1wild(const struct cls_rule *fixed, - const struct cls_rule *wild, int field_idx); -static bool rules_match_2wild(const struct cls_rule *wild1, - const struct cls_rule *wild2, int field_idx); - -/* Converts the flow in 'flow' into a cls_rule in 'rule', with the given - * 'wildcards' and 'priority'.*/ +/* Initializes 'rule' to match packets specified by 'match' at the given + * 'priority'. 'match' must satisfy the invariant described in the comment at + * the definition of struct match. + * + * The caller must eventually destroy 'rule' with cls_rule_destroy(). + * + * (OpenFlow uses priorities between 0 and UINT16_MAX, inclusive, but + * internally Open vSwitch supports a wider range.) */ void -cls_rule_from_flow(const struct flow *flow, uint32_t wildcards, - unsigned int priority, struct cls_rule *rule) +cls_rule_init(struct cls_rule *rule, + const struct match *match, unsigned int priority) { - rule->flow = *flow; - flow_wildcards_init(&rule->wc, wildcards); + minimatch_init(&rule->match, match); rule->priority = priority; - rule->table_idx = table_idx_from_wildcards(rule->wc.wildcards); } -/* Converts the ofp_match in 'match' into a cls_rule in 'rule', with the given - * 'priority'. If 'tun_id_from_cookie' is set then the upper 32 bits of - * 'cookie' are stored in the rule as the tunnel ID. */ +/* Same as cls_rule_init() for initialization from a "struct minimatch". */ void -cls_rule_from_match(const struct ofp_match *match, unsigned int priority, - bool tun_id_from_cookie, uint64_t cookie, - struct cls_rule *rule) +cls_rule_init_from_minimatch(struct cls_rule *rule, + const struct minimatch *match, + unsigned int priority) { - uint32_t wildcards; - flow_from_match(match, tun_id_from_cookie, cookie, &rule->flow, &wildcards); - flow_wildcards_init(&rule->wc, wildcards); - rule->priority = rule->wc.wildcards ? priority : UINT16_MAX; - rule->table_idx = table_idx_from_wildcards(rule->wc.wildcards); + minimatch_clone(&rule->match, match); + rule->priority = priority; } -/* Converts 'rule' to a string and returns the string. The caller must free - * the string (with free()). */ -char * -cls_rule_to_string(const struct cls_rule *rule) +/* Initializes 'dst' as a copy of 'src'. + * + * The caller must eventually destroy 'rule' with cls_rule_destroy(). */ +void +cls_rule_clone(struct cls_rule *dst, const struct cls_rule *src) { - struct ds s = DS_EMPTY_INITIALIZER; - ds_put_format(&s, "wildcards=%x priority=%u ", - rule->wc.wildcards, rule->priority); - flow_format(&s, &rule->flow); - return ds_cstr(&s); + minimatch_clone(&dst->match, &src->match); + dst->priority = src->priority; } -/* Prints cls_rule 'rule', for debugging. +/* Frees memory referenced by 'rule'. Doesn't free 'rule' itself (it's + * normally embedded into a larger structure). * - * (The output could be improved and expanded, but this was good enough to - * debug the classifier.) */ + * ('rule' must not currently be in a classifier.) */ +void +cls_rule_destroy(struct cls_rule *rule) +{ + minimatch_destroy(&rule->match); +} + +/* Returns true if 'a' and 'b' match the same packets at the same priority, + * false if they differ in some way. */ +bool +cls_rule_equal(const struct cls_rule *a, const struct cls_rule *b) +{ + return a->priority == b->priority && minimatch_equal(&a->match, &b->match); +} + +/* Returns a hash value for 'rule', folding in 'basis'. */ +uint32_t +cls_rule_hash(const struct cls_rule *rule, uint32_t basis) +{ + return minimatch_hash(&rule->match, hash_int(rule->priority, basis)); +} + +/* Appends a string describing 'rule' to 's'. */ void -cls_rule_print(const struct cls_rule *rule) +cls_rule_format(const struct cls_rule *rule, struct ds *s) { - printf("wildcards=%x priority=%u ", rule->wc.wildcards, rule->priority); - flow_print(stdout, &rule->flow); - putc('\n', stdout); + minimatch_format(&rule->match, s, rule->priority); +} + +/* Returns true if 'rule' matches every packet, false otherwise. */ +bool +cls_rule_is_catchall(const struct cls_rule *rule) +{ + return minimask_is_catchall(&rule->match.mask); } /* Initializes 'cls' as a classifier that initially contains no classification @@ -109,13 +133,8 @@ cls_rule_print(const struct cls_rule *rule) void classifier_init(struct classifier *cls) { - int i; - cls->n_rules = 0; - for (i = 0; i < ARRAY_SIZE(cls->tables); i++) { - hmap_init(&cls->tables[i]); - } - hmap_init(&cls->exact_table); + hmap_init(&cls->tables); } /* Destroys 'cls'. Rules within 'cls', if any, are not freed; this is the @@ -124,212 +143,191 @@ void classifier_destroy(struct classifier *cls) { if (cls) { - struct cls_bucket *bucket, *next_bucket; - struct hmap *tbl; + struct cls_table *table, *next_table; - for (tbl = &cls->tables[0]; tbl < &cls->tables[CLS_N_FIELDS]; tbl++) { - HMAP_FOR_EACH_SAFE (bucket, next_bucket, hmap_node, tbl) { - free(bucket); - } - hmap_destroy(tbl); + HMAP_FOR_EACH_SAFE (table, next_table, hmap_node, &cls->tables) { + hmap_destroy(&table->rules); + hmap_remove(&cls->tables, &table->hmap_node); + free(table); } - hmap_destroy(&cls->exact_table); + hmap_destroy(&cls->tables); } } -/* Returns true if 'cls' does not contain any classification rules, false - * otherwise. */ +/* Returns true if 'cls' contains no classification rules, false otherwise. */ bool classifier_is_empty(const struct classifier *cls) { return cls->n_rules == 0; } -/* Returns the number of rules in 'classifier'. */ +/* Returns the number of rules in 'cls'. */ int classifier_count(const struct classifier *cls) { return cls->n_rules; } -/* Returns the number of rules in 'classifier' that have no wildcards. */ -int -classifier_count_exact(const struct classifier *cls) -{ - return hmap_count(&cls->exact_table); -} - -/* Inserts 'rule' into 'cls'. Transfers ownership of 'rule' to 'cls'. +/* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller + * must not modify or free it. * * If 'cls' already contains an identical rule (including wildcards, values of * fixed fields, and priority), replaces the old rule by 'rule' and returns the * rule that was replaced. The caller takes ownership of the returned rule and - * is thus responsible for freeing it, etc., as necessary. + * is thus responsible for destroying it with cls_rule_destroy(), freeing the + * memory block in which it resides, etc., as necessary. * * Returns NULL if 'cls' does not contain a rule with an identical key, after * inserting the new rule. In this case, no rules are displaced by the new * rule, even rules that cannot have any effect because the new rule matches a * superset of their flows and has higher priority. */ struct cls_rule * -classifier_insert(struct classifier *cls, struct cls_rule *rule) +classifier_replace(struct classifier *cls, struct cls_rule *rule) { - struct cls_rule *old; - assert((rule->wc.wildcards == 0) == (rule->table_idx == CLS_F_IDX_EXACT)); - old = (rule->wc.wildcards - ? table_insert(&cls->tables[rule->table_idx], rule) - : insert_exact_rule(cls, rule)); - if (!old) { + struct cls_rule *old_rule; + struct cls_table *table; + + table = find_table(cls, &rule->match.mask); + if (!table) { + table = insert_table(cls, &rule->match.mask); + } + + old_rule = insert_rule(table, rule); + if (!old_rule) { + table->n_table_rules++; cls->n_rules++; } - return old; + return old_rule; } -/* Inserts 'rule' into 'cls'. Transfers ownership of 'rule' to 'cls'. +/* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller + * must not modify or free it. * - * 'rule' must be an exact-match rule (rule->wc.wildcards must be 0) and 'cls' - * must not contain any rule with an identical key. */ + * 'cls' must not contain an identical rule (including wildcards, values of + * fixed fields, and priority). Use classifier_find_rule_exactly() to find + * such a rule. */ void -classifier_insert_exact(struct classifier *cls, struct cls_rule *rule) +classifier_insert(struct classifier *cls, struct cls_rule *rule) { - hmap_insert(&cls->exact_table, &rule->node.hmap, - flow_hash(&rule->flow, 0)); - cls->n_rules++; + struct cls_rule *displaced_rule = classifier_replace(cls, rule); + assert(!displaced_rule); } -/* Removes 'rule' from 'cls'. It is caller's responsibility to free 'rule', if - * this is desirable. */ +/* Removes 'rule' from 'cls'. It is the caller's responsibility to destroy + * 'rule' with cls_rule_destroy(), freeing the memory block in which 'rule' + * resides, etc., as necessary. */ void classifier_remove(struct classifier *cls, struct cls_rule *rule) { - if (rule->wc.wildcards) { - /* Remove 'rule' from bucket. If that empties the bucket, remove the - * bucket from its table. */ - struct hmap *table = &cls->tables[rule->table_idx]; - struct list *rules = list_remove(&rule->node.list); - if (list_is_empty(rules)) { - /* This code is a little tricky. list_remove() returns the list - * element just after the one removed. Since the list is now - * empty, this will be the address of the 'rules' member of the - * bucket that was just emptied, so pointer arithmetic (via - * CONTAINER_OF) can find that bucket. */ - struct cls_bucket *bucket; - bucket = CONTAINER_OF(rules, struct cls_bucket, rules); - hmap_remove(table, &bucket->hmap_node); - free(bucket); - } + struct cls_rule *head; + struct cls_table *table; + + table = find_table(cls, &rule->match.mask); + head = find_equal(table, &rule->match.flow, rule->hmap_node.hash); + if (head != rule) { + list_remove(&rule->list); + } else if (list_is_empty(&rule->list)) { + hmap_remove(&table->rules, &rule->hmap_node); } else { - /* Remove 'rule' from cls->exact_table. */ - hmap_remove(&cls->exact_table, &rule->node.hmap); + struct cls_rule *next = CONTAINER_OF(rule->list.next, + struct cls_rule, list); + + list_remove(&rule->list); + hmap_replace(&table->rules, &rule->hmap_node, &next->hmap_node); } + + if (--table->n_table_rules == 0) { + destroy_table(cls, table); + } + cls->n_rules--; } /* Finds and returns the highest-priority rule in 'cls' that matches 'flow'. * Returns a null pointer if no rules in 'cls' match 'flow'. If multiple rules - * of equal priority match 'flow', returns one arbitrarily. - * - * (When multiple rules of equal priority happen to fall into the same bucket, - * rules added more recently take priority over rules added less recently, but - * this is subject to change and should not be depended upon.) */ + * of equal priority match 'flow', returns one arbitrarily. */ struct cls_rule * classifier_lookup(const struct classifier *cls, const struct flow *flow) { - struct cls_rule *rule = classifier_lookup_exact(cls, flow); - if (!rule) { - rule = classifier_lookup_wild(cls, flow); - } - return rule; -} - -struct cls_rule * -classifier_lookup_exact(const struct classifier *cls, const struct flow *flow) -{ - return (!hmap_is_empty(&cls->exact_table) - ? search_exact_table(cls, flow_hash(flow, 0), flow) - : NULL); -} + struct cls_table *table; + struct cls_rule *best; -struct cls_rule * -classifier_lookup_wild(const struct classifier *cls, const struct flow *flow) -{ - struct cls_rule *best = NULL; - if (cls->n_rules > hmap_count(&cls->exact_table)) { - struct cls_rule target; - int i; - - cls_rule_from_flow(flow, 0, 0, &target); - for (i = 0; i < CLS_N_FIELDS; i++) { - struct cls_rule *rule = search_table(&cls->tables[i], i, &target); - if (rule && (!best || rule->priority > best->priority)) { - best = rule; - } + best = NULL; + HMAP_FOR_EACH (table, hmap_node, &cls->tables) { + struct cls_rule *rule = find_match(table, flow); + if (rule && (!best || rule->priority > best->priority)) { + best = rule; } } return best; } +/* Finds and returns a rule in 'cls' with exactly the same priority and + * matching criteria as 'target'. Returns a null pointer if 'cls' doesn't + * contain an exact match. */ struct cls_rule * classifier_find_rule_exactly(const struct classifier *cls, - const struct flow *target, uint32_t wildcards, - unsigned int priority) + const struct cls_rule *target) { - struct cls_bucket *bucket; - int table_idx; - uint32_t hash; + struct cls_rule *head, *rule; + struct cls_table *table; - if (!wildcards) { - /* Ignores 'priority'. */ - return search_exact_table(cls, flow_hash(target, 0), target); + table = find_table(cls, &target->match.mask); + if (!table) { + return NULL; } - assert(wildcards == (wildcards & OVSFW_ALL)); - table_idx = table_idx_from_wildcards(wildcards); - hash = hash_fields(target, table_idx); - HMAP_FOR_EACH_WITH_HASH (bucket, hmap_node, hash, - &cls->tables[table_idx]) { - if (equal_fields(&bucket->fixed, target, table_idx)) { - struct cls_rule *pos; - LIST_FOR_EACH (pos, node.list, &bucket->rules) { - if (pos->priority < priority) { - return NULL; - } else if (pos->priority == priority && - pos->wc.wildcards == wildcards && - flow_equal(target, &pos->flow)) { - return pos; - } - } + head = find_equal(table, &target->match.flow, + miniflow_hash_in_minimask(&target->match.flow, + &target->match.mask, 0)); + FOR_EACH_RULE_IN_LIST (rule, head) { + if (target->priority >= rule->priority) { + return target->priority == rule->priority ? rule : NULL; } } return NULL; } -/* Checks if the flow defined by 'target' with 'wildcards' at 'priority' - * overlaps with any other rule at the same priority in the classifier. - * Two rules are considered overlapping if a packet could match both. */ -bool -classifier_rule_overlaps(const struct classifier *cls, - const struct flow *target, uint32_t wildcards, - unsigned int priority) +/* Finds and returns a rule in 'cls' with priority 'priority' and exactly the + * same matching criteria as 'target'. Returns a null pointer if 'cls' doesn't + * contain an exact match. */ +struct cls_rule * +classifier_find_match_exactly(const struct classifier *cls, + const struct match *target, + unsigned int priority) { - struct cls_rule target_rule; - const struct hmap *tbl; + struct cls_rule *retval; + struct cls_rule cr; - if (!wildcards) { - return search_exact_table(cls, flow_hash(target, 0), target) ? - true : false; - } + cls_rule_init(&cr, target, priority); + retval = classifier_find_rule_exactly(cls, &cr); + cls_rule_destroy(&cr); - cls_rule_from_flow(target, wildcards, priority, &target_rule); + return retval; +} + +/* Checks if 'target' would overlap any other rule in 'cls'. Two rules are + * considered to overlap if both rules have the same priority and a packet + * could match both. */ +bool +classifier_rule_overlaps(const struct classifier *cls, + const struct cls_rule *target) +{ + struct cls_table *table; - for (tbl = &cls->tables[0]; tbl < &cls->tables[CLS_N_FIELDS]; tbl++) { - struct cls_bucket *bucket; + HMAP_FOR_EACH (table, hmap_node, &cls->tables) { + uint32_t storage[FLOW_U32S]; + struct minimask mask; + struct cls_rule *head; - HMAP_FOR_EACH (bucket, hmap_node, tbl) { + minimask_combine(&mask, &target->match.mask, &table->mask, storage); + HMAP_FOR_EACH (head, hmap_node, &table->rules) { struct cls_rule *rule; - LIST_FOR_EACH (rule, node.list, &bucket->rules) { - if (rule->priority == priority - && rules_match_2wild(rule, &target_rule, 0)) { + FOR_EACH_RULE_IN_LIST (rule, head) { + if (rule->priority == target->priority + && miniflow_equal_in_minimask(&target->match.flow, + &rule->match.flow, &mask)) { return true; } } @@ -339,511 +337,259 @@ classifier_rule_overlaps(const struct classifier *cls, return false; } -/* Ignores target->priority. +/* Returns true if 'rule' exactly matches 'criteria' or if 'rule' is more + * specific than 'criteria'. That is, 'rule' matches 'criteria' and this + * function returns true if, for every field: * - * 'callback' is allowed to delete the rule that is passed as its argument, but - * 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_match(const struct classifier *cls, - const struct cls_rule *target, - int include, cls_cb_func *callback, void *aux) -{ - if (include & CLS_INC_WILD) { - const struct hmap *table; - - for (table = &cls->tables[0]; table < &cls->tables[CLS_N_FIELDS]; - table++) { - struct cls_bucket *bucket, *next_bucket; - - HMAP_FOR_EACH_SAFE (bucket, next_bucket, hmap_node, table) { - /* XXX there is a bit of room for optimization here based on - * rejecting entire buckets on their fixed fields, but it will - * only be worthwhile for big buckets (which we hope we won't - * get anyway, but...) */ - 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, node.list, &bucket->rules) { - if (rules_match_1wild(rule, target, 0)) { - if (prev_rule) { - callback(prev_rule, aux); - } - prev_rule = rule; - } - } - if (prev_rule) { - callback(prev_rule, aux); - } - } - } - } - - if (include & CLS_INC_EXACT) { - if (target->wc.wildcards) { - struct cls_rule *rule, *next_rule; - - HMAP_FOR_EACH_SAFE (rule, next_rule, node.hmap, - &cls->exact_table) { - if (rules_match_1wild(rule, target, 0)) { - callback(rule, aux); - } - } - } else { - /* Optimization: there can be at most one match in the exact - * table. */ - size_t hash = flow_hash(&target->flow, 0); - struct cls_rule *rule = search_exact_table(cls, hash, - &target->flow); - if (rule) { - callback(rule, aux); - } - } - } -} - -/* 'callback' is allowed to delete the rule that is passed as its argument, but - * 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. + * - 'criteria' and 'rule' specify the same (non-wildcarded) value for the + * field, or * - * If 'include' is CLS_INC_EXACT then CLASSIFIER_FOR_EACH_EXACT_RULE(_SAFE) is - * probably easier to use. */ -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, 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, 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, node.hmap, &cls->exact_table) { - callback(rule, aux); - } - } + * - 'criteria' wildcards the field, + * + * Conversely, 'rule' does not match 'criteria' and this function returns false + * if, for at least one field: + * + * - 'criteria' and 'rule' specify different values for the field, or + * + * - 'criteria' specifies a value for the field but 'rule' wildcards it. + * + * Equivalently, the truth table for whether a field matches is: + * + * rule + * + * c wildcard exact + * r +---------+---------+ + * i wild | yes | yes | + * t card | | | + * e +---------+---------+ + * r exact | no |if values| + * i | |are equal| + * a +---------+---------+ + * + * This is the matching rule used by OpenFlow 1.0 non-strict OFPT_FLOW_MOD + * commands and by OpenFlow 1.0 aggregate and flow stats. + * + * Ignores rule->priority. */ +bool +cls_rule_is_loose_match(const struct cls_rule *rule, + const struct minimatch *criteria) +{ + return (!minimask_has_extra(&rule->match.mask, &criteria->mask) + && miniflow_equal_in_minimask(&rule->match.flow, &criteria->flow, + &criteria->mask)); } -static struct cls_bucket *create_bucket(struct hmap *, size_t hash, - const struct flow *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 struct flow *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; -} +/* Iteration. */ -/* 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'). - * - * Returns true if all the compared fields are equal, false otherwise. */ static bool -equal_fields(const struct flow *a, const struct flow *b, int table_idx) -{ - /* XXX The generated code could be better here. */ -#define CLS_FIELD(WILDCARDS, MEMBER, NAME) \ - if (table_idx == CLS_F_IDX_##NAME) { \ - return true; \ - } else if (!equal_bytes(&a->MEMBER, &b->MEMBER, sizeof a->MEMBER)) { \ - return false; \ - } - CLS_FIELDS -#undef CLS_FIELD - - return true; -} - -static int -table_idx_from_wildcards(uint32_t wildcards) +rule_matches(const struct cls_rule *rule, const struct cls_rule *target) { - if (!wildcards) { - return CLS_F_IDX_EXACT; - } -#define CLS_FIELD(WILDCARDS, MEMBER, NAME) \ - if (wildcards & WILDCARDS) { \ - return CLS_F_IDX_##NAME; \ - } - CLS_FIELDS -#undef CLS_FIELD - NOT_REACHED(); + return (!target + || miniflow_equal_in_minimask(&rule->match.flow, + &target->match.flow, + &target->match.mask)); } -/* Inserts 'rule' into 'table'. Returns the rule, if any, that was displaced - * in favor of 'rule'. */ static struct cls_rule * -table_insert(struct hmap *table, struct cls_rule *rule) +search_table(const struct cls_table *table, const struct cls_rule *target) { - struct cls_bucket *bucket; - size_t hash; - - hash = hash_fields(&rule->flow, rule->table_idx); - bucket = find_bucket(table, hash, rule); - if (!bucket) { - bucket = create_bucket(table, hash, &rule->flow); - } - - return bucket_insert(bucket, rule); -} + if (!target || !minimask_has_extra(&table->mask, &target->match.mask)) { + struct cls_rule *rule; -/* Inserts 'rule' into 'bucket', given that 'field' is the first wildcarded - * field in 'rule'. - * - * Returns the rule, if any, that was displaced in favor of 'rule'. */ -static struct cls_rule * -bucket_insert(struct cls_bucket *bucket, struct cls_rule *rule) -{ - struct cls_rule *pos; - LIST_FOR_EACH (pos, node.list, &bucket->rules) { - if (pos->priority == rule->priority) { - if (pos->wc.wildcards == rule->wc.wildcards - && rules_match_1wild(pos, rule, rule->table_idx)) - { - list_replace(&rule->node.list, &pos->node.list); - return pos; + HMAP_FOR_EACH (rule, hmap_node, &table->rules) { + if (rule_matches(rule, target)) { + return rule; } - } else if (pos->priority < rule->priority) { - break; } } - list_insert(&pos->node.list, &rule->node.list); return NULL; } -static struct cls_rule * -insert_exact_rule(struct classifier *cls, struct cls_rule *rule) +/* Initializes 'cursor' for iterating through rules in 'cls': + * + * - If 'target' is null, the cursor will visit every rule in 'cls'. + * + * - If 'target' is nonnull, the cursor will visit each 'rule' in 'cls' + * such that cls_rule_is_loose_match(rule, target) returns true. + * + * Ignores target->priority. */ +void +cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls, + const struct cls_rule *target) { - struct cls_rule *old_rule; - size_t hash; - - hash = flow_hash(&rule->flow, 0); - old_rule = search_exact_table(cls, hash, &rule->flow); - if (old_rule) { - hmap_remove(&cls->exact_table, &old_rule->node.hmap); - } - hmap_insert(&cls->exact_table, &rule->node.hmap, hash); - return old_rule; + cursor->cls = cls; + cursor->target = target && !cls_rule_is_catchall(target) ? target : NULL; } -/* Returns the bucket in 'table' that has the given 'hash' and the same fields - * as 'rule->flow' (up to 'rule->table_idx'), or a null pointer if no bucket - * matches. */ -static struct cls_bucket * -find_bucket(struct hmap *table, size_t hash, const struct cls_rule *rule) +/* Returns the first matching cls_rule in 'cursor''s iteration, or a null + * pointer if there are no matches. */ +struct cls_rule * +cls_cursor_first(struct cls_cursor *cursor) { - struct cls_bucket *bucket; - HMAP_FOR_EACH_WITH_HASH (bucket, hmap_node, hash, table) { - if (equal_fields(&bucket->fixed, &rule->flow, rule->table_idx)) { - return bucket; + struct cls_table *table; + + HMAP_FOR_EACH (table, hmap_node, &cursor->cls->tables) { + struct cls_rule *rule = search_table(table, cursor->target); + if (rule) { + cursor->table = table; + return rule; } } + return NULL; } -/* Creates a bucket and inserts it in 'table' with the given 'hash' and 'fixed' - * values. Returns the new bucket. */ -static struct cls_bucket * -create_bucket(struct hmap *table, size_t hash, const struct flow *fixed) +/* Returns the next matching cls_rule in 'cursor''s iteration, or a null + * pointer if there are no more matches. */ +struct cls_rule * +cls_cursor_next(struct cls_cursor *cursor, struct cls_rule *rule) { - struct cls_bucket *bucket = xmalloc(sizeof *bucket); - list_init(&bucket->rules); - bucket->fixed = *fixed; - hmap_insert(table, &bucket->hmap_node, hash); - return bucket; -} + const struct cls_table *table; + struct cls_rule *next; -/* Returns true if the 'n' bytes in 'a' and 'b' are equal, false otherwise. */ -static inline bool ALWAYS_INLINE -equal_bytes(const void *a, const void *b, size_t n) -{ -#ifdef __i386__ - /* For some reason GCC generates stupid code for memcmp() of small - * constant integer lengths. Help it out. - * - * This function is always inlined, and it is always called with 'n' as a - * compile-time constant, so the switch statement gets optimized out and - * this whole function just expands to an instruction or two. */ - switch (n) { - case 1: - return *(uint8_t *) a == *(uint8_t *) b; + next = next_rule_in_list__(rule); + if (next->priority < rule->priority) { + return next; + } - case 2: - return *(uint16_t *) a == *(uint16_t *) b; + /* 'next' is the head of the list, that is, the rule that is included in + * the table's hmap. (This is important when the classifier contains rules + * that differ only in priority.) */ + rule = next; + HMAP_FOR_EACH_CONTINUE (rule, hmap_node, &cursor->table->rules) { + if (rule_matches(rule, cursor->target)) { + return rule; + } + } - case 4: - return *(uint32_t *) a == *(uint32_t *) b; + table = cursor->table; + HMAP_FOR_EACH_CONTINUE (table, hmap_node, &cursor->cls->tables) { + rule = search_table(table, cursor->target); + if (rule) { + cursor->table = table; + return rule; + } + } - case 6: - return (*(uint32_t *) a == *(uint32_t *) b - && ((uint16_t *) a)[2] == ((uint16_t *) b)[2]); + return NULL; +} + +static struct cls_table * +find_table(const struct classifier *cls, const struct minimask *mask) +{ + struct cls_table *table; - default: - abort(); + HMAP_FOR_EACH_IN_BUCKET (table, hmap_node, minimask_hash(mask, 0), + &cls->tables) { + if (minimask_equal(mask, &table->mask)) { + return table; + } } -#else - /* I hope GCC is smarter on your platform. */ - return !memcmp(a, b, n); -#endif + return NULL; } -/* Returns the 32-bit unsigned integer at 'p'. */ -static inline uint32_t -read_uint32(const void *p) +static struct cls_table * +insert_table(struct classifier *cls, const struct minimask *mask) { - /* GCC optimizes this into a single machine instruction on x86. */ - uint32_t x; - memcpy(&x, p, sizeof x); - return x; -} + struct cls_table *table; -/* Compares the specified field in 'a' and 'b'. Returns true if the fields are - * equal, or if the ofp_match wildcard bits in 'wildcards' are set such that - * non-equal values may be ignored. 'nw_src_mask' and 'nw_dst_mask' must be - * those that would be set for 'wildcards' by cls_rule_set_masks(). - * - * The compared field is the one with wildcard bit or bits 'field_wc', offset - * 'rule_ofs' within cls_rule's "fields" member, and length 'len', in bytes. */ -static inline bool ALWAYS_INLINE -field_matches(const struct flow *a_, const struct flow *b_, - uint32_t wildcards, uint32_t nw_src_mask, uint32_t nw_dst_mask, - uint32_t field_wc, int ofs, int len) -{ - /* This function is always inlined, and it is always called with 'field_wc' - * as a compile-time constant, so the "if" conditionals here generate no - * code. */ - const void *a = (const uint8_t *) a_ + ofs; - const void *b = (const uint8_t *) b_ + ofs; - if (!(field_wc & (field_wc - 1))) { - /* Handle all the single-bit wildcard cases. */ - return wildcards & field_wc || equal_bytes(a, b, len); - } else if (field_wc == OFPFW_NW_SRC_MASK || - field_wc == OFPFW_NW_DST_MASK) { - uint32_t a_ip = read_uint32(a); - uint32_t b_ip = read_uint32(b); - uint32_t mask = (field_wc == OFPFW_NW_SRC_MASK - ? nw_src_mask : nw_dst_mask); - return ((a_ip ^ b_ip) & mask) == 0; - } else { - abort(); - } -} + table = xzalloc(sizeof *table); + hmap_init(&table->rules); + minimask_clone(&table->mask, mask); + hmap_insert(&cls->tables, &table->hmap_node, minimask_hash(mask, 0)); -/* Returns true if 'a' and 'b' match, ignoring fields for which the wildcards - * in 'wildcards' are set. 'nw_src_mask' and 'nw_dst_mask' must be those that - * would be set for 'wildcards' by cls_rule_set_masks(). 'field_idx' is the - * index of the first field to be compared; fields before 'field_idx' are - * assumed to match. (Always returns true if 'field_idx' is CLS_N_FIELDS.) */ -static bool -rules_match(const struct cls_rule *a, const struct cls_rule *b, - uint32_t wildcards, uint32_t nw_src_mask, uint32_t nw_dst_mask, - int field_idx) -{ - /* This is related to Duff's device (see - * http://en.wikipedia.org/wiki/Duff's_device). */ - switch (field_idx) { -#define CLS_FIELD(WILDCARDS, MEMBER, NAME) \ - case CLS_F_IDX_##NAME: \ - if (!field_matches(&a->flow, &b->flow, \ - wildcards, nw_src_mask, nw_dst_mask, \ - WILDCARDS, offsetof(struct flow, MEMBER), \ - sizeof a->flow.MEMBER)) { \ - return false; \ - } \ - /* Fall though */ - CLS_FIELDS -#undef CLS_FIELD - } - return true; + return table; } -/* Returns true if 'fixed' and 'wild' match. All fields in 'fixed' must have - * fixed values; 'wild' may contain wildcards. - * - * 'field_idx' is the index of the first field to be compared; fields before - * 'field_idx' are assumed to match. Always returns true if 'field_idx' is - * CLS_N_FIELDS. */ -static bool -rules_match_1wild(const struct cls_rule *fixed, const struct cls_rule *wild, - int field_idx) +static void +destroy_table(struct classifier *cls, struct cls_table *table) { - return rules_match(fixed, wild, wild->wc.wildcards, wild->wc.nw_src_mask, - wild->wc.nw_dst_mask, field_idx); + minimask_destroy(&table->mask); + hmap_remove(&cls->tables, &table->hmap_node); + hmap_destroy(&table->rules); + free(table); } -/* Returns true if 'wild1' and 'wild2' match, that is, if their fields - * are equal modulo wildcards in 'wild1' or 'wild2'. - * - * 'field_idx' is the index of the first field to be compared; fields before - * 'field_idx' are assumed to match. Always returns true if 'field_idx' is - * CLS_N_FIELDS. */ -static bool -rules_match_2wild(const struct cls_rule *wild1, const struct cls_rule *wild2, - int field_idx) +static struct cls_rule * +find_match(const struct cls_table *table, const struct flow *flow) { - return rules_match(wild1, wild2, - wild1->wc.wildcards | wild2->wc.wildcards, - wild1->wc.nw_src_mask & wild2->wc.nw_src_mask, - wild1->wc.nw_dst_mask & wild2->wc.nw_dst_mask, - field_idx); + uint32_t hash = flow_hash_in_minimask(flow, &table->mask, 0); + struct cls_rule *rule; + + HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &table->rules) { + if (miniflow_equal_flow_in_minimask(&rule->match.flow, flow, + &table->mask)) { + return rule; + } + } + + return NULL; } -/* Searches 'bucket' for a rule that matches 'target'. Returns the - * highest-priority match, if one is found, or a null pointer if there is no - * match. - * - * 'field_idx' must be the index of the first wildcarded field in 'bucket'. */ static struct cls_rule * -search_bucket(struct cls_bucket *bucket, int field_idx, - const struct cls_rule *target) +find_equal(struct cls_table *table, const struct miniflow *flow, uint32_t hash) { - struct cls_rule *pos; + struct cls_rule *head; - if (!equal_fields(&bucket->fixed, &target->flow, field_idx)) { - return NULL; - } - - LIST_FOR_EACH (pos, node.list, &bucket->rules) { - if (rules_match_1wild(target, pos, field_idx)) { - return pos; + HMAP_FOR_EACH_WITH_HASH (head, hmap_node, hash, &table->rules) { + if (miniflow_equal(&head->match.flow, flow)) { + return head; } } return NULL; } -/* Searches 'table' for a rule that matches 'target'. Returns the - * highest-priority match, if one is found, or a null pointer if there is no - * match. - * - * 'field_idx' must be the index of the first wildcarded field in 'table'. */ static struct cls_rule * -search_table(const struct hmap *table, int field_idx, - const struct cls_rule *target) +insert_rule(struct cls_table *table, struct cls_rule *new) { - struct cls_bucket *bucket; + struct cls_rule *head; - switch (hmap_count(table)) { - /* In these special cases there's no need to hash. */ - case 0: + new->hmap_node.hash = miniflow_hash_in_minimask(&new->match.flow, + &new->match.mask, 0); + + head = find_equal(table, &new->match.flow, new->hmap_node.hash); + if (!head) { + hmap_insert(&table->rules, &new->hmap_node, new->hmap_node.hash); + list_init(&new->list); return NULL; - case 1: - bucket = CONTAINER_OF(hmap_first(table), struct cls_bucket, hmap_node); - return search_bucket(bucket, field_idx, target); - } + } else { + /* Scan the list for the insertion point that will keep the list in + * order of decreasing priority. */ + struct cls_rule *rule; + FOR_EACH_RULE_IN_LIST (rule, head) { + if (new->priority >= rule->priority) { + if (rule == head) { + /* 'new' is the new highest-priority flow in the list. */ + hmap_replace(&table->rules, + &rule->hmap_node, &new->hmap_node); + } - HMAP_FOR_EACH_WITH_HASH (bucket, hmap_node, - hash_fields(&target->flow, field_idx), table) { - struct cls_rule *rule = search_bucket(bucket, field_idx, target); - if (rule) { - return rule; + if (new->priority == rule->priority) { + list_replace(&new->list, &rule->list); + return rule; + } else { + list_insert(&rule->list, &new->list); + return NULL; + } + } } + + /* Insert 'new' at the end of the list. */ + list_push_back(&head->list, &new->list); + return NULL; } - return NULL; } static struct cls_rule * -search_exact_table(const struct classifier *cls, size_t hash, - const struct flow *target) +next_rule_in_list__(struct cls_rule *rule) { - struct cls_rule *rule; + struct cls_rule *next = OBJECT_CONTAINING(rule->list.next, next, list); + return next; +} - HMAP_FOR_EACH_WITH_HASH (rule, node.hmap, hash, &cls->exact_table) { - if (flow_equal(&rule->flow, target)) { - return rule; - } - } - return NULL; +static struct cls_rule * +next_rule_in_list(struct cls_rule *rule) +{ + struct cls_rule *next = next_rule_in_list__(rule); + return next->priority < rule->priority ? next : NULL; }