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   uword alloc_arena_mapped;           /**< size of mapped memory in the arena */
  85 } clib_bihash_t;
  86
  87 /** Get pointer to value page given its clib mheap offset */
  88 static inline void *clib_bihash_get_value (clib_bihash * h, uword offset);
  89
  90 /** Get clib mheap offset given a pointer */
  91 static inline uword clib_bihash_get_offset (clib_bihash * h, void *v);
  92
  93 /**
  94  * initialize a bounded index extensible hash table
  95  *
  96  * @param h - the bi-hash table to initialize
  97  * @param name - name of the hash table
  98  * @param nbuckets - the number of buckets, will be rounded up to
  99  * a power of two
 100  * @param memory_size - clib mheap size, in bytes
 101  */
 102 void clib_bihash_init
 103   (clib_bihash * h, char *name, u32 nbuckets, uword memory_size);
 104
 105 /**
 106  * initialize a bounded index extensible hash table with arguments passed as
 107  * a struct
 108  *
 109  * @param a - initialization parameters
 110  *   h - the bi-hash table to initialize;
 111  *   name - name of the hash table
 112  *   nbuckets - the number of buckets, will be rounded up to a power of two
 113  *   memory_size - clib mheap size, in bytes
 114  *   format_function_t - format function for the bihash kv pairs
 115  *   instantiate_immediately - allocate memory right away
 116  *   dont_add_to_all_bihash_list - dont mention in 'show bihash'
 117  */
 118 void BV (clib_bihash_init2) (BVT (clib_bihash_init2_args) * a);
 119
 120 /**
 121  * Set the formating function for the bihash
 122  *
 123  * @param h - the bi-hash table
 124  * @param kvp_fmt_fn - the format function
 125  */
 126 void BV (clib_bihash_set_kvp_format_fn) (BVT (clib_bihash) * h,
 127                                          format_function_t *kvp_fmt_fn);
 128
 129 /**
 130  * Destroy a bounded index extensible hash table
 131  *
 132  * @param h - the bi-hash table to free
 133  */
 134 void clib_bihash_free (clib_bihash *h);
 135
 136 /**
 137  * Add or delete a (key,value) pair from a bi-hash table
 138  *
 139  * @param h - the bi-hash table to search
 140  * @param add_v - the (key,value) pair to add
 141  * @param is_add - add=1 (BIHASH_ADD), delete=0 (BIHASH_DEL)
 142  * @returns 0 on success, < 0 on error
 143  * @note This function will replace an existing (key,value) pair if the
 144  * new key matches an existing key
 145  */
 146 int clib_bihash_add_del (clib_bihash * h, clib_bihash_kv * add_v, int is_add);
 147
 148 /**
 149  * Add or delete a (key,value) pair from a bi-hash table, using a pre-computed
 150  * hash
 151  *
 152  * @param h - the bi-hash table to search
 153  * @param add_v - the (key,value) pair to add
 154  * @param hash - the precomputed hash of the key
 155  * @param is_add - add=1 (BIHASH_ADD), delete=0 (BIHASH_DEL)
 156  * @returns 0 on success, < 0 on error
 157  * @note This function will replace an existing (key,value) pair if the
 158  * new key matches an existing key
 159  */
 160 int BV (clib_bihash_add_del_with_hash) (BVT (clib_bihash) * h,
 161                                         BVT (clib_bihash_kv) * add_v, u64 hash,
 162                                         int is_add);
 163
 164 /**
 165  * Add a (key,value) pair to a bi-hash table, and tries to free stale entries
 166  * on collisions with passed filter.
 167  *
 168  * @param h - the bi-hash table to search
 169  * @param add_v - the (key,value) pair to add
 170  * @param is_stale_cb - callback receiving a kv pair, returning 1 if the kv is
 171  * stale and can be overwriten. This will be called on adding a kv in a full
 172  * page before trying to split & rehash its bucket.
 173  * @param arg - opaque arguement passed to is_stale_cb
 174  * @returns 0 on success, < 0 on error
 175  * @note This function will replace an existing (key,value) pair if the
 176  * new key matches an existing key
 177  */
 178 int BV (clib_bihash_add_or_overwrite_stale) (
 179   BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
 180   int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg);
 181
 182 /**
 183  * Add a (key,value) pair to a bi-hash table, calling a callback on overwrite
 184  * with the bucket lock held.
 185  *
 186  * @param h - the bi-hash table to search
 187  * @param add_v - the (key,value) pair to add
 188  * @param overwrite_cb - callback called when overwriting a key, allowing
 189  * you to cleanup the value with the bucket lock held.
 190  * @param arg - opaque arguement passed to overwrite_cb
 191  * @returns 0 on success, < 0 on error
 192  * @note This function will replace an existing (key,value) pair if the
 193  * new key matches an existing key
 194  */
 195 int BV (clib_bihash_add_with_overwrite_cb) (
 196   BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
 197   void (*overwrite_cb) (BVT (clib_bihash_kv) *, void *), void *arg);
 198
 199 /**
 200  * Tells if the bihash was initialised (i.e. mem allocated by first add)
 201  *
 202  * @param h - the bi-hash table to search
 203  */
 204 int BV (clib_bihash_is_initialised) (const BVT (clib_bihash) * h);
 205
 206 /**
 207  * Search a bi-hash table, use supplied hash code
 208  *
 209  * @param h - the bi-hash table to search
 210  * @param hash - the hash code
 211  * @param in_out_kv - (key,value) pair containing the search key
 212  * @returns 0 on success (with in_out_kv set), < 0 on error
 213  */
 214 int clib_bihash_search_inline_with_hash (clib_bihash *h, u64 hash,
 215                                          clib_bihash_kv *in_out_kv);
 216
 217 /**
 218  * Search a bi-hash table
 219  *
 220  * @param h - the bi-hash table to search
 221  * @param in_out_kv - (key,value) pair containing the search key
 222  * @returns 0 on success (with in_out_kv set), < 0 on error
 223  */
 224 int clib_bihash_search_inline (clib_bihash *h, clib_bihash_kv *in_out_kv);
 225
 226 /**
 227  * Prefetch a bi-hash bucket given a hash code
 228  *
 229  * @param h - the bi-hash table to search
 230  * @param hash - the hash code
 231  * @note see also clib_bihash_hash to compute the code
 232  */
 233 void clib_bihash_prefetch_bucket (clib_bihash * h, u64 hash);
 234
 235 /**
 236  * Prefetch bi-hash (key,value) data given a hash code
 237  *
 238  * @param h - the bi-hash table to search
 239  * @param hash - the hash code
 240  * @note assumes that the bucket has been prefetched, see
 241  * clib_bihash_prefetch_bucket
 242  */
 243 void clib_bihash_prefetch_data (clib_bihash * h, u64 hash);
 244
 245 /**
 246  * Search a bi-hash table
 247  *
 248  * @param h - the bi-hash table to search
 249  * @param search_key - (key,value) pair containing the search key
 250  * @param valuep - (key,value) set to search result
 251  * @returns 0 on success (with valuep set), < 0 on error
 252  * @note used in situations where key modification is not desired
 253  */
 254 int clib_bihash_search_inline_2
 255   (clib_bihash * h, clib_bihash_kv * search_key, clib_bihash_kv * valuep);
 256
 257 /**
 258  * Calback function for walking a bihash table
 259  *
 260  * @param kv - KV pair visited
 261  * @param ctx - Context passed to the walk
 262  * @return BIHASH_WALK_CONTINUE to continue BIHASH_WALK_STOP to stop
 263  */
 264 typedef int (*clib_bihash_foreach_key_value_pair_cb) (clib_bihash_kv * kv,
 265                                                       void *ctx);
 266
 267 /**
 268  * Visit active (key,value) pairs in a bi-hash table
 269  *
 270  * @param h - the bi-hash table to search
 271  * @param callback - function to call with each active (key,value) pair
 272  * @param arg - arbitrary second argument passed to the callback function
 273  * First argument is the (key,value) pair to visit
 274  */
 275 void clib_bihash_foreach_key_value_pair (clib_bihash * h,
 276                                          clib_bihash_foreach_key_value_pair_cb
 277                                          * callback, void *arg);
 278
 279 /*
 280  * fd.io coding-style-patch-verification: ON
 281  *
 282  * Local Variables:
 283  * eval: (c-set-style "gnu")
 284  * End:
 285  */