2 * Copyright (c) 2008, 2011, 2012, 2013 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.
27 * A 'tag' represents an arbitrary category. Currently, tags are used to
28 * represent categories of flows and in particular the value of the 64-bit
29 * "metadata" field in the flow. The universe of possible categories is very
30 * large (2**64). The number of categories in use at a given time can also be
31 * large. This means that keeping track of category membership via
32 * conventional means (lists, bitmaps, etc.) is likely to be expensive.
34 * Tags are actually implemented via a "superimposed coding", as discussed in
35 * Knuth TAOCP v.3 section 6.5 "Retrieval on Secondary Keys". A tag is an
36 * unsigned integer in which exactly 2 bits are set to 1 and the rest set to 0.
37 * For 32-bit integers (as currently used) there are 32 * 31 / 2 = 496 unique
38 * tags; for 64-bit integers there are 64 * 63 / 2 = 2,016.
40 * Because there is a small finite number of unique tags, tags must collide
41 * after some number of them have been created. In practice we generally
42 * create tags by choosing bits randomly or based on a hash function.
44 * The key property of tags is that we can combine them without increasing the
45 * amount of data required using bitwise-OR, since the result has the 1-bits
46 * from both tags set. The necessary tradeoff is that the result is even more
47 * ambiguous: if combining two tags yields a value with 4 bits set to 1, then
48 * the result value will test as having 4 * 3 / 2 = 6 unique tags, not just the
49 * two tags that we combined.
51 * The upshot is this: a value that is the bitwise-OR combination of a number
52 * of tags will always include the tags that were combined, but it may contain
53 * any number of additional tags as well. This is acceptable for our use,
54 * since we want to be sure that we check every classifier table that contains
55 * a rule with a given metadata value, but it is OK if we check a few extra
58 * If we combine too many tags, then the result will have every bit set, so
59 * that it will test as including every tag. This can happen, but we hope that
60 * this is not the common case.
63 /* Represents a tag, or the combination of 0 or more tags. */
64 typedef uint32_t tag_type;
66 /* A 'tag_type' value that intersects every tag. */
67 #define TAG_ALL UINT32_MAX
69 /* An arbitrary tag. */
70 #define TAG_ARBITRARY UINT32_C(3)
72 tag_type tag_create_deterministic(uint32_t seed);
73 static inline bool tag_intersects(tag_type, tag_type);
75 /* Returns true if 'a' and 'b' have at least one tag in common,
76 * false if their set of tags is disjoint. */
78 tag_intersects(tag_type a, tag_type b)
81 return (x & (x - 1)) != 0;