Hily Jiang
Email&Gtalk: hilyjiang at Gmail
Blog: http://hily.iyi.cn/

一、头文件中的声明
malloc 和 free 在头文件 stdlib.h 中声明：

/* Allocate SIZE bytes of memory.  */
extern void *malloc (size_t __size) __THROW __attribute_malloc__;
/* Free a block allocated by `malloc', `realloc' or `calloc'.  */
extern void free (void *__ptr) __THROW;

malloc 返回一个指定大小为 __size 的指针。
free 释放指针 __ptr 指向的内存空间。

 

二、基本机制
stdlib 中的 malloc 模块维护了一个空闲区域的链表，这个链表可以说是这个模块最为核心的部分。
当调用 malloc 申请空间时，先检查该链表中是否有满足条件的空闲区域节点，如果没有，则向内核申请内存空间，放入这个链表中，然后再重新在链表中查找一次满足条件的空闲区域节点。
当调用 free 释放空间时，把释放的空间放入空闲区域中。和 malloc 相对应地，如果空闲的空间大于某个阈值时，调用 free 时会把不需要的空间再还给内核，以节约内存。

三、两个重要的结构
前面说到这个模块中最核心的空闲区域链表，它的节点结构为（heap.h中）：

struct heap_free_area
{
size_t size;
struct heap_free_area *next, *prev;
};

size 表示该空闲区域的大小，这个空闲区域的实际地址并没有用指针详细地指明，因为它就位于当前 heap_free_area 节点的前面，如下图所示：

+-------------------------------+--------------------+
|                               |   heap_free_area   |
+-------------------------------+--------------------+
\___________ 空闲空间 ___________/\___ 空闲空间信息 ___/

从图上我们可以看出，实际可用的空闲空间大小为 size - sizeof(struct heap_free_area)。
指针 next, prev 分别指向下一个和上一个空间区域，所有的空闲区域就是通过许许多多这样的节点链起来的，很显然，这样组成的是一个双向链表。
双向链表的头节点由另外一个结构 heap 索引，heap 的定义为（heap.h中）：

struct heap
{
/* A list of memory in the heap available for allocation.  */
struct heap_free_area *free_areas;
#ifdef HEAP_USE_LOCKING
/* A lock that can be used by callers to control access to the heap.
The heap code _does not_ use this lock, it's merely here for the
convenience of users!  */
pthread_mutex_t lock;
#endif
};

heap 结构中只有两个成员，free_areas 指向空间区域链表头节点，lock 在多线程环境中作线程锁使用。

 

四、模块初始化
malloc 模块的初始化，其实就是对以上两个结构的初始化，在 malloc.c 中进行：

/* The malloc heap.  We provide a bit of initial static space so that
programs can do a little mallocing without mmaping in more space.  */
HEAP_DECLARE_STATIC_FREE_AREA (initial_fa, 256);
struct heap __malloc_heap = HEAP_INIT_WITH_FA (initial_fa);

宏 HEAP_DECLARE_STATIC_FREE_AREA 在 heap.h 中定义：

#define HEAP_DECLARE_STATIC_FREE_AREA(name, size)			\
static struct								\
{									\
char space[(size) - sizeof (struct heap_free_area)];		\
struct heap_free_area _fa;						\
} name = { "", { (size), 0, 0 } }

HEAP_DECLARE_STATIC_FREE_AREA 在这里初始化了一个大小为 256 字节的静态空闲区域。
接下来创建一个 heap，它的 free_areas 成员指向上面这个刚初始化的空间中的 _fa，同时初始化线程锁：

# define HEAP_INIT_WITH_FA(fa)	{ &fa._fa, PTHREAD_MUTEX_INITIALIZER }

至此初始化完毕，生成了一个 heap 结构，它的 free_areas 成员指向一个静态空间区域。

 

五、malloc 解读
malloc 函数在 malloc.c 中定义，它实际上是调用 malloc_from_heap 从空闲区域中申请空间。
为减短篇幅，下面采用源代码注释的方法进行解读，同样删除了一些对于理解工作原理不太重要的代码：

