glibc源码阅读

Posted on Edited on In Views: Word count in article: 63k Reading time ≈ 57 mins.
glibc2.31 malloc.c

目标：

  • 做出malloc导图
  • 理解largebin_attack等攻击利用

malloc.c

__malloc_assert

__int_malloc()函数的断言，一个用于处理断言失败的 C 语言宏和函数实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#ifndef NDEBUG
# define __assert_fail(assertion, file, line, function)			\
	 __malloc_assert(assertion, file, line, function)

extern const char *__progname;//声明一个外部变量 __progname，它存储程序的名称。

static void//静态函数 __malloc_assert，用于处理断言失败的情况。因为它是静态的，所以它只能在当前文件中被访问。
__malloc_assert (const char *assertion, const char *file, unsigned int line,
		 const char *function)
{
  (void) __fxprintf (NULL, "%s%s%s:%u: %s%sAssertion `%s' failed.\n",
		     __progname, __progname[0] ? ": " : "",
		     file, line,
		     function ? function : "", function ? ": " : "",
		     assertion);
  fflush (stderr);//刷新标准错误流
  abort ();//函数被调用以异常终止程序执行
}
#endif

代码总结

  • 此代码块定义了一个断言失败时的处理机制：
    • 在程序的调试版本中，如果某个断言失败，__assert_fail 宏会被调用。
    • 宏调用 __malloc_assert，该函数会生成详细的错误信息，并将其输出到标准错误流，然后终止程序。
  • 由于整个处理是通过宏和函数来完成的，因此提供了灵活性和可读性，便于在需要时进行调试，而在发布版本中可以通过定义 NDEBUG 来禁用这些检查。

USE_TCACHE

tcache的初始化

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
#if USE_TCACHE
/* We want 64 entries.  This is an arbitrary limit, which tunables can reduce.  */
# define TCACHE_MAX_BINS		64
# define MAX_TCACHE_SIZE	tidx2usize (TCACHE_MAX_BINS-1)

/* Only used to pre-fill the tunables.定义了 tidx2usize 宏，这个宏用于将bin的idx转换为相应的字节大小。*/
# define tidx2usize(idx)	(((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - SIZE_SZ)

/* When "x" is from chunksize().定义了 csize2tidx 宏，将一个给定的chunk大小 x 转换为对应的bin idx。 */
# define csize2tidx(x) (((x) - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT)
/* When "x" is a user-provided size.  */
# define usize2tidx(x) csize2tidx (request2size (x))

/* With rounding and alignment, the bins are...
   idx 0   bytes 0..24 (64-bit) or 0..12 (32-bit)
   idx 1   bytes 25..40 or 13..20
   idx 2   bytes 41..56 or 21..28
   etc.  */

/* This is another arbitrary limit, which tunables can change.  Each
   tcache bin will hold at most this number of chunks.  */
# define TCACHE_FILL_COUNT 7
//tcache 中最多 7 个
/* Maximum chunks in tcache bins for tunables.  This value must fit the range
   of tcache->counts[] entries, else they may overflow.  */
# define MAX_TCACHE_COUNT UINT16_MAX
#endif

这里见名知意，例：tidx2usize —> tcache_idx to unsigned_size

一些设置

目的：提高项目的可移植性和开启一些优化措施

1
2
3
4
5
6
7
8
9
10
/*
  REALLOC_ZERO_BYTES_FREES should be set if a call to
  realloc with zero bytes should be the same as a call to free.
  This is required by the C standard. Otherwise, since this malloc
  returns a unique pointer for malloc(0), so does realloc(p, 0).
*/
//realloc()参数为 0 相当于free
#ifndef REALLOC_ZERO_BYTES_FREES
#define REALLOC_ZERO_BYTES_FREES 1
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
/*
  TRIM_FASTBINS 控制非常小的内存块的 free() 调用是否可以立即导致内存修剪。
  将其设置为 true (1) 可以减少内存占用，但几乎总是会降低使用大量小块的程序的速度。

  仅在您愿意牺牲一些速度以在释放大量小块内存的程序中更积极地减少系统级内存占用时，
  定义此选项。通过将 MXFAST 设置为 0，您可以获得基本相同的效果，但这可能导致
  使用许多小块的程序出现更大的性能下降。 TRIM_FASTBINS 是一个折中的编译时选项，
  它只禁用那些靠近顶部内存的块被放置在快速链表中。
*/

#ifndef TRIM_FASTBINS
#define TRIM_FASTBINS  0
#endif
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/* 从操作系统获取更多内存的定义。 */
#define MORECORE         (*__morecore)
#define MORECORE_FAILURE 0
void * __default_morecore (ptrdiff_t);
void *(*__morecore)(ptrdiff_t) = __default_morecore;

#include <string.h>

/*
  与 MORECORE 相关的声明。默认情况下，依赖于 sbrk。
*/

/*
  MORECORE 是从系统获取更多内存的函数名称。有关编写替代 MORECORE 函数的一般指导，
  以及 WIN32 的版本和 pre-OSX macOS 的示例版本，请参见下文。
*/

#ifndef MORECORE
#define MORECORE sbrk
#endif

/*
  MORECORE_FAILURE 是 MORECORE 和 mmap 失败时返回的值。
  由于它不能是有效的内存地址，并且必须反映标准系统调用的值，
  因此您可能不应该尝试重新定义它。
*/

#ifndef MORECORE_FAILURE
#define MORECORE_FAILURE (-1)
#endif

/*
  如果 MORECORE_CONTIGUOUS 为真，则利用连续调用 MORECORE 
  并使用正参数总是返回连续递增地址的事实。 
  这在 UNIX 的 sbrk 中是正确的。即使没有定义，
  当区域恰好是连续的时，malloc 也允许从不同调用中获得的区域跨越分配。
  但是在适用时定义这个可以启用更强的一致性检查和空间效率。
*/

#ifndef MORECORE_CONTIGUOUS
#define MORECORE_CONTIGUOUS 1
#endif

/*
  如果您的 MORECORE 版本在给定负参数时无法将空间释放回系统，
  请定义 MORECORE_CANNOT_TRIM。 
  这通常仅在您使用无法处理负参数的手工编写的 MORECORE 函数时是必要的。
*/

/* #define MORECORE_CANNOT_TRIM */

/*  MORECORE_CLEARS (默认 1)
     被映射到 MORECORE 的例程清零内存的程度：
     从不 (0)、仅对新分配的空间 (1) 或总是 (2)。
     (1) 和 (2) 之间的区别是必要的，因为在某些系统上，
     如果应用程序先将断点值递减，然后再增加，
     则重新分配空间的内容是未指定的。
 */

#ifndef MORECORE_CLEARS
# define MORECORE_CLEARS 1
#endif

/*
   MMAP_AS_MORECORE_SIZE 是使用 mmap 作为备份时，如果 sbrk 失败，则使用的最小 mmap 大小参数。
   该值必须是页面大小的倍数。 
   此备份策略通常仅在系统的地址空间中存在“空洞”时适用，
   这样 sbrk 不能执行连续扩展，但系统上仍然有空间可用。
   对于已知对此有用的系统（即大多数 Linux 内核），
   这仅在程序分配大量内存时发生。
   鉴于此，以及 mmap 区域往往有限，大小应该较大，
   以避免过多的 mmap 调用，从而避免耗尽内核资源。 
*/

#ifndef MMAP_AS_MORECORE_SIZE
#define MMAP_AS_MORECORE_SIZE (1024 * 1024)
#endif

/*
  定义 HAVE_MREMAP 以使 realloc() 使用 mremap() 重新分配大块内存。
*/

#ifndef HAVE_MREMAP
#define HAVE_MREMAP 0
#endif

/* 我们可能需要支持 __malloc_initialize_hook 以实现向后兼容性。 */

#if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_24)
# define HAVE_MALLOC_INIT_HOOK 1
#else
# define HAVE_MALLOC_INIT_HOOK 0
#endif

一些声明

__libc_malloc()

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
/*
  这个版本的 malloc 支持标准的 SVID/XPG mallinfo 
  函数，该函数返回一个包含使用属性和统计信息的结构体。
  它应该可以在任何符合 SVID/XPG 的系统上工作，该系统在 
  /usr/include/malloc.h 中定义了 struct mallinfo。
  （如果您想自己安装这样的东西，可以根据上面和下面的描述
  删除初步声明，并将其保存到一个 malloc.h 文件中。但实际上
  没有 compelling 的理由去费心去做这件事。）

  主要需要的声明是由 mallinfo() 返回的 mallinfo 结构体。
  SVID/XPG 的 mallinfo 结构体包含了一些在这个版本的 malloc 
  中甚至没有意义的字段。这些字段则被 mallinfo() 填充
  为其他可能感兴趣的数字。
*/

/* ---------- description of public routines ------------ */

/*
  malloc(size_t n)
  返回一个指向新分配的至少 n 字节的内存块的指针，如果没有可用空间，则返回 null。
  此外，在失败时，ANSI C 系统上的 errno 被设置为 ENOMEM。

  如果 n 为零，malloc 返回一个最小大小的块。 
  （在大多数 32 位系统上，最小大小为 16 字节，而在 64 位系统上为 24 或 32 字节。）
  在大多数系统上，size_t 是一种无符号类型，因此对于负参数的调用
  被解释为请求巨大的空间，这通常会失败。
  支持的 n 的最大值在各系统之间有所不同，但在任何情况下都小于
  size_t 的最大可表示值。
*/
void*  __libc_malloc(size_t);
libc_hidden_proto (__libc_malloc)//宏，用于隐藏这个函数的实现细节，使其在外部不可见

__libc_free()

1
2
3
4
5
6
7
8
9
10
11
/*
  free(void* p)
  释放由 p 指向的内存块，该内存块是之前使用 malloc 或相关例程（如 realloc）分配的。
  如果 p 为 null，则没有任何效果。如果 p 已经被释放，则可能会产生任意（即，不良的！）
  效果。

  除非被禁用（使用 mallopt），否则释放非常大的空间时，系统会在可能的情况下
  自动触发将未使用的内存返回给系统的操作，从而减少程序的内存占用。
*/
void     __libc_free(void*);
libc_hidden_proto (__libc_free)//宏，用于隐藏这个函数的实现细节，使其在外部不可见

__libc_calloc

1
2
3
4
5
/*
  calloc(size_t n_elements, size_t element_size);
  返回指向 n_elements * element_size 字节的指针，并将所有位置设置为零。
*/
void*  __libc_calloc(size_t, size_t);

__libc_realloc()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
  realloc(void* p, size_t n)
  返回一个大小为 n 的内存块指针，该内存块包含与指针 p 相同的数据，直到 (n, p 的大小) 中的最小值字节。如果没有可用空间，则返回 null。

  返回的指针可能与 p 相同，也可能不同。算法优先选择扩展 p，如果不可能，则使用相当于 malloc-copy-free 的序列。

  如果 p 为 null，则 realloc 相当于 malloc。

  如果没有可用空间，realloc 将返回 null，errno 被设置（如果在 ANSI 下），同时 p 不会被释放。

  如果 n 小于 p 当前持有的字节数，新的未使用空间将被截断并在可能的情况下释放。除非定义了 #define REALLOC_ZERO_BYTES_FREES，否则 realloc 的大小参数为零时（重新）分配一个最小大小的块。

  通过 mmap 方式内部获得的大块内存将始终使用 malloc-copy-free 序列扩展，除非系统支持 MREMAP（目前仅限于 Linux）。

  不支持旧 Unix realloc 约定，即允许将最后释放的内存块作为 realloc 的参数。
*/
void*  __libc_realloc(void*, size_t);
libc_hidden_proto (__libc_realloc)

__libc_memalign

1
2
3
4
5
6
7
8
9
10
11
/*
  memalign(size_t alignment, size_t n);
  返回指向新分配的 n 字节内存块的指针，该内存块的对齐方式符合 alignment 参数的要求。

  alignment 参数应该是 2 的幂。如果参数不是 2 的幂，则使用最近的较大 2 的幂。
  正常的 malloc 调用保证了 8 字节对齐，因此不要使用 8 或更小的参数调用 memalign。

  过度依赖 memalign 会导致内存碎片化。
*/
void*  __libc_memalign(size_t, size_t);
libc_hidden_proto (__libc_memalign)

__libc_valloc

1
2
3
4
5
6
/*
  valloc(size_t n);
  等同于 memalign(pagesize, n)，其中 pagesize 是系统的页面大小。
  如果页面大小未知，则使用 4096 字节作为默认值。
*/
void*  __libc_valloc(size_t);

跳过，感觉这些没啥意思，跳转978行

