From 4aacd02daa1ece830c604b9c5679e2175ff53194 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Mon, 11 Feb 2013 13:11:42 -0800 Subject: [PATCH] classifier: Refactor table priority updates and tables_priority reordering. I find this organization clearer. CC: Jarno Rajahalme Signed-off-by: Ben Pfaff --- lib/classifier.c | 193 ++++++++++++++++++++++++++++------------------- 1 file changed, 116 insertions(+), 77 deletions(-) diff --git a/lib/classifier.c b/lib/classifier.c index 5ab8ba99c..2d1e50bbb 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. @@ -33,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) \ @@ -166,52 +174,6 @@ 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. * @@ -236,16 +198,7 @@ classifier_replace(struct classifier *cls, struct cls_rule *rule) table = insert_table(cls, &rule->match.mask); } - 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; - } - + old_rule = insert_rule(cls, table, rule); if (!old_rule) { table->n_table_rules++; cls->n_rules++; @@ -291,20 +244,8 @@ classifier_remove(struct classifier *cls, struct cls_rule *rule) if (--table->n_table_rules == 0) { destroy_table(cls, table); - } else if (rule->priority == table->max_priority - && --table->max_count == 0) { - /* Maintain table's max_priority. */ - struct cls_rule *head; - unsigned int new_max_priority = 0; - HMAP_FOR_EACH (head, hmap_node, &table->rules) { - if (head->priority > new_max_priority) { - new_max_priority = head->priority; - table->max_count = 1; - } else if (head->priority == new_max_priority) { - ++table->max_count; - } - } - classifier_update_table_max_priority(cls, table, new_max_priority); + } else { + update_tables_after_removal(cls, table, rule->priority); } cls->n_rules--; } @@ -603,6 +544,96 @@ destroy_table(struct classifier *cls, struct cls_table *table) 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) { @@ -633,9 +664,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); @@ -644,7 +677,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. */ @@ -659,18 +692,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 * -- 2.43.0