X-Git-Url: https://pd.if.org/git/?p=nbds;a=blobdiff_plain;f=map%2Fhashtable.c;h=231384c22cb626ac8f6e03ed8991cd7fcd719602;hp=a9916465104b196d59647ce926cae5b98296155e;hb=2b107655a1df8ae7703b44ef8cf1430a7250a5c3;hpb=e592519ef19f890e551c27f47ef8b773bb4860da diff --git a/map/hashtable.c b/map/hashtable.c index a991646..231384c 100644 --- a/map/hashtable.c +++ b/map/hashtable.c @@ -16,6 +16,7 @@ #include "common.h" #include "murmur.h" #include "mem.h" +#include "rcu.h" #include "hashtable.h" #ifndef NBD32 @@ -33,6 +34,9 @@ typedef struct hti { volatile entry_t *table; hashtable_t *ht; // parent ht; struct hti *next; +#ifdef USE_SYSTEM_MALLOC + void *unaligned_table_ptr; // system malloc doesn't guarentee cache-line alignment +#endif unsigned scale; int max_probe; int ref_count; @@ -94,7 +98,7 @@ static volatile entry_t *hti_lookup (hti_t *hti, map_key_t key, uint32_t key_has map_key_t ent_key = ent->key; if (ent_key == DOES_NOT_EXIST) { TRACE("h1", "hti_lookup: entry %p for key %p is empty", ent, - (hti->ht->key_type == NULL) ? (void *)ent_key : GET_PTR(ent_key)); + (hti->ht->key_type == NULL) ? (void *)key : GET_PTR(key)); *is_empty = 1; // indicate an empty so the caller avoids an expensive key compare return ent; } @@ -135,13 +139,16 @@ static volatile entry_t *hti_lookup (hti_t *hti, map_key_t key, uint32_t key_has static hti_t *hti_alloc (hashtable_t *parent, int scale) { hti_t *hti = (hti_t *)nbd_malloc(sizeof(hti_t)); memset(hti, 0, sizeof(hti_t)); + hti->scale = scale; size_t sz = sizeof(entry_t) * (1 << scale); - entry_t *table = nbd_malloc(sz); - memset(table, 0, sz); - hti->table = table; - - hti->scale = scale; +#ifdef USE_SYSTEM_MALLOC + hti->unaligned_table_ptr = nbd_malloc(sz + CACHE_LINE_SIZE - 1); + hti->table = (void *)(((size_t)hti->unaligned_table_ptr + CACHE_LINE_SIZE - 1) & ~(CACHE_LINE_SIZE - 1)); +#else + hti->table = nbd_malloc(sz); +#endif + memset((void *)hti->table, 0, sz); // When searching for a key probe a maximum of 1/4 of the buckets up to 1000 buckets. hti->max_probe = ((1 << (hti->scale - 2)) / ENTRIES_PER_BUCKET) + 4; @@ -177,7 +184,11 @@ static void hti_start_copy (hti_t *hti) { if (old_next != NULL) { // Another thread beat us to it. TRACE("h0", "hti_start_copy: lost race to install new hti; found %p", old_next, 0); - nbd_free(next); +#ifdef USE_SYSTEM_MALLOC + nbd_free(next->unaligned_table_ptr); +#else + nbd_free((void *)next->table); +#endif return; } TRACE("h0", "hti_start_copy: new hti %p scale %llu", next, next->scale); @@ -232,9 +243,11 @@ static int hti_copy_entry (hti_t *ht1, volatile entry_t *ht1_ent, uint32_t key_h // We use 0 to indicate that is uninitiallized. Occasionally the key's hash will really be 0 and we // waste time recomputing it every time. It is rare enough that it won't hurt performance. if (key_hash == 0) { - key_hash = (ht1->ht->key_type == NULL) - ? murmur32_8b(ht1_ent_key) - : ht1->ht->key_type->hash((void *)key); +#ifdef NBD32 + key_hash = (ht1->ht->key_type == NULL) ? murmur32_4b(ht1_ent_key) : ht1->ht->key_type->hash((void *)key); +#else + key_hash = (ht1->ht->key_type == NULL) ? murmur32_8b(ht1_ent_key) : ht1->ht->key_type->hash((void *)key); +#endif } int ht2_ent_is_empty; @@ -441,7 +454,11 @@ static map_val_t hti_get (hti_t *hti, map_key_t key, uint32_t key_hash) { // map_val_t ht_get (hashtable_t *ht, map_key_t key) { +#ifdef NBD32 + uint32_t hash = (ht->key_type == NULL) ? murmur32_4b((uint64_t)key) : ht->key_type->hash((void *)key); +#else uint32_t hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash((void *)key); +#endif return hti_get(ht->hti, key, hash); } @@ -498,11 +515,15 @@ static void hti_defer_free (hti_t *hti) { continue; assert(!IS_TAGGED(val, TAG1) || val == TAG_VALUE(TOMBSTONE, TAG1)); // copy not in progress if (hti->ht->key_type != NULL && key != DOES_NOT_EXIST) { - nbd_defer_free(GET_PTR(key)); + rcu_defer_free(GET_PTR(key)); } } - nbd_defer_free((void *)hti->table); - nbd_defer_free(hti); +#ifdef USE_SYSTEM_MALLOC + rcu_defer_free(hti->unaligned_table_ptr); +#else + rcu_defer_free((void *)hti->table); +#endif + rcu_defer_free(hti); } static void hti_release (hti_t *hti) { @@ -537,7 +558,11 @@ map_val_t ht_cas (hashtable_t *ht, map_key_t key, map_val_t expected_val, map_va } map_val_t old_val; +#ifdef NBD32 + uint32_t key_hash = (ht->key_type == NULL) ? murmur32_4b((uint64_t)key) : ht->key_type->hash((void *)key); +#else uint32_t key_hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash((void *)key); +#endif while ((old_val = hti_cas(hti, key, key_hash, expected_val, new_val)) == COPIED_VALUE) { assert(hti->next); hti = hti->next; @@ -551,7 +576,11 @@ map_val_t ht_cas (hashtable_t *ht, map_key_t key, map_val_t expected_val, map_va map_val_t ht_remove (hashtable_t *ht, map_key_t key) { hti_t *hti = ht->hti; map_val_t val; +#ifdef NBD32 + uint32_t key_hash = (ht->key_type == NULL) ? murmur32_4b((uint64_t)key) : ht->key_type->hash((void *)key); +#else uint32_t key_hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash((void *)key); +#endif do { val = hti_cas(hti, key, key_hash, CAS_EXPECT_WHATEVER, DOES_NOT_EXIST); if (val != COPIED_VALUE) @@ -652,9 +681,12 @@ map_val_t ht_iter_next (ht_iter_t *iter, map_key_t *key_ptr) { *key_ptr = key; } if (val == COPIED_VALUE) { - uint32_t hash = (iter->hti->ht->key_type == NULL) - ? murmur32_8b((uint64_t)key) - : iter->hti->ht->key_type->hash((void *)key); + const datatype_t *key_type = iter->hti->ht->key_type; +#ifdef NBD32 + uint32_t hash = (key_type == NULL) ? murmur32_4b((uint64_t)key) : key_type->hash((void *)key); +#else + uint32_t hash = (key_type == NULL) ? murmur32_8b((uint64_t)key) : key_type->hash((void *)key); +#endif val = hti_get(iter->hti->next, (map_key_t)ent->key, hash); }