malloc、free的底层实现

前言

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

• brk是将数据段(.data)的最高地址指针_edata
• mmap是在进程的虚拟地址空间中（堆和栈中间，称为文件映射区域的地方）找一块空闲的虚拟内存。

这两种方式分配的都是虚拟内存，没有分配物理内存。在

malloc概述

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

malloc()到底从哪里得到了内存空间？答案是从堆里面获得空间。也就是说函数返回的指针是指向堆里面的一块内存。操作系统中有一个记录空闲内存地址的链表。当。

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

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

小于128K的内存分配

，如下图(32位系统)：

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

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

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

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

   malloc函数会，就完成虚拟内存分配。

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

事实是这样的，_edata+30K只是完成虚拟地址的分配，，等到进程。也就是说，。

大于128K的内存分配

malloc大于128k的内存，，如下图：

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

2. 默认情况下，malloc函数分配内存，如果请求内存大于128K（），那就不是去推_edata指针了，而是利用mmap系统调用，从堆和栈的中间分配一块虚拟内存。这样子做主要是因为：

分配虚拟内存的细节

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

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

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

此外，，并不是申请多少字节，就拿出多少个字节的内存来提供使用。（8Byte(for 32bit system)或16Byte(for 64bit system)。

因此，。

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

综合上面的知识，可以很容易想到malloc()实现的大体思路。。思路很简单，malloc()实现流程图如下所示：

看完上面的思路，也会很容易的想到。这样下次调用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。