OC底层原理十一: cache_t分析

OC底层原理 学习大纲

学习是一件循序渐进的事情。步子大了扯到蛋🥚

我们回顾下之前学习的内容。 将所学知识进行串联，做一个小结。

话说几万年前，世界就是一个封闭的鸡蛋，没有光明与黑暗，也毫无生机。

冥冥中大家都有种预感，大事将近。

盘古开天辟地(4S横空出世)，激活了世间万物。

（--- 此处省略1万字 ---）

我记得爷爷的爷爷的爷爷曾经跟我说过，世界上第一个生物的诞生
.
.
.

对咯。 我们就是从对象的创建开始说起。

image.png

这个通关游戏，咱们继续。 类的基础结构我们都了解了，但是cache。我们上次只偷瞄了一眼。计算了它占用空间大小。

  • 如此重要的缓存机制，怎么能冷落ta。今天，咱们撸ta!

cache_t 分析

    1. 结构分析
    1. 探究缓存机制
    1. 快捷查找
    1. cache原理分析

1. 结构分析

打开objc4源码，搜索struct objc_class：

image.png

进入cache_t:

  • 暂时剔除``const、void、static和函数。
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;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;
#else
#error Unknown cache mask storage type.
#endif
    
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;
};
  • 我们先弄清楚判断条件的几个宏是什么意思

CACHE_MASK_STORAGE: 当前是使用mac调试，所以会进入

  • macos系统：i386， 模拟器： x86， 苹果真机: arm64 
// 是真机且是64位系统 
#if defined(__arm64__) && __LP64__              
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16
// 是真机但不是64位系统
#elif defined(__arm64__) && !__LP64__ 
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_LOW_4
// 其他
#else                                 
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_OUTLINED
#endif

现在我以电脑端为平台来进行探究。简化cache_t代码：

struct cache_t {
    explicit_atomic<struct bucket_t *> _buckets;
    explicit_atomic<mask_t> _mask;
    uint16_t _flags;
    uint16_t _occupied;
};

清爽~ 舒服~

如果是真机，cache_t分支是:

struct cache_t {
   explicit_atomic<uintptr_t> _maskAndBuckets;
   mask_t _mask_unused; // 猜测是系统暂时没用到的参数。😂  占坑
   
   // mask掩码移动位数
   static constexpr uintptr_t maskShift = 48;
   
   // 掩码清零4位
  static constexpr uintptr_t maskZeroBits = 4;
   
   // 可以存储的最大mask掩码值(2^16 - 1)
   static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
   
   // 用于从`_maskAndBuckets`中找回`buckets`的指针位置
   //  (1 << (48 - 4)) - 1  buckets最大位数只有43位
   static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
   
   // 没有足够的空间来存放buckets了
   static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS, "Bucket field doesn't have enough bits for arbitrary pointers.");
  
   uint16_t _flags;
   uint16_t _occupied;
}
  • 我们可以看到_buckets和_mask被合并成了 _maskAndBuckets，并加设了一些静态mask掩码。
  • 你是否还记得isa中也有掩码，我们利用isa的union联合体结构，在更小的空间内高效记录更多信息。利用mask掩码从isa中取出shiftcls部分。获取到类的信息。
  • 这里同样是苹果官方的优化手段，利用掩码和位运算，在有限空间内存储更多信息，使用位运算的高效读取

  • 回到mac环境。

  • 我们进入explicit_atomic，会发现返回的类型就是传入的泛型T。 它的作用是将操作环境设定为原子操作，防止同一时间多端处理同一数据，保障数据的准确性。

如果在测试环境，不要求原子操作，上述代码等同于

struct cache_t {
   bucket_t *  _buckets;
   mask_t _mask;
   uint16_t _flags;
   uint16_t _occupied;
};

现在我们一个个来分析：

  • _buckets： 存储bucket_t的数组。其中bucket_t是包含SEL和IMP的结构体

    image.png

    我们可以看到这有公开的sel和imp的读取方法

  • _mask： 重要的掩码，下面分析cache机制会介绍

  • _flags： 标记

  • _occupied： 占用位置个数

2.探究缓存机制

我们了解了cache_t的内部结构，现在我们来探索cache的缓存机制

  • 在objc4源码的main.m中添加测试代码
@interface HTPerson : NSObject

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

