堆相关数据结构_m0

文章目录

堆相关数据结构

堆相关数据结构

参考：

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

https://ctf-wiki.org/pwn/linux/user-mode/heap/ptmalloc2/heap-structure/

1.微观结构

1.1 malloc_chunk

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

1.1.1 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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

每个字段的具体的解释如下

prev_size, 如果该 chunk 的**物理相邻的前一地址 chunk（两个指针的地址差值为前一 chunk 大小）**是空闲的话，那该字段记录的是前一个 chunk 的大小 (包括 chunk 头)。否则，前一chunk的prev_size字段被当前chunk使用，这就是chunk的空间复用。这里的前一 chunk 指的是较低地址的 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|
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1
2
3
4
5
6
7
8
9
10
11
12
13
14

可以发现，如果一个 chunk 处于 free 状态，那么会有两个位置记录其相应的大小

本身的 size 字段会记录，
它后面的 chunk 会记录。

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

size，该 chunk 的大小，大小必须是 2 * SIZE_SZ 的整数倍。如果申请的内存大小不是 2 * SIZE_SZ 的整数倍，会被转换满足大小的最小的 2 * SIZE_SZ 的倍数。32 位系统中，SIZE_SZ 是 4；64 位系统中，SIZE_SZ 是 8。该字段的低三个比特位对 chunk 的大小没有影响，它们从高到低分别表示:
- A: NON_MAIN_ARENA，记录当前 chunk 是否不属于主线程，1 表示不属于，0 表示属于。
- M: IS_MAPPED，记录当前 chunk 是否是由 mmap 分配的。
- P: PREV_INUSE，记录前一个 chunk 块是否被分配。一般来说，堆中第一个被分配的内存块的 size 字段的 P 位都会被设置为 1，以便于防止访问前面的非法内存。当一个 chunk 的 size 的 P 位为 0 时，我们能通过 prev_size 字段来获取上一个 chunk 的大小以及地址。这也方便进行空闲 chunk 之间的合并。
(之所以这三位可以被复用为A、M、P是因为chunk大小为2 * SIZE_SZ的整数倍，比如SIZE_SZ=4，则为8的倍数，而8u=0x1000，因此这三位其实不被需要，那么复用节约空间)
fd，bk。chunk 处于分配状态时，从 fd 字段开始是用户的数据。chunk 空闲时，会被添加到对应的空闲管理链表中，其字段的含义如下
- fd 指向下一个（非物理相邻）空闲的 chunk
- bk 指向上一个（非物理相邻）空闲的 chunk
- 通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理
fd_nextsize， bk_nextsize，也是只有 chunk 空闲的时候才使用，不过其用于较大的 chunk（large chunk）。
- fd_nextsize 指向前一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
- bk_nextsize 指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
- 一般空闲的 large chunk 在 fd 的遍历顺序中，按照由大到小的顺序排列。这样做可以避免在寻找合适 chunk 时挨个遍历。

一个已经分配的 chunk 的样子如下。我们称前两个字段称为 chunk header，后面的部分称为 user data。每次 malloc 申请得到的内存指针，其实指向 user data 的起始处。

无论一个 chunk 的大小如何，处于分配状态还是释放状态，它们都使用一个统一的结构，但是根据是否被释放，它们的表现形式会有所不同。

1.1.2 使用中的chunk

1.1.3 空闲的chunk（被free后）

1.2 bin

1.2.1 概述

我们曾经说过，用户释放掉的 chunk 不会马上归还给系统，ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk。当用户再一次请求分配内存时，ptmalloc 分配器会试图在空闲的 chunk 中挑选一块合适的给用户。这样可以避免频繁的系统调用，降低内存分配的开销。

在具体的实现中，ptmalloc 采用分箱式方法对空闲的 chunk 进行管理。首先，它会根据空闲的 chunk 的大小以及使用状态将 chunk 初步分为 4 类：fast bins，small bins，large bins，unsorted bin。每类中仍然有更细的划分，相似大小的 chunk 会用双向链表链接起来。也就是说，在每类 bin 的内部仍然会有多个互不相关的链表来保存不同大小的 chunk。

对于 small bins，large bins，unsorted bin 来说，ptmalloc 将它们维护在同一个数组中。这些 bin 对应的数据结构在 malloc_state 中，如下：

#define NBINS 128
/* Normal bins packed as described above */
mchunkptr bins[ NBINS * 2 - 2 ];
1
2
3

