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