cache_t底层原理

cache的数据结构

我们需要知道cache中存储的到底是什么？我们通过objc源码分析cache_t的结构，发现其根据架构处理分成了三种情况，分别为:

CACHE_MASK_STORAGE_OUTLINED 表示运行的环境模拟器或者 macOS
CACHE_MASK_STORAGE_HIGH_16 表示运行环境是ram64架构64位的真机
CACHE_MASK_STORAGE_LOW_4 表示运行环境是ram64架构非64位的真机
其中这三种情况在源码中的处理又区分为真机与非真机，真机时cache_t有_maskAndBuckets而非真机则分为_buckets、_mask。对于存储bucket及mask，真机上有做优化。
源码分析bucket_t结构，发现其主要有sel跟imp的。

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

所以可以得出一个结论cache中存储是方法编码及方法实现。

验证cache缓存方法

我们之前使用过lldb调试去分析objc_class的内部结构，同样我们可以通过lldb调试去看，到底方法是如何存储到cache中的。

LGPerson *p  = [LGPerson alloc];
Class pClass = [LGPerson class];
//在此断点

(lldb) p/x pClass //pClass是LGPerson类
(Class) $0 = 0x0000000100002350 LGPerson 
(lldb) p (cache_t *)0x0000000100002360 //通过首地址偏移16位定位到cache的地址
(cache_t *) $1 = 0x0000000100002360
(lldb) p *$1 //读取
(cache_t) $2 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x000000010032e430 {
      _sel = {
        std::__1::atomic<objc_selector *> = (null)
      }
      _imp = {
        std::__1::atomic<unsigned long> = 0
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 0
  }
  _flags = 32820
  _occupied = 0
}
(lldb) p $2.buckets() //获取cache中的buckets
(bucket_t *) $3 = 0x000000010032e430
(lldb) p * $3 //读取buckets存储的信息
(bucket_t) $4 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null)
  }
  _imp = {
    std::__1::atomic<unsigned long> = 0
  }
}

LGPerson是我们定义的一个类，通过调试获取其类首地址。通过lldb调试我们可以看到，实例创建后我们没有做其他处理。接下来我们调用一次实例方法，继续lldb调试。

2020-09-19 15:14:40.256183+0800 KCObjc[11077:193815] sayHelloWorld方法调用
(lldb) p $2.buckets()
(bucket_t *) $6 = 0x0000000102904fc0
(lldb) p *$6
(bucket_t) $7 = {
  _sel = {
    std::__1::atomic<objc_selector *> = ""
  }
  _imp = {
    std::__1::atomic<unsigned long> = 10336
  }
}
(lldb) p $7.sel()
(SEL) $8 = "sayHelloWorld"
(lldb) p $7.imp([LGPerson class])
(IMP) $9 = 0x0000000100000b30 (KCObjc`-[LGPerson sayHelloWorld])

调用一次方法后，继续去读cache，发现确实能够读取到方法的sel及imp。验证了cache确实是存储了我们定义的实例方法。
只缓存了一个方法的调试我们已经清楚了，那么多个方法的情况怎么办呢？

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

因为buckets返回的是个数组，我们可以直接通过下标的方式访问到数组中的其他的bucket_t。
注意:cache缓存方法不是顺序的而是乱序的。

cache_t底层源码分析

通过源码，我们可以对cache有一个初步的了解，其内部主要的一些属性buckets、occupied、mask，
通过对应的数据结构，初步有一个模糊的概念，cache_t内部主要是为了存储bucket_t,在前面的lldb调试时，可以看到occupied在缓存方法后是发生了变化的，猜测其是用来记录缓存方法数的，mask是用来做掩码处理的。
cache_t的public方法


    static bucket_t *emptyBuckets();
    struct bucket_t *buckets();
    mask_t mask();
    mask_t occupied();
    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    void initializeToEmpty();

这些方法中我们主要看的是incrementOccupied。通过查找incrementOccupied，我们找到了

void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{
    ....
}

在insert方法的源码中我们可以找到两个很关键的处理，
1.cache_t扩容的逻辑

  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 <= capacity / 4 * 3)) { // 4  3 + 1 bucket    cache_t
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 扩容两倍 4
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);  // 内存 库容完毕
    }

最初容量值定义为4.容量如果达到当前容量的3/4，就会在当前容量的基础上扩容两倍。
扩容完毕后调用reallocate方法，重新开辟空间，再进行存储。这里注意，扩容开辟存储时，之前的存储的方法在新的存储中时没有了。

存储sel、imp的处理

    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;
    do {
        if (fastpath(b[i].sel() == 0)) {
            incrementOccupied();
            b[i].set<Atomic, Encoded>(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));

static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}

#if __arm__  ||  __x86_64__  ||  __i386__
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;
}

存储的位置begin是通过cache_hash计算得到的，然后使用&mask计算得到具体的位置，mask值为当前容量减一，如果这个位置为空则插入存储，如果已经被缓存则退出，否则继续cache_next。
cache_next在真机跟非真机上是处理不同的。