Linux教程

Linux堆管理基础知识(二)- 数据结构

本文主要是介绍Linux堆管理基础知识(二)- 数据结构,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • Arena
  • Bins
    • Fast Bin
    • Unsorted Bin
    • Small Bin
    • Large Bin
  • Top chunk
  • Last Reminder
  • Refence

Arena

glibc的malloc源码中涉及三种数据结构:Arena、Heap、Chunk ,分别对应结构体malloc_state、heap_info、malloc_chunk。具体的对应关系如下图所示

在这里插入图片描述

  • Thread - Arena : 一个Arena对应多个线程Thread。即每个线程都有一个Arena,但是有可能多个线程共用一个Arena。每个Arena都包含一个malloc_state结构体,保存bins, top chunk, Last reminder chunk等信息。
  • Arena - Heap:一个Arena可能拥有多个heap。Arena开始的时候只有一个heap,但是当这个heap的空间用尽时,就需要获取新的heap。
  • Heap - Chunk:一个Heap根据用户的请求会划分为多个chunk,每个chunk拥有自己的header - malloc_chunk。

需要注意的是,Main Arena只有一个heap,因此没有heap_info结构。当main arena用尽空间后,会扩展当前的heap空间。此外,Main Arean的Arena header并不是heap segment的一部分,而作为全局变量储存在libc.so的数据段中。

下图是只有一个heap时,主线程和线程的堆结构示意图,左图是Main Arena,右图是Threa Arena。堆是从低地址向高地址增长的,可以看到每一个malloc_chunk上面都跟着一个chunk。同时Main Arena没有heap_info和malloc_state的结构。

在这里插入图片描述

下图是存在多个heap的thread Arena的情况。可以看到每一个heap都一个heap header(heap_info),但是只有最初的heap拥有arena header

在这里插入图片描述

当线程申请内存时,就创建一个Arena。主线程有自己独立的Arena,叫做main arena,但不是每一个线程都有独立的Arena。

Arena的个数取决于cpu核的个数

For 32 bit systems:
     Number of arena = 2 * number of cores + main arena
For 64 bit systems:
     Number of arena = 8 * number of cores + main arena

Q: 多线程时,Arena是怎样分配的呢?

A: 假设一个单核的cpu上运行着一个拥有4个线程(main thread + user thread )的32位程序。

  • 当主线程第一次调用malloc时,将创建main arena;
  • 当thread 1和thread 2第一次调用malloc时,它们将分别创建一个arena,即Arena-1 和 Arena-2;
  • 当thread 3第一次调用malloc时,已经不能再创建新的arena,因此需要复用已存在的arena;
  • 详细的复用规则参考源码 reused_arena

Bins

bins是用来索引空闲chunk的结构。根据chunk大小,可以分为四类不同的Bin。

  • Fast Bin
  • Unsorted Bin
  • Small Bin
  • Large Bin

数据结构中包含如下两类:

  • fastbinsY: 用来索引fast bin的数组;

    typedef struct malloc_chunk *mfastbinptr;
    
    mfastbinptr fastbinsY[]; // Array of pointers to chunks
    
  • bins: 一个用来索引unsorted, small, large三种bins的数组。总长度为126

    • bins[1] : unsorted bin;
    • Bins[2] - bins[63]: small bin;
    • Bins[64] - bins[126]: Large bin
    typedef struct malloc_chunk* mchunkptr;
    
    mchunkptr bins[]; // Array of pointers to chunks
    

Fast Bin

Fastbin是“An array of lists holding recently freed small chunks”。

默认情况下(32 位系统为例), fastbin 中默认支持最大的 chunk 的数据空间大小为 64 字节。但是其可以支持的 chunk 的数据空间最大为 80 字节。

  • 数量:包含10个bins。每个bin都是一个单链表(只使用fd指针),链表的入队出队都在表头进行,所以是LIFO。如下图所示

    在这里插入图片描述

  • 大小:每个bin都包含同样大小的chunk,fastbinsY[0]储存数据空间大小为0 bytes的chunk,fastbinsY[1]储存大小为8 bytes的chunk,以此类推,每次增加8个byte。

    注意,chunk的数据空间是指用户可以利用来储存数据的空间,总是小于chunk的实际大小的。

  • malloc初始化时,最大的fast bin大小被设置为64byte,而不是80 bytes。

  • 不合并:两个freed chunk可以相邻。与malloc_chunk学习时的说明有所冲突,主要是fast bin更注重分配的速度。

  • malloc(fast chunk):用户通过malloc请求的大小属于fast chunk的大小范围

    • 在初始化的时候fast bin支持的最大chunk大小和所有的bins都是空的。所以一开始即使申请的大小时fast chunk的范围内,也不会交由fast bin处理,而是交由small bin,如果small bin也为空的话,交由unsorted bin处理。
    • 当fast bin不为空时,会根据用户申请的空间大小计算索引,去对应的bin中获取chunk
    • 第一个索引到的chunk会在bin中被移除,并返回给用户
  • Free(fast chunk):用户通过free释放的大小属于fast chunk的大小范围

    • fast bin根据用户释放的空间大小计算索引,
    • 释放的chunk会被加入bin中。