DEFAULT_MMAP_MAX

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
  M_MMAP_MAX 是同时使用 mmap 服务的最大请求数量。
  这个参数存在的原因是，有些系统对 mmap 使用的内部表有数量限制，
  超过一定数量可能会降低性能。

  默认值设置为一个仅作为保护的值。
  将该值设置为 0 会禁用使用 mmap 来处理大请求。
*/
#define M_MMAP_MAX             -4

#ifndef DEFAULT_MMAP_MAX
#define DEFAULT_MMAP_MAX       (65536)
#endif

#include <malloc.h>

#ifndef RETURN_ADDRESS
#define RETURN_ADDRESS(X_) (NULL)
#endif

重要函数声明

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
/* Forward declarations.  */
struct malloc_chunk;
typedef struct malloc_chunk* mchunkptr;//这个指针指向malloc_chunk的头部

/* Internal routines.  */

static void*  _int_malloc(mstate, size_t);
static void     _int_free(mstate, mchunkptr, int);
static void*  _int_realloc(mstate, mchunkptr, INTERNAL_SIZE_T,
			   INTERNAL_SIZE_T);
static void*  _int_memalign(mstate, size_t, size_t);
static void*  _mid_memalign(size_t, size_t, void *);

static void malloc_printerr(const char *str) __attribute__ ((noreturn));

static void* mem2mem_check(void *p, size_t sz);
static void top_check(void);
static void munmap_chunk(mchunkptr p);
#if HAVE_MREMAP
static mchunkptr mremap_chunk(mchunkptr p, size_t new_size);
#endif

static void*   malloc_check(size_t sz, const void *caller);
static void      free_check(void* mem, const void *caller);
static void*   realloc_check(void* oldmem, size_t bytes,
			       const void *caller);
static void*   memalign_check(size_t alignment, size_t bytes,
				const void *caller);

chunk representations

chunk的表示

1
2
3
4
5
6
7
8
9
10
11
12
struct malloc_chunk {

  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

chunk的一些计算操作

mem就是返回给用户的指针，即上面的 fd 的位置

堆地址是由低地址往高地址生长的

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
/*
  ---------- Size and alignment checks and conversions ----------
*/

/* conversion from malloc headers to user pointers, and back */

#define chunk2mem(p)   ((void*)((char*)(p) + 2*SIZE_SZ))
#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))

/* The smallest possible chunk */
//计算最小内存块的大小，即从 struct malloc_chunk 结构体中 fd_nextsize 字段的偏移量。
#define MIN_CHUNK_SIZE        (offsetof(struct malloc_chunk, fd_nextsize))

/* The smallest size we can malloc is an aligned minimal chunk */
//定义可以分配的最小内存块的大小。它确保计算出的大小是对齐的，使用 MALLOC_ALIGN_MASK 来进行对齐。
#define MINSIZE  \
  (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))

/* Check if m has acceptable alignment */

#define aligned_OK(m)  (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0)
//判断给定内存块指针 p 是否对齐。如果对齐规则是 2 * SIZE_SZ，则直接使用指针 p，否则使用 chunk2mem(p) 进行转换。
#define misaligned_chunk(p) \
  ((uintptr_t)(MALLOC_ALIGNMENT == 2 * SIZE_SZ ? (p) : chunk2mem (p)) \
   & MALLOC_ALIGN_MASK)

/* pad request bytes into a usable size -- internal version */

