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 #ifndef MAP_HUGE_SHIFT
  19 #define MAP_HUGE_SHIFT 26
  20 #endif
  21
  22 #ifndef BIIHASH_MIN_ALLOC_LOG2_PAGES
  23 #define BIIHASH_MIN_ALLOC_LOG2_PAGES 10
  24 #endif
  25
  26 #ifndef BIHASH_USE_HEAP
  27 #define BIHASH_USE_HEAP 1
  28 #endif
  29
  30 static inline void *BV (alloc_aligned) (BVT (clib_bihash) * h, uword nbytes)
  31 {
  32   uword rv;
  33
  34   /* Round to an even number of cache lines */
  35   nbytes = round_pow2 (nbytes, CLIB_CACHE_LINE_BYTES);
  36
  37   if (BIHASH_USE_HEAP)
  38     {
  39       void *rv, *oldheap;
  40       uword page_sz = sizeof (BVT (clib_bihash_value));
  41       uword chunk_sz = round_pow2 (page_sz << BIIHASH_MIN_ALLOC_LOG2_PAGES,
  42                                    CLIB_CACHE_LINE_BYTES);
  43
  44       BVT (clib_bihash_alloc_chunk) * chunk = h->chunks;
  45
  46       /* if there is enough space in the currenrt chunk */
  47       if (chunk && chunk->bytes_left >= nbytes)
  48         {
  49           rv = chunk->next_alloc;
  50           chunk->bytes_left -= nbytes;
  51           chunk->next_alloc += nbytes;
  52           return rv;
  53         }
  54
  55       /* requested allocation is bigger than chunk size */
  56       if (nbytes >= chunk_sz)
  57         {
  58           oldheap = clib_mem_set_heap (h->heap);
  59           chunk = clib_mem_alloc_aligned (nbytes + sizeof (*chunk),
  60                                           CLIB_CACHE_LINE_BYTES);
  61           clib_mem_set_heap (oldheap);
  62           clib_memset_u8 (chunk, 0, sizeof (*chunk));
  63           chunk->size = nbytes;
  64           rv = (u8 *) (chunk + 1);
  65           if (h->chunks)
  66             {
  67               /* take 2nd place in the list */
  68               chunk->next = h->chunks->next;
  69               chunk->prev = h->chunks;
  70               h->chunks->next = chunk;
  71               if (chunk->next)
  72                 chunk->next->prev = chunk;
  73             }
  74           else
  75             h->chunks = chunk;
  76
  77           return rv;
  78         }
  79
  80       oldheap = clib_mem_set_heap (h->heap);
  81       chunk = clib_mem_alloc_aligned (chunk_sz + sizeof (*chunk),
  82                                       CLIB_CACHE_LINE_BYTES);
  83       clib_mem_set_heap (oldheap);
  84       chunk->size = chunk_sz;
  85       chunk->bytes_left = chunk_sz;
  86       chunk->next_alloc = (u8 *) (chunk + 1);
  87       chunk->next = h->chunks;
  88       chunk->prev = 0;
  89       if (chunk->next)
  90         chunk->next->prev = chunk;
  91       h->chunks = chunk;
  92       rv = chunk->next_alloc;
  93       chunk->bytes_left -= nbytes;
  94       chunk->next_alloc += nbytes;
  95       return rv;
  96     }
  97
  98   rv = alloc_arena_next (h);
  99   alloc_arena_next (h) += nbytes;
 100
 101   if (alloc_arena_next (h) > alloc_arena_size (h))
 102     os_out_of_memory ();
 103
 104   if (alloc_arena_next (h) > alloc_arena_mapped (h))
 105     {
 106       void *base, *rv;
 107       uword alloc = alloc_arena_next (h) - alloc_arena_mapped (h);
 108       int mmap_flags = MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS;
 109       int mmap_flags_huge = (mmap_flags | MAP_HUGETLB | MAP_LOCKED |
 110                              BIHASH_LOG2_HUGEPAGE_SIZE << MAP_HUGE_SHIFT);
 111
 112       /* new allocation is 25% of existing one */
 113       if (alloc_arena_mapped (h) >> 2 > alloc)
 114         alloc = alloc_arena_mapped (h) >> 2;
 115
 116       /* round allocation to page size */
 117       alloc = round_pow2 (alloc, 1 << BIHASH_LOG2_HUGEPAGE_SIZE);
 118
 119       base = (void *) (uword) (alloc_arena (h) + alloc_arena_mapped (h));
 120
 121       rv = mmap (base, alloc, PROT_READ | PROT_WRITE, mmap_flags_huge, -1, 0);
 122
 123       /* fallback - maybe we are still able to allocate normal pages */
 124       if (rv == MAP_FAILED || mlock (base, alloc) != 0)
 125         rv = mmap (base, alloc, PROT_READ | PROT_WRITE, mmap_flags, -1, 0);
 126
 127       if (rv == MAP_FAILED)
 128         os_out_of_memory ();
 129
 130       alloc_arena_mapped (h) += alloc;
 131     }
 132
 133   return (void *) (uword) (rv + alloc_arena (h));
 134 }
 135
 136 static void BV (clib_bihash_instantiate) (BVT (clib_bihash) * h)
 137 {
 138   uword bucket_size;
 139
 140   if (BIHASH_USE_HEAP)
 141     {
 142       h->heap = clib_mem_get_heap ();
 143       h->chunks = 0;
 144       alloc_arena (h) = (uword) clib_mem_get_heap_base (h->heap);
 145     }
 146   else
 147     {
 148       alloc_arena (h) = clib_mem_vm_reserve (0, h->memory_size,
 149                                              BIHASH_LOG2_HUGEPAGE_SIZE);
 150       if (alloc_arena (h) == ~0)
 151         os_out_of_memory ();
 152       alloc_arena_next (h) = 0;
 153       alloc_arena_size (h) = h->memory_size;
 154       alloc_arena_mapped (h) = 0;
 155     }
 156
 157   bucket_size = h->nbuckets * sizeof (h->buckets[0]);
 158
 159   if (BIHASH_KVP_AT_BUCKET_LEVEL)
 160     bucket_size +=
 161       h->nbuckets * BIHASH_KVP_PER_PAGE * sizeof (BVT (clib_bihash_kv));
 162
 163   h->buckets = BV (alloc_aligned) (h, bucket_size);
 164   clib_memset_u8 (h->buckets, 0, bucket_size);
 165
 166   if (BIHASH_KVP_AT_BUCKET_LEVEL)
 167     {
 168       int i, j;
 169       BVT (clib_bihash_bucket) * b;
 170
 171       b = h->buckets;
 172
 173       for (i = 0; i < h->nbuckets; i++)
 174         {
 175           BVT (clib_bihash_kv) * v;
 176           b->offset = BV (clib_bihash_get_offset) (h, (void *) (b + 1));
 177           b->refcnt = 1;
 178           /* Mark all elements free */
 179           v = (void *) (b + 1);
 180           for (j = 0; j < BIHASH_KVP_PER_PAGE; j++)
 181             {
 182               BV (clib_bihash_mark_free) (v);
 183               v++;
 184             }
 185           /* Compute next bucket start address */
 186           b = (void *) (((uword) b) + sizeof (*b) +
 187                         (BIHASH_KVP_PER_PAGE *
 188                          sizeof (BVT (clib_bihash_kv))));
 189         }
 190     }
 191   CLIB_MEMORY_STORE_BARRIER ();
 192   h->instantiated = 1;
 193 }
 194
 195 void BV (clib_bihash_init2) (BVT (clib_bihash_init2_args) * a)
 196 {
 197   int i;
 198   void *oldheap;
 199   BVT (clib_bihash) * h = a->h;
 200
 201   a->nbuckets = 1 << (max_log2 (a->nbuckets));
 202
 203   h->name = (u8 *) a->name;
 204   h->nbuckets = a->nbuckets;
 205   h->log2_nbuckets = max_log2 (a->nbuckets);
 206   h->memory_size = BIHASH_USE_HEAP ? 0 : a->memory_size;
 207   h->instantiated = 0;
 208   h->dont_add_to_all_bihash_list = a->dont_add_to_all_bihash_list;
 209   h->fmt_fn = BV (format_bihash);
 210   h->kvp_fmt_fn = a->kvp_fmt_fn;
 211
 212   alloc_arena (h) = 0;
 213
 214   /*
 215    * Make sure the requested size is rational. The max table
 216    * size without playing the alignment card is 64 Gbytes.
 217    * If someone starts complaining that's not enough, we can shift
 218    * the offset by CLIB_LOG2_CACHE_LINE_BYTES...
 219    */
 220   if (BIHASH_USE_HEAP)
 221     ASSERT (h->memory_size < (1ULL << BIHASH_BUCKET_OFFSET_BITS));
 222
 223   /* Add this hash table to the list */
 224   if (a->dont_add_to_all_bihash_list == 0)
 225     {
 226       for (i = 0; i < vec_len (clib_all_bihashes); i++)
 227         if (clib_all_bihashes[i] == h)
 228           goto do_lock;
 229       oldheap = clib_all_bihash_set_heap ();
 230       vec_add1 (clib_all_bihashes, (void *) h);
 231       clib_mem_set_heap (oldheap);
 232     }
 233
 234 do_lock:
 235   if (h->alloc_lock)
 236     clib_mem_free ((void *) h->alloc_lock);
 237
 238   /*
 239    * Set up the lock now, so we can use it to make the first add
 240    * thread-safe
 241    */
 242   h->alloc_lock = clib_mem_alloc_aligned (CLIB_CACHE_LINE_BYTES,
 243                                           CLIB_CACHE_LINE_BYTES);
 244   h->alloc_lock[0] = 0;
 245
 246 #if BIHASH_LAZY_INSTANTIATE
 247   if (a->instantiate_immediately)
 248 #endif
 249     BV (clib_bihash_instantiate) (h);
 250 }
 251
 252 void BV (clib_bihash_init)
 253   (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size)
 254 {
 255   BVT (clib_bihash_init2_args) _a, *a = &_a;
 256
 257   memset (a, 0, sizeof (*a));
 258
 259   a->h = h;
 260   a->name = name;
 261   a->nbuckets = nbuckets;
 262   a->memory_size = memory_size;
 263
 264   BV (clib_bihash_init2) (a);
 265 }
 266
 267 #if BIHASH_32_64_SVM
 268 #if !defined (MFD_ALLOW_SEALING)
 269 #define MFD_ALLOW_SEALING 0x0002U
 270 #endif
 271
 272 void BV (clib_bihash_initiator_init_svm)
 273   (BVT (clib_bihash) * h, char *name, u32 nbuckets, u64 memory_size)
 274 {
 275   uword bucket_size;
 276   u8 *mmap_addr;
 277   vec_header_t *freelist_vh;
 278   int fd;
 279
 280   ASSERT (BIHASH_USE_HEAP == 0);
 281
 282   ASSERT (memory_size < (1ULL << 32));
 283   /* Set up for memfd sharing */
 284   if ((fd = clib_mem_vm_create_fd (CLIB_MEM_PAGE_SZ_DEFAULT, name) == -1)
 285     {
 286       clib_unix_warning ("memfd_create");
 287       return;
 288     }
 289
 290   if (ftruncate (fd, memory_size) < 0)
 291     {
 292       clib_unix_warning ("ftruncate");
 293       return;
 294     }
 295
 296   /* Not mission-critical, complain and continue */
 297   if ((fcntl (fd, F_ADD_SEALS, F_SEAL_SHRINK)) == -1)
 298     clib_unix_warning ("fcntl (F_ADD_SEALS)");
 299
 300   mmap_addr = mmap (0, memory_size,
 301                     PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0 /* offset */ );
 302
 303   if (mmap_addr == MAP_FAILED)
 304     {
 305       clib_unix_warning ("mmap failed");
 306       ASSERT (0);
 307     }
 308
 309   h->sh = (void *) mmap_addr;
 310   h->memfd = fd;
 311   nbuckets = 1 << (max_log2 (nbuckets));
 312
 313   h->name = (u8 *) name;
 314   h->sh->nbuckets = h->nbuckets = nbuckets;
 315   h->log2_nbuckets = max_log2 (nbuckets);
 316
 317   alloc_arena (h) = (u64) (uword) mmap_addr;
 318   alloc_arena_next (h) = CLIB_CACHE_LINE_BYTES;
 319   alloc_arena_size (h) = memory_size;
 320
 321   bucket_size = nbuckets * sizeof (h->buckets[0]);
 322   h->buckets = BV (alloc_aligned) (h, bucket_size);
 323   clib_memset_u8 (h->buckets, 0, bucket_size);
 324   h->sh->buckets_as_u64 = (u64) BV (clib_bihash_get_offset) (h, h->buckets);
 325
 326   h->alloc_lock = BV (alloc_aligned) (h, CLIB_CACHE_LINE_BYTES);
 327   h->alloc_lock[0] = 0;
 328
 329   h->sh->alloc_lock_as_u64 =
 330     (u64) BV (clib_bihash_get_offset) (h, (void *) h->alloc_lock);
 331   freelist_vh =
 332     BV (alloc_aligned) (h,
 333                         sizeof (vec_header_t) +
 334                         BIHASH_FREELIST_LENGTH * sizeof (u64));
 335   freelist_vh->len = BIHASH_FREELIST_LENGTH;
 336   h->sh->freelists_as_u64 =
 337     (u64) BV (clib_bihash_get_offset) (h, freelist_vh->vector_data);
 338   h->freelists = (void *) (freelist_vh->vector_data);
 339
 340   h->fmt_fn = BV (format_bihash);
 341   h->kvp_fmt_fn = NULL;
 342   h->instantiated = 1;
 343 }
 344
 345 void BV (clib_bihash_responder_init_svm)
 346   (BVT (clib_bihash) * h, char *name, int fd)
 347 {
 348   u8 *mmap_addr;
 349   u64 memory_size;
 350   BVT (clib_bihash_shared_header) * sh;
 351
 352   ASSERT (BIHASH_USE_HEAP == 0);
 353
 354   /* Trial mapping, to learn the segment size */
 355   mmap_addr = mmap (0, 4096, PROT_READ, MAP_SHARED, fd, 0 /* offset */ );
 356   if (mmap_addr == MAP_FAILED)
 357     {
 358       clib_unix_warning ("trial mmap failed");
 359       ASSERT (0);
 360     }
 361
 362   sh = (BVT (clib_bihash_shared_header) *) mmap_addr;
 363
 364   memory_size = sh->alloc_arena_size;
 365
 366   munmap (mmap_addr, 4096);
 367
 368   /* Actual mapping, at the required size */
 369   mmap_addr = mmap (0, memory_size,
 370                     PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0 /* offset */ );
 371
 372   if (mmap_addr == MAP_FAILED)
 373     {
 374       clib_unix_warning ("mmap failed");
 375       ASSERT (0);
 376     }
 377
 378   (void) close (fd);
 379
 380   h->sh = (void *) mmap_addr;
 381   alloc_arena (h) = (u64) (uword) mmap_addr;
 382   h->memfd = -1;
 383
 384   h->name = (u8 *) name;
 385   h->buckets = BV (clib_bihash_get_value) (h, h->sh->buckets_as_u64);
 386   h->nbuckets = h->sh->nbuckets;
 387   h->log2_nbuckets = max_log2 (h->nbuckets);
 388
 389   h->alloc_lock = BV (clib_bihash_get_value) (h, h->sh->alloc_lock_as_u64);
 390   h->freelists = BV (clib_bihash_get_value) (h, h->sh->freelists_as_u64);
 391   h->fmt_fn = BV (format_bihash);
 392   h->kvp_fmt_fn = NULL;
 393 }
 394 #endif /* BIHASH_32_64_SVM */
 395
 396 void BV (clib_bihash_set_kvp_format_fn) (BVT (clib_bihash) * h,
 397                                          format_function_t * kvp_fmt_fn)
 398 {
 399   h->kvp_fmt_fn = kvp_fmt_fn;
 400 }
 401
 402 int BV (clib_bihash_is_initialised) (const BVT (clib_bihash) * h)
 403 {
 404   return (h->instantiated != 0);
 405 }
 406
 407 void BV (clib_bihash_free) (BVT (clib_bihash) * h)
 408 {
 409   int i;
 410
 411   if (PREDICT_FALSE (h->instantiated == 0))
 412     goto never_initialized;
 413
 414   h->instantiated = 0;
 415
 416   if (BIHASH_USE_HEAP)
 417     {
 418       BVT (clib_bihash_alloc_chunk) * next, *chunk;
 419       void *oldheap = clib_mem_set_heap (h->heap);
 420
 421       chunk = h->chunks;
 422       while (chunk)
 423         {
 424           next = chunk->next;
 425           clib_mem_free (chunk);
 426           chunk = next;
 427         }
 428       clib_mem_set_heap (oldheap);
 429     }
 430
 431   vec_free (h->working_copies);
 432   vec_free (h->working_copy_lengths);
 433   clib_mem_free ((void *) h->alloc_lock);
 434 #if BIHASH_32_64_SVM == 0
 435   vec_free (h->freelists);
 436 #else
 437   if (h->memfd > 0)
 438     (void) close (h->memfd);
 439 #endif
 440   if (BIHASH_USE_HEAP == 0)
 441     clib_mem_vm_free ((void *) (uword) (alloc_arena (h)),
 442                       alloc_arena_size (h));
 443 never_initialized:
 444   if (h->dont_add_to_all_bihash_list)
 445     {
 446       clib_memset_u8 (h, 0, sizeof (*h));
 447       return;
 448     }
 449   clib_memset_u8 (h, 0, sizeof (*h));
 450   for (i = 0; i < vec_len (clib_all_bihashes); i++)
 451     {
 452       if ((void *) h == clib_all_bihashes[i])
 453         {
 454           vec_delete (clib_all_bihashes, 1, i);
 455           return;
 456         }
 457     }
 458   clib_warning ("Couldn't find hash table %llx on clib_all_bihashes...",
 459                 (u64) (uword) h);
 460 }
 461
 462 static
 463 BVT (clib_bihash_value) *
 464 BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages)
 465 {
 466   int i;
 467   BVT (clib_bihash_value) * rv = 0;
 468
 469   ASSERT (h->alloc_lock[0]);
 470
 471 #if BIHASH_32_64_SVM
 472   ASSERT (log2_pages < vec_len (h->freelists));
 473 #endif
 474
 475   if (log2_pages >= vec_len (h->freelists) || h->freelists[log2_pages] == 0)
 476     {
 477       vec_validate_init_empty (h->freelists, log2_pages, 0);
 478       rv = BV (alloc_aligned) (h, (sizeof (*rv) * (1 << log2_pages)));
 479       goto initialize;
 480     }
 481   rv = BV (clib_bihash_get_value) (h, (uword) h->freelists[log2_pages]);
 482   h->freelists[log2_pages] = rv->next_free_as_u64;
 483
 484 initialize:
 485   ASSERT (rv);
 486
 487   BVT (clib_bihash_kv) * v;
 488   v = (BVT (clib_bihash_kv) *) rv;
 489
 490   for (i = 0; i < BIHASH_KVP_PER_PAGE * (1 << log2_pages); i++)
 491     {
 492       BV (clib_bihash_mark_free) (v);
 493       v++;
 494     }
 495   return rv;
 496 }
 497
 498 static void
 499 BV (value_free) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * v,
 500                  u32 log2_pages)
 501 {
 502   ASSERT (h->alloc_lock[0]);
 503
 504   ASSERT (vec_len (h->freelists) > log2_pages);
 505
 506   if (BIHASH_USE_HEAP && log2_pages >= BIIHASH_MIN_ALLOC_LOG2_PAGES)
 507     {
 508       /* allocations bigger or equal to chunk size always contain single
 509        * alloc and they can be given back to heap */
 510       void *oldheap;
 511       BVT (clib_bihash_alloc_chunk) * c;
 512       c = (BVT (clib_bihash_alloc_chunk) *) v - 1;
 513
 514       if (c->prev)
 515         c->prev->next = c->next;
 516       else
 517         h->chunks = c->next;
 518
 519       if (c->next)
 520         c->next->prev = c->prev;
 521
 522       oldheap = clib_mem_set_heap (h->heap);
 523       clib_mem_free (c);
 524       clib_mem_set_heap (oldheap);
 525       return;
 526     }
 527
 528   if (CLIB_DEBUG > 0)
 529     clib_memset_u8 (v, 0xFE, sizeof (*v) * (1 << log2_pages));
 530
 531   v->next_free_as_u64 = (u64) h->freelists[log2_pages];
 532   h->freelists[log2_pages] = (u64) BV (clib_bihash_get_offset) (h, v);
 533 }
 534
 535 static inline void
 536 BV (make_working_copy) (BVT (clib_bihash) * h, BVT (clib_bihash_bucket) * b)
 537 {
 538   BVT (clib_bihash_value) * v;
 539   BVT (clib_bihash_bucket) working_bucket __attribute__ ((aligned (8)));
 540   BVT (clib_bihash_value) * working_copy;
 541   u32 thread_index = os_get_thread_index ();
 542   int log2_working_copy_length;
 543
 544   ASSERT (h->alloc_lock[0]);
 545
 546   if (thread_index >= vec_len (h->working_copies))
 547     {
 548       vec_validate (h->working_copies, thread_index);
 549       vec_validate_init_empty (h->working_copy_lengths, thread_index, ~0);
 550     }
 551
 552   /*
 553    * working_copies are per-cpu so that near-simultaneous
 554    * updates from multiple threads will not result in sporadic, spurious
 555    * lookup failures.
 556    */
 557   working_copy = h->working_copies[thread_index];
 558   log2_working_copy_length = h->working_copy_lengths[thread_index];
 559
 560   h->saved_bucket.as_u64 = b->as_u64;
 561
 562   if (b->log2_pages > log2_working_copy_length)
 563     {
 564       /*
 565        * It's not worth the bookkeeping to free working copies
 566        *   if (working_copy)
 567        *     clib_mem_free (working_copy);
 568        */
 569       working_copy = BV (alloc_aligned)
 570         (h, sizeof (working_copy[0]) * (1 << b->log2_pages));
 571       h->working_copy_lengths[thread_index] = b->log2_pages;
 572       h->working_copies[thread_index] = working_copy;
 573
 574       BV (clib_bihash_increment_stat) (h, BIHASH_STAT_working_copy_lost,
 575                                        1ULL << b->log2_pages);
 576     }
 577
 578   v = BV (clib_bihash_get_value) (h, b->offset);
 579
 580   clib_memcpy_fast (working_copy, v, sizeof (*v) * (1 << b->log2_pages));
 581   working_bucket.as_u64 = b->as_u64;
 582   working_bucket.offset = BV (clib_bihash_get_offset) (h, working_copy);
 583   CLIB_MEMORY_STORE_BARRIER ();
 584   b->as_u64 = working_bucket.as_u64;
 585   h->working_copies[thread_index] = working_copy;
 586 }
 587
 588 static
 589 BVT (clib_bihash_value) *
 590 BV (split_and_rehash)
 591   (BVT (clib_bihash) * h,
 592    BVT (clib_bihash_value) * old_values, u32 old_log2_pages,
 593    u32 new_log2_pages)
 594 {
 595   BVT (clib_bihash_value) * new_values, *new_v;
 596   int i, j, length_in_kvs;
 597
 598   ASSERT (h->alloc_lock[0]);
 599
 600   new_values = BV (value_alloc) (h, new_log2_pages);
 601   length_in_kvs = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE;
 602
 603   for (i = 0; i < length_in_kvs; i++)
 604     {
 605       u64 new_hash;
 606
 607       /* Entry not in use? Forget it */
 608       if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
 609         continue;
 610
 611       /* rehash the item onto its new home-page */
 612       new_hash = BV (clib_bihash_hash) (&(old_values->kvp[i]));
 613       new_hash = extract_bits (new_hash, h->log2_nbuckets, new_log2_pages);
 614       new_v = &new_values[new_hash];
 615
 616       /* Across the new home-page */
 617       for (j = 0; j < BIHASH_KVP_PER_PAGE; j++)
 618         {
 619           /* Empty slot */
 620           if (BV (clib_bihash_is_free) (&(new_v->kvp[j])))
 621             {
 622               clib_memcpy_fast (&(new_v->kvp[j]), &(old_values->kvp[i]),
 623                                 sizeof (new_v->kvp[j]));
 624               goto doublebreak;
 625             }
 626         }
 627       /* Crap. Tell caller to try again */
 628       BV (value_free) (h, new_values, new_log2_pages);
 629       return 0;
 630     doublebreak:;
 631     }
 632
 633   return new_values;
 634 }
 635
 636 static
 637 BVT (clib_bihash_value) *
 638 BV (split_and_rehash_linear)
 639   (BVT (clib_bihash) * h,
 640    BVT (clib_bihash_value) * old_values, u32 old_log2_pages,
 641    u32 new_log2_pages)
 642 {
 643   BVT (clib_bihash_value) * new_values;
 644   int i, j, new_length, old_length;
 645
 646   ASSERT (h->alloc_lock[0]);
 647
 648   new_values = BV (value_alloc) (h, new_log2_pages);
 649   new_length = (1 << new_log2_pages) * BIHASH_KVP_PER_PAGE;
 650   old_length = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE;
 651
 652   j = 0;
 653   /* Across the old value array */
 654   for (i = 0; i < old_length; i++)
 655     {
 656       /* Find a free slot in the new linear scan bucket */
 657       for (; j < new_length; j++)
 658         {
 659           /* Old value not in use? Forget it. */
 660           if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
 661             goto doublebreak;
 662
 663           /* New value should never be in use */
 664           if (BV (clib_bihash_is_free) (&(new_values->kvp[j])))
 665             {
 666               /* Copy the old value and move along */
 667               clib_memcpy_fast (&(new_values->kvp[j]), &(old_values->kvp[i]),
 668                                 sizeof (new_values->kvp[j]));
 669               j++;
 670               goto doublebreak;
 671             }
 672         }
 673       /* This should never happen... */
 674       clib_warning ("BUG: linear rehash failed!");
 675       BV (value_free) (h, new_values, new_log2_pages);
 676       return 0;
 677
 678     doublebreak:;
 679     }
 680   return new_values;
 681 }
 682
 683 static_always_inline int BV (clib_bihash_add_del_inline_with_hash) (
 684   BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, u64 hash, int is_add,
 685   int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *is_stale_arg,
 686   void (*overwrite_cb) (BVT (clib_bihash_kv) *, void *), void *overwrite_arg)
 687 {
 688   BVT (clib_bihash_bucket) * b, tmp_b;
 689   BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy;
 690   int i, limit;
 691   u64 new_hash;
 692   u32 new_log2_pages, old_log2_pages;
 693   u32 thread_index = os_get_thread_index ();
 694   int mark_bucket_linear;
 695   int resplit_once;
 696
 697   /* *INDENT-OFF* */
 698   static const BVT (clib_bihash_bucket) mask = {
 699     .linear_search = 1,
 700     .log2_pages = -1
 701   };
 702   /* *INDENT-ON* */
 703
 704 #if BIHASH_LAZY_INSTANTIATE
 705   /*
 706    * Create the table (is_add=1,2), or flunk the request now (is_add=0)
 707    * Use the alloc_lock to protect the instantiate operation.
 708    */
 709   if (PREDICT_FALSE (h->instantiated == 0))
 710     {
 711       if (is_add == 0)
 712         return (-1);
 713
 714       BV (clib_bihash_alloc_lock) (h);
 715       if (h->instantiated == 0)
 716         BV (clib_bihash_instantiate) (h);
 717       BV (clib_bihash_alloc_unlock) (h);
 718     }
 719 #else
 720   /* Debug image: make sure the table has been instantiated */
 721   ASSERT (h->instantiated != 0);
 722 #endif
 723
 724   /*
 725    * Debug image: make sure that an item being added doesn't accidentally
 726    * look like a free item.
 727    */
 728   ASSERT ((is_add && BV (clib_bihash_is_free) (add_v)) == 0);
 729
 730   b = BV (clib_bihash_get_bucket) (h, hash);
 731
 732   BV (clib_bihash_lock_bucket) (b);
 733
 734   /* First elt in the bucket? */
 735   if (BIHASH_KVP_AT_BUCKET_LEVEL == 0 && BV (clib_bihash_bucket_is_empty) (b))
 736     {
 737       if (is_add == 0)
 738         {
 739           BV (clib_bihash_unlock_bucket) (b);
 740           return (-1);
 741         }
 742
 743       BV (clib_bihash_alloc_lock) (h);
 744       v = BV (value_alloc) (h, 0);
 745       BV (clib_bihash_alloc_unlock) (h);
 746
 747       *v->kvp = *add_v;
 748       tmp_b.as_u64 = 0;         /* clears bucket lock */
 749       tmp_b.offset = BV (clib_bihash_get_offset) (h, v);
 750       tmp_b.refcnt = 1;
 751       CLIB_MEMORY_STORE_BARRIER ();
 752
 753       b->as_u64 = tmp_b.as_u64; /* unlocks the bucket */
 754       BV (clib_bihash_increment_stat) (h, BIHASH_STAT_alloc_add, 1);
 755
 756       return (0);
 757     }
 758
 759   /* WARNING: we're still looking at the live copy... */
 760   limit = BIHASH_KVP_PER_PAGE;
 761   v = BV (clib_bihash_get_value) (h, b->offset);
 762
 763   if (PREDICT_FALSE (b->as_u64 & mask.as_u64))
 764     {
 765       if (PREDICT_FALSE (b->linear_search))
 766         limit <<= b->log2_pages;
 767       else
 768         v += extract_bits (hash, h->log2_nbuckets, b->log2_pages);
 769     }
 770
 771   if (is_add)
 772     {
 773       /*
 774        * Because reader threads are looking at live data,
 775        * we have to be extra careful. Readers do NOT hold the
 776        * bucket lock. We need to be SLOWER than a search, past the
 777        * point where readers CHECK the bucket lock.
 778        */
 779
 780       /*
 781        * For obvious (in hindsight) reasons, see if we're supposed to
 782        * replace an existing key, then look for an empty slot.
 783        */
 784       for (i = 0; i < limit; i++)
 785         {
 786           if (BV (clib_bihash_is_free) (&(v->kvp[i])))
 787             continue;
 788           if (BV (clib_bihash_key_compare) (v->kvp[i].key, add_v->key))
 789             {
 790               /* Add but do not overwrite? */
 791               if (is_add == 2)
 792                 {
 793                   BV (clib_bihash_unlock_bucket) (b);
 794                   return (-2);
 795                 }
 796               if (overwrite_cb)
 797                 overwrite_cb (&(v->kvp[i]), overwrite_arg);
 798               clib_memcpy_fast (&(v->kvp[i].value),
 799                                 &add_v->value, sizeof (add_v->value));
 800               BV (clib_bihash_unlock_bucket) (b);
 801               BV (clib_bihash_increment_stat) (h, BIHASH_STAT_replace, 1);
 802               return (0);
 803             }
 804         }
 805       /*
 806        * Look for an empty slot. If found, use it
 807        */
 808       for (i = 0; i < limit; i++)
 809         {
 810           if (BV (clib_bihash_is_free) (&(v->kvp[i])))
 811             {
 812               /*
 813                * Copy the value first, so that if a reader manages
 814                * to match the new key, the value will be right...
 815                */
 816               clib_memcpy_fast (&(v->kvp[i].value),
 817                                 &add_v->value, sizeof (add_v->value));
 818               CLIB_MEMORY_STORE_BARRIER ();     /* Make sure the value has settled */
 819               clib_memcpy_fast (&(v->kvp[i]), &add_v->key,
 820                                 sizeof (add_v->key));
 821               b->refcnt++;
 822               ASSERT (b->refcnt > 0);
 823               BV (clib_bihash_unlock_bucket) (b);
 824               BV (clib_bihash_increment_stat) (h, BIHASH_STAT_add, 1);
 825               return (0);
 826             }
 827         }
 828       /* look for stale data to overwrite */
 829       if (is_stale_cb)
 830         {
 831           for (i = 0; i < limit; i++)
 832             {
 833               if (is_stale_cb (&(v->kvp[i]), is_stale_arg))
 834                 {
 835                   clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v));
 836                   CLIB_MEMORY_STORE_BARRIER ();
 837                   BV (clib_bihash_unlock_bucket) (b);
 838                   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_replace, 1);
 839                   return (0);
 840                 }
 841             }
 842         }
 843       /* Out of space in this bucket, split the bucket... */
 844     }
 845   else                          /* delete case */
 846     {
 847       for (i = 0; i < limit; i++)
 848         {
 849           /* no sense even looking at this one */
 850           if (BV (clib_bihash_is_free) (&(v->kvp[i])))
 851             continue;
 852           /* Found the key? Kill it... */
 853           if (BV (clib_bihash_key_compare) (v->kvp[i].key, add_v->key))
 854             {
 855               BV (clib_bihash_mark_free) (&(v->kvp[i]));
 856               /* Is the bucket empty? */
 857               if (PREDICT_TRUE (b->refcnt > 1))
 858                 {
 859                   b->refcnt--;
 860                   /* Switch back to the bucket-level kvp array? */
 861                   if (BIHASH_KVP_AT_BUCKET_LEVEL && b->refcnt == 1
 862                       && b->log2_pages > 0)
 863                     {
 864                       tmp_b.as_u64 = b->as_u64;
 865                       b->offset = BV (clib_bihash_get_offset)
 866                         (h, (void *) (b + 1));
 867                       b->linear_search = 0;
 868                       b->log2_pages = 0;
 869                       /* Clean up the bucket-level kvp array */
 870                       BVT (clib_bihash_kv) *v = (void *) (b + 1);
 871                       int j;
 872                       for (j = 0; j < BIHASH_KVP_PER_PAGE; j++)
 873                         {
 874                           BV (clib_bihash_mark_free) (v);
 875                           v++;
 876                         }
 877                       CLIB_MEMORY_STORE_BARRIER ();
 878                       BV (clib_bihash_unlock_bucket) (b);
 879                       BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del, 1);
 880                       goto free_backing_store;
 881                     }
 882
 883                   CLIB_MEMORY_STORE_BARRIER ();
 884                   BV (clib_bihash_unlock_bucket) (b);
 885                   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del, 1);
 886                   return (0);
 887                 }
 888               else              /* yes, free it */
 889                 {
 890                   /* Save old bucket value, need log2_pages to free it */
 891                   tmp_b.as_u64 = b->as_u64;
 892
 893                   /* Kill and unlock the bucket */
 894                   b->as_u64 = 0;
 895
 896                 free_backing_store:
 897                   /* And free the backing storage */
 898                   BV (clib_bihash_alloc_lock) (h);
 899                   /* Note: v currently points into the middle of the bucket */
 900                   v = BV (clib_bihash_get_value) (h, tmp_b.offset);
 901                   BV (value_free) (h, v, tmp_b.log2_pages);
 902                   BV (clib_bihash_alloc_unlock) (h);
 903                   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del_free,
 904                                                    1);
 905                   return (0);
 906                 }
 907             }
 908         }
 909       /* Not found... */
 910       BV (clib_bihash_unlock_bucket) (b);
 911       return (-3);
 912     }
 913
 914   /* Move readers to a (locked) temp copy of the bucket */
 915   BV (clib_bihash_alloc_lock) (h);
 916   BV (make_working_copy) (h, b);
 917
 918   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
 919
 920   old_log2_pages = h->saved_bucket.log2_pages;
 921   new_log2_pages = old_log2_pages + 1;
 922   mark_bucket_linear = 0;
 923   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_split_add, 1);
 924   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits, old_log2_pages);
 925
 926   working_copy = h->working_copies[thread_index];
 927   resplit_once = 0;
 928   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits, 1);
 929
 930   new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
 931                                  new_log2_pages);
 932   if (new_v == 0)
 933     {
 934     try_resplit:
 935       resplit_once = 1;
 936       new_log2_pages++;
 937       /* Try re-splitting. If that fails, fall back to linear search */
 938       new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
 939                                      new_log2_pages);
 940       if (new_v == 0)
 941         {
 942         mark_linear:
 943           new_log2_pages--;
 944           /* pinned collisions, use linear search */
 945           new_v =
 946             BV (split_and_rehash_linear) (h, working_copy, old_log2_pages,
 947                                           new_log2_pages);
 948           mark_bucket_linear = 1;
 949           BV (clib_bihash_increment_stat) (h, BIHASH_STAT_linear, 1);
 950         }
 951       BV (clib_bihash_increment_stat) (h, BIHASH_STAT_resplit, 1);
 952       BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits,
 953                                        old_log2_pages + 1);
 954     }
 955
 956   /* Try to add the new entry */
 957   save_new_v = new_v;
 958   new_hash = BV (clib_bihash_hash) (add_v);
 959   limit = BIHASH_KVP_PER_PAGE;
 960   if (mark_bucket_linear)
 961     limit <<= new_log2_pages;
 962   else
 963     new_v += extract_bits (new_hash, h->log2_nbuckets, new_log2_pages);
 964
 965   for (i = 0; i < limit; i++)
 966     {
 967       if (BV (clib_bihash_is_free) (&(new_v->kvp[i])))
 968         {
 969           clib_memcpy_fast (&(new_v->kvp[i]), add_v, sizeof (*add_v));
 970           goto expand_ok;
 971         }
 972     }
 973
 974   /* Crap. Try again */
 975   BV (value_free) (h, save_new_v, new_log2_pages);
 976   /*
 977    * If we've already doubled the size of the bucket once,
 978    * fall back to linear search now.
 979    */
 980   if (resplit_once)
 981     goto mark_linear;
 982   else
 983     goto try_resplit;
 984
 985 expand_ok:
 986   tmp_b.log2_pages = new_log2_pages;
 987   tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
 988   tmp_b.linear_search = mark_bucket_linear;
 989 #if BIHASH_KVP_AT_BUCKET_LEVEL
 990   /* Compensate for permanent refcount bump at the bucket level */
 991   if (new_log2_pages > 0)
 992 #endif
 993     tmp_b.refcnt = h->saved_bucket.refcnt + 1;
 994   ASSERT (tmp_b.refcnt > 0);
 995   tmp_b.lock = 0;
 996   CLIB_MEMORY_STORE_BARRIER ();
 997   b->as_u64 = tmp_b.as_u64;
 998
 999 #if BIHASH_KVP_AT_BUCKET_LEVEL
