1.前提

本文將以講解原理為主，部分代碼講解清寇，可以自行下載HAHA庫源碼進(jìn)行對照學(xué)習(xí)向叉。

implementation 'com.squareup.haha:haha:2.0.3'

如果你看過Leakcanary2.0之前的源碼岖赋，你應(yīng)該會熟悉HAHA庫哄褒，它是一個解析hrpof文件的庫赘理，通過它我們可以獲得當(dāng)前內(nèi)存的對象信息翘紊，包括如下信息换薄。

1.獲得對象的shallow size和retained size鞠呈。

2.獲得對象的引用鏈融师。

2.HAHA庫的實(shí)現(xiàn)步驟：

1.Hprof（堆轉(zhuǎn)存）文件的解析。

2.支配樹的構(gòu)造和Retained Size計(jì)算蚁吝。

3.最短路徑構(gòu)建旱爆。

下面我將會從這幾個主要維度進(jìn)行介紹舀射。

2.1 Hprof（堆轉(zhuǎn)存）文件的解析。

    Hprof是一份存儲了當(dāng)前時刻內(nèi)存信息的文件怀伦，即內(nèi)存快照后控。可以方便我們進(jìn)行內(nèi)存分析空镜。里面包括類信息浩淘、棧信息、堆信息吴攒。其中堆信息是需要我們關(guān)注的重點(diǎn)张抄。堆信息包括了所有的對象：線程對象、類對象洼怔、實(shí)例對象署惯、對象數(shù)組對象、原始類型數(shù)組對象镣隶。其中類對象可以獲得該類的常量极谊、靜態(tài)變量、實(shí)例變量等信息安岂。

2.1.1 Hprof 文件格式

    首先需要理解Hprof文件的格式轻猖，它的基本數(shù)據(jù)類型為u1、u2域那、u4咙边、u8，分別代表1 byte次员、2 byte败许、4 byte、8 byte的內(nèi)容淑蔚，由文件頭和文件內(nèi)容（records)組成,如下圖：

image

2.1.2 文件頭格式如下：

2.1.3 文件頭格式如下：

文件內(nèi)容格式如下：

2.1.4 文件內(nèi)容格式如下：

string的格式如下办陷，其他信息可以自行查閱：http://hg.openjdk.java.net/jdk6/jdk6/jdk/raw-file/tip/src/share/demo/jvmti/hprof/manual.html#mozTocId848088

圖片.png

2.1.5 TAG類型信息：

HPROF_TAG_STRING = 0x01；字符串信息
HPROF_TAG_LOAD_CLASS = 0x02律歼； 可以獲得類id對應(yīng)的字符串信息
HPROF_TAG_STACK_FRAME = 0x04民镜；棧幀信息
HPROF_TAG_STACK_TRACE = 0x05；棧信息
HPROF_TAG_HEAP_DUMP = 0x0C险毁；
HPROF_TAG_HEAP_DUMP_SEGMENT = 0x1C制圈；這2個是所有的對象信息

如果TAG是HEAP_DUMP 或 HEAP_DUMP_SEGMENT ，它的BODY由一系列子record組成
HEAP DUMP 或  HEAP DUMP SEGMENT的sub-tag信息
// Traditional. 
HPROF_ROOT_UNKNOWN = 0xFF, 
HPROF_ROOT_JNI_GLOBAL = 0x01,        // native 變量  
HPROF_ROOT_JNI_LOCAL = 0x02,  
HPROF_ROOT_JAVA_FRAME = 0x03,  
HPROF_ROOT_NATIVE_STACK = 0x04,  
HPROF_ROOT_STICKY_CLASS = 0x05,  
HPROF_ROOT_THREAD_BLOCK = 0x06,  
HPROF_ROOT_MONITOR_USED = 0x07,  
HPROF_ROOT_THREAD_OBJECT = 0x08,  
HPROF_CLASS_DUMP = 0x20,            // 類  
HPROF_INSTANCE_DUMP = 0x21,         // 實(shí)例對象  
HPROF_OBJECT_ARRAY_DUMP = 0x22,     // 對象數(shù)組  
HPROF_PRIMITIVE_ARRAY_DUMP = 0x23,  // 基礎(chǔ)類型數(shù)組   
// Android.  
HPROF_HEAP_DUMP_INFO = 0xfe,  
HPROF_ROOT_INTERNED_STRING = 0x89,  
HPROF_ROOT_FINALIZING = 0x8a,  // Obsolete.  
HPROF_ROOT_DEBUGGER = 0x8b,  
HPROF_ROOT_REFERENCE_CLEANUP = 0x8c,  // Obsolete.  
HPROF_ROOT_VM_INTERNAL = 0x8d,  
HPROF_ROOT_JNI_MONITOR = 0x8e,  
HPROF_UNREACHABLE = 0x90,  // Obsolete.  
HPROF_PRIMITIVE_ARRAY_NODATA_DUMP = 0xc3,  // Obsolete.

