前言

在《类的探究分析》一文中详细地分析了类结构的bits成员，但是除此之外cache成员也是非常重要的。那么cache中保存了什么信息？我们验证流程是怎么样的？cache底层代码流程是怎么样子的？那我们下面就进行探索了喔！

类结构回顾

struct objc_class : objc_object {
    //Class ISA;        //isa是隐藏成员 占8字节
    Class superclass;    //占8字节
    cache_t cache;        //占16字节
    class_data_bits_t bits; 
};

cache存在的必要性

在类方法调用的过程中，我们知道是通过方法的SEL（方法编号）在内存中寻找对应的IMP（方法指针），最后找到方法的实现。为了避免每次寻找方法都要循环遍历类的方法列表，使方法响应更加快速，效率更高，cache_t结构体出现了。cache_t将调用过的方法的SEL和IMP以及receiver以bucket_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字节
    };
   //此处省略部分代码
......
   //以下是提供的方法
    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);
  //此处省略部分代码
......

分析：

• _bucketsAndMaybeMask是uintptr_t（无符号长整形）类型的，占内存8字节。里面存放着一个地址。
• union（联合体）中有一个结构体，_originalPreoptCache是结构体指针。
• 结构体中有三个成员变量（_maybeMask、_flags、_occupied），__LP64__指的是Unix（linux）或者macOS系统。
  • _maybeMask：当前的缓存区count，第一次开辟是3。
  • _occupied：当前cache的可存储的buckets数量，默认是0。
• 在union（联合体）中，结构体跟_originalPreoptCache是互斥的。_originalPreoptCache初始时候的缓存。
• cache_t结构体中提供了一些方法去取值，其中buckets()方法就是我们需要的。
  在观察cache_t结构里面的方法时候，最直观的就是insert()方法，参数是SEL和IMP。然后进入insert方法的实现，发现是对buckets的操作，同样我们也在cache_t结构里面找到了buckets()方法，那么我们可以猜测buckets()方法可以拿到一些信息。

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

分析：

• bucket_t结构体中存放着imp（方法指针）和sel（方法编号）。
• 在arm64架构下，先存放imp（方法指针）再存放sel（方法编号）。
• 非arm64架构下，先存放sel（方法编号）再存放imp（方法指针）。
• cache里面存的是方法。

总结

cache结构对应关系

LLDB调试cache

【第一步：创建LGPersion类】

@interface LGPerson : NSObject
@property (nonatomic, copy) NSString *name;
@property (nonatomic) int age;
@property (nonatomic, strong) NSString *hobby;

//创建两个方法
- (void)saySomething;     
- (void)sayNB;
@end

【第二步：lldb调试】
1.在类没有调用任何方法的时候：

lldb调试1.0

lldb调试1.1

lldb调试2.0

lldb调试2.1

lldb调试2.2

lldb调试2.3

lldb调试2.4

lldb调试2.5

lldb调试3.0

lldb调试3.1

lldb调试3.2

lldb调试3.3

lldb调试3.4

lldb调试3.5

总结：

• buckets容器最后一个成员存放着其首地址。
• lldb调用类的方法时候底层会调用class与respondSelecter:方法（查看llvm源码）。
• lldb调用类的方法时候buckets容器会进行扩容。
• buckets不是数组，而是一个哈希链表（无规则存放成员）。
• 哈希链表存在这一个临界容量（3/4）,当超过容器容量的3/4时候会进行扩容，这样子能有效的减少哈希冲突。(这方面cache源码有体现)

cache模拟代码分析

由于lldb调试并不方便且其底层会调用一些方法也会影响我们的判断，那么用代码实现lldb的操作流程能更好的理解cache的结构和流程。

代码模拟

struct xj_cache_t {
    unsigned long _bucketsAndMaybeMask;    //简化了代码，除去联合体互斥的代码以及非arm64架构下的判断代码
    uint32_t _maybeMask;
    uint16_t _flags;
    uint16_t _occupied;
};

struct xj_class_data_bits_t {
    uintptr_t bits;
};

struct xj_objc_class {
    Class ISA;
    Class superclass;
    struct xj_cache_t cache;
    struct xj_class_data_bits_t bits;
};

以上是还原了objc_class的结构，在cache_t结构中，我们除去联合体互斥的代码和部项目判断不会进去的代码！简化得出非arm64架构下的bucket_t结构如下：

//非arm64
struct xj_bucket_t {
    SEL _sel;
    IMP _imp;
};

