前言

本篇记录探索objc_class中成员变量cache的数据结构，以及方法缓存的流程。

struct objc_class {
    Class isa;
    Class superclass;
    cache_t cache;       
    class_data_bits_t bits; 
    .....
}
复制代码

cache_t的数据结构

找到源码中cache_t的定义，先来看看cache_t的成员变量。

typedef uint32_t mask_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;
    };

    .....
    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld);
    unsigned capacity() const;
    struct bucket_t *buckets() const;
    Class cls() const;
    void insert(SEL sel, IMP imp, id receiver);
}
复制代码

__LP64__表示在64位系统下

cache_t有两个成员变量，源码中没有相关字段的注释，很难知道每个字段存的是啥。
bucket_t *buckets()方法中返回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
......
}
复制代码

bucket_t存储了方法的SEL和IMP.

用LLDB调试到SEL 和 IMP

定义一个Person类，并定义多个方法，如下

@interface Person : NSObject

-(void)func1;
-(void)func2;
-(void)func3;
-(void)func4;
-(void)func5;
-(void)func6;

@end

复制代码

int main() {
    @autoreleasepool {
        Person *p = [Person alloc];
        [p func1];
        [p func2];
        [p func3];
        [p func4];
        [p func5];
    }
    return 0;
}
复制代码

将断点设在[p func2]，此时已调用过func1方法，通过lldb打印此时的cache

(lldb) p/x [Person class]              ->获取类对象的地址
(Class) $1 = 0x0000000100008370 Person
(lldb) p (cache_t *)0x0000000100008380 ->地址偏移0x10
(cache_t *) $2 = 0x0000000100008380
(lldb) p *$2                           ->打印此时的cache
(cache_t) $3 = {
  _bucketsAndMaybeMask = {
    std::__1::atomic<unsigned long> = {
      Value = 4301326736
    }
  }
   = {
     = {
      _maybeMask = {
        std::__1::atomic<unsigned int> = {
          Value = 3
        }
      }
      _flags = 32784
      _occupied = 1
    }
    _originalPreoptCache = {
      std::__1::atomic<preopt_cache_t *> = {
        Value = 0x0001801000000003
      }
    }
  }
}
复制代码

调用buckets()方法：

(lldb) p $3.buckets() //调用buckets()
(bucket_t *) $4 = 0x0000000100610990
(lldb) p *$4
(bucket_t) $5 = {
  _sel = {
    std::__1::atomic<objc_selector *> = "" {
      Value = ""
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 48656
    }
  }
}
(lldb) p $5.sel() //调用bucket_t的sel()
(SEL) $6 = "func1"
(lldb) p $5.imp(nil, [Person class]) //调用bucket_t的imp()
(IMP) $7 = 0x0000000100003d60 (KCObjcBuild`-[Person func1])
复制代码

此时大概可以得出如下图的所示的结构图，但是cache_t是如何存放bucket_t还不得而知。

insert的流程

首次缓存方法

定位到关键方法insert，接着分析该方法的流程。
重新运行代码，设置断点在insert，在调用func1前断下，此时cache中还没缓存任何方法

mask_t cache_t::occupied() const
{
    return _occupied;
}

mask_t cache_t::mask() const
{
    return _maybeMask.load(memory_order_relaxed);
}

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

bool cache_t::isConstantEmptyCache() const
{
    return occupied() == 0  &&
        buckets() == emptyBucketsForCapacity(capacity(), false);
}

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    runtimeLock.assertLocked();
    ......
    //获取_occupied，初始值为0，表示当前的缓存方法的个数，
    mask_t newOccupied = occupied() + 1;  // 1
    //获取_maybeMask，不为0值为_maybeMask + 1，否则为0
    unsigned oldCapacity = capacity(), capacity = oldCapacity;// 0
    ......
}
复制代码

此时cache还未缓存方法，进入下面的if分支

void cache_t::insert(SEL sel, IMP imp, id receiver){
    ......
    if (slowpath(isConstantEmptyCache())) {
        //INIT_CACHE_SIZE = 1 << 2 = 4
        if (!capacity) capacity = INIT_CACHE_SIZE;
        //调用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.
    }
#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);
    }
    ......
}

复制代码

开辟内存

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    bucket_t *oldBuckets = buckets();
    //开辟内存
    bucket_t *newBuckets = allocateBuckets(newCapacity);

    ASSERT(newCapacity > 0);
    ASSERT((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
    // mask和buckets 赋值, mask 为 4 - 1
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    //释放原来的oldBuckets，此时还没有缓存，freeOld为false
    if (freeOld) {
        collect_free(oldBuckets, oldCapacity);
    }
}
复制代码

源码的注释提到会给最后的位置会占位用来标记列表的结尾，所以_maybeMask为capacity - 1，表示当前最多存放方法的个数

bucket_t *cache_t::endMarker(struct bucket_t *b, uint32_t cap)
{
    return (bucket_t *)((uintptr_t)b + bytesForCapacity(cap)) - 1;
}

bucket_t *cache_t::allocateBuckets(mask_t newCapacity)
{
    // Allocate one extra bucket to mark the end of the list.
    // This can't overflow mask_t because newCapacity is a power of 2.
    
    //开辟newCapacity个bucket_t大小的内存空间，当前newCapacity = 4
    bucket_t *newBuckets = (bucket_t *)calloc(bytesForCapacity(newCapacity), 1);
    //通过内存平移取到最后的一个 bucket_t的地址
    bucket_t *end = endMarker(newBuckets, newCapacity);

// 设置结束的标记
#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>(newBuckets, (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>(newBuckets, (SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    
    if (PrintCaches) recordNewCache(newCapacity);

    return newBuckets;
}
复制代码

方法缓存

insert流程继续往下走

static constexpr uintptr_t bucketsMask = ~0ul;
struct bucket_t *cache_t::buckets() const
{
    uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return (bucket_t *)(addr & bucketsMask);
}
//------------------------
// 哈希函数
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);
}
//------------------------
void cache_t::incrementOccupied() 
{
    _occupied++;
}
//------------------------
// mac x86 环境下
//哈希冲突处理，
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}
void cache_t::insert(SEL sel, IMP imp, id receiver){
    ......
    bucket_t *b = buckets();
    
    mask_t m = capacity - 1; // 4 - 1 = 3
    //哈希函数拿到存放的位置
    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() == 0 说明该位置还未使用，
        if (fastpath(b[i].sel() == 0)) {
            //occupied + 1
            incrementOccupied();
            //将方法存到该位置
            b[i].set<Atomic, Encoded>(b, sel, imp, cls());
            return;
        }
        //sel() == sel 方法已被缓存
        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_next获取下一个位置，直到 i == begin, 退出循环

    bad_cache(receiver, (SEL)sel);
}
复制代码

buckets扩容

buckets首次只开辟了4个空间，必然会有存不下的情况，回到insert前面的部分

#define CACHE_END_MARKER 1

// 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;
}
void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    ......
    if (slowpath(isConstantEmptyCache())) {
        ......
    }
    //cache_fill_ratio(capacity) = 4 * 3 / 4 = 3
    // newOccupied + 1 <= 3才能存，也就是4个空间存放2个方法之后就需要扩容了
    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扩大一倍，当最大不超过1<<16的大小
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        // 重新开辟空间，并释放之前的空间，考虑到效率会放弃之前缓存的方法
        reallocate(oldCapacity, capacity, true);
    }
    ......
}
复制代码