IOS底层探索Cache_t（一）

Cache_t的数据结构

1.下载objc818可调试源码

2.在main.m文件添加如下代码：

#import <Foundation/Foundation.h>
@interface ABPerson : NSObject

@end
@implementation ABPerson

@end

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        Class pClass = [ABPerson class];
        NSLog(@"%@",pClass);
    }
    return 0;
}
复制代码

3.通过lldb调试Cache_t的数据结构

• p/x pClass获取类对象的首地址
• p/x 0x0000000100008498 + 0x10首地址偏移16个字节拿到cache_t
• p (cache_t *)0x00000001000084a8打印cache_t地址
• p *$2查看cache_t结构

struct cache_t {
private:
    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
    };
复制代码

能够发现打印出的结构与objc源码中cache_t的结构相对应。

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;

    // 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
}
复制代码

cache_t中的insert方法里面是将SEL和IMP用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__
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
省略部分代码
}
复制代码

进一步说明了bucket_t是包装SEL和IMP的。

Cache_t的数据结构图

LLDB验证方法的存储

修改main.m文件代码：

@interface ABPerson : NSObject
-(void)saySomething;
@end
@implementation ABPerson
-(void)saySomething
{
    NSLog(@"saySomething");
}
@end

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

        ABPerson *p = [ABPerson alloc];
        Class pClass = [ABPerson class];
        NSLog(@"%@",pClass);
    
    }
    return 0;
}
复制代码

• p/x pClass获取类对象的首地址
• p/x 0x00000001000084b8 + 0x10首地址偏移16个字节拿到cache_t
• p (cache_t *)0x00000001000084c8打印cache_t地址
• p *$2查看cache_t结构
• p [p saySomething]调用一次方法，让其有缓存
• p $3.buckets()[4] 获取哈希表里的值，当前在4号位置有值
• p $4.imp(nil,pClass)打印imp

小规模取样

1.参照objc_class结构定义ab_objc_class

struct objc_class : objc_object {
 省略部分代码
    // Class ISA;
    Class superclass;
    cache_t cache;             // formerly cache pointer and vtable
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
     省略部分代码
}
复制代码

struct ab_objc_class {
    Class isa;
    Class superclass;
    struct ab_cache_t cache;            
    struct ab_class_data_bits_t bits;
};
复制代码

2.参照cache_t定义ab_cache_t

struct cache_t {
private:
    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
    };
     省略部分代码
 }
复制代码

typedef uint32_t mask_t;
struct ab_cache_t {
    struct ab_bucket_t *_bukets; // 8
    mask_t    _maybeMask; // 4
    uint16_t  _flags;  // 2
    uint16_t  _occupied; // 2
};
复制代码

3.参照class_data_bits_t定义ab_class_data_bits_t

struct class_data_bits_t {
    friend objc_class;

    // Values are the FAST_ flags above.
    uintptr_t bits;
     省略部分代码
}
复制代码

struct ab_class_data_bits_t {
    uintptr_t bits;
};
复制代码

4.参照bucket_t定义ab_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__
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
省略部分代码
复制代码

struct ab_bucket_t {
    SEL _sel;
    IMP _imp;
};
复制代码

测试类ABPerson的定义

@interface ABPerson : NSObject

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

@end
复制代码

@implementation ABPerson
- (void)say1{
    NSLog(@"ABPerson say : %s",__func__);
}
- (void)say2{
    NSLog(@"ABPerson say : %s",__func__);
}
- (void)say3{
    NSLog(@"ABPerson say : %s",__func__);
}
- (void)say4{
    NSLog(@"ABPerson say : %s",__func__);
}
- (void)say5{
    NSLog(@"ABPerson say : %s",__func__);
}
- (void)say6{
    NSLog(@"ABPerson say : %s",__func__);
}
- (void)say7{
    NSLog(@"ABPerson say : %s",__func__);
}
+ (void)sayHappy{
    NSLog(@"ABPerson say : %s",__func__);
}
@end
复制代码

