OC底层原理07 - 类结构探索(2)

在类结构探索(1)中，对类结构中的isa进行了探索，接下来将对类结构中的其它成员进行探索。

cache_t cache

cache主要是用来缓存方法的，但如何缓存还需要我们去探索，首先来看一下cache_t这个结构体。

struct cache_t {
//表示运行的环境 模拟器 或者 macOS
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    // 是一个结构体指针类型，占8字节
    explicit_atomic<struct bucket_t *> _buckets; 
    //mask_t 类型，而 mask_t 是 unsigned int 的别名，占4字节
    explicit_atomic<mask_t> _mask; 

//表示运行环境是 64位的真机
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    //指针类型，占8字节
    explicit_atomic<uintptr_t> _maskAndBuckets; 
    //mask_t 类型，而 mask_t 是 unsigned int 的别名，占4字节
    mask_t _mask_unused; 
    
#if __LP64__
    //uint16_t类型，uint16_t是 unsigned short 的别名，占 2个字节
    uint16_t _flags;  
#endif
    //uint16_t类型，uint16_t是 unsigned short 的别名，占 2个字节
    uint16_t _occupied; 
}

cache_t结构体在不同的架构中含有的属性个数不同，在真机中对mask和buckets的存储进行了优化，将这两个属性存储到一个指针里面。

以下以macOS为例进行说明。

_buckets
它是一个的数组，里面存放了多个bucket_t结构体，而每一个bucket_t结构体中又存放了sel、imp。

struct bucket_t {
private:
#if __arm64__ //真机
    //explicit_atomic 是加了原子性的保护
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else //非真机
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
    //方法等其他部分省略
}

_mask
_mask是指掩码数据，用于在哈希算法或者哈希冲突算法中计算哈希下标，其中mask 等于capacity。
_occupied
_occupied表示哈希表中sel-imp的占用大小(即可以理解为分配的内存中已经存储了sel-imp的个数)。

我们通过一个示例来进行探索。

准备工作

定义一个自定义类LGPerson，并在这个类中定义两个属性，若干个实例方法。

@interface LGPerson : NSObject

@property(nonatomic, strong)NSString* name;
@property(nonatomic, strong)NSString* nickName;

- (void)say111;

- (void)say222;

- (void)say333;

- (void)say444;

- (void)say555;

@end

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

- (void)say222{
    NSLog(@"%s", __func__);
}

- (void)say333{
    NSLog(@"%s", __func__);
}

- (void)say444{
    NSLog(@"%s", __func__);
}

- (void)say555{
    NSLog(@"%s", __func__);
}

@end3

在main.cpp中，定义一个LGPerson的对象，并使用该对象调用其对象方法。

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        //0x00007ffffffffff8ULL
        LGPerson* person = [LGPerson alloc];
        Class pClass = [LGPerson class];
        [person say111];
        [person say222];
        [person say333];
        [person say444];
        [person say555];
    }
    return 0;
}

开始探索

将程序运行起来，在调用对象方法之前，通过断点停下。通过lldb查看一下，当前catch_t中的内容。

获取类的首地址

(lldb) p/x pClass
(Class) $0 = 0x0000000100008320 LGPerson

由于类结构体中的前两个成员为isa和superclass，各占8个字节，因此，将首地址偏移16个字节，即为cache起始地址。

(lldb) p/x (cache_t*)0x0000000100008330
(cache_t *) $1 = 0x0000000100008330

读取cache中的内容

(lldb) p *$1
(cache_t) $2 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = {
      Value = 0x0000000100346460
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = {
      Value = 0
    }
  }
  _flags = 32804
  _occupied = 0
}

获取buckets中的sel和imp

(lldb) p $2.buckets()[0].sel()
(SEL) $3 = <no value available>

由此时可以看出，当未调用对象方法时，cache中没有缓存。

调用一次对象方法后，再读取一次buckets中的sel和imp

(lldb) p *$1
(cache_t) $4 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = {
      Value = 0x000000010070ea30
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = {
      Value = 3
    }
  }
  _flags = 32804
  _occupied = 1
}

(lldb) p $2.buckets()[0].sel()
(SEL) $5 = "say111"

此时可以发现，当调用了一次对象方法后，cache中缓存一次方法。
那再调用一次对象方法呢，是不是又会缓存一次？为了验证这个想法，让应用再调用一次对象方法后，再查看一下当前cache中的内容。