那么根据以上的代码，我们基本还原了cache的代码。但是_bucketsAndMaybeMask还存在着问题，里面实现了load方法，源码如下：

struct bucket_t *cache_t::buckets() const
{
    uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return (bucket_t *)(addr & bucketsMask);
}

_bucketsAndMaybeMask好明显返回的是bucket_t *类型的，是一个结构体指针，那么我们就可以替换上面xj_cache_t结构体的第一个元素得到：

struct xj_cache_t {
    struct xj_bucket_t *_buckets;   
    uint32_t _maybeMask;
    uint16_t _flags;
    uint16_t _occupied;
};

开始验证

首先往LGPerson类中添加如下的方法：

- (void)say1;
- (void)say2;
- (void)say3;
- (void)say4;
- (void)say5;
- (void)say6;
- (void)say7;
//定义类方法
+ (void)sayHappy; 

然后添加实现代码：

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        LGPerson *p  = [LGPerson alloc];
        Class pClass = p.class;       // objc_clas
       //类中的方法可以尝试性的调用，例如我实现两个，五个方法的时候看看下面的打印情况
        [p say1];
        [p say2];
        [p say3];
        [p say4];
        [p say5];
        [p say6];
        [p say7];
        [LGPerson sayHappy];
        //打印LGPerson类中的cache内容
        struct xj_objc_class *xj_class = (__bridge struct xj_objc_class *)(pClass);
        NSLog(@"occupied:%hu  maybeMask:%u",xj_class->cache._occupied,xj_class->cache._maybeMask);
       //循环打印buckets链表中的成员，并查看成员内容
        for (mask_t i = 0; i<xj_class->cache._maybeMask; i++) {
            struct xj_bucket_t bucket = xj_class->cache._bukets[i];
            NSLog(@"SEL:%@ - IMP:%pf",NSStringFromSelector(bucket._sel),bucket._imp);
        }
   }
return 0 ;
}

各种情况的打印结果：
1.当调用say1方法时，打印如下：

image.png

image.png

image.png

image.png

• _occupied是容器中可用成员的个数。
• _maybeMask表示容器容量的大小（其实是容器容量大小-1，最后一个元素存储的sel -imp为0x1-bucket指针地址）。
• 类方法不存在本类的cache中，而是存到元类的cache中。
• 父类的方法（如：init）也会存到本类的cache中。
• 当_maybeMask值变化的时候，_occupied会重新计数。这也意味着扩容的时候之前的缓存被清空了。

cache_t底层探索

疑点

• 根据上面的分析我们清楚了_occupied与_maybeMask之间的变化关系，但是init方法插入到cache的流程我们还是不清楚的，这就要分析cache_t的源码实现了。
• _bucketsAndMaybeMask是存储着_buckets的首地址（类似于isa），还有maybeMask的相关信息，那么这个需要我们分析源码看看过程。
  那么bucket添加到buckets容器的过程逻辑是需要我们进行分析的，也就是cache_t中的insert方法。

insert

核心源码如下：

    // Never cache before +initialize is done
    if (slowpath(!cls()->isInitialized())) {
        return;
    }
