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   vec_free (h->working_copy_lengths);
 200 #if BIHASH_32_64_SVM == 0
 201   vec_free (h->freelists);
 202 #else
 203   if (h->memfd > 0)
 204     (void) close (h->memfd);
 205 #endif
 206   clib_mem_vm_free ((void *) (uword) (alloc_arena (h)), alloc_arena_size (h));
 207   clib_memset (h, 0, sizeof (*h));
 208 }
 209
 210 static
 211 BVT (clib_bihash_value) *
 212 BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages)
 213 {
 214   BVT (clib_bihash_value) * rv = 0;
 215
 216   ASSERT (h->alloc_lock[0]);
 217
 218 #if BIHASH_32_64_SVM
 219   ASSERT (log2_pages < vec_len (h->freelists));
 220 #endif
 221
 222   if (log2_pages >= vec_len (h->freelists) || h->freelists[log2_pages] == 0)
 223     {
 224       vec_validate_init_empty (h->freelists, log2_pages, 0);
 225       rv = BV (alloc_aligned) (h, (sizeof (*rv) * (1 << log2_pages)));
 226       goto initialize;
 227     }
 228   rv = BV (clib_bihash_get_value) (h, (uword) h->freelists[log2_pages]);
 229   h->freelists[log2_pages] = rv->next_free_as_u64;
 230
 231 initialize:
 232   ASSERT (rv);
 233   /*
 234    * Latest gcc complains that the length arg is zero
 235    * if we replace (1<<log2_pages) with vec_len(rv).
 236    * No clue.
 237    */
 238   clib_memset (rv, 0xff, sizeof (*rv) * (1 << log2_pages));
 239   return rv;
 240 }
 241
 242 static void
 243 BV (value_free) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * v,
 244                  u32 log2_pages)
 245 {
 246   ASSERT (h->alloc_lock[0]);
 247
 248   ASSERT (vec_len (h->freelists) > log2_pages);
 249
 250   if (CLIB_DEBUG > 0)
 251     clib_memset (v, 0xFE, sizeof (*v) * (1 << log2_pages));
 252
 253   v->next_free_as_u64 = (u64) h->freelists[log2_pages];
 254   h->freelists[log2_pages] = (u64) BV (clib_bihash_get_offset) (h, v);
 255 }
 256
 257 static inline void
 258 BV (make_working_copy) (BVT (clib_bihash) * h, BVT (clib_bihash_bucket) * b)
 259 {
 260   BVT (clib_bihash_value) * v;
 261   BVT (clib_bihash_bucket) working_bucket __attribute__ ((aligned (8)));
 262   BVT (clib_bihash_value) * working_copy;
 263   u32 thread_index = os_get_thread_index ();
 264   int log2_working_copy_length;
 265
 266   ASSERT (h->alloc_lock[0]);
 267
 268   if (thread_index >= vec_len (h->working_copies))
 269     {
 270       vec_validate (h->working_copies, thread_index);
 271       vec_validate_init_empty (h->working_copy_lengths, thread_index, ~0);
 272     }
 273
 274   /*
 275    * working_copies are per-cpu so that near-simultaneous
 276    * updates from multiple threads will not result in sporadic, spurious
 277    * lookup failures.
 278    */
 279   working_copy = h->working_copies[thread_index];
 280   log2_working_copy_length = h->working_copy_lengths[thread_index];
 281
 282   h->saved_bucket.as_u64 = b->as_u64;
 283
 284   if (b->log2_pages > log2_working_copy_length)
 285     {
 286       /*
 287        * It's not worth the bookkeeping to free working copies
 288        *   if (working_copy)
 289        *     clib_mem_free (working_copy);
 290        */
 291       working_copy = BV (alloc_aligned)
 292         (h, sizeof (working_copy[0]) * (1 << b->log2_pages));
 293       h->working_copy_lengths[thread_index] = b->log2_pages;
 294       h->working_copies[thread_index] = working_copy;
 295
 296       BV (clib_bihash_increment_stat) (h, BIHASH_STAT_working_copy_lost,
 297                                        1ULL << b->log2_pages);
 298     }
 299
 300   v = BV (clib_bihash_get_value) (h, b->offset);
 301
 302   clib_memcpy_fast (working_copy, v, sizeof (*v) * (1 << b->log2_pages));
 303   working_bucket.as_u64 = b->as_u64;
 304   working_bucket.offset = BV (clib_bihash_get_offset) (h, working_copy);
 305   CLIB_MEMORY_BARRIER ();
 306   b->as_u64 = working_bucket.as_u64;
 307   h->working_copies[thread_index] = working_copy;
 308 }
 309
 310 static
 311 BVT (clib_bihash_value) *
 312 BV (split_and_rehash)
 313   (BVT (clib_bihash) * h,
 314    BVT (clib_bihash_value) * old_values, u32 old_log2_pages,
 315    u32 new_log2_pages)
 316 {
 317   BVT (clib_bihash_value) * new_values, *new_v;
 318   int i, j, length_in_kvs;
 319
 320   ASSERT (h->alloc_lock[0]);
 321
 322   new_values = BV (value_alloc) (h, new_log2_pages);
 323   length_in_kvs = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE;
 324
 325   for (i = 0; i < length_in_kvs; i++)
 326     {
 327       u64 new_hash;
 328
 329       /* Entry not in use? Forget it */
 330       if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
 331         continue;
 332
 333       /* rehash the item onto its new home-page */
 334       new_hash = BV (clib_bihash_hash) (&(old_values->kvp[i]));
 335       new_hash >>= h->log2_nbuckets;
 336       new_hash &= (1 << new_log2_pages) - 1;
 337       new_v = &new_values[new_hash];
 338
 339       /* Across the new home-page */
 340       for (j = 0; j < BIHASH_KVP_PER_PAGE; j++)
 341         {
 342           /* Empty slot */
 343           if (BV (clib_bihash_is_free) (&(new_v->kvp[j])))
 344             {
 345               clib_memcpy_fast (&(new_v->kvp[j]), &(old_values->kvp[i]),
 346                                 sizeof (new_v->kvp[j]));
 347               goto doublebreak;
 348             }
 349         }
 350       /* Crap. Tell caller to try again */
 351       BV (value_free) (h, new_values, new_log2_pages);
 352       return 0;
 353     doublebreak:;
 354     }
 355
 356   return new_values;
 357 }
 358
 359 static
 360 BVT (clib_bihash_value) *
 361 BV (split_and_rehash_linear)
 362   (BVT (clib_bihash) * h,
 363    BVT (clib_bihash_value) * old_values, u32 old_log2_pages,
 364    u32 new_log2_pages)
 365 {
 366   BVT (clib_bihash_value) * new_values;
 367   int i, j, new_length, old_length;
 368
 369   ASSERT (h->alloc_lock[0]);
 370
 371   new_values = BV (value_alloc) (h, new_log2_pages);
 372   new_length = (1 << new_log2_pages) * BIHASH_KVP_PER_PAGE;
 373   old_length = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE;
 374
 375   j = 0;
 376   /* Across the old value array */
 377   for (i = 0; i < old_length; i++)
 378     {
 379       /* Find a free slot in the new linear scan bucket */
 380       for (; j < new_length; j++)
 381         {
 382           /* Old value not in use? Forget it. */
 383           if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
 384             goto doublebreak;
 385
 386           /* New value should never be in use */
 387           if (BV (clib_bihash_is_free) (&(new_values->kvp[j])))
 388             {
 389               /* Copy the old value and move along */
 390               clib_memcpy_fast (&(new_values->kvp[j]), &(old_values->kvp[i]),
 391                                 sizeof (new_values->kvp[j]));
 392               j++;
 393               goto doublebreak;
 394             }
 395         }
 396       /* This should never happen... */
 397       clib_warning ("BUG: linear rehash failed!");
 398       BV (value_free) (h, new_values, new_log2_pages);
 399       return 0;
 400
 401     doublebreak:;
 402     }
 403   return new_values;
 404 }
 405
 406 static inline int BV (clib_bihash_add_del_inline)
 407   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add,
 408    int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg)
 409 {
 410   u32 bucket_index;
 411   BVT (clib_bihash_bucket) * b, tmp_b;
 412   BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy;
 413   int i, limit;
 414   u64 hash, new_hash;
 415   u32 new_log2_pages, old_log2_pages;
 416   u32 thread_index = os_get_thread_index ();
 417   int mark_bucket_linear;
 418   int resplit_once;
 419
 420   hash = BV (clib_bihash_hash) (add_v);
 421
 422   bucket_index = hash & (h->nbuckets - 1);
 423   b = &h->buckets[bucket_index];
 424
 425   hash >>= h->log2_nbuckets;
 426
 427   BV (clib_bihash_lock_bucket) (b);
 428
 429   /* First elt in the bucket? */
 430   if (BV (clib_bihash_bucket_is_empty) (b))
 431     {
 432       if (is_add == 0)
 433         {
 434           BV (clib_bihash_unlock_bucket) (b);
 435           return (-1);
 436         }
 437
 438       BV (clib_bihash_alloc_lock) (h);
 439       v = BV (value_alloc) (h, 0);
 440       BV (clib_bihash_alloc_unlock) (h);
 441
 442       *v->kvp = *add_v;
 443       tmp_b.as_u64 = 0;         /* clears bucket lock */
 444       tmp_b.offset = BV (clib_bihash_get_offset) (h, v);
 445       tmp_b.refcnt = 1;
 446       CLIB_MEMORY_BARRIER ();
 447
 448       b->as_u64 = tmp_b.as_u64; /* unlocks the bucket */
 449       BV (clib_bihash_increment_stat) (h, BIHASH_STAT_alloc_add, 1);
 450
 451       return (0);
 452     }
 453
 454   /* WARNING: we're still looking at the live copy... */
 455   limit = BIHASH_KVP_PER_PAGE;
 456   v = BV (clib_bihash_get_value) (h, b->offset);
 457
 458   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 459   if (b->linear_search)
 460     limit <<= b->log2_pages;
 461
 462   if (is_add)
 463     {
 464       /*
 465        * Because reader threads are looking at live data,
 466        * we have to be extra careful. Readers do NOT hold the
 467        * bucket lock. We need to be SLOWER than a search, past the
 468        * point where readers CHECK the bucket lock.
 469        */
 470
 471       /*
 472        * For obvious (in hindsight) reasons, see if we're supposed to
 473        * replace an existing key, then look for an empty slot.
 474        */
 475       for (i = 0; i < limit; i++)
 476         {
 477           if (BV (clib_bihash_key_compare) (v->kvp[i].key, add_v->key))
 478             {
 479               CLIB_MEMORY_BARRIER ();   /* Add a delay */
 480               clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v));
 481               BV (clib_bihash_unlock_bucket) (b);
 482               BV (clib_bihash_increment_stat) (h, BIHASH_STAT_replace, 1);
 483               return (0);
 484             }
 485         }
 486       /*
 487        * Look for an empty slot. If found, use it
 488        */
 489       for (i = 0; i < limit; i++)
 490         {
 491           if (BV (clib_bihash_is_free) (&(v->kvp[i])))
 492             {
 493               /*
 494                * Copy the value first, so that if a reader manages
 495                * to match the new key, the value will be right...
 496                */
 497               clib_memcpy_fast (&(v->kvp[i].value),
 498                                 &add_v->value, sizeof (add_v->value));
 499               CLIB_MEMORY_BARRIER ();   /* Make sure the value has settled */
 500               clib_memcpy_fast (&(v->kvp[i]), &add_v->key,
 501                                 sizeof (add_v->key));
 502               b->refcnt++;
 503               ASSERT (b->refcnt > 0);
 504               BV (clib_bihash_unlock_bucket) (b);
 505               BV (clib_bihash_increment_stat) (h, BIHASH_STAT_add, 1);
 506               return (0);
 507             }
 508         }
 509       /* look for stale data to overwrite */
 510       if (is_stale_cb)
 511         {
 512           for (i = 0; i < limit; i++)
 513             {
 514               if (is_stale_cb (&(v->kvp[i]), arg))
 515                 {
 516                   CLIB_MEMORY_BARRIER ();
 517                   clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v));
 518                   BV (clib_bihash_unlock_bucket) (b);
 519                   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_replace, 1);
 520                   return (0);
 521                 }
 522             }
 523         }
 524       /* Out of space in this bucket, split the bucket... */
 525     }
 526   else                          /* delete case */
 527     {
 528       for (i = 0; i < limit; i++)
 529         {
 530           /* Found the key? Kill it... */
 531           if (BV (clib_bihash_key_compare) (v->kvp[i].key, add_v->key))
 532             {
 533               clib_memset (&(v->kvp[i]), 0xff, sizeof (*(add_v)));
 534               /* Is the bucket empty? */
 535               if (PREDICT_TRUE (b->refcnt > 1))
 536                 {
 537                   b->refcnt--;
 538                   BV (clib_bihash_unlock_bucket) (b);
 539                   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del, 1);
 540                   return (0);
 541                 }
 542               else              /* yes, free it */
 543                 {
 544                   /* Save old bucket value, need log2_pages to free it */
 545                   tmp_b.as_u64 = b->as_u64;
 546                   CLIB_MEMORY_BARRIER ();
 547
 548                   /* Kill and unlock the bucket */
 549                   b->as_u64 = 0;
 550
 551                   /* And free the backing storage */
 552                   BV (clib_bihash_alloc_lock) (h);
 553                   /* Note: v currently points into the middle of the bucket */
 554                   v = BV (clib_bihash_get_value) (h, tmp_b.offset);
 555                   BV (value_free) (h, v, tmp_b.log2_pages);
 556                   BV (clib_bihash_alloc_unlock) (h);
 557                   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del_free,
 558                                                    1);
 559                   return (0);
 560                 }
 561             }
 562         }
 563       /* Not found... */
 564       BV (clib_bihash_unlock_bucket) (b);
 565       return (-3);
 566     }
 567
 568   /* Move readers to a (locked) temp copy of the bucket */
 569   BV (clib_bihash_alloc_lock) (h);
 570   BV (make_working_copy) (h, b);
 571
 572   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
 573
 574   old_log2_pages = h->saved_bucket.log2_pages;
 575   new_log2_pages = old_log2_pages + 1;
 576   mark_bucket_linear = 0;
 577   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_split_add, 1);
 578   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits, old_log2_pages);
 579
 580   working_copy = h->working_copies[thread_index];
 581   resplit_once = 0;
 582   BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits, 1);
 583
 584   new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
 585                                  new_log2_pages);
 586   if (new_v == 0)
 587     {
 588     try_resplit:
 589       resplit_once = 1;
 590       new_log2_pages++;
 591       /* Try re-splitting. If that fails, fall back to linear search */
 592       new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
 593                                      new_log2_pages);
 594       if (new_v == 0)
 595         {
 596         mark_linear:
 597           new_log2_pages--;
 598           /* pinned collisions, use linear search */
 599           new_v =
 600             BV (split_and_rehash_linear) (h, working_copy, old_log2_pages,
 601                                           new_log2_pages);
 602           mark_bucket_linear = 1;
 603           BV (clib_bihash_increment_stat) (h, BIHASH_STAT_linear, 1);
 604         }
 605       BV (clib_bihash_increment_stat) (h, BIHASH_STAT_resplit, 1);
 606       BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits,
 607                                        old_log2_pages + 1);
 608     }
 609
 610   /* Try to add the new entry */
 611   save_new_v = new_v;
 612   new_hash = BV (clib_bihash_hash) (add_v);
 613   limit = BIHASH_KVP_PER_PAGE;
 614   if (mark_bucket_linear)
 615     limit <<= new_log2_pages;
 616   new_hash >>= h->log2_nbuckets;
 617   new_hash &= (1 << new_log2_pages) - 1;
 618   new_v += mark_bucket_linear ? 0 : new_hash;
 619
 620   for (i = 0; i < limit; i++)
 621     {
 622       if (BV (clib_bihash_is_free) (&(new_v->kvp[i])))
 623         {
 624           clib_memcpy_fast (&(new_v->kvp[i]), add_v, sizeof (*add_v));
 625           goto expand_ok;
 626         }
 627     }
 628
 629   /* Crap. Try again */
 630   BV (value_free) (h, save_new_v, new_log2_pages);
 631   /*
 632    * If we've already doubled the size of the bucket once,
 633    * fall back to linear search now.
 634    */
 635   if (resplit_once)
 636     goto mark_linear;
 637   else
 638     goto try_resplit;
 639
 640 expand_ok:
 641   tmp_b.log2_pages = new_log2_pages;
 642   tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
 643   tmp_b.linear_search = mark_bucket_linear;
 644   tmp_b.refcnt = h->saved_bucket.refcnt + 1;
 645   ASSERT (tmp_b.refcnt > 0);
 646   tmp_b.lock = 0;
 647   CLIB_MEMORY_BARRIER ();
 648   b->as_u64 = tmp_b.as_u64;
 649   /* free the old bucket */
 650   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
 651   BV (value_free) (h, v, h->saved_bucket.log2_pages);
 652   BV (clib_bihash_alloc_unlock) (h);
 653   return (0);
 654 }
 655
 656 int BV (clib_bihash_add_del)
 657   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
 658 {
 659   return BV (clib_bihash_add_del_inline) (h, add_v, is_add, 0, 0);
 660 }
 661
 662 int BV (clib_bihash_add_or_overwrite_stale)
 663   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v,
 664    int (*stale_callback) (BVT (clib_bihash_kv) *, void *), void *arg)
 665 {
 666   return BV (clib_bihash_add_del_inline) (h, add_v, 1, stale_callback, arg);
 667 }
 668
 669 int BV (clib_bihash_search)
 670   (BVT (clib_bihash) * h,
 671    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
 672 {
 673   u64 hash;
 674   u32 bucket_index;
 675   BVT (clib_bihash_value) * v;
 676   BVT (clib_bihash_bucket) * b;
 677   int i, limit;
 678
 679   ASSERT (valuep);
 680
 681   hash = BV (clib_bihash_hash) (search_key);
 682
 683   bucket_index = hash & (h->nbuckets - 1);
 684   b = &h->buckets[bucket_index];
 685
 686   if (BV (clib_bihash_bucket_is_empty) (b))
 687     return -1;
 688
 689   if (PREDICT_FALSE (b->lock))
 690     {
 691       volatile BVT (clib_bihash_bucket) * bv = b;
 692       while (bv->lock)
 693         CLIB_PAUSE ();
 694     }
 695
 696   hash >>= h->log2_nbuckets;
 697
 698   v = BV (clib_bihash_get_value) (h, b->offset);
 699   limit = BIHASH_KVP_PER_PAGE;
 700   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 701   if (PREDICT_FALSE (b->linear_search))
 702     limit <<= b->log2_pages;
 703
 704   for (i = 0; i < limit; i++)
 705     {
 706       if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
 707         {
 708           *valuep = v->kvp[i];
 709           return 0;
 710         }
 711     }
 712   return -1;
 713 }
 714
 715 u8 *BV (format_bihash) (u8 * s, va_list * args)
 716 {
 717   BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *);
 718   int verbose = va_arg (*args, int);
 719   BVT (clib_bihash_bucket) * b;
 720   BVT (clib_bihash_value) * v;
 721   int i, j, k;
 722   u64 active_elements = 0;
 723   u64 active_buckets = 0;
 724   u64 linear_buckets = 0;
 725   u64 used_bytes;
 726
 727   s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)");
 728
 729   for (i = 0; i < h->nbuckets; i++)
 730     {
 731       b = &h->buckets[i];
 732       if (BV (clib_bihash_bucket_is_empty) (b))
 733         {
 734           if (verbose > 1)
 735             s = format (s, "[%d]: empty\n", i);
 736           continue;
 737         }
 738
 739       active_buckets++;
 740
 741       if (b->linear_search)
 742         linear_buckets++;
 743
 744       if (verbose)
 745         {
 746           s = format (s, "[%d]: heap offset %lld, len %d, linear %d\n", i,
 747                       b->offset, (1 << b->log2_pages), b->linear_search);
 748         }
 749
 750       v = BV (clib_bihash_get_value) (h, b->offset);
 751       for (j = 0; j < (1 << b->log2_pages); j++)
 752         {
 753           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
 754             {
 755               if (BV (clib_bihash_is_free) (&v->kvp[k]))
 756                 {
 757                   if (verbose > 1)
 758                     s = format (s, "    %d: empty\n",
 759                                 j * BIHASH_KVP_PER_PAGE + k);
 760                   continue;
 761                 }
 762               if (verbose)
 763                 {
 764                   if (h->fmt_fn)
 765                     {
 766                       s = format (s, "    %d: %U\n",
 767                                   j * BIHASH_KVP_PER_PAGE + k,
 768                                   h->fmt_fn, &(v->kvp[k]), verbose);
 769                     }
 770                   else
 771                     {
 772                       s = format (s, "    %d: %U\n",
 773                                   j * BIHASH_KVP_PER_PAGE + k,
 774                                   BV (format_bihash_kvp), &(v->kvp[k]));
 775                     }
 776                 }
 777               active_elements++;
 778             }
 779           v++;
 780         }
 781     }
 782
 783   s = format (s, "    %lld active elements %lld active buckets\n",
 784               active_elements, active_buckets);
 785   s = format (s, "    %d free lists\n", vec_len (h->freelists));
 786
 787   for (i = 0; i < vec_len (h->freelists); i++)
 788     {
 789       u32 nfree = 0;
 790       BVT (clib_bihash_value) * free_elt;
 791       u64 free_elt_as_u64 = h->freelists[i];
 792
 793       while (free_elt_as_u64)
 794         {
 795           free_elt = BV (clib_bihash_get_value) (h, free_elt_as_u64);
 796           nfree++;
 797           free_elt_as_u64 = free_elt->next_free_as_u64;
 798         }
 799
 800       if (nfree || verbose)
 801         s = format (s, "       [len %d] %u free elts\n", 1 << i, nfree);
 802     }
 803
 804   s = format (s, "    %lld linear search buckets\n", linear_buckets);
 805   used_bytes = alloc_arena_next (h);
 806   s = format (s,
 807               "    arena: base %llx, next %llx\n"
 808               "           used %lld b (%lld Mbytes) of %lld b (%lld Mbytes)\n",
 809               alloc_arena (h), alloc_arena_next (h),
 810               used_bytes, used_bytes >> 20,
 811               alloc_arena_size (h), alloc_arena_size (h) >> 20);
 812   return s;
 813 }
 814
 815 void BV (clib_bihash_foreach_key_value_pair)
 816   (BVT (clib_bihash) * h, void *callback, void *arg)
 817 {
 818   int i, j, k;
 819   BVT (clib_bihash_bucket) * b;
 820   BVT (clib_bihash_value) * v;
 821   void (*fp) (BVT (clib_bihash_kv) *, void *) = callback;
 822
 823   for (i = 0; i < h->nbuckets; i++)
 824     {
 825       b = &h->buckets[i];
 826       if (BV (clib_bihash_bucket_is_empty) (b))
 827         continue;
 828
 829       v = BV (clib_bihash_get_value) (h, b->offset);
 830       for (j = 0; j < (1 << b->log2_pages); j++)
 831         {
 832           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
 833             {
 834               if (BV (clib_bihash_is_free) (&v->kvp[k]))
 835                 continue;
 836
 837               (*fp) (&v->kvp[k], arg);
 838               /*
 839                * In case the callback deletes the last entry in the bucket...
 840                */
 841               if (BV (clib_bihash_bucket_is_empty) (b))
 842                 goto doublebreak;
 843             }
 844           v++;
 845         }
 846     doublebreak:
 847       ;
 848     }
 849 }
 850
 851 /** @endcond */
 852
 853 /*
 854  * fd.io coding-style-patch-verification: ON
 855  *
 856  * Local Variables:
 857  * eval: (c-set-style "gnu")
 858  * End:
 859  */