iOS 探索cache_t
2020-09-19 本文已影响0人
Sheisone
前面我们探索类的时候，了解类的结构。并且有看到objc_class中包含cache属性是用来做方法缓存的，其是一个cache_t结构体，那cache_t内部又是什么样的？是如果做到换方法缓存呢？今天我们就来一探究竟。
一、 cache_t结构
struct objc_class : objc_object {
// Class ISA;
Class superclass;
cache_t cache; // formerly cache pointer and vtable
class_data_bits_t bits; // class_rw_t * plus custom rr/alloc flags
...
}
这是我们前面了解到的objc_class的结构，主要包括以下：
- ISA：
objc_class继承与objc_object，而objc_object中只有isa，所以这里的ISA实际上来自于objc_object，注释并不代表不存在，只是说明不是在这个地方。 -
superclass：superclass的类型依然是Class， 指向了类的父类。 -
cache：来自于cache_t结构体，是方法列表的缓存，存储了最近使用的方法 -
bits：来自于class_data_bits_t，存储了类更详细的信息，我们后面会探索
objc_class是继承自objc_object的，也就是说 类 也是一个对象。这也是万物皆对象的由来。因其继承自objc_object，自然默认就含有了objc_object的成员 isa。
接下来主角登场，我们进入cache_t中看下其结构，因为cache_t源码还是很多，我们提炼一下关键信息：
struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
// explicit_atomic 显示原子性，目的是为了能够 保证 增删改查时 线程的安全性
//等价于 struct bucket_t * _buckets;
//_buckets 中放的是 sel imp
//_buckets的读取 有提供相应名称的方法 buckets()
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;
#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;
#if __LP64__
uint16_t _flags;
#endif
uint16_t _occupied;
查看cache_t的源码，发现分成了3个架构的处理，其中真机的架构中，mask和bucket是写在一起，目的是为了优化，可以通过各自的掩码来获取相应的数据：
这三个架构分别是：
-
CACHE_MASK_STORAGE_OUTLINED:表示运行的环境 模拟器 或者macOS -
CACHE_MASK_STORAGE_HIGH_16:表示运行环境是 64位的真机 -
CACHE_MASK_STORAGE_LOW_4:表示运行环境是 非64位 的真机
虽然是三种架构，但是他们结构中都包含了：
image.png
_buckets中是bucket_t的集合，我们再看下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__
//explicit_atomic，原子性，保证安全
explicit_atomic<uintptr_t> _imp;
explicit_atomic<SEL> _sel;
#else
explicit_atomic<SEL> _sel;
explicit_atomic<uintptr_t> _imp;
#endif
...
}
bucket_t同样分为两种类型：真机和非真机，但是他们都包含了：
-
sel: 方法编号 -
imp: 方法的函数指针
至此，我们总结下从objc_class到bucket_t的结构：
image.png
二、在cache中查找sel-imp
方式一：lldb调试
我们新建mac app项目，创建一个LPPerson类，并新建部分方法：
@interface LPPerson : NSObject
@property (nonatomic, copy) NSString *name;
@property (nonatomic, strong) NSString *nickName;
- (void)say1;
- (void)say2;
- (void)say3;
- (void)say4;
+ (void)say5;
@end
@implementation LPPerson
- (void)say1{
NSLog(@"LPPerson say : %s",__func__);
}
- (void)say2{
NSLog(@"LPPerson say : %s",__func__);
}
- (void)say3{
NSLog(@"LPPerson say : %s",__func__);
}
- (void)say4{
NSLog(@"LPPerson say : %s",__func__);
}
+ (void)say5{
NSLog(@"LPPerson say : %s",__func__);
}
@end
并在main.m中创建person对象并调用方法：
int main(int argc, const char * argv[]) {
@autoreleasepool {
LPPerson *p = [LPPerson alloc];
Class pClass = [LPPerson class];
[p say1];
[p say2];
[p say3];
NSLog(@"%@",pClass);
}
return 0;
}
我们在[p say1];这里打上断点,进行如下调试：
(lldb) p/x pClass
(Class) $0 = 0x0000000100008298 LPPerson
(lldb) p (cache_t *)0x00000001000082a8
(cache_t *) $1 = 0x00000001000082a8
(lldb) p *$1
(cache_t) $2 = {
_buckets = {
std::__1::atomic<bucket_t *> = {
Value = 0x0000000100346460
}
}
_mask = {
std::__1::atomic<unsigned int> = {
Value = 0
}
}
_flags = 32804
_occupied = 0
}
(lldb) p $2.buckets()
(bucket_t *) $3 = 0x0000000100346460
(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>
(lldb) p $4.imp(pClass)
(IMP) $6 = 0x0000000000000000
cache属性的获取，需要通过pclass的首地址平移16字节，即首地址+0x10获取cache的地址
从源码的分析中，我们知道sel-imp是在cache_t的_buckets属性中（目前处于macOS环境），而在cache_t结构体中提供了获取_buckets属性的方法buckets()
获取了_buckets属性，就可以获取sel-imp了，这两个的获取在bucket_t结构体中同样提供了相应的获取方法sel()以及 imp(pClass)
可以看到，此时buckets中并没有数据，因为其内部没有sel和imp的存在
我们在[p say2]加上断点，并放开[p say1]的断点，并再次打印：
2020-09-19 15:20:45.571484+0800 KCObjc[18159:13023877] LPPerson say : -[LPPerson say1]
(lldb) p *$1
(cache_t) $7 = {
_buckets = {
std::__1::atomic<bucket_t *> = {
Value = 0x0000000102070af0
}
}
_mask = {
std::__1::atomic<unsigned int> = {
Value = 3
}
}
_flags = 32804
_occupied = 1
}
可以发现，_occupied从0变成了1，_mask 从0变为了3,
我们获取下$3.buckets()
(lldb) p $7.buckets()
(bucket_t *) $8 = 0x0000000101d04790
(lldb) p *$8
(bucket_t) $9 = {
_sel = {
std::__1::atomic<objc_selector *> = "" {
Value = ""
}
}
_imp = {
std::__1::atomic<unsigned long> = {
Value = 48824
}
}
}
(lldb) p $9.sel()
(SEL) $10 = "say1"
(lldb) p $9.imp()
(IMP) $11 = 0x0000000100003c20 (KCObjc`-[LPPerson say1])
从这一步，我们可以到，buckets中有了一个bucket_t，并且获取这个bucket_t中的sel和imp正是我们执行的say1方法。
方式二：模拟源码
lldb可能不是很直接，并且可能相对麻烦点，那么我们就模拟源码来实现一个cache_t，再观察下：
新建一个工程，同样使用刚才的LPPerson，在mian.m中模拟源码：
typedef uint32_t mask_t; // x86_64 & arm64 asm are less efficient with 16-bits
struct lp_bucket_t {
SEL _sel;
IMP _imp;
};
struct lp_cache_t {
struct lp_bucket_t * _buckets;
mask_t _mask;
uint16_t _flags;
uint16_t _occupied;
};
struct lp_class_data_bits_t {
uintptr_t bits;
};
struct lp_objc_class {
Class ISA;
Class superclass;
struct lp_cache_t cache; // formerly cache pointer and vtable
struct lp_class_data_bits_t bits; // class_rw_t * plus custom rr/alloc flags
};
int main(int argc, const char * argv[]) {
@autoreleasepool {
LPPerson *p = [LPPerson alloc];
Class pClass = [LPPerson class]; // objc_clas
[p say1];
// [p say2];
// [p say3];
// [p say4];
struct lp_objc_class *lp_pClass = (__bridge struct lp_objc_class *)(pClass);
NSLog(@"%hu - %u",lp_pClass->cache._occupied,lp_pClass->cache._mask);
for (mask_t i = 0; i<lp_pClass->cache._mask; i++) {
// 打印获取的 bucket
struct lp_bucket_t bucket = lp_pClass->cache._buckets[i];
NSLog(@"%@ - %p",NSStringFromSelector(bucket._sel),bucket._imp);
}
NSLog(@"Hello, World!");
}
return 0;
}
我们先执行say1 一个方法，看下结果：
LPPerson say : -[LPPerson say1]
1 - 3
say1 - 0xb850
(null) - 0x0
(null) - 0x0
Hello, World!
再放开say2的注释，执行2个方法后，再看下结果：
LPPerson say : -[LPPerson say1]
LPPerson say : -[LPPerson say2]
2 - 3
say1 - 0xb858
say2 - 0xb808
(null) - 0x0
Hello, World!
再放开所有的注释，执行4个方法后，再看下结果：
LPPerson say : -[LPPerson say1]
LPPerson say : -[LPPerson say2]
LPPerson say : -[LPPerson say3]
LPPerson say : -[LPPerson say4]
2 - 7
say4 - 0xb9b8
(null) - 0x0
say3 - 0xb9e8
(null) - 0x0
(null) - 0x0
(null) - 0x0
(null) - 0x0
Hello, World!
通过上面的结果，我们可以发现几个问题：
-
mask和occupied是什么？ -
mask和occupied会有变化，为什么会变化？并且变化的没有规律。 -
buckets中sel和imp并不是全部保存，有些已经执行过的方法，按理说应该要缓存，但是结果却没有。这是为什么？
接下来我们就来分析下
三、cache_t原理分析
查看cache_t源码，会发现这样的代码：
public:
static bucket_t *emptyBuckets();
struct bucket_t *buckets();
mask_t mask();
mask_t occupied();
void incrementOccupied();
incrementOccupied()，函数名字面意思应该是增加occupied，进入函数内部：
void cache_t::incrementOccupied()
{
_occupied++;
}
果然，这里就是处理_occupied的增加的，再全局搜索下，看哪里用到这个方法
image.png
void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{
...
do {
if (fastpath(b[i].sel() == 0)) {
incrementOccupied();
b[i].set<Atomic, Encoded>(sel, imp, cls);
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里面inser方法的地方了，我们接下来就重点分析下：
第一步、根据当前的缓存情况，并根据条件执行各种操作：
// Use the cache as-is if it is less than 3/4 full
///1、获取当前的占用量
mask_t newOccupied = occupied() + 1;
///2、获取当前缓存的最大缓存量
unsigned oldCapacity = capacity(), capacity = oldCapacity;
///3、判断当前cache是否为空
if (slowpath(isConstantEmptyCache())) {
// Cache is read-only. Replace it.
///最大缓存量为空，则赋值为INIT_CACHE_SIZE == 4
if (!capacity) capacity = INIT_CACHE_SIZE;
///开辟空间
reallocate(oldCapacity, capacity, /* freeOld */false);
} ///4、判断当前容量是否没有超过最大容量的3/4
else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) {
// Cache is less than 3/4 full. Use it as-is.
}///5、判断当前容量超过最大容量的3/4，则需要扩容，新的容量为原来容量的2倍
else {
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;
}
reallocate(oldCapacity, capacity, true);
}
具体步骤如下：
- 1、获取当前的占用量
- 2、获取当前缓存的最大缓存量
- 3、判断当前
cache是否为空
1)、最大缓存量为空，则赋值为INIT_CACHE_SIZE == 4
enum {
INIT_CACHE_SIZE_LOG2 = 2,
INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2),
MAX_CACHE_SIZE_LOG2 = 16,
MAX_CACHE_SIZE = (1 << MAX_CACHE_SIZE_LOG2),
};
INIT_CACHE_SIZE = INIT_CACHE_SIZE_LOG2左移1位，INIT_CACHE_SIZE_LOG2= 2，左移1位即为4。
2)、开辟空间
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
///判断是够存在oldBuckets
bucket_t *oldBuckets = buckets();
/// 创建新的临时newBuckets
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);
//插入newBuckets
setBucketsAndMask(newBuckets, newCapacity - 1);
//释放oldBuckets
if (freeOld) {
cache_collect_free(oldBuckets, oldCapacity);
}
}
- 4、判断当前容量是否没有超过最大容量的3/4
- 5、判断当前容量超过最大容量的3/4，则需要扩容，新的容量为原来容量的2倍,并扩大空间
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;
}
reallocate(oldCapacity, capacity, true);
第二步、找到合适的bucket位置，存放sel和imp
/// 1、初始化buckets
bucket_t *b = buckets();
/// 2、倒序查找，所以获取当前最大容量- 1
mask_t m = capacity - 1;
mask_t begin = cache_hash(sel, m);
mask_t i = begin;
///3、利用hash算法，找bucket_t的位置，如果当前bucket_t的sel和要插入的不一样，则存储，反之，继续寻找位置。
// 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();
b[i].set<Atomic, Encoded>(sel, imp, cls);
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));
具体步骤如下：
- 1、初始化
buckets - 2、获取当前缓存的最大缓存量,并利用哈希算法，算出一个开始位置
- 3、利用
hash算法得到要插入的位置，如果当前bucket_t的sel和要插入的不一样，则存储，反之，继续寻找位置
- 、
cache_hash源码：
static inline mask_t cache_hash(SEL sel, mask_t mask)
{
return (mask_t)(uintptr_t)sel & mask; // 通过sel & mask（mask = cap -1）
}
- 、
cache_next源码：
#if __arm__ || __x86_64__ || __i386__
// objc_msgSend has few registers available.
// Cache scan increments and wraps at special end-marking bucket.
#define CACHE_END_MARKER 1
static inline mask_t cache_next(mask_t i, mask_t mask) {
return (i+1) & mask; //（将当前的哈希下标 +1） & mask，重新进行哈希计算，得到一个新的下标
}
#elif __arm64__
// objc_msgSend has lots of registers available.
// Cache scan decrements. No end marker needed.
#define CACHE_END_MARKER 0
static inline mask_t cache_next(mask_t i, mask_t mask) {
return i ? i-1 : mask; //如果i是空，则为mask，mask = cap -1，如果不为空，则 i-1，向前插入sel-imp
}
insert的流程我们可以总结如下流程图:
image.png
基于上面的分析，针对开始的问题，我们可以知道答案如下：
1、_mask和_occupied是什么？
_mask是指掩码数据，用于在哈希算法或者哈希冲突算法中计算哈希下标，其中mask 等于capacity - 1
_occupied表示哈希表中 sel-imp的占用大小 (即可以理解为分配的内存中已经存储了sel-imp的的个数)
2、为什么occupied 和mask会变化？
因为在cache初始化时，分配的空间是4个，随着方法调用的增多，当存储的sel-imp个数，即newOccupied + CACHE_END_MARKER（等于1）的和 超过 总容量的3/4,例如有4个时，当 occupied等于2时，就需要对cache的内存进行两倍扩容
3、bucket数据为什么会有丢失的情况？
原因是在扩容时，是将原有的内存全部清除了，再重新申请了内存导致的。并且因为sel-imp的存储是通过哈希算法计算下标的，其计算的下标有可能已经存储了sel，所以又需要通过哈希冲突算法重新计算哈希下标，所以导致下标是随机的，并不是固定的。
觉得不错记得点赞哦！听说看完点赞的人逢考必过，逢奖必中。ღ( ´･ᴗ･` )比心