#define request2size(req)                                         \
  (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
   MINSIZE :                                                      \
   ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

/* 这个内联函数确保请求的大小 req 不会溢出 PTRDIFF_MAX。如果 req 大于 PTRDIFF_MAX，函数返回 false。否则，调用 request2size 计算可用大小，并将结果存储在 sz 中，最后返回 true */
static inline bool
checked_request2size (size_t req, size_t *sz) __nonnull (1)
{
  if (__glibc_unlikely (req > PTRDIFF_MAX))
    return false;
  *sz = request2size (req);
  return true;
}

chunk的物理操作

即 A M P 哪几个标志位

这里的东西可以在分析代码逻辑时跳转回来看

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/*
   --------------- Physical chunk operations ---------------
 */


/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
#define PREV_INUSE 0x1

/* extract inuse bit of previous chunk */
#define prev_inuse(p)       ((p)->mchunk_size & PREV_INUSE)


/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
#define IS_MMAPPED 0x2

/* check for mmap()'ed chunk */
#define chunk_is_mmapped(p) ((p)->mchunk_size & IS_MMAPPED)


/* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
   from a non-main arena.  This is only set immediately before handing
   the chunk to the user, if necessary.  */
#define NON_MAIN_ARENA 0x4

/* Check for chunk from main arena.  */
#define chunk_main_arena(p) (((p)->mchunk_size & NON_MAIN_ARENA) == 0)

/* Mark a chunk as not being on the main arena.  */
#define set_non_main_arena(p) ((p)->mchunk_size |= NON_MAIN_ARENA)

/*
   提取大小时需要屏蔽掉的位

   注意：IS_MMAPPED 在那些不应看到内存映射块的宏中被故意保留在大小字段中。这会导致在扩展或改编这个 malloc 时，如果不小心尝试访问这些块，会产生有用的核心转储。
*/

#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)

/* Get size, ignoring use bits */
#define chunksize(p) (chunksize_nomask (p) & ~(SIZE_BITS))

/* Like chunksize, but do not mask SIZE_BITS.  */
#define chunksize_nomask(p)         ((p)->mchunk_size)

/* Ptr to next physical malloc_chunk. */
#define next_chunk(p) ((mchunkptr) (((char *) (p)) + chunksize (p)))

/* Size of the chunk below P.  Only valid if !prev_inuse (P).  */
#define prev_size(p) ((p)->mchunk_prev_size)

/* Set the size of the chunk below P.  Only valid if !prev_inuse (P).  */
#define set_prev_size(p, sz) ((p)->mchunk_prev_size = (sz))

/* Ptr to previous physical malloc_chunk.  Only valid if !prev_inuse (P).  */
#define prev_chunk(p) ((mchunkptr) (((char *) (p)) - prev_size (p)))

/* Treat space at ptr + offset as a chunk */
#define chunk_at_offset(p, s)  ((mchunkptr) (((char *) (p)) + (s)))

/* extract p's inuse bit */
#define inuse(p)							      \
  ((((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size) & PREV_INUSE)

/* set/clear chunk as being inuse without otherwise disturbing */
#define set_inuse(p)							      \
  ((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size |= PREV_INUSE

#define clear_inuse(p)							      \
  ((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size &= ~(PREV_INUSE)


/* check/set/clear inuse bits in known places */
#define inuse_bit_at_offset(p, s)					      \
  (((mchunkptr) (((char *) (p)) + (s)))->mchunk_size & PREV_INUSE)

#define set_inuse_bit_at_offset(p, s)					      \
  (((mchunkptr) (((char *) (p)) + (s)))->mchunk_size |= PREV_INUSE)

#define clear_inuse_bit_at_offset(p, s)					      \
  (((mchunkptr) (((char *) (p)) + (s)))->mchunk_size &= ~(PREV_INUSE))


/* Set size at head, without disturbing its use bit */
#define set_head_size(p, s)  ((p)->mchunk_size = (((p)->mchunk_size & SIZE_BITS) | (s)))

/* Set size/use field */
#define set_head(p, s)       ((p)->mchunk_size = (s))

/* Set size at footer (only when chunk is not in use) */
#define set_foot(p, s)       (((mchunkptr) ((char *) (p) + (s)))->mchunk_prev_size = (s))


#pragma GCC poison mchunk_size
#pragma GCC poison mchunk_prev_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
/*
   -------------------- Internal data structures --------------------
   内部数据结构
   所有内部状态都保存在下面定义的 malloc_state 实例中。除了在两种可选情况下，没有其他静态变量：
 * 如果定义了 USE_MALLOC_LOCK，则上面声明的 mALLOC_MUTEx。
 * 如果 mmap 不支持 MAP_ANONYMOUS，则为 mmap 提供一个虚拟文件描述符。

   注意许多技巧旨在最小化总的记账空间需求。结果大约是 1K 字节（对于 4 字节指针和 size_t）。
*/

/*
	Bins

   一个用于free chunk的数组。每个bin都是双向链接的。bins之间的间隔大致成比例（对数）分布。bin的数量非常多（128个）。这看起来可能有些过多，但在实际使用中效果非常好。大多数bin所包含的大小在 malloc 请求中并不常见，但对于片段和合并的块组合来说却是比较常见的，这正是这些箱子所存储的内容，因此可以快速找到。所有过程都保持不变，即没有一个合并的块物理上与另一个合并的chunk相邻，因此列表中的每个chunk都知道其前后是使用中的chunk或内存的末尾。

   bins中的chunk按大小顺序排列，大小相同的chunk在近似最近使用的块中进行排序。对于small bins而言，排序并不是必须的，因为它们都包含相同大小的chunk，但对于较大的chunk，有助于最佳适配分配。这些列表只是顺序的。保持它们有序几乎从来不需要遍历到足以使用更复杂的有序数据结构的程度。

   相同大小的chunk以最近释放的chunk在前的顺序链接，分配则从后面取。这导致了 LRU（FIFO）分配顺序，这通常为每个chunk提供了与相邻释放的chunk合并的平等机会，从而产生了更大的自由块并减少了碎片化。

   为了简化在双向链表中的使用，每个箱头都充当 malloc_chunk。这避免了对头的特殊处理。但为了节省空间并改善局部性，我们仅分配箱子的 fd/bk 指针，然后利用重定位技巧将这些视为 malloc_chunk* 的字段。
*/

typedef struct malloc_chunk *mbinptr;

/* 地址计算 -- 请注意， bin_at(0) 不存在 */
#define bin_at(m, i) \
  (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))			      \
             - offsetof (struct malloc_chunk, fd))

/* ++bin 的类似物 */
#define next_bin(b)  ((mbinptr) ((char *) (b) + (sizeof (mchunkptr) << 1)))

/* 关于箱子内列表方向性的提醒 */
#define first(b)     ((b)->fd)
#define last(b)      ((b)->bk)

bin_at() 是一个宏，用于通过给定的索引从内存管理器（m）的 bins 数组中获取特定的 bin（内存块管理单元）。它的实现依赖于 offsetof，计算出特定 bin 的地址，并进行适当的类型转换。

参数说明：

  • m: 这是一个指向内存管理结构的指针，通常是一个包含多个 bins 的结构体。
  • i: 这是一个 bin 的索引，表示你想要获取的 bin 的位置（注意，索引是从 1 开始的，bin_at(0) 不存在）。

宏 bin_at(m, i)通过 bin index 获得 bin 的链表头，chunk 中的fd 和 bk 用于将空闲 chunk 链入链表中，而对于每个 bin 的链表头，只需要这两个域就可以了，prev_size 和 size 对链表 都来说都没有意义，浪费空间，ptmalloc 为了节约这点内存空间，增大 cpu 高速缓存的命中 率，在 bins 数组中只为每个 bin 预留了两个指针的内存空间用于存放 bin 的链表头的 fb 和 bk 指针。

从 bin_at(m, i)的定义可以看出，bin[0]不存在，以 SIZE_SZ 为 4B 的平台为例，bin[1]的前 4B 存储的是指针 fb，后 4B 存储的是指针 bk，而 bin_at 返回的是 malloc_chunk 的指针，由 于 fb 在 malloc_chunk 的偏移地址为 offsetof (struct malloc_chunk, fd))=8，所以用 fb 的地址减 去 8 就得到 malloc_chunk 的地址。但切记，对 bin 的链表头的 chunk，一定不能修改 prev_size 和 size 域，这两个域是与其他 bin 的链表头的 fb 和 bk 内存复用的。

宏 next_bin(b)用于获得下一个 bin 的地址，根据前面的分析，我们知道只需要将当前 bin 的地址向后移动两个指针的长度就得到下一个 bin 的链表头地址。 每个 bin 使用双向循环链表管理空闲 chunk，bin 的链表头的指针 fb 指向第一个可用的 chunk，指针 bk 指向最后一个可用的 chunk。宏 first(b)用于获得 bin 的第一个可用 chunk， 宏 last(b)用于获得 bin 的最后一个可用的 chunk，这两个宏便于遍历 bin，而跳过 bin 的链表 头。

Indexing

这段代码主要是根据chunk的size去计算出合适的bins。

smallbin:

ptmalloc使用small bins管理空闲小chunk，每个small bin中的chunk的大小与bin的index 有如下关系： Chunk_size=2 * SIZE_SZ * index 在 SIZE_SZ 为 4B 的平台上，small bins 中的 chunk 大小是以 8B 为公差的等差数列，最大 的 chunk 大小为 504B，最小的 chunk 大小为 16B，所以实际共 62 个 bin。分别为 16B、24B、 32B，„„，504B。在 SIZE_SZ 为 8B 的平台上，small bins 中的 chunk 大小是以 16B 为公差 的等差数列，最大的 chunk 大小为 1008B，最小的 chunk 大小为 32B，所以实际共 62 个 bin。 分别为 32B、48B、64B，„„，1008B。 ptmalloc 维护了 62 个双向环形链表（每个链表都具有链表头节点，加头节点的最大作 用就是便于对链表内节点的统一处理，即简化编程），每一个链表内的各空闲 chunk 的大小 一致，因此当应用程序需要分配某个字节大小的内存空间时直接在对应的链表内取就可以了，这样 既可以很好的满足应用程序的内存空间申请请求而又不会出现太多的内存碎片。我们可 以用 如下图来表示在 SIZE_SZ 为 4B 的平台上 ptmalloc 对 512B 字节以下的空闲 chunk 组织方 式 （所谓的分箱机制）。

image-20250422212550966

largebin:

在 SIZE_SZ 为 4B 的平台上，大于等于 512B的空闲 chunk，或者，在 SIZE_SZ 为 8B 的平 台上，大小大于等于 1024B的空闲 chunk，由sorted bins 管理。Large bins 一共包括 63 个 bin， 每个 bin 中的 chunk 大小不是一个固定公差的等差数列，而是分成 6 组 bin，每组 bin 是一个 固定公差的等差数列，每组的 bin 数量依次为 32、16、8、4、2、1，公差依次为 64B、512B、 4096B、32768B、262144B 等。 以 SIZE_SZ 为 4B 的平台为例，第一个 large bin 的起始 chunk 大小为 512B，共 32 个 bin， 公差为 64B，等差数列满足如下关系： Chunk_size=512 + 64 * index 第二个 large bin的起始 chunk 大小为第一组 bin 的结束 chunk 大小，满足如下关系： Chunk_size=512 + 64 * 32 + 512 * index 同理，我们可计算出每个 bin 的起始 chunk 大小和结束 chunk 大小。这些 bin 都是很有 规律的，其实small bins 也是满足类似规律，small bins 可以看着是公差为 8 的等差数列，一 共有 64 个 bin（第 0和 1bin 不存在），所以我们可以将 small bins 和 large bins存放在同一个 包含 128 个 chunk 的数组上，数组的前一部分位 small bins，后一部分为 large bins，每个 bin 的 index 为 chunk 数组的下标，于是，我们可以根据数组下标计算出该 bin 的 chunk 大小（small bins）或是 chunk 大小范围（large bins），也可以根据需要分配内存块大小计算出所需 chunk 所属 bin 的 index，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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
   Indexing

    Bins for sizes < 512 bytes contain chunks of all the same size, spaced
    8 bytes apart. Larger bins are approximately logarithmically spaced:

    64 bins of size       8
    32 bins of size      64
    16 bins of size     512
     8 bins of size    4096
     4 bins of size   32768
     2 bins of size  262144
     1 bin  of size what's left

    There is actually a little bit of slop in the numbers in bin_index
    for the sake of speed. This makes no difference elsewhere.

    The bins top out around 1MB because we expect to service large
    requests via mmap.

    Bin 0 does not exist.  Bin 1 is the unordered list; if that would be
    a valid chunk size the small bins are bumped up one.
 */

#define NBINS             128
#define NSMALLBINS         64
#define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
#define MIN_LARGE_SIZE    ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)

#define in_smallbin_range(sz)  \
  ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)

#define smallbin_index(sz) \
  ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
   + SMALLBIN_CORRECTION)

#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 It remains to be seen whether it is good to keep the widths of
// XXX the buckets the same or whether it should be scaled by a factor
// XXX of two as well.
#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))

#define bin_index(sz) \
  ((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))

宏bin_index(sz)根据所需内存大小计算出所需 bin 的 index，如果所需内存大小属于 small bins 的大小范围，调用 smallbin_index(sz)，否则调用 largebin_index(sz))。smallbin_index(sz) 的计算相当简单，如果 SIZE_SZ 为 4B，则将 sz 除以 8，如果 SIZE_SZ 为 8B，则将 sz 除以 16， 也就是除以small bins 中等差数列的公差。largebin_index(sz)的计算相对复杂一些，可以用如 下的表格直观的显示 chunk 的大小范围与 bin index 的关系。

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
/* Take a chunk off a bin list.  */
static void
unlink_chunk (mstate av, mchunkptr p)
{
  if (chunksize (p) != prev_size (next_chunk (p)))
    malloc_printerr ("corrupted size vs. prev_size");

  mchunkptr fd = p->fd;
  mchunkptr bk = p->bk;

  if (__builtin_expect (fd->bk != p || bk->fd != p, 0))
    malloc_printerr ("corrupted double-linked list");

  fd->bk = bk; //unlink操作的利用点
  bk->fd = fd;
  if (!in_smallbin_range (chunksize_nomask (p)) && p->fd_nextsize != NULL)
    {
      if (p->fd_nextsize->bk_nextsize != p
	  || p->bk_nextsize->fd_nextsize != p)
	malloc_printerr ("corrupted double-linked list (not small)");

      if (fd->fd_nextsize == NULL)
	{
	  if (p->fd_nextsize == p)
	    fd->fd_nextsize = fd->bk_nextsize = fd;
	  else
	    {
	      fd->fd_nextsize = p->fd_nextsize;
	      fd->bk_nextsize = p->bk_nextsize;
	      p->fd_nextsize->bk_nextsize = fd;
	      p->bk_nextsize->fd_nextsize = fd;
	    }
	}
      else
	{
	  p->fd_nextsize->bk_nextsize = p->bk_nextsize;
	  p->bk_nextsize->fd_nextsize = p->fd_nextsize;
	}
    }
}

Unsorted_bin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
   Unsorted chunks

   所有从内存块拆分而来的剩余部分，以及所有被释放的内存块，
   首先都会被放置在“未排序” bin 中。在 malloc 函数给它们
   一次使用的机会之前，这些块将不会被移入常规的 bin。因此，
   基本上，未排序的内存块列表充当一个队列，内存块在 free（和
   malloc_consolidate）时被放入该队列，而在 malloc 时被取出（要么
   被使用，要么放入常规的 bin）。

   对于未排序的内存块，NON_MAIN_ARENA 标志永远不会被设置，
   因此在大小比较时不需要考虑这个标志。
 */
/* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
#define unsorted_chunks(M)          (bin_at (M, 1))

Top

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
   Top

   最上方可用的内存块（即，靠近可用内存末尾的块）被特殊处理。
   它从不被包含在任何 bin 中，仅在没有其他块可用时使用，
   如果它非常大，则会被释放回系统（参见 M_TRIM_THRESHOLD）。
   因为初始的 top 指向自身的 bin，初始大小为零，这样在第一次
   malloc 请求时强制进行扩展，从而避免在 malloc 中需要任何
   特殊代码来检查它是否已经存在。但是，在从系统获取内存时
   我们仍然需要这样做，因此在初始化和第一次调用 sysmalloc 
   之间，我们让 initial_top 将 bin 视为在此期间合法但不可用的块。
   （这有点微妙，因为这依赖于在此期间前面的两个字都为零。）
*/

/* 方便的是，未排序的 bin 可以在第一次调用时作为虚拟的顶部 */
#define initial_top(M)              (unsorted_chunks (M))

Binmap

记录一个块内chunk的状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
   Binmap

   为了帮助补偿大量的bins，一个一层索引结构被用来逐个桶(bin by bin)地搜索。
   `binmap` 是一个位向量，用于记录bins是否绝对为空，以便在遍历
   时可以跳过它们。位并不会在桶变空后立即清除，而是仅在
   malloc 遍历过程中注意到它们是空时才会清除。
*/

/* 在映射字中保守地使用32位，即使在64位系统上也是如此 */
#define BINMAPSHIFT      5  // 每个映射字的位移量，表示每个字包含 2^5 = 32 位
#define BITSPERMAP       (1U << BINMAPSHIFT)  // 每个映射字包含的位数，这里是 32 位
#define BINMAPSIZE       (NBINS / BITSPERMAP) // 桶映射的大小，即总桶数除以每个映射字的位数

// 将bin索引转换为桶映射字的索引
#define idx2block(i)     ((i) >> BINMAPSHIFT)
// 根据bin的索引计算出对应的位掩码
#define idx2bit(i)       ((1U << ((i) & ((1U << BINMAPSHIFT) - 1))))
// 标记指定的桶为空，更新映射字
#define mark_bin(m, i)    ((m)->binmap[idx2block(i)] |= idx2bit(i))
// 清除指定的桶位，标记为非空
#define unmark_bin(m, i)  ((m)->binmap[idx2block(i)] &= ~(idx2bit(i)))
// 获取指定桶的映射状态（是否为空），返回对应的位
#define get_binmap(m, i)  ((m)->binmap[idx2block(i)] & idx2bit(i))

Fastbin

单向链表，头插法，即每次插入新的chunk都在头节点和头结点的下一个节点进行插入

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
/*
   快速桶（Fastbins）

   一组链表，保存最近释放的小块内存。fastbin
   不是双向链接的。单向链接更快，并且由于块从未
   从这些链表的中间位置删除，因此不需要双向链接。
   此外，与常规桶不同，它们甚至不是以先进先出
   的顺序处理（使用更快的后进先出），因为在fastbin
   通常使用的瞬态上下文中，顺序并不是非常重要。

   fastbin中的块保持其使用位被设置，因此不能与
   其他释放的块合并。malloc_consolidate 函数会释放
   所有fastbin中的块，并将它们与其他释放的块合并。
 */

typedef struct malloc_chunk *mfastbinptr;  // 定义指向 malloc_chunk 结构的指针类型
#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])  // 获取指定索引的fastbin中的块

/* 偏移量为 2，以使用其他不可索引的前两个桶 */
#define fastbin_index(sz) \
  ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)  // 计算给定大小对应的fastbin索引

/* 我们支持的最大fastbin请求大小 */
#define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)  // 最大fastbin大小，根据系统字长调整

#define NFASTBINS  (fastbin_index(request2size(MAX_FAST_SIZE)) + 1)  // fastbin的数量

这个fastbin合并操作也可以利用

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
/*
   FASTBIN_CONSOLIDATION_THRESHOLD 是在 free() 中触发
   自动合并可能周围的fastbin chunk。这个值是一个
   启发式的值，因此具体的数值不应该太过于重要。它
   被定义为默认修剪阈值的一半，作为一种折中启发式，
   仅在可能导致修剪的情况下尝试合并。然而，由于
   合并即使在不使用修剪时也能减少大块周围的碎片，
   所以这个值并不是动态可调的。
 */

#define FASTBIN_CONSOLIDATION_THRESHOLD  (65536UL)

/*
   NONCONTIGUOUS_BIT 表示 MORECORE 不返回连续的区域。
   否则，连续性在合并结果时会被利用，尽可能地
   合并连续的 MORECORE 调用结果。

   初始值来自 MORECORE_CONTIGUOUS，但如果使用 mmap
   作为 sbrk 的替代品，则会动态改变。
 */

#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)        // 设置内存块为连续

/* fastbin中处理的最大内存大小。 */
static INTERNAL_SIZE_T global_max_fast;

/*
   设置 max_fast 的值。
   如果为 0，则使用不可能的较小值。
   前提条件：main_arena中没有现有的fastbin chunk。
   由于 do_check_malloc_state() 会检查这一点，
   我们在更改 max_fast 之前调用 malloc_consolidate()。
   请注意，如果 max_fast 被减少，则其他区域将泄露
   它们的fastbin条目。
 */

#define set_max_fast(s) \
  global_max_fast = (((s) == 0)						      \
                     ? MIN_CHUNK_SIZE / 2 : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))

static inline INTERNAL_SIZE_T
get_max_fast (void)
{
  /* 告诉 GCC 优化器 global_max_fast 永远不会大于
     MAX_FAST_SIZE。这避免了在 _int_malloc 中
     的越界数组访问（在大小参数的常量传播后）。
     （这段代码不会执行，因为 malloc 保持
     global_max_fast 不变量，但优化器可能不会识别
     这一点。） */
  if (global_max_fast > MAX_FAST_SIZE)
    __builtin_unreachable ();
  return global_max_fast;
}

Internal state representation and initialization

malloc_state

malloc_state 结构体是实现内存分配器的核心数据结构之一，它包含了多个用于管理内存分配和释放状态的字段。在多线程环境中，需要通过互斥锁来确保对这些状态的安全访问。

