抖音研发实践：基于二进制文件重排的解决方案 APP启动速度提升超15%
原创 Leo 字节跳动技术团队 2019-08-09
https://mp.weixin.qq.com/s/Drmmx5JtjG3UtTFksL6Q8Q
背景
启动是App给用户的第一印象，对用户体验至关重要。抖音的业务迭代迅速，如果放任不管，启动速度会一点点劣化。为此抖音iOS客户端团队做了大量优化工作，除了传统的修改业务代码方式，我们还做了些开拓性的探索，发现修改代码在二进制文件的布局可以提高启动性能，方案落地后在抖音上启动速度提高了约15%。
本文从原理出发，介绍了我们是如何通过静态扫描和运行时trace找到启动时候调用的函数，然后修改编译参数完成二进制文件的重新排布。
原理
Page Fault
进程如果能直接访问物理内存无疑是很不安全的，所以操作系统在物理内存的上又建立了一层虚拟内存。为了提高效率和方便管理，又对虚拟内存和物理内存又进行分页（Page）。当进程访问一个虚拟内存Page而对应的物理内存却不存在时，会触发一次缺页中断（Page Fault），分配物理内存，有需要的话会从磁盘mmap读人数据。
通过App Store渠道分发的App，Page Fault还会进行签名验证，所以一次Page Fault的耗时比想象的要多：
分配物理内存 磁盘IO 验签
重排
编译器在生成二进制代码的时候，默认按照链接的Object File(.o)顺序写文件，按照Object File内部的函数顺序写函数。
静态库文件.a就是一组.o文件的ar包，可以用
ar -t查看.a包含的所有.o。
简化问题：假设我们只有两个page：page1/page2，其中绿色的method1和method3启动时候需要调用，为了执行对应的代码，系统必须进行两个Page Fault。
但如果我们把method1和method3排布到一起，那么只需要一个Page Fault即可，这就是二进制文件重排的核心原理
我们的经验是优化一个Page Fault，启动速度提升0.6~0.8ms。
核心问题
为了完成重排，有以下几个问题要解决：
重排效果怎么样 - 获取启动阶段的page fault次数
重排成功了没 - 拿到当前二进制的函数布局
如何重排 - 让链接器按照指定顺序生成Mach-O
重排的内容 - 获取启动时候用到的函数
System Trace
日常开发中性能分析是用最多的工具无疑是Time Profiler，但Time Profiler是基于采样的，并且只能统计线程实际在运行的时间，而发生Page Fault的时候线程是被blocked，所以我们需要用一个不常用但功能却很强大的工具：System Trace。
选中主线程，在VM Activity中的File Backed Page In次数就是Page Fault次数，并且双击还能按时序看到引起Page Fault的堆栈：
signpost
现在我们在Instrument中已经能拿到某个时间段的Page In次数，那么如何和启动映射起来呢？
我们的答案是：os_signpost。
os_signpost是iOS 12开始引入的一组API，可以在Instruments绘制一个时间段，代码也很简单：
1os_log_t logger = os_log_create("com.bytedance.tiktok", "performance");
2os_signpost_id_t signPostId = os_signpost_id_make_with_pointer(logger,sign);
3//标记时间段开始
4os_signpost_interval_begin(logger, signPostId, "Launch","%{public}s", "");
5//标记结束
6os_signpost_interval_end(logger, signPostId, "Launch");通常可以把启动分为四个阶段处理：
load -> C++静态初始化 -> didFinishLaunch -> UISetup
有多少个Mach-O，就会有多少个Load和C++静态初始化阶段，用signpost相关API对对应阶段打点，方便跟踪每个阶段的优化效果。
Linkmap
Linkmap是iOS编译过程的中间产物，记录了二进制文件的布局，需要在Xcode的Build Settings里开启Write Link Map File：
比如以下是一个单页面Demo项目的linkmap。
linkmap主要包括三大部分：
Object Files 生成二进制用到的link单元的路径和文件编号
Sections 记录Mach-O每个Segment/section的地址范围
Symbols 按顺序记录每个符号的地址范围
ld
Xcode使用的链接器件是ld，ld有一个不常用的参数-order_file，通过man ld可以看到详细文档：
Alters the order in which functions and data are laid out. For each section in the output file, any symbol in that section that are specified in the order file file is moved to the start of its section and laid out in the same order as in the order file file.
可以看到，order_file中的符号会按照顺序排列在对应section的开始，完美的满足了我们的需求。
Xcode的GUI也提供了order_file选项：
如果order_file中的符号实际不存在会怎么样呢？
ld会忽略这些符号，如果提供了link选项-order_file_statistics，会以warning的形式把这些没找到的符号打印在日志里。
获得符号
还剩下最后一个，也是最核心的一个问题，获取启动时候用到的函数符号。
我们首先排除了解析Instruments(Time Profiler/System Trace) trace文件方案，因为他们都是基于特定场景采样的，大多数符号获取不到。最后选择了静态扫描+运行时Trace结合的解决方案。
Load
Objective C的符号名是+-[Class_name(category_name) method:name:]，其中+表示类方法，-表示实例方法。
刚刚提到linkmap里记录了所有的符号名，所以只要扫一遍linkmap的__TEXT,__text，正则匹配("^\+\[.*\ load\]$")既可以拿到所有的load方法符号。
C++静态初始化
C++并不像Objective C方法那样，大部分方法调用编译后都是objc_msgSend，也就没有一个入口函数去运行时hook。
但是可以用-finstrument-functions在编译期插桩“hook”，但由于抖音的很多依赖由其他团队提供静态库，这套方案需要修改依赖的构建过程。二进制文件重排在没有业界经验可供参考，不确定收益的情况下，选择了并不完美但成本最低的静态扫描方案。
1. 扫描linkmap的__DATA，__mod_init_func，这个section存储了包含C++静态初始化方法的文件，获得文件号[ 5]。
1//__mod_init_func
20x100008060 0x00000008 [ 5] ltmp7
3//[ 5]对应的文件
4[ 5] .../Build/Products/Debug-iphoneos/libStaticLibrary.a(StaticLibrary.o)2. 通过文件号，解压出.o。
1➜ lipo libStaticLibrary.a -thin arm64 -output arm64.a
2➜ ar -x arm64.a StaticLibrary.o3. 通过.o，获得静态初始化的符号名_demo_constructor。
1➜ objdump -r -section=__mod_init_func StaticLibrary.o
2
3StaticLibrary.o: file format Mach-O arm64
4
5RELOCATION RECORDS FOR [__mod_init_func]:
60000000000000000 ARM64_RELOC_UNSIGNED _demo_constructor4. 通过符号名，文件号，在linkmap中找到符号在二进制中的范围：
10x100004A30 0x0000001C [ 5] _demo_constructor5. 通过起始地址，对代码进行反汇编：
1➜ objdump -d --start-address=0x100004A30 --stop-address=0x100004A4B demo_arm64
2
3_demo_constructor:
4100004a30: fd 7b bf a9 stp x29, x30, [sp, #-16]!
5100004a34: fd 03 00 91 mov x29, sp
6100004a38: 20 0c 80 52 mov w0, #97
7100004a3c: da 06 00 94 bl #7016
8100004a40: 40 0c 80 52 mov w0, #98
9100004a44: fd 7b c1 a8 ldp x29, x30, [sp], #16
10100004a48: d7 06 00 14 b #7004
6. 通过扫描bl指令扫描子程序调用，子程序在二进制的开始地址为：100004a3c +1b68（对应十进制的7016）。
1100004a3c: da 06 00 94 bl #7016
7. 通过开始地址，可以找到符号名和结束地址，然后重复5～7，递归的找到所有的子程序调用的函数符号。
小坑
STL里会针对string生成初始化函数，这样会导致多个.o里存在同名的符号，例如：
1__ZNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEC1IDnEEPKc类似这样的重复符号的情况在C++里有很多，所以C/C++符号在order_file里要带着所在的.o信息：
1//order_file.txt
2libDemoLibrary.a(object.o):__GLOBAL__sub_I_demo_file.cpp局限性
branch系列汇编指令除了bl/b，还有br/blr，即通过寄存器的间接子程序调用，静态扫描无法覆盖到这种情况。
Local符号
在做C++静态初始化扫描的时候，发现扫描出了很多类似l002的符号。经过一番调研，发现是依赖方输出静态库的时候裁剪了local符号。导致__GLOBAL__sub_I_demo_file.cpp 变成了l002。
需要静态库出包的时候保留local符号，CI脚本不要执行strip -x，同时Xcode对应target的Strip Style修改为Debugging symbol：
Objective C方法
绝大部分Objective C的方法在编译后会走objc_msgSend，所以通过fishhook(https://github.com/facebook/fishhook) hook这一个C函数即可获得Objective C符号。由于objc_msgSend是变长参数，所以hook代码需要用汇编来实现：
1//代码参考InspectiveC
2__attribute__((__naked__))
3static void hook_Objc_msgSend() {
4 save()
5 __asm volatile ("mov x2, lr\n");
6 __asm volatile ("mov x3, x4\n");
7 call(blr, &before_objc_msgSend)
8 load()
9 call(blr, orig_objc_msgSend)
10 save()
11 call(blr, &after_objc_msgSend)
12 __asm volatile ("mov lr, x0\n");
13 load()
14 ret()
15}子程序调用时候要保存和恢复参数寄存器，所以save和load分别对x0~x9, q0~q9入栈/出栈。call则通过寄存器来间接调用函数：
1#define save() \
2__asm volatile ( \
3"stp q6, q7, [sp, #-32]!\n"\
4...
5
6#define load() \
7__asm volatile ( \
8"ldp x0, x1, [sp], #16\n" \
9...
10
11#define call(b, value) \
12__asm volatile ("stp x8, x9, [sp, #-16]!\n"); \
13__asm volatile ("mov x12, %0\n" :: "r"(value)); \
14__asm volatile ("ldp x8, x9, [sp], #16\n"); \
15__asm volatile (#b " x12\n");在before_objc_msgSend中用栈保存lr，在after_objc_msgSend恢复lr。由于要生成trace文件，为了降低文件的大小，直接写入的是函数地址，且只有当前可执行文件的Mach-O(app和动态库)代码段才会写入：
iOS中，由于ALSR(https://en.wikipedia.org/wiki/Address_space_layout_randomization)的存在，在写入之前需要先减去偏移量slide：
1IMP imp = (IMP)class_getMethodImplementation(object_getClass(self), _cmd);
2unsigned long imppos = (unsigned long)imp;
3unsigned long addr = immpos - macho_slide获取一个二进制的__text段地址范围：
1unsigned long size = 0;
2unsigned long start = (unsigned long)getsectiondata(mhp, "__TEXT", "__text", &size);
3unsigned long end = start + size;获取到函数地址后，反查linkmap既可找到方法的符号名。
Block
block是一种特殊的单元，block在编译后的函数体是一个C函数，在调用的时候直接通过指针调用，并不走objc_msgSend，所以需要单独hook。
通过Block的源码可以看到block的内存布局如下：
1struct Block_layout {
2 void *isa;
3 int32_t flags; // contains ref count
4 int32_t reserved;
5 void *invoke;
6 struct Block_descriptor1 *descriptor;
7};
8struct Block_descriptor1 {
9 uintptr_t reserved;
10 uintptr_t size;
11};其中invoke就是函数的指针，hook思路是将invoke替换为自定义实现，然后在reserved保存为原始实现。
1//参考 https://github.com/youngsoft/YSBlockHook
2if (layout->descriptor != NULL && layout->descriptor->reserved == NULL)
3{
4 if (layout->invoke != (void *)hook_block_envoke)
5 {
6 layout->descriptor->reserved = layout->invoke;
7 layout->invoke = (void *)hook_block_envoke;
8 }
9}由于block对应的函数签名不一样，所以这里仍然采用汇编来实现hook_block_envoke：
1__attribute__((__naked__))
2static void hook_block_envoke() {
3 save()
4 __asm volatile ("mov x1, lr\n");
5 call(blr, &before_block_hook);
6 __asm volatile ("mov lr, x0\n");
7 load()
8 //调用原始的invoke，即resvered存储的地址
9 __asm volatile ("ldr x12, [x0, #24]\n");
10 __asm volatile ("ldr x12, [x12]\n");
11 __asm volatile ("br x12\n");
12}在before_block_hook中获得函数地址（同样要减去slide）。
1intptr_t before_block_hook(id block,intptr_t lr)
2{
3 Block_layout * layout = (Block_layout *)block;
4 //layout->descriptor->reserved即block的函数地址
5 return lr;
6}同样，通过函数地址反查linkmap既可找到block符号。
瓶颈
基于静态扫描+运行时trace的方案仍然存在少量瓶颈：
initialize hook不到
部分block hook不到
C++通过寄存器的间接函数调用静态扫描不出来
目前的重排方案能够覆盖到80%～90%的符号，未来我们会尝试编译期插桩等方案来进行100%的符号覆盖，让重排达到最优效果。
整体流程
总结
目前，在缺少业界经验参考的情况下，我们成功验证了二进制文件重排方案在iOS APP开发中的可行性和稳定性。基于二进制文件重排，我们在针对抖音的iOS客户端上的优化工作中，获得了约15%的启动速度提升。
抽象来看，APP开发中大家会遇到这样一个通用的问题，即在某些情况下，APP运行需要进行大量的Page Fault，这会影响代码执行速度。而二进制文件重排方案，目前看来是解决这一通用问题比较好的方案。
未来我们会进行更多的尝试，让二进制文件重排在更多的业务场景落地。
手淘架构组最新实践 | iOS基于静态库插桩的⼆进制重排启动优化
原创 谢俊逸(极目) 淘系技术 2020-01-03
作者|谢俊逸(极目)
出品|阿里巴巴新零售淘系技术部
本文知识点提炼：1、APP 启动时 PageFault 的性能分析 2、静态库插桩重排方案的技术原理
背景
近期抖音和 Facebook 分享了自己通过二进制重排优化启动时间的方案，手淘 iOS 架构团队也对二进制重排进行了研究，由于手淘工程模块已经二进制化，因此实现了一套基于静态库插桩的重排方案。
▐ APP 启动 和 PageFault
当我们向操作系统申请内存时，操作系统并不是直接分配给我们物理内存，而是只标记当前进程拥有该段内存，当真正使用这段内存时才会分配。这种延迟分配物理内存的方式就通过 page fault 机制来实现的。当我们访问一个内存地址时，如果该地址非法，或者我们对其没有访问权限，或者该地址对应的物理内存还未分配， cpu 都会生成一个 page fault ，进而执行操作系统的 page fault handler 。如果是因为还未分配物理内存，操作系统会立即分配物理内存给当前进程，然后重试产生这个 page fault 的内存访问指令。
分配虚拟内存 读取 Page Fault 分配物理内存 读取
App 在启动时，需要执行各种函数，我们需要读取 TEXT 段代码到物理内存中，这个过程会发生缺⻚中断，由于启动时所需要执行的代码分布在 TEXT 段的各个部分，会读取很多⻚面，导致启动时 Page Fault 数量非常多。与直接访问物理内存不同， page fault 过程大部分是由软件完成的，消耗时间比较久，所以是影响启动性能的一个关键指标。
例如下图中，手淘启动时首先的调用的几个方法 会分布在虚拟内存的各个⻚面中, 执行这些方法时，需要从读取到物理内容中，就会产生多次 page fault 。
如果能将启动阶段需要的读取代码集中排布，将这些方法全都放到相邻的区域中，我们读取这些方法可能就只需要极少的 page fault 次数。可以减少不必要的 page fault 时间。达到优化启动时间的效果。
重排前后的函数在页面的布局对比：
重排方案
▐ 如何获取方法的执行顺序
为了生成 order_file , 我们需要确定应用启动时方法的执行顺序。之前抖音和 facebook 都分享过自己的方案，在实际操作的过程中，我们发现抖音和 facebook 的方案并不适用于手淘。
抖音通过静态扫描和运行时 Trace 等方法确定 order_file，该方案无法覆盖 initialize、block 和 C++ 通过寄存器的间接函数调用静态扫描不出来调用。
facebook 分享过通过 llvm 插桩的确定 order_file 的方案，需要使用源码重新打包。由于手淘几乎全是已经编译好的二进制模块，在手淘使用该方案不现实。
只能想其他办法...
手淘之前已经做过 pod 预编译，我和师兄念纪想到了是否可以通过在汇编层面对 pod 编译后的静态库进行插桩。在启动时，插桩后的方法都会调用记录方法，从而获得启动方法的执行顺序。在参考了离青对汇编插桩的研究后，确定了静态库插桩的实现方案。
▐ 静态库插桩
我们编译过的静态库由 .o 文件组成，我们可以对 .o 中的函数代码进行修改，在每个函数的开头插入调用我们指定记录函数的指令。
举个例子：
插入前 -[MyApp window]: 的汇编代码
-[MyApp window]:0000000000002d88 adrp x8, #0x0000000000002d8c ldrsw x8, [x8, #0xf18]; 0x2f18@PAGEOFF, _OBJC_IVAR_$_MyApp._window0000000000002d90 ldr x0, [x0, x8]0000000000002d94 ret
插入后的 汇编代码，可以看到 增加了跳转到 _record_method 的指令，并且补上了 prologue 和 epilogue 。
-[MyApp window]:0000000000002ebc stp x29, x30, [sp, #-0x10]!0000000000002ec0 mov x29, sp0000000000002ec4 bl _record_method0000000000002ec8 ldp x29, x30, [sp], #0x0000000000002ecc adrp x8, #0x0000000000002ed0 ldrsw x8, [x8, #0xc0]0000000000002ed4 ldr x0, [x0, x8]0000000000002ed8 ret
▐ 生成 order file
linkmap 记录了连接过程中的相关信息。其中包含链接用到的 symbol 相关的信息。通过 pc address 减去 slide 得到的地址，我们可以在 linkmap 中找到对应的 symbol .
address = pc - slide. // 因为ASLR， APP 可执行文件随机载入的原因，需要处理一下偏移量。
我们需要将之前记录的地址转换成对应的符号，为了真实还原线上的执行环境，我们只是在 app 中简单地的记录了 pc 地址 和 Image 的偏移量。通过解析 linkmap ，获取函数的地址区间， 得到距离 address 最近的 symbol ，生成 order_file 。
linkmap 文件:
# Symbols:# Address Size File Name0x100001630 0x00000039 [ 2] -[ViewController viewDidLoad]0x100001670 0x00000092 [ 3] _main0x100001710 0x00000080 [ 4] -[AppDelegate application:didFinishLaunchingWithOptions:]0x100001790 0x00000040 [ 4] -[AppDelegate applicationWillResignActive:]0x1000017D0 0x00000040 [ 4] -[AppDelegate applicationDidEnterBackground:]0x100001810 0x00000040 [ 4] -[AppDelegate applicationWillEnterForeground:]0x100001850 0x00000040 [ 4] -[AppDelegate applicationDidBecomeActive:]0x100001890 0x00000040 [ 4] -[AppDelegate applicationWillTerminate:]
▐ 更改符号的排列顺序
默认情况下， ld 链接器会按照链接的顺序将各个 .o 文件的数据重新布局生成可执行文件。ld 链接器提供 -order-file 选项操控数据排列的顺序。在 Xcode 中可以通过 Order File 选项指定符号排序文件。
//Order file 内容例子:+[xxxxx1 load]+[xxxxx2 swizzleResumeAndSuspendMethodForClass:]+[xxxxx3 load]+[xxxxx4 initialize]___+[xxxxx5 initialize]_block_invoke+[xxxxx6 initialize]___+[xxxxx7 initialize]_block_invoke...
优化效果
通过精准的启动函数重排，最后重排效果还是很可观的，在 iPhone6 上优化了400ms 的启动时间。
参考
感谢抖音团队和 Facebook 团队提供优化新思路
抖音研发实践：基于二进制文件重排的解决方案 APP启动速度提升超15%
Improving iOS Startup Performance with Binary Layout Optimizationshttps://atscaleconference.com/videos/performance-scale-improving-ios-startup-performance-with-binary-layout-optimizations/Linux下Page Fault的处理流程 https://cloud.tencent.com/developer/article/1459526
https://mp.weixin.qq.com/s/Drmmx5JtjG3UtTFksL6Q8Q
