Struct crndm::alloc::BuddyAlg

#[repr(C)]pub struct BuddyAlg<A: MemPool> { /* fields omitted */ }

Buddy Allocation Algorithm

It contains 61 free-lists of available buddy blocks to keep at most 2^64 bytes including meta-data information. A free-list k keeps all available memory blocks of size 2^k bytes. Assuming that Buddy has a size of 8 bytes, the shape of lists can be like this:

   [8]: [8] -> [8]
  [16]: [8|8] -> [8|8]
  [32]: [8|24] -> [8|24] -> [8|24]
  [64]: [8|56]
  ...

The first 8 bytes of each free block is meta-data. Once they are selected for occupation, this 8 byte is going to be used, too. So, the smallest block size is 8 bytes.

Implementations

impl<A: MemPool> BuddyAlg<A>

pub fn init(&mut self, size: usize)

Pool Initialization with a given device size

pub unsafe fn log(&mut self, off: u64, data: u64)

Adds a new low-level 64-bit log entry

pub unsafe fn drop_on_failure(&mut self, off: u64, len: usize)

Adds a new low-level DropOnFailure log entry

pub unsafe fn aux_push(&mut self, off: u64, data: u64)

Adds a new entry to the auxiliary list of changes

pub fn drain_aux(&mut self)

Drain the auxiliary list of changes

The functions alloc_impl and dealloc_impl fills up the auxiliary buffer with the required changes to the free lists. Then, they call this function to materialize the changes. The changes are not valid until drain_aux() is called. The recovery procedure performs changes if they are valid. Otherwise, it discards them.

pub fn discard(&mut self)

Discards the changes in the auxiliary buffer

pub unsafe fn alloc_impl(&mut self, len: usize, perform: bool) -> u64

Generates required changes to the metadata for allocating a new memory block with the size len, and materialize them by calling drain_aux according to the perform argument. If successful, it returns the offset of the available free block. Otherwise, u64::MAX is returned.

pub unsafe fn dealloc_impl(&mut self, off: u64, len: usize, perform: bool)

Generates required changes to the metadata for reclaiming the memory block at offset off with the size of len, and materialize them by calling drain_aux according to the perform argument.

pub unsafe fn perform(&mut self)

Materializes the changes in the auxiliary list and clears the drop log records

pub fn is_allocated(&mut self, off: u64, _len: usize) -> bool

Determines if the given address range is allocated

pub fn recover(&mut self)

Starts the recovery procedure. If the crash happened while draining the auxiliary buffer, it continues draining it and making the remaining changes. It is rational because the DropOnFailure log was taken before draining the auxiliary buffer. When the draining is finished, the higher-level log reclaims the allocation in the higher level recovery procedure.

pub fn size(&self) -> usize

Returns the pool size

pub fn available(&self) -> usize

Returns the total available space in the pool

pub fn used(&self) -> usize

Returns the total number of bytes used from the pool

pub fn print(&self)

Prints the free lists