数据类型

在过去的版本,cache_t是这样的

struct cache_t {
    struct bucket_t *_buckets;
    mask_t _mask; 
    mask_t _occupied;
public:
    struct bucket_t *buckets();

而最近的版本增加了很多类型安全性和适配性的代码和设计,看起来比较麻烦

struct cache_t {
private:
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask;
    union {
        struct {
            explicit_atomic<mask_t>    _maybeMask;
#if __LP64__
            uint16_t                   _flags;
#endif
            uint16_t                   _occupied;
        };
        explicit_atomic<preopt_cache_t *> _originalPreoptCache;
    };

但是基本的代码逻辑还是没变的,所以打算新旧结合起来看.
随着版本的更迭,我发现对于学习源码的人来说,成员变量变得越来越边缘,关键在于成员函数,
旧版本的数据结构非常直白,而较新的版本都是通过函数来操作成员变量,比如objc_class里的bits,methods,safe_ro等等,
从函数能够更清晰的看出这个数据结构的行为.

typedef uint32_t mask_t; 

其中mask_t是4字节,uintptr_t相当于long或者可以认为等于指针的大小,是8字节.
所以,旧版本是8+4+4=16字节;
新版是explicit_atomic<uintptr_t>(8字节) + union(8字节) = 16字节;
新旧是一样的大小,

//较新的版本
struct bucket_t *cache_t::buckets() const
{
    uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return (bucket_t *)(addr & bucketsMask);
}

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    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 <= cache_fill_ratio(capacity))) {
        // Cache is less than 3/4 or 7/8 full. Use it as-is.
    }
    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;
    do {
        if (fastpath(b[i].sel() == 0)) {
            incrementOccupied();
            b[i].set<Atomic, Encoded>(b, 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));
    bad_cache(receiver, (SEL)sel);
}

//较旧的版本
struct bucket_t *cache_t::buckets() 
{
    return _buckets; 
}

static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
    cache_t *cache = getCache(cls);
    cache_key_t key = getKey(sel);
    mask_t newOccupied = cache->occupied() + 1;
    mask_t capacity = cache->capacity();
    if (cache->isConstantEmptyCache()) {
        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();
    }
    bucket_t *bucket = cache->find(key, receiver);
    if (bucket->key() == 0) cache->incrementOccupied();
    bucket->set(key, imp);
}

再来看看函数,各贴了两个函数,一个是获取bucket,一个是插入cache.各自的实现不同,但是目的是相同的.
似乎从总体设计上来说,objc4没有大的变化,旨在通过重写设计局部数据结构和函数,来实现更强的适用性和健壮性.

struct cache_t {
    mask_t mask() const;
    mask_t occupied() const;
    Class cls() const;
    struct bucket_t *buckets() const;
    unsigned capacity() const;
    void insert(SEL sel, IMP imp, id receiver);
    bool isConstantEmptyCache() const;
    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    static bucket_t *allocateBuckets(mask_t newCapacity);
    void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld);
    void collect_free(bucket_t *oldBuckets, mask_t oldCapacity);
    static bucket_t *emptyBucketsForCapacity(mask_t capacity, bool allocate = true);

cache_t大概有这些关键函数.
既然是缓存,那就有预设的空间,capacity()表示当前的空间,这里指的是可以存几个bucket.
occupied()表示已经占用的空间,和capacity()同理.
buckets()返回的是一个struct bucket_t *,这样它就可以被作为一个bucket_t的数组,通过下标访问.
insert()是添加bucket的函数.
isConstantEmptyCache()表示当前缓存是否为空,也就是occupied为0的时候.
incrementOccupied()里面的实现就是_occupied++.
setBucketsAndMask()用于适配不同的架构,设置_bucketsAndMaybeMask.
allocateBuckets(),reallocate(),collect_free()结合,用于开启新的内存,释放旧内存.
emptyBucketsForCapacity()创建一个空的指定大小的buckets.

