Sieve—Android 内存分析系统 | 解决你的内存溢出问题

来这里找志同道合的小伙伴！

>>>> 背景

内存问题是个老大难，对用户来说，泄漏或者不合理的内存使用最终会反映到性能和体验上，并且极易造成 OOM( Out Of Memories ) 而闪退， 而对开发者来说更为头疼：

• OOM 堆栈价值不大 它是压倒骆驼的最后一根稻草罢了。
• 现有工具不够理想 LeakCanary 为解决内存泄漏而存在，但其实“泄漏”的定性其实是人为的：即你认为该对象不该继续存在了，结果它仍然被一条链路引用着，那我们说这个对象泄漏了。 LeakCanary 帮我们把 对象不该继续存在了 这个概念绑定为了比如 Activity 这种本身有生命周期的对象的 onDestroy()，这也意味着对于其他一些没有所谓生命周期的对象，只要它还在内存中存在着，那它泄漏与否实际上取决于你认定它该不该活着（但 LeakCanary 不知道你怎么想的，所以它无法帮你找到这些泄漏）。因此，我们希望能够单纯的提供对象的引用链路给你，至于它存在的合理性交由你自己判断。 MAT 的问题在于它实际上是个专为 Java 虚拟机做内存分析的工具，对于 Android 不够友好，尤其是 Bitmap 等对象大小不对的问题，这个后面细说，并且功能上来讲，部分冗余部分又达不到一些特定的需求，比较难用。
• 元凶不止一个 举个例子，一个 OOM 背后可能是两个 Activity 的泄漏，三张超大的图片等等一系列问题。这些捆稻草都有责任，理想情况是让这些稻草从重到轻排个序，谁负主要责任一目了然。

>>>> 成果

先上链接为敬！Sieve—Android 内存分析系统（http://performance.jd.com/，暂时只面向京东集团内部使用）

这是一个面向开发者的工具，上传一份 Hprof 文件（堆转储），系统将为你生成一份分析报告，下面是某一份报告页的截图。

总览

Activity/Fragment

Bitmap

对象的引用路径

Class 前三十

>>>> 实现

实现主要分为堆转储的解析、支配树的生成、RetainSize 的计算、引用链路的构造

>>>> 解析堆转储文件

Android Studio 中 Monitor 工具 Hprof 文件存储了当前时刻堆的情况，主要包括类信息、栈帧信息、堆栈信息、堆信息。其中堆信息是我们关注的重点，其中包括了所有的对象：线程对象、类对象、实例对象、对象数组对象、原始类型数组对象。

在所有对象中，部分对象还拥有另一重身份：虚拟机认定的 GC Root（指向的对象）。众所周知，GC Roots 是 ART VM 垃圾回收算法设定的根，代表了从这些根出发，顺着强引用关系所能达到对象是绝不会被回收的。 GC Roots 必须是对于当前 GC 堆的一组活跃的引用，这是显然的，因为引用是活跃的，那么引用直接或间接引用的对象们必然是有用的，是不能被回收的。知道了谁是不能回收的，也就知道了谁是能被回收的，GC 的目标也就找到了。这便是是 GC Roots 存在的意义。

GC Roots 分许多类型（不同虚拟机甚至更细或者不同的叫法），比如：

• Stack Local：当前活跃的栈帧里指向 GC 堆中对象的引用（也就是当前调用方法的参数、局部变量）
• Thread：存活的线程
• JNI Local：Native 栈中的局部变量
• JNI Global：Native 全局引用
• 分代收集中，从非收集代指向收集代的引用

等等，可以看出，这些分类都与 "GC Roots 是一组活跃的引用"的说法相吻合。同时，需要知道的是，GC Roots 是动态变化的，一个引用可能刚刚是 GC Root ，这会又不是了。

解析工作其实就是读取文件中以上提到的信息，并将其映射至内存的过程。最终映射的结果是一个叫做堆快照的数据结构。

严格来讲，GC Root 是引用而不是对象，为了描述方便，文中我们把其指向的对象也叫做 GC Root。

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 的对象的头上添加一个超级源点同时作为他们的父亲的话，其实我们就得到了一个以这个”超级源点“为根的引用关系”树“。（引号的原因是，实际情况里引用之间可能存在环，严格的讲它不一定是个树）

