LYL's Blog
0%

操作系统之malloc底层原理

发表于 分类于 ，
本文字数： 3.4k 阅读时长 ≈ 3 分钟

先来了解一些背景知识。

进程地址空间的组成：

  1. 内核空间：这块区域包含两种数据，一种是对每个进程都一样的数据，如共享的内核代码和全局数据结构。另一种是每个进程都不一样的数据，如页表、内核在进程上下文中执行代码时使用的栈，以及记录该进程虚拟地址空间当前组织状态的各种数据结构。
  2. BSS（Block Started by Symbol）通常是指用来存放程序中未初始化的全局变量和静态变量的一块内存区域。是可读写的。在程序执行之前BSS段会自动清0。所以，未初始的全局变量在程序执行之前已经成0了）。
  3. 数据段（data segment）通常是指用来存放程序中已初始化的全局变量的一块内存区域。数据段属于静态内存分配。
  4. 代码段（code segment/text segment）通常是指用来存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定，并且内存区域通常属于只读, 某些架构也允许代码段为可写，即允许修改程序。在代码段中，也有可能包含一些只读的常数变量，例如字符串常量等。
  5. 堆（heap）是用于存放进程运行中被动态分配的内存段，它的大小并不固定，可动态扩张或缩减。当进程调用malloc函数分配内存时，新分配的内存就被动态添加到堆上（堆被扩张）；当利用free函数释放内存时，被释放的内存从堆中被释放（堆被缩减） 。
  6. 栈（stack）又称堆栈， 是用户存放程序临时创建的局部变量，也就是说我们函数块中定义的变量（但不包括static声明的变量，static意味着在数据段中存放变量）。除此以外，在函数被调用时，其参数也会被压入发起调用的栈中，并且待到调用结束后，函数的返回值也会被存放回栈中。由于栈的后进先出特点，所以栈特别方便用来保存/恢复调用现场。从这个意义上讲，我们可以把堆栈看成一个寄存、交换临时数据的内存区。
  7. 内存映射区：这块虚拟内存区域被映射到任何需要的对象身上，如共享库文件、磁盘上的普通文件和将要介绍的通过malloc分配的大块内存区域（大于128K）。

注意这些区域实际上存在于进程的虚拟地址空间上，一开始并没有被装载到物理内存上，比如说bss段，理论上是被初始化为零值，但并不是说在物理内存区域的对应段被填入零值，实际上，是将其映射到了零页，等到CPU向这块区域内写数据时，通过引发缺页故障的形式，才被装载到物理内存，分配到初始化为零的页（所谓的写时复制）。

进程虚拟内存布局图

操作系统提供的两个系统调用函数：

1
2
3
4
#include <unistd.h>
#include <sys/mman.h>
void* sbrk(intptr_t incr);
void* mmap(void* start, size_t length, int prot, int flags, int fd, off_t offset);

sbrk函数的作用是移动brk指针扩展heap的上界。函数的参数指示brk指针移动的大小，返回申请之前的brk地址。注意申请的内存地址中的值是随机的，即不要求为零。

mmap函数第一种用法是映射磁盘文件到内存中；而malloc使用的mmap函数的第二种用法，即匿名映射，匿名映射不映射磁盘文件，而是向映射区申请一块全零页内存，相应的虚拟页面是被初始化为零的。

如上面的进程虚拟内存布局图所示，mmap对应Memory Mapping Segment，brk对应Heap。start_brk是堆段的开始位置，brk(program break)则是堆段的结束位置。

下面开始介绍malloc的实现原理。

那么，既然brk/mmap提供了内存分配的功能，直接使用brk/mmap进行内存管理不是更简单吗，为什么需要malloc呢？

我们知道，系统调用本身会产生软中断，导致程序从用户态陷入内核态，比较消耗资源。试想，如果频繁分配回收小块内存区，那么将有很大的性能耗费在系统调用中。因此，为了减少系统调用带来的性能损耗，malloc采用了内存池的设计，增加了一个代理层，每次内存分配，都优先从内存池中寻找，如果内存池中无法提供，再向操作系统申请。

当申请小于128K内存时，malloc使用sbrk分配内存，当申请大于128K内存时，使用mmap函数申请内存。

下面主要讨论对于小块内存的申请malloc所采用的内存池设计方案。分配器不但要管理已分配的内存块，还需要管理空闲的内存块。malloc利用chunk结构体来管理这些内存块，内存池就是由许多不同大小的chunk链表组成的。

img

内存池保存在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_chunk来描述这些块：

1
2
3
4
5
6
7
8
9
10
11
12
struct malloc_chunk
{  
    INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free).  */  
    INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */  

    struct malloc_chunk* fd; /* double links -- used only if free. */  
    struct malloc_chunk* bk;  

    /* Only used for large blocks: pointer to next larger size.  */  
    struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */  
    struct malloc_chunk* bk_nextsize;
};

img

glibc在内存池中查找合适的chunk时，采用了最佳适应的伙伴算法。举例如下：

  1. 如果分配内存< 512字节，则通过内存大小定位到smallbins对应的index上。
    • 如果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。

top chunk
如下图示: top chunk是堆顶的chunk，堆顶指针brk位于top chunk的顶部。移动brk指针，即可扩充top chunk的大小。

img

free释放内存时，有两种情况：

  1. chunk和top chunk相邻，则和top chunk合并。
  2. chunk和top chunk不相邻，则直接插入到unsorted_list中。

参考链接：

  1. glibc内存管理那些事儿 - 简书

  2. Understanding glibc malloc – sploitF-U-N

  3. 自己实现一个简单的malloc可参考

  4. [译] malloc中的系统调用brk和mmap | yoko blog。

  5. [malloc的底层实现（ptmalloc）_牛客博客