图5-1 htab和freelist结构
所有非平凡的C程序都会在运行时分配内存。标准C库提供了4个内存管理例程：malloc、calloc、realloc和free。Mem接口将这些例程重新包装为一组宏和例程，使之不那么容易出错，并提供了一些额外的功能。
遗憾的是，C程序中内存管理方面的bug很常见，而且通常难于诊断和修复。例如，下述代码片段
p = malloc(nbytes); ... free(p);
调用malloc分配nbytes长的内存块，将该内存块第一个字节的地址赋值给p，使用p和它指向的内存块，最终释放该内存块。在调用free之后，p包含一个悬挂指针——指向逻辑上不存在的内存的指针。接下来反引用p是一个错误，但如果该内存块没有因其他原因而再次分配出去，这个错误可能不会被检测到。这种行为是使得此类内存访问错误难于诊断的原因：在检测到错误时，错误暴露的时间和位置可能与错误的来源距离颇远。
下述代码片段
p = malloc(nbytes); ... free(p); ... free(p);
说明了另一个错误：释放空闲的内存。该错误通常会破坏内存管理函数使用的数据结构，但在下一次调用某个内存管理函数之前，这个错误可能不会被检测到。
另一个错误是释放并非由malloc、calloc或realloc分配的内存。例如，考虑下述程序：
char buf[20], *p;
if (n >= sizeof buf)
p = malloc(n);
else
p = buf;
...
free(p);
上述程序的本意是在n小于buf的长度时避免分配内存，但即使p指向buf时，上述程序也会错误地调用free。该错误通常也会破坏用于内存管理的数据结构，而且直到以后才能发现。
最后，考虑下述函数：
void itoa(int n, char *buf, int size) {
char *p = malloc(43);
sprintf(p, "%d", n);
if (strlen(p) >= size - 1) {
while (--size > 0)
*buf++ = '*';
*buf = '\0';
} else
strcpy(buf, p);
}
将整数n的十进制字符串表示填充到buf[0..size-1]中，如果该表示需要的字符数目大于size-1，则用星号填充buf。该代码看起来很健壮，但它至少包含两个错误。第一，如果分配内存失败malloc返回NULL指针，该代码没有检测这种情况。第二，该代码产生了一个内存泄漏：它没有释放分配的内存。程序每次调用itoa时，内存会被逐渐消耗。如果经常调用itoa，程序最终将用尽内存并失败。另外，当size小于2时itoa工作正常，但它会将buf[0]设置为零字符。或许更好的设计需要要求size大于等于2，并通过一个已检查的运行时错误来强制实施该约束。
Mem接口中的宏和例程针对上述各种内存管理错误提供了一些保护。但它们不能消除所有这些错误。例如，它们无法防止反引用已破坏的指针或使用指针指向超出作用域的局部变量。C语言初学者经常犯后一个错误，下面给出的一个表面看起来更简单的itoa版本就是一个例子：
char *itoa(int n) {
char buf[43];
sprintf(buf, "%d", n);
return buf;
}
itoa返回其局部数组buf的地址，但在itoa返回后，buf就不再存在了。
Mem接口导出了以下异常、例程和宏：
〈mem.h 〉≡ #ifndef MEM_INCLUDED #define MEM_INCLUDED #include "except.h" 〈exported exceptions 51〉 〈exported functions 51〉 〈exported macros 51〉 #endif
Mem提供的分配函数类似于标准C库，但它们不接受零长度，也不返回NULL指针：
〈exported exceptions 51〉≡ extern const Except_T Mem_Failed; 〈exported functions 51〉≡ extern void *Mem_alloc (long nbytes, const char *file, int line); extern void *Mem_calloc(long count, long nbytes, const char *file, int line);
Mem_alloc分配一块至少为nbytes长的内存，并返回指向其中第一个字节的指针。该内存块对齐到地址边界，能够适合于具有最严格对齐要求的数据。该块的内容是未初始化的。如果nbytes的值不是正数，这就是一个已检查的运行时错误。
Mem_calloc分配一个足够大的的内存块，可以容纳一个包含count个元素的数组，每个数组项的长度为nbytes，并返回指向第一个数组元素的指针。该内存块的对齐与Mem_alloc类似，其内容初始化为0。NULL指针和0.0不一定由0表示，因此Mem_calloc可能不能正确地初始化它们。count或nbytes不是正数，是已检查的运行时错误。
Mem_alloc和Mem_calloc的最后两个参数是函数被调用处的文件名和行号。这些信息由以下宏提供，这是调用这些函数的通常方式。
〈exported macros 51〉≡ #define ALLOC(nbytes ) \ Mem_alloc((nbytes ), __FILE__, __LINE__) #define CALLOC(count, nbytes ) \ Mem_calloc((count ), (nbytes ), __FILE__, __LINE__)
如果Mem_alloc或Mem_calloc无法分配所要的内存，则引发Mem_Failed异常，并将file和line参数传递给Except_raise，这样，抛出的异常就给出了调用相应函数的位置。如果file为NULL指针，mem_alloc和Mem_calloc将提供其实现内部引发Mem_Failed异常的位置。
许多分配操作具有下述形式：
struct T *p; p = Mem_alloc(sizeof (struct T));
即为结构T的一个实例分配内存块，返回指向块的一个指针。该惯用法的一个更好的版本如下：
p = Mem_alloc(sizeof *p);
对void指针以外的任何指针类型，都可以使用sizeof*p代替sizeof(struct T)，sizeof*p的好处在于，这种用法不依赖指针指向的类型。如果*p的类型发生了改变，这种分配方式仍然是正确的，但使用sizeof(struct T)的分配则必须改变，以反映*p类型的变化 [1] 。即
p = Mem_alloc(sizeof (struct T));
仅当p确实是指向struct T实例的指针时，才是正确的。如果p改为指向另一个结构的指针而不更新该调用，那么上述调用有可能分配过多的内存，这会浪费空间，也有可能分配太少的内存，这会造成严重的损失，因为客户程序访问p指向的结构时，可能访问到未分配的内存。
这种内存分配的惯用法是如此之常见，以至于Mem接口提供了宏，将内存分配和赋值封装起来：
〈exported macros 51〉+≡ #define NEW(p ) ((p ) = ALLOC((long)sizeof *(p ))) #define NEW0(p ) ((p ) = CALLOC(1, (long)sizeof *(p )))
NEW(p)分配了一个未初始化的内存块以容纳*p，并将p设置为该块的地址。NEW0(p)完成的工作类似，还将内存块清零。提供NEW时有下述假设：大多数客户程序在分配内存块后会立即初始化。传递给编译时运算符sizeof的参数只用于获取其类型，运行时不会计算其值。因此NEW和NEW0只会计算p一次，使用具有副效应的表达式作为这两个宏的实参是安全的，例如NEW(a[i++])。
malloc和calloc的参数类型为size_t，sizeof得到的常数，其类型也是size_t。size_t类型是一个无符号整数类型（integral type），能够表示可声明的最大对象的大小，在标准库中指定对象大小时都会使用该类型。实际上，size_t或者是unsigned int，或者是unsigned long。mem_alloc和Mem_calloc使用int类型参数，避免将负数传递给无符号参数可能造成的错误。例如，
int n = -1; ... p = malloc(n);
显然是一个错误，但malloc的许多实现不会捕获该错误，因为当-1转换为size_t时，通常是一个非常大的无符号值。
内存通过Mem_free释放：
〈exported functions 51〉+≡ extern void Mem_free(void *ptr, const char *file, int line); 〈exported macros 51〉+≡ #define FREE(ptr ) ((void)(Mem_free((ptr ), \ __FILE__, __LINE__), (ptr ) = 0))
Mem_free需要一个指向被释放内存块的指针作为参数。如果ptr不为NULL指针，那么Mem_free将释放该内存块，如果ptr是NULL指针，Mem_free没有效果。FREE宏也需要一个指向内存块的指针作为参数，它调用Mem_free释放该块，并将ptr设置为NULL指针，如2.4节所述，这样做有助于避免悬挂指针。由于ptr指向的内存被FREE释放后，ptr被设置为NULL指针，此后对ptr进行反引用，通常会导致程序因某种寻址错误而崩溃。这种确定性的错误，比反引用悬挂指针导致的不可预测的行为要好得多。请注意，FREE会多次对ptr求值。
本章提供了两个导出Mem接口的实现，后续各节会详细阐述。“稽核实现”实现了一些已检查的运行时错误，有助于捕获前一节描述的那些内存访问错误。在该实现中，将并非由Mem_alloc、Mem_calloc或Mem_resize返回的非NULL指针ptr传递给Mem_free是一个已检查的运行时错误，将已经传递给Mem_free或Mem_resize的指针ptr再次传递给Mem_free也是已检查的运行时错误。Mem_free的file和line参数的值用于报告这些已检查的运行时错误。
但在“产品实现”中，这些内存访问错误是未检查的运行时错误。
下面的函数
〈exported functions 51〉+≡ extern void *Mem_resize(void *ptr, long nbytes, const char *file, int line); 〈exported macros 51〉+≡ #define RESIZE(ptr, nbytes ) ((ptr ) = Mem_resize((ptr ), \ (nbytes ), __FILE__, __LINE__))
将修改上一次调用Mem_alloc、Mem_calloc或Mem_resize分配的内存块的长度。类似Mem_free，Mem_resize的第一个参数也是一个指针，其中包含了将改变长度的内存块的地址。Mem_resize会扩展或缩减该内存块，使之包含至少nbytes内存，并适当对齐，最后返回一个指向调整大小后的内存块的指针。Mem_resize为改变块的长度可能会移动其位置，如此Mem_resize在逻辑上等价于分配一个新的块，将ptr指向的一部分或全部数据复制到新的内存块，并释放ptr指向的内存块。如果Mem_resize无法分配新内存块，将引发Mem_Failed异常，并将file和line作为异常的“坐标”。宏RESIZE将ptr改为指向新的内存块，这是Mem_resize的一种常见用法。请注意，RESIZE宏会多次对ptr求值。
如果nbytes大于ptr指向的内存块的长度，那么超出部分的字节是未初始化的。否则，ptr开头的nbytes字节会复制到新的内存块。
向Mem_resize传递的ptr指针为NULL，或nbytes不是正值，这些是已检查的运行时错误。在“稽核实现”中，将并非由Mem_alloc、Mem_calloc或Mem_resize返回的非NULL指针Ptr传递给Mem_resize是一个已检查的运行时错误，将已经传递给Mem_free或Mem_resize的指针再次传递给Mem_resize也是已检查的运行时错误。在“产品实现”中，这些内存访问错误都是未检查的运行时错误。
Mem接口中的函数可以与标准C库函数malloc、calloc、realloc和free同时使用。即，一个程序可以使用这两种内存分配函数。“稽核实现”将内存访问错误报告为已检查的运行时错误，这种行为仅适用于该实现管理的内存。任何给定程序中，只能使用Mem接口的一个实现。
在产品实现中，这些例程将对标准库中内存管理函数的调用封装到通过Mem接口规定的更安全的软件包中。
〈mem.c 〉≡ #include <stdlib.h> #include <stddef.h> #include "assert.h" #include "except.h" #include "mem.h" 〈data 54〉 〈functions 54〉
例如，Mem_alloc调用malloc，并在malloc返回NULL指针时引发Mem_Failed异常：
〈functions 54〉≡ void *Mem_alloc(long nbytes, const char *file, int line){ void *ptr; assert(nbytes > 0); ptr = malloc(nbytes); if (ptr == NULL) 〈raise Mem_Failed 54〉 return ptr; } 〈raise Mem_Failed 54〉≡ { if (file == NULL) RAISE(Mem_Failed); else Except_raise(&Mem_Failed, file, line); } 〈data 54〉≡ const Except_T Mem_Failed = { "Allocation Failed" };
如果客户程序不处理Mem_Failed异常，Except_raise将在报告未处理的异常时输出调用者的“坐标”（文件和行号，这些是在调用Mem_alloc时传递进来的）。例如：
Uncaught exception Allocation Failed raised @parse.c:431 aborting...
同样，Mem_calloc将对calloc的调用封装了进来
〈functions 54〉+≡ void *Mem_calloc(long count, long nbytes, const char *file, int line) { void *ptr; assert(count > 0); assert(nbytes > 0); ptr = calloc(count, nbytes); if (ptr == NULL) 〈raise Mem_Failed 54〉 return ptr; }
在count或nbytes为零时，calloc的行为是由具体实现定义的。在这种情况下Mem接口规定了函数的行为，这也是它的优点之一，且有助于避免bug。
Mem_free只是调用free：
〈functions
54〉+≡
void Mem_free(void *ptr, const char *file, int line) {
if (ptr)
free(ptr);
}
C语言标准允许将NULL指针传递给free，Mem_free不会传递NULL指针，因为free的比较旧的实现可能不接受NULL指针。
Mem_resize的规格说明比realloc简单得多，这也反映在它的更简单的实现中：
〈functions 54〉+≡ void *Mem_resize(void *ptr, long nbytes, const char *file, int line) { assert(ptr); assert(nbytes > 0); ptr = realloc(ptr, nbytes); if (ptr == NULL) 〈raise Mem_Failed 54〉 return ptr; }
Mem_resize唯一的目的就是改变某个现存内存块的长度。realloc也完成了同样的工作，但它在nbytes为零时会释放内存块，而在ptr是NULL指针时会分配内存块。这些额外的功能与修改现存内存块的长度只有松散的关联，很容易引入bug。
Mem接口的稽核实现导出的各个函数，会捕获本章开头描述的各种内存访问错误，并将其作为已检查的运行时错误报告。
〈memchk.c 〉≡ #include <stdlib.h> #include <string.h> #include "assert.h" #include "except.h" #include "mem.h" 〈checking types 58〉 〈checking macros 58〉 〈data 54〉 〈checking data 56〉 〈checking functions 58〉
如果Mem_alloc、Mem_calloc和Mem_resize从来不把同一地址返回两次，且能够记录所有返回的地址以及哪些地址指向已分配的内存，那么Mem_free和Mem_resize就可以检测内存访问错误。抽象地说，这些函数维护了一个集合S，其元素为对（α, free ）或（α, allocated ），其中α 是某次分配返回的内存地址。值free 表示地址α 不指向已分配的内存，即，该内存已经显式释放，值allocated 表示α 指向已分配的内存。
Mem_alloc和Mem_calloc会添加对（ptr, allocated ）到集合S，其中ptr是这两个函数的返回值，在添加之前，二者保证（ptr, allocated ）和（ptr, free ）都不在S中。当ptr为NULL指针或（ptr, allocated ）在S 中，Mem_free(ptr)是合法的。如果ptr非空且（ptr, allocated ）在S 中，Mem_free将释放ptr指向的内存块，并将S 中的对应项改为（ptr, free ）。类似地，仅当（ptr, allocated ）在S中时，Mem_resize(ptr, nbytes, ...)才是合法的。倘若如此，Mem_resize会调用Mem_alloc分配一个新块，并将旧内存块的内容复制到新块，并调用Mem_free释放旧块，这些调用会对集合S 的内容进行适当的修改。
分配函数从来不返回同一地址两次的条件，可以通过从不释放任何内存块来实现。这种方法会浪费空间，而且很容易实现更好的方法：即从不释放由分配函数返回的内存块 [2] 。通过维护一个保存这种内存块地址的表，即可实现集合S。
这种方案的内存分配器，可以基于标准库函数实现。该分配器维护了块描述符的一个哈希表：
〈checking data
56〉≡
static struct descriptor {
struct descriptor *free;
struct descriptor *link;
const void *ptr;
long size;
const char *file;
int line;
} *htab[2048];
ptr是块的地址，在代码中其他地方分配（在下文讲述），size是块的长度。file和line是该块的分配“坐标”，即客户程序中调用相关分配函数的源代码所处的位置（也会作为参数传递给分配函数）。这些值并不使用，但会保存在描述符中，以便调试器在调试会话期间输出相关信息。
link字段构建了一个块描述符的链表，这些块散列到htab中的同一索引，htab本身是一个描述符指针的数组。这些描述符还形成了一个空闲块链表，该链表的头是空描述符
〈checking data
56〉+≡
static struct descriptor freelist = { &freelist };
该链表通过描述符的free字段建立。该链表是环形的：freelist是链表中最后一个描述符，其free字段指向链表中第一个描述符。在任一给定时刻，htab包含了所有块的描述符，包括空闲块和已分配块，同时空闲块还出现在freelist链表上。如果描述符的free字段为NULL，则该块已经分配，如果free字段不是NULL，则该块是空闲的，因而htab就实现了集合S。图5-1给出了这些数据结构在某个时间点上的快照。与每个描述符结构关联的内存块，在图中表示描述符之后的方框。阴影方框表示已分配的空间，空白的方框表示空闲空间，实线表示link字段建立的链表，而虚线表示空闲链表。
图5-1 htab和freelist结构
给出一个地址，find将搜索其描述符。该函数返回指向描述符的指针或者NULL指针：
〈checking functions 58〉≡ static struct descriptor *find(const void *ptr) { struct descriptor *bp = htab[hash(ptr, htab)]; while (bp && bp->ptr != ptr) bp = bp->link; return bp; } 〈checking macros 58〉≡ #define hash(p, t) (((unsigned long)(p)>>3) & \ (sizeof (t)/sizeof ((t)[0])-1))
hash宏将地址作为一个位模式处理，右移三位，并将其对htab的大小取模，以减小其值。给出find之后，就完全可以写出一个Mem_free版本，将内存访问错误实现为已检查的运行时错误：
〈checking functions 58〉+≡ void Mem_free(void *ptr, const char *file, int line) { if (ptr) { struct descriptor *bp; 〈set bp if ptr is valid 58〉 bp->free = freelist.free; freelist.free = bp; } }
如果ptr不是NULL，而且是一个有效地址，会将对应的内存块添加到空闲链表而释放该块，这样的空闲块可能由后续的Mem_alloc调用来重用。如果指针指向已分配内存块，那么就是有效的：
〈set bp if ptr is valid 58〉≡ if (((unsigned long)ptr)%(sizeof (union align)) != 0 || (bp = find(ptr)) == NULL || bp->free) Except_raise(&Assert_Failed, file, line);
if语句中对((unsigned long)ptr) % (sizeof(union align)) != 0的检查过滤掉了那些不是严格对齐值倍数的地址，这样的地址不可能是有效的块指针。
如下所示，Mem_alloc返回的指针，地址值总是对齐到下列联合的大小倍数。
〈checking types
58〉≡
union align {
int i;
long l;
long *lp;
void *p;
void (*fp)(void);
float f;
double d;
long double ld;
};
这种对齐确保了任何类型的数据都可以保存在Mem_alloc返回的块中。如果传递给Mem_free的ptr不符合这种对齐，它不可能在htab中，因而是无效的。
Mem_resize通过同样的检查来捕获内存访问错误，然后调用Mem_free、Mem_alloc和库函数memcpy：
〈checking functions 58〉+≡ void *Mem_resize(void *ptr, long nbytes, const char *file, int line) { struct descriptor *bp; void *newptr; assert(ptr); assert(nbytes > 0); 〈set bp if ptr is valid 58〉 newptr = Mem_alloc(nbytes, file, line); memcpy(newptr, ptr, nbytes < bp->size ? nbytes : bp->size); Mem_free(ptr, file, line); return newptr; }
类似地，Mem_calloc可以通过调用Mem_alloc和库函数memset来实现：
〈checking functions
58〉+≡
void *Mem_calloc(long count, long nbytes,
const char *file, int line) {
void *ptr;
assert(count > 0);
assert(nbytes > 0);
ptr = Mem_alloc(count*nbytes, file, line);
memset(ptr, '\0', count*nbytes);
return ptr;
}
剩下的工作只是对描述符以及Mem_alloc的代码的分配。同时完成这两个任务的一种方法是，分配一个足够大的块，可以容纳一个描述符以及调用Mem_alloc所请求的内存空间。这种方法有两个缺点。第一，它使划分一块空闲内存以满足几个较小请求的工作复杂化，因为每个请求都需要自身的描述符。第二，它使描述符易受破坏，当通过指针或索引写内存越界时，就会发生这种情况。
独立分配描述符，解除了描述符分配与Mem_alloc进行的内存分配之间的耦合，并减少了（但不会消除）描述符被破坏的可能性。dalloc会分配、初始化并返回一个描述符，这来自由malloc分配的包含512个描述符的内存块：
〈checking functions 58〉+≡ static struct descriptor *dalloc(void *ptr, long size, const char *file, int line) { static struct descriptor *avail; static int nleft; if (nleft <= 0) { 〈allocate descriptors 60〉 nleft = NDESCRIPTORS; } avail->ptr = ptr; avail->size = size; avail->file = file; avail->line = line; avail->free = avail->link = NULL; nleft--; return avail++; } 〈checking macros 58〉+≡ #define NDESCRIPTORS 512
对malloc的调用可能返回NULL指针，这种情况下，dalloc将NULL返回给调用者。
〈allocate descriptors
60〉≡
avail = malloc(NDESCRIPTORS*sizeof (*avail));
if (avail == NULL)
return NULL;
如下所示，Mem_alloc在dalloc返回NULL指针时引发Mem_Failed异常。
Mem_alloc使用最先适配算法分配内存，这是诸多内存分配算法之一。它会搜索freelist来查找第一个能够满足请求的足够大的空闲块，并划分该块来满足请求。如果freelist不包含适当的块，Mem_alloc调用malloc分配比nbytes大的一个内存块，将该块添加到空闲链表，然后再次尝试。因为新的内存块比nbytes大，这一次将使用该块来满足请求。这里是代码：
〈checking functions 58〉+≡ void *Mem_alloc(long nbytes, const char *file, int line){ struct descriptor *bp; void *ptr; assert(nbytes > 0); 〈round nbytes up to an alignment boundary 61〉 for (bp = freelist.free; bp; bp = bp->free) { if (bp->size > nbytes) { 〈use the end of the block at bp->ptr 61〉 } if (bp == &freelist) { struct descriptor *newptr; 〈newptr ← a block of size NALLOC + nbytes 62〉 newptr->free = freelist.free; freelist.free = newptr; } } assert(0); return NULL; }
Mem_alloc首先将nbytes向上舍入，使得其返回的每个指针都对齐到联合align大小的倍数：
〈round nbytes up to an alignment boundary 61〉≡ nbytes = ((nbytes + sizeof (union align) - 1)/ (sizeof (union align)))*(sizeof (union align));
freelist.free指向空闲链表的起始，for循环从这里开始。第一个大小大于nbytes的空闲块用来满足该请求。该空闲块末端nbytes长的空间被切分为一个新块，在创建其描述符、初始化并添加到htab后，返回该内存块地址：
〈use the end of the block at bp->ptr 61〉≡ bp->size -= nbytes; ptr = (char *)bp->ptr + bp->size; if ((bp = dalloc(ptr, nbytes, file, line)) != NULL) { unsigned h = hash(ptr, htab); bp->link = htab[h]; htab[h] = bp; return ptr; } else 〈raise Mem_Failed 54〉
图5-2说明了该代码块的效果：左侧是一个描述符，指向划分前的一些空闲空间。在右侧，已经分配的空间用阴影标识，有一个新的描述符指向该内存块。请注意，新描述符的空闲链表链接为NULL [3] 。
图5-2 分配空闲块的尾部
对bp->size > nbytes的检查保证了bp->ptr永远不会重用。大的空闲块被划分来满足较小的请求，直至其长度减少到sizeof(union align)字节，此后bp->size决不会大于nbytes。每个内存块中前sizeof(union align)字节决不会分配。
在循环时，如果bp到达freelist，说明该链表不包含长度大于nbytes的内存块。在这种情况下，需要分配一个新的内存块，其长度为
〈checking macros
58〉+≡
#define NALLOC ((4096 + sizeof (union align) - 1)/ \
(sizeof (union align)))*(sizeof (union align))
加上nbytes，该块将添加到空闲链表的起始处，在for循环的下一次迭代中，将使用该空闲块来满足分配请求。新块有一个描述符，就像是该块此前已分配并被释放一样：
〈newptr ← a block of size NALLOC + nbytes 62〉≡ if ((ptr = malloc(nbytes + NALLOC)) == NULL || (newptr = dalloc(ptr, nbytes + NALLOC, __FILE__, __LINE__)) == NULL) 〈raise Mem_Failed 54〉
Mem接口的目的之一是改进标准C分配函数的接口。[Maguire，1993]一书批评了这些函数并描述了一个类似的重新封装接口。
在C程序中内存分配bug是如此普遍，以至于有些公司专门构建并销售有助于诊断和修复此类bug的工具。其中最好的之一是Purify [Hastings and Joyce，1992]，该工具能够检测几乎所有种类的内存访问错误，包括5.3节描述的那些。Purify会检查每个load和store指令，因为它是通过编辑目标码来完成其工作的，所以即使当源代码不可用时也可以使用该工具，如私有的库。通过修改源代码来捕获内存访问错误，是另一种大不相同的实现技术，例如，[Austin, Breach and Sohi，1994]一文描述了一种系统，其中的“安全”指针承载了足够的信息，可以捕获大量内存访问错误。LCLint [Evans，1996]有许多类似PC-Lint之类工具的特性，可以在编译时检测许多潜在的内存分配错误。
[Knuth，1973a]一书综述了所有重要的内存分配算法，并解释了最先适配通常优于其他方法（例如最佳适配，该方法寻找长度最接近请求的空闲块）的原因。Mem_alloc中使用的最先适配算法与[Kernighan and Ritchie，1988]书中8.7节描述的算法类似。
对于大多数内存管理算法来说，都有大量变体，通常用来针对特定应用或分配模式改进性能。快速适配（quick fit，参见[Weinstock and Wulf，1988]）是使用最广泛的变体之一。许多应用程序分配的内存块中，仅有少量不同长度，快速适配利用了这一事实。快速适配维护N个空闲链表，每个链表用于一种最常请求的块长。在分配其中某种长度的内存块时，只需从对应的链表上移除第一块，而释放内存块时，将其添加到对应的链表即可。在链表为空或请求的长度链表不支持时，会使用一种备用算法，如最先适配。
[Grunwald and Zorn，1993]描述了一个系统，能够针对某种特定应用的使用模式，生成调优过的malloc和free实现。该系统首先用能够收集统计数据的malloc和free版本来运行应用程序，收集的统计数据包括块长、分配与释放的相对频繁程度等。接下来，系统将收集的数据输入到一个程序中，程序将生成针对该应用程序定制的malloc和free版本的源代码。这种定制版本通常使用快速适配，支持少量特定于该应用程序的块长。
5.1 [Maguire，1993]提倡将未初始化的内存初始化为某种独特的位模式，以帮助诊断访问未初始化内存造成的bug。一种好的位模式需要具备什么样的特性？请提出一种适当的位模式，并修改Mem_alloc的稽核实现，使之使用该位模式。设法找到一种应用程序，使得这种修改能够捕获到一个bug。
5.2 在代码块〈use the end of the block at bp->ptr 61〉中，当一个空闲块的长度减小到sizeof(union align)字节后，它就无法满足分配请求了，但仍然会留在空闲链表中。修改代码以删除这种内存块。你能找到这样的应用程序，使得通过测量能够检测到这种改进对该程序的效果吗？
5.3 最先适配的大多数实现（如[Kernighan and Ritchie，1988]的8.7节中给出的）都会合并相邻的空闲块，以形成更大的空闲块。Mem_alloc的稽核实现无法合并相邻的空闲块，因为它不能将同一地址返回两次。为Mem_alloc设计一个算法，使之既可以合并相邻的空闲块，又无需返回同一地址两次。
5.4 一些程序员可能主张，在Mem_free中针对内存访问错误引发Assert_Failure异常属于过度反应，因为只要将错误的调用记入日志并忽略，执行可以继续。请实现
extern void Mem_log(FILE *log);
如果向Mem_log传递的FILE指针不是NULL，则可以通过向log写入消息的方式来通知内存访问错误，而不再引发Assert_Failure异常。这些消息可以记录错误调用和分配操作的“坐标”。例如，如果在调用Mem_free时传递的指针指向一个已经释放的内存块，可能会输出下列消息：
** freeing free memory Mem_free(0x6418) called from parse.c:461 This block is 48 bytes long and was allocated from sym.c:123
类似地，如果在调用Mem_resize时传递的指针无效，可能会报告：
** resizing unallocated memory Mem_resize(0xf7fff930,640) called from types.c:1101
Mem_log(NULL)可关闭日志，恢复使内存访问错误引发断言失败的行为。
5.5 稽核实现拥有报告潜在内存泄漏所需的所有信息。如本章章首所述，内存泄漏是不再被任何指针引用的已分配内存块，因而无法释放。泄漏会导致程序最终用尽内存。对只是短时间运行的程序来说，内存泄漏不是问题，但对于需要长时间运行的程序来说（如用户界面和服务器），这是个严重的问题。请实现
extern void Mem_leak(apply(void *ptr, long size,
const char *file, int line, void *cl), void *cl);
该函数对每个已分配内存块调用apply指向的函数，ptr是内存块的地址，size是块的分配长度，file和line是其分配坐标。客户程序可以向Mem_leak传递一个特定于应用程序的指针cl，该指针顺次传递给apply，用作最后一个参数。Mem_leak不知道cl的用途，但apply很可能知道。apply和cl合称一个闭包（closure）：它们规定了一个操作和一些用于该操作的上下文相关数据。例如，
void inuse(void *ptr, long size,
const char *file, int line, void *cl) {
FILE *log = cl;
fprintf(log, "** memory in use at %p\n", ptr);
fprintf(log, "This block is %ld bytes long "
"and was allocated from %s:%d\n", size,
file, line);
}
会输出如下消息：
** memory in use at 0x13428 This block is 32 bytes long and was allocated from gen.c:23
到前一习题所述的日志文件。调用inuse时，将其和日志文件的FILE指针一同传递给Mem_leak即可：
Mem_leak(inuse, log);
[1] 这里实际上改变的是*p的类型，不是p的类型。——译者注
[2] 这貌似和前一种方法没有本质的差别，因为一般来说前一种方法也会释放直接用malloc/new返回的内存块。——译者注
[3] 即free字段。——译者注