iOS类结构：cache_t分析

一、cache_t 内部结构分析

1.1 在iOS类的结构分析中，我们已经分析过类（Class）的本质是一个结构体 ，结构体内部结构如下 :

typedef struct objc_class *Class;
typedef struct objc_object *id;

struct objc_class : objc_object {
    // Class ISA;
    Class superclass;
    cache_t cache;             // formerly cache pointer and vtable
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
    class_rw_t *data() const {
        return bits.data();
    }
    ...
}
  • Class ISA ：指向关联类 , 继承自 objc_object 。 参考 isa底层结构分析
  • Class superclass：父类指针 , 同样参考上述文章中有详细指向探索。
  • cache_t cache , 方法缓存存储数据结构。
  • class_data_bits_t bits , bit 中存储了属性，方法等类的源数据。

1.2 在iOS类的结构分析中，我们已经分析过 cache_t 结构体，分为以下四个部分:

struct cache_t {
    struct bucket_t * _buckets; // 缓存数组，即哈希桶
    mask_t _mask; // 缓存数组的容量临界值,实际上是为了 capacity 服务
    uint16_t _flags; // 位置标记
    uint16_t _occupied; // 缓存数组中已缓存方法数量
    ...省略
}
  • _buckets：是 bucket_t 结构体的数组，bucket_t 是用来存放方法编号 SEL 和函数指针 IMP 的。
struct bucket_t {
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
}
  • _mask: mask_t m = capacity - 1; (capacity = MAX_CACHE_SIZE;)，用作掩码。因为这里缓存 Cache 的容量 Size 一直是2倍扩容的，所以 MAX_CACHE_SIZE 是2的整数次幂，所以 mask 的二进制位 000011, 000111, 001111 ）刚好可以用作 Hash取余数的掩码。刚好保证相与后不超过缓存大小。
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 扩容至两倍
  • _flags: 位置标记
  • _occupied是当前已缓存的方法数量。即数组中已使用了多少位置。

二、方法缓存原理探索

源码如下：

@interface LGPerson : NSObject

- (void)sayHello;

- (void)sayCode;

- (void)sayMaster;

- (void)sayNB;

+ (void)sayHappy;

@end
#import "LGPerson.h"

@implementation LGPerson
- (void)sayHello{
    NSLog(@"LGPerson say : %s",__func__);
}

- (void)sayCode{
    NSLog(@"LGPerson say : %s",__func__);
}

- (void)sayMaster{
    NSLog(@"LGPerson say : %s",__func__);
}

- (void)sayNB{
    NSLog(@"LGPerson say : %s",__func__);
}

+ (void)sayHappy{
    NSLog(@"LGPerson say : %s",__func__);
}
@end

#import <Foundation/Foundation.h>
#import "LGPerson.h"
#import <objc/runtime.h>


// cache_t
int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        LGPerson *p  = [LGPerson alloc];
        Class pClass = [LGPerson class];

        [p sayHello];
        [p sayCode];
        [p sayMaster];
        [p sayNB];

        NSLog(@"%@",pClass);
    }
    return 0;
}

2.1 我们再sayHello方法前设置断点，LLDB调试 其中的 cache_t 的数据

因为在类结构体中 cache_t 前面有 Class ISA指针 和 Class superclass 父类指针 ，所以要偏移16位。

(lldb) p/x pClass
(Class) $0 = 0x00000001000022a0 LGPerson
(lldb) p (cache_t *)0x00000001000022b0
(cache_t *) $1 = 0x00000001000022b0
(lldb) p *$1
(cache_t) $2 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x000000010032e420 {
      _sel = {
        std::__1::atomic<objc_selector *> = (null)
      }
      _imp = {
        std::__1::atomic<unsigned long> = 0
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 0
  }
  _flags = 32804
  _occupied = 0
}

2.2 然后执行一步 sayHello 方法，再次进行 LLDB调试 ，查看 cache_t 的数据

2020-09-17 22:37:33.187060+0800 KCObjc[34953:549295] LGPerson say : -[LGPerson sayHello]
(lldb) p *$1
(cache_t) $3 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x00000001006ad5f0 {
      _sel = {
        std::__1::atomic<objc_selector *> = ""
      }
      _imp = {
        std::__1::atomic<unsigned long> = 11936
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 3
  }
  _flags = 32804
  _occupied = 1
}

2.3 走到这里，大家应该发现 _buckets 、_mask 、_occupied 的变化了。其中_occupied 从0变为1，也证明了执行完 sayHello 方法 之后，缓存方法数量 + 1 。接下来我们查看一下哈希桶 _buckets 的变化，哈希桶数据类型 struct bucket_t 我们点进去查看如下：

struct bucket_t {
public:
    inline SEL sel() const { return _sel.load(memory_order::memory_order_relaxed); }

    inline IMP imp(Class cls) const {
        uintptr_t imp = _imp.load(memory_order::memory_order_relaxed);
        if (!imp) return nil;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
        SEL sel = _sel.load(memory_order::memory_order_relaxed);
        return (IMP)
            ptrauth_auth_and_resign((const void *)imp,
                                    ptrauth_key_process_dependent_code,
                                    modifierForSEL(sel, cls),
                                    ptrauth_key_function_pointer, 0);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
        return (IMP)(imp ^ (uintptr_t)cls);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
        return (IMP)imp;
#else
#error Unknown method cache IMP encoding.
#endif
    }
}

我们就可以查看 _buckets 的 SEL 和 IMP 信息。

