1.cache中存儲的是什么？
上一篇博客分析了類的isa、superclass、bits，這一篇主要分析cache的緩存機制
1.cache_t 結(jié)構(gòu)體部分代碼，用到的成員變量和部分函數(shù)
struct cache_t {
private:
// explicit_atomic 顯式原子性，目的是為了能夠 保證 增刪改查時 線程的安全性
explicit_atomic<uintptr_t> _bucketsAndMaybeMask;
//mask(高16位)+bucket(低48位) mask的本質(zhì)是開辟可以存儲bucket_t空間的下標(biāo)
// _bucketsAndMaybeMask is a buckets_t pointer in the low 48 bits
// _bucketsAndMaybeMask: 低48位是bucket_t pointer即指向bucket_t的指針，高16位是mask
union {
struct {// 可見bucket_t在cache里面是指針的形式存在的
explicit_atomic<mask_t> _maybeMask; // _maybeMask is unused, the mask is stored in the top 16 bits.
#if __LP64__ // _maybeMask不再使用
uint16_t _flags; //狀態(tài)標(biāo)識，用于計算某些值
#endif
uint16_t _occupied; //已經(jīng)占用單位空間的數(shù)量
};
explicit_atomic<preopt_cache_t *> _originalPreoptCache;
};
// 不同架構(gòu)下掩碼的值
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED // MacOS、模擬器
// _bucketsAndMaybeMask is a buckets_t pointer
// _maybeMask is the buckets mask
static constexpr uintptr_t bucketsMask = ~0ul;
static_assert(!CONFIG_USE_PREOPT_CACHES, "preoptimized caches not supported");
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
static constexpr uintptr_t maskShift = 48;
static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << maskShift) - 1;
static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS, "Bucket field doesn't have enough bits for arbitrary pointers.");
#if CONFIG_USE_PREOPT_CACHES
static constexpr uintptr_t preoptBucketsMarker = 1ul;
static constexpr uintptr_t preoptBucketsMask = bucketsMask & ~preoptBucketsMarker;
#endif
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 //64位真機
// _bucketsAndMaybeMask is a buckets_t pointer in the low 48 bits
// _maybeMask is unused, the mask is stored in the top 16 bits.
// _bucketsAndMaybeMask 低48位是bucket指針，高16位是mask
// How much the mask is shifted by.
static constexpr uintptr_t maskShift = 48; //mask在64位中的高16位，要想獲取到對應(yīng)的值需要_bucketsAndMaybeMask里面的值左移48位
// Additional bits after the mask which must be zero. msgSend
// takes advantage of these additional bits to construct the value
// `mask << 4` from `_maskAndBuckets` in a single instruction.
static constexpr uintptr_t maskZeroBits = 4;
// The largest mask value we can store.
//可以存儲mask的最大值
static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1; // maxMask最大mask 2^(16-1)
// The mask applied to `_maskAndBuckets` to retrieve the buckets pointer.
// bucketsMask用來在這_bucketsAndMaybeMask里面獲取bucket指針
static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
// Ensure we have enough bits for the buckets pointer.
static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS,
"Bucket field doesn't have enough bits for arbitrary pointers.");
// 以下為private函數(shù)
bool isConstantEmptyCache() const; // 是否位空
mask_t mask() const; // 獲取mask
void incrementOccupied(); //每插入一個bucket_t，occupied++ --> 標(biāo)記已經(jīng)占用幾個位置了
void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask); // buckets和mask寫入緩存
void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld); //開辟緩存空間
void collect_free(bucket_t *oldBuckets, mask_t oldCapacity);//釋放緩存空間
public:
// The following four fields are public for objcdt's use only.
// objcdt reaches into fields while the process is suspended
// hence doesn't care for locks and pesky little details like this
// and can safely use these.
// public函數(shù)
unsigned capacity() const;//獲取capacity 開辟的緩存空間容量
struct bucket_t *buckets() const; //獲取緩存空間的bucket指針
Class cls() const;
mask_t occupied() const;// 獲取occupied已經(jīng)占用了多少個緩存空間
void insert(SEL sel, IMP imp, id receiver);// 向緩存插入sel，imp轉(zhuǎn)成bucket結(jié)構(gòu)體的sel和imp進行存儲
};
2.其他函數(shù)源碼
// bucketsMask用來在這_bucketsAndMaybeMask里面獲取bucket指針
static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
buckets()源碼獲取bucket指針，第一個緩存的bucket的地址
struct bucket_t *cache_t::buckets() const
{
uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
return (bucket_t *)(addr & bucketsMask);
}
occupied()源碼，獲取占用數(shù)量，即已經(jīng)插入多少個bucket
mask_t cache_t::occupied() const
{
return _occupied;
}
void incrementOccupied()源碼
void cache_t::incrementOccupied()
{
_occupied++;
}
capacity() 源碼 // 獲取容量，總共開辟了幾個緩存bucket的空間
unsigned cache_t::capacity() const
{
return mask() ? mask()+1 : 0;
}
3.cache_t 中重要的成員變量和函數(shù)說明
成員變量
1. _bucketsAndMaybeMask
explicit_atomic<uintptr_t> _bucketsAndMaybeMask;
源碼本身注釋
// _bucketsAndMaybeMask is a buckets_t pointer in the low 48 bits
// _maybeMask is unused, the mask is stored in the top 16 bits.
_bucketsAndMaybeMask (64位) = mask(數(shù)值)(高16位) + bucket指針(低48位)
存儲的mask用于mask()函數(shù)取值，存儲的bucket指針是cache緩存bucket的首地址
2. _maybeMask
explicit_atomic<mask_t> _maybeMask
64位真機里不再使用
3. _flags
uint16_t _flags;
狀態(tài)標(biāo)識，用于某些函數(shù)的計算
掩碼
// _bucketsAndMaybeMask is a buckets_t pointer in the low 48 bits
// _maybeMask is unused, the mask is stored in the top 16 bits.
1. maskShift
獲取mask需要左移的位數(shù)
static constexpr uintptr_t maskShift = 48;
mask在_bucketsAndMaybeMask64位 中的高16位，要想獲取到對應(yīng)的值需要_bucketsAndMaybeMask里面的值左移48位
2. maxMask
最大mask值，1 << (16-1) = 2 ^ 15
static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
3.bucketsMask
獲取bucket的掩碼
// The mask applied to _maskAndBuckets to retrieve the buckets pointer.
static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
函數(shù)
private
1. isConstantEmptyCache()
判斷是否位空的cache
bool isConstantEmptyCache() const;
**2. mask()**
獲取mask
mask_t mask() const;
3. incrementOccupied()
_occupied++
void incrementOccupied();
3. setBucketsAndMask()
calloc() 創(chuàng)建新的bucket指針地址，開辟空間的長度是newCapacity * sizeof(bucket_t)，sizeof(bucket_t) = 16，比如newCapacity長度為8則創(chuàng)建8個空的bucket_t存儲空間，將其首地址bucket指針和mask = newCapacity - 1 寫入_bucketsAndMaybeMask緩存數(shù)據(jù)，同時_occupied = 0，就是創(chuàng)建newCapacity個可以裝bucket_t的空間，保存起來備用
void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
3. reallocate()
開辟新的bucket_t存儲空間，如果有舊的bucket_t存儲空間，則進行釋放
void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld);
4. collect_free()
釋放舊的bucket_t存儲空，即cache里的_bucketsAndMaybeMask --> buckets()不再指向其開始的存儲空間
void collect_free(bucket_t *oldBuckets, mask_t oldCapacity);
public
1. capacity
獲取容量 capacity
unsigned capacity() const;
2. buckets()
獲取指向bucket存儲空間的首地址指針
struct bucket_t *buckets() const;
3. occupied()
獲取occupied，占用數(shù)量
mask_t occupied() const;
4. struct bucket_t部分源碼，依然是展示成員變量和主要函數(shù)
struct bucket_t {
private:
// IMP-first is better for arm64e ptrauth and no worse for arm64.
// SEL-first is better for armv7* and i386 and x86_64.
#if __arm64__
explicit_atomic<uintptr_t> _imp; // 64位真機 _imp和_sel
explicit_atomic<SEL> _sel;
#else
explicit_atomic<SEL> _sel;
explicit_atomic<uintptr_t> _imp;
#endif
public:
static inline size_t offsetOfSel() { return offsetof(bucket_t, _sel); }
inline SEL sel() const { return _sel.load(memory_order_relaxed); } // 獲取sel
inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls) const {
uintptr_t imp = _imp.load(memory_order_relaxed); // 獲取imp
if (!imp) return nil;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
SEL sel = _sel.load(memory_order_relaxed);
return (IMP)
ptrauth_auth_and_resign((const void *)imp,
ptrauth_key_process_dependent_code,
modifierForSEL(base, sel, cls),
ptrauth_key_function_pointer, 0);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
return (IMP)(imp ^ (uintptr_t)cls);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
return (IMP)imp;
#else
#error Unknown method cache IMP encoding.
#endif
}
template <Atomicity, IMPEncoding>
void set(bucket_t *base, SEL newSel, IMP newImp, Class cls); // 寫入sel和imp
};
bucket_t成員變量
1._sel和_imp
sizeof(bucket_t) = 16，兩個成員變量 8字節(jié)+8字節(jié)= 16字節(jié)
explicit_atomic<uintptr_t> _imp; // 64位真機 _imp和_sel
explicit_atomic<SEL> _sel;
bucket_t函數(shù)
1.sel()
獲取sel
inline SEL sel() const { return _sel.load(memory_order_relaxed); }
2. imp()
獲取imp
inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls) const {}
3. set()
向bucket寫入sel和imp
void set(bucket_t *base, SEL newSel, IMP newImp, Class cls);
2.cache緩存機制
通過上面的cache_t結(jié)構(gòu)體成員變量和方法解析，知道了cache_t存儲bucket_t指針，bucket_t里面有倆個成員變量_sel和_imp，用來保存方法method_t的sel和imp，
而且cache_t 存儲bucket_t 并不是像bits存儲類信息
method ---> method_list_t、
property---> property_list_t、
protocol ---> protocol_list_t、
ivar ---> ivar_list_t、
一樣使用數(shù)組的形式，而是指針的形式指向存儲bucket_t空間的首地址，
即不會有bucket_list_t這樣的情況出現(xiàn)，這是cache和bits非常大的不同？為什么這么設(shè)計，下面通過LLDB調(diào)試現(xiàn)象以及cache相關(guān)函數(shù)的源碼分析來解釋這一現(xiàn)象
1.cache LLDB調(diào)試Xcode截圖
從LLDB調(diào)試來看，cache存儲bucket有幾點疑問？
第一，bucket會丟失，可以看到并不是所有的方法都緩存到了cache里面
第二，bucket會亂序，并不是按照我們調(diào)用方法的順序進行存儲
第三，bucket不是連續(xù)存儲的，中間有空的bucket存儲空間
第四，capacity、mask、occupied三者之間有什么關(guān)系，分別是用來做什么的？
為什么會出現(xiàn)上面的三種異常的，這就要看cache存儲的底層機制是什么？從insert的源碼中尋找答案
LLDB調(diào)試對應(yīng)數(shù)據(jù)
KCObjcBuild was compiled with optimization - stepping may behave oddly; variables may not be available.
(lldb) p/x LGPerson.class
(Class) $0 = 0x00000001000086d8 LGPerson
(lldb) p (cache_t *) 0x00000001000086e8
(cache_t *) $1 = 0x00000001000086e8
(lldb) p $1->capacity()
(unsigned int) $2 = 8
(lldb) p $1->mask()
(mask_t) $3 = 7
(lldb) p $1->occupied()
(mask_t) $4 = 7
(lldb) p $1->buckets()
(bucket_t *) $5 = 0x0000000100a9bd50
(lldb) p $1->buckets()[0].sel()
(SEL) $6 = "sayWorld333"
(lldb) p $1->buckets()[0].imp(nil, LGPerson.class)
(IMP) $7 = 0x000000010000369c (KCObjcBuild`-[LGPerson sayWorld333] at main.m:100)
(lldb) p $1->buckets()[1].sel()
(SEL) $8 = "sayWorld888"
(lldb) p $1->buckets()[1].imp(nil, LGPerson.class)
(IMP) $9 = 0x0000000100003700 (KCObjcBuild`-[LGPerson sayWorld888] at main.m:106)
(lldb) p $1->buckets()[2].sel()
(SEL) $10 = "sayWorld666"
(lldb) p $1->buckets()[2].imp(nil, LGPerson.class)
(IMP) $11 = 0x00000001000036d8 (KCObjcBuild`-[LGPerson sayWorld666] at main.m:104)
(lldb) p $1->buckets()[3].sel()
(SEL) $12 = "sayWorld444"
(lldb) p $1->buckets()[3].imp(nil, LGPerson.class)
(IMP) $13 = 0x00000001000036b0 (KCObjcBuild`-[LGPerson sayWorld444] at main.m:101)
(lldb) p $1->buckets()[4].sel()
(SEL) $14 = "sayWorld222"
(lldb) p $1->buckets()[4].imp(nil, LGPerson.class)
(IMP) $15 = 0x0000000100003688 (KCObjcBuild`-[LGPerson sayWorld222] at main.m:99)
(lldb) p $1->buckets()[5].sel()
(SEL) $16 = (null)
(lldb) p $1->buckets()[5].imp(nil, LGPerson.class)
(IMP) $17 = 0x0000000000000000
(lldb) p $1->buckets()[6].sel()
(SEL) $18 = "sayWorld777"
(lldb) p $1->buckets()[6].imp(nil, LGPerson.class)
(IMP) $19 = 0x00000001000036ec (KCObjcBuild`-[LGPerson sayWorld777] at main.m:105)
(lldb) p $1->buckets()[7].sel()
(SEL) $20 = "sayWorld555"
(lldb) p $1->buckets()[7].imp(nil, LGPerson.class)
(IMP) $21 = 0x00000001000036c4 (KCObjcBuild`-[LGPerson sayWorld555] at main.m:102)
(lldb) p $1->buckets()[8].sel()
(SEL) $22 = ""
(lldb) p $1->buckets()[8].imp(nil, LGPerson.class)
(IMP) $23 = 0x0000000000000000
(lldb) p ($1 + 1)
(cache_t *) $24 = 0x00000001000086f8
(lldb) p ($1 + 2)
(cache_t *) $25 = 0x0000000100008708
(lldb) p ($1 + 3)
(cache_t *) $26 = 0x0000000100008718
(lldb) p ($1 + 4)
(cache_t *) $27 = 0x0000000100008728
(lldb) p ($1 + 5)
(cache_t *) $28 = 0x0000000100008738
(lldb) p ($1 + 6)
(cache_t *) $29 = 0x0000000100008748
(lldb) p ($1 + 7)
(cache_t *) $30 = 0x0000000100008758
(lldb) p ($1 + 8)
(cache_t *) $31 = 0x0000000100008768
(lldb) p ($1 + 9)
(cache_t *) $32 = 0x0000000100008778
(lldb) p ($1 + 10)
(cache_t *) $33 = 0x0000000100008788
(lldb)
2.insert()函數(shù)源碼
insert()函數(shù)的幾個關(guān)鍵點
1.初始化4個(arm64情況下)空的bucket存儲空間，newBucket的指針和mask寫入_bucketsAndMaybeMask，同時free掉舊的bucket存儲空間
2.存儲空間擴容，擴容的規(guī)則和算法是怎么實現(xiàn)的？
3.存儲bucket的位置是怎么確定的？
4.如何將sel和imp寫入到bucket里面去？
cache insert調(diào)用堆棧
insert()需要的一些枚舉值
/* Initial cache bucket count. INIT_CACHE_SIZE must be a power of two. */
enum {
#if CACHE_END_MARKER || (__arm64__ && !__LP64__)
// When we have a cache end marker it fills a bucket slot, so having a
// initial cache size of 2 buckets would not be efficient when one of the
// slots is always filled with the end marker. So start with a cache size
// 4 buckets.
INIT_CACHE_SIZE_LOG2 = 2,
#else
// Allow an initial bucket size of 2 buckets, since a large number of
// classes, especially metaclasses, have very few imps, and we support
// the ability to fill 100% of the cache before resizing.
INIT_CACHE_SIZE_LOG2 = 1,
#endif
INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2),
MAX_CACHE_SIZE_LOG2 = 16,
MAX_CACHE_SIZE = (1 << MAX_CACHE_SIZE_LOG2),
FULL_UTILIZATION_CACHE_SIZE_LOG2 = 3,
FULL_UTILIZATION_CACHE_SIZE = (1 << FULL_UTILIZATION_CACHE_SIZE_LOG2),
};
cache_fill_ratio()
static inline mask_t cache_fill_ratio(mask_t capacity) {
return capacity * 7 / 8;
}
#define CACHE_END_MARKER 0
cache_hash()
// Class points to cache. SEL is key. Cache buckets store SEL+IMP.
// Caches are never built in the dyld shared cache.
static inline mask_t cache_hash(SEL sel, mask_t mask)
{
uintptr_t value = (uintptr_t)sel;
#if CONFIG_USE_PREOPT_CACHES
value ^= value >> 7;
#endif
return (mask_t)(value & mask);
}
cache_next()
#if CACHE_END_MARKER
static inline mask_t cache_next(mask_t i, mask_t mask) {
return (i+1) & mask;
}
#elif __arm64__
static inline mask_t cache_next(mask_t i, mask_t mask) {
return i ? i-1 : mask;
}
#else
#error unexpected configuration
#endif
insert()函數(shù)源碼
void cache_t::insert(SEL sel, IMP imp, id receiver)
{
runtimeLock.assertLocked();
// Never cache before +initialize is done
if (slowpath(!cls()->isInitialized())) {
return;
}
if (isConstantOptimizedCache()) {
_objc_fatal("cache_t::insert() called with a preoptimized cache for %s",
cls()->nameForLogging());
}
#if DEBUG_TASK_THREADS
return _collecting_in_critical();
#else
#if CONFIG_USE_CACHE_LOCK
mutex_locker_t lock(cacheUpdateLock);
#endif
ASSERT(sel != 0 && cls()->isInitialized());
// Use the cache as-is if until we exceed our expected fill ratio.
mask_t newOccupied = occupied() + 1;
unsigned oldCapacity = capacity(), capacity = oldCapacity;
if (slowpath(isConstantEmptyCache())) { //初始化 capacity = 4
// Cache is read-only. Replace it. // capacity表示初始化多個bucket空間，容量
if (!capacity) capacity = INIT_CACHE_SIZE; // INIT_CACHE_SIZE =4 ---> 1 << 2 == 4
reallocate(oldCapacity, capacity, /* freeOld */false); // 開辟capacity 個bucket存儲空間，
//bucket首地址并與 mask一起寫入_bucketsAndMaybeMask
}
else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) {
// Cache is less than 3/4 or 7/8 full. Use it as-is.
// newOccupied + 0 <= capacity * (7/8)，如果newOccupied <= 7/8 * capacity則什么都不做，即不擴容
// capacity = 4，capacity * (7/8) = 3.5，capacity = 8，capacity * (7/8) = 7
}
#if CACHE_ALLOW_FULL_UTILIZATION
else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) {
// Allow 100% cache utilization for small buckets. Use it as-is.
// capacity <= 8 && newOccupied + 0 <= capacity，即newOccupied = 4的時候什么也不做
}
#endif
else {
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE; // 擴容2倍，否則兩倍擴容，
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;
}
reallocate(oldCapacity, capacity, true); // true ---> free 掉舊的bucket存儲空間
}
bucket_t *b = buckets(); // 獲取bucket指針，首地址
mask_t m = capacity - 1; // m ---> mask 與capacity的關(guān)系是 mask = capacity - 1
mask_t begin = cache_hash(sel, m); //哈希算法函數(shù)利用sel的唯一性大概率begin不會重復(fù)
mask_t i = begin; // begin保持最初的哈希值，即下標(biāo)，i動態(tài)變化尋找空的bucket存儲空間存入sel和imp
// 哈希算法 uintptr_t value = (uintptr_t)sel; ---> (value & mask)
// 由于m = capacity - 1，所以任何值按位與上都是0-7之間
//即 capacity = 4， begin = 0-->3，capacity = 8， began = 0-->7
// Scan for the first unused slot and insert there.
// There is guaranteed to be an empty slot.
do {
if (fastpath(b[i].sel() == 0)) { // == 0表示位空，則寫入sel和imp
incrementOccupied(); // _occupied++
b[i].set<Atomic, Encoded>(b, sel, imp, cls());// bucket寫入sel和imp
return; //寫入后返回
}
if (b[i].sel() == sel) { //如果已經(jīng)存儲了sel則返回
// The entry was added to the cache by some other thread
// before we grabbed the cacheUpdateLock.
return;
}
} while (fastpath((i = cache_next(i, m)) != begin));
// 如果最初的哈希值begin對應(yīng)的bucket[i]有值且bucket[i]不等于要寫入的sel，稱為哈希沖突，則進行二次哈希
// static inline mask_t cache_next(mask_t i, mask_t mask) {
// return i ? i-1 : mask;
//}
// 假設(shè) i = 0的位置寫入了a的sel，假設(shè)capacity = 4，則 m = 3， 后面又b，c，d的sel和imp需要寫入
// { a_sel }，{ }，{ }，{ }
// 此時如果b的哈希值 在 1-3之間，則走第一個if判斷直接在對應(yīng)的bucket[i] = bucket[begin]位置上寫入sel和imp
// cache_next是第二次哈希，用于處理第一次哈希下標(biāo)begin的位置上，bucket已經(jīng)寫入sel和imp了，假設(shè)b的哈希值begin = 0，
// 則i = cache_nex(i, m) = 3，3! = 0，滿足while條件執(zhí)行兩個if分支，第一個if在b[3]上寫入sel和imp
// { a_sel, a_imp}，{ }，{ }，{ b_sel, b_imp}
// 此時c放來了，begin = 3，cache_next后 i = 2，第一個if在b[2]上寫入sel和imp
// { a_sel, a_imp}，{ }，{ c_sel, c_imp }，{ b_sel, b_imp}
// 此時c放來了，begin = 0，cache_next后 i = 3，再次cache_next后 i = 2，第一個if在b[2]上寫入sel和imp
// { a_sel, a_imp}，{ }，{ c_sel, c_imp }，{ b_sel, b_imp}
// 總之，如果沒有哈希沖突b[i]位置直接寫入sel和imp，如果有哈希沖突的話
// i = 1 ---> i = 0
// i = 0 ---> i = 3
// i = 3 ---> i = 2
// i = 2 ---> i = 1
// 由于容量capacity肯定是夠存儲的，加上cache_next 這種算法，一定可以找到空的bucket寫入sel和imp
// i = 1 ---> i = 0
// i = 0 ---> i = m
// i = m ---> i = m - 1
// i = m - 1 ---> i = m - 2
bad_cache(receiver, (SEL)sel);
#endif // !DEBUG_TASK_THREADS
}
insert()函數(shù)主要流程
1.初始化 ---> 2.擴容 ---> 3.bucket寫入準(zhǔn)備 ---> 4.do-while循環(huán)寫入sel和imp到bucket
1.初始化
確定capacity和開辟與capacity對應(yīng)的新的空的bucket存儲空間，bucket首地址指針和mask寫入_bucketsAndMaybeMask，由于沒有舊的bucket指針，所以，不會free舊的bucket存儲空間
2.擴容
擴容條件達到后， 即newOccupied > capacity * (7/8)
擴容兩倍capacity = capacity * 2 ，開辟與capacity對應(yīng)的新的空的bucket存儲空間，bucket首地址指針和mask寫入_bucketsAndMaybeMask，并且free掉舊的bucket存儲空間
3.bucket寫入準(zhǔn)備
do - while寫入之前準(zhǔn)備數(shù)據(jù)
bucket_t *b = buckets(); 拿到bucket指針
mask_t m = capacity - 1; 確定下標(biāo)范圍 0 - m
mask_t begin = cache_hash(sel, m); sel和m哈希后得到初始存儲下標(biāo)begin，0-m之間隨機的
mask_t i = begin; i變動下標(biāo)賦初值
4.do-while循環(huán)寫入sel和imp到bucket
do - while循環(huán)寫入
b[i].sel() == 0，沒有寫入sel和imp，則直接寫入
b[i].sel() == sel，要寫入的sel和imp已經(jīng)寫入到了b[i]的位置上，則什么都不做
b[i]已經(jīng)寫入sel和imp并且不是要寫入的sel和imp，則二次哈希尋找其他可以寫入的位置
由于cache_next()的算法和capacity足夠大，一定會找到可以寫入sel和imp的bucket
LLDB調(diào)試的幾個疑點解答
第一，bucket會丟失，可以看到并不是所有的方法都緩存到了cache里面
原因是擴容后會free掉舊的bucket存儲空間，只緩存觸發(fā)擴容的這個方法，所以，bucket會丟失
第二，bucket會亂序，并不是按照我們調(diào)用方法的順序進行存儲
因為b[i]中的緩存下標(biāo)是用sel和mask哈希后的值，如果哈希沖突還要進行二次哈希，所以是一個隨機值，在0-mask之間
第三，bucket不是連續(xù)存儲的，中間有空的bucket存儲空間
同樣，b[i]下標(biāo)是sel和mask哈希后或者二次哈希的，存儲順序并不是調(diào)用順序，有空的是因為reallocate()函數(shù)，開辟capacity個新的、空的、bucket存儲空間，然后將bucket指針和mask寫入到_bucketsAndMaybeMask，存儲是隨機的所以會有空的bucket存在
第四，capacity、mask、occupied三者之間有什么關(guān)系，分別是用來做什么的？
capacity容量，即創(chuàng)建多少個空的bucket空間
mask掩碼，確定存儲下標(biāo)， 0-mask之間，mask = capacity - 1
occupied，已經(jīng)占用多少個bucket存儲空間，即寫入了多少次sel和imp
insert()內(nèi)部關(guān)鍵函數(shù)reallocate
1. reallocate()
核心三點
第一，allocateBuckets() ---> calloc()開辟ewCapacity個bucket存儲空間
第二，setBucketsAndMask() ---> 新開辟的bucket存儲空間和newCapacity寫入_bucketsAndMaybeMask
第三，collect_free() ---> collect_free掉舊的bucket存儲空間
第一和第二容易理解，開辟對應(yīng)個數(shù)的bucket存儲空間，保存起來
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
bucket_t *oldBuckets = buckets();
bucket_t *newBuckets = allocateBuckets(newCapacity); //臨時變量
// 開辟newCapacity個bucket存儲空間，新的空的，newBuckets首地址指針
// Cache's old contents are not propagated.
// This is thought to save cache memory at the cost of extra cache fills.
// fixme re-measure this
ASSERT(newCapacity > 0);
ASSERT((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
setBucketsAndMask(newBuckets, newCapacity - 1); //存儲newBuckets，空格，空格，沒有存儲sel和imp
//newBuckets首地址指針和mask寫入_bucketsAndMaybeMask
if (freeOld) {
collect_free(oldBuckets, oldCapacity); //舊的free掉，所以會有丟失
}
}
allocateBuckets()
calloc()開辟newCapacity個bucket存儲空間
bucket_t *cache_t::allocateBuckets(mask_t newCapacity)
{
if (PrintCaches) recordNewCache(newCapacity);
return (bucket_t *)calloc(bytesForCapacity(newCapacity), 1); // calloc開辟內(nèi)存，轉(zhuǎn)換為bucket_t *
}
**```bytesForCapacity()```**
size_t cache_t::bytesForCapacity(uint32_t cap)
{
return sizeof(bucket_t) * cap;
}
setBucketsAndMask()
新的空的newBuckets首地址指針和mask存入_bucketsAndMaybeMask成員變量，同時_occupied = 0 清零
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
uintptr_t buckets = (uintptr_t)newBuckets;
uintptr_t mask = (uintptr_t)newMask;
ASSERT(buckets <= bucketsMask);
ASSERT(mask <= maxMask);
// 新的bucket指針，newBuckets和mask寫入_bucketsAndMaybeMask
// (uintptr_t)newMask << maskShift，mask左移48位存儲在高16位
// newMask 和newBuckets 或 | 操作，各自存儲相互不影響，
// newMask低48位是0，newBuckets高16位是0
_bucketsAndMaybeMask.store(((uintptr_t)newMask << maskShift) | (uintptr_t)newBuckets, memory_order_relaxed);
_occupied = 0; // occupied 清零
}
mask()
獲取mask ---> _bucketsAndMaybeMask成員變量通過maskShift掩碼獲取``mask```
mask_t cache_t::mask() const
{
uintptr_t maskAndBuckets = _bucketsAndMaybeMask.load(memory_order_relaxed);
return maskAndBuckets >> maskShift; // 通過maskShift獲取mask，高16位的值
}
2. collect_free()
觸發(fā)節(jié)點
free舊的bucket存儲空間的觸發(fā)節(jié)點是擴容后，開辟新的free舊的，并不一定真的會free掉，只是cache的bucket指針不再指向該空間，實現(xiàn)了cache_::buckets() 邏輯上面的剝離
核心邏輯
1.malloc()或者realloc()標(biāo)記這段地址空間，已經(jīng)被使用，系統(tǒng)開辟空間不會占用到該段內(nèi)存
2.每次擴容后地址空間累計，一段一段的累計，用一個二級指針存儲舊的buckets指針，用這一次舊的bucket緩存在二級指針的最后，，garbage_count++標(biāo)記二級指針的下標(biāo)
也就是數(shù)組的最后，比如第一次8個地址需要標(biāo)記為已經(jīng)被使用，則bucket指針指向二級指針的下標(biāo)index = 7的位置，第二次16個，則指向index = 15的位置，真正觸發(fā)c函數(shù)free()地址空間的時候，倒序輸出
由于有舊的bucket指針做指向，所以，bucket垃圾回收空間就是擴容之前的舊的bucket指向的空間，征用被標(biāo)記為已經(jīng)被使用且沒有賦初值，所以依然保存原值，即地址空間內(nèi)的值是真實的擴容之前的cache 的buckets指向的那段內(nèi)存
3.符合條件觸發(fā)真正的c語言函數(shù) free(dead); free掉指向bucket的指針，這里的條件有兩個
第一，是累計標(biāo)記為被使用的空間 >= 32K = 32 * 1024，小于32K，則return返回
第二，objc_msgSend或者其他的 cache reader 沒有正在訪問該段內(nèi)存且有可能會用到里面的buckets信息
簡單理解就是超長垃圾回收存儲空間的閾值，該段內(nèi)存沒有再繼續(xù)被使用了
第一點的源碼內(nèi)英文注釋
// Done if the garbage is not full
第二點的源碼內(nèi)英文注釋
// Synchronize collection with objc_msgSend and other cache readers
// objc_msgSend (or other cache reader) is currently looking in
// the cache and might still be using some garbage.
只有兩個條件同時滿足才會觸發(fā)真正的c語言函數(shù)free()，其他情況都是標(biāo)記為已經(jīng)被使用，系統(tǒng)開辟空間不會占用到該段內(nèi)存，cache的buckets不再指向，默默的備用狀態(tài)
1.collect_free()
void cache_t::collect_free(bucket_t *data, mask_t capacity)
{
#if CONFIG_USE_CACHE_LOCK
cacheUpdateLock.assertLocked();
#else
runtimeLock.assertLocked();
#endif
if (PrintCaches) recordDeadCache(capacity);
// 舊的bucket存儲空間被標(biāo)記為已經(jīng)使用，malloc(),realloc()
_garbage_make_room ();
// 垃圾回收空間累加器累計本次舊的buckets存儲空間的長度，
// 這里是字節(jié)數(shù)，不是sizeof(bucket_t)的數(shù)值，即sizeof(bucket_t) * capacity
garbage_byte_size += cache_t::bytesForCapacity(capacity);
// 舊的bucket指針，指向最后面，用于collectNolock倒序free指針
garbage_refs[garbage_count++] = data;
// 有條件調(diào)用c語言函數(shù) free()，真正釋放掉舊的bucket指向的空間，不滿足條件則只是標(biāo)記為被使用
// 地址空間內(nèi)的值，依然是舊的bucket存儲的sel和imp，轉(zhuǎn)為默默的備用狀態(tài)
cache_t::collectNolock(false);
}
// capacity of initial garbage_refs
enum {
INIT_GARBAGE_COUNT = 128 // 128 / sizeof(bucket_t) = 128 / 16 = 8，剛好8個字節(jié)
};
2.第一次擴容
arm64情況下，第一次擴容是8個字節(jié)，reallocate(oldCapacity, capacity, true);最后一個傳true表示需要collect_free ---> /* freeOld */
else { // 滿足擴容條件
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE; // 擴容2倍
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;
}
reallocate(oldCapacity, capacity, true); //開辟新的buckets空間，collect_free舊的buckets空間
}
2.第一次擴容觸發(fā)節(jié)點
// amount of memory represented by all refs in the garbage
static size_t garbage_byte_size = 0; // 垃圾回收空間累加器，
//標(biāo)記為被使用地址空間的長度字節(jié)數(shù)
// do not empty the garbage until garbage_byte_size gets at least this big
static size_t garbage_threshold = 32*1024; // 最大的垃圾回收閾值，32k，小于32k則什么都不做
// table of refs to free
static bucket_t **garbage_refs = 0; // 二級指針，指向指針的指針
// current number of refs in garbage_refs
static size_t garbage_count = 0; //累計地址空間下標(biāo)
// capacity of current garbage_refs
static size_t garbage_max = 0; //標(biāo)記為被使用最大的字節(jié)數(shù)，這里不是sizeof(bucket_t)的數(shù)量
// capacity of initial garbage_refs
enum {
INIT_GARBAGE_COUNT = 128 // 128 / sizeof(bucket_t) = 128 / 16 = 8，剛好8個字節(jié)，第次剛好8個字節(jié)
};
3._garbage_make_room()
舊的bucket指向空間標(biāo)記為被使用
static void _garbage_make_room(void)
{
static int first = 1;
// Create the collection table the first time it is needed
if (first) //第一次，8個字節(jié)空間被標(biāo)記為已經(jīng)被使用
{ // INIT_GARBAGE_COUNT = 128, 128 / sizeof(bucket_t) = 128 / 16 = 8，剛好8個字節(jié)
first = 0;
garbage_refs = (bucket_t**)
malloc(INIT_GARBAGE_COUNT * sizeof(void *));
garbage_max = INIT_GARBAGE_COUNT;// garbage_max垃圾回收存儲空間最大值賦初值
}
// 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; // garbage_max垃圾回收存儲空間最大值每次擴容兩倍
// bucket_t *newBuckets = allocateBuckets(newCapacity);
// 剛好和cache bucket兩倍擴容完全對應(yīng)上，完美標(biāo)記為被使用，指針地址安全
// 由于有舊的bucket指針做指向，所以，bucket垃圾回收空間就是擴容之前的
// 舊的bucket指向的空間，征用被標(biāo)記為已經(jīng)被使用且沒有賦初值，所以依然保存原值
// 即地址空間內(nèi)是真實的擴容之前的cache 的buckets指向的那段內(nèi)存
}
}
4. collectNolock()
有條件觸發(fā)真正的c語言函數(shù)free()，釋放舊的buckets指向的空間，倒序釋放
void cache_t::collectNolock(bool collectALot)
{
#if CONFIG_USE_CACHE_LOCK
cacheUpdateLock.assertLocked();
#else
runtimeLock.assertLocked();
#endif
// Done if the garbage is not full
if (garbage_byte_size < garbage_threshold && !collectALot) {
return; // collectALot = false，garbage_byte_size垃圾回收空間累加器
//小于垃圾回收閾值32k，則返回 ，什么都不做
}
// Synchronize collection with objc_msgSend and other cache readers
if (!collectALot) { // collectALot = false，指向分支
if (_collecting_in_critical ()) { // 是否處于objc_msgSend (or other cache reader)
// 正在查看或者有可能使用垃圾回收空間的數(shù)據(jù)的臨界狀態(tài)，如果是則返回，什么都不做
// objc_msgSend (or other cache reader) is currently looking in
// the cache and might still be using some garbage.
if (PrintCaches) {
_objc_inform ("CACHES: not collecting; "
"objc_msgSend in progress");
}
return;
}
}
else {
// No excuses.
while (_collecting_in_critical())
;
}
// No cache readers in progress - garbage is now deletable
// Log our progress
if (PrintCaches) {
cache_collections++;
_objc_inform ("CACHES: COLLECTING %zu bytes (%zu allocations, %zu collections)", garbage_byte_size, cache_allocations, cache_collections);
}
// 超過閾值32K并且沒有被使用，則真正的會釋放掉，調(diào)用c語言的free()函數(shù)
// Dispose all refs now in the garbage
// Erase each entry so debugging tools don't see stale pointers.
while (garbage_count--) { // 倒序輸出
auto dead = garbage_refs[garbage_count]; // 去除指針
garbage_refs[garbage_count] = nil; // 指針= nil，避免野指針
free(dead); // 釋放指向的空間
}
// Clear the garbage count and total size indicator
garbage_count = 0; //二級指針index下標(biāo)清零
garbage_byte_size = 0; // 垃圾回收空間累加器清零
if (PrintCaches) {
size_t I;
size_t total_count = 0;
size_t total_size = 0;
for (i = 0; i < countof(cache_counts); i++) {
int count = cache_counts[I];
int slots = 1 << I;
size_t size = count * slots * sizeof(bucket_t);
if (!count) continue;
_objc_inform("CACHES: %4d slots: %4d caches, %6zu bytes",
slots, count, size);
total_count += count;
total_size += size;
}
_objc_inform("CACHES: total: %4zu caches, %6zu bytes",
total_count, total_size);
}
}
4.總結(jié)
cache insert 整體流程圖
