Searching in a lock-free ordered single-linked list

The code below represents a lock-free ordered single-linked list, and is a modification of the algorithm proposed in this doc.

How can I improve speed of searching (lookingup) in the list maintaining lock-free capability? Any suggestions, code modifications, examples, maybe other lock-free data structures?

```
typedef uintptr_t marked_ptr_t;
#define PTR_OF(x) ((Node*)(x))
#define CONSTRUCT(ptr) ((uintptr_t)ptr)
#define CAS(ADDR, OLDV, NEWV) __sync_val_compare_and_swap((ADDR), (OLDV), (NEWV))
#define INCR(ADDR, INCVAL) __sync_fetch_and_add((ADDR), (INCVAL))

typedef struct
{
void *value;
uint64_t key;
marked_ptr_t next;
} Node;

typedef struct
{
marked_ptr_t bucket;
uint32_t size;
} LF_List;

void lf_list_get(LF_List, uint64_t);

void lf_list_put_if_absent(LF_List, uint64_t, void*);

int lf_list_remove(LF_List*, uint64_t);

void lf_list_find(marked_ptr_t head, uint64_t key, marked_ptr_t** prev, marked_ptr_t cur, marked_ptr_t last)
{
marked_ptr_t* tp_prev;
marked_ptr_t tp_cur, tp_last;
marked_ptr_t* tp_next;

uint64_t cur_key;
void* cur_value;

tp_prev = head;
tp_cur = *head;
tp_last = (marked_ptr_t)NULL;

while(1)
{
if (PTR_OF(tp_cur) == NULL)
{
if(prev){*prev = tp_prev;};
if(cur){*cur = tp_cur;};
if(last){*last = tp_last;};

return NULL;
}

tp_next = &PTR_OF(tp_cur)->next;

cur_key = PTR_OF(tp_cur)->key;
cur_value = PTR_OF(tp_cur)->value;

if (key >= cur_key)
{
if(prev){*prev = tp_prev;};
if(cur){*cur = tp_cur;};
if(last){*last = tp_last;};

return key == cur_key ? cur_value : NULL;
}

tp_last = tp_cur;
tp_prev = tp_next;
tp_cur = *tp_next;
}
}

void lf_list_get(LF_List table, uint64_t key)
{
return lf_list_find(&table->b

Lockless list not threadsafe

I was able to break your list with a simple program:

LF_List list = {0};

void *threadFunc(void *arg)
{
    uint64_t key = (uintptr_t) arg;
    int i;

    for (i=0;i<100000;i++) {
        lf_list_put_if_absent(&list, key, (void *) 1);
        if (lf_list_remove(&list, key) == 0) {
            printf("ERROR\n");
            exit(1);
        }
    }
    return NULL;
}

int main(void)
{
    pthread_t t1, t2;
    pthread_create(&t1, 0, threadFunc, (void *) 9);
    pthread_create(&t2, 0, threadFunc, (void *) 8);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
}

When I ran this program, one of three things happened:

• The program terminated (no errors).

• The program printed ERROR, meaning that something went wrong with a put or remove.

• The program never terminated, indicating a cycle in the list was created.

I was also able to cause a segmentation violation by modifying lf_list_remove() to write 0xffffffff to the next pointer of a node just before freeing it:

if (CAS(prev, cur, PTR_OF(cur)->next) == cur) {
        // Once a pointer is freed, its memory could be trashed.
        // Simulate this by writing an invalid address to cur->next.
        PTR_OF(cur)->next = 0xffffffff;
        free(PTR_OF(cur));
        INCR(&table->size, -1);
        return 1;
    } else {
        continue;
    }

I was also able to cause the program to crash by specifically adding some strategic sleep() calls to cause two threads to perform a specific sequence of events, but that code is too lengthy to list here unless you really want to see it.

Basically, what it all boils down to is that when one thread is freeing a node, the other thread can access the freed node because there is nothing to stop it from doing so. The original code in the research paper used marking bits to prevent this from happening, but those marking bits have been removed from this implementation.

StackExchange Code Review Q#92501, answer score: 9