Unsorted Bin

当small chunk和large chunk被释放的时候,这些chunk并不会添加到对应的small bin或者large bin中,而是被添加到unsroted bin中。这是符合局部性原则的。

  • 数量:只有一个bin。bin是双向链表,采用FIFO的规则。

在这里插入图片描述

Small Bin

chunk大小小于512byte的属于small chunk,

chunk大小和bin index的换算关系如下:chunk_size = 2 * SIZE_SZ * index。具体如下

下标SIZE_SZ=4(32 位)SIZE_SZ=8(64 位)
21632
32448
43264
54080
n2 * 4 * n2 * 8 * n
635041008
  • 合并:两个空闲的chunk相邻时要合并成一个空闲的chunk。

    这里的相邻指的是在链表中相邻吗?还是在物理地址上相邻。

  • malloc(small chunk):

    • 类似于fast bins,最初所有的small bin都是空的,因此在对这些small bin完成初始化之前,即使用户请求的内存大小属于small chunk也不会交由small bin进行处理,而是交由unsorted bin处理,如果unsorted bin也不能处理的话,glibc malloc就依次遍历后续的所有bins,找出第一个满足要求的bin,如果所有的bin都不满足的话,就转而使用top chunk,如果top chunk大小不够,那么就扩充top chunk,这样就一定能满足需求了
    • 之后再调用时,如果small bin不为空,则从small bin中获取chunk
  • free(small chunk):

    • 释放small chunk时,先检查物理地址上相邻的chunk,若相邻的chunk为未分配状态,则合并这些chunk。合并的时候需要先把这些chunk从对应的链上unlink,之后把合并后chunk添加到unsorted bin中

Large Bin

chunk大小大于512byte的属于large chunk,large bins 中一共包括 63 个 bin,每个 bin 中的 chunk 的大小不一致,而是处于一定区间范围内。此外,这 63 个 bin 被分成了 6 组,每组 bin 中的 chunk 大小之间的公差一致,具体如下:

数量公差
13264B
216512B
384096B
4432768B
52262144B
61不限制

为了增加内存管理的效率,large bin中的链表采用降序排列

  • malloc(large chunk)
    • 初始化完成之前的操作类似于small bin
    • 初始化完成之后调用malloc(large chunk)时,首先确定用户请求的大小属于哪一个large bin,然后判断该large bin中最大的chunk的size是否大于用户请求的size(只需要对比链表中front end的size即可)。
    • 如果最大的chunk大于用户请求的空间,就从最小的(rear end)开始遍历该large bin,找到第一个size相等或接近的chunk,分配给用户。如果该chunk大于用户请求的大小的话,就将该chunk拆分为两个chunk:前者返回给用户,且size等同于用户请求的size;多出来的部分做为一个新的chunk,即remainder chunk,添加到unsorted bin中。
    • 如果bin中最大的chunk小于用户请求的空间,尝试通过binmaps寻找下一个不为空的large bin,知道找到满足要求的bin。
  • free(large chunk):类似samll chunk的释放。

Top chunk

在Arena的图中,可以看到靠近内存上边界的chunk叫做top chunk。Top chunk不属于任何bin。它的作用是满足bin中没有空闲的chunk时,用户申请内存空间的请求。

  • 当top chunk的大小大于用户申请的空间时,它将拆分为两个chunk
    • User chunk (大小等于用户申请的大小)
    • Remainder chunk (剩余的空间),这部分chunk将成为新的top chunk
  • 当top chunk无法满足用户申请的空间时,使用sbrk(main arena)或mmap(thread arena)扩展top chunk的空间。

需要注意的是,top chunk 的 prev_inuse 比特位始终为 1,否则其前面的 chunk 就会被合并到 top chunk 中。

Last Reminder

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

Refence

https://heap-exploitation.dhavalkapil.com

https://zhuanlan.zhihu.com/p/24753861

https://zhuanlan.zhihu.com/p/185826940

https://www.cnblogs.com/alisecurity/p/5520847.html

https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/comment-page-1/

这篇关于Linux堆管理基础知识(二)- 数据结构的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!