lib/tag.h

   1 /*
   2  * Copyright (c) 2008, 2011 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 <assert.h>
  21 #include <stdbool.h>
  22 #include <stdint.h>
  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 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
  33  * table.
  34  *
  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.
  39  *
  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.
  45  *
  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.
  49  *
  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.
  56  *
  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.
  62  *
  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.
  67  */
  68
  69 /* Represents a tag, or the combination of 0 or more tags. */
  70 typedef uint32_t tag_type;
  71
  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);
  76
  77 /* Returns true if 'a' and 'b' have at least one tag in common,
  78  * false if their set of tags is disjoint. */
  79 static inline bool
  80 tag_intersects(tag_type a, tag_type b)
  81 {
  82     tag_type x = a & b;
  83     return (x & (x - 1)) != 0;
  84 }
  85
  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. */
  88 static inline bool
  89 tag_is_valid(tag_type tag)
  90 {
  91     tag_type x = tag & (tag - 1);
  92     tag_type y = x & (x - 1);
  93     return x && !y;
  94 }
  95 \f
  96 /*
  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.
 100  */
 101 #define TAG_SET_SIZE 4
 102 struct tag_set {
 103     tag_type total;
 104     tag_type tags[TAG_SET_SIZE];
 105     unsigned int n;
 106 };
 107
 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);
 113
 114 /* Returns true if 'set' will match no tags at all,
 115  * false if it will match at least one tag. */
 116 static inline bool
 117 tag_set_is_empty(const struct tag_set *set)
 118 {
 119     return !set->n;
 120 }
 121
 122 /* Returns true if any of the tags in 'tags' are also in 'set',
 123  * false if the intersection is empty. */
 124 static inline bool
 125 tag_set_intersects(const struct tag_set *set, tag_type tags)
 126 {
 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)));
 133 }
 134
 135 #endif /* tag.h */