iOS 底層探索： 學(xué)習(xí)大綱 OC篇

前言

• 這篇主要內(nèi)容是分析cache_t流程。之前分析了objc_class中的bits探尋的類的內(nèi)存結(jié)構(gòu)麸塞，在oc語(yǔ)言中，對(duì)象調(diào)用方法之后袭蝗，這個(gè)方法是會(huì)被緩存起來(lái)的。下次再調(diào)用這個(gè)方法的時(shí)候般婆，直接從緩存里面去找到腥，而不用再去遍歷從類到父類再到祖宗類的方法列表了。本文就是從源碼分析這個(gè)方法緩存的功能流程蔚袍；
• 分析環(huán)境：arm64 構(gòu)架乡范，iPhone 真機(jī) 編譯環(huán)境下。

準(zhǔn)備工作

• 復(fù)習(xí)：iOS底層探索： 類的結(jié)構(gòu)分析
• 先學(xué)習(xí)幾個(gè)重要的單詞以便于理解源碼：

• 回憶SDWebImage緩存策略

  
  
  SDWebImage實(shí)現(xiàn)流程

• 大腦中是否已經(jīng)有了緩存實(shí)現(xiàn)思路了呢瓶佳？大致思路：1.先去緩存找，2.找不到就創(chuàng)建鳞青，3.創(chuàng)建成功再去緩存霸饲，然后返回結(jié)束。

我們接下來(lái)看看apple的工程師是如何在底層做方法的緩存的臂拓。

一 厚脉、源碼中簡(jiǎn)單查看cache_t 大致結(jié)構(gòu)和定義

結(jié)構(gòu)體objc_class中

Class是指向objc_class的指針，objc_class內(nèi)部存在一個(gè)cache_t cache胶惰；cache就是用來(lái)緩存最近調(diào)用過(guò)的方法的傻工。

結(jié)構(gòu)體cache_t中

• _buckets：數(shù)組，是bucket_t結(jié)構(gòu)體的數(shù)組，bucket_t是用來(lái)存放方法的SEL內(nèi)存地址和IMP的;
• _mask的大小是數(shù)組大小 - 1中捆，用作掩碼威鹿。（因?yàn)檫@里維護(hù)的數(shù)組大小都是2的整數(shù)次冪，所以_mask的二進(jìn)制位000011, 000111, 001111）剛好可以用作hash取余數(shù)的掩碼轨香。剛好保證相與后不超過(guò)緩存大小。
• _occupied是當(dāng)前已緩存的方法數(shù)幼东。即數(shù)組中已使用了多少位置臂容。
• _maskAndBucket是mask和bucket的結(jié)合體，提升了性能和效率根蟹；

結(jié)構(gòu)體bucket_t中

• SEL應(yīng)該是char*類型的字符串脓杉，char*強(qiáng)轉(zhuǎn)unsigned long，其實(shí)就是SEL的內(nèi)存地址简逮。代碼如下
• _imp就是方法實(shí)現(xiàn)IMP了球散。

二 、lldb 調(diào)試 方法緩存的時(shí)機(jī)

1 .分析 cache_t的緩存時(shí)機(jī)

-cache屬性的獲取散庶，需要通過(guò)pclass的首地址平移16字節(jié)蕉堰，即首地址+0x10獲取cache的地址

注：通過(guò)打印 分析 方法執(zhí)行后，cache_t中的_buckets中有值了悲龟，并且_occupied 為1 屋讶，很明顯說(shuō)明，方法執(zhí)行調(diào)用后進(jìn)行的緩存须教。

2 .分析 cache_t中的_buckets讀取sel和imp皿渗。
我們無(wú)法像往常一樣通過(guò)* buckets打印_buckets，但是cache_t中提供了public方法*buckets()轻腺，同理sel和imp 乐疆，但是imp需要傳參數(shù)類；看源碼

struct cache_t {
    explicit_atomic<struct bucket_t *> _buckets;
    explicit_atomic<mask_t> _mask;
public: //對(duì)外公開(kāi)可以調(diào)用的方法
    static bucket_t *emptyBuckets();
    struct bucket_t *buckets();
    mask_t mask();
    mask_t occupied();
   ......
}

struct bucket_t {
explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
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;
}

這樣就在cache中找到了 sayHello贬养！

• 從源碼的分析中挤土，我們知道sel-imp是在cache_t的_buckets屬性中（目前處于macOS環(huán)境），而在cache_t結(jié)構(gòu)體中提供了獲取_buckets屬性的方法buckets();
• 獲取了_buckets屬性煤蚌，就可以獲取sel-imp了耕挨，這兩個(gè)的獲取在bucket_t結(jié)構(gòu)體中同樣提供了相應(yīng)的獲取方法sel()以及 imp(pClass).

