众所周知 Objective-C 在查找办法的 imp 时会先查找缓存，那么缓存是如何完结的呢？本文就记录下阅览 runtime 源码的过程。

objc-runtime-new.h

先从 objc-runtime-new.h 中 objc_class 的界说开端。

struct objc_class : objc_object {
    // Class ISA;
    Class superclass;
    cache_t cache;
    // ...
}
struct cache_t {
private:
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask;
    // ...
}

在 objc_class 中有一个结构体 cache_t，这个就是办法的缓存。而 cache_t 的榜首个成员变量是 _bucketsAndMaybeMask，了解数据结构相关知识的同学应该会立刻联想到哈希表。没错，办法缓存就是经过哈希表完结的。

再细心看看 cache_t ，依据CACHE_MASK_STORAGE宏界说了不同的字段，而 CACHE_MASK_STORAGE 界说在 objc-config.h 中。

#if defined(__arm64__) && __LP64__
#if TARGET_OS_EXCLAVEKIT
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
#elif 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

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    //...
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
    //...
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    // _bucketsAndMaybeMask is a buckets_t pointer in the low 48 bits
    // How much the mask is shifted by.
    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.
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
    // ...
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
    // ...
#else
#error Unknown cache mask storage type.
#endif

以 __arm64__ && __LP64__ 为例：

界说了成员变量：

maskShift mask 偏移量 48
maskZeroBits mask 后方必须为 0 的 bits 4
maxMask mask 最大值 1111 1111 1111 1111，即 16 bits
- 1 << (64 – maskShift) 表明 1 左移 16 位，成果为 1 0000 0000 0000 0000
- 1 0000 0000 0000 0000 – 1 ，成果为 0 1111 1111 1111 1111
bucketsMask buckets 的 mask 1111 … 1111 (44 个 1)
- 1 << (maskShift – maskZeroBits) 表明 1 左移 44 位，成果为 1 0000 … 0000 (44 个 0)
- 1 0000 … 0000 (44 个 0) – 1，成果为 1111 … 1111 (44 个 1)

界说了以下办法：

private:
    mask_t mask() const;
    static bucket_t *allocateBuckets(mask_t newCapacity);
public:
    unsigned capacity() const;
    struct bucket_t *buckets() const;
    Class cls() const;
    void insert(SEL sel, IMP imp, id receiver);

下面到 objc-cache.mm 看看详细完结

objc-cache.mm

从最主要 insert 办法开端，大致分为三个部分。

Part 1 initialize 判别

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    // Never cache before +initialize is done
    if (slowpath(!cls()->isInitialized())) {
        return;
    }
    ASSERT(sel != 0 && cls()->isInitialized());
    // Part 2
    // Part 3
}

榜首部分是对 cls +initialize 办法是否执行完结的判别，假如没有则直接 return

Part 2 初始化及扩容

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    // Part 1
    // 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.
    }
    else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);
    }
    // Part 3
}

isConstantEmptyCache

首先会获取哈希表当时的元素个数 occupied 以及容量 capacity，然后经过isConstantEmptyCache判别哈希表是否为空

bool cache_t::isConstantEmptyCache() const
{
    return
        occupied() == 0  &&
        buckets() == emptyBucketsForCapacity(capacity(), false);
}
struct bucket_t *cache_t::buckets() const
{
    uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return (bucket_t *)(addr & bucketsMask);
}

其间经过 buckets 函数获取了当时桶数组，是将_bucketsAndMaybeMask 指针与 bucketsMask 做位与，前面咱们知道了bucketsMask 的值为 44，所以 _bucketsAndMaybeMask 中的低 44 位存储的是 buckets 数组的地址。

INIT_CACHE_SIZE

再回到 insert 中，假如哈希表为空则进行初始化分配空间，大小为 INIT_CACHE_SIZE, INIT_CACHE_SIZE为枚举值

/* Initial cache bucket count. INIT_CACHE_SIZE must be a power of two. */
enum {
#if CACHE_END_MARKER || (__arm64__ && !__LP64__)
    // When we have a cache end marker it fills a bucket slot, so having a
    // initial cache size of 2 buckets would not be efficient when one of the
    // slots is always filled with the end marker. So start with a cache size
    // 4 buckets.
    INIT_CACHE_SIZE_LOG2 = 2,
#else
    // Allow an initial bucket size of 2 buckets, since a large number of
    // classes, especially metaclasses, have very few imps, and we support
    // the ability to fill 100% of the cache before resizing.
    INIT_CACHE_SIZE_LOG2 = 1,
#endif
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2),
};

这儿又引入了一个新的宏界说 CACHE_END_MARKER