2.1.6 Basic Type：

在類對象中可以獲得所有實(shí)例變量的type畔况，通過type我們即可以知道它是一個什么類型鲸鹦。

通常我們關(guān)心的主要是三類信息：

1. 字符串信息：所有的字符串，包括類名跷跪、實(shí)例名馋嗜、變量名等。
2. 類的結(jié)構(gòu)信息：父類信息吵瞻、變量布局等葛菇。
3. 堆信息：包括GC ROOT、普通對象橡羞、普通對象數(shù)組眯停、對象之間的引用等。

2.2 GC ROOT

HAHA庫就是通過上述規(guī)則讀取獲得類對象卿泽、實(shí)例對象庵朝、對象數(shù)組、基本類型數(shù)組又厉、GC ROOT等信息九府。
在所有對象中，會有一部分虛擬機(jī)認(rèn)定的GC Root覆致。
什么是GC Root：首先我們需要了解一下JVM的垃圾回收算法侄旬，其中一個是可達(dá)性算法，可達(dá)性的意思是如果存在從一個起點(diǎn)到該對象的引用鏈煌妈，該對象就不能被回收儡羔，該起點(diǎn)就是GC Root。
GC Root的特點(diǎn)：當(dāng)前時刻存活的對象璧诵！這是肯定的汰蜘，只有引用是活躍的，那么它所直接引用和間接引用的對象必然是有用的之宿，是不能被回收的族操。
可以被當(dāng)成GC root的類型：

• Stack Local：當(dāng)前活躍的棧幀中指向GC堆中的引用（局部變量、方法的引用類型參數(shù)）
• Thread：存活的線程
• JNI Local:Native棧中的局部變量
• JNI Global:Native全局引用
• Monitor Used：用于同步的監(jiān)控對象
• Held by JVM：用于JVM特殊目的由GC保留的對象。包括類加載器色难、JVM中重要的異常類等泼舱。

3.構(gòu)建支配樹：

在Hprof這份文件中，將解析出來的對象之間建立一個引用與被引用的關(guān)系枷莉，然后再為所有的GC ROOT設(shè)置一個超級源點(diǎn)娇昙，這樣就會形成一個以超級源點(diǎn)為根的引用樹（中間可能會存在環(huán)）。

3.1 Shallow Size 和 Retained Size

3.1.1 Shallow Size：

某個對象的Shallow Size就是對象本身的大小笤妙，不包含引用的大小冒掌。
下面是對象的內(nèi)存結(jié)構(gòu)：包括下面幾個部分：

1. 對象頭：包括Mark Word和Klass Point（指針，指向方法區(qū)的Class對象信息）蹲盘，下面還分三種大小

1. 在32位系統(tǒng)下股毫，Mark Word是4byte，指針大小是4byte辜限，所以對象頭為8byte
2. 在64位系統(tǒng)下皇拣，Mark Word是8byte，指針大小是8byte薄嫡，所以對象頭為16byte
3. 在64位系統(tǒng)下并開啟指針壓縮的情況下氧急，Mark Word是8byte，指針大小是4byte毫深，所以對象頭為12byte

