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虚拟机 | 接口方法调用的具体实现

art::mirror::Class中有一个字段名为iftable_，它是一个用HeapReference封装的指针，指向一个art::mirror::IfTable方针。这儿的If指的就是interface。IfTable中每个接口占用两个slot，第一个slot存储的是该接口对应的art::mirror::Class指针，第二个slot存储的是一个Array指针，其间存储了一系列ArtMethod*，表明该接口中办法的详细完成。当ART选用这种办法进行办法派发时，它会做如下几步：

  1. 经过text这样的art::mirror::Object拿到它的类指针，Class*存储在Object的第一个字段klass_中。
  2. 经过CharacterIterator.getBeginIndex()这样的ArtMethod拿到它的类指针，Class*存储在ArtMethod的第一个字段declaring_class_中。
  3. 找到方针所属Class的IfTable，遍历其间的接口，判别它和第二步拿到的接口办法的类是否持平，然后取出接口所对应的Method Array。
  4. 将接口办法中的method_index_字段作为index，找出Method Array中对应方位的ArtMethod*。

如此一来便能够找到子类中终究完成的接口办法。

归于Class的IfTable会在类加载的时候创立并填充，详细在LinkMethods阶段。值得留意的是，一个类所完成的接口包含以下三种意义，其间重复的接口会在填充时被去重。

  1. 该类直接implements的一切接口。
  2. 上述接口所承继的一切接口。(super-interface)
  3. 父类所完成的一切接口。(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中。这种办法归纳考虑了内存占用和功能开支，做到了两方面的平衡和高效，因而一向沿用至今。

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

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*：

  1. Unimplemented method，表明没有接口办法的imt_index_等于这个序号，对应上图的白色。
  2. Implemented method，表明只有一个接口办法的imt_index_等于这个序号，对应上图的绿色。
  3. 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@12729
    0x0003: 0a00                     	| move-result v0
    0x0004: 3402 0900                	| if-lt v2, v0, +9
    0x0006: 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,
};

Footnotes

  1. citeseerx.ist.psu.edu/document?re… ↩