There is a very simple free list-based implementation of malloc in The C Programming Language, 2nd edition, by Brian Kernighan and Dennis Ritchie (“K&R”). Because it’s 🦃 Holiday Season 🎄 and I am taking time off, I decided to play around with it.

This is the malloc implementation from pp. 185 – 189 of K&R. I have tried to transcribe it exactly, even down to the spacing of the end-of-line comments.

To build on a modern system, I had to make a few trivial adjustments.

This is a fairly faithful version of K&R, but which replaces sbrk with mmap, uses C’s type system somewhat better (it is -Weverything-clean), and does a bit of style cleanup.

This version parameterizes the global state in the 2 previous versions by making an Arena object an explicit argument to all functions in the public interface. This enables various interesting enhancements to the API and to the implementation.