struct bucket_t {
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
    inline SEL sel()
     inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls)
    void set(bucket_t *base, SEL newSel, IMP newImp, Class cls);

bucket_t大概就是这些内容,一个SEL,一个IMP,以及存取函数.

添加缓存

接下来就是编译objc4,看看void cache_t::insert(SEL sel, IMP imp, id receiver)每一步都干了什么.

@interface MyClass : NSObject
- (int)instanceMethod:(int)a;
@end

//main.m
id myObj = [MyClass alloc];
MyClass *my = (MyClass *)[myObj init];
[my instanceMethod:9];

在init断点,到达断点的时候,在insert里添加第二个断点.然后前往这个断点.
然后可以看到sel是"init".

先看几个相关的定义

#if __arm__  ||  __x86_64__  ||  __i386__
#define CACHE_END_MARKER 1
static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 3 / 4;
}
#elif __arm64__ && !__LP64__
#define CACHE_END_MARKER 0
static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 3 / 4;
}
#elif __arm64__ && __LP64__
#define CACHE_END_MARKER 0
static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 7 / 8;
}
#define CACHE_ALLOW_FULL_UTILIZATION 1
#else
#error unknown architecture
#endif
enum {
#if CACHE_END_MARKER || (__arm64__ && !__LP64__)
    INIT_CACHE_SIZE_LOG2 = 2,
#else
    INIT_CACHE_SIZE_LOG2 = 1,
#endif
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2),
    MAX_CACHE_SIZE_LOG2  = 16,
    MAX_CACHE_SIZE       = (1 << MAX_CACHE_SIZE_LOG2),
    FULL_UTILIZATION_CACHE_SIZE_LOG2 = 3,
    FULL_UTILIZATION_CACHE_SIZE = (1 << FULL_UTILIZATION_CACHE_SIZE_LOG2),
};

一是函数cache_fill_ratio,传进去一个容量安装一定比例返回一个容量最大值,在64位arm是7/8,其他是3/4.
二是CACHE_END_MARKER,在32位是1,在64位是0,和上面一样都是因为32位可用的寄存器或者缓存比较少.
三是CACHE_ALLOW_FULL_UTILIZATION,在64位arm是1.表示允许100%的容量占用比例.

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 <= cache_fill_ratio(capacity))) {
        // Cache is less than 3/4 or 7/8 full. Use it as-is.
        printf("进入判断1");
    }
#if CACHE_ALLOW_FULL_UTILIZATION
    else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) {
        // Allow 100% cache utilization for small buckets. Use it as-is.
      printf("进入判断2");  
    }
#endif
    else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);
    }

为了方便断点,加了两行printf("进入判断1");和printf("进入判断2");不过我是x86_64环境,判断2是肯定不会进了.
这里得到newOccupied是1,表示此时oldCapacity是0,
此时mask()是空,返回0,因此capacity()是0,oldCapacity和capacity是0.
进入isConstantEmptyCache(),然后按照INIT_CACHE_SIZE来初始化容量,INIT_CACHE_SIZE是1<<2,也就是4.
然后调用reallocate重置缓存.

如果newOccupied满足条件,比如在arm64小于capacity的7/8或者CACHE_ALLOW_FULL_UTILIZATION时满足下面的条件,
在缓存空间这方面就不会做什么.
如果不满足,就会扩充空间为2倍.然后reallocate.

再走一次断点,看到sel是"instanceMethod:",这次进入了printf("进入判断1");
给MyClass多加几个实例方法再看看.

- (int)myMethod0;
- (int)myMethod1;
- (int)myMethod2;

//main.m
id myObj = [MyClass alloc];
MyClass *my = (MyClass *)[myObj init];
[my myMethod0];
[my myMethod1];
[my myMethod2];

当走到method1时,newOccupied是3,CACHE_END_MARKER在x86_64下是1,所以进入了扩充容量的逻辑.

    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;

//buckets函数
struct bucket_t *cache_t::buckets() const
{
    uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return (bucket_t *)(addr & bucketsMask);
}

