1. 前言

musl libc 是一个专门为嵌入式系统开发的轻量级 libc 库，以简单、轻量和高效率为特色。有不少 Linux 发行版将其设为默认的 libc 库，用来代替体积臃肿的 glibc ，如 Alpine Linux（做过 Docker 镜像的应该很熟悉）、OpenWrt（常用于路由器）和 Gentoo 等。

作者在写该篇文章的时候，musl最新发布版本是1.2.2。据作者所知 musl-1.2.0 和 musl-1.2.1 中malloc的算法是不同的，由于历史malloc算法（1.2.0及之前）存在缺陷，所以1.2.1版本中进行了算法重构，新版malloc命名为mallocng，老版malloc命名为oldmalloc。本文是对musl-1.2.0的内存管理进行分析，关于新版内存管理算法将来会在另外文章中介绍。

本文所说的内存管理，主要是指堆内存管理，所以，如无特殊说明，下文出现的内存即表示堆内存。

2. 设计思想

malloc的设计思想如下：

In principle, this memory allocator is roughly equivalent to Doug
Lea's dlmalloc with fine-grained locking.

malloc:

Uses a freelist binned by chunk size, with a bitmap to optimize
searching for the smallest non-empty bin which can satisfy an
allocation. If no free chunks are available, it creates a new chunk of
the requested size and attempts to merge it with any existing free
chunk immediately below the newly created chunk.

Whether the chunk was obtained from a bin or newly created, it's
likely to be larger than the requested allocation. malloc always
finishes its work by passing the new chunk to realloc, which will
split it into two chunks and free the tail portion.

原则上，这个内存分配器大致相当于 Doug Lea 的带有细粒度锁定的 dlmalloc。

malloc：

• 使用按块（chunk）大小分箱（bin）的空闲列表，并使用位图（bitmap）来优化搜索可以满足分配的最小非空分箱（bin）。 如果没有可用的空闲块，它会创建一个具有请求大小的新块，并尝试将其与紧邻新创建的块下方的任何现有空闲块合并。
• 无论块是从 bin 获得还是新创建的，它都可能大于请求的分配。malloc 总是通过将新块传递给 realloc 来完成其工作，realloc 会将其拆分为两个块并释放尾部。

这里出现了两个术语：chunk 和 bin。想要更好的理解这两个术语，可能要对堆内存管理知识有一定的了解才行。这两个术语被用在很多堆内存管理算法中。

• chunk
  区块，表示内存块，是内存管理中分配的基本单位。内存空间会被分成连续的、大小不一的chunk。内存管理器的核心目的就是能够高效地分配和回收这些内存块（chunk）。

  这些chunk可以大致分为两类：

  • allocated chunk：已分配的chunk，即被使用的chunk
  • free chunk：空闲的chunk，即未被使用的chunk

• bin
  bin是一种记录free chunk的链表数据结构，不同内存管理中可能也会对bin进行分类，主要是按free chunk的大小进行不同程度的分组。

3. malloc本质

在linux平台上，malloc本质上都是通过系统调用brk或者mmap从操作系统获取内存，可以参考 Syscalls used by malloc。

1、brk是将数据段(.data)的最高地址指针_edata往高地址推；
2、mmap是在进程的虚拟地址空间中（堆和栈中间，称为文件映射区域的地方）找一块空闲的虚拟内存。

这两种方式分配的都是虚拟内存，没有分配物理内存。在第一次访问已分配的虚拟地址空间的时候，发生缺页中断，操作系统负责分配物理内存，然后建立虚拟内存和物理内存之间的映射关系。

musl中的内存是分别通过这两种方式来获取的。

3.1. brk

brk 通过增加程序中断位置 (brk) 从内核获取（非零初始化的）内存。 最初，堆段的起始 (start_brk) 和结束 (brk) 将指向相同的位置。

• 当 ASLR 关闭时，start_brk 和 brk 将指向 data/bss 段的结尾（end_data）。
• 当 ASLR 打开时，start_brk 和 brk 将等于 data/bss 段的结尾（end_data）加上随机 brk 偏移量。

上图“进程虚拟内存布局”图中start_brk是堆段的开始，brk（程序中断）是堆段的结束

3.1.1. 举例

系统调用brk通过直接推高堆顶指针来实现虚拟内存的分配，如下图所示：

第一次访问该内存时触发缺页异常再分配物理内存。操作系统回收内存的时候需要按照顺序回收，上图中需要先回收B，再回收A，brk适于分配小块内存。

3.2. mmap

malloc 使用 mmap 创建私有匿名映射段。私有匿名映射的主要目的是分配（零填充的）新内存，而这个新内存将专门由调用进程使用。

3.2.1. 举例

系统调用mmap直接在堆栈之间分配一大块内存，可以单独释放，适用于分配大块的内存，如下图中的C：

4. 数据结构

4.1. chuck 和 bin

4.1.1. chunk 结构

struct chunk {
	size_t psize, csize;
	struct chunk *next, *prev;
};

• psize：表示前一个chunk的大小，最后一位是flag位。
• csize：表示当前chunk的大小，最后一位是flag位。
• *next：当chunk在bin中时，表示指向下一个chunk；当chunk不在bin中时，暂未使用。
• *prev：当chunk在bin中时，表示指向上一个chunk；当chunk不在bin中时，暂未使用。

4.1.2. bin 结构

struct bin {
	volatile int lock[2];
	struct chunk *head;
	struct chunk *tail;
};

• lock[2]：用于锁
• *head：指向第一个chunk
• *tail：指向最后一个chunk

4.1.3. 小结

1）chunk特点

chunk是连续的内存块。

已分配的chunk之间是通过psize和csize进行关联，当前chunk首地址向前移动上一个chunk的大小，可以找到上一个chunk的首地址；当前chunk首地址向后移动当前chunk大小，可以找到下一个chunk的首地址。

空闲的chunk之间是通过next和prev进行关联，通过当前chunk的next指针可以找到下一个chunk的首地址；通过当前chunk的prev指针可以找到上一个chunk的首地址。

flag位是1表示该chunk被使用，flag位是0表示该chunk未使用，未使用的chunk统一由bin表管理。

备注：这里说的chunk是指小内存chunk，大内存chunk不需要进行管理，大内存的chunk的flag位一直是0，所以对于使用中的chunk，flag是0表示大内存，flag是1表示小内存。关于大内存和小内存后续章节会介绍。

2）bin是一种特殊的chunk

bin和chunk结构体的前两个成员类型不同，int用于表示有符号整型数，size_t用于表示无符号整型数，但int和size_t两种类型的大小都等于机器的字长，这就说明两个结构体的前两个成员在空间上是相等的，所以bin可以看成是一种特殊的chunk。可bin又不是真的chunk，所以不需要表示chunk大小，因此前两个成员被用于锁。

3）空bin的特点
bin是一个管理空闲chunk的链表结构，成员head指向第一个chunk，成员tail指向最后一个chunk。由于bin是一种特殊的chunk，当bin链表中无空闲chunk时，head和tail将指向bin结构体的首地址。bin实际就是空闲chunk链表的表头，链表空时，head和tail指针都指向表头。

4.2. 宏

#define SIZE_ALIGN (4*sizeof(size_t)) // 最小的chunk大小
#define SIZE_MASK (-SIZE_ALIGN)
#define OVERHEAD (2*sizeof(size_t)) // chunk的前导大小，psize和csize占用的字节
#define MMAP_THRESHOLD (0x1c00*SIZE_ALIGN) // MMAP阈值，0x1c00*4*sizeof(size_t)，32位上是112KB，64位上是224KB
#define DONTCARE 16
#define RECLAIM 163840  // 160KB

#define CHUNK_SIZE(c) ((c)->csize & -2)	// 清空flag位
#define CHUNK_PSIZE(c) ((c)->psize & -2) // 清空flag位
#define PREV_CHUNK(c) ((struct chunk *)((char *)(c) - CHUNK_PSIZE(c))) // chunk是连续的内存块
#define NEXT_CHUNK(c) ((struct chunk *)((char *)(c) + CHUNK_SIZE(c)))
#define MEM_TO_CHUNK(p) (struct chunk *)((char *)(p) - OVERHEAD)  // 用户使用的memory地址和chunk首地址之间相差OVERHEAD长度
#define CHUNK_TO_MEM(c) (void *)((char *)(c) + OVERHEAD)
#define BIN_TO_CHUNK(i) (MEM_TO_CHUNK(&mal.bins[i].head)) // 取head的地址，然后从内存转换到chunk，因为bin是一种特殊的chunk，所以等于获取bin结构的首地址

#define C_INUSE  ((size_t)1)  // flag位为1，表示申请的内存是小内存，释放时，通过bin链表管理，并不真正释放

#define IS_MMAPPED(c) !((c)->csize & (C_INUSE))  // flag位为0，表示内存是通过mmap分配的大内存，释放时，直接调用munmap释放

4.3. mal 结构

static struct {
	volatile uint64_t binmap;
	struct bin bins[64];
	volatile int free_lock[2];
} mal;

• bitmap：位图，64位每位对应一个bin，1 表示对应bin非空（有空闲chunk），0 表示对应bin空（无空闲chunk）
• bins[64]：bin数组，固定64个bin，表示可以有64个空闲chunk链表
• free_lock[2]：用于锁

5. malloc/free 函数

5.1. 初识 malloc/free 函数

5.1.1. malloc 函数

void *malloc(size_t n)
{
	struct chunk *c;
	int i, j;

	if (adjust_size(&n) < 0) return 0;

	if (n > MMAP_THRESHOLD) {
		size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE;
		char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
			MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
		if (base == (void *)-1) return 0;
		c = (void *)(base + SIZE_ALIGN - OVERHEAD);
		c->csize = len - (SIZE_ALIGN - OVERHEAD);
		c->psize = SIZE_ALIGN - OVERHEAD;
		return CHUNK_TO_MEM(c);
	}

	i = bin_index_up(n);
	for (;;) {
		uint64_t mask = mal.binmap & -(1ULL<<i);
		if (!mask) {
			c = expand_heap(n);
			if (!c) return 0;
			if (alloc_rev(c)) {
				struct chunk *x = c;
				c = PREV_CHUNK(c);
				NEXT_CHUNK(x)->psize = c->csize =
					x->csize + CHUNK_SIZE(c);
			}
			break;
		}
		j = first_set(mask);
		lock_bin(j);
		c = mal.bins[j].head;
		if (c != BIN_TO_CHUNK(j)) {
			if (!pretrim(c, n, i, j)) unbin(c, j);
			unlock_bin(j);
			break;
		}
		unlock_bin(j);
	}

	/* Now patch up in case we over-allocated */
	trim(c, n);

	return CHUNK_TO_MEM(c);
}

malloc的大致逻辑为：
1）如果 n 大小超过了MMAP_THRESHOLD，就直接通过__mmap（内部调用系统调用mmap）进行申请；
2）否则，试图从bin中找一个合适的chunk来分配，如果找不到合适的，就通过expand_heap延展堆空间，然后生成新的chunk；（expand_heap的逻辑是：如果brk可用就用brk，否则继续使用mmap）
3）chunk可能大于用户申请的大小，所以还会涉及到分割/合并等操作。

5.1.2. free 函数

void free(void *p)
{
	if (!p) return;

	struct chunk *self = MEM_TO_CHUNK(p);

	if (IS_MMAPPED(self))
		unmap_chunk(self);
	else
		__bin_chunk(self);
}

free的大致逻辑为：
1）如果内存是通过mmap申请的（较大的内存），就通过unmap_chunk（内部通过系统调用munmap）进行释放。
2）否则，通过__bin_chunk管理这些空闲chunk（较小的内存），并不进行释放。

5.1.3. 小结

1）大内存，小内存

• 大内存：申请大于MMAP_THRESHOLD的内存称为大内存。用户申请大内存时，直接通过系统调用mmap获取；释放时，直接通过系统调用munmap释放。每次都要向操作系统申请。

• 小内存：申请不大于MMAP_THRESHOLD的内存称为小内存。用户申请小内存时，如果bin链表中有合适的空闲chunk，则直接通过空闲chunk获取，否则，通过brk或mmap获取新的内存；释放时，将chunk返还到合适的bin链表中，而不是返还给操作系统。并非每次都要向操作系统申请，已申请到的内存可以重复使用。（若管理不好，可能会导致内存持续增长）

5.2. 解析 malloc 函数

malloc函数的处理逻辑分如下几步：
1）调整用户指定的申请大小
2）若申请大内存，通过mmap进行申请
3）若申请小内存，通过bin链表查找可用空闲chunk，或重新分配新的chunk，然后做chunk分割/合并操作

下面是每一步的详细介绍。

5.2.1. adjust_size 函数

static int adjust_size(size_t *n)
{
	/* Result of pointer difference must fit in ptrdiff_t. */
	if (*n-1 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) {
		if (*n) {
			errno = ENOMEM;
			return -1;
		} else {
			*n = SIZE_ALIGN;
			return 0;
		}
	}
	*n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK;
	return 0;
}

adjust_size用于对申请的大小做调整，如果调整失败，说明本次申请内存失败；如果调整成功，说明可以继续进行内存申请。另外，调整成功后的大小一般都会比用户指定的申请大小大。

5.2.1.1. 数据结构

