Objc4-818底层探索(六):cache

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
...

之前我们探索类时候已经了解objc_calss中isa, superclass, bits, 这次介绍下cache。

缓存:
        原始意义是指访问速度比一般随机存取存储器（RAM）快的一种高速存储器，通常它不像系统主存那样使用DRAM技术，而使用昂贵但较快速的SRAM技术。缓存的设置是所有现代计算机系统发挥高性能的重要因素之一。

        是指可以进行高速数据交换的存储器，它先于内存与CPU交换数据，因此速率很快。

Cache_t

cache是一个cache_t类型, 我们先看下cache_t底层

struct cache_t {
private:
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask;
    union {
        struct {
            explicit_atomic<mask_t>    _maybeMask;
#if __LP64__ // 当前系统支持LP64
            uint16_t                   _flags;
#endif
            uint16_t                   _occupied;
        };
        explicit_atomic<preopt_cache_t *> _originalPreoptCache;
    };

...
    static bucket_t *emptyBuckets();
    static bucket_t *allocateBuckets(mask_t newCapacity);
    static bucket_t *emptyBucketsForCapacity(mask_t capacity, bool allocate = true);
    static struct bucket_t * endMarker(struct bucket_t *b, uint32_t cap);
    void bad_cache(id receiver, SEL sel) __attribute__((noreturn, cold));
...

public:
    // The following four fields are public for objcdt's use only.
    // objcdt reaches into fields while the process is suspended
    // hence doesn't care for locks and pesky little details like this
    // and can safely use these.
    unsigned capacity() const;
    struct bucket_t *buckets() const;
    Class cls() const;

#if CONFIG_USE_PREOPT_CACHES
    const preopt_cache_t *preopt_cache() const;
#endif

    mask_t occupied() const;
...

   void insert(SEL sel, IMP imp, id receiver);
...
}

cache方法很多, 但因为缓存毕竟是存储某些东西, 所以肯定会有插入方法, 那么我们从cache_t插入方法入开始进行探索。 往下翻, 我们会发现插入方法insert

void insert(SEL sel, IMP imp, id receiver);

首先会注意到传入3个参数, 方法sel, 函数指针imp以及接收者receiver, 可看到cache主要用来进行存储方法, 接下来进入insert方法

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    ...    
    mask_t newOccupied = occupied() + 1;
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    ...
    // 从
    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
}

可看到主要是对mask_t, bucket_t做些操作

---

bucket_t

我们先看下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
// explicit_atomic 是加了原子性的保护(主要是加个锁)
...
    }

可以看见bucket_t主要缓存很多的sel, imp

bucket_t

接下来我们通过该lldb验证下方法存储

lldb获取buckets内容 lldb获取buckets内容指示图

先简单说几个注意点:

1. 留意cache存在class类里面, 所以要用类的首地址+平移去查找
2. cache前面有isa, superclass, 所以需要首地址平移8 + 8 = 16字节

返回来看lldb打印信息, 发现buckets里面没有值, _sel, _imp都为nil。
这是因为我们还没有调用方法, 固没有插入缓存。 我们可以lldb调用函数方法, 重新再打印一下buckets, 有

lldb获取buckets内容 lldb获取buckets内容指示图

调用方法之后, 发现buckets有内容了

这里稍微介绍个知识点哈希表也叫散列表

哈希表/散列表

    散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

而buckets就是这种哈希表形式存放的(例如: 可能buckets()[0]有值, 可能buckets()[1]有值...)

接来下看下我们怎么取buckets中的sel, imp, 返回看下struct bucket_t

struct bucket_t {
...
public:
 
    // 关键代码 sel 方法
    inline SEL sel() const { return _sel.load(memory_order_relaxed); }
...

// 关键代码 imp 方法
    inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls) const {
        uintptr_t imp = _imp.load(memory_order_relaxed);
        if (!imp) return nil;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
        SEL sel = _sel.load(memory_order_relaxed);
        return (IMP)
            ptrauth_auth_and_resign((const void *)imp,
                                    ptrauth_key_process_dependent_code,
                                    modifierForSEL(base, sel, cls),
                                    ptrauth_key_function_pointer, 0);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
        return (IMP)(imp ^ (uintptr_t)cls);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
        return (IMP)imp;
#else
#error Unknown method cache IMP encoding.
#endif
...
}

取sel & imp 取imp

这里留意下bucket_t里面的sel方法不需要传入参数, 而imp方法需要传2个参数, 一个bucket_t *base, Class cls。第一个传nil即可, 第二个要传对应的类。

---

cache 项目中实现

我们可以把cache源码拷贝到项目里面, 模拟下cache实现

typedef uint32_t mask_t;

struct sa_cache_t {
    
