X-Git-Url: https://pd.if.org/git/?p=nbds;a=blobdiff_plain;f=struct%2Flist.c;fp=struct%2Flist.c;h=b9ec91fd97af1d04c302a9336d9483350a482223;hp=1920e60fd80be20005a04ef457fbb428ead540cf;hb=f0777b2151019e22458f6f166a8f3c569c32a505;hpb=9b3e566281f7e2ac0683205042796958bfd8939f diff --git a/struct/list.c b/struct/list.c index 1920e60..b9ec91f 100644 --- a/struct/list.c +++ b/struct/list.c @@ -55,15 +55,13 @@ list_t *ll_alloc (void) { return ll; } -static node_t *find_pred (node_t **pred_ptr, list_t *ll, const void *key_data, uint32_t key_len, int help_remove) { +static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, const void *key_data, uint32_t key_len, int help_remove) { node_t *pred = ll->head; node_t *item = pred->next; - TRACE("l3", "find_pred: searching for key %p in ll (head is %p)", key_data, pred); + TRACE("l2", "find_pred: searching for key %p in ll (head is %p)", key_data, pred); while (item != NULL) { node_t *next = item->next; - TRACE("l3", "find_pred: visiting item %p (next %p)", item, next); - TRACE("l3", "find_pred: key %p", STRIP_TAG(item->key), item->val); // A tag means an item is logically removed but not physically unlinked yet. while (EXPECT_FALSE(IS_TAGGED(next))) { @@ -73,26 +71,29 @@ static node_t *find_pred (node_t **pred_ptr, list_t *ll, const void *key_data, u item = (node_t *)STRIP_TAG(item->next); if (EXPECT_FALSE(item == NULL)) break; + TRACE("l3", "find_pred: skipping marked item %p (next is %p)", item, next); next = item->next; continue; } // Unlink logically removed items. node_t *other; + TRACE("l3", "find_pred: unlinking marked item %p next is %p", item, next); if ((other = SYNC_CAS(&pred->next, item, STRIP_TAG(next))) == item) { + TRACE("l2", "find_pred: unlinked item %p from pred %p", item, pred); item = (node_t *)STRIP_TAG(next); if (EXPECT_FALSE(item == NULL)) break; next = item->next; - TRACE("l3", "find_pred: unlinked item %p from pred %p", item, pred); - TRACE("l3", "find_pred: now item is %p next is %p", item, next); + 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_defer_free(other); } else { - TRACE("l3", "find_pred: lost race to unlink from pred %p; its link changed to %p", pred, other); + 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)) - return find_pred(pred_ptr, ll, key_data, key_len, help_remove); // retry + return find_pred(pred_ptr, item_ptr, ll, key_data, key_len, help_remove); // retry item = other; if (EXPECT_FALSE(item == NULL)) break; @@ -103,102 +104,173 @@ static node_t *find_pred (node_t **pred_ptr, list_t *ll, const void *key_data, u if (EXPECT_FALSE(item == NULL)) break; + TRACE("l3", "find_pred: visiting item %p (next is %p)", item, next); + TRACE("l4", "find_pred: key %p val %p", STRIP_TAG(item->key), item->val); + + // A tagged key is an integer, otherwise it is a pointer to a string + int d; + if (IS_TAGGED(item->key)) { + d = (STRIP_TAG(item->key) - (uint64_t)key_data); + } else { + int item_key_len = item->key->len; + int len = (key_len < item_key_len) ? key_len : item_key_len; + d = memcmp(item->key->data, key_data, len); + if (d == 0) { d = item_key_len - key_len; } + } + // If we reached the key (or passed where it should be), we found the right predesssor - int x = (IS_TAGGED(item->key)) - ? (STRIP_TAG(item->key) - (uint64_t)key_data) - : ns_cmp_raw(item->key, key_data, key_len); - if (x >= 0) { - TRACE("l3", "find_pred: found pred %p item %p", pred, item); + if (d >= 0) { if (pred_ptr != NULL) { *pred_ptr = pred; } - return x == 0 ? item : NULL; + *item_ptr = item; + if (d == 0) { + TRACE("l2", "find_pred: found matching item %p in list, pred is %p", item, pred); + return TRUE; + } + TRACE("l2", "find_pred: found proper place for key %p in list, pred is %p. returning null", key_data, pred); + return FALSE; } pred = item; item = next; - } // is not in . if (pred_ptr != NULL) { *pred_ptr = pred; } - return NULL; + *item_ptr = NULL; + TRACE("l2", "find_pred: reached end of list. last item is %p", pred, 0); + return FALSE; } // Fast find. Do not help unlink partially removed nodes and do not return the found item's predecessor. uint64_t ll_lookup (list_t *ll, const void *key_data, uint32_t key_len) { - TRACE("l3", "ll_lookup: searching for key %p in list %p", key_data, ll); - node_t *item = find_pred(NULL, ll, key_data, key_len, FALSE); + TRACE("l1", "ll_lookup: searching for key %p in list %p", key_data, ll); + node_t *item; + int found = find_pred(NULL, &item, ll, key_data, key_len, FALSE); // If we found an matching the key return its value. - return item != NULL ? item->val : DOES_NOT_EXIST; + if (found) { + uint64_t val = item->val; + if (val != DOES_NOT_EXIST) { + TRACE("l1", "ll_lookup: found item %p. val %p. returning item", item, item->val); + return val; + } + } + + TRACE("l1", "ll_lookup: no item in the list matched the key", 0, 0); + return DOES_NOT_EXIST; } -// Insert a new item if a matching key doesn't already exist in -uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val) { - assert(new_val != DOES_NOT_EXIST); - TRACE("l3", "ll_cas: inserting key %p val %p", key_data, new_val); +uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t expectation, uint64_t new_val) { + TRACE("l1", "ll_cas: key %p list %p", key_data, ll); + TRACE("l1", "ll_cas: expectation %p new value %p", expectation, new_val); + ASSERT((int64_t)new_val > 0); + + node_t *pred, *old_item; do { - node_t *pred; - node_t *old_item = find_pred(&pred, ll, key_data, key_len, TRUE); + if (!find_pred(&pred, &old_item, ll, key_data, key_len, TRUE)) { - // If a node matching the key already exists in return its value. - if (old_item != NULL) { - TRACE("l3", "ll_cas: there is already an item %p (value %p) with the same key", old_item, old_item->val); - return old_item->val; - } + // There is no existing item in the list that matches the key. + if (EXPECT_FALSE((int64_t)expectation > 0 || expectation == EXPECT_EXISTS)) { + TRACE("l1", "ll_cas: the expectation was not met, the list was not changed", 0, 0); + return DOES_NOT_EXIST; // failure + } + + ASSERT(expectation == EXPECT_DOES_NOT_EXIST || expectation == 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); + node_t *new_item = node_alloc(key_data, key_len, new_val); + node_t *next = new_item->next = old_item; + node_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 + } - TRACE("l3", "ll_cas: attempting to insert item between %p and %p", pred, pred->next); - node_t *new_item = node_alloc(key_data, key_len, new_val); - node_t *next = new_item->next = pred->next; - node_t *other = SYNC_CAS(&pred->next, next, new_item); - if (other == next) { - TRACE("l3", "ll_cas: successfully inserted 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); + node_free(new_item); + continue; // retry } - TRACE("l3", "ll_cas: failed to change pred's link: expected %p found %p", next, other); - node_free(new_item); + // Found an item in the list that matches the key. + uint64_t old_item_val = old_item->val; + 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("l2", "ll_cas: lost a race, found an item but another thread removed it. retry", 0, 0); + break; // retry + } + + if (EXPECT_FALSE(expectation == EXPECT_DOES_NOT_EXIST)) { + TRACE("l1", "ll_cas: found an item %p in the list that matched the key. the expectation was " + "not met, the list was not changed", old_item, old_item_val); + return old_item_val; // failure + } + + // 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. + uint64_t ret_val = SYNC_CAS(&old_item->val, old_item_val, new_val); + if (ret_val == old_item_val) { + TRACE("l1", "ll_cas: the CAS succeeded. updated the value of the item", 0, 0); + return ret_val; // success + } + TRACE("l2", "ll_cas: lost a race. the CAS failed. another thread changed the item's value", 0, 0); + + old_item_val = ret_val; + } while (1); } while (1); } uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len) { - TRACE("l3", "ll_remove: removing item with key %p from list %p", key_data, ll); + TRACE("l1", "ll_remove: removing item with key %p from list %p", key_data, ll); node_t *pred; - node_t *item = find_pred(&pred, ll, key_data, key_len, TRUE); - if (item == NULL) { - TRACE("l3", "ll_remove: remove failed, an item with a matching key does not exist in the list", 0, 0); + node_t *item; + int found = find_pred(&pred, &item, ll, key_data, key_len, TRUE); + if (!found) { + TRACE("l1", "ll_remove: remove failed, an item with a matching key does not exist in the list", 0, 0); return DOES_NOT_EXIST; } // Mark removed. This must be atomic. If multiple threads try to remove the same item // only one of them should succeed. - if (EXPECT_FALSE(IS_TAGGED(item->next))) { - TRACE("l3", "ll_remove: %p is already marked for removal by another thread", item, 0); - return DOES_NOT_EXIST; - } - node_t *next = SYNC_FETCH_AND_OR(&item->next, TAG); - if (EXPECT_FALSE(IS_TAGGED(next))) { - TRACE("l3", "ll_remove: lost race -- %p is already marked for removal by another thread", item, 0); - return DOES_NOT_EXIST; - } + node_t *next; + node_t *old_next = item->next; + do { + next = old_next; + old_next = SYNC_CAS(&item->next, next, TAG_VALUE(next)); + if (IS_TAGGED(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(item->next)); + + // This has to be an atomic swap in case another thread is updating the item while we are removing it. + uint64_t val = SYNC_SWAP(&item->val, DOES_NOT_EXIST); - uint64_t val = item->val; + TRACE("l2", "ll_remove: replaced item's val %p with DOES_NOT_EXIT", val, 0); // Unlink from . If we lose a race to another thread just back off. It is safe to leave the // item logically removed for a later call (or some other thread) to physically unlink. By marking the // item earlier, we logically removed it. - TRACE("l3", "ll_remove: link item's pred %p to it's successor %p", pred, next); + TRACE("l2", "ll_remove: unlink the item by linking its pred %p to its successor %p", pred, next); node_t *other; if ((other = SYNC_CAS(&pred->next, item, next)) != item) { - TRACE("l3", "ll_remove: unlink failed; pred's link changed from %p to %p", item, other); + 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. - node_defer_free(item); + node_defer_free((node_t *)item); + TRACE("l1", "ll_remove: successfully unlinked item %p from the list", item, 0); return val; } @@ -206,13 +278,18 @@ void ll_print (list_t *ll) { node_t *item; item = ll->head->next; while (item) { + node_t *next = item->next; + if (IS_TAGGED(item)) { + printf("*"); + } + printf("%p:", item); if (IS_TAGGED(item->key)) { printf("0x%llx ", STRIP_TAG(item->key)); } else { - printf("%s ", (char *)ns_data(item->key)); + printf("%s ", (char *)item->key->data); } fflush(stdout); - item = item->next; + item = (node_t *)STRIP_TAG(next); } printf("\n"); }