......
//此处省略了一部分代码 
    ASSERT(sel != 0 && cls()->isInitialized());

    // Use the cache as-is if until we exceed our expected fill ratio.
    //对old occupied+1，第一次的话新的occupied = 1；
    mask_t newOccupied = occupied() + 1;
    //旧容量，（mask+1）或者 0
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    //判断是否为空cache，首次进入这里
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        //默认容量为4
        if (!capacity) capacity = INIT_CACHE_SIZE;  // 4
        //0 4，开辟新的缓存空间，false代表是否释放旧的容器空间，这里第一次开辟空间，传false（不需要释放）
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    //newOccupied + 1 (相当于 _occupied + 2) <= capacity * 3 / 4 容量够的时候什么都不做，直接插入。<=75%的容积正常插入，否则扩容。
    //在arm64位的情况下，CACHE_END_MARKER 0 扩容条件为：7 / 8 87.5% 这个时候CACHE_ALLOW_FULL_UTILIZATION 为 1
    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   //在arm64位的情况下进入
    //capacity <= 1<<3 (8), _occupied + 1（CACHE_END_MARKER为0） <= 容量。少于8个元素的时候允许100%占满。
    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 {
        //容量不为空时，返回2倍的容量  否则返回4
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        //MAX_CACHE_SIZE = 1 << 16 = 2^16 = (最大缓存)65532 = 64k
        if (capacity > MAX_CACHE_SIZE) {
            //容量超出最大值就取最大值
            capacity = MAX_CACHE_SIZE;
        }
        //开辟新的容器，释放就的容器空间
        reallocate(oldCapacity, capacity, true);
    }
    //从cahche_t中的_bucketsAndMaybeMask获取buckets,首地址
    bucket_t *b = buckets();
    //首次是4-1 这里也就解释了前面代码调试的时候maybeMask为什么为3,7
    mask_t m = capacity - 1;
    //用sel和mybeMask进行哈希运行得到插入的index
    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 {
        //能走到这里大概率是cache不存在，所以这里走fastpath
        if (fastpath(b[i].sel() == 0)) {
            //occupied+1
            incrementOccupied();
            // buckets链表中插入bucket
            b[i].set<Atomic, Encoded>(b, sel, imp, cls());
            return;
        }
        //如果bucket中的sel已经存在了，就不进行操作。也有可能是其他线程插入的
        if (b[i].sel() == sel) {
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
        }//cahche_next是为了防止hash冲突，然而再hash了一次 ----（i+1）& mask
    } while (fastpath((i = cache_next(i, m)) != begin));
    //异常处理
    bad_cache(receiver, (SEL)sel);
#endif // !DEBUG_TASK_THREADS

步骤：

• 首次进入isConstantEmptyCache分支。会创建一个容量为4的空buckets。这个时候由于旧buckets不存在不需要释放所以参数传递false。
• 当容量大于等于3/4或7/8的情况下扩容。arm64的条件下为7 / 8。
• arm64条件下容量<=8的时候会占用100%才扩容。
• 扩容是直接翻倍，默认值4。最大值MAX_CACHE_SIZE为2^16(65536)。在扩容的时候直接释放了旧值。
• mask值为capacity - 1，这也就是调试的时候输出3、7的原因（因为最后一个元素存储的是buckets的地址，格式为(sel-imp)0x1-buckets address）。
• 通过cache_hash计算插入的index，后面会通过cache_next再进行计算hash解决冲突问题。
• 循环判断通过b[i].set插入bucket数据。
• 插入过程中有异常的就会调用 bad_cache(receiver, (SEL)sel)。

reallocate（开辟新的缓存空间）

核心代码如下：

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
   //获取就得buckets
    bucket_t *oldBuckets = buckets();
   //初始化新的buckets
    bucket_t *newBuckets = allocateBuckets(newCapacity);
   //设置新的buckets和mask  = newBuckets的容量 - 1
   //newBuckets 最后的元素已经在初始化时候有了sel ：0x10 和 imp：buckets首地址
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
//如果之前又buckets，释放旧的buckets
        collect_free(oldBuckets, oldCapacity);
    }
}

• reallocate方法是重新开辟buckets空间。
• 在开辟新的buckets过程中，会释放旧的buckets。因为内存平移很消耗性能。

allocateBuckets（buckets初始化）

核心代码如下：

bucket_t *cache_t::allocateBuckets(mask_t newCapacity)
{
    // Allocate one extra bucket to mark the end of the list.
    //开辟空间
    bucket_t *newBuckets = (bucket_t *)calloc(bytesForCapacity(newCapacity), 1);
    //拿出最后的bucket，进行往下的操作
    bucket_t *end = endMarker(newBuckets, newCapacity);

#if __arm__
    // End marker's sel is 1 and imp points BEFORE the first bucket.
    // This saves an instruction in objc_msgSend.
    end->set<NotAtomic, Raw>(newBuckets, (SEL)(uintptr_t)1, (IMP)(newBuckets - 1), nil);
#else
    // End marker's sel is 1 and imp points to the first bucket.
    //新buckets的最后一个元素存储的是自身的指针地址。格式为sel-imp（0x1-buckets address）
    end->set<NotAtomic, Raw>(newBuckets, (SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    
    if (PrintCaches) recordNewCache(newCapacity);

    return newBuckets;
}

• calloc方法是开辟buckets的空间。
• 在buckets的最后的一个成员里面存放着SEL：0x1和IMP：bucket address。

setBucketsAndMask

核心代码如下：

//方法中用到相关的宏定义以及架构的判定
#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__
#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

//具体方法的实现
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
#ifdef __arm__
    // ensure other threads see buckets contents before buckets pointer
    mega_barrier();

    _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_relaxed);

    // ensure other threads see new buckets before new mask
    //内存屏障
    mega_barrier();

    _maybeMask.store(newMask, memory_order_relaxed);
    _occupied = 0;
#elif __x86_64__ || i386
    //_bucketsAndMaybeMask 存储buckets，这里进行了强转。_bucketsAndMaybeMask只存储buckets的指针。
    _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_release);

    // ensure other threads see new buckets before new mask
    //_maybeMask存储newCapacity-1
    _maybeMask.store(newMask, memory_order_release);
    //元素值赋值为0，由于是新桶。
    _occupied = 0;
