lib/tag.h

   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>
  22 #include <limits.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 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
  67 #define N_TAG_BITS (CHAR_BIT * sizeof(tag_type))
  68 BUILD_ASSERT_DECL(IS_POW2(N_TAG_BITS));
  69
  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 }
  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);
  99
 100 #endif /* tag.h */