在前面的文章中我們探索了objc_class中isa和bits，這次主要是分析objc_calss中的cache屬性

一 . cache_t 結(jié)構(gòu)探索

struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED//macOS斤吐、模擬器 -- 主要是架構(gòu)區(qū)分
    // explicit_atomic 顯示原子性，目的是為了能夠 保證 增刪改查時 線程的安全性
    //等價于 struct bucket_t * _buckets;
    //_buckets 中放的是 sel imp
    //_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位真機(jī)
    explicit_atomic<uintptr_t> _maskAndBuckets;//寫在一起的目的是為了優(yōu)化
    mask_t _mask_unused;
    
    //以下都是掩碼顽爹，即面具 -- 類似于isa的掩碼归苍，即位域
    // 掩碼省略....
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4 //非64位 真機(jī)
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;

    //以下都是掩碼只恨，即面具 -- 類似于isa的掩碼，即位域
    // 掩碼省略....
#else
#error Unknown cache mask storage type.
#endif
    
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;

    //方法省略.....
}

struct bucket_t {
private:
#if __arm64__ //真機(jī)
    //explicit_atomic 是加了原子性的保護(hù)
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else //非真機(jī)
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
    //方法等其他部分省略
}

從上面源碼可以看出cache_t主要存儲sel-imp
主要結(jié)構(gòu)如下圖

結(jié)構(gòu)圖

• _mask 掩碼(面具)用來獲取制定位數(shù)的數(shù)據(jù),如獲取isa中的代表對象信息的33位或者44位數(shù)據(jù)指針信息
• _flags 標(biāo)記
• _occupied占用位置個數(shù)

在第四篇文章,通過指針首地址偏移的方式,分析過bits的結(jié)構(gòu),現(xiàn)在用同樣的方式分析下cache_t的結(jié)構(gòu)

準(zhǔn)備一個類 并實現(xiàn)部分方法 main函數(shù)中調(diào)用斷點執(zhí)行

    Person *p = [[Person alloc] init];

    [p instanceMethod1];
    [p instanceMethod2];
    [p instanceMethod3];
    [p instanceMethod4];
    [p instanceMethod5];
    [p instanceMethod6];
    [p instanceMethod7];
    [p instanceMethod8];

在instanceMethod1之前打斷點卖子，通過lldb調(diào)試工具略号，查看p的類的內(nèi)存結(jié)構(gòu)

(lldb) x/4gx p.class
0x100002488: 0x0000000100002460 0x0000000100334140
0x100002498: 0x0000000100680ff0 0x0005801000000007

我們已知類的內(nèi)存布局，是以isa洋闽、superclass玄柠、cache_t、class_data_bits_t順序排布的诫舅，其中isa 與 superclass分別占用8個字節(jié)羽利，所以 cache_t的位置應(yīng)該是從類的首地址偏移16字節(jié)的位置，所以我們?nèi)?code>0x100002488 偏移 16字節(jié)刊懈，即 0x100002498的地址

(lldb) p (cache_t *)0x100002498
(cache_t *) $1 = 0x0000000100002498
(lldb) p *$1
(cache_t) $2 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x0000000100680ff0 {
      _sel = {
        std::__1::atomic<objc_selector *> = 0x00007fff75c3186
      }
      _imp = {
        std::__1::atomic<unsigned long> = 4047440
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 3
  }
  _flags = 32784
  _occupied = 1
}

其中 _buckets中存儲 sel的地址 和 編碼后的 imp这弧；_mask 為3，_occupied 為1（雖然 自定義的實例方法還沒有調(diào)用虚汛，但是 init方法已執(zhí)行匾浪，所以此處為1），我們繼續(xù)增加調(diào)用方法的數(shù)量卷哩，觀察_mask 與_occupied的取值蛋辈，

• _mask 3 3 7
• _occupied 1 2 1

為什么會發(fā)生這樣的變化的 我們進(jìn)行下面的探索

