在OC底層原理05 - isa與類關(guān)聯(lián)的原理和OC底層原理06 - 類 & 類結(jié)構(gòu)分析中，分析了objc_class中isa和bits刽沾，這篇文章主要是分析objc_calss中的cache屬性

cache初探

• 打開objc4源碼， 搜索objc_class
  image.png
• 查看cache_t源碼侧漓，發(fā)現(xiàn)分成了3個架構(gòu)的處理监氢，其中真機的架構(gòu)中布蔗，mask和bucket是寫在一起浪腐，目的是為了優(yōu)化，可以通過各自的掩碼來獲取相應(yīng)的數(shù)據(jù)
  • CACHE_MASK_STORAGE_OUTLINED表示運行的環(huán)境為模擬器或macOS
  • CACHE_MASK_STORAGE_HIGH_16表示運行環(huán)境為64位真機
  • CACHE_MASK_STORAGE_LOW_4表示運行環(huán)境為非64位真機

struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED    // macOS议街、模擬器
    // explicit_atomic 顯示原子性，目的是為了能夠 保證 增刪改查時 線程的安全性
    // 等價于 struct bucket_t * _buckets;
    // _buckets的讀取 有提供相應(yīng)名稱的方法 buckets()
    explicit_atomic<struct bucket_t *> _buckets;
    explicit_atomic<mask_t> _mask;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16  // 64位真機
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;

    // 掩碼代碼省略...    

#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4  // //非64位 真機
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;

    // 掩碼代碼省略...
#else
#error Unknown cache mask storage type.
#endif
    
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;

    // 部分代碼省略.....
};

• 查看bucket_t源碼傍睹，同樣分為兩個版本犹菱，真機和非真機拾稳，不同的區(qū)別在于sel和imp的順序不同

struct bucket_t {
private:
#if __arm64__
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif

  // 部分代碼省略.....
};

所以通過上面兩個結(jié)構(gòu)體源碼可知腊脱，cache中緩存的是sel-imp

cache_t緩存機制

cache_t中查找存儲的sel-imp，有以下兩種方式

在源碼中查找

• 定義一個HLPerson類，并添加屬性及方法悍抑，如下

@interface HLPerson : NSObject

@property (nonatomic, copy) NSString *name;
@property (nonatomic, copy) NSString *nickName;

- (void)instanceMethod1;
- (void)instanceMethod2;
- (void)instanceMethod3;
- (void)instanceMethod4;
- (void)instanceMethod5;
+ (void)classMethod;

@end

//.m
@implementation HLPerson

- (void)instanceMethod1 {
    NSLog(@"%s",__func__);
}
- (void)instanceMethod2 {
    NSLog(@"%s",__func__);
}
- (void)instanceMethod3 {
    NSLog(@"%s",__func__);
}
- (void)instanceMethod4 {
    NSLog(@"%s",__func__);
}
- (void)instanceMethod5 {
    NSLog(@"%s",__func__);
}

+ (void)classMethod {
    NSLog(@"%s",__func__);
}

@end

• 在main中定義HLPerson類的對象person，并調(diào)用其中的3個實例方法拂盯，在person調(diào)用第一個方法處添加斷點，運行代碼
  image.png
• 程序運行至斷點處谈竿，lldb調(diào)試
  image.png
  從lldb打印結(jié)果來看，sel空凸、imp、mask呀洲、occupied等值出現(xiàn)了變化，由上圖可知道逗，在沒有執(zhí)行方法調(diào)用時，此時的cache是沒有緩存的憔辫，執(zhí)行了一次方法調(diào)用，cache中就有了一個緩存贰您，即調(diào)用一次方法就會緩存一次方法。
  【驗證】使用machoView打開target的可執(zhí)行文件拢操，在方法列表中查看其imp的值是否是一致的，如下所示令境，發(fā)現(xiàn)是一致的，所以打印的這個sel-imp就是HLPerson的實例方法
  
  image.png
• 點擊step over舔庶，程序再執(zhí)行一步，此時-[HLPerson instanceMethod2]已經(jīng)執(zhí)行惕橙，我們再看下此時cache的情況
  
  image.png
  
  發(fā)現(xiàn)獲取到的buckets中sel和之前是相同的，此時想要獲取第二個sel弥鹦，應(yīng)該通過指針平移獲取
  
  image.png
  
  這樣雖然也能獲取到數(shù)據(jù)，但是操作過程略顯繁瑣，所以我們換一種方式凡是進(jìn)行探索

