Crate lock_free_buddy_allocator 

Scalable lock-free buddy system allocator implementation

Algorithm is based on Andrea Scarselli’s thesis.

Into

Algorithm works on top of pre-allocated full binary tree where each node represents a contiguous memory region with size equal to some power of two. For non-leaf nodes, right and left children represent nodes that occupy the same range, but with two times smaller size. For example tree for range 0..2 looks like following

          ----------
         | start: 0 |
     +---| order: 1 | ------+
     |    ---------         |
     v                      v
  ----------            ----------
 | start: 0 |          | start: 1 |
 | order: 0 |          | order: 0 |
  ---------             ---------

Node state

Node state contains information about the node itself and it’s subtree. Node can be in 4 different states: - Occupied – whole node is allocated - Partially occupied – left or right sub-tree have occupied nodes - Coalescing – is going to be freed soon - Free – node is free

which sums to 5 bits of space.

State does not contain information about the parent, which makes allocation faster, since it’s not required to walk sub-tree to update each children state.

To reduce number of CAS instructions, node state contains information about 15 connected nodes (4 levels of the tree). Since it’s not possible to compact 15 * 5 bits into atomic word (without considering double CMPXCH), only leaf nodes contain all 5 bits, but other 8 nodes contain just free / occupied bits.

Example usage

#![feature(allocator_api)]
#![feature(thread_id_value)]

extern crate lock_free_buddy_allocator;

use lock_free_buddy_allocator::buddy_alloc::BuddyAlloc;
use lock_free_buddy_allocator::cpuid;

use std::{alloc::Global, thread};

struct Cpu;

impl cpuid::Cpu for Cpu {
    fn current_cpu() -> usize {
        thread::current().id().as_u64().get() as usize
    }
}

fn main() {
    let buddy: BuddyAlloc<Cpu, std::alloc::Global> =
        BuddyAlloc::<Cpu, _>::new(0, 10, &Global).unwrap();

    buddy.free(buddy.alloc(2).unwrap(), 2);
}

Modules

buddy_alloc

Core allocator structure

cpuid

Definition of a trait for current CPU id