Android编程之Android热修复Tinker源码分析之DexDiff / DexPatch-职坐标

Android编程之Android热修复Tinker源码分析之DexDiff / DexPatch

安安 2017-10-11 来源：网络阅读 609 评论 0

摘要：本篇Android编程程教程将为大家讲解Android编程的知识点，看完这篇文章会让你对Android编程的知识点有更加清晰的理解和运用。

本篇Android编程程教程将为大家讲解Android编程的知识点，看完这篇文章会让你对Android编程的知识点有更加清晰的理解和运用。

在上一篇文章中，我们介绍了Android 热修复 Tinker接入及源码浅析，里面包含了热修的一些背景知识，从tinker对dex文件的处理来看，源码大体上可以分为3部分阅读：

1. 在应用中对patch的合并与加载，已经在上篇文章中详细介绍过了Android 热修复 Tinker接入及源码浅析

2. 详细的dex patch，dex diff算法

3. tinker gradle plugin相关知识

tinker有个非常大的亮点就是自研发了一套dex diff、patch相关算法。本篇文章主要目的就是分析该算法。当然值得注意的是，分析的前提就是需要对dex文件的格式要有一定的认识，否则的话可能会一脸懵逼态。

所以，本文会先对dex文件格式做一个简单的分析，也会做一些简单的实验，最后进入到dex diff,patch算法部分。

一、Dex文件格式浅析

首先简单了解下Dex文件，大家在反编译的时候，都清楚apk中会包含一个或者多个*.dex文件，该文件中存储了我们编写的代码，一般情况下我们还会通过工具转化为jar，然后通过一些工具反编译查看。

jar文件大家应该都清楚，类似于class文件的压缩包，一般情况下，我们直接解压就可以看到一个个class文件。而dex文件我们无法通过解压获取内部的一个个class文件，说明dex文件拥有自己特定的格式：

dex对Java类文件重新排列，将所有JAVA类文件中的常量池分解，消除其中的冗余信息，重新组合形成一个常量池，所有的类文件共享同一个常量池，使得相同的字符串、常量在DEX文件中只出现一次，从而减小了文件的体积。引自：//blog.csdn.net/jason0539/article/details/50440669

接下来我们看看dex文件的内部结构到底是什么样子。

分析一个文件的组成，最好自己编写一个最简单的dex文件来分析。

（1）编写代码生成dex

首先我们编写一个类Hello.java：

