008-消息的快速查找（下）

通过这篇文章可以获得什么

• objc_msgSend流程的简化回顾
• 真机调试（汇编分析）
• 真机汇编分解(图解)
• 关于类cache_t内存扩容在真机情况下的源码模拟
• 真机与模拟器模式下的cache_fill_ratio & INIT_CACHE_SIZE_LOG2
• 本节设计汇编指令补充
• 真机源码调试Demo

流程的简化回顾

第一：判断当前接收者是否存在

cmp	p0, #0
复制代码

第二：通过isa拿到class

GetClassFromIsa_p16 p13, 1, x0
复制代码

第三：进入CacheLookup流程,两种结果，找到并抛出imp，没找到通过__objc_msgSend_uncached进入后续的慢速查找流程

CacheLookup NORMAL, _objc_msgSend, __objc_msgSend_uncached
复制代码

第四：LLookupStart，查找开始，这里分解真机、arm64架构，A12以上芯片汇编，下面只列出满足此条件的汇编

//arm64架构
CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
//真机
CONFIG_USE_PREOPT_CACHES = 1
//是判断编译器是否支持指针身份验证功能，针对arm64e
//A12以上芯片（支持arm64e结构）
 __has_feature(ptrauth_calls)
复制代码

第五：将isa偏移16个字节，得到cache_t

ldr	p11, [x16, #CACHE]
复制代码

第六：判断cache_t的0号位置是否为0，如果不为0，执行LLookupPreopt，去找共享缓存，如果为0，将cache_t(_bucketsAndMaybeMask) & #0x0000ffffffffffff,得到了bucekts

tbnz	p11, #0, LLookupPreopt\Function
and	p10, p11, #0x0000ffffffffffff	// p10 = buckets
复制代码

第七：将sel右移7位在与自己做逻辑异或^赋值给p12,将cache_t(_bucketsAndMaybeMask)右移48位，即清空了buckets，可以得到mask，最后将p12 & mask，得到了第一次查找bucket_t的index，即first_probed

eor	p12, p1, p1, LSR #7
and	p12, p12, p11, LSR #48		// x12 = (_cmd ^ (_cmd >> 7)) & mask
复制代码

对于第七步的源码解释：

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    uintptr_t value = (uintptr_t)sel;
#if CONFIG_USE_PREOPT_CACHES
    value ^= value >> 7;
#endif
    return (mask_t)(value & mask);
}
复制代码

第八：有第七步得知第一个查找的bucket_t的下标index，那么接下来就是如何偏移到这个bucket_t拿到里面的sel与imp，这里的做法是将index向左偏移4位，可以理解为index * （1 << 4）即index * 16，得到的是偏移距离，为什么偏移4位，因为一个bucket_t占16字节，最后在加上buckets地址，就得到了第一个要比较的bucket_t。

add	p13, p10, p12, LSL #(1+PTRSHIFT)
复制代码

第九：将p13内的imp和sel拿出来分别存在p17和p9，执行bucket--。如果sel != _cmd,执行3f，判断sel是否存在，有值，将bucket（当前）与bucekts（bucket首位）比较，如果>0，继续循环，回到1b，执行bucket--。如果这个过程找到了目标_cmd,跳转到2，命中缓存，结束查找。

1:	ldp	p17, p9, [x13], #-BUCKET_SIZE	
	cmp	p9, p1				
	b.ne	3f				
复制代码

2:	CacheHit \Mode				
复制代码

3:	cbz	p9, \MissLabelDynamic		
	cmp	p13, p10			
	b.hs	1b
复制代码

如果找到bucket首位都未匹配到目标_cmd，则直接跳转至mask处bucket（末位bucket_t），查找缓存内剩余的buckets，这里还获取了第一次探查的位置index，为了避免重复探查。4内操作为将bucket_t的imp和sel拿出来赋值给p17和p9，bucket--，比较sel与_cmd，如果成功，执行2b，命中缓存，判断p9是否存在，判断当前bucket是否大于第一次探查的bucket，如果上述条件都满足，则继续循环4b，直到命中缓存。如果全部都搜索完还没有命中，进入慢速查找流程。