have_fastchunks 字段虽然是近似值，但对于优化内存管理的性能十分重要，通过减少不必要的合并调用，可以提高分配效率。整体上，这种设计具有良好的性能和灵活性，适合在动态内存管理中使用。

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
/*
   have_fastchunks 表示可能存在一些fastbin chunks。
   它在将块放入任何fastbin时设置为 true，并在
   malloc_consolidate 中被清除。这个值是近似的，
   因为它可能在没有fastbin chunk时被设置，或者即使
   存在fastbin chunk时也可能被清除。由于它的唯一目的是
   减少对 malloc_consolidate 的冗余调用，因此
   它并不影响正确性。因此我们可以安全地使用
   放松的原子访问。
 */

struct malloc_state
{
  /* 序列化访问。 */
  __libc_lock_define (, mutex);
 
  /* 标志（以前在 max_fast 中）。 */
  int flags;

  /* 如果快速桶块包含最近插入的空闲块，则设置。 */
  /* 注意这是一个布尔值，但并不是所有目标都支持
     布尔类型的原子操作。 */
  int have_fastchunks;

  /* 快速桶 */
  mfastbinptr fastbinsY[NFASTBINS];

  /* top chunk的基址--不在其他桶中保存 */
  mchunkptr top;

  /* 最近一次拆分小请求的剩余部分 */
  mchunkptr last_remainder;

  /* 正常的桶，按照上述描述打包 */
  mchunkptr bins[NBINS * 2 - 2];

  /* 桶的位图 */
  unsigned int binmap[BINMAPSIZE];

  /* 链表 */
  struct malloc_state *next;

  /* 空闲区域的链表。该字段的访问由 arena.c 中的 free_list_lock 序列化。 */
  struct malloc_state *next_free;

  /* 附加到该区域的线程数量。 如果区域在空闲列表中，则为 0。
     该字段的访问由 arena.c 中的 free_list_lock 序列化。 */
  INTERNAL_SIZE_T attached_threads;

  /* 从系统中在该区域分配的内存。 */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

mutex是互斥锁，前面说到的arena为了解决多线程冲突的问题，所以如果使用了该arena，会进行上锁。
后面的flags是标志位标志着一些特征，这里不做深入只需要有个概念。fastbins是一个链表后面再做解释，top指的是top chunk，bins也是一个chunk的链表数组，next指针指向的是下一个malloc_state的位置。而后面那个*next_free指针是指向下一个未使用的malloc_state的位置。

malloc_par

malloc_par 结构体用于管理和配置内存分配器的参数。它包含了多个调节和监控内存分配行为的字段，这使得内存管理更加灵活和高效。

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
struct malloc_par
{
  /* 可调参数 */
  unsigned long trim_threshold;    // 修剪阈值
  INTERNAL_SIZE_T top_pad;         // 顶部填充
  INTERNAL_SIZE_T mmap_threshold;   // mmap 阈值
  INTERNAL_SIZE_T arena_test;       // arena 测试
  INTERNAL_SIZE_T arena_max;        // arena 最大值

  /* 内存映射支持 */
  int n_mmaps;                      // 当前 mmap 的数量
  int n_mmaps_max;                  // 当前 mmap 的最大数量
  int max_n_mmaps;                  // 最大 mmap 数量
  /* mmap_threshold 是动态的，直到用户手动设置它，
     此时我们需要禁用任何动态行为。 */
  int no_dyn_threshold;             // 禁用动态阈值

  /* 统计信息 */
  INTERNAL_SIZE_T mmapped_mem;      // 已映射内存
  INTERNAL_SIZE_T max_mmapped_mem;  // 最大映射内存

  /* 通过 MORECORE/sbrk 分配的第一个地址。 */
  char *sbrk_base;                  // sbrk 基础地址

#if USE_TCACHE
  /* 使用的最大桶数量。 */
  size_t tcache_bins;               // tcache 桶数量
  size_t tcache_max_bytes;          // tcache 最大字节数
  /* 每个桶中最大块数。 */
  size_t tcache_count;              // tcache 块数量
  /* 从未排序列表中移除的最大块数，这些块不用于
     填充缓存。 */
  size_t tcache_unsorted_limit;     // tcache 未排序限制
#endif
};

这里需要注意一下mp_结构体后面经常用到

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/* There are several instances of this struct ("arenas") in this
   malloc.  If you are adapting this malloc in a way that does NOT use
   a static or mmapped malloc_state, you MUST explicitly zero-fill it
   before using. This malloc relies on the property that malloc_state
   is initialized to all zeroes (as is true of C statics).  */

static struct malloc_state main_arena =
{
  .mutex = _LIBC_LOCK_INITIALIZER,
  .next = &main_arena,
  .attached_threads = 1
};

/* These variables are used for undumping support.  Chunked are marked
   as using mmap, but we leave them alone if they fall into this
   range.  NB: The chunk size for these chunks only includes the
   initial size field (of SIZE_SZ bytes), there is no trailing size
   field (unlike with regular mmapped chunks).  */
static mchunkptr dumped_main_arena_start; /* Inclusive.  */
static mchunkptr dumped_main_arena_end;   /* Exclusive.  */

/* True if the pointer falls into the dumped arena.  Use this after
   chunk_is_mmapped indicates a chunk is mmapped.  */
#define DUMPED_MAIN_ARENA_CHUNK(p) \
  ((p) >= dumped_main_arena_start && (p) < dumped_main_arena_end)

/* There is only one instance of the malloc parameters.  */

static struct malloc_par mp_ =
{
  .top_pad = DEFAULT_TOP_PAD,
  .n_mmaps_max = DEFAULT_MMAP_MAX,
  .mmap_threshold = DEFAULT_MMAP_THRESHOLD,
  .trim_threshold = DEFAULT_TRIM_THRESHOLD,
#define NARENAS_FROM_NCORES(n) ((n) * (sizeof (long) == 4 ? 2 : 8))
  .arena_test = NARENAS_FROM_NCORES (1)
#if USE_TCACHE
  ,
  .tcache_count = TCACHE_FILL_COUNT,
  .tcache_bins = TCACHE_MAX_BINS,
  .tcache_max_bytes = tidx2usize (TCACHE_MAX_BINS-1),
  .tcache_unsorted_limit = 0 /* No limit.  */
#endif
};

/*
   Initialize a malloc_state struct.

   This is called from ptmalloc_init () or from _int_new_arena ()
   when creating a new arena.
 */

static void
malloc_init_state (mstate av)
{
  int i;
  mbinptr bin;

  /* Establish circular links for normal bins */
  for (i = 1; i < NBINS; ++i)
    {
      bin = bin_at (av, i);
      bin->fd = bin->bk = bin;
    }

#if MORECORE_CONTIGUOUS
  if (av != &main_arena)
#endif
  set_noncontiguous (av);
  if (av == &main_arena)
    set_max_fast (DEFAULT_MXFAST);
  atomic_store_relaxed (&av->have_fastchunks, false);

  av->top = initial_top (av);
}

/*
   Other internal utilities operating on mstates
 */

static void *sysmalloc (INTERNAL_SIZE_T, mstate);
static int      systrim (size_t, mstate);
static void     malloc_consolidate (mstate);

hook函数

在用户没有自定义之前，hook函数默认为空，所以我们常通过改hook函数为one_gadget来getshell

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
/* -------------- Early definitions for debugging hooks ---------------- */

/* Define and initialize the hook variables.  These weak definitions must
   appear before any use of the variables in a function (arena.c uses one).  */
#ifndef weak_variable
/* In GNU libc we want the hook variables to be weak definitions to
   avoid a problem with Emacs.  */
# define weak_variable weak_function
#endif

/* Forward declarations.  */
static void *malloc_hook_ini (size_t sz,
                              const void *caller) __THROW;
static void *realloc_hook_ini (void *ptr, size_t sz,
                               const void *caller) __THROW;
static void *memalign_hook_ini (size_t alignment, size_t sz,
                                const void *caller) __THROW;

#if HAVE_MALLOC_INIT_HOOK
void weak_variable (*__malloc_initialize_hook) (void) = NULL;
compat_symbol (libc, __malloc_initialize_hook,
	       __malloc_initialize_hook, GLIBC_2_0);
#endif

void weak_variable (*__free_hook) (void *__ptr,
                                   const void *) = NULL;
void *weak_variable (*__malloc_hook)
  (size_t __size, const void *) = malloc_hook_ini;
void *weak_variable (*__realloc_hook)
  (void *__ptr, size_t __size, const void *)
  = realloc_hook_ini;
void *weak_variable (*__memalign_hook)
  (size_t __alignment, size_t __size, const void *)
  = memalign_hook_ini;
void weak_variable (*__after_morecore_hook) (void) = NULL;

/* This function is called from the arena shutdown hook, to free the
   thread cache (if it exists).  */
static void tcache_thread_shutdown (void);
1
void weak_variable (*__free_hook) (void *__ptr, const void *) = NULL;

语法分析

  1. void：

    • 这是返回类型，表示这个函数不返回任何值。

  2. weak_variable：

    • 这是一个类型修饰符，通常用于指示编译器这是一个弱符号（weak symbol）。弱符号允许在链接时可以被同名的强符号（strong symbol）覆盖。这在库中常用，以允许用户自定义特定的行为而不影响库的默认实现。

  3. (*__free_hook)：

    • 这里定义了一个函数指针，__free_hook 是指针的名字。(*__free_hook) 表示 __free_hook 是一个指向函数的指针。函数指针的定义需要括号将指针名称括起来，这是因为在 C 语言中，* 优先级高于函数的参数列表。

  4. (void *__ptr, const void *)：

    • 这是函数指针所指向的函数的参数列表：
      • void *__ptr：第一个参数是一个指向 void 类型的指针，通常用于指向要释放的内存块。
      • const void *：第二个参数也是一个指向 void 的常量指针，常用于传递上下文信息或其他数据，而不希望在钩子函数中修改它。

  5. = NULL;：

    • 这是对 __free_hook 的初始化，将其初始值设为 NULL，表示目前没有关联的具体实现。当这个钩子被调用时，如果没有用户提供的实现，指针为 NULL 时通常会导致调用默认的 free 函数或产生错误。

整体含义

综上所述，这行代码的作用是定义一个名为 __free_hook 的函数指针，这个指针可以指向一个特定的函数，该函数用于替代标准 free 操作。这个替代操作可以在内存管理系统中提供自定义行为，例如在释放内存时进行日志记录、统计等操作。由于它是一个弱符号，用户可以在链接时提供自己的实现来替代这个钩子，从而定制内存释放的行为。

示例用法

假设用户想要定义自己的 free 行为，他们可能会这样做：

1
2
3
4
5
6
7
8
void my_free_hook(void *ptr, const void *context) {
    // 自定义释放操作
    printf("Freeing memory at %p\n", ptr);
    free(ptr); // 调用标准的 free 函数释放内存
}

// 在某处的代码中
__free_hook = my_free_hook; // 将钩子指向用户自定义的实现

在这个例子中，用户定义了一个自定义的 my_free_hook 函数，并将 __free_hook 指向它。这样，任何调用 free 的操作，都会通过 my_free_hook 先执行，从而实现用户自定义的内存释放逻辑。

声明并定义了一堆检查

一部分是用于开发人员调试，一部分是实际用户用的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#if !MALLOC_DEBUG

# define check_chunk(A, P)
# define check_free_chunk(A, P)
# define check_inuse_chunk(A, P)
# define check_remalloced_chunk(A, P, N)
# define check_malloced_chunk(A, P, N)
# define check_malloc_state(A)

#else

# define check_chunk(A, P)              do_check_chunk (A, P)
# define check_free_chunk(A, P)         do_check_free_chunk (A, P)
# define check_inuse_chunk(A, P)        do_check_inuse_chunk (A, P)
# define check_remalloced_chunk(A, P, N) do_check_remalloced_chunk (A, P, N)
# define check_malloced_chunk(A, P, N)   do_check_malloced_chunk (A, P, N)
# define check_malloc_state(A)         do_check_malloc_state (A)
...

分析后面的代码需要时直接跳转回了看就行

sysmalloc()

当_int_malloc()函数尝试从 fast bins，last remainder chunk，small bins，large bins 和 top chunk 都失败之后，就会使用 sYSMALLOc()函数直接向系统申请内存用于分配所需的 chunk。 其实现源代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
[开始]
   |
   v
[检查 av 和请求大小]
   |
   +---是---> [尝试 mmap 分配] ---> [设置返回块] ---> [结束]
   |
   +---否---> [记录并检查当前top chunk]
                   |
                   v
           [尝试扩展当前堆]
                   |
           +---是---> [更新 av->system_mem]
           |
           +---否---> [使用 MORECORE]
                             |
                             v
                  [检查 MORECORE 返回值]
                             |
                 +---是---> [对齐和更新]
                 |
                 +---否---> [返回 ENOMEM]

值得注意：

