08-慢速查找流程

知识点

1: dirty memory : 脏内存, 支持增删改的内存区域
eg: rw结构体
2: clean memory : 干净内存, 只支持读的内存区域
eg: ro结构体

为什么这么设计呢?

苹果的内存优化操作, 防止干净内存(不经常修改的内存区域)受到污染, 比如方法列表, 如果苹果不区分两块儿区域的话, 意味着每次运行时动态添加的方法和分类里扩展的方法都会被写入进去, 那么就会导致objc_class整片区域的内存都要受到污染, 导致内存增大, 性能耗损. 但是区分开后, 我们只处理dirty memory中的methods列表就会是内存和性能得到很大的提升

详见: Runtime2020升级改版-更小, 更安全, 更高效

1: 慢速查询的进入方式

方法1: 汇编最终流程发现

MethodTableLookup-c856

这里跟lookUpImpOrForward方法实现中的这块代码相对应

// 这里是预防多线程有可能调用缓存方法的情况
// 需要注意behavior & LOOKUP_CACHE的结果
// behavior: cache查找完后会传3, &后为0, 会跳过cache快速查找
if (fastpath(behavior & LOOKUP_CACHE)) {
    imp = cache_getImp(cls, sel);
    if (imp) goto done_nolock;
}

方法2: 汇编

通过注释掉实现, 通过debug Workflow-> always show disassembly 查看汇编流程, objc_msgSend ->(ctrl + step info) _objc_msgSend_uncached -> lookUpImpOrForward

2: 解析`lookUpImpOrForward`方法

IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
    const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    IMP imp = nil;
    Class curClass;

    runtimeLock.assertUnlocked();
    // 1.
    // 这里是预防多线程有可能调用缓存方法的情况
    // 需要注意behavior & LOOKUP_CACHE的结果
    // behavior: cache查找完后会传3, &后为0, 跳过cache快速查找
    if (fastpath(behavior & LOOKUP_CACHE)) {
        imp = cache_getImp(cls, sel);
        if (imp) goto done_nolock;
    }
    // 加锁(保障线程安全)
    runtimeLock.lock();
    
    // 2. 是否是已注册验证的Class, 防止代码被恶意入侵, 注入
    checkIsKnownClass(cls);

    // 3. 检查是否进行了类初始化
    if (slowpath(!cls->isRealized())) {
        // 4. 内部进行了ro和rw等基础信息的分配, 以及cls作为一个双向链表的继承关系绑定操作
        cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
    }
    
    // 5. 检查是否完成类信息的初始化
    if (slowpath((behavior & LOOKUP_INITIALIZE) && !cls->isInitialized())) {
        // 6. 内部将递归初始化所有类并自动发送initialize方法
        // 根据需要将“ + initialize”消息发送给任何继承链上未初始化的类
        // ((void(*)(Class, SEL))objc_msgSend)(cls, @selector(initialize));
        cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
    }

    runtimeLock.assertLocked();
    curClass = cls;

    // 7. 这里的for是死循环, 因为没有设置循环结束条件
    for (unsigned attempts = unreasonableClassCount();;) {
        // 1. 先查找自己的method list里有没有, 而不查找父类的
        // 内部查找方法findMethodInSortedMethodList用到了二分查找算法, 提高查找效率, 详见注释
        Method meth = getMethodNoSuper_nolock(curClass, sel);
        if (meth) {//查到了则跳出循环完成
            imp = meth->imp;
            goto done;
        }
        
        // 2. curClass在这里会递归赋值为它的父类,直到继承关系的最终点nil时, 则会赋值imp为forward_imp
        if (slowpath((curClass = curClass->superclass) == nil)) {
            imp = forward_imp;
            // 3. 这里是for死循环的出口条件
            break;
        }

        // Halt if there is a cycle in the superclass chain.
        if (slowpath(--attempts == 0)) {
            _objc_fatal("Memory corruption in class list.");
        }

        // 4. Superclass cache.
        // 因为上面curClass会递归被赋值为它的父类, 所以这里查找到的是父类的缓存 -> 汇编快速查找cache
        // 注意: cache_getimp 快速查询时, 传入参数是`GETIMP`
        // 如果没找到, 最终jumpMiss返回的是`LGetImpMiss`, 即0x0
        imp = cache_getImp(curClass, sel);
        
        // 5. 当在父类找到的imp等于forward_imp时, 跳出循环
        if (slowpath(imp == forward_imp)) {
            // Found a forward:: entry in a superclass.
            // Stop searching, but don't cache yet; call method
            // resolver for this class first.
            break;
        }
        // 6. 如果cache_getImp找到了imp在这跳出循环完成
        if (fastpath(imp)) {
            // Found the method in a superclass. Cache it in this class.
            goto done;
        }
    }

    // 8. No implementation found. Try method resolver once.
    // 动态方法决议,
    // behavior & LOOKUP_RESOLVER)类似上面, 作用是只调用一次
    // 待验证: 通过这里实现消息转发的, 这里会只调用1次
    //        没有实现消息转发的, 则会调用2次
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        behavior ^= LOOKUP_RESOLVER;
        // 9. 动态方法决议
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

 done:
    // 10. 0将查找到的方法写入缓存, 避免下次调用还是慢速查找, 并形成一个闭环
    log_and_fill_cache(cls, imp, sel, inst, curClass);
    runtimeLock.unlock();
 done_nolock:
    if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
        return nil;
    }
    return imp;
}

