classifier: Maintain tables in descending priority order.

Signed-off-by: Jarno Rajahalme <jarno.rajahalme@nsn.com>
[blp@nicira.com: this along with Jarno's previous patch to the
 classifier give me a combined 15% boost in "ovs-benchmark rate"
 with a complicated flow table involving multiple resubmits]
Signed-off-by: Ben Pfaff <blp@nicira.com>

diff --git a/lib/classifier.c b/lib/classifier.c
index 6000db1..5ab8ba9 100644 (file)
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -134,6 +134,7 @@ classifier_init(struct classifier *cls)
 {
     cls->n_rules = 0;
     hmap_init(&cls->tables);
+    list_init(&cls->tables_priority);
 }
 
 /* Destroys 'cls'.  Rules within 'cls', if any, are not freed; this is the
@@ -165,6 +166,52 @@ classifier_count(const struct classifier *cls)
     return cls->n_rules;
 }
 
+static void
+classifier_update_table_max_priority(struct classifier *cls,
+                                     struct cls_table *table,
+                                     unsigned int priority)
+{
+    struct cls_table *iter = table;
+
+    if (priority > table->max_priority) {
+        /* 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). */
+        LIST_FOR_EACH_REVERSE_CONTINUE (iter, list_node,
+                                        &cls->tables_priority) {
+            if (iter->max_priority >= 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);
+        }
+    } else if (priority < table->max_priority) {
+        /* Possibly move 'table' earlier in the priority list.  If we break out
+         * 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). */
+        LIST_FOR_EACH_CONTINUE (iter, list_node, &cls->tables_priority) {
+            if (iter->max_priority <= 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);
+        }
+    }
+    table->max_priority = priority;
+}
+
 /* Inserts 'rule' into 'cls'.  Until 'rule' is removed from 'cls', the caller
  * must not modify or free it.
  *
@@ -190,6 +237,15 @@ classifier_replace(struct classifier *cls, struct cls_rule *rule)
     }
 
     old_rule = insert_rule(table, rule);
+
+    if (rule->priority > table->max_priority) {
+        classifier_update_table_max_priority(cls, table, rule->priority);
+        table->max_count = 1;
+    } else if (!old_rule && rule->priority == table->max_priority) {
+        /* Only if we are not replacing an old entry. */
+        ++table->max_count;
+    }
+
     if (!old_rule) {
         table->n_table_rules++;
         cls->n_rules++;
@@ -239,16 +295,16 @@ classifier_remove(struct classifier *cls, struct cls_rule *rule)
                && --table->max_count == 0) {
         /* Maintain table's max_priority. */
         struct cls_rule *head;
-
-        table->max_priority = 0;
+        unsigned int new_max_priority = 0;
         HMAP_FOR_EACH (head, hmap_node, &table->rules) {
-            if (head->priority > table->max_priority) {
-                table->max_priority = head->priority;
+            if (head->priority > new_max_priority) {
+                new_max_priority = head->priority;
                 table->max_count = 1;
-            } else if (head->priority == table->max_priority) {
+            } else if (head->priority == new_max_priority) {
                 ++table->max_count;
             }
         }
+        classifier_update_table_max_priority(cls, table, new_max_priority);
     }
     cls->n_rules--;
 }
@@ -263,15 +319,22 @@ classifier_lookup(const struct classifier *cls, const struct flow *flow)
     struct cls_rule *best;
 
     best = NULL;
