PROGRESS64

September 11, 2025 · View on GitHub

Progress by Design

Purpose

PROGRESS64 is a C library of scalable functions for parallel and concurrent programs. It provides functionality which is often required in multithreaded networking applications. The general goal is to provide primitives which enable scalable and preferably non-blocking concurrent applications.

A secondary purpose is to inform and inspire the use of the C11-based memory model (especially Release Consistency i.e. using load-acquire/store-release) for multithreaded programming.

Functionality

Non-blocking or concurrent functions

Name	Description	Properties
antireplay	replay protection	lock-free/wait-free
blkring	ring buffer with blocking enqueue & dequeue	blocking
buckring	ring buffer using pass-the-buck algorithm	non-blocking (1)
buckrob	reorder buffer using pass-the-buck algorithm	non-blocking (1)
counter	shared counters	reader obstruction-free, writer wait-free
cuckooht	hash table - cuckoo with cellar, one-level move	non-blocking (1)
deque	Michael double ended queue	lock-free
hashtable	hash table - separate chaining with linked lists	lock-free
hazardptr	safe object reclamation using hazard pointers	reader lock-free, writer blocking/non-blocking
hopscotch	hash table - hopscotch with cellar	non-blocking (1)
mcas	Harris/Fraser/Pratt multi-word CAS	lock-free
mcqueue	Mellor-Crummey concurrent queue	blocking
msqueue	Michael & Scott queue with configurable ABA workaround (lock/tag/smr)	blocking/lock-free
laxrob	'lax' reorder buffer	non-blocking (1)
lfring	ring buffer	lock-free
lfstack	lock-free stack (using tagged pointers) with backoff and progress-in-update flag	lock-free
linklist	Harris single linked list	lock-free
mbtrie	multi-bit trie	reader lock-free/wait-free, writer non-blocking (1)
qsbr	safe object reclamation using quiescent state based reclamation	reader wait-free, writer blocking
reassemble	IP reassembly	lock-free, resizeable
reorder	'strict' reorder buffer	non-blocking (1)
ringbuf	classic ring buffer, support for user-defined element type	blocking & non-blocking (2), lock-free dequeue
stack	Treiber stack with configurable ABA workaround (lock/tag/smr/llsc)	blocking/lock-free
timer	timers	lock-free

"Obstruction-free", "lock-free" and "wait-free" have the standard definitions from computer science.

(1) Non-blocking but not (always) linearizable (2) Non-blocking within a limited window (currently 32 elements)

Locks & other blocking functions

Name	Description	Properties
barrier	thread barrier	blocking
clhlock	CLH queue lock	mutex, fcfs, queue
hemlock	hemlock queue lock	mutex, fcfs, queue
mcslock	MCS queue lock	mutex, fcfs, queue
pfrwlock	phase fair reader/writer lock	rw, fcfs
rplock	reciprocating lock	mutex, queue
rwclhlock	reader/writer CLH queue lock	rw, fcfs, queue, sleep
rwlock	reader/writer lock (writer preference)	rw
rwlock_r	recursive version of rwlock	rw, recursive
rwsync	lightweight reader/writer synchronisation aka 'seqlock' (writer preference)	rw
rwsync_r	recursive version of rwsync	rw, recursive
semaphore	counting semaphore	rw, fcfs
skiplock	skippable ticket-like lock	mutex
spinlock	basic CAS-based spin lock	mutex
tfrwlock	task fair reader/writer lock	rw, fcfs
tfrwlock_r	recursive version of tfrw lock	rw, fcfs, recursive
tktlock	ticket lock	mutex, fcfs

"mutex" - mutual exclusion, only one thread at a time can acquire lock.
"rw" - multiple threads may concurrently acquire lock in reader (shared) mode.
"fcfs" - first come, first served. FCFS locks can be considered fair.
"queue" - each waiting thread spins on a separate location. Queue locks generally scale better with high lock contention.
"recursive" - the same thread can re-acquire the lock when it is already acquired.
"sleep" - waiting thread will sleep after spinning has timed out.

Concurrency support

Name	Description	Properties
coroutine	coroutines using "crosscall"	aarch64 only
fiber	fibers using "crosscall"	aarch64 only

Requirements

A C11 compiler (e.g. GCC or Clang) which supports the '__atomic' builtins and inline assembler. Several other GCC'isms are used as well.
Several functions require 64-bit and 128-bit atomics (e.g. CAS) support in the hardware.

HW/SW Support

Architectures
- ARMv8/AArch64 (aka ARM64)
- x86-64
Operating Systems
- Linux
- Windows
- macOS (Darwin)

Usage

Use library through the provided C header files. Or copy source files into your own project. Use the 'verify' command to verify all or specific permutation(s) (interleavings) of two threads accessing a datatype.

Notes

Hazardptr and QSBR support one reclamation domain only. This is a trade-off that simplifies the API and usage. For QSBR, multiple reclamation domains do make sense...
The hazard pointer implementation is non-blocking (wait-free) when a thread has space for more retired objects than the total number of hazard pointers (for all threads).
The hazard pointer API will actually use the QSBR implementation when 'nrefs' (number of hazard pointers per thread) is set to 0 when the hazard pointer domain is allocated.
The resizeable reassembly function is experimental and has not yet endured stress testing.
The mbtrie is experimental and has not yet endured stress testing.
The hopscotch hash table is experimental and has not yet endured stress testing.
The cuckooht hash table is experimental and has not yet endured stress testing.
When using Safe Memory Reclamation as ABA workaround with the Treiber stack, LIFO order is not guaranteed (so not really a LIFO stack...)
The skiplock is a simplified version of a ring buffer based ticket-like lock.

TODO

Some missing examples
Multithreaded stress test programs for e.g. hash tables, reassembly, mbtrie
Use C11 features instead of GNU extensions and other non-standard features