src/vppinfra/cuckoo_template.h

   1 /*
   2   Copyright (c) 2017 Cisco and/or its affiliates.
   3
   4   * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15 */
  16
  17 /*
  18  * cuckoo hash implementation based on paper
  19  * 'Algorithmic Improvements for Fast Concurrent Cuckoo Hashing'
  20  * by Xiaozhou Li, David G. Andersen, Michael Kaminsky, Michael J. Freedman
  21  * and their libcuckoo implementation (https://github.com/efficient/libcuckoo)
  22  */
  23
  24 /*
  25  * Note: to instantiate the template multiple times in a single file,
  26  * #undef __included_cuckoo_template_h__...
  27  */
  28 #ifndef __included_cuckoo_template_h__
  29 #define __included_cuckoo_template_h__
  30
  31 #include <vppinfra/heap.h>
  32 #include <vppinfra/format.h>
  33 #include <vppinfra/pool.h>
  34 #include <vppinfra/lock.h>
  35 #include <vppinfra/error.h>
  36 #include <vppinfra/hash.h>
  37 #include <vppinfra/cache.h>
  38
  39 #ifndef CLIB_CUCKOO_TYPE
  40 #error CLIB_CUCKOO_TYPE not defined
  41 #endif
  42
  43 #ifndef CLIB_CUCKOO_BFS_MAX_STEPS
  44 #error CLIB_CUCKOO_BFS_MAX_STEPS not defined
  45 #endif
  46
  47 #ifndef CLIB_CUCKOO_KVP_PER_BUCKET
  48 #error CLIB_CUCKOO_KVP_PER_BUCKET not defined
  49 #endif
  50
  51 #ifndef CLIB_CUCKOO_LOG2_KVP_PER_BUCKET
  52 #error CLIB_CUCKOO_LOG2_KVP_PER_BUCKET not defined
  53 #endif
  54
  55 #ifndef CLIB_CUCKOO_BFS_MAX_PATH_LENGTH
  56 #error CLIB_CUCKOO_BFS_MAX_PATH_LENGTH not defined
  57 #endif
  58
  59 STATIC_ASSERT (CLIB_CUCKOO_KVP_PER_BUCKET ==
  60                (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET),
  61                "CLIB_CUCKOO_KVP_PER_BUCKET != (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET");
  62
  63 #define _cv(a, b) a##b
  64 #define __cv(a, b) _cv (a, b)
  65 #define CV(a) __cv (a, CLIB_CUCKOO_TYPE)
  66
  67 #define _cvt(a, b) a##b##_t
  68 #define __cvt(a, b) _cvt (a, b)
  69 #define CVT(a) __cvt (a, CLIB_CUCKOO_TYPE)
  70
  71 typedef u64 clib_cuckoo_bucket_aux_t;
  72
  73 #define CLIB_CUCKOO_USE_COUNT_BIT_WIDTH (1 + CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)
  74
  75 always_inline u64
  76 clib_cuckoo_bucket_aux_get_version (clib_cuckoo_bucket_aux_t aux)
  77 {
  78   return aux >> (1 + CLIB_CUCKOO_USE_COUNT_BIT_WIDTH);
  79 }
  80
  81 always_inline int
  82 clib_cuckoo_bucket_aux_get_use_count (clib_cuckoo_bucket_aux_t aux)
  83 {
  84   u64 use_count_mask = (1 << CLIB_CUCKOO_USE_COUNT_BIT_WIDTH) - 1;
  85   return (aux >> 1) & use_count_mask;
  86 }
  87
  88 always_inline int
  89 clib_cuckoo_bucket_aux_get_writer_flag (clib_cuckoo_bucket_aux_t aux)
  90 {
  91   return aux & 1;
  92 }
  93
  94 always_inline clib_cuckoo_bucket_aux_t
  95 clib_cuckoo_bucket_aux_pack (u64 version, int use_count, int writer_flag)
  96 {
  97   return (version << (1 + CLIB_CUCKOO_USE_COUNT_BIT_WIDTH)) +
  98     (use_count << 1) + writer_flag;
  99 }
 100
 101 always_inline clib_cuckoo_bucket_aux_t
 102 clib_cuckoo_bucket_aux_set_version (clib_cuckoo_bucket_aux_t aux, u64 version)
 103 {
 104   int use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
 105   int writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
 106   return clib_cuckoo_bucket_aux_pack (version, use_count, writer_flag);
 107 }
 108
 109 always_inline clib_cuckoo_bucket_aux_t
 110 clib_cuckoo_bucket_aux_set_use_count (clib_cuckoo_bucket_aux_t aux,
 111                                       int use_count)
 112 {
 113   u64 version = clib_cuckoo_bucket_aux_get_version (aux);
 114   int writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
 115   return clib_cuckoo_bucket_aux_pack (version, use_count, writer_flag);
 116 }
 117
 118 always_inline clib_cuckoo_bucket_aux_t
 119 clib_cuckoo_bucket_aux_set_writer_flag (clib_cuckoo_bucket_aux_t aux,
 120                                         int writer_flag)
 121 {
 122   u64 version = clib_cuckoo_bucket_aux_get_version (aux);
 123   int use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
 124   return clib_cuckoo_bucket_aux_pack (version, use_count, writer_flag);
 125 }
 126
 127 #define PATH_BITS_REQ \
 128   (CLIB_CUCKOO_BFS_MAX_PATH_LENGTH * CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)
 129
 130 #if PATH_BITS_REQ <= 8
 131 typedef u8 path_data_t;
 132 #elif PATH_BITS_REQ <= 16
 133 typedef u16 path_data_t;
 134 #elif PATH_BITS_REQ <= 32
 135 typedef u32 path_data_t;
 136 #elif PATH_BITS_REQ <= 64
 137 typedef u64 path_data_t;
 138 #else
 139 #error no suitable datatype for path storage...
 140 #endif
 141
 142 typedef struct
 143 {
 144   /** bucket where this path begins */
 145   u64 start;
 146   /** bucket at end of path */
 147   u64 bucket;
 148   /** length of the path */
 149   u8 length;
 150   /** holds compressed offsets in buckets along path */
 151   path_data_t data;
 152 } clib_cuckoo_path_t;
 153
 154 typedef struct
 155 {
 156   CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
 157
 158   /** reduced hashes corresponding to elements */
 159   u8 reduced_hashes[CLIB_CUCKOO_KVP_PER_BUCKET];
 160
 161   /** auxiliary data - version, writer flag and used count */
 162   volatile clib_cuckoo_bucket_aux_t aux;
 163
 164   /** cuckoo elements in this bucket */
 165     CVT (clib_cuckoo_kv) elts[CLIB_CUCKOO_KVP_PER_BUCKET];
 166 } CVT (clib_cuckoo_bucket);
 167
 168 #define clib_cuckoo_bucket_foreach_idx(var) \
 169   for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; var++)
 170
 171 #if CLIB_CUCKOO_OPTIMIZE_UNROLL
 172 #if CLIB_CUCKOO_KVP_PER_BUCKET == 2
 173 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
 174   do                                                       \
 175     {                                                      \
 176       var = 0;                                             \
 177       body;                                                \
 178       var = 1;                                             \
 179       body;                                                \
 180     }                                                      \
 181   while (0);
 182 #elif CLIB_CUCKOO_KVP_PER_BUCKET == 4
 183 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
 184   do                                                       \
 185     {                                                      \
 186       var = 0;                                             \
 187       body;                                                \
 188       var = 1;                                             \
 189       body;                                                \
 190       var = 2;                                             \
 191       body;                                                \
 192       var = 3;                                             \
 193       body;                                                \
 194     }                                                      \
 195   while (0);
 196 #elif CLIB_CUCKOO_KVP_PER_BUCKET == 8
 197 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
 198   do                                                       \
 199     {                                                      \
 200       var = 0;                                             \
 201       body;                                                \
 202       var = 1;                                             \
 203       body;                                                \
 204       var = 2;                                             \
 205       body;                                                \
 206       var = 3;                                             \
 207       body;                                                \
 208       var = 4;                                             \
 209       body;                                                \
 210       var = 5;                                             \
 211       body;                                                \
 212       var = 6;                                             \
 213       body;                                                \
 214       var = 7;                                             \
 215       body;                                                \
 216     }                                                      \
 217   while (0);
 218 #else
 219 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
 220   clib_cuckoo_bucket_foreach_idx (var)                     \
 221   {                                                        \
 222     body;                                                  \
 223   }
 224 #endif
 225 #else /* CLIB_CUCKOO_OPTIMIZE_UNROLL */
 226 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
 227   clib_cuckoo_bucket_foreach_idx (var)                     \
 228   {                                                        \
 229     body;                                                  \
 230   }
 231 #endif /* CLIB_CUCKOO_OPTIMIZE_UNROLL */
 232
 233 #define clib_cuckoo_bucket_foreach_elt_index(var, bucket) \
 234   for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
 235
 236 #define clib_cuckoo_foreach_bucket(var, h, body)        \
 237   do                                                    \
 238     {                                                   \
 239       CVT (clib_cuckoo_bucket) *__buckets = h->buckets; \
 240       vec_foreach (var, __buckets)                      \
 241       {                                                 \
 242         body;                                           \
 243       }                                                 \
 244     }                                                   \
 245   while (0)
 246
 247 typedef struct CV (clib_cuckoo)
 248 {
 249   /** vector of elements containing key-value pairs and auxiliary data */
 250   CVT (clib_cuckoo_bucket) * volatile buckets;
 251
 252   /** garbage to be freed once its safe to do so .. */
 253   CVT (clib_cuckoo_bucket) * *to_be_freed;
 254
 255   /** hash table name */
 256   const char *name;
 257
 258   /** pool of cuckoo paths (reused when doing bfd search) */
 259   clib_cuckoo_path_t *paths;
 260
 261   /**
 262    * vector used as queue when doing cuckoo path searches - holds offsets
 263    * in paths pool
 264    */
 265   uword *bfs_search_queue;
 266
 267   /**
 268    * writer lock - whether this lock is taken or not has zero effect on
 269    * readers
 270    */
 271   clib_spinlock_t writer_lock;
 272
 273   /** caller context passed to callback with garbage notification */
 274   void *garbage_ctx;
 275
 276   /**
 277    * garbage notify function - called when some garbage needs to be collected
 278    * in main thread while other threads are stopped
 279    */
 280   void (*garbage_callback) (struct CV (clib_cuckoo) * h, void *garbage_ctx);
 281
 282 #if CLIB_CUCKOO_DEBUG_COUNTERS
 283   u64 steps_exceeded;
 284   u64 bfs_queue_emptied;
 285   u64 fast_adds;
 286   u64 slow_adds;
 287   u64 rehashes;
 288 #endif
 289
 290 } CVT (clib_cuckoo);
 291
 292 void CV (clib_cuckoo_init) (CVT (clib_cuckoo) * h, const char *name,
 293                             uword nbuckets,
 294                             void (*garbage_callback) (CVT (clib_cuckoo) *,
 295                                                       void *),
 296                             void *garbage_ctx);
 297
 298 void CV (clib_cuckoo_garbage_collect) (CVT (clib_cuckoo) * h);
 299
 300 void CV (clib_cuckoo_free) (CVT (clib_cuckoo) * h);
 301
 302 int CV (clib_cuckoo_add_del) (CVT (clib_cuckoo) * h,
 303                               CVT (clib_cuckoo_kv) * add_v, int is_add,
 304                               int dont_overwrite);
 305 int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h,
 306                              CVT (clib_cuckoo_kv) * search_v,
 307                              CVT (clib_cuckoo_kv) * return_v);
 308
 309 void CV (clib_cuckoo_foreach_key_value_pair) (CVT (clib_cuckoo) * h,
 310                                               void *callback, void *arg);
 311
 312 float CV (clib_cuckoo_calc_load) (CVT (clib_cuckoo) * h);
 313
 314 format_function_t CV (format_cuckoo);
 315 format_function_t CV (format_cuckoo_kvp);
 316
 317 always_inline u8
 318 clib_cuckoo_reduce_hash (u64 hash)
 319 {
 320   u32 v32 = ((u32) hash) ^ ((u32) (hash >> 32));
 321   u16 v16 = ((u16) v32) ^ ((u16) (v32 >> 16));
 322   u8 v8 = ((u8) v16) ^ ((u8) (v16 >> 8));
 323   return v8;
 324 }
 325
 326 always_inline u64
 327 clib_cuckoo_get_other_bucket (u64 nbuckets, u64 bucket, u8 reduced_hash)
 328 {
 329   u64 mask = (nbuckets - 1);
 330   return (bucket ^ ((reduced_hash + 1) * 0xc6a4a7935bd1e995)) & mask;
 331 }
 332
 333 always_inline clib_cuckoo_lookup_info_t
 334 CV (clib_cuckoo_calc_lookup) (CVT (clib_cuckoo_bucket) * buckets, u64 hash)
 335 {
 336   clib_cuckoo_lookup_info_t lookup;
 337   u64 nbuckets = vec_len (buckets);
 338   u64 mask = (nbuckets - 1);
 339   lookup.bucket1 = hash & mask;
 340 #if CLIB_CUCKOO_OPTIMIZE_PREFETCH
 341   CLIB_PREFETCH (vec_elt_at_index (buckets, lookup.bucket1),
 342                  sizeof (*buckets), LOAD);
 343 #endif
 344   u8 reduced_hash = clib_cuckoo_reduce_hash (hash);
 345   lookup.bucket2 =
 346     clib_cuckoo_get_other_bucket (nbuckets, lookup.bucket1, reduced_hash);
 347 #if CLIB_CUCKOO_OPTIMIZE_PREFETCH
 348   CLIB_PREFETCH (vec_elt_at_index (buckets, lookup.bucket2),
 349                  sizeof (*buckets), LOAD);
 350 #endif
 351   lookup.reduced_hash = reduced_hash;
 352   ASSERT (lookup.bucket1 < nbuckets);
 353   ASSERT (lookup.bucket2 < nbuckets);
 354   return lookup;
 355 }
 356
 357 /**
 358  * search for key within bucket
 359  */
 360 always_inline int CV (clib_cuckoo_bucket_search) (CVT (clib_cuckoo_bucket) *
 361                                                   b,
 362                                                   CVT (clib_cuckoo_kv) * kvp,
 363                                                   u8 reduced_hash)
 364 {
 365   clib_cuckoo_bucket_aux_t bucket_aux;
 366   u8 writer_flag;
 367   do
 368     {
 369       bucket_aux = b->aux;
 370       writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (bucket_aux);
 371     }
 372   while (PREDICT_FALSE (writer_flag));  /* loop while writer flag is set */
 373
 374   int i;
 375 #if CLIB_CUCKOO_OPTIMIZE_USE_COUNT_LIMITS_SEARCH
 376   const int use_count = clib_cuckoo_bucket_aux_get_use_count (bucket_aux);
 377 #endif
 378   /* *INDENT-OFF* */
 379   clib_cuckoo_bucket_foreach_idx_unrolled (i, {
 380 #if CLIB_CUCKOO_OPTIMIZE_USE_COUNT_LIMITS_SEARCH
 381     if (i > use_count)
 382       {
 383         break;
 384       }
 385 #endif
 386     if (
 387 #if CLIB_CUCKOO_OPTIMIZE_CMP_REDUCED_HASH
 388         reduced_hash == b->reduced_hashes[i] &&
 389 #endif
 390         0 == memcmp (&kvp->key, &b->elts[i].key, sizeof (kvp->key)))
 391       {
 392         kvp->value = b->elts[i].value;
 393         clib_cuckoo_bucket_aux_t bucket_aux2 = b->aux;
 394         if (PREDICT_TRUE (clib_cuckoo_bucket_aux_get_version (bucket_aux) ==
 395                           clib_cuckoo_bucket_aux_get_version (bucket_aux2)))
 396           {
 397             /* yay, fresh data */
 398             return CLIB_CUCKOO_ERROR_SUCCESS;
 399           }
 400         else
 401           {
 402             /* oops, modification detected */
 403             return CLIB_CUCKOO_ERROR_AGAIN;
 404           }
 405       }
 406   });
 407   /* *INDENT-ON* */
 408   return CLIB_CUCKOO_ERROR_NOT_FOUND;
 409 }
 410
 411 always_inline int
 412 CV (clib_cuckoo_search_inline_with_hash) (CVT (clib_cuckoo) * h, u64 hash,
 413                                           CVT (clib_cuckoo_kv) * kvp)
 414 {
 415   CVT (clib_cuckoo_bucket) * buckets = h->buckets;
 416   uword bucket1, bucket2;
 417   u8 reduced_hash;
 418   u64 nbuckets = vec_len (buckets);
 419   u64 mask = nbuckets - 1;
 420   int rv;
 421
 422   bucket1 = hash & mask;
 423   reduced_hash = clib_cuckoo_reduce_hash (hash);
 424
 425 again:
 426   rv = CV (clib_cuckoo_bucket_search) (vec_elt_at_index (buckets, bucket1),
 427                                        kvp, reduced_hash);
 428
 429   if (rv == CLIB_CUCKOO_ERROR_SUCCESS)
 430     return CLIB_CUCKOO_ERROR_SUCCESS;
 431
 432   if (PREDICT_FALSE (rv == CLIB_CUCKOO_ERROR_AGAIN))
 433     goto again;
 434
 435   bucket2 = clib_cuckoo_get_other_bucket (nbuckets, bucket1, reduced_hash);
 436   rv = CV (clib_cuckoo_bucket_search) (vec_elt_at_index (buckets, bucket2),
 437                                        kvp, reduced_hash);
 438
 439   /* change to 2nd bucket could bump the item to 1st bucket and the bucket
 440    * indexes might not even be valid anymore - restart the search */
 441   if (PREDICT_FALSE (rv == CLIB_CUCKOO_ERROR_AGAIN))
 442     goto again;
 443
 444   return rv;
 445 }
 446
 447 always_inline int CV (clib_cuckoo_search_inline) (CVT (clib_cuckoo) * h,
 448                                                   CVT (clib_cuckoo_kv) * kvp)
 449 {
 450   u64 hash = CV (clib_cuckoo_hash) (kvp);
 451   return CV (clib_cuckoo_search_inline_with_hash) (h, hash, kvp);
 452 }
 453
 454 #endif /* __included_cuckoo_template_h__ */
 455
 456 /** @endcond */
 457
 458 /*
 459  * fd.io coding-style-patch-verification: ON
 460  *
 461  * Local Variables:
 462  * eval: (c-set-style "gnu")
 463  * End:
 464  */