在之前的文章中分析了objc_class中isa和bits，這次分析的是objc_class中的cache屬性，cache緩存_sel和_imp.在真機(jī)架構(gòu)中mask和bucket寫在一起，目的是為了優(yōu)化，通過各自的的掩碼來獲取相應(yīng)數(shù)據(jù)。

cache.png

查看cache_t源碼，分成3個(gè)架構(gòu)處理分別是

• CACHE_MASK_STORAGE_OUTLINED 運(yùn)行環(huán)境是模擬機(jī)和masOS
• CACHE_MASK_STORAGE_HIGH_16 運(yùn)行環(huán)境是64位的真機(jī)
• CACHE_MASK_STORAGE_LOW_4 運(yùn)行環(huán)境非64位的真機(jī)

struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    explicit_atomic<struct bucket_t *> _buckets;
    explicit_atomic<mask_t> _mask;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;
    
    // How much the mask is shifted by.
    static constexpr uintptr_t maskShift = 48;
    
    // Additional bits after the mask which must be zero. msgSend
    // takes advantage of these additional bits to construct the value
    // `mask << 4` from `_maskAndBuckets` in a single instruction.
    static constexpr uintptr_t maskZeroBits = 4;
    
    // The largest mask value we can store.
    static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
    
    // The mask applied to `_maskAndBuckets` to retrieve the buckets pointer.
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
    
    // Ensure we have enough bits for the buckets pointer.
    static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS, "Bucket field doesn't have enough bits for arbitrary pointers.");
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
    // _maskAndBuckets stores the mask shift in the low 4 bits, and
    // the buckets pointer in the remainder of the value. The mask
    // shift is the value where (0xffff >> shift) produces the correct
    // mask. This is equal to 16 - log2(cache_size).
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;

    static constexpr uintptr_t maskBits = 4;
    static constexpr uintptr_t maskMask = (1 << maskBits) - 1;
    static constexpr uintptr_t bucketsMask = ~maskMask;
#else
#error Unknown cache mask storage type.
#endif

查看bucket_t的源碼，分為真機(jī)和非真機(jī)，卻就是_sel和_imp的位置不同

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

cache中查找sel-imp

cache_t 查找sel-imp，有兩種方式：

• 通過源碼查找
• 脫離源碼項(xiàng)目中查找

源碼查找sel-imp

• 定義一個(gè)LGPerson類，定義屬性和實(shí)例方法以及類方法

//.h文件
@interface LGPerson : NSObject
@property (nonatomic, copy) NSString *lgName;
@property (nonatomic, strong) NSString *nickName;

- (void)sayHello;

- (void)sayCode;

- (void)sayMaster;

- (void)sayNB;

+ (void)sayHappy;

@end

//.m文件
@implementation LGPerson
- (void)sayHello{
    NSLog(@"LGPerson say : %s",__func__);
}

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

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

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

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

• 在main函數(shù)定義的[p sayHello];打一個(gè)斷點(diǎn)，通過lldb命令調(diào)試流程,打印cache信息
  

  cache信息

• 在main函數(shù)定義的[p sayMaster];打一個(gè)斷點(diǎn)，通過lldb命令調(diào)試流程
  

  cache信息
  
  

• 從圖中可以看出，cache屬性的獲取需要平移16位

• sel-imp是cache_t的_buckets屬性中（目前處于masOS環(huán)境），cache_t結(jié)構(gòu)體中提供了獲取_buckets屬性的方法buckets()

• 通過 cache_t結(jié)構(gòu)體提供的sel()和imp (cls)方法在_buckets屬性中獲取對(duì)應(yīng)的數(shù)據(jù)

通過上圖可知，沒有調(diào)用方法的時(shí)候，cache是沒有緩存的，調(diào)用了方法，cache中就有緩存即調(diào)用一次方法就會(huì)緩存一次

這里我們了解了如何打印sel-imp，但是我們還需要驗(yàn)證打印的信息是否正確
通過machoView打開可執(zhí)行文件，在Function stars中查看imp，發(fā)現(xiàn)信息是一致的。

• 接著我們進(jìn)行打印第二個(gè)sel，lldb命令流程

  
  
  獲取第二個(gè)sel-imp

第一個(gè)方法打印非常方便，但是第二個(gè)sel-imp就涉及到偏移的知識(shí)，可以IOS- 底層原理-類結(jié)構(gòu)分析中提及多指針偏移，這里通過_buckets屬性的首地址偏移即 p *($3+1)即可獲取第二個(gè)方法的sel 和imp

脫離源碼通過項(xiàng)目查找

