Heap learning

属于是国赛前的临时抱佛脚了

简介

在程序运行过程中，堆可以提供动态分配的内存，允许程序申请大小未知的内存。堆其实就是程序虚拟地址空间的一块连续的线性区域，它由低地址向高地址方向增长。我们一般称管理堆的那部分程序为堆管理器。

其主要功能如下

1. 响应用户的申请内存请求，向操作系统申请内存，然后将其返回给用户程序。同时为了保持内存管理的高效性，内核一般会预先分配一块很大的连续内存，然后让堆管理器通过某种算法进行管理，只有出现堆空间不足的情况时，堆管理器才会再次与操作系统进行交互

2. 管理用户释放的内存。一般来说用户释放的内存并不是直接返还给操作系统，而是由堆管理器进行管理。

结构

malloc_chunk

概述

在程序执行过程中，我们称由malloc申请的内存为chunk。这块内存在ptmalloc内部用malloc_chunk结构体表示，当申请的chunk被free后会加入到相应的空闲管理列表中

值得注意的是不管处于何种状态malloc_chunk均使用的统一的结构

/*
  This struct declaration is misleading (but accurate and necessary).
  It declares a "view" into memory allowing access to necessary
  fields at known offsets from a given base. See explanation below.
*/
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;
};

字段解释

prev_size:如果该chunk的物理相邻的前一个chunk空闲则记录前一个chunk的size(包括chunk头)。否则用来储存前一个chunk的数据

size:记录该chunk的大小，低三比特对chunk大小无影响

• A:NON_MAIN_ARENA:记录是否属于主线程
• M:IS_MAPPED:记录该chunk是否由mmap分配
• P:PREV_INUSE:记录前一个chunk是否被分配

fd,bk:chunk处于分配状态时，从fd开始是用户的数据区。空闲时则被添加到相应空闲管理链表中，通过fd和bk将空闲chunk块加入到链表进行统一管理

fd_nextsize,bk_nextsize:只有chunk空闲且该chunk为large chunk时使用

• fd_nestsize:指向前一个与当前chunk大小不同的空闲块(不包含bin头指针)
• bk_nestsize:指向后一个与当前chunk大小不同的空闲块(不包含bin头指针)

bin

概述

用户释放掉的chunk不会马上归还系统，ptmalloc会统一管理heap和mmap映射区域空闲的chunk，以避免频繁的系统调用，降低内存分配开销

ptmalloc根据chunk的大小及状态将chunk初步分为4类:fast bins，small bins，large bins，unsorted bins

除了fast bins其他类型bin中的排布都遵循任意两物理相邻的空闲chunk不能再一起

• fastbin: 大小范围在0x20-0x80
• smallbin: 大小范围在0x90-0x400
• largebin: 大小范围在0x410以上
• unsortedbin: 未被归类的bin用于临时储存，存放大小不定

堆块合并:当free掉一个chunk时可能会触发向前合并和向后合并

• fastbin

  管理fastbin free chunk，单链表结构，FILO策略

  共十个fastbin链表，每个链表fastbin的size从0x20-0x80以0x10递增

• unsortedbin

  管理unsorted chunk，只有一个双向链表，所有大小大于fastbin的chunk都先被暂时存入unsortedbin中，链表中chunk大小不一

• smallbin

  管理small chunk由62个双向链表组成，每个链表的chunk大小一致以0x10递增

• largebin

  管理large chunk，由63个双向链表组成，FIFO策略，同一双向链表中的chunk大小可不一致但在一定范围内，bins大小从小到大排列

top chunk

glibc中对top chunk的描述

/*
   Top

    The top-most available chunk (i.e., the one bordering the end of
    available memory) is treated specially. It is never included in
    any bin, is used only if no other chunk is available, and is
    released back to the system if it is very large (see
    M_TRIM_THRESHOLD).  Because top initially
    points to its own bin with initial zero size, thus forcing
    extension on the first malloc request, we avoid having any special
    code in malloc to check whether it even exists yet. But we still
    need to do so when getting memory from system, so we make
    initial_top treat the bin as a legal but unusable chunk during the
    interval between initialization and the first call to
    sysmalloc. (This is somewhat delicate, since it relies on
    the 2 preceding words to be zero during this interval as well.)
 */

/* Conveniently, the unsorted bin can be used as dummy top on first call */
#define initial_top(M) (unsorted_chunks(M))

top chunk就是处于当前堆物理地址最高的chunk，其作用是在当所有bin都无法满足用户请求的大小时，如果其大小不小于指定大小就进行分配，并将剩余部分作为新top chunk。否则先对heap进行扩展再进行分配

ptmalloc2

常见操作

unlink

用于将一个双向链表中的一个元素取出，和数据结构中的链表元素的删除一样，在malloc，free时都有使用

wiki上说因为P的指针最后未变化所以会导致地址的泄露，以后遇到了再了解吧

tcache机制

tcache是glibc2.26之后引入的技术，目的是提升堆管理的性能，同时为了性能的提升也放弃了很多的安全检查，因此具有很多新的利用方式

工作方式

当chunk被free时若size小于small bin的size时会被放置在对应的tcache中直到被填满(7个)，填满后再free则和之前一致

在malloc时若size在tcache范围内先从tcache取chunk，直到tcache为空，之后再从bin中找

summary:确实还是挺难的但是理解起来比以前清楚多了，之后再实践一些常用的漏洞和利用吧