extras/deprecated/vppinfra/cuckoo_template.c

   1 /*
   2  * Copyright (c) 2017 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 /*
  17  * cuckoo hash implementation based on paper
  18  * 'Algorithmic Improvements for Fast Concurrent Cuckoo Hashing'
  19  * by Xiaozhou Li, David G. Andersen, Michael Kaminsky, Michael J. Freedman
  20  * and their libcuckoo implementation (https://github.com/efficient/libcuckoo)
  21  */
  22
  23 #include <vppinfra/vec.h>
  24
  25 int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h,
  26                              CVT (clib_cuckoo_kv) * search_v,
  27                              CVT (clib_cuckoo_kv) * return_v)
  28 {
  29   CVT (clib_cuckoo_kv) tmp = *search_v;
  30   int rv = CV (clib_cuckoo_search_inline) (h, &tmp);
  31   if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
  32     {
  33       *return_v = tmp;
  34     }
  35   return rv;
  36 }
  37
  38 static
  39 CVT (clib_cuckoo_bucket) *
  40 CV (clib_cuckoo_bucket_at_index) (CVT (clib_cuckoo) * h, uword bucket)
  41 {
  42   return vec_elt_at_index (h->buckets, bucket);
  43 }
  44
  45 static uword CV (clib_cuckoo_get_nbuckets) (CVT (clib_cuckoo) * h)
  46 {
  47   return vec_len (h->buckets);
  48 }
  49
  50 static inline uword
  51 CV (clib_cuckoo_elt_in_bucket_to_offset) (CVT (clib_cuckoo_bucket) * b,
  52                                           CVT (clib_cuckoo_kv) * e)
  53 {
  54   ASSERT (e >= b->elts);
  55   ASSERT (e <= &b->elts[sizeof (b->elts) / sizeof (b->elts[0]) - 1]);
  56   return e - b->elts;
  57 }
  58
  59 u8 *CV (format_cuckoo_elt) (u8 * s, va_list * args)
  60 {
  61   CVT (clib_cuckoo_kv) * elt = va_arg (*args, CVT (clib_cuckoo_kv) *);
  62   unsigned reduced_hash = va_arg (*args, unsigned);
  63   if (CV (clib_cuckoo_kv_is_free) (elt))
  64     {
  65       s = format (s, "[ -- empty -- ]");
  66     }
  67   else
  68     {
  69       s = format (s, "[%U, reduced hash: %u]", CV (format_cuckoo_kvp), elt,
  70                   reduced_hash);
  71     }
  72   return s;
  73 }
  74
  75 u8 *CV (format_cuckoo_bucket) (u8 * s, va_list * args)
  76 {
  77   CVT (clib_cuckoo_bucket) * bucket =
  78     va_arg (*args, CVT (clib_cuckoo_bucket) *);
  79   int i = 0;
  80
  81   /* *INDENT-OFF* */
  82   clib_cuckoo_bucket_foreach_idx (i)
  83   {
  84     CVT (clib_cuckoo_kv) *elt = bucket->elts + i;
  85     s = format (s, "bucket %p, offset %d: %U\n", bucket, i,
  86                 CV (format_cuckoo_elt), elt, bucket->reduced_hashes[i]);
  87   }
  88   /* *INDENT-ON* */
  89   clib_cuckoo_bucket_aux_t aux = bucket->aux;
  90   s = format (s, "version: %lld, use count: %d\n",
  91               clib_cuckoo_bucket_aux_get_version (aux),
  92               clib_cuckoo_bucket_aux_get_use_count (aux));
  93   return s;
  94 }
  95
  96 #if CLIB_CUCKOO_DEBUG
  97 static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h)
  98 {
  99   CVT (clib_cuckoo_bucket) * bucket;
 100   uword bucket_idx = 0;
 101   /* *INDENT-OFF* */
 102   clib_cuckoo_foreach_bucket (bucket, h, {
 103     int i = 0;
 104     int used = 0;
 105     clib_cuckoo_bucket_foreach_idx (i)
 106     {
 107       CVT (clib_cuckoo_kv) *elt = bucket->elts + i;
 108       if (!CV (clib_cuckoo_kv_is_free) (elt))
 109         {
 110           u64 hash = CV (clib_cuckoo_hash) (elt);
 111           clib_cuckoo_lookup_info_t lookup =
 112               CV (clib_cuckoo_calc_lookup) (h->buckets, hash);
 113           CVT (clib_cuckoo_kv) kv = *elt;
 114           int rv = CV (clib_cuckoo_search) (h, &kv, &kv);
 115           if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
 116             {
 117               CLIB_CUCKOO_DBG ("Search for elt `%U' failed!",
 118                                CV (format_cuckoo_elt), elt,
 119                                bucket->reduced_hashes[i]);
 120               CLIB_CUCKOO_DBG ("%U", CV (format_cuckoo), h, 1);
 121             }
 122           ASSERT (lookup.bucket1 == bucket_idx || lookup.bucket2 == bucket_idx);
 123           ASSERT (CLIB_CUCKOO_ERROR_SUCCESS == rv);
 124           ++used;
 125         }
 126     }
 127     clib_cuckoo_bucket_aux_t aux = bucket->aux;
 128     ASSERT (used == clib_cuckoo_bucket_aux_get_use_count (aux));
 129     ++bucket_idx;
 130   });
 131   /* *INDENT-ON* */
 132   // CLIB_CUCKOO_DBG ("Deep self check passed: %U", CV (format_cuckoo), h);
 133 }
 134
 135 #define CLIB_CUCKOO_DEEP_SELF_CHECK(h) CV (clib_cuckoo_deep_self_check) (h)
 136 #define CLIB_CUCKOO_ASSERT_BUCKET_SORTED(b)                                 \
 137   do                                                                        \
 138     {                                                                       \
 139       int i;                                                                \
 140       int min_free = CLIB_CUCKOO_KVP_PER_BUCKET;                            \
 141       int max_used = 0;                                                     \
 142       clib_cuckoo_bucket_foreach_idx (i)                                    \
 143       {                                                                     \
 144         if (!CV (clib_cuckoo_kv_is_free) (b->elts + i))                     \
 145           {                                                                 \
 146             max_used = i;                                                   \
 147           }                                                                 \
 148         if (CV (clib_cuckoo_kv_is_free) (b->elts +                          \
 149                                          (CLIB_CUCKOO_KVP_PER_BUCKET - i))) \
 150           {                                                                 \
 151             min_free = i;                                                   \
 152           }                                                                 \
 153       }                                                                     \
 154       ASSERT (min_free > max_used);                                         \
 155     }                                                                       \
 156   while (0)
 157
 158 #else
 159 #define CLIB_CUCKOO_DEEP_SELF_CHECK(h)
 160 #define CLIB_CUCKOO_ASSERT_BUCKET_SORTED(b)
 161 #endif
 162
 163 void CV (clib_cuckoo_init) (CVT (clib_cuckoo) * h, const char *name,
 164                             uword nbuckets,
 165                             void (*garbage_callback) (CVT (clib_cuckoo) *,
 166                                                       void *),
 167                             void *garbage_ctx)
 168 {
 169   uword log2_nbuckets = max_log2 (nbuckets);
 170   nbuckets = 1ULL << (log2_nbuckets);
 171   CLIB_CUCKOO_DBG ("New cuckoo, adjusted nbuckets %wu", nbuckets);
 172   CVT (clib_cuckoo_bucket) * buckets = NULL;
 173   vec_validate_aligned (buckets, nbuckets - 1, CLIB_CACHE_LINE_BYTES);
 174   ASSERT (nbuckets == vec_len (buckets));
 175   h->buckets = buckets;
 176   clib_spinlock_init (&h->writer_lock);
 177   /* mark all elements free ... */
 178   CVT (clib_cuckoo_bucket) * bucket;
 179   /* *INDENT-OFF* */
 180   clib_cuckoo_foreach_bucket (
 181       bucket, h, { clib_memset (bucket->elts, 0xff, sizeof (bucket->elts)); });
 182   /* *INDENT-ON* */
 183   h->name = name;
 184   h->garbage_callback = garbage_callback;
 185   h->garbage_ctx = garbage_ctx;
 186 }
 187
 188 void CV (clib_cuckoo_free) (CVT (clib_cuckoo) * h)
 189 {
 190   clib_memset (h, 0, sizeof (*h));
 191 }
 192
 193 static clib_cuckoo_bucket_aux_t
 194 CV (clib_cuckoo_bucket_version_bump_and_lock) (CVT (clib_cuckoo_bucket) * b)
 195 {
 196   clib_cuckoo_bucket_aux_t aux = b->aux;
 197   u64 version = clib_cuckoo_bucket_aux_get_version (aux);
 198   u8 use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
 199   u8 writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
 200   ASSERT (0 == writer_flag);
 201   aux = clib_cuckoo_bucket_aux_pack (version + 1, use_count, 1);
 202   b->aux = aux;
 203   return aux;
 204 }
 205
 206 static void CV (clib_cuckoo_bucket_unlock) (CVT (clib_cuckoo_bucket) * b,
 207                                             clib_cuckoo_bucket_aux_t aux)
 208 {
 209   u64 version = clib_cuckoo_bucket_aux_get_version (aux);
 210   u8 use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
 211   u8 writer_flag = clib_cuckoo_bucket_aux_get_writer_flag (aux);
 212   ASSERT (1 == writer_flag);
 213   aux = clib_cuckoo_bucket_aux_pack (version, use_count, 0);
 214   b->aux = aux;
 215 }
 216
 217 #define CLIB_CUCKOO_DEBUG_PATH (1)
 218 #define CLIB_CUCKOO_DEBUG_PATH_DETAIL (0)
 219
 220 #if CLIB_CUCKOO_DEBUG && CLIB_CUCKOO_DEBUG_PATH
 221 static u8 *CV (format_cuckoo_path) (u8 * s, va_list * args);
 222 #endif
 223
 224 static clib_cuckoo_path_t *CV (clib_cuckoo_path_get) (CVT (clib_cuckoo) * h)
 225 {
 226   clib_cuckoo_path_t *path;
 227   pool_get (h->paths, path);
 228   clib_memset (path, 0, sizeof (*path));
 229 #if CLIB_CUCKOO_DEBUG_PATH_DETAIL
 230   CLIB_CUCKOO_DBG ("Get path @%lu", (long unsigned) (path - h->paths));
 231 #endif
 232   return path;
 233 }
 234
 235 static void CV (clib_cuckoo_path_put) (CVT (clib_cuckoo) * h, uword path_idx)
 236 {
 237   clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
 238 #if CLIB_CUCKOO_DEBUG_PATH_DETAIL
 239   CLIB_CUCKOO_DBG ("Put path @%lu", (long unsigned) (path - h->paths));
 240 #endif
 241   pool_put (h->paths, path);
 242 }
 243
 244 static clib_cuckoo_path_t *CV (clib_cuckoo_path_begin) (CVT (clib_cuckoo) * h,
 245                                                         uword bucket,
 246                                                         uword next_offset)
 247 {
 248   ASSERT (next_offset < CLIB_CUCKOO_KVP_PER_BUCKET);
 249   clib_cuckoo_path_t *new_path = CV (clib_cuckoo_path_get) (h);
 250   new_path->length = 1;
 251   new_path->data = next_offset;
 252   new_path->start = bucket;
 253   new_path->bucket = bucket;
 254 #if CLIB_CUCKOO_DEBUG_PATH
 255   CLIB_CUCKOO_DBG ("Create new path @%wu, length: %u data: %llu bucket: %wu "
 256                    "next-offset: %wu",
 257                    new_path - h->paths, new_path->length,
 258                    (long long unsigned) new_path->data, new_path->bucket,
 259                    next_offset);
 260 #endif
 261   return new_path;
 262 }
 263
 264 /**
 265  * create a new path based on existing path extended by adding a bucket
 266  * and offset
 267  */
 268 static uword CV (clib_cuckoo_path_extend) (CVT (clib_cuckoo) * h,
 269                                            uword path_idx, uword bucket,
 270                                            unsigned offset)
 271 {
 272   ASSERT (offset < CLIB_CUCKOO_KVP_PER_BUCKET);
 273   clib_cuckoo_path_t *new_path = CV (clib_cuckoo_path_get) (h);
 274   uword new_path_idx = new_path - h->paths;
 275   clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
 276   new_path->start = path->start;
 277   new_path->length = path->length + 1;
 278   new_path->data = (path->data << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET) + offset;
 279   new_path->bucket = bucket;
 280 #if CLIB_CUCKOO_DEBUG_PATH
 281   CLIB_CUCKOO_DBG ("Extend path @%wu, new path @%wu, %U", path_idx,
 282                    new_path_idx, CV (format_cuckoo_path), h, new_path_idx);
 283 #endif
 284   return new_path_idx;
 285 }
 286
 287 /** return the offset of the last element in the path */
 288 static uword CV (clib_cuckoo_path_peek_offset) (const clib_cuckoo_path_t *
 289                                                 path)
 290 {
 291   ASSERT (path->length > 0);
 292   uword mask = (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET) - 1;
 293   uword offset = path->data & mask;
 294   return offset;
 295 }
 296
 297 static
 298 CVT (clib_cuckoo_kv) *
 299 CV (clib_cuckoo_bucket_find_empty) (CVT (clib_cuckoo_bucket) * bucket)
 300 {
 301   clib_cuckoo_bucket_aux_t aux = bucket->aux;
 302   u8 use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
 303   if (use_count < CLIB_CUCKOO_KVP_PER_BUCKET)
 304     {
 305       return bucket->elts + use_count;
 306     }
 307   return NULL;
 308 }
 309
 310 /**
 311  * walk the cuckoo path two ways,
 312  * first backwards, extracting offsets,
 313  * then forward, extracting buckets
 314  *
 315  * buckets and offsets are arrays filled with elements extracted from path
 316  * the arrays must be able to contain CLIB_CUCKOO_BFS_MAX_PATH_LENGTH elements
 317  */
 318 static void
 319 clib_cuckoo_path_walk (CVT (clib_cuckoo) * h, uword path_idx,
 320                        uword * buckets, uword * offsets)
 321 {
 322   clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
 323   ASSERT (path->length > 0);
 324   u64 data = path->data;
 325   uword mask = (1 << CLIB_CUCKOO_LOG2_KVP_PER_BUCKET) - 1;
 326   uword i;
 327   for (i = path->length; i > 0; --i)
 328     {
 329       uword offset = data & mask;
 330       offsets[i - 1] = offset;
 331       data >>= CLIB_CUCKOO_LOG2_KVP_PER_BUCKET;
 332     }
 333   buckets[0] = path->start;
 334   for (i = 1; i < path->length; ++i)
 335     {
 336       CVT (clib_cuckoo_bucket) * b =
 337         CV (clib_cuckoo_bucket_at_index) (h, buckets[i - 1]);
 338       buckets[i] =
 339         clib_cuckoo_get_other_bucket (CV (clib_cuckoo_get_nbuckets) (h),
 340                                       buckets[i - 1],
 341                                       b->reduced_hashes[offsets[i - 1]]);
 342     }
 343 }
 344
 345 #if CLIB_CUCKOO_DEBUG && CLIB_CUCKOO_DEBUG_PATH
 346 static u8 *CV (format_cuckoo_path) (u8 * s, va_list * args)
 347 {
 348   CVT (clib_cuckoo) * h = va_arg (*args, CVT (clib_cuckoo) *);
 349   uword path_idx = va_arg (*args, uword);
 350   clib_cuckoo_path_t *p = pool_elt_at_index (h->paths, path_idx);
 351   uword buckets[CLIB_CUCKOO_BFS_MAX_PATH_LENGTH];
 352   uword offsets[CLIB_CUCKOO_BFS_MAX_PATH_LENGTH];
 353   clib_cuckoo_path_walk (h, path_idx, buckets, offsets);
 354   s = format (s, "length %u: ", p->length);
 355   for (uword i = p->length - 1; i > 0; --i)
 356     {
 357       s = format (s, "%wu[%wu]->", buckets[i], offsets[i]);
 358     }
 359   if (p->length)
 360     {
 361       s = format (s, "%wu[%wu]", buckets[0], offsets[0]);
 362     }
 363   return s;
 364 }
 365 #endif
 366
 367 /*
 368  * perform breadth-first search in the cuckoo hash, finding the closest
 369  * empty slot, i.e. one which requires minimum swaps to move it
 370  * to one of the buckets provided
 371  */
 372 static int CV (clib_cuckoo_find_empty_slot_bfs) (CVT (clib_cuckoo) * h,
 373                                                  clib_cuckoo_lookup_info_t *
 374                                                  lookup, uword * path_idx_out,
 375                                                  uword * found_bucket,
 376                                                  CVT (clib_cuckoo_kv) *
 377                                                  *found_elt)
 378 {
 379   uword *tail;
 380   ASSERT (!vec_len (h->bfs_search_queue));
 381   clib_cuckoo_path_t *tmp;
 382   pool_flush (tmp, h->paths,);
 383   int rv = CLIB_CUCKOO_ERROR_AGAIN;
 384   int counter = 0;
 385   /* start by creating paths starting in each of the buckets ... */
 386   vec_add2 (h->bfs_search_queue, tail, CLIB_CUCKOO_KVP_PER_BUCKET);
 387   int i;
 388   for (i = 0; i < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
 389     {
 390       clib_cuckoo_path_t *path =
 391         CV (clib_cuckoo_path_begin) (h, lookup->bucket1, i);
 392       tail[i] = path - h->paths;
 393     }
 394   if (lookup->bucket1 != lookup->bucket2)
 395     {
 396       vec_add2 (h->bfs_search_queue, tail, CLIB_CUCKOO_KVP_PER_BUCKET);
 397       for (i = 0; i < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
 398         {
 399           clib_cuckoo_path_t *path =
 400             CV (clib_cuckoo_path_begin) (h, lookup->bucket2, i);
 401           tail[i] = path - h->paths;
 402         }
 403     }
 404   while (1)
 405     {
 406       if (counter >= CLIB_CUCKOO_BFS_MAX_STEPS)
 407         {
 408 #if CLIB_CUCKOO_DEBUG_COUNTERS
 409           ++h->steps_exceeded;
 410 #endif
 411           break;
 412         }
 413       if (counter >= vec_len (h->bfs_search_queue))
 414         {
 415 #if CLIB_CUCKOO_DEBUG_COUNTERS
 416           ++h->bfs_queue_emptied;
 417 #endif
 418           break;
 419         }
 420       const uword path_idx = vec_elt (h->bfs_search_queue, counter);
 421       const clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
 422 #if CLIB_CUCKOO_DEBUG_PATH
 423       CLIB_CUCKOO_DBG ("Examine path @%wu: %U", path_idx,
 424                        CV (format_cuckoo_path), h, path_idx);
 425 #endif
 426       /* TODO prefetch ? */
 427       /* search the alternative bucket for free space */
 428       int offset = CV (clib_cuckoo_path_peek_offset) (path);
 429       CVT (clib_cuckoo_bucket) * bucket =
 430         CV (clib_cuckoo_bucket_at_index) (h, path->bucket);
 431       uword other_bucket =
 432         clib_cuckoo_get_other_bucket (CV (clib_cuckoo_get_nbuckets) (h),
 433                                       path->bucket,
 434                                       bucket->reduced_hashes[offset]);
 435       CLIB_CUCKOO_DBG
 436         ("Path ends in bucket %wu, offset #%wu, other bucket is %wu",
 437          path->bucket, CV (clib_cuckoo_path_peek_offset) (path),
 438          other_bucket);
 439       if (path->bucket != other_bucket)
 440         {
 441           if ((*found_elt =
 442                CV (clib_cuckoo_bucket_find_empty) (CV
 443                                                    (clib_cuckoo_bucket_at_index)
 444                                                    (h, other_bucket))))
 445             {
 446               /* found empty element */
 447               *found_bucket = other_bucket;
 448               *path_idx_out = path_idx;
 449               rv = CLIB_CUCKOO_ERROR_SUCCESS;
 450 #if CLIB_CUCKOO_DEBUG_PATH
 451               CLIB_CUCKOO_DBG ("Bucket with empty slot:\n%U",
 452                                CV (format_cuckoo_bucket),
 453                                CV (clib_cuckoo_bucket_at_index) (h,
 454                                                                  other_bucket));
 455 #endif
 456               goto out;
 457             }
 458           /* extend the current path with possible next buckets and add to
 459            * queue */
 460           if (path->length < CLIB_CUCKOO_BFS_MAX_PATH_LENGTH &&
 461               vec_len (h->bfs_search_queue) < CLIB_CUCKOO_BFS_MAX_STEPS)
 462             {
 463               uword *tail;
 464               vec_add2 (h->bfs_search_queue, tail,
 465                         CLIB_CUCKOO_KVP_PER_BUCKET);
 466               for (i = 0; i < CLIB_CUCKOO_KVP_PER_BUCKET; ++i)
 467                 {
 468                   uword new_path_idx =
 469                     CV (clib_cuckoo_path_extend) (h, path_idx, other_bucket,
 470                                                   i);
 471                   tail[i] = new_path_idx;
 472                 }
 473             }
 474         }
 475       else
 476         {
 477           CLIB_CUCKOO_DBG ("Discard path @%wu, loop detected", path_idx);
 478         }
 479       /* done with this path - put back to pool for later reuse */
 480       CV (clib_cuckoo_path_put) (h, path_idx);
 481       ++counter;
 482     }
 483 out:
 484   vec_reset_length (h->bfs_search_queue);
 485   return rv;
 486 }
 487
 488 static void CV (clib_cuckoo_swap_elts_in_bucket) (CVT (clib_cuckoo_bucket) *
 489                                                   b, uword e1, uword e2)
 490 {
 491   CVT (clib_cuckoo_kv) kv;
 492   clib_memcpy (&kv, b->elts + e1, sizeof (kv));
 493   clib_memcpy (b->elts + e1, b->elts + e2, sizeof (kv));
 494   clib_memcpy (b->elts + e2, &kv, sizeof (kv));
 495   u8 reduced_hash = b->reduced_hashes[e1];
 496   b->reduced_hashes[e1] = b->reduced_hashes[e2];
 497   b->reduced_hashes[e2] = reduced_hash;
 498 }
 499
 500 static void CV (clib_cuckoo_bucket_tidy) (CVT (clib_cuckoo_bucket) * b)
 501 {
 502   int i = 0;
 503   int j = CLIB_CUCKOO_KVP_PER_BUCKET - 1;
 504   while (i != j)
 505     {
 506       int min_free = i;
 507       int max_used = j;
 508       while (!CV (clib_cuckoo_kv_is_free) (&b->elts[min_free]))
 509         {
 510           ++min_free;
 511         }
 512       while (CV (clib_cuckoo_kv_is_free) (&b->elts[max_used]))
 513         {
 514           --max_used;
 515         }
 516       if (min_free < max_used)
 517         {
 518           CV (clib_cuckoo_swap_elts_in_bucket) (b, min_free, max_used);
 519           i = min_free + 1;
 520           j = max_used - 1;
 521         }
 522       else
 523         {
 524           break;
 525         }
 526     }
 527 }
 528
 529 static void CV (clib_cuckoo_free_locked_elt) (CVT (clib_cuckoo_kv) * elt)
 530 {
 531   /*
 532    * FIXME - improve performance by getting rid of this clib_memset - make all
 533    * functions in this file not rely on clib_cuckoo_kv_is_free but instead
 534    * take use_count into account */
 535   clib_memset (elt, 0xff, sizeof (*elt));
 536 }
 537
 538 static void CV (clib_cuckoo_free_elt_in_bucket) (CVT (clib_cuckoo_bucket) * b,
 539                                                  CVT (clib_cuckoo_kv) * elt)
 540 {
 541   clib_cuckoo_bucket_aux_t aux =
 542     CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
 543   int use_count = clib_cuckoo_bucket_aux_get_use_count (aux);
 544   int offset = elt - b->elts;
 545   ASSERT (offset < use_count);
 546   CV (clib_cuckoo_free_locked_elt) (elt);
 547   if (offset != use_count - 1)
 548     {
 549       CV (clib_cuckoo_bucket_tidy) (b);
 550     }
 551   aux = clib_cuckoo_bucket_aux_set_use_count (aux, use_count - 1);
 552   CV (clib_cuckoo_bucket_unlock) (b, aux);
 553 }
 554
 555 static void CV (clib_cuckoo_set_locked_elt) (CVT (clib_cuckoo_bucket) * b,
 556                                              CVT (clib_cuckoo_kv) * elt,
 557                                              CVT (clib_cuckoo_kv) * kvp,
 558                                              u8 reduced_hash)
 559 {
 560   int offset = CV (clib_cuckoo_elt_in_bucket_to_offset) (b, elt);
 561   clib_memcpy (elt, kvp, sizeof (*elt));
 562   b->reduced_hashes[offset] = reduced_hash;
 563   CLIB_CUCKOO_DBG ("Set bucket %p, offset %d, %U", b, offset,
 564                    CV (format_cuckoo_elt), elt, b->reduced_hashes[offset]);
 565 }
 566
 567 static void CV (clib_cuckoo_set_elt) (CVT (clib_cuckoo_bucket) * b,
 568                                       CVT (clib_cuckoo_kv) * elt,
 569                                       CVT (clib_cuckoo_kv) * kvp,
 570                                       u8 reduced_hash)
 571 {
 572   clib_cuckoo_bucket_aux_t aux =
 573     CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
 574   CV (clib_cuckoo_set_locked_elt) (b, elt, kvp, reduced_hash);
 575   CV (clib_cuckoo_bucket_unlock) (b, aux);
 576 }
 577
 578 static int CV (clib_cuckoo_add_slow) (CVT (clib_cuckoo) * h,
 579                                       CVT (clib_cuckoo_kv) * kvp,
 580                                       clib_cuckoo_lookup_info_t * lookup,
 581                                       u8 reduced_hash)
 582 {
 583   uword path_idx;
 584   uword empty_bucket_idx;
 585   CVT (clib_cuckoo_kv) * empty_elt;
 586   int rv = CV (clib_cuckoo_find_empty_slot_bfs) (h, lookup, &path_idx,
 587                                                  &empty_bucket_idx,
 588                                                  &empty_elt);
 589   if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
 590     {
 591       uword buckets[CLIB_CUCKOO_BFS_MAX_PATH_LENGTH];
 592       uword offsets[CLIB_CUCKOO_BFS_MAX_PATH_LENGTH];
 593       clib_cuckoo_path_walk (h, path_idx, buckets, offsets);
 594       /*
 595        * walk back the path, moving the free element forward to one of our
 596        * buckets ...
 597        */
 598       clib_cuckoo_path_t *path = pool_elt_at_index (h->paths, path_idx);
 599       CVT (clib_cuckoo_bucket) * empty_bucket =
 600         CV (clib_cuckoo_bucket_at_index) (h, empty_bucket_idx);
 601       int i;
 602       for (i = path->length - 1; i >= 0; --i)
 603         {
 604           /* copy the key-value in path to the bucket with empty element */
 605           CVT (clib_cuckoo_bucket) * b =
 606             CV (clib_cuckoo_bucket_at_index) (h, buckets[i]);
 607           CVT (clib_cuckoo_kv) * elt = b->elts + offsets[i];
 608           clib_cuckoo_bucket_aux_t empty_aux =
 609             CV (clib_cuckoo_bucket_version_bump_and_lock) (empty_bucket);
 610           CV (clib_cuckoo_set_locked_elt)
 611             (empty_bucket, empty_elt, elt, b->reduced_hashes[elt - b->elts]);
 612           if (i == path->length - 1)
 613             {
 614               /* we only need to increase the use count for the bucket with
 615                * free element - all other buckets' use counts won't change */
 616               empty_aux = clib_cuckoo_bucket_aux_set_use_count (empty_aux,
 617                                                                 clib_cuckoo_bucket_aux_get_use_count
 618                                                                 (empty_aux) +
 619                                                                 1);
 620             }
 621           CV (clib_cuckoo_bucket_unlock) (empty_bucket, empty_aux);
 622           /*
 623            * the element now exists in both places - in the previously empty
 624            * element and in its original bucket - we can now safely overwrite
 625            * the element in the original bucket with previous element in path
 626            * without loosing data (and we don't need to modify the use count)
 627            */
 628           empty_bucket = b;
 629           empty_elt = elt;
 630         }
 631       /* now we have a place to put the kvp in ... */
 632       CV (clib_cuckoo_set_elt) (empty_bucket, empty_elt, kvp, reduced_hash);
 633       CLIB_CUCKOO_DBG ("Slow insert success, bucket: %p\n%U", empty_bucket,
 634                        CV (format_cuckoo_bucket), empty_bucket);
 635 #if CLIB_CUCKOO_DEBUG_COUNTERS
 636       ++h->slow_adds;
 637 #endif
 638     }
 639   return rv;
 640 }
 641
 642 static int CV (clib_cuckoo_add_fast) (CVT (clib_cuckoo) * h,
 643                                       clib_cuckoo_lookup_info_t * lookup,
 644                                       CVT (clib_cuckoo_kv) * kvp,
 645                                       u8 reduced_hash)
 646 {
 647   CVT (clib_cuckoo_kv) * elt;
 648   CVT (clib_cuckoo_bucket) * bucket1 =
 649     CV (clib_cuckoo_bucket_at_index) (h, lookup->bucket1);
 650   if ((elt = CV (clib_cuckoo_bucket_find_empty) (bucket1)))
 651     {
 652       clib_cuckoo_bucket_aux_t aux =
 653         CV (clib_cuckoo_bucket_version_bump_and_lock) (bucket1);
 654       CV (clib_cuckoo_set_locked_elt) (bucket1, elt, kvp, reduced_hash);
 655       aux =
 656         clib_cuckoo_bucket_aux_set_use_count (aux,
 657                                               clib_cuckoo_bucket_aux_get_use_count
 658                                               (aux) + 1);
 659       CV (clib_cuckoo_bucket_unlock) (bucket1, aux);
 660 #if CLIB_CUCKOO_DEBUG_COUNTERS
 661       ++h->fast_adds;
 662 #endif
 663       return CLIB_CUCKOO_ERROR_SUCCESS;
 664     }
 665   CVT (clib_cuckoo_bucket) * bucket2 =
 666     CV (clib_cuckoo_bucket_at_index) (h, lookup->bucket2);
 667   if ((elt =
 668        CV (clib_cuckoo_bucket_find_empty) (CV (clib_cuckoo_bucket_at_index)
 669                                            (h, lookup->bucket2))))
 670     {
 671       clib_cuckoo_bucket_aux_t aux =
 672         CV (clib_cuckoo_bucket_version_bump_and_lock) (bucket2);
 673       CV (clib_cuckoo_set_locked_elt) (bucket2, elt, kvp, reduced_hash);
 674       aux =
 675         clib_cuckoo_bucket_aux_set_use_count (aux,
 676                                               clib_cuckoo_bucket_aux_get_use_count
 677                                               (aux) + 1);
 678       CV (clib_cuckoo_bucket_unlock) (bucket2, aux);
 679 #if CLIB_CUCKOO_DEBUG_COUNTERS
 680       ++h->fast_adds;
 681 #endif
 682       return CLIB_CUCKOO_ERROR_SUCCESS;
 683     }
 684   return CLIB_CUCKOO_ERROR_AGAIN;
 685 }
 686
 687 /**
 688  * perform garbage collection
 689  *
 690  * this function assumes there is no other thread touching the cuckoo hash,
 691  * not even a reader, it's meant to be called from main thread
 692  * in a stop-the-world situation
 693  */
 694 void CV (clib_cuckoo_garbage_collect) (CVT (clib_cuckoo) * h)
 695 {
 696   CLIB_MEMORY_BARRIER ();
 697   CVT (clib_cuckoo_bucket) * *b;
 698   /* *INDENT-OFF* */
 699   vec_foreach (b, h->to_be_freed)
 700   {
 701     if (*b == h->buckets)
 702       {
 703         continue;
 704       }
 705 #if CLIB_CUCKOO_DEBUG_GC
 706     fformat (stdout, "gc: free %p\n", *b);
 707 #endif
 708     vec_free (*b);
 709   }
 710   /* *INDENT-ON* */
 711   vec_free (h->to_be_freed);
 712   CLIB_MEMORY_BARRIER ();
 713 }
 714
 715 /**
 716  * expand and rehash a cuckoo hash
 717  *
 718  * 1. double the size of the hash table
 719  * 2. move items to new locations derived from the new size
 720  */
 721 static void CV (clib_cuckoo_rehash) (CVT (clib_cuckoo) * h)
 722 {
 723   CVT (clib_cuckoo_bucket) * old = h->buckets;
 724   uword old_nbuckets = vec_len (old);
 725   uword new_nbuckets = 2 * old_nbuckets;
 726   CVT (clib_cuckoo_bucket) * new =
 727     vec_dup_aligned (old, CLIB_CACHE_LINE_BYTES);
 728   /* allocate space */
 729   vec_validate_aligned (new, new_nbuckets - 1, CLIB_CACHE_LINE_BYTES);
 730   ASSERT (new_nbuckets == vec_len (new));
 731   /* store old pointer in to-be-freed list */
 732   vec_add1 (h->to_be_freed, old);
 733   /* mark new elements as free */
 734   CVT (clib_cuckoo_bucket) * bucket;
 735   for (bucket = new + old_nbuckets; bucket < vec_end (new); ++bucket)
 736     {
 737       clib_memset (bucket->elts, 0xff, sizeof (bucket->elts));
 738     }
 739   /*
 740    * this for loop manipulates the new (unseen) memory, so no locks
 741    * are required here
 742    */
 743   uword old_bucket_idx;
 744   for (old_bucket_idx = 0; old_bucket_idx < old_nbuckets; ++old_bucket_idx)
 745     {
 746       /* items in old bucket might be moved to new bucket */
 747       uword new_bucket_idx = old_bucket_idx + old_nbuckets;
 748       CVT (clib_cuckoo_bucket) * old_bucket = new + old_bucket_idx;
 749       CVT (clib_cuckoo_bucket) * new_bucket = new + new_bucket_idx;
 750       int i = 0;
 751       int moved = 0;
 752       clib_cuckoo_bucket_aux_t aux = old_bucket->aux;
 753       for (i = 0; i < clib_cuckoo_bucket_aux_get_use_count (aux); ++i)
 754         {
 755           CVT (clib_cuckoo_kv) * elt = old_bucket->elts + i;
 756           u64 hash = CV (clib_cuckoo_hash) (elt);
 757           clib_cuckoo_lookup_info_t old_lookup =
 758             CV (clib_cuckoo_calc_lookup) (old, hash);
 759           clib_cuckoo_lookup_info_t new_lookup =
 760             CV (clib_cuckoo_calc_lookup) (new, hash);
 761           if ((old_bucket_idx == old_lookup.bucket1 &&
 762                new_bucket_idx == new_lookup.bucket1) ||
 763               (old_bucket_idx == old_lookup.bucket2 &&
 764                new_bucket_idx == new_lookup.bucket2))
 765             {
 766               /* move the item to new bucket */
 767               CVT (clib_cuckoo_kv) * empty_elt = new_bucket->elts + moved;
 768               ASSERT (empty_elt);
 769               CV (clib_cuckoo_set_locked_elt)
 770                 (new_bucket, empty_elt, elt, old_bucket->reduced_hashes[i]);
 771               CV (clib_cuckoo_free_locked_elt) (elt);
 772               ++moved;
 773             }
 774         }
 775       if (moved)
 776         {
 777           CV (clib_cuckoo_bucket_tidy) (old_bucket);
 778           aux =
 779             clib_cuckoo_bucket_aux_set_use_count (aux,
 780                                                   clib_cuckoo_bucket_aux_get_use_count
 781                                                   (aux) - moved);
 782           old_bucket->aux = aux;
 783           aux = new_bucket->aux;
 784           aux =
 785             clib_cuckoo_bucket_aux_set_use_count (aux,
 786                                                   clib_cuckoo_bucket_aux_get_use_count
 787                                                   (aux) + moved);
 788           new_bucket->aux = aux;
 789         }
 790     }
 791   h->buckets = new;
 792 #if CLIB_CUCKOO_DEBUG_COUNTERS
 793   ++h->rehashes;
 794 #endif
 795   h->garbage_callback (h, h->garbage_ctx);
 796 }
 797
 798 static int CV (clib_cuckoo_bucket_search_internal) (CVT (clib_cuckoo) * h,
 799                                                     uword bucket,
 800                                                     CVT (clib_cuckoo_kv) *
 801                                                     kvp,
 802                                                     CVT (clib_cuckoo_kv) *
 803                                                     *found)
 804 {
 805   CVT (clib_cuckoo_bucket) * b = CV (clib_cuckoo_bucket_at_index) (h, bucket);
 806   int i;
 807   /* *INDENT-OFF* */
 808   clib_cuckoo_bucket_foreach_idx_unrolled (i, {
 809     CVT (clib_cuckoo_kv) *elt = &b->elts[i];
 810     if (CV (clib_cuckoo_key_compare) (elt->key, kvp->key))
 811       {
 812         *found = elt;
 813         return CLIB_CUCKOO_ERROR_SUCCESS;
 814       }
 815   });
 816   /* *INDENT-ON* */
 817   return CLIB_CUCKOO_ERROR_NOT_FOUND;
 818 }
 819
 820 int CV (clib_cuckoo_add_del) (CVT (clib_cuckoo) * h,
 821                               CVT (clib_cuckoo_kv) * kvp, int is_add,
 822                               int dont_overwrite)
 823 {
 824   CLIB_CUCKOO_DBG ("%s %U", is_add ? "Add" : "Del", CV (format_cuckoo_kvp),
 825                    kvp);
 826   clib_cuckoo_lookup_info_t lookup;
 827   u64 hash = CV (clib_cuckoo_hash) (kvp);
 828   u8 reduced_hash = clib_cuckoo_reduce_hash (hash);
 829   clib_spinlock_lock (&h->writer_lock);
 830 restart:
 831   lookup = CV (clib_cuckoo_calc_lookup) (h->buckets, hash);
 832   CVT (clib_cuckoo_bucket) * b =
 833     CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket1);
 834   CVT (clib_cuckoo_kv) * found;
 835   int rv =
 836     CV (clib_cuckoo_bucket_search_internal) (h, lookup.bucket1, kvp, &found);
 837   if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
 838     {
 839       ASSERT (CLIB_CUCKOO_ERROR_NOT_FOUND == rv);
 840       b = CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket2);
 841       rv = CV (clib_cuckoo_bucket_search_internal) (h, lookup.bucket2, kvp,
 842                                                     &found);
 843     }
 844   if (CLIB_CUCKOO_ERROR_SUCCESS == rv)
 845     {
 846       if (is_add)
 847         {
 848           if (dont_overwrite)
 849             {
 850               CLIB_CUCKOO_DBG ("Refused replacing existing %U",
 851                                CV (format_cuckoo_elt), found,
 852                                b->reduced_hashes[found - b->elts]);
 853               rv = CLIB_CUCKOO_ERROR_AGAIN;
 854             }
 855           else
 856             {
 857               /* prevent readers reading this bucket while we switch the values */
 858               clib_cuckoo_bucket_aux_t aux =
 859                 CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
 860               clib_memcpy (&found->value, &kvp->value, sizeof (found->value));
 861               CLIB_CUCKOO_DBG ("Replaced existing %U", CV (format_cuckoo_elt),
 862                                found, b->reduced_hashes[found - b->elts]);
 863               CV (clib_cuckoo_bucket_unlock) (b, aux);
 864               rv = CLIB_CUCKOO_ERROR_SUCCESS;
 865             }
 866         }
 867       else
 868         {
 869           CV (clib_cuckoo_free_elt_in_bucket) (b, found);
 870           rv = CLIB_CUCKOO_ERROR_SUCCESS;
 871         }
 872       CLIB_CUCKOO_DEEP_SELF_CHECK (h);
 873       goto unlock;
 874     }
 875   if (!is_add)
 876     {
 877       CLIB_CUCKOO_DBG ("%U not present in table", CV (format_cuckoo_kvp),
 878                        kvp);
 879       rv = CLIB_CUCKOO_ERROR_NOT_FOUND;
 880       goto unlock;
 881     }
 882   /* from this point on, it's add code only */
 883   ASSERT (CLIB_CUCKOO_ERROR_NOT_FOUND == rv);
 884   /* fast path: try to search for unoccupied slot in one of the buckets */
 885   rv = CV (clib_cuckoo_add_fast) (h, &lookup, kvp, reduced_hash);
 886   CLIB_CUCKOO_DEEP_SELF_CHECK (h);
 887   if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
 888     {
 889       CLIB_CUCKOO_DBG
 890         ("Fast insert failed, bucket 1: %wu, bucket 2: %wu\n%U%U",
 891          lookup.bucket1, lookup.bucket2, CV (format_cuckoo_bucket),
 892          CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket1),
 893          CV (format_cuckoo_bucket),
 894          CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket2));
 895       /* slow path */
 896       rv = CV (clib_cuckoo_add_slow) (h, kvp, &lookup, reduced_hash);
 897       CLIB_CUCKOO_DEEP_SELF_CHECK (h);
 898       if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
 899         {
 900           CLIB_CUCKOO_DBG ("Slow insert failed, rehash required:\n%U",
 901                            CV (format_cuckoo), h, 1);
 902           /* ultra slow path */
 903           CV (clib_cuckoo_rehash) (h);
 904           CLIB_CUCKOO_DEEP_SELF_CHECK (h);
 905           CLIB_CUCKOO_DBG ("Restarting add after rehash...");
 906           goto restart;
 907         }
 908     }
 909 unlock:
 910   clib_spinlock_unlock (&h->writer_lock);
 911   return rv;
 912 }
 913
 914 u8 *CV (format_cuckoo) (u8 * s, va_list * args)
 915 {
 916   CVT (clib_cuckoo) * h = va_arg (*args, CVT (clib_cuckoo) *);
 917   int verbose = va_arg (*args, int);
 918
 919   s = format (s, "Hash table %s\n", h->name ? h->name : "(unnamed)");
 920
 921   uword free = 0;
 922   uword used = 0;
 923   uword use_count_total = 0;
 924   float load_factor;
 925   CVT (clib_cuckoo_bucket) * b;
 926   /* *INDENT-OFF* */
 927   clib_cuckoo_foreach_bucket (b, h, {
 928     if (verbose)
 929       {
 930         s = format (s, "%U", CV (format_cuckoo_bucket), b);
 931       }
 932     int i;
 933     clib_cuckoo_bucket_foreach_idx (i)
 934     {
 935       CVT (clib_cuckoo_kv) *elt = &b->elts[i];
 936       if (CV (clib_cuckoo_kv_is_free) (elt))
 937         {
 938           ++free;
 939         }
 940       else
 941         {
 942           ++used;
 943         }
 944     }
 945     clib_cuckoo_bucket_aux_t aux = b->aux;
 946     use_count_total += clib_cuckoo_bucket_aux_get_use_count (aux);
 947   });
 948   /* *INDENT-ON* */
 949   s = format (s, "Used slots: %wu\n", used);
 950   s = format (s, "Use count total: %wu\n", use_count_total);
 951   s = format (s, "Free slots: %wu\n", free);
 952   if (free + used != 0)
 953     load_factor = ((float) used) / ((float) (free + used));
 954   else
 955     load_factor = 0.0;
 956   s = format (s, "Load factor: %.2f\n", load_factor);
 957 #if CLIB_CUCKOO_DEBUG_COUNTERS
 958   s = format (s, "BFS attempts limited by max steps: %lld\n",
 959               h->steps_exceeded);
 960   s = format (s, "BFS cutoffs due to empty queue: %lld\n",
 961               h->bfs_queue_emptied);
 962   s = format (s, "Fast adds: %lld\n", h->fast_adds);
 963   s = format (s, "Slow adds: %lld\n", h->slow_adds);
 964   s = format (s, "Rehashes: %lld\n", h->rehashes);
 965 #endif
 966   return s;
 967 }
 968
 969 float CV (clib_cuckoo_calculate_load_factor) (CVT (clib_cuckoo) * h)
 970 {
 971   uword nonfree = 0;
 972   uword all = 0;
 973   CVT (clib_cuckoo_bucket) * bucket;
 974   /* *INDENT-OFF* */
 975   clib_cuckoo_foreach_bucket (bucket, h, {
 976     int i;
 977     clib_cuckoo_bucket_foreach_idx (i)
 978     {
 979       CVT (clib_cuckoo_kv) *elt = bucket->elts + i;
 980       ++all;
 981       if (!CV (clib_cuckoo_kv_is_free) (elt))
 982         {
 983           ++nonfree;
 984         }
 985     }
 986   });
 987   /* *INDENT-ON* */
 988   if (all)
 989     return (float) nonfree / (float) all;
 990   else
 991     return 0.0;
 992 }
 993
 994 /** @endcond */
 995
 996 /*
 997  * fd.io coding-style-patch-verification: ON
 998  *
 999  * Local Variables:
1000  * eval: (c-set-style "gnu")
1001  * End:
1002  */