-    HMAP_FOR_EACH (table, hmap_node, &cls->tables) {
-        /* Find only if there is hope.
-         * Would be even better to search the tables in the descending
-         * order of max_priority. */
-        if (!best || table->max_priority > best->priority) {
-            struct cls_rule *rule = find_match(table, flow);
-            if (rule && (!best || rule->priority > best->priority)) {
-                best = rule;
+    LIST_FOR_EACH (table, list_node, &cls->tables_priority) {
+        struct cls_rule *rule = find_match(table, flow);
+        if (rule) {
+            best = rule;
+            LIST_FOR_EACH_CONTINUE (table, list_node, &cls->tables_priority) {
+                if (table->max_priority <= best->priority) {
+                    /* Tables in descending priority order,
+                     * can not find anything better. */
+                    return best;
+                }
+                rule = find_match(table, flow);
+                if (rule && rule->priority > best->priority) {
+                    best = rule;
+                }
             }
+            break;
         }
     }
     return best;
@@ -335,13 +398,14 @@ classifier_rule_overlaps(const struct classifier *cls,
 {
     struct cls_table *table;
 
-    HMAP_FOR_EACH (table, hmap_node, &cls->tables) {
+    /* Iterate tables in the descending max priority order. */
+    LIST_FOR_EACH (table, list_node, &cls->tables_priority) {
         uint32_t storage[FLOW_U32S];
         struct minimask mask;
         struct cls_rule *head;
 
         if (target->priority > table->max_priority) {
-            continue; /* Can skip this table. */
+            break; /* Can skip this and the rest of the tables. */
         }
 
         minimask_combine(&mask, &target->match.mask, &table->mask, storage);
@@ -524,6 +588,7 @@ 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));
+    list_push_back(&cls->tables_priority, &table->list_node);
 
     return table;
 }
@@ -534,6 +599,7 @@ destroy_table(struct classifier *cls, struct cls_table *table)
     minimask_destroy(&table->mask);
     hmap_remove(&cls->tables, &table->hmap_node);
     hmap_destroy(&table->rules);
+    list_remove(&table->list_node);
     free(table);
 }
 
@@ -570,7 +636,6 @@ static struct cls_rule *
 insert_rule(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);
@@ -579,7 +644,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);
-        goto out;
+        return NULL;
     } else {
         /* Scan the list for the insertion point that will keep the list in
          * order of decreasing priority. */
@@ -594,29 +659,18 @@ insert_rule(struct cls_table *table, struct cls_rule *new)
 
                 if (new->priority == rule->priority) {
                     list_replace(&new->list, &rule->list);
-                    old = rule;
-                    goto out;
+                    return rule;
                 } else {
                     list_insert(&rule->list, &new->list);
-                    goto out;
+                    return NULL;
                 }
             }
         }
 
         /* Insert 'new' at the end of the list. */
         list_push_back(&head->list, &new->list);
+        return NULL;
     }
-
- out:
-    if (new->priority > table->max_priority) {
-        table->max_priority = new->priority;
-        table->max_count = 1;
-    } else if (!old && new->priority == table->max_priority) {
-        /* Only if we are not replacing an old entry. */
-        ++table->max_count;
-    }
-
-    return old;
 }
 
 static struct cls_rule *

diff --git a/lib/classifier.h b/lib/classifier.h
index 4227571..d318864 100644 (file)
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -41,11 +41,13 @@ extern "C" {
 struct classifier {
     int n_rules;                /* Total number of rules. */
     struct hmap tables;         /* Contains "struct cls_table"s.  */
+    struct list tables_priority; /* Tables in descending priority order */
 };
 
 /* A set of rules that all have the same fields wildcarded. */
 struct cls_table {
     struct hmap_node hmap_node; /* Within struct classifier 'tables' hmap. */
+    struct list list_node;      /* Within classifier 'tables_priority_list' */
     struct hmap rules;          /* Contains "struct cls_rule"s. */
     struct minimask mask;       /* Wildcards for fields. */
     int n_table_rules;          /* Number of rules, including duplicates. */

diff --git a/lib/list.h b/lib/list.h
index 8ffa797..55e0d0a 100644 (file)
--- a/lib/list.h
+++ b/lib/list.h
@@ -60,10 +60,18 @@ bool list_is_short(const struct list *);
     for (ASSIGN_CONTAINER(ITER, (LIST)->next, MEMBER);                  \
          &(ITER)->MEMBER != (LIST);                                     \
          ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER))
+#define LIST_FOR_EACH_CONTINUE(ITER, MEMBER, LIST)                      \
+    for (ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER);           \
+         &(ITER)->MEMBER != (LIST);                                     \
+         ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER))
 #define LIST_FOR_EACH_REVERSE(ITER, MEMBER, LIST)                       \
     for (ASSIGN_CONTAINER(ITER, (LIST)->prev, MEMBER);                  \
          &(ITER)->MEMBER != (LIST);                                     \
          ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER))
+#define LIST_FOR_EACH_REVERSE_CONTINUE(ITER, MEMBER, LIST)              \
+    for (ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER);           \
+         &(ITER)->MEMBER != (LIST);                                     \
+         ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER))
 #define LIST_FOR_EACH_SAFE(ITER, NEXT, MEMBER, LIST)            \
     for (ASSIGN_CONTAINER(ITER, (LIST)->next, MEMBER);          \
          (&(ITER)->MEMBER != (LIST)                             \