  • _int_free (av, old_top, 1);在179行
  • _int_free (av, old_top, 1);在451行
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
/* ----------- Routines dealing with system allocation -------------- */
/*
   sysmalloc 处理从系统请求更多内存的 malloc 情况。
   进入时，假设 av->top 没有足够的空间来满足 nb 字节的请求，
   因此需要扩展或替换 av->top。
 */
static void *
sysmalloc (INTERNAL_SIZE_T nb, mstate av)
{
  mchunkptr old_top;              /* incoming value of av->top */
  INTERNAL_SIZE_T old_size;       /* its size */
  char *old_end;                  /* its end address */

  long size;                      /* arg to first MORECORE or mmap call */
  char *brk;                      /* return value from MORECORE */

  long correction;                /* arg to 2nd MORECORE call */
  char *snd_brk;                  /* 2nd return val */

  INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
  INTERNAL_SIZE_T end_misalign;   /* partial page left at end of new space */
  char *aligned_brk;              /* aligned offset into brk */

  mchunkptr p;                    /* the allocated/returned chunk */
  mchunkptr remainder;            /* remainder from allocation */
  unsigned long remainder_size;   /* its size */


  size_t pagesize = GLRO (dl_pagesize);
  bool tried_mmap = false;


    /*
         如果支持 mmap，并且请求的大小符合 mmap 阈值，    128kb
         并且系统支持 mmap，并且当前分配的 mmap 区域数量足够少，
         那么尝试直接映射此请求，而不是扩展 top。
     */


  if (av == NULL
      || ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
	  && (mp_.n_mmaps < mp_.n_mmaps_max)))
    {
      char *mm;           /* return value from mmap call*/

如果所需分配的 chunk 大小大于 mmap 分配阈值，默认为 128K，并且当前进程使用 mmap()分配的内存块小于设定的最大值，将使用mmap()系统调用直接向操作系统申请内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
    try_mmap:
      /*
         将大小向上舍入到最近的页面。
         对于通过 mmap 获取的块，开销比普通块多一个 SIZE_SZ 单位，因为没有后续块的 prev_size 字段可以使用。

         请参见下面的 front_misalign 处理，对于 glibc，除非我们有高对齐需求，否则不需要进一步的对齐处理。
*/

      if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
        size = ALIGN_UP (nb + SIZE_SZ, pagesize);
      else
        size = ALIGN_UP (nb + SIZE_SZ + MALLOC_ALIGN_MASK, pagesize);
      tried_mmap = true;

由于 nb 为所需 chunk 的大小，在_int_malloc()函数中已经将用户需要分配的大小转化为 chunk 大小，当如果这个 chunk 直接使用 mmap()分配的话，该 chunk 不存在下一个相邻的 chunk，也就没有 prev_size 的内存空间可以复用，所以还需要额外 SIZE_SZ 大小的内存。由 于 mmap()分配的内存块必须页对齐。如果使用 mmap()分配内存，需要重新计算分配的内存 大小 size。

systrim()

1
2
3
4
5
6
7
/*
   systrim 在某种程度上是 sysmalloc 的反向操作。
   它通过对 sbrk 传递负参数，将未使用的内存返还给系统（如果在 malloc 池的“高”端有未使用的内存）。
   当 top 空间超过修整阈值时，它会被 free() 自动调用。
   它也可以被公共的 malloc_trim 例程调用。如果实际释放了任何内存，则返回 1，否则返回 0。
 */

munmap()

munmap_chunk 函数用于释放通过内存映射分配的内存块

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
static void
munmap_chunk (mchunkptr p)
{
  size_t pagesize = GLRO (dl_pagesize); // 获取系统页面大小
  INTERNAL_SIZE_T size = chunksize (p); // 获取当前块的大小

  assert (chunk_is_mmapped (p)); // 确保该块是一个内存映射块

  /* 如果该块是一个在转储主区域中的伪内存映射块，则不执行任何操作。
     我们从不释放这块内存。  */
  if (DUMPED_MAIN_ARENA_CHUNK (p))
    return;

  uintptr_t mem = (uintptr_t) chunk2mem (p); // 获取块的内存地址
  uintptr_t block = (uintptr_t) p - prev_size (p); // 计算块的起始地址
  size_t total_size = prev_size (p) + size; // 计算总大小

  /* 不幸的是，我们必须手动完成编译器的工作。通常我们会分别测试
     BLOCK 和 TOTAL-SIZE 是否符合页面大小的要求。但 gcc 目前并不
     识别优化的可能性，因此我们在位测试之前将两个值合并为一个。 */
  if (__glibc_unlikely ((block | total_size) & (pagesize - 1)) != 0
      || __glibc_unlikely (!powerof2 (mem & (pagesize - 1))))
    malloc_printerr ("munmap_chunk(): 无效的指针"); // 输出错误信息

  atomic_decrement (&mp_.n_mmaps); // 减少内存映射块计数
  atomic_add (&mp_.mmapped_mem, -total_size); // 减少映射内存的总量

  /* 如果 munmap 失败，进程的虚拟内存地址空间处于不良状态。
     只是让块悬挂在那里，进程很快就会终止，因为无能为力。 */
  __munmap ((char *) block, total_size); // 尝试释放内存
}

以后闲了再看吧，直接看tcache，malloc()和free()

tcache

tcache_entry

在glibc2.29之后加入了key变量

1
2
3
4
5
6
7
8
9
10
11
12
/*------------------------ Public wrappers. --------------------------------*/

#if USE_TCACHE

/* We overlay this structure on the user-data portion of a chunk when
   the chunk is stored in the per-thread cache.  */
typedef struct tcache_entry
{
  struct tcache_entry *next;
  /* This field exists to detect double frees.  */
  struct tcache_perthread_struct *key;
} tcache_entry;

tcache_perthread_struct

1
2
3
4
5
6
7
8
9
10
11
12
/* 每个线程都有一个这样的结构体，
   它包含每个线程的缓存（因此称为“tcache_perthread_struct”）。
   保持总体大小较小是稍微重要的。
   请注意，COUNTS 和 ENTRIES 是冗余的（我们本可以每次只计算链表的长度），但这是出于性能考虑。 */
typedef struct tcache_perthread_struct
{
  uint16_t counts[TCACHE_MAX_BINS];
  tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;

static __thread bool tcache_shutting_down = false;
static __thread tcache_perthread_struct *tcache = NULL;

tcache_puts()

将chunk放入tcache中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 调用者必须确保我们知道 tc_idx 是有效的，并且有足够的空间
   存放更多的块。 */
static __always_inline void
tcache_put (mchunkptr chunk, size_t tc_idx)
{
  tcache_entry *e = (tcache_entry *) chunk2mem (chunk);

  /* 将这个块标记为“在 tcache 中”，以便在 _int_free 中测试
         可以检测到重复释放。 */
  e->key = tcache;

  e->next = tcache->entries[tc_idx];
  tcache->entries[tc_idx] = e;
  ++(tcache->counts[tc_idx]);
}

tcache_get()

从tcache中拿走chunk

1
2
3
4
5
6
7
8
9
10
/* 调用者必须确保 tc_idx 是有效的，并且有可移除的内存块。 */
static __always_inline void *
tcache_get (size_t tc_idx)
{
  tcache_entry *e = tcache->entries[tc_idx];
  tcache->entries[tc_idx] = e->next;
  --(tcache->counts[tc_idx]);
  e->key = NULL;
  return (void *) e;
}

tcache_thread_shutdown()

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
static void
tcache_thread_shutdown (void)
{
  int i;
  tcache_perthread_struct *tcache_tmp = tcache;

  if (!tcache)
    return;

  /* Disable the tcache and prevent it from being reinitialized.  */
  tcache = NULL;
  tcache_shutting_down = true;

  /* Free all of the entries and the tcache itself back to the arena
     heap for coalescing.  */
  for (i = 0; i < TCACHE_MAX_BINS; ++i)
    {
      while (tcache_tmp->entries[i])
	{
	  tcache_entry *e = tcache_tmp->entries[i];
	  tcache_tmp->entries[i] = e->next;
	  __libc_free (e);
	}
    }

  __libc_free (tcache_tmp);
}

tcache_init()

这里重要的就是_int_malloc (ar_ptr, bytes);他分配了每次程序运行起来后哪个0x290的chunk，这个chunk里面就是本线程的tcache的所有信息

1
2
3
4
5
6
7
8
9
10
11
12
pwndbg> heap
Allocated chunk | PREV_INUSE
Addr: 0x56493e4e9000
Size: 0x290 (with flag bits: 0x291)

Allocated chunk | PREV_INUSE
Addr: 0x56493e4e9290
Size: 0x20 (with flag bits: 0x21)

Top chunk | PREV_INUSE
Addr: 0x56493e4e92b0
Size: 0x20d50 (with flag bits: 0x20d51)
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
static void
tcache_init(void)
{
  mstate ar_ptr;
  void *victim = 0;
  const size_t bytes = sizeof (tcache_perthread_struct);

  if (tcache_shutting_down)
    return;

  arena_get (ar_ptr, bytes);
  victim = _int_malloc (ar_ptr, bytes);//*
  if (!victim && ar_ptr != NULL)
    {
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }

  if (ar_ptr != NULL)
    __libc_lock_unlock (ar_ptr->mutex);

  /* In a low memory situation, we may not be able to allocate memory
     - in which case, we just keep trying later.  However, we
     typically do this very early, so either there is sufficient
     memory, or there isn't enough memory to do non-trivial
     allocations anyway.  */
  if (victim)
    {
      tcache = (tcache_perthread_struct *) victim;
      memset (tcache, 0, sizeof (tcache_perthread_struct));
    }
}

__libc_malloc()

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
62
63
64
void *
__libc_malloc (size_t bytes)
{
  mstate ar_ptr;
  void *victim;

  _Static_assert (PTRDIFF_MAX <= SIZE_MAX / 2,
                  "PTRDIFF_MAX is not more than half of SIZE_MAX");
//存在hook函数则执行hook函数
  void *(*hook) (size_t, const void *)
    = atomic_forced_read (__malloc_hook);
  if (__builtin_expect (hook != NULL, 0))
    return (*hook)(bytes, RETURN_ADDRESS (0));
//若tcache启用，首先使用tcache来分配chunk
#if USE_TCACHE
  /* int_free also calls request2size, be careful to not pad twice.  */
  size_t tbytes;
  if (!checked_request2size (bytes, &tbytes))
    {//获取 nb+2*SIZE_SZ (0x10在64位中) 的大小，并判断
      __set_errno (ENOMEM);
      return NULL;
    }
  size_t tc_idx = csize2tidx (tbytes);

  MAYBE_INIT_TCACHE ();

  DIAG_PUSH_NEEDS_COMMENT;
  if (tc_idx < mp_.tcache_bins
      && tcache
      && tcache->counts[tc_idx] > 0)
    {
      return tcache_get (tc_idx);
    }
  DIAG_POP_NEEDS_COMMENT;
#endif
//tcache不满足的话，再用_int_malloc()，下面这些和单多线程有关
  if (SINGLE_THREAD_P)
    {
      victim = _int_malloc (&main_arena, bytes);
      assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
	      &main_arena == arena_for_chunk (mem2chunk (victim)));
      return victim;
    }

  arena_get (ar_ptr, bytes);

  victim = _int_malloc (ar_ptr, bytes);
  /* Retry with another arena only if we were able to find a usable arena
     before.  */
  if (!victim && ar_ptr != NULL)
    {
      LIBC_PROBE (memory_malloc_retry, 1, bytes);
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }

  if (ar_ptr != NULL)
    __libc_lock_unlock (ar_ptr->mutex);

  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          ar_ptr == arena_for_chunk (mem2chunk (victim)));
  return victim;
}
libc_hidden_def (__libc_malloc)

__libc_free()

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
void
__libc_free (void *mem)
{
  mstate ar_ptr;
  mchunkptr p;                          /* chunk corresponding to mem */
//有hook函数调用hook函数
  void (*hook) (void *, const void *)
    = atomic_forced_read (__free_hook);
  if (__builtin_expect (hook != NULL, 0))
    {
      (*hook)(mem, RETURN_ADDRESS (0));
      return;
    }

  if (mem == 0)                              /* free(0) has no effect */
    return;

  p = mem2chunk (mem);

  if (chunk_is_mmapped (p))                       /* release mmapped memory. */
    {
      /* 查看动态的 brk/mmap 阈值是否需要调整。
		转储的虚假 mmap 块不会影响该阈值。 */
      if (!mp_.no_dyn_threshold
          && chunksize_nomask (p) > mp_.mmap_threshold
          && chunksize_nomask (p) <= DEFAULT_MMAP_THRESHOLD_MAX
	  && !DUMPED_MAIN_ARENA_CHUNK (p))
        {
          mp_.mmap_threshold = chunksize (p);
          mp_.trim_threshold = 2 * mp_.mmap_threshold;
          LIBC_PROBE (memory_mallopt_free_dyn_thresholds, 2,
                      mp_.mmap_threshold, mp_.trim_threshold);
        }
      munmap_chunk (p);//这个就是前面那个munmap()释放通过内存映射(mmap)分配的内存块
      return;
    }

  MAYBE_INIT_TCACHE ();

  ar_ptr = arena_for_chunk (p);
  _int_free (ar_ptr, p, 0);//调用_int_free()
}
libc_hidden_def (__libc_free)

malloc()

初始化声明变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static void *
_int_malloc (mstate av, size_t bytes)
{
  INTERNAL_SIZE_T nb;               /* normalized request size */
  unsigned int idx;                 /* associated bin index */
  mbinptr bin;                      /* associated bin */

  mchunkptr victim;                 /* inspected/selected chunk */
  INTERNAL_SIZE_T size;             /* its size */
  int victim_index;                 /* its bin index */

  mchunkptr remainder;              /* remainder from a split */
  unsigned long remainder_size;     /* its size */

  unsigned int block;               /* bit map traverser */
  unsigned int bit;                 /* bit map traverser */
  unsigned int map;                 /* current word of binmap */

  mchunkptr fwd;                    /* misc temp for linking */
  mchunkptr bck;                    /* misc temp for linking */

#if USE_TCACHE
  size_t tcache_unsorted_count;	    /* count of unsorted chunks processed */
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
     将请求大小转换为内部形式，通过添加 SIZE_SZ 字节的
     额外开销，并可能需要更多以获得必要的对齐，或
     至少获得 MINSIZE，即最小可分配大小。
     同时，checked_request2size 对于请求大小过大
     的情况返回 false，这样在填充和对齐后会
     发生零值回绕。
   */

if (!checked_request2size (bytes, &nb))
{
  __set_errno (ENOMEM);
  return NULL;
}

/* 没有可用的内存区域。回退到 sysmalloc 从 mmap 获取一个 chunk。 */
if (__glibc_unlikely (av == NULL))
{
  void *p = sysmalloc (nb, av);
  if (p != NULL)
    alloc_perturb (p, bytes);
  return p;
}				\

fastbin

在启用tcache的情况下，从fastbin中取出chunk:

  • 首先会在fastbin中找到所需的chunk
  • 然后在tcachebin未满或这为空的情况下，会将它放入tcachebin中
  • 即在tcache启用后优先从tcachebin中取出chunk给用户，所以这里就显示出了tcachebin的优先级比fastbin更高

注意：

  • 因为tcache的单向链表用的头插法，头插法的特点就是如下：
    • 插入input: 10 20 30
    • 遍历output：30 20 10
  • 所以这就导致了在同样size时，当tcachehbin中的chunk被取出后，若fastbin中有多个chunk，它们会逆序放入到tcachebin中

攻击手法：fastbin_reverse_into_tcache

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
62
63
64
65
66
67
68
69
70
71
72
73
/*
   如果大小符合快速分配（fastbin）的条件，首先检查相应的空闲bin。
   这段代码即使在 av 尚未初始化的情况下也可以安全执行，因此
   可以在不检查的情况下尝试，这样可以节省在快速路径上的时间。
*/

#define REMOVE_FB(fb, victim, pp)			\
  do							\
    {							\
      victim = pp;					\
      if (victim == NULL)				\
	break;						\
    }							\
  while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim)) \
	 != victim);
