ios底层原理-006 cache分析

之前的文章已经分析了objc_class中，ISA和bit。这次分析cache属性
简单的回顾一下

isa : isa 指向
superclass : 父类。
bits : bits 的类型为 class_data_bits_t ，存储了类中更详细的信息。
cache : cache是今天要研究的属性

MyClass.jpg

提出问题

• cache 是什么， 打开源码查看(objc4-818.2)

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;
    };
 /*
     #if defined(__arm64__) && __LP64__
     #if TARGET_OS_OSX || TARGET_OS_SIMULATOR
     // __arm64__的模拟器
     #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
     #else
     //__arm64__的真机
     #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16
     #endif
     #elif defined(__arm64__) && !__LP64__
     //32位 真机
     #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_LOW_4
     #else
     //macOS 模拟器
     #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_OUTLINED
     #endif
    */

    public:
    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld);
    unsigned capacity() const;
    struct bucket_t *buckets() const;
    Class cls() const;
    void insert(SEL sel, IMP imp, id receiver);

};

可以看到
_bucketsAndMaybeMaskuintptr_t类型，占8字节和isa_t中的bits类似，也是一个指针类型里面存放地址
联合体里嵌套结构体和一个结构体指针_originalPreoptCache
结构体中有三个成员变量_maybeMask，_flags，_occupied。__LP64__：模拟器环境或者MacOS
_originalPreoptCache和结构体是互斥的，_originalPreoptCache初始时候的缓存，现在探究类中的缓存，这个变量基本不会用到
public下，有几个方法，可以获取一些相关信息

struct bucket_t { //bucket_t的源码，真机和非真机环境下imp和sel的顺序不同
private:
#if __arm64__
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif

既然看到了sel和imp，可以猜想cache是方法的缓存

通过源码查找sel和imp，进行内存偏移访问

• 准备一个类LGPerson，初始化实现几个方法,

- (void)sayHello;
- (void)sayCode;
- (void)sayHappy;
- (void)sayMaster;
-------------------------------------------------------------------
- (void)sayHello {
    NSLog(@"%s",__func__);
}
- (void)sayCode {
    NSLog(@"%s",__func__);

}
- (void)sayHappy {
    NSLog(@"%s",__func__);
}
- (void)sayMaster {
    NSLog(@"%s",__func__);
}
------------------------------------------------------------------------
//main.m中调用
        LGPerson *person = [LGPerson alloc];
        Class pclass = [LGPerson class];
        [person sayHello];
        [person sayCode];
        [person sayHappy];
        [person sayMaster];
        NSLog(@"%@",pclass);

在main.m数中调用，在[person sayHello]打断点，进行lldb调试。

查找sel，imp

• 获取cache，和bits一样，通过内存平移。
• 没有执行方法之前，_occupied为0，调用了一次方法之后变为1，可以猜想，每调用一次方法都可以使_occupied +1。
• 获取bucket_t需要调用buckets()。获取sel调用sel()。获取imp调用imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls)。
  如何验证获取的sel，imp就是调用的。可以把可执行文件拖入到macO中查看function。完全一样。证明是对的。
  MachOView.png

继续调用方法，进一步验证

sayCode.jpg

• 在这里第一次没有找到sayCode方法，原因是_buckets是一个集合，需要通过下标访问其它的元素。

脱离源码环境创建项目查找sel&imp

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


struct lg_class_data_bits_t {
    uintptr_t bits;
};
struct lg_bucket_t {
    SEL _sel;
    uintptr_t _imp;
};

struct lg_cache_t {
    struct lg_bucket_t *_bucketsAndMaybeMask;
    union {
        struct {
            mask_t    _maybeMask;
            uint16_t                   _flags;
            uint16_t                   _occupied;
        };
        struct lg_preopt_cache_t * _originalPreoptCache;
    };

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

main.m中

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        LGPerson *p  = [LGPerson alloc];
        Class pClass = [LGPerson class];  // objc_class.
        [p say1];
        [p say2];
//        [p say3];
        // [p say4];
        struct lg_objc_class *cls = (__bridge struct lg_objc_class *)(pClass);
        NSLog(@"%hu,%u",cls->cache._occupied,cls->cache._maybeMask);
        
        for (mask_t i = 0; i < cls->cache._maybeMask; i ++) {
            struct lg_bucket_t  _bucketsAnd = cls->cache._bucketsAndMaybeMask[i];
            NSLog(@"sel = %@, imp = %p",NSStringFromSelector(_bucketsAnd._sel),_bucketsAnd._imp);
        }
        NSLog(@"Hello, World!");
    }
    return 0;
}

