OC底层原理05-cache_t探索-一一网

类结构

在OC底层原理04-类结构分析中，类主要是下列组成：isa，superclass，cache，bits。

本文只探究cache_t。

cache_t探索

cache_t源码

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 CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    // _bucketsAndMaybeMask is a buckets_t pointer
    // _maybeMask is the buckets mask

    static constexpr uintptr_t bucketsMask = ~0ul;
    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 is a buckets_t pointer in the low 48 bits
    // _maybeMask is unused, the mask is stored in the top 16 bits.

    // 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.
    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
#error Unknown cache mask storage type.
#endif

    bool isConstantEmptyCache() const;
    bool canBeFreed() const;
    mask_t mask() const;

#if CONFIG_USE_PREOPT_CACHES
    void initializeToPreoptCacheInDisguise(const preopt_cache_t *cache);
    const preopt_cache_t *disguised_preopt_cache() const;
#endif

    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);

    void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld);
    void collect_free(bucket_t *oldBuckets, mask_t oldCapacity);

    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);
    void bad_cache(id receiver, SEL sel) __attribute__((noreturn, cold));

public:
    // The following four fields are public for objcdt's use only.
    // objcdt reaches into fields while the process is suspended
    // hence doesn't care for locks and pesky little details like this
    // and can safely use these.
    unsigned capacity() const;
    struct bucket_t *buckets() const;
    Class cls() const;

#if CONFIG_USE_PREOPT_CACHES
    const preopt_cache_t *preopt_cache() const;
#endif

    mask_t occupied() const;
    void initializeToEmpty();

#if CONFIG_USE_PREOPT_CACHES
    bool isConstantOptimizedCache(bool strict = false, uintptr_t empty_addr = (uintptr_t)&_objc_empty_cache) const;
    bool shouldFlush(SEL sel, IMP imp) const;
    bool isConstantOptimizedCacheWithInlinedSels() const;
    Class preoptFallbackClass() const;
    void maybeConvertToPreoptimized();
    void initializeToEmptyOrPreoptimizedInDisguise();
#else
    inline bool isConstantOptimizedCache(bool strict = false, uintptr_t empty_addr = 0) const { return false; }
    inline bool shouldFlush(SEL sel, IMP imp) const {
        return cache_getImp(cls(), sel) == imp;
    }
    inline bool isConstantOptimizedCacheWithInlinedSels() const { return false; }
    inline void initializeToEmptyOrPreoptimizedInDisguise() { initializeToEmpty(); }
#endif

    void insert(SEL sel, IMP imp, id receiver);
    void copyCacheNolock(objc_imp_cache_entry *buffer, int len);
    void destroy();
    void eraseNolock(const char *func);

    static void init();
    static void collectNolock(bool collectALot);
    static size_t bytesForCapacity(uint32_t cap);

#if __LP64__
    bool getBit(uint16_t flags) const {
        return _flags & flags;
    }
    void setBit(uint16_t set) {
        __c11_atomic_fetch_or((_Atomic(uint16_t) *)&_flags, set, __ATOMIC_RELAXED);
    }
    void clearBit(uint16_t clear) {
        __c11_atomic_fetch_and((_Atomic(uint16_t) *)&_flags, ~clear, __ATOMIC_RELAXED);
    }
#endif

#if FAST_CACHE_ALLOC_MASK
    bool hasFastInstanceSize(size_t extra) const
    {
        if (__builtin_constant_p(extra) && extra == 0) {
            return _flags & FAST_CACHE_ALLOC_MASK16;
        }
        return _flags & FAST_CACHE_ALLOC_MASK;
    }

    size_t fastInstanceSize(size_t extra) const
    {
        ASSERT(hasFastInstanceSize(extra));

        if (__builtin_constant_p(extra) && extra == 0) {
            return _flags & FAST_CACHE_ALLOC_MASK16;
        } else {
            size_t size = _flags & FAST_CACHE_ALLOC_MASK;
            // remove the FAST_CACHE_ALLOC_DELTA16 that was added
            // by setFastInstanceSize
            return align16(size + extra - FAST_CACHE_ALLOC_DELTA16);
        }
    }

    void setFastInstanceSize(size_t newSize)
    {
        // Set during realization or construction only. No locking needed.
        uint16_t newBits = _flags & ~FAST_CACHE_ALLOC_MASK;
        uint16_t sizeBits;

        // Adding FAST_CACHE_ALLOC_DELTA16 allows for FAST_CACHE_ALLOC_MASK16
        // to yield the proper 16byte aligned allocation size with a single mask
        sizeBits = word_align(newSize) + FAST_CACHE_ALLOC_DELTA16;
        sizeBits &= FAST_CACHE_ALLOC_MASK;
        if (newSize <= sizeBits) {
            newBits |= sizeBits;
        }
        _flags = newBits;
    }
