It is needed for the classifier partitioning optimization.
Signed-off-by: Ben Pfaff <b...@nicira.com>
---
lib/automake.mk | 2 +
lib/tag.c | 117 ++++++++++++++++++++++++++++++++++++++++++++++++
lib/tag.h | 134 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 253 insertions(+)
create mode 100644 lib/tag.c
create mode 100644 lib/tag.h
diff --git a/lib/automake.mk b/lib/automake.mk
index da1896a..820ee1a 100644
--- a/lib/automake.mk
+++ b/lib/automake.mk
@@ -197,6 +197,8 @@ lib_libopenvswitch_a_SOURCES = \
lib/svec.h \
lib/table.c \
lib/table.h \
+ lib/tag.c \
+ lib/tag.h \
lib/timer.c \
lib/timer.h \
lib/timeval.c \
diff --git a/lib/tag.c b/lib/tag.c
new file mode 100644
index 0000000..f064d17
--- /dev/null
+++ b/lib/tag.c
@@ -0,0 +1,117 @@
+/*
+ * Copyright (c) 2008, 2009, 2010, 2011 Nicira, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <config.h>
+#include "tag.h"
+#include <limits.h>
+#include "random.h"
+#include "type-props.h"
+#include "util.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);
+
+/* Returns a randomly selected tag. */
+tag_type
+tag_create_random(void)
+{
+ int x, y;
+ do {
+ uint16_t r = random_uint16();
+ x = r & (N_TAG_BITS - 1);
+ y = r >> (16 - LOG2_N_TAG_BITS);
+ } while (x == y);
+ return (1u << x) | (1u << y);
+}
+
+/* Returns a tag deterministically generated from 'seed'.
+ *
+ * 'seed' should have data in all of its bits; if it has data only in its
+ * low-order bits then the resulting tags will be poorly distributed. Use a
+ * hash function such as hash_bytes() to generate 'seed' if necessary. */
+tag_type
+tag_create_deterministic(uint32_t seed)
+{
+ int x = seed & (N_TAG_BITS - 1);
+ int y = (seed >> LOG2_N_TAG_BITS) % (N_TAG_BITS - 1);
+ y += y >= x;
+ return (1u << x) | (1u << y);
+}
+
+/* Initializes 'set' as an empty tag set. */
+void
+tag_set_init(struct tag_set *set)
+{
+ memset(set, 0, sizeof *set);
+}
+
+static bool
+tag_is_worth_adding(const struct tag_set *set, tag_type tag)
+{
+ if (!tag) {
+ /* Nothing to add. */
+ return false;
+ } else if ((set->total & tag) != tag) {
+ /* 'set' doesn't have all the bits in 'tag', so we need to add it. */
+ return true;
+ } else {
+ /* We can drop it if some member of 'set' already includes all of the
+ * 1-bits in 'tag'. (tag_set_intersects() does a different test:
+ * whether some member of 'set' has at least two 1-bit in common with
+ * 'tag'.) */
+ int i;
+
+ for (i = 0; i < TAG_SET_SIZE; i++) {
+ if ((set->tags[i] & tag) == tag) {
+ return false;
+ }
+ }
+ return true;
+ }
+}
+
+/* Adds 'tag' to 'set'. */
+void
+tag_set_add(struct tag_set *set, tag_type tag)
+{
+ if (tag_is_worth_adding(set, tag)) {
+ /* XXX We could do better by finding the set member to which we would
+ * add the fewest number of 1-bits. This would reduce the amount of
+ * ambiguity, since e.g. three 1-bits match 3 * 2 / 2 = 3 unique tags
+ * whereas four 1-bits match 4 * 3 / 2 = 6 unique tags. */
+ tag_type *t = &set->tags[set->n++ % TAG_SET_SIZE];
+ *t |= tag;
+ if (*t == TYPE_MAXIMUM(tag_type)) {
+ set->tags[0] = *t;
+ }
+
+ set->total |= tag;
+ }
+}
+
+/* Adds all the tags in 'other' to 'set'. */
+void
+tag_set_union(struct tag_set *set, const struct tag_set *other)
+{
+ size_t i;
+
+ for (i = 0; i < TAG_SET_SIZE; i++) {
+ tag_set_add(set, other->tags[i]);
+ }
+}
diff --git a/lib/tag.h b/lib/tag.h
new file mode 100644
index 0000000..9d6b4aa
--- /dev/null
+++ b/lib/tag.h
@@ -0,0 +1,134 @@
+/*
+ * Copyright (c) 2008, 2011, 2012 Nicira, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef TAG_H
+#define TAG_H 1
+
+#include <stdbool.h>
+#include <stdint.h>
+#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
+ * conventional means (lists, bitmaps, etc.) is likely to be expensive.
+ *
+ * Tags are actually implemented via a "superimposed coding", as discussed in
+ * Knuth TAOCP v.3 section 6.5 "Retrieval on Secondary Keys". A tag is an
+ * unsigned integer in which exactly 2 bits are set to 1 and the rest set to 0.
+ * For 32-bit integers (as currently used) there are 32 * 31 / 2 = 496 unique
+ * tags; for 64-bit integers there are 64 * 63 / 2 = 2,016.
+ *
+ * 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.
+ *
+ * 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
+ * from both tags set. The necessary tradeoff is that the result is even more
+ * ambiguous: if combining two tags yields a value with 4 bits set to 1, then
+ * the result value will test as having 4 * 3 / 2 = 6 unique tags, not just the
+ * two tags that we combined.
+ *
+ * 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.
+ *
+ * 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.
+ */
+
+/* Represents a tag, or the combination of 0 or more tags. */
+typedef uint32_t tag_type;
+
+tag_type tag_create_random(void);
+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. */
+static inline bool
+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;
+};
+
+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)));
+}
+
+#endif /* tag.h */
--
1.7.10.4
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
