src/vppinfra/bihash_template.h

   1 /*
   2   Copyright (c) 2014 Cisco and/or its affiliates.
   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 /** @cond DOCUMENTATION_IS_IN_BIHASH_DOC_H */
  18
  19 /*
  20  * Note: to instantiate the template multiple times in a single file,
  21  * #undef __included_bihash_template_h__...
  22  */
  23 #ifndef __included_bihash_template_h__
  24 #define __included_bihash_template_h__
  25
  26 #include <vppinfra/heap.h>
  27 #include <vppinfra/format.h>
  28 #include <vppinfra/pool.h>
  29 #include <vppinfra/cache.h>
  30
  31 #ifndef BIHASH_TYPE
  32 #error BIHASH_TYPE not defined
  33 #endif
  34
  35 #define _bv(a,b) a##b
  36 #define __bv(a,b) _bv(a,b)
  37 #define BV(a) __bv(a,BIHASH_TYPE)
  38
  39 #define _bvt(a,b) a##b##_t
  40 #define __bvt(a,b) _bvt(a,b)
  41 #define BVT(a) __bvt(a,BIHASH_TYPE)
  42
  43 typedef struct BV (clib_bihash_value)
  44 {
  45   union
  46   {
  47     BVT (clib_bihash_kv) kvp[BIHASH_KVP_PER_PAGE];
  48     struct BV (clib_bihash_value) * next_free;
  49   };
  50 } BVT (clib_bihash_value);
  51
  52 #if BIHASH_KVP_CACHE_SIZE > 5
  53 #error Requested KVP cache LRU data exceeds 16 bits
  54 #endif
  55
  56 typedef struct
  57 {
  58   union
  59   {
  60     struct
  61     {
  62       u32 offset;
  63       u8 linear_search;
  64       u8 log2_pages;
  65       i16 refcnt;
  66     };
  67     u64 as_u64;
  68   };
  69 #if BIHASH_KVP_CACHE_SIZE > 0
  70   u16 cache_lru;
  71     BVT (clib_bihash_kv) cache[BIHASH_KVP_CACHE_SIZE];
  72 #endif
  73 } BVT (clib_bihash_bucket);
  74
  75 typedef struct
  76 {
  77   BVT (clib_bihash_value) * values;
  78   BVT (clib_bihash_bucket) * buckets;
  79   volatile u32 *writer_lock;
  80
  81     BVT (clib_bihash_value) ** working_copies;
  82   int *working_copy_lengths;
  83     BVT (clib_bihash_bucket) saved_bucket;
  84
  85   u32 nbuckets;
  86   u32 log2_nbuckets;
  87   u8 *name;
  88
  89   u64 cache_hits;
  90   u64 cache_misses;
  91
  92     BVT (clib_bihash_value) ** freelists;
  93
  94   /*
  95    * Backing store allocation. Since bihash manages its own
  96    * freelists, we simple dole out memory at alloc_arena_next.
  97    */
  98   uword alloc_arena;
  99   uword alloc_arena_next;
 100   uword alloc_arena_size;
 101
 102   /**
 103     * A custom format function to print the Key and Value of bihash_key instead of default hexdump
 104     */
 105   format_function_t *fmt_fn;
 106
 107 } BVT (clib_bihash);
 108
 109
 110 static inline void
 111 BV (clib_bihash_update_lru) (BVT (clib_bihash_bucket) * b, u8 slot)
 112 {
 113 #if BIHASH_KVP_CACHE_SIZE > 1
 114   u16 value, tmp, mask;
 115   u8 found_lru_pos;
 116   u16 save_hi;
 117
 118   ASSERT (slot < BIHASH_KVP_CACHE_SIZE);
 119
 120   /* First, find the slot in cache_lru */
 121   mask = slot;
 122   if (BIHASH_KVP_CACHE_SIZE > 1)
 123     mask |= slot << 3;
 124   if (BIHASH_KVP_CACHE_SIZE > 2)
 125     mask |= slot << 6;
 126   if (BIHASH_KVP_CACHE_SIZE > 3)
 127     mask |= slot << 9;
 128   if (BIHASH_KVP_CACHE_SIZE > 4)
 129     mask |= slot << 12;
 130
 131   value = b->cache_lru;
 132   tmp = value ^ mask;
 133
 134   /* Already the most-recently used? */
 135   if ((tmp & 7) == 0)
 136     return;
 137
 138   found_lru_pos = ((tmp & (7 << 3)) == 0) ? 1 : 0;
 139   if (BIHASH_KVP_CACHE_SIZE > 2)
 140     found_lru_pos = ((tmp & (7 << 6)) == 0) ? 2 : found_lru_pos;
 141   if (BIHASH_KVP_CACHE_SIZE > 3)
 142     found_lru_pos = ((tmp & (7 << 9)) == 0) ? 3 : found_lru_pos;
 143   if (BIHASH_KVP_CACHE_SIZE > 4)
 144     found_lru_pos = ((tmp & (7 << 12)) == 0) ? 4 : found_lru_pos;
 145
 146   ASSERT (found_lru_pos);
 147
 148   /* create a mask to kill bits in or above slot */
 149   mask = 0xFFFF << found_lru_pos;
 150   mask <<= found_lru_pos;
 151   mask <<= found_lru_pos;
 152   mask ^= 0xFFFF;
 153   tmp = value & mask;
 154
 155   /* Save bits above slot */
 156   mask ^= 0xFFFF;
 157   mask <<= 3;
 158   save_hi = value & mask;
 159
 160   value = save_hi | (tmp << 3) | slot;
 161
 162   b->cache_lru = value;
 163 #endif
 164 }
 165
 166 void
 167 BV (clib_bihash_update_lru_not_inline) (BVT (clib_bihash_bucket) * b,
 168                                         u8 slot);
 169
 170 static inline u8 BV (clib_bihash_get_lru) (BVT (clib_bihash_bucket) * b)
 171 {
 172 #if BIHASH_KVP_CACHE_SIZE > 0
 173   return (b->cache_lru >> (3 * (BIHASH_KVP_CACHE_SIZE - 1))) & 7;
 174 #else
 175   return 0;
 176 #endif
 177 }
 178
 179 static inline void BV (clib_bihash_reset_cache) (BVT (clib_bihash_bucket) * b)
 180 {
 181 #if BIHASH_KVP_CACHE_SIZE > 0
 182   u16 initial_lru_value;
 183
 184   memset (b->cache, 0xff, sizeof (b->cache));
 185
 186   /*
 187    * We'll want the cache to be loaded from slot 0 -> slot N, so
 188    * the initial LRU order is reverse index order.
 189    */
 190   if (BIHASH_KVP_CACHE_SIZE == 1)
 191     initial_lru_value = 0;
 192   else if (BIHASH_KVP_CACHE_SIZE == 2)
 193     initial_lru_value = (0 << 3) | (1 << 0);
 194   else if (BIHASH_KVP_CACHE_SIZE == 3)
 195     initial_lru_value = (0 << 6) | (1 << 3) | (2 << 0);
 196   else if (BIHASH_KVP_CACHE_SIZE == 4)
 197     initial_lru_value = (0 << 9) | (1 << 6) | (2 << 3) | (3 << 0);
 198   else if (BIHASH_KVP_CACHE_SIZE == 5)
 199     initial_lru_value = (0 << 12) | (1 << 9) | (2 << 6) | (3 << 3) | (4 << 0);
 200
 201   b->cache_lru = initial_lru_value;
 202 #endif
 203 }
 204
 205 static inline int BV (clib_bihash_lock_bucket) (BVT (clib_bihash_bucket) * b)
 206 {
 207 #if BIHASH_KVP_CACHE_SIZE > 0
 208   u16 cache_lru_bit;
 209   u16 rv;
 210
 211   cache_lru_bit = 1 << 15;
 212
 213   rv = __sync_fetch_and_or (&b->cache_lru, cache_lru_bit);
 214   /* Was already locked? */
 215   if (rv & (1 << 15))
 216     return 0;
 217 #endif
 218   return 1;
 219 }
 220
 221 static inline void BV (clib_bihash_unlock_bucket)
 222   (BVT (clib_bihash_bucket) * b)
 223 {
 224 #if BIHASH_KVP_CACHE_SIZE > 0
 225   u16 cache_lru;
 226
 227   cache_lru = b->cache_lru & ~(1 << 15);
 228   b->cache_lru = cache_lru;
 229 #endif
 230 }
 231
 232 static inline void *BV (clib_bihash_get_value) (BVT (clib_bihash) * h,
 233                                                 uword offset)
 234 {
 235   u8 *hp = (u8 *) h->alloc_arena;
 236   u8 *vp = hp + offset;
 237
 238   return (void *) vp;
 239 }
 240
 241 static inline uword BV (clib_bihash_get_offset) (BVT (clib_bihash) * h,
 242                                                  void *v)
 243 {
 244   u8 *hp, *vp;
 245
 246   hp = (u8 *) h->alloc_arena;
 247   vp = (u8 *) v;
 248
 249   return vp - hp;
 250 }
 251
 252 void BV (clib_bihash_init)
 253   (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size);
 254
 255 void BV (clib_bihash_set_kvp_format_fn) (BVT (clib_bihash) * h,
 256                                          format_function_t * fmt_fn);
 257
 258 void BV (clib_bihash_free) (BVT (clib_bihash) * h);
 259
 260 int BV (clib_bihash_add_del) (BVT (clib_bihash) * h,
 261                               BVT (clib_bihash_kv) * add_v, int is_add);
 262 int BV (clib_bihash_search) (BVT (clib_bihash) * h,
 263                              BVT (clib_bihash_kv) * search_v,
 264                              BVT (clib_bihash_kv) * return_v);
 265
 266 void BV (clib_bihash_foreach_key_value_pair) (BVT (clib_bihash) * h,
 267                                               void *callback, void *arg);
 268
 269 format_function_t BV (format_bihash);
 270 format_function_t BV (format_bihash_kvp);
 271 format_function_t BV (format_bihash_lru);
 272
 273 static inline int BV (clib_bihash_search_inline_with_hash)
 274   (BVT (clib_bihash) * h, u64 hash, BVT (clib_bihash_kv) * key_result)
 275 {
 276   u32 bucket_index;
 277   BVT (clib_bihash_value) * v;
 278   BVT (clib_bihash_bucket) * b;
 279 #if BIHASH_KVP_CACHE_SIZE > 0
 280   BVT (clib_bihash_kv) * kvp;
 281 #endif
 282   int i, limit;
 283
 284   bucket_index = hash & (h->nbuckets - 1);
 285   b = &h->buckets[bucket_index];
 286
 287   if (b->offset == 0)
 288     return -1;
 289
 290 #if BIHASH_KVP_CACHE_SIZE > 0
 291   /* Check the cache, if not currently locked */
 292   if (PREDICT_TRUE ((b->cache_lru & (1 << 15)) == 0))
 293     {
 294       limit = BIHASH_KVP_CACHE_SIZE;
 295       kvp = b->cache;
 296       for (i = 0; i < limit; i++)
 297         {
 298           if (BV (clib_bihash_key_compare) (kvp[i].key, key_result->key))
 299             {
 300               *key_result = kvp[i];
 301               h->cache_hits++;
 302               return 0;
 303             }
 304         }
 305     }
 306 #endif
 307
 308   hash >>= h->log2_nbuckets;
 309
 310   v = BV (clib_bihash_get_value) (h, b->offset);
 311
 312   /* If the bucket has unresolvable collisions, use linear search */
 313   limit = BIHASH_KVP_PER_PAGE;
 314   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 315   if (PREDICT_FALSE (b->linear_search))
 316     limit <<= b->log2_pages;
 317
 318   for (i = 0; i < limit; i++)
 319     {
 320       if (BV (clib_bihash_key_compare) (v->kvp[i].key, key_result->key))
 321         {
 322           *key_result = v->kvp[i];
 323
 324 #if BIHASH_KVP_CACHE_SIZE > 0
 325           u8 cache_slot;
 326           /* Try to lock the bucket */
 327           if (BV (clib_bihash_lock_bucket) (b))
 328             {
 329               cache_slot = BV (clib_bihash_get_lru) (b);
 330               b->cache[cache_slot] = v->kvp[i];
 331               BV (clib_bihash_update_lru) (b, cache_slot);
 332
 333               /* Unlock the bucket */
 334               BV (clib_bihash_unlock_bucket) (b);
 335               h->cache_misses++;
 336             }
 337 #endif
 338           return 0;
 339         }
 340     }
 341   return -1;
 342 }
 343
 344 static inline int BV (clib_bihash_search_inline)
 345   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * key_result)
 346 {
 347   u64 hash;
 348
 349   hash = BV (clib_bihash_hash) (key_result);
 350
 351   return BV (clib_bihash_search_inline_with_hash) (h, hash, key_result);
 352 }
 353
 354 static inline void BV (clib_bihash_prefetch_bucket)
 355   (BVT (clib_bihash) * h, u64 hash)
 356 {
 357   u32 bucket_index;
 358   BVT (clib_bihash_bucket) * b;
 359
 360   bucket_index = hash & (h->nbuckets - 1);
 361   b = &h->buckets[bucket_index];
 362
 363   CLIB_PREFETCH (b, CLIB_CACHE_LINE_BYTES, READ);
 364 }
 365
 366 static inline void BV (clib_bihash_prefetch_data)
 367   (BVT (clib_bihash) * h, u64 hash)
 368 {
 369   u32 bucket_index;
 370   BVT (clib_bihash_value) * v;
 371   BVT (clib_bihash_bucket) * b;
 372
 373   bucket_index = hash & (h->nbuckets - 1);
 374   b = &h->buckets[bucket_index];
 375
 376   if (PREDICT_FALSE (b->offset == 0))
 377     return;
 378
 379   hash >>= h->log2_nbuckets;
 380   v = BV (clib_bihash_get_value) (h, b->offset);
 381
 382   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 383
 384   CLIB_PREFETCH (v, CLIB_CACHE_LINE_BYTES, READ);
 385 }
 386
 387 static inline int BV (clib_bihash_search_inline_2_with_hash)
 388   (BVT (clib_bihash) * h,
 389    u64 hash, BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
 390 {
 391   u32 bucket_index;
 392   BVT (clib_bihash_value) * v;
 393   BVT (clib_bihash_bucket) * b;
 394 #if BIHASH_KVP_CACHE_SIZE > 0
 395   BVT (clib_bihash_kv) * kvp;
 396 #endif
 397   int i, limit;
 398
 399   ASSERT (valuep);
 400
 401   bucket_index = hash & (h->nbuckets - 1);
 402   b = &h->buckets[bucket_index];
 403
 404   if (b->offset == 0)
 405     return -1;
 406
 407   /* Check the cache, if currently unlocked */
 408 #if BIHASH_KVP_CACHE_SIZE > 0
 409   if (PREDICT_TRUE ((b->cache_lru & (1 << 15)) == 0))
 410     {
 411       limit = BIHASH_KVP_CACHE_SIZE;
 412       kvp = b->cache;
 413       for (i = 0; i < limit; i++)
 414         {
 415           if (BV (clib_bihash_key_compare) (kvp[i].key, search_key->key))
 416             {
 417               *valuep = kvp[i];
 418               h->cache_hits++;
 419               return 0;
 420             }
 421         }
 422     }
 423 #endif
 424
 425   hash >>= h->log2_nbuckets;
 426   v = BV (clib_bihash_get_value) (h, b->offset);
 427
 428   /* If the bucket has unresolvable collisions, use linear search */
 429   limit = BIHASH_KVP_PER_PAGE;
 430   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 431   if (PREDICT_FALSE (b->linear_search))
 432     limit <<= b->log2_pages;
 433
 434   for (i = 0; i < limit; i++)
 435     {
 436       if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
 437         {
 438           *valuep = v->kvp[i];
 439
 440 #if BIHASH_KVP_CACHE_SIZE > 0
 441           u8 cache_slot;
 442
 443           /* Try to lock the bucket */
 444           if (BV (clib_bihash_lock_bucket) (b))
 445             {
 446               cache_slot = BV (clib_bihash_get_lru) (b);
 447               b->cache[cache_slot] = v->kvp[i];
 448               BV (clib_bihash_update_lru) (b, cache_slot);
 449
 450               /* Reenable the cache */
 451               BV (clib_bihash_unlock_bucket) (b);
 452               h->cache_misses++;
 453             }
 454 #endif
 455           return 0;
 456         }
 457     }
 458   return -1;
 459 }
 460
 461 static inline int BV (clib_bihash_search_inline_2)
 462   (BVT (clib_bihash) * h,
 463    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
 464 {
 465   u64 hash;
 466
 467   hash = BV (clib_bihash_hash) (search_key);
 468
 469   return BV (clib_bihash_search_inline_2_with_hash) (h, hash, search_key,
 470                                                      valuep);
 471 }
 472
 473
 474 #endif /* __included_bihash_template_h__ */
 475
 476 /** @endcond */
 477
 478 /*
 479  * fd.io coding-style-patch-verification: ON
 480  *
 481  * Local Variables:
 482  * eval: (c-set-style "gnu")
 483  * End:
 484  */