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