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