在前面的几篇文章中, 我们第一次尝试实现一个malloc函数，但是我们没能满足所有的需求，在本文，我们将试着探寻一种堆的组织方式，这样我们就可以实现一种高效而且包含free和relloc的malloc.
1.我们需要什么 ?
如果我们考虑编程上下文之外的问题，可以推断我们需要出什么样的信息类来解决我们的问题，打一个比方：你拥有一块领地，并且将它划分成一段段的portion，然后出租部分portion，客户要求不同的连续的长度（你的领地仅使用一维来描述），当他们使用结束后将租地归还给你，于是你可以再一次将它出租。
在领地的一端，你有一条路和一辆可编程小轿车：你输入区域的开始位置和目的地之间的距离(portion的起始部分) 于是我们需要知道每一个portion的开始部分 (这就是malloc返回的指针) 并且当我们在portion的开始位置，我们需要下一个portion的地址。
一个解决办法是在每一块的前面使用一个指向下一块的标记 (为了避免不必要的计算，还应包含当前块的大小) 我们还要为空闲块增加标志 (当客户归还的时候标记) ，现在，当一个客户请求一个指定大小的 portion，我们使用汽车轮询这些标记。当我们找到一个空闲且大小足以满足客户请求的 portion 标记，除去标记。 当我们达到最后的portion (它没有下一个portion的地址的标志)增加一个新的标记。现在我们可以将这种想法转变到内存：我们需要在每一块的前面设置额外的信息来至少指明块大小、下一个块的地址以及是否被释放。
本文地址：http://wuyudong.com/2016/07/28/2353.html，转载请注明源地址。
2.怎样表示块信息
通过上面的分析，我们需要在每一块（chunk）的前面包含信息的小块（block），名为meta-data，这个block至少包含一个指向下一个chunk的指针，一个表示空闲块的标志和chunk的大小。 当然，block的信息在malloc返回的指针的前面。
Figure 3 展示了一个使用包含meta-data前缀的已分配块的堆管理例子。每一个chunck的数据由一小块的meta-data以及跟着的数据块组成。由malloc返回的指针如上图底部所示，注意它指向数据块（block），并不是整个块（chunk）。现在我们怎样将其转换成C语言代码？这个看起来像经典的线性链表，于是我写了一个包含所需信息类型的链表。
typedef struct s_block *t_block;
struct s_block {
size_t size;
t_block next;
int free;
};
注意到使用 typedef 可以简化类型的使用，因为我们将不会再使用非指针类型的结构体。
上面的代码使用int作为free的标记是不是有点浪费空间，但是由于结构体默认对齐，后面将会看到如何压缩metadata的大小，还会看到mallo必须返回对齐的地址。
一个经常被问起的观点是：怎样创建一个结构体而不使用malloc？这个问题很简单，你仅仅需要搞清楚什么是结构体，在内存中，一个结构体是字段简单地连接，在我们的例子中结构体块仅12 字节(使用32位整型)，前面的4个对应块大小，接下来的4个字节为指向下一个块的指针，对后的4个字节为整型标记free。当编译器遇到访问结构体域的时候(比如 s.free 或 p->free) 将其转到结构体的起始地址再加上前面所有域的字节长度 (于是p->free等价于 *((char*)p+8) ，s.free 等价于 *((char*)&s + 8))，你需要做的就是使用sbrk为块分配足够的空间 (即meta-data的大小加上数据块的大小)，并且将 旧的break的地址放入变量t_block:
/* 使用t_block的例子 without malloc */ t_block b; /* 在b中保存旧的break */ b = sbrk(0); /* 增加请求的空间 */ /* 大小为malloc的参数 */ sbrk(sizeof(struct s_block) + size); b->size = size; /* ... */
Comments