之前有分析過OC類的底層結(jié)構(gòu)，今天來(lái)重點(diǎn)分析一個(gè)重要的結(jié)構(gòu)體cache_t冈涧；

cache_t結(jié)構(gòu)體分析

首先通過lldb斷點(diǎn)打印我們的cache_t內(nèi)容茂附，之前在分析OC類的底層結(jié)構(gòu)的時(shí)候，有分析過通過內(nèi)存偏移的方式督弓，取出結(jié)構(gòu)體里的變量营曼，這里不再贅述了，直接看結(jié)果：

image.png

打印出來(lái)里面有不少東西咽筋，那具體哪一個(gè)值得我們?cè)敿?xì)探究呢溶推？這里主要是要探究cache_t的結(jié)構(gòu)徊件，與其說是探究它的結(jié)構(gòu)奸攻，不如說cache_t有什么用蒜危，通過它的作用，反推我們想要探究的結(jié)構(gòu)睹耐；

cache的作用辐赞？
答：cache顧名思義，緩存硝训，在一個(gè)類里面响委，緩存能緩存什么呢？屬性是存在對(duì)象里面窖梁，協(xié)議對(duì)應(yīng)protocol赘风，所以這里是緩存我們調(diào)用過的方法；

方法最重要的是消息的主體纵刘，即sel和imp邀窃，即我們要重點(diǎn)探索sel跟imp被保存在哪里；mask假哎、occupied瞬捕、flags這些都是面具符跟標(biāo)志位，所以可能在_bucketsAndMaybeMask或者_(dá)originalPreoptCache中舵抹；

struct cache_t {
private:
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask;
    union {
        // Note: _flags on ARM64 needs to line up with the unused bits of
        // _originalPreoptCache because we access some flags (specifically
        // FAST_CACHE_HAS_DEFAULT_CORE and FAST_CACHE_HAS_DEFAULT_AWZ) on
        // unrealized classes with the assumption that they will start out
        // as 0.
        struct {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED && !__LP64__
            // Outlined cache mask storage, 32-bit, we have mask and occupied.
            explicit_atomic<mask_t>    _mask;
            uint16_t                   _occupied;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED && __LP64__
            // Outlined cache mask storage, 64-bit, we have mask, occupied, flags.
            explicit_atomic<mask_t>    _mask;
            uint16_t                   _occupied;
            uint16_t                   _flags;
#   define CACHE_T_HAS_FLAGS 1
#elif __LP64__
            // Inline cache mask storage, 64-bit, we have occupied, flags, and
            // empty space to line up flags with originalPreoptCache.
            //
            // Note: the assembly code for objc_release_xN knows about the
            // location of _flags and the
            // FAST_CACHE_HAS_CUSTOM_DEALLOC_INITIATION flag within. Any changes
            // must be applied there as well.
            uint32_t                   _unused;
            uint16_t                   _occupied;
            uint16_t                   _flags;
#   define CACHE_T_HAS_FLAGS 1
#else
            // Inline cache mask storage, 32-bit, we have occupied, flags.
            uint16_t                   _occupied;
            uint16_t                   _flags;
#   define CACHE_T_HAS_FLAGS 1
#endif

        };
        explicit_atomic<preopt_cache_t *> _originalPreoptCache;
    };

    // Simple constructor for testing purposes only.
    cache_t() : _bucketsAndMaybeMask(0) {}

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    // _bucketsAndMaybeMask is a buckets_t pointer

    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 >= OBJC_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

