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 = h->alloc_arena_next;
  27   h->alloc_arena_next += nbytes;
  28
  29   if (rv >= (h->alloc_arena + h->alloc_arena_size))
  30     os_out_of_memory ();
  31
  32   return (void *) rv;
  33 }
  34
  35
  36 void BV (clib_bihash_init)
  37   (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size)
  38 {
  39   uword bucket_size;
  40
  41   nbuckets = 1 << (max_log2 (nbuckets));
  42
  43   h->name = (u8 *) name;
  44   h->nbuckets = nbuckets;
  45   h->log2_nbuckets = max_log2 (nbuckets);
  46   h->cache_hits = 0;
  47   h->cache_misses = 0;
  48
  49   /*
  50    * Make sure the requested size is rational. The max table
  51    * size without playing the alignment card is 64 Gbytes.
  52    * If someone starts complaining that's not enough, we can shift
  53    * the offset by CLIB_LOG2_CACHE_LINE_BYTES...
  54    */
  55   ASSERT (memory_size < (1ULL << BIHASH_BUCKET_OFFSET_BITS));
  56
  57   h->alloc_arena = (uword) clib_mem_vm_alloc (memory_size);
  58   h->alloc_arena_next = h->alloc_arena;
  59   h->alloc_arena_size = memory_size;
  60
  61   bucket_size = nbuckets * sizeof (h->buckets[0]);
  62   h->buckets = BV (alloc_aligned) (h, bucket_size);
  63
  64   h->alloc_lock = BV (alloc_aligned) (h, CLIB_CACHE_LINE_BYTES);
  65   h->alloc_lock[0] = 0;
  66
  67   h->fmt_fn = NULL;
  68 }
  69
  70 void BV (clib_bihash_set_kvp_format_fn) (BVT (clib_bihash) * h,
  71                                          format_function_t * fmt_fn)
  72 {
  73   h->fmt_fn = fmt_fn;
  74 }
  75
  76 void BV (clib_bihash_free) (BVT (clib_bihash) * h)
  77 {
  78   vec_free (h->working_copies);
  79   vec_free (h->freelists);
  80   clib_mem_vm_free ((void *) (h->alloc_arena), h->alloc_arena_size);
  81   memset (h, 0, sizeof (*h));
  82 }
  83
  84 static
  85 BVT (clib_bihash_value) *
  86 BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages)
  87 {
  88   BVT (clib_bihash_value) * rv = 0;
  89
  90   ASSERT (h->alloc_lock[0]);
  91   if (log2_pages >= vec_len (h->freelists) || h->freelists[log2_pages] == 0)
  92     {
  93       vec_validate_init_empty (h->freelists, log2_pages, 0);
  94       rv = BV (alloc_aligned) (h, (sizeof (*rv) * (1 << log2_pages)));
  95       goto initialize;
  96     }
  97   rv = h->freelists[log2_pages];
  98   h->freelists[log2_pages] = rv->next_free;
  99
 100 initialize:
 101   ASSERT (rv);
 102   /*
 103    * Latest gcc complains that the length arg is zero
 104    * if we replace (1<<log2_pages) with vec_len(rv).
 105    * No clue.
 106    */
 107   memset (rv, 0xff, sizeof (*rv) * (1 << log2_pages));
 108   return rv;
 109 }
 110
 111 static void
 112 BV (value_free) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * v,
 113                  u32 log2_pages)
 114 {
 115   ASSERT (h->alloc_lock[0]);
 116
 117   ASSERT (vec_len (h->freelists) > log2_pages);
 118
 119   if (CLIB_DEBUG > 0)
 120     memset (v, 0xFE, sizeof (*v) * (1 << log2_pages));
 121
 122   v->next_free = h->freelists[log2_pages];
 123   h->freelists[log2_pages] = v;
 124 }
 125
 126 static inline void
 127 BV (make_working_copy) (BVT (clib_bihash) * h, BVT (clib_bihash_bucket) * b)
 128 {
 129   BVT (clib_bihash_value) * v;
 130   BVT (clib_bihash_bucket) working_bucket __attribute__ ((aligned (8)));
 131   BVT (clib_bihash_value) * working_copy;
 132   u32 thread_index = os_get_thread_index ();
 133   int log2_working_copy_length;
 134
 135   ASSERT (h->alloc_lock[0]);
 136
 137   if (thread_index >= vec_len (h->working_copies))
 138     {
 139       vec_validate (h->working_copies, thread_index);
 140       vec_validate_init_empty (h->working_copy_lengths, thread_index, ~0);
 141     }
 142
 143   /*
 144    * working_copies are per-cpu so that near-simultaneous
 145    * updates from multiple threads will not result in sporadic, spurious
 146    * lookup failures.
 147    */
 148   working_copy = h->working_copies[thread_index];
 149   log2_working_copy_length = h->working_copy_lengths[thread_index];
 150
 151   h->saved_bucket.as_u64 = b->as_u64;
 152
 153   if (b->log2_pages > log2_working_copy_length)
 154     {
 155       /*
 156        * It's not worth the bookkeeping to free working copies
 157        *   if (working_copy)
 158        *     clib_mem_free (working_copy);
 159        */
 160       working_copy = BV (alloc_aligned)
 161         (h, sizeof (working_copy[0]) * (1 << b->log2_pages));
 162       h->working_copy_lengths[thread_index] = b->log2_pages;
 163       h->working_copies[thread_index] = working_copy;
 164     }
 165
 166   v = BV (clib_bihash_get_value) (h, b->offset);
 167
 168   clib_memcpy (working_copy, v, sizeof (*v) * (1 << b->log2_pages));
 169   working_bucket.as_u64 = b->as_u64;
 170   working_bucket.offset = BV (clib_bihash_get_offset) (h, working_copy);
 171   CLIB_MEMORY_BARRIER ();
 172   b->as_u64 = working_bucket.as_u64;
 173   h->working_copies[thread_index] = working_copy;
 174 }
 175
 176 static
 177 BVT (clib_bihash_value) *
 178 BV (split_and_rehash)
 179   (BVT (clib_bihash) * h,
 180    BVT (clib_bihash_value) * old_values, u32 old_log2_pages,
 181    u32 new_log2_pages)
 182 {
 183   BVT (clib_bihash_value) * new_values, *new_v;
 184   int i, j, length_in_kvs;
 185
 186   ASSERT (h->alloc_lock[0]);
 187
 188   new_values = BV (value_alloc) (h, new_log2_pages);
 189   length_in_kvs = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE;
 190
 191   for (i = 0; i < length_in_kvs; i++)
 192     {
 193       u64 new_hash;
 194
 195       /* Entry not in use? Forget it */
 196       if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
 197         continue;
 198
 199       /* rehash the item onto its new home-page */
 200       new_hash = BV (clib_bihash_hash) (&(old_values->kvp[i]));
 201       new_hash >>= h->log2_nbuckets;
 202       new_hash &= (1 << new_log2_pages) - 1;
 203       new_v = &new_values[new_hash];
 204
 205       /* Across the new home-page */
 206       for (j = 0; j < BIHASH_KVP_PER_PAGE; j++)
 207         {
 208           /* Empty slot */
 209           if (BV (clib_bihash_is_free) (&(new_v->kvp[j])))
 210             {
 211               clib_memcpy (&(new_v->kvp[j]), &(old_values->kvp[i]),
 212                            sizeof (new_v->kvp[j]));
 213               goto doublebreak;
 214             }
 215         }
 216       /* Crap. Tell caller to try again */
 217       BV (value_free) (h, new_values, new_log2_pages);
 218       return 0;
 219     doublebreak:;
 220     }
 221
 222   return new_values;
 223 }
 224
 225 static
 226 BVT (clib_bihash_value) *
 227 BV (split_and_rehash_linear)
 228   (BVT (clib_bihash) * h,
 229    BVT (clib_bihash_value) * old_values, u32 old_log2_pages,
 230    u32 new_log2_pages)
 231 {
 232   BVT (clib_bihash_value) * new_values;
 233   int i, j, new_length, old_length;
 234
 235   ASSERT (h->alloc_lock[0]);
 236
 237   new_values = BV (value_alloc) (h, new_log2_pages);
 238   new_length = (1 << new_log2_pages) * BIHASH_KVP_PER_PAGE;
 239   old_length = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE;
 240
 241   j = 0;
 242   /* Across the old value array */
 243   for (i = 0; i < old_length; i++)
 244     {
 245       /* Find a free slot in the new linear scan bucket */
 246       for (; j < new_length; j++)
 247         {
 248           /* Old value not in use? Forget it. */
 249           if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
 250             goto doublebreak;
 251
 252           /* New value should never be in use */
 253           if (BV (clib_bihash_is_free) (&(new_values->kvp[j])))
 254             {
 255               /* Copy the old value and move along */
 256               clib_memcpy (&(new_values->kvp[j]), &(old_values->kvp[i]),
 257                            sizeof (new_values->kvp[j]));
 258               j++;
 259               goto doublebreak;
 260             }
 261         }
 262       /* This should never happen... */
 263       clib_warning ("BUG: linear rehash failed!");
 264       BV (value_free) (h, new_values, new_log2_pages);
 265       return 0;
 266
 267     doublebreak:;
 268     }
 269   return new_values;
 270 }
 271
 272 int BV (clib_bihash_add_del)
 273   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
 274 {
 275   u32 bucket_index;
 276   BVT (clib_bihash_bucket) * b, tmp_b;
 277   BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy;
 278   int i, limit;
 279   u64 hash, new_hash;
 280   u32 new_log2_pages, old_log2_pages;
 281   u32 thread_index = os_get_thread_index ();
 282   int mark_bucket_linear;
 283   int resplit_once;
 284
 285   hash = BV (clib_bihash_hash) (add_v);
 286
 287   bucket_index = hash & (h->nbuckets - 1);
 288   b = &h->buckets[bucket_index];
 289
 290   hash >>= h->log2_nbuckets;
 291
 292   BV (clib_bihash_lock_bucket) (b);
 293
 294   /* First elt in the bucket? */
 295   if (BV (clib_bihash_bucket_is_empty) (b))
 296     {
 297       if (is_add == 0)
 298         {
 299           BV (clib_bihash_unlock_bucket) (b);
 300           return (-1);
 301         }
 302
 303       BV (clib_bihash_alloc_lock) (h);
 304       v = BV (value_alloc) (h, 0);
 305       BV (clib_bihash_alloc_unlock) (h);
 306
 307       *v->kvp = *add_v;
 308       tmp_b.as_u64 = 0;         /* clears bucket lock */
 309       tmp_b.offset = BV (clib_bihash_get_offset) (h, v);
 310       tmp_b.refcnt = 1;
 311       CLIB_MEMORY_BARRIER ();
 312
 313       b->as_u64 = tmp_b.as_u64;
 314       BV (clib_bihash_unlock_bucket) (b);
 315       return (0);
 316     }
 317
 318   /* WARNING: we're still looking at the live copy... */
 319   limit = BIHASH_KVP_PER_PAGE;
 320   v = BV (clib_bihash_get_value) (h, b->offset);
 321
 322   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 323   if (b->linear_search)
 324     limit <<= b->log2_pages;
 325
 326   if (is_add)
 327     {
 328       /*
 329        * Because reader threads are looking at live data,
 330        * we have to be extra careful. Readers do NOT hold the
 331        * bucket lock. We need to be SLOWER than a search, past the
 332        * point where readers CHECK the bucket lock.
 333        */
 334
 335       /*
 336        * For obvious (in hindsight) reasons, see if we're supposed to
 337        * replace an existing key, then look for an empty slot.
 338        */
 339       for (i = 0; i < limit; i++)
 340         {
 341           if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
 342             {
 343               CLIB_MEMORY_BARRIER ();   /* Add a delay */
 344               clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
 345               BV (clib_bihash_unlock_bucket) (b);
 346               return (0);
 347             }
 348         }
 349       /*
 350        * Look for an empty slot. If found, use it
 351        */
 352       for (i = 0; i < limit; i++)
 353         {
 354           if (BV (clib_bihash_is_free) (&(v->kvp[i])))
 355             {
 356               /*
 357                * Copy the value first, so that if a reader manages
 358                * to match the new key, the value will be right...
 359                */
 360               clib_memcpy (&(v->kvp[i].value),
 361                            &add_v->value, sizeof (add_v->value));
 362               CLIB_MEMORY_BARRIER ();   /* Make sure the value has settled */
 363               clib_memcpy (&(v->kvp[i]), &add_v->key, sizeof (add_v->key));
 364               b->refcnt++;
 365               BV (clib_bihash_unlock_bucket) (b);
 366               return (0);
 367             }
 368         }
 369       /* Out of space in this bucket, split the bucket... */
 370     }
 371   else                          /* delete case */
 372     {
 373       for (i = 0; i < limit; i++)
 374         {
 375           /* Found the key? Kill it... */
 376           if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
 377             {
 378               memset (&(v->kvp[i]), 0xff, sizeof (*(add_v)));
 379               /* Is the bucket empty? */
 380               if (PREDICT_TRUE (b->refcnt > 1))
 381                 {
 382                   b->refcnt--;
 383                   BV (clib_bihash_unlock_bucket) (b);
 384                   return (0);
 385                 }
 386               else              /* yes, free it */
 387                 {
 388                   /* Save old bucket value, need log2_pages to free it */
 389                   tmp_b.as_u64 = b->as_u64;
 390                   CLIB_MEMORY_BARRIER ();
 391
 392                   /* Kill and unlock the bucket */
 393                   b->as_u64 = 0;
 394
 395                   /* And free the backing storage */
 396                   BV (clib_bihash_alloc_lock) (h);
 397                   /* Note: v currently points into the middle of the bucket */
 398                   v = BV (clib_bihash_get_value) (h, tmp_b.offset);
 399                   BV (value_free) (h, v, tmp_b.log2_pages);
 400                   BV (clib_bihash_alloc_unlock) (h);
 401                   return (0);
 402                 }
 403             }
 404         }
 405       /* Not found... */
 406       BV (clib_bihash_unlock_bucket) (b);
 407       return (-3);
 408     }
 409
 410   /* Move readers to a (locked) temp copy of the bucket */
 411   BV (clib_bihash_alloc_lock) (h);
 412   BV (make_working_copy) (h, b);
 413
 414   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
 415
 416   old_log2_pages = h->saved_bucket.log2_pages;
 417   new_log2_pages = old_log2_pages + 1;
 418   mark_bucket_linear = 0;
 419
 420   working_copy = h->working_copies[thread_index];
 421   resplit_once = 0;
 422
 423   new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
 424                                  new_log2_pages);
 425   if (new_v == 0)
 426     {
 427     try_resplit:
 428       resplit_once = 1;
 429       new_log2_pages++;
 430       /* Try re-splitting. If that fails, fall back to linear search */
 431       new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
 432                                      new_log2_pages);
 433       if (new_v == 0)
 434         {
 435         mark_linear:
 436           new_log2_pages--;
 437           /* pinned collisions, use linear search */
 438           new_v =
 439             BV (split_and_rehash_linear) (h, working_copy, old_log2_pages,
 440                                           new_log2_pages);
 441           mark_bucket_linear = 1;
 442         }
 443     }
 444
 445   /* Try to add the new entry */
 446   save_new_v = new_v;
 447   new_hash = BV (clib_bihash_hash) (add_v);
 448   limit = BIHASH_KVP_PER_PAGE;
 449   if (mark_bucket_linear)
 450     limit <<= new_log2_pages;
 451   new_hash >>= h->log2_nbuckets;
 452   new_hash &= (1 << new_log2_pages) - 1;
 453   new_v += mark_bucket_linear ? 0 : new_hash;
 454
 455   for (i = 0; i < limit; i++)
 456     {
 457       if (BV (clib_bihash_is_free) (&(new_v->kvp[i])))
 458         {
 459           clib_memcpy (&(new_v->kvp[i]), add_v, sizeof (*add_v));
 460           goto expand_ok;
 461         }
 462     }
 463
 464   /* Crap. Try again */
 465   BV (value_free) (h, save_new_v, new_log2_pages);
 466   /*
 467    * If we've already doubled the size of the bucket once,
 468    * fall back to linear search now.
 469    */
 470   if (resplit_once)
 471     goto mark_linear;
 472   else
 473     goto try_resplit;
 474
 475 expand_ok:
 476   tmp_b.log2_pages = new_log2_pages;
 477   tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
 478   tmp_b.linear_search = mark_bucket_linear;
 479   tmp_b.refcnt = h->saved_bucket.refcnt + 1;
 480   tmp_b.lock = 0;
 481   CLIB_MEMORY_BARRIER ();
 482   b->as_u64 = tmp_b.as_u64;
 483   BV (clib_bihash_alloc_unlock) (h);
 484   return (0);
 485 }
 486
 487 int BV (clib_bihash_search)
 488   (BVT (clib_bihash) * h,
 489    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
 490 {
 491   u64 hash;
 492   u32 bucket_index;
 493   BVT (clib_bihash_value) * v;
 494   BVT (clib_bihash_bucket) * b;
 495   int i, limit;
 496
 497   ASSERT (valuep);
 498
 499   hash = BV (clib_bihash_hash) (search_key);
 500
 501   bucket_index = hash & (h->nbuckets - 1);
 502   b = &h->buckets[bucket_index];
 503
 504   if (BV (clib_bihash_bucket_is_empty) (b))
 505     return -1;
 506
 507   if (PREDICT_FALSE (b->lock))
 508     {
 509       volatile BVT (clib_bihash_bucket) * bv = b;
 510       while (bv->lock)
 511         CLIB_PAUSE ();
 512     }
 513
 514   hash >>= h->log2_nbuckets;
 515
 516   v = BV (clib_bihash_get_value) (h, b->offset);
 517   limit = BIHASH_KVP_PER_PAGE;
 518   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 519   if (PREDICT_FALSE (b->linear_search))
 520     limit <<= b->log2_pages;
 521
 522   for (i = 0; i < limit; i++)
 523     {
 524       if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
 525         {
 526           *valuep = v->kvp[i];
 527           return 0;
 528         }
 529     }
 530   return -1;
 531 }
 532
 533 u8 *BV (format_bihash) (u8 * s, va_list * args)
 534 {
 535   BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *);
 536   int verbose = va_arg (*args, int);
 537   BVT (clib_bihash_bucket) * b;
 538   BVT (clib_bihash_value) * v;
 539   int i, j, k;
 540   u64 active_elements = 0;
 541   u64 active_buckets = 0;
 542   u64 linear_buckets = 0;
 543   u64 used_bytes;
 544
 545   s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)");
 546
 547   for (i = 0; i < h->nbuckets; i++)
 548     {
 549       b = &h->buckets[i];
 550       if (BV (clib_bihash_bucket_is_empty) (b))
 551         {
 552           if (verbose > 1)
 553             s = format (s, "[%d]: empty\n", i);
 554           continue;
 555         }
 556
 557       active_buckets++;
 558
 559       if (b->linear_search)
 560         linear_buckets++;
 561
 562       if (verbose)
 563         {
 564           s = format (s, "[%d]: heap offset %d, len %d, linear %d\n", i,
 565                       b->offset, (1 << b->log2_pages), b->linear_search);
 566         }
 567
 568       v = BV (clib_bihash_get_value) (h, b->offset);
 569       for (j = 0; j < (1 << b->log2_pages); j++)
 570         {
 571           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
 572             {
 573               if (BV (clib_bihash_is_free) (&v->kvp[k]))
 574                 {
 575                   if (verbose > 1)
 576                     s = format (s, "    %d: empty\n",
 577                                 j * BIHASH_KVP_PER_PAGE + k);
 578                   continue;
 579                 }
 580               if (verbose)
 581                 {
 582                   if (h->fmt_fn)
 583                     {
 584                       s = format (s, "    %d: %U\n",
 585                                   j * BIHASH_KVP_PER_PAGE + k,
 586                                   h->fmt_fn, &(v->kvp[k]));
 587                     }
 588                   else
 589                     {
 590                       s = format (s, "    %d: %U\n",
 591                                   j * BIHASH_KVP_PER_PAGE + k,
 592                                   BV (format_bihash_kvp), &(v->kvp[k]));
 593                     }
 594                 }
 595               active_elements++;
 596             }
 597           v++;
 598         }
 599     }
 600
 601   s = format (s, "    %lld active elements %lld active buckets\n",
 602               active_elements, active_buckets);
 603   s = format (s, "    %d free lists\n", vec_len (h->freelists));
 604
 605   for (i = 0; i < vec_len (h->freelists); i++)
 606     {
 607       u32 nfree = 0;
 608       BVT (clib_bihash_value) * free_elt;
 609
 610       free_elt = h->freelists[i];
 611       while (free_elt)
 612         {
 613           nfree++;
 614           free_elt = free_elt->next_free;
 615         }
 616
 617       s = format (s, "       [len %d] %u free elts\n", 1 << i, nfree);
 618     }
 619
 620   s = format (s, "    %lld linear search buckets\n", linear_buckets);
 621   s = format (s, "    %lld cache hits, %lld cache misses\n",
 622               h->cache_hits, h->cache_misses);
 623   used_bytes = h->alloc_arena_next - h->alloc_arena;
 624   s = format (s,
 625               "    arena: base %llx, next %llx\n"
 626               "           used %lld b (%lld Mbytes) of %lld b (%lld Mbytes)\n",
 627               h->alloc_arena, h->alloc_arena_next,
 628               used_bytes, used_bytes >> 20,
 629               h->alloc_arena_size, h->alloc_arena_size >> 20);
 630   return s;
 631 }
 632
 633 void BV (clib_bihash_foreach_key_value_pair)
 634   (BVT (clib_bihash) * h, void *callback, void *arg)
 635 {
 636   int i, j, k;
 637   BVT (clib_bihash_bucket) * b;
 638   BVT (clib_bihash_value) * v;
 639   void (*fp) (BVT (clib_bihash_kv) *, void *) = callback;
 640
 641   for (i = 0; i < h->nbuckets; i++)
 642     {
 643       b = &h->buckets[i];
 644       if (BV (clib_bihash_bucket_is_empty) (b))
 645         continue;
 646
 647       v = BV (clib_bihash_get_value) (h, b->offset);
 648       for (j = 0; j < (1 << b->log2_pages); j++)
 649         {
 650           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
 651             {
 652               if (BV (clib_bihash_is_free) (&v->kvp[k]))
 653                 continue;
 654
 655               (*fp) (&v->kvp[k], arg);
 656             }
 657           v++;
 658         }
 659     }
 660 }
 661
 662 /** @endcond */
 663
 664 /*
 665  * fd.io coding-style-patch-verification: ON
 666  *
 667  * Local Variables:
 668  * eval: (c-set-style "gnu")
 669  * End:
 670  */