iOS底层原理总结 – 探寻Runtime本质(二)

释放双眼,带上耳机,听听看~!

《iOS底层原理总结 – 探寻block本质(一)》
《iOS底层原理总结 – 探寻block本质(二)》
《iOS底层原理总结 – 探寻Runtime本质(三)》
《iOS底层原理总结 – 探寻Runtime本质(四)》

本篇学习总结:

  • Class的结构
  • class_rw_t存储数据
  • Method知识
  • 方法缓存 cache_t

好了,带着问题,我们一一开始阅读吧 ?

一.Class的结构

通过上一篇中对isa本质结构有了新的认识,本篇总结一下Class的结构,重新认识一下Class内部结构。
首先来看一下Class的内部结构代码,我们之前也总结过《《iOS底层原理总结 – 探寻Class的本质》》 ,这里稍微简单回顾一下

struct objc_class : objc_object {
// Class ISA;
Class superclass;
cache_t cache;             // formerly cache pointer and vtable
class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
class_rw_t *data() {
return bits.data();
}
void setData(class_rw_t *newData) {
bits.setData(newData);
}
}
class_rw_t* data() {
return (class_rw_t *)(bits & FAST_DATA_MASK);
}

1.class_rw_t
上述源码中我们知道bits & FAST_DATA_MASK位运算之后,可以得到class_rw_t,而class_rw_t中存储着方法列表属性列表协议列表,来看一下class_rw_t这部分代码。

struct class_rw_t {
// Be warned that Symbolication knows the layout of this structure.
uint32_t flags;
uint32_t version;
const class_ro_t *ro;
method_array_t methods; // 方法列表
property_array_t properties; // 属性列表
protocol_array_t protocols; // 协议列表
Class firstSubclass;
Class nextSiblingClass;
char *demangledName;
};

上述代码中,class_rw_t里面的method_array_t,property_array_t,protocol_array_t都是二维数组,class_rw_t是可读可写的,其中包含了类的初始内容以及分类内容。
来到method_array_t,property_array_t,protocol_array_t内部看一下。这里以method_array_t为例,method_array_t本身就是一个数组,数组里面存放的是数组method_list_t,method_list_t里面最终存放的是method_t

class method_array_t :
public list_array_tt<method_t, method_list_t>
{
typedef list_array_tt<method_t, method_list_t> Super;
public:
method_list_t **beginCategoryMethodLists() {
return beginLists();
}
method_list_t **endCategoryMethodLists(Class cls);
method_array_t duplicate() {
return Super::duplicate<method_array_t>();
}
};
class property_array_t :
public list_array_tt<property_t, property_list_t>
{
typedef list_array_tt<property_t, property_list_t> Super;
public:
property_array_t duplicate() {
return Super::duplicate<property_array_t>();
}
};
class protocol_array_t :
public list_array_tt<protocol_ref_t, protocol_list_t>
{
typedef list_array_tt<protocol_ref_t, protocol_list_t> Super;
public:
protocol_array_t duplicate() {
return Super::duplicate<protocol_array_t>();
}
};

这里以method_array_t为例,图示其中的结构。

methods、properties、protocols内结构.png

2.class_ro_t

我们之前提到过class_ro_t中也有存储的方法属性协议列表,另外还有成员变量列表
接下来看一下class_ro_t部分代码

struct class_ro_t {
uint32_t flags;
uint32_t instanceStart;
uint32_t instanceSize;
#ifdef __LP64__
uint32_t reserved;
#endif
const uint8_t * ivarLayout;
const char * name;
method_list_t * baseMethodList;
protocol_list_t * baseProtocols;
const ivar_list_t * ivars;
const uint8_t * weakIvarLayout;
property_list_t *baseProperties;
method_list_t *baseMethods() const {
return baseMethodList;
}
};

上述源码中可以看到class_ro_t *ro是只读的,内部直接存储的method_list_t,protocol_list_t,property_list_t类型的一堆数组,数组里面分别存放的是类的初始化信息,以method_list_t为例,method_list_t中直接存放的就是method_t,但是是只读的,不允许增加删除修改操作。

总结

1.以方法列表为例,class_rw_t中的methods是二维数组的结构,并且可读可写,因此可以动态添加方法,并且更加便于分类方法的添加。因为在我们在前面的总结《iOS底层原理总结 – 探寻Category的本质》中提到过,attachList函数内通过memmovememcpy两个操作将分类的方法列表合并到本类的方法列表中,那么此时就将分类的方法和本类的方法统一整合到一起了。

