Home > Article > System Tutorial > Android hot fix Tinker source code analysis
Android hot fix Tinker source code analysis
- 王林forward
- 2024-03-25 09:20:24934browse
One of the biggest highlights of tinker is that it has self-developed a set of dex diff and patch related algorithms. The main purpose of this article is to analyze this algorithm. Of course, it is worth noting that the prerequisite for analysis is that you need to have a certain understanding of the format of the dex file, otherwise you may be confused.
So, this article will first do a simple analysis of the dex file format, and also do some simple experiments, and finally enter the dex diff and patch algorithm parts.
First of all, let’s briefly understand the Dex file. When decompiling, everyone knows that the apk will contain one or more *.dex files. This file stores the code we wrote. Under normal circumstances, we will also use tools Convert it into a jar, and then decompile and view it through some tools.
Everyone should know that jar files are similar to compressed packages of class files. Under normal circumstances, we can directly decompress and see each class file. We cannot obtain the internal class files by decompressing the dex file, which means that the dex file has its own specific format:
dex rearranges Java class files, decomposes the constant pools in all JAVA class files, eliminates redundant information, and recombines them to form a constant pool. All class files share the same constant pool, making the same strings and constants Appears only once in the DEX file, thus reducing the file size.
Next, let’s take a look at what the internal structure of the dex file looks like.
To analyze the composition of a file, it is best to write the simplest dex file for analysis.
First we write a class Hello.java:
public class Hello{
public static void main(String[] args){
System.out.println("hello dex！");
}
}
Then compile:
javac -source 1.7 -target 1.7 Hello.java
Finally convert it into a dex file through dx work:
dx --dex --output=Hello.dex Hello.class
The dx path is under Android-sdk/build-tools/version number/dx. If the dx command cannot be recognized, remember to put the path under path, or use an absolute path.
In this way we get a very simple dex file.
First show a rough internal structure diagram of the dex file:
Of course, simply explaining it from a picture is definitely not enough, because we will study diff and patch algorithms later. In theory, we should know more details, even down to: each element of a dex file. What do the bytes represent?
For a binary-like file, the best way is definitely not to rely on memory. Fortunately, there is such a software that can help us analyze:
- Software name: 010 Editor
After downloading and installing, open our dex file and you will be guided to install the parsing template of the dex file.
The final rendering is as follows:
The upper part represents the content of the dex file (displayed in hexadecimal format), and the lower part shows each area of the dex file. You can click on the lower part to view its corresponding content area and content.
Of course, it is also highly recommended here to read some special articles to deepen your understanding of dex files:
- DEX file format analysis
- Android reverse engineering journey—parsing the compiled Dex file format
This article will only do a simple format analysis of the dex file.
dex_header
First, we do a rough analysis of dex_header. The header contains the following fields:
First of all, we guess the role of the header. We can see that it contains some verification-related fields and the approximate distribution of blocks in the entire dex file (off is the offset).
The advantage of this is that when the virtual machine reads the dex file, it only needs to read the header part to know the approximate block distribution of the dex file; and it can check whether the file format is correct and whether the file is Tampering etc.
- Can prove that the file is a dex file
- checksum and signature are mainly used to verify the integrity of files
- file_size is the size of the dex file
- head_size is the size of the header file
- The default value of endian_tag is 12345678, and the logo defaults to Little-Endian (self-search).
The rest are almost all size and off that appear in pairs, most of which represent the number and offset of specific data structures contained in each block. For example: string_ids_off is 112, which means the string_ids area starts at offset 112; string_ids_size is 14, which means the number of string_id_items is 14. The rest are similar so I won’t introduce them.
Combined with 010Editor, you can see the data structure contained in each area and the corresponding values. Just take a look at it.
Besides the header, there is another important part which is dex_map_list. Let’s look at the picture first:
The first is the number of map_item_list, followed by the description of each map_item_list.
What is the use of map_item_list?
You can see that each map_list_item contains an enumeration type, a 2-byte unused member, a size indicating the number of the current type, and offset indicating the offset of the current type.
Take this example:
- The first is the TYPE_HEADER_ITEM type, which contains 1 header (size=1) and the offset is 0.
- Next is TYPE_STRING_ID_ITEM, which contains 14 string_id_item (size=14), and the offset is 112 (if you remember, the length of the header is 112, followed by the header).
The rest can be deduced in order~~
In this case, it can be seen that through map_list, a complete dex file can be divided into fixed areas (13 in this example), and the start of each area and the number of data formats corresponding to the area are known.
Find the beginning of each area through map_list. Each area will correspond to a specific data structure. Just view it through 010 Editor.
Now that we understand the basic format of dex, let's consider how to do dex diff and patch.
The first thing to consider is what we have:
- olddex
- new dex
We want to generate a patch file, which can also generate new dex through the patch algorithm with old dex.
- So what should we do?
Based on the above analysis, we know that the dex file roughly has three parts (the three parts here are mainly used for analysis, don’t take it seriously):
- header
- Various areas
- map list
The header can actually determine its content based on the following data, and has a fixed length of 112; each area will be mentioned later; the map list can actually locate the starting position of each area;
We finally patch old dex -> new dex; for the above three parts,
- We don’t need to process the header because it can be generated based on other data;
- For map list, what we mainly want is the start (offset) of each area
- After knowing the offset of each area, when we generate new dex, we can locate the start and end positions of each area, then we only need to write data to each area.
Then let’s look at the diff for an area. Suppose there is a string area, which is mainly used to store strings:
The strings in this area of old dex are: Hello, World, zhy
The strings in this area of new dex are: Android, World, zhy
It can be seen that for this area, we deleted Hello and added Android.
Then the patch can record this area as follows:
"del Hello, add Android" (actual situation needs to be converted into binary).
Think about the old dex that can be read directly in the application, that is, you will know:
- It turns out that this area includes: Hello, World, zhy
- This area in the patch contains: "del Hello, add Android"
Then, it can be very easily calculated that new dex contains:
Android, World, zhy.
In this way, we have completed the rough diff and patch algorithm for one area. The diff and patch for other areas are similar to the above.
Looking at it this way, do you think that the diff and patch algorithms are not that complicated? In fact, tinker's approach is similar to the above. The actual situation may be more complicated than the above description, but it is basically the same.
After we have a general concept of the algorithm, we can look at the source code.
There is actually a trick to reading the code here. There are actually quite a lot of tinker codes, and you may often get stuck in a bunch of codes. We can think about it this way, such as the diff algorithm. The input parameters are old dex and new dex, and the output is patch file.
Then there must be a class or a method that accepts and outputs the above parameters. In fact, this class is DexPatchGenerator:
The API usage code of diff is:
@Test
public 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);
}
The code is under tinker-patch-lib of tinker-build.
Write a unit test or main method. The above lines of code are the diff algorithm.
So when you look at the code, you need to be targeted. For example, if you look at the diff algorithm, find the entrance to the diff algorithm. Don't worry about it in the gradle plugin.
public DexPatchGenerator(File oldDexFile, File newDexFile) throws IOException {
this(new Dex(oldDexFile), new Dex(newDexFile));
}
Convert the dex file we passed in into a Dex object.
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);
}
First read our file as a byte[] array (this is quite memory-consuming), then wrap it with ByteBuffer, and set the byte order to little endian (it shows that ByteBuffer is quite convenient here. Then through readFrom The method assigns a value to tableOfContents of the Dex object.
#TableOfContents
public 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 and readMap are executed internally. Above, we roughly analyzed the header and map list. In fact, these two areas are converted into certain data structures, read and then stored in memory.
First look at 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();
}
If you open 010 Editor now, or take a look at the front picture, you are actually defining all the fields in the header, reading the response bytes and assigning values.
Next, look at 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;
}
}
}
Note here that when reading the header, the offset except the map list area has actually been read and stored in mapList.off. So the map list actually starts from this position. The first thing to read is the number of map_list_item, and the next thing to read is the actual data corresponding to each map_list_item.
You can see that it is read in sequence: type, unused, size, offset. If you still have the impression that we described map_list_item earlier, it corresponds to this, and the corresponding data structure is the TableContents.Section object.
computeSizesFromOffsets() mainly assigns values to the byteCount (occupies multiple bytes) parameter of section.
This completes the initialization of dex file to Dex object.
After you have two Dex objects, you need to perform a diff operation.
Continue back to the source code:
public DexPatchGenerator(File oldDexFile, InputStream newDexStream) throws IOException {
this(new Dex(oldDexFile), new Dex(newDexStream));
}
Directly to the constructors of the two Dex objects:
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 = ...
}
See that it first assigns values to oldDex and newDex, and then initializes 15 algorithms in sequence. Each algorithm represents each area. The purpose of the algorithm is as we described before. We must know "which ones have been deleted and which ones have been added." Which";
Let’s continue looking at the code:
dexPatchGenerator.executeAndSaveTo(patchFile);
With the dexPatchGenerator object, it directly points to the executeAndSaveTo method.
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.
}
}
}
}
To executeAndSaveTo method:
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);
}
Because there are 15 algorithms involved, the code here is very long. We only use one of the algorithms to illustrate here.
Each algorithm will execute the execute and simulatePatchOperation methods:
First look at 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;
}
}
}
// 未完
}
You can see that the data in the corresponding areas of oldDex and newDex are first read and sorted, adjustedOldIndexedItems and adjustedNewIndexedItems respectively.
The traversal starts next, look directly at the else part:
According to the current cursor, obtain oldItem and newItem respectively, and compare their value pairs:
- If <0, the old Item is considered to be deleted, recorded as PatchOperation.OP_DEL, and the oldItem index is recorded in the PatchOperation object and added to the patchOperationList.
- If >0, the newItem is considered to be newly added, recorded as PatchOperation.OP_ADD, and the newItem index and value are recorded in the PatchOperation object and added to the patchOperationList.
- If =0, PatchOperation will not be generated.
After the above, we got a patchOperationList object.
Continue with the second half of the code:
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;
}
}
}
}
<ol>
<li>First sort the patchOperationList according to index. If the index is consistent, DEL first and then ADD. </li>
<li>The next iteration of all operations mainly converts DEL and ADD with consistent index and continuous into REPLACE operations. </li>
<li>Finally, the patchOperationList is converted into 3 Maps, namely: indexToDelOperationMap, indexToAddOperationMap, indexToReplaceOperationMap. </li>
</ol>
<p>ok, after completing execute, our main products are three Maps, which record respectively: which indexes in oldDex need to be deleted; which items have been added to newDex; which items need to be replaced with new items. </p>
<p>I just said that in addition to execute(), each algorithm also has a simulatePatchOperation()</p>
<pre class="brush:php;toolbar:false">this.stringDataSectionDiffAlg
.simulatePatchOperation(this.patchedStringDataItemsOffset);
The offset passed in is the offset of the data area.
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);
}
Traverse oldIndex and newIndex, and search in indexToAddOperationMap, indexToReplaceOperationMap, indexToDelOperationMap respectively.
Pay attention here. The final product is this.patchedSectionSize, which is obtained by patchedOffset-baseOffset.
There are several situations that will cause patchedOffset =itemSize:
- indexToAddOperationMap contains patchIndex
- indexToReplaceOperationMap contains patchIndex
- oldDex. that is not in indexToDelOperationMap and indexToReplaceOperationMap
In fact, it is easy to understand. This patchedSectionSize actually corresponds to the size of this area of newDex. Therefore, it includes Items that require ADD, Items that will be replaced, and Items that have not been deleted or replaced in OLD ITEMS. The addition of these three is the itemList of newDex.
At this point, an algorithm has been executed.
After such an algorithm, we get the PatchOperationList and the corresponding area sectionSize. Then after executing all the algorithms, you should get the PatchOperationList for each algorithm and the sectionSize of each area; the sectionSize of each area is actually converted to the offset of each area.
The algorithm, execute and simulatePatchOperation codes of each area are reused, so there are only minor changes in the others, you can check it yourself.
Next, look at the writeResultToStream method after executing all algorithms.
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();
}
- First I wrote MAGIC, CURRENT_VERSION is mainly used to check that the file is a legal tinker patch file.
- Then write patchedDexSize
- The fourth bit is written to the offset of the data area. You can see that the 0 station position is used first, and after all offsets related to the map list are written, the current position is written.
- Next, write all the offsets related to each area of the maplist (the ordering of each area is not important here, just read and write the same)
- Then execute each algorithm to write the information in the corresponding area
- Finally generate patch file
We still only look at the stringDataSectionDiffAlg algorithm.
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
}
}
First convert our patchOperationList into 3 OpIndexList, corresponding to DEL, ADD, REPLACE, and store all items in newItemList.
Then write in sequence:
- The number of del operations, the index of each del
- The number of add operations, the index of each add
- The number of replace operations, each index that needs to be replaced
- Finally write newItemList.
The index is done here (an index – lastIndex operation is done here)
Other algorithms also perform similar operations.
It’s best to take a look at what the patch we generated looks like:
- First include several fields to prove that you are a tinker patch
- Contains the offsets for generating each area of newDex, that is, newDex can be divided into multiple areas and positioned to the starting point
- Contains the deleted index (oldDex), new index and value, and replaced index and value of the Item in each area of newDex
Looking at it this way, our guess at Patch’s logic is as follows:
- First determine the starting point of each area based on the offset of each area
- Read the items in each area of oldDex, then remove the items that need to be deleted and replaced in oldDex according to the patch, and add the new items and replaced items to form the items in the area of newOld.
That is, a certain area of newDex contains:
oldItems - del - replace + addItems + replaceItems
This is quite clear, let’s look at the code below~
Same as diff, there must be a class or method that accepts old dex File and patch file, and finally generates new Dex. Don't get stuck in a bunch of security verification and apk decompression codes.
This class is called DexPatchApplier, in tinker-commons.
The relevant code for patch is as follows:
@Test
public 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);
}
You can see that it is similar to the diff code, see the code below.
public DexPatchApplier(File oldDexIn, File patchFileIn) throws IOException {
this(new Dex(oldDexIn), new DexPatchFile(patchFileIn));
}
oldDex will be converted into a Dex object. This has been analyzed above, mainly readHeader and readMap. Note that our patchFile is converted into a DexPatchFile object.
public DexPatchFile(File file) throws IOException {
this.buffer = new DexDataBuffer(ByteBuffer.wrap(FileUtils.readFile(file)));
init();
}
First read the patch file as byte[], and then call 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);
}
Do you still remember how we wrote the patch? We first wrote MAGIC and Version to verify that the file is a patch file; then assigned values to patchedDexSize and various offsets; finally located the data area (firstChunkOffset), and Remember that when writing, this field is in the fourth position.
After locating the position, what is read later is the data. When the data is saved, it is stored in the following format:
- The number of del operations, the index of each del
- The number of add operations, the index of each add
- The number of replace operations, each index that needs to be replaced
- Finally write newItemList.
Let’s briefly recall that we continue source code analysis.
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();
}
In addition to oldDex and patchFile, a patchedDex is also initialized as our final output Dex object.
After the construction is completed, the executeAndSaveTo method is directly executed.
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.
}
}
}
}
Go directly to executeAndSaveTo(os). The code of this method is relatively long. We will explain it in three paragraphs:
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();
// 未完待续...
}
Actually, here, the values recorded in patchFile are read and assigned to various Sections in the TableOfContent of patchedDex (roughly corresponding to each map_list_item in the map list).
Next to sort, set field information such as byteCount.
continue:
public void executeAndSaveTo(OutputStream out) throws IOException {
// 省略第一部分代码
// Secondly, run patch algorithms according to sections' dependencies.
this.stringDataSectionPatchAlg = new StringDataSectionPatchAlgorithm(
patchFile, oldDex, patchedDex, oldToPatchedIndexMap
);
this.typeIdSectionPatchAlg = new TypeIdSectionPatchAlgorithm(
patchFile, oldDex, patchedDex, oldToPatchedIndexMap
);
this.protoIdSectionPatchAlg = new ProtoIdSectionPatchAlgorithm(
patchFile, oldDex, patchedDex, oldToPatchedIndexMap
);
this.fieldIdSectionPatchAlg = new FieldIdSectionPatchAlgorithm(
patchFile, oldDex, patchedDex, oldToPatchedIndexMap
);
this.methodIdSectionPatchAlg = new MethodIdSectionPatchAlgorithm(
patchFile, oldDex, patchedDex, oldToPatchedIndexMap
);
this.classDefSectionPatchAlg = new ClassDefSectionPatchAlgorithm(
patchFile, oldDex, patchedDex, oldToPatchedIndexMap
);
this.typeListSectionPatchAlg = new TypeListSectionPatchAlgorithm(
patchFile, oldDex, patchedDex, oldToPatchedIndexMap
);
this.annotationSetRefListSectionPatchAlg = new AnnotationSetRefListSectionPatchAlgorithm(
patchFile, oldDex, patchedDex, oldToPatchedIndexMap
);
this.annotationSetSectionPatchAlg = new AnnotationSetSectionPatchAlgorithm(
patchFile, oldDex, patchedDex, oldToPatchedIndexMap
);
this.classDataSectionPatchAlg = new ClassDataSectionPatchAlgorithm(
patchFile, oldDex, patchedDex, oldToPatchedIndexMap
);
this.codeSectionPatchAlg = new CodeSectionPatchAlgorithm(
patchFile, oldDex, patchedDex, oldToPatchedIndexMap
);
this.debugInfoSectionPatchAlg = new DebugInfoItemSectionPatchAlgorithm(
patchFile, oldDex, patchedDex, oldToPatchedIndexMap
);
this.annotationSectionPatchAlg = new AnnotationSectionPatchAlgorithm(
patchFile, oldDex, patchedDex, oldToPatchedIndexMap
);
this.encodedArraySectionPatchAlg = new StaticValueSectionPatchAlgorithm(
patchFile, oldDex, patchedDex, oldToPatchedIndexMap
);
this.annotationsDirectorySectionPatchAlg = new AnnotationsDirectorySectionPatchAlgorithm(
patchFile, oldDex, patchedDex, oldToPatchedIndexMap
);
this.stringDataSectionPatchAlg.execute();
this.typeIdSectionPatchAlg.execute();
this.typeListSectionPatchAlg.execute();
this.protoIdSectionPatchAlg.execute();
this.fieldIdSectionPatchAlg.execute();
this.methodIdSectionPatchAlg.execute();
this.annotationSectionPatchAlg.execute();
this.annotationSetSectionPatchAlg.execute();
this.annotationSetRefListSectionPatchAlg.execute();
this.annotationsDirectorySectionPatchAlg.execute();
this.debugInfoSectionPatchAlg.execute();
this.codeSectionPatchAlg.execute();
this.classDataSectionPatchAlg.execute();
this.encodedArraySectionPatchAlg.execute();
this.classDefSectionPatchAlg.execute();
//未完待续...
}
This part obviously initializes a bunch of algorithms and then executes them separately. We still use stringDataSectionPatchAlg for analysis.
public void execute() {
final int deletedItemCount = patchFile.getBuffer().readUleb128();
final int[] deletedIndices = readDeltaIndiciesOrOffsets(deletedItemCount);
final int addedItemCount = patchFile.getBuffer().readUleb128();
final int[] addedIndices = readDeltaIndiciesOrOffsets(addedItemCount);
final int replacedItemCount = patchFile.getBuffer().readUleb128();
final int[] replacedIndices = readDeltaIndiciesOrOffsets(replacedItemCount);
final TableOfContents.Section tocSec = getTocSection(this.oldDex);
Dex.Section oldSection = null;
int oldItemCount = 0;
if (tocSec.exists()) {
oldSection = this.oldDex.openSection(tocSec);
oldItemCount = tocSec.size;
}
// Now rest data are added and replaced items arranged in the order of
// added indices and replaced indices.
doFullPatch(
oldSection, oldItemCount, deletedIndices, addedIndices, replacedIndices
);
}
Let’s post the rules when we write:
- The number of del operations, the index of each del
- The number of add operations, the index of each add
- The number of replace operations, each index that needs to be replaced
- Finally write newItemList.
Looking at the code, the reading order is as follows:
- The number of del, all indexes of del are stored in an int[];
- The number of add, all indexes of add are stored in an int[];
- The number of replacements, all indexes of replacement are stored in an int[];
Is it the same as when it was written?
Continue, and then obtain the oldItems and oldItemCount in oldDex.
So now we have:
- del count and indices
- add count add indices
- replace count and indices
- oldItems and oldItemCount
Take what we have and continue executing doFullPatch
private void doFullPatch(
Dex.Section oldSection,
int oldItemCount,
int[] deletedIndices,
int[] addedIndices,
int[] replacedIndices) {
int deletedItemCount = deletedIndices.length;
int addedItemCount = addedIndices.length;
int replacedItemCount = replacedIndices.length;
int newItemCount = oldItemCount + addedItemCount - deletedItemCount;
int deletedItemCounter = 0;
int addActionCursor = 0;
int replaceActionCursor = 0;
int oldIndex = 0;
int patchedIndex = 0;
while (oldIndex < oldItemCount || patchedIndex < newItemCount) {
if (addActionCursor < addedItemCount && addedIndices[addActionCursor] == patchedIndex) {
T addedItem = nextItem(patchFile.getBuffer());
int patchedOffset = writePatchedItem(addedItem);
++addActionCursor;
++patchedIndex;
} else
if (replaceActionCursor < replacedItemCount && replacedIndices[replaceActionCursor] == patchedIndex) {
T replacedItem = nextItem(patchFile.getBuffer());
int patchedOffset = writePatchedItem(replacedItem);
++replaceActionCursor;
++patchedIndex;
} else
if (Arrays.binarySearch(deletedIndices, oldIndex) >= 0) {
T skippedOldItem = nextItem(oldSection); // skip old item.
++oldIndex;
++deletedItemCounter;
} else
if (Arrays.binarySearch(replacedIndices, oldIndex) >= 0) {
T skippedOldItem = nextItem(oldSection); // skip old item.
++oldIndex;
} else
if (oldIndex < oldItemCount) {
T oldItem = adjustItem(this.oldToPatchedIndexMap, nextItem(oldSection));
int patchedOffset = writePatchedItem(oldItem);
++oldIndex;
++patchedIndex;
}
}
}
Let’s take a look at it as a whole. The purpose here is to write data to the stringData area of patchedDex. The written data should theoretically be:
- New data
- Alternative data
- New and replaced data in oldDex
Of course they need to be written sequentially.
So looking at the code, first calculate newItemCount=oldItemCount addCount - delCount, and then start traversing. The traversal condition is 0~oldItemCount or 0~newItemCount.
What we expect is that the corresponding Item will be written in patchIndex from 0 to newItemCount.
Item is written through the code and we can see:
- First determine whether the patchIndex is included in addIndices, and if so, write it;
- Furthermore, determine whether it is in replicaIndices, and write if it is included;
- Then judge if oldIndex is found to be deleted or replaced, skip it directly;
- Then the last index refers to the oldIndex that is non-delete and replace, which is the same part as the items in newDex.
The above three parts in 1.2.4 can form this area of the complete newDex.
In this way, the patch algorithm of the stringData area is completed.
The execution codes of the remaining 14 algorithms are the same (parent class), and the operations performed are similar, and all parts of the patch algorithm will be completed.
When all areas are restored, all that is left is the header and mapList, so go back to the place where all algorithm execution is completed:
public void executeAndSaveTo(OutputStream out) throws IOException {
//1.省略了offset的各种赋值
//2.省略了各个部分的patch算法
// Thirdly, write header, mapList. Calculate and write patched dex's sign and checksum.
Dex.Section headerOut = this.patchedDex.openSection(patchedToc.header.off);
patchedToc.writeHeader(headerOut);
Dex.Section mapListOut = this.patchedDex.openSection(patchedToc.mapList.off);
patchedToc.writeMap(mapListOut);
this.patchedDex.writeHashes();
// Finally, write patched dex to file.
this.patchedDex.writeTo(out);
}
Locate the header area and write header-related data; locate the map list area and write map list-related data. When both are completed, you need to write two special fields in the header: signature and checkSum. Because these two fields depend on the map list, they must be written after the map list.
This completes the complete dex recovery, and finally writes all the data in the memory to the file.
Just now we have Hello.dex, let’s write another class:
public class World{
public static void main(String[] args){
System.out.println("nani World");
}
}
Then compile and type this class into a dx file.
javac -source 1.7 -target 1.7 World.java dx --dex --output=World.dex World.class
In this way we have prepared two dex, Hello.dex and World.dex.
Use 010 Editor to open two dex respectively. We mainly focus on string_id_item;
There are 13 strings on both sides. According to the diff algorithm we introduced above, we can get the following operations:
Start traversing and comparing the strings on both sides:
- If <0, the old Item is considered to be deleted, recorded as PatchOperation.OP_DEL, and the oldItem index is recorded in the PatchOperation object and added to the patchOperationList.
- If >0, the newItem is considered to be newly added, recorded as PatchOperation.OP_ADD, and the newItem index and value are recorded in the PatchOperation object and added to the patchOperationList.
- If =0, PatchOperation will not be generated.
del 1 add 1 LWorld; del 2 add 8 World.java del 10 add 11 naniWorld
Then sort according to the index, no change;
Next, iterate through all operations and replace operations with consistent index and adjacent DEL and ADD with replace
replace 1 LWorld del 2 add 8 World.java del 10 add 11 naniWorld
Finally, when writing, a traversal will be performed, the operations will be classified according to DEL, ADD, and REPLACE, and the items that appear will be placed in newItemList.
del ops:
del 2
del 10
add ops:
add 8
add 11
replace ops:
replace 1
newItemList becomes:
LWorld //replace 1 World.java //add 8 naniWorld //add 11
Then write, then the writing order should be:
2 //del size 2 8 // index - lastIndex 2 // add size 8 3 // index - lastIndex 1 //replace size 1 LWorld World.java naniWorld
Here we directly log in the relevant position of writeResultToStream of DexPatchGenerator:
buffer.writeUleb128(delOpIndexList.size());
System.out.println("del size = " + delOpIndexList.size());
int lastIndex = 0;
for (Integer index : delOpIndexList) {
buffer.writeSleb128(index - lastIndex);
System.out.println("del index = " + (index - lastIndex));
lastIndex = index;
}
buffer.writeUleb128(addOpIndexList.size());
System.out.println("add size = " + addOpIndexList.size());
lastIndex = 0;
for (Integer index : addOpIndexList) {
buffer.writeSleb128(index - lastIndex);
System.out.println("add index = " + (index - lastIndex));
lastIndex = index;
}
buffer.writeUleb128(replaceOpIndexList.size());
System.out.println("replace size = " + addOpIndexList.size());
lastIndex = 0;
for (Integer index : replaceOpIndexList) {
buffer.writeSleb128(index - lastIndex);
System.out.println("replace index = " + (index - lastIndex));
lastIndex = index;
}
for (T newItem : newItemList) {
if (newItem instanceof StringData) {
buffer.writeStringData((StringData) newItem);
System.out.println("stringdata = " + ((StringData) newItem).value);
}
}
You can see the output is:
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
Consistent with our above analysis results ~~
Then other areas can be verified in a similar way, and the patch is similar, so I won’t go into details.
The above is the detailed content of Android hot fix Tinker source code analysis. For more information, please follow other related articles on the PHP Chinese website!