三 、cache_t的緩存原理

• 類似SDWebImage尉桩，我們探究方法的緩存的時(shí)候筒占，我們不僅要探索什么時(shí)候存，還要探索怎么存蜘犁，存在哪翰苫，占多大內(nèi)存，存取方式等。所以我們接下來(lái)就一步一步的去剖析奏窑。

1. 方法怎么存导披？
存是個(gè)動(dòng)作，必然也是個(gè)函數(shù)埃唯，我們?cè)诮Y(jié)構(gòu)體中cache_t去尋找有關(guān)聯(lián)的函數(shù)解釋如下：

struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED//macOS撩匕、模擬器 -- 主要是架構(gòu)區(qū)分
  // explicit_atomic 顯示原子性，目的是為了能夠 保證 增刪改查時(shí) 線程的安全性
    //等價(jià)于 struct bucket_t * _buckets;
    //_buckets 中放的是 sel imp
    //_buckets的讀取 有提供相應(yīng)名稱的方法 buckets()
    explicit_atomic<struct bucket_t *> _buckets; //最小的buckets大小是 4（為了支持?jǐn)U容算法需要）
    explicit_atomic<mask_t> _mask;  //散列表長(zhǎng)度 - 1
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 //64位真機(jī)
    explicit_atomic<uintptr_t> _maskAndBuckets;//寫(xiě)在一起的目的是為了優(yōu)化
    mask_t _mask_unused;
public: //對(duì)外公開(kāi)可以調(diào)用的方法
    static bucket_t *emptyBuckets(); // 清空buckets
    
    struct bucket_t *buckets(); //這個(gè)方法的實(shí)現(xiàn)很簡(jiǎn)單就是_buckets對(duì)外的一個(gè)獲取函數(shù)
    mask_t mask();  //獲取緩存容量_mask
    mask_t occupied(); //獲取已經(jīng)占用的緩存?zhèn)€數(shù)_occupied
    void incrementOccupied(); //增加緩存墨叛，_occupied自++
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask); //這個(gè)函數(shù)是設(shè)置一個(gè)新的Buckets
    void initializeToEmpty();
    unsigned capacity();
    bool isConstantEmptyCache();
    bool canBeFreed();
   ......
}

一看到 void incrementOccupied(); 這個(gè)方法就開(kāi)始激動(dòng)了止毕，打開(kāi)源碼：

void cache_t::incrementOccupied() 
{
  _occupied++;  //已占用的 遞增
}

源碼查看這個(gè)方法 在哪調(diào)用的，只有一個(gè)地方調(diào)用Ｄ谩１饬荨！

// 哈希表中插入sel 和 imp
ALWAYS_INLINE
void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{
  ......
}

看到這個(gè)方法： void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)

insert: 插入的意思

• Class cls ：當(dāng)前class
• SEL sel : 方法名
• IMP imp : 方法的指針
• id receiver ：接收者

一目了然闯传，這個(gè)方法就是在展示cache是如何緩存的谨朝，這個(gè)方法內(nèi)容比較多，我們一點(diǎn)點(diǎn)的去理解甥绿。我們?cè)僬艺夷睦镎{(diào)用了cache->insert字币，源碼進(jìn)行全局搜索 只有一處：

void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
    runtimeLock.assertLocked(); // runtime鎖  assert斷言
#if !DEBUG_TASK_THREADS 
    // Never cache before +initialize is done
    if (cls->isInitialized()) {
        cache_t *cache = getCache(cls);
#if CONFIG_USE_CACHE_LOCK
        mutex_locker_t lock(cacheUpdateLock);
#endif
        cache->insert(cls, sel, imp, receiver);
    }
#else
    _collecting_in_critical();
#endif
}

注：看到這么多Lock 這部分肯定是在做線程的操作，這段cache_fill中的一些操作最后都是在做insert操作妹窖，我們?cè)僬蚁?code>cache_fill是你什么時(shí)候調(diào)用的纬朝，經(jīng)過(guò)全局搜索，并沒(méi)有搜到骄呼，說(shuō)明這里又是經(jīng)過(guò)編譯器做了處理共苛，所以我們今天就只討論cache_fill —>insert里的操作。

2. cache_fill執(zhí)行流程

3. cache_t::insert執(zhí)行流程

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());
/*
 step1 創(chuàng)建臨時(shí)變量 newOccupied 蜓萄，oldCapacity 
*/

    mask_t newOccupied = occupied() + 1;
    unsigned oldCapacity = capacity(), capacity = oldCapacity;

