mulle-concurrent

mulle-concurrent is a library for lock- and wait-free data structures. Wait-freeness is a desirable property for "hotly" contested data structures in multi-threaded environments.

Many of the ideas are taken from Preshing on Programming: A Resizable, Concurrent Map. The definition of concurrent and wait-free are from concurrencyfreaks.blogspot.de

Release Version	Release Notes	AI Documentation
	RELEASENOTES	DeepWiki for mulle-concurrent

For the hashmap progress argument, see Wait-free status of mulle_concurrent_hashmap_register.

• API Summary
• Coder Guide

mulle-concurrent data structures require mulle-aba for safe concurrent memory reclamation. You must initialize mulle-aba once per process and register every thread that accesses mulle-concurrent data structures.

#include <mulle-concurrent/mulle-concurrent.h>

int   main( int argc, char *argv[])
{
   struct mulle_concurrent_hashmap   map;

   mulle_aba_init( NULL);                          // once per process
   mulle_aba_register();                           // register main thread

   mulle_concurrent_hashmap_init( &map, 0, NULL);

   // ... use the hashmap ...

   mulle_concurrent_hashmap_done( &map);

   mulle_aba_unregister();                         // unregister main thread
   mulle_aba_done();                               // once per process
   return( 0);
}

Every participating thread must call mulle_aba_register before accessing any mulle-concurrent data structure and mulle_aba_unregister before exiting. Forgetting to do so will crash.

With mulle_thread you can automate the unregister with a TSS destructor:

#include <mulle-concurrent/mulle-concurrent.h>

static mulle_thread_tss_t   aba_tss_key;


static void   aba_thread_destructor( void *value)
{
   mulle_aba_unregister();
}


// call once from main before spawning threads
static void   aba_setup_thread_cleanup( void)
{
   mulle_thread_tss_create( aba_thread_destructor, &aba_tss_key);
}


// call at the start of each thread function
static void   aba_register_thread( void)
{
   mulle_aba_register();
   mulle_thread_tss_set( aba_tss_key, (void *) 1);  // non-NULL triggers destructor
}

Then your thread function becomes:

static void   *my_worker( void *arg)
{
   struct mulle_concurrent_hashmap   *map = arg;

   aba_register_thread();

   // ... safely use map ...

   return( NULL);  // destructor calls mulle_aba_unregister automatically
}

init and done must be externally serialized, and every thread that touches a mulle-concurrent data structure must be registered with mulle-aba. The complete process looks like this:

1. Initialize mulle-aba once per process — mulle_aba_init( allocator).
2. Configure the allocator for ABA reclamation — if you pass a custom allocator, wire it up with mulle_allocator_set_aba() so that old storage can be freed safely.
3. Register every participating thread — mulle_aba_register() before the first access, mulle_aba_unregister() when the thread is done. In a thread pool, use the TSS destructor recipe from Multi-threaded setup above to make this automatic.
4. init your structures — in a single-threaded context, before any worker threads start.
5. Use the structures — from any registered thread.
6. Stop the world — ensure no thread accesses the structures anymore (join the workers / drain the pool) before you tear anything down.
7. done your structures — in a single-threaded context, after the stop.
8. Unregister the threads and finish mulle-aba — mulle_aba_done() once per process, after all accesses have ceased.

Destroying a structure while a reader is still active is not recoverable. If a thread accesses a structure without being registered, the process will crash.

• Point operations are wait-free — register, insert, lookup, remove, add, get, member complete in a bounded number of steps regardless of contention. Growth and migration are cooperative: any thread that observes a REDIRECT slot helps finish the migration and then retries its own operation.
• count, get_size, get_count and lookup_any are snapshots — they return a value from some point in time during the call and may be stale if the structure is mutated concurrently. Use them for diagnostics and heuristics, not for correctness decisions.
• Enumeration is "limited multi-threaded" — an enumerator is only usable by the calling thread. For the hashmap and pointerset, concurrent mutation (insert/remove/growth) may interrupt the enumeration; the enumerator then returns ECANCELLED and you retry the whole enumeration from the start. Retrying may yield duplicates or miss entries that changed in between — that is expected. The pointerarray is append-only, so its enumerators work reliably even while other threads add values.
• remove on a hashmap requires the matching value — the pair (hash, value) must match, so a removed entry cannot be resurrected by a newer value. The slot is left as a tombstone: the hash stays claimed (so probe chains through it keep working) but the value is marked removed. The same hash cannot be registered or inserted again in that storage generation; register reports EEXIST and insert returns EEXIST. Migration drops tombstones, after which the hash can be used again.
• Hashmap register/insert never return a foreign key's value — a slot is claimed by CASing its hash, and only operations with that matching hash may write its value, so two different keys can never collide on one slot's value.
• Pointerset and hashmap tombstones accumulate — removed slots are not reused within a storage generation. Migration drops tombstones while strictly growing the storage. For remove-heavy pointerset workloads, mulle_concurrent_pointerset_reset() can reclaim them explicitly.
• init and done are single-threaded — no other thread may access the structure while either runs. See the Lifecycle checklist.

The containers store void * pointers and reserve a few values for internal use. Never store any of these values as payload.

The values are defined in src/mulle-concurrent-types.h. They are compile-time constants derived from the platform's intptr_t, so the reserved set is fixed per architecture. Passing a reserved value to an operation that rejects it returns EINVAL.

All allocation is fail-fast: the mulle allocator contract is success or abort. When the default allocator cannot satisfy an allocation it prints an error and aborts the process. The API therefore only reports allocation failure by aborting; do not write code that depends on recovering from it.

This project is a component of the mulle-core library. As such you usually will not add or install it individually, unless you specifically do not want to link against mulle-core.

mulle-concurrent is intended to be consumed as a git submodule with CMake's add_subdirectory() — no mulle tooling is required in the parent build:

git submodule add https://github.com/mulle-concurrent/mulle-concurrent.git \
   third_party/mulle-concurrent

Add this to your CMakeLists.txt:

add_subdirectory( third_party/mulle-concurrent)
target_link_libraries( my_target PRIVATE mulle-concurrent)

#include <mulle-concurrent/mulle-concurrent.h>

The parent project must supply the mulle dependency graph — mulle-aba and its transitive targets (e.g. by also adding mulle-core) — so that the dependency resolves to CMake targets rather than system libraries.

Use mulle-sde to add mulle-concurrent to your project:

mulle-sde add github:mulle-concurrent/mulle-concurrent

To only add the sources of mulle-concurrent with dependency sources use clib:

clib install --out src/mulle-concurrent mulle-concurrent/mulle-concurrent

Add -isystem src/mulle-concurrent to your CFLAGS and compile all the sources that were downloaded with your project.

Use mulle-sde to build and install mulle-concurrent and all dependencies:

mulle-sde install --prefix /usr/local \
   https://github.com/mulle-concurrent/mulle-concurrent/archive/latest.tar.gz

Install the requirements:

Download the latest tar or zip archive and unpack it.

Install mulle-concurrent into /usr/local with cmake:

PREFIX_DIR="/usr/local"
cmake -B build                               \
      -DMULLE_SDK_PATH="${PREFIX_DIR}"       \
      -DCMAKE_INSTALL_PREFIX="${PREFIX_DIR}" \
      -DCMAKE_PREFIX_PATH="${PREFIX_DIR}"    \
      -DCMAKE_BUILD_TYPE=Release &&
cmake --build build --config Release &&
cmake --install build --config Release

Nat! for Mulle kybernetiK