2 * Written by Josh Dybnis and released to the public domain, as explained at
3 * http://creativecommons.org/licenses/publicdomain
5 * Harris-Michael lock-free list-based set
6 * http://www.research.ibm.com/people/m/michael/spaa-2002.pdf
17 #define NUM_ITERATIONS 10000000
19 #define PLACE_MARK(x) (((size_t)(x))|1)
20 #define CLEAR_MARK(x) (((size_t)(x))&~(size_t)1)
21 #define IS_MARKED(x) ((size_t)(x))&1
33 static void list_node_init (node_t *item, int key)
35 memset(item, 0, sizeof(node_t));
39 node_t *list_node_alloc (int key)
41 node_t *item = (node_t *)nbd_malloc(sizeof(node_t));
42 list_node_init(item, key);
46 list_t *list_alloc (void)
48 list_t *list = (list_t *)nbd_malloc(sizeof(list_t));
49 list_node_init(list->head, INT_MIN);
50 list_node_init(&list->last, INT_MAX);
51 list->head->next = &list->last;
55 static void find_pred_and_item (node_t **pred_ptr, node_t **item_ptr, list_t *list, int key)
57 node_t *pred = list->head;
58 node_t *item = list->head->next; // head is never removed
59 TRACE("l3", "find_pred_and_item: searching for key %llu in list (head is %p)", key, pred);
65 node_t *other, *next = item->next;
66 TRACE("l3", "find_pred_and_item: visiting item %p (next is %p)", item, next);
67 while (EXPECT_FALSE(IS_MARKED(next))) {
69 // assist in unlinking partially removed items
70 if ((other = SYNC_CAS(&pred->next, item, CLEAR_MARK(next))) != item)
72 TRACE("l3", "find_pred_and_item: failed to unlink item from pred %p, pred's next pointer was changed to %p", pred, other);
73 return find_pred_and_item(pred_ptr, item_ptr, list, key); // retry
77 item = (node_t *)CLEAR_MARK(next);
79 TRACE("l3", "find_pred_and_item: unlinked item, %p is the new item (next is %p)", item, next);
82 if (item->key >= key) {
85 TRACE("l3", "find_pred_and_item: key found, returning pred %p and item %p", pred, item);
96 int list_insert (list_t *list, node_t *item)
98 TRACE("l3", "list_insert: inserting %p (with key %llu)", item, item->key);
99 node_t *pred, *next, *other = (node_t *)-1;
101 if (other != (node_t *)-1) {
102 TRACE("l3", "list_insert: failed to swap item into list; pred's next was changed to %p", other, 0);
104 find_pred_and_item(&pred, &next, list, item->key);
106 // fail if item already exists in list
107 if (next->key == item->key)
109 TRACE("l3", "list_insert: insert failed item with key already exists %p", next, 0);
114 TRACE("l3", "list_insert: attempting to insert item between %p and %p", pred, next);
116 } while ((other = __sync_val_compare_and_swap(&pred->next, next, item)) != next);
118 TRACE("l3", "list_insert: insert was successful", 0, 0);
124 node_t *list_remove (list_t *list, int key)
126 node_t *pred, *item, *next;
128 TRACE("l3", "list_remove: removing item with key %llu", key, 0);
129 find_pred_and_item(&pred, &item, list, key);
130 if (item->key != key)
132 TRACE("l3", "list_remove: remove failed, key does not exist in list", 0, 0);
136 // Mark <item> removed, must be atomic. If multiple threads try to remove the
137 // same item only one of them should succeed
139 node_t *other = (node_t *)-1;
140 if (IS_MARKED(next) || (other = __sync_val_compare_and_swap(&item->next, next, PLACE_MARK(next))) != next) {
141 if (other == (node_t *)-1) {
142 TRACE("l3", "list_remove: retry; %p is already marked for removal (it's next pointer is %p)", item, next);
144 TRACE("l3", "list_remove: retry; failed to mark %p for removal; it's next pointer was %p, but changed to %p", next, other);
146 return list_remove(list, key); // retry
149 // Remove <item> from list
150 TRACE("l3", "list_remove: link item's pred %p to it's successor %p", pred, next);
151 if ((other = __sync_val_compare_and_swap(&pred->next, item, next)) != item) {
152 TRACE("l3", "list_remove: link failed; pred's link changed from %p to %p", item, other);
154 // make sure item gets unlinked before returning it
156 find_pred_and_item(&d1, &d2, list, key);
158 TRACE("l3", "list_remove: link succeeded; pred's link changed from %p to %p", item, next);
164 void list_print (list_t *list)
169 printf("%d ", item->key);
176 #ifdef MAKE_list_test
181 static volatile int wait_;
182 static long num_threads_;
183 static list_t *list_;
185 void *worker (void *arg)
187 int id = (int)(size_t)arg;
190 unsigned int rand_seed = id+1;//rdtsc_l();
192 // Wait for all the worker threads to be ready.
193 __sync_fetch_and_add(&wait_, -1);
195 __asm__ __volatile__("lfence");
198 for (i = 0; i < NUM_ITERATIONS/num_threads_; ++i) {
199 int n = rand_r(&rand_seed);
200 int key = (n & 0xF) + 1;
202 node_t *item = list_node_alloc(key);
203 int success = list_insert(list_, item);
208 node_t *item = list_remove(list_, key);
210 nbd_defer_free(item);
220 int main (int argc, char **argv)
223 //lwt_set_trace_level("m0l0");
225 char* program_name = argv[0];
226 pthread_t thread[MAX_NUM_THREADS];
229 fprintf(stderr, "Usage: %s num_threads\n", program_name);
237 num_threads_ = strtol(argv[1], NULL, 10);
239 fprintf(stderr, "%s: Invalid argument for number of threads\n", program_name);
242 if (num_threads_ <= 0) {
243 fprintf(stderr, "%s: Number of threads must be at least 1\n", program_name);
246 if (num_threads_ > MAX_NUM_THREADS) {
247 fprintf(stderr, "%s: Number of threads cannot be more than %d\n", program_name, MAX_NUM_THREADS);
252 list_ = list_alloc();
254 struct timeval tv1, tv2;
255 gettimeofday(&tv1, NULL);
257 __asm__ __volatile__("sfence");
258 wait_ = num_threads_;
261 for (i = 0; i < num_threads_; ++i) {
262 int rc = pthread_create(thread + i, NULL, worker, (void*)(size_t)i);
263 if (rc != 0) { perror("pthread_create"); return rc; }
266 for (i = 0; i < num_threads_; ++i) {
267 pthread_join(thread[i], NULL);
270 gettimeofday(&tv2, NULL);
271 int ms = (int)(1000000*(tv2.tv_sec - tv1.tv_sec) + tv2.tv_usec - tv1.tv_usec) / 1000;
272 printf("Th:%ld Time:%dms\n", num_threads_, ms);