堆概述

什么是堆

在程序运行过程中，堆可以提供动态分布的内存，允许程序申请大小未知的内存。堆其实就是程序虚拟地址空间的一块连续的线性区域，它由低地址向高地址方向增长。我们一般称管理堆的那部分程序为堆管理器。

堆管理器处于用户程序与内核中间，主要做以下工作：

1.响应用户的申请内存请求，向操作系统申请内存，然后将其返回给用户程序，同时为了保持内存管理的高效性，内核一般都会预先分配很大的一块连续的内存，然后让堆管理通过某种算法管理这块内存。只有当出现了堆空间不足的情况，堆管理器才会再次与操作系统进行交互。

2.管理用户所释放的内存。一般来说用户释放的内存并不是直接返还给操作系统的，而是由堆管理器进行管理。这些释放的内存可以来响应用户新申请的内存请求。

Linux 中早期的堆分配与回收由 Doug Lea 实现，但它在并行处理多个线程时，会共享进程的堆内存空间。因此，为了安全性，一个线程使用堆时，会进行加锁。然而，与此同时，加锁会导致其它线程无法使用堆，降低了内存分配和回收的高效性。同时，如果在多线程使用时，没能正确控制，也可能影响内存分配和回收的正确性。Wolfram Gloger 在 Doug Lea 的基础上进行改进使其可以支持多线程，这个堆分配器就是 ptmalloc 。在 glibc-2.3.x. 之后，glibc 中集成了 ptmalloc2。

目前 Linux 标准发行版中使用的堆分配器是 glibc 中的堆分配器：ptmalloc2。ptmalloc2 主要是通过 malloc/free 函数来分配和释放内存块。

需要注意的是，在内存分配与使用的过程中，Linux 有这样的一个基本内存管理思想，只有当真正访问一个地址的时候，系统才会建立虚拟页面与物理页面的映射关系。 所以虽然操作系统已经给程序分配了很大的一块内存，但是这块内存其实只是虚拟内存。只有当用户使用到相应的内存时，系统才会真正分配物理页面给用户使用。

堆的基本操作

这里我们主要介绍

  • 基本的堆操作，包括堆的分配，回收，堆分配背后的系统覅用
  • 介绍堆目前的多线程支持

malloc

在 glibc 的 malloc.c 中，malloc 的说明如下

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
  malloc(size_t n)
  Returns a pointer to a newly allocated chunk of at least n bytes, or null
  if no space is available. Additionally, on failure, errno is
  set to ENOMEM on ANSI C systems.
  If n is zero, malloc returns a minumum-sized chunk. (The minimum
  size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit
  systems.)  On most systems, size_t is an unsigned type, so calls
  with negative arguments are interpreted as requests for huge amounts
  of space, which will often fail. The maximum supported value of n
  differs across systems, but is in all cases less than the maximum
  representable value of a size_t.
*/

可以看出，malloc 函数返回对应大小字节的内存块的指针。此外，该函数还对一些异常情况进行了处理

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

free

在 glibc 的 malloc.c 中，free 的说明如下

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
  malloc(size_t n)
  Returns a pointer to a newly allocated chunk of at least n bytes, or null
  if no space is available. Additionally, on failure, errno is
  set to ENOMEM on ANSI C systems.
  If n is zero, malloc returns a minumum-sized chunk. (The minimum
  size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit
  systems.)  On most systems, size_t is an unsigned type, so calls
  with negative arguments are interpreted as requests for huge amounts
  of space, which will often fail. The maximum supported value of n
  differs across systems, but is in all cases less than the maximum
  representable value of a size_t.
*/

可以看出，free 函数会释放由 p 所指向的内存块。这个内存块有可能是通过 malloc 函数得到的，也有可能是通过相关的函数 realloc 得到的。

此外，该函数也同样对异常情况进行了处理

  • 当 p 为空指针时，函数不执行任何操作。
  • 当 p 已经被释放之后，再次释放会出现乱七八糟的效果，这其实就是 double free。
  • 除了被禁用 (mallopt) 的情况下，当释放很大的内存空间时，程序会将这些内存空间还给系统，以便于减小程序所使用的内存空间。

内存分配背后的系统调用

在前面提到的函数中，无论是 malloc 函数还是 free 函数，我们动态申请和释放内存时，都经常会使用，但是它们并不是真正与系统交互的函数。这些函数背后的系统调用主要是 (s)brk 函数以及 mmap, munmap 函数。

如下图所示，我们主要考虑对堆进行申请内存块的操作。

1

(s)brk

对于堆的操作，操作系统提供了brk函数，glibc库提供了sbrk函数，我们可以通过增加brk的大小来向操作系统申请内存

初始时，堆的起始地址start_brk以及堆的当前末尾brk指向同一地址。根据是否开启ASLR，两者的具体位置会有所不同

  • 不开启 ASLR 保护时，start_brk 以及 brk 会指向 data/bss 段的结尾。
  • 开启 ASLR 保护时，start_brk 以及 brk 也会指向同一位置，只是这个位置是在 data/bss 段结尾后的随机偏移处。

具体效果如下图：

1

接下来实际操作来深入理解通过改变brk的大小来分配或释放堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/* sbrk and brk example */
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>

int main()
{
        void *curr_brk, *tmp_brk = NULL;

        printf("Welcome to sbrk example:%d\n", getpid());

        /* sbrk(0) gives current program break location */
        tmp_brk = curr_brk = sbrk(0);
        printf("Program Break Location1:%p\n", curr_brk);
        getchar();

        /* brk(addr) increments/decrements program break location */
        brk(curr_brk+4096);

        curr_brk = sbrk(0);
        printf("Program break Location2:%p\n", curr_brk);
        getchar();

        brk(tmp_brk);

        curr_brk = sbrk(0);
        printf("Program Break Location3:%p\n", curr_brk);
        getchar();

        return 0;
}

该程序用于演示程序如何手动控制 “程序中断点（Program Break）”（堆内存的边界），理解堆内存动态分配的底层原理。

