diff options
| -rw-r--r-- | lib/classifier.c | 116 | ||||
| -rw-r--r-- | lib/classifier.h | 2 | ||||
| -rw-r--r-- | lib/list.h | 8 |
3 files changed, 95 insertions, 31 deletions
diff --git a/lib/classifier.c b/lib/classifier.c index 6000db180..5ab8ba99c 100644 --- a/lib/classifier.c +++ b/lib/classifier.c @@ -134,6 +134,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 @@ -165,6 +166,52 @@ classifier_count(const struct classifier *cls) return cls->n_rules; } +static void +classifier_update_table_max_priority(struct classifier *cls, + struct cls_table *table, + unsigned int priority) +{ + struct cls_table *iter = table; + + if (priority > table->max_priority) { + /* 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). */ + LIST_FOR_EACH_REVERSE_CONTINUE (iter, list_node, + &cls->tables_priority) { + if (iter->max_priority >= 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); + } + } else if (priority < table->max_priority) { + /* Possibly move 'table' earlier 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). */ + LIST_FOR_EACH_CONTINUE (iter, list_node, &cls->tables_priority) { + if (iter->max_priority <= 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); + } + } + table->max_priority = priority; +} + /* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller * must not modify or free it. * @@ -190,6 +237,15 @@ classifier_replace(struct classifier *cls, struct cls_rule *rule) } old_rule = insert_rule(table, rule); + + if (rule->priority > table->max_priority) { + classifier_update_table_max_priority(cls, table, rule->priority); + table->max_count = 1; + } else if (!old_rule && rule->priority == table->max_priority) { + /* Only if we are not replacing an old entry. */ + ++table->max_count; + } + if (!old_rule) { table->n_table_rules++; cls->n_rules++; @@ -239,16 +295,16 @@ classifier_remove(struct classifier *cls, struct cls_rule *rule) && --table->max_count == 0) { /* Maintain table's max_priority. */ struct cls_rule *head; - - table->max_priority = 0; + unsigned int new_max_priority = 0; HMAP_FOR_EACH (head, hmap_node, &table->rules) { - if (head->priority > table->max_priority) { - table->max_priority = head->priority; + if (head->priority > new_max_priority) { + new_max_priority = head->priority; table->max_count = 1; - } else if (head->priority == table->max_priority) { + } else if (head->priority == new_max_priority) { ++table->max_count; } } + classifier_update_table_max_priority(cls, table, new_max_priority); } cls->n_rules--; } @@ -263,15 +319,22 @@ classifier_lookup(const struct classifier *cls, const struct flow *flow) struct cls_rule *best; best = NULL; - HMAP_FOR_EACH (table, hmap_node, &cls->tables) { - /* Find only if there is hope. - * Would be even better to search the tables in the descending - * order of max_priority. */ - if (!best || table->max_priority > best->priority) { - struct cls_rule *rule = find_match(table, flow); - if (rule && (!best || rule->priority > best->priority)) { - best = rule; + LIST_FOR_EACH (table, list_node, &cls->tables_priority) { + struct cls_rule *rule = find_match(table, flow); + 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 (rule && rule->priority > best->priority) { + best = rule; + } } + break; } } return best; @@ -335,13 +398,14 @@ 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) { - continue; /* Can skip this table. */ + break; /* Can skip this and the rest of the tables. */ } minimask_combine(&mask, &target->match.mask, &table->mask, storage); @@ -524,6 +588,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; } @@ -534,6 +599,7 @@ 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); } @@ -570,7 +636,6 @@ static struct cls_rule * insert_rule(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); @@ -579,7 +644,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); - goto out; + return NULL; } else { /* Scan the list for the insertion point that will keep the list in * order of decreasing priority. */ @@ -594,29 +659,18 @@ insert_rule(struct cls_table *table, struct cls_rule *new) if (new->priority == rule->priority) { list_replace(&new->list, &rule->list); - old = rule; - goto out; + return rule; } else { list_insert(&rule->list, &new->list); - goto out; + return NULL; } } } /* Insert 'new' at the end of the list. */ list_push_back(&head->list, &new->list); + return NULL; } - - out: - if (new->priority > table->max_priority) { - table->max_priority = new->priority; - table->max_count = 1; - } else if (!old && new->priority == table->max_priority) { - /* Only if we are not replacing an old entry. */ - ++table->max_count; - } - - return old; } static struct cls_rule * diff --git a/lib/classifier.h b/lib/classifier.h index 422757129..d318864e1 100644 --- a/lib/classifier.h +++ b/lib/classifier.h @@ -41,11 +41,13 @@ extern "C" { struct classifier { int n_rules; /* Total number of rules. */ struct hmap tables; /* Contains "struct cls_table"s. */ + struct list tables_priority; /* Tables in descending priority order */ }; /* A set of rules that all have the same fields wildcarded. */ struct cls_table { struct hmap_node hmap_node; /* Within struct classifier 'tables' hmap. */ + struct list list_node; /* Within classifier 'tables_priority_list' */ struct hmap rules; /* Contains "struct cls_rule"s. */ struct minimask mask; /* Wildcards for fields. */ int n_table_rules; /* Number of rules, including duplicates. */ diff --git a/lib/list.h b/lib/list.h index 8ffa797db..55e0d0add 100644 --- a/lib/list.h +++ b/lib/list.h @@ -60,10 +60,18 @@ bool list_is_short(const struct list *); for (ASSIGN_CONTAINER(ITER, (LIST)->next, MEMBER); \ &(ITER)->MEMBER != (LIST); \ ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER)) +#define LIST_FOR_EACH_CONTINUE(ITER, MEMBER, LIST) \ + for (ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER); \ + &(ITER)->MEMBER != (LIST); \ + ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER)) #define LIST_FOR_EACH_REVERSE(ITER, MEMBER, LIST) \ for (ASSIGN_CONTAINER(ITER, (LIST)->prev, MEMBER); \ &(ITER)->MEMBER != (LIST); \ ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER)) +#define LIST_FOR_EACH_REVERSE_CONTINUE(ITER, MEMBER, LIST) \ + for (ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER); \ + &(ITER)->MEMBER != (LIST); \ + ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER)) #define LIST_FOR_EACH_SAFE(ITER, NEXT, MEMBER, LIST) \ for (ASSIGN_CONTAINER(ITER, (LIST)->next, MEMBER); \ (&(ITER)->MEMBER != (LIST) \ |