脫離源碼環(huán)境

脫離源碼環(huán)境膝晾，就是將所需的源碼的部分拷貝至項目中，其完整代碼如下

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

struct hl_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct hl_cache_t {
    struct hl_bucket_t * _buckets;
    mask_t _mask;
    uint16_t _flags;
    uint16_t _occupied;
};

struct hl_class_data_bits_t {
    uintptr_t bits;
};

struct hl_objc_class {
    Class ISA;
    Class superclass;
    struct hl_cache_t cache;             // formerly cache pointer and vtable
    struct hl_class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
};

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        HLPerson *person  = [HLPerson alloc];
        Class pClass = [HLPerson class];  
        [person instanceMethod1];
        [person instanceMethod2];
        [person instanceMethod3];
        [person instanceMethod4];
      
        struct hl_objc_class *hl_pClass = (__bridge struct hl_objc_class *)(pClass);
        NSLog(@"%hu - %u", hl_pClass->cache._occupied, hl_pClass->cache._mask);
        for (mask_t i = 0; i<hl_pClass->cache._mask; i++) {
            // 打印獲取的 bucket
            struct hl_bucket_t bucket = hl_pClass->cache._buckets[i];
            NSLog(@"%@ - %p", NSStringFromSelector(bucket._sel), bucket._imp);
        }
    }
    return 0;
}

運行項目血当，結(jié)果如下

image.png

• 1歹颓、_mask是什么油湖？
• 2、_occupied是什么乏德？
• 3撤奸、_occupied和_mask隨什么變化喊括？
• 4、_bucket數(shù)據(jù)為什么會有丟失的情況郑什？
• 5、方法存儲順序是順序存儲還是有別的規(guī)則蘑拯？

帶著上述的這些疑問，下面來進(jìn)行cache底層原理的探索

cache_t底層原理分析

• 首先申窘，從cache_t中的_mask屬性開始分析，找cache_t中引起變化的函數(shù)剃法，發(fā)現(xiàn)了incrementOccupied()函數(shù)
  
  image.png
  跳轉(zhuǎn)至incrementOccupied()
  image.png
• 在源碼中全局搜索incrementOccupied()函數(shù)，發(fā)現(xiàn)只在cache_t的insert方法有調(diào)用
  
  image.png
• insert方法贷洲，理解為cache_t的插入，而cache中存儲的就是sel-imp优构，所以cache的原理從insert方法開始分析，以下是cache原理分析的流程圖
  
  image.png
• 全局搜索->insert方法俩块，發(fā)現(xiàn)只有cache_fill方法中的調(diào)用符合
  
  image.png
