Blogger traces Unix's earliest malloc() in recovered V4 source code
Archived — this story has rotated out of today’s deck. It is kept here in full.
The gist
A blogger examining recovered Unix V4 source found an early allocator in c20.c and a map-based malloc.c in Dennis Ritchie's directory.
The find shows how memory allocation looked before the malloc()/free() pair programmers use today.
Background
The post is Unix archaeology: a blogger reading original source code through The Unix Tree, an archive of early Unix sources, after a tape containing the fourth edition of Unix (V4) was found last year, having previously been thought lost. Unix is the operating system whose early designs shaped much of today's computing, and Dennis Ritchie, a Bell Labs figure, is named alongside Ken Thompson as behind the interface decisions. The blogger dug into how memory was handed out in V4, where C had only recently appeared and was not yet widely used.
How it unfolded
- 1973 -11The fourth edition of Unix is released; most of the kernel is written in C by this point.
- 1975 (spring)The sixth edition of Unix is released, keeping the same malloc()/mfree() interfaces as V4.
- recentlyA tape containing V4 is found, having previously been thought completely lost to time.
- recentlyIn /usr/c/c20.c:814, a primitive allocator routine aligns the size, checks whether the region is big enough, and otherwise calls sbrk(2000), exiting with "Out of space" on failure.
- recentlyIn Dennis Ritchie's directory, /usr/sys/dmr/malloc.c contains malloc(mp, size) and mfree(mp, size, aa), which take an explicit map argument; coremap and swapmap are declared in /usr/sys/systm.h.
Who’s saying what
- Author
- The blogger calls the V4 allocator "just a linear allocator" where callers need not check for NULL and memory is never freed, since everything lives for the program's lifetime.
- Author
- The blogger says the map-based malloc()/mfree() interfaces are "infinitely-times better interfaces than traditional malloc()/free()".
- Author
- The blogger believes the map-based interface and core/swap split came from "just hardware constraints," and that the regions should have been sized CMAPSIZ/2 and SMAPSIZ/2, which "they did fix that later."
- Expert
- John Lions, author of A Commentary on the Sixth Edition UNIX Operating System, describes the functions as handling main memory in units of 32 words (64 bytes) and disk swap area in units of 256 words (512 bytes).
Still unverified
The blogger says "from what I can gather" that c20.c is a very primitive optimiser, noting V4 has few comments; the blogger also says the interfaces stay the same up to V6 "(maybe V7 too?)" and presents the hardware-constraint explanation as a belief rather than documented fact.