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 static inline int BV (clib_bihash_add_del_inline)
 273   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add,
 274    int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg)
 275 {
 276   u32 bucket_index;
 277   BVT (clib_bihash_bucket) * b, tmp_b;
 278   BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy;
 279   int i, limit;
 280   u64 hash, new_hash;
 281   u32 new_log2_pages, old_log2_pages;
 282   u32 thread_index = os_get_thread_index ();
 283   int mark_bucket_linear;
 284   int resplit_once;
 285
 286   hash = BV (clib_bihash_hash) (add_v);
 287
 288   bucket_index = hash & (h->nbuckets - 1);
 289   b = &h->buckets[bucket_index];
 290
 291   hash >>= h->log2_nbuckets;
 292
 293   BV (clib_bihash_lock_bucket) (b);
 294
 295   /* First elt in the bucket? */
 296   if (BV (clib_bihash_bucket_is_empty) (b))
 297     {
 298       if (is_add == 0)
 299         {
 300           BV (clib_bihash_unlock_bucket) (b);
 301           return (-1);
 302         }
 303
 304       BV (clib_bihash_alloc_lock) (h);
 305       v = BV (value_alloc) (h, 0);
 306       BV (clib_bihash_alloc_unlock) (h);
 307
 308       *v->kvp = *add_v;
 309       tmp_b.as_u64 = 0;         /* clears bucket lock */
 310       tmp_b.offset = BV (clib_bihash_get_offset) (h, v);
 311       tmp_b.refcnt = 1;
 312       CLIB_MEMORY_BARRIER ();
 313
 314       b->as_u64 = tmp_b.as_u64;
 315       BV (clib_bihash_unlock_bucket) (b);
 316       return (0);
 317     }
 318
 319   /* WARNING: we're still looking at the live copy... */
 320   limit = BIHASH_KVP_PER_PAGE;
 321   v = BV (clib_bihash_get_value) (h, b->offset);
 322
 323   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 324   if (b->linear_search)
 325     limit <<= b->log2_pages;
 326
 327   if (is_add)
 328     {
 329       /*
 330        * Because reader threads are looking at live data,
 331        * we have to be extra careful. Readers do NOT hold the
 332        * bucket lock. We need to be SLOWER than a search, past the
 333        * point where readers CHECK the bucket lock.
 334        */
 335
 336       /*
 337        * For obvious (in hindsight) reasons, see if we're supposed to
 338        * replace an existing key, then look for an empty slot.
 339        */
 340       for (i = 0; i < limit; i++)
 341         {
 342           if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
 343             {
 344               CLIB_MEMORY_BARRIER ();   /* Add a delay */
 345               clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
 346               BV (clib_bihash_unlock_bucket) (b);
 347               return (0);
 348             }
 349         }
 350       /*
 351        * Look for an empty slot. If found, use it
 352        */
 353       for (i = 0; i < limit; i++)
 354         {
 355           if (BV (clib_bihash_is_free) (&(v->kvp[i])))
 356             {
 357               /*
 358                * Copy the value first, so that if a reader manages
 359                * to match the new key, the value will be right...
 360                */
 361               clib_memcpy (&(v->kvp[i].value),
 362                            &add_v->value, sizeof (add_v->value));
 363               CLIB_MEMORY_BARRIER ();   /* Make sure the value has settled */
 364               clib_memcpy (&(v->kvp[i]), &add_v->key, sizeof (add_v->key));
 365               b->refcnt++;
 366               BV (clib_bihash_unlock_bucket) (b);
 367               return (0);
 368             }
 369         }
 370       /* look for stale data to overwrite */
 371       if (is_stale_cb)
 372         {
 373           for (i = 0; i < limit; i++)
 374             {
 375               if (is_stale_cb (&(v->kvp[i]), arg))
 376                 {
 377                   CLIB_MEMORY_BARRIER ();
 378                   clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
 379                   BV (clib_bihash_unlock_bucket) (b);
 380                   return (0);
 381                 }
 382             }
 383         }
 384       /* Out of space in this bucket, split the bucket... */
 385     }
 386   else                          /* delete case */
 387     {
 388       for (i = 0; i < limit; i++)
 389         {
 390           /* Found the key? Kill it... */
 391           if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
 392             {
 393               memset (&(v->kvp[i]), 0xff, sizeof (*(add_v)));
 394               /* Is the bucket empty? */
 395               if (PREDICT_TRUE (b->refcnt > 1))
 396                 {
 397                   b->refcnt--;
 398                   BV (clib_bihash_unlock_bucket) (b);
 399                   return (0);
 400                 }
 401               else              /* yes, free it */
 402                 {
 403                   /* Save old bucket value, need log2_pages to free it */
 404                   tmp_b.as_u64 = b->as_u64;
 405                   CLIB_MEMORY_BARRIER ();
 406
 407                   /* Kill and unlock the bucket */
 408                   b->as_u64 = 0;
 409
 410                   /* And free the backing storage */
 411                   BV (clib_bihash_alloc_lock) (h);
 412                   /* Note: v currently points into the middle of the bucket */
 413                   v = BV (clib_bihash_get_value) (h, tmp_b.offset);
 414                   BV (value_free) (h, v, tmp_b.log2_pages);
 415                   BV (clib_bihash_alloc_unlock) (h);
 416                   return (0);
 417                 }
 418             }
 419         }
 420       /* Not found... */
 421       BV (clib_bihash_unlock_bucket) (b);
 422       return (-3);
 423     }
 424
 425   /* Move readers to a (locked) temp copy of the bucket */
 426   BV (clib_bihash_alloc_lock) (h);
 427   BV (make_working_copy) (h, b);
 428
 429   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
 430
 431   old_log2_pages = h->saved_bucket.log2_pages;
 432   new_log2_pages = old_log2_pages + 1;
 433   mark_bucket_linear = 0;
 434
 435   working_copy = h->working_copies[thread_index];
 436   resplit_once = 0;
 437
 438   new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
 439                                  new_log2_pages);
 440   if (new_v == 0)
 441     {
 442     try_resplit:
 443       resplit_once = 1;
 444       new_log2_pages++;
 445       /* Try re-splitting. If that fails, fall back to linear search */
 446       new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
 447                                      new_log2_pages);
 448       if (new_v == 0)
 449         {
 450         mark_linear:
 451           new_log2_pages--;
 452           /* pinned collisions, use linear search */
 453           new_v =
 454             BV (split_and_rehash_linear) (h, working_copy, old_log2_pages,
 455                                           new_log2_pages);
 456           mark_bucket_linear = 1;
 457         }
 458     }
 459
 460   /* Try to add the new entry */
 461   save_new_v = new_v;
 462   new_hash = BV (clib_bihash_hash) (add_v);
 463   limit = BIHASH_KVP_PER_PAGE;
 464   if (mark_bucket_linear)
 465     limit <<= new_log2_pages;
 466   new_hash >>= h->log2_nbuckets;
 467   new_hash &= (1 << new_log2_pages) - 1;
 468   new_v += mark_bucket_linear ? 0 : new_hash;
 469
 470   for (i = 0; i < limit; i++)
 471     {
 472       if (BV (clib_bihash_is_free) (&(new_v->kvp[i])))
 473         {
 474           clib_memcpy (&(new_v->kvp[i]), add_v, sizeof (*add_v));
 475           goto expand_ok;
 476         }
 477     }
 478
 479   /* Crap. Try again */
 480   BV (value_free) (h, save_new_v, new_log2_pages);
 481   /*
 482    * If we've already doubled the size of the bucket once,
 483    * fall back to linear search now.
 484    */
 485   if (resplit_once)
 486     goto mark_linear;
 487   else
 488     goto try_resplit;
 489
 490 expand_ok:
 491   tmp_b.log2_pages = new_log2_pages;
 492   tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
 493   tmp_b.linear_search = mark_bucket_linear;
 494   tmp_b.refcnt = h->saved_bucket.refcnt + 1;
 495   tmp_b.lock = 0;
 496   CLIB_MEMORY_BARRIER ();
 497   b->as_u64 = tmp_b.as_u64;
 498   BV (clib_bihash_alloc_unlock) (h);
 499   return (0);
 500 }
 501
 502 int BV (clib_bihash_add_del)
 503   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
 504 {
 505   return BV (clib_bihash_add_del_inline) (h, add_v, is_add, 0, 0);
 506 }
 507
 508 int BV (clib_bihash_add_or_overwrite_stale)
 509   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
 510    int (*stale_callback) (BVT (clib_bihash_kv) *, void *), void *arg)
 511 {
 512   return BV (clib_bihash_add_del_inline) (h, add_v, 1, stale_callback, arg);
 513 }
 514
 515 int BV (clib_bihash_search)
 516   (BVT (clib_bihash) * h,
 517    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
 518 {
 519   u64 hash;
 520   u32 bucket_index;
 521   BVT (clib_bihash_value) * v;
 522   BVT (clib_bihash_bucket) * b;
 523   int i, limit;
 524
 525   ASSERT (valuep);
 526
 527   hash = BV (clib_bihash_hash) (search_key);
 528
 529   bucket_index = hash & (h->nbuckets - 1);
 530   b = &h->buckets[bucket_index];
 531
 532   if (BV (clib_bihash_bucket_is_empty) (b))
 533     return -1;
 534
 535   if (PREDICT_FALSE (b->lock))
 536     {
 537       volatile BVT (clib_bihash_bucket) * bv = b;
 538       while (bv->lock)
 539         CLIB_PAUSE ();
 540     }
 541
 542   hash >>= h->log2_nbuckets;
 543
 544   v = BV (clib_bihash_get_value) (h, b->offset);
 545   limit = BIHASH_KVP_PER_PAGE;
 546   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 547   if (PREDICT_FALSE (b->linear_search))
 548     limit <<= b->log2_pages;
 549
 550   for (i = 0; i < limit; i++)
 551     {
 552       if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
 553         {
 554           *valuep = v->kvp[i];
 555           return 0;
 556         }
 557     }
 558   return -1;
 559 }
 560
 561 u8 *BV (format_bihash) (u8 * s, va_list * args)
 562 {
 563   BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *);
 564   int verbose = va_arg (*args, int);
 565   BVT (clib_bihash_bucket) * b;
 566   BVT (clib_bihash_value) * v;
 567   int i, j, k;
 568   u64 active_elements = 0;
 569   u64 active_buckets = 0;
 570   u64 linear_buckets = 0;
 571   u64 used_bytes;
 572
 573   s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)");
 574
 575   for (i = 0; i < h->nbuckets; i++)
 576     {
 577       b = &h->buckets[i];
 578       if (BV (clib_bihash_bucket_is_empty) (b))
 579         {
 580           if (verbose > 1)
 581             s = format (s, "[%d]: empty\n", i);
 582           continue;
 583         }
 584
 585       active_buckets++;
 586
 587       if (b->linear_search)
 588         linear_buckets++;
 589
 590       if (verbose)
 591         {
 592           s = format (s, "[%d]: heap offset %d, len %d, linear %d\n", i,
 593                       b->offset, (1 << b->log2_pages), b->linear_search);
 594         }
 595
 596       v = BV (clib_bihash_get_value) (h, b->offset);
 597       for (j = 0; j < (1 << b->log2_pages); j++)
 598         {
 599           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
 600             {
 601               if (BV (clib_bihash_is_free) (&v->kvp[k]))
 602                 {
 603                   if (verbose > 1)
 604                     s = format (s, "    %d: empty\n",
 605                                 j * BIHASH_KVP_PER_PAGE + k);
 606                   continue;
 607                 }
 608               if (verbose)
 609                 {
 610                   if (h->fmt_fn)
 611                     {
 612                       s = format (s, "    %d: %U\n",
 613                                   j * BIHASH_KVP_PER_PAGE + k,
 614                                   h->fmt_fn, &(v->kvp[k]));
 615                     }
 616                   else
 617                     {
 618                       s = format (s, "    %d: %U\n",
 619                                   j * BIHASH_KVP_PER_PAGE + k,
 620                                   BV (format_bihash_kvp), &(v->kvp[k]));
 621                     }
 622                 }
 623               active_elements++;
 624             }
 625           v++;
 626         }
 627     }
 628
 629   s = format (s, "    %lld active elements %lld active buckets\n",
 630               active_elements, active_buckets);
 631   s = format (s, "    %d free lists\n", vec_len (h->freelists));
 632
 633   for (i = 0; i < vec_len (h->freelists); i++)
 634     {
 635       u32 nfree = 0;
 636       BVT (clib_bihash_value) * free_elt;
 637
 638       free_elt = h->freelists[i];
 639       while (free_elt)
 640         {
 641           nfree++;
 642           free_elt = free_elt->next_free;
 643         }
 644
 645       s = format (s, "       [len %d] %u free elts\n", 1 << i, nfree);
 646     }
 647
 648   s = format (s, "    %lld linear search buckets\n", linear_buckets);
 649   s = format (s, "    %lld cache hits, %lld cache misses\n",
 650               h->cache_hits, h->cache_misses);
 651   used_bytes = h->alloc_arena_next - h->alloc_arena;
 652   s = format (s,
 653               "    arena: base %llx, next %llx\n"
 654               "           used %lld b (%lld Mbytes) of %lld b (%lld Mbytes)\n",
 655               h->alloc_arena, h->alloc_arena_next,
 656               used_bytes, used_bytes >> 20,
 657               h->alloc_arena_size, h->alloc_arena_size >> 20);
 658   return s;
 659 }
 660
 661 void BV (clib_bihash_foreach_key_value_pair)
 662   (BVT (clib_bihash) * h, void *callback, void *arg)
 663 {
 664   int i, j, k;
 665   BVT (clib_bihash_bucket) * b;
 666   BVT (clib_bihash_value) * v;
 667   void (*fp) (BVT (clib_bihash_kv) *, void *) = callback;
 668
 669   for (i = 0; i < h->nbuckets; i++)
 670     {
 671       b = &h->buckets[i];
 672       if (BV (clib_bihash_bucket_is_empty) (b))
 673         continue;
 674
 675       v = BV (clib_bihash_get_value) (h, b->offset);
 676       for (j = 0; j < (1 << b->log2_pages); j++)
 677         {
 678           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
 679             {
 680               if (BV (clib_bihash_is_free) (&v->kvp[k]))
 681                 continue;
 682
 683               (*fp) (&v->kvp[k], arg);
 684               /*
 685                * In case the callback deletes the last entry in the bucket...
 686                */
 687               if (BV (clib_bihash_bucket_is_empty) (b))
 688                 goto doublebreak;
 689             }
 690           v++;
 691         }
 692     doublebreak:
 693       ;
 694     }
 695 }
 696
 697 /** @endcond */
 698
 699 /*
 700  * fd.io coding-style-patch-verification: ON
 701  *
 702  * Local Variables:
 703  * eval: (c-set-style "gnu")
 704  * End:
 705  */