小小pwn
0%

unsortbins

发表于 分类于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

以下是关于 unsorted bin 的 bin头 的 fd 和 bk 指向的详细解释和结构图，涵盖不同链表情形：

1. 基础规则

在 glibc 的堆管理中：

  • unsorted bin 是双向循环链表，遵循 FIFO（先进先出）规则。
  • bin头 的 fd：指向链表的第一个 chunk（最靠近头部的 chunk）。
  • bin头 的 bk：指向链表的最后一个 chunk（最靠近尾部的 chunk）。
  • 空链表时：fd 和 bk 均指向 bin头 自身。

2. 不同链表情形的结构图

(1) 空链表

当 unsorted bin 为空时，fd 和 bk 均指向自身：

1
2
3
4
5
+-------------------+
|      bin头        |
| fd = &bin头       |
| bk = &bin头       |
+-------------------+

(2) 单个 chunk（chunk1）

插入一个 chunk 后，链表形成循环：

1
2
3
4
5
+-------------------+       +-------------------+
|      bin头        | <---> |      chunk1       |
| fd = chunk1       |       | fd = &bin头        |
| bk = chunk1       |       | bk = &bin头        |
+-------------------+       +-------------------+
  • 逻辑：bin头 的 fd 和 bk 均指向 chunk1，chunk1 的 fd 和 bk 回指 bin头。

(3) 两个 chunk（chunk1 和 chunk2）

插入第二个 chunk 到链表头部后：

1
2
3
4
5
+-------------------+       +-------------------+       +-------------------+
|      bin头        | <---> |      chunk2       | <---> |      chunk1       |
| fd = chunk2       |       | fd = chunk1       |       | fd = &bin头        |
| bk = chunk1       |       | bk = &bin头        |       | bk = chunk2       |
+-------------------+       +-------------------+       +-------------------+

  • 关键指针：

  • bin头.fd 指向第一个 chunk（chunk2）。

  • bin头.bk 指向最后一个 chunk（chunk1）。

  • chunk2.fd 指向 chunk1，chunk2.bk 指向 bin头。

  • chunk1.fd 指向 bin头，chunk1.bk 指向 chunk2。

(4) 三个 chunk（chunk1、chunk2、chunk3）

插入第三个 chunk 到链表头部后：

1
2
3
4
5
+-------------------+       +-------------------+       +-------------------+       +-------------------+
|      bin头        | <---> |      chunk3       | <---> |      chunk2       | <---> |      chunk1       |
| fd = chunk3       |       | fd = chunk2       |       | fd = chunk1       |       | fd = &bin头        |
| bk = chunk1       |       | bk = &bin头        |       | bk = chunk3       |       | bk = chunk2       |
+-------------------+       +-------------------+       +-------------------+       +-------------------+
  • 逻辑：新 chunk 插入链表头部，bin头.bk 始终指向尾部 chunk（chunk1）。

3. 动态操作示例

(1) 插入新 chunk

向空链表插入 chunk1：

1
2
3
4
5
6
7
8
9
[初始] 空链表：
bin头.fd = &bin头
bin头.bk = &bin头

[插入 chunk1]：
bin头.fd = chunk1
bin头.bk = chunk1
chunk1.fd = &bin头
chunk1.bk = &bin头

(2) 从链表中移除 chunk

从两个 chunk 的链表中移除 chunk1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[移除前]：
bin头.fd = chunk2
bin头.bk = chunk1
chunk2.fd = chunk1
chunk2.bk = &bin头
chunk1.fd = &bin头
chunk1.bk = chunk2

[移除 chunk1 后]：
+-------------------+       +-------------------+
|      bin头        | <---> |      chunk2       |
| fd = chunk2       |       | fd = &bin头        |
| bk = chunk2       |       | bk = &bin头        |
+-------------------+       +-------------------+

4. 总结

  • fd 和 bk 的指向规则：
链表情形 bin头.fd 指向 bin头.bk 指向
空链表 &bin头 &bin头
单个 chunk 第一个 chunk 第一个 chunk
多个 chunk 第一个 chunk 最后一个 chunk

  • 链表操作规则：

  • 插入：新 chunk 插入链表头部（bin头.fd 更新为新 chunk）。

  • 移除：从头部或尾部移除 chunk，保持双向链表的完整性。

// 在最后添加