X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=lib%2Fclassifier.c;h=e5d226ecb883249687dabed0465fce262d41f46f;hb=refs%2Fheads%2Fmanual;hp=3e0e2150d60c20d412e9ff453b83c98dc39c2d3a;hpb=52ce26ee3b13496f65132996120e59ec29ab64c2;p=openvswitch diff --git a/lib/classifier.c b/lib/classifier.c index 3e0e2150..e5d226ec 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,33 +19,27 @@ #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 *); + const struct minimask *); static struct cls_table *insert_table(struct classifier *, - const struct flow_wildcards *); + const struct minimask *); -static struct cls_table *classifier_first_table(const struct classifier *); -static struct cls_table *classifier_next_table(const struct classifier *, - const struct cls_table *); static void destroy_table(struct classifier *, struct cls_table *); -static bool should_include(const struct cls_table *, int include); - 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 *find_equal(struct cls_table *, + const struct miniflow *, uint32_t hash); static struct cls_rule *insert_rule(struct cls_table *, struct cls_rule *); -static bool flow_equal_except(const struct flow *, const struct flow *, - const struct flow_wildcards *); -static void zero_wildcards(struct flow *, const struct flow_wildcards *); - /* 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)) @@ -54,122 +48,84 @@ static void zero_wildcards(struct flow *, const struct flow_wildcards *); (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. */ -static struct cls_table * -cls_table_from_hmap_node(const struct hmap_node *node) -{ - return node ? CONTAINER_OF(node, struct cls_table, hmap_node) : NULL; -} - -static struct cls_rule * -cls_rule_from_hmap_node(const struct hmap_node *node) -{ - return node ? CONTAINER_OF(node, struct cls_rule, hmap_node) : NULL; -} - -/* Returns the cls_table within 'cls' that has no wildcards, or NULL if there - * is none. */ -struct cls_table * -classifier_exact_table(const struct classifier *cls) -{ - struct flow_wildcards exact_wc; - flow_wildcards_init_exact(&exact_wc); - return find_table(cls, &exact_wc); -} - -/* Returns the first rule in 'table', or a null pointer if 'table' is NULL. */ -struct cls_rule * -cls_table_first_rule(const struct cls_table *table) +/* 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_init(struct cls_rule *rule, + const struct match *match, unsigned int priority) { - return table ? cls_rule_from_hmap_node(hmap_first(&table->rules)) : NULL; + minimatch_init(&rule->match, match); + rule->priority = priority; } -/* Returns the next rule in 'table' following 'rule', or a null pointer if - * 'rule' is the last rule in 'table'. */ -struct cls_rule * -cls_table_next_rule(const struct cls_table *table, const struct cls_rule *rule) +/* Same as cls_rule_init() for initialization from a "struct minimatch". */ +void +cls_rule_init_from_minimatch(struct cls_rule *rule, + const struct minimatch *match, + unsigned int priority) { - struct cls_rule *next - = CONTAINER_OF(rule->list.next, struct cls_rule, hmap_node); - - return (next->priority < rule->priority - ? next - : cls_rule_from_hmap_node(hmap_next(&table->rules, - &next->hmap_node))); + minimatch_clone(&rule->match, match); + rule->priority = priority; } -static void -cls_rule_init__(struct cls_rule *rule, - const struct flow *flow, uint32_t wildcards) +/* 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) { - rule->flow = *flow; - flow_wildcards_init(&rule->wc, wildcards); - cls_rule_zero_wildcarded_fields(rule); + minimatch_clone(&dst->match, &src->match); + dst->priority = src->priority; } -/* Converts the flow in 'flow' into a cls_rule in 'rule', with the given - * 'wildcards' and 'priority'.*/ +/* Frees memory referenced by 'rule'. Doesn't free 'rule' itself (it's + * normally embedded into a larger structure). + * + * ('rule' must not currently be in a classifier.) */ void -cls_rule_from_flow(const struct flow *flow, uint32_t wildcards, - unsigned int priority, struct cls_rule *rule) +cls_rule_destroy(struct cls_rule *rule) { - cls_rule_init__(rule, flow, wildcards); - rule->priority = priority; + minimatch_destroy(&rule->match); } -/* Converts the ofp_match in 'match' (with format 'flow_format', one of NXFF_*) - * into a cls_rule in 'rule', with the given 'priority'. 'cookie' is used - * when 'flow_format' is NXFF_TUN_ID_FROM_COOKIE. */ -void -cls_rule_from_match(const struct ofp_match *match, unsigned int priority, - int flow_format, uint64_t cookie, - 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) { - uint32_t wildcards; - struct flow flow; - - flow_from_match(match, flow_format, cookie, &flow, &wildcards); - cls_rule_init__(rule, &flow, wildcards); - rule->priority = rule->wc.wildcards ? priority : UINT16_MAX; + return a->priority == b->priority && minimatch_equal(&a->match, &b->match); } -/* For each bit or field wildcarded in 'rule', sets the corresponding bit or - * field in 'flow' to all-0-bits. It is important to maintain this invariant - * in a clr_rule that might be inserted into a classifier. - * - * It is never necessary to call this function directly for a cls_rule that is - * initialized or modified only by cls_rule_*() functions. It is useful to - * restore the invariant in a cls_rule whose 'wc' member is modified by hand. - */ -void -cls_rule_zero_wildcarded_fields(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) { - zero_wildcards(&rule->flow, &rule->wc); + return minimatch_hash(&rule->match, hash_int(rule->priority, basis)); } -/* 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) +/* Appends a string describing 'rule' to 's'. */ +void +cls_rule_format(const struct cls_rule *rule, struct ds *s) { - 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_format(&rule->match, s, rule->priority); } -/* 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 true if 'rule' matches every packet, false otherwise. */ +bool +cls_rule_is_catchall(const struct cls_rule *rule) { - printf("wildcards=%x priority=%u ", rule->wc.wildcards, rule->priority); - flow_print(stdout, &rule->flow); - putc('\n', stdout); + return minimask_is_catchall(&rule->match.mask); } /* Initializes 'cls' as a classifier that initially contains no classification @@ -205,42 +161,35 @@ 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) -{ - struct cls_table *exact_table = classifier_exact_table(cls); - return exact_table ? exact_table->n_table_rules : 0; -} - /* 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_rule; struct cls_table *table; - table = find_table(cls, &rule->wc); + table = find_table(cls, &rule->match.mask); if (!table) { - table = insert_table(cls, &rule->wc); + table = insert_table(cls, &rule->match.mask); } old_rule = insert_rule(table, rule); @@ -251,16 +200,30 @@ classifier_insert(struct classifier *cls, struct cls_rule *rule) return old_rule; } -/* Removes 'rule' from 'cls'. It is the caller's responsibility to free - * 'rule', if this is desirable. */ +/* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller + * must not modify or free it. + * + * '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(struct classifier *cls, struct cls_rule *rule) +{ + struct cls_rule *displaced_rule = classifier_replace(cls, rule); + assert(!displaced_rule); +} + +/* 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) { struct cls_rule *head; struct cls_table *table; - table = find_table(cls, &rule->wc); - head = find_equal(table, &rule->flow, rule->hmap_node.hash); + 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)) { @@ -273,7 +236,7 @@ classifier_remove(struct classifier *cls, struct cls_rule *rule) hmap_replace(&table->rules, &rule->hmap_node, &next->hmap_node); } - if (--table->n_table_rules == 0 && !table->n_refs) { + if (--table->n_table_rules == 0) { destroy_table(cls, table); } @@ -282,24 +245,18 @@ classifier_remove(struct classifier *cls, struct cls_rule *rule) /* 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. - * - * 'include' is a combination of CLS_INC_* values that specify tables to - * include in the search. */ + * of equal priority match 'flow', returns one arbitrarily. */ struct cls_rule * -classifier_lookup(const struct classifier *cls, const struct flow *flow, - int include) +classifier_lookup(const struct classifier *cls, const struct flow *flow) { struct cls_table *table; struct cls_rule *best; best = NULL; HMAP_FOR_EACH (table, hmap_node, &cls->tables) { - if (should_include(table, include)) { - struct cls_rule *rule = find_match(table, flow); - if (rule && (!best || rule->priority > best->priority)) { - best = rule; - } + struct cls_rule *rule = find_match(table, flow); + if (rule && (!best || rule->priority > best->priority)) { + best = rule; } } return best; @@ -307,10 +264,7 @@ classifier_lookup(const struct classifier *cls, const struct flow *flow, /* 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. - * - * Priority is ignored for exact-match rules (because OpenFlow 1.0 always - * treats exact-match rules as highest priority). */ + * contain an exact match. */ struct cls_rule * classifier_find_rule_exactly(const struct classifier *cls, const struct cls_rule *target) @@ -318,15 +272,14 @@ classifier_find_rule_exactly(const struct classifier *cls, struct cls_rule *head, *rule; struct cls_table *table; - table = find_table(cls, &target->wc); + table = find_table(cls, &target->match.mask); if (!table) { return NULL; } - head = find_equal(table, &target->flow, flow_hash(&target->flow, 0)); - if (!target->wc.wildcards) { - return head; - } + 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; @@ -335,6 +288,24 @@ classifier_find_rule_exactly(const struct classifier *cls, return NULL; } +/* 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 *retval; + struct cls_rule cr; + + cls_rule_init(&cr, target, priority); + retval = classifier_find_rule_exactly(cls, &cr); + cls_rule_destroy(&cr); + + 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. */ @@ -345,16 +316,18 @@ classifier_rule_overlaps(const struct classifier *cls, struct cls_table *table; HMAP_FOR_EACH (table, hmap_node, &cls->tables) { - struct flow_wildcards wc; + uint32_t storage[FLOW_U32S]; + struct minimask mask; struct cls_rule *head; - flow_wildcards_combine(&wc, &target->wc, &table->wc); + minimask_combine(&mask, &target->match.mask, &table->mask, storage); HMAP_FOR_EACH (head, hmap_node, &table->rules) { struct cls_rule *rule; FOR_EACH_RULE_IN_LIST (rule, head) { if (rule->priority == target->priority - && flow_equal_except(&target->flow, &rule->flow, &wc)) { + && miniflow_equal_in_minimask(&target->match.flow, + &rule->match.flow, &mask)) { return true; } } @@ -364,123 +337,151 @@ classifier_rule_overlaps(const struct classifier *cls, return false; } -/* Searches 'cls' for rules that exactly match 'target' or are more specific - * than 'target'. That is, a given 'rule' matches 'target' if, for every - * field: +/* 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: * - * - 'target' and 'rule' specify the same (non-wildcarded) value for the + * - 'criteria' and 'rule' specify the same (non-wildcarded) value for the * field, or * - * - 'target' wildcards the field, + * - 'criteria' wildcards the field, * - * but not if: + * Conversely, 'rule' does not match 'criteria' and this function returns false + * if, for at least one field: * - * - 'target' and 'rule' specify different values for the field, or + * - 'criteria' and 'rule' specify different values for the field, or * - * - 'target' specifies a value for the field but 'rule' wildcards it. + * - 'criteria' specifies a value for the field but 'rule' wildcards it. * * Equivalently, the truth table for whether a field matches is: * * rule * - * wildcard exact - * +---------+---------+ - * t wild | yes | yes | - * a card | | | + * c wildcard exact * r +---------+---------+ - * g exact | no |if values| - * e | |are equal| - * t +---------+---------+ + * 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 target->priority. - * - * '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 have the same - * wildcards as the argument rule. */ -void -classifier_for_each_match(const struct classifier *cls_, - const struct cls_rule *target, - int include, cls_cb_func *callback, void *aux) -{ - struct classifier *cls = (struct classifier *) cls_; - struct cls_table *table, *next_table; - - for (table = classifier_first_table(cls); table; table = next_table) { - if (should_include(table, include) - && !flow_wildcards_has_extra(&table->wc, &target->wc)) { - /* We have eliminated the "no" case in the truth table above. Two - * of the three remaining cases are trivial. We only need to check - * the fourth case, where both 'rule' and 'target' require an exact - * match. */ - struct cls_rule *head, *next_head; - - table->n_refs++; - HMAP_FOR_EACH_SAFE (head, next_head, hmap_node, &table->rules) { - if (flow_equal_except(&head->flow, &target->flow, - &target->wc)) { - struct cls_rule *rule, *next_rule; - - FOR_EACH_RULE_IN_LIST_SAFE (rule, next_rule, head) { - callback(rule, aux); - } - } - } - next_table = classifier_next_table(cls, table); - if (!--table->n_refs && !table->n_table_rules) { - destroy_table(cls, table); + * 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)); +} + +/* Iteration. */ + +static bool +rule_matches(const struct cls_rule *rule, const struct cls_rule *target) +{ + return (!target + || miniflow_equal_in_minimask(&rule->match.flow, + &target->match.flow, + &target->match.mask)); +} + +static struct cls_rule * +search_table(const struct cls_table *table, const struct cls_rule *target) +{ + if (!target || !minimask_has_extra(&table->mask, &target->match.mask)) { + struct cls_rule *rule; + + HMAP_FOR_EACH (rule, hmap_node, &table->rules) { + if (rule_matches(rule, target)) { + return rule; } - } else { - next_table = classifier_next_table(cls, table); } } + return NULL; } -/* '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 have the same - * wildcards as the argument 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. * - * If 'include' is CLS_INC_EXACT then CLASSIFIER_FOR_EACH_EXACT_RULE is - * probably easier to use. */ + * Ignores target->priority. */ void -classifier_for_each(const struct classifier *cls_, int include, - cls_cb_func *callback, void *aux) +cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls, + const struct cls_rule *target) { - struct classifier *cls = (struct classifier *) cls_; - struct cls_table *table, *next_table; + cursor->cls = cls; + cursor->target = target && !cls_rule_is_catchall(target) ? target : NULL; +} - for (table = classifier_first_table(cls); table; table = next_table) { - if (should_include(table, include)) { - struct cls_rule *head, *next_head; +/* 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_table *table; - table->n_refs++; - HMAP_FOR_EACH_SAFE (head, next_head, hmap_node, &table->rules) { - struct cls_rule *rule, *next_rule; + 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; + } + } - FOR_EACH_RULE_IN_LIST_SAFE (rule, next_rule, head) { - callback(rule, aux); - } - } - next_table = classifier_next_table(cls, table); - if (!--table->n_refs && !table->n_table_rules) { - destroy_table(cls, table); - } - } else { - next_table = classifier_next_table(cls, table); + return NULL; +} + +/* 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) +{ + const struct cls_table *table; + struct cls_rule *next; + + next = next_rule_in_list__(rule); + if (next->priority < rule->priority) { + return next; + } + + /* '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; + } + } + + 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; } } + + return NULL; } static struct cls_table * -find_table(const struct classifier *cls, const struct flow_wildcards *wc) +find_table(const struct classifier *cls, const struct minimask *mask) { struct cls_table *table; - HMAP_FOR_EACH_IN_BUCKET (table, hmap_node, flow_wildcards_hash(wc), + HMAP_FOR_EACH_IN_BUCKET (table, hmap_node, minimask_hash(mask, 0), &cls->tables) { - if (flow_wildcards_equal(wc, &table->wc)) { + if (minimask_equal(mask, &table->mask)) { return table; } } @@ -488,72 +489,50 @@ find_table(const struct classifier *cls, const struct flow_wildcards *wc) } static struct cls_table * -insert_table(struct classifier *cls, const struct flow_wildcards *wc) +insert_table(struct classifier *cls, const struct minimask *mask) { struct cls_table *table; table = xzalloc(sizeof *table); hmap_init(&table->rules); - table->wc = *wc; - hmap_insert(&cls->tables, &table->hmap_node, flow_wildcards_hash(wc)); + minimask_clone(&table->mask, mask); + hmap_insert(&cls->tables, &table->hmap_node, minimask_hash(mask, 0)); return table; } -static struct cls_table * -classifier_first_table(const struct classifier *cls) -{ - return cls_table_from_hmap_node(hmap_first(&cls->tables)); -} - -static struct cls_table * -classifier_next_table(const struct classifier *cls, - const struct cls_table *table) -{ - return cls_table_from_hmap_node(hmap_next(&cls->tables, - &table->hmap_node)); -} - static void destroy_table(struct classifier *cls, struct cls_table *table) { + minimask_destroy(&table->mask); hmap_remove(&cls->tables, &table->hmap_node); hmap_destroy(&table->rules); free(table); } -/* Returns true if 'table' should be included by an operation with the - * specified 'include' (a combination of CLS_INC_*). */ -static bool -should_include(const struct cls_table *table, int include) -{ - return include & (table->wc.wildcards ? CLS_INC_WILD : CLS_INC_EXACT); -} - static struct cls_rule * find_match(const struct cls_table *table, const struct flow *flow) { + uint32_t hash = flow_hash_in_minimask(flow, &table->mask, 0); struct cls_rule *rule; - struct flow f; - f = *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->flow)) { + 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; } static struct cls_rule * -find_equal(struct cls_table *table, const struct flow *flow, uint32_t hash) +find_equal(struct cls_table *table, const struct miniflow *flow, uint32_t hash) { struct cls_rule *head; HMAP_FOR_EACH_WITH_HASH (head, hmap_node, hash, &table->rules) { - if (flow_equal(&head->flow, flow)) { + if (miniflow_equal(&head->match.flow, flow)) { return head; } } @@ -565,9 +544,10 @@ insert_rule(struct cls_table *table, struct cls_rule *new) { struct cls_rule *head; - new->hmap_node.hash = flow_hash(&new->flow, 0); + new->hmap_node.hash = miniflow_hash_in_minimask(&new->match.flow, + &new->match.mask, 0); - head = find_equal(table, &new->flow, new->hmap_node.hash); + 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); @@ -601,75 +581,15 @@ insert_rule(struct cls_table *table, struct cls_rule *new) } static struct cls_rule * -next_rule_in_list(struct cls_rule *rule) +next_rule_in_list__(struct cls_rule *rule) { struct cls_rule *next = OBJECT_CONTAINING(rule->list.next, next, list); - return next->priority < rule->priority ? next : NULL; -} - -static bool -flow_equal_except(const struct flow *a, const struct flow *b, - const struct flow_wildcards *wildcards) -{ - const uint32_t wc = wildcards->wildcards; - - BUILD_ASSERT_DECL(FLOW_SIG_SIZE == 37); - - return ((wc & NXFW_TUN_ID || a->tun_id == b->tun_id) - && !((a->nw_src ^ b->nw_src) & wildcards->nw_src_mask) - && !((a->nw_dst ^ b->nw_dst) & wildcards->nw_dst_mask) - && (wc & OFPFW_IN_PORT || a->in_port == b->in_port) - && (wc & OFPFW_DL_VLAN || a->dl_vlan == b->dl_vlan) - && (wc & OFPFW_DL_TYPE || a->dl_type == b->dl_type) - && (wc & OFPFW_TP_SRC || a->tp_src == b->tp_src) - && (wc & OFPFW_TP_DST || a->tp_dst == b->tp_dst) - && (wc & OFPFW_DL_SRC || eth_addr_equals(a->dl_src, b->dl_src)) - && (wc & OFPFW_DL_DST || eth_addr_equals(a->dl_dst, b->dl_dst)) - && (wc & OFPFW_NW_PROTO || a->nw_proto == b->nw_proto) - && (wc & OFPFW_DL_VLAN_PCP || a->dl_vlan_pcp == b->dl_vlan_pcp) - && (wc & OFPFW_NW_TOS || a->nw_tos == b->nw_tos)); + return next; } -static void -zero_wildcards(struct flow *flow, const struct flow_wildcards *wildcards) +static struct cls_rule * +next_rule_in_list(struct cls_rule *rule) { - const uint32_t wc = wildcards->wildcards; - - BUILD_ASSERT_DECL(FLOW_SIG_SIZE == 37); - - if (wc & NXFW_TUN_ID) { - flow->tun_id = 0; - } - flow->nw_src &= wildcards->nw_src_mask; - flow->nw_dst &= wildcards->nw_dst_mask; - if (wc & OFPFW_IN_PORT) { - flow->in_port = 0; - } - if (wc & OFPFW_DL_VLAN) { - flow->dl_vlan = 0; - } - if (wc & OFPFW_DL_TYPE) { - flow->dl_type = 0; - } - if (wc & OFPFW_TP_SRC) { - flow->tp_src = 0; - } - if (wc & OFPFW_TP_DST) { - flow->tp_dst = 0; - } - if (wc & OFPFW_DL_SRC) { - memset(flow->dl_src, 0, sizeof flow->dl_src); - } - if (wc & OFPFW_DL_DST) { - memset(flow->dl_dst, 0, sizeof flow->dl_dst); - } - if (wc & OFPFW_NW_PROTO) { - flow->nw_proto = 0; - } - if (wc & OFPFW_DL_VLAN_PCP) { - flow->dl_vlan_pcp = 0; - } - if (wc & OFPFW_NW_TOS) { - flow->nw_tos = 0; - } + struct cls_rule *next = next_rule_in_list__(rule); + return next->priority < rule->priority ? next : NULL; }