- (void)sayHello;

- (void)sayCode;

- (void)sayMaster;

- (void)sayNB;

+ (void)sayHappy;

@end

@implementation HTPerson

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

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

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

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

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

+ (void)sayHappy{
    NSLog(@"%s",__func__);
}
@end

int main(int argc, const char * argv[]) {
    @autoreleasepool {

        HTPerson *p  = [HTPerson alloc];
        Class pClass = [HTPerson class]; // 记录类，便于后面使用
        //p.name     = @"mark";
        //p.nickName   = @"哈哈";

        [p sayHello];
        [p sayCode];
        //[p sayDevelop];
        //[p sayMaster];
        //[p sayNB];
        NSLog(@"%@",pClass);
    }
    return 0;
}

在[p sayHello]一行加入断点，运行函数。

  • 找到HTPerson的cache的内存地址：
image.png

执行代码，到达[p sayCode]一行。再次打印cache_t内容:

image.png

发现执行了一遍sayHello方法后，imp有值了。_occupied占用位置也由0变成了1 。

- 我们如何打印处sel和imp内容呢？

image.png
  • 我们查找cache_t的函数，发现有公开获取buckets的方法。
image.png

  • _buckets是一个数组。上图实际上是读取到了数组的第一个元素。

  • 我们上面知道在bucket_t结构中，有公开的sel()和imp(class)方法供外部获取sel和class。 所以可以读取：

image.png

我们看到sayHello存储在cache中了。

  • 我们继续执行一行代码，运行[p sayCode]，打印buckets数组。
image.png

- 我们只拿到数组地址，如何读取数组所有元素呢？

方法一：既然拿到了数组首地址，而数组的元素类型都是一致的，我们可以通过内存偏移读取元素。

image.png

方法二：既然是数组，就可以直接使用数组下标进行读取。

image.png
  • 在cache内存中成功读取到2个函数
    image.png

如果我们将测试代码的注释都放开, 逐行执行和打印buckets数组，会发现一些奇怪的现象

  • 1. occupied 和mask 在变化，是什么在影响它们？mask又是啥？
  • 2. cache中的buckets数组打印的值会有丢失
  • 3. buckets数组的顺序与执行顺序不相同
image.png
image.png

在分析这个原因之前。

  • 我们发现每次lldb来p查找很麻烦。所以先介绍个快捷查找的方式

3. 快捷查找

  • 我们打印buckets相关信息，每次都得进入objc源码工程，很麻烦！
  • 有没有一种任何项目都可以直接查询的方法呢？

有，请接好：

  • 每次进入objc4源码，其实我们只用到了业务线上的实现和结构。
  • 既然如此，我们直接从源码中把需要的拷出来，做成{ }代码块工具(点此了解代码块)，随时可用，岂不爽歪歪？

老规矩，授人以渔 + 授人以鱼：

授人以渔(思维方式):
  • 确定自己想要的东西，再开始拷贝。简化无用代码。保存完整内存结构即可。
    例如：
  • 我现在研究cache的结构。所以把cache_t结构从objc4拷贝出来。
  • 剔除无用代码(不影响cache_t空间结构的代码)
  • 将原子操作explicit_atomic直接换成直接类型(因为不是完整运行，只仿照代码来获取想要的内容)
  • 需要bucket_t结构，所以我们仿写一个ht_bucket_t，并简化类型。
  • 如何到达cache？ 所以我们需要仿写一个objc_class类。然后发现缺少class_data_bits_t类，所有也仿写一个ht_class_data_bits_t。
  • 我们知道，所有OC类都是以底层objc_class为模板创建的，所以我们可以直接将任何类强转为ht_objc_class。 在进行结构读取。
授人以鱼:
struct ht_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct ht_cache_t {
    struct ht_bucket_t * _buckets;  // 将bucket_t 改成自己的 ht_bucket_t
    uint32_t  _mask; // 直接使用内部 uint32_t 格式
    uint16_t _flags;
    uint16_t _occupied;
};

struct ht_class_data_bits_t {
    uintptr_t bits;
};

// 原继承自objc_object。
// 我们只需要研究cache，所以直接取objc_object内部的Class ISA
// 保证数据结构一致，可以类型强转就行。
struct ht_objc_class {
    Class ISA;
    Class superclass;
    struct ht_cache_t cache;
    struct ht_class_data_bits_t bits; // 将 class_data_bits_t 改成 ht_class_data_bits_t
};
使用方式:

