iOS底层原理09：类结构分析——cache属性

在前面的文章中，我们探索了isa、superclass、bits属性
iOS底层原理07：类 & 类结构分析
iOS底层原理08：类结构分析——bits属性
本文主要探索cache的结构和底层原理

1、探索cache的数据结构

cache的类型是cache_t结构体

1.1、cache_t结构体

👇来看看objc4-818源码中cache_t结构体

typedef unsigned long           uintptr_t;

#if __LP64__
typedef uint32_t mask_t;  // x86_64 & arm64 asm are less efficient with 16-bits
#else
typedef uint16_t mask_t;
#endif

struct cache_t {
private:
    // explicit_atomic 显示原子性，目的是为了能够 保证 增删改查时 线程的安全性
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask; //8字节
    union {
        struct {
            explicit_atomic<mask_t>    _maybeMask; //4字节
#if __LP64__
            uint16_t                   _flags; //2字节
#endif
            uint16_t                   _occupied;//2字节
        };
        explicit_atomic<preopt_cache_t *> _originalPreoptCache; // 8字节
    };
    
    //下面是一些static属性和方法，并不影响结构体的内存大小，主要是因为static类型的属性 不存在结构体的内存中
    /*
     #if defined(__arm64__) && __LP64__
     #if TARGET_OS_OSX || TARGET_OS_SIMULATOR
     // macOS 或 __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
     ******  中间是不同的架构之间的判断 主要是用来不同类型 mask 和 buckets 的掩码
    */
        
    // ...省略代码
    // 下面是几个比较重要的方法
    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);

    void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld);
    void collect_free(bucket_t *oldBuckets, mask_t oldCapacity);
    
    unsigned capacity() const;
    struct bucket_t *buckets() const;
    Class cls() const;
    
    void insert(SEL sel, IMP imp, id receiver);
    /// 快速计算对象内存大小，16字节对齐，在对象的alloc中我们已经分析过了
    size_t fastInstanceSize(size_t extra) const {...}
    
    // ...省略代码
}

cache_t是结构体类型，有两个成员变量：_bucketsAndMaybeMask和一个联合体

• _bucketsAndMaybeMask是uintptr_t类型，占8字节
• 联合体里面有两个成员变量：结构体和_originalPreoptCache，联合体由最大的成员变量的大小决定
  • _originalPreoptCache是preopt_cache_t *结构体指针，占8字节
  • 结构体中有_maybeMask、_flags、_occupied三个成员变量。
    • _maybeMask的大小取决于mask_t即uint32_t，占4字节
    • _flags是uint16_t类型，占2字节
    • _occupied是uint16_t类型，占2字节

所以cache_t的大小等于 8+8或者8+4+2+2，即16字节

• cache_t结构体提供了buckets()方法，返回类型是bucket_t *结构体指针

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

• cache_t结构体还提供了insert方法，插入sel和imp，即对方法的缓存

void cache_t::insert(SEL sel, IMP imp, id receiver) {
   //对各种不符合条件的判断报出错误码
      
   //省略代码。。。。
       
    //通过buckets数组来判断需要插入的内容情况
    bucket_t *b = buckets();  
    mask_t m = capacity - 1;
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;

   //省略代码。。。。
}

1.2、bucket_t结构体

struct bucket_t {
private:
    // IMP-first is better for arm64e ptrauth and no worse for arm64.
    // SEL-first is better for armv7* and i386 and x86_64.
#if __arm64__  // arm64架构
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else  // 其他架构
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif

    // ...省略代码
}

• bucket_t的成员顺序与架构有关
• bucket_t有两个成员变量_sel和_imp，存储方法的信息

1.3、lldb调试验证

• 创建HTPerson类

image

• main.m中代码如下，在[p sayHello];设置断点，运行代码

image

• 通过p *$1查看 cache的值，此时_maybeMask.Value 和 _occupied的值都为0

image

• 执行完[p sayHello];对象方法，继续查看cache的值，此时_maybeMask.Value 和 _occupied的值都发生了变化

image

• 完整的lldb调试过程如下图

image

通过源码和lldb调试，可以发现 cache存储的 方法缓存

• 调用对象方法sayHello后，_maybeMask和_occupied被赋值，这两个变量应该和缓存是有关系的，我们在后面进行深入分析。
• bucket_t结构体提供了sel()和imp(nil, Class)方法

2、根据源码，对类和cache进行仿写

为什么需要进行代码仿写呢？

• 当源码无法直接运行调试时，就需要进行代码仿写；
• 使用lldb调试时，增减一些属性、方法，就需要再次执行比较多的重复步骤，比较繁琐；
• 小规模取样的方式，会让你对底层更加清晰。

2.1、准备工作

• 新建一个macOS -> Command Line Tool工程，并创建HTPerson类，代码如下：

/*** HTPerson.h ***/
#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface HTPerson : NSObject

- (void)say1;
- (void)say2;
- (void)say3;
- (void)say4;
- (void)say5;
- (void)say6;
- (void)say7;
+ (void)sayHappy;

@end

NS_ASSUME_NONNULL_END

/*** HTPerson.m ***/
#import "HTPerson.h"

@implementation HTPerson

- (void)say1{
    NSLog(@"%s",__func__);
}
- (void)say2{
    NSLog(@"%s",__func__);
}
- (void)say3{
    NSLog(@"%s",__func__);
}
- (void)say4{
    NSLog(@"%s",__func__);
}
- (void)say5{
    NSLog(@"%s",__func__);
}
- (void)say6{
    NSLog(@"%s",__func__);
}
- (void)say7{
    NSLog(@"%s",__func__);
}

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