• 全局搜索cache_fill，發(fā)現(xiàn)在寫入之前玉凯，還有一步操作，即cache讀取漫仆，即查找sel-imp，如下所示
  
  image.png
  可以看到在cache寫入流程前有一個讀取流程盲厌，讀取流程將在下篇文章中分析探討，本文還是回到insert寫入上

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

    // 原occupied計數(shù)+1
    mask_t newOccupied = occupied() + 1;
    // 進(jìn)入capacity()查看： return mask() ? mask()+1 : 0;
    // 就是當(dāng)前mask有值就+1吗浩，否則設(shè)置初始值0
    unsigned oldCapacity = capacity(), capacity = oldCapacity;

    // 當(dāng)前緩存是否為空
    if (slowpath(isConstantEmptyCache())) {
        // Cache 是只讀的，所以只能替換而不能修改
        // 如果為空懂扼，就給空間設(shè)置初始值4(進(jìn)入INIT_CACHE_SIZE查看，可以發(fā)現(xiàn)就是1<<2阀湿，就是二進(jìn)制100，十進(jìn)制為4)
        if (!capacity) capacity = INIT_CACHE_SIZE;

        // 創(chuàng)建新空間（第三個入?yún)閒alse陷嘴，表示不需要釋放舊空間）
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }

    // CACHE_END_MARKER 就是 1
    // 如果當(dāng)前計數(shù) + 1 <= 空間的 3/4，表示空間夠用灾挨，不需要空間擴容邑退，不作處理
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) {
        // Cache is less than 3/4 full. Use it as-is.
    }

    // 如果計數(shù)大于3/4涨醋， 就需要進(jìn)行擴容操作
    else {
        // 如果空間存在瓜饥，就2倍擴容浴骂。 如果不存在乓土，就設(shè)為初始值4
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;

        // 防止超出最大空間值（2^16 - 1）
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }

        // 創(chuàng)建新空間（第三個入?yún)閠rue溯警，表示需要釋放舊空間）
        reallocate(oldCapacity, capacity, true);
    }

    // 讀取現(xiàn)在的buckets數(shù)組
    bucket_t *b = buckets();
    // 新的mask值(當(dāng)前空間最大存儲大小 - 1)
    mask_t m = capacity - 1;
    // 使用hash計算當(dāng)前函數(shù)的位置(內(nèi)部就是sel & m， 就是取余操作梯轻，保障begin值在m當(dāng)前可用空間內(nèi))
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;

    do {
        // 如果當(dāng)前位置為空，直接寫入存儲
        if (fastpath(b[i].sel() == 0)) {
            // Occupied計數(shù)+1
            incrementOccupied();
            // 將sel和imp與cls關(guān)聯(lián)起來并寫入內(nèi)存中
            b[i].set<Atomic, Encoded>(sel, imp, cls);
            return;
        }
        // 如果當(dāng)前位置有值喳挑，且儲存sel為當(dāng)前sel滔悉，直接返回
        if (b[i].sel() == sel) {
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
        }

        // 程序運行到這步，代表位置有值单绑，且儲存sel不是當(dāng)前sel，那么再次使用哈希算法找下一個空位置去寫入
        // 需要注意的是搂橙，cache_next內(nèi)部有分支： 
        // 如果是arm64真機環(huán)境： 從最大空間位置開始，依次-1往回找空位
        // 如果是arm舊版真機区转、x86_64電腦、i386模擬器： 從當(dāng)前位置開始废离，依次+1往后找空位。不能超過最大空間厅缺。
        // 因為當(dāng)前空間是沒超出mask最大空間的蔬顾，所以一定有空位置可以放置的湘捎。
    } while (fastpath((i = cache_next(i, m)) != begin));

    // 各種錯誤處理
    cache_t::bad_cache(receiver, (SEL)sel, cls);
}

• 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__
#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)行哈希計算窥妇，得到一個新的下標(biāo)
}

#elif __arm64__
#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
}

reallocate方法分析

該方法拉宗，在第一次創(chuàng)建以及兩倍擴容時峦树，都會調(diào)用，其作用為開辟新空間魁巩，釋放舊空間，源碼實現(xiàn)如下

ALWAYS_INLINE
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    // 讀取舊buckets數(shù)組
    bucket_t *oldBuckets = buckets();
    // 創(chuàng)建新空間大小的buckets數(shù)組
    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

    // 新空間必須大于0
    ASSERT(newCapacity > 0);

    // 新空間-1 轉(zhuǎn)為mask_t類型谷遂，再與新空間-1 進(jìn)行判斷
    ASSERT((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);

    // 設(shè)置新的bucktes數(shù)組和mask
    // 【重點】我們發(fā)現(xiàn)mask就是newCapacity - 1, 表示當(dāng)前最大可存儲空間
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    // 釋放舊內(nèi)存空間
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
    }
}

allocateBuckets方法分析

其作用為創(chuàng)建新空間大小的buckets數(shù)組卖鲤，此時的buckets是一個臨時變量肾扰，源碼如下

