refactor header files

fix regression in ht_remove()

diff --git a/include/hashtable.h b/include/hashtable.h
new file mode 100644 (file)
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 (file)
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 42a5a1d2e8c2ebf1d2d196dc14506259e9aa466c..357b66895f3b16ace6ae137226ab2599818e938a 100644 (file)
--- 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 (file)
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 56144e93086d0a15ee96c4e909b80e7a7ac6e55f..635a3692d20fdb8c58bffbcf9715c27918167f7a 100644 (file)
--- 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 da5adae11b6e42da65c07c7a6e58399660a0b066..3471af4db05410e5e6775f9e0d328be96587ecd6 100644 (file)
--- 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 <expected> with the existing value associated with <key>. If the values match then 
-// replace the existing value with <new>. If <new> is TOMBSTONE, delete the value associated with 
+// replace the existing value with <new>. If <new> is DOES_NOT_EXIST, delete the value associated with 
 // the key by replacing it with a TOMBSTONE.
 //
 // Return the previous value associated with <key>, or DOES_NOT_EXIST if <key> 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, <key> is already deleted.
-        if (new == TOMBSTONE)
+        if (new == DOES_NOT_EXIST)
             return DOES_NOT_EXIST;
 
         // Allocate <new_key>.
@@ -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 f7a9cd43cbaa2da9049be46bc791d11f81e92cda..e900f0203229c8d52618b6d2fa1c499b096d0c53 100644 (file)
--- 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 <item> removed. This must be atomic. If multiple threads try to remove the same item
-    // only one of them should succeed.
+    // Mark <item> 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 f7de2ac9b62c5442d47bfd6ceb2de76ef0380aa8..c422ec1c130e964b34900d08281b8e54d3d7be29 100644 (file)
--- 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 ad05dd190f25bbae2e7df828d87fe340e3f53925..a0e9c60769a2ce5847471fbbaf9fc6894c8828db 100644 (file)
--- a/map/skiplist.c
+++ b/map/skiplist.c
@@ -20,13 +20,11 @@
 #include <stdio.h>
 #include <string.h>
 
-#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 7c35b4592e9959acda072443a25135a13894032b..27226d6bb2a52dbe0396869f255ca36ba22e885b 100644 (file)
--- 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 92a269ec4f81fdd699327e096aad2ed0e2048a60..897fe8e295d6619539be6335dbb77da09ecff03b 100644 (file)
--- 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 018f19e3657f5406fc6903d7925d4fb251d447b7..a8684da41b5140ccb25f0b362631a7f11f82c27a 100644 (file)
--- 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 3edf666983962076dfb7110f3b3975241055ff63..e05d332386fe8284727fc0ced57c107d26a59cf2 100644 (file)
--- 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 <key>. 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;
 }