(lldb) p *$1
(cache_t) $7 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = {
      Value = 0x000000010070ea30
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = {
      Value = 3
    }
  }
  _flags = 32804
  _occupied = 2
}

(lldb) p $7.buckets()[0].sel()
(SEL) $8 = "say111"
(lldb) p $7.buckets()[1].sel()
(SEL) $9 = "say222"

总结：

未调用对象方法之前，_occupied为0，cache中没有缓存。
调用一次对象方法，_occupied为1，cache的buckets中可以读取到当前被调用的对象方法的sel和imp。
调用两次对象方法，_occupied为2，cache的buckets中可以读取到这两个对象方法的sel和imp。

那调用对象方法时，是如何将方法存入cache中？

由于每一次调用，会对_occupied值进行加1，那就先从这个值着手。

查看源码，对_occupied值进行加1的操作是在incrementOccupied函数中完成

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

继续查找调用incrementOccupied这个函数的地方。发现只在cache_t的insert方法有调用。

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)) {
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        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);
}

该方法就是cache的插入，即向cache中插入sel、imp。
接下来我们来分析一下这个方法。

根据occupied的值计算出当前的缓存占用量，当属性未赋值或方法未调用时，occupied()为0。而newOccupied=occupied()+1，即newOccupied为1。
当对属性进行操作时，会隐式的调用属性的set/get方法，occupied也会增加。
当对方法进行调用时，occupied也会增加。
当对对象的父类方法进行调用时，occupied也会增加。
根据缓存占用量判断执行的操作。
如果是第一次创建，则默认开辟4个；

if (slowpath(isConstantEmptyCache())) { //小概率发生的 即当 occupied() = 0时，即创建缓存，创建属于小概率事件
    // Cache is read-only. Replace it.
    if (!capacity) capacity = INIT_CACHE_SIZE; //初始化时，capacity = 4（1<<2 -- 100）
    reallocate(oldCapacity, capacity, /* freeOld */false); //开辟空间
    //到目前为止，if的流程的操作都是初始化创建
}

如果缓存占用量小于等于3/4，则不作任何处理；

else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) { 
    // Cache is less than 3/4 full. Use it as-is.
}

如果缓存占用量超过3/4，则需要进行两倍扩容以及重新开辟空间。

else {//如果超出了3/4，则需要扩容（两倍扩容）
    //扩容算法： 有cap时，扩容两倍，没有cap就初始化为4
    capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 扩容两倍 2*4 = 8
    if (capacity > MAX_CACHE_SIZE) {
        capacity = MAX_CACHE_SIZE;
    }
    // 走到这里表示 曾经有，但是已经满了，需要重新梳理
    reallocate(oldCapacity, capacity, true);
    // 内存 扩容完毕
}

针对需要存储的bucket进行内部imp和sel赋值
这部分主要是根据cache_hash方法，即哈希算法，计算sel-imp存储的哈希下标，分为以下三种情况
- 如果哈希下标的位置未存储sel，即该下标位置获取sel等于0，此时将sel-imp存储进去，并将occupied占用大小加1。
- 如果当前哈希下标存储的sel 等于即将插入的sel，则直接返回。
- 如果当前哈希下标存储的sel 不等于即将插入的sel，则重新经过cache_next方法即哈希冲突算法，重新进行哈希计算，得到新的下标，再去对比进行存储。

到此，cache_t的原理基本分析完成了。

接下来有几个问题为重点面试问题：

bucket数据为什么会有丢失的情况？
答：原因是在扩容时，是将原有的内存全部清除了，再重新申请了内存导致的。
为什么随着方法调用的增多，其打印的occupied 和 mask会变化？
答：因为在cache初始化时，分配的空间是4个，随着方法调用的增多，当存储的sel-imp个数，即newOccupied + CACHE_END_MARKER的和超过总容量的3/4，例如有4个时，当occupied等于2时，就需要对cache的内存进行两倍扩容。
say333、say444的打印顺序为什么是say444先打印，say333后打印，且还是挨着的，即顺序有问题？
答：因为sel-imp的存储是通过哈希算法计算下标的，其计算的下标有可能已经存储了sel，所以又需要通过哈希冲突算法重新计算哈希下标，所以导致下标是随机的，并不是固定的。