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