2 * Copyright (c) 2008, 2011 Nicira, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at:
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
28 * A 'tag' represents an arbitrary category. Currently, tags are used to
29 * represent categories of flows and in particular the dependencies for a flow
30 * switching decision. For example, if a flow's output port is based on
31 * knowledge that source MAC 00:02:e3:0f:80:a4 is on eth0, then a tag that
32 * represents that dependency is attached to that flow in the flowtracking hash
35 * As this example shows, the universe of possible categories is very large,
36 * and even the number of categories that are in use at a given time can be
37 * very large. This means that keeping track of category membership via
38 * conventional means (lists, bitmaps, etc.) is likely to be expensive.
40 * Tags are actually implemented via a "superimposed coding", as discussed in
41 * Knuth TAOCP v.3 section 6.5 "Retrieval on Secondary Keys". A tag is an
42 * unsigned integer in which exactly 2 bits are set to 1 and the rest set to 0.
43 * For 32-bit integers (as currently used) there are 32 * 31 / 2 = 496 unique
44 * tags; for 64-bit integers there are 64 * 63 / 2 = 2,016.
46 * Because there is a small finite number of unique tags, tags must collide
47 * after some number of them have been created. In practice we generally
48 * create tags by choosing bits randomly.
50 * The key property of tags is that we can combine them without increasing the
51 * amount of data required using bitwise-OR, since the result has the 1-bits
52 * from both tags set. The necessary tradeoff is that the result is even more
53 * ambiguous: if combining two tags yields a value with 4 bits set to 1, then
54 * the result value will test as having 4 * 3 / 2 = 6 unique tags, not just the
55 * two tags that we combined.
57 * The upshot is this: a value that is the bitwise-OR combination of a number
58 * of tags will always include the tags that were combined, but it may contain
59 * any number of additional tags as well. This is acceptable for flowtracking,
60 * since we want to be sure that we catch every flow that needs to be
61 * revalidated, but it is OK if we revalidate a few extra flows as well.
63 * If we combine too many tags, then the result will have every bit set, so
64 * that it will test as including every tag. Fortunately, this is not a big
65 * problem for us: although there are many flows overall, each individual flow
66 * belongs only to a small number of categories.
69 /* Represents a tag, or the combination of 0 or more tags. */
70 typedef uint32_t tag_type;
72 tag_type tag_create_random(void);
73 tag_type tag_create_deterministic(uint32_t seed);
74 static inline bool tag_intersects(tag_type, tag_type);
75 static inline bool tag_is_valid(tag_type);
77 /* Returns true if 'a' and 'b' have at least one tag in common,
78 * false if their set of tags is disjoint. */
80 tag_intersects(tag_type a, tag_type b)
83 return (x & (x - 1)) != 0;
86 /* Returns true if 'tag' is a valid tag, that is, if exactly two bits are set
87 * to 1 and the rest to 0. Otherwise, returns false. */
89 tag_is_valid(tag_type tag)
91 tag_type x = tag & (tag - 1);
92 tag_type y = x & (x - 1);
97 * A tag set accumulates tags with reduced ambiguity compared to a single tag.
98 * The flow tracking uses tag sets to keep track of tags that need to
99 * revalidated after a number of packets have been processed.
101 #define TAG_SET_SIZE 4
104 tag_type tags[TAG_SET_SIZE];
108 void tag_set_init(struct tag_set *);
109 void tag_set_add(struct tag_set *, tag_type);
110 void tag_set_union(struct tag_set *, const struct tag_set *);
111 static inline bool tag_set_is_empty(const struct tag_set *);
112 static inline bool tag_set_intersects(const struct tag_set *, tag_type);
114 /* Returns true if 'set' will match no tags at all,
115 * false if it will match at least one tag. */
117 tag_set_is_empty(const struct tag_set *set)
122 /* Returns true if any of the tags in 'tags' are also in 'set',
123 * false if the intersection is empty. */
125 tag_set_intersects(const struct tag_set *set, tag_type tags)
127 BUILD_ASSERT_DECL(TAG_SET_SIZE == 4);
128 return (tag_intersects(set->total, tags)
129 && (tag_intersects(set->tags[0], tags)
130 || tag_intersects(set->tags[1], tags)
131 || tag_intersects(set->tags[2], tags)
132 || tag_intersects(set->tags[3], tags)));