The C library’s malloc and free implementations build on the kernel-supplied allocation system calls to provide more efficient and convenient memory management to applications. We look at how allocation works with the goal of implementing out own allocator.
The allocator that we develop mostly follows the book, but some
details are different—
- Why we need an allocator that wraps the kernel’s memory-allocation functions.
- A review of the allocation API that is provided by the standard C library.
- About the right and responsibilities of an application and an allocator, and performance goals for the allocator—
on the path to implementing our own allocator.
- At a high level, an implemention of an allocator must address five key questions.
- This naive sbrk-based allocator is no better than using sbrk directly, but it starts us on a path to a realistic allocator.
- To make our diagrams both compact and realistic, we adopt the convention of writing memory and numbers in multiples of 16 (instead of individual bytes), and we call that a “word.”
- To support freeing memory blocks, our allocator needs to keep track of block sizes and allocation status. We use a block header for that information.
- How a block header is represented in C and how we manipulate payload pointers to read headers and follow the block list
- Full implementation of an allocator that suports free where freed blocks are implicitly listed as part of the full block list.
- To avoid fragmentation, unallocated blocks in a row should be coalesced to a single, unallocated block.
- Data structures to support coalescing unallocated blocks.
- Full implementation of an allocator with free-block coalescing.