堆笔记1

2018-10-22

ctf

1. 什么是 chunk

由 malloc 申请的内存称为 chunk

2. chunk 结构

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

struct malloc_chunk {

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

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

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

chunk 字段解释

prev_size : 如果前一个chunk空闲,则该字段表示前一个chunk的大小。如果前一个chunk 非空闲状态,则此处作为前一个 chunk 的数据部分(即被前一个chunk使用)。

size : 记录当前块的大小,必须为 2 * SIZE_T 的整数倍(SIZE_T 在32位为4,64位为8)该字段的低三位和大小没关系,分别为:

1. NON_MAIN_ARENA 记录该 chunk 是否属于主线程
2. IS_MAPPED  记录当前 chunk 是否由 mmap 分配
3. PREV_INUSE 记录前一个 chunk 是否被分配(第一个被分配的 chunk 的 P位都会设置成 1,防止访问前面的非法内存)。当该位为 0 时,可以用 prev_size 字段获得上个 chunk 的大小和地址。也方便空闲块的合并

fd: 如果该 chunk 被分配,从此处开始就是用户的数据,否则指向上一个空闲 chunk
bk: 指向上一个空闲的 chunk

fd_nextsize: 指向前一个与当前 chunk 大小不同的空闲块
bk_nextsize: 指向后一个与当前 chunk 大小不同的空闲块

3. bins

什么是 bins

用户释放掉的 chunk 不会立马归还给系统,而是程序保留管理着,这样下次再分配时无需系统调用,节省资源。

ptmalloc 将 chunk 分为四类:

1
2
3
4
fast bins
unsorted bins
small bins
large bins

对于后三个 bins,ptmalloc 将他们分在同一个数组中,结构如下:

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

数组中的 bins 顺序如下:

1
2
3
1. 数组第一个为 unsorted bin ,没有排序,内部 chunk 比较杂
2. 数组中第 2 到 63 个为 small bin , 同一个 small bin 链中的大小相同,两个相邻的 small bin 链中的大小相差字节数为 2*机器字长(即 32 位相差8 ,64位相差 16)
3. 后面的为 large bins,chunk 的 fd 按从大到小排序。

当然还有上面提到的 fast bins,ptmalloc 为了提高分配速度,会把一些小的 bins 分配到 fast bins 中,fast bins 中的每个 P 位(chunk 的使用标记)都被设置为 1,所以不会被合并起来。

4. bins 们

4.1 fast bin

为了提高分配效率而设计的 fast bin 将存储一些较小的内存块,它们的 使用位
永远被置为 1,所以不会被合并起来。

看两个宏:

1
2
3
4
5
6
7
8
9
10
#ifndef DEFAULT_MXFAST
#define DEFAULT_MXFAST (64 * SIZE_SZ / 4)
#endif

#define MAX_FAST_SIZE (80 * SIZE_SZ / 4)

#define set_max_fast(s) \
global_max_fast = \
(((s) == 0) ? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
#define get_max_fast() global_max_fast

  1. ptmalloc 首先会调用 set_max_fast 并把 DEFAULT_MXFAST 传进去,也就是设置 fast bins 中 chunk 的最大值。
  2. MAX_FAST_SIZE 为 0 时,系统就不会支持 fastbin 。
  3. 当申请空间一个小于或等于 global_max_fast 时,ptmalloc 首先会在 fast bin 查询是否有合适大小的块。

再来看个东西:

1
2

#define FASTBIN_CONSOLIDATION_THRESHOLD (65536UL)

当释放的 chunk 与该 chunk 相邻的空闲 chunk 合并后大于 FASTBIN_CONSOLIDATION_THRESHOLD,表明内存碎片比较多了,我们就需要把 fast bins 中的 chunk 都进行合并。

malloc_consolidate 函数可以释放后所有 fastbins 并且将他们和其他的 空闲块 合并。

4.2 small bin

small bins 有 62 个双向链表,每个链表存储的大小都一致。

small bins 中每个链表的大小都有规律,即:chunk_size = 2SIZE_INDEXindex,例如在 32 位系统下下标为 2 的链表的大小为 242 = 16 个字节。

当然,fast bin 中的 chunk 是有可能会被放到 small bin 中去的,因为他们确实有些重合了。

4.3 large bin

  1. large bins 共有 63个 bin,每个 bin 中的大小不一致,但有个差值。
  2. 每个 bin 中的 chunk 大小之间公差一致。
  3. 第一个 large bin 的起始 chunk 大小为 512 字节,该组公差为 64B,所以该组可以存储 chunk 的大小范围为: [512,512+64)

4.4 unsorted bin

  1. 乱序的 bins
  2. 放进 unsorted bin 的 chunk 来自:
    1. 分割完大块后剩余部分,并且该部分要大于 MINSIZE
    2. 释放不属于 fast bin 的 chunk 并且 该 chunk 不和 top chunk 紧邻。

4.5 top chunk

  1. 简单理解就是在地址最高的一个 chunk,不属于任何 bins。
  2. 当程序需要分配的内存大小在 bins 中都不满足的情况下,尝试用 top chunk 给程序分配,如果够,则剩余部分继续做 top chunk,如果不够,则申请扩展内存后再分配。
  3. 当邻近 top chunkchunk 被释放后,会合并到 top chunk

4.6 last remainder

  1. 当在 small chunk 找不到合适的块时,如果 last remainder chunk 大于要分配的内存,则分割这个 chunk 给用户并将剩余部分继续作为 last remainder chunk,该块好像是放在 unsorted bins 中的。