Forwarded from 刘阳
GitHub
[MEMORY] Switched from a sparse array to a red-black tree by rajdakin · Pull Request #1180 · ptitSeb/box64
This PR switches the way memory permission is tracked, from a sparse array to a red-black tree (self-balancing binary search tree). The notion of hot pages has also been removed.
Performance does n...
Performance does n...
年前在 DynamoRIO 遇到一个比较好玩的东西：
首先 RISC-V 直接跳转的范围只有 +/- 4 KiB，而 AArch64 则是 +/- 32 KiB，所以这个问题算是 RV 独有的。这个范围也直接决定了代码块的最大尺寸，也就是说，RV 中的一个代码块不能超过 4096 个字节（否则块内的直接跳转就有危险了）。
其次，DynamoRIO 有一个叫 clean call 的插桩机制，可以允许用户在任意的两条指令之间插入一个 C 函数的调用。
这个机制的实现方式是，在调用这个 C 函数之前，会保存当前所有寄存器的状态，切换到一个干净的栈上，按照 C 调用约定设置好参数，然后调用 C 函数。函数返回后，再恢复所有的现场，把栈切换回去。
所以大致估算一下，整个 clean call 的主要指令开销就是 context switch 了，32 个整形寄存器 + 32 个浮点寄存器，save + restore 总共是 32 * 2 * 2 * 4 = 512 字节，但是 RV 的 C 扩展刚好提供了
这样一来，在 RISC-V 中每个代码块中最多只能有 15 条指令。
首先 RISC-V 直接跳转的范围只有 +/- 4 KiB，而 AArch64 则是 +/- 32 KiB，所以这个问题算是 RV 独有的。这个范围也直接决定了代码块的最大尺寸，也就是说，RV 中的一个代码块不能超过 4096 个字节（否则块内的直接跳转就有危险了）。
其次，DynamoRIO 有一个叫 clean call 的插桩机制，可以允许用户在任意的两条指令之间插入一个 C 函数的调用。
这个机制的实现方式是，在调用这个 C 函数之前，会保存当前所有寄存器的状态，切换到一个干净的栈上，按照 C 调用约定设置好参数，然后调用 C 函数。函数返回后，再恢复所有的现场，把栈切换回去。
所以大致估算一下，整个 clean call 的主要指令开销就是 context switch 了，32 个整形寄存器 + 32 个浮点寄存器，save + restore 总共是 32 * 2 * 2 * 4 = 512 字节，但是 RV 的 C 扩展刚好提供了
c.ldsp/c.fldsp/c.sdsp/c.fsdsp 指令，所以我们还可以再减个半，也就是 256 字节。这样一来，在 RISC-V 中每个代码块中最多只能有 15 条指令。
box64 中的 CALL/RET 优化
这个优化基于一个假设：当一个 x86 程序执行 CALL 指令的时候，它大概是在做函数的调用；当执行 RET 指令的时候，它大概是在做函数的返回。
正常情况下，模拟 CALL / RET 的开销是比较大的，因为当 RET 的时候，需要从栈上获取到 return 的地址，然后去 jumptable 中查到该地址对应的代码块，再跳转过去。
但如果接受了上面的假设，则在 CALL 的时候可以把 guest x86 的返回地址以及下一个代码块的地址（CALL 指令会结束当前的代码块）同时压到 host 的栈上。在 RET 的时候，就可以检查 %rip 和 host 栈上的 guest x86 addr 是否相等，如果相等，这时候就可以省去了 jumptable 查表的流程了，直接跳转回 CALL 指令保存的下一个代码块的地址即可。
但如果不相等，此时有多种补救措施，box64 选择直接清空当前 jit frame 的栈空间。这个机制是通过在进入 dynarec 的时候，记录一下当时的 host 栈的位置到一个专用寄存器来实现的。
这个优化基于一个假设：当一个 x86 程序执行 CALL 指令的时候，它大概是在做函数的调用；当执行 RET 指令的时候，它大概是在做函数的返回。
正常情况下，模拟 CALL / RET 的开销是比较大的，因为当 RET 的时候，需要从栈上获取到 return 的地址，然后去 jumptable 中查到该地址对应的代码块，再跳转过去。
但如果接受了上面的假设，则在 CALL 的时候可以把 guest x86 的返回地址以及下一个代码块的地址（CALL 指令会结束当前的代码块）同时压到 host 的栈上。在 RET 的时候，就可以检查 %rip 和 host 栈上的 guest x86 addr 是否相等，如果相等，这时候就可以省去了 jumptable 查表的流程了，直接跳转回 CALL 指令保存的下一个代码块的地址即可。
但如果不相等，此时有多种补救措施，box64 选择直接清空当前 jit frame 的栈空间。这个机制是通过在进入 dynarec 的时候，记录一下当时的 host 栈的位置到一个专用寄存器来实现的。
ksco 的工作日志
年前在 DynamoRIO 遇到一个比较好玩的东西： 首先 RISC-V 直接跳转的范围只有 +/- 4 KiB，而 AArch64 则是 +/- 32 KiB，所以这个问题算是 RV 独有的。这个范围也直接决定了代码块的最大尺寸，也就是说，RV 中的一个代码块不能超过 4096 个字节（否则块内的直接跳转就有危险了）。 其次，DynamoRIO 有一个叫 clean call 的插桩机制，可以允许用户在任意的两条指令之间插入一个 C 函数的调用。 这个机制的实现方式是，在调用这个 C 函数之前，会保存…
想法很好，但是实际写代码发现 ldsp/sdsp 的 imm 不够长，迂回了一晚上终于可以工作了，FML
🥰2
ksco 的工作日志
box64 中的 CALL/RET 优化 这个优化基于一个假设：当一个 x86 程序执行 CALL 指令的时候，它大概是在做函数的调用；当执行 RET 指令的时候，它大概是在做函数的返回。 正常情况下，模拟 CALL / RET 的开销是比较大的，因为当 RET 的时候，需要从栈上获取到 return 的地址，然后去 jumptable 中查到该地址对应的代码块，再跳转过去。 但如果接受了上面的假设，则在 CALL 的时候可以把 guest x86 的返回地址以及下一个代码块的地址（CALL 指令会结束当前的代码块）同时压到…
给 RV64 后端加上了这个优化，做了个简单的 7z b，这个优化获得了 50% 以上的性能提升！https://ksco.cool/RdPW