cache拓展补充

buckets是什么结构？为什么是3/4扩容？

使用上节课代码进行lldb调试 cache分析

• 查看cache_t源码，发现分成了3个架构的处理，其中真机的架构中mask和bucket是写在一起，目的是为了优化，可以通过各自的掩码来获取相应的数据
  CACHE_MASK_STORAGE_OUTLINED 表示运行的环境 模拟器 或者 macOS
  CACHE_MASK_STORAGE_HIGH_16 表示运行环境是 64位的真机
  CACHE_MASK_STORAGE_LOW_4表示运行环境是 非64位 的真机

image.png image.png

• 查看insert源码

主要分为以下几部分

1. 计算出当前的缓存占用量
2. 根据缓存占用量判断执行的操作
3. 针对需要存储的bucket进行内部imp和sel赋值

• 第一步 根据occupied的值计算出当前的缓存占用量，当属性未赋值及无方法调用时，此时的occupied()为0，而newOccupied为1，源码如下

mask_t newOccupied = occupied() + 1;

• 第二步 根据缓存占用量判断执行的操作

1. 如果是第一次创建，则默认开辟4个

if (slowpath(isConstantEmptyCache())) { //小概率发生的 即当 occupied() = 0时，即创建缓存，创建属于小概率事件
    // Cache is read-only. Replace it.
    if (!capacity) capacity = INIT_CACHE_SIZE; //初始化时，capacity = 4（1<<2 -- 100）
    reallocate(oldCapacity, capacity, /* freeOld */false); //开辟空间
    //到目前为止，if的流程的操作都是初始化创建
}

2. 如果缓存占用量小于等于3/4，则不作任何处理

else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) { 
    // Cache is less than 3/4 full. Use it as-is.
}

3. 如果缓存占用量超过3/4，则需要进行两倍扩容以及重新开辟空间

else {//如果超出了3/4，则需要扩容（两倍扩容）
    //扩容算法： 有cap时，扩容两倍，没有cap就初始化为4
    capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 扩容两倍 2*4 = 8
    if (capacity > MAX_CACHE_SIZE) {
        capacity = MAX_CACHE_SIZE;
    }
    // 走到这里表示 曾经有，但是已经满了，需要重新梳理
    reallocate(oldCapacity, capacity, true);
    // 内存 扩容完毕
}

• 第三步 针对需要存储的bucket进行内部imp和sel赋值

这部分主要是根据cache_hash方法即哈希算法 ，计算sel-imp存储的哈希下标，分为以下三种情况：

1. 如果哈希下标的位置未存储sel，即该下标位置获取sel等于0，此时将sel-imp存储进去，并将occupied占用大小加1
2. 如果当前哈希下标存储的sel 等于 即将插入的sel，则直接返回
3. 如果当前哈希下标存储的sel 不等于 即将插入的sel，则重新经过cache_next方法 即哈希冲突算法，重新进行哈希计算，得到新的下标，再去对比进行存储

得出结论

• _bucketsAndMaybeMask存储的就是buckets()的首地址
• 3/4扩容空间利用率最高，哈希冲突概率最低

cache读取流程分析

objc4源码中objc_cache.mm文件描述了cache的读取流程，如下所示

 * Cache readers (PC-checked by collecting_in_critical())
 * objc_msgSend*
 * cache_getImp
 *
 * Cache readers/writers (hold cacheUpdateLock during access; not PC-checked)
 * cache_t::copyCacheNolock    (caller must hold the lock)
 * cache_t::eraseNolock        (caller must hold the lock)
 * cache_t::collectNolock      (caller must hold the lock)
 * cache_t::insert             (acquires lock)
 * cache_t::destroy            (acquires lock)

从上面可以看出，cache_getImp发起了对cache的读写调用流程，用于读取缓存中函数调用地址。在这之前又调用了objc_msgSend，这就引出了本节课探索的重点objc_msgSend函数，这个函数的流程是怎么的呢？下面进行探索......

OC的编译时与运行时

编译时

Building，编译时是源代码翻译成机器能识别的代码的过程，主要是对语言进行最基本的检查报错，即词法分析、语法分析等，是一个静态的阶段，这些都是LLVM来做的