    // 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 >= OBJC_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

    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(bool authenticated = true) 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 CACHE_T_HAS_FLAGS
#   if __arm64__
// class or superclass has .cxx_construct/.cxx_destruct implementation
//   FAST_CACHE_HAS_CXX_DTOR is the first bit so that setting it in
//   isa_t::has_cxx_dtor is a single bfi
#       define FAST_CACHE_HAS_CXX_DTOR       (1<<0)
#       define FAST_CACHE_HAS_CXX_CTOR       (1<<1)
// Denormalized RO_META to avoid an indirection
#       define FAST_CACHE_META               (1<<2)
#   else
// Denormalized RO_META to avoid an indirection
#       define FAST_CACHE_META               (1<<0)
// class or superclass has .cxx_construct/.cxx_destruct implementation
//   FAST_CACHE_HAS_CXX_DTOR is chosen to alias with isa_t::has_cxx_dtor
#       define FAST_CACHE_HAS_CXX_CTOR       (1<<1)
#       define FAST_CACHE_HAS_CXX_DTOR       (1<<2)
#endif

// Fast Alloc fields:
//   This stores the word-aligned size of instances + "ALLOC_DELTA16",
//   or 0 if the instance size doesn't fit.
//
//   These bits occupy the same bits than in the instance size, so that
//   the size can be extracted with a simple mask operation.
//
//   FAST_CACHE_ALLOC_MASK16 allows to extract the instance size rounded
//   rounded up to the next 16 byte boundary, which is a fastpath for
//   _objc_rootAllocWithZone()

// The code in fastInstanceSize/setFastInstanceSize is not quite right for
// 32-bit, so we currently only enable this for 64-bit.
#   if __LP64__
#       define FAST_CACHE_ALLOC_MASK         0x0ff8
#       define FAST_CACHE_ALLOC_MASK16       0x0ff0
#       define FAST_CACHE_ALLOC_DELTA16      0x0008
#   endif

#   define FAST_CACHE_HAS_CUSTOM_DEALLOC_INITIATION (1<<12)
// class's instances requires raw isa
#   define FAST_CACHE_REQUIRES_RAW_ISA   (1<<13)
// class or superclass has default alloc/allocWithZone: implementation
// Note this is is stored in the metaclass.
#   define FAST_CACHE_HAS_DEFAULT_AWZ    (1<<14)
// class or superclass has default new/self/class/respondsToSelector/isKindOfClass
#   define FAST_CACHE_HAS_DEFAULT_CORE   (1<<15)

    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
}

直接貼源碼肪虎，從源碼中查看；發(fā)現(xiàn)很多關(guān)于bucket的東西惧蛹，類似setBucketsAndMask扇救、emptyBuckets、allocateBuckets赊淑、emptyBucketsForCapacity爵政，整個(gè)篇章就圍繞bucket進(jìn)行操作，所以剛才說的要分析重點(diǎn)也比較清晰了陶缺，就是_bucketsAndMaybeMask钾挟；

bucket_t

上面提到了，cache_t的重點(diǎn)是bucket_t饱岸，所以點(diǎn)開bucket_t查看其結(jié)構(gòu)體內(nèi)容掺出；
不難發(fā)現(xiàn)，這里面就是我們一直想要尋找的sel苫费、imp汤锨；

bucket_t結(jié)構(gòu)體部分截圖

cache_t結(jié)構(gòu)

嘗試找出bucket_t闲礼，通過lldb直接取值，發(fā)現(xiàn)沒辦法打印Value沒辦法直接打印出來(lái)；

嘗試用lldb找出bucket_t

這個(gè)時(shí)候只能繼續(xù)查看源碼了柬泽，看看有沒有源碼能夠直接獲取bucket_t的慎菲，在cache_t源碼中發(fā)現(xiàn)這么一個(gè)API，直接調(diào)用看看結(jié)果锨并；

struct bucket_t *buckets() const;

確實(shí)是打印出bucket_t對(duì)象了露该，但是沒有清晰明了的顯示我們想要sel跟imp；

image.png

同樣的第煮，查看bucket_t結(jié)構(gòu)體解幼，看看有沒有獲取直接獲取sel跟imp的，功夫不負(fù)有心人了包警，成功在bucket_t中找到了對(duì)應(yīng)的接口撵摆；

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

inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls) const {
        uintptr_t imp = _imp.load(memory_order_relaxed);
        if (!imp) return nil;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
        SEL sel = _sel.load(memory_order_relaxed);
        return (IMP)
            ptrauth_auth_and_resign((const void *)imp,
                                    ptrauth_key_process_dependent_code,
                                    modifierForSEL(base, sel, cls),
                                    ptrauth_key_function_pointer, 0);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
        return (IMP)(imp ^ (uintptr_t)cls);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
        return (IMP)imp;
#else
#error Unknown method cache IMP encoding.
#endif
    }

