ART虚拟机 | 接口方法调用的具体实现

Java语言中，一个新创建的类只能继承一个父类，但是可以实现多个接口。这两种不同的语言特性使得多态在虚拟机中的实现也不相同。具体而言，当我们调用virtual方法时，可以使用对象所属类的virtual table进行派发，其中的元素为ArtMethod。父类方法在前，子类方法拼接在后，因此不论经过多少次继承，每个方法在vtable中的偏移都是固定的。所谓的覆盖(override)，无非就是替换掉父类方法所在位置的指针值，使其指向子类实现的新的ArtMethod。那么调用接口方法呢？当一个类实现多个接口时，我们又该用怎样的数据结构进行派发呢？

先看一个具体的例子。

protected static final void checkOffset(int offset, CharacterIterator text) {if (offset < text.getBeginIndex() || offset > text.getEndIndex()) {throw new IllegalArgumentException("offset out of bounds");}
}public interface CharacterIterator extends Cloneable {...
}

传入的参数text为接口类型，它的真实类型一定是某个实现了CharacterIterator的类。此外，调用的具体方法为CharacterIterator.getBeginIndex()。因此，ART在调用发生前可以知道CharacterIterator.getBeginIndex()对应的ArtMethod（注意是接口的ArtMethod，而不是子类最终实现的ArtMethod），以及text这个对象。方法派发的目的就是根据text和CharacterIterator.getBeginIndex()的ArtMethod找到子类最终实现的ArtMethod，从而跳转过去。这句话很重要，值得全体复诵。

回到开头那个问题：当一个类实现多个接口时，我们又该用怎样的数据结构进行方法派发呢？一个自然的想法是：既然一个类可以实现多个接口，那为何不为每个接口创建一个单独的vtable？然后通过二级列表的方式进行派发？事实上，ART也是这么做的。

在这里插入图片描述

art::mirror::Class中有一个字段名为iftable_，它是一个用HeapReference封装的指针，指向一个art::mirror::IfTable对象。这里的If指的便是interface。IfTable中每个接口占用两个slot，第一个slot存储的是该接口对应的art::mirror::Class指针，第二个slot存储的是一个Array指针，其中存储了一系列ArtMethod*，表示该接口中方法的具体实现。当ART采用这种方式进行方法派发时，它会做如下几步：

通过text这样的art::mirror::Object拿到它的类指针，Class*存储在Object的第一个字段klass_中。
通过CharacterIterator.getBeginIndex()这样的ArtMethod拿到它的类指针，Class*存储在ArtMethod的第一个字段declaring_class_中。
找到对象所属Class的IfTable，遍历其中的接口，判断它和第二步拿到的接口方法的类是否相等，从而取出接口所对应的Method Array。
将接口方法中的method_index_字段作为index，找出Method Array中对应位置的ArtMethod*。

如此一来便可以找到子类中最终实现的接口方法。

属于Class的IfTable会在类加载的时候创建并填充，具体在LinkMethods阶段。值得注意的是，一个类所实现的接口包含以下三种含义，其中重复的接口会在填充时被去重。

该类直接implements的所有接口。
上述接口所继承的所有接口。(super-interface)
父类所实现的所有接口。(superclass’s interfaces)

这种派发方式较为简单，且IfTable包含了所有的派发信息。但是它的性能并不好，尤其是当一个类实现了很多接口时。因此，ART只会迫不得已才fallback到这种方式。这个概念有点像CPU的多级缓存，L0、L1虽然速度快，但是存储的信息少，当无法满足访问要求时，CPU将不得不从L2、L3甚至主存中读取信息。这里我们将IfTable类比为L2 Cache，那么ART中接口方法派发的“L0 Cache”、“L1 Cache”又在哪里呢？

下面我们引入了一个新的概念：IMTable，它的全称是interface method table。通过该结构进行接口方法派发的方式首次发表在2001年的论文《Efficient Implementation of Java Interfaces: Invokeinterface Considered Harmless》1中。这种方式综合考虑了内存占用和性能开销，做到了两方面的平衡和高效，因此一直沿用至今。

在这里插入图片描述

