Unix V4 源码中发现的早期 malloc 实现

（抱歉，我忍不住起了个抓眼球的标题 :)

因为另一个突然冒出来的项目想法，我做了点 Unix 考古，翻了翻最初的源码。这是我读别人代码读得最开心的一次——大概是因为它的历史意义。也因为相比现代那些庞然大物，它亲切得令人愉快。

在遥远遥远的 PDP 上，我们的旅程从 1973 年 11 月发布的 Unix 第四版开始，距今已超过半个世纪。C 其实早在一年前发布的第二版中就首次出现了，但并未被广泛使用。V4 之所以特别，是因为到那时连内核的大部分都已经用（我们姑且称之为“中世纪”）C 写成。不过系统已经成长起来，功能相当强大。你会发现今天我们 POSIX 世界里许多 Unix 的东西，在 V4 中就已经存在了。

超级有趣的事实：一盘包含 V4 的磁带去年才被找到！此前人们认为它已彻底湮没于时间之中。

在清理一间储藏室时，我们的员工发现了这盘来自贝尔实验室、约 1973 年的 UNIX v4 磁带。

第一个有意思的地方出现在 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);

是不是很迷人？这个例程在整个程序中被用来分配内存。眯起眼睛看，这不过是个线性分配器。它对大小做对齐，检查区域是否足够大，否则就尝试扩展它。失败时，它就直接冷冰冰地退出。这意味着调用者不必每次都检查 NULL，而事实上他们也确实没有检查。

这个“区域”没有名字，不像今天你会用 arena 那样。不过上面的代码有一个很好的性质：通过使用 sbrk()，当我们扩展堆时，没有任何指针会失效。

而且他们根本懒得释放内存，何必呢？没必要。一切都与程序同生命周期。

在我看来这是最有趣的一点，也是我选这个标题的原因。

在 Dennis 的目录里，你会找到一个名为 malloc.c 的文件。里面有两个函数：

struct map { char *m_size; char *m_addr; }; malloc(mp, size) struct map *mp; mfree(mp, size, aa) struct map *mp;

看着眼熟吗？没错，是带 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);

所以，它们传入了一些对象：coremap 和 swapmap。这些是什么？

来自 /usr/sys/systm.h:2：

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

它们就是平坦的内存区域！所以这些 malloc() 和 mfree() 作用于显式的内存区域！不仅如此，mfree() 还接收它所释放对象的大小，本就该如此。这些接口比传统的 malloc()/free() 好了无数倍。

想象一下使用一个有这种接口的库。你只需丢弃委托给它的整个区域，就能释放它所有的内存资源。堆破坏 bug 的严重性会降低，因为你可以划分内存。你可以轻而易举地限制第三方代码分配的内存量。好处数不胜数……

（旁注：他们在这里出了点小差错，这两个区域的大小本应分别是 CMAPSIZ/2 和 SMAPSIZ/2。他们后来修正了。）

不过，我不认为 Dennis 和 Ken 脑子里想的是这些好处。那么他们为什么采用这种接口，又为什么把内存划分为“core”和“swap”？我认为原因仅仅是硬件限制。这些接口一直保持到 1975 年春天发布的 V6（也许 V7 也是？），幸运的是，关于那一版有一份出了名优秀的资料。

摘自 John Lions 的《A Commentary on the Sixth Edition UNIX Operating System》：

这些涉及两类内存资源的分配与后续释放，即：

对于这两类资源中的每一类，都在一个资源“map”（“coremap”或“swapmap”）内维护一份可用区域列表。指向相应资源“map”的指针总是被传递给“malloc”和“mfree”，这样这些例程本身就不必知道自己处理的是哪类资源。

接着它解释了底层分配算法如何工作。这些并不做线性分配（所以才有了 mfree()）。基本上，它是一个按地址排序的块列表（struct map），你在其中做首次适配，并合并相邻的块。

第六版也是“arena”一词首次出现的地方，在 /usr/source/s4/alloc.s:17：

/char *allocs[2] { /initial empty arena/

回滚 ……回到线性分配的话题……在 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(1024) == -1) { mesg("Out of space\n"); exit(1); top =+ 1024; return(p);

这和之前的 alloc() 差别不大，但这次它能处理任意分配大小。它用一个 while 循环持续扩展区域，直到预留了足够的空间才停止。真正有趣的部分在后面，unsort():143：

unsort(f, l, b) struct line *f; int *b; int *a; int i;

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）