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   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   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     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 (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 (&(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 (&(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 (&(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 (&(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 (&(v->kvp[i]), &add_v->key, sizeof (add_v->key));
 495               b->refcnt++;
 496               ASSERT (b->refcnt > 0);
 497               BV (clib_bihash_unlock_bucket) (b);
 498               return (0);
 499             }
 500         }
 501       /* look for stale data to overwrite */
 502       if (is_stale_cb)
 503         {
 504           for (i = 0; i < limit; i++)
 505             {
 506               if (is_stale_cb (&(v->kvp[i]), arg))
 507                 {
 508                   CLIB_MEMORY_BARRIER ();
 509                   clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
 510                   BV (clib_bihash_unlock_bucket) (b);
 511                   return (0);
 512                 }
 513             }
 514         }
 515       /* Out of space in this bucket, split the bucket... */
 516     }
 517   else                          /* delete case */
 518     {
 519       for (i = 0; i < limit; i++)
 520         {
 521           /* Found the key? Kill it... */
 522           if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
 523             {
 524               memset (&(v->kvp[i]), 0xff, sizeof (*(add_v)));
 525               /* Is the bucket empty? */
 526               if (PREDICT_TRUE (b->refcnt > 1))
 527                 {
 528                   b->refcnt--;
 529                   BV (clib_bihash_unlock_bucket) (b);
 530                   return (0);
 531                 }
 532               else              /* yes, free it */
 533                 {
 534                   /* Save old bucket value, need log2_pages to free it */
 535                   tmp_b.as_u64 = b->as_u64;
 536                   CLIB_MEMORY_BARRIER ();
 537
 538                   /* Kill and unlock the bucket */
 539                   b->as_u64 = 0;
 540
 541                   /* And free the backing storage */
 542                   BV (clib_bihash_alloc_lock) (h);
 543                   /* Note: v currently points into the middle of the bucket */
 544                   v = BV (clib_bihash_get_value) (h, tmp_b.offset);
 545                   BV (value_free) (h, v, tmp_b.log2_pages);
 546                   BV (clib_bihash_alloc_unlock) (h);
 547                   return (0);
 548                 }
 549             }
 550         }
 551       /* Not found... */
 552       BV (clib_bihash_unlock_bucket) (b);
 553       return (-3);
 554     }
 555
 556   /* Move readers to a (locked) temp copy of the bucket */
 557   BV (clib_bihash_alloc_lock) (h);
 558   BV (make_working_copy) (h, b);
 559
 560   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
 561
 562   old_log2_pages = h->saved_bucket.log2_pages;
 563   new_log2_pages = old_log2_pages + 1;
 564   mark_bucket_linear = 0;
 565
 566   working_copy = h->working_copies[thread_index];
 567   resplit_once = 0;
 568
 569   new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
 570                                  new_log2_pages);
 571   if (new_v == 0)
 572     {
 573     try_resplit:
 574       resplit_once = 1;
 575       new_log2_pages++;
 576       /* Try re-splitting. If that fails, fall back to linear search */
 577       new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
 578                                      new_log2_pages);
 579       if (new_v == 0)
 580         {
 581         mark_linear:
 582           new_log2_pages--;
 583           /* pinned collisions, use linear search */
 584           new_v =
 585             BV (split_and_rehash_linear) (h, working_copy, old_log2_pages,
 586                                           new_log2_pages);
 587           mark_bucket_linear = 1;
 588         }
 589     }
 590
 591   /* Try to add the new entry */
 592   save_new_v = new_v;
 593   new_hash = BV (clib_bihash_hash) (add_v);
 594   limit = BIHASH_KVP_PER_PAGE;
 595   if (mark_bucket_linear)
 596     limit <<= new_log2_pages;
 597   new_hash >>= h->log2_nbuckets;
 598   new_hash &= (1 << new_log2_pages) - 1;
 599   new_v += mark_bucket_linear ? 0 : new_hash;
 600
 601   for (i = 0; i < limit; i++)
 602     {
 603       if (BV (clib_bihash_is_free) (&(new_v->kvp[i])))
 604         {
 605           clib_memcpy (&(new_v->kvp[i]), add_v, sizeof (*add_v));
 606           goto expand_ok;
 607         }
 608     }
 609
 610   /* Crap. Try again */
 611   BV (value_free) (h, save_new_v, new_log2_pages);
 612   /*
 613    * If we've already doubled the size of the bucket once,
 614    * fall back to linear search now.
 615    */
 616   if (resplit_once)
 617     goto mark_linear;
 618   else
 619     goto try_resplit;
 620
 621 expand_ok:
 622   tmp_b.log2_pages = new_log2_pages;
 623   tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
 624   tmp_b.linear_search = mark_bucket_linear;
 625   tmp_b.refcnt = h->saved_bucket.refcnt + 1;
 626   ASSERT (tmp_b.refcnt > 0);
 627   tmp_b.lock = 0;
 628   CLIB_MEMORY_BARRIER ();
 629   b->as_u64 = tmp_b.as_u64;
 630   /* free the old bucket */
 631   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
 632   BV (value_free) (h, v, h->saved_bucket.log2_pages);
 633   BV (clib_bihash_alloc_unlock) (h);
 634   return (0);
 635 }
 636
 637 int BV (clib_bihash_add_del)
 638   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
 639 {
 640   return BV (clib_bihash_add_del_inline) (h, add_v, is_add, 0, 0);
 641 }
 642
 643 int BV (clib_bihash_add_or_overwrite_stale)
 644   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
 645    int (*stale_callback) (BVT (clib_bihash_kv) *, void *), void *arg)
 646 {
 647   return BV (clib_bihash_add_del_inline) (h, add_v, 1, stale_callback, arg);
 648 }
 649
 650 int BV (clib_bihash_search)
 651   (BVT (clib_bihash) * h,
 652    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
 653 {
 654   u64 hash;
 655   u32 bucket_index;
 656   BVT (clib_bihash_value) * v;
 657   BVT (clib_bihash_bucket) * b;
 658   int i, limit;
 659
 660   ASSERT (valuep);
 661
 662   hash = BV (clib_bihash_hash) (search_key);
 663
 664   bucket_index = hash & (h->nbuckets - 1);
 665   b = &h->buckets[bucket_index];
 666
 667   if (BV (clib_bihash_bucket_is_empty) (b))
 668     return -1;
 669
 670   if (PREDICT_FALSE (b->lock))
 671     {
 672       volatile BVT (clib_bihash_bucket) * bv = b;
 673       while (bv->lock)
 674         CLIB_PAUSE ();
 675     }
 676
 677   hash >>= h->log2_nbuckets;
 678
 679   v = BV (clib_bihash_get_value) (h, b->offset);
 680   limit = BIHASH_KVP_PER_PAGE;
 681   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 682   if (PREDICT_FALSE (b->linear_search))
 683     limit <<= b->log2_pages;
 684
 685   for (i = 0; i < limit; i++)
 686     {
 687       if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
 688         {
 689           *valuep = v->kvp[i];
 690           return 0;
 691         }
 692     }
 693   return -1;
 694 }
 695
 696 u8 *BV (format_bihash) (u8 * s, va_list * args)
 697 {
 698   BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *);
 699   int verbose = va_arg (*args, int);
 700   BVT (clib_bihash_bucket) * b;
 701   BVT (clib_bihash_value) * v;
 702   int i, j, k;
 703   u64 active_elements = 0;
 704   u64 active_buckets = 0;
 705   u64 linear_buckets = 0;
 706   u64 used_bytes;
 707
 708   s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)");
 709
 710   for (i = 0; i < h->nbuckets; i++)
 711     {
 712       b = &h->buckets[i];
 713       if (BV (clib_bihash_bucket_is_empty) (b))
 714         {
 715           if (verbose > 1)
 716             s = format (s, "[%d]: empty\n", i);
 717           continue;
 718         }
 719
 720       active_buckets++;
 721
 722       if (b->linear_search)
 723         linear_buckets++;
 724
 725       if (verbose)
 726         {
 727           s = format (s, "[%d]: heap offset %lld, len %d, linear %d\n", i,
 728                       b->offset, (1 << b->log2_pages), b->linear_search);
 729         }
 730
 731       v = BV (clib_bihash_get_value) (h, b->offset);
 732       for (j = 0; j < (1 << b->log2_pages); j++)
 733         {
 734           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
 735             {
 736               if (BV (clib_bihash_is_free) (&v->kvp[k]))
 737                 {
 738                   if (verbose > 1)
 739                     s = format (s, "    %d: empty\n",
 740                                 j * BIHASH_KVP_PER_PAGE + k);
 741                   continue;
 742                 }
 743               if (verbose)
 744                 {
 745                   if (h->fmt_fn)
 746                     {
 747                       s = format (s, "    %d: %U\n",
 748                                   j * BIHASH_KVP_PER_PAGE + k,
 749                                   h->fmt_fn, &(v->kvp[k]));
 750                     }
 751                   else
 752                     {
 753                       s = format (s, "    %d: %U\n",
 754                                   j * BIHASH_KVP_PER_PAGE + k,
 755                                   BV (format_bihash_kvp), &(v->kvp[k]));
 756                     }
 757                 }
 758               active_elements++;
 759             }
 760           v++;
 761         }
 762     }
 763
 764   s = format (s, "    %lld active elements %lld active buckets\n",
 765               active_elements, active_buckets);
 766   s = format (s, "    %d free lists\n", vec_len (h->freelists));
 767
 768   for (i = 0; i < vec_len (h->freelists); i++)
 769     {
 770       u32 nfree = 0;
 771       BVT (clib_bihash_value) * free_elt;
 772       u64 free_elt_as_u64 = h->freelists[i];
 773
 774       while (free_elt_as_u64)
 775         {
 776           free_elt = BV (clib_bihash_get_value) (h, free_elt_as_u64);
 777           nfree++;
 778           free_elt_as_u64 = free_elt->next_free_as_u64;
 779         }
 780
 781       if (nfree || verbose)
 782         s = format (s, "       [len %d] %u free elts\n", 1 << i, nfree);
 783     }
 784
 785   s = format (s, "    %lld linear search buckets\n", linear_buckets);
 786   used_bytes = alloc_arena_next (h);
 787   s = format (s,
 788               "    arena: base %llx, next %llx\n"
 789               "           used %lld b (%lld Mbytes) of %lld b (%lld Mbytes)\n",
 790               alloc_arena (h), alloc_arena_next (h),
 791               used_bytes, used_bytes >> 20,
 792               alloc_arena_size (h), alloc_arena_size (h) >> 20);
 793   return s;
 794 }
 795
 796 void BV (clib_bihash_foreach_key_value_pair)
 797   (BVT (clib_bihash) * h, void *callback, void *arg)
 798 {
 799   int i, j, k;
 800   BVT (clib_bihash_bucket) * b;
 801   BVT (clib_bihash_value) * v;
 802   void (*fp) (BVT (clib_bihash_kv) *, void *) = callback;
 803
 804   for (i = 0; i < h->nbuckets; i++)
 805     {
 806       b = &h->buckets[i];
 807       if (BV (clib_bihash_bucket_is_empty) (b))
 808         continue;
 809
 810       v = BV (clib_bihash_get_value) (h, b->offset);
 811       for (j = 0; j < (1 << b->log2_pages); j++)
 812         {
 813           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
 814             {
 815               if (BV (clib_bihash_is_free) (&v->kvp[k]))
 816                 continue;
 817
 818               (*fp) (&v->kvp[k], arg);
 819               /*
 820                * In case the callback deletes the last entry in the bucket...
 821                */
 822               if (BV (clib_bihash_bucket_is_empty) (b))
 823                 goto doublebreak;
 824             }
 825           v++;
 826         }
 827     doublebreak:
 828       ;
 829     }
 830 }
 831
 832 /** @endcond */
 833
 834 /*
 835  * fd.io coding-style-patch-verification: ON
 836  *
 837  * Local Variables:
 838  * eval: (c-set-style "gnu")
 839  * End:
 840  */