OC中类的结构探索之cache
2021-06-28 本文已影响0人
Eli_app
在前面的文章里面我们已经探索过类的结构《OC中类的结构探索》本篇文章我们重点分析一下cache
cache的结构
我们先看下cache的源码结构，本次继续使用objc4-818.2,下面代码精简一下
typedef unsigned long uintptr_t; //8
#if __LP64__
typedef uint32_t mask_t; // x86_64 & arm64 asm are less efficient with 16-bits
#else
typedef uint16_t mask_t;
#endif
struct cache_t {
private:
explicit_atomic<uintptr_t> _bucketsAndMaybeMask;//8
union {
struct {
explicit_atomic<mask_t> _maybeMask; //4
#if __LP64__
uint16_t _flags; //2
#endif
uint16_t _occupied; //2
};
explicit_atomic<preopt_cache_t *> _originalPreoptCache;//8（结构体指针）
};
/*
#if defined(__arm64__) && __LP64__
#if TARGET_OS_OSX || TARGET_OS_SIMULATOR
// __arm64__的模拟器
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
#else
//__arm64__的真机
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16
#endif
#elif defined(__arm64__) && !__LP64__
//32位 真机
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_LOW_4
#else
//macOS 模拟器
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_OUTLINED
#endif
****** 中间是不同的架构之间的判断 主要是用来不同类型 mask 和 buckets 的掩码
*/
public:
void incrementOccupied();
void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld);
unsigned capacity() const;
struct bucket_t *buckets() const;
Class cls() const;
void insert(SEL sel, IMP imp, id receiver);
//省略。。。
};
我们在源码里面发现有bucket_t还有insert()方法。跟进去看一下insert()的实现，也有bucket_t我们猜测cache里面存储的内容，实际上就是在bucket_t里面存储。我们先看下bucket_t的源码实现
struct bucket_t {
private:
#if __arm64__
explicit_atomic<uintptr_t> _imp;
explicit_atomic<SEL> _sel;
#else
explicit_atomic<SEL> _sel;
explicit_atomic<uintptr_t> _imp;
#endif
}
这个一看我们太熟悉了，里面就是sel和imp，我们用lldb动态调试一下，看看能不能打印出我们想要的内容
(lldb) x/4gx ELPerson.class
0x100008258: 0x0000000100008230 0x0000000100357140
0x100008268: 0x000000010034f390 0x0000802c00000000
(lldb) p (cache_t \*)0x100008268 //0x100008258+0x16=0x100008268内存偏移
(cache_t *) $1 = 0x0000000100008268
(lldb) p *$1
(cache_t) $2 = {
_bucketsAndMaybeMask = {
std::__1::atomic<unsigned long> = {
Value = 4298437520
}
}
= {
= {
_maybeMask = {
std::__1::atomic<unsigned int> = {
Value = 0
}
}
_flags = 32812
_occupied = 0
}
_originalPreoptCache = {
std::__1::atomic<preopt_cache_t *> = {
Value = 0x0000802c00000000
}
}
}
}
可以看到_maybeMask和_occupied的值都是0，我们调用一下方法，看看是不是会有变化
p [per sayNB]
2021-06-24 17:31:51.447839+0800 KCObjcBuild[79832:1703897] NB
(lldb) p *$1
(cache_t) $3 = {
_bucketsAndMaybeMask = {
std::__1::atomic<unsigned long> = {
Value = 4311894672
}
}
= {
= {
_maybeMask = {
std::__1::atomic<unsigned int> = {
Value = 7
}
}
_flags = 32812
_occupied = 1
}
_originalPreoptCache = {
std::__1::atomic<preopt_cache_t *> = {
Value = 0x0001802c00000007
}
}
}
}
(lldb) p $3->buckets()
(bucket_t *) $4 = 0x0000000101024a90
Fix-it applied, fixed expression was:
$3.buckets()
(lldb) p *$4
(bucket_t) $5 = {
_sel = {
std::__1::atomic<objc_selector *> = "" {
Value = ""
}
}
_imp = {
std::__1::atomic<unsigned long> = {
Value = 48968
}
}
}
(lldb) p $5.sel()
(SEL) $6 = "sayNB"
(lldb) p $5.imp(nil,ELPerson.class)
(IMP) $7 = 0x0000000100003d10 (KCObjcBuild`-[ELPerson sayNB])
我们发现方法被调用之后_maybeMask和_occupied都有值了，并且我们打印出来了缓存的方法。
cache_t::insert(SEL sel, IMP imp, id receiver)
1、获取已缓存的容量并且+1，第一次为0
2、获取缓存容量，不存在时，需要先开辟容量，第一次开辟1<<2=4。将bucket_t *首地址存入_bucketsAndMaybeMask，将newCapacity - 1的mask存入_maybeMask，_occupied设置为0。
3、容量情况判断，当容量用完3/4或者7/8时（具体分架构），需要按照2倍的大小扩容。扩容过程开辟新的容量，同时回收旧的容量。
3.1、这个容量是因为负载因子问题，超过这个限制的时候，哈希冲突将会大大增加
3.2、扩容时要清除旧的容量，开辟新的容量。第一、已经开辟出来的内存无法更改，所以不是原内存简单的增加。第二、旧的内存里面的东西如果全部移动到新的内存中耗费性能，并且旧的内存中被调用过的方法，继续调用的概率比较低，全部移动到新内存不划算。如果再次调用，会再新的内存中缓存的。
4、通过哈希算法查找存储的位置，do...while循环查找，没有就存，不能存再哈希，一直找下去。最后不成功，调用bad_cache
4.1在arm64中cache_next会向前插入i ? i-1 : mask，其他架构中，向后插入(i+1) & mask
void cache_t::insert(SEL sel, IMP imp, id receiver)
{
mask_t newOccupied = occupied() + 1; // 1+1
unsigned oldCapacity = capacity(), capacity = oldCapacity;
if (slowpath(isConstantEmptyCache())) {//第一次进来为空
if (!capacity) capacity = INIT_CACHE_SIZE;//capacity = 1 << 2 = 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 {// 超过3/4或者7/8，会2倍扩容
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;
}
// 重新开辟一块capacity * sizeof(bucket_t)大小的内存空间，
// 将`bucket_t *`首地址存入`_bucketsAndMaybeMask`，
// 将`newCapacity - 1`的`mask`存入`_maybeMask`，
// _occupied设置为0，回收旧内存
reallocate(oldCapacity, capacity, true);
}
//创建bucket_t
bucket_t *b = buckets();
mask_t m = capacity - 1; // 4-1=3
//哈希算法，存储
mask_t begin = cache_hash(sel, m);
mask_t i = begin;
do {
//找到为空的地方插入，do...while循环查找
if (fastpath(b[i].sel() == 0)) {
incrementOccupied();
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));
//无论如何都找不到，就bad_cache()
bad_cache(receiver, (SEL)sel);
#endif // !DEBUG_TASK_THREADS
}
cache流程图：
image
