类的内存布局之cache_t

在类的编译成cpp的文件中，了解到编译期数据，方法的存储以及类和元类的相关信息。现在则根据源码，了解具体的类的结构

objc_class

在编译文件中，可以看到Class的定义是 struct objc_class * 的指针。看下源码中objc_class 的定义

struct objc_object {
    Class _Nonnull isa  OBJC_ISA_AVAILABILITY;
};

struct objc_class : objc_object {
    // Class ISA;
    Class superclass;
    cache_t cache;             // formerly cache pointer and vtable
    class_data_bits_t bits;  
    ...
}

cache_t

从lldb命令查看数据

(lldb) x/4gx LGPerson.class
0x1000023a0: 0x0000000100002378 0x0000000100333140 
// 根据objc_class 的机构，第一个8字节时isa，第二个8字节时superclass。
// 下一个地址就是cache_t的地址
0x1000023b0: 0x000000010072c110 0x0001803400000003

// 0x1000023a0 时只想LGPerson.class 内存的地址，也就是一个指针，
// 加16个字节就是只想cache_t的内存地址
// 所以 0x000000010072c110 时cache_t 的首地址
(lldb) p (cache_t *) 0x000000010072c110
(cache_t *) $3 = 0x000000010072c110
(lldb) p * $3
(cache_t) $4 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x00007fff7757d6f8 {
      _sel = {
        std::__1::atomic<objc_selector *> = (null)
      }
      _imp = {
        std::__1::atomic<unsigned long> = 8462954688753721208
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 3262288
  }
  _flags = 0
  _occupied = 0
}
// 计算一下cache_t 的内存大小 16个字节。用来计算下面的bit的起始地址
(lldb) p sizeof($4) 
(unsigned long) $5 = 16

cache_t 的首地址距离类的首地址偏移16个字节（isa 8个字节 + superclass 8个字节）
cache_t结构体大小为16个字节。

cache_t 的定义

#if defined(__arm64__) && __LP64__
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16
#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 {
// 根据cache_t 打印出来的变量可知，当前的环境时 非__arm64__ CACHE_MASK_STORAGE_OUTLINED
#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
    // _maskAndBuckets 可以看作 _buckets 和mask同时存储的数据
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;
    ...
#if __LP64__  // 是  __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;
}

在debug的打印中，我们看到 cache_t 中有四个成员：

1. _buckets 是一个只含有一个类行为std::__1::atomic<bucket_t *> 变量的结构体，这个变量是一个指针，指向是一个bucket_t *
2. _mask // 1是sel & mask 作为散列的key。另外就是_mask 是cache_t的容量减1
3. _flags //
4. _occupied // 已经占用的数量

_maskAndBuckets

使用_maskAndBuckets 的时候，还有一下几个定义

使用 _maskAndBuckets
    // How much the mask is shifted by.
    // 是 buckets 指针所占的位数
    static constexpr uintptr_t maskShift = 48;
    
    // Additional bits after the mask which must be zero. msgSend
    // takes advantage of these additional bits to construct the value
    // `mask << 4` from `_maskAndBuckets` in a single instruction.
    // 就是
    static constexpr uintptr_t maskZeroBits = 4;
    
    // The largest mask value we can store.
    static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
    
    // The mask applied to `_maskAndBuckets` to retrieve the buckets pointer.
    // 可以用来计算出  buckets 指针的 掩码。 1 向右移动 44（44 - 4） 位 然后减1 
    // 可以知道就是 从第三位开始到第 43位 存储的就是 buckets的指针地址数据
    // 所以后续的 44 位到64 位存储的 mask 数据。
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;

在 CACHE_MASK_STORAGE_HIGH_16 环境下 _maskAndBuckets 的存储布局

• 3 - 43 位存储的是 buckets指针的地址（1 - 2 两个位置全位0）
• 44 - 64 位存储的是 mak 容量

同样分析 CACHE_MASK_STORAGE_LOW_4 环境。可以知道

• 1- 4 位存储的是mask，容量
• 后续的位置存储的 是 buckets的地址

这三种环境，使用不同的存储方式进行存储buckets 和mask。后两种则是在优化容量

_occupied

已经存储的方法数量。在insert方法中，存储之后会执行 +1 操作

