src/vppinfra/bihash_doc.h

   1 /*
   2  * Copyright (c) 2014 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14 */
  15
  16 #error do not #include this file!
  17
  18 /** \file
  19
  20     Bounded-index extensible hashing. The basic algorithm performs
  21     thread-safe constant-time lookups in the face of a rational number
  22     of hash collisions. The computed hash code h(k) must have
  23     reasonable statistics with respect to the key space. It won't do
  24     to have h(k) = 0 or 1, for all values of k.
  25
  26     Each bucket in the power-of-two bucket array contains the index
  27     (in a private vppinfra memory heap) of the "backing store" for the
  28     bucket, as well as a size field. The size field (log2_pages)
  29     corresponds to 1, 2, 4, ... contiguous "pages" containing the
  30     (key,value) pairs in the bucket.
  31
  32     When a single page fills, we allocate two contiguous pages.  We
  33     recompute h(k) for each (key,value) pair, using an additional bit
  34     to deal the (key, value) pairs into the "top" and "bottom" pages.
  35
  36     At lookup time, we compute h(k), using lg(bucket-array-size) to
  37     pick the bucket. We read the bucket to find the base of the
  38     backing pages.  We use an additional log2_pages' worth of bits
  39     from h(k) to compute the offset of the page which will contain the
  40     (key,value) pair we're trying to find.
  41 */
  42
  43 /** template key/value backing page structure */
  44 typedef struct clib_bihash_value
  45 {
  46   union
  47   {
  48
  49     clib_bihash_kv kvp[BIHASH_KVP_PER_PAGE]; /**< the actual key/value pairs */
  50     clib_bihash_value *next_free;  /**< used when a KVP page (or block thereof) is on a freelist */
  51   };
  52 } clib_bihash_value_t
  53 /** bihash bucket structure */
  54   typedef struct
  55 {
  56   union
  57   {
  58     struct
  59     {
  60       u32 offset;  /**< backing page offset in the clib memory heap */
  61       u8 pad[3];   /**< log2 (size of the packing page block) */
  62       u8 log2_pages;
  63     };
  64     u64 as_u64;
  65   };
  66 } clib_bihash_bucket_t;
  67
  68 /** A bounded index extensible hash table */
  69 typedef struct
  70 {
  71   clib_bihash_bucket_t *buckets;  /**< Hash bucket vector, power-of-two in size */
  72   volatile u32 *writer_lock;  /**< Writer lock, in its own cache line */
  73     BVT (clib_bihash_value) ** working_copies;
  74                                             /**< Working copies (various sizes), to avoid locking against readers */
  75   clib_bihash_bucket_t saved_bucket; /**< Saved bucket pointer */
  76   u32 nbuckets;                      /**< Number of hash buckets */
  77   u32 log2_nbuckets;                 /**< lg(nbuckets) */
  78   u8 *name;                          /**< hash table name */
  79     BVT (clib_bihash_value) ** freelists;
  80                                       /**< power of two freelist vector */
  81   uword alloc_arena;                  /**< memory allocation arena  */
  82   uword alloc_arena_next;             /**< first available mem chunk */
  83   uword alloc_arena_size;             /**< size of the arena */
  84 } clib_bihash_t;
  85
  86 /** Get pointer to value page given its clib mheap offset */
  87 static inline void *clib_bihash_get_value (clib_bihash * h, uword offset);
  88
  89 /** Get clib mheap offset given a pointer */
  90 static inline uword clib_bihash_get_offset (clib_bihash * h, void *v);
  91
  92 /** initialize a bounded index extensible hash table
  93
  94     @param h - the bi-hash table to initialize
  95     @param name - name of the hash table
  96     @param nbuckets - the number of buckets, will be rounded up to
  97 a power of two
  98     @param memory_size - clib mheap size, in bytes
  99 */
 100
 101 void clib_bihash_init
 102   (clib_bihash * h, char *name, u32 nbuckets, uword memory_size);
 103
 104 /** Destroy a bounded index extensible hash table
 105     @param h - the bi-hash table to free
 106 */
 107
 108 void clib_bihash_free (clib_bihash * h);
 109
 110 /** Add or delete a (key,value) pair from a bi-hash table
 111
 112     @param h - the bi-hash table to search
 113     @param add_v - the (key,value) pair to add
 114     @param is_add - add=1, delete=0
 115     @returns 0 on success, < 0 on error
 116     @note This function will replace an existing (key,value) pair if the
 117     new key matches an existing key
 118 */
 119 int clib_bihash_add_del (clib_bihash * h, clib_bihash_kv * add_v, int is_add);
 120
 121
 122 /** Search a bi-hash table, use supplied hash code
 123
 124     @param h - the bi-hash table to search
 125     @param hash - the hash code
 126     @param in_out_kv - (key,value) pair containing the search key
 127     @returns 0 on success (with in_out_kv set), < 0 on error
 128 */
 129 int clib_bihash_search_inline_with_hash
 130   (clib_bihash * h, u64 hash, clib_bihash_kv * in_out_kv);
 131
 132 /** Search a bi-hash table
 133
 134     @param h - the bi-hash table to search
 135     @param in_out_kv - (key,value) pair containing the search key
 136     @returns 0 on success (with in_out_kv set), < 0 on error
 137 */
 138 int clib_bihash_search_inline (clib_bihash * h, clib_bihash_kv * in_out_kv);
 139
 140 /** Prefetch a bi-hash bucket given a hash code
 141
 142     @param h - the bi-hash table to search
 143     @param hash - the hash code
 144     @note see also clib_bihash_hash to compute the code
 145 */
 146 void clib_bihash_prefetch_bucket (clib_bihash * h, u64 hash);
 147
 148 /** Prefetch bi-hash (key,value) data given a hash code
 149
 150     @param h - the bi-hash table to search
 151     @param hash - the hash code
 152     @note assumes that the bucket has been prefetched, see
 153      clib_bihash_prefetch_bucket
 154 */
 155 void clib_bihash_prefetch_data (clib_bihash * h, u64 hash);
 156
 157 /** Search a bi-hash table
 158
 159     @param h - the bi-hash table to search
 160     @param search_key - (key,value) pair containing the search key
 161     @param valuep - (key,value) set to search result
 162     @returns 0 on success (with valuep set), < 0 on error
 163     @note used in situations where key modification is not desired
 164 */
 165 int clib_bihash_search_inline_2
 166   (clib_bihash * h, clib_bihash_kv * search_key, clib_bihash_kv * valuep);
 167
 168 /* Calback function for walking a bihash table
 169  *
 170  * @param kv - KV pair visited
 171  * @param ctx - Context passed to the walk
 172  * @return BIHASH_WALK_CONTINUE to continue BIHASH_WALK_STOP to stop
 173  */
 174 typedef int (*clib_bihash_foreach_key_value_pair_cb) (clib_bihash_kv * kv,
 175                                                       void *ctx);
 176
 177 /** Visit active (key,value) pairs in a bi-hash table
 178
 179     @param h - the bi-hash table to search
 180     @param callback - function to call with each active (key,value) pair
 181     @param arg - arbitrary second argument passed to the callback function
 182     First argument is the (key,value) pair to visit
 183 */
 184 void clib_bihash_foreach_key_value_pair (clib_bihash * h,
 185                                          clib_bihash_foreach_key_value_pair_cb
 186                                          * callback, void *arg);
 187
 188 /*
 189  * fd.io coding-style-patch-verification: ON
 190  *
 191  * Local Variables:
 192  * eval: (c-set-style "gnu")
 193  * End:
 194  */