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

[Jarno Rajahalme]

On Sep 25, 2013, at 3:42 PM, Ben Pfaff <blp at nicira.com> wrote:

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

At first the tracker implementation seems heavy, but then the tag ever only contains two bits set.

The tag collection now takes more space, maybe we do not need full 64 bits for each counter?

Haven't tested but looks good.

  Jarno

> 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
> 
> _______________________________________________
> dev mailing list
> dev at openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev