Shooter系统内存分析工具OOM实践
在我们日常开发工作中，遇到的崩溃问题大多说是可以通过堆栈日志信息找到问题的关键所在，但是内存的泄漏和不合理的使用导致的OOM（Out-Of-Memory）却无法在堆栈日志中定位到问题，通过dump内存得到内存镜像对内存的使用进行分析需要专业的人员，为了解决这些弊端，我们研发了一款用于开发者线下使用的内存分析系统。
移动应用在运行的时候系统会分给应用指定大小的内存空间，在不同的设备上大小可能不一样。应用在运行期间不断的申请内存，当应用占有的内存即将达到系统分配的阈值，应用再次申请大于剩余空间的时候，这时候会导致应用直接闪退，在日志中可以看到发生了OOM（Out-Of-Memory）的异常，当然这些都是表象，在android系统中导致OOM的情况大致分为以下4种情况：
系统分派的空间不足或者没有连续足够可用的空间（堆内存）
我们知道在android中GC（垃圾回收机制）会不断的清理应用在运行期间产生的不再使用的对象，即我们在编程中常说的对象不再使用的时候要及时的释放掉或者置为null，GC的过程中会回收混杂在连续内存空间中的不再使用的对象，这样就导致了可用的内存空间不再连续，当应用再次向系统申请空间的时候，没有一段连续的内存空间满足条件的时候就会抛出OOM的异常，当然如果本来就没有任何空间可以使用就会立即抛出OOM异常。
FD的数量超过了系统所允许的最大值
FD是File Descriptor的缩写，在Linux系统中，所以的操作都是对文件的操作，而文件操作是通过FD来实现的，当FD的数量超过了系统所允许的最大值，那么也会抛出OOM。
线程数超过了系统允许的最大值
手机所允许的最大线程数也是和厂商有关系，不同的手机厂商设置的最大线程阈值也是不相同的，当创建的线程超过了最大值，系统也会抛出OOM的异常。
虚拟内存不足
这里的虚拟内存指的是应用运行时候所产生的一块与内核态内存映射的用户态虚拟内存空间， 用户通过该内存实现用户态与内核态的调用操作，即native层方法的调用，如果该内存空间耗尽也会导致OOM。
发生OOM异常一般情况下都是由于情况1中的堆内存的空间不够使用，虽然也遇到过线程数超过了系统最大限制的情况， 但是很少见到，其他两种情况基本没有见到过，所以接下来的分析中我们的侧重点就是对于堆内存的解析。
OOM与其他的崩溃的分析方法大相径庭。一般的异常我们可以通过异常堆栈就可以分析定位原因，但是OOM导致崩溃时候的堆栈并不能准确的反馈出问题的关键，此时的堆栈反馈出来的只是压死骆驼的最后一根稻草，也许是一个正常的操作。业界的分析方案一般为以下几种情况：
开发期间集成LeakCanary，在开发人员自测的时候检测内存泄漏情况
LeakCanary 为解决内存泄漏而存在，但其实“泄漏”的定性其实是人为的：即你认为该对象不该继续存在了，结果它仍然被一条链路引用着，那我们说这个对象泄漏了。LeakCanary 帮我们把 对象不该继续存在了 这个概念绑定为了比如 Activity 这种本身有生命周期的对象的 onDestroy()，这也意味着对于其他一些没有所谓生命周期的对象，只要它还在内存中存在着，那它泄漏与否实际上取决于你认定它该不该活着（但 LeakCanary 不知道你怎么想的，所以它无法帮你找到这些泄漏）。因此，我们希望能够单纯的提供对象的引用链路给你，至于它存在的合理性交由你自己判断。
通过命令获取应用运行期间的内存快照，通过JVM内存分析工具MAT解析出当时的内存使用情况
在应用运行期间通过调用Debug.dumpHprofData(String fileName)函数得到当前进程的Java内存快照文件，再通过MAT工具导入hprof文件，使用该工具的解析结果分析android运行时候的内存使用情况。虽然MAT可以分析出内存快照中内存的使用情况，但是它是针对于java的一个内存分析工具且有一定的学习成本，对android的分析还有一些小的区别，并不是完全的符合android的内存分析。
为了避免上述OOM分析时候出现的弊端，我们开发了一套对于内存快照（hprof文件）的线下分析工具，只需要开发者将生成的hprof文件上传即可, 该工具会进行内存快照的解析、支配树的生成、RetainSize 的计算、引用链路的构造得到内存分析结果，具体的实现流程如下：
1.1 内存快照hprof文件的获取以及结构
我们可以使用命令行来获取内存快照，也可以通过Android Studio自带的 Monitor 工具获取。
Hprof 文件存储了当前时刻堆的情况，主要包括类信息、栈帧信息、堆栈信息、堆信息。其中堆信息是我们关注的重点，其中包括了所有的对象：线程对象、类对象、实例对象、对象数组对象、原始类型数组对象。
1.2 SNAPSHOT中堆栈的组成
Default Heap：对于某对象，系统未指定堆；
App Heap：对应 ART VM 中的 Allocation Space，其实分裂自 Zygote Space。进程独享的主堆。这里是我们主要关注的地方，程序运行期间生产的对象实例以及数组实例都是存放在这个地方。
Image Heap：对应 ART VM 中的 Image Space，系统启动映像，包含启动期间预加载的类， 此处的分配保证绝不会移动或消失。
Zygote Heap：对应 ART VM 中的 Zygote Space ，进程共享。在该Hprof 文件中表示Zygote Space 中属于该进程的那部分。
在将 Hprof 映射至这份快照的同时，我们通过它提供类的继承关系、类的字段信息等等，在这份 SnapShot 的各个对象之间建立了引用与被引用的关系(可以叫它父子关系，这里我们只保留强引用关系)。那如果再为所有是 GC Root 的对象的头上添加一个超级源点同时作为他们的父亲的话，其实我们就得到了一个以这个”超级源点“为根的引用关系”树“。（引号的原因是，实际情况里引用之间可能存在环，严格的讲它不一定是个树）。
1.3 链路构建的起点GCRoot
GC Root 是虚拟机认定的。众所周知，GC Roots 是 ART VM 垃圾回收算法设定的根，代表了从这些根出发，顺着强引用关系所能达到对象是绝不会被回收的。 GC Roots 必须是对于当前 GC 堆的一组活跃的引用，这是显然的，因为引用是活跃的，那么引用直接或间接引用的对象们必然是有用的，是不能被回收的。知道了谁是不能回收的，也就知道了谁是能被回收的，GC 的目标也就找到了。这便是是 GC Roots 存在的意义。GC Roots 分许多类型，比如：
Stack Local：Java 方法中的局部变量或者方法形参；
Thread：存活的线程；
JNI Local：JNI方法中的变量或者方法形参；
JNI Global：全局 JNI引用；
分代收集中，从非收集代指向收集代的引用等等；
同时，需要知道的是，GC Roots 是动态变化的，我们本次分析的时候这个引用是一个 GC Root , 但是下次同样运行环境得到的hprof文件，这个引用却不是一个 GC Root 了。
解析工作其实就是读取文件中以上提到的信息，并将其映射至内存的过程。最终映射的结果是一个叫做堆快照的数据结构。
1.4 支配树的生成与 RetainSize 的计算
1.4.1 支配点与支配树
在有向图中，如果从源点（R点）到 B 点，无论如何都要经过 A 点，则 A 是 B 的 支配点，称 A 支配 B。距离 B 最近的支配点，则称之为 B 的 直接支配点。
比如下图中：
A 支配 B、C、D、E、F， 而 B 支配 D、E 不支配 F；
E 的直接支配点是 B；
支配树是基于原图生成的一棵树，其每个点的父亲是原图中这个点的直接支配点。对于上图来说，支配树是：
1.4.2 Shallow Size 与 Retained Size
某个对象的Shallow Size是对象本身的大小，不包含其引用的对象，其实就是该对象所能维护和保有的大小，换句话说它代表了如果回收掉该对象虚拟机所能收回掉的内存大小。
具体举例如下：
public class A {int a；B b；}
class A 的Shallow Size应该为：12（对象头）+ 4（int a）+ 4（B b）+ 4(对齐) = 24 （关于对象头，字段在内存中排列，对齐等不展开讨论）
这里重点关注字段 B 只计算了一个引用的大小：4 byte，而不管这个 B 有多少字段，每个字段是什么。
某个对象的Retained Size是其支配的所有节点的Shallow Size之和。各个对象的 Retained Size大小是我们分析内存使用情况的重要指标，当某些对象的Retained Size 过大时，可能代表着不合理的内存使用或者泄露。
1.4.3 支配树的生成
对于 DAG（有向无环图）来说，可以按照拓扑序来构建支配树，记拓扑序中第 x 个点 为 v ，求 v 的直接支配点时，拓扑序中 v 之前的点（拓扑序为 1~x-1的点 ）的直接支配点已经求好了（也就是对于这些点，支配树已经构造好了），接下来对在原图中 v 的所有父亲求在已经构造的支配树上的最近公共祖先（因为父亲们肯定拓扑序小于 x，所以父亲们已经在目前构造好的支配树上了）。举个栗子，对于下图（点已按拓扑序标号）：
假设走到了求点 8 的直接支配点这一步，则说明 1~7 的支配树已构造完毕，如下图：
接着，对点 8 的父亲，点 5、6、7 求在上图支配树中的最近公共祖先，显而易见他们的最近公共祖先是点 1，因此点 8 的直接支配点就是点 1，继续添加到支配树上，得到：
以上就是支配树的构造过程，这里是树在不断改变并且是在线查询的情况，我们采用的倍增法，树的 LCA（最近公共祖先）问题的算法很多，比如转化为 RMQ（范围最值查询） 问题求解等等，可自行了解。
还没完呢！细心的你可能发现了，之前提到过，实际的引用关系并不是树，也不是 DAG ，而仅仅是个有向图。这意味着有环，意味着拓扑序失去了意义，意味着对每个点的所有父亲求在支配树上的 LCA 时，它的某个父亲可能还没有处理。这里采取的方式是，如果这个父亲没有处理，那就先跳过，继续之前的算法，就当少了一个父亲，直至支配树构造完毕。紧接着，从头开始重复构造支配树，之前某点没有处理的父亲，这一次可能就变成处理过的了，所以就可能将该点求出的直接支配点结果“刷新”。不断的重复这一过程，直至不存在某个点求出的直接支配点被“刷新”。也就是说既然环的存在使的拓扑关系不再成立，那就跳过因此导致此时还未处理的父节点，通过不断迭代的方式使得最终所有求得的支配点“收敛”。
上述算法的瓶颈在于这个迭代的次数随着图的复杂程度爆炸增长，有向图（有环也行）的支配树构造其实有更为优秀的算法，Lengauer-Tarjan算法。该算法引入了半支配点的概念，半支配点代表了有潜力成为直接支配点的点，该算法正是通过修正半支配点得到直接支配点的。详细可自行了解。
1.4.4 Retained Size 计算
有了支配树，Retained Size 计算就是个累加过程。遍历每个点，将其 Shallow Size 加至支配树里其所有祖先身上去。当遍历完的时候，所有点的 Retained Size 也就计算完毕了。
但如果真就这样算下来，会发现比如不少 Bitmap 的 RetainSize “根本不对”，如果你用 MAT 查看，发现经常就几十字节，这在直觉上是无法理解的。这就与文初提到的 GC Root 有关了，虚拟机会将某些对象标记成各种 Type 的 GC Root。可以想象一下，这就相当于把某个本是从顶到下的引用关系链中的普通节点，被提扯到最顶上去当做根节点，这也是出现环的原因之一。
Bitmap 中 mBuffer 成员正是如此，byte[] 类型的 mBuffer 存储了位图的像素数据，几乎占据了 Bitmap 的全部大小。如果它本本分分，那么它就是支配树上的一个叶子，其直接支配点就是其父对象 Bitmap，那就一切正常皆大欢喜。然而事实是在某些情况下，由于它被“提拔”成了 GC Root，它的直接支配点会被支配树算法直接置为超级源点。这会导致其 Shallow Size 无法加至其原本的祖先链上去。
比如上面图中，假设点 5 就是那个 mBuffer，点 4 是 Bitmap，因为点 5 的支配点不是点 4 了，所有点 5 的 Shallow Size ，加不到点 4、点 2、点 1 身上去了。因此我们做些特殊的处理，让mBuffer 记下其对应的 bitmap 对象，计算 Retained Size 时，碰到 mBuffer ，直接将其 Shallow Size 加至支配树中其记下的 bitmap 和 bitmap 的祖先链上去。
那 MAT 就是错的吗？并不是，按照 retained size 的定义，既然 bitmap 并不是 mBuffer 的直接支配点了，那 bitmap 所支配的大小确确实实就不包含 mBuffer 的大小。只是考虑到 mBuffer 作为 GC Root 的状态是变化的，而开发者又希望能够直观了解应用中位图的大小，才产生了这个“修补”策略。
如果某个对象是 GC Root，那么它的内存当然不会被回收。但有时候这个对象就不应该一直还是 GC Root。比如我们常常调侃单例模式其实就是个泄漏，因为静态成员让其成为了 GC Root，内存永远无法释放。所以你应该在不再需要某个对象的时候，断掉对它的强引用（无论是让其不再不合理的成为 GC Root或是断掉其被引用链中的一环）。对于图片来说，如果你选择自行管理其加载缓存等，那你可能还需要及时的 bitmap.recycle() , 该方法会断掉对 mbuffer 的引用。如果你使用 Fresco ，那你需要确保 DraweeView 的 onAttach 和 onDetach 能够正确及时的被调用。
此外，以上修补策略仅限于 8.0 以下。在 Android 8.0及以上，java 层 Bitmap 不再持有 mBuffer 成员，像素数据被移至 Zygote Heap。
1.5 引用链路的构造
通过 Retained Size 大小找到怀疑对象之后，需要找到它被引用的链路。对象的被引用路径其实就是个树，从怀疑对象开始，一层一层展开，树的叶子们就是 GC Root 。
考虑到实际需要，这里采用是类似宽搜的方式，维护一个 FIFO 队列， 从怀疑对象开始，当搜索到GC Root 时保存当前的搜索状态，并返回路径。然后无限重复从保存的状态继续搜索，直到该次搜索找不到路径（返回为空）。最终得到若干条”最短路径“，也就是该对象的一条条的伸展开来的被引用链路。
注意到每一条路径中的任意相邻的点构成的线段实际上就代表了我们最终构造的树中的父子关系，遍历这些线段，完成这个有向图的存储即可。
在上述的分析中我们主要进行的是链路的构造工作以及链路中每个节点在内存中占用的空间大小的计算，通过将内存中的对象按照引用构造好我们就可以直观的查看到是什么占用了大量的内存。
根据Android的特性，我们按照如下维度进行了汇总。
2.1 Activity/Fragment对象的引用链路
与用户交互的具有生命周期的控件是否有内存泄漏，这个主要是观察一个Activity/Fragment是否有多个实例对象存在于内存中，如果有多个实例对象存在于内存中，说明该控件可能被其他对象所引用，没有及时的得到释放，需要重点关注。
2.2 图片信息以及引用链路
图片一直是Android内存中重量级选手，各种图片框架都通过三级缓存等复用机制来降低对内存的占用，内存不够使用甚至导致OOM很大一部分都是图片导致的，可能图片的尺寸不对，缩放的大小不合理，像素点占用的大小不合理等问题导致的，所以这里我们将图片按照占用内存由大到小展示出来，如图所示：
2.3 对象的引用链路展示
上述图片中每条记录点击LeakTrace即可查看当前对象的引用链路：
2.4 内存快照中各对象的空间占用情况
上述两种情况是一般内存泄漏以及导致OOM的关键点，当然可能不是上述两种情况导致的，那么就可能是某个对象创建的次数太多，在内存中占有的空间太大，这样就可以根据对象在内存中的个数以及占用空间的大小确认导致OOM的问题了。
通过上述流程查询一遍，基本就可以找到出现OOM的问题所在了：
Shooter 系统致力于应用性能的监控工作，内存监控监控只是其中的一个点，还包括网络，webview，图片等各种监控方案。内存分析工具本意是做成一个线下的工具，但是由于Dump时候系统的GC会导致卡死，hprof文件映射到内存会占用大量的空间而没有完全的实现，我们会努力寻找相关的解决方案，不断的完善线下内存分析。