iOS - cache_t分析

1. cache中存儲的是什么载慈？

查看cache_t的源碼毅桃，發(fā)現(xiàn)分成了3個架構的處理缸匪，其中真機的架構中翁狐，mask和bucket是寫在一起，目的是為了優(yōu)化凌蔬，可以通過各自的掩碼來獲取相應的數(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露懒、模擬器 -- 主要是架構區(qū)分
    // explicit_atomic 顯示原子性，目的是為了能夠 保證 增刪改查時 線程的安全性
    //等價于 struct bucket_t * _buckets;
    //_buckets 中放的是 sel imp
    //_buckets的讀取 有提供相應名稱的方法 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é)構體源碼可知，cache中緩存的是sel-imp
整體的結(jié)構如下圖所示

2. 在cache中查找sel-imp

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

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

準備工作

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

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

2.1. 通過源碼查找

運行執(zhí)行象迎，斷在[p sayHello]部分，此時執(zhí)行以下lldb調(diào)試流程
- cache屬性的獲取呛踊，需要通過pclass的首地址平移16字節(jié)砾淌，即首地址+0x10獲取cache的地址
- 從源碼的分析中，我們知道sel-imp是在cache_t的_buckets屬性中（目前處于macOS環(huán)境）谭网，而在cache_t結(jié)構體中提供了獲取_buckets屬性的方法buckets()
- 獲取了_buckets屬性汪厨，就可以獲取sel-imp了，這兩個的獲取在bucket_t結(jié)構體中同樣提供了相應的獲取方法sel() 以及imp(pClass)

由上圖流程可知愉择，在沒有執(zhí)行方法調(diào)用時劫乱，此時的cache是沒有緩存的，執(zhí)行了一次方法調(diào)用锥涕，cache中就有了一個緩存衷戈，即調(diào)用一次方法就會緩存一次方法。

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

我們再次調(diào)用一個方法采盒，這次我們想要獲取第二個sel，其調(diào)試的lldb如下

那么獲取第二個呢蔚润？曾提及過一個概念 指針偏移磅氨，所以我們這里可以通過_buckets屬性的首地址偏移，即 p *($9+1)即可獲取第二個方法的sel 和imp
如果有多個方法需要獲取嫡纠，以此類推烦租，例如p *($9+i)

2.2. 脫離源碼通過項目查找

脫離源碼環(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的繼承關系，需要將這個屬性明確踱侣，否則打印的結(jié)果是有問題粪小，所以得加上ISA屬性，打印結(jié)果
在增加兩個方法的調(diào)用抡句，即解開say3探膊、say4的注釋，其打印結(jié)果如下

針對上面的打印結(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中的_occupied為什么是從2開始沐绒？

3. cache_t底層原理分析

首先，從cache_t中的_mask屬性開始分析旺坠，找cache_t中引起變化的函數(shù)乔遮，發(fā)現(xiàn)了incrementOccupied()函數(shù)

incrementOccupied()的具體實現(xiàn)為

void incrementOccupied(); //Occupied自增

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

源碼中，全局搜索incrementOccupied()函數(shù)取刃，發(fā)現(xiàn)只在cache_t的insert方法有調(diào)用
insert方法蹋肮，理解為cache_t的插入，而cache中存儲的就是sel-imp璧疗，所以cache的原理從insert方法開始分析坯辩，以下是cache原理分析的流程圖

Cache_t原理分析圖來自 Cooci

全局搜索insert( 方法，發(fā)現(xiàn)只有cache_fill方法中的調(diào)用符合
搜索cache_fill崩侠，發(fā)現(xiàn)在寫入之前漆魔，還有一步操作，即cache讀取却音，即查找sel-imp有送，如下所示

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

3.1 insert方法分析

insert其源碼實現(xiàn)如下

主要分為以下幾部分

【第一步】計算出當前的緩存占用量
關于緩存占用量的計算，有以下幾點說明：
- alloc申請空間時裸删，此時的對象已經(jīng)創(chuàng)建八拱，如果再調(diào)用init方法，occupied也會+1
- 當有屬性賦值時涯塔，會隱式調(diào)用set方法肌稻，occupied也會增加，即有幾個屬性賦值匕荸，occupied就會在原有的基礎上加幾個
- 當有方法調(diào)用時爹谭，occupied也會增加，即有幾次調(diào)用方法榛搔，occupied就會在原有的基礎上加幾個
- 根據(jù)occupied的值計算出當前的緩存占用量诺凡，當屬性未賦值及無方法調(diào)用時，此時的occupied()為0践惑，而newOccupied為1腹泌，如下所示
```
mask_t newOccupied = occupied() + 1;
```
【第二步】根據(jù)緩存占用量判斷執(zhí)行的操作
- 如果是第一次創(chuàng)建，則默認開辟4個
```
if (slowpath(isConstantEmptyCache())) { //小概率發(fā)生的 即當 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方法, 主要有以下幾步
  - allocateBuckets方法：向系統(tǒng)申請開辟內(nèi)存左敌，即開辟bucket，此時的bucket只是一個臨時變量
  - setBucketsAndMask方法：將臨時的bucket存入緩存中俐镐，此時的存儲分為兩種情況：
    - 如果是真機矫限，根據(jù)bucket和mask的位置存儲，并將occupied占用設置為0
    - 如果不是真機佩抹，正常存儲bucket和mask叼风，并將occupied占用設置為0
  - 如果有舊的buckets，需要清理之前的緩存棍苹，即調(diào)用方法无宿，其源碼實現(xiàn)如下cache_collect_free
    - _garbage_make_room方法：創(chuàng)建垃圾回收空間，如果是第一次枢里，需要分配回收空間孽鸡，如果不是第一次，則將內(nèi)存段加大栏豺，即原有內(nèi)存*2
    - 記錄存儲這次的bucket
    - cache_collect方法：垃圾回收彬碱，清理舊的bucket

【第三步】針對需要存儲的bucket進行內(nèi)部imp和sel賦值
這部分主要是根據(jù)cache_hash方法，即哈希算法 奥洼，計算sel-imp存儲的哈希下標巷疼，分為以下三種情況

如果哈希下標的位置未存儲sel，即該下標位置獲取sel等于0灵奖，此時將sel-imp存儲進去嚼沿，并將occupied占用大小加1
如果當前哈希下標存儲的sel 等于 即將插入的sel，則直接返回
如果當前哈希下標存儲的sel 不等于 即將插入的sel瓷患，則重新經(jīng)過cache_next方法即哈希沖突算法伏尼，重新進行哈希計算，得到新的下標尉尾，再去對比進行存儲

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

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; //（將當前的哈希下標 +1） & mask，重新進行哈希計算，得到一個新的下標
}

#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ù)凑阶，用于在哈希算法或者哈希沖突算法中計算哈希下標猿规，其中mask 等于capacity - 1

2、_occupied 是什么宙橱？

_occupied表示哈希表中 sel-imp 的占用大小 (即可以理解為分配的內(nèi)存中已經(jīng)存儲了sel-imp的的個數(shù))姨俩，

init會導致occupied變化

屬性賦值，也會隱式調(diào)用师郑，導致occupied變化

方法調(diào)用环葵，導致occupied變化

3、為什么隨著方法調(diào)用的增多宝冕，其打印的occupied 和 mask會變化张遭？

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

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

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

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

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

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

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