bucket_t *allocateBuckets(mask_t newCapacity)
{
    // 創(chuàng)建1個bucket
    bucket_t *newBuckets = (bucket_t *)
        calloc(cache_t::bytesForCapacity(newCapacity), 1);
    // 將創(chuàng)建的bucket放到當(dāng)前空間的最尾部，標(biāo)記數(shù)組的結(jié)束
    bucket_t *end = cache_t::endMarker(newBuckets, newCapacity);

#if __arm__
    // End marker's sel is 1 and imp points BEFORE the first bucket.
    // This saves an instruction in objc_msgSend.
    end->set<NotAtomic, Raw>((SEL)(uintptr_t)1, (IMP)(newBuckets - 1), nil);
#else
    // 將結(jié)束標(biāo)記為sel為1集晚，imp為這個buckets
    end->set<NotAtomic, Raw>((SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
   
     // 只是打印記錄
    if (PrintCaches) recordNewCache(newCapacity);

    // 返回這個bucket
    return newBuckets;
}

setBucketsAndMask方法分析

將臨時的bucket存入緩存中

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    // 如果是macOS或者模擬器環(huán)境，分開存儲 bucket_t 和 mask_t
    // 將 _occupied 置為 0
#ifdef __arm__
    mega_barrier();
    _buckets.store(newBuckets, memory_order::memory_order_relaxed);    
    mega_barrier();
    _mask.store(newMask, memory_order::memory_order_relaxed);
    _occupied = 0;
#elif __x86_64__ || i386
    _buckets.store(newBuckets, memory_order::memory_order_release);
    _mask.store(newMask, memory_order::memory_order_release);
    _occupied = 0;
#else
#error Don't know how to do setBucketsAndMask on this architecture.
#endif
}

#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    // 創(chuàng)建兩個臨時變量存儲 newBuckets 和 newMask
    uintptr_t buckets = (uintptr_t)newBuckets;
    uintptr_t mask = (uintptr_t)newMask;
    
    // 判斷所要存儲的數(shù)據(jù)是否小于最大值
    ASSERT(buckets <= bucketsMask);
    ASSERT(mask <= maxMask);
    
    // static constexpr uintptr_t maskShift = 48;
    // 將 newMask 存儲在 高48位甩恼，newBuckets 存儲在 低16位
    _maskAndBuckets.store(((uintptr_t)newMask << maskShift) | (uintptr_t)newBuckets, std::memory_order_relaxed);

    // 將 _occupied 置為 0
    _occupied = 0;
}

cache_collect_free方法分析

如果有舊的buckets沉颂，需要清理之前的緩存，即調(diào)用cache_collect_free方法铸屉，其源碼實現(xiàn)如下

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

    if (PrintCaches) recordDeadCache(capacity);
    
    // 垃圾房： 開辟空間 （如果首次，就開辟初始空間彻坛，如果不是，就空間*2進(jìn)行拓展）
    _garbage_make_room ();
    // 將當(dāng)前擴容后的capacity加入垃圾房的尺寸中昌屉，便于后續(xù)釋放钙蒙。
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    // 將當(dāng)前新數(shù)據(jù)data存放到 garbage_count 后面 這樣可以釋放前面的间驮，而保留后面的新值
    garbage_refs[garbage_count++] = data;
    // 不記錄之前的緩存 = 【清空之前的緩存】。
    cache_collect(false);
}

至此竞帽，cache_t的原理基本分析完成了扛施，至于前文提及的幾個問題屹篓，我們現(xiàn)在也有答案

疑問解答

1、_mask是什么堆巧？
_mask是指掩碼數(shù)據(jù)，用于在哈希算法或者哈希沖突算法中計算哈希下標(biāo)恳邀，_mask等于capacity - 1
2懦冰、_occupied是什么谣沸？

• _occupied表示哈希表中sel-imp的占用大小 (即可以理解為分配的內(nèi)存中已經(jīng)存儲的sel-imp的個數(shù))刷钢，
• init會導(dǎo)致_occupied變化
• 屬性賦值乳附，也會隱式調(diào)用伴澄，導(dǎo)致_occupied變化
• 方法調(diào)用，導(dǎo)致_occupied變化

3非凌、_occupied和_mask隨什么變化？
_occupied為當(dāng)前緩存的方法個數(shù)荆针，_mask等于總?cè)萘?1。當(dāng)調(diào)用一個未緩存的方式時_occupied + 1航背，如果新的_occupied再+1不小于總?cè)萘?/code>的3/4時，例如總?cè)萘繛?code>4玖媚，調(diào)用第3個未緩存方法時箕肃，總?cè)萘繛?code>8，調(diào)用第6個未緩存方法時勺像，就需要對cache的內(nèi)存進(jìn)行兩倍擴容，此時_mask被重新賦值吟宦，_occupied重置為0
4、_bucket數(shù)據(jù)為什么會有丟失的情況
在擴容時督函，是將原有的內(nèi)存全部清除了，再重新申請了內(nèi)存導(dǎo)致的
5激挪、方法存儲順序是順序存儲還是有別的規(guī)則？
因為sel-imp的存儲是通過哈希算法計算下標(biāo)的垄分，其計算的下標(biāo)有可能已經(jīng)存儲了sel，所以又需要通過哈希沖突算法重新計算哈希下標(biāo)薄湿，所以導(dǎo)致下標(biāo)是隨機的叫倍，并不是固定的