kickalloc

An O(1), non-fragmenting, wait-free fixed-size pool allocator for real-time robotics stacks. It always hands back a full page ("element"): predictable, bounded-latency allocation, paid for in memory.

Two ways to use it, both opt-in — the rest of your stack keeps using std::vector/std::string on the system heap until you choose to swap:

• kickalloc::PoolAllocator<T> — a standard C++17 allocator you drop into a container: std::vector<T, kickalloc::PoolAllocator<T>> (or the kickalloc::vector<T> / kickalloc::string aliases).
• kickalloc_global — a separately-linkable target that overrides the global operator new/delete family, routing every allocation through per-thread pools transparently.
• kickalloc_malloc — (opt-in via KICKALLOC_OVERRIDE_MALLOC, glibc only) interposes the C family too: malloc/calloc/realloc/free/ posix_memalign/aligned_alloc. Shares one registry with kickalloc_global, so the two overrides agree on who owns a pointer.

Design in one paragraph

Each pool is a wait-free MPSC free list (Vyukov-style intrusive index FIFO, out-of-band links): one thread allocates, any thread frees. Free is one atomic exchange plus two stores — no retry loop; allocation is at most two link hops — no CAS. The price is visibility, not time: a freer preempted mid-push briefly hides its page, so the pool can look exhausted while that free is in flight. Tiers of increasing page size are composed into a MultiPool that routes by request size and alignment. Storage is caller-provided — place it in BSS or mmap it once at startup (optionally huge-paged + mlocked). See lib/include/kickalloc/ and the design notes in the headers.

Requirements

• C++17, CMake ≥ 3.15, pthreads. The pool hot path needs only lock-free 32-bit atomics; the per-thread lease registry (not the alloc/free path) additionally needs a lock-free 64-bit atomic (x86-64 / aarch64).
• Tests need GoogleTest; benchmarks need Google Benchmark. Both are resolved via find_package(... CONFIG) — supply them through Conan (see conan/conanfile.py) or a system install.

Build

The library core is header-only; the two compiled bits are the OS helpers (kickalloc) and the global override (kickalloc_global).

# Stamp the version from the current git tag (vX.Y.Z[-rcN]; off-scheme -> 0.0.0)
./tools/setup/version.sh

# Library only
cmake -S . -B build -DCMAKE_INSTALL_PREFIX=/desired/prefix
cmake --build build -j
cmake --install build

With tests and benchmarks (via Conan)

conan install conan/conanfile.py -o unit_tests=True -o benchmarks=True \
    --output-folder=build --build=missing
cmake -S . -B build \
    -DCMAKE_TOOLCHAIN_FILE=build/conan_toolchain.cmake \
    -DBUILD_UNIT_TESTS=ON -DBUILD_BENCHMARKS=ON
cmake --build build -j
ctest --test-dir build --output-on-failure
./build/kickalloc_microbench          # kickalloc vs malloc / std::pmr

CMake options

Option	Default	Effect
BUILD_UNIT_TESTS	OFF	Build the GoogleTest suites (incl. a stats-off suite)
BUILD_BENCHMARKS	OFF	Build the Google Benchmark microbench
KICKALLOC_ENABLE_STATS	ON	Diagnostic counters; set OFF for hard-RT (changes ABI)
KICKALLOC_OVERRIDE_MALLOC	OFF	Build kickalloc_malloc (glibc only)
ENABLE_TSAN	OFF	ThreadSanitizer (validate the lock-free code)
ENABLE_ASAN	OFF	AddressSanitizer
ENABLE_UBSAN	OFF	UndefinedBehaviorSanitizer
ENABLE_WERROR	OFF	Treat warnings as errors

tools/verify.sh runs the full sweep: Release (stats on/off + both overrides), Debug (asserts + death tests live), and the TSan concurrency suite.

ENABLE_TSAN cannot be combined with ENABLE_ASAN/ENABLE_UBSAN. The concurrency suite is meant to be run under TSan:

cmake -S . -B build-tsan -DBUILD_UNIT_TESTS=ON -DENABLE_TSAN=ON \
    -DCMAKE_TOOLCHAIN_FILE=$PWD/build/conan_toolchain.cmake
cmake --build build-tsan -j && ctest --test-dir build-tsan --output-on-failure

Consume it

pkg-config:

g++ myapp.cc $(pkg-config --cflags --libs kickalloc) -lpthread
# transparent global override: also add -lkickalloc_global

CMake find_package:

find_package(kickalloc CONFIG REQUIRED)
target_link_libraries(myapp PRIVATE kickalloc::kickalloc)
# transparent global override: kickalloc::kickalloc_global

Usage

#include "kickalloc/containers.h"   // kickalloc::vector / kickalloc::string

kickalloc::vector<int> v;          // per-thread default pool resource
v.push_back(42);

// Explicit, sized resource (e.g. a hard-RT buffer):
using Pool = kickalloc::MultiPool<kickalloc::Exhaustion::Strict,
                                  kickalloc::Fallback::Off,
                                  kickalloc::FixedPool<64, 1024>,
                                  kickalloc::FixedPool<4096, 256>>;
static Pool::Storage storage;      // BSS, or mmap Pool::required_bytes()
Pool pool(&storage);
if (not pool.lock_memory())        // commit + pin at startup (mlock populates)
{
    // fail loud: the RT residency guarantee is not in place
}
std::vector<int, kickalloc::PoolAllocator<int, Pool>> rt(kickalloc::PoolAllocator<int, Pool>{pool});

Policy trade-off

• Strict + Off — hard-RT, fail loud: a full tier (or a request larger than the largest tier) yields bad_alloc. Use for explicitly-sized buffers; reserve().
• Cascade + On — best-effort, never fail on capacity: spill to a larger tier, then to the system heap. The default for the container aliases, because a fixed-size pool would otherwise throw at a data-dependent size on vector growth.

The overrides are fail-loud end to end. kickalloc::global exposes: exhausted_count() (lease exhaustion), spill_count() (tier exhaustion served by the system heap), rejected_free_count() (detected double/interior frees), retired_undrained_count() (pools pinned by buffers outliving their thread), pool_owns() (canary that the override is live), and prefault_and_lock() (commit + mlock everything up front; returns false when the pin is refused). Handlers: set_unknown_pointer_handler() for foreign frees, set_rejected_free_handler() for detected double/interior frees.