/*
 step2 進(jìn)行buckets的計(jì)算
*/
    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
       //如果小于等于占用內(nèi)存的3 /4 則什么都不用做隅茎。
    }
    else {
//擴(kuò)容原因：第一次申請(qǐng)開(kāi)辟的內(nèi)存容量是 4 ，如果已經(jīng)有3個(gè)bucket插入到cache里面嫉沽，再次插入一個(gè)就會(huì)存滿這個(gè)容量辟犀，為了保證讀取的正確性，就對(duì)其進(jìn)行擴(kuò)容
// 擴(kuò)容算法：有capacity時(shí)擴(kuò)容為兩倍绸硕，沒(méi)有就初始化為INIT_CACHE_SIZE 也就是4
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true); 
 // 內(nèi)存 庫(kù)容完畢
    }
/*
 step3 計(jì)算好容量之后堂竟，進(jìn)行插入sel imp class
*/

    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    mask_t begin = cache_hash(sel, m); //求cache的hash ，通過(guò)計(jì)算得到sel存儲(chǔ)的下標(biāo)
    mask_t i = begin;
//遍歷操作 
    do {
// 如果sel 不存在就將sel存進(jìn)去
        if (fastpath(b[i].sel() == 0)) {
            incrementOccupied(); //Occupied ++ 
            b[i].set<Atomic, Encoded>(sel, imp, cls); //存入  sel imp cls 
            return;
        }
// 如果sel 存在就返回
        if (b[i].sel() == sel) {
            return;
        }
    } while (fastpath((i = cache_next(i, m)) != begin));

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

注： 以上總共分為三步：

• 1 計(jì)算當(dāng)前bucket占用量玻佩；
• 2 根據(jù)bucket在buckets中的占用比出嘹，開(kāi)辟空間
• 3 根據(jù)cache_hash方法，計(jì)算sel-imp存儲(chǔ)的哈希下標(biāo)咬崔，存入sel, imp, cls

• 1.待分析處理1:
  reallocate()源碼

ALWAYS_INLINE
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    //取到老的緩存池
    bucket_t *oldBuckets = buckets();
    //建立新容量的緩存池
    bucket_t *newBuckets = allocateBuckets(newCapacity);

    ASSERT(newCapacity > 0);
    ASSERT((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
    //初始化緩存池税稼，緩存池的可緩存數(shù)比緩存池的r總?cè)萘恳?
    setBucketsAndMask(newBuckets, newCapacity - 1);
   /*
    釋放老的緩存池烦秩，因?yàn)樽x和寫(xiě)是非常耗時(shí)的操作，
    緩存的目的是為了節(jié)省時(shí)間郎仆，
    所以在創(chuàng)建新的緩存池時(shí)候沒(méi)有將老緩存池的內(nèi)存copy過(guò)來(lái)
    而且這種操作也會(huì)清理掉緩存中長(zhǎng)時(shí)間沒(méi)調(diào)用的方法
    */
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
    }
}

分析如下

reallocate操作

• 如果有舊的buckets只祠，需要清理之前的緩存，即調(diào)用cache_collect_free方法

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

    _garbage_make_room ();// 創(chuàng)建 垃圾回收空間
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    garbage_refs[garbage_count++] = data;//存bucket_t *data
    cache_collect(false); // 清理舊bucket_t 垃圾回收
}

_garbage_make_room 源碼解析

static void _garbage_make_room(void)
{
    static int first = 1;

    // Create the collection table the first time it is needed
    //在第一次需要集合表時(shí)創(chuàng)建它
    if (first)
    {
        first = 0;
        garbage_refs = (bucket_t**)
            malloc(INIT_GARBAGE_COUNT * sizeof(void *));
        garbage_max = INIT_GARBAGE_COUNT;
    }

    // Double the table if it is full  如果表已滿扰肌，則加倍
    else if (garbage_count == garbage_max)
    {
        garbage_refs = (bucket_t**)
            realloc(garbage_refs, garbage_max * 2 * sizeof(void *));
        garbage_max *= 2; //擴(kuò)容
    }
}

為什么要?jiǎng)?chuàng)建新的新的buckets來(lái)替換原有的buckets并抹掉原有的buckets的方案抛寝，而不是在在原有buckets的基礎(chǔ)上進(jìn)行擴(kuò)容？

1. 減少對(duì)方法快速查找流程的影響：調(diào)用objc_msgSend時(shí)會(huì)觸發(fā)方法快速查找曙旭，如果進(jìn)行擴(kuò)容需要做一些讀寫(xiě)操作墩剖，對(duì)快速查找影響比較大。
2. 對(duì)性能要求比較高：開(kāi)辟新的buckets空間并抹掉原有buckets的消耗比在原有buckets上進(jìn)行擴(kuò)展更加高效

