Branch Allocator

A lock-free buddy allocator for no_std.

Usage

The allocator manages a region of page frames, virtual memory space, or equivalent, using atomic operations and compare-and-swap retry loops to allow allocation and deallocation using only shared references without internal locking. It does not depend on std, and uses alloc only for tests.

Each allocation attempt requires a seed index to begin allocating until a conflict is found. This seed should aim to avoid creating competition between threads, keep track of areas that are likely to already be allocated, and provide new indices to attempt allocation if a prior attempt fails.

The allocator's performance is architecture-dependent, but will automatically select the largest word size that the target can compare-and-swap atomically.

Algorithm

Safe, concurrent allocation is achieved by attempting allocation and then undoing work if a conflict is found, repeating until a subsection of the tree is allocated atomically. This wastes work, but itself is no worse than spinning, except allowing a thread to safely allocate from a non-preemptable context (interrupt; signal) without deadlocking.

The algorithm is derived from Andrea Scarselli's bunch allocator, detailed in their thesis "A Lock-Free Buddy System for Scalable Memory Allocation".

AI Policy

Use of generative AI is not restricted, but contributors will be held accountable for the quality of code submitted.

License

Licensed under either of:

Apache License, Version 2.0 (LICENSE-APACHE or http://apache.org/licenses/LICENSE-2.0)
MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT) at your option.

Contribution