From d26bac75802a324ed98c8d3d88cfb9eb87b3b35a Mon Sep 17 00:00:00 2001 From: jdybnis Date: Fri, 5 Dec 2008 02:33:14 +0000 Subject: [PATCH 1/1] refactor header files fix regression in ht_remove() --- include/hashtable.h | 16 ++++++++++++++++ include/list.h | 19 +++++++++++++++++++ include/map.h | 2 -- include/skiplist.h | 19 +++++++++++++++++++ include/txn.h | 9 ++++----- map/hashtable.c | 17 +++++++++-------- map/list.c | 7 ++++--- map/mlocal.h | 29 ----------------------------- map/skiplist.c | 6 ++---- test/map_test1.c | 3 +++ test/map_test2.c | 3 +++ test/txn_test.c | 8 +++++--- txn/txn.c | 42 ++++++++++++++++++++++++++++++++++-------- 13 files changed, 118 insertions(+), 62 deletions(-) create mode 100644 include/hashtable.h create mode 100644 include/list.h create mode 100644 include/skiplist.h diff --git a/include/hashtable.h b/include/hashtable.h new file mode 100644 index 0000000..9cffb7f --- /dev/null +++ b/include/hashtable.h @@ -0,0 +1,16 @@ +#ifndef HASHTABLE_H +#define HASHTABLE_H + +#include "datatype.h" + +typedef struct ht hashtable_t; + +hashtable_t *ht_alloc (const datatype_t *key_type); +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); + +#endif//HASHTABLE_H diff --git a/include/list.h b/include/list.h new file mode 100644 index 0000000..7eeda46 --- /dev/null +++ b/include/list.h @@ -0,0 +1,19 @@ +#ifndef LIST_H +#define LIST_H + +#include "datatype.h" +#include "map.h" + +typedef struct ll list_t; + +extern map_type_t MAP_TYPE_LIST; + +list_t * ll_alloc (const datatype_t *key_type); +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); + +#endif//LIST_H diff --git a/include/map.h b/include/map.h index 42a5a1d..357b668 100644 --- a/include/map.h +++ b/include/map.h @@ -8,8 +8,6 @@ typedef struct map map_t; typedef const struct map_impl *map_type_t; 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, const datatype_t *key_type); uint64_t map_get (map_t *map, void *key); diff --git a/include/skiplist.h b/include/skiplist.h new file mode 100644 index 0000000..11824f8 --- /dev/null +++ b/include/skiplist.h @@ -0,0 +1,19 @@ +#ifndef SKIPLIST_H +#define SKIPLIST_H + +#include "datatype.h" +#include "map.h" + +typedef struct sl skiplist_t; + +extern map_type_t MAP_TYPE_SKIPLIST; + +skiplist_t *sl_alloc (const datatype_t *key_type); +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); + +#endif//SKIPLIST_H diff --git a/include/txn.h b/include/txn.h index 56144e9..635a369 100644 --- a/include/txn.h +++ b/include/txn.h @@ -7,17 +7,16 @@ #include "map.h" -typedef enum { TXN_READ_WRITE, TXN_READ_ONLY, TXN_BLIND_WRITE } txn_access_e; -typedef enum { TXN_REPEATABLE_READ, TXN_READ_COMMITTED, TXN_DIRTY_READ } txn_isolation_e; +typedef enum { TXN_REPEATABLE_READ, TXN_READ_COMMITTED, TXN_READ_ONLY } txn_type_e; typedef enum { TXN_RUNNING, TXN_VALIDATING, TXN_VALIDATED, TXN_ABORTED } txn_state_e; typedef struct txn txn_t; -txn_t * txn_begin (txn_access_e access, txn_isolation_e isolation, map_t *map); +txn_t * txn_begin (txn_type_e type, map_t *map); void txn_abort (txn_t *txn); txn_state_e txn_commit (txn_t *txn); -uint64_t tm_get (txn_t *txn, void *key); -void tm_set (txn_t *txn, void *key, 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/map/hashtable.c b/map/hashtable.c index da5adae..3471af4 100644 --- a/map/hashtable.c +++ b/map/hashtable.c @@ -17,6 +17,7 @@ #include "murmur.h" #include "mem.h" #include "mlocal.h" +#include "hashtable.h" #define GET_PTR(x) ((void *)((x) & MASK(48))) // low-order 48 bits is a pointer to a nstring_t @@ -284,7 +285,7 @@ static int hti_copy_entry (hti_t *ht1, volatile entry_t *ht1_ent, uint32_t key_h } // Compare with the existing value associated with . If the values match then -// replace the existing value with . If is TOMBSTONE, delete the value associated with +// replace the existing value with . If is DOES_NOT_EXIST, delete the value associated with // the key by replacing it with a TOMBSTONE. // // Return the previous value associated with , or DOES_NOT_EXIST if is not in the table @@ -301,7 +302,7 @@ static uint64_t hti_cas (hti_t *hti, void *key, uint32_t key_hash, uint64_t expe 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(!IS_TAGGED(new)); assert(key); int is_empty; @@ -322,7 +323,7 @@ static uint64_t hti_cas (hti_t *hti, void *key, uint32_t key_hash, uint64_t expe return DOES_NOT_EXIST; // No need to do anything, is already deleted. - if (new == TOMBSTONE) + if (new == DOES_NOT_EXIST) return DOES_NOT_EXIST; // Allocate . @@ -377,22 +378,22 @@ static uint64_t hti_cas (hti_t *hti, void *key, uint32_t key_hash, uint64_t expe } // No need to update if value is unchanged. - if ((new == TOMBSTONE && !old_existed) || ent_val == new) { + if ((new == DOES_NOT_EXIST && !old_existed) || ent_val == new) { TRACE("h1", "hti_cas: old value and new value were the same", 0, 0); return ent_val; } // CAS the value into the entry. Retry if it fails. - uint64_t v = SYNC_CAS(&ent->val, ent_val, new); + uint64_t v = SYNC_CAS(&ent->val, ent_val, new == DOES_NOT_EXIST ? TOMBSTONE : 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. - if (old_existed && new == TOMBSTONE) { + if (old_existed && new == DOES_NOT_EXIST) { SYNC_ADD(&hti->count, -1); - } else if (!old_existed && new != TOMBSTONE) { + } else if (!old_existed && new != DOES_NOT_EXIST) { SYNC_ADD(&hti->count, 1); } @@ -512,7 +513,7 @@ uint64_t ht_remove (hashtable_t *ht, void *key) { uint64_t val; uint32_t key_hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash(key); do { - val = hti_cas(hti, key, key_hash, CAS_EXPECT_WHATEVER, TOMBSTONE); + val = hti_cas(hti, key, key_hash, CAS_EXPECT_WHATEVER, DOES_NOT_EXIST); if (val != COPIED_VALUE) return val == TOMBSTONE ? DOES_NOT_EXIST : val; assert(hti->next); diff --git a/map/list.c b/map/list.c index f7a9cd4..e900f02 100644 --- a/map/list.c +++ b/map/list.c @@ -11,6 +11,7 @@ #include "common.h" #include "mlocal.h" +#include "list.h" #include "mem.h" typedef struct node { @@ -252,8 +253,7 @@ uint64_t ll_remove (list_t *ll, void *key) { return DOES_NOT_EXIST; } - // Mark removed. This must be atomic. If multiple threads try to remove the same item - // only one of them should succeed. + // Mark removed. If multiple threads try to remove the same item only one of them should succeed. node_t *next; node_t *old_next = item->next; do { @@ -267,7 +267,8 @@ uint64_t ll_remove (list_t *ll, void *key) { TRACE("l2", "ll_remove: logically removed item %p", item, 0); ASSERT(IS_TAGGED(item->next)); - // This has to be an atomic swap in case another thread is updating the item while we are removing it. + // Atomically swap out the item's value in case another thread is updating the item while we are + // removing it. This establishes which operation occurs first logically, the update or the remove. uint64_t val = SYNC_SWAP(&item->val, DOES_NOT_EXIST); TRACE("l2", "ll_remove: replaced item's val %p with DOES_NOT_EXIT", val, 0); diff --git a/map/mlocal.h b/map/mlocal.h index f7de2ac..c422ec1 100644 --- a/map/mlocal.h +++ b/map/mlocal.h @@ -25,33 +25,4 @@ typedef struct map_impl { map_free_t free_; } map_impl_t; -typedef struct ht hashtable_t; -typedef struct sl skiplist_t; -typedef struct ll list_t; - -hashtable_t * ht_alloc (const datatype_t *key_type); -skiplist_t * sl_alloc (const datatype_t *key_type); -list_t * ll_alloc (const datatype_t *key_type); - -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, 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, 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); - #endif//MLOCAL_H diff --git a/map/skiplist.c b/map/skiplist.c index ad05dd1..a0e9c60 100644 --- a/map/skiplist.c +++ b/map/skiplist.c @@ -20,13 +20,11 @@ #include #include -#define ENABLE_TRACE - #include "common.h" #include "runtime.h" #include "mlocal.h" +#include "skiplist.h" #include "mem.h" -#include "tls.h" // Setting MAX_LEVEL to 0 essentially makes this data structure the Harris-Michael lock-free list (in list.c). #define MAX_LEVEL 31 @@ -409,7 +407,7 @@ uint64_t sl_remove (skiplist_t *sl, void *key) { 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. + // removing it. This establishes which operation occurs first logically, 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); diff --git a/test/map_test1.c b/test/map_test1.c index 7c35b45..27226d6 100644 --- a/test/map_test1.c +++ b/test/map_test1.c @@ -7,6 +7,9 @@ #include "nstring.h" #include "runtime.h" #include "map.h" +#include "list.h" +#include "skiplist.h" +#include "hashtable.h" #define NUM_ITERATIONS 10000000 diff --git a/test/map_test2.c b/test/map_test2.c index 92a269e..897fe8e 100644 --- a/test/map_test2.c +++ b/test/map_test2.c @@ -12,6 +12,9 @@ #include "runtime.h" #include "nstring.h" #include "map.h" +#include "list.h" +#include "skiplist.h" +#include "hashtable.h" #include "lwt.h" #define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y) diff --git a/test/txn_test.c b/test/txn_test.c index 018f19e..a8684da 100644 --- a/test/txn_test.c +++ b/test/txn_test.c @@ -4,13 +4,15 @@ #include "common.h" #include "runtime.h" #include "txn.h" +#include "map.h" +#include "hashtable.h" #define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y) void test1 (CuTest* tc) { - map_t *map = map_alloc(MAP_TYPE_LIST, 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); + map_t *map = map_alloc(MAP_TYPE_HASHTABLE, NULL); + txn_t *t1 = txn_begin(TXN_REPEATABLE_READ, map); + txn_t *t2 = txn_begin(TXN_REPEATABLE_READ, map); tm_set(t1, "abc", 2); tm_set(t1, "abc", 3); ASSERT_EQUAL( DOES_NOT_EXIST, tm_get(t2, "abc") ); diff --git a/txn/txn.c b/txn/txn.c index 3edf666..e05d332 100644 --- a/txn/txn.c +++ b/txn/txn.c @@ -5,6 +5,7 @@ #include "common.h" #include "txn.h" #include "mem.h" +#include "skiplist.h" #define UNDETERMINED_VERSION 0 #define INITIAL_WRITES_SIZE 4 @@ -33,14 +34,19 @@ struct txn { uint32_t writes_size; uint32_t writes_count; uint32_t writes_scan; - txn_access_e access; - txn_isolation_e isolation; + txn_type_e type; txn_state_e state; }; +static uint64_t version_ = 1; + static txn_state_e txn_validate (txn_t *txn); -static uint64_t version_ = 1; +static map_t *active_ = NULL; + +void txn_init (void) { + active_ = map_alloc(MAP_TYPE_SKIPLIST, NULL); +} // Validate the updates for . Validation fails for a key we have written to if there is a // write committed newer than our read version. @@ -130,19 +136,39 @@ static update_rec_t *alloc_update_rec (void) { return u; } -txn_t *txn_begin (txn_access_e access, txn_isolation_e isolation, map_t *map) { +txn_t *txn_begin (txn_type_e type, map_t *map) { txn_t *txn = (txn_t *)nbd_malloc(sizeof(txn_t)); memset(txn, 0, sizeof(txn_t)); - txn->access = access; - txn->isolation = isolation; - txn->rv = version_; + txn->type = type; txn->wv = UNDETERMINED_VERSION; txn->state = TXN_RUNNING; txn->map = map; - if (isolation != TXN_READ_ONLY) { + if (type != TXN_READ_ONLY) { txn->writes = nbd_malloc(sizeof(*txn->writes) * INITIAL_WRITES_SIZE); txn->writes_size = INITIAL_WRITES_SIZE; } + + // aquire the read version for txn. + do { + txn->rv = version_; + + uint64_t old_count; + uint64_t temp = 0; + do { + old_count = temp; + temp = (uint64_t)map_cas(active_, (void *)txn->rv, old_count, old_count + 1); + } while (temp != old_count); + + if (txn->rv == version_) + break; + + temp = 1; + do { + old_count = temp; + temp = map_cas(active_, (void *)txn->rv, old_count, old_count - 1); + } while (temp != old_count); + } while (1); + return txn; } -- 2.40.0