Crate lfqueue

This crate is an implementation of “A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue”_ by Ruslan Nikolaev (arXiV/1908.04511).

It supports #![no_std] and std. std gives you access to the rings backed by an allocated buffer.

Example

use lfqueue::ConstBoundedQueue;
 
// We want a queue of size 2, so we make a constant queue
// with the generic set to 2 ^ 2 = 4.
let queue = ConstBoundedQueue::<usize, 4>::new_const();
 
// Let us add a few values.
assert!(queue.enqueue(1).is_ok());
assert!(queue.enqueue(2).is_ok());
 
// Let us verify the correctnes by dequeing these values.
assert_eq!(queue.dequeue(), Some(1));
assert_eq!(queue.dequeue(), Some(2));
assert_eq!(queue.dequeue(), None);

Design

SCQ Rings

Each data structure fundamentally relies on the SCQ ring described in the ACM paper. The ring is a MPMC queue for indices. The size must be a power of two, hence why on initialization we must pass an order instead of a capacity directly.

Bounded Queue

The bounded queue is the SCQ queue from the ACM paper. It works by maintaining two rings:

• Free Ring: This ring contains all the available indexes that we can slot a value into.
• Allocation Ring: This ring contains all the indexes that are currently allocated. The correctness of the various methods relies

Macros

const_queue

Creates a ConstBoundedQueue. This function exists mostly to creates queues of the correct size easily. For instance, to create a queue that can hold 2 values, the bound needs to be four. This macro assists with that by generating an initialization that takes this into account.

Structs

BoundedQueue

The bounded queue type from the ACM paper. This uses two SCQ rings internally, one that keeps track of free indices and the other that keeps track of the allocated indices.

SingleSize

A queue that has a capacity of 1.

UnboundedEnqueueHandle

A enqueue handle to an UnboundedQueue, allowing for bulk enqueues efficiently. Internally, the unbounded queue manages the queue of bounded queues with hazard pointers to avoid the ABA problem, this allows minimizing the creation of these hazard pointers.

UnboundedFullHandle

A full handle to an UnboundedQueue, allowing for bulk enqueues efficiently. Internally, the unbounded queue manages the queue of bounded queues with hazard pointers to avoid the ABA problem, this allows minimizing the creation of these hazard pointers.

UnboundedQueue

An unbounded lock-free queue. This is the LCSQ from the ACM paper, “A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue” by Ruslan Nikolaev.

Enums

ScqError

Type Aliases

AllocBoundedQueue

A bounded SCQ queue backed by an allocated array.

ConstBoundedQueue

A constant generic constant bounded queue, this implements the SCQ from the ACM paper, “A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue” by Ruslan Nikolaev.