oc-底層原理分析之Cache_t

在類的結(jié)構(gòu)分析一文中我們探索了類的底層定義，其中的屬性Cache_t我們并沒有深入研究蹭睡，這一篇文章我們來深入探索一下Cache_t

注意：以下的源碼解讀都是在mac電腦上運行衍菱，也就是說基于x86的結(jié)構(gòu)，請記住這一點

什么是Cache_t

要搞清楚什么是Cache_t和Cache_t用來做什么肩豁，我們先看看在objc源碼中脊串，Cache_t的定義

struct cache_t {
    explicit_atomic<struct bucket_t *> _buckets;
    explicit_atomic<mask_t> _mask;
    uint16_t _occupied;

public:
    static bucket_t *emptyBuckets();
    
    struct bucket_t *buckets();
    mask_t mask();
    mask_t occupied();
    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    void initializeToEmpty();
    //部分代碼已略
}

通過源碼我們看到Cache_t結(jié)構(gòu)體中定義了三個屬性：

_buckets
_mask
_occupied

但是我們現(xiàn)在并不知道這三個屬性用來做什么，要搞清楚這三個屬性的作用清钥，我們通過一個例子來探索一下

先定義一個WPerson類：

@interface WPerson : NSObject

@property (nonatomic, copy) NSString *lgName;
@property (nonatomic, strong) NSString *nickName;

- (void)sayHello;
- (void)sayCode;
- (void)sayMaster;
- (void)sayNB;
+ (void)sayHappy;
@end

@implementation WPerson
- (void)sayHello{
    NSLog(@"WPerson say : %s",__func__);
}

- (void)sayCode{
    NSLog(@"WPerson say : %s",__func__);
}

- (void)sayMaster{
    NSLog(@"WPerson say : %s",__func__);
}

- (void)sayNB{
    NSLog(@"WPerson say : %s",__func__);
}

+ (void)sayHappy{
    NSLog(@"WPerson say : %s",__func__);
}
@end

現(xiàn)在我們創(chuàng)建一個WPerson對象琼锋，然后調(diào)用sayHello方法：

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        WPerson *p  = [WPerson alloc];
        Class pClass = [WPerson class];
        [p sayHello];

        NSLog(@"%@",pClass);
    }
    return 0;
}

Cache_t 結(jié)構(gòu)探索

先找到pClass的首地址：

x/4gx pClass：以16進制形式打印出pClass地址

0x100002288: 0x0000000100002260 0x0000000100334140
0x100002298: 0x00000001006f4050 0x0001802400000003

pClass首地址為：0x100002288

通過在類結(jié)構(gòu)分析一文中我們得知了類的結(jié)構(gòu)如下：

struct objc_class : objc_object {
    // Class ISA;
    Class superclass;
    cache_t cache;             // formerly cache pointer and vtable
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags

    class_rw_t *data() const {
        return bits.data();
    }
}

由于isa和superclass都占用8個字節(jié)，所以我們要訪問到cache祟昭，我們需要將首地址偏移16字節(jié)缕坎，所以：

(lldb) p (cache_t *)0x100002298
(cache_t *) $1 = 0x0000000100002298

我們得到了cache的地址

訪問cache.buckets(),我們知道_buckets是一個數(shù)組，所以我們先訪問第一個值看存儲的是什么

(lldb) p $2.buckets()[0]
(bucket_t) $3 = {
_sel = {
std::__1::atomic<objc_selector *> = ""
}
_imp = {
std::__1::atomic<unsigned long> = 11912
}

}
```
我們得到一個bucket_t結(jié)構(gòu)篡悟，我們再看看bucket_t的源碼：

```c
struct bucket_t {
private:
    // IMP-first is better for arm64e ptrauth and no worse for arm64.
    // SEL-first is better for armv7* and i386 and x86_64.
#if __arm64__
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif

public:
    inline SEL sel() const { return _sel.load(memory_order::memory_order_relaxed); }

