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 /** initialize a bounded index extensible hash table
  94
  95     @param h - the bi-hash table to initialize
  96     @param name - name of the hash table
  97     @param nbuckets - the number of buckets, will be rounded up to
  98 a power of two
  99     @param memory_size - clib mheap size, in bytes
 100 */
 101
 102 void clib_bihash_init
 103   (clib_bihash * h, char *name, u32 nbuckets, uword memory_size);
 104
 105 /** Destroy a bounded index extensible hash table
 106     @param h - the bi-hash table to free
 107 */
 108
 109 void clib_bihash_free (clib_bihash * h);
 110
 111 /** Add or delete a (key,value) pair from a bi-hash table
 112
 113     @param h - the bi-hash table to search
 114     @param add_v - the (key,value) pair to add
 115     @param is_add - add=1, delete=0
 116     @returns 0 on success, < 0 on error
 117     @note This function will replace an existing (key,value) pair if the
 118     new key matches an existing key
 119 */
 120 int clib_bihash_add_del (clib_bihash * h, clib_bihash_kv * add_v, int is_add);
 121
 122
 123 /** Search a bi-hash table, use supplied hash code
 124
 125     @param h - the bi-hash table to search
 126     @param hash - the hash code
 127     @param in_out_kv - (key,value) pair containing the search key
 128     @returns 0 on success (with in_out_kv set), < 0 on error
 129 */
 130 int clib_bihash_search_inline_with_hash
 131   (clib_bihash * h, u64 hash, clib_bihash_kv * in_out_kv);
 132
 133 /** Search a bi-hash table
 134
 135     @param h - the bi-hash table to search
 136     @param in_out_kv - (key,value) pair containing the search key
 137     @returns 0 on success (with in_out_kv set), < 0 on error
 138 */
 139 int clib_bihash_search_inline (clib_bihash * h, clib_bihash_kv * in_out_kv);
 140
 141 /** Prefetch a bi-hash bucket given a hash code
 142
 143     @param h - the bi-hash table to search
 144     @param hash - the hash code
 145     @note see also clib_bihash_hash to compute the code
 146 */
 147 void clib_bihash_prefetch_bucket (clib_bihash * h, u64 hash);
 148
 149 /** Prefetch bi-hash (key,value) data given a hash code
 150
 151     @param h - the bi-hash table to search
 152     @param hash - the hash code
 153     @note assumes that the bucket has been prefetched, see
 154      clib_bihash_prefetch_bucket
 155 */
 156 void clib_bihash_prefetch_data (clib_bihash * h, u64 hash);
 157
 158 /** Search a bi-hash table
 159
 160     @param h - the bi-hash table to search
 161     @param search_key - (key,value) pair containing the search key
 162     @param valuep - (key,value) set to search result
 163     @returns 0 on success (with valuep set), < 0 on error
 164     @note used in situations where key modification is not desired
 165 */
 166 int clib_bihash_search_inline_2
 167   (clib_bihash * h, clib_bihash_kv * search_key, clib_bihash_kv * valuep);
 168
 169 /* Calback function for walking a bihash table
 170  *
 171  * @param kv - KV pair visited
 172  * @param ctx - Context passed to the walk
 173  * @return BIHASH_WALK_CONTINUE to continue BIHASH_WALK_STOP to stop
 174  */
 175 typedef int (*clib_bihash_foreach_key_value_pair_cb) (clib_bihash_kv * kv,
 176                                                       void *ctx);
 177
 178 /** Visit active (key,value) pairs in a bi-hash table
 179
 180     @param h - the bi-hash table to search
 181     @param callback - function to call with each active (key,value) pair
 182     @param arg - arbitrary second argument passed to the callback function
 183     First argument is the (key,value) pair to visit
 184 */
 185 void clib_bihash_foreach_key_value_pair (clib_bihash * h,
 186                                          clib_bihash_foreach_key_value_pair_cb
 187                                          * callback, void *arg);
 188
 189 /*
 190  * fd.io coding-style-patch-verification: ON
 191  *
 192  * Local Variables:
 193  * eval: (c-set-style "gnu")
 194  * End:
 195  */