add	p13, p10, p11, LSR #(48 - (1+PTRSHIFT))
复制代码

add	p12, p10, p12, LSL #(1+PTRSHIFT)
复制代码

4:	ldp	p17, p9, [x13], #-BUCKET_SIZE	//     {imp, sel} = *bucket--
	cmp	p9, p1				//     if (sel == _cmd)
	b.eq	2b				//         goto hit
	cmp	p9, #0				// } while (sel != 0 &&
	ccmp	p13, p12, #0, ne		//     bucket > first_probed)
	b.hi	4b
复制代码

真机调试（汇编分析）

案例源码：

@interface FFPerson : NSObject
- (void)likeGirls;
@end

@implementation FFPerson
- (void)likeGirls{
    NSLog(@"%s",__func__);
}
@end
int main(int argc, char * argv[]) {
    @autoreleasepool {

        FFPerson *person = [FFPerson alloc];
        [person likeGirls];
        
    }
    return UIApplicationMain(argc, argv, nil, NSStringFromClass([AppDelegate class]));
}
复制代码

确认当前探索的类与方法

真机汇编分解图解：

关于类cache_t内存扩容在真机情况下的源码模拟

Demo地址

部分关键源码：

typedef uint32_t mask_t;  // x86_64 & arm64 asm are less efficient

//preopt_cache_entry_t源码模仿
struct ff_preopt_cache_entry_t {
    uint32_t sel_offs;
    uint32_t imp_offs;
};

//preopt_cache_t源码模仿
struct ff_preopt_cache_t {
    int32_t  fallback_class_offset;
    union {
        struct {
            uint16_t shift       :  5;
            uint16_t mask        : 11;
        };
        uint16_t hash_params;
    };
    uint16_t occupied    : 14;
    uint16_t has_inlines :  1;
    uint16_t bit_one     :  1;
    struct ff_preopt_cache_entry_t entries;
    
    inline int capacity() const {
        return mask + 1;
    }
};

//bucket_t源码模仿
struct ff_bucket_t {
    IMP _imp;
    SEL _sel;
};

//cache_t源码模仿
struct ff_cache_t {
    uintptr_t _bucketsAndMaybeMask; // 8
    struct ff_preopt_cache_t _originalPreoptCache; // 8

    static constexpr uintptr_t maskShift = 48;

    static constexpr uintptr_t maskZeroBits = 4;

    static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
    
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
    
    static constexpr uintptr_t preoptBucketsMarker = 1ul;

    static constexpr uintptr_t preoptBucketsMask = 0x007ffffffffffffe;
    
    ff_bucket_t *buckets() {
        return (ff_bucket_t *)(_bucketsAndMaybeMask & bucketsMask);
    }
    
    uint32_t mask() const {
        return _bucketsAndMaybeMask >> maskShift;
    }
    
};

//class_data_bits_t源码模仿
struct ff_class_data_bits_t {
    uintptr_t objc_class;
};

//类源码模仿
struct ff_objc_class {
    Class isa;
    Class superclass;
    struct ff_cache_t cache;
    struct ff_class_data_bits_t bits;
};


void test(Class cls) {
    
    //将person的类型转换成自定义的源码ff_objc_class类型，方便后续操作
    struct ff_objc_class *pClass = (__bridge struct ff_objc_class *)(cls);
    
    struct ff_cache_t cache = pClass->cache;
    struct ff_bucket_t * buckets = cache.buckets();
    struct ff_preopt_cache_t origin = cache._originalPreoptCache;
    uintptr_t _bucketsAndMaybeMask = cache._bucketsAndMaybeMask;
    uintptr_t mask = cache.mask();
    
    
    
    NSLog(@"class: %p", pClass);
    NSLog(@"_bucketsAndMaybeMask: 0x%lx, mask: %lu", _bucketsAndMaybeMask, mask);
    
    //打印当前有多少个方法缓存与最大缓存数量
    NSLog(@"%u-%u",origin.occupied,origin.capacity());
    
    //打印buckets
    for (int i = 0; i < mask + 1; i++ ) {
        SEL sel = buckets[i]._sel;
        IMP imp = buckets[i]._imp;
        NSLog(@"%@-%p",NSStringFromSelector(sel),imp);
    }
}

