[ovs-dev] [PATCH] classifier: Refactor table priority updates and tables_priority reordering.

Rajahalme, Jarno (NSN - FI/Espoo) jarno.rajahalme at nsn.com
Mon Feb 11 19:43:52 UTC 2013


On Feb 11, 2013, at 20:35 , ext Ben Pfaff wrote:

> I find this organization clearer.
> 

Agree, but see the minor comments below,

  Jarno

> CC: Jarno Rajahalme <jarno.rajahalme at nsn.com>
> Signed-off-by: Ben Pfaff <blp at nicira.com>
> ---
> lib/classifier.c |  190 ++++++++++++++++++++++++++++++++----------------------
> 1 files changed, 114 insertions(+), 76 deletions(-)
> 
> diff --git a/lib/classifier.c b/lib/classifier.c
> index 5ab8ba9..bcf7a36 100644
> --- a/lib/classifier.c
> +++ b/lib/classifier.c
> @@ -33,11 +33,18 @@ static struct cls_table *insert_table(struct classifier *,
> 
> static void destroy_table(struct classifier *, struct cls_table *);
> 
> +static void update_table_after_insertion(struct classifier *,
> +                                         struct cls_table *,
> +                                         unsigned int new_priority);
> +static void update_table_after_removal(struct classifier *, struct cls_table *,
> +                                       unsigned int del_priority);
> +

I'm not 100% happy with the fact that these functions names kind of
hide the fact that the update may change things outside of the table
itself (the priority list). How about "update_tables_after_*"?

> 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 +173,6 @@ classifier_count(const struct classifier *cls)
>     return cls->n_rules;
> }
> 
...
> 
> +/* 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_table_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_table_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' earlier in the priority list.  If we break out

s/earlier/later/

> +         * 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 +663,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 +676,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 +691,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_table_after_insertion(cls, table, new->priority);
> +    }
> +    return old;
> }
> 
> static struct cls_rule *
> -- 
> 1.7.2.5
> 




More information about the dev mailing list