static void *
malloc_from_heap (size_t size, struct heap *heap)
{
void *mem;
/* 一个 malloc 块的结构如下：
+--------+---------+-------------------+
| SIZE   |(unused) | allocation  ...   |
+--------+---------+-------------------+
^ BASE             ^ ADDR
^ ADDR - MALLOC_ALIGN
申请成功后返回的地址是 ADDR
SIZE 表示块的大小，包括前面的那部分，也就是 MALLOC_HEADER_SIZE
*/
size += MALLOC_HEADER_SIZE;
/* 申请线程锁，避免其它线程操作 heap 引起冲突 */
__heap_lock (heap);
/* 从 heap 中申请大小为 size 的空间 */
mem = __heap_alloc (heap, &size);
/* 释放线程锁 */
__heap_unlock (heap);
if (! mem)
/* 如果空间申请失败，则从系统中申请空间放入 heap 后再重新申请  */
{
/* 从系统申请空间时，最小的单元为 MALLOC_HEAP_EXTEND_SIZE，大于 MALLOC_HEAP_EXTEND_SIZE 时，
则根据需要的空间大小向上申请 MALLOC_HEAP_EXTEND_SIZE 的整数倍大小的空间 */
void *block;
size_t block_size
= (size < MALLOC_HEAP_EXTEND_SIZE
? MALLOC_HEAP_EXTEND_SIZE
: MALLOC_ROUND_UP_TO_PAGE_SIZE (size));
/* 向内核申请空间 */
block = mmap (0, block_size, PROT_READ | PROT_WRITE,
MAP_SHARED | MAP_ANONYMOUS, 0, 0);
/* 申请成功，将空间放入 heap 的空闲区域 */
if (block != (void *)-1)
{
/* 申请线程锁 */
__heap_lock (heap);
/* 将空间放入 heap 的空闲区域 */
__heap_free (heap, block, block_size);
/* 重新申请一次空间 */
mem = __heap_alloc (heap, &size);
/* 释放线程锁 */
__heap_unlock (heap);
}
}
if (mem)
{
/* 申请成功，将 mem 指向 ADDR 处
+--------+---------+-------------------+
| SIZE   |(unused) | allocation  ...   |
+--------+---------+-------------------+
^ BASE             ^ ADDR
^ mem
*/
mem = MALLOC_SETUP (mem, size);
}
else
MALLOC_DEBUG (-1, "malloc: returning 0");
return mem;
}

malloc_from_heap 中调用了两个重要的函数，以下分别作解读。
__heap_alloc函数，位于 heap_alloc.c，这个函数的作用就是从空闲区域链表中找到满足条件的节点，同时它会修改参数中的 size，返回实际分配的空间大小：

void *
__heap_alloc (struct heap *heap, size_t *size)
{
struct heap_free_area *fa;
size_t _size = *size;
void *mem = 0;
/* 根据 HEAP_GRANULARITY 大小向上取整，在 heap.h 中定义 */
_size = HEAP_ADJUST_SIZE (_size);
/* 在空闲区域链表中查找大小大于等于 _SIZE 的节点  */
for (fa = heap->free_areas; fa; fa = fa->next)
if (fa->size >= _size)
{
/* 找到满足条件的节点 */
mem = HEAP_FREE_AREA_START (fa);
*size = __heap_free_area_alloc (heap, fa, _size);
break;
}
return mem;
}

在链表中如果找到满足条件的节点，则通过 __heap_free_area_alloc 分配空间（heap.h中）：

extern inline size_t
__heap_free_area_alloc (struct heap *heap,
struct heap_free_area *fa, size_t size)
{
size_t fa_size = fa->size;
if (fa_size < size + HEAP_MIN_FREE_AREA_SIZE)
{
/* 如果在这个空闲区域中剩余的空间不足以维持一个 heap_free_area 节点，
则把这个区域从链表中移除
__heap_delete 只是个简单的链表操作，在 heap.h 中定义
*/
__heap_delete (heap, fa);
/* 修改大小，实际申请的空间要大于传入的 size */
size = fa_size;
}
else
/* 如果这个区域中还有空闲空间，就把 heap_free_area 节点中
的 size 减小 size就可以了：
分配前：
__________ 空闲空间 __________     __ 空闲空间信息 __
/                              \ /                  \
+-------------------------------+--------------------+
|                               |   heap_free_area   |
+-------------------------------+--------------------+
\__________ fa->size __________/
分配后：
___ 已分配 __     __ 空闲空间 __   __ 空闲空间信息 __
/             \ /              \ /                  \
+-------------------------------+--------------------+
|              |                |   heap_free_area   |
+-------------------------------+--------------------+
\____ size ___/ \__ fa->size __/
*/
fa->size = fa_size - size;
return size;
}

