X-Git-Url: https://pd.if.org/git/?p=nbds;a=blobdiff_plain;f=map%2Fhashtable.c;h=bff782f84afdf46867dcbc27275402f1e3ac18dd;hp=88bf6311efcea09aeca0bae1cff82fa62595d7a0;hb=5aa9223647fbb52fa8941d92c8896ebaf148b41c;hpb=a1d0b3ca99552878b1becf561d8f3291992aaa67 diff --git a/map/hashtable.c b/map/hashtable.c index 88bf631..bff782f 100644 --- a/map/hashtable.c +++ b/map/hashtable.c @@ -10,6 +10,8 @@ * Every atomic operation is also an implicit full memory barrier. The upshot is that it simplifies * the code a bit, but it won't be as fast as it could be on platforms that provide weaker * operations like and unfenced CAS which would still do the job. + * + * 11FebO9 - Bug fix in ht_iter_next() from Rui Ueyama */ #include @@ -34,6 +36,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; @@ -136,13 +141,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; @@ -178,7 +186,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); @@ -278,8 +290,8 @@ static int hti_copy_entry (hti_t *ht1, volatile entry_t *ht1_ent, uint32_t key_h // Update the count if we were the one that completed the copy. if (old_ht2_ent_val == DOES_NOT_EXIST) { TRACE("h0", "hti_copy_entry: key %p value %p copied to new entry", key, ht1_ent_val); - SYNC_ADD(&ht1->count, -1); - SYNC_ADD(&ht2->count, 1); + (void)SYNC_ADD(&ht1->count, -1); + (void)SYNC_ADD(&ht2->count, 1); return TRUE; } @@ -364,9 +376,9 @@ static map_val_t hti_cas (hti_t *hti, map_key_t key, uint32_t key_hash, map_val_ map_val_t ent_val = ent->val; if (EXPECT_FALSE(IS_TAGGED(ent_val, TAG1))) { if (ent_val != COPIED_VALUE && ent_val != TAG_VALUE(TOMBSTONE, TAG1)) { - int did_copy = hti_copy_entry(hti, ent, key_hash, ((volatile hti_t *)hti)->next); + int did_copy = hti_copy_entry(hti, ent, key_hash, VOLATILE_DEREF(hti).next); if (did_copy) { - SYNC_ADD(&hti->num_entries_copied, 1); + (void)SYNC_ADD(&hti->num_entries_copied, 1); } TRACE("h0", "hti_cas: value in the middle of a copy, copy completed by %s", (did_copy ? "self" : "other"), 0); @@ -400,9 +412,9 @@ static map_val_t hti_cas (hti_t *hti, map_key_t key, uint32_t key_hash, map_val_ // The set succeeded. Adjust the value count. if (old_existed && new == DOES_NOT_EXIST) { - SYNC_ADD(&hti->count, -1); + (void)SYNC_ADD(&hti->count, -1); } else if (!old_existed && new != DOES_NOT_EXIST) { - SYNC_ADD(&hti->count, 1); + (void)SYNC_ADD(&hti->count, 1); } // Return the previous value. @@ -419,7 +431,7 @@ static map_val_t hti_get (hti_t *hti, map_key_t key, uint32_t key_hash) { // searching the table. In that case, if a copy is in progress the key // might exist in the copy. if (EXPECT_FALSE(ent == NULL)) { - if (((volatile hti_t *)hti)->next != NULL) + if (VOLATILE_DEREF(hti).next != NULL) return hti_get(hti->next, key, key_hash); // recursive tail-call return DOES_NOT_EXIST; } @@ -431,12 +443,12 @@ static map_val_t hti_get (hti_t *hti, map_key_t key, uint32_t key_hash) { map_val_t ent_val = ent->val; if (EXPECT_FALSE(IS_TAGGED(ent_val, TAG1))) { if (EXPECT_FALSE(ent_val != COPIED_VALUE && ent_val != TAG_VALUE(TOMBSTONE, TAG1))) { - int did_copy = hti_copy_entry(hti, ent, key_hash, ((volatile hti_t *)hti)->next); + int did_copy = hti_copy_entry(hti, ent, key_hash, VOLATILE_DEREF(hti).next); if (did_copy) { - SYNC_ADD(&hti->num_entries_copied, 1); + (void)SYNC_ADD(&hti->num_entries_copied, 1); } } - return hti_get(((volatile hti_t *)hti)->next, key, key_hash); // tail-call + return hti_get(VOLATILE_DEREF(hti).next, key, key_hash); // tail-call } return (ent_val == TOMBSTONE) ? DOES_NOT_EXIST : ent_val; @@ -508,7 +520,11 @@ static void hti_defer_free (hti_t *hti) { rcu_defer_free(GET_PTR(key)); } } +#ifdef USE_SYSTEM_MALLOC + rcu_defer_free(hti->unaligned_table_ptr); +#else rcu_defer_free((void *)hti->table); +#endif rcu_defer_free(hti); } @@ -663,9 +679,6 @@ map_val_t ht_iter_next (ht_iter_t *iter, map_key_t *key_ptr) { } while (key == DOES_NOT_EXIST || val == DOES_NOT_EXIST || val == TOMBSTONE); - if (key_ptr) { - *key_ptr = key; - } if (val == COPIED_VALUE) { const datatype_t *key_type = iter->hti->ht->key_type; #ifdef NBD32 @@ -674,8 +687,15 @@ map_val_t ht_iter_next (ht_iter_t *iter, map_key_t *key_ptr) { 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); + + // Go to the next entry if key is already deleted. + if (val == DOES_NOT_EXIST) + return ht_iter_next(iter, key_ptr); // recursive tail-call } + if (key_ptr) { + *key_ptr = key; + } return val; }