cache_t結(jié)構(gòu).png
數(shù)據(jù)結(jié)構(gòu)：
struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
explicit_atomic<struct bucket_t *> _buckets;
explicit_atomic<mask_t> _mask;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
explicit_atomic<uintptr_t> _maskAndBuckets;
mask_t _mask_unused;
// How much the mask is shifted by.
static constexpr uintptr_t maskShift = 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.
static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
// The mask applied to `_maskAndBuckets` to retrieve the buckets pointer.
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.");
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
// _maskAndBuckets stores the mask shift in the low 4 bits, and
// the buckets pointer in the remainder of the value. The mask
// shift is the value where (0xffff >> shift) produces the correct
// mask. This is equal to 16 - log2(cache_size).
explicit_atomic<uintptr_t> _maskAndBuckets;
mask_t _mask_unused;
static constexpr uintptr_t maskBits = 4;
static constexpr uintptr_t maskMask = (1 << maskBits) - 1;
static constexpr uintptr_t bucketsMask = ~maskMask;
#else
#error Unknown cache mask storage type.
#endif
#if __LP64__
uint16_t _flags;
#endif
uint16_t _occupied;
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();
#if __LP64__
bool getBit(uint16_t flags) const {
return _flags & flags;
}
void setBit(uint16_t set) {
__c11_atomic_fetch_or((_Atomic(uint16_t) *)&_flags, set, __ATOMIC_RELAXED);
}
void clearBit(uint16_t clear) {
__c11_atomic_fetch_and((_Atomic(uint16_t) *)&_flags, ~clear, __ATOMIC_RELAXED);
}
#endif
#if FAST_CACHE_ALLOC_MASK
bool hasFastInstanceSize(size_t extra) const
{
if (__builtin_constant_p(extra) && extra == 0) {
return _flags & FAST_CACHE_ALLOC_MASK16;
}
return _flags & FAST_CACHE_ALLOC_MASK;
}
size_t fastInstanceSize(size_t extra) const
{
ASSERT(hasFastInstanceSize(extra));
if (__builtin_constant_p(extra) && extra == 0) {
return _flags & FAST_CACHE_ALLOC_MASK16;
} else {
size_t size = _flags & FAST_CACHE_ALLOC_MASK;
// remove the FAST_CACHE_ALLOC_DELTA16 that was added
// by setFastInstanceSize
return align16(size + extra - FAST_CACHE_ALLOC_DELTA16);
}
}
void setFastInstanceSize(size_t newSize)
{
// Set during realization or construction only. No locking needed.
uint16_t newBits = _flags & ~FAST_CACHE_ALLOC_MASK;
uint16_t sizeBits;
// Adding FAST_CACHE_ALLOC_DELTA16 allows for FAST_CACHE_ALLOC_MASK16
// to yield the proper 16byte aligned allocation size with a single mask
sizeBits = word_align(newSize) + FAST_CACHE_ALLOC_DELTA16;
sizeBits &= FAST_CACHE_ALLOC_MASK;
if (newSize <= sizeBits) {
newBits |= sizeBits;
}
_flags = newBits;
}
#else
bool hasFastInstanceSize(size_t extra) const {
return false;
}
size_t fastInstanceSize(size_t extra) const {
abort();
}
void setFastInstanceSize(size_t extra) {
// nothing
}
#endif
static size_t bytesForCapacity(uint32_t cap);
static struct bucket_t * endMarker(struct bucket_t *b, uint32_t cap);
void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld);
void insert(Class cls, SEL sel, IMP imp, id receiver);
static void bad_cache(id receiver, SEL sel, Class isa) __attribute__((noreturn, cold));
};
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;
explicit_atomic<SEL> _sel;
#else
explicit_atomic<SEL> _sel;
explicit_atomic<uintptr_t> _imp;
#endif
// Compute the ptrauth signing modifier from &_imp, newSel, and cls.
uintptr_t modifierForSEL(SEL newSel, Class cls) const {
return (uintptr_t)&_imp ^ (uintptr_t)newSel ^ (uintptr_t)cls;
}
// Sign newImp, with &_imp, newSel, and cls as modifiers.
uintptr_t encodeImp(IMP newImp, SEL newSel, Class cls) const {
if (!newImp) return 0;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
return (uintptr_t)
ptrauth_auth_and_resign(newImp,
ptrauth_key_function_pointer, 0,
ptrauth_key_process_dependent_code,
modifierForSEL(newSel, cls));
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
return (uintptr_t)newImp ^ (uintptr_t)cls;
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
return (uintptr_t)newImp;
#else
#error Unknown method cache IMP encoding.
#endif
}
public:
inline SEL sel() const { return _sel.load(memory_order::memory_order_relaxed); }
inline IMP imp(Class cls) const {
uintptr_t imp = _imp.load(memory_order::memory_order_relaxed);
if (!imp) return nil;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
SEL sel = _sel.load(memory_order::memory_order_relaxed);
return (IMP)
ptrauth_auth_and_resign((const void *)imp,
ptrauth_key_process_dependent_code,
modifierForSEL(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(SEL newSel, IMP newImp, Class cls);
};
LLDB調(diào)試
#import <Foundation/Foundation.h>
#import "LGPerson.h"
#import <objc/runtime.h>
// cache_t
int main(int argc, const char * argv[]) {
@autoreleasepool {
LGPerson *p = [LGPerson alloc];
Class pClass = [LGPerson class];
// p.lgName = @"Cooci";
// p.nickName = @"KC";
// 緩存一次方法 sayHello
[p sayHello];
[p sayCode];
[p sayMaster];
// [p sayNB];
NSLog(@"%@",pClass);
}
return 0;
}
控制臺(tái)輸出：
/*
(lldb) p/x pClass
(Class) $0 = 0x0000000100008298 LGPerson
(lldb) p (cache_t *)0x00000001000082a8
(cache_t *) $1 = 0x00000001000082a8
(lldb) p *$1
(cache_t) $2 = {
_buckets = {
std::__1::atomic<bucket_t *> = {
Value = 0x0000000100347430
}
}
_mask = {
std::__1::atomic<unsigned int> = {
Value = 0
}
}
_flags = 32804
_occupied = 0
}
(lldb) p $2.buckets()
(bucket_t *) $3 = 0x0000000100347430
(lldb) p *$3
(bucket_t) $4 = {
_sel = {
std::__1::atomic<objc_selector *> = (null) {
Value = (null)
}
}
_imp = {
std::__1::atomic<unsigned long> = {
Value = 0
}
}
}
(lldb) p $4.sel()
(SEL) $5 = <no value available>
2021-01-17 16:03:43.912443+0800 KCObjc[67437:1764005] LGPerson say : -[LGPerson sayHello]
(lldb) p $2.buckets()
(bucket_t *) $6 = 0x0000000100607330
(lldb) p *$6
(bucket_t) $7 = {
_sel = {
std::__1::atomic<objc_selector *> = "" {
Value = ""
}
}
_imp = {
std::__1::atomic<unsigned long> = {
Value = 48792
}
}
}
(lldb) p $7.sel()
(SEL) $8 = "sayHello"
(lldb) p $7.imp(pClass)
(IMP) $9 = 0x0000000100003c00 (KCObjc`-[LGPerson sayHello])
2021-01-17 16:05:31.068273+0800 KCObjc[67437:1764005] LGPerson say : -[LGPerson sayCode]
(lldb) p $2.buckets()
(bucket_t *) $10 = 0x0000000100607330
(lldb) p *$10
(bucket_t) $11 = {
_sel = {
std::__1::atomic<objc_selector *> = "" {
Value = ""
}
}
_imp = {
std::__1::atomic<unsigned long> = {
Value = 48792
}
}
}
(lldb) p $2.buckets()[1]
(bucket_t) $12 = {
_sel = {
std::__1::atomic<objc_selector *> = "" {
Value = ""
}
}
_imp = {
std::__1::atomic<unsigned long> = {
Value = 48808
}
}
}
(lldb) p $12.sel()
(SEL) $13 = "sayCode"
(lldb) p $2.buckets()[2]
(bucket_t) $14 = {
_sel = {
std::__1::atomic<objc_selector *> = (null) {
Value = (null)
}
}
_imp = {
std::__1::atomic<unsigned long> = {
Value = 0
}
}
}
(lldb) p $14.sel()
(SEL) $15 = <no value available>
(lldb)
*/
Cooci 關(guān)于Cache_t原理分析圖.png
/***********************************************************************
* Method cache locking (GrP 2001-1-14)
*
* For speed, objc_msgSend does not acquire any locks when it reads
* method caches. Instead, all cache changes are performed so that any
* objc_msgSend running concurrently with the cache mutator will not
* crash or hang or get an incorrect result from the cache.
*
* When cache memory becomes unused (e.g. the old cache after cache
* expansion), it is not immediately freed, because a concurrent
* objc_msgSend could still be using it. Instead, the memory is
* disconnected from the data structures and placed on a garbage list.
* The memory is now only accessible to instances of objc_msgSend that
* were running when the memory was disconnected; any further calls to
* objc_msgSend will not see the garbage memory because the other data
* structures don't point to it anymore. The collecting_in_critical
* function checks the PC of all threads and returns FALSE when all threads
* are found to be outside objc_msgSend. This means any call to objc_msgSend
* that could have had access to the garbage has finished or moved past the
* cache lookup stage, so it is safe to free the memory.
*
* All functions that modify cache data or structures must acquire the
* cacheUpdateLock to prevent interference from concurrent modifications.
* The function that frees cache garbage must acquire the cacheUpdateLock
* and use collecting_in_critical() to flush out cache readers.
* The cacheUpdateLock is also used to protect the custom allocator used
* for large method cache blocks.
*
* Cache readers (PC-checked by collecting_in_critical())
* objc_msgSend*
* cache_getImp
*
* Cache writers (hold cacheUpdateLock while reading or writing; not PC-checked)
* cache_fill (acquires lock)
* cache_expand (only called from cache_fill)
* cache_create (only called from cache_expand)
* bcopy (only called from instrumented cache_expand)
* flush_caches (acquires lock)
* cache_flush (only called from cache_fill and flush_caches)
* cache_collect_free (only called from cache_expand and cache_flush)
*
* UNPROTECTED cache readers (NOT thread-safe; used for debug info only)
* cache_print
* _class_printMethodCaches
* _class_printDuplicateCacheEntries
* _class_printMethodCacheStatistics
*
***********************************************************************/
疑問(wèn)解答
1、_mask是什么？
_mask是指掩碼數(shù)據(jù)，用于在哈希算法或者哈希沖突算法中計(jì)算哈希下標(biāo)，其中mask 等于capacity - 1。
2、_occupied 是什么？
_occupied表示哈希表中 sel-imp 的占用大小 (即可以理解為分配的內(nèi)存中已經(jīng)存儲(chǔ)了sel-imp的的個(gè)數(shù))。
1）init會(huì)導(dǎo)致occupied變化
2）屬性賦值，也會(huì)隱式調(diào)用，導(dǎo)致occupied變化
3）方法調(diào)用，導(dǎo)致occupied變化
3、為什么隨著方法調(diào)用的增多，其打印的occupied 和 mask會(huì)變化？
因?yàn)樵赾ache初始化時(shí)，分配的空間是4個(gè)，隨著方法調(diào)用的增多，當(dāng)存儲(chǔ)的sel-imp個(gè)數(shù)，即newOccupied + CACHE_END_MARKER（等于1）的和 超過(guò) 總?cè)萘康?/4,例如有4個(gè)時(shí)，當(dāng)occupied等于2時(shí)，就需要對(duì)cache的內(nèi)存進(jìn)行兩倍擴(kuò)容
4、bucket數(shù)據(jù)為什么會(huì)有丟失的情況？
原因是在擴(kuò)容時(shí)，是將原有的內(nèi)存全部清除了，再重新申請(qǐng)了內(nèi)存導(dǎo)致的。
5、2-7中say3、say4的打印順序?yàn)槭裁词莝ay4先打印，say3后打印，且還是挨著的，即順序有問(wèn)題 。
因?yàn)閟el-imp的存儲(chǔ)是通過(guò)哈希算法計(jì)算下標(biāo)的，其計(jì)算的下標(biāo)有可能已經(jīng)存儲(chǔ)了sel，所以又需要通過(guò)哈希沖突算法重新計(jì)算哈希下標(biāo)，所以導(dǎo)致下標(biāo)是隨機(jī)的，并不是固定的。
6、打印的 cache_t 中的 ocupied 為什么是從 2 開(kāi)始？
這里是因?yàn)長(zhǎng)GPerson通過(guò)alloc創(chuàng)建的對(duì)象，并對(duì)其兩個(gè)屬性賦值的原因，屬性賦值，會(huì)隱式調(diào)用set方法，set方法的調(diào)用也會(huì)導(dǎo)致occupied變化。
