这是Kernighan和Ritchie关于C的书的摘录。它显示了如何实现malloc的版本。虽然评论很好，但我很难理解它。有人可以解释一下吗？
typedef long Align; /* for alignment to long boundary */
union header { /* block header */
struct {
union header *ptr; /* next block if on free list */
unsigned size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
};
typedef union header Header;
static Header base; /* empty list to get started */
static Header *freep = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void *malloc(unsigned nbytes)
{
Header *p, *prevp;
Header *morecore(unsigned);
unsigned nunits;
nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;
if ((prevp = freep) == NULL) { /* no free list yet */
base.s.ptr = freeptr = prevptr = &base;
base.s.size = 0;
}
for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
if (p->s.size >= nunits) { /* big enough */
if (p->s.size == nunits) /* exactly */
prevp->s.ptr = p->s.ptr;
else { /* allocate tail end */
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits
}
freep = prevp;
return (void *)(p+1);
}
if (p == freep) /* wrapped around free list */
if ((p = morecore(nunits)) == NULL)
return NULL; /* none left */
}
}
#define NALLOC 1024 /* minimum #units to request */
/* morecore: ask system for more memory */
static Header *morecore(unsigned nu)
{
char *cp, *sbrk(int);
Header *up;
if (nu < NALLOC)
nu = NALLOC;
cp = sbrk(nu * sizeof(Header));
if (cp == (char *) -1) /* no space at all */
return NULL;
up = (Header *) cp;
up->s.size = nu;
free((void *)(up+1));
return freep;
}
/* free: put block ap in free list */
void free(void *ap) {
Header *bp, *p;
bp = (Header *)ap - 1; /* point to block header */
for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
break; /* freed block at start or end of arena */
if (bp + bp->size == p->s.ptr) {
bp->s.size += p->s.ptr->s.size;
bp->s.ptr = p->s.ptr->s.ptr;
} else
bp->s.ptr = p->s.ptr;
if (p + p->size == bp) {
p->s.size += bp->s.size;
p->s.ptr = bp->s.ptr;
} else
p->s.ptr = bp;
freep = p;
}
好吧，我们这里有一大堆写得很糟糕的代码。我将在这篇文章中做的最好被描述为软件考古学。
第1步：修复格式。
压痕和紧凑格式对任何人都没有好处。需要插入各种空格和空行。评论可以用更可读的方式编写。我将首先解决这个问题。
与此同时，我正在改变K＆R风格的支架式 - 请注意K＆R支架式是可以接受的，这仅仅是我个人的偏好。另一个个人偏好是在指向的类型旁边写指针。我不会在这里争论（主观）风格问题。
此外，Header的类型定义是完全不可读的，它需要一个彻底的修复。
我发现了一些完全模糊不清的东西：它们似乎在函数内声明了一个函数原型。 Header* morecore(unsigned);。这是非常古老而且非常糟糕的风格，我不确定C是否会再允许它。让我们删除该行，无论该函数做什么，都必须在别处定义。
typedef long Align; /* for alignment to long boundary */
typedef union header /* block header */
{
struct
{
union header *ptr; /* next block if on free list */
unsigned size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
} Header;
static Header base; /* empty list to get started */
static Header* freep = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void* malloc (unsigned nbytes)
{
Header* p;
Header* prevp;
unsigned nunits;
nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1;
if ((prevp = freep) == NULL) /* no free list yet */
{
base.s.ptr = freeptr = prevptr = &base;
base.s.size = 0;
}
for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr)
{
if (p->s.size >= nunits) /* big enough */
{
if (p->s.size == nunits) /* exactly */
prevp->s.ptr = p->s.ptr;
else /* allocate tail end */
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits
}
freep = prevp;
return (void *)(p+1);
}
if (p == freep) /* wrapped around free list */
if ((p = morecore(nunits)) == NULL)
return NULL; /* none left */
}
}
好的，现在我们实际上可以读取代码了。
第二步：清除广泛认可的不良做法。
这段代码充满了现在被认为是不好的做法。它们需要被删除，因为它们会危害代码的安全性，可读性和维护性。如果您想要提及与我一样宣传相同做法的权威，请查看广泛认可的编码标准MISRA-C。
我发现并删除了以下不良做法：
1）在代码中输入unsigned可能会导致混淆：这是程序员的错字还是打算写unsigned int？我们应该用unsigned替换所有unsigned int。但是当我们这样做时，我们发现它在这个上下文中用于给出各种二进制数据的大小。正确的类型是C标准型size_t。这基本上只是一个unsigned int，但它保证对于特定平台来说“足够大”。 sizeof运算符返回size_t类型的结果，如果我们看一下C标准对真正malloc的定义，那就是void *malloc(size_t size);。所以size_t是最正确的类型。
2）对于我们自己的malloc函数使用与stdlib.h中相同的名称是一个坏主意。如果我们需要包含stdlib.h，事情会变得混乱。根据经验，永远不要在自己的代码中使用C标准库函数的标识符名称。我将名称更改为kr_malloc。
3）代码滥用了所有静态变量保证初始化为零的事实。这是由C标准明确定义的，但却是一个相当微妙的规则。让我们明确初始化所有静态，以表明我们没有忘记偶然启动它们。
4）内部条件的分配是危险的，难以阅读。如果可能，应该避免这种情况，因为它也可能导致错误，例如classic = vs == bug。
5）由于评估的顺序，同一行上的多个分配难以阅读，也可能是危险的。
6）同一行上的多个声明很难阅读，也很危险，因为混合数据和指针声明时可能会导致错误。始终在每行上声明每个变量。
7）每次声明后都要使用大括号。不这样做会导致bug错误。
8）永远不要将特定指针类型的强制类型转换为void *。它在C中是不必要的，并且可以隐藏编译器本来会检测到的错误。
9）避免在函数内使用多个return语句。有时他们会导致更清晰的代码，但在大多数情况下，他们会导致意大利面。正如代码所代表的那样，我们不能在不重写循环的情况下改变它，所以我稍后会修复它。
10）保持循环简单。它们应该包含一个init语句，一个循环条件和一个迭代，没有别的。这个for循环，使用逗号运算符和所有内容，非常模糊。同样，我们发现需要将此循环重写为理智的东西。我接下来会这样做，但现在我们有：
typedef long Align; /* for alignment to long boundary */
typedef union header /* block header */
{
struct
{
union header *ptr; /* next block if on free list */
size_t size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
} Header;
static Header base = {0}; /* empty list to get started */
static Header* freep = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
Header* p;
Header* prevp;
size_t nunits;
nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1;
prevp = freep;
if (prevp == NULL) /* no free list yet */
{
base.s.ptr = &base;
freeptr = &base;
prevptr = &base;
base.s.size = 0;
}
for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr)
{
if (p->s.size >= nunits) /* big enough */
{
if (p->s.size == nunits) /* exactly */
{
prevp->s.ptr = p->s.ptr;
}
else /* allocate tail end */
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits
}
freep = prevp;
return p+1;
}
if (p == freep) /* wrapped around free list */
{
p = morecore(nunits);
if (p == NULL)
{
return NULL; /* none left */
}
}
} /* for */
}
第3步：重写模糊循环。
由于前面提到的原因。我们可以看到这个循环永远持续，它通过从函数返回来终止，无论是在分配完成时，还是在没有内存的情况下。因此，我们将其创建为循环条件，然后将返回到函数末尾的位置。让我们摆脱那个丑陋的逗号运算符。
我将介绍两个新变量：一个用于保存结果指针的结果变量，另一个用于跟踪循环是否应该继续。我将通过使用bool类型来吹嘘K＆R的思想，这是自1999年以来C语言的一部分。
（我希望我没有用这个改变改变算法，我相信我没有）
#include <stdbool.h>
typedef long Align; /* for alignment to long boundary */
typedef union header /* block header */
{
struct
{
union header *ptr; /* next block if on free list */
size_t size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
} Header;
static Header base = {0}; /* empty list to get started */
static Header* freep = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
Header* p;
Header* prevp;
size_t nunits;
void* result;
bool is_allocating;
nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1;
prevp = freep;
if (prevp == NULL) /* no free list yet */
{
base.s.ptr = &base;
freeptr = &base;
prevptr = &base;
base.s.size = 0;
}
is_allocating = true;
for (p = prevp->s.ptr; is_allocating; p = p->s.ptr)
{
if (p->s.size >= nunits) /* big enough */
{
if (p->s.size == nunits) /* exactly */
{
prevp->s.ptr = p->s.ptr;
}
else /* allocate tail end */
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits
}
freep = prevp;
result = p+1;
is_allocating = false; /* we are done */
}
if (p == freep) /* wrapped around free list */
{
p = morecore(nunits);
if (p == NULL)
{
result = NULL; /* none left */
is_allocating = false;
}
}
prevp = p;
} /* for */
return result;
}
第4步：编译这个垃圾。
由于这是来自K＆R，它充满了拼写错误。 sizeof(header)应该是sizeof(Header)。缺少分号。他们使用不同的名称freep，prevp与freeptr，prevptr，但显然意味着相同的变量。我相信后者实际上是更好的名字，所以让我们使用它们。
#include <stdbool.h>
typedef long Align; /* for alignment to long boundary */
typedef union header /* block header */
{
struct
{
union header *ptr; /* next block if on free list */
size_t size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
} Header;
static Header base = {0}; /* empty list to get started */
static Header* freeptr = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
Header* p;
Header* prevptr;
size_t nunits;
void* result;
bool is_allocating;
nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
prevptr = freeptr;
if (prevptr == NULL) /* no free list yet */
{
base.s.ptr = &base;
freeptr = &base;
prevptr = &base;
base.s.size = 0;
}
is_allocating = true;
for (p = prevptr->s.ptr; is_allocating; p = p->s.ptr)
{
if (p->s.size >= nunits) /* big enough */
{
if (p->s.size == nunits) /* exactly */
{
prevptr->s.ptr = p->s.ptr;
}
else /* allocate tail end */
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits;
}
freeptr = prevptr;
result = p+1;
is_allocating = false; /* we are done */
}
if (p == freeptr) /* wrapped around free list */
{
p = morecore(nunits);
if (p == NULL)
{
result = NULL; /* none left */
is_allocating = false;
}
}
prevptr = p;
} /* for */
return result;
}
现在我们有一些可读的，可维护的代码，没有很多危险的做法，甚至可以编译！所以现在我们真的可以开始思考代码实际上在做什么了。
正如您可能已经猜到的那样，结构“标题”是链接列表中节点的声明。每个这样的节点都包含指向下一个节点的指针。我不太了解morecore函数，也没有“环绕”，我从来没有使用过这个函数，也没有使用sbrk。但我假设它分配了这个结构中指定的头，以及该头后面的一些原始数据块。如果是这样，那就解释了为什么没有实际的数据指针：假设数据在内存中相邻的标题之后。因此，对于每个节点，我们得到标头，然后我们在标头后面获得一大块原始数据。
迭代本身非常简单，它们通过单链表，一次一个节点。
在循环结束时，他们将指针设置为超过“块”结尾的第一点，然后将其存储在静态变量中，以便程序在下次调用函数时记住先前分配内存的位置。
他们正在使用一种技巧使其标题最终位于对齐的内存地址上：它们将所有开销信息存储在一个联合中，并且变量足够大，以对应平台的对齐要求。因此，如果“ptr”的大小加上“size”的大小太小而无法给出精确对齐，则union保证至少分配sizeof（Align）字节。我相信今天整个技巧已经过时，因为C标准要求自动结构/联合填充。
我正在研究K＆R，因为我想到OP在他问这个问题的时候，我来到这里是因为我也发现这些实现令人困惑。虽然接受的答案非常详细和有用，但我试图采用不同的方法来理解最初编写的代码 - 我已经完成了代码并在代码的部分添加了注释，这对我来说很难。这包括该部分中其他例程的代码（函数free和memcore - 我已将它们重命名为kandr_malloc和kandr_free以避免与stdlib冲突）。我想我会把它留在这里作为接受答案的补充，对于其他可能觉得有用的学生。
我承认此代码中的注释过多。请知道我只是在做这个学习练习，我并不是说这是实际编写代码的好方法。
我冒昧地将一些变量名称改为对我来说更直观的变量名称;除此之外，代码基本上保持不变。它似乎编译并运行我使用的测试程序，虽然valgrind有一些应用程序的投诉。
另外：评论中的一些文字是直接从K＆R或手册页中提取的 - 我不打算对这些部分给予任何信任。
#include <unistd.h> // sbrk
#define NALLOC 1024 // Number of block sizes to allocate on call to sbrk
#ifdef NULL
#undef NULL
#endif
#define NULL 0
// long is chosen as an instance of the most restrictive alignment type
typedef long Align;
/* Construct Header data structure. To ensure that the storage returned by
* kandr_malloc is aligned properly for the objects that are stored in it, all
* blocks are multiples of the header size, and the header itself is aligned
* properly. This is achieved through the use of a union; this data type is big
* enough to hold the "widest" member, and the alignment is appropriate for all
* of the types in the union. Thus by including a member of type Align, which
* is an instance of the most restrictive type, we guarantee that the size of
* Header is aligned to the worst-case boundary. The Align field is never used;
* it just forces each header to the desired alignment.
*/
union header {
struct {
union header *next;
unsigned size;
} s;
Align x;
};
typedef union header Header;
static Header base; // Used to get an initial member for free list
static Header *freep = NULL; // Free list starting point
static Header *morecore(unsigned nblocks);
void kandr_free(void *ptr);
void *kandr_malloc(unsigned nbytes) {
Header *currp;
Header *prevp;
unsigned nunits;
/* Calculate the number of memory units needed to provide at least nbytes of
* memory.
*
* Suppose that we need n >= 0 bytes and that the memory unit sizes are b > 0
* bytes. Then n / b (using integer division) yields one less than the number
* of units needed to provide n bytes of memory, except in the case that n is
* a multiple of b; then it provides exactly the number of units needed. It
* can be verified that (n - 1) / b provides one less than the number of units
* needed to provide n bytes of memory for all values of n > 0. Thus ((n - 1)
* / b) + 1 provides exactly the number of units needed for n > 0.
*
* The extra sizeof(Header) in the numerator is to include the unit of memory
* needed for the header itself.
*/
nunits = ((nbytes + sizeof(Header) - 1) / sizeof(Header)) + 1;
// case: no free list yet exists; we have to initialize.
if (freep == NULL) {
// Create degenerate free list; base points to itself and has size 0
base.s.next = &base;
base.s.size = 0;
// Set free list starting point to base address
freep = &base;
}
/* Initialize pointers to two consecutive blocks in the free list, which we
* call prevp (the previous block) and currp (the current block)
*/
prevp = freep;
currp = prevp->s.next;
/* Step through the free list looking for a block of memory large enough to
* fit nunits units of memory into. If the whole list is traversed without
* finding such a block, then morecore is called to request more memory from
* the OS.
*/
for (; ; prevp = currp, currp = currp->s.next) {
/* case: found a block of memory in free list large enough to fit nunits
* units of memory into. Partition block if necessary, remove it from the
* free list, and return the address of the block (after moving past the
* header).
*/
if (currp->s.size >= nunits) {
/* case: block is exactly the right size; remove the block from the free
* list by pointing the previous block to the next block.
*/
if (currp->s.size == nunits) {
/* Note that this line wouldn't work as intended if we were down to only
* 1 block. However, we would never make it here in that scenario
* because the block at &base has size 0 and thus the conditional will
* fail (note that nunits is always >= 1). It is true that if the block
* at &base had combined with another block, then previous statement
* wouldn't apply - but presumably since base is a global variable and
* future blocks are allocated on the heap, we can be sure that they
* won't border each other.
*/
prevp->s.next = currp->s.next;
}
/* case: block is larger than the amount of memory asked for; allocate
* tail end of the block to the user.
*/
else {
// Changes the memory stored at currp to reflect the reduced block size
currp->s.size -= nunits;
// Find location at which to create the block header for the new block
currp += currp->s.size;
// Store the block size in the new header
currp->s.size = nunits;
}
/* Set global starting position to the previous pointer. Next call to
* malloc will start either at the remaining part of the partitioned block
* if a partition occurred, or at the block after the selected block if
* not.
*/
freep = prevp;
/* Return the location of the start of the memory, i.e. after adding one
* so as to move past the header
*/
return (void *) (currp + 1);
} // end found a block of memory in free list case
/* case: we've wrapped around the free list without finding a block large
* enough to fit nunits units of memory into. Call morecore to request that
* at least nunits units of memory are allocated.
*/
if (currp == freep) {
/* morecore returns freep; the reason that we have to assign currp to it
* again (since we just tested that they are equal), is that there is a
* call to free inside of morecore that can potentially change the value
* of freep. Thus we reassign it so that we can be assured that the newly
* added block is found before (currp == freep) again.
*/
if ((currp = morecore(nunits)) == NULL) {
return NULL;
}
} // end wrapped around free list case
} // end step through free list looking for memory loop
}
static Header *morecore(unsigned nunits) {
void *freemem; // The address of the newly created memory
Header *insertp; // Header ptr for integer arithmatic and constructing header
/* Obtaining memory from OS is a comparatively expensive operation, so obtain
* at least NALLOC blocks of memory and partition as needed
*/
if (nunits < NALLOC) {
nunits = NALLOC;
}
/* Request that the OS increment the program's data space. sbrk changes the
* location of the program break, which defines the end of the process's data
* segment (i.e., the program break is the first location after the end of the
* uninitialized data segment). Increasing the program break has the effect
* of allocating memory to the process. On success, brk returns the previous
* break - so if the break was increased, then this value is a pointer to the
* start of the newly allocated memory.
*/
freemem = sbrk(nunits * sizeof(Header));
// case: unable to allocate more memory; sbrk returns (void *) -1 on error
if (freemem == (void *) -1) {
return NULL;
}
// Construct new block
insertp = (Header *) freemem;
insertp->s.size = nunits;
/* Insert block into the free list so that it is available for malloc. Note
* that we add 1 to the address, effectively moving to the first position
* after the header data, since of course we want the block header to be
* transparent for the user's interactions with malloc and free.
*/
kandr_free((void *) (insertp + 1));
/* Returns the start of the free list; recall that freep has been set to the
* block immediately preceeding the newly allocated memory (by free). Thus by
* returning this value the calling function can immediately find the new
* memory by following the pointer to the next block.
*/
return freep;
}
void kandr_free(void *ptr) {
Header *insertp, *currp;
// Find address of block header for the data to be inserted
insertp = ((Header *) ptr) - 1;
/* Step through the free list looking for the position in the list to place
* the insertion block. In the typical circumstances this would be the block
* immediately to the left of the insertion block; this is checked for by
* finding a block that is to the left of the insertion block and such that
* the following block in the list is to the right of the insertion block.
* However this check doesn't check for one such case, and misses another. We
* still have to check for the cases where either the insertion block is
* either to the left of every other block owned by malloc (the case that is
* missed), or to the right of every block owned by malloc (the case not
* checked for). These last two cases are what is checked for by the
* condition inside of the body of the loop.
*/
for (currp = freep; !((currp < insertp) && (insertp < currp->s.next)); currp = currp->s.next) {
/* currp >= currp->s.ptr implies that the current block is the rightmost
* block in the free list. Then if the insertion block is to the right of
* that block, then it is the new rightmost block; conversely if it is to
* the left of the block that currp points to (which is the current leftmost
* block), then the insertion block is the new leftmost block. Note that
* this conditional handles the case where we only have 1 block in the free
* list (this case is the reason that we need >= in the first test rather
* than just >).
*/
if ((currp >= currp->s.next) && ((currp < insertp) || (insertp < currp->s.next))) {
break;
}
}
/* Having found the correct location in the free list to place the insertion
* block, now we have to (i) link it to the next block, and (ii) link the
* previous block to it. These are the tasks of the next two if/else pairs.
*/
/* case: the end of the insertion block is adjacent to the beginning of
* another block of data owned by malloc. Absorb the block on the right into
* the block on the left (i.e. the previously existing block is absorbed into
* the insertion block).
*/
if ((insertp + insertp->s.size) == currp->s.next) {
insertp->s.size += currp->s.next->s.size;
insertp->s.next = currp->s.next->s.next;
}
/* case: the insertion block is not left-adjacent to the beginning of another
* block of data owned by malloc. Set the insertion block member to point to
* the next block in the list.
*/
else {
insertp->s.next = currp->s.next;
}
/* case: the end of another block of data owned by malloc is adjacent to the
* beginning of the insertion block. Absorb the block on the right into the
* block on the left (i.e. the insertion block is absorbed into the preceeding
* block).
*/
if ((currp + currp->s.size) == insertp) {
currp->s.size += insertp->s.size;
currp->s.next = insertp->s.next;
}
/* case: the insertion block is not right-adjacent to the end of another block
* of data owned by malloc. Set the previous block in the list to point to
* the insertion block.
*/
else {
currp->s.next = insertp;
}
/* Set the free pointer list to start the block previous to the insertion
* block. This makes sense because calls to malloc start their search for
* memory at the next block after freep, and the insertion block has as good a
* chance as any of containing a reasonable amount of memory since we've just
* added some to it. It also coincides with calls to morecore from
* kandr_malloc because the next search in the iteration looks at exactly the
* right memory block.
*/
freep = currp;
}
在Linux中，有两种典型的请求内存的方法：sbrk和mmap。这些系统调用对频繁的小分配有严格的限制。 malloc（）是一个解决此问题的库函数。它使用sbrk / mmap请求大块内存，并在大块内部返回小内存块。这比直接调用sbrk / mmap更有效，更灵活。
在K＆R实现中，核心（通常称为竞技场）是一大块内存。 morecore()通过sbrk()向系统请求核心。当您多次调用malloc（）/ free（）时，将使用/分配核心中的某些块，而其他块则是空闲的。 K＆R malloc将空闲块的地址存储在循环单链表中。在此列表中，每个节点都是一个空闲内存块。第一个sizeof(Header)字节保持块的大小和指向下一个空闲块的指针。空闲块中的其余字节未初始化。与教科书中的典型列表不同，空闲列表中的节点只是指向核心中一些未使用区域的指针;除了核心之外，您实际上并没有分配每个节点。该列表是理解算法的关键。
下图显示了具有两个核心/竞技场的示例内存布局。在图中，每个字符采用sizeof(Header)字节。 @是Header，+标记分配记忆和-标记内核内的自由记忆。在该示例中，有三个分配的块和三个空闲块。三个空闲块存储在循环列表中。对于三个已分配的块，只有它们的大小存储在Header中。
This is core 1 This is core 2
@---------@+++++++++@++++++++++++ @----------@+++++++++++++++++@------------
| | |
p->ptr->ptr p = p->ptr->ptr->ptr p->ptr
在您的代码中，freep是免费列表的入口点。如果你反复跟随freep->ptr，你会回到freep - 它是循环的。一旦你理解了循环单链表，剩下的就相对简单了。 malloc()找到一个自由区块并可能将其拆分。 free()将一个空闲块添加回列表，并可将其合并到相邻的空闲块中。他们都试图维护列表的结构。
malloc()中提到“缠绕”。当您遍历整个空闲列表但找不到大于请求长度的空闲块时，会发生该行。在这种情况下，您必须使用morecore()添加新核心。base是一个零大小的块，始终包含在空闲列表中。避免特殊套管是一种技巧。这不是绝对必要的。free()可能看起来有点复杂，因为它必须考虑四种不同的情况来将新释放的块合并到列表中的其他空闲块。除非您想自己重新实现，否则这个细节并不重要。PS：K＆R malloc是我认为最优雅的代码之一。当我第一次理解代码时，真的很开眼界。令我感到难过的是，一些现代程序员，甚至不了解这种实现的基本原理，仅根据其编码风格调用了杰作。
我还发现这个练习非常有趣。
在我看来，可视化结构可能有助于理解逻辑 - 或者至少这对我有用。下面是我的代码，它尽可能地打印出K＆R malloc的流程。
我在K＆R malloc中做出的最重大的改变是“免费”的改变，以确保一些旧的指针不会再被使用。除此之外，我添加了评论并修复了一些小错字。
尝试使用NALLOC，MAXMEM和'main'中的测试变量也可能有所帮助。
在我的计算机（Ubuntu 16.04.3）上编译时没有错误：
gcc -g -std=c99 -Wall -Wextra -pedantic-errors krmalloc.c
krmalloc.c：
#include <stdio.h>
#include <unistd.h>
typedef long Align; /* for alignment to long boundary */
union header { /* block header */
struct {
union header *ptr; /* next block if on free list */
size_t size; /* size of this block */
/* including the Header itself */
/* measured in count of Header chunks */
/* not less than NALLOC Header's */
} s;
Align x; /* force alignment of blocks */
};
typedef union header Header;
static Header *morecore(size_t);
void *mmalloc(size_t);
void _mfree(void **);
void visualize(const char*);
size_t getfreem(void);
size_t totmem = 0; /* total memory in chunks */
static Header base; /* empty list to get started */
static Header *freep = NULL; /* start of free list */
#define NALLOC 1 /* minimum chunks to request */
#define MAXMEM 2048 /* max memory available (in bytes) */
#define mfree(p) _mfree((void **)&p)
void *sbrk(__intptr_t incr);
int main(void)
{
char *pc, *pcc, *pccc, *ps;
long *pd, *pdd;
int dlen = 100;
int ddlen = 50;
visualize("start");
/* trying to fragment as much as possible to get a more interesting view */
/* claim a char */
if ((pc = (char *) mmalloc(sizeof(char))) == NULL)
return -1;
/* claim a string */
if ((ps = (char *) mmalloc(dlen * sizeof(char))) == NULL)
return -1;
/* claim some long's */
if ((pd = (long *) mmalloc(ddlen * sizeof(long))) == NULL)
return -1;
/* claim some more long's */
if ((pdd = (long *) mmalloc(ddlen * 2 * sizeof(long))) == NULL)
return -1;
/* claim one more char */
if ((pcc = (char *) mmalloc(sizeof(char))) == NULL)
return -1;
/* claim the last char */
if ((pccc = (char *) mmalloc(sizeof(char))) == NULL)
return -1;
/* free and visualize */
printf("\n");
mfree(pccc);
/* bugged on purpose to test free(NULL) */
mfree(pccc);
visualize("free(the last char)");
mfree(pdd);
visualize("free(lot of long's)");
mfree(ps);
visualize("free(string)");
mfree(pd);
visualize("free(less long's)");
mfree(pc);
visualize("free(first char)");
mfree(pcc);
visualize("free(second char)");
/* check memory condition */
size_t freemem = getfreem();
printf("\n");
printf("--- Memory claimed : %ld chunks (%ld bytes)\n",
totmem, totmem * sizeof(Header));
printf(" Free memory now : %ld chunks (%ld bytes)\n",
freemem, freemem * sizeof(Header));
if (freemem == totmem)
printf(" No memory leaks detected.\n");
else
printf(" (!) Leaking memory: %ld chunks (%ld bytes).\n",
(totmem - freemem), (totmem - freemem) * sizeof(Header));
printf("// Done.\n\n");
return 0;
}
/* visualize: print the free list (educational purpose) */
void visualize(const char* msg)
{
Header *tmp;
printf("--- Free list after \"%s\":\n", msg);
if (freep == NULL) { /* does not exist */
printf("\tList does not exist\n\n");
return;
}
if (freep == freep->s.ptr) { /* self-pointing list = empty */
printf("\tList is empty\n\n");
return;
}
printf(" ptr: %10p size: %-3lu --> ", (void *) freep, freep->s.size);
tmp = freep; /* find the start of the list */
while (tmp->s.ptr > freep) { /* traverse the list */
tmp = tmp->s.ptr;
printf("ptr: %10p size: %-3lu --> ", (void *) tmp, tmp->s.size);
}
printf("end\n\n");
}
/* calculate the total amount of available free memory */
size_t getfreem(void)
{
if (freep == NULL)
return 0;
Header *tmp;
tmp = freep;
size_t res = tmp->s.size;
while (tmp->s.ptr > tmp) {
tmp = tmp->s.ptr;
res += tmp->s.size;
}
return res;
}
/* mmalloc: general-purpose storage allocator */
void *mmalloc(size_t nbytes)
{
Header *p, *prevp;
size_t nunits;
/* smallest count of Header-sized memory chunks */
/* (+1 additional chunk for the Header itself) needed to hold nbytes */
nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
/* too much memory requested? */
if (((nunits + totmem + getfreem())*sizeof(Header)) > MAXMEM) {
printf("Memory limit overflow!\n");
return NULL;
}
if ((prevp = freep) == NULL) { /* no free list yet */
/* set the list to point to itself */
base.s.ptr = freep = prevp = &base;
base.s.size = 0;
}
/* traverse the circular list */
for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
if (p->s.size >= nunits) { /* big enough */
if (p->s.size == nunits) /* exactly */
prevp->s.ptr = p->s.ptr;
else { /* allocate tail end */
/* adjust the size */
p->s.size -= nunits;
/* find the address to return */
p += p->s.size;
p->s.size = nunits;
}
freep = prevp;
return (void *)(p+1);
}
/* back where we started and nothing found - we need to allocate */
if (p == freep) /* wrapped around free list */
if ((p = morecore(nunits)) == NULL)
return NULL; /* none left */
}
}
/* morecore: ask system for more memory */
/* nu: count of Header-chunks needed */
static Header *morecore(size_t nu)
{
char *cp;
Header *up;
/* get at least NALLOC Header-chunks from the OS */
if (nu < NALLOC)
nu = NALLOC;
cp = (char *) sbrk(nu * sizeof(Header));
if (cp == (char *) -1) /* no space at all */
return NULL;
printf("... (sbrk) claimed %ld chunks.\n", nu);
totmem += nu; /* keep track of allocated memory */
up = (Header *) cp;
up->s.size = nu;
/* add the free space to the circular list */
void *n = (void *)(up+1);
mfree(n);
return freep;
}
/* mfree: put block ap in free list */
void _mfree(void **ap)
{
if (*ap == NULL)
return;
Header *bp, *p;
bp = (Header *)*ap - 1; /* point to block header */
if (bp->s.size == 0 || bp->s.size > totmem) {
printf("_mfree: impossible value for size\n");
return;
}
/* the free space is only marked as free, but 'ap' still points to it */
/* to avoid reusing this address and corrupt our structure set it to '\0' */
*ap = NULL;
/* look where to insert the free space */
/* (bp > p && bp < p->s.ptr) => between two nodes */
/* (p > p->s.ptr) => this is the end of the list */
/* (p == p->p.str) => list is one element only */
for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
/* freed block at start or end of arena */
break;
if (bp + bp->s.size == p->s.ptr) { /* join to upper nbr */
/* the new block fits perfect up to the upper neighbor */
/* merging up: adjust the size */
bp->s.size += p->s.ptr->s.size;
/* merging up: point to the second next */
bp->s.ptr = p->s.ptr->s.ptr;
} else
/* set the upper pointer */
bp->s.ptr = p->s.ptr;
if (p + p->s.size == bp) { /* join to lower nbr */
/* the new block fits perfect on top of the lower neighbor */
/* merging below: adjust the size */
p->s.size += bp->s.size;
/* merging below: point to the next */
p->s.ptr = bp->s.ptr;
} else
/* set the lower pointer */
p->s.ptr = bp;
/* reset the start of the free list */
freep = p;
}