前言
在之前的文章中，我们剖析了类的结构，今天我们来分析一下类结构中一个非常重要的结构体cache_t，从名字上我们可以大致可以猜出，cache_t是用来做缓存的，那么它究竟是缓存的什么呢？又是如何缓存的呢？今天我们就来探索一下（本次探究源码基于objc781）.
cache_t是什么？
我们进入cache_t的源码发现
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;
...一些static属性
#if __LP64__
uint16_t _flags;
#endif
uint16_t _occupied;
...一些static属性
bucket_t源码
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__
MethodCacheIMP _imp;
cache_key_t _key;
#else
cache_key_t _key;
MethodCacheIMP _imp;
#endif
其中explicit_atomic是苹果为了保护缓存安全所加的一个原子性的结构体，并没有太大的意义，_buckets的真实类型是struct bucket_t *，
_mask的真实类型是mask_t，而_flags（64位）和_occupied（32位）为一个标识常量。
下面我们逐个介绍一下，这些属性代表的含义。
-
_buckets：数组，是存放bucket_t结构体的数组，而bucket_t是用来存放方法的SEL和IMP内存地址的。 -
_mask：_mask的大小是_buckets长度 - 1，用作面具掩码 -
_occupied：数组实际所占的内存大小
下面我们通过LLDB调试验证一下。
LLDB调试验证
同样的我们定义一个ZGPerson类，代码如下：
@interface ZGPerson : NSObject
@property (nonatomic, copy) NSString *name;
@property (nonatomic, strong) NSString *nickName;
- (void)test1;
- (void)test2;
- (void)test3;
- (void)test4;
- (void)test5;
+ (void)test6;
@end
@implementation ZGPerson
- (void)test1{
NSLog(@"方法名: %s",__func__);
}
- (void)test2{
NSLog(@"方法名: %s",__func__);
}
- (void)test3{
NSLog(@"方法名: %s",__func__);
}
- (void)test4{
NSLog(@"方法名: %s",__func__);
}
- (void)test5{
NSLog(@"方法名: %s",__func__);
}
+ (void)test6{
NSLog(@"方法名: %s",__func__);
}
@end
当我们在main中初始化而未执行方法时
初始化
LLDB打印如下
(lldb) p/x pClass //打印类的首地址
(Class) $0 = 0x00000001000022b8 ZGPerson
(lldb) p (cache_t *)0x00000001000022c8 //内存偏移16字节获取cache_t的值（前面有isa和superclass各占8个字节）
(cache_t *) $1 = 0x00000001000022c8
(lldb) p *$1// 取cache_t *的值
(cache_t) $2 = {
_buckets = {
std::__1::atomic<bucket_t *> = 0x00000001003ea440 {
_sel = {
std::__1::atomic<objc_selector *> = 0x0000000000000000
}
_imp = {
std::__1::atomic<unsigned long> = 0
}
}
}
_mask = {
std::__1::atomic<unsigned int> = 0
}
_flags = 32804
_occupied = 0
}
可见，_mask为0，_occupied内存占用为0
当我们执行了test1后
执行了test1
2020-09-17 22:01:29.612583+0800 KCObjc[50334:1426342] 方法名: -[ZGPerson test1]
(lldb) p *$1
(cache_t) $3 = {
_buckets = {
std::__1::atomic<bucket_t *> = 0x00000001011191d0 {
_sel = {
std::__1::atomic<objc_selector *> = 0x0000000100000e4c
}
_imp = {
std::__1::atomic<unsigned long> = 10584
}
}
}
_mask = {
std::__1::atomic<unsigned int> = 3
}
_flags = 32804
_occupied = 1
}
(lldb) p $3.buckets() //通过系统定义的buckets()方法获取_buckets数组
(bucket_t *) $4 = 0x00000001011191d0
(lldb) p $4[0].sel() //通过系统定义的sel())方法获取bucket_t中_sel的的值
(SEL) $5 = "test1"
可见，方法调用正常，_occupied = 1，_mask = 3，也打印出了test1.
但是当我们调用了好几个方法后
调用多个方法
我们却发现了奇怪的现象
(lldb) p/x pClass
(Class) $0 = 0x00000001000022b8 ZGPerson
(lldb) p (cache_t *)0x00000001000022c8
(cache_t *) $1 = 0x00000001000022c8
(lldb) p *$1
(cache_t) $2 = {
_buckets = {
std::__1::atomic<bucket_t *> = 0x0000000100666950 {
_sel = {
std::__1::atomic<objc_selector *> = 0x0000000100000e58
}
_imp = {
std::__1::atomic<unsigned long> = 12024
}
}
}
_mask = {
std::__1::atomic<unsigned int> = 7
}
_flags = 32804
_occupied = 2
}
(lldb) p $2.buckets()
(bucket_t *) $3 = 0x00000001006a0c20
(lldb) p $3[0].sel()
(SEL) $4 = "test3"
(lldb) p $3[1].sel()
(SEL) $5 = <no value available>
(lldb) p $3[2].sel()
(SEL) $6 = <no value available>
此时，_occupied = 2，_mask = 7，而不是我们想象的_occupied = 4，而且我们打印方法也只打印出了一个test3，这究竟是为什么呢？下面我们通过源码一探究竟！
cache_t怎么存的？
下面我们从源码分析一下cache_t的存储流程，前面我们注意到，一旦开始调用方法，_occupied就会增加，而我们cache_t的结构体中发现了一个使_occupied 增加的方法为void incrementOccupied();
void cache_t::incrementOccupied()
{
_occupied++;
}
我们全局搜索incrementOccupied，发现只在cache_t的insert方法中有调用，我们继续搜索insert(发现在objc_cache.mm文件的cache_fill方法中会调用insert
cache_fill源码
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
}
insert源码（关键代码）
ALWAYS_INLINE
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
//1.初始化缓存空间
mask_t newOccupied = occupied() + 1;//即将要占用的个数 = 已占用个数+ 1
unsigned oldCapacity = capacity(), capacity = oldCapacity;//获取已占用的个数
//2.判断是否需要扩容
if (slowpath(isConstantEmptyCache())) {//如果缓存是空的，去开辟内存空间
// Cache is read-only. Replace it.
//INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2), 1左移两位为4
if (!capacity) capacity = INIT_CACHE_SIZE;
reallocate(oldCapacity, capacity, /* freeOld */false);// 根据当前内容分配空间
}
else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) { // 4 3 + 1 bucket
// 如果 newOccupied +1 <= 容量的4分之3，存储空间还足够，不需额外处理，由此可以看出只要容量等于4分之3时，立马就要进行其他操作
// Cache is less than 3/4 full. Use it as-is.
}
//如果等于或超过4分之3
else {
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE; // 扩容两倍 4
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;// 最大不能 超出 1<< 16即256
}
reallocate(oldCapacity, capacity, true); // 扩容
}
// 3.判断散列表中是否已有该方法的缓存情况插入缓存或者return
bucket_t *b = buckets();// 获取散列表
mask_t m = capacity - 1;// 获取散列表大小 - 1（面具）
// 通过cache_hash函数【begin = sel & m】计算出key值 k 对应的 index值
// begin，用来记录查询起始索引
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 because the
// minimum size is 4 and we resized at 3/4 full.
do {
if (fastpath(b[i].sel() == 0)) {// 如果没有找到缓存的方法
incrementOccupied();// _occupied ++;
b[i].set<Atomic, Encoded>(sel, imp, cls);// 缓存实例方法：内存缓存了imp和sel
return;
}
if (b[i].sel() == sel) {// 如果找到需要缓存的方法，不需要缓存，直接return
// 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));// 当出现hash冲突 cache_next查找下一个 直到回到begin 全部查找结束
cache_t::bad_cache(receiver, (SEL)sel, cls);
}
以上源码我加了一些注释，方便大家阅读，可以看出insert大致分为3步
初始化缓存空间- 判断是否需要扩容，如果需要，以原始空间的
2倍扩容，重新分配空间，释放已有缓存- 判断散列表中是否已有该方法的缓存情况插入缓存或者
return
我们再对申请内存的方法reallocate和其中涉及的hash算法做一下详细的讲解。
reallocate源码
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
bucket_t *oldBuckets = buckets();
bucket_t *newBuckets = allocateBuckets(newCapacity);//申请新的
// 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);//这里为了节省内存将bucket和mask放在一起
if (freeOld) {
cache_collect_free(oldBuckets, oldCapacity);//释放老的
}
}
allocateBuckets源码
bucket_t *allocateBuckets(mask_t newCapacity)
{
// Allocate one extra bucket to mark the end of the list.
// This can't overflow mask_t because newCapacity is a power of 2.
bucket_t *newBuckets = (bucket_t *)
calloc(cache_t::bytesForCapacity(newCapacity), 1);
bucket_t *end = cache_t::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>((SEL)(uintptr_t)1, (IMP)(newBuckets - 1), nil);
#else
// End marker's sel is 1 and imp points to the first bucket.
end->set<NotAtomic, Raw>((SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
if (PrintCaches) recordNewCache(newCapacity);
return newBuckets;
}
reallocate函数中 通过allocateBuckets函数的calloc向系统申请newCapacity大小的空间- 通过
setBucketsAndMask设置buckets和mask，其中 mask 更新为新申请的总空间大小 - 1
hash算法
cache_hash源码
static inline mask_t cache_hash(SEL sel, mask_t mask)
{
return (mask_t)(uintptr_t)sel & mask;
}
解释：
mask值 始终为capacity - 1，即3，7，15，31...，用二进制表示为00000001，00000011，00000111，00001111，所以取任意值& mask必定小于等于mask，这一步sel & mask的操作确保了begin的值不会超过总容量-1，以确保遍历的时候下标不会超出capacity，出现越界的情况。
cache_next源码
static inline mask_t cache_next(mask_t i, mask_t mask) {
return (i+1) & mask;
}
解释：
当上一个hash算法冲突时：（将当前的哈希下标 +1） & mask，重新进行哈希计算，得到一个新的下标，继续遍历
疑问解答
在扩容的时候，我们释放了已有缓存，把原来的方法也释放掉了，又因为sel-imp的存储是通过哈希算法计算下标的，而hash取到的下标是随机的，并不是固定的。
这里也就解释了为什么_occupied = 2，_mask = 7，而不是我们想象的_occupied = 4，而且我们打印方法也只打印出了一个test3的疑问。
网友评论