]>
Commit | Line | Data |
---|---|---|
b63e3bbc BP |
1 | /* |
2 | * Copyright (c) 2008, 2011, 2012, 2013 Nicira, Inc. | |
3 | * | |
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: | |
7 | * | |
8 | * http://www.apache.org/licenses/LICENSE-2.0 | |
9 | * | |
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. | |
15 | */ | |
16 | ||
17 | #ifndef TAG_H | |
18 | #define TAG_H 1 | |
19 | ||
20 | #include <stdbool.h> | |
21 | #include <stdint.h> | |
183126a1 | 22 | #include <limits.h> |
b63e3bbc BP |
23 | #include "util.h" |
24 | ||
25 | /* | |
26 | * Tagging support. | |
27 | * | |
28 | * A 'tag' represents an arbitrary category. Currently, tags are used to | |
29 | * represent categories of flows and in particular the value of the 64-bit | |
30 | * "metadata" field in the flow. The universe of possible categories is very | |
31 | * large (2**64). The number of categories in use at a given time can also be | |
32 | * large. This means that keeping track of category membership via | |
33 | * conventional means (lists, bitmaps, etc.) is likely to be expensive. | |
34 | * | |
35 | * Tags are actually implemented via a "superimposed coding", as discussed in | |
36 | * Knuth TAOCP v.3 section 6.5 "Retrieval on Secondary Keys". A tag is an | |
37 | * unsigned integer in which exactly 2 bits are set to 1 and the rest set to 0. | |
38 | * For 32-bit integers (as currently used) there are 32 * 31 / 2 = 496 unique | |
39 | * tags; for 64-bit integers there are 64 * 63 / 2 = 2,016. | |
40 | * | |
41 | * Because there is a small finite number of unique tags, tags must collide | |
42 | * after some number of them have been created. In practice we generally | |
43 | * create tags by choosing bits randomly or based on a hash function. | |
44 | * | |
45 | * The key property of tags is that we can combine them without increasing the | |
46 | * amount of data required using bitwise-OR, since the result has the 1-bits | |
47 | * from both tags set. The necessary tradeoff is that the result is even more | |
48 | * ambiguous: if combining two tags yields a value with 4 bits set to 1, then | |
49 | * the result value will test as having 4 * 3 / 2 = 6 unique tags, not just the | |
50 | * two tags that we combined. | |
51 | * | |
52 | * The upshot is this: a value that is the bitwise-OR combination of a number | |
53 | * of tags will always include the tags that were combined, but it may contain | |
54 | * any number of additional tags as well. This is acceptable for our use, | |
55 | * since we want to be sure that we check every classifier table that contains | |
56 | * a rule with a given metadata value, but it is OK if we check a few extra | |
57 | * tables as well. | |
58 | * | |
59 | * If we combine too many tags, then the result will have every bit set, so | |
60 | * that it will test as including every tag. This can happen, but we hope that | |
61 | * this is not the common case. | |
62 | */ | |
63 | ||
64 | /* Represents a tag, or the combination of 0 or more tags. */ | |
65 | typedef uint32_t tag_type; | |
66 | ||
183126a1 BP |
67 | #define N_TAG_BITS (CHAR_BIT * sizeof(tag_type)) |
68 | BUILD_ASSERT_DECL(IS_POW2(N_TAG_BITS)); | |
69 | ||
b63e3bbc BP |
70 | /* A 'tag_type' value that intersects every tag. */ |
71 | #define TAG_ALL UINT32_MAX | |
72 | ||
73 | /* An arbitrary tag. */ | |
74 | #define TAG_ARBITRARY UINT32_C(3) | |
75 | ||
76 | tag_type tag_create_deterministic(uint32_t seed); | |
77 | static inline bool tag_intersects(tag_type, tag_type); | |
78 | ||
79 | /* Returns true if 'a' and 'b' have at least one tag in common, | |
80 | * false if their set of tags is disjoint. */ | |
81 | static inline bool | |
82 | tag_intersects(tag_type a, tag_type b) | |
83 | { | |
84 | tag_type x = a & b; | |
85 | return (x & (x - 1)) != 0; | |
86 | } | |
183126a1 BP |
87 | \f |
88 | /* Adding tags is easy, but subtracting is hard because you can't tell whether | |
89 | * a bit was set only by the tag you're removing or by multiple tags. The | |
90 | * tag_tracker data structure counts the number of tags that set each bit, | |
91 | * which allows for efficient subtraction. */ | |
92 | struct tag_tracker { | |
93 | unsigned int counts[N_TAG_BITS]; | |
94 | }; | |
95 | ||
96 | void tag_tracker_init(struct tag_tracker *); | |
97 | void tag_tracker_add(struct tag_tracker *, tag_type *, tag_type); | |
98 | void tag_tracker_subtract(struct tag_tracker *, tag_type *, tag_type); | |
b63e3bbc BP |
99 | |
100 | #endif /* tag.h */ |