# Branch Allocator
## 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.
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
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
Unless you explicitly state otherwise, any contribution intentionally submitted
for inclusion in the work by you, as defined in the Apache-2.0 license, shall be
dual licensed as above, without any additional terms or conditions.