工学1号馆

home

« | 返回首页 | »

malloc 深入剖析4--组织堆

By Wu Yudong on July 28, 2016

在前面的几篇文章中, 我们第一次尝试实现一个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返回的指针的前面。

QQ截图20160727203023

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

No comments yet.
To verify that you are human, please fill in "七"(required)