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