上篇文章中,我们探索了Class的结构,并学习了其内部的成员了isa,superClass以及bits的作用,还剩下一个cache_t cache没有进行详细的介绍,我们只能基本知道,其内部存放的只是一个key和imp的键值对,本文就系统的学习cache_t。
1. cache_t的结构
先看下cache_t的源码
struct cache_t {
struct bucket_t *_buckets;
mask_t _mask;
mask_t _occupied;
...
};
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__
MethodCacheIMP _imp;
cache_key_t _key;
#else
cache_key_t _key;
MethodCacheIMP _imp;
#endif
public:
inline cache_key_t key() const { return _key; }
inline IMP imp() const { return (IMP)_imp; }
inline void setKey(cache_key_t newKey) { _key = newKey; }
inline void setImp(IMP newImp) { _imp = newImp; }
void set(cache_key_t newKey, IMP newImp);
};
- _mask:tmask_t可以看出是一个无符号Int类型,在64位下为uint32_t
- _occupied:字面意思容积
- _buckets:结构体指针
字面意思上cache肯定是一种缓存,而且又与方法有关。我们先猜测,cache的功能就是对方法进行缓存,加快方法调用速度。
2. cache_t 调试
2.1 LLVM调试
还是熟悉的测试代码
@interface AKPerson : NSObject {
NSString *hobby;
}
@property (nonatomic, copy) NSString *name;
- (void)personInstanceMethed;
- (void)personInstanceMethed2;
- (void)personInstanceMethed3;
+ (void)personClassMethod;
@end
@implementation AKPerson
- (void)personInstanceMethed {}
- (void)personInstanceMethed2 {}
- (void)personInstanceMethed3 {}
+ (void)personClassMethod {}
@end
int main(int argc, const char * argv[]) {
@autoreleasepool {
// insert code here...
AKPerson *person = [[AKPerson alloc] init];
Class clz = object_getClass(person);
[person personInstanceMethed];
}
return 0;
}
_mask = 3,_occupied = 2,而且我们在_buckets找到了init和personInstanceMethed方法。
2.2 伪代码调试
LLVM调试太容易蒙圈了,我们用更直观的伪代码调试。
typedef uint32_t mask_t;
typedef uintptr_t cache_key_t;
typedef unsigned long uintptr_t;
struct ak_bucket_t {
IMP _imp;
cache_key_t _key;
};
struct ak_cache_t {
struct ak_bucket_t *_buckets;
mask_t _mask;
mask_t _occupied;
};
struct ak_class_data_bits_t {
uintptr_t bits;
};
struct ak_objc_class {
Class ISA;
Class superclass;
struct ak_cache_t cache; // formerly cache pointer and vtable
struct ak_class_data_bits_t bits; // class_rw_t * plus custom rr/alloc flags
};
int main(int argc, const char * argv[]) {
@autoreleasepool {
// insert code here...
AKPerson *person = [[AKPerson alloc] init];
Class clz = object_getClass(person);
[person personInstanceMethed];
struct ak_objc_class *ak_pClass = (__bridge struct ak_objc_class *)(clz);
for (mask_t i = 0; i < ak_pClass->cache._mask; i++) {
struct ak_bucket_t bucket = ak_pClass->cache._buckets[i];
NSLog(@"%lu - %p",bucket._key,bucket._imp);
}
}
return 0;
}
cmd + B 开始调试
- 调用一个实例方法
- _mask = 3, _occupied = 2,与LLVM调试一致。
- 调用2个实例方法
- _mask = 3, _occupied = 3,一切都很顺利。
- 调用3个实例方法
- 然而当我们一次调用3个实例方法测试时,_mask = 7, _occupied = 1,这又是什么原因呢?
- 为什么缓存了init和personInstanceMethed,没有缓存alloc方法呢?上一章我们说过,对象的方法存在类中,类的类方法以实例方法的形式存在元类中。alloc是类方法,存在元类中。
3. cache_t 策略
通过伪代码测试发现:cache_t不是调用一个方法就添加一个缓存,应该有特殊的缓存策略。
3.1 寻找切入点
- 既然_mask发生了变化,我们就寻着_mask的线索,找cache_t中_mask发生变化的函数。首先想到的就是mask()函数,结果发现其只是反回了_mask本身。
mask_t cache_t::mask()
{
return _mask;
}
- 继续搜索mask(),发现在capacity()中有mask的相应操作,但是很模糊。
mask_t cache_t::capacity()
{
return mask() ? mask()+1 : 0;
}
3.2 expand()
继续搜索capacity(), 找到了expand()扩容方法。
enum {
INIT_CACHE_SIZE_LOG2 = 2,
INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2)
};
void cache_t::expand()
{
cacheUpdateLock.assertLocked();
uint32_t oldCapacity = capacity();
uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;
if ((uint32_t)(mask_t)newCapacity != newCapacity) {
// mask overflow - can't grow further
// fixme this wastes one bit of mask
newCapacity = oldCapacity;
}
reallocate(oldCapacity, newCapacity);
}
- 如果oldCapacity == 0,那么久用INIT_CACHE_SIZE(1<<2 实际为4)来初始化
- 否则,那么就用 oldCapacity * 2 来作为newCapacity。
- reallocate 创建并覆盖原来的缓存reallocate
扩容的逻辑我们已经找到,继续找cache_t何时何地调用了expand()。
3.3 cache_fill_nolock()
很快在cache_fill_nolock中找到了。
static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
cacheUpdateLock.assertLocked();
if (!cls->isInitialized()) return; // 1. 类是否初始化对象,没有就返回
// Make sure the entry wasn't added to the cache by some other thread
// before we grabbed the cacheUpdateLock.
if (cache_getImp(cls, sel)) return; // 2. 通过cls和sel查找是否已经有缓存
cache_t *cache = getCache(cls); // 3. 获取当前cls的缓存
// Use the cache as-is if it is less than 3/4 full
mask_t newOccupied = cache->occupied() + 1; // 4. newOccupied = occupied + 1
mask_t capacity = cache->capacity(); // 5. 获取capacity
if (cache->isConstantEmptyCache()) {
// Cache is read-only. Replace it.
cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE); // 6.1 如果缓存为空,重新创建并覆盖之前的缓存
}
else if (newOccupied <= capacity / 4 * 3) {
// Cache is less than 3/4 full. Use it as-is. // 6.2 如果新的缓存占用大小 <= 缓存容量的四分之三,则可以进行缓存流程
}
else {
// Cache is too full. Expand it.
cache->expand(); // 6.3 如果缓存不为空,且缓存占用大小已经超过了容量的四分之三,则需要进行扩容
}
bucket_t *bucket = cache->find(sel, receiver); // 7. 通过key在缓存中查找到对应的bucket_t
if (bucket->sel() == 0) cache->incrementOccupied();
bucket->set<Atomic>(sel, imp); // 8. 如果找到的bucket中key为0,那么_occupied++, 把key、imp成对放入bucket。
}
- 先根据cls找到当前类的缓存cache
- 新建newOccupied = cache.occupied + 1
- 如果newOccupied为空,新建并覆盖cache
- 如果newOccupied <= cache的容积 * 0.75,缓存
- 如果newOccupied > cache的容积 * 0.75, 扩容
- 把最新的imp和key缓存了下来,cache中仅仅只留下了最新的方法,这里就适用了LRU算法,把最近调用过的方法缓存下来
LRU算法的全称是Least Recently Used,也就是最近最少使用策略——这个策略的核心思想就是先淘汰最近最少使用的内容,在方法缓存中也用到了这种算法
3.4 cache_t::reallocate()
来看下mask和bucket是如何创建的
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
bool freeOld = canBeFreed();
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);
cache_collect(false);
}
}
bucket_t *allocateBuckets(mask_t newCapacity)
{
// Allocate one extra bucket to mark the end of the list.
// This can't overflow mask_t because newCapacity is a power of 2.
// fixme instead put the end mark inline when +1 is malloc-inefficient
bucket_t *newBuckets = (bucket_t *)
calloc(cache_t::bytesForCapacity(newCapacity), 1);
bucket_t *end = cache_t::endMarker(newBuckets, newCapacity);
#if __arm__
// End marker's key is 1 and imp points BEFORE the first bucket.
// This saves an instruction in objc_msgSend.
end->setKey((cache_key_t)(uintptr_t)1);
end->setImp((IMP)(newBuckets - 1));
#else
// End marker's key is 1 and imp points to the first bucket.
end->setKey((cache_key_t)(uintptr_t)1);
end->setImp((IMP)newBuckets);
#endif
if (PrintCaches) recordNewCache(newCapacity);
return newBuckets;
}
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.
// ensure other threads see buckets contents before buckets pointer
mega_barrier();
_buckets = newBuckets;
// ensure other threads see new buckets before new mask
mega_barrier();
_mask = newMask;
_occupied = 0;
}
- oldBuckets获取到当前bucket
- 传入新的缓存容量allocateBuckets初始化bucket_t,保存在newBuckets
- setBucketsAndMask做的操作: 用新创建的bucket保存,mask=newcapcity-1,occupied置零(因为还没有方法缓存)
- 如果缓存不为空(需要释放)则释放原先的bucket、capacity
3.5 4.cache_t::find
cache_t::find是 查找class对应的cache的bucket
bucket_t * cache_t::find(cache_key_t k, id receiver)
{
assert(k != 0);
bucket_t *b = buckets();
mask_t m = mask();
// 通过cache_hash函数【begin = k & m】计算出key值 k 对应的 index值 begin,用来记录查询起始索引
mask_t begin = cache_hash(k, m);
// begin 赋值给 i,用于切换索引
mask_t i = begin;
do {
if (b[i].key() == 0 || b[i].key() == k) {
//用这个i从散列表取值,如果取出来的bucket_t的 key = k,则查询成功,返回该bucket_t,
//如果key = 0,说明在索引i的位置上还没有缓存过方法,同样需要返回该bucket_t,用于中止缓存查询。
return &b[i];
}
} while ((i = cache_next(i, m)) != begin);
// 这一步其实相当于 i = i-1,回到上面do循环里面,相当于查找散列表上一个单元格里面的元素,再次进行key值 k的比较,
//当i=0时,也就i指向散列表最首个元素索引的时候重新将mask赋值给i,使其指向散列表最后一个元素,重新开始反向遍历散列表,
//其实就相当于绕圈,把散列表头尾连起来,不就是一个圈嘛,从begin值开始,递减索引值,当走过一圈之后,必然会重新回到begin值,
//如果此时还没有找到key对应的bucket_t,或者是空的bucket_t,则循环结束,说明查找失败,调用bad_cache方法。
// hack
Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
cache_t::bad_cache(receiver, (SEL)k, cls);
}
- 获取当前cache_t下所有的缓存bucket
- 获取当前cache_t的缓存容量减一的值mask_t
- 获取起始索引
- 遍历bucket_t:如果key == 0 说明索引i位置上还没有缓存过方法;如果bucket的key == k,查询成功,返回bucket_t
4. 总结
4.1 为什么在0.75的时候进行扩容
capacity的变化主要发生在扩容cache->expand()的时候,当缓存已经占满了四分之三的时候,会进行两倍原来缓存空间大小的扩容。
在哈希这种数据结构里面,有一个概念用来表示空位的多少叫做装载因子——装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降 负载因子是3/4的时候,空间利用率比较高,而且避免了相当多的Hash冲突,提升了空间效率
4.2 bucket与mask、capacity、sel、imp的关系
类cls拥有属性cache_t,cache_t中的buckets有多个bucket,bucket里存储着方法实现imp和方法编号sel强转成的key值cache_key_t
- mask对于bucket,主要是用来在缓存查找时的哈希算法
- capacity对于bucket,可以获取到cache_t中bucket的数量
4.3 cache_t的作用
Class中的Cache主要是为了在消息发送的过程中,进行方法的缓存,加快调用效率。其中使用了动态扩容的方法,当容量达到最大值的0.75时,开始2倍扩容,扩容时会完全抹除旧的buckets,并且创建新的buckets代替,之后把最近一次临界的imp和key缓存进来。
4.4 cache_t什么时候调用?
* Cache readers (PC-checked by collecting_in_critical())
* objc_msgSend*
* cache_getImp
cache_fill_nolock的调用时机,我们在源码中可以看到,是在cache_fill中进行了调用。cache_fill的调用时机其实是在method lookup的过程中调用的,而方法查找则要牵扯到objc_msgSend,也就是消息发送机制。所以我们姑且可以认为,在消息发送的过程中,先通过缓存查找imp,如果查找到就直接调用,如果没有,那么就进行缓存。
关于消息发送机制,我们下篇文章会学习。