X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=lib%2Fclassifier.c;h=a717bd347177fedc319f6075812e4c8c6ff2d067;hb=bbb8dee92d639331e8bd81823638267dcc895396;hp=e5d226ecb883249687dabed0465fce262d41f46f;hpb=e8d780af73b8571f5998cae8d3fa97069e49c9fe;p=sliver-openvswitch.git diff --git a/lib/classifier.c b/lib/classifier.c index e5d226ecb..a717bd347 100644 --- a/lib/classifier.c +++ b/lib/classifier.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2009, 2010, 2011, 2012 Nicira, Inc. + * 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,7 +16,6 @@ #include #include "classifier.h" -#include #include #include #include "byte-order.h" @@ -34,11 +33,19 @@ static struct cls_table *insert_table(struct classifier *, 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 miniflow *, uint32_t hash); -static struct cls_rule *insert_rule(struct cls_table *, struct cls_rule *); +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) \ @@ -135,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 @@ -146,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); } @@ -192,7 +198,7 @@ classifier_replace(struct classifier *cls, struct cls_rule *rule) 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++; @@ -210,7 +216,7 @@ void classifier_insert(struct classifier *cls, struct cls_rule *rule) { struct cls_rule *displaced_rule = classifier_replace(cls, rule); - assert(!displaced_rule); + ovs_assert(!displaced_rule); } /* Removes 'rule' from 'cls'. It is the caller's responsibility to destroy @@ -238,25 +244,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; @@ -277,6 +309,11 @@ classifier_find_rule_exactly(const struct classifier *cls, return NULL; } + /* 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)); @@ -315,16 +352,24 @@ classifier_rule_overlaps(const struct classifier *cls, { struct cls_table *table; - HMAP_FOR_EACH (table, hmap_node, &cls->tables) { + /* 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; + 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 && miniflow_equal_in_minimask(&target->match.flow, &rule->match.flow, &mask)) { @@ -497,6 +542,7 @@ insert_table(struct classifier *cls, const struct minimask *mask) hmap_init(&table->rules); 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; } @@ -507,9 +553,100 @@ destroy_table(struct classifier *cls, struct cls_table *table) minimask_destroy(&table->mask); hmap_remove(&cls->tables, &table->hmap_node); hmap_destroy(&table->rules); + list_remove(&table->list_node); free(table); } +/* 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 +update_tables_after_removal(struct classifier *cls, struct cls_table *table, + unsigned int del_priority) +{ + 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) { @@ -540,9 +677,11 @@ find_equal(struct cls_table *table, const struct miniflow *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 = miniflow_hash_in_minimask(&new->match.flow, &new->match.mask, 0); @@ -551,7 +690,7 @@ insert_rule(struct cls_table *table, struct cls_rule *new) 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. */ @@ -566,18 +705,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 *