public class Hello{

public static void main(String[] args){

System.out.println("hello dex！");

}

然后进行编译：

javac -source 1.7 -target 1.7 Hello.java

最后通过dx工作将其转化为dex文件：

dx --dex --output=Hello.dex Hello.class

dx路径在Android-sdk/build-tools/版本号/dx下，如果无法识别dx命令，记得将该路径放到path下，或者使用绝对路径。

这样我们就得到了一个非常简单的dex文件。

（2）查看dex文件的内部结构

首先展示一张dex文件的大致的内部结构图：

Android编程之Android热修复Tinker源码分析之DexDiff / DexPatch

该图来自dodola的tinker文章->AloneMonkey 的博客

当然，单纯从一张图来说明肯定是远远不够的，因为我们后续要研究diff，patch算法，理论上我们应该要知道更多的细节，甚至要细致到：一个dex文件的每个字节表示的是什么内容。

对于一个类似于二进制的文件，最好的办法肯定不是靠记忆，好在有这么一个软件可以帮助我们的分析：

· 软件名称：010 Editor

· 下载地址：//www.sweetscape.com/010editor/

下载完成安装后，打开我们的dex文件，会引导你安装dex文件的解析模板。

最终打开效果图如下：

Android编程之Android热修复Tinker源码分析之DexDiff / DexPatch

上面部分代表了dex文件的内容（16进制的方式展示），下面部分展示了dex文件的各个区域，你可以通过点击下面部分，来查看其对应的内容区域以及内容。

当然这里也非常建议，阅读一些专门的文章来加深对dex文件的理解：

· DEX文件格式分析

· Android逆向之旅—解析编译之后的Dex文件格式

本文也仅会对dex文件做简单的格式分析。

（3）dex文件内部结构简单分析

dex_header

首先我们队dex_header做一个大致的分析，header中包含如下字段：

Android编程之Android热修复Tinker源码分析之DexDiff / DexPatch

首先我们猜测下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，首先看个图：

Android编程之Android热修复Tinker源码分析之DexDiff / DexPatch

首先是map_item_list数量，接下来是每个map_item_list的描述。

map_item_list有什么用呢？

Android编程之Android热修复Tinker源码分析之DexDiff / DexPatch

可以看到每个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。

先要考虑的是我们有什么：

1. old dex

2. new dex

我们想要生成一个patch文件，该文件和old dex 通过patch算法还能生成new dex。

· 那么我们该如何做呢？

根据上文的分析，我们知道dex文件大致有3个部分(这里3个部分主要用于分析，勿较真)：

1. header

2. 各个区域

3. 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。

那么patch中针对该区域可以如下记录：
“del Hello , add Android”（实际情况需要转化为二进制）。

想想应用中可以直接读取出old dex，即知道:

· 原来该区域包含：Hello、World、zhy

· patch中该区域包含：”del Hello , add Android”

那么，可以非常容易的计算出new dex中包含：

Android、World、zhy。

这样我们就完成了一个区域大致的diff和patch算法，其他各个区域的diff和patch和上述类似。

这样来看，是不是觉得这个diff和patch算法也没有那么的复杂，实际上tinker的做法与上述类似，实际情况可能要比上述描述要复杂一些，但是大体上是差不多的。

有了一个大致的算法概念之后，我们就可以去看源码了。

三、Tinker DexDiff源码浅析

tinker的地址：https://github.com/Tencent/tinker

这里看代码实际上也是有技巧的，tinker的代码实际上蛮多的，往往你可以会陷在一堆的代码中。我们可以这么考虑，比如diff算法，输入参数为old dex 、new dex，输出为patch file。

那么肯定存在某个类，或者某个方法接受和输出上述参数。实际上该类为DexPatchGenerator：

diff的API使用代码为：

@Testpublic void testDiff() throws IOException {

File oldFile = new File("Hello.dex");

File newFile = new File("Hello-World.dex");

File patchFile = new File("patch.dex");

DexPatchGenerator dexPatchGenerator

= new DexPatchGenerator(oldFile, newFile);

dexPatchGenerator.executeAndSaveTo(patchFile);

}

代码在tinker-build的tinker-patch-lib下。

写一个单元测试或者main方法，上述几行代码就是diff算法。

所以查看代码时要有针对性，比如看diff算法，就找到diff算法的入口，不要在gradle plugin中去纠结。

（1）dex file => Dex

public DexPatchGenerator(File oldDexFile, File newDexFile) throws IOException {

this(new Dex(oldDexFile), new Dex(newDexFile));

}

将我们传入的dex文件转化为了Dex对象。

public Dex(File file) throws IOException {

// 删除了一堆代码

InputStream in = new BufferedInputStream(new FileInputStream(file));

loadFrom(in, (int) file.length());

}

private void loadFrom(InputStream in, int initSize) throws IOException {

byte[] rawData = FileUtils.readStream(in, initSize);

this.data = ByteBuffer.wrap(rawData);

this.data.order(ByteOrder.LITTLE_ENDIAN);

this.tableOfContents.readFrom(this);

}

首先将我们的文件读取为byte[]数组（这里还是蛮耗费内存的），然后由ByteBuffer进行包装，并设置字节顺序为小端（这里说明ByteBuffer还是蛮方便的。然后通过readFrom方法为Dex对象的tableOfContents赋值。

#TableOfContentspublic void readFrom(Dex dex) throws IOException {

readHeader(dex.openSection(header));

// special case, since mapList.byteCount is available only after

// computeSizesFromOffsets() was invoked, so here we can't use

// dex.openSection(mapList) to get dex section. Or

// an {@code java.nio.BufferUnderflowException} will be thrown.

readMap(dex.openSection(mapList.off));

computeSizesFromOffsets();

}

在其内部执行了readHeader和readMap，上文我们大致分析了header和map list相关，实际上就是将这两个区域转化为一定的数据结构，读取然后存储到内存中。

首先看readHeader:

