X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=lib%2Ftag.h;h=c99fd098eec3b1ec4af0c15f117f662b77c56576;hb=0ef165ecb57943e17a8ee8270df68ffb8d032e29;hp=9cb581d23a834204b091fb044cd2f96ae12aacdc;hpb=ddb378111158c603ef6f253095c496d9045b1905;p=sliver-openvswitch.git diff --git a/lib/tag.h b/lib/tag.h index 9cb581d23..c99fd098e 100644 --- a/lib/tag.h +++ b/lib/tag.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2008, 2011 Nicira Networks. + * Copyright (c) 2008, 2011, 2012, 2013 Nicira, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -17,24 +17,19 @@ #ifndef TAG_H #define TAG_H 1 -#include #include #include +#include #include "util.h" /* * Tagging support. * * A 'tag' represents an arbitrary category. Currently, tags are used to - * represent categories of flows and in particular the dependencies for a flow - * switching decision. For example, if a flow's output port is based on - * knowledge that source MAC 00:02:e3:0f:80:a4 is on eth0, then a tag that - * represents that dependency is attached to that flow in the flowtracking hash - * table. - * - * As this example shows, the universe of possible categories is very large, - * and even the number of categories that are in use at a given time can be - * very large. This means that keeping track of category membership via + * represent categories of flows and in particular the value of the 64-bit + * "metadata" field in the flow. The universe of possible categories is very + * large (2**64). The number of categories in use at a given time can also be + * large. This means that keeping track of category membership via * conventional means (lists, bitmaps, etc.) is likely to be expensive. * * Tags are actually implemented via a "superimposed coding", as discussed in @@ -45,7 +40,7 @@ * * Because there is a small finite number of unique tags, tags must collide * after some number of them have been created. In practice we generally - * create tags by choosing bits randomly. + * create tags by choosing bits randomly or based on a hash function. * * The key property of tags is that we can combine them without increasing the * amount of data required using bitwise-OR, since the result has the 1-bits @@ -56,23 +51,30 @@ * * The upshot is this: a value that is the bitwise-OR combination of a number * of tags will always include the tags that were combined, but it may contain - * any number of additional tags as well. This is acceptable for flowtracking, - * since we want to be sure that we catch every flow that needs to be - * revalidated, but it is OK if we revalidate a few extra flows as well. + * any number of additional tags as well. This is acceptable for our use, + * since we want to be sure that we check every classifier table that contains + * a rule with a given metadata value, but it is OK if we check a few extra + * tables as well. * * If we combine too many tags, then the result will have every bit set, so - * that it will test as including every tag. Fortunately, this is not a big - * problem for us: although there are many flows overall, each individual flow - * belongs only to a small number of categories. + * that it will test as including every tag. This can happen, but we hope that + * this is not the common case. */ /* Represents a tag, or the combination of 0 or more tags. */ typedef uint32_t tag_type; -tag_type tag_create_random(void); +#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 + +/* An arbitrary tag. */ +#define TAG_ARBITRARY UINT32_C(3) + tag_type tag_create_deterministic(uint32_t seed); static inline bool tag_intersects(tag_type, tag_type); -static inline bool tag_is_valid(tag_type); /* Returns true if 'a' and 'b' have at least one tag in common, * false if their set of tags is disjoint. */ @@ -82,54 +84,17 @@ tag_intersects(tag_type a, tag_type b) tag_type x = a & b; return (x & (x - 1)) != 0; } - -/* Returns true if 'tag' is a valid tag, that is, if exactly two bits are set - * to 1 and the rest to 0. Otherwise, returns false. */ -static inline bool -tag_is_valid(tag_type tag) -{ - tag_type x = tag & (tag - 1); - tag_type y = x & (x - 1); - return x && !y; -} -/* - * A tag set accumulates tags with reduced ambiguity compared to a single tag. - * The flow tracking uses tag sets to keep track of tags that need to - * revalidated after a number of packets have been processed. - */ -#define TAG_SET_SIZE 4 -struct tag_set { - tag_type total; - tag_type tags[TAG_SET_SIZE]; - unsigned int n; +/* 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_set_init(struct tag_set *); -void tag_set_add(struct tag_set *, tag_type); -void tag_set_union(struct tag_set *, const struct tag_set *); -static inline bool tag_set_is_empty(const struct tag_set *); -static inline bool tag_set_intersects(const struct tag_set *, tag_type); - -/* Returns true if 'set' will match no tags at all, - * false if it will match at least one tag. */ -static inline bool -tag_set_is_empty(const struct tag_set *set) -{ - return !set->n; -} - -/* Returns true if any of the tags in 'tags' are also in 'set', - * false if the intersection is empty. */ -static inline bool -tag_set_intersects(const struct tag_set *set, tag_type tags) -{ - BUILD_ASSERT_DECL(TAG_SET_SIZE == 4); - return (tag_intersects(set->total, tags) - && (tag_intersects(set->tags[0], tags) - || tag_intersects(set->tags[1], tags) - || tag_intersects(set->tags[2], tags) - || tag_intersects(set->tags[3], tags))); -} +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 */