把这份代码，方法工程里，克隆出一个类似于源码的环境。要先将 lg_objc_class的ClassISA取消注释，因为克隆的代码没有默认继承。直接用的话会得不到想要的结果。
打印后：

脱离源码1.png
然后增加say3和say4的调用,打印结果
脱离源码2.png

对比两个打印结果，会发现有几个问题

• _occupied到底是什么，为什么一直是2，和猜想中有不同
• _maybeMask是什么，为什么调用的方法不一样，_maybeMask也不同
• 随着方法的增加，say1和say2为啥找不到了，而且顺序不同了。
  带着问题，我们进入源码查看

cache_t的源码查看相应的方法

Occupied.png

• 可以看到第一个是增加的方法， 第二个是get方法

// 方法内部
void cache_t::incrementOccupied() 
{
    _occupied++;
}

• 全局搜索incrementOccupied() ，只有一个地方进行了调用。

  
  incrementOccupied()调用位置.png

• 最终定位在cache_t的insert中，而且cache中存储的就是imp和sel，分析这个方法的源码

  
  代码.gif
  

  主要分为以下几部分
  【第一步】计算出当前的缓存占用量
  【第二步】根据缓存占用量``判断执行的操作
  【第三步】针对需要存储的bucket进行内部imp和sel赋值

第一步

根据occupied的值计算出当前的缓存占用量，当属性未赋值及无方法调用时，此时的occupied()为0，而newOccupied为1。

关于缓存占用量的计算，有以下几点说明：

alloc申请空间时，此时的对象已经创建，如果再调用init方法，occupied也会+1

当有属性赋值时，会隐式调用set方法，occupied也会增加，即有几个属性赋值，occupied就会在原有的基础上加几个

当有方法调用时，occupied也会增加，即有几次调用，occupied就会在原有的基础上加几个

第二步

根据缓存占用量判断执行的操作

• 第一次进入的时候，会先申请内存空间（默认开辟4个）
• 当小于3/4或者7/8时，不做处理

• 当占用量超过，需要进行两倍扩容和重新开辟空间
  重点说一下空间的开辟

  
  开辟空间
  

  主要有以下几步
  1.allocateBuckets方法：向系统申请开辟内存，即开辟bucket，此时的bucket只是一个临时变量
  2.setBucketsAndMask方法：将临时的bucket存入缓存中，根据bucket和mask的位置存储，并将occupied占用设置为0

• 如果有旧的buckets，需要清理之前的缓存，即调用cache_collect_free方法，其源码实现如下：

  
  回收旧的buckets.png

第三步

针对需要存储的bucket进行内部imp和sel赋值

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

哈希算法.png
cache_next：哈希算法
哈希冲突算法.png

总结

1、_maybeMask是什么？
_maybeMask是指掩码数据，用于在哈希算法或者哈希冲突算法中计算哈希下标，其中_maybeMask 等于capacity - 1

2、_occupied 是什么？
_occupied表示哈希表中 sel-imp 的占用大小 (即可以理解为分配的内存中已经存储了sel-imp的的个数)，
init会导致occupied变化，属性赋值，也会隐式调用，导致occupied变化，方法调用，导致occupied变化

3、为什么随着方法调用的增多，其打印的occupied 和 mask会变化？
因为在cache初始化时，分配的空间是4个，随着方法调用的增多，当存储的sel-imp个数，即newOccupied + CACHE_END_MARKER（等于1）的和 超过 总容量的3/4,例如有4个时，当occupied等于2时，就需要对cache的内存进行两倍扩容

4、bucket数据为什么会有丢失的情况？，例如2-7中，只有say3、say4方法有函数指针
原因是在扩容时，是将原有的内存全部清除了，再重新申请了内存导致的

5、脱离源码第二次打印，say3、say4的打印顺序为什么是say4先打印，say3后打印，而且中间还不是连着的。
因为sel-imp的存储是通过哈希算法计算下标的，其计算的下标有可能已经存储了sel，所以又需要通过哈希冲突算法重新计算哈希下标，所以导致下标是随机的，并不是固定的

6、打印的 cache_t 中的 ocupied 为什么是从 2 开始？
这里是因为LGPerson通过alloc创建的对象，并对其两个属性赋值的原因，属性赋值，会隐式调用set方法，set方法的调用也会导致occupied变化

附图

cache_t流程.jpg