1
2
3
4
5
6
curr_brk：记录当前程序中断点地址。
tmp_brk：临时保存初始中断点地址，用于后续恢复。
sbrk(0) 作用：返回当前程序中断点的地址（堆内存的 “边界”，堆向上生长的终点）。
getpid()：获取当前进程 ID，方便调试时区分不同进程。
brk 函数作用：手动设置程序中断点的位置。传入新地址 curr_brk+4096 表示扩展堆内存

需要注意的是，在每一次执行完操作后，都执行了 getchar() 函数，这是为了我们方便我们查看程序真正的映射。

gcc编译链接

1
gcc -o sbrk sbrk.c

gdb调试sbrk程序观察堆边界变化情况

这里我们可以通过两种方式来查看内存分配情况

1
2
vmmap
cat /proc/进程号/maps

在第一次调用brk之前

1

可以看到并没有出现堆，结合输出可以发现

start_brk = brk = end_data = 0x555555559000

调用完第一个printf之后

出现了堆段，brk = 0x5555557a000

1

觉得应该是在printf函数内部改变了brk的大小

此时调用sbrk(0)可以发现rax存储了此时的brk

1

接下来我们尝试将brk变大，来扩展堆内存空间

扩展

brk(curr_brk+4096);扩大一页内存

1

可以看到此时brk变为了0x55555557b000堆空间得到了拓展

接下来将brk变小释放刚刚扩展的堆空间

释放

brk(tmp_brk);将brk变回初始的0x55555557a000

1

可以看到此时brk变为了0x55555557a000刚刚扩展的部分得到了释放

mmap

malloc 会使用 mmap 来创建独立的匿名映射段。匿名映射的目的主要是可以申请以 0 填充的内存，并且这块内存仅被调用进程所使用。

同样的我们通过一个程序来深入理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/* Private anonymous mapping example using mmap syscall */
#include <stdio.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdlib.h>

void static inline errExit(const char* msg)
{
        printf("%s failed. Exiting the process\n", msg);
        exit(-1);
}

