一、内存分区

在探讨malloc和free如何操作内存之前，首先要明白内存分区：

在csapp这本书中，就将内存分为了代码段（text），data，bss以及堆和栈区，每个段的存放的数据如图所示：

其中最主要的栈区存放的是局部变量。

堆是动态内存分配的区域，malloc和new分配的内存就是在这个区域。

二、malloc的内存从何而来

由于虚拟内存的存在，每个进程都好像是独占用户空间的。内核除了管理自身的内存之外，也需要管理用户空间里进程的内存，这个内存又叫做进程地址空间。

在32位系统中，可寻址的范围是4g，在linux系统当中，内核占1g（3-4g），用户空间占3g（0-3g）。

在linux系统当中，内核使用进程描述符结构体来表示进程地址空间。 该结构包括了和进程地址空间有关的全部信息。

内存描述符由mm_struct结构体表示，，如下所示:

///include/linux/sched.h 

struct mm_struct {
  struct vm_area_struct * mmap;  /* 指向虚拟区间（VMA）链表 */
  rb_root_t mm_rb;         /*指向red_black树*/
  struct vm_area_struct * mmap_cache;     /* 指向最近找到的虚拟区间*/
  pgd_t * pgd;             /*指向进程的页目录*/
  atomic_t mm_users;                   /* 用户空间中的有多少用户*/                                     
  atomic_t mm_count;               /* 对"struct mm_struct"有多少引用*/                                     
  int map_count;                        /* 虚拟区间的个数*/
  struct rw_semaphore mmap_sem;
  spinlock_t page_table_lock;        /* 保护任务页表和 mm->rss */       
  struct list_head mmlist;            /*所有活动（active）mm的链表 */
  unsigned long start_code, end_code, start_data, end_data; /* 代码段、数据段 起始地址和结束地址 */
  unsigned long start_brk, brk, start_stack; /* 栈区 的起始地址，堆区 起始地址和结束地址 */
  unsigned long arg_start, arg_end, env_start, env_end; /*命令行参数 和 环境变量的 起始地址和结束地址*/
  unsigned long rss, total_vm, locked_vm;
  unsigned long def_flags;
  unsigned long cpu_vm_mask;
  unsigned long swap_address;

  unsigned dumpable:1;
  /* Architecture-specific MM context */
  mm_context_t context;
};

具体每个成员的含义可以查阅《Linux内核设计与实现》第15章。

内存映射

mmap内存段的的作用就是：内核将硬盘上的数据直接映射到内存，任何应用程序都可以通过系统调用mmap()函数来实现这种映射。

其中，start_brk和brk分别是堆的起始位置和终止位置，而我们用malloc和new分配内存的时候，就是在这段内存区域上进行的。 堆的大小是确定的，但是如果不够用的话，也可以通过系统调用brk()来增加堆的空间，但是这样做是有代价的，因为涉及到用户态和内核态的状态切换。

相关系统调用

1、mmap()

函数原型：

mmap这个函数我觉得大家应该再熟悉不过了，无论是许欸小网络编程还是操作系统还是Linux内核的时候，都会遇到他。通过mmap和read函数还可以实现零拷贝技术。 mmap（）有两种映射方法，可以将硬盘上的文件映射到内存上去，也可以创建匿名映射。

malloc采用的是匿名映射。 匿名映射就是不映射文件，而是直接向映射区mmap区申请一块内存。

malloc分配小内存的话，调用sbrk系统调用，分配大内存的话，就直接使用mmap系统调用直接映射！！！！

注意，malloc分配内存之后，只是分配了虚拟内存，还没有映射到物理内存，只有当访问申请的内存的时候，才会发生缺页中断，分配对应的物理内存！！！

• 分配内存 < DEFAULT_MMAP_THRESHOLD，走__brk，从内存池获取，失败的话走brk系统调用
• 分配内存 > DEFAULT_MMAP_THRESHOLD，走__mmap，直接调用mmap系统调用