运行时

Running，运行时 是代码跑起来，被装载到内存中的过程，如果此时出错，则程序会崩溃，是一个动态阶段

Runtime有两个版本

Objective-C Runtime Programming Guide

一个Legacy版本(早期版本)

• 早期版本对应的编程接口:Objective-C 1.0
• 早期版本用于Objective-C 1.0, 32位的Mac OS X的平台上

一个Modern版本(现行版本)

• 现行版本对应的编程接口:Objective-C 2.0
• 现行版本:iPhone程序和Mac OS X v10.5及以后的系统中的64位程序

runtime的使用方式

runtime使用有三种方式，其三种实现方法与编译层和底层的关系如图所示

• 通过OC层面方法调用，例如[person sayNB]
• 通过NSObject调用相关的API，例如isKindOfClass
• 通过Runtime API，例如class_getInstanceSize

image.png

Compiler就是我们了解的编译器即LLVM，例如OC的alloc对应底层的objc_alloc，runtime system libarary就是底层库

objc_msgSend流程

创建LGPerson类，其中sayHello方法没有实现，在main函数中调用。代码如下

@interface LGPerson : NSObject
- (void)sayHello;
- (void)sayNB;
@end

@implementation LGPerson
- (void)sayNB{
    NSLog(@"666");
}
@end

//main.m中方法的调用
int main(int argc, const char * argv[]) {
    @autoreleasepool {
        LGPerson *person = [LGPerson alloc];
        [person sayNB];
        [person sayHello];
    }
    return 0;
}

使用clang把main.m编译main.cpp文件，通过查看main函数中方法调用的实现如下所示

//clang编译后的底层实现
LGPerson *person = ((LGPerson *(*)(id, SEL))(void *)objc_msgSend)((id)objc_getClass("LGPerson"), sel_registerName("alloc"));
((void (*)(id, SEL))(void *)objc_msgSend)((id)person, sel_registerName("sayNB"));
((void (*)(id, SEL))(void *)objc_msgSend)((id)person, sel_registerName("sayHello"));

得出结论： 方法的本质就是objc_msgSend消息发送

下面验证objc_msgSend方法来完成[person sayNB]的调用，查看其打印是否是一致

• 直接调用objc_msgSend，需要导入头文件#import <objc/message.h>
• 需要将target --> Build Setting -->搜索msg -- 将enable strict checking of obc_msgSend calls由YES 改为NO，将严厉的检查机制关掉，否则objc_msgSend的参数会报错

LGPerson *person = [LGPerson alloc];   
objc_msgSend(person,sel_registerName("sayNB"));
[person sayNB];

// 控制台打印
2021-07-25 11:59:18.414202+0800 001-运行时感受[55836:6041045] 666
2021-07-25 11:59:18.416631+0800 001-运行时感受[55836:6041045] 666

得出结论：[person sayNB]等价于objc_msgSend(person,sel_registerName("sayNB"))

接下来我们修改代码如下，让person调用执行父类中的实现

@interface LGTeacher : NSObject
- (void)sayHello;
@end

@implementation LGTeacher
- (void)sayHello{
    NSLog(@"666 %s",__func__);
}
@end

@interface LGPerson : LGTeacher
- (void)sayHello;
- (void)sayNB;
@end

@implementation LGPerson
- (void)sayNB{
    NSLog(@"666");
}
@end

// main中的调用
LGPerson *person = [LGPerson alloc];
[person sayHello];

// 控制台打印
2021-07-25 12:14:01.223238+0800 001-运行时感受[55928:6051186] 666 -[LGTeacher sayHello]

