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 —

《uClibc 中的 malloc 和 free》有14个想法

  1. I am glad for commenting to let you know what a helpful experience my friend’s girl enjoyed reading through your webblog. She even learned many pieces, not to mention how it is like to possess a marvelous giving style to make many others completely know precisely specific hard to do subject matter. You really surpassed our desires. Thanks for offering those important, trusted, revealing and as well as easy tips about the topic to Jane.

  2. I like the helpful info you provide in your articles. I’ll bookmark your weblog and check again here regularly. I’m quite sure I will learn many new stuff right here! Best of luck for the next!

  3. Very interesting blog. A lot of blogs I see these days don’t really provide anything that I’m interested in, but I’m most definitely interested in this one. Just thought that I would post and let you know.

  4. This website online is mostly a stroll-through for all the information you needed about this and didn’t know who to ask. Glimpse here, and you’ll definitely discover it.

  5. An outstanding share! I’ve just forwarded this onto a colleague who had been doing a little homework on this. And he actually bought me lunch due to the fact that I found it for him… lol. So allow me to reword this…. Thank YOU for the meal!! But yeah, thanx for spending some time to talk about this issue here on your internet site.|

  6. fantastic points altogether, you simply gained a new reader. What may you recommend in regards to your submit that you made some days in the past? Any certain?|

发表评论

电子邮件地址不会被公开。 必填项已用*标注