malloc()/free()的实现

比眉伴天荒 2022-11-10 10:43 177阅读 0赞

malloc()/free()的实现

*  [brk()/sbrk()][brk_sbrk]
 *  [C 风格的内存分配程序][C]
 *  [一个简单的分配程序][Link 1]
 *  [参考][Link 2]

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()`系统调用， 这两个函数是[POSIX标准规定的操作系统接口][POSIX] [(头文件)][Link 3]：

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

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

*  `brk()` 函数对应linux的`sys_brk()`内核接口[(mm/mmap.c)][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区起始与结束地址

![mm_struct.png_psid_1][]

`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()时只需把那块占用块加入空闲块即可。如果前后都是空闲块，则合并，防止碎片化。

![malloc_1.png_psid_1][]

对于每一个空闲块，用一个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;

![malloc_2.png_psid_1][]

因为使用循环链表，我们使用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/][http_www.ibm.com_developerworks_cn_linux_l-memory]
 *  GLibc内存管理 - Ptmalloc2源代码分析, 华庭
 *  C语言接口与实现, 第5章讨论了一个基于malloc()和free()的安全内存管理器实现，第6章讨论了一个基于内存池的分配方法。

[brk_sbrk]: http://www.findfunaax.com/notes/file/170#note_head0
[C]: http://www.findfunaax.com/notes/file/170#note_head1
[Link 1]: http://www.findfunaax.com/notes/file/170#note_head2
[Link 2]: http://www.findfunaax.com/notes/file/170#note_head3
[POSIX]: http://learn.akae.cn/media/ch28s02.html
[Link 3]: http://linux.die.net/include/unistd.h
[mm_mmap.c]: http://stackoverflow.com/questions/997425/how-are-sbrk-brk-implemented-in-linux
[mm_struct.png_psid_1]: https://xcliua.bay.livefilestore.com/y1pYzaK_IQeDglDH-gSvRp0ug_QvuHlPjmITYeg17RZYRee3LGR6VekiGih6qebNZ3QDGabFobOjFg/mm_struct.png?psid=1
[malloc_1.png_psid_1]: https://xcliua.bay.livefilestore.com/y1pgeSdY-nfK9a6Dkh6-3_N5P0C6cU389mv-yAjv15FuOnuDTFxgqMukFXhsqKC7webgCVor5gs4NU/malloc_1.png?psid=1
[malloc_2.png_psid_1]: https://xcliua.bay.livefilestore.com/y1pNMJgX-67N-W2yrrfCw6NwRE_buHOhx9--UVbVkB5l-gJ3CCPfa8PT7KJmMB90ecYp9zqzE_0nYE/malloc_2.png?psid=1
[http_www.ibm.com_developerworks_cn_linux_l-memory]: http://www.ibm.com/developerworks/cn/linux/l-memory/