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