Android 热修复 Tinker 源码分析之DexDiff / DexPatch
每日推荐
昨天很多使用JsPatch的应用开发者都收到了Apple的邮件，很多人担心RN也会遇到同样的问题，可以关注这个issue关注：
https://github.com/facebook/react-native/issues/12778
今天推荐一个开源项目，主要是做MD资源聚合的：
关于 Material Design 的一切资料都在这里
https://github.com/Luosunce/material-design-data
好了，接下来就是正文了，主要是tinker的dex diff和patch相关的源码分析，其实我第一次在MDCC上听说到这个东西觉得难度应该是比较大的，所以博客以方便是为了自己总结，一方面也为了让更多人能看懂了~~
本篇文章巨长，不过相信我，如果你认真看了，以后面试就可以吹吹tinker的源码（开玩笑~），是多么愉快的事情~
在上一篇文章中，我们介绍了Android 热修复 Tinker接入及源码浅析，里面包含了热修的一些背景知识，从tinker对dex文件的处理来看，源码大体上可以分为3部分阅读：
在应用中对patch的合并与加载，已经在上篇文章中详细介绍过了Android 热修复 Tinker接入及源码浅析
详细的dex patch，dex diff算法
tinker gradle plugin相关知识
tinker有个非常大的亮点就是自研发了一套dex diff、patch相关算法。本篇文章主要目的就是分析该算法。当然值得注意的是，分析的前提就是需要对dex文件的格式要有一定的认识，否则的话可能会一脸懵逼态。
所以，本文会先对dex文件格式做一个简单的分析，也会做一些简单的实验，最后进入到dex diff,patch算法部分。
首先简单了解下Dex文件，大家在反编译的时候，都清楚apk中会包含一个或者多个*.dex文件，该文件中存储了我们编写的代码，一般情况下我们还会通过工具转化为jar，然后通过一些工具反编译查看。
jar文件大家应该都清楚，类似于class文件的压缩包，一般情况下，我们直接解压就可以看到一个个class文件。而dex文件我们无法通过解压获取内部的一个个class文件，说明dex文件拥有自己特定的格式：
dex对Java类文件重新排列，将所有JAVA类文件中的常量池分解，消除其中的冗余信息，重新组合形成一个常量池，所有的类文件共享同一个常量池，使得相同的字符串、常量在DEX文件中只出现一次，从而减小了文件的体积。引自：http://blog.csdn.net/jason0539/article/details/50440669
接下来我们看看dex文件的内部结构到底是什么样子。
分析一个文件的组成，最好自己编写一个最简单的dex文件来分析。
（1）编写代码生成dex
首先我们编写一个类Hello.java：
然后进行编译：
javac -source 1.7 -target 1.7 Hello.java最后通过dx工作将其转化为dex文件：
dx --dex --output=Hello.dex Hello.classdx路径在android-sdk/build-tools/版本号/dx下，如果无法识别dx命令，记得将该路径放到path下，或者使用绝对路径。
这样我们就得到了一个非常简单的dex文件。
（2）查看dex文件的内部结构
首先展示一张dex文件的大致的内部结构图：
该图来自dodola的tinker文章(https://www.zybuluo.com/dodola/note/554061)->
当然，单纯从一张图来说明肯定是远远不够的，因为我们后续要研究diff，patch算法，理论上我们应该要知道更多的细节，甚至要细致到：一个dex文件的每个字节表示的是什么内容。
对于一个类似于二进制的文件，最好的办法肯定不是靠记忆，好在有这么一个软件可以帮助我们的分析：
软件名称：010 Editor
下载地址：http://www.sweetscape.com/010editor/
下载完成安装后，打开我们的dex文件，会引导你安装dex文件的解析模板。
最终打开效果图如下：
上面部分代表了dex文件的内容（16进制的方式展示），下面部分展示了dex文件的各个区域，你可以通过点击下面部分，来查看其对应的内容区域以及内容。
当然这里也非常建议，阅读一些专门的文章来加深对dex文件的理解：
DEX文件格式分析(https://segmentfault.com/a/1190000007652937#articleHeader0)
Android逆向之旅---解析编译之后的Dex文件格式(http://blog.csdn.net/jiangwei0910410003/article/details/50668549)
本文也仅会对dex文件做简单的格式分析。
（3）dex文件内部结构简单分析
dex_header
首先我们队dex_header做一个大致的分析，header中包含如下字段：
首先我们猜测下header的作用，可以看到起包含了一些校验相关的字段，和整个dex文件大致区块的分布(off都为偏移量)。
这样的好处就是，当虚拟机读取dex文件时，只需要读取出header部分，就可以知道dex文件的大致区块分布了；并且可以检验出该文件格式是否正确、文件是否被篡改等。
magic能够证明该文件是dex文件
checksum和signature主要用于校验文件的完整性
file_size为dex文件的大小
head_size为头文件的大小
endian_tag预设值为12345678，标识默认采用Little-Endian(自行搜索)。
剩下的几乎都是成对出现的size和off，大多代表各区块的包含的特定数据结构的数量和偏移量。例如：string_ids_off为112，指的是偏移量112开始为string_ids区域；string_ids_size为14，代表string_id_item的数量为14个。剩下的都类似就不介绍了。
结合010Editor可以看到各个区域包含的数据结构，以及对应的值，慢慢看就好了。
dex_map_list
除了header还有个比较重要的部分是dex_map_list，首先看个图：
首先是map_item_list数量，接下来是每个map_item_list的描述。
map_item_list有什么用呢？
可以看到每个map_list_item包含一个枚举类型，一个2字节暂未使用的成员、一个size表明当前类型的个数，offset表明当前类型偏移量。
拿本例来说：
首先是TYPE_HEADER_ITEM类型，包含1个header(size=1)，且偏移量为0。
接下来是TYPE_STRING_ID_ITEM，包含14个string_id_item（size=14），且偏移量为112（如果有印象，header的长度为112，紧跟着header）。
剩下的依次类推~~
这样的话，可以看出通过map_list，可以将一个完整的dex文件划分成固定的区域（本例为13），且知道每个区域的开始，以及该区域对应的数据格式的个数。
通过map_list找到各个区域的开始，每个区域都会对应特定的数据结构，通过010 Editor看就好了。
现在我们了解了dex的基本格式，接下来我们考虑下如何做dex diff 和 patch。
先要考虑的是我们有什么：
old dex
new dex
我们想要生成一个patch文件，该文件和old dex 通过patch算法还能生成new dex。
那么我们该如何做呢？
根据上文的分析，我们知道dex文件大致有3个部分(这里3个部分主要用于分析，勿较真)：
header
各个区域
map list
header实际上是可以根据后面的数据确定其内容的，并且是定长112的；各个区域后面说；map list实际上可以做到定位到各个区域开始位置。
我们最终patch + old dex -> new dex；针对上述的3个部分，
header我们可以不做处理，因为可以根据其他数据生成；
map list这个东西，其实我们主要要的是各个区域的开始(offset)
知道了各个区域的offset后，在我们生成new dex的时候，我们就可以定位各个区域的开始和结束位置，那么只需要往各个区域写数据即可。
那么我们看看针对一个区域的diff，假设有个string区域，主要用于存储字符串：
old dex该区域的字符串有： Hello、World、zhy
new dex该区域的字符串有： Android、World、zhy
可以看出，针对该区域，我们删除了Hello，增加了Android、zhy。
那么patch中针对该区域可以如下记录：
"del Hello , add Android、zhy"（实际情况需要转化为二进制）。
想想应用中可以直接读取出old dex，即知道:
原来该区域包含：Hello、World、zhy
patch中该区域包含："del Hello , add Android、zhy"
那么，可以非常容易的计算出new dex中包含：
Android、World、zhy。
这样我们就完成了一个区域大致的diff和patch算法，其他各个区域的diff和patch和上述类似。
这样来看，是不是觉得这个diff和patch算法也没有那么的复杂，实际上tinker的做法与上述类似，实际情况可能要比上述描述要复杂一些，但是大体上是差不多的。
有了一个大致的算法概念之后，我们就可以去看源码了。
tinker的地址：
https://github.com/Tencent/tinker
这里看代码实际上也是有技巧的，tinker的代码实际上蛮多的，往往你可以会陷在一堆的代码中。我们可以这么考虑，比如diff算法，输入参数为old dex 、new dex，输出为patch file。
那么肯定存在某个类，或者某个方法接受和输出上述参数。实际上该类为DexPatchGenerator：
diff的API使用代码为：
代码在tinker-build的tinker-patch-lib下。
写一个单元测试或者main方法，上述几行代码就是diff算法。
所以查看代码时要有针对性，比如看diff算法，就找到diff算法的入口，不要在gradle plugin中去纠结。
（1）dex file => Dex
将我们传入的dex文件转化为了Dex对象。
首先将我们的文件读取为byte[]数组（这里还是蛮耗费内存的），然后由ByteBuffer进行包装，并设置字节顺序为小端（这里说明ByteBuffer还是蛮方便的。
然后通过readFrom方法为Dex对象的tableOfContents赋值。
在其内部执行了readHeader和readMap，上文我们大致分析了header和map list相关，实际上就是将这两个区域转化为一定的数据结构，读取然后存储到内存中。
首先看readHeader:
如果你现在打开着010 Editor，或者看一眼最前面的图，实际上就是将header中所有的字段定义出来，读取响应的字节并赋值。
接下来看readMap:
这里注意，在读取header的时候，实际上已经读取除了map list区域的offset，并存储在mapList.off中。所以map list中实际上是从这个位置开始的。
首先读取的就是map_list_item的个数，接下来读取的就是每个map_list_item对应的实际数据。
可以看到依次读取：type,unused,size,offset，如果你还有印象前面我们描述了map_list_item是与此对应的，对应的数据结构为TableContents.Section对象。
computeSizesFromOffsets()主要为section的byteCount（占据了多个字节）参数赋值。
到这里就完成了dex file 到 Dex对象的初始化。
有了两个Dex对象之后，就需要去做diff操作了。
（2）dex diff
继续回到源码：
直接到两个Dex对象的构造函数：
看到其首先为oldDex,newDex赋值，然后依次初始化了15个算法，每个算法代表每个区域，算法的目的就像我们之前描述的那样，要知道“删除了哪些，新增了哪些”；
我们继续看代码:
dexPatchGenerator
.executeAndSaveTo(patchFile);有了dexPatchGenerator对象后，直接指向了executeAndSaveTo方法。
到executeAndSaveTo方法：
因为涉及到15个算法，所以这里的代码非常长，我们这里只拿其中一个算法来说明。
每个算法都会执行execute和simulatePatchOperation方法：
首先看execute:
可以看到首先读取oldDex和newDex对应区域的数据并排序，分别adjustedOldIndexedItems和adjustedNewIndexedItems。
接下来就开始遍历了，直接看else部分：
分别根据当前的cursor，获取oldItem和newItem，对其value对对比：
如果<0 ,则认为该old Item被删除了，记录为PatchOperation.OP_DEL，并记录该oldItem index到PatchOperation对象，加入到patchOperationList中。
如果>0,则认为该newItem是新增的，记录为PatchOperation.OP_ADD，并记录该newItem index和value到PatchOperation对象，加入到patchOperationList中。
如果=0,不会生成PatchOperation。
经过上述，我们得到了一个patchOperationList对象。
继续下半部分代码：
首先对patchOperationList按照index排序，如果index一致则先DEL、后ADD。
接下来一个对所有的operation的迭代，主要将index一致的，且连续的DEL、ADD转化为REPLACE操作。
最后将patchOperationList转化为3个Map，分别为：indexToDelOperationMap，indexToAddOperationMap,indexToReplaceOperationMap。
ok，经历完成execute之后，我们主要的产物就是3个Map，分别记录了：oldDex中哪些index需要删除；newDex中新增了哪些item；哪些item需要替换为新item。
刚才说了每个算法除了execute()还有个simulatePatchOperation()
传入的偏移量为data区域的偏移量。
遍历oldIndex与newIndex，分别在indexToAddOperationMap,indexToReplaceOperationMap,indexToDelOperationMap中查找。
这里关注一点最终的一个产物是this.patchedSectionSize，由patchedOffset-baseOffset所得。
这里有几种情况会造成patchedOffset+=itemSize：
indexToAddOperationMap中包含patchIndex
indexToReplaceOperationMap包含patchIndex
不在indexToDelOperationMap与indexToReplaceOperationMap中的oldDex.
其实很好理解，这个patchedSectionSize其实对应newDex的这个区域的size。所以，包含需要ADD的Item，会被替代的Item，以及OLD ITEMS中没有被删除和替代的Item。
这三者相加即为newDex的itemList。
到这里，一个算法就执行完毕了。
经过这样的一个算法，我们得到了PatchOperationList和对应区域sectionSize。那么执行完成所有的算法，应该会得到针对每个算法的PatchOperationList，和每个区域的sectionSize；每个区域的sectionSize实际上换算得到每个区域的offset。
每个区域的算法，execute和simulatePatchOperation代码都是复用的，所以其他的都只有细微的变化，可以自己看了。
接下来看执行完成所有的算法后的writeResultToStream方法。
(3) 生成patch文件
首先写了MAGIC，CURRENT_VERSION主要用于检查该文件为合法的tinker patch 文件。
然后写入patchedDexSize
第四位写入的是数据区的offset，可以看到先使用0站位，等所有的map list相关的offset书写结束，写入当前的位置。
接下来写入所有的跟maplist各个区域相关的offset（这里各个区域的排序不重要，读写一致即可）
然后执行每个算法写入对应区域的信息
最后生成patch文件
我们依旧只看stringDataSectionDiffAlg这个算法。
首先将我们的patchOperationList转化为3个OpIndexList，分别对应DEL,ADD,REPLACE，以及将所有的item存入newItemList。
然后依次写入：
del操作的个数，每个del的index
add操作的个数，每个add的index
replace操作的个数，每个需要replace的index
最后依次写入newItemList.
这里index都做了（这里做了个index - lastIndex操作）
其他的算法也是执行了类似的操作。
最好来看看我们生成的patch是什么样子的：
首先包含几个字段，证明自己是tinker patch
包含生成newDex各个区域的offset，即可以将newDex划分了多个区域，定位到起点
包含newDex各个区域的Item的删除的索引(oldDex)，新增的索引和值，替换的索引和值
那么这么看，我们猜测Patch的逻辑时这样的：
首先根据各个区域的offset，确定各个区域的起点
读取oldDex各个区域的items，然后根据patch中去除掉oldDex中需要删除的和需要替换的item，再加上新增的item和替换的item即可组成newOld该区域的items。
即，newDex的某个区域的包含：
oldItems - del - replace + addItems + replaceItems这么看挺清晰的，下面看代码咯~
（1）寻找入口
与diff一样，肯定有那么一个类或者方法，接受old dex File 和 patch File，最后生成new Dex。不要陷在一堆安全校验，apk解压的代码中。
这个类叫做DexPatchApplier,在tinker-commons中。
patch的相关代码如下：
可以看到和diff代码类似，下面看代码去。
（2）源码分析
oldDex会转化为Dex对象，这个上面分析过，主要就是readHeader和readMap.注意我们的patchFile是转为一个DexPatchFile对象。
首先将patch file读取为byte[]，然后调用init
还记得我们写patch的操作么，先写了MAGIC和Version用于校验该文件是一个patch file；接下来为patchedDexSize和各种offset进行赋值；
最后定位到数据区（firstChunkOffset），还记得写的时候，该字段在第四个位置。
定位到该位置后，后面读取的就是数据了，数据存的时候按照如下格式存储的：
del操作的个数，每个del的index
add操作的个数，每个add的index
replace操作的个数，每个需要replace的index
最后依次写入newItemList.
简单回忆下，我们继续源码分析。
除了oldDex,patchFile,还初始化了一个patchedDex作为我们最终输出Dex对象。
构造完成后，直接执行了executeAndSaveTo方法。
直接到executeAndSaveTo(os),该方法代码比较长，我们分3段讲解：
这里实际上，就是读取patchFile中记录的值给patchedDex的TableOfContent中各种Section(大致对应map list中各个map_list_item)赋值。
接下来排序呢，设置byteCount等字段信息。
继续：
这一部分很明显初始化了一堆算法，然后分别去执行。我们依然是拿stringDataSectionPatchAlg来分析。
再贴一下我们写入时的规则：
del操作的个数，每个del的index
add操作的个数，每个add的index
replace操作的个数，每个需要replace的index
最后依次写入newItemList.
看代码，读取顺序如下：
del的数量，del的所有的index存储在一个int[]中；
add的数量，add的所有的index存储在一个int[]中；
replace的数量，replace的所有的index存储在一个int[]中；
是不是和写入时一致。
继续，接下来获取了oldDex中oldItems和oldItemCount。
那么现在有了：
del count and indices
add count add indices
replace count and indices
oldItems and oldItemCount
拿着我们拥有的，继续执行doFullPatch
先整体上看一下，这里的目的就是往patchedDex的stringData区写数据，写的数据理论上应该是：
新增的数据
替代的数据
oldDex中出去新增和被替代的数据
当然他们需要顺序写入。
所以看代码，首先计算出newItemCount=oldItemCount + addCount - delCount，然后开始遍历，遍历条件为0~oldItemCount或0~newItemCount。
我们期望的是，在patchIndex从0~newItemCount之间都会写入对应的Item。
Item写入通过代码我们可以看到：
首先判断该patchIndex是否包含在addIndices中，如果包含则写入；
再者判断是否在repalceIndices中，如果包含则写入；
然后判断如果发现oldIndex被delete或者replace，直接跳过；
那么最后一个index指的就是，oldIndex为非delete和replace的，也就是和newDex中items相同的部分。
上述1.2.4三个部分即可组成完整的newDex的该区域。
这样的话就完成了stringData区域的patch算法。
其他剩下的14个算法的execute代码是相同的（父类），执行的操作类似，都会完成各个部分的patch算法。
当所有的区域都完成恢复后，那么剩下的就是header和mapList了，所以回到所有算法执行完成的地方：
定位到header区域，写header相关数据；定位到map list区域，编写map list相关数据。两者都完成的时候，需要编写header中比较特殊的两个字段：签名和checkSum,因为这两个字段是依赖map list的，所以必须在编写map list后。
这样就完成了完整的dex的恢复，最后将内存中的所有数据写到文件中。
（1）dex准备
刚才我们有个Hello.dex，我们再编写一个类：
然后将这个类编译以及打成dx文件。
javac -source 1.7 -target 1.7 World.java
dx --dex --output=World.dex World.class这样我们就准备好了两个dex，Hello.dex和World.dex.
(2) diff
使用010 Editor分别打开两个dex，我们主要关注string_id_item；
两边分别13个字符串，按照我们上面介绍的diff算法，我们可以得到以下操作：
两边的字符串分别开始遍历对比：
如果<0 ,则认为该old Item被删除了，记录为PatchOperation.OP_DEL，并记录该oldItem index到PatchOperation对象，加入到patchOperationList中。
如果>0,则认为该newItem是新增的，记录为PatchOperation.OP_ADD，并记录该newItem index和value到PatchOperation对象，加入到patchOperationList中。
如果=0,不会生成PatchOperation。
del 1
add 1 LWorld;
del 2
add 8 World.java
del 10
add 11 naniWorld然后是根据索引排序，没有变化；
接下来遍历所有的操作，将index一致且DEL和ADD相邻的操作替换为replace
replace 1 LWorld
del 2
add 8 World.java
del 10
add 11 naniWorld最终在write时，会做一次遍历，将操作按DEL,ADD,REPLACE进行分类，并且将出现的item放置到newItemList中。
del ops:
del 2
del 10
add ops:
add 8
add 11
replace ops:
replace 1newItemList变为：
LWorld //replace 1
World.java //add 8
naniWorld //add 11然后写入，那么写入的顺序应该是：
2 //del size
2
8 // index - lastIndex
2 // add size
8
3 // index - lastIndex
1 //replace size
1
LWorld
World.java
naniWorld这里我们直接在DexPatchGenerator的writeResultToStream的相关位置打上日志：
可以看到输出为：
del size = 2
del index = 2
del index = 8
add size = 2
add index = 8
add index = 3
replace size = 2
replace index = 1
stringdata = LWorld;
stringdata = World.java
stringdata = nani World与我们上述分析结果一致 ~~
那么其他区域可以用类似的方式去验证，patch的话也差不多，就不赘述了。
文章太长了，能看到这里的人应该不多，本来想把源码分析在微信上省去的，但是考虑文章完整性损失会比较大，所以硬着头皮编辑完了~~~
千万要看呀~~不然多浪费！
参考
http://blog.csdn.net/jason0539/article/details/50440669
https://www.zybuluo.com/dodola/note/554061
https://segmentfault.com/a/1190000007652937#articleHeader0
https://github.com/Tencent/tinker
优秀人才不缺工作机会，只缺适合自己的好机会。但是他们往往没有精力从海量机会中找到最适合的那个。
100offer 会对平台上的人才和企业进行严格筛选，让「最好的人才」和「最好的公司」相遇。
扫描下方二维码，注册 100offer，谈谈你对下一份工作的期待。一周内，收到 5-10 个满足你要求的好机会！
如果你有想学习的文章直接留言，我会整理征稿。如果你有好的文章想和大家分享欢迎投稿，直接向我投递文章链接即可。
欢迎长按下图->识别图中二维码或者扫一扫关注我的公众号：