2. 實(shí)際數(shù)據(jù)：就是實(shí)例對象的類型大小吩坝，比如int，String等大小

3. 對齊填充：這個并不一定會存在哑蔫，因?yàn)橐髮ο笃鹗嫉刂繁仨毷?字節(jié)的整數(shù)倍钉寝。

   
   
   圖片.png
   
   

   比如下面這個類：

public class A {
    int a;
    B b;
}

在64位系統(tǒng)并開啟指針壓縮的情況下，它的Shallow Size = 12 （對象頭）+ 8（實(shí)際大姓⒚浴）+4（對齊填充）= 24byte嵌纲。

3.1.2 Retained Size：

Retained Size的大小簡單來理解就是其支配的所有節(jié)點(diǎn)的Shallow Size之和，這里有一個支配的節(jié)點(diǎn)的概念腥沽，在對象中的應(yīng)用就是對象A->B->C逮走，這中間沒有任何引用指向B或者C，這就是A支配B今阳，B支配C师溅，A支配C。
比如下面這張圖盾舌，我們來求對象A的Retained Size墓臭，對象A有實(shí)例對象B、C妖谴、D窿锉，正常來說就是B、C、D的Shallow Size之和就是它的Retained Size榆综，但是對象D（D有可能是一個全局的實(shí)例）也被對象E所引用妙痹，所以對象D的支配點(diǎn)就不是A而是最頂層的O铸史，因此對象A的Retained Size = B + C的Retained Size鼻疮。

圖片.png

換句話說Retained Size就是某對象被VM回收后所能釋放的內(nèi)存大小。
Retained Size對于內(nèi)存的分析有很大的指引作用琳轿，該值大有可能是不合理的內(nèi)存使用或者泄露判沟。

3.2 支配樹

再來看一下支配樹的定義：對于有向圖D,起點(diǎn)S,終點(diǎn)T，存在S>多條路徑>T崭篡，在所有的路徑中S到T必經(jīng)的點(diǎn)稱為支配點(diǎn)挪哄，刪了該點(diǎn)，將不存在S到T的路徑琉闪，因此稱起點(diǎn)為S時迹炼，該點(diǎn)支配了T。離T點(diǎn)最近的支配點(diǎn)稱為直接支配點(diǎn)颠毙。
S>T中可能有很多支配點(diǎn)斯入，由這些支配點(diǎn)構(gòu)成的樹，稱為支配樹
支配樹的性質(zhì)：

• S為樹根
• 根到樹上任一點(diǎn)的路徑經(jīng)過的點(diǎn)均為根支配的點(diǎn)
  任意子樹也有上述性質(zhì)蛀蜜。
  有木有覺得和求Reatined Size的流程很像刻两，也就是說，在求某個對象的Reatined Size滴某，只要構(gòu)建相應(yīng)的支配樹磅摹，然后進(jìn)行其支配節(jié)點(diǎn)的相加即可。
  支配樹的生成：
  一般來說霎奢，對于一張DAG（有向無環(huán)圖）來說户誓，可以通過拓?fù)湫?LCA(最近公共祖先）的方法來構(gòu)造支配樹。但是對于實(shí)際對象的引用關(guān)系幕侠，有可能會存在環(huán)帝美，也就是普通的有向圖。下面我先介紹一下DAG構(gòu)造支配樹的過程：

3.3 拓?fù)渑判?/h2>

定義：它是對有向圖的頂點(diǎn)排成一個線性序列橙依。
在圖論中证舟，拓?fù)渑判蚴且粋€有向無環(huán)圖（DAG）的所有頂點(diǎn)的線性序列。且滿足下面兩個條件：

• 每個頂點(diǎn)出現(xiàn)且只出現(xiàn)一次窗骑。
• 若存在一條從頂點(diǎn)A到頂點(diǎn)B的路徑女责，那么在序列中頂點(diǎn)A出現(xiàn)在頂點(diǎn)B的前面。

