cache补充

在cache底层原理分析的过程中，讲到cache的内存扩容，这里对内存扩容做一些补充。cache存储sel-imp需要insert方法，接下来就来分析insert源码

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    runtimeLock.assertLocked();

    // Never cache before +initialize is done
    if (slowpath(!cls()->isInitialized())) {
        return;
    }

    if (isConstantOptimizedCache()) {
        _objc_fatal("cache_t::insert() called with a preoptimized cache for %s",
                    cls()->nameForLogging());
    }

#if DEBUG_TASK_THREADS
    return _collecting_in_critical();
#else
#if CONFIG_USE_CACHE_LOCK
    mutex_locker_t lock(cacheUpdateLock);
#endif

    ASSERT(sel != 0 && cls()->isInitialized());

    // Use the cache as-is if until we exceed our expected fill ratio.
    <!-- 第一步 -->
    // 当缓存使用少于3/4时，没有属性赋值的情况下 occupied() = 0，newOccupied = 1
    mask_t newOccupied = occupied() + 1; // 1+1
    unsigned oldCapacity = capacity(), capacity = oldCapacity;

    <!-- 第二步 -->
    // 小概率发生，当occupied() = 0时，即创建缓存，创建属于小概率事件
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        // 初始化是，capacity = 4 (1<<2 -- 100)
        if (!capacity) capacity = INIT_CACHE_SIZE;//4
        reallocate(oldCapacity, capacity, /* freeOld */false); //开辟空间
        // 到目前为止，if的流程操作都是初始化创建
    }
    else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) {
        // Cache is less than 3/4 or 7/8 full. Use it as-is.
        // 如果小于等于占用内存的3/4，什么都不用做
        // 第一次申请开辟的内存是4个，如果此时已经有3个从bucket插入到cache里面，在插入1个就是4个，当大于4即当前下标是4，数组越界肯定不行，所以需要在原来的容量上进行两倍扩容
    }
#if CACHE_ALLOW_FULL_UTILIZATION
    else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) {
        // Allow 100% cache utilization for small buckets. Use it as-is.
    }
#endif
    else {// 4*2 = 8
        // 如果超出了3/4，则需要扩容(两倍扩容)  -- 即occupied为2时，就没有进去了
        // 扩容算法：有cap时扩容两倍，没有cap就初始化为4
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE; // 扩容两倍
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        // 走到这里表示曾经有，但是已经满了，需要重新梳理
        reallocate(oldCapacity, capacity, true);
        // 内存扩容完毕
    }
    
    <!-- 第三步 -->
    bucket_t *b = buckets();
    mask_t m = capacity - 1; // 4-1=3  mask = cap - 1 
    // 求cache哈希，即哈希下标---通过哈希算法函数计算sel存储的下标
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;

    // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot.
    // 如果存在了哈希冲突，则从冲突的下标开始遍历。即进行do-while循环
    do {
        // 如果当前遍历的下标拿不到sel，即表示当前下标没有存储sel
        if (fastpath(b[i].sel() == 0)) {
            //则将sel存储进去，并将对应的occupied标记++，即从0变为1
            incrementOccupied();
            b[i].set<Atomic, Encoded>(b, sel, imp, cls());
            return;
        }
        // 如果当前哈希下标的sel等于准备插入的sel，则直接返回
        if (b[i].sel() == sel) {
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
        }
    //如果当前计算的哈希下标已经存储了sel，且两个sel不相等，需要重新进行哈希算法，得到新的下标
    } while (fastpath((i = cache_next(i, m)) != begin));

    bad_cache(receiver, (SEL)sel);
#endif // !DEBUG_TASK_THREADS
}

insert方法主要分为三步

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

第一步

根据occupied的值计算出当前的缓存占用量，当属性未赋值或方法无调用时，occupied()为0，newOccupied为1，如下所示

mask_t newOccupied = occupied() + 1;

关于缓存占用量计算的几点说明：

• alloc申请空间时，此时的对象已经创建，如果再调用init方法，occupied也会+1
• 当有属性赋值时，会隐式调用set方法，occupied也会增加，即有几个属性赋值，occupied就会在原有的基础上加几个
• 当有方法调用时，occupied也会增加，即有几次调用，occupied就会在原有的基础上加几个

第二步

• 如果是第一次创建，默认开辟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的流程的操作都是初始化创建
}

• 如果缓存占用量小于等于3/4，不作任何处理
• 如果缓存占用量超过3/4，则需要进行两倍扩容以及重新开辟空间

reallocate方法开辟空间

该方法在第一次创建以及两倍扩容时，都会使用

