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