src/vppinfra/bihash_template.c

   1 /*
   2  * Copyright (c) 2015 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 /** @cond DOCUMENTATION_IS_IN_BIHASH_DOC_H */
  17
  18 static inline void *BV (alloc_aligned) (BVT (clib_bihash) * h, uword nbytes)
  19 {
  20   uword rv;
  21
  22   /* Round to an even number of cache lines */
  23   nbytes += CLIB_CACHE_LINE_BYTES - 1;
  24   nbytes &= ~(CLIB_CACHE_LINE_BYTES - 1);
  25
  26   rv = alloc_arena_next (h);
  27   alloc_arena_next (h) += nbytes;
  28
  29   if (alloc_arena_next (h) > alloc_arena_size (h))
  30     os_out_of_memory ();
  31
  32   return (void *) (uword) (rv + alloc_arena (h));
  33 }
  34
  35 static void BV (clib_bihash_instantiate) (BVT (clib_bihash) * h)
  36 {
  37   uword bucket_size;
  38
  39   alloc_arena (h) = (uword) clib_mem_vm_alloc (h->memory_size);
  40   alloc_arena_next (h) = 0;
  41   alloc_arena_size (h) = h->memory_size;
  42
  43   bucket_size = h->nbuckets * sizeof (h->buckets[0]);
  44   h->buckets = BV (alloc_aligned) (h, bucket_size);
  45   CLIB_MEMORY_BARRIER ();
  46   h->instantiated = 1;
  47 }
  48
  49 void BV (clib_bihash_init2) (BVT (clib_bihash_init2_args) * a)
  50 {
  51   int i;
  52   void *oldheap;
  53   BVT (clib_bihash) * h = a->h;
  54
  55   a->nbuckets = 1 << (max_log2 (a->nbuckets));
  56
  57   h->name = (u8 *) a->name;
  58   h->nbuckets = a->nbuckets;
  59   h->log2_nbuckets = max_log2 (a->nbuckets);
  60   h->memory_size = a->memory_size;
  61   h->instantiated = 0;
  62   h->fmt_fn = a->fmt_fn;
  63
  64   alloc_arena (h) = 0;
  65
  66   /*
  67    * Make sure the requested size is rational. The max table
  68    * size without playing the alignment card is 64 Gbytes.
  69    * If someone starts complaining that's not enough, we can shift
  70    * the offset by CLIB_LOG2_CACHE_LINE_BYTES...
  71    */
  72   ASSERT (h->memory_size < (1ULL << BIHASH_BUCKET_OFFSET_BITS));
  73
  74   /* Add this hash table to the list */
  75   if (a->dont_add_to_all_bihash_list == 0)
  76     {
  77       for (i = 0; i < vec_len (clib_all_bihashes); i++)
  78         if (clib_all_bihashes[i] == h)
  79           goto do_lock;
  80       oldheap = clib_all_bihash_set_heap ();
  81       vec_add1 (clib_all_bihashes, (void *) h);
  82       clib_mem_set_heap (oldheap);
  83     }
  84
  85 do_lock:
  86   if (h->alloc_lock)
  87     clib_mem_free ((void *) h->alloc_lock);
  88
  89   /*
  90    * Set up the lock now, so we can use it to make the first add
  91    * thread-safe
  92    */
  93   h->alloc_lock = clib_mem_alloc_aligned (CLIB_CACHE_LINE_BYTES,
  94                                           CLIB_CACHE_LINE_BYTES);
  95   h->alloc_lock[0] = 0;
  96
  97   if (a->instantiate_immediately)
  98     BV (clib_bihash_instantiate) (h);
  99 }
 100
 101 void BV (clib_bihash_init)
 102   (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size)
 103 {
 104   BVT (clib_bihash_init2_args) _a, *a = &_a;
 105
 106   memset (a, 0, sizeof (*a));
 107
 108   a->h = h;
 109   a->name = name;
 110   a->nbuckets = nbuckets;
 111   a->memory_size = memory_size;
 112
 113   BV (clib_bihash_init2) (a);
 114 }
 115
 116 #if BIHASH_32_64_SVM
 117 #if !defined (MFD_ALLOW_SEALING)
 118 #define MFD_ALLOW_SEALING 0x0002U
 119 #endif
 120
 121 void BV (clib_bihash_master_init_svm)
 122   (BVT (clib_bihash) * h, char *name, u32 nbuckets, u64 memory_size)
 123 {
 124   uword bucket_size;
 125   u8 *mmap_addr;
 126   vec_header_t *freelist_vh;
 127   int fd;
 128
 129   ASSERT (memory_size < (1ULL << 32));
 130   /* Set up for memfd sharing */
 131   if ((fd = memfd_create (name, MFD_ALLOW_SEALING)) == -1)
 132     {
 133       clib_unix_warning ("memfd_create");
 134       return;
 135     }
 136
 137   if (ftruncate (fd, memory_size) < 0)
 138     {
 139       clib_unix_warning ("ftruncate");
 140       return;
 141     }
 142
 143   /* Not mission-critical, complain and continue */
 144   if ((fcntl (fd, F_ADD_SEALS, F_SEAL_SHRINK)) == -1)
 145     clib_unix_warning ("fcntl (F_ADD_SEALS)");
 146
 147   mmap_addr = mmap (0, memory_size,
 148                     PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0 /* offset */ );
 149
 150   if (mmap_addr == MAP_FAILED)
 151     {
 152       clib_unix_warning ("mmap failed");
 153       ASSERT (0);
 154     }
 155
 156   h->sh = (void *) mmap_addr;
 157   h->memfd = fd;
 158   nbuckets = 1 << (max_log2 (nbuckets));
 159
 160   h->name = (u8 *) name;
 161   h->sh->nbuckets = h->nbuckets = nbuckets;
 162   h->log2_nbuckets = max_log2 (nbuckets);
 163
 164   alloc_arena (h) = (u64) (uword) mmap_addr;
 165   alloc_arena_next (h) = CLIB_CACHE_LINE_BYTES;
 166   alloc_arena_size (h) = memory_size;
 167
 168   bucket_size = nbuckets * sizeof (h->buckets[0]);
 169   h->buckets = BV (alloc_aligned) (h, bucket_size);
 170   h->sh->buckets_as_u64 = (u64) BV (clib_bihash_get_offset) (h, h->buckets);
 171
 172   h->alloc_lock = BV (alloc_aligned) (h, CLIB_CACHE_LINE_BYTES);
 173   h->alloc_lock[0] = 0;
 174
 175   h->sh->alloc_lock_as_u64 =
 176     (u64) BV (clib_bihash_get_offset) (h, (void *) h->alloc_lock);
 177   freelist_vh =
 178     BV (alloc_aligned) (h,
 179                         sizeof (vec_header_t) +
 180                         BIHASH_FREELIST_LENGTH * sizeof (u64));
 181   freelist_vh->len = BIHASH_FREELIST_LENGTH;
 182   h->sh->freelists_as_u64 =
 183     (u64) BV (clib_bihash_get_offset) (h, freelist_vh->vector_data);
 184   h->freelists = (void *) (freelist_vh->vector_data);
 185
 186   h->fmt_fn = NULL;
 187   h->instantiated = 1;
 188 }
 189
 190 void BV (clib_bihash_slave_init_svm)
 191   (BVT (clib_bihash) * h, char *name, int fd)
 192 {
 193   u8 *mmap_addr;
 194   u64 memory_size;
 195   BVT (clib_bihash_shared_header) * sh;
 196
 197   /* Trial mapping, to learn the segment size */
 198   mmap_addr = mmap (0, 4096, PROT_READ, MAP_SHARED, fd, 0 /* offset */ );
 199   if (mmap_addr == MAP_FAILED)
 200     {
 201       clib_unix_warning ("trial mmap failed");
 202       ASSERT (0);
 203     }
 204
 205   sh = (BVT (clib_bihash_shared_header) *) mmap_addr;
 206
 207   memory_size = sh->alloc_arena_size;
 208
 209   munmap (mmap_addr, 4096);
 210
 211   /* Actual mapping, at the required size */
 212   mmap_addr = mmap (0, memory_size,
 213                     PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0 /* offset */ );
 214
 215   if (mmap_addr == MAP_FAILED)
 216     {
 217       clib_unix_warning ("mmap failed");
 218       ASSERT (0);
 219     }
 220
 221   (void) close (fd);
 222
 223   h->sh = (void *) mmap_addr;
 224   alloc_arena (h) = (u64) (uword) mmap_addr;
 225   h->memfd = -1;
 226
 227   h->name = (u8 *) name;
 228   h->buckets = BV (clib_bihash_get_value) (h, h->sh->buckets_as_u64);
 229   h->nbuckets = h->sh->nbuckets;
 230   h->log2_nbuckets = max_log2 (h->nbuckets);
 231
 232   h->alloc_lock = BV (clib_bihash_get_value) (h, h->sh->alloc_lock_as_u64);
 233   h->freelists = BV (clib_bihash_get_value) (h, h->sh->freelists_as_u64);
 234   h->fmt_fn = NULL;
 235 }
 236 #endif /* BIHASH_32_64_SVM */
 237
 238 void BV (clib_bihash_set_kvp_format_fn) (BVT (clib_bihash) * h,
 239                                          format_function_t * fmt_fn)
 240 {
 241   h->fmt_fn = fmt_fn;
 242 }
 243
 244 void BV (clib_bihash_free) (BVT (clib_bihash) * h)
 245 {
 246   int i;
 247
 248   if (PREDICT_FALSE (h->instantiated == 0))
 249     goto never_initialized;
 250
 251   h->instantiated = 0;
 252   vec_free (h->working_copies);
 253   vec_free (h->working_copy_lengths);
 254 #if BIHASH_32_64_SVM == 0
 255   vec_free (h->freelists);
 256 #else
 257   if (h->memfd > 0)
 258     (void) close (h->memfd);
 259 #endif
 260   clib_mem_vm_free ((void *) (uword) (alloc_arena (h)), alloc_arena_size (h));
 261 never_initialized:
 262   clib_memset (h, 0, sizeof (*h));
 263   for (i = 0; i < vec_len (clib_all_bihashes); i++)
 264     {
 265       if ((void *) h == clib_all_bihashes[i])
 266         {
 267           vec_delete (clib_all_bihashes, 1, i);
 268           return;
 269         }
 270     }
 271   clib_warning ("Couldn't find hash table %llx on clib_all_bihashes...",
 272                 (u64) (uword) h);
 273 }
 274
 275 static
 276 BVT (clib_bihash_value) *
 277 BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages)
 278 {
 279   BVT (clib_bihash_value) * rv = 0;
 280
 281   ASSERT (h->alloc_lock[0]);
 282
 283 #if BIHASH_32_64_SVM
 284   ASSERT (log2_pages < vec_len (h->freelists));
 285 #endif
 286
 287   if (log2_pages >= vec_len (h->freelists) || h->freelists[log2_pages] == 0)
 288     {
 289       vec_validate_init_empty (h->freelists, log2_pages, 0);
 290       rv = BV (alloc_aligned) (h, (sizeof (*rv) * (1 << log2_pages)));
 291       goto initialize;
 292     }
 293   rv = BV (clib_bihash_get_value) (h, (uword) h->freelists[log2_pages]);
 294   h->freelists[log2_pages] = rv->next_free_as_u64;
 295
 296 initialize:
 297   ASSERT (rv);
 298   /*
 299    * Latest gcc complains that the length arg is zero
 300    * if we replace (1<<log2_pages) with vec_len(rv).
 301    * No clue.
 302    */
 303   clib_memset (rv, 0xff, sizeof (*rv) * (1 << log2_pages));
 304   return rv;
 305 }
 306
 307 static void
 308 BV (value_free) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * v,
 309                  u32 log2_pages)
 310 {
 311   ASSERT (h->alloc_lock[0]);
 312
 313   ASSERT (vec_len (h->freelists) > log2_pages);
 314
 315   if (CLIB_DEBUG > 0)
 316     clib_memset (v, 0xFE, sizeof (*v) * (1 << log2_pages));
 317
 318   v->next_free_as_u64 = (u64) h->freelists[log2_pages];
 319   h->freelists[log2_pages] = (u64) BV (clib_bihash_get_offset) (h, v);
 320 }
 321
 322 static inline void
 323 BV (make_working_copy) (BVT (clib_bihash) * h, BVT (clib_bihash_bucket) * b)
 324 {
 325   BVT (clib_bihash_value) * v;
 326   BVT (clib_bihash_bucket) working_bucket __attribute__ ((aligned (8)));
 327   BVT (clib_bihash_value) * working_copy;
 328   u32 thread_index = os_get_thread_index ();
 329   int log2_working_copy_length;
 330
 331   ASSERT (h->alloc_lock[0]);
 332
 333   if (thread_index >= vec_len (h->working_copies))
 334     {
 335       vec_validate (h->working_copies, thread_index);
 336       vec_validate_init_empty (h->working_copy_lengths, thread_index, ~0);
 337     }
 338
 339   /*
 340    * working_copies are per-cpu so that near-simultaneous
 341    * updates from multiple threads will not result in sporadic, spurious
 342    * lookup failures.
 343    */
 344   working_copy = h->working_copies[thread_index];
 345   log2_working_copy_length = h->working_copy_lengths[thread_index];
 346
 347   h->saved_bucket.as_u64 = b->as_u64;
 348
 349   if (b->log2_pages > log2_working_copy_length)
 350     {
 351       /*
 352        * It's not worth the bookkeeping to free working copies
 353        *   if (working_copy)
 354        *     clib_mem_free (working_copy);
 355        */
 356       working_copy = BV (alloc_aligned)
 357         (h, sizeof (working_copy[0]) * (1 << b->log2_pages));
 358       h->working_copy_lengths[thread_index] = b->log2_pages;
 359       h->working_copies[thread_index] = working_copy;
 360
 361       BV (clib_bihash_increment_stat) (h, BIHASH_STAT_working_copy_lost,
 362                                        1ULL << b->log2_pages);
 363     }
 364
 365   v = BV (clib_bihash_get_value) (h, b->offset);
 366
 367   clib_memcpy_fast (working_copy, v, sizeof (*v) * (1 << b->log2_pages));
 368   working_bucket.as_u64 = b->as_u64;
 369   working_bucket.offset = BV (clib_bihash_get_offset) (h, working_copy);
 370   CLIB_MEMORY_BARRIER ();
 371   b->as_u64 = working_bucket.as_u64;
 372   h->working_copies[thread_index] = working_copy;
 373 }
 374
 375 static
 376 BVT (clib_bihash_value) *
 377 BV (split_and_rehash)
 378   (BVT (clib_bihash) * h,
 379    BVT (clib_bihash_value) * old_values, u32 old_log2_pages,
 380    u32 new_log2_pages)
 381 {
 382   BVT (clib_bihash_value) * new_values, *new_v;
 383   int i, j, length_in_kvs;
 384
 385   ASSERT (h->alloc_lock[0]);
 386
 387   new_values = BV (value_alloc) (h, new_log2_pages);
 388   length_in_kvs = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE;
 389
 390   for (i = 0; i < length_in_kvs; i++)
 391     {
 392       u64 new_hash;
 393
 394       /* Entry not in use? Forget it */
 395       if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
 396         continue;
 397
 398       /* rehash the item onto its new home-page */
 399       new_hash = BV (clib_bihash_hash) (&(old_values->kvp[i]));
 400       new_hash >>= h->log2_nbuckets;
 401       new_hash &= (1 << new_log2_pages) - 1;
 402       new_v = &new_values[new_hash];
 403
 404       /* Across the new home-page */
 405       for (j = 0; j < BIHASH_KVP_PER_PAGE; j++)
 406         {
 407           /* Empty slot */
 408           if (BV (clib_bihash_is_free) (&(new_v->kvp[j])))
 409             {
 410               clib_memcpy_fast (&(new_v->kvp[j]), &(old_values->kvp[i]),
 411                                 sizeof (new_v->kvp[j]));
 412               goto doublebreak;
 413             }
 414         }
 415       /* Crap. Tell caller to try again */
 416       BV (value_free) (h, new_values, new_log2_pages);
 417       return 0;
 418     doublebreak:;
 419     }
 420
 421   return new_values;
 422 }
 423
 424 static
 425 BVT (clib_bihash_value) *
 426 BV (split_and_rehash_linear)
 427   (BVT (clib_bihash) * h,
 428    BVT (clib_bihash_value) * old_values, u32 old_log2_pages,
 429    u32 new_log2_pages)
 430 {
 431   BVT (clib_bihash_value) * new_values;
 432   int i, j, new_length, old_length;
 433
 434   ASSERT (h->alloc_lock[0]);
 435
 436   new_values = BV (value_alloc) (h, new_log2_pages);
 437   new_length = (1 << new_log2_pages) * BIHASH_KVP_PER_PAGE;
 438   old_length = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE;
 439
 440   j = 0;
 441   /* Across the old value array */
 442   for (i = 0; i < old_length; i++)
 443     {
 444       /* Find a free slot in the new linear scan bucket */
 445       for (; j < new_length; j++)
 446         {
 447           /* Old value not in use? Forget it. */
 448           if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
 449             goto doublebreak;
 450
 451           /* New value should never be in use */
 452           if (BV (clib_bihash_is_free) (&(new_values->kvp[j])))
 453             {
 454               /* Copy the old value and move along */
 455               clib_memcpy_fast (&(new_values->kvp[j]), &(old_values->kvp[i]),
 456                                 sizeof (new_values->kvp[j]));
 457               j++;
 458               goto doublebreak;
 459             }
 460         }
 461       /* This should never happen... */
 462       clib_warning ("BUG: linear rehash failed!");
 463       BV (value_free) (h, new_values, new_log2_pages);
 464       return 0;
 465
 466     doublebreak:;
 467     }
 468   return new_values;
 469 }
 470
 471 static inline int BV (clib_bihash_add_del_inline)
 472   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add,
 473    int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg)
 474 {
 475   BVT (clib_bihash_bucket) * b, tmp_b;
 476   BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy;
 477   int i, limit;
 478   u64 hash, new_hash;
 479   u32 new_log2_pages, old_log2_pages;
 480   u32 thread_index = os_get_thread_index ();
 481   int mark_bucket_linear;
 482   int resplit_once;
 483
 484   /*
 485    * Create the table (is_add=1,2), or flunk the request now (is_add=0)
 486    * Use the alloc_lock to protect the instantiate operation.
 487    */
 488   if (PREDICT_FALSE (h->instantiated == 0))
 489     {
 490       if (is_add == 0)
 491         return (-1);
 492
 493       BV (clib_bihash_alloc_lock) (h);
 494       if (h->instantiated == 0)
 495         BV (clib_bihash_instantiate) (h);
 496       BV (clib_bihash_alloc_unlock) (h);
 497     }
 498
 499   hash = BV (clib_bihash_hash) (add_v);
 500
 501   b = BV (clib_bihash_get_bucket) (h, hash);
 502
 503   hash >>= h->log2_nbuckets;
 504
 505   BV (clib_bihash_lock_bucket) (b);
 506
 507   /* First elt in the bucket? */
 508   if (BV (clib_bihash_bucket_is_empty) (b))
 509     {
 510       if (is_add == 0)
 511         {
 512           BV (clib_bihash_unlock_bucket) (b);
 513           return (-1);
 514         }
 515
 516       BV (clib_bihash_alloc_lock) (h);
 517       v = BV (value_alloc) (h, 0);
 518       BV (clib_bihash_alloc_unlock) (h);
 519
 520       *v->kvp = *add_v;
 521       tmp_b.as_u64 = 0;         /* clears bucket lock */
 522       tmp_b.offset = BV (clib_bihash_get_offset) (h, v);
 523       tmp_b.refcnt = 1;
 524       CLIB_MEMORY_BARRIER ();
 525
 526       b->as_u64 = tmp_b.as_u64; /* unlocks the bucket */
 527       BV (clib_bihash_increment_stat) (h, BIHASH_STAT_alloc_add, 1);
 528
 529       return (0);
 530     }
 531
 532   /* WARNING: we're still looking at the live copy... */
 533   limit = BIHASH_KVP_PER_PAGE;
 534   v = BV (clib_bihash_get_value) (h, b->offset);
 535
 536   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 537   if (b->linear_search)
 538     limit <<= b->log2_pages;
 539
 540   if (is_add)
 541     {
 542       /*
 543        * Because reader threads are looking at live data,
 544        * we have to be extra careful. Readers do NOT hold the
 545        * bucket lock. We need to be SLOWER than a search, past the
 546        * point where readers CHECK the bucket lock.
 547        */
 548
 549       /*
 550        * For obvious (in hindsight) reasons, see if we're supposed to
 551        * replace an existing key, then look for an empty slot.
 552        */
 553       for (i = 0; i < limit; i++)
 554         {
 555           if (BV (clib_bihash_key_compare) (v->kvp[i].key, add_v->key))
 556             {
 557               /* Add but do not overwrite? */
 558               if (is_add == 2)
 559                 {
 560                   BV (clib_bihash_unlock_bucket) (b);
 561                   return (-2);
 562                 }
 563
 564               CLIB_MEMORY_BARRIER ();   /* Add a delay */
 565               clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v));
 566               BV (clib_bihash_unlock_bucket) (b);
 567               BV (clib_bihash_increment_stat) (h, BIHASH_STAT_replace, 1);
 568               return (0);
 569             }
 570         }
 571       /*
 572        * Look for an empty slot. If found, use it
 573        */
 574       for (i = 0; i < limit; i++)
 575         {
 576           if (BV (clib_bihash_is_free) (&(v->kvp[i])))
 577             {
 578               /*
 579                * Copy the value first, so that if a reader manages
 580                * to match the new key, the value will be right...
 581                */
 582               clib_memcpy_fast (&(v->kvp[i].value),
 583                                 &add_v->value, sizeof (add_v->value));
 584               CLIB_MEMORY_BARRIER ();   /* Make sure the value has settled */
 585               clib_memcpy_fast (&(v->kvp[i]), &add_v->key,
 586                                 sizeof (add_v->key));
 587               b->refcnt++;
 588               ASSERT (b->refcnt > 0);
 589               BV (clib_bihash_unlock_bucket) (b);
 590               BV (clib_bihash_increment_stat) (h, BIHASH_STAT_add, 1);
 591               return (0);
 592             }
 593         }
 594       /* look for stale data to overwrite */
 595       if (is_stale_cb)
 596         {
 597           for (i = 0; i < limit; i++)
 598             {
 599               if (is_stale_cb (&(v->kvp[i]), arg))
 600                 {
 601                   CLIB_MEMORY_BARRIER ();
 602                   clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v));
 603                   BV (clib_bihash_unlock_bucket) (b);
 604                   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_replace, 1);
 605                   return (0);
 606                 }
 607             }
 608         }
 609       /* Out of space in this bucket, split the bucket... */
 610     }
 611   else                          /* delete case */
 612     {
 613       for (i = 0; i < limit; i++)
 614         {
 615           /* Found the key? Kill it... */
 616           if (BV (clib_bihash_key_compare) (v->kvp[i].key, add_v->key))
 617             {
 618               clib_memset (&(v->kvp[i]), 0xff, sizeof (*(add_v)));
 619               /* Is the bucket empty? */
 620               if (PREDICT_TRUE (b->refcnt > 1))
 621                 {
 622                   b->refcnt--;
 623                   BV (clib_bihash_unlock_bucket) (b);
 624                   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del, 1);
 625                   return (0);
 626                 }
 627               else              /* yes, free it */
 628                 {
 629                   /* Save old bucket value, need log2_pages to free it */
 630                   tmp_b.as_u64 = b->as_u64;
 631                   CLIB_MEMORY_BARRIER ();
 632
 633                   /* Kill and unlock the bucket */
 634                   b->as_u64 = 0;
 635
 636                   /* And free the backing storage */
 637                   BV (clib_bihash_alloc_lock) (h);
 638                   /* Note: v currently points into the middle of the bucket */
 639                   v = BV (clib_bihash_get_value) (h, tmp_b.offset);
 640                   BV (value_free) (h, v, tmp_b.log2_pages);
 641                   BV (clib_bihash_alloc_unlock) (h);
 642                   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del_free,
 643                                                    1);
 644                   return (0);
 645                 }
 646             }
 647         }
 648       /* Not found... */
 649       BV (clib_bihash_unlock_bucket) (b);
 650       return (-3);
 651     }
 652
 653   /* Move readers to a (locked) temp copy of the bucket */
 654   BV (clib_bihash_alloc_lock) (h);
 655   BV (make_working_copy) (h, b);
 656
 657   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
 658
 659   old_log2_pages = h->saved_bucket.log2_pages;
 660   new_log2_pages = old_log2_pages + 1;
 661   mark_bucket_linear = 0;
 662   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_split_add, 1);
 663   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits, old_log2_pages);
 664
 665   working_copy = h->working_copies[thread_index];
 666   resplit_once = 0;
 667   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits, 1);
 668
 669   new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
 670                                  new_log2_pages);
 671   if (new_v == 0)
 672     {
 673     try_resplit:
 674       resplit_once = 1;
 675       new_log2_pages++;
 676       /* Try re-splitting. If that fails, fall back to linear search */
 677       new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
 678                                      new_log2_pages);
 679       if (new_v == 0)
 680         {
 681         mark_linear:
 682           new_log2_pages--;
 683           /* pinned collisions, use linear search */
 684           new_v =
 685             BV (split_and_rehash_linear) (h, working_copy, old_log2_pages,
 686                                           new_log2_pages);
 687           mark_bucket_linear = 1;
 688           BV (clib_bihash_increment_stat) (h, BIHASH_STAT_linear, 1);
 689         }
 690       BV (clib_bihash_increment_stat) (h, BIHASH_STAT_resplit, 1);
 691       BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits,
 692                                        old_log2_pages + 1);
 693     }
 694
 695   /* Try to add the new entry */
 696   save_new_v = new_v;
 697   new_hash = BV (clib_bihash_hash) (add_v);
 698   limit = BIHASH_KVP_PER_PAGE;
 699   if (mark_bucket_linear)
 700     limit <<= new_log2_pages;
 701   new_hash >>= h->log2_nbuckets;
 702   new_hash &= (1 << new_log2_pages) - 1;
 703   new_v += mark_bucket_linear ? 0 : new_hash;
 704
 705   for (i = 0; i < limit; i++)
 706     {
 707       if (BV (clib_bihash_is_free) (&(new_v->kvp[i])))
 708         {
 709           clib_memcpy_fast (&(new_v->kvp[i]), add_v, sizeof (*add_v));
 710           goto expand_ok;
 711         }
 712     }
 713
 714   /* Crap. Try again */
 715   BV (value_free) (h, save_new_v, new_log2_pages);
 716   /*
 717    * If we've already doubled the size of the bucket once,
 718    * fall back to linear search now.
 719    */
 720   if (resplit_once)
 721     goto mark_linear;
 722   else
 723     goto try_resplit;
 724
 725 expand_ok:
 726   tmp_b.log2_pages = new_log2_pages;
 727   tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
 728   tmp_b.linear_search = mark_bucket_linear;
 729   tmp_b.refcnt = h->saved_bucket.refcnt + 1;
 730   ASSERT (tmp_b.refcnt > 0);
 731   tmp_b.lock = 0;
 732   CLIB_MEMORY_BARRIER ();
 733   b->as_u64 = tmp_b.as_u64;
 734   /* free the old bucket */
 735   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
 736   BV (value_free) (h, v, h->saved_bucket.log2_pages);
 737   BV (clib_bihash_alloc_unlock) (h);
 738   return (0);
 739 }
 740
 741 int BV (clib_bihash_add_del)
 742   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
 743 {
 744   return BV (clib_bihash_add_del_inline) (h, add_v, is_add, 0, 0);
 745 }
 746
 747 int BV (clib_bihash_add_or_overwrite_stale)
 748   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
 749    int (*stale_callback) (BVT (clib_bihash_kv) *, void *), void *arg)
 750 {
 751   return BV (clib_bihash_add_del_inline) (h, add_v, 1, stale_callback, arg);
 752 }
 753
 754 int BV (clib_bihash_search)
 755   (BVT (clib_bihash) * h,
 756    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
 757 {
 758   u64 hash;
 759   BVT (clib_bihash_value) * v;
 760   BVT (clib_bihash_bucket) * b;
 761   int i, limit;
 762
 763   ASSERT (valuep);
 764
 765   if (PREDICT_FALSE (alloc_arena (h) == 0))
 766     return -1;
 767
 768   hash = BV (clib_bihash_hash) (search_key);
 769
 770   b = BV (clib_bihash_get_bucket) (h, hash);
 771
 772   if (BV (clib_bihash_bucket_is_empty) (b))
 773     return -1;
 774
 775   if (PREDICT_FALSE (b->lock))
 776     {
 777       volatile BVT (clib_bihash_bucket) * bv = b;
 778       while (bv->lock)
 779         CLIB_PAUSE ();
 780     }
 781
 782   hash >>= h->log2_nbuckets;
 783
 784   v = BV (clib_bihash_get_value) (h, b->offset);
 785   limit = BIHASH_KVP_PER_PAGE;
 786   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 787   if (PREDICT_FALSE (b->linear_search))
 788     limit <<= b->log2_pages;
 789
 790   for (i = 0; i < limit; i++)
 791     {
 792       if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
 793         {
 794           *valuep = v->kvp[i];
 795           return 0;
 796         }
 797     }
 798   return -1;
 799 }
 800
 801 u8 *BV (format_bihash) (u8 * s, va_list * args)
 802 {
 803   BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *);
 804   int verbose = va_arg (*args, int);
 805   BVT (clib_bihash_bucket) * b;
 806   BVT (clib_bihash_value) * v;
 807   int i, j, k;
 808   u64 active_elements = 0;
 809   u64 active_buckets = 0;
 810   u64 linear_buckets = 0;
 811   u64 used_bytes;
 812
 813   s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)");
 814
 815   if (PREDICT_FALSE (alloc_arena (h) == 0))
 816     return format (s, "[empty, uninitialized]");
 817
 818   for (i = 0; i < h->nbuckets; i++)
 819     {
 820       b = &h->buckets[i];
 821       if (BV (clib_bihash_bucket_is_empty) (b))
 822         {
 823           if (verbose > 1)
 824             s = format (s, "[%d]: empty\n", i);
 825           continue;
 826         }
 827
 828       active_buckets++;
 829
 830       if (b->linear_search)
 831         linear_buckets++;
 832
 833       if (verbose)
 834         {
 835           s = format (s, "[%d]: heap offset %lld, len %d, linear %d\n", i,
 836                       b->offset, (1 << b->log2_pages), b->linear_search);
 837         }
 838
 839       v = BV (clib_bihash_get_value) (h, b->offset);
 840       for (j = 0; j < (1 << b->log2_pages); j++)
 841         {
 842           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
 843             {
 844               if (BV (clib_bihash_is_free) (&v->kvp[k]))
 845                 {
 846                   if (verbose > 1)
 847                     s = format (s, "    %d: empty\n",
 848                                 j * BIHASH_KVP_PER_PAGE + k);
 849                   continue;
 850                 }
 851               if (verbose)
 852                 {
 853                   if (h->fmt_fn)
 854                     {
 855                       s = format (s, "    %d: %U\n",
 856                                   j * BIHASH_KVP_PER_PAGE + k,
 857                                   h->fmt_fn, &(v->kvp[k]), verbose);
 858                     }
 859                   else
 860                     {
 861                       s = format (s, "    %d: %U\n",
 862                                   j * BIHASH_KVP_PER_PAGE + k,
 863                                   BV (format_bihash_kvp), &(v->kvp[k]));
 864                     }
 865                 }
 866               active_elements++;
 867             }
 868           v++;
 869         }
 870     }
 871
 872   s = format (s, "    %lld active elements %lld active buckets\n",
 873               active_elements, active_buckets);
 874   s = format (s, "    %d free lists\n", vec_len (h->freelists));
 875
 876   for (i = 0; i < vec_len (h->freelists); i++)
 877     {
 878       u32 nfree = 0;
 879       BVT (clib_bihash_value) * free_elt;
 880       u64 free_elt_as_u64 = h->freelists[i];
 881
 882       while (free_elt_as_u64)
 883         {
 884           free_elt = BV (clib_bihash_get_value) (h, free_elt_as_u64);
 885           nfree++;
 886           free_elt_as_u64 = free_elt->next_free_as_u64;
 887         }
 888
 889       if (nfree || verbose)
 890         s = format (s, "       [len %d] %u free elts\n", 1 << i, nfree);
 891     }
 892
 893   s = format (s, "    %lld linear search buckets\n", linear_buckets);
 894   used_bytes = alloc_arena_next (h);
 895   s = format (s,
 896               "    arena: base %llx, next %llx\n"
 897               "           used %lld b (%lld Mbytes) of %lld b (%lld Mbytes)\n",
 898               alloc_arena (h), alloc_arena_next (h),
 899               used_bytes, used_bytes >> 20,
 900               alloc_arena_size (h), alloc_arena_size (h) >> 20);
 901   return s;
 902 }
 903
 904 void BV (clib_bihash_foreach_key_value_pair)
 905   (BVT (clib_bihash) * h,
 906    BV (clib_bihash_foreach_key_value_pair_cb) cb, void *arg)
 907 {
 908   int i, j, k;
 909   BVT (clib_bihash_bucket) * b;
 910   BVT (clib_bihash_value) * v;
 911
 912   if (PREDICT_FALSE (alloc_arena (h) == 0))
 913     return;
 914
 915   for (i = 0; i < h->nbuckets; i++)
 916     {
 917       b = &h->buckets[i];
 918       if (BV (clib_bihash_bucket_is_empty) (b))
 919         continue;
 920
 921       v = BV (clib_bihash_get_value) (h, b->offset);
 922       for (j = 0; j < (1 << b->log2_pages); j++)
 923         {
 924           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
 925             {
 926               if (BV (clib_bihash_is_free) (&v->kvp[k]))
 927                 continue;
 928
 929               if (BIHASH_WALK_STOP == cb (&v->kvp[k], arg))
 930                 return;
 931               /*
 932                * In case the callback deletes the last entry in the bucket...
 933                */
 934               if (BV (clib_bihash_bucket_is_empty) (b))
 935                 goto doublebreak;
 936             }
 937           v++;
 938         }
 939     doublebreak:
 940       ;
 941     }
 942 }
 943
 944 /** @endcond */
 945
 946 /*
 947  * fd.io coding-style-patch-verification: ON
 948  *
 949  * Local Variables:
 950  * eval: (c-set-style "gnu")
 951  * End:
 952  */