DEFAULT_MMAP_THRESHOLD默认是128k，当然也可以调整。

2、brk()和sbrk()

前面提到过，如果堆空间不够，就可以调用这两个系统调用函数来对堆的空间进行扩大。mallloc申请内存的时候也可以调用这两个函数。 函数原型如下：

brk（）是直接设定堆的终止地址的指针，把brk指针设置为addr。而sbrk则是设置brk指针的增量为increment。

三、malloc实现方案

如果每次申请内存都要调用mmap（）或者brk系统调用的话，那么开销是很大的，因为系统调用涉及到用户态和内核态的上下文切换。 而且这么做还容易产生内存碎片。

所以，malloc还采用了另一种机制来实现内存分配：内存池。（突然想插一句，我发现计算机在为了避免由频繁创建某个东西或者频繁调用某个函数所带来的额外开销的时候，经常采用的一种方法就是“池”，为了避免频繁创建进程线程，所以有了线程池进程池，为了避免频繁分配内存，于是有了内存池，真的很巧妙）

话说回来，内存池保存在长度为128的bins数组当中，每个bin维护一个双向链表，双向链表中是一个个的chunk。如下图：

• bin[1]被称为unsorted_list，用于维护free释放的chunk。

• bins[2,63) 的区间称为small_bins ，用于维护小于512字节的内存块。而且每个bin上面的chunk大小是相等的，为8*index。

• bins[64,127)称为large_bins，用于维护>512字节的内存块，每个元素对应的链表中的chunk大小不同，index越大，链表中chunk的内存大小相差越大，例如: 下标为64的chunk大小介于[512, 512+64)，下标为95的chunk大小介于[2k+1,2k+512)。同一条链表上的chunk，按照从小到大的顺序排列。

malloc将相似大小的chunk组织起来，这样的一个双链表称为bin。

在分配内存的时候，我们经常可能要经常分配或者合并很多个较小的内存空间。那么如果分配器合并了较小的chunk，那我们再malloc的话，就会又要重新分配，这样做就很低效。

事实上，malloc还有一个fast_bin。不大于max_fast的chunk被释放之后，我们首先把他加入到fastbin里面去，然后后面再需要分配内存的时候，就先从fastbin里面找。

如果free掉的内存大于max_fast或者fastbin的chunk合并之后（没错也是要定期合并的），就会先把这个内存放到unsorted_bin中去，

所以，malloc在分配内存的时候，先是去fastbin里去找，找不到再去unsortedbin里去找，最后再找不到再去其他bin里面去找。

由此可见，unsorted_bin可以看作是一个bins的缓冲区，因为根据局部性原理，经常用到的内存块大小可能差不多，所以每次寻找先去缓冲区找，加快分配速度。

当所申请的内存很大的时候，fastbin和bins都不能满足要求的时候，这个时候malloc就会直接在mmap区域建立内存映射，直接把页映射到进程地址空间中去，这样一来，free的时候直接解除映射就可以。

总结一下，malloc分配内存流程：

malloc 内存分配流程

1. 遍历fast_bins

2. 遍历unsorted_list，查找合适size的chunk，如果找到则返回；否则，将这些chunk都归类放到smallbins和largebins里面

3. 如果分配内存<512字节，则通过内存大小定位到smallbins对应的index上(floor(size/8))

   • 如果smallbins[index]为空，进入步骤3
   • 如果smallbins[index]非空，直接返回第一个chunk

4. 如果分配内存>512字节，则定位到largebins对应的index上

   • 如果largebins[index]为空，进入步骤3
   • 如果largebins[index]非空，扫描链表，找到第一个大小最合适的chunk，如size=12.5K，则使用chunk B，剩下的0.5k放入unsorted_list中

5. index++从更大的链表中查找，直到找到合适大小的chunk为止，找到后将chunk拆分，并将剩余的加入到unsorted_list中

6. 或者，内存<128k，使用brk；内存>128k，使用mmap获取新内存