void cache_t::incrementOccupied() 
{
    _occupied++;
}
...
// 在insert 新的方法缓存方法中调用的
void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver){
    ...

        if (fastpath(b[i].sel() == 0)) {
            // 设置自己的 _occupied 加1
            incrementOccupied();
            // 设置对应的方法名，实现，以及类
            b[i].set<Atomic, Encoded>(sel, imp, cls);
            return;
        }
    ...
}

_mask

既是cache_t的容量-1。 也用于计算散列key（hashkey）的值

// Class points to cache. SEL is key. Cache buckets store SEL+IMP.
// Caches are never built in the dyld shared cache.
// cache存储的hash值计算 mask 是当前容量大小-1
static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;
}
// 加1计算下一个hash  
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}
// 可以看出 mask 存储的就是容量-1
unsigned cache_t::capacity()
{
    return mask() ? mask()+1 : 0; 
}
// 对应的获取方法。
mask_t cache_t::mask() 
{
    return _mask.load(memory_order::memory_order_relaxed);
}

类cache_t的方法存储逻辑

进行发送消息时 lookUpImpOrForward -> log_and_fill_cache

IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
    ...
    // Optimistic cache lookup
    if (fastpath(behavior & LOOKUP_CACHE)) {
        // 去混存中查找。是在汇编中写的方法
        imp = cache_getImp(cls, sel);
        if (imp) goto done_nolock;
    }
    ...
 done: // 查找结束后，会将方法存入类的cache_t中
    log_and_fill_cache(cls, imp, sel, inst, curClass);
    runtimeLock.unlock();
 done_nolock:
    if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
        return nil;
    }
    return imp;
}
static void log_and_fill_cache(Class cls, IMP imp, SEL sel, id receiver, Class implementer)
{
    ...
    cache_fill(cls, sel, imp, receiver);
}
void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
    ...
#if !DEBUG_TASK_THREADS
    // Never cache before +initialize is done
    if (cls->isInitialized()) {
        cache_t *cache = getCache(cls);
#if CONFIG_USE_CACHE_LOCK
        mutex_locker_t lock(cacheUpdateLock);
#endif
        // 将类，sel，imp插入累的chache_t
        cache->insert(cls, sel, imp, receiver);
    }
    ...
}

实例对象在发送消息是，msg_send 会先去查找方法的实现。

1. 方法调用会找到lookUpImpOrForward。
2. lookUpImpOrForward 查找到方法的实现imp后，或存储在对应类的cache_t中。

cache_t的插入函数

// cache_t 插入方法实现
ALWAYS_INLINE 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());

    // Use the cache as-is if it is less than 3/4 full
    // 使用量加1 
    mask_t newOccupied = occupied() + 1;
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    
    //INIT_CACHE_SIZE 4 小概率执行，初始化容量位4。 capacity容量
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE; 
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    // fastpath 大概率会执行下面的这句。 当使用量没有达到 容量的 3/4 继续使用。
    // 否则会执行下面的，容量*2  翻倍。（有个最大值 1 << 16  0x10000 ）
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) {
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);
    }
    // 获取buckets
    bucket_t *b = buckets();
    //  容量-1
    mask_t m = capacity - 1;
    // 参考一下hashmap 碰撞检测
    // 根据sel和 容量减1 计算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 because the
    // minimum size is 4 and we resized at 3/4 full.
    do {
        if (fastpath(b[i].sel() == 0)) {
            // 设置自己的 _occupied 加1
            incrementOccupied();
            // 设置对应的方法名，实现，以及类
            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;
        }
    // while 计算下一个的地址  index + 1
    } while (fastpath((i = cache_next(i, m)) != begin));

    cache_t::bad_cache(receiver, (SEL)sel, cls);
}

cache_t 的存储逻辑

1. cache_t使用hash表进行存储方法缓存。
2. hash表的index是根据 sel & mask 获取。其中mask为cache_t 的容量大小减1。这样保证了产生的index 不会超出容量（从0开始）。
3. 当使用的数量超过了容量的四分之三。会进行扩容。容量翻倍。
4. cache_t中的Occupied代表着使用的容量，在设置buckets都会自动加1
5. mask 则即使用户hash计算的掩码，也是cache_t容量大小的-1。

