cache_t分析

作者: Y丶舜禹 | 来源:发表于2020-09-18 15:25 被阅读0次

前言

在之前的文章中，我们剖析了类的结构，今天我们来分析一下类结构中一个非常重要的结构体cache_t，从名字上我们可以大致可以猜出，cache_t是用来做缓存的，那么它究竟是缓存的什么呢？又是如何缓存的呢？今天我们就来探索一下（本次探究源码基于objc781）.

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;

...一些static属性

#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;

...一些static属性

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__
    MethodCacheIMP _imp;
    cache_key_t _key;
#else
    cache_key_t _key;
    MethodCacheIMP _imp;
#endif

其中explicit_atomic是苹果为了保护缓存安全所加的一个原子性的结构体，并没有太大的意义，_buckets的真实类型是struct bucket_t *，
_mask的真实类型是mask_t，而_flags（64位）和_occupied（32位）为一个标识常量。

下面我们逐个介绍一下，这些属性代表的含义。

_buckets：数组，是存放bucket_t结构体的数组，而bucket_t是用来存放方法的SEL和IMP内存地址的。
_mask：_mask的大小是_buckets长度 - 1，用作面具掩码
_occupied：数组实际所占的内存大小

下面我们通过LLDB调试验证一下。

LLDB调试验证

同样的我们定义一个ZGPerson类，代码如下：

@interface ZGPerson : NSObject
@property (nonatomic, copy) NSString *name;
@property (nonatomic, strong) NSString *nickName;

- (void)test1;

- (void)test2;

- (void)test3;

- (void)test4;

- (void)test5;

+ (void)test6;

@end
@implementation ZGPerson
- (void)test1{
    NSLog(@"方法名: %s",__func__);
}

- (void)test2{
    NSLog(@"方法名: %s",__func__);
}

- (void)test3{
    NSLog(@"方法名: %s",__func__);
}

- (void)test4{
    NSLog(@"方法名: %s",__func__);
}

- (void)test5{
    NSLog(@"方法名: %s",__func__);
}

+ (void)test6{
    NSLog(@"方法名: %s",__func__);
}
@end

当我们在main中初始化而未执行方法时

初始化

LLDB打印如下

(lldb) p/x pClass     //打印类的首地址
(Class) $0 = 0x00000001000022b8 ZGPerson
(lldb) p (cache_t *)0x00000001000022c8  //内存偏移16字节获取cache_t的值（前面有isa和superclass各占8个字节）
(cache_t *) $1 = 0x00000001000022c8
(lldb) p *$1// 取cache_t *的值
(cache_t) $2 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x00000001003ea440 {
      _sel = {
        std::__1::atomic<objc_selector *> = 0x0000000000000000
      }
      _imp = {
        std::__1::atomic<unsigned long> = 0
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 0
  }
  _flags = 32804
  _occupied = 0
}

可见，_mask为0，_occupied内存占用为0

当我们执行了test1后

执行了test1

2020-09-17 22:01:29.612583+0800 KCObjc[50334:1426342] 方法名: -[ZGPerson test1]
(lldb) p *$1
(cache_t) $3 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x00000001011191d0 {
      _sel = {
        std::__1::atomic<objc_selector *> = 0x0000000100000e4c
      }
      _imp = {
        std::__1::atomic<unsigned long> = 10584
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 3
  }
  _flags = 32804
  _occupied = 1
}
(lldb) p $3.buckets()  //通过系统定义的buckets()方法获取_buckets数组
(bucket_t *) $4 = 0x00000001011191d0
(lldb) p $4[0].sel()  //通过系统定义的sel())方法获取bucket_t中_sel的的值
(SEL) $5 = "test1"

可见，方法调用正常，_occupied = 1，_mask = 3，也打印出了test1.

但是当我们调用了好几个方法后

调用多个方法

我们却发现了奇怪的现象

(lldb) p/x pClass
(Class) $0 = 0x00000001000022b8 ZGPerson
(lldb) p (cache_t *)0x00000001000022c8
(cache_t *) $1 = 0x00000001000022c8
(lldb) p *$1
(cache_t) $2 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x0000000100666950 {
      _sel = {
        std::__1::atomic<objc_selector *> = 0x0000000100000e58
      }
      _imp = {
        std::__1::atomic<unsigned long> = 12024
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 7
  }
  _flags = 32804
  _occupied = 2
}
(lldb) p $2.buckets()
(bucket_t *) $3 = 0x00000001006a0c20
(lldb) p $3[0].sel()
(SEL) $4 = "test3"
(lldb) p $3[1].sel()
(SEL) $5 = <no value available>
(lldb) p $3[2].sel()
(SEL) $6 = <no value available>

