方法缓存的查找和cache的读写操作
在苹果提供的oc底层源码中，可以看到类的结构，isa是指向类和原类，superclass指向父类，bits存储方法和属性，cache是缓存,那么oc的方法是如何查找和缓存的呢
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的结构，这应该是一个bucket_t的结构体数组，mask是总数量，_occupied是已使用的数量。理论上来说，为了实现快速查找，这个bucket应该是指向一个哈希表。
struct cache_t {
struct bucket_t *_buckets;
mask_t _mask;
mask_t _occupied;
public:
struct bucket_t *buckets();
mask_t mask();
mask_t occupied();
...
}
bucket_t的结构，就是一个key和一个imp，估计key是sel相关的东西
struct bucket_t {
private:
// IMP-first is better for arm64e ptrauth and no worse for arm64.
// SEL-first is better for armv7* and i386 and x86_64.
#if __arm64__
MethodCacheIMP _imp;
cache_key_t _key;
#else
cache_key_t _key;
MethodCacheIMP _imp;
#endif
回到cache_t这个结构体，有两个成员函数mask()和occupied()，这两个应该只有在表的长度变化和表中内容的填充数量变化时才会调用，那么全局搜索，发现只有在两个函数中调用了occupied()方法
static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
这个是方法写入缓存时调用
void cache_erase_nolock(Class cls)
这个是释放掉oldBuckets，但是在这段代码中没有把以前cache的数据保留下来，直接丢弃，然后开一个新的空bucket
void cache_erase_nolock(Class cls)
{
cacheUpdateLock.assertLocked();
cache_t *cache = getCache(cls);//拿到当前类的cache
mask_t capacity = cache->capacity(); // capacity函数(mask() ? mask()+1 : 0;)mask存在就加1
if (capacity > 0 && cache->occupied() > 0) {
auto oldBuckets = cache->buckets();
auto buckets = emptyBucketsForCapacity(capacity);//创建新的首个bucket
cache->setBucketsAndMask(buckets, capacity - 1); // also clears occupied
cache_collect_free(oldBuckets, capacity);
cache_collect(false);
}
}
继续，从cache_fill_nolock（）入手，全局查找
在这个函数中，先在对应cls的缓存中查找sel，找不到就将cache中的occupied加1，然后判断
如果cache是空的，先reallocate来初始化，初始大小是4（这个方法也被用来更新bucket，释放旧的，生成新的）
如果cache里的occupied超过了四分之三，就调用expand来扩容，大小为mask+1的两倍
这里会放掉旧的bucket，然后把本次查询的方法加入新的bucket表，哈希表的扩容操作。
注意，最下面 cache->find 这个函数是变量了buckets这个hash表来查找，从key往后找，这应该是由于hash表解决冲突采用的是开放定址法，即发生冲突会向后找到空余的位置存入
cache_getImp查询函数实现是汇编。。。。
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_fill有两个地方
一 IMP lookupMethodInClassAndLoadCache(Class cls, SEL sel)
该函数会由object_cxxConstructFromClass调用，根据前面用lldb打印的方法时的输出来看（打印类的方法时也会存在一个cxx的方法），该方法可能是类的相关cxx构造方法，自动给你添加到类里面的，估计在初始化时会调用。
id
objc_constructInstance(Class cls, void *bytes)
{
if (!cls || !bytes) return nil;
id obj = (id)bytes;
// Read class's info bits all at once for performance
bool hasCxxCtor = cls->hasCxxCtor();
bool hasCxxDtor = cls->hasCxxDtor();
bool fast = cls->canAllocNonpointer();
if (fast) {
obj->initInstanceIsa(cls, hasCxxDtor);
} else {
obj->initIsa(cls);
}
if (hasCxxCtor) {
return object_cxxConstructFromClass(obj, cls);
} else {
return obj;
}
}
这个函数在初始化时调用，不符合探索的目标，看下一个
二 IMP lookUpImpOrForward(Class cls, SEL sel, id inst, bool initialize, bool cache, bool resolver)
该函数主要实现了方法的查询
首先如果可以找缓存，先找缓存，然后加锁
确认是否realizeClass和是否初始化，是才能继续，不是就realize或者初始化，然后继续
先找缓存，没有就在类（cls）的方法存储里面找，找到加入缓存
自己的方法没有，就循环找父类（根父类的父类是nil），找到了就返回imp
找不到就再找一次，还是找不到，就走转发_objc_msgForward_impcache（是个汇编），还进行了缓存
不管有没有找到方法，都会调用cache_fill来缓存，没有找到就缓存_objc_msgForward_impcache并且返回的IMP也是这个
不过每次如果没有在缓存里找到方法都会在类和父类里面找，而且判断找到的是不是_objc_msgForward_impcache，所以用runtime添加的方法是有效的，前提是添加之前程序没崩
IMP lookUpImpOrForward(Class cls, SEL sel, id inst,
bool initialize, bool cache, bool resolver)
{
IMP imp = nil;
bool triedResolver = NO;
runtimeLock.assertUnlocked();
if (cache) {
imp = cache_getImp(cls, sel);
if (imp) return imp;
}
runtimeLock.lock();
checkIsKnownClass(cls);
if (!cls->isRealized()) {
realizeClass(cls);
}
if (initialize && !cls->isInitialized()) {
runtimeLock.unlock();
_class_initialize (_class_getNonMetaClass(cls, inst));
runtimeLock.lock();
}
retry:
runtimeLock.assertLocked();
imp = cache_getImp(cls, sel);
if (imp) goto done;
{
Method meth = getMethodNoSuper_nolock(cls, sel);
if (meth) {
log_and_fill_cache(cls, meth->imp, sel, inst, cls);
imp = meth->imp;
goto done;
}
}
{
unsigned attempts = unreasonableClassCount();
for (Class curClass = cls->superclass;
curClass != nil;
curClass = curClass->superclass)
{
if (--attempts == 0) {
_objc_fatal("Memory corruption in class list.");
}
// Superclass cache.
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;
}
else {
break;
}
}
Method meth = getMethodNoSuper_nolock(curClass, sel);
if (meth) {
log_and_fill_cache(cls, meth->imp, sel, inst, curClass);
imp = meth->imp;
goto done;
}
}
}
if (resolver && !triedResolver) {
runtimeLock.unlock();
_class_resolveMethod(cls, sel, inst);
runtimeLock.lock();
triedResolver = YES;
goto retry;
}
imp = (IMP)_objc_msgForward_impcache;
cache_fill(cls, sel, imp, inst);
done:
runtimeLock.unlock();
return imp;
}
这里有一个问题，原类里的静态方法怎么找的？
在这段函数里面没看到在原类里查询方法，那么可能在调用这个函数的时候，cls就已经是原类了，同理，查询实例方法时，cls应该就是类了。
仔细查看函数的实现后有了新发现
在首次lookUpImpOrForward方法中查询cls及其父类方法未果后，会调用_class_resolveMethod这个方法，这个方法看不懂，它查询方法是查询的SEL_resolveInstanceMethod这个全局变量，那么可能就是，这个变量保存了需要查询的sel，但我没找到赋值在哪里。
该方法只会缓存函数，不直接返回IMP，说明等待第二次调用在缓存里查询
对于调用lookUpImpOrNil函数注意最后一个参数，如果是no，就不走二次查询，就不会导致死循环，但是感觉对于类方法调用查询和缓存的次数比较多，有点多余了。
void _class_resolveMethod(Class cls, SEL sel, id inst)
{
if (! cls->isMetaClass()) {
// try [cls resolveInstanceMethod:sel]
_class_resolveInstanceMethod(cls, sel, inst);//cls不是原类
}
else {
// try [nonMetaClass resolveClassMethod:sel] //cls是原类
// and [cls resolveInstanceMethod:sel]
_class_resolveClassMethod(cls, sel, inst);
if (!lookUpImpOrNil(cls, sel, inst,
NO/*initialize*/, YES/*cache*/, NO/*resolver*/))
{
_class_resolveInstanceMethod(cls, sel, inst);
}
}
}
调用这个函数lookUpImpOrForward（）的有两个地方
这个直接走到汇编里面去了
IMP _class_lookupMethodAndLoadCache3(id obj, SEL sel, Class cls)
{
return lookUpImpOrForward(cls, sel, obj,
YES/*initialize*/, NO/*cache*/, YES/*resolver*/);
}
这个是查询失败过，再找一次还是找不到方法，直接返回nil，注意这个最后一个参数是false，不会导致循环，只查cls及其父类
IMP lookUpImpOrNil(Class cls, SEL sel, id inst,
bool initialize, bool cache, bool resolver)
{
IMP imp = lookUpImpOrForward(cls, sel, inst, initialize, cache, resolver);
if (imp == _objc_msgForward_impcache) return nil;
else return imp;
}
其他调用lookUpImpOrNil的地方就4个，都和方法查找流程没什么关系
bool class_respondsToSelector_inst(Class cls, SEL sel, id inst) #// 被+/- respondsToSelector和instancesRespondToSelector调用，查询方法是否可用
IMP class_getMethodImplementation(Class cls, SEL sel) #// 只有一个地方objc_loadWeakRetained这里是查询是否有SEL_retainWeakReference，其他都是获取方法
static bool classHasTrivialInitialize(Class cls) #//查询有没有SEL_initialize这个方法，可能是初始化时检查
Method class_getInstanceMethod(Class cls, SEL sel) #// 同样也是获取方法，没看出获取类方法和对象方法有什么区别，可能是参数cls不同
（晚点加一个方法查找的流程图）
看了苹果的源码，感觉就两个特点，复用多，封装多，还有看不明白的多
