From: jdybnis Date: Thu, 4 Dec 2008 05:00:44 +0000 (+0000) Subject: all structures now support arbitrary type keys with a fast path for integers X-Git-Url: https://pd.if.org/git/?p=nbds;a=commitdiff_plain;h=f1098084dd54496a61f9a254541190df77edd166 all structures now support arbitrary type keys with a fast path for integers --- diff --git a/include/map.h b/include/map.h index 44b9d27..71d0dde 100644 --- a/include/map.h +++ b/include/map.h @@ -5,17 +5,21 @@ typedef struct map map_t; typedef const struct map_impl *map_type_t; +typedef int (*cmp_fun_t) (void *, void *); +typedef void * (*clone_fun_t) (void *); +typedef uint32_t (*hash_fun_t) (void *); + extern map_type_t MAP_TYPE_HASHTABLE; extern map_type_t MAP_TYPE_SKIPLIST; extern map_type_t MAP_TYPE_LIST; -map_t * map_alloc (map_type_t map_type); -uint64_t map_get (map_t *map, const void *key_data, uint32_t key_len); -uint64_t map_set (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val); -uint64_t map_add (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val); -uint64_t map_cas (map_t *map, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val); -uint64_t map_replace(map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val); -uint64_t map_remove (map_t *map, const void *key_data, uint32_t key_len); +map_t * map_alloc (map_type_t map_type, cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun); +uint64_t map_get (map_t *map, void *key); +uint64_t map_set (map_t *map, void *key, uint64_t new_val); +uint64_t map_add (map_t *map, void *key, uint64_t new_val); +uint64_t map_cas (map_t *map, void *key, uint64_t expected_val, uint64_t new_val); +uint64_t map_replace(map_t *map, void *key, uint64_t new_val); +uint64_t map_remove (map_t *map, void *key); uint64_t map_count (map_t *map); void map_print (map_t *map); void map_free (map_t *map); diff --git a/include/murmur.h b/include/murmur.h index fcb4cb6..84d7135 100644 --- a/include/murmur.h +++ b/include/murmur.h @@ -61,3 +61,8 @@ static inline unsigned int murmur32 (const char *key, int len) return h; } + +static inline unsigned int murmur32_8b (uint64_t key) +{ + return murmur32((char *)&key, 8); +} diff --git a/include/nstring.h b/include/nstring.h new file mode 100644 index 0000000..5d6fc89 --- /dev/null +++ b/include/nstring.h @@ -0,0 +1,14 @@ +#ifndef NSTRING_H +#define NSTRING_H + +typedef struct nstring { + uint32_t len; + char data[]; +} nstring_t; + +nstring_t * ns_alloc (uint32_t len); +int ns_cmp (const nstring_t *ns1, const nstring_t *ns2); +uint32_t ns_hash (const nstring_t *ns); +nstring_t * ns_dup (const nstring_t *ns); + +#endif//NSTRING_H diff --git a/include/txn.h b/include/txn.h index b2d6a10..56144e9 100644 --- a/include/txn.h +++ b/include/txn.h @@ -17,7 +17,7 @@ txn_t * txn_begin (txn_access_e access, txn_isolation_e isolation, map_t *m void txn_abort (txn_t *txn); txn_state_e txn_commit (txn_t *txn); -uint64_t tm_get (txn_t *txn, const char *key, uint32_t key_len); -void tm_set (txn_t *txn, const char *key, uint32_t key_len, uint64_t value); +uint64_t tm_get (txn_t *txn, void *key); +void tm_set (txn_t *txn, void *key, uint64_t value); #endif//TXN_H diff --git a/makefile b/makefile index edd6735..21fa6d9 100644 --- a/makefile +++ b/makefile @@ -10,8 +10,8 @@ INCS := $(addprefix -I, include) TESTS := output/map_test1 output/map_test2 output/rcu_test output/txn_test EXES := $(TESTS) -RUNTIME_SRCS := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c -MAP_SRCS := map/map.c map/nstring.c map/list.c map/skiplist.c map/hashtable.c +RUNTIME_SRCS := runtime/runtime.c runtime/rcu.c runtime/lwt.c runtime/mem.c runtime/nstring.c +MAP_SRCS := map/map.c map/list.c map/skiplist.c map/hashtable.c rcu_test_SRCS := $(RUNTIME_SRCS) test/rcu_test.c txn_test_SRCS := $(RUNTIME_SRCS) $(MAP_SRCS) test/txn_test.c test/CuTest.c txn/txn.c diff --git a/map/hashtable.c b/map/hashtable.c index 42ab07e..1039ff0 100644 --- a/map/hashtable.c +++ b/map/hashtable.c @@ -12,33 +12,35 @@ * weaker operations which would still do the job. */ +#include #include "common.h" #include "murmur.h" #include "mem.h" #include "mlocal.h" -#include "nstring.h" -#define GET_PTR(x) ((nstring_t *)((x) & MASK(48))) // low-order 48 bits is a pointer to a nstring_t +#define GET_PTR(x) ((void *)((x) & MASK(48))) // low-order 48 bits is a pointer to a nstring_t typedef struct ht_entry { - uint64_t key; // ptr to nstring_t - uint64_t value; + uint64_t key; + uint64_t val; } entry_t; typedef struct hti { volatile entry_t *table; hashtable_t *ht; // parent ht; struct hti *next; - struct hti *next_free; unsigned int scale; int max_probe; int count; // TODO: make these counters distributed int num_entries_copied; int scan; -} hashtable_i_t; +} hti_t; struct ht { - hashtable_i_t *hti; + hti_t *hti; + cmp_fun_t cmp_fun; + hash_fun_t hash_fun; + clone_fun_t clone_fun; }; static const map_impl_t ht_map_impl = { @@ -56,7 +58,7 @@ static const unsigned ENTRIES_PER_COPY_CHUNK = CACHE_LINE_SIZE/sizeof(entry_t)*2 static const unsigned MIN_SCALE = 4; // min 16 entries (4 buckets) static const unsigned MAX_BUCKETS_TO_PROBE = 250; -static int hti_copy_entry (hashtable_i_t *ht1, volatile entry_t *e, uint32_t e_key_hash, hashtable_i_t *ht2); +static int hti_copy_entry (hti_t *ht1, volatile entry_t *ent, uint32_t ent_key_hash, hti_t *ht2); // Choose the next bucket to probe using the high-order bits of . static inline int get_next_ndx(int old_ndx, uint32_t key_hash, int ht_scale) { @@ -65,27 +67,16 @@ static inline int get_next_ndx(int old_ndx, uint32_t key_hash, int ht_scale) { return (old_ndx + incr) & MASK(ht_scale); } -// Compare two keys. -// -// A key is made up of two parts. The 48 low-order bits are a pointer to a null terminated string. -// The high-order 16 bits are taken from the hash of that string. The bits from the hash are used -// as a quick check to rule out non-equal keys without doing a complete string compare. -static inline int ht_key_equals (uint64_t a, uint32_t b_hash, const char *b_value, uint32_t b_len) { - if ((b_hash >> 16) != (a >> 48)) // high-order 16 bits are from the hash value - return FALSE; - return ns_cmp_raw(GET_PTR(a), b_value, b_len) == 0; -} - // Lookup in . // // Return the entry that is in, or if isn't in return the entry that it would be // in if it were inserted into . If there is no room for in then return NULL, to // indicate that the caller should look in next>. // -// Record if the entry being returned is empty. Otherwise the caller will have to waste time with -// ht_key_equals() to confirm that it did not lose a race to fill an empty entry. -static volatile entry_t *hti_lookup (hashtable_i_t *hti, uint32_t key_hash, const char *key_data, uint32_t key_len, int *is_empty) { - TRACE("h2", "hti_lookup(key %p in hti %p)", key_data, hti); +// Record if the entry being returned is empty. Otherwise the caller will have to waste time +// re-comparing the keys to confirm that it did not lose a race to fill an empty entry. +static volatile entry_t *hti_lookup (hti_t *hti, void *key, uint32_t key_hash, int *is_empty) { + TRACE("h2", "hti_lookup(key %p in hti %p)", key, hti); *is_empty = 0; // Probe one cache line at a time @@ -97,19 +88,31 @@ static volatile entry_t *hti_lookup (hashtable_i_t *hti, uint32_t key_hash, cons // Start searching at the indexed entry. Then loop around to the begining of the cache line. for (int j = 0; j < ENTRIES_PER_BUCKET; ++j) { - volatile entry_t *e = bucket + ((ndx + j) & (ENTRIES_PER_BUCKET-1)); - - uint64_t e_key = e->key; - if (e_key == DOES_NOT_EXIST) { - TRACE("h1", "hti_lookup: entry %p for key \"%s\" is empty", e, GET_PTR(e_key)->data); - *is_empty = 1; // indicate an empty so the caller avoids an expensive ht_key_equals - return e; + volatile entry_t *ent = bucket + ((ndx + j) & (ENTRIES_PER_BUCKET-1)); + + uint64_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->clone_fun == NULL) ? (void *)ent_key : GET_PTR(ent_key)); + *is_empty = 1; // indicate an empty so the caller avoids an expensive key compare + return ent; } - if (ht_key_equals(e_key, key_hash, key_data, key_len)) { - TRACE("h1", "hti_lookup: entry %p key \"%s\"", e, GET_PTR(e_key)->data); - TRACE("h2", "hti_lookup: entry key len %llu, value %p", GET_PTR(e_key)->len, e->value); - return e; + // Compare with the key in the entry. + if (EXPECT_TRUE(hti->ht->cmp_fun == NULL)) { + // fast path for integer keys + if (ent_key == (uint64_t)key) { + TRACE("h1", "hti_lookup: found entry %p with key %p", ent, ent_key); + return ent; + } + } else { + // The key in is made up of two parts. The 48 low-order bits are a pointer. The + // high-order 16 bits are taken from the hash. The bits from the hash are used as a + // quick check to rule out non-equal keys without doing a complete compare. + if ((key_hash >> 16) == (ent_key >> 48) && hti->ht->cmp_fun(GET_PTR(ent_key), key) == 0) { + TRACE("h1", "hti_lookup: found entry %p with key %p", ent, GET_PTR(ent_key)); + return ent; + } } } @@ -121,22 +124,22 @@ static volatile entry_t *hti_lookup (hashtable_i_t *hti, uint32_t key_hash, cons return NULL; } -// Allocate and initialize a hashtable_i_t with 2^ entries. -static hashtable_i_t *hti_alloc (hashtable_t *parent, int scale) { +// Allocate and initialize a hti_t with 2^ entries. +static hti_t *hti_alloc (hashtable_t *parent, int scale) { // Include enough slop to align the actual table on a cache line boundry - size_t n = sizeof(hashtable_i_t) + size_t n = sizeof(hti_t) + sizeof(entry_t) * (1 << scale) + (CACHE_LINE_SIZE - 1); - hashtable_i_t *hti = (hashtable_i_t *)calloc(n, 1); + hti_t *hti = (hti_t *)calloc(n, 1); // Align the table of hash entries on a cache line boundry. - hti->table = (entry_t *)(((uint64_t)hti + sizeof(hashtable_i_t) + (CACHE_LINE_SIZE-1)) + hti->table = (entry_t *)(((uint64_t)hti + sizeof(hti_t) + (CACHE_LINE_SIZE-1)) & ~(CACHE_LINE_SIZE-1)); hti->scale = scale; // 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) + 2; + hti->max_probe = ((1 << (hti->scale - 2)) / ENTRIES_PER_BUCKET) + 4; if (hti->max_probe > MAX_BUCKETS_TO_PROBE) { hti->max_probe = MAX_BUCKETS_TO_PROBE; } @@ -152,8 +155,8 @@ static hashtable_i_t *hti_alloc (hashtable_t *parent, int scale) { // Called when runs out of room for new keys. // -// Initiates a copy by creating a larger hashtable_i_t and installing it in next>. -static void hti_start_copy (hashtable_i_t *hti) { +// Initiates a copy by creating a larger hti_t and installing it in next>. +static void hti_start_copy (hti_t *hti) { TRACE("h0", "hti_start_copy(hti %p scale %llu)", hti, hti->scale); // heuristics to determine the size of the new table @@ -163,8 +166,8 @@ static void hti_start_copy (hashtable_i_t *hti) { new_scale += (count > (1 << (new_scale - 2))); // double size again if more than 1/2 full // Allocate the new table and attempt to install it. - hashtable_i_t *next = hti_alloc(hti->ht, new_scale); - hashtable_i_t *old_next = SYNC_CAS(&hti->next, NULL, next); + hti_t *next = hti_alloc(hti->ht, new_scale); + hti_t *old_next = SYNC_CAS(&hti->next, NULL, next); 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); @@ -174,113 +177,111 @@ static void hti_start_copy (hashtable_i_t *hti) { TRACE("h0", "hti_start_copy: new hti %p scale %llu", next, next->scale); } -// Copy the key and value stored in (which must be an entry in ) to . +// Copy the key and value stored in (which must be an entry in ) to . // -// Return 1 unless is already copied (then return 0), so the caller can account for the total +// Return 1 unless is already copied (then return 0), so the caller can account for the total // number of entries left to copy. -static int hti_copy_entry (hashtable_i_t *ht1, volatile entry_t *ht1_e, uint32_t key_hash, - hashtable_i_t *ht2) { - TRACE("h2", "hti_copy_entry: entry %p to table %p", ht1_e, ht2); +static int hti_copy_entry (hti_t *ht1, volatile entry_t *ht1_ent, uint32_t key_hash, hti_t *ht2) { + TRACE("h2", "hti_copy_entry: entry %p to table %p", ht1_ent, ht2); assert(ht1); assert(ht1->next); assert(ht2); - assert(ht1_e >= ht1->table && ht1_e < ht1->table + (1 << ht1->scale)); - assert(key_hash == 0 || (key_hash >> 16) == (ht1_e->key >> 48)); + assert(ht1_ent >= ht1->table && ht1_ent < ht1->table + (1 << ht1->scale)); + assert(key_hash == 0 || ht1->ht->hash_fun == NULL || (key_hash >> 16) == (ht1_ent->key >> 48)); - uint64_t ht1_e_value = ht1_e->value; - if (EXPECT_FALSE(ht1_e_value == COPIED_VALUE)) { - TRACE("h1", "hti_copy_entry: entry %p already copied to table %p", ht1_e, ht2); + uint64_t ht1_ent_val = ht1_ent->val; + if (EXPECT_FALSE(ht1_ent_val == COPIED_VALUE)) { + TRACE("h1", "hti_copy_entry: entry %p already copied to table %p", ht1_ent, ht2); return FALSE; // already copied } // Kill empty entries. - if (EXPECT_FALSE(ht1_e_value == DOES_NOT_EXIST)) { - uint64_t ht1_e_value = SYNC_CAS(&ht1_e->value, DOES_NOT_EXIST, COPIED_VALUE); - if (ht1_e_value == DOES_NOT_EXIST) { - TRACE("h1", "hti_copy_entry: empty entry %p killed", ht1_e, 0); + if (EXPECT_FALSE(ht1_ent_val == DOES_NOT_EXIST)) { + uint64_t ht1_ent_val = SYNC_CAS(&ht1_ent->val, DOES_NOT_EXIST, COPIED_VALUE); + if (ht1_ent_val == DOES_NOT_EXIST) { + TRACE("h1", "hti_copy_entry: empty entry %p killed", ht1_ent, 0); return TRUE; } - if (ht1_e_value == COPIED_VALUE) { - TRACE("h0", "hti_copy_entry: lost race to kill empty entry %p", ht1_e, 0); + if (ht1_ent_val == COPIED_VALUE) { + TRACE("h0", "hti_copy_entry: lost race to kill empty entry %p; the entry is already killed", ht1_ent, 0); return FALSE; // another thread beat us to it } - TRACE("h0", "hti_copy_entry: lost race to kill empty entry %p; the entry is now" - "in use and should be copied", ht1_e, 0); + TRACE("h0", "hti_copy_entry: lost race to kill empty entry %p; the entry is not empty", ht1_ent, 0); } // Tag the value in the old entry to indicate a copy is in progress. - ht1_e_value = SYNC_FETCH_AND_OR(&ht1_e->value, TAG_VALUE(0)); - TRACE("h2", "hti_copy_entry: tagged the value %p in old entry %p", ht1_e_value, ht1_e); - if (ht1_e_value == COPIED_VALUE) { - TRACE("h1", "hti_copy_entry: entry %p already copied to table %p", ht1_e, ht2); + ht1_ent_val = SYNC_FETCH_AND_OR(&ht1_ent->val, TAG_VALUE(0)); + TRACE("h2", "hti_copy_entry: tagged the value %p in old entry %p", ht1_ent_val, ht1_ent); + if (ht1_ent_val == COPIED_VALUE) { + TRACE("h1", "hti_copy_entry: entry %p already copied to table %p", ht1_ent, ht2); return FALSE; // was already copied by another thread. } - // The old table's deleted entries don't need to be copied to the new table, but their keys need - // to be freed. + // Install the key in the new table. + uint64_t ht1_ent_key = ht1_ent->key; + void *key = (ht1->ht->hash_fun == NULL) ? (void *)ht1_ent_key : GET_PTR(ht1_ent_key); + + // The old table's dead entries don't need to be copied to the new table, but their keys need to be freed. assert(COPIED_VALUE == TAG_VALUE(TOMBSTONE)); - if (ht1_e_value == TOMBSTONE) { - TRACE("h1", "hti_copy_entry: entry %p old value was deleted, now freeing key %p", ht1_e, GET_PTR(ht1_e->key)); - nbd_defer_free(GET_PTR(ht1_e->key)); + if (ht1_ent_val == TOMBSTONE) { + TRACE("h1", "hti_copy_entry: entry %p old value was deleted, now freeing key %p", ht1_ent, key); + if (EXPECT_FALSE(ht1->ht->clone_fun != NULL)) { + nbd_defer_free(key); + } return TRUE; } - // Install the key in the new table. - uint64_t key = ht1_e->key; - nstring_t *key_string = GET_PTR(key); - uint64_t value = STRIP_TAG(ht1_e_value); - - // We use 0 to indicate that isn't initiallized. Occasionally the will - // really be 0 and we will waste time recomputing it. That is rare enough that it is OK. + // 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 (1 in 65k) that it won't hurt performance. if (key_hash == 0) { - key_hash = murmur32(key_string->data, key_string->len); + key_hash = (ht1->ht->hash_fun == NULL) ? murmur32_8b(ht1_ent_key) : ht1->ht->hash_fun(key); } - int is_empty; - volatile entry_t *ht2_e = hti_lookup(ht2, key_hash, key_string->data, key_string->len, &is_empty); - TRACE("h0", "hti_copy_entry: copy entry %p to entry %p", ht1_e, ht2_e); + int ht2_ent_is_empty; + volatile entry_t *ht2_ent = hti_lookup(ht2, key, key_hash, &ht2_ent_is_empty); + TRACE("h0", "hti_copy_entry: copy entry %p to entry %p", ht1_ent, ht2_ent); - // it is possible that there is not any room in the new table either - if (EXPECT_FALSE(ht2_e == NULL)) { + // It is possible that there isn't any room in the new table either. + if (EXPECT_FALSE(ht2_ent == NULL)) { TRACE("h0", "hti_copy_entry: no room in table %p copy to next table %p", ht2, ht2->next); if (ht2->next == NULL) { hti_start_copy(ht2); // initiate nested copy, if not already started } - return hti_copy_entry(ht1, ht1_e, key_hash, ht2->next); // recursive tail-call + return hti_copy_entry(ht1, ht1_ent, key_hash, ht2->next); // recursive tail-call } - // a tagged entry returned from hti_lookup() means it is either empty or has a new key - if (is_empty) { - uint64_t old_ht2_e_key = SYNC_CAS(&ht2_e->key, DOES_NOT_EXIST, key); - if (old_ht2_e_key != DOES_NOT_EXIST) { + if (ht2_ent_is_empty) { + uint64_t old_ht2_ent_key = SYNC_CAS(&ht2_ent->key, DOES_NOT_EXIST, ht1_ent_key); + if (old_ht2_ent_key != DOES_NOT_EXIST) { TRACE("h0", "hti_copy_entry: lost race to CAS key %p into new entry; found %p", - key, old_ht2_e_key); - return hti_copy_entry(ht1, ht1_e, key_hash, ht2); // recursive tail-call + ht1_ent_key, old_ht2_ent_key); + return hti_copy_entry(ht1, ht1_ent, key_hash, ht2); // recursive tail-call } } // Copy the value to the entry in the new table. - uint64_t old_ht2_e_value = SYNC_CAS(&ht2_e->value, DOES_NOT_EXIST, value); + ht1_ent_val = STRIP_TAG(ht1_ent_val); + uint64_t old_ht2_ent_val = SYNC_CAS(&ht2_ent->val, DOES_NOT_EXIST, ht1_ent_val); // If there is a nested copy in progress, we might have installed the key into a dead entry. - if (old_ht2_e_value == COPIED_VALUE) { - TRACE("h0", "hti_copy_entry: nested copy in progress; copy %p to next table %p", ht2_e, ht2->next); - return hti_copy_entry(ht1, ht1_e, key_hash, ht2->next); // recursive tail-call + if (old_ht2_ent_val == COPIED_VALUE) { + TRACE("h0", "hti_copy_entry: nested copy in progress; copy %p to next table %p", ht2_ent, ht2->next); + return hti_copy_entry(ht1, ht1_ent, key_hash, ht2->next); // recursive tail-call } // Mark the old entry as dead. - ht1_e->value = COPIED_VALUE; + ht1_ent->val = COPIED_VALUE; // Update the count if we were the one that completed the copy. - if (old_ht2_e_value == DOES_NOT_EXIST) { - TRACE("h0", "hti_copy_entry: key \"%s\" value %p copied to new entry", key_string->data, value); + 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); return TRUE; } TRACE("h0", "hti_copy_entry: lost race to install value %p in new entry; found value %p", - value, old_ht2_e_value); + ht1_ent_val, old_ht2_ent_val); return FALSE; // another thread completed the copy } @@ -295,22 +296,21 @@ static int hti_copy_entry (hashtable_i_t *ht1, volatile entry_t *ht1_e, uint32_t // NOTE: the returned value matches iff the set succeeds // // Certain values of have special meaning. If is CAS_EXPECT_EXISTS then any -// real value matches (i.e. not a TOMBSTONE or DOES_NOT_EXIST) as long as is in the table. If +// real value matches (i.ent. not a TOMBSTONE or DOES_NOT_EXIST) as long as is in the table. If // is CAS_EXPECT_WHATEVER then skip the test entirely. // -static uint64_t hti_cas (hashtable_i_t *hti, uint32_t key_hash, const char *key_data, uint32_t key_len, - uint64_t expected, uint64_t new) { - TRACE("h1", "hti_cas: hti %p key %p", hti, key_data); +static uint64_t hti_cas (hti_t *hti, void *key, uint32_t key_hash, uint64_t expected, uint64_t new) { + TRACE("h1", "hti_cas: hti %p key %p", hti, key); TRACE("h1", "hti_cas: value %p expect %p", new, expected); assert(hti); assert(new != DOES_NOT_EXIST && !IS_TAGGED(new)); - assert(key_data); + assert(key); int is_empty; - volatile entry_t *e = hti_lookup(hti, key_hash, key_data, key_len, &is_empty); + volatile entry_t *ent = hti_lookup(hti, key, key_hash, &is_empty); // There is no room for , grow the table and try again. - if (e == NULL) { + if (ent == NULL) { if (hti->next == NULL) { hti_start_copy(hti); } @@ -319,7 +319,7 @@ static uint64_t hti_cas (hashtable_i_t *hti, uint32_t key_hash, const char *key_ // Install in the table if it doesn't exist. if (is_empty) { - TRACE("h0", "hti_cas: entry %p is empty", e, 0); + TRACE("h0", "hti_cas: entry %p is empty", ent, 0); if (expected != CAS_EXPECT_WHATEVER && expected != CAS_EXPECT_DOES_NOT_EXIST) return DOES_NOT_EXIST; @@ -327,30 +327,37 @@ static uint64_t hti_cas (hashtable_i_t *hti, uint32_t key_hash, const char *key_ if (new == TOMBSTONE) return DOES_NOT_EXIST; - // Allocate . - nstring_t *key = ns_alloc(key_data, key_len); + // Allocate . + uint64_t new_key = (uint64_t)((hti->ht->clone_fun == NULL) ? key : hti->ht->clone_fun(key)); + if (EXPECT_FALSE(hti->ht->hash_fun != NULL)) { + // Combine pointer with bits from its hash + new_key = ((uint64_t)(key_hash >> 16) << 48) | new_key; + } - // Combine pointer with bits from its hash, CAS it into the table. - uint64_t temp = ((uint64_t)(key_hash >> 16) << 48) | (uint64_t)key; - uint64_t e_key = SYNC_CAS(&e->key, DOES_NOT_EXIST, temp); + // CAS the key into the table. + uint64_t old_ent_key = SYNC_CAS(&ent->key, DOES_NOT_EXIST, new_key); // Retry if another thread stole the entry out from under us. - if (e_key != DOES_NOT_EXIST) { - TRACE("h0", "hti_cas: lost race to install key %p in entry %p", key, e); - TRACE("h0", "hti_cas: found %p instead of NULL", GET_PTR(e_key), 0); - nbd_free(key); - return hti_cas(hti, key_hash, key_data, key_len, expected, new); // tail-call + if (old_ent_key != DOES_NOT_EXIST) { + TRACE("h0", "hti_cas: lost race to install key %p in entry %p", new_key, ent); + TRACE("h0", "hti_cas: found %p instead of NULL", + (hti->ht->clone_fun != NULL) ? (void *)old_ent_key : GET_PTR(old_ent_key), 0); + if (hti->ht->clone_fun != NULL) { + nbd_free(GET_PTR(new_key)); + } + return hti_cas(hti, key, key_hash, expected, new); // tail-call } - TRACE("h2", "hti_cas: installed key %p in entry %p", key, e); + TRACE("h2", "hti_cas: installed key %p in entry %p", new_key, ent); } - TRACE("h0", "hti_cas: entry for key \"%s\" is %p", GET_PTR(e->key)->data, e); + TRACE("h0", "hti_cas: entry for key %p is %p", + (hti->ht->clone_fun != NULL) ? (void *)ent->key : GET_PTR(ent->key), ent); // If the entry is in the middle of a copy, the copy must be completed first. - uint64_t e_value = e->value; - if (EXPECT_FALSE(IS_TAGGED(e_value))) { - if (e_value != COPIED_VALUE) { - int did_copy = hti_copy_entry(hti, e, key_hash, ((volatile hashtable_i_t *)hti)->next); + uint64_t ent_val = ent->val; + if (EXPECT_FALSE(IS_TAGGED(ent_val))) { + if (ent_val != COPIED_VALUE) { + int did_copy = hti_copy_entry(hti, ent, key_hash, ((volatile hti_t *)hti)->next); if (did_copy) { SYNC_ADD(&hti->num_entries_copied, 1); } @@ -362,26 +369,26 @@ static uint64_t hti_cas (hashtable_i_t *hti, uint32_t key_hash, const char *key_ } // Fail if the old value is not consistent with the caller's expectation. - int old_existed = (e_value != TOMBSTONE && e_value != DOES_NOT_EXIST); - if (EXPECT_FALSE(expected != CAS_EXPECT_WHATEVER && expected != e_value)) { + int old_existed = (ent_val != TOMBSTONE && ent_val != DOES_NOT_EXIST); + if (EXPECT_FALSE(expected != CAS_EXPECT_WHATEVER && expected != ent_val)) { if (EXPECT_FALSE(expected != (old_existed ? CAS_EXPECT_EXISTS : CAS_EXPECT_DOES_NOT_EXIST))) { TRACE("h1", "hti_cas: value %p expected by caller not found; found value %p", - expected, e_value); - return e_value; + expected, ent_val); + return ent_val; } } // No need to update if value is unchanged. - if ((new == TOMBSTONE && !old_existed) || e_value == new) { + if ((new == TOMBSTONE && !old_existed) || ent_val == new) { TRACE("h1", "hti_cas: old value and new value were the same", 0, 0); - return e_value; + return ent_val; } // CAS the value into the entry. Retry if it fails. - uint64_t v = SYNC_CAS(&e->value, e_value, new); - if (EXPECT_FALSE(v != e_value)) { - TRACE("h0", "hti_cas: value CAS failed; expected %p found %p", e_value, v); - return hti_cas(hti, key_hash, key_data, key_len, expected, new); // recursive tail-call + uint64_t v = SYNC_CAS(&ent->val, ent_val, new); + if (EXPECT_FALSE(v != ent_val)) { + TRACE("h0", "hti_cas: value CAS failed; expected %p found %p", ent_val, v); + return hti_cas(hti, key, key_hash, expected, new); // recursive tail-call } // The set succeeded. Adjust the value count. @@ -392,23 +399,21 @@ static uint64_t hti_cas (hashtable_i_t *hti, uint32_t key_hash, const char *key_ } // Return the previous value. - TRACE("h0", "hti_cas: CAS succeeded; old value %p new value %p", e_value, new); - return e_value; + TRACE("h0", "hti_cas: CAS succeeded; old value %p new value %p", ent_val, new); + return ent_val; } // -static uint64_t hti_get (hashtable_i_t *hti, uint32_t key_hash, const char *key_data, uint32_t key_len) { - assert(key_data); - +static uint64_t hti_get (hti_t *hti, void *key, uint32_t key_hash) { int is_empty; - volatile entry_t *e = hti_lookup(hti, key_hash, key_data, key_len, &is_empty); + volatile entry_t *ent = hti_lookup(hti, key, key_hash, &is_empty); // When hti_lookup() returns NULL it means we hit the reprobe limit while // searching the table. In that case, if a copy is in progress the key // might exist in the copy. - if (EXPECT_FALSE(e == NULL)) { - if (((volatile hashtable_i_t *)hti)->next != NULL) - return hti_get(hti->next, key_hash, key_data, key_len); // recursive tail-call + if (EXPECT_FALSE(ent == NULL)) { + if (((volatile hti_t *)hti)->next != NULL) + return hti_get(hti->next, key, key_hash); // recursive tail-call return DOES_NOT_EXIST; } @@ -416,38 +421,39 @@ static uint64_t hti_get (hashtable_i_t *hti, uint32_t key_hash, const char *key_ return DOES_NOT_EXIST; // If the entry is being copied, finish the copy and retry on the next table. - uint64_t e_value = e->value; - if (EXPECT_FALSE(IS_TAGGED(e_value))) { - if (EXPECT_FALSE(e_value != COPIED_VALUE)) { - int did_copy = hti_copy_entry(hti, e, key_hash, ((volatile hashtable_i_t *)hti)->next); + uint64_t ent_val = ent->val; + if (EXPECT_FALSE(IS_TAGGED(ent_val))) { + if (EXPECT_FALSE(ent_val != COPIED_VALUE)) { + int did_copy = hti_copy_entry(hti, ent, key_hash, ((volatile hti_t *)hti)->next); if (did_copy) { SYNC_ADD(&hti->num_entries_copied, 1); } } - return hti_get(((volatile hashtable_i_t *)hti)->next, key_hash, key_data, key_len); // tail-call + return hti_get(((volatile hti_t *)hti)->next, key, key_hash); // tail-call } - return (e_value == TOMBSTONE) ? DOES_NOT_EXIST : e_value; + return (ent_val == TOMBSTONE) ? DOES_NOT_EXIST : ent_val; } // -uint64_t ht_get (hashtable_t *ht, const char *key_data, uint32_t key_len) { - return hti_get(ht->hti, murmur32(key_data, key_len), key_data, key_len); +uint64_t ht_get (hashtable_t *ht, void *key) { + uint32_t hash = (ht->hash_fun == NULL) ? murmur32_8b((uint64_t)key) : ht->hash_fun(key); + return hti_get(ht->hti, key, hash); } // -uint64_t ht_cas (hashtable_t *ht, const char *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val) { +uint64_t ht_cas (hashtable_t *ht, void *key, uint64_t expected_val, uint64_t new_val) { - TRACE("h2", "ht_cas: key %p len %u", key_data, key_len); + TRACE("h2", "ht_cas: key %p ht %p", key, ht); TRACE("h2", "ht_cas: expected val %p new val %p", expected_val, new_val); - assert(key_data); - assert(!IS_TAGGED(new_val) && new_val != DOES_NOT_EXIST); + assert(key != DOES_NOT_EXIST); + assert(!IS_TAGGED(new_val) && new_val != DOES_NOT_EXIST && new_val != TOMBSTONE); - hashtable_i_t *hti = ht->hti; + hti_t *hti = ht->hti; // Help with an ongoing copy. if (EXPECT_FALSE(hti->next != NULL)) { - volatile entry_t *e; + volatile entry_t *ent; uint64_t limit; int num_copied = 0; int x = hti->scan; @@ -465,18 +471,18 @@ uint64_t ht_cas (hashtable_t *ht, const char *key_data, uint32_t key_len, uint64 // scan> might be larger than the size of the table, if some thread stalls while // copying. In that case we just wrap around to the begining and make another pass through // the table. - e = hti->table + (x & MASK(hti->scale)); + ent = hti->table + (x & MASK(hti->scale)); } else { TRACE("h1", "ht_cas: help copy panic", 0, 0); // scan the whole table limit = (1 << hti->scale); - e = hti->table; + ent = hti->table; } // Copy the entries for (int i = 0; i < limit; ++i) { - num_copied += hti_copy_entry(hti, e++, 0, hti->next); - assert(e <= hti->table + (1 << hti->scale)); + num_copied += hti_copy_entry(hti, ent++, 0, hti->next); + assert(ent <= hti->table + (1 << hti->scale)); } if (num_copied != 0) { SYNC_ADD(&hti->num_entries_copied, num_copied); @@ -492,9 +498,8 @@ uint64_t ht_cas (hashtable_t *ht, const char *key_data, uint32_t key_len, uint64 } uint64_t old_val; - uint32_t key_hash = murmur32(key_data, key_len); - while ((old_val = hti_cas(hti, key_hash, key_data, key_len, expected_val, new_val)) - == COPIED_VALUE) { + uint32_t key_hash = (ht->hash_fun == NULL) ? murmur32_8b((uint64_t)key) : ht->hash_fun(key); + while ((old_val = hti_cas(hti, key, key_hash, expected_val, new_val)) == COPIED_VALUE) { assert(hti->next); hti = hti->next; } @@ -502,14 +507,14 @@ uint64_t ht_cas (hashtable_t *ht, const char *key_data, uint32_t key_len, uint64 return old_val == TOMBSTONE ? DOES_NOT_EXIST : old_val; } -// Remove the value in associated with . Returns the value removed, or -// DOES_NOT_EXIST if there was no value for that key. -uint64_t ht_remove (hashtable_t *ht, const char *key_data, uint32_t key_len) { - hashtable_i_t *hti = ht->hti; +// Remove the value in associated with . Returns the value removed, or DOES_NOT_EXIST if there was +// no value for that key. +uint64_t ht_remove (hashtable_t *ht, void *key) { + hti_t *hti = ht->hti; uint64_t val; - uint32_t key_hash = murmur32(key_data, key_len); + uint32_t key_hash = (ht->hash_fun == NULL) ? murmur32_8b((uint64_t)key) : ht->hash_fun(key); do { - val = hti_cas(hti, key_hash, key_data, key_len, CAS_EXPECT_WHATEVER, TOMBSTONE); + val = hti_cas(hti, key, key_hash, CAS_EXPECT_WHATEVER, TOMBSTONE); if (val != COPIED_VALUE) return val == TOMBSTONE ? DOES_NOT_EXIST : val; assert(hti->next); @@ -520,7 +525,7 @@ uint64_t ht_remove (hashtable_t *ht, const char *key_data, uint32_t key_len) { // Returns the number of key-values pairs in uint64_t ht_count (hashtable_t *ht) { - hashtable_i_t *hti = ht->hti; + hti_t *hti = ht->hti; uint64_t count = 0; while (hti) { count += hti->count; @@ -530,23 +535,26 @@ uint64_t ht_count (hashtable_t *ht) { } // Allocate and initialize a new hash table. -hashtable_t *ht_alloc (void) { +hashtable_t *ht_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun) { hashtable_t *ht = nbd_malloc(sizeof(hashtable_t)); - ht->hti = (hashtable_i_t *)hti_alloc(ht, MIN_SCALE); + ht->cmp_fun = cmp_fun; + ht->hash_fun = hash_fun; + ht->clone_fun = clone_fun; + ht->hti = (hti_t *)hti_alloc(ht, MIN_SCALE); return ht; } // Free and its internal structures. void ht_free (hashtable_t *ht) { - hashtable_i_t *hti = ht->hti; + hti_t *hti = ht->hti; do { for (uint32_t i = 0; i < (1 << hti->scale); ++i) { - assert(hti->table[i].value == COPIED_VALUE || !IS_TAGGED(hti->table[i].value)); - if (hti->table[i].key != DOES_NOT_EXIST) { + assert(hti->table[i].val == COPIED_VALUE || !IS_TAGGED(hti->table[i].val)); + if (ht->clone_fun != NULL && hti->table[i].key != DOES_NOT_EXIST) { nbd_free(GET_PTR(hti->table[i].key)); } } - hashtable_i_t *next = hti->next; + hti_t *next = hti->next; nbd_free(hti); hti = next; } while (hti); @@ -554,4 +562,17 @@ void ht_free (hashtable_t *ht) { } void ht_print (hashtable_t *ht) { + hti_t *hti = ht->hti; + while (hti) { + printf("hti:%p scale:%u count:%d copied:%d\n", hti, hti->scale, hti->count, hti->num_entries_copied); + for (int i = 0; i < (1 << hti->scale); ++i) { + volatile entry_t *ent = hti->table + i; + printf("[0x%x] %p:%p\n", i, (void *)ent->key, (void *)ent->val); + if (i > 30) { + printf("...\n"); + break; + } + } + hti = hti->next; + } } diff --git a/map/list.c b/map/list.c index e726cb1..979c91e 100644 --- a/map/list.c +++ b/map/list.c @@ -11,17 +11,18 @@ #include "common.h" #include "mlocal.h" -#include "nstring.h" #include "mem.h" typedef struct node { - nstring_t *key; + void *key; uint64_t val; struct node *next; } node_t; struct ll { node_t *head; + cmp_fun_t cmp_fun; + clone_fun_t clone_fun; }; static const map_impl_t ll_map_impl = { @@ -31,34 +32,18 @@ static const map_impl_t ll_map_impl = { const map_impl_t *MAP_TYPE_LIST = &ll_map_impl; -static node_t *node_alloc (const void *key_data, uint32_t key_len, uint64_t val) { +static node_t *node_alloc (void *key, uint64_t val) { node_t *item = (node_t *)nbd_malloc(sizeof(node_t)); - memset(item, 0, sizeof(node_t)); - // If is -1 it indicates is an integer and not a pointer - item->key = (key_len == (unsigned)-1) - ? (void *)TAG_VALUE(key_data) - : ns_alloc(key_data, key_len); + item->key = key; item->val = val; return item; } -static void node_free (node_t *item) { - if (!IS_TAGGED(item->key)) { - nbd_free(item->key); - } - nbd_free(item); -} - -static void node_defer_free (node_t *item) { - if (!IS_TAGGED(item->key)) { - nbd_defer_free(item->key); - } - nbd_defer_free(item); -} - -list_t *ll_alloc (void) { +list_t *ll_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun) { list_t *ll = (list_t *)nbd_malloc(sizeof(list_t)); - ll->head = node_alloc(" ", 0, 0); + ll->cmp_fun = cmp_fun; + ll->clone_fun = clone_fun; + ll->head = node_alloc(NULL, 0); ll->head->next = NULL; return ll; } @@ -82,10 +67,10 @@ uint64_t ll_count (list_t *ll) { return count; } -static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, const void *key_data, uint32_t key_len, int help_remove) { +static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, void *key, int help_remove) { node_t *pred = ll->head; node_t *item = pred->next; - TRACE("l2", "find_pred: searching for key %p in ll (head is %p)", key_data, pred); + TRACE("l2", "find_pred: searching for key %p in list (head is %p)", key, pred); while (item != NULL) { node_t *next = item->next; @@ -115,12 +100,15 @@ static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, const vo TRACE("l3", "find_pred: now current item is %p next is %p", item, next); // The thread that completes the unlink should free the memory. - node_defer_free(other); + if (ll->clone_fun != NULL) { + nbd_defer_free((void*)other->key); + } + nbd_defer_free(other); } else { TRACE("l2", "find_pred: lost a race to unlink item %p from pred %p", item, pred); TRACE("l2", "find_pred: pred's link changed to %p", other, 0); if (IS_TAGGED(other)) - return find_pred(pred_ptr, item_ptr, ll, key_data, key_len, help_remove); // retry + return find_pred(pred_ptr, item_ptr, ll, key, help_remove); // retry item = other; if (EXPECT_FALSE(item == NULL)) break; @@ -132,17 +120,13 @@ static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, const vo break; TRACE("l3", "find_pred: visiting item %p (next is %p)", item, next); - TRACE("l4", "find_pred: key %p val %p", STRIP_TAG(item->key), item->val); + TRACE("l4", "find_pred: key %p val %p", item->key, item->val); - // A tagged key is an integer, otherwise it is a pointer to a string int d; - if (IS_TAGGED(item->key)) { - d = (STRIP_TAG(item->key) - (uint64_t)key_data); + if (EXPECT_TRUE(ll->cmp_fun == NULL)) { + d = (uint64_t)item->key - (uint64_t)key; } else { - int item_key_len = item->key->len; - int len = (key_len < item_key_len) ? key_len : item_key_len; - d = memcmp(item->key->data, key_data, len); - if (d == 0) { d = item_key_len - key_len; } + d = ll->cmp_fun(item->key, key); } // If we reached the key (or passed where it should be), we found the right predesssor @@ -155,7 +139,7 @@ static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, const vo TRACE("l2", "find_pred: found matching item %p in list, pred is %p", item, pred); return TRUE; } - TRACE("l2", "find_pred: found proper place for key %p in list, pred is %p", key_data, pred); + TRACE("l2", "find_pred: found proper place for key %p in list, pred is %p", key, pred); return FALSE; } @@ -173,10 +157,10 @@ static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, const vo } // Fast find. Do not help unlink partially removed nodes and do not return the found item's predecessor. -uint64_t ll_lookup (list_t *ll, const void *key_data, uint32_t key_len) { - TRACE("l1", "ll_lookup: searching for key %p in list %p", key_data, ll); +uint64_t ll_lookup (list_t *ll, void *key) { + TRACE("l1", "ll_lookup: searching for key %p in list %p", key, ll); node_t *item; - int found = find_pred(NULL, &item, ll, key_data, key_len, FALSE); + int found = find_pred(NULL, &item, ll, key, FALSE); // If we found an matching the key return its value. if (found) { @@ -191,14 +175,15 @@ uint64_t ll_lookup (list_t *ll, const void *key_data, uint32_t key_len) { return DOES_NOT_EXIST; } -uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t expectation, uint64_t new_val) { - TRACE("l1", "ll_cas: key %p list %p", key_data, ll); +uint64_t ll_cas (list_t *ll, void *key, uint64_t expectation, uint64_t new_val) { + TRACE("l1", "ll_cas: key %p list %p", key, ll); TRACE("l1", "ll_cas: expectation %p new value %p", expectation, new_val); ASSERT((int64_t)new_val > 0); do { node_t *pred, *old_item; - if (!find_pred(&pred, &old_item, ll, key_data, key_len, TRUE)) { + int found = find_pred(&pred, &old_item, ll, key, TRUE); + if (!found) { // There was not an item in the list that matches the key. if (EXPECT_FALSE((int64_t)expectation > 0 || expectation == CAS_EXPECT_EXISTS)) { @@ -210,7 +195,8 @@ uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t ex // Create a new item and insert it into the list. TRACE("l2", "ll_cas: attempting to insert item between %p and %p", pred, pred->next); - node_t *new_item = node_alloc(key_data, key_len, new_val); + void *new_key = (ll->clone_fun == NULL) ? key : ll->clone_fun(key); + node_t *new_item = node_alloc(new_key, new_val); node_t *next = new_item->next = old_item; node_t *other = SYNC_CAS(&pred->next, next, new_item); if (other == next) { @@ -220,7 +206,10 @@ uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t ex // Lost a race. Failed to insert the new item into the list. TRACE("l1", "ll_cas: lost a race. CAS failed. expected pred's link to be %p but found %p", next, other); - node_free(new_item); + if (ll->clone_fun != NULL) { + nbd_free(new_key); + } + nbd_free(new_item); continue; // retry } @@ -255,11 +244,11 @@ uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t ex } while (1); } -uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len) { - TRACE("l1", "ll_remove: removing item with key %p from list %p", key_data, ll); +uint64_t ll_remove (list_t *ll, void *key) { + TRACE("l1", "ll_remove: removing item with key %p from list %p", key, ll); node_t *pred; node_t *item; - int found = find_pred(&pred, &item, ll, key_data, key_len, TRUE); + int found = find_pred(&pred, &item, ll, key, TRUE); if (!found) { TRACE("l1", "ll_remove: remove failed, an item with a matching key does not exist in the list", 0, 0); return DOES_NOT_EXIST; @@ -295,7 +284,10 @@ uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len) { } // The thread that completes the unlink should free the memory. - node_defer_free(item); + if (ll->clone_fun != NULL) { + nbd_defer_free(item->key); + } + nbd_defer_free(item); TRACE("l1", "ll_remove: successfully unlinked item %p from the list", item, 0); return val; } @@ -303,19 +295,19 @@ uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len) { void ll_print (list_t *ll) { node_t *item; item = ll->head->next; + int i = 0; while (item) { node_t *next = item->next; if (IS_TAGGED(item)) { printf("*"); } - printf("%p:", item); - if (IS_TAGGED(item->key)) { - printf("0x%llx ", STRIP_TAG(item->key)); - } else { - printf("%s ", (char *)item->key->data); - } + printf("%p:%p ", item, item->key); fflush(stdout); item = (node_t *)STRIP_TAG(next); + if (i++ > 30) { + printf("..."); + break; + } } printf("\n"); } diff --git a/map/map.c b/map/map.c index cb761ef..c4749b3 100644 --- a/map/map.c +++ b/map/map.c @@ -15,11 +15,11 @@ struct map { void *data; }; -map_t *map_alloc (map_type_t map_type) { +map_t *map_alloc (map_type_t map_type, cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun) { const map_impl_t *map_impl = map_type; map_t *map = nbd_malloc(sizeof(map_t)); map->impl = map_impl; - map->data = map->impl->alloc(); + map->data = map->impl->alloc(cmp_fun, hash_fun, clone_fun); return map; } @@ -35,26 +35,26 @@ uint64_t map_count (map_t *map) { return map->impl->count(map->data); } -uint64_t map_get (map_t *map, const void *key_data, uint32_t key_len) { - return map->impl->get(map->data, key_data, key_len); +uint64_t map_get (map_t *map, void *key) { + return map->impl->get(map->data, key); } -uint64_t map_set (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val) { - return map->impl->cas(map->data, key_data, key_len, CAS_EXPECT_WHATEVER, new_val); +uint64_t map_set (map_t *map, void *key, uint64_t new_val) { + return map->impl->cas(map->data, key, CAS_EXPECT_WHATEVER, new_val); } -uint64_t map_add (map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val) { - return map->impl->cas(map->data, key_data, key_len, CAS_EXPECT_DOES_NOT_EXIST, new_val); +uint64_t map_add (map_t *map, void *key, uint64_t new_val) { + return map->impl->cas(map->data, key, CAS_EXPECT_DOES_NOT_EXIST, new_val); } -uint64_t map_cas (map_t *map, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val) { - return map->impl->cas(map->data, key_data, key_len, expected_val, new_val); +uint64_t map_cas (map_t *map, void *key, uint64_t expected_val, uint64_t new_val) { + return map->impl->cas(map->data, key, expected_val, new_val); } -uint64_t map_replace(map_t *map, const void *key_data, uint32_t key_len, uint64_t new_val) { - return map->impl->cas(map->data, key_data, key_len, CAS_EXPECT_EXISTS, new_val); +uint64_t map_replace(map_t *map, void *key, uint64_t new_val) { + return map->impl->cas(map->data, key, CAS_EXPECT_EXISTS, new_val); } -uint64_t map_remove (map_t *map, const void *key_data, uint32_t key_len) { - return map->impl->remove(map->data, key_data, key_len); +uint64_t map_remove (map_t *map, void *key) { + return map->impl->remove(map->data, key); } diff --git a/map/mlocal.h b/map/mlocal.h index 9336ab7..1dae928 100644 --- a/map/mlocal.h +++ b/map/mlocal.h @@ -1,14 +1,16 @@ #ifndef MLOCAL_H #define MLOCAL_H +#include "map.h" + #define CAS_EXPECT_DOES_NOT_EXIST ( 0) #define CAS_EXPECT_EXISTS (-1) #define CAS_EXPECT_WHATEVER (-2) -typedef void * (*map_alloc_t) (void); -typedef uint64_t (*map_cas_t) (void *, const void *, uint32_t, uint64_t, uint64_t); -typedef uint64_t (*map_get_t) (void *, const void *, uint32_t); -typedef uint64_t (*map_remove_t) (void *, const void *, uint32_t); +typedef void * (*map_alloc_t) (cmp_fun_t, hash_fun_t, clone_fun_t); +typedef uint64_t (*map_cas_t) (void *, void *, uint64_t, uint64_t); +typedef uint64_t (*map_get_t) (void *, void *); +typedef uint64_t (*map_remove_t) (void *, void *); typedef uint64_t (*map_count_t) (void *); typedef void (*map_print_t) (void *); typedef void (*map_free_t) (void *); @@ -27,27 +29,27 @@ typedef struct ht hashtable_t; typedef struct sl skiplist_t; typedef struct ll list_t; -hashtable_t * ht_alloc (void); -skiplist_t * sl_alloc (void); -list_t * ll_alloc (void); +hashtable_t * ht_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun); +skiplist_t * sl_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun); +list_t * ll_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun); -uint64_t ht_cas (hashtable_t *ht, const char *key, uint32_t key_len, uint64_t expected_val, uint64_t val); -uint64_t ht_get (hashtable_t *ht, const char *key, uint32_t len); -uint64_t ht_remove (hashtable_t *ht, const char *key, uint32_t len); +uint64_t ht_cas (hashtable_t *ht, void *key, uint64_t expected_val, uint64_t val); +uint64_t ht_get (hashtable_t *ht, void *key); +uint64_t ht_remove (hashtable_t *ht, void *key); uint64_t ht_count (hashtable_t *ht); void ht_print (hashtable_t *ht); void ht_free (hashtable_t *ht); -uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val); -uint64_t sl_lookup (skiplist_t *sl, const void *key_data, uint32_t key_len); -uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len); +uint64_t sl_cas (skiplist_t *sl, void *key, uint64_t expected_val, uint64_t new_val); +uint64_t sl_lookup (skiplist_t *sl, void *key); +uint64_t sl_remove (skiplist_t *sl, void *key); uint64_t sl_count (skiplist_t *sl); void sl_print (skiplist_t *sl); void sl_free (skiplist_t *sl); -uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val); -uint64_t ll_lookup (list_t *ll, const void *key_data, uint32_t key_len); -uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len); +uint64_t ll_cas (list_t *ll, void *key, uint64_t expected_val, uint64_t new_val); +uint64_t ll_lookup (list_t *ll, void *key); +uint64_t ll_remove (list_t *ll, void *key); uint64_t ll_count (list_t *ll); void ll_print (list_t *ll); void ll_free (list_t *ll); diff --git a/map/nstring.c b/map/nstring.c deleted file mode 100644 index db35ee1..0000000 --- a/map/nstring.c +++ /dev/null @@ -1,15 +0,0 @@ -#include "common.h" -#include "nstring.h" -#include "mem.h" - -nstring_t *ns_alloc (const void *data, uint32_t len) { - nstring_t *ns = nbd_malloc(sizeof(nstring_t) + len); - ns->len = len; - memcpy(ns->data, data, len); - return ns; -} - -int ns_cmp_raw (nstring_t *ns, const void *data, uint32_t len) { - int d = memcmp(ns->data, data, (len < ns->len) ? len : ns->len); - return (d == 0) ? ns->len - len : d; -} diff --git a/map/nstring.h b/map/nstring.h deleted file mode 100644 index 9aa4ce4..0000000 --- a/map/nstring.h +++ /dev/null @@ -1,12 +0,0 @@ -#ifndef NSTRING_H -#define NSTRING_H - -typedef struct nstring { - uint32_t len; - char data[]; -} nstring_t; - -nstring_t * ns_alloc (const void *data, uint32_t len); -int ns_cmp_raw (nstring_t *ns, const void *data, uint32_t len); - -#endif//NSTRING_H diff --git a/map/skiplist.c b/map/skiplist.c index ec8a6ff..66bfb2d 100644 --- a/map/skiplist.c +++ b/map/skiplist.c @@ -17,10 +17,11 @@ #include #include +#define ENABLE_TRACE + #include "common.h" #include "runtime.h" #include "mlocal.h" -#include "nstring.h" #include "mem.h" #include "tls.h" @@ -29,7 +30,7 @@ #define MAX_LEVEL 31 typedef struct node { - nstring_t *key; + void *key; uint64_t val; int top_level; struct node *next[]; @@ -37,6 +38,8 @@ typedef struct node { struct sl { node_t *head; + cmp_fun_t cmp_fun; + clone_fun_t clone_fun; }; static const map_impl_t sl_map_impl = { @@ -58,37 +61,22 @@ static int random_level (void) { return n; } -static node_t *node_alloc (int level, const void *key_data, uint32_t key_len, uint64_t val) { +static node_t *node_alloc (int level, void *key, uint64_t val) { assert(level >= 0 && level <= MAX_LEVEL); size_t sz = sizeof(node_t) + (level + 1) * sizeof(node_t *); node_t *item = (node_t *)nbd_malloc(sz); memset(item, 0, sz); - // If is -1 it indicates is an integer and not a pointer - item->key = (key_len == (unsigned)-1) - ? (void *)TAG_VALUE(key_data) - : ns_alloc(key_data, key_len); + item->key = key; item->val = val; item->top_level = level; return item; } -static void node_free (node_t *item) { - if (!IS_TAGGED(item->key)) { - nbd_free(item->key); - } - nbd_free(item); -} - -static void node_defer_free (node_t *item) { - if (!IS_TAGGED(item->key)) { - nbd_defer_free(item->key); - } - nbd_defer_free(item); -} - -skiplist_t *sl_alloc (void) { +skiplist_t *sl_alloc (cmp_fun_t cmp_fun, hash_fun_t hash_fun, clone_fun_t clone_fun) { skiplist_t *sl = (skiplist_t *)nbd_malloc(sizeof(skiplist_t)); - sl->head = node_alloc(MAX_LEVEL, " ", 0, 0); + sl->cmp_fun = cmp_fun; + sl->clone_fun = clone_fun; + sl->head = node_alloc(MAX_LEVEL, NULL, 0); memset(sl->head->next, 0, (MAX_LEVEL+1) * sizeof(skiplist_t *)); return sl; } @@ -106,16 +94,18 @@ uint64_t sl_count (skiplist_t *sl) { uint64_t count = 0; node_t *item = sl->head->next[0]; while (item) { - count++; + if (!IS_TAGGED(item->next[0])) { + count++; + } item = (node_t *)STRIP_TAG(item->next[0]); } return count; } -static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl, const void *key_data, uint32_t key_len, int help_remove) { +static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl, void *key, int help_remove) { node_t *pred = sl->head; node_t *item = NULL; - TRACE("s2", "find_preds: searching for key %p in sl (head is %p)", key_data, pred); + TRACE("s2", "find_preds: searching for key %p in skiplist (head is %p)", key, pred); int d; int start_level = MAX_LEVEL; #if MAX_LEVEL > 2 @@ -139,7 +129,7 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl item = pred->next[level]; if (EXPECT_FALSE(IS_TAGGED(item))) { TRACE("s2", "find_preds: pred %p is marked for removal (item %p); retry", pred, item); - return find_preds(preds, succs, n, sl, key_data, key_len, help_remove); // retry + return find_preds(preds, succs, n, sl, key, help_remove); // retry } while (item != NULL) { node_t *next = item->next[level]; @@ -168,12 +158,17 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl TRACE("s3", "find_preds: now the current item is %p next is %p", item, next); // The thread that completes the unlink should free the memory. - if (level == 0) { node_defer_free(other); } + if (level == 0) { + if (sl->clone_fun != NULL) { + nbd_defer_free((void*)other->key); + } + nbd_defer_free(other); + } } else { - TRACE("s2", "find_preds: lost race to unlink item %p from pred %p", item, pred); - TRACE("s2", "find_preds: pred's link changed to %p", other, 0); + TRACE("s3", "find_preds: lost race to unlink item %p from pred %p", item, pred); + TRACE("s3", "find_preds: pred's link changed to %p", other, 0); if (IS_TAGGED(other)) - return find_preds(preds, succs, n, sl, key_data, key_len, help_remove); // retry + return find_preds(preds, succs, n, sl, key, help_remove); // retry item = other; if (EXPECT_FALSE(item == NULL)) break; @@ -184,21 +179,17 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl if (EXPECT_FALSE(item == NULL)) break; - TRACE("s3", "find_preds: visiting item %p (next is %p)", item, next); + TRACE("s4", "find_preds: visiting item %p (next is %p)", item, next); TRACE("s4", "find_preds: key %p val %p", STRIP_TAG(item->key), item->val); - // A tagged key is an integer, otherwise it is a pointer to a string - if (IS_TAGGED(item->key)) { - d = (STRIP_TAG(item->key) - (uint64_t)key_data); + if (EXPECT_TRUE(sl->cmp_fun == NULL)) { + d = (uint64_t)item->key - (uint64_t)key; } else { - int item_key_len = item->key->len; - int len = (key_len < item_key_len) ? key_len : item_key_len; - d = memcmp(item->key->data, key_data, len); - if (d == 0) { d = item_key_len - key_len; } + d = sl->cmp_fun(item->key, key); } if (d >= 0) { - TRACE("s2", "find_preds: found pred %p item %p", pred, item); + TRACE("s4", "find_preds: found pred %p item %p", pred, item); break; } @@ -217,25 +208,25 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl } } - // fill in empty levels - if (n == -1 && item != NULL) { - for (int level = start_level + 1; level <= item->top_level; ++level) { - preds[level] = sl->head; - } - } - + // fill in empty levels + if (n == -1 && item != NULL) { + for (int level = start_level + 1; level <= item->top_level; ++level) { + preds[level] = sl->head; + } + } + if (d == 0) { TRACE("s2", "find_preds: found matching item %p in skiplist, pred is %p", item, pred); return item; } - TRACE("s2", "find_preds: found proper place for key %p in skiplist, pred is %p. returning null", key_data, pred); + TRACE("s2", "find_preds: found proper place for key %p in skiplist, pred is %p. returning null", key, pred); return NULL; } // Fast find that does not help unlink partially removed nodes and does not return the node's predecessors. -uint64_t sl_lookup (skiplist_t *sl, const void *key_data, uint32_t key_len) { - TRACE("s1", "sl_lookup: searching for key %p in skiplist %p", key_data, sl); - node_t *item = find_preds(NULL, NULL, 0, sl, key_data, key_len, FALSE); +uint64_t sl_lookup (skiplist_t *sl, void *key) { + TRACE("s1", "sl_lookup: searching for key %p in skiplist %p", key, sl); + node_t *item = find_preds(NULL, NULL, 0, sl, key, FALSE); // If we found an matching the return its value. if (item != NULL) { @@ -250,8 +241,8 @@ uint64_t sl_lookup (skiplist_t *sl, const void *key_data, uint32_t key_len) { return DOES_NOT_EXIST; } -uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_t expectation, uint64_t new_val) { - TRACE("s1", "sl_cas: key %p skiplist %p", key_data, sl); +uint64_t sl_cas (skiplist_t *sl, void *key, uint64_t expectation, uint64_t new_val) { + TRACE("s1", "sl_cas: key %p skiplist %p", key, sl); TRACE("s1", "sl_cas: expectation %p new value %p", expectation, new_val); ASSERT((int64_t)new_val > 0); @@ -260,7 +251,7 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_ node_t *new_item = NULL; int n = random_level(); do { - node_t *old_item = find_preds(preds, nexts, n, sl, key_data, key_len, TRUE); + node_t *old_item = find_preds(preds, nexts, n, sl, key, TRUE); if (old_item == NULL) { // There was not an item in the skiplist that matches the key. @@ -273,7 +264,8 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_ // First insert into the bottom level. TRACE("s3", "sl_cas: attempting to insert item between %p and %p", preds[0], nexts[0]); - new_item = node_alloc(n, key_data, key_len, new_val); + void *new_key = (sl->clone_fun == NULL) ? key : sl->clone_fun(key); + new_item = node_alloc(n, new_key, new_val); node_t *pred = preds[0]; node_t *next = new_item->next[0] = nexts[0]; for (int level = 1; level <= new_item->top_level; ++level) { @@ -285,7 +277,10 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_ break; // success } TRACE("s3", "sl_cas: failed to change pred's link: expected %p found %p", next, other); - node_free(new_item); + if (sl->clone_fun != NULL) { + nbd_free(new_key); + } + nbd_free(new_item); continue; } @@ -331,7 +326,7 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_ break; // success } TRACE("s3", "sl_cas: failed to change pred's link: expected %p found %p", next, other); - find_preds(preds, nexts, new_item->top_level, sl, key_data, key_len, TRUE); + find_preds(preds, nexts, new_item->top_level, sl, key, TRUE); pred = preds[level]; next = nexts[level]; @@ -351,62 +346,83 @@ uint64_t sl_cas (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_ return DOES_NOT_EXIST; // success } -uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len) { - TRACE("s1", "sl_remove: removing item with key %p from skiplist %p", key_data, sl); +uint64_t sl_remove (skiplist_t *sl, void *key) { + TRACE("s1", "sl_remove: removing item with key %p from skiplist %p", key, sl); node_t *preds[MAX_LEVEL+1]; - node_t *item = find_preds(preds, NULL, -1, sl, key_data, key_len, TRUE); + node_t *item = find_preds(preds, NULL, -1, sl, key, TRUE); if (item == NULL) { TRACE("s3", "sl_remove: remove failed, an item with a matching key does not exist in the skiplist", 0, 0); return DOES_NOT_EXIST; } - // Mark removed at each level of from the top down. This must be atomic. If multiple threads - // try to remove the same item only one of them should succeed. Marking the bottom level establishes which of - // them succeeds. - for (int level = item->top_level; level >= 0; --level) { - if (EXPECT_FALSE(IS_TAGGED(item->next[level]))) { - TRACE("s3", "sl_remove: %p is already marked for removal by another thread", item, 0); - if (level == 0) - return DOES_NOT_EXIST; - continue; - } + // Mark and unlink at each level of from the top down. If multiple threads try to concurrently remove + // the same item only one of them should succeed. Marking the bottom level establishes which of them succeeds. + for (int level = item->top_level; level > 0; --level) { node_t *next; node_t *old_next = item->next[level]; do { next = old_next; old_next = SYNC_CAS(&item->next[level], next, TAG_VALUE(next)); if (IS_TAGGED(old_next)) { - TRACE("s2", "sl_remove: lost race -- %p is already marked for removal by another thread", item, 0); - if (level == 0) - return DOES_NOT_EXIST; + TRACE("s2", "sl_remove: %p is already marked for removal by another thread at level %llu", item, level); break; } } while (next != old_next); - } - - // This has to be an atomic swap in case another thread is updating the item while we are removing it. - uint64_t val = SYNC_SWAP(&item->val, DOES_NOT_EXIST); - TRACE("s2", "sl_remove: replaced item's val %p with DOES_NOT_EXIT", val, 0); - // Unlink from . If we lose a race to another thread just back off. It is safe to leave the - // item partially unlinked for a later call (or some other thread) to physically unlink. By marking the - // item earlier, we logically removed it. - int level = item->top_level; - while (level >= 0) { node_t *pred = preds[level]; - node_t *next = item->next[level]; - TRACE("s2", "sl_remove: unlink the item by linking its pred %p to it's successor %p", pred, STRIP_TAG(next)); + TRACE("s2", "sl_remove: linking the item's pred %p to the item's successor %p", pred, STRIP_TAG(next)); node_t *other = NULL; if ((other = SYNC_CAS(&pred->next[level], item, STRIP_TAG(next))) != item) { TRACE("s1", "sl_remove: unlink failed; pred's link changed from %p to %p", item, other); - return val; + // If our former predecessor now points past us we know another thread unlinked us. Otherwise, we need + // to search for a new set of preds. + if (other == NULL) + continue; // points past to the end of the list; go on to the next level. + + int d = -1; + if (!IS_TAGGED(other)) { + if (EXPECT_TRUE(sl->cmp_fun == NULL)) { + d = (uint64_t)item->key - (uint64_t)other->key; + } else { + d = sl->cmp_fun(item->key, other->key); + } + } + if (d > 0) { + node_t *temp = find_preds(preds, NULL, level, sl, key, TRUE); + if (temp != item) + return DOES_NOT_EXIST; // Another thread removed the item we were targeting. + level++; // Redo this level. + } } - --level; } - // The thread that completes the unlink should free the memory. - TRACE("s1", "sl_remove: successfully unlinked item %p from the skiplist", item, 0); - node_defer_free(item); + node_t *next; + node_t *old_next = item->next[0]; + do { + next = old_next; + old_next = SYNC_CAS(&item->next[0], next, TAG_VALUE(next)); + if (IS_TAGGED(old_next)) { + TRACE("s2", "sl_remove: %p is already marked for removal by another thread at level 0", item, 0); + return DOES_NOT_EXIST; + } + } while (next != old_next); + TRACE("s1", "sl_remove: marked item %p removed at level 0", item, 0); + + // Atomically swap out the item's value in case another thread is updating the item while we are + // removing it. This establishes which one occurs first, the update or the remove. + uint64_t val = SYNC_SWAP(&item->val, DOES_NOT_EXIST); + TRACE("s2", "sl_remove: replaced item %p's value with DOES_NOT_EXIT", item, 0); + + node_t *pred = preds[0]; + TRACE("s2", "sl_remove: linking the item's pred %p to the item's successor %p", pred, STRIP_TAG(next)); + if (SYNC_CAS(&pred->next[0], item, STRIP_TAG(next))) { + TRACE("s2", "sl_remove: unlinked item %p from the skiplist at level 0", item, 0); + // The thread that completes the unlink should free the memory. + if (sl->clone_fun != NULL) { + nbd_defer_free(item->key); + } + nbd_defer_free(item); + } return val; } @@ -416,29 +432,29 @@ void sl_print (skiplist_t *sl) { if (item->next[level] == NULL) continue; printf("(%d) ", level); + int i = 0; while (item) { node_t *next = item->next[level]; printf("%s%p ", IS_TAGGED(next) ? "*" : "", item); item = (node_t *)STRIP_TAG(next); + if (i++ > 30) { + printf("..."); + break; + } } printf("\n"); fflush(stdout); } - printf("\n"); node_t *item = sl->head; + int i = 0; while (item) { int is_marked = IS_TAGGED(item->next[0]); - - if (IS_TAGGED(item->key)) { - printf("%s%p:%llx ", is_marked ? "*" : "", item, STRIP_TAG(item->key)); - } else { - printf("%s%p:%s ", is_marked ? "*" : "", item, (char *)item->key->data); - } + printf("%s%p:%p ", is_marked ? "*" : "", item, item->key); if (item != sl->head) { printf("[%d]", item->top_level); } else { - printf("[*]"); + printf("[HEAD]"); } for (int level = 1; level <= item->top_level; ++level) { node_t *next = (node_t *)STRIP_TAG(item->next[level]); @@ -450,5 +466,9 @@ void sl_print (skiplist_t *sl) { printf("\n"); fflush(stdout); item = (node_t *)STRIP_TAG(item->next[0]); + if (i++ > 30) { + printf("...\n"); + break; + } } } diff --git a/runtime/nstring.c b/runtime/nstring.c new file mode 100644 index 0000000..a3fdd1f --- /dev/null +++ b/runtime/nstring.c @@ -0,0 +1,25 @@ +#include "common.h" +#include "nstring.h" +#include "murmur.h" +#include "mem.h" + +nstring_t *ns_alloc (uint32_t len) { + nstring_t *ns = nbd_malloc(sizeof(nstring_t) + len); + ns->len = len; + return ns; +} + +int ns_cmp (const nstring_t *ns1, const nstring_t *ns2) { + int d = memcmp(ns1->data, ns2->data, (ns1->len < ns2->len) ? ns1->len : ns1->len); + return (d == 0) ? ns1->len - ns2->len : d; +} + +uint32_t ns_hash (const nstring_t *ns) { + return murmur32(ns->data, ns->len); +} + +nstring_t *ns_dup (const nstring_t *ns1) { + nstring_t *ns2 = ns_alloc(ns1->len); + memcpy(ns2->data, ns1->data, ns1->len); + return ns2; +} diff --git a/test/CuTest.c b/test/CuTest.c index 2bcce60..6eccb94 100644 --- a/test/CuTest.c +++ b/test/CuTest.c @@ -140,10 +140,9 @@ static void CuFailInternal(CuTest* tc, const char* file, int line, CuString* str tc->failed = 1; tc->message = string->buffer; -#ifdef ENABLE_TRACE + extern void lwt_halt(void); extern void lwt_dump(const char *); lwt_dump(tc->name); -#endif if (tc->jumpBuf != 0) longjmp(*(tc->jumpBuf), 0); } diff --git a/test/map_test1.c b/test/map_test1.c index 30d7ce0..34d4ba7 100644 --- a/test/map_test1.c +++ b/test/map_test1.c @@ -4,11 +4,14 @@ #include #include "common.h" +#include "nstring.h" #include "runtime.h" #include "map.h" #define NUM_ITERATIONS 10000000 +//#define TEST_STRING_KEYS + static volatile int wait_; static long num_threads_; static map_t *map_; @@ -19,22 +22,26 @@ void *worker (void *arg) { SYNC_ADD(&wait_, -1); do {} while (wait_); +#ifdef TEST_STRING_KEYS + nstring_t *key_str = ns_alloc(10); +#endif + for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) { unsigned r = nbd_rand(); uint64_t key = r & 0xF; -#if 1 - char key_str[10]; - sprintf(key_str, "%llX", key); +#ifdef TEST_STRING_KEYS + key_str->len = sprintf(key_str->data, "%llX", key) + 1; + assert(key_str->len <= 10); if (r & (1 << 8)) { - map_set(map_, key_str, strlen(key_str) + 1, 1); + map_set(map_, key_str, 1); } else { - map_remove(map_, key_str, strlen(key_str) + 1); + map_remove(map_, key_str); } #else if (r & (1 << 8)) { - map_set(map_, (void *)key, -1, 1); + map_set(map_, (void *)(key + 1), 1); } else { - map_remove(map_, (void *)key, -1); + map_remove(map_, (void *)(key + 1)); } #endif @@ -46,7 +53,7 @@ void *worker (void *arg) { int main (int argc, char **argv) { nbd_init(); - //lwt_set_trace_level("l3"); + lwt_set_trace_level("l3"); char* program_name = argv[0]; pthread_t thread[MAX_NUM_THREADS]; @@ -77,7 +84,11 @@ int main (int argc, char **argv) { map_type_t map_types[] = { MAP_TYPE_LIST, MAP_TYPE_SKIPLIST, MAP_TYPE_HASHTABLE }; for (int i = 0; i < sizeof(map_types)/sizeof(*map_types); ++i) { - map_ = map_alloc(map_types[i]); +#ifdef TEST_STRING_KEYS + map_ = map_alloc(map_types[i], (cmp_fun_t)ns_cmp, (hash_fun_t)ns_hash, (clone_fun_t)ns_dup); +#else + map_ = map_alloc(map_types[i], NULL, NULL, NULL); +#endif struct timeval tv1, tv2; gettimeofday(&tv1, NULL); @@ -96,7 +107,7 @@ int main (int argc, char **argv) { gettimeofday(&tv2, NULL); int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000; map_print(map_); - printf("Th:%ld Time:%dms\n", num_threads_, ms); + printf("Th:%ld Time:%dms\n\n", num_threads_, ms); fflush(stdout); } diff --git a/test/map_test2.c b/test/map_test2.c index b321a68..3e13a68 100644 --- a/test/map_test2.c +++ b/test/map_test2.c @@ -4,6 +4,7 @@ */ #include #include +#include #include "CuTest.h" @@ -18,61 +19,61 @@ typedef struct worker_data { int id; CuTest *tc; map_t *map; - int *wait; + volatile int *wait; } worker_data_t; static map_type_t map_type_; // Test some basic stuff; add a few keys, remove a few keys -void basic_test (CuTest* tc) { +void simple (CuTest* tc) { - map_t *map = map_alloc(map_type_); + map_t *map = map_alloc(map_type_, NULL, NULL, NULL); ASSERT_EQUAL( 0, map_count(map) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_add(map,"a",2,10) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_add(map, (void *)'a',10) ); ASSERT_EQUAL( 1, map_count(map) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_add(map,"b",2,20) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_add(map, (void *)'b',20) ); ASSERT_EQUAL( 2, map_count(map) ); - ASSERT_EQUAL( 20, map_get(map,"b",2) ); - ASSERT_EQUAL( 10, map_set(map,"a",2,11) ); - ASSERT_EQUAL( 20, map_set(map,"b",2,21) ); + ASSERT_EQUAL( 20, map_get(map, (void *)'b') ); + ASSERT_EQUAL( 10, map_set(map, (void *)'a',11) ); + ASSERT_EQUAL( 20, map_set(map, (void *)'b',21) ); ASSERT_EQUAL( 2, map_count(map) ); - ASSERT_EQUAL( 21, map_add(map,"b",2,22) ); - ASSERT_EQUAL( 11, map_remove(map,"a",2) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map,"a",2) ); + ASSERT_EQUAL( 21, map_add(map, (void *)'b',22) ); + ASSERT_EQUAL( 11, map_remove(map, (void *)'a') ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'a') ); ASSERT_EQUAL( 1, map_count(map) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(map,"a",2) ); - ASSERT_EQUAL( 21, map_remove(map,"b",2) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(map, (void *)'a') ); + ASSERT_EQUAL( 21, map_remove(map, (void *)'b') ); ASSERT_EQUAL( 0, map_count(map) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(map,"b",2) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(map,"c",2) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(map, (void *)'b') ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_remove(map, (void *)'c') ); ASSERT_EQUAL( 0, map_count(map) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_add(map,"d",2,40) ); - ASSERT_EQUAL( 40, map_get(map,"d",2) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_add(map, (void *)'d',40) ); + ASSERT_EQUAL( 40, map_get(map, (void *)'d') ); ASSERT_EQUAL( 1, map_count(map) ); - ASSERT_EQUAL( 40, map_remove(map,"d",2) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map,"d",2) ); + ASSERT_EQUAL( 40, map_remove(map, (void *)'d') ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'d') ); ASSERT_EQUAL( 0, map_count(map) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map,"d",2,10) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map,"d",2) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_set(map,"d",2,40) ); - ASSERT_EQUAL( 40, map_replace(map,"d",2,41) ); - ASSERT_EQUAL( 41, map_get(map,"d",2) ); - ASSERT_EQUAL( 41, map_remove(map,"d",2) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map,"d",2) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, (void *)'d',10) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'d') ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_set(map, (void *)'d',40) ); + ASSERT_EQUAL( 40, map_replace(map, (void *)'d',41) ); + ASSERT_EQUAL( 41, map_get(map, (void *)'d') ); + ASSERT_EQUAL( 41, map_remove(map, (void *)'d') ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'d') ); ASSERT_EQUAL( 0, map_count(map) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map,"b",2,20) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map,"b",2) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_replace(map, (void *)'b',20) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'b') ); // In the end, all entries should be removed - ASSERT_EQUAL( DOES_NOT_EXIST, map_set(map,"b",2,20) ); - ASSERT_EQUAL( 20, map_replace(map,"b",2,21) ); - ASSERT_EQUAL( 21, map_get(map,"b",2) ); - ASSERT_EQUAL( 21, map_remove(map,"b",2) ); - ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map,"b",2) ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_set(map, (void *)'b',20) ); + ASSERT_EQUAL( 20, map_replace(map, (void *)'b',21) ); + ASSERT_EQUAL( 21, map_get(map, (void *)'b') ); + ASSERT_EQUAL( 21, map_remove(map, (void *)'b') ); + ASSERT_EQUAL( DOES_NOT_EXIST, map_get(map, (void *)'b') ); ASSERT_EQUAL( 0, map_count(map) ); map_free(map); @@ -81,29 +82,25 @@ void basic_test (CuTest* tc) { rcu_update(); } -void *simple_worker (void *arg) { +void *add_remove_worker (void *arg) { worker_data_t *wd = (worker_data_t *)arg; map_t *map = wd->map; CuTest* tc = wd->tc; uint64_t d = wd->id; - int iters = map_type_ == MAP_TYPE_LIST ? 100 : 1000000; + int iters = (map_type_ == MAP_TYPE_LIST) ? 5000 : 500000; SYNC_ADD(wd->wait, -1); - do { } while (*((volatile worker_data_t *)wd)->wait); // wait for all workers to be ready + do { } while (*wd->wait); // wait for all workers to be ready for (int j = 0; j < 10; ++j) { - for (int i = d; i < iters; i+=2) { - char key[10]; - sprintf(key, "k%u", i); + for (uint64_t i = d+1; i < iters; i+=2) { TRACE("t0", "test map_add() iteration (%llu, %llu)", j, i); - CuAssertIntEquals_Msg(tc, key, DOES_NOT_EXIST, map_add(map, key, strlen(key)+1, d+1) ); + CuAssertIntEquals_Msg(tc, (void *)i, DOES_NOT_EXIST, map_add(map, (void *)i, d+1) ); rcu_update(); } - for (int i = d; i < iters; i+=2) { - char key[10]; - sprintf(key, "k%u", i); + for (uint64_t i = d+1; i < iters; i+=2) { TRACE("t0", "test map_remove() iteration (%llu, %llu)", j, i); - CuAssertIntEquals_Msg(tc, key, d+1, map_remove(map, key, strlen(key)+1) ); + CuAssertIntEquals_Msg(tc, (void *)i, d+1, map_remove(map, (void *)i) ); rcu_update(); } } @@ -111,12 +108,15 @@ void *simple_worker (void *arg) { } // Do some simple concurrent testing -void simple_add_remove (CuTest* tc) { +void add_remove (CuTest* tc) { pthread_t thread[2]; worker_data_t wd[2]; - int wait = 2; - map_t *map = map_alloc(map_type_); + volatile int wait = 2; + map_t *map = map_alloc(map_type_, NULL, NULL, NULL); + + struct timeval tv1, tv2; + gettimeofday(&tv1, NULL); // In 2 threads, add & remove even & odd elements concurrently int i; @@ -125,13 +125,20 @@ void simple_add_remove (CuTest* tc) { wd[i].tc = tc; wd[i].map = map; wd[i].wait = &wait; - int rc = nbd_thread_create(thread + i, i, simple_worker, wd + i); + int rc = nbd_thread_create(thread + i, i, add_remove_worker, wd + i); if (rc != 0) { perror("nbd_thread_create"); return; } } + for (i = 0; i < 2; ++i) { pthread_join(thread[i], NULL); } + gettimeofday(&tv2, NULL); + int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000; + map_print(map); + printf("Th:%d Time:%dms\n", 2, ms); + fflush(stdout); + // In the end, all members should be removed ASSERT_EQUAL( 0, map_count(map) ); @@ -139,7 +146,6 @@ void simple_add_remove (CuTest* tc) { map_free(map); } - void *inserter_worker (void *arg) { //pthread_t thread[NUM_THREADS]; @@ -154,7 +160,7 @@ void concurrent_insert (CuTest* tc) { int main (void) { nbd_init(); - //lwt_set_trace_level("h0"); + lwt_set_trace_level("h3"); map_type_t map_types[] = { MAP_TYPE_LIST, MAP_TYPE_SKIPLIST, MAP_TYPE_HASHTABLE }; for (int i = 0; i < sizeof(map_types)/sizeof(*map_types); ++i) { @@ -164,8 +170,8 @@ int main (void) { CuString *output = CuStringNew(); CuSuite* suite = CuSuiteNew(); - SUITE_ADD_TEST(suite, basic_test); - SUITE_ADD_TEST(suite, simple_add_remove); + SUITE_ADD_TEST(suite, simple); + SUITE_ADD_TEST(suite, add_remove); CuSuiteRun(suite); CuSuiteDetails(suite, output); diff --git a/test/txn_test.c b/test/txn_test.c index 6e9044f..dee5151 100644 --- a/test/txn_test.c +++ b/test/txn_test.c @@ -8,15 +8,15 @@ #define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y) void test1 (CuTest* tc) { - map_t *map = map_alloc(MAP_TYPE_LIST); + map_t *map = map_alloc(MAP_TYPE_LIST, NULL, NULL, NULL); txn_t *t1 = txn_begin(TXN_READ_WRITE, TXN_REPEATABLE_READ, map); txn_t *t2 = txn_begin(TXN_READ_WRITE, TXN_REPEATABLE_READ, map); - tm_set(t1, "abc", 4, 2); - tm_set(t1, "abc", 4, 3); - ASSERT_EQUAL( DOES_NOT_EXIST, tm_get(t2, "abc", 4) ); - tm_set(t2, "abc", 4, 4); - ASSERT_EQUAL( 3, tm_get(t1, "abc", 4) ); - ASSERT_EQUAL( 4, tm_get(t2, "abc", 4) ); + tm_set(t1, "abc", 2); + tm_set(t1, "abc", 3); + ASSERT_EQUAL( DOES_NOT_EXIST, tm_get(t2, "abc") ); + tm_set(t2, "abc", 4); + ASSERT_EQUAL( 3, tm_get(t1, "abc") ); + ASSERT_EQUAL( 4, tm_get(t2, "abc") ); ASSERT_EQUAL( TXN_VALIDATED, txn_commit(t2)); ASSERT_EQUAL( TXN_ABORTED, txn_commit(t1)); } diff --git a/todo b/todo index e052f1c..9ed547f 100644 --- a/todo +++ b/todo @@ -11,3 +11,6 @@ + optimize integer keys - ht_print() - iterators +- characterize performance of data structures +- experiment with the performance impact of not passing the hash between functions +- experiment with embedding key is the list/skiplist nodes diff --git a/txn/txn.c b/txn/txn.c index 5275882..3edf666 100644 --- a/txn/txn.c +++ b/txn/txn.c @@ -21,7 +21,7 @@ struct update_rec { }; typedef struct write_rec { - const char *key; + void *key; update_rec_t *rec; } write_rec_t; @@ -44,9 +44,9 @@ static uint64_t version_ = 1; // Validate the updates for . Validation fails for a key we have written to if there is a // write committed newer than our read version. -static txn_state_e tm_validate_key (txn_t *txn, const char *key, uint32_t key_len) { +static txn_state_e tm_validate_key (txn_t *txn, void *key) { - update_rec_t *update = (update_rec_t *) map_get(txn->map, key, key_len); + update_rec_t *update = (update_rec_t *) map_get(txn->map, key); for (; update != NULL; update = update->prev) { uint64_t writer_version = update->version; if (writer_version <= txn->rv) @@ -102,7 +102,7 @@ static txn_state_e txn_validate (txn_t *txn) { } for (i = 0; i < txn->writes_count; ++i) { - txn_state_e s = tm_validate_key(txn, txn->writes[i].key, strlen(txn->writes[i].key)); + txn_state_e s = tm_validate_key(txn, txn->writes[i].key); if (s == TXN_ABORTED) { txn->state = TXN_ABORTED; break; @@ -179,11 +179,11 @@ txn_state_e txn_commit (txn_t *txn) { } // Get most recent committed version prior to our read version. -uint64_t tm_get (txn_t *txn, const char *key, uint32_t key_len) { +uint64_t tm_get (txn_t *txn, void *key) { // Iterate through update records associated with to find the latest committed version. // We can use the first matching version. Older updates always come later in the list. - update_rec_t *update = (update_rec_t *) map_get(txn->map, key, key_len); + update_rec_t *update = (update_rec_t *) map_get(txn->map, key); for (; update != NULL; update = update->prev) { uint64_t writer_version = update->version; if (writer_version < txn->rv) @@ -213,7 +213,7 @@ uint64_t tm_get (txn_t *txn, const char *key, uint32_t key_len) { return DOES_NOT_EXIST; } -void tm_set (txn_t *txn, const char *key, uint32_t key_len, uint64_t value) { +void tm_set (txn_t *txn, void *key, uint64_t value) { // create a new update record update_rec_t *update = alloc_update_rec(); @@ -224,9 +224,9 @@ void tm_set (txn_t *txn, const char *key, uint32_t key_len, uint64_t value) { // push the new update record onto 's update list uint64_t update_prev; do { - update->prev = (update_rec_t *) map_get(txn->map, key, key_len); + update->prev = (update_rec_t *) map_get(txn->map, key); update_prev = (uint64_t)update->prev; - } while (map_cas(txn->map, key, key_len, update_prev, (uint64_t)update) != update_prev); + } while (map_cas(txn->map, key, update_prev, (uint64_t)update) != update_prev); // add to the write set for commit-time validation if (txn->writes_count == txn->writes_size) {