reallocate

// 根据容量，创建一个 buckets 数组。返回数组指针
bucket_t *allocateBuckets(mask_t newCapacity)
{
    // Allocate one extra bucket to mark the end of the list.
    // 在结束的位值创建一个额外的buckte对象去标记list的结尾
    // This can't overflow mask_t because newCapacity is a power of 2.
    //  newCapacity 是2 的幂，意义 不会溢出 mask_t
    // 计算大小 数量 * sizeof(bucket)  
    // 返回指针
    bucket_t *newBuckets = (bucket_t *)
        calloc(cache_t::bytesForCapacity(newCapacity), 1);
    
    // 返回数组中 最后一个 bucket地址的地址
    bucket_t *end = cache_t::endMarker(newBuckets, newCapacity);

    // 对最后一个bucket特殊处理
#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
    // End marker's sel is 1 and imp points to the first bucket.
    end->set<NotAtomic, Raw>((SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    
    if (PrintCaches) recordNewCache(newCapacity);

    return newBuckets;
}

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    bucket_t *oldBuckets = buckets();
    // 分配内存，并且标记最后一个bucket
    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);
    
    // 存储 bucket数组指针 和 容量 
    // 不同环境存储方法不同
    setBucketsAndMask(newBuckets, newCapacity - 1);
    // 是否需要释放以前的地址
    // 当以前是空的，不需要是释放
    // 如果以前是有数据，是扩容，就释放原先的内容
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
    }
}

• 根据容量和bucket的大小 分配新的内存空间
• 标记bucket 数组的最后一个位置
• 按需释放原数组

explicit_atomic<struct bucket_t *> _buckets;

_buckets 是一个存储着sel和对应imp的数组。成员时struct bucket_t 类型。

关于 explicit_atomic<T> 类型可以看文章最下面的扩展。可以看作是一个是有一个 T成员的结构体，不过这个结构体必须使用显示创建函数而且是原子操作。

// $4 是上面从类中获取到的cache_t的结构体
(lldb) p/x $4._buckets
(explicit_atomic<bucket_t *>) $8 = {
  std::__1::atomic<bucket_t *> = 0x00007fff7757d6f8 {
    _sel = {
      std::__1::atomic<objc_selector *> = 0x78632e0074696e69 (null)
    }
    _imp = {
      std::__1::atomic<unsigned long> = 0x7572747365645f78
    }
  }
}
// 计算成员$4._buckets 的大小
(lldb) p sizeof($4._buckets)
(unsigned long) $12 = 8
// 从cache_t开始的内存数据。 在前8个字节的数据  0x00007fff7757d6f8 就是  _buckets的数据，从上面看到是一个指针。
(lldb) x/4xg 0x000000010072c110
0x10072c110: 0x00007fff7757d6f8 0x000000000031c750
0x10072c120: 0x0000000000000000 0x0000000000000000

// 也可以直接用 bucket_t的类型去取这个变量。获取数据，（只是使用不同的类型获取同一块内存的数据，类型不同，提供的方法会不同）
(lldb) p (bucket_t *)0x00007fff7757d6f8
(bucket_t *) $9 = 0x00007fff7757d6f8
(lldb) p *$9
(bucket_t) $10 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null)
  }
  _imp = {
    std::__1::atomic<unsigned long> = 8462954688753721208
  }
}
// 可以看出和第一种 (explicit_atomic<bucket_t *>) 获取到的数据里具体的方法是一样的。

在cache_t中 _buckets 负责存储着方法的sel和imp数组。

1. _buckets占用8个字节。
2. 既可以通过cache_t的struct bucket_t *buckets(); 方法获取，也可以直接使用bucket_t * 来进行取值。这个和explicit_atomic<struct bucket_t *>定义有关。

struct bucket_t

// 
typedef struct objc_selector *SEL;

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 // 打印出来的结果来看，环境位非 __arm64__
    explicit_atomic<SEL> _sel;   // 
    explicit_atomic<uintptr_t> _imp;