IMTable是一个长度固定为43的数组，其中的元素是ArtMethod*。当我们拿到一个接口方法时，可以将它里面的特殊字段imt_index_作为index，从而找到数组中对应位置的ArtMethod*。之所以说imt_index_特殊，是因为ART只会在加载抽象方法时才给它赋值，而invoke-interface的那些接口方法恰好属于抽象方法。

imt_index_的计算方式如下，通过类名、方法名和签名综合计算出一个哈希值，再用哈希值余上43，得到[0,42]范围内的值。

// Magic configuration that minimizes some common runtime calls.
static constexpr uint32_t kImTableHashCoefficientClass = 427;
static constexpr uint32_t kImTableHashCoefficientName = 16;
static constexpr uint32_t kImTableHashCoefficientSignature = 14;mixed_hash = kImTableHashCoefficientClass * class_hash + kImTableHashCoefficientName * name_hash + kImTableHashCoefficientSignature * signature_hash;
imt_index_ = mixed_hash % ImTable::kSize;

至于IMTable的长度为什么取43，以及三个哈希值的系数为什么这么取，我并没有准确的答案。但我有一个猜测：它们的最终目的是为了让不同接口方法计算出的imt_index_在[0,42]范围内均匀分布，或者更加智能一些，让频繁调用的接口方法独占某些序号，让不频繁的接口方法共享一些序号。至于原因，后面会给出。

和IfTable相同，IMTable也会在类加载的过程中创建并填充。填充结束的IMTable中会存在三种类型的ArtMethod*：

Unimplemented method，表示没有接口方法的imt_index_等于这个序号，对应上图的白色。
Implemented method，表示只有一个接口方法的imt_index_等于这个序号，对应上图的绿色。
Conflict method，表示有多个（≥2）接口方法的imt_index_等于这个序号，这种情况称为“碰撞”，或者“冲突”。对应上图的紫色。

当我们拿着接口方法的imt_index_作为序号去寻找时，如果找到implemented method，那么也就找到了最终的实现。可是如果找到的是Conflict method，那么还得去解冲突。Implemented method和Conflict method都是一个ArtMethod对象，作为调用方而言，它从IMTable中拿回一个ArtMethod可不会管它是什么类型，而是直接跳转到它的entry_point_from_quick_compiled_code_去。区别在于，Implemented method的entry_point_from_quick_compiled_code_指向最终实现的函数入口，而Conflict method的entry_point_from_quick_compiled_code_指向一个Conflict Resolution Function。

解冲突需要一个新的数据结构：ImtConflictTable。在这个结构里，每个接口方法和它的最终实现方法组成一对，顺次排列。解冲突的过程就是拿着接口方法的指针遍历ImtConflictTable，从而找出最终实现方法。

ImtConflictTable中的数据并非在类加载过程中填充，而是在第一次方法调用时填充，这个概念有点类似于"lazy load"。当第一次调用发生时，ImtConflictTable中搜索不到对应的接口方法，ART会选择fallback到IfTable中，根据接口方法的类型，选择对应的method array并找出最终实现。之后再将接口方法和找到的实现方法填入到ImtConflictTable中，方便下次寻找。

至此，整个接口方法的调用过程便阐述完毕。回到三级缓存的比喻中，IMTable相当于L0 Cache，ImtConflictTable相当于L1 Cache，而IfTable则相当于L2 Cache。此外，IMTable和IfTable中的数据在类加载的过程中填充完毕，而ImtConflictTable中的数据则等到第一次调用发生时才填充，属于lazy load。

下面我们通过一段Java代码和对应的汇编代码来验证上述分析。

[Java代码]

protected static final void checkOffset(int offset, CharacterIterator text) {if (offset < text.getBeginIndex() || offset > text.getEndIndex()) {throw new IllegalArgumentException("offset out of bounds");}
}public interface CharacterIterator extends Cloneable {...
}

[Dex字节码]

1: void java.text.IcuIteratorWrapper.checkOffset(int, java.text.CharacterIterator) (dex_method_idx=13041)DEX CODE:0x0000: 7210 b931 0300           	| invoke-interface {v3}, int java.text.CharacterIterator.getBeginIndex() // method@127290x0003: 0a00                     	| move-result v00x0004: 3402 0900                	| if-lt v2, v0, +90x0006: 7210 ba31 0300           	| invoke-interface {v3}, int java.text.CharacterIterator.getEndIndex() // method@12730

