丢失的 malloc() 函数

（抱歉，我忍不住没加个吸引人的标题 :)

受另一个项目想法的启发，我做了一些 Unix 考古，查看了原始源码。这是我阅读他人代码时最有趣的一次——可能是因为其历史意义。但也因为与现代那些庞然大物相比，它的代码是多么令人愉悦地易于接近。

这是一篇简短（-ish）的文章，关于他们如何处理在 C 中分配和管理内存这一平凡而枯燥的任务。未来我想读更多关于 Unix 操作系统、其设计、架构和实现的内容。

很久以前...

在遥远的 PDP 机上，我们的旅程始于第四版 Unix，发布于 1973 年 11 月，距今半个多世纪了。C 语言实际上最早出现在前一年发布的第二版中，但并未被广泛使用。V4 很特别，因为到那时，甚至大部分内核都是用（姑且称之为“中世纪”的）C 编写的。

然而，系统已经发展壮大，并且相当强大。你会发现，我们在 POSIX 领域今天看到的许多 Unix 特性，在 V4 中就已经存在了。

超级有趣的事实：包含 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()，当我们扩展堆时，没有指针会失效。

而且他们不费心去释放内存，因为为什么要呢？没必要。一切都在程序的整个生命周期内存在。

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;

看起来很眼熟？没错，就是带个 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() 好了无限倍。

想象一下使用一个具有这种接口的库。你只需丢弃你委托给它的整个区域，就可以释放其所有内存资源。堆损坏错误会不那么严重，因为你可以划分内存。你可以轻松地限制第三方代码分配的内存量。好处不胜枚举……

（旁注：他们在这里稍微搞错了，区域的大小本应分别为 CMAPSIZ/2 和 SMAPSIZ/2。他们后来确实修复了这个问题。）

然而，我不认为 Dennis 和 Ken 考虑到了所有这些好处。那么，他们为什么选择这种接口，又为什么要将内存划分为“核心”和“交换”呢？我认为原因仅仅是硬件限制。这些接口一直保持到 V6（也许 V7 也是？），发布于 1975 年的春天，幸运的是，关于该版本有一份臭名昭著的优秀资源。

来自 John Lions 的《第六版 UNIX 操作系统评注》：

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

· 主内存，以 32 个字（64 字节）为单位；

· 磁盘交换区，以 256 个字（512 字节）为单位。

对于这两种类型的资源中的每一种，都在一个资源的“映射”（即“coremap”或“swapmap”）中维护一个可用区域的列表。一个指向适当资源“映射”的指针总是被传递给“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); }

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, r