在 指针偏移&读取bits信息& class_rw_t文章中我们已经分析了bits今天我们分析cache 看看 cache是如何工作的
首先准备在源码环境下创建如下代码并断言
@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 调试获取cache
断点在lookBeauty位置
截屏2020-09-18 下午4.56.12.png
lldb调试cache 2.jpg
断点过 lookBeauty 断点到 sayNB
lldb调试cache 2备份.jpg
断点过 sayNB 断点到 listenStory
lldb调试cache 2备份 2.jpg
断过listenStory 断到 NSLog
lldb调试cache 2备份 3.jpg
带着上面的疑问 我们开始分析源码 mask 是啥 occupied是啥 为啥变化 ,为啥数据会丢失， 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(); 函数 中文是 增加 occupied 点进去
void cache_t::incrementOccupied()
{
_occupied++;
}
_occupied ++ 缓存一个方法就++ ？继续探寻全局搜索 incrementOccupied() 此方法 看从哪里调用的
ALWAYS_INLINE
void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{
.....省略 后面着重分析
}
我的天在整个源码里面 只有这一个地方进行了 调用 看方法名字为insert 在继续搜索 insert 看在哪里调用的
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
}
继续搜索cache_fill，发现在写入之前，还有一步操作，即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())) { ///判断是否需要初始化创建缓存 小概率：occupied（） = 0 时
// Cache is read-only. Replace it.
if (!capacity) capacity = INIT_CACHE_SIZE; /// 初始化 capacity = (1<<2) 二进制 100 十进制 4
reallocate(oldCapacity, capacity, /* freeOld */false); /// 开辟 空间 不需要释放回收老的内存
}
else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) {
// Cache is less than 3/4 full. Use it as-is. //缓存不足3/4满。按原样使用它。
// 假如上之前有两个缓存
// mask_t newOccupied = occupied() + 1; ///2 +1
//第一次开辟 申请内存是4个 已经有2个插入 bucket 插入到缓存里
/// newOccupied + 1 < = capacity/4*3 == （3+1 <= capacity/4*3）所以不满足 要进行内容扩张 看下面的方法
}
else {
/// 有 cap 是否 存才 ： 存在 进行 2倍扩容 :不存在 4
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
/// 最大 不能 超过 1<<16
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;
}
///重新开辟内存空间 并回收老的数据
reallocate(oldCapacity, capacity, true);
}
bucket_t *b = buckets();/// 获取 bukets
mask_t m = capacity - 1; //mask 实际内存个数 -1 类似 最大 下标
/// 获取 根据 m 7 和当前 sel 获取 hash表 mask
mask_t begin = cache_hash(sel, m); //查找 hash表 key为 sel m = 最大下标 计算当前需要插入的缓存下标
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.
//扫描第一个未使用的插槽并插入。
//保证有一个空槽，因为
//最小尺寸是4，我们将大小调整为3/4满。
do {
///循环遍历 buckets() sel() 一旦发现 没有 就进行 occupied+1 并进行存储 并跳出循环
if (fastpath(b[i].sel() == 0)) {
incrementOccupied();
b[i].set<Atomic, Encoded>(sel, imp, cls);
return;
}
///循环遍历 发现了已经有存了 occupied 不做任何处理 并return
if (b[i].sel() == 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));
cache_t::bad_cache(receiver, (SEL)sel, cls);
}
分析：
- 第一步，根据occupied的值计算出当前的缓存占用量，当没有方法调用时候 _occupied 为0
mask_t cache_t::occupied()
{
return _occupied;
}
- 第二步，根据缓存占用量计算需开辟空间大小
1.是否为初始化 首次 开辟空间 是的话 开辟 4 个大小
if (slowpath(isConstantEmptyCache())) { ///判断是否需要初始化创建缓存 小概率：occupied（） = 0 时
// Cache is read-only. Replace it.
if (!capacity) capacity = INIT_CACHE_SIZE; /// 初始化 capacity = (1<<2) 二进制 100 十进制 4
reallocate(oldCapacity, capacity, /* freeOld */false); /// 开辟 空间 不需要释放回收老的内存
}
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满。按原样使用它。
// 假如上之前有两个缓存
// mask_t newOccupied = occupied() + 1; ///2 +1
//第一次开辟 申请内存是4个 已经有2个插入 bucket 插入到缓存里
/// newOccupied + 1 < = capacity/4*3 == （3+1 <= capacity/4*3）所以不满足 要进行内容扩张 看下面的方法
}
3.如果缓存占用量超过3/4，则需要进行两倍扩容以及重新开辟空间
/// 有 cap 是否 存才 ： 存在 进行 2倍扩容 :不存在 4
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
/// 最大 不能 超过 1<<16
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;
}
///重新开辟内存空间 并回收老的数据
reallocate(oldCapacity, capacity, true);
}
- 第三步，针对需要存储的bucket进行内部imp 和sel赋值
bucket_t *b = buckets();/// 获取 bukets
mask_t m = capacity - 1; //mask 实际内存个数 -1 类似 最大 下标
/// 获取 根据 m 7 和当前 sel 获取 hash表 mask
mask_t begin = cache_hash(sel, m); //查找 hash表 key为 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.
//扫描第一个未使用的插槽并插入。
//保证有一个空槽，因为
//最小尺寸是4，我们将大小调整为3/4满。
do {
///循环遍历 buckets() sel() 一旦发现 没有 就进行 occupied+1 并进行存储 并跳出循环
if (fastpath(b[i].sel() == 0)) {
incrementOccupied();
b[i].set<Atomic, Encoded>(sel, imp, cls);
return;
}
///循环遍历 发现了已经有存了 occupied 不做任何处理 并return
if (b[i].sel() == 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));
cache_t::bad_cache(receiver, (SEL)sel, cls);
}
循环 查找 当前sel在缓存是否存才 ，存在直接跳出循环 不存在存入缓存并且缓存占用量+1 并跳出循环
cache原理分析的流程图
cache_fill方法.jpg
疑问解答
1、_mask是什么？
_mask是指的掩码数据，用于在哈希算法或者哈希冲突算法中计算哈希下标，其中mask = 开辟空间总大小 -1
2、_occupied 是什么？
_occupied 表示 当前存储了几个 sel-imp ，方法调用 也就是消息发送 会导致 occupied 变化
3、为什么 调用第三个方法的时候 _mask 会变为 7 _occupied 变为了1 ？
因为在cache初始化的时候，分配的空间是4个，随着方法的增多，当存储的 sel-imp个数 即newOccupied + CACHE_END_MARKER（等于1）的和 超过 总容量的3/4,例如有4个时，当occupied等于2时，就需要对cache的内存进行两倍扩容
4、为什么 数据丢失了呢 ？
因为sel-imp的存储是通过哈希算法计算下标的，其计算的下标有可能已经存储了sel被占用，所以又需要通过哈希冲突算法重新计算哈希下标，所以导致下标是随机的，并不是固定的
网友评论