cache_t 缓存流程分析
2020-09-18 本文已影响0人
深圳_你要的昵称
上次面试题答案
上回面试题分析最后留了个题，关于class_getMethodImplementation的返回值判断，题目如下
void lgIMP_classToMetaclass(Class pClass) {
const char *className = class_getName(pClass);
Class metaClass = objc_getMetaClass(className);
IMP imp1 = class_getMethodImplementation(pClass, @selector(sayHello));
IMP imp2 = class_getMethodImplementation(metaClass, @selector(sayHello));
IMP imp3 = class_getMethodImplementation(pClass, @selector(sayByebye));
IMP imp4 = class_getMethodImplementation(metaClass, @selector(sayByebye));
NSLog(@"%s-%p-%p-%p-%p",__func__,imp1,imp2,imp3,imp4);
}
运行结果如下：
KCObjc[815:9353] lgIMP_classToMetaclass-0x100000da0-0x7fff70dba580-0x7fff70dba580-0x100000d70
分析：
-
sayHello是实例方法，存在于类LGPerson中，所以imp1有值。 -
sayByebye是类方法，存在于LGPerson元类中，所以imp4也有值。 - 重点看
imp2 imp3，上述结果中发现值一样，why？
先看class_getMethodImplementation底层方法实现：
IMP class_getMethodImplementation(Class cls, SEL sel)
{
IMP imp;
if (!cls || !sel) return nil;
imp = lookUpImpOrNil(nil, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER);
// Translate forwarding function to C-callable external version
if (!imp) {
return _objc_msgForward;
}
return imp;
}
很简单，lookUpImpOrNil寻找imp指针，有则返回，没有则 return _objc_msgForward【消息转发】，很明显在类中找不到类方法，在元类中也找不到实例方法，所以imp2 imp3中都进行了消息转发，都有值，且一样。
背景
言归正传，之前类的结构分析中，发现类Class对应底层结构体objc_class中包含的成员有：
- 由
objc_object继承的Class ISA - 父类指针
Class superclass - 缓存
cache_t cache - 类中属性及实例方法所存储的结构体
class_data_bits_t bits;
今天重点剖析缓存结构体cache_t。
1.大致结构
先看看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;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
explicit_atomic<uintptr_t> _maskAndBuckets;
mask_t _mask_unused;
#else
#error Unknown cache mask storage type.
#endif
#if __LP64__
uint16_t _flags;
#endif
uint16_t _occupied;
首先很多条件编译判断CACHE_MASK_STORAGE，查看其源码：
#define CACHE_MASK_STORAGE_OUTLINED 1
#define CACHE_MASK_STORAGE_HIGH_16 2
#define CACHE_MASK_STORAGE_LOW_4 3
#if defined(__arm64__) && __LP64__
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16
#elif defined(__arm64__) && !__LP64__
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_LOW_4
#else
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_OUTLINED
#endif
原来是关于cpu架构的区分。HIGH_16是64位真机，LOW_4是非64位的真机，其余则是OUTLINED。又发现很多explicit_atomic，猜测是跟原子性操作相关（这个不是今天的重点）。
1.1CACHE_MASK_STORAGE_OUTLINED情况下
explicit_atomic<struct bucket_t *> _buckets;
explicit_atomic<mask_t> _mask;
-
mask_t之前分析过了，64位时占4个字节大小，32位时占2个字节大小。 -
explicit_atomic<struct bucket_t *> _buckets;根据变量名称_buckets，应该是一个类似数组，里面元素是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<uintptr_t> _imp;
explicit_atomic<SEL> _sel;
#else
explicit_atomic<SEL> _sel;
explicit_atomic<uintptr_t> _imp;
#endif
// 省略了部分方法。。。
}
很熟悉，存储的_sel和_imp。
1.2CACHE_MASK_STORAGE_HIGH_16 与 CACHE_MASK_STORAGE_LOW_4情况下
explicit_atomic<uintptr_t> _maskAndBuckets;
mask_t _mask_unused;
发现将mask_t和buckets整在了一起_maskAndBuckets，根据上面分析，那么方法也是缓存在里面。同时_mask_unused从命名来看，既然未使用，则忽略。
同时有几个mask相关的静态变量定义：
// 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;
以上静态变量专业术语称作掩码，类似于之前分析isa指针中，跟ISA_MASK与运算，这个define ISA_MASK 0x0000000ffffffff8ULL就是一个掩码，取出shiftcls位域的值。
1.3 其它成员
#if __LP64__
uint16_t _flags;
#endif
uint16_t _occupied;
大致猜测，应该是占位和标记用的，可能跟缓存的算法相关。
综上所述，大致结构如下图所示
cache_t.png
2.查看cache_t存储的内容
以上分析得出，缓存的方法都存储在_buckets或_maskAndBuckets里面，那么如何查看里面的内容呢？先将示例运行起来:
@interface LGPerson : NSObject
- (void)sayHello;
- (void)sayByebye;
@end
@implementation LGPerson
- (void)sayHello {
NSLog(@"LGPerson: say hello!");
}
+ (void)sayByebye {
NSLog(@"LGPerson: say bye!");
}
2.1 lldb打印查看
调用处打断点.jpg
1.查看
LGPerson类的首地址
(lldb) p/x [LGPerson class]
(Class) $0 = 0x00000001000022a0 LGPerson
2.查看cache_t地址，需指针偏移16位（因为之前有成员isa + superclass）
0x00000001000022a0 + 0x10 = 0x00000001000022b0
(lldb) p/x (cache_t *)0x00000001000022b0
(cache_t *) $1 = 0x00000001000022b0
(lldb) p *$1
(cache_t) $2 = {
_buckets = {
std::__1::atomic<bucket_t *> = 0x000000010101c160 {
_sel = {
std::__1::atomic<objc_selector *> = (null)
}
_imp = {
std::__1::atomic<unsigned long> = 0
}
}
}
_mask = {
std::__1::atomic<unsigned int> = 3
}
_flags = 32804
_occupied = 1
}
3.查看方法
(lldb) p $2.buckets()
(bucket_t *) $3 = 0x000000010101c160
(lldb) p *$3
(bucket_t) $4 = {
_sel = {
std::__1::atomic<objc_selector *> = (null)
}
_imp = {
std::__1::atomic<unsigned long> = 0
}
}
(lldb) p $4.sel()
(SEL) $5 = <no value available>
没找到方法，why？
4.仔细找，一个个打印方法
(lldb) p $2.buckets()[0]
(bucket_t) $6 = {
_sel = {
std::__1::atomic<objc_selector *> = (null)
}
_imp = {
std::__1::atomic<unsigned long> = 0
}
}
(lldb) p $2.buckets()[1]
(bucket_t) $7 = {
_sel = {
std::__1::atomic<objc_selector *> = (null)
}
_imp = {
std::__1::atomic<unsigned long> = 0
}
}
(lldb) p $2.buckets()[2]
(bucket_t) $8 = {
_sel = {
std::__1::atomic<objc_selector *> = ""
}
_imp = {
std::__1::atomic<unsigned long> = 10592
}
}
(lldb) p $2.buckets()[2].sel()
(SEL) $9 = "sayHello"
找到了，居然在第3个，why？看来得看看缓存的插入的流程才行。
3.缓存策略
在讨论cache缓存流程之前，先看看方法缓存的存储顺序，先多调用几个方法
int main(int argc, const char * argv[]) {
@autoreleasepool {
// insert code here...
LGPerson *person = [LGPerson alloc];
[person sayHello];
[person sayByebye];
[person sayNB];
[person sayMaster];
}
return 0;
}
3.1方法乱序现象
打断点，查看buckets()中这几个方法缓存的顺序
(lldb) p *$1
(cache_t) $2 = {
_buckets = {
std::__1::atomic<bucket_t *> = 0x0000000101858910 {
_sel = {
std::__1::atomic<objc_selector *> = ""
}
_imp = {
std::__1::atomic<unsigned long> = 12000
}
}
}
_mask = {
std::__1::atomic<unsigned int> = 7
}
_flags = 32804
_occupied = 2
}
(lldb) p $2.buckets()[0].sel()
(SEL) $3 = "sayMaster"
(lldb) p $2.buckets()[1].sel()
(SEL) $4 = "sayNB"
(lldb) p $2.buckets()[2].sel()
(SEL) $5 = <no value available>
(lldb) p $2.buckets()[3].sel()
(SEL) $6 = <no value available>
(lldb) p $2.buckets()[4].sel()
(SEL) $7 = <no value available>
(lldb) p $2.buckets()[5].sel()
(SEL) $8 = <no value available>
(lldb) p $2.buckets()[6].sel()
(SEL) $9 = <no value available>
(lldb) p $2.buckets()[7].sel()
(SEL) $10 = <no value available>
上述可见，有下列问题:
- 调用了4个方法，但是
buckets()中只缓存了2个sayMaster和sayNB，丢失了2个方法； -
sayMaster后调用，但是索引比sayNB靠前； - 上面2.1小节的打印内容，
sayHello()缓存在索引3里面，并不一定从索引0开始；
带着这些疑问，下面仔细查看cache_t的方法插入流程。
3.2 如何查找缓存的添加？
当然是先看看cache_t有没有提供关于添加或插入的方法，找到了
image.png
void cache_t::incrementOccupied()
{
_occupied++;
}
_occupied的自增，再搜下哪里调用：
image.png
就是在
void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)里面，找到了，就是我们要找的缓存插入方法！方法很长，一段段的看：
3.2.1 insert方法-1
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());
一些断言，跟锁相关，好比数据库的增删改查，当前只能保证一个线程进去写入。
3.2.2 insert方法-2
mask_t newOccupied = occupied() + 1;
unsigned oldCapacity = capacity(), capacity = oldCapacity;
-
mask_t newOccupied = occupied() + 1;索引+1 unsigned oldCapacity = capacity(), capacity = oldCapacity;
unsigned cache_t::capacity()
{
return mask() ? mask()+1 : 0;
}
表示oldCapacity指向mask+1的位置，而capacity指向oldCapacity
3.2.3 insert方法-3 内存扩容
if (slowpath(isConstantEmptyCache())) {
// Cache is read-only. Replace it.
if (!capacity) capacity = INIT_CACHE_SIZE;
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.
}
else {
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;
}
reallocate(oldCapacity, capacity, true);
}
3种情况的判断：
bool cache_t::isConstantEmptyCache()
{
return
occupied() == 0 &&
buckets() == emptyBucketsForCapacity(capacity(), false);
}
-
slowpath标识小概率事件。isConstantEmptyCache()表示找到的bucket_t为空，则reallocate()申请新的内存空间，if (!capacity) capacity = INIT_CACHE_SIZE;如果没有默认空间，则空间为INIT_CACHE_SIZE（大小为1<<2 = 4） -
fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)大概率会进入该条件判断，CACHE_END_MARKER为1，即当前的newOccupied+1 <= 当前capacity的四分之三的情况时，例如capacity =4时，那newOccupied =2，当前只能缓存2个方法，当第3个方法进入时，则需要进入else条件 - 猜猜看下面代码在做什么？
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;
}
reallocate(oldCapacity, capacity, true);
给capacity赋值，要么capacity *2，要么= INIT_CACHE_SIZE 4，不能超过MAX_CACHE_SIZE 1<<16，然后reallocate开辟新的内存空间，这个过程专业术语就是内存扩容。这套流程大致意思就是方法缓存快满时就扩容。
3.2.4 insert方法-4 插入前的准备
bucket_t *b = buckets();
mask_t m = capacity - 1;
mask_t begin = cache_hash(sel, m);
mask_t i = begin;
-
bucket_t *b = buckets();b指针指向 buckets()的首地址 -
mask_t m = capacity - 1;m指向倒数第2个的位置 -
mask_t begin = cache_hash(sel, m);根据哈希算法cache_hash取出m位置的mask_t值 -
mask_t i = begin;将i指向上面的mask_t值
3.2.5 insert方法-5 插入核心算法
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_t::bad_cache(receiver, (SEL)sel, cls);
这段是insert的核心算法，循环的大致流程是：
- 循环终止条件
fastpath((i = cache_next(i, m)) != begin)，其中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;
}
#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;
}
cache_next表示索引i与mask之间计算，得出哈希算法关键字key值，当这个结果key值与begin相等时，则终止循环，否则继续循环
- 循环中的第一个if判断
if (fastpath(b[i].sel() == 0)) {
incrementOccupied();
b[i].set<Atomic, Encoded>(sel, imp, cls);
return;
}
b默认指向buckets()的首地址，取出的索引值i的方法sel() ==0,表示i没有方法时，插入方法b[i].set<Atomic, Encoded>(sel, imp, cls); 自增_occupied，流程结束。
- 循环的第二个if判断
if (b[i].sel() == sel) {
// The entry was added to the cache by some other thread
// before we grabbed the cacheUpdateLock.
return;
}
当前索引i的bucket_t的方法跟当前方法相等时，表示是同一个方法，也结束插入流程。
- 如果循环完毕了，还是没有找到合适的
bucket_t插入方法时，则cache_t::bad_cache(receiver, (SEL)sel, cls);字面意思是没有成功，暂不深究，哈哈。
以上就是插入的整体流程分析，首先判断是否开辟新内存或内存扩容，再以哈希算法遍历buckets()，找到位置插入方法sel 和 imp。
总结
方法缓存的顺序问题
因为哈希表本身也称作散列表，通过把关键码值映射到表中一个位置来访问记录，所以插入顺序并不确定，跟数组的有序插入完全不同，所以上面的方法缓存的位置很随意。
方法缓存的丢失问题
至于buckets()中只缓存了2个方法sayMaster和sayNB，丢失了2个方法。这个问题是因为reallocate(oldCapacity, capacity, true)，看看reallocate源码
ALWAYS_INLINE
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);
if (freeOld) {
cache_collect_free(oldBuckets, oldCapacity);
}
}
第三个参数为true，会进入cache_collect_free(oldBuckets, oldCapacity);，释放了oldBuckets，所以会有几率存在部分方法的丢失问题。
最后附上cache_t缓存的整体流程图:
cache_t插入流程.jpg
