classifier: Defer pvector publication.

This patch adds a new functions classifier_defer() and
classifier_publish(), which control when the classifier modifications
are made available to lookups.  By default, all modifications are made
available to lookups immediately.  Modifications made after a
classifier_defer() call MAY be 'deferred' for later 'publication'.  A
call to classifier_publish() will both publish any deferred
modifications, and cause subsequent changes to to be published
immediately.

Currently any deferring is limited to the visibility of the subtable
vector changes.  pvector now processes modifications mostly in a
working copy, which needs to be explicitly published with
pvector_publish().  pvector_publish() sorts the working copy and
removes gaps before publishing it.

This change helps avoiding O(n**2) memory behavior in corner cases,
where large number of rules with different masks are inserted or
deleted.

VMware-BZ: #1322017
Signed-off-by: Jarno Rajahalme <jrajahalme@nicira.com>
Acked-by: Ben Pfaff <blp@nicira.com>

1 files changed, 11 insertions, 0 deletions

diff --git a/lib/classifier.c b/lib/classifier.c
index bf9a44ccd..b05d140ea 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -248,6 +248,7 @@ classifier_init(struct classifier *cls, const uint8_t *flow_segments)
     for (int i = 0; i < CLS_MAX_TRIES; i++) {
         trie_init(cls, i, NULL);
     }
+    cls->publish = true;
 }
 
 /* Destroys 'cls'.  Rules within 'cls', if any, are not freed; this is the
@@ -634,6 +635,11 @@ classifier_replace(struct classifier *cls, const struct cls_rule *rule)
 
     /* Nothing was replaced. */
     cls->n_rules++;
+
+    if (cls->publish) {
+        pvector_publish(&cls->subtables);
+    }
+
     return NULL;
 }
 
@@ -767,6 +773,11 @@ check_priority:
             pvector_change_priority(&cls->subtables, subtable, max_priority);
         }
     }
+
+    if (cls->publish) {
+        pvector_publish(&cls->subtables);
+    }
+
 free:
     ovsrcu_postpone(free, cls_match);
     cls->n_rules--;