Memory Allocator Lab

Project roadmap

1. 01

   Design the allocator

   ~2.5h

   Write DESIGN.md: memory is taken from the OS in large arenas with mmap; each block has a header (size, flags for free and in use, and a magic number) and a footer copy of the size (a boundary tag) so the previous block can be found for merging; free blocks sit in segregated lists by size class; blocks are 16-byte aligned; and debug features (canaries after each block, fill patterns and an allocation record with the caller's address) can be turned on with an environment variable. Done when: DESIGN.md shows the block layout and every feature with diagrams.

2. 02

   Allocate and free with free lists

   ~3h

   Implement my_malloc: round the size up for alignment, find a block in the right size class list (or a larger one), split it if the rest is big enough, and get a new arena with mmap when nothing fits (very large requests get their own mmap). Implement my_free: mark the block free, merge it with free neighbors using the headers and footers, and put it in the right list. Done when: a test with random sizes allocates and frees thousands of blocks correctly.

3. 03

   Add calloc and realloc

   ~1.5h

   Implement my_calloc with an overflow check on count × size, and my_realloc: shrink in place, grow in place when the next block is free and big enough, and otherwise allocate, copy and free, with realloc(NULL, n) and realloc(p, 0) behaving like the standard. Make all functions thread-safe with a mutex (or per-thread arenas as an extra). Done when: tests show realloc keeps the data in every case, including with several threads.

4. 04

   Add debugging features

   ~2.5h

   Detect double frees and pointers that weren't allocated (by checking the header's magic number and flags), write canary bytes after each block and check them on free, fill new blocks with 0xAA and freed blocks with 0xDD so bugs show up, and record each allocation's size and caller (with __builtin_return_address). Report problems with a clear message and abort. Done when: small programs with a double free, a buffer overflow and a use-after-free are each caught with a clear report.

5. 05

   Report statistics and leaks

   ~1.5h

   Keep counters: bytes in use, peak use, number of allocations and frees, arena memory from the OS, and fragmentation (free bytes that are too scattered to be useful). At exit (with atexit or a destructor function), print the statistics and every block still allocated, with its size and caller, as a leak report. Done when: a program that forgets to free memory gets a leak report pointing to the allocations.

6. 06

   Run real programs

   ~1.5h

   Build the allocator as a shared library that defines malloc, free, calloc, realloc (and posix_memalign) and run real programs with LD_PRELOAD (such as ls, sort on a big file, or a small program of your own), fixing anything that breaks, such as the allocator itself calling malloc through printf. Done when: several real programs run correctly with your allocator, and the statistics print at exit.

7. 07

   Test and benchmark

   ~2h

   Write a stress test with random operations checking data patterns in every block, and benchmark your allocator against the system's on workloads with small, mixed and large allocations, recording speed and peak memory in README.md with and without the debug features. Done when: the stress test passes, and README.md shows the comparison.

Resources

• DocsOperating Systems: Three Easy Pieces, free-space management (chapter)
• Docsmmap(2) man page
• ArticleDan Luu: malloc tutorial
• Docsld.so(8) man page (LD_PRELOAD)
• Docsglibc malloc internals (a design to compare with)