我们在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
的成员主要包括了:
-
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
,它们都是原子安全的,区别是,它们的顺序不一样。在arm64
位环境下,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的原理分析图如下