cache_t分析

前言

在之前的文章中，我们剖析了类的结构，今天我们来分析一下类结构中一个非常重要的结构体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的疑问。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 217,826评论 6赞 506
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,968评论 3赞 395
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 164,234评论 0赞 354
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,562评论 1赞 293
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,611评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,482评论 1赞 302
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,271评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,166评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,608评论 1赞 314
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,814评论 3赞 336
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,926评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,644评论 5赞 346
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,249评论 3赞 329
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,866评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,991评论 1赞 269
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,063评论 3赞 370
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,871评论 2赞 354