• 拓?fù)湫蚩梢杂卸鄠€创译。
  拓?fù)湫虻那蟮梅绞娇梢宰孕胁橘Y料抵知，我這里只說結(jié)果。求拓?fù)湫蛑械趚點(diǎn)的直接支配點(diǎn)時，該x點(diǎn)前的直接支配點(diǎn)已經(jīng)求得完成刷喜，也就是支配樹已經(jīng)構(gòu)造好残制，這時候就可以對點(diǎn)x的所有父親求LCA求得直接支配點(diǎn)。舉個例子掖疮，對于下圖（數(shù)字代表求好的拓?fù)湫蛱枺?/p>
  

  圖片.png
  
  

  比如我們現(xiàn)在想求7的直接支配點(diǎn)初茶，則說明1-6的支配樹已經(jīng)構(gòu)造完成，只需要求7所有父類的LCA即可
  浊闪。即下圖：

  
  
  圖片.png
  
  上面是一般情況恼布，正常來說引用都是存在環(huán)的，也就是說在求某個點(diǎn)的直接支配點(diǎn)時搁宾，它的有些父親可能還沒有找到自己的直接支配點(diǎn)折汞，這時候子類當(dāng)然也不能找到它自己的支配點(diǎn)，HAHA庫中的做法是：如果某個父類沒有支配點(diǎn)（也就是并未處理）盖腿，就先跳過它爽待，也就是認(rèn)為少了一個父類，繼續(xù)當(dāng)前尋找直接支配點(diǎn)翩腐，等整棵樹處理完畢以后鸟款，再迭代進(jìn)行支配樹的構(gòu)建，直到所有的節(jié)點(diǎn)的支配樹都找到且沒有改變栗菜，至此結(jié)束欠雌。
  第一遍可能看的會有點(diǎn)蒙，我舉個例子疙筹，比如下面的有向圖：序號是已經(jīng)排好的拓?fù)湫?br>
  圖片.png
  
  

  我們現(xiàn)在求點(diǎn)3的直接支配點(diǎn)富俄，具體步驟如下：

1. 找到所有指向3的引用點(diǎn)（也就是1和4），求他們的最近公共節(jié)點(diǎn)而咆。
2. 1的支配點(diǎn)是它自己霍比，但是4的直接支配點(diǎn)并未處理（第一遍還沒輪到它呢），所以4的支配點(diǎn)肯定是null暴备。
3. 這種情況下我們本次就先去掉父節(jié)點(diǎn)4悠瞬，所以本次3的直接支配點(diǎn)是1。
4. 繼續(xù)往后求4的直接支配點(diǎn)涯捻，即2和3的最近公共節(jié)點(diǎn)浅妆，也就是1。
5. 重頭開始構(gòu)建支配樹障癌，再次輪到3求直接支配點(diǎn)凌外，因?yàn)?的直接支配點(diǎn)上一次已經(jīng)求得是1，所以3最終的支配點(diǎn)就是1涛浙。
6. 在構(gòu)造過程中所有節(jié)點(diǎn)的支配點(diǎn)未改變康辑，結(jié)束支配樹的構(gòu)造摄欲。
   可以看到通過這種迭代的方式可以求得最終的構(gòu)造樹，但是缺點(diǎn)也顯而易見疮薇，如果有向圖過于復(fù)雜胸墙，時間復(fù)雜度會爆炸增長。其實(shí)構(gòu)造支配樹有一張更優(yōu)的算法按咒，Lengauer-Tarjan算法迟隅，不過我并沒有去研究過，感興趣的小伙伴可以去研究下胖齐。

3.4 Retained Size的計(jì)算

支配樹構(gòu)造完畢以后將每個對象的Shallow size加到各自的直接支配點(diǎn)上去就是某個對象的Retained Size大小玻淑。
上面就是HAHA庫構(gòu)造支配樹和Reatined Size的整體流程嗽冒。下面是代碼實(shí)現(xiàn)：
//構(gòu)建支配樹并計(jì)算retainedSize

