#define TRUE 1
#define FALSE 0
+#ifdef NBD32
+#define TAG1 (1U << 31)
+#define TAG2 (1U << 30)
+#else
#define TAG1 (1ULL << 63)
#define TAG2 (1ULL << 62)
+#endif
#define TAG_VALUE(v, tag) ((v) | tag)
#define IS_TAGGED(v, tag) ((v) & tag)
#define STRIP_TAG(v, tag) ((v) & ~tag)
typedef unsigned int uint32_t;
typedef unsigned char uint8_t;
-typedef uint64_t markable_t;
+typedef size_t markable_t;
#include "lwt.h"
#endif //COMMON_H
typedef struct map_iter map_iter_t;
typedef struct map_impl map_impl_t;
+#ifdef NBD32
+typedef uint32_t map_key_t;
+typedef uint32_t map_val_t;
+#else
typedef uint64_t map_key_t;
typedef uint64_t map_val_t;
+#endif
map_t * map_alloc (const map_impl_t *map_impl, const datatype_t *key_type);
map_val_t map_get (map_t *map, map_key_t key);
void map_free (map_t *map);
map_iter_t * map_iter_begin (map_t *map, map_key_t key);
-map_val_t map_iter_next (map_iter_t *iter, map_key_t *key);
+map_val_t map_iter_next (map_iter_t *iter, map_key_t *key);
void map_iter_free (map_iter_t *iter);
/////////////////////////////////////////////////////////////////////////////////////
#define CAS_EXPECT_WHATEVER (-2)
typedef void * (*map_alloc_t) (const datatype_t *);
-typedef map_val_t (*map_cas_t) (map_impl_t *, map_key_t , map_val_t, map_val_t);
-typedef map_val_t (*map_get_t) (map_impl_t *, map_key_t );
-typedef map_val_t (*map_remove_t) (map_impl_t *, map_key_t );
-typedef map_val_t (*map_count_t) (map_impl_t *);
-typedef void (*map_print_t) (map_impl_t *);
-typedef void (*map_free_t) (map_impl_t *);
-
-typedef map_iter_t * (*map_iter_begin_t) (map_impl_t *, map_key_t );
+typedef map_val_t (*map_cas_t) (void *, map_key_t , map_val_t, map_val_t);
+typedef map_val_t (*map_get_t) (void *, map_key_t );
+typedef map_val_t (*map_remove_t) (void *, map_key_t );
+typedef size_t (*map_count_t) (void *);
+typedef void (*map_print_t) (void *);
+typedef void (*map_free_t) (void *);
+
+typedef map_iter_t * (*map_iter_begin_t) (void *, map_key_t);
typedef map_val_t (*map_iter_next_t) (map_iter_t *, map_key_t *);
typedef void (*map_iter_free_t) (map_iter_t *);
void txn_abort (txn_t *txn);
txn_state_e txn_commit (txn_t *txn);
-uint64_t txn_map_get (txn_t *txn, map_key_t key);
+map_val_t txn_map_get (txn_t *txn, map_key_t key);
void txn_map_set (txn_t *txn, map_key_t key, map_val_t value);
#endif//TXN_H
# Makefile for building programs with whole-program interfile optimization
###################################################################################################
OPT := -fwhole-program -combine -03 #-DNDEBUG
-CFLAGS := -g -Wall -Werror -std=c99 -m64 $(OPT) #-DENABLE_TRACE
+CFLAGS := -g -Wall -Werror -std=c99 $(OPT) -m64 #-DNBD32 #-DENABLE_TRACE
INCS := $(addprefix -I, include)
TESTS := output/map_test1 output/map_test2 output/txn_test
EXES := $(TESTS)
#include "mem.h"
#include "hashtable.h"
+#ifndef NBD32
#define GET_PTR(x) ((void *)((x) & MASK(48))) // low-order 48 bits is a pointer to a nstring_t
+#else
+#define GET_PTR(x) ((void *)(x))
+#endif
typedef struct entry {
map_key_t key;
return ent;
}
} else {
+#ifndef NBD32
// The key in <ent> is made up of two parts. The 48 low-order bits are a pointer. The
// high-order 16 bits are taken from the hash. The bits from the hash are used as a
// quick check to rule out non-equal keys without doing a complete compare.
if ((key_hash >> 16) == (ent_key >> 48)) {
+#endif
if (hti->ht->key_type->cmp(GET_PTR(ent_key), (void *)key) == 0) {
TRACE("h1", "hti_lookup: found entry %p with key %p", ent, GET_PTR(ent_key));
return ent;
+#ifndef NBD32
}
+#endif
}
}
}
assert(ht1->next);
assert(ht2);
assert(ht1_ent >= ht1->table && ht1_ent < ht1->table + (1 << ht1->scale));
+#ifndef NBD32
assert(key_hash == 0 || ht1->ht->key_type == NULL || (key_hash >> 16) == (ht1_ent->key >> 48));
+#endif
map_val_t ht1_ent_val = ht1_ent->val;
if (EXPECT_FALSE(ht1_ent_val == COPIED_VALUE)) {
printf("hti:%p scale:%u count:%d copied:%d\n", hti, hti->scale, hti->count, hti->num_entries_copied);
for (int i = 0; i < (1 << hti->scale); ++i) {
volatile entry_t *ent = hti->table + i;
- printf("[0x%x] 0x%llx:0x%llx\n", i, (uint64_t)ent->key, ent->val);
+ printf("[0x%x] 0x%llx:0x%llx\n", i, (uint64_t)ent->key, (uint64_t)ent->val);
if (i > 30) {
printf("...\n");
break;
d = ll->key_type->cmp((void *)item->key, (void *)key);
}
- if (next != DOES_NOT_EXIST && GET_NODE(next)->key < item->key) {
- lwt_halt();
- assert(0);
- }
-
// If we reached the key (or passed where it should be), we found the right predesssor
if (d >= 0) {
if (pred_ptr != NULL) {
if (!found) {
// There was not an item in the list that matches the key.
- if (EXPECT_FALSE((int64_t)expectation > 0 || expectation == CAS_EXPECT_EXISTS)) {
+ if (EXPECT_FALSE(expectation != CAS_EXPECT_DOES_NOT_EXIST && expectation != CAS_EXPECT_WHATEVER)) {
TRACE("l1", "ll_cas: the expectation was not met, the list was not changed", 0, 0);
return DOES_NOT_EXIST; // failure
}
- ASSERT(expectation == CAS_EXPECT_DOES_NOT_EXIST || expectation == CAS_EXPECT_WHATEVER);
-
// Create a new item and insert it into the list.
TRACE("l2", "ll_cas: attempting to insert item between %p and %p", pred, pred->next);
map_key_t new_key = ll->key_type == NULL ? key : (map_key_t)ll->key_type->clone((void *)key);
node_t *item = STRIP_MARK(next);
if (item == NULL)
break;
- printf("%p:0x%llx ", item, item->key);
+ printf("%p:0x%llx ", item, (uint64_t)item->key);
fflush(stdout);
if (i++ > 30) {
printf("...");
ll_iter_t *ll_iter_begin (list_t *ll, map_key_t key) {
ll_iter_t *iter = (ll_iter_t *)nbd_malloc(sizeof(ll_iter_t));
- find_pred(NULL, &iter->next, ll, key, FALSE);
+ if (key != DOES_NOT_EXIST) {
+ find_pred(NULL, &iter->next, ll, key, FALSE);
+ } else {
+ iter->next = GET_NODE(ll->head->next);
+ }
return iter;
}
if (old_item == NULL) {
// There was not an item in the skiplist that matches the key.
- if (EXPECT_FALSE((int64_t)expectation > 0 || expectation == CAS_EXPECT_EXISTS)) {
+ if (EXPECT_FALSE(expectation != CAS_EXPECT_DOES_NOT_EXIST && expectation != CAS_EXPECT_WHATEVER)) {
TRACE("l1", "sl_cas: the expectation was not met, the skiplist was not changed", 0, 0);
return DOES_NOT_EXIST; // failure
}
- ASSERT(expectation == CAS_EXPECT_DOES_NOT_EXIST || expectation == CAS_EXPECT_WHATEVER);
-
// First insert <new_item> into the bottom level.
TRACE("s3", "sl_cas: attempting to insert item between %p and %p", preds[0], nexts[0]);
map_key_t new_key = sl->key_type == NULL ? key : (map_key_t)sl->key_type->clone((void *)key);
int i = 0;
while (item) {
int is_marked = HAS_MARK(item->next[0]);
- printf("%s%p:0x%llx ", is_marked ? "*" : "", item, (map_key_t)item->key);
+ printf("%s%p:0x%llx ", is_marked ? "*" : "", item, (uint64_t)item->key);
if (item != sl->head) {
printf("[%d]", item->top_level);
} else {
sl_iter_t *sl_iter_begin (skiplist_t *sl, map_key_t key) {
sl_iter_t *iter = (sl_iter_t *)nbd_malloc(sizeof(sl_iter_t));
- find_preds(NULL, &iter->next, 0, sl, key, FALSE);
+ if (key != DOES_NOT_EXIST) {
+ find_preds(NULL, &iter->next, 0, sl, key, FALSE);
+ } else {
+ iter->next = GET_NODE(sl->head->next[0]);
+ }
return iter;
}
do {} while (wait_);
#ifdef TEST_STRING_KEYS
- nstring_t *key_str = ns_alloc(10);
+ nstring_t *key_str = ns_alloc(10);
#endif
for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) {
unsigned r = nbd_rand();
int key = r & 0xF;
#ifdef TEST_STRING_KEYS
- key_str->len = sprintf(key_str->data, "%llX", key) + 1;
+ key_str->len = sprintf(key_str->data, "%X", key) + 1;
assert(key_str->len <= 10);
if (r & (1 << 8)) {
map_set(map_, (map_key_t)key_str, 1);
return -1;
}
- num_threads_ = 2;
+ num_threads_ = 1;
if (argc == 2)
{
errno = 0;
#include "skiplist.h"
#include "hashtable.h"
#include "lwt.h"
+#include "mem.h"
#define ASSERT_EQUAL(x, y) CuAssertIntEquals(tc, x, y)
#ifdef TEST_STRING_KEYS
map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);
- nstring_t *k1 = ns_alloc(3); strcpy(k1->data, "k1");
- nstring_t *k2 = ns_alloc(3); strcpy(k1->data, "k2");
- nstring_t *k3 = ns_alloc(3); strcpy(k1->data, "k3");
- nstring_t *k4 = ns_alloc(3); strcpy(k1->data, "k4");
+ nstring_t *s1 = ns_alloc(3); strcpy(s1->data, "k1");
+ nstring_t *s2 = ns_alloc(3); strcpy(s2->data, "k2");
+ nstring_t *s3 = ns_alloc(3); strcpy(s3->data, "k3");
+ nstring_t *s4 = ns_alloc(3); strcpy(s4->data, "k4");
+ map_key_t k1 = (map_key_t)s1;
+ map_key_t k2 = (map_key_t)s2;
+ map_key_t k3 = (map_key_t)s3;
+ map_key_t k4 = (map_key_t)s4;
#else
map_t *map = map_alloc(map_type_, NULL);
map_key_t k1 = (map_key_t)1;
rcu_update(); // In a quiecent state.
#ifdef TEST_STRING_KEYS
- nbd_free(k1); nbd_free(k2); nbd_free(k3); nbd_free(k4);
+ nbd_free(s1); nbd_free(s2); nbd_free(s3); nbd_free(s4);
#endif
}
SYNC_ADD(wd->wait, -1);
do { } while (*wd->wait); // wait for all workers to be ready
-#ifdef TEST_STRING_KEYS
- nstring_t *key = ns_alloc(9);
-#else
map_key_t key;
+#ifdef TEST_STRING_KEYS
+ nstring_t *s = ns_alloc(9);
+ key = (map_key_t)s;
#endif
for (int j = 0; j < 10; ++j) {
for (int i = d+1; i < iters; i+=2) {
#ifdef TEST_STRING_KEYS
- memset(key->data, 0, key->len);
- snprintf(key->data, key->len, "%llu", i);
+ s->len = 1 + snprintf(s->data, 9, "%u", i);
#else
key = (map_key_t)i;
#endif
}
for (int i = d+1; i < iters; i+=2) {
#ifdef TEST_STRING_KEYS
- memset(key->data, 0, key->len);
- snprintf(key->data, key->len, "%u", i);
+ s->len = 1 + snprintf(s->data, 9, "%u", i);
#else
key = (map_key_t)i;
#endif
rcu_update(); // In a quiecent state.
}
}
+#ifdef TEST_STRING_KEYS
+ nbd_free(s);
+#endif
return NULL;
}
void basic_iteration_test (CuTest* tc) {
#ifdef TEST_STRING_KEYS
map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);
- nstring_t *k1 = ns_alloc(3); strcpy(k1->data, "k1");
- nstring_t *k2 = ns_alloc(3); strcpy(k1->data, "k2");
+ nstring_t *s1 = ns_alloc(3); strcpy(s1->data, "k1");
+ nstring_t *s2 = ns_alloc(3); strcpy(s2->data, "k2");
+ map_key_t k1 = (map_key_t)s1;
+ map_key_t k2 = (map_key_t)s2;
nstring_t *x_k;
nstring_t *y_k;
#else
map_val_t x_v, y_v;
map_iter_t *iter = map_iter_begin(map, 0);
- x_v = map_iter_next(iter, &x_k);
- y_v = map_iter_next(iter, &y_k);
+ x_v = map_iter_next(iter, (map_key_t *)&x_k);
+ y_v = map_iter_next(iter, (map_key_t *)&y_k);
ASSERT_EQUAL( DOES_NOT_EXIST, map_iter_next(iter, NULL) );
map_iter_free(iter);
#ifdef TEST_STRING_KEYS
- ASSERT_EQUAL( TRUE, (ns_cmp(x_k, k1) == 0 && x_v == 1) || (ns_cmp(y_k, k1) == 0 && y_v == 1) );
- ASSERT_EQUAL( TRUE, (ns_cmp(x_k, k2) == 0 && x_v == 2) || (ns_cmp(y_k, k2) == 0 && y_v == 2) );
- nbd_free(k1);
- nbd_free(k2);
+ ASSERT_EQUAL( TRUE, (ns_cmp(x_k, s1) == 0 && x_v == 1) || (ns_cmp(y_k, s1) == 0 && y_v == 1) );
+ ASSERT_EQUAL( TRUE, (ns_cmp(x_k, s2) == 0 && x_v == 2) || (ns_cmp(y_k, s2) == 0 && y_v == 2) );
+ nbd_free(s1);
+ nbd_free(s2);
#else
ASSERT_EQUAL( TRUE, (x_k == k1 && x_v == 1) || (y_k == k1 && y_v == 1) );
ASSERT_EQUAL( TRUE, (x_k == k2 && x_v == 2) || (y_k == k2 && y_v == 2) );
#ifdef TEST_STRING_KEYS
map_t *map = map_alloc(map_type_, &DATATYPE_NSTRING);
- nstring_t *key = ns_alloc(9);
- nstring_t *k3 = ns_alloc(3); strcpy(k1->data, "k3");
- nstring_t *k4 = ns_alloc(3); strcpy(k1->data, "k4");
+ nstring_t *s = ns_alloc(9);
+ nstring_t *s3 = ns_alloc(3); strcpy(s3->data, "k3");
+ nstring_t *s4 = ns_alloc(3); strcpy(s4->data, "k4");
+ map_key_t k3 = (map_key_t)s3;
+ map_key_t k4 = (map_key_t)s4;
+ map_key_t key = (map_key_t)s;
#else
map_t *map = map_alloc(map_type_, NULL);
map_key_t k3 = (map_key_t)3;
map_key_t key;
#endif
- for (size_t i = 1; i <= n; ++i) {
+ for (int i = 1; i <= n; ++i) {
#ifdef TEST_STRING_KEYS
- memset(key->data, 0, key->len);
- snprintf(key->data, key->len, "k%llu", i);
+ s->len = 1 + snprintf(s->data, 9, "k%d", i);
#else
key = (map_key_t)i;
#endif
ASSERT_EQUAL(n*(n+1)/2 - (3+4), sum);
#ifdef TEST_STRING_KEYS
- nbd_free(key);
+ nbd_free(s);
#endif
}
+ optimize integer keys
+ ht_print()
+ iterators
++ 32 bit support
memory manangement
------------------
- make rcu yield when its buffer gets full instead of throwing an assert
- alternate memory reclamation schemes: hazard pointers and/or reference counting
- verify the key management in list, skiplist, and hashtable
+- seperate nbd_malloc/nbd_free into general purpose malloc/free replacement
quality
-------
features
--------
-- a version of hashtable for 32bit keys and values
-- verify correctness on 32 bit platforms
- allow values of 0 to be inserted into maps (change DOES_NOT_EXIST to something else)
-- seperate nbd_malloc/nbd_free into general purpose malloc/free replacement
#define INITIAL_WRITES_SIZE 4
typedef struct update_rec update_t;
+typedef map_key_t version_t;
struct update_rec {
- uint64_t version;
+ version_t version;
map_val_t value;
map_val_t next; // an earlier update
};
} write_rec_t;
struct txn {
- uint64_t rv;
- uint64_t wv;
+ version_t rv;
+ version_t wv;
map_t *map;
write_rec_t *writes;
size_t writes_size;
static txn_state_e txn_validate (txn_t *txn);
-static uint64_t version_ = 1;
+static version_t version_ = 1;
static skiplist_t *active_ = NULL;
case TXN_VALIDATING:
if (txn->wv == UNDETERMINED_VERSION) {
- uint64_t wv = SYNC_ADD(&version_, 1);
+ version_t wv = SYNC_ADD(&version_, 1);
SYNC_CAS(&txn->wv, UNDETERMINED_VERSION, wv);
}
do {
txn->rv = version_;
- uint64_t old_count;
- uint64_t temp = 0;
+ unsigned old_count;
+ unsigned temp = 0;
do {
old_count = temp;
- temp = (uint64_t)sl_cas(active_, (map_key_t)txn->rv, old_count, old_count + 1);
+ temp = sl_cas(active_, txn->rv, old_count, old_count + 1);
} while (temp != old_count);
if (txn->rv == version_)
txn_state_e state = txn_validate(txn);
// Detach <txn> from its updates.
- uint64_t wv = (txn->state == TXN_ABORTED) ? ABORTED_VERSION : txn->wv;
+ version_t wv = (txn->state == TXN_ABORTED) ? ABORTED_VERSION : txn->wv;
int i;
for (i = 0; i < txn->writes_count; ++i) {
update_t *update = (update_t *)txn->writes[i].rec;
}
// Lower the reference count for <txn>'s read version
- uint64_t temp = 2;
- uint64_t old_count;
+ unsigned temp = 2;
+ unsigned old_count;
do {
old_count = temp;
temp = sl_cas(active_, (map_key_t)txn->rv, old_count, old_count - 1);
map_val_t value = update->value;
// collect some garbage
- uint64_t min_active_version = UNDETERMINED_VERSION;
+ version_t min_active_version = UNDETERMINED_VERSION;
update_t *next_update = NULL;
if (IS_TAGGED(update->next, TAG2)) {
next_update = (update_t *)STRIP_TAG(update->next, TAG2);
- min_active_version = (uint64_t)sl_min_key(active_);
+ min_active_version = (version_t)sl_min_key(active_);
if (next_update->version < min_active_version) {
// <next_update> (and all update records following it [execpt if it is aborted]) is old enough that it is
// not visible to any active transaction. We can safely free it.
update_t *temp = next_update;
while (temp->version == ABORTED_VERSION) {
assert(!IS_TAGGED(temp->version, TAG1));
- uint64_t next = next_update->next;
+ map_val_t next = next_update->next;
if (!IS_TAGGED(next, TAG2))
break;
// free <next> and all the update records following it
temp = next_update;
while (1) {
- uint64_t next = SYNC_SWAP(&temp->next, DOES_NOT_EXIST);
+ map_val_t next = SYNC_SWAP(&temp->next, DOES_NOT_EXIST);
// if we find ourself in a race just back off and let the other thread take care of it
if (next == DOES_NOT_EXIST)
// There is no need for an update record.
if (next_update == NULL && val == newest_val) {
if (min_active_version == UNDETERMINED_VERSION) {
- min_active_version = (uint64_t)sl_min_key(active_);
+ min_active_version = (version_t)sl_min_key(active_);
}
if (update->version <= min_active_version) {
if (map_cas(txn->map, key, TAG_VALUE(val, TAG2), value) == TAG_VALUE(val, TAG2)) {
// create a new update record
update_t *update = alloc_update_rec();
update->value = value;
- update->version = TAG_VALUE((uint64_t)txn, TAG1);
+ update->version = TAG_VALUE((version_t)txn, TAG1);
// push the new update record onto <key>'s update list
- uint64_t old_update;
+ map_val_t old_update;
do {
old_update = map_get(txn->map, key);
update->next = old_update;
- } while (map_cas(txn->map, key, old_update, TAG_VALUE((uint64_t)update, TAG2)) != old_update);
+ } while (map_cas(txn->map, key, old_update, TAG_VALUE((map_val_t)update, TAG2)) != old_update);
// add <key> to the write set for commit-time validation
if (txn->writes_count == txn->writes_size) {