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