[ovs-dev] [partition v5 4/4] classifier: Avoid accumulating junk in cls_partition 'tags'.

[Ben Pfaff]

It's easy to add two tags together, but it's hard to subtract them.  The
new "tag_tracker" data structure provides a solution.

Signed-off-by: Ben Pfaff <blp at nicira.com>
---
 lib/classifier.c |   15 +++++++++------
 lib/classifier.h |    2 +-
 lib/tag.c        |   33 +++++++++++++++++++++++++++++----
 lib/tag.h        |   16 ++++++++++++++++
 4 files changed, 55 insertions(+), 11 deletions(-)

diff --git a/lib/classifier.c b/lib/classifier.c
index 4c19c90..53487a4 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -227,11 +227,10 @@ create_partition(struct classifier *cls, struct cls_table *table,
         partition = xmalloc(sizeof *partition);
         partition->metadata = metadata;
         partition->tags = 0;
-        partition->n_refs = 0;
+        tag_tracker_init(&partition->tracker);
         hmap_insert(&cls->partitions, &partition->hmap_node, hash);
     }
-    partition->tags |= table->tag;
-    partition->n_refs++;
+    tag_tracker_add(&partition->tracker, &partition->tags, table->tag);
     return partition;
 }
 
@@ -314,9 +313,13 @@ classifier_remove(struct classifier *cls, struct cls_rule *rule)
     }
 
     partition = rule->partition;
-    if (partition && --partition->n_refs == 0) {
-        hmap_remove(&cls->partitions, &partition->hmap_node);
-        free(partition);
+    if (partition) {
+        tag_tracker_subtract(&partition->tracker, &partition->tags,
+                             table->tag);
+        if (!partition->tags) {
+            hmap_remove(&cls->partitions, &partition->hmap_node);
+            free(partition);
+        }
     }
 
     if (--table->n_table_rules == 0) {
diff --git a/lib/classifier.h b/lib/classifier.h
index 3755b09..2cb7ed3 100644
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -162,7 +162,7 @@ struct cls_partition {
     struct hmap_node hmap_node; /* In struct classifier's 'partitions' hmap. */
     ovs_be64 metadata;          /* metadata value for this partition. */
     tag_type tags;              /* OR of each included flow's cls_table tag. */
-    unsigned int n_refs;        /* # of flows that refer to this partition. */
+    struct tag_tracker tracker; /* Tracks the bits in 'tags'. */
 };
 
 void cls_rule_init(struct cls_rule *, const struct match *,
diff --git a/lib/tag.c b/lib/tag.c
index b45bcd5..13d1829 100644
--- a/lib/tag.c
+++ b/lib/tag.c
@@ -16,10 +16,6 @@
 
 #include <config.h>
 #include "tag.h"
-#include <limits.h>
-
-#define N_TAG_BITS (CHAR_BIT * sizeof(tag_type))
-BUILD_ASSERT_DECL(IS_POW2(N_TAG_BITS));
 
 #define LOG2_N_TAG_BITS (N_TAG_BITS == 32 ? 5 : N_TAG_BITS == 64 ? 6 : 0)
 BUILD_ASSERT_DECL(LOG2_N_TAG_BITS > 0);
@@ -37,3 +33,32 @@ tag_create_deterministic(uint32_t seed)
     y += y >= x;
     return (1u << x) | (1u << y);
 }
+
+/* Initializes 'tracker'. */
+void
+tag_tracker_init(struct tag_tracker *tracker)
+{
+    memset(tracker, 0, sizeof *tracker);
+}
+
+/* Adds 'add' to '*tags' and records the bits added in 'tracker'. */
+void
+tag_tracker_add(struct tag_tracker *tracker, tag_type *tags, tag_type add)
+{
+    *tags |= add;
+    for (; add; add = zero_rightmost_1bit(add)) {
+        tracker->counts[rightmost_1bit_idx(add)]++;
+    }
+}
+
+/* Removes 'sub' from 'tracker' and unsets any bits in '*tags' that no
+ * remaining tag includes. */
+void
+tag_tracker_subtract(struct tag_tracker *tracker, tag_type *tags, tag_type sub)
+{
+    for (; sub; sub = zero_rightmost_1bit(sub)) {
+        if (!--tracker->counts[rightmost_1bit_idx(sub)]) {
+            *tags &= ~rightmost_1bit(sub);
+        }
+    }
+}
diff --git a/lib/tag.h b/lib/tag.h
index 841177f..c99fd09 100644
--- a/lib/tag.h
+++ b/lib/tag.h
@@ -19,6 +19,7 @@
 
 #include <stdbool.h>
 #include <stdint.h>
+#include <limits.h>
 #include "util.h"
 
 /*
@@ -63,6 +64,9 @@
 /* Represents a tag, or the combination of 0 or more tags. */
 typedef uint32_t tag_type;
 
+#define N_TAG_BITS (CHAR_BIT * sizeof(tag_type))
+BUILD_ASSERT_DECL(IS_POW2(N_TAG_BITS));
+
 /* A 'tag_type' value that intersects every tag. */
 #define TAG_ALL UINT32_MAX
 
@@ -80,5 +84,17 @@ tag_intersects(tag_type a, tag_type b)
     tag_type x = a & b;
     return (x & (x - 1)) != 0;
 }
+
+/* Adding tags is easy, but subtracting is hard because you can't tell whether
+ * a bit was set only by the tag you're removing or by multiple tags.  The
+ * tag_tracker data structure counts the number of tags that set each bit,
+ * which allows for efficient subtraction. */
+struct tag_tracker {
+    unsigned int counts[N_TAG_BITS];
+};
+
+void tag_tracker_init(struct tag_tracker *);
+void tag_tracker_add(struct tag_tracker *, tag_type *, tag_type);
+void tag_tracker_subtract(struct tag_tracker *, tag_type *, tag_type);
 
 #endif /* tag.h */
-- 
1.7.10.4