pd.if.org Git - nbds/blob - map/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
   9 #include <stdio.h>
  10 #include <string.h>
  11
  12 #include "common.h"
  13 #include "list.h"
  14 #include "mem.h"
  15
  16 typedef struct node {
  17     void *key;
  18     uint64_t val;
  19     struct node *next;
  20 } node_t;
  21
  22 struct ll {
  23     node_t *head;
  24     const datatype_t *key_type;
  25 };
  26
  27 static node_t *node_alloc (void *key, uint64_t val) {
  28     node_t *item = (node_t *)nbd_malloc(sizeof(node_t));
  29     item->key = key;
  30     item->val = val;
  31     return item;
  32 }
  33
  34 list_t *ll_alloc (const datatype_t *key_type) {
  35     list_t *ll = (list_t *)nbd_malloc(sizeof(list_t));
  36     ll->key_type = key_type;
  37     ll->head = node_alloc(NULL, 0);
  38     ll->head->next = NULL;
  39     return ll;
  40 }
  41
  42 void ll_free (list_t *ll) {
  43     node_t *item = ll->head->next;
  44     while (item) {
  45         node_t *next = (node_t *)STRIP_TAG(item->next, TAG1);
  46         nbd_free(item);
  47         item = next;
  48     }
  49 }
  50
  51 uint64_t ll_count (list_t *ll) {
  52     uint64_t count = 0;
  53     node_t *item = ll->head->next;
  54     while (item) {
  55         if (!IS_TAGGED(item->next, TAG1)) {
  56             count++;
  57         }
  58         item = (node_t *)STRIP_TAG(item->next, TAG1);
  59     }
  60     return count;
  61 }
  62
  63 static int find_pred (node_t **pred_ptr, node_t **item_ptr, list_t *ll, void *key, int help_remove) {
  64     node_t *pred = ll->head;
  65     node_t *item = pred->next;
  66     TRACE("l2", "find_pred: searching for key %p in list (head is %p)", key, pred);
  67
  68     while (item != NULL) {
  69         node_t *next = item->next;
  70
  71         // A tag means an item is logically removed but not physically unlinked yet.
  72         while (EXPECT_FALSE(IS_TAGGED(next, TAG1))) {
  73
  74             // Skip over logically removed items.
  75             if (!help_remove) {
  76                 item = (node_t *)STRIP_TAG(item->next, TAG1);
  77                 if (EXPECT_FALSE(item == NULL))
  78                     break;
  79                 TRACE("l3", "find_pred: skipping marked item %p (next is %p)", item, next);
  80                 next = item->next;
  81                 continue;
  82             }
  83
  84             // Unlink logically removed items.
  85             node_t *other;
  86             TRACE("l3", "find_pred: unlinking marked item %p next is %p", item, next);
  87             if ((other = SYNC_CAS(&pred->next, item, STRIP_TAG(next, TAG1))) == item) {
  88                 TRACE("l2", "find_pred: unlinked item %p from pred %p", item, pred);
  89                 item = (node_t *)STRIP_TAG(next, TAG1);
  90                 if (EXPECT_FALSE(item == NULL))
  91                     break;
  92                 next = item->next;
  93                 TRACE("l3", "find_pred: now current item is %p next is %p", item, next);
  94
  95                 // The thread that completes the unlink should free the memory.
  96                 if (ll->key_type != NULL) {
  97                     nbd_defer_free((void*)other->key);
  98                 }
  99                 nbd_defer_free(other);
 100             } else {
 101                 TRACE("l2", "find_pred: lost a race to unlink item %p from pred %p", item, pred);
 102                 TRACE("l2", "find_pred: pred's link changed to %p", other, 0);
 103                 if (IS_TAGGED(other, TAG1))
 104                     return find_pred(pred_ptr, item_ptr, ll, key, help_remove); // retry
 105                 item = other;
 106                 if (EXPECT_FALSE(item == NULL))
 107                     break;
 108                 next = item->next;
 109             }
 110         }
 111
 112         if (EXPECT_FALSE(item == NULL))
 113             break;
 114
 115         TRACE("l3", "find_pred: visiting item %p (next is %p)", item, next);
 116         TRACE("l4", "find_pred: key %p val %p", item->key, item->val);
 117
 118         int d;
 119         if (EXPECT_TRUE(ll->key_type == NULL)) {
 120             d = (uint64_t)item->key - (uint64_t)key;
 121         } else {
 122             d = ll->key_type->cmp(item->key, key);
 123         }
 124
 125         // If we reached the key (or passed where it should be), we found the right predesssor
 126         if (d >= 0) {
 127             if (pred_ptr != NULL) {
 128                 *pred_ptr = pred;
 129             }
 130             *item_ptr = item;
 131             if (d == 0) {
 132                 TRACE("l2", "find_pred: found matching item %p in list, pred is %p", item, pred);
 133                 return TRUE;
 134             }
 135             TRACE("l2", "find_pred: found proper place for key %p in list, pred is %p", key, pred);
 136             return FALSE;
 137         }
 138
 139         pred = item;
 140         item = next;
 141     }
 142
 143     // <key> is not in <ll>.
 144     if (pred_ptr != NULL) {
 145         *pred_ptr = pred;
 146     }
 147     *item_ptr = NULL;
 148     TRACE("l2", "find_pred: reached end of list. last item is %p", pred, 0);
 149     return FALSE;
 150 }
 151
 152 // Fast find. Do not help unlink partially removed nodes and do not return the found item's predecessor.
 153 uint64_t ll_lookup (list_t *ll, void *key) {
 154     TRACE("l1", "ll_lookup: searching for key %p in list %p", key, ll);
 155     node_t *item;
 156     int found = find_pred(NULL, &item, ll, key, FALSE);
 157
 158     // If we found an <item> matching the key return its value.
 159     if (found) {
 160         uint64_t val = item->val;
 161         if (val != DOES_NOT_EXIST) {
 162             TRACE("l1", "ll_lookup: found item %p. val %p. returning item", item, item->val);
 163             return val;
 164         }
 165     }
 166
 167     TRACE("l1", "ll_lookup: no item in the list matched the key", 0, 0);
 168     return DOES_NOT_EXIST;
 169 }
 170
 171 uint64_t ll_cas (list_t *ll, void *key, uint64_t expectation, uint64_t new_val) {
 172     TRACE("l1", "ll_cas: key %p list %p", key, ll);
 173     TRACE("l1", "ll_cas: expectation %p new value %p", expectation, new_val);
 174     ASSERT((int64_t)new_val > 0);
 175
 176     do {
 177         node_t *pred, *old_item;
 178         int found = find_pred(&pred, &old_item, ll, key, TRUE);
 179         if (!found) {
 180
 181             // There was not an item in the list that matches the key.
 182             if (EXPECT_FALSE((int64_t)expectation > 0 || expectation == CAS_EXPECT_EXISTS)) {
 183                 TRACE("l1", "ll_cas: the expectation was not met, the list was not changed", 0, 0);
 184                 return DOES_NOT_EXIST; // failure
 185             }
 186
 187             ASSERT(expectation == CAS_EXPECT_DOES_NOT_EXIST || expectation == CAS_EXPECT_WHATEVER);
 188
 189             // Create a new item and insert it into the list.
 190             TRACE("l2", "ll_cas: attempting to insert item between %p and %p", pred, pred->next);
 191             void *new_key  = (ll->key_type == NULL) ? key : ll->key_type->clone(key);
 192             node_t *new_item = node_alloc(new_key, new_val);
 193             node_t *next = new_item->next = old_item;
 194             node_t *other = SYNC_CAS(&pred->next, next, new_item);
 195             if (other == next) {
 196                 TRACE("l1", "ll_cas: successfully inserted new item %p", new_item, 0);
 197                 return DOES_NOT_EXIST; // success
 198             }
 199
 200             // Lost a race. Failed to insert the new item into the list.
 201             TRACE("l1", "ll_cas: lost a race. CAS failed. expected pred's link to be %p but found %p", next, other);
 202             if (ll->key_type != NULL) {
 203                 nbd_free(new_key);
 204             }
 205             nbd_free(new_item);
 206             continue; // retry
 207         }
 208
 209         // Found an item in the list that matches the key.
 210         uint64_t old_item_val = old_item->val;
 211         do {
 212             // If the item's value is DOES_NOT_EXIST it means another thread removed the node out from under us.
 213             if (EXPECT_FALSE(old_item_val == DOES_NOT_EXIST)) {
 214                 TRACE("l2", "ll_cas: lost a race, found an item but another thread removed it. retry", 0, 0);
 215                 break; // retry
 216             }
 217
 218             if (EXPECT_FALSE(expectation == CAS_EXPECT_DOES_NOT_EXIST)) {
 219                 TRACE("l1", "ll_cas: found an item %p in the list that matched the key. the expectation was "
 220                         "not met, the list was not changed", old_item, old_item_val);
 221                 return old_item_val; // failure
 222             }
 223
 224             // Use a CAS and not a SWAP. If the node is in the process of being removed and we used a SWAP, we could
 225             // replace DOES_NOT_EXIST with our value. Then another thread that is updating the value could think it
 226             // succeeded and return our value even though we indicated that the node has been removed. If the CAS
 227             // fails it means another thread either removed the node or updated its value.
 228             uint64_t ret_val = SYNC_CAS(&old_item->val, old_item_val, new_val);
 229             if (ret_val == old_item_val) {
 230                 TRACE("l1", "ll_cas: the CAS succeeded. updated the value of the item", 0, 0);
 231                 return ret_val; // success
 232             }
 233             TRACE("l2", "ll_cas: lost a race. the CAS failed. another thread changed the item's value", 0, 0);
 234
 235             old_item_val = ret_val;
 236         } while (1);
 237     } while (1);
 238 }
 239
 240 uint64_t ll_remove (list_t *ll, void *key) {
 241     TRACE("l1", "ll_remove: removing item with key %p from list %p", key, ll);
 242     node_t *pred;
 243     node_t *item;
 244     int found = find_pred(&pred, &item, ll, key, TRUE);
 245     if (!found) {
 246         TRACE("l1", "ll_remove: remove failed, an item with a matching key does not exist in the list", 0, 0);
 247         return DOES_NOT_EXIST;
 248     }
 249
 250     // Mark <item> removed. If multiple threads try to remove the same item only one of them should succeed.
 251     node_t *next;
 252     node_t *old_next = item->next;
 253     do {
 254         next = old_next;
 255         old_next = SYNC_CAS(&item->next, next, TAG_VALUE(next, TAG1));
 256         if (IS_TAGGED(old_next, TAG1)) {
 257             TRACE("l1", "ll_remove: lost a race -- %p is already marked for removal by another thread", item, 0);
 258             return DOES_NOT_EXIST;
 259         }
 260     } while (next != old_next);
 261     TRACE("l2", "ll_remove: logically removed item %p", item, 0);
 262     ASSERT(IS_TAGGED(item->next, TAG1));
 263
 264     // Atomically swap out the item's value in case another thread is updating the item while we are
 265     // removing it. This establishes which operation occurs first logically, the update or the remove.
 266     uint64_t val = SYNC_SWAP(&item->val, DOES_NOT_EXIST);
 267     TRACE("l2", "ll_remove: replaced item's val %p with DOES_NOT_EXIT", val, 0);
 268
 269     // Unlink <item> from <ll>. If we lose a race to another thread just back off. It is safe to leave the
 270     // item logically removed for a later call (or some other thread) to physically unlink. By marking the
 271     // item earlier, we logically removed it.
 272     TRACE("l2", "ll_remove: unlink the item by linking its pred %p to its successor %p", pred, next);
 273     node_t *other;
 274     if ((other = SYNC_CAS(&pred->next, item, next)) != item) {
 275         TRACE("l1", "ll_remove: unlink failed; pred's link changed from %p to %p", item, other);
 276         return val;
 277     }
 278
 279     // The thread that completes the unlink should free the memory.
 280     if (ll->key_type != NULL) {
 281         nbd_defer_free(item->key);
 282     }
 283     nbd_defer_free(item);
 284     TRACE("l1", "ll_remove: successfully unlinked item %p from the list", item, 0);
 285     return val;
 286 }
 287
 288 void ll_print (list_t *ll) {
 289     node_t *item;
 290     item = ll->head->next;
 291     int i = 0;
 292     while (item) {
 293         node_t *next = item->next;
 294         if (IS_TAGGED(item, TAG1)) {
 295             printf("*");
 296         }
 297         printf("%p:%p ", item, item->key);
 298         fflush(stdout);
 299         item = (node_t *)STRIP_TAG(next, TAG1);
 300         if (i++ > 30) {
 301             printf("...");
 302             break;
 303         }
 304     }
 305     printf("\n");
 306 }