// 使用clang把main.m编译main.cpp文件，并在main.cpp文件中全局搜索objc_msgSend，结果发现了objc_msgSendSuper
#define __OBJC_RW_DLLIMPORT extern
__OBJC_RW_DLLIMPORT void objc_msgSend(void);
__OBJC_RW_DLLIMPORT void objc_msgSendSuper(void);
__OBJC_RW_DLLIMPORT void objc_msgSend_stret(void);
__OBJC_RW_DLLIMPORT void objc_msgSendSuper_stret(void);
__OBJC_RW_DLLIMPORT void objc_msgSend_fpret(void);
__OBJC_RW_DLLIMPORT struct objc_class *objc_getClass(const char *);
__OBJC_RW_DLLIMPORT struct objc_class *class_getSuperclass(struct objc_class *);
__OBJC_RW_DLLIMPORT struct objc_class *objc_getMetaClass(const char *);
__OBJC_RW_DLLIMPORT void objc_exception_throw( struct objc_object *);
__OBJC_RW_DLLIMPORT int objc_sync_enter( struct objc_object *);
__OBJC_RW_DLLIMPORT int objc_sync_exit( struct objc_object *);
__OBJC_RW_DLLIMPORT Protocol *objc_getProtocol(const char *);

上面[person sayHello]为什么会触发到objc_msgSendSuper，objc_msgSendSuper底层又是什么结构呢？
原因是person中没有sayHello方法，就会去父类中查找，这时就会触发到objc_msgSendSuper。查看源码发现objc_msgSendSuper方法中有两个参数（结构体，sel），其结构体类型是objc_super定义的结构体对象，且需要指定receiver和super_class两个属性。

源码实现如下

• objc_msgSendSuper方法

objc_msgSendSuper(void /* struct objc_super *super, SEL op, ... */ )
    OBJC_AVAILABLE(10.0, 2.0, 9.0, 1.0, 2.0);

• objc_super方法

#ifndef OBJC_SUPER
#define OBJC_SUPER

/// Specifies the superclass of an instance. 
struct objc_super {
    /// Specifies an instance of a class.
    __unsafe_unretained _Nonnull id receiver;

    /// Specifies the particular superclass of the instance to message. 
#if !defined(__cplusplus)  &&  !__OBJC2__
    /* For compatibility with old objc-runtime.h header */
    __unsafe_unretained _Nonnull Class class;
#else
    __unsafe_unretained _Nonnull Class super_class;
#endif
    /* super_class is the first class to search */
};
#endif

既然已经探索到objc_msgSendSuper源码与objc_super结构体，我们修改main.m中代码如下

LGPerson *person = [LGPerson alloc];
[person sayHello];

struct objc_super kc_objc_super;
kc_objc_super.receiver = person;//消息的接收者还是person
kc_objc_super.super_class = LGTeacher.class;//告诉父类是谁
//消息的接受者还是自己 - 父类 - 请你直接找我的父亲
objc_msgSendSuper(&kc_objc_super,@selector(sayHello));

// 控制台打印
2021-07-25 14:54:32.642329+0800 001-运行时感受[56624:6133486] 666 -[LGTeacher sayHello]
2021-07-25 14:54:32.642828+0800 001-运行时感受[56624:6133486] 666 -[LGTeacher sayHello]

得出结论：发现不论是[person sayHello]还是objc_msgSendSuper都执行的是父类中sayHello的实现，所以这里我们可以作一个猜测：方法调用，首先是在类中查找，如果类中没有找到，会到类的父类中查找。

objc_msgSend 汇编分析

objc_msgSend是消息发送源码的入口，是使用汇编实现的。而其他方法是使用C或者C++实现的。objc_msgSend汇编根据sel查找imp的流程实现如下

//---- 消息发送 -- 汇编入口--objc_msgSend主要是拿到接收者的isa信息
ENTRY _objc_msgSend 
//---- 无窗口
    UNWIND _objc_msgSend, NoFrame 
    
//---- p0 和空对比，即判断接收者是否存在，其中p0是objc_msgSend的第一个参数-消息接收者receiver
    cmp p0, #0          // nil check and tagged pointer check 
//---- le小于 --支持taggedpointer（小对象类型）的流程
#if SUPPORT_TAGGED_POINTERS
    b.le    LNilOrTagged        //  (MSB tagged pointer looks negative) 
#else
//---- p0 等于 0 时，直接返回 空
    b.eq    LReturnZero 
