pd.if.org Git - nbds/blob - struct/list.c

   1 /*
   2  * Written by Josh Dybnis and released to the public domain, as explained at
   3  * http://creativecommons.org/licenses/publicdomain
   4  *
   5  * Harris-Michael lock-free list-based set
   6  * http://www.research.ibm.com/people/m/michael/spaa-2002.pdf
   7  */
   8 #include <stdio.h>
   9 #include <string.h>
  10
  11 #include "common.h"
  12 #include "struct.h"
  13 #include "nstring.h"
  14 #include "mem.h"
  15
  16 typedef struct node {
  17     nstring_t *key;
  18     uint64_t val;
  19     struct node *next;
  20 } node_t;
  21
  22 struct ll {
  23     node_t *head;
  24 };
  25
  26 static node_t *node_alloc (const void *key_data, uint32_t key_len, uint64_t val) {
  27     node_t *item = (node_t *)nbd_malloc(sizeof(node_t));
  28     memset(item, 0, sizeof(node_t));
  29     // If <key_len> is -1 it indicates <key_data> is an integer and not a pointer
  30     item->key = (key_len == (unsigned)-1)
  31               ? (void *)TAG_VALUE(key_data)
  32               : ns_alloc(key_data, key_len);
  33     item->val = val;
  34     return item;
  35 }
  36
  37 static void node_free (node_t *item) {
  38     if (!IS_TAGGED(item->key)) {
  39         nbd_free(item->key);
  40     }
  41     nbd_free(item);
  42 }
  43
  44 static void node_defer_free (node_t *item) {
  45     if (!IS_TAGGED(item->key)) {
  46         nbd_defer_free(item->key);
  47     }
  48     nbd_defer_free(item);
  49 }
  50
  51 list_t *ll_alloc (void) {
  52     list_t *ll = (list_t *)nbd_malloc(sizeof(list_t));
  53     ll->head = node_alloc(" ", 0, 0);
  54     ll->head->next = NULL;
  55     return ll;
  56 }
  57
  58 static node_t *find_pred (node_t **pred_ptr, list_t *ll, const void *key_data, uint32_t key_len, int help_remove) {
  59     node_t *pred = ll->head;
  60     node_t *item = pred->next;
  61     TRACE("l3", "find_pred: searching for key %p in ll (head is %p)", key_data, pred);
  62
  63     while (item != NULL) {
  64         node_t *next = item->next;
  65         TRACE("l3", "find_pred: visiting item %p (next %p)", item, next);
  66         TRACE("l3", "find_pred: key %p", STRIP_TAG(item->key), item->val);
  67
  68         // A tag means an item is logically removed but not physically unlinked yet.
  69         while (EXPECT_FALSE(IS_TAGGED(next))) {
  70
  71             // Skip over logically removed items.
  72             if (!help_remove) {
  73                 item = (node_t *)STRIP_TAG(item->next);
  74                 if (EXPECT_FALSE(item == NULL))
  75                     break;
  76                 next = item->next;
  77                 continue;
  78             }
  79
  80             // Unlink logically removed items.
  81             node_t *other;
  82             if ((other = SYNC_CAS(&pred->next, item, STRIP_TAG(next))) == item) {
  83                 item = (node_t *)STRIP_TAG(next);
  84                 if (EXPECT_FALSE(item == NULL))
  85                     break;
  86                 next = item->next;
  87                 TRACE("l3", "find_pred: unlinked item %p from pred %p", item, pred);
  88                 TRACE("l3", "find_pred: now item is %p next is %p", item, next);
  89
  90                 // The thread that completes the unlink should free the memory.
  91                 node_defer_free(other);
  92             } else {
  93                 TRACE("l3", "find_pred: lost race to unlink from pred %p; its link changed to %p", pred, other);
  94                 if (IS_TAGGED(other))
  95                     return find_pred(pred_ptr, ll, key_data, key_len, help_remove); // retry
  96                 item = other;
  97                 if (EXPECT_FALSE(item == NULL))
  98                     break;
  99                 next = item->next;
 100             }
 101         }
 102
 103         if (EXPECT_FALSE(item == NULL))
 104             break;
 105
 106         // If we reached the key (or passed where it should be), we found the right predesssor
 107         int x = (IS_TAGGED(item->key))
 108               ? (STRIP_TAG(item->key) - (uint64_t)key_data)
 109               : ns_cmp_raw(item->key, key_data, key_len);
 110         if (x >= 0) {
 111             TRACE("l3", "find_pred: found pred %p item %p", pred, item);
 112             if (pred_ptr != NULL) {
 113                 *pred_ptr = pred;
 114             }
 115             return x == 0 ? item : NULL;
 116         }
 117
 118         pred = item;
 119         item = next;
 120
 121     }
 122
 123     // <key> is not in <ll>.
 124     if (pred_ptr != NULL) {
 125         *pred_ptr = pred;
 126     }
 127     return NULL;
 128 }
 129
 130 // Fast find. Do not help unlink partially removed nodes and do not return the found item's predecessor.
 131 uint64_t ll_lookup (list_t *ll, const void *key_data, uint32_t key_len) {
 132     TRACE("l3", "ll_lookup: searching for key %p in list %p", key_data, ll);
 133     node_t *item = find_pred(NULL, ll, key_data, key_len, FALSE);
 134
 135     // If we found an <item> matching the key return its value.
 136     return item != NULL ? item->val : DOES_NOT_EXIST;
 137 }
 138
 139 // Insert a new item if a matching key doesn't already exist in <ll>
 140 uint64_t ll_cas (list_t *ll, const void *key_data, uint32_t key_len, uint64_t expected_val, uint64_t new_val) {
 141     assert(new_val != DOES_NOT_EXIST);
 142     TRACE("l3", "ll_cas: inserting key %p val %p", key_data, new_val);
 143     do {
 144         node_t *pred;
 145         node_t *old_item = find_pred(&pred, ll, key_data, key_len, TRUE);
 146
 147         // If a node matching the key already exists in <ll> return its value.
 148         if (old_item != NULL) {
 149             TRACE("l3", "ll_cas: there is already an item %p (value %p) with the same key", old_item, old_item->val);
 150             return old_item->val;
 151         }
 152
 153         TRACE("l3", "ll_cas: attempting to insert item between %p and %p", pred, pred->next);
 154         node_t *new_item = node_alloc(key_data, key_len, new_val);
 155         node_t *next = new_item->next = pred->next;
 156         node_t *other = SYNC_CAS(&pred->next, next, new_item);
 157         if (other == next) {
 158             TRACE("l3", "ll_cas: successfully inserted item %p", new_item, 0);
 159             return DOES_NOT_EXIST; // success
 160         }
 161         TRACE("l3", "ll_cas: failed to change pred's link: expected %p found %p", next, other);
 162         node_free(new_item);
 163
 164     } while (1);
 165 }
 166
 167 uint64_t ll_remove (list_t *ll, const void *key_data, uint32_t key_len) {
 168     TRACE("l3", "ll_remove: removing item with key %p from list %p", key_data, ll);
 169     node_t *pred;
 170     node_t *item = find_pred(&pred, ll, key_data, key_len, TRUE);
 171     if (item == NULL) {
 172         TRACE("l3", "ll_remove: remove failed, an item with a matching key does not exist in the list", 0, 0);
 173         return DOES_NOT_EXIST;
 174     }
 175
 176     // Mark <item> removed. This must be atomic. If multiple threads try to remove the same item
 177     // only one of them should succeed.
 178     if (EXPECT_FALSE(IS_TAGGED(item->next))) {
 179         TRACE("l3", "ll_remove: %p is already marked for removal by another thread", item, 0);
 180         return DOES_NOT_EXIST;
 181     }
 182     node_t *next = SYNC_FETCH_AND_OR(&item->next, TAG);
 183     if (EXPECT_FALSE(IS_TAGGED(next))) {
 184         TRACE("l3", "ll_remove: lost race -- %p is already marked for removal by another thread", item, 0);
 185         return DOES_NOT_EXIST;
 186     }
 187
 188     uint64_t val = item->val;
 189
 190     // Unlink <item> from <ll>. If we lose a race to another thread just back off. It is safe to leave the
 191     // item logically removed for a later call (or some other thread) to physically unlink. By marking the
 192     // item earlier, we logically removed it.
 193     TRACE("l3", "ll_remove: link item's pred %p to it's successor %p", pred, next);
 194     node_t *other;
 195     if ((other = SYNC_CAS(&pred->next, item, next)) != item) {
 196         TRACE("l3", "ll_remove: unlink failed; pred's link changed from %p to %p", item, other);
 197         return val;
 198     }
 199
 200     // The thread that completes the unlink should free the memory.
 201     node_defer_free(item);
 202     return val;
 203 }
 204
 205 void ll_print (list_t *ll) {
 206     node_t *item;
 207     item = ll->head->next;
 208     while (item) {
 209         if (IS_TAGGED(item->key)) {
 210             printf("0x%llx ", STRIP_TAG(item->key));
 211         } else {
 212             printf("%s ", (char *)ns_data(item->key));
 213         }
 214         fflush(stdout);
 215         item = item->next;
 216     }
 217     printf("\n");
 218 }