the lost malloc() - gardenweb

2026-10-29 (Sorry, I couldn't resist not putting a catchy title :) Prompted by another project idea that popped into my mind, I did some Unix archaeology and looked at the original sources. This is the most fun I've ever had reading someone else's code - probably due to the historical significance. But also because of how delightfully approachable it was, compared to modern monstrocities. This is a short(-ish) post regarding how they handled the mundane and boring task of allocating and managing memory (in C). In the future I'd like to read more about Unix the OS, its design, architecture & implementation. A long time ago... In a PDP far, far away, our journey begins with the fourth edition of Unix, released November '73, more than half a century ago. C actually first appeared in the second edition, released the year before, but wasn't extensively used. V4 is special because even the majority of the kernel was written in (let's call it "medieval") C by that point. The system had grown, however, and it was quite capable. You'll find that many Unix things we have today in POSIX-land were already present in V4. Super fun fact: A tape containing V4 was only found last year! Previously, it was thought to be completely lost to time. While cleaning a storage room, our staff found this tape containing UNIX v4 from Bell Labs, circa 1973 ~ Rob Ricci Linear allocation The first interesting bit is found among the C "compiler" sources. In quotes, because it wasn't a monolithic compiler as we know it today. Rather, it was a set of distinct tools which you chained in order to get an object file from C code. In /usr/c/c20.c:814, from what I can gather a very primitive optimiser, if you will (referred to as "C object code improver" in V5; there aren't many comments in V4) you see: alloc(an) { register int n; register char *p; n = an; n++; n =& ~01; if (lasta+n >= lastr) { if (sbrk(2000) == -1) { write(2, "Out of space\n", 14); exit(1); } lastr =+ 2000; } p = lasta; lasta =+ n; return(p); } Isn't that fascinating? This routine is used throughout the program to allocate memory. And if you squint, this is just a linear allocator. It aligns the size, checks if the region is big enough, otherwise tries to extend it. On failure, it just cold-exits. Which means callers don't have to check for NULL every single time, and indeed they do not. The "region" isn't named, unlike how you'd do it today with arenas. However, the above does have a nice property, in that by using sbrk(), when we extend the heap, no pointer is invalidated. And they don't bother freeing memory, because why would they? There's no need. Everything exists for the lifetime of the program. dmr/malloc This is the most interesting bit in my opinion, and the reason why I chose that title. In Dennis' directory, you find a file named malloc.c. And you see two functions there: struct map { char *m_size; char *m_addr; }; malloc(mp, size) struct map *mp; mfree(mp, size, aa) struct map *mp; Seems familiar? Yep, it's mfree() with an m. These functions obviously deal with memory (de)allocation, and are the precursor to the ones we're familiar with today. But, the interfaces are different. malloc() receives an additional first argument called mp (for "map"), and so does mfree(). What is that? Well, let's see how they're used: p = malloc(coremap, sizeof foo); ... mfree(coremap, sizeof foo, p); q = malloc(swapmap, sizeof bar); ... mfree(swapmap, sizeof bar, q); So, they pass in some objects coremap and swapmap. What are those? From /usr/sys/systm.h:2: int coremap[CMAPSIZ]; int swapmap[SMAPSIZ]; They're just flat memory regions! So these malloc() and mfree() work on explicit memory regions! Not only that, mfree() receives the size of the object it is deallocating, as it should. Those are just infinitely-times better interfaces than traditional malloc()/free(). Imagine using a library that has such an interface. You could deallocate all its memory resources by just discarding the entire region you delegated to it. Heap corruption bugs would be less severe because you could partition memory. You could trivially limit the amount of memory third party code allocates. The list goes on and on... (Side note: They slightly messed up here and the regions should've been sized CMAPSIZ/2 and SMAPSIZ/2 respectively. They did fix that later.) However, I don't think all these benefits were in the minds of Dennis and Ken. So why did they go with that interface and why did they partition memory to "core" and "swap"? The reason is, I believe, just hardware constraints. These interfaces stay like that up to V6 (maybe V7 too?), released the spring of '75, and thankfully there's an infamously good resource about that edition. Brian Kernighan, from Wikipedia. From A Commentary on the Sixth Edition UNIX Operating System by John Lions: These are concerned with the allocation and subsequent release of two kinds of memory resources, namely: main memory in units of 32 words (64 bytes); disk swap area in units of 256 words (512 bytes). For each of these two kinds of resource, a list of available areas is maintained within a resource "map" (either "coremap" or "swapmap"). A pointer to the appropriate resource "map" is always passed to "malloc" and "mfree" so that the routines themselves do not have to know the kind of resource with which they are dealing. And it goes on to explain how the underlying allocation algorithm works. These do not do linear allocation (hence the mfree()). Basically, it's a list of blocks (struct map), ordered by address, where you do first-fit and also coalesce neighbour blocks. The sixth edition is also the first where the term "arena" appears, in /usr/source/s4/alloc.s:17: /char *allocs[2] { /*initial empty arena*/ Rolling back ... to the topic of linear allocation... In V6's /usr/source/s1/diff1.c:88, I think the first ever version of diff(1), you find: char *area; char *top; alloc(n) { register char *p; p = area; n = (n+1) & ~1; area =+ n; while(area > top) { if(sbrk(1024) == -1) { mesg("Out of space\n"); exit(1); } top =+ 1024; } return(p); } This is not all that much different from the previous alloc(), but this time it handles any allocation size. It uses a while to continue extending the region and stops when enough space has been reserved. The actual interesting part happens later, at unsort():143: unsort(f, l, b) struct line *f; int *b; { int *a; int i; a = alloc((l+1)*sizeof(a[0])); for(i=1;i<=l;i++) a[f[i].serial] = f[i].value; for(i=1;i<=l;i++) b[i] = a[i]; area = a; } I'm not exactly sure what that function does, but it doesn't matter. What matters is that they allocate some memory (a = alloc(...);), then roll back the region (area = a;)! Though they subsequently just copy it to b, so it seems like this was redundant. Computing sizes Most of the code directly calls malloc()/alloc() and friends, and inlines the size computation logic. Like the line we saw earlier: a = alloc((l+1)*sizeof(a[0])); I don't do that anymore, and neither should you! I use a couple macros akin to C++'s new that handle all the sizeof business. But I am a dumb-dumb. Surely these guys must've come across the same pain points, and, if so, what did they do? Let's jump to V7, released January '79, four years after V6. You find this macro: #define ALLOC(x) (struct x *) ckalloc(sizeof(struct x)) where they use it like: struct foo { ... }; p = ALLOC(foo); Nice! It's interesting to note where you find it; In /usr/src/cmd/f77/defines:38 and /usr/src/cmd/make/defs:38. Slightly suspicious. The former is part of the Fortran 77 compiler and latter of make. Stuart Feldman is the person who worked on both of those programs! It's clear that multiple people were working on the system at that time. A macro like that isn't used in any other program, sadly. V7 is the first edition where you also find the assert() macro, and it was used extensively back then too. Good job! They also significantly expanded the number of man pages. Fun fact: I did $ man V7/usr/man/man3/foo.3 -- on 47 year old pages -- and it worked first try absolutely fine. Let's go to V8, released in February '85, four years before the first C standard. You find this wild macro in /usr/src/cmd/ideal/memut.c:7: char *fooalloc; #define tryalloc(new,kind) \ if (!(new =(kind *) malloc(sizeof (kind)))) {\ emergency ();\ if (!(new =(kind *) malloc(sizeof (kind)))) {\ fprintf (stderr, "ideal: Out of space\n");\ exit (1);\ }\ };\ for (fooalloc = (char *) new;\ fooalloc < ((char *) new) + sizeof (kind);\ fooalloc ++)\ *fooalloc = '\0'; If someone is too harsh because you used macros, point them at the above. Usage is bit different this time: struct foo *x; tryalloc(x, struct foo); I decided to include it because the macro zero-initialises by default whatever was allocated! You also see a more familiar-looking malloc() being used. It appears this is the edition that they switched to the more traditional malloc()/free() interfaces we know. I'll hypothesize why that is at the very end. But it gets even more interesting. In V8 you also find these macros: #define new(type) ((type *) alloc (sizeof (type))) #define new(t) ((t *) alloc (sizeof (t))) #define new(s) (s *)alloc(sizeof (s)) When I saw these definitions I jumped out of my chair. It's basically how I'd define it too! You'll find them in: /usr/src/cmd/finddev.c:245, part of finddev(8). /usr/src/cmd/asd/asd.h:13, part of asd(8). /usr/include/ic.h:55, part of *checks notes* I have no idea.

respectively.

Unfortunately, I can't find the author(s) of any of these. Cfront In V8, you'll also find Cfront, a.k.a.

medieval C++.

It's then reasonable to assume that Stroustrup was inspired by the above macros and decided to incorporate new as a language-level feature. However, in A History of C++: 1979−1991, he writes: In Simula, it is not possible to have local or global variables of class types; that is, every object of a class must be allocated on the free store using the new operator.

Huh.