>>>> 支配树的生成与 RetainSize 的计算

先介绍一下相关概念

1、支配点与支配树

在有向图中，如果从源点到 B 点，无论如何都要经过 A 点，则 A 是 B 的支配点，称 A 支配 B。而距离 B 最近的支配点，称之为直接支配点。

比如上图中

• A 支配 B、C、D、E、F， 而 B 支配 D、E 不支配 F
• E 的直接支配点是 B

支配树是基于原图生成的一棵树，其每个点的父亲是原图中这个点的直接支配点。对与上图来说，支配树是

2、Shallow Size 与 Retained Size

某个对象的 Shallow Size 是对象本身的大小，不包含其引用的对象。也就是说比如对于下面这个类：

public class TestA {
    int a;
    TestB b;
}

其大小应该为：12（对象头）+4（int a）+4（TestB b）+4(对齐) = 24 （关于对象头，字段在内存中排列，对齐等不展开讨论）

这里重点关注字段 TestB 只计算了一个引用的大小：4 byte，而不管这个 TestB 有多少字段，每个字段是什么。

某个对象的 Retained Size 是其支配的所有节点的 Shallow Size 之和。

讲到这里其实就明白了，Retained Size 其实就是某个对象所能维护和保有的大小，换句话说它代表了如果回收掉该对象虚拟机所能收回掉的内存大小。各个对象的 Retained Size 大小是我们分析内存使用情况的重要指标，当某些对象的Retained Size 过大时，可能代表着不合理的内存使用或者泄露。

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算法。该算法引入了半支配点的概念，半支配点代表了有潜力成为直接支配点的点，该算法正是通过修正半支配点得到直接支配点的。详细可自行了解

4、Retained Size 计算

有了支配树，Retained Size 计算就是个累加过程。遍历每个点，将其 Shallow Size 加至支配树里其所有祖先身上去，比如对于上面的那张图，对于点 5 ，就是将其 Shallow Size 加至点 4 、点 2、点 1。当遍历完的时候，所有点的 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。

>>>> 引用链路的构造

通过 Retained Size 大小找到怀疑对象之后，需要找到它被引用的链路。对象的被引用路径其实就是个树，从怀疑对象开始，一层一层展开，树的叶子们就是 GC Root 。（见成果展示中的 Leak Trace 附图）

考虑到实际需要，这里采用是类似宽搜的方式，维护一个 FIFO 队列， 从怀疑对象开始，当搜索到GC Root 时保存当前的搜索状态，并返回路径。然后无限重复从保存的状态继续搜索，直到该次搜索找不到路径（返回为空）。最终得到若干条”最短路径“，也就是该对象的一条条的伸展开来的被引用链路。

注意到每一条路径中的任意相邻的点构成的线段实际上就代表了我们最终构造的树中的父子关系，遍历这些线段，完成这个有向图的存储即可。这里用邻接表的方式存下这个树，举个例子，这个数据结构可以长这样

public final class PathsFromGCRootsTree{
    private String description;
    private ArrayList<PathsFromGCRootsTree> inboundTrees;
}

>>>> Something else

其实这个项目一开始不是一个放在服务端的离线的面向开发者的分析系统，我们想在客户端线上搞定这个事情。在接近 OOM 的时候 dump hprof，另起进程分析，分析完上报，这样会解决很多痛点。不理想的是：

• Debug.dumpHprof（）会造成 GC，在接近 OOM 时的 GC 更是卡顿的让人无法接受。
• dump 下来的 hprof 文件如果映射至内存，动辄两三百兆（经观察发现它与 hprof 中对象的多少正相关），这显然会直接让分析进程就 OOM 了。
• 我们尝试过解决分析进程 OOM 的问题，设定一个阈值，舍弃同类型实例中的数量大于阈值的那一部分，边瘦身边映射。这样确实可以继续分析了，然而由于不少实例被舍弃，引用关系这张图变的残缺，也就导致引用链路构造变得不准确。

另外，研发过程中我们碰到并解决了巨多细节上的坑和问题，限于篇幅，感兴趣的同学可以私下交流探讨。

点击阅读原文，来试试Sieve—Android 内存分析系统吧。