Expand description
A lock-free buddy allocator for no_std.
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.
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 with the new advantage of allowing a core to safely preempt itself from an interrupt context without deadlocking.
The algorithm is heavily inspired by Andrea Scarselli’s bunch allocator, detailed in their thesis “A Lock-Free Buddy System for Scalable Memory Allocation”.
§License
This crate is dual-licensed under the MIT and Apache 2.0 licenses. See the LICENSE-* files in the repository root for details.
Structs§
- Branch
Allocator - An allocator. Stores its order, and a shared reference to a slice of
Atomics, which is used to store an internal tree.