public void computeDominators() {
    if (mDominators == null) {
        //根據(jù)GC ROOT 計(jì)算拓?fù)湫?        mTopSort = TopologicalSort.compute(getGCRoots());
        //根據(jù)拓?fù)湫驑?gòu)建支配樹
        mDominators = new Dominators(this, mTopSort);
        //根據(jù)支配樹計(jì)算retained size
        mDominators.computeRetainedSizes();

        ShortestDistanceVisitor shortestDistanceVisitor = new ShortestDistanceVisitor();
        shortestDistanceVisitor.doVisit(getGCRoots());
    }
}

@NonNull
public static ImmutableList<Instance> compute(@NonNull Iterable<RootObj> roots) {
    TopologicalSortVisitor visitor = new TopologicalSortVisitor();
    visitor.doVisit(roots);
    ImmutableList<Instance> instances = visitor.getOrderedInstances();

    // We add the special sentinel node as the single root of the object graph, to ensure the
    // dominator algorithm terminates when having to choose between two GC roots.
    //設(shè)置一個超級源點(diǎn)
    Snapshot.SENTINEL_ROOT.setTopologicalOrder(0);

    // Set localIDs in the range 1..keys.size(). This simplifies the algorithm & data structures
    // for dominator computation.
    int currentIndex = 0;
     //設(shè)置拓?fù)湫蛱栄交铮瑸楹竺娌檎易罱沧嫦茸鲣亯|
    for (Instance node : instances) {
        node.setTopologicalOrder(++currentIndex);
    }

    return instances;
}

@Override
public void doVisit(Iterable<? extends Instance> startNodes) {
    // root nodes are instances that share the same id as the node they point to.
    // This means that we cannot mark them as visited here or they would be marking
    // the actual root instance
    // TODO RootObj should not be Instance objects
    //將GC root壓棧
    for (Instance node : startNodes) {
        node.accept(this);
    }
    //這里的算法是先根據(jù)右左根的方式放入隊(duì)列
    while (!mStack.isEmpty()) {
        Instance node = mStack.peek();
        //這里會把各自的實(shí)例對象加入棧中
        //如果存在環(huán)，不會再進(jìn)行入棧
        if (mSeen.add(node.getId())) {
            node.accept(this);
        } else {
            mStack.pop();
            //因?yàn)榭赡艽嬖诃h(huán)添坊，所以這里是防止重復(fù)寫入
            if (mVisited.add(node.getId())) {
                mPostorder.add(node);
            }
        }
    }
}
//按照拓?fù)湫蚍聪蛉ト〕?ImmutableList<Instance> getOrderedInstances() {
    return ImmutableList.copyOf(Lists.reverse(mPostorder));
}

/**
 * Kicks off the computation of dominators and retained sizes.
 */
public void computeRetainedSizes() {
    // Initialize retained sizes for all classes and objects, including unreachable ones.
    for (Heap heap : mSnapshot.getHeaps()) {
        for (Instance instance : Iterables.concat(heap.getClasses(), heap.getInstances())) {
            //先重置變成shallow size
            instance.resetRetainedSize();
        }
    }
    //設(shè)置對象的支配點(diǎn)
    computeDominators();
    // We only update the retained sizes of objects in the dominator tree (i.e. reachable).
    for (Instance node : mSnapshot.getReachableInstances()) {
        int heapIndex = mSnapshot.getHeapIndex(node.getHeap());
        // Add the size of the current node to the retained size of every dominator up to the
        // root, in the same heap.
        //計(jì)算某個對象的retained size就是從頂點(diǎn)開始到該對象的所有shallow size之和
        for (Instance dom = node.getImmediateDominator(); dom != Snapshot.SENTINEL_ROOT;
                dom = dom.getImmediateDominator()) {
            dom.addRetainedSize(heapIndex, node.getSize());
        }
    }
}

