iOS底层之cache_t探究
我们在iOS底层之类的结构分析分析了类的内部结构，而类的C/C++底层实际是objc_class结构体，其中包含了4个成员。
类的底层结构
那么这一节我们来探究
cache_t——类的方法缓存的真面目，存储了什么，怎么存储的。
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;
}
#endif
#if __LP64__
uint16_t _flags;
#endif
uint16_t _occupied;
// ......
//省略了其他静态成员和方法
这里的系统架构的判断条件宏定义是：
#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
可以看到
CACHE_MASK_STORAGE_HIGH_16——真机64位架构
CACHE_MASK_STORAGE_LOW_4——真机非64位架构
CACHE_MASK_STORAGE_OUTLINED——非真机即macOS环境
在macOS环境和真机64位环境下，它们的区别是：
cache_t结构
cache_t的成员主要包括了:
-
macOS环境下:
_buckets：桶，包含了sel方法编号、imp函数指针地址。原子安全的。
_mask：掩码。原子安全的。 -
64位真机环境下 :
_maskAndBuckets：将_mask和_buckets放在一起。也就是存储_mask&_buckets的结果。原子安全的。
公共成员：
_mask_unused：未使用的掩码，全局搜索后发现，这个成员并没有被使用，猜测可能是没开源出来或者是这部分还未写完。
_flags：位置标识。
_occupied：已占用的。
1.成员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<uintptr_t> _imp;
explicit_atomic<SEL> _sel;
#else
explicit_atomic<SEL> _sel;
explicit_atomic<uintptr_t> _imp;
#endif
}
可以看到存储了_imp和_sel，它们都是原子安全的，区别是，它们的顺序不一样。在64位环境下，imp放在前面对arm64e架构的ptrauth更好，而其他环境下，sel放在前面对armv7*、i386、 x86_64架构更优。
那么我们知道了bucket_t的结构，就可以通过项目去查看下我们实例的对象的方法编号和实现了。
定义一个类，包括属性和实例方法、类方法。
@interface BKPerson : NSObject
@property (nonatomic, copy) NSString *name;
@property (nonatomic, strong) NSString *nickName;
- (void)sayHello;
- (void)sayWorld;
- (void)sayMaster;
- (void)sayNB;
+ (void)sayHappy;
@end
@implementation BKPerson
- (void)sayHello{
NSLog(@"BKPerson say : %s",__func__);
}
- (void)sayWorld{
NSLog(@"BKPerson say : %s",__func__);
}
- (void)sayMaster{
NSLog(@"BKPerson say : %s",__func__);
}
- (void)sayNB{
NSLog(@"BKPerson say : %s",__func__);
}
+ (void)sayHappy{
NSLog(@"BKPerson say : %s",__func__);
}
在main.m文件中
int main(int argc, const char * argv[]) {
@autoreleasepool {
BKPerson *p = [BKPerson alloc];
Class pClass = [BKPerson class];
[p sayHello];
[p sayWorld];
[p sayMaster];
NSLog(@"%@",pClass);
}
return 0;
}
在[p sayHello];设置一个断点，运行，并打印调试BKPerson类的cache_t信息：
这一步通过打印类的内存首地址，偏移16个字节（isa和superclass成员各占了8字节）后得到的内存位置就是cache_t的信息。打印可以看到，这时候只初始化了类的实例对象，还没有执行实例方法。_buckets里的_sel=null，_imp=0，而且_mask=0，_occupied=0。
我们将断点跳到下一行代码。再打印cache_t：
可以看到这时候的
cache_t里面是：_buckets里的_sel=""，_imp=11928，而且_mask=3，_occupied=1。而这个变数是因为我们执行了sayHello这个方法。
难道真的是因为执行了sayHello吗，我不信？
为了验证这一点，那么可以打印下_buckets的信息：
⚠️这里要注意的是：如果直接使用打印的信息里的成员去打印，像图上那样的，是会取不到的。这时候我们可以查看cache_t的定义，看看有没有相关的方法。
struct cache_t {
struct bucket_t *buckets();
mask_t mask();
mask_t occupied();
}
可以找到以上方法，而如果要打印sel和imp，则需要查看bucket_t的定义:
struct bucket_t {
inline SEL sel() const { return _sel.load(memory_order::memory_order_relaxed); }
inline IMP imp(Class cls) const {
uintptr_t imp = _imp.load(memory_order::memory_order_relaxed);
if (!imp) return nil;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
SEL sel = _sel.load(memory_order::memory_order_relaxed);
return (IMP)
ptrauth_auth_and_resign((const void *)imp,
ptrauth_key_process_dependent_code,
modifierForSEL(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
}
}
这时再通过以上方法打印：
可以百分百确定，由于执行到了sayHello方法，所以cache_t存储的信息发生了改变。
进一步验证，我们把断点跳到下一行。执行了sayWorld方法。
可以看到这时的_occupied=2，但是我们继续用之前的方式打印sel和imp，却还是只能打印出sayHello，而sayWorld没看到，但是通过成员名_buckets可以确定这是一个集合类型。
那么问题是，如何打印出_buckets这个集合里的所有元素？
这里有两种方式：
第一种：使用数组下标的方式访问元素
既然我们知道
buckets是个数组，那么可以用下标方式，取出第0个、第1个元素，而打印第1个元素，可以得到sayWorld的信息。
第二种：使用地址偏移，访问集合元素
我们知道，对于一个数组，我们可以将
数组指针+下标数，之后对其*取值，得出元素。比如，这里sayWorld是第二个元素，则对buckets数组指针，进行+1，之后用*整体取值，可以得出sayWorld元素。
可以发现，我们现在是在源码环境，而每次打印值都需要$取变量，很麻烦。那我们能在日常开发环境中进行调试吗？
答案是肯定的。
脱离源码环境，我们可以模拟底层的类型结构，一样可以调试。
typedef uint32_t mask_t; // x86_64 & arm64 asm are less efficient with 16-bits
struct my_bucket_t {
SEL _sel;
IMP _imp;
};
struct my_cache_t {
struct my_bucket_t * _buckets;
mask_t _mask;
uint16_t _flags;
uint16_t _occupied;
};
struct my_class_data_bits_t {
uintptr_t bits;
};
struct my_objc_class {
Class ISA;
Class superclass;
struct my_cache_t cache; // formerly cache pointer and vtable
struct my_class_data_bits_t bits; // class_rw_t * plus custom rr/alloc flags
};
我们只需要取我们需要的成员，继承的关系也可以不要了。而这里需要注意的是：由于objc_class是继承于objc_object，也就继承了isa成员，所以我们去掉了继承的关系后，就要加上isa成员。否则，在打印类的cache_t的相关信息时，就会打印不到正确的值。
之后就可以打印类的方法sel和imp了。
int main(int argc, const char * argv[]) {
@autoreleasepool {
BKPerson *p = [BKPerson alloc];
Class pClass = [BKPerson class]; // objc_clas
[p eat1];
[p eat2];
[p eat3];
[p eat4];
struct my_objc_class *my_pClass = (__bridge struct my_objc_class *)(pClass);
NSLog(@"%hu - %u",my_pClass->cache._occupied,my_pClass->cache._mask);
for (mask_t i = 0; i<my_pClass->cache._mask; i++) {
// 打印获取的 bucket
struct my_bucket_t bucket = my_pClass->cache._buckets[I];
NSLog(@"%@ - %p",NSStringFromSelector(bucket._sel),bucket._imp);
}
NSLog(@"Hello, World!");
}
return 0;
}
但是当我们只执行eat1和eat2，和执行eat1～eat4，对比打印信息，可以看到：
可以看到_occupied都是2，而_mask从2变成7，而且后一张图的buckets里打印的eat1和eat2不见了，而且eat3和eat4的顺序，是错乱的。
提出问题：_occupied和_mask是什么，为什么_occupied都是2，_mask从2变成7，为什么有些方法缺失了，为什么顺序混乱？
可以知道，产生变化是由于函数的调用，而非成员属性发生变化。
那么从源码查找cache_t，主要包含了以下的函数：
struct cache_t {
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();
}
点入occupied()
mask_t cache_t::occupied()
{
return _occupied;
}
void cache_t::incrementOccupied()
{
_occupied++;
}
可以看到occupied()是一个get方法，incrementOccupied()是对_occupied的递增操作。这就是重点所在。
全局搜索incrementOccupied()的调用，可以看到在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
mask_t newOccupied = occupied() + 1;
unsigned oldCapacity = capacity(), capacity = oldCapacity;
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)) { // 4 3 + 1 bucket cache_t
// Cache is less than 3/4 full. Use it as-is.
}
else {
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE; // 扩容两倍 4
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;
}
reallocate(oldCapacity, capacity, true); // 内存 库容完毕
}
bucket_t *b = buckets();
mask_t m = capacity - 1;
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();
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分析
mask_t newOccupied = occupied() + 1;：对occupied()加一。
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)) { // 4 3 + 1 bucket cache_t
// Cache is less than 3/4 full. Use it as-is.
}
else {
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE; // 扩容两倍 4
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;
}
reallocate(oldCapacity, capacity, true); // 内存 库容完毕
}
这一步有三个条件跳转语句：
1. 如果是初始化：
由于初始化的情况比较少，所以系统使用slowpath修饰条件以加快指令跳转，当isConstantEmptyCache()缓存为空的时候，也就是刚初始化时，if (!capacity) capacity = INIT_CACHE_SIZE;，给capacity赋初值为4。
INIT_CACHE_SIZE_LOG2 = 2,
INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2),
从上面宏知道INIT_CACHE_SIZE的值为4。
之后执行reallocate(oldCapacity, capacity, /* freeOld */false);重新梳理。
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);
}
}
reallocate这个函数里主要做的是：根据newCapacity开辟buckets内存，而setBucketsAndMask函数定义
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
// objc_msgSend uses mask and buckets with no locks.
// It is safe for objc_msgSend to see new buckets but old mask.
// (It will get a cache miss but not overrun the buckets' bounds).
// It is unsafe for objc_msgSend to see old buckets and new mask.
// Therefore we write new buckets, wait a lot, then write new mask.
// objc_msgSend reads mask first, then buckets.
#ifdef __arm__
// ensure other threads see buckets contents before buckets pointer
mega_barrier();
_buckets.store(newBuckets, memory_order::memory_order_relaxed);
// ensure other threads see new buckets before new mask
mega_barrier();
_mask.store(newMask, memory_order::memory_order_relaxed);
_occupied = 0;
#elif __x86_64__ || i386
// ensure other threads see buckets contents before buckets pointer
_buckets.store(newBuckets, memory_order::memory_order_release);
// ensure other threads see new buckets before new mask
_mask.store(newMask, memory_order::memory_order_release);
_occupied = 0;
#else
#error Don't know how to do setBucketsAndMask on this architecture.
#endif
}
做了初始化的工作：根据_buckets和_mask进行内存初始化工作，_occupied设置为0。
2. 如果小于capacity的3/4时
fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)
#define CACHE_END_MARKER 1
可以看到这个宏定义为1，也就是fastpath大部分情况下是这个条件newOccupied+1<= capacity的3/4，则不执行任何语句。
3. 其他情况：也就是newOccupied+1>capacity的3/4
这时候则需要内存扩容：
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;,如果capacity等于0，则给初始值4，否则，扩容为原来的两倍。
if (capacity > MAX_CACHE_SIZE) { capacity = MAX_CACHE_SIZE; }
MAX_CACHE_SIZE_LOG2 = 16,
MAX_CACHE_SIZE = (1 << MAX_CACHE_SIZE_LOG2),
防止扩容后的capacity超出最大值，最大值为1左移16位。
之后重新梳理内存reallocate(oldCapacity, capacity, true);，要注意这里传入的第三个参数为true，所以会执行reallocate函数里的清理旧垃圾的代码。
if (freeOld) {
cache_collect_free(oldBuckets, oldCapacity);
}
cache_collect_free的定义
static void cache_collect_free(bucket_t *data, mask_t capacity)
{
#if CONFIG_USE_CACHE_LOCK
cacheUpdateLock.assertLocked();
#else
runtimeLock.assertLocked();
#endif
if (PrintCaches) recordDeadCache(capacity);
_garbage_make_room ();
garbage_byte_size += cache_t::bytesForCapacity(capacity);
garbage_refs[garbage_count++] = data;
cache_collect(false);
}
static void _garbage_make_room(void)
{
static int first = 1;
// Create the collection table the first time it is needed
if (first)
{
first = 0;
garbage_refs = (bucket_t**)
malloc(INIT_GARBAGE_COUNT * sizeof(void *));
garbage_max = INIT_GARBAGE_COUNT;
}
// Double the table if it is full
else if (garbage_count == garbage_max)
{
garbage_refs = (bucket_t**)
realloc(garbage_refs, garbage_max * 2 * sizeof(void *));
garbage_max *= 2;
}
}
enum {
INIT_GARBAGE_COUNT = 128
};
作用：上面我们只是给capacity标记扩容了，那么内存也要相应扩容。
-
_garbage_make_room
初始时，first=1，将first = 0并且开辟128个指针类型字节大小的bucket_t类型指针，垃圾最大值为128。这时候的capacity为4。
如果表已经满了，也就是垃圾达到了128。重新开辟两倍原来的garbage_max大小的内存给bucket_t类型指针，也就是buckets。
否则，则不执行任何代码。 -
garbage_byte_size += cache_t::bytesForCapacity(capacity);
将旧capacity容量加入整个垃圾容量里。 -
garbage_refs[garbage_count++] = data;
将这一次执行的方法缓存先置放在garbage_count下标的位置。
总结：前面就是根据capacity标记进行方法缓存空间的申请，不足则需要扩容。扩容时会将之前的缓存抹除掉，重新开辟双倍大小的空间。扩容之后可以直接开始存储了，不需要算法扫描是否有同样的方法缓存，更加快速。
回到insert方法。
下面
bucket_t *b = buckets();
mask_t m = capacity - 1;
mask_t begin = cache_hash(sel, m);
mask_t i = begin;
mask_t m = capacity - 1;根据这一句，可以知道前面的mask就是capacity - 1，如果初始化的时候，那么mask=3，如果扩容后，就是4*2-1=7。
static inline mask_t cache_hash(SEL sel, mask_t mask)
{
return (mask_t)(uintptr_t)sel & mask;
}
传入sel和mask的算法计算哈希表存储的位置。
运行断点调试，可以看到当执行sayMaster算出的key值为2，再手动传入sayHellow和sayWorld的sel之后，得出的key分别为0和1。
// 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));
扫描第一个未使用的插槽，保证必定会有一个可用插槽，因为最小尺寸是4，而我们前面已经修改了为3/4就满了。
当扫描哈希表时，大多数情况下b[i].sel() == 0)成立，也就是空插槽，那么就对occupied加1。而
template<Atomicity atomicity, IMPEncoding impEncoding>
void bucket_t::set(SEL newSel, IMP newImp, Class cls)
{
ASSERT(_sel.load(memory_order::memory_order_relaxed) == 0 ||
_sel.load(memory_order::memory_order_relaxed) == newSel);
// objc_msgSend uses sel and imp with no locks.
// It is safe for objc_msgSend to see new imp but NULL sel
// (It will get a cache miss but not dispatch to the wrong place.)
// It is unsafe for objc_msgSend to see old imp and new sel.
// Therefore we write new imp, wait a lot, then write new sel.
uintptr_t newIMP = (impEncoding == Encoded
? encodeImp(newImp, newSel, cls)
: (uintptr_t)newImp);
if (atomicity == Atomic) {
_imp.store(newIMP, memory_order::memory_order_relaxed);
if (_sel.load(memory_order::memory_order_relaxed) != newSel) {
#ifdef __arm__
mega_barrier();
_sel.store(newSel, memory_order::memory_order_relaxed);
#elif __x86_64__ || __i386__
_sel.store(newSel, memory_order::memory_order_release);
#else
#error Don't know how to do bucket_t::set on this architecture.
#endif
}
} else {
_imp.store(newIMP, memory_order::memory_order_relaxed);
_sel.store(newSel, memory_order::memory_order_relaxed);
}
}
这个函数将类的sel和imp存储到缓存中。之后return跳出。
如果插槽不为空，则判断插槽里的sel和当前要存的sel是否是同一个，如果相同，就返回，不存储。
如果不相同，则执行while语句。如果cache表的下一个插槽的key不等于当前begin，则执行do代码块，如此循环扫描，直到找到插槽插入。
static inline mask_t cache_next(mask_t i, mask_t mask) {
return (i+1) & mask;
}
这是cache_next的算法。
总结：mask数值等于capacity - 1，使用cache_hash算法获得当前sel的在哈希表的begin开始扫描位置，如果begin位置的插槽为空则存储并返回，不为空则判断是否是同一个sel，相同则返回，不同则使用cache_next算法得到下一个扫描位置，跟当前begin比对，不是同个插槽，则继续循环上面的查找逻辑。
这样就可以解释上面的问题了。
问：_occupied和_mask是什么，为什么_occupied都是2，_mask从2变成7，为什么有些方法缺失了，为什么顺序混乱？
答：_occupied是占用的方法缓存数，_mask是缓存容量的capacity-1，_mask从2变成7是因为capacity初始值为4，容量扩容算法capacity*2，_mask就等于新的capacity-1等于7，而扩容会清理之前的缓存，导致了方法缺失，顺序混乱是因为通过哈希算法以sel为key存储导致。
cache_t的原理分析图如下
cache_t原理分析图
