ck_rhs.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    1 /*
    2  * Copyright 2014-2015 Olivier Houchard.
    3  * Copyright 2012-2015 Samy Al Bahra.
    4  * All rights reserved.
    5  *
    6  * Redistribution and use in source and binary forms, with or without
    7  * modification, are permitted provided that the following conditions
    8  * are met:
    9  * 1. Redistributions of source code must retain the above copyright
   10  *    notice, this list of conditions and the following disclaimer.
   11  * 2. Redistributions in binary form must reproduce the above copyright
   12  *    notice, this list of conditions and the following disclaimer in the
   13  *    documentation and/or other materials provided with the distribution.
   14  *
   15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
   16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
   19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   22  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   23  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   24  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   25  * SUCH DAMAGE.
   26  */
   27 
   28 #include <ck_cc.h>
   29 #include <ck_rhs.h>
   30 #include <ck_limits.h>
   31 #include <ck_md.h>
   32 #include <ck_pr.h>
   33 #include <ck_stdint.h>
   34 #include <ck_stdbool.h>
   35 #include <ck_string.h>
   36 
   37 #include "ck_internal.h"
   38 
   39 #ifndef CK_RHS_PROBE_L1_SHIFT
   40 #define CK_RHS_PROBE_L1_SHIFT 3ULL
   41 #endif /* CK_RHS_PROBE_L1_SHIFT */
   42 
   43 #define CK_RHS_PROBE_L1 (1 << CK_RHS_PROBE_L1_SHIFT)
   44 #define CK_RHS_PROBE_L1_MASK (CK_RHS_PROBE_L1 - 1)
   45 
   46 #ifndef CK_RHS_PROBE_L1_DEFAULT
   47 #define CK_RHS_PROBE_L1_DEFAULT CK_MD_CACHELINE
   48 #endif
   49 
   50 #define CK_RHS_VMA_MASK ((uintptr_t)((1ULL << CK_MD_VMA_BITS) - 1))
   51 #define CK_RHS_VMA(x)   \
   52         ((void *)((uintptr_t)(x) & CK_RHS_VMA_MASK))
   53 
   54 #define CK_RHS_EMPTY     NULL
   55 #define CK_RHS_G                (1024)
   56 #define CK_RHS_G_MASK   (CK_RHS_G - 1)
   57 
   58 #if defined(CK_F_PR_LOAD_8) && defined(CK_F_PR_STORE_8)
   59 #define CK_RHS_WORD          uint8_t
   60 #define CK_RHS_WORD_MAX     UINT8_MAX
   61 #define CK_RHS_STORE(x, y)   ck_pr_store_8(x, y)
   62 #define CK_RHS_LOAD(x)       ck_pr_load_8(x)
   63 #elif defined(CK_F_PR_LOAD_16) && defined(CK_F_PR_STORE_16)
   64 #define CK_RHS_WORD          uint16_t
   65 #define CK_RHS_WORD_MAX     UINT16_MAX
   66 #define CK_RHS_STORE(x, y)   ck_pr_store_16(x, y)
   67 #define CK_RHS_LOAD(x)       ck_pr_load_16(x)
   68 #elif defined(CK_F_PR_LOAD_32) && defined(CK_F_PR_STORE_32)
   69 #define CK_RHS_WORD          uint32_t
   70 #define CK_RHS_WORD_MAX     UINT32_MAX
   71 #define CK_RHS_STORE(x, y)   ck_pr_store_32(x, y)
   72 #define CK_RHS_LOAD(x)       ck_pr_load_32(x)
   73 #else
   74 #error "ck_rhs is not supported on your platform."
   75 #endif
   76 
   77 #define CK_RHS_MAX_WANTED       0xffff
   78 
   79 enum ck_rhs_probe_behavior {
   80         CK_RHS_PROBE = 0,       /* Default behavior. */
   81         CK_RHS_PROBE_RH,        /* Short-circuit if RH slot found. */
   82         CK_RHS_PROBE_INSERT,    /* Short-circuit on probe bound if tombstone found. */
   83 
   84         CK_RHS_PROBE_ROBIN_HOOD,/* Look for the first slot available for the entry we are about to replace, only used to internally implement Robin Hood */
   85         CK_RHS_PROBE_NO_RH,     /* Don't do the RH dance */
   86 };
   87 struct ck_rhs_entry_desc {
   88         unsigned int probes;
   89         unsigned short wanted;
   90         CK_RHS_WORD probe_bound;
   91         bool in_rh;
   92         const void *entry;
   93 } CK_CC_ALIGN(16);
   94 
   95 struct ck_rhs_no_entry_desc {
   96         unsigned int probes;
   97         unsigned short wanted;
   98         CK_RHS_WORD probe_bound;
   99         bool in_rh;
  100 } CK_CC_ALIGN(8);
  101 
  102 typedef long ck_rhs_probe_cb_t(struct ck_rhs *hs,
  103     struct ck_rhs_map *map,
  104     unsigned long *n_probes,
  105     long *priority,
  106     unsigned long h,
  107     const void *key,
  108     const void **object,
  109     unsigned long probe_limit,
  110     enum ck_rhs_probe_behavior behavior);
  111 
  112 struct ck_rhs_map {
  113         unsigned int generation[CK_RHS_G];
  114         unsigned int probe_maximum;
  115         unsigned long mask;
  116         unsigned long step;
  117         unsigned int probe_limit;
  118         unsigned long n_entries;
  119         unsigned long capacity;
  120         unsigned long size;
  121         unsigned long max_entries;
  122         char offset_mask;
  123         union {
  124                 struct ck_rhs_entry_desc *descs;
  125                 struct ck_rhs_no_entry {
  126                         const void **entries;
  127                         struct ck_rhs_no_entry_desc *descs;
  128                 } no_entries;
  129         } entries;
  130         bool read_mostly;
  131         ck_rhs_probe_cb_t *probe_func;
  132 };
  133 
  134 static CK_CC_INLINE const void *
  135 ck_rhs_entry(struct ck_rhs_map *map, long offset)
  136 {
  137 
  138         if (map->read_mostly)
  139                 return (map->entries.no_entries.entries[offset]);
  140         else
  141                 return (map->entries.descs[offset].entry);
  142 }
  143 
  144 static CK_CC_INLINE const void **
  145 ck_rhs_entry_addr(struct ck_rhs_map *map, long offset)
  146 {
  147 
  148         if (map->read_mostly)
  149                 return (&map->entries.no_entries.entries[offset]);
  150         else
  151                 return (&map->entries.descs[offset].entry);
  152 }
  153 
  154 static CK_CC_INLINE struct ck_rhs_entry_desc *
  155 ck_rhs_desc(struct ck_rhs_map *map, long offset)
  156 {
  157 
  158         if (CK_CC_UNLIKELY(map->read_mostly))
  159                 return ((struct ck_rhs_entry_desc *)(void *)&map->entries.no_entries.descs[offset]);
  160         else
  161                 return (&map->entries.descs[offset]);
  162 }
  163 
  164 static CK_CC_INLINE void
  165 ck_rhs_wanted_inc(struct ck_rhs_map *map, long offset)
  166 {
  167 
  168         if (CK_CC_UNLIKELY(map->read_mostly))
  169                 map->entries.no_entries.descs[offset].wanted++;
  170         else
  171                 map->entries.descs[offset].wanted++;
  172 }
  173 
  174 static CK_CC_INLINE unsigned int
  175 ck_rhs_probes(struct ck_rhs_map *map, long offset)
  176 {
  177 
  178         if (CK_CC_UNLIKELY(map->read_mostly))
  179                 return (map->entries.no_entries.descs[offset].probes);
  180         else
  181                 return (map->entries.descs[offset].probes);
  182 }
  183 
  184 static CK_CC_INLINE void
  185 ck_rhs_set_probes(struct ck_rhs_map *map, long offset, unsigned int value)
  186 {
  187 
  188         if (CK_CC_UNLIKELY(map->read_mostly))
  189                 map->entries.no_entries.descs[offset].probes = value;
  190         else
  191                 map->entries.descs[offset].probes = value;
  192 }
  193 
  194 static CK_CC_INLINE CK_RHS_WORD
  195 ck_rhs_probe_bound(struct ck_rhs_map *map, long offset)
  196 {
  197 
  198         if (CK_CC_UNLIKELY(map->read_mostly))
  199                 return (map->entries.no_entries.descs[offset].probe_bound);
  200         else
  201                 return (map->entries.descs[offset].probe_bound);
  202 }
  203 
  204 static CK_CC_INLINE CK_RHS_WORD *
  205 ck_rhs_probe_bound_addr(struct ck_rhs_map *map, long offset)
  206 {
  207 
  208         if (CK_CC_UNLIKELY(map->read_mostly))
  209                 return (&map->entries.no_entries.descs[offset].probe_bound);
  210         else
  211                 return (&map->entries.descs[offset].probe_bound);
  212 }
  213 
  214 
  215 static CK_CC_INLINE bool
  216 ck_rhs_in_rh(struct ck_rhs_map *map, long offset)
  217 {
  218 
  219         if (CK_CC_UNLIKELY(map->read_mostly))
  220                 return (map->entries.no_entries.descs[offset].in_rh);
  221         else
  222                 return (map->entries.descs[offset].in_rh);
  223 }
  224 
  225 static CK_CC_INLINE void
  226 ck_rhs_set_rh(struct ck_rhs_map *map, long offset)
  227 {
  228 
  229         if (CK_CC_UNLIKELY(map->read_mostly))
  230                 map->entries.no_entries.descs[offset].in_rh = true;
  231         else
  232                 map->entries.descs[offset].in_rh = true;
  233 }
  234 
  235 static CK_CC_INLINE void
  236 ck_rhs_unset_rh(struct ck_rhs_map *map, long offset)
  237 {
  238 
  239         if (CK_CC_UNLIKELY(map->read_mostly))
  240                 map->entries.no_entries.descs[offset].in_rh = false;
  241         else
  242                 map->entries.descs[offset].in_rh = false;
  243 }
  244 
  245 
  246 #define CK_RHS_DEFAULT_LOAD_FACTOR      50
  247 
  248 static ck_rhs_probe_cb_t ck_rhs_map_probe;
  249 static ck_rhs_probe_cb_t ck_rhs_map_probe_rm;
  250 
  251 bool
  252 ck_rhs_set_load_factor(struct ck_rhs *hs, unsigned int load_factor)
  253 {
  254         struct ck_rhs_map *map = hs->map;
  255 
  256         if (load_factor == 0 || load_factor > 100)
  257                 return false;
  258 
  259         hs->load_factor = load_factor;
  260         map->max_entries = (map->capacity * (unsigned long)hs->load_factor) / 100;
  261         while (map->n_entries > map->max_entries) {
  262                 if (ck_rhs_grow(hs, map->capacity << 1) == false)
  263                         return false;
  264                 map = hs->map;
  265         }
  266         return true;
  267 }
  268 
  269 void
  270 ck_rhs_iterator_init(struct ck_rhs_iterator *iterator)
  271 {
  272 
  273         iterator->cursor = NULL;
  274         iterator->offset = 0;
  275         return;
  276 }
  277 
  278 bool
  279 ck_rhs_next(struct ck_rhs *hs, struct ck_rhs_iterator *i, void **key)
  280 {
  281         struct ck_rhs_map *map = hs->map;
  282         void *value;
  283 
  284         if (i->offset >= map->capacity)
  285                 return false;
  286 
  287         do {
  288                 value = CK_CC_DECONST_PTR(ck_rhs_entry(map, i->offset));
  289                 if (value != CK_RHS_EMPTY) {
  290 #ifdef CK_RHS_PP
  291                         if (hs->mode & CK_RHS_MODE_OBJECT)
  292                                 value = CK_RHS_VMA(value);
  293 #endif
  294                         i->offset++;
  295                         *key = value;
  296                         return true;
  297                 }
  298         } while (++i->offset < map->capacity);
  299 
  300         return false;
  301 }
  302 
  303 void
  304 ck_rhs_stat(struct ck_rhs *hs, struct ck_rhs_stat *st)
  305 {
  306         struct ck_rhs_map *map = hs->map;
  307 
  308         st->n_entries = map->n_entries;
  309         st->probe_maximum = map->probe_maximum;
  310         return;
  311 }
  312 
  313 unsigned long
  314 ck_rhs_count(struct ck_rhs *hs)
  315 {
  316 
  317         return hs->map->n_entries;
  318 }
  319 
  320 static void
  321 ck_rhs_map_destroy(struct ck_malloc *m, struct ck_rhs_map *map, bool defer)
  322 {
  323 
  324         m->free(map, map->size, defer);
  325         return;
  326 }
  327 
  328 void
  329 ck_rhs_destroy(struct ck_rhs *hs)
  330 {
  331 
  332         ck_rhs_map_destroy(hs->m, hs->map, false);
  333         return;
  334 }
  335 
  336 static struct ck_rhs_map *
  337 ck_rhs_map_create(struct ck_rhs *hs, unsigned long entries)
  338 {
  339         struct ck_rhs_map *map;
  340         unsigned long size, n_entries, limit;
  341 
  342         n_entries = ck_internal_power_2(entries);
  343         if (n_entries < CK_RHS_PROBE_L1)
  344                 n_entries = CK_RHS_PROBE_L1;
  345 
  346         if (hs->mode & CK_RHS_MODE_READ_MOSTLY)
  347                 size = sizeof(struct ck_rhs_map) +
  348                     (sizeof(void *) * n_entries +
  349                      sizeof(struct ck_rhs_no_entry_desc) * n_entries +
  350                      2 * CK_MD_CACHELINE - 1);
  351         else
  352                 size = sizeof(struct ck_rhs_map) +
  353                     (sizeof(struct ck_rhs_entry_desc) * n_entries +
  354                      CK_MD_CACHELINE - 1);
  355         map = hs->m->malloc(size);
  356         if (map == NULL)
  357                 return NULL;
  358         map->read_mostly = !!(hs->mode & CK_RHS_MODE_READ_MOSTLY);
  359 
  360         map->size = size;
  361         /* We should probably use a more intelligent heuristic for default probe length. */
  362         limit = ck_internal_max(n_entries >> (CK_RHS_PROBE_L1_SHIFT + 2), CK_RHS_PROBE_L1_DEFAULT);
  363         if (limit > UINT_MAX)
  364                 limit = UINT_MAX;
  365 
  366         map->probe_limit = (unsigned int)limit;
  367         map->probe_maximum = 0;
  368         map->capacity = n_entries;
  369         map->step = ck_cc_ffsl(n_entries);
  370         map->mask = n_entries - 1;
  371         map->n_entries = 0;
  372 
  373         map->max_entries = (map->capacity * (unsigned long)hs->load_factor) / 100;
  374         /* Align map allocation to cache line. */
  375         if (map->read_mostly) {
  376                 map->entries.no_entries.entries = (void *)(((uintptr_t)&map[1] +
  377                     CK_MD_CACHELINE - 1) & ~(CK_MD_CACHELINE - 1));
  378                 map->entries.no_entries.descs = (void *)(((uintptr_t)map->entries.no_entries.entries + (sizeof(void *) * n_entries) + CK_MD_CACHELINE - 1) &~ (CK_MD_CACHELINE - 1));
  379                 memset(map->entries.no_entries.entries, 0,
  380                     sizeof(void *) * n_entries);
  381                 memset(map->entries.no_entries.descs, 0,
  382                     sizeof(struct ck_rhs_no_entry_desc) * n_entries);
  383                 map->offset_mask = (CK_MD_CACHELINE / sizeof(void *)) - 1;
  384                 map->probe_func = ck_rhs_map_probe_rm;
  385 
  386         } else {
  387                 map->entries.descs = (void *)(((uintptr_t)&map[1] +
  388                     CK_MD_CACHELINE - 1) & ~(CK_MD_CACHELINE - 1));
  389                 memset(map->entries.descs, 0, sizeof(struct ck_rhs_entry_desc) * n_entries);
  390                 map->offset_mask = (CK_MD_CACHELINE / sizeof(struct ck_rhs_entry_desc)) - 1;
  391                 map->probe_func = ck_rhs_map_probe;
  392         }
  393         memset(map->generation, 0, sizeof map->generation);
  394 
  395         /* Commit entries purge with respect to map publication. */
  396         ck_pr_fence_store();
  397         return map;
  398 }
  399 
  400 bool
  401 ck_rhs_reset_size(struct ck_rhs *hs, unsigned long capacity)
  402 {
  403         struct ck_rhs_map *map, *previous;
  404 
  405         previous = hs->map;
  406         map = ck_rhs_map_create(hs, capacity);
  407         if (map == NULL)
  408                 return false;
  409 
  410         ck_pr_store_ptr(&hs->map, map);
  411         ck_rhs_map_destroy(hs->m, previous, true);
  412         return true;
  413 }
  414 
  415 bool
  416 ck_rhs_reset(struct ck_rhs *hs)
  417 {
  418         struct ck_rhs_map *previous;
  419 
  420         previous = hs->map;
  421         return ck_rhs_reset_size(hs, previous->capacity);
  422 }
  423 
  424 static inline unsigned long
  425 ck_rhs_map_probe_next(struct ck_rhs_map *map,
  426     unsigned long offset,
  427     unsigned long probes)
  428 {
  429 
  430         if (probes & map->offset_mask) {
  431                 offset = (offset &~ map->offset_mask) +
  432                     ((offset + 1) & map->offset_mask);
  433                 return offset;
  434         } else
  435                 return (offset + probes) & map->mask;
  436 }
  437 
  438 static inline unsigned long
  439 ck_rhs_map_probe_prev(struct ck_rhs_map *map, unsigned long offset,
  440     unsigned long probes)
  441 {
  442 
  443         if (probes & map->offset_mask) {
  444                 offset = (offset &~ map->offset_mask) + ((offset - 1) &
  445                     map->offset_mask);
  446                 return offset;
  447         } else
  448                 return ((offset - probes) & map->mask);
  449 }
  450 
  451 
  452 static inline void
  453 ck_rhs_map_bound_set(struct ck_rhs_map *m,
  454     unsigned long h,
  455     unsigned long n_probes)
  456 {
  457         unsigned long offset = h & m->mask;
  458         struct ck_rhs_entry_desc *desc;
  459 
  460         if (n_probes > m->probe_maximum)
  461                 ck_pr_store_uint(&m->probe_maximum, n_probes);
  462         if (!(m->read_mostly)) {
  463                 desc = &m->entries.descs[offset];
  464 
  465                 if (desc->probe_bound < n_probes) {
  466                         if (n_probes > CK_RHS_WORD_MAX)
  467                                 n_probes = CK_RHS_WORD_MAX;
  468 
  469                         CK_RHS_STORE(&desc->probe_bound, n_probes);
  470                         ck_pr_fence_store();
  471                 }
  472         }
  473 
  474         return;
  475 }
  476 
  477 static inline unsigned int
  478 ck_rhs_map_bound_get(struct ck_rhs_map *m, unsigned long h)
  479 {
  480         unsigned long offset = h & m->mask;
  481         unsigned int r = CK_RHS_WORD_MAX;
  482 
  483         if (m->read_mostly)
  484                 r = ck_pr_load_uint(&m->probe_maximum);
  485         else {
  486                 r = CK_RHS_LOAD(&m->entries.descs[offset].probe_bound);
  487                 if (r == CK_RHS_WORD_MAX)
  488                         r = ck_pr_load_uint(&m->probe_maximum);
  489         }
  490         return r;
  491 }
  492 
  493 bool
  494 ck_rhs_grow(struct ck_rhs *hs,
  495     unsigned long capacity)
  496 {
  497         struct ck_rhs_map *map, *update;
  498         const void *previous, *prev_saved;
  499         unsigned long k, offset, probes;
  500 
  501 restart:
  502         map = hs->map;
  503         if (map->capacity > capacity)
  504                 return false;
  505 
  506         update = ck_rhs_map_create(hs, capacity);
  507         if (update == NULL)
  508                 return false;
  509 
  510         for (k = 0; k < map->capacity; k++) {
  511                 unsigned long h;
  512 
  513                 prev_saved = previous = ck_rhs_entry(map, k);
  514                 if (previous == CK_RHS_EMPTY)
  515                         continue;
  516 
  517 #ifdef CK_RHS_PP
  518                 if (hs->mode & CK_RHS_MODE_OBJECT)
  519                         previous = CK_RHS_VMA(previous);
  520 #endif
  521 
  522                 h = hs->hf(previous, hs->seed);
  523                 offset = h & update->mask;
  524                 probes = 0;
  525 
  526                 for (;;) {
  527                         const void **cursor = ck_rhs_entry_addr(update, offset);
  528 
  529                         if (probes++ == update->probe_limit) {
  530                                 /*
  531                                  * We have hit the probe limit, map needs to be even larger.
  532                                  */
  533                                 ck_rhs_map_destroy(hs->m, update, false);
  534                                 capacity <<= 1;
  535                                 goto restart;
  536                         }
  537 
  538                         if (CK_CC_LIKELY(*cursor == CK_RHS_EMPTY)) {
  539                                 *cursor = prev_saved;
  540                                 update->n_entries++;
  541                                 ck_rhs_set_probes(update, offset, probes);
  542                                 ck_rhs_map_bound_set(update, h, probes);
  543                                 break;
  544                         } else if (ck_rhs_probes(update, offset) < probes) {
  545                                 const void *tmp = prev_saved;
  546                                 unsigned int old_probes;
  547                                 prev_saved = previous = *cursor;
  548 #ifdef CK_RHS_PP
  549                                 if (hs->mode & CK_RHS_MODE_OBJECT)
  550                                         previous = CK_RHS_VMA(previous);
  551 #endif
  552                                 *cursor = tmp;
  553                                 ck_rhs_map_bound_set(update, h, probes);
  554                                 h = hs->hf(previous, hs->seed);
  555                                 old_probes = ck_rhs_probes(update, offset);
  556                                 ck_rhs_set_probes(update, offset, probes);
  557                                 probes = old_probes - 1;
  558                                 continue;
  559                         }
  560                         ck_rhs_wanted_inc(update, offset);
  561                         offset = ck_rhs_map_probe_next(update, offset,  probes);
  562                 }
  563 
  564         }
  565 
  566         ck_pr_fence_store();
  567         ck_pr_store_ptr(&hs->map, update);
  568         ck_rhs_map_destroy(hs->m, map, true);
  569         return true;
  570 }
  571 
  572 bool
  573 ck_rhs_rebuild(struct ck_rhs *hs)
  574 {
  575 
  576         return ck_rhs_grow(hs, hs->map->capacity);
  577 }
  578 
  579 static long
  580 ck_rhs_map_probe_rm(struct ck_rhs *hs,
  581     struct ck_rhs_map *map,
  582     unsigned long *n_probes,
  583     long *priority,
  584     unsigned long h,
  585     const void *key,
  586     const void **object,
  587     unsigned long probe_limit,
  588     enum ck_rhs_probe_behavior behavior)
  589 {
  590         const void *k;
  591         const void *compare;
  592         long pr = -1;
  593         unsigned long offset, probes, opl;
  594 
  595 #ifdef CK_RHS_PP
  596         /* If we are storing object pointers, then we may leverage pointer packing. */
  597         unsigned long hv = 0;
  598 
  599         if (hs->mode & CK_RHS_MODE_OBJECT) {
  600                 hv = (h >> 25) & CK_RHS_KEY_MASK;
  601                 compare = CK_RHS_VMA(key);
  602         } else {
  603                 compare = key;
  604         }
  605 #else
  606         compare = key;
  607 #endif
  608         *object = NULL;
  609         if (behavior != CK_RHS_PROBE_ROBIN_HOOD) {
  610                 probes = 0;
  611                 offset = h & map->mask;
  612         } else {
  613                 /* Restart from the bucket we were previously in */
  614                 probes = *n_probes;
  615                 offset = ck_rhs_map_probe_next(map, *priority,
  616                     probes);
  617         }
  618         opl = probe_limit;
  619 
  620         for (;;) {
  621                 if (probes++ == probe_limit) {
  622                         if (probe_limit == opl || pr != -1) {
  623                                 k = CK_RHS_EMPTY;
  624                                 goto leave;
  625                         }
  626                         /*
  627                          * If no eligible slot has been found yet, continue probe
  628                          * sequence with original probe limit.
  629                          */
  630                         probe_limit = opl;
  631                 }
  632                 k = ck_pr_load_ptr(&map->entries.no_entries.entries[offset]);
  633                 if (k == CK_RHS_EMPTY)
  634                         goto leave;
  635 
  636                 if (behavior != CK_RHS_PROBE_NO_RH) {
  637                         struct ck_rhs_entry_desc *desc = (void *)&map->entries.no_entries.descs[offset];
  638 
  639                         if (pr == -1 &&
  640                             desc->in_rh == false && desc->probes < probes) {
  641                                 pr = offset;
  642                                 *n_probes = probes;
  643 
  644                                 if (behavior == CK_RHS_PROBE_RH ||
  645                                     behavior == CK_RHS_PROBE_ROBIN_HOOD) {
  646                                         k = CK_RHS_EMPTY;
  647                                         goto leave;
  648                                 }
  649                         }
  650                 }
  651 
  652                 if (behavior != CK_RHS_PROBE_ROBIN_HOOD) {
  653 #ifdef CK_RHS_PP
  654                         if (hs->mode & CK_RHS_MODE_OBJECT) {
  655                                 if (((uintptr_t)k >> CK_MD_VMA_BITS) != hv) {
  656                                         offset = ck_rhs_map_probe_next(map, offset, probes);
  657                                         continue;
  658                                 }
  659 
  660                                 k = CK_RHS_VMA(k);
  661                         }
  662 #endif
  663 
  664                         if (k == compare)
  665                                 goto leave;
  666 
  667                         if (hs->compare == NULL) {
  668                                 offset = ck_rhs_map_probe_next(map, offset, probes);
  669                                 continue;
  670                         }
  671 
  672                         if (hs->compare(k, key) == true)
  673                                 goto leave;
  674                 }
  675                 offset = ck_rhs_map_probe_next(map, offset, probes);
  676         }
  677 leave:
  678         if (probes > probe_limit) {
  679                 offset = -1;
  680         } else {
  681                 *object = k;
  682         }
  683 
  684         if (pr == -1)
  685                 *n_probes = probes;
  686 
  687         *priority = pr;
  688         return offset;
  689 }
  690 
  691 static long
  692 ck_rhs_map_probe(struct ck_rhs *hs,
  693     struct ck_rhs_map *map,
  694     unsigned long *n_probes,
  695     long *priority,
  696     unsigned long h,
  697     const void *key,
  698     const void **object,
  699     unsigned long probe_limit,
  700     enum ck_rhs_probe_behavior behavior)
  701 {
  702         const void *k;
  703         const void *compare;
  704         long pr = -1;
  705         unsigned long offset, probes, opl;
  706 
  707 #ifdef CK_RHS_PP
  708         /* If we are storing object pointers, then we may leverage pointer packing. */
  709         unsigned long hv = 0;
  710 
  711         if (hs->mode & CK_RHS_MODE_OBJECT) {
  712                 hv = (h >> 25) & CK_RHS_KEY_MASK;
  713                 compare = CK_RHS_VMA(key);
  714         } else {
  715                 compare = key;
  716         }
  717 #else
  718         compare = key;
  719 #endif
  720 
  721         *object = NULL;
  722         if (behavior != CK_RHS_PROBE_ROBIN_HOOD) {
  723                 probes = 0;
  724                 offset = h & map->mask;
  725         } else {
  726                 /* Restart from the bucket we were previously in */
  727                 probes = *n_probes;
  728                 offset = ck_rhs_map_probe_next(map, *priority,
  729                     probes);
  730         }
  731         opl = probe_limit;
  732         if (behavior == CK_RHS_PROBE_INSERT)
  733                 probe_limit = ck_rhs_map_bound_get(map, h);
  734 
  735         for (;;) {
  736                 if (probes++ == probe_limit) {
  737                         if (probe_limit == opl || pr != -1) {
  738                                 k = CK_RHS_EMPTY;
  739                                 goto leave;
  740                         }
  741                         /*
  742                          * If no eligible slot has been found yet, continue probe
  743                          * sequence with original probe limit.
  744                          */
  745                         probe_limit = opl;
  746                 }
  747                 k = ck_pr_load_ptr(&map->entries.descs[offset].entry);
  748                 if (k == CK_RHS_EMPTY)
  749                         goto leave;
  750                 if ((behavior != CK_RHS_PROBE_NO_RH)) {
  751                         struct ck_rhs_entry_desc *desc = &map->entries.descs[offset];
  752 
  753                         if (pr == -1 &&
  754                             desc->in_rh == false && desc->probes < probes) {
  755                                 pr = offset;
  756                                 *n_probes = probes;
  757 
  758                                 if (behavior == CK_RHS_PROBE_RH ||
  759                                     behavior == CK_RHS_PROBE_ROBIN_HOOD) {
  760                                         k = CK_RHS_EMPTY;
  761                                         goto leave;
  762                                 }
  763                         }
  764                 }
  765 
  766                 if (behavior != CK_RHS_PROBE_ROBIN_HOOD) {
  767 #ifdef CK_RHS_PP
  768                         if (hs->mode & CK_RHS_MODE_OBJECT) {
  769                                 if (((uintptr_t)k >> CK_MD_VMA_BITS) != hv) {
  770                                         offset = ck_rhs_map_probe_next(map, offset, probes);
  771                                         continue;
  772                                 }
  773 
  774                                 k = CK_RHS_VMA(k);
  775                         }
  776 #endif
  777 
  778                         if (k == compare)
  779                                 goto leave;
  780 
  781                         if (hs->compare == NULL) {
  782                                 offset = ck_rhs_map_probe_next(map, offset, probes);
  783                                 continue;
  784                         }
  785 
  786                         if (hs->compare(k, key) == true)
  787                                 goto leave;
  788                 }
  789                 offset = ck_rhs_map_probe_next(map, offset, probes);
  790         }
  791 leave:
  792         if (probes > probe_limit) {
  793                 offset = -1;
  794         } else {
  795                 *object = k;
  796         }
  797 
  798         if (pr == -1)
  799                 *n_probes = probes;
  800 
  801         *priority = pr;
  802         return offset;
  803 }
  804 
  805 static inline const void *
  806 ck_rhs_marshal(unsigned int mode, const void *key, unsigned long h)
  807 {
  808 #ifdef CK_RHS_PP
  809         const void *insert;
  810 
  811         if (mode & CK_RHS_MODE_OBJECT) {
  812                 insert = (void *)((uintptr_t)CK_RHS_VMA(key) | ((h >> 25) << CK_MD_VMA_BITS));
  813         } else {
  814                 insert = key;
  815         }
  816 
  817         return insert;
  818 #else
  819         (void)mode;
  820         (void)h;
  821 
  822         return key;
  823 #endif
  824 }
  825 
  826 bool
  827 ck_rhs_gc(struct ck_rhs *hs)
  828 {
  829         unsigned long i;
  830         struct ck_rhs_map *map = hs->map;
  831 
  832         unsigned int max_probes = 0;
  833         for (i = 0; i < map->capacity; i++) {
  834                 if (ck_rhs_probes(map, i) > max_probes)
  835                         max_probes = ck_rhs_probes(map, i);
  836         }
  837         map->probe_maximum = max_probes;
  838         return true;
  839 }
  840 
  841 static void
  842 ck_rhs_add_wanted(struct ck_rhs *hs, long end_offset, long old_slot,
  843         unsigned long h)
  844 {
  845         struct ck_rhs_map *map = hs->map;
  846         long offset;
  847         unsigned int probes = 1;
  848         bool found_slot = false;
  849         struct ck_rhs_entry_desc *desc;
  850 
  851         offset = h & map->mask;
  852 
  853         if (old_slot == -1)
  854                 found_slot = true;
  855         while (offset != end_offset) {
  856                 if (offset == old_slot)
  857                         found_slot = true;
  858                 if (found_slot) {
  859                         desc = ck_rhs_desc(map, offset);
  860                         if (desc->wanted < CK_RHS_MAX_WANTED)
  861                                 desc->wanted++;
  862                 }
  863                 offset = ck_rhs_map_probe_next(map, offset, probes);
  864                 probes++;
  865         }
  866 }
  867 
  868 static unsigned long
  869 ck_rhs_remove_wanted(struct ck_rhs *hs, long offset, long limit)
  870 {
  871         struct ck_rhs_map *map = hs->map;
  872         int probes = ck_rhs_probes(map, offset);
  873         bool do_remove = true;
  874         struct ck_rhs_entry_desc *desc;
  875 
  876         while (probes > 1) {
  877                 probes--;
  878                 offset = ck_rhs_map_probe_prev(map, offset, probes);
  879                 if (offset == limit)
  880                         do_remove = false;
  881                 if (do_remove) {
  882                         desc = ck_rhs_desc(map, offset);
  883                         if (desc->wanted != CK_RHS_MAX_WANTED)
  884                                 desc->wanted--;
  885                 }
  886         }
  887         return offset;
  888 }
  889 
  890 static long
  891 ck_rhs_get_first_offset(struct ck_rhs_map *map, unsigned long offset, unsigned int probes)
  892 {
  893         while (probes > (unsigned long)map->offset_mask + 1) {
  894                 offset -= ((probes - 1) &~ map->offset_mask);
  895                 offset &= map->mask;
  896                 offset = (offset &~ map->offset_mask) +
  897                     ((offset - map->offset_mask) & map->offset_mask);
  898                 probes -= map->offset_mask + 1;
  899         }
  900         return ((offset &~ map->offset_mask) + ((offset - (probes - 1)) & map->offset_mask));
  901 }
  902 
  903 #define CK_RHS_MAX_RH   512
  904 
  905 static int
  906 ck_rhs_put_robin_hood(struct ck_rhs *hs,
  907     long orig_slot, struct ck_rhs_entry_desc *desc)
  908 {
  909         long slot, first;
  910         const void *object, *insert;
  911         unsigned long n_probes;
  912         struct ck_rhs_map *map;
  913         unsigned long h = 0;
  914         long prev;
  915         void *key;
  916         long prevs[CK_RHS_MAX_RH];
  917         unsigned int prevs_nb = 0;
  918         unsigned int i;
  919 
  920         map = hs->map;
  921         first = orig_slot;
  922         n_probes = desc->probes;
  923 restart:
  924         key = CK_CC_DECONST_PTR(ck_rhs_entry(map, first));
  925         insert = key;
  926 #ifdef CK_RHS_PP
  927         if (hs->mode & CK_RHS_MODE_OBJECT)
  928             key = CK_RHS_VMA(key);
  929 #endif
  930         orig_slot = first;
  931         ck_rhs_set_rh(map, orig_slot);
  932 
  933         slot = map->probe_func(hs, map, &n_probes, &first, h, key, &object,
  934             map->probe_limit, prevs_nb == CK_RHS_MAX_RH ?
  935             CK_RHS_PROBE_NO_RH : CK_RHS_PROBE_ROBIN_HOOD);
  936 
  937         if (slot == -1 && first == -1) {
  938                 if (ck_rhs_grow(hs, map->capacity << 1) == false) {
  939                         desc->in_rh = false;
  940 
  941                         for (i = 0; i < prevs_nb; i++)
  942                                 ck_rhs_unset_rh(map, prevs[i]);
  943 
  944                         return -1;
  945                 }
  946 
  947                 return 1;
  948         }
  949 
  950         if (first != -1) {
  951                 desc = ck_rhs_desc(map, first);
  952                 int old_probes = desc->probes;
  953 
  954                 desc->probes = n_probes;
  955                 h = ck_rhs_get_first_offset(map, first, n_probes);
  956                 ck_rhs_map_bound_set(map, h, n_probes);
  957                 prev = orig_slot;
  958                 prevs[prevs_nb++] = prev;
  959                 n_probes = old_probes;
  960                 goto restart;
  961         } else {
  962                 /* An empty slot was found. */
  963                 h =  ck_rhs_get_first_offset(map, slot, n_probes);
  964                 ck_rhs_map_bound_set(map, h, n_probes);
  965                 ck_pr_store_ptr(ck_rhs_entry_addr(map, slot), insert);
  966                 ck_pr_inc_uint(&map->generation[h & CK_RHS_G_MASK]);
  967                 ck_pr_fence_atomic_store();
  968                 ck_rhs_set_probes(map, slot, n_probes);
  969                 desc->in_rh = 0;
  970                 ck_rhs_add_wanted(hs, slot, orig_slot, h);
  971         }
  972         while (prevs_nb > 0) {
  973                 prev = prevs[--prevs_nb];
  974                 ck_pr_store_ptr(ck_rhs_entry_addr(map, orig_slot),
  975                     ck_rhs_entry(map, prev));
  976                 h = ck_rhs_get_first_offset(map, orig_slot,
  977                     desc->probes);
  978                 ck_rhs_add_wanted(hs, orig_slot, prev, h);
  979                 ck_pr_inc_uint(&map->generation[h & CK_RHS_G_MASK]);
  980                 ck_pr_fence_atomic_store();
  981                 orig_slot = prev;
  982                 desc->in_rh = false;
  983                 desc = ck_rhs_desc(map, orig_slot);
  984         }
  985         return 0;
  986 }
  987 
  988 static void
  989 ck_rhs_do_backward_shift_delete(struct ck_rhs *hs, long slot)
  990 {
  991         struct ck_rhs_map *map = hs->map;
  992         struct ck_rhs_entry_desc *desc, *new_desc = NULL;
  993         unsigned long h;
  994 
  995         desc = ck_rhs_desc(map, slot);
  996         h = ck_rhs_remove_wanted(hs, slot, -1);
  997         while (desc->wanted > 0) {
  998                 unsigned long offset = 0, tmp_offset;
  999                 unsigned long wanted_probes = 1;
 1000                 unsigned int probe = 0;
 1001                 unsigned int max_probes;
 1002 
 1003                 /* Find a successor */
 1004                 while (wanted_probes < map->probe_maximum) {
 1005                         probe = wanted_probes;
 1006                         offset = ck_rhs_map_probe_next(map, slot, probe);
 1007                         while (probe < map->probe_maximum) {
 1008                                 new_desc = ck_rhs_desc(map, offset);
 1009                                 if (new_desc->probes == probe + 1)
 1010                                         break;
 1011                                 probe++;
 1012                                 offset = ck_rhs_map_probe_next(map, offset,
 1013                                     probe);
 1014                         }
 1015                         if (probe < map->probe_maximum)
 1016                                 break;
 1017                         wanted_probes++;
 1018                 }
 1019                 if (!(wanted_probes < map->probe_maximum)) {
 1020                         desc->wanted = 0;
 1021                         break;
 1022                 }
 1023                 desc->probes = wanted_probes;
 1024                 h = ck_rhs_remove_wanted(hs, offset, slot);
 1025                 ck_pr_store_ptr(ck_rhs_entry_addr(map, slot),
 1026                     ck_rhs_entry(map, offset));
 1027                 ck_pr_inc_uint(&map->generation[h & CK_RHS_G_MASK]);
 1028                 ck_pr_fence_atomic_store();
 1029                 if (wanted_probes < CK_RHS_WORD_MAX) {
 1030                         struct ck_rhs_entry_desc *hdesc = ck_rhs_desc(map, h);
 1031                         if (hdesc->wanted == 1)
 1032                                 CK_RHS_STORE(&hdesc->probe_bound,
 1033                                     wanted_probes);
 1034                         else if (hdesc->probe_bound == CK_RHS_WORD_MAX ||
 1035                             hdesc->probe_bound == new_desc->probes) {
 1036                                 probe++;
 1037                                 if (hdesc->probe_bound == CK_RHS_WORD_MAX)
 1038                                         max_probes = map->probe_maximum;
 1039                                 else {
 1040                                         max_probes = hdesc->probe_bound;
 1041                                         max_probes--;
 1042                                 }
 1043                                 tmp_offset = ck_rhs_map_probe_next(map, offset,
 1044                                     probe);
 1045                                 while (probe < max_probes) {
 1046                                         if (h == (unsigned long)ck_rhs_get_first_offset(map, tmp_offset, probe))
 1047                                                 break;
 1048                                         probe++;
 1049                                         tmp_offset = ck_rhs_map_probe_next(map, tmp_offset, probe);
 1050                                 }
 1051                                 if (probe == max_probes)
 1052                                         CK_RHS_STORE(&hdesc->probe_bound,
 1053                                             wanted_probes);
 1054                         }
 1055                 }
 1056                 if (desc->wanted < CK_RHS_MAX_WANTED)
 1057                         desc->wanted--;
 1058                 slot = offset;
 1059                 desc = new_desc;
 1060         }
 1061         ck_pr_store_ptr(ck_rhs_entry_addr(map, slot), CK_RHS_EMPTY);
 1062         if ((desc->probes - 1) < CK_RHS_WORD_MAX)
 1063                 CK_RHS_STORE(ck_rhs_probe_bound_addr(map, h),
 1064                     desc->probes - 1);
 1065         desc->probes = 0;
 1066 }
 1067 
 1068 bool
 1069 ck_rhs_fas(struct ck_rhs *hs,
 1070     unsigned long h,
 1071     const void *key,
 1072     void **previous)
 1073 {
 1074         long slot, first;
 1075         const void *object;
 1076         const void *insert;
 1077         unsigned long n_probes;
 1078         struct ck_rhs_map *map = hs->map;
 1079         struct ck_rhs_entry_desc *desc, *desc2;
 1080 
 1081         *previous = NULL;
 1082 restart:
 1083         slot = map->probe_func(hs, map, &n_probes, &first, h, key, &object,
 1084             ck_rhs_map_bound_get(map, h), CK_RHS_PROBE);
 1085 
 1086         /* Replacement semantics presume existence. */
 1087         if (object == NULL)
 1088                 return false;
 1089 
 1090         insert = ck_rhs_marshal(hs->mode, key, h);
 1091 
 1092         if (first != -1) {
 1093                 int ret;
 1094 
 1095                 desc = ck_rhs_desc(map, slot);
 1096                 desc2 = ck_rhs_desc(map, first);
 1097                 desc->in_rh = true;
 1098                 ret = ck_rhs_put_robin_hood(hs, first, desc2);
 1099                 desc->in_rh = false;
 1100                 if (CK_CC_UNLIKELY(ret == 1))
 1101                         goto restart;
 1102                 else if (CK_CC_UNLIKELY(ret != 0))
 1103                         return false;
 1104                 ck_pr_store_ptr(ck_rhs_entry_addr(map, first), insert);
 1105                 ck_pr_inc_uint(&map->generation[h & CK_RHS_G_MASK]);
 1106                 ck_pr_fence_atomic_store();
 1107                 desc2->probes = n_probes;
 1108                 ck_rhs_add_wanted(hs, first, -1, h);
 1109                 ck_rhs_do_backward_shift_delete(hs, slot);
 1110         } else {
 1111                 ck_pr_store_ptr(ck_rhs_entry_addr(map, slot), insert);
 1112                 ck_rhs_set_probes(map, slot, n_probes);
 1113         }
 1114         *previous = CK_CC_DECONST_PTR(object);
 1115         return true;
 1116 }
 1117 
 1118 /*
 1119  * An apply function takes two arguments. The first argument is a pointer to a
 1120  * pre-existing object. The second argument is a pointer to the fifth argument
 1121  * passed to ck_hs_apply. If a non-NULL pointer is passed to the first argument
 1122  * and the return value of the apply function is NULL, then the pre-existing
 1123  * value is deleted. If the return pointer is the same as the one passed to the
 1124  * apply function then no changes are made to the hash table.  If the first
 1125  * argument is non-NULL and the return pointer is different than that passed to
 1126  * the apply function, then the pre-existing value is replaced. For
 1127  * replacement, it is required that the value itself is identical to the
 1128  * previous value.
 1129  */
 1130 bool
 1131 ck_rhs_apply(struct ck_rhs *hs,
 1132     unsigned long h,
 1133     const void *key,
 1134     ck_rhs_apply_fn_t *fn,
 1135     void *cl)
 1136 {
 1137         const void *insert;
 1138         const void  *object, *delta = false;
 1139         unsigned long n_probes;
 1140         long slot, first;
 1141         struct ck_rhs_map *map;
 1142         bool delta_set = false;
 1143 
 1144 restart:
 1145         map = hs->map;
 1146 
 1147         slot = map->probe_func(hs, map, &n_probes, &first, h, key, &object, map->probe_limit, CK_RHS_PROBE_INSERT);
 1148         if (slot == -1 && first == -1) {
 1149                 if (ck_rhs_grow(hs, map->capacity << 1) == false)
 1150                         return false;
 1151 
 1152                 goto restart;
 1153         }
 1154         if (!delta_set) {
 1155                 delta = fn(CK_CC_DECONST_PTR(object), cl);
 1156                 delta_set = true;
 1157         }
 1158 
 1159         if (delta == NULL) {
 1160                 /*
 1161                  * The apply function has requested deletion. If the object doesn't exist,
 1162                  * then exit early.
 1163                  */
 1164                 if (CK_CC_UNLIKELY(object == NULL))
 1165                         return true;
 1166 
 1167                 /* Otherwise, delete it. */
 1168                 ck_rhs_do_backward_shift_delete(hs, slot);
 1169                 return true;
 1170         }
 1171 
 1172         /* The apply function has not requested hash set modification so exit early. */
 1173         if (delta == object)
 1174                 return true;
 1175 
 1176         /* A modification or insertion has been requested. */
 1177         ck_rhs_map_bound_set(map, h, n_probes);
 1178 
 1179         insert = ck_rhs_marshal(hs->mode, delta, h);
 1180         if (first != -1) {
 1181                 /*
 1182                  * This follows the same semantics as ck_hs_set, please refer to that
 1183                  * function for documentation.
 1184                  */
 1185                 struct ck_rhs_entry_desc *desc = NULL, *desc2;
 1186                 if (slot != -1) {
 1187                         desc = ck_rhs_desc(map, slot);
 1188                         desc->in_rh = true;
 1189                 }
 1190                 desc2 = ck_rhs_desc(map, first);
 1191                 int ret = ck_rhs_put_robin_hood(hs, first, desc2);
 1192                 if (slot != -1)
 1193                         desc->in_rh = false;
 1194 
 1195                 if (CK_CC_UNLIKELY(ret == 1))
 1196                         goto restart;
 1197                 if (CK_CC_UNLIKELY(ret == -1))
 1198                         return false;
 1199                 /* If an earlier bucket was found, then store entry there. */
 1200                 ck_pr_store_ptr(ck_rhs_entry_addr(map, first), insert);
 1201                 desc2->probes = n_probes;
 1202                 /*
 1203                  * If a duplicate key was found, then delete it after
 1204                  * signaling concurrent probes to restart. Optionally,
 1205                  * it is possible to install tombstone after grace
 1206                  * period if we can guarantee earlier position of
 1207                  * duplicate key.
 1208                  */
 1209                 ck_rhs_add_wanted(hs, first, -1, h);
 1210                 if (object != NULL) {
 1211                         ck_pr_inc_uint(&map->generation[h & CK_RHS_G_MASK]);
 1212                         ck_pr_fence_atomic_store();
 1213                         ck_rhs_do_backward_shift_delete(hs, slot);
 1214                 }
 1215         } else {
 1216                 /*
 1217                  * If we are storing into same slot, then atomic store is sufficient
 1218                  * for replacement.
 1219                  */
 1220                 ck_pr_store_ptr(ck_rhs_entry_addr(map, slot), insert);
 1221                 ck_rhs_set_probes(map, slot, n_probes);
 1222                 if (object == NULL)
 1223                         ck_rhs_add_wanted(hs, slot, -1, h);
 1224         }
 1225 
 1226         if (object == NULL) {
 1227                 map->n_entries++;
 1228                 if ((map->n_entries ) > map->max_entries)
 1229                         ck_rhs_grow(hs, map->capacity << 1);
 1230         }
 1231         return true;
 1232 }
 1233 
 1234 bool
 1235 ck_rhs_set(struct ck_rhs *hs,
 1236     unsigned long h,
 1237     const void *key,
 1238     void **previous)
 1239 {
 1240         long slot, first;
 1241         const void *object;
 1242         const void *insert;
 1243         unsigned long n_probes;
 1244         struct ck_rhs_map *map;
 1245 
 1246         *previous = NULL;
 1247 
 1248 restart:
 1249         map = hs->map;
 1250 
 1251         slot = map->probe_func(hs, map, &n_probes, &first, h, key, &object, map->probe_limit, CK_RHS_PROBE_INSERT);
 1252         if (slot == -1 && first == -1) {
 1253                 if (ck_rhs_grow(hs, map->capacity << 1) == false)
 1254                         return false;
 1255 
 1256                 goto restart;
 1257         }
 1258         ck_rhs_map_bound_set(map, h, n_probes);
 1259         insert = ck_rhs_marshal(hs->mode, key, h);
 1260 
 1261         if (first != -1) {
 1262                 struct ck_rhs_entry_desc *desc = NULL, *desc2;
 1263                 if (slot != -1) {
 1264                         desc = ck_rhs_desc(map, slot);
 1265                         desc->in_rh = true;
 1266                 }
 1267                 desc2 = ck_rhs_desc(map, first);
 1268                 int ret = ck_rhs_put_robin_hood(hs, first, desc2);
 1269                 if (slot != -1)
 1270                         desc->in_rh = false;
 1271 
 1272                 if (CK_CC_UNLIKELY(ret == 1))
 1273                         goto restart;
 1274                 if (CK_CC_UNLIKELY(ret == -1))
 1275                         return false;
 1276                 /* If an earlier bucket was found, then store entry there. */
 1277                 ck_pr_store_ptr(ck_rhs_entry_addr(map, first), insert);
 1278                 desc2->probes = n_probes;
 1279                 /*
 1280                  * If a duplicate key was found, then delete it after
 1281                  * signaling concurrent probes to restart. Optionally,
 1282                  * it is possible to install tombstone after grace
 1283                  * period if we can guarantee earlier position of
 1284                  * duplicate key.
 1285                  */
 1286                 ck_rhs_add_wanted(hs, first, -1, h);
 1287                 if (object != NULL) {
 1288                         ck_pr_inc_uint(&map->generation[h & CK_RHS_G_MASK]);
 1289                         ck_pr_fence_atomic_store();
 1290                         ck_rhs_do_backward_shift_delete(hs, slot);
 1291                 }
 1292 
 1293         } else {
 1294                 /*
 1295                  * If we are storing into same slot, then atomic store is sufficient
 1296                  * for replacement.
 1297                  */
 1298                 ck_pr_store_ptr(ck_rhs_entry_addr(map, slot), insert);
 1299                 ck_rhs_set_probes(map, slot, n_probes);
 1300                 if (object == NULL)
 1301                         ck_rhs_add_wanted(hs, slot, -1, h);
 1302         }
 1303 
 1304         if (object == NULL) {
 1305                 map->n_entries++;
 1306                 if ((map->n_entries ) > map->max_entries)
 1307                         ck_rhs_grow(hs, map->capacity << 1);
 1308         }
 1309 
 1310         *previous = CK_CC_DECONST_PTR(object);
 1311         return true;
 1312 }
 1313 
 1314 static bool
 1315 ck_rhs_put_internal(struct ck_rhs *hs,
 1316     unsigned long h,
 1317     const void *key,
 1318     enum ck_rhs_probe_behavior behavior)
 1319 {
 1320         long slot, first;
 1321         const void *object;
 1322         const void *insert;
 1323         unsigned long n_probes;
 1324         struct ck_rhs_map *map;
 1325 
 1326 restart:
 1327         map = hs->map;
 1328 
 1329         slot = map->probe_func(hs, map, &n_probes, &first, h, key, &object,
 1330             map->probe_limit, behavior);
 1331 
 1332         if (slot == -1 && first == -1) {
 1333                 if (ck_rhs_grow(hs, map->capacity << 1) == false)
 1334                         return false;
 1335 
 1336                 goto restart;
 1337         }
 1338 
 1339         /* Fail operation if a match was found. */
 1340         if (object != NULL)
 1341                 return false;
 1342 
 1343         ck_rhs_map_bound_set(map, h, n_probes);
 1344         insert = ck_rhs_marshal(hs->mode, key, h);
 1345 
 1346         if (first != -1) {
 1347                 struct ck_rhs_entry_desc *desc = ck_rhs_desc(map, first);
 1348                 int ret = ck_rhs_put_robin_hood(hs, first, desc);
 1349                 if (CK_CC_UNLIKELY(ret == 1))
 1350                         return ck_rhs_put_internal(hs, h, key, behavior);
 1351                 else if (CK_CC_UNLIKELY(ret == -1))
 1352                         return false;
 1353                 /* Insert key into first bucket in probe sequence. */
 1354                 ck_pr_store_ptr(ck_rhs_entry_addr(map, first), insert);
 1355                 desc->probes = n_probes;
 1356                 ck_rhs_add_wanted(hs, first, -1, h);
 1357         } else {
 1358                 /* An empty slot was found. */
 1359                 ck_pr_store_ptr(ck_rhs_entry_addr(map, slot), insert);
 1360                 ck_rhs_set_probes(map, slot, n_probes);
 1361                 ck_rhs_add_wanted(hs, slot, -1, h);
 1362         }
 1363 
 1364         map->n_entries++;
 1365         if ((map->n_entries ) > map->max_entries)
 1366                 ck_rhs_grow(hs, map->capacity << 1);
 1367         return true;
 1368 }
 1369 
 1370 bool
 1371 ck_rhs_put(struct ck_rhs *hs,
 1372     unsigned long h,
 1373     const void *key)
 1374 {
 1375 
 1376         return ck_rhs_put_internal(hs, h, key, CK_RHS_PROBE_INSERT);
 1377 }
 1378 
 1379 bool
 1380 ck_rhs_put_unique(struct ck_rhs *hs,
 1381     unsigned long h,
 1382     const void *key)
 1383 {
 1384 
 1385         return ck_rhs_put_internal(hs, h, key, CK_RHS_PROBE_RH);
 1386 }
 1387 
 1388 void *
 1389 ck_rhs_get(struct ck_rhs *hs,
 1390     unsigned long h,
 1391     const void *key)
 1392 {
 1393         long first;
 1394         const void *object;
 1395         struct ck_rhs_map *map;
 1396         unsigned long n_probes;
 1397         unsigned int g, g_p, probe;
 1398         unsigned int *generation;
 1399 
 1400         do {
 1401                 map = ck_pr_load_ptr(&hs->map);
 1402                 generation = &map->generation[h & CK_RHS_G_MASK];
 1403                 g = ck_pr_load_uint(generation);
 1404                 probe  = ck_rhs_map_bound_get(map, h);
 1405                 ck_pr_fence_load();
 1406 
 1407                 first = -1;
 1408                 map->probe_func(hs, map, &n_probes, &first, h, key, &object, probe, CK_RHS_PROBE_NO_RH);
 1409 
 1410                 ck_pr_fence_load();
 1411                 g_p = ck_pr_load_uint(generation);
 1412         } while (g != g_p);
 1413 
 1414         return CK_CC_DECONST_PTR(object);
 1415 }
 1416 
 1417 void *
 1418 ck_rhs_remove(struct ck_rhs *hs,
 1419     unsigned long h,
 1420     const void *key)
 1421 {
 1422         long slot, first;
 1423         const void *object;
 1424         struct ck_rhs_map *map = hs->map;
 1425         unsigned long n_probes;
 1426 
 1427         slot = map->probe_func(hs, map, &n_probes, &first, h, key, &object,
 1428             ck_rhs_map_bound_get(map, h), CK_RHS_PROBE_NO_RH);
 1429         if (object == NULL)
 1430                 return NULL;
 1431 
 1432         map->n_entries--;
 1433         ck_rhs_do_backward_shift_delete(hs, slot);
 1434         return CK_CC_DECONST_PTR(object);
 1435 }
 1436 
 1437 bool
 1438 ck_rhs_move(struct ck_rhs *hs,
 1439     struct ck_rhs *source,
 1440     ck_rhs_hash_cb_t *hf,
 1441     ck_rhs_compare_cb_t *compare,
 1442     struct ck_malloc *m)
 1443 {
 1444 
 1445         if (m == NULL || m->malloc == NULL || m->free == NULL || hf == NULL)
 1446                 return false;
 1447 
 1448         hs->mode = source->mode;
 1449         hs->seed = source->seed;
 1450         hs->map = source->map;
 1451         hs->load_factor = source->load_factor;
 1452         hs->m = m;
 1453         hs->hf = hf;
 1454         hs->compare = compare;
 1455         return true;
 1456 }
 1457 
 1458 bool
 1459 ck_rhs_init(struct ck_rhs *hs,
 1460     unsigned int mode,
 1461     ck_rhs_hash_cb_t *hf,
 1462     ck_rhs_compare_cb_t *compare,
 1463     struct ck_malloc *m,
 1464     unsigned long n_entries,
 1465     unsigned long seed)
 1466 {
 1467 
 1468         if (m == NULL || m->malloc == NULL || m->free == NULL || hf == NULL)
 1469                 return false;
 1470 
 1471         hs->m = m;
 1472         hs->mode = mode;
 1473         hs->seed = seed;
 1474         hs->hf = hf;
 1475         hs->compare = compare;
 1476         hs->load_factor = CK_RHS_DEFAULT_LOAD_FACTOR;
 1477 
 1478         hs->map = ck_rhs_map_create(hs, n_entries);
 1479         return hs->map != NULL;
 1480 }
Cache object: 8d83a7564f602daefcf62c6bb732a1c0
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/contrib/ck/src/ck_rhs.c

FreeBSD/Linux Kernel Cross Reference
sys/contrib/ck/src/ck_rhs.c