参考上面测试代码，加入我们自己的代码

int main(int argc, const char * argv[]) {
    @autoreleasepool {

        HTPerson *p  = [HTPerson alloc];
        Class pClass = [HTPerson class];
        p.name     = @"mark";
        p.nickName   = @"哈哈";

        [p sayHello];
        [p sayCode];
        [p sayMaster];
        [p sayNB];
        
        // 将类强转为我们自己的类
        struct ht_objc_class * ht_class = (__bridge struct ht_objc_class *)(pClass);
        
        // struct 类型要用 -> 读取。
        NSLog(@"_occupied: %hu, _mask:%u",ht_class->cache._occupied, ht_class->cache._mask);
        
        // 我们读取mask中每一个值
        for (uint32_t i = 0; i < ht_class->cache._mask; i ++) {
            // 取出每个bucket
            struct ht_bucket_t bucket = ht_class->cache._buckets[i];
            // 打印sel 和 imp
            NSLog(@"第%u个:  sel:%@  imp:%p ", i, NSStringFromSelector(bucket._sel), bucket._imp);
        }
    }
    return 0;
}

打印结果如下：

image.png

自定义类型和调用函数的代码，都可以写成代码块(点此了解{ }代码块工具)，便于后续使用。

刘德华说的 学到了，就要教出去 😃 （ 感谢KC ）

4. cache原理分析

走到这，你能感受到_occupied和_mask的意思吗？

  • _mask： 总空间大小
  • _occupied： 当前占用的空间大小

我们发现buckets中只存储函数。 我们细想一下:

  • 属性不影响缓存，只负责存储，函数才是影响缓存大小的。增删改查都是函数实现

回到上面问题： _mask 和 _occupied 是如何变化的？

  • 查看cache_t结构，发现public处，有incrementOccupied函数和setBucketsAndMask函数。

    image.png

  • 进入incrementOccupied发现只是执行了_occupied++。

  • 进入setBucketsAndMask发现每次都是重新设置_buckets和_mask，并且把_occupied设置为0

    image.png

有意思的是，我们发现苹果留了个其他情况他也不知道怎么处理😂

  • 还记得前面_mask_unused字段吗？ 我们猜测是系统暂时没用到的字段。

我们发现incrementOccupied是执行计数加一操作，那我们搜索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());

    // 原occupied计数+1
    mask_t newOccupied = occupied() + 1;

    // 进入查看： return mask() ? mask()+1 : 0;
    // 就是当前mask有值就+1，否则设置初始值0
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    
    // 当前缓存是否为空
    if (slowpath(isConstantEmptyCache())) {
        
        // Cache is read-only. Replace it.
        // 如果为空，就给空间设置初始值4
        // (进入INIT_CACHE_SIZE查看，可以发现就是1<<2，就是二进制100，十进制为4)
        if (!capacity) capacity = INIT_CACHE_SIZE;
        
        // 创建新空间（第三个入参为false，表示不需要释放旧空间）
        reallocate(oldCapacity, capacity, /* freeOld */false);
    
    }
    
    // CACHE_END_MARKER 就是 1
    // 如果当前计数+1 < 空间的 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 {
        // 如果空间存在，就2倍扩容。 如果不存在，就设为初始值4
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        
        // 防止超出最大空间值（2^16 - 1）
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        
        // 创建新空间（第三个入参为true，表示需要释放旧空间）
        reallocate(oldCapacity, capacity, true);
    }

    // 读取现在的buckets数组
    bucket_t *b = buckets();
    
    // 新的mask值(当前空间最大存储大小)
    mask_t m = capacity - 1;
    
    // 使用hash计算当前函数的位置(内部就是sel & m， 就是取余操作，保障begin值在m当前可用空间内)
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;

    do {
        // 如果当前位置为空（空间位置没被占用）
        if (fastpath(b[i].sel() == 0)) {
            // Occupied计数+1
            incrementOccupied();
            // 将sle和imp与cls关联起来并写入内存中
            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;
        }
        // 如果位置有值，再次使用哈希算法找下一个空位置去写入
        // 需要注意的是，cache_next内部有分支： 
        // 如果是arm64真机环境： 从最大空间位置开始，依次-1往回找空位
        // 如果是arm旧版真机、x86_64电脑、i386模拟器： 从当前位置开始，依次+1往后找空位。不能超过最大空间。
        // 因为当前空间是没超出mask最大空间的，所以一定有空位置可以放置的。
    } while (fastpath((i = cache_next(i, m)) != begin));

    // 各种错误处理
    cache_t::bad_cache(receiver, (SEL)sel, cls);
}

