From c23740be661db40a54b8cd0c397945fb3987e771 Mon Sep 17 00:00:00 2001
From: Ben Pfaff <blp@nicira.com>
Date: Mon, 9 Apr 2012 15:49:22 -0700
Subject: [PATCH] classifier: Optimize search of "catchall" table.

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@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 b6c477a0..122a6c6e 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 f9bcabbe..84cb6028 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.
-- 
2.30.2