堆入门概述

1
2
3
4
5
参考资料；
https://www.yuque.com/cyberangel/rg9gdm/uhdudz
https://www.anquanke.com/post/id/163971#h3-9
https://zhuanlan.zhihu.com/p/374431199
《CTF竞赛权威指南pwn篇》

什么是堆?

堆和栈不同，堆是（由操作系统内核或者堆管理器）动态分配的，是程序虚拟内存中由低地址到高地址增长的线性区域。一般只有当用户向操作系统申请内存时，这片区域才会被内核分配出来，并且出于效率和页对齐的考虑。通常会分配相当大的连续内存。程序再次申请时便会从这片内存中分配，直到堆空间不能满足时才会再次增长。

先看看堆在虚拟内存中的位置

img

堆的属性是可读可写的，大小通过brk()或sbrk()函数进行控制。如上图所示，在堆未初始化时，Program break指向BSS段的末尾，通过调用brk()和sbrk()来移动program_break使得堆增长。在堆初始化时，如果开启了ASLR,则堆的起始地址start_brk会在BSS段之后的随机位移处，反之则start_brk紧挨着BSS段。

两个函数定义如下：

1
2
3
4
#include <unistd.h>
int brk(void *addr);//addr指针用来设置program break指向的位置，成功执行后返回0

void *sbrk(intptr_t increment); //用于与program_break相加调整program_break的值，成功执行后返								  回上一次program_break的值

堆的生长方向是低地址到高地址生长的，而栈是从高地址到低地址生长的。

实际上堆可以申请的内存空间要比栈大很多，在linux的4G的虚拟内存空间里最高可以达到2.9G的空间

mmap()和unmmap()

​ 当用户申请的内存过大时，ptmalloc2会选择通过mmap()函数创建匿名映射段（不与任何文件关联）供用户使用，并通过unmmap()函数回收。

堆块的基本结构

pre size(prev size)和size头统称为chunk头（chunk header）

每次malloc申请得到的内存指针，其实指向user data的起始处。

堆的大致图解如下:

image-20230716075408744

prev size和 size字段分别代表前一个chunk的大小和当前chunk的大小，在64位环境下两个分别都是8字节，共16字节，称之为chunk的头部字段。后面的user data是用户可以输入数据的地方。

为了节省空间，将size的最低三位设置为标志位，从高到低依此是：

  • non-main-arena 用来记录当前chunk是否不属于主线程，1代表不属于，0代表属于。
  • is-mmap表示当前chunk是否由mmap分配的，1表示属于，0表示不属于。
  • prev-inuse用来表示前面紧邻的那个chunk是否正在使用，0表示前面的chunk已经被释放，1表示正在被用户使用

image-20230716081011494

空间复用

prev size记录前面一个chunk的大小。注意，prev size只有在前面的chunk被free掉的时候才生效，也就是说，只有在prev_inuse为0的时候，系统才把prev_size字段当作prev size（记录前一个chunk的大小）

如果chunk正在被使用，那么他会把下一个chunk的prevsize字段当作userdata,充分利用空间。

也就是说，如果我们申请一个0x80长度大小的区域，系统实际给我我们0x90（0x10头部），如果我们申请0x88大小的区域，系统同样也会给我们0x90大小的区域（算上头部）,剩下的8字节，使用nextchunk的prevsize才真正代表前一个chunk的大小。

特殊的堆块

  • 最开始时，程序的堆还未被利用，整个的堆区域属于一个很大的堆块叫做topchunk。
  • 当已经使用的空间不够时，程序就会从topchunk中分割一块出来给程序使用

重要概念和结构体

arena

这是Linux堆管理的常用术语。arena包含一片或数片连续的内存，堆块将会从这片区域划分给用户。

主线程的arena被称为main_arena，它包含start_brk和brk之间这片连续的区域。其实就是ptmalloc2堆管理器通过与操作系统内核进行交互申请到的。

因为是主线程分配的，所以叫做main arena，是通过brk()调用来扩展。

其它子线程的arena可以有数片连续内存。但是子线程分配的映射段大小是固定的，不可以扩展，如果映射段不够用的话需要再次调用mmap()来分配新的内存。

heap_info

img

子线程的arena可以有多片连续内存，这些内存被称为heap。每一个heap都有自己的head_info描述头。其定义如下，heap_info是通过（prev指针）链表相连接的，并且heap header里面面保存了指向其所属的arena的指针ar_ptr。

1
2
3
4
5
6
7
8
9
10
11
12
13
// malloc/arena.c
typedef struct _heap_info {
  // Arena for this heap
  struct malloc_state *ar_ptr;
  // Previous heap
  struct _heap_info *prev;
  // Current size in bytes
  size_t size;
  // Size in bytes that has been mprotected PROT_READ|PROT_WRITE
  size_t mprotect_size;
  // padding
  char pad[];
} heap_info;

arena在ptmalloc2中对应的数据结构是malloc_state，定义如下:

