X-Git-Url: https://pd.if.org/git/?p=nbds;a=blobdiff_plain;f=struct%2Flist.c;h=5849247abd9a2a59f188c3e244d97acdd472643f;hp=aa28b85190ddcdc330bd3bb38ac35d36721e6b45;hb=2d93f3b29622488bde80b6cd18661fd7eb603eee;hpb=269f52d6f8cd031692c83afaa05c389115d05bd0 diff --git a/struct/list.c b/struct/list.c index aa28b85..5849247 100644 --- a/struct/list.c +++ b/struct/list.c @@ -10,268 +10,285 @@ #include "common.h" #include "struct.h" +#include "nstring.h" #include "mem.h" typedef struct node { - uint64_t key; - uint64_t value; + nstring_t *key; + uint64_t val; struct node *next; } node_t; -typedef struct list { +struct ll { node_t *head; - node_t *last; -} list_t; +}; -node_t *node_alloc (uint64_t key, uint64_t value) { +static node_t *node_alloc (const void *key_data, uint32_t key_len, uint64_t val) { node_t *item = (node_t *)nbd_malloc(sizeof(node_t)); memset(item, 0, sizeof(node_t)); - item->key = key; - item->value = value; + // If is -1 it indicates is an integer and not a pointer + item->key = (key_len == (unsigned)-1) + ? (void *)TAG_VALUE(key_data) + : ns_alloc(key_data, key_len); + item->val = val; return item; } -list_t *list_alloc (void) { - list_t *list = (list_t *)nbd_malloc(sizeof(list_t)); - list->head = node_alloc(0, 0); - list->last = node_alloc((uint64_t)-1, 0); - list->head->next = list->last; - return list; +static void node_free (node_t *item) { + if (!IS_TAGGED(item->key)) { + nbd_free(item->key); + } + nbd_free(item); +} + +static void node_defer_free (node_t *item) { + if (!IS_TAGGED(item->key)) { + nbd_defer_free(item->key); + } + nbd_defer_free(item); +} + +list_t *ll_alloc (void) { + list_t *ll = (list_t *)nbd_malloc(sizeof(list_t)); + ll->head = node_alloc(" ", 0, 0); + ll->head->next = NULL; + return ll; } -static node_t *find_pred (node_t **pred_ptr, list_t *list, uint64_t key, int help_remove) { - node_t *pred = list->head; +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 list (head is %p)", key, pred); -#ifndef NDEBUG - int count = 0; -#endif + TRACE("l2", "find_pred: searching for key %p in ll (head is %p)", key_data, pred); - do { + 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 value %p", item->key, item->value); - // Marked items are partially removed. + // A tag means an item is logically removed but not physically unlinked yet. while (EXPECT_FALSE(IS_TAGGED(next))) { - // Skip over partially removed items. + // Skip over logically removed items. if (!help_remove) { 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 partially removed items. + // 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 is the new item (next is %p)", item, next); - nbd_defer_free(other); + 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 item 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, list, key, 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; next = item->next; } } + 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 - if (item->key >= key) { - TRACE("l3", "find_pred: returning pred %p and item %p", pred, item); + if (d >= 0) { if (pred_ptr != NULL) { *pred_ptr = pred; } - return item; + *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", key_data, pred); + return FALSE; } - assert(count++ < 18); pred = item; item = next; + } - } while (1); + // is not in . + if (pred_ptr != NULL) { + *pred_ptr = pred; + } + *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 list_lookup (list_t *list, uint64_t key) { - TRACE("l3", "list_lookup: searching for key %p in list %p", key, list); - node_t *item = find_pred(NULL, list, key, FALSE); +uint64_t ll_lookup (list_t *ll, const void *key_data, uint32_t key_len) { + 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. + 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; + } + } - // If we found an matching the return its value. - return (item->key == key) ? item->value : DOES_NOT_EXIST; + TRACE("l1", "ll_lookup: no item in the list matched the key", 0, 0); + return DOES_NOT_EXIST; } -// Insert the , if it doesn't already exist in the -uint64_t list_add (list_t *list, uint64_t key, uint64_t value) { - TRACE("l3", "list_add: inserting key %p value %p", key, value); - node_t *pred; - node_t *item = NULL; +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); + do { - node_t *next = find_pred(&pred, list, key, TRUE); + node_t *pred, *old_item; + if (!find_pred(&pred, &old_item, ll, key_data, key_len, TRUE)) { - // If a node matching already exists in the list, return its value. - if (next->key == key) { - TRACE("l3", "list_add: there is already an item %p (value %p) with the same key", next, next->value); - if (EXPECT_FALSE(item != NULL)) { nbd_free(item); } - return next->value; - } + // There was not an 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", "list_add: attempting to insert item between %p and %p", pred, next); - if (EXPECT_TRUE(item == NULL)) { item = node_alloc(key, value); } - item->next = next; - node_t *other = SYNC_CAS(&pred->next, next, item); - if (other == next) { - TRACE("l3", "list_add: insert was successful", 0, 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", "list_add: failed to change pred's link: expected %p found %p", next, other); + // 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 list_remove (list_t *list, uint64_t key) { - TRACE("l3", "list_remove: removing item with key %p from list %p", key, list); +uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len) { + TRACE("l1", "ll_remove: removing item with key %p from list %p", key_data, ll); node_t *pred; - node_t *item = find_pred(&pred, list, key, TRUE); - if (item->key != key) { - TRACE("l3", "list_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", "list_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", "list_remove: lost race -- %p is already marked for removal by another thread", item, 0); - return DOES_NOT_EXIST; - } - - uint64_t value = item->value; - - // Unlink from the list. - TRACE("l3", "list_remove: link item's pred %p to it's successor %p", pred, next); + 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); + 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("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", "list_remove: unlink failed; pred's link changed from %p to %p", item, other); - // By being marked, the item was logically removed. It is safe to leave it for - // another thread to finish physically removing it from the skiplist. - return value; + 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. - nbd_defer_free(item); - return value; + node_defer_free(item); + TRACE("l1", "ll_remove: successfully unlinked item %p from the list", item, 0); + return val; } -void list_print (list_t *list) { +void ll_print (list_t *ll) { node_t *item; - item = list->head; + item = ll->head->next; while (item) { - printf("0x%llx ", item->key); - fflush(stdout); - item = item->next; - } - printf("\n"); -} - -#ifdef MAKE_list_test -#include -#include -#include - -#include "runtime.h" - -#define NUM_ITERATIONS 10000000 - -static volatile int wait_; -static long num_threads_; -static list_t *list_; - -void *worker (void *arg) { - int id = (int)(size_t)arg; - - unsigned int rand_seed = id+1;//rdtsc_l(); - - // Wait for all the worker threads to be ready. - SYNC_ADD(&wait_, -1); - do {} while (wait_); - __asm__ __volatile__("lfence"); - - for (int i = 0; i < NUM_ITERATIONS/num_threads_; ++i) { - int n = rand_r(&rand_seed); - int key = (n & 0xF) + 1; - if (n & (1 << 8)) { - list_add(list_, key, 1); - } else { - list_remove(list_, key); - } - - rcu_update(); - } - - return NULL; -} - -int main (int argc, char **argv) { - nbd_init(); - //lwt_set_trace_level("m0l0"); - - char* program_name = argv[0]; - pthread_t thread[MAX_NUM_THREADS]; - - if (argc > 2) { - fprintf(stderr, "Usage: %s num_threads\n", program_name); - return -1; - } - - num_threads_ = 2; - if (argc == 2) - { - errno = 0; - num_threads_ = strtol(argv[1], NULL, 10); - if (errno) { - fprintf(stderr, "%s: Invalid argument for number of threads\n", program_name); - return -1; - } - if (num_threads_ <= 0) { - fprintf(stderr, "%s: Number of threads must be at least 1\n", program_name); - return -1; + node_t *next = item->next; + if (IS_TAGGED(item)) { + printf("*"); } - if (num_threads_ > MAX_NUM_THREADS) { - fprintf(stderr, "%s: Number of threads cannot be more than %d\n", program_name, MAX_NUM_THREADS); - return -1; + printf("%p:", item); + if (IS_TAGGED(item->key)) { + printf("0x%llx ", STRIP_TAG(item->key)); + } else { + printf("%s ", (char *)item->key->data); } + fflush(stdout); + item = (node_t *)STRIP_TAG(next); } - - list_ = list_alloc(); - - struct timeval tv1, tv2; - gettimeofday(&tv1, NULL); - - __asm__ __volatile__("sfence"); - wait_ = num_threads_; - - for (int i = 0; i < num_threads_; ++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) { - pthread_join(thread[i], NULL); - } - - gettimeofday(&tv2, NULL); - int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000; - printf("Th:%ld Time:%dms\n", num_threads_, ms); - list_print(list_); - lwt_dump("lwt.out"); - - return 0; + printf("\n"); } -#endif//list_test