如果第一次申请空间不成功，就会向系统申请空间，通过 __heap_free 加入到 heap 的空闲区域链表中。
__heap_free 在 heap_free.c 中被定义，它将指定的内存区域加入链表：

struct heap_free_area *
__heap_free (struct heap *heap, void *mem, size_t size)
{
struct heap_free_area *fa, *prev_fa;
void *end = (char *)mem + size;
/* 空闲区域链表是按照地址从小到大排列的，这个循环是为了找到 mem 应该插入的位置 */
for (prev_fa = 0, fa = heap->free_areas; fa; prev_fa = fa, fa = fa->next)
if (HEAP_FREE_AREA_END (fa) >= mem)
break;
if (fa && HEAP_FREE_AREA_START (fa) <= end)
{
size_t fa_size = fa->size + size;
if (HEAP_FREE_AREA_START (fa) == end)
/* mem 在 fa 之前
如果 fa 和 mem 是连续的，那么将 mem 空间并入 fa 节点管理
+---------------+--------------+---------------+
|       |prev_fa|      mem     |       |   fa  |
+---------------+--------------+---------------+
^______________________________^
prev_fa 与 fa 的链接关系不变，只要更改 fa 中的 size 就可以了
*/
{
/* 如果 fa 前一个节点和 mem 是连续的，那么将 fa 前一个节点的空间
也并入 fa 节点管理
+---------------+---------------+--------------+---------------+
|       |pre2_fa|       |prev_fa|      mem     |       |   fa  |
+---------------+---------------+--------------+---------------+
^______________________________________________^
将 prev_fa 从链表中移出，同时修改 fa 中的 size
*/
if (prev_fa && mem == HEAP_FREE_AREA_END (prev_fa))
{
fa_size += prev_fa->size;
__heap_link_free_area_after (heap, fa, prev_fa->prev);
}
}
else
/* mem 在 fa 之后 */
{
struct heap_free_area *next_fa = fa->next;
/* 如果 mem 与 next_fa 是连续的，将 mem 并入 next_fa 节点管理
+---------------+--------------+--------------+---------------+
|       |prev_fa|      |   fa  |      mem     |       |next_fa|
+---------------+--------------+--------------+---------------+
^_____________________________________________^
将 fa 从链表中移出，同时修改 next_fa 中的 size
*/
if (next_fa && end == HEAP_FREE_AREA_START (next_fa))
{
fa_size += next_fa->size;
__heap_link_free_area_after (heap, next_fa, prev_fa);
fa = next_fa;
}
else
{
/* 如果 mem 与 next_fa 不连续，将 fa 结点移到 mem 尾部
+---------------+--------------+--------------+---------------+
|       |prev_fa|      |   fa  | mem | unused |       |next_fa|
+---------------+--------------+--------------+---------------+
^___________________^^________________________^
需要重新链接 fa 与 prev_fa 和 next_fa 的关系
*/
fa = (struct heap_free_area *)((char *)fa + size);
__heap_link_free_area (heap, fa, prev_fa, next_fa);
}
}
fa->size = fa_size;
}
else
/* 如果找不到 fa，或 mem 在 fa 之前，那么可以简单地
把 mem 插入 prev_fa 和 fa之间 */
fa = __heap_add_free_area (heap, mem, size, prev_fa, fa);
return fa;
}

 

六、free 解读
解读完 malloc 的代码，再解读 free 应该是件容易的事了，因为 free 中也用到了上面解读过程中的一些函数。
来看代码吧，free 在 free.c 中定义，它实际调用的是 free_to_heap：

