Unbelievable
首页 标签 归档 友链 关于

堆相关数据结构学习（一）——chunk

2021-08-07

What is chunk

由malloc申请的内存称之为chunk。在ptmalloc内部用malloc_chunk结构体来表示。

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

malloc_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
struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  
    /*  
    若物理相邻的前一个（较低地址）chunk是空闲的，则记录其大小，否则可用来存储前一个chunk的数据
    */
    
  INTERNAL_SIZE_T      size;       
    /* 
    该chunk的大小，且必须时2*SIZE_SZ的整数倍，若不是则会转换为满足大小和要求的最小值。
	32位系统中，SIZE_SZ是 4；64位系统中，SIZE_SZ是 8。 
	该字段的低三位比特对chunk大小没有影响，从高到低分别表示：
NON_MAIN_ARENA -> 记录上一个 chunk 是否不属于主线程，1 表示不属于
IS_MAPPED -> 记录上一个chunk是否被mmap分配的
PREV_INUSE -> 标志上一个chunk是否处于释放状态，处于释放状态为 1。
	一般来说，堆中第一个被分配的内存块的 size 字段的 P 位都会被设置为 1，以便于防止访问前面的非法内存
  */

  struct malloc_chunk* fd;         
  struct malloc_chunk* bk;
      /* 
    chunk 处于分配状态时，从 fd 字段开始是用户的数据，bk 指向数据末。
    
    chunk 空闲时，会被添加到对应的空闲管理链表中，其字段的含义如下：
    fd 指向下一个（非物理相邻）空闲的 chunk
    bk 指向上一个（非物理相邻）空闲的 chunk
    通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理
    */

  struct malloc_chunk* fd_nextsize; 
  struct malloc_chunk* bk_nextsize;
    /*
    仅在chunk空闲时有效
    仅用于large bin
    分别指向前后第一个与当前chunk大小不同的chunk（利于遍历合适的chunk）
    */
};

处于已分配状态的chunk内存如下：（图中少标了一个标志位）前两个字段称为 chunk header，后面的部分称为 user data。每次 malloc 申请得到的内存指针，其实指向 user data 的起始处即图中的mem。

1

处于释放状态的chunk：此时 fd，bk 有效

1

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

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

chunk相关宏

chunk与mem指针头部的转换

1
2
3
/* 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))

最小的chunk大小等同于 MINSIZE

1
2
/* The smallest possible chunk */
#define MIN_CHUNK_SIZE (offsetof(struct malloc_chunk, fd_nextsize))

其中，offset()函数算出 fd_nextsize 在 malloc_chunk 中的偏移，说明最小的 chunk 至少要包含到 bk 指针。

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

1
2
3
4
5
6
7
/* Check if m has acceptable alignment */
// MALLOC_ALIGN_MASK = 2 * SIZE_SZ -1
#define aligned_OK(m) (((unsigned long) (m) & MALLOC_ALIGN_MASK) == 0)

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

请求字节数判断

就是判断请求的内存大小是否可以满足

1
2
3
4
5
6
7
8
/*
   Check if a request is so large that it would wrap around zero when
   padded and aligned. To simplify some other code, the bound is made
   low enough so that adding MINSIZE will also not wrap around zero.
 */

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* pad request bytes into a usable size -- internal version */
//MALLOC_ALIGN_MASK = 2 * SIZE_SZ -1
#define request2size(req)                                                      \
    (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)                           \
         ? MINSIZE                                                             \
         : ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

/*  Same, except also perform argument check */

#define checked_request2size(req, sz)                                          \
    if (REQUEST_OUT_OF_RANGE(req)) {                                           \
        __set_errno(ENOMEM);                                                   \
        return 0;                                                              \
    }                                                                          \
    (sz) = request2size(req);

大致流程如下：

  • 判断用户请求的字节大小是否可以满足，REQUEST_OUT_OF_RANGE
  • 由于chunk间存在复用，所以当前chunk若是用来分配，则下一个chunk的 prev_chunk 也属于当前chunk的user_data部分
  • 若 请求大小 + SIZE_SZ 对齐后的大小小于MINSIZE则直接分配MINSIZE
  • 若大于，则再进行 2*SIZE_SZ 对齐

标记相关

chunk标志位进行或运算，用于掩码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
#define PREV_INUSE 0x1

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

/* 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

/*
   Bits to mask off when extracting size
   Note: IS_MMAPPED is intentionally not masked off from size field in
   macros for which mmapped chunks should never be seen. This should
   cause helpful core dumps to occur if it is tried by accident by
   people extending or adapting this malloc.
 */
#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)

通过chunk指针p 对某标志位进行提取、检查、置位和清除

1
2
3
4
5
6
7
8
9
10
11
/* extract inuse bit of previous chunk */
#define prev_inuse(p) ((p)->mchunk_size & PREV_INUSE)

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

/* 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)

要注意，当前chunk的使用状态是由下一个chunk的size成员的低比特位决定的。

获取chunk size

1
2
3
4
5
/* 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)

获取下一个物理相邻的chunk

当前chunk指针加上当前chunk的大小以获得

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

获取（修改）前一个chunk的信息

仅当前一个chunk处于释放状态有效

1
2
3
4
5
6
7
8
/* 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)))

当前chunk使用状态相关操作

即对下一个chunk的size对象的标志位操作

1
2
3
4
5
6
7
8
9
10
/* 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)

设置 chunk 的 size 字段

set_head_size 不会改变当前 chunk 的标志位（这里书是这么写，但单实现好像不然，这里先不管）而 set_head 会

1
2
3
4
5
6
7
8
9
10
11
/* Set size at head, without disturbing its use bit */
// SIZE_BITS = 7
#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))

获取指定偏移的 chunk

直接把指定偏移处看作chunk

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

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

1
2
3
4
5
6
7
8
9
/* 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))

chunk 合并

当一个非fast bin 的chunk被释放 时，会与相邻的chunk合并，顺序通常是先向后合并（相邻低地址）再向前合并（相邻高地址）。如果向前合并的chunk时 top chunk，则合并成新的chunk；如果不是的话则合并之后会被加入 unsorted bin 中。

chunk 拆分

当用户申请的 chunk 较小时，会先将一个大的 chunk 进行拆分，合适的部分返回给用户，剩下的部分（称为remainder）加入unsorted bin 中。同时malloc_state 中的last_remainder 会记录最近拆分出的remainder。当然这个remainder的大小至少要为MINSIZE，否则不能拆分。

拆分 chunk 的一种情况是：fast bin 和 small bin 中都没有合适的chunk，同时unsorted bin 中有且只有一个可拆分的chunk，并且该chunk 是last remainder。

关于其源码另起一篇来分析

参考资料

  • 《CTF竞赛权威指南（PWN篇）》

  • CTF wiki

updated at 2021-11-25

# Heap
Previous Post
关于dll注入
Next Post
ROP

Comments