通過我們找到的sel、imp相關(guān)API可以成功獲取到我們之前調(diào)用的sayHello方法害晦；

API獲取sel台汇、imp

通過index獲取全部的內(nèi)容，這里可以看出bucket_t的存儲(chǔ)是不連續(xù)的篱瞎，然后它又可以通過下標(biāo)進(jìn)行索引苟呐，所以這個(gè)存儲(chǔ)方式是哈希結(jié)構(gòu)的；

打印buckets

接下來(lái)就要探索一下bucket_t底層實(shí)現(xiàn)了;

脫離源碼環(huán)境分析cache_t

將objc_class俐筋、class_data_bits_t牵素、cache_t、bucket_t的成員變量都拷貝出來(lái)澄者，新建新的結(jié)構(gòu)體笆呆，利用強(qiáng)制類型轉(zhuǎn)換的方式，打印出對(duì)應(yīng)的標(biāo)志位及cache._buckets粱挡；

#import <objc/runtime.h>
// https://developer.apple.com/videos/play/wwdc2020/10163/
typedef uint32_t mask_t;

struct yx_bucket_t {
    SEL _sel;
    IMP _imp;
};

// 項(xiàng)目運(yùn)行 調(diào)試
struct yx_cache_t {
    struct yx_bucket_t *_buckets;
    mask_t    _mask;
    uint16_t  _occupied;
    uint16_t  _flags;
};

struct yx_class_data_bits_t {
    uintptr_t bits;
};

// cache_t objc_class
struct yx_objc_class  {
    Class ISA;
    Class superclass;
    struct yx_cache_t cache;             // formerly cache pointer and vtable 16
    struct yx_class_data_bits_t bits;
};