int main()
{
        int ret = -1;
        printf("Welcome to private anonymous mapping example::PID:%d\n", getpid());
        printf("Before mmap\n");
        getchar();
        char* addr = NULL;
        addr = mmap(NULL, (size_t)132*1024, PROT_READ|PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
        if (addr == MAP_FAILED)
                errExit("mmap");
        printf("After mmap\n");
        getchar();

        /* Unmap mapped region. */
        ret = munmap(addr, (size_t)132*1024);
        if(ret == -1)
                errExit("munmap");
        printf("After munmap\n");
        getchar();
        return 0;
}

gcc编译链接

1
gcc -o mmap mmap.c

调用mmap前的内存段

1

可以看到调用mmap后内存段的变大了

1

调用munmap后内存段恢复

1

多线程支持

在原来的 dlmalloc 实现中，当两个线程同时要申请内存时，只有一个线程可以进入临界区申请内存，而另外一个线程则必须等待直到临界区中不再有线程。这是因为所有的线程共享一个堆。在 glibc 的 ptmalloc 实现中，比较好的一点就是支持了多线程的快速访问。在新的实现中，所有的线程共享多个堆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/* Per thread arena example. */
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <sys/types.h>

void* threadFunc(void* arg) {
        printf("Before malloc in thread 1\n");
        getchar();
        char* addr = (char*) malloc(1000);
        printf("After malloc and before free in thread 1\n");
        getchar();
        free(addr);
        printf("After free in thread 1\n");
        getchar();
}

int main() {
        pthread_t t1;
        void* s;
        int ret;
        char* addr;

        printf("Welcome to per thread arena example::%d\n",getpid());
        printf("Before malloc in main thread\n");
        getchar();
        addr = (char*) malloc(1000);
        printf("After malloc and before free in main thread\n");
        getchar();
        free(addr);
        printf("After free in main thread\n");
        getchar();
        ret = pthread_create(&t1, NULL, threadFunc, NULL);
        if(ret)
        {
                printf("Thread creation error\n");
                return -1;
        }
        ret = pthread_join(t1, &s);
        if(ret)
        {
                printf("Thread join error\n");
                return -1;
        }
        return 0;
}

第一次申请之前， 没有任何任何堆段。

1
2
3
4
5
6
7
8
9
10
11
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread
Welcome to per thread arena example::6501
Before malloc in main thread
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
b7e05000-b7e07000 rw-p 00000000 00:00 0
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$

第一次申请后， 从下面的输出可以看出，堆段被建立了，并且它就紧邻着数据段，这说明 malloc 的背后是用 brk 函数来实现的。同时，需要注意的是，我们虽然只是申请了 1000 个字节，但是我们却得到了 0x0806c000-0x0804b000=0x21000 个字节的堆。这说明虽然程序可能只是向操作系统申请很小的内存，但是为了方便，操作系统会把很大的内存分配给程序。这样的话，就避免了多次内核态与用户态的切换，提高了程序的效率。我们称这一块连续的内存区域为 arena。此外，我们称由主线程申请的内存为 main_arena。后续的申请的内存会一直从这个 arena 中获取，直到空间不足。当 arena 空间不足时，它可以通过增加 brk 的方式来增加堆的空间。类似地，arena 也可以通过减小 brk 来缩小自己的空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
...
sploitfun@sploitfun-VirtualBox:~/lsploits/hof/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0          [heap]
b7e05000-b7e07000 rw-p 00000000 00:00 0
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$

在主线程释放内存后，我们从下面的输出可以看出，其对应的 arena 并没有进行回收，而是交由 glibc 来进行管理。当后面程序再次申请内存时，在 glibc 中管理的内存充足的情况下，glibc 就会根据堆分配的算法来给程序分配相应的内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
After free in main thread
...
sploitfun@sploitfun-VirtualBox:~/lsploits/hof/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0          [heap]
b7e05000-b7e07000 rw-p 00000000 00:00 0
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$

在第一个线程 malloc 之前，我们可以看到并没有出现与线程 1 相关的堆，但是出现了与线程 1 相关的栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
After free in main thread
Before malloc in thread 1
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0          [heap]
b7604000-b7605000 ---p 00000000 00:00 0
b7605000-b7e07000 rw-p 00000000 00:00 0          [stack:6594]
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$

第一个线程 malloc 后， 我们可以从下面输出看出线程 1 的堆段被建立了。而且它所在的位置为内存映射段区域，同样大小也是 132KB(b7500000-b7521000)。因此这表明该线程申请的堆时，背后对应的函数为 mmap 函数。同时，我们可以看出实际真的分配给程序的内存为 1M(b7500000-b7600000)。而且，只有 132KB 的部分具有可读可写权限，这一块连续的区域成为 thread arena。

注意：

当用户请求的内存大于 128KB 时，并且没有任何 arena 有足够的空间时，那么系统就会执行 mmap 函数来分配相应的内存空间。这与这个请求来自于主线程还是从线程无关。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
After free in main thread
Before malloc in thread 1
After malloc and before free in thread 1
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0          [heap]
b7500000-b7521000 rw-p 00000000 00:00 0
b7521000-b7600000 ---p 00000000 00:00 0
b7604000-b7605000 ---p 00000000 00:00 0
b7605000-b7e07000 rw-p 00000000 00:00 0          [stack:6594]
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$

在第一个线程释放内存后， 我们可以从下面的输出看到，这样释放内存同样不会把内存重新给系统。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
After free in main thread
Before malloc in thread 1
After malloc and before free in thread 1
After free in thread 1
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0          [heap]
b7500000-b7521000 rw-p 00000000 00:00 0
b7521000-b7600000 ---p 00000000 00:00 0
b7604000-b7605000 ---p 00000000 00:00 0
b7605000-b7e07000 rw-p 00000000 00:00 0          [stack:6594]
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$

堆相关数据结构

堆的操作就这么复杂，那么在 glibc 内部必然也有精心设计的数据结构来管理它。与堆相应的数据结构主要分为

  • 宏观结构，包含堆的宏观信息，可以通过这些数据结构索引堆的基本信息。
  • 微观结构，用于具体处理堆的分配与回收中的内存块。

微观结构

这里首先介绍堆的一些主要内部结构，堆的漏洞利用与这些结构密切相关。

malloc_chunk

概述

在程序的执行过程中，我们称由malloc申请的内存为chunk。这块内存在ptmalloc内部用malloc_chunk结构体来表示。当程序申请的chunk被free后，会被加入到相应的空闲管理列表中。

无论一个chunk的大小如何，处于分配状态还是释放状态，它们都使用一个统一的结构。虽然它们使用了同一个数据结构，但是根据是否被释放，它们的表现形式会有所不同。

malloc_chunk 的结构体如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
  This struct declaration is misleading (but accurate and necessary).
  It declares a "view" into memory allowing access to necessary
  fields at known offsets from a given base. See explanation below.
*/
struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  /* 前一个chunk的大小（仅当前一个chunk空闲时有效） */
  INTERNAL_SIZE_T      size;       /* 当前chunk的总大小（包含头部和数据区） */

  struct malloc_chunk* fd;         /* 双向链表指针：指向下一个空闲chunk */
  struct malloc_chunk* bk;         /* 双向链表指针：指向前一个空闲chunk */

 /* 仅用于大内存块：维护更大尺寸的chunk链表 */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

一些必要的宏定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/* INTERNAL_SIZE_T is the word-size used for internal bookkeeping of
   chunk sizes.
   The default version is the same as size_t.
   While not strictly necessary, it is best to define this as an
   unsigned type, even if size_t is a signed type. This may avoid some
   artificial size limitations on some systems.
   On a 64-bit machine, you may be able to reduce malloc overhead by
   defining INTERNAL_SIZE_T to be a 32 bit `unsigned int' at the
   expense of not being able to handle more than 2^32 of malloced
   space. If this limitation is acceptable, you are encouraged to set
   this unless you are on a platform requiring 16byte alignments. In
   this case the alignment requirements turn out to negate any
   potential advantages of decreasing size_t word size.
   Implementors: Beware of the possible combinations of:
     - INTERNAL_SIZE_T might be signed or unsigned, might be 32 or 64 bits,
       and might be the same width as int or as long
     - size_t might have different width and signedness as INTERNAL_SIZE_T
     - int and long might be 32 or 64 bits, and might be the same width
   To deal with this, most comparisons and difference computations
   among INTERNAL_SIZE_Ts should cast them to unsigned long, being
   aware of the fact that casting an unsigned int to a wider long does
   not sign-extend. (This also makes checking for negative numbers
   awkward.) Some of these casts result in harmless compiler warnings
   on some systems.  */
#ifndef INTERNAL_SIZE_T
# define INTERNAL_SIZE_T size_t
#endif

/* The corresponding word size.  */
#define SIZE_SZ (sizeof (INTERNAL_SIZE_T))

/* The corresponding bit mask value.  */
#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)

/* MALLOC_ALIGNMENT is the minimum alignment for malloc'ed chunks.  It
   must be a power of two at least 2 * SIZE_SZ, even on machines for
   which smaller alignments would suffice. It may be defined as larger
   than this though. Note however that code and data structures are
   optimized for the case of 8-byte alignment.  */
#define MALLOC_ALIGNMENT (2 * SIZE_SZ < __alignof__ (long double) \
              ? __alignof__ (long double) : 2 * SIZE_SZ)

一般来说， size_t 被定义为 unsigned long ，其在 64 位中是 64 位无符号整数，32 位中是 32 位无符号整数。

接下来逐个解释chunk结构体的各个字段

结构体设计的 “误导性”

注释提到该结构体是一种 “视图（view）”，原因在于：

  • 双重角色：同一个结构体既要表示已分配的内存块，也要表示空闲的内存块。

  • 字段复用

    ：

    • 当 chunk 被分配时，fd 和 bk 指针不使用（被应用程序数据覆盖）。
    • 仅当 chunk 空闲时，fd 和 bk 才构成双向链表，用于快速查找可用内存。

  • prev_size

    • 若物理相邻的前一个 chunk 是空闲的，则存储其大小（包括chunk头）。
    • 若物理相邻的前一个 chunk 已分配，则该字段被前一个 chunk 的数据覆盖（节省空间）。

  • **size**该chunk的大小，大小必须是MALLOC_ALIGNMENT的整数倍。如果申请的内存大小不是MALLOC_ALIGNMENT的整数倍，会被转换为满足大小的最小的MALLOC_ALIGNMENT的倍数，这通过request2size()宏完成。32位系统中，MALLOC_ALIGNMENT可能是 4 或 8 ；64位系统中，MALLOC_ALIGNMENT是 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时挨个遍历 ，加速寻找过程

