X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=lib%2Fclassifier.c;h=591322e7748fc5598c2ae82ab882b2b5fe0d3cba;hb=80642190644ae6fbcf485924b1c59e67d0be8a87;hp=dc2230de9b7ade07c7fcb23d3c317e6da623cc53;hpb=64420dfac5b1e350867da0949af5f193d9b6ca8c;p=openvswitch diff --git a/lib/classifier.c b/lib/classifier.c index dc2230de..591322e7 100644 --- a/lib/classifier.c +++ b/lib/classifier.c @@ -34,8 +34,6 @@ 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 *, @@ -62,59 +60,27 @@ 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, hmap_node); - - return (next->priority < rule->priority - ? next - : cls_rule_from_hmap_node(hmap_next(&table->rules, - &next->hmap_node))); -} - -static void -cls_rule_init__(struct cls_rule *rule, - const struct flow *flow, uint32_t wildcards) +/* 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; - flow_wildcards_init(&rule->wc, wildcards); + rule->wc = *wildcards; + rule->priority = priority; cls_rule_zero_wildcarded_fields(rule); } -/* Converts the flow in 'flow' into a cls_rule in 'rule', with the given - * 'wildcards' and 'priority'.*/ +/* 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.) */ void -cls_rule_from_flow(const struct flow *flow, uint32_t wildcards, - unsigned int priority, struct cls_rule *rule) +cls_rule_init_exact(const struct flow *flow, + unsigned int priority, struct cls_rule *rule) { - cls_rule_init__(rule, flow, wildcards); + rule->flow = *flow; + flow_wildcards_init_exact(&rule->wc); rule->priority = priority; } @@ -126,12 +92,9 @@ 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; - 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; + 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 @@ -140,7 +103,7 @@ void cls_rule_init_catchall(struct cls_rule *rule, unsigned int priority) { memset(&rule->flow, 0, sizeof rule->flow); - flow_wildcards_init(&rule->wc, OVSFW_ALL); + flow_wildcards_init(&rule->wc, OVSFW_ALL | FWW_ALL); rule->priority = priority; } @@ -182,10 +145,90 @@ cls_rule_set_dl_src(struct cls_rule *rule, const uint8_t 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; + 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) { @@ -210,15 +253,57 @@ cls_rule_set_nw_proto(struct cls_rule *rule, uint8_t nw_proto) void cls_rule_set_nw_src(struct cls_rule *rule, ovs_be32 nw_src) { - flow_wildcards_set_nw_src_mask(&rule->wc, htonl(UINT32_MAX)); - rule->flow.nw_src = nw_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; + } } void cls_rule_set_nw_dst(struct cls_rule *rule, ovs_be32 nw_dst) { - flow_wildcards_set_nw_dst_mask(&rule->wc, htonl(UINT32_MAX)); - rule->flow.nw_dst = 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 @@ -285,14 +370,6 @@ 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. * @@ -346,7 +423,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); } @@ -355,24 +432,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; @@ -436,10 +507,34 @@ classifier_rule_overlaps(const struct classifier *cls, return false; } + +/* Iteration. */ + +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)); +} -/* 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: +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)) { + struct cls_rule *rule; + + HMAP_FOR_EACH (rule, hmap_node, &table->rules) { + if (rule_matches(rule, target)) { + return rule; + } + } + } + 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 @@ -470,80 +565,63 @@ classifier_rule_overlaps(const struct classifier *cls, * * 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. */ + * 'target' may be NULL to iterate over every rule in 'cls'. */ 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); - } - } else { - next_table = classifier_next_table(cls, table); +cls_cursor_init(struct cls_cursor *cursor, const struct classifier *cls, + const struct cls_rule *target) +{ + cursor->cls = cls; + cursor->target = target; +} + +/* 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; + + for (table = classifier_first_table(cursor->cls); table; + table = classifier_next_table(cursor->cls, table)) { + struct cls_rule *rule = search_table(table, cursor->target); + if (rule) { + cursor->table = table; + return rule; } } + + 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. - * - * If 'include' is CLS_INC_EXACT then CLASSIFIER_FOR_EACH_EXACT_RULE is - * probably easier to use. */ -void -classifier_for_each(const struct classifier *cls_, int include, - cls_cb_func *callback, void *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) { - struct classifier *cls = (struct classifier *) cls_; - struct cls_table *table, *next_table; + const struct cls_table *table; + struct cls_rule *next; - for (table = classifier_first_table(cls); table; table = next_table) { - if (should_include(table, include)) { - struct cls_rule *head, *next_head; + next = next_rule_in_list(rule); + if (next) { + return next; + } - table->n_refs++; - HMAP_FOR_EACH_SAFE (head, next_head, hmap_node, &table->rules) { - struct cls_rule *rule, *next_rule; + HMAP_FOR_EACH_CONTINUE (rule, hmap_node, &cursor->table->rules) { + if (rule_matches(rule, cursor->target)) { + 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); + for (table = classifier_next_table(cursor->cls, cursor->table); table; + table = classifier_next_table(cursor->cls, table)) { + rule = search_table(table, cursor->target); + if (rule) { + cursor->table = table; + return rule; } } + + return NULL; } static struct cls_table * @@ -595,14 +673,6 @@ destroy_table(struct classifier *cls, struct cls_table *table) 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) { @@ -685,8 +755,15 @@ 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); - BUILD_ASSERT_DECL(FLOW_SIG_SIZE == 37); + 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) @@ -697,7 +774,14 @@ flow_equal_except(const struct flow *a, const struct flow *b, && (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_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)); @@ -707,9 +791,13 @@ 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); + 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; } @@ -734,7 +822,11 @@ zero_wildcards(struct flow *flow, const struct flow_wildcards *wildcards) memset(flow->dl_src, 0, sizeof flow->dl_src); } if (wc & OFPFW_DL_DST) { - memset(flow->dl_dst, 0, sizeof flow->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;