iOS底层-类的cacht_t探究

前言

在前面的文章中我们讲到了类的isa走位以及bits相关信息，类的属性和实例变量，我们知道类的结构中还有cache，字面意思是缓存，今天我们就来对cache进行一个详细的探究。

一、分析cache

• 根据前面获取bits数据，我们在用同样的方法来打印cache。
• 1. 先定义好类WSPerson:

@interface WSPerson : NSObject

@property (nonatomic, strong) NSString *name;
@property (nonatomic, strong) NSString *nickName;

- (void)sayABC;
- (void)sayBCD;
- (void)sayCDE;

@end
复制代码

• 2. 再根据首地址获取cache，再打印：

(lldb) p/x WSPerson.class
(Class) $0 = 0x00000001000083e8 WSPerson
(lldb) p (cache_t *)0x00000001000083f8
(cache_t *) $1 = 0x00000001000083f8
(lldb) p *$1
(cache_t) $2 = {
  _bucketsAndMaybeMask = {
    std::__1::atomic<unsigned long> = {
      Value = 4298437504
    }
  }
   = {
     = {
      _maybeMask = {
        std::__1::atomic<unsigned int> = {
          Value = 0
        }
      }
      _flags = 32800
      _occupied = 0
    }
    _originalPreoptCache = {
      std::__1::atomic<preopt_cache_t *> = {
        Value = 0x0000802000000000
      }
    }
  }
}
复制代码

我们得到$2是这个类型，根据之前的经验，我们在取下里面的数据

(lldb) p $2._bucketsAndMaybeMask
(explicit_atomic<unsigned long>) $3 = {
  std::__1::atomic<unsigned long> = {
    Value = 4298437504
  }
}
(lldb) p $3.Value
error: <user expression 4>:1:4: no member named 'Value' in 'explicit_atomic<unsigned long>'
$3.Value
~~ ^
(lldb) p $2._maybeMask
(explicit_atomic<unsigned int>) $4 = {
  std::__1::atomic<unsigned int> = {
    Value = 0
  }
}
(lldb) p $4.Value
error: <user expression 6>:1:4: no member named 'Value' in 'explicit_atomic<unsigned int>'
$4.Value
~~ ^
(lldb) p $2._originalPreoptCache
(explicit_atomic<preopt_cache_t *>) $5 = {
  std::__1::atomic<preopt_cache_t *> = {
    Value = 0x0000802000000000
  }
}
(lldb) p $5.Value
error: <user expression 8>:1:4: no member named 'Value' in 'explicit_atomic<preopt_cache_t *>'
$5.Value
~~ ^
复制代码

数据全部没取到，说明要读的数据不是这个，我们再分析cache_t的结构

分析cache的存取

在objc4-818.2中，我们找到cache_t的结构，它是一个结构体，那么改怎么找数据呢？我们想，缓存肯定有存的操作，然后我们去找有关存的步骤：

• 在寻找的过程中，我们找到了清空，创建，固定清空等方法：

static bucket_t *emptyBuckets(); // 清空
static bucket_t *allocateBuckets(mask_t newCapacity); //创建
static bucket_t *emptyBucketsForCapacity(mask_t capacity, bool allocate = true); //清空固定大小
复制代码

这三个方法都围绕着bucket_t这个类型，那么核心数据到底是不是它呢，我们继续去找存缓存的方法：

void insert(SEL sel, IMP imp, id receiver);
复制代码

接下来，找到了个insert方法，极大可能就是存数据的方法，然后我们进去查看：

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

我们知道缓存肯定是没有的时候创建，那么这个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);
    }
}
复制代码

在reallocate里，我们能够判断，核心数据就是bucket_t类型，找到核心数据类型后，那么再找怎么取这个数据，我们继续查找cache_t结构体：

struct bucket_t *buckets() const;
复制代码

找到了个buckets()，返回的类型也是我们需要的，我们来验证下：

