OC方法调用慢查找流程底层逻辑探究

发表于   |  

在OC方法调用快查找流程底层逻辑探究中,我们分析了方法调用快查找的逻辑，所谓的快查找也就是对方法缓存列表的查找，如果没有命中缓存，则会进入到慢查找的逻辑，即对类的方法列表的查找，下面我们就来探究下OC底层是如何进行慢查找的。

在快查找未命中的出口，有如下的代码逻辑:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
.macro JumpMiss
.if $0 == GETIMP
	b	LGetImpMiss
.elseif $0 == NORMAL
	b	__objc_msgSend_uncached
.elseif $0 == LOOKUP
	b	__objc_msgLookup_uncached
.else
.abort oops
.endif
.endmacro
STATIC_ENTRY __objc_msgSend_uncached
UNWIND __objc_msgSend_uncached, FrameWithNoSaves
// THIS IS NOT A CALLABLE C FUNCTION
// Out-of-band p16 is the class to search
	
MethodTableLookup
TailCallFunctionPointer x17
END_ENTRY __objc_msgSend_uncached
STATIC_ENTRY __objc_msgLookup_uncached
UNWIND __objc_msgLookup_uncached, FrameWithNoSaves
// THIS IS NOT A CALLABLE C FUNCTION
// Out-of-band p16 is the class to search
	
MethodTableLookup
ret
END_ENTRY __objc_msgLookup_uncached

共同指向了MethodTableLookup这个方法，我们来看看这个方法的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
.macro MethodTableLookup
	
