cache_t底层分析

类的本质我们已经分析完了，里面有isa、superclass、cache、bits。
今天对cache进行研究。在objc源码中可以看到cache的类型是cache_t，用lldb调试打印cache的所有数据：

cache_t

在这里看的数据会感觉比较混乱，那我们从源码中分析，最后再回来验证。
在struct cache_t结构中，我们根据提供的方法来分析里面的数据结构，找到一行关键代码void insert(SEL sel, IMP imp, id receiver);，缓存中插入数据，根据参数我们一下就能知道cache里面缓存的是方法了。点击insert方法看里面都有哪些操作：

image

发现里面有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
}

bucket_t里面就有两个成员，一个_imp，一个_sel，这下我们心里大概能有个概念，cache是缓存方法的，里面有个bucket_t数组，数组每一项里面存着imp和sel。

虽然得出了一些结论，但是还是要通过lldb进行验证。因为cache_t里面没有bucket_t这个成员，所以就要找相关方法看有没有能获取的，正好找到struct bucket_t *buckets() const;这个方法可以获取，那我们进行验证。

bucket_t

输出发现是有bucket_t，但是里面的值都是空的，怎么回事呢？以为缓存是缓存的方法，你什么方法都不执行哪来的缓存，我们重新执行下代码。

SJPerson *p = [SJPerson alloc];
[p doSomething];

image
image

我们看到上面Value是3，打印出来为什么还是没有数据呢？那我们试图打印buckets后面几个数据试试：

image

发现第2个元素有值了，为了验证是不是我们的doSomething方法，在bucket_t结构里面找对应的输出方法，继续调试

image

发现确实是我们的方法，没有问题。
接下来我们对cache_t进行原理分析。既然是缓存，肯定有读写相应的操作，我们从写作为入口进行分析，为什么不从读作为入口呢，因为你不先写，读也读不出来数据。在cache_t中的方法void insert(SEL sel, IMP imp, id receiver);，我们点进去看下插入都做了什么操作。

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    /// occupied(): return _occupied; 成员变量，默认0
    mask_t newOccupied = occupied() + 1; // 这里+1是为了把这次执行的方法先加上
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    /// 第一个if:cache是空
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        ///  capacity=0时 初始设置 capacity = INIT_CACHE_SIZE = 4，真机为2
        if (!capacity) capacity = INIT_CACHE_SIZE;
        /// 申请缓存的内存空间，具体代码在下一段
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    /// 如果 newOccupied + 1 <= 3/4 * capacity，还可以继续插入，对桶子不做操作，真机的负载因子是7/8
    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.
    }
/// arm64&&LP64 即真机环境下  CACHE_ALLOW_FULL_UTILIZATION为1
#if CACHE_ALLOW_FULL_UTILIZATION
    /// 如果 capacity<=1<<3，即8 && newOccupied <= capacity，还可以继续插入，对桶子不做操作
    /// 真机容量小于等于8，可以全填满，大于8时真机用7/8
    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为0时，capacity = 4，不为0时 capacity *2直接扩容到原来的2倍
        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; 
    /// 利用hash算法计算下标开始值，供下面循环使用，算法真机环境稍微有所区别
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;

    /// 一个循环，退出条件：1、成功插入  2、已经被插入  3、找一圈下标也没合适位置插入。3个条件满足一个即退出循环，最后一种情况会走bad_cache
    // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot.
    do {
        /// 如果桶子的i位置没有存数据，则直接插入
        if (fastpath(b[i].sel() == 0)) {
            /// _occupied++;  也就是说_occupied是记录方法插入的个数
            incrementOccupied();
            /// 插入方法，真机和非真机有小区别
            b[i].set<Atomic, Encoded>(b, sel, imp, cls());
            return;
        }
        /// 如果当前位置插入的有数据并且与执行的方法相同，直接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实现在下面
    } while (fastpath((i = cache_next(i, m)) != begin));

    bad_cache(receiver, (SEL)sel);
#endif // !DEBUG_TASK_THREADS
}

/**
 * 模拟器，mac环境CACHE_END_MARKER为1
 * 负载因子3/4
 * CACHE_END_MARKER为1，buckets填充结束标志
*/ 
#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;
}
/**
 * 真机环境 CACHE_END_MARKER为0
 * 负载因子7/8
 * CACHE_END_MARKER为0，buckets不用填充结束标志
 * CACHE_ALLOW_FULL_UTILIZATION为1，小容量缓存允许充满
*/ 
#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


