malloc和free底层实现原理

前言

从操作系统角度来看，进程分配内存有2种方式，分别由2个系统调用完成：brk和mmap（不考虑共享内存）。

1. brk是将数据段(.data)的最高地址指针_edata往高地址推
2. mmap是在进程的虚拟地址空间中（堆和栈中间，称为文件映射区域的地方）找一块空闲的虚拟内存。
   这两种方式分配的都是虚拟内存，没有分配物理内存。在第一次访问已分配的虚拟地址空间的时候，发生缺页中断，操作系统负责分配物理内存，然后建立虚拟内存和物理内存之间的映射关系。

malloc概述

在C语言中只能通过malloc()和其派生的函数进行动态的申请内存，而实现的根本是通过系统调用实现的（在linux下是通过sbrk()系统调用实现）。

malloc()到底从哪里得到了内存空间？答案是从堆里面获得空间。也就是说函数返回的指针是指向堆里面的一块内存。操作系统中有一个记录空闲内存地址的链表。当**操作系统收到程序的申请时，就会遍历该链表，然后就寻找第一个空间大于所申请空间的堆结点，然后就将该结点从空闲结点链表中删除，**并将该结点的空间分配给程序。

malloc()在运行期动态分配分配内存,free()释放由其分配的内存。malloc()在分配用户传入的大小的时候，还分配的一个相关的用于管理的额外内存，不过，用户是看不到的。所以，

实际的大小 = 管理空间 + 用户空间

小于128K的内存分配

malloc小于128k的内存，使用brk分配内存，将_edata往高地址推(只分配虚拟空间，不对应物理内存(因此没有初始化)，第一次读/写数据时，引起内核缺页中断，内核才分配对应的物理内存，然后虚拟地址空间建立映射关系)，如下图(32位系统)：

1. 进程启动的时候，其（虚拟）内存空间的初始布局如图1所示

其中，mmap内存映射文件是在堆和栈的中间（例如libc-2.2.93.so，其它数据文件等），为了简单起见，省略了内存映射文件。

_edata指针（glibc里面定义）指向数据段的最高地址。

2. 进程调用A=malloc(30K)以后，内存空间如图2

malloc函数会调用brk系统调用，将_edata指针往高地址推30K，就完成虚拟内存分配。

你可能会问：只要把_edata+30K就完成内存分配了？

事实是这样的，_edata+30K只是完成虚拟地址的分配，A这块内存现在还是没有物理页与之对应的，等到进程第一次读写A这块内存的时候，发生缺页中断，这个时候，内核才分配A这块内存对应的物理页。也就是说，如果用malloc分配了A这块内容，然后从来不访问它，那么，A对应的物理页是不会被分配的。

大于128K的内存分配

malloc大于128k的内存，使用mmap分配内存，在堆和栈之间找一块空闲内存分配(对应独立内存，而且初始化为0)，如下图：

4. 进程调用C=malloc(200K)以后，内存空间如图4：

5. 默认情况下，malloc函数分配内存，如果请求内存大于128K（可由M_MMAP_THRESHOLD选项调节），那就不是去推_edata指针了，而是利用mmap系统调用，从堆和栈的中间分配一块虚拟内存。这样子做主要是因为:brk分配的内存需要等到高地址内存释放以后才能释放（例如，在B释放之前，A是不可能释放的，这就是内存碎片产生的原因，什么时候紧缩看下面），而mmap分配的内存可以单独释放。

分配虚拟内存的细节

malloc()在运行期动态分配分配内存,free()释放由其分配的内存。malloc()在分配用户传入的大小的时候，还分配的一个相关的用于管理的额外内存，不过，用户是看不到的。所以，

实际的大小 = 管理空间 + 用户空间

在64位系统中，malloc(0)的有效内存大小为24，32位中为12,准确的说是至少是这么多，并且这些内存是可以用的

结果为

此外，堆中的内存块总是成块分配的，并不是申请多少字节，就拿出多少个字节的内存来提供使用。堆中内存块的大小通常与内存对齐有关（8Byte(for 32bit system)或16Byte(for 64bit system)。

因此，在64位系统下，当(申请内存大小+sizeof(struct mem_control_block) )% 16 == 0的时候，刚好可以完成一次满额的分配，但是当其!=0的时候，就会多分配内存块。

在linux系统下面一个程序的堆的管理是通过内存块进行管理的，也就是将堆分成了很多大小不一的内存块。这些块怎么管理尼，比如怎么查询块的大小，怎么查询块是否正在被程序使用，怎么知道这个块的地址。为了解决内存块的管理所以要设计一个管理内存块的数据结构，详细的数据结构如下：

/**内存控制块数据结构，用于管理所有的内存块
* is_available: 标志着该块是否可用。1表示可用，0表示不可用
* size: 该块的大小
**/
struct mem_control_block {
    int is_available;
    int size;
};