ALWAYS_INLINE
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    // 判断是否有旧的bucket，第一次肯定是旧的bucket
    bucket_t *oldBuckets = buckets();
    // 开辟bucket，此时只有一个临时变量
    bucket_t *newBuckets = allocateBuckets(newCapacity);

    // Cache's old contents are not propagated. 
    // This is thought to save cache memory at the cost of extra cache fills.
    // fixme re-measure this

    ASSERT(newCapacity > 0);
    ASSERT((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
    // 将临时的bucket存入缓存中
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
        collect_free(oldBuckets, oldCapacity);
    }
}

主要步骤

• allocateBuckets方法：向系统申请开辟内存即开辟bucket，此时的bucket只是一个临时变量
• setBucketsAndMask方法：将临时的bucket存入缓存中，此时的存储分为两种情况：

1. 如果是真机，根据bucket和mask的位置存储，并将occupied占用设置为0
2. 如果不是真机，正常存储bucket和mask，并将occupied占用设置为0

• 如果有旧的buckets，需要清理之前的缓存即调用collect_free方法，源码如下

void cache_t::collect_free(bucket_t *data, mask_t capacity)
{
#if CONFIG_USE_CACHE_LOCK
    cacheUpdateLock.assertLocked();
#else
    runtimeLock.assertLocked();
#endif

    if (PrintCaches) recordDeadCache(capacity);
    // 创建垃圾回收空间
    _garbage_make_room ();
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    // 将sel-imp存在后置的位置
    garbage_refs[garbage_count++] = data;
    // 垃圾回收，清理旧的bucket
    cache_t::collectNolock(false);
}

第三步

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

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

其中涉及的两种哈希算法源码如下

• cache_hash哈希算法

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);
}

• cache_next哈希冲突算法

#if CACHE_END_MARKER
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask; //（将当前的哈希下标 +1） & mask，重新进行哈希计算，得到一个新的下标
}
#elif __arm64__
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask; //如果i是空，则为mask，mask = cap -1，如果不为空，则 i-1，向前插入sel-imp
}
#else
#error unexpected configuration
#endif

汇编objc_msgSend原理

上节课我们在objc_msgSend汇编源码分析的时候，讲到获取isa完毕之后，会进入慢速查找流程CacheLookup NORMAL

CacheLookup缓存查找汇编源码

.macro CacheLookup Mode, Function, MissLabelDynamic, MissLabelConstant
......
    
    // 把x16也就是class移到x15 
    mov x15, x16            // stash the original isa