reallocate : 上面创建新空间并释放旧空间的函数

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    // 读取旧buckets数组
    bucket_t *oldBuckets = buckets();
    // 创建新空间大小的buckets数组
    bucket_t *newBuckets = allocateBuckets(newCapacity);

    // Cache's old contents are not propagated. 
    // This is thought to save cache memory at the cost of extra cache fills.
    // fixme re-measure this

    // 新空间必须大于0
    ASSERT(newCapacity > 0);
    
    // 新空间-1 转为mask_t类型，再与新空间-1 进行判断
    ASSERT((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);

    // 设置新的bucktes数组和mask
    // 【重点】我们发现mask就是newCapacity - 1, 表示当前最大可存储空间
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    // 释放旧内存空间
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
    }
}

allocateBuckets： 创建新空间大小的buckets数组

bucket_t *allocateBuckets(mask_t newCapacity)
{
    // 创建1个bucket
    bucket_t *newBuckets = (bucket_t *)
        calloc(cache_t::bytesForCapacity(newCapacity), 1);
    // 将创建的bucket放到当前空间的最尾部，标记数组的结束
    bucket_t *end = cache_t::endMarker(newBuckets, newCapacity);

#if __arm__
    // End marker's sel is 1 and imp points BEFORE the first bucket.
    // This saves an instruction in objc_msgSend.
    end->set<NotAtomic, Raw>((SEL)(uintptr_t)1, (IMP)(newBuckets - 1), nil);
#else
    // 将结束标记为sel为1，imp为这个buckets
    end->set<NotAtomic, Raw>((SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    
    // 只是打印记录
    if (PrintCaches) recordNewCache(newCapacity);
    
    // 返回这个bucket
    return newBuckets;
}

cache_collect_free：释放内存空间

static void cache_collect_free(bucket_t *data, mask_t capacity)
{
#if CONFIG_USE_CACHE_LOCK
    cacheUpdateLock.assertLocked();
#else
    runtimeLock.assertLocked();
#endif

    if (PrintCaches) recordDeadCache(capacity);
    
    // 垃圾房： 开辟空间 （如果首次，就开辟初始空间，如果不是，就空间*2进行拓展）
    _garbage_make_room ();
    // 将当前扩容后的capacity加入垃圾房的尺寸中，便于后续释放。
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    // 将当前新数据data存放到 garbage_count 后面 这样可以释放前面的，而保留后面的新值
    garbage_refs[garbage_count++] = data;
    // 不记录之前的缓存 = 【清空之前的缓存】。
    cache_collect(false);
}

所有代码分析完毕。 画龙点睛👀的汇总流程图。

  • cache分析流程
cache分析流程
  • cache_t 结构
cache_t结构
  • 写入(cache_t::insert)
写入(cache_t::insert)

  • 读取【objc_msgSend】将在下一章节讲

  • 如果你看完上面的cache_t分析。我相信上面的3个问题答案你应该已经有了

1. occupied 和mask 在变化，是什么在影响它们？mask又是啥?

  • 函数写入cache缓存时，occupied会加1，mask记录当前cache最大可存储空间。
  • 当inset缓存的操作，触发空间使用率超过3/4，空间2倍扩容时，mask记录新空间的最大可存储大小，因为旧空间被释放，之前cache的所有内容都被垃圾房清空了，所以occupied重置为0。从新开始计数

2. cache中的buckets数组打印的值会有丢失

  • 因为触发空间扩容时，旧空间被释放，所以cache中的旧值都被清空。 新值插入新cache空间。

3. buckets数组的顺序与执行顺序不相同

  • 插入操作是使用的hash算法。插入位置是经过取余计算的。且如果插入位置已经有值，就会不停的后移1位，直到找到空位置完成插入位置。

下一节 OC底层原理十二: objc_msgSend(汇编)

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。