On Feb 7, 2013, at 22:36 , ext Ben Pfaff wrote:
> With complicated flow tables and multiple levels of resubmit, I see
> flow setup performance improvements of up to 5-6% with this patch.
>
I played around with the same issue last week and came up with a
little bit different solution. I think I spotted couple more locations where
the search can be stopped based on the max priority.
I'll send my patches right away. There are two parts:
1. Maintain max priority of each table.
2. Maintain tables in descending priority order.
The latter should be beneficial e.g. for longest prefix match tables (such
as an IP routing table that is implemented by assigning higher priorities
for rules with longer prefixes) as tables with shorter prefixes need not be
searched after a match is found.
I'd be interested to know how these perform with your test case, if you
care to test. Anyway, please feel free use these as you see fit.
Jarno
> Signed-off-by: Ben Pfaff <b...@nicira.com>
> ---
> lib/classifier.c | 30 ++++++++++++++++++++++++++----
> lib/classifier.h | 16 +++++++++++++++-
> 2 files changed, 41 insertions(+), 5 deletions(-)
>
> diff --git a/lib/classifier.c b/lib/classifier.c
> index 7192602..0ffaa8d 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.
> @@ -188,10 +188,17 @@ classifier_replace(struct classifier *cls, struct
> cls_rule *rule)
> if (!table) {
> table = insert_table(cls, &rule->match.mask);
> }
> + if (rule->priority > table->max_priority) {
> + table->max_priority = rule->priority;
> + }
>
> old_rule = insert_rule(table, rule);
> if (!old_rule) {
> table->n_table_rules++;
> + if (table->n_table_rules > table->max_rules) {
> + table->max_rules = table->n_table_rules;
> + }
> +
> cls->n_rules++;
> }
> return old_rule;
> @@ -235,6 +242,17 @@ classifier_remove(struct classifier *cls, struct
> cls_rule *rule)
>
> if (--table->n_table_rules == 0) {
> destroy_table(cls, table);
> + } else if (table->n_table_rules < table->max_rules / 2) {
> + /* We've had a lot of deletions so reassess the maximum priority. */
> + 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_rules = table->n_table_rules;
> }
>
> cls->n_rules--;
> @@ -251,9 +269,11 @@ classifier_lookup(const struct classifier *cls, const
> struct flow *flow)
>
> best = NULL;
> HMAP_FOR_EACH (table, hmap_node, &cls->tables) {
> - struct cls_rule *rule = find_match(table, flow);
> - if (rule && (!best || rule->priority > best->priority)) {
> - best = rule;
> + if (!best || table->max_priority > best->priority) {
> + struct cls_rule *rule = find_match(table, flow);
> + if (rule && (!best || rule->priority > best->priority)) {
> + best = rule;
> + }
> }
> }
> return best;
> @@ -494,6 +514,8 @@ 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));
> + table->max_priority = 0;
> + table->max_rules = 0;
>
> return table;
> }
> diff --git a/lib/classifier.h b/lib/classifier.h
> index bc9db33..31ff375 100644
> --- a/lib/classifier.h
> +++ b/lib/classifier.h
> @@ -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.
> @@ -49,6 +49,20 @@ struct cls_table {
> struct hmap rules; /* Contains "struct cls_rule"s. */
> struct minimask mask; /* Wildcards for fields. */
> int n_table_rules; /* Number of rules, including duplicates. */
> +
> + /* Optimize lookups by tracking the maximum priority of rules in the
> table.
> + * If a lookup finds a matching rule with a given priority, then it can
> + * skip over any tables whose 'max_priority' is less than or equal to
> that
> + * priority.
> + *
> + * The value of 'max_priority' is conservative: it can be larger than the
> + * largest priority actually found in 'rules'. This happens if a rule
> with
> + * a high priority is inserted, then later removed. To make sure that
> + * 'max_priority' can eventually get adjusted downward, we refresh it
> after
> + * any sequence of deletions that reduces the size of the table by over
> + * half. */
> + unsigned int max_priority; /* Max 'priority' of any rule in 'rules'. */
> + unsigned int max_rules; /* Max size of table size last refresh. */
> };
>
> /* Returns true if 'table' is a "catch-all" table that will match every
> --
> 1.7.2.5
>
> _______________________________________________
> dev mailing list
> dev@openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
