我一直在通读K&R，在实现包含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 */
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 = freep = prevp = &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->s.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->s.size == bp) {
p->s.size += bp->s.size;
p->s.ptr = bp->s.ptr;
} else
p->s.ptr = bp;
freep = p;
}
我难以理解的是尾端是如何分配的。
- 对块进行分区后，
prevp->s.ptr是否仍指向块的开头(但现在大小为 - nunits)，因此块的剩余部分仍然可用？ - 当递增(
p += p->size)到新的，要返回的块开始的位置时，我们如何能够引用p->s.size并将其分配给nunits。p不应该NULL，因为除了标头之外，块从未初始化过？
在第一次调用malloc时，内存块通过调用sbrk进行物理分配，并添加到自由列表中。 此时，内存如下所示：
1 (base) freep
----------- -------
| 10 / 0 | | 1 |
----------- -------
10 11 12 13 14 15
-------------------------------------------------------------
| 1 / 6 | | | | | |
-------------------------------------------------------------
为了简单起见，我根据"单位"而不是实际字节对内存块进行了编号。 在这里，我们假设全局变量base位于地址 1，并且从地址 10 开始分配了一个由 6 个单元组成的块。 在每个单位中，第一个数字是ptr的值，第二个是size的值。 此外，freep还包含免费块开始的地址。
因此，自由列表从空的基本块开始，然后指向地址 10 处的块。 该块包含 5 个空闲单位，并指向基本块。
假设当前对malloc的调用请求 2 个单位。 当我们第一次进入for循环时，prev == 1和p == 10：
1 (base) freep prev p
----------- ------- ------ ------
| 10 / 0 | | 1 | | 1 | | 10 |
----------- ------- ------ ------
10 11 12 13 14 15
-------------------------------------------------------------
| 1 / 6 | | | | | |
-------------------------------------------------------------
在尾部添加时，第一个语句是p->s.size -= nunits;。 这会将 p 中的size减nunits：
1 (base) freep prev p
----------- ------- ------ ------
| 10 / 0 | | 1 | | 1 | | 10 |
----------- ------- ------ ------
10 11 12 13 14 15
-------------------------------------------------------------
| 1 / 4 | | | | | |
-------------------------------------------------------------
所以现在地址 10 处的块大小为 4 个单位，而不是 6 个单位。 接下来是p += p->s.size;，它将size的值添加到p：
1 (base) freep prev p
----------- ------- ------ ------
| 10 / 0 | | 1 | | 1 | | 14 |
----------- ------- ------ ------
10 11 12 13 14 15
-------------------------------------------------------------
| 1 / 4 | | | | xx / xx | |
-------------------------------------------------------------
现在p指向解决 14。 目前，ptr和size字段包含垃圾，此处表示为"xx"。 请注意，p不是空的。 它指向某个地方，但该内存没有有意义的数据。
现在我们运行p->s.size = nunits;，它将p指向的单位中的size字段设置为：
1 (base) freep prev p
----------- ------- ------ ------
| 10 / 0 | | 1 | | 1 | | 14 |
----------- ------- ------ ------
10 11 12 13 14 15
-------------------------------------------------------------
| 1 / 4 | | | | xx / 2 | |
-------------------------------------------------------------
然后我们有freep = prevp;将自由指针设置为prev的当前值。 在这一点上，没有任何变化。 然后我们返回p+1，即 15，给调用方。
最终结果是prev指向的块没有更改，但prev->s.ptr指向的块现在小于请求的单元数，地址 14 现在是大小为 2 个单元的已分配内存块的开始。
当地址 15 稍后传递给free时，它会查看地址 14 以查看分配的块有多大，以便它可以将这些单元放回空闲列表中。
如果malloc()将使用自由隔离的一部分，则将其分为两部分。 第一个保持免费，第二个将是返回的。我想你已经明白了。
那么，后果是什么：
prev->s.ptr仍然指向相同的地址(原始p)，这没关系，因为这里仍然有可用内存，只是比以前少nunits。- 在标题"原始 p"中，地址
s.ptr保持不变，因此prev->s.ptr->s.ptr仍然指向与以前相同的地址，则链仍然有效(前两个项目符号应回答第一个问题)。 - 现在
p递增以指向我们要返回的内存块的开头(p += p->s.size)。当然，该内存块也应以尚未初始化的标头开头，因此我们设置p->s.size = nunits;p->s.ptr可能仍然包含垃圾值，但这没关系，因为它不是一个免费块(这应该回答第二个问题)。 - 最后返回
p + 1，这是新标头后面的内存块的"有效负载"。