前言
从前面一篇文章类的原理探究中，我们可以看到类的结构如下：
// 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
.....
}
并且我们在上一篇文章中已经探索了类的bits数据结构，今天我们来看一下类的cache_t的结构
开始探究
1.cache_t数据结构
通过LLDB输出cache_t的结构如下：
从输出的结构信息中，我们得不到太多的信息，这个时候我们应该去源码中查看一下cache_t结构体信息。从源码中我们可以看到在cache_t主要是对
bucket_t数据进行操作
struct cache_t {
static bucket_t *emptyBuckets();
static bucket_t *allocateBuckets(mask_t newCapacity);
static bucket_t *emptyBucketsForCapacity(mask_t capacity, bool allocate = true);
static struct bucket_t * endMarker(struct bucket_t *b, uint32_t cap);
struct bucket_t *buckets() const;
}
那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
}
从源码中我们可以看到bucket_t里面存储的就是方法的SEL与IMP，那么怎么验证呢，我们从cache_t结构体中可以看到它提供了一个struct bucket_t *buckets() const;buckets()函数，
所以下面我们通过LLDB获取一下bucket_t数据如下：
但是一看，里面数据为空啊，所以我们调用一下类的对象方法，然后用LLDB输出bucket_t的sel与imp
所以cache_t是针对于方法进行缓存。并且它的数据结构是
struct cache_t {
private:
explicit_atomic<uintptr_t> _bucketsAndMaybeMask; // 存储的是buckets地址与maybeMask
union {
struct {
explicit_atomic<mask_t> _maybeMask; // maybeMask是开辟的大小-1
#if __LP64__
uint16_t _flags;
#endif
uint16_t _occupied; // 缓存的方法数量
};
explicit_atomic<preopt_cache_t *> _originalPreoptCache;
};
2. sel与imp缓存的插入与读取
在cache_t结构中有一个insert方法，下面我们来看一下insert方法。
void cache_t::insert(SEL sel, IMP imp, id receiver)
{
// Use the cache as-is if until we exceed our expected fill ratio.
//如果超过了预期的填充比率，就按原样使用缓存。
mask_t newOccupied = occupied() + 1; // 1+1
unsigned oldCapacity = capacity(), capacity = oldCapacity;
if (slowpath(isConstantEmptyCache())) {
// Cache is read-only. Replace it.
if (!capacity) capacity = INIT_CACHE_SIZE;//4，开辟的大小
reallocate(oldCapacity, capacity, /* freeOld */false);
}
else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) {
// 缓存小于3/4或7/8。按原样使用它。
}
#if CACHE_ALLOW_FULL_UTILIZATION
else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) {
// Allow 100% cache utilization for small buckets. Use it as-is.
}
#endif
else {// 4*2 = 8
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE; //当缓存使用超过3/4的时候进行两倍扩容。
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;
}
reallocate(oldCapacity, capacity, true);
}
bucket_t *b = buckets();//读取已有的缓存
mask_t m = capacity - 1; // 4-1=3
mask_t begin = cache_hash(sel, m);//类指向缓存。SEL是key。buckets缓存SEL+IMP。缓存从来没有建立在dyld共享缓存。
mask_t i = begin;//插入位置
// Scan for the first unused slot and insert there.
// There is guaranteed to be an empty slot.
// 扫描第一个未使用的插槽并在那里插入。
//保证有一个空槽。
do {
if (fastpath(b[i].sel() == 0)) {//如果有空的位置，进行sel与imp插入
incrementOccupied(); //occupied = occupied + 1
b[i].set<Atomic, Encoded>(b, 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_next(i, m)避免哈希冲突
bad_cache(receiver, (SEL)sel);
}
#if CACHE_END_MARKER
static inline mask_t cache_next(mask_t i, mask_t mask) {
return (i+1) & mask;
}
#elif __arm64__
static inline mask_t cache_next(mask_t i, mask_t mask) {
return i ? i-1 : mask;
}
#else
总结一下就是：
1.就是先开辟一个bucket_t哈希表，并且将buckets地址与_maybeMask存储在cache_t结构体的_bucketsAndMaybeMask变量中。_maybeMask = capacity -1，capacity是开辟空间的大小。
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) {
collect_free(oldBuckets, oldCapacity);
}
}
2.检查buckets使用率是否小于3/4,如果大于3/4就进行2倍扩容
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;//capacity开辟的大小
3.找到空的位置插入sel+imp
if (fastpath(b[i].sel() == 0)) {
incrementOccupied();
b[i].set<Atomic, Encoded>(b, sel, imp, cls());
return;
}
接下来看一下imp与sel的读取，也就是查看一下buckets()函数的实现，然后在查看bucket_t结构体里面提供的方法。
struct bucket_t *cache_t::buckets() const
{
uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
return (bucket_t *)(addr & bucketsMask);
}
struct bucket_t {
inline SEL sel() const { return _sel.load(memory_order_relaxed); }
inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls) const
}
bucketsMask是啥呢？
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
// _bucketsAndMaybeMask 是 buckets_t 指针
// _maybeMask is the buckets mask
static constexpr uintptr_t bucketsMask = ~0ul; //18446744073709551615
static_assert(!CONFIG_USE_PREOPT_CACHES, "preoptimized caches not supported");
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
static constexpr uintptr_t maskShift = 48;
static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << maskShift) - 1;
static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS, "Bucket field doesn't have enough bits for arbitrary pointers.");
#if CONFIG_USE_PREOPT_CACHES
static constexpr uintptr_t preoptBucketsMarker = 1ul;
static constexpr uintptr_t preoptBucketsMask = bucketsMask & ~preoptBucketsMarker;
#endif
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
// _bucketsAndMaybeMask是一个低48位的buckets_t指针
// _maybeMask未使用时，掩码存储在前16位。
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;
// Ensure we have enough bits for the buckets pointer.
static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS,
"Bucket field doesn't have enough bits for arbitrary pointers.");
#if CONFIG_USE_PREOPT_CACHES
static constexpr uintptr_t preoptBucketsMarker = 1ul;
#if __has_feature(ptrauth_calls)
// 63..60: hash_mask_shift
// 59..55: hash_shift
// 54.. 1: buckets ptr + auth
// 0: always 1
static constexpr uintptr_t preoptBucketsMask = 0x007ffffffffffffe;
static inline uintptr_t preoptBucketsHashParams(const preopt_cache_t *cache) {
uintptr_t value = (uintptr_t)cache->shift << 55;
// masks have 11 bits but can be 0, so we compute
// the right shift for 0x7fff rather than 0xffff
return value | ((objc::mask16ShiftBits(cache->mask) - 1) << 60);
}
#else
// 63..53: hash_mask
// 52..48: hash_shift
// 47.. 1: buckets ptr
// 0: always 1
static constexpr uintptr_t preoptBucketsMask = 0x0000fffffffffffe;
static inline uintptr_t preoptBucketsHashParams(const preopt_cache_t *cache) {
return (uintptr_t)cache->hash_params << 48;
}
#endif
#endif // CONFIG_USE_PREOPT_CACHES
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
// _bucketsAndMaybeMask is a buckets_t pointer in the top 28 bits
// _maybeMask is unused, the mask length is stored in the low 4 bits
static constexpr uintptr_t maskBits = 4;
static constexpr uintptr_t maskMask = (1 << maskBits) - 1;
static constexpr uintptr_t bucketsMask = ~maskMask;
static_assert(!CONFIG_USE_PREOPT_CACHES, "preoptimized caches not supported");
#else
我在x86_64上面运行，bucketsMask = ~0ul，_bucketsAndMaybeMask是buckets_t的指针，验证如下：
总结
用两张图来总结一下cache_t结构与方法缓存的流程