数组中的 bin 依次如下

第一个为 unsorted bin，字如其面，这里面的 chunk 没有进行排序，存储的 chunk 比较杂。
索引从 2 到 63 的 bin 称为 small bin，同一个 small bin 链表中的 chunk 的大小相同。两个相邻索引的 small bin 链表中的 chunk 大小相差的字节数为 2 个机器字长，即 32 位相差 8 字节，64 位相差 16 字节。
small bins 后面的 bin 被称作 large bins。large bins 中的每一个 bin 都包含一定范围内的 chunk，其中的 chunk 按 fd 指针的顺序从大到小排列。相同大小的 chunk 同样按照最近使用顺序排列。

此外，上述这些 bin 的排布都会遵循一个原则：任意两个物理相邻的空闲 chunk 不能在一起。

需要注意的是，并不是所有的 chunk 被释放后就立即被放到 bin 中。ptmalloc 为了提高分配的速度，会把一些小的 chunk 先放到 fast bins 的容器内。而且，fastbin 容器中的 chunk 的使用标记总是被置位的，所以不满足上面的原则。

图示如下：

bin的通用宏如下：

typedef struct malloc_chunk *mbinptr;

/* addressing -- note that bin_at(0) does not exist */
#define bin_at(m, i)                                                           
    (mbinptr)(((char *) &((m)->bins[ ((i) -1) * 2 ])) -                        
              offsetof(struct malloc_chunk, fd))

/* analog of ++bin */
//获取下一个bin的地址
#define next_bin(b) ((mbinptr)((char *) (b) + (sizeof(mchunkptr) << 1)))

/* Reminders about list directionality within bins */
// 这两个宏可以用来遍历bin
// 获取 bin 的位于链表头的 chunk
#define first(b) ((b)->fd)
// 获取 bin 的位于链表尾的 chunk
#define last(b) ((b)->bk)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.2.2 fast bin

因为经常会有比较小的内存块被释放，但是这样的内存一旦释放后就容易与相邻的chunk合并，不断合并影响了效率。浴室和，专门设计流fast bin，对应的变量就是 malloc state 中的 fastbinsY。

/*
   Fastbins

    An array of lists holding recently freed small chunks.  Fastbins
    are not doubly linked.  It is faster to single-link them, and
    since chunks are never removed from the middles of these lists,
    double linking is not necessary. Also, unlike regular bins, they
    are not even processed in FIFO order (they use faster LIFO) since
    ordering doesn't much matter in the transient contexts in which
    fastbins are normally used.

    Chunks in fastbins keep their inuse bit set, so they cannot
    be consolidated with other free chunks. malloc_consolidate
    releases all chunks in fastbins and consolidates them with
    other free chunks.
 */
typedef struct malloc_chunk *mfastbinptr;

/*
    This is in malloc_state.
    /* Fastbins */
    mfastbinptr fastbinsY[ NFASTBINS ];
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

fast bin有如下的特点：

单向列表
这类bin通常申请和释放的堆块都比较小，所以使用单链表结构，LIFO（后进先出）分配策略。
管理 16、24、32、40、48、56、64 Bytes 的 free chunks（32位下默认，即0x10 ~ 0x40，公差为0x8递增）；64位下，管理的区间为0x20 ~ 0x80，公差为0x10递增。
在fastbinsY数组里按照从小到大的顺序排列。
为了速度，fast bin不会进行合并：其中的 chunk 的 in_use 位（下一个物理相邻的 chunk 的 P 位）总为1

图示如下：

1.2.3 small bin

特点：

bins[2] ~ bins[63]
62 个循环双向链表
FIFO
管理 16、24、32、40、 …… 、504 Bytes 的 free chunks（32位下）
每个链表中存储的 chunk 大小都一致
每次取bin链中的chunk是从bk指向的位置取的，bk指向目前最早释放进来的chunk
small bins中的每个chunk的大小与其所在的bin的index的关系是：chunk_size = 2 * SIZE_T * index：32位对应的SIZE_T为4，64位对应的SIZE_T为8。small bins的index从2到62，比如说对于64位机器，index = 2 ，chunk_size = 32；index = 62 ，chunk_size = 992
对于fastbin和small bin的重合问题的解释：fastbin的chunk在经过consolidate之后都会进入到small bin中的0x20到0x80的对应位置

