iOS 底层原理 - cache_t分析

cache_t 的基本结构

上之前类的结构分析一篇中，我们知道类的结构为：

struct objc_class : objc_object {
    // Class ISA; // 8
    Class superclass; // 8
    cache_t cache;    // 16 不是8         // formerly cache pointer and vtable
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags

    class_rw_t *data() { 
        return bits.data();
    }

    ...省略其他的信息...

也明白了bits，ISA以及superclass，今天来看一下剩下的cache。先看一下cache的结构：

struct cache_t {
    struct bucket_t *_buckets;  //8
    mask_t _mask;    //4
    mask_t _occupied;   //4

再看一下里面的成员_buckets的结构：

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

从源码定义中不难看出，bucket_t 其实缓存的是方法实现 IMP。这里有一个注意点，就是 IMP-first 和 SEL-first。IMP-first 对 arm64e 的效果更好，对 arm64 不会有坏的影响。SEL-first 适用于 armv7 * 和 i386 和 x86_64。说道方法实现，我们再看一下method_t，他的结构为：

struct method_t {
    SEL name;
    const char *types;
    MethodListIMP imp;

    struct SortBySELAddress :
        public std::binary_function<const method_t&,
                                    const method_t&, bool>
    {
        bool operator() (const method_t& lhs,
                         const method_t& rhs)
        { return lhs.name < rhs.name; }
    };
};

分析方法的缓存流程

我们先通过LLVM来进行一个验证，还是在我们的源码工程下，新建一个类LGPerson，执行以下代码：

LGPerson *person = [[LGPerson alloc] init];
        Class pClass = [LGPerson class];
        [person sayHello];
        [person sayCode];
        [person sayNB];

如下图所示加两个断点，运行代码


屏幕快照 2020-02-16 下午5.49.22.png

在第一个断点处，在lldb调试台上，打印一下bucket的内容

(lldb) x pClass
0x1000012a8: 81 12 00 00 01 80 1d 00 40 d1 af 00 01 00 00 00  ........@.......
0x1000012b8: 40 02 9b 02 01 00 00 00 03 00 00 00 01 00 00 00  @...............
(lldb) p (cache_t*)0x1000012b8
(cache_t *) $1 = 0x00000001000012b8
(lldb) p *$1
(cache_t) $2 = {
  _buckets = 0x00000001029b0240
  _mask = 3
  _occupied = 1
}
(lldb) p $2._buckets
(bucket_t *) $3 = 0x00000001029b0240
(lldb) p *$3
(bucket_t) $4 = {
  _key = 0
  _imp = 0x0000000000000000
}

在第二个断点处，再打印一下bucket的内容

2020-02-16 17:47:17.556182+0800 LGTest[61334:2665351] LGPerson say : -[LGPerson sayHello]
2020-02-16 17:47:17.558324+0800 LGTest[61334:2665351] LGPerson say : -[LGPerson sayCode]
2020-02-16 17:47:17.558976+0800 LGTest[61334:2665351] LGPerson say : -[LGPerson sayNB]
(lldb) x pClass
0x1000012a8: 81 12 00 00 01 80 1d 00 40 d1 af 00 01 00 00 00  ........@.......
0x1000012b8: 90 02 9b 02 01 00 00 00 07 00 00 00 01 00 00 00  ................
(lldb) p (cache_t*)0x1000012b8
(cache_t *) $6 = 0x00000001000012b8
(lldb) p *$6
(cache_t) $7 = {
  _buckets = 0x00000001029b0290
  _mask = 7
  _occupied = 1
}
(lldb) p $7._buckets
(bucket_t *) $8 = 0x00000001029b0290
(lldb) p *$8
(bucket_t) $9 = {
  _key = 0
  _imp = 0x0000000000000000
}

我们依次调用了 init，sayHello，sayCode，sayNB一共4个实例方法，按照我们的猜测，cache中应该缓存了他们4个方法，我们下面打印输出看了一下，结果发现mask的值从3增加到了7。说明cache的缓存并不是无脑的，肯定是在某个条件达成时，进行了一些优化。
我们回归源码继续分析，找到 mask_t mask();方法，发现只是返回了本身

mask_t cache_t::mask() 
{
    return _mask; 
}

继续搜索mask()，发现在capacity方法中有mask的相应操作

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

然后依据capacity()在扩容方法expand方法内部看到了capacity方法的调用，意思是，如果oldCapacity获取的值为0，那么就用INIT_CACHE_SIZE（1<<2 实际为4）来初始化，如果存在，那么就用oldCapacity的2倍来作为newCapacity，扩容的逻辑也就如下所示：

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    
    uint32_t oldCapacity = capacity();
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;

    if ((uint32_t)(mask_t)newCapacity != newCapacity) {
        // mask overflow - can't grow further
        // fixme this wastes one bit of mask
        newCapacity = oldCapacity;
    }

    reallocate(oldCapacity, newCapacity);
}

从上述分析中看到 最后调用 reallocate 方法进行缓存大小的重置，这里重置是为了避免后续缓存太多，读取缓存浪费时间，不符合快的有点，那继续看下这里面的实现：

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
    bool freeOld = canBeFreed();

    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);
        cache_collect(false);
    }
}