(lldb) p $2->buckets()
(bucket_t *) $6 = 0x000000010034f380
  Fix-it applied, fixed expression was: 
    $2.buckets()
(lldb) p *$6
(bucket_t) $7 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null) {
      Value = (null)
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 0
    }
  }
}
复制代码

于是我们就得到了数据，也验证了猜想，核心的数据类型就是bucket_t，取值的方法是buckets()，此刻就看到了熟悉的东西SEL和IMP，我们在继续取数据：

(lldb) p $7._sel
(explicit_atomic<objc_selector *>) $8 = {
  std::__1::atomic<objc_selector *> = (null) {
    Value = (null)
  }
}
(lldb) p $6._imp
(explicit_atomic<unsigned long>) $9 = {
  std::__1::atomic<unsigned long> = {
    Value = 0
  }
}
  Fix-it applied, fixed expression was: 
    $6->_imp
(lldb)
复制代码

怎么都没有值？难道和没有调用方法有关？，我们是调用下方法再尝试下：

(lldb) p [p1 sayABC]
2021-06-24 09:14:49.383322+0800 KCObjcBuild[53698:903825] -[WSPerson sayABC]
(lldb) p/x WSPerson.class
(Class) $0 = 0x00000001000083e8 WSPerson
(lldb) p (cache_t *)0x00000001000083f8
(cache_t *) $1 = 0x00000001000083f8
(lldb) p $1->buckets()
(bucket_t *) $2 = 0x0000000100646750
(lldb) p *$2
(bucket_t) $3 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null) {
      Value = (null)
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 0
    }
  }
}
复制代码

打印的还是没数据，这什么情况？，我们在回过头来观察bucket_t和insert方法，在insert中发现了哈希取bucket_t：

    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)) { // 如果此位置的sel()为空，就进行赋值
            incrementOccupied(); // _occupied++， 使用数+1
            b[i].set<Atomic, Encoded>(b, sel, imp, cls()); //将sel和imp分别存入bucket的_sel和_imp中
            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));
复制代码

• 这个while循环是在b中找到第一个sel为0处，然后在这个位置将sel和imp分别存到butket的_sel和_imp中。b[i].sel()中，可断定b[i]是butket，所以我们可以用这个方式取拿数据。
• 于是我们再验证下：

(lldb) p $2[1]
(bucket_t) $3 = {
  _sel = {
    std::__1::atomic<objc_selector *> = "" {
      Value = ""
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 49032
    }
  }
}
复制代码

说明：这里下标取1$2[1]，是因为哈希存储不确定位置

• 这里就有值了，根据上面代码分析b[i].sel()，可以得到sel的获取方法，然后也同样去取下imp()：

(lldb) p $3.sel()
(SEL) $4 = "sayABC"
(lldb) p $3.imp()
error: <user expression 7>:1:8: too few arguments to function call, expected 2, have 0
$3.imp()
~~~~~~ ^
note: 'imp' declared here
复制代码

• 我们很顺利的得到了sel，但imp()的读取不对，再次去查看bucket_t中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
}
复制代码

• 根据代码分析得知，上面的base和imp没关系，可以传nil，于是可得到imp：

(lldb) p $3.imp(nil, p1)
(IMP) $5 = 0x0000000100640b48 (0x0000000100640b48)
复制代码

• 至此，我们就拿到了SEL和IMP。

总结：用lldb结合源码的方式去获取cache，结构清楚但比较复杂，我们可以通过脱离源码的方式，进行小规模取样。

小规模取样取cache

用上面这种方式取方法，步骤是比较繁琐的，我们这里介绍一种简便的方法，称为小规模取样。

确定取样结构

• 1. 首先我们创建个MAC工程(非Objc源码)，然后创建个WSPerson类

@interface WSPerson : NSObject

@property (nonatomic, copy) NSString *name;
@property (nonatomic, strong) NSString *nickName;

- (void)sayNB_A;
- (void)sayNB_B;
- (void)sayNB_C;
- (void)sayNB_D;
- (void)sayNB_E;
- (void)sayNB_F;