1.2.4 large bin

特点：

bins[64] ~ bins[126] （一共包含63个bin），32位下，公差32Bytes；64位下，公差64Bytes。
63 个循环双向链表
fd_nextsize和bk_nextsize按照chunk的大小排列，分别指向下一个更大size的chunk和更小的chunk
fd和bk按照chunk的free顺序排列(先来的和main_arena相连)·
FIFO
32位下，管理大于 504 Bytes 的 free chunks；64位下，管理大于1024Bytes的free chunk。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Pn7j72uv-1635679108628)(https://i.loli.net/2021/10/31/ZmSMyYiwfeoNXbR.png)]

1.2.5 unsorted bin

特点：

bins[1]
管理刚刚释放还为分类的 chunk
可以视为空闲 chunk 回归其所属 bin 之前的缓冲区
Unsorted Bin 在使用的过程中，采用的遍历顺序是 FIFO 。
双向循环链表

unsorted bin 中的空闲 chunk 处于乱序状态，主要有两个来源：

当一个较大的 chunk 被分割成两半后，如果剩下的部分大于 MINSIZE，就会被放到 unsorted bin 中。
释放一个不属于 fast bin 的 chunk，并且该 chunk 不和 top chunk 紧邻时，该 chunk 会被首先放到 unsorted bin 中。关于 top chunk 的解释，请参考下面的介绍。（也就是说，释放一个chunk时，如果这个chunk比较大，无法放入fastbin，那么就先存入unsorted bin中）

1.3 Top chunk

程序第一次进行 malloc 的时候，heap 会被分为两块，一块给用户，剩下的那块就是 top chunk。其实，所谓的 top chunk 就是处于当前堆的物理地址最高的 chunk。这个 chunk 不属于任何一个 bin，它的作用在于当所有的 bin 都无法满足用户请求的大小时，如果其大小不小于指定的大小，就进行分配，并将剩下的部分作为新的 top chunk。否则，就对 heap 进行扩展后再进行分配。在 main arena 中通过 sbrk 扩展 heap，而在 thread arena 中通过 mmap 分配新的 heap。

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

初始情况下，我们可以将 unsorted chunk 作为 top chunk。

1.4 last remainder

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

2.宏观结构

2.1 arena

无论是主线程还是新创建的线程，在第一次申请内存时，都会有独立的 arena。

arena数量：

32位，arena数量 = 2 * number of cores
64位，arena数量 = 8 * number of cores

显然，不是每一个线程都能够有独立的arena

main arena与thread arena不同的是，main arena并不在申请的heap中，而是一个全局变量，在libc.so的数据段。

2.2 heap_info

程序刚开始执行时，每个线程是没有 heap 区域的。当其申请内存时，就需要一个结构来记录对应的信息，而 heap_info 的作用就是这个。而且当该 heap 的资源被使用完后，就必须得再次申请内存了。此外，一般申请的 heap 是不连续的，因此需要记录不同 heap 之间的链接结构。（换言之，每一次当前线程申请堆，就会产生一个heap_info来描述当前申请的空间）

该数据结构是专门为从 Memory Mapping Segment 处申请的内存准备的，即为非主线程准备的。

主线程可以通过 sbrk() 函数扩展 program break location 获得（直到触及 Memory Mapping Segment），只有一个 heap，没有 heap_info 数据结构。

2.3 malloc_state

该结构用于管理堆，记录每个 arena 当前申请的内存的具体状态，比如说是否有空闲 chunk，有什么大小的空闲 chunk 等等。无论是 thread arena 还是 main arena，它们都只有一个 malloc state 结构。由于 thread 的 arena 可能有多个，malloc state 结构会在最新申请的 arena 中。

注意，main arena 的 malloc_state 并不是 heap segment 的一部分，而是一个全局变量，存储在 libc.so 的数据段。

图示：

Pandas某列删除None值首先应该判断自己表格中的None的类型处理空值类型的None处理字符串类型的None首先应该判断自己表格中的None的类型表格中None有两种情况：（1）空值类型的None。（2）字符串类型的None，是真实存在的。处理空值类型的Nonedf.dropna(how=\'all\')#删除所有内容均为缺失值的行df.dropna(axis=1) #丢弃有缺失值的列df.dropna(axis=1, how = \'all\') #丢弃所有列中所有值均缺失的列df.drop

堆相关数据结构_m0

文章目录