// 检查请求的内存大小是否小于等于最大快速分配大小
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
{
    // 计算请求大小对应的fastbin索引
    idx = fastbin_index (nb);
    mfastbinptr *fb = &fastbin (av, idx); // 获取相应的fastbin指针
    mchunkptr pp; // 定义一个指针，用于操作快速分配器中的块
    victim = *fb; // 从fastbin中获取一个空闲chunk
    // 检查是否有可用的内存块
    if (victim != NULL)
    {
        // 在单线程环境下，直接更新快速分配器指针
        if (SINGLE_THREAD_P)
            *fb = victim->fd; // 将 fb 指向下一个空闲块
        else
            REMOVE_FB (fb, pp, victim); // 在多线程环境下安全地移除该块

        // 确保 victim 不为 NULL 以继续处理
        if (__glibc_likely (victim != NULL))
        {
            // 获取 victim 的大小对应的索引
            size_t victim_idx = fastbin_index (chunksize (victim));
            // 检查 victim 的索引是否与请求的索引一致
            if (__builtin_expect (victim_idx != idx, 0))
                // 如果不一致，报告内存损坏错误
                malloc_printerr ("malloc(): memory corruption (fast)");
            // 执行对 victim 块的进一步检查，确保其可以安全使用
            check_remalloced_chunk (av, victim, nb);
#if USE_TCACHE
	      /* While we're here, if we see other chunks of the same size,
		 stash them in the tcache.  */
	      size_t tc_idx = csize2tidx (nb);
	      if (tcache && tc_idx < mp_.tcache_bins)
		{
		  mchunkptr tc_victim;

		  /* While bin not empty and tcache not full, copy chunks.  */
		  while (tcache->counts[tc_idx] < mp_.tcache_count
			 && (tc_victim = *fb) != NULL)
		    {
		      if (SINGLE_THREAD_P)//单线程
			*fb = tc_victim->fd;
		      else
			{//多线程操作
			  REMOVE_FB (fb, pp, tc_victim);
			  if (__glibc_unlikely (tc_victim == NULL))
			    break;
			}
		      tcache_put (tc_victim, tc_idx);//将victim放入tcache中
		    }
		}
#endif
	      void *p = chunk2mem (victim);
	      alloc_perturb (p, bytes);
	      return p;
	    }
	}
        }