此时，_occupied = 2，_mask = 7，而不是我们想象的_occupied = 4，而且我们打印方法也只打印出了一个test3，这究竟是为什么呢？下面我们通过源码一探究竟！

cache_t怎么存的？

下面我们从源码分析一下cache_t的存储流程，前面我们注意到，一旦开始调用方法，_occupied就会增加，而我们cache_t的结构体中发现了一个使_occupied 增加的方法为void incrementOccupied();

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

我们全局搜索incrementOccupied，发现只在cache_t的insert方法中有调用，我们继续搜索insert(发现在objc_cache.mm文件的cache_fill方法中会调用insert

cache_fill源码

void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
    runtimeLock.assertLocked();

#if !DEBUG_TASK_THREADS
    // Never cache before +initialize is done
    if (cls->isInitialized()) {
        cache_t *cache = getCache(cls);
#if CONFIG_USE_CACHE_LOCK
        mutex_locker_t lock(cacheUpdateLock);
#endif
        cache->insert(cls, sel, imp, receiver);
    }
#else
    _collecting_in_critical();
#endif
}

insert源码（关键代码）

ALWAYS_INLINE
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
    //1.初始化缓存空间
    mask_t newOccupied = occupied() + 1;//即将要占用的个数 = 已占用个数+ 1
    unsigned oldCapacity = capacity(), capacity = oldCapacity;//获取已占用的个数

    //2.判断是否需要扩容
    if (slowpath(isConstantEmptyCache())) {//如果缓存是空的，去开辟内存空间
        // Cache is read-only. Replace it.
        //INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2), 1左移两位为4
        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
        // 如果 newOccupied +1 <= 容量的4分之3，存储空间还足够，不需额外处理，由此可以看出只要容量等于4分之3时，立马就要进行其他操作
        // Cache is less than 3/4 full. Use it as-is.
    }
    //如果等于或超过4分之3
    else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 扩容两倍 4
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;// 最大不能 超出 1<< 16即256
        }
        reallocate(oldCapacity, capacity, true);  // 扩容
    }
    //  3.判断散列表中是否已有该方法的缓存情况插入缓存或者return

    bucket_t *b = buckets();// 获取散列表
    mask_t m = capacity - 1;// 获取散列表大小 - 1（面具）
    // 通过cache_hash函数【begin  = sel & m】计算出key值 k 对应的 index值
    // begin，用来记录查询起始索引
    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();//   _occupied ++;
            b[i].set<Atomic, Encoded>(sel, imp, cls);// 缓存实例方法：内存缓存了imp和sel
            return;
        }
        if (b[i].sel() == sel) {// 如果找到需要缓存的方法，不需要缓存，直接return
            // 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冲突 cache_next查找下一个 直到回到begin 全部查找结束

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

以上源码我加了一些注释，方便大家阅读，可以看出insert大致分为3步

初始化缓存空间

判断是否需要扩容，如果需要，以原始空间的2倍扩容，重新分配空间，释放已有缓存

判断散列表中是否已有该方法的缓存情况插入缓存或者return

我们再对申请内存的方法reallocate和其中涉及的hash算法做一下详细的讲解。

reallocate源码

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);//这里为了节省内存将bucket和mask放在一起
    
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);//释放老的
    }
}

allocateBuckets源码

bucket_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(cache_t::bytesForCapacity(newCapacity), 1);

    bucket_t *end = cache_t::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>((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>((SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    
    if (PrintCaches) recordNewCache(newCapacity);

    return newBuckets;
}

reallocate函数中通过allocateBuckets 函数的 calloc向系统申请 newCapacity大小的空间

通过 setBucketsAndMask 设置 buckets和 mask，其中 mask 更新为 新申请的总空间大小 - 1

hash算法

cache_hash源码

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

解释：
mask值始终为 capacity - 1，即3，7，15，31...，用二进制表示为 00000001，00000011，00000111，00001111，所以取任意值 & mask必定小于等于mask，这一步 sel & mask 的操作确保了begin 的值不会超过总容量-1，以确保遍历的时候下标不会超出 capacity ，出现越界的情况。

cache_next源码

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

解释：
当上一个hash算法冲突时：（将当前的哈希下标 +1） & mask，重新进行哈希计算，得到一个新的下标，继续遍历

疑问解答

在扩容的时候，我们释放了已有缓存，把原来的方法也释放掉了，又因为sel-imp的存储是通过哈希算法计算下标的，而hash取到的下标是随机的，并不是固定的。

这里也就解释了为什么_occupied = 2，_mask = 7，而不是我们想象的_occupied = 4，而且我们打印方法也只打印出了一个test3的疑问。

cache_t分析

前言

cache_t是什么？

LLDB调试验证

cache_t怎么存的？

疑问解答

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读