[text.getBeginIndex()的汇编代码，通过oatdump生成]

//checkOffset是静态方法，x0存储checkOffset方法对应的ArtMethod*，x1存储第一个参数offset，x2存储第二个参数text。这条指令将x2里的内容复制到x1中。
0x0022817c: aa0203e1	mov x1, x2
//将x1中的内容复制到x23中，其他地方会使用x23，不过与本话题无关。
0x00228180: aa0103f7	mov x23, x1
//参数text作为引用类型，传递的实际上是art::mirror::Object*，Object的第一个字段为art::mirror::Class*，也即该对象所属的类。因此这条指令执行后，w0里将存有art::mirror::Class*。之所以用32位的w0，而不是64位的x0，是因为Java Heap位于虚拟地址中的低位，32位地址表示的4G空间足够容纳Heap。
0x00228184: b9400020	ldr w0, [x1]
//adrp和add指令会计算出CharacterIterator.checkOffset方法所对应的ArtMethod的地址，注意是接口的方法，而不是继承接口的类中的方法。该地址位于boot.art范围内，表示该方法的内存结构在.art文件中被提前创建。
0x00228188: b0ffe051	adrp x17, #-0x3f7000 (addr -0x1cf000)
0x0022818c: 912ee231	add x17, x17, #0xbb8 (3000)
//art::mirror::Class中偏移128的位置存储的是(interface method table)IMTable*，该table长度固定，当前版本为43。
0x00228190: f9404000	ldr x0, [x0, #128]
//取出IMTable中第14个元素，序号由接口方法的名称哈希得出，偏移为14*8=112。取出的元素为ArtMethod*。
0x00228194: f9403800	ldr x0, [x0, #112]
//取出ArtMethod的字段entry_point_from_quick_compiled_code_，该字段存储方法的汇编入口。
0x00228198: f9400c1e	ldr lr, [x0, #24]
//跳转到目标方法的汇编入口处。
0x0022819c: d63f03c0	blr lr

前文我们提到，接口方法派发需要两个信息，一个是调用的对象，另一个是接口方法的ArtMethod。通过上面的汇编代码可知，调用对象可以通过参数传递，而ArtMethod则通过adrp和add指令计算得出。至于两条指令后面跟的偏移值为什么是这个数字，这又牵扯到ArtMethod的加载过程。对于大部分boot class，它们里面的ArtMethod会通过adrp定位到boo.art文件里。而对于大部分APP而言，它们的ArtMethod通常通过ODEX文件中的.bss段来寻找。至于具体细节，以后再写一篇文章详述吧。

// Determines how to load an ArtMethod*.
enum class MethodLoadKind {// Use a String init ArtMethod* loaded from Thread entrypoints.kStringInit,// Use the method's own ArtMethod* loaded by the register allocator.kRecursive,// Use PC-relative boot image ArtMethod* address that will be known at link time.// Used for boot image methods referenced by boot image code.kBootImageLinkTimePcRelative,// Load from an entry in the .data.bimg.rel.ro using a PC-relative load.// Used for app->boot calls with relocatable image.kBootImageRelRo,// Load from an entry in the .bss section using a PC-relative load.// Used for methods outside boot image referenced by AOT-compiled app and boot image code.kBssEntry,// Use ArtMethod* at a known address, embed the direct address in the code.// Used for for JIT-compiled calls.kJitDirectAddress,// Make a runtime call to resolve and call the method. This is the last-resort-kind// used when other kinds are unimplemented on a particular architecture.kRuntimeCall,
};

最后

如果想要成为架构师或想突破20~30K薪资范畴，那就不要局限在编码，业务，要会选型、扩展，提升编程思维。此外，良好的职业规划也很重要，学习的习惯很重要，但是最重要的还是要能持之以恒，任何不能坚持落实的计划都是空谈。

如果你没有方向，这里给大家分享一套由阿里高级架构师编写的《Android八大模块进阶笔记》，帮大家将杂乱、零散、碎片化的知识进行体系化的整理，让大家系统而高效地掌握Android开发的各个知识点。
在这里插入图片描述
相对于我们平时看的碎片化内容，这份笔记的知识点更系统化，更容易理解和记忆，是严格按照知识体系编排的。