首页 > 代码库 > Dalvik虚拟机中DexClassLookup结构解析

Dalvik虚拟机中DexClassLookup结构解析

http://blog.csdn.net/roland_sun/article/details/46877563 原文如下:

在Android系统中,所有的类定义以及具体的代码都是包含在DEX文件中的。但是,一个功能丰富的程序往往都比较复杂,由很多类组成。

而每一个类,都由一个所谓类描述符(Class Descriptor)的字符串来唯一标识,两个类不可能有同一个类描述符。类描述符不仅包含类名,还包含了类所在的包名。例如,如果你的类所在包名是“com.trendmicro.mars”,且类名是“Test”的话,那么这个类的类描述符就是“Lcom/trendmicro/mars/Test;”。

但是,如果要从一个DEX文件内的众多类中找出那个你想使用的类,仅仅通过逐一比较DEX文件中所有类的类描述符字符串的话,速度往往会比较慢,用户体验会比较差。

Dalvik虚拟机为了解决这个问题,在加载和验证一个DEX文件的时候,会附带生成一个所谓的DexClassLookup结构体,来加快类的查找速度。

[cpp] view plain copy
 
  1. struct DexClassLookup {  
  2.     int     size;  
  3.     int     numEntries;  
  4.     struct {  
  5.         u4      classDescriptorHash;  
  6.         int     classDescriptorOffset;  
  7.         int     classDefOffset;  
  8.     } table[1];  
  9. };  

结构体最开始是一个int型的size,表示了这个DexClassLookup结构体到底要占用多少字节的空间。这个大小也包含了size变量本身的4字节。

接下来的int型numEntries,表示DexClassLookup到底包含了多少个条目。

最后定义了一个内部结构体,存放具体的数据。不过table[1]并不是表示DexClassLookup中只包含一项这个结构体数据,这里只表示下面的是一个数组,具体有多少项,是由前面的numEntries来指定的。

下面,我们来看看,到底这个结构体是如何生成的(代码位于\dalvik\libdex\DexFile.cpp内):

[cpp] view plain copy
 
  1. DexClassLookup* dexCreateClassLookup(DexFile* pDexFile)  
  2. {  
  3.     DexClassLookup* pLookup;  
  4.     int allocSize;  
  5.     int i, numEntries;  
  6.     int numProbes, totalProbes, maxProbes;  
  7.   
  8.     numProbes = totalProbes = maxProbes = 0;  
  9.   
  10.     assert(pDexFile != NULL);  
  11.   
  12.     numEntries = dexRoundUpPower2(pDexFile->pHeader->classDefsSize * 2);  
  13.     allocSize = offsetof(DexClassLookup, table)  
  14.                     + numEntries * sizeof(pLookup->table[0]);  
  15.   
  16.     pLookup = (DexClassLookup*) calloc(1, allocSize);  
  17.     if (pLookup == NULL)  
  18.         return NULL;  
  19.     pLookup->size = allocSize;  
  20.     pLookup->numEntries = numEntries;  
  21.   
  22.     for (i = 0; i < (int)pDexFile->pHeader->classDefsSize; i++) {  
  23.         const DexClassDef* pClassDef;  
  24.         const char* pString;  
  25.   
  26.         pClassDef = dexGetClassDef(pDexFile, i);  
  27.         pString = dexStringByTypeIdx(pDexFile, pClassDef->classIdx);  
  28.   
  29.         classLookupAdd(pDexFile, pLookup,  
  30.             (u1*)pString - pDexFile->baseAddr,  
  31.             (u1*)pClassDef - pDexFile->baseAddr, &numProbes);  
  32.   
  33.         if (numProbes > maxProbes)  
  34.             maxProbes = numProbes;  
  35.         totalProbes += numProbes;  
  36.     }  
  37.   
  38.     ...  
  39.   
  40.     return pLookup;  
  41. }  

代码首先确定到底要存放多少条数据。注意,并不是有多少个类就生成多少个条目的。可以看到,具体生成的条目数是类的个数乘以2,然后再算下一个2的幂次方。比如,如果我有5个类的话,那么首先乘以2,得到10,下一个2的幂次方数字是16,,就会生成16个条目。为什么要这么做?我觉得是为了尽量减少Hash碰撞的情况发生。

知道了要创建多少条目的数据后,就可以知道到底要开辟多大的空间来存放这个结构体数据(按照现在的定义,分配空间的计算公式是8+numEntries*12),并且在内存中为这个结构体分配一段连续的空间。接着,对DexClassLookup结构体的前两个变量size和numEntries赋值。

最后,就是要来填写具体的数据了。程序中会遍历DEX文件中包含的每一个类,逐一获得它们的DexClassDef结构和类描述符,且传递给classLookupAdd函数,让它来填写对应该类的快速查找数据(代码位于\dalvik\libdex\DexFile.cpp内):