有了管理内存块的数据结构，那么在内存中堆的组织形式也好理解了，也就是堆是由很多内存块组成的，所以有了如下的示意图：

综合上面的知识，可以很容易想到malloc()实现的大体思路。首先挨个检查堆中的内存是否可用，如果可用那么大小是否能满足需求，要是都满足的话就直接用。当遍历了堆中的所有内存块时，要是没有能满足需求的块时就只能通过系统调用向操作系统申请新的内存，然后将新的内存添加到堆中。思路很简单，malloc()实现流程图如下所示：

看完上面的思路，也会很容易的想到free()函数的实现思路，只要将内存管理块设置为可用就可以了。这样下次调用malloc()函数的时候就可以将该内存块作为可分配块再次进行分配了。

最后，贴上malloc()和free()实现的代码：

malloc()实现：

/**内存控制块数据结构，用于管理所有的内存块
* is_available: 标志着该块是否可用。1表示可用，0表示不可用
* size: 该块的大小
**/
struct mem_control_block {
    int is_available;
    int size;
};

/**在实现malloc时要用到linux下的全局变量
*managed_memory_start：该指针指向进程的堆底，也就是堆中的第一个内存块
*last_valid_address：该指针指向进程的堆顶，也就是堆中最后一个内存块的末地址
**/
void *managed_memory_start;
void *last_valid_address;

/**malloc()功能是动态的分配一块满足参数要求的内存块
*numbytes：该参数表明要申请多大的内存空间
*返回值：函数执行结束后将返回满足参数要求的内存块首地址，要是没有分配成功则返回NULL
**/
void *malloc(size_t numbytes) {
    //游标，指向当前的内存块
    void *current_location;
    //保存当前内存块的内存控制结构
    struct mem_control_block *current_location_mcb;
    //保存满足条件的内存块的地址用于函数返回
    void *memory_location;
    memory_location = NULL;
    //计算内存块的实际大小，也就是函数参数指定的大小+内存控制块的大小
    numbytes = numbytes + sizeof(struct mem_control_block);
    //利用全局变量得到堆中的第一个内存块的地址
    current_location = managed_memory_start;

    //对堆中的内存块进行遍历，找合适的内存块
    while (current_location != last_valid_address) //检查是否遍历到堆顶了
    {
        //取得当前内存块的内存控制结构
        current_location_mcb = (struct mem_control_block*)current_location;
        //判断该块是否可用
        if (current_location_mcb->is_available)
            //检查该块大小是否满足
            if (current_location_mcb->size >= numbytes)
            {
                //满足的块将其标志为不可用
                current_location_mcb->is_available = 0;
                //得到该块的地址，结束遍历
                memory_location = current_location;
                break;
            }
        //取得下一个内存块
        current_location = current_location + current_location_mcb->size;
    }

    //在堆中已有的内存块中没有找到满足条件的内存块时执行下面的函数
    if (!memory_location)
    {
        //向操作系统申请新的内存块
        if (sbrk(numbytes) == -1)
            return NULL;//申请失败，说明系统没有可用内存
        memory_location = last_valid_address;
        last_valid_address = last_valid_address + numbytes;
        current_location_mcb = (struct mem_control_block)memory_location;
        current_location_mcb->is_available = 0;
        current_location_mcb->size = numbytes;
    }
    //到此已经得到所要的内存块，现在要做的是越过内存控制块返回内存块的首地址
    memory_location = memory_location + sizeof(struct mem_control_block);
    return memory_location;
}

free实现：

/**free()功能是将参数指向的内存块进行释放
*firstbyte：要释放的内存块首地址
*返回值：空
**/
void free(void *firstbyte)
{
    struct mem_control_block *mcb;
    //取得该块的内存控制块的首地址
    mcb = firstbyte - sizeof(struct mem_control_block);
    //将该块标志设为可用
    mcb->is_available = 1;
    return;
}

缺页中断

用ps -o majflt,minflt -C program命令查看缺页中断的次数。

majflt代表majorfault，中文名叫大错误，minflt代表minor fault，中文名叫小错误。

这2个数值表示一个进程自启动以来所发生的缺页中断的次数。

发生缺页中断后，执行了哪些操作？

当一个进程发生缺页中断的时候，进程会陷入内核态，执行以下操作：

1. 检查要访问的虚拟地址是否合法

2. 查找/分配一个物理页

3. 填充物理页内容（读取磁盘，或者直接置0，或者啥也不干）

4. 建立映射关系（虚拟地址到物理地址）

5. 重新执行发生缺页中断的那条指令

如果第3步，需要读取磁盘，那么这次缺页中断就是majflt，否则就是minflt。