自 glibc 2.26 版本起，在 32 位 glibc 中，MALLOC_ALIGNMENT 宏的定义在编译时优先选择 sysdeps/i386/malloc-alignment.h 当中的定义，该值定义为一个常量：

1
#define MALLOC_ALIGNMENT 16

因此，对于自 2.26 版本起始的 32 位 glibc，其 MALLOC_ALIGNMENT 并非基于 SIZE_SZ 计算的 8 ，而是和 64 位 glibc 所用值相同的 16。

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

当一个 chunk 处于使用状态时，它的下一个 chunk 的 prev_size 域无效，所以下一个 chunk 的该部分也可以被当前 chunk 使用。这就是 chunk 中的空间复用。

1

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

1

可以发现，如果一个 chunk 处于 free 状态，那么会有两个位置记录其相应的大小

  1. 本身的 size 字段会记录，
  2. 它后面的 chunk 会记录。

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

chunk 相关宏

介绍一些宏定义里用到的内存计算指令

按位取反（~）

~7 = 0xFFFFFFF8

47 & ~7 = 47 & 0xFFFFFFF8 = 40（将数值 47 向下舍入到 8 字节对齐 的边界，即找到 ≤47 且为 8 的倍数 的最大数值）

&按位与（Bitwise AND）运算，用于将数值 47 对齐到 8 字节边界

这里主要介绍chunk的大小、对齐检查以及一些转换的宏

chunk 与 mem 指针头部的转换

mem 指向用户得到的内存的起始位置

1
2
3
/*从 malloc 头部（chunk）到用户指针（mem）的转换，以及反向转换。*/
#define chunk2mem(p) ((void *) ((char *) (p) + 2 * SIZE_SZ))
#define mem2chunk(mem) ((mchunkptr)((char *) (mem) -2 * SIZE_SZ))
  • chunk2mem(p)：将 chunk 指针（指向 malloc_chunk 结构体）转换为用户实际可用的内存指针（跳过 prev_size 和 size 字段，指向用户数据区起始位置）。
  • mem2chunk(mem)：将用户内存指针反向转换为 chunk 指针（回溯两个 SIZE_SZ 大小的偏移，指向 malloc_chunk 结构体起始位置）。
  • 关键：SIZE_SZ 为 INTERNAL_SIZE_T 的字节数（32 位系统为 4，64 位为 8），因此偏移量为 2 * SIZE_SZ（即 prev_size 和 size 字段总长度）。

最小的chunk大小

1
2
/* 最小可能的 chunk 大小。 */
#define MIN_CHUNK_SIZE (offsetof(struct malloc_chunk, fd_nextsize))
  • 使用 offsetof 计算 malloc_chunk 结构体中 fd_nextsize 字段的偏移量，即 chunk 至少需包含 prev_size、size、fd、bk 字段（fd_nextsize 为 large bin 专用，最小块不包含）。
  • 实际含义：最小 chunk 大小为 2 * SIZE_SZ（prev_size + size） + 2 * sizeof(void*)（fd + bk），确保双向链表基本结构。

最小申请的堆内存大小

用户最小申请的内存大小必须是 2*SIZE_SE 的最下整数倍

注：就目前而看 MIN_CHUNK_SIZE 和 MINSIZE 大小是一致的

1
2
3
4
5
/* malloc 能申请的最小大小为对齐后的最小块 */
//MALLOC_ALIGN_MASK = 2 * SIZE_SZ -1
#define MINSIZE                                                                \
    (unsigned long) (((MIN_CHUNK_SIZE + MALLOC_ALIGN_MASK) &                   \
                      ~MALLOC_ALIGN_MASK))
  • MALLOC_ALIGN_MASK 为对齐掩码（值为 MALLOC_ALIGNMENT - 1，如 64 位系统为 0xf）。
  • 计算逻辑：将 MIN_CHUNK_SIZE 向上对齐到 MALLOC_ALIGNMENT 的倍数，确保内存地址对齐（如 64 位系统对齐 16 字节）。
  • 示例：若 MIN_CHUNK_SIZE 为 0x20（32 字节），MALLOC_ALIGNMENT 为 16，则 MINSIZE 为 0x20（已对齐）。

检查分配给用户的内存是否对齐

2 * SIZE_SZ 大小对齐

1
2
3
4
5
6
7
/* 检查 m 是否符合对齐要求 */
// MALLOC_ALIGN_MASK = 2 * SIZE_SZ -1
#define aligned_OK(m) (((unsigned long) (m) & MALLOC_ALIGN_MASK) == 0)

#define misaligned_chunk(p)                                                    \
    ((uintptr_t)(MALLOC_ALIGNMENT == 2 * SIZE_SZ ? (p) : chunk2mem(p)) &       \
     MALLOC_ALIGN_MASK)

请求字节数判断

1
2
3
4
5
6
/*
  检查请求是否过大，导致在填充和对齐后其值会绕零回环（即溢出）。为简化其他代码逻辑，边界值被设得足够低，确保加上最小尺寸（MINSIZE）后也不会发生绕零回环。
 */

#define REQUEST_OUT_OF_RANGE(req)                                              \
    ((unsigned long) (req) >= (unsigned long) (INTERNAL_SIZE_T)(-2 * MINSIZE))

将用户请求内存大小转为实际分配内存大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 将用户请求的字节数转换为可用的块大小（内部版本） */
//MALLOC_ALIGN_MASK = 2 * SIZE_SZ -1
#define request2size(req)                                                      \
    (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)                           \
         ? MINSIZE                                                             \
         : ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

/*  相同，但同时执行参数检查 */

