前言：

在最近学习过程中我们知道一个类的结构的定义，以及一个对象的alloc的执行流程。初探底层的源码。经过最新开源的objc781我们知道，类的结构中重要的成员有

• Class ISA

• Class superclass

• cache_t cache

• class_data_bits_t bits

类的定义代码如下

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();
    }
     ......... //还包括很多数据和方法等

在之前的博客中我们曾对 isa、class_data_bits_t 已经进行了一个自我学习和总结的过程，接下来我们就针对类中很重要的cache_t再次深入进行一个自我学习和总结。希望通过这样的学习、帮助自己更深刻的理解类的缓存和工作原理。

一、cache_t 的环境结构

一个类的结构cache_t大致流程如下：截图来自Cooci老师的课件

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 constexpr uintptr_t maskShift = 48;

    static constexpr uintptr_t maskZeroBits = 4;

    static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;

    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;

    static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS, "Bucket field doesn't have enough bits for arbitrary pointers.");
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4

    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;

    static constexpr uintptr_t maskBits = 4;
    static constexpr uintptr_t maskMask = (1 << maskBits) - 1;
    static constexpr uintptr_t bucketsMask = ~maskMask;
#else
#error Unknown cache mask storage type.
#endif
    
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;

1在虚拟模拟器中的结构

当我们编译我们代码中的时候，相关的环境已经就确定了；所以我们能看到模拟器和macOS中的结构是

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
 explicit_atomic<struct bucket_t *> _buckets;
 explicit_atomic<mask_t> _mask;
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;

public:
    static bucket_t *emptyBuckets();
    
    struct bucket_t *buckets();
    mask_t mask();
    mask_t occupied();
    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    void initializeToEmpty();

    unsigned capacity();
    bool isConstantEmptyCache();
    bool canBeFreed();

再次进入_buckets 能看到 在模拟器和macOS中的结构

  explicit_atomic<SEL> _sel;
  explicit_atomic<uintptr_t> _imp;

2在真机调试中的结构

#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;

public:
    static bucket_t *emptyBuckets();
    
    struct bucket_t *buckets();
    mask_t mask();
    mask_t occupied();
    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    void initializeToEmpty();

    unsigned capacity();
    bool isConstantEmptyCache();
    bool canBeFreed();

再次进入_buckets 能看到 在模拟器和macOS中的结构

    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;

这就是cache_t在各个环境中的代码配置结构，编译器会自动根据环境进入到指定的代码进行编译和运行。非此环境下的代码我们想进入去查看是进不去，这就是编译器的智能体现。

二、cache_t的SEL本丢查看

我们都知道 对象调用方法都是通过编译器进行方法查找。而编译器会经常查找的方法进行缓存，下次进行方法查找的时候进行先进入缓存中查找，这样会大大节省时间，从而达到快速的作用，cache_t就是为此而生的。正好解决这个查找问题。
接下来我们分两种不同的环境进行调试和学习cache_t的内部_buckets,也就是sel 和imp,在iOS开发过程中，

• 1 源码环境下指令查看
• 2 脱离源码进行代码答应

1,源码环境下指令查看

首先我们创建一个类LGPerson集成自NSObject 如下

@interface LGPerson : NSObject
@property (nonatomic, copy) NSString *lgName;
@property (nonatomic, strong) NSString *nickName;

- (void)sayHello;

- (void)sayCode;

- (void)sayMaster;

- (void)sayNB;

+ (void)sayHappy;

@end

在接下来进行相关的指令调试步骤查看相应的cache_t

• 1 创建对象，获取对象的类，将断点断住相应的位置

  
  断点调试.png

• 2 在控制台进行打印类信息

p/x pClass

结果是：

(Class) $0 = 0x00000001000022a8 LGPerson

• 3 进行偏移 我们知道cache_t和类地址相差16位，正好是0x10 所以cache_t是0x00000001000022b8

• 4 打印cache_t指针信息；

p (cache_t *)0x00000001000022b8

结果是

(cache_t *) $1 = 0x00000001000022b8

• 5 取出相关cache_t的内容；

p *$1

结果是

