由Android 65K方法数限制引发的思考

xman

前言

没想到，65536真的很小。

1. 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的结构定义。

1. /*
   
2. * Direct-mapped "header_item" struct.
   
3. */
   
4. struct DexHeader {
   
5.     u1  magic[8];
   
6.     u4  checksum;
   
7.     u1  signature[kSHA1DigestLen];
   
8.     u4  fileSize;
   
9.     u4  headerSize;
   
10.     u4  endianTag;
    
11.     u4  linkSize;
    
12.     u4  linkOff;
    
13.     u4  mapOff;
    
14.     u4  stringIdsSize;
    
15.     u4  stringIdsOff;
    
16.     u4  typeIdsSize;
    
17.     u4  typeIdsOff;
    
18.     u4  protoIdsSize;
    
19.     u4  protoIdsOff;
    
20.     u4  fieldIdsSize;
    
21.     u4  fieldIdsOff;
    
22.     u4  methodIdsSize; // 这里存放了方法字段索引的大小，methodIdsSize的类型为u4
    
23.     u4  methodIdsOff;
    
24.     u4  classDefsSize;
    
25.     u4  classDefsOff;
    
26.     u4  dataSize;
    
27.     u4  dataOff;
    
28. };

复制代码

u4的类型定义如下：

1. /*
   
2. * These match the definitions in the VM specification.
   
3. */
   
4. typedef uint8_t             u1;
   
5. typedef uint16_t            u2;
   
6. typedef uint32_t            u4;
   
7. typedef uint64_t            u8;
   
8. typedef int8_t              s1;
   
9. typedef int16_t             s2;
   
10. typedef int32_t             s4;
    
11. typedef int64_t             s8;

复制代码

进一步推出，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里找到了抛出异常的地方：

1. /**
   
2. * Combine two dex files into one.
   
3.   */
   
4. public final class DexMerger {
   
5. 
   
6.     private void mergeMethodIds() {
   
7.         new IdMerger<MethodId>(idsDefsOut) {
   
8.             @Override TableOfContents.Section getSection(TableOfContents tableOfContents) {
   
9.                 return tableOfContents.methodIds;
   
10.             }
    
11. 
    
12.             @Override MethodId read(Dex.Section in, IndexMap indexMap, int index) {
    
13.                 return indexMap.adjust(in.readMethodId());
    
14.             }
    
15. 
    
16.             @Override void updateIndex(int offset, IndexMap indexMap, int oldIndex, int newIndex) {
    
17.                 if (newIndex < 0 || newIndex > 0xffff) {
    
18.                     throw new DexIndexOverflowException(
    
19.                             "method ID not in [0, 0xffff]: " + newIndex);
    
20.                 }
    
21.                 indexMap.methodIds[oldIndex] = (short) newIndex;
    
22.             }
    
23. 
    
24.             @Override void write(MethodId methodId) {
    
25.                 methodId.writeTo(idsDefsOut);
    
26.             }
    
27.         }.mergeSorted();
    
28.     }
    
29. }

复制代码

这里定义了indexMap的methodIds的单项值要强转short，所以在存放之前check一下范围是不是0 ~ 0xffff。我们看看IndexMap的定义：

1. /**
   
2. * Maps the index offsets from one dex file to those in another. For example, if
   
3. * you have string #5 in the old dex file, its position in the new dex file is
   
4. * {@code strings[5]}.
   
5. */
   
6. public final class IndexMap {
   
7.     private final Dex target;
   
8.     public final int[] stringIds;
   
9.     public final short[] typeIds;
   
10.     public final short[] protoIds;
    
11.     public final short[] fieldIds;
    
12.     public final short[] methodIds;
    
13. 
    
14.     // ... ...
    
15. }

复制代码

看上去是对了，可是这个DexMerger是合并两个dex的，默认情况下我们只有一个dex的，那么这个65k是哪里限制的呢？再查！

4. 回归DexFile

基本上前面基本是一个摸着石头过河、反复验证网络说法的一个过程，虽然回想起来傻傻的，但是这种记录还是有必要的。

前面看到DexFile的存放方法数大小的类型是uint32，但是根据后面的判断，我们确定是打包的过程中产生了65k问题，所以我们得回过头老老实实研究一下dx的打包流程。

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

OK，我把dx打包涉及到流程记录下来：

1. // 源码目录：dalvik/dx
   
