Android 65K问题之65K来源探究

news/2024/11/29 9:44:28/

65K问题相信不少人都遇到过,65K即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 
65536按1024算的话,是64k = 64 
65536按1024算的话,是64k = 64 
65536按1024算的话,是64k = 64 
1024。
重点是65536=2^16,请大家记住这个数字。
时间点
从大家的经历和这篇文章:
http://developer.android.com/tools/building/multidex.html
来看,这个错误是发生在构建时期。
65536是怎么算出来的?
65536网上众说纷纭,有对的,有不全对的,也有错的。
下面将跟踪最新的AOSP源码来顺藤摸瓜,但是探索问题必然迂回冗余,仅作记录,读者可直接跳过看结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
 * 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;
};
u4的类型定义如下:
1
2
3
4
5
6
7
8
9
10
11
/*
 * 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;
进一步推出,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类型,特此说明。
这个说法源自:
当Android系统启动一个应用的时候,有一步是对Dex进行优化,这个过程有一个专门的工具来处理,叫DexOpt。DexOpt的执行过程是在第一次加载Dex文件的时候执行的。这个过程会生成一个ODEX文件,即Optimised Dex。执行ODex的效率会比直接执行Dex文件的效率要高很多。但是在早期的Android系统中,DexOpt有一个问题,也就是这篇文章想要说明并解决的问题。DexOpt会把每一个类的方法id检索起来,存在一个链表结构里面。但是这个链表的长度是用一个short类型来保存的,导致了方法id的数目不能够超过65536个。当一个项目足够大的时候,显然这个方法数的上限是不够的。尽管在新版本的Android系统中,DexOpt修复了这个问题,但是我们仍然需要对老系统做兼容。
鉴于我能力有限,没有找到这块逻辑对应的代码。
但我有个疑问,这个限制是在Android启动一个应用的时候发生的,但从前面的“时间点”章节,65k问题是在构建的时候就发生了,还没到启动或者运行这一步。
我不敢否定这种说法,但说明65k至少还有其他地方限制。
只能在dalvik目录下搜索关键字”methid ID not in”,在DexMergger里找到了抛出异常的地方:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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();
    }
}
这里定义了indexMap的methodIds的单项值要强转short,所以在存放之前check一下范围是不是0 ~ 0xffff。
我们看看IndexMap的定义:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 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;

    // ... ...
}
看上去是对了,可是这个DexMerger是合并两个dex的,默认情况下我们只有一个dex的,那么这个65k是哪里限制的呢?再查!
基本上前面基本是一个摸着石头过河、反复验证网络说法的一个过程,虽然回想起来傻傻的,但是这种记录还是有必要的。
前面看到DexFile的存放方法数大小的类型是uint32,但是根据后面的判断,我们确定是打包的过程中产生了65k问题,所以我们得回过头老老实实研究一下dx的打包流程。
… 此处省略分析流程5000字 …
OK,我把dx打包涉及到流程记录下来:
1
2
3
4
5
6
7
8
9
// 源码目录: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漏出来了:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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();
        }
    }

}
里面有一段:
1
2
3
4
5
6
7
8
9
10
11
12
// 如果方法数大于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;
至此,真相大白!
为什么定义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:以上分析得到群里很多朋友的讨论和帮忙。
我好像明白了什么:
65k问题是dx打包单个Dex时报的错,所以只要用dx打包单个dex就可能有这个问题。
不仅方法数,字段数也有65k问题。
目前来说,65k问题和系统无关。
目前来说,65k问题和art无关。
即使分包MultiDex,当主Dex的方法数超过65k依然会报错。
MultiDex方案不是从根本上解决了65k问题,但是大大缓解甚至说基本解决了65k问题。
新的Jack能否解决65k问题?
Jack (Java Android Compiler Kit) is a new Android toolchain that comprises a compiler from Java programming language source to the Android dex file format. Jack and Jill Application Build
新的编译器目前还不了解实现的细节,网上的资料是说解决了65k问题,但看了最新的图,我觉得并不能终结65k问题,暂无法评论。
1. 首先,查找Dex的结构定义。
2. DexOpt优化造成?
3. DexMerger的检测
4. 回归DexFile

5. 根本原因

6. 回顾

本文转载:http://jayfeng.com/2016/03/10/由ANdroid-65k方法限制引发的思考


http://www.ppmy.cn/news/130838.html

相关文章

聚类分析(K-means算法)

1 聚类分析 1.1 相似度与距离度量1.2 聚类算法 及 划分方法 2 聚类模型评估&#xff08;优缺点&#xff09;3 K-means 在 sklearn方法4 确定K值–肘部法则–SSE5 模型评估指标–轮廓系数法–最近簇 5.1 轮廓系数5.2 最近簇定义—平均轮廓系数 [0,1]&#xff1a;5.3、Canopy算法…

K-means聚类算法

目录 简介 对距离的度量及SSE 问题及如何避免 k-means示例 k值选取 肘方法 可视化方法 TSNE 雷达图 总结一些对K-means聚类算法的理解。 K-means是一种聚类分析方法&#xff0c;聚类分析即是在没有给定划分类别的情况下&#xff0c;根据数据自身的相似度对样本数据进行…

K-Means中K值的选取

K-Means中K值的选择 &#xff08;1&#xff09;拍脑袋法&#xff08;2&#xff09;肘部法则&#xff08;Elbow Method&#xff09;&#xff08;3&#xff09;间隔统计量&#xff08;Gap Statistic&#xff09;&#xff08;4&#xff09;轮廓系数&#xff08;Silhouette Coeffic…

k近邻算法

本文来自的CSDN 博客 &#xff0c;全文地址请点击&#xff1a;https://blog.csdn.net/qq_35082030/article/details/60965320?utm_sourcecopy 0. 写在前面 在这一讲的讨论班中&#xff0c;我们将要讨论一下K近邻模型。可能有人会说&#xff0c;K近邻模型有什么好写的&#x…

华为k662c的虚拟服务器,华为k662c路由器怎么设置 | 华为k662c路由器设置_什么值得买...

WIFI6光猫(无线路由器)华为K662C使用设置 2021-01-09 18:50:50 39点赞 155收藏 64评论 华为K662C是一个三合一的设备,有3种工作模式。一种是光猫模式,另外一种是无线路由器模式,还有一种是光纤组网模式(设置较复杂,需要补全shell和更新固件程序,不推荐普通用户尝试,这里就…

K-D树算法的一些总结

在2016年ACM ICPC青岛站的比赛中&#xff0c;一道K-D树问题成为了金银牌的分界线&#xff0c;最后由我们队一个强力队友写出了该题&#xff0c;其实那题本来该由我负责的&#xff0c;都怪我学艺不精。 k-d树&#xff08;k-dimensional树的简称&#xff09;&#xff0c;是一种分…

不足20行 python 代码,高效实现 k-means 均值聚类算法

scikti-learn 将机器学习分为4个领域&#xff0c;分别是分类(classification)、聚类(clustering)、回归(regression)和降维(dimensionality reduction)。k-means均值算法虽然是聚类算法中比较简单的一种&#xff0c;却包含了丰富的思想内容&#xff0c;非常适合作为初学者的入门…

k-d tree树 近邻算法

k-d树(k-dimensional树的简称),是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。 应用背景 SIFT算法中做特征点匹配的时候就会利用到k-d树。而特征点匹配实际上就是一个通过距离函数在高维矢量之间进行相似性检索的问题。…