#endif 
//---- p0即receiver 肯定存在的流程
//---- 根据对象拿出isa ，即从x0寄存器指向的地址 取出 isa，存入 p13寄存器
    ldr p13, [x0]       // p13 = isa 
//---- 在64位架构下通过 p16 = isa（p13） & ISA_MASK，拿出shiftcls信息，得到class信息
    GetClassFromIsa_p16 p13     // p16 = class 
LGetIsaDone:
    // calls imp or objc_msgSend_uncached 
//---- 如果有isa，走到CacheLookup 即缓存查找流程，也就是所谓的sel-imp快速查找流程
    CacheLookup NORMAL, _objc_msgSend

#if SUPPORT_TAGGED_POINTERS
LNilOrTagged:
//---- 等于空，返回空
    b.eq    LReturnZero     // nil check 

    // tagged
    adrp    x10, _objc_debug_taggedpointer_classes@PAGE
    add x10, x10, _objc_debug_taggedpointer_classes@PAGEOFF
    ubfx    x11, x0, #60, #4
    ldr x16, [x10, x11, LSL #3]
    adrp    x10, _OBJC_CLASS_$___NSUnrecognizedTaggedPointer@PAGE
    add x10, x10, _OBJC_CLASS_$___NSUnrecognizedTaggedPointer@PAGEOFF
    cmp x10, x16
    b.ne    LGetIsaDone

    // ext tagged
    adrp    x10, _objc_debug_taggedpointer_ext_classes@PAGE
    add x10, x10, _objc_debug_taggedpointer_ext_classes@PAGEOFF
    ubfx    x11, x0, #52, #8
    ldr x16, [x10, x11, LSL #3]
    b   LGetIsaDone
// SUPPORT_TAGGED_POINTERS
#endif

LReturnZero:
    // x0 is already zero
    mov x1, #0
    movi    d0, #0
    movi    d1, #0
    movi    d2, #0
    movi    d3, #0
    ret

    END_ENTRY _objc_msgSend

主要步骤如下

• 判断objc_msgSend方法的第一个参数receiver是否为空

1. 如果支持tagged pointer，跳转至LNilOrTagged
   如果小对象为空，则直接返回空，即LReturnZero
   如果小对象不为空，则处理小对象的isa
2. 如果即不是小对象，receiver也不为空，有以下两步
   从receiver中取出isa存入p13寄存器，
   通过 GetClassFromIsa_p16中，arm64架构下通过isa & ISA_MASK获取shiftcls位域的类信息，即class，GetClassFromIsa_p16的汇编实现如下

.macro GetClassFromIsa_p16 /* src */
//---- 此处用于watchOS
#if SUPPORT_INDEXED_ISA 
    // Indexed isa
//---- 将isa的值存入p16寄存器
    mov p16, $0         // optimistically set dst = src 
    tbz p16, #ISA_INDEX_IS_NPI_BIT, 1f  // done if not non-pointer isa -- 判断是否是 nonapointer isa
    // isa in p16 is indexed
//---- 将_objc_indexed_classes所在的页的基址 读入x10寄存器
    adrp    x10, _objc_indexed_classes@PAGE 
//---- x10 = x10 + _objc_indexed_classes(page中的偏移量) --x10基址 根据 偏移量 进行 内存偏移
    add x10, x10, _objc_indexed_classes@PAGEOFF
//---- 从p16的第ISA_INDEX_SHIFT位开始，提取 ISA_INDEX_BITS 位 到 p16寄存器，剩余的高位用0补充
    ubfx    p16, p16, #ISA_INDEX_SHIFT, #ISA_INDEX_BITS  // extract index 
    ldr p16, [x10, p16, UXTP #PTRSHIFT] // load class from array
1:

//--用于64位系统
#elif __LP64__ 
    // 64-bit packed isa
//---- p16 = class = isa & ISA_MASK(位运算 & 即获取isa中的shiftcls信息)
    and p16, $0, #ISA_MASK 

#else
    // 32-bit raw isa ---- 用于32位系统
    mov p16, $0

#endif

.endmacro

• 获取isa完毕，进入慢速查找流程CacheLookup NORMAL

汇编整体流程图如下

image.png