简谈二进制重排

二进制重排

二进制重排其实并不是什么特别新颖的技术。

目的

二进制重排(layout)的目的在于将hot code聚合在一起，即使得最经常执行的代码或最需要关键执行的代码（如启动阶段的顺序调用）聚合在一起，形成一个更紧凑的__TEXT段。

经过Layout后的二进制，其高频或关键代码排列会更紧凑，更利于优化startup启动阶段，以及mmap out/in(前后台切换或函数调用)阶段的速度和内存占用。

• 对于startup启动阶段：

一个well-layout的二进制，如果使得所有启动阶段顺序执行的代码按照执行顺序排列在一起，那么整体page faults频率和次数会减少不少。在iphone 6s上，大概一次page faults平均需要0.2ms或更久。所以对于巨型app而言，更少的page faults会带来更大的启动提升。

• 对于mmap in阶段：

对于less-well layout的二进制，可能会存在如下图问题：

image.png

如图：如果存在funA->funB->funC->funD的顺序调用过程，则上述调用过程需要4次page faults，且均在非相邻页发生。那么4次page faults就需要4次页中断，以及4次物理页内存的占用；假设程序里存在很多这样的调用问题，那么就会频繁造成mmap的碎片化，并且导致占用的物理页内存更多。

而反之，如果经过了well-layout，如下图：

image.png

则可能只占用了1到2页物理内存，只触发了2次page faults，且是相邻页的page faults；

那上述二者有什么差异呢？

opt\cmp	页中断	物理内存	耗时
well layout	2	2*4kb	小
less-well layout	4	4*4kb	更大

1. 总page faults次数减少50%;
2. 总物理内存占用减少50%;
3. 相邻页page fault耗时远小于非相邻页；

将以上范围扩大化，对于大型app而言，运行时会涉及到很多函数调用和切换，所以当Layout不当时，以上的数据会影响更大。这就会导致几个问题：

1. 前后台切换可能更耗时
2. cold launch可能更耗时
3. 运行时需要占用更高内存，更容易OOM

这一点苹果的上古文档Improving Locality of Reference里也有提及。

方案

Layout方式总体而言分为如下几种：

opt\cmp	原理	适用于	实现方
Basic block placement	将hot code排列在一起，relayout代码中低概率执行的代码块	任何代码尤其是很多分支跳转的代码	编译器实现
Basic block alignment	使用nop指令将hot code排列在相同cache line	hot loops循环	编译器实现
Function splitting	将函数中低概率执行的代码抽出来到新的函数,relayout	复杂控制流的函数	编译器实现
Function grouping	将hot function紧凑排列在一起	small hot function	链接器实现

对于app而言，最简单可行的方案是使用linker链接器提供的function grouping来实现重排。其它都是编译器内部做的优化。

对于lldb而言，可采取的方案是基于linker提供的-order_file选项。

-order_file

-order_file提供一个参数，该参数为一个文件路径，对应文件的格式要求如下：

• 换行符分隔

每一行是一个符号，符号间以换行符分隔

• 注释以#开头

#text这是一行注释

• 默认为函数符号名

_ZThn32_N5AISDK13AIPushManagerD0Ev
-[FMResultSet setStatement:]

• 可指定object file解决符号冲突

FileModule.o:+[FileModule load]
libhippy.a(RCTEventObserverModule.o):+[RCTEventObserverModule load]

-order_file在当前llvm上只支持代码段layout，即只支持指定函数符号来进行重排。
而在gdb上则还有-section order等选项可配置特定section的符号重排。

备注：虽然man ld文档里说的-order_file支持literal string重排，但经过测试以及查看llvm源码发现，目前版本的llvm并不支持。

其它方式

-order_file在iOS上只支持__text代码段的重排，而对于其余section，如__cstring,__ustring,__const,__objc等都是不支持重排的。
如果想完成上述重排，最好的方式是编译重写一个linker，当然也可以利用默认linker的order规则来尝试完成。我们也是基于默认order规则完成的字符串重排，但并没有什么卵用，因为字符串重排提升不是很明显。

目前看，在iOS上除了基于-order_file的代码段重排外，基本没有别的方式可行了。当然另外再自己改llvm编译当我没说。

trace

基于-order_file完成Machine Code Layout，我们需要获取到所有关键的symbol：即函数符号；
获取函数符号的方式即trace；
几种trace方式如下：

opt\cmp	原理	优点	缺点	举例
编译插桩	编译阶段结合源码插入桩代码记录	可实现对任何函数调用的trace	需要源码构建，对于链接的二进制.a无效	XCode PGO
运行时插桩	hook或动态插桩来记录	不需要源码，可解决二进制.a问题	hook无法解决c/c++问题，dtrace无法解决真机运行问题	dtrace

基于上述考量，我们是采取编译插桩+运行时trace的结合方式，来生成更好的order_file。

编译插桩的方式可以参考FB的方案Performance Scale 2019，或者杨帝写的 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。

为什么没用descriptor->reserved这个64位数？因为发现对于globalBlock这个reserved不能被使用，使用后会导致block可能执行多次或者hook失效。

• load/mod init

所有load存在__objc_nlclasslist以及__objc_nlcatlist里，基于此去插桩，mod_init也同理。

trace string

前面提到我们也完成了字符串重排，这里也简略介绍下原理：
字符串重排要解决的是__cstring和__ustring的重排问题。__cstring是UTF8 C string。__ustring是unicode string；
他们的本质都是一个如下的结构体：

struct __builtin_CFString {
    void *isa; // point to __CFConstantStringClassReference
    long flags;
    const char *str;
    long length;
};

在运行时他们对应的是__NSCFConstantString这个私有类，也就是只要hook了这个类的所有消息转发过程，即可完成对字符串的trace过程。
trace完毕后就利用linker的默认排列策略来去重排字符串即可。

接入

话不多说，我们结合自己的使用场景，完善了一个sdk，感兴趣的同学可以接入使用。完成生成order_file的步骤，当然它也还支持生成order_string。

demo和sdk见 https://github.com/rhythmkay/PGOAnalyzer

结语

Machine Code Layout并不是什么特别新鲜的东西，它的优化效果是有的，但在移动端上并不会有特别特别大的效果提升，但本着能提升一点是一点，所以还是有意义的，尤其是启动优化，的确还是有些提升效果的。
苹果的那篇上古文档Improving Locality of Reference，里面的很多概念和内容其实还是很有价值的，只不过无法使用。

总之，整个mach-o二进制理论上可以随意重排，想怎么来都可以做到。不外乎要么自己编译改linker，要么利用linker的默认排列，要么就是基于linker已有的order_file选项来。

另外对二进制重排理论感兴趣的同学，可以拜读下facebook的一篇论文 Optimizing Function Placement for
Large-Scale Data-Center Applications