3 months ago
- A simple bump allocator works by moving a cursor forward but cannot free individual allocations.
- To support free(), metadata (header) is stored before the user memory to record size and alignment.
- Alignment requirements cause variable padding between header and user memory, making it impossible to locate the header by simple subtraction.
- A back pointer (stored at a fixed offset before user memory) points to the header, solving the alignment-distance problem.
- Internal fragmentation occurs because padding bytes between metadata and user memory are allocated but never used.
- A free list (linked list of freed blocks) enables reuse; first-fit search finds the first suitable block.
- Splitting large free blocks into smaller pieces avoids wasting memory, but leftover fragments must be large enough to hold their own metadata.
- Coalescing merges adjacent free blocks by having both a header and a footer (size stored at both ends of a block).
- Bugs often arise from misalignment of metadata (e.g., FreeNode), or forgetting to write footers on every size change.