根据源码,简单分析一下glibc的ptmalloc分配器的实现,主要是明确malloc与free的流程

下面的例子都是基于glibc 2.19的原始实现,在不说明的情况下为64bit。

相关结构

对于glibc管理堆需要的结构也有很多资料详细介绍过了,这里只简单地回顾一下。

chunk (块)

堆内存分配的基本单位,分为malloc chunk, free chunk, top chunk三类,都使用下面的struct表示

1
2
3
4
5
6
7
8
9
10
11
12
struct malloc_chunk {

INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). 前一块的大小*/
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. 此块的大小*/

struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;

/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk* bk_nextsize;
};

一般来说这些头信息和用户数据都是按规律紧密排列在内存中,通过prev_size和size可以很容易地找到内存中的上一块和下一块的位置

chunk的大小在32位系统下最小16 bytes,对齐8 bytes;64位系统下最小32 bytes,对齐16 bytes

常量

因为对齐的缘故,size的低3位用于记录chunk的一些flag

1
2
3
#define PREV_INUSE 0x1 //上一块是否在使用
#define IS_MMAPPED 0x2 //是否为mmap的内存
#define NON_MAIN_ARENA 0x4 //是否非main_arena

bins

将free之后的chunk链起来进行管理,以便在下次malloc的时候能够再次利用,分为fast bin, small bin, large bin, unsorted bin 4类。除了fast bin是单向链表LIFO外,其余都是双向循环链表且为FIFO。

实现时,bins都是使用chunk的结构来表示的,但是只使用fd,bk这两个成员,空间上也只分配16 bytes,这是glibc的一种hack的做法。

malloc_state

表示一个模块中堆的分配情况,在主线程中的实例是main_arena这个全局变量

malloc流程

malloc的具体过程在_int_malloc中实现,比较复杂

调整大小

将传入malloc的size加上8 bytes的overhead并向16 bytes对齐,如果不足32 bytes则分配32 bytes,之后所有分配用的size都用调整后的。

检查fastbins

如果块大小符合fast bins,则在对应大小的fastbin中寻找是否有合适的chunk,如果有则直接返回。

检查smallbins

如果块大小符合small bins,则在对应大小的smallbin中寻找是否有合适的chunk,如果有则直接返回。

对于fastbins和smallbins来说,每个bin中的chunk大小都是相同的,所以只要对应的bin中有chunk,就能够直接返回恰好符合的块。

consolidate fastbin

如果块大小符合large bins,这时不会直接在对应的bin中寻找因为这时每个bin中的chunk并不是同一大小不能马上找到正好符合的快。此时会调用malloc_consolidate函数进行fastbin chunk的合并,fastbin chunk在free时不会清除下一块的PREV_INUSE,在此函数中将所有fastbins中的chunk取出并清除其下一块PREV_INUSE以及进行相应的合并操作,最后放入unsorted bin。

处理unsorted bin

如果之前没能返回恰好符合的块,则开始处理unsorted bin中的块

这里有一个例外,如果unsorted bin中只有一个chunk且这个chunk是last_remainder,而且大小足够,则优先使用此chunk,分裂后将前一块返回给用户,剩下的一块作为新的last_remainder再次放入unsorted bin.关于last_remainder可以参考最后给出的understanding glibc malloc中的叙述

  1. 逐个迭代unsorted bin中的块,如果发现chunk的大小正好是需要的大小,则迭代过程中止,直接返回此块;否则将此块放入到对应的small bin或者large bin中,这也是整个heap管理中唯一会将chunk放入small bin与large bin中的代码。
  2. 迭代过程直到unsorted bin中没有chunk或超过最大迭代次数(10000)为止。
  3. 随后开始在small bins与large bins中寻找best-fit,即满足需求大小的最小块,如果能够找到,则分裂后将前一块返回给用户,剩下的块放入unsorted bin中。
  4. 如果没能找到,则回到开头,继续迭代过程,直到unsorted bin空为止

使用top chunk

如果之前的操作都没能找到合适的块,将分裂top chunk返回给用户,若top chunk的大小还是不够,再次执行malloc_consolidate函数清除fastbin,若没有fastbin的chunk,只能使用sysmalloc函数借助系统调用拓展空间。

free流程

free的实现主要在_int_free函数中,相对来说简单一点

安全检查

进行一系列的检查,包括内存地址对齐,PREV_INUSE位是否正确等等,能够发现一些破坏与double free的问题,这些检查以后再详述。

fastbin chunk

如果chunk大小满足fastbin,则不取消下一块的PREV_INUSE位,直接放入fastbin中

consolidate

首先检查被free chunk的前一块,如果未使用,则合并这2块,将前一块从其bin中移除(使用unlink宏)

再检查其后一块,如果发现是top chunk,则最后合并到top chunk中,不放入任何bin;如果不是top chunk且未使用,则再合并这2块,将后一块从其bin中移除。

将合并过的大块放入unsorted bin中。

小结

这里只是大概地阐述了一下malloc/free的过程,比较浅显,主要是大致有一个感觉,之后在利用时还会详述有关的过程。

参考资料

Understanding glibc malloc

这里还有一篇译文: 深入理解glibc malloc

GNU Libc Source: malloc.c