mymalloc
My own malloc and free in C, with error detection, leak reports and a benchmark against the real thing.
- 6 msper memgrind workload run, against 3 ms for the system malloc
The whole heap is one static 4,096-byte array. It's carved into chunks, and every chunk starts with an 8-byte header: a flag saying whether it's in use, and the chunk's size. Because each header knows its own size, jumping that many bytes lands on the next header, so the chunks form a linked list without storing a single pointer.
malloc rounds the request up to a multiple of 8, walks the list from the start and takes the first free chunk that fits. If the chunk is bigger than needed, it's split, and the leftover becomes a new free chunk with its own header.
free walks the list looking for a chunk whose data starts exactly at the pointer it was given. If there isn't one, the pointer was never allocated, was already freed, or points into the middle of a chunk, and it stops with an error naming the file and line. Otherwise it marks the chunk free and merges it with any free neighbours, so the heap doesn't break into unusable scraps. When the program exits, a leak checker reports anything still allocated.
Program
Calls malloc and free
mymalloc
First fit, split, merge, check errors
Heap
4,096 bytes of chunks, each with an 8-byte header
- Program and mymalloc
- mymalloc and Heap
See it work
The heap, one call at a time
a = malloc(20)20 rounds up to 24, plus the header makes 32. The one big free chunk is split.
1a32 B+32 to next0free4056 Bend of heapb = malloc(100)100 rounds up to 104, plus the header makes 112, split from the free chunk.
1a32 B+32 to next1b112 B+112 to next0free3944 Bend of heapc = malloc(8)8 bytes of data plus the header.
1a32 B+32 to next1b112 B+112 to next1c16 B+16 to next0free3928 Bend of heapfree(b)b is marked free. Its neighbours are both in use, so nothing merges.
1a32 B+32 to next0free112 B+112 to next1c16 B+16 to next0free3928 Bend of heapfree(a)a is free and so is the chunk after it, so they merge: 32 + 112 = 144.
0free144 B+144 to next1c16 B+16 to next0free3928 Bend of heapfree(c)c merges with both sides, and the heap is one free chunk again.
0free4088 Bend of heap
Taken from mymalloc's own debug output for this sequence of calls. The narrow box at the start of each chunk is its 8-byte header, 1 if in use and 0 if free. Sizes include the header, and each header's size is the jump to the next chunk. Not to scale.
Catching a bad free, then the leaks
char *a = malloc(20);
char *b = malloc(100);
free(a + 4); // not the start of a chunk
return 0;What it printed
$ ./leakfree: Invalid pointer (leak.c:5)mymalloc: 144 bytes leaked in 2 objects.
The real output. free stops the program, and on the way out the leak checker reports a and b, 32 + 112 bytes.