2.其实一开始类的方法,属性,成员变量,协议等信息都放在class_ro_t中,当程序运行的时候,需要将分类中的列表跟类初始化的列表和听到一起时,就会将class_ro_t中的列表和分类中的列表合并起来存放到class_rw_t中,也就是说class_rw_t中有部分列表是从class_ro_t里面拿出来的,并且最终和分类的方法合并,详情看下面的realizeClass源码

static Class realizeClass(Class cls)
{
runtimeLock.assertWriting();
const class_ro_t *ro;
class_rw_t *rw;
Class supercls;
Class metacls;
bool isMeta;
if (!cls) return nil;
if (cls->isRealized()) return cls;
assert(cls == remapClass(cls));
// 最开始cls->data是指向ro的
ro = (const class_ro_t *)cls->data();
if (ro->flags & RO_FUTURE) {
// rw已经初始化并且分配内存空间
rw = cls->data();  // cls->data指向rw
ro = cls->data()->ro;  // cls->data()->ro指向ro
cls->changeInfo(RW_REALIZED|RW_REALIZING, RW_FUTURE);
} else {
// 如果rw并不存在,则为rw分配空间
rw = (class_rw_t *)calloc(sizeof(class_rw_t), 1); // 分配空间
rw->ro = ro;  // rw->ro重新指向ro
rw->flags = RW_REALIZED|RW_REALIZING;
// 将rw传入setData函数,等于cls->data()重新指向rw
cls->setData(rw);
}
}

3解释一下上面的源码,类的初始化信息本来其实是存储在class_ro_t中的,并且ro本来是指向cls->data()的,也就是说bits.data()得到的是ro,但是在运行过程中创建了class_rw_t,并将cls->data指向rw,同时将初始化信息ro赋值给rw中的ro,最后在通过setData(rw)设置data,那么此时bits.data()得到的就是rw,之后再去检查是否有分类,同时将分类的方法,属性,协议列表整合存储在class_rw_t的方法,属性,以及协议列表中。

我们通过对源码的分析,对class_rw_t 中存储的方法,属性,协议列表有了更清楚的认识,接下来探寻class_rw_t是如何存储方法的。

二.class_rw_t存储数据

1. method_t
我们还是以method_array_t为例,method_array_t中存储的是method_list_t, method_list_t 中最终存储的是method_tmethod_t是对方法,函数的封装,可以理解为每一个方法对应一个method_t
我们看一下method_t的结构体

struct method_t {
SEL name;  // 函数名
const char *types;  // 编码(返回值类型,参数类型)
IMP imp; // 指向函数的指针(函数地址)
};

method_t结构体中可以看到有三个成员变量,分别看一下意思

2.SEL
SEL代表方法/函数名,一般叫做选择器,底层结构跟char *类似。
typedef struct objc_selector *SEL,可以把SEL看作是方法名字符串。
SEL可以通过@selector() 或者sel_registerName()(Runtime 方法)获得。

SEL sel1 = @selector(test);
SEL sel2 = sel_registerName("test");

也可以通过sel_getName()NSStringFromSelector()将SEL转成字符串。

char *string = sel_getName(sel1);
NSString *string2 = NSStringFromSelector(sel2);

不同类中相同名字的方法,所对应的方法选择器是相同的。

NSLog(@"%p,%p", sel1,sel2);
Runtime-test[23738:8888825] 0x1017718a3,0x1017718a3

SEL仅仅代表方法的名字,不同类中相同的方法名SEL是全局唯一的。

3.types
types包含了函数返回值,参数编码的字符串,通过字符串拼接的方式将返回值和参数拼接成一个字符串,来代表函数返回值及参数。
我们可以经常看到types的值为v16@0:8,这个值代表什么意思呢?为了更能清楚表示方法返回值,参数,Apple制定了type encoding 编码规则

OC type encodings.png

那对照上面的表查看typesv16@0:8表示什么呢?

- (void) test;
v    16      @     0     :     8
void          id          SEL
// 16表示参数的占用空间大小,id后面跟的0表示从0位开始存储,id占8位空间。
// SEL后面的8表示从第8位开始存储,SEL同样占8位空间

我们知道任何方法默认都有两个参数,id类型的self, SEL类型的_cmd,而上述的例子也证明了这一点,我们再来看一个例子

- (int)testWithAge:(int)age Height:(float)height
{
return 0;
}
i    24    @    0    :    8    i    16    f    20
int           id        SEL       int        float
// 参数的总占用空间为 8 + 8 + 4 + 4 = 24
// id 从第0位开始占据8位空间
// SEL 从第8位开始占据8位空间
// int 从第16位开始占据4位空间
// float 从第20位开始占据4位空间

iOS提供了@endcode的指令,可以将具体的类型转化成字符串编码。

