C语言自行实现malloc和free函数

2018/9/28

在C语言中，我们对于malloc和free函数可不会陌生，作为最常用的库函数之一，许多高级的功能由它们实现，但是同时许多“高级”的Bug也是因为它们产生的。

那malloc和free是如何实现的呢？这要从操作系统的内存管理说起了。

虚拟内存

虚拟内存是一种系统内存管理的方式，现代操作系统大多数都采用这种方式。

操作系统将整个内存（物理和虚拟）分割成许多小块，这些小块大小固定，叫做页（page），内存的分配就是以页为单位的。

在程序的运行过程中，对程序来说，它“占用”了所有的物理内存，但其实是操作系统“欺骗”了它：任意时刻，每个程序只有部分分页会驻留在物理内存上，剩下的未使用过的分页被保存在交换区里（交换区是操作系统在磁盘中保留的一部分区域，作为物理内存的补充），当进程试图访问当前未驻留在物理内存上的页面时，会引发页面错误中断，内核立即挂起当前进程，同时从磁盘的交换区中载入页面。

虚拟内存

从上图可以看出，一个程序所使用的内存不一定是连续的。

进程内存分布

在一个进程的虚拟内存中，各项资源的大致分布如下图（Linux/x86_32）：

进程内存分布

我们这次在图中只关心两个部分，一个是从顶向下增长的栈，另一个是从底往上增长的堆。（其他部分可以自己查一查）

C语言的程序的主体是一个一个的函数，每次调用函数，都会在创建新的栈帧，在编译器不做优化的情况下，我们在程序中直接声明的变量（不包括静态分配的变量）和其所在函数处在同一栈帧，随着函数栈帧的解构而销毁。但是写程序时经常会有函数间共享同一内存的情况出现，静态区又不方便，这时候就需要使用堆来存储数据了。

malloc和free的实现原理

一般我们是直接调用malloc和free来实现对堆内存的使用，而今天我们要做的就是自己通过对堆的管理，实现这两个函数。

首先我们需要知道，一般我们将堆内存的顶部称作"Program Break"（下文简称pb），用来标记堆内存分配的上边界；

接下来了解两个系统调用：

int brk(void *addr);
			// On  success,  brk() returns zero.  On error, -1 is returned, and errno is set to ENOMEM.

void *sbrk(intptr_t increment);
			// On success, sbrk() returns the  previous  program  break. On error, (void *) -1 is returned, and errno is set to ENOMEM.

brk()用来将pb 设置为传入的addr，成功返回0；sbrk()在linux上是基于brk()调用实现的，可以对pb进行增减操作，接受一个参数指定增减量，这里要注意他的返回值：成功返回之前的pb位置（其实就是新分配的内存的起始地址），失败返回的是-1。

在我们使用free()函数的时候，程序并不会直接改变pb从而释放掉内存，而是将这段内存记录到一个表中，以供之后再次malloc时使用。这样一是可以有效减小调用sbrk()的次数，以减小cpu资源的使用，二来需要被释放的内存不一定处于堆的顶端，直接通过sbrk释放是不现实的。

malloc的实现就相对简单，首先会在free维护的表中寻找合适的段，如果找到就调整表信息并返回合适的地址，否则调用sbrk()请求新空间。

细节设计

通过上面的分析，这两个函数的实现关键之处就是free表的维护，这里我参考glibc，使用链表实现。

malloc()

在malloc中，主要处理的就是什么时候使用sbrk()分配新空间，这里使用firstfit()来实现。要注意的：

如果在free表中找到了合适的块，需要重新调整这个块的大小（封装成resize()函数），并改变链表的信息。为了减少一个重设头部链表节点的步骤，可以将新分配出的空间放在内存块的高位置。
对于malloc(size_t size)函数，按理来说分配size大小的空间就足够了，但是想一下，调用的程序一般还会将malloc返回的地址传入free来释放，而free是无法获得关于这个空间的信息的，也就不知道如何去调整free表，所以，我们在malloc分配空间的时候，分配出比size大一点的空间，用头部来记录这块内存的长度信息，以供free获取，同时返回剩余的空间首地址。在程序中，头部只是一个sizeof(int *)大小的空间。

malloc返回的地址