    struct sa_bucket_t *bucket;
    mask_t _maybeMask;
    uint16_t _flags;
    uint16_t _occupied;

};


struct sa_objc_class {
    Class isa;
    Class superclass;
    struct sa_cache_t cache;
};

struct sa_bucket_t {
    SEL _sel;
    IMP _imp;
};


int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        
        SATest *test = [SATest alloc];
        Class pclass = test.class;
        [test say1];
        
        struct sa_objc_class* sa_class = (__bridge struct sa_objc_class *)pclass;
        NSLog(@"cache._occupied: %u", sa_class->cache._occupied);
        NSLog(@"cache._maybeMask: %u", sa_class->cache._maybeMask);
        
        for(mask_t i = 0; i< sa_class->cache._maybeMask; i++) {
            struct sa_bucket_t b  = sa_class->cache.bucket[I];
            NSLog(@"sel: %@", NSStringFromSelector(b._sel));
            NSLog(@"imp: %p", b._imp);
        
        }
        
    }
    return 0;
}

解释

• 关于cache_t, 主要就是以下源码

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

① 以 explicit_atomic<mask_t> _maybeMask为例, _maybeMask类型主要是里面的泛型里面的mask_t, 所以外层的修饰符可以去掉, 直接mask_t _maybeMask;

② 外层union联合体, 但是我们重点要查看_maybeMask, _flags, _occupied里面信息, 原缓存我们不关注, 所以只保留原结构体成员

③ 关于__LP64__, 64架构, 编程模型

LP64
Mac_OS_X是满足__LP64__的固其结构体为

        struct {
            mask_t    _maybeMask;
            uint16_t                   _flags;
            uint16_t                   _occupied;
        };

④cache_t最后整理

struct cache_t {
    uintptr_t _bucketsAndMaybeMask;
        struct {
            mask_t    _maybeMask;
            uint16_t                   _flags;
            uint16_t                   _occupied;
        };
}

由于内层结构体完美满足字节对齐, 整体可整理为

struct sa_cache_t {
    
    uintptr_t _bucketsAndMaybeMask;
    mask_t _maybeMask;
    uint16_t _flags;
    uint16_t _occupied;

};

• 关于bucket_t, 看下源码

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

可知bucket_t是从_bucketsAndMaybeMask获取的, 那么sa_cache_t中用struct sa_bucket_t *bucket;替换explicit_atomic<mask_t> _maybeMask;。于是有

struct sa_bucket_t {
    SEL _sel;
    IMP _imp;
};


struct sa_cache_t {
    struct sa_bucket_t *bucket;
    mask_t _maybeMask;
    uint16_t _flags;
    uint16_t _occupied;
};

• 关于objc_class, 看下源码(只去关键内容即可)

struct objc_class : objc_object {
    // Class ISA;
    Class superclass;
    cache_t cache;             // formerly cache pointer and vtable
    // 只关心cache, cache后面无关的就不需要了    

}

整理后为

struct sa_objc_class {
    Class isa;
    Class superclass;
    struct sa_cache_t cache;
};

① cache用我们新的struct sa_cache_t即可
② objc_class中默认了isa, 但是自定义时候要写出来, 不然会找错
③ 只关心cache, cache之后就不需要, 不过写上也可以。例如, 加个bits可写成

struct sa_class_data_bits_t {
    uintptr_t bits;
};

struct sa_objc_class {
    Class isa;
    Class superclass;
    struct sa_cache_t cache;
    struct sa_class_data_bits_tbits;
};

结果

运行可看到有

模拟cache

因为我们只运行了1个方法, 缓存只有1个。我们执行2个方法, 就会有2个缓存, 如下

image.png

---

我们接下来针对上面的重写, 看下几个问题

问题一

occupied, maybeMask是什么? 怎么计算的?

问题二

为什么只执行1个方法缓存却有三个bucket?

问题三

问题三

加个7个对象方法, 1个类方法, 但是只缓存了5个实例方法? 缓存是怎么扩容的?

问题四

接下来我们加一个init方法进行打印, 可发现也缓存了init方法

init

我们先看下init方法, 发现底层执行的是objc_alloc_init

汇编

源码搜索下objc_alloc_init, 我们发现在NSObject中, 父类或者说是根类方法

objc_alloc_init

为什么init父类方法也缓存进去了?

探索

针对这些问题我们探索一下。首先我们留意到, 方法越多缓存越大, 那么cache肯定有一个增值方法吗查找cache_t。

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;
    };
...
    void incrementOccupied(); // 自增函数
...
    void insert(SEL sel, IMP imp, id receiver);
    void copyCacheNolock(objc_imp_cache_entry *buffer, int len);
    void destroy();
    void eraseNolock(const char *func);
...
};