@end

• main.m文件中代码如下：

#import <Foundation/Foundation.h>
#import "HTPerson.h"

typedef uint32_t mask_t;
// bucket_t结构体
struct ht_bucket_t {
    SEL _sel;
    IMP _imp;
};

// cache_t结构体
struct ht_cache_t {
    struct ht_bucket_t * _buckets; //8字节
    mask_t _maybeMask; //4字节
    uint16_t _flags; //2字节
    uint16_t _occupied;//2字节
};

// 类结构体
struct ht_objc_class {
    Class isa;  // 8字节
    Class superclass; //8字节
    struct ht_cache_t cache;    //16字节
    uintptr_t  bits;    // 8字节
};


int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        HTPerson *p = [HTPerson alloc];
        Class pClass = p.class;
        
//        [p say1];
//        [p say2];
//        [p say3];
//        [p say4];
//        [p say5];
//        [p say6];
//        [p say1];
//        [p say2];
        
        struct ht_objc_class * ht_class = (__bridge struct ht_objc_class *)(pClass);
        NSLog(@"- %hu - %u", ht_class->cache._occupied, ht_class->cache._maybeMask);

        for (int i = 0; i < ht_class->cache._maybeMask; i++) {
            struct ht_bucket_t bucket = ht_class->cache._buckets[I];
            NSLog(@"%@ - %pf", NSStringFromSelector(bucket._sel), bucket._imp);
        }
    }
    return 0;
}

2.2、对象方法的调用 与 cache值的关系

• 未调用对象方法

如果对象方法都没有调用，则cache不会进行方法缓存，此时_occupied和_maybeMask的值都为0

image

• 调用say1和say2方法，查看打印结果

image

• 如果继续调用say3、say4和say5方法呢

image

【问题】 这里就产生了几个疑问？

• _occupied和_maybeMask是什么？他们的值是如何变化？
• 调用say3、say4和say5方法后，say1和say2怎么消失了？
• cache存储的位置怎么是乱序的呢？

_occupied和_maybeMask是什么？在什么地方赋值，只能去objc源码中找答案。我们要缓存方法，首先看怎么把方法插入到bukets中的。带着这些疑问继续探讨cache_t源码

3、cache_t源码探究

• 首先找到方法缓存的入口

image

从这个插入的方法来看，插入的参数有sel、imp、还有receiver消息接收者。👇下面是这个插入方法的代码实现：

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    // ...省略代码 （错误处理相关代码）
    
    // Use the cache as-is if until we exceed our expected fill ratio.
    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.
    }
#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.
    }
#endif
    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.
    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);
#endif // !DEBUG_TASK_THREADS
}

计算当前所占容量

image

• occupied()获取当前所占的容量，其实就是告诉你缓存中已经有几个bucket
• newOccupied = occupied() + 1，表示当前方法第几个进来缓存的
• oldCapacity 目的是为了重新扩容的时候释放旧的内存

开辟容量

image

• 第一次缓存方法的时，开辟默认容量是 capacity = INIT_CACHE_SIZE 即capacity = 4 就是4个bucket的内存大小
• reallocate(oldCapacity, capacity, /* freeOld */false)开辟内存，freeOld变量控制是否释放旧的内存

reallocate方法探究

image

reallocate 方法主要做三件事

• allocateBuckets开辟内存
• setBucketsAndMask设置mask和buckets的值
• collect_free是否释放旧的内存，由freeOld控制

allocateBuckets方法（开辟内存）探究

image

allocateBuckets 方法主要做两件事

• calloc(bytesForCapacity(newCapacity), 1)开辟内存
• end->set将开辟内存的最后一个位置存入sel = 1，imp = 第一个buket位置的地址

setBucketsAndMask 方法探究

image

setBucketsAndMask方法主要用来赋值

• 根据不同的架构系统向_bucketsAndMaybeMask 和 _maybeMask写入数据
• _occupied重置为 0

collect_free 方法探究

image

• collect_free方法主要是清空数据，回收内存

二倍扩容

image

• 当方法缓存到总容量的3/4或者7/8时，回进行二倍扩容
• 二倍扩容即开辟2倍新内存，释放旧内存

方法缓存

image

• 首先拿到buckets()，即开辟这块内存首地址，也就是第一个bucket的地址，buckets()既不是数组也不是链表，只是一块连续的内存
• cache_hash方法计算hash下标， cache_next方法处理hash冲突
• 如果当前的位置没有数据，就缓存该方法；如果该位置有方法且和你的方法一样的，说明该方法缓存过了，直接return；如果存在hash冲突，下标一样，sel不一样，此时会进行再次hash，冲突解决继续缓存

方法缓存写入方法 set

image

set方法：将imp和sel写入bucket中

insert方法调用流程

前面探究了insert方法的源码实现，接下来我们探究insert方法调用流程，是如何从调用实例方法走到cache里面的insert方法的？

• 首先在insert方法中打个断点，然后运行源码，查看函数调用栈

image

从堆栈信息可以看出insert的调用流程：_objc_msgSend_uncached --> lookUpImpOrForward --> log_and_fill_cache --> cache_t::insert

【问题】 _objc_msgSend_uncached方法又是何时调用的呢？

• 在objc4-818源码中搜索_objc_msgSend_uncached如下图

image

我们发现：objc_msgSend方法会调用_objc_msgSend_uncached，至此整个流程就串联起来了

• 方法调用的本质就是消息发送，即调用objc_msgSend
• 方法缓存的调用流程：objc_msgSend --> _objc_msgSend_uncached --> lookUpImpOrForward --> log_and_fill_cache --> cache_t::insert