src/vppinfra/bihash_template.c

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