+ (void)sayHappy;
@end
复制代码

每个方法的实现中打印__func__，例如：

- (void)sayNB_A {
    NSLog(@"%s", __func__);
}
复制代码

• 2. 在main.m中引入：

#import <Foundation/Foundation.h>
#import "WSPerson.h"
#import <objc/runtime.h>

int main(int argc, const char * argv[]) {

    WSPerson *p = [WSPerson alloc];
    Class pClass = p.class;

    [p sayNB_A];
    
    return 0;
}
复制代码

• 3. 将响应拿cache的结构从objc源码中拿出来，去掉没用的，写到main上面：

typedef uint32_t mask_t;

struct ws_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct ws_cache_t {
    uintptr_t _bucketsAndMaybeMask; // 8
    mask_t    _maybeMask; // 4
    uint16_t  _flags; // 2
    uint16_t  _occupied; // 2
};

struct ws_class_data_bits_t {
    uintptr_t bits;
};

struct ws_objc_class {
    Class superclass;
    struct ws_cache_t cache;
    struct ws_class_data_bits_t bits;
};
复制代码

4. 然后我们将main中的pClass强转为自定义的classws_objc_class，然后打印：

struct kc_objc_class *kc_class = (__bridge struct kc_objc_class *)(pClass);
NSLog(@"%hu - %u",kc_class->cache._occupied,kc_class->cache._maybeMask);

// 打印结果
// _occupied: 0  _maybeMask: 42026256
复制代码

• _occupied这个怎么为0呢，使用了一次，应该是1呀，还有_maybeMask这个也比较离谱，因为存储的时候_maybeMask存一次，_occupied记录一次，理论上都是1，很明显数据没对应上，通过观察发现ws_objc_class中少了个isa，然后我们加上后再打印：

struct ws_objc_class {
    Class isa;
    Class superclass;
    struct ws_cache_t cache;
    struct ws_class_data_bits_t bits;
};

// 打印结果 _occupied: 1  _maybeMask: 3
复制代码

这个时候结果比较接近，我们先来尝试打印下buckets，我们来看看源码：

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

获取bucket，需要先读取内存，再位与，操作比较繁琐，细思我们想要的数据，在bucket中的sel和imp是我们想要的，然后我们这样写试试：

struct ws_cache_t {
//    uintptr_t _bucketsAndMaybeMask; // 8
    struct ws_bucket_t *buckets;
    mask_t    _maybeMask; // 4
    uint16_t  _flags; // 2
    uint16_t  _occupied; // 2
};
复制代码

因为 _bucketsAndMaybeMask存的是bucket，而bucket存的是imp和sel，所以可以这样写，然后我们循环打印下试试：

for (mask_t i = 0; i < wsClass->cache._maybeMask; i++) {
     struct ws_bucket_t bucket = wsClass->cache.buckets[i];
     NSLog(@"%@ --- %p", NSStringFromSelector(bucket._sel), bucket._imp);
}

// 结果：
// _occupied: 1  _maybeMask: 3
// sayNB_A --- 0xbb58
// (null) --- 0x0
// (null) --- 0x0
复制代码

这里我们就得到了imp和sel,同时也可以得出：缓存存的是方法

• 得到imp和sel，然后再加个方法调用再打印：

[p sayNB_A];
[p sayNB_B];

// 结果：_occupied: 2  _maybeMask: 3  
// sayNB_A --- 0xbb10
// sayNB_B --- 0xb8c0 
// (null) --- 0x0
复制代码

再加个方法调用，再打印：

[p sayNB_A];
[p sayNB_B];
[p sayNB_C];
// 结果：_occupied: 1  _maybeMask: 7
// sayNB_C --- 0xb8e8
// (null) --- 0x0
// (null) --- 0x0
// (null) --- 0x0
// (null) --- 0x0
// (null) --- 0x0
// (null) --- 0x0
复制代码