• 2. 待分析處理2:

   bucket_t *b = buckets();
    mask_t m = capacity - 1;
    mask_t begin = cache_hash(sel, m); //求cache的hash 夷狰，通過(guò)計(jì)算得到sel存儲(chǔ)的下標(biāo)
    mask_t i = begin;
//遍歷操作 
    do {
// 如果sel 不存在就將sel存進(jìn)去
        if (fastpath(b[i].sel() == 0)) {
            incrementOccupied(); //Occupied ++ 
            b[i].set<Atomic, Encoded>(sel, imp, cls); //存入  sel imp cls 
            return;
        }
// 如果sel 存在就返回
        if (b[i].sel() == sel) {
            return;
        }
    } while (fastpath((i = cache_next(i, m)) != begin));

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

bucket賦值插入操作

mask_t begin = cache_hash(sel, m);

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
//求cache的hash ，通過(guò)計(jì)算得到sel存儲(chǔ)的下標(biāo)
    return (mask_t)(uintptr_t)sel & mask;
}

key 就是 SEL
映射關(guān)系其實(shí)就是 sel & mask = index
mask = 散列表長(zhǎng)度 - 1
所以 index 一定是 <= mask

• 至此：cache_t的緩存過(guò)程基本分析完了郊霎≌油罚總體而言就是圍繞bucket_t進(jìn)行分析處理，大致思路 ：1計(jì)算bucket大惺槿啊进倍；2計(jì)算bucket在buckets的占比進(jìn)行容量重組；3存入賦值

4 . cache_t的緩存原理如圖

Cache_t原理分析圖來(lái)自 Cooci大神.png

四 购对、重難點(diǎn)答疑

• 1 .什么時(shí)候存儲(chǔ)到cache中猾昆？

objc_msgSend第一次發(fā)送消息會(huì)觸發(fā)方法查找，找到方法后會(huì)調(diào)用cache_fill()方法把方法緩存到cache中,這個(gè)在后面分析方法的本質(zhì)的時(shí)候會(huì)提到骡苞。

• 2 .哪幾種情況下會(huì)調(diào)用insert垂蜗？

a. init初始化對(duì)象的時(shí)候;
b. 屬性賦值，調(diào)用了set方法解幽；
c. 方法調(diào)用贴见；

• 3.bucket數(shù)據(jù)為什么會(huì)有丟失的情況？

原因是在擴(kuò)容時(shí)躲株，是將原有的內(nèi)存全部清除了片部，再重新申請(qǐng)了內(nèi)存導(dǎo)致的

• 4 .方法緩存cache_t的方法?

散列表技術(shù) key-value, 用散列表來(lái)緩存曾經(jīng)調(diào)用過(guò)的方法，可以提高方法的查找速度

• 5. 散列表的數(shù)據(jù)儲(chǔ)存位置：

_mask( 散列表的長(zhǎng)度-1 ) = 這個(gè)數(shù)據(jù)緩存的位置的下標(biāo)霜定，也就是緩存方法的索引档悠，這個(gè)下標(biāo)經(jīng)過(guò)位運(yùn)算之后，一定會(huì)小于或者等于散列表的長(zhǎng)度-1 望浩，就不會(huì)出現(xiàn)數(shù)組越界的情況了

五 辖所、總結(jié)

這篇主要探索了cache_t的結(jié)構(gòu)和大概的緩存原理，其實(shí)cache_t的整個(gè)流程在源碼的注釋中已經(jīng)給出曾雕，注釋如下：

 * All functions that modify cache data or structures must acquire the 
 * cacheUpdateLock to prevent interference from concurrent modifications.
 * The function that frees cache garbage must acquire the cacheUpdateLock 
 * and use collecting_in_critical() to flush out cache readers.
 * The cacheUpdateLock is also used to protect the custom allocator used 
 * for large method cache blocks.
 *
 * Cache readers (PC-checked by collecting_in_critical())
 * objc_msgSend*
 * cache_getImp
 *
 * Cache writers (hold cacheUpdateLock while reading or writing; not PC-checked)
 * cache_fill         (acquires lock)
 * cache_expand       (only called from cache_fill)
 * cache_create       (only called from cache_expand)
 * bcopy               (only called from instrumented cache_expand)
 * flush_caches        (acquires lock)
 * cache_flush        (only called from cache_fill and flush_caches)
 * cache_collect_free (only called from cache_expand and cache_flush)

接下來(lái)我們就會(huì)討論objc_msgSend奴烙。