#else
#error Don't know how to do setBucketsAndMask on this architecture.
#endif
}
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 || CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
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_relaxed);
    _occupied = 0;
}
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    uintptr_t buckets = (uintptr_t)newBuckets;
    unsigned mask = (unsigned)newMask;

    ASSERT(buckets == (buckets & bucketsMask));
    ASSERT(mask <= 0xffff);

    _bucketsAndMaybeMask.store(buckets | objc::mask16ShiftBits(mask), memory_order_relaxed);
    _occupied = 0;

    ASSERT(this->buckets() == newBuckets);
    ASSERT(this->mask() == newMask);
}
#else
#error Unknown cache mask storage type.
#endif

CACHE_MASK_STORAGE对应的值：

• arm64 64位运行设备
  • OSX/SIMULATOR：CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS（4）
  • 真机（手机，pad等）：CACHE_MASK_STORAGE_HIGH_16(2)
• arm64 32位设备：CACHE_MASK_STORAGE_LOW_4(3)
• x86_64/i386/arm：CACHE_MASK_STORAGE_OUTLINED(1)

CACHE_MASK_STORAGE_OUTLINED流程：

• 强转newBuckets为地址存储在_bucketsAndMaybeMask中，这也是为什么前面代码验证的时候能直接用buckets接收这个数据的原因（只存buckets地址）。
  -_maybeMask存储的值为capacity-1（容量-1，最后一个存储的是自身的地址）。

CACHE_MASK_STORAGE_HIGH_16 或 CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS (真机上)流程：

• mask与buckets都存储在_bucketsAndMaybeMask中，mask << maskShift | newBuckets。
• 此时maskShift为48/44也就是mask存储在高16/20位，buckets存储在低48/44位。（mac以及模拟器maskShift是48，其它为44）。

CACHE_MASK_STORAGE_LOW_4 arm64指令32位设备流程：

• mask与buckets都存储在_bucketsAndMaybeMask中，buckets | objc::mask16ShiftBits(mask)。
• buckets存储在高60位，mask存储在低4位，mask16ShiftBits的具体逻辑会在后面分析（其实存储的不是mask，而是mask前置的0）。

注意：在扩容的时候_occupied = 0。其实这也相当于开辟新的空间，旧空间的_occupied不会累加在新的空间中，且_occupied不包括最后一个元素bucket。

cache_fill_ratio

核心代码如下：

#if __arm__  ||  __x86_64__  ||  __i386__

#define CACHE_END_MARKER 1

static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 3 / 4;
}

#elif __arm64__ && !__LP64__

#define CACHE_END_MARKER 0

static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 3 / 4;
}

#elif __arm64__ && __LP64__

#define CACHE_END_MARKER 0

static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 7 / 8;
}
#define CACHE_ALLOW_FULL_UTILIZATION 1

#else
#error unknown architecture
#endif

• 不同架构下容量算法有差异,__arm64__ && __LP64__（arm64架构）下，buckets会在使用到7/8（87.5%）时候进行扩容，其他架构都是3/4（75%）就进行扩容。
• 因为涉及到负载因子，为了有效得避免hash冲突，而且在3/4和7/8空间利用率最高，所以在此进行扩容比较好。

cache_hash和cache_next

核心代码如下：

#if defined(__arm64__) && TARGET_OS_IOS && !TARGET_OS_SIMULATOR && !TARGET_OS_MACCATALYST
#define CONFIG_USE_PREOPT_CACHES 1
#else
#define CONFIG_USE_PREOPT_CACHES 0
#endif

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    uintptr_t value = (uintptr_t)sel;
#if CONFIG_USE_PREOPT_CACHES    
    //arm64架构下 
    value ^= value >> 7;
#endif   
    return (mask_t)(value & mask);   //返回sel&mask作为index
}


