X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=lib%2Fclassifier.c;h=919e05fca456ebdb3af52bf424eb0d44c64c932a;hb=81a76618be9ea195a1e4a881ba9591728891d10b;hp=cdad9c9e1bc8caf44d32c48ec4680caabe2ff027;hpb=5f55c39b21e69025045437ffbd3bb98fe6ce2e89;p=sliver-openvswitch.git diff --git a/lib/classifier.c b/lib/classifier.c index cdad9c9e1..919e05fca 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,136 +19,76 @@ #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 flow_wildcards *); +static struct cls_table *insert_table(struct classifier *, + const struct flow_wildcards *); + +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 flow *, + 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(flow_t, MEMBER), \ - sizeof ((flow_t *)0)->MEMBER, \ - WILDCARDS, \ - #NAME }, - CLS_FIELDS -#undef CLS_FIELD - { sizeof(flow_t), 0, 0, "exact" }, -}; - -static uint32_t hash_fields(const flow_t *, int table_idx); -static bool equal_fields(const flow_t *, const flow_t *, 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 flow_t *); -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. + * + * (OpenFlow uses priorities between 0 and UINT16_MAX, inclusive, but + * internally Open vSwitch supports a wider range.) */ void -cls_rule_from_flow(struct cls_rule *rule, const flow_t *flow, - uint32_t wildcards, unsigned int priority) +cls_rule_init(struct cls_rule *rule, + const struct match *match, unsigned int priority) { - assert(!flow->reserved[0] && !flow->reserved[1] && !flow->reserved[2]); - rule->flow = *flow; - flow_wildcards_init(&rule->wc, wildcards); + 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'. */ -void -cls_rule_from_match(struct cls_rule *rule, const struct ofp_match *match, - unsigned int priority) -{ - uint32_t wildcards; - flow_from_match(&rule->flow, &wildcards, match); - flow_wildcards_init(&rule->wc, wildcards); - rule->priority = rule->wc.wildcards ? priority : UINT16_MAX; - rule->table_idx = table_idx_from_wildcards(rule->wc.wildcards); } -/* 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) +/* 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) { - 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); + return a->priority == b->priority && match_equal(&a->match, &b->match); } -/* Prints cls_rule 'rule', for debugging. - * - * (The output could be improved and expanded, but this was good enough to - * debug the classifier.) */ -void -cls_rule_print(const struct cls_rule *rule) +/* Returns a hash value for 'rule', folding in 'basis'. */ +uint32_t +cls_rule_hash(const struct cls_rule *rule, uint32_t basis) { - printf("wildcards=%x priority=%u ", rule->wc.wildcards, rule->priority); - flow_print(stdout, &rule->flow); - putc('\n', stdout); + return match_hash(&rule->match, hash_int(rule->priority, basis)); } -/* Adjusts pointers around 'old', which must be in classifier 'cls', to - * compensate for it having been moved in memory to 'new' (e.g. due to - * realloc()). - * - * This function cannot be realized in all possible flow classifier - * implementations, so we will probably have to change the interface if we - * change the implementation. Shouldn't be a big deal though. */ +/* Appends a string describing 'rule' to 's'. */ void -cls_rule_moved(struct classifier *cls, struct cls_rule *old, - struct cls_rule *new) +cls_rule_format(const struct cls_rule *rule, struct ds *s) { - if (old != new) { - if (new->wc.wildcards) { - list_moved(&new->node.list); - } else { - hmap_node_moved(&cls->exact_table, - &old->node.hmap, &new->node.hmap); - } - } -} - -/* Replaces 'old', which must be in classifier 'cls', by 'new' (e.g. due to - * realloc()); that is, after calling this function 'new' will be in 'cls' in - * place of 'old'. - * - * 'new' and 'old' must be exactly the same: wildcard the same fields, have the - * same fixed values for non-wildcarded fields, and have the same priority. - * - * The caller takes ownership of 'old' and is thus responsible for freeing it, - * etc., as necessary. - * - * This function cannot be realized in all possible flow classifier - * implementations, so we will probably have to change the interface if we - * change the implementation. Shouldn't be a big deal though. */ -void -cls_rule_replace(struct classifier *cls, const struct cls_rule *old, - struct cls_rule *new) -{ - assert(old != new); - assert(old->wc.wildcards == new->wc.wildcards); - assert(old->priority == new->priority); - - if (new->wc.wildcards) { - list_replace(&new->node.list, &old->node.list); - } else { - hmap_replace(&cls->exact_table, &old->node.hmap, &new->node.hmap); - } + match_format(&rule->match, s, rule->priority); } /* Initializes 'cls' as a classifier that initially contains no classification @@ -156,13 +96,8 @@ cls_rule_replace(struct classifier *cls, const struct cls_rule *old, 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 @@ -171,43 +106,33 @@ 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, - struct cls_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 @@ -219,166 +144,148 @@ classifier_count_exact(const struct classifier *cls) * 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.wc); + if (!table) { + table = insert_table(cls, &rule->match.wc); + } + + 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 free + * 'rule', if this is desirable. */ 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.wc); + 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.) */ -struct cls_rule * -classifier_lookup(const struct classifier *cls, const flow_t *flow) -{ - struct cls_rule *rule = classifier_lookup_exact(cls, flow); - if (!rule) { - rule = classifier_lookup_wild(cls, flow); - } - return rule; -} - + * of equal priority match 'flow', returns one arbitrarily. */ struct cls_rule * -classifier_lookup_exact(const struct classifier *cls, const flow_t *flow) +classifier_lookup(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 flow_t *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(&target, flow, 0, 0); - 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 flow_t *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.wc); + if (!table) { + return NULL; } - assert(wildcards == (wildcards & OFPFW_ALL)); - table_idx = table_idx_from_wildcards(wildcards); - hash = hash_fields(target, table_idx); - HMAP_FOR_EACH_WITH_HASH (bucket, struct cls_bucket, hmap_node, hash, - &cls->tables[table_idx]) { - if (equal_fields(&bucket->fixed, target, table_idx)) { - struct cls_rule *pos; - LIST_FOR_EACH (pos, struct cls_rule, 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, + flow_hash(&target->match.flow, 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 flow_t *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_from_flow(&target_rule, target, wildcards, priority); + return retval; +} - for (tbl = &cls->tables[0]; tbl < &cls->tables[CLS_N_FIELDS]; tbl++) { - struct cls_bucket *bucket; +/* 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; - HMAP_FOR_EACH (bucket, struct cls_bucket, hmap_node, tbl) { + HMAP_FOR_EACH (table, hmap_node, &cls->tables) { + struct flow_wildcards wc; + struct cls_rule *head; + + flow_wildcards_combine(&wc, &target->match.wc, &table->wc); + HMAP_FOR_EACH (head, hmap_node, &table->rules) { struct cls_rule *rule; - LIST_FOR_EACH (rule, struct cls_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 + && flow_equal_except(&target->match.flow, + &rule->match.flow, &wc)) { return true; } } @@ -388,515 +295,266 @@ 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) + * - 'criteria' and 'rule' specify the same (non-wildcarded) value for the + * field, or + * + * - '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 match *criteria) { - 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, - struct cls_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, struct cls_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, struct cls_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); - } - } - } + return (!flow_wildcards_has_extra(&rule->match.wc, &criteria->wc) + && flow_equal_except(&rule->match.flow, &criteria->flow, + &criteria->wc)); } + +/* Iteration. */ -/* '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(const struct classifier *cls, int include, - void (*callback)(struct cls_rule *, void *aux), - void *aux) +static bool +rule_matches(const struct cls_rule *rule, const struct cls_rule *target) { - 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); - } - } + return (!target + || flow_equal_except(&rule->match.flow, &target->match.flow, + &target->match.wc)); } - -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) +static struct cls_rule * +search_table(const struct cls_table *table, const struct cls_rule *target) { - /* 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; \ + if (!target || !flow_wildcards_has_extra(&table->wc, &target->match.wc)) { + struct cls_rule *rule; + + HMAP_FOR_EACH (rule, hmap_node, &table->rules) { + if (rule_matches(rule, target)) { + return rule; + } + } } - CLS_FIELDS -#undef CLS_FIELD - -finish: - a += tmp[0]; - b += tmp[1]; - c += tmp[2]; - HASH_FINAL(a, b, c); - return c; + return NULL; } -/* 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'). +/* Initializes 'cursor' for iterating through rules in 'cls': * - * Returns true if all the compared fields are equal, false otherwise. */ -static bool -equal_fields(const flow_t *a, const flow_t *b, int table_idx) + * - 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) { - /* 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; + cursor->cls = cls; + cursor->target = target; } -static int -table_idx_from_wildcards(uint32_t wildcards) +/* 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) { - if (!wildcards) { - return CLS_F_IDX_EXACT; - } -#define CLS_FIELD(WILDCARDS, MEMBER, NAME) \ - if (wildcards & WILDCARDS) { \ - return CLS_F_IDX_##NAME; \ + 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; + } } - CLS_FIELDS -#undef CLS_FIELD - NOT_REACHED(); + + return NULL; } -/* 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) +/* 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; - size_t hash; + const struct cls_table *table; + struct cls_rule *next; - hash = hash_fields(&rule->flow, rule->table_idx); - bucket = find_bucket(table, hash, rule); - if (!bucket) { - bucket = create_bucket(table, hash, &rule->flow); + next = next_rule_in_list__(rule); + if (next->priority < rule->priority) { + return next; } - return bucket_insert(bucket, rule); -} + /* '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; + } + } -/* 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, struct cls_rule, node.list, &bucket->rules) { - if (pos->priority <= rule->priority) { - if (pos->priority == rule->priority - && pos->wc.wildcards == rule->wc.wildcards - && rules_match_1wild(pos, rule, rule->table_idx)) - { - list_replace(&rule->node.list, &pos->node.list); - return pos; - } - break; + 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; } } - list_insert(&pos->node.list, &rule->node.list); + return NULL; } - -static struct cls_rule * -insert_exact_rule(struct classifier *cls, struct cls_rule *rule) + +static struct cls_table * +find_table(const struct classifier *cls, const struct flow_wildcards *wc) { - 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; -} + struct cls_table *table; -/* 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) -{ - struct cls_bucket *bucket; - HMAP_FOR_EACH_WITH_HASH (bucket, struct cls_bucket, hmap_node, hash, - table) { - if (equal_fields(&bucket->fixed, &rule->flow, rule->table_idx)) { - return bucket; + HMAP_FOR_EACH_IN_BUCKET (table, hmap_node, flow_wildcards_hash(wc, 0), + &cls->tables) { + if (flow_wildcards_equal(wc, &table->wc)) { + return table; } } 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 flow_t *fixed) +static struct cls_table * +insert_table(struct classifier *cls, const struct flow_wildcards *wc) { - struct cls_bucket *bucket = xmalloc(sizeof *bucket); - list_init(&bucket->rules); - bucket->fixed = *fixed; - hmap_insert(table, &bucket->hmap_node, hash); - return bucket; -} + struct cls_table *table; -/* 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; - - case 2: - return *(uint16_t *) a == *(uint16_t *) b; - - case 4: - return *(uint32_t *) a == *(uint32_t *) b; - - case 6: - return (*(uint32_t *) a == *(uint32_t *) b - && ((uint16_t *) a)[2] == ((uint16_t *) b)[2]); - - default: - abort(); - } -#else - /* I hope GCC is smarter on your platform. */ - return !memcmp(a, b, n); -#endif -} + table = xzalloc(sizeof *table); + hmap_init(&table->rules); + table->wc = *wc; + table->is_catchall = flow_wildcards_is_catchall(&table->wc); + hmap_insert(&cls->tables, &table->hmap_node, flow_wildcards_hash(wc, 0)); -/* Returns the 32-bit unsigned integer at 'p'. */ -static inline uint32_t -read_uint32(const void *p) -{ - /* GCC optimizes this into a single machine instruction on x86. */ - uint32_t x; - memcpy(&x, p, sizeof x); - return x; + return 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 flow_t *a_, const flow_t *b_, - uint32_t wildcards, uint32_t nw_src_mask, uint32_t nw_dst_mask, - uint32_t field_wc, int ofs, int len) +static void +destroy_table(struct classifier *cls, struct cls_table *table) { - /* 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(); - } + hmap_remove(&cls->tables, &table->hmap_node); + hmap_destroy(&table->rules); + free(table); } -/* 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) +static struct cls_rule * +find_match(const struct cls_table *table, const struct flow *flow) { - /* 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(flow_t, MEMBER), \ - sizeof a->flow.MEMBER)) { \ - return false; \ - } \ - /* Fall though */ - CLS_FIELDS -#undef CLS_FIELD - } - return true; -} + struct cls_rule *rule; -/* 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) -{ - return rules_match(fixed, wild, wild->wc.wildcards, wild->wc.nw_src_mask, - wild->wc.nw_dst_mask, field_idx); -} + if (table->is_catchall) { + HMAP_FOR_EACH (rule, hmap_node, &table->rules) { + return rule; + } + } else { + struct flow f; + + f = *flow; + flow_zero_wildcards(&f, &table->wc); + HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, flow_hash(&f, 0), + &table->rules) { + if (flow_equal(&f, &rule->match.flow)) { + return rule; + } + } + } -/* 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) -{ - 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); + 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 flow *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, struct cls_rule, 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 (flow_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; + + new->hmap_node.hash = flow_hash(&new->match.flow, 0); - switch (hmap_count(table)) { - /* In these special cases there's no need to hash. */ - case 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, struct cls_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 flow_t *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, struct cls_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; }