前言
在《類(lèi)的探究分析》一文中詳細(xì)地分析了類(lèi)結(jié)構(gòu)的bits成員，但是除此之外cache成員也是非常重要的这难。那么cache中保存了什么信息？我們驗(yàn)證流程是怎么樣的衔肢？cache底層代碼流程是怎么樣子的赌髓？那我們下面就進(jìn)行探索了喔！
類(lèi)結(jié)構(gòu)回顧
struct objc_class : objc_object {
//Class ISA; //isa是隱藏成員 占8字節(jié)
Class superclass; //占8字節(jié)
cache_t cache; //占16字節(jié)
class_data_bits_t bits;
};
cache存在的必要性
在類(lèi)方法調(diào)用的過(guò)程中比规，我們知道是通過(guò)方法的SEL（方法編號(hào)）在內(nèi)存中尋找對(duì)應(yīng)的IMP（方法指針），最后找到方法的實(shí)現(xiàn)拦英。為了避免每次尋找方法都要循環(huán)遍歷類(lèi)的方法列表苞俘，使方法響應(yīng)更加快速，效率更高龄章，cache_t結(jié)構(gòu)體出現(xiàn)了吃谣。cache_t將調(diào)用過(guò)的方法的SEL和IMP以及receiver以bucket_t結(jié)構(gòu)體方式存儲(chǔ)在當(dāng)前類(lèi)結(jié)構(gòu)中，以便后續(xù)方法的查找做裙。
cache_t結(jié)構(gòu)分析
struct cache_t {
private:
explicit_atomic<uintptr_t> _bucketsAndMaybeMask; //占8字節(jié)
union {
struct {
explicit_atomic<mask_t> _maybeMask; // 占4字節(jié)
#if __LP64__
uint16_t _flags; //占2字節(jié)
#endif
uint16_t _occupied; // 占2字節(jié)
};
explicit_atomic<preopt_cache_t *> _originalPreoptCache; // 占8字節(jié)
};
//此處省略部分代碼
......
//以下是提供的方法
void insert(SEL sel, IMP imp, id receiver);
void copyCacheNolock(objc_imp_cache_entry *buffer, int len);
void destroy();
void eraseNolock(const char *func);
static void init();
static void collectNolock(bool collectALot);
static size_t bytesForCapacity(uint32_t cap);
//此處省略部分代碼
......
分析：
-
_bucketsAndMaybeMask是uintptr_t（無(wú)符號(hào)長(zhǎng)整形）類(lèi)型的岗憋，占內(nèi)存8字節(jié)。里面存放著一個(gè)地址锚贱。 -
union（聯(lián)合體）中有一個(gè)結(jié)構(gòu)體仔戈，_originalPreoptCache是結(jié)構(gòu)體指針。 - 結(jié)構(gòu)體中有三個(gè)成員變量
（_maybeMask、_flags监徘、_occupied）晋修，__LP64__指的是Unix（linux）或者macOS系統(tǒng)。-
_maybeMask：當(dāng)前的緩存區(qū)count凰盔，第一次開(kāi)辟是3墓卦。 -
_occupied：當(dāng)前cache的可存儲(chǔ)的buckets數(shù)量，默認(rèn)是0户敬。
-
- 在
union（聯(lián)合體）中落剪，結(jié)構(gòu)體跟_originalPreoptCache是互斥的。_originalPreoptCache初始時(shí)候的緩存尿庐。 -
cache_t結(jié)構(gòu)體中提供了一些方法去取值忠怖，其中buckets()方法就是我們需要的。
在觀察cache_t結(jié)構(gòu)里面的方法時(shí)候抄瑟，最直觀的就是insert()方法凡泣，參數(shù)是SEL和IMP。然后進(jìn)入insert方法的實(shí)現(xiàn)皮假，發(fā)現(xiàn)是對(duì)buckets的操作问麸，同樣我們也在cache_t結(jié)構(gòu)里面找到了buckets()方法，那么我們可以猜測(cè)buckets()方法可以拿到一些信息钞翔。
bucket_t結(jié)構(gòu)
struct bucket_t {
private:
#if __arm64__
explicit_atomic<uintptr_t> _imp;
explicit_atomic<SEL> _sel;
#else
explicit_atomic<SEL> _sel;
explicit_atomic<uintptr_t> _imp;
#endif
分析：
-
bucket_t結(jié)構(gòu)體中存放著imp（方法指針）和sel（方法編號(hào)）。 - 在
arm64架構(gòu)下席舍，先存放imp（方法指針）再存放sel（方法編號(hào)）布轿。 - 非
arm64架構(gòu)下，先存放sel（方法編號(hào)）再存放imp（方法指針）来颤。 -
cache里面存的是方法汰扭。
總結(jié)
cache結(jié)構(gòu)對(duì)應(yīng)關(guān)系
LLDB調(diào)試cache
【第一步：創(chuàng)建LGPersion類(lèi)】
@interface LGPerson : NSObject
@property (nonatomic, copy) NSString *name;
@property (nonatomic) int age;
@property (nonatomic, strong) NSString *hobby;
//創(chuàng)建兩個(gè)方法
- (void)saySomething;
- (void)sayNB;
@end
【第二步：lldb調(diào)試】
1.在類(lèi)沒(méi)有調(diào)用任何方法的時(shí)候：
lldb調(diào)試1.0
lldb調(diào)試1.1
2.lldb調(diào)用
LGPersion方法，再查看cache情況：
lldb調(diào)試2.0
lldb調(diào)試2.1
lldb調(diào)試2.2
lldb調(diào)試2.3
lldb調(diào)試2.4
查看有方法的bucket內(nèi)容：
lldb調(diào)試2.5
3.代碼調(diào)用
LGPersion方法福铅，lldb不調(diào)用LGPerson類(lèi)的方法,再查看cache情況：
lldb調(diào)試3.0
lldb調(diào)試3.1
lldb調(diào)試3.2
只用代碼調(diào)用sayNB和saySomething兩個(gè)方法呢
lldb調(diào)試3.3
lldb調(diào)試3.4
lldb調(diào)試3.5
總結(jié)：
-
buckets容器最后一個(gè)成員存放著其首地址萝毛。 -
lldb調(diào)用類(lèi)的方法時(shí)候底層會(huì)調(diào)用class與respondSelecter:方法（查看llvm源碼）。 -
lldb調(diào)用類(lèi)的方法時(shí)候buckets容器會(huì)進(jìn)行擴(kuò)容滑黔。 -
buckets不是數(shù)組笆包，而是一個(gè)哈希鏈表（無(wú)規(guī)則存放成員）。 - 哈希鏈表存在這一個(gè)臨界容量
（3/4）,當(dāng)超過(guò)容器容量的3/4時(shí)候會(huì)進(jìn)行擴(kuò)容略荡，這樣子能有效的減少哈希沖突庵佣。(這方面cache源碼有體現(xiàn))
cache模擬代碼分析
由于lldb調(diào)試并不方便且其底層會(huì)調(diào)用一些方法也會(huì)影響我們的判斷，那么用代碼實(shí)現(xiàn)lldb的操作流程能更好的理解cache的結(jié)構(gòu)和流程汛兜。
代碼模擬
struct xj_cache_t {
unsigned long _bucketsAndMaybeMask; //簡(jiǎn)化了代碼巴粪，除去聯(lián)合體互斥的代碼以及非arm64架構(gòu)下的判斷代碼
uint32_t _maybeMask;
uint16_t _flags;
uint16_t _occupied;
};
struct xj_class_data_bits_t {
uintptr_t bits;
};
struct xj_objc_class {
Class ISA;
Class superclass;
struct xj_cache_t cache;
struct xj_class_data_bits_t bits;
};
以上是還原了objc_class的結(jié)構(gòu)，在cache_t結(jié)構(gòu)中，我們除去聯(lián)合體互斥的代碼和部項(xiàng)目判斷不會(huì)進(jìn)去的代碼肛根！簡(jiǎn)化得出非arm64架構(gòu)下的bucket_t結(jié)構(gòu)如下：
//非arm64
struct xj_bucket_t {
SEL _sel;
IMP _imp;
};
那么根據(jù)以上的代碼辫塌，我們基本還原了cache的代碼。但是_bucketsAndMaybeMask還存在著問(wèn)題派哲，里面實(shí)現(xiàn)了load方法臼氨，源碼如下：
struct bucket_t *cache_t::buckets() const
{
uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
return (bucket_t *)(addr & bucketsMask);
}
_bucketsAndMaybeMask好明顯返回的是bucket_t *類(lèi)型的，是一個(gè)結(jié)構(gòu)體指針狮辽，那么我們就可以替換上面xj_cache_t結(jié)構(gòu)體的第一個(gè)元素得到：
struct xj_cache_t {
struct xj_bucket_t *_buckets;
uint32_t _maybeMask;
uint16_t _flags;
uint16_t _occupied;
};
開(kāi)始驗(yàn)證
首先往LGPerson類(lèi)中添加如下的方法：
- (void)say1;
- (void)say2;
- (void)say3;
- (void)say4;
- (void)say5;
- (void)say6;
- (void)say7;
//定義類(lèi)方法
+ (void)sayHappy;
然后添加實(shí)現(xiàn)代碼：
int main(int argc, const char * argv[]) {
@autoreleasepool {
LGPerson *p = [LGPerson alloc];
Class pClass = p.class; // objc_clas
//類(lèi)中的方法可以嘗試性的調(diào)用一也，例如我實(shí)現(xiàn)兩個(gè)，五個(gè)方法的時(shí)候看看下面的打印情況
[p say1];
[p say2];
[p say3];
[p say4];
[p say5];
[p say6];
[p say7];
[LGPerson sayHappy];
//打印LGPerson類(lèi)中的cache內(nèi)容
struct xj_objc_class *xj_class = (__bridge struct xj_objc_class *)(pClass);
NSLog(@"occupied:%hu maybeMask:%u",xj_class->cache._occupied,xj_class->cache._maybeMask);
//循環(huán)打印buckets鏈表中的成員喉脖，并查看成員內(nèi)容
for (mask_t i = 0; i<xj_class->cache._maybeMask; i++) {
struct xj_bucket_t bucket = xj_class->cache._bukets[i];
NSLog(@"SEL:%@ - IMP:%pf",NSStringFromSelector(bucket._sel),bucket._imp);
}
}
return 0 ;
}
各種情況的打印結(jié)果：
1.當(dāng)調(diào)用say1方法時(shí)椰苟，打印如下：
image.png
當(dāng)一個(gè)方法時(shí)候，
occupied = 1 和 maybeMask = 3树叽，結(jié)果符合預(yù)期舆蝴。2.當(dāng)調(diào)用
say1和say2方法時(shí)，打印如下：
image.png
當(dāng)調(diào)用兩個(gè)方法時(shí)候题诵，
occupied = 2 和 maybeMask = 3洁仗，結(jié)果符合預(yù)期。3.當(dāng)調(diào)用
say1性锭、say2赠潦、say3和sayHappy（類(lèi)方法）時(shí)，打印如下：
image.png
此時(shí)
_occupied = 1草冈，maybeMask = 7她奥。當(dāng)我們添加
init方法時(shí)候，打印如下：
image.png
此時(shí)
_occupied = 2怎棱，maybeMask = 7(保持不變)哩俭。得出結(jié)論：
-
_occupied是容器中可用成員的個(gè)數(shù)。 -
_maybeMask表示容器容量的大腥怠（其實(shí)是容器容量大小-1凡资，最后一個(gè)元素存儲(chǔ)的sel -imp為0x1-bucket指針地址）。 -
類(lèi)方法不存在本類(lèi)的cache中谬运，而是存到元類(lèi)的cache中隙赁。 - 父類(lèi)的方法（如：
init）也會(huì)存到本類(lèi)的cache中。 - 當(dāng)
_maybeMask值變化的時(shí)候梆暖，_occupied會(huì)重新計(jì)數(shù)鸳谜。這也意味著擴(kuò)容的時(shí)候之前的緩存被清空了。
cache_t底層探索
疑點(diǎn)
- 根據(jù)上面的分析我們清楚了
_occupied與_maybeMask之間的變化關(guān)系式廷，但是init方法插入到cache的流程我們還是不清楚的咐扭，這就要分析cache_t的源碼實(shí)現(xiàn)了。 -
_bucketsAndMaybeMask是存儲(chǔ)著_buckets的首地址（類(lèi)似于isa），還有maybeMask的相關(guān)信息蝗肪，那么這個(gè)需要我們分析源碼看看過(guò)程袜爪。
那么bucket添加到buckets容器的過(guò)程邏輯是需要我們進(jìn)行分析的棋凳，也就是cache_t中的insert方法皂冰。
insert
核心源碼如下：
// Never cache before +initialize is done
if (slowpath(!cls()->isInitialized())) {
return;
}
......
//此處省略了一部分代碼
ASSERT(sel != 0 && cls()->isInitialized());
// Use the cache as-is if until we exceed our expected fill ratio.
//對(duì)old occupied+1渊胸，第一次的話(huà)新的occupied = 1朱巨；
mask_t newOccupied = occupied() + 1;
//舊容量，（mask+1）或者 0
unsigned oldCapacity = capacity(), capacity = oldCapacity;
//判斷是否為空cache丐重，首次進(jìn)入這里
if (slowpath(isConstantEmptyCache())) {
// Cache is read-only. Replace it.
//默認(rèn)容量為4
if (!capacity) capacity = INIT_CACHE_SIZE; // 4
//0 4惯殊，開(kāi)辟新的緩存空間携御，false代表是否釋放舊的容器空間诱咏，這里第一次開(kāi)辟空間苔可，傳false（不需要釋放）
reallocate(oldCapacity, capacity, /* freeOld */false);
}
//newOccupied + 1 (相當(dāng)于 _occupied + 2) <= capacity * 3 / 4 容量夠的時(shí)候什么都不做，直接插入袋狞。<=75%的容積正常插入焚辅，否則擴(kuò)容。
//在arm64位的情況下苟鸯，CACHE_END_MARKER 0 擴(kuò)容條件為：7 / 8 87.5% 這個(gè)時(shí)候CACHE_ALLOW_FULL_UTILIZATION 為 1
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.
}
#if CACHE_ALLOW_FULL_UTILIZATION //在arm64位的情況下進(jìn)入
//capacity <= 1<<3 (8), _occupied + 1（CACHE_END_MARKER為0） <= 容量同蜻。少于8個(gè)元素的時(shí)候允許100%占滿(mǎn)。
else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) {
// Allow 100% cache utilization for small buckets. Use it as-is.
}
#endif
//進(jìn)行擴(kuò)容操作
else {
//容量不為空時(shí)早处，返回2倍的容量 否則返回4
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
//MAX_CACHE_SIZE = 1 << 16 = 2^16 = (最大緩存)65532 = 64k
if (capacity > MAX_CACHE_SIZE) {
//容量超出最大值就取最大值
capacity = MAX_CACHE_SIZE;
}
//開(kāi)辟新的容器湾蔓，釋放就的容器空間
reallocate(oldCapacity, capacity, true);
}
//從cahche_t中的_bucketsAndMaybeMask獲取buckets,首地址
bucket_t *b = buckets();
//首次是4-1 這里也就解釋了前面代碼調(diào)試的時(shí)候maybeMask為什么為3,7
mask_t m = capacity - 1;
//用sel和mybeMask進(jìn)行哈希運(yùn)行得到插入的index
mask_t begin = cache_hash(sel, m);
mask_t i = begin;
// Scan for the first unused slot and insert there.
// There is guaranteed to be an empty slot.
//循環(huán)插入數(shù)據(jù)
do {
//能走到這里大概率是cache不存在，所以這里走fastpath
if (fastpath(b[i].sel() == 0)) {
//occupied+1
incrementOccupied();
// buckets鏈表中插入bucket
b[i].set<Atomic, Encoded>(b, sel, imp, cls());
return;
}
//如果bucket中的sel已經(jīng)存在了砌梆，就不進(jìn)行操作默责。也有可能是其他線(xiàn)程插入的
if (b[i].sel() == sel) {
// The entry was added to the cache by some other thread
// before we grabbed the cacheUpdateLock.
return;
}//cahche_next是為了防止hash沖突，然而再hash了一次 ----（i+1）& mask
} while (fastpath((i = cache_next(i, m)) != begin));
//異常處理
bad_cache(receiver, (SEL)sel);
#endif // !DEBUG_TASK_THREADS
步驟：
- 首次進(jìn)入
isConstantEmptyCache分支么库。會(huì)創(chuàng)建一個(gè)容量為4的空buckets。這個(gè)時(shí)候由于舊buckets不存在不需要釋放所以參數(shù)傳遞false甘有。 - 當(dāng)容量大于等于
3/4或7/8的情況下擴(kuò)容诉儒。arm64的條件下為7 / 8。 -
arm64條件下容量<=8的時(shí)候會(huì)占用100%才擴(kuò)容亏掀。 - 擴(kuò)容是直接
翻倍忱反，默認(rèn)值4。最大值MAX_CACHE_SIZE為2^16(65536)滤愕。在擴(kuò)容的時(shí)候直接釋放了舊值温算。 -
mask值為capacity - 1，這也就是調(diào)試的時(shí)候輸出3间影、7的原因（因?yàn)樽詈笠粋€(gè)元素存儲(chǔ)的是buckets的地址注竿，格式為(sel-imp)0x1-buckets address）。 - 通過(guò)
cache_hash計(jì)算插入的index，后面會(huì)通過(guò)cache_next再進(jìn)行計(jì)算hash解決沖突問(wèn)題巩割。 - 循環(huán)判斷通過(guò)
b[i].set插入bucket數(shù)據(jù)裙顽。 - 插入過(guò)程中有異常的就會(huì)調(diào)用
bad_cache(receiver, (SEL)sel)。
reallocate（開(kāi)辟新的緩存空間）
核心代碼如下：
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
//獲取就得buckets
bucket_t *oldBuckets = buckets();
//初始化新的buckets
bucket_t *newBuckets = allocateBuckets(newCapacity);
//設(shè)置新的buckets和mask = newBuckets的容量 - 1
//newBuckets 最后的元素已經(jīng)在初始化時(shí)候有了sel ：0x10 和 imp：buckets首地址
setBucketsAndMask(newBuckets, newCapacity - 1);
if (freeOld) {
//如果之前又buckets宣谈，釋放舊的buckets
collect_free(oldBuckets, oldCapacity);
}
}
-
reallocate方法是重新開(kāi)辟buckets空間愈犹。 - 在開(kāi)辟新的
buckets過(guò)程中，會(huì)釋放舊的buckets闻丑。因?yàn)閮?nèi)存平移很消耗性能漩怎。
allocateBuckets（buckets初始化）
核心代碼如下：
bucket_t *cache_t::allocateBuckets(mask_t newCapacity)
{
// Allocate one extra bucket to mark the end of the list.
//開(kāi)辟空間
bucket_t *newBuckets = (bucket_t *)calloc(bytesForCapacity(newCapacity), 1);
//拿出最后的bucket，進(jìn)行往下的操作
bucket_t *end = endMarker(newBuckets, newCapacity);
#if __arm__
// End marker's sel is 1 and imp points BEFORE the first bucket.
// This saves an instruction in objc_msgSend.
end->set<NotAtomic, Raw>(newBuckets, (SEL)(uintptr_t)1, (IMP)(newBuckets - 1), nil);
#else
// End marker's sel is 1 and imp points to the first bucket.
//新buckets的最后一個(gè)元素存儲(chǔ)的是自身的指針地址嗦嗡。格式為sel-imp（0x1-buckets address）
end->set<NotAtomic, Raw>(newBuckets, (SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
if (PrintCaches) recordNewCache(newCapacity);
return newBuckets;
}
-
calloc方法是開(kāi)辟buckets的空間勋锤。 - 在
buckets的最后的一個(gè)成員里面存放著SEL：0x1和IMP：bucket address。
setBucketsAndMask
核心代碼如下：
//方法中用到相關(guān)的宏定義以及架構(gòu)的判定
#define CACHE_MASK_STORAGE_OUTLINED 1
#define CACHE_MASK_STORAGE_HIGH_16 2
#define CACHE_MASK_STORAGE_LOW_4 3
#define CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS 4
#if defined(__arm64__) && __LP64__
#if TARGET_OS_OSX || TARGET_OS_SIMULATOR
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
#else
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16
#endif
#elif defined(__arm64__) && !__LP64__
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_LOW_4
#else
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_OUTLINED
#endif
//具體方法的實(shí)現(xiàn)
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
#ifdef __arm__
// ensure other threads see buckets contents before buckets pointer
mega_barrier();
_bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_relaxed);
// ensure other threads see new buckets before new mask
//內(nèi)存屏障
mega_barrier();
_maybeMask.store(newMask, memory_order_relaxed);
_occupied = 0;
#elif __x86_64__ || i386
//_bucketsAndMaybeMask 存儲(chǔ)buckets酸钦，這里進(jìn)行了強(qiáng)轉(zhuǎn)怪得。_bucketsAndMaybeMask只存儲(chǔ)buckets的指針。
_bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_release);
// ensure other threads see new buckets before new mask
//_maybeMask存儲(chǔ)newCapacity-1
_maybeMask.store(newMask, memory_order_release);
//元素值賦值為0卑硫，由于是新桶徒恋。
_occupied = 0;
#else
#error Don't know how to do setBucketsAndMask on this architecture.
#endif
}
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 || CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
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);
_bucketsAndMaybeMask.store(((uintptr_t)newMask << maskShift) | (uintptr_t)newBuckets, memory_order_relaxed);
_occupied = 0;
}
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
uintptr_t buckets = (uintptr_t)newBuckets;
unsigned mask = (unsigned)newMask;
ASSERT(buckets == (buckets & bucketsMask));
ASSERT(mask <= 0xffff);
_bucketsAndMaybeMask.store(buckets | objc::mask16ShiftBits(mask), memory_order_relaxed);
_occupied = 0;
ASSERT(this->buckets() == newBuckets);
ASSERT(this->mask() == newMask);
}
#else
#error Unknown cache mask storage type.
#endif
CACHE_MASK_STORAGE對(duì)應(yīng)的值：
-
arm64 64位運(yùn)行設(shè)備OSX/SIMULATOR：CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS（4）真機(jī)（手機(jī)，pad等）：CACHE_MASK_STORAGE_HIGH_16(2)
-
arm64 32位設(shè)備：CACHE_MASK_STORAGE_LOW_4(3) x86_64/i386/arm：CACHE_MASK_STORAGE_OUTLINED(1)
CACHE_MASK_STORAGE_OUTLINED流程：
- 強(qiáng)轉(zhuǎn)
newBuckets為地址存儲(chǔ)在_bucketsAndMaybeMask中欢伏，這也是為什么前面代碼驗(yàn)證的時(shí)候能直接用buckets接收這個(gè)數(shù)據(jù)的原因（只存buckets地址）入挣。
-_maybeMask存儲(chǔ)的值為capacity-1（容量-1，最后一個(gè)存儲(chǔ)的是自身的地址）硝拧。
CACHE_MASK_STORAGE_HIGH_16 或 CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS (真機(jī)上)流程：
-
mask與buckets都存儲(chǔ)在_bucketsAndMaybeMask中径筏，mask << maskShift | newBuckets。 - 此時(shí)
maskShift為48/44也就是mask存儲(chǔ)在高16/20位障陶，buckets存儲(chǔ)在低48/44位滋恬。（mac以及模擬器maskShift是48，其它為44）抱究。
CACHE_MASK_STORAGE_LOW_4 arm64指令32位設(shè)備流程：
-
mask與buckets都存儲(chǔ)在_bucketsAndMaybeMask中恢氯，buckets | objc::mask16ShiftBits(mask)。 -
buckets存儲(chǔ)在高60位鼓寺，mask存儲(chǔ)在低4位勋拟，mask16ShiftBits的具體邏輯會(huì)在后面分析（其實(shí)存儲(chǔ)的不是mask，而是mask前置的0）妈候。
注意：在擴(kuò)容的時(shí)候_occupied = 0敢靡。其實(shí)這也相當(dāng)于開(kāi)辟新的空間，舊空間的_occupied不會(huì)累加在新的空間中苦银，且_occupied不包括最后一個(gè)元素bucket啸胧。
cache_fill_ratio
核心代碼如下：
#if __arm__ || __x86_64__ || __i386__
#define CACHE_END_MARKER 1
static inline mask_t cache_fill_ratio(mask_t capacity) {
return capacity * 3 / 4;
}
#elif __arm64__ && !__LP64__
#define CACHE_END_MARKER 0
static inline mask_t cache_fill_ratio(mask_t capacity) {
return capacity * 3 / 4;
}
#elif __arm64__ && __LP64__
#define CACHE_END_MARKER 0
static inline mask_t cache_fill_ratio(mask_t capacity) {
return capacity * 7 / 8;
}
#define CACHE_ALLOW_FULL_UTILIZATION 1
#else
#error unknown architecture
#endif
- 不同架構(gòu)下容量算法有差異,
__arm64__ && __LP64__（arm64架構(gòu)）下赶站，buckets會(huì)在使用到7/8（87.5%）時(shí)候進(jìn)行擴(kuò)容，其他架構(gòu)都是3/4（75%）就進(jìn)行擴(kuò)容吓揪。 - 因?yàn)樯婕暗?code>負(fù)載因子亲怠，為了有效得避免
hash沖突，而且在3/4和7/8空間利用率最高柠辞，所以在此進(jìn)行擴(kuò)容比較好团秽。
cache_hash和cache_next
核心代碼如下：
#if defined(__arm64__) && TARGET_OS_IOS && !TARGET_OS_SIMULATOR && !TARGET_OS_MACCATALYST
#define CONFIG_USE_PREOPT_CACHES 1
#else
#define CONFIG_USE_PREOPT_CACHES 0
#endif
static inline mask_t cache_hash(SEL sel, mask_t mask)
{
uintptr_t value = (uintptr_t)sel;
#if CONFIG_USE_PREOPT_CACHES
//arm64架構(gòu)下
value ^= value >> 7;
#endif
return (mask_t)(value & mask); //返回sel&mask作為index
}
#if CACHE_END_MARKER
static inline mask_t cache_next(mask_t i, mask_t mask) {
return (i+1) & mask; //index +1 & mask
}
#elif __arm64__
static inline mask_t cache_next(mask_t i, mask_t mask) {
return i ? i-1 : mask; //在平移尋找插入位置的時(shí)候，如果index不等于0叭首，那么index-1向前著习勤，否則index = mask，移到最后
}
#else
#error unexpected configuration
#endif
-
CONFIG_USE_PREOPT_CACHES表示arm64指令并且非iOS模擬器非MACCATALYST焙格，也就是arm64指令真機(jī)图毕。 -
cache_next在intel mac以及arm 32的情況是向后(+)插入，在arm64的情況下是向前(-)插入眷唉。-
(i+1) & mask的邏輯是向后(+)插入予颤，會(huì)進(jìn)行二次&mask。 -
i ? i-1 : mask沖突的時(shí)候向前(-)冬阳，直接沒(méi)有二次hash蛤虐。當(dāng)i為0時(shí)會(huì)返回mask相當(dāng)于到倒數(shù)第二個(gè)元素的地址(倒數(shù)第一個(gè)位0x1-buckets address)。
-
_bucketsAndMaybeMask分析
由上面的代碼分析到_bucketsAndMaybeMask保存著buckets和maybeMask肝陪，那么他們是怎么計(jì)算得來(lái)的呢驳庭？那么我么就要分析buckets()方法與mask()方法了。請(qǐng)繼續(xù)往下看氯窍！
buckets()
核心代碼如下：
struct bucket_t *cache_t::buckets() const
{
//_bucketsAndMaybeMask調(diào)用了load方法
uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
//上面拿到的地址&bucketsMask（類(lèi)似掩碼）饲常，轉(zhuǎn)化成bucket_t *類(lèi)型的結(jié)構(gòu)體指針并返回給外面
return (bucket_t *)(addr & bucketsMask);
}
bucketsMask是多少？不同架構(gòu)估計(jì)不一樣吧狼讨？（類(lèi)似于isa的掩碼）
bucketsMask的核心代碼：
/intel芯片
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
static constexpr uintptr_t bucketsMask = ~0ul;//全1
//arm64 64位OSX`/`SIMULATOR`
#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;//1<<15（低15位是0）
static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << maskShift) - 1; //(1<<48) - 1(低48位都是1)
//`arm64真機(jī)`
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
static constexpr uintptr_t maskShift = 48;
static constexpr uintptr_t maskZeroBits = 4;
// The largest mask value we can store.
static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;//1<<15(低15位0)
// The mask applied to `_maskAndBuckets` to retrieve the buckets pointer.
static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1; //(1 << 44)-1（低44位1）
//arm64 32 位
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
static constexpr uintptr_t maskBits = 4;
static constexpr uintptr_t maskMask = (1 << maskBits) - 1;// (1<<4) -1（低4位1）
static constexpr uintptr_t bucketsMask = ~maskMask; // ~((1<<4) -1)（低4位為0贝淤，其余全為1）
#endif
#end
-
intel/arm：直接存儲(chǔ)的就是buckets地址，64/32位存儲(chǔ)buckets政供。 -
arm64指令64位OSX/SIMULATOR：(1<<48) - 1播聪，低48位存儲(chǔ)buckets。 -
arm64指令64位真機(jī)（除了mac以及模擬器）：(1 << 44)-1鲫骗，低44位存儲(chǔ)buckets犬耻。 -
arm64指令32位：~((1<<4) -1)：高60位存儲(chǔ)buckets踩晶。
mask()
核心代碼如下：(簡(jiǎn)化了一些不必要的代碼)
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED //intel芯片
//調(diào)用了setBucketsAndMask方法
mask_t cache_t::mask() const
{
return _maybeMask.load(memory_order_relaxed);
}
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 || CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS //arm64架的64位設(shè)備
//調(diào)用了setBucketsAndMask方法
mask_t cache_t::mask() const
{
uintptr_t maskAndBuckets = _bucketsAndMaybeMask.load(memory_order_relaxed);
//maskShift 為48,
return maskAndBuckets >> maskShift;
}
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4 //arm64架的32位設(shè)備
//調(diào)用了setBucketsAndMask方法
mask_t cache_t::mask() const
{
uintptr_t maskAndBuckets = _bucketsAndMaybeMask.load(memory_order_relaxed);
//maskMask = (1<<4) -1（低4位1）
uintptr_t maskShift = (maskAndBuckets & maskMask);//保留后4位执泰。
//0xffff >> maskShift 獲取mask值。
return 0xffff >> maskShift;
}
-
intel/arm：需要直接從_maybeMask字段讀取渡蜻。 -
arm64 64位OSX/SIMULATOR：maskAndBuckets >> maskShift术吝，取高16位计济。 -
arm64 64位真機(jī)：maskAndBuckets >> maskShift，取高16位排苍。 -
arm64 32位：0xffff >> maskShift沦寂，取低4位存儲(chǔ)的mask的值。
驗(yàn)證CACHE_MASK_STORAGE_LOW_4下mask的獲取
結(jié)合存儲(chǔ)的時(shí)候邏輯來(lái)看淘衙，在存儲(chǔ)的時(shí)候調(diào)用了objc::mask16ShiftBits(mask)：
tatic inline uintptr_t mask16ShiftBits(uint16_t mask)
{
// returns by how much 0xffff must be shifted "right" to return mask
uintptr_t maskShift = __builtin_clz(mask) - 16; //拿出16位前置0的
ASSERT((0xffff >> maskShift) == mask);
return maskShift;
}
__builtin_clz()方法返回的是32位中最高位1之前0的個(gè)數(shù)(前置0的個(gè)數(shù))传藏，一下進(jìn)行驗(yàn)證：
__builtin_clz驗(yàn)證
- __builtin_clz(mask) - 16減16也就意味著要計(jì)算在16位下有多少前置位為0，這里不會(huì)為負(fù)數(shù)彤守。因?yàn)樵谏厦娣治鲋幸呀?jīng)說(shuō)了buckets擴(kuò)容的時(shí)候最大值為2^16毯侦。
- objc::mask16ShiftBits(mask)存儲(chǔ)的就是16位下mask的前置的0的個(gè)數(shù)。
那么可以推導(dǎo)出：0xffff >> maskShift也就是0xffff >> 前置的0的值 這樣就恢復(fù)了mask（3/7/15）具垫。非常牛逼的算法哦３蘩搿！ｓ莶稀Ｘ阅搿！
參考：_builtin
總結(jié)mask與buckets的分布
mask與buckets的分布
補(bǔ)充：為什么imp()需要參數(shù)cls
首先我們要繼續(xù)查看源碼起宽，看看imp賦值的方法里面cls的作用是什么洲胖。
核心源碼如下：
inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls) const {
uintptr_t imp = _imp.load(memory_order_relaxed);
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);
};
//查看set方法的源碼
template<Atomicity atomicity, IMPEncoding impEncoding>
void bucket_t::set(bucket_t *base, SEL newSel, IMP newImp, Class cls)
{
ASSERT(_sel.load(memory_order_relaxed) == 0 ||
_sel.load(memory_order_relaxed) == newSel);
static_assert(offsetof(bucket_t,_imp) == 0 &&
offsetof(bucket_t,_sel) == sizeof(void *),
"bucket_t layout doesn't match arm64 bucket_t::set()");
uintptr_t encodedImp = (impEncoding == Encoded
? encodeImp(base, newImp, newSel, cls)
: (uintptr_t)newImp);
// LDP/STP guarantees that all observers get
// either imp/sel or newImp/newSel
stp(encodedImp, (uintptr_t)newSel, this);
}
#else
template<Atomicity atomicity, IMPEncoding impEncoding>
void bucket_t::set(bucket_t *base, SEL newSel, IMP newImp, Class cls)
{
ASSERT(_sel.load(memory_order_relaxed) == 0 ||
_sel.load(memory_order_relaxed) == newSel);
uintptr_t newIMP = (impEncoding == Encoded
? encodeImp(base, newImp, newSel, cls)
: (uintptr_t)newImp);
if (atomicity == Atomic) {
_imp.store(newIMP, memory_order_relaxed);
if (_sel.load(memory_order_relaxed) != newSel) {
#ifdef __arm__
mega_barrier();
_sel.store(newSel, memory_order_relaxed);
#elif __x86_64__ || __i386__
_sel.store(newSel, memory_order_release);
#else
#error Don't know how to do bucket_t::set on this architecture.
#endif
}
} else {
_imp.store(newIMP, memory_order_relaxed);
_sel.store(newSel, memory_order_relaxed);
}
}
//查看encodedImp方法源碼如下
uintptr_t encodeImp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, IMP newImp, UNUSED_WITHOUT_PTRAUTH 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(base, 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
得出結(jié)論：bucket_t::set的時(shí)候會(huì)判斷是否需要mpEncoding，如果需要會(huì)進(jìn)行(uintptr_t)newImp ^ (uintptr_t)cls燎含，所以在讀取imp的時(shí)候需要傳參數(shù)cls進(jìn)行還原宾濒。相當(dāng)于(uintptr_t)cls^imp^(uintptr_t)cls = imp。那么就說(shuō)明buckets中存儲(chǔ)的imp不一定是真實(shí)的imp屏箍，有可能是經(jīng)過(guò)編碼的绘梦。
cache原理詳圖
cache原理詳圖
