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 #include <vppinfra/cuckoo_8_8.h>
  39
  40 #ifndef CLIB_CUCKOO_TYPE
  41 #error CLIB_CUCKOO_TYPE not defined
  42 #endif
  43
  44 #ifndef CLIB_CUCKOO_BFS_MAX_STEPS
  45 #error CLIB_CUCKOO_BFS_MAX_STEPS not defined
  46 #endif
  47
  48 #ifndef CLIB_CUCKOO_KVP_PER_BUCKET
  49 #error CLIB_CUCKOO_KVP_PER_BUCKET not defined
  50 #endif
  51
  52 #ifndef CLIB_CUCKOO_LOG2_KVP_PER_BUCKET
  53 #error CLIB_CUCKOO_LOG2_KVP_PER_BUCKET not defined
  54 #endif
  55
  56 #ifndef CLIB_CUCKOO_BFS_MAX_PATH_LENGTH
  57 #error CLIB_CUCKOO_BFS_MAX_PATH_LENGTH not defined
  58 #endif
  59
  60 STATIC_ASSERT (CLIB_CUCKOO_KVP_PER_BUCKET ==
  61                (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET),
  62                "CLIB_CUCKOO_KVP_PER_BUCKET != (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET");
  63
  64 #define _cv(a, b) a##b
  65 #define __cv(a, b) _cv (a, b)
  66 #define CV(a) __cv (a, CLIB_CUCKOO_TYPE)
  67
  68 #define _cvt(a, b) a##b##_t
  69 #define __cvt(a, b) _cvt (a, b)
  70 #define CVT(a) __cvt (a, CLIB_CUCKOO_TYPE)
  71
  72 typedef u64 clib_cuckoo_bucket_aux_t;
  73
  74 #define CLIB_CUCKOO_USE_COUNT_BIT_WIDTH (1 + CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)
  75
  76 always_inline u64
  77 clib_cuckoo_bucket_aux_get_version (clib_cuckoo_bucket_aux_t aux)
  78 {
  79   return aux >> (1 + CLIB_CUCKOO_USE_COUNT_BIT_WIDTH);
  80 }
  81
  82 always_inline int
  83 clib_cuckoo_bucket_aux_get_use_count (clib_cuckoo_bucket_aux_t aux)
  84 {
  85   u64 use_count_mask = (1 << CLIB_CUCKOO_USE_COUNT_BIT_WIDTH) - 1;
  86   return (aux >> 1) & use_count_mask;
  87 }
  88
  89 always_inline int
  90 clib_cuckoo_bucket_aux_get_writer_flag (clib_cuckoo_bucket_aux_t aux)
  91 {
  92   return aux & 1;
  93 }
  94
  95 always_inline clib_cuckoo_bucket_aux_t
  96 clib_cuckoo_bucket_aux_pack (u64 version, int use_count, int writer_flag)
  97 {
  98   return (version << (1 + CLIB_CUCKOO_USE_COUNT_BIT_WIDTH)) +
  99     (use_count << 1) + writer_flag;
 100 }
 101
 102 always_inline clib_cuckoo_bucket_aux_t
 103 clib_cuckoo_bucket_aux_set_version (clib_cuckoo_bucket_aux_t aux, u64 version)
 104 {
 105   int use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
 106   int writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
 107   return clib_cuckoo_bucket_aux_pack (version, use_count, writer_flag);
 108 }
 109
 110 always_inline clib_cuckoo_bucket_aux_t
 111 clib_cuckoo_bucket_aux_set_use_count (clib_cuckoo_bucket_aux_t aux,
 112                                       int use_count)
 113 {
 114   u64 version = clib_cuckoo_bucket_aux_get_version (aux);
 115   int writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
 116   return clib_cuckoo_bucket_aux_pack (version, use_count, writer_flag);
 117 }
 118
 119 always_inline clib_cuckoo_bucket_aux_t
 120 clib_cuckoo_bucket_aux_set_writer_flag (clib_cuckoo_bucket_aux_t aux,
 121                                         int writer_flag)
 122 {
 123   u64 version = clib_cuckoo_bucket_aux_get_version (aux);
 124   int use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
 125   return clib_cuckoo_bucket_aux_pack (version, use_count, writer_flag);
 126 }
 127
 128 #define PATH_BITS_REQ \
 129   (CLIB_CUCKOO_BFS_MAX_PATH_LENGTH * CLIB_CUCKOO_LOG2_KVP_PER_BUCKET)
 130
 131 #if PATH_BITS_REQ <= 8
 132 typedef u8 path_data_t;
 133 #elif PATH_BITS_REQ <= 16
 134 typedef u16 path_data_t;
 135 #elif PATH_BITS_REQ <= 32
 136 typedef u32 path_data_t;
 137 #elif PATH_BITS_REQ <= 64
 138 typedef u64 path_data_t;
 139 #else
 140 #error no suitable datatype for path storage...
 141 #endif
 142
 143 typedef struct
 144 {
 145   /** bucket where this path begins */
 146   u64 start;
 147   /** bucket at end of path */
 148   u64 bucket;
 149   /** length of the path */
 150   u8 length;
 151   /** holds compressed offsets in buckets along path */
 152   path_data_t data;
 153 } clib_cuckoo_path_t;
 154
 155 typedef struct
 156 {
 157   CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
 158
 159   /** reduced hashes corresponding to elements */
 160   u8 reduced_hashes[CLIB_CUCKOO_KVP_PER_BUCKET];
 161
 162   /** auxiliary data - version, writer flag and used count */
 163   volatile clib_cuckoo_bucket_aux_t aux;
 164
 165   /** cuckoo elements in this bucket */
 166     CVT (clib_cuckoo_kv) elts[CLIB_CUCKOO_KVP_PER_BUCKET];
 167 } CVT (clib_cuckoo_bucket);
 168
 169 #define clib_cuckoo_bucket_foreach_idx(var) \
 170   for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; var++)
 171
 172 #if CLIB_CUCKOO_OPTIMIZE_UNROLL
 173 #if CLIB_CUCKOO_KVP_PER_BUCKET == 2
 174 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
 175   do                                                       \
 176     {                                                      \
 177       var = 0;                                             \
 178       body;                                                \
 179       var = 1;                                             \
 180       body;                                                \
 181     }                                                      \
 182   while (0);
 183 #elif CLIB_CUCKOO_KVP_PER_BUCKET == 4
 184 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
 185   do                                                       \
 186     {                                                      \
 187       var = 0;                                             \
 188       body;                                                \
 189       var = 1;                                             \
 190       body;                                                \
 191       var = 2;                                             \
 192       body;                                                \
 193       var = 3;                                             \
 194       body;                                                \
 195     }                                                      \
 196   while (0);
 197 #elif CLIB_CUCKOO_KVP_PER_BUCKET == 8
 198 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
 199   do                                                       \
 200     {                                                      \
 201       var = 0;                                             \
 202       body;                                                \
 203       var = 1;                                             \
 204       body;                                                \
 205       var = 2;                                             \
 206       body;                                                \
 207       var = 3;                                             \
 208       body;                                                \
 209       var = 4;                                             \
 210       body;                                                \
 211       var = 5;                                             \
 212       body;                                                \
 213       var = 6;                                             \
 214       body;                                                \
 215       var = 7;                                             \
 216       body;                                                \
 217     }                                                      \
 218   while (0);
 219 #else
 220 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
 221   clib_cuckoo_bucket_foreach_idx (var)                     \
 222   {                                                        \
 223     body;                                                  \
 224   }
 225 #endif
 226 #else /* CLIB_CUCKOO_OPTIMIZE_UNROLL */
 227 #define clib_cuckoo_bucket_foreach_idx_unrolled(var, body) \
 228   clib_cuckoo_bucket_foreach_idx (var)                     \
 229   {                                                        \
 230     body;                                                  \
 231   }
 232 #endif /* CLIB_CUCKOO_OPTIMIZE_UNROLL */
 233
 234 #define clib_cuckoo_bucket_foreach_elt_index(var, bucket) \
 235   for (var = 0; var < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
 236
 237 #define clib_cuckoo_foreach_bucket(var, h, body)        \
 238   do                                                    \
 239     {                                                   \
 240       CVT (clib_cuckoo_bucket) *__buckets = h->buckets; \
 241       vec_foreach (var, __buckets)                      \
 242       {                                                 \
 243         body;                                           \
 244       }                                                 \
 245     }                                                   \
 246   while (0)
 247
 248 typedef struct CV (clib_cuckoo)
 249 {
 250   /** vector of elements containing key-value pairs and auxiliary data */
 251   CVT (clib_cuckoo_bucket) * volatile buckets;
 252
 253   /** garbage to be freed once its safe to do so .. */
 254   CVT (clib_cuckoo_bucket) * *to_be_freed;
 255
 256   /** hash table name */
 257   const char *name;
 258
 259   /** pool of cuckoo paths (reused when doing bfd search) */
 260   clib_cuckoo_path_t *paths;
 261
 262   /**
 263    * vector used as queue when doing cuckoo path searches - holds offsets
 264    * in paths pool
 265    */
 266   uword *bfs_search_queue;
 267
 268   /**
 269    * writer lock - whether this lock is taken or not has zero effect on
 270    * readers
 271    */
 272   clib_spinlock_t writer_lock;
 273
 274   /** caller context passed to callback with garbage notification */
 275   void *garbage_ctx;
 276
 277   /**
 278    * garbage notify function - called when some garbage needs to be collected
 279    * in main thread while other threads are stopped
 280    */
 281   void (*garbage_callback) (struct CV (clib_cuckoo) * h, void *garbage_ctx);
 282
 283 #if CLIB_CUCKOO_DEBUG_COUNTERS
 284   u64 steps_exceeded;
 285   u64 bfs_queue_emptied;
 286   u64 fast_adds;
 287   u64 slow_adds;
 288   u64 rehashes;
 289 #endif
 290
 291 } CVT (clib_cuckoo);
 292
 293 void CV (clib_cuckoo_init) (CVT (clib_cuckoo) * h, const char *name,
 294                             uword nbuckets,
 295                             void (*garbage_callback) (CVT (clib_cuckoo) *,
 296                                                       void *),
 297                             void *garbage_ctx);
 298
 299 void CV (clib_cuckoo_garbage_collect) (CVT (clib_cuckoo) * h);
 300
 301 void CV (clib_cuckoo_free) (CVT (clib_cuckoo) * h);
 302
 303 int CV (clib_cuckoo_add_del) (CVT (clib_cuckoo) * h,
 304                               CVT (clib_cuckoo_kv) * add_v, int is_add);
 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 CV (clib_cuckoo_search_inline) (CVT (clib_cuckoo) * h,
 412                                                   CVT (clib_cuckoo_kv) * kvp)
 413 {
 414   clib_cuckoo_lookup_info_t lookup;
 415   int rv;
 416
 417   u64 hash = CV (clib_cuckoo_hash) (kvp);
 418   CVT (clib_cuckoo_bucket) * buckets;
 419 again:
 420   buckets = h->buckets;
 421   lookup = CV (clib_cuckoo_calc_lookup) (buckets, hash);
 422   do
 423     {
 424       rv =
 425         CV (clib_cuckoo_bucket_search) (vec_elt_at_index
 426                                         (buckets, lookup.bucket1), kvp,
 427                                         lookup.reduced_hash);
 428     }
 429   while (PREDICT_FALSE (CLIB_CUCKOO_ERROR_AGAIN == rv));
 430   if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
 431     {
 432       return CLIB_CUCKOO_ERROR_SUCCESS;
 433     }
 434
 435   rv =
 436     CV (clib_cuckoo_bucket_search) (vec_elt_at_index
 437                                     (buckets, lookup.bucket2), kvp,
 438                                     lookup.reduced_hash);
 439   if (PREDICT_FALSE (CLIB_CUCKOO_ERROR_AGAIN == rv))
 440     {
 441       /*
 442        * change to 2nd bucket could bump the item to 1st bucket and the bucket
 443        * indexes might not even be valid anymore - restart the search
 444        */
 445       goto again;
 446     }
 447   return rv;
 448 }
 449
 450 #endif /* __included_cuckoo_template_h__ */
 451
 452 /** @endcond */
 453
 454 /*
 455  * fd.io coding-style-patch-verification: ON
 456  *
 457  * Local Variables:
 458  * eval: (c-set-style "gnu")
 459  * End:
 460  */