显然，_mask 是这一步 setBucketsAndMask(newBuckets, newCapacity - 1); 被赋值为容量减 1 的。

cache_t 缓存流程

在源码中搜索 capacity() 方法，我们找到了 cache_fill_nolock 方法，也就是缓存入口，而cache_fill_nolock的调用是在cache_fill()函数，cache_fill()又是在lookUpImpOrForward和lookupMethodInClassAndLoadCache方法里调用的，因此我们可以想到是在消息发送objc_msgSend的时候调用了方法缓存。

static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
    cacheUpdateLock.assertLocked();

    // Never cache before +initialize is done
    //没有初始化的类直接return
    if (!cls->isInitialized()) return;

    // Make sure the entry wasn't added to the cache by some other thread 
    // before we grabbed the cacheUpdateLock.
    ////可以获取到方法imp，直接return
    if (cache_getImp(cls, sel)) return;

    //获取类的缓存内容
    cache_t *cache = getCache(cls);
    //生成(获取)该方法缓存key，因为name难以读取，数字更直接
    cache_key_t key = getKey(sel);

    // Use the cache as-is if it is less than 3/4 full
    //已占用的 + 1
    mask_t newOccupied = cache->occupied() + 1;
    //获取缓存总容量
    mask_t capacity = cache->capacity();
    //判断是否有缓存过内容
    if (cache->isConstantEmptyCache()) {
        // Cache is read-only. Replace it.
        //没有缓存过内容，重新开辟空间，最少4字节
        cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
    }
    else if (newOccupied <= capacity / 4 * 3) {
        // Cache is less than 3/4 full. Use it as-is.
    }
//调用新方法之后，占用总内存时候大于总容量的四分之三
    else {
        // Cache is too full. Expand it.
        //大于总容量的四分之三，那就扩容
        cache->expand();
    }

    // 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.
    //把新方法添加到缓存内（不管有没有扩容，都要把新调用的方法添加到缓存中）
    bucket_t *bucket = cache->find(key, receiver);
    if (bucket->key() == 0) cache->incrementOccupied();
    //key和imp绑定
    bucket->set(key, imp);
}

从上面的源码可以看出cache是空的，就需要reallocte。如果新的缓存占用大小 小于等于 缓存容量的四分之三，则可以进行缓存流程，如果大于3/4，就需要expand()即缓存扩容。

bucket_t *bucket = cache->find(key, receiver);
    if (bucket->key() == 0) cache->incrementOccupied();
    bucket->set(key, imp);

通过前面生成的 key 在缓存中查找对应的 bucket_t，也就是对应的方法实现。判断获取到的桶 bucket 是否是新的桶，如果是的话，就在缓存里面增加一个占用大小。然后把 key 和 imp 放到桶里面。
然后我们再看一下里面的find方法

bucket_t * cache_t::find(cache_key_t k, id receiver)
{
    assert(k != 0);

    bucket_t *b = buckets();
    mask_t m = mask();
    // 通过cache_hash函数【begin  = k & m】计算出key值 k 对应的 index值 begin，用来记录查询起始索引
    mask_t begin = cache_hash(k, m);
    // begin 赋值给 i，用于切换索引
    mask_t i = begin;
    do {
        if (b[i].key() == 0  ||  b[i].key() == k) {
            //用这个i从散列表取值，如果取出来的bucket_t的 key = k，则查询成功，返回该bucket_t，
            //如果key = 0，说明在索引i的位置上还没有缓存过方法，同样需要返回该bucket_t，用于中止缓存查询。
            return &b[i];
        }
    } while ((i = cache_next(i, m)) != begin);
    
    // 这一步其实相当于 i = i-1,回到上面do循环里面，相当于查找散列表上一个单元格里面的元素，再次进行key值 k的比较，
    //当i=0时，也就i指向散列表最首个元素索引的时候重新将mask赋值给i，使其指向散列表最后一个元素，重新开始反向遍历散列表，
    //其实就相当于绕圈，把散列表头尾连起来，不就是一个圈嘛，从begin值开始，递减索引值，当走过一圈之后，必然会重新回到begin值，
    //如果此时还没有找到key对应的bucket_t，或者是空的bucket_t，则循环结束，说明查找失败，调用bad_cache方法。
 
    // hack
    Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
    cache_t::bad_cache(receiver, (SEL)k, cls);
}

整个 cache_t 的工作流程，简略描述如下：

当前查找的 IMP 没有被缓存，调用 cache_fill_nolock 方法进行填充缓存。
当前查找的 IMP 已经被缓存了，然后判断缓存容量是否已经达到 3/4 的临界点

如果已经到了临界点，则需要进行扩容，扩容大小为原来缓存大小的 2 倍。扩容后处于效率的考虑，会清空之前的内容，然后把当前要查找的 IMP 通过 cache_fill_nolock 方法缓存起来。
如果没有到临界点，那么直接返回找到的 IMP。

最后再补充一点：

类的方法缓存是通过hash表存储的。
OC 中实例方法缓存在类上面，类方法缓存在元类上面。
cache_t 缓存会提前进行扩容防止溢出。
方法缓存是为了最大化的提高程序的执行效率

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