#define checked_request2size(req, sz)                                          \
    if (REQUEST_OUT_OF_RANGE(req)) {                                           \
        __set_errno(ENOMEM);                                                   \
        return 0;                                                              \
    }                                                                          \
    (sz) = request2size(req);
  • 步骤 1：判断请求大小 req 加上 SIZE_SZ（预留 size 字段空间）和对齐掩码后的总大小是否小于 MINSIZE。
  • 步骤 2：若小于，直接返回 MINSIZE（强制分配最小块）；否则，通过掩码对齐到 MALLOC_ALIGNMENT 的倍数。
  • 核心逻辑：确保用户数据区大小为 req，但整个 chunk 需包含头部（prev_size 和 size）并满足对齐要求。

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

  1. 首先，利用 REQUEST_OUT_OF_RANGE 判断是否可以分配用户请求的字节大小的 chunk。
  2. 其次，需要注意的是用户请求的字节是用来存储数据的，即 chunk header 后面的部分。与此同时，由于 chunk 间复用，所以可以使用下一个 chunk 的 prev_size 字段。因此，这里只需要再添加 SIZE_SZ 大小即可以完全存储内容。
  3. 由于系统中所允许的申请的 chunk 最小是 MINSIZE，所以与其进行比较。如果不满足最低要求，那么就需要直接分配 MINSIZE 字节。
  4. 如果大于的话，因为系统中申请的 chunk 需要 2 * SIZE_SZ 对齐，所以这里需要加上 MALLOC_ALIGN_MASK 以便于对齐。

标记位相关

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* 当相邻的前一个内存块（chunk）被使用时，size字段会与PREV_INUSE进行按位或操作 */
#define PREV_INUSE 0x1

/* 提取前一个内存块的使用状态位 */
#define prev_inuse(p) ((p)->mchunk_size & PREV_INUSE)

/* 如果内存块是通过mmap()分配的，size字段会与IS_MMAPPED进行按位或操作 */
#define IS_MMAPPED 0x2

/* 检查内存块是否通过mmap()分配 */
#define chunk_is_mmapped(p) ((p)->mchunk_size & IS_MMAPPED)

/* 如果内存块来自非主分配区（non-main arena），size字段会与NON_MAIN_ARENA进行按位或操作。
   该标志仅在必要时，在将内存块交给用户前设置。 */
#define NON_MAIN_ARENA 0x4

/* 检查内存块是否来自主分配区 */
#define chunk_main_arena(p) (((p)->mchunk_size & NON_MAIN_ARENA) == 0)

/* 将内存块标记为非主分配区 */
#define set_non_main_arena(p) ((p)->mchunk_size |= NON_MAIN_ARENA)

/*
   提取内存块大小时需要屏蔽的位
   注意：在设计上，对于不应该出现mmap内存块的宏，IS_MMAPPED标志不会从size字段中屏蔽。
   这可以在有人意外扩展或修改此malloc实现时，通过核心转储（core dump）提供有效提示。
*/
#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)

**获取 chunk size **

1
2
3
4
5
/* 获取内存块大小（忽略使用标志位） */
#define chunksize(p) (chunksize_nomask(p) & ~(SIZE_BITS))

/* 与 chunksize 功能类似，但不屏蔽 SIZE_BITS 标志位  */
#define chunksize_nomask(p) ((p)->mchunk_size)

获取下一个物理相邻的 chunk

1
2
/* 指向下一个物理相邻的 chunk 指针。 */
#define next_chunk(p) ((mchunkptr)(((char *) (p)) + chunksize(p)))

通过 chunksize(p) 获取当前块总大小（含头部），计算下一块起始地址（当前地址 + 块大小）

获取前一个 chunk 的信息

1
2
3
4
5
6
7
8
/* 获取 p 下方块的大小，仅当前一块空闲时有效。  */
#define prev_size(p) ((p)->mchunk_prev_size)

/* 设置 p 下方块的大小。仅当 !prev_inuse(P) 时有效。  */
#define set_prev_size(p, sz) ((p)->mchunk_prev_size = (sz))

/* 指向物理上前一个 malloc_chunk 的指针。仅当 !prev_inuse(P) 时有效  */
#define prev_chunk(p) ((mchunkptr)(((char *) (p)) - prev_size(p)))

当前 chunk 使用状态相关操作

1
2
3
4
5
6
7
8
9
10
11
/* 提取 p 的使用状态位 */
#define inuse(p)                                                               \
    ((((mchunkptr)(((char *) (p)) + chunksize(p)))->mchunk_size) & PREV_INUSE)
    
/* 提取 p 的使用状态位 */
#define inuse(p)                                                               \
    ((((mchunkptr)(((char *) (p)) + chunksize(p)))->mchunk_size) & PREV_INUSE)
    
/* 清除块的使用状态标记，不干扰其他标志 */
#define clear_inuse(p)                                                         \
    ((mchunkptr)(((char *) (p)) + chunksize(p)))->mchunk_size &= ~(PREV_INUSE)

设置 chunk 的 size 字段

1
2
3
4
5
6
7
8
9
10
/* 设置头部的大小，不干扰其使用标志位 */
#define set_head_size(p, s)                                                    \
    ((p)->mchunk_size = (((p)->mchunk_size & SIZE_BITS) | (s)))

/* 设置头部的大小/使用标志字段 */
#define set_head(p, s) ((p)->mchunk_size = (s))

/* 设置尾部的大小（仅当内存块未被使用时） */
#define set_foot(p, s)                                                         \
    (((mchunkptr)((char *) (p) + (s)))->mchunk_prev_size = (s))

获取指定偏移的 chunk

1
2
/* 将 ptr + offset 位置的空间视为一个 chunk */
#define chunk_at_offset(p, s) ((mchunkptr)(((char *) (p)) + (s)))

指定偏移处 chunk 使用状态相关操作

1
2
3
4
5
6
7
8
9
10
11
/* 检查 p + s 位置的内存块的使用状态位 */
#define inuse_bit_at_offset(p, s)                                              \
    (((mchunkptr)(((char *) (p)) + (s)))->mchunk_size & PREV_INUSE)