smallbin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
#include<stdlib.h>
int main(){
    unsigned long *chunk_list[0x10] = {0};
    for(int i=0;i<10;i++)
        chunk_list[i] = malloc(0x100);
    malloc(0x10);
    for(int i=0;i<6;i++)
        free(chunk_list[i]);
	free(chunk_list[9]);
    free(chunk_list[7]);//这个进入了smallbin
    malloc(0x110);
    printf("chunk_list[7]进入了smallbin");
    for(int i=0;i<7;i++){
        malloc(0x100);
    }
    //观察源代码的执行
    malloc(0x100);//这个就是从smallbin中取出来放进tcache的
    return 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
  如果请求的内存较小，检查常规的内存池（small bins）。
  由于这些“smallbin”每个只包含一个大小，因此不需要在内存池内搜索。
  （对于较大的请求，我们需要等待unsortedbin被处理，以找到最佳匹配。
   但对于smallbin chunk请求，适配是准确的，因此我们现在可以检查，这样更快。）
*/

if (in_smallbin_range(nb))  // 检查请求的大小是否在smallbin范围内
{
    idx = smallbin_index(nb);  // 计算请求大小对应的smallbin索引
    bin = bin_at(av, idx);  // 获取对应的smallbin指针

    if ((victim = last(bin)) != bin)  // 获取smllbin中的最后一个块，如果不为空
    {
        bck = victim->bk;  // 记录被分配chunk的后继chunk
        if (__glibc_unlikely(bck->fd != victim))  // 检查双向链表的完整性
            malloc_printerr("malloc(): smallbin double linked list corrupted");

        set_inuse_bit_at_offset(victim, nb);  // 设置块状态为已使用
        bin->bk = bck;  // 更新小块指针
        bck->fd = bin;  // 维护双向链表的完整性

        if (av != &main_arena)  // 检查是否在主分配区
            set_non_main_arena(victim);
        
        check_malloced_chunk(av, victim, nb);  // 检查分配的块

#if USE_TCACHE
        /* 在这里，如果我们看到相同大小的其他块，
           将它们存入线程缓存（tcache）。 */
        size_t tc_idx = csize2tidx(nb);  // 计算tcache索引
        if (tcache && tc_idx < mp_.tcache_bins)  // 检查tcache是否有效
        {
            mchunkptr tc_victim;

            /* 当小块不为空且线程缓存未满时，复制块。 */
            while (tcache->counts[tc_idx] < mp_.tcache_count
                && (tc_victim = last(bin)) != bin)  // 获取小块列表中的最后一个块
            {
                if (tc_victim != 0)  // 检查块是否有效
                {
                    bck = tc_victim->bk;  // 获取块的后继块
                    set_inuse_bit_at_offset(tc_victim, nb);  // 设置状态为已使用
                    if (av != &main_arena)
                        set_non_main_arena(tc_victim);  // 更新非主分配区标志

                    bin->bk = bck;  // 更新小块指针
                    bck->fd = bin;  // 维护双向链表的完整性

                    tcache_put(tc_victim, tc_idx);  // 将victim放入tcache中
                }
            }
        }
#endif
        void *p = chunk2mem(victim);  
        alloc_perturb(p, bytes);  
        return p;  
    }
}

largebin

首先处理unsortedbin中的空闲chunk

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
/*
  如果这是一个大请求，在继续之前合并快速块（fastbins）。
  虽然在查看是否有可用空间之前处理所有快速块看起来有些过度，
  但这样可以避免通常与快速块相关的碎片问题。
  此外，实际上，程序倾向于连续产生小请求或大请求，
  而不常出现混合请求，因此在大多数程序中，
  不会频繁调用合并操作。而在那些频繁调用合并操作的程序
  中，往往会导致内存碎片。
*/

else
{
    idx = largebin_index(nb);  // 计算请求大小对应的大块索引
    if (atomic_load_relaxed(&av->have_fastchunks))  // 检查fastbin中是否存在空闲chunk
        malloc_consolidate(av);  // 合并fastbin的空闲chunk
}
/*
  处理最近释放或剩余的内存块，仅在块完全匹配时才取用，
  或者如果这是一个小请求，则取用从最近的非完全匹配中剩余的块。
  将其他遍历到的块放入合适的池中。
  请注意，这个步骤是在任何例程中唯一将块放入池中的地方。

  这里的外部循环是必要的，因为我们可能直到 malloc 接近结束时
  才意识到我们应该合并，因此必须执行合并并重试。
  这最多发生一次，并且只在我们需要扩展内存以满足“小”请求时。
*/

#if USE_TCACHE
  INTERNAL_SIZE_T tcache_nb = 0;  // 用于缓存的块大小
  size_t tc_idx = csize2tidx(nb);  // 将请求大小转换为tcache索引
  if (tcache && tc_idx < mp_.tcache_bins)  // 检查缓存是否启用并且索引有效
    tcache_nb = nb;  // 设置缓存块大小
  int return_cached = 0;  // 标记返回缓存块的状态

  tcache_unsorted_count = 0;
#endif

项目 说明
unsorted_chunks(av) 获取 unsorted bin 的链表头（伪 chunk），位于 main_arena 固定偏移处
循环条件 遍历 unsorted bin 中的真实 chunk，逆序处理直到链表头
链表头特性 fd 指向第一个真实 chunk，bk 指向最后一个真实 chunk

首先要搞明白一个宏unsorted_chunks(av)

1
2
3
4
5
unsorted_chunks(av) = bin_at(av, 1)
                    = (char*)&av->bins[(1-1)*2] - offsetof(malloc_chunk, fd)
                    = (char*)&av->bins[0] - 0x10  // 因 malloc_chunk.fd 偏移为 0x10
                    = main_arena + 0x58 - 0x10    
                    = main_arena + 0x48           //这个是main_arena+88的head

下面的源代码实现从 last remainder chunk，large bins 和top chunk 中分配所需的 chunk， 这里包含了多个多层循环，在这些循环中，主要工作是分配前两步都未分配成功的 small bin chunk，large bin chunk 和 large chunk。最外层的循环用于重新尝试分配 small bin chunk，因 为如果在前一步分配small bin chunk 不成功，并没有调用 malloc_consolidate()函数合并 fast bins 中的 chunk，将空闲 chunk 加入 unsorted bin 中，如果第一尝试从 last remainder chunk， top chunk 中分配 small bin chunk 都失败以后，如果 fast bins 中存在空闲 chunk，会调用 malloc_consolidate()函数，那么在 usorted bin 中就可能存在合适的 small bin chunk 供分配， 所以需要再次尝试。

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
for (;; )//遍历unsortedbin
  {
    int iters = 0;//记录循环的次数
    while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
      {//逆序
        bck = victim->bk; //bck需要注意
        size = chunksize (victim);
        mchunkptr next = chunk_at_offset (victim, size);

        if (__glibc_unlikely (size <= 2 * SIZE_SZ)
            || __glibc_unlikely (size > av->system_mem))
          malloc_printerr ("malloc(): invalid size (unsorted)");
        if (__glibc_unlikely (chunksize_nomask (next) < 2 * SIZE_SZ)
            || __glibc_unlikely (chunksize_nomask (next) > av->system_mem))
          malloc_printerr ("malloc(): invalid next size (unsorted)");
        if (__glibc_unlikely ((prev_size (next) & ~(SIZE_BITS)) != size))
          malloc_printerr ("malloc(): mismatching next->prev_size (unsorted)");
        if (__glibc_unlikely (bck->fd != victim)
            || __glibc_unlikely (victim->fd != unsorted_chunks (av)))
          malloc_printerr ("malloc(): unsorted double linked list corrupted");
        if (__glibc_unlikely (prev_inuse (next)))
          malloc_printerr ("malloc(): invalid next->prev_inuse (unsorted)");
        /* 
             如果是小内存请求，且unsorted bin中仅存最后一个剩余块（last_remainder），
             则尝试使用它。这有助于提升连续小内存请求的局部性。
             这是最佳适配策略的唯一例外，且仅适用于小内存块没有精确匹配的情况。
          */
         if (in_smallbin_range (nb) &&//判断是否需要分配一个small bin chunk
            bck == unsorted_chunks (av) &&//unsortedbin中只有一个chunk
            victim == av->last_remainder &&//并且这个chunk为last_remainder chunk
            (unsigned long) (size) > (unsigned long) (nb + MINSIZE))//且大于所需chunk的size加上MINSIZE
          {
            /* split and reattach remainder */
            remainder_size = size - nb;//计算切分后剩下的chunk大小
            remainder = chunk_at_offset (victim, nb);
            unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
            av->last_remainder = remainder;
            remainder->bk = remainder->fd = unsorted_chunks (av);//链入unsortedbin中
            if (!in_smallbin_range (remainder_size))
              {//如果属于largebin chunk将该chunk的fd_nextsize和bk_nextsize设置为NULL
                remainder->fd_nextsize = NULL;
                remainder->bk_nextsize = NULL;
              }
	  //设置分配出的chunk和last_remainder chunk的相关信息
            set_head (victim, nb | PREV_INUSE |
                      (av != &main_arena ? NON_MAIN_ARENA : 0));
            set_head (remainder, remainder_size | PREV_INUSE);
            set_foot (remainder, remainder_size);

            check_malloced_chunk (av, victim, nb);
            void *p = chunk2mem (victim);
            alloc_perturb (p, bytes);
            return p;
          }//返回应用层，退出

原unsortedbin_attack（向任意地址即bck的fd写入main_arena+88），因加了这个检查后就用不了了

若前面仍未完成分配，则将usnortedbin中最后一个chunk拿出来若与所需大小一致，将当前chunk返回，否则分类并归位。

1
2
3
4
5
/* remove from unsorted list */
if (__glibc_unlikely (bck->fd != victim))
  malloc_printerr ("malloc(): corrupted unsorted chunks 3");
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);

启用tcache，将chunk先放入tcache中，再返回给给用户，当tcache满的时候才直接返回给用户

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
          /* Take now instead of binning if exact fit */

          if (size == nb)
            {
              set_inuse_bit_at_offset (victim, size);
              if (av != &main_arena)
		set_non_main_arena (victim);
#if USE_TCACHE
	      /* Fill cache first, return to user only if cache fills.
		 We may return one of these chunks later.  */
	      if (tcache_nb
		  && tcache->counts[tc_idx] < mp_.tcache_count)
		{
		  tcache_put (victim, tc_idx);
		  return_cached = 1;
		  continue;
		}
	      else
		{
#endif
              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
#if USE_TCACHE
		}
#endif
            }

开始归为前面遍历到但不符合需求的chunk。

如果当前 chunk 属于small bins，获得当前 chunk 所属small bin 的 index，并将该 small bin 的链表表头赋值给 bck，第一个 chunk 赋值给 fwd，也就是当前的 chunk 会插入到 bck 和 fwd 之间，作为small bin 链表的第一个 chunk。

1
2
3
4
5
6
7
8
/* place chunk in bin */

if (in_smallbin_range (size))
  {
    victim_index = smallbin_index (size);
    bck = bin_at (av, victim_index);
    fwd = bck->fd;
  }

如果当前 chunk 属于 large bins，获得当前 chunk 所属 large bin 的 index，并将该 large bin 的链表表头赋值给 bck，第一个 chunk 赋值给 fwd，也就是当前的 chunk 会插入到 bck 和 fwd 之间，作为 large bin 链表的第一个 chunk。

1
2
3
4
5
else
  {
    victim_index = largebin_index (size);
    bck = bin_at (av, victim_index);
    fwd = bck->fd

如果fwd 不等于 bck，意味着large bin 中有空闲chunk 存在，由于large bin 中的空闲chunk 是按照大小顺序排序的，需要将当前从 unsorted bin 中取出的 chunk 插入到 large bin 中合适 的位置。将当前 chunk 的 size 的 inuse 标志 bit 置位，相当于加 1，便于加快 chunk 大小的比 较，找到合适的地方插入当前 chunk。这里还做了一次检查，断言在 large bin 双向循环链表 中的最后一个 chunk的 size 字段中的非主分配区的标志 bit没有置位，因为所有在 large bin 中的 chunk 都处于空闲状态，该标志位一定是清零的。

根据内存结构理解largebin的fd和bk

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
largebins
0x400-0x430: 0x1f2ae850 —▸ 0x1f2ae420 —▸ 0x1f2ae000 —▸ 0x7f5cf0f79f68 (main_arena+1096) ◂— 0x1f2ae850
pwndbg> x/10gx 0x1f2ae850 #最大 
0x1f2ae850:     0x0000000000000000      0x0000000000000421
0x1f2ae860:     0x000000001f2ae420      0x00007f5cf0f79f68#bk->main_arena+1096
0x1f2ae870:     0x000000001f2ae420      0x000000001f2ae000
0x1f2ae880:     0x0000000000000000      0x0000000000000000
0x1f2ae890:     0x0000000000000000      0x0000000000000000
pwndbg> x/10gx 0x1f2ae420 # fd_nextsize->小的 bk_nextsize->大的
0x1f2ae420:     0x0000000000000000      0x0000000000000411
0x1f2ae430:     0x000000001f2ae000      0x000000001f2ae850
0x1f2ae440:     0x000000001f2ae000      0x000000001f2ae850
0x1f2ae450:     0x0000000000000000      0x0000000000000000
0x1f2ae460:     0x0000000000000000      0x0000000000000000
pwndbg> x/10gx 0x1f2ae000 # 最小
0x1f2ae000:     0x0000000000000000      0x0000000000000401
0x1f2ae010:     0x00007f5cf0f79f68      0x000000001f2ae420#fd->main_arena+1096
0x1f2ae020:     0x000000001f2ae850      0x000000001f2ae420
0x1f2ae030:     0x0000000000000000      0x0000000000000000
0x1f2ae040:     0x0000000000000000      0x0000000000000000
pwndbg> x/10gx 0x7f5cf0f79f68 #头节点  fd->最大  bk->最小
0x7f5cf0f79f68 <main_arena+1096>:       0x00007f5cf0f79f58      0x00007f5cf0f79f58
0x7f5cf0f79f78 <main_arena+1112>:       0x000000001f2ae850<-fwd 0x000000001f2ae000<-bck
0x7f5cf0f79f88 <main_arena+1128>:       0x00007f5cf0f79f78      0x00007f5cf0f79f78
0x7f5cf0f79f98 <main_arena+1144>:       0x00007f5cf0f79f88      0x00007f5cf0f79f88
0x7f5cf0f79fa8 <main_arena+1160>:       0x00007f5cf0f79f98      0x00007f5cf0f79f98
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
largebins
0x400-0x430: 0x1fa8f000 —▸ 0x1fa8f840 —▸ 0x1fa8f420 —▸ 0x7f9a8e388f68 (main_arena+1096) ◂— 0x1fa8f000
pwndbg> x/10gx 0x1fa8f000
0x1fa8f000:     0x0000000000000000      0x0000000000000401
0x1fa8f010:     0x000000001fa8f840      0x00007f9a8e388f68
0x1fa8f020:     0x000000001fa8f000      0x000000001fa8f000
0x1fa8f030:     0x0000000000000000      0x0000000000000000
0x1fa8f040:     0x0000000000000000      0x0000000000000000
pwndbg> x/10gx 0x1fa8f840
0x1fa8f840:     0x0000000000000000      0x0000000000000401
0x1fa8f850:     0x000000001fa8f420      0x000000001fa8f000
0x1fa8f860:     0x0000000000000000      0x0000000000000000
0x1fa8f870:     0x0000000000000000      0x0000000000000000
0x1fa8f880:     0x0000000000000000      0x0000000000000000
pwndbg> x/10gx 0x1fa8f420
0x1fa8f420:     0x0000000000000000      0x0000000000000401
0x1fa8f430:     0x00007f9a8e388f68      0x000000001fa8f840
0x1fa8f440:     0x0000000000000000      0x0000000000000000
0x1fa8f450:     0x0000000000000000      0x0000000000000000
0x1fa8f460:     0x0000000000000000      0x0000000000000000
pwndbg> x/10gx 0x7f9a8e388f68
0x7f9a8e388f68 <main_arena+1096>:       0x00007f9a8e388f58      0x00007f9a8e388f58
0x7f9a8e388f78 <main_arena+1112>:       0x000000001fa8f000      0x000000001fa8f420
0x7f9a8e388f88 <main_arena+1128>:       0x00007f9a8e388f78      0x00007f9a8e388f78
0x7f9a8e388f98 <main_arena+1144>:       0x00007f9a8e388f88      0x00007f9a8e388f88
0x7f9a8e388fa8 <main_arena+1160>:       0x00007f9a8e388f98      0x00007f9a8e388f98

largebin_attack

从上面的内存结构可以看出fwd->最小的；bck->最大的

1
2
3
4
5
6
7
/* maintain large bins in sorted order */
if (fwd != bck)
  {//large bin 中有空闲chunk 存在
    /* Or with inuse bit to speed comparisons */
    size |= PREV_INUSE;
    /* if smaller than smallest, bypass loop below */
    assert (chunk_main_arena (bck->bk));

如果当前chunk比large bin的最后一个chunk的大小还小，那么当前chunk就插入到large bin 的链表的最后，作为最后一个 chunk。可以看出 large bin 中的 chunk 是按照从大到小的 顺序排序的，同时一个 chunk 存在于两个双向循环链表中，一个链表包含了 large bin 中所有 的chunk，另一个链表为chunk size 链表，该链表从每个相同大小的chunk 的取出第一个chunk 按照大小顺序链接在一起，便于一次跨域多个相同大小的 chunk 遍历下一个不同大小的 chunk，这样可以加快在 large bin 链表中的遍历速度。

1
2
3
4
5
6
7
8
9
          if ((unsigned long) (size)
< (unsigned long) chunksize_nomask (bck->bk))//bck->bk是当前largebin中最小的chunk
            {//直接链入largebin
              fwd = bck;
              bck = bck->bk;

              victim->fd_nextsize = fwd->fd;
              victim->bk_nextsize = fwd->fd->bk_nextsize;
              fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;

正向遍历 chunk size 链表，直到找到第一个 chunk 大小小于等于当前 chunk 大小的 chunk 退出循环。

1
2
3
4
5
6
7
8
  else
               {//即等于或大于fwd的size
                 assert (chunk_main_arena (fwd));
                 while ((unsigned long) size < chunksize_nomask (fwd))
                   {//正向遍历largebin
                     fwd = fwd->fd_nextsize;
assert (chunk_main_arena (fwd));
                   }

如果从 large bin 链表中找到了与当前 chunk 大小相同的 chunk，则同一大小的 chunk 已 经存在，那么 chunk size 链表中一定包含了fwd 所指向的 chunk，为了不修改 chunk size 链 表，当前 chunk 只能插入 fwd 之后。

1
2
3
4
                 if ((unsigned long) size
== (unsigned long) chunksize_nomask (fwd))//直到等于fwd的情况成立
                   /* Always insert in the second position.  */
                   fwd = fwd->fd;//直接链在fwd后面

如果 chunk size 链表中还没有包含当前 chunk 大小的 chunk，也就是说当前 chunk 的大小大于 fwd 的大小，则将当前 chunk 作为该 chunk size 的代表加入 chunk size 链表，chunk size 链表也是按照由大到小的顺序排序。

1
2
3
4
5
6
7
8
9
else
                 {
                   victim->fd_nextsize = fwd;
                   victim->bk_nextsize = fwd->bk_nextsize;
                   if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))
                     malloc_printerr ("malloc(): largebin double linked list corrupted 									  (nextsize)");
                   fwd->bk_nextsize = victim;
                   victim->bk_nextsize->fd_nextsize = victim;
                 }

如果 large bin 链表中没有 chunk，直接将当前 chunk加入 chunk size 链表。

1
2
3
4
5
6
7
        bck = fwd->bk;
        if (bck->fd != fwd)
          malloc_printerr ("malloc(): largebin double linked list corrupted (bk)");
      }
  }
else
  victim->fd_nextsize = victim->bk_nextsize = victim;
1
2
3
4
5
6
7
  }

mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

上面的代码将当前 chunk 插入到 large bin 的空闲 chunk 链表中，并将 large bin 所对应 binmap 的相应 bit 置位。

1
2
3
4
5
6
7
8
9
10
11
#if USE_TCACHE
      /* If we've processed as many chunks as we're allowed while
	 filling the cache, return one of the cached ones.  */
      ++tcache_unsorted_count;
      if (return_cached
	  && mp_.tcache_unsorted_limit > 0
	  && tcache_unsorted_count > mp_.tcache_unsorted_limit)
	{
	  return tcache_get (tc_idx);
	}
#endif
1
2
3
4
5
6
7
8
9
10
11
12
#define MAX_ITERS       10000
          if (++iters >= MAX_ITERS)
            break;
        }

