Table of Contents

• Overview
• Current Status
• Availability
• Bugs
• Resources
• People

Please send FSF & GNU inquiries & questions to [email protected]. There are also other ways to contact the FSF.

Please send comments on these web pages to webmasterswww.gnu.org. Send other questions to [email protected].

Copyright © 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA

Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.

Updated: $Date: 2008/10/23 16:21:23 $

作者：Hily 原始链接：http://hily.me/blog/2007/06/uclibc-malloc-free/
版权声明：可以转载，转载时务必以超链接形式标题文章原始出处和作者信息及版权声明

　　uClibc 是一个小型的 C 库，应用于嵌入式 Linux 系统开发。它基本实现了 glibc 的功能，几乎所有 glibc 支持的应用程序都能在 uClibc 上运行，这使得应用程序的移植变得相当简单，只需要使用 uClibc 库重新编译源代码就可以了。目前 uClibc 主要运行在不带 MMU 的平台下，支持 alpha, ARM, i386, i960, h8300, m68k, mips/mipsel, PowerPC, SH, SPARC 等等。
　　在国内，Linux 的小型应用一般采用 ARM7 作为处理器（见得较多的是Samsung S3C44B0X），加上开源的 uClinux 作为操作系统，构成一个价格上相对较低的嵌入式开发平台。
　　在 uClinux 上最经常使用的 C 库，便是 uClibc，本篇主要是对 uClibc 中的 malloc 和 free 做简要分析，希望能起到一个抛砖引玉的作用。目前我使用的开发平台为 S3C44B0X + uClinux (Kernel Version 2.4.20)，uClibc 的版本为 0.9.19，版本虽然旧了些，但不影响理解 malloc 的工作机制，而且可能更有利（通常版本越高，代码越复杂）。
　　顺便在此附上该版本 malloc 部分的代码，它位于 uClibc/libc/stdlib/ 目录下。 点击下载文件

Hily Jiang
Email&Gtalk: hilyjiang at Gmail
Blog: http://hily.me/blog/

一、头文件中的声明
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 库函数远不如想像中的恐怖，希望读到此文的朋友们够循此继续解读下去能

本篇完。

– EOF –