Searching in a lock-free ordered single-linked list

Question

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->bucket, key, NULL, NULL, NULL);
}

void* lf_list_put_if_absent(LF_List* table, uint64_t key, void* value)
{
    marked_ptr_t* prev;
    marked_ptr_t cur, last;
    marked_ptr_t new_node;

    while(1)
    {
        if(lf_list_find(&table->bucket, key, &prev, &cur, &last) != NULL)
        {
            return PTR_OF(cur)->value;
        }

        new_node = CONSTRUCT(calloc(1, sizeof(Node)));

        PTR_OF(new_node)->value = value;
        PTR_OF(new_node)->key = key;

        PTR_OF(new_node)->next = *prev;

        if(CAS(prev, cur, new_node) == cur)
        {

            INCR(&table->size, 1);
            break;
        } else {
            free(PTR_OF(new_node));
            continue;
        }       
    }
    return NULL;
}

int lf_list_remove(LF_List* table, uint64_t key)
{
    marked_ptr_t cur, last;
    marked_ptr_t *prev;

    while(1)
    {
        if(lf_list_find(&table->bucket, key, &prev, &cur, &last) == NULL)
        {
            return 0;
        }

        if (CAS(prev, cur, PTR_OF(cur)->next) == cur) {

            free(PTR_OF(cur));
            INCR(&table->size, -1);
            return 1;
        } else {
            continue;
        }   
    }

    return 0;
}

Answer 1

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:

1. The program terminated (no errors).
2. The program printed ERROR, meaning that something went wrong with a put or remove.
3. 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.