这里通过 buckets()函数获取一个指针b,可以看做是一个数组指针.
_bucketsAndMaybeMask.store是设值,load是取值,当类第一次调用实例方法的时候,给cache_t申请空间.
在申请空间的时候,调用emptyBucketsForCapacity,会根据容量来申请.
之后调用setBucketsAndMask来给cache_t初始化或者在其他情况下设值.
而_bucketsAndMaybeMask是一个复合含义的变量,与上bucketsMask获得bucket_t的地址.

//cache_hash
static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    uintptr_t value = (uintptr_t)sel;
#if CONFIG_USE_PREOPT_CACHES
    value ^= value >> 7;
#endif
    return (mask_t)(value & mask);
}

上面经过 buckets()得到了一个数组,它被作为哈希表来运作.
这个数组的长度是capacity
cache_hash这个函数的目的是得到一个索引.
这里的mask传进来的是capacity - 1,所以此时=7.
value是SEL的值,SEL的类型是objc_selector *,是一个指针.
CONFIG_USE_PREOPT_CACHES在arm64真机是为1.如果是1,value右移7位异或自己,相当于只取前面7位,后面全是0.
然后value再和mask按位与,最终得到一个0 ~ mask之间的索引,也就是0 ~ capacity-1.对应这个数组.

这是一个比较简单的哈希算法,mask永远是容量capacity - 1,比如mask=7,也就是0111,这时候和SEL与运算,结果是0000~0111之间,
假如有一个SEL1是1010 11111 0100 有一个SEL2是1111 0000 0100,他们和mask与运算的结果是一样的,就会导致获取的索引是一样的,这就是所谓哈希碰撞.

 do {
        if (fastpath(b[i].sel() == 0)) {
            incrementOccupied();
            b[i].set<Atomic, Encoded>(b, 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));

   

现在得到了索引,对于数组该索引下的值,有三种情况,第一是存的就是这次需要存的SEL.
第二种是存了其他的SEL,也就是发生了哈希碰撞.
第三种是该位置还是空的.

所以下面就会进行判断.
接下来b[i].sel()获取begin的bucket,查看是否有SEL,如果没有,那就把新的bucket放在这个位置.
如果已经有了,并且就是打算存的这个SEL,那么就什么都不做.
如果该索引不可用,存的也不是目标sel,那就需要通过cache_next获取一个新的索引.

#if CACHE_END_MARKER
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}
#elif __arm64__
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}

cache_next有两种实现,
第一种是+1然后与运算,前面我们知道capacity是4,8,16这样每次翻倍,也就是2^n,mask是 capacity- 1,
所以此时,如果i= 4, 4发生了碰撞, (i +1) & 7 = 5,结果相当于返回i+1.也就是索引后移一位.
当i = mask的时候,比如i= 7的时候,i+1是1000,1000 & 0111 = 0,相当于回到了索引第一位.
第二种是从索引前移一位,如果i=0,就返回最后一个索引,也就是mask.

所以最终全部的索引都有机会尝试,但是如果只是这样的话,当这个表填充的越多,也就是occupied越大,效率就越低,
所以就有了在3/4或者7/8的时候进行扩充,就是为了减少do while的次数.

 bad_cache(receiver, (SEL)sel);

如果最终while循环执行完毕还没有return,就会执行bad_cache.会触发crash并输出信息.

初始化和扩容

