参考链接

ptmalloc2和glibc

ptmalloc2是我们当前使用的glibc的malloc函数的实现；另外google有对应的内存管理是tcmalloc；以及facebook的内存管理jemalloc。以下是其他的内存管理的相关信息。

dlmalloc  – General purpose allocator
ptmalloc2 – glibc
jemalloc  – FreeBSD and Firefox
tcmalloc  – Google
libumem   – Solaris

glibc是GNU发布的libc库，也就是C语言运行需要依赖的底层api库。

堆的基本知识

当一个程序执行时被映射进内存，在高地址为内核地址范围，应用进程无法访问，稍微低一点的地址是栈所在的位置。从内存较低地址开始为程序的text、data、bss等段(也可以叫节)，在bss段和栈之间有一块空间被划分为两部分，在较高的地址部分为mmap、较低的部分为heap部分（heap部分紧贴着bss段）。

对于heap的操作，操作系统提供了brk()函数，libc提供了sbrk()函数，对mmap的操作，操作系统提供了mmap()和munmap()函数。

malloc

堆的申请通常使用malloc，malloc函数做了一些异常情况处理

malloc(size_t n)
当n=0时，返回当前系统允许的堆的最小内存块。
当n<0时，由于在大多数系统上，size_t 是无符号数（这一点非常重要），所以程序就会申请很大的内存空间，但通常来说都会失败，因为系统没有那么多的内存可以分配。

heap区域的操作—brk、sbrk

#include <unistd.h>
int brk(void *addr);
void *sbrk(intptr_t increment);

start_brk是进程动态内存分配(堆heap)起始地址，brk是堆的终止地址。

sbrk()的参数 increment 为 0 时，sbrk()返回的是进程的当前 brk 值， increment 为正数时扩展 brk 值，当 increment 为负值时收缩 brk 值。

mmap区域的操作—mmap、munmap

注意使用 mmap()直接映射的 chunk 在释放时直接解除映射，而不再属于进程的内存空间。但并不是所有使用mmap函数分配的内存都是直接对内存进行映射。

arena

堆由低地址向高地址方向增长，一般称管理堆的那部分程序为堆管理器。堆管理器主要做两部分工作，一方面预先分配一块很大的连续内存来保证内存管理的高效性；另一方面管理用户释放的内存，一般来说，用户释放的内存并不是直接返还给操作系统的，而是由堆管理器进行管理。这些释放的内存可以来响应用户新申请的内存的请求。

**虽然程序可能只是向操作系统申请很小的内存，但是为了方便，操作系统会把很大的内存分配给程序。这样的话，就避免了多次内核态与用户态的切换，提高了程序的效率。**我们称这一块连续的内存区域为 arena。

arena分为main arena和no main arena，每个进程只有一个主分配区，但可能存在多个非主分配区。主分配区可以访问heap和mmap区，非主分配区只能访问mmap。

对于从mmap分配的内存，释放时直接归还给操作系统。

chunk

chunk是用户申请内存的基本单位，也是堆管理器管理内存的基本单位

malloc函数返回的指针就指向一个chunk的数据区域。当程序申请的 chunk 被 free 后，会被加入到相应的空闲管理列表中。无论一个 chunk 的大小如何，处于分配状态还是释放状态，它们都使用一个统一的结构。虽然它们使用了同一个数据结构，但是根据是否被释放，它们的表现形式会有所不同。

chunk的数据结构

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;
};

一般来说，size_t 在 64 位中是 64 位无符号整数，32 位中是 32 位无符号整数。最小的 chunk 至少要包含 bk 指针。

prev_size, 如果该 chunk 的物理相邻的前一地址chunk是空闲的话，那该字段记录的是前一个 chunk 的大小 (包括 chunk 头)。否则，该字段可以用来存储物理相邻的前一个 chunk 的数据。

size ，该 chunk 的大小，大小必须是 2 * SIZE_SZ 的整数倍。如果申请的内存大小不是 2 * SIZE_SZ 的整数倍，会被转换满足大小的最小的 2 * SIZE_SZ 的倍数。32 位系统中，SIZE_SZ 是 4；64 位系统中，SIZE_SZ 是 8。该字段的低三个比特位对 chunk 的大小没有影响，它们从高到低分别表示

NON_MAIN_ARENA，记录当前 chunk 是否不属于主线程，1 表示不属于，0 表示属于。
IS_MAPPED，记录当前 chunk 是否是由 mmap 分配的。
PREV_INUSE，记录前一个 chunk 块是否被分配。一般来说，堆中第一个被分配的内存块的 size 字段的 P 位都会被设置为 1，以便于防止访问前面的非法内存。当一个 chunk 的 size 的 P 位为 0 时，我们能通过 prev_size 字段来获取上一个 chunk 的大小以及地址。这也方便进行空闲 chunk 之间的合并。

fd，bk，chunk 处于分配状态时，从 fd 字段开始是用户的数据。chunk 空闲时，会被添加到对应的空闲管理链表中，其字段的含义如下

fd 指向下一个（非物理相邻）空闲的 chunk
bk 指向上一个（非物理相邻）空闲的 chunk
通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理

fd_nextsize， bk_nextsize，也是只有 chunk 空闲的时候才使用，不过其用于较大的 chunk（large chunk）。

fd_nextsize 指向前一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
bk_nextsize 指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
一般空闲的 large chunk 在 fd 的遍历顺序中，按照由大到小的顺序排列。这样做可以避免在寻找合适 chunk 时挨个遍历。

