Overview of Implicit Allocator

The implicit allocator:

1. Stores the size of the whole block in bytes in the header.
   • Each header (BoundaryTag) is 8 bytes long.
   • A block that contains a payload of size 24 will be at least 24 + 2 * 8 bytes long.
   • The phrase ”at least” is because: - The block size might be bigger due to the 16-byte payload alignment requirement (see point 2). - We may use a larger block for a smaller payload when looking for a free block in the heap during allocation.
2. Aligns payloads to a multiple of 16.

   • This is done by aligning the first block to a multiple of 24.

   • The initial memory layout is like so:

     

   • After the first call to extend_heap, the memory layout is like so:

     

   • Notice the alignment of the first free block. If an allocation were to be placed in that block, the pointer to the payload (which would be just past the header) would have address 0x20 or 32, which is 16-byte aligned.

   • Additionally, by ensuring block sizes are multiples of 16, we ensure that the payload of the next block is also aligned to a multiple of 16.

Use of the List Struct

The src/introspectable/list.rs file contains a partial implementation of an intrusive linked list. The word intrusive means that unlike regular lists where a ListElem contains the data contained within a node, the node itself contains a ListElem, which will point to other ListElems in the previous and next linked nodes.

Here is a sketch of how you can use the List:

First, you need to define a struct that embeds a ListElem.

#[derive(Clone, Copy, Default, Debug, bytemuck::Pod, bytemuck::Zeroable)]
#[repr(C)]
pub struct FreeBlock {
    header: BoundaryTag,
    elem: ListElem,
}

godbolt
playground

• To push a FreeBlock to a List, you need to:
  1. Get a TypedPointer<FreeBlock>. You should already have this if you are looking to add it to a list.
  2. Get a TypedPointer<ListElem>. This can be done by pointer manipulation similar to the Block::payload and Block::from_payload methods.
  3. Call List::push_front with the memory and pointer from step 2.
• To get the next FreeBlock in the list given a free_block: FreeBlock, you need to:
  1. Get a TypedPointer<ListElem> through free_block.elem.next.
  2. Get a TypedPointer<FreeBlock>. This can be done by pointer manipulation similar to the Block::payload and Block::from_payload methods.
  3. Read the memory using the TypedPointer<FreeBlock>.

Realloc Optimizations

When optimizing the realloc routine, consider the following cases, and how you can reuse the allocation to reallocate in order to save memory and time.