#if __arm__  ||  __x86_64__  ||  __i386__
// objc_msgSend has few registers available.
// Cache scan increments and wraps at special end-marking bucket.
#define CACHE_END_MARKER 1
#elif __arm64__ && !__LP64__
// objc_msgSend has lots of registers available.
// Cache scan decrements. No end marker needed.
#define CACHE_END_MARKER 0
#elif __arm64__ && __LP64__
// objc_msgSend has lots of registers available.
// Cache scan decrements. No end marker needed.
#define CACHE_END_MARKER 0
#else
#error unknown architecture
#endif

从注释和命名能够得知，这是用于符号缓存的终止位置，在 __arm64__ && __LP64__ 的 case 下有很多寄存器，缓存扫描是递减的，不需要 marker 。

所以这儿缓存的初始大小是 1 << 1 , 即 2 。

reallocate

再再回到 insert 中，调用了 reallocate 函数

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

获取旧的 buckets，调用allocateBuckets拓荒新的空间，调用 setBucketsAndMask 设置新的 buckets 和 mask 到 _bucketsAndMaybeMask, mask 值为当时 buckets 的最大 index。最后再释放旧的 buckets

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_release);
    _occupied = 0;
}

这儿用到前面在 .h 中看到的 maskShift（48），所以这儿能够得出 _bucketsAndMaybeMask 的高 16 位是 mask，低 44 位是 buckets，中间 4 位是 maskZeroBits 为 0

cache_fill_ratio

再再再回到 insert 中，会调用 cache_fill_ratio判别是否需要扩容

#if __arm__  ||  __x86_64__  ||  __i386__
// Historical fill ratio of 75% (since the new objc runtime was introduced).
static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 3 / 4;
}
#elif __arm64__ && !__LP64__
// Historical fill ratio of 75% (since the new objc runtime was introduced).
static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 3 / 4;
}
#elif __arm64__ && __LP64__
// Allow 87.5% fill ratio in the fast path for all cache sizes.
// Increasing the cache fill ratio reduces the fragmentation and wasted space
// in imp-caches at the cost of potentially increasing the average lookup of
// a selector in imp-caches by increasing collision chains. Another potential
// change is that cache table resizes / resets happen at different moments.
static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 7 / 8;
}
#else
#error unknown architecture
#endif

Part 3 刺进数据

再再再再回到 insert 中，看看第三部分

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

cache_hash

经过 cache_hash 函数核算 sel 在 buckets 中的索引

// Class points to cache. SEL is key. Cache buckets store SEL+IMP.
// Caches are never built in the dyld shared cache.
static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    uintptr_t value = (uintptr_t)sel;
    //...
    return (mask_t)(value & mask);
}

和哈希表的基本思想一致，把 sel 与 mask 做位与运算，等同于模运算 % (mask + 1)。

do – while

再再再再再回到 insert 中，是一个 do – while 循环

假如 bucket 的 sel 值为 0，则表明这是一个空槽能够刺进数据。
假如 sel 的值和当时 sel 持平，则表明其他线程现已缓存过该办法。
假如都不满意，则会调用 cache_next 查找下一个位置，是哈希表处理哈希冲突方法的开放寻址-线性探测

#if CACHE_END_MARKER
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}
#elif __arm64__
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}
#else

在 __arm64__ && __LP64__ case 下，只需 i 不为 0，就会一直递减，和前面 CACHE_END_MARKER 的注释相对应。

总结

办法缓存是根据哈希表的数据结构完结的
确定索引的哈希算法是将 sel 与 buckets 大小做位与运算，即取余数
哈希表处理哈希冲突的方法是线性探查

以上内容根据 objc4-906.2 纯理论阅览所写，省去了部分逻辑分支，如有过错，欢迎纠正。

Objective-C 方法缓存探密

objc-runtime-new.h

objc-cache.mm

Part 1 initialize 判别

Part 2 初始化及扩容

isConstantEmptyCache

INIT_CACHE_SIZE

reallocate

cache_fill_ratio

Part 3 刺进数据

cache_hash

do – while

总结

作者信息

推广

Objective-C 方法缓存探密

objc-runtime-new.h

objc-cache.mm

Part 1 initialize 判别

Part 2 初始化及扩容

isConstantEmptyCache

INIT_CACHE_SIZE

reallocate

cache_fill_ratio

Part 3 刺进数据

cache_hash

do – while

总结

相关文章

还没35岁的我已经快秃了

Flutter中Globalkey和Get是如何获取BuildContext的

LeetCode – #166 分数到小数

Android源码分析 – Framework层的ContentProvider全解析

作者信息

推广