这种情况sel没了，再调用类方法试试：

[p sayNB_A];
[p sayNB_B];
[p sayNB_C];
[pClass sayHappy];

// 结果：_occupied: 1  _maybeMask: 7
// sayNB_C --- 0xb8c0
// (null) --- 0x0
// (null) --- 0x0
// (null) --- 0x0
// (null) --- 0x0
// (null) --- 0x0
// (null) --- 0x0
复制代码

这个情况也是没有，再加个方法试试：

[p sayNB_A];
[p sayNB_B];
[p sayNB_C];
[pClass sayHappy];
[p sayNB_D];

// 结果：_occupied: 2  _maybeMask: 7
// (null) --- 0x0
// (null) --- 0x0
// (null) --- 0x0
// sayNB_C --- 0xb8d8
// sayNB_D --- 0xb8e8
// (null) --- 0x0
// (null) --- 0x0
复制代码

这里发现了新问题：调用的方法个数影响打印结果，方法调用多了，前面的方法打印不出来了，带着问题，我们继续进行分析。

insert核心

缓存的核心是insert插入操作，我们先来分析下，在上面我们提到了insert的一些代码：

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);
    }
...
}
复制代码

从代码中可以看到，insert的流程

开辟内存

//第一次使用时，没有缓存，则occupied为0
mask_t newOccupied = occupied() + 1; 
// 第一次没有缓存，所以 oldCapacity = 0，capacity = 0
unsigned oldCapacity = capacity(), capacity = oldCapacity;
if (slowpath(isConstantEmptyCache())) { // 第一次没有缓存，则进入创建方法
    // Cache is read-only. Replace it.
    if (!capacity) capacity = INIT_CACHE_SIZE; //INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2) 为4
    reallocate(oldCapacity, capacity, /* freeOld */false); // 0，4，false
}
复制代码

• 第一次调用时，capacity = INIT_CACHE_SIZE = 4，再调用reallocate开辟：

//  第一次，oldCapacity：0，newCapacity：4，freeOld：false
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    bucket_t *oldBuckets = buckets(); //加载旧的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);
    }
}
复制代码

reallocate核心步骤是：

• 1. allocateBuckets：开辟内存创建新bucket
• 2. setBucketsAndMask：存储_maybeMask，设置_occupied，_bucketsAndMaybeMask存储新bucket。
• 3. collect_free：是否释放旧内存。

allocateBuckets

// 第一次，newCapacity：4
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.
    bucket_t *newBuckets = (bucket_t *)calloc(bytesForCapacity(newCapacity), 1); // 根据计算出的内存，创建bucket

    bucket_t *end = endMarker(newBuckets, newCapacity); //根据新bucket起始位置，获取最后一个butket的地址

#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.
    // 最后一个 bucket赋值：sel = 1，imp = newBuckets
    end->set<NotAtomic, Raw>(newBuckets, (SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    
    if (PrintCaches) recordNewCache(newCapacity); //记录缓存

    return newBuckets;
}

size_t cache_t::bytesForCapacity(uint32_t cap)
{
    return sizeof(bucket_t) * cap; //根据容量，计算内存
}

#if CACHE_END_MARKER // 模拟器
bucket_t *cache_t::endMarker(struct bucket_t *b, uint32_t cap)
{
    return (bucket_t *)((uintptr_t)b + bytesForCapacity(cap)) - 1; //根据新bucket大小，
}
复制代码

allocateBuckets主要步骤：

• 1. bytesForCapacity(newCapacity)开辟内存
• 2. 计算出bucket地址，也就是最后一个bucket的地址，然后将bucket赋值，sel=1，imp=newBuckets

setBucketsAndMask

// 第一次 `newMask` 为3
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
    mega_barrier();

    _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_relaxed);

    // ensure other threads see new buckets before new mask
    mega_barrier();

    _maybeMask.store(newMask, memory_order_relaxed);
    _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.store(newMask, memory_order_release);
    _occupied = 0;