#if USE_TCACHE
      /* If all the small chunks we found ended up cached, return one now.  */
      if (return_cached)
	{
	  return tcache_get (tc_idx);
	}
#endif

最多遍历unsortedbin 10000次，后面的一部分（在use_top）之前在pwn中可能很少用到，简略分析

当将 unsorted bin 中的空闲 chunk 加入到相应的 small bins 和 large bins 后，将使用最佳匹配法分配 large bin chunk。源代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
   If a large request, scan through the chunks of current bin in
   sorted order to find smallest that fits.  Use the skip list for this.
 */

if (!in_smallbin_range (nb))
  {
    bin = bin_at (av, idx);

    /* skip scan if empty or largest chunk is too small */
    if ((victim = first (bin)) != bin
 && (unsigned long) chunksize_nomask (victim)
   >= (unsigned long) (nb))

如果所需分配的 chunk为 large bin chunk，查询对应的 large bin 链表，如果 large bin 链 表为空，或者链表中最大的 chunk 也不能满足要求，则不能从 large bin 中分配。否则，遍历 98 large bin 链表，找到合适的 chunk。

1
2
3
4
5
{
  victim = victim->bk_nextsize;
  while (((unsigned long) (size = chunksize (victim)) <
          (unsigned long) (nb)))
    victim = victim->bk_nextsize;

反向遍历chunk size链表(由小到大)，直到找到第一个大于等于所需chunk大小的chunk退出循环。

1
2
3
4
5
6
          /* Avoid removing the first entry for a size so that the skip
             list does not have to be rerouted.  */
          if (victim != last (bin)
&& chunksize_nomask (victim)
  == chunksize_nomask (victim->fd))
            victim = victim->fd;

如果从 large bin 链表中选取的 chunk victim 不是链表中的最后一个 chunk，并且与 victim 大小相同的chunk 不止一个，那么意味着victim 为chunk size 链表中的节点，为了不调整chunk size 链表，需要避免将 chunk size 链表中的节点取出，所以取 victim->fd 节点对应的 chunk 作为候选 chunk。由于 large bin 链表中的 chunk 也是按大小排序，同一大小的 chunk 有多个 时，这些 chunk 必定排在一起，所以 victim->fd 节点对应的 chunk 的大小必定与 victim 的大 小一样。

1
2
remainder_size = size - nb;
unlink_chunk (av, victim);

计算将victim切分后剩余大小，并调用 unlink()宏函数将 victim从 large bin 链表中取出。

1
2
3
4
5
6
7
        /* Exhaust */
        if (remainder_size < MINSIZE)
          {
            set_inuse_bit_at_offset (victim, size);
            if (av != &main_arena)
set_non_main_arena (victim);
          }

如果将 victim 切分后剩余大小小于 MINSIZE，则将整个 victim 分配给应用层，这种情况 下，实际分配的 chunk 比所需的 chunk 要大一些。以 64 位系统为例，remainder_size 的可能 大小为 0 和 16，如果为 0，表示victim 的大小刚好等于所需 chunk 的大小，设置 victim 的 inuse 标志，inuse 标志位于下一个相邻的 chunk 的 size 字段中。如果 remainder_size 为 16，则这 16 字节就浪费掉了。如果当前分配区不是主分配区，将 victim 的 size 字段中的非主分配区 标志置位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
          /* Split */
          else
            {
              remainder = chunk_at_offset (victim, nb);
              /* We cannot assume the unsorted list is empty and therefore
                 have to perform a complete insert here.  */
              bck = unsorted_chunks (av);
              fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
  malloc_printerr ("malloc(): corrupted unsorted chunks");
              remainder->bk = bck;
              remainder->fd = fwd;
              bck->fd = remainder;
              fwd->bk = remainder;
              if (!in_smallbin_range (remainder_size))
                {
                  remainder->fd_nextsize = NULL;
                  remainder->bk_nextsize = NULL;
                }

从victim 中切分出所需的chunk，剩余部分作为一个新的 chunk 加入到 unsorted bin 中。 如果剩余部分 chunk 属于large bins，将剩余部分 chunk 的 chunk size 链表指针设置为NULL， 因为 unsorted bin 中的 chunk 是不排序的，这两个指针无用，必须清零。

1
2
3
4
5
6
7
8
9
10
11
          set_head (victim, nb | PREV_INUSE |
                    (av != &main_arena ? NON_MAIN_ARENA : 0));
          set_head (remainder, remainder_size | PREV_INUSE);
          set_foot (remainder, remainder_size);
        }
      check_malloced_chunk (av, victim, nb);
      void *p = chunk2mem (victim);
      alloc_perturb (p, bytes);
      return p;
    }
}

从 large bin中使用最佳匹配法找到了合适的 chunk，设置victim和remainder的状态，由于 remainder 为空闲 chunk，所以需要设置该 chunk 的 foot；调用 chunk2mem()获得 chunk 中可 用的内存指针，返回给应用层，退出。

如果通过上面的方式从最合适的 small bin 或 large bin 中都没有分配到需要的chunk，则 查看比当前 bin 的 index 大的 small bin 或 large bin 是否有空闲 chunk 可利用来分配所需的 chunk。源代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
         通过扫描bins来搜索chunk，从下一个较大的bin开始。
         这个搜索严格遵循最佳适配原则；即选择适合的最小块（在平局的情况下选择约最少最近使用的块）。

         binmap避免了需要检查大多数块是否为空的情况。
         在热身阶段（即还没有返回任何块的情况下）跳过所有桶的特殊情况比看上去的要快得多。
       */

      ++idx;  // 增加索引
      bin = bin_at(av, idx);  // 获取当前索引对应的桶
      block = idx2block(idx);  // 将索引转换为块
      map = av->binmap[block];  // 获取对应块的位图
      bit = idx2bit(idx);  // 将索引转换为位图中的位

获取下一个相邻bin 的空闲chunk 链表，并获取该bin 对于binmap 中的bit 位的值。Binmap 中的标识了相应的 bin 中是否有空闲 chunk 存在。Binmap 按 block 管理，每个 block 为一个 int，共 32 个 bit，可以表示 32 个 bin 中是否有空闲 chunk 存在。使用 binmap 可以加快查找 bin 是否包含空闲 chunk。这里只查询比所需 chunk 大的 bin 中是否有空闲 chunk 可用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (;; )
  {
    /* Skip rest of block if there are no more set bits in this block.  */
    if (bit > map || bit == 0)
      {
        do
          {
            if (++block >= BINMAPSIZE) /* out of bins */
              goto use_top;
          }
        while ((map = av->binmap[block]) == 0);

        bin = bin_at (av, (block << BINMAPSHIFT));
        bit = 1;
      }

Idx2bit()宏将 idx 指定的位设置为 1，其它位清零，map 表示一个 block（unsigned int） 值，如果 bit 大于 map，意味着 map 为 0，该 block 所对应的所有 bins 中都没有空闲 chunk， 于是遍历 binmap 的下一个 block，直到找到一个不为 0 的 block 或者遍历完所有的 block。 退出循环遍历后，设置 bin 指向 block 的第一个 bit 对应的 bin，并将 bit 置为 1，表示该 block 中 bit 1 对应的 bin，这个 bin 中如果有空闲 chunk，该 chunk 的大小一定满足要求。

….过了

如果从所有的 bins 中都没有获得所需的 chunk，可能的情况为 bins 中没有空闲 chunk， 或者所需的 chunk 大小很大，下一步将尝试从 top chunk 中分配所需 chunk。源代码实现如 下：

use_top

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
use_top:
  /*
     If large enough, split off the chunk bordering the end of memory
     (held in av->top). Note that this is in accord with the best-fit
     search rule.  In effect, av->top is treated as larger (and thus
     less well fitting) than any other available chunk since it can
     be extended to be as large as necessary (up to system
     limitations).

     We require that av->top always exists (i.e., has size >=
     MINSIZE) after initialization, so if it would otherwise be
     exhausted by current request, it is replenished. (The main
     reason for ensuring it exists is that we may need MINSIZE space
     to put in fenceposts in sysmalloc.)
   */

  victim = av->top;
  size = chunksize (victim);

将当前分配区的top chunk赋值给 victim，并获得 victim 的大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if (__glibc_unlikely (size > av->system_mem))
  malloc_printerr ("malloc(): corrupted top size");

if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
  {//topchunk够用
    remainder_size = size - nb;
    remainder = chunk_at_offset (victim, nb);
    av->top = remainder;
    set_head (victim, nb | PREV_INUSE |
              (av != &main_arena ? NON_MAIN_ARENA : 0));
    set_head (remainder, remainder_size | PREV_INUSE);

    check_malloced_chunk (av, victim, nb);
    void *p = chunk2mem (victim);
    alloc_perturb (p, bytes);
    return p;
  }

由于 top chunk 切分出所需 chunk 后，还需要 MINSIZE 的空间来作为fencepost，所需必须满足 top chunk 的大小大于所需 chunk 的大小加上 MINSIZE 这个条件，才能从 top chunk 中分配所需 chunk。从 top chunk 切分出所需 chunk 的处理过程跟前面的 chunk 切分类似， 不同的是，原 top chunk 切分后的剩余部分将作为新的 top chunk，原 top chunk 的 fencepost 仍然作为新的top chunk 的 fencepost，所以切分之后剩余的 chunk 不用 set_foot。

1
2
3
4
5
6
7
8
9
10
11
/* When we are using atomic ops to free fast chunks we can get
   here for all block sizes.  */
else if (atomic_load_relaxed (&av->have_fastchunks))
  {
    malloc_consolidate (av);
    /* restore original bin index */
    if (in_smallbin_range (nb))
      idx = smallbin_index (nb);
    else
      idx = largebin_index (nb);
  }

如果 top chunk 也不能满足要求，查看 fast bins 中是否有空闲 chunk 存在，由于开启了 ATOMIC_FASTBINS 优化情况下，free 属于 fast bins 的 chunk 时不需要获得分配区的锁，所以在调用_int_malloc()函数时，有可能有其它线程已经向 fast bins 中加入了新的空闲 chunk，也有可能是所需的 chunk 属于 small bins，但通过前面的步骤都没有分配到所需的 chunk，由于 分配 small bin chunk 时在前面的步骤都不会调用 malloc_consolidate()函数将 fast bins 中的 chunk 合并加入到 unsorted bin 中。所在这里如果 fast bin 中有 chunk 存在， 调用 malloc_consolidate()函数，并重新设置当前 bin 的 index。并转到最外层的循环，尝试重新分 配 small bin chunk 或是 large bin chunk。如果开启了 ATOMIC_FASTBINS 优化，有可能在由其 它线程加入到fast bins 中的 chunk 被合并后加入 unsorted bin 中，从 unsorted bin 中就可以 分配出所需的 large bin chunk 了，所以对没有成功分配的 large bin chunk 也需要重试。

1
2
3
4
5
6
7
8
9
10
11
12
      /*
         Otherwise, relay to handle system-dependent cases
       */
      else
        {
          void *p = sysmalloc (nb, av);
          if (p != NULL)
            alloc_perturb (p, bytes);
          return p;
        }
    }
}

山穷水尽了，只能想系统申请内存了。sysmalloc()函数可能分配的 chunk 包括 small bin chunk，large bin chunk 和 large chunk。

至此，_int_malloc()函数的代码就罗列完了，当还有两个关键函数没有分析，一个为 malloc_consolidate()，另一个为 sysmalloc()。

malloc_consolidate()