|
（一）综述 内存管理不外乎三个层面，用户程序层，C运行时库层，内核层。如下图所示：
allocator 正是值C运行时库的内存管理模块, 它响应用户的分配请求, 向内核申请内存, 然后将其返回给用户程序。为了保持高效的分配, allocator 一般都会预先分配一块大于用户请求的内存, 并通过某种算法管理这块内存. 来满足用户的内存分配要求, 用户 free 掉的内存也并不是立即就返回给操作系统, 相反, allocator 会管理这些被 free 掉的空闲空间, 以应对用户以后的内存分配要求. 也就是说, allocator 不但要管理已分配的内存块, 还需要管理空闲的内存块, 当响应用户分配要求时, allocator 会首先在空闲空间中寻找一块合适的内存给用户, 在空闲空间中找不到的情况下才分配一块新的内存。 1. Linux进程内存布局Linux 系统在装载 elf 格式的程序文件时，会调用 loader 把可执行文件中的各个段依次载入到从某一地址开始的空间中(载入地址取决 link editor(ld)和机器地址位数，在 32 位机 器上是 0x8048000，即 128M 处)。如下图所示： 以 32 位机器为例，首先被载入的是.text 段， 然后是.data 段，最后是.bss 段。这可以看作是程序的开始空间。程序所能访问的最后的地 址是 0xbfffffff，也就是到 3G 地址处，3G 以上的 1G 空间是内核使用的，应用程序不可以直接访问。 应用程序的堆栈从最高地址处开始向下生长，.bss 段与堆栈之间的空间是空闲的， 空闲空间被分成两部分，一部分为 heap，一部分为 mmap 映射区域，mmap 映射区域一般 从 TASK_SIZE/3 的地方开始，但在不同的 Linux 内核和机器上，mmap 区域的开始位置一般是 不同的。Heap 和 mmap 区域都可以供用户自由使用，但是它在刚开始的时候并没有映射到 内存空间内，是不可访问的。在向内核请求分配该空间之前，对这个空间的访问会导致 segmentation fault。用户程序可以直接使用系统调用来管理 heap 和 mmap 映射区域，但更 多的时候程序都是使用 C 语言提供的 malloc()和 free()函数来动态的分配和释放内存。Stack 区域是唯一不需要映射，用户却可以访问的内存区域，这也是利用堆栈溢出进行攻击的基础。 上图这种布局是 Linux 内核 2.6.7 以前的默认进程内存布局形式，mmap 区域与栈区域相对增 长，这意味着堆只有 1GB 的虚拟地址空间可以使用，继续增长就会进入 mmap 映射区域， 这显然不是我们想要的。这是由于 32 模式地址空间限制造成的，所以内核引入了另一种虚 拟地址空间的布局形式，将在后面介绍。但对于 64 位系统，提供了巨大的虚拟地址空间， 这种布局就相当好。Linux内核2.6.7之后，进程的内存布局如下图所示： 从上图可以看到，栈至顶向下扩展，并且栈是有界的。堆至底向上扩展，mmap 映射区 域至顶向下扩展，mmap 映射区域和堆相对扩展，直至耗尽虚拟地址空间中的剩余区域，这种结构便于 C 运行时库使用 mmap 映射区域和堆进行内存分配。上图的布局形式是在内核 2.6.7 以后才引入的，这是 32 位模式下进程的默认内存布局形式。 在 64 位模式下各个区域的起始位置是什么呢?对于 AMD64 系统，内存布局采用经典 内存布局，text 的起始地址为 0x0000000000400000，堆紧接着 BSS 段向上增长，mmap 映射 区域开始位置一般设为 TASK_SIZE/3。 #define TASK_SIZE_MAX ((1UL << 47) - PAGE_SIZE) #define TASK_SIZE (test_thread_flag(TIF_IA32) ? IA32_PAGE_OFFSET : TASK_SIZE_MAX) #define STACK_TOP TASK_SIZE #define TASK_UNMAPPED_BASE (PAGE_ALIGN(TASK_SIZE/3)) 计算一下可知，mmap 的开始区域地址为 0x00002AAAAAAAA000，栈顶地址为0x00007FFFFFFFF000，下图为64位的进程内存布局： 上图是 X86_64 下 Linux 进程的默认内存布局形式，这只是一个示意图，当前内核默认 配置下，进程的栈和 mmap 映射区域并不是从一个固定地址开始，并且每次启动时的值都 不一样，这是程序在启动时随机改变这些值的设置，使得使用缓冲区溢出进行攻击更加困难。 当然也可以让进程的栈和 mmap 映射区域从一个固定位置开始，只需要设置全局变量 randomize_va_space 值为 0，这个变量默认值为 1。用户可以通过设置 /proc/sys/kernel/randomize_va_space 来停用该特性，也可以用如下命令: sudo sysctl -w kernel.randomize_va_space=0 2、为什么要限制栈的大小2.1 进程栈 进程栈的初始化大小是由编译器和链接器计算出来的，但是栈的实时大小并不是固定的，Linux 内核会根据入栈情况对栈区进行动态增长（其实也就是添加新的页表）。但是并不是说栈区可以无限增长，它也有最大限制 RLIMIT_STACK (一般为 8M)，我们可以通过 ulimit 2.2 线程栈从 Linux 内核的角度来说，其实它并没有线程的概念。Linux 把所有线程都当做进程来实现，它将线程和进程不加区分的统一到了 task_struct 中。线程仅仅被视为一个与其他进程共享某些资源的进程，而是否共享地址空间几乎是进程和 Linux 中所谓线程的唯一区别。线程创建的时候，加上了 CLONE_VM 标记，这样 线程的内存描述符 将直接指向 父进程的内存描述符。虽然线程的地址空间和进程一样，但是对待其地址空间的 stack 还是有些区别的。对于 Linux 进程或者说主线程，其 stack 是在 fork 的时候生成的，实际上就是复制了父亲的 stack 空间地址，然后写时拷贝 (cow) 以及动态增长。然而对于主线程生成的子线程而言，其 stack 将不再是这样的了，而是事先固定下来的，创建线程时使用 mmap 系统调用给线程分配栈，线程栈的起始地址跟大小保存在pthread_attr_t。 栈需要存储在连续的内存位置。这意味着不能根据需要随机分配栈，但至少需要为此保留虚拟地址。保留的虚拟地址空间越大，可以执行的线程就创建的越少。用于例如，32位应用程序通常具有2GB的虚拟地址空间。这意味着如果栈大小是2MB（在pthreads中是默认值），那么最多可以创建1024个线程。对于诸如web服务器之类的应用程序来说，这可能很小。将栈大小增加到100MB（即保留100MB，但不一定立即将100MB分配给栈）会将线程数限制在20个左右，即使对于简单的GUI应用程序也是如此。一个有趣的问题是，为什么我们在64位平台上仍有此限制。我不知道答案，但我假设人们已经习惯了一些“堆栈最佳实践”：小心在栈上分配巨大的对象，如果需要，手动增加栈大小。因此，没有人发现在64位平台上添加“巨大”栈支持是有用的。 3. 操作系统内存布局相关函数上节提到 heap 和 mmap 映射区域是可以提供给用户程序使用的虚拟内存空间，如何获 得该区域的内存呢?操作系统提供了相关的系统调用来完成相关工作。对 heap 的操作，操 作系统提供了 brk()函数，C 运行时库提供了 sbrk()函数;对 mmap 映射区域的操作，操作系 统提供了 mmap()和 munmap()函数。sbrk()，brk() 或者 mmap() 都可以用来向我们的进程添 加额外的虚拟内存。Glibc 同样是使用这些函数向操作系统申请虚拟内存。 这里要提到一个很重要的概念，内存的延迟分配，只有在真正访问一个地址的时候才建 立这个地址的物理映射，这是 Linux 内存管理的基本思想之一。Linux 内核在用户申请内存的 时候，只是给它分配了一个线性区(也就是虚拟内存)，并没有分配实际物理内存;只有当 用户使用这块内存的时候，内核才会分配具体的物理页面给用户，这时候才占用宝贵的物理 内存。内核释放物理页面是通过释放线性区，找到其所对应的物理页面，将其全部释放的过程。 3.1 Heap 操作相关函数Heap 操作函数主要有两个，brk()为系统调用，sbrk()为 C 库函数。系统调用通常提供一种最小功能，而库函数通常提供比较复杂的功能。Glibc 的 malloc 函数族(realloc，calloc 等) 就调用 sbrk()函数将数据段的下界移动，sbrk()函数在内核的管理下将虚拟地址空间映射到内 存，供 malloc()函数使用。内核数据结构 mm_struct 中:
C 语言的动态内存分配基本函数是 malloc()，在 Linux 上的实现是通过内核的 brk 系统调用。brk()是一个非常简单的系统调用， 只是简单地改变 mm_struct 结构的成员变量 brk 的值。这两个函数的定义如下: #include <unistd.h> int brk(void *addr); void *sbrk(intptr_t increment); 需要说明的是，但 sbrk()的参数 increment 为 0 时，sbrk()返回的是进程的当前 brk值， increment 为正数时扩展 brk 值，当 increment 为负值时收缩 brk 值。 3.2 Mmap 映射区域操作相关函数mmap()函数将一个文件或者其它对象映射进内存。文件被映射到多个页上，如果文件的 大小不是所有页的大小之和，最后一个页不被使用的空间将会清零。munmap 执行相反的操 作，删除特定地址区域的对象映射。函数的定义如下: #include <sys/mman.h> void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset); // 若映射成功则返回映射区的内存起始地址，否则返回MAP_FAILED(－1)，错误原因存于errno 中。 int munmap(void *addr, size_t length); 参数:
4. 内存管理方法4.1. C 风格的内存管理程序C 风格的内存管理程序主要实现 malloc()和 free()函数。内存管理程序主要通过调用 brk() 或者 mmap()进程添加额外的虚拟内存。Doug Lea Malloc，ptmalloc，BSD malloc，Hoard， TCMalloc都属于这一类内存管理程序。 基于 malloc()的内存管理器仍然有很多缺点，不管使用的是哪个分配程序。对于那些需 要保持长期存储的程序使用 malloc()来管理内存可能会非常令人失望。如果有大量的不固定 的内存引用，经常难以知道它们何时被释放。生存期局限于当前函数的内存非常容易管理， 但是对于生存期超出该范围的内存来说，管理内存则困难得多。因为管理内存的问题，很多 程序倾向于使用它们自己的内存管理规则。 4.2. 池式内存管理内存池是一种半内存管理方法。内存池帮助某些程序进行自动内存管理，这些程序会经历一些特定的阶段，而且每个阶段中都有分配给进程的特定阶段的内存。例如，很多网络服务器进程都会分配很多针对每个连接的内存——内存的最大生存期限为当前连接的存在期。 Apache 使用了池式内存(pooled memory)，将其连接拆分为各个阶段，每个阶段都有自己 的内存池。在结束每个阶段时，会一次释放所有内存。 在池式内存管理中，每次内存分配都会指定内存池，从中分配内存。每个内存池都有不同的生存期限。在 Apache 中，有一个持续时间为服务器存在期的内存池，还有一个持续时 间为连接的存在期的内存池，以及一个持续时间为请求的存在期的池，另外还有其他一些内 存池。因此，如果我的一系列函数不会生成比连接持续时间更长的数据，那么我就可以完全 从连接池中分配内存，并知道在连接结束时，这些内存会被自动释放。另外，有一些实现允 许注册清除函数(cleanup functions)，在清除内存池之前，恰好可以调用它，来完成在内存 被清理前需要完成的其他所有任务(类似于面向对象中的析构函数)。 使用池式内存分配的优点如下所示:
池式内存的缺点是:
4.3. 引用计数在引用计数中，所有共享的数据结构都有一个域来包含当前活动“引用”结构的次数。 当向一个程序传递一个指向某个数据结构指针时，该程序会将引用计数增加 1。实质上，是在告诉数据结构，它正在被存储在多少个位置上。然后，当进程完成对它的使用后，该程序就会将引用计数减少 1。结束这个动作之后，它还会检查计数是否已经减到零。如果是，那么它将释放内存。 在 Java，Perl 等高级语言中，进行内存管理时使用引用计数非常广泛。在这些语言中， 引用计数由语言自动地处理，所以您根本不必担心它，除非要编写扩展模块。由于所有内容都必须进行引用计数，所以这会对速度产生一些影响，但它极大地提高了编程的安全性和方便性。 以下是引用计数的好处:
它也有其不足之处:
4.4. 垃圾收集垃圾收集(Garbage collection)是全自动地检测并移除不再使用的数据对象。垃圾收集器通常会在当可用内存减少到少于一个具体的阈值时运行。通常，它们以程序所知的可用的 一组“基本”数据——栈数据、全局变量、寄存器——作为出发点。然后它们尝试去追踪通 过这些数据连接到每一块数据。收集器找到的都是有用的数据;它没有找到的就是垃圾，可 以被销毁并重新使用这些无用的数据。为了有效地管理内存，很多类型的垃圾收集器都需要 知道数据结构内部指针的规划，所以，为了正确运行垃圾收集器，它们必须是语言本身的一 部分。 垃圾收集的一些优点:
其缺点包括:
5. 常见的C内存管理程序
Doug Lea Malloc 实际上是完整的一组分配程序，其中包括 Doug Lea的原始分配程序、GNU libc 分配程序和 ptmalloc。Doug Lea 的分配程序加入了索引， 这使得搜索速度更快，并且可以将多个没有被使用的块组合为一个大的块。它还支 持缓存，以便更快地再次使用最近释放的内存。ptmalloc 是 Doug Lea Malloc 的一个 扩展版本，支持多线程。
BSD Malloc 是随 4.2 BSD 发行的实现，包含在 FreeBSD 之中，这个分配 程序可以从预先确实大小的对象构成的池中分配对象。它有一些用于对象大小的 size 类，这些对象的大小为 2 的若干次幂减去某一常数。所以，如果您请求给定大 小的一个对象，它就简单地分配一个与之匹配的 size 类。这样就提供了一个快速的 实现，但是可能会浪费内存。
编写 Hoard 的目标是使内存分配在多线程环境中进行得非常快。因此，它的 构造以锁的使用为中心，从而使所有进程不必等待分配内存。它可以显著地加快那 些进行很多分配和回收的多线程进程的速度。
tcmalloc是Google开发的内存分配器，在Golang、Chrome中都有使用该分配器进行内存分配。有效的优化了ptmalloc中存在的问题。当然为此也付出了一些代价，按下不表，先看tcmalloc的具体实现。
jemalloc是facebook推出的，目前在firefox、facebook服务器、android 5.0 等服务中大量使用。 jemalloc最大的优势还是其强大的多核/多线程分配能力. 以现代计算机硬件架构来说, 最大的瓶颈已经不再是内存容量或cpu速度, 而是多核/多线程下的lock contention(锁竞争). 因为无论CPU核心数量如何多, 通常情况下内存只有一份. 可以说, 如果内存足够大, CPU的核心数量越多, 程序线程数越多, jemalloc的分配速度越快。
性能对比图如下：
最左边的就是glibc的malloc，最右边的就是jemalloc。从图表上可以看出，jemalloc的性能有glibc的两倍以上。非常压倒性的性能差异。因此，使用了jemalloc的应用程序自然会快很多。Jemalloc旁边的就是tcmalloc。Tcmalloc的性能与其相差甚微，低jemalloc2.1.0慢4.5%。图上和tcmalloc的1.4版本，而现在已经到2.1版本，因此实际上这两者应该是不相仲伯的。Jemalloc的创始人jason evans也意识到这一点，说在cpu core 8以上的计算机上jemalloc效率更高。 1. ptmalloc简介Linux 中 malloc 的早期版本是由 Doug Lea 实现的，它有一个重要问题就是在并行处理时 多个线程共享进程的内存空间，各线程可能并发请求内存，在这种情况下应该如何保证分配 和回收的正确和高效。Wolfram Gloger 在 Doug Lea 的基础上改进使得 Glibc 的 malloc 可以支 持多线程——ptmalloc，在 glibc-2.3.x.中已经集成了 ptmalloc2，这就是我们平时使用的 malloc， 目前 ptmalloc 的最新版本 ptmalloc3。ptmalloc2 的性能略微比 ptmalloc3 要高一点点。 ptmalloc 实现了 malloc()，free()以及一组其它的函数. 以提供动态内存管理的支持。分 配器处在用户程序和内核之间，它响应用户的分配请求，向操作系统申请内存，然后将其返 回给用户程序，为了保持高效的分配，分配器一般都会预先分配一块大于用户请求的内存， 并通过某种算法管理这块内存。来满足用户的内存分配要求，用户释放掉的内存也并不是立 即就返回给操作系统，相反，分配器会管理这些被释放掉的空闲空间，以应对用户以后的内 存分配要求。也就是说，分配器不但要管理已分配的内存块，还需要管理空闲的内存块，当 响应用户分配要求时，分配器会首先在空闲空间中寻找一块合适的内存给用户，在空闲空间 中找不到的情况下才分配一块新的内存。为实现一个高效的分配器，需要考虑很多的因素。 比如，分配器本身管理内存块所占用的内存空间必须很小，分配算法必须要足够的快。 2. 内存管理数据结构2.1 主分配区与非主分配区在 Doug Lea 实现的内存分配器中只有一个主分配区(main arena)，每次分配内存都必须对主分配区加锁，分配完成后释放锁，在 SMP 多线程环境下，对主分配区的锁的争用很激烈，严重影响了 malloc 的分配效率。 于是 Wolfram Gloger 在 Doug Lea 的基础上改进使得 Glibc 的 malloc 可以支持多线程，增加了非主分配区(non main arena)支持，主分配区与非 主分配区用环形链表进行管理。每一个分配区利用互斥锁(mutex)使线程对于该分配区的访问互斥，主分配区和非主分配区如下图所示：
（1）每个进程只有一个主分配区，但可能存在多个非主分配区； （2）ptmalloc 根据系统对分配区的争用情况动态增加非主分配区的数量，分配区的数量一旦增加，就不会再减少了； （3）主分配区可以访问进程的 heap 区域和 mmap 映射区域，也就是说主分配区可以使用 sbrk 和 mmap 向操作系统申请虚拟内存，而非主分配区只能访问进程的 mmap 映射区域； （4）非主分配区每次使用 mmap()向操作系统“批发”HEAP_MAX_SIZE(32 位系统上默认为 1MB，64 位系统默 认为 64MB)大小的虚拟内存，当用户向非主分配区请求分配内存时再切割成小块“零售” 出去，毕竟系统调用是相对低效的，直接从用户空间分配内存快多了。所以 ptmalloc 在必要的情况下才会调用 mmap()函数向操作系统申请虚拟内存。 （5）主分配区可以访问 heap 区域，如果用户不调用 brk()或是 sbrk()函数，分配程序就可以保证分配到连续的虚拟地址空间，因为每个进程只有一个主分配区使用 sbrk()分配 heap 区 域的虚拟内存。内核对 brk 的实现可以看着是 mmap 的一个精简版，相对高效一些； （6）如果主分配区的内存是通过 mmap()向系统分配的，当 free 该内存时，主分配区会直接调用 munmap() 将该内存归还给系统； （7）当某一线程需要调用 malloc()分配内存空间时，该线程先查看线程私有变量中是否已经存在一个分配区，如果存在，尝试对该分配区加锁，如果加锁成功，使用该分配区分配内存， 如果失败，该线程搜索循环链表试图获得一个没有加锁的分配区。如果所有的分配区都已经加锁，那么 malloc()会开辟一个新的分配区，把该分配区加入到全局分配区循环链表并加锁， 然后使用该分配区进行分配内存操作。 （8）在释放操作中，线程同样试图获得待释放内存块所在分配区的锁，如果该分配区正在被别的线程使用，则需要等待直到其他线程释放该分配区的互斥锁之后才可以进行释放操作。 申请小块内存时会产生很多内存碎片，ptmalloc 在整理时也需要对分配区做加锁操作。 每个加锁操作大概需要 5~10 个 cpu 指令，而且程序线程很多的情况下，锁等待的时间就会延长，导致 malloc 性能下降。一次加锁操作需要消耗 100ns 左右，正是锁的缘故，导致 ptmalloc 在多线程竞争情况下性能远远落后于 tcmalloc。最新版的 ptmalloc 对锁进行了优化，加入了 PER_THREAD 和 ATOMIC_FASTBINS 优化，但默认编译不会启用该优化，这两个对锁的优化应该能够提升多线程内存的分配的效率。 2.2 chunk的组织不管内存是在哪里被分配的，用什么方法分配，用户请求分配的空间在 ptmalloc 中都使用一个 chunk 来表示。用户调用 free()函数释放掉的内存也并不是立即就归还给操作系统， 相反，它们也会被表示为一个 chunk，ptmalloc 使用特定的数据结构来管理这些空闲的 chunk。 （1）Chunk 格式 ptmalloc 在给用户分配的空间的前后加上了一些控制信息，用这样的方法来记录分配的信息，以便完成分配和释放工作。一个使用中的 chunk(使用中，就是指还没有被 free 掉) 在内存中的样子如图所示: 在图中，chunk 指针指向一个 chunk 的开始，一个 chunk 中包含了用户请求的内存区域和相关的控制信息。图中的 mem 指针才是真正返回给用户的内存指针。
空闲 chunk 在内存中的结构如图所示: 当 chunk 空闲时，其 M 状态不存在，只有 AP 状态，原本是用户数据区的地方存储了四 个指针，指针 fd 指向后一个空闲的 chunk，而 bk 指向前一个空闲的 chunk，ptmalloc 通过这 两个指针将大小相近的 chunk 连成一个双向链表。对于 large bin 中的空闲 chunk，还有两个 指针，fd_nextsize 和 bk_nextsize，这两个指针用于加快在 large bin 中查找最近匹配的空闲 chunk。不同的 chunk 链表又是通过 bins 或者 fastbins 来组织的。 （2）Chunk的复用 为了使得 chunk 所占用的空间最小，ptmalloc 使用了空间复用，一个 chunk 或者正在被使用，或者已经被 free 掉，所以 chunk 的中的一些域可以在使用状态和空闲状态表示不 同的意义，来达到空间复用的效果。以 32 位系统为例，空闲时，一个 chunk 中至少需要 4 个 size_t(4B)大小的空间，用来存储 prev_size，size，fd 和 bk (见上图)，也就是 16B， chunk 的大小要对齐到 8B。当一个 chunk 处于使用状态时，它的下一个 chunk 的 prev_size 域肯定是无效的。所以实际上，这个空间也可以被当前 chunk 使用。这听起来有点不可思议， 但确实是合理空间复用的例子。故而实际上，一个使用中的 chunk 的大小的计算公式应该是: in_use_size = (用户请求大小 + 8 - 4 ) align to 8B 这里加 8 是因为需要存储 prev_size 和 size， 但又因为向下一个 chunk“借”了 4B，所以要减去 4。最后，因为空闲的 chunk 和使用中的 chunk 使用的是同一块空间。所以肯定要取其中最大者作为实际的分配空间。即最终的分配空间： chunk_size = max(in_use_size, 16) 这就是当用户请求内存分配时，ptmalloc 实际需要 分配的内存大小，在后面的介绍中。如果不是特别指明的地方，指的都是这个经过转换的实际需要分配的内存大小，而不是用户请求的内存分配大小。 2.3 空闲chunk链表（1）Bins 用户 free 掉的内存并不是都会马上归还给系统，ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk，当用户进行下一次分配请求时，ptmalloc 会首先试图在空闲的 chunk 中挑选一块给用户，这样就避免了频繁的系统调用，降低了内存分配的开销。ptmalloc 将相似大小的 chunk 用双向链表链接起来，这样的一个链表被称为一个 bin。Ptmalloc 一共 维护了 128 个 bin，并使用一个数组来存储这些 bin(如下图所示)。每个bin都维护了大小相近的双向链表的chunk。基于chunk的大小，有下列几种可用bins，分别是：Unsorted bin、Small bin和Large bin。
unsorted bin 的队列使用 bins 数组的第一个，如果被用户释放的 chunk 大于 max_fast，或者 fast bins 中的空闲 chunk 合并后，这些 chunk 首先会被放到 unsorted bin 队列中，在进 行 malloc 操作的时候，如果在 fast bins 中没有找到合适的 chunk，则 ptmalloc 会先在 unsorted bin 中查找合适的空闲 chunk，然后才查找 bins。如果 unsorted bin 不能满足分配要求。malloc 便会将 unsorted bin 中的 chunk 加入 bins 中。然后再从 bins 中继续进行查找和分配过程。从 这个过程可以看出来，unsorted bin 可以看做是 bins 的一个缓冲区，增加它只是为了加快分配的速度。 当空闲的 chunk 被链接到 bin 中的时候，ptmalloc 会把表示该 chunk 是否处于使用中的 标志 P 设为 0(注意，这个标志实际上处在下一个 chunk 中)，同时 ptmalloc 还会检查它前 后的 chunk 是否也是空闲的，如果是的话，ptmalloc 会首先把它们合并为一个大的 chunk， 然后将合并后的 chunk 放到 unstored bin 中。要注意的是，并不是所有的 chunk 被释放后就 立即被放到 bin 中。ptmalloc 为了提高分配的速度，会把一些小的的 chunk 先放到一个叫做 fast bins 的容器内。
数组中从 2 开始编号的前 64 个 bin 称为 small bins，同 一个 small bin 中的 chunk 具有相同的大小。两个相邻的 small bin 中的 chunk 大小相差 8bytes。 small bins 中的 chunk 按照最近使用顺序进行排列，最后释放的 chunk 被链接到链表的头部， 而申请 chunk 是从链表尾部开始，这样，每一个 chunk 都有相同的机会被 ptmalloc 选中。
Small bins 后面的 bin 被称作 large bins。large bins 中的每一个 bin 分别包含了一个给定范围 内的 chunk，其中的 chunk 按大小序排列。相同大小的 chunk 同样按照最近使用顺序排列。 ptmalloc 使用“smallest-first，best-fit”原则在空闲 large bins 中查找合适的 chunk。 （2）Fast Bins 一般的情况是，程序在运行时会经常需要申请和释放一些较小的内存空间。当分配器合并了相邻的几个小的 chunk 之后，也许马上就会有另一个小块内存的请求，这样分配器又需 要从大的空闲内存中切分出一块，这样无疑是比较低效的，故而，ptmalloc 中在分配过程中 引入了 fast bins，不大于 max_fast(默认值为 64B)的 chunk 被释放后，首先会被放到 fast bins 中，fast bins 中的 chunk 并不改变它的使用标志 P。这样也就无法将它们合并，当需要给用 户分配的 chunk 小于或等于 max_fast 时，ptmalloc 首先会在 fast bins 中查找相应的空闲块， 然后才会去查找 bins 中的空闲 chunk。在某个特定的时候，ptmalloc 会遍历 fast bins 中的 chunk，将相邻的空闲 chunk 进行合并，并将合并后的 chunk 加入 unsorted bin 中，然后再将 usorted bin 里的 chunk 加入 bins 中。
2.4 其它chunk并不是所有的 chunk 都按照上面的方式来组织，实际上，有三种例外情况。Top chunk，mmaped chunk 和 last remainder，下面会分别介绍这三类特殊的 chunk。top chunk 对于主分 配区和非主分配区是不一样的。 （1）Top chunk 对于非主分配区会预先从 mmap 区域分配一块较大的空闲内存模拟 sub-heap，通过管 理 sub-heap 来响应用户的需求，因为内存是按地址从低向高进行分配的，在空闲内存的最 高处，必然存在着一块空闲 chunk，叫做 top chunk。当 bins 和 fast bins 都不能满足分配需 要的时候，ptmalloc 会设法在 top chunk 中分出一块内存给用户，如果 top chunk 本身不够大， 分配程序会重新分配一个 sub-heap，并将 top chunk 迁移到新的 sub-heap 上，新的 sub-heap 与已有的 sub-heap 用单向链表连接起来，然后在新的 top chunk 上分配所需的内存以满足分 配的需要，实际上，top chunk 在分配时总是在 fast bins 和 bins 之后被考虑，所以，不论 top chunk 有多大，它都不会被放到 fast bins 或者是 bins 中。Top chunk 的大小是随着分配和回 收不停变换的，如果从 top chunk 分配内存会导致 top chunk 减小，如果回收的 chunk 恰好 与 top chunk 相邻，那么这两个 chunk 就会合并成新的 top chunk，从而使 top chunk 变大。 如果在 free 时回收的内存大于某个阈值，并且 top chunk 的大小也超过了收缩阈值，ptmalloc 会收缩 sub-heap，如果 top-chunk 包含了整个 sub-heap，ptmalloc 会调用 munmap 把整个 sub-heap 的内存返回给操作系统。 由于主分配区是唯一能够映射进程 heap 区域的分配区，它可以通过 sbrk()来增大或是 收缩进程 heap 的大小，ptmalloc 在开始时会预先分配一块较大的空闲内存(也就是所谓 的 heap)，主分配区的 top chunk 在第一次调用 malloc 时会分配一块(chunk_size + 128KB) align 4KB 大小的空间作为初始的 heap，用户从 top chunk 分配内存时，可以直接取出一块内 存给用户。在回收内存时，回收的内存恰好与 top chunk 相邻则合并成新的 top chunk，当该 次回收的空闲内存大小达到某个阈值，并且 top chunk 的大小也超过了收缩阈值，会执行内 存收缩，减小 top chunk 的大小，但至少要保留一个页大小的空闲内存，从而把内存归还给 操作系统。如果向主分配区的 top chunk 申请内存，而 top chunk 中没有空闲内存，ptmalloc 会调用 sbrk()将的进程 heap 的边界 brk 上移，然后修改 top chunk 的大小。 （2）mmaped chunk 当需要分配的 chunk 足够大，而且 fast bins 和 bins 都不能满足要求，甚至 top chunk 本身也不能满足分配需求时，ptmalloc 会使用 mmap 来直接使用内存映射来将页映射到进程空 间。这样分配的 chunk 在被 free 时将直接解除映射，于是就将内存归还给了操作系统，再次对这样的内存区的引用将导致 segmentation fault 错误。这样的 chunk 也不会包含在任何bin中。 （3）Last remainder Last remainder 是另外一种特殊的 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 chuk。如果分配的chunk是在large bins中的chunk split 之后的到的， split之后剩下的chunk会被加到unsorted chunk中，同时如果分配的chunk size在small chunk之内，split之后剩下的chunk还会被赋值给Last remainder. 2.5 sbrk 与 mmap从进程的内存布局可知，.bss 段之上的这块分配给用户程序的空间被称为 heap(堆)。 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_SIZ(E 32位系统上默认为1MB，64位系统上默认为64MB)的空间作为sub-heap。 这就是前面所说的 ptmalloc 所维护的分配空间，当用户请求内存分配时，首先会在这个区 域内找一块合适的 chunk 给用户。当用户释放了 heap 中的 chunk 时，ptmalloc 又会使用 fast bins 和 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 中分 配的空间则可能会留在进程内存空间内，还可以再次引用(当然是很危险的)。 当 ptmalloc munmap chunk 时，如果回收的 chunk 空间大小大于 mmap 分配阈值的当前 值，并且小于 DEFAULT_MMAP_THRESHOLD_MAX(32 位系统默认为 512KB，64 位系统默认 为 32MB)，ptmalloc 会把 mmap 分配阈值调整为当前回收的 chunk 的大小，并将 mmap 收 缩阈值(mmap trim threshold)设置为 mmap 分配阈值的 2 倍。这就是 ptmalloc 的对 mmap 分配阈值的动态调整机制，该机制是默认开启的，当然也可以用 mallopt()关闭该机制。 3. 内存分配3.1 分配算法
3.2 分配具体步骤
（1) 获取分配区的锁，为了防止多个线程同时访问同一个分配区，在进行分配之前需要取得分配区域的锁。线程先查看线程私有实例中是否已经存在一个分配区，如果存 在尝试对该分配区加锁，如果加锁成功，使用该分配区分配内存，否则，该线程搜 索分配区循环链表试图获得一个空闲(没有加锁)的分配区。如果所有的分配区都 已经加锁，那么 ptmalloc 会开辟一个新的分配区，把该分配区加入到全局分配区循 环链表和线程的私有实例中并加锁，然后使用该分配区进行分配操作。开辟出来的 新分配区一定为非主分配区，因为主分配区是从父进程那里继承来的。开辟非主分 配区时会调用 mmap()创建一个 sub-heap，并设置好 top chunk。 （2) 将用户的请求大小转换为实际需要分配的 chunk 空间大小。 （3) 判断所需分配 chunk 的大小是否满足 chunk_size <= max_fast (max_fast 默认为 64B)，如果是的话，则转下一步，否则跳到第 5 步。 （4) 首先尝试在 fast bins 中取一个所需大小的 chunk 分配给用户。如果可以找到，则分配结束。否则转到下一步。 （5) 判断所需大小是否处在 small bins 中，即判断 chunk_size < 512B 是否成立。如果chunk 大小处在 small bins 中，则转下一步，否则转到第 6 步。 （6) 根据所需分配的 chunk 的大小，找到具体所在的某个 small bin，从该 bin 的尾部摘取一个恰好满足大小的 chunk。若成功，则分配结束，否则，转到下一步。 （7) 到了这一步，说明需要分配的是一块大的内存，或者 small bins 中找不到合适的 chunk。于是，ptmalloc 首先会遍历 fast bins 中的 chunk，将相邻的 chunk 进行合并， 并链接到 unsorted bin 中，然后遍历 unsorted bin 中的 chunk，如果 unsorted bin 只 有一个 chunk，并且这个 chunk 在上次分配时被使用过，并且所需分配的 chunk 大 小属于 small bins，并且 chunk 的大小大于等于需要分配的大小，这种情况下就直 接将该 chunk 进行切割，分配结束，否则将根据 chunk 的空间大小将其放入 small bins 或是 large bins 中，遍历完成后，转入下一步。 （8) 到了这一步，说明需要分配的是一块大的内存，或者 small bins 和 unsorted bin 中都找不到合适的 chunk，并且 fast bins 和 unsorted bin 中所有的 chunk 都清除干净 了。从 large bins 中按照“smallest-first，best-fit”原则，找一个合适的 chunk，从 中划分一块所需大小的 chunk，并将剩下的部分链接回到 bins 中。若操作成功，则 分配结束，否则转到下一步。 （9) 如果搜索 fast bins 和 bins 都没有找到合适的 chunk，那么就需要操作 top chunk 来 进行分配了。判断 top chunk 大小是否满足所需 chunk 的大小，如果是，则从 top chunk 中分出一块来。否则转到下一步。 （10) 到了这一步，说明 top chunk 也不能满足分配要求，所以，于是就有了两个选择: 如果是主分配区，调用 sbrk()，增加 top chunk 大小;如果是非主分配区，调用 mmap 来分配一个新的 sub-heap，增加 top chunk 大小;或者使用 mmap()来直接分配。在这里，需要依靠 chunk 的大小来决定到底使用哪种方法。判断所需分配的 chunk 大小是否大于等于 mmap 分配阈值（默认128KB），如果是的话，则转下一步，调用 mmap 分配， 否则跳到第 12 步，增加 top chunk 的大小。 （11) 使用 mmap 系统调用为程序的内存空间映射一块 chunk_size align 4KB 大小的空间。 然后将内存指针返回给用户。 （12) 判断是否为第一次调用 malloc，若是主分配区，则需要进行一次初始化工作，分配一块大小为(chunk_size + 128KB) align 4KB 大小的空间作为初始的 heap。若已经初 始化过了，主分配区则调用 sbrk()增加 heap 空间，分主分配区则在 top chunk 中切 割出一个 chunk，使之满足分配需求，并将内存指针返回给用户。 总结一下：主分配区/分主分配区 ——> fast bin ——> small bins ——> unsorted bin ——> large bin ——> top chunk ——> 增加top chunk(sbrk/mmap) 或者 mmaped chunk。 4. 内存回收free() 函数接受一个指向分配区域的指针作为参数，释放该指针所指向的 chunk。而具体的释放方法则看该 chunk 所处的位置和该 chunk 的大小。free()函数的工作步骤如下:
（1) free()函数同样首先需要获取分配区的锁，来保证线程安全。 （2) 判断传入的指针是否为 0，如果为 0，则什么都不做，直接 return。否则转下一步。 （3) 判断所需释放的 chunk 是否为 mmaped chunk，如果是，则调用 munmap()释放mmaped chunk，解除内存空间映射，该空间不再有效。如果开启了 mmap 分配阈值的动态调整机制，并且当前回收的 chunk 大小大于 mmap 分配阈值，将 mmap 分配阈值设置为该 chunk 的大小，将 mmap 收缩阈值设定为 mmap 分配阈值的 2 倍，释放完成，否则跳到下一步。 （4) 判断 chunk 的大小和所处的位置，若 chunk_size <= max_fast，并且 chunk 并不位于 heap 的顶部，也就是说并不与 top chunk 相邻，则转到下一步，否则跳到第 6 步。 (因为与 top chunk 相邻的小 chunk 也和 top chunk 进行合并，所以这里不仅需要 判断大小，还需要判断相邻情况) （5) 将 chunk 放到 fast bins 中，chunk 放入到 fast bins 中时，并不修改该 chunk 使用状 态位 P。也不与相邻的 chunk 进行合并。只是放进去，如此而已。这一步做完之后 释放便结束了，程序从 free()函数中返回。 （6) 判断前一个 chunk 是否处在使用中，如果前一个块也是空闲块，则合并。并转下一 步。 （7) 判断当前释放 chunk 的下一个块是否为 top chunk，如果是，则转第 9 步，否则转 下一步。 （8) 判断下一个 chunk 是否处在使用中，如果下一个 chunk 也是空闲的，则合并，并将合并后的 chunk 放到 unsorted bin 中。注意，这里在合并的过程中，要更新 chunk的大小，以反映合并后的 chunk 的大小。并转到第 10 步。 （9) 如果执行到这一步，说明释放了一个与 top chunk 相邻的 chunk。则无论它有多大，都将它与 top chunk 合并，并更新 top chunk 的大小等信息。转下一步。 （10) 判断合并后的 chunk 的大小是否大于 FASTBIN_CONSOLIDATION_THRESHOLD(默认 64KB)，如果是的话，则会触发进行 fast bins 的合并操作，fast bins 中的 chunk 将被 遍历，并与相邻的空闲 chunk 进行合并，合并后的 chunk 会被放到 unsorted bin 中。fast bins 将变为空，操作完成之后转下一步。 （11) 判断 top chunk 的大小是否大于 mmap 收缩阈值(默认为 128KB)，如果是的话，对于主分配区，则会试图归还 top chunk 中的一部分给操作系统。但是最先分配的 128KB 空间是不会归还的，ptmalloc 会一直管理这部分内存，用于响应用户的分配 请求;如果为非主分配区，会进行 sub-heap 收缩，将 top chunk 的一部分返回给操 作系统，如果 top chunk 为整个 sub-heap，会把整个 sub-heap 还回给操作系统。做 完这一步之后，释放结束，从 free() 函数退出。可以看出，收缩堆的条件是当前 free 的 chunk 大小加上前后能合并 chunk 的大小大于 64k，并且要 top chunk 的大 小要达到 mmap 收缩阈值，才有可能收缩堆。 5. 配置选项Ptmalloc 主要提供以下几个配置选项用于调优，这些选项可以通过 mallopt()进行设置： 5.1. M_MXFASTM_MXFAST 用于设置 fast bins 中保存的 chunk 的最大大小，默认值为 64B，fast bins 中保存的 chunk 在一段时间内不会被合并，分配小对象时可以首先查找 fast bins，如果 fast bins 找到了所需大小的 chunk，就直接返回该 chunk，大大提高小对象的分配速度，但这个值设 置得过大，会导致大量内存碎片，并且会导致 ptmalloc 缓存了大量空闲内存，去不能归还给 操作系统，导致内存暴增。M_MXFAST 的最大值为 80B，不能设置比 80B 更大的值，因为设置为更大的值并不能提 高分配的速度。Fast bins 是为需要分配许多小对象的程序设计的，比如需要分配许多小 struct， 小对象，小的 string 等等。如果设置该选项为 0，就会不使用 fast bins。 5.2. M_TRIM_THRESHOLDM_TRIM_THRESHOLD 用于设置 mmap 收缩阈值，默认值为 128KB。自动收缩只会在 free 时才发生，如果当前 free 的 chunk 大小加上前后能合并 chunk 的大小大于 64KB，并且 top chunk 的大小达到 mmap 收缩阈值，对于主分配区，调用 malloc_trim()返回一部分内存给操 作系统，对于非主分配区，调用 heap_trim()返回一部分内存给操作系统，在发生内存收缩 时，还是从新设置 mmap 分配阈值和 mmap 收缩阈值。 这个选项一般与 M_MMAP_THRESHOLD 选项一起使用，M_MMAP_THRESHOLD 用于设置 mmap 分配阈值，对于长时间运行的程序，需要对这两个选项进行调优，尽量保证在 ptmalloc 中缓存的空闲 chunk 能够得到重用，尽量少用 mmap 分配临时用的内存。不停地使用系统 调用 mmap 分配内存，然后很快又 free 掉该内存，这样是很浪费系统资源的，并且这样分 配的内存的速度比从 ptmalloc 的空闲 chunk 中分配内存慢得多，由于需要页对齐导致空间利 用率降低，并且操作系统调用 mmap()分配内存是串行的，在发生缺页异常时加载新的物理 页，需要对新的物理页做清 0 操作，大大影响效率。M_TRIM_THRESHOLD 的值必须设置为页大小对齐，设置为-1 会关闭内存收缩设置。 注意:试图在程序开始运行时分配一块大内存，并马上释放掉，以期望来触发内存收缩， 这是不可能的，因为该内存马上就返回给操作系统了。 5.3. M_MMAP_THRESHOLDM_MMAP_THRESHOLD 用于设置 mmap 分配阈值，默认值为 128KB，ptmalloc 默认开启 动态调整 mmap 分配阈值和 mmap 收缩阈值。当用户需要分配的内存大于 mmap 分配阈值，ptmalloc 的 malloc()函数其实相当于 mmap() 的简单封装，free 函数相当于 munmap()的简单封装。相当于直接通过系统调用分配内存， 回收的内存就直接返回给操作系统了。因为这些大块内存不能被 ptmalloc 缓存管理，不能重 用，所以 ptmalloc 也只有在万不得已的情况下才使用该方式分配内存。 但使用 mmap 分配有如下的好处:
使用 mmap 分配内存的缺点:
5.4. M_MMAP_MAXM_MMAP_MAX 用于设置进程中用 mmap 分配的内存块的最大限制，默认值为 64K，因 为有些系统用 mmap 分配的内存块太多会导致系统的性能下降。如果将 M_MMAP_MAX 设置为 0，ptmalloc 将不会使用 mmap 分配大块内存。Ptmalloc 为优化锁的竞争开销，做了 PER_THREAD 的优化，也提供了两个选项， M_ARENA_TEST 和 M_ARENA_MAX，由于 PER_THREAD 的优化默认没有开启，这里暂不对这 两个选项做介绍。 另外，ptmalloc 没有提供关闭 mmap 分配阈值动态调整机制的选项，mmap 分配阈值动 态调整时默认开启的，如果要关闭 mmap 分配阈值动态调整机制，可以设置 M_TRIM_THRESHOLD，M_MMAP_THRESHOLD，M_TOP_PAD 和 M_MMAP_MAX 中的任意一个。 但是强烈建议不要关闭该机制，该机制保证了 ptmalloc 尽量重用缓存中的空闲内存，不用每 次对相对大一些的内存使用系统调用 mmap 去分配内存。 6. 注意事项为了避免 Glibc 内存暴增，使用时需要注意以下几点： （1）后分配的内存先释放，因为 ptmalloc 收缩内存是从 top chunk 开始，如果与 top chunk 相邻的 chunk 不能释放，top chunk 以下的 chunk 都无法释放。 （2）Ptmalloc 不适合用于管理长生命周期的内存，特别是持续不定期分配和释放长生命周期的内存，这将导致 ptmalloc 内存暴增。如果要用 ptmalloc 分配长周期内存，在 32 位系统上，分配的内存块最好大于 1MB，64 位系统上，分配的内存块大小大于 32MB。这是 由于 ptmalloc 默认开启 mmap 分配阈值动态调整功能，1MB 是 32 位系统 mmap 分配阈值的最大值，32MB 是 64 位系统 mmap 分配阈值的最大值，这样可以保证 ptmalloc 分配 的内存一定是从 mmap 映射区域分配的，当 free 时，ptmalloc 会直接把该内存返回给操 作系统，避免了被 ptmalloc 缓存。 （3）不要关闭 ptmalloc 的 mmap 分配阈值动态调整机制，因为这种机制保证了短生命周期的内存分配尽量从 ptmalloc 缓存的内存 chunk 中分配，更高效，浪费更少的内存。如果关闭了该机制，对大于 128KB 的内存分配就会使用系统调用 mmap 向操作系统分配内存， 使用系统调用分配内存一般会比从 ptmalloc 缓存的 chunk 中分配内存慢，特别是在多线程同时分配大内存块时，操作系统会串行调用 mmap()，并为发生缺页异常的页加载新物理页时，默认强制清 0。频繁使用 mmap 向操作系统分配内存是相当低效的。使用 mmap 分配的内存只适合长生命周期的大内存块。 （4）多线程分阶段执行的程序不适合用 ptmalloc，这种程序的内存更适合用内存池管理，就像 Apache 那样，每个连接请求处理分为多个阶段，每个阶段都有自己的内存池，每个阶段完成后，将相关的内存就返回给相关的内存池。Google 的许多应用也是分阶段执行的，他们在使用 ptmalloc 也遇到了内存暴增的相关问题，于是他们实现了 TCMalloc 来代替 ptmalloc，TCMalloc 具有内存池的优点，又有垃圾回收的机制，并最大限度优化了锁的争用，并且空间利用率也高于 ptmalloc。Ptmalloc 假设了线程 A 释放的内存块能在线程B中得到重用，但 B 不一定会分配和 A 线程同样大小的内存块，于是就需要不断地做切割和合并，可能导致内存碎片。 （5）尽量减少程序的线程数量和避免频繁分配/释放内存，Ptmalloc 在多线程竞争激烈的情况 下，首先查看线程私有变量是否存在分配区，如果存在则尝试加锁，如果加锁不成功会 尝试其它分配区，如果所有的分配区的锁都被占用着，就会增加一个非主分配区供当前 线程使用。由于在多个线程的私有变量中可能会保存同一个分配区，所以当线程较多时， 加锁的代价就会上升，ptmalloc 分配和回收内存都要对分配区加锁，从而导致了多线程竞争环境下 ptmalloc 的效率降低。 （6）防止内存泄露，ptmalloc 对内存泄露是相当敏感的，根据它的内存收缩机制，如果与 top chunk 相邻的那个 chunk 没有回收，将导致 top chunk 一下很多的空闲内存都无法返回给操作系统。 （7）防止程序分配过多内存，或是由于 Glibc 内存暴增，导致系统内存耗尽，程序因 OOM 被 系统杀掉。预估程序可以使用的最大物理内存大小，配置系统的 /proc/sys/vm/overcommit_memory，/proc/sys/vm/overcommit_ratio，以及使用 ulimt –v 限制程序能使用虚拟内存空间大小，防止程序因 OOM 被杀掉。 参考：《Glibc 内存管理 Ptmalloc2 源代码分析》 1. TCMalloc简介TCMalloc全称Thread-Caching Malloc，即线程缓存的malloc，实现了高效的多线程内存管理，用于替代系统的内存分配相关的函数（malloc、free，new，new[]等）。TCMalloc是gperftools的一部分，除TCMalloc外，gperftools还包括heap-checker、heap-profiler和cpu-profiler。本文只讨论gperftools的TCMalloc部分。TCMalloc是专门对多线并发的内存管理而设计的，TCMalloc主要是在线程级实现了缓存，使得用户在申请内存时大多情况下是无锁内存分配。按照所分配内存的大小，TCMalloc将内存分配分为三类：
简要介绍几个概念，Page，Span，PageHeap：
PageHeap以span为单位向系统申请内存，申请到的span可能只有一个page，也可能包含n个page。可能会被划分为一系列的小对象，供小对象分配使用，也可能当做一整块当做中对象或大对象分配。 2. 小对象分配整个 TCMalloc对小内存(小于等于256k)的管理实现了三级缓存，分别是ThreadCache(线程级缓存)，Central Cache(中央缓存：CentralFreeeList)，PageHeap(页缓存)。 2.1 SizeClass对于256KB以内的小对象分配，TCMalloc按大小划分了85个类别（官方介绍中说是88个左右，但我个人实际测试是85个，不包括0字节大小），称为Size Class，每个size class都对应一个大小，比如8字节，16字节，32字节。应用程序申请内存时，TCMalloc会首先将所申请的内存大小向上取整到size class的大小，比如1~8字节之间的内存申请都会分配8字节，9~16字节之间都会分配16字节，以此类推。因此这里会产生内部碎片。 2.2. ThreadCache对于每个线程，TCMalloc都为其保存了一份单独的缓存，称之为ThreadCache，这也是TCMalloc名字的由来（Thread-Caching Malloc）。每个ThreadCache中对于每个size class都有一个单独的FreeList，缓存了n个还未被应用程序使用的空闲对象。小对象的分配直接从ThreadCache的FreeList中返回一个空闲对象，相应的，小对象的回收也是将其重新放回ThreadCache中对应的FreeList中。由于每线程一个ThreadCache，因此从ThreadCache中取用或回收内存是不需要加锁的，速度很快。为了方便统计数据，各线程的ThreadCache连接成一个双向链表。ThreadCache的结构示大致如下： 2.3. Central Cache那么ThreadCache中的空闲对象从何而来呢？答案是CentralCache——一个所有线程公用的缓存。与ThreadCache类似，CentralCache中对于每个size class也都有一个单独的链表来缓存空闲对象，称之为CentralFreeList，供各线程的ThreadCache从中取用空闲对象。由于是所有线程公用的，因此从CentralCache中取用或回收对象，是需要加锁的。为了平摊锁操作的开销，ThreadCache一般从CentralCache中一次性取用或回收多个空闲对象。CentralCache在TCMalloc中并不是一个类，只是一个逻辑上的概念，其本质是CentralFreeList类型的数组。后文会详细讨论CentralCache的内部结构，现在暂且认为CentralCache的简化结构如下： 2.4. PageHeapCentralCache中的空闲对象又是从何而来呢？答案是之前提到的PageHeap——TCMalloc对可动态分配的内存的抽象。当CentralCache中的空闲对象不够用时，CentralCache会向PageHeap申请一块内存（可能来自PageHeap的缓存，也可能向系统申请新的内存），并将其拆分成一系列空闲对象，添加到对应size class的CentralFreeList中。PageHeap内部根据内存块（span）的大小采取了两种不同的缓存策略。128个page以内的span，每个大小都用一个链表来缓存，超过128个page的span，存储于一个有序set（std::set）。讨论TCMalloc的实现细节时再具体分析，现在可以认为PageHeap的简化结构如下： 2.5 内存回收上面说的都是内存分配，内存回收的情况是怎样的？应用程序调用free()或delete一个小对象时，仅仅是将其插入到ThreadCache中其size class对应的FreeList中而已，不需要加锁，因此速度也是非常快的。只有当满足一定的条件时，ThreadCache中的空闲对象才会重新放回CentralCache中，以供其他线程取用。同样的，当满足一定条件时，CentralCache中的空闲对象也会还给PageHeap，PageHeap再还给系统。 2.6 小结总结一下，小对象分配流程大致如下：
3. 中对象分配超过256KB但不超过1MB（128个page）的内存分配被认为是中对象分配，采取了与小对象不同的分配策略。首先，TCMalloc会将应用程序所要申请的内存大小向上取整到整数个page（因此，这里会产生1B~8KB的内部碎片）。之后的操作表面上非常简单，向PageHeap申请一个指定page数量的span并返回其起始地址即可。 对128个page以内的span和超过128个page的span，PageHeap采取的缓存策略不一样。为了描述方便，以下将128个page以内的span称为小span，大于128个page的span称为大span。先来看小span是如何管理的，大span的管理放在大对象分配一节介绍。PageHeap中有128个小span的链表，分别对应1~128个page的span： 假设要分配一块内存，其大小经过向上取整之后对应k个page，因此需要从PageHeap取一个大小为k个page的span，过程如下：
4. 大对象分配超过1MB（128个page）的内存分配被认为是大对象分配，与中对象分配类似，也是先将所要分配的内存大小向上取整到整数个page，假设是k个page，然后向PageHeap申请一个k个page大小的span。对于中对象的分配，如果上述的span链表无法满足，也会被当做是大对象来处理。也就是说，TCMalloc在源码层面其实并没有区分中对象和大对象，只是对于不同大小的span的缓存方式不一样罢了。大对象分配用到的span都是超过128个page的span，其缓存方式不是链表，而是一个按span大小排序的有序set（std::set），以便按大小进行搜索。 假设要分配一块超过1MB的内存，其大小经过向上取整之后对应k个page（k>128），或者是要分配一块1MB以内的内存，但无法由中对象分配逻辑来满足，此时k <= 128。不管哪种情况，都是要从PageHeap的span set中取一个大小为k个page的span，其过程如下：
5. 总结画张图概括下TCMalloc的管理内存的策略：
不超过256KB的小对象分配，在应用程序和内存之间其实有三层缓存：PageHeap、CentralCache、ThreadCache。而中对象和大对象分配，则只有PageHeap一层缓存。 1. Jemalloc简介jemalloc 是由 Jason Evans 在 FreeBSD 项目中引入的新一代内存分配器。它是一个通用的 malloc 实现，侧重于减少内存碎片和提升高并发场景下内存的分配效率，其目标是能够替代 malloc。jemalloc 在 2005 年首次作为 FreeBSD libc 分配器使用，2010年，jemalloc 的功能延伸到如堆分析和监控/调优等。现代的 jemalloc 版本依然集成在 FreeBSD 中。 jemalloc 应用十分广泛，在 Firefox、Redis、Rust、Netty 等出名的产品或者编程语言中都有大量使用。具体细节可以参考 Jason Evans 发表的论文 《A Scalable Concurrent malloc Implementation for FreeBSD》。这篇文章介绍 JeMalloc-5.1.0 版本。 2. 基础知识下图是旧版本的jemalloc：
旧版本的jemalloc中， 每个arena内都会包含对应的管理信息，记录该arena的分配情况。arena都有专属的chunks, 每个chunk的头部都记录了chunk的分配信息。在使用某一个chunk的时候，会把它分割成很多个run，并记录到bin中。不同size的class对应着不同的bin，在bin里，都会有一个红黑树来维护空闲的run，并且在run里，使用了bitmap来记录了分配状态。此外，每个arena里面维护一组按地址排列的可获得的run的红黑树。 对于jemalloc 5.1.0版本来说，有几点需要说明：
2.1 size_class每个 size_class 代表 jemalloc 分配的内存大小，共有 NSIZES（232）个小类（如果用户申请的大小位于两个小类之间，会取较大的，比如申请14字节，位于8和16字节之间，按16字节分配），分为2大类：
对于64位机器来说，通常区间是 [8, 14kb]，常见的有 8, 16, 32, 48, 64, …, 2kb, 4kb, 8kb，注意为了减少内存碎片并不都是2的次幂，比如如果没有48字节，那当申请33字节时，分配64字节显然会造成约50%的内存碎片
对于64位机器来说，通常区间是 [16kB, 7EiB]，从 4 * page_size 开始，常见的比如 16kB, 32kB, …, 1mB, 2mB, 4mB，最大是 $2^{62}+3^{60}$，对于64位操作系统，页大小为4kB。
size 位于 size_class 中的索引号，区间为 [0，231]，比如8字节则为0，14字节（按16计算）为1，4kb字节为28，当 size 是 small_class 时，size_index 也称作 binind 2.2 arenaarena 是 jemalloc 最重要的部分，内存由一定数量的 arenas 负责管理。每个用户线程都会被绑定到一个 arena 上，线程采用 round-robin 轮询的方式选择可用的 arena 进行内存分配，为了减少线程之间的锁竞争，默认每个 CPU 会分配 4 个 arena，各个 arena 所管理的内存相互独立。 struct arena_s {
atomic_u_t nthreads[2];
tsdn_t *last_thd;
arena_stats_t stats; // arena的状态
ql_head(tcache_t) tcache_ql;
ql_head(cache_bin_array_descriptor_t) cache_bin_array_descriptor_ql;
malloc_mutex_t tcache_ql_mtx;
prof_accum_t prof_accum;
uint64_t prof_accumbytes;
atomic_zu_t offset_state;
atomic_zu_t extent_sn_next; // extent的序列号生成器状态
atomic_u_t dss_prec;
atomic_zu_t nactive; // 激活的extents的page数量
extent_list_t large; // 存放 large extent 的 extents
malloc_mutex_t large_mtx; // large extent的锁
extents_t extents_dirty; // 刚被释放后空闲 extent 位于的地方
extents_t extents_muzzy; // extents_dirty 进行 lazy purge 后位于的地方，dirty -> muzzy
extents_t extents_retained; // extents_muzzy 进行 decommit 或 force purge 后 extent 位于的地方，muzzy -> retained
arena_decay_t decay_dirty; // dirty --> muzzy
arena_decay_t decay_muzzy; // muzzy --> retained
pszind_t extent_grow_next;
pszind_t retain_grow_limit;
malloc_mutex_t extent_grow_mtx;
extent_tree_t extent_avail; // heap，存放可用的 extent 元数据
malloc_mutex_t extent_avail_mtx; // extent_avail的锁
bin_t bins[NBINS]; // 所有用于分配小内存的 bin
base_t *base; // 用于分配元数据的 base
nstime_t create_time; // 创建时间
};几种extent的状态如下：
2.2 extent 管理 jemalloc 内存块（即用于用户分配的内存）的结构，每一个内存块大小可以是 struct extent_s {
uint64_t e_bits; // 8字节长，记录多种信息
void *e_addr; // 管理的内存块的起始地址
union {
size_t e_size_esn; // extent和序列号的大小
size_t e_bsize; // 基本extent的大小
};
union {
/*
* S位图，当此 extent 用于分配 small_class 内存时，用来记录这个 extent 的分配情况，
* 此时每个 extent 的内的小内存称为 region
*/
arena_slab_data_t e_slab_data;
atomic_p_t e_prof_tctx; // 一个计数器，用于large object
};
}2.3 extents管理 extent 的集合。 struct extents_s {
malloc_mutex_t mtx; // 同步锁
extent_heap_t heaps[NPSIZES+1]; // 各种 page(4kb) 倍数大小的 extent
/* Bitmap for which set bits correspond to non-empty heaps. */
bitmap_t bitmap[BITMAP_GROUPS(NPSIZES+1)];
extent_list_t lru; // 存放所有 extent 的双向链表
atomic_zu_t npages; // 堆中的page个数
extent_state_t state; // extent的状态
bool delay_coalesce; // 是否延迟extent的合并
};2.4 slab当 extent 用于分配 small_class 内存时，称其为 slab。一个 extent 可以被用来处理多个同一 size_class 的内存申请。 2.5 bin 在arena中， bin用于管理正在使用中的 slab（即用于小内存分配的 extent） 的集合，每 struct bin_s {
malloc_mutex_t lock; // 对bin进行操作的锁
extent_t *slabcur; // 当前用于该bin的extent
extent_heap_t slabs_nonfull; // 有空闲内存块的 slab
extent_list_t slabs_full; // 已经使用的slab列表
bin_stats_t stats; // bin的状态统计
};2.6 base用于分配 jemalloc 元数据内存的结构，通常一个 base 大小为 2mb， 所有 base 组成一个链表。 struct base_s {
/* Associated arena's index within the arenas array. */
unsigned ind;
/*
* User-configurable extent hook functions. Points to an
* extent_hooks_t.
*/
atomic_p_t extent_hooks;
malloc_mutex_t mtx; // 锁
bool auto_thp_switched; // 是否使用THP
/*
* Most recent size class in the series of increasingly large base
* extents. Logarithmic spacing between subsequent allocations ensures
* that the total number of distinct mappings remains small.
*/
pszind_t pind_last;
size_t extent_sn_next; // Serial number generation state
base_block_t *blocks; // Chain of all blocks associated with base
extent_heap_t avail[NSIZES]; // 存放每个size_class的extent元数据
/* Stats, only maintained if config_stats. */
size_t allocated;
size_t resident;
size_t mapped;
size_t n_thp; // Number of THP regions touched.
};2.7 tcache每个线程独有的缓存（Thread Cache），大多数内存申请都可以在 tcache 中直接得到，从而避免加锁： struct tcache_s {
uint64_t prof_accumbytes;
ticker_t gc_ticker;
cache_bin_t bins_small[NBINS]; // 小内存的 cache_bin
ql_elm(tcache_t) link;
cache_bin_array_descriptor_t cache_bin_array_descriptor;
arena_t *arena; // tcache关联的arena
szind_t next_gc_bin; // 进行GC的下一个bin
uint8_t lg_fill_div[NBINS]; // 填写ncached_max >> lg_fill_div
cache_bin_t bins_large[NSIZES-NBINS]; // 大内存的cache bin
};2.8 cache bin每个线程独有的用于分配小内存的缓存： struct cache_bin_s {
cache_bin_sz_t low_water; // 上一次 gc 后剩余的缓存数量
cache_bin_sz_t ncached; // 当前 cache_bin 存放的缓存数量
cache_bin_stats_t tstats; // cache bin的状态
void **avail; // 可直接用于分配的内存，从左往右依次分配（注意这里的寻址方式）
};2.9 tsdThread Specific Data，每个线程独有，用于存放与这个线程相关的结构：
2.10 rtree 全局唯一的存放每个 extent 信息的 Radix Tree，以 extent->e_addr 即 uintptr_t 为 key，以我的机器为例，uintptr_t 为64位（8字节）， rtree 的高度为3，由于 extent->e_addr 是
3. 内存分配（malloc）3.1 小内存分配首先从 tsd->tcache->bins_small[binind] 中获取对应 size_class 的内存，有的话将内存直接返回给用户，如果 bins_small[binind] 中没有的话，需要通过 slab(extent) 对 tsd->tcache->bins_small[binind] 进行填充，一次填充多个以备后续分配，填充方式如下（当前步骤无法成功则进行下一步）： （1）通过 bin->slabcur 分配； （2）从 bin->slabs_nonfull 中获取可使用的 extent； （3）从 arena->extents_dirty 中回收 extent，回收方式为 best-fit，即满足大小要求的最小 （4）从 arena->extents_muzzy 中回收 extent，回收方式为 first-fit，即满足大小要求且序列号最小地址最低（最旧）的 extent，遍历每个满足大小要求并且非空的 arena->extents_dirty->bitmap，获取其对应 extents->heaps 中第一个 extent，然后进行比较，找到最旧的 extent，之后仍然需要分裂； （5）从 arena->extents_retained 中回收 extent，回收方式与 extents_muzzy 相同； （6）尝试通过 mmap 向内核获取所需的 extent 内存，并且在 rtree 中注册新 extent 的信息； （7）再次尝试从 bin->slabs_nonfull 中获取可使用的 extent；
3.2 大内存分配 大内存不存放在 tsd->tcache 中，因为这样可能会浪费内存，所以每次申请都需要重新分配一个 extent，申请的流程和小内存申请 extent 4. 内存释放（free）4.1 小内存释放在 rtree 中找到需要被释放内存所属的 extent 信息，将要被释放的内存还给 tsd->tcache->bins_small[binind]，如果 tsd->tcache->bins_small[binind] 已满，需要对其进行 flush，流程如下： （1）将这块内存返还给所属 extent，如果这个 extent 中空闲的内存块变成了最大（即没有一份内存被分配），跳到2；如果这个 extent 中的空闲块变成了1并且这个 extent 不是 arena->bins[binind]->slabcur，跳到（3）； （2）将这个 extent 释放，即插入 arena->extents_dirty 中； （3）将arena->bins[binind]->slabcur 切换为这个 extent，前提是这个 extent “更旧”（序列号更小地址更低），并且将替换后的 extent 移入 arena->bins[binind]->slabs_nonfull； 4.2 大内存释放 因为大内存不存放在 tsd->tcache 中，所以大内存释放只进行小内存释放的步骤2，即将 5. 内存再分配（realloc）5.1 小内存再分配（1）尝试进行 no move 分配，如果两次申请位于同一 size class 的话就可以不做任何事情，直接返回。比如第一次申请了12字节，但实际上 jemalloc 会实际分配16字节，然后第二次申请将12扩大到15字节或者缩小到9字节，那这时候16字节就已经满足需求了，所以不做任何事情，如果无法满足，跳到（2）； （2）重新分配，申请新内存大小（参考内存分配），然后将旧内存内容拷贝到新地址，之后释放旧内存（参考内存释放），最后返回新内存； 5.2 大内存再分配（1）尝试进行 no move 分配，如果两次申请位于同一 size class 的话就可以不做任何事情，直接返回； （2）尝试进行 no move resize 分配，如果第二次申请的大小大于第一次，则尝试对当前地址所属 extent 的下一地址查看是否可以分配，比如当前 extent 地址是 0x1000，大小是 0x1000，那么我们查看地址 0x2000 开始的 extent 是否存在（通过 rtree）并且是否满足要求，如果满足要求那两个 extent 可以进行合并，成为一个新的 extent 而不需要重新分配；如果第二次申请的大小小于第一次，那么尝试对当前 extent 进行 split，移除不需要的后半部分，以减少内存碎片；如果无法进行 no move resize 分配，跳到（3）； （3）重新分配，申请新内存大小（参考内存分配），然后将旧内存内容拷贝到新地址，之后释放旧内存（参考内存释放），最后返回新内存； 6. 内存回收（GC）GC（Garbage Collection）即是进行内存的垃圾回收，分为2种， tcache GC和 extent GC； 6.1 tcache GC针对 small_class，防止某个线程预先分配了内存但是却没有实际分配给用户，会定期将缓存 flush 到 extent。 （1）GC 策略 每次对于 tcache 进行 malloc 或者 free 操作都会执行一次计数，默认情况下达到228次就会触发 gc，每次 gc 一个 cache_bin。 （2）如何 GC
6.2 extent GC 调用 free 时，内存并没有归还给内核。 jemalloc 内部会不定期地将没有用于分配的 （1）GC 策略 默认10s为 extents_dirty 和 extents_muzzy 的一个 gc 周期，每次对于 arena 注意并不是每隔10s一次性 gc，实际上 jemalloc 会将10s划分成200份，即每隔0.05s进行一次 gc，这样一来如果 t 时刻有 N 个 page 需要 gc，那么 jemalloc 尽力保证在 t+10 时刻这 N 个 page 会被 gc 完成。 严格来说，对于两次 gc 时刻 $t_{1}$ 和 $t_{2}$，在 $t_{2}-t_{1}$ 时间段内产生的所有 对于 N 个需要 gc 的 page 来说，并不是简单地每0.05s处理 N/200 个 page，jemalloc 引入了 Smoothstep（主要用于计算机图形学）来获得更加平滑的 gc 机制，这是 jemalloc 非常有意思的一个点。 jemalloc 内部维护了一个长度为200的数组，用来计算在10s的 gc 周期内每个时间点应该对多少 page 进行 gc。这样保证两次 gc 的时间段内产生的需要 gc 的 page 都会以图中绿色线条（默认使用 smootherstep）的变化曲线在10s的周期内从 N 减为 0（从右往左）。 （2）如何 GC 先进行 extents_dirty 的 gc，后进行 extents_muzzy 。
7. |
|
|
