Ordered doubly-linked lock-free list

Question

I'm implementing a lock-free ordered doubly-linked list based on heavily modified paper entitled Split-Ordered Lists: Lock-Free Extensible Hash Tables by ORI SHALEV. My main concern is correctness of algorithm, secondly performance.

Is the algorithm used in the code really lock-free? How can I improve the code?

typedef __uint64_t              uint64_t;
typedef uintptr_t               node_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
{
    int             mark;
    void            *value;
    uint64_t        key;
    node_ptr_t      prev, next;
} Node;

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

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

    uint64_t cur_key;
    void* cur_value;

    while(1)
    {
        tp_prev = head;
        tp_cur  = *head;
        tp_last = (node_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(*tp_prev != tp_cur)
            {
                break;
            }

            if (PTR_OF(tp_cur)->mark == 1)
            {

                if (PTR_OF(*tp_next) != NULL)
                {
                    if (CAS(&PTR_OF(*tp_next)->prev, tp_cur, tp_last) != tp_cur)
                    {
                        continue;
                    }
                }

                if (CAS(tp_prev, tp_cur, *tp_next) == tp_cur) {

                    free(PTR_OF(tp_cur));
                    tp_cur = *tp_next;
                    INCR(&list->size, -1);
                    continue;
                } else {
                    break;
                }           
            } else if (CAS(&PTR_OF(tp_cur)->mark, 2, 0) == 2)
            {
                if (PTR_OF(*tp_next) != NULL)
                {
                    if (CAS(&PTR_OF(*tp_next)->prev, tp_last, tp_cur) == tp_last)
                    {
                        INCR(&list->size, 1);
                        continue;
                    } else {
                        break;
                    }
                }
            }

            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* list, uint64_t key)
{
    return lf_list_find(list, &list->bucket, key, NULL, NULL, NULL);
}

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

    while(1)
    {
        if(lf_list_find(list, &list->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)->mark = 2;

        PTR_OF(new_node)->next = *prev;
        PTR_OF(new_node)->prev = last;

        if(CAS(prev, cur, new_node) == cur)
        {
            lf_list_find(list, &last, key, NULL, NULL, NULL);
            break;
        } else {
            free(PTR_OF(new_node));
            continue;
        }       
    }
    return NULL;
}

int lf_list_remove(LF_List* list, uint64_t key)
{
    node_ptr_t cur, last;
    node_ptr_t *prev;

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

    PTR_OF(cur)->mark = 1;

    lf_list_find(list, &last, key, NULL, NULL, NULL);

    return 1;
}

Answer 1

Still not safe

I haven't run the new code yet but I can already theorize at least one possible flaw. Suppose you have the following list:

4 -> 3 -> 2 -> 1

Then suppose element 2 is deleted:

4 -> 3 -> 2* -> 1 (* = marked for deletion)

Now thread 1 iterates across the list and stops at element 2, and is about to delete it. Meanwhile, element 3 is deleted:

4 -> 3* -> 2* -> 1

Thread 2 iterates across the list and stops at element 3. Now you have two threads both trying to delete separate elements at the same time. One is trying to make 4 point to 2. The other is trying to make 3 point to 1. All sorts of bad things can happen. I'm even leaving out the part where the list is now doubly linked with prev pointers.

The reason that the research paper algorithm works is because the mark is stored within the next pointer. That way, the CAS will fail if it tries to change the pointer with the wrong mark on it. With your program, the mark is stored separately from the next pointer. Therefore, you can't atomically change both the mark and the pointer.