int main(int argc, char * argv[]) {

    @autoreleasepool {
        
        //给person分配内存
        FFPerson *person = [FFPerson alloc];
        //调用方法
        [person likeGirls];
        test(person.class);
        [person likeFoods];
        test(person.class);
        [person likeflower];
        test(person.class);
        [person likeStudy];
        test(person.class);
        [person enjoyLift];
        test(person.class);
        [person lnspireCreativity];
        test(person.class);
        
       ......

    }
    return UIApplicationMain(argc, argv, nil, NSStringFromClass([AppDelegate class]));
}
复制代码

打印结果

2021-06-30 23:38:39.523507+0800 002-cache真机源码还原[2001:757686] -[FFPerson likeGirls]
2021-06-30 23:38:39.524594+0800 002-cache真机源码还原[2001:757686] class: 0x102ef9680
2021-06-30 23:38:39.524617+0800 002-cache真机源码还原[2001:757686] _bucketsAndMaybeMask: 0x10002835b60e0, mask: 1
2021-06-30 23:38:39.524633+0800 002-cache真机源码还原[2001:757686] 1-1025
2021-06-30 23:38:39.524651+0800 002-cache真机源码还原[2001:757686] (null)-0x0
2021-06-30 23:38:39.524706+0800 002-cache真机源码还原[2001:757686] likeGirls-0xe00f9f8102ef148c
2021-06-30 23:38:39.524728+0800 002-cache真机源码还原[2001:757686] -[FFPerson likeFoods]
2021-06-30 23:38:39.524868+0800 002-cache真机源码还原[2001:757686] class: 0x102ef9680
2021-06-30 23:38:39.525038+0800 002-cache真机源码还原[2001:757686] _bucketsAndMaybeMask: 0x10002835b60e0, mask: 1
2021-06-30 23:38:39.525138+0800 002-cache真机源码还原[2001:757686] 2-1025
2021-06-30 23:38:39.525253+0800 002-cache真机源码还原[2001:757686] likeFoods-0xf64c0b0102ef1504
2021-06-30 23:38:39.525279+0800 002-cache真机源码还原[2001:757686] likeGirls-0xe00f9f8102ef148c
2021-06-30 23:38:39.525298+0800 002-cache真机源码还原[2001:757686] -[FFPerson likeflower]
2021-06-30 23:38:39.525312+0800 002-cache真机源码还原[2001:757686] class: 0x102ef9680
2021-06-30 23:38:39.525326+0800 002-cache真机源码还原[2001:757686] _bucketsAndMaybeMask: 0x30002820b4c40, mask: 3
2021-06-30 23:38:39.525437+0800 002-cache真机源码还原[2001:757686] 1-1025
2021-06-30 23:38:39.525517+0800 002-cache真机源码还原[2001:757686] (null)-0x0
2021-06-30 23:38:39.525783+0800 002-cache真机源码还原[2001:757686] (null)-0x0
2021-06-30 23:38:39.525910+0800 002-cache真机源码还原[2001:757686] (null)-0x0
2021-06-30 23:38:39.526071+0800 002-cache真机源码还原[2001:757686] likeflower-0x2d78768102ef14c8
2021-06-30 23:38:39.526236+0800 002-cache真机源码还原[2001:757686] -[FFPerson likeStudy]
2021-06-30 23:38:39.526347+0800 002-cache真机源码还原[2001:757686] class: 0x102ef9680
2021-06-30 23:38:39.526438+0800 002-cache真机源码还原[2001:757686] _bucketsAndMaybeMask: 0x30002820b4c40, mask: 3
2021-06-30 23:38:39.526548+0800 002-cache真机源码还原[2001:757686] 2-1025
2021-06-30 23:38:39.526643+0800 002-cache真机源码还原[2001:757686] (null)-0x0
2021-06-30 23:38:39.526745+0800 002-cache真机源码还原[2001:757686] (null)-0x0
2021-06-30 23:38:39.526900+0800 002-cache真机源码还原[2001:757686] likeStudy-0xf26c730102ef1540
2021-06-30 23:38:39.527019+0800 002-cache真机源码还原[2001:757686] likeflower-0x2d78768102ef14c8
2021-06-30 23:38:39.527098+0800 002-cache真机源码还原[2001:757686] -[FFPerson enjoyLift]
2021-06-30 23:38:39.527195+0800 002-cache真机源码还原[2001:757686] class: 0x102ef9680
2021-06-30 23:38:39.527316+0800 002-cache真机源码还原[2001:757686] _bucketsAndMaybeMask: 0x30002820b4c40, mask: 3
2021-06-30 23:38:39.527427+0800 002-cache真机源码还原[2001:757686] 3-1025
2021-06-30 23:38:39.527520+0800 002-cache真机源码还原[2001:757686] (null)-0x0
2021-06-30 23:38:39.527626+0800 002-cache真机源码还原[2001:757686] enjoyLift-0x8e617e8102ef157c
2021-06-30 23:38:39.527728+0800 002-cache真机源码还原[2001:757686] likeStudy-0xf26c730102ef1540
2021-06-30 23:38:39.527829+0800 002-cache真机源码还原[2001:757686] likeflower-0x2d78768102ef14c8
2021-06-30 23:38:39.528005+0800 002-cache真机源码还原[2001:757686] -[FFPerson lnspireCreativity]
2021-06-30 23:38:39.528130+0800 002-cache真机源码还原[2001:757686] class: 0x102ef9680
2021-06-30 23:38:39.528236+0800 002-cache真机源码还原[2001:757686] _bucketsAndMaybeMask: 0x30002820b4c40, mask: 3
2021-06-30 23:38:39.528349+0800 002-cache真机源码还原[2001:757686] 4-1025
2021-06-30 23:38:39.528450+0800 002-cache真机源码还原[2001:757686] lnspireCreativity-0xc6607b8102ef15b8
2021-06-30 23:38:39.528536+0800 002-cache真机源码还原[2001:757686] enjoyLift-0x8e617e8102ef157c
2021-06-30 23:38:39.528705+0800 002-cache真机源码还原[2001:757686] likeStudy-0xf26c730102ef1540
2021-06-30 23:38:39.528804+0800 002-cache真机源码还原[2001:757686] likeflower-0x2d78768102ef14c8
复制代码

