前言
iOS内存泄漏是一个不起眼的小问题，但是随着业务增加，项目越来越大，内存泄漏导致的卡顿、耗电、OOM等问题也会越来越多，得物作为快速崛起的一家公司，技术没有完全跟上业务的发展，此问题更为严重。
在得物APM架构团队的研发实践中，我们参考了市面的一些内存泄漏监控方案，研发了基于对象关系扫描，精准定位泄漏对象的方案，并可用于生产环境。
本文主要分享下该解决方案的技术背景，技术原理，为该问题的解决提供相对比较完整的方案和一些新的思路。
一、内存泄漏背景介绍
内存泄露 memory leak，是指程序在申请内存后，无法释放已申请的内存空间，一次内存泄露危害可以忽略，但内存泄露堆积后果很严重，无论多少内存,迟早会被占光， memory leak 会导致内存占用过高、卡顿、耗电增加等，最终会导致out of memory！
常见问题汇总
为什么要做内存泄漏监控&监控上线？
内存泄漏无关设备型号，debug还是release环境，该发生的场景一定会发生。如线下监控，需要需要有人力去check和维护监控覆盖到了每一个业务场景，我们的期望是不入侵业务，所以让用户帮我们覆盖每一个业务场景。
监控上线需要全量开启吗？
不需要，有一定数量的样本即可。
为什么内存泄漏需要精准定位?
监控不准确，一个内存泄漏问题需要check大量的代码，更重要的是，看代码能轻易看出来的内存泄漏，这段代码就不会被这么写了。
精准定位泄漏问题后，开发同学只需要看某几行或几个对象关联的代码即可，大大减小了工作量，缩短问题的修复周期。
二、 内存泄漏模型
遍历全部内存理论上可以扫描到所有的引用关系，但损耗太大，所以采用页面为单位局部分析。若要分析内存中所有的对象，Xcode instruments Leaks你值得拥有。
说明：A结点为当前页面，其他结点为当前页面中的对象
内存模型1
页面A没有泄漏，A正常释放，B->C->D->E-B 循环引用导致内存泄漏，通过A可以扫描到循环依赖环及前置引用链。
内存模型2
内存模型3
页面A内存泄漏，A没有释放，A->B->C->D->A 循环引用导致内存泄漏，通过结点A可以扫描到这个依赖环以及引用关系链。
内存模型4
页面A没有泄漏，A正常释放，但是页面中的C结点内存泄漏，通过A没有可扫描的循环依赖，Thread->Timer->C泛指通过A获取不到的引用关系。
内存模型5
页面A内存泄漏，没有释放，通过A没有可扫描的循环依赖。
分析
- 内存模型1、2、3为循环引用，其中1、3可以通过A扫描对象引用关系链，定位到内存泄漏，内存模型2只能通过遍历全部内存对象获取到泄漏。
- 内存模型4、5被系统对象引用，虽无法获取具体泄漏对象的引用关系链，但是通过分析引用关系链可以准确定位到具体泄漏的位置。内存模型4可以定位到C结点泄漏，前置引用链为A->B-C，内存模型5可以定位到A结点泄漏。
内存模型小结
内存泄漏的数据模型大致可以总结为上述的5种，实际场景中可能是多种内存模型交错，通过图状数据结构以及相关算法分析，可以把具体的内存泄漏问题转化为抽象的数据结构与算法问题，具体解法可以多种多样。
三、技术方案
定义内存泄漏
Lim A = OOM
0-> ∞
一个Action重复多次，最终会导致OOM（Out Of Memory），则认定这个Action会导致内存泄漏，然后分析这个Action中存在的内存泄漏对象，若不会导致OOM，则认定此Action不会内存泄漏。
我的策略
检测时机
页面退出时，检测退出的页面是否存在内存泄漏。
扫描策略
获取页面对象引用的对象，可以生成以页面对象为顶点，向每一个引用的对象发出一条弧的图，依次遍历，可以生成以当前页面为顶点，包含当前页面中所有对象以及引用关系的有向图。
强引用指针指向当前页面对象，引用关系图扫描完成，解除强引用，回归原对象生命周期，3秒后检测当期对象是否存在，并且扫描引用关系图，如果有循环引用或者确认到泄漏的对象，上报泄漏数据。
关键case
- oc通过runtime，可以获取到引用的对象以及引用类型强弱，在生成有向图时，就可以过滤掉弱引用的弧，swift通过反射，无法获取引用类型强弱，所以需要先确认对象存在内存泄漏，若存在则必然存在强引用的环。
- swift闭包暂时还没找到怎么获取引用的对象的方法，所以当swift闭包等类似的场景，按内存模型4类比
当然，这些Swift兼容的问题若能解决，这个方案会做更好。
数据结构及算法
数据结构编程与语言无关，OC、Swift或者其他语言都可以有相同的实现。
图的三种实现，领接矩阵、邻接表、十字链表，此场景生成的图是一个稀疏矩阵，所以十字链表比较合适，可以实现稀疏矩阵遍历的最佳时间复杂度O(n+e)。
内存对象的数据结构定义
typedef struct EdgeNode //弧结点的定义
{
int tailvex; //弧尾结点的下标
int headvex; //弧头结点的下标
struct EdgeNode *headlink; //指向弧头相同的下一条弧的链域
struct EdgeNode *taillink; //指向弧尾相同的下一条弧的链域
EdgeType info; //弧中所含有的信息 可以是权值等
} EdgeNode;
typedef struct VertexNode //顶点结点的定义
{
int index; //下标值
VertexType data; //顶点内容
EdgeNode *firstout; //顶点的第一条出弧
EdgeNode *firstin; //顶点的第一条入弧
} VertexNode;
typedef struct OLGraph //十字链表存储结构的有向图定义
{
VertexNode vertices[MaxVex];
int vexnum; //顶点数
int arcnum; //边数
} OLGraph核心算法
核心算法
用栈协助完成非递归DFS遍历，实现稀疏矩阵遍历的最优时间复杂度O(n+e)，为最佳实践。
栈缓存遍历的弧，若存在环，则一定还会遍历到缓存的弧，以此就可以定位到环的位置，同时还需要断掉这条弧，以使程序不会在环中死循环。
//核心算法
while (!is_stack_empty(&S))
{
int index = Top(&S);
EdgeNode *node;
if (nodeCache[index] && nodeCache[index] != NULL)
{
node = nodeCache[index];
}
else
{
node = g->vertices[index].firstout;
}
// 当前顶点出弧的缓存数组
EdgeNode *edgeCycle[MaxVex];
while (node)
{
// 当前的弧已被访问过
if (node->visit == 1)
{
if (cycle)
{
// 判断到有环存在,收集环的数据并断掉这个
// node.tail = nil;// 断掉这个环
break;
}
} else {
addObject(node, edgeCycle);
}
//时间复杂度O(n+e)
count++;
if (visited[node->headvex] != 1)
{
//变换到下一条尾结点相同的弧
//共e（弧数量）次操作
Push(&S, node->headvex);
scount++;
node = g->vertices[node->headvex].firstout;
if (node && node->taillink != NULL)
{
nodeCache[node->headvex - 1] = node->taillink;
}
}
else
{
//变换结点
//共n（结点数量）次操作
dcount++;
node = node->taillink;
}
}
int j = -1;
Pop(&S, &j);
visited[j] = 1;
}
如何确认对象内存泄漏
引用关系图中存在环，且环中的对象都未释放，则这里就是内存泄漏的地方。
存在的问题
- 如果环中的对象都是单例，这种情况不会造成内存一直增长，按照上边内存泄漏的定义，不符合定义，应当过滤掉。
- 如不考虑内存模型2，扫描引用关系中环，可以覆盖到内存模型1和3，其中内存模型2和4无法覆盖。
优化策略
对比前后扫描结果
上图中存在两个泄漏，应上报两次
- C结点内存泄漏
- DE结点内存泄漏
对比策略
扫描当前引用关系图，如果上次扫描结果中也存在相同位置结点且都未释放
- 内存地址一样，可能是单例，不会导致内存一直增长，不认定为泄漏
- 内存地址不一样，认定为内存泄漏对象
最终扫描结果
-
内存模型1：上报所在页面A，前置引用链A->B，循环依赖环 B->E->D->C->B
-
内存模型2：扫描不到
-
内存模型3：上报所在页面A，前置引用链为空，循环依赖环 A->B->C-D->A
-
内存模型4：上报所在页面A，前置引用链为A->B->C，循环依赖为空，内存泄漏可以锁定到C对象
-
内存模型5：上报所在页面A，前置引用链为空，循环依赖环为空，A对象内存泄漏，并且排除了其他的泄漏情况。
监控策略小结
扫描引用关系中的环，配合前后扫描图的对比，可以覆盖除内存模型2外的所有模型，并可以生成比较完整的引用关系链，精确定位到具体的泄漏位置。
扫描时长
得物随机页面的扫描时长示例，单位（秒），大多数页面扫描时间会在1秒以内
=====>:等待...0.573888
=====>:等待...0.556977
=====>:等待...1.401240
=====>:等待...0.791259
=====>:等待...1.368312
=====>:等待...3.868116
=====>:等待...0.841532
=====>:等待...0.607546
=====>:等待...0.911085
=====>:等待...0.831673
=====>:等待...0.441535
=====>:等待...3.720887
内存
扫描过程中，会强持有该对象，导致该对象在扫描过程中不会被释放，如果未发生内存泄漏，此对象应该立即被释放，所以这个对象在内存中会多存在一段时间，时长为扫描时长，与设备性能逆相关。
导致的特殊问题
有音频、视频播放页面（直播页面）退出时，页面立即释放，音视频立即消失，但若开启扫描引用链，扫描时页面不释放，若播放停止在delloc方法中，就会出现页面退出还有一段时间在播放声音，后台播放时长为扫描时长。
CPU
扫描时，大量的内存读取操作，对CPU有一定的消耗，对页面流畅度整体影响不大，但是会有一定的损耗，得物release环境测试结果如下（此处仅为表示损耗具体说明，并非量化）：
- 关闭引用链扫描时，退出某页面，CPU出现波峰，但立即就下去
- 开启引用链扫描时，退出某页面，波峰会延长一小段时间再下去，此时在扫描生成对象引用关系图，3秒后又出现一个遍历引用关系图的波峰。
开启引用链扫描CPU波动图，波峰较多
关闭引用链扫描CPU波动图，波峰较少
减小用户体验影响的策略：
- 不需要全量开启，每个版本有一定数量的样本即可
- 设备型号限制，低端设备不开启
- 相同页面最多次数设置阈值
- 设置单次最大扫描时长设置阈值
文/刘崇
得物技术
关注我们，做最潮技术人！