重新創(chuàng)建一個(gè)沒有源碼的項(xiàng)目，講源碼中需要的cache相關(guān)的結(jié)構(gòu)體，內(nèi)容復(fù)制過來并修改名字。

typedef uint32_t mask_t;  // x86_64 & arm64 asm are less efficient with 16-bits

struct lg_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct lg_cache_t {
    struct lg_bucket_t * _buckets;
    mask_t _mask;
    uint16_t _flags;
    uint16_t _occupied;
};

struct lg_class_data_bits_t {
    uintptr_t bits;
};

struct lg_objc_class {
    Class ISA;
    Class superclass;
    struct lg_cache_t cache;             // formerly cache pointer and vtable
    struct lg_class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
};

LGPerson類中多定義幾個(gè)方法，在main函數(shù)中調(diào)用

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        LGPerson *p  = [LGPerson alloc];
        Class pClass = [LGPerson class];  // objc_clas
        [p say1];
        [p say2];
        [p say3];
        [p say4];
         
        // _occupied  _mask 是什么  cup - 1
        // 會(huì)變化 2-3 -> 2-7
        // bucket 會(huì)有丟失  重新申請(qǐng)
        // 順序有點(diǎn)問題  哈希
        
        // cache_t 底層原理
        // 線索 :
        
        struct lg_objc_class *lg_pClass = (__bridge struct lg_objc_class *)(pClass);
        NSLog(@"%hu - %u",lg_pClass->cache._occupied,lg_pClass->cache._mask);
        for (mask_t i = 0; i<lg_pClass->cache._mask; i++) {
            // 打印獲取的 bucket
            struct lg_bucket_t bucket = lg_pClass->cache._buckets[i];
            NSLog(@"%@ - %p",NSStringFromSelector(bucket._sel),bucket._imp);
        }

        
        NSLog(@"Hello, World!");
    }
    return 0;
}

這里就有一個(gè)問題需要注意，就是objc_class的ISA是繼承自objc_object,但是我們?cè)诳截愡^來的時(shí)候，去掉了objc_class繼承關(guān)系，現(xiàn)在需要將這個(gè)屬性明確，否則會(huì)出現(xiàn)下面的現(xiàn)象

如果將ISA加上就顯示正常了

針對(duì)打印的結(jié)果，我們有幾個(gè)疑惑

• _mask和_occupied是什么？
• bucket數(shù)據(jù)為什么會(huì)丟失，并且為什么打印亂序？
• cache_t中的_ocupied為什么是從2開始？
• 為什么隨著方法調(diào)用的增多，其打印的occupied 和 mask會(huì)變化

帶著上述的疑問，進(jìn)行cache底層探索

• 在cache_t_中的_mask屬性開始分析，找cache_t中引起變化的函數(shù)，發(fā)現(xiàn)了incrementOccupied()函數(shù)
  

• incrementOccupied()的具體實(shí)現(xiàn)
  

搜索incrementOccupied()查找源碼，此時(shí)只有cache_t::insert調(diào)用了這個(gè)方法

• insert方法可以理解為cache_t的插入，cache存儲(chǔ)的就是sel-imp，因此從insert進(jìn)行分析，下面是insert流程圖
  
  insert流程.png

全局搜索insert(),發(fā)現(xiàn)cache_fill符合條件調(diào)用

insert分析

源碼實(shí)現(xiàn)如下

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;  // 擴(kuò)容兩倍 4
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);  // 內(nèi)存 庫(kù)容完畢
    }

    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    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 because the
    // minimum size is 4 and we resized at 3/4 full.
    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));

    cache_t::bad_cache(receiver, (SEL)sel, cls);
}

首先根據(jù)occupied的值計(jì)算出當(dāng)前緩存占用量，當(dāng)屬性沒有調(diào)用方法，occupied()為0，newOccupied為1

 mask_t newOccupied = occupied() + 1;

關(guān)于緩存占用計(jì)算，需要說明的是：

• 使用alloc申請(qǐng)空間，此時(shí)他就是一個(gè)對(duì)象，如果再調(diào)用init，也是會(huì)加入緩存那么occupied +1
• 調(diào)用方法時(shí)，也是會(huì)加入緩存即occupied增加，在原基礎(chǔ)上增加
• 對(duì)象屬性賦值是，會(huì)隱式調(diào)用set方法，occupied也會(huì)增加，在原基礎(chǔ)上增加

緩存占用量判斷

• 第一次創(chuàng)建，默認(rèn)開辟4個(gè)

 if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE;
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }

• 如果緩存占用小于等于3/4，將不做處理

 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.
    }

