8 Apr 2019

堆利用从入门到入狱

堆利用从入门到入狱

11

  • 程序虚拟地址空间的一块连续的线性区域,由低地址向高地址方向增长,在程序运行过程中,堆可以提供动态分配的内存,允许程序申请大小未知的内存。

    1

    • 堆管理器

      管理堆的那部分程序称为堆管理器。

      堆管理器处于用户程序与内核中间,主要做以下工作:

      1. 响应用户的申请内存请求,向操作系统申请内存,然后将其返回给用户程序

        内核一般会预先分配很大的一块连续的内存,让堆管理器管理,只有出现了堆空间不足的情况,堆管理器才会再次与操作系统交互。

      2. 管理用户所释放的内存。

        一般来说,用户释放的内存不是直接返还给操作系统,而是由堆管理器管理,这些释放的内存可以响应用户新申请内存的请求。

    • 基本操作
      • malloc
        /*
          malloc(size_t n)
          Returns a pointer to a newly allocated chunk of at least n bytes, or null
          if no space is available. Additionally, on failure, errno is
          set to ENOMEM on ANSI C systems.
          If n is zero, malloc returns a minumum-sized chunk. (The minimum
          size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit
          systems.)  On most systems, size_t is an unsigned type, so calls
          with negative arguments are interpreted as requests for huge amounts
          of space, which will often fail. The maximum supported value of n
          differs across systems, but is in all cases less than the maximum
          representable value of a size_t.
        */
        

        返回对应大小字节的内存块的指针

        当n=0时,返回当前系统允许的堆的最小内存块。

        size_t是无符号数,在 64 位中是 64 位无符号整数,32 位中是 32 位无符号整数 ,当n为负数时,会申请很大的内存空间,但通常都会失败。

      • free
        /*
              free(void* p)
              Releases the chunk of memory pointed to by p, that had been previously
              allocated using malloc or a related routine such as realloc.
              It has no effect if p is null. It can have arbitrary (i.e., bad!)
              effects if p has already been freed.
              Unless disabled (using mallopt), freeing very large spaces will
              when possible, automatically trigger operations that give
              back unused memory to the system, thus reducing program footprint.
            */
        

        释放p指向的内存块

        当p为空指针时,函数不执行任何操作

        若p已经被释放,再次释放,gg

        当释放很大的内存空间时,程序会将这些内存空间还给系统(被禁用时除外)

      • 内存分配背后的系统调用
        • (s)brk

          start_brk:堆的起始地址

          brk:堆的当前末尾

          通过增加brk的大小向操作系统申请内存

          初始时,start_brk和brk指向同一地址,若不开启ASLR,指向data/bss段结尾,若开启,指向data/bss段结尾后的随机偏移处

        • mmap

          malloc 会使用 mmap 来创建独立的匿名映射段。匿名映射的目的主要是可以申请以 0 填充的内存,并且这块内存仅被调用进程所使用。

      • 多线程支持
    • 堆相关数据结构
      • malloc_chunk

        由 malloc 申请的内存,在 ptmalloc 内部用 malloc_chunk 结构体来表示。

        当程序申请的 chunk 被 free 后,会被加入到相应的空闲管理列表中。

        无论一个 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大小)空闲,则该字段记录前一个chunk的大小(包括chunk头),否则,该字段可以储存物理相邻的前一(较低地址)chunk的数据(空间复用)

        • size

          该chunk的大小,大小必须是 2 * SIZE_SZ 的整数倍,若申请的内存大小不是 2 * SIZE_SZ 的整数倍,会转换为满足大小且最小的 2 * SIZE_SZ的倍数。

          size字段低三位对chunk大小没有影响,从高到底分别表示

          • NON_MAIN_ARENA,记录当前 chunk 是否不属于主线程,1 表示不属于,0 表示属于。
          • IS_MAPPED,记录当前 chunk 是否是由 mmap 分配的。
          • PREV_INUSE,记录前一个 chunk 块是否被分配。
        • fd,bk

          chunk 处于分配状态时,从 fd 字段开始是用户的数据。

          chunk 空闲时,会被添加到对应的空闲管理链表中

          通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理

          fd 指向下一个(非物理相邻)空闲的 chunk

          bk 指向上一个(非物理相邻)空闲的 chunk

        • fd_nextsize, bk_nextsize

          只有 chunk 空闲的时候才使用,用于较大的 chunk

          fd_nextsize 指向前一个与当前 chunk 大小不同的第一个空闲块,不包含 bin 的头指针。

          bk_nextsize 指向后一个与当前 chunk 大小不同的第一个空闲块,不包含 bin 的头指针。

      • 已分配的chunk
        chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                |             Size of previous chunk, if unallocated (P clear)  |
                +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                |             Size of chunk, in bytes                     |A|M|P|
          mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                |             User data starts here...                          .
                .                                                               .
                .             (malloc_usable_size() bytes)                      .
        next    .                                                               |
        chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                |             (size of chunk, but used for application data)    |
                +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                |             Size of next chunk, in bytes                |A|0|1|
                +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        

        前两个字段称为chunk header,后面的称为user data,每次 malloc 申请得到的内存指针指向 user data 的起始处

      • free状态的chunk

        记录在链表中,循环双向链表或单向链表

        chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                |             Size of previous chunk, if unallocated (P clear)  |
                +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        `head:' |             Size of chunk, in bytes                     |A|0|P|
          mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                |             Forward pointer to next chunk in list             |
                +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                |             Back pointer to previous chunk in list            |
                +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                |             Unused space (may be 0 bytes long)                .
                .                                                               .
         next   .                                                               |
        chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        `foot:' |             Size of chunk, in bytes                           |
                +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                |             Size of next chunk, in bytes                |A|0|0|
                +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        

        一般情况下,物理相邻的两个空闲 chunk 会被合并为一个 chunk 。堆管理器会通过 prev_size 字段以及 size 字段合并两个物理相邻的空闲 chunk 块

      • bin

        ptmalloc 采用分箱式方法对空闲的 chunk 进行管理。

        据空闲的 chunk 的大小以及使用状态将 chunk 初步分为 4 类:fast bins,small bins,large bins,unsorted bin

        • Fast Bin

          单向链表组织,LIFO,后被释放的先被分配

          当用户需要的 chunk 的大小小于 fastbin 的最大大小时, ptmalloc 会首先判断 fastbin 中相应的 bin 中是否有对应大小的空闲块。

          fastbin 范围的 chunk 的 inuse 始终被置为 1,因此它们不会和其它被释放的 chunk 合并

        • Small Bin

          small bins 中一共有 62 个循环双向链表,每个链表中存储的 chunk 大小都一致,FIFO,先被释放的先被分配

          small bins 中每个 chunk 的大小与其所在的 bin 的 index 的关系为:chunk_size = 2 * SIZE_SZ *index

        • Large Bin

          一共包括 63 个 bin,每个 bin 中的 chunk 的大小不一致,处于一定区间范围内

          63 个 bin 被分成了 6 组,每组 bin 中的 chunk 大小之间的公差一致

          数量 公差
          1 32 64B
          2 16 512B
          3 8 4096B
          4 4 32768B
          5 2 262144B
          6 1 不限制
        • Unsorted Bin

          可以视为空闲 chunk 回归其所属 bin 之前的缓冲区。

      • Top Chunk

        程序第一次进行 malloc 的时候,heap 会被分为两块,一块给用户,剩下的那块就是 top chunk(处于当前堆的物理地址最高的 chunk)

        top chunk不属于任何一个 bin

        当所有的 bin 都无法满足用户请求的大小时,如果top chunk大小不小于指定的大小,就进行分配,并将剩下的部分作为新的 top chunk。否则,就对 heap 进行扩展后再进行分配

      • last remainder

        在用户使用 malloc 请求分配内存时,ptmalloc2 找到的 chunk 可能并不和申请的内存大小一致,这时候就将分割之后的剩余部分称之为 last remainder chunk ,unsort bin 也会存这一块。top chunk 分割剩下的部分不会作为 last remainer

  • free顺序
  1. size是否属于fast bin?

    是,插入fast bin 链表,结束

  2. 是不是mmap分配出去的内存?

    是,munmap,结束

  3. 与当前被free chunk的前一个相邻堆块是不是freed状态?

是,则两个chunk合并

  1. 与当前被free chunk的后一个相邻堆块是不是top chunk?

    是,则与top chunk合并,结束

  2. 与当前被free chunk的后一个相邻堆块是不是freed状态? 是,则两个chunk合并

  3. 将该chunk链入Unsorted bin

  • malloc顺序
  1. size是否属于fast bin?

    是,寻找对应链表

    若找到,则拆下对应chunk,结束

  2. size是否属于small bin?

    是,寻找对应链表 若找到,则拆下对应chunk,结束

  3. 尝试使用Unsorted bin分配 遍历、分割、拆卸

    从链表尾部开始遍历,若能切分则,切分后剩下仍存在于unsortedbin,结束

    不满足切分则拆链,根据大小放入small bin或large bin

  4. size是否属于large bin?

    是,寻找对应链表

    若找到,则拆下(切分)对应chunk,剩下的加入Unsorted bin,结束

  5. 再次从small bin 和large bin中寻找

    是否存在size(victim) > size(nb)的chunk,若有,则切分,剩下的加入Unsorted bin,结束

  6. 使用top chunk,结束

  7. 扩展堆空间,结束


Tags:
0 comments



本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议CC BY-NC-ND 4.0)进行许可。

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY-NC-ND 4.0).