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 "util.h"
  23
  24 /*
  25  * Tagging support.
  26  *
  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.
  33  *
  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.
  39  *
  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.
  43  *
  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.
  50  *
  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
  56  * tables as well.
  57  *
  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.
  61  */
  62
  63 /* Represents a tag, or the combination of 0 or more tags. */
  64 typedef uint32_t tag_type;
  65
  66 /* A 'tag_type' value that intersects every tag. */
  67 #define TAG_ALL UINT32_MAX
  68
  69 /* An arbitrary tag. */
  70 #define TAG_ARBITRARY UINT32_C(3)
  71
  72 tag_type tag_create_deterministic(uint32_t seed);
  73 static inline bool tag_intersects(tag_type, tag_type);
  74
  75 /* Returns true if 'a' and 'b' have at least one tag in common,
  76  * false if their set of tags is disjoint. */
  77 static inline bool
  78 tag_intersects(tag_type a, tag_type b)
  79 {
  80     tag_type x = a & b;
  81     return (x & (x - 1)) != 0;
  82 }
  83
  84 #endif /* tag.h */