本文为原文前 6,000 字符的节选翻译，完整内容请查看原文。

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.

（抱歉，我实在忍不住想写个吸引人的标题 :) 受脑海中冒出的另一个项目想法启发，我进行了一些 Unix 考古工作，查阅了原始源代码。这是我读过别人的代码中最有趣的一次——大概是因为其历史意义。但也因为与现代的庞然大物相比，它显得格外平易近人。这是一篇关于他们如何处理 C 语言中分配和管理内存这一枯燥乏味任务的短文。未来，我想阅读更多关于 Unix 操作系统、其设计、架构及实现的内容。

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

很久很久以前……在遥远的 PDP 上，我们的旅程始于 1973 年 11 月发布的 Unix 第四版，距今已超过半个世纪。C 语言实际上是在前一年发布的第二版中首次出现的，但当时并未被广泛使用。V4 很特别，因为到那时为止，即使是内核的大部分也已经用（姑且称之为“中世纪”）C 语言编写了。然而，系统已经发展壮大，功能相当强大。你会发现，今天我们在 POSIX 世界中拥有的许多 Unix 特性在 V4 中就已经存在了。一个超级有趣的冷知识：包含 V4 的磁带直到去年才被发现！此前，人们认为它已经彻底失传。在清理储藏室时，我们的工作人员发现了这盘来自贝尔实验室、大约 1973 年的 UNIX v4 磁带 ~ 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:

线性分配。第一个有趣的部分出现在 C 语言“编译器”的源代码中。之所以加引号，是因为它不像我们今天所知的单体编译器。相反，它是一组独立的工具，你需要将它们串联起来，才能从 C 代码中获得目标文件。在 /usr/c/c20.c:814 中，据我推测，这是一个非常原始的优化器（在 V5 中被称为“C 目标代码改进器”；V4 中注释不多），你可以看到：

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.

这难道不迷人吗？这个例程在整个程序中被用来分配内存。如果你仔细观察，这只是一个线性分配器。它对齐大小，检查区域是否足够大，否则尝试扩展它。如果失败，它直接冷退出。这意味着调用者不必每次都检查 NULL，事实上他们也确实没检查。这个“区域”没有命名，不像今天使用内存池（arenas）那样。然而，上述代码有一个很好的特性：通过使用 sbrk()，当我们扩展堆时，没有任何指针会失效。而且他们也不费心去释放内存，因为为什么要释放呢？没必要。一切都存在于程序的整个生命周期中。

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:

dmr/malloc。在我看来，这是最有趣的部分，也是我选择这个标题的原因。在 Dennis 的目录中，你会发现一个名为 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() 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:

看起来很眼熟？没错，就是带 m 的 mfree()。这些函数显然处理内存的分配与释放，是我们今天所熟悉的那些函数的先驱。但是，接口不同。malloc() 接收一个额外的第一个参数 mp（代表“map”），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 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.)

所以，他们传入了一些对象 coremap 和 swapmap。那些是什么？来自 /usr/sys/systm.h:2：int coremap[CMAPSIZ]; int swapmap[SMAPSIZ]; 它们只是平坦的内存区域！所以这些 malloc() 和 mfree() 是在显式的内存区域上工作的！不仅如此，mfree() 还接收它正在释放的对象的大小，这本该如此。这些接口比传统的 malloc()/free() 好上无数倍。想象一下使用具有这种接口的库。你只需丢弃分配给它的整个区域，就可以释放其所有的内存资源。堆损坏错误的影响会减轻，因为你可以划分内存。你可以轻而易举地限制第三方代码分配的内存量。这样的例子不胜枚举……（旁注：他们在这里稍微搞砸了，区域的大小本应分别是 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:

然而，我不认为 Dennis 和 Ken 当时考虑到了所有这些好处。那么，他们为什么要采用那种接口，为什么要将内存划分为“核心（core）”和“交换（swap）”呢？我相信原因仅仅是硬件限制。这些接口一直保持到 1975 年春季发布的 V6（也许还有 V7？），幸运的是，有一份关于该版本的著名优秀资源。Brian Kernighan，来自维基百科。摘自 John Lions 所著的《Unix 操作系统第六版注释》：

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.

这些函数涉及两种内存资源的分配和随后的释放，即：以 32 字（64 字节）为单位的主内存；以 256 字（512 字节）为单位的磁盘交换区。对于这两种资源中的每一种，可用区域列表都维护在资源“映射表”（“coremap”或“swapmap”）中。指向相应资源“映射表”的指针总是被传递给“malloc”和“mfree”，这样例程本身就不必知道它们正在处理哪种资源。

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/

文中继续解释了底层分配算法是如何工作的。这些函数不进行线性分配（因此才需要 mfree()）。基本上，它是一个按地址排序的块列表（struct map），你可以在其中执行首次适应算法，并合并相邻的块。第六版也是“arena”一词首次出现的地方，在 /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:

回到……线性分配的话题……在 V6 的 /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(102