一个已经分配的 chunk 的样子如下。我们称前两个字段称为 chunk header，后面的部分称为 user data。每次 malloc 申请得到的内存指针，其实指向 user data 的起始处！！！！！

chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of previous chunk, if unallocated (P clear)  |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of chunk, in bytes                     |A|M|P|
  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             User data starts here...                          .
        .                                                               .
        .             (malloc_usable_size() bytes)                      .
next    .                                                               |
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             (size of chunk, but used for application data)    |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of next chunk, in bytes                |A|0|1|
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

被释放的 chunk 被记录在链表中（可能是循环双向链表，也可能是单向链表）。具体结构如下

chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of previous chunk, if unallocated (P clear)  |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`head:' |             Size of chunk, in bytes                     |A|0|P|
  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Forward pointer to next chunk in list             |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Back pointer to previous chunk in list            |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Unused space (may be 0 bytes long)                .
        .                                                               .
 next   .                                                               |
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`foot:' |             Size of chunk, in bytes                           |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of next chunk, in bytes                |A|0|0|
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

可以发现，如果一个 chunk 处于 free 状态，那么会有两个位置记录其相应的大小，一个是本身的 size 字段会记录，另一个是它后面的 chunk 会记录。

一般情况下，物理相邻的两个空闲 chunk 会被合并为一个 chunk 。堆管理器会通过 prev_size 字段以及 size 字段合并两个物理相邻的空闲 chunk 块。

另外，当一个 chunk 处于已分配状态时，它的物理相邻的下一个 chunk 的 prev_size 字段必然是无效的，故而这个字段就可以被当前这个 chunk 使用。这就是 ptmalloc 中 chunk 间的复用。

bin

ptmalloc 将相似大小的 chunk 用双向链表链接起来，这样的一个链表被称为一个 bin。Ptmalloc 一共维护了 128 个 bin，并使用一个数组来存储这些 bin。

普通的bin包括了fast bin，unstorted bin，small bins，large bins

用户释放掉的 chunk 不会马上归还给系统，ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk。当用户再一次请求分配内存时，ptmalloc 分配器会试图在空闲的 chunk 中挑选一块合适的给用户。这样可以避免频繁的系统调用，降低内存分配的开销。

在具体的实现中，ptmalloc 采用分箱式方法对空闲的 chunk 进行管理。首先，它会根据空闲的 chunk 的大小以及使用状态将 chunk 初步分为 4 类：fast bins，small bins，large bins，unsorted bin。每类中仍然有更细的划分，相似大小的 chunk 会用双向链表链接起来。也就是说，在每类 bin 的内部仍然会有多个互不相关的链表来保存不同大小的 chunk。

对于 small bins，large bins，unsorted bin 来说，ptmalloc 将它们维护在同一个数组中。

#define NBINS 128
/* Normal bins packed as described above */
mchunkptr bins[ NBINS * 2 - 2 ];

top chunk

不管是heap区还是mmap区，都会在大地址端存在一段提前申请给进程，但是还没有使用的空闲chunk，这就是top chunk，因此在heap会有一个top chunk，在mmap区也会有一个top chunk。

mmaped chunk

当需要分配的 chunk 足够大，而且 fast bins 和 bins 都不能满足要求，甚至 top chunk 本身也不能满足分配需求时，ptmalloc 会使用 mmap 来直接使用内存映射来将页映射到进程空间。这样分配的 chunk 在被 free 时将直接解除映射，于是就将内存归还给了操作系统，再次对这样的内存区的引用将导致 segmentation fault 错误。这样的 chunk 也不会包含在任何bin中。

Last remainder

当需要分配一个 small chunk，但在 small bins 中找不到合适的 chunk，如果 last remainder chunk 的大小大于所需的 small chunk 大小，last remainder chunk 被分裂成两个 chunk，其中一个 chunk 返回给用户，另一个 chunk 变成新的 last remainder chuk。

内存分配概述

内存分配时，先在fast bin中找是否有满足条件的chunk，没有的话再去small bins中找。如果没有，再遍历一次fast bin，将相邻的chunk合并，并连接到unsorted bin中，然后便利unsorted bin。如果还没有合适的chunk，将unsorted bin中的chunk根据大小放入small bins或者large bins中。再从large bins中找合适的chunk。如果还没找到，再操作top chunk来分配。如果还不行，如果是主分配区，调用sbrk函数增加top chunk大小，如果是非主分配区，调用mmap函数分配top chunnk大小；或者直接使用mmap函数直接从内存分配。如果还是不行就增加heap的大小并且调整heap的边界结束位置来增加top chunk来达到分配的要求。

内存回收概述

判断释放的chunk是否为mmaped chunk，如果是，则调用munmap函数直接归还给操作系统。

如果chunk_size <= max_fast，并且chunk不位于heap顶部，则放到fast bin中，free结束。

否则判断前一个chunk是否为空闲，如果是则合并。

判断当前释放的chunk是否为下一个chunk的top chunk，如果是则说明当前chunk和top chunk相邻，与top chunk合并，否则判断下一个chunk是否空闲，如果空闲则合并然后放到unsorted bin中。如果此合并后的chunk大小大于FASTBIN_CONSOLIDATION_THRESHOLD会触发fast bin合并操作，便利fast bin，将相邻空闲chunk合并，放入unsorted bin中。

判断topchunk大小是否大于mmap收缩阈值，是的话，对于主分配区会归还top chunk的一部分给操作系统；对于非主分配区，进行sub-heap收缩，将此top chunk一部分返回给操作系统；

标签：bin,二进制,mmap,chunk,基础,内存,bins,空闲
From： https://blog.51cto.com/u_15457669/5786018

二进制基础