The lost malloc()

(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

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

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()

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

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()

m

malloc()

mp

mfree()

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

swapmap

/usr/sys/systm.h:2

int	coremap[CMAPSIZ];
int	swapmap[SMAPSIZ];

They're just flat memory regions! So these

malloc()

mfree()

mfree()

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

SMAPSIZ/2

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()

struct map

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

diff(1)

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()

while

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(...);

area = a;

b

Computing sizes

Most of the code directly calls

malloc()

alloc()

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

sizeof

#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

/usr/src/cmd/make/defs:38

make

V7 is the first edition where you also find the

assert()

$ man V7/usr/man/man3/foo.3

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()

malloc()

free()

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

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. So C++'s

new

The

new

operator that both allocates memory from the free store and invokes a constructor to ensure initialization was borrowed from Simula. The

delete

operator was a necessary complement because I did not want C with Classes to depend on a garbage collector. The argument for the

new

operator can be summarized like this. Would you rather write:

X* p = new X(2);

or

struct X * p = (struct X *) malloc(sizeof(struct X));
if (p == 0) error("memory exhausted");
p−>init(2);

and which version are you most likely to make a mistake in? The arguments against -- which were voiced quite a lot at the time -- were "but we don’t really need it," and "but someone will have used

new

as an identifier." Both observations are correct, of course. Introducing operator

new

thus made the use of free store more convenient and less error−prone. This increased its use even further so that the C free store allocation routine

malloc()

used to implement

new

became the most common performance bottleneck in real systems. [...] Having real programs spend 50% or more of their time in

malloc()

wasn’t acceptable.

(emphasis mine :P)

He makes a compelling argument, which I agree with, but doesn't mention the

new()

Sims

This is a big parentheses because I wanted to know how Simula came up with

new

Simula 67 introduced objects, classes, inheritance and subclasses, virtual procedures, coroutines, and discrete event simulation, and featured garbage collection.

And it appeared in 1967. Wow! In the