iOS 底層原理 文章匯總

本文的主要目的是理解cache_t以及sel-imp的緩存原理

整體分析

在之前的iOS-底層原理 07：isa與類關(guān)聯(lián)的原理和iOS-底層原理 08：類 & 類結(jié)構(gòu)分析中，分析了objc_class中isa和bits，這次主要是分析objc_calss中的cache屬性

cache中存儲的是什么？

首先，我們需要知道cache中存儲的到底是什么？

• 查看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、模擬器 -- 主要是架構(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位真機
    explicit_atomic<uintptr_t> _maskAndBuckets;//寫在一起的目的是為了優(yōu)化
    mask_t _mask_unused;
    
    //以下都是掩碼，即面具 -- 類似于isa的掩碼，即位域
    // 掩碼省略....
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4 //非64位 真機
    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;

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

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

struct bucket_t {
private:
#if __arm64__ //真機
    //explicit_atomic 是加了原子性的保護
    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

整體的結(jié)構(gòu)如下圖所示

整體類型關(guān)系結(jié)構(gòu)圖

在cache中查找sel-imp

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

• 通過源碼查找
• 脫離源碼在項目中查找

準備工作

• 定義一個LGPerson類，并定義兩個屬性及5個實例方法及其實現(xiàn)
  

  定義LGPerson類-1
  
  
  定義LGPerson類-2

• 在main中定義LGPerson類的對象p，并調(diào)用其中的3個實例方法，在p調(diào)用第一個方法處加一個斷點
  

  main函數(shù)

通過源碼查找

• 運行執(zhí)行，斷在[p sayHello];部分，此時執(zhí)行以下lldb調(diào)試流程
  
  僅一個方法調(diào)用的sel-imp查找流程

  • cache屬性的獲取，需要通過pclass的首地址平移16字節(jié)，即首地址+0x10獲取cache的地址

  • 從源碼的分析中，我們知道sel-imp是在cache_t的_buckets屬性中（目前處于macOS環(huán)境），而在cache_t結(jié)構(gòu)體中提供了獲取_buckets屬性的方法buckets()

  • 獲取了_buckets屬性，就可以獲取sel-imp了，這兩個的獲取在bucket_t結(jié)構(gòu)體中同樣提供了相應(yīng)的獲取方法sel() 以及 imp(pClass)

由上圖可知，在沒有執(zhí)行方法調(diào)用時，此時的cache是沒有緩存的，執(zhí)行了一次方法調(diào)用，cache中就有了一個緩存，即調(diào)用一次方法就會緩存一次方法。

我們現(xiàn)在了解了如何獲取cache中sel-imp，如何驗證打印的sel和imp就是我們調(diào)用的呢？可以通過machoView打開target的可執(zhí)行文件，在方法列表中查看其imp的值是否是一致的，如下所示，發(fā)現(xiàn)是一致的，所以打印的這個sel-imp就是LGPerson的實例方法

方法imp對比

• 接著上面的步驟，我們再次調(diào)用一個方法，這次我們想要獲取第二個sel，其調(diào)試的lldb如下
  
  多個方法調(diào)用的sel-imp查找
  
  第一個調(diào)用方法的存儲獲取很簡單，直接通過_buckets的首地址調(diào)用對應(yīng)的方法即可，那么獲取第二個呢？在之前的iOS-底層原理 08：類 & 類結(jié)構(gòu)分析文章中，曾提及過一個概念 指針偏移，所以我們這里可以通過_buckets屬性的首地址偏移，即 p *($9+1)即可獲取第二個方法的sel 和imp
  如果有多個方法需要獲取，以此類推，例如p *($9+i)

脫離源碼通過項目查找

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

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


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

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

• 這里有個問題需要注意，在源碼中，objc_class的ISA屬性是繼承自objc_object的，但在我們將其拷貝過來時，去掉了objc_class的繼承關(guān)系，需要將這個屬性明確，否則打印的結(jié)果是有問題，如下圖所示，
  

  有問題的打印

• 加上ISA屬性后，增加兩個方法的調(diào)用，其正確的打印結(jié)果應(yīng)該是這樣的

  
  
  結(jié)果打印-1

• 在增加兩個方法的調(diào)用，即解開say3、say4的注釋，其打印結(jié)果如下

  
  
  結(jié)果打印-2

針對上面的打印結(jié)果，有以下幾點疑問

• 1、_mask是什么？
• 2、_occupied 是什么？
• 3、為什么隨著方法調(diào)用的增多，其打印的occupied 和 mask會變化？
• 4、bucket數(shù)據(jù)為什么會有丟失的情況？，例如2-7中，只有say3、say4方法有函數(shù)指針
• 5、2-7中say3、say4的打印順序為什么是say4先打印，say3后打印，且還是挨著的，即順序有問題？
• 6、打印的cache_t中的_ocupied為什么是從2開始？

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

cache_t底層原理分析

• 首先，從cache_t中的_mask屬性開始分析，找cache_t中引起變化的函數(shù)，發(fā)現(xiàn)了incrementOccupied()函數(shù)
  
  cache_t中的incrementOccupied方法
  
  該函數(shù)的具體實現(xiàn)為

void incrementOccupied(); //Occupied自增

//??具體實現(xiàn)
void cache_t::incrementOccupied() 
{
    _occupied++;
}

• 源碼中，全局搜索incrementOccupied()函數(shù)，發(fā)現(xiàn)只在cache_t的insert方法有調(diào)用
  

  cache_t中insert調(diào)用incrementOccupied方法

• insert方法，理解為cache_t的插入，而cache中存儲的就是sel-imp，所以cache的原理從insert方法開始分析，以下是cache原理分析的流程圖
  

  cache_t原理圖示

• 全局搜索insert(方法，發(fā)現(xiàn)只有cache_fill方法中的調(diào)用符合
  

  cache_t中cache_fill中調(diào)用insert方法

• 全局搜索cache_fill，發(fā)現(xiàn)在寫入之前，還有一步操作，即cache讀取，即查找sel-imp，如下所示
  

  cache_fill之前的流程

但本文的重點還是分析cache存儲的原理，接下來根據(jù)cache_t寫入的流程圖，著重分析insert方法

insert方法分析

在insert方法中，其源碼實現(xiàn)如下

insert源碼實現(xiàn)

• 【第一步】計算出當(dāng)前的緩存占用量
• 【第二步】根據(jù)緩存占用量``判斷執(zhí)行的操作
• 【第三步】針對需要存儲的bucket進行內(nèi)部imp和sel賦值

其中，第一步，根據(jù)occupied的值計算出當(dāng)前的緩存占用量，當(dāng)屬性未賦值及無方法調(diào)用時，此時的occupied()為0，而newOccupied為1，如下所示

mask_t newOccupied = occupied() + 1;

關(guān)于緩存占用量的計算，有以下幾點說明：

• alloc申請空間時，此時的對象已經(jīng)創(chuàng)建，如果再調(diào)用init方法，occupied也會+1

• 當(dāng)有屬性賦值時，會隱式調(diào)用set方法，occupied也會增加，即有幾個屬性賦值，occupied就會在原有的基礎(chǔ)上加幾個

• 當(dāng)有方法調(diào)用時，occupied也會增加，即有幾次調(diào)用，occupied就會在原有的基礎(chǔ)上加幾個

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

• 如果是第一次創(chuàng)建，則默認開辟4個

if (slowpath(isConstantEmptyCache())) { //小概率發(fā)生的 即當(dāng) occupied() = 0時，即創(chuàng)建緩存，創(chuàng)建屬于小概率事件
    // Cache is read-only. Replace it.
    if (!capacity) capacity = INIT_CACHE_SIZE; //初始化時，capacity = 4（1<<2 -- 100）
    reallocate(oldCapacity, capacity, /* freeOld */false); //開辟空間
    //到目前為止，if的流程的操作都是初始化創(chuàng)建
}

• 如果緩存占用量小于等于3/4，則不作任何處理

else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) { 
    // Cache is less than 3/4 full. Use it as-is.
}

• 如果緩存占用量超過3/4，則需要進行兩倍擴容以及重新開辟空間

else {//如果超出了3/4，則需要擴容（兩倍擴容）
    //擴容算法： 有cap時，擴容兩倍，沒有cap就初始化為4
    capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 擴容兩倍 2*4 = 8
    if (capacity > MAX_CACHE_SIZE) {
        capacity = MAX_CACHE_SIZE;
    }
    // 走到這里表示 曾經(jīng)有，但是已經(jīng)滿了，需要重新梳理
    reallocate(oldCapacity, capacity, true);
    // 內(nèi)存 擴容完畢
}

realloc方法：開辟空間

該方法，在第一次創(chuàng)建以及兩倍擴容時，都會使用，其源碼實現(xiàn)如圖所示

realloc方法源碼實現(xiàn)

• allocateBuckets方法：向系統(tǒng)申請開辟內(nèi)存，即開辟bucket，此時的bucket只是一個臨時變量

• setBucketsAndMask方法：將臨時的bucket存入緩存中，此時的存儲分為兩種情況：

  • 如果是真機，根據(jù)bucket和mask的位置存儲，并將occupied占用設(shè)置為0
    

    真機的setBucketsAndMask源碼實現(xiàn)

  • 如果不是真機，正常存儲bucket和mask，并將occupied占用設(shè)置為0
    

    非真機的setBucketsAndMask源碼實現(xiàn)

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

  cache_collect_free源碼實現(xiàn)
  
  該方法的實現(xiàn)主要有以下幾步：

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

    _garbage_make_room源碼實現(xiàn)

    • 如果是第一次，需要分配回收空間

    • 如果不是第一次，則將內(nèi)存段加大，即原有內(nèi)存*2

  • 記錄存儲這次的bucket

  • cache_collect方法：垃圾回收，清理舊的bucket
    

    cache_collect源碼實現(xiàn)

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

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

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

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

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

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

• 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，重新進行哈希計算，得到一個新的下標(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的原理基本分析完成了，然后前文提及的幾個問題，我們現(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、為什么隨著方法調(diào)用的增多，其打印的occupied 和 mask會變化？

因為在cache初始化時，分配的空間是4個，隨著方法調(diào)用的增多，當(dāng)存儲的sel-imp個數(shù)，即newOccupied + CACHE_END_MARKER（等于1）的和 超過 總?cè)萘康?/4,例如有4個時，當(dāng)occupied等于2時，就需要對cache的內(nèi)存進行兩倍擴容

4、bucket數(shù)據(jù)為什么會有丟失的情況？，例如2-7中，只有say3、say4方法有函數(shù)指針

原因是在擴容時，是將原有的內(nèi)存全部清除了，再重新申請了內(nèi)存導(dǎo)致的

5、2-7中say3、say4的打印順序為什么是say4先打印，say3后打印，且還是挨著的，即 順序有問題 ？

因為sel-imp的存儲是通過哈希算法計算下標(biāo)的，其計算的下標(biāo)有可能已經(jīng)存儲了sel，所以又需要通過哈希沖突算法重新計算哈希下標(biāo)，所以導(dǎo)致下標(biāo)是隨機的，并不是固定的

6、打印的 cache_t 中的 ocupied 為什么是從 2 開始？

這里是因為LGPerson通過alloc創(chuàng)建的對象，并對其兩個屬性賦值的原因，屬性賦值，會隱式調(diào)用set方法，set方法的調(diào)用也會導(dǎo)致occupied變化