#endif
...
}
// 断点中的调试数据
(lldb) p this // 就是bucket_t *
(bucket_t *) $18 = 0x0000000100725e20
(lldb) p *this
(bucket_t) $19 = {
  _sel = {
    std::__1::atomic<objc_selector *> = ""
  }
  _imp = {
    std::__1::atomic<unsigned long> = 3262264
  }
}
(lldb) p sizeof(_imp)
(unsigned long) $14 = 8
(lldb) p sizeof(_sel)
(unsigned long) $24 = 8
// bucket_t的第一个值是sel 
// 所以 bucket_t的首地址就是其内部explicit_atomic<SEL> _sel 的首地址
(lldb) p this
(bucket_t *) $25 = 0x0000000100725e20
// 渠道 _sel的值，是objc_selector * 方法名
(lldb) p (objc_selector *)0x0000000100725e20
(objc_selector *) $23 = "init"

cache_t中的_bucket 是一个指向bucket_t类型数组的指针
bucket_t是负责存储方法名和IMP对应的结构体 16个字节

1. _sel 存储着方法名. 8个字节(objc_selector * )类型
2. _imp 存储着imp地址专程 uintprt_t类型的数据 也是8个字节

bucket_t的方法

^ 是 逐位 异或运算符。即两个位只有一个1则为1，否则为0

uintptr_t modifierForSEL(SEL newSel, Class cls) const {
        return (uintptr_t)&_imp ^ (uintptr_t)newSel ^ (uintptr_t)cls;
}
// 获取imp 可以看出imp的存储方式，跟cls/sel进行了 ^ 异或操作
inline IMP imp(Class cls) const {
        uintptr_t imp = _imp.load(memory_order::memory_order_relaxed);
        if (!imp) return nil;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
        SEL sel = _sel.load(memory_order::memory_order_relaxed);
        return (IMP)
            ptrauth_auth_and_resign((const void *)imp,
                                    ptrauth_key_process_dependent_code,
                                    modifierForSEL(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
    }
// bucket_t 设置方法和对应的数据
void bucket_t::set(SEL newSel, IMP newImp, Class cls)
{
    ASSERT(_sel.load(memory_order::memory_order_relaxed) == 0 ||
           _sel.load(memory_order::memory_order_relaxed) == newSel);

    // objc_msgSend uses sel and imp with no locks.
    // It is safe for objc_msgSend to see new imp but NULL sel
    // (It will get a cache miss but not dispatch to the wrong place.)
    // It is unsafe for objc_msgSend to see old imp and new sel.
    // Therefore we write new imp, wait a lot, then write new sel.
    // 在非 __arm64 下，这个判断为false 会等于(uintptr_t)newImp。
    // 可以使用 p (void(*)(void))0x0998 打印方法
    uintptr_t newIMP = (impEncoding == Encoded
                        ? encodeImp(newImp, newSel, cls)
                        : (uintptr_t)newImp);

    if (atomicity == Atomic) {
        // _imp 存储的是 IMP地址的int类型
        _imp.store(newIMP, memory_order::memory_order_relaxed);
        
        // 当对应的sel不等于 要存储的newSel 重新赋值。
        // 应该是没用锁，又可能会不安全。所以再一次判断
        // It is unsafe for objc_msgSend to see old imp and new sel.
        // Therefore we write new imp, wait a lot, then write new sel.
        if (_sel.load(memory_order::memory_order_relaxed) != newSel) {
#ifdef __arm__
            mega_barrier();
            _sel.store(newSel, memory_order::memory_order_relaxed);
#elif __x86_64__ || __i386__
            _sel.store(newSel, memory_order::memory_order_release);
#else
#error Don't know how to do bucket_t::set on this architecture.
#endif
        }
    } else {
        _imp.store(newIMP, memory_order::memory_order_relaxed);
        _sel.store(newSel, memory_order::memory_order_relaxed);
    }
}

主要是存储_sel和_imp两个数据。需要注意的是先设置IMP。

1. 因为如果先设置newsel 会存在不安全的情况（比如设置了newsel，为设置newImp是，有查找查到了oldImp），所以先设置newImp。然后再去设置newSel

总结

x86

类的内存布局之cache_t.png

arm64

cache_t arm64.png

cache的存储逻辑： 使用hash表的方法进行存储，hashkey 是 mask & sel 计算而来，通过向下计算解决hashkey冲突

]