/* 设置 p + s 位置的内存块为已使用状态 */
#define set_inuse_bit_at_offset(p, s)                                          \
    (((mchunkptr)(((char *) (p)) + (s)))->mchunk_size |= PREV_INUSE)

/* 清除 p + s 位置的内存块的使用状态标志 */
#define clear_inuse_bit_at_offset(p, s)                                        \
    (((mchunkptr)(((char *) (p)) + (s)))->mchunk_size &= ~(PREV_INUSE))

bin

概述

  • bin 本质是双向链表，用于链接空闲的chunk。每 bin的 header 包含两个指针：
    • fd（forward）：指向下一个空闲 chunk。
    • bk（backward）：指向前一个空闲 chunk。
  • 由于 malloc_chunk 结构体中天然包含 fd 和 bk 字段（仅在空闲时使用），bin 的 header 可以直接作为链表的 “虚拟头结点”，方便插入、删除操作。

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

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

对于small bins，large bins，unsorted bin来说，ptmalloc将它们维护在同一个数组中。这些 bin 对应的数据结构在 malloc_state 中，如下

1
2
3
#define NBINS 128
/*  如上文所述打包的常规 bins */
mchunkptr bins[ NBINS * 2 - 2 ];

bins 主要用于索引不同 bin 的 fd 和 bk。

为了简化在双链接列表中的使用，每个 bin 的header都设置为 malloc_chunk 类型。这样可以避免 header 类型及其特殊处理。但是，为了节省空间和提高局部性，只分配 bin 的fd/bk 指针，然后使用repositioning tricks 将这些指针视为一个malloc_chunk*的字段。

以32位系统为例，bins前4项的含义如下

含义 bin1 的 fd/bin2 的 prev_size bin1 的 bk/bin2 的 size bin2 的 fd/bin3 的 prev_size bin2 的 bk/bin3 的 size
bin 下标 0 1 2 3

可以看到，bin2 的 prev_size、size 和 bin1 的 fd、bks是重合的。由于我们只会使用 fd 和 bk 来索引链表，所以该重合部分的数据其实记录的是 bin1 的 fd 、bk。也就是说，虽然后一个 bin 和前一个 bin 共用部分数据，但是其实记录的仍然是前一个 bin 的链表数据。通过这样的复用，可以节省空间。

数组中的 bin 依次如下

1.第一个为 unsorted bin（未排序的箱子），这里面的chunk没有进行排序，存储的chunk比较杂。

2.索引从2到63的 bin 称为 small bin，同一个 small bin 链表中的chunk的大小相同。两个相邻索引的 small bin 链表中的chunk大小相差的字节数为2个机器字长，即32位相差8字节，64位相差16字节。

3.small bins 后面的 bin 被称作 large bins。large bins中的每一个 bin 都包含一定范围内的 chunk，其中的 chunk 按 fd 指针的顺序从大到小排列。相同大小的chunk同样按照最近使用顺序排列。

此外，上述这些 bin 的排布都会遵循一个原则: 任意两个物理相邻的空闲 chunk 不能在一起

示例：若内存中有块 A（已用）、块 B（空闲）、块 C（空闲），则块 B 和 C 因物理相邻违反规则，需通过分配其他数据或合并为一个大块来调整。

需要注意的是，并不是所有的chunk被释放后就立即被放到 bin 中。ptmalloc 为了提高分配的速度，会把一些小的chunk先放到 fast bins 的容器内。而且，fastbin容器中的chunk的使用标记总是被置位的，所以不满足上面的原则。

bin 通用的宏如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct malloc_chunk *mbinptr;

/* addressing -- note that bin_at(0) does not exist */
#define bin_at(m, i)                                                           \
    (mbinptr)(((char *) &((m)->bins[ ((i) -1) * 2 ])) -                        \
              offsetof(struct malloc_chunk, fd))

/* analog of ++bin */
//获取下一个bin的地址
#define next_bin(b) ((mbinptr)((char *) (b) + (sizeof(mchunkptr) << 1)))

/* Reminders about list directionality within bins */
// 这两个宏可以用来遍历bin
// 获取 bin 的位于链表头的 chunk
#define first(b) ((b)->fd)
// 获取 bin 的位于链表尾的 chunk
#define last(b) ((b)->bk)

Fast Bin

大多数程序经常会申请以及释放一些比较小的内存块。如果将一些较小的chunk释放之后发现存在与之相邻的空闲的chunk并将它们进行合并，那么当下一次再次申请相应大小的chunk时，就需要对chunk进行分割，这样就大大降低了堆的利用效率。因为我们把大部分时间花在了合并、分割以及中间检查的过程中。因此，prmalloc中专门设计了 fast bin，对应的变量就是malloc state 中的 fastbinsY

1
2
3
4
5
6
7
8
9
10
*/快速链表
一个存储最近释放的小块内存的链表数组。快速链表不是双向链表。将它们单向链接会更快，而且由于内存块永远不会从这些链表的中间移除，所以双向链接没有必要。此外，与常规链表不同，它们甚至不以先进先出（FIFO）顺序处理（它们使用更快的后进先出（LIFO）顺序），因为在通常使用快速链表的临时环境中，顺序并不是很重要。
快速链表中的内存块保持其使用位被设置，因此它们不能与其他空闲内存块合并。malloc_consolidate 函数会释放快速链表中的所有内存块，并将它们与其他空闲内存块合并*/
typedef struct malloc_chunk *mfastbinptr;

/*
    This is in malloc_state.
    /* Fastbins */
    mfastbinptr fastbinsY[ NFASTBINS ];
*/

为了更加高效地利用 fast bin，glibc采用单向链表对其中的每个bin进行组织，并且每个bin采取LIFO策略(后进先出)，最近释放的chunk会更早的被分配，所以会更加适合于局部性。也就是说，当用户需要的chunk的大小小于 fastbin 的最大大小时，ptmalloc会首先判断 fastbin 中相应的 bin 中是否有对应大小的空闲块，如果有的话，就会直接从这个 bin 中获取 chunk。如果没有的话，ptmalloc才会做接下来的一系列操作。