(cache_t) $2 = {
_buckets = {
std::__1::atomic<bucket_t *> = 0x000000010032e430 {
_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
}

• 6 我们知道类的层级结构后，知道_buckets里边存储的类的sel 和 imp,从我们打印的结果知道，此处的_occupied = 0；也就是第一个断点的位置还没开始存储 sel ，不信我们继续；

p $2.buckets()

结果是：

(bucket_t *) $3 = 0x000000010032e430

• 7 取出buckets_t中的内容

p *$3

结果是

(bucket_t) $4 = {
_sel = {std::__1::atomic<objc_selector *> = (null}
_imp = {
std::__1::atomic<unsigned long> = 0
}
}

• 8 接下来我们过掉一个断点，执行第一个方法。再次打印结果；

  
  第二个断点调试.png

• 9 再次打印 cache_t中的内容

p *$1

结果是

(cache_t) $5 = {
_buckets = {
std::__1::atomic<bucket_t *> = 0x0000000100661c50 {
_sel = {
std::__1::atomic<objc_selector *> = ""
}
_imp = {
std::__1::atomic<unsigned long> = 10584
}
}
}
_mask = {
std::__1::atomic<unsigned int> = 7
}
_flags = 32804
_occupied = 1
}

• 10 我们此时看到 _occupied = 1 也就是缓存中存在了我们调用的方法了:[p sayHello]已经完美执行了，接下来我们再次验证；

p $5.buckets()

结构是

(bucket_t *) $6 = 0x0000000100661c50

• 11 取出bucket_t的内容；

p *$6

结果是

(bucket_t) $7 = {
_sel = {
std::__1::atomic<objc_selector *> = ""
}
_imp = {
std::__1::atomic<unsigned long> = 10584
}
}

• 12 取出sel

p $7.sel()

结果是

(SEL) $8 = "sayHello"

• 13 取出imp

p $7.imp(pClass)

结果是

(IMP) $9 = 0x0000000100000bf0 (KCObjc`-[LGPerson sayHello])

同理过掉第二个断点进入第三个，也可以进行相关的打印，_occupied = 2 用相关的指令也能打印相关内容；

2、脱离源码进行代码答应

从以文章开头介绍，cache_t,依靠系统的几部分内容

• 1 _buckets

typedef uint32_t mask_t;  // x86_64 & arm64 asm are less efficient with 16-bits

struct lg_bucket_t {
    SEL _sel;
    IMP _imp;
};

• 2 cache_t

struct lg_cache_t {
    struct lg_bucket_t * _buckets;
    mask_t _mask;
    uint16_t _flags;
    uint16_t _occupied;
};

• 3 class_data_bits_t

struct lg_class_data_bits_t {
    uintptr_t bits;
};

• 4 objc_class

struct lg_objc_class {
    Class ISA;
    Class superclass;
    struct lg_cache_t cache;             // formerly cache pointer and vtable
    struct lg_class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
};

• 5 接下来创建类，并调用相关的两个方法

        LGPerson *p  = [LGPerson alloc];
        Class pClass = [LGPerson class];  // objc_clas
        [p say1];
        [p say2];
//        [p say3];
//        [p say4];

• 6 配置打印结果代码

      struct lg_objc_class *lg_pClass = (__bridge struct lg_objc_class *)(pClass);
        NSLog(@"%hu - %u",lg_pClass->cache._occupied,lg_pClass->cache._mask);
        for (mask_t i = 0; i<lg_pClass->cache._mask; i++) {
            // 打印获取的 bucket
            struct lg_bucket_t bucket = lg_pClass->cache._buckets[i];
            NSLog(@"%@ - %p",NSStringFromSelector(bucket._sel),bucket._imp);
        }

• 7 打印结果是

  
  两个方法的打印结果.png

我们能看到 _occupied = 2 和 _mask = 3 以及相关的方法对应的实现 也就是 sel 和 imp;

• 8 我们把第4步的ISA 注释掉，打印的结果却是

  
  注释掉类的ISA打印结果.png

我们能看到 _occupied = 0 和 _mask = 5380272 未知情况

• 9 我们再次打印4个方法查看打印结果、[p say1]、[p say2]、[p say3]、[p say4]
  4个方法答应的结果图.png

我们能看到 _occupied = 2 和 _mask = 7,明确的知道mask 已经从原来的 3 变化到7,那么为什么打印的方法还是只有两个呢，这就是我们接下来研究的mask的机制和扩容的奥秘了。

三、cache_t 的buckets 和mask的机制探索

从上边的问题 mask 已经从原来的 3 变化到7，就是存在一个mask 的调整，那么mask 最大能到多少呢？

 explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;

    static constexpr uintptr_t maskShift = 48;
    static constexpr uintptr_t maskZeroBits = 4;
    static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;

• maskShift = 48
• maxMask = (1 << 16 ) - 1 = 2^16 -1

• bucketsMask = (1<<44) - 1 = 2^44 -1

  
  mask 变化前后图.png

四、cache_t下的sel存储机制

我们从objc781 开源代码能清楚的知道cache_t 的过程是

• 1 cache_fill
• 2 cache_t::insert
• 3 cache_create
• 4 bcopy
• 5 flush_caches
• 6 cache_flush
• 7 cache_collect_free

1 cache_fill

我们知道创建一个方法需要先走cache_fill,代码定义如下：

void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
    runtimeLock.assertLocked();
    if (cls->isInitialized()) {
        cache_t *cache = getCache(cls);
        cache->insert(cls, sel, imp, receiver);
    }

}

2 cache_t::insert (最核心)

代码定义如下

ALWAYS_INLINE
void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{


    // part1 计算相关的occupied
    mask_t newOccupied = occupied() + 1;
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
   // part2 判断如果是创建 进行初始化
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE;
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
//part3 判断是否需要扩容
    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.
    }
//part4 扩容操作；
    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;

    //part5;进行相关的方法存储
    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);
}

首先将代码的定义分配为5部分；代码里已经注释的很清楚了

part1 计算相关的新的newOccupied

    mask_t newOccupied = occupied() + 1;

part2.判读第一次进行初始化操作

• 1 计算新值

if (!capacity) capacity = INIT_CACHE_SIZE;
        reallocate(oldCapacity, capacity, /* freeOld */false);

• 2 INIT_CACHE_SIZE 的定义如下

INIT_CACHE_SIZE_LOG2 = 2,
INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2),

也就是1 << 2,就是4.也就是说默认进来分配4的内存空间；

• 3 再进行setBucketsAndMask

 setBucketsAndMask(newBuckets, newCapacity - 1);

具体函数就是

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{

#ifdef __arm__
    mega_barrier();
    _buckets.store(newBuckets, memory_order::memory_order_relaxed);
    mega_barrier();
    _mask.store(newMask, memory_order::memory_order_relaxed);
    _occupied = 0;
#elif __x86_64__ || i386
    _buckets.store(newBuckets, memory_order::memory_order_release);
    _mask.store(newMask, memory_order::memory_order_release);
    _occupied = 0;
#else

也即是向内存中存储相关的sel操作；再次把_occupied = 0 ;也就是不占用任何空间，也就是初始化的的操作，只是一个空壳子，不存在实质性的操作；

• 4 如果旧的值存在，则全部释放cache_collect_free

static void cache_collect_free(bucket_t *data, mask_t capacity)
{
    if (PrintCaches) recordDeadCache(capacity);
    _garbage_make_room ();
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    garbage_refs[garbage_count++] = data;
    cache_collect(false);
}

part3 如果新的值小于或等于原来的3/4，不做任何处理；

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

part4.超过原来的3/4，进行内存扩容；

     capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 扩容两倍 4
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);  // 内存 库容完毕

也就是将原来的内存扩容到当前的2倍；然后始终保持mask_t m = capacity - 1;这也就是为什么之前我们打印的mask从3变化到7的原因；

因为我们原来的内存大小是4，因为同时执行了4个方法，存储已经超过了原来的3/4,所以扩容到8.而根据mask_t m = capacity - 1;，所以原来的是 mask = 4- 1 = 3, 而新的mask = 8- 1 = 7

part5方法的存储机制

• 1 在iOS开发中我们很多数据结构存储都是以快速为主，例如字典,内存映射等，其目的都是为了快速的查找想要的到的内容。同理。cache_t 也不例外，其存储的代码如下

 mask_t begin = cache_hash(sel, m);
   mask_t i = begin;

• 2 查看· cache_hash的内部结构

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

• 3 通过上面的cache_hash 和mask 进行相关的与操作。我们都知道任何方法在内存中都存在一个方法编号，用这个方法编号进行与操作，就能准确的得到这个方法在cache中的索引；

• 4 如果得到的索引存在冲突，则继续处理hash 冲突；

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中就能有并且存储是一个唯一的索引，通过查找方法我们就能快速的查找到；

五、总结

通过将近5个小时的整理和断点调试，终于写完这次的内容，虽然内容过于简单，但是还是自己实现了一遍流程，也算是一种收获吧，希望以后再接再厉。继续努力；如果大神们有什么好的建议请不吝赐教。谢谢。