Objective-C类结构分析(cache_t)

在Objective-C中Class底层实现其实是一个objc_class类型的结构体

/// An opaque type that represents an Objective-C class.
typedef struct objc_class *Class;

查看源码，可以看到objc_class的结构如下

struct objc_class : objc_object {
    Class superclass;
    cache_t cache;             // formerly cache pointer and vtable
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
}

objc_class继承于objc_object结构体，objc_object里面只有个isa_t isa指针，这里就不再分析，想了解更多可以看往期内容。

除了isa指针外，可以看到还有个Class类型的superclass，很明显这个是指向父类的指针。

然后就是cache_t类型的cache，从源码中查找其结构，只需要提取需要的部分。然后又发现CACHE_MASK_STORAGE宏对应的不同的情况，搜索宏CACHE_MASK_STORAGE可以找到如下

#if defined(__arm64__) && __LP64__
    #if TARGET_OS_OSX || TARGET_OS_SIMULATOR
    #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
    #else
    #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16
    #endif
#elif defined(__arm64__) && !__LP64__
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_LOW_4
#else
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_OUTLINED
#endif

可得只有CACHE_MASK_STORAGE==CACHE_MASK_STORAGE_HIGH_16的时候才是需要的部分，可以简化cache_t结构如下

struct cache_t {
    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;
    };

    // _bucketsAndMaybeMask is a buckets_t pointer in the low 48 bits
    // _maybeMask is unused, the mask is stored in the top 16 bits.
};

看注释，_bucketsAndMaybeMask是一个低48位存储着buckets_t的指针，_maybeMask在当前架构下unused，mask存在了_bucketsAndMaybeMask高16位里面。

搜索flags，发现参与FAST_CACHE_ALLOC_MASK位运算，应该FAST CACHE标志位

搜索_occupied，发现在setBucketsAndMask的时候，被赋值0，在cache_t::insert方法中找到调用了 _occupied++，insert是插入新方法缓存，所以这个值应该为当前cache已存储缓存方法的数量。

方法最终是存储在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
};

可以看到这是一个存放方法指针和方法名的结构体，需要注意的是，arm64架构下方法实现在前方法名在后。

SEL _sel为什么是方法名字？搜索SEL可得，SEL 是一个struct objc_selector的指针

/// An opaque type that represents a method selector.
typedef struct objc_selector *SEL;

然后写以下代码测试下

SEL sel = @selector(run);
NSLog(@"%s",sel);

运行后输出结果如下图

可以看出_sel是指向方法名的指针。

void bucket_t::set(bucket_t *base, SEL newSel, IMP newImp, Class cls)方法可以看到具体写入过程

template<Atomicity atomicity, IMPEncoding impEncoding>
void bucket_t::set(bucket_t *base, SEL newSel, IMP newImp, Class cls)
{
    uintptr_t encodedImp = (impEncoding == Encoded
                            ? encodeImp(base, newImp, newSel, cls)
                            : (uintptr_t)newImp);

    // LDP/STP guarantees that all observers get
    // either imp/sel or newImp/newSel
    stp(encodedImp, (uintptr_t)newSel, this);
}

可以看到，stp写入的是方法名和加密后的方法，可以找到stp方法实现如下

stp(uintptr_t onep, uintptr_t twop, void *destp)
{
    __asm__ ("stp %" p "[one], %" p "[two], [%x[dest]]"
             : "=m" (((uintptr_t *)(destp))[0]),
               "=m" (((uintptr_t *)(destp))[1])
             : [one] "r" (onep),
               [two] "r" (twop),
               [dest] "r" (destp)
             : /* no clobbers */
             );
}

通过汇编把两个值写入到bucket_t里面，加快了写入速度。

分析完方法时如何写入的，继续看bucket_t是怎么写入的。在objc-cache.mm文件中搜索.set找到void cache_t::insert(SEL sel, IMP imp, id receiver)方法，简化后代码如下

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    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);
}

先获取capacity，搜索capacity()方法，发现capacity = mask() + 1

unsigned cache_t::capacity() const
{
    return mask() ? mask()+1 : 0; 
}

继续搜索找到mask的赋值和取值过程

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    uintptr_t buckets = (uintptr_t)newBuckets;
    uintptr_t mask = (uintptr_t)newMask;

    ASSERT(buckets <= bucketsMask);
    ASSERT(mask <= maxMask);

    _bucketsAndMaybeMask.store(((uintptr_t)newMask << maskShift) | (uintptr_t)newBuckets, memory_order_relaxed);
    _occupied = 0;
}

mask_t cache_t::mask() const
{
    uintptr_t maskAndBuckets = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return maskAndBuckets >> maskShift;
}

搜索setBucketsAndMask，可以找到

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);

    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
        collect_free(oldBuckets, oldCapacity);
    }
}

可以得出capacity是buckets的长度，mask是capacity-1。

继续分析insert方法，

第一个if是当cache为空的时候，初始化buckets。

第二个和第三个if分别是新的长度小于等于容器的3/4或者小于等于容器的大小的时候什么也不做。

第四个是新的长度大于容器的长度时，以2倍的capacity扩容，并且释放之前的buckets。

在下面就是插入逻辑，通过buckets()获取bucket_t 数组指针，通过长度减1获取mask，再通过sel和mask算出插入的索引。

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    uintptr_t value = (uintptr_t)sel;
#if CONFIG_USE_PREOPT_CACHES
    value ^= value >> 7;
#endif
    return (mask_t)(value & mask);
}

do while是插入方法。如果，当前索引下的bucket没有被使用或者是当前存入的方法和要存入的方法一样的话就会返回。如果有值且不一样的话，计算新的索引继续插入。具体索引算法如下

static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}

最后就是，遍历完buckets，方法依旧没能插入成功，就会Crash。

综上，cache_t里面有个散列表buckets，buckets里面存储bucket_t，bucket_t里面存储着方法实现和方法名。方法存入buckets的索引是以sel和mask算出的。如果存入的方法大于buckets的长度后，会以2倍的长度扩容一个新的buckets，然后释放旧的。