默认情况下(32位系统为例)，fast bin中默认支持最大的chunk的数据空间大小为64字节。但是其可以支持的chunk的数据空间最大为0x80字节。除此之外，fast bin 最多可以支持的 bin 的个数为10个，从数据空间为8字节开始一直到80字节(这里说的大小是数据空间的大小，也就是除去prev_size和size字段部分的大小)

定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#define NFASTBINS (fastbin_index(request2size(MAX_FAST_SIZE)) + 1)

#ifndef DEFAULT_MXFAST
#define DEFAULT_MXFAST (64 * SIZE_SZ / 4)
#endif

/* 我们支持的最大快速堆块请求大小 */
#define MAX_FAST_SIZE (80 * SIZE_SZ / 4)

/*
   由于max_fast的最低2位在尺寸比较中无关紧要，因此被用作标志位。
*/

/*
   max_fast中存储的FASTCHUNKS_BIT标志表示可能存在一些快速箱块（fastbin chunk）。
   当有块进入任何快速箱时，该标志设为真；仅在malloc_consolidate函数中清除该标志。

   真值取反设计是为了在启动时have_fastchunks默认为真（因为静态变量初始化为零），简化初始化检查。
*/
// 判断分配区是否存在快速箱块，1表示不存在
#define FASTCHUNKS_BIT (1U)

#define have_fastchunks(M) (((M)->flags & FASTCHUNKS_BIT) == 0)
#define clear_fastchunks(M) catomic_or(&(M)->flags, FASTCHUNKS_BIT)
#define set_fastchunks(M) catomic_and(&(M)->flags, ~FASTCHUNKS_BIT)

/*
   NONCONTIGUOUS_BIT标志表示MORECORE不会返回连续内存区域。
   否则，在可能的情况下，会利用连续性合并连续MORECORE调用的结果。

   初始值来自MORECORE_CONTIGUOUS，但如果使用mmap作为sbrk的替代方案，该值会动态改变。
*/
// 判断MORECORE是否返回连续内存区域：
// 主分配区的MORECORE对应sbrk()，默认返回连续虚拟地址空间；
// 非主分配区使用mmap()分配大块内存并切分，而mmap默认不保证地址连续，因此非主分配区默认非连续。
#define NONCONTIGUOUS_BIT (2U)

#define contiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) == 0)
#define noncontiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) != 0)
#define set_noncontiguous(M) ((M)->flags |= NONCONTIGUOUS_BIT)
#define set_contiguous(M) ((M)->flags &= ~NONCONTIGUOUS_BIT)

/*
   若检测到分配区（arena）存在内存损坏，则设置ARENA_CORRUPTION_BIT标志。
   此类分配区不再用于分配内存块，且检测到损坏前已分配的块不会被释放。
*/
#define ARENA_CORRUPTION_BIT (4U)

#define arena_is_corrupt(A) (((A)->flags & ARENA_CORRUPTION_BIT))
#define set_arena_corrupt(A) ((A)->flags |= ARENA_CORRUPTION_BIT)

/*
   设置max_fast的值：
   - 若参数为0，则使用极小值（避免影响正常分配）。
   - 前置条件：当前无快速箱块存在。
   - 设置该值时会清除fastchunk标志，但保留非连续标志（noncontiguous bit）。
*/
#define set_max_fast(s)                                                        \
    global_max_fast =                                                          \
        (((s) == 0) ? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
#define get_max_fast() global_max_fast

ptmalloc 默认情况下会调用 set_max_fast(s) 将全局变量 global_max_fast 设置为 DEFAULT_MXFAST，也就是设置 fast bins 中 chunk 的最大值。当 MAX_FAST_SIZE 被设置为 0 时，系统就不会支持 fast bins 。

fastbin 的索引

1
2
3
4
5
6
7
#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[ idx ])

/* offset 2 to use otherwise unindexable first 2 bins */
// chunk size=2*size_sz*(2+idx)
// 这里要减2，否则的话，前两个bin没有办法索引到。
#define fastbin_index(sz)                                                      \
    ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)

需要特别注意的是，fastbin 范围的 chunk 的 inuse 始终被置为 1。因此它们不会和其它被释放的 chunk 合并。

但是当释放的 chunk 与该 chunk 相邻的空闲 chunk 合并后的大小大于 FASTBIN_CONSOLIDATION_THRESHOLD 时，内存碎片可能比较多了，我们就需要把 fast bins 中的 chunk 都进行合并，以减少内存碎片对系统的影响。

1
2
3
4
5
/*
   FASTBIN_CONSOLIDATION_THRESHOLD是free()函数中一个块的大小，当达到这个大小，就会触发对可能相邻的快速链表块进行自动合并。这是一种启发式方法，所以具体的值并没有太大影响。它被定义为默认修剪阈值的一半，这是一种折中的启发式策略，即只有在可能导致修剪的情况下才尝试合并。然而，它不能动态调整，因为即使不使用修剪，合并也能减少大块周围的碎片。
 */

#define FASTBIN_CONSOLIDATION_THRESHOLD (65536UL)

malloc_consolidate 函数可以将 fastbin 中所有能和其它 chunk 合并的 chunk 合并在一起。具体地参见后续的详细函数的分析。

1
2
3
/*
   快速链表（fastbins）中的块会保持其已使用位（inuse bit）被设置，因此它们不能与其他空闲块合并。malloc_consolidate 函数会释放快速链表中的所有块，并将它们与其他空闲块合并。
 */

small bin

small bins中每个chunk的大小与其所在的 bin 的index的关系为: chunk_size = 2 * SIZE_SZ*index，具体如下

下标 SIZE_SZ=4（32 位） SIZE_SZ=8（64 位）
2 16 32
3 24 48
4 32 64
5 40 80
x 2*4*x 2*8*x
63 504 1008

small bins 中一共有62个循环双向链表，每个链表中存储的chunk大小都一致。比如对于32位系统来说，下标2对应的双向链表中存储的chunk大小均为16字节。每个链表都有链表头节点，这样可以方便对于链表内部结点的管理。此外，**small bins中每个 bin 对应的链表采用 FIFO 的规则(先进先出)**，所以同一个链表中先被释放的chunk会先被分配出去

