Some refactoring. WARNING: tests not passing!
authorjdybnis <jdybnis@9ec2166a-aeea-11dd-8830-69e4bb380a4a>
Wed, 12 Nov 2008 08:11:26 +0000 (08:11 +0000)
committerjdybnis <jdybnis@9ec2166a-aeea-11dd-8830-69e4bb380a4a>
Wed, 12 Nov 2008 08:11:26 +0000 (08:11 +0000)
17 files changed:
include/common.h
include/ht.h
include/lwt.h
include/mem.h
include/nbd.h [deleted file]
include/rcu.h [deleted file]
include/runtime.h [new file with mode: 0644]
include/tls.h [deleted file]
makefile
runtime/lwt.c
runtime/mem.c
runtime/rcu.c
runtime/runtime.c
struct/ht.c
struct/ht_test.c
struct/list.c
tags [deleted file]

index aea1f67d33b820fc3315452844f159e121e3ac7b..477462842d8b5ac69bbe97cad61082f532439898 100644 (file)
@@ -11,6 +11,9 @@
 #include <string.h>
 #include <sys/types.h>
 
+#define malloc "DON'T USE MALLOC" // use nbd_malloc() instead
+#define free   "DON'T USE FREE"   // use nbd_free() instead
+
 #define MAX_NUM_THREADS 4 // make this whatever you want, but make it a power of 2
 
 #define CACHE_LINE_SIZE 64
 #define MASK(n)     ((1LL << (n)) - 1)
 
 #define TAG          (1LL << 63)
-#define IS_TAGGED(v) ((int64_t)(v) < 0)
-#define TAG_VALUE(v) ((int64_t)(v) |  TAG)
-#define STRIP_TAG(v) ((int64_t)(v) & ~TAG)
+#define IS_TAGGED(v) ((uint64_t)(v) < 0)
+#define TAG_VALUE(v) ((uint64_t)(v) |  TAG)
+#define STRIP_TAG(v) ((uint64_t)(v) & ~TAG)
 
 #define TRUE  1
 #define FALSE 0
 
-typedef          long long  int64_t;
 typedef unsigned long long uint64_t;
 typedef unsigned int       uint32_t;
+typedef unsigned char      uint8_t;
 
 #include "lwt.h"
 #endif //COMMON_H
index b396ce86170b619656d32957c185d301badc8e56..965986e781b60f8adc76260c416b7de61ad3a8a9 100644 (file)
@@ -17,9 +17,9 @@ typedef struct hash_table_i *hash_table_t;
 
 hash_table_t *ht_alloc (void);
 void ht_free (hash_table_t *ht);
-int64_t ht_get (hash_table_t *ht, const char *key, uint32_t len);
-int64_t ht_compare_and_set (hash_table_t *ht, const char *key, uint32_t key_len, int64_t expected_val, int64_t val);
-int64_t ht_remove (hash_table_t *ht, const char *key, uint32_t len);
+uint64_t ht_get (hash_table_t *ht, const char *key, uint32_t len);
+uint64_t ht_compare_and_set (hash_table_t *ht, const char *key, uint32_t key_len, uint64_t expected_val, uint64_t val);
+uint64_t ht_remove (hash_table_t *ht, const char *key, uint32_t len);
 uint64_t ht_count (hash_table_t *ht);
 
 #endif//HT_H
index 789c66704c98f3c6602310d4300c284dd44f5858..db862921e2a27881d2c2bc1322dc4648e8aa4a56 100644 (file)
@@ -6,7 +6,6 @@
  */ 
 #ifndef LWT_H
 #define LWT_H
-#include "tls.h"
 
 #ifndef ENABLE_TRACE
 #define TRACE(...) do { } while (0)
 #define TRACE(flag, format, v1, v2) lwt_trace(flag, format, (size_t)(v1), (size_t)(v2))
 #endif
 
-#define LWT_BUFFER_SCALE 16
-#define LWT_BUFFER_SIZE (1 << LWT_BUFFER_SCALE)
-#define LWT_BUFFER_MASK (LWT_BUFFER_SIZE - 1)
-
-typedef struct lwt_record {
-    uint64_t timestamp;
-    const char *format;
-    size_t value1;
-    size_t value2;
-} lwt_record_t;
-
-typedef struct lwt_buffer {
-    uint32_t head;
-    lwt_record_t x[0];
-} lwt_buffer_t;
-
-void lwt_init (void);
-void lwt_thread_init (int thread_id);
-
+// Dump trace records to <file_name>. The file should be post-processed with "sort" before viewing.
 void lwt_dump (const char *file_name) __attribute__ ((externally_visible));
 
 // <flags> indicates what kind of trace messages should be included in the dump. <flags> is a sequence of letters
@@ -49,16 +30,11 @@ void lwt_set_trace_level (const char *flags);
 static inline void lwt_trace (const char *flag, const char *format, size_t value1, size_t value2) {
     extern uint64_t flag_mask_;
     if (EXPECT_FALSE(flag_mask_ & (1 << (flag[0] - 'A')))) {
-        LOCALIZE_THREAD_LOCAL(tb_, lwt_buffer_t *);
-        unsigned int u, l;
-        __asm__ __volatile__("rdtsc" : "=a" (l), "=d" (u)); 
-        uint64_t timestamp = ((uint64_t)u << 32) | l; 
         // embed <flags> in <format> so we don't have to make the lwt_record_t any bigger than it already is
         format = (const char *)((size_t)format | ((uint64_t)flag[0] << 56) | ((uint64_t)flag[1] << 48));
-        lwt_record_t temp = { timestamp, format, value1, value2 };
-        if (tb_) {
-            tb_->x[tb_->head++ & LWT_BUFFER_MASK] = temp;
-        }
+        extern void lwt_trace_i (const char *format, size_t value1, size_t value2);
+        lwt_trace_i(format, value1, value2);
     }
 }
+
 #endif//LWT_H
index b04602c2c44692e16042987aebbc93ef83ad0aa1..3e1d940fa12a776ab0cd4e7abaa64b2059e295ab 100644 (file)
@@ -4,7 +4,7 @@
  */
 #ifndef MEM_H
 #define MEM_H
-void mem_init (void);
-void nbd_free (void *x);
 void *nbd_malloc (size_t n);
+void nbd_free (void *x);
+void nbd_defer_free (void *x);
 #endif//MEM_H
diff --git a/include/nbd.h b/include/nbd.h
deleted file mode 100644 (file)
index a6e1dcc..0000000
+++ /dev/null
@@ -1,9 +0,0 @@
-/* 
- * Written by Josh Dybnis and released to the public domain, as explained at
- * http://creativecommons.org/licenses/publicdomain
- */
-#ifndef NBD_H
-#define NBD_H
-void nbd_init (void);
-void nbd_thread_init (int id);
-#endif//NBD_H
diff --git a/include/rcu.h b/include/rcu.h
deleted file mode 100644 (file)
index dd3f121..0000000
+++ /dev/null
@@ -1,10 +0,0 @@
-/* 
- * Written by Josh Dybnis and released to the public domain, as explained at
- * http://creativecommons.org/licenses/publicdomain
- */
-#ifndef RCU_H
-#define RCU_H
-void rcu_thread_init (int thread_id);
-void rcu_update (void);
-void nbd_defer_free (void *x);
-#endif//RCU_H
diff --git a/include/runtime.h b/include/runtime.h
new file mode 100644 (file)
index 0000000..8d9638e
--- /dev/null
@@ -0,0 +1,14 @@
+/* 
+ * Written by Josh Dybnis and released to the public domain, as explained at
+ * http://creativecommons.org/licenses/publicdomain
+ */
+#ifndef THREADS_H
+#define THREADS_H
+
+void nbd_init (void);
+
+int nbd_thread_create (pthread_t *restrict thread, int thread_id, void *(*start_routine)(void *), void *restrict arg);
+
+void rcu_update (void);
+
+#endif//THREADS_H
diff --git a/include/tls.h b/include/tls.h
deleted file mode 100644 (file)
index def2bec..0000000
+++ /dev/null
@@ -1,34 +0,0 @@
-/* 
- * Written by Josh Dybnis and released to the public domain, as explained at
- * http://creativecommons.org/licenses/publicdomain
- *
- * A platform independant wrapper around thread-local storage. On platforms that don't support 
- * __thread variables (e.g. Mac OS X), we have to use the pthreads library for thread-local storage 
- */
-#ifndef TLS_H
-#define TLS_H
-
-#ifdef __ELF__ // use gcc thread-local storage (i.e. __thread variables)
-#define DECLARE_THREAD_LOCAL (name, type)  type name
-#define INIT_THREAD_LOCAL    (name, value) name = value
-#define SET_THREAD_LOCAL     (name, value) name = value
-#define LOCALIZE_THREAD_LOCAL(name, type)  extern __thread type name
-
-#else//!__ELF__
-
-#include <pthread.h>
-
-#define DECLARE_THREAD_LOCAL(name, type) pthread_key_t name##_KEY
-
-#define INIT_THREAD_LOCAL(name, value) \
-    do { \
-        if (pthread_key_create(&name##_KEY, (void *)(size_t)value) != 0) { assert(FALSE); } \
-    } while (0)
-
-#define SET_THREAD_LOCAL(name, value) pthread_setspecific(name##_KEY, (void *)(size_t)value);
-
-#define LOCALIZE_THREAD_LOCAL(name, type) \
-    extern pthread_key_t name##_KEY; type name = (type)(size_t)pthread_getspecific(name##_KEY)
-
-#endif//__ELF__
-#endif//TLS_H
index 1e4c1ec19a698680f3b6f0acfb1433d9ea0246ec..1c9a3b6075038bde1975d083c912de2e2019df10 100644 (file)
--- a/makefile
+++ b/makefile
@@ -6,7 +6,7 @@
 # Makefile for building programs with whole-program interfile optimization 
 ###################################################################################################
 OPT       := -fwhole-program -combine -03 #-DNDEBUG
-CFLAGS := -g -Wall -Werror -std=c99 -m64 -fnested-functions $(OPT) #-DENABLE_TRACE 
+CFLAGS := -g -Wall -Werror -std=c99 -m64 -fnested-functions #$(OPT) #-DENABLE_TRACE 
 INCS   := $(addprefix -I, include)
 TESTS  := output/rcu_test output/list_test output/ht_test
 EXES   := $(TESTS)
index d7b9862d360284750df0a4d47518750958d1fc56..42e79bff9ae89651447e05490e0dca5572af409a 100644 (file)
 #include "lwt.h"
 #include "mem.h"
 
+#define LWT_BUFFER_SCALE 16
+#define LWT_BUFFER_SIZE (1 << LWT_BUFFER_SCALE)
+#define LWT_BUFFER_MASK (LWT_BUFFER_SIZE - 1)
+
+typedef struct lwt_record {
+    uint64_t timestamp;
+    const char *format;
+    size_t value1;
+    size_t value2;
+} lwt_record_t;
+
+typedef struct lwt_buffer {
+    uint32_t head;
+    lwt_record_t x[0];
+} lwt_buffer_t;
+
 DECLARE_THREAD_LOCAL(tb_, int);
 
 lwt_buffer_t *lwt_buf_[MAX_NUM_THREADS] = {};
@@ -109,3 +125,14 @@ void lwt_dump (const char *file_name)
         fclose(file);
     }
 }
