由Android 65K方法數限制引發的思考

Mable4642 8年前發布 | 36K 次閱讀安卓開發 Android開發移動開發

來自： http://www.jcodecraeer.com/a/anzhuokaifa/androidkaifa/2016/0311/4048.html

原文出處：杰風居。

前言

沒想到，65536真的很小。

Unable to execute dex: method ID not in [0, 0xffff]: 65536

PS:本文只是純探索一下這個65K的來源，僅此而已。

到底是65k還是64k?

都沒錯，同一個問題，不同的說法而已。

65536按1000算的話，是65k ~ 65 1000;

65536按1024算的話，是64k = 64 1024。

重點是65536=2^16，請大家記住這個數字。

時間點

從大家的經歷和這篇文章：

http://source.android.com/devices/tech/dalvik/dalvik-bytecode.html

來看，這個錯誤是發生在構建時期。

65536是怎么算出來的？

65536網上眾說紛紜，有對的，有不全對的，也有錯的。下面將跟蹤最新的AOSP源碼來順藤摸瓜，但是探索問題必然迂回冗余，僅作記錄，讀者可直接跳過看結果。

1. 首先，查找Dex的結構定義。

/*

Direct-mapped "header_item" struct.
*/
struct DexHeader {
 u1  magic[8];
 u4  checksum;
 u1  signature[kSHA1DigestLen];
 u4  fileSize;
 u4  headerSize;
 u4  endianTag;
 u4  linkSize;
 u4  linkOff;
 u4  mapOff;
 u4  stringIdsSize;
 u4  stringIdsOff;
 u4  typeIdsSize;
 u4  typeIdsOff;
 u4  protoIdsSize;
 u4  protoIdsOff;
 u4  fieldIdsSize;
 u4  fieldIdsOff;
 u4  methodIdsSize; // 這里存放了方法字段索引的大小，methodIdsSize的類型為u4
 u4  methodIdsOff;
 u4  classDefsSize;
 u4  classDefsOff;
 u4  dataSize;
 u4  dataOff;
};</pre>
u4的類型定義如下：
/*

These match the definitions in the VM specification.
*/
typedef uint8_t             u1;
typedef uint16_t            u2;
typedef uint32_t            u4;
typedef uint64_t            u8;
typedef int8_t              s1;
typedef int16_t             s2;
typedef int32_t             s4;
typedef int64_t             s8;</pre>
 
進一步推出，methodIdsSize的類型是uint32_t，但它的限制為2^32 = 65536 * 65536，比65536大的多。

所以，65k不是dex文件結構本身限制造成的。

PS：Dex文件中存儲方法ID用的并不是short類型，無論最新的DexFile.h新定義的u4是uint32_t，還是老版本DexFile引用的vm/Common.h里定義的u4是uint32或者unsigned int，都不是short類型，特此說明。

2. DexOpt優化造成？ 
這個說法源自：
 
當Android系統啟動一個應用的時候，有一步是對Dex進行優化，這個過程有一個專門的工具來處理，叫DexOpt。DexOpt的執行過程是在第一次加載Dex文件的時候執行的。這個過程會生成一個ODEX文件，即Optimised Dex。執行ODex的效率會比直接執行Dex文件的效率要高很多。但是在早期的Android系統中，DexOpt有一個問題，也就是這篇文章想要說明并解決的問題。DexOpt會把每一個類的方法id檢索起來，存在一個鏈表結構里面。但是這個鏈表的長度是用一個short類型來保存的，導致了方法id的數目不能夠超過65536個。當一個項目足夠大的時候，顯然這個方法數的上限是不夠的。盡管在新版本的Android系統中，DexOpt修復了這個問題，但是我們仍然需要對老系統做兼容。

 
鑒于我能力有限，沒有找到這塊邏輯對應的代碼。

但我有個疑問，這個限制是在Android啟動一個應用的時候發生的，但從前面的“時間點”章節，65k問題是在構建的時候就發生了，還沒到啟動或者運行這一步。

我不敢否定這種說法，但說明65k至少還有其他地方限制。

3. DexMerger的檢測 
只能在dalvik目錄下搜索關鍵字”methid ID not in”，在DexMergger里找到了拋出異常的地方：
/**

Combine two dex files into one.
*/
public final class DexMerger {
private void mergeMethodIds() {

 new IdMerger<MethodId>(idsDefsOut) {
     @Override TableOfContents.Section getSection(TableOfContents tableOfContents) {
         return tableOfContents.methodIds;
     }

     @Override MethodId read(Dex.Section in, IndexMap indexMap, int index) {
         return indexMap.adjust(in.readMethodId());
     }

     @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) {
         if (newIndex < 0 || newIndex > 0xffff) {
             throw new DexIndexOverflowException(
                     "method ID not in [0, 0xffff]: " + newIndex);
         }
         indexMap.methodIds[oldIndex] = (short) newIndex;
     }

     @Override void write(MethodId methodId) {
         methodId.writeTo(idsDefsOut);
     }
 }.mergeSorted();

}
}</pre>
這里定義了indexMap的methodIds的單項值要強轉short，所以在存放之前check一下范圍是不是0 ~ 0xffff。我們看看IndexMap的定義： 
/**

Maps the index offsets from one dex file to those in another. For example, if
you have string #5 in the old dex file, its position in the new dex file is
{@code strings[5]}.
*/
public final class IndexMap {
 private final Dex target;
 public final int[] stringIds;
 public final short[] typeIds;
 public final short[] protoIds;
 public final short[] fieldIds;
 public final short[] methodIds;
// ... ...
}</pre>
看上去是對了，可是這個DexMerger是合并兩個dex的，默認情況下我們只有一個dex的，那么這個65k是哪里限制的呢？再查！
4. 回歸DexFile 
 
