前面两篇文章中分析了类的bits，其实还有一个重要的字段cache（cache_t）。这篇文章将详细分析cache的结构以及原理。

一、cache 数据结构

HPObject *obj = [HPObject alloc];
Class objClass = [HPObject class];

1.1 cache_t 分析定位数据

首先根据源码明确objc_class：

struct objc_class : objc_object {
    Class ISA;//继承
    Class superclass;
    cache_t cache;   
    class_data_bits_t bits; 
};

以及cache_t：

struct cache_t {
private:
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask; //unsigned long 8字节
    union {
        struct {
            explicit_atomic<mask_t>    _maybeMask;//uint32_t 4字节
#if __LP64__
            uint16_t                   _flags;//2字节
#endif
            uint16_t                   _occupied;//2字节
        };
        explicit_atomic<preopt_cache_t *> _originalPreoptCache;//指针 8字节
    };
};

LLDB验证:

(lldb) p/x [HPObject class]
(Class) $0 = 0x00000001000083c8 HPObject
(lldb) p (cache_t *)0x00000001000083D8
(cache_t *) $1 = 0x00000001000083d8
(lldb) p *$1
(cache_t) $2 = {
  _bucketsAndMaybeMask = {
    std::__1::atomic<unsigned long> = {
      Value = 4298437472
    }
  }
   = {
     = {
      _maybeMask = {
        std::__1::atomic<unsigned int> = {
          Value = 0
        }
      }
      _flags = 32820
      _occupied = 0
    }
    _originalPreoptCache = {
      std::__1::atomic<preopt_cache_t *> = {
        Value = 0x0000803400000000
      }
    }
  }
}

• 获取类地址后平移0x10得到了cache的指针。
• 打印cache结构与源码中看到的相同。

根据源码_originalPreoptCache与内部结构体是同一份数据，那么缓存数据是保存在_bucketsAndMaybeMask中呢？还是_originalPreoptCache中呢？sel和imp在哪块呢？

官方在这块并没有给注释，但是有个思路。既然是缓存那就应该有增删改查相应的操作。直接在cache_t中查找对应的方法会找到bucket_t相关的方法：

static bucket_t *emptyBuckets();
static bucket_t *allocateBuckets(mask_t newCapacity);
static bucket_t *emptyBucketsForCapacity(mask_t capacity, bool allocate = true);

并且还有一个insert方法：

void insert(SEL sel, IMP imp, id receiver);

insert内部也是对bucket的操作。显然缓存应该与bucket(_bucketsAndMaybeMask）有关。

1.2 bucket_t

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

发现了imp与sel，果然方法与bucket_t有关。
那么就有了如下结构对应关系：

cache_t结构

• arm64下bucket_t中_sel与_imp顺序不同。注释也说了顺序与架构有关，arm64e下imp在前更好，估计是有优化。

二、cache底层LLDB分析

上面分析出了_sel与_imp保存在bucket_t中，那么接下来就验证下：

(lldb) p $2._bucketsAndMaybeMask
(explicit_atomic<unsigned long>) $3 = {
  std::__1::atomic<unsigned long> = {
    Value = 4298437472
  }
}
(lldb) p $3.Value
error: <user expression 4>:1:4: no member named 'Value' in 'explicit_atomic<unsigned long>'
$3.Value
~~ ^

_bucketsAndMaybeMask能正常获取但是Value却获取不到。同样的_maybeMask以及_flags、_occupied的Value也获取不到。
只好分析下cache_t看有没有暴露什么方法，在源码中发现了buckets()：

struct bucket_t *buckets() const;

验证：

(lldb) p $2.buckets()
(bucket_t *) $4 = 0x000000010034f360
(lldb) p *$4
(bucket_t) $5 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null) {
      Value = (null)
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 0
    }
  }
}

这样数据结构是正常拿到了，但是没有数据（没有调用实例方法）。调用一个方法继续验证：

(lldb) p [obj instanceMethod]
(lldb) p/x [HPObject class]
(Class) $9 = 0x00000001000083c8 HPObject
(lldb) p (cache_t *)0x00000001000083D8
(cache_t *) $10 = 0x00000001000083d8
(lldb) p *$10
(cache_t) $11 = {
  _bucketsAndMaybeMask = {
    std::__1::atomic<unsigned long> = {
      Value = 4301540560
    }
  }
   = {
     = {
      _maybeMask = {
        std::__1::atomic<unsigned int> = {
          Value = 7
        }
      }
      _flags = 32820
      _occupied = 3
    }
    _originalPreoptCache = {
      std::__1::atomic<preopt_cache_t *> = {
        Value = 0x0003803400000007
      }
    }
  }
}
(lldb) p $11.buckets()
(bucket_t *) $12 = 0x0000000100644cd0
(lldb) p *$12
(bucket_t) $13 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null) {
      Value = (null)
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 0
    }
  }
}