bucket_t *cache_t::allocateBuckets(mask_t newCapacity)
{
    bucket_t *newBuckets = (bucket_t *)calloc(bytesForCapacity(newCapacity), 1);
    bucket_t *end = endMarker(newBuckets, newCapacity);
#if __arm__
    end->set<NotAtomic, Raw>(newBuckets, (SEL)(uintptr_t)1, (IMP)(newBuckets - 1), nil);
#else
    end->set<NotAtomic, Raw>(newBuckets, (SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    if (PrintCaches) recordNewCache(newCapacity);
    return newBuckets;
}

这个函数是初始化bucket散列表的,也就是那个数组,根据newCapacity申请内存空间.
endMarker返回这个数组的最后一个元素.
然后把end赋值,SEL设置为1,IMP指向第一个元素.

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    bucket_t *oldBuckets = buckets();
    bucket_t *newBuckets = allocateBuckets(newCapacity);
    setBucketsAndMask(newBuckets, newCapacity - 1);
    if (freeOld) {
        collect_free(oldBuckets, oldCapacity);
    }
}

这个函数是重设散列表,当类第一次调用方法时,或者当需要扩充时,以及copy等操作的时候回调用.

但是可以看到一个问题,那就是旧的buckets没有被赋值到新的位置.也就是没有内存平移,或者用代码进行cpoy的操作.确实如此,因为旧的缓存直接就被丢弃了

验证一下

        id myObj = [MyClass alloc];
        MyClass *my = (MyClass *)[myObj init];
        [my myMethod0];
        [my myMethod1];
        [my myMethod2];

//objc-cache.mm
void cache_t::insert(SEL sel, IMP imp, id receiver){
//...
    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;
//...

从第二行开始每一行都加断点,运行到第一个断点的时候,在void cache_t::insert(SEL sel, IMP imp, id receiver)的bucket_t *b = buckets();这一行添加断点.
之后注意每次都要先取消insert的断点,然后再前进,这样.m每个断点都对应insert的一个.因为.m执行一行,insert可能会执行多次.

(lldb) p sel
(SEL) $0 = "init"
(lldb) p occupied()
(mask_t) $1 = 0
(lldb) p capacity
(unsigned int) $2 = 4

首先是第一次进入insert,sel是init方法.这是类第一次调用方法,此时occupied是0,capacity是4.

(lldb) p sel
(SEL) $3 = "myMethod0"
(lldb) p occupied()
(mask_t) $4 = 1
(lldb) p buckets()
(bucket_t *) $5 = 0x0000000120004080
(lldb) p $5[0].sel()
(SEL) $6 = (null)
(lldb) p $5[1].sel()
(SEL) $7 = (null)
(lldb) p $5[2].sel()
(SEL) $8 = "init"

然后是第二次进入,此时sel是myMethod0方法,occupied是1,刚才的init已经缓存进来了
并且可以找到存在索引2的位置.

(lldb) p sel
(SEL) $1 = "myMethod1"
(lldb) p capacity
(unsigned int) $2 = 8
(lldb) p occupied()
(mask_t) $3 = 0

然后是第三次进入insert,
因为我是用mac运行,x86_64环境,走的是newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity)),
此时newOccupied是3,CACHE_END_MARKER是1, cache_fill_ratio(capacity)是3,所以走了扩容.
capacity增加到了8.
但是可以看到此时获取occupied是0,也就是说缓存里是空的.

(lldb) p occupied()
(mask_t) $4 = 1
(lldb) p sel
(SEL) $5 = "myMethod2"
(lldb) p capacity
(unsigned int) $6 = 8
(lldb) p buckets()
(bucket_t *) $7 = 0x000000010912b7f0
(lldb) p $7[0].sel()
(SEL) $8 = (null)
(lldb) p $7[1].sel()
(SEL) $9 = (null)
(lldb) p $7[2].sel()
(SEL) $10 = (null)
(lldb) p $7[3].sel()
(SEL) $11 = (null)
(lldb) p $7[5].sel()
(SEL) $12 = (null)
(lldb) p $7[4].sel()
(SEL) $13 = "myMethod1"
(lldb) p $7[6].sel()
(SEL) $14 = (null)
(lldb) p $7[7].sel()
(SEL) $15 = ""

然后是第四次进入,sel是myMethod2,occupied是1,然后查看了所有的8个bucket_t,确实只有一个有值,就是第三次进入时保存的myMethod1.
所以当扩容的时候,旧的缓存会被丢弃.