基本上前面基本是一個摸著石頭過河、反復驗證網絡說法的一個過程，雖然回想起來傻傻的，但是這種記錄還是有必要的。

前面看到DexFile的存放方法數大小的類型是uint32，但是根據后面的判斷，我們確定是打包的過程中產生了65k問題，所以我們得回過頭老老實實研究一下dx的打包流程。

… 此處省略分析流程5000字 …

OK，我把dx打包涉及到流程記錄下來：

// 源碼目錄：dalvik/dx
// Main.java
-> main() -> run() -> runMonoDex()(或者runMultiDex()) -> writeDex()
// DexFile
-> toDex() -> toDex0()
// MethodIdsSection extends MemberIdsSection extends UniformItemSection extends  Section
-> prepare() -> prepare0() -> orderItems() -> getTooManyMembersMessage()
// Main.java
-> getTooManyIdsErrorMessage()

最終狐貍的尾巴是在MemberIdsSection漏出來了：
package com.android.dx.dex.file;


import com.android.dex.DexException;
import com.android.dex.DexFormat;
import com.android.dex.DexIndexOverflowException;
import com.android.dx.command.dexer.Main;
import java.util.Formatter;
import java.util.Map;
import java.util.TreeMap;
import java.util.concurrent.atomic.AtomicInteger;
/**

Member (field or method) refs list section of a {@code .dex} file.
*/
public abstract class MemberIdsSection extends UniformItemSection {
/**

Constructs an instance. The file offset is initially unknown.
*
@param name {@code null-ok;} the name of this instance, for annotation
purposes
@param file {@code non-null;} file that this instance is part of
*/
public MemberIdsSection(String name, DexFile file) {
 super(name, file, 4);
}
/* {@inheritDoc} /
@Override
 protected void orderItems() {

 int idx = 0;

 if (items().size() > DexFormat.MAX_MEMBER_IDX + 1) {
     throw new DexIndexOverflowException(getTooManyMembersMessage());
 }

 for (Object i : items()) {
     ((MemberIdItem) i).setIndex(idx);
     idx++;
 }

}
private String getTooManyMembersMessage() {
 Map<String, AtomicInteger> membersByPackage = new TreeMap<String, AtomicInteger>();
 for (Object member : items()) {

 String packageName = ((MemberIdItem) member).getDefiningClass().getPackageName();
 AtomicInteger count = membersByPackage.get(packageName);
 if (count == null) {
     count = new AtomicInteger();
     membersByPackage.put(packageName, count);
 }
 count.incrementAndGet();

}
Formatter formatter = new Formatter();
 try {

 String memberType = this instanceof MethodIdsSection ? "method" : "field";
 formatter.format("Too many %s references: %d; max is %d.%n" +
         Main.getTooManyIdsErrorMessage() + "%n" +
         "References by package:",
         memberType, items().size(), DexFormat.MAX_MEMBER_IDX + 1);
 for (Map.Entry<String, AtomicInteger> entry : membersByPackage.entrySet()) {
     formatter.format("%n%6d %s", entry.getValue().get(), entry.getKey());
 }
 return formatter.toString();

} finally {

 formatter.close();

}
}




}</pre> 
 
里面有一段：

// 如果方法數大于0xffff就提示65k錯誤
if (items().size() > DexFormat.MAX_MEMBER_IDX + 1) {
    throw new DexIndexOverflowException(getTooManyMembersMessage());
}
// 這個DexFormat.MAX_MEMBER_IDX就是0xFFFF
/**

Maximum addressable field or method index.
The largest addressable member is 0xffff, in the "instruction formats" spec as field@CCCC or
meth@CCCC.
*/
public static final int MAX_MEMBER_IDX = 0xFFFF;</pre>
至此，真相大白！
5. 根本原因 
 
為什么定義DexFormat.MAX_MEMBER_IDX為0xFFFF?

雖然我們找到了65k報錯的地方，但是為什么程序中方法數超過0xFFFF就要報錯呢？

通過搜索”instruction formats”, 我最終查到了Dalvik VM Bytecode，找到最新的官方說明：

 https://source.android.com/devices/tech/dalvik/dalvik-bytecode.html 

里面說明了上面的@CCCC的范圍必須在0～65535之間，這是dalvik bytecode的限制。

所以，65536是bytecode的16位限制算出來的：2^16。

PS：以上分析得到群里很多朋友的討論和幫忙。

6. 回顧 
我好像明白了什么：
 
 65k問題是dx打包單個Dex時報的錯，所以只要用dx打包單個dex就可能有這個問題。


 不僅方法數，字段數也有65k問題。


 目前來說，65k問題和系統無關。


 目前來說，65k問題和art無關。


 即使分包MultiDex，當主Dex的方法數超過65k依然會報錯。


 MultiDex方案不是從根本上解決了65k問題，但是大大緩解甚至說基本解決了65k問題。


新的Jack能否解決65k問題？ 
據說Jack的方式把class打包成.jack文件。所以我認為，Jack具備解決65k問題的條件： 
 
 打包：新的jack文件肯定是拋棄了dalvik的兼容性，這也注定咱們這兩年可能還用不了。


 虛擬機：完全采用新的ART虛擬機，把class轉化成本地機器碼，就能避開dalvik bytecode的16位限制。


 上面兩條屬于廢話，說白了，完全不用dalvik虛擬機了，同時也就完全不用dx了，如此，當然就不存在65k問題了。


以上純屬我個人推測，一切以科學分析為準。
</div>

本文由用戶 Mable4642 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1457672319140.html

安卓開發 Android開發移動開發

由Android 65K方法數限制引發的思考

前言

到底是65k還是64k?

時間點

65536是怎么算出來的？

1. 首先，查找Dex的結構定義。

相關經驗

相關資訊

相關文檔

目錄