NSLog(@"%s",@encode(int));
NSLog(@"%s",@encode(float));
NSLog(@"%s",@encode(id));
NSLog(@"%s",@encode(SEL));
// 打印内容
Runtime-test[25275:9144176] i
Runtime-test[25275:9144176] f
Runtime-test[25275:9144176] @
Runtime-test[25275:9144176] :

上述代码中可以看出,对应关系确实如上表所示。

4.IMP
IMP代表函数的具体的实现,存储的内存是函数的地址,也就是说当找到IMP的时候就可以找到函数实现,进而对函数进行调用。

在上述代码中打印IMP的值

Printing description of data->methods->first.imp:
(IMP) imp = 0x000000010c66a4a0 (Runtime-test`-[Person testWithAge:Height:] at Person.m:13)

之后在test方法内部打印断点,并来到其方法内部可以看出IMP内部存储的地址也就是方法实现的地址。

test方法内部.png

通过上面的学习我们知道了方法列表是存储在类对象中的,但是当多次继承的子类想要调用基类方法时,就需要通过superclass指针一层一层找到基类,就从基类方法列表中找到对应的方法进行调用,如果多次调用基类方法,那么就需要多次遍历每一层父类的方法列表,这对性能来说无疑是伤害巨大的。

Apple通过方法缓存的形式解决了这一问题,接下来我们探寻一下Class类对象 是如何进行方法缓存的。

四.方法缓存 cache_t

回到类对象结构体,成员变量cache 就是用来对方法进行缓存的。

struct objc_class : objc_object {
// Class ISA;
Class superclass;
cache_t cache;             // formerly cache pointer and vtable
class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
class_rw_t *data() {
return bits.data();
}
void setData(class_rw_t *newData) {
bits.setData(newData);
}
}

cache_t cache:用于缓存曾经调用过的方法,可以提高方法的查找速度。

那么此时调用方法逻辑就会变成,以实例方法为例,先去类对象的cache中查找是否有缓存方法,如果没有的话,再去类对象的方法列表中查找,以此类推直接到找到方法之后,就会将方法直接存储在cache中,下一次在调用这个方法的时候,就会在类对象的cache里面找到这个方法,直接调用即可。

1.cache_t 如何进行缓存
那么cache_t是如何对方法进行缓存的呢?首先来看一下cache_t的内部结构。

struct cache_t {
struct bucket_t *_buckets; // 散列表 数组
mask_t _mask; // 散列表的长度 -1
mask_t _occupied; // 已经缓存的方法数量
};

bucket_t是以数组的方法存储方法列表的,看一下bucket_t内部结构。

struct bucket_t {
private:
cache_key_t _key; // SEL作为Key
IMP _imp; // 函数的内存地址
};

从源码中可以看出bucket_t中存储着_key_imp,其中_key代表SEL,通过key->value的形式,以SEL_key函数实现的内存地址_impvalue来存储方法。

通过一张图来展示一下cache_t的结构

cache_t的结构.png

上述的bucket_t列表我们称之为散列表(哈希表)

普及一下哈希表知识点:

  • 1.散列表概念

散列表(Hash table)也叫哈希表,是根据键值(Key-Value)而直接进行访问的数据结构,也就是说,它通过把键值映射到表中的一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

  • 2.散列函数及散列表原理
    我们结合Apple看一下散列函数的原理是什么,首先来看一下存储的源码,主要查看几个函数,关键代码都有注释。
    cache_fill 及 cache_fill_nolock 函数
void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
#if !DEBUG_TASK_THREADS
mutex_locker_t lock(cacheUpdateLock);
cache_fill_nolock(cls, sel, imp, receiver);
#else
_collecting_in_critical();
return;
#endif
}
static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
cacheUpdateLock.assertLocked();
// 如果没有initialize直接return
if (!cls->isInitialized()) return;
// 确保线程安全,没有其他线程添加缓存
if (cache_getImp(cls, sel)) return;
// 通过类对象获取到cache
cache_t *cache = getCache(cls);
// 将SEL包装成Key
cache_key_t key = getKey(sel);
// 占用空间+1
mask_t newOccupied = cache->occupied() + 1;
// 获取缓存列表的缓存能力,能存储多少个键值对
mask_t capacity = cache->capacity();
if (cache->isConstantEmptyCache()) {
// 如果为空的,则创建空间,这里创建的空间为4个。
cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
}
else if (newOccupied <= capacity / 4 * 3) {
// 如果所占用的空间占总数的3/4一下,则继续使用现在的空间
}
else {
// 如果占用空间超过3/4则扩展空间
cache->expand();
}
// 通过key查找合适的存储空间。
bucket_t *bucket = cache->find(key, receiver);
// 如果key==0则说明之前未存储过这个key,占用空间+1
if (bucket->key() == 0) cache->incrementOccupied();
// 存储key,imp
bucket->set(key, imp);
}

reallocate 函数
通过上述源码看到reallocate函数负责分配散列空间,来到reallocate函数内部,

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
// 旧的散列表能否被释放
bool freeOld = canBeFreed();
// 获取旧的散列表
bucket_t *oldBuckets = buckets();
// 通过新的空间需求量创建新的散列表
bucket_t *newBuckets = allocateBuckets(newCapacity);
assert(newCapacity > 0);
assert((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
// 设置Buckets和Mash,Mask的值为散列表长度-1
setBucketsAndMask(newBuckets, newCapacity - 1);
// 释放旧的散列表
if (freeOld) {
cache_collect_free(oldBuckets, oldCapacity);
cache_collect(false);
}
}

上述源码中首次传入reallocate函数的newCapacityINIT_CACHE_SIZE,INIT_CACHE_SIZE是个枚举值,也就是4。因此三列表最初创建的空间就是4个。

enum {
INIT_CACHE_SIZE_LOG2 = 2,
INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2)
};

expand ()函数
当散列表的空间被占用超过3/4的时候,散列表会调用expand ()函数进行扩展,我们来看一下expand ()函数内部散列表如何进行扩展的。

void cache_t::expand()
{
cacheUpdateLock.assertLocked();
// 获取旧的散列表的存储空间
uint32_t oldCapacity = capacity();
// 将旧的散列表存储空间扩容至两倍
uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;
// 为新的存储空间赋值
if ((uint32_t)(mask_t)newCapacity != newCapacity) {
newCapacity = oldCapacity;
}
// 调用reallocate函数,重新创建存储空间
reallocate(oldCapacity, newCapacity);
}

上述源码中可以发现散列表进行扩容时会将容量增至之前的2倍。

find 函数
最后来看一下散列表中如何快速的通过key找到相应的bucket呢?我们来到find函数内部

bucket_t * cache_t::find(cache_key_t k, id receiver)
{
assert(k != 0);
// 获取散列表
bucket_t *b = buckets();
// 获取mask
mask_t m = mask();
// 通过key找到key在散列表中存储的下标
mask_t begin = cache_hash(k, m);
// 将下标赋值给i
mask_t i = begin;
// 如果下标i中存储的bucket的key==0说明当前没有存储相应的key,将b[i]返回出去进行存储
// 如果下标i中存储的bucket的key==k,说明当前空间内已经存储了相应key,将b[i]返回出去进行存储
do {
if (b[i].key() == 0  ||  b[i].key() == k) {
// 如果满足条件则直接reutrn出去
return &b[i];
}
// 如果走到这里说明上面不满足,那么会往前移动一个空间重新进行判定,知道可以成功return为止
} while ((i = cache_next(i, m)) != begin);
// hack
Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
cache_t::bad_cache(receiver, (SEL)k, cls);
}

函数cache_hash (k, m)用来通过key找到方法在散列表中存储的下标,来到cache_hash (k, m)函数内部

static inline mask_t cache_hash(cache_key_t key, mask_t mask)
{
return (mask_t)(key & mask);
}

可以发现cache_hash (k, m)函数内部仅仅是进行了key & mask的按位与运算,得到下标即存储在相应的位置上。按位与运算在《iOS底层原理总结 – 探寻Runtime本质(一)》中讲过,可以回看。

_mask
通过上面的分析我们知道_mask的值是散列表的长度减一,那么任何数通过与_mask进行按位与元算之后获得的值都会小于等于_mask,因此不会出现数组溢出的情况。
举个例子,假设散列表的长度为8,那么mask的值为7。

  0101 1011  // 任意值
& 0000 0111  // mask = 7
------------
0000 0011 //获取的值始终等于或小于mask的值

总结

1.当第一次使用方法的时候,消息机制通过isa找到方法之后,会对方法以SEL为key,IMP为value的方式缓存在cache_buckets中,当第一次存储的时候,会创建具有4个空间的散列表,并将_mask的值置为散列表的长度减一,之后通过SEL & mask计算出方法存储的下标值,并将方法存储在散列表中。举个例子,如果计算出下标值为3,那么就将方法直接存储在下标为3的空间中,前面的空间会留空。

2.当散列表中存储的方法占据散列表长度超过3/4的时候,散列表会进行扩容操作,将创建一个新的散列并且空间扩容至原来空间的2倍,并重置_mask的值,最后释放旧的散列表,此时再有方法要进行缓存的话,就需要重新通过SEL & mask计算出下标值之后再按照下标进行存储了。

3.如果一个类中方法很多,其中很可能会出现多个方法的SEL & mask得到的值为同一个下标值,那么会调用cache_next函数往下标值为-1位去进行存储,如果下标值为-1位空间有存储方法,并且key不与要存储的key相同,那么再到前面一位进行比较,直到找到一位空间没有存储方法或者key与要存储的key相同为止,如果到下标0的话就会到下标为_mask的空间也就是最大空间处进行比较。

4.当要查找方法时,并不需要遍历散列表,同样通过SEL & mask计算出下标值,直接去下标值的空间取值即可,同上,如果下标值中存储的key与要查找的key不相同,就去前面一位查找,这样虽然占用了少量空间,但是大大节省了时间,也就是说其实Apple是使用了空间换去了存取的时间。

通过一张图更能清楚的了解其中的流程。

 

散列表内部存取逻辑.png

代码验证上述流程
我们通过代码验证缓存问题,我们创建Person类继承NSObjectStudent类继承Person类,CollegeStudent类继承Student类,三个类分别有personTeststudentTestcolleaeStudentTest方法。

int main(int argc, const char * argv[]) {
@autoreleasepool {
CollegeStudent *collegeStudent = [[CollegeStudent alloc] init];
objc_class *collegeStudentClass = (__bridge objc_class *)[CollegeStudent class];
cache_t cache = collegeStudentClass->cache;
bucket_t *buckets = cache._buckets;
[collegeStudent personTest];
[collegeStudent studentTest];
NSLog(@"----------------------------");
for (int i = 0; i <= cache._mask; i++) {
bucket_t bucket = buckets[i];
NSLog(@"%s %p", bucket._key, bucket._imp);
}
NSLog(@"----------------------------");
[collegeStudent colleaeStudentTest];
cache = collegeStudentClass->cache;
buckets = cache._buckets;
NSLog(@"----------------------------");
for (int i = 0; i <= cache._mask; i++) {
bucket_t bucket = buckets[i];
NSLog(@"%s %p", bucket._key, bucket._imp);
}
NSLog(@"----------------------------");
NSLog(@"%p",@selector(colleaeStudentTest));
NSLog(@"----------------------------");
}
return 0;
}

我们分别在collegeStudent实例对象调用personTeststudentTestcolleaeStudentTest方法处打断点查看cache的变化。
personTest方法调用之前

personTest方法调用之前.png

从上图中可以看出,personTest方法调用之前,cache中仅仅存储了init方法,上图中可以看出init方法恰好存储在下标为0的位置,因此我们可以看到,_mask的值为3验证我们上述源码中提到的散列表第一次存储时会分配4个内存空间,_occupied的值为1证明此时_buckets中仅仅存储了一个方法。
当collegeStudent在调用personTest的时候,首先发现collegeStudent类对象的cache中没有personTest方法,就会去collegeStudent类对象的方法列表中查找,方法列表中也没有,那么就通过superclass指针找到Student类对象,Student类对象中的cache和方法列表同样没有,在通过superclass指针找到Person类对象,最终在Person类对象方法列表中找到之后进行调用,并缓存在collegeStudent类对象的cache中。
执行personTest方法之后查看cache方法的变化

 

personTest方法调用之后.png

上图中可以发现_occupied的值为2,说明此时personTest方法已经被缓存在collegeStudent类对象的cache中了。

同理执行过studentTest方法之后,我们通过打印查看一下此时cache内存储的信息。

 

cache内存储的信息.png

上图中可以看到cache中确实存储了init 、personTest 、studentTest三个方法。
那么执行过colleaeStudentTest方法之后此时cache中应该对colleaeStudentTest方法进行缓存。上面源码提到过,当存储的方法数超过散列表长度的3/4时,系统会重新创建一个容量为原来1倍的新的散列列表替代原来的散列表。过掉colleaeStudentTest方法,重新打印cache内存储的方法查看。

 

_bucket列表扩容之后.png

可以看出上图中_bucket

《iOS底层原理总结 – 探寻block本质(一)》
《iOS底层原理总结 – 探寻block本质(二)》
《iOS底层原理总结 – 探寻Runtime本质(三)》
《iOS底层原理总结 – 探寻Runtime本质(四)》

人已赞赏
iOS文章

iOS底层原理总结 - 探寻Runtime本质(三)

2020-5-11 3:18:13

iOS文章

iOS底层原理总结 - 探寻Runtime本质(一)

2020-5-11 4:33:40

个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
有新消息 消息中心
搜索