Cache_t的结构和原理

在之间的文章里我们分析了isa的指向和结构isa结构分析，分析了bits类的结构分析,在这篇文章里，我们来分析objc_class里面的cache

cache1.png

Cache_t的结构

我们先看下在x86（模拟器）环境下， cache_t的结构

struct cache_t {
    explicit_atomic<struct bucket_t *> _buckets;
    explicit_atomic<mask_t> _mask;
}
struct bucket_t {
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
}

分析

首先我们先创建一个实例对象person，并且查看其类对象的内存地址

 LYPerson *p = [[LYPerson alloc] init];
[p sayMaster];

(lldb) p/x p.class
(Class)  $0 = 0x00000001000022a0 LYPerson

从objc_class的结构我们可以分析得出，cache_t位于其内存偏移 16 字节的位置，根据类对象的首地址和其内存偏移，我们可以得到cache对象

(lldb) p/x 0x00000001000022a0 + 0x10
(long) $1 = 0x00000001000022b0
(lldb) p (cache_t *)0x00000001000022b0
(cache_t *) $2 = 0x00000001000022b0
(lldb) p *$2
(cache_t) $4 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x0000000101a38990 {
      _sel = {
        std::__1::atomic<objc_selector *> = 0x0000000000000000
      }
      _imp = {
        std::__1::atomic<unsigned long> = 0
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 7
  }
  _flags = 32804
  _occupied = 1
}

接下来，让我们来看看Cache_t里面的bucket存放的是什么？通过源码中的buckets()方法，我们可以获取bucket

(lldb) p $4.buckets()
(bucket_t *) $5 = 0x0000000101a38990
(lldb) p *$5
(bucket_t) $7 = {
  _sel = {
    std::__1::atomic<objc_selector *> = 0x0000000000000000
  }
  _imp = {
    std::__1::atomic<unsigned long> = 0
  }
}

通过lldb，我们验证了，bucket由两部分组成，一个是_sel，一个是_imp,下一步我们要做的就是读取bucket里面的 _sel和_imp的值。

(lldb) p $4.buckets()[0].sel()
(SEL) $9 = <no value available>
(lldb) p $4.buckets()[1].sel()
(SEL) $10 = <no value available>
(lldb) p $4.buckets()[2].sel()
(SEL) $11 = <no value available>
(lldb) p $4.buckets()[3].sel()
(SEL) $12 = <no value available>
(lldb) p $4.buckets()[4].sel()
(SEL) $13 = <no value available>
(lldb) p $4.buckets()[5].sel()
(SEL) $14 = "sayMaster"

(lldb) p $4.buckets()[5].imp(pClass)
(IMP) $32 = 0x0000000100000c60 (KCObjc`-[LYPerson sayMaster])

我们可以看出，bucket里面存放的是已经调用过的sel和imp。

Cache_t脱离源码环境分析

接下来，我们仿造Cache_t的结构，脱离源码环境进行探索：

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

struct lg_bucket_t {
    SEL _sel;
    IMP _imp;
};

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

struct lg_class_data_bits_t {
    uintptr_t bits;
};

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

我们来看以下输出

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

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

输出结果

2020-09-19 19:26:30.862600+0800 003-cache_t[19867:3905733] LGPerson say : -[LGPerson say1]
2020-09-19 19:26:30.863308+0800 003-cache_t[19867:3905733] LGPerson say : -[LGPerson say2]
2020-09-19 19:26:30.863393+0800 003-cache_t[19867:3905733] LGPerson say : -[LGPerson say3]
2020-09-19 19:26:30.863483+0800 003-cache_t[19867:3905733] LGPerson say : -[LGPerson say4]
2020-09-19 19:26:30.863530+0800 003-cache_t[19867:3905733] 2 - 7
2020-09-19 19:26:30.863667+0800 003-cache_t[19867:3905733] say4 - 0x29a8
2020-09-19 19:26:30.863716+0800 003-cache_t[19867:3905733] (null) - 0x0
2020-09-19 19:26:30.863785+0800 003-cache_t[19867:3905733] say3 - 0x29d8
2020-09-19 19:26:30.863829+0800 003-cache_t[19867:3905733] (null) - 0x0
2020-09-19 19:26:30.863870+0800 003-cache_t[19867:3905733] (null) - 0x0
2020-09-19 19:26:30.863909+0800 003-cache_t[19867:3905733] (null) - 0x0
2020-09-19 19:26:30.863992+0800 003-cache_t[19867:3905733] (null) - 0x0

从上面我可以看出，我们调用了 4个函数方法，但在 buckets里面只存储了2个方法，并且顺序有点问题，并不是按照调用顺序进行存放的。我们带着以下问题在继续探讨：

1，_occupied, _mask 是什么？
2，为什么存放bucket的顺序是乱序？
3，为什么调用的sel和imp没有全部存起来？

Cache_t的实现原理

当对象调用函数时，_occupied的值会发生变化，我们以此为突破口，在cache_t中发现incrementOccupied方法。然后，查看什么时候调用该函数。
在 void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)方法中调用了该函数。

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
    mask_t newOccupied = occupied() + 1;  // 1
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE; // 2
        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 {
        // 扩容两倍 4
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE; // 3
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        // 内存 库容完毕
        reallocate(oldCapacity, capacity, true); // 4
    }

    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    mask_t begin = cache_hash(sel, m); // 5
    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)) { // 6
            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)); // 7

    cache_t::bad_cache(receiver, (SEL)sel, cls);
}

1，获取新的已占用的值。
2，设置容量的初始值为 4（INIT_CACHE_SIZE == 4）。
3，如果 已占用的空间小于整个空间大小的3/4,则对容量进行2倍扩容。
4，扩容只会重新申请空间，对之前的数据并没有进行复制。
5，将sel与mask(capacity - 1)进行与运算，得到小于capacity的索引值i。
6，如果buckets[i]处，没有存放bucket，则将其放到i处。
7，如果buckets[i]处，已经存放了bucket，那么说明发生了哈希冲突，则使用开放地址法，从尾部开始查找空桶，将其放入空桶中。

通过以上分析我们可以得出问题的答案了。

1，_occupied:表示当前 buckets()里面的bucket数量。_mask等于buckets的容量 - 1。
2，bucket存放的位置是由sel的哈希值&capacity - 1决定的，与方法的调用顺序无关，所以是无序的。
3，当buckets的_occupied> capacity * 3/4时，buckets会进行扩容，会对buckets进行重新开辟内存，导致之前存放的bucket会丢失。

总结

在这篇文章里，我们先分析了 cache_t的结构，紧接着，我们脱离源码来分析cache_t，最后一部分，我们结合源码分析了cache_t实现的原理。