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

   1 /*
   2  * Written by Josh Dybnis and released to the public domain, as explained at
   3  * http://creativecommons.org/licenses/publicdomain
   4  *
   5  * Implementation of the lock-free skiplist data-structure created by Maurice Herlihy, Yossi Lev,
   6  * and Nir Shavit. See Herlihy's and Shivit's book "The Art of Multiprocessor Programming".
   7  * http://www.amazon.com/Art-Multiprocessor-Programming-Maurice-Herlihy/dp/0123705916/
   8  *
   9  * See also Kir Fraser's dissertation "Practical Lock Freedom".
  10  * www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf
  11  *
  12  * This code is written for the x86 memory-model. The algorithim depends on certain stores and
  13  * loads being ordered. Be careful, this code probably won't work correctly on platforms with
  14  * weaker memory models if you don't add memory barriers in the right places.
  15  */
  16 #include <stdio.h>
  17 #include <string.h>
  18
  19 #include "common.h"
  20 #include "runtime.h"
  21 #include "struct.h"
  22 #include "nstring.h"
  23 #include "mem.h"
  24 #include "tls.h"
  25
  26 // Setting MAX_LEVEL to 0 essentially makes this data structure the Harris-Michael lock-free list
  27 // in list.c
  28 #define MAX_LEVEL 31
  29
  30 typedef struct node {
  31     nstring_t *key;
  32     uint64_t value;
  33     int top_level;
  34     struct node *next[];
  35 } node_t;
  36
  37 struct sl {
  38     node_t *head;
  39 };
  40
  41 static int random_level (void) {
  42     unsigned r = nbd_rand();
  43     if (r&1)
  44         return 0;
  45     int n = __builtin_ctz(r)-1;
  46 #if MAX_LEVEL < 31
  47     if (n > MAX_LEVEL)
  48         return MAX_LEVEL;
  49 #endif
  50     assert(n <= MAX_LEVEL);
  51     return n;
  52 }
  53
  54 node_t *node_alloc (int level, const void *key_data, uint32_t key_len, uint64_t value) {
  55     assert(level >= 0 && level <= MAX_LEVEL);
  56     size_t sz = sizeof(node_t) + (level + 1) * sizeof(node_t *);
  57     node_t *item = (node_t *)nbd_malloc(sz);
  58     memset(item, 0, sz);
  59     item->key   = ns_alloc(key_data, key_len);
  60     item->value = value;
  61     item->top_level = level;
  62     return item;
  63 }
  64
  65 skiplist_t *sl_alloc (void) {
  66     skiplist_t *sl = (skiplist_t *)nbd_malloc(sizeof(skiplist_t));
  67     sl->head = node_alloc(MAX_LEVEL, " ", 0, 0);
  68     memset(sl->head->next, 0, (MAX_LEVEL+1) * sizeof(skiplist_t *));
  69     return sl;
  70 }
  71
  72 static node_t *find_preds (int *found, node_t *preds[MAX_LEVEL+1], int n, skiplist_t *sl, const void *key_data, uint32_t key_len, int help_remove) {
  73     node_t *pred = sl->head;
  74     node_t *item = NULL;
  75     TRACE("s3", "find_preds: searching for key %p in sl (head is %p)", key_data, pred);
  76     *found = 0;
  77
  78     int start_level = MAX_LEVEL;
  79 #if MAX_LEVEL > 2
  80     // Optimization for small lists. No need to traverse empty higher levels.
  81     start_level = 2;
  82     while (pred->next[start_level+1] != NULL) {
  83         start_level += start_level - 1;
  84         if (EXPECT_FALSE(start_level >= MAX_LEVEL)) {
  85             start_level = MAX_LEVEL;
  86             break;
  87         }
  88     }
  89     if (EXPECT_FALSE(start_level < n)) {
  90         start_level = n;
  91     }
  92 #endif
  93
  94     // Traverse the levels of <sl> from the top level to the bottom
  95     for (int level = start_level; level >= 0; --level) {
  96         TRACE("s3", "find_preds: level %llu", level, 0);
  97         item = pred->next[level];
  98         if (EXPECT_FALSE(IS_TAGGED(item))) {
  99             TRACE("s3", "find_preds: pred %p is marked for removal (item %p); retry", pred, item);
 100             return find_preds(found, preds, n, sl, key_data, key_len, help_remove); // retry
 101         }
 102         while (item != NULL) {
 103             node_t *next = item->next[level];
 104             TRACE("s3", "find_preds: visiting item %p (next %p)", item, next);
 105             TRACE("s3", "find_preds: key %p", item->key, 0);
 106
 107             // A tag means an item is logically removed but not physically unlinked yet.
 108             while (EXPECT_FALSE(IS_TAGGED(next))) {
 109
 110                 // Skip over logically removed items.
 111                 if (!help_remove) {
 112                     item = (node_t *)STRIP_TAG(item->next);
 113                     if (EXPECT_FALSE(item == NULL))
 114                         break;
 115                     next = item->next[level];
 116                     continue;
 117                 }
 118
 119                 // Unlink logically removed items.
 120                 node_t *other;
 121                 if ((other = SYNC_CAS(&pred->next[level], item, STRIP_TAG(next))) == item) {
 122                     item = (node_t *)STRIP_TAG(next);
 123                     if (EXPECT_FALSE(item == NULL))
 124                         break;
 125                     next = item->next[level];
 126                     TRACE("s3", "find_preds: unlinked item %p from pred %p", item, pred);
 127                     TRACE("s3", "find_preds: now item is %p next is %p", item, next);
 128
 129                     // The thread that completes the unlink should free the memory.
 130                     if (level == 0) { nbd_defer_free(other); }
 131                 } else {
 132                     TRACE("s3", "find_preds: lost race to unlink from pred %p; its link changed to %p", pred, other);
 133                     if (IS_TAGGED(other))
 134                         return find_preds(found, preds, n, sl, key_data, key_len, help_remove); // retry
 135                     item = other;
 136                     if (EXPECT_FALSE(item == NULL))
 137                         break;
 138                     next = item->next[level];
 139                 }
 140             }
 141
 142             if (EXPECT_FALSE(item == NULL))
 143                 break;
 144
 145             // If we reached the key (or passed where it should be), we found a pred. Save it and continue down.
 146             int x = ns_cmp_raw(item->key, key_data, key_len);
 147             if (x >= 0) {
 148                 if (level == 0 && x == 0) {
 149                     *found = 1;
 150                 }
 151                 TRACE("s3", "find_preds: found pred %p item %p", pred, item);
 152                 break;
 153             }
 154
 155             pred = item;
 156             item = next;
 157         }
 158         if (preds != NULL) {
 159             preds[level] = pred;
 160         }
 161     }
 162     if (n == -1 && item != NULL) {
 163         assert(preds != NULL);
 164         for (int level = start_level + 1; level <= item->top_level; ++level) {
 165             preds[level] = sl->head;
 166         }
 167     }
 168     return item;
 169 }
 170
 171 // Fast find that does not help unlink partially removed nodes and does not return the node's predecessors.
 172 uint64_t sl_lookup (skiplist_t *sl, const void *key_data, uint32_t key_len) {
 173     TRACE("s3", "sl_lookup: searching for key %p in sl %p", key, sl);
 174     int found;
 175     node_t *item = find_preds(&found, NULL, 0, sl, key_data, key_len, FALSE);
 176
 177     // If we found an <item> matching the <key> return its value.
 178     return found ? item->value : DOES_NOT_EXIST;
 179 }
 180
 181 // Insert the <key> if it doesn't already exist in <sl>
 182 uint64_t sl_add (skiplist_t *sl, const void *key_data, uint32_t key_len, uint64_t value) {
 183     TRACE("s3", "sl_add: inserting key %p value %p", key, value);
 184     node_t *preds[MAX_LEVEL+1];
 185     node_t *item = NULL;
 186     int n = random_level();
 187     do {
 188         int found;
 189         node_t *next = find_preds(&found, preds, n, sl, key_data, key_len, TRUE);
 190
 191         // If a node matching <key> already exists in <sl>, return its value.
 192         if (found) {
 193             TRACE("s3", "sl_add: there is already an item %p (value %p) with the same key", next, next->value);
 194             if (EXPECT_FALSE(item != NULL)) { nbd_free(item); }
 195             return next->value;
 196         }
 197
 198         // First insert <item> into the bottom level.
 199         if (EXPECT_TRUE(item == NULL)) { item = node_alloc(n, key_data, key_len, value); }
 200         TRACE("s3", "sl_add: attempting to insert item between %p and %p", preds[0], next);
 201         item->next[0] = next;
 202         for (int level = 1; level <= item->top_level; ++level) {
 203             node_t *pred = preds[level];
 204             item->next[level] = pred->next[level];
 205         }
 206         node_t *pred = preds[0];
 207         node_t *other = SYNC_CAS(&pred->next[0], next, item);
 208         if (other == next) {
 209             TRACE("s3", "sl_add: successfully inserted item %p at level 0", item, 0);
 210             break; // success
 211         }
 212         TRACE("s3", "sl_add: failed to change pred's link: expected %p found %p", next, other);
 213
 214     } while (1);
 215
 216     // Insert <item> into <sl> from the bottom level up.
 217     for (int level = 1; level <= item->top_level; ++level) {
 218         do {
 219             node_t *pred;
 220             node_t *next;
 221             do {
 222                 pred = preds[level];
 223                 next = pred->next[level];
 224                 if (next == NULL) // item goes at the end of the list
 225                     break;
 226                 if (!IS_TAGGED(next) && ns_cmp_raw(next->key, key_data, key_len) > 0) // pred's link changed
 227                     break;
 228                 int found;
 229                 find_preds(&found, preds, item->top_level, sl, key_data, key_len, TRUE);
 230             } while (1);
 231
 232             do {
 233                 // There in no need to continue linking in the item if another thread removed it.
 234                 node_t *old_next = ((volatile node_t *)item)->next[level];
 235                 if (IS_TAGGED(old_next))
 236                     return DOES_NOT_EXIST; // success
 237
 238                 // Use a CAS so we to not inadvertantly remove a mark another thread placed on the item.
 239                 if (next == old_next || SYNC_CAS(&item->next[level], old_next, next) == old_next)
 240                     break;
 241             } while (1);
 242
 243             TRACE("s3", "sl_add: attempting to insert item between %p and %p", pred, next);
 244             node_t *other = SYNC_CAS(&pred->next[level], next, item);
 245             if (other == next) {
 246                 TRACE("s3", "sl_add: successfully inserted item %p at level %llu", item, level);
 247                 break; // success
 248             }
 249             TRACE("s3", "sl_add: failed to change pred's link: expected %p found %p", next, other);
 250
 251         } while (1);
 252     }
 253     return value;
 254 }
 255
 256 uint64_t sl_remove (skiplist_t *sl, const void *key_data, uint32_t key_len) {
 257     TRACE("s3", "sl_remove: removing item with key %p from sl %p", key_data, sl);
 258     int found;
 259     node_t *preds[MAX_LEVEL+1];
 260     node_t *item = find_preds(&found, preds, -1, sl, key_data, key_len, TRUE);
 261     if (!found) {
 262         TRACE("s3", "sl_remove: remove failed, an item with a matching key does not exist in the sl", 0, 0);
 263         return DOES_NOT_EXIST;
 264     }
 265
 266     // Mark <item> removed at each level of <sl> from the top down. This must be atomic. If multiple threads
 267     // try to remove the same item only one of them should succeed. Marking the bottom level establishes which of
 268     // them succeeds.
 269     for (int level = item->top_level; level >= 0; --level) {
 270         if (EXPECT_FALSE(IS_TAGGED(item->next[level]))) {
 271             TRACE("s3", "sl_remove: %p is already marked for removal by another thread", item, 0);
 272             if (level == 0)
 273                 return DOES_NOT_EXIST;
 274             continue;
 275         }
 276         node_t *next = SYNC_FETCH_AND_OR(&item->next[level], TAG);
 277         if (EXPECT_FALSE(IS_TAGGED(next))) {
 278             TRACE("s3", "sl_remove: lost race -- %p is already marked for removal by another thread", item, 0);
 279             if (level == 0)
 280                 return DOES_NOT_EXIST;
 281             continue;
 282         }
 283     }
 284
 285     uint64_t value = item->value;
 286
 287     // Unlink <item> from the top down.
 288     int level = item->top_level;
 289     while (level >= 0) {
 290         node_t *pred = preds[level];
 291         node_t *next = item->next[level];
 292         TRACE("s3", "sl_remove: link item's pred %p to it's successor %p", pred, STRIP_TAG(next));
 293         node_t *other = NULL;
 294         if ((other = SYNC_CAS(&pred->next[level], item, STRIP_TAG(next))) != item) {
 295             TRACE("s3", "sl_remove: unlink failed; pred's link changed from %p to %p", item, other);
 296             // By marking the item earlier, we logically removed it. It is safe to leave the item partially
 297             // unlinked. Another thread will finish physically removing it from <sl>.
 298             return value;
 299         }
 300         --level;
 301     }
 302
 303     // The thread that completes the unlink should free the memory.
 304     nbd_defer_free(item);
 305     return value;
 306 }
 307
 308 void sl_print (skiplist_t *sl) {
 309     for (int level = MAX_LEVEL; level >= 0; --level) {
 310         node_t *item = sl->head;
 311         if (item->next[level] == NULL)
 312             continue;
 313         printf("(%d) ", level);
 314         while (item) {
 315             node_t *next = item->next[level];
 316             printf("%s%p ", IS_TAGGED(next) ? "*" : "", item);
 317             item = (node_t *)STRIP_TAG(next);
 318         }
 319         printf("\n");
 320         fflush(stdout);
 321     }
 322
 323     printf("\n");
 324     node_t *item = sl->head;
 325     while (item) {
 326         int is_marked = IS_TAGGED(item->next[0]);
 327         printf("%s%p:%s ", is_marked ? "*" : "", item, (char *)ns_data(item->key));
 328         if (item != sl->head) {
 329             printf("[%d]", item->top_level);
 330         } else {
 331             printf("[*]");
 332         }
 333         for (int level = 1; level <= item->top_level; ++level) {
 334             node_t *next = (node_t *)STRIP_TAG(item->next[level]);
 335             is_marked = IS_TAGGED(item->next[0]);
 336             printf(" %p%s", next, is_marked ? "*" : "");
 337             if (item == sl->head && item->next[level] == NULL)
 338                 break;
 339         }
 340         printf("\n");
 341         fflush(stdout);
 342         item = (node_t *)STRIP_TAG(item->next[0]);
 343     }
 344 }