private void readHeader(Dex.Section headerIn) throws UnsupportedEncodingException {

byte[] magic = headerIn.readByteArray(8);

int apiTarget = DexFormat.magicToApi(magic);

if (apiTarget != DexFormat.API_NO_EXTENDED_OPCODES) {

throw new DexException("Unexpected magic: " + Arrays.toString(magic));

}

checksum = headerIn.readInt();

signature = headerIn.readByteArray(20);

fileSize = headerIn.readInt();

int headerSize = headerIn.readInt();

if (headerSize != SizeOf.HEADER_ITEM) {

throw new DexException("Unexpected header: 0x" + Integer.toHexString(headerSize));

}

int endianTag = headerIn.readInt();

if (endianTag != DexFormat.ENDIAN_TAG) {

throw new DexException("Unexpected endian tag: 0x" + Integer.toHexString(endianTag));

}

linkSize = headerIn.readInt();

linkOff = headerIn.readInt();

mapList.off = headerIn.readInt();

if (mapList.off == 0) {

throw new DexException("Cannot merge dex files that do not contain a map");

}

stringIds.size = headerIn.readInt();

stringIds.off = headerIn.readInt();

typeIds.size = headerIn.readInt();

typeIds.off = headerIn.readInt();

protoIds.size = headerIn.readInt();

protoIds.off = headerIn.readInt();

fieldIds.size = headerIn.readInt();

fieldIds.off = headerIn.readInt();

methodIds.size = headerIn.readInt();

methodIds.off = headerIn.readInt();

classDefs.size = headerIn.readInt();

classDefs.off = headerIn.readInt();

dataSize = headerIn.readInt();

dataOff = headerIn.readInt();

}

如果你现在打开着010 Editor，或者看一眼最前面的图，实际上就是将header中所有的字段定义出来，读取响应的字节并赋值。

接下来看readMap:

