Videos: Memory Allocation

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—so that we end up with, for example, 16-byte alignment.

• Malloc 1: Allocation via syscalls   3:39
  Why we need an allocator that wraps the kernel’s memory-allocation functions.

• Malloc 2: Allocation via the C library   1:55
  A review of the allocation API that is provided by the standard C library.

• Malloc 3: Allocator constraints and goals   4:42
  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.

• Malloc 4: Key allocator questions   1:20
  At a high level, an implemention of an allocator must address five key questions.

• Malloc 5: Naive sbrk allocator   3:13

  This naive sbrk-based allocator is no better than using sbrk directly, but it starts us on a path to a realistic allocator.

  You can run the mm_sbrk.c allocator using mcheck.c and the trace files in traces.zip.

• Malloc 6: “Word” convention for diagrams   1:03
  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.”

• Malloc 7: Allocating pages in chunks   5:00
  Allocating pages from the kernel in chunks by mm_chunk.c provides a slight performance boost for our naive allocator. It also foreshadows how to use mmap instead of sbrk, as in mm_mmap.c.

• Malloc 8: Block headers   4:27
  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.

• Malloc 9: Payload and block pointers   2:35
  How a block header is represented in C and how we manipulate payload pointers to read headers and follow the block list

• Malloc 10: Implicit free list implementation   5:29
  Full implementation of an allocator that suports free where freed blocks are implicitly listed as part of the full block list.

• Malloc 11: Coalescing unallocated blocks   3:53
  To avoid fragmentation, unallocated blocks in a row should be coalesced to a single, unallocated block.

• Malloc 12: Payload and footer pointers   1:54
  Data structures to support coalescing unallocated blocks.

• Malloc 13: Coalescing implementation   4:53
  Full implementation of an allocator with free-block coalescing.