8
\$\begingroup\$

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;
}
\$\endgroup\$
2
  • \$\begingroup\$ This code doesn't implement the code in the linked document. Where are the marks in the marked pointers? What prevents your deletion function from interfering with lf_list_find()? Have you tested this code? Because from just a casual inspection, it doesn't look like it works. \$\endgroup\$
    – JS1
    Jun 2, 2015 at 21:16
  • \$\begingroup\$ Original algo is indeed split-ordered hashtable. But for 1 bucket it behaves as ordered single-linked list. In original algo uses least significant bit as mark to remove in lf_list_find. In my modification name ramained but logic has been moved to lf_list_remove. Please dont pay attantion to names. Deletion function does not interfer with lf_list_find, as logic has been replaced. Lf_list_find simply finds. I test it on own-written websocket server - multithreaded, epoll. Yes, it is in use on development server. \$\endgroup\$ Jun 2, 2015 at 21:25

1 Answer 1

9
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ U are right, I oversimplified this approch(have few of them). Have read you coment, and modified code, tried to post but missed few sec. \$\endgroup\$ Jun 3, 2015 at 0:19
  • \$\begingroup\$ @DawidSzymański You can make a new post with your modified code if you want feedback on it. You aren't supposed to change your code in a question you already asked though. \$\endgroup\$
    – JS1
    Jun 3, 2015 at 0:33
  • \$\begingroup\$ I see, am quite new to this site - therefore have difficulty knowing whats allowable. \$\endgroup\$ Jun 3, 2015 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.