方法的存取

首先我們要找到存儲的源碼

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    // ...省略代碼 （錯誤處理相關(guān)代碼）
    
    // Use the cache as-is if until we exceed our expected fill ratio.
    mask_t newOccupied = occupied() + 1; //沒有屬性賦值的情況下 newOccupied  = 1 occupied = 0
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    if (slowpath(isConstantEmptyCache())) {//occupied = 0 創(chuàng)建緩存
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE;//初始化 capacity  = 4
        reallocate(oldCapacity, capacity, /* freeOld */false);//開辟空見
    }
    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.
//如果 <= 占用內(nèi)存的 3/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 { //如果超出了 3/4 兩倍擴(kuò)容 即 occupied = 2 的時候
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;//擴(kuò)容兩倍 
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);
    }

    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    mask_t begin = cache_hash(sel, m);//求cache哈希 通過哈希算法請求 sel下標(biāo)
    mask_t i = begin;

    // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot.
//如果存在哈希沖突  ,從沖突的下表開始遍歷 
    do {
//如果當(dāng)前遍歷的鞋標(biāo)都拿不到sel,即表示沒有存儲sel
        if (fastpath(b[i].sel() == 0)) {
//存儲sel   Occupied ++ 
            incrementOccupied();
            b[i].set<Atomic, Encoded>(b, sel, imp, cls());
            return;
        }
//如果當(dāng)前哈希下標(biāo)的sel == sel  直接返回
        if (b[i].sel() == sel) {
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
        }
//如果不相等  重新計算 拿到新的下標(biāo)
    } while (fastpath((i = cache_next(i, m)) != begin));

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

主要分為以下幾部分

【第一步】初始化緩存空間

• 當(dāng)屬性未賦值及無方法調(diào)用時，此時的occupied()為0将谊，而newOccupied為1
• init及方法賦值調(diào)用set方法 occupied也會+1

reallocate 創(chuàng)建新空間并釋放舊空間的函數(shù)

• 該方法冷溶，在第一次創(chuàng)建以及兩倍擴(kuò)容時寓搬，都會使用，其源碼實現(xiàn)

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 :向系統(tǒng)申請開辟內(nèi)存超营，即開辟bucket

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

cache_collect_free 釋放內(nèi)存空間 如果有舊的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)前擴(kuò)容后的capacity加入垃圾房的尺寸中应结，便于后續(xù)釋放。
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    // 將當(dāng)前新數(shù)據(jù)data存放到 garbage_count 后面 這樣可以釋放前面的泉唁，而保留后面的新值
    garbage_refs[garbage_count++] = data;
    // 不記錄之前的緩存 = 【清空之前的緩存】鹅龄。
    cache_collect(false);
}

【第二步】根據(jù)緩存占用量判斷執(zhí)行的操作

• 如果是第一次創(chuàng)建，則默認(rèn)開辟4個
• 如果緩存占用量小于等于3/4亭畜，則不作任何處理
• 如果緩存占用量超過3/4扮休，則需要進(jìn)行兩倍擴(kuò)容以及重新開辟空間

【第三步】針對需要存儲的bucket進(jìn)行內(nèi)部imp和sel賦值

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

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

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

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

• 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)行哈希計算，得到一個新的下標(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
}

小結(jié)：方法的緩存是以散列表的形式進(jìn)行存儲的，所以它是無序的，當(dāng) 當(dāng)前緩存數(shù)量 超過 散列表 總存儲空間的四分之三時形庭，散列表的存儲空間以2倍的原始大小進(jìn)行擴(kuò)容铅辞，并抹除已有緩存。存儲緩存時萨醒，是通過遍歷當(dāng)前散列表的所有已存儲方法斟珊，如果散列表中已有緩存，則不存儲并結(jié)束遍歷富纸，如果遍歷完畢依然沒有找到該方法囤踩，則將該方法存入散列表