2. 分段
1. 分段概述

(资料图片)
前面介绍了分页内存管理，可以说通过多级页表，TLB 等，分页内存管理方法已经相当不错了。那么分页有什么缺点呢？
共享困难：通过共享页面来实现共享当然是可以的。这里的问题在于我们要保证页面上只包含可以共享的内容并不是一件容易的事儿，因为进程空间是直接映射到页面上的。这样一个页面上很可能包含不能共享的内容（比如既包含代码又包含数据，代码可以共享，而数据不能共享）。早期的 PDP-11 实现的一种解决方法是为指令和数据设置分离的地址空间，分别称为 I 空间和 D 空间（其实这已经和分段很像了）。
程序地址空间受限于虚拟地址：我们将程序全部映射到一个统一的虚拟地址的问题在于不好扩张。不如我们程序的地址按先代码放在一起，然后把数据放在一起，然后再放 XXX，这样其中某一部分的空间扩张起来都会影响到相邻的空间，非常不方便。
上面的问题一个比较直观的解决方法是提供多个独立的地址空间，也就是段（segment）。每个段的长度视具体的段不同而不同，而且是可以在运行期动态改变的。因为每个段都构成了一个独立的地址空间，所以它们可以独立的增长或者减小而不会影响到其他的段。如果一个段比较大，把它整个保存到内存中可能很不方便甚至是不可能的，因此可以对段采用分页管理，只有那些真正需要的页面才会被调入内存。
采用分段和分页结合的方式管理内存，一个地址由两个部分组成：段和段内陆址。段内陆址又进一步分为页号和页偏移。在进行内存访问时，过程如下：
根据段号找到段描述符（存放段基址）。
检查该段的页表是否在内存中。如果在，则找到它的位置，如果不在，则产生段错误。
检查所请求的虚拟页面的页表项，如果该页面不在内存中则产生缺页中断，如果在内存中就从页表项中取出这个页面在内存中的起始地址。
将页面起始地址和偏移量进行拼接得到物理地址，然后完成读写。
2. 进程的段
每个 Linux 程序都有一个运行时内存映像，也就是各个段的布局，简单如下图所示。
注意上图只是一个相对位置图，实际上这些段并不是相邻的。主要的段包括只读代码段、读写段、运行时堆、用户栈。在分配栈、堆段运行时地址的时候，链接器会使用空间地址空间布局随机化（ASLR），但是相对位置不会变。上图中 .data 等是对应进程中的不同数据的 section ，或者叫做节。简介如下。
.text: 已编译程序的机器代码。
.rodata: 只读数据。
.data: 已初始化的全局和静态变量。局部变量保存在栈上。
.bss: 未初始化的全局和静态变量，以及所有被初始化为 0 的全局或者静态变量。在目标文件中这个节不占据实际的空间，它仅仅是一个占位符。
3. malloc 实现
1. 堆内存管理
我们常说的 malloc 函数是 glibc 提供的库函数。glibc 的内存管理使用的方法是 ptmalloc，除此之后还有很多其他内存管理方案，比如 tcmalloc （golang 使用的就是 tcmalloc）。
ptmalloc 对于申请内存小于 128KB 时，分配是在堆段，使用系统调用 brk() 或者 sbrk()。如果大于 128 KB 的话，分配在映射区，使用系统调用 mmap()。
2. brk, sbrk
在堆段申请的话，使用系统调用 brk 或者 sbrk。
int brk(const void *addr);void *sbrk(intptr_t incr);
brk 将 brk 指针放置到指定地址处，成功返回 0，否则返回 -1。sbrk 将 brk 指针向后移动指定字节，返回依赖于系统实现，或者返回移动前的 brk 位置，或者返回移动后的 brk 位置。下面使用 sbrk 实现一个巨简单的 malloc。
void *malloc(size_t size) {    void *p = sbrk(0);    void *request = sbrk(size);    if (request == (void*) -1) {        return NULL; // sbrk failed.    } else {        assert(p == request); // Not thread safe.        return p;    }}
3. mmap
linux 系统调用 mmap 将一个文件或者其它对象映射进内存。
#include void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
mmap 的 flags 可选多种参数，当选择 MAP_ANONYMOUS 时，不需要传入文件描述符，malloc 使用的就是 MAP_ANONYMOUS 模式。mmap 申请的内存在操作系统的映射区。比如 32 位系统，映射区从 3G 虚拟地址粗向下生长，但是因为程序的其他段也会占用空间（比如代码段必须以特定的地址开始），所以并不能申请 3G 的大小。
4. malloc 和物理内存有关系吗？
可以说没关系，malloc 申请的地址是线性地址，申请的时候并没有进行映射。访问到的时候触发缺页异常，这个时候才会进行物理地址映射。
5. ptmalloc
Malloc实现原理：
因为brk、sbrk、mmap都属于系统调用，若每次申请内存，都调用这三个，那么每次都会产生系统调用，影响性能；其次，这样申请的内存容易产生碎片，因为堆是从低地址到高地址，如果高地址的内存没有被释放，低地址的内存就不能被回收。
所以malloc采用的是内存池的管理方式（ptmalloc），Ptmalloc 采用边界标记法将内存划分成很多块，从而对内存的分配与回收进行管理。为了内存分配函数malloc的高效性，ptmalloc会预先向操作系统申请一块内存供用户使用，当我们申请和释放内存的时候，ptmalloc会将这些内存管理起来，并通过一些策略来判断是否将其回收给操作系统。这样做的最大好处就是，使用户申请和释放内存的时候更加高效，避免产生过多的内存碎片。
chunk 内存块的基本组织单元
在 ptmalloc 的实现源码中定义结构体 malloc_chunk 来描述这些块。malloc_chunk 定义如下：
1.struct malloc_chunk {  2.  INTERNAL_SIZE_T      prev_size;    /* Size of previous chunk (if free).  */  3.  INTERNAL_SIZE_T      size;         /* Size in bytes, including overhead. */  4.  5.  struct malloc_chunk* fd;           /* double links -- used only if free. */  6.  struct malloc_chunk* bk;  7.  8.  /* Only used for large blocks: pointer to next larger size.  */  9.  struct malloc_chunk* fd_nextsize;      /* double links -- used only if free. */  10.  struct malloc_chunk* bk_nextsize; 11.};
chunk 的定义相当简单明了，对各个域做一下简单介绍 :
prev_size: 如果前一个 chunk 是空闲的，该域表示前一个 chunk 的大小，如果前一个 chunk 不空闲，该域无意义。
size ：当前 chunk 的大小，并且记录了当前 chunk 和前一个 chunk 的一些属性，包括前一个 chunk 是否在使用中，当前 chunk 是否是通过 mmap 获得的内存，当前 chunk 是否属于非主分配区。
fd 和 bk ：指针 fd 和 bk 只有当该 chunk 块空闲时才存在，其作用是用于将对应的空闲 chunk 块加入到空闲chunk 块链表中统一管理，如果该 chunk 块被分配给应用程序使用，那么这两个指针也就没有用（该 chunk 块已经从空闲链中拆出）了，所以也当作应用程序的使用空间，而不至于浪费。
fd_nextsize 和 bk_nextsize: 当当前的 chunk 存在于 large bins 中时， large bins 中的空闲 chunk 是按照大小排序的，但同一个大小的 chunk 可能有多个，增加了这两个字段可以加快遍历空闲 chunk ，并查找满足需要的空闲 chunk ， fd_nextsize 指向下一个比当前 chunk 大小大的第一个空闲 chunk ， bk_nextszie 指向前一个比当前 chunk 大小小的第一个空闲 chunk 。如果该 chunk 块被分配给应用程序使用，那么这两个指针也就没有用（该chunk 块已经从 size 链中拆出）了，所以也当作应用程序的使用空间，而不至于浪费。
chunk的结构
chunk的结构可以分为使用中的chunk和空闲的chunk。使用中的chunk和空闲的chunk数据结构基本项同，但是会有一些设计上的小技巧，巧妙的节省了内存。
使用中的chunk：
说明：
1、 chunk指针指向chunk开始的地址；mem指针指向用户内存块开始的地址。
2、 p=0时，表示前一个chunk为空闲，prev_size才有效
3、p=1时，表示前一个chunk正在使用，prev_size无效 p主要用于内存块的合并操作；ptmalloc 分配的第一个块总是将p设为1, 以防止程序引用到不存在的区域
4、M=1 为mmap映射区域分配；M=0为heap区域分配
5、 A=0 为主分配区分配；A=1 为非主分配区分配。
空闲的chunk：
说明：
1、当chunk空闲时，其M状态是不存在的，只有AP状态，
２、原本是用户数据区的地方存储了四个指针，
指针fd指向后一个空闲的chunk,而bk指向前一个空闲的chunk，malloc通过这两个指针将大小相近的chunk连成一个双向链表。
在large bin中的空闲chunk，还有两个指针，fd_nextsize和bk_nextsize，用于加快在large bin中查找最近匹配的空闲chunk。不同的chunk链表又是通过bins或者fastbins来组织的。
空闲链表bins
当用户使用free函数释放掉的内存，ptmalloc并不会马上交还给操作系统，而是被ptmalloc本身的空闲链表bins管理起来了，这样当下次进程需要malloc一块内存的时候，ptmalloc就会从空闲的bins上寻找一块合适大小的内存块分配给用户使用。这样的好处可以避免频繁的系统调用，降低内存分配的开销。
malloc将相似大小的chunk用双向链表链接起来，这样一个链表被称为一个bin。ptmalloc一共维护了128bin。每个bins都维护了大小相近的双向链表的chunk。基于chunk的大小，有下列几种可用bins：
1、Fast bin
2、Unsorted bin
3、Small bin
4、Large bin　
保存这些bin的数据结构为：
fastbinsY：这个数组用以保存fast bins。
bins：这个数组用以保存unsorted、small以及large bins，共计可容纳126个：
当用户调用malloc的时候，能很快找到用户需要分配的内存大小是否在维护的bin上，如果在某一个bin上，就可以通过双向链表去查找合适的chunk内存块给用户使用。
1. fast bins。
程序在运行时会经常需要申请和释放一些较小的内存空间。当分配器合并了相邻的几个小的 chunk 之后,也许马上就会有另一个小块内存的请求,这样分配器又需要从大的空闲内存中切分出一块,这样无疑是比较低效的,故而,malloc 中在分配过程中引入了 fast bins,
fast bins是bins的高速缓冲区，大约有10个定长队列。每个fast bin都记录着一条free chunk的单链表（称为binlist ，采用单链表是出于fast bin中链表中部的chunk不会被摘除的特点），增删chunk都发生在链表的前端。fast bins 记录着大小以8字节递增的bin链表。
当用户释放一块不大于max_fast（默认值64B）的chunk的时候，会默认会被放到fast bins上。当需要给用户分配的 chunk 小于或等于 max_fast 时,malloc 首先会到fast bins上寻找是否有合适的chunk，
除非特定情况，两个毗连的空闲chunk并不会被合并成一个空闲chunk。不合并可能会导致碎片化问题，但是却可以大大加速释放的过程！
分配时，binlist中被检索的第一个chunk将被摘除并返回给用户。free掉的chunk将被添加在索引到的binlist的前端。
2. unsorted bin。
unsorted bin 的队列使用 bins 数组的第一个，是bins的一个缓冲区，加快分配的速度。当用户释放的内存大于max_fast或者fast bins合并后的chunk都会首先进入unsorted bin上。chunk大小 – 无尺寸限制，任何大小chunk都可以添加进这里。这种途径给予 "glibc malloc’ 第二次机会以重新使用最近free掉的chunk，这样寻找合适bin的时间开销就被抹掉了，因此内存的分配和释放会更快一些。
用户malloc时，如果在 fast bins 中没有找到合适的 chunk,则malloc 会先在 unsorted bin 中查找合适的空闲 chunk，如果没有合适的bin，ptmalloc会将unsorted bin上的chunk放入bins上，然后到bins上查找合适的空闲chunk。
3. small bins
大小小于512字节的chunk被称为small chunk，而保存small chunks的bin被称为small bin。数组从2开始编号，前64个bin为small bins，small bin每个bin之间相差8个字节，同一个small bin中的chunk具有相同大小。
每个small bin都包括一个空闲区块的双向循环链表（也称binlist）。free掉的chunk添加在链表的前端，而所需chunk则从链表后端摘除。
两个毗连的空闲chunk会被合并成一个空闲chunk。合并消除了碎片化的影响但是减慢了free的速度。
分配时，当samll bin非空后，相应的bin会摘除binlist中最后一个chunk并返回给用户。在free一个chunk的时候，检查其前或其后的chunk是否空闲，若是则合并，也即把它们从所属的链表中摘除并合并成一个新的chunk，新chunk会添加在unsorted bin链表的前端。
4.large bins
大小大于等于512字节的chunk被称为large chunk，而保存large chunks的bin被称为large bin，位于small bins后面。large bins中的每一个bin分别包含了一个给定范围内的chunk，其中的chunk按大小递减排序，大小相同则按照最近使用时间排列。
两个毗连的空闲chunk会被合并成一个空闲chunk。
分配时，遵循原则“smallest-first , best-fit”,从顶部遍历到底部以找到一个大小最接近用户需求的chunk。一旦找到，相应chunk就会分成两块User chunk（用户请求大小）返回给用户。
Remainder chunk（剩余大小添加到unsorted bin。free时和small bin 类似。
并不是所有chunk都按照上面的方式来组织，有三种列外情况。top chunk，mmaped chunk 和last remainder chunk
1. Top chunk
top chunk相当于分配区的顶部空闲内存，当bins上都不能满足内存分配要求的时候，就会来top chunk上分配。
当top chunk大小比用户所请求大小还大的时候，top chunk会分为两个部分：User chunk（用户请求大小）和Remainder chunk（剩余大小）。其中Remainder chunk成为新的top chunk。
当top chunk大小小于用户所请求的大小时，top chunk就通过sbrk（main arena）或mmap（thread arena）系统调用来扩容。
2. mmaped chunk
当分配的内存非常大（大于分配阀值，默认128K）的时候，需要被mmap映射，则会放到mmaped chunk上，当释放mmaped chunk上的内存的时候会直接交还给操作系统。
3、Last remainder chunk
Last remainder chunk是另外一种特殊的chunk，就像top chunk和mmaped chunk一样，不会在任何bins中找到这种chunk。当需要分配一个small chunk,但在small bins中找不到合适的chunk，如果last remainder chunk的大小大于所需要的small chunk大小，last remainder chunk被分裂成两个chunk，其中一个chunk返回给用户，另一个chunk变成新的last remainder chunk。
sbrk与mmap
在堆区中， start_brk 指向 heap 的开始，而 brk 指向 heap 的顶部。可以使用系统调用 brk()和 sbrk()来增 加标识 heap 顶部的 brk 值，从而线性的增加分配给用户的 heap 空间。在使 malloc 之前，brk 的值等于 start_brk，也就是说 heap 大小为 0。
ptmalloc 在开始时，若请求的空间小于 mmap 分配阈值（mmap threshold，默认值为 128KB）时，主分配区会调用 sbrk()增加一块大小为 (128 KB + chunk_size) align 4KB 的空间作为 heap。非主分配区会调用 mmap 映射一块大小为 HEAP_MAX_SIZE（32 位系统上默认为 1MB，64 位系统上默认为 64MB）的空间作为 sub-heap。这就是前面所说的 ptmalloc 所维护的分配空间;　　　
当用户请求内存分配时，首先会在这个区域内找一块合适的 chunk 给用户。当用户释放了 heap 中的 chunk 时，ptmalloc 又会使用 fastbins 和 bins 来组织空闲 chunk。以备用户的下一次分配。
若需要分配的 chunk 大小小于 mmap分配阈值，而 heap 空间又不够，则此时主分配区会通过 sbrk()调用来增加 heap 大小，非主分配区会调用 mmap 映射一块新的 sub-heap，也就是增加 top chunk 的大小，每次 heap 增加的值都会对齐到 4KB。当用户的请求超过 mmap 分配阈值，并且主分配区使用 sbrk()分配失败的时候，或是非主分配区在 top chunk 中不能分配到需要的内存时，ptmalloc 会尝试使用 mmap()直接映射一块内存到进程内存空间。使用 mmap()直接映射的 chunk 在释放时直接解除映射，而不再属于进程的内存空间。任何对该内存的访问都会产生段错误。而在 heap 中或是 sub-heap 中分配的空间则可能会留在进程内存空间内，还可以再次引用（当然是很危险的）。
内存分配malloc流程
获取分配区的锁，防止多线程冲突。
计算出实际需要分配的内存的chunk实际大小。
判断chunk的大小，如果小于max_fast（64Ｂ），则尝试去fast bins上取适合的chunk，如果有则分配结束。否则，下一步；
判断chunk大小是否小于512B，如果是，则从small bins上去查找chunk，如果有合适的，则分配结束。否则下一步；
ptmalloc首先会遍历fast bins中的chunk，将相邻的chunk进行合并，并链接到unsorted bin中然后遍历 unsorted bins。如果unsorted bins上只有一个chunk并且大于待分配的chunk，则进行切割，并且剩余的chunk继续扔回unsorted bins；如果unsorted bins上有大小和待分配chunk相等的，则返回，并从unsorted bins删除；如果unsorted bins中的某一chunk大小 属于small bins的范围，则放入small bins的头部；如果unsorted bins中的某一chunk大小 属于large bins的范围，则找到合适的位置放入。若未分配成功，转入下一步；
从large bins中查找找到合适的chunk之后，然后进行切割，一部分分配给用户，剩下的放入unsorted bin中。
如果搜索fast bins和bins都没有找到合适的chunk，那么就需要操作top chunk来进行分配了
当top chunk大小比用户所请求大小还大的时候，top chunk会分为两个部分：User chunk（用户请求大小）和Remainder chunk（剩余大小）。其中Remainder chunk成为新的top chunk。
当top chunk大小小于用户所请求的大小时，top chunk就通过sbrk（main arena）或mmap（thread arena）系统调用来扩容。
到了这一步，说明 top chunk 也不能满足分配要求，所以，于是就有了两个选择: 如 果是主分配区，调用 sbrk()，增加 top chunk 大小；如果是非主分配区，调用 mmap 来分配一个新的 sub-heap，增加 top chunk 大小；或者使用 mmap()来直接分配。在 这里，需要依靠 chunk 的大小来决定到底使用哪种方法。判断所需分配的 chunk 大小是否大于等于 mmap 分配阈值，如果是的话，则转下一步，调用 mmap 分配， 否则跳到第 10 步，增加 top chunk 的大小。
使用 mmap 系统调用为程序的内存空间映射一块 chunk_size align 4kB 大小的空间。然后将内存指针返回给用户。
判断是否为第一次调用 malloc，若是主分配区，则需要进行一次初始化工作，分配 一块大小为(chunk_size + 128KB) align 4KB 大小的空间作为初始的 heap。若已经初 始化过了，主分配区则调用 sbrk()增加 heap 空间，分主分配区则在 top chunk 中切 割出一个 chunk，使之满足分配需求，并将内存指针返回给用户。
简而言之：获取分配区(arena)并加锁–> fast bin –> unsorted bin –> small bin –> large bin –> top chunk –> 扩展堆
内存回收流程
获取分配区的锁，保证线程安全。
如果free的是空指针，则返回，什么都不做。
判断当前chunk是否是mmap映射区域映射的内存，如果是，则直接munmap()释放这块内存。前面的已使用chunk的数据结构中，我们可以看到有M来标识是否是mmap映射的内存。
判断chunk是否与top chunk相邻，如果相邻，则直接和top chunk合并（和top chunk相邻相当于和分配区中的空闲内存块相邻）。转到步骤8
如果chunk的大小大于max_fast（64b），则放入unsorted bin，并且检查是否有合并，有合并情况并且和top chunk相邻，则转到步骤8；没有合并情况则free。
如果chunk的大小小于 max_fast（64b），则直接放入fast bin，fast bin并没有改变chunk的状态。没有合并情况，则free；有合并情况，转到步骤7
在fast bin，如果当前chunk的下一个chunk也是空闲的，则将这两个chunk合并，放入unsorted bin上面。合并后的大小如果大于64B，会触发进行fast bins的合并操作，fast bins中的chunk将被遍历，并与相邻的空闲chunk进行合并，合并后的chunk会被放到unsorted bin中，fast bin会变为空。合并后的chunk和topchunk相邻，则会合并到topchunk中。转到步骤8
判断top chunk的大小是否大于mmap收缩阈值（默认为128KB），如果是的话，对于主分配区，则会试图归还top chunk中的一部分给操作系统。free结束。
使用注意事项
为了避免Glibc内存暴增，需要注意：
1. 后分配的内存先释放，因为ptmalloc收缩内存是从top chunk开始，如果与top chunk相邻的chunk不能释放，top chunk以下的chunk都无法释放。
2. Ptmalloc不适合用于管理长生命周期的内存，特别是持续不定期分配和释放长生命周期的内存，这将导致ptmalloc内存暴增。
3. 不要关闭 ptmalloc 的 mmap 分配阈值动态调整机制，因为这种机制保证了短生命周期的 内存分配尽量从 ptmalloc 缓存的内存 chunk 中分配，更高效，浪费更少的内存。
4. 多线程分阶段执行的程序不适合用ptmalloc，这种程序的内存更适合用内存池管理
5. 尽量减少程序的线程数量和避免频繁分配/释放内存。频繁分配，会导致锁的竞争，最终导致非主分配区增加，内存碎片增高，并且性能降低。
6. 防止内存泄露，ptmalloc对内存泄露是相当敏感的，根据它的内存收缩机制，如果与top chunk相邻的那个chunk没有回收，将导致top chunk一下很多的空闲内存都无法返回给操作系统。
7. 防止程序分配过多的内存，或是由于glibc内存暴增，导致系统内存耗尽，程序因为OOM被系统杀掉。预估程序可以使用的最大物理内存的大小，配置系统的/proc/sys/vm/overcommit_memory ,/proc/sys/vm/overcommit_ratio,以及使用ulimit -v限制程序能使用的虚拟内存的大小，防止程序因OOM被杀死掉。

关键词：