OC底层探索（八）：cache

cache 很好理解就是缓存，缓存的作用大家都很熟悉，就为了下次能够快速的读取，提升性能, 之前分析了bits，我们也看到了类结构里有cache_t，缓存了什么，接下来我们探索一下

cache_t的数据结构

成员变量

struct cache_t {
private:
    // buckets 的指针/首地址 , explicit_atomic<T> 确定类型 允许转换, uintptr_t = unsigned long 无符号长整型
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask;  //8
    // 联合体，内存共享，成员变量互斥
    union {
        struct {
            // mask_t: mac: uint32_t, 真机：uint16_t
            // 掩码
            explicit_atomic<mask_t>    _maybeMask; //4
#if __LP64__ // 架构是64位
            // 标记
            uint16_t                   _flags; // 2
#endif
            //已占用数量
            uint16_t                   _occupied; //2
        };
        // 指针，原始的规则缓存
        explicit_atomic<preopt_cache_t *> _originalPreoptCache; //8
    };
   .....
   .....
 }
复制代码

真机架构下常量

    // 真机
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    
    // _bucketsAndMaybeMask is a buckets_t pointer in the low 48 bits
    // _bucketsAndMaybeMask 是 buckets_t 指针的 低48位
    
    // _maybeMask is unused, the mask is stored in the top 16 bits.
    // _maybeMask 未使用使用， 掩码存在高16位

    // How much the mask is shifted by.
    // 掩码需要移动多少
    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.
    // 掩码必须要有额外的4位，msgSend需要用到这些位去构建值
    //  _maskAndBuckets 的 `mask << 4` (掩码左移4位)在一条指令中
    static constexpr uintptr_t maskZeroBits = 4;
    
    // The largest mask value we can store.
    // 能存储掩码的最大值 1 << 64 - 48 - 1
    static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
    
    // The mask applied to `_maskAndBuckets` to retrieve the buckets pointer.
    // bucketsMask 用于'_maskAndBuckets ' 来检索buckets指针的掩码
    // 1 << 48 - 4 - 1
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
    
    // Ensure we have enough bits for the buckets pointer.
    // 确保我们有足够的位用于 buckets 指针。
    // MACH_VM_MAX_ADDRESS 0x10 0000 0000 = 1 << 36
    // bucketsMask = 1 << 43
    static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS,
            "Bucket field doesn't have enough bits for arbitrary pointers.");
          
 #if CONFIG_USE_PREOPT_CACHES // 真机是 1
    // 优先 Buckets 标记
    static constexpr uintptr_t preoptBucketsMarker = 1ul;
    
#if __has_feature(ptrauth_calls)  // A12 以上是 1 ，arme64e

struct preopt_cache_t {
    int32_t  fallback_class_offset; // 4 
    union {
        struct {
            uint16_t shift       :  5; 
            uint16_t mask        : 11; 
        };
        uint16_t hash_params; 
    };
    uint16_t occupied    : 14; 
    uint16_t has_inlines :  1;
    uint16_t bit_one     :  1;
    preopt_cache_entry_t entries[];

    inline int capacity() const {
        return mask + 1;
    }
};

// 63..60: hash_mask_shift
// 59..55: hash_shift
// 54.. 1: buckets ptr + auth
//      0: always 1

// 优先 Buckets 标记, 0x007ffffffffffffe ，56位，前两位和最后一位是0
static constexpr uintptr_t preoptBucketsMask = 0x007ffffffffffffe;
// 优先 Buckets 哈希参数
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
    // 掩码有11位，但是可能是0， 所以我们计算右移 0x7fff 而不是 0xffff
    return value | ((objc::mask16ShiftBits(cache->mask) - 1) << 60);
}
#else // A12 以下

// 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;
}
复制代码

可以看出 cache_t与 buckets 很有关系

struct bucket_t *buckets() const;

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
复制代码

buckets 存的就是 sel跟 imp ，只是不同架构存到位置不一样

函数（不全）

bool isConstantEmptyCache() const;

bool cache_t::isConstantEmptyCache() const
{
    return
        occupied() == 0  &&
        buckets() == emptyBucketsForCapacity(capacity(), false);
}

mask_t cache_t::occupied() const
{
    return _occupied;
}

复制代码

缓存是否为空 _occupied == 0
maskAndBuckets >> maskShift (48) 是否有值

bool canBeFreed() const;

bool cache_t::canBeFreed() const
{
    return !isConstantEmptyCache() && !isConstantOptimizedCache();
}
复制代码

是否可以释放
缓存不为空并且不是优先缓存（OptimizedCache）

mask_t mask() const;

真机
mask_t cache_t::mask() const
{
 // maskAndBuckets 也就是 buckets 的首地址
 // maskShift = 48
    uintptr_t maskAndBuckets = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return maskAndBuckets >> maskShift;
}
复制代码

maskAndBuckets 也就是 buckets 的首地址
maskShift = 48
也就是buckets 的首地址右移48位

initializeToPreoptCacheInDisguise