仍然没有数据，但是_maybeMask与_occupied有值了。既然buckets是个指针，那么平移继续查找发现index为6的时候有值了。

(lldb) p $2.buckets()[6]
(bucket_t) $11 = {
  _sel = {
    std::__1::atomic<objc_selector *> = "" {
      Value = ""
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 49016
    }
  }
}

虽然有值了，但是打印出来的数据仍然不是需要的，继续分析下bucket_t的方法在源码中找到了sel()和imp()方法：

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
}

验证：

(lldb) p $11.sel()
(SEL) $12 = "instanceMethod"
(lldb) p $11.imp(nil,HPObject.class)
(IMP) $13 = 0x0000000100003cb0 (HPObjcTest`-[HPObject instanceMethod])

这样就获取了sel和imp的值了。

• sel获取：cls->偏移0x10-> cache_t ->buckets()-> bucket_t （根据index）->sel()
• imp获取：cls->偏移0x10-> cache_t ->buckets()-> bucket_t （根据index）->imp(nil,cls)

上面分析完就有了以下疑问，这些问题将在后续分析解读。（在第六部分）

1. 为什么imp需要cls？
2. 为什么_maybeMask值为7，_occupied值为3。？
3. 为什么放在了6号位置？

三、cache模拟代码分析

由于lldb调试并不方便，更好的方式是模拟cache的结构将数据转换为结构体。

3.1 模拟代码

模拟代码如下：

struct hp_cache_t {
    unsigned long _bucketsAndMaybeMask;
    uint32_t _maybeMask;
    uint16_t _flags;
    uint16_t _occupied;
};

struct hp_class_data_bits_t {
    uintptr_t bits;
};

struct hp_objc_class {
    Class ISA;
    Class superclass;
    struct hp_cache_t cache;
    struct hp_class_data_bits_t bits;
};

• hp_cache_t这样定义是因为内部有一个共用体，可以只保留一个结构体。
• 内部结构体可以拆出来放在外层就有了hp_cache_t的结构。

由于最终存储的数据是bucket_t，所以还需要模拟下bucket_t的实现：

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

这样基本的数据结构就还原了。但是有个问题是怎么从_bucketsAndMaybeMask获取buckets呢？
源码如下:

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

是_bucketsAndMaybeMask进行了load操作，这块还原的话内容就太多了，那么直接将_bucketsAndMaybeMask替换为bucket_t的指针呢？然后通过平移去获取下一个元素。这样hp_cache_t内容修改如下：

struct hp_cache_t {
    struct hp_bucket_t *_buckets;
    uint32_t _maybeMask;
    uint16_t _flags;
    uint16_t _occupied;
};

3.2 代码验证

HPObject增加以下方法：

- (void)instanceMethod1;

- (void)instanceMethod2;

- (void)instanceMethod3;

- (void)instanceMethod4;

- (void)instanceMethod5;

- (void)instanceMethod6;

- (void)instanceMethod7;

+ (void)classMethod;

方法实现都是打印方法名。
调用：

HPObject *obj  = [HPObject alloc];
[obj instanceMethod1];
Class objClass = obj.class;
//obj强转成hp_objc_class
struct hp_objc_class *hp_class = (__bridge struct hp_objc_class *)(objClass);
NSLog(@"_occupied :%u _maybeMask :%u",hp_class->cache._occupied,hp_class->cache._maybeMask);
//循环打印bucket数据，_maybeMask为容器大小
for (uint32_t i = 0; i < hp_class->cache._maybeMask; i++) {
    //获取bucket
    struct hp_bucket_t bucket = hp_class->cache._buckets[i];
    NSLog(@"SEL:%@ --- IMP:%p",NSStringFromSelector(bucket._sel),bucket._imp);
}

这段代码先创建HPObject的实例对象然后调用instanceMethod1。最后将objClass转换为hp_objc_class结构体取到_buckets进行循环打印。

输出：

//方法调用信息
HPObject method : -[HPObject instanceMethod1]
//容器信息
_occupied :1 _maybeMask :3
//buckets信息
SEL:(null) --- IMP:0x0
SEL:(null) --- IMP:0x0
SEL:instanceMethod1 --- IMP:0xbb48

_occupied为了1，_maybeMask为3。输出结果符合预期，那么多调用几个方法呢。
增加instanceMethod2调用：

[obj instanceMethod2];

输出：

HPObject method : -[HPObject instanceMethod1]
HPObject method : -[HPObject instanceMethod2]
_occupied :2 _maybeMask :3
SEL:instanceMethod2 --- IMP:0xbb50
SEL:(null) --- IMP:0x0
SEL:instanceMethod1 --- IMP:0xbb60

_occupied变为了2，_maybeMask变为了3。
再调用个方法以及类方法：

[obj instanceMethod1];
[obj instanceMethod2];
[obj instanceMethod3];
Class objClass = obj.class;
[objClass classMethod];

输出：

HPObject method : -[HPObject instanceMethod1]
HPObject method : -[HPObject instanceMethod2]
HPObject method : -[HPObject instanceMethod3]
HPObject class method : +[HPObject classMethod]
_occupied :1 _maybeMask :7
SEL:(null) --- IMP:0x0
SEL:(null) --- IMP:0x0
SEL:instanceMethod3 --- IMP:0xbb30
SEL:(null) --- IMP:0x0
SEL:(null) --- IMP:0x0
SEL:(null) --- IMP:0x0
SEL:(null) --- IMP:0x0

_occupied变为了1，_maybeMask为7。
在调用个init方法:

[obj init];

输出：

_occupied :2 _maybeMask :7
SEL:(null) --- IMP:0x0
SEL:(null) --- IMP:0x0
SEL:instanceMethod3 --- IMP:0xbb68
SEL:init --- IMP:0x7ffe67244ed5
SEL:(null) --- IMP:0x0
SEL:(null) --- IMP:0x0
SEL:(null) --- IMP:0x0

_occupied变为了2，_maybeMask仍为7。

至此可以得到以下结论：

• _occupied为容器中元素个数。
• _maybeMask容器容量大小（其实是容器容量大小-1。在__x86_64__ / __i386__ / __arm__架构下由于存在CACHE_END_MARKER，所以最后一个元素存储的sel -imp为0x1-bucket指针地址，其它架构正常存储。mask的值都是减了1，架构不同存储位置不同）。
• 类方法不在类的cache中，按照之前的分析应该在元类的cache中。
• 父类方法(init)也会存到cache中。
• 当_maybeMask的值变化的时候，_occupied会重新计数。也就意味着扩容的时候之前的缓存都被清空了。

四、cache_t底层原理

上面的结论都是通过代码输出验证的，那么_occupied和_maybeMask到底是怎么变化的呢？父类的init为什么也会被缓存起来呢？这就需要查看底层的源码实现了。

通过之前的验证清楚了数据是存在_bucketsAndMaybeMask中的，根据名字就能判断出来结构类似isa不仅存储_buckets还有MaybeMask信息。

那么切入点就是bucket插入_buckets的逻辑，也就是insert方法。

4.1 insert

核心逻辑如下：

//sel imp 接收者
void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    //对_occupied赋值 + 1。首次 newOccupied = 1。
    mask_t newOccupied = occupied() + 1;
    //旧容量，（mask + 1） 或者 0
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    //是否为空，首次进入这里
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        //默认容量给4
        if (!capacity) capacity = INIT_CACHE_SIZE;//1 << 2 = 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
    //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。最大缓存65536
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        //开辟新的容器控件，释放旧的空间。
        reallocate(oldCapacity, capacity, true);
    }
    //从_bucketsAndMaybeMask获取buckets
    bucket_t *b = buckets();
    mask_t m = capacity - 1;//首次是4-1 这里也就解释了前面代码调试的时候maybeMask为什么为3,7。
    //计算插入的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;
        }
        //已经存在了，不进行任何处理。有可能是其它线程插入的。
        if (b[i].sel() == sel) {
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
        }
        //cache_next为了防止hash冲突。再hash了一次。
    } while (fastpath((i = cache_next(i, m)) != begin));
    //异常处理
    bad_cache(receiver, (SEL)sel);
#endif // !DEBUG_TASK_THREADS
}

• 首次进入isConstantEmptyCache分支。会创建一个容量为4/2的空buckets。这个时候由于旧buckets不存在不需要释放所以参数传递false。

是4还是2取决于INIT_CACHE_SIZE的值，在__x86_64__ / __i386__ / __arm__ / __arm64__ && !__LP64__架构下值为4，在arm64 && LP64架构下值为2。

• 当容量大于等于3/4或7/8的情况下扩容。arm64_64的条件下为7 / 8，其它条件为3/4。
• arm64_64条件下容量小于等于8的时候会占用100%才扩容。

CACHE_ALLOW_FULL_UTILIZATION是arm64_64才为1。FULL_UTILIZATION_CACHE_SIZE值为8。

• 扩容是直接翻倍，默认值4/2。最大值MAX_CACHE_SIZE为2¹⁶(65536)。在扩容的时候直接释放了旧值。
• mask值为capacity - 1，这也就是调试的时候输出3、7的原因（因为最后一个元素有可能存储的是buckets的地址，格式为(sel-imp)0x1-buckets address，存不存在与架构有关）。
• 通过cache_hash计算插入的index，后面会通过cache_next再进行计算hash解决冲突问题。
• 循环判断通过b[i].set插入bucket数据。

为什么扩容后不复制之前的cache？因为内存平移很消耗性能。

4.2 reallocate

ALWAYS_INLINE
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  mask = newCapacity - 1，这里newBuckets为新开辟的，没有数据。空桶
//（其实是有数据的，最后一个存储的是自己的指针，这也是这里为什么传递newCapacity - 1的原因）
    setBucketsAndMask(newBuckets, newCapacity - 1);
    //释放旧bucket
    if (freeOld) {
        //底层垃圾栈回收
        collect_free(oldBuckets, oldCapacity);
    }
}

• reallocate是重新开辟空间。
• 如果是扩容会释放掉旧的buckets

4.3 allocateBuckets

#if CACHE_END_MARKER

bucket_t *cache_t::endMarker(struct bucket_t *b, uint32_t cap)
{
    return (bucket_t *)((uintptr_t)b + bytesForCapacity(cap)) - 1;
}

bucket_t *cache_t::allocateBuckets(mask_t newCapacity)
{
    // Allocate one extra bucket to mark the end of the list.
    // This can't overflow mask_t because newCapacity is a power of 2.
    bucket_t *newBuckets = (bucket_t *)calloc(bytesForCapacity(newCapacity), 1);
//    printf("newBuckets---:%p\n",newBuckets);
    //取最后一个元素
    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;
}

#else

bucket_t *cache_t::allocateBuckets(mask_t newCapacity)
{
    if (PrintCaches) recordNewCache(newCapacity);
    //最后一个不插入 endmarker
    return (bucket_t *)calloc(bytesForCapacity(newCapacity), 1);
}

#endif

• 调用calloc开辟空间。
• x86/i382/arm架构下newBuckets最后一个元素存储SEL-IMP(0x1-bucket address)。
• arm64架构不存储自身地址（包含32位以及64位）。

4.4 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 intel/arm

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

CACHE_MASK_STORAGE_HIGH_16 或 CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS arm64指令64位设备上

• 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不包括最后一个元素buckets自身的地址。

4.5 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指令64位 ）的情况下为7/8 87.5%，其它情况为3/4 75%扩容。
• arm64_64在容量小于8的时候执行100%填满再扩充的逻辑。
• 为什么是这两个值？这里就涉及到了 负载因子，具体可以查阅哈希函数相关知识。在3/4和7/8空间利用率最高，对哈希冲突能进行有效避免。

4.6 cache_hash

#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
    value ^= value >> 7;
#endif
    //sel & mask 得到hash地址。
    return (mask_t)(value & mask);
}

#if CACHE_END_MARKER
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}
#elif __arm64__
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}
#else

• 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相当于娜到最后了(这里是arm64架构可以占用最后一个位置)。

那么insert是在什么时候调用的呢？打个断点查看下调用栈：

image.png

五、_bucketsAndMaybeMask

上面分析道_bucketsAndMaybeMask不仅仅存储buckets还存储MaybeMask，那么它是怎么分布的呢？
这就要看获取buckets()与获取mask()的方法了。

5.1 buckets

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

可以看到关键是bucketsMask，需要确认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。

5.2 mask

上面分析了buckets存储的内容是地址，会根据平台不同占用_bucketsAndMaybeMask的位数和位置不同。那么mask是怎么存储的呢？

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
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

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

#else
#error Unknown cache mask storage type.
#endif

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

5.3 mask存储的到底是什么？

通过上面的分析有两个问题。

5.3.1 arm64指令32位下 0xffff >> maskShift 就取到了 mask，怎么做到的？

要分析这个问题，我们要结合存储的时候逻辑来看，在存储的时候调用了objc::mask16ShiftBits(mask)

static 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;
    ASSERT((0xffff >> maskShift) == mask);
    return maskShift;
}

那么显然核心在__builtin_clz究竟是干什么的？

• __builtin_clz返回前导的0的个数。
  验证：
  

  image.png
  
  也就是说返回的传递进去的值在32位的前置0的个数。0是没有定义的，会返回不确定的值。

• __builtin_clz(mask) - 16减16也就意味着要计算在16位下有多少前置位为0，这里不会为负数。因为在上面分析中已经说了buckets扩容的时候最大值为2¹⁶。

• 所以objc::mask16ShiftBits(mask)存储的就是16位下mask的前置的0的个数。

那么0xffff >> maskShift也就是0xffff >> 前置的0的值 这样就恢复了mask。

为什么能恢复？
0xffff就是0b1111111111111111，而mask的值是从1~65535（当然是1，3，7，15这样的都是全1111111的值，不存在0）这样前置0的取值就从15~0。也就是通过0xffff右移15~0位就能恢复mask的值了。相当于通过前置位的个数将0xffff前面的1抹0而还原了mask(mask有规律，是全1的值。)

在上面mask分别出现过3和7，我们就用这两个值来验证（mask最小为3/1，根据架构不同值不同）：

image.png

为什么苹果要这么存呢？
因为只有4位存储mask()，而在这种情况下前置0的个数最多15个所以4位刚好够存。

在这里我只想给Apple扣666。

具体可以看下这个：_builtin

5.3.2 arm64 64位真机(非mac以及模拟器) mask 占用了高16位，但是buckes占用了低44位。那么中间4位存储了什么？也就是maskZeroBits存储了什么。

在maskZeroBits定义的地方有以下注释：

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

image.png

image.png

buckets与mask分布

_bucketsAndMaybeMask数据分布

六、补充知识

在lldb分析的时候遗留了3个问题，接下来将进行分析。

6.1 为什么imp()需要参数cls？

解决这个问题需要解读源码，分别看下imp的取值和设置

    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
    }

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

    // objc_msgSend uses sel and imp with no locks.
    // It is safe for objc_msgSend to see new imp but NULL sel
    // (It will get a cache miss but not dispatch to the wrong place.)
    // It is unsafe for objc_msgSend to see old imp and new sel.
    // Therefore we write new imp, wait a lot, then write new sel.
    
    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);
    }
}

    // Sign newImp, with &_imp, newSel, and cls as modifiers.
    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的时候会判断是否需要impEncoding，如果需要会进行(uintptr_t)newImp ^ (uintptr_t)cls，所以在读取imp的时候需要传参数cls进行还原。相当于(uintptr_t)cls^imp^(uintptr_t)cls = imp。那么就说明buckets中存储的imp不一定是真实的imp，有可能是经过编码的。

6.2 为什么在调用了一个方法后_maybeMask值为7，_occupied值为3？

在lldb调试的时候在调用了一个方法后发现_maybeMask为7，_occupied为3。正常情况应该是3和1。
根据前面的源码分析既然_maybeMask为7了那么肯定进行了扩容操作，在扩容前打印buckets中的内容查看下是什么数据：

image.png

• 这里cls传nil是为了恢复0x1的imp，因为在源码添加第一个元素的时候cls是nil。

image.png

这样就清晰了在lldb调试的过程中会调用class以及responseToSelector方法。0x1是最后一个数据buckets的地址。

image.png

代码验证：

image.png

⚠️ 非arm64架构下buckes最后一个元素是自身的地址。

6.3 为什么第一个元素放在了6号位置？

简单说就是

• 数组：方便读取，插入和删除不方便
• 链表：方便插入和删除，读取不便。

所以就有了哈希数据结构，哈希结合了数据和链表的能力方便增删和查找。4.6中分析了cache_hash。哈希函数用的是sel & mask，解决冲突用的是开放定址法的线性探查法

具体参考
哈希函数
哈希表理论

Cache_t原理分析图

cache_t流程