From 9ec5405d406696c6cbdb7a47ade7fccc736a8b53 Mon Sep 17 00:00:00 2001 From: jdybnis Date: Wed, 12 Nov 2008 08:11:26 +0000 Subject: [PATCH] Some refactoring. WARNING: tests not passing! --- include/common.h | 11 +- include/ht.h | 6 +- include/lwt.h | 32 +---- include/mem.h | 4 +- include/nbd.h | 9 -- include/rcu.h | 10 -- include/runtime.h | 14 ++ include/tls.h | 34 ----- makefile | 2 +- runtime/lwt.c | 27 ++++ runtime/mem.c | 4 +- runtime/rcu.c | 7 +- runtime/runtime.c | 37 ++++- struct/ht.c | 122 ++++++++--------- struct/ht_test.c | 6 +- struct/list.c | 33 ++--- tags | 335 ---------------------------------------------- 17 files changed, 165 insertions(+), 528 deletions(-) delete mode 100644 include/nbd.h delete mode 100644 include/rcu.h create mode 100644 include/runtime.h delete mode 100644 include/tls.h delete mode 100644 tags diff --git a/include/common.h b/include/common.h index aea1f67..4774628 100644 --- a/include/common.h +++ b/include/common.h @@ -11,6 +11,9 @@ #include #include +#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 @@ -32,16 +35,16 @@ #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 diff --git a/include/ht.h b/include/ht.h index b396ce8..965986e 100644 --- a/include/ht.h +++ b/include/ht.h @@ -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 diff --git a/include/lwt.h b/include/lwt.h index 789c667..db86292 100644 --- a/include/lwt.h +++ b/include/lwt.h @@ -6,7 +6,6 @@ */ #ifndef LWT_H #define LWT_H -#include "tls.h" #ifndef ENABLE_TRACE #define TRACE(...) do { } while (0) @@ -14,25 +13,7 @@ #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 . The file should be post-processed with "sort" before viewing. void lwt_dump (const char *file_name) __attribute__ ((externally_visible)); // indicates what kind of trace messages should be included in the dump. 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 in 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 diff --git a/include/mem.h b/include/mem.h index b04602c..3e1d940 100644 --- a/include/mem.h +++ b/include/mem.h @@ -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 index a6e1dcc..0000000 --- a/include/nbd.h +++ /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 index dd3f121..0000000 --- a/include/rcu.h +++ /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 index 0000000..8d9638e --- /dev/null +++ b/include/runtime.h @@ -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 index def2bec..0000000 --- a/include/tls.h +++ /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 - -#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 diff --git a/makefile b/makefile index 1e4c1ec..1c9a3b6 100644 --- 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) diff --git a/runtime/lwt.c b/runtime/lwt.c index d7b9862..42e79bf 100644 --- a/runtime/lwt.c +++ b/runtime/lwt.c @@ -11,6 +11,22 @@ #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; + } +} diff --git a/runtime/mem.c b/runtime/mem.c index 0967c4a..c65dfb0 100644 --- a/runtime/mem.c +++ b/runtime/mem.c @@ -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; diff --git a/runtime/rcu.c b/runtime/rcu.c index dfa49c8..8378453 100644 --- a/runtime/rcu.c +++ b/runtime/rcu.c @@ -6,10 +6,8 @@ */ #include #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 #include #include +#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) { diff --git a/runtime/runtime.c b/runtime/runtime.c index ed93e8f..0731bfd 100644 --- a/runtime/runtime.c +++ b/runtime/runtime.c @@ -2,23 +2,46 @@ * Written by Josh Dybnis and released to the public domain, as explained at * http://creativecommons.org/licenses/publicdomain */ +#include #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); } diff --git a/struct/ht.c b/struct/ht.c index 54eb2e0..e3debc4 100644 --- a/struct/ht.c +++ b/struct/ht.c @@ -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 . 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 (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 (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; // 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 isn't initiallized. Occasionally the 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 is in the table. If // 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 associated with . 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); diff --git a/struct/ht_test.c b/struct/ht_test.c index 61b2bfc..e8fcc4c 100644 --- a/struct/ht_test.c +++ b/struct/ht_test.c @@ -4,10 +4,9 @@ */ #include #include +#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 diff --git a/struct/list.c b/struct/list.c index 28c15aa..2fad6ee 100644 --- a/struct/list.c +++ b/struct/list.c @@ -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 #include -#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 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: -- 2.40.0