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;
}
}
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) {
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 *,
#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);
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);
+ }
+ }
+}
#include <stdbool.h>
#include <stdint.h>
+#include <limits.h>
#include "util.h"
/*
/* 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
tag_type x = a & b;
return (x & (x - 1)) != 0;
}
+\f
+/* 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 */