//圖中可能會存在環(huán)剿另，所以有可能在處理某個點(diǎn)時父節(jié)點(diǎn)還未被處理，也就是沒有支配點(diǎn)贬蛙。
//當(dāng)前的算法是如果父類沒有支配點(diǎn)就先跳過雨女，等父類的支配點(diǎn)計(jì)算完以后再迭代去計(jì)算，
//直到所有計(jì)算完所有的支配點(diǎn)即可阳准。
//缺陷：如果圖很復(fù)雜氛堕，話費(fèi)的時間就會非常龐大。
private void computeDominators() {
    // We need to iterate on the dominator computation because the graph may contain cycles.
    // TODO: Check how long it takes to converge, and whether we need to place an upper bound.
    boolean changed = true;
    //有可能會存在環(huán)野蝇，進(jìn)行迭代計(jì)算
    while (changed) {
        changed = false;
        //把之前排好的拓?fù)湫蜻M(jìn)行對象支配點(diǎn)的設(shè)置
        for (int i = 0; i < mTopSort.size(); i++) {
            Instance node = mTopSort.get(i);
            // Root nodes and nodes immediately dominated by the SENTINEL_ROOT are skipped.
            if (node.getImmediateDominator() != Snapshot.SENTINEL_ROOT) {
                Instance dominator = null;

                //如果有多個指向該對象的引用讼稚，就尋找最近支配點(diǎn)
                for (int j = 0; j < node.getHardReferences().size(); j++) {
                    //拿到指向它的引用
                    Instance predecessor = node.getHardReferences().get(j);
                    if (predecessor.getImmediateDominator() == null) {
                        // If we don't have a dominator/approximation for predecessor, skip it
                        continue;
                    }
                    if (dominator == null) {
                        dominator = predecessor;
                    } else {
                        Instance fingerA = dominator;
                        Instance fingerB = predecessor;
                        //找到最近公共祖先，也就是最近支配點(diǎn)
                        while (fingerA != fingerB) {
                            //這里有個疑問绕沈，如果存在環(huán)的情況下锐想，有可能拿出的支配點(diǎn)是null
                            //會有空指針？
                            if (fingerA.getTopologicalOrder() < fingerB.getTopologicalOrder()) {
                                fingerB = fingerB.getImmediateDominator();
                            } else {
                                fingerA = fingerA.getImmediateDominator();
                            }
                        }
                        dominator = fingerA;
                    }
                }
                //設(shè)置該對象的支配點(diǎn)
                if (node.getImmediateDominator() != dominator) {
                    node.setImmediateDominator(dominator);
                    changed = true;
                }
            }
        }
    }
}

3.最短路徑構(gòu)建：

HAHA庫對于引用鏈的構(gòu)造也比較簡單乍狐，從GC ROOT開始赠摇，利用PriorityQueue先進(jìn)先出的性質(zhì)，將構(gòu)造一條從GC root開始不斷加到實(shí)例變量上的引用鏈浅蚪。下面是實(shí)現(xiàn)

@Override
public void doVisit(Iterable<? extends Instance> startNodes) {
    // root nodes are instances that share the same id as the node they point to.
    // This means that we cannot mark them as visited here or they would be marking
    // the actual root instance
    // TODO RootObj should not be Instance objects
    //將GC root放入隊(duì)列中
    for (Instance node : startNodes) {
        node.accept(this);
    }
    
    while (!mPriorityQueue.isEmpty()) {
        Instance node = mPriorityQueue.poll();
        mVisitDistance = node.getDistanceToGcRoot() + 1;
        mPreviousInstance = node;
        node.accept(this);
    }
}

@Override
public void visitLater(Instance parent, @NonNull Instance child) {
    //如果當(dāng)前child不在隊(duì)列中
    //（是GC ROOT || 指向child的軟引用列表不存在 || 指向chaild的軟引用列表不包括當(dāng)前的parent || child是一個軟引用
    if (mVisitDistance < child.getDistanceToGcRoot() &&
            (parent == null ||
                 child.getSoftReferences() == null ||
                 !child.getSoftReferences().contains(parent) ||
                 child.getIsSoftReference())) {
        child.setDistanceToGcRoot(mVisitDistance);
        child.setNextInstanceToGcRoot(mPreviousInstance);
        mPriorityQueue.add(child);
    }
}