[cpp] view plain copy
 
  1. static void classLookupAdd(DexFile* pDexFile, DexClassLookup* pLookup,  
  2.     int stringOff, int classDefOff, int* pNumProbes)  
  3. {  
  4.     const char* classDescriptor =  
  5.         (const char*) (pDexFile->baseAddr + stringOff);  
  6.     const DexClassDef* pClassDef =  
  7.         (const DexClassDef*) (pDexFile->baseAddr + classDefOff);  
  8.     u4 hash = classDescriptorHash(classDescriptor);  
  9.     int mask = pLookup->numEntries-1;  
  10.     int idx = hash & mask;  
  11.   
  12.     int probes = 0;  
  13.     while (pLookup->table[idx].classDescriptorOffset != 0) {  
  14.         idx = (idx + 1) & mask;  
  15.         probes++;  
  16.     }  
  17.   
  18.     pLookup->table[idx].classDescriptorHash = hash;  
  19.     pLookup->table[idx].classDescriptorOffset = stringOff;  
  20.     pLookup->table[idx].classDefOffset = classDefOff;  
  21.     *pNumProbes = probes;  
  22. }  

函数首先调用classDescriptorHash,计算出类描述符对应的一个Hash值,这是一个数字。

然后,代码会根据条目数的多少,计算出一个mask,并且和前面计算的Hash值与以下,算出该条数据在数组中存放位置的下标。前面说过了,数据的条目数一定是2的幂次方。比如,如果是8的话,下标值就取Hash值得后三位,16的话就取Hash值得后四位。这也就解释了,为什么快速查找数据的条目数必须是2的幂次方了。

接下来,看看数组中这个下标对应的条目是不是已经存放了别的类的信息。这种情况,就是碰撞,两个不同的类被映射到了同一个数字上。一旦出现了碰撞的情况话,程序接着用了一种非常简单的处理方法,直接将下标加1,和mask再与一下,得到接着要尝试存放的那个位置,再重头判断一下,直到找到一个没有被用过的位置。但是,这样处理,有可能会占了别的类应该存放的位置,使得性能下降。所以,前面的代码在计算条目数的时候,人为的乘以2,降低了碰撞的概率。不过这样处理的话,存储空间会比较浪费。最后,找到了一个空的位置后,会将对应类的具体数据,包括前面算的类描述符Hash值、类描述符字符串和该类的DexClassDef相对于DEX文件头的偏移量等信息,存放在该位置上。

好了,看完了如何生成DexClassLookup结构体数据,我们再来看看Dalvik虚拟机是如何利用它来加快类的查找速度的(代码位于\dalvik\libdex\DexFile.cpp内):

[cpp] view plain copy
 
  1. const DexClassDef* dexFindClass(const DexFile* pDexFile,  
  2.     const char* descriptor)  
  3. {  
  4.     const DexClassLookup* pLookup = pDexFile->pClassLookup;  
  5.     u4 hash;  
  6.     int idx, mask;  
  7.   
  8.     hash = classDescriptorHash(descriptor);  
  9.     mask = pLookup->numEntries - 1;  
  10.     idx = hash & mask;  
  11.   
  12.     while (true) {  
  13.         int offset;  
  14.   
  15.         offset = pLookup->table[idx].classDescriptorOffset;  
  16.         if (offset == 0)  
  17.             return NULL;  
  18.   
  19.         if (pLookup->table[idx].classDescriptorHash == hash) {  
  20.             const char* str;  
  21.   
  22.             str = (const char*) (pDexFile->baseAddr + offset);  
  23.             if (strcmp(str, descriptor) == 0) {  
  24.                 return (const DexClassDef*)  
  25.                     (pDexFile->baseAddr + pLookup->table[idx].classDefOffset);  
  26.             }  
  27.         }  
  28.   
  29.         idx = (idx + 1) & mask;  
  30.     }  
  31. }  

查找的代码就非常简单了,还是先对要查找类的类描述符,用同样的算法计算一下Hash值,根据条目的数目,取Hash值相应的低几位。以这个值为下标,尝试读取数组中对应位置的数据。如果没有碰撞情况发生的话,一次就能找到你想找的类。如果有碰撞情况的话,还是试着循环查找下一个位置的信息。所以,可以看出来,查找的时候,是将字符串的逐个字符比较转变成了一个四字节数字的比较,速度大大加快了。

对每一个DEX文件来说,其实只需要在最开始计算一次就可以了,没必要每次加载的时候都计算一遍。大家知道,一个DEX文件在第一次被加载的时候,Dalvik虚拟机会对其进行验证和优化,从而以后再次加载这个DEX文件的时候,可以直接读取优化过得ODEX文件,加快加载速度。而在ODEX文件中,其实就包含了对应于这个DEX文件的DexClassLookup结构体数据,直接mmap到内存就好了,不需要再算了。

这里再引申讨论一下,为什么DEX文件中不直接包含对应的DexClassLookup结构体数据呢,就像ELF文件一样?理论上其实是可以的,因为这些都是静态数据,不会在运行的时候改变。我想唯一的解释估计是android不想把快速查找的功能和DEX绑死,而是由Dalvik虚拟机自己实现。这样,不同版本的虚拟机完全可以使用不同的快速查找算法。

 

Dalvik虚拟机中DexClassLookup结构解析