本文主要是介绍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。具体如下

• 合并：两个空闲的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 大小之间的公差一致，具体如下：

为了增加内存管理的效率，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堆管理基础知识（二）- 数据结构的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！