Velan Studios Velan Studios Blog

Our First Open Source Release: Lock-Free Queue and Pool

Chris McEvoy — May 19, 2017

Today the programmers at Velan are releasing two of our lock-free data structures; a lock-free queue and a lock-free integer pool. We use both as a core part of our Viper technology. Both data structures are written in C99 and are fairly self-contained.

Lock-Free Queue: vqueue

Our lock-free queue is an implementation of the non-blocking queue in Michael and Scott's "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms" paper. While this excellent paper is over 20 years old, it is not something we'd seen cleanly implemented in our language of choice without calls to malloc() in the push operation.

The queue supports three major operations:

  • Push a void pointer on the queue.
  • Pop a void pointer from the queue.
  • Get the number of void pointers currently in the queue.

The queue is lock-free and thread-safe. A push performs at least 3 atomic 64-bit compare-and-swap (CAS) operations and 1 atomic 32-bit increment. A pop on a non-empty queue performs at least 2 atomic 64-bit CAS operations and 1 atomic 32-bit decrement.

We pre-allocate space for the capacity of the queue. There is 8 bytes of overhead for each item that the queue can hold.

Lock-Free Integer Pool: vintpool

After writing the queue node allocator for vqueue, we decided to generalize the code slightly, and thus was born vintpool. One common pattern we have in Viper is managing a block of pre-allocated storage in a thread-safe way.

    thing_t things[k_max_things];
    int alloc_thing() { /* Get an index to a free thing. */ }
    void free_thing(int thing_index) { /* Marked an indexed thing as free. */ }

This is the mission of vintpool, to manage pools of indexed resources. The pool supports two operations:

  • Allocate an index.
  • Free an index.

Both operations are lock-free and thread-safe. Each operation incurs the overhead of at least 1 atomic 64-bit CAS. Storage for the pool is pre-allocated at a cost of 8-bytes per index.

Where to Get the Code

The code for vqueue and vintpool are up on GitHub now. If you use this code, please let us know. We'd love to hear from you.

You can reach the technology team at Velan by emailing viper@velanstudios.com.