X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=lib%2Fclassifier.c;h=a717bd347177fedc319f6075812e4c8c6ff2d067;hb=bbb8dee92d639331e8bd81823638267dcc895396;hp=f568f6196b383d9b4f2993f87f10fed8ebc4d71b;hpb=3c4486a5f784731b1cb289d187ad9d9e100407c3;p=sliver-openvswitch.git diff --git a/lib/classifier.c b/lib/classifier.c index f568f6196..a717bd347 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, 2013 Nicira, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -16,33 +16,36 @@ #include #include "classifier.h" -#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 void update_tables_after_insertion(struct classifier *, + struct cls_table *, + unsigned int new_priority); +static void update_tables_after_removal(struct classifier *, + struct cls_table *, + unsigned int del_priority); + 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 *); - -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 *); +static struct cls_rule *find_equal(struct cls_table *, + const struct miniflow *, uint32_t hash); +static struct cls_rule *insert_rule(struct classifier *, + 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) \ @@ -52,319 +55,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) -{ - return table ? cls_rule_from_hmap_node(hmap_first(&table->rules)) : NULL; -} - -/* 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) -{ - struct cls_rule *next - = CONTAINER_OF(rule->list.next, struct cls_rule, list); - - return (next->priority < rule->priority - ? next - : cls_rule_from_hmap_node(hmap_next(&table->rules, - &next->hmap_node))); -} - -/* Converts the flow in 'flow' into a cls_rule in 'rule', with the given - * 'wildcards' and 'priority'. */ -void -cls_rule_init(const struct flow *flow, const struct flow_wildcards *wildcards, - unsigned int priority, struct cls_rule *rule) -{ - rule->flow = *flow; - rule->wc = *wildcards; - rule->priority = priority; - cls_rule_zero_wildcarded_fields(rule); -} - -/* Converts the flow in 'flow' into an exact-match cls_rule in 'rule', with the - * given 'priority'. (For OpenFlow 1.0, exact-match rule are always highest - * priority, so 'priority' should be at least 65535.) */ +/* 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_exact(const struct flow *flow, - 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_exact(&rule->wc); + minimatch_init(&rule->match, match); rule->priority = priority; } -/* 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) -{ - flow_from_match(match, flow_format, cookie, &rule->flow, &rule->wc); - rule->priority = !rule->wc.wildcards ? UINT16_MAX : priority; - cls_rule_zero_wildcarded_fields(rule); -} - -/* Initializes 'rule' as a "catch-all" rule that matches every packet, with - * priority 'priority'. */ +/* Same as cls_rule_init() for initialization from a "struct minimatch". */ void -cls_rule_init_catchall(struct cls_rule *rule, unsigned int priority) +cls_rule_init_from_minimatch(struct cls_rule *rule, + const struct minimatch *match, + unsigned int priority) { - memset(&rule->flow, 0, sizeof rule->flow); - flow_wildcards_init(&rule->wc, OVSFW_ALL | FWW_ALL); + minimatch_clone(&rule->match, match); rule->priority = priority; } -/* 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. +/* Initializes 'dst' as a copy of 'src'. * - * 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. - */ + * The caller must eventually destroy 'rule' with cls_rule_destroy(). */ void -cls_rule_zero_wildcarded_fields(struct cls_rule *rule) +cls_rule_clone(struct cls_rule *dst, const struct cls_rule *src) { - zero_wildcards(&rule->flow, &rule->wc); -} - -void -cls_rule_set_in_port(struct cls_rule *rule, uint16_t odp_port) -{ - rule->wc.wildcards &= ~OFPFW_IN_PORT; - rule->flow.in_port = odp_port; -} - -void -cls_rule_set_dl_type(struct cls_rule *rule, ovs_be16 dl_type) -{ - rule->wc.wildcards &= ~OFPFW_DL_TYPE; - rule->flow.dl_type = dl_type; -} - -void -cls_rule_set_dl_src(struct cls_rule *rule, const uint8_t dl_src[ETH_ADDR_LEN]) -{ - rule->wc.wildcards &= ~OFPFW_DL_SRC; - memcpy(rule->flow.dl_src, dl_src, ETH_ADDR_LEN); + minimatch_clone(&dst->match, &src->match); + dst->priority = src->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_set_dl_dst(struct cls_rule *rule, const uint8_t dl_dst[ETH_ADDR_LEN]) +cls_rule_destroy(struct cls_rule *rule) { - rule->wc.wildcards &= ~(OFPFW_DL_DST | FWW_ETH_MCAST); - memcpy(rule->flow.dl_dst, dl_dst, ETH_ADDR_LEN); + 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_set_dl_tci(struct cls_rule *rule, ovs_be16 tci) +cls_rule_equal(const struct cls_rule *a, const struct cls_rule *b) { - return cls_rule_set_dl_tci_masked(rule, tci, htons(0xffff)); + return a->priority == b->priority && minimatch_equal(&a->match, &b->match); } -bool -cls_rule_set_dl_tci_masked(struct cls_rule *rule, ovs_be16 tci, ovs_be16 mask) -{ - switch (ntohs(mask)) { - case 0xffff: - if (tci == htons(0)) { - /* Match only packets that have no 802.1Q header. */ - rule->wc.wildcards &= ~(OFPFW_DL_VLAN | OFPFW_DL_VLAN_PCP); - rule->flow.dl_vlan = htons(OFP_VLAN_NONE); - rule->flow.dl_vlan_pcp = 0; - return true; - } else if (tci & htons(VLAN_CFI)) { - /* Match only packets that have a specific 802.1Q VID and PCP. */ - rule->wc.wildcards &= ~(OFPFW_DL_VLAN | OFPFW_DL_VLAN_PCP); - rule->flow.dl_vlan = htons(vlan_tci_to_vid(tci)); - rule->flow.dl_vlan_pcp = vlan_tci_to_pcp(tci); - return true; - } else { - /* Impossible. */ - return false; - } - - case 0x1fff: - if (!(tci & htons(VLAN_CFI))) { - return false; - } else { - /* Match only packets that have a specific 802.1Q VID. */ - cls_rule_set_dl_vlan(rule, tci & htons(VLAN_VID_MASK)); - rule->wc.wildcards |= OFPFW_DL_VLAN_PCP; - rule->flow.dl_vlan_pcp = 0; - return true; - } - - case 0xf000: - if (!(tci & htons(VLAN_CFI))) { - return false; - } else { - /* Match only packets that have a specific 802.1Q PCP. */ - cls_rule_set_dl_vlan_pcp(rule, vlan_tci_to_pcp(tci)); - rule->wc.wildcards |= OFPFW_DL_VLAN; - rule->flow.dl_vlan = 0; - return true; - } - - case 0x0000: - /* Match anything. */ - rule->wc.wildcards |= OFPFW_DL_VLAN | OFPFW_DL_VLAN_PCP; - rule->flow.dl_vlan = htons(0); - rule->flow.dl_vlan_pcp = 0; - return true; - - default: - return false; - } -} - -void -cls_rule_set_dl_vlan(struct cls_rule *rule, ovs_be16 dl_vlan) -{ - if (dl_vlan != htons(OFP_VLAN_NONE)) { - dl_vlan &= htons(VLAN_VID_MASK); - } - - rule->wc.wildcards &= ~OFPFW_DL_VLAN; - rule->flow.dl_vlan = dl_vlan; -} - -void -cls_rule_set_dl_vlan_pcp(struct cls_rule *rule, uint8_t dl_vlan_pcp) +/* Returns a hash value for 'rule', folding in 'basis'. */ +uint32_t +cls_rule_hash(const struct cls_rule *rule, uint32_t basis) { - rule->wc.wildcards &= ~OFPFW_DL_VLAN_PCP; - rule->flow.dl_vlan_pcp = dl_vlan_pcp & 0x07; + return minimatch_hash(&rule->match, hash_int(rule->priority, basis)); } +/* Appends a string describing 'rule' to 's'. */ void -cls_rule_set_tp_src(struct cls_rule *rule, ovs_be16 tp_src) +cls_rule_format(const struct cls_rule *rule, struct ds *s) { - rule->wc.wildcards &= ~OFPFW_TP_SRC; - rule->flow.tp_src = tp_src; -} - -void -cls_rule_set_tp_dst(struct cls_rule *rule, ovs_be16 tp_dst) -{ - rule->wc.wildcards &= ~OFPFW_TP_DST; - rule->flow.tp_dst = tp_dst; -} - -void -cls_rule_set_nw_proto(struct cls_rule *rule, uint8_t nw_proto) -{ - rule->wc.wildcards &= ~OFPFW_NW_PROTO; - rule->flow.nw_proto = nw_proto; -} - -void -cls_rule_set_nw_src(struct cls_rule *rule, ovs_be32 nw_src) -{ - cls_rule_set_nw_src_masked(rule, nw_src, htonl(UINT32_MAX)); + minimatch_format(&rule->match, s, rule->priority); } +/* Returns true if 'rule' matches every packet, false otherwise. */ bool -cls_rule_set_nw_src_masked(struct cls_rule *rule, ovs_be32 ip, ovs_be32 mask) +cls_rule_is_catchall(const struct cls_rule *rule) { - if (flow_wildcards_set_nw_src_mask(&rule->wc, mask)) { - rule->flow.nw_src = ip & mask; - return true; - } else { - return false; - } -} - -void -cls_rule_set_nw_dst(struct cls_rule *rule, ovs_be32 nw_dst) -{ - cls_rule_set_nw_dst_masked(rule, nw_dst, htonl(UINT32_MAX)); -} - -bool -cls_rule_set_nw_dst_masked(struct cls_rule *rule, ovs_be32 ip, ovs_be32 mask) -{ - if (flow_wildcards_set_nw_dst_mask(&rule->wc, mask)) { - rule->flow.nw_dst = ip & mask; - return true; - } else { - return false; - } -} - -void -cls_rule_set_nw_tos(struct cls_rule *rule, uint8_t nw_tos) -{ - rule->wc.wildcards &= ~OFPFW_NW_TOS; - rule->flow.nw_tos = nw_tos & IP_DSCP_MASK; -} - -void -cls_rule_set_icmp_type(struct cls_rule *rule, uint8_t icmp_type) -{ - rule->wc.wildcards &= ~OFPFW_ICMP_TYPE; - rule->flow.icmp_type = htons(icmp_type); - -} - -void -cls_rule_set_icmp_code(struct cls_rule *rule, uint8_t icmp_code) -{ - rule->wc.wildcards &= ~OFPFW_ICMP_CODE; - rule->flow.icmp_code = htons(icmp_code); -} - -/* 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) -{ - 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); -} - -/* 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) -{ - 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 @@ -374,6 +142,7 @@ classifier_init(struct classifier *cls) { cls->n_rules = 0; hmap_init(&cls->tables); + list_init(&cls->tables_priority); } /* Destroys 'cls'. Rules within 'cls', if any, are not freed; this is the @@ -385,9 +154,7 @@ classifier_destroy(struct classifier *cls) struct cls_table *table, *next_table; HMAP_FOR_EACH_SAFE (table, next_table, hmap_node, &cls->tables) { - hmap_destroy(&table->rules); - hmap_remove(&cls->tables, &table->hmap_node); - free(table); + destroy_table(cls, table); } hmap_destroy(&cls->tables); } @@ -400,45 +167,38 @@ 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); + old_rule = insert_rule(cls, table, rule); if (!old_rule) { table->n_table_rules++; cls->n_rules++; @@ -446,16 +206,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); + ovs_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)) { @@ -468,27 +242,53 @@ 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); + } else { + update_tables_after_removal(cls, table, rule->priority); } - 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. */ + * of equal priority match 'flow', returns one arbitrarily. + * + * If a rule is found and 'wc' is non-null, bitwise-OR's 'wc' with the + * set of bits that were significant in the lookup. At some point + * earlier, 'wc' should have been initialized (e.g., by + * flow_wildcards_init_catchall()). */ struct cls_rule * -classifier_lookup(const struct classifier *cls, const struct flow *flow) +classifier_lookup(const struct classifier *cls, const struct flow *flow, + struct flow_wildcards *wc) { struct cls_table *table; struct cls_rule *best; best = NULL; - HMAP_FOR_EACH (table, hmap_node, &cls->tables) { + LIST_FOR_EACH (table, list_node, &cls->tables_priority) { struct cls_rule *rule = find_match(table, flow); - if (rule && (!best || rule->priority > best->priority)) { + + if (wc) { + flow_wildcards_fold_minimask(wc, &table->mask); + } + if (rule) { best = rule; + LIST_FOR_EACH_CONTINUE (table, list_node, &cls->tables_priority) { + if (table->max_priority <= best->priority) { + /* Tables in descending priority order, + * can not find anything better. */ + return best; + } + rule = find_match(table, flow); + if (wc) { + flow_wildcards_fold_minimask(wc, &table->mask); + } + if (rule && rule->priority > best->priority) { + best = rule; + } + } + break; } } return best; @@ -496,10 +296,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) @@ -507,15 +304,19 @@ 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; + /* Skip if there is no hope. */ + if (target->priority > table->max_priority) { + return NULL; } + + 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; @@ -524,6 +325,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. */ @@ -533,17 +352,27 @@ classifier_rule_overlaps(const struct classifier *cls, { struct cls_table *table; - HMAP_FOR_EACH (table, hmap_node, &cls->tables) { - struct flow_wildcards wc; + /* Iterate tables in the descending max priority order. */ + LIST_FOR_EACH (table, list_node, &cls->tables_priority) { + uint32_t storage[FLOW_U32S]; + struct minimask mask; struct cls_rule *head; - flow_wildcards_combine(&wc, &target->wc, &table->wc); + if (target->priority > table->max_priority) { + break; /* Can skip this and the rest of the tables. */ + } + + 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) { + break; /* Rules in descending priority order. */ + } 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; } } @@ -553,115 +382,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, - 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 (!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. + * + * Ignores target->priority. */ void -classifier_for_each(const struct classifier *cls_, - cls_cb_func *callback, void *aux) +cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls, + const struct cls_rule *target) +{ + cursor->cls = cls; + cursor->target = target && !cls_rule_is_catchall(target) ? target : NULL; +} + +/* 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 classifier *cls = (struct classifier *) cls_; - struct cls_table *table, *next_table; + struct cls_table *table; - for (table = classifier_first_table(cls); table; table = next_table) { - struct cls_rule *head, *next_head; + 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; + } + } - table->n_refs++; - HMAP_FOR_EACH_SAFE (head, next_head, hmap_node, &table->rules) { - struct cls_rule *rule, *next_rule; + return NULL; +} - FOR_EACH_RULE_IN_LIST_SAFE (rule, next_rule, head) { - callback(rule, aux); - } +/* 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; } - next_table = classifier_next_table(cls, table); - if (!--table->n_refs && !table->n_table_rules) { - destroy_table(cls, table); + } + + 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; } } @@ -669,64 +534,142 @@ 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)); + list_push_back(&cls->tables_priority, &table->list_node); return table; } -static struct cls_table * -classifier_first_table(const struct classifier *cls) +static void +destroy_table(struct classifier *cls, struct cls_table *table) { - return cls_table_from_hmap_node(hmap_first(&cls->tables)); + minimask_destroy(&table->mask); + hmap_remove(&cls->tables, &table->hmap_node); + hmap_destroy(&table->rules); + list_remove(&table->list_node); + free(table); } -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)); +/* This function performs the following updates for 'table' in 'cls' following + * the addition of a new rule with priority 'new_priority' to 'table': + * + * - Update 'table->max_priority' and 'table->max_count' if necessary. + * + * - Update 'table''s position in 'cls->tables_priority' if necessary. + * + * This function should only be called after adding a new rule, not after + * replacing a rule by an identical one or modifying a rule in-place. */ +static void +update_tables_after_insertion(struct classifier *cls, struct cls_table *table, + unsigned int new_priority) +{ + if (new_priority == table->max_priority) { + ++table->max_count; + } else if (new_priority > table->max_priority) { + struct cls_table *iter; + + table->max_priority = new_priority; + table->max_count = 1; + + /* Possibly move 'table' earlier in the priority list. If we break out + * of the loop, then 'table' should be moved just after that 'iter'. + * If the loop terminates normally, then 'iter' will be the list head + * and we'll move table just after that (e.g. to the front of the + * list). */ + iter = table; + LIST_FOR_EACH_REVERSE_CONTINUE (iter, list_node, + &cls->tables_priority) { + if (iter->max_priority >= table->max_priority) { + break; + } + } + + /* Move 'table' just after 'iter' (unless it's already there). */ + if (iter->list_node.next != &table->list_node) { + list_splice(iter->list_node.next, + &table->list_node, table->list_node.next); + } + } } +/* This function performs the following updates for 'table' in 'cls' following + * the deletion of a rule with priority 'del_priority' from 'table': + * + * - Update 'table->max_priority' and 'table->max_count' if necessary. + * + * - Update 'table''s position in 'cls->tables_priority' if necessary. + * + * This function should only be called after removing a rule, not after + * replacing a rule by an identical one or modifying a rule in-place. */ static void -destroy_table(struct classifier *cls, struct cls_table *table) +update_tables_after_removal(struct classifier *cls, struct cls_table *table, + unsigned int del_priority) { - hmap_remove(&cls->tables, &table->hmap_node); - hmap_destroy(&table->rules); - free(table); + struct cls_table *iter; + + if (del_priority == table->max_priority && --table->max_count == 0) { + struct cls_rule *head; + + table->max_priority = 0; + HMAP_FOR_EACH (head, hmap_node, &table->rules) { + if (head->priority > table->max_priority) { + table->max_priority = head->priority; + table->max_count = 1; + } else if (head->priority == table->max_priority) { + ++table->max_count; + } + } + + /* Possibly move 'table' later in the priority list. If we break out + * of the loop, then 'table' should be moved just before that 'iter'. + * If the loop terminates normally, then 'iter' will be the list head + * and we'll move table just before that (e.g. to the back of the + * list). */ + iter = table; + LIST_FOR_EACH_CONTINUE (iter, list_node, &cls->tables_priority) { + if (iter->max_priority <= table->max_priority) { + break; + } + } + + /* Move 'table' just before 'iter' (unless it's already there). */ + if (iter->list_node.prev != &table->list_node) { + list_splice(&iter->list_node, + &table->list_node, table->list_node.next); + } + } } 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; } } @@ -734,17 +677,20 @@ find_equal(struct cls_table *table, const struct flow *flow, uint32_t hash) } static struct cls_rule * -insert_rule(struct cls_table *table, struct cls_rule *new) +insert_rule(struct classifier *cls, + struct cls_table *table, struct cls_rule *new) { struct cls_rule *head; + struct cls_rule *old = NULL; - 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); - return NULL; + goto out; } else { /* Scan the list for the insertion point that will keep the list in * order of decreasing priority. */ @@ -759,112 +705,36 @@ insert_rule(struct cls_table *table, struct cls_rule *new) if (new->priority == rule->priority) { list_replace(&new->list, &rule->list); - return rule; + old = rule; + goto out; } else { list_insert(&rule->list, &new->list); - return NULL; + goto out; } } } /* Insert 'new' at the end of the list. */ list_push_back(&head->list, &new->list); - return NULL; } + + out: + if (!old) { + update_tables_after_insertion(cls, table, new->priority); + } + return old; } 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; - int i; - - BUILD_ASSERT_DECL(FLOW_SIG_SIZE == 37 + FLOW_N_REGS * 4); - - for (i = 0; i < FLOW_N_REGS; i++) { - if ((a->regs[i] ^ b->regs[i]) & wildcards->reg_masks[i]) { - return false; - } - } - - 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 - || (!((a->dl_dst[0] ^ b->dl_dst[0]) & 0xfe) - && a->dl_dst[1] == b->dl_dst[1] - && a->dl_dst[2] == b->dl_dst[2] - && a->dl_dst[3] == b->dl_dst[3] - && a->dl_dst[4] == b->dl_dst[4] - && a->dl_dst[5] == b->dl_dst[5])) - && (wc & FWW_ETH_MCAST || !((a->dl_dst[0] ^ b->dl_dst[0]) & 0x01)) - && (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; - int i; - - BUILD_ASSERT_DECL(FLOW_SIG_SIZE == 37 + 4 * FLOW_N_REGS); - - for (i = 0; i < FLOW_N_REGS; i++) { - flow->regs[i] &= wildcards->reg_masks[i]; - } - 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) { - flow->dl_dst[0] &= 0x01; - memset(&flow->dl_dst[1], 0, 5); - } - if (wc & FWW_ETH_MCAST) { - flow->dl_dst[0] &= 0xfe; - } - 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; }