void cache_t::initializeToPreoptCacheInDisguise(const preopt_cache_t *cache)
{
    // preopt_cache_t::bit_one is 1 which sets the top bit  设置在最高的bit_one = 1
    // and is never set on any valid selector // 不会设置在有效的 selector上

    uintptr_t value = (uintptr_t)cache + sizeof(preopt_cache_t) -
            (bucket_t::offsetOfSel() + sizeof(SEL));

    _originalPreoptCache.store(nullptr, std::memory_order_relaxed);
    setBucketsAndMask((bucket_t *)value, 0);
    _occupied = cache->occupied;
}
 * +----------------+----------------+
 * |      IMP       |       SEL      | << a bucket_t
 * +----------------+----------------+--------------...
 * preopt_cache_t >>|               1| ...
 *                  +----------------+--------------...
复制代码

将共享缓存标记放在 sel上

void incrementOccupied();

void cache_t::incrementOccupied() 
{
    _occupied++;
}
复制代码

占用数量 ++

插入缓存 insert(SEL sel, IMP imp, id receiver)

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    // 互斥锁
    runtimeLock.assertLocked();

    // 类是否已经初始化
    // Never cache before +initialize is done
    if (slowpath(!cls()->isInitialized())) {
        return;
    }
    
    // 是否是共享缓存
    if (isConstantOptimizedCache()) {
        _objc_fatal("cache_t::insert() called with a preoptimized cache for %s",
                    cls()->nameForLogging());
    }

#if DEBUG_TASK_THREADS
    return _collecting_in_critical();
#else
#if CONFIG_USE_CACHE_LOCK
    mutex_locker_t lock(cacheUpdateLock);
#endif

    // 是否有sel 并且 类是否初始化
    ASSERT(sel != 0 && cls()->isInitialized());

    // Use the cache as-is if until we exceed our expected fill ratio.
    // 使用缓存，知道超出填充率
    // 新的方法数量 ==  _occupied + 1, 开始 _occupied = 0
    mask_t newOccupied = occupied() + 1; // _occupied + 1
    /*
     mask_t cache_t::mask() const
    {
        uintptr_t maskAndBuckets = _bucketsAndMaybeMask.load(memory_order_relaxed);
        return maskAndBuckets >> maskShift;
    }
    */
    // capacity() = mask() ? mask()+1 : 0;
    
    // 获取容量
    unsigned oldCapacity = capacity(), capacity = oldCapacity; //
    if (slowpath(isConstantEmptyCache())) {
        // 如果是空的话，从新初始化 buckets, INIT_CACHE_SIZE = 4
        // 容量为4
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE;
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    // 开始 newOccupied = 1 + 0 <= 2 * 7 / 8
    else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) {
        // Cache is less than 3/4 or 7/8 full. Use it as-is.
    }
#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 {
        // 两倍扩容
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        // 将旧缓存清空，从新开辟一块新的缓存
        reallocate(oldCapacity, capacity, true);
    }

    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    /*static inline mask_t cache_hash(SEL sel, mask_t mask) 
    {
        uintptr_t value = (uintptr_t)sel;
    #if CONFIG_USE_PREOPT_CACHES
        value ^= value >> 7;
    #endif
        return (mask_t)(value & mask);
    }
    */
    // 哈希算法，算出最开始的位置  
    // (sel ^ (sel >> 7)) & 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.
    // 找个第一个未使用的位置插入
    do {
     //  查看sel存在
        if (fastpath(b[i].sel() == 0)) {
            // 存在 _occupied++
            // 将sel和imp 存到 bucket中
            //  <Atomic, Encoded> 加锁，编码
            // enum Atomicity { Atomic = true, NotAtomic = false };
            // enum IMPEncoding { Encoded = true, Raw = false };
            incrementOccupied();
            // 将sel和imp 存到 bucket中
            b[i].set<Atomic, Encoded>(b, sel, imp, cls());
            return;
        }
        // 如果当前位子的sel 是正要缓存的sel，则return
        if (b[i].sel() == sel) {
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
        }
     // 如果当前i 位子，已有缓存，并且 不是当前要缓存的 sel，则找下一个位子
    // i ? i-1 : mask; 向前找下一个位子，如果找到第一个位子的话，就放在m的位子上，也就是容量 - 1
    // 并且位子不能是第一个位置，如果是的话则退出循环
    } while (fastpath((i = cache_next(i, m)) != begin));

    bad_cache(receiver, (SEL)sel);
#endif // !DEBUG_TASK_THREADS
}
复制代码

类是否初始化
是否是共享缓存
sel 不为 0，并且再次判断类是否初始化
newOccupied = occupied + 1，占用数量加1
获取就的容量大小
缓存是否是空的，容量是否为空，
如果是空的容量 capacity = 4, 重新按容量开辟内存
如果不是空判断 newOccupied + 1 <= capacity * 3 / 4
true则不作处理
false,则 capacity = capacity ？capacity * 2 : 4, 最大 capacity = 1 << 16，清空旧的cache，按容量再开辟一块缓存空间
取出 buckets, 赋值mask = capacity - 1
通过哈希函数确定开始的位置，begin = sel ^ (sel >> 7) & mask
判断 begin 位置是否有缓存，没有 buckets[i] bucket 换粗
在判断当前位置的缓存是不是将要缓存的 sel，如果是则 return
都不符合的话 cache_next,向上寻找下一片缓存位置 i = i ? i - 1 : mask, 找到为 0 的位则缓存在mask的位置，依次循环
不符合，则是错误缓存