四：类结构分析四：Cache_t

前情回顾：

!! 两节课为大家介绍了class_data_bits_t中的class_rw_t，然后从中获取我们的成员变量和属性，以及我们的对象方法,并且能通过元类获取我们的类方法.

本节知识点：

!!! 我们来讲解cache_t

struct objc_class : objc_object {
    // 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

    class_rw_t *data() const {
        return bits.data();
    }
    void setData(class_rw_t *newData) {
        bits.setData(newData);
    }
}

三个环境的cache_t(macOS、真机、模拟器)

struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED  //macOS环境
    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;
    static constexpr uintptr_t maskShift = 48;
    static constexpr uintptr_t maskZeroBits = 4;
    static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
   
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
        static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS, "Bucket field doesn't have enough bits for arbitrary pointers.");
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4 // 模拟器环境
   
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;
    static constexpr uintptr_t maskBits = 4;
    static constexpr uintptr_t maskMask = (1 << maskBits) - 1;
    static constexpr uintptr_t bucketsMask = ~maskMask;
#else
#error Unknown cache mask storage type.
#endif
    
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;

public:
    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();


}

cache_t重要的几个参数和方法"_buckets","_mask","_flags","_occupied","buckets()","occupied",

struct bucket_t {
    // 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

public:
   inline SEL sel() const { return _sel.load(memory_order::memory_order_relaxed); }

    inline IMP imp(Class cls) const {
        //省略
    }
    template <Atomicity, IMPEncoding>
    void set(SEL newSel, IMP newImp, Class cls);
};

bucket_t重要的几个参数和方法"_sel","_imp"," imp(Class cls) ","sel()"

• lldb调试：

@interface HJTeacher : HJPerson
- (void)function_1;
- (void)function_2;
- (void)function_3;
- (void)function_4;

@end

@implementation HJTeacher
- (void)function_1{
}
- (void)function_2{
}
- (void)function_3{
}
- (void)function_4{
}
@end

//i386:macos/模拟器
//x86 :模拟器
//arm64 真机
int main(int argc, const char * argv[]) {
    @autoreleasepool {
        Class pClass  = [HJTeacher class];
        HJTeacher* p = [HJTeacher alloc];
        [p function_1];
        [p function_2];
        [p function_3];
        [p function_4];
        NSLog(@"%@",pClass);
    }
    return 0;
}

• 1. 论证"ISA","superClass"各占8个字节

image.png

• 2. 首地址平移16字节，即可拿到 "cache_t" 数据 , 0x0000000100002410 -> 0x0000000100002420

image.png

此时cache中并没有存储数据

• 3. 断点下移，走完“function_1”方法，接着再次打印cache，发现找到sel
  image.png

解释：p *($10+1) 是根据指针平移的操作，意思是下标+1的操作，也就是数组list的下标+1的操作，其实可以等价于 p $9.bukets()[1]

image.png

!!! 问题思考：为什么function_1 没有存储在[0]号位置，却在1号位置？？？？

!!! 问题思考： mask的值为什么为3，？？？？

!!! 问题思考： occupied的值为什么为1，？？？？

• ``4. 断点下移，走完“function_2”方法，接着再次打印

  
  image.png

function2 在第0号位置，mask依然为3
!!! 问题思考： occupied的值为什么为2，？？？？

• ``5. 断点下移，走完“function_3”方法，接着再次打印

  
  image.png

!!! 问题思考：为什么 function_3 存储在[0]号位置，之前存储的function2 为何却不见了，并且原来在1号位置的function1 也不见了？？？？

!!! 问题思考： mask的值为什么为7？？？？

带着问题看源码

重要源码部分

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.
        printf("");
    }
    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);
}

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);
    }
}

• 流程梳理 (按照每个方法的执行步骤开始疏通流程)

        [p function_1];
        [p function_2];
        [p function_3];
        [p function_4];

• function_1为断点，进入cache的流程

首先判断cache是否为空，第一次的时候进入“reallocate”

if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE; //值为 4
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }

reallocate 方法中，开辟一个“newCapacity”(4)大小内存的newBuckets,并将此赋值给_buckets, ，此时并不进入“cache_collect_free”方法

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    bucket_t *oldBuckets = buckets(); //获取之前存在的buckets，第一次肯定为空

    bucket_t *newBuckets = allocateBuckets(newCapacity);//开辟一个“newCapacity”大小内存的bucket_t

    setBucketsAndMask(newBuckets, newCapacity - 1);//初始化
    if (freeOld) {//当存在老buckets的时候，释放之前的缓存空间
        cache_collect_free(oldBuckets, oldCapacity);
    }
}

setBucketsAndMask 方法 ，初始化buckets，并且将_occupied 归0.

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
}

验证： 将sel和imp存入buckets中的bucket，利用哈希算法计算出存储位置，这也是为什么buckets中的元素位置是错乱的原因，另外可以得到mask的值为 4-1 = 3 ！！！！，并且也验证了 occupied的 值为已经存储的sel的个数

    bucket_t *b = buckets();//获取_buckets
    mask_t m = capacity - 1; //此时为4-1 = 3，
    mask_t begin = cache_hash(sel, m); //哈希算法获取下标
    mask_t i = begin;    
    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));

• function_3为断点，进入cache的流程
进行扩容操作，此时传入的capacity值为8

else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 扩容两倍 4
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);  // 内存 库容完毕
    }

重新进行buckets的内存开辟，开辟的大小为8，并且occupied值重新置为0，并且进入cache_collect_free方法

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);
    }
}

cache_collect_free 方法 ，清除旧的buckets.

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);
}

验证得出：为什么之前的存储的sel都会不在了

总结：

1.occupied的值为buckets中存储的sel的个数
2.mask值为4-1 = 3，8-1 = 7,16-1 = 15 ......
3.当进行扩容的时候，之前的存储的sel都会并清空，所以找不到之前存储的sel
4.存储的顺序是hash哈希算法计算出来的，所以里面存储的位置不是按顺序排列的

Cooci 关于Cache_t原理分析图.png