src/vppinfra/bihash_template.c

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