    inline IMP imp(Class cls) const {
        uintptr_t imp = _imp.load(memory_order::memory_order_relaxed);
        if (!imp) return nil;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
        SEL sel = _sel.load(memory_order::memory_order_relaxed);
        return (IMP)
            ptrauth_auth_and_resign((const void *)imp,
                                    ptrauth_key_process_dependent_code,
                                    modifierForSEL(sel, cls),
                                    ptrauth_key_function_pointer, 0);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
        return (IMP)(imp ^ (uintptr_t)cls);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
        return (IMP)imp;
#else
#error Unknown method cache IMP encoding.
#endif
    }

//部分代碼已略去
};
```
我們看到`bucket_t`有兩個屬性`_sel`和`_imp`谜叹，看到這里是不是很熟悉，但是別急搬葬，我們先來打印一下sel的值

打印sel

(lldb) p $3.sel()
(SEL) $4 = "sayHello"

我們看到結(jié)果打印出了我們剛剛調(diào)用的方法sayHello荷腊，我們?nèi)绻嗾{(diào)用幾個方法，這里可以打印出多個方法
所以我們得出結(jié)論：

cache_t用來緩存類的sel以及imp

既然我們知道了cache_t用來緩存類的方法踩萎，那么還有一些疑問：

緩存的策略是什么呢停局？
如果空間不足，如何對空間進行擴容香府？
緩存又是怎么讀取的董栽？（這部分內(nèi)容接下來會補上）

帶著這三個疑問，我們開始探索

cache_t緩存策略

我們先來看看insert()方法

ALWAYS_INLINE
void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{
#if CONFIG_USE_CACHE_LOCK
    cacheUpdateLock.assertLocked();
#else
    runtimeLock.assertLocked();
#endif

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

    // Use the cache as-is if it is less than 3/4 full
    mask_t newOccupied = occupied() + 1;
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE;
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) { // 4  3 + 1 bucket cache_t
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 擴容兩倍 4
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);  // 內(nèi)存 庫容完畢
}

從這里我們可以看到：

如果buckets還未初始化企孩，則會先調(diào)用reallocate()方法對buckets進行初始化锭碳，初始的存儲大小為INIT_CACHE_SIZE我們看到INIT_CACHE_SIZE定義為(1 << INIT_CACHE_SIZE_LOG2)也就是4
如果本次插入后所占用的空間小于總空間的3/4時，則直接進行數(shù)據(jù)插入
如果本次插入后所占用的空間>=3/4勿璃，則需要對總空間進行擴容擒抛，如何進行的擴容，在cache_t擴容部分會有講解

我們知道了在_buckets中存儲的是bucket_t類型补疑，當數(shù)據(jù)insert的時候歧沪，都會創(chuàng)建一個bucket_t變量

mask

_buckets是一個數(shù)組，如果我們要通過某個方法的sel去查找imp莲组，我們怎么查找呢诊胞？我們大概率會想去去遍歷_buckets，但是這樣的效率是低下的锹杈，每一次的方法查找都會遍歷整個緩存撵孤，那么有沒有什么辦法能不遍歷呢迈着？

我們來看看源碼中采用的方式，我們在源碼中能看到這樣一個方法：

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;
}

mask傳入的是mask_t m = capacity - 1;也就是當前的容量 - 1邪码。通過和mask相與裕菠，我們得到的數(shù)字肯定是小于等于mask的，通過這種方式就可以得到sel和數(shù)組index的對應(yīng)關(guān)系闭专，在查找的時候就可以直接通過sel得到數(shù)組對應(yīng)的index奴潘，不再需要遍歷整個數(shù)組

但是你可能有一個疑問，這樣不會出現(xiàn)編碼的沖突嗎喻圃？不同的sel會不會得到同一個index呢萤彩？答案是會的，源碼中也解決了這個問題

bucket_t *b = buckets();
mask_t m = capacity - 1;
mask_t begin = cache_hash(sel, m);
mask_t i = begin;
    
do {
    if (fastpath(b[i].sel() == 0)) {
        incrementOccupied();
        b[i].set<Atomic, Encoded>(sel, imp, cls);
        return;
    }
    if (b[i].sel() == sel) {
        // The entry was added to the cache by some other thread
        // before we grabbed the cacheUpdateLock.
        return;
    }
} while (fastpath((i = cache_next(i, m)) != begin));

如果index存在了斧拍，就會調(diào)用cache_next重新生成一個index來存儲雀扶，直到找到合適的位置

cache_t擴容

capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 擴容兩倍
if (capacity > MAX_CACHE_SIZE) {
    capacity = MAX_CACHE_SIZE;
}
reallocate(oldCapacity, capacity, true);  // 內(nèi)存 庫容完畢

我們可以看到擴容的原則是當前容量的兩倍，并且擴容時肆汹，重新調(diào)用reallocate將原來的數(shù)據(jù)清空愚墓。也就是說擴容后，原來的數(shù)據(jù)將不存在昂勉，重新調(diào)用原有方法的時候才會重新進行緩存浪册，如果你這時候去打印cache中的所有數(shù)據(jù)，得到的并不是你當前調(diào)用的所有方法岗照，也能得到驗證