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, *v, *new_v;
 145   int i, j, k;
 146
 147   new_values = BV (value_alloc) (h, new_log2_pages);
 148
 149   v = old_values;
 150   for (i = 0; i < vec_len (old_values); i++)
 151     {
 152       u64 new_hash;
 153
 154       for (j = 0; j < BIHASH_KVP_PER_PAGE; j++)
 155         {
 156           if (BV (clib_bihash_is_free) (&(v->kvp[j])) == 0)
 157             {
 158               new_hash = BV (clib_bihash_hash) (&(v->kvp[j]));
 159               new_hash >>= h->log2_nbuckets;
 160               new_hash &= (1 << new_log2_pages) - 1;
 161
 162               new_v = &new_values[new_hash];
 163
 164               for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
 165                 {
 166                   if (BV (clib_bihash_is_free) (&(new_v->kvp[k])))
 167                     {
 168                       clib_memcpy (&(new_v->kvp[k]), &(v->kvp[j]),
 169                                    sizeof (new_v->kvp[k]));
 170                       goto doublebreak;
 171                     }
 172                 }
 173               /* Crap. Tell caller to try again */
 174               BV (value_free) (h, new_values);
 175               return 0;
 176             }
 177         doublebreak:
 178           ;
 179         }
 180       v++;
 181     }
 182   return new_values;
 183 }
 184
 185 int BV (clib_bihash_add_del)
 186   (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
 187 {
 188   u32 bucket_index;
 189   clib_bihash_bucket_t *b, tmp_b;
 190   BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy;
 191   u32 value_index;
 192   int rv = 0;
 193   int i;
 194   u64 hash, new_hash;
 195   u32 new_log2_pages;
 196   u32 cpu_number = os_get_cpu_number ();
 197
 198   hash = BV (clib_bihash_hash) (add_v);
 199
 200   bucket_index = hash & (h->nbuckets - 1);
 201   b = &h->buckets[bucket_index];
 202
 203   hash >>= h->log2_nbuckets;
 204
 205   while (__sync_lock_test_and_set (h->writer_lock, 1))
 206     ;
 207
 208   /* First elt in the bucket? */
 209   if (b->offset == 0)
 210     {
 211       if (is_add == 0)
 212         {
 213           rv = -1;
 214           goto unlock;
 215         }
 216
 217       v = BV (value_alloc) (h, 0);
 218       *v->kvp = *add_v;
 219       tmp_b.as_u64 = 0;
 220       tmp_b.offset = BV (clib_bihash_get_offset) (h, v);
 221
 222       b->as_u64 = tmp_b.as_u64;
 223       goto unlock;
 224     }
 225
 226   BV (make_working_copy) (h, b);
 227
 228   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
 229   value_index = hash & ((1 << h->saved_bucket.log2_pages) - 1);
 230   v += value_index;
 231
 232   if (is_add)
 233     {
 234       /*
 235        * For obvious (in hindsight) reasons, see if we're supposed to
 236        * replace an existing key, then look for an empty slot.
 237        */
 238       for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
 239         {
 240           if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
 241             {
 242               clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
 243               CLIB_MEMORY_BARRIER ();
 244               /* Restore the previous (k,v) pairs */
 245               b->as_u64 = h->saved_bucket.as_u64;
 246               goto unlock;
 247             }
 248         }
 249       for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
 250         {
 251           if (BV (clib_bihash_is_free) (&(v->kvp[i])))
 252             {
 253               clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v));
 254               CLIB_MEMORY_BARRIER ();
 255               b->as_u64 = h->saved_bucket.as_u64;
 256               goto unlock;
 257             }
 258         }
 259       /* no room at the inn... split case... */
 260     }
 261   else
 262     {
 263       for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
 264         {
 265           if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
 266             {
 267               memset (&(v->kvp[i]), 0xff, sizeof (*(add_v)));
 268               CLIB_MEMORY_BARRIER ();
 269               b->as_u64 = h->saved_bucket.as_u64;
 270               goto unlock;
 271             }
 272         }
 273       rv = -3;
 274       b->as_u64 = h->saved_bucket.as_u64;
 275       goto unlock;
 276     }
 277
 278   new_log2_pages = h->saved_bucket.log2_pages + 1;
 279
 280 expand_again:
 281   working_copy = h->working_copies[cpu_number];
 282   new_v = BV (split_and_rehash) (h, working_copy, new_log2_pages);
 283   if (new_v == 0)
 284     {
 285       new_log2_pages++;
 286       goto expand_again;
 287     }
 288
 289   /* Try to add the new entry */
 290   save_new_v = new_v;
 291   new_hash = BV (clib_bihash_hash) (add_v);
 292   new_hash >>= h->log2_nbuckets;
 293   new_hash &= (1 << min_log2 (vec_len (new_v))) - 1;
 294   new_v += new_hash;
 295
 296   for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
 297     {
 298       if (BV (clib_bihash_is_free) (&(new_v->kvp[i])))
 299         {
 300           clib_memcpy (&(new_v->kvp[i]), add_v, sizeof (*add_v));
 301           goto expand_ok;
 302         }
 303     }
 304   /* Crap. Try again */
 305   new_log2_pages++;
 306   BV (value_free) (h, save_new_v);
 307   goto expand_again;
 308
 309 expand_ok:
 310   tmp_b.log2_pages = min_log2 (vec_len (save_new_v));
 311   tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
 312   CLIB_MEMORY_BARRIER ();
 313   b->as_u64 = tmp_b.as_u64;
 314   v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
 315   BV (value_free) (h, v);
 316
 317 unlock:
 318   CLIB_MEMORY_BARRIER ();
 319   h->writer_lock[0] = 0;
 320   return rv;
 321 }
 322
 323 int BV (clib_bihash_search)
 324   (const BVT (clib_bihash) * h,
 325    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
 326 {
 327   u64 hash;
 328   u32 bucket_index;
 329   uword value_index;
 330   BVT (clib_bihash_value) * v;
 331   clib_bihash_bucket_t *b;
 332   int i;
 333
 334   ASSERT (valuep);
 335
 336   hash = BV (clib_bihash_hash) (search_key);
 337
 338   bucket_index = hash & (h->nbuckets - 1);
 339   b = &h->buckets[bucket_index];
 340
 341   if (b->offset == 0)
 342     return -1;
 343
 344   hash >>= h->log2_nbuckets;
 345
 346   v = BV (clib_bihash_get_value) (h, b->offset);
 347   value_index = hash & ((1 << b->log2_pages) - 1);
 348   v += value_index;
 349
 350   for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
 351     {
 352       if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
 353         {
 354           *valuep = v->kvp[i];
 355           return 0;
 356         }
 357     }
 358   return -1;
 359 }
 360
 361 u8 *BV (format_bihash) (u8 * s, va_list * args)
 362 {
 363   BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *);
 364   int verbose = va_arg (*args, int);
 365   clib_bihash_bucket_t *b;
 366   BVT (clib_bihash_value) * v;
 367   int i, j, k;
 368   u64 active_elements = 0;
 369
 370   s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)");
 371
 372   for (i = 0; i < h->nbuckets; i++)
 373     {
 374       b = &h->buckets[i];
 375       if (b->offset == 0)
 376         {
 377           if (verbose > 1)
 378             s = format (s, "[%d]: empty\n", i);
 379           continue;
 380         }
 381
 382       if (verbose)
 383         {
 384           s = format (s, "[%d]: heap offset %d, len %d\n", i,
 385                       b->offset, (1 << b->log2_pages));
 386         }
 387
 388       v = BV (clib_bihash_get_value) (h, b->offset);
 389       for (j = 0; j < (1 << b->log2_pages); j++)
 390         {
 391           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
 392             {
 393               if (BV (clib_bihash_is_free) (&v->kvp[k]))
 394                 {
 395                   if (verbose > 1)
 396                     s = format (s, "    %d: empty\n",
 397                                 j * BIHASH_KVP_PER_PAGE + k);
 398                   continue;
 399                 }
 400               if (verbose)
 401                 {
 402                   s = format (s, "    %d: %U\n",
 403                               j * BIHASH_KVP_PER_PAGE + k,
 404                               BV (format_bihash_kvp), &(v->kvp[k]));
 405                 }
 406               active_elements++;
 407             }
 408           v++;
 409         }
 410     }
 411
 412   s = format (s, "    %lld active elements\n", active_elements);
 413   s = format (s, "    %d free lists\n", vec_len (h->freelists));
 414
 415   return s;
 416 }
 417
 418 void BV (clib_bihash_foreach_key_value_pair)
 419   (BVT (clib_bihash) * h, void *callback, void *arg)
 420 {
 421   int i, j, k;
 422   clib_bihash_bucket_t *b;
 423   BVT (clib_bihash_value) * v;
 424   void (*fp) (BVT (clib_bihash_kv) *, void *) = callback;
 425
 426   for (i = 0; i < h->nbuckets; i++)
 427     {
 428       b = &h->buckets[i];
 429       if (b->offset == 0)
 430         continue;
 431
 432       v = BV (clib_bihash_get_value) (h, b->offset);
 433       for (j = 0; j < (1 << b->log2_pages); j++)
 434         {
 435           for (k = 0; k < BIHASH_KVP_PER_PAGE; k++)
 436             {
 437               if (BV (clib_bihash_is_free) (&v->kvp[k]))
 438                 continue;
 439
 440               (*fp) (&v->kvp[k], arg);
 441             }
 442           v++;
 443         }
 444     }
 445 }
 446
 447 /** @endcond */
 448
 449 /*
 450  * fd.io coding-style-patch-verification: ON
 451  *
 452  * Local Variables:
 453  * eval: (c-set-style "gnu")
 454  * End:
 455  */