enum {
#if CACHE_END_MARKER || (__arm64__ && !__LP64__)
    INIT_CACHE_SIZE_LOG2 = 2,
#else
    INIT_CACHE_SIZE_LOG2 = 1,
#endif
    /// 真机环境INIT_CACHE_SIZE=2，模拟器mac INIT_CACHE_SIZE=4
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2),
    MAX_CACHE_SIZE_LOG2  = 16,
    MAX_CACHE_SIZE       = (1 << MAX_CACHE_SIZE_LOG2),
    FULL_UTILIZATION_CACHE_SIZE_LOG2 = 3,
    FULL_UTILIZATION_CACHE_SIZE = (1 << FULL_UTILIZATION_CACHE_SIZE_LOG2),
};

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    /// 旧桶子
    bucket_t *oldBuckets = buckets();
    /// 新桶子根据newCapacity来申请，申请的具体代码在下一段
    bucket_t *newBuckets = allocateBuckets(newCapacity);
    /// 设置_bucketsAndMaybeMask成员变量
    setBucketsAndMask(newBuckets, newCapacity - 1);
    /// 释放旧桶子，也就是把原来的缓存数据丢掉不要了
    if (freeOld) {
        collect_free(oldBuckets, oldCapacity);
    }
}

#if CACHE_END_MARKER
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.
    /// 申请内存空间，大小：newCapacity
    bucket_t *newBuckets = (bucket_t *)calloc(bytesForCapacity(newCapacity), 1);

    /// 创建桶子最后一个元素，来标记buckets末尾
    bucket_t *end = endMarker(newBuckets, newCapacity);

    /// 官方注释也写的很明白，把最后一个元素设置上值，sel是1，
#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.
    end->set<NotAtomic, Raw>(newBuckets, (SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    /// 打印相关信息
    if (PrintCaches) recordNewCache(newCapacity);

    return newBuckets;
}
#else
/// 真机会走这个方法，直接申请内存，没有插入endBucket
bucket_t *cache_t::allocateBuckets(mask_t newCapacity)
{
    if (PrintCaches) recordNewCache(newCapacity);

    return (bucket_t *)calloc(bytesForCapacity(newCapacity), 1);
}

#endif

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
/// 从这个方法代码可以看出_bucketsAndMaybeMask是存buckets。
/// 这里有个小细节newMask是（newCapacity - 1），也就是总长度减1
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_release);
    _maybeMask.store(newMask, memory_order_release);
    _occupied = 0;
}
/// 这里又有小细节，mac环境mask直接用_maybeMask，和真机不一样哦，调试时会发现
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和buckets存到_bucketsAndMaybeMask里面，基于位运算
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;
}

/// 真机的mask是根据_bucketsAndMaybeMask来的，这也是写类似结构体真机调试时_maybeMask一直为0的原因
mask_t cache_t::mask() const
{
    uintptr_t maskAndBuckets = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return maskAndBuckets >> maskShift;
}

/// 真机是每次-1，当减到0时，设置为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;
}

上面代码关键内容我都进行了注释，里面有些需要注意的细节

1. mac初始创建容量为4，真机环境初始创建容量为2，每次扩容是当前容量的2倍
2. mac当_occupied+1大于3/4容量时进行扩容，为什么是3/4呢？因为负载因子0.75时，空间利用率是比较好的，和对hash冲突可以有效避免，具体的可查阅相关算法知识
3. 真机当容量小于等于8的时候是可以填满buckets的，大于8时负载因子是7/8
4. _maybeMask的值是容量减1
5. mac环境_maybeMask直接可以读到值，真机时没有，只能用_bucketsAndMaybeMask做位运算获取
6. hash算法解决冲突时，arm64与非arm64算法不同，真机是减1，减到0是等于mask
7. buckets是散列表结构，单是注意不是数组！不是数组！！不是数组！！！强调3遍！！！
8. 每次扩容申请新buckets时，都会把旧的释放掉
9. mac环境buckets有个结束标志，新建时把最后一个bucket设置到buckets末尾，来标记这段散列表的结束，它的sel是1。真机是没有结束标志的。