#if CACHE_END_MARKER
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;     //index +1 & mask 
}
#elif __arm64__
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;   //在平移寻找插入位置的时候，如果index不等于0，那么index-1向前着，否则index = mask，移到最后
}
#else
#error unexpected configuration
#endif

• CONFIG_USE_PREOPT_CACHES表示arm64指令并且非iOS模拟器非MACCATALYST，也就是arm64指令真机。
• cache_next在intel mac以及arm 32的情况是向后(+)插入，在 arm64的情况下是向前(-)插入。
  • (i+1) & mask的逻辑是向后(+)插入，会进行二次&mask。
  • i ? i-1 : mask冲突的时候向前(-)，直接没有二次hash。当i为0时会返回mask相当于到倒数第二个元素的地址(倒数第一个位0x1-buckets address)。

_bucketsAndMaybeMask分析

由上面的代码分析到_bucketsAndMaybeMask保存着buckets和maybeMask，那么他们是怎么计算得来的呢？那么我么就要分析buckets()方法与mask()方法了。请继续往下看！

buckets()

核心代码如下：

struct bucket_t *cache_t::buckets() const
{
    //_bucketsAndMaybeMask调用了load方法
    uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
    //上面拿到的地址&bucketsMask（类似掩码），转化成bucket_t *类型的结构体指针并返回给外面
    return (bucket_t *)(addr & bucketsMask);
}

bucketsMask是多少？不同架构估计不一样吧？（类似于isa的掩码）

bucketsMask的核心代码：

/intel芯片
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    static constexpr uintptr_t bucketsMask = ~0ul;//全1

//arm64 64位OSX`/`SIMULATOR`
#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;//1<<15（低15位是0）
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << maskShift) - 1;   //(1<<48) - 1(低48位都是1)

 //`arm64真机`
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    static constexpr uintptr_t maskShift = 48;
    static constexpr uintptr_t maskZeroBits = 4;

    // The largest mask value we can store.
    static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;//1<<15(低15位0)
    
    // The mask applied to `_maskAndBuckets` to retrieve the buckets pointer.
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1; //(1 << 44)-1（低44位1）

//arm64 32 位
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4

    static constexpr uintptr_t maskBits = 4;
    static constexpr uintptr_t maskMask = (1 << maskBits) - 1;// (1<<4) -1（低4位1）
    static constexpr uintptr_t bucketsMask = ~maskMask; // ~((1<<4) -1)（低4位为0，其余全为1）
#endif
#end

• intel/arm：直接存储的就是buckets地址，64/32位存储buckets。
• arm64指令 64位OSX/SIMULATOR：(1<<48) - 1，低48位存储buckets。
• arm64指令64 位真机（除了mac以及模拟器）：(1 << 44)-1，低44位存储buckets。
• arm64指令 32位： ~((1<<4) -1)：高60位存储buckets。

mask()

核心代码如下：(简化了一些不必要的代码)

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED   //intel芯片
//调用了setBucketsAndMask方法
mask_t cache_t::mask() const
{
    return _maybeMask.load(memory_order_relaxed);
}
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 || CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS     //arm64架的64位设备
//调用了setBucketsAndMask方法
mask_t cache_t::mask() const
{
    uintptr_t maskAndBuckets = _bucketsAndMaybeMask.load(memory_order_relaxed);
//maskShift 为48,
    return maskAndBuckets >> maskShift;
}
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4   //arm64架的32位设备
//调用了setBucketsAndMask方法
mask_t cache_t::mask() const
{
    uintptr_t maskAndBuckets = _bucketsAndMaybeMask.load(memory_order_relaxed);
   //maskMask =  (1<<4) -1（低4位1）
    uintptr_t maskShift = (maskAndBuckets & maskMask);//保留后4位。
//0xffff >> maskShift 获取mask值。
    return 0xffff >> maskShift;
}

• intel/arm：需要直接从_maybeMask字段读取。
• arm64 64位OSX/SIMULATOR：maskAndBuckets >> maskShift，取高16位。
• arm64 64位真机：maskAndBuckets >> maskShift，取高16位。
• arm64 32位：0xffff >> maskShift，取低4位存储的mask的值。

验证CACHE_MASK_STORAGE_LOW_4下mask的获取

结合存储的时候逻辑来看，在存储的时候调用了objc::mask16ShiftBits(mask)：

