Custom Memory Allocator (malloc/free clone)

Project roadmap

1. 01

   Design the block header

   ~1.5h

   Define a header struct placed right before every block: its size, whether it's free, and pointers to the next and previous blocks. Decide the alignment (16 bytes on 64-bit systems) and write helpers to round sizes up and to convert between a header and the pointer given to the user. Draw the heap layout in DESIGN.md. Done when: DESIGN.md shows the layout, and the helper functions pass small tests.

2. 02

   Implement my_malloc

   ~3h

   Implement my_malloc(size): search the free list for the first block big enough (first fit), split it when the leftover is large enough to hold a header plus a minimum size, and mark it used. When nothing fits, grow the heap with sbrk, checking for failure. Return NULL for size 0 or when memory runs out. Done when: allocating blocks of various sizes returns aligned, non-overlapping pointers.

3. 03

   Implement my_free with merging

   ~2.5h

   Implement my_free(ptr): ignore NULL, mark the block free, and merge it with the next and previous blocks when they're free. Add a debug check that detects freeing a pointer twice or a pointer the allocator never returned (for example with a magic number in the header). Done when: freeing neighboring blocks merges them into one, and a double free is caught in debug builds.

4. 04

   Implement my_calloc and my_realloc

   ~2h

   Implement my_calloc(n, size), checking that n × size doesn't overflow, and zeroing the memory. Implement my_realloc(ptr, size): NULL behaves like malloc, size 0 like free, shrinking splits the block, growing uses the next block when it's free and large enough, and otherwise allocates a new block, copies the data and frees the old one. Done when: tests show realloc keeps the data in every case.

5. 05

   Stress test

   ~2h

   Write a test program that performs 100,000 random operations (allocate random sizes, free random blocks, and realloc) and fills each block with a pattern based on its address, checking the pattern before freeing, to detect overlapping or corrupted blocks. Add a heap check function that walks all blocks and verifies headers, sizes and that no two free blocks are next to each other. Done when: the stress test and heap check pass with different random seeds.

6. 06

   Benchmark and improve

   ~2h

   Measure the time for several workloads (many small blocks, mixed sizes, and a lot of realloc) with your allocator and the system's malloc, and measure fragmentation (heap size compared with memory in use). Try one improvement, such as best fit or separate free lists by size, and record the before and after numbers in README.md. Done when: README.md compares the results and explains the trade-offs.

Resources

• ArticleDan Luu: malloc tutorial
• Docssbrk(2) man page
• DocsOperating Systems: Three Easy Pieces, free-space management (chapter)
• Docsmalloc(3) man page