二进制重排
二进制重排其实并不是什么特别新颖的技术。
目的
二进制重排(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的二进制，可能会存在如下图问题：
如图：如果存在funA->funB->funC->funD的顺序调用过程，则上述调用过程需要4次page faults，且均在非相邻页发生。那么4次page faults就需要4次页中断，以及4次物理页内存的占用；假设程序里存在很多这样的调用问题，那么就会频繁造成mmap的碎片化，并且导致占用的物理页内存更多。
而反之，如果经过了well-layout，如下图：
则可能只占用了1到2页物理内存，只触发了2次page faults，且是相邻页的page faults；
那上述二者有什么差异呢？
| opt\cmp | 页中断 | 物理内存 | 耗时 |
|---|---|---|---|
| well layout | 2 | 2*4kb | 小 |
| less-well layout | 4 | 4*4kb | 更大 |
- 总page faults次数减少50%;
- 总物理内存占用减少50%;
- 相邻页page fault耗时远小于非相邻页；
将以上范围扩大化，对于大型app而言，运行时会涉及到很多函数调用和切换，所以当Layout不当时，以上的数据会影响更大。这就会导致几个问题：
- 前后台切换可能更耗时
- cold launch可能更耗时
- 运行时需要占用更高内存，更容易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
