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