• 如果緩存占用大于3/4，會(huì)進(jìn)行兩倍擴(kuò)容以及重新開辟空間

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

allocateBuckets 開辟空間

該方法，在第一次創(chuàng)建以及兩倍擴(kuò)容時(shí)，都會(huì)使用，其源碼實(shí)現(xiàn)如下

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    bucket_t *oldBuckets = buckets();
    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);

    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
    }
}

• allocateBuckets方法：向系統(tǒng)申請(qǐng)開辟內(nèi)存，即開辟bucket，此時(shí)的bucket只是一個(gè)臨時(shí)變量
• setBucketsAndMask方法：將臨時(shí)的bucket存入緩存中，此時(shí)的存儲(chǔ)分為兩種情況：
  • 如果是真機(jī)，根據(jù)bucket和mask的位置存儲(chǔ)，并將occupied占用設(shè)置為0
  • 如果不是真機(jī)，正常存儲(chǔ)bucket和mask，并將occupied占用設(shè)置為0
• 如果有舊的buckets，需要清理之前的緩存，即調(diào)用cache_collect_free方法，其源碼實(shí)現(xiàn)如下

  _garbage_make_room ();
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    garbage_refs[garbage_count++] = data;
    cache_collect(false);

 *  _garbage_make_room方法：創(chuàng)建垃圾回收空間

• 如果是第一次，需要分配回收空間
• 如果不是第一次，則將內(nèi)存段加大，即原有內(nèi)存*2
• cache_collect方法：垃圾回收，清理舊的bucket

bucket進(jìn)行內(nèi)部imp和sel賦值

這部分主要是根據(jù)cache_hash方法，即哈希算法 ，計(jì)算sel-imp存儲(chǔ)的哈希下標(biāo)，分為以下三種情況：

• 如果哈希下標(biāo)的位置未存儲(chǔ)sel，即該下標(biāo)位置獲取sel等于0，此時(shí)將sel-imp存儲(chǔ)進(jìn)去，并將occupied占用大小加1

• 如果當(dāng)前哈希下標(biāo)存儲(chǔ)的sel 等于 即將插入的sel，則直接返回

• 如果當(dāng)前哈希下標(biāo)存儲(chǔ)的sel 不等于 即將插入的sel，則重新經(jīng)過cache_next方法 即哈希沖突算法，重新進(jìn)行哈希計(jì)算，得到新的下標(biāo)，再去對(duì)比進(jìn)行存儲(chǔ)

涉及的兩種哈希算法，其源碼如下

• cache_hash：哈希算法

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask; // 通過sel & mask（mask = cap -1）
}

• cache_next：哈希沖突算法

#if __arm__  ||  __x86_64__  ||  __i386__
// objc_msgSend has few registers available.
// Cache scan increments and wraps at special end-marking bucket.
#define CACHE_END_MARKER 1
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask; //（將當(dāng)前的哈希下標(biāo) +1） & mask，重新進(jìn)行哈希計(jì)算，得到一個(gè)新的下標(biāo)
}

#elif __arm64__
// objc_msgSend has lots of registers available.
// Cache scan decrements. No end marker needed.
#define CACHE_END_MARKER 0
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
}

到這里cache_t的源碼就分析完畢了

疑問解答

1 _mask和_occupied是什么？

• _mask是指掩碼數(shù)據(jù)，用于在哈希算法或者哈希沖突算法中計(jì)算哈希下標(biāo)，其中mask 等于capacity - 1。
• _occupied：哈希表中 sel-imp 的占用大小
  2 bucket數(shù)據(jù)為什么會(huì)丟失，并且為什么打印亂序？
  數(shù)據(jù)丟失：原因是在擴(kuò)容時(shí)，是將原有的內(nèi)存全部清除了，再重新申請(qǐng)了內(nèi)存導(dǎo)致的。
  亂序：sel-imp的存儲(chǔ)是通過哈希算法計(jì)算下標(biāo)的，其計(jì)算的下標(biāo)有可能已經(jīng)存儲(chǔ)了sel，所以又需要通過哈希沖突算法重新計(jì)算哈希下標(biāo)，所以導(dǎo)致下標(biāo)是隨機(jī)的，并不是固定的。
  3 cache_t中的_ocupied為什么是從2開始？
  4 為什么隨著方法調(diào)用的增多，其打印的occupied 和 mask會(huì)變化
  因?yàn)?code>LGPerson通過alloc創(chuàng)建的對(duì)象，并對(duì)其兩個(gè)屬性賦值的原因，會(huì)隱式調(diào)用set方法，set方法的調(diào)用也會(huì)導(dǎo)致occupied變化