// push frame
SignLR
stp	fp, lr, [sp, #-16]!
mov	fp, sp
// save parameter registers: x0..x8, q0..q7
sub	sp, sp, #(10*8 + 8*16)
stp	q0, q1, [sp, #(0*16)]
stp	q2, q3, [sp, #(2*16)]
stp	q4, q5, [sp, #(4*16)]
stp	q6, q7, [sp, #(6*16)]
stp	x0, x1, [sp, #(8*16+0*8)]
stp	x2, x3, [sp, #(8*16+2*8)]
stp	x4, x5, [sp, #(8*16+4*8)]
stp	x6, x7, [sp, #(8*16+6*8)]
str	x8,     [sp, #(8*16+8*8)]
// lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
// receiver and selector already in x0 and x1
mov	x2, x16
mov	x3, #3
bl	_lookUpImpOrForward
// IMP in x0
mov	x17, x0
	
// restore registers and return
ldp	q0, q1, [sp, #(0*16)]
ldp	q2, q3, [sp, #(2*16)]
ldp	q4, q5, [sp, #(4*16)]
ldp	q6, q7, [sp, #(6*16)]
ldp	x0, x1, [sp, #(8*16+0*8)]
ldp	x2, x3, [sp, #(8*16+2*8)]
ldp	x4, x5, [sp, #(8*16+4*8)]
ldp	x6, x7, [sp, #(8*16+6*8)]
ldr	x8,     [sp, #(8*16+8*8)]
mov	sp, fp
ldp	fp, lr, [sp], #16
AuthenticateLR
.endmacro

我们暂时忽略寄存器先关操作，主要看方法调用逻辑，可以看到，内部是调用了_lookUpImpOrForward 这个方法，看命名应该能猜到是跟imp的查找和转发逻辑相关，那我们找找这个函数的定义，发现在汇编代码中没有相关定义，我们去runtime原文件中看看，果然在objc_runtime-new.mm的6094行发现了该函数的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/***********************************************************************
* lookUpImpOrForward.
* The standard IMP lookup. 
* Without LOOKUP_INITIALIZE: tries to avoid +initialize (but sometimes fails)
* Without LOOKUP_CACHE: skips optimistic unlocked lookup (but uses cache elsewhere)
* Most callers should use LOOKUP_INITIALIZE and LOOKUP_CACHE
* 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 LOOKUP_NIL.
**********************************************************************/
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
    const IMP forward_imp = (IMP)_objc_msgForward_impcache; // 这里imp有一个默认值 是一个坑点 具体下面解释。
    
    IMP imp = nil;
    Class curClass;
    runtimeLock.assertUnlocked();
    // Optimistic cache lookup // 再去缓存中查找一遍，防止多线程已调用
    if (fastpath(behavior & LOOKUP_CACHE)) {
        imp = cache_getImp(cls, sel);
        if (imp) goto done_nolock;
    }
    runtimeLock.lock(); // 线程安全哦
    checkIsKnownClass(cls);
	// 下面两个操作是对类的继承链,ro,rw等数据的递归实例化，比较重要，不过不在这个文章的讨论范围 先不进去细看。
    if (slowpath(!cls->isRealized())) {
        cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
    }
    if (slowpath((behavior & LOOKUP_INITIALIZE) && !cls->isInitialized())) {
    	 // 类的initialize()方法就是在这里被调用
        cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
    }
    runtimeLock.assertLocked();
    curClass = cls;
    for (unsigned attempts = unreasonableClassCount();;) {
        
        // 直接能从当前类的方法列表中查找到 
        Method meth = getMethodNoSuper_nolock(curClass, sel);
        if (meth) {
            imp = meth->imp;
            goto done;
        }
			
		  // 如果已经查找完当前类的父类中了 给imp一个默认值然后跳出本次递归 
		  // 还没有查找则将当前类赋值为父类 下面继续对父类进行查找
        if (slowpath((curClass = curClass->superclass) == nil)) {
            imp = forward_imp;
            break;
        }
        // 是否还在继承链中查找
        if (slowpath(--attempts == 0)) {
            _objc_fatal("Memory corruption in class list.");
        }
        // 从父类的缓存中查找 curclass已经在上面被赋值为父类了
        // 这个方法也是汇编实现 复用的快查找的逻辑
        imp = cache_getImp(curClass, sel);
        
        // 父类缓存中没有找到 跳出本轮递归 下次又从父类的父类中开始查找
        if (slowpath(imp == forward_imp)) {
           break;
        }
        
        // 找到了 goto done 
        if (fastpath(imp)) {
            goto done;
        }
    }
	// 以上逻辑走完，说明imp还是没有找到，这个时候会做一个动态的方法决议，这部分属于方法转发逻辑，暂时不进去细看。
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        behavior ^= LOOKUP_RESOLVER;
        return resolveMethod_locked(inst, sel, cls, behavior);
    }
 done:
 	// imp找到了，则进行缓存，缓存逻辑参考之前的文章
    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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
    runtimeLock.assertLocked();
    ASSERT(cls->isRealized());
    // fixme nil cls? 
    // fixme nil sel?
	// 方法列表是多级的 
    auto const methods = cls->data()->methods();
    for (auto mlists = methods.beginLists(),
              end = methods.endLists();
         mlists != end;
         ++mlists)
    {
       method_t *m = search_method_list_inline(*mlists, sel);
        if (m) return m;
    }
    return nil;
}
ALWAYS_INLINE static method_t *
search_method_list_inline(const method_list_t *mlist, SEL sel)
{
    int methodListIsFixedUp = mlist->isFixedUp();
    int methodListHasExpectedSize = mlist->entsize() == sizeof(method_t);
    
    if (fastpath(methodListIsFixedUp && methodListHasExpectedSize)) {
        // 对已排序数据进行查找 你想到了什么？？？
        return findMethodInSortedMethodList(sel, mlist);
    } else {
        // Linear search of unsorted method list
        for (auto& meth : *mlist) {
            if (meth.name == sel) return &meth;
        }
    }
    return nil;
}
ALWAYS_INLINE 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;
    
    // 没有错 就是折半查找 不过apple的折半写的比较有逼格。
    for (count = list->count; count != 0; count >>= 1) {
        probe = base + (count >> 1);
        
        uintptr_t probeValue = (uintptr_t)probe->name;
        
        // 如果已找到 则找到同名方法的第一个 这里说明列表内可能有方法名相同的方法，什么情况会出现呢？比如分类同名方法。说明一点，上层的结论在底层都是都代码依据的。
        if (keyValue == probeValue) {
            while (probe > first && keyValue == (uintptr_t)probe[-1].name) {
                probe--;
            }
            return (method_t *)probe;
        }
        
        if (keyValue > probeValue) {
            base = probe + 1;
            count--;
        }
    }
    
    return nil;
}
扩展二 默认的imp

在查找函数的最前面，有下面这行初始化代码：

1
const IMP forward_imp = (IMP)_objc_msgForward_impcache;

这个默认的imp具体指向哪里，我们来全局查找一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
STATIC_ENTRY __objc_msgForward_impcache
// No stret specialization.
b	__objc_msgForward
END_ENTRY __objc_msgForward_impcache
ENTRY __objc_msgForward
// Non-stret version
MI_GET_EXTERN(r12, __objc_forward_handler)
ldr	r12, [r12]
bx	r12
END_ENTRY __objc_msgForward

在汇编代码中找到 __objc_forward_handler这里就线索中断，这个猜测应该是一个回调函数，ok，那我们去源代码里面看看。

1
2
3
4
5
6
7
8
9
10
// Default forward handler halts the process.
__attribute__((noreturn, cold)) void
objc_defaultForwardHandler(id self, SEL sel)
{
    _objc_fatal("%c[%s %s]: unrecognized selector sent to instance %p "
                "(no message forward handler is installed)", 
                class_isMetaClass(object_getClass(self)) ? '+' : '-', 
                object_getClassName(self), sel_getName(sel), self);
}
void *_objc_forward_handler = (void*)objc_defaultForwardHandler;

是不是看到了我们非常熟悉的一个错误信息，没有错，这个默认的imp就是找不到方法实现的错误处理函数。此时，坑点也就出现了，如果你使用class_getMethodImplementation去查找一个未实现的方法时，不会返回空，而是返回这个函数的地址，这里需要注意一下。

小结

以上就是整个慢查找的流程和其中的一些相关的知识点的梳理，除了整体流程的分析，上面的两个扩展也是比较重要的。其中还有一些比较重要的内容没有做深入分析，如realizeClassMaybeSwiftAndLeaveLocked和initializeAndLeaveLocked,留到以后再做分析，毕竟这篇文章主要分析慢查找的流程。