insert流程我们总结完了，是不是对cache_t的理解更深一步呢？什么？？上面代码太乱？？？好吧，我就总结下insert的流程图吧，因为mac和真机流程不一样，所以这里总结两个流程图：

cache_t insert-mac.jpg cache_t insert-真机.jpg

insert流程总结完，我们看一个非常有意思的现象。创建SJPerson类，里面生命并实现say1、say2方法：

@interface SJPerson : NSObject

- (void)say1;
- (void)say2;

@end

@implementation SJPerson

- (void)say1
{
    NSLog(@"%s", __func__);
}
- (void)say2
{
    NSLog(@"%s", __func__);
}
@end

然后我们执行下面代码并打断点

SJPerson *p = [SJPerson alloc];
[p say1];

执行完say1的时候，按上面的分析，maybeMask应该等于3，lldb进行调试验证：

image

验证没有问题，我们增加代码[p say2]，并在say2后面打断点，按上面的分析，maybeMask应该等于3，lldb进行调试验证：

image

验证通过，接下来我们做一个骚操作，删除say2，在say1执行完后打断点，这时候我们已经验证过maybeMask是3，occupied是1，没有问题。这时我们在lldb中输入p [p say2]，这时候也是让p执行say2方法，按道理执行完cache里面的结果应该跟上面一样，进行验证：

image

神奇的一幕出现了，maybeMask成7了，occupied还是2没问题。诶?7也就是说cache做了一次扩容，但是我们就执行了两个方法，初始容量是4，负载因子0.75，2小于3应该不会扩容啊，我们继续看这8个位置的方法都有什么。

image

缓存里面有class和say2两个方法，但是class我们并没有执行啊，这时候我们猜测在lldb调试执行p [p say2]，系统会自动执行一些方法。在insert方法里面打印相关信息printf("cache_t insert ====== sel : %s imp : %p receiver : %p \n", (char *)sel, imp, receiver);

image image

我们看到p [p say2]时，插入了很多方法，我们只看receiver是p对象的方法，有三个，这时候我们可以继续分析，[p say1]时候插入一个方法；要插入respondsToSelector时，计算3<=43/4，继续插入；插入class时，4>43/4，所以要扩容重新开辟内存，这是容量就变成8了，maybeMask为7；插入say2时，3<=8*3/4，插入，这时cache里面有两个方法，跟我们分析的一致了。

真机验证insert

我们先根据上面分析猜测一下真机验证的结果。我们画个猜测流程图：

真机cache缓存流程猜测.jpg

流程猜测完了，真机验证下是否和我们猜测结果一致呢？答案是一致，非常完美，附上测试demo的链接，可以下载测试。cache_t-Demo

这里还有个坑点，我最早跑demo时候，结果和上面流程并不一样，初始容量4，负载因子一致是0.75，把源码看了一遍又一遍都怀疑人生了。后来发现是自己iOS版本太低，因为objc源码我下载最新的，但是iOS版本低，真机运行和分析结果会有所差别，所以在分析时，
一定要下载最新的源码，iOS升级最新系统，xcode升级最新版本！！！
一定要下载最新的源码，iOS升级最新系统，xcode升级最新版本！！！！！
一定要下载最新的源码，iOS升级最新系统，xcode升级最新版本！！！！！！！
重要的事情说3遍，我下载源码版本818.2，手机iphoneX，iOS14.6，xcode12.5。

objc_msgSend引入

缓存的插入我们已经了解了，那在什么时机会调用插入呢，我们继续研究。
在objc-cache.mm可以看到文件说明注释中写的很清楚

 * Cache readers (PC-checked by collecting_in_critical())
 * objc_msgSend*
 * cache_getImp
 *
 * Cache readers/writers (hold cacheUpdateLock during access; not PC-checked)
 * cache_t::copyCacheNolock    (caller must hold the lock)
 * cache_t::eraseNolock        (caller must hold the lock)
 * cache_t::collectNolock      (caller must hold the lock)
 * cache_t::insert             (acquires lock)
 * cache_t::destroy            (acquires lock)

在读缓存的时候，最早会调用objc_msgSend，也就是发送消息时候会进行读取方法。下一个篇章分析objc_msgSend。