ck_hs.c revision 328515
162587Sitojun/* 278064Sume * Copyright 2012-2015 Samy Al Bahra. 362587Sitojun * All rights reserved. 4139826Simp * 553541Sshin * Redistribution and use in source and binary forms, with or without 653541Sshin * modification, are permitted provided that the following conditions 753541Sshin * are met: 853541Sshin * 1. Redistributions of source code must retain the above copyright 953541Sshin * notice, this list of conditions and the following disclaimer. 1053541Sshin * 2. Redistributions in binary form must reproduce the above copyright 1153541Sshin * notice, this list of conditions and the following disclaimer in the 1253541Sshin * documentation and/or other materials provided with the distribution. 1353541Sshin * 1453541Sshin * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 1553541Sshin * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1653541Sshin * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1753541Sshin * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 1853541Sshin * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 1953541Sshin * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2053541Sshin * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2153541Sshin * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2253541Sshin * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2353541Sshin * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2453541Sshin * SUCH DAMAGE. 2553541Sshin */ 2653541Sshin 2753541Sshin#include <ck_cc.h> 2853541Sshin#include <ck_hs.h> 2953541Sshin#include <ck_limits.h> 3053541Sshin#include <ck_md.h> 3153541Sshin#include <ck_pr.h> 3253541Sshin#include <ck_stdint.h> 3362587Sitojun#include <ck_stdbool.h> 3462587Sitojun#include <ck_string.h> 3562587Sitojun 3653541Sshin#include "ck_internal.h" 3753541Sshin 3853541Sshin#ifndef CK_HS_PROBE_L1_SHIFT 3953541Sshin#define CK_HS_PROBE_L1_SHIFT 3ULL 4053541Sshin#endif /* CK_HS_PROBE_L1_SHIFT */ 4153541Sshin 4253541Sshin#define CK_HS_PROBE_L1 (1 << CK_HS_PROBE_L1_SHIFT) 4378064Sume#define CK_HS_PROBE_L1_MASK (CK_HS_PROBE_L1 - 1) 4453541Sshin 4553541Sshin#ifndef CK_HS_PROBE_L1_DEFAULT 4678064Sume#define CK_HS_PROBE_L1_DEFAULT CK_MD_CACHELINE 4753541Sshin#endif 4853541Sshin 4953541Sshin#define CK_HS_VMA_MASK ((uintptr_t)((1ULL << CK_MD_VMA_BITS) - 1)) 5053541Sshin#define CK_HS_VMA(x) \ 5153541Sshin ((void *)((uintptr_t)(x) & CK_HS_VMA_MASK)) 5253541Sshin 5353541Sshin#define CK_HS_EMPTY NULL 5453541Sshin#define CK_HS_TOMBSTONE ((void *)~(uintptr_t)0) 5553541Sshin#define CK_HS_G (2) 5678064Sume#define CK_HS_G_MASK (CK_HS_G - 1) 5762587Sitojun 5853541Sshin#if defined(CK_F_PR_LOAD_8) && defined(CK_F_PR_STORE_8) 5953541Sshin#define CK_HS_WORD uint8_t 6062587Sitojun#define CK_HS_WORD_MAX UINT8_MAX 6162587Sitojun#define CK_HS_STORE(x, y) ck_pr_store_8(x, y) 6253541Sshin#define CK_HS_LOAD(x) ck_pr_load_8(x) 6353541Sshin#elif defined(CK_F_PR_LOAD_16) && defined(CK_F_PR_STORE_16) 6453541Sshin#define CK_HS_WORD uint16_t 6562587Sitojun#define CK_HS_WORD_MAX UINT16_MAX 6653541Sshin#define CK_HS_STORE(x, y) ck_pr_store_16(x, y) 6762587Sitojun#define CK_HS_LOAD(x) ck_pr_load_16(x) 6878064Sume#elif defined(CK_F_PR_LOAD_32) && defined(CK_F_PR_STORE_32) 6978064Sume#define CK_HS_WORD uint32_t 7062587Sitojun#define CK_HS_WORD_MAX UINT32_MAX 7178064Sume#define CK_HS_STORE(x, y) ck_pr_store_32(x, y) 7262587Sitojun#define CK_HS_LOAD(x) ck_pr_load_32(x) 7362587Sitojun#else 7462587Sitojun#error "ck_hs is not supported on your platform." 7578064Sume#endif 7662587Sitojun 7778064Sumeenum ck_hs_probe_behavior { 7853541Sshin CK_HS_PROBE = 0, /* Default behavior. */ 79120941Sume CK_HS_PROBE_TOMBSTONE, /* Short-circuit on tombstone. */ 80120941Sume CK_HS_PROBE_INSERT /* Short-circuit on probe bound if tombstone found. */ 8153541Sshin}; 8262587Sitojun 8353541Sshinstruct ck_hs_map { 8462587Sitojun unsigned int generation[CK_HS_G]; 8553541Sshin unsigned int probe_maximum; 8678064Sume unsigned long mask; 8762587Sitojun unsigned long step; 8862587Sitojun unsigned int probe_limit; 8978064Sume unsigned int tombstones; 9078064Sume unsigned long n_entries; 9178064Sume unsigned long capacity; 9278064Sume unsigned long size; 9378064Sume CK_HS_WORD *probe_bound; 9453541Sshin const void **entries; 9578064Sume}; 9678064Sume 9778064Sumestatic inline void 9878064Sumeck_hs_map_signal(struct ck_hs_map *map, unsigned long h) 9978064Sume{ 10078064Sume 10178064Sume h &= CK_HS_G_MASK; 10253541Sshin ck_pr_store_uint(&map->generation[h], 10353541Sshin map->generation[h] + 1); 10453541Sshin ck_pr_fence_store(); 10553541Sshin return; 10653541Sshin} 10753541Sshin 10853541Sshinvoid 10953541Sshinck_hs_iterator_init(struct ck_hs_iterator *iterator) 11053541Sshin{ 11153541Sshin 11253541Sshin iterator->cursor = NULL; 11353541Sshin iterator->offset = 0; 11453541Sshin return; 11562587Sitojun} 11653541Sshin 11753541Sshinbool 11853541Sshinck_hs_next(struct ck_hs *hs, struct ck_hs_iterator *i, void **key) 11953541Sshin{ 12053541Sshin struct ck_hs_map *map = hs->map; 12153541Sshin void *value; 12253541Sshin 12362587Sitojun if (i->offset >= map->capacity) 12453541Sshin return false; 12553541Sshin 12653541Sshin do { 12778064Sume value = CK_CC_DECONST_PTR(map->entries[i->offset]); 12878064Sume if (value != CK_HS_EMPTY && value != CK_HS_TOMBSTONE) { 12978064Sume#ifdef CK_HS_PP 13078064Sume if (hs->mode & CK_HS_MODE_OBJECT) 13178064Sume value = CK_HS_VMA(value); 13253541Sshin#endif 13353541Sshin i->offset++; 13453541Sshin *key = value; 13553541Sshin return true; 13653541Sshin } 13753541Sshin } while (++i->offset < map->capacity); 13853541Sshin 13962587Sitojun return false; 14062587Sitojun} 14162587Sitojun 14262587Sitojunvoid 14362587Sitojunck_hs_stat(struct ck_hs *hs, struct ck_hs_stat *st) 14462587Sitojun{ 14562587Sitojun struct ck_hs_map *map = hs->map; 14662587Sitojun 14762587Sitojun st->n_entries = map->n_entries; 14853541Sshin st->tombstones = map->tombstones; 14962587Sitojun st->probe_maximum = map->probe_maximum; 15062587Sitojun return; 15153541Sshin} 15253541Sshin 15353541Sshinunsigned long 15453541Sshinck_hs_count(struct ck_hs *hs) 15578064Sume{ 15678064Sume 15778064Sume return hs->map->n_entries; 15862587Sitojun} 15953541Sshin 16053541Sshinstatic void 16153541Sshinck_hs_map_destroy(struct ck_malloc *m, struct ck_hs_map *map, bool defer) 16253541Sshin{ 16353541Sshin 16453541Sshin m->free(map, map->size, defer); 16553541Sshin return; 16653541Sshin} 16778064Sume 16853541Sshinvoid 16953541Sshinck_hs_destroy(struct ck_hs *hs) 170120941Sume{ 171120941Sume 17278064Sume ck_hs_map_destroy(hs->m, hs->map, false); 17353541Sshin return; 17453541Sshin} 17553541Sshin 17662587Sitojunstatic struct ck_hs_map * 17762587Sitojunck_hs_map_create(struct ck_hs *hs, unsigned long entries) 17862587Sitojun{ 17978064Sume struct ck_hs_map *map; 18078064Sume unsigned long size, n_entries, prefix, limit; 18178064Sume 18278064Sume n_entries = ck_internal_power_2(entries); 18378064Sume if (n_entries < CK_HS_PROBE_L1) 18453541Sshin n_entries = CK_HS_PROBE_L1; 18553541Sshin 18653541Sshin size = sizeof(struct ck_hs_map) + (sizeof(void *) * n_entries + CK_MD_CACHELINE - 1); 18753541Sshin 18853541Sshin if (hs->mode & CK_HS_MODE_DELETE) { 18953541Sshin prefix = sizeof(CK_HS_WORD) * n_entries; 19053541Sshin size += prefix; 19153541Sshin } else { 19253541Sshin prefix = 0; 19353541Sshin } 19453541Sshin 19553541Sshin map = hs->m->malloc(size); 19653541Sshin if (map == NULL) 19753541Sshin return NULL; 19853541Sshin 199121161Sume map->size = size; 20053541Sshin 20162587Sitojun /* We should probably use a more intelligent heuristic for default probe length. */ 20253541Sshin limit = ck_internal_max(n_entries >> (CK_HS_PROBE_L1_SHIFT + 2), CK_HS_PROBE_L1_DEFAULT); 20353541Sshin if (limit > UINT_MAX) 20453541Sshin limit = UINT_MAX; 20553541Sshin 206118498Sume map->probe_limit = (unsigned int)limit; 207118498Sume map->probe_maximum = 0; 208118498Sume map->capacity = n_entries; 209118498Sume map->step = ck_internal_bsf(n_entries); 210118498Sume map->mask = n_entries - 1; 21153541Sshin map->n_entries = 0; 21262587Sitojun 213118498Sume /* Align map allocation to cache line. */ 214118498Sume map->entries = (void *)(((uintptr_t)&map[1] + prefix + 21553541Sshin CK_MD_CACHELINE - 1) & ~(CK_MD_CACHELINE - 1)); 21653541Sshin 21778064Sume memset(map->entries, 0, sizeof(void *) * n_entries); 21878064Sume memset(map->generation, 0, sizeof map->generation); 21978064Sume 22078064Sume if (hs->mode & CK_HS_MODE_DELETE) { 22178064Sume map->probe_bound = (CK_HS_WORD *)&map[1]; 22253541Sshin memset(map->probe_bound, 0, prefix); 22353541Sshin } else { 22453541Sshin map->probe_bound = NULL; 22578064Sume } 22653541Sshin 22778064Sume /* Commit entries purge with respect to map publication. */ 22878064Sume ck_pr_fence_store(); 22962587Sitojun return map; 23062587Sitojun} 23162587Sitojun 23262587Sitojunbool 23362587Sitojunck_hs_reset_size(struct ck_hs *hs, unsigned long capacity) 23462587Sitojun{ 23562587Sitojun struct ck_hs_map *map, *previous; 23662587Sitojun 23762587Sitojun previous = hs->map; 23853541Sshin map = ck_hs_map_create(hs, capacity); 23953541Sshin if (map == NULL) 24062587Sitojun return false; 24153541Sshin 24253541Sshin ck_pr_store_ptr(&hs->map, map); 24353541Sshin ck_hs_map_destroy(hs->m, previous, true); 24453541Sshin return true; 24578064Sume} 24678064Sume 24778064Sumebool 24862587Sitojunck_hs_reset(struct ck_hs *hs) 24953541Sshin{ 25053541Sshin struct ck_hs_map *previous; 25153541Sshin 25253541Sshin previous = hs->map; 25353541Sshin return ck_hs_reset_size(hs, previous->capacity); 25453541Sshin} 25553541Sshin 25653541Sshinstatic inline unsigned long 25753541Sshinck_hs_map_probe_next(struct ck_hs_map *map, 25853541Sshin unsigned long offset, 25953541Sshin unsigned long h, 26053541Sshin unsigned long level, 26153541Sshin unsigned long probes) 26290868Smike{ 26353541Sshin unsigned long r, stride; 26453541Sshin 26553541Sshin r = (h >> map->step) >> level; 26653541Sshin stride = (r & ~CK_HS_PROBE_L1_MASK) << 1 | (r & CK_HS_PROBE_L1_MASK); 26753541Sshin 26853541Sshin return (offset + (probes >> CK_HS_PROBE_L1_SHIFT) + 26953541Sshin (stride | CK_HS_PROBE_L1)) & map->mask; 27053541Sshin} 27153541Sshin 27253541Sshinstatic inline void 27353541Sshinck_hs_map_bound_set(struct ck_hs_map *m, 27453541Sshin unsigned long h, 27553541Sshin unsigned long n_probes) 27653541Sshin{ 27753541Sshin unsigned long offset = h & m->mask; 27853541Sshin 27953541Sshin if (n_probes > m->probe_maximum) 28053541Sshin ck_pr_store_uint(&m->probe_maximum, n_probes); 28153541Sshin 28278064Sume if (m->probe_bound != NULL && m->probe_bound[offset] < n_probes) { 28353541Sshin if (n_probes > CK_HS_WORD_MAX) 28453541Sshin n_probes = CK_HS_WORD_MAX; 28553541Sshin 28653541Sshin CK_HS_STORE(&m->probe_bound[offset], n_probes); 28753541Sshin ck_pr_fence_store(); 28853541Sshin } 28953541Sshin 29053541Sshin return; 29153541Sshin} 29253541Sshin 29353541Sshinstatic inline unsigned int 29478064Sumeck_hs_map_bound_get(struct ck_hs_map *m, unsigned long h) 29578064Sume{ 29678064Sume unsigned long offset = h & m->mask; 29778064Sume unsigned int r = CK_HS_WORD_MAX; 29853541Sshin 29953541Sshin if (m->probe_bound != NULL) { 30053541Sshin r = CK_HS_LOAD(&m->probe_bound[offset]); 30153541Sshin if (r == CK_HS_WORD_MAX) 30278064Sume r = ck_pr_load_uint(&m->probe_maximum); 30378064Sume } else { 30478064Sume r = ck_pr_load_uint(&m->probe_maximum); 30578064Sume } 30653541Sshin 30753541Sshin return r; 30853541Sshin} 30953541Sshin 31053541Sshinbool 31178064Sumeck_hs_grow(struct ck_hs *hs, 31278064Sume unsigned long capacity) 31378064Sume{ 31478064Sume struct ck_hs_map *map, *update; 31553541Sshin unsigned long k, i, j, offset, probes; 31653541Sshin const void *previous, **bucket; 31753541Sshin 31853541Sshinrestart: 31953541Sshin map = hs->map; 32053541Sshin if (map->capacity > capacity) 32178064Sume return false; 32278064Sume 32378064Sume update = ck_hs_map_create(hs, capacity); 32478064Sume if (update == NULL) 32578064Sume return false; 32653541Sshin 32753541Sshin for (k = 0; k < map->capacity; k++) { 32853541Sshin unsigned long h; 32953541Sshin 33053541Sshin previous = map->entries[k]; 33153541Sshin if (previous == CK_HS_EMPTY || previous == CK_HS_TOMBSTONE) 33253541Sshin continue; 33353541Sshin 33453541Sshin#ifdef CK_HS_PP 33553541Sshin if (hs->mode & CK_HS_MODE_OBJECT) 336120941Sume previous = CK_HS_VMA(previous); 33753541Sshin#endif 338120941Sume 33953541Sshin h = hs->hf(previous, hs->seed); 34053541Sshin offset = h & update->mask; 341120941Sume i = probes = 0; 34253541Sshin 34353541Sshin for (;;) { 34453541Sshin bucket = (const void **)((uintptr_t)&update->entries[offset] & ~(CK_MD_CACHELINE - 1)); 34553541Sshin 34653541Sshin for (j = 0; j < CK_HS_PROBE_L1; j++) { 34753541Sshin const void **cursor = bucket + ((j + offset) & (CK_HS_PROBE_L1 - 1)); 34853541Sshin 34953541Sshin if (probes++ == update->probe_limit) 35053541Sshin break; 35153541Sshin 352121283Sume if (CK_CC_LIKELY(*cursor == CK_HS_EMPTY)) { 353121283Sume *cursor = map->entries[k]; 35453541Sshin update->n_entries++; 355121283Sume 356120941Sume ck_hs_map_bound_set(update, h, probes); 35753541Sshin break; 35853541Sshin } 35978064Sume } 360121283Sume 36178064Sume if (j < CK_HS_PROBE_L1) 36253541Sshin break; 36353541Sshin 36453541Sshin offset = ck_hs_map_probe_next(update, offset, h, i++, probes); 36553541Sshin } 366121283Sume 367121283Sume if (probes > update->probe_limit) { 368121283Sume /* 369121283Sume * We have hit the probe limit, map needs to be even larger. 37053541Sshin */ 371121283Sume ck_hs_map_destroy(hs->m, update, false); 372121283Sume capacity <<= 1; 373121283Sume goto restart; 37453541Sshin } 375121283Sume } 376121283Sume 377121283Sume ck_pr_fence_store(); 378121283Sume ck_pr_store_ptr(&hs->map, update); 37953541Sshin ck_hs_map_destroy(hs->m, map, true); 38053541Sshin return true; 38153541Sshin} 38253541Sshin 383120941Sumestatic void 38453541Sshinck_hs_map_postinsert(struct ck_hs *hs, struct ck_hs_map *map) 38595023Ssuz{ 38653541Sshin 38753541Sshin map->n_entries++; 38853541Sshin if ((map->n_entries << 1) > map->capacity) 38953541Sshin ck_hs_grow(hs, map->capacity << 1); 390120941Sume 39153541Sshin return; 39253541Sshin} 39353541Sshin 39453541Sshinbool 39553541Sshinck_hs_rebuild(struct ck_hs *hs) 39653541Sshin{ 39778064Sume 39853541Sshin return ck_hs_grow(hs, hs->map->capacity); 399120941Sume} 400120941Sume 40178064Sumestatic const void ** 40253541Sshinck_hs_map_probe(struct ck_hs *hs, 40353541Sshin struct ck_hs_map *map, 404120941Sume unsigned long *n_probes, 405120941Sume const void ***priority, 40662587Sitojun unsigned long h, 40762587Sitojun const void *key, 40862587Sitojun const void **object, 40962587Sitojun unsigned long probe_limit, 41062587Sitojun enum ck_hs_probe_behavior behavior) 41162587Sitojun{ 41262587Sitojun const void **bucket, **cursor, *k, *compare; 41353541Sshin const void **pr = NULL; 41462587Sitojun unsigned long offset, j, i, probes, opl; 41578064Sume 41662587Sitojun#ifdef CK_HS_PP 41778064Sume /* If we are storing object pointers, then we may leverage pointer packing. */ 41878064Sume unsigned long hv = 0; 41978064Sume 42078064Sume if (hs->mode & CK_HS_MODE_OBJECT) { 42178064Sume hv = (h >> 25) & CK_HS_KEY_MASK; 42253541Sshin compare = CK_HS_VMA(key); 42353541Sshin } else { 42453541Sshin compare = key; 42553541Sshin } 42653541Sshin#else 42762587Sitojun compare = key; 42862587Sitojun#endif 42962587Sitojun 43078064Sume offset = h & map->mask; 43162587Sitojun *object = NULL; 43262587Sitojun i = probes = 0; 43362587Sitojun 43462587Sitojun opl = probe_limit; 43562587Sitojun if (behavior == CK_HS_PROBE_INSERT) 43662587Sitojun probe_limit = ck_hs_map_bound_get(map, h); 43762587Sitojun 43862587Sitojun for (;;) { 43962587Sitojun bucket = (const void **)((uintptr_t)&map->entries[offset] & ~(CK_MD_CACHELINE - 1)); 44078064Sume 44178064Sume for (j = 0; j < CK_HS_PROBE_L1; j++) { 44278064Sume cursor = bucket + ((j + offset) & (CK_HS_PROBE_L1 - 1)); 44362587Sitojun 44462587Sitojun if (probes++ == probe_limit) { 44562587Sitojun if (probe_limit == opl || pr != NULL) { 44662587Sitojun k = CK_HS_EMPTY; 44753541Sshin goto leave; 44853541Sshin } 44953541Sshin 45053541Sshin /* 45153541Sshin * If no eligible slot has been found yet, continue probe 45262587Sitojun * sequence with original probe limit. 45353541Sshin */ 454128397Sluigi probe_limit = opl; 455128397Sluigi } 456128397Sluigi 45753541Sshin k = ck_pr_load_ptr(cursor); 458120941Sume if (k == CK_HS_EMPTY) 459120941Sume goto leave; 46053541Sshin 46153541Sshin if (k == CK_HS_TOMBSTONE) { 46253541Sshin if (pr == NULL) { 46353541Sshin pr = cursor; 464120941Sume *n_probes = probes; 465120941Sume 46662587Sitojun if (behavior == CK_HS_PROBE_TOMBSTONE) { 467120727Ssam k = CK_HS_EMPTY; 46878064Sume goto leave; 469122334Ssam } 470120727Ssam } 47162587Sitojun 47253541Sshin continue; 47353541Sshin } 47453541Sshin 47562587Sitojun#ifdef CK_HS_PP 47662587Sitojun if (hs->mode & CK_HS_MODE_OBJECT) { 47762587Sitojun if (((uintptr_t)k >> CK_MD_VMA_BITS) != hv) 47862587Sitojun continue; 47962587Sitojun 48062587Sitojun k = CK_HS_VMA(k); 48162587Sitojun } 48262587Sitojun#endif 48362587Sitojun 48462587Sitojun if (k == compare) 48562587Sitojun goto leave; 48662587Sitojun 48762587Sitojun if (hs->compare == NULL) 48862587Sitojun continue; 48962587Sitojun 49062587Sitojun if (hs->compare(k, key) == true) 49162587Sitojun goto leave; 49262587Sitojun } 49362587Sitojun 49462587Sitojun offset = ck_hs_map_probe_next(map, offset, h, i++, probes); 49562587Sitojun } 49678064Sume 49762587Sitojunleave: 49862587Sitojun if (probes > probe_limit) { 49978064Sume cursor = NULL; 50062587Sitojun } else { 50162587Sitojun *object = k; 50262587Sitojun } 50362587Sitojun 50478064Sume if (pr == NULL) 505120941Sume *n_probes = probes; 50678064Sume 50778064Sume *priority = pr; 50862587Sitojun return cursor; 50962587Sitojun} 51078064Sume 51162587Sitojunstatic inline const void * 51262587Sitojunck_hs_marshal(unsigned int mode, const void *key, unsigned long h) 513120727Ssam{ 51478064Sume#ifdef CK_HS_PP 515122334Ssam const void *insert; 516120727Ssam 51762587Sitojun if (mode & CK_HS_MODE_OBJECT) { 51862587Sitojun insert = (void *)((uintptr_t)CK_HS_VMA(key) | 51962587Sitojun ((h >> 25) << CK_MD_VMA_BITS)); 52062587Sitojun } else { 52153541Sshin insert = key; 52253541Sshin } 52353541Sshin 52453541Sshin return insert; 52553541Sshin#else 52653541Sshin (void)mode; 52753541Sshin (void)h; 52862587Sitojun 52962587Sitojun return key; 53053541Sshin#endif 531120856Sume} 53262587Sitojun 53353541Sshinbool 534120856Sumeck_hs_gc(struct ck_hs *hs, unsigned long cycles, unsigned long seed) 53553541Sshin{ 53653541Sshin unsigned long size = 0; 53753541Sshin unsigned long i; 53853541Sshin struct ck_hs_map *map = hs->map; 53953541Sshin unsigned int maximum; 54053541Sshin CK_HS_WORD *bounds = NULL; 54153541Sshin 54253541Sshin if (map->n_entries == 0) { 54362587Sitojun ck_pr_store_uint(&map->probe_maximum, 0); 54453541Sshin if (map->probe_bound != NULL) 545128397Sluigi memset(map->probe_bound, 0, sizeof(CK_HS_WORD) * map->capacity); 546128397Sluigi 547128397Sluigi return true; 54853541Sshin } 549120941Sume 550120941Sume if (cycles == 0) { 55153541Sshin maximum = 0; 55253541Sshin 55353541Sshin if (map->probe_bound != NULL) { 55453541Sshin size = sizeof(CK_HS_WORD) * map->capacity; 555120941Sume bounds = hs->m->malloc(size); 556120941Sume if (bounds == NULL) 55762587Sitojun return false; 55878064Sume 559108269Sru memset(bounds, 0, size); 56062587Sitojun } 56153541Sshin } else { 56262587Sitojun maximum = map->probe_maximum; 56353541Sshin } 56453541Sshin 56553541Sshin for (i = 0; i < map->capacity; i++) { 56653541Sshin const void **first, *object, **slot, *entry; 56753541Sshin unsigned long n_probes, offset, h; 56853541Sshin 56953541Sshin entry = map->entries[(i + seed) & map->mask]; 57053541Sshin if (entry == CK_HS_EMPTY || entry == CK_HS_TOMBSTONE) 57153541Sshin continue; 57253541Sshin 57353541Sshin#ifdef CK_HS_PP 57453541Sshin if (hs->mode & CK_HS_MODE_OBJECT) 57553541Sshin entry = CK_HS_VMA(entry); 57653541Sshin#endif 577120941Sume 57853541Sshin h = hs->hf(entry, hs->seed); 57953541Sshin offset = h & map->mask; 58062587Sitojun 58153541Sshin slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, entry, &object, 58253541Sshin ck_hs_map_bound_get(map, h), CK_HS_PROBE); 58362587Sitojun 58453541Sshin if (first != NULL) { 58553541Sshin const void *insert = ck_hs_marshal(hs->mode, entry, h); 58653541Sshin 58753541Sshin ck_pr_store_ptr(first, insert); 58862587Sitojun ck_hs_map_signal(map, h); 58953541Sshin ck_pr_store_ptr(slot, CK_HS_TOMBSTONE); 59053541Sshin } 59153541Sshin 59253541Sshin if (cycles == 0) { 59353541Sshin if (n_probes > maximum) 59453541Sshin maximum = n_probes; 59553541Sshin 59662587Sitojun if (n_probes > CK_HS_WORD_MAX) 59762587Sitojun n_probes = CK_HS_WORD_MAX; 59862587Sitojun 59953541Sshin if (bounds != NULL && n_probes > bounds[offset]) 60053541Sshin bounds[offset] = n_probes; 60162587Sitojun } else if (--cycles == 0) 60262587Sitojun break; 60353541Sshin } 60453541Sshin 60553541Sshin /* 60662587Sitojun * The following only apply to garbage collection involving 60762587Sitojun * a full scan of all entries. 60862587Sitojun */ 60962587Sitojun if (maximum != map->probe_maximum) 61062587Sitojun ck_pr_store_uint(&map->probe_maximum, maximum); 61162587Sitojun 61262587Sitojun if (bounds != NULL) { 61362587Sitojun for (i = 0; i < map->capacity; i++) 61462587Sitojun CK_HS_STORE(&map->probe_bound[i], bounds[i]); 61562587Sitojun 61662587Sitojun hs->m->free(bounds, size, false); 61762587Sitojun } 61862587Sitojun 61962587Sitojun return true; 62062587Sitojun} 62162587Sitojun 62262587Sitojunbool 62362587Sitojunck_hs_fas(struct ck_hs *hs, 62462587Sitojun unsigned long h, 62562587Sitojun const void *key, 62662587Sitojun void **previous) 62762587Sitojun{ 62862587Sitojun const void **slot, **first, *object, *insert; 62962587Sitojun struct ck_hs_map *map = hs->map; 63062587Sitojun unsigned long n_probes; 63162587Sitojun 63262587Sitojun *previous = NULL; 63362587Sitojun slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object, 63462587Sitojun ck_hs_map_bound_get(map, h), CK_HS_PROBE); 63562587Sitojun 63662587Sitojun /* Replacement semantics presume existence. */ 63762587Sitojun if (object == NULL) 63862587Sitojun return false; 63962587Sitojun 64062587Sitojun insert = ck_hs_marshal(hs->mode, key, h); 64162587Sitojun 64262587Sitojun if (first != NULL) { 64362587Sitojun ck_pr_store_ptr(first, insert); 64462587Sitojun ck_hs_map_signal(map, h); 64562587Sitojun ck_pr_store_ptr(slot, CK_HS_TOMBSTONE); 64662587Sitojun } else { 64762587Sitojun ck_pr_store_ptr(slot, insert); 64862587Sitojun } 64962587Sitojun 65062587Sitojun *previous = CK_CC_DECONST_PTR(object); 65162587Sitojun return true; 65262587Sitojun} 65362587Sitojun 65462587Sitojun/* 65562587Sitojun * An apply function takes two arguments. The first argument is a pointer to a 65662587Sitojun * pre-existing object. The second argument is a pointer to the fifth argument 65762587Sitojun * passed to ck_hs_apply. If a non-NULL pointer is passed to the first argument 65862587Sitojun * and the return value of the apply function is NULL, then the pre-existing 65962587Sitojun * value is deleted. If the return pointer is the same as the one passed to the 66062587Sitojun * apply function then no changes are made to the hash table. If the first 66162587Sitojun * argument is non-NULL and the return pointer is different than that passed to 66262587Sitojun * the apply function, then the pre-existing value is replaced. For 66362587Sitojun * replacement, it is required that the value itself is identical to the 66462587Sitojun * previous value. 66562587Sitojun */ 66662587Sitojunbool 66762587Sitojunck_hs_apply(struct ck_hs *hs, 66862587Sitojun unsigned long h, 66962587Sitojun const void *key, 67078064Sume ck_hs_apply_fn_t *fn, 67178064Sume void *cl) 67278064Sume{ 67378064Sume const void **slot, **first, *object, *delta, *insert; 67462587Sitojun unsigned long n_probes; 67562587Sitojun struct ck_hs_map *map; 67678064Sume 67778064Sumerestart: 67878064Sume map = hs->map; 67978064Sume 68062587Sitojun slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object, map->probe_limit, CK_HS_PROBE_INSERT); 68162587Sitojun if (slot == NULL && first == NULL) { 68262587Sitojun if (ck_hs_grow(hs, map->capacity << 1) == false) 68362587Sitojun return false; 68462587Sitojun 68562587Sitojun goto restart; 68662587Sitojun } 68762587Sitojun 68853541Sshin delta = fn(CK_CC_DECONST_PTR(object), cl); 68953541Sshin if (delta == NULL) { 69053541Sshin /* 69153541Sshin * The apply function has requested deletion. If the object doesn't exist, 69253541Sshin * then exit early. 69353541Sshin */ 69453541Sshin if (CK_CC_UNLIKELY(object == NULL)) 69553541Sshin return true; 69653541Sshin 69753541Sshin /* Otherwise, mark slot as deleted. */ 69853541Sshin ck_pr_store_ptr(slot, CK_HS_TOMBSTONE); 69953541Sshin map->n_entries--; 70053541Sshin map->tombstones++; 70153541Sshin return true; 70253541Sshin } 70353541Sshin 70453541Sshin /* The apply function has not requested hash set modification so exit early. */ 70553541Sshin if (delta == object) 70653541Sshin return true; 707120856Sume 70853541Sshin /* A modification or insertion has been requested. */ 70953541Sshin ck_hs_map_bound_set(map, h, n_probes); 71053541Sshin 71153541Sshin insert = ck_hs_marshal(hs->mode, delta, h); 71253541Sshin if (first != NULL) { 713120856Sume /* 71453541Sshin * This follows the same semantics as ck_hs_set, please refer to that 71553541Sshin * function for documentation. 71653541Sshin */ 71753541Sshin ck_pr_store_ptr(first, insert); 71853541Sshin 719120856Sume if (object != NULL) { 72053541Sshin ck_hs_map_signal(map, h); 72153541Sshin ck_pr_store_ptr(slot, CK_HS_TOMBSTONE); 72253541Sshin } 72362587Sitojun } else { 72462587Sitojun /* 72562587Sitojun * If we are storing into same slot, then atomic store is sufficient 72662587Sitojun * for replacement. 72762587Sitojun */ 72862587Sitojun ck_pr_store_ptr(slot, insert); 72962587Sitojun } 73062587Sitojun 73162587Sitojun if (object == NULL) 73253541Sshin ck_hs_map_postinsert(hs, map); 733120941Sume 734120856Sume return true; 73553541Sshin} 73653541Sshin 73753541Sshinbool 73853541Sshinck_hs_set(struct ck_hs *hs, 73953541Sshin unsigned long h, 74053541Sshin const void *key, 74153541Sshin void **previous) 74253541Sshin{ 743120941Sume const void **slot, **first, *object, *insert; 74462587Sitojun unsigned long n_probes; 74553541Sshin struct ck_hs_map *map; 74653541Sshin 74753541Sshin *previous = NULL; 74853541Sshin 749120856Sumerestart: 75053541Sshin map = hs->map; 75153541Sshin 75253541Sshin slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object, map->probe_limit, CK_HS_PROBE_INSERT); 75353541Sshin if (slot == NULL && first == NULL) { 75453541Sshin if (ck_hs_grow(hs, map->capacity << 1) == false) 75553541Sshin return false; 75653541Sshin 75753541Sshin goto restart; 75853541Sshin } 75953541Sshin 76053541Sshin ck_hs_map_bound_set(map, h, n_probes); 76153541Sshin insert = ck_hs_marshal(hs->mode, key, h); 76253541Sshin 76353541Sshin if (first != NULL) { 76453541Sshin /* If an earlier bucket was found, then store entry there. */ 76553541Sshin ck_pr_store_ptr(first, insert); 76653541Sshin 76753541Sshin /* 76853541Sshin * If a duplicate key was found, then delete it after 76953541Sshin * signaling concurrent probes to restart. Optionally, 77053541Sshin * it is possible to install tombstone after grace 77153541Sshin * period if we can guarantee earlier position of 77253541Sshin * duplicate key. 77353541Sshin */ 77453541Sshin if (object != NULL) { 77553541Sshin ck_hs_map_signal(map, h); 77653541Sshin ck_pr_store_ptr(slot, CK_HS_TOMBSTONE); 77753541Sshin } 77878064Sume } else { 77978064Sume /* 78053541Sshin * If we are storing into same slot, then atomic store is sufficient 78153541Sshin * for replacement. 78253541Sshin */ 78353541Sshin ck_pr_store_ptr(slot, insert); 78462587Sitojun } 78553541Sshin 78653541Sshin if (object == NULL) 78753541Sshin ck_hs_map_postinsert(hs, map); 788120941Sume 78953541Sshin *previous = CK_CC_DECONST_PTR(object); 79053541Sshin return true; 79153541Sshin} 79253541Sshin 793120856SumeCK_CC_INLINE static bool 79453541Sshinck_hs_put_internal(struct ck_hs *hs, 79553541Sshin unsigned long h, 79678064Sume const void *key, 79778064Sume enum ck_hs_probe_behavior behavior) 79878064Sume{ 79953541Sshin const void **slot, **first, *object, *insert; 80053541Sshin unsigned long n_probes; 80178064Sume struct ck_hs_map *map; 80253541Sshin 80353541Sshinrestart: 80453541Sshin map = hs->map; 80553541Sshin 806120941Sume slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object, 80753541Sshin map->probe_limit, behavior); 80853541Sshin 80978064Sume if (slot == NULL && first == NULL) { 81078064Sume if (ck_hs_grow(hs, map->capacity << 1) == false) 81153541Sshin return false; 812120941Sume 81353541Sshin goto restart; 81453541Sshin } 81553541Sshin 81653541Sshin /* Fail operation if a match was found. */ 81753541Sshin if (object != NULL) 818120941Sume return false; 81953541Sshin 82053541Sshin ck_hs_map_bound_set(map, h, n_probes); 82153541Sshin insert = ck_hs_marshal(hs->mode, key, h); 82253541Sshin 82353541Sshin if (first != NULL) { 82453541Sshin /* Insert key into first bucket in probe sequence. */ 82578064Sume ck_pr_store_ptr(first, insert); 82678064Sume } else { 82778064Sume /* An empty slot was found. */ 82878064Sume ck_pr_store_ptr(slot, insert); 82978064Sume } 83078064Sume 83178064Sume ck_hs_map_postinsert(hs, map); 83278064Sume return true; 83378064Sume} 83478064Sume 83578064Sumebool 83678064Sumeck_hs_put(struct ck_hs *hs, 83778064Sume unsigned long h, 838120941Sume const void *key) 83953541Sshin{ 84053541Sshin 84153541Sshin return ck_hs_put_internal(hs, h, key, CK_HS_PROBE_INSERT); 84253541Sshin} 84353541Sshin 84453541Sshinbool 84553541Sshinck_hs_put_unique(struct ck_hs *hs, 84653541Sshin unsigned long h, 84753541Sshin const void *key) 84853541Sshin{ 84978064Sume 85053541Sshin return ck_hs_put_internal(hs, h, key, CK_HS_PROBE_TOMBSTONE); 85178064Sume} 85278064Sume 85378064Sumevoid * 85478064Sumeck_hs_get(struct ck_hs *hs, 85578064Sume unsigned long h, 856151479Ssuz const void *key) 857151479Ssuz{ 85878064Sume const void **first, *object; 859151479Ssuz struct ck_hs_map *map; 86078064Sume unsigned long n_probes; 86178064Sume unsigned int g, g_p, probe; 86278064Sume unsigned int *generation; 86378064Sume 86478064Sume do { 86578064Sume map = ck_pr_load_ptr(&hs->map); 86678064Sume generation = &map->generation[h & CK_HS_G_MASK]; 86778064Sume g = ck_pr_load_uint(generation); 86878064Sume probe = ck_hs_map_bound_get(map, h); 86978064Sume ck_pr_fence_load(); 87078064Sume 87178064Sume ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object, probe, CK_HS_PROBE); 87253541Sshin 87378064Sume ck_pr_fence_load(); 87453541Sshin g_p = ck_pr_load_uint(generation); 87553541Sshin } while (g != g_p); 87653541Sshin 87753541Sshin return CK_CC_DECONST_PTR(object); 87862587Sitojun} 87962587Sitojun 88053541Sshinvoid * 88153541Sshinck_hs_remove(struct ck_hs *hs, 88253541Sshin unsigned long h, 88378064Sume const void *key) 88478064Sume{ 88553541Sshin const void **slot, **first, *object; 88653541Sshin struct ck_hs_map *map = hs->map; 88753541Sshin unsigned long n_probes; 88853541Sshin 88953541Sshin slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object, 89053541Sshin ck_hs_map_bound_get(map, h), CK_HS_PROBE); 89153541Sshin if (object == NULL) 89253541Sshin return NULL; 89353541Sshin 89453541Sshin ck_pr_store_ptr(slot, CK_HS_TOMBSTONE); 89553541Sshin map->n_entries--; 89678064Sume map->tombstones++; 89778064Sume return CK_CC_DECONST_PTR(object); 89878064Sume} 89953541Sshin 90053541Sshinbool 90153541Sshinck_hs_move(struct ck_hs *hs, 90278064Sume struct ck_hs *source, 90353541Sshin ck_hs_hash_cb_t *hf, 90478064Sume ck_hs_compare_cb_t *compare, 90553541Sshin struct ck_malloc *m) 90653541Sshin{ 90753541Sshin 90853541Sshin if (m == NULL || m->malloc == NULL || m->free == NULL || hf == NULL) 90953541Sshin return false; 91053541Sshin 91153541Sshin hs->mode = source->mode; 91253541Sshin hs->seed = source->seed; 913120941Sume hs->map = source->map; 914120941Sume hs->m = m; 91553541Sshin hs->hf = hf; 91653541Sshin hs->compare = compare; 91753541Sshin return true; 91878064Sume} 91978064Sume 92078064Sumebool 92178064Sumeck_hs_init(struct ck_hs *hs, 92278064Sume unsigned int mode, 92353541Sshin ck_hs_hash_cb_t *hf, 92453541Sshin ck_hs_compare_cb_t *compare, 92578064Sume struct ck_malloc *m, 92678064Sume unsigned long n_entries, 92778064Sume unsigned long seed) 92853541Sshin{ 92978064Sume 93078064Sume if (m == NULL || m->malloc == NULL || m->free == NULL || hf == NULL) 93178064Sume return false; 93278064Sume 93378064Sume hs->m = m; 93478064Sume hs->mode = mode; 93578064Sume hs->seed = seed; 93678064Sume hs->hf = hf; 93778064Sume hs->compare = compare; 93878064Sume 93953541Sshin hs->map = ck_hs_map_create(hs, n_entries); 94078064Sume return hs->map != NULL; 94178064Sume} 94278064Sume