#else
    bool hasFastInstanceSize(size_t extra) const {
        return false;
    }
    size_t fastInstanceSize(size_t extra) const {
        abort();
    }
    void setFastInstanceSize(size_t extra) {
        // nothing
    }
#endif
};
复制代码

区分宏CACHE_MASK_STORAGE：
#define CACHE_MASK_STORAGE_OUTLINED 1
#define CACHE_MASK_STORAGE_HIGH_16 2
#define CACHE_MASK_STORAGE_LOW_4 3
#define CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS 4

#if defined(__arm64__) && __LP64__ //真机&&64位
 #if TARGET_OS_OSX || TARGET_OS_SIMULATOR
 #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
 #else
 #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16
 #endif
#elif defined(__arm64__) && !__LP64__
 #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_LOW_4
#else
 #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_OUTLINED
#endif
复制代码
模拟器32位处理器测试需要i386架构（iphone5,iphone5s以下的模拟器;
模拟器64位处理器测试需要x86_64架构 (iphone6以上的模拟器);
真机64位处理器需要arm64架构 (iphone6,iphone6p以上的真机);
macOSX需要i386架构;
真机32位处理器需要armv7架构（iphone4真机/armv7）;
真机32位处理器需要armv7s架构（ ipnone5,iphone5s真机/armv7s）.

下面通过真机64位处理器架构 即CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16来分析cache_t源码。

explicit_atomic只是把范型做了原子性安全的封装.例如explicit_atomic<uintptr_t> _bucketsAndMaybeMask; 其实就是uintptr_t _bucketsAndMaybeMask;

由cache_t源码可看到cache_t主要由_buckets，_mask，_flags，_occupied，结构如下：

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

public:
    inline SEL sel() const { return _sel.load(memory_order_relaxed); }
    inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls) const {
...
    }
}
复制代码

bucket_t里放了sel和imp，结构如下：

2种cache探索方式

示例代码：

//LGPerson.h
@property (nonatomic, copy) NSString *nickName;
@property (nonatomic, strong) NSString *name;

- (void)lgPersonInstanceMethod1;
- (void)lgPersonInstanceMethod2;
- (void)lgPersonInstanceMethod3;
- (void)lgPersonInstanceMethod4;
- (void)lgPersonInstanceMethod5;
+ (void)lgPersonClassMethod;

//LGPerson.m
- (void)lgPersonInstanceMethod1{
    NSLog(@"lgPersonInstanceMethod1");
}
- (void)lgPersonInstanceMethod2{
    NSLog(@"lgPersonInstanceMethod2");
}
- (void)lgPersonInstanceMethod3{
    NSLog(@"lgPersonInstanceMethod3");
}
- (void)lgPersonInstanceMethod4{
    NSLog(@"lgPersonInstanceMethod4");
}
- (void)lgPersonInstanceMethod5{
    NSLog(@"lgPersonInstanceMethod5");
}
+ (void)lgPersonClassMethod{
    NSLog(@"LGPerson Class Method");
}


//main.m 调用
LGPerson *person = [LGPerson alloc];
Class pClass = [person class];
//        person.nickName = @"nick";
[person lgPersonInstanceMethod1];
复制代码

cache探索 – 方式1 通过源码环境`lldb`打印

这个是不是那个方法可以通过MachOView验证：

多个方法时候，断点走完第二个类方法时候，应该会缓存2个方法
因为buckets是集合类型所以可以通过下面2种方式打印出其他的方法：
通过 指针偏移 ：

或者通过数组偏移方式 打印:

cache探索 – 方式2 脱离objc源码环境探索校验

把源码环境关键代码拷贝到main文件。

typedef uint32_t mask_t;  // x86_64 & arm64 asm are less efficient with 16-bits

struct lg_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct lg_cache_t {
    struct lg_bucket_t * _buckets;
    mask_t _mask;
    uint16_t _flags;
    uint16_t _occupied;
};

struct lg_class_data_bits_t {
    uintptr_t bits;
};

struct lg_objc_class {
    Class ISA;
    Class superclass;
    struct lg_cache_t cache;             // formerly cache pointer and vtable
    struct lg_class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
};

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        LGPerson *p  = [LGPerson alloc];
        Class pClass = [LGPerson class];  // objc_clas
        [p say1];
        [p say2];
        //[p say3];
        //[p say4];

        struct lg_objc_class *lg_pClass = (__bridge struct lg_objc_class *)(pClass);
        NSLog(@"%hu - %u",lg_pClass->cache._occupied,lg_pClass->cache._mask);
        for (mask_t i = 0; i<lg_pClass->cache._mask; i++) {
            // 打印获取的 bucket
            struct lg_bucket_t bucket = lg_pClass->cache._buckets[i];
            NSLog(@"%@ - %p",NSStringFromSelector(bucket._sel),bucket._imp);
        }

        
        NSLog(@"Hello, World!");
    }
    return 0;
}

