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 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           /* This should never happen... */
 216           clib_warning ("BUG: linear rehash failed!");
 217           BV (value_free) (h, new_values);
 218           return 0;
 219         }
 220     doublebreak:;
 221     }
 222   return new_values;
 223 }
 224
 225 int BV (clib_bihash_add_del)
 226   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
 227 {
 228   u32 bucket_index;
 229   clib_bihash_bucket_t *b, tmp_b;
 230   BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy;
 231   int rv = 0;
 232   int i, limit;
 233   u64 hash, new_hash;
 234   u32 new_log2_pages;
 235   u32 cpu_number = os_get_cpu_number ();
 236   int mark_bucket_linear;
 237   int resplit_once;
 238
 239   hash = BV (clib_bihash_hash) (add_v);
 240
 241   bucket_index = hash & (h->nbuckets - 1);
 242   b = &h->buckets[bucket_index];
 243
 244   hash >>= h->log2_nbuckets;
 245
 246   while (__sync_lock_test_and_set (h->writer_lock, 1))
 247     ;
 248
 249   /* First elt in the bucket? */
 250   if (b->offset == 0)
 251     {
 252       if (is_add == 0)
 253         {
 254           rv = -1;
 255           goto unlock;
 256         }
 257
 258       v = BV (value_alloc) (h, 0);
 259       *v->kvp = *add_v;
 260       tmp_b.as_u64 = 0;
 261       tmp_b.offset = BV (clib_bihash_get_offset) (h, v);
 262
 263       b->as_u64 = tmp_b.as_u64;
 264       goto unlock;
 265     }
 266
 267   BV (make_working_copy) (h, b);
 268
 269   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
 270
 271   limit = BIHASH_KVP_PER_PAGE;
 272   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 273   if (b->linear_search)
 274     limit <<= b->log2_pages;
 275
 276   if (is_add)
 277     {
 278       /*
 279        * For obvious (in hindsight) reasons, see if we're supposed to
 280        * replace an existing key, then look for an empty slot.
 281        */
 282       for (i = 0; i < limit; i++)
 283         {
 284           if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
 285             {
 286               clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
 287               CLIB_MEMORY_BARRIER ();
 288               /* Restore the previous (k,v) pairs */
 289               b->as_u64 = h->saved_bucket.as_u64;
 290               goto unlock;
 291             }
 292         }
 293       for (i = 0; i < limit; i++)
 294         {
 295           if (BV (clib_bihash_is_free) (&(v->kvp[i])))
 296             {
 297               clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
 298               CLIB_MEMORY_BARRIER ();
 299               b->as_u64 = h->saved_bucket.as_u64;
 300               goto unlock;
 301             }
 302         }
 303       /* no room at the inn... split case... */
 304     }
 305   else
 306     {
 307       for (i = 0; i < limit; i++)
 308         {
 309           if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
 310             {
 311               memset (&(v->kvp[i]), 0xff, sizeof (*(add_v)));
 312               CLIB_MEMORY_BARRIER ();
 313               b->as_u64 = h->saved_bucket.as_u64;
 314               goto unlock;
 315             }
 316         }
 317       rv = -3;
 318       b->as_u64 = h->saved_bucket.as_u64;
 319       goto unlock;
 320     }
 321
 322   new_log2_pages = h->saved_bucket.log2_pages + 1;
 323   mark_bucket_linear = 0;
 324
 325   working_copy = h->working_copies[cpu_number];
 326   resplit_once = 0;
 327
 328   new_v = BV (split_and_rehash) (h, working_copy, new_log2_pages);
 329   if (new_v == 0)
 330     {
 331     try_resplit:
 332       resplit_once = 1;
 333       new_log2_pages++;
 334       /* Try re-splitting. If that fails, fall back to linear search */
 335       new_v = BV (split_and_rehash) (h, working_copy, new_log2_pages);
 336       if (new_v == 0)
 337         {
 338         mark_linear:
 339           new_log2_pages--;
 340           /* pinned collisions, use linear search */
 341           new_v =
 342             BV (split_and_rehash_linear) (h, working_copy, new_log2_pages);
 343           mark_bucket_linear = 1;
 344         }
 345     }
 346
 347   /* Try to add the new entry */
 348   save_new_v = new_v;
 349   new_hash = BV (clib_bihash_hash) (add_v);
 350   limit = BIHASH_KVP_PER_PAGE;
 351   if (mark_bucket_linear)
 352     limit <<= new_log2_pages;
 353   new_hash >>= h->log2_nbuckets;
 354   new_hash &= (1 << new_log2_pages) - 1;
 355   new_v += mark_bucket_linear ? 0 : new_hash;
 356
 357   for (i = 0; i < limit; i++)
 358     {
 359       if (BV (clib_bihash_is_free) (&(new_v->kvp[i])))
 360         {
 361           clib_memcpy (&(new_v->kvp[i]), add_v, sizeof (*add_v));
 362           goto expand_ok;
 363         }
 364     }
 365   /* Crap. Try again */
 366   BV (value_free) (h, save_new_v);
 367   /*
 368    * If we've already doubled the size of the bucket once,
 369    * fall back to linear search now.
 370    */
 371   if (resplit_once)
 372     goto mark_linear;
 373   else
 374     goto try_resplit;
 375
 376 expand_ok:
 377   /* Keep track of the number of linear-scan buckets */
 378   if (tmp_b.linear_search ^ mark_bucket_linear)
 379     h->linear_buckets += (mark_bucket_linear == 1) ? 1 : -1;
 380
 381   tmp_b.log2_pages = new_log2_pages;
 382   tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
 383   tmp_b.linear_search = mark_bucket_linear;
 384   CLIB_MEMORY_BARRIER ();
 385   b->as_u64 = tmp_b.as_u64;
 386   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
 387   BV (value_free) (h, v);
 388
 389 unlock:
 390   CLIB_MEMORY_BARRIER ();
 391   h->writer_lock[0] = 0;
 392   return rv;
 393 }
 394
 395 int BV (clib_bihash_search)
 396   (const BVT (clib_bihash) * h,
 397    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
 398 {
 399   u64 hash;
 400   u32 bucket_index;
 401   BVT (clib_bihash_value) * v;
 402   clib_bihash_bucket_t *b;
 403   int i, limit;
 404
 405   ASSERT (valuep);
 406
 407   hash = BV (clib_bihash_hash) (search_key);
 408
 409   bucket_index = hash & (h->nbuckets - 1);
 410   b = &h->buckets[bucket_index];
 411
 412   if (b->offset == 0)
 413     return -1;
 414
 415   hash >>= h->log2_nbuckets;
 416
 417   v = BV (clib_bihash_get_value) (h, b->offset);
 418   limit = BIHASH_KVP_PER_PAGE;
 419   v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
 420   if (PREDICT_FALSE (b->linear_search))
 421     limit <<= b->log2_pages;
 422
 423   for (i = 0; i < limit; i++)
 424     {
 425       if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
 426         {
 427           *valuep = v->kvp[i];
 428           return 0;
 429         }
 430     }
 431   return -1;
 432 }
 433
 434 u8 *BV (format_bihash) (u8 * s, va_list * args)
 435 {
 436   BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *);
 437   int verbose = va_arg (*args, int);
 438   clib_bihash_bucket_t *b;
 439   BVT (clib_bihash_value) * v;
 440   int i, j, k;
 441   u64 active_elements = 0;
 442
 443   s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)");
 444
 445   for (i = 0; i < h->nbuckets; i++)
 446     {
 447       b = &h->buckets[i];
 448       if (b->offset == 0)
 449         {
 450           if (verbose > 1)
 451             s = format (s, "[%d]: empty\n", i);
 452           continue;
 453         }
 454
 455       if (verbose)
 456         {
 457           s = format (s, "[%d]: heap offset %d, len %d, linear %d\n", i,
 458                       b->offset, (1 << b->log2_pages), b->linear_search);
 459         }
 460
 461       v = BV (clib_bihash_get_value) (h, b->offset);
 462       for (j = 0; j < (1 << b->log2_pages); j++)
 463         {
 464           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
 465             {
 466               if (BV (clib_bihash_is_free) (&v->kvp[k]))
 467                 {
 468                   if (verbose > 1)
 469                     s = format (s, "    %d: empty\n",
 470                                 j * BIHASH_KVP_PER_PAGE + k);
 471                   continue;
 472                 }
 473               if (verbose)
 474                 {
 475                   s = format (s, "    %d: %U\n",
 476                               j * BIHASH_KVP_PER_PAGE + k,
 477                               BV (format_bihash_kvp), &(v->kvp[k]));
 478                 }
 479               active_elements++;
 480             }
 481           v++;
 482         }
 483     }
 484
 485   s = format (s, "    %lld active elements\n", active_elements);
 486   s = format (s, "    %d free lists\n", vec_len (h->freelists));
 487   s = format (s, "    %d linear search buckets\n", h->linear_buckets);
 488
 489   return s;
 490 }
 491
 492 void BV (clib_bihash_foreach_key_value_pair)
 493   (BVT (clib_bihash) * h, void *callback, void *arg)
 494 {
 495   int i, j, k;
 496   clib_bihash_bucket_t *b;
 497   BVT (clib_bihash_value) * v;
 498   void (*fp) (BVT (clib_bihash_kv) *, void *) = callback;
 499
 500   for (i = 0; i < h->nbuckets; i++)
 501     {
 502       b = &h->buckets[i];
 503       if (b->offset == 0)
 504         continue;
 505
 506       v = BV (clib_bihash_get_value) (h, b->offset);
 507       for (j = 0; j < (1 << b->log2_pages); j++)
 508         {
 509           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
 510             {
 511               if (BV (clib_bihash_is_free) (&v->kvp[k]))
 512                 continue;
 513
 514               (*fp) (&v->kvp[k], arg);
 515             }
 516           v++;
 517         }
 518     }
 519 }
 520
 521 /** @endcond */
 522
 523 /*
 524  * fd.io coding-style-patch-verification: ON
 525  *
 526  * Local Variables:
 527  * eval: (c-set-style "gnu")
 528  * End:
 529  */