2. // Main.java
   
3. -> main() -> run() -> runMonoDex()(或者runMultiDex()) -> writeDex()
   
4. // DexFile
   
5. -> toDex() -> toDex0()
   
6. // MethodIdsSection extends MemberIdsSection extends UniformItemSection extends  Section
   
7. -> prepare() -> prepare0() -> orderItems() -> getTooManyMembersMessage()
   
8. // Main.java
   
9. -> getTooManyIdsErrorMessage()

复制代码

最终狐狸的尾巴是在MemberIdsSection漏出来了：

1. package com.android.dx.dex.file;
   
2. 
   
3. import com.android.dex.DexException;
   
4. import com.android.dex.DexFormat;
   
5. import com.android.dex.DexIndexOverflowException;
   
6. import com.android.dx.command.dexer.Main;
   
7. 
   
8. import java.util.Formatter;
   
9. import java.util.Map;
   
10. import java.util.TreeMap;
    
11. import java.util.concurrent.atomic.AtomicInteger;
    
12. 
    
13. /**
    
14. * Member (field or method) refs list section of a {@code .dex} file.
    
15. */
    
16. public abstract class MemberIdsSection extends UniformItemSection {
    
17. 
    
18.     /**
    
19.      * Constructs an instance. The file offset is initially unknown.
    
20.      *
    
21.      * @param name {@code null-ok;} the name of this instance, for annotation
    
22.      * purposes
    
23.      * @param file {@code non-null;} file that this instance is part of
    
24.      */
    
25.     public MemberIdsSection(String name, DexFile file) {
    
26.         super(name, file, 4);
    
27.     }
    
28. 
    
29.     /** {@inheritDoc} */
    
30.     @Override
    
31.         protected void orderItems() {
    
32.             int idx = 0;
    
33. 
    
34.             if (items().size() > DexFormat.MAX_MEMBER_IDX + 1) {
    
35.                 throw new DexIndexOverflowException(getTooManyMembersMessage());
    
36.             }
    
37. 
    
38.             for (Object i : items()) {
    
39.                 ((MemberIdItem) i).setIndex(idx);
    
40.                 idx++;
    
41.             }
    
42.         }
    
43. 
    
44.     private String getTooManyMembersMessage() {
    
45.         Map<String, AtomicInteger> membersByPackage = new TreeMap<String, AtomicInteger>();
    
46.         for (Object member : items()) {
    
47.             String packageName = ((MemberIdItem) member).getDefiningClass().getPackageName();
    
48.             AtomicInteger count = membersByPackage.get(packageName);
    
49.             if (count == null) {
    
50.                 count = new AtomicInteger();
    
51.                 membersByPackage.put(packageName, count);
    
52.             }
    
53.             count.incrementAndGet();
    
54.         }
    
55. 
    
56.         Formatter formatter = new Formatter();
    
57.         try {
    
58.             String memberType = this instanceof MethodIdsSection ? "method" : "field";
    
59.             formatter.format("Too many %s references: %d; max is %d.%n" +
    
60.                     Main.getTooManyIdsErrorMessage() + "%n" +
    
61.                     "References by package:",
    
62.                     memberType, items().size(), DexFormat.MAX_MEMBER_IDX + 1);
    
63.             for (Map.Entry<String, AtomicInteger> entry : membersByPackage.entrySet()) {
    
64.                 formatter.format("%n%6d %s", entry.getValue().get(), entry.getKey());
    
65.             }
    
66.             return formatter.toString();
    
67.         } finally {
    
68.             formatter.close();
    
69.         }
    
70.     }
    
71. 
    
72. }

复制代码

里面有一段：

1. // 如果方法数大于0xffff就提示65k错误
   
2. if (items().size() > DexFormat.MAX_MEMBER_IDX + 1) {
   
3.     throw new DexIndexOverflowException(getTooManyMembersMessage());
   
4. }
   
5. 
   
6. // 这个DexFormat.MAX_MEMBER_IDX就是0xFFFF
   
7. /**
   
8. * Maximum addressable field or method index.
   
9. * The largest addressable member is 0xffff, in the "instruction formats" spec as field@CCCC or
   
10. * meth@CCCC.
    
11. */
    
12. public static final int MAX_MEMBER_IDX = 0xFFFF;

复制代码

至此，真相大白！

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问题了。
  

以上纯属我个人推测，一切以科学分析为准。