测试即输出：

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        ABPerson *p  = [ABPerson alloc];
        Class pClass = p.class;
        [p say1];
        [p say2];
        [p say3];
        [pClass sayHappy];
        struct ab_objc_class *ab_class = (__bridge struct ab_objc_class *)(pClass);
        NSLog(@"%hu - %u",ab_class->cache._occupied,ab_class->cache._maybeMask);
        
        for (mask_t i = 0; i<ab_class->cache._maybeMask; i++) {
            struct ab_bucket_t bucket = ab_class->cache._bukets[i];
            NSLog(@"%@ - %pf",NSStringFromSelector(bucket._sel),bucket._imp);
        }
        
        NSLog(@"Hello, World!");
    }
    return 0;
}
复制代码

没有报错，并且能够正常输出（输出结果后面还会分析到，这里先略过），说明小规模取样是可行的。

insert源码分析

void insert(SEL sel, IMP imp, id receiver);
复制代码

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
   省略部分代码
    mask_t newOccupied = occupied() + 1; // 1+1
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    //首次是空的cache
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        // INIT_CACHE_SIZE_LOG2 = 2,
        //INIT_CACHE_SIZE  = (1 << INIT_CACHE_SIZE_LOG2),
        //1左移两位就是4，INIT_CACHE_SIZE= 4
        if (!capacity) capacity = INIT_CACHE_SIZE;//初始化容量为4
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    //cache_fill_ratio:capacity * 3 / 4; 如果小于等于当前容积的3/4，正常插入数据
    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 {
    //如果大于当前容积的3/4，就进行容积的2倍扩容 ：4*2 = 8
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        //分配内存
        reallocate(oldCapacity, capacity, true);
    }

    bucket_t *b = buckets();
    //capacity首次容量为4
    mask_t m = capacity - 1; // 4-1=3  8-1 = 7
    //通过cache_hash得到哈希地址
    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 {
         //sel首次加入进来
        if (fastpath(b[i].sel() == 0)) {
            incrementOccupied(); //occupied++;
            //bucket插入sel和imp
            b[i].set<Atomic, Encoded>(b, sel, imp, cls());
            return;
        }
        //已存在sel就跳过
        if (b[i].sel() == sel) {
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
        }
        //cache_next: (i+1) & mask
    } while (fastpath((i = cache_next(i, m)) != begin));

    bad_cache(receiver, (SEL)sel);
#endif // !DEBUG_TASK_THREADS
}

复制代码

ALWAYS_INLINE
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    bucket_t *oldBuckets = 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

    ASSERT(newCapacity > 0);
    ASSERT((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
   //存储newBuckets指针
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
    //回收旧内存
        collect_free(oldBuckets, oldCapacity);
    }
}

复制代码

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
#ifdef __arm__
    mega_barrier();
    //存储newBuckets指针
    _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_relaxed);
    mega_barrier();
    //存储newMask值
    _maybeMask.store(newMask, memory_order_relaxed);
    _occupied = 0;
#elif __x86_64__ || i386
    // ensure other threads see buckets contents before buckets pointer
    _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_release);

    // ensure other threads see new buckets before new mask
    _maybeMask.store(newMask, memory_order_release);
    _occupied = 0;
#else
#error Don't know how to do setBucketsAndMask on this architecture.
#endif
}
复制代码

小规模取样中调用了say1、say2、say3，输出cache._occupied = 1，cache._maybeMask = 7。方法存储也不是按顺序存储的。
现在去掉一个，只调用say1、say2：

输出cache._occupied = 2，cache._maybeMask = 3。

根据上面分析的原理：

• 初始化容量为4，mask = capacity - 1所以为cache._maybeMask = 3，当前调用了2个方法所以cache._occupied = 2
• 调用3个方法后：newOccupied = occupied() + 1，即newOccupied = 3

newOccupied + CACHE_END_MARKER = 3 + 1 = 4 > capacity * 3 / 4 = 3，

扩容为2倍的capacity，即capacity = 2 * 4 = 8，mask = capacity - 1，

所以cache._maybeMask = 8 - 1 = 7，又因为分配空间的时候，collect_free回收旧的内存，之前的被清空，只有新的方法say3加进去，所以cache._occupied = 1。因为是哈希表存储的说以并不是从头开始纯粹的。

最后，附上插入分析图：