#else
#error Don't know how to do setBucketsAndMask on this architecture.
#endif
}
复制代码

• 1. _bucketsAndMaybeMask存储newBuckets，根据架构不同存储newBuckets时的key不同
• 2. _maybeMask存储newMask
• 3. 存储完_occupied置为0。

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); //获取回收的`bucket`大小，并加到garbage_byte_size上
    garbage_refs[garbage_count++] = data;
    cache_t::collectNolock(false);
}
复制代码

• 1. _garbage_make_room：创建回收站，如果回收站满了会重新分配2倍空间：

  static void _garbage_make_room(void)
  {
       static int first = 1;
  
       // Create the collection table the first time it is needed
       if (first)
       {
           // 第一次调用创建回收站内存
           first = 0;
           garbage_refs = (bucket_t**)malloc(INIT_GARBAGE_COUNT * sizeof(void *));
           garbage_max = INIT_GARBAGE_COUNT; //设置最大存储量
       }
  
       // Double the table if it is full
       // 如果存储满了，就重新分配内存，最大的内存为之前的2倍
       else if (garbage_count == garbage_max)
       {
           garbage_refs = (bucket_t**)realloc(garbage_refs, garbage_max * 2 * sizeof(void *));
           garbage_max *= 2;
       }
  }
  复制代码

• 2. garbage_refs：将当前回收bucket放在回收站上一个回收后的位置上。
• 3. collectNolock：清空数据，回收内存

容量小于3/4

else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) {
     // CACHE_END_MARKER = 1
     // 第一次判断：newOccupied = 1，capacity = 4， 1+1 < 3*4/4，无其他操作
     // 第二次判断：newOccupied = 1+1=2，capacity = 4，2+1=3*4/4，无其他操作
     // 第三次判断：newOccupied = 2+1 = 3，capacity=4，3+1 > 3 * 4 / 4，不满足，走else
     // Cache is less than 3/4 or 7/8 full. Use it as-is.
}
复制代码

• 当bucket容量小于等于3/4时，无其他操作
• 当bucket容量大于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
复制代码

• 在small bucket中，可以存满

扩容(容量>3/4)

else {
    capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
    // MAX_CACHE_SIZE = 1<<16 = 2^5 = 32
    if (capacity > MAX_CACHE_SIZE) {
        capacity = MAX_CACHE_SIZE;
    }
    reallocate(oldCapacity, capacity, true);
}
复制代码

• 当容量大于总容量3/4时，会进行扩容，总容量为之前的2倍，最大扩容不能超过32位
• 扩容后创建个新bucket，然后释放旧的bucket内存

缓存

bucket_t *b = buckets(); //拿到`bucket`地址
mask_t m = capacity - 1; // 计算能存储的位置
mask_t begin = cache_hash(sel, m); //拿到hash下标
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)) { // 如果此位置的sel()为空，就进行赋值
        incrementOccupied(); // _occupied++， 使用数+1
        b[i].set<Atomic, Encoded>(b, sel, imp, cls()); //将sel和imp分别存入bucket的_sel和_imp中
        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));
复制代码

缓存步骤：

• 1. 根据内存订单memory_order拿到bucket地址
• 2. 根据sel和mask计算出起始位置
• 3. 通过遍历在bucket中寻找sel为空的位置，并在这个位置对插入的sel和imp进行存储，然后进行进行_occupied自增。

insert流程图

通过上面的insert分析，可得到如下流程图：

调用insert流程

• 我们在objc中，对insert断点，然后进行汇编调试分析：
• 第一步：断点至方法处：

• 第二步：打开汇编：

• 第三步，查看objc_msgsend:

• 方法里面的_objc_msgSend_uncached是发送没有缓存过的消息，然后一步步进行分析得出最终的调用流程：

二、cache整体流程

根据上面分析，得到cache整体流程如下：

• 探索cache，了解了很多新东西，当一步一步克服困难时，也懂了不少新东西