free()
free函数要考虑到的，首先是链表的维护，再一个就是要处理malloc留下的对长度的记录。其中需要注意的地方：
1. 链表的节点位于内存块的头部（低地址），每次连接free的时候就将空间加入链表。
2. 传入free的参数是malloc返回的地址，也就是说这个地址前面还有一块用来记录块大小的空间。
这里容易忽视的一点，如果malloc分配的空间太小，小到不能存储链表的节点，那就不能按一般情况处理，不然会影响到其他的内存。为避免这个情况，我想到了两种解决方式：一是直接丢弃这个区块，不往链表中加入，这样虽然会造成内存泄漏，但是考虑到分配小空间的情况比较少，也算得上“将就”一种办法；另一种方法则更好一些，就是让malloc额外分配的部分的大小与链表节点大小一致，这样每个已分配的内存区块至少和链表节点一样大，这种方式虽然损失了一些空间，但是总比上一种方式好。
1. 上面的问题同样存在于resize()函数，在调整区块大小时，如果分配之后的内存无法存储一个链表节点，可以直接返回整个区块，有内存的损失，但可以接受。！！需要注意的是，如果吧整个区块返回，必须将这个节点从链表中除去！！

我们整理一下需要实现的函数：除了malloc和free以外，还需要加入新节点的add_block()、寻找合适区块的firstfit()、重设区块的resize_block()。

最终程序代码如下：

mymalloc.h

#ifndef MALLOC_H_
#define MALLOC_H_

#include <sys/types.h>

typedef struct free_block free_block, *pfree_block;
struct free_block {
    pfree_block next;
    pfree_block prev;
    size_t size;
};

typedef struct free_list free_list, *pfree_list;
struct free_list {
    pfree_block head;
    pfree_block tail;
};

void *mymalloc(size_t size);
void myfree(void *ptr);

static void add_block(pfree_block block, pfree_list list);
static void *firstfit(size_t size);
static void *resize_block(size_t need_size, pfree_block block);

#endif

mymalloc.c

#include <unistd.h>
#include <stdio.h>
#include "mymalloc.h"

static size_t SIZE_BLOCK_NODE = sizeof(free_block);

// 节点记录信息所需的空间

static free_block head = {NULL, 0};
static free_list flist = {&head, &head};

static void add_block(pfree_block block, pfree_list list)
{
    pfree_block p = list->head;
    while (p->next)
        p = p->next;

    p->next = block;
    block->prev = p;
    block->next = NULL;
}

static void *firstfit(size_t size)
    // 在free链表中找到第一个合适的空间，没有返回NULL
{
    if (flist.head->next == NULL)
        return NULL;

    pfree_block pb = flist.head;
    while (pb) {
        if (pb->size >= size)
            return pb;
        pb = pb->next;
    }
    return NULL;
}

static void *resize_block(size_t need_size, pfree_block block)
    // 改变block的大小，将剩下的部分加入链表中，
    // 返回空闲出来的空间首地址
{
    void *pret;

    if (need_size > block->size)
        return NULL;

    if (need_size >= block->size - SIZE_BLOCK_NODE)  {
            // 如果分配之后剩余的空间，不足以存储节点信息

        block->prev->next = block->next;
        block->next->prev = block->prev;
           // 从表中删除这个节点

        return (void*)block;
    }

    pret = (char*)block + (block->size - need_size) / sizeof(char);
    block->size -= need_size;
    return pret;
}

void *mymalloc(size_t size)
{
    size_t real_need = size + SIZE_BLOCK_NODE;
        // 在实际返回的空间前加入一个链表节点的大小的空间，
        // 在这个额外空间存储分配的空间大小，方便后续free操作

    void *pblock_ret = firstfit(real_need);

    if (!pblock_ret) {  // 在free表中没有找到合适的
        pblock_ret = sbrk(real_need);
            // 开辟新的堆空间

        if (pblock_ret == (void *)-1){
            // sbrk失败
            return NULL;
        }
    }
    else {
        pblock_ret = resize_block(real_need, (pfree_block)pblock_ret);
    }

    *((intptr_t*)pblock_ret) = size + SIZE_BLOCK_NODE; // 将最低的整型空间设置为空间大小
    return (pfree_block)pblock_ret + 1;  // 返回实际可用的空间
}

void myfree(void *ptr)
{
    size_t free_size;
    pfree_block pblock;

    free_size = *(intptr_t*)((pfree_block)ptr - 1);
        // 实际需要释放的内存大小
    pblock = (pfree_block)((pfree_block)ptr - 1);
        // 指向实际需要释放的位置

    pblock->next = NULL;
    pblock->size = free_size;
    add_block(pblock, &flist);
}

本文参考：《Linux&UNIX系统编程手册（上）