vppinfra/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   union {
  46
  47     clib_bihash_kv kvp[BIHASH_KVP_PER_PAGE]; /**< the actual key/value pairs */
  48     clib_bihash_value * next_free; /**< used when a KVP page (or block thereof) is on a freelist */
  49   };
  50 } clib_bihash_value_t
  51
  52 /** bihash bucket structure */
  53 typedef struct {
  54   union {
  55     struct {
  56       u32 offset;  /**< backing page offset in the clib memory heap */
  57       u8 pad[3];   /**< log2 (size of the packing page block) */
  58       u8 log2_pages;
  59     };
  60     u64 as_u64;
  61   };
  62 } clib_bihash_bucket_t;
  63 #endif /* __defined_clib_bihash_bucket_t__ */
  64
  65 /** A bounded index extensible hash table */
  66 typedef struct {
  67   clib_bihash_bucket_t * buckets; /**< Hash bucket vector, power-of-two in size */
  68   volatile u32 * writer_lock; /**< Writer lock, in its own cache line */
  69   BVT(clib_bihash_value) ** working_copies; /**< Working copies (various sizes), to avoid locking against readers */
  70   clib_bihash_bucket_t saved_bucket; /**< Saved bucket pointer */
  71   u32 nbuckets;                      /**< Number of hash buckets */
  72   u32 log2_nbuckets;                 /**< lg(nbuckets) */
  73   u8 * name;                         /**< hash table name */
  74   BVT(clib_bihash_value) **freelists; /**< power of two freelist vector */
  75   void * mheap; /**< clib memory heap */
  76 } clib_bihash_t;
  77
  78 /** Get pointer to value page given its clib mheap offset */
  79 static inline void *
  80 clib_bihash_get_value (clib_bihash * h, uword offset);
  81
  82 /** Get clib mheap offset given a pointer */
  83 static inline uword clib_bihash_get_offset (clib_bihash * h, void * v);
  84
  85 /** initialize a bounded index extensible hash table
  86
  87     @param h - the bi-hash table to initialize
  88     @param name - name of the hash table
  89     @param nbuckets - the number of buckets, will be rounded up to
  90 a power of two
  91     @param memory_size - clib mheap size, in bytes
  92 */
  93
  94 void clib_bihash_init
  95 (clib_bihash * h, char * name, u32 nbuckets, uword memory_size);
  96
  97 /** Destroy a bounded index extensible hash table
  98     @param h - the bi-hash table to free
  99 */
 100
 101 void clib_bihash_free (clib_bihash * h);
 102
 103 /** Add or delete a (key,value) pair from a bi-hash table
 104
 105     @param h - the bi-hash table to search
 106     @param add_kv - the (key,value) pair to add
 107     @param is_add - add=1, delete=0
 108     @returns 0 on success, < 0 on error
 109     @note This function will replace an existing (key,value) pair if the
 110     new key matches an existing key
 111 */
 112 int clib_bihash_add_del (clib_bihash * h,
 113                          clib_bihash_kv * add_v,
 114                          int is_add);
 115
 116
 117 /** Search a bi-hash table
 118
 119     @param h - the bi-hash table to search
 120     @param search_v - (key,value) pair containing the search key
 121     @param return_v - (key,value) pair which matches search_v.key
 122     @returns 0 on success (with return_v set), < 0 on error
 123 */
 124 int clib_bihash_search (clib_bihash * h,
 125                         clib_bihash_kv * search_v,
 126                         clib_bihash_kv * return_v);
 127
 128
 129 /** Visit active (key,value) pairs in a bi-hash table
 130
 131     @param h - the bi-hash table to search
 132     @param callback - function to call with each active (key,value) pair
 133     @param arg - arbitrary second argument passed to the callback function
 134     First argument is the (key,value) pair to visit
 135     @note Trying to supply a proper function prototype for the
 136     callback function appears to be a fool's errand.
 137 */
 138 void clib_bihash_foreach_key_value_pair (clib_bihash) * h,
 139     void *callback,
 140     void *arg);