[ovs-dev] [PATCH v2 1/2] lib/classifier: Simplify subtable array.

Jarno Rajahalme jrajahalme at nicira.com
Mon May 19 19:35:45 UTC 2014


Do not cache the 'tag' and 'max_priority' in the subtable array.  This
makes later changes to classifier easier.

Change CLS_SUBTABLES_FOR_EACH to iterate with a regular array index.

Also makes the 'cls_subtables*' functions to always leave the
subtables array in a consistent state.  This includes the new
cls_subtables_insert() function and removal of the old
cls_subtables_push_back() function.

Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
---
 lib/classifier.c |  438 +++++++++++++++++++++++-------------------------------
 1 file changed, 185 insertions(+), 253 deletions(-)

diff --git a/lib/classifier.c b/lib/classifier.c
index 00d47ac..2004266 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -43,16 +43,10 @@ struct cls_trie {
     struct trie_node *root;       /* NULL if none. */
 };
 
-struct cls_subtable_entry {
-    struct cls_subtable *subtable;
-    tag_type tag;
-    unsigned int max_priority;
-};
-
 struct cls_subtables {
-    size_t count;          /* One past last valid array element. */
+    int count;             /* One past last valid array element. */
     size_t alloc_size;     /* Number of allocated elements. */
-    struct cls_subtable_entry *array;
+    struct cls_subtable **array;
 };
 
 enum {
@@ -138,13 +132,6 @@ static struct cls_subtable *insert_subtable(struct cls_classifier *,
 
 static void destroy_subtable(struct cls_classifier *, struct cls_subtable *);
 
-static void update_subtables_after_insertion(struct cls_classifier *,
-                                             struct cls_subtable *,
-                                             unsigned int new_priority);
-static void update_subtables_after_removal(struct cls_classifier *,
-                                           struct cls_subtable *,
-                                           unsigned int del_priority);
-
 static struct cls_match *find_match_wc(const struct cls_subtable *,
                                        const struct flow *, struct trie_ctx *,
                                        unsigned int n_tries,
@@ -199,85 +186,71 @@ cls_subtables_destroy(struct cls_subtables *subtables)
     memset(subtables, 0, sizeof *subtables);
 }
 
-/* Subtables insertion. */
 static void
-cls_subtables_push_back(struct cls_subtables *subtables,
-                        struct cls_subtable_entry a)
-{
-    if (subtables->count == subtables->alloc_size) {
-        subtables->array = x2nrealloc(subtables->array, &subtables->alloc_size,
-                                      sizeof a);
-    }
-
-    subtables->array[subtables->count++] = a;
-}
+cls_subtables_change_priority(struct cls_classifier *, struct cls_subtable *,
+                              unsigned int new_priority);
 
-/* Move subtable entry at 'from' to 'to', shifting the elements in between
- * (including the one at 'to') accordingly. */
-static inline void
-cls_subtables_move(struct cls_subtable_entry *to,
-                   struct cls_subtable_entry *from)
+/* Subtable insertion.  'a->max_priority' must be updated after insertion,
+ * Unless 'max_priority' remains at 0. */
+static void
+cls_subtables_insert(struct cls_classifier *cls, struct cls_subtable *a)
 {
-    if (to != from) {
-        struct cls_subtable_entry temp = *from;
+    unsigned int priority = a->max_priority;
 
-        if (to > from) {
-            /* Shift entries (from,to] backwards to make space at 'to'. */
-            memmove(from, from + 1, (to - from) * sizeof *to);
-        } else {
-            /* Shift entries [to,from) forward to make space at 'to'. */
-            memmove(to + 1, to, (from - to) * sizeof *to);
-        }
-
-        *to = temp;
+    if (cls->subtables.count == cls->subtables.alloc_size) {
+        cls->subtables.array = x2nrealloc(cls->subtables.array,
+                                          &cls->subtables.alloc_size,
+                                          sizeof a);
     }
+
+    /* Lowest priority subtables at the end. */
+    a->max_priority = 0;
+    cls->subtables.array[cls->subtables.count++] = a;
+    cls_subtables_change_priority(cls, a, priority);
 }
 
-/* Subtables removal. */
+/* Subtable removal. */
 static inline void
-cls_subtables_remove(struct cls_subtables *subtables,
-                     struct cls_subtable_entry *elem)
+cls_subtables_remove(struct cls_subtables *subtables, int index)
 {
-    ssize_t size = (&subtables->array[subtables->count]
-                    - (elem + 1)) * sizeof *elem;
-    if (size > 0) {
-        memmove(elem, elem + 1, size);
+    ovs_assert(index >= 0 && index < subtables->count);
+
+    if (index < subtables->count - 1) {
+        memmove(&subtables->array[index], &subtables->array[index + 1],
+                (subtables->count - (index + 1)) * sizeof subtables->array[0]);
     }
     subtables->count--;
 }
 
-#define CLS_SUBTABLES_FOR_EACH(SUBTABLE, ITER, SUBTABLES)  \
-    for ((ITER) = (SUBTABLES)->array;                      \
-         (ITER) < &(SUBTABLES)->array[(SUBTABLES)->count]  \
-             && OVS_LIKELY((SUBTABLE) = (ITER)->subtable); \
-         ++(ITER))
-#define CLS_SUBTABLES_FOR_EACH_CONTINUE(SUBTABLE, ITER, SUBTABLES) \
-    for (++(ITER);                                                 \
-         (ITER) < &(SUBTABLES)->array[(SUBTABLES)->count]          \
-             && OVS_LIKELY((SUBTABLE) = (ITER)->subtable);         \
-         ++(ITER))
-#define CLS_SUBTABLES_FOR_EACH_REVERSE(SUBTABLE, ITER, SUBTABLES)  \
-    for ((ITER) = &(SUBTABLES)->array[(SUBTABLES)->count];         \
-         (ITER) > (SUBTABLES)->array                               \
-             && OVS_LIKELY((SUBTABLE) = (--(ITER))->subtable);)
+#define CLS_SUBTABLES_FOR_EACH(SUBTABLE, INDEX, SUBTABLES)      \
+    for ((INDEX) = 0;                                           \
+         (INDEX) < (SUBTABLES)->count                           \
+             && ((SUBTABLE) = (SUBTABLES)->array[INDEX], true); \
+         (INDEX)++)
+#define CLS_SUBTABLES_FOR_EACH_CONTINUE(SUBTABLE, INDEX, SUBTABLES) \
+    for ((INDEX)++;                                                 \
+         (INDEX) < (SUBTABLES)->count                               \
+             && ((SUBTABLE) = (SUBTABLES)->array[INDEX], true);     \
+         (INDEX)++)
+#define CLS_SUBTABLES_FOR_EACH_REVERSE(SUBTABLE, INDEX, SUBTABLES) \
+    for ((INDEX) = (int)(SUBTABLES)->count - 1;                    \
+         (int)(INDEX) >= 0                                         \
+             && ((SUBTABLE) = (SUBTABLES)->array[INDEX], true);    \
+         (INDEX)--)
 
 static void
 cls_subtables_verify(struct cls_subtables *subtables)
 {
     struct cls_subtable *table;
-    struct cls_subtable_entry *iter;
+    int index;
     unsigned int priority = 0;
 
-    CLS_SUBTABLES_FOR_EACH_REVERSE (table, iter, subtables) {
-        if (iter->max_priority != table->max_priority) {
-            VLOG_WARN("Subtable %p has mismatching priority in cache (%u != %u)",
-                      table, iter->max_priority, table->max_priority);
-        }
-        if (iter->max_priority < priority) {
+    CLS_SUBTABLES_FOR_EACH_REVERSE (table, index, subtables) {
+        if (table->max_priority < priority) {
             VLOG_WARN("Subtable cache is out of order (%u < %u)",
-                      iter->max_priority, priority);
+                      table->max_priority, priority);
         }
-        priority = iter->max_priority;
+        priority = table->max_priority;
     }
 }
 
@@ -295,13 +268,27 @@ cls_subtables_reset(struct cls_classifier *cls)
 
     HMAP_FOR_EACH (subtable, hmap_node, &cls->subtables_map) {
         struct cls_match *head;
-        struct cls_subtable_entry elem;
         struct cls_subtable *table;
-        struct cls_subtable_entry *iter, *from = NULL;
+        int index;
         unsigned int new_max = 0;
         unsigned int max_count = 0;
         bool found;
 
+        /* Locate the subtable from the old cache. */
+        found = false;
+        CLS_SUBTABLES_FOR_EACH (table, index, &old) {
+            if (table == subtable) {
+                if (found) {
+                    VLOG_WARN("Subtable %p duplicated in the old cache.",
+                              subtable);
+                }
+                found = true;
+            }
+        }
+        if (!found) {
+            VLOG_WARN("Subtable %p not found from the old cache.", subtable);
+        }
+
         /* Verify max_priority. */
         HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
             if (head->priority > new_max) {
@@ -311,6 +298,7 @@ cls_subtables_reset(struct cls_classifier *cls)
                 max_count++;
             }
         }
+
         if (new_max != subtable->max_priority ||
             max_count != subtable->max_count) {
             VLOG_WARN("subtable %p (%u rules) has mismatching max_priority "
@@ -321,60 +309,95 @@ cls_subtables_reset(struct cls_classifier *cls)
             subtable->max_priority = new_max;
             subtable->max_count = max_count;
         }
+        cls_subtables_insert(cls, subtable);
+    }
 
-        /* Locate the subtable from the old cache. */
-        found = false;
-        CLS_SUBTABLES_FOR_EACH (table, iter, &old) {
-            if (table == subtable) {
-                if (iter->max_priority != new_max) {
-                    VLOG_WARN("Subtable %p has wrong max priority (%u != %u) "
-                              "in the old cache.",
-                              subtable, iter->max_priority, new_max);
-                }
-                if (found) {
-                    VLOG_WARN("Subtable %p duplicated in the old cache.",
-                              subtable);
-                }
-                found = true;
-            }
-        }
-        if (!found) {
-            VLOG_WARN("Subtable %p not found from the old cache.", subtable);
-        }
+    /* Verify that the old and the new have the same size. */
+    if (old.count != cls->subtables.count) {
+        VLOG_WARN("subtables cache sizes differ: old (%d) != new (%d).",
+                  old.count, cls->subtables.count);
+    }
+
+    cls_subtables_destroy(&old);
+
+    cls_subtables_verify(&cls->subtables);
+}
+
+/* Change subtable's 'max_priority' and keep the array ordered. */
+static void
+cls_subtables_change_priority(struct cls_classifier *cls,
+                              struct cls_subtable *subtable,
+                              unsigned int new_priority)
+{
+    struct cls_subtable *table;
+    int index, from = -1;
+    unsigned int old_priority = subtable->max_priority;
 
-        elem.subtable = subtable;
-        elem.tag = subtable->tag;
-        elem.max_priority = subtable->max_priority;
-        cls_subtables_push_back(&cls->subtables, elem);
+    subtable->max_priority = new_priority;
 
+    if (new_priority > old_priority) {
         /* Possibly move 'subtable' earlier in the priority array.  If
          * we break out of the loop, then the subtable (at 'from')
          * should be moved to the position right after the current
-         * element.  If the loop terminates normally, then 'iter' will
-         * be at the first array element and we'll move the subtable
-         * to the front of the array. */
-        CLS_SUBTABLES_FOR_EACH_REVERSE (table, iter, &cls->subtables) {
+         * element.  This will become the first entry, if the loop
+         * terminated normally. */
+        CLS_SUBTABLES_FOR_EACH_REVERSE (table, index, &cls->subtables) {
             if (table == subtable) {
-                from = iter; /* Locate the subtable as we go. */
-            } else if (table->max_priority >= new_max) {
-                ovs_assert(from != NULL);
-                iter++; /* After this. */
+                from = index; /* Locate the subtable as we go. */
+            } else if (table->max_priority >= new_priority) {
                 break;
             }
         }
+        /* Now at one before the destination. */
+        index++;
+
+        if (from < 0) {
+            /* Corrupted cache? */
+            cls_subtables_reset(cls);
+            VLOG_ABORT("cls_subtable_change_priority(>): Subtable priority list corrupted.");
+            OVS_NOT_REACHED();
+        }
 
-        /* Move subtable at 'from' to 'iter'. */
-        cls_subtables_move(iter, from);
-    }
+        /* Move subtable at 'from' to 'index'. */
+        if (index < from) {
+            /* Shift entries [index,from) forward to make space at 'index'. */
+            memmove(&cls->subtables.array[index + 1],
+                    &cls->subtables.array[index],
+                    (from - index) * sizeof cls->subtables.array[0]);
+            cls->subtables.array[index] = subtable;
+        }
+    } else if (new_priority < old_priority) {
+        /* Possibly move 'subtable' later in the priority array.
+         * After the loop the 'iter' will point right after the position
+         * at which the subtable should be moved (either at a subtable
+         * with an equal or lower priority, or just past the array),
+         * so it is decremented once. */
+        CLS_SUBTABLES_FOR_EACH (table, index, &cls->subtables) {
+            if (table == subtable) {
+                from = index; /* Locate the subtable as we go. */
+            } else if (table->max_priority <= new_priority) {
+                break;
+            }
+        }
+        /* Now at one past the destination. */
+        index--;
 
-    /* Verify that the old and the new have the same size. */
-    if (old.count != cls->subtables.count) {
-        VLOG_WARN("subtables cache sizes differ: old (%"PRIuSIZE
-                  ") != new (%"PRIuSIZE").",
-                  old.count, cls->subtables.count);
-    }
+        if (from < 0) {
+            /* Corrupted cache? */
+            cls_subtables_reset(cls);
+            VLOG_ABORT("cls_subtable_change_priority(<) Subtable priority list corrupted.");
+            OVS_NOT_REACHED();
+        }
 
-    cls_subtables_destroy(&old);
+        /* Move subtable at 'from' to 'index'. */
+        if (index > from) {
+            /* Shift entries (from,index] backwards to make space at 'index'. */
+            memmove(&cls->subtables.array[from],
+                    &cls->subtables.array[from + 1],
+                    (index - from) * sizeof cls->subtables.array[0]);
+            cls->subtables.array[index] = subtable;
+        }
+    }
 
     cls_subtables_verify(&cls->subtables);
 }
@@ -767,7 +790,7 @@ trie_init(struct cls_classifier *cls, int trie_idx,
 {
     struct cls_trie *trie = &cls->tries[trie_idx];
     struct cls_subtable *subtable;
-    struct cls_subtable_entry *iter;
+    int index;
 
     if (trie_idx < cls->n_tries) {
         trie_destroy(trie->root);
@@ -776,7 +799,7 @@ trie_init(struct cls_classifier *cls, int trie_idx,
     trie->field = field;
 
     /* Add existing rules to the trie. */
-    CLS_SUBTABLES_FOR_EACH (subtable, iter, &cls->subtables) {
+    CLS_SUBTABLES_FOR_EACH (subtable, index, &cls->subtables) {
         unsigned int plen;
 
         plen = field ? minimask_get_prefix_len(&subtable->mask, field) : 0;
@@ -999,8 +1022,21 @@ classifier_remove(struct classifier *cls_, struct cls_rule *rule)
 
     if (--subtable->n_rules == 0) {
         destroy_subtable(cls, subtable);
-    } else {
-        update_subtables_after_removal(cls, subtable, cls_match->priority);
+    } else if (subtable->max_priority == cls_match->priority
+               && --subtable->max_count == 0) {
+        /* Find the new 'max_priority' and 'max_count'. */
+        struct cls_match *head;
+        unsigned int max_priority = 0;
+
+        HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
+            if (head->priority > max_priority) {
+                max_priority = head->priority;
+                subtable->max_count = 1;
+            } else if (head->priority == max_priority) {
+                ++subtable->max_count;
+            }
+        }
+        cls_subtables_change_priority(cls, subtable, max_priority);
     }
 
     cls->n_rules--;
@@ -1030,9 +1066,9 @@ trie_ctx_init(struct trie_ctx *ctx, const struct cls_trie *trie)
 }
 
 static inline void
-lookahead_subtable(const struct cls_subtable_entry *subtables)
+lookahead_subtable(const struct cls_subtable *subtable)
 {
-    ovs_prefetch_range(subtables->subtable, sizeof *subtables->subtable);
+    ovs_prefetch_range(subtable, sizeof *subtable);
 }
 
 /* Finds and returns the highest-priority rule in 'cls' that matches 'flow'.
@@ -1050,13 +1086,14 @@ classifier_lookup(const struct classifier *cls_, const struct flow *flow,
     struct cls_classifier *cls = cls_->cls;
     const struct cls_partition *partition;
     tag_type tags;
-    struct cls_match *best;
+    const struct cls_match *best;
     struct trie_ctx trie_ctx[CLS_MAX_TRIES];
     int i;
-    struct cls_subtable_entry *subtables = cls->subtables.array;
+    struct cls_subtable **subtables = cls->subtables.array;
     int n_subtables = cls->subtables.count;
     int64_t best_priority = -1;
 
+
     /* Prefetch the subtables array. */
     ovs_prefetch_range(subtables, n_subtables * sizeof *subtables);
 
@@ -1091,15 +1128,16 @@ classifier_lookup(const struct classifier *cls_, const struct flow *flow,
 
     /* Prefetch the first subtables. */
     if (n_subtables > 1) {
-        lookahead_subtable(subtables);
-        lookahead_subtable(subtables + 1);
+        lookahead_subtable(subtables[0]);
+        lookahead_subtable(subtables[1]);
     }
 
     best = NULL;
+
     for (i = 0; OVS_LIKELY(i < n_subtables); i++) {
         struct cls_match *rule;
 
-        if ((int64_t)subtables[i].max_priority <= best_priority) {
+        if ((int64_t)subtables[i]->max_priority <= best_priority) {
             /* Subtables are in descending priority order,
              * can not find anything better. */
             break;
@@ -1107,15 +1145,14 @@ classifier_lookup(const struct classifier *cls_, const struct flow *flow,
 
         /* Prefetch a forthcoming subtable. */
         if (i + 2 < n_subtables) {
-            lookahead_subtable(&subtables[i + 2]);
+            lookahead_subtable(subtables[i + 2]);
         }
 
-        if (!tag_intersects(tags, subtables[i].tag)) {
+        if (!tag_intersects(tags, subtables[i]->tag)) {
             continue;
         }
 
-        rule = find_match_wc(subtables[i].subtable, flow, trie_ctx,
-                             cls->n_tries, wc);
+        rule = find_match_wc(subtables[i], flow, trie_ctx, cls->n_tries, wc);
         if (rule && (int64_t)rule->priority > best_priority) {
             best_priority = (int64_t)rule->priority;
             best = rule;
@@ -1176,9 +1213,9 @@ struct cls_rule *classifier_lookup_miniflow_first(const struct classifier *cls_,
 {
     struct cls_classifier *cls = cls_->cls;
     struct cls_subtable *subtable;
-    struct cls_subtable_entry *iter;
+    int index;
 
-    CLS_SUBTABLES_FOR_EACH (subtable, iter, &cls->subtables) {
+    CLS_SUBTABLES_FOR_EACH (subtable, index, &cls->subtables) {
         struct cls_match *rule;
 
         rule = find_match_miniflow(subtable, flow,
@@ -1252,15 +1289,15 @@ classifier_rule_overlaps(const struct classifier *cls_,
 {
     struct cls_classifier *cls = cls_->cls;
     struct cls_subtable *subtable;
-    struct cls_subtable_entry *iter;
+    int index;
 
     /* Iterate subtables in the descending max priority order. */
-    CLS_SUBTABLES_FOR_EACH (subtable, iter, &cls->subtables) {
+    CLS_SUBTABLES_FOR_EACH (subtable, index, &cls->subtables) {
         uint32_t storage[FLOW_U32S];
         struct minimask mask;
         struct cls_match *head;
 
-        if (target->priority > iter->max_priority) {
+        if (target->priority > subtable->max_priority) {
             break; /* Can skip this and the rest of the subtables. */
         }
 
@@ -1445,7 +1482,6 @@ insert_subtable(struct cls_classifier *cls, const struct minimask *mask)
     int i, index = 0;
     struct flow_wildcards old, new;
     uint8_t prev;
-    struct cls_subtable_entry elem;
     int count = count_1bits(mask->masks.map);
 
     subtable = xzalloc(sizeof *subtable - sizeof mask->masks.inline_values
@@ -1496,10 +1532,7 @@ insert_subtable(struct cls_classifier *cls, const struct minimask *mask)
         = 32 - ctz32(ntohl(MINIFLOW_GET_BE32(&mask->masks, tp_src)));
 
     hmap_insert(&cls->subtables_map, &subtable->hmap_node, hash);
-    elem.subtable = subtable;
-    elem.tag = subtable->tag;
-    elem.max_priority = subtable->max_priority;
-    cls_subtables_push_back(&cls->subtables, elem);
+    cls_subtables_insert(cls, subtable);
 
     return subtable;
 }
@@ -1508,12 +1541,12 @@ static void
 destroy_subtable(struct cls_classifier *cls, struct cls_subtable *subtable)
 {
     int i;
-    struct cls_subtable *table = NULL;
-    struct cls_subtable_entry *iter;
+    struct cls_subtable *table;
+    int index;
 
-    CLS_SUBTABLES_FOR_EACH (table, iter, &cls->subtables) {
+    CLS_SUBTABLES_FOR_EACH (table, index, &cls->subtables) {
         if (table == subtable) {
-            cls_subtables_remove(&cls->subtables, iter);
+            cls_subtables_remove(&cls->subtables, index);
             break;
         }
     }
@@ -1529,114 +1562,6 @@ destroy_subtable(struct cls_classifier *cls, struct cls_subtable *subtable)
     free(subtable);
 }
 
-/* This function performs the following updates for 'subtable' in 'cls'
- * following the addition of a new rule with priority 'new_priority' to
- * 'subtable':
- *
- *    - Update 'subtable->max_priority' and 'subtable->max_count' if necessary.
- *
- *    - Update 'subtable''s position in 'cls->subtables' if necessary.
- *
- * This function should only be called after adding a new rule, not after
- * replacing a rule by an identical one or modifying a rule in-place. */
-static void
-update_subtables_after_insertion(struct cls_classifier *cls,
-                                 struct cls_subtable *subtable,
-                                 unsigned int new_priority)
-{
-    if (new_priority == subtable->max_priority) {
-        ++subtable->max_count;
-    } else if (new_priority > subtable->max_priority) {
-        struct cls_subtable *table;
-        struct cls_subtable_entry *iter, *from = NULL;
-
-        subtable->max_priority = new_priority;
-        subtable->max_count = 1;
-
-        /* Possibly move 'subtable' earlier in the priority array.  If
-         * we break out of the loop, then the subtable (at 'from')
-         * should be moved to the position right after the current
-         * element.  If the loop terminates normally, then 'iter' will
-         * be at the first array element and we'll move the subtable
-         * to the front of the array. */
-        CLS_SUBTABLES_FOR_EACH_REVERSE (table, iter, &cls->subtables) {
-            if (table == subtable) {
-                from = iter; /* Locate the subtable as we go. */
-                iter->max_priority = new_priority;
-            } else if (table->max_priority >= new_priority) {
-                if (from == NULL) {
-                    /* Corrupted cache? */
-                    cls_subtables_reset(cls);
-                    VLOG_ABORT("update_subtables_after_insertion(): Subtable priority list corrupted.");
-                    OVS_NOT_REACHED();
-                }
-                iter++; /* After this. */
-                break;
-            }
-        }
-
-        /* Move subtable at 'from' to 'iter'. */
-        cls_subtables_move(iter, from);
-    }
-}
-
-/* This function performs the following updates for 'subtable' in 'cls'
- * following the deletion of a rule with priority 'del_priority' from
- * 'subtable':
- *
- *    - Update 'subtable->max_priority' and 'subtable->max_count' if necessary.
- *
- *    - Update 'subtable''s position in 'cls->subtables' if necessary.
- *
- * This function should only be called after removing a rule, not after
- * replacing a rule by an identical one or modifying a rule in-place. */
-static void
-update_subtables_after_removal(struct cls_classifier *cls,
-                               struct cls_subtable *subtable,
-                               unsigned int del_priority)
-{
-    if (del_priority == subtable->max_priority && --subtable->max_count == 0) {
-        struct cls_match *head;
-        struct cls_subtable *table;
-        struct cls_subtable_entry *iter, *from = NULL;
-
-        subtable->max_priority = 0;
-        HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
-            if (head->priority > subtable->max_priority) {
-                subtable->max_priority = head->priority;
-                subtable->max_count = 1;
-            } else if (head->priority == subtable->max_priority) {
-                ++subtable->max_count;
-            }
-        }
-
-        /* Possibly move 'subtable' later in the priority array.
-         * After the loop the 'iter' will point right after the position
-         * at which the subtable should be moved (either at a subtable
-         * with an equal or lower priority, or just past the array),
-         * so it is decremented once. */
-        CLS_SUBTABLES_FOR_EACH (table, iter, &cls->subtables) {
-            if (table == subtable) {
-                from = iter; /* Locate the subtable as we go. */
-                iter->max_priority = subtable->max_priority;
-            } else if (table->max_priority <= subtable->max_priority) {
-                if (from == NULL) {
-                    /* Corrupted cache? */
-                    cls_subtables_reset(cls);
-                    VLOG_ABORT("update_subtables_after_removal(): Subtable priority list corrupted.");
-                    OVS_NOT_REACHED();
-                }
-                break;
-            }
-        }
-        /* Now at one past the destination. */
-        iter--;
-
-        /* Move subtable at 'from' to 'iter'. */
-        cls_subtables_move(iter, from);
-    }
-}
-
 struct range {
     uint8_t start;
     uint8_t end;
@@ -1914,7 +1839,14 @@ insert_rule(struct cls_classifier *cls, struct cls_subtable *subtable,
 
  out:
     if (!old) {
-        update_subtables_after_insertion(cls, subtable, cls_match->priority);
+        /* Rule was added, not replaced.  Update 'subtable's 'max_priority'
+         * and 'max_count', if necessary. */
+        if (subtable->max_priority == cls_match->priority) {
+            ++subtable->max_count;
+        } else if (cls_match->priority > subtable->max_priority) {
+            subtable->max_count = 1;
+            cls_subtables_change_priority(cls, subtable, cls_match->priority);
+        }
     } else {
         /* Remove old node from indices. */
         for (i = 0; i < subtable->n_indices; i++) {
-- 
1.7.10.4




More information about the dev mailing list