Struct corundum::alloc::BuddyAlg [−][src]
#[repr(C)]pub struct BuddyAlg<A: MemPool> { /* fields omitted */ }
Expand description
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
Adds a new low-level DropOnFailure
log entry
Adds a new entry to the auxiliary list of changes
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.
Materializes the changes in the auxiliary list and clears the drop log records
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.
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.
Determines if the given address range is allocated
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.