在 指針偏移&讀取bits信息& class_rw_t文章中我們已經(jīng)分析了bits今天我們分析cache 看看 cache是如何工作的
首先準(zhǔn)備在源碼環(huán)境下創(chuàng)建如下代碼并斷言
@interface LGPerson : NSObject
@property (nonatomic, copy) NSString *nickName;
@property (nonatomic, strong) NSString *name;
-(void)lookBeauty;
-(void)sayNB;
-(void)listenStory;
@end
#import "LGPerson.h"
@implementation LGPerson
-(void)lookBeauty
{
NSLog(@"看美女");
}
-(void)sayNB
{
NSLog(@"吹牛皮");
}
-(void)listenStory
{
NSLog(@"聽故事");
}
@end
lldb 調(diào)試獲取cache
斷點(diǎn)在lookBeauty位置
截屏2020-09-18 下午4.56.12.png
lldb調(diào)試cache 2.jpg
斷點(diǎn)過 lookBeauty 斷點(diǎn)到 sayNB
lldb調(diào)試cache 2備份.jpg
斷點(diǎn)過 sayNB 斷點(diǎn)到 listenStory
lldb調(diào)試cache 2備份 2.jpg
斷過listenStory 斷到 NSLog
lldb調(diào)試cache 2備份 3.jpg
帶著上面的疑問 我們開始分析源碼 mask 是啥 occupied是啥 為啥變化 ,為啥數(shù)據(jù)會丟失白热， cache到底怎么存儲的摸袁？
底層源碼分析
cache_t 中找線索
struct cache_t {
....省略
public:
static bucket_t *emptyBuckets();
struct bucket_t *buckets();
mask_t mask();
mask_t occupied();
void incrementOccupied();
void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
void initializeToEmpty();
unsigned capacity();
bool isConstantEmptyCache();
bool canBeFreed();
....省略
看到了incrementOccupied(); 函數(shù) 中文是 增加 occupied 點(diǎn)進(jìn)去
void cache_t::incrementOccupied()
{
_occupied++;
}
_occupied ++ 緩存一個(gè)方法就++ ？繼續(xù)探尋全局搜索 incrementOccupied() 此方法 看從哪里調(diào)用的
ALWAYS_INLINE
void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{
.....省略 后面著重分析
}
我的天在整個(gè)源碼里面 只有這一個(gè)地方進(jìn)行了 調(diào)用 看方法名字為insert 在繼續(xù)搜索 insert 看在哪里調(diào)用的
void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
runtimeLock.assertLocked();
#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
}
繼續(xù)搜索cache_fill，發(fā)現(xiàn)在寫入之前，還有一步操作，即cache讀取漾岳，即查找sel-imp,如下圖
截屏2020-09-19 下午1.21.25.png
insert 方法分析
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());
// Use the cache as-is if it is less than 3/4 full /////如果緩存不足3/4滿，就按原樣使用
mask_t newOccupied = occupied() + 1;/// newOccupied = ( 拿到 以前的 occuoied() ＋1 ),如沒有屬性賦值家乘，occupied() = 0
unsigned oldCapacity = capacity(), capacity = oldCapacity; // return mask() ? mask()+1 : 0;
if (slowpath(isConstantEmptyCache())) { ///判斷是否需要初始化創(chuàng)建緩存 小概率：occupied（） = 0 時(shí)
// Cache is read-only. Replace it.
if (!capacity) capacity = INIT_CACHE_SIZE; /// 初始化 capacity = (1<<2) 二進(jìn)制 100 十進(jìn)制 4
reallocate(oldCapacity, capacity, /* freeOld */false); /// 開辟 空間 不需要釋放回收老的內(nèi)存
}
else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) {
// Cache is less than 3/4 full. Use it as-is. //緩存不足3/4滿蝗羊。按原樣使用它。
// 假如上之前有兩個(gè)緩存
// mask_t newOccupied = occupied() + 1; ///2 +1
//第一次開辟 申請內(nèi)存是4個(gè) 已經(jīng)有2個(gè)插入 bucket 插入到緩存里
/// newOccupied + 1 < = capacity/4*3 == （3+1 <= capacity/4*3）所以不滿足 要進(jìn)行內(nèi)容擴(kuò)張 看下面的方法
}
else {
/// 有 cap 是否 存才 ： 存在 進(jìn)行 2倍擴(kuò)容 :不存在 4
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
/// 最大 不能 超過 1<<16
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;
}
///重新開辟內(nèi)存空間 并回收老的數(shù)據(jù)
reallocate(oldCapacity, capacity, true);
}
bucket_t *b = buckets();/// 獲取 bukets
mask_t m = capacity - 1; //mask 實(shí)際內(nèi)存?zhèn)€數(shù) -1 類似 最大 下標(biāo)
/// 獲取 根據(jù) m 7 和當(dāng)前 sel 獲取 hash表 mask
mask_t begin = cache_hash(sel, m); //查找 hash表 key為 sel m = 最大下標(biāo) 計(jì)算當(dāng)前需要插入的緩存下標(biāo)
mask_t i = begin; //i = 0
// Scan for the first unused slot and insert there.
// There is guaranteed to be an empty slot because the
// minimum size is 4 and we resized at 3/4 full.
//掃描第一個(gè)未使用的插槽并插入仁锯。
//保證有一個(gè)空槽耀找，因?yàn)? //最小尺寸是4，我們將大小調(diào)整為3/4滿业崖。
do {
///循環(huán)遍歷 buckets() sel() 一旦發(fā)現(xiàn) 沒有 就進(jìn)行 occupied+1 并進(jìn)行存儲 并跳出循環(huán)
if (fastpath(b[i].sel() == 0)) {
incrementOccupied();
b[i].set<Atomic, Encoded>(sel, imp, cls);
return;
}
///循環(huán)遍歷 發(fā)現(xiàn)了已經(jīng)有存了 occupied 不做任何處理 并return
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));
cache_t::bad_cache(receiver, (SEL)sel, cls);
}
分析：
- 第一步野芒，根據(jù)occupied的值計(jì)算出當(dāng)前的緩存占用量，當(dāng)沒有方法調(diào)用時(shí)候 _occupied 為0
mask_t cache_t::occupied()
{
return _occupied;
}
- 第二步双炕，根據(jù)緩存占用量計(jì)算需開辟空間大小
1.是否為初始化 首次 開辟空間 是的話 開辟 4 個(gè)大小
if (slowpath(isConstantEmptyCache())) { ///判斷是否需要初始化創(chuàng)建緩存 小概率：occupied（） = 0 時(shí)
// Cache is read-only. Replace it.
if (!capacity) capacity = INIT_CACHE_SIZE; /// 初始化 capacity = (1<<2) 二進(jìn)制 100 十進(jìn)制 4
reallocate(oldCapacity, capacity, /* freeOld */false); /// 開辟 空間 不需要釋放回收老的內(nèi)存
}
2.如果緩存占用量小于等于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滿。按原樣使用它妇斤。
// 假如上之前有兩個(gè)緩存
// mask_t newOccupied = occupied() + 1; ///2 +1
//第一次開辟 申請內(nèi)存是4個(gè) 已經(jīng)有2個(gè)插入 bucket 插入到緩存里
/// newOccupied + 1 < = capacity/4*3 == （3+1 <= capacity/4*3）所以不滿足 要進(jìn)行內(nèi)容擴(kuò)張 看下面的方法
}
3.如果緩存占用量超過3/4摇锋，則需要進(jìn)行兩倍擴(kuò)容以及重新開辟空間
/// 有 cap 是否 存才 ： 存在 進(jìn)行 2倍擴(kuò)容 :不存在 4
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
/// 最大 不能 超過 1<<16
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;
}
///重新開辟內(nèi)存空間 并回收老的數(shù)據(jù)
reallocate(oldCapacity, capacity, true);
}
- 第三步，針對需要存儲的bucket進(jìn)行內(nèi)部imp 和sel賦值
bucket_t *b = buckets();/// 獲取 bukets
mask_t m = capacity - 1; //mask 實(shí)際內(nèi)存?zhèn)€數(shù) -1 類似 最大 下標(biāo)
/// 獲取 根據(jù) m 7 和當(dāng)前 sel 獲取 hash表 mask
mask_t begin = cache_hash(sel, m); //查找 hash表 key為 sel m = 最大下標(biāo) 計(jì)算當(dāng)前此次插入的哈希下標(biāo)
mask_t i = begin;
// Scan for the first unused slot and insert there.
// There is guaranteed to be an empty slot because the
// minimum size is 4 and we resized at 3/4 full.
//掃描第一個(gè)未使用的插槽并插入站超。
//保證有一個(gè)空槽荸恕，因?yàn)? //最小尺寸是4，我們將大小調(diào)整為3/4滿死相。
do {
///循環(huán)遍歷 buckets() sel() 一旦發(fā)現(xiàn) 沒有 就進(jìn)行 occupied+1 并進(jìn)行存儲 并跳出循環(huán)
if (fastpath(b[i].sel() == 0)) {
incrementOccupied();
b[i].set<Atomic, Encoded>(sel, imp, cls);
return;
}
///循環(huán)遍歷 發(fā)現(xiàn)了已經(jīng)有存了 occupied 不做任何處理 并return
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));
cache_t::bad_cache(receiver, (SEL)sel, cls);
}
循環(huán) 查找 當(dāng)前sel在緩存是否存才 腿宰，存在直接跳出循環(huán) 不存在存入緩存并且緩存占用量+1 并跳出循環(huán)
cache原理分析的流程圖
cache_fill方法.jpg
疑問解答
1窃这、_mask是什么吮旅？
_mask是指的掩碼數(shù)據(jù)，用于在哈希算法或者哈希沖突算法中計(jì)算哈希下標(biāo)县昂，其中mask = 開辟空間總大小 -1
2、_occupied 是什么陷舅？
_occupied 表示 當(dāng)前存儲了幾個(gè) sel-imp 倒彰，方法調(diào)用 也就是消息發(fā)送 會導(dǎo)致 occupied 變化
3、為什么 調(diào)用第三個(gè)方法的時(shí)候 _mask 會變?yōu)?7 _occupied 變?yōu)榱?code>1 蔑赘？
因?yàn)樵?code>cache初始化的時(shí)候狸驳，分配的空間是4個(gè)，隨著方法的增多缩赛，當(dāng)存儲的 sel-imp個(gè)數(shù) 即newOccupied + CACHE_END_MARKER（等于1）的和 超過 總?cè)萘康?/4,例如有4個(gè)時(shí)耙箍，當(dāng)occupied等于2時(shí)，就需要對cache的內(nèi)存進(jìn)行兩倍擴(kuò)容
4酥馍、為什么 數(shù)據(jù)丟失了呢 辩昆？
因?yàn)?code>sel-imp的存儲是通過哈希算法計(jì)算下標(biāo)的，其計(jì)算的下標(biāo)有可能已經(jīng)存儲了sel被占用旨袒，所以又需要通過哈希沖突算法重新計(jì)算哈希下標(biāo)汁针，所以導(dǎo)致下標(biāo)是隨機(jī)的，并不是固定的
