本文的主要目的是理解cache_t以及sel-imp的緩存原理
整體分析
在之前的iOS-底層原理 07：isa與類關聯(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)化，可以通過各自的掩碼來獲取相應的數(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的讀取 有提供相應名稱的方法 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)如下圖所示
在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)體中同樣提供了相應的獲取方法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的實例方法
- 接著上面的步驟诈泼，我們再次調(diào)用一個方法懂拾，這次我們想要獲取第二個sel，其調(diào)試的lldb如下
多個方法調(diào)用的sel-imp查找
第一個調(diào)用方法的存儲獲取很簡單铐达，直接通過_buckets的首地址調(diào)用對應的方法即可岖赋，那么獲取第二個呢？在之前的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的繼承關系，需要將這個屬性明確沮峡，否則打印的結(jié)果是有問題疚脐，如下圖所示，
有問題的打印 -
加上ISA屬性后邢疙，增加兩個方法的調(diào)用棍弄，其正確的打印結(jié)果應該是這樣的
結(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)如下
主要分為以下幾部分
- 【第一步】
計算出當前的緩存占用量 - 【第二步】根據(jù)
緩存占用量``判斷執(zhí)行的操作 - 【第三步】針對需要存儲的
bucket進行內(nèi)部imp和sel賦值
其中瘦馍，第一步歼秽，根據(jù)occupied的值計算出當前的緩存占用量，當屬性未賦值及無方法調(diào)用時情组，此時的occupied()為0燥筷，而newOccupied為1，如下所示
mask_t newOccupied = occupied() + 1;
關于緩存占用量的計算院崇，有以下幾點說明：
alloc申請空間時肆氓，此時的對象已經(jīng)創(chuàng)建，如果再調(diào)用init方法亚脆，occupied也會+1當
有屬性賦值時做院，會隱式調(diào)用set方法，occupied也會增加，即有幾個屬性賦值键耕，occupied就會在原有的基礎上加幾個當
有方法調(diào)用時寺滚，occupied也會增加，即有幾次調(diào)用屈雄，occupied就會在原有的基礎上加幾個
【第二步】根據(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)如圖所示
主要有以下幾步
allocateBuckets方法：向系統(tǒng)申請開辟內(nèi)存勺爱，即開辟bucket，此時的bucket只是一個臨時變量-
setBucketsAndMask方法：將臨時的bucket存入緩存中讯检，此時的存儲分為兩種情況：-
如果是
真機琐鲁，根據(jù)bucket和mask的位置存儲，并將occupied占用設置為0
真機的setBucketsAndMask源碼實現(xiàn) -
如果
不是真機视哑，正常存儲bucket和mask绣否，并將occupied占用設置為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存儲的哈希下標，分為以下三種情況：
如果哈希下標的位置
未存儲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è)萘康?/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變化
