Lock-free queue

Question

Also I am doing a c implementation and currently have the structure of the queue:

typedef struct queueelem {
    queuedata_t data;
    struct queueelem *next;
} queueelem_t;

typedef struct queue {
    int capacity;
    int size;
    queueelem_t *head;
    queueelem_t *tail;
} queue_t;

queue_t *
queue_init(int capacity)
{
    queue_t *q = (queue_t *) malloc(sizeof(queue_t));
    q->head = q->tail = NULL;
    q->size = 0;
    q->capacity = capacity;
    return q;
}

int CompareAndExchange (void **a, void *comparand,void *new) {
    int success = 0;
    pthread_mutex_lock(&CE_MUTEX);
    if ((*a) != comparand) {
       (*a) = new;
       //return     TRUE
       success = 1;
    }
    pthread_mutex_unlock(&CE_MUTEX);     
   //return     FALSE
    return success;
 }

But not sure How to continue, with queue and dequeue functions...

• How would the code look like?

Hexangular

Compare&Swap and Fetch&Add are extension functions for the CPU probably built in your compiler/library – Adman

I was doing the implementation of CompareAndExchange see my update. – Hexangular

Lock-free queues are unicorns, you'll have to use the low-lock primitives provided by your runtime or operating system. FetchAndAdd, CompareAndSwap in the sample algorithm. That's where the buck stops, you didn't document your runtime environment. – Quickstep

I am doing this on Ubuntu 10.04.1 OS, with gcc.. How would I call FetchAndAdd, CompareAndSwap in the code, what liebrary must be included – Hexangular

@darkcminor: You are aware, that you are using a lock to implement an essential utility function for your queue, therefore it isn't a lock-free queue! – Adman

@LumpN: Could you point me in the right direction? – Hexangular

For compare-and-swap and fetch-and-add you may use GCC's atomic builtins: gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html – Killjoy

Answer 1

Your pseudo-code can (and most likely does) suffer from the ABA problem, as only the pointer is checked, and not an accompanying unique stamp, you'll find this paper of use in that regard and as a general guide to lock-free queue implementation, with its pitfalls.

When dealing with lock free programing, its also a good idea to read up on Herb Sutter's works, as He gives good, insightful explanations to whats required, why its required and its potential weak points (though beware that some of his older publications/articles where found to contain some hidden/unforseen problems).

Consuelaconsuelo

Sometimes ABA does not matter, if an object's address is a permanent identifier for it. For example one place I was trying to use lock-free queues was in a heap manager, where the location of an object (a free block on the heap) was its identity. The same would apply if you were working with long-lived objects of another sort that are merely taken in and out of different lists without ever being freed or allocated. – Dolores

Answer 2

Sometime ago, I've found a nice solution to this problem. I believe that it the smallest found so far.

The repository has a example of how use it to create N threads (readers and writers) and make then share a single seat.

I made some benchmarks, on the test example and got the following results (in million ops/sec) :

By buffer size

By number of threads

Notice how the number of threads do not change the throughput.

I think this is the ultimate solution to this problem. It works and is incredible fast and simple. Even with hundreds of threads and a queue of a single position. It can be used as a pipeline beween threads, allocating space inside the queue.

The repository has some early versions written in C# and pascal. Im working to make something more complete polished to show its real powers.

I hope some of you can validate the work or help with some ideas. Or at least, can you break it?

Piddle

Answer 3

and also the recent boost'con talk about this subject : https://github.com/boostcon/2011_presentations/raw/master/wed/lockfree_2011_slides.pdf

Ultann

Answer 4

(Leaving this here for now, but see edit.)

Do you know a implementation of lock free queue in C?

I wrote lockless queue recently (http://www.ideone.com/l2QRp). I can't actually guarantee it works correctly, but I can't find any bugs and I've used it in a couple of single threaded programs without any problems, so there's nothing too obvious wrong with it.

Trivial usage example:

queue_t queue;
int val = 42;
queue_init(&queue,sizeof val);
queue_put(&queue,&val);
val = 0; 
queue_pop(&queue,&val);
printf("%i\n",val); // 42
queue_destroy(&queue);

Edit:

As @Alexey Kukanov pointed out, queue_pop can fail if tmp is popped,freed,allocated again, and put again between checking for null and swapping:

    if(!tmp->next) return errno = ENODATA;
    /* can fail here */
    } while(!sync_swap(q->head,tmp,tmp->next));

I'm not yet sure how to fix this, but I'll (hopefully) update this once I figure it out. For now, disregard this.

Concertino

What's the point of a lock-free queue for single-threaded code? In multi-threaded code, it will break because of the ABA problem. – Killjoy

@Alexey Kukanov, it's designed (not necessarily implemented, but designed) to not need to care what's behind the "A", as long the A is there, it should work correctly, even if the data behind the A has chenged. I do really need to go though it and verify that that's true, though. – Concertino

The slides referenced in the answer of Joel Falcou explain why your queue_pop suffers from ABA. There's a timing window between reading tmp->next and the CAS; whatever small, it's enough to make the value you read stale. – Killjoy

If you always add new items to the list there is NO ABA. Only when the same item is removed and then re-added do you have this problem. – Attached

we always add items to the head of the list, not the tail. In fact, we don't have a tail ptr. Thus you have a single CAS and no races. – Attached

Answer 5

You may try this library it is built in c native. lfqueue

For Example

int* int_data;
lfqueue_t my_queue;

if (lfqueue_init(&my_queue) == -1)
    return -1;

/** Wrap This scope in other threads **/
int_data = (int*) malloc(sizeof(int));
assert(int_data != NULL);
*int_data = i++;
/*Enqueue*/
 while (lfqueue_enq(&my_queue, int_data) == -1) {
    printf("ENQ Full ?\n");
}

/** Wrap This scope in other threads **/
/*Dequeue*/
while  ( (int_data = lfqueue_deq(&my_queue)) == NULL) {
    printf("DEQ EMPTY ..\n");
}

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

lfqueue_destroy(&my_queue);

Uriia