1000   if (h->saved_bucket.log2_pages > 0)
1001     {
1002 #endif
1003
1004       /* free the old bucket, except at the bucket level if so configured */
1005       v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
1006       BV (value_free) (h, v, h->saved_bucket.log2_pages);
1007
1008 #if BIHASH_KVP_AT_BUCKET_LEVEL
1009     }
1010 #endif
1011
1012
1013   BV (clib_bihash_alloc_unlock) (h);
1014   return (0);
1015 }
1016
1017 static_always_inline int BV (clib_bihash_add_del_inline)
1018   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add,
1019    int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg)
1020 {
1021   u64 hash = BV (clib_bihash_hash) (add_v);
1022   return BV (clib_bihash_add_del_inline_with_hash) (h, add_v, hash, is_add,
1023                                                     is_stale_cb, arg, 0, 0);
1024 }
1025
1026 int BV (clib_bihash_add_del_with_hash) (BVT (clib_bihash) * h,
1027                                         BVT (clib_bihash_kv) * add_v, u64 hash,
1028                                         int is_add)
1029 {
1030   return BV (clib_bihash_add_del_inline_with_hash) (h, add_v, hash, is_add, 0,
1031                                                     0, 0, 0);
1032 }
1033
1034 int BV (clib_bihash_add_del)
1035   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
1036 {
1037   return BV (clib_bihash_add_del_inline) (h, add_v, is_add, 0, 0);
1038 }
1039
1040 int BV (clib_bihash_add_or_overwrite_stale)
1041   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
1042    int (*stale_callback) (BVT (clib_bihash_kv) *, void *), void *arg)
1043 {
1044   return BV (clib_bihash_add_del_inline) (h, add_v, 1, stale_callback, arg);
1045 }
1046
1047 int BV (clib_bihash_add_with_overwrite_cb) (
1048   BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
1049   void (overwrite_cb) (BVT (clib_bihash_kv) *, void *), void *arg)
1050 {
1051   u64 hash = BV (clib_bihash_hash) (add_v);
1052   return BV (clib_bihash_add_del_inline_with_hash) (h, add_v, hash, 1, 0, 0,
1053                                                     overwrite_cb, arg);
1054 }
1055
1056 int BV (clib_bihash_search)
1057   (BVT (clib_bihash) * h,
1058    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
1059 {
1060   return BV (clib_bihash_search_inline_2) (h, search_key, valuep);
1061 }
1062
1063 u8 *BV (format_bihash) (u8 * s, va_list * args)
1064 {
1065   BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *);
1066   int verbose = va_arg (*args, int);
1067   BVT (clib_bihash_bucket) * b;
1068   BVT (clib_bihash_value) * v;
1069   int i, j, k;
1070   u64 active_elements = 0;
1071   u64 active_buckets = 0;
1072   u64 linear_buckets = 0;
1073
1074   s = format (s, "Hash table '%s'\n", h->name ? h->name : (u8 *) "(unnamed)");
1075
1076 #if BIHASH_LAZY_INSTANTIATE
1077   if (PREDICT_FALSE (h->instantiated == 0))
1078     return format (s, "    empty, uninitialized");
1079 #endif
1080
1081   for (i = 0; i < h->nbuckets; i++)
1082     {
1083       b = BV (clib_bihash_get_bucket) (h, i);
1084       if (BV (clib_bihash_bucket_is_empty) (b))
1085         {
1086           if (verbose > 1)
1087             s = format (s, "[%d]: empty\n", i);
1088           continue;
1089         }
1090
1091       active_buckets++;
1092
1093       if (b->linear_search)
1094         linear_buckets++;
1095
1096       if (verbose)
1097         {
1098           s = format
1099             (s, "[%d]: heap offset %lld, len %d, refcnt %d, linear %d\n", i,
1100              b->offset, (1 << b->log2_pages), b->refcnt, b->linear_search);
1101         }
1102
1103       v = BV (clib_bihash_get_value) (h, b->offset);
1104       for (j = 0; j < (1 << b->log2_pages); j++)
1105         {
1106           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
1107             {
1108               if (BV (clib_bihash_is_free) (&v->kvp[k]))
1109                 {
1110                   if (verbose > 1)
1111                     s = format (s, "    %d: empty\n",
1112                                 j * BIHASH_KVP_PER_PAGE + k);
1113                   continue;
1114                 }
1115               if (verbose)
1116                 {
1117                   if (h->kvp_fmt_fn)
1118                     {
1119                       s = format (s, "    %d: %U\n",
1120                                   j * BIHASH_KVP_PER_PAGE + k,
1121                                   h->kvp_fmt_fn, &(v->kvp[k]), verbose);
1122                     }
1123                   else
1124                     {
1125                       s = format (s, "    %d: %U\n",
1126                                   j * BIHASH_KVP_PER_PAGE + k,
1127                                   BV (format_bihash_kvp), &(v->kvp[k]));
1128                     }
1129                 }
1130               active_elements++;
1131             }
1132           v++;
1133         }
1134     }
1135
1136   s = format (s, "    %lld active elements %lld active buckets\n",
1137               active_elements, active_buckets);
1138   s = format (s, "    %d free lists\n", vec_len (h->freelists));
1139
1140   for (i = 0; i < vec_len (h->freelists); i++)
1141     {
1142       u32 nfree = 0;
1143       BVT (clib_bihash_value) * free_elt;
1144       u64 free_elt_as_u64 = h->freelists[i];
1145
1146       while (free_elt_as_u64)
1147         {
1148           free_elt = BV (clib_bihash_get_value) (h, free_elt_as_u64);
1149           nfree++;
1150           free_elt_as_u64 = free_elt->next_free_as_u64;
1151         }
1152
1153       if (nfree || verbose)
1154         s = format (s, "       [len %d] %u free elts\n", 1 << i, nfree);
1155     }
1156
1157   s = format (s, "    %lld linear search buckets\n", linear_buckets);
1158   if (BIHASH_USE_HEAP)
1159     {
1160       BVT (clib_bihash_alloc_chunk) * c = h->chunks;
1161       uword bytes_left = 0, total_size = 0, n_chunks = 0;
1162
1163       while (c)
1164         {
1165           bytes_left += c->bytes_left;
1166           total_size += c->size;
1167           n_chunks += 1;
1168           c = c->next;
1169         }
1170       s = format (s,
1171                   "    heap: %u chunk(s) allocated\n"
1172                   "          bytes: used %U, scrap %U\n", n_chunks,
1173                   format_memory_size, total_size,
1174                   format_memory_size, bytes_left);
1175     }
1176   else
1177     {
1178       u64 used_bytes = alloc_arena_next (h);
1179       s = format (s,
1180                   "    arena: base %llx, next %llx\n"
1181                   "           used %lld b (%lld Mbytes) of %lld b (%lld Mbytes)\n",
1182                   alloc_arena (h), alloc_arena_next (h),
1183                   used_bytes, used_bytes >> 20,
1184                   alloc_arena_size (h), alloc_arena_size (h) >> 20);
1185     }
1186   return s;
1187 }
1188
1189 void BV (clib_bihash_foreach_key_value_pair)
1190   (BVT (clib_bihash) * h,
1191    BV (clib_bihash_foreach_key_value_pair_cb) cb, void *arg)
1192 {
1193   int i, j, k;
1194   BVT (clib_bihash_bucket) * b;
1195   BVT (clib_bihash_value) * v;
1196
1197
1198 #if BIHASH_LAZY_INSTANTIATE
1199   if (PREDICT_FALSE (h->instantiated == 0))
1200     return;
1201 #endif
1202
1203   for (i = 0; i < h->nbuckets; i++)
1204     {
1205       b = BV (clib_bihash_get_bucket) (h, i);
1206       if (BV (clib_bihash_bucket_is_empty) (b))
1207         continue;
1208
1209       v = BV (clib_bihash_get_value) (h, b->offset);
1210       for (j = 0; j < (1 << b->log2_pages); j++)
1211         {
1212           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
1213             {
1214               if (BV (clib_bihash_is_free) (&v->kvp[k]))
1215                 continue;
1216
1217               if (BIHASH_WALK_STOP == cb (&v->kvp[k], arg))
1218                 return;
1219               /*
1220                * In case the callback deletes the last entry in the bucket...
1221                */
1222               if (BV (clib_bihash_bucket_is_empty) (b))
1223                 goto doublebreak;
1224             }
1225           v++;
1226         }
1227     doublebreak:
1228       ;
1229     }
1230 }
1231
1232 /** @endcond */
1233
1234 /*
1235  * fd.io coding-style-patch-verification: ON
1236  *
1237  * Local Variables:
1238  * eval: (c-set-style "gnu")
1239  * End:
1240  */