0%

malloc实现原理

发表于 更新于 分类于 ，

malloc 和 free的实现原理解析

https://jacktang816.github.io/post/mallocandfree/

进程地址空间

img

如上图所示在一个32位系统中，可寻址的空间大小是4G，linux系统下0-3G是用户模式，3-4G是内核模式。而在用户模式下又分为代码段、数据段、.bss段、堆、栈。

  • 代码段： 主要存放进程的可执行二进制代码，字符串字面值和只读变量（不能修改的）
  • 数据段：数据段存放已经初始化且初始值非0的全局变量和局部静态变量
  • bss段：存放未初始化或初始值为0的全局变量和局部静态变量
  • 堆：存放由用户动态分配内存存储的变量；
  • 栈：主要存储局部变量、函数参数、返回地址等

bss段、数据段和代码段是可执行程序编译时的分段，运行时还需要栈和堆。将应用程序加载到内存空间执行时，操作系统负责代码段、数据段和bss段的加载，并在内存中为这些段分配空间。栈也由操作系统分配和管理，堆则是由程序员自己管理。

为什么要区分 .bss段 和 数据段？ .data段存放的是已经初始化的且非0的全局或局部变量，因此这个初始化的值会保存在可执行文件中，而.bss段中是未初始化的，因此编译的时候只是记录了该段需要的空间大小，在执行额时候才会给.bss段中的数据分配内存。这样可以减少生成的可执行文件的大小。而对于字面值常量，显示是和代码一样的不可修改的常量值，所以放在代码段。

内存映射段(mmap) 内核将硬盘文件的内容直接映射到内存，任何应用程序都可通过 Linux 的 mmap() 系统调用请求这种映射。

  • 内存映射是一种方便高效的文件 I/O 方式， 因而被用于装载动态共享库。

  • 用户也可创建匿名内存映射，该映射没有对应的文件，可用于存放程序数据。

  • mmap 映射区向下扩展，堆向上扩展，两者相对扩展，直到耗尽虚拟地址空间中的剩余区域.

进程

在Linux中进程由进程控制块(PCB)描述，用一个task_struct 数据结构表示，这个数据结构记录了所有进程信息，包括进程状态、进程调度信息、标示符、进程通信相关信息、进程连接信息、时间和定时器、文件系统信息、虚拟内存信息等.。

和 malloc密切相关的就是虚拟内存信息，定义为 struct mm_struct *mm 具体描述进程的地址空间。mm_struct结构是对整个用户空间（进程空间）的描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
///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;
};
  • start_brk 和 brk 分别是堆的起始和终止地址。堆的大小由start_brk 和brk决定。
    • 可以使用系统调用 sbrk() 或 brk() 增加 brk的值，达到增大堆空间的效果，但是系统调用代价太大，涉及到用户态和内核态的相互转换。所以，实际中系统分配较大的堆空间，进程通过malloc() 库函数在堆上进行空间动态分配，堆如果不够用 malloc 可以进行系统调用，增大brk的值。
  • start_stack是进程栈的起始地址，栈的大小是在编译时期确定的，在运行时不能改变。

malloc 只知道 start_brk 和brk之间连续可用的内存空间它可用任意分配，如果不够用了就向系统申请增大brk。后面一部分主要就malloc如何分配内存进行说明。

个人理解：每个进程都有一个4G的虚拟进程空间，但是其中很大一部分起始都没有映射到物理内存，比如堆区，不可能每个进程都同时把这么大的堆空间都分配物理内存。而是在动态申请后，真正使用了 才会分配。每个进程malloc管理的也是自己区域虚拟空间中的堆区，不同进程之间的malloc不存在交叉。

相关的系统调用

brk() 和 sbrk()

由之前的进程地址空间结构分析可以知道，要增加一个进程实际的可用堆大小，就需要将 brk 指针向高地址移动。Linux通过brk和sbrk系统调用操作break指针。两个系统调用的原型如下：

1
2
3
#include <unistd.h>
int brk(void *addr);             //将brk指针直接设置为某个地址
void *sbrk(intptr_t increment);  //将brk指针从当前位置移动increment所指定的增量 ，失败返回-1

进程所面对的虚拟内存地址空间，只有按页映射到物理内存地址，才能真正使用。受物理存储容量限制，整个堆虚拟内存空间不可能全部映射到实际的物理内存。因此每个进程有一个rlimit表示当前进程可用的资源上限。这个限制可以通过getrlimit系统调用得到。

img

mmap

1
2
3
#include <sys/mman.h>
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off\_t offset);  // 向映射区申请一块内存
int munmap(void *addr, size_t length);   // 用于释放内存