• ptrdiff_t：是两个指针相减的结果的带符号整数类型，PTRDIFF_MAX定义该类型最大值。
• SIZE_ALIGN：用于chunk的内存大小对齐
• PAGE_SIZE：用于通过mmap申请的内存大小对齐

5.2.1.2. 函数解析

用户调用malloc申请内存，指定的大小有三种情况：0，适中，超大。
1）0：要么申请失败，要么按默认的最小内存申请；
2）适中：一般都会在申请的大小上加一些管理信息大小，再做内存对齐，然后根据调整后的大小进行内存申请；
3）超大：当进行超大内存申请时，将申请失败。

	/* Result of pointer difference must fit in ptrdiff_t. */
	if (*n-1 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) {
		if (*n) {
			errno = ENOMEM;
			return -1;
		} else {
			*n = SIZE_ALIGN;
			return 0;
		}
	}

1）如果申请超大内存，提示无可用内存错误
2）如果申请0大小内存，重新调整大小为默认的最小内存大小

	*n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK;

3）如果申请适中内存，加上chunk中管理信息大小OVERHEAD，再做 + SIZE_ALIGN - 1) & SIZE_MASK 内存对齐，得到新的申请大小。

理解：
假设用户申请的内存大小为n1，调整后的大小为n，此时 n = (n1 + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK。

• 例子1：n1 + OVERHEAD 正好是 SIZE_ALIGN 整数倍，那么 n = n1 + OVERHEAD。
• 例子2：n1 + OVERHEAD 不是 SIZE_ALGIN 整数倍，那么 n > n1 + OVERHEAD 且 n < n1 + OVERHEAD + SIZE_ALIGN。

5.2.2. 申请大内存

	if (n > MMAP_THRESHOLD) {
		size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE;
		char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
			MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
		if (base == (void *)-1) return 0;
		c = (void *)(base + SIZE_ALIGN - OVERHEAD);
		c->csize = len - (SIZE_ALIGN - OVERHEAD);
		c->psize = SIZE_ALIGN - OVERHEAD;
		return CHUNK_TO_MEM(c);
	}

5.2.2.1. 哨兵chunk

每次分配chunk的时候，如果新chunk与之前分配的chunk地址不连续，都会多分配一个零大小的哨兵chunk。哨兵chunk和后面chunk间的内存是连续的，作为chunk的前导，像站岗的哨兵一样。哨兵chunk不关心可用内存，至少预留psize和csize两个成员的空间，因此占用的大小不低于OVERHEAD。

5.2.2.2. 逻辑简析

		size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE;

n 在 adjust_size 函数中已经调整过了，且按SIZE_ALIGN进行了对齐，此处 + OVERHEAD 预留了哨兵chunk。PAGE_SIZE - 1 & -PAGE_SIZE 按页大小对齐。

        c = (void *)(base + SIZE_ALIGN - OVERHEAD);
        c->csize = len - (SIZE_ALIGN - OVERHEAD);
        c->psize = SIZE_ALIGN - OVERHEAD;

上面提到内存的大小按SIZE_ALGIN对齐，因为分配的内存需要预留一个哨兵chunk，又因为SIZE_ALGIN等于2倍OVERHEAD，所以将内存地址向后偏移SIZE_ALGIN，既能能保证内存按SIZE_ALGIN对齐，又能保证预留足够的空间给哨兵chunk。内存地址向前偏移OVERHEAD可以得到chunk首地址，所以c = (void *)(base + SIZE_ALIGN - OVERHEAD)。

SIZE_ALGIN长度内，chunk又占用了OVERHEAD，所以哨兵chunk的大小为 SIZE_ALIGN - OVERHEAD，根据哨兵chunk的大小，初始化当前chunk信息，其中当前chunk的psize等于哨兵chunk的大小，由于csize是偶数，且chunk是通过mmap分配的，所以不需要单独清空flag位，默认flag位就是0。哨兵chunk不关心内存大小，所以不需要初始化哨兵chunk。

思考：内存地址向后偏移了SIZE_AGLIN，那么能保证剩下的内存大小满足用户申请的内存大小吗？
解：假设用户申请的大小是n1，剩下的内存大小是n2，论证过程如下：
1）n 在adjust_size中经过了调整，那么n >= n1 + OVERHEAD 且 n < n1 + OVERHEAD + SIZE_ALIGN，n = x * SIZE_ALGIN。
2）因为len经过了PAGE_SIZE对齐，所以len >= n + OVERHEAD 且 len < n + OVERHEAD + PAGE_SIZE。
3）当n和len都取最小值时，即n = n1 + OVERHEAD，len = n + OVERHEAD = n1 + OVERHEAD + OVERHEAD = n1 + 2 * OVERHEAD，内存地址向后偏移了SIZE_AGLIN，相当于len减去SIZE_AGLIN，所以n2 = len - SIZE_AGLIN = n1 + 2 * OVERHEAD - SIZE_AGLIN。
4）只要SIZE_AGLIN <= 2 * OVERHEAD，就能保证剩下的内存大小满足用户申请的内存大小。目前SIZE_AGLIN = 2 * OVERHEAD，所以剩下的内存大小满足用户申请的内存大小，不会出现内存越界操作。

5.2.2.3. __mmap 函数

#define UNIT SYSCALL_MMAP2_UNIT
#define OFF_MASK ((-0x2000ULL << (8*sizeof(syscall_arg_t)-1)) | (UNIT-1))

void *__mmap(void *start, size_t len, int prot, int flags, int fd, off_t off)
{
	long ret;
	if (off & OFF_MASK) {
		errno = EINVAL;
		return MAP_FAILED;
	}
	if (len >= PTRDIFF_MAX) {
		errno = ENOMEM;
		return MAP_FAILED;
	}
	if (flags & MAP_FIXED) {
		__vm_wait();
	}
#ifdef SYS_mmap2
	ret = __syscall(SYS_mmap2, start, len, prot, flags, fd, off/UNIT);
#else
	ret = __syscall(SYS_mmap, start, len, prot, flags, fd, off);
#endif
	/* Fixup incorrect EPERM from kernel. */
	if (ret == -EPERM && !start && (flags&MAP_ANON) && !(flags&MAP_FIXED))
		ret = -ENOMEM;
	return (void *)__syscall_ret(ret);
}

weak_alias(__mmap, mmap);

weak_alias(mmap, mmap64);

__mmap对外接口是mmap，通过调用系统调用mmap实现内存分配。关于mmap的原理读者可以自行研究。

5.2.3. 申请小内存

	i = bin_index_up(n);
	for (;;) {
		uint64_t mask = mal.binmap & -(1ULL<<i);
		if (!mask) {
			c = expand_heap(n);
			if (!c) return 0;
			if (alloc_rev(c)) {
				struct chunk *x = c;
				c = PREV_CHUNK(c);
				NEXT_CHUNK(x)->psize = c->csize =
					x->csize + CHUNK_SIZE(c);
			}
			break;
		}
		j = first_set(mask);
		lock_bin(j);
		c = mal.bins[j].head;
		if (c != BIN_TO_CHUNK(j)) {
			if (!pretrim(c, n, i, j)) unbin(c, j);
			unlock_bin(j);
			break;
		}
		unlock_bin(j);
	}

	/* Now patch up in case we over-allocated */
	trim(c, n);

5.2.3.1. 逻辑简析

	i = bin_index_up(n);

根据内存大小n，通过bin_index_up查找对应的bin的索引值。

		uint64_t mask = mal.binmap & -(1ULL<<i);

将位图binmap低于i的位清零，大于等于i对应的bin链表上的空闲chunk都能满足内存分配。

		if (!mask) {
			c = expand_heap(n);
			if (!c) return 0;
			if (alloc_rev(c)) {
				struct chunk *x = c;
				c = PREV_CHUNK(c);
				NEXT_CHUNK(x)->psize = c->csize =
					x->csize + CHUNK_SIZE(c);
			}
			break;
		}

mask为0，表示大于等于i对应的bin链表都是空链表，没有空闲chunk可用于分配，所以需要expand_heap扩展堆内存分配新的chunk。
alloc_rev©用于判断前一个chunk是否空闲，如果前一个chunk是空闲的，会将其从bin链表上取下，用于同新chunk进行合并。
合并操作很简单，就是将新chunk的大小和新chunk的下一个chunk的psize进行更新，加上前一个chunk的大小。

思考：新chunk怎么会有下一个chunk呢？
解：新的chunk都是通过expand_heap分配的，expand_heap内部会保证chunk的内存连续性，如果第一次扩展堆，即分配第一个chunk，这时就会多分配一个哨兵chunk。除了哨兵chunk，实际上还有一个尾chunk，它是一个连续chunk的最后一个chunk，和哨兵chunk是一对，一前一后标识着连续内存块的起始和结尾。大内存中没有尾chunk，而小内存中在分配chunk的时候，会预留尾chunk的空间。所以新chunk的下一个chunk就是尾chunk。

		j = first_set(mask);
		lock_bin(j);
		c = mal.bins[j].head;
		if (c != BIN_TO_CHUNK(j)) {
			if (!pretrim(c, n, i, j)) unbin(c, j);
			unlock_bin(j);
			break;
		}
		unlock_bin(j);

大于等于i对应的bin链表可能会有多个是非空的链表，由于bin是分组的，下标越大对应的空闲chunk就越大，所以取最低下标对应的bin上的chunk是最合适的。first_set(mask)获取mask二进制位从低到高第一次出现1的位置，该位置就对应着bins的索引。

bin链表属于共享资源，从bin表上取下合适的chunk需要加锁操作，lock_bin函数除了加锁，如果bin链表未初始化，还会初始化bin链表，即bin结构的head和tail指针指向bin结构体的首地址，标识bin链表是一个空表。

c = mal.bins[j].head 表示c是bin表上的第一个chunk，BIN_TO_CHUNK(j)表示bin结构的首地址，即bin链表的表头，如果第一个chunk和表头相等，说明bin链表是一个空表，所以只有c != BIN_TO_CHUNK(j)时，才有可用的空闲chunk。

找到可用的空闲chunk之后，如果该chunk对应的内存比用户申请的内存大一些，可能需要稍微裁剪一下，如果预裁剪pretrim成功，将会完成裁剪；如果不成功，将该空闲chunk从bin中取下来，等待后续的处理。

	/* Now patch up in case we over-allocated */
	trim(c, n);

裁剪即将被用户使用的chunk，新分配的chunk或未预裁剪成功（某些chunk裁剪下来的chunk需要重新找到合适的bin链表进行挂载，所以不在pretrim中处理）的空闲chunk对应的内存都可能比用户申请的内存大一些，裁剪trim除了保留够用户使用的内存，还会将裁剪下来的chunk重新找到合适的bin链表进行挂载。

5.2.3.2. bin 下标

static const unsigned char bin_tab[60] = {
	            32,33,34,35,36,36,37,37,38,38,39,39,
	40,40,40,40,41,41,41,41,42,42,42,42,43,43,43,43,
	44,44,44,44,44,44,44,44,45,45,45,45,45,45,45,45,
	46,46,46,46,46,46,46,46,47,47,47,47,47,47,47,47,
};

static int bin_index(size_t x)
{
	x = x / SIZE_ALIGN - 1;
	if (x <= 32) return x;
	if (x < 512) return bin_tab[x/8-4];
	if (x > 0x1c00) return 63;
	return bin_tab[x/128-4] + 16;
}

static int bin_index_up(size_t x)
{
	x = x / SIZE_ALIGN - 1;
	if (x <= 32) return x;
	x--;
	if (x < 512) return bin_tab[x/8-4] + 1;
	return bin_tab[x/128-4] + 17;
}

5.2.3.2.1. bin_tab 表

bin_tab中数据比较有意思，如：
32~35 每个出现1次
36~39 每个出现2次
40~43 每个出现4次
44~47 每个出现8次

bins数组根据不同空闲chunk的大小做了分组，不同bin上面的chunk的大小有的是固定的，有的是一个范围，而范围的宽度也不全是一样的。

bin_tab中出现的数值其实就是bins数组的下标，下标出现的次数代表范围的宽度，比如：[1, 4) 范围宽度为4，[4, 12) 范围宽度为8。

其中，下标0~31和48 ~63都不在bin_tab表中，实际上，下标0 ~31对应的是固定的chunk，下标32 ~47对应的是一些范围的chunk，而下标48 ~63同下标32 ~47出现的次数规律是一样的，但是次数是指数递增的，通过在下标32 ~47的基础上加16，规律如下：
48~51 每个出现16次，即范围宽度是16
52~55 每个出现32次，即范围宽度是32
56~59 每个出现64次，即范围宽度是64
60~62 每个出现128次，即范围宽度是128
63 范围宽度不限制

5.2.3.2.2. bin_index 函数

x 是经过 SIZE_ALIGN对齐的，所以 (x = x / SIZE_ALIGN - 1) >= 0。
假设下标为i，N = SIZE_ALIGN，下面列出x和i的对应关系：
1）当 x = [0, 31] 时，i = x = [0, 31]，bin[i]对应的chunk大小为：(i + 1) * N
2）当 x >= 32 时，i不再对应固定的x，而是对应x的范围，如下：
当 x = [32, 40) 时，i = 32，bin[i]对应的chunk大小为：[32+(i-32)*8+1, 40+(i-32)*8] * N
当 x = [40, 48) 时，i = 33，bin[i]对应的chunk大小为：[32+(i-32)*8+1, 40+(i-32)*8] * N
当 x = [48, 56) 时，i = 34，bin[i]对应的chunk大小为：[32+(i-32)*8+1, 40+(i-32)*8] * N
当 x = [56, 64) 时，i = 35，bin[i]对应的chunk大小为：[32+(i-32)*8+1, 40+(i-32)*8] * N
当 x = [64, 80) 时，i = 36，bin[i]对应的chunk大小为：[64+(i-36)*16+1, 80+(i-36)*16] * N
当 x = [80, 96) 时，i = 37，bin[i]对应的chunk大小为：[64+(i-36)*16+1, 80+(i-36)*16] * N
当 x = [96, 112) 时，i = 38，bin[i]对应的chunk大小为：[64+(i-36)*16+1, 80+(i-36)*16] * N
当 x = [112, 128) 时，i = 39，bin[i]对应的chunk大小为：[64+(i-36)*16+1, 80+(i-36)*16] * N
当 x = [128, 160) 时，i = 40，bin[i]对应的chunk大小为：[128+(i-40)*32+1, 160+(i-40)*32] * N
当 x = [160, 192) 时，i = 41，bin[i]对应的chunk大小为：[128+(i-40)*32+1, 160+(i-40)*32] * N
当 x = [192, 224) 时，i = 42，bin[i]对应的chunk大小为：[128+(i-40)*32+1, 160+(i-40)*32] * N
当 x = [224, 256) 时，i = 43，bin[i]对应的chunk大小为：[128+(i-40)*32+1, 160+(i-40)*32] * N
当 x = [256, 320) 时，i = 44，bin[i]对应的chunk大小为：[256+(i-44)*64+1, 320+(i-44)*64] * N
当 x = [320, 384) 时，i = 45，bin[i]对应的chunk大小为：[256+(i-44)*64+1, 320+(i-44)*64] * N
当 x = [384, 448) 时，i = 46，bin[i]对应的chunk大小为：[256+(i-44)*64+1, 320+(i-44)*64] * N
当 x = [448, 512) 时，i = 47，bin[i]对应的chunk大小为：[256+(i-44)*64+1, 320+(i-44)*64] * N
…
当 x = [512, 640) 时，i = 48，bin[i]对应的chunk大小为：[512+(i-48)*128+1, 640+(i-48)*128] * N
当 x = [640, 768) 时，i = 49，bin[i]对应的chunk大小为：[512+(i-48)*128+1, 640+(i-48)*128] * N
…
当 x = [1024, 1280) 时，i = 52，bin[i]对应的chunk大小为：[1024+(i-52)*256+1, 1280+(i-52)*256] * N
当 x = [1280, 1536) 时，i = 53，bin[i]对应的chunk大小为：[1024+(i-52)*256+1, 1280+(i-52)*256] * N
…
当 x = [2048, 2560) 时，i = 56，bin[i]对应的chunk大小为：[2048+(i-56)*512+1, 2560+(i-56)*512] * N
当 x = [2560, 3072) 时，i = 57，bin[i]对应的chunk大小为：[2048+(i-56)*512+1, 2560+(i-56)*512] * N
…
当 x = [4096, 5120) 时，i = 60，bin[i]对应的chunk大小为：[4096+(i-60)*1024+1, 5120+(i-60)*1024] * N
…
当 x = [6144, 7168) 时，i = 62，bin[i]对应的chunk大小为：[4096+(i-60)*1024+1, 5120+(i-60)*1024] * N
当 x >= 7168 时，i = 63，bin[i]对应的chunk大小为：> (5120+(62-60)*1024) * N

下面列出不同bin的下标和管理的chunk大小的关系：（64位上：N=32）

bin的下标i	chunk大小公式	chunk大小范围	下标i于chunk大小的关系
0~31	(i+1) * N	0x20~0x400(1k)	(i+1)*0x20
32~35	[32+(i-32)*8+1, 40+(i-32)*8] * N	0x420~0x800(2k)	[0x420+(i-32)*0x100, 0x500+(i-32)*0x100]
36~39	[64+(i-36)*16+1, 80+(i-36)*16] * N	0x820~0x1000(4k)	[0x820+(i-36)*0x200, 0xA00+(i-36)*0x200]
40~43	[128+(i-40)*32+1, 160+(i-40)*32] * N	0x1020~0x2000(8k)	[0x1020+(i-40)*0x400, 0x1400+(i-40)*0x400]
44~47	[256+(i-44)*64+1, 320+(i-44)*64] * N	0x2020~0x4000(16k)	[0x2020+(i-44)*0x800, 0x2800+(i-44)*0x800]
48~51	[512+(i-48)*128+1, 640+(i-48)*128] * N	0x4020~0x8000(32k)	[0x4020+(i-48)*0x1000, 0x5000+(i-48)*0x1000]
52~55	[1024+(i-52)*256+1, 1280+(i-52)*256] * N	0x8020~0x10000(64k)	[0x8020+(i-52)*0x2000, 0xA000+(i-52)*0x2000]
56~59	[2048+(i-56)*512+1, 2560+(i-56)*512] * N	0x10020~0x20000(128k)	[0x10020+(i-56)*0x4000, 0x14000+(i-56)*0x4000]
60~62	[4096+(i-60)*1024+1, 5120+(i-60)*1024] * N	0x20020~0x38000(224k)	[0x20020+(i-60)*0x8000, 0x28000+(i-60)*0x8000]
63	> (5120+(62-60)*1024) * N	> 0x38000

5.2.3.2.3. bin_index_up 函数

static int bin_index_up(size_t x)
{
	x = x / SIZE_ALIGN - 1;
	if (x <= 32) return x;
	x--;
	if (x < 512) return bin_tab[x/8-4] + 1;
	return bin_tab[x/128-4] + 17;
}

x 在 adjust_size函数中已经进行了SIZE_ALIGN对齐，所以x / SIZE_ALIGIN必然是一个大于等于1的整数，同时，x小于等于MMAP_THRESHOLD，所以x / SIZE_ALIGN又必然是一个小于等于0x1c00（7168）的整数。

通过上一节我们知道，bin[62] 管理的chunk大小范围是[6145, 7168] * SIZE_ALIGN。
1）假设 x 为 6145 * SIZE_ALIGN，则：

x = x / SIZE_ALIGN - 1 = 6144
x--
x = 6143
bin_tab[x/128-4] + 17 = bin_tab[6143/128-4] + 17 = bin_tab[54-4] + 17 = 45 + 17 = 62

2）假设 x 为 6146 * SIZE_ALIGN，则：

x = x / SIZE_ALIGN - 1 = 6145
x--
x = 6144
bin_tab[x/128-4] + 17 = bin_tab[6144/128-4] + 17 = bin_tab[48-4] + 17 = 46 + 17 = 63

3）假设 x 为 7168 * SIZE_ALIGN，则：

x = x / SIZE_ALIGN - 1 = 7167
x--
x = 7166
bin_tab[x/128-4] + 17 = bin_tab[7166/128-4] + 17 = bin_tab[55-4] + 17 = 46 + 17 = 63

由于bin[62]管理的chunk大小是一个范围，当根据x的大小查找合适的bin时，如果x的大小正好是某个bin管理的最小chunk大小时，那么这个bin上的所有chunk都符合分配要求，所以选择该bin即可。如果x的大小在某个bin管理的chunk中并不是最小，此时，如果选择该bin，就需要通过遍历bin链表找到大于等于x的chunk进行分配，这样会损失性能，所以应该选择下一个bin，下一个bin上管理的所有chunk都会比x大，可以快速进行获取符合分配要求的chunk。这就是bin_index_up的作用，向上找到最合适的bin，即可以快速匹配合适的chunk又不至于过度碎片化chunk。

if (x <= 32) return x;
x--;

如果x = [0，31]，由于下标0 ~31的bin上面的chunk大小是固定的，所以不需要试图找下一个。如果x = 32，尽管下标32的bin上面的chunk大小是一个范围，但是x = 32时，表示原始x的大小正好是该bin上管理的最小chunk大小，所以下标32正好满足，也不需要再向下找。

通过上面的举例分析，对于那些管理chunk大小范围的bin，只有原始x的大小正好是某个bin管理的最小chunk大小时，才不用获取下一个bin，除此之外，都需要获取下一个bin，为了后续逻辑兼容，将x自减1，在查找完bin_tab后都加1，表示获取下一个bin对应的下标。对于正好是某个bin的管理的最小chunk大小的原始x，减1之后理论上通过bin_tab会找到上一个bin的下标，加1正好获取当前bin的下标。其它x减1，bin_tab都会获取当前bin的下标，加1也正好获取下一个bin的下标。

由于调用bin_index_up时的x小于等于MMAP_THRESHOLD，所以最大的x对应的bin下标才是62，这些被下标是62的bin管理的，最后经过bin_index_up都会找到下标63。

5.2.3.3. expand_heap 函数

static struct chunk *expand_heap(size_t n)
{
	static int heap_lock[2];
	static void *end;
	void *p;
	struct chunk *w;

	/* The argument n already accounts for the caller's chunk
	 * overhead needs, but if the heap can't be extended in-place,
	 * we need room for an extra zero-sized sentinel chunk. */
	n += SIZE_ALIGN;

	lock(heap_lock);

	p = __expand_heap(&n);
	if (!p) {
		unlock(heap_lock);
		return 0;
	}

	/* If not just expanding existing space, we need to make a
	 * new sentinel chunk below the allocated space. */
	if (p != end) {
		/* Valid/safe because of the prologue increment. */
		n -= SIZE_ALIGN;
		p = (char *)p + SIZE_ALIGN;
		w = MEM_TO_CHUNK(p);
		w->psize = 0 | C_INUSE;
	}

	/* Record new heap end and fill in footer. */
	end = (char *)p + n;
	w = MEM_TO_CHUNK(end);
	w->psize = n | C_INUSE;
	w->csize = 0 | C_INUSE;

	/* Fill in header, which may be new or may be replacing a
	 * zero-size sentinel header at the old end-of-heap. */
	w = MEM_TO_CHUNK(p);
	w->csize = n | C_INUSE;

	unlock(heap_lock);

	return w;
}

5.2.3.3.1. 逻辑简析

	/* The argument n already accounts for the caller's chunk
	 * overhead needs, but if the heap can't be extended in-place,
	 * we need room for an extra zero-sized sentinel chunk. */
	n += SIZE_ALIGN;

参数 n 已经考虑了调用者的chunk overhead需要，但是如果堆不能就地扩展，我们需要空间来容纳一个额外的零大小的哨兵chunk。

	p = __expand_heap(&n);
	if (!p) {
		unlock(heap_lock);
		return 0;
	}

调用__expand_heap进行堆空间扩展。

	/* If not just expanding existing space, we need to make a
	 * new sentinel chunk below the allocated space. */
	if (p != end) {
		/* Valid/safe because of the prologue increment. */
		n -= SIZE_ALIGN;
		p = (char *)p + SIZE_ALIGN;
		w = MEM_TO_CHUNK(p);
		w->psize = 0 | C_INUSE;
	}

如果不是扩展现有空间，比如第一次扩展堆内存，end初始值是0，如果堆内存扩展成功，p显然不是0，所以我们需要在分配的空间中创建一个新的哨兵块。

开始的时候n += SIZE_ALIGN，此处n -= SIZE_ALIGN，相当于还原n，n是新chunk的大小，n减去SIZE_ALIGN，SIZE_ALIGN等于2倍OVERHEAD，其中最前面的OVERHEAD大小的空间作为哨兵chunk，最后面的OVERHEAD大小的空间作为尾chunk。

p从__expand_heap扩展后指向chunk首地址，经过p = (char *)p + SIZE_ALIGN后，p现在指向新chunk的可用内存首地址。

w = MEM_TO_CHUNK§，得到新chunk，前一个chunk是哨兵chunk，w->psize = 0 | C_INUSE 设置哨兵chunk的大小，同时将flag位设置为C_INUSE，表示前一个（哨兵）chunk是小内存。

疑问：哨兵chunk的大小应该是OVERHEAD，而此处设置为0，是代码错误，还是故意为之？

	/* Record new heap end and fill in footer. */
	end = (char *)p + n;
	w = MEM_TO_CHUNK(end);
	w->psize = n | C_INUSE;
	w->csize = 0 | C_INUSE;

记录新的堆尾并填写尾chunk。下次扩展堆内存时，如果内存连续，那么前一次end应该等于新的p。

1）第一次扩展堆内存

n表示新chunk大小，p指向新chunk的可用内存首地址，end = (char *)p + n 后，end指向扩展堆内存的尾地址。

w = MEM_TO_CHUNK(end)，得到尾chunk。

尾chunk的前一个chunk是新chunk，新chunk大小是n，所以设置 w->psize = n | C_INUSE。

疑问：尾chunk的大小应该是OVERHEAD，而此处设置为0，是代码错误，还是故意为之？

2）非第一次扩展堆内存

n表示新chunk大小，p指向扩展堆内存的首地址，end = (char *)p + n 后，end指向扩展堆内存的尾地址。

w = MEM_TO_CHUNK(end)，得到尾chunk。

尾chunk的前一个chunk是新chunk，新chunk大小是n，所以设置 w->psize = n | C_INUSE。

(char *)p + n后，n宽度的地址空间中，尾chunk占用了OVERHEAD空间，由于新chunk的大小为n，所以如果p指向新chunk的首地址，则chunk大小少了OVERHEAD，所以，此处p也应该指向新chunk的可用内存首地址，而新chunk首地址应该是MEM_TO_CHUNK§，但是，可以发现新chunk覆盖了之前的尾chunk，不过上面重新设置了新的尾chunk，所以之前的尾chunk理论上就是要覆盖，不然相当于浪费。

	/* Fill in header, which may be new or may be replacing a
	 * zero-size sentinel header at the old end-of-heap. */
	w = MEM_TO_CHUNK(p);
	w->csize = n | C_INUSE;

设置新chunk的csize，为什么不设置psize？

1）第一次扩展堆内存

psize在 if (p != end) {中已设置

2）非第一次扩展堆内存

新chunk头覆盖了之前的尾chunk，所以psize在之前的尾chunk中已设置了，之前尾chunk的前一个chunk，也是新chunk的前一个chunk，所以共用psize。

5.2.3.3.2. __expand_heap 函数

/* Expand the heap in-place if brk can be used, or otherwise via mmap,
 * using an exponential lower bound on growth by mmap to make
 * fragmentation asymptotically irrelevant. The size argument is both
 * an input and an output, since the caller needs to know the size
 * allocated, which will be larger than requested due to page alignment
 * and mmap minimum size rules. The caller is responsible for locking
 * to prevent concurrent calls. */

void *__expand_heap(size_t *pn)
{
	static uintptr_t brk;
	static unsigned mmap_step;
	size_t n = *pn;

	if (n > SIZE_MAX/2 - PAGE_SIZE) {
		errno = ENOMEM;
		return 0;
	}
	n += -n & PAGE_SIZE-1;

	if (!brk) {
		brk = __syscall(SYS_brk, 0);
		brk += -brk & PAGE_SIZE-1;
	}

	if (n < SIZE_MAX-brk && !traverses_stack_p(brk, brk+n)
	    && __syscall(SYS_brk, brk+n)==brk+n) {
		*pn = n;
		brk += n;
		return (void *)(brk-n);
	}

	size_t min = (size_t)PAGE_SIZE << mmap_step/2;
	if (n < min) n = min;
	void *area = __mmap(0, n, PROT_READ|PROT_WRITE,
		MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
	if (area == MAP_FAILED) return 0;
	*pn = n;
	mmap_step++;
	return area;
}

如果可以使用 brk，则就地扩展堆，否则通过 mmap，使用 mmap 增长的指数下限使碎片渐近无关。 size 参数既是输入又是输出，因为调用者需要知道分配的大小，由于页面对齐和 mmap 最小大小规则，该大小将大于请求的大小。 调用者负责锁定以防止并发调用

brk和mmap_step都是静态变量，以此保证扩展堆内存的地址连续性。

5.2.3.3.3. 小结

chunk分配的过程如下：

5.2.3.4. alloc_rev 函数

static int alloc_rev(struct chunk *c)
{
	int i;
	size_t k;
	while (!((k=c->psize) & C_INUSE)) {
		i = bin_index(k);
		lock_bin(i);
		if (c->psize == k) {
			unbin(PREV_CHUNK(c), i);
			unlock_bin(i);
			return 1;
		}
		unlock_bin(i);
	}
	return 0;
}

alloc_rev用于判断前一个chunk是否空闲，如果前一个chunk是空闲的，会将其从bin链表上取下。

lock_bin(i)之后的if判断的原因是防止上锁之前前一个chunk被其它线程操作后引起变更。

5.2.3.5. alloc_fwd 函数

static int alloc_fwd(struct chunk *c)
{
	int i;
	size_t k;
	while (!((k=c->csize) & C_INUSE)) {
		i = bin_index(k);
		lock_bin(i);
		if (c->csize == k) {
			unbin(c, i);
			unlock_bin(i);
			return 1;
		}
		unlock_bin(i);
	}
	return 0;
}

alloc_fwd用于判断当前chunk是否空闲，如果当前chunk是空闲的，会将其从bin链表上取下。

lock_bin(i)之后的if判断的原因是防止上锁前当前chunk被其它线程操作后引起变更。

5.2.3.6. first_set 函数

static int first_set(uint64_t x)
{
#if 1
	return a_ctz_64(x);
#else
	static const char debruijn64[64] = {
		0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
		62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
		63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
		51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
	};
	static const char debruijn32[32] = {
		0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13,
		31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14
	};
	if (sizeof(long) < 8) {
		uint32_t y = x;
		if (!y) {
			y = x>>32;
			return 32 + debruijn32[(y&-y)*0x076be629 >> 27];
		}
		return debruijn32[(y&-y)*0x076be629 >> 27];
	}
	return debruijn64[(x&-x)*0x022fdd63cc95386dull >> 58];
#endif
}

求x末尾连续0的个数，即x二进制位从低到高第一次出现1的位置。

x = 0 时结果未定义。

5.2.3.7. pretrim 函数

/* pretrim - trims a chunk _prior_ to removing it from its bin.
 * Must be called with i as the ideal bin for size n, j the bin
 * for the _free_ chunk self, and bin j locked. */
static int pretrim(struct chunk *self, size_t n, int i, int j)
{
	size_t n1;
	struct chunk *next, *split;

	/* We cannot pretrim if it would require re-binning. */
	if (j < 40) return 0;
	if (j < i+3) {
		if (j != 63) return 0;
		n1 = CHUNK_SIZE(self);
		if (n1-n <= MMAP_THRESHOLD) return 0;
	} else {
		n1 = CHUNK_SIZE(self);
	}
	if (bin_index(n1-n) != j) return 0;

	next = NEXT_CHUNK(self);
	split = (void *)((char *)self + n);

	split->prev = self->prev;
	split->next = self->next;
	split->prev->next = split;
	split->next->prev = split;
	split->psize = n | C_INUSE;
	split->csize = n1-n;
	next->psize = n1-n;
	self->csize = n | C_INUSE;
	return 1;
}

pretrim - 修剪一个 prior chunk以将其从其 bin 中删除。 必须使用 i 作为大小 n 的理想 bin 调用，j 是 free chunk 自身的 bin，并且 bin j 被锁定。

5.2.3.7.1. 逻辑简析

    /* We cannot pretrim if it would require re-binning. */
	if (j < 40) return 0;
	if (j < i+3) {
		if (j != 63) return 0;
		n1 = CHUNK_SIZE(self);
		if (n1-n <= MMAP_THRESHOLD) return 0;
	} else {
		n1 = CHUNK_SIZE(self);
	}
	if (bin_index(n1-n) != j) return 0;

如果裁剪下来的chunk需要重新挂载到bin，那么就不能预裁剪，后面由trim统一裁剪。

下标小于40的最大chunk大小为4k，出现重新挂载到bin的概率较高，所以不预裁剪。

如果 j < i+3，有下面几种情况：
1）j == i
2）j == i + 1
3）j == i + 2
如果j != 63，从下标j对应的bin中裁剪i对应的bin中对应的chunk大小，裁掉的chunk大概率需要重新挂载到合适bin。因为下标63上对应的chunk比较大，所以裁掉的chunk需要重新挂载到合适bin的概率较低。
对于j == 63，下标63上对应的chunk大小大于MMAP_THRESHOLD，n1是找到的空闲chunk大小，n是需要的chunk大小，n1-n是裁掉的chunk大小，如果小于等于MMAP_THRESHOLD，说明不能继续挂载到下标63对应的bin上，所以不能预裁剪。

如果 bin_index(n1-n) != j，说明裁掉的chunk大小所对应的bin的下标不是j，因此裁掉的chunk需要重新挂载到合适bin，所以不能预裁剪。

	next = NEXT_CHUNK(self);
	split = (void *)((char *)self + n);

	split->prev = self->prev;
	split->next = self->next;
	split->prev->next = split;
	split->next->prev = split;
	split->psize = n | C_INUSE;
	split->csize = n1-n;
	next->psize = n1-n;
	self->csize = n | C_INUSE;

裁剪掉的chunk大小是n1-n，因为裁剪掉的chunk依然是空闲的chunk，所以flag位为0，剩下的chunk将返回给用户，所以需要设置flag位为C_INUSE。

5.2.3.8. unbin 函数

从下标为i的bin表中取下chunk。

static void unbin(struct chunk *c, int i)
{
	if (c->prev == c->next)
		a_and_64(&mal.binmap, ~(1ULL<<i));
	c->prev->next = c->next;
	c->next->prev = c->prev;
	c->csize |= C_INUSE;
	NEXT_CHUNK(c)->psize |= C_INUSE;
}

如果 c->prev == c->next，说明bin上只有一个chunk，该chunk都指向bin表头，即将从bin表中取下这唯一的空闲chunk，那么bin表将变成空表，所以该bin表对应的binmap位需要清0.

chunk从bin表取下之后，就不是空闲的chunk了，所以需要设置flag位为C_INUSE。

5.2.3.9. trim 函数

根据需要的大小n裁剪chunk

static void trim(struct chunk *self, size_t n)
{
	size_t n1 = CHUNK_SIZE(self);
	struct chunk *next, *split;

	if (n >= n1 - DONTCARE) return;

	next = NEXT_CHUNK(self);
	split = (void *)((char *)self + n);

	split->psize = n | C_INUSE;
	split->csize = n1-n | C_INUSE;
	next->psize = n1-n | C_INUSE;
	self->csize = n | C_INUSE;

	__bin_chunk(split);
}

n1是当前chunk的大小，n是需要的chunk大小。如果n >= n1 - DONTCARE，说明n1-n太小，没必要进行裁剪，直接将当前chunk返回给用户即可，根本不会造成浪费。

当前chunk已经从不是空闲chunk，所以裁剪掉的chunk在未挂载回bin之前也不是空闲chunk，所以flag位都设置为C_INUSE。

__bin_chunk(split) 将裁剪掉的chunk重新挂回合适的bin。

5.2.3.10. __bin_chunk 函数

将chunk重新挂回合适的bin，挂回前可能会迭代合并当前chunk的前后空闲chunk。

void __bin_chunk(struct chunk *self)
{
	struct chunk *next = NEXT_CHUNK(self);
	size_t final_size, new_size, size;
	int reclaim=0;
	int i;

	final_size = new_size = CHUNK_SIZE(self);

	/* Crash on corrupted footer (likely from buffer overflow) */
	if (next->psize != self->csize) a_crash();

	for (;;) {
		if (self->psize & next->csize & C_INUSE) {
			self->csize = final_size | C_INUSE;
			next->psize = final_size | C_INUSE;
			i = bin_index(final_size);
			lock_bin(i);
			lock(mal.free_lock);
			if (self->psize & next->csize & C_INUSE)
				break;
			unlock(mal.free_lock);
			unlock_bin(i);
		}

		if (alloc_rev(self)) {
			self = PREV_CHUNK(self);
			size = CHUNK_SIZE(self);
			final_size += size;
			if (new_size+size > RECLAIM && (new_size+size^size) > size)
				reclaim = 1;
		}

		if (alloc_fwd(next)) {
			size = CHUNK_SIZE(next);
			final_size += size;
			if (new_size+size > RECLAIM && (new_size+size^size) > size)
				reclaim = 1;
			next = NEXT_CHUNK(next);
		}
	}

	if (!(mal.binmap & 1ULL<<i))
		a_or_64(&mal.binmap, 1ULL<<i);

	self->csize = final_size;
	next->psize = final_size;
	unlock(mal.free_lock);

	self->next = BIN_TO_CHUNK(i);
	self->prev = mal.bins[i].tail;
	self->next->prev = self;
	self->prev->next = self;

	/* Replace middle of large chunks with fresh zero pages */
	if (reclaim) {
		uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
		uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
#if 1
		__madvise((void *)a, b-a, MADV_DONTNEED);
#else
		__mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
			MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
#endif
	}

	unlock_bin(i);
}

5.2.3.10.1. 逻辑简析

	for (;;) {
		if (self->psize & next->csize & C_INUSE) {
			self->csize = final_size | C_INUSE;
			next->psize = final_size | C_INUSE;
			i = bin_index(final_size);
			lock_bin(i);
			lock(mal.free_lock);
			if (self->psize & next->csize & C_INUSE)
				break;
			unlock(mal.free_lock);
			unlock_bin(i);
		}

		if (alloc_rev(self)) {
			self = PREV_CHUNK(self);
			size = CHUNK_SIZE(self);
			final_size += size;
			if (new_size+size > RECLAIM && (new_size+size^size) > size)
				reclaim = 1;
		}

		if (alloc_fwd(next)) {
			size = CHUNK_SIZE(next);
			final_size += size;
			if (new_size+size > RECLAIM && (new_size+size^size) > size)
				reclaim = 1;
			next = NEXT_CHUNK(next);
		}
	}

1）前后chunk都在使用中
加锁之后，又判断一次前后chunk是否在使用中，是防止加锁前其它线程将前后chunk修改成空闲chunk了。如果前后chunk还是在使用中，则直接退出循环。

2）前一个chunk空闲
如果前一个chunk是空闲的，则将其从对应的bin中取下，然后累加前一个chunk的大小

3）后一个chunk空闲
如果后一个chunk是空闲的，则将其从对应的bin中取下，然后累加后一个chunk的大小

循环上面步骤，直至前后chunk都在使用中，循环过程中，会不断的累加前后空闲chunk的大小

i = bin_index(final_size) 根据chunk的最终的大小找到合适的bin下标。

			if (new_size+size > RECLAIM && (new_size+size^size) > size)
				reclaim = 1;

如果当前chunk大小加上任一前或后空闲chunk的大小大于RECLAIM（160K），并且 (new_size+size^size) > size，将会在之后进行回收操作，此处的回收并不是回收内存，稍后会说明。

(new_size+size^size) > size ？？？
new_size和size都是chunk的大小，都是经过SIZE_ALIGIN对齐的。一个数异或自己后等于0，该数加上一个数然后再异或自己，并要求大于自己，以二进制位来看，两位相加必须使高位上有1，否则异或自己的时候，会使高位变0，必然小于自己。
1）new_size大于等于size，相加后的结果的高位1必然高于size高位1的位置，所以，结果异或size必然大于size。
2）new_size小于size，相加后的结果的高位1必须高于size高位1的位置，结果异或size后才能大于size。

关系式：(a+b^b) > b
假设：b为32，二进制表示00100000
1）当a为40时
(a+b) => 00101000 + 00100000 = 01001000
(a+b^b) => 01001000 ^ 00100000 = 01101000
(a+b^b) > b => 01101000(104) > 00100000(32)
2）当a为32时
(a+b) => 00100000 + 00100000 = 01000000
(a+b^b) => 01000000 ^ 00100000 = 01100000
(a+b^b) > b => 01100000(96) > 00100000(32)
3）当a为24时
(a+b) => 00011000 + 00100000 = 00111000
(a+b^b) => 00111000 ^ 00100000 = 00011000
(a+b^b) > b => 00011000(24) < 00100000(32)
4）当a为16时
(a+b) => 00010000 + 00100000 = 00110000
(a+b^b) => 00110000 ^ 00100000 = 00010000
(a+b^b) > b => 00010000(16) < 00100000(32)

	if (!(mal.binmap & 1ULL<<i))
		a_or_64(&mal.binmap, 1ULL<<i);

因为马上要将chunk挂到下标为i的bin表上，如果bin表对应的binmap位还是0，需要将bitmap对应的位置1。

缺陷：这里先设置binmap，再挂回chunk，逻辑上有问题。多线程场景下，若一个线程正好刚设置完binmap，还没来得及挂回chunk，另一个线程读到binmap对应位有效，然后读bin表时发现又是空表，这应该也是malloc中判断bin表是否为空的原因之一。

	self->csize = final_size;
	next->psize = final_size;
	unlock(mal.free_lock);

	self->next = BIN_TO_CHUNK(i);
	self->prev = mal.bins[i].tail;
	self->next->prev = self;
	self->prev->next = self;

设置chunk的大小，因为chunk将是空闲的，所以flag位为0。

chunk挂到bin表最后：
当前chunk的next指向bin表头
当前chunk的prev指向bin表中的最后一个chunk
当前chunk的next的prev，即bin的prev，因为bin是特殊chunk，即bin的tail指向当前chunk
当前chunk的prev的next，即bin表中的最后一个chunk的next指向当前chunk

如下图所示：

	/* Replace middle of large chunks with fresh zero pages */
	if (reclaim) {
		uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
		uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
#if 1
		__madvise((void *)a, b-a, MADV_DONTNEED);
#else
		__mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
			MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
#endif
	}

用新的零页替换大块的中间，相当于清空这些大块的中间部分。另外__madvise还有提高系统或应用程序的性能作用（释放物理内存？）。

5.2.3.10.2. __madvise 函数

int __madvise(void *addr, size_t len, int advice)
{
	return syscall(SYS_madvise, addr, len, advice);
}

madvise 系统调用用于向内核提供有关从地址 addr 开始且长度为字节的地址范围的建议或指示。在大多数情况下，此类建议的目标是提高系统或应用程序的性能

• 当advice取值 MADV_DONTNEED 时
  表示不要指望在不久的将来访问。 （目前，应用程序在给定的范围内完成，因此内核可以释放与之相关的资源。）

  在成功的 MADV_DONTNEED 操作之后，指定区域中内存访问的语义发生变化：该范围内页面的后续访问将成功，但将导致从底层映射文件的最新内容重新填充内存内容（用于共享文件映射、共享匿名映射和基于 shmem 的技术，例如 System V 共享内存段）或用于匿名私有映射的零填充按需页面。

  请注意，当应用于共享映射时，MADV_DONTNEED 可能不会导致立即释放范围内的页面。内核可以自由地将释放页面延迟到适当的时刻。然而，调用进程的常驻集大小 (RSS) 将立即减少。

5.2.3.11. lock/unlock 函数

static inline void lock(volatile int *lk)
{
	if (libc.threads_minus_1)
		while(a_swap(lk, 1)) __wait(lk, lk+1, 1, 1);
}

static inline void unlock(volatile int *lk)
{
	if (lk[0]) {
		a_store(lk, 0);
		if (lk[1]) __wake(lk, 1, 1);
	}
}

5.2.3.12. lock_bin/unlock_bin 函数

static inline void lock_bin(int i)
{
	lock(mal.bins[i].lock);
	if (!mal.bins[i].head)
		mal.bins[i].head = mal.bins[i].tail = BIN_TO_CHUNK(i);
}

static inline void unlock_bin(int i)
{
	unlock(mal.bins[i].lock);
}

5.3. 解析 free 函数

void free(void *p)
{
	if (!p) return;

	struct chunk *self = MEM_TO_CHUNK(p);

	if (IS_MMAPPED(self))
		unmap_chunk(self);
	else
		__bin_chunk(self);
}

如果当前chunk是从mmap分配的（大内存），则通过unmap_chunk进行释放，否则当前chunk是小内存，通过__bin_chunk进行管理。

5.3.1. unmap_chunk 函数

static void unmap_chunk(struct chunk *self)
{
	size_t extra = self->psize;
	char *base = (char *)self - extra;
	size_t len = CHUNK_SIZE(self) + extra;
	/* Crash on double free */
	if (extra & 1) a_crash();
	__munmap(base, len);
}

extra是哨兵chunk大小，base是哨兵chunk首地址，len是哨兵chunk与当前chunk的大小和，即从mmap分配的内存长度。

调用__munmap释放chunk内存。

5.3.1.1. __munmap 函数

int __munmap(void *start, size_t len)
{
	__vm_wait();
	return syscall(SYS_munmap, start, len);
}

6. calloc 函数

int __malloc_replaced;

static size_t mal0_clear(char *p, size_t pagesz, size_t n)
{
#ifdef __GNUC__
	typedef uint64_t __attribute__((__may_alias__)) T;
#else
	typedef unsigned char T;
#endif
	char *pp = p + n;
	size_t i = (uintptr_t)pp & (pagesz - 1);
	for (;;) {
		pp = memset(pp - i, 0, i);
		if (pp - p < pagesz) return pp - p;
		for (i = pagesz; i; i -= 2*sizeof(T), pp -= 2*sizeof(T))
		        if (((T *)pp)[-1] | ((T *)pp)[-2])
				break;
	}
}

void *calloc(size_t m, size_t n)
{
	if (n && m > (size_t)-1/n) {
		errno = ENOMEM;
		return 0;
	}
	n *= m;
	void *p = malloc(n);
	if (!p) return p;
	if (!__malloc_replaced) {
		if (IS_MMAPPED(MEM_TO_CHUNK(p)))
			return p;
		if (n >= PAGE_SIZE)
			n = mal0_clear(p, PAGE_SIZE, n);
	}
	return memset(p, 0, n);
}

m – 要被分配的元素个数。
n – 元素的大小。

相较于malloc函数，calloc函数会自动将内存初始化为0。

6.1. 逻辑简析

	if (n && m > (size_t)-1/n) {
		errno = ENOMEM;
		return 0;
	}

检查参数范围，m * n 溢出检测

	n *= m;
	void *p = malloc(n);
	if (!p) return p;

调用malloc分配内存

	if (!__malloc_replaced) {
		if (IS_MMAPPED(MEM_TO_CHUNK(p)))
			return p;
		if (n >= PAGE_SIZE)
			n = mal0_clear(p, PAGE_SIZE, n);
	}
    return memset(p, 0, n);

__malloc_replaced 标识malloc是否被替换，一些内存检测工具可能需要替换系统的malloc函数，从而实现内存监测的目的。

因为calloc需要将内存初始化为0，如果malloc没有被替换，则调用内部的初始化函数，否认调用标准memset接口。

关于内部的初始化函数，如果内存是通过mmap分配的，mmap分配的内存会初始化为0，所以不需要再初始化。否则，如果n >= PAGE_SIZE，则调用mal0_clear进行初始化0，如果n < PAGE_SIZE，则不进行内部初始化，通过后面调用memset进行初始化。

通过上面我们可以初步判断，不直接都调用memset，应该是memset存在性能问题，比如：mmap分配的本身就初始化了，所以没必要再调用memset初始化。

为什么 n >= PAGE_SIZE 要调用mal0_clear而不是memset进行初始化呢？应该是此时的内存比较大，对于性能的影响就不容忽视了，通过mal0_clear的实现可以发现，对于内存中已经是0的内存块不需要初始化操作，非0的再进行memset初始化。

7. realloc 函数

void *realloc(void *p, size_t n)
{
	struct chunk *self, *next;
	size_t n0, n1;
	void *new;

	if (!p) return malloc(n);

	if (adjust_size(&n) < 0) return 0;

	self = MEM_TO_CHUNK(p);
	n1 = n0 = CHUNK_SIZE(self);

	if (IS_MMAPPED(self)) {
		size_t extra = self->psize;
		char *base = (char *)self - extra;
		size_t oldlen = n0 + extra;
		size_t newlen = n + extra;
		/* Crash on realloc of freed chunk */
		if (extra & 1) a_crash();
		if (newlen < PAGE_SIZE && (new = malloc(n-OVERHEAD))) {
			n0 = n;
			goto copy_free_ret;
		}
		newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
		if (oldlen == newlen) return p;
		base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
		if (base == (void *)-1)
			goto copy_realloc;
		self = (void *)(base + extra);
		self->csize = newlen - extra;
		return CHUNK_TO_MEM(self);
	}

	next = NEXT_CHUNK(self);

	/* Crash on corrupted footer (likely from buffer overflow) */
	if (next->psize != self->csize) a_crash();

	/* Merge adjacent chunks if we need more space. This is not
	 * a waste of time even if we fail to get enough space, because our
	 * subsequent call to free would otherwise have to do the merge. */
	if (n > n1 && alloc_fwd(next)) {
		n1 += CHUNK_SIZE(next);
		next = NEXT_CHUNK(next);
	}
	/* FIXME: find what's wrong here and reenable it..? */
	if (0 && n > n1 && alloc_rev(self)) {
		self = PREV_CHUNK(self);
		n1 += CHUNK_SIZE(self);
	}
	self->csize = n1 | C_INUSE;
	next->psize = n1 | C_INUSE;

	/* If we got enough space, split off the excess and return */
	if (n <= n1) {
		//memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD);
		trim(self, n);
		return CHUNK_TO_MEM(self);
	}

copy_realloc:
	/* As a last resort, allocate a new chunk and copy to it. */
	new = malloc(n-OVERHEAD);
	if (!new) return 0;
copy_free_ret:
	memcpy(new, p, n0-OVERHEAD);
	free(CHUNK_TO_MEM(self));
	return new;
}

realloc尝试重新调整之前调用 malloc 或 calloc 所分配的 p 所指向的内存块的大小。

realloc函数有三种行为：
1）分配内存：如果p为空，则相当于调用malloc分配新的内存，然后返回新分配内存的首地址
2）释放内存：如果p非空，n为0，则相当于调用free释放内存，然后返回空指针
3）重新分配内存：扩展内存（n比p指向的原内存大），缩小内存（n比p指向的原内存小）

7.1. 逻辑简析

	if (!p) return malloc(n);

分配内存

	if (adjust_size(&n) < 0) return 0;

	self = MEM_TO_CHUNK(p);
	n1 = n0 = CHUNK_SIZE(self);

调整n大小，然后初始化n1，n0为当前chunk大小

7.1.1. 大内存重新分配

	if (IS_MMAPPED(self)) {
		size_t extra = self->psize;
		char *base = (char *)self - extra;
		size_t oldlen = n0 + extra;
		size_t newlen = n + extra;
		/* Crash on realloc of freed chunk */
		if (extra & 1) a_crash();
		if (newlen < PAGE_SIZE && (new = malloc(n-OVERHEAD))) {
			n0 = n;
			goto copy_free_ret;
		}
		newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
		if (oldlen == newlen) return p;
		base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
		if (base == (void *)-1)
			goto copy_realloc;
		self = (void *)(base + extra);
		self->csize = newlen - extra;
		return CHUNK_TO_MEM(self);
	}

extra是哨兵chunk大小，base是哨兵chunk首地址。oldlen 是原先从mmap分配的内存长度，newlen 是即将从mmap分配的内存长度。

		if (newlen < PAGE_SIZE && (new = malloc(n-OVERHEAD))) {
			n0 = n;
			goto copy_free_ret;
		}

从mmap分配的都是大内存，且都按PAGE_SIZE做了对齐处理，如果newlen < PAGE_SIZE，根本不够大内存分配要求，用mmap分配也是浪费，所以直接调用malloc进行分配。n-OVERHEAD是因为n在adjust_size进行了调整，这里需要减去OVERHEAD，n-OVERHEAD是用户可用的内存大小。

copy_realloc:
	/* As a last resort, allocate a new chunk and copy to it. */
	new = malloc(n-OVERHEAD);
	if (!new) return 0;
copy_free_ret:
	memcpy(new, p, n0-OVERHEAD);
	free(CHUNK_TO_MEM(self));
	return new;

如果分配成功，则从原来内存中拷贝n0-OVERHEAD长度的数据到新的内存中，然后释放原来的内存块。（此时n0等于n）

		newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
		if (oldlen == newlen) return p;

newlen做PAGE_SIZE大小对齐，如果oldlen和对齐后的newlen相等，说明原来的内存足够使用，因此没必要再重新分配新的。

		base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
		if (base == (void *)-1)
			goto copy_realloc;
		self = (void *)(base + extra);
		self->csize = newlen - extra;
		return CHUNK_TO_MEM(self);

调用__mremap函数进行内存重新分配，如果分配失败，则跳转到copy_realloc标签调用malloc进行分配n-OVERHEAD长度内存，如果分配成功，则从原来内存中拷贝n0-OVERHEAD长度的数据到新的内存中，然后释放原来的内存块。（缺陷：此时n0并不等于n，若n0大于n，内存拷贝将会出现越界）

__mremap分配成功后，设置新分配的chunk当前大小，然后将可用内存首地址返回给用户。

7.1.1.1. __mremap 函数

void *__mremap(void *old_addr, size_t old_len, size_t new_len, int flags, ...)
{
	va_list ap;
	void *new_addr = 0;

	if (new_len >= PTRDIFF_MAX) {
		errno = ENOMEM;
		return MAP_FAILED;
	}

	if (flags & MREMAP_FIXED) {
		__vm_wait();
		va_start(ap, flags);
		new_addr = va_arg(ap, void *);
		va_end(ap);
	}

	return (void *)syscall(SYS_mremap, old_addr, old_len, new_len, flags, new_addr);
}

7.1.2. 小内存重新分配

	next = NEXT_CHUNK(self);

	/* Crash on corrupted footer (likely from buffer overflow) */
	if (next->psize != self->csize) a_crash();

	/* Merge adjacent chunks if we need more space. This is not
	 * a waste of time even if we fail to get enough space, because our
	 * subsequent call to free would otherwise have to do the merge. */
	if (n > n1 && alloc_fwd(next)) {
		n1 += CHUNK_SIZE(next);
		next = NEXT_CHUNK(next);
	}
	/* FIXME: find what's wrong here and reenable it..? */
	if (0 && n > n1 && alloc_rev(self)) {
		self = PREV_CHUNK(self);
		n1 += CHUNK_SIZE(self);
	}
	self->csize = n1 | C_INUSE;
	next->psize = n1 | C_INUSE;

	/* If we got enough space, split off the excess and return */
	if (n <= n1) {
		//memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD);
		trim(self, n);
		return CHUNK_TO_MEM(self);
	}

copy_realloc:
	/* As a last resort, allocate a new chunk and copy to it. */
	new = malloc(n-OVERHEAD);
	if (!new) return 0;
copy_free_ret:
	memcpy(new, p, n0-OVERHEAD);
	free(CHUNK_TO_MEM(self));
	return new;

小内存的重新分配是先考虑将chunk进行合并，如果合并后的大小满足重新分配需要，则再进行裁剪。
如果合并后的大小不满足重新分配需要，则调用malloc进行分配n-OVERHEAD长度的内存，如果分配成功，则从原来内存中拷贝n0-OVERHEAD长度的数据到新的内存中，然后释放原来的内存块。（此时n大于n1，n1大于等于n0，所以n大于n0，内存拷贝不会越界）

	/* Merge adjacent chunks if we need more space. This is not
	 * a waste of time even if we fail to get enough space, because our
	 * subsequent call to free would otherwise have to do the merge. */
	if (n > n1 && alloc_fwd(next)) {
		n1 += CHUNK_SIZE(next);
		next = NEXT_CHUNK(next);
	}
	/* FIXME: find what's wrong here and reenable it..? */
	if (0 && n > n1 && alloc_rev(self)) {
		self = PREV_CHUNK(self);
		n1 += CHUNK_SIZE(self);
	}
	self->csize = n1 | C_INUSE;
	next->psize = n1 | C_INUSE;

如果n > n1，我们需要更多空间，尝试合并相邻的块。即使我们没有获得足够的空间，这也不是浪费时间，因为我们随后对 free 的调用将不得不进行合并。

	/* If we got enough space, split off the excess and return */
	if (n <= n1) {
		//memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD);
		trim(self, n);
		return CHUNK_TO_MEM(self);
	}

如果合并后的大小满足重新分配需要，则再进行裁剪。

8. 缺陷

前言中讲过musl-1.2.0中的内存管理算法中存在缺陷，下面主要谈一谈有哪些缺陷。

8.1. 堆内存无限增长

我们在讲到小内存的时候，从操作系统申请的小内存释放后都由合适的bin表进行管理，下次再申请时，可以从合适的bin中取出可用的空闲小内存，如果找不到合适的小内存，再向操作系统申请新的小内存。这种只借不还的方式，若是管理不当，将会导致内存持续增长。

下面看看malloc函数关于小内存申请中存在什么缺陷。

void *malloc(size_t n)
{
	struct chunk *c;
	int i, j;

	if (adjust_size(&n) < 0) return 0;
...
	i = bin_index_up(n);
	for (;;) {
		uint64_t mask = mal.binmap & -(1ULL<<i);
		if (!mask) {
			c = expand_heap(n);
			if (!c) return 0;
			if (alloc_rev(c)) {
				struct chunk *x = c;
				c = PREV_CHUNK(c);
				NEXT_CHUNK(x)->psize = c->csize =
					x->csize + CHUNK_SIZE(c);
			}
			break;
		}
		j = first_set(mask);
		lock_bin(j);
		c = mal.bins[j].head;
		if (c != BIN_TO_CHUNK(j)) {
			if (!pretrim(c, n, i, j)) unbin(c, j);
			unlock_bin(j);
			break;
		}
		unlock_bin(j);
	}

	/* Now patch up in case we over-allocated */
	trim(c, n);

	return CHUNK_TO_MEM(c);
}

向操作系统申请新内存的函数是expand_heap，在binmap大于等于i对应的位都为0时发生。

对于多线程场景下，binmap属于共享资源，此处是读资源，关于写资源有两处：
1）unbin中，当从bin中取下最后一个空闲chunk时，bin将变为空表，此时会将binmap对应的位写0

static void unbin(struct chunk *c, int i)
{
	if (c->prev == c->next)
		a_and_64(&mal.binmap, ~(1ULL<<i));
...
}

unbin的调用都会包含在bin[i].lock锁中，所以binmap对应位写0是在加锁条件下。
2）__bin_chunk中，当向bin中挂载chunk时，如果bin之前是空表，此时会将binmap对应的位写1

void __bin_chunk(struct chunk *self)
{
...
	if (!(mal.binmap & 1ULL<<i))
		a_or_64(&mal.binmap, 1ULL<<i);

	self->csize = final_size;
	next->psize = final_size;
	unlock(mal.free_lock);
...

__bin_chunk中对binmap对应位写1包含在mal.free_lock锁中，也是在加锁条件下。

关于binmap资源，写资源都是在加锁条件下操作，只有读资源没有在加锁条件下操作。

读binmap是需要1，unbin写binmap是1->0，__bin_chunk写binmap是0->1。那么在ubin写binmap执行后，__bin_chunk写binmap执行前的这段时间，malloc在读binmap的时候很可能读不到1。

下面看看unbin和__bin_chunk都在什么时候被调用。
1）unbin被调用关系

• malloc时，从bin中找到合适的chunk，调用pretrim预裁剪chunk成功后，会调用unbin，将裁剪后的chunk从bin表中取下来。
  不存在副作用
• malloc时，分配新的chunk，调用alloc_rev，当新chunk的前一个chunk空闲时，会调用unbin，将前一个chunk从bin表中取下来，然后和新chunk合并。
  存在副作用：取下额外的空闲chunk（1->0）

2）__bin_chunk被调用关系
__bin_chunk将chunk还回bin表。还回的过程中，若chunk的前后存在空闲chunk，会调用unbin（alloc_rev和alloc_fwd中调用unbin），将前后chunk从bin表中取下，然后和chunk进行合并，最后重新挂回合适的bin表中。
存在副作用：取下额外的空闲chunk（1->0），挂载合并后新的chunk（0->1）

• malloc时，新分配的chunk（包括合并了前一个空闲chunk的情况）或从bin表中找到的空闲chunk，最后会调用trim裁剪chunk，若chunk可以被裁剪，那么会调用__bin_chunk将裁掉的chunk还回bin表。
• free时，会调用__bin_chunk将chunk还回bin表。

通过上面分析，分配新chunk、裁剪chunk、释放chunk都存在从bin表中取下额外的空闲chunk的情况。当malloc时，读binmap之前，上述三个场景发生，空闲chunk被从bin表取下，若导致bin表短暂（后续合并后会重新挂回合适的bin表）为空，相应的binmap位被写0，那么读binmap时，就读不到为1的binmap位，然后就会扩展堆空间，从操作系统申请新的内存。这就导致，明明有空闲的chunk，只是短暂脱离bin表，申请时却找不到，反而又去申请新的，最终导致内存无限增长。

8.1.1. 修复补丁

社区关键修复补丁：https://git.musl-libc.org/cgit/musl/commit/?id=3e16313f8fe2ed143ae0267fd79d63014c24779f

多年来，这一直是一个长期存在的问题，而且越来越清楚地表明它可能在实践中受到打击。在多线程并发 malloc 和 free 的情况下，尽管总标称使用量很小且有界，但仍有可能通过 brk/mmap 获得无限量的新内存。

根本原因是，作为保持锁定尽可能细粒度的基本结果，free 将一个从bin表取下的空闲块与新释放的块合并，但尚未重新将合并的块挂回bin的状态，暴露给了其他线程。即使是小块，这也很糟糕，并导致内存使用不理想，但它真正爆炸的地方是已经释放的块是“堆顶部”的大空闲区域。在这种情况下，其他线程会暂时看到几乎没有可用内存的状态，并得出结论，它们需要获得更多内存。

据我所知，没有任何不损害性能的解决方法。此处进行的修复强制所有空闲块的拆分/合并在单个锁下进行，这也取代了旧的 free_lock，在空闲时至少暂时保留以确定是否有相邻的空闲块需要合并。

因此，pretrim、alloc_fwd 和 alloc_rev 操作不再有意义并被删除。简化的合并现在在 free (__bin_chunk) 和 realloc 中内联进行。

正如源代码中所评论的那样，持有 split_merge_lock 会阻止从使用中到空闲状态的任何块转换。在大多数情况下，它还排除了块头大小的更改。然而，__memalign 仍然可以修改一个使用中的块的大小以将其拆分为两个使用中的块。可以说，这应该需要持有 split_merge_lock，但这将需要重构以在外部公开它，这是一团糟。结果证明没有必要，至少假设 malloc 一直在使用现有的草率内存模型，因为如果 free (__bin_chunk) 或 realloc 看到任何未同步的大小更改，它也会看到正在使用的位被设置，因此不能对改变大小的相邻块做任何事情。

8.1.2. 补丁分析

diff --git a/src/malloc/malloc.c b/src/malloc/malloc.c
index a803d4c9..20598ec3 100644
--- a/src/malloc/malloc.c
+++ b/src/malloc/malloc.c
@@ -17,7 +17,7 @@
 static struct {
 	volatile uint64_t binmap;
 	struct bin bins[64];
-	volatile int free_lock[2];
+	volatile int split_merge_lock[2];
 } mal;

 int __malloc_replaced;
@@ -128,7 +128,6 @@ void __dump_heap(int x)

 static struct chunk *expand_heap(size_t n)
 {
-	static int heap_lock[2];
 	static void *end;
 	void *p;
 	struct chunk *w;
@@ -138,13 +137,8 @@ static struct chunk *expand_heap(size_t n)
 	 * we need room for an extra zero-sized sentinel chunk. */
 	n += SIZE_ALIGN;

-	lock(heap_lock);
-
 	p = __expand_heap(&n);
-	if (!p) {
-		unlock(heap_lock);
-		return 0;
-	}
+	if (!p) return 0;

 	/* If not just expanding existing space, we need to make a
 	 * new sentinel chunk below the allocated space. */
@@ -167,8 +161,6 @@ static struct chunk *expand_heap(size_t n)
 	w = MEM_TO_CHUNK(p);
 	w->csize = n | C_INUSE;

-	unlock(heap_lock);
-
 	return w;
 }

@@ -198,96 +190,44 @@ static void unbin(struct chunk *c, int i)
 	NEXT_CHUNK(c)->psize |= C_INUSE;
 }

-static int alloc_fwd(struct chunk *c)
-{
-	int i;
-	size_t k;
-	while (!((k=c->csize) & C_INUSE)) {
-		i = bin_index(k);
-		lock_bin(i);
-		if (c->csize == k) {
-			unbin(c, i);
-			unlock_bin(i);
-			return 1;
-		}
-		unlock_bin(i);
-	}
-	return 0;
-}
-
-static int alloc_rev(struct chunk *c)
+static void bin_chunk(struct chunk *self, int i)
 {
-	int i;
-	size_t k;
-	while (!((k=c->psize) & C_INUSE)) {
-		i = bin_index(k);
-		lock_bin(i);
-		if (c->psize == k) {
-			unbin(PREV_CHUNK(c), i);
-			unlock_bin(i);
-			return 1;
-		}
-		unlock_bin(i);
-	}
-	return 0;
+	self->next = BIN_TO_CHUNK(i);
+	self->prev = mal.bins[i].tail;
+	self->next->prev = self;
+	self->prev->next = self;
+	if (self->prev == BIN_TO_CHUNK(i))
+		a_or_64(&mal.binmap, 1ULL<<i);
 }

-
-/* pretrim - trims a chunk _prior_ to removing it from its bin.
- * Must be called with i as the ideal bin for size n, j the bin
- * for the _free_ chunk self, and bin j locked. */
-static int pretrim(struct chunk *self, size_t n, int i, int j)
+static void trim(struct chunk *self, size_t n)
 {
-	size_t n1;
+	size_t n1 = CHUNK_SIZE(self);
 	struct chunk *next, *split;

-	/* We cannot pretrim if it would require re-binning. */
-	if (j < 40) return 0;
-	if (j < i+3) {
-		if (j != 63) return 0;
-		n1 = CHUNK_SIZE(self);
-		if (n1-n <= MMAP_THRESHOLD) return 0;
-	} else {
-		n1 = CHUNK_SIZE(self);
-	}
-	if (bin_index(n1-n) != j) return 0;
+	if (n >= n1 - DONTCARE) return;

 	next = NEXT_CHUNK(self);
 	split = (void *)((char *)self + n);

-	split->prev = self->prev;
-	split->next = self->next;
-	split->prev->next = split;
-	split->next->prev = split;
 	split->psize = n | C_INUSE;
 	split->csize = n1-n;
 	next->psize = n1-n;
 	self->csize = n | C_INUSE;
-	return 1;
-}

-static void trim(struct chunk *self, size_t n)
-{
-	size_t n1 = CHUNK_SIZE(self);
-	struct chunk *next, *split;
-
-	if (n >= n1 - DONTCARE) return;
+	int i = bin_index(n1-n);
+	lock_bin(i);

-	next = NEXT_CHUNK(self);
-	split = (void *)((char *)self + n);
-
-	split->psize = n | C_INUSE;
-	split->csize = n1-n | C_INUSE;
-	next->psize = n1-n | C_INUSE;
-	self->csize = n | C_INUSE;
+	bin_chunk(split, i);

-	__bin_chunk(split);
+	unlock_bin(i);
 }

 void *malloc(size_t n)
 {
 	struct chunk *c;
 	int i, j;
+	uint64_t mask;

 	if (adjust_size(&n) < 0) return 0;

@@ -303,33 +243,37 @@ void *malloc(size_t n)
 	}

 	i = bin_index_up(n);
-	for (;;) {
-		uint64_t mask = mal.binmap & -(1ULL<<i);
-		if (!mask) {
-			c = expand_heap(n);
-			if (!c) return 0;
-			if (alloc_rev(c)) {
-				struct chunk *x = c;
-				c = PREV_CHUNK(c);
-				NEXT_CHUNK(x)->psize = c->csize =
-					x->csize + CHUNK_SIZE(c);
-			}
-			break;
+	if (i<63 && (mal.binmap & (1ULL<<i))) {
+		lock_bin(i);
+		c = mal.bins[i].head;
+		if (c != BIN_TO_CHUNK(i) && CHUNK_SIZE(c)-n <= DONTCARE) {
+			unbin(c, i);
+			unlock_bin(i);
+			return CHUNK_TO_MEM(c);
 		}
+		unlock_bin(i);
+	}
+	lock(mal.split_merge_lock);
+	for (mask = mal.binmap & -(1ULL<<i); mask; mask -= (mask&-mask)) {
 		j = first_set(mask);
 		lock_bin(j);
 		c = mal.bins[j].head;
 		if (c != BIN_TO_CHUNK(j)) {
-			if (!pretrim(c, n, i, j)) unbin(c, j);
+			unbin(c, j);
 			unlock_bin(j);
 			break;
 		}
 		unlock_bin(j);
 	}
-
-	/* Now patch up in case we over-allocated */
+	if (!mask) {
+		c = expand_heap(n);
+		if (!c) {
+			unlock(mal.split_merge_lock);
+			return 0;
+		}
+	}
 	trim(c, n);
-
+	unlock(mal.split_merge_lock);
 	return CHUNK_TO_MEM(c);
 }

@@ -382,6 +326,8 @@ void *realloc(void *p, size_t n)
 	self = MEM_TO_CHUNK(p);
 	n1 = n0 = CHUNK_SIZE(self);

+	if (n<=n0 && n0-n<=DONTCARE) return p;
+
 	if (IS_MMAPPED(self)) {
 		size_t extra = self->psize;
 		char *base = (char *)self - extra;
@@ -408,27 +354,24 @@ void *realloc(void *p, size_t n)
 	/* Crash on corrupted footer (likely from buffer overflow) */
 	if (next->psize != self->csize) a_crash();

-	/* Merge adjacent chunks if we need more space. This is not
-	 * a waste of time even if we fail to get enough space, because our
-	 * subsequent call to free would otherwise have to do the merge. */
-	if (n > n1 && alloc_fwd(next)) {
-		n1 += CHUNK_SIZE(next);
-		next = NEXT_CHUNK(next);
-	}
-	/* FIXME: find what's wrong here and reenable it..? */
-	if (0 && n > n1 && alloc_rev(self)) {
-		self = PREV_CHUNK(self);
-		n1 += CHUNK_SIZE(self);
-	}
-	self->csize = n1 | C_INUSE;
-	next->psize = n1 | C_INUSE;
+	lock(mal.split_merge_lock);

-	/* If we got enough space, split off the excess and return */
-	if (n <= n1) {
-		//memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD);
-		trim(self, n);
-		return CHUNK_TO_MEM(self);
+	size_t nsize = next->csize & C_INUSE ? 0 : CHUNK_SIZE(next);
+	if (n0+nsize >= n) {
+		int i = bin_index(nsize);
+		lock_bin(i);
+		if (!(next->csize & C_INUSE)) {
+			unbin(next, i);
+			unlock_bin(i);
+			next = NEXT_CHUNK(next);
+			self->csize = next->psize = n0+nsize | C_INUSE;
+			trim(self, n);
+			unlock(mal.split_merge_lock);
+			return CHUNK_TO_MEM(self);
+		}
+		unlock_bin(i);
 	}
+	unlock(mal.split_merge_lock);

 copy_realloc:
 	/* As a last resort, allocate a new chunk and copy to it. */
@@ -443,59 +386,51 @@ copy_free_ret:
 void __bin_chunk(struct chunk *self)
 {
 	struct chunk *next = NEXT_CHUNK(self);
-	size_t final_size, new_size, size;
-	int reclaim=0;
-	int i;
-
-	final_size = new_size = CHUNK_SIZE(self);

 	/* Crash on corrupted footer (likely from buffer overflow) */
 	if (next->psize != self->csize) a_crash();

-	for (;;) {
-		if (self->psize & next->csize & C_INUSE) {
-			self->csize = final_size | C_INUSE;
-			next->psize = final_size | C_INUSE;
-			i = bin_index(final_size);
-			lock_bin(i);
-			lock(mal.free_lock);
-			if (self->psize & next->csize & C_INUSE)
-				break;
-			unlock(mal.free_lock);
-			unlock_bin(i);
-		}
+	lock(mal.split_merge_lock);

-		if (alloc_rev(self)) {
-			self = PREV_CHUNK(self);
-			size = CHUNK_SIZE(self);
-			final_size += size;
-			if (new_size+size > RECLAIM && (new_size+size^size) > size)
-				reclaim = 1;
-		}
+	size_t osize = CHUNK_SIZE(self), size = osize;
+
+	/* Since we hold split_merge_lock, only transition from free to
+	 * in-use can race; in-use to free is impossible */
+	size_t psize = self->psize & C_INUSE ? 0 : CHUNK_PSIZE(self);
+	size_t nsize = next->csize & C_INUSE ? 0 : CHUNK_SIZE(next);

-		if (alloc_fwd(next)) {
-			size = CHUNK_SIZE(next);
-			final_size += size;
-			if (new_size+size > RECLAIM && (new_size+size^size) > size)
-				reclaim = 1;
+	if (psize) {
+		int i = bin_index(psize);
+		lock_bin(i);
+		if (!(self->psize & C_INUSE)) {
+			struct chunk *prev = PREV_CHUNK(self);
+			unbin(prev, i);
+			self = prev;
+			size += psize;
+		}
+		unlock_bin(i);
+	}
+	if (nsize) {
+		int i = bin_index(nsize);
+		lock_bin(i);
+		if (!(next->csize & C_INUSE)) {
+			unbin(next, i);
 			next = NEXT_CHUNK(next);
+			size += nsize;
 		}
+		unlock_bin(i);
 	}

-	if (!(mal.binmap & 1ULL<<i))
-		a_or_64(&mal.binmap, 1ULL<<i);
-
-	self->csize = final_size;
-	next->psize = final_size;
-	unlock(mal.free_lock);
+	int i = bin_index(size);
+	lock_bin(i);

-	self->next = BIN_TO_CHUNK(i);
-	self->prev = mal.bins[i].tail;
-	self->next->prev = self;
-	self->prev->next = self;
+	self->csize = size;
+	next->psize = size;
+	bin_chunk(self, i);
+	unlock(mal.split_merge_lock);

 	/* Replace middle of large chunks with fresh zero pages */
-	if (reclaim) {
+	if (size > RECLAIM && (size^(size-osize)) > size-osize) {
 		uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
 		uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
 #if 1

8.1.2.1. malloc 函数

void *malloc(size_t n)
{
	struct chunk *c;
	int i, j;
	uint64_t mask;

	if (adjust_size(&n) < 0) return 0;

...

	i = bin_index_up(n);
	if (i<63 && (mal.binmap & (1ULL<<i))) {
		lock_bin(i);
		c = mal.bins[i].head;
		if (c != BIN_TO_CHUNK(i) && CHUNK_SIZE(c)-n <= DONTCARE) {
			unbin(c, i);
			unlock_bin(i);
			return CHUNK_TO_MEM(c);
		}
		unlock_bin(i);
	}
	lock(mal.split_merge_lock);
	for (mask = mal.binmap & -(1ULL<<i); mask; mask -= (mask&-mask)) {
		j = first_set(mask);
		lock_bin(j);
		c = mal.bins[j].head;
		if (c != BIN_TO_CHUNK(j)) {
			unbin(c, j);
			unlock_bin(j);
			break;
		}
		unlock_bin(j);
	}
	if (!mask) {
		c = expand_heap(n);
		if (!c) {
			unlock(mal.split_merge_lock);
			return 0;
		}
	}
	trim(c, n);
	unlock(mal.split_merge_lock);
	return CHUNK_TO_MEM(c);
}

8.1.2.1.1. 逻辑简析

	if (i<63 && (mal.binmap & (1ULL<<i))) {
		lock_bin(i);
		c = mal.bins[i].head;
		if (c != BIN_TO_CHUNK(i) && CHUNK_SIZE(c)-n <= DONTCARE) {
			unbin(c, i);
			unlock_bin(i);
			return CHUNK_TO_MEM(c);
		}
		unlock_bin(i);
	}

对于i小于63的下标的bin上的空闲chunk相对来说比较小，如果正好下标i对应的bin上有合适的空闲chunk且不需要分割，就直接将该chunk从bin上取下返回给用户。（这里只是初步判断，且只找指定下标上的bin，又因为不会导致新分配内存，所以不需要对binmap加锁处理）

	lock(mal.split_merge_lock);
	for (mask = mal.binmap & -(1ULL<<i); mask; mask -= (mask&-mask)) {
		j = first_set(mask);
		lock_bin(j);
		c = mal.bins[j].head;
		if (c != BIN_TO_CHUNK(j)) {
			unbin(c, j);
			unlock_bin(j);
			break;
		}
		unlock_bin(j);
	}
	if (!mask) {
		c = expand_heap(n);
		if (!c) {
			unlock(mal.split_merge_lock);
			return 0;
		}
	}
	trim(c, n);
	unlock(mal.split_merge_lock);

接下来，涉及共享资源binmap的读写，所以都包含在split_merge_lock锁下面，从该锁命名可知，chunk的分割/合并操作都在加锁条件下处理。

这里遍历binmap上大于等于i位上所有的1，直到所有bin上都没有空闲chunk时，才去扩展堆空间分配新的chunk。遍历binmap，一方面，可以防止binmap被破坏，导致i对应位上是1，但对应的bin表是空，而不继续向高位（下标大的bin表）上找合适的chunk，导致循环等待i对应的bin表有空闲chunk为止。另一方面，也防止一次判断bin表空，而直接分配新的chunk，导致内存又出现异常增长。

如果binmap被破坏，导致大于等于i位上都是1，而对应的bin都是空表，这时遍历binmap后，开始分配新的chunk。由于bin表都是空表，本来就需要分配新的chunk，所以不会导致内存异常增长，仅仅是多遍历几次binmap而已。同时，后期分割/合并chunk都会写binmap，所以，即使binmap被破坏，binmap也会被自修复。

8.1.2.2. expand_heap 函数

由于expand_heap的调用整个被包含在split_merge_lock中，所以不再需要内部锁。

8.1.2.3. trim 函数

static void bin_chunk(struct chunk *self, int i)
{
	self->next = BIN_TO_CHUNK(i);
	self->prev = mal.bins[i].tail;
	self->next->prev = self;
	self->prev->next = self;
	if (self->prev == BIN_TO_CHUNK(i))
		a_or_64(&mal.binmap, 1ULL<<i);
}

static void trim(struct chunk *self, size_t n)
{
	size_t n1 = CHUNK_SIZE(self);
	struct chunk *next, *split;

	if (n >= n1 - DONTCARE) return;

	next = NEXT_CHUNK(self);
	split = (void *)((char *)self + n);

	split->psize = n | C_INUSE;
	split->csize = n1-n;
	next->psize = n1-n;
	self->csize = n | C_INUSE;

	int i = bin_index(n1-n);
	lock_bin(i);

	bin_chunk(split, i);

	unlock_bin(i);
}

trim相比于之前有两处变化：
1）split未设置flag为1，这说明split在游离状态时，即还没挂回bin表之前就被标记为空闲chunk。
2）原来调用__bin_chunk，现在改为调用bin_chunk。bin_chunk中不再做合并操作，而是直接将split挂回bin表，若split是第一个挂到bin表的chunk，再设置binmap对应位为1。（原来是先设置binmap，后挂回bin表，这里修正了逻辑）

8.1.2.4. __bin_chunk 函数

void __bin_chunk(struct chunk *self)
{
	struct chunk *next = NEXT_CHUNK(self);

	/* Crash on corrupted footer (likely from buffer overflow) */
	if (next->psize != self->csize) a_crash();

	lock(mal.split_merge_lock);

	size_t osize = CHUNK_SIZE(self), size = osize;

	/* Since we hold split_merge_lock, only transition from free to
	 * in-use can race; in-use to free is impossible */
	size_t psize = self->psize & C_INUSE ? 0 : CHUNK_PSIZE(self);
	size_t nsize = next->csize & C_INUSE ? 0 : CHUNK_SIZE(next);

	if (psize) {
		int i = bin_index(psize);
		lock_bin(i);
		if (!(self->psize & C_INUSE)) {
			struct chunk *prev = PREV_CHUNK(self);
			unbin(prev, i);
			self = prev;
			size += psize;
		}
		unlock_bin(i);
	}
	if (nsize) {
		int i = bin_index(nsize);
		lock_bin(i);
		if (!(next->csize & C_INUSE)) {
			unbin(next, i);
			next = NEXT_CHUNK(next);
			size += nsize;
		}
		unlock_bin(i);
	}

	int i = bin_index(size);
	lock_bin(i);

	self->csize = size;
	next->psize = size;
	bin_chunk(self, i);
	unlock(mal.split_merge_lock);

	/* Replace middle of large chunks with fresh zero pages */
	if (size > RECLAIM && (size^(size-osize)) > size-osize) {
		uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
		uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
#if 1
		__madvise((void *)a, b-a, MADV_DONTNEED);
#else
		__mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
			MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
#endif
	}

	unlock_bin(i);
}

/* Since we hold split_merge_lock, only transition from free to
 * in-use can race; in-use to free is impossible */

由于我们持有split_merge_lock，所以只有从空闲到使用中的转换才存在竞争，从使用中到空闲不存在竞争？？
改进后的malloc中分配小内存时的第一段逻辑是没有加锁的，这里所说的莫非就是那里的申请跟这里的合并存在资源竞争？

由于分配和释放共用split_merge_lock锁，所以为了防止分配时被阻塞过久，改进后的__bin_chunk中最多只合并一次前后空闲chunk。

8.1.2.5. realloc 函数

void *realloc(void *p, size_t n)
{
	struct chunk *self, *next;
	size_t n0, n1;
	void *new;

	if (!p) return malloc(n);

	if (adjust_size(&n) < 0) return 0;

	self = MEM_TO_CHUNK(p);
	n1 = n0 = CHUNK_SIZE(self);

	if (n<=n0 && n0-n<=DONTCARE) return p;

...

	/* Crash on corrupted footer (likely from buffer overflow) */
	if (next->psize != self->csize) a_crash();

	lock(mal.split_merge_lock);

	size_t nsize = next->csize & C_INUSE ? 0 : CHUNK_SIZE(next);
	if (n0+nsize >= n) {
		int i = bin_index(nsize);
		lock_bin(i);
		if (!(next->csize & C_INUSE)) {
			unbin(next, i);
			unlock_bin(i);
			next = NEXT_CHUNK(next);
			self->csize = next->psize = n0+nsize | C_INUSE;
			trim(self, n);
			unlock(mal.split_merge_lock);
			return CHUNK_TO_MEM(self);
		}
		unlock_bin(i);
	}
	unlock(mal.split_merge_lock);

copy_realloc:
	/* As a last resort, allocate a new chunk and copy to it. */
	new = malloc(n-OVERHEAD);
	if (!new) return 0;
copy_free_ret:
	memcpy(new, p, n0-OVERHEAD);
	free(CHUNK_TO_MEM(self));
	return new;
}

8.1.2.5.1. 逻辑简析

if (n<=n0 && n0-n<=DONTCARE) return p;

n<=n0，说明是缩小内存；n0-n<=DONTCARE，说明当前chunk不需要进行裁剪，所以直接返回原内存即可。

	lock(mal.split_merge_lock);

	size_t nsize = next->csize & C_INUSE ? 0 : CHUNK_SIZE(next);
	if (n0+nsize >= n) {
		int i = bin_index(nsize);
		lock_bin(i);
		if (!(next->csize & C_INUSE)) {
			unbin(next, i);
			unlock_bin(i);
			next = NEXT_CHUNK(next);
			self->csize = next->psize = n0+nsize | C_INUSE;
			trim(self, n);
			unlock(mal.split_merge_lock);
			return CHUNK_TO_MEM(self);
		}
		unlock_bin(i);
	}
	unlock(mal.split_merge_lock);

只有当前chunk的下一个chunk空闲，且当前chunk大小（n0）加上下一个空闲chunk的大小（nsize）大于等于重新分配的大小（n）时，才尝试合并当前chunk和下一个空闲chunk，然后按重新分配的大小进行裁剪。

copy_realloc:
	/* As a last resort, allocate a new chunk and copy to it. */
	new = malloc(n-OVERHEAD);
	if (!new) return 0;
copy_free_ret:
	memcpy(new, p, n0-OVERHEAD);
	free(CHUNK_TO_MEM(self));
	return new;
}

分配n-OVERHEAD大小内存，则从原来内存中拷贝n0-OVERHEAD长度的数据到新的内存中，然后释放原来的内存块。

缺陷：内存越界访问
n0是原来chunk大小，n是重新申请的大小，n0和n大小关系如下：
1）n0 > n + DONTCARE，缩小内存，内存拷贝时，出现越界访问
2）n0 < n，扩展内存，内存拷贝时，正常

社区修复补丁：https://git.musl-libc.org/cgit/musl/commit/?id=cb5babdc8d624a3e3e7bea0b4e28a677a2f2fc46

8.2. 多线程场景下fork，子进程调用malloc存在死锁

通过fork创建的一个子进程几乎但不完全与父进程相同。子进程得到与父进程用户级虚拟地址空间相同的（但是独立的）一份拷贝，包括文本、数据和bss段、堆以及用户栈等。子进程还获得与父进程任何打开文件描述符相同的拷贝，这就意味着子进程可以读写父进程中任何打开的文件，父进程和子进程之间最大的区别在于它们有着不同的PID。

但是有一点需要注意的是，在Linux中，fork的时候只复制当前线程到子进程。也就是说除了调用fork的线程外，其他线程在子进程中“蒸发”了。这就是多线程中fork所带来的一切问题的根源所在了。

其中互斥锁是多线程fork大部分问题的关键部分。在大多数操作系统上，为了性能的因素，锁基本上都是实现在用户态的而非内核态（因为在用户态实现最方便，基本上就是通过原子操作或者memory barrier实现的），所以调用fork的时候，会复制父进程的所有锁到子进程中。

问题就出在这了。从操作系统的角度上看，对于每一个锁都有它的持有者，即对它进行lock操作的线程。假设在fork之前，一个线程对某个锁进行的lock操作，即持有了该锁，然后另外一个线程调用了fork创建子进程。可是在子进程中持有那个锁的线程却"消失"了，从子进程的角度来看，这个锁被“永久”的上锁了，因为它的持有者“蒸发”了。

那么如果子进程中的任何一个线程对这个已经被持有的锁进行lock操作话，就会发生死锁。

对于用户自己使用的锁，可以在fork之前调用pthread_atfork来清理线程中互斥锁的状态，从而防止死锁，pthread_atfork的用法如下：

函数原型：
#include <pthread.h>

pthread_atfork(void (*prepare)(void), void(*parent)(void), void(*child)(void))

参数：
prepare：在fork()函数创建子进程之前调用，可以用来对多线程中的锁进行加锁操作
parent: 在fork()函数创建子进程后，在fork()函数返回之前，在父进程中被执行，可以用来对多线程中的锁进行解锁操作
child: 在fork()函数返回之前，在子进程中执行，可以用来对多线程中的锁进行解锁操作

但是对于库函数，却无法使用pthread_atfork来控制其内部锁。有相当一部分线程安全的库函数都是在内部通过持有互斥锁的方式来实现的，比如几乎所有程序都会用到的C/C++标准库函数malloc、printf等等。

比如一个多线程程序在fork之前难免会分配动态内存，这就必然会用到malloc函数；而在fork之后的子进程中也难免要分配动态内存，这也同样要用到malloc，可这却是不安全的，因为有可能malloc内部的锁已经在fork之前被某一个线程所持有了，而那个线程却在子进程中消失了。

8.2.1. 修复补丁

malloc中原来存在bin锁，修复堆内存无限增长后，增加了大锁split_merge_lock，又增大了死锁的概率，针对死锁问题，社区提供了修复方案，在fork中进行解锁，关键补丁为：https://git.musl-libc.org/cgit/musl/commit/?id=167390f05564e0a4d3fcb4329377fd7743267560

作为 Austin Group tracker issue #62 的结果，POSIX 的未来版本已经放弃了 fork 是 AS-safe 的要求。这允许但不需要实现将 fork 与内部锁同步，并为多线程父级的fork子进程提供部分或完全不受限制的执行环境，在那里他们可以继续使用标准库（根据 POSIX，他们只能可移植地使用安全的函数）。

直到最近，接受这项津贴似乎并不可取。然而，提交 8ed2bd8bfcb4ea6448afb55a941f4b5b2b0398c0 通过将潜在的极低概率灾难性状态损坏转换为可预测的死锁，暴露了应用程序和库依赖于在多线程fork（MT-forked）子进程中使用 malloc 和其他非安全接口的能力的程度。处理这些影响对用户/发行版来说是一个巨大的负担。

虽然看起来应用程序中的大多数不可移植的使用可以通过足够的努力来修复，至少其中一些似乎发生在语言运行时中，这些运行时暴露了在子进程中运行不受限制的代码的能力，作为与程序员的合同的一部分。修复此类合同的任何尝试不仅是技术问题，而且是社会问题，并且可能难以处理。

这个补丁扩展了 fork 函数来为父进程中的所有 libc 单例获取锁，并释放或重置子进程中的这些锁，这样当底层的 fork 操作发生时，这些锁保护的状态是一致的，并为子进程做好使用准备。在父进程是单线程的情况下会跳过锁定，以免干扰单线程程序中 fork 的遗留安全属性。锁顺序大多是任意的，但必须在任何可能使用 malloc 的子系统上的锁之后获取 malloc 锁（包括使用时的碰撞分配器bump allocator），并且在持有线程列表锁时不能获取非安全锁，强加了最后采取它的要求。

8.2.2. 补丁分析

如果who小于0，则加锁；如果who等于0，则解锁；如果who大于0，则重置锁资源。

如果need_locks大于0，说明父进程是多线程。

多线程下，父进程首先获取所有锁，在fork之前，让这些锁保护的状态是一致的。然后调用_Fork函数创建子进程，创建成功后，这些锁的状态也被子进程继承。父进程中ret是非0，子进程中ret为0。_Fork之后，父进程解除所有锁，子进程重置所有锁。

9. 参考

• [阅读型]新版musl libc(1.2.2)堆管理之源码剖析！
• 从一次 CTF 出题谈 musl libc 堆漏洞利用
• dlmalloc 2.8.6 源码详解(1)
• Linux堆内存管理深入分析（上）
• Linux堆内存管理深入分析（下）
• Linux进程分配内存的两种方式–brk() 和mmap()
• 谨慎使用多线程中的fork

10. 历史记录

• 2021-11-20
  完成初稿，包括：前言、设计思想、malloc本质、数据结构、malloc/free函数、calloc函数、realloc函数、缺陷、参考。
• 2021-11-22
  __bin_chunk中增加对__madvise说明