隐式空闲链表


1 堆-块数据结构简介

如下图所示:

31

头部

3 2  1  0
块大小

00 a (a=1 代表已分配 a=0代表未分配)
malloc返回指针开始处
有效负载(包括分配块)
填充(块对齐)–可选


堆块格式

通常一个块由一个字的头部、有效负载、以及一些额外填充,头部编码定义了块大小以及块的状态(空闲还是分配),如果定义块为双字对齐约束条件,那么块大小总是8的倍数,且块大小的最低3位为零,因此我们只需要块大小的29个高位,释放剩余的3位来编码其他信息。在这种情况中,我们用其中的最低位来指明块是否已分配或空闲。例:假设我们有一个已分配块,大小为24(0X18)字节,那么它的头部将是:
0X00000018 |0X1 = 0X00000019
类似地,一个块大小为40(0X28)字节的空闲块有如下的头部
0X00000028 |0X0 = 0X00000028
头部后面就是应用调用malloc时请求的有效负载。有效负载后面是一块不使用的填充块,其大小为任意。需要填充有很多原因。比如,填充可能是分配器的策略的一部分,主要是避免外部碎片,或满足块对齐模式。


相关阅读:
分配器实现
分配器 要求 性能指标