typedef unsigned int uint32_t;
typedef unsigned char uint8_t;
+typedef uint64_t markable_t;
+
#include "lwt.h"
#endif //COMMON_H
typedef struct ht_iter ht_iter_t;
hashtable_t * ht_alloc (const datatype_t *key_type);
-uint64_t ht_cas (hashtable_t *ht, map_key_t key, uint64_t expected_val, uint64_t val);
-uint64_t ht_get (hashtable_t *ht, map_key_t key);
-uint64_t ht_remove (hashtable_t *ht, map_key_t key);
-uint64_t ht_count (hashtable_t *ht);
-void ht_print (hashtable_t *ht);
-void ht_free (hashtable_t *ht);
+map_val_t ht_cas (hashtable_t *ht, map_key_t key, map_val_t expected_val, map_val_t val);
+map_val_t ht_get (hashtable_t *ht, map_key_t key);
+map_val_t ht_remove (hashtable_t *ht, map_key_t key);
+size_t ht_count (hashtable_t *ht);
+void ht_print (hashtable_t *ht);
+void ht_free (hashtable_t *ht);
ht_iter_t * ht_iter_begin (hashtable_t *ht, map_key_t key);
-uint64_t ht_iter_next (ht_iter_t *iter, map_key_t *key_ptr);
+map_val_t ht_iter_next (ht_iter_t *iter, map_key_t *key_ptr);
void ht_iter_free (ht_iter_t *iter);
static const map_impl_t ht_map_impl = {
map_val_t ll_cas (list_t *ll, map_key_t key, map_val_t expected_val, map_val_t new_val);
map_val_t ll_lookup (list_t *ll, map_key_t key);
map_val_t ll_remove (list_t *ll, map_key_t key);
-map_val_t ll_count (list_t *ll);
+size_t ll_count (list_t *ll);
void ll_print (list_t *ll);
void ll_free (list_t *ll);
map_key_t ll_min_key (list_t *sl);
map_val_t sl_cas (skiplist_t *sl, map_key_t key, map_val_t expected_val, map_val_t new_val);
map_val_t sl_lookup (skiplist_t *sl, map_key_t key);
map_val_t sl_remove (skiplist_t *sl, map_key_t key);
-map_val_t sl_count (skiplist_t *sl);
+size_t sl_count (skiplist_t *sl);
void sl_print (skiplist_t *sl);
void sl_free (skiplist_t *sl);
map_key_t sl_min_key (skiplist_t *sl);
gcc $(CFLAGS:-combine:) $(INCS) -MM -MT $@ $($*_SRCS) > $@.d
gcc $(CFLAGS) $(INCS) -o $@ $($*_SRCS)
+asm: $(addsuffix .s, $(EXES))
+
+$(addsuffix .s, $(EXES)): output/%.s : output/%.d makefile
+ gcc $(CFLAGS:-combine:) $(INCS) -MM -MT $@ $($*_SRCS) > output/$*.d
+ gcc $(CFLAGS) $(INCS) -S -o $@.temp $($*_SRCS)
+ grep -v "^L[BFM]\|^LCF" $@.temp > $@
+ rm $@.temp
+
###################################################################################################
# tags file for vi
###################################################################################################
-include $(addsuffix .d, $(EXES))
-.PHONY: clean test tags
+.PHONY: clean test tags asm
#include "mem.h"
#include "hashtable.h"
-#define GET_PTR(x) ((void *)(size_t)((x) & MASK(48))) // low-order 48 bits is a pointer to a nstring_t
+#define GET_PTR(x) ((void *)((x) & MASK(48))) // low-order 48 bits is a pointer to a nstring_t
typedef struct entry {
- uint64_t key;
+ map_key_t key;
map_val_t val;
} entry_t;
for (int j = 0; j < ENTRIES_PER_BUCKET; ++j) {
volatile entry_t *ent = bucket + ((ndx + j) & (ENTRIES_PER_BUCKET-1));
- uint64_t ent_key = ent->key;
+ map_key_t ent_key = ent->key;
if (ent_key == DOES_NOT_EXIST) {
TRACE("h1", "hti_lookup: entry %p for key %p is empty", ent,
(hti->ht->key_type == NULL) ? (void *)ent_key : GET_PTR(ent_key));
// Compare <key> with the key in the entry.
if (EXPECT_TRUE(hti->ht->key_type == NULL)) {
// fast path for integer keys
- if (ent_key == (uint64_t)key) {
+ if (ent_key == key) {
TRACE("h1", "hti_lookup: found entry %p with key %p", ent, ent_key);
return ent;
}
// 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)) {
- if (hti->ht->key_type->cmp(GET_PTR(ent_key), (void *)(size_t)key) == 0) {
+ 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;
}
TRACE("h0", "hti_start_copy(hti %p scale %llu)", hti, hti->scale);
// heuristics to determine the size of the new table
- uint64_t count = ht_count(hti->ht);
+ size_t count = ht_count(hti->ht);
unsigned int new_scale = hti->scale;
new_scale += (count > (1 << (new_scale - 2))); // double size if more than 1/4 full
new_scale += (count > (1 << (new_scale - 2))); // double size again if more than 1/2 full
}
// Install the key in the new table.
- uint64_t ht1_ent_key = ht1_ent->key;
- map_key_t key = (ht1->ht->key_type == NULL) ? (map_key_t)ht1_ent_key : (map_key_t)(size_t)GET_PTR(ht1_ent_key);
+ map_key_t ht1_ent_key = ht1_ent->key;
+ map_key_t key = (ht1->ht->key_type == NULL) ? (map_key_t)ht1_ent_key : (map_key_t)GET_PTR(ht1_ent_key);
// The old table's dead entries don't need to be copied to the new table, but their keys need to be freed.
assert(COPIED_VALUE == TAG_VALUE(TOMBSTONE, TAG1));
if (ht1_ent_val == TOMBSTONE) {
TRACE("h1", "hti_copy_entry: entry %p old value was deleted, now freeing key %p", ht1_ent, key);
if (EXPECT_FALSE(ht1->ht->key_type != NULL)) {
- nbd_defer_free((void *)(size_t)key);
+ nbd_defer_free((void *)key);
}
return TRUE;
}
if (key_hash == 0) {
key_hash = (ht1->ht->key_type == NULL)
? murmur32_8b(ht1_ent_key)
- : ht1->ht->key_type->hash((void *)(size_t)key);
+ : ht1->ht->key_type->hash((void *)key);
}
int ht2_ent_is_empty;
}
if (ht2_ent_is_empty) {
- uint64_t old_ht2_ent_key = SYNC_CAS(&ht2_ent->key, DOES_NOT_EXIST, ht1_ent_key);
+ map_key_t old_ht2_ent_key = SYNC_CAS(&ht2_ent->key, DOES_NOT_EXIST, ht1_ent_key);
if (old_ht2_ent_key != DOES_NOT_EXIST) {
TRACE("h0", "hti_copy_entry: lost race to CAS key %p into new entry; found %p",
ht1_ent_key, old_ht2_ent_key);
return DOES_NOT_EXIST;
// Allocate <new_key>.
- uint64_t new_key = (uint64_t)((hti->ht->key_type == NULL) ? key : (map_key_t)(size_t)hti->ht->key_type->clone((void *)(size_t)key));
+ map_key_t new_key = (hti->ht->key_type == NULL)
+ ? (map_key_t)key
+ : (map_key_t)hti->ht->key_type->clone((void *)key);
if (EXPECT_FALSE(hti->ht->key_type != NULL)) {
// Combine <new_key> pointer with bits from its hash
new_key = ((uint64_t)(key_hash >> 16) << 48) | new_key;
}
// CAS the key into the table.
- uint64_t old_ent_key = SYNC_CAS(&ent->key, DOES_NOT_EXIST, new_key);
+ map_key_t old_ent_key = SYNC_CAS(&ent->key, DOES_NOT_EXIST, new_key);
// Retry if another thread stole the entry out from under us.
if (old_ent_key != DOES_NOT_EXIST) {
//
map_val_t ht_get (hashtable_t *ht, map_key_t key) {
- uint32_t hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash((void *)(size_t)key);
+ uint32_t hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash((void *)key);
return hti_get(ht->hti, key, hash);
}
// returns TRUE if copy is done
int hti_help_copy (hti_t *hti) {
volatile entry_t *ent;
- uint64_t limit;
- uint64_t total_copied = hti->num_entries_copied;
- uint64_t num_copied = 0;
- uint64_t x = hti->copy_scan;
+ size_t limit;
+ size_t total_copied = hti->num_entries_copied;
+ size_t num_copied = 0;
+ size_t x = hti->copy_scan;
TRACE("h1", "ht_cas: help copy. scan is %llu, size is %llu", x, 1<<hti->scale);
if (total_copied != (1 << hti->scale)) {
}
map_val_t old_val;
- uint32_t key_hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash((void *)(size_t)key);
+ uint32_t key_hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash((void *)key);
while ((old_val = hti_cas(hti, key, key_hash, expected_val, new_val)) == COPIED_VALUE) {
assert(hti->next);
hti = hti->next;
map_val_t ht_remove (hashtable_t *ht, map_key_t key) {
hti_t *hti = ht->hti;
map_val_t val;
- uint32_t key_hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash((void *)(size_t)key);
+ uint32_t key_hash = (ht->key_type == NULL) ? murmur32_8b((uint64_t)key) : ht->key_type->hash((void *)key);
do {
val = hti_cas(hti, key, key_hash, CAS_EXPECT_WHATEVER, DOES_NOT_EXIST);
if (val != COPIED_VALUE)
}
// Returns the number of key-values pairs in <ht>
-uint64_t ht_count (hashtable_t *ht) {
+size_t ht_count (hashtable_t *ht) {
hti_t *hti = ht->hti;
- uint64_t count = 0;
+ size_t count = 0;
while (hti) {
count += hti->count;
hti = hti->next;
volatile entry_t *ent;
map_key_t key;
map_val_t val;
- uint64_t table_size = (1 << iter->hti->scale);
+ size_t table_size = (1 << iter->hti->scale);
do {
iter->idx++;
if (iter->idx == table_size) {
return DOES_NOT_EXIST;
}
ent = &iter->hti->table[iter->idx];
- key = (iter->hti->ht->key_type == NULL) ? (map_key_t)ent->key : (map_key_t)(size_t)GET_PTR(ent->key);
+ key = (iter->hti->ht->key_type == NULL) ? (map_key_t)ent->key : (map_key_t)GET_PTR(ent->key);
val = ent->val;
} while (key == DOES_NOT_EXIST || val == DOES_NOT_EXIST || val == TOMBSTONE);
if (val == COPIED_VALUE) {
uint32_t hash = (iter->hti->ht->key_type == NULL)
? murmur32_8b((uint64_t)key)
- : iter->hti->ht->key_type->hash((void *)(size_t)key);
+ : iter->hti->ht->key_type->hash((void *)key);
val = hti_get(iter->hti->next, (map_key_t)ent->key, hash);
}
#include "mem.h"
typedef struct node {
- map_key_t key;
- map_val_t val;
- uint64_t next; // next node
+ map_key_t key;
+ map_val_t val;
+ markable_t next; // next node
} node_t;
struct ll_iter {
const datatype_t *key_type;
};
+// Marking the <next> field of a node logically removes it from the list
+#define MARK_NODE(x) TAG_VALUE((markable_t)(x), TAG1)
+#define HAS_MARK(x) (IS_TAGGED((x), TAG1) == TAG1)
+#define GET_NODE(x) ((node_t *)(x))
+#define STRIP_MARK(x) ((node_t *)STRIP_TAG((x), TAG1))
+
static node_t *node_alloc (map_key_t key, map_val_t val) {
node_t *item = (node_t *)nbd_malloc(sizeof(node_t));
item->key = key;
}
void ll_free (list_t *ll) {
- node_t *item = (node_t *)(size_t)ll->head->next; // the head can't be tagged
- while (item) {
- node_t *next = (node_t *)(size_t)STRIP_TAG(item->next, TAG1);
+ node_t *item = STRIP_MARK(ll->head->next);
+ while (item != NULL) {
+ node_t *next = STRIP_MARK(item->next);
nbd_free(item);
item = next;
}
}
-uint64_t ll_count (list_t *ll) {
- uint64_t count = 0;
- node_t *item = (node_t *)(size_t)ll->head->next;
+size_t ll_count (list_t *ll) {
+ size_t count = 0;
+ node_t *item = STRIP_MARK(ll->head->next);
while (item) {
- if (!IS_TAGGED(item->next, TAG1)) {
+ if (!HAS_MARK(item->next)) {
count++;
}
- item = (node_t *)(size_t)STRIP_TAG(item->next, TAG1);
+ item = STRIP_MARK(item->next);
}
return count;
}
static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, map_key_t key, int help_remove) {
node_t *pred = ll->head;
- node_t *item = (node_t *)(size_t)pred->next;
+ node_t *item = GET_NODE(pred->next);
TRACE("l2", "find_pred: searching for key %p in list (head is %p)", key, pred);
while (item != NULL) {
- uint64_t next = item->next;
+ markable_t next = item->next;
- // A tag means an item is logically removed but not physically unlinked yet.
- while (EXPECT_FALSE(IS_TAGGED(next, TAG1))) {
+ // A mark means the node is logically removed but not physically unlinked yet.
+ while (EXPECT_FALSE(HAS_MARK(next))) {
// Skip over logically removed items.
if (!help_remove) {
- item = (node_t *)(size_t)STRIP_TAG(item->next, TAG1);
+ item = STRIP_MARK(item->next);
if (EXPECT_FALSE(item == NULL))
break;
TRACE("l3", "find_pred: skipping marked item %p (next is %p)", item, next);
// Unlink logically removed items.
TRACE("l3", "find_pred: unlinking marked item %p next is %p", item, next);
- uint64_t other = SYNC_CAS(&pred->next, (uint64_t)(size_t)item, STRIP_TAG(next, TAG1));
- if (other == (uint64_t)(size_t)item) {
+ markable_t other = SYNC_CAS(&pred->next, item, STRIP_MARK(next));
+ if (other == (markable_t)item) {
TRACE("l2", "find_pred: unlinked item %p from pred %p", item, pred);
- item = (node_t *)(size_t)STRIP_TAG(next, TAG1);
+ item = STRIP_MARK(next);
next = (item != NULL) ? item->next : DOES_NOT_EXIST;
TRACE("l3", "find_pred: now current item is %p next is %p", item, next);
// The thread that completes the unlink should free the memory.
+ node_t *unlinked = GET_NODE(other);
if (ll->key_type != NULL) {
- nbd_defer_free((void *)(size_t)((node_t *)(size_t)other)->key);
+ nbd_defer_free((void *)unlinked->key);
}
- nbd_defer_free(((node_t *)(size_t)other));
+ nbd_defer_free(unlinked);
} else {
TRACE("l2", "find_pred: lost a race to unlink item %p from pred %p", item, pred);
TRACE("l2", "find_pred: pred's link changed to %p", other, 0);
- if (IS_TAGGED(other, TAG1))
+ if (HAS_MARK(other))
return find_pred(pred_ptr, item_ptr, ll, key, help_remove); // retry
- item = (node_t *)(size_t)other;
+ item = GET_NODE(other);
next = (item != NULL) ? item->next : DOES_NOT_EXIST;
}
}
int d;
if (EXPECT_TRUE(ll->key_type == NULL)) {
- d = (uint64_t)item->key - (uint64_t)key;
+ d = item->key - key;
} else {
- d = ll->key_type->cmp((void *)(size_t)item->key, (void *)(size_t)key);
+ d = ll->key_type->cmp((void *)item->key, (void *)key);
}
- if (next != DOES_NOT_EXIST && ((node_t *)next)->key < item->key) {
+ if (next != DOES_NOT_EXIST && GET_NODE(next)->key < item->key) {
lwt_halt();
assert(0);
}
}
pred = item;
- item = (node_t *)(size_t)next;
+ item = GET_NODE(next);
}
// <key> is not in <ll>.
// 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)(size_t)ll->key_type->clone((void *)(size_t)key);
+ map_key_t new_key = ll->key_type == NULL ? key : (map_key_t)ll->key_type->clone((void *)key);
node_t *new_item = node_alloc(new_key, new_val);
- uint64_t next = new_item->next = (uint64_t)(size_t)old_item;
- uint64_t other = SYNC_CAS(&pred->next, next, new_item);
+ markable_t next = new_item->next = (markable_t)old_item;
+ markable_t other = SYNC_CAS(&pred->next, next, new_item);
if (other == next) {
TRACE("l1", "ll_cas: successfully inserted new item %p", new_item, 0);
return DOES_NOT_EXIST; // success
// Lost a race. Failed to insert the new item into the list.
TRACE("l1", "ll_cas: lost a race. CAS failed. expected pred's link to be %p but found %p", next, other);
if (ll->key_type != NULL) {
- nbd_free((void *)(size_t)new_key);
+ nbd_free((void *)new_key);
}
nbd_free(new_item);
continue; // retry
}
// Mark <item> removed. If multiple threads try to remove the same item only one of them should succeed.
- uint64_t next;
- uint64_t old_next = item->next;
+ markable_t next;
+ markable_t old_next = item->next;
do {
next = old_next;
- old_next = SYNC_CAS(&item->next, next, TAG_VALUE(next, TAG1));
- if (IS_TAGGED(old_next, TAG1)) {
+ old_next = SYNC_CAS(&item->next, next, MARK_NODE(STRIP_MARK(next)));
+ if (HAS_MARK(old_next)) {
TRACE("l1", "ll_remove: lost a race -- %p is already marked for removal by another thread", item, 0);
return DOES_NOT_EXIST;
}
} while (next != old_next);
TRACE("l2", "ll_remove: logically removed item %p", item, 0);
- ASSERT(IS_TAGGED(((volatile node_t *)item)->next, TAG1));
+ ASSERT(HAS_MARK(((volatile node_t *)item)->next));
// Atomically swap out the item's value in case another thread is updating the item while we are
// removing it. This establishes which operation occurs first logically, the update or the remove.
// item logically removed for a later call (or some other thread) to physically unlink. By marking the
// item earlier, we logically removed it.
TRACE("l2", "ll_remove: unlink the item by linking its pred %p to its successor %p", pred, next);
- uint64_t other;
- if ((other = SYNC_CAS(&pred->next, (uint64_t)(size_t)item, next)) != (uint64_t)(size_t)item) {
+ markable_t other;
+ if ((other = SYNC_CAS(&pred->next, item, next)) != (markable_t)item) {
TRACE("l1", "ll_remove: unlink failed; pred's link changed from %p to %p", item, other);
return val;
}
// The thread that completes the unlink should free the memory.
if (ll->key_type != NULL) {
- nbd_defer_free((void *)(size_t)item->key);
+ nbd_defer_free((void *)item->key);
}
nbd_defer_free(item);
TRACE("l1", "ll_remove: successfully unlinked item %p from the list", item, 0);
}
void ll_print (list_t *ll) {
- uint64_t next = ll->head->next;
+ markable_t next = ll->head->next;
int i = 0;
while (next != DOES_NOT_EXIST) {
- if (IS_TAGGED(next, TAG1)) {
+ if (HAS_MARK(next)) {
printf("*");
}
- node_t *item = (node_t *)(size_t)STRIP_TAG(next, TAG1);
+ node_t *item = STRIP_MARK(next);
if (item == NULL)
break;
printf("%p:0x%llx ", item, item->key);
map_val_t ll_iter_next (ll_iter_t *iter, map_key_t *key_ptr) {
assert(iter);
node_t *item = iter->next;
- while (item != NULL && IS_TAGGED(item->next, TAG1)) {
- item = (node_t *)(size_t)STRIP_TAG(item->next, TAG1);
+ while (item != NULL && HAS_MARK(item->next)) {
+ item = STRIP_MARK(item->next);
}
if (item == NULL) {
iter->next = NULL;
return DOES_NOT_EXIST;
}
- iter->next = (node_t *)(size_t)STRIP_TAG(item->next, TAG1);
+ iter->next = STRIP_MARK(item->next);
if (key_ptr != NULL) {
*key_ptr = item->key;
}
map_key_t key;
map_val_t val;
int top_level;
- uint64_t next[];
+ markable_t next[];
} node_t;
struct sl_iter {
const datatype_t *key_type;
};
+// Marking the <next> field of a node logically removes it from the list
+#if 0
+static inline markable_t MARK_NODE(node_t * x) { return TAG_VALUE((markable_t)x, TAG1); }
+static inline int HAS_MARK(markable_t x) { return (IS_TAGGED(x, TAG1) == TAG1); }
+static inline node_t * GET_NODE(markable_t x) { assert(!HAS_MARK(x)); return (node_t *)x; }
+static inline node_t * STRIP_MARK(markable_t x) { return ((node_t *)STRIP_TAG(x, TAG1)); }
+#else
+#define MARK_NODE(x) TAG_VALUE((markable_t)(x), TAG1)
+#define HAS_MARK(x) (IS_TAGGED((x), TAG1) == TAG1)
+#define GET_NODE(x) ((node_t *)(x))
+#define STRIP_MARK(x) ((node_t *)STRIP_TAG((x), TAG1))
+#endif
+
static int random_level (void) {
unsigned r = nbd_rand();
if (r & 1)
}
void sl_free (skiplist_t *sl) {
- node_t *item = (node_t *)(size_t)sl->head->next[0];
+ node_t *item = GET_NODE(sl->head->next[0]);
while (item) {
- node_t *next = (node_t *)(size_t)STRIP_TAG(item->next[0], TAG1);
+ node_t *next = STRIP_MARK(item->next[0]);
if (sl->key_type != NULL) {
- nbd_free((void *)(size_t)item->key);
+ nbd_free((void *)item->key);
}
nbd_free(item);
item = next;
}
}
-uint64_t sl_count (skiplist_t *sl) {
- uint64_t count = 0;
- node_t *item = (node_t *)(size_t)sl->head->next[0];
+size_t sl_count (skiplist_t *sl) {
+ size_t count = 0;
+ node_t *item = GET_NODE(sl->head->next[0]);
while (item) {
- if (!IS_TAGGED(item->next[0], TAG1)) {
+ if (!HAS_MARK(item->next[0])) {
count++;
}
- item = (node_t *)(size_t)STRIP_TAG(item->next[0], TAG1);
+ item = STRIP_MARK(item->next[0]);
}
return count;
}
// Traverse the levels of <sl> from the top level to the bottom
for (int level = start_level; level >= 0; --level) {
TRACE("s3", "find_preds: level %llu", level, 0);
- item = (node_t *)pred->next[level];
- if (EXPECT_FALSE(IS_TAGGED((uint64_t)item, TAG1))) {
- TRACE("s2", "find_preds: pred %p is marked for removal (item %p); retry", pred, item);
+ markable_t next = pred->next[level];
+ if (EXPECT_FALSE(HAS_MARK(next))) {
+ TRACE("s2", "find_preds: pred %p is marked for removal (next %p); retry", pred, next);
return find_preds(preds, succs, n, sl, key, help_remove); // retry
}
+ item = GET_NODE(next);
while (item != NULL) {
- uint64_t next = item->next[level];
+ next = item->next[level];
// A tag means an item is logically removed but not physically unlinked yet.
- while (EXPECT_FALSE(IS_TAGGED(next, TAG1))) {
+ while (EXPECT_FALSE(HAS_MARK(next))) {
// Skip over logically removed items.
if (!help_remove) {
- item = (node_t *)(size_t)STRIP_TAG(next, TAG1);
+ item = STRIP_MARK(next);
if (EXPECT_FALSE(item == NULL))
break;
next = item->next[level];
// Unlink logically removed items.
TRACE("s3", "find_preds: unlinking marked item %p; next is 0x%llx", item, next);
- uint64_t other = SYNC_CAS(&pred->next[level], (uint64_t)(size_t)item, STRIP_TAG(next, TAG1));
- if (other == (uint64_t)(size_t)item) {
- item = (node_t *)(size_t)STRIP_TAG(next, TAG1);
+ markable_t other = SYNC_CAS(&pred->next[level], item, STRIP_MARK(next));
+ if (other == (markable_t)item) {
+ item = STRIP_MARK(next);
next = (item != NULL) ? item->next[level] : DOES_NOT_EXIST;
TRACE("s3", "find_preds: now the current item is %p next is 0x%llx", item, next);
// The thread that completes the unlink should free the memory.
if (level == 0) {
+ node_t *unlinked = GET_NODE(other);
if (sl->key_type != NULL) {
- nbd_defer_free((void *)(size_t)((node_t *)(size_t)other)->key);
+ nbd_defer_free((void *)unlinked->key);
}
- nbd_defer_free(((node_t *)(size_t)other));
+ nbd_defer_free(unlinked);
}
} else {
TRACE("s3", "find_preds: lost race to unlink item %p from pred %p", item, pred);
TRACE("s3", "find_preds: pred's link changed to %p", other, 0);
- if (IS_TAGGED(other, TAG1))
+ if (HAS_MARK(other))
return find_preds(preds, succs, n, sl, key, help_remove); // retry
- item = (node_t *)(size_t)other;
+ item = GET_NODE(other);
next = (item != NULL) ? item->next[level] : DOES_NOT_EXIST;
}
}
break;
TRACE("s4", "find_preds: visiting item %p (next is %p)", item, next);
- TRACE("s4", "find_preds: key %p val %p", STRIP_TAG(item->key, TAG1), item->val);
+ TRACE("s4", "find_preds: key %p val %p", STRIP_MARK(item->key), item->val);
if (EXPECT_TRUE(sl->key_type == NULL)) {
- d = (uint64_t)item->key - (uint64_t)key;
+ d = item->key - key;
} else {
- d = sl->key_type->cmp((void *)(size_t)item->key, (void *)(size_t)key);
+ d = sl->key_type->cmp((void *)item->key, (void *)key);
}
if (d >= 0) {
}
pred = item;
- item = (node_t *)(size_t)next;
+ item = GET_NODE(next);
}
// The cast to unsigned is for the case when n is -1.
}
map_key_t sl_min_key (skiplist_t *sl) {
- node_t *item = (node_t *)(size_t)sl->head->next[0];
+ node_t *item = GET_NODE(sl->head->next[0]);
while (item != NULL) {
- uint64_t next = item->next[0];
- if (!IS_TAGGED(next, TAG1))
+ markable_t next = item->next[0];
+ if (!HAS_MARK(next))
return item->key;
- item = (node_t *)(size_t)STRIP_TAG(next, TAG1);
+ item = STRIP_MARK(next);
}
return DOES_NOT_EXIST;
}
// 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)(size_t)sl->key_type->clone((void *)(size_t)key);
+ map_key_t new_key = sl->key_type == NULL ? key : (map_key_t)sl->key_type->clone((void *)key);
new_item = node_alloc(n, new_key, new_val);
node_t *pred = preds[0];
- uint64_t next = new_item->next[0] = (uint64_t)(size_t)nexts[0];
+ markable_t next = new_item->next[0] = (markable_t)nexts[0];
for (int level = 1; level <= new_item->top_level; ++level) {
- new_item->next[level] = (uint64_t)(size_t)nexts[level];
+ new_item->next[level] = (markable_t)nexts[level];
}
- uint64_t other = SYNC_CAS(&pred->next[0], next, (uint64_t)(size_t)new_item);
+ markable_t other = SYNC_CAS(&pred->next[0], next, new_item);
if (other == next) {
TRACE("s3", "sl_cas: successfully inserted item %p at level 0", new_item, 0);
break; // success
}
TRACE("s3", "sl_cas: failed to change pred's link: expected %p found %p", next, other);
if (sl->key_type != NULL) {
- nbd_free((void *)(size_t)new_key);
+ nbd_free((void *)new_key);
}
nbd_free(new_item);
continue;
// Link <new_item> into <sl> from the bottom up.
for (int level = 1; level <= new_item->top_level; ++level) {
node_t *pred = preds[level];
- uint64_t next = (uint64_t)(size_t)nexts[level];
+ markable_t next = (markable_t)nexts[level];
do {
TRACE("s3", "sl_cas: attempting to insert item between %p and %p", pred, next);
- uint64_t other = SYNC_CAS(&pred->next[level], next, (uint64_t)(size_t)new_item);
+ markable_t other = SYNC_CAS(&pred->next[level], next, (markable_t)new_item);
if (other == next) {
TRACE("s3", "sl_cas: successfully inserted item %p at level %llu", new_item, level);
break; // success
TRACE("s3", "sl_cas: failed to change pred's link: expected %p found %p", next, other);
find_preds(preds, nexts, new_item->top_level, sl, key, TRUE);
pred = preds[level];
- next = (uint64_t)(size_t)nexts[level];
+ next = (markable_t)nexts[level];
// Update <new_item>'s next pointer
do {
// There in no need to continue linking in the item if another thread removed it.
- uint64_t old_next = ((volatile node_t *)new_item)->next[level];
- if (IS_TAGGED(old_next, TAG1))
+ markable_t old_next = ((volatile node_t *)new_item)->next[level];
+ if (HAS_MARK(old_next))
return DOES_NOT_EXIST; // success
// Use a CAS so we do not inadvertantly stomp on a mark another thread placed on the item.
// Mark and unlink <item> at each level of <sl> from the top down. If multiple threads try to concurrently remove
// the same item only one of them should succeed. Marking the bottom level establishes which of them succeeds.
for (int level = item->top_level; level > 0; --level) {
- uint64_t next;
- uint64_t old_next = item->next[level];
+ markable_t next;
+ markable_t old_next = item->next[level];
do {
next = old_next;
- old_next = SYNC_CAS(&item->next[level], next, TAG_VALUE(next, TAG1));
- if (IS_TAGGED(old_next, TAG1)) {
+ old_next = SYNC_CAS(&item->next[level], next, MARK_NODE((node_t *)next));
+ if (HAS_MARK(old_next)) {
TRACE("s2", "sl_remove: %p is already marked for removal by another thread at level %llu", item, level);
break;
}
} while (next != old_next);
node_t *pred = preds[level];
- TRACE("s2", "sl_remove: linking the item's pred %p to the item's successor %p", pred, STRIP_TAG(next, TAG1));
- uint64_t other = SYNC_CAS(&pred->next[level], (uint64_t)(size_t)item, STRIP_TAG(next, TAG1));
- if (other != (uint64_t)(size_t)item) {
+ TRACE("s2", "sl_remove: linking the item's pred %p to the item's successor %p", pred, STRIP_MARK(next));
+ markable_t other = SYNC_CAS(&pred->next[level], item, STRIP_MARK(next));
+ if (other != (markable_t)item) {
TRACE("s1", "sl_remove: unlink failed; pred's link changed from %p to %p", item, other);
// If our former predecessor now points past us we know another thread unlinked us. Otherwise, we need
// to search for a new set of preds.
continue; // <pred> points past <item> to the end of the list; go on to the next level.
int d = -1;
- if (!IS_TAGGED(other, TAG1)) {
- map_key_t other_key = ((node_t *)(size_t)other)->key;
+ if (!HAS_MARK(other)) {
+ map_key_t other_key = GET_NODE(other)->key;
if (EXPECT_TRUE(sl->key_type == NULL)) {
- d = (uint64_t)item->key - (uint64_t)other_key;
+ d = item->key - other_key;
} else {
- d = sl->key_type->cmp((void *)(size_t)item->key, (void *)(size_t)other_key);
+ d = sl->key_type->cmp((void *)item->key, (void *)other_key);
}
}
if (d > 0) {
}
}
- uint64_t next;
- uint64_t old_next = item->next[0];
+ markable_t next;
+ markable_t old_next = item->next[0];
do {
next = old_next;
- old_next = SYNC_CAS(&item->next[0], next, TAG_VALUE(next, TAG1));
- if (IS_TAGGED(old_next, TAG1)) {
+ old_next = SYNC_CAS(&item->next[0], next, MARK_NODE((node_t *)next));
+ if (HAS_MARK(old_next)) {
TRACE("s2", "sl_remove: %p is already marked for removal by another thread at level 0", item, 0);
return DOES_NOT_EXIST;
}
TRACE("s2", "sl_remove: replaced item %p's value with DOES_NOT_EXIT", item, 0);
node_t *pred = preds[0];
- TRACE("s2", "sl_remove: linking the item's pred %p to the item's successor %p", pred, STRIP_TAG(next, TAG1));
- if (SYNC_CAS(&pred->next[0], item, STRIP_TAG(next, TAG1))) {
+ TRACE("s2", "sl_remove: linking the item's pred %p to the item's successor %p", pred, STRIP_MARK(next));
+ if (SYNC_CAS(&pred->next[0], item, STRIP_MARK(next))) {
TRACE("s2", "sl_remove: unlinked item %p from the skiplist at level 0", item, 0);
// The thread that completes the unlink should free the memory.
if (sl->key_type != NULL) {
- nbd_defer_free((void *)(size_t)item->key);
+ nbd_defer_free((void *)item->key);
}
nbd_defer_free(item);
}
printf("(%d) ", level);
int i = 0;
while (item) {
- uint64_t next = item->next[level];
- printf("%s%p ", IS_TAGGED(next, TAG1) ? "*" : "", item);
- item = (node_t *)(size_t)STRIP_TAG(next, TAG1);
+ markable_t next = item->next[level];
+ printf("%s%p ", HAS_MARK(next) ? "*" : "", item);
+ item = STRIP_MARK(next);
if (i++ > 30) {
printf("...");
break;
node_t *item = sl->head;
int i = 0;
while (item) {
- int is_marked = IS_TAGGED(item->next[0], TAG1);
- printf("%s%p:0x%llx ", is_marked ? "*" : "", item, (uint64_t)(size_t)item->key);
+ int is_marked = HAS_MARK(item->next[0]);
+ printf("%s%p:0x%llx ", is_marked ? "*" : "", item, (map_key_t)item->key);
if (item != sl->head) {
printf("[%d]", item->top_level);
} else {
printf("[HEAD]");
}
for (int level = 1; level <= item->top_level; ++level) {
- node_t *next = (node_t *)(size_t)STRIP_TAG(item->next[level], TAG1);
- is_marked = IS_TAGGED(item->next[0], TAG1);
+ node_t *next = STRIP_MARK(item->next[level]);
+ is_marked = HAS_MARK(item->next[0]);
printf(" %p%s", next, is_marked ? "*" : "");
if (item == sl->head && item->next[level] == DOES_NOT_EXIST)
break;
}
printf("\n");
fflush(stdout);
- item = (node_t *)(size_t)STRIP_TAG(item->next[0], TAG1);
+ item = STRIP_MARK(item->next[0]);
if (i++ > 30) {
printf("...\n");
break;
map_val_t sl_iter_next (sl_iter_t *iter, map_key_t *key_ptr) {
assert(iter);
node_t *item = iter->next;
- while (item != NULL && IS_TAGGED(item->next[0], TAG1)) {
- item = (node_t *)(size_t)STRIP_TAG(item->next[0], TAG1);
+ while (item != NULL && HAS_MARK(item->next[0])) {
+ item = STRIP_MARK(item->next[0]);
}
if (item == NULL) {
iter->next = NULL;
return DOES_NOT_EXIST;
}
- iter->next = (node_t *)(size_t)STRIP_TAG(item->next[0], TAG1);
+ iter->next = STRIP_MARK(item->next[0]);
if (key_ptr != NULL) {
*key_ptr = item->key;
}
#include "skiplist.h"
#include "hashtable.h"
-#define NUM_ITERATIONS 1000000
+#define NUM_ITERATIONS 10000000
//#define TEST_STRING_KEYS
for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) {
unsigned r = nbd_rand();
- uint64_t key = r & 0xF;
+ int key = r & 0xF;
#ifdef TEST_STRING_KEYS
key_str->len = sprintf(key_str->data, "%llX", key) + 1;
assert(key_str->len <= 10);
if (r & (1 << 8)) {
- map_set(map_, key_str, 1);
+ map_set(map_, (map_key_t)key_str, 1);
} else {
- map_remove(map_, key_str);
+ map_remove(map_, (map_key_t)key_str);
}
#else
if (r & (1 << 8)) {
static const map_impl_t *map_type_;
-static uint64_t iterator_size (map_t *map) {
+static size_t iterator_size (map_t *map) {
map_iter_t *iter = map_iter_begin(map, 0);
- uint64_t count = 0;
+ size_t count = 0;
while (map_iter_next(iter, NULL) != DOES_NOT_EXIST) {
count++;
}
worker_data_t *wd = (worker_data_t *)arg;
map_t *map = wd->map;
CuTest* tc = wd->tc;
- uint64_t d = wd->id;
+ int d = wd->id;
int iters = 10000;
SYNC_ADD(wd->wait, -1);
#endif
for (int j = 0; j < 10; ++j) {
- for (uint64_t i = d+1; i < iters; i+=2) {
+ 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);
ASSERT_EQUAL(DOES_NOT_EXIST, map_add(map, key, d+1) );
rcu_update(); // In a quiecent state.
}
- for (uint64_t i = d+1; i < iters; i+=2) {
+ 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);
+ snprintf(key->data, key->len, "%u", i);
#else
key = (map_key_t)i;
#endif
ASSERT_EQUAL( DOES_NOT_EXIST, map_add (map, k1,1) );
ASSERT_EQUAL( DOES_NOT_EXIST, map_add (map, k2,2) );
- uint64_t x_v, y_v;
+ 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);
ASSERT_EQUAL( n, iterator_size(map) );
uint64_t sum = 0;
- uint64_t val;
+ map_val_t val;
map_iter_t *iter = map_iter_begin(map, 0);
while ((val = map_iter_next(iter, NULL)) != DOES_NOT_EXIST) {
sum += val;
uint64_t wv;
map_t *map;
write_rec_t *writes;
- uint64_t writes_size;
- uint64_t writes_count;
- uint64_t writes_scan;
+ size_t writes_size;
+ size_t writes_count;
+ size_t writes_scan;
txn_state_e state;
};
// will eventually conflict with it and abort.
if (!IS_TAGGED(val, TAG2))
return TXN_VALIDATED;
- update = (update_t *)(size_t)STRIP_TAG(val, TAG2);
+ update = (update_t *)STRIP_TAG(val, TAG2);
if (!IS_TAGGED(update->version, TAG1))
return (update->version <= txn->rv) ? TXN_VALIDATED : TXN_ABORTED;
continue;
// The update's transaction is still in progress. Access its txn_t.
- txn_t *writer = (txn_t *)(size_t)STRIP_TAG(update->version, TAG1);
+ txn_t *writer = (txn_t *)STRIP_TAG(update->version, TAG1);
if (writer == txn)
continue; // Skip our own updates.
txn_state_e writer_state = writer->state;
}
// Get most recent committed version prior to our read version.
-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) {
if (txn->state != TXN_RUNNING)
return ERROR_TXN_NOT_RUNNING;
// Iterate through the update records to find the latest committed version prior to our read version.
- uint64_t newest_val = map_get(txn->map, key);
- uint64_t val = newest_val;
+ map_val_t newest_val = map_get(txn->map, key);
+ map_val_t val = newest_val;
update_t *update = NULL;
for ( ; ; val = update->next) {
if (!IS_TAGGED(val, TAG2))
return val;
- update = (update_t *)(size_t)STRIP_TAG(val, TAG2);
+ update = (update_t *)STRIP_TAG(val, TAG2);
assert(update != NULL);
// If the update's version is not tagged it means the update is committed.
continue;
// The update's transaction is still in progress. Access its txn_t.
- txn_t *writer = (txn_t *)(size_t)STRIP_TAG(update->version, TAG1);
+ txn_t *writer = (txn_t *)STRIP_TAG(update->version, TAG1);
if (writer == txn) // found our own update
break; // success
break; // success
}
- uint64_t value = update->value;
+ map_val_t value = update->value;
// collect some garbage
uint64_t min_active_version = UNDETERMINED_VERSION;
update_t *next_update = NULL;
if (IS_TAGGED(update->next, TAG2)) {
- next_update = (update_t *)(size_t)STRIP_TAG(update->next, TAG2);
+ next_update = (update_t *)STRIP_TAG(update->next, TAG2);
min_active_version = (uint64_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
if (!IS_TAGGED(next, TAG2))
break;
- temp = (update_t *)(size_t)STRIP_TAG(next, TAG2);
+ temp = (update_t *)STRIP_TAG(next, TAG2);
if (temp->version >= min_active_version)
return value;
}
if (!IS_TAGGED(next, TAG2))
break;
- temp = (update_t *)(size_t)STRIP_TAG(next, TAG2);
+ temp = (update_t *)STRIP_TAG(next, TAG2);
nbd_free(update);
}
}
return value;
}
-void txn_map_set (txn_t *txn, map_key_t key, uint64_t value) {
+void txn_map_set (txn_t *txn, map_key_t key, map_val_t value) {
if (txn->state != TXN_RUNNING)
return; // TODO: return some sort of error code
// create a new update record
update_t *update = alloc_update_rec();
update->value = value;
- update->version = TAG_VALUE((uint64_t)(size_t)txn, TAG1);
+ update->version = TAG_VALUE((uint64_t)txn, TAG1);
// push the new update record onto <key>'s update list
uint64_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)(size_t)update, TAG2)) != old_update);
+ } while (map_cas(txn->map, key, old_update, TAG_VALUE((uint64_t)update, TAG2)) != old_update);
// add <key> to the write set for commit-time validation
if (txn->writes_count == txn->writes_size) {