X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=lib%2Fclassifier.c;h=556278f3d745920fc8aa220fac3373eccb5d6260;hb=591cb419cf3694e0ae66a95973e73c61bad9e03d;hp=76a33dd253f84671bcda7d577297ed56e6bbcf63;hpb=844dff325b1f6a6f520fce9242c85162275ab7ad;p=sliver-openvswitch.git diff --git a/lib/classifier.c b/lib/classifier.c index 76a33dd25..556278f3d 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,34 +16,37 @@ #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" +#include "ovs-thread.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) \ @@ -55,349 +58,82 @@ static void zero_wildcards(struct flow *, const struct flow_wildcards *); 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; -} - -/* 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; } -/* 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; } -/* 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) -{ - uint32_t wildcards = ntohl(match->wildcards) & OVSFW_ALL; - - rule->priority = !wildcards ? UINT16_MAX : priority; - - rule->flow.tun_id = 0; - if (flow_format != NXFF_TUN_ID_FROM_COOKIE) { - wildcards |= NXFW_TUN_ID; - } else { - if (!(wildcards & NXFW_TUN_ID)) { - rule->flow.tun_id = htonl(ntohll(cookie) >> 32); - } - } - if (wildcards & OFPFW_DL_DST) { - /* OpenFlow 1.0 OFPFW_DL_DST covers the whole Ethernet destination, but - * internally to OVS it excludes the multicast bit, which has to be set - * separately with FWW_ETH_MCAST. */ - wildcards |= FWW_ETH_MCAST; - } - flow_wildcards_init(&rule->wc, wildcards); - - rule->flow.nw_src = match->nw_src; - rule->flow.nw_dst = match->nw_dst; - rule->flow.in_port = (match->in_port == htons(OFPP_LOCAL) ? ODPP_LOCAL - : ntohs(match->in_port)); - rule->flow.dl_vlan = match->dl_vlan; - rule->flow.dl_vlan_pcp = match->dl_vlan_pcp; - rule->flow.dl_type = match->dl_type; - rule->flow.tp_src = match->tp_src; - rule->flow.tp_dst = match->tp_dst; - memcpy(rule->flow.dl_src, match->dl_src, ETH_ADDR_LEN); - memcpy(rule->flow.dl_dst, match->dl_dst, ETH_ADDR_LEN); - rule->flow.nw_tos = match->nw_tos; - rule->flow.nw_proto = match->nw_proto; - - cls_rule_zero_wildcarded_fields(rule); -} - -/* Converts 'rule' into an OpenFlow match structure 'match' with the given flow - * format 'flow_format' (one of NXFF_*). */ -void -cls_rule_to_match(const struct cls_rule *rule, int flow_format, - struct ofp_match *match) -{ - match->wildcards = htonl(rule->wc.wildcards - & (flow_format == NXFF_TUN_ID_FROM_COOKIE - ? OVSFW_ALL : OFPFW_ALL)); - match->in_port = htons(rule->flow.in_port == ODPP_LOCAL ? OFPP_LOCAL - : rule->flow.in_port); - match->dl_vlan = rule->flow.dl_vlan; - match->dl_vlan_pcp = rule->flow.dl_vlan_pcp; - memcpy(match->dl_src, rule->flow.dl_src, ETH_ADDR_LEN); - memcpy(match->dl_dst, rule->flow.dl_dst, ETH_ADDR_LEN); - match->dl_type = rule->flow.dl_type; - match->nw_src = rule->flow.nw_src; - match->nw_dst = rule->flow.nw_dst; - match->nw_tos = rule->flow.nw_tos; - match->nw_proto = rule->flow.nw_proto; - match->tp_src = rule->flow.tp_src; - match->tp_dst = rule->flow.tp_dst; - memset(match->pad1, '\0', sizeof match->pad1); - memset(match->pad2, '\0', sizeof match->pad2); -} - -/* 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. - */ -void -cls_rule_zero_wildcarded_fields(struct cls_rule *rule) -{ - 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); -} - -void -cls_rule_set_dl_dst(struct cls_rule *rule, const uint8_t dl_dst[ETH_ADDR_LEN]) -{ - rule->wc.wildcards &= ~(OFPFW_DL_DST | FWW_ETH_MCAST); - memcpy(rule->flow.dl_dst, dl_dst, ETH_ADDR_LEN); -} - -bool -cls_rule_set_dl_tci(struct cls_rule *rule, ovs_be16 tci) -{ - return cls_rule_set_dl_tci_masked(rule, tci, htons(0xffff)); -} - -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) -{ - rule->wc.wildcards &= ~OFPFW_DL_VLAN_PCP; - rule->flow.dl_vlan_pcp = dl_vlan_pcp & 0x07; -} - -void -cls_rule_set_tp_src(struct cls_rule *rule, ovs_be16 tp_src) -{ - 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; -} - + * The caller must eventually destroy 'rule' with cls_rule_destroy(). */ void -cls_rule_set_nw_src(struct cls_rule *rule, ovs_be32 nw_src) +cls_rule_clone(struct cls_rule *dst, const struct cls_rule *src) { - cls_rule_set_nw_src_masked(rule, nw_src, htonl(UINT32_MAX)); -} - -bool -cls_rule_set_nw_src_masked(struct cls_rule *rule, ovs_be32 ip, ovs_be32 mask) -{ - if (flow_wildcards_set_nw_src_mask(&rule->wc, mask)) { - rule->flow.nw_src = ip & mask; - return true; - } else { - return false; - } + 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_nw_dst(struct cls_rule *rule, ovs_be32 nw_dst) +cls_rule_destroy(struct cls_rule *rule) { - cls_rule_set_nw_dst_masked(rule, nw_dst, htonl(UINT32_MAX)); + 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_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) +cls_rule_equal(const struct cls_rule *a, const struct cls_rule *b) { - rule->wc.wildcards &= ~OFPFW_NW_TOS; - rule->flow.nw_tos = nw_tos & IP_DSCP_MASK; + return a->priority == b->priority && minimatch_equal(&a->match, &b->match); } -void -cls_rule_set_icmp_type(struct cls_rule *rule, uint8_t icmp_type) +/* 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_ICMP_TYPE; - rule->flow.icmp_type = htons(icmp_type); - + return minimatch_hash(&rule->match, hash_int(rule->priority, basis)); } +/* Appends a string describing 'rule' to 's'. */ void -cls_rule_set_icmp_code(struct cls_rule *rule, uint8_t icmp_code) +cls_rule_format(const struct cls_rule *rule, struct ds *s) { - rule->wc.wildcards &= ~OFPFW_ICMP_CODE; - rule->flow.icmp_code = htons(icmp_code); + minimatch_format(&rule->match, s, rule->priority); } -/* Returns true if 'a' and 'b' have the same priority, wildcard the same - * fields, and have the same values for fixed fields, otherwise false. */ +/* Returns true if 'rule' matches every packet, false otherwise. */ bool -cls_rule_equal(const struct cls_rule *a, const struct cls_rule *b) -{ - return (a->priority == b->priority - && flow_wildcards_equal(&a->wc, &b->wc) - && flow_equal(&a->flow, &b->flow)); -} - -/* 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) +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 @@ -407,6 +143,8 @@ classifier_init(struct classifier *cls) { cls->n_rules = 0; hmap_init(&cls->tables); + list_init(&cls->tables_priority); + ovs_rwlock_init(&cls->rwlock); } /* Destroys 'cls'. Rules within 'cls', if any, are not freed; this is the @@ -418,11 +156,10 @@ 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); + ovs_rwlock_destroy(&cls->rwlock); } } @@ -433,7 +170,7 @@ 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) { @@ -446,24 +183,25 @@ classifier_count(const struct classifier *cls) * 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++; @@ -471,16 +209,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)) { @@ -495,25 +247,51 @@ classifier_remove(struct classifier *cls, struct cls_rule *rule) 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; @@ -521,10 +299,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) @@ -532,15 +307,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 (flow_wildcards_is_exact(&target->wc)) { - 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; @@ -549,6 +328,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. */ @@ -558,17 +355,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; } } @@ -577,6 +384,48 @@ classifier_rule_overlaps(const struct classifier *cls, return false; } + +/* 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: + * + * - '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 minimatch *criteria) +{ + return (!minimask_has_extra(&rule->match.mask, &criteria->mask) + && miniflow_equal_in_minimask(&rule->match.flow, &criteria->flow, + &criteria->mask)); +} /* Iteration. */ @@ -584,13 +433,15 @@ static bool rule_matches(const struct cls_rule *rule, const struct cls_rule *target) { return (!target - || flow_equal_except(&rule->flow, &target->flow, &target->wc)); + || 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 || !flow_wildcards_has_extra(&table->wc, &target->wc)) { + if (!target || !minimask_has_extra(&table->mask, &target->match.mask)) { struct cls_rule *rule; HMAP_FOR_EACH (rule, hmap_node, &table->rules) { @@ -602,46 +453,20 @@ search_table(const struct cls_table *table, const struct cls_rule *target) return NULL; } -/* Initializes 'cursor' for iterating through 'cls' rules that exactly match - * 'target' or are more specific than 'target'. That is, a given 'rule' - * matches 'target' if, for every field: - * - * - 'target' and 'rule' specify the same (non-wildcarded) value for the - * field, or - * - * - 'target' wildcards the field, - * - * but not if: - * - * - 'target' and 'rule' specify different values for the field, or - * - * - 'target' specifies a value for the field but 'rule' wildcards it. - * - * Equivalently, the truth table for whether a field matches is: +/* Initializes 'cursor' for iterating through rules in 'cls': * - * rule - * - * wildcard exact - * +---------+---------+ - * t wild | yes | yes | - * a card | | | - * r +---------+---------+ - * g exact | no |if values| - * e | |are equal| - * t +---------+---------+ - * - * 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. + * - If 'target' is null, the cursor will visit every rule in 'cls'. * - * Ignores target->priority. + * - If 'target' is nonnull, the cursor will visit each 'rule' in 'cls' + * such that cls_rule_is_loose_match(rule, target) returns true. * - * 'target' may be NULL to iterate over every rule in 'cls'. */ + * Ignores target->priority. */ void cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls, const struct cls_rule *target) { cursor->cls = cls; - cursor->target = target; + cursor->target = target && !cls_rule_is_catchall(target) ? target : NULL; } /* Returns the first matching cls_rule in 'cursor''s iteration, or a null @@ -651,8 +476,7 @@ cls_cursor_first(struct cls_cursor *cursor) { struct cls_table *table; - for (table = classifier_first_table(cursor->cls); table; - table = classifier_next_table(cursor->cls, table)) { + HMAP_FOR_EACH (table, hmap_node, &cursor->cls->tables) { struct cls_rule *rule = search_table(table, cursor->target); if (rule) { cursor->table = table; @@ -686,8 +510,8 @@ cls_cursor_next(struct cls_cursor *cursor, struct cls_rule *rule) } } - for (table = classifier_next_table(cursor->cls, cursor->table); table; - table = classifier_next_table(cursor->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; @@ -699,13 +523,13 @@ cls_cursor_next(struct cls_cursor *cursor, struct cls_rule *rule) } 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; } } @@ -713,64 +537,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; } } @@ -778,17 +680,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. */ @@ -803,18 +708,24 @@ 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 * @@ -830,92 +741,3 @@ next_rule_in_list(struct cls_rule *rule) struct cls_rule *next = next_rule_in_list__(rule); 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)); -} - -static void -zero_wildcards(struct flow *flow, const struct flow_wildcards *wildcards) -{ - 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; - } -}