1)重要流程2-4. cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);

OC准备Class基本信息01-c906

下面这个方法的实现, 是在慢速查找流程前的重点, 它准备了class信息中ro和rw等基础信息, 以及双向链表(父类, 元类, 子类)的处理, 确认传入对象的继承关系, 给后面递归其父类缓存方法的流程提供准备工作

static Class realizeClassWithoutSwift(Class cls, Class previously)

⬇️

// 双向链表, 确认继承关系
supercls = realizeClassWithoutSwift(remapClass(cls->superclass), nil);
metacls = realizeClassWithoutSwift(remapClass(cls->ISA()), nil);
⬇️    
cls->superclass = supercls;
cls->initClassIsa(metacls);
⬇️
// 将此类连接到其超类的子类列表
if (supercls) {
    addSubclass(supercls, cls);
} else {
    addRootClass(cls);
}

2)核心流程2-7-1 Method meth = getMethodNoSuper_nolock(curClass, sel);

查找主类或其分类的方法列表: 采用二分查找算法, 提高查询效率, 减少性能损耗

Method meth = getMethodNoSuper_nolock(curClass, sel);
⬇️
ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
    ASSERT(list);
    // list: 是个排完序, 并从小到大递增的方法列表.eg: 0, 1, 2,
    // &list->first: 取址, 并找到首元素
    const method_t * const first = &list->first;
    const method_t *base = first;
    const method_t *probe;
    // 要找的SEL, SEL被强转为uintptr_t, 用来比较大小
    uintptr_t keyValue = (uintptr_t)key;
    uint32_t count;
    
    // 1: 二分查找
    //count >>= 1 等价于count/2 16进制
    for (count = list->count; count != 0; count >>= 1) {
        //内存偏移(base指针地址偏移(count >> 1)个位置)
        probe = base + (count >> 1);
        
        uintptr_t probeValue = (uintptr_t)probe->name;
        
        if (keyValue == probeValue) {
            // 这个当sel相同时, 需要循环递减查找到它的分类的方法实现, 因为加载到内存时, 分类会加载在主类的前边
            // 也可以侧面验证分类可以重写并覆盖主类的方法的调用
            while (probe > first && keyValue == (uintptr_t)probe[-1].name) {
                probe--;
            }
            return (method_t *)probe;
        }
        
        if (keyValue > probeValue) {
            base = probe + 1;
            count--;
        }
    }
    /* * 举个栗子
     **运行流程举例1**: 编译断点走一走, 你懂我也懂
     list = [0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7 ,0x8];
     base = 0x1
     keyValue = 0x7;
     运行流程举例1: 编译断点走一走, 你懂我也懂
     1: count: 8;  count >> 1: 4;  probe = 0x5(0x1+4);
        1): keyValue > probeValue: true;
            base = 0x6 (probe + 1);  count: 7(count--)
        2): 进入下一次循环
     2: count: 7(--);  count >>= 1: 3;  probe = 0x6 + 1(3>>1): 0x7;
        命中返回.
    -----------------------------------------------------------------
    **运行流程举例2**: 编译断点走一走, 你懂我也懂
    list = [0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7 ,0x8];
    base = 0x1
    keyValue = 0x2;
    1: count: 8;  probe = 0x5(0x1+4(count>>1));
        1): keyValue > probeValue: false;
        2): 进入下一次循环: true
            base = 0x1;  count: 8 (都不变)
    2: count: 8;  count >>= 1: 4;  probe = 0x1 + 2(4>>1): 0x3;
        1): keyValue > probeValue: false;
        2): 进入下一次循环: true
            base = 0x1;  count: 4 (都不变)
    3: count: 4;  count >>= 1: 2;  probe = 0x1 + 1(4>>1): 0x2;
        命中返回
     **/
    
    return nil;
}

二分查找图示-c964

3)核心流程2-8和9. resolveMethod_locked(inst, sel, cls, behavior);

    // 动态方法决议,
    // behavior & LOOKUP_RESOLVER)类似上面, 作用是只调用一次
    // 待验证: 通过这里实现消息转发的, 这里会只调用1次
    //        没有实现消息转发的, 则会调用2次
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        behavior ^= LOOKUP_RESOLVER;
        // 动态方法决议
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

3. 慢速查找流程图

慢速查找流程图

08-慢速查找流程

知识点

1: 慢速查询的进入方式

2: 解析lookUpImpOrForward方法

1)重要流程2-4. cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);

2)核心流程2-7-1 Method meth = getMethodNoSuper_nolock(curClass, sel);

3)核心流程2-8和9. resolveMethod_locked(inst, sel, cls, behavior);

3. 慢速查找流程图

2: 解析`lookUpImpOrForward`方法