姬長信(Redy)

简谈二进制重排

#### 目的 二进制重排的目的在于将hot code聚合在一起/uff0c即使得最经常执行的代码或最需要关键执行的代码/uff08如启动阶段的顺序调用/uff09聚合在一起/uff0c形成一个更紧凑的__TEXT段。 经过重排后的二进制/uff0c其高频或关键代码排列会更紧凑/uff0c更利于优化启动阶段/uff0c以及mmap out/in(前后台切换或函数调用)阶段的速度和内存占用。 - 对于startup启动阶段/uff1a 一个well-layout的二进制/uff0c如果使得所有启动阶段顺序执行的代码按照执行顺序排列在一起/uff0c那么整体page faults频率和次数会减少不少。在iphone 6s上/uff0c大概一次page faults平均需要0.2ms或更久。所以对于大型app而言/uff0c更少的page faults会带来更大的启动提升。 - 对于mmap in阶段/uff1a 对于less-well layout的二进制/uff0c可能会存在如下图问题/uff1a ![less-well layout](https://cocosbcx.oss-cn-beijing.aliyuncs.com/article/201909181700592592 "less-well layout") 如图/uff1a如果存在funA->funB->funC->funD的顺序调用过程/uff0c则上述调用过程需要4次page faults/uff0c且均在非相邻页发生。那么4次page faults就需要4次页中断/uff0c以及4次物理页内存的占用/uff1b假设程序里存在很多这样的调用问题/uff0c那么就会频繁造成mmap的碎片化/uff0c并且导致占用的物理页内存更多。 而反之/uff0c如果经过了well-layout/uff0c如下图/uff1a ![well layout](https://cocosbcx.oss-cn-beijing.aliyuncs.com/article/201909181701224708 "well layout") 则可能只占用了1到2页物理内存/uff0c只触发了2次page faults/uff0c且是相邻页的page faults/uff1b 那上述二者有什么差异呢/uff1f opt/cmp | 页中断 | 物理内存 | 耗时 --- | --- | --- | --- well layout | 2 | 2*4kb | 小 less-well layout | 4 | 4*4kb | 更大 > 1. 总page faults次数减少50%; > 2. 总物理内存占用减少50%; > 3. 相邻页page fault耗时远小于非相邻页/uff1b 将以上范围扩大化/uff0c对于大型app而言/uff0c运行时会涉及到很多函数调用和切换/uff0c所以当排列不当时/uff0c以上的数据会影响更大。这就会导致几个问题/uff1a 1. 前后台切换可能更耗时 2. cold launch可能更耗时 3. 运行时需要占用更高内存/uff0c更容易OOM 这一点苹果的上古文档[Improving Locality of Reference](https://developer.apple.com/library/archive/documentation/Performance/Conceptual/CodeFootprint/Articles/ImprovingLocality.html#//apple_ref/doc/uid/20001862-103584)里也有提及。 ### 方案 排列的方式总体而言分为如下几种/uff1a opt/cmp | 原理 | 适用于 | 实现方 --- | --- | --- | --- Basic block placement | 将hot code排列在一起/uff0crelayout代码中低概率执行的代码块 | 任何代码尤其是很多分支跳转的代码 | 编译器实现 Basic block alignment | 使用nop指令将hot code排列在相同cache line | hot loops循环 | 编译器实现 Function splitting | 将函数中低概率执行的代码抽出来到新的函数,relayout | 复杂控制流的函数 | 编译器实现 Function grouping | 将hot function紧凑排列在一起 | small hot function | 链接器实现 对于app而言/uff0c最简单可行的方案是使用linker链接器提供的function grouping来实现重排。其它都是编译器内部做的优化。 对于lldb而言/uff0c可采取的方案是基于linker提供的-order_file选项。 #### -order_file -order_file提供一个参数/uff0c该参数为一个文件路径/uff0c对应文件的格式要求如下/uff1a - 换行符分隔 每一行是一个符号/uff0c符号间以换行符分隔 - 注释以#开头 ``` #text这是一行注释 ``` - 默认为函数符号名 ``` _ZThn32_N5MTSDK13ADPushManagerD0Ev -[FMResultSet setStatement:] ``` - 可指定object file解决符号冲突 ``` FileModule.o:+[FileModule load] librn.a(RCTEventObserver.o):+[RCTEventObserver load] ``` -order_file在当前llvm上只支持代码段layout/uff0c即只支持指定函数符号来进行重排。 而在gdb上则还有-section order等选项可配置特定section的符号重排。 > 备注/uff1a虽然man ld文档里说的-order_file支持literal string重排/uff0c但经过测试以及查看llvm源码发现/uff0c目前版本的llvm并不支持。 #### 其它方式 -order_file在iOS上只支持/_/_text代码段的重排/uff0c而对于其余section/uff0c如/_/_cstring,/_/_ustring,/_/_const,/_/_objc等都是不支持重排的。 如果想完成上述重排/uff0c最好的方式是编译重写一个linker/uff0c当然也可以利用默认linker的order规则来尝试完成。我们也是基于默认order规则完成的字符串重排/uff0c不过由于字符串一般都比较小/uff0c所以字符串重排提升不是很明显。 目前看/uff0c在iOS上除了基于-order_file的代码段重排外/uff0c基本没有别的方式可行了。当然另外再自己改llvm编译当就另当别论了。 ### trace 基于-order_file完成代码段重排/uff0c我们需要获取到所有关键的symbol/uff1a即函数符号/uff1b 获取函数符号的方式即trace/uff1b 几种trace方式如下/uff1a opt/cmp | 原理 | 优点 | 缺点 | 举例 --- | --- | --- | --- | --- 编译插桩 | 编译阶段结合源码插入桩代码记录 | 可实现对任何函数调用的trace | 需要源码构建/uff0c对于链接的二进制.a无效 | XCode PGO 运行时插桩 | hook或动态插桩来记录 | 不需要源码/uff0c可解决二进制.a问题| hook无法解决c/c++问题/uff0cdtrace无法解决真机运行问题 | dtrace 基于上述考量/uff0c我们是采取编译插桩+运行时trace的结合方式/uff0c来生成更好的order_file。 编译插桩的方式可以参考FB的方案[Performance Scale 2019](https://www.facebook.com/atscaleevents/videos/performance-scale-2019-improving-ios-startup-performance-with-binary-layout-opti/664302790740440/)/uff0c或者杨帝写的 [yulingtianxia/AppOrderFiles](https://github.com/yulingtianxia/AppOrderFiles) 更简单快速一些。 运行时trace则更多涉及到msgsend hook,block hook,mod_init stub,load stub,initialize hook的一些基础objc知识。 #### trace objc - msgSend 所有消息转发基于msgSend所以hook msgSend以及msgSendSuper2即可 - block block的本质是如下结构体 ``` struct Block_descriptor_1 { uintptr_t reserved; uintptr_t size; }; typedef void(*BlockInvokeFunction)(void *, ...); struct Block_layout { void *isa; volatile int32_t flags; // contains ref count int32_t reserved; BlockInvokeFunction invoke; struct Block_descriptor_1 *descriptor; // imported variables }; ``` 因此借助于其int32_t reserved我们完成了block hook。 - load/mod init 所有load存在/_/_objc_nlclasslist以及 /_objc_nlcatlist里/uff0c基于此去插桩. /_mod_init也同理。 #### trace string 前面提到我们也完成了字符串重排/uff0c这里也简略介绍下原理/uff1a 字符串重排要解决的是__cstring和__ustring的重排问题。__cstring是UTF8 C string。__ustring是unicode string/uff1b 他们的本质都是一个如下的结构体/uff1a ``` struct __builtin_CFString { void *isa; long flags; const char *str; long length; }; ``` 在运行时他们对应的是__NSCFConstantString这个私有类/uff0c也就是只要hook了这个类的所有消息转发过程/uff0c即可完成对字符串的trace过程。 ### demo 话不多说/uff0c我们结合自己的使用场景/uff0c完善了一个sdk/uff0c感兴趣的可以了解一下。当然它也还支持生成order_string。 demo和sdk见 https://github.com/rhythmkay/PGOAnalyzer ### 结语 二进制重排并不是什么特别新鲜的东西/uff0cXCode早就提供了PGO/uff0c同样Android 8.0开始也提供了DexLayout/uff0c本质都是对hot code做聚合排列。重排后的优化效果是有的/uff0c但在移动端上并不会有特别特别大的效果提升。本着能提升一点是一点/uff0c所以还是有意义的/uff0c尤其是启动优化/uff0c的确还是有些提升效果的。 苹果的那篇上古文档Improving Locality of Reference/uff0c里面的很多概念和内容其实还是很有价值的/uff0c只不过其提供的工具则无法使用。 总之/uff0c整个mach-o二进制理论上可以随意重排/uff0c想怎么来都可以做到。不外乎要么自己编译改linker/uff0c要么利用linker的默认排列/uff0c要么就是基于linker已有的order_file选项来。 另外对二进制重排理论感兴趣的同学/uff0c可以拜读下facebook的一篇论文 [Optimizing Function Placement for Large-Scale Data-Center Applications](https://research.fb.com/wp-content/uploads/2017/01/cgo2017-hfsort-final1.pdf) ### 参考 [Machine code layout optimizations](https://easyperf.net/blog/2019/03/27/Machine-code-layout-optimizatoins) [Improving Locality of Reference](https://developer.apple.com/library/archive/documentation/Performance/Conceptual/CodeFootprint/Articles/ImprovingLocality.html#//apple_ref/doc/uid/20001862-103584) [Optimizing Function Placement for Large-Scale Data-Center Applications](https://research.fb.com/wp-content/uploads/2017/01/cgo2017-hfsort-final1.pdf "Optimizing Function Placement for Large-Scale Data-Center Applications")