(lldb) p $3.buckets()
(bucket_t *) $4 = 0x00000001006ad5f0
(lldb) p *$4
(bucket_t) $5 = {
  _sel = {
    std::__1::atomic<objc_selector *> = ""
  }
  _imp = {
    std::__1::atomic<unsigned long> = 11936
  }
}
(lldb) p $5.sel()
(SEL) $6 = "sayHello"
(lldb) p $5.imp(pClass)
(IMP) $7 = 0x0000000100000c00 (KCObjc`-[LGPerson sayHello])

然后我们也可以打开 MachOView 查看一下 sayHello 方法的 IMP 指针

MachOView

与我们 LLDB调试 结果不谋而合，完美~

2.4 接下来我们继续执行 sayMaster 方法 和 sayNB 方法 ，进行 LLDB调试 ，查看 cache_t 的数据

2020-09-17 23:12:37.095330+0800 KCObjc[34953:549295] LGPerson say : -[LGPerson sayCode]
(lldb) p *$1
(cache_t) $8 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x00000001006ad5f0 {
      _sel = {
        std::__1::atomic<objc_selector *> = ""
      }
      _imp = {
        std::__1::atomic<unsigned long> = 11936
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 3
  }
  _flags = 32804
  _occupied = 2
}
2020-09-17 23:12:59.163825+0800 KCObjc[34953:549295] LGPerson say : -[LGPerson sayMaster]
(lldb) p *$1
(cache_t) $9 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x0000000103b4c7d0 {
      _sel = {
        std::__1::atomic<objc_selector *> = (null)
      }
      _imp = {
        std::__1::atomic<unsigned long> = 0
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 7
  }
  _flags = 32804
  _occupied = 1
}

走到这里，我们发现：
问题①. _occupied 由 2 变为了 1 ，缓存方法数量 _occupied 为什么会减少呢？
问题②. _mask 由 3 变为了 7 ，至于 _mask 的变化，大家可以能想到，前面我们讲过， _mask 是受缓存容量 CACHE SIZE 2 倍扩容的影响。缓存容量 CACHE SIZE 由 4 变为了 8 。
问题③. _buckets 里面的 SEL 和 IMP 消失了。

2.5 接下来，我们来一探究竟。在 void incrementOccupied(); 方法中我们看到了 _occupied++; 。

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

2.6 然后我们在源码中找一下，什么地方执行了 incrementOccupied(); 这个方法。惊喜来了，cache_t::insert() 方法中执行了 incrementOccupied(); 这个方法。从名称我们就可以发现，这是向缓存插入的方法。

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

2.6.1 接下来我们分析一下这个小概率事件 -> 初始化方法：
如果缓存为空，则开辟缓存 INIT_CACHE_SIZE ：4。然后利用 reallocate() 方法 开辟空间。

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),
};

if (slowpath(isConstantEmptyCache())) { // 小概率事件 -> 初始化方法
    // Cache is read-only. Replace it.
    if (!capacity) capacity = INIT_CACHE_SIZE; // 4 (枚举定义：1 左移 2 位)
    reallocate(oldCapacity, capacity, /* freeOld */false);
}

reallocate() 方法

  1. 申请 newCapacity 大小的地址
  2. 调用 setBucketsAndMask() 方法 初始化 bucket 
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);
    }
}

setBucketsAndMask() 方法

  1. 将 旧bucket 存入 新bucket
  2. 将 _occupied = 0，这里我们留意到了 reallocate() 方法 会将 _occupied = 0。
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();

    _buckets.store(newBuckets, memory_order::memory_order_relaxed);
    
    // ensure other threads see new buckets before new mask
    mega_barrier();
    
    _mask.store(newMask, memory_order::memory_order_relaxed);
    _occupied = 0;
#elif __x86_64__ || i386
    // ensure other threads see buckets contents before buckets pointer
    _buckets.store(newBuckets, memory_order::memory_order_release);
    
    // ensure other threads see new buckets before new mask
    _mask.store(newMask, memory_order::memory_order_release);
    _occupied = 0;
#else
#error Don't know how to do setBucketsAndMask on this architecture.
#endif
}

2.6.2 接下来就是大概率事件方法

如果缓存 newOccupied + CACHE_END_MARKER（1） < capacity / 4 * 3，则什么都不需要做。

#define CACHE_END_MARKER 1

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.
}

2.6.3 接下来就是扩容方法

  • 如果大于总容量的 3 / 4 的时候，就需要扩容了（扩容至2倍）。
  • 扩容之后仍然需要利用 reallocate() 方法 开辟空间，在 2.6.1 的
    setBucketsAndMask() 方法 中我们讲过， reallocate() 方法 会将 _occupied = 0。到这，我们终于理解了2.4 当中的 问题② ，为什么 _occupied 会减少，因为扩容之后 _occupied 会初始化至 0，重新计算。
else {
    capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 扩容至两倍 4
    if (capacity > MAX_CACHE_SIZE) {
        capacity = MAX_CACHE_SIZE;
    }
    reallocate(oldCapacity, capacity, true);  // 内存 扩容完毕
}

2.6.4 reallocate() 方法

  • 调用 setBucketsAndMask() 方法 初始化 bucket ，因为 bucket 受扩容影响重新初始化了，所以2.4 当中的 问题③ 的原因就在这里。
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);
    }
}

2.6.5 接下来就是 _mask 变化的方法，在2.6.3 中我们知道容量扩容到 2 倍，那么 mask 的值就是 2 的 n次幂 - 1 , 所以 2.4 当中的 问题① 便迎刃而解了。

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