iOS底层学习-类的cache_t 分析

这是我参与8月更文挑战的第6天，活动详情查看：8月更文挑战

在类的原理分析篇章中，已经了解类的结构，并分析了bits结构，文中也有提及cache。今天来具体分析下cache

一、cache数据结构

cache就是缓存，类的缓存。具体是怎么缓存的呢？带着问题先看下cache_t的数据结构

通过lldb断点调试，首地址平移16字节即0x10即可得到cacht_t

发现和源码中cache_t的结构一致。那么结构中的成员变量哪个是cache_t的重点呢？

首先我们知道对缓存的操作就是增删改查。在cache_t结构体中再看看有没有其他关键的方法或操作。在cache_t的public:方法中找到了insert方法。

void insert(SEL sel, IMP imp, id receiver);
复制代码

insert顾名思义插入，接着进入insert方法

insert方法中是对bucket的操作，继续进入bucket_t

bucket_t中有我们熟悉的IMP和SEL，明显缓存的方法在bucket_t中

最后得到如下结构关系图：

二、LLDB分析cache底层

上面分析了cache的结构，最终找到缓存在bucket_t中，那么现在就通过lldb调试验证一下

先获取cache_t中的_bucketsAndMaybeMask，在获取_bucketsAndMaybeMask中的Value时却获取不到。然后我们在cache_t结构体中找到下面这个方法

struct bucket_t *buckets() const;
复制代码

获取cache_t中的buckets()，找到我们想要的_sel和_imp。但这里的值都不是null就是0就是没有值。是因为目前还没执行方法所以没有缓存，修改代码调用方法后再调试下

结果buckets中还是没有值，但是mask和occupied中有了变化，说明应该是有缓存了。为何buckets还是没有呢？

可以看到上面定义buckets是一个结构体指针，直接打印buckets()获取到的是首地址，需要用buckets()[index]地址偏移获取其他bucket

最终在下标为2时找到有值的bucket，通过bucket_t的sel方法打印出刚调用过的方法名。

三、cache底层原理分析

我们知道缓存首先要先写进去，才能读取。刚才我们已经看到了一个insert插入方法。那么就从这个方法开始分析

void insert(SEL sel, IMP imp, id receiver);
复制代码

insert方法传入的参数分别是sel、imp和receiver接受者。源码分析：

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    ...
    
    // Use the cache as-is if until we exceed our expected fill ratio.
    mask_t newOccupied = occupied() + 1;// 第一次进occupied() = 0， newOccupied = 1
    unsigned oldCapacity = capacity(), capacity = oldCapacity;// _maybeMask + 1， 第一次进为0
    if (slowpath(isConstantEmptyCache())) { // 空缓存，首次进入
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE;// 默认赋值为4
        reallocate(oldCapacity, capacity, /* freeOld */false);// 开辟容量
    }
    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.
        // 缓存容量小于等于capacity的3/4或7/8(不同架构)，什么也不做继续往下走
    }
#if CACHE_ALLOW_FULL_UTILIZATION
    else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) {
        // Allow 100% cache utilization for small buckets. Use it as-is.
        // capacity <= 8 且 newOccupied + 1/0 <= capacity时，允许缓存100%使用
    }
#endif
    else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;// capacity有值就两倍扩容，否则为4
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);// 开辟新内存，释放旧的空间
    }

    bucket_t *b = buckets();// 获取buckets()首地址
    mask_t m = capacity - 1;// mask = capacity - 1
    mask_t begin = cache_hash(sel, m);// 获取hash下标
    mask_t i = begin;

    // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot.
    do {
        if (fastpath(b[i].sel() == 0)) { // bucket为空
            incrementOccupied(); // Occupied + 1
            b[i].set<Atomic, Encoded>(b, sel, imp, cls()); // 将sel、imp存入bucket
            return;
        }
        if (b[i].sel() == sel) { // bucket已存在 不做处理
            // 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));// 防止hash冲突。再hash一次。不等于begin下标为止
    
    ...
}
复制代码

先创建了一个newOccupied。occupied()获取当前所占的容量，就是缓存中有几个bucket：

mask_t cache_t::occupied() const
{
    return _occupied;
}
复制代码

oldCapacity和capacity为_maybeMask + 1或0：

unsigned cache_t::capacity() const
{
    return mask() ? mask()+1 : 0; 
}

mask_t cache_t::mask() const
{
    return _maybeMask.load(memory_order_relaxed);
}
复制代码

reallocate方法：

ALWAYS_INLINE
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    bucket_t *oldBuckets = buckets();// 获取oldBuckets
    bucket_t *newBuckets = allocateBuckets(newCapacity);// 获取新开辟的newBuckets

    // 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);
    
    // 设置Buckets和Mask的值，Buckets为newBuckets，Mask为newCapacity - 1
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
        // 释放旧内存，即清空之前的缓存
        collect_free(oldBuckets, oldCapacity);
    }
}
复制代码

• allocateBuckets开辟内存空间
• setBucketsAndMask设置buckets和mask
• collect_free判断是否释放旧内存（扩容时会释放）

allocateBuckets 方法：

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);// 开辟新buckets

    bucket_t *end = endMarker(newBuckets, newCapacity);// 取新buckets的最后一个

#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 = 1，imp=新newBuckets的首地址
    end->set<NotAtomic, Raw>(newBuckets, (SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    
    if (PrintCaches) recordNewCache(newCapacity);

    return newBuckets;
}
复制代码

• calloc开辟内存
• end->set将开辟内存的最后一个位置存入sel = 1，imp = 第一个buket位置的地址

setBucketsAndMask方法：

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    // objc_msgSend uses mask and buckets with no locks.
    // It is safe for objc_msgSend to see new buckets but old mask.
    // (It will get a cache miss but not overrun the buckets' bounds).
    // It is unsafe for objc_msgSend to see old buckets and new mask.
    // Therefore we write new buckets, wait a lot, then write new mask.
    // objc_msgSend reads mask first, then buckets.

#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
    // ensure other threads see buckets contents before buckets pointer
    // _bucketsAndMaybeMask把newBuckets转为地址指针存入
    _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_release);

    // ensure other threads see new buckets before new mask
    // _maybeMask存入newMask
    _maybeMask.store(newMask, memory_order_release);
    _occupied = 0;
#else
#error Don't know how to do setBucketsAndMask on this architecture.
#endif
}
复制代码

• _bucketsAndMaybeMask.store()向_bucketsAndMaybeMask中存入数据
• _maybeMask.store()向_maybeMask中存入数据

四、cache_t整体流程图

cache_t的整体流程（借用kc老师的图?）