CODEWITHSUNDEEP
multithreadinglinked-listatomiclockless
chris.sun
chris.sun

Reputation: 11

Lockfree linked list

I am implementing a lockfree linked list in C, similar to what's available in linux kernel llist.h. I am using atomic operation of "__sync_bool_compare_and_swap".

Here is the code snipet:

    struct llist_head {
    struct llist_node *head;
    struct llist_node *tail;
};

struct llist_node {
    struct llist_node *next;
    int mm_ref;
};

#define LLIST_HEAD_INIT(name)   { NULL, NULL }
#define LLIST_HEAD(name)    struct llist_head name = LLIST_HEAD_INIT(name)

void llist_insert_tail(struct llist_head *head, struct llist_node *new)
{
    volatile struct llist_node *last;
    new->mm_ref = 0;

    mb();
    new->next = NULL;
    do {
        last = head->tail;
        if (last)
            last->next = new;
    } while(!CAS(&(head->tail), last, new));
    CAS(&(head->head), NULL, new);
    mb();
}

struct llist_node *llist_remove_head(struct llist_head *head)
{
    volatile struct llist_node *first, *next;

    do {
        first = head->head;
        if (first != head->head)
            continue;
        if (first == NULL)
            return 0;
        next = first->next;
        printf("%s: tid=%lx first=%p next=%p first->next=%p\n", 
              __func__, pthread_self(), first, next, first->next);
    } while(!CAS(&(head->head), first, next));
    return first;
}

I have a small multi-thread test program, there is only 1 producer thread to insert node into the tail list, and two consumers threads to remove the node from head of the list. The insert/remove functions are showed bellow:

    void *list_insert(void *data)
{
    int i;
    printf("producer: id=%lx\n", pthread_self());

    for ( i = 0 ; i < 10 ; i++) {
        struct my_list_node *e = malloc(sizeof(struct my_list_node));
        e->a = SOMEID;
        llist_insert_tail(&global_list, &(e_array[i]->list));
        printf("new node p=%p next=%p\n", e_array[i], e_array[i]->list.next);
        ATOMIC_ADD64(&cn_added, 1);
    }
    ATOMIC_SUB(&cn_producer, 1);
    printf("Producer thread [%lx] exited! Still %d running...\n",pthread_self(), cn_producer);
    return 0;
}

void *list_remove(void *data)
{
    struct llist_node *pos = NULL;
    printf("consumer: id=%lx\n", pthread_self());
    while(cn_producer || !llist_empty(&global_list)) {
        struct my_list_node *e;
        pos = llist_remove_head(&global_list);
        if (pos) {
            e = llist_entry(pos, struct my_list_node, list);
            printf("tid=%lx removed %p\n", pthread_self(), pos);
            if (e->a != SOMEID) {
                printf("data wrong!!\n");
                exit(1);
            }
            ATOMIC_ADD64(&cn_deleted, 1);
        } else {
            sched_yield();
        }
    }
    printf("Consumer thread [%lx] exited %d\n", pthread_self(), cn_producer);
    return 0;
}

The test showing consistent failure, e.g. the producer inserted 10 nodes,but the consumer only popped 1/2 or 3 nodes, one of the typical output i got showed bellow:

consumer: id=7f4d469e8700
consumer: id=7f4d461e7700
producer: id=7f4d459e6700
new node p=0x7f4d400008c0 next=(nil)
new node p=0x7f4d400008e0 next=(nil)
new node p=0x7f4d40000900 next=(nil)
new node p=0x7f4d40000920 next=(nil)
new node p=0x7f4d40000940 next=(nil)
new node p=0x7f4d40000960 next=(nil)
new node p=0x7f4d40000980 next=(nil)
new node p=0x7f4d400009a0 next=(nil)
new node p=0x7f4d400009c0 next=(nil)
new node p=0x7f4d400009e0 next=(nil)
Producer thread [7f4d459e6700] exited! Still 0 running...
llist_remove_head: tid=7f4d469e8700 first=0x7f4d400008c0 next=(nil) first->next=(nil)
llist_remove_head: tid=7f4d469e8700 head=(nil)
tid=7f4d469e8700 removed 0x7f4d400008c0
Consumer thread [7f4d469e8700] exited 0
llist_remove_head: tid=7f4d461e7700 first=0x7f4d400008c0 next=(nil) first->next=(nil)
Consumer thread [7f4d461e7700] exited 0

As can be seen, the producer threads exited first,and switched to consumer threads, however, this line: llist_remove_head: tid=7f4d469e8700 first=0x7f4d400008c0 next=(nil) first->next=(nil) showing that one of the consumer thread is trying to remove first node, but it's next pointer points to the NULL, which should NOT be the case since by now, the list is fully populated (with 10 nodes). So there are race condition, which suppose to happen since this is lock-free list, but I scratch my head and couldn't figure out what kind of race condition could cause this output. This implementation is similar to https://github.com/darkautism/lfqueue But I can't figure out why my version doesn't work.

Upvotes: 1

Views: 1156

Answers (1)

Oktaheta
Oktaheta

Reputation: 626

You may try lfqueue

It is simple to use, it is circular design lock free 

    int *ret;

    lfqueue_t results;

    lfqueue_init(&results);

    /** Wrap This scope in multithread testing **/
    int_data = (int*) malloc(sizeof(int));
    assert(int_data != NULL);
    *int_data = i++;
    /*Enqueue*/
    while (lfqueue_enq(&results, int_data) != 1) ;

    /*Dequeue*/
    while ( (ret = lfqueue_deq(&results)) == NULL);

    // printf("%d\n", *(int*) ret );
    free(ret);
    /** End **/

    lfqueue_clear(&results);

There is a lfstack which come together with same developer.

Upvotes: 1

Related Questions