small bin 相关的宏如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define NSMALLBINS 64
#define SMALLBIN_WIDTH MALLOC_ALIGNMENT
// 是否需要对small bin的下标进行纠正
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)

#define MIN_LARGE_SIZE ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)
//判断chunk的大小是否在small bin范围内
#define in_smallbin_range(sz)                                                  \
    ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)
// 根据chunk的大小得到small bin对应的索引。
#define smallbin_index(sz)                                                     \
    ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4)                          \
                           : (((unsigned) (sz)) >> 3)) +                       \
     SMALLBIN_CORRECTION)

或许，大家会很疑惑，那 fast bin 与 small bin 中 chunk 的大小会有很大一部分重合啊，那 small bin 中对应大小的 bin 是不是就没有什么作用啊？ 其实不然，fast bin 中的 chunk 是有可能被放到 small bin 中去的，我们在后面分析具体的源代码时会有深刻的体会。

Large Bin

large bins 中一共包括 63 个 bin，每个 bin 中的 chunk 的大小不一致，而是处于一定区间范围内。此外，这 63 个 bin 被分成了 6 组，每组 bin 中的 chunk 大小之间的公差一致，具体如下：

组 数量 公差
1 32 64B
2 16 512B
3 8 4096B
4 4 32768B
5 2 262144B
6 1 不限制

这里我们以32位平台的large bin 为例，第一个large bin 的其实chunk大小为512字节，位于第一组，所以该bin可以存储的chunk的大小范围为[512,512+64）。

关于large bin 的宏如下，这里我们以32位平台下，第一个large bin 的起始chunk大小为例，为512字节

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#define largebin_index_32(sz)                                                  \
    (((((unsigned long) (sz)) >> 6) <= 38)                                     \
         ? 56 + (((unsigned long) (sz)) >> 6)                                  \
         : ((((unsigned long) (sz)) >> 9) <= 20)                               \
               ? 91 + (((unsigned long) (sz)) >> 9)                            \
               : ((((unsigned long) (sz)) >> 12) <= 10)                        \
                     ? 110 + (((unsigned long) (sz)) >> 12)                    \
                     : ((((unsigned long) (sz)) >> 15) <= 4)                   \
                           ? 119 + (((unsigned long) (sz)) >> 15)              \
                           : ((((unsigned long) (sz)) >> 18) <= 2)             \
                                 ? 124 + (((unsigned long) (sz)) >> 18)        \
                                 : 126)

#define largebin_index_32_big(sz)                                              \
    (((((unsigned long) (sz)) >> 6) <= 45)                                     \
         ? 49 + (((unsigned long) (sz)) >> 6)                                  \
         : ((((unsigned long) (sz)) >> 9) <= 20)                               \
               ? 91 + (((unsigned long) (sz)) >> 9)                            \
               : ((((unsigned long) (sz)) >> 12) <= 10)                        \
                     ? 110 + (((unsigned long) (sz)) >> 12)                    \
                     : ((((unsigned long) (sz)) >> 15) <= 4)                   \
                           ? 119 + (((unsigned long) (sz)) >> 15)              \
                           : ((((unsigned long) (sz)) >> 18) <= 2)             \
                                 ? 124 + (((unsigned long) (sz)) >> 18)        \
                                 : 126)

// XXX 目前尚不清楚，保持桶的宽度不变是否合适，还是也应该按系数 2 进行缩放。

#define largebin_index_64(sz)                                                  \
    (((((unsigned long) (sz)) >> 6) <= 48)                                     \
         ? 48 + (((unsigned long) (sz)) >> 6)                                  \
         : ((((unsigned long) (sz)) >> 9) <= 20)                               \
               ? 91 + (((unsigned long) (sz)) >> 9)                            \
               : ((((unsigned long) (sz)) >> 12) <= 10)                        \
                     ? 110 + (((unsigned long) (sz)) >> 12)                    \
                     : ((((unsigned long) (sz)) >> 15) <= 4)                   \
                           ? 119 + (((unsigned long) (sz)) >> 15)              \
                           : ((((unsigned long) (sz)) >> 18) <= 2)             \
                                 ? 124 + (((unsigned long) (sz)) >> 18)        \
                                 : 126)

#define largebin_index(sz)                                                     \
    (SIZE_SZ == 8 ? largebin_index_64(sz) : MALLOC_ALIGNMENT == 16             \
                                                ? largebin_index_32_big(sz)    \
                                                : largebin_index_32(sz))

Unsorted Bin

unsorted bin 可以视为空闲 chunk 回归其所属 bin 之前的缓冲区。

其在 glibc 中具体的说明如下

1
2
3
4
5
/*
   未排序块
所有因块分割产生的剩余部分，以及所有返回的块，
首先会被放入 “未排序” 桶中。然后，在 malloc 为它们提供一次在入桶前被使用的机会后，这些块会被放入常规桶中。所以，基本上，未排序块列表就像一个队列，块在 free（以及 malloc_consolidate）操作中被放入该列表，而在 malloc 操作中被取出（要么被使用，要么被放入桶中）。未排序块永远不会设置 NON_MAIN_ARENA 标志，所以在进行大小比较时无需考虑该标志。
 */

在 ptmalloc 内存管理机制中，NON_MAIN_ARENA flag 是malloc_chunk结构体中size字段的一个标志位，用于表示当前chunk是否属于主线程的分配区（main arena）

从下面的宏我们可以看出

1
2
/* 无法索引的 1 号 bin 用于存放未排序的块。 */
#define unsorted_chunks(M) (bin_at(M, 1))

unsorted bin 处于我们之前所说的 bin 数组下标 1 处。故而 unsorted bin 只有一个链表。unsorted bin 中的空闲 chunk 处于乱序状态，主要有两个来源

  • 当一个较大的 chunk 被分割成两半后，如果剩下的部分大于 MINSIZE，就会被放到 unsorted bin 中。
  • 释放一个不属于 fast bin 的 chunk，并且该 chunk 不和 top chunk 紧邻时，该 chunk 会被首先放到 unsorted bin 中。关于 top chunk 的解释，请参考下面的介绍。

此外，Unsorted Bin 在使用的过程中，采用的遍历顺序是 FIFO 。