//LGPerson.h
@property (nonatomic, copy) NSString *lgName;
@property (nonatomic, strong) NSString *nickName;

- (void)say1;
- (void)say2;
- (void)say3;
- (void)say4;
- (void)say5;
- (void)say6;
- (void)say7;

+ (void)sayHappy;

//LGPerson.m
- (void)say1{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say2{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say3{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say4{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say5{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say6{
    NSLog(@"LGPerson say : %s",__func__);
}
- (void)say7{
    NSLog(@"LGPerson say : %s",__func__);
}
+ (void)sayHappy{
    NSLog(@"LGPerson say : %s",__func__);
}
复制代码

打印如下：
当注释掉[p say3]; [p say4];打印如下：

打开注释，打印如下：

发现下面几个问题：

_occupied和_mask是什么
随着方法增多，_occupied和_mask会变化 2-3 -> 2-7
为什么打印的cache._buckets的bucket中数据会有丢失，例如2-7中，只有say3、say4方法有函数指针
打印的cache._buckets里的方法顺序有点问题例如2-7中say3、say4的打印顺序为什么是say4先打印，say3后打印

下面探究下为什么会这样。

cache_t底层原理分析

线索：首先，从cache_t中的_mask属性开始分析，找cache_t中引起变化的函数，发现了incrementOccupied()函数.

`incrementOccupied()`函数

该函数的具体实现为：

void incrementOccupied(); //Occupied自增

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

搜索下源码中哪里调用此方法：
全局搜索incrementOccupied()函数，发现只在cache_t的insert方法有调用:

`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;
    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 <= 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;
    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 {
        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(receiver, (SEL)sel);
#endif // !DEBUG_TASK_THREADS
}
复制代码

insert方法，理解为cache_t的插入，而cache中存储的就是sel-imp，所以cache的原理从insert方法开始分析.

主要分为以下几个部分：

【第一步】计算出当前的缓存占用量
【第二步】根据缓存占用量判断执行的操作
【第三步】针对需要存储的bucket进行内部imp和sel赋值

第一步，根据`occupied`的值计算出当前的缓存占用量

其中，第一步，根据occupied的值计算出当前的缓存占用量，当属性未赋值及无方法调用时，此时的occupied()为0，而newOccupied为1，如下所示：

mask_t newOccupied = occupied() + 1;
复制代码

关于缓存占用量的计算，有以下几点说明：

alloc申请空间时，此时的对象已经创建，如果再调用init方法，occupied也会+1
当有属性赋值时，会隐式调用set方法，occupied也会增加，即有几个属性赋值，occupied就会在原有的基础上加几个
当有方法调用时，occupied也会增加，即有几次调用，occupied就会在原有的基础上加几个

第二步根据缓存占用量判断执行的操作

如果是第一次创建，则默认开辟4个容量

if (slowpath(isConstantEmptyCache())) { //小概率发生的 即当 occupied() = 0时，即创建缓存，创建属于小概率事件
    // Cache is read-only. Replace it.
    if (!capacity) capacity = INIT_CACHE_SIZE; //初始化时，分配capacity = 4（1<<2 -- 100）个容量 
    reallocate(oldCapacity, capacity, /* freeOld */false); //开辟空间
    //到目前为止，if的流程的操作都是初始化创建
}
复制代码

如果缓存占用量小于等于3/4，则不作任何处理

else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) { 
    // Cache is less than 3/4 full. Use it as-is.
}
复制代码

如果缓存占用量超过3/4，则需要进行两倍扩容以及重新开辟空间

else {//如果超出了3/4，则需要扩容（两倍扩容）
    //扩容算法： 有`capacity`时，扩容两倍，没有`capacity`就初始化为4
    capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 扩容两倍 2*4 = 8
    if (capacity > MAX_CACHE_SIZE) {
        capacity = MAX_CACHE_SIZE;
    }
    // 走到这里表示 曾经有，但是已经满了，需要重新梳理
    reallocate(oldCapacity, capacity, true);
    // 内存 扩容完毕
}
复制代码

我们发现，当第一次创建以及缓存占用量超过3/4，则需要进行两倍扩容以及重新开辟空间时，都会调用reallocate方法，下面看下reallocate方法。

`reallocate`开辟空间方法

主要步骤源码如下：

步骤1 `allocateBuckets`方法

allocateBuckets方法向系统申请开辟内存，即开辟bucket，此时的bucket只是一个临时变量。

步骤2 `setBucketsAndMask`方法

setBucketsAndMask方法：将临时的bucket存入缓存中。

步骤3 `cache_collect_free`方法

如果有旧的buckets，需要清理之前的缓存，即调用cache_collect_free方法，其源码实现如下：

该方法主要有以下几个步骤：

_garbage_make_room方法：创建垃圾回收空间
- 如果是第一次，需要分配回收空间
- 如果不是第一次，则将内存段加大，即原有内存*2
- 记录存储这次的bucket
garbage_refs[garbage_count++] = data;将sel-imp存储在后置的位置
cache_collect方法：垃圾回收，清理旧的bucket

第三步针对需要存储的bucket进行内部imp和sel赋值

    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.
    do {
        if (fastpath(b[i].sel() == 0)) {//未存储sel
            incrementOccupied();//将occupied占用大小加1
            b[i].set<Atomic, Encoded>(b, sel, imp, cls());//将sel-imp存储进去
            return;
        }
        if (b[i].sel() == sel) {//当前哈希下标存储的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_hash方法，即哈希算法 ，计算sel-imp存储的哈希下标。
当前哈希下标存储的sel 不等于 即将插入的sel，则重新经过cache_next方法即哈希冲突算法，重新进行哈希计算，得到新的下标，再去对比进行存储。

如果哈希下标的位置未存储sel，即该下标位置获取sel等于0，此时将sel-imp存储进去，并将occupied占用大小加1；
如果当前哈希下标存储的sel 等于 即将插入的sel，则直接返回。

其中涉及的两种哈希算法，其源码如下：

cache_hash：哈希算法

    static inline mask_t cache_hash(SEL sel, mask_t mask) 
    {
        return (mask_t)(uintptr_t)sel & mask; // 通过sel & mask（mask = cap -1）
    }
复制代码

cache_next：哈希冲突算法

#if __arm__  ||  __x86_64__  ||  __i386__
// objc_msgSend has few registers available.
// Cache scan increments and wraps at special end-marking bucket.
#define CACHE_END_MARKER 1
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask; //（将当前的哈希下标 +1） & mask，重新进行哈希计算，得到一个新的下标
}

#elif __arm64__
// objc_msgSend has lots of registers available.
// Cache scan decrements. No end marker needed.
#define CACHE_END_MARKER 0
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask; //如果i是空，则为mask，mask = cap -1，如果不为空，则 i-1，向前插入sel-imp
}
复制代码

到此，cache_t的原理基本分析完成了，然后前文提及的几个问题，我们现在就有答案了。

问题解答

_occupied和_mask是什么
- _mask是什么
  - _mask是指掩码数据，用于在哈希算法或者哈希冲突算法中计算哈希下标，其中mask 等于capacity - 1。
- _occupied是什么
  - _occupied表示哈希表中 sel-imp 的占用大小 (即可以理解为分配的内存中已经存储了sel-imp的的个数)
  - 方法调用，导致occupied变化
  - init会导致_occupied变化因为init也是对象方法
  - 属性赋值和获取，也会隐式调用，导致_occupied变化
- 缓存的最大数量是 2的15次方， _maskAndBuckets中低48位是 buckets的地址，高16位是 mask， cache_t是利用散列表进行存储，采用的线性探测来解决hash冲突的
随着方法增多，_occupied和_mask会变化 2-3 -> 2-7
- 因为在cache初始化时，分配的空间是4个，随着方法调用的增多，当存储的sel-imp个数，即newOccupied + CACHE_END_MARKER（等于1）的和超过总容量的3/4,例如有4个时，当_occupied等于2时，就需要对cache的内存进行两倍扩容。
为什么打印的cache._buckets的bucket中数据会有丢失，例如2-7中，只有say3、say4方法有函数指针
- 原因是在扩容时，是将原有的内存全部清除了，再重新申请了内存导致的。
打印的cache._buckets里的方法顺序有点问题例如2-7中say3、say4的打印顺序为什么是say4先打印，say3后打印
- 因为sel-imp的存储是通过哈希算法计算下标的，其计算的下标有可能已经存储了sel，所以又需要通过哈希冲突算法重新计算哈希下标，所以导致下标是随机的，并不是固定的。

`cache_fill`方法

全局搜索insert(方法，发现只有cache_fill方法中的调用符合。

全局搜索cache_fill，发现在写入之前，还有一步操作，即cache读取，即查找sel-imp，如下所示：

关于objc_msgSend会在下篇文章分析。
cache分析流程图如下：

本文的重点是分析cache存储的原理–cache_t写入的流程，即insert方法。