与 K&R 的 malloc 实现混淆
Confusion with implementation of malloc from K&R
我一直在通读 K&R,在实施 malloc()
included 时遇到了一点困惑。
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
) 到新的 to-be-returned 块开始的位置时,我们如何能够引用 p->s.size
并将其分配给 nunits
。 p
不应该是 NULL
,因为除了 header 之外,该块从未被初始化过吗?
如果malloc()
将使用一部分免费段,则将其分成两部分。第一个仍然免费,第二个将是 returned。我想你已经明白了。
那么,后果是什么:
prev->s.ptr
仍然指向相同的地址(原来的 p
),这没关系,因为这里仍然有空闲内存,只是比以前少 nunits
。
- 在头部'original p'中,地址
s.ptr
保持不变,所以prev->s.ptr->s.ptr
仍然指向与之前相同的地址,链仍然有效(前两个子弹应该回答第一个问题)。
- 现在
p
递增指向我们想要return(p += p->s.size
)的内存块的开始。当然那个内存块也应该以一个还没有初始化的头开始,所以我们设置p->s.size = nunits
; p->s.ptr
可能仍然包含垃圾值,但这没关系,因为它不是一个空闲块(应该回答第二个问题)。
- 最后
p + 1
被return编辑,也就是新header后面的内存块"payload"
在第一次调用 malloc
时,通过调用 sbrk
物理分配内存块并将其添加到空闲列表中。此时内存看起来像这样:
1 (base) freep
----------- -------
| 10 / 0 | | 1 |
----------- -------
10 11 12 13 14 15
-------------------------------------------------------------
| 1 / 6 | | | | | |
-------------------------------------------------------------
为了简单起见,我根据 "units" 而非实际字节对内存块进行了编号。这里我们假设全局变量 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
是 而不是 NULL。它指向某处,但该内存没有有意义的数据。
现在我们 运行 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
的当前值。在这一点上,没有任何变化。然后我们returnp+1
,也就是15,给调用者。
最终结果是prev
指向的块没有变化,但是prev->s.ptr
指向的块现在变小了请求的单元数,地址14是现在是分配的内存块的开始,大小为 2 个单位。
当地址 15 稍后传递给 free
时,它会查看地址 14 以查看分配的块有多大,以便它可以将这些单元放回空闲列表中。
我一直在通读 K&R,在实施 malloc()
included 时遇到了一点困惑。
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
) 到新的 to-be-returned 块开始的位置时,我们如何能够引用p->s.size
并将其分配给nunits
。p
不应该是NULL
,因为除了 header 之外,该块从未被初始化过吗?
如果malloc()
将使用一部分免费段,则将其分成两部分。第一个仍然免费,第二个将是 returned。我想你已经明白了。
那么,后果是什么:
prev->s.ptr
仍然指向相同的地址(原来的p
),这没关系,因为这里仍然有空闲内存,只是比以前少nunits
。- 在头部'original p'中,地址
s.ptr
保持不变,所以prev->s.ptr->s.ptr
仍然指向与之前相同的地址,链仍然有效(前两个子弹应该回答第一个问题)。 - 现在
p
递增指向我们想要return(p += p->s.size
)的内存块的开始。当然那个内存块也应该以一个还没有初始化的头开始,所以我们设置p->s.size = nunits
;p->s.ptr
可能仍然包含垃圾值,但这没关系,因为它不是一个空闲块(应该回答第二个问题)。 - 最后
p + 1
被return编辑,也就是新header后面的内存块"payload"
在第一次调用 malloc
时,通过调用 sbrk
物理分配内存块并将其添加到空闲列表中。此时内存看起来像这样:
1 (base) freep
----------- -------
| 10 / 0 | | 1 |
----------- -------
10 11 12 13 14 15
-------------------------------------------------------------
| 1 / 6 | | | | | |
-------------------------------------------------------------
为了简单起见,我根据 "units" 而非实际字节对内存块进行了编号。这里我们假设全局变量 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
是 而不是 NULL。它指向某处,但该内存没有有意义的数据。
现在我们 运行 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
的当前值。在这一点上,没有任何变化。然后我们returnp+1
,也就是15,给调用者。
最终结果是prev
指向的块没有变化,但是prev->s.ptr
指向的块现在变小了请求的单元数,地址14是现在是分配的内存块的开始,大小为 2 个单位。
当地址 15 稍后传递给 free
时,它会查看地址 14 以查看分配的块有多大,以便它可以将这些单元放回空闲列表中。