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