malloc()/free()的实现
目录

malloc()/free()是C语言标准库中的内存分配函数。

C标准库中与内存分配相关的函数还有:

#include <stdlib.h>
void *malloc(size_t size);
void *calloc(size_t nobj, size_t size);
void *realloc(void *ptr, size_t new_size);
void free(void *p);

brk()/sbrk()

glibc中的malloc()实现是使用brk()sbrk()系统调用(最新的glibc使用mmap()实现malloc), 这两个函数是POSIX标准规定的操作系统接口 (头文件)

#include <unistd.h>
int brk(void *end_data_segment);
void *sbrk(ptrdiff_t increment);

这些函数也由glibc来实现调用内核接口

  • brk() 函数对应linux的sys_brk()内核接口(mm/mmap.c)
  • sbrk() 没有对应的内核接口,只是进一步封装了brk(),由glibc实现。

每个进程的进程描述符task_struct有一个字段指向当前进程的内存描述符mm_struct,保存了当前进程的内存使用情况。mm_struct的各个字段中:

  • start_code, end_code: 代码段的开始与结束地址
  • start_data, end_data: 数据段的开始与结束地址
  • start_stack: stack区起始地址
  • start_brk, brk: heap区起始与结束地址

brk()的作用就是改变mm_struct中brk字段的值,成功返回0,失败返回-1并置errno。

sbrk()的作用就是以当前brk字段为起始做偏移,参数increment可以是正数或负数,成功返回之前的地址,失败返回-1。

由此可见,对于内核来说,每个进程的heap区就是一段连续虚拟地址的内存。 因为系统调用的代价,进程不可能每次新建heap区变量都要向操作系统申请。 并且因为是连续的内存区域,琐碎的变量很难调整和释放。 因此,进程申请一块内存区域后,自己负责管理分配和释放,和内核无关了(只在heap空间不够时再使用系统调用调整heap区大小)。 这就是内存管理器所做的事。

内存管理器有很多类型,典型的有:

  • C风格内存分配程序
  • 池式内存管理
  • 引用计数
  • 垃圾收集

这里使用的是C风格的内存分配程序

C 风格的内存分配程序

C语言内存管理器就是这种类型,通过malloc()/free()向用户提供heap区内存使用。 但是malloc()的实现有很多,这些实现各有优点与缺点。在设计一个分配程序时, 要面临许多需要折衷的选择,其中包括:

  • 分配的速度。
  • 回收的速度。
  • 有线程的环境的行为。
  • 内存将要被用光时的行为。
  • 局部缓存。
  • 簿记(Bookkeeping)内存开销。
  • 虚拟内存环境中的行为。
  • 小的或者大的对象。
  • 实时保证。

比较著名的C内存管理实现有:

  • Doug lea Malloc: Goug Lea的实现,glibc和ptmalloc
  • BSD Malloc: FreeBSD中的实现
  • Hoard
  • TCMalloc: google开源工具箱 google-perftools中的成员

一个简单的分配程序

这里了解一个简单的实现,在K&R C的8.7节。

基本思想是首先通过brk()/sbrk()获得一块heap区域组成一个空闲块。 接下来对于每一次malloc()申请,通过first fit算法找到符合的空闲块, 把用户需要的大小返还给用户,剩余的空间再组成新的空闲块。 经过多次malloc()/free()之后,heap区域应该是空闲块和占用块相间隔。 然后把这些空闲块通过循环链表free list链接起来以便查找。 如果没找到合适的空闲块,则再次通过brk()/sbrk()新申请heap区域,并把新区域单独做一块放到链表中。 最后,free()时只需把那块占用块加入空闲块即可。如果前后都是空闲块,则合并,防止碎片化。

对于每一个空闲块,用一个header保存其大小和链表中的信息:

struct {                      // block header
union header *ptr;        // next block if on free list
unsigned size;            // size of this block
} s;

这里有一个问题,涉及到地址对齐。 malloc()必须返回能够存储变量的地址,即变量大小的整数倍的地址。 因此这里把占用空间最大的基本类型(大部分是double)的大小作为对齐标准。

typedef double Align;

union header {
struct {
union header *ptr;
unsigned size;
} s;
Align x;
};

typedef union header Header;

因为使用循环链表,我们使用base保存链表的起始,使用freep保存当前空闲块指针。 这样每次查找空闲块时从freep开始,而不是从base开始,使得分散的分配内存块。 这样,malloc纯粹就是链表操作了:

static Header base;                       // empty list to get started
static Header *freep = NULL;              // start of free list

void *malloc(size_t nbytes) {
Header *p, *prevp;
unsigned nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;

if ((prevp = freep) == NULL) {
base.s.ptr = freep = prevp = &base;
base.s.size = 0;
}

for (p = prevp->s.ptr ;; prevp = p, p = p->s.ptr) {
if (p->size >= nunits) {          // big enough
if (p->s.size == nunits)
prevp->s.ptr = p->s.ptr;
else {                        // allocate tail end
p->size -= nunits;
p += p->s.size;
p->s.size = nunits;
}
freep = prevp;
return (void*)(p+1);
}

if (p == freep)                  // wrapped around free list
if ((p = morecore(nunits)) == NULL)
return NULL;
}
}

上面一段代码中的morecore()函数通过系统调用获得更大的内存空间。 为了防止每次morecore()都要申请空间,这里设置一个申请空间大小的下限NALLOC。

#define NALLOC 1024        // minimum #units to request

static Header *morecore(unsigned nu){
char *cp;
Header *up;

if (nu < NALLOC)
nu = NALLOC;
cp = sbrk(nu * sizeof(Header));
if (cp == (char*)-1)   // check
return NULL;
up = (Header*) cp;
up->s.size = nu;
free((void*)(up+1));
return freep;
}


free()把释放的块放入空闲链表,并合并前后空闲的块:

void free(void *ap)
{
Header *bp, *p;
bp = (Header *)ap - 1; /* point to block header */
for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
break; /* freed block at start or end of arena */

if (bp + bp->size == p->s.ptr) { /* join to upper nbr */
bp->s.size += p->s.ptr->s.size;
bp->s.ptr = p->s.ptr->s.ptr;
} else
bp->s.ptr = p->s.ptr;
if (p + p->size == bp) { /* join to lower nbr */
p->s.size += bp->s.size;
p->s.ptr = bp->s.ptr;
} else
p->s.ptr = bp;
freep = p;
}

这样一个简单的内存分配器就实现了。 当然这个内存分配器还有很多问题,比如内存归还操作系统、线程安全、碎片问题等。

还有两类实现方法:

  1. 基于位图(Bitmap)实现的方法,把堆划分成大量块(block),分配相邻的块。
  2. 对象池方法,分配固定对象大小的池。

如果继续研究这方面,就可以看Glibc中内存管理的实现。 Glibc基本思想是:

  1. 小于64B: 采用对象池
  2. 大于64B小于512B:最佳折中策略
  3. 大于512B小于128KB:最佳适配算法
  4. 大于128KB,mmap映射一块区域给用户

参考

  • http://www.ibm.com/developerworks/cn/linux/l-memory/
  • GLibc内存管理 - Ptmalloc2源代码分析, 华庭
  • C语言接口与实现, 第5章讨论了一个基于malloc()和free()的安全内存管理器实现,第6章讨论了一个基于内存池的分配方法。
master 于 2013-10-26 19:45 时评论:
很好,大神能做朋友吗

发表评论