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;