发现有一个这个方法incrementOccupied()(increment: 增加, 增量 | occupied: 占用)
进去看一下(后面还有对_occupied 操作)

void cache_t::incrementOccupied() 
{
    让_occupied参数+1, 自增操作
    _occupied++;
}

接下来看下缓存肯定是跟buckets的插入有关, 所以我们再看下cache_t, 中的插入方法void insert(SEL sel, IMP imp, id receiver);

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
...
    // 占位符 + 1操作
    // 初始 occupied 为 1
    mask_t newOccupied = occupied() + 1; 
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        // 初始没有缓存走这个方法或者第一次进入的方法
        // INIT_CACHE_SIZE: 1<<2  // 4
        if (!capacity) capacity = INIT_CACHE_SIZE;
        // capacity初始为4, reallocate 方法源码在下面
        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.
        // 第二次进入cache_fill_ratio 是一个 3/4 容积计算方法, 主要是为了处理扩容
        // static inline mask_t cache_fill_ratio(mask_t capacity) {
        // return capacity * 3 / 4;
        // } 
    }
#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 {
        // 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 从_bucketsAndMaybeMask获取到地址buckects地址
    bucket_t *b = buckets();
    // 第一次时候capacity = 4, 4-1 = 3
    // 第二次时候capacity = 7, 8-1 = 7
    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-while循环
    do {
        // 方法为0, 可以理解成从未进入
        if (fastpath(b[i].sel() == 0)) {
             // Occupied + 1
            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;
        }
    // 防止hash冲突进行再次hash
    } while (fastpath((i = cache_next(i, m)) != begin));
...
}

• occupied 方法源码

mask_t cache_t::occupied() const
{
    // 只是将_occupied返回
    return _occupied;
}

• reallocate 方法源码

ALWAYS_INLINE


void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    // 1.第一次开辟会走。 2.扩容之后的也会走这里

    // 设置旧桶, 初始化新桶 
    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);

   // 给cache_t 第一个参数赋值
   // explicit_atomic<uintptr_t> _bucketsAndMaybeMask;
   // 第一个参数即存储buckets和MaybeMask
   // setBucketsAndMask主要设置新值释放旧值, 并且将_occupied设置为0
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    // freeOld: 第一次false, 扩容为true
    if (freeOld) {
        // 如果有原始的脏内存会做一次清空, 下面可以看详细源码
        // 扩容之后,里面之前数据都没有了
        collect_free(oldBuckets, oldCapacity);
    }
}


void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    // objc_msgSend uses mask and buckets with no locks.
    // It is safe for objc_msgSend to see new buckets but old mask.
    // (It will get a cache miss but not overrun the buckets' bounds).
    // It is unsafe for objc_msgSend to see old buckets and new mask.
    // Therefore we write new buckets, wait a lot, then write new mask.
    // objc_msgSend reads mask first, then buckets.

#ifdef __arm__
    // ensure other threads see buckets contents before buckets pointer
    // arm真机环境设置屏障, 保证 后面执行bucketsAndMaybeMask存储安全
   mega_barrier();

    // _bucketsAndMaybeMask存储新值, 释放旧值
    _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_relaxed);

    // ensure other threads see new buckets before new mask
    // 结束屏障
    mega_barrier();
    //  _maybeMask存储新值, 释放旧值
    _maybeMask.store(newMask, memory_order_relaxed);
    // 占位occupied 设置为0, 新桶时又把_occupied设置为0
    _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存储新值, 释放旧值
    _maybeMask.store(newMask, memory_order_release);
    //  占位occupied 设置为0, 新桶时又把_occupied设置为0
    _occupied = 0;
#else
#error Don't know how to do setBucketsAndMask on this architecture.
#endif
}

• cache_hash 哈希方法

// mask_t m = capacity - 1;
// mask_t begin = cache_hash(sel, m);
static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    // 把sel转成uintptr_t 类型
    uintptr_t value = (uintptr_t)sel;
#if CONFIG_USE_PREOPT_CACHES
    value ^= value >> 7;
#endif
    return (mask_t)(value & mask);
}

• bucket_t()

struct bucket_t *cache_t::buckets() const
{
    // 从`bucketsAndMaybeMask`获取buckets信息地址返回
    uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return (bucket_t *)(addr & bucketsMask);
}

• collect_free

// 针对扩容之前的脏内存, 做一清空操作
void cache_t::collect_free(bucket_t *data, mask_t capacity)
{
#if CONFIG_USE_CACHE_LOCK
    cacheUpdateLock.assertLocked();
#else
    runtimeLock.assertLocked();
#endif

    if (PrintCaches) recordDeadCache(capacity);

    // 直接掉底层清空, 回收操作
    _garbage_make_room ();
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    garbage_refs[garbage_count++] = data;
    cache_t::collectNolock(false);
}