#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
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
*/
#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
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
*/
#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
+++ /dev/null
-/*
- * 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
+++ /dev/null
-/*
- * 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
--- /dev/null
+/*
+ * 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
+++ /dev/null
-/*
- * 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
# 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)
#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] = {};
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;
+ }
+}
// 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;
*/
#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
}
#ifdef MAKE_rcu_test
-#include <pthread.h>
#include <errno.h>
#include <stdio.h>
+#include "runtime.h"
#define NUM_ITERATIONS 10000000
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);
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) {
* 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);
}
#include "ht.h"
#include "murmur.h"
#include "mem.h"
-#include "rcu.h"
#define COPIED_VALUE (-1)
#define TOMBSTONE STRIP_TAG(COPIED_VALUE)
#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 {
} 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) {
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
}
}
// 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
}
// 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);
}
// 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);
}
//
-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;
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);
}
//
-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);
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) {
// 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);
*/
#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"
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
int main (void) {
nbd_init();
- nbd_thread_init(0);
-
//lwt_set_trace_level("h4");
// Create and run test suite
#include "common.h"
#include "lwt.h"
-#include "rcu.h"
#include "mem.h"
#define NUM_ITERATIONS 10000000
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);
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);
} 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 {
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);
return item;
}
-void list_print (list_t *list)
-{
+void list_print (list_t *list) {
node_t *item;
item = list->head;
while (item) {
#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();
return NULL;
}
-int main (int argc, char **argv)
-{
+int main (int argc, char **argv) {
nbd_init();
//lwt_set_trace_level("m0l0");
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; }
}
+++ /dev/null
-!_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: