Runtime系列文章
Runtime原理探究(一)—— isa的深入体会(苹果对isa的优化)
Runtime原理探究(二)—— Class结构的深入分析
Runtime原理探究(三)—— OC Class的方法缓存cache_t
Runtime原理探究(四)—— 刨根问底消息机制
Runtime原理探究(五)—— super的本质
[Runtime原理探究(六)—— Runtime的应用...待续]-()
[Runtime原理探究(七)—— Runtime的API...待续]-()
Runtime原理探究(八)—— 面试题中的Runtime
☕️☕️本文篇幅比较长,创作的目的并不是为了在简书上刷赞和阅读量,而是为了自己日后温习知识所用。如果有幸被你发现这篇文章,并且引起了你的阅读兴趣,请休息充分,静下心来,精力充足地开始阅读,希望这篇文章能对你有所帮助。如发现任何有误之处,肯请留言纠正,谢谢。☕️☕️
承接上一篇的内容,我们回过头去看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 用于获取具体的类信息
};
这里面还有一个cache_t cache
没有解读过,一起来看一看这个东西。看名字很好理解,就是缓存的意思,缓存什么呢?——缓存方法。
它的底层是通过散列表(哈希表)
的数据结构来实现的,用于缓存曾经调用过的方法,可以提高方法的查找速度。
首先,回顾一下正常情况下方法调用的流程。假设我们调用一个实例方法[bj XXXX];
obj
->isa
->obj
的Class
对象 ->method_array_t methods
-> 对该表进行遍历查找,找到就调用,没找到继续往下走obj
->superclass
->obj
的父类 ->isa
->method_array_t methods
-> 对父类的方法列表进行遍历查找,找到就调用,没找到就重复本步骤- 找到就调用,没找到重复流程
- 找到就调用,没找到重复流程
- 找到就调用,没找到重复流程
- 直到
NSObject
->isa
->NSObject
的Class
对象 -> method_array_t methods ......
如果XXXX
方法在程序内会被频繁的调用,那么这种逐层便利查找的方式肯定是效率低下的,因此苹果设计了cache_t cache
,当XXXX
第一次被调用的时候,会按照常规流程查找,找到之后,就会被加入到cache_t cache
中,当再次被调用的时候,系统就会直接现到cache_t cache
来查找,找到就直接调用,这样便大大提升了查找的效率。
刚才介绍了cache_t cache
是通过散列表
来实现的,下面就来着重分析一下,方法是如何被缓存的。散列/哈希表,想必大部分iOS开发这至少应该听过,而我们常用的NSDictionary
其实就是一种散列表数据结构。来看一下cache_t cache
的定义
struct cache_t {
struct bucket_t *_buckets;
mask_t _mask;
mask_t _occupied;
}
-
struct bucket_t *_buckets;
—— 用来缓存方法的散列/哈希表 -
mask_t _mask;
—— 这个值 = 散列表长度 - 1 -
mask_t _occupied;
—— 表示已经缓存的方法的数量
上面介绍的_buckets
散列表里面的存储单元是bucket_t
,来看看它包含了方法的什么信息
struct bucket_t {
private:
cache_key_t _key;
IMP _imp;
}
-
cache_key_t _key;
—— 这个key实际上就是方法的SEL,也就是方法名 -
IMP _imp;
—— 这个就是方法对应的函数的内存地址
想一想我们平时是怎么使用NSDictionary的,通过一堆Key-Value键值对来进行存储的,NSDictionary的底层就是散列表,这个刚才说过。方法缓存的时候,key就是上面的cache_key_t _key;
,value就是上面的bucket_t
结构体对象。
但是散列表的运作原理到底如何呢,这个属于数据结构问题,这里简要介绍一下。首先散列表本质上就是一个数组
key
计算出一个index,然后再将元素插入散列表的index位置那么从散列表里面取值就显而易见了,根据一个key,计算出index,然后到散列表对应位置将值取出
这里的查询方法的时候(也就是取值操作),时间复杂度为O(1), 对比我们一开始从方法列表的遍历查询,它的时间复杂度为O(n),因此通过缓存方法,可以极大的提高方法查询的效率,从而提高了方法调用机制的效率。
根据key计算出index值的这个算法称作散列算法,这个算法可以由你自己设计,总之目的就是尽可能减少不同的key得出相同index的情况出现,这种情况被称作哈希碰撞,同时还要保证得出的index值在合理的范围。index越大,意味着对应的散列表的长度越长,这是需要占用实际物理空间的,而我们的内存是有限的。散列表是一种通过牺牲一定空间,来换取时间效率的设计思想。
我们通过key计算出的index大小是随机的,无顺序的,因此在方法缓存的过程中,插入的顺序也是无顺序的而且可以预见的是,散列表里面再实际使用中会有很多位置是空着的,比如散列表长度为16,最终值存储了10个方法,散列表长度为64,最终可能只会存储40个方法,有一部分空间终究是要被浪费的。但是却提高查找的效率。这既是所谓的空间换时间。
再介绍一下苹果这里所采用的散列算法,其实很简单,如下
index = @selector(XXXX) & mask
根据&运算的特点,可以得知最终index <= mask
,而mask
= 散列表长度 - 1,也就是说 0 <= index <= 散列表长度 - 1
,这实际上覆盖了散列表的索引范围。而刚刚我们还提到过一个问题——哈希碰撞,也就是不同的key得到相同的index,该怎么处理呢?我们看一下源码,在objc源码里面搜索cache_t,可以发现一个跟查找相关的方法
bucket_t * cache_t::find(cache_key_t k, id receiver) //根据key值 k 进行查找
{
assert(k != 0);
bucket_t *b = buckets();
mask_t m = mask();
mask_t begin = cache_hash(k, m); //通过cache_hash函数【begin = k & m】计算出key值 k 对应的 index值 begin,用来记录查询起始索引
mask_t i = begin; // begin 赋值给 i,用于切换索引
do {
if (b[i].key() == 0 || b[i].key() == k) {
//用这个i从散列表取值,如果取出来的bucket_t的 key = k,则查询成功,返回该bucket_t,
//如果key = 0,说明在索引i的位置上还没有缓存过方法,同样需要返回该bucket_t,用于中止缓存查询。
return &b[i];
}
} while ((i = cache_next(i, m)) != begin);
// 这一步其实相当于 i = i-1,回到上面do循环里面,相当于查找散列表上一个单元格里面的元素,再次进行key值 k的比较,
//当i=0时,也就i指向散列表最首个元素索引的时候重新将mask赋值给i,使其指向散列表最后一个元素,重新开始反向遍历散列表,
//其实就相当于绕圈,把散列表头尾连起来,不就是一个圈嘛,从begin值开始,递减索引值,当走过一圈之后,必然会重新回到begin值,
//如果此时还没有找到key对应的bucket_t,或者是空的bucket_t,则循环结束,说明查找失败,调用bad_cache方法。
// hack
Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
cache_t::bad_cache(receiver, (SEL)k, cls);
}
*********************************** cache_hash(k, m);
static inline mask_t cache_hash(cache_key_t key, mask_t mask)
{
return (mask_t)(key & mask);
}
*********************************** cache_next(i, m)
static inline mask_t cache_next(mask_t i, mask_t mask) {
// return (i-1) & mask; // 非arm64
return i ? i-1 : mask; // arm64
}
cache_t::find
函数还被源码里面的另一个函数调用过——cache_fill_nolock
,缓存填充(插入)操作,源码如下
static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
cacheUpdateLock.assertLocked();
// Never cache before +initialize is done
if (!cls->isInitialized()) return;
// Make sure the entry wasn't added to the cache by some other thread
// before we grabbed the cacheUpdateLock.
if (cache_getImp(cls, sel)) return;
cache_t *cache = getCache(cls);
cache_key_t key = getKey(sel);
// Use the cache as-is if it is less than 3/4 full
mask_t newOccupied = cache->occupied() + 1;
mask_t capacity = cache->capacity();
if (cache->isConstantEmptyCache()) {
// Cache is read-only. Replace it.
cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
}
else if (newOccupied <= capacity / 4 * 3) {
// Cache is less than 3/4 full. Use it as-is.
}
else {
// Cache is too full. Expand it.
cache->expand();
}
// Scan for the first unused slot and insert there.
// There is guaranteed to be an empty slot because the
// minimum size is 4 and we resized at 3/4 full.
bucket_t *bucket = cache->find(key, receiver);
if (bucket->key() == 0) cache->incrementOccupied();
bucket->set(key, imp);
}
上面源码的最后一段以及它的注释说明可以明白,当通过cache->find
返回的bucket->key() == 0
,就说明该位置上是空的,没有缓存过方法,是一个unused slot
(未使用的槽口),因此可以进行插入操作bucket->set(key, imp);
,也就是将方法缓存到这个位置上。
根据上面的分析,下面用图示来总结一下方法存入cache_t中,以及从cache_t中取方法的整体流程
向cache_t存入方法
从cache_t查询方法
你可能还会有一个疑问,如果不断的往缓存里添加方法,缓存满了怎么办?我们回到刚才看过的一段代码cache_fill_nolock
函数,直接用截图解读一下
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) {
// mask overflow - can't grow further
// fixme this wastes one bit of mask
newCapacity = oldCapacity;
}
reallocate(oldCapacity, newCapacity);
}
上面代码里面uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;
说的很明白,扩容就是将当前缓存容量* 2
,如果是首次调用这个函数,会使用一个初始容量值INIT_CACHE_SIZE
来设定缓存容量
enum {
INIT_CACHE_SIZE_LOG2 = 2,
INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2)
};
从INIT_CACHE_SIZE
的定义显示它的值是4,也就是说苹果给cache_t设定的初始容量是4。
你可能还会问,重置缓存之后,原来老缓存里面的内容还要不要呢,expand()
函数里面调用的最后一个函数是reallocate(oldCapacity, newCapacity);
,我们在进入它的源码看看
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
bool freeOld = canBeFreed();
bucket_t *oldBuckets = buckets();
bucket_t *newBuckets = allocateBuckets(newCapacity);
// Cache's old contents are not propagated.
// This is thought to save cache memory at the cost of extra cache fills.
// fixme re-measure this
assert(newCapacity > 0);
assert((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
setBucketsAndMask(newBuckets, newCapacity - 1);
if (freeOld) {
cache_collect_free(oldBuckets, oldCapacity);
cache_collect(false);
}
}
很明显,在最对旧的缓存空间进行了释放,但是条件是freeOld = true
,函数开头给出了freeOld
的由来,通过canBeFreed()
函数获得
bool cache_t::isConstantEmptyCache()
{
return
occupied() == 0 &&
buckets() == emptyBucketsForCapacity(capacity(), false);
}
bool cache_t::canBeFreed()
{
return !isConstantEmptyCache();
}
canBeFreed()
函数其实很简单,就是判断一下缓存是不是空的,如果空的,旧没必要释放空间了,如果原来的缓存不是空的,就直接释放掉,并且我们发现,扩容的操作里面,并没有对旧的缓存空间里面的内容进行复制保留,就是很粗暴的直接分配一块新的缓存空间,然后直接释放掉旧的缓存空间,这意味着,每次进行扩容操作之后,原来缓存过的方法就会全部丢失,而上面的cache_fill_nolock
函数里面,在进行完expand()
扩容操作之后,也仅仅是把当前处理的方法放到缓存空间里面,因此,扩容之前曾经被缓存过的方法,如果下次再次调用的话,有需要被重新缓存了。这里好好体会一下。
父类的方法被调用的时候,会如何缓存?
现在,我们知道,当对一个对象发送消息后,会通过对象的isa找到它的Class对象,在Class对象里面先从方法缓存cache_t查找该方法,没有的话再对Class对象的方法列表进行遍历查找,如果找到了方法,就进行缓存并且调用,那么这里肯定是将方法缓存到了该对象的Class对象的cache_t里面。
如果在当前Class对象里面没有找到该方法,那么会通过Class对象的superclass进入其父类的Class对象里面,同样,会先查找它的cache_t,如果没有找到方法,会对其方法列表进行遍历查找,问题就在这里,如果此时在方法列表里面找到了方法,进行缓存操作的时候,是会将方法存入当前父类的Class对象的cache_t里面呢,还是会存到接收消息的对象的Class对象的cache_t里面呢?
要搞清楚这个问题,首先可以看一下哪些地方调用了static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
函数,因为它的参数里面传入了一个Class cls
我们只需要搞清楚这个Class cls
到底是谁。
根据下图的操作进入上层调用函数cache_fill
用同样方法查看一下
cache_fill
的上层调用函数,如下图首先来看一下这个
log_and_cache()
lockUpImpOrForward()
函数调用的。
接下来我们在先看一下lookUpMethodInClassAndLoadCache()
函数
最后在来看一下剩下的那个 lookUpImpOrForward
函数,下面代码请看⚠️⚠️⚠️处标记的中文注解即可
/***********************************************************************
* lookUpImpOrForward.
* The standard IMP lookup.-------------------------------->⚠️⚠️⚠️标准的IMP查找流程
* initialize==NO tries to avoid +initialize (but sometimes fails)
* cache==NO skips optimistic unlocked lookup (but uses cache elsewhere)
* Most callers should use initialize==YES and cache==YES.
* inst is an instance of cls or a subclass thereof, or nil if none is known.
* If cls is an un-initialized metaclass then a non-nil inst is faster.
* May return _objc_msgForward_impcache. IMPs destined for external use
* must be converted to _objc_msgForward or _objc_msgForward_stret.
* If you don't want forwarding at all, use lookUpImpOrNil() instead.
**********************************************************************/
IMP lookUpImpOrForward(Class cls, SEL sel, id inst,
bool initialize, bool cache, bool resolver)
{
IMP imp = nil;
bool triedResolver = NO;
runtimeLock.assertUnlocked();
// Optimistic cache lookup
if (cache) {//------------------------------>⚠️⚠️⚠️查询当前Class对象的缓存,如果找到方法,就返回该方法
imp = cache_getImp(cls, sel);
if (imp) return imp;
}
// runtimeLock is held during isRealized and isInitialized checking
// to prevent races against concurrent realization.
// runtimeLock is held during method search to make
// method-lookup + cache-fill atomic with respect to method addition.
// Otherwise, a category could be added but ignored indefinitely because
// the cache was re-filled with the old value after the cache flush on
// behalf of the category.
runtimeLock.read();
if (!cls->isRealized()) {//------------------------------>⚠️⚠️⚠️当前Class如果没有被realized,就进行realize操作
// Drop the read-lock and acquire the write-lock.
// realizeClass() checks isRealized() again to prevent
// a race while the lock is down.
runtimeLock.unlockRead();
runtimeLock.write();
realizeClass(cls);
runtimeLock.unlockWrite();
runtimeLock.read();
}
if (initialize && !cls->isInitialized()) {//-------------->⚠️⚠️⚠️当前Class如果没有初始化,就进行初始化操作
runtimeLock.unlockRead();
_class_initialize (_class_getNonMetaClass(cls, inst));
runtimeLock.read();
// If sel == initialize, _class_initialize will send +initialize and
// then the messenger will send +initialize again after this
// procedure finishes. Of course, if this is not being called
// from the messenger then it won't happen. 2778172
}
retry:
runtimeLock.assertReading();
// Try this class's cache.//------------------------------>⚠️⚠️⚠️尝试从该Class对象的缓存中查找,如果找到,就跳到done处返回该方法
imp = cache_getImp(cls, sel);
if (imp) goto done;
// Try this class's method lists.//---------------->⚠️⚠️⚠️尝试从该Class对象的方法列表中查找,找到的话,就缓存到该Class的cache_t里面,并跳到done处返回该方法
{
Method meth = getMethodNoSuper_nolock(cls, sel);
if (meth) {
log_and_fill_cache(cls, meth->imp, sel, inst, cls);
imp = meth->imp;
goto done;
}
}
// Try superclass caches and method lists.------>⚠️⚠️⚠️进入当前Class对象的superclass对象
{
unsigned attempts = unreasonableClassCount();
for (Class curClass = cls->superclass;//------>⚠️⚠️⚠️该for循环每循环一次,就会进入上一层的superclass对象,进行循环内部方法查询流程
curClass != nil;
curClass = curClass->superclass)
{
// Halt if there is a cycle in the superclass chain.
if (--attempts == 0) {
_objc_fatal("Memory corruption in class list.");
}
// Superclass cache.------>⚠️⚠️⚠️在当前superclass对象的缓存进行查找
imp = cache_getImp(curClass, sel);
if (imp) {
if (imp != (IMP)_objc_msgForward_impcache) {
// Found the method in a superclass. Cache it in this class.
log_and_fill_cache(cls, imp, sel, inst, curClass);
goto done;//------>⚠️⚠️⚠️如果在当前superclass的缓存里找到了方法,就调用log_and_fill_cache进行方法缓存,注意这里传入的参数是cls,也就是将方法缓存到消息接受对象所对应的Class对象的cache_t中,然后跳到done处返回该方法
}
else {
// Found a forward:: entry in a superclass.
// Stop searching, but don't cache yet; call method
// resolver for this class first.
break;//---->⚠️⚠️⚠️如果缓存里找到的方法是_objc_msgForward_impcache,就跳出该轮循环,进入上一层的superclass,再次进行查找
}
}
// Superclass method list.---->⚠️⚠️⚠️如过画缓存里面没有找到方法,则对当前superclass的方法列表进行查找
Method meth = getMethodNoSuper_nolock(curClass, sel);
if (meth) {
//------>⚠️⚠️⚠️如果在当前superclass的方法列表里找到了方法,就调用log_and_fill_cache进行方法缓存,注意这里传入的参数是cls,也就是将方法缓存到消息接受对象所对应的Class对象的cache_t中,然后跳到done处返回该方法
log_and_fill_cache(cls, meth->imp, sel, inst, curClass);
imp = meth->imp;
goto done;
}
}
}
// No implementation found. Try method resolver once.//------>⚠️⚠️⚠️如果到基类还没有找到方法,就尝试进行方法解析
if (resolver && !triedResolver) {
runtimeLock.unlockRead();
_class_resolveMethod(cls, sel, inst);
runtimeLock.read();
// Don't cache the result; we don't hold the lock so it may have
// changed already. Re-do the search from scratch instead.
triedResolver = YES;
goto retry;
}
// No implementation found, and method resolver didn't help. //------>⚠️⚠️⚠️如果方法解析不成功,就进行消息转发
// Use forwarding.
imp = (IMP)_objc_msgForward_impcache;
cache_fill(cls, sel, imp, inst);
done:
runtimeLock.unlockRead();
return imp;
}
关于上面再方法列表查找的函数Method meth = getMethodNoSuper_nolock(cls, sel);
还需要说明一下,进入它的实现
static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
runtimeLock.assertLocked();
assert(cls->isRealized());
// fixme nil cls?
// fixme nil sel?
for (auto mlists = cls->data()->methods.beginLists(),
end = cls->data()->methods.endLists();
mlists != end;
++mlists)
{
method_t *m = search_method_list(*mlists, sel);//---⚠️⚠️⚠️核心函数
if (m) return m;
}
return nil;
}
再进入其核心函数search_method_list(*mlists, sel)
static method_t *search_method_list(const method_list_t *mlist, SEL sel)
{
int methodListIsFixedUp = mlist->isFixedUp();
int methodListHasExpectedSize = mlist->entsize() == sizeof(method_t);
if (__builtin_expect(methodListIsFixedUp && methodListHasExpectedSize, 1)) {
//---⚠️⚠️⚠️如果方法列表是经过排序的,则进行二分查找
return findMethodInSortedMethodList(sel, mlist);
} else {
// Linear search of unsorted method list
//---⚠️⚠️⚠️如果方法列表没有进行排序,则进行线性遍历查找
for (auto& meth : *mlist) {
if (meth.name == sel) return &meth;
}
}
#if DEBUG
// sanity-check negative results
if (mlist->isFixedUp()) {
for (auto& meth : *mlist) {
if (meth.name == sel) {
_objc_fatal("linear search worked when binary search did not");
}
}
}
#endif
return nil;
}
}
根据代码中的逻辑,如果方法列表是经过排序的,会使用findMethodInSortedMethodList
进行查找,而这里面实际上是用二分法进行查找的,具体代码如下
static method_t *findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
assert(list);
const method_t * const first = &list->first;
const method_t *base = first;
const method_t *probe;
uintptr_t keyValue = (uintptr_t)key;
uint32_t count;
//---⚠️⚠️⚠️count >>= 1相当于 count/=2,说明是从数组中间开始查找,也就是二分查找发
for (count = list->count; count != 0; count >>= 1) {
probe = base + (count >> 1);
uintptr_t probeValue = (uintptr_t)probe->name;
if (keyValue == probeValue) {
// `probe` is a match.
// Rewind looking for the *first* occurrence of this value.
// This is required for correct category overrides.
while (probe > first && keyValue == (uintptr_t)probe[-1].name) {
probe--;
}
return (method_t *)probe;
}
if (keyValue > probeValue) {
base = probe + 1;
count--;
}
}
return nil;
}
经过上述解读,我们已经基本了解方法查询和方法缓存所涉及到的细节,现在可以把方法查找和方法缓存流程结合起来描述一下 Runtime消息机制 当中的 消息发送 流程
- (1) 当一个对象接收到消息时
[obj message];
,首先根据obj
的isa
指针进入它的类对象cls
里面。- (2) 在
obj
的cls
里面,首先到缓存cache_t
里面查询方法message
的函数实现,如果找到,就直接调用该函数。- (3) 如果上一步没有找到对应函数,在对该
cls
的方法列表进行二分/遍历查找,如果找到了对应函数,首先会将该方法缓存到obj
的类对象cls
的cache_t
里面,然后对函数进行调用。- (4) 在每次进行缓存操作之前,首先需要检查缓存容量,如果缓存内的方法数量超过规定的临界值(
设定容量的3/4
),需要先对缓存进行2倍扩容,原先缓存过的方法全部丢弃,然后将当前方法存入扩容后的新缓存内。- (5) 如果在
obj
的cls
对象里面,发现缓存和方法列表都找不到mssage
方法,则通过cls
的superclass
指针进入它的父类对象f_cls
里面- (6) 进入
f_cls
后,首先在它的cache_t
里面查找mssage
,如果找到了该方法,那么会首先将方法缓存到消息接受者obj
的类对象cls
的cache_t
里面,然后调用方法对应的函数。- (7) 如果上一步没有找到方法,将会对
f_cls
的方法列表进行遍历二分/遍历查找,如果找到了mssage
方法,那么同样,会首先将方法缓存到消息接受者obj
的类对象cls
的cache_t
里面,然后调用方法对应的函数。需要注意的是,这里并不会将方法缓存到当前父类对象f_cls
的cache_t里面。- (8) 如果还没找到方法,则会通过
f_cls
的superclass
进入更上层的父类对象里面,按照(6)->(7)->(8)
步骤流程重复。如果此时已经到了基类对象NSObject
,仍没有找到mssage
,则进入步骤(9)
- (9) 接下来将会转到消息机制的 动态方法解析 阶段
至此,OC Runtime里面的消息发送流程
和方法缓存策略
就分析完毕。
Runtime系列文章
Runtime原理探究(一)—— isa的深入体会(苹果对isa的优化)
Runtime原理探究(二)—— Class结构的深入分析
Runtime原理探究(三)—— OC Class的方法缓存cache_t
Runtime原理探究(四)—— 刨根问底消息机制
Runtime原理探究(五)—— super的本质
[Runtime原理探究(六)—— Runtime的应用...待续]-()
[Runtime原理探究(七)—— Runtime的API...待续]-()
Runtime原理探究(八)—— 面试题中的Runtime