mmap函数第一种用法是映射磁盘文件到内存中；而malloc使用的mmap函数的第二种用法，即匿名映射，匿名映射不映射磁盘文件，而是向映射区申请一块内存。

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

上述的只是分配了虚拟内存，还没有映射到物理内存，当访问申请的内存时，才会因为缺页异常，内核分配物理内存。

malloc实现方案

直接使用系统调用分配内存存在的问题：

  1. 由于brk/sbrk/mmap属于系统调用，如果每次申请内存，都调用这三个函数中的一个，那么每次都要产生系统调用开销（即cpu从用户态切换到内核态的上下文切换，这里要保存用户态数据，等会还要切换回用户态），这是非常影响性能的；
  2. 其次，这样申请的内存容易产生碎片，因为堆是从低地址到高地址，如果低地址的内存没有被释放，高地址的内存就不能被回收。

因此， malloc采用的是内存池的实现方式，malloc内存池实现方式更类似于STL分配器和memcached的内存池，先申请一大块内存，然后将内存分成不同大小的内存块，然后用户申请内存时，直接从内存池中选择一块相近的内存块即可。

img

image-20210407212612902

上图左边 是隐式 空闲闲链表，和上图的堆的结构对应；右边是显式空闲链表的结构，和bins(即内存池对应)。内存池保存在bins这个长128的数组中，每个元素都是一双向个链表，每个双向链表将大小接近的空闲块连接起来。

  • bins[0]目前没有使用
  • bins[1]的链表称为unsorted_list，用于维护free释放的chunk。
  • bins[2,63)的区间称为small_bins，用于维护＜512字节的内存块，其中每个元素对应的链表中的chunk大小相同，均为index*8。
  • bins[64,127)称为large_bins，用于维护>512字节的内存块，每个元素对应的链表中的chunk大小不同，index越大，链表中chunk的内存大小相差越大，例如: 下标为64的chunk大小介于[512, 512+64)，下标为95的chunk大小介于[2k+1,2k+512)。同一条链表上的chunk，按照从小到大的顺序排列。

malloc除了有unsorted bin，small bin，large bin三个bin之外，还有一个fast bin。一般的情况是，程序在运行时会经常需要申请和释放一些较小的内存空间。当分配器合并了相邻的几个小的 chunk 之后，也许马上就会有另一个小块内存的请求，这样分配器又需要从大的空闲内存中切分出一块，这样无疑是比较低效的，故而，malloc 中在分配过程中引入了 fast bins，不大于 max_fast(默认值为 64B)的 chunk 被释放后，首先会被放到 fast bins中，fast bins 中的 chunk 并不改变它的使用标志 P。这样也就无法将它们合并，当需要给用户分配的 chunk 小于或等于 max_fast 时，malloc 首先会在 fast bins 中查找相应的空闲块，然后才会去查找 bins 中的空闲 chunk。在某个特定的时候，malloc 会遍历 fast bins 中的 chunk，将相邻的空闲 chunk 进行合并，并将合并后的 chunk 加入 unsorted bin 中，然后再将 unsorted bin 里的 chunk 加入 bins 中。

unsorted bin 的队列使用 bins 数组的第一个，如果被用户释放的 chunk 大于 max_fast，或者 fast bins 中的空闲 chunk 合并后，这些 chunk 首先会被放到 unsorted bin 队列中，在进行 malloc 操作的时候，如果在 fast bins 中没有找到合适的 chunk，则malloc 会先在 unsorted bin 中查找合适的空闲 chunk，然后才查找 bins。如果 unsorted bin 不能满足分配要求。 malloc便会将 unsorted bin 中的 chunk 加入 bins 中。然后再从 bins 中继续进行查找和分配过程。从这个过程可以看出来，unsorted bin 可以看做是 bins 的一个缓冲区，增加它只是为了加快分配的速度。

综上：

malloc 内存分配流程

  1. 如果分配内存<512字节，则通过内存大小定位到smallbins对应的index上(floor(size/8))
    • 如果smallbins[index]为空，进入步骤3
    • 如果smallbins[index]非空，直接返回第一个chunk
  2. 如果分配内存>512字节，则定位到largebins对应的index上
    • 如果largebins[index]为空，进入步骤3
    • 如果largebins[index]非空，扫描链表，找到第一个大小最合适的chunk，如size=12.5K，则使用chunk B，剩下的0.5k放入unsorted_list中
  3. 遍历unsorted_list，查找合适size的chunk，如果找到则返回；否则，将这些chunk都归类放到smallbins和largebins里面
  4. index++从更大的链表中查找，直到找到合适大小的chunk为止，找到后将chunk拆分，并将剩余的加入到unsorted_list中
  5. 如果还没有找到，那么使用top chunk
  6. 或者，内存<128k，使用brk；内存>128k，使用mmap获取新内存