+
+void lwt_trace_i (const char *format, size_t value1, size_t value2) {
+    LOCALIZE_THREAD_LOCAL(tb_, lwt_buffer_t *);
+    if (tb_) {
+        unsigned int u, l;
+        __asm__ __volatile__("rdtsc" : "=a" (l), "=d" (u)); 
+        uint64_t timestamp = ((uint64_t)u << 32) | l; 
+        lwt_record_t temp = { timestamp, format, value1, value2 };
+        tb_->x[tb_->head++ & LWT_BUFFER_MASK] = temp;
+    }
+}
index 0967c4afb524b93b0941907da78d88b5568d76a8..c65dfb05c7705fce3e2900ef6d306d708ba153ad 100644 (file)
@@ -23,8 +23,8 @@ typedef struct block {
 
 // region header
 typedef struct header {
-    char owner; // thread id of owner
-    char scale; // log2 of the block size
+    uint8_t owner; // thread id of owner
+    uint8_t scale; // log2 of the block size
 } header_t;
 
 static header_t *region_header_ = NULL;
index dfa49c8652ed277de7eb847716bd61d0f21e96a5..837845381c1b9c7fc0df50d9ea4748bf3eabc63a 100644 (file)
@@ -6,10 +6,8 @@
  */
 #include <string.h>
 #include "common.h"
-#include "rcu.h"
 #include "lwt.h"
 #include "mem.h"
-#include "nbd.h"
 #include "tls.h"
 
 #define RCU_POST_THRESHOLD 10
@@ -101,9 +99,9 @@ void nbd_defer_free (void *x) {
 }
 
 #ifdef MAKE_rcu_test
-#include <pthread.h>
 #include <errno.h>
 #include <stdio.h>
+#include "runtime.h"
 
 #define NUM_ITERATIONS 10000000
 
@@ -152,7 +150,6 @@ node_t *node_alloc (void) {
 void *worker (void *arg) {
     int id = (int)(size_t)arg;
     unsigned int rand_seed = (unsigned int)id + 1;
-    nbd_thread_init(id);
 
     // Wait for all the worker threads to be ready.
     __sync_fetch_and_add(&wait_, -1);
@@ -199,7 +196,7 @@ int main (int argc, char **argv) {
 
     pthread_t thread[num_threads];
     for (int i = 0; i < num_threads; ++i) {
-        int rc = pthread_create(thread + i, NULL, worker, (void *)(size_t)i);
+        int rc = nbd_thread_create(thread + i, i, worker, (void *)(size_t)i);
         if (rc != 0) { perror("pthread_create"); return rc; }
     }
     for (int i = 0; i < num_threads; ++i) {
index ed93e8f8764f57e4e95176f94850a3ec85e267c8..0731bfdc70226d81ba2c87a95d9405a7dcfd500c 100644 (file)
@@ -2,23 +2,46 @@
  * Written by Josh Dybnis and released to the public domain, as explained at
  * http://creativecommons.org/licenses/publicdomain
  */
+#include <pthread.h>
 #include "common.h"
-#include "rcu.h"
-#include "lwt.h"
+#include "runtime.h"
+#include "runtime_local.h"
 #include "mem.h"
-#include "nbd.h"
 #include "tls.h"
 
+#undef malloc
+#undef free
+
 DECLARE_THREAD_LOCAL(tid_, int);
 
+typedef struct thread_info {
+    int thread_id;
+    void *(*start_routine)(void *);
+    void *restrict arg;
+} thread_info_t;
+
 void nbd_init (void) {
     INIT_THREAD_LOCAL(tid_, NULL);
     mem_init();
     lwt_init();
+    lwt_thread_init(0);
+    rcu_thread_init(0);
+}
+
+static void *worker (void *arg) {
+    thread_info_t *ti = (thread_info_t *)arg;
+    SET_THREAD_LOCAL(tid_, ti->thread_id);
+    lwt_thread_init(ti->thread_id);
+    rcu_thread_init(ti->thread_id);
+    void *ret = ti->start_routine(ti->arg);
+    free(ti);
+    return ret;
 }
 
-void nbd_thread_init (int id) {
-    SET_THREAD_LOCAL(tid_, id);
-    lwt_thread_init(id);
-    rcu_thread_init(id);
+int nbd_thread_create (pthread_t *restrict thread, int thread_id, void *(*start_routine)(void *), void *restrict arg) {
+    thread_info_t *ti = (thread_info_t *)malloc(sizeof(thread_info_t));
+    ti->thread_id = thread_id;
+    ti->start_routine = start_routine;
+    ti->arg = arg;
+    return pthread_create(thread, NULL, worker, ti);
 }
index 54eb2e05724a6a2f68c98640d3b616699e2a05af..e3debc4c9f0eac5dfc32c86022fb69f90f7bae38 100644 (file)
@@ -16,7 +16,6 @@
 #include "ht.h"
 #include "murmur.h"
 #include "mem.h"
-#include "rcu.h"
 
 #define COPIED_VALUE            (-1)
 #define TOMBSTONE               STRIP_TAG(COPIED_VALUE)
@@ -27,8 +26,8 @@
 #define MAX_BUCKETS_TO_PROBE    250
 
 typedef struct ht_entry {
-    int64_t key;
-    int64_t value;
+    uint64_t key;
+    uint64_t value;
 } entry_t;
 
 typedef struct string {
@@ -49,7 +48,7 @@ typedef struct hash_table_i {
 } hash_table_i_t;
 
 static int hti_copy_entry 
-    (hash_table_i_t *old_hti, volatile entry_t *e, uint32_t e_key_hash, hash_table_i_t *new_hti);
+    (hash_table_i_t *ht1, volatile entry_t *e, uint32_t e_key_hash, hash_table_i_t *ht2);
 
 // Choose the next bucket to probe using the high-order bits of <key_hash>.
 static inline int get_next_ndx(int old_ndx, uint32_t key_hash, int ht_scale) {
@@ -175,31 +174,32 @@ static void hti_start_copy (hash_table_i_t *hti) {
     TRACE("h0", "hti_start_copy: new hti is %p", next, 0);
 }
 
-// Copy the key and value stored in <old_e> (which must be an entry in <old_hti>) to <new_hti>. 
+// Copy the key and value stored in <ht1_e> (which must be an entry in <ht1>) to <ht2>. 
 //
-// Return 1 unless <old_e> is already copied (then return 0), so the caller can account for the total
+// Return 1 unless <ht1_e> 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 (hash_table_i_t *old_hti, volatile entry_t *old_e, uint32_t key_hash, 
-                           hash_table_i_t *new_hti) {
-    TRACE("h0", "hti_copy_entry(copy entry from %p to %p)", old_hti, new_hti);
-    assert(old_hti);
-    assert(old_hti->next);
-    assert(new_hti);
-    assert(old_e >= old_hti->table && old_e < old_hti->table + (1 << old_hti->scale));
-
-    int64_t old_e_value = old_e->value;
-    TRACE("h0", "hti_copy_entry: entry %p current value %p", old_e, old_e_value);
-    if (EXPECT_FALSE(old_e_value == COPIED_VALUE))
+static int hti_copy_entry (hash_table_i_t *ht1, volatile entry_t *ht1_e, uint32_t key_hash, 
+                           hash_table_i_t *ht2) {
+    TRACE("h0", "hti_copy_entry(copy entry from %p to %p)", ht1, 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));
+
+    uint64_t ht1_e_value = ht1_e->value;
+    TRACE("h0", "hti_copy_entry: entry %p current value %p", ht1_e, ht1_e_value);
+    if (EXPECT_FALSE(ht1_e_value == COPIED_VALUE))
         return FALSE; // already copied
 
     // Kill empty entries.
-    if (EXPECT_FALSE(old_e_value == DOES_NOT_EXIST)) {
-        old_e_value = SYNC_CAS(&old_e->value, DOES_NOT_EXIST, COPIED_VALUE);
-        if (old_e_value == DOES_NOT_EXIST) {
+    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("h0", "hti_copy_entry: old entry killed", 0, 0);
             return TRUE;
         }
-        if (old_e_value == COPIED_VALUE) {
+        if (ht1_e_value == COPIED_VALUE) {
             TRACE("h0", "hti_copy_entry: lost race to kill empty entry in old hti", 0, 0);
             return FALSE; // another thread beat us to it
         }
@@ -208,72 +208,72 @@ static int hti_copy_entry (hash_table_i_t *old_hti, volatile entry_t *old_e, uin
     }
 
     // Tag the value in the old entry to indicate a copy is in progress.
-    old_e_value = SYNC_FETCH_AND_OR(&old_e->value, TAG_VALUE(0));
-    TRACE("h0", "hti_copy_entry: tagged the value %p in old entry %p", old_e_value, old_e);
-    if (old_e_value == COPIED_VALUE) 
+    ht1_e_value = SYNC_FETCH_AND_OR(&ht1_e->value, TAG_VALUE(0));
+    TRACE("h0", "hti_copy_entry: tagged the value %p in old entry %p", ht1_e_value, ht1_e);
+    if (ht1_e_value == COPIED_VALUE) 
         return FALSE; // <value> was already copied by another thread.
 
     // Deleted entries don't need to be installed into to the new table, but their keys do need to
     // be freed.
     assert(COPIED_VALUE == TAG_VALUE(TOMBSTONE));
-    if (old_e_value == TOMBSTONE) {
-        nbd_defer_free((string_t *)(old_e->key & MASK(48)));
+    if (ht1_e_value == TOMBSTONE) {
+        nbd_defer_free((string_t *)(ht1_e->key & MASK(48)));
         return TRUE; 
     }
-    old_e_value = STRIP_TAG(old_e_value);
 
     // Install the key in the new table.
-    uint64_t old_e_key = old_e->key;
-    string_t *key = (string_t *)(old_e_key & MASK(48));
-    TRACE("h0", "hti_copy_entry: key %p is %s", old_e_key, key->val);
+    uint64_t key = ht1_e->key;
+    string_t *key_string = (string_t *)(key & MASK(48));
+    uint64_t value = STRIP_TAG(ht1_e_value);
+    TRACE("h0", "hti_copy_entry: key %p is %s", key, key_string->val);
 
     // We use 0 to indicate that <key_hash> isn't initiallized. Occasionally the <key_hash> will
     // really be 0 and we will waste time recomputing it. That is rare enough that it is OK. 
     if (key_hash == 0) { 
-        key_hash = murmur32(key->val, key->len);
+        key_hash = murmur32(key_string->val, key_string->len);
     }
 
     int is_empty;
-    volatile entry_t *new_e = hti_lookup(new_hti, key_hash, key->val, key->len, &is_empty);
+    volatile entry_t *ht2_e = hti_lookup(ht2, key_hash, key_string->val, key_string->len, &is_empty);
 
     // it is possible that there is not any room in the new table either
-    if (EXPECT_FALSE(new_e == NULL)) {
-        hti_start_copy(new_hti); // initiate nested copy, if not already started
-        return hti_copy_entry(old_hti, old_e, key_hash, new_hti->next); // recursive tail-call
+    if (EXPECT_FALSE(ht2_e == 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
     }
 
     // a tagged entry returned from hti_lookup() means it is either empty or has a new key
     if (is_empty) {
-        uint64_t new_e_key = SYNC_CAS(&new_e->key, DOES_NOT_EXIST, old_e_key);
-        if (new_e_key != DOES_NOT_EXIST) {
+        uint64_t old_ht2_e_key = SYNC_CAS(&ht2_e->key, DOES_NOT_EXIST, key);
+        if (old_ht2_e_key != DOES_NOT_EXIST) {
             TRACE("h0", "hti_copy_entry: lost race to CAS key %p into new entry; found %p",
-                    old_e_key, new_e_key);
-            return hti_copy_entry(old_hti, old_e, key_hash, new_hti); // recursive tail-call
+                    key, old_ht2_e_key);
+            return hti_copy_entry(ht1, ht1_e, key_hash, ht2); // recursive tail-call
         }
     }
-    assert(ht_key_equals(new_e->key, key_hash, key->val, key->len));
-    TRACE("h0", "hti_copy_entry: key %p installed in new old hti %p", key->val, new_hti);
+    assert(ht_key_equals(ht2_e->key, key_hash, key_string->val, key_string->len));
+    TRACE("h0", "hti_copy_entry: key %p installed in new old hti %p", key_string->val, ht2);
 
     // Copy the value to the entry in the new table.
-    uint64_t new_e_value = SYNC_CAS(&new_e->value, DOES_NOT_EXIST, old_e_value);
+    uint64_t old_ht2_e_value = SYNC_CAS(&ht2_e->value, DOES_NOT_EXIST, value);
 
     // If there is a nested copy in progress, we might have installed the key into a dead entry.
-    if (new_e_value == COPIED_VALUE)
-        return hti_copy_entry(old_hti, old_e, key_hash, new_hti->next); // recursive tail-call
+    if (old_ht2_e_value == COPIED_VALUE)
+        return hti_copy_entry(ht1, ht1_e, key_hash, ht2->next); // recursive tail-call
 
     // Mark the old entry as dead.
-    old_e->value = COPIED_VALUE;
+    ht1_e->value = COPIED_VALUE;
 
     // Update the count if we were the one that completed the copy.
-    if (new_e_value == DOES_NOT_EXIST) {
-        TRACE("h0", "hti_copy_entry: value %p installed in new hti %p", old_e_value, new_hti);
-        SYNC_ADD(&old_hti->count, -1);
-        SYNC_ADD(&new_hti->count, 1);
+    if (old_ht2_e_value == DOES_NOT_EXIST) {
+        TRACE("h0", "hti_copy_entry: value %p installed in new hti %p", value, ht2);
+        SYNC_ADD(&ht1->count, -1);
+        SYNC_ADD(&ht2->count, 1);
         return TRUE;
     }
 
     TRACE("h0", "hti_copy_entry: lost race to CAS value %p in new hti; found %p", 
-                old_e_value, new_e_value);
+                value, old_ht2_e_value);
     return FALSE; // another thread completed the copy
 }
 
@@ -291,8 +291,8 @@ static int hti_copy_entry (hash_table_i_t *old_hti, volatile entry_t *old_e, uin
 // real value matches (i.e. not a TOMBSTONE or DOES_NOT_EXIST) as long as <key> is in the table. If
 // <expected> is HT_EXPECT_WHATEVER then skip the test entirely.
 //
-static int64_t hti_compare_and_set (hash_table_i_t *hti, uint32_t key_hash, const char *key_val, 
-                                    uint32_t key_len, int64_t expected, int64_t new) {
+static uint64_t hti_compare_and_set (hash_table_i_t *hti, uint32_t key_hash, const char *key_val, 
+                                    uint32_t key_len, uint64_t expected, uint64_t new) {
     TRACE("h0", "hti_compare_and_set(hti %p key \"%s\")", hti, key_val);
     TRACE("h0", "hti_compare_and_set(new value %p; caller expects value %p)", new, expected);
     assert(hti);
@@ -337,7 +337,7 @@ static int64_t hti_compare_and_set (hash_table_i_t *hti, uint32_t key_hash, cons
     }
 
     // If the entry is in the middle of a copy, the copy must be completed first.
-    int64_t e_value = e->value;
+    uint64_t e_value = e->value;
     TRACE("h0", "hti_compare_and_set: value in entry %p is %p", e, e_value);
     if (EXPECT_FALSE(IS_TAGGED(e_value))) {
         int did_copy = hti_copy_entry(hti, e, key_hash, ((volatile hash_table_i_t *)hti)->next);
@@ -377,7 +377,7 @@ static int64_t hti_compare_and_set (hash_table_i_t *hti, uint32_t key_hash, cons
 }
 
 //
-static int64_t hti_get (hash_table_i_t *hti, uint32_t key_hash, const char *key_val, uint32_t key_len) {
+static uint64_t hti_get (hash_table_i_t *hti, uint32_t key_hash, const char *key_val, uint32_t key_len) {
     assert(key_val);
 
     int is_empty;
@@ -396,7 +396,7 @@ static int64_t hti_get (hash_table_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.
-    int64_t e_value = e->value;
+    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 hash_table_i_t *)hti)->next);
@@ -411,13 +411,13 @@ static int64_t hti_get (hash_table_i_t *hti, uint32_t key_hash, const char *key_
 }
 
 //
-int64_t ht_get (hash_table_t *ht, const char *key_val, uint32_t key_len) {
+uint64_t ht_get (hash_table_t *ht, const char *key_val, uint32_t key_len) {
     return hti_get(*ht, murmur32(key_val, key_len), key_val, key_len);
 }
 
 //
-int64_t ht_compare_and_set (hash_table_t *ht, const char *key_val, uint32_t key_len, 
-                            int64_t expected_val, int64_t new_val) {
+uint64_t ht_compare_and_set (hash_table_t *ht, const char *key_val, uint32_t key_len, 
+                            uint64_t expected_val, uint64_t new_val) {
 
     assert(key_val);
     assert(!IS_TAGGED(new_val) && new_val != DOES_NOT_EXIST);
@@ -457,7 +457,7 @@ int64_t ht_compare_and_set (hash_table_t *ht, const char *key_val, uint32_t key_
         hti = *ht;
     }
 
-    int64_t old_val;
+    uint64_t old_val;
     uint32_t key_hash = murmur32(key_val, key_len);
     while ((old_val = hti_compare_and_set(hti, key_hash, key_val, key_len, expected_val, new_val)) 
            == COPIED_VALUE) {
@@ -470,9 +470,9 @@ int64_t ht_compare_and_set (hash_table_t *ht, const char *key_val, uint32_t key_
 
 // Remove the value in <ht> associated with <key_val>. Returns the value removed, or 
 // DOES_NOT_EXIST if there was no value for that key.
-int64_t ht_remove (hash_table_t *ht, const char *key_val, uint32_t key_len) {
+uint64_t ht_remove (hash_table_t *ht, const char *key_val, uint32_t key_len) {
     hash_table_i_t *hti = *ht;
-    int64_t val;
+    uint64_t val;
     uint32_t key_hash = murmur32(key_val, key_len);
     do {
         val = hti_compare_and_set(hti, key_hash, key_val, key_len, HT_EXPECT_WHATEVER, TOMBSTONE);
index 61b2bfc29a432d6556586489cbc2721b35b0bbb9..e8fcc4c299489355eb4cdb88b1e17eae9bf1308b 100644 (file)
@@ -4,10 +4,9 @@
  */
 #include <stdio.h>
 #include <pthread.h>
+#include "runtime.h"
 #include "CuTest.h"
 #include "common.h"
-#include "nbd.h"
-#include "rcu.h"
 #include "ht.h"
 #include "mem.h"
 
@@ -96,7 +95,6 @@ void *simple_worker (void *arg) {
     uint64_t d = wd->id;
     int iters = 20000;
 
-    nbd_thread_init(d);
     SYNC_ADD(wd->wait, -1);
     do { } while (*((volatile worker_data_t *)wd)->wait); // wait for all workers to be ready
 
@@ -161,8 +159,6 @@ void concurrent_insert (CuTest* tc) {
 int main (void) {
 
     nbd_init();
-    nbd_thread_init(0);
-
     //lwt_set_trace_level("h4");
 
     // Create and run test suite
index 28c15aa9da2f4e9643b0c1b89a421f4208faf9e6..2fad6ee340bff01ca7c7b4c65584d7551a619b92 100644 (file)
@@ -11,7 +11,6 @@
 
 #include "common.h"
 #include "lwt.h"
-#include "rcu.h"
 #include "mem.h"
 
 #define NUM_ITERATIONS 10000000
@@ -30,21 +29,18 @@ typedef struct list {
     node_t last;
 } list_t;
 
-static void list_node_init (node_t *item, int key)
-{
+static void list_node_init (node_t *item, int key) {
     memset(item, 0, sizeof(node_t));
     item->key = key;
 }
 
-node_t *list_node_alloc (int key)
-{
+node_t *list_node_alloc (int key) {
     node_t *item = (node_t *)nbd_malloc(sizeof(node_t));
     list_node_init(item, key);
     return item;
 }
 
-list_t *list_alloc (void)
-{
+list_t *list_alloc (void) {
     list_t *list = (list_t *)nbd_malloc(sizeof(list_t));
     list_node_init(list->head, INT_MIN);
     list_node_init(&list->last, INT_MAX);
@@ -52,8 +48,7 @@ list_t *list_alloc (void)
     return list;
 }
 
-static void find_pred_and_item (node_t **pred_ptr, node_t **item_ptr, list_t *list, int key)
-{
+static void find_pred_and_item (node_t **pred_ptr, node_t **item_ptr, list_t *list, int key) {
     node_t *pred = list->head;
     node_t *item = list->head->next; // head is never removed
     TRACE("l3", "find_pred_and_item: searching for key %llu in list (head is %p)", key, pred);
@@ -93,8 +88,7 @@ static void find_pred_and_item (node_t **pred_ptr, node_t **item_ptr, list_t *li
     } while (1);
 }
 
-int list_insert (list_t *list, node_t *item)
-{
+int list_insert (list_t *list, node_t *item) {
     TRACE("l3", "list_insert: inserting %p (with key %llu)", item, item->key);
     node_t *pred, *next, *other = (node_t *)-1;
     do {
@@ -121,8 +115,7 @@ int list_insert (list_t *list, node_t *item)
     return 1;
 }
 
-node_t *list_remove (list_t *list, int key)
-{
+node_t *list_remove (list_t *list, int key) {
     node_t *pred, *item, *next;
 
     TRACE("l3", "list_remove: removing item with key %llu", key, 0);
@@ -161,8 +154,7 @@ node_t *list_remove (list_t *list, int key)
     return item;
 }
 
-void list_print (list_t *list)
-{
+void list_print (list_t *list) {
     node_t *item;
     item = list->head;
     while (item) {
@@ -176,16 +168,14 @@ void list_print (list_t *list)
 #ifdef MAKE_list_test
 #include <errno.h>
 #include <pthread.h>
-#include "nbd.h"
+#include "runtime.h"
 
 static volatile int wait_;
 static long num_threads_;
 static list_t *list_;
 
-void *worker (void *arg)
-{
+void *worker (void *arg) {
     int id = (int)(size_t)arg;
-    nbd_thread_init(id);
 
     unsigned int rand_seed = id+1;//rdtsc_l();
 
@@ -217,8 +207,7 @@ void *worker (void *arg)
     return NULL;
 }
 
-int main (int argc, char **argv)
-{
+int main (int argc, char **argv) {
     nbd_init();
     //lwt_set_trace_level("m0l0");
 
@@ -259,7 +248,7 @@ int main (int argc, char **argv)
 
     int i;
     for (i = 0; i < num_threads_; ++i) {
-        int rc = pthread_create(thread + i, NULL, worker, (void*)(size_t)i);
+        int rc = nbd_thread_create(thread + i, i, worker, (void*)(size_t)i);
         if (rc != 0) { perror("pthread_create"); return rc; }
     }
 
diff --git a/tags b/tags
deleted file mode 100644 (file)
index 7f019cb..0000000
--- a/tags
+++ /dev/null
@@ -1,335 +0,0 @@
-!_TAG_FILE_FORMAT      2       /extended format; --format=1 will not append ;" to lines/
-!_TAG_FILE_SORTED      1       /0=unsorted, 1=sorted, 2=foldcase/
-!_TAG_PROGRAM_AUTHOR   Darren Hiebert  /dhiebert@users.sourceforge.net/
-!_TAG_PROGRAM_NAME     Exuberant Ctags //
-!_TAG_PROGRAM_URL      http://ctags.sourceforge.net    /official site/
-!_TAG_PROGRAM_VERSION  5.7     //
-ASSERT_EQUAL   struct/ht_test.c        /^#define ASSERT_EQUAL(/;"      d       file:
-CACHE_LINE_SIZE        include/common.h        /^#define CACHE_LINE_SIZE /;"   d
-CAT    include/common.h        /^#define CAT(/;"       d
-CFLAGS makefile        /^CFLAGS := -g -Wall -Werror -std=c99 -m64 -fnested-functions -fwhole-program -combine -03 -DENABLE_TRACE$/;"   m
-CLEAR_MARK     struct/list.c   /^#define CLEAR_MARK(/;"        d       file:
-COPIED_VALUE   struct/ht.c     /^#define COPIED_VALUE /;"      d       file:
-CU_ALLOC       include/CuTest.h        /^#define CU_ALLOC(/;"  d
-CU_TEST_H      include/CuTest.h        /^#define CU_TEST_H$/;" d
-CuAssert       include/CuTest.h        /^#define CuAssert(/;"  d
-CuAssertDblEquals      include/CuTest.h        /^#define CuAssertDblEquals(/;" d
-CuAssertDblEquals_LineMsg      util/CuTest.c   /^void CuAssertDblEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, $/;"      f
-CuAssertDblEquals_Msg  include/CuTest.h        /^#define CuAssertDblEquals_Msg(/;"     d
-CuAssertIntEquals      include/CuTest.h        /^#define CuAssertIntEquals(/;" d
-CuAssertIntEquals_LineMsg      util/CuTest.c   /^void CuAssertIntEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, $/;"      f
-CuAssertIntEquals_Msg  include/CuTest.h        /^#define CuAssertIntEquals_Msg(/;"     d
-CuAssertPtrEquals      include/CuTest.h        /^#define CuAssertPtrEquals(/;" d
-CuAssertPtrEquals_LineMsg      util/CuTest.c   /^void CuAssertPtrEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, $/;"      f
-CuAssertPtrEquals_Msg  include/CuTest.h        /^#define CuAssertPtrEquals_Msg(/;"     d
-CuAssertPtrNotNull     include/CuTest.h        /^#define CuAssertPtrNotNull(/;"        d
-CuAssertPtrNotNullMsg  include/CuTest.h        /^#define CuAssertPtrNotNullMsg(/;"     d
-CuAssertStrEquals      include/CuTest.h        /^#define CuAssertStrEquals(/;" d
-CuAssertStrEquals_LineMsg      util/CuTest.c   /^void CuAssertStrEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message, $/;"      f
-CuAssertStrEquals_Msg  include/CuTest.h        /^#define CuAssertStrEquals_Msg(/;"     d
-CuAssertTrue   include/CuTest.h        /^#define CuAssertTrue(/;"      d
-CuAssert_Line  util/CuTest.c   /^void CuAssert_Line(CuTest* tc, const char* file, int line, const char* message, int condition)$/;"    f
-CuFail include/CuTest.h        /^#define CuFail(/;"    d
-CuFailInternal util/CuTest.c   /^static void CuFailInternal(CuTest* tc, const char* file, int line, CuString* string)$/;"      f       file:
-CuFail_Line    util/CuTest.c   /^void CuFail_Line(CuTest* tc, const char* file, int line, const char* message2, const char* message)$/;"       f
-CuStrAlloc     util/CuTest.c   /^char* CuStrAlloc(int size)$/;"        f
-CuStrCopy      util/CuTest.c   /^char* CuStrCopy(const char* old)$/;"  f
-CuString       include/CuTest.h        /^} CuString;$/;"       t       typeref:struct:__anon1
-CuStringAppend util/CuTest.c   /^void CuStringAppend(CuString* str, const char* text)$/;"      f
-CuStringAppendChar     util/CuTest.c   /^void CuStringAppendChar(CuString* str, char ch)$/;"   f
-CuStringAppendFormat   util/CuTest.c   /^void CuStringAppendFormat(CuString* str, const char* format, ...)$/;" f
-CuStringInit   util/CuTest.c   /^void CuStringInit(CuString* str)$/;"  f
-CuStringInsert util/CuTest.c   /^void CuStringInsert(CuString* str, const char* text, int pos)$/;"     f
-CuStringNew    util/CuTest.c   /^CuString* CuStringNew(void)$/;"       f
-CuStringResize util/CuTest.c   /^void CuStringResize(CuString* str, int newSize)$/;"   f
-CuSuite        include/CuTest.h        /^} CuSuite;$/;"        t       typeref:struct:__anon2
-CuSuiteAdd     util/CuTest.c   /^void CuSuiteAdd(CuSuite* testSuite, CuTest *testCase)$/;"     f
-CuSuiteAddSuite        util/CuTest.c   /^void CuSuiteAddSuite(CuSuite* testSuite, CuSuite* testSuite2)$/;"     f
-CuSuiteDetails util/CuTest.c   /^void CuSuiteDetails(CuSuite* testSuite, CuString* details)$/;"        f
-CuSuiteInit    util/CuTest.c   /^void CuSuiteInit(CuSuite* testSuite)$/;"      f
-CuSuiteNew     util/CuTest.c   /^CuSuite* CuSuiteNew(void)$/;" f
-CuSuiteRun     util/CuTest.c   /^void CuSuiteRun(CuSuite* testSuite)$/;"       f
-CuSuiteSummary util/CuTest.c   /^void CuSuiteSummary(CuSuite* testSuite, CuString* summary)$/;"        f
-CuTest include/CuTest.h        /^struct CuTest$/;"     s
-CuTest include/CuTest.h        /^typedef struct CuTest CuTest;$/;"     t       typeref:struct:CuTest
-CuTestInit     util/CuTest.c   /^void CuTestInit(CuTest* t, const char* name, TestFunction function)$/;"       f
-CuTestNew      util/CuTest.c   /^CuTest* CuTestNew(const char* name, TestFunction function)$/;"        f
-CuTestRun      util/CuTest.c   /^void CuTestRun(CuTest* tc)$/;"        f
-DECLARE_THREAD_LOCAL   include/tls.h   /^#define DECLARE_THREAD_LOCAL(/;"      d
-DOES_NOT_EXIST include/ht.h    /^#define DOES_NOT_EXIST /;"    d
-ENTRIES_PER_BUCKET     struct/ht.c     /^#define ENTRIES_PER_BUCKET /;"        d       file:
-ENTRIES_PER_COPY_CHUNK struct/ht.c     /^#define ENTRIES_PER_COPY_CHUNK /;"    d       file:
-EXES   makefile        /^EXES   := $(TESTS)$/;"        m
-EXPECT_FALSE   include/common.h        /^#define EXPECT_FALSE(/;"      d
-EXPECT_TRUE    include/common.h        /^#define EXPECT_TRUE(/;"       d
-FALSE  include/common.h        /^#define FALSE /;"     d
-GET_SCALE      util/mem.c      /^#define GET_SCALE(/;" d       file:
-GlobalVersion  txn/txn.c       /^uint64_t GlobalVersion = 1;$/;"       v
-HT_EXPECT_EXISTS       include/ht.h    /^#define HT_EXPECT_EXISTS /;"  d
-HT_EXPECT_NOT_EXISTS   include/ht.h    /^#define HT_EXPECT_NOT_EXISTS /;"      d
-HT_EXPECT_WHATEVER     include/ht.h    /^#define HT_EXPECT_WHATEVER /;"        d
-HUGE_STRING_LEN        include/CuTest.h        /^#define HUGE_STRING_LEN       /;"     d
-INCS   makefile        /^INCS   := $(addprefix -I, include)$/;"        m
-INITIAL_WRITES_SIZE    txn/txn.c       /^#define INITIAL_WRITES_SIZE /;"       d       file:
-INIT_THREAD_LOCAL      include/tls.h   /^#define INIT_THREAD_LOCAL /;" d
-INIT_THREAD_LOCAL      include/tls.h   /^#define INIT_THREAD_LOCAL(/;" d
-IS_MARKED      struct/list.c   /^#define IS_MARKED(/;" d       file:
-IS_TAGGED      include/common.h        /^#define IS_TAGGED(/;" d
-LOCALIZE       include/tls.h   /^#define LOCALIZE /;"  d
-LOCALIZE       include/tls.h   /^#define LOCALIZE(/;"  d
-LWT_BUFFER_MASK        include/lwt.h   /^#define LWT_BUFFER_MASK /;"   d
-LWT_BUFFER_SCALE       include/lwt.h   /^#define LWT_BUFFER_SCALE /;"  d
-LWT_BUFFER_SIZE        include/lwt.h   /^#define LWT_BUFFER_SIZE /;"   d
-LWT_H  include/lwt.h   /^#define LWT_H$/;"     d
-MASK   include/common.h        /^#define MASK(/;"      d
-MAX_BUCKETS_TO_PROBE   struct/ht.c     /^#define MAX_BUCKETS_TO_PROBE /;"      d       file:
-MAX_NUM_THREADS        struct/list.c   /^#define MAX_NUM_THREADS /;"   d       file:
-MAX_SCALE      util/mem.c      /^#define MAX_SCALE /;" d       file:
-MAX_TEST_CASES include/CuTest.h        /^#define MAX_TEST_CASES        /;"     d
-MEM_H  include/mem.h   /^#define MEM_H$/;"     d
-MIN_SCALE      struct/ht.c     /^#define MIN_SCALE /;" d       file:
-MinActiveTxnVersion    txn/txn.c       /^uint64_t MinActiveTxnVersion = 0;$/;" v
-NBD_H  include/nbd.h   /^#define NBD_H$/;"     d
-NBHT_H include/ht.h    /^#define NBHT_H$/;"    d
-NUM_ITERATIONS struct/list.c   /^#define NUM_ITERATIONS /;"    d       file:
-NUM_ITERATIONS util/rcu.c      /^#define NUM_ITERATIONS /;"    d       file:
-NUM_THREADS    include/common.h        /^#define NUM_THREADS /;"       d
-ON_EXIT_SCOPE  include/common.h        /^#define ON_EXIT_SCOPE(/;"     d
-ON_EXIT_SCOPE_I        include/common.h        /^#define ON_EXIT_SCOPE_I(/;"   d
-PLACE_MARK     struct/list.c   /^#define PLACE_MARK(/;"        d       file:
-RCU_POST_THRESHOLD     util/rcu.c      /^#define RCU_POST_THRESHOLD /;"        d       file:
-RCU_QUEUE_SCALE        util/rcu.c      /^#define RCU_QUEUE_SCALE /;"   d       file:
-SET_THREAD_LOCAL       include/tls.h   /^#define SET_THREAD_LOCAL /;"  d
-SET_THREAD_LOCAL       include/tls.h   /^#define SET_THREAD_LOCAL(/;"  d
-STRING_INC     include/CuTest.h        /^#define STRING_INC    /;"     d
-STRING_MAX     include/CuTest.h        /^#define STRING_MAX    /;"     d
-STRIP_TAG      include/common.h        /^#define STRIP_TAG(/;" d
-SUITE_ADD_TEST include/CuTest.h        /^#define SUITE_ADD_TEST(/;"    d
-SUPERBLOCK_SCALE       util/mem.c      /^#define SUPERBLOCK_SCALE /;"  d       file:
-SUPERBLOCK_SIZE        util/mem.c      /^#define SUPERBLOCK_SIZE /;"   d       file:
-SYNC_ADD       include/common.h        /^#define SYNC_ADD /;"  d
-SYNC_CAS       include/common.h        /^#define SYNC_CAS /;"  d
-SYNC_FETCH_AND_OR      include/common.h        /^#define SYNC_FETCH_AND_OR /;" d
-SYNC_SWAP      include/common.h        /^#define SYNC_SWAP /;" d
-TAG    include/common.h        /^#define TAG /;"       d
-TAG_VALUE      include/common.h        /^#define TAG_VALUE(/;" d
-TESTS  makefile        /^TESTS  := $(addsuffix _test, $(addprefix output\/,rcu list ht txn))$/;"       m
-TLS_H  include/tls.h   /^#define TLS_H$/;"     d
-TOMBSTONE      struct/ht.c     /^#define TOMBSTONE /;" d       file:
-TRACE  include/lwt.h   /^#define TRACE(/;"     d
-TRUE   include/common.h        /^#define TRUE /;"      d
-TXN_ABORTED    txn/txn.c       /^typedef enum { TXN_RUNNING, TXN_VALIDATING, TXN_VALIDATED, TXN_ABORTED } txn_state_t;$/;"     e       enum:__anon5    file:
-TXN_BLIND_WRITE        include/txn.h   /^typedef enum { TXN_READ_WRITE, TXN_READ_ONLY, TXN_BLIND_WRITE } txn_access_t;$/;"     e       enum:__anon3
-TXN_DIRTY_READ include/txn.h   /^typedef enum { TXN_DIRTY_READ, TXN_READ_COMMITTED, TXN_REPEATABLE_READ } txn_isolation_t;$/;" e       enum:__anon4
-TXN_READ_COMMITTED     include/txn.h   /^typedef enum { TXN_DIRTY_READ, TXN_READ_COMMITTED, TXN_REPEATABLE_READ } txn_isolation_t;$/;" e       enum:__anon4
-TXN_READ_ONLY  include/txn.h   /^typedef enum { TXN_READ_WRITE, TXN_READ_ONLY, TXN_BLIND_WRITE } txn_access_t;$/;"     e       enum:__anon3
-TXN_READ_WRITE include/txn.h   /^typedef enum { TXN_READ_WRITE, TXN_READ_ONLY, TXN_BLIND_WRITE } txn_access_t;$/;"     e       enum:__anon3
-TXN_REPEATABLE_READ    include/txn.h   /^typedef enum { TXN_DIRTY_READ, TXN_READ_COMMITTED, TXN_REPEATABLE_READ } txn_isolation_t;$/;" e       enum:__anon4
-TXN_RUNNING    txn/txn.c       /^typedef enum { TXN_RUNNING, TXN_VALIDATING, TXN_VALIDATED, TXN_ABORTED } txn_state_t;$/;"     e       enum:__anon5    file:
-TXN_VALIDATED  txn/txn.c       /^typedef enum { TXN_RUNNING, TXN_VALIDATING, TXN_VALIDATED, TXN_ABORTED } txn_state_t;$/;"     e       enum:__anon5    file:
-TXN_VALIDATING txn/txn.c       /^typedef enum { TXN_RUNNING, TXN_VALIDATING, TXN_VALIDATED, TXN_ABORTED } txn_state_t;$/;"     e       enum:__anon5    file:
-TestFunction   include/CuTest.h        /^typedef void (*TestFunction)(CuTest *);$/;"   t
-UNDETERMINED_VERSION   txn/txn.c       /^#define UNDETERMINED_VERSION /;"      d       file:
-UPDATE_TYPE_DELETE     txn/txn.c       /^typedef enum { UPDATE_TYPE_PUT, UPDATE_TYPE_DELETE } update_type_t;$/;"       e       enum:__anon6    file:
-UPDATE_TYPE_PUT        txn/txn.c       /^typedef enum { UPDATE_TYPE_PUT, UPDATE_TYPE_DELETE } update_type_t;$/;"       e       enum:__anon6    file:
-UTIL_SRCS      makefile        /^UTIL_SRCS      := util\/rcu.c util\/lwt.c util\/CuTest.c util\/mem.c util\/nbd.c$/;"  m
-YAMS_H include/common.h        /^#define YAMS_H$/;"    d
-access txn/txn.c       /^    txn_access_t access;$/;"  m       struct:txn      file:
-alloc_update_rec       txn/txn.c       /^update_rec_t *alloc_update_rec (void) {$/;"   f
-basic_test     struct/ht_test.c        /^void basic_test (CuTest* tc) {$/;"    f
-block  util/mem.c      /^typedef struct block {$/;"    s       file:
-block_t        util/mem.c      /^} block_t;$/;"        t       typeref:struct:block    file:
-buf_count_     util/lwt.c      /^static int buf_count_ = 0;$/;"        v       file:
-buffer include/CuTest.h        /^      char* buffer;$/;"       m       struct:__anon1
-concurrent_insert      struct/ht_test.c        /^void concurrent_insert (CuTest* tc) {$/;"     f
-concurrent_simple      struct/ht_test.c        /^void concurrent_simple (CuTest* tc) {$/;"     f
-count  include/CuTest.h        /^      int count;$/;"  m       struct:__anon2
-count  struct/ht.c     /^    int count; \/\/ TODO: make these counters distributed$/;" m       struct:hash_table_i     file:
-deferred_      struct/ht.c     /^static hash_table_i_t *deferred_ = NULL;$/;"  v       file:
-dequeue        struct/queue.c  /^queue_elem_t dequeue (queue_t *q)$/;" f
-dump_buffer    util/lwt.c      /^static void dump_buffer (FILE *file, int thread_id, uint64_t offset)$/;"      f       file:
-dump_record    util/lwt.c      /^static inline void dump_record (FILE *file, int thread_id, lwt_record_t *r, uint64_t offset)$/;"      f       file:
-enqueue        struct/queue.c  /^void enqueue (queue_t *q, queue_elem_t *e)$/;"        f
-entry_t        struct/ht.c     /^} entry_t;$/;"        t       typeref:struct:ht_entry file:
-failCount      include/CuTest.h        /^      int failCount;$/;"      m       struct:__anon2
-failed include/CuTest.h        /^      int failed;$/;" m       struct:CuTest
-fifo   util/rcu.c      /^typedef struct fifo {$/;"     s       file:
-fifo_alloc     util/rcu.c      /^static fifo_t *fifo_alloc(int scale)$/;"      f       file:
-fifo_dequeue   util/rcu.c      /^static void *fifo_dequeue (fifo_t *q)$/;"     f       file:
-fifo_enqueue   util/rcu.c      /^static void fifo_enqueue (fifo_t *q, void *x)$/;"     f       file:
-fifo_index     util/rcu.c      /^static uint32_t fifo_index (fifo_t *q, uint32_t i)$/;"        f       file:
-fifo_t util/rcu.c      /^} fifo_t;$/;" t       typeref:struct:fifo     file:
-find_pred_and_item     struct/list.c   /^static void find_pred_and_item (node_t **pred_ptr, node_t **item_ptr, list_t *list, int key)$/;"      f       file:
-flag_mask_     util/lwt.c      /^uint64_t flag_mask_ = 0;$/;"  v
-flags_ util/lwt.c      /^static const char *flags_ = "";$/;"   v       file:
-format include/lwt.h   /^    const char *format;$/;"   m       struct:lwt_record
-free   include/common.h        /^#define free /;"      d
-free_list_     util/mem.c      /^static block_t free_list_[NUM_THREADS][MAX_SCALE+1][NUM_THREADS];$/;" v       file:
-function       include/CuTest.h        /^      TestFunction function;$/;"      m       struct:CuTest
-get_new_superblock     util/mem.c      /^static void *get_new_superblock (int scale) {$/;"     f       file:
-get_next_ndx   struct/ht.c     /^static inline int get_next_ndx(int old_ndx, uint32_t key_hash, int ht_scale) {$/;"    f       file:
-hash_table_i   struct/ht.c     /^typedef struct hash_table_i {$/;"     s       file:
-hash_table_i_t struct/ht.c     /^} hash_table_i_t;$/;" t       typeref:struct:hash_table_i     file:
-hash_table_t   include/ht.h    /^typedef struct hash_table_i *hash_table_t;$/;"        t       typeref:struct:hash_table_i
-head   include/lwt.h   /^    uint32_t head;$/;"        m       struct:lwt_buffer
-head   struct/list.c   /^    node_t head[1];$/;"       m       struct:list     file:
-head   struct/queue.c  /^    queue_elem_t *head;$/;"   m       struct:queue    file:
-head   util/rcu.c      /^    node_t *head;$/;" m       struct:lifo     file:
-head   util/rcu.c      /^    uint32_t head;$/;"        m       struct:fifo     file:
-header util/mem.c      /^typedef struct header {$/;"   s       file:
-header_t       util/mem.c      /^} header_t;$/;"       t       typeref:struct:header   file:
-ht     struct/ht.c     /^    hash_table_t *ht; \/\/ parent ht;$/;"     m       struct:hash_table_i     file:
-ht     struct/ht_test.c        /^    hash_table_t *ht;$/;"     m       struct:worker_data      file:
-ht     txn/txn.c       /^    hash_table_t *ht;$/;"     m       struct:txn      file:
-ht_add struct/ht_test.c        /^int64_t ht_add (hash_table_t *ht, const char *key, int64_t val) {$/;" f
-ht_alloc       struct/ht.c     /^hash_table_t *ht_alloc (void) {$/;"   f
-ht_compare_and_set     struct/ht.c     /^int64_t ht_compare_and_set (hash_table_t *ht, const char *key_string, $/;"    f
-ht_count       struct/ht.c     /^uint64_t ht_count (hash_table_t *ht) {$/;"    f
-ht_entry       struct/ht.c     /^typedef struct ht_entry {$/;" s       file:
-ht_free        struct/ht.c     /^void ht_free (hash_table_t *ht) {$/;" f
-ht_free_deferred       struct/ht.c     /^void ht_free_deferred (void) {$/;"    f
-ht_get struct/ht.c     /^int64_t ht_get (hash_table_t *ht, const char *key_string) {$/;"       f
-ht_key_equals  struct/ht.c     /^static inline int ht_key_equals (uint64_t a, uint32_t b_hash, const char *b_value) {$/;"      f       file:
-ht_remove      struct/ht.c     /^int64_t ht_remove (hash_table_t *ht, const char *key_string) {$/;"    f
-ht_replace     struct/ht_test.c        /^int64_t ht_replace (hash_table_t *ht, const char *key, int64_t val) {$/;"     f
-ht_set struct/ht_test.c        /^int64_t ht_set (hash_table_t *ht, const char *key, int64_t val) {$/;" f
-ht_test_SRCS   makefile        /^ht_test_SRCS   := $(UTIL_SRCS) struct\/ht.c struct\/ht_test.c$/;"     m
-hti_alloc      struct/ht.c     /^static hash_table_i_t *hti_alloc (hash_table_t *parent, int scale) {$/;"      f       file:
-hti_compare_and_set    struct/ht.c     /^static int64_t hti_compare_and_set (hash_table_i_t *hti, uint32_t key_hash, const char *key_string, $/;"      f       file:
-hti_copy_entry struct/ht.c     /^static int hti_copy_entry (hash_table_i_t *old_hti, volatile entry_t *old_e, uint32_t key_hash, $/;"  f       file:
-hti_defer_free struct/ht.c     /^static void hti_defer_free (hash_table_i_t *hti) {$/;"        f       file:
-hti_get        struct/ht.c     /^static int64_t hti_get (hash_table_i_t *hti, uint32_t key_hash, const char *key_string) {$/;" f       file:
-hti_lookup     struct/ht.c     /^static volatile entry_t *hti_lookup (hash_table_i_t *hti, uint32_t key_hash, const char *key_string, int *is_empty) {$/;"     f       file:
-hti_start_copy struct/ht.c     /^static void hti_start_copy (hash_table_i_t *hti) {$/;"        f       file:
-id     struct/ht_test.c        /^    int id;$/;"       m       struct:worker_data      file:
-inserter_worker        struct/ht_test.c        /^void *inserter_worker (void *arg) {$/;"       f
-int64_t        include/common.h        /^typedef long long int64_t;$/;"        t
-isolation      txn/txn.c       /^    txn_isolation_t isolation;$/;"    m       struct:txn      file:
-jumpBuf        include/CuTest.h        /^      jmp_buf *jumpBuf;$/;"   m       struct:CuTest
-key    struct/ht.c     /^    int64_t key;$/;"  m       struct:ht_entry file:
-key    struct/list.c   /^    int key;$/;"      m       struct:node     file:
-key    txn/txn.c       /^    struct { const char *key; update_rec_t *rec; } *writes;$/;"       m       struct:txn::__anon7     file:
-last   struct/list.c   /^    node_t last;$/;"  m       struct:list     file:
-last_posted_   util/rcu.c      /^static uint64_t **last_posted_;$/;"   v       file:
-length include/CuTest.h        /^      int length;$/;" m       struct:__anon1
-lifo   util/rcu.c      /^typedef struct lifo {$/;"     s       file:
-lifo_aba_pop   util/rcu.c      /^node_t *lifo_aba_pop (lifo_t *stk)$/;"        f
-lifo_aba_push  util/rcu.c      /^static void lifo_aba_push (lifo_t *stk, node_t *x)$/;"        f       file:
-lifo_alloc     util/rcu.c      /^static lifo_t *lifo_alloc (void)$/;"  f       file:
-lifo_t util/rcu.c      /^} lifo_t;$/;" t       typeref:struct:lifo     file:
-list   include/CuTest.h        /^      CuTest* list[MAX_TEST_CASES];$/;"       m       struct:__anon2
-list   struct/list.c   /^typedef struct list {$/;"     s       file:
-list_  struct/list.c   /^static list_t *list_;$/;"     v       file:
-list_alloc     struct/list.c   /^list_t *list_alloc (void)$/;" f
-list_insert    struct/list.c   /^int list_insert (list_t *list, node_t *item)$/;"      f
-list_node_alloc        struct/list.c   /^node_t *list_node_alloc (int key)$/;" f
-list_node_init struct/list.c   /^static void list_node_init (node_t *item, int key)$/;"        f       file:
-list_print     struct/list.c   /^void list_print (list_t *list)$/;"    f
-list_remove    struct/list.c   /^node_t *list_remove (list_t *list, int key)$/;"       f
-list_t struct/list.c   /^} list_t;$/;" t       typeref:struct:list     file:
-list_test_SRCS makefile        /^list_test_SRCS := $(UTIL_SRCS) struct\/list.c$/;"     m
-lwt_buf_       util/lwt.c      /^lwt_buffer_t **lwt_buf_ = NULL;$/;"   v
-lwt_buffer     include/lwt.h   /^typedef struct lwt_buffer {$/;"       s
-lwt_buffer_t   include/lwt.h   /^} lwt_buffer_t;$/;"   t       typeref:struct:lwt_buffer
-lwt_dump       util/lwt.c      /^void lwt_dump (const char *file_name)$/;"     f
-lwt_init       util/lwt.c      /^void lwt_init (void)$/;"      f
-lwt_record     include/lwt.h   /^typedef struct lwt_record {$/;"       s
-lwt_record_t   include/lwt.h   /^} lwt_record_t;$/;"   t       typeref:struct:lwt_record
-lwt_set_trace_level    util/lwt.c      /^void lwt_set_trace_level (const char *flags)$/;"      f
-lwt_thread_init        util/lwt.c      /^void lwt_thread_init (int thread_id)$/;"      f
-lwt_trace      include/lwt.h   /^static inline void lwt_trace (const char *flag, const char *format, size_t value1, size_t value2) {$/;"       f
-main   struct/ht_test.c        /^int main (void) {$/;" f
-main   struct/list.c   /^int main (int argc, char **argv)$/;"  f
-main   txn/txn.c       /^int main (void) {$/;" f
-main   util/rcu.c      /^int main (void)$/;"   f
-malloc include/common.h        /^#define malloc /;"    d
-max_probe      struct/ht.c     /^    int max_probe;$/;"        m       struct:hash_table_i     file:
-mem_init       util/mem.c      /^void mem_init (void) {$/;"    f
-message        include/CuTest.h        /^      const char* message;$/;"        m       struct:CuTest
-murmur32       include/murmur.h        /^static inline uint32_t murmur32 (const char *key, int len)$/;"        f
-name   include/CuTest.h        /^      const char* name;$/;"   m       struct:CuTest
-nbd_defer_free util/rcu.c      /^void nbd_defer_free (void *x)$/;"     f
-nbd_free       util/mem.c      /^void nbd_free (void *x) {$/;" f
-nbd_init       util/nbd.c      /^void nbd_init (void) {$/;"    f
-nbd_malloc     util/mem.c      /^void *nbd_malloc (size_t n) {$/;"     f
-nbd_thread_init        util/nbd.c      /^void nbd_thread_init (int id) {$/;"   f
-next   struct/ht.c     /^    struct hash_table_i *next;$/;"    m       struct:hash_table_i     typeref:struct:hash_table_i::hash_table_i       file:
-next   struct/list.c   /^    struct node *next;$/;"    m       struct:node     typeref:struct:node::node       file:
-next   struct/queue.c  /^    struct queue_elem *next;$/;"      m       struct:queue_elem       typeref:struct:queue_elem::queue_elem   file:
-next   util/mem.c      /^    struct block *next;$/;"   m       struct:block    typeref:struct:block::block     file:
-next   util/rcu.c      /^    struct node *next;$/;"    m       struct:node     typeref:struct:node::node       file:
-next_free      struct/ht.c     /^    struct hash_table_i *next_free;$/;"       m       struct:hash_table_i     typeref:struct:hash_table_i::hash_table_i       file:
-node   struct/list.c   /^typedef struct node {$/;"     s       file:
-node   util/rcu.c      /^typedef struct node {$/;"     s       file:
-node_alloc     util/rcu.c      /^node_t *node_alloc (void)$/;" f
-node_t struct/list.c   /^} node_t;$/;" t       typeref:struct:node     file:
-node_t util/rcu.c      /^} node_t;$/;" t       typeref:struct:node     file:
-num_entries_copied     struct/ht.c     /^    int num_entries_copied;$/;"       m       struct:hash_table_i     file:
-num_threads_   struct/list.c   /^static long num_threads_;$/;" v       file:
-owner  util/mem.c      /^    char owner; \/\/ thread id of owner$/;"   m       struct:header   file:
-pending_       util/rcu.c      /^static fifo_t **pending_;$/;" v       file:
-prev   txn/txn.c       /^    update_rec_t *prev; \/\/ a previous update$/;"    m       struct:update_rec       file:
-queue  struct/queue.c  /^typedef struct queue {$/;"    s       file:
-queue_elem     struct/queue.c  /^typedef struct queue_elem {$/;"       s       file:
-queue_elem_t   struct/queue.c  /^} queue_elem_t;$/;"   t       typeref:struct:queue_elem       file:
-queue_t        struct/queue.c  /^} queue_t;$/;"        t       typeref:struct:queue    file:
-ran    include/CuTest.h        /^      int ran;$/;"    m       struct:CuTest
-rcu_   util/rcu.c      /^static uint64_t **rcu_;$/;"   v       file:
-rcu_init       util/rcu.c      /^void rcu_init (void)$/;"      f
-rcu_post       util/rcu.c      /^static void rcu_post (uint64_t x)$/;" f       file:
-rcu_test_SRCS  makefile        /^rcu_test_SRCS  := $(UTIL_SRCS)$/;"    m
-rcu_update     util/rcu.c      /^void rcu_update (void)$/;"    f
-rec    txn/txn.c       /^    struct { const char *key; update_rec_t *rec; } *writes;$/;"       m       struct:txn::__anon7     file:
-rv     txn/txn.c       /^    uint64_t rv;$/;"  m       struct:txn      file:
-sb_header_     util/mem.c      /^static header_t *sb_header_ = NULL;$/;"       v       file:
-scale  struct/ht.c     /^    unsigned int scale;$/;"   m       struct:hash_table_i     file:
-scale  util/mem.c      /^    char scale; \/\/ log2 of block size$/;"   m       struct:header   file:
-scale  util/rcu.c      /^    uint32_t scale;$/;"       m       struct:fifo     file:
-scan   struct/ht.c     /^    int scan;$/;"     m       struct:hash_table_i     file:
-simple_worker  struct/ht_test.c        /^void *simple_worker (void *arg) {$/;" f
-size   include/CuTest.h        /^      int size;$/;"   m       struct:__anon1
-state  txn/txn.c       /^    txn_state_t state;$/;"    m       struct:txn      file:
-stk_   util/rcu.c      /^static lifo_t *stk_;$/;"      v       file:
-table  struct/ht.c     /^    volatile entry_t *table;$/;"      m       struct:hash_table_i     file:
-tail   struct/queue.c  /^    queue_elem_t *tail;$/;"   m       struct:queue    file:
-tail   util/rcu.c      /^    uint32_t tail;$/;"        m       struct:fifo     file:
-tc     struct/ht_test.c        /^    CuTest *tc;$/;"   m       struct:worker_data      file:
-timestamp      include/lwt.h   /^    uint64_t timestamp;$/;"   m       struct:lwt_record
-txn    txn/txn.c       /^struct txn {$/;"      s       file:
-txn_abort      txn/txn.c       /^void txn_abort (txn_t *txn) {$/;"     f
-txn_access_t   include/txn.h   /^typedef enum { TXN_READ_WRITE, TXN_READ_ONLY, TXN_BLIND_WRITE } txn_access_t;$/;"     t       typeref:enum:__anon3
-txn_begin      txn/txn.c       /^txn_t *txn_begin (txn_access_t access, txn_isolation_t isolation, hash_table_t *ht) {$/;"     f
-txn_commit     txn/txn.c       /^txn_state_t txn_commit (txn_t *txn) {$/;"     f
-txn_ht_get     txn/txn.c       /^int64_t txn_ht_get (txn_t *txn, const char *key) {$/;"        f
-txn_ht_put     txn/txn.c       /^void txn_ht_put (txn_t *txn, const char *key, int64_t value) {$/;"    f
-txn_ht_validate_key    txn/txn.c       /^static txn_state_t txn_ht_validate_key (txn_t *txn, const char *key) {$/;"    f       file:
-txn_isolation_t        include/txn.h   /^typedef enum { TXN_DIRTY_READ, TXN_READ_COMMITTED, TXN_REPEATABLE_READ } txn_isolation_t;$/;" t       typeref:enum:__anon4
-txn_state_t    txn/txn.c       /^typedef enum { TXN_RUNNING, TXN_VALIDATING, TXN_VALIDATED, TXN_ABORTED } txn_state_t;$/;"     t       typeref:enum:__anon5    file:
-txn_t  include/txn.h   /^typedef struct txn txn_t;$/;" t       typeref:struct:txn
-txn_test_SRCS  makefile        /^txn_test_SRCS  := $(UTIL_SRCS) struct\/ht.c txn\/txn.c$/;"    m
-txn_validate   txn/txn.c       /^static txn_state_t txn_validate (txn_t *txn) {$/;"    f       file:
-type   txn/txn.c       /^    update_type_t type;$/;"   m       struct:update_rec       file:
-uint32_t       include/common.h        /^typedef unsigned int uint32_t;$/;"    t
-uint64_t       include/common.h        /^typedef unsigned long long uint64_t;$/;"      t
-update_rec     txn/txn.c       /^struct update_rec {$/;"       s       file:
-update_rec_t   txn/txn.c       /^typedef struct update_rec update_rec_t;$/;"   t       typeref:struct:update_rec       file:
-update_type_t  txn/txn.c       /^typedef enum { UPDATE_TYPE_PUT, UPDATE_TYPE_DELETE } update_type_t;$/;"       t       typeref:enum:__anon6    file:
-value  struct/ht.c     /^    int64_t value;$/;"        m       struct:ht_entry file:
-value  txn/txn.c       /^    uint64_t value;$/;"       m       struct:update_rec       file:
-value1 include/lwt.h   /^    size_t value1;$/;"        m       struct:lwt_record
-value2 include/lwt.h   /^    size_t value2;$/;"        m       struct:lwt_record
-version        txn/txn.c       /^    uint64_t version;$/;"     m       struct:update_rec       file:
-wait   struct/ht_test.c        /^    int *wait;$/;"    m       struct:worker_data      file:
-wait_  struct/list.c   /^static volatile int wait_;$/;"        v       file:
-wait_  util/rcu.c      /^static volatile int wait_;$/;"        v       file:
-worker struct/list.c   /^void *worker (void *arg)$/;"  f
-worker util/rcu.c      /^void *worker (void *arg)$/;"  f
-worker_data    struct/ht_test.c        /^typedef struct worker_data {$/;"      s       file:
-worker_data_t  struct/ht_test.c        /^} worker_data_t;$/;"  t       typeref:struct:worker_data      file:
-writes txn/txn.c       /^    struct { const char *key; update_rec_t *rec; } *writes;$/;"       m       struct:txn      typeref:struct:txn::__anon7     file:
-writes_count   txn/txn.c       /^    uint32_t writes_count;$/;"        m       struct:txn      file:
-writes_scan    txn/txn.c       /^    uint32_t writes_scan;$/;" m       struct:txn      file:
-writes_size    txn/txn.c       /^    uint32_t writes_size;$/;" m       struct:txn      file:
-wv     txn/txn.c       /^    uint64_t wv;$/;"  m       struct:txn      file:
-x      include/lwt.h   /^    lwt_record_t x[0];$/;"    m       struct:lwt_buffer
-x      util/rcu.c      /^    void *x[0];$/;"   m       struct:fifo     file: