X-Git-Url: https://pd.if.org/git/?p=nbds;a=blobdiff_plain;f=map%2Fskiplist.c;h=73bad7b03dbe6cac22b98d0845a8fab396b2f2bb;hp=c2777a904f188ff215a7681fea0dd934540275b2;hb=778b8c8ca708b082a1192acfb114a6751b2ad7c9;hpb=2cce67f0002cdb6dcdc2ab8ccf837e3d2b3336de diff --git a/map/skiplist.c b/map/skiplist.c index c2777a9..73bad7b 100644 --- a/map/skiplist.c +++ b/map/skiplist.c @@ -21,18 +21,25 @@ #include #include "common.h" -#include "runtime.h" #include "skiplist.h" +#include "runtime.h" #include "mem.h" +#include "rcu.h" -// Setting MAX_LEVEL to 0 essentially makes this data structure the Harris-Michael lock-free list (in list.c). -#define MAX_LEVEL 31 +// Setting MAX_LEVELS to 1 essentially makes this data structure the Harris-Michael lock-free list (see list.c). +#define MAX_LEVELS 32 + +enum unlink { + FORCE_UNLINK, + ASSIST_UNLINK, + DONT_UNLINK +}; typedef struct node { map_key_t key; map_val_t val; - int top_level; - uint64_t next[]; + unsigned num_levels; + markable_t next[1]; } node_t; struct sl_iter { @@ -42,157 +49,148 @@ struct sl_iter { struct sl { node_t *head; const datatype_t *key_type; + int high_water; // max level of any item in the list }; -static int random_level (void) { - unsigned r = nbd_rand(); - if (r & 1) - return 0; -#if MAX_LEVEL < 31 - r |= 1 << (MAX_LEVEL+1); +// Marking the 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, 0x1); } +static inline int HAS_MARK(markable_t x) { return (IS_TAGGED(x, 0x1) == 0x1); } +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, 0x1)); } +#else +#define MARK_NODE(x) TAG_VALUE((markable_t)(x), 0x1) +#define HAS_MARK(x) (IS_TAGGED((x), 0x1) == 0x1) +#define GET_NODE(x) ((node_t *)(x)) +#define STRIP_MARK(x) ((node_t *)STRIP_TAG((x), 0x1)) #endif - int n = __builtin_ctz(r)-1; - assert(n <= MAX_LEVEL); + +static int random_levels (void) { + unsigned r = nbd_rand(); + int n = __builtin_ctz(r) / 2 + 1; + if (n > MAX_LEVELS) { n = MAX_LEVELS; } return n; } -static node_t *node_alloc (int level, map_key_t key, map_val_t val) { - assert(level >= 0 && level <= MAX_LEVEL); - size_t sz = sizeof(node_t) + (level + 1) * sizeof(node_t *); +static node_t *node_alloc (int num_levels, map_key_t key, map_val_t val) { + assert(num_levels >= 0 && num_levels <= MAX_LEVELS); + size_t sz = sizeof(node_t) + (num_levels - 1) * sizeof(node_t *); node_t *item = (node_t *)nbd_malloc(sz); memset(item, 0, sz); item->key = key; item->val = val; - item->top_level = level; + item->num_levels = num_levels; + TRACE("s2", "node_alloc: new node %p (%llu levels)", item, num_levels); return item; } skiplist_t *sl_alloc (const datatype_t *key_type) { skiplist_t *sl = (skiplist_t *)nbd_malloc(sizeof(skiplist_t)); sl->key_type = key_type; - sl->head = node_alloc(MAX_LEVEL, 0, 0); - memset(sl->head->next, 0, (MAX_LEVEL+1) * sizeof(skiplist_t *)); + sl->high_water = 0; + sl->head = node_alloc(MAX_LEVELS, 0, 0); + memset(sl->head->next, 0, MAX_LEVELS * sizeof(skiplist_t *)); return sl; } 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; } -static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl, map_key_t key, int help_remove) { +static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl, map_key_t key, enum unlink unlink) { node_t *pred = sl->head; node_t *item = NULL; TRACE("s2", "find_preds: searching for key %p in skiplist (head is %p)", key, pred); - int d; - int start_level = MAX_LEVEL; -#if MAX_LEVEL > 2 - // Optimization for small lists. No need to traverse empty higher levels. - start_level = 2; - while (pred->next[start_level+1] != DOES_NOT_EXIST) { - start_level += start_level - 1; - if (EXPECT_FALSE(start_level >= MAX_LEVEL)) { - start_level = MAX_LEVEL; - break; - } - } - if (EXPECT_FALSE(start_level < n)) { - start_level = n; - } -#endif + int d = 0; // Traverse the levels of from the top level to the bottom - for (int level = start_level; level >= 0; --level) { - TRACE("s3", "find_preds: level %llu", level, 0); - uint64_t next = pred->next[level]; - if (EXPECT_FALSE(IS_TAGGED(next, TAG1))) { + for (int level = sl->high_water - 1; level >= 0; --level) { + markable_t next = pred->next[level]; + if (next == DOES_NOT_EXIST && level >= n) + continue; + TRACE("s3", "find_preds: traversing level %p starting at %p", level, pred); + 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 + ASSERT(level == pred->num_levels - 1 || HAS_MARK(pred->next[level+1])); + return find_preds(preds, succs, n, sl, key, unlink); // retry } - while (next != DOES_NOT_EXIST) { - item = (node_t *)(size_t)next; + item = GET_NODE(next); + while (item != NULL) { 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))) { + TRACE("s3", "find_preds: found marked item %p (next is %p)", item, next); + if (unlink == DONT_UNLINK) { - // Skip over logically removed items. - if (!help_remove) { - item = (node_t *)(size_t)STRIP_TAG(next, TAG1); + // Skip over logically removed items. + item = STRIP_MARK(next); if (EXPECT_FALSE(item == NULL)) break; next = item->next[level]; - TRACE("s3", "find_preds: skipping marked item %p (next is 0x%llx)", item, next); - continue; - } + } else { - // 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); - 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) { - if (sl->key_type != NULL) { - nbd_defer_free((void *)(size_t)((node_t *)(size_t)other)->key); - } - nbd_defer_free(((node_t *)(size_t)other)); + // Unlink logically removed items. + markable_t other = SYNC_CAS(&pred->next[level], (markable_t)item, (markable_t)STRIP_MARK(next)); + if (other == (markable_t)item) { + TRACE("s3", "find_preds: unlinked item from pred %p", pred, 0); + item = STRIP_MARK(next); + } else { + TRACE("s3", "find_preds: lost race to unlink item pred %p's link changed to %p", pred, other); + if (HAS_MARK(other)) + return find_preds(preds, succs, n, sl, key, unlink); // retry + item = GET_NODE(other); } - } 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)) - return find_preds(preds, succs, n, sl, key, help_remove); // retry - item = (node_t *)(size_t)other; next = (item != NULL) ? item->next[level] : DOES_NOT_EXIST; } } - if (EXPECT_FALSE(item == NULL)) + if (EXPECT_FALSE(item == NULL)) { + TRACE("s3", "find_preds: past the last item in the skiplist", 0, 0); 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) { - TRACE("s4", "find_preds: found pred %p item %p", pred, item); + if (d > 0) + break; + if (d == 0 && unlink != FORCE_UNLINK) break; - } pred = item; - item = (node_t *)(size_t)next; + item = GET_NODE(next); } - // The cast to unsigned is for the case when n is -1. - if ((unsigned)level <= (unsigned)n) { + TRACE("s3", "find_preds: found pred %p next %p", pred, item); + + if (level < n) { if (preds != NULL) { preds[level] = pred; } @@ -202,14 +200,6 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl } } - // fill in empty levels - if (n == -1 && item != NULL) { - assert(item->top_level <= MAX_LEVEL); - for (int level = start_level + 1; level <= item->top_level; ++level) { - preds[level] = sl->head; - } - } - if (d == 0) { TRACE("s2", "find_preds: found matching item %p in skiplist, pred is %p", item, pred); return item; @@ -221,7 +211,7 @@ static node_t *find_preds (node_t **preds, node_t **succs, int n, skiplist_t *sl // Fast find that does not help unlink partially removed nodes and does not return the node's predecessors. map_val_t sl_lookup (skiplist_t *sl, map_key_t key) { TRACE("s1", "sl_lookup: searching for key %p in skiplist %p", key, sl); - node_t *item = find_preds(NULL, NULL, 0, sl, key, FALSE); + node_t *item = find_preds(NULL, NULL, 0, sl, key, DONT_UNLINK); // If we found an matching the return its value. if (item != NULL) { @@ -237,215 +227,208 @@ map_val_t sl_lookup (skiplist_t *sl, map_key_t key) { } 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; } +static map_val_t update_item (node_t *item, map_val_t expectation, map_val_t new_val) { + map_val_t old_val = item->val; + + // If the item's value is DOES_NOT_EXIST it means another thread removed the node out from under us. + if (EXPECT_FALSE(old_val == DOES_NOT_EXIST)) { + TRACE("s2", "update_item: lost a race to another thread removing the item. retry", 0, 0); + return DOES_NOT_EXIST; // retry + } + + if (EXPECT_FALSE(expectation == CAS_EXPECT_DOES_NOT_EXIST)) { + TRACE("s1", "update_item: found an item %p in the skiplist that matched the key. the expectation was " + "not met, the skiplist was not changed", item, old_val); + return old_val; // failure + } + + // Use a CAS and not a SWAP. If the CAS fails it means another thread removed the node or updated its + // value. If another thread removed the node but it is not unlinked yet and we used a SWAP, we could + // replace DOES_NOT_EXIST with our value. Then another thread that is updating the value could think it + // succeeded and return our value even though it should return DOES_NOT_EXIST. + if (old_val == SYNC_CAS(&item->val, old_val, new_val)) { + TRACE("s1", "update_item: the CAS succeeded. updated the value of the item", 0, 0); + return old_val; // success + } + TRACE("s2", "update_item: lost a race. the CAS failed. another thread changed the item's value", 0, 0); + + // retry + return update_item(item, expectation, new_val); // tail call +} + map_val_t sl_cas (skiplist_t *sl, map_key_t key, map_val_t expectation, map_val_t new_val) { TRACE("s1", "sl_cas: key %p skiplist %p", key, sl); TRACE("s1", "sl_cas: expectation %p new value %p", expectation, new_val); ASSERT((int64_t)new_val > 0); - node_t *preds[MAX_LEVEL+1]; - node_t *nexts[MAX_LEVEL+1]; + node_t *preds[MAX_LEVELS]; + node_t *nexts[MAX_LEVELS]; node_t *new_item = NULL; - int n = random_level(); - do { - node_t *old_item = find_preds(preds, nexts, n, sl, key, TRUE); - 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)) { - TRACE("l1", "sl_cas: the expectation was not met, the skiplist was not changed", 0, 0); - return DOES_NOT_EXIST; // failure - } + int n = random_levels(); + if (n > sl->high_water) { + n = SYNC_ADD(&sl->high_water, 1); + TRACE("s2", "sl_cas: incremented high water mark to %p", n, 0); + } + node_t *old_item = find_preds(preds, nexts, n, sl, key, ASSIST_UNLINK); - ASSERT(expectation == CAS_EXPECT_DOES_NOT_EXIST || expectation == CAS_EXPECT_WHATEVER); - - // First insert 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); - 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]; - for (int level = 1; level <= new_item->top_level; ++level) { - new_item->next[level] = (uint64_t)(size_t)nexts[level]; - } - uint64_t other = SYNC_CAS(&pred->next[0], next, (uint64_t)(size_t)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(new_item); - continue; + // If there is already an item in the skiplist that matches the key just update its value. + if (old_item != NULL) { + map_val_t ret_val = update_item(old_item, expectation, new_val); + if (ret_val != DOES_NOT_EXIST) + return ret_val; + + // If we lose a race with a thread removing the item we tried to update then we have to retry. + return sl_cas(sl, key, expectation, new_val); // tail call + } + + 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, the caller expected an item for the to already exist + } + + // Create a new node and insert it into the skiplist. + TRACE("s3", "sl_cas: attempting to insert a new 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); + new_item = node_alloc(n, new_key, new_val); + + // Set 's next pointers to their proper values + markable_t next = new_item->next[0] = (markable_t)nexts[0]; + for (int level = 1; level < new_item->num_levels; ++level) { + new_item->next[level] = (markable_t)nexts[level]; + } + + // Link into from the bottom level up. After is inserted into the bottom level + // it is officially part of the skiplist. + node_t *pred = preds[0]; + markable_t other = SYNC_CAS(&pred->next[0], next, (markable_t)new_item); + if (other != next) { + TRACE("s3", "sl_cas: failed to change pred's link: expected %p found %p", next, other); + + // Lost a race to another thread modifying the skiplist. Free the new item we allocated and retry. + if (sl->key_type != NULL) { + nbd_free((void *)new_key); } + nbd_free(new_item); + return sl_cas(sl, key, expectation, new_val); // tail call + } + + TRACE("s3", "sl_cas: successfully inserted a new item %p at the bottom level", new_item, 0); - // Found an item in the skiplist that matches the key. - map_val_t old_item_val = old_item->val; + ASSERT(new_item->num_levels <= MAX_LEVELS); + for (int level = 1; level < new_item->num_levels; ++level) { + TRACE("s3", "sl_cas: inserting the new item %p at level %p", new_item, level); do { - // If the item's value is DOES_NOT_EXIST it means another thread removed the node out from under us. - if (EXPECT_FALSE(old_item_val == DOES_NOT_EXIST)) { - TRACE("s2", "sl_cas: lost a race, found an item but another thread removed it. retry", 0, 0); - break; // retry - } + node_t * pred = preds[level]; + ASSERT(new_item->next[level]==(markable_t)nexts[level] || new_item->next[level]==MARK_NODE(nexts[level])); + TRACE("s3", "sl_cas: attempting to to insert the new item between %p and %p", pred, nexts[level]); - if (EXPECT_FALSE(expectation == CAS_EXPECT_DOES_NOT_EXIST)) { - TRACE("s1", "sl_cas: found an item %p in the skiplist that matched the key. the expectation was " - "not met, the skiplist was not changed", old_item, old_item_val); - return old_item_val; // failure - } + markable_t other = SYNC_CAS(&pred->next[level], (markable_t)nexts[level], (markable_t)new_item); + if (other == (markable_t)nexts[level]) + break; // successfully linked into the skiplist at the current + TRACE("s3", "sl_cas: lost a race. failed to change pred's link. expected %p found %p", nexts[level], other); - // Use a CAS and not a SWAP. If the node is in the process of being removed and we used a SWAP, we could - // replace DOES_NOT_EXIST with our value. Then another thread that is updating the value could think it - // succeeded and return our value even though we indicated that the node has been removed. If the CAS - // fails it means another thread either removed the node or updated its value. - map_val_t ret_val = SYNC_CAS(&old_item->val, old_item_val, new_val); - if (ret_val == old_item_val) { - TRACE("s1", "sl_cas: the CAS succeeded. updated the value of the item", 0, 0); - return ret_val; // success - } - TRACE("s2", "sl_cas: lost a race. the CAS failed. another thread changed the item's value", 0, 0); + // Find 's new preds and nexts. + find_preds(preds, nexts, new_item->num_levels, sl, key, ASSIST_UNLINK); - old_item_val = ret_val; - } while (1); - } while (1); + for (int i = level; i < new_item->num_levels; ++i) { + markable_t old_next = new_item->next[i]; + if ((markable_t)nexts[i] == old_next) + continue; - // Link into 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]; - 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); - if (other == next) { - TRACE("s3", "sl_cas: successfully inserted item %p at level %llu", new_item, level); - break; // success + // Update 's inconsistent next pointer before trying again. Use a CAS so if another thread + // is trying to remove the new item concurrently we do not stomp on the mark it places on the item. + TRACE("s3", "sl_cas: attempting to update the new item's link from %p to %p", old_next, nexts[i]); + other = SYNC_CAS(&new_item->next[i], old_next, (markable_t)nexts[i]); + ASSERT(other == old_next || other == MARK_NODE(old_next)); + + // If another thread is removing this item we can stop linking it into to skiplist + if (HAS_MARK(other)) { + find_preds(NULL, NULL, 0, sl, key, FORCE_UNLINK); // see comment below + return DOES_NOT_EXIST; + } } - 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]; - - // Update '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)) - return DOES_NOT_EXIST; // success - - // Use a CAS so we do not inadvertantly stomp on a mark another thread placed on the item. - if (old_next == next || SYNC_CAS(&new_item->next[level], old_next, next) == old_next) - break; - } while (1); } while (1); } - return DOES_NOT_EXIST; // success + + // In case another thread was in the process of removing the while we were added it, we have to + // make sure it is completely unlinked before we return. We might have lost a race and inserted the new item + // at some level after the other thread thought it was fully removed. That is a problem because once a thread + // thinks it completely unlinks a node it queues it to be freed + if (HAS_MARK(new_item->next[new_item->num_levels - 1])) { + find_preds(NULL, NULL, 0, sl, key, FORCE_UNLINK); + } + + return DOES_NOT_EXIST; // success, inserted a new item } map_val_t sl_remove (skiplist_t *sl, map_key_t key) { TRACE("s1", "sl_remove: removing item with key %p from skiplist %p", key, sl); - node_t *preds[MAX_LEVEL+1]; - node_t *item = find_preds(preds, NULL, -1, sl, key, TRUE); + node_t *preds[MAX_LEVELS]; + node_t *item = find_preds(preds, NULL, sl->high_water, sl, key, ASSIST_UNLINK); if (item == NULL) { TRACE("s3", "sl_remove: remove failed, an item with a matching key does not exist in the skiplist", 0, 0); return DOES_NOT_EXIST; } - // Mark and unlink at each level of from the top down. If multiple threads try to concurrently remove + // Mark at each level of 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 old_next = 0; + for (int level = item->num_levels - 1; level >= 0; --level) { + markable_t next; + old_next = item->next[level]; do { + TRACE("s3", "sl_remove: marking item at level %p (next %p)", level, old_next); next = old_next; - old_next = SYNC_CAS(&item->next[level], next, TAG_VALUE(next, TAG1)); - if (IS_TAGGED(old_next, TAG1)) { - TRACE("s2", "sl_remove: %p is already marked for removal by another thread at level %llu", item, level); + 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 (next %p)", item, old_next); + if (level == 0) + return DOES_NOT_EXIST; 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("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. - if (other == DOES_NOT_EXIST) - continue; // points past 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 (EXPECT_TRUE(sl->key_type == NULL)) { - d = (uint64_t)item->key - (uint64_t)other_key; - } else { - d = sl->key_type->cmp((void *)(size_t)item->key, (void *)(size_t)other_key); - } - } - if (d > 0) { - node_t *temp = find_preds(preds, NULL, level, sl, key, TRUE); - if (temp != item) - return DOES_NOT_EXIST; // Another thread removed the item we were targeting. - level++; // Redo this level. - } - } } - uint64_t next; - uint64_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)) { - TRACE("s2", "sl_remove: %p is already marked for removal by another thread at level 0", item, 0); - return DOES_NOT_EXIST; - } - } while (next != old_next); - TRACE("s1", "sl_remove: marked item %p removed at level 0", item, 0); - // 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. map_val_t val = SYNC_SWAP(&item->val, 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: 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(item); + // unlink the item + find_preds(NULL, NULL, 0, sl, key, FORCE_UNLINK); + + // free the node + if (sl->key_type != NULL) { + rcu_defer_free((void *)item->key); } + rcu_defer_free(item); + return val; } void sl_print (skiplist_t *sl) { - for (int level = MAX_LEVEL; level >= 0; --level) { + + printf("high water: %d levels\n", sl->high_water); + for (int level = MAX_LEVELS - 1; level >= 0; --level) { node_t *item = sl->head; if (item->next[level] == DOES_NOT_EXIST) continue; 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; @@ -457,23 +440,23 @@ void sl_print (skiplist_t *sl) { 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, (uint64_t)item->key); if (item != sl->head) { - printf("[%d]", item->top_level); + printf("[%d]", item->num_levels); } 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); + for (int level = 1; level < item->num_levels; ++level) { + 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; @@ -483,21 +466,25 @@ void sl_print (skiplist_t *sl) { 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, 1, sl, key, DONT_UNLINK); + } else { + iter->next = GET_NODE(sl->head->next[0]); + } return iter; } 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; }