LLookupStart\Function:
    // p1 = SEL, p16 = isa
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
    ldr p10, [x16, #CACHE]              // p10 = mask|buckets
    lsr p11, p10, #48           // p11 = mask
    and p10, p10, #0xffffffffffff   // p10 = buckets
    and w12, w1, w11            // x12 = _cmd & mask
    //如果是真机arm64执行 HIGH_16
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    //---- p1 = SEL, p16 = isa --- #define CACHE (2 * __SIZEOF_POINTER__)，其中 __SIZEOF_POINTER__表示pointer的大小 ，即 2*8 = 16
    //---- p11 = mask|buckets -- 从x16（即isa）中平移16字节，取出cache 存入p11寄存器 -- isa距离cache 正好16字节：isa（8字节）-superClass（8字节）-cache（mask高16位 + buckets低48位）
    ldr p11, [x16, #CACHE]          // p11 = mask|buckets 或理解为 p11 = cache_t
    #if CONFIG_USE_PREOPT_CACHES
        #if __has_feature(ptrauth_calls)
    tbnz    p11, #0, LLookupPreopt\Function
    and p10, p11, #0x0000ffffffffffff   // p10 = buckets
        #else
    and p10, p11, #0x0000fffffffffffe   // p10 = buckets
    tbnz    p11, #0, LLookupPreopt\Function
        #endif
    eor p12, p1, p1, LSR #7
    and p12, p12, p11, LSR #48      // x12 = (_cmd ^ (_cmd >> 7)) & mask
    #else

//  p11 cache -> p10 = buckets
//  p11, LSR #48 -> mask
//  p1(_cmd) & mask = index -> p12
    //--- p11(cache) & 0x0000ffffffffffff ，mask高16位抹零，得到buckets 存入p10寄存器-- 即去掉mask，留下buckets
    and p10, p11, #0x0000ffffffffffff   // p10 = buckets
    //--- p11(cache)右移48位，得到mask（即p11 存储mask），mask & p1(msgSend的第二个参数 cmd-sel) ，得到sel-imp的下标index（即搜索下标） 存入p12（cache insert写入时的哈希下标计算是 通过 sel & mask，读取时也需要通过这种方式）
    and p12, p1, p11, LSR #48       // x12 = _cmd & mask

#endif // CONFIG_USE_PREOPT_CACHES
//--- 非64位真机
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
    ldr p11, [x16, #CACHE]              // p11 = mask|buckets
    and p10, p11, #~0xf         // p10 = buckets
    and p11, p11, #0xf          // p11 = maskShift
    mov p12, #0xffff
    lsr p11, p12, p11           // p11 = mask = 0xffff >> p11
    and p12, p1, p11            // x12 = _cmd & mask
#else
#error Unsupported cache mask storage for ARM64.
#endif

// objc - 源码调试 + 汇编
//  p11 cache -> p10 = buckets
//  p1(_cmd) & mask = index -> p12
//  (_cmd & mask) << 4  -> int 1 2 3 4 5   地址->int
//  buckets +  内存平移 (1 2 3 4)
//  b[i] -> b + i
//  p13 当前查找bucket
    add p13, p10, p12, LSL #(1+PTRSHIFT)
                        // p13 = buckets + ((_cmd & mask) << (1+PTRSHIFT))

                        // do {
//  *bucket--  p17, p9
//  bucket 里面的东西 imp (p17) sel (p9)
//  查到的 sel (p9) 和我们 say1
1:  ldp p17, p9, [x13], #-BUCKET_SIZE   //     {imp, sel} = *bucket--
    cmp p9, p1              //     if (sel != _cmd) {
    b.ne    3f              //         scan more
                        //     } else {
//--- 如果相等 即命中，直接返回imp
2:  CacheHit \Mode              // hit:    call or return imp
                        //     }
3:  cbz p9, \MissLabelDynamic       //     if (sel == 0) goto Miss;
    cmp p13, p10            // } while (bucket >= buckets)
//--- 跳转至第1步，继续对比 sel 与 cmd
    b.hs    1b

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
    add p13, p10, w11, UXTW #(1+PTRSHIFT)
                        // p13 = buckets + (mask << 1+PTRSHIFT)
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    add p13, p10, p11, LSR #(48 - (1+PTRSHIFT))
                        // p13 = buckets + (mask << 1+PTRSHIFT)
                        // see comment about maskZeroBits
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
    add p13, p10, p11, LSL #(1+PTRSHIFT)
                        // p13 = buckets + (mask << 1+PTRSHIFT)
#else
#error Unsupported cache mask storage for ARM64.
#endif
    add p12, p10, p12, LSL #(1+PTRSHIFT)
                        // p12 = first probed bucket

                        // do {
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

LLookupEnd\Function:
LLookupRecover\Function:
    b   \MissLabelDynamic

#if CONFIG_USE_PREOPT_CACHES
#if CACHE_MASK_STORAGE != CACHE_MASK_STORAGE_HIGH_16
#error config unsupported
#endif
LLookupPreopt\Function:
#if __has_feature(ptrauth_calls)
    and p10, p11, #0x007ffffffffffffe   // p10 = buckets
    autdb   x10, x16            // auth as early as possible
#endif

    // x12 = (_cmd - first_shared_cache_sel)
    adrp    x9, _MagicSelRef@PAGE
    ldr p9, [x9, _MagicSelRef@PAGEOFF]
    sub p12, p1, p9

    // w9  = ((_cmd - first_shared_cache_sel) >> hash_shift & hash_mask)
#if __has_feature(ptrauth_calls)
    // bits 63..60 of x11 are the number of bits in hash_mask
    // bits 59..55 of x11 is hash_shift

    lsr x17, x11, #55           // w17 = (hash_shift, ...)
    lsr w9, w12, w17            // >>= shift

    lsr x17, x11, #60           // w17 = mask_bits
    mov x11, #0x7fff
    lsr x11, x11, x17           // p11 = mask (0x7fff >> mask_bits)
    and x9, x9, x11         // &= mask
#else
    // bits 63..53 of x11 is hash_mask
    // bits 52..48 of x11 is hash_shift
    lsr x17, x11, #48           // w17 = (hash_shift, hash_mask)
    lsr w9, w12, w17            // >>= shift
    and x9, x9, x11, LSR #53        // &=  mask
#endif

    ldr x17, [x10, x9, LSL #3]      // x17 == sel_offs | (imp_offs << 32)
    cmp x12, w17, uxtw

.if \Mode == GETIMP
    b.ne    \MissLabelConstant      // cache miss
    sub x0, x16, x17, LSR #32       // imp = isa - imp_offs
    SignAsImp x0
    ret
.else
    b.ne    5f              // cache miss
    sub x17, x16, x17, LSR #32      // imp = isa - imp_offs
.if \Mode == NORMAL
    br  x17
.elseif \Mode == LOOKUP
    orr x16, x16, #3 // for instrumentation, note that we hit a constant cache
    SignAsImp x17
    ret
.else
.abort  unhandled mode \Mode
.endif

5:  ldursw  x9, [x10, #-8]          // offset -8 is the fallback offset
    add x16, x16, x9            // compute the fallback isa
    b   LLookupStart\Function       // lookup again with a new isa
.endif
#endif // CONFIG_USE_PREOPT_CACHES

.endmacro

上面汇编源码清楚的还原了objc_msgSend通过sel找到imp的过程。

上面步骤总结

• 判断当前接收者是否存在

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