Language FoundationsC Programming Deep DiveMedium

Implement malloc and free

Master the fundamental concepts of c programming deep dive through this focused micro-challenge.

~45 minutes C Programming Deep Dive Ready to learn

Topic Overview

What glibc Hides From You

When you call malloc(100) on Linux, glibc's ptmalloc searches free lists, may mmap fresh pages from the kernel, and returns a pointer aligned to 16 bytes. Your exercise strips that down to a fixed char heap[4096] and an explicit Block header: size, used flag, and next pointer. That header-before-payload layout is the same idea jemalloc and tcmalloc use, just with fancier bookkeeping.

First-Fit and Coalescing

c
Loading…

First-fit: walk the list, take the first free block large enough
Alignment: round requested size up to 8 bytes before comparing
Free: mark the block unused, then merge with adjacent free neighbors to fight fragmentation

Returning user memory means skipping the header: (char*)block + sizeof(Block). Finding the header from a user pointer reverses that subtraction.

For this exercise, you will finish my_malloc and implement my_free with coalescing on a static buffer. This task asks you to see allocation as list surgery, because heap exploitation CVEs and allocator tuning both start with understanding these block headers.

Keep the relevant man page, ABI doc, or Rust reference chapter open while you work. When your output disagrees with the reference implementation on the same machine, the mismatch is usually an alignment rule, an off-by-one terminator, or a register slot you misread in GDB.

Implementation Task

Your Task

Implement my_malloc and my_free on top of a 4096-byte static array, the way a tiny embedded allocator works:

a linked list of blocks, each preceded by a header;
first-fit search;
splitting of large free blocks;
coalescing of adjacent free blocks on free.

Then run the fixed scenario selected on stdin and print the heap.

Heap layout

Header: struct Block { size_t size; int used; struct Block *next; }, which is 24 bytes on x86-64. size counts the payload bytes after the header.
Initial state: one free block at the start of the buffer, with size 4096 - 24 = 4072.
my_malloc(n): round n up to a multiple of 8 (at least 8). Take the first free block that is big enough. If it has room for another header plus 8 bytes, split it: the remainder becomes a new free block right after the payload.
my_free(p): NULL does nothing. Otherwise mark the block free, then merge every free block with a free successor, walking from the list head.

Input

One word: alloc, free, merge, edge or multi.

Scenarios and output

alloc: allocate 64, 128 and 32 bytes, then print After allocations: and the block list.
free: allocate 64, 128 and 32 bytes, free the 128-byte block, then print After freeing p2: and the block list.
merge: allocate three 64-byte blocks, free the first two, then the third. Print Blocks merged and free_blocks=N, the number of free blocks left.
edge: call my_malloc(0), my_malloc(4096) and my_free(NULL). Print zero=nonnull if the 0-byte request returned a pointer (zero=null_or_ok if it returned NULL), big=null if the 4096-byte request returned NULL (big=nonnull otherwise), then All edge cases pass. Under the rules above, a 0-byte request is rounded up to 8 bytes and succeeds, and 4096 bytes is more than the 4072 free bytes and fails, so the test expects zero=nonnull and big=null.
multi: allocate eight 32-byte blocks and free them all. Print All allocations successful and ok=1 if all eight succeeded (else ok=0).

The block list is one line per block, in list order: Block I: used=U size=S.

Example

Input:

c
Loading…

Output:

c
Loading…

Requirements

Keep all metadata inside the 4096-byte buffer. No real malloc.
Coalesce on free, so freeing neighbours restores one large free block.

Hidden tests cover freeing a middle block, coalescing into a single free block, zero-size and oversized requests, and many small allocations.