tatic inline uintptr_t mask16ShiftBits(uint16_t mask)
{
    // returns by how much 0xffff must be shifted "right" to return mask
    uintptr_t maskShift = __builtin_clz(mask) - 16;  //拿出16位前置0的
    ASSERT((0xffff >> maskShift) == mask);
    return maskShift;
}

__builtin_clz()方法返回的是32位中最高位1之前0的个数(前置0的个数)，一下进行验证：

__builtin_clz验证

• __builtin_clz(mask) - 16减16也就意味着要计算在16位下有多少前置位为0，这里不会为负数。因为在上面分析中已经说了buckets扩容的时候最大值为2^16。
• objc::mask16ShiftBits(mask)存储的就是16位下mask的前置的0的个数。
  那么可以推导出：0xffff >> maskShift也就是0xffff >> 前置的0的值 这样就恢复了mask（3/7/15）。非常牛逼的算法哦！！！！！
  参考：_builtin

总结mask与buckets的分布

mask与buckets的分布

补充：为什么imp()需要参数cls

首先我们要继续查看源码，看看imp赋值的方法里面cls的作用是什么。
核心源码如下：

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
    }

    template <Atomicity, IMPEncoding>
    void set(bucket_t *base, SEL newSel, IMP newImp, Class cls);
};

//查看set方法的源码
template<Atomicity atomicity, IMPEncoding impEncoding>
void bucket_t::set(bucket_t *base, SEL newSel, IMP newImp, Class cls)
{
    ASSERT(_sel.load(memory_order_relaxed) == 0 ||
           _sel.load(memory_order_relaxed) == newSel);

    static_assert(offsetof(bucket_t,_imp) == 0 &&
                  offsetof(bucket_t,_sel) == sizeof(void *),
                  "bucket_t layout doesn't match arm64 bucket_t::set()");

    uintptr_t encodedImp = (impEncoding == Encoded
                            ? encodeImp(base, newImp, newSel, cls)
                            : (uintptr_t)newImp);

    // LDP/STP guarantees that all observers get
    // either imp/sel or newImp/newSel
    stp(encodedImp, (uintptr_t)newSel, this);
}

#else

template<Atomicity atomicity, IMPEncoding impEncoding>
void bucket_t::set(bucket_t *base, SEL newSel, IMP newImp, Class cls)
{
    ASSERT(_sel.load(memory_order_relaxed) == 0 ||
           _sel.load(memory_order_relaxed) == newSel);

    
    uintptr_t newIMP = (impEncoding == Encoded
                        ? encodeImp(base, newImp, newSel, cls)
                        : (uintptr_t)newImp);

    if (atomicity == Atomic) {
        _imp.store(newIMP, memory_order_relaxed);
        
        if (_sel.load(memory_order_relaxed) != newSel) {
#ifdef __arm__
            mega_barrier();
            _sel.store(newSel, memory_order_relaxed);
#elif __x86_64__ || __i386__
            _sel.store(newSel, memory_order_release);
#else
#error Don't know how to do bucket_t::set on this architecture.
#endif
        }
    } else {
        _imp.store(newIMP, memory_order_relaxed);
        _sel.store(newSel, memory_order_relaxed);
    }
}

//查看encodedImp方法源码如下
    uintptr_t encodeImp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, IMP newImp, UNUSED_WITHOUT_PTRAUTH SEL newSel, Class cls) const {
        if (!newImp) return 0;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
        return (uintptr_t)
            ptrauth_auth_and_resign(newImp,
                                    ptrauth_key_function_pointer, 0,
                                    ptrauth_key_process_dependent_code,
                                    modifierForSEL(base, newSel, cls));
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
        return (uintptr_t)newImp ^ (uintptr_t)cls;
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
        return (uintptr_t)newImp;
#else
#error Unknown method cache IMP encoding.
#endif

得出结论：bucket_t::set的时候会判断是否需要mpEncoding，如果需要会进行(uintptr_t)newImp ^ (uintptr_t)cls，所以在读取imp的时候需要传参数cls进行还原。相当于(uintptr_t)cls^imp^(uintptr_t)cls = imp。那么就说明buckets中存储的imp不一定是真实的imp，有可能是经过编码的。

cache原理详图

cache原理详图

总结：这篇文章花了我三天的时间去总结，需要得到就必须要花心思去思考去探索。希望我们学习过程中看到的不是上帝视角，而是看到自己一步一步的走向上帝的过程。之后的文章会根据这篇文章进行拓展，然后会发现知识是连贯的，不说了我开始总结下一篇文章去了哦！💪🏻！~~