malloc_state
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
// malloc/malloc.c
struct malloc_state {
  // Flags (formerly in max_fast)
  int flags;
  // Set if the fastbin chunks contain recently 
  // inserted free blocks, Note this is a bool 
  // but not all targets support atomics on booleans
  int have_fastchunks;
  // Fastbins
  mfastbinptr fastbinsY[NFASTBINS];
  // Base of the topmost chunk -- not otherwise kept in a bin
  mchunkptr top;
  // The remainder from the most recent split of a small request
  mchunkptr last_remainder;
  // Normal bins packed as described above
  mchunkptr bins[NBINS * 2 - 2];
  // Bitmap of bins
  unsigned int binmap[BINMAPSIZE];
  // Linked list
  struct malloc_state *next;
  // Linked list for free arenas.  
  struct malloc_state *next_free;
​
  // Number of threads attached to this arena
  INTERNAL_SIZE_T attached_threads;
  // Memory allocated from the system in this arena
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};
  • 每个线程只有一个arena header，里面保存了bins、top chunk等信息。主线程的main_arena保存在libc.so的数据段里，其他线程的arena则保存在给该arena分配的heap里面。

堆块的管理

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;
};

image-20230716084131625

因为chunk被free之后，按常理来说用户不应该能够访问到这个chunk,所以在userdata区域存放一些用于管理内存的指针信息。

  • fastbin：单链表结构，只有fd，是个单链表结构
  • small&unsortedbin：双向链表结构，fd和bk都有
  • largebin：双向链表，fd和bk都有，同时还有fd nexesize和bk nextsize

在ptmalloc2内存管理机制下，为了保证程序的快速运行，而且方便内存管理，所以ptmalloc2将释放后的堆块根据其大小分成不同的bin。不同大小区间的chunk被划分到不同的bin中，再加上一种特殊的bin，一共有四种

  • fastbin：大小范围0x20~0x80
  • smallbin：大小范围0x90-0x400
  • Large bin：大小范围0x410以上
  • unsortedbin：未被归类的bin,临时存储用，存储的堆块大小不一定多大。

这些bin记录在malloc_state结构中

  • fastbinsY：这是一个bin数组，里面有NFASTBINS个fast bin。
  • bins: 也是一个bin数组，一共有126个bin，按顺序分别是：
    • bin 1为unsorted bin
    • bin2到bin63为small bin
    • bin64到bin126为large bin
fastbin

image-20230716100219297

​ 实践中，程序申请和释放的堆块往往都比较小，所以glibc对这类bin使用单链表结构，并采用LIFO（后进先出）的分配策略。并且在ptmalloc2下，为了加快速度，fast bin里的chunk不会进行合并操作，并且下个chunk的prv_inuse始终标记为1，使其始终处于使用状态。

unsorted bin

image-20230716103137071

image-20230716100319758

一定大小的chunk被释放时，在进入small bin或者large bin之前，会先加入unsorted bin。因为可以加快分配效率。并且采用FIFO（先进先出）的分配策略。

small bin

（以64位系统为例）

image-20230716103206648

image-20230716101014227

满足空间比fast bin大一点。如果程序请求的内存范围不在fast bin范围内，就会考虑small bin。简单点说就是大于80 bytes小于某一个值时就会选择它。

描述：

  1. 在32位系统中，当用户释放的堆块大小大于64B,小于等于512B时使用small bin进行管理
  2. small bin为双向循环链表，且使用FIFO（先入先出）
  3. 当满足small bin条件的chunk被释放后，会优先被放入unsorted bin，才会被分配到small bin中。
  4. 相邻的free chunk将会被合并成一个更大的free chunk，增加内存利用率。
  5. 由于small bin和fast bin有重合部分，所以这些chunk在某些情况下会被加入到small bin中。
largebin

large bin在bins里居第64位到第126位，共63个。

image-20230716103757122

调用malloc时，程序在干什么

  • 计算真正的堆块大小（加上头部长度，对齐）

  • 在fastbin范围内？

    • 是，检查对应的bin链表中有没有chunk
      • 有，分配给用户，完成

  • 如果不在fastbin范围内，或者没有chunk可用

  • 在smallbin范围内？

    • 是，检查对应大小的bin链表中有没有chunk
      • 有，取出来给程序，完成

  • 如果不在smallbin范围内，或者smallbin里面也没有。

  • unsortedbin中有没有chunk？

    • 有的话，从尾部取出第一个chunk，看看大小是否满足需求。
      • 满足，切分后大小是或否大于minsize？
        • 大于，切分块，返回给用户，剩下的块放进unsorted bin
        • 小于等于minsize，直接返回给用户，完成
    • 不满足，把这个块放入small/largebin对应的链表中，继续遍历下一个块

  • 如果unsortedbin中所有的块也不能满足需求。

  • 大小是否在largebin范围？

    • 是，检查对应的bin链表中有没有符合的chunk。
      • 有，找到满足需求最小的chunk，切分块返回，剩下的放进unsorted bin中。

  • largebin也不行？再次遍历small/large找best fit的chunk。

  • 还是没有，那就从topchunk中切割。

  • topchunk也不够？mmap系统调用。

当调用free时，程序干了什么

  • free的chunk大小属于fastbin吗？
    • 是，放进fastbin，完成。
  • 是mmap分配的吗？
    • 是，调用munmap
  • 前一个chunk空闲吗？
    • 是，向前合并。
  • 后一个chunk是topchunk吗？
    • 是，和topchunk合并，完成
  • 后一个chunk是free的吗？
    • 是，向后合并。
  • 放进unsortedbin，完成。