private void readMap(Dex.Section in) throws IOException {

int mapSize = in.readInt();

Section previous = null;

for (int i = 0; i < mapSize; i++) {

short type = in.readShort();

in.readShort(); // unused

Section section = getSection(type);

int size = in.readInt();

int offset = in.readInt();

section.size = size;

section.off = offset;

previous = section;

}

header.off = 0;

Arrays.sort(sections);

// Skip header section, since its offset must be zero.

for (int i = 1; i < sections.length; ++i) {

if (sections[i].off == Section.UNDEF_OFFSET) {

sections[i].off = sections[i - 1].off;

}

这里注意，在读取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

继续回到源码：

public DexPatchGenerator(File oldDexFile, InputStream newDexStream) throws IOException {

this(new Dex(oldDexFile), new Dex(newDexStream));

}

直接到两个Dex对象的构造函数：

public DexPatchGenerator(Dex oldDex, Dex newDex) {

this.oldDex = oldDex;

this.newDex = newDex;

SparseIndexMap oldToNewIndexMap = new SparseIndexMap();

SparseIndexMap oldToPatchedIndexMap = new SparseIndexMap();

SparseIndexMap newToPatchedIndexMap = new SparseIndexMap();

SparseIndexMap selfIndexMapForSkip = new SparseIndexMap();

additionalRemovingClassPatternSet = new HashSet<>();

this.stringDataSectionDiffAlg = new StringDataSectionDiffAlgorithm(

oldDex, newDex,

oldToNewIndexMap,

oldToPatchedIndexMap,

newToPatchedIndexMap,

selfIndexMapForSkip

);

this.typeIdSectionDiffAlg = ...

this.protoIdSectionDiffAlg = ...

this.fieldIdSectionDiffAlg = ...

this.methodIdSectionDiffAlg = ...

this.classDefSectionDiffAlg = ...

this.typeListSectionDiffAlg = ...

this.annotationSetRefListSectionDiffAlg = ...

this.annotationSetSectionDiffAlg = ...

this.classDataSectionDiffAlg = ...

this.codeSectionDiffAlg = ...

this.debugInfoSectionDiffAlg = ...

this.annotationSectionDiffAlg = ...

this.encodedArraySectionDiffAlg = ...

this.annotationsDirectorySectionDiffAlg = ...

}

看到其首先为oldDex,newDex赋值，然后依次初始化了15个算法，每个算法代表每个区域，算法的目的就像我们之前描述的那样，要知道“删除了哪些，新增了哪些”；

我们继续看代码:

dexPatchGenerator.executeAndSaveTo(patchFile);

有了dexPatchGenerator对象后，直接指向了executeAndSaveTo方法。

public void executeAndSaveTo(File file) throws IOException {

OutputStream os = null;

try {

os = new BufferedOutputStream(new FileOutputStream(file));

executeAndSaveTo(os);

} finally {

if (os != null) {

try {

os.close();

} catch (Exception e) {

// ignored.

}

到executeAndSaveTo方法：

public void executeAndSaveTo(OutputStream out) throws IOException {

int patchedheaderSize = SizeOf.HEADER_ITEM;

int patchedStringIdsSize = newDex.getTableOfContents().stringIds.size * SizeOf.STRING_ID_ITEM;

int patchedTypeIdsSize = newDex.getTableOfContents().typeIds.size * SizeOf.TYPE_ID_ITEM;

int patchedProtoIdsSize = newDex.getTableOfContents().protoIds.size * SizeOf.PROTO_ID_ITEM;

int patchedFieldIdsSize = newDex.getTableOfContents().fieldIds.size * SizeOf.MEMBER_ID_ITEM;

int patchedMethodIdsSize = newDex.getTableOfContents().methodIds.size * SizeOf.MEMBER_ID_ITEM;

int patchedClassDefsSize = newDex.getTableOfContents().classDefs.size * SizeOf.CLASS_DEF_ITEM;

int patchedIdSectionSize =

patchedStringIdsSize

+ patchedTypeIdsSize

+ patchedProtoIdsSize

+ patchedFieldIdsSize

+ patchedMethodIdsSize

+ patchedClassDefsSize;

this.patchedHeaderOffset = 0;

this.patchedStringIdsOffset = patchedHeaderOffset + patchedheaderSize;

this.stringDataSectionDiffAlg.execute();

this.patchedStringDataItemsOffset = patchedheaderSize + patchedIdSectionSize;

this.stringDataSectionDiffAlg.simulatePatchOperation(this.patchedStringDataItemsOffset);

// 省略了其余14个算法的一堆代码

this.patchedDexSize

= this.patchedMapListOffset

+ patchedMapListSize;

writeResultToStream(out);

}

因为涉及到15个算法，所以这里的代码非常长，我们这里只拿其中一个算法来说明。

每个算法都会执行execute和simulatePatchOperation方法：

首先看execute:

public void execute() {

this.patchOperationList.clear();

// 1. 拿到oldDex和newDex的itemList

this.adjustedOldIndexedItemsWithOrigOrder = collectSectionItems(this.oldDex, true);

this.oldItemCount = this.adjustedOldIndexedItemsWithOrigOrder.length;

AbstractMap.SimpleEntry<Integer, T>[] adjustedOldIndexedItems = new AbstractMap.SimpleEntry[this.oldItemCount];

System.arraycopy(this.adjustedOldIndexedItemsWithOrigOrder, 0, adjustedOldIndexedItems, 0, this.oldItemCount);

Arrays.sort(adjustedOldIndexedItems, this.comparatorForItemDiff);

AbstractMap.SimpleEntry<Integer, T>[] adjustedNewIndexedItems = collectSectionItems(this.newDex, false);

this.newItemCount = adjustedNewIndexedItems.length;

Arrays.sort(adjustedNewIndexedItems, this.comparatorForItemDiff);

int oldCursor = 0;

int newCursor = 0;

// 2.遍历，对比，收集patch操作

while (oldCursor < this.oldItemCount || newCursor < this.newItemCount) {

if (oldCursor >= this.oldItemCount) {

// rest item are all newItem.

while (newCursor < this.newItemCount) {

// 对剩下的newItem做ADD操作

}

} else if (newCursor >= newItemCount) {

// rest item are all oldItem.

while (oldCursor < oldItemCount) {

// 对剩下的oldItem做DEL操作

}

} else {

AbstractMap.SimpleEntry<Integer, T> oldIndexedItem = adjustedOldIndexedItems[oldCursor];

AbstractMap.SimpleEntry<Integer, T> newIndexedItem = adjustedNewIndexedItems[newCursor];

int cmpRes = oldIndexedItem.getValue().compareTo(newIndexedItem.getValue());

if (cmpRes < 0) {

int deletedIndex = oldIndexedItem.getKey();

int deletedOffset = getItemOffsetOrIndex(deletedIndex, oldIndexedItem.getValue());

this.patchOperationList.add(new PatchOperation<T>(PatchOperation.OP_DEL, deletedIndex));

markDeletedIndexOrOffset(this.oldToPatchedIndexMap, deletedIndex, deletedOffset);

++oldCursor;

} else if (cmpRes > 0) {

this.patchOperationList.add(new PatchOperation<>(PatchOperation.OP_ADD,

newIndexedItem.getKey(), newIndexedItem.getValue()));

++newCursor;

} else {

int oldIndex = oldIndexedItem.getKey();

int newIndex = newIndexedItem.getKey();

int oldOffset = getItemOffsetOrIndex(oldIndexedItem.getKey(), oldIndexedItem.getValue());

int newOffset = getItemOffsetOrIndex(newIndexedItem.getKey(), newIndexedItem.getValue());

if (oldIndex != newIndex) {

this.oldIndexToNewIndexMap.put(oldIndex, newIndex);

}

if (oldOffset != newOffset) {

this.oldOffsetToNewOffsetMap.put(oldOffset, newOffset);

}

++oldCursor;

++newCursor;

}

// 未完

}

可以看到首先读取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对象。

继续下半部分代码：

public void execute() {

// 接上...

// 根据index排序，如果index一样，则先DEL后ADD

Collections.sort(this.patchOperationList, comparatorForPatchOperationOpt);

Iterator<PatchOperation<T>> patchOperationIt = this.patchOperationList.iterator();

PatchOperation<T> prevPatchOperation = null;

while (patchOperationIt.hasNext()) {

PatchOperation<T> patchOperation = patchOperationIt.next();

if (prevPatchOperation != null

&& prevPatchOperation.op == PatchOperation.OP_DEL

&& patchOperation.op == PatchOperation.OP_ADD

) {

if (prevPatchOperation.index == patchOperation.index) {

prevPatchOperation.op = PatchOperation.OP_REPLACE;

prevPatchOperation.newItem = patchOperation.newItem;

patchOperationIt.remove();

prevPatchOperation = null;

} else {

prevPatchOperation = patchOperation;

}

} else {

prevPatchOperation = patchOperation;

}

// Finally we record some information for the final calculations.

patchOperationIt = this.patchOperationList.iterator();

while (patchOperationIt.hasNext()) {

PatchOperation<T> patchOperation = patchOperationIt.next();

switch (patchOperation.op) {

case PatchOperation.OP_DEL: {

indexToDelOperationMap.put(patchOperation.index, patchOperation);

break;

}

case PatchOperation.OP_ADD: {

indexToAddOperationMap.put(patchOperation.index, patchOperation);

break;

}

case PatchOperation.OP_REPLACE: {

indexToReplaceOperationMap.put(patchOperation.index, patchOperation);

break;

}

1. 首先对patchOperationList按照index排序，如果index一致则先DEL、后ADD。

2. 接下来一个对所有的operation的迭代，主要将index一致的，且连续的DEL、ADD转化为REPLACE操作。

3. 最后将patchOperationList转化为3个Map，分别为：indexToDelOperationMap，indexToAddOperationMap,indexToReplaceOperationMap。

ok，经历完成execute之后，我们主要的产物就是3个Map，分别记录了：oldDex中哪些index需要删除；newDex中新增了哪些item；哪些item需要替换为新item。

刚才说了每个算法除了execute()还有个simulatePatchOperation()

this.stringDataSectionDiffAlg

.simulatePatchOperation(this.patchedStringDataItemsOffset);

传入的偏移量为data区域的偏移量。

public void simulatePatchOperation(int baseOffset) {

int oldIndex = 0;

int patchedIndex = 0;

int patchedOffset = baseOffset;

while (oldIndex < this.oldItemCount || patchedIndex < this.newItemCount) {

if (this.indexToAddOperationMap.containsKey(patchedIndex)) {

//省略了一些代码

T newItem = patchOperation.newItem;

int itemSize = getItemSize(newItem);

++patchedIndex;

patchedOffset += itemSize;

} else if (this.indexToReplaceOperationMap.containsKey(patchedIndex)) {

//省略了一些代码

T newItem = patchOperation.newItem;

int itemSize = getItemSize(newItem);

++patchedIndex;

patchedOffset += itemSize;

} else if (this.indexToDelOperationMap.containsKey(oldIndex)) {

++oldIndex;

} else if (this.indexToReplaceOperationMap.containsKey(oldIndex)) {

++oldIndex;

} else if (oldIndex < this.oldItemCount) {

++oldIndex;

++patchedIndex;

patchedOffset += itemSize;

}

this.patchedSectionSize = SizeOf.roundToTimesOfFour(patchedOffset - baseOffset);

}

遍历oldIndex与newIndex，分别在indexToAddOperationMap,indexToReplaceOperationMap,indexToDelOperationMap中查找。

这里关注一点最终的一个产物是this.patchedSectionSize，由patchedOffset-baseOffset所得。
这里有几种情况会造成patchedOffset+=itemSize：

1. indexToAddOperationMap中包含patchIndex

2. indexToReplaceOperationMap包含patchIndex

3. 不在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文件

private void writeResultToStream(OutputStream os) throws IOException {

DexDataBuffer buffer = new DexDataBuffer();

buffer.write(DexPatchFile.MAGIC); // DEXDIFF

buffer.writeShort(DexPatchFile.CURRENT_VERSION); /0x0002

buffer.writeInt(this.patchedDexSize);

// we will return here to write firstChunkOffset later.

int posOfFirstChunkOffsetField = buffer.position();

buffer.writeInt(0);

buffer.writeInt(this.patchedStringIdsOffset);

buffer.writeInt(this.patchedTypeIdsOffset);

buffer.writeInt(this.patchedProtoIdsOffset);

buffer.writeInt(this.patchedFieldIdsOffset);

buffer.writeInt(this.patchedMethodIdsOffset);

buffer.writeInt(this.patchedClassDefsOffset);

buffer.writeInt(this.patchedMapListOffset);

buffer.writeInt(this.patchedTypeListsOffset);

buffer.writeInt(this.patchedAnnotationSetRefListItemsOffset);

buffer.writeInt(this.patchedAnnotationSetItemsOffset);

buffer.writeInt(this.patchedClassDataItemsOffset);

buffer.writeInt(this.patchedCodeItemsOffset);

buffer.writeInt(this.patchedStringDataItemsOffset);

buffer.writeInt(this.patchedDebugInfoItemsOffset);

buffer.writeInt(this.patchedAnnotationItemsOffset);

buffer.writeInt(this.patchedEncodedArrayItemsOffset);

buffer.writeInt(this.patchedAnnotationsDirectoryItemsOffset);

buffer.write(this.oldDex.computeSignature(false));

int firstChunkOffset = buffer.position();

buffer.position(posOfFirstChunkOffsetField);

buffer.writeInt(firstChunkOffset);

buffer.position(firstChunkOffset);

writePatchOperations(buffer, this.stringDataSectionDiffAlg.getPatchOperationList());

// 省略其他14个writePatch...

byte[] bufferData = buffer.array();

os.write(bufferData);

os.flush();

}

· 首先写了MAGIC，CURRENT_VERSION主要用于检查该文件为合法的tinker patch 文件。

· 然后写入patchedDexSize

· 第四位写入的是数据区的offset，可以看到先使用0站位，等所有的map list相关的offset书写结束，写入当前的位置。

· 接下来写入所有的跟maplist各个区域相关的offset（这里各个区域的排序不重要，读写一致即可）

· 然后执行每个算法写入对应区域的信息

· 最后生成patch文件

我们依旧只看stringDataSectionDiffAlg这个算法。

private <T extends Comparable<T>> void writePatchOperations(

DexDataBuffer buffer, List<PatchOperation<T>> patchOperationList

) {

List<Integer> delOpIndexList = new ArrayList<>(patchOperationList.size());

List<Integer> addOpIndexList = new ArrayList<>(patchOperationList.size());

List<Integer> replaceOpIndexList = new ArrayList<>(patchOperationList.size());

List<T> newItemList = new ArrayList<>(patchOperationList.size());

for (PatchOperation<T> patchOperation : patchOperationList) {

switch (patchOperation.op) {

case PatchOperation.OP_DEL: {

delOpIndexList.add(patchOperation.index);

break;

}

case PatchOperation.OP_ADD: {

addOpIndexList.add(patchOperation.index);

newItemList.add(patchOperation.newItem);

break;

}

case PatchOperation.OP_REPLACE: {

replaceOpIndexList.add(patchOperation.index);

newItemList.add(patchOperation.newItem);

break;

}

buffer.writeUleb128(delOpIndexList.size());

int lastIndex = 0;

for (Integer index : delOpIndexList) {

buffer.writeSleb128(index - lastIndex);

lastIndex = index;

}

buffer.writeUleb128(addOpIndexList.size());

lastIndex = 0;

for (Integer index : addOpIndexList) {

buffer.writeSleb128(index - lastIndex);

lastIndex = index;

}

buffer.writeUleb128(replaceOpIndexList.size());

lastIndex = 0;

for (Integer index : replaceOpIndexList) {

buffer.writeSleb128(index - lastIndex);

lastIndex = index;

}

for (T newItem : newItemList) {

if (newItem instanceof StringData) {

buffer.writeStringData((StringData) newItem);

}

// else 其他类型，write其他类型Data

}

首先将我们的patchOperationList转化为3个OpIndexList，分别对应DEL,ADD,REPLACE，以及将所有的item存入newItemList。

然后依次写入：

1. del操作的个数，每个del的index

2. add操作的个数，每个add的index

3. replace操作的个数，每个需要replace的index

4. 最后依次写入newItemList.

这里index都做了（这里做了个index – lastIndex操作）

其他的算法也是执行了类似的操作。

最好来看看我们生成的patch是什么样子的：

1. 首先包含几个字段，证明自己是tinker patch

2. 包含生成newDex各个区域的offset，即可以将newDex划分了多个区域，定位到起点

3. 包含newDex各个区域的Item的删除的索引(oldDex)，新增的索引和值，替换的索引和值

那么这么看，我们猜测Patch的逻辑时这样的：

1. 首先根据各个区域的offset，确定各个区域的起点

2. 读取oldDex各个区域的items，然后根据patch中去除掉oldDex中需要删除的和需要替换的item，再加上新增的item和替换的item即可组成newOld该区域的items。

即，newDex的某个区域的包含：

oldItems - del - replace + addItems + replaceItems

这么看挺清晰的，下面看代码咯~

四、Tinker DexPatch源码浅析

（1）寻找入口

与diff一样，肯定有那么一个类或者方法，接受old dex File 和 patch File，最后生成new Dex。不要陷在一堆安全校验，apk解压的代码中。

这个类叫做DexPatchApplier,在tinker-commons中。

patch的相关代码如下：

@Testpublic void testPatch() throws IOException {

File oldFile = new File("Hello.dex");

File patchFile = new File("patch.dex");

File newFile = new File("new.dex");

DexPatchApplier dexPatchGenerator

= new DexPatchApplier(oldFile, patchFile);

dexPatchGenerator.executeAndSaveTo(newFile);

}

可以看到和diff代码类似，下面看代码去。

（2）源码分析

public DexPatchApplier(File oldDexIn, File patchFileIn) throws IOException {

this(new Dex(oldDexIn), new DexPatchFile(patchFileIn));

}

oldDex会转化为Dex对象，这个上面分析过，主要就是readHeader和readMap.注意我们的patchFile是转为一个DexPatchFile对象。

public DexPatchFile(File file) throws IOException {

this.buffer = new DexDataBuffer(ByteBuffer.wrap(FileUtils.readFile(file)));

init();

}

首先将patch file读取为byte[]，然后调用init

private void init() {

byte[] magic = this.buffer.readByteArray(MAGIC.length);

if (CompareUtils.uArrCompare(magic, MAGIC) != 0) {

throw new IllegalStateException("bad dex patch file magic: " + Arrays.toString(magic));

}

this.version = this.buffer.readShort();

if (CompareUtils.uCompare(this.version, CURRENT_VERSION) != 0) {

throw new IllegalStateException("bad dex patch file version: " + this.version + ", expected: " + CURRENT_VERSION);

}

this.patchedDexSize = this.buffer.readInt();

this.firstChunkOffset = this.buffer.readInt();

this.patchedStringIdSectionOffset = this.buffer.readInt();

this.patchedTypeIdSectionOffset = this.buffer.readInt();

this.patchedProtoIdSectionOffset = this.buffer.readInt();

this.patchedFieldIdSectionOffset = this.buffer.readInt();

this.patchedMethodIdSectionOffset = this.buffer.readInt();

this.patchedClassDefSectionOffset = this.buffer.readInt();

this.patchedMapListSectionOffset = this.buffer.readInt();

this.patchedTypeListSectionOffset = this.buffer.readInt();

this.patchedAnnotationSetRefListSectionOffset = this.buffer.readInt();

this.patchedAnnotationSetSectionOffset = this.buffer.readInt();

this.patchedClassDataSectionOffset = this.buffer.readInt();

this.patchedCodeSectionOffset = this.buffer.readInt();

this.patchedStringDataSectionOffset = this.buffer.readInt();

this.patchedDebugInfoSectionOffset = this.buffer.readInt();

this.patchedAnnotationSectionOffset = this.buffer.readInt();

this.patchedEncodedArraySectionOffset = this.buffer.readInt();

this.patchedAnnotationsDirectorySectionOffset = this.buffer.readInt();

this.oldDexSignature = this.buffer.readByteArray(SizeOf.SIGNATURE);

this.buffer.position(firstChunkOffset);

}

还记得我们写patch的操作么，先写了MAGIC和Version用于校验该文件是一个patch file；接下来为patchedDexSize和各种offset进行赋值；最后定位到数据区（firstChunkOffset），还记得写的时候，该字段在第四个位置。

定位到该位置后，后面读取的就是数据了，数据存的时候按照如下格式存储的：

1. del操作的个数，每个del的index

2. add操作的个数，每个add的index

3. replace操作的个数，每个需要replace的index

4. 最后依次写入newItemList.

简单回忆下，我们继续源码分析。

public DexPatchApplier(File oldDexIn, File patchFileIn) throws IOException {

this(new Dex(oldDexIn), new DexPatchFile(patchFileIn));

}

public DexPatchApplier(

Dex oldDexIn,

DexPatchFile patchFileIn) {

this.oldDex = oldDexIn;

this.patchFile = patchFileIn;

this.patchedDex = new Dex(patchFileIn.getPatchedDexSize());

this.oldToPatchedIndexMap = new SparseIndexMap();

}

除了oldDex,patchFile,还初始化了一个patchedDex作为我们最终输出Dex对象。

构造完成后，直接执行了executeAndSaveTo方法。

public void executeAndSaveTo(File file) throws IOException {

OutputStream os = null;

try {

os = new BufferedOutputStream(new FileOutputStream(file));

executeAndSaveTo(os);

} finally {

if (os != null) {

try {

os.close();

} catch (Exception e) {

// ignored.

}

直接到executeAndSaveTo(os),该方法代码比较长，我们分3段讲解：

public void executeAndSaveTo(OutputStream out) throws IOException {

TableOfContents patchedToc = this.patchedDex.getTableOfContents();

patchedToc.header.off = 0;

patchedToc.header.size = 1;

patchedToc.mapList.size = 1;

patchedToc.stringIds.off

= this.patchFile.getPatchedStringIdSectionOffset();

patchedToc.typeIds.off

= this.patchFile.getPatchedTypeIdSectionOffset();

patchedToc.typeLists.off

= this.patchFile.getPatchedTypeListSectionOffset();

patchedToc.protoIds.off

= this.patchFile.getPatchedProtoIdSectionOffset();

patchedToc.fieldIds.off

= this.patchFile.getPatchedFieldIdSectionOffset();

patchedToc.methodIds.off

= this.patchFile.getPatchedMethodIdSectionOffset();

patchedToc.classDefs.off

= this.patchFile.getPatchedClassDefSectionOffset();

patchedToc.mapList.off

= this.patchFile.getPatchedMapListSectionOffset();

patchedToc.stringDatas.off

= this.patchFile.getPatchedStringDataSectionOffset();

patchedToc.annotations.off

= this.patchFile.getPatchedAnnotationSectionOffset();

patchedToc.annotationSets.off

= this.patchFile.getPatchedAnnotationSetSectionOffset();

patchedToc.annotationSetRefLists.off

= this.patchFile.getPatchedAnnotationSetRefListSectionOffset();

patchedToc.annotationsDirectories.off

= this.patchFile.getPatchedAnnotationsDirectorySectionOffset();

patchedToc.encodedArrays.off

= this.patchFile.getPatchedEncodedArraySectionOffset();

patchedToc.debugInfos.off

= this.patchFile.getPatchedDebugInfoSectionOffset();

patchedToc.codes.off

= this.patchFile.getPatchedCodeSectionOffset();

patchedToc.classDatas.off

= this.patchFile.getPatchedClassDataSectionOffset();

patchedToc.fileSize

= this.patchFile.getPatchedDexSize();

Arrays.sort(patchedToc.sections);

patchedToc.computeSizesFromOffsets();

// 未完待续...

}

这里实际上，就是读取patchFile中记录的值给patchedDex的TableOfContent中各种Section(大致对应map list中各个map_list_item)赋值。

接下来排序呢，设置byteCount等字段信息。

继续：

public void executeAndSaveTo(OutputStream out) throws IOException {

// 省略第一部分代码

// Secondly, run patch algorithms according to sections' dependencies.

this.stringDataSectionPatchAlg = new StringDataSectionPatchAlgorithm(