[ovs-dev] [optimize 20/26] classifier: Optimize search of "catchall" table.

[Ben Pfaff]

Most flow tables have some kind of "catchall" rule that matches every
packet.  For this table, the cost of copying, zeroing, and hashing the
input flow is significant.  This patch avoids these costs.

Signed-off-by: Ben Pfaff <blp at nicira.com>
---
 lib/classifier.c |   21 +++++++++++++++------
 lib/classifier.h |    7 ++-----
 2 files changed, 17 insertions(+), 11 deletions(-)

diff --git a/lib/classifier.c b/lib/classifier.c
index b6c477a..122a6c6 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -1036,6 +1036,7 @@ insert_table(struct classifier *cls, const struct flow_wildcards *wc)
     table = xzalloc(sizeof *table);
     hmap_init(&table->rules);
     table->wc = *wc;
+    table->is_catchall = flow_wildcards_is_catchall(&table->wc);
     hmap_insert(&cls->tables, &table->hmap_node, flow_wildcards_hash(wc, 0));
 
     return table;
@@ -1053,16 +1054,24 @@ static struct cls_rule *
 find_match(const struct cls_table *table, const struct flow *flow)
 {
     struct cls_rule *rule;
-    struct flow f;
 
-    f = *flow;
-    flow_zero_wildcards(&f, &table->wc);
-    HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, flow_hash(&f, 0),
-                             &table->rules) {
-        if (flow_equal(&f, &rule->flow)) {
+    if (table->is_catchall) {
+        HMAP_FOR_EACH (rule, hmap_node, &table->rules) {
             return rule;
         }
+    } else {
+        struct flow f;
+
+        f = *flow;
+        flow_zero_wildcards(&f, &table->wc);
+        HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, flow_hash(&f, 0),
+                                 &table->rules) {
+            if (flow_equal(&f, &rule->flow)) {
+                return rule;
+            }
+        }
     }
+
     return NULL;
 }
 
diff --git a/lib/classifier.h b/lib/classifier.h
index f9bcabb..84cb602 100644
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -48,6 +48,7 @@ struct cls_table {
     struct hmap rules;          /* Contains "struct cls_rule"s. */
     struct flow_wildcards wc;   /* Wildcards for fields. */
     int n_table_rules;          /* Number of rules, including duplicates. */
+    bool is_catchall;           /* True if this table wildcards every field. */
 };
 
 /* Returns true if 'table' is a "catch-all" table that will match every
@@ -55,11 +56,7 @@ struct cls_table {
 static inline bool
 cls_table_is_catchall(const struct cls_table *table)
 {
-    /* A catch-all table can only have one rule, so use hmap_count() as a cheap
-     * check to rule out other kinds of match before doing the full check with
-     * flow_wildcards_is_catchall(). */
-    return (hmap_count(&table->rules) == 1
-            && flow_wildcards_is_catchall(&table->wc));
+    return table->is_catchall;
 }
 
 /* A flow classification rule.
-- 
1.7.9