[ovs-dev] [PATCH] classifier: Skip tables if priorities guarantee no match.

Ben Pfaff blp at nicira.com
Thu Feb 7 20:36:42 UTC 2013


With complicated flow tables and multiple levels of resubmit, I see
flow setup performance improvements of up to 5-6% with this patch.

Signed-off-by: Ben Pfaff <blp at 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




More information about the dev mailing list