类的结构

OC中类的结构分为isa、superclass、cache、bits，这里我们来探索一下cache。

cache_t

首先然我们来看看cache_t的源码:

struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    explicit_atomic<struct bucket_t *> _buckets;
    explicit_atomic<mask_t> _mask;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;    
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;

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

    unsigned capacity();
    bool isConstantEmptyCache();
    bool canBeFreed();
}

以上是objc中cache_t的源码，上面只摘录了个人觉得比较重要的一部分，省略了很多不重要的代码，想要看完整源码可以自己去源码查找。
下面就让我们来分析一下源码:

_buckets

首先来看一下explicit_atomic<struct bucket_t *> _buckets;这里的explicit_atomic是一个泛型结构体，它的类型和传入的结构体类型有关。
_buckets：通过查找源码可以发现它是用来缓存方法的sel和imp的，它是用哈希散列方法来实现存储的。下面我用lldb调试来验证一下_buckets中所存储的内容是不是sel和imp。

代码.png

buckets内容.png

获取cache，用LGPerson的首地址指针平移16字节，也就是上面的98加0x10得到a8.
获取cache中所存放的东西_buckets、_mask、_flags、_occupied.
获取到buckets里面的内容，可以发现里面正是存放了方法sel和函数指针imp

sel和imp.png

_mask

获取sel以及imp的具体内容。
在进行lldb调试时可以发现上面的buckets只打印出了一个数据，如果buckets中存在多条数据，可以通过地址偏移来打印出其他的数据，如*($3 + 1)

_mask：可以用做掩码，用来计算buckets内存大小时表示最大空间数,它等于capacity - 1。

_flags
_occupied

_buckets中已经缓存的方法数量

cache_t如何缓存方法

从上面代码中可以看到有void incrementOccupied();这是occuiped增加的函数，它的具体实现为

void cache_t::incrementOccupied() 
{
    _occupied++;
}

通过全局搜索可以发现存在void cache_t::insert这样一个函数，显然这是cache_t的插入方法，下面来具体分析一下它的具体实现:

void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{
#if CONFIG_USE_CACHE_LOCK
    cacheUpdateLock.assertLocked();
#else
    runtimeLock.assertLocked();
#endif

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

    // Use the cache as-is if it is less than 3/4 full
    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 <= 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);  // 内存 库容完毕
    }

    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 because the
    // minimum size is 4 and we resized at 3/4 full.
    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));

    cache_t::bad_cache(receiver, (SEL)sel, cls);
}

以上源码大致分为3个步骤：

初始化：计算出当前需要缓存大小；

判断是否需要扩容。扩容时是扩容至原始空间大小的两倍，并且是释放原来的缓存重新申请，而不是在原来的基础上增加。

根据哈希函数计算查找当前缓存中是否存在方法，判断是否需要插入。

具体实现：

1. 初始化缓存大小

当我们要缓存方法是首先肯定是要初始化缓存空间，给它一个size,而我们初次初始化时大小为4。

if (!capacity) capacity = INIT_CACHE_SIZE; //初始化大小

点击查看INIT_CACHE_SIZE

enum {
    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2),
    MAX_CACHE_SIZE_LOG2  = 16,
    MAX_CACHE_SIZE       = (1 << MAX_CACHE_SIZE_LOG2),
};

从上面源码可以得到INIT_CACHE_SIZE的大小为1左移2位，所以我们初次初始化缓存空间的大小为4。

reallocate(oldCapacity, capacity, /* freeOld */false); 这是去开辟缓存缓存空间，参数分别是原来的缓存大小、刚刚计算得到的缓存大小、是否需要清理旧的缓存。
由于是初次初始化不需要清理，所以第三个参数传false。

2. 判断是否需要进行扩容

在初始化创建完成之后去缓存方法时，要判断是否需要扩容，防止超出。
判断条件为：当前已占用的是否小于等于缓存大小的3/4。如果小于那么不需要扩容，否则需要进行扩容。

fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3) //判断条件

扩容的方法如下:

capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // capacity存在扩容至原大小的两倍，否则为4
if (capacity > MAX_CACHE_SIZE) {
    capacity = MAX_CACHE_SIZE;     //缓存大小 最大为 1<<16  1左移16位
}
reallocate(oldCapacity, capacity, true);  // 开辟缓存，这一步需要清理初次创建的缓存，然后重新创建

清理方法如下:

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) {
        cache_collect_free(oldBuckets, oldCapacity);
    }
}

3. 缓存方法

开辟完缓存空间这一步只是相当于制作了一个容器，容器造好了然后就是往里面放东西了，那么怎么放呢？

mask_t begin = cache_hash(sel, m); 通过哈希算法计算出初始查找下标。
fastpath(b[i].sel() == 0) 该位置没有缓存方法，将占用计数occupied加1，并插入方法
b[i].sel() == sel 该位置已经存在该方法，直接return
fastpath((i = cache_next(i, m)) != begin) 该位置已存在方法，但是不是将要存入的方法，通过cache_next重新计算得到一个下标再进行判断插入。

cache_hash哈希算法

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;
}

cache_next哈希冲突算法

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

OC底层探索-cache_t