int main(int argc, const char * argv[]) {
    @autoreleasepool {
        LGPerson *p  = [LGPerson alloc];
        Class pClass = p.class;
        [p say1];
//        [p say2];
//        [p say3];
        // 增加緩存 -> cache_t 是否存在插入緩存的方法
        
        struct yx_objc_class *yx_class = (__bridge struct yx_objc_class *)(pClass);
        NSLog(@"%u-%u-%hu",yx_class->cache._mask,yx_class->cache._occupied,yx_class->cache._flags);
        for (int i = 0 ; i < yx_class->cache._mask ; i++){
            struct yx_bucket_t bucket = yx_class->cache._buckets[i];
            NSLog(@"%@-%p - %d",NSStringFromSelector(bucket._sel),bucket._imp,i);
        }
        
        // 插入方法 -> 寫 -> 讀(cache 讀取)

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

_mask是3赠幕，_occupied是1；

say1方法

_mask是3询筏，_occupied變成了2榕堰；

調(diào)用say1、say2方法

調(diào)用say1、say2踱讨、say3方法

這個(gè)_mask跟_occupied是從哪里來(lái)的魏蔗？

cache_t::insert

從cache_t插入方法進(jìn)行分析；
第一步是occupied() + 1痹筛，占用方法加一莺治，這也可以解釋調(diào)用say2的時(shí)候廓鞠，_occupied從1變成2的原因了；
第二步是判斷有沒有能夠插入的對(duì)象谣旁，沒有的話就使用reallocate進(jìn)行開辟能夠插入的對(duì)象空間诫惭；有的話就判斷空間是否足夠，是否需要擴(kuò)容蔓挖；

傳入的capacity = INIT_CACHE_SIZE；INIT_CACHE_SIZE = 1 << 2 = 4;
所以第一次傳入newCapacity = 4馆衔，在reallocate中有個(gè)方法setBucketsAndMask瘟判，newCapacity - 1 = 3；這里也可以解釋為什么我們第一次調(diào)用say1方法的時(shí)候角溃，_mask會(huì)是3了拷获；

第三步就是對(duì)sel跟imp進(jìn)行存儲(chǔ)；

1减细、調(diào)用buckets()創(chuàng)建空桶子匆瓜，調(diào)用cache_hash對(duì)sel跟mask進(jìn)行哈希得到要存儲(chǔ) 位置，對(duì)sel的值進(jìn)行平移操作未蝌，再與上mask驮吱，所以3的空間就是012；
2萧吠、使用do-while循環(huán)判斷buckets桶子里面對(duì)應(yīng)的位置是否有值左冬，沒有值的話就調(diào)用set方法進(jìn)行插入，同時(shí)調(diào)用incrementOccupied讓_occupied++纸型，這里才是真正的_occupied增加的原因拇砰，上面那個(gè)第一步occupied() + 1只是為了判斷當(dāng)前的空間是否達(dá)到需要擴(kuò)容的臨界點(diǎn)而已；如果有值的話狰腌，就再次hash除破，尋找下一個(gè)位置，循環(huán)往復(fù);

問題：mask什么時(shí)候變成的7琼腔？為什么調(diào)用say3方法的時(shí)候瑰枫，say1、say2都不見了丹莲？

• 看一下這個(gè)else方法里面的reallocate傳入的 capacity * 2躁垛，做了兩倍擴(kuò)容，所以當(dāng)我們內(nèi)容一直增加到需要擴(kuò)容的時(shí)候圾笨，第二次_mask就變成了 4 * 2 - 1 = 7教馆；
• 因?yàn)閟etBucketsAndMask中有對(duì)_occupied = 0進(jìn)行重置操作，所以一旦有擴(kuò)容擂达，_occupied就從0開始計(jì)算土铺，所以調(diào)用say3的時(shí)候，_occupied就變成了1；
• 當(dāng)擴(kuò)容的時(shí)候悲敷，傳入的第三個(gè)參數(shù)freeOld = true究恤，
  if (freeOld) {
  collect_free(oldBuckets, oldCapacity);
  }
  這個(gè)時(shí)候，就會(huì)釋放oldBuckets后德，所以調(diào)用say3的時(shí)候部宿，之前存儲(chǔ)的say1、say2就會(huì)不見了瓢湃；

至于蘋果為什么要把原來(lái)的內(nèi)容干掉理张，而不是往后直接增加呢？或者把原來(lái)的內(nèi)容拷貝到現(xiàn)在新空間呢绵患？

• 第一個(gè)就是內(nèi)存初始化的時(shí)候空間大小已經(jīng)定好了雾叭，繼續(xù)往后增加，有可能數(shù)據(jù)可能不連續(xù)落蝙；因?yàn)檫@個(gè)cache_t在類里面织狐，而類的結(jié)構(gòu)在堆內(nèi)存，后面直接加的內(nèi)存不一定連續(xù)筏勒；
• 第二個(gè)就是平時(shí)我們方法調(diào)用是很頻繁的操作移迫，當(dāng)我們需要擴(kuò)容的時(shí)候，每次都要把之前的緩存挨個(gè)平移管行、hash等一系列操作進(jìn)行拷貝起意，這個(gè)時(shí)候就比較費(fèi)時(shí)間了，所以蘋果這里就是利用空間換時(shí)間的處理方式病瞳，直接把前面的抹掉揽咕；

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    lockdebug::assert_locked(&runtimeLock);

    // 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

    ASSERT(sel != 0 && cls()->isInitialized());

    // 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 {
        // 4 * 2 = 8 - 1 = 7
        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
}

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

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    uintptr_t buckets = (uintptr_t)newBuckets;
    uintptr_t mask = (uintptr_t)newMask;

    ASSERT(buckets <= bucketsMask);
    ASSERT(mask <= maxMask);

    _bucketsAndMaybeMask.store(((uintptr_t)newMask << maskShift) | (uintptr_t)newBuckets, memory_order_release);
    _occupied = 0;
}

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
    // 0110 1111 : 11 3 01: 1  10: 2 00: 0
    // 0000 0011 - mask = 3
    return (mask_t)(value & mask);
}

Cache_t原理分析圖.png