INIT_CACHE_SIZE_LOG2

#if CACHE_END_MARKER || (__arm64__ && !__LP64__)
    INIT_CACHE_SIZE_LOG2 = 2,
#else
    INIT_CACHE_SIZE_LOG2 = 1,
#endif
复制代码

cache_fill_ratio

#if __arm__  ||  __x86_64__  ||  __i386__

#define CACHE_END_MARKER 1

static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 3 / 4;
}

#elif __arm64__ && !__LP64__

#define CACHE_END_MARKER 0

static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 3 / 4;
}

#elif __arm64__ && __LP64__

#define CACHE_END_MARKER 0

static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 7 / 8;
}

#define CACHE_ALLOW_FULL_UTILIZATION 1

#else
#error unknown architecture
#endif
复制代码

结论：

1. iPhoneXs，初始缓存容量为2（INIT_CACHE_SIZE = (1 << 1)）
2. 真机扩容按照7/8的规则，2倍扩容，所以扩容规律2-> 4 -> 8 -> 16 -> 2^n
3. x86_64架构初始容量为4（INIT_CACHE_SIZE = (1 << 2)）
4. 模拟器扩容按照3/4的规则，2倍扩容，扩容规律4 -> 8 -> 16 -> 2^(n+1)

拓展

源码释义补充

objc底层操作预留位，判断是否有preopt_cache_t，是给objc_msgSend使用的

static constexpr uintptr_t maskZeroBits = 4;
复制代码

汇编指令：

本篇内容涉及的部分汇编指令：