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 void BV (clib_bihash_init)
  19   (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size)
  20 {
  21   void *oldheap;
  22
  23   nbuckets = 1 << (max_log2 (nbuckets));
  24
  25   h->name = (u8 *) name;
  26   h->nbuckets = nbuckets;
  27   h->log2_nbuckets = max_log2 (nbuckets);
  28
  29   h->mheap = mheap_alloc (0 /* use VM */ , memory_size);
  30
  31   oldheap = clib_mem_set_heap (h->mheap);
  32   vec_validate_aligned (h->buckets, nbuckets - 1, CLIB_CACHE_LINE_BYTES);
  33   h->writer_lock = clib_mem_alloc_aligned (CLIB_CACHE_LINE_BYTES,
  34                                            CLIB_CACHE_LINE_BYTES);
  35
  36   clib_mem_set_heap (oldheap);
  37 }
  38
  39 void BV (clib_bihash_free) (BVT (clib_bihash) * h)
  40 {
  41   mheap_free (h->mheap);
  42   memset (h, 0, sizeof (*h));
  43 }
  44
  45 static
  46 BVT (clib_bihash_value) *
  47 BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages)
  48 {
  49   BVT (clib_bihash_value) * rv = 0;
  50   void *oldheap;
  51
  52   ASSERT (h->writer_lock[0]);
  53   if (log2_pages >= vec_len (h->freelists) || h->freelists[log2_pages] == 0)
  54     {
  55       oldheap = clib_mem_set_heap (h->mheap);
  56
  57       vec_validate (h->freelists, log2_pages);
  58       vec_validate_aligned (rv, (1 << log2_pages) - 1, CLIB_CACHE_LINE_BYTES);
  59       clib_mem_set_heap (oldheap);
  60       goto initialize;
  61     }
  62   rv = h->freelists[log2_pages];
  63   h->freelists[log2_pages] = rv->next_free;
  64
  65 initialize:
  66   ASSERT (rv);
  67   ASSERT (vec_len (rv) == (1 << log2_pages));
  68   /*
  69    * Latest gcc complains that the length arg is zero
  70    * if we replace (1<<log2_pages) with vec_len(rv).
  71    * No clue.
  72    */
  73   memset (rv, 0xff, sizeof (*rv) * (1 << log2_pages));
  74   return rv;
  75 }
  76
  77 static void
  78 BV (value_free) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * v)
  79 {
  80   u32 log2_pages;
  81
  82   ASSERT (h->writer_lock[0]);
  83
  84   log2_pages = min_log2 (vec_len (v));
  85
  86   ASSERT (vec_len (h->freelists) > log2_pages);
  87
  88   v->next_free = h->freelists[log2_pages];
  89   h->freelists[log2_pages] = v;
  90 }
  91
  92 static inline void
  93 BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b)
  94 {
  95   BVT (clib_bihash_value) * v;
  96   clib_bihash_bucket_t working_bucket __attribute__ ((aligned (8)));
  97   void *oldheap;
  98   BVT (clib_bihash_value) * working_copy;
  99   u32 cpu_number = os_get_cpu_number ();
 100
 101   if (cpu_number >= vec_len (h->working_copies))
 102     {
 103       oldheap = clib_mem_set_heap (h->mheap);
 104       vec_validate (h->working_copies, cpu_number);
 105       clib_mem_set_heap (oldheap);
 106     }
 107
 108   /*
 109    * working_copies are per-cpu so that near-simultaneous
 110    * updates from multiple threads will not result in sporadic, spurious
 111    * lookup failures.
 112    */
 113   working_copy = h->working_copies[cpu_number];
 114
 115   h->saved_bucket.as_u64 = b->as_u64;
 116   oldheap = clib_mem_set_heap (h->mheap);
 117
 118   if ((1 << b->log2_pages) > vec_len (working_copy))
 119     {
 120       vec_validate_aligned (working_copy, (1 << b->log2_pages) - 1,
 121                             sizeof (u64));
 122       h->working_copies[cpu_number] = working_copy;
 123     }
 124
 125   _vec_len (working_copy) = 1 << b->log2_pages;
 126   clib_mem_set_heap (oldheap);
 127
 128   v = BV (clib_bihash_get_value) (h, b->offset);
 129
 130   clib_memcpy (working_copy, v, sizeof (*v) * (1 << b->log2_pages));
 131   working_bucket.as_u64 = b->as_u64;
 132   working_bucket.offset = BV (clib_bihash_get_offset) (h, working_copy);
 133   CLIB_MEMORY_BARRIER ();
 134   b->as_u64 = working_bucket.as_u64;
 135   h->working_copies[cpu_number] = working_copy;
 136 }
 137
 138 static
 139 BVT (clib_bihash_value) *
 140 BV (split_and_rehash)
 141   (BVT (clib_bihash) * h,
 142    BVT (clib_bihash_value) * old_values, u32 new_log2_pages)
 143 {
 144   BVT (clib_bihash_value) * new_values, *new_v;
 145   int i, j, length;
 146
 147   new_values = BV (value_alloc) (h, new_log2_pages);
 148   length = vec_len (old_values) * BIHASH_KVP_PER_PAGE;
 149
 150   for (i = 0; i < length; i++)
 151     {
 152       u64 new_hash;
 153
 154       /* Entry not in use? Forget it */
 155       if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
 156         continue;
 157
 158       /* rehash the item onto its new home-page */
 159       new_hash = BV (clib_bihash_hash) (&(old_values->kvp[i]));
 160       new_hash >>= h->log2_nbuckets;
 161       new_hash &= (1 << new_log2_pages) - 1;
 162       new_v = &new_values[new_hash];
 163
 164       /* Across the new home-page */
 165       for (j = 0; j < BIHASH_KVP_PER_PAGE; j++)
 166         {
 167           /* Empty slot */
 168           if (BV (clib_bihash_is_free) (&(new_v->kvp[j])))
 169             {
 170               clib_memcpy (&(new_v->kvp[j]), &(old_values->kvp[i]),
 171                            sizeof (new_v->kvp[j]));
 172               goto doublebreak;
 173             }
 174         }
 175       /* Crap. Tell caller to try again */
 176       BV (value_free) (h, new_values);
 177       return 0;
 178     doublebreak:;
 179     }
 180   return new_values;
 181 }
 182
 183 static
 184 BVT (clib_bihash_value) *
 185 BV (split_and_rehash_linear)
 186   (BVT (clib_bihash) * h,
 187    BVT (clib_bihash_value) * old_values, u32 new_log2_pages)
 188 {
 189   BVT (clib_bihash_value) * new_values;
 190   int i, j, new_length;
 191
 192   new_values = BV (value_alloc) (h, new_log2_pages);
 193   new_length = (1 << new_log2_pages) * BIHASH_KVP_PER_PAGE;
 194
 195   j = 0;
 196   /* Across the old value array */
 197   for (i = 0; i < vec_len (old_values) * BIHASH_KVP_PER_PAGE; i++)
 198     {
 199       /* Find a free slot in the new linear scan bucket */
 200       for (; j < new_length; j++)
 201         {
 202           /* Old value not in use? Forget it. */
 203           if (BV (clib_bihash_is_free) (&(old_values->kvp[i])))
 204             goto doublebreak;
 205
 206           /* New value should never be in use */
 207           if (BV (clib_bihash_is_free) (&(new_values->kvp[j])))
 208             {
 209               /* Copy the old value and move along */
 210               clib_memcpy (&(new_values->kvp[j]), &(old_values->kvp[i]),
 211                            sizeof (new_values->kvp[j]));
 212               j++;
 213               goto doublebreak;
 214             }
 215         }
 216       /* This should never happen... */
 217       clib_warning ("BUG: linear rehash failed!");
 218       BV (value_free) (h, new_values);
 219       return 0;
 220
 221     doublebreak:;
 222     }
 223   return new_values;
 224 }
 225
 226 int BV (clib_bihash_add_del)
 227   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
 228 {
 229   u32 bucket_index;
 230   clib_bihash_bucket_t *b, tmp_b;
 231   BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy;
 232   int rv = 0;
 233   int i, limit;
 234   u64 hash, new_hash;
 235   u32 new_log2_pages;
 236   u32 cpu_number = os_get_cpu_number ();
 237   int mark_bucket_linear;
 238   int resplit_once;
 239
 240   hash = BV (clib_bihash_hash) (add_v);
 241
 242   bucket_index = hash & (h->nbuckets - 1);
 243   b = &h->buckets[bucket_index];
 244
 245   hash >>= h->log2_nbuckets;
 246
 247   while (__sync_lock_test_and_set (h->writer_lock, 1))
 248     ;
 249
 250   /* First elt in the bucket? */
 251   if (b->offset == 0)
 252     {
 253       if (is_add == 0)
 254         {
 255           rv = -1;
 256           goto unlock;
 257         }
 258
 259       v = BV (value_alloc) (h, 0);
 260       *v->kvp = *add_v;
 261       tmp_b.as_u64 = 0;
 262       tmp_b.offset = BV (clib_bihash_get_offset) (h, v);
 263
 264       b->as_u64 = tmp_b.as_u64;
 265       goto unlock;
 266     }
 267
 268   BV (make_working_copy) (h, b);
 269
 270   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
 271
 272   limit = BIHASH_KVP_PER_PAGE;
 273   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 274   if (b->linear_search)
 275     limit <<= b->log2_pages;
 276
 277   if (is_add)
 278     {
 279       /*
 280        * For obvious (in hindsight) reasons, see if we're supposed to
 281        * replace an existing key, then look for an empty slot.
 282        */
 283       for (i = 0; i < limit; i++)
 284         {
 285           if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
 286             {
 287               clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
 288               CLIB_MEMORY_BARRIER ();
 289               /* Restore the previous (k,v) pairs */
 290               b->as_u64 = h->saved_bucket.as_u64;
 291               goto unlock;
 292             }
 293         }
 294       for (i = 0; i < limit; i++)
 295         {
 296           if (BV (clib_bihash_is_free) (&(v->kvp[i])))
 297             {
 298               clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
 299               CLIB_MEMORY_BARRIER ();
 300               b->as_u64 = h->saved_bucket.as_u64;
 301               goto unlock;
 302             }
 303         }
 304       /* no room at the inn... split case... */
 305     }
 306   else
 307     {
 308       for (i = 0; i < limit; i++)
 309         {
 310           if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
 311             {
 312               memset (&(v->kvp[i]), 0xff, sizeof (*(add_v)));
 313               CLIB_MEMORY_BARRIER ();
 314               b->as_u64 = h->saved_bucket.as_u64;
 315               goto unlock;
 316             }
 317         }
 318       rv = -3;
 319       b->as_u64 = h->saved_bucket.as_u64;
 320       goto unlock;
 321     }
 322
 323   new_log2_pages = h->saved_bucket.log2_pages + 1;
 324   mark_bucket_linear = 0;
 325
 326   working_copy = h->working_copies[cpu_number];
 327   resplit_once = 0;
 328
 329   new_v = BV (split_and_rehash) (h, working_copy, new_log2_pages);
 330   if (new_v == 0)
 331     {
 332     try_resplit:
 333       resplit_once = 1;
 334       new_log2_pages++;
 335       /* Try re-splitting. If that fails, fall back to linear search */
 336       new_v = BV (split_and_rehash) (h, working_copy, new_log2_pages);
 337       if (new_v == 0)
 338         {
 339         mark_linear:
 340           new_log2_pages--;
 341           /* pinned collisions, use linear search */
 342           new_v =
 343             BV (split_and_rehash_linear) (h, working_copy, new_log2_pages);
 344           mark_bucket_linear = 1;
 345         }
 346     }
 347
 348   /* Try to add the new entry */
 349   save_new_v = new_v;
 350   new_hash = BV (clib_bihash_hash) (add_v);
 351   limit = BIHASH_KVP_PER_PAGE;
 352   if (mark_bucket_linear)
 353     limit <<= new_log2_pages;
 354   new_hash >>= h->log2_nbuckets;
 355   new_hash &= (1 << new_log2_pages) - 1;
 356   new_v += mark_bucket_linear ? 0 : new_hash;
 357
 358   for (i = 0; i < limit; i++)
 359     {
 360       if (BV (clib_bihash_is_free) (&(new_v->kvp[i])))
 361         {
 362           clib_memcpy (&(new_v->kvp[i]), add_v, sizeof (*add_v));
 363           goto expand_ok;
 364         }
 365     }
 366   /* Crap. Try again */
 367   BV (value_free) (h, save_new_v);
 368   /*
 369    * If we've already doubled the size of the bucket once,
 370    * fall back to linear search now.
 371    */
 372   if (resplit_once)
 373     goto mark_linear;
 374   else
 375     goto try_resplit;
 376
 377 expand_ok:
 378   /* Keep track of the number of linear-scan buckets */
 379   if (tmp_b.linear_search ^ mark_bucket_linear)
 380     h->linear_buckets += (mark_bucket_linear == 1) ? 1 : -1;
 381
 382   tmp_b.log2_pages = new_log2_pages;
 383   tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
 384   tmp_b.linear_search = mark_bucket_linear;
 385   CLIB_MEMORY_BARRIER ();
 386   b->as_u64 = tmp_b.as_u64;
 387   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
 388   BV (value_free) (h, v);
 389
 390 unlock:
 391   CLIB_MEMORY_BARRIER ();
 392   h->writer_lock[0] = 0;
 393   return rv;
 394 }
 395
 396 int BV (clib_bihash_search)
 397   (const BVT (clib_bihash) * h,
 398    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
 399 {
 400   u64 hash;
 401   u32 bucket_index;
 402   BVT (clib_bihash_value) * v;
 403   clib_bihash_bucket_t *b;
 404   int i, limit;
 405
 406   ASSERT (valuep);
 407
 408   hash = BV (clib_bihash_hash) (search_key);
 409
 410   bucket_index = hash & (h->nbuckets - 1);
 411   b = &h->buckets[bucket_index];
 412
 413   if (b->offset == 0)
 414     return -1;
 415
 416   hash >>= h->log2_nbuckets;
 417
 418   v = BV (clib_bihash_get_value) (h, b->offset);
 419   limit = BIHASH_KVP_PER_PAGE;
 420   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 421   if (PREDICT_FALSE (b->linear_search))
 422     limit <<= b->log2_pages;
 423
 424   for (i = 0; i < limit; i++)
 425     {
 426       if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
 427         {
 428           *valuep = v->kvp[i];
 429           return 0;
 430         }
 431     }
 432   return -1;
 433 }
 434
 435 u8 *BV (format_bihash) (u8 * s, va_list * args)
 436 {
 437   BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *);
 438   int verbose = va_arg (*args, int);
 439   clib_bihash_bucket_t *b;
 440   BVT (clib_bihash_value) * v;
 441   int i, j, k;
 442   u64 active_elements = 0;
 443
 444   s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)");
 445
 446   for (i = 0; i < h->nbuckets; i++)
 447     {
 448       b = &h->buckets[i];
 449       if (b->offset == 0)
 450         {
 451           if (verbose > 1)
 452             s = format (s, "[%d]: empty\n", i);
 453           continue;
 454         }
 455
 456       if (verbose)
 457         {
 458           s = format (s, "[%d]: heap offset %d, len %d, linear %d\n", i,
 459                       b->offset, (1 << b->log2_pages), b->linear_search);
 460         }
 461
 462       v = BV (clib_bihash_get_value) (h, b->offset);
 463       for (j = 0; j < (1 << b->log2_pages); j++)
 464         {
 465           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
 466             {
 467               if (BV (clib_bihash_is_free) (&v->kvp[k]))
 468                 {
 469                   if (verbose > 1)
 470                     s = format (s, "    %d: empty\n",
 471                                 j * BIHASH_KVP_PER_PAGE + k);
 472                   continue;
 473                 }
 474               if (verbose)
 475                 {
 476                   s = format (s, "    %d: %U\n",
 477                               j * BIHASH_KVP_PER_PAGE + k,
 478                               BV (format_bihash_kvp), &(v->kvp[k]));
 479                 }
 480               active_elements++;
 481             }
 482           v++;
 483         }
 484     }
 485
 486   s = format (s, "    %lld active elements\n", active_elements);
 487   s = format (s, "    %d free lists\n", vec_len (h->freelists));
 488   s = format (s, "    %d linear search buckets\n", h->linear_buckets);
 489
 490   return s;
 491 }
 492
 493 void BV (clib_bihash_foreach_key_value_pair)
 494   (BVT (clib_bihash) * h, void *callback, void *arg)
 495 {
 496   int i, j, k;
 497   clib_bihash_bucket_t *b;
 498   BVT (clib_bihash_value) * v;
 499   void (*fp) (BVT (clib_bihash_kv) *, void *) = callback;
 500
 501   for (i = 0; i < h->nbuckets; i++)
 502     {
 503       b = &h->buckets[i];
 504       if (b->offset == 0)
 505         continue;
 506
 507       v = BV (clib_bihash_get_value) (h, b->offset);
 508       for (j = 0; j < (1 << b->log2_pages); j++)
 509         {
 510           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
 511             {
 512               if (BV (clib_bihash_is_free) (&v->kvp[k]))
 513                 continue;
 514
 515               (*fp) (&v->kvp[k], arg);
 516             }
 517           v++;
 518         }
 519     }
 520 }
 521
 522 /** @endcond */
 523
 524 /*
 525  * fd.io coding-style-patch-verification: ON
 526  *
 527  * Local Variables:
 528  * eval: (c-set-style "gnu")
 529  * End:
 530  */