static void
free_to_heap (void *mem, struct heap *heap)
{
size_t size;
struct heap_free_area *fa;
/* 检查 mem 是否合法 */
if (! mem)
return;
/* 获取 mem 指向的 malloc 块的的实际大小和起始地址 */
size = MALLOC_SIZE (mem);
mem = MALLOC_BASE (mem);
/* 申请线程锁 */
__heap_lock (heap);
/* 把 mem 指向的空间放到 heap 中，__heap_free 在 malloc 中已解读过了  */
fa = __heap_free (heap, mem, size);
/* 检查空闲区域大小是否超过了阈值 MALLOC_UNMAP_THRESHOLD */
if (HEAP_FREE_AREA_SIZE (fa) < MALLOC_UNMAP_THRESHOLD)
/* 没有超过，只需要释放线程锁就可以了 */
__heap_unlock (heap);
else
/* 超过了，则把多余的空间释放，交还给系统内核管理  */
{
unsigned long start = (unsigned long)HEAP_FREE_AREA_START (fa);
unsigned long end = (unsigned long)HEAP_FREE_AREA_END (fa);
/* 从空闲链表中删除该空闲区域 */
__heap_delete (heap, fa);
if (__heap_is_empty (heap))
/* 如果空闲链表为空 */
{
/* 保留 MALLOC_MIN_SIZE 大小的区域给 heap，作为空闲区域 */
__heap_free (heap, (void *)start, MALLOC_MIN_SIZE);
start += MALLOC_MIN_SIZE;
}
/* 使要释放的空间的起止地址按页对齐，开始地址向上对齐，结束地址向下对齐 */
unmap_start = MALLOC_ROUND_UP_TO_PAGE_SIZE (start);
unmap_end = MALLOC_ROUND_DOWN_TO_PAGE_SIZE (end);
/* 将对齐后余下的空间再放回 heap 中 */
if (unmap_start > start)
{
if (unmap_start - start < HEAP_MIN_FREE_AREA_SIZE)
unmap_start += MALLOC_PAGE_SIZE;
__heap_free (heap, (void *)start, unmap_start - start);
}
if (end > unmap_end)
{
if (end - unmap_end < HEAP_MIN_FREE_AREA_SIZE)
unmap_end -= MALLOC_PAGE_SIZE;
__heap_free (heap, (void *)unmap_end, end - unmap_end);
}
/* 系统调用前需要先释放锁 */
__heap_unlock (heap);
if (unmap_end > unmap_start)
/* 最后，调用 munmap 释放内存 */
munmap ((void *)unmap_start, unmap_end - unmap_start);
}
}

在这个过程中值得提到的有两点，似乎是 uClibc 不完善的地方。
1. 在检查到空闲链表为空时，为何不把模块初始化时产生的静态空闲域 initial_fa._fa 赋给 heap 中的 free_areas？而偏偏要到将要释放的空间里割出一块呢？
2. 源代码在将对齐后余下的空间放回 heap 中前有一段注释：

      /* We have to be careful that any left-over bits are large enough to
return.  Note that we _don't check_ to make sure there's room to
grow/shrink the start/end by another page, we just assume that
the unmap threshold is high enough so that this is always safe
(i.e., it should probably be at least 3 pages).  */

意思是余下的空间应该要足够大，也就是就最小也要有 HEAP_MIN_FREE_AREA_SIZE 这么大，否则上面的对齐就没有意义了。程序中没有去处理这种情况，是因为它假设当阈值设置得足够大时，这种情况发生的机率很小，作者认为它基本上是安全的。
检查了一下官方最新的代码，这部分仍然没有做修改：
http://www.uclibc.org/cgi-bin/viewcvs.cgi/trunk/uClibc/libc/stdlib/malloc/free.c?rev=18427&view=markup

 

七、结语
之前从来没读过 C 库的代码，这次对 malloc 和 free 代码的走读，原因是开发过程中碰上了 Bug，跟踪到这里面来的。看完后发现 C 库函数远不如想像中的恐怖，希望读到此文的朋友们够循此继续解读下去能 :-)