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