iOS原理探索06--cache_t分析

概要

前面文章我们分析了isa、bits，本文主要分析一下cache_t和类的关系。我们知道cache是用来缓存指针和函数表的，那么底层是如何具体实现的呢？带着问题来分析、思考一下。

cache_t的结构

首先我们来看一下它的源码实现

struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    //模拟器或者macOS环境
    //explicit_atomic:显示原子性，保证增删改查的安全
    explicit_atomic<struct bucket_t *> _buckets;//存放SEL、imp
    explicit_atomic<mask_t> _mask;
    ///省略代码....
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    //64位真机环境
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
    //非64位真机环境
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;
  //省略代码
#else
#error Unknown cache mask storage type.
#endif
    
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;

//////省略方法.......

};

上面源码可以看出，cach_t主要包含_buckets、_mask、_flags、_occupied四个部分，当然在不同的环境下变量名不同，以上代码有详细注释，我们以MacOS环境为例。

我们可以根据cach_t的源码流程图来探索一下每个环节的具体实现过程

cach_t源码实现流程图----来自style_月月简书

cache_t的结构解释

_buckets：我们可以进入到bucket_t源码查看一下里面的具体实现，我们可以看到无论是arm64还是其他环境下，bucket_t结构体包含了两个东西，一个是imp、另外一个是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
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
}

_mask：指掩码数据，用于在哈希算法或者哈希冲突算法中计算哈希下标；
_flags：标识
_occupied：表示哈希表中 sel-imp 的占用大小 (即可以理解为分配的内存中已经存储了sel-imp的的个数)；

结合示例代码分析cache_t是否在方法调用时会被缓存

示例代码

//LGPerson.h
@interface LGPerson : NSObject
@property (nonatomic, copy) NSString *lgName;
@property (nonatomic, strong) NSString *nickName;

- (void)sayHello;

- (void)sayCode;

- (void)sayMaster;

- (void)sayNB;

+ (void)sayHappy;

@end

//LGPerson.m
@implementation LGPerson
- (void)sayHello{
    NSLog(@"LGPerson say : %s",__func__);
}

- (void)sayCode{
    NSLog(@"LGPerson say : %s",__func__);
}

- (void)sayMaster{
    NSLog(@"LGPerson say : %s",__func__);
}

- (void)sayNB{
    NSLog(@"LGPerson say : %s",__func__);
}

+ (void)sayHappy{
    NSLog(@"LGPerson say : %s",__func__);
}

//mian.m
int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        LGPerson *p  = [LGPerson alloc];
        Class pClass = [LGPerson class];
//        p.lgName     = @"Cooci";
//        p.nickName   = @"KC";
        // 缓存一次方法 sayHello
        // 4
        [p sayHello];
        [p sayCode];
        [p sayMaster];
//        [p sayNB];


        NSLog(@"%@",pClass);
    }
    return 0;
}

我们先创建一个类，并添加类方法和实例方法，在main.m中初始化LGPerson并调用该方法，来探索cach_t中的各变量的值的变化。

我们在[p sayHello];打个断点，运行程序，通过lldb调试看一下cache_t的打印情况:

断点位置	指令	输出结果
`[p sayHello]`	`p/x pClass`	`$0 = 0x0000000100002298 LGPerson`
`指针偏移16位`	`0x0000000100002298` + `0x10`	`0x00000001000022a8`
... ...	`p (cache_t *)0x00000001000022a8`	`(cache_t *) $1 = 0x00000001000022a8`
... ...	`p *$1`	输出结果见下面代码

`p *$1`的输出结果
(cache_t) $2 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x000000010032e420 {
      _sel = {
        std::__1::atomic<objc_selector *> = (null)
      }
      _imp = {
        std::__1::atomic<unsigned long> = 0
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 0
  }
  _flags = 32804
  _occupied = 0
}

根据表格内容以及输出结果我们可以得出，在我们没有调用方法之前，cache_t中的bucket_t,_mask,_occupied都没有值。

现在我们过一下【[p sayHello]】断点，使用相同的方法查看一下cache_t内容

断点位置	指令	输出结果
... ...	`p (cache_t *)0x00000001000022a8`	`$5 = 0x00000001000022a8`
... ...	`p *$5`	输出结果见下面代码

(cache_t) $6 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x00000001007bf8c0 {
      _sel = {
        std::__1::atomic<objc_selector *> = ""
      }
      _imp = {
        std::__1::atomic<unsigned long> = 11928
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 3
  }
  _flags = 32804
  _occupied = 1
}

我们可以看出，在调用了-[LGPerson sayHello]方法后，_buckets和_mask中也有值了_occupied +1,这就说明当方法被调用后就会被cache缓存起来。

接下来我们证明一下上面输出结果(cache_t) $6中的方法是不是sayHello，接着上面的步骤我们来打印一下cache_t中的_sel和_imp；

断点位置	指令	输出结果
... ...	`$6.buckets()`	`$7 = 0x00000001007bf8c0`
... ...	`p *$7`	输出结果见下面代码
... ...	`p $8.sel()`	`(SEL) $9 = "sayHello"`
... ...	`p $8.imp(pClass)`	`$10 = 0x0000000100000c00 (KCObjc`-[LGPerson sayHello])`

(lldb) p *$7
(bucket_t) $8 = {
  _sel = {
    std::__1::atomic<objc_selector *> = ""
  }
  _imp = {
    std::__1::atomic<unsigned long> = 11928
  }
}

总结：系统在调用方法后确实会被cace_t缓存起来！那么问题来了，这些cace_t的值是怎么变化的呢？有什么作用呢？带着这个问题我们继续来探索一下。

探索`cache`的值的变化

我们还是根据前面的断点接着执行下一个sayCode方法，看一下cache中的值的变化。

断点位置	指令	输出结果
执行完`sayCode方法`	`p *$5`	`$11`输出结果见下面代码1
... ...	`p $11.buckets()`	`$12 = 0x00000001007bf8c0`
... ...	`p *$12`	`$13`输出结果见下面代码2
... ...	`p $13.sel()`	`$14 = "sayHello"`
... ...	`指针偏移1：p *($12 + 1)`	`$15`输出结果见下面代码3
... ...	`p $15.sel()`	`(SEL) $16 = "sayCode"`

$11输出结果代码1

(lldb) p *$5
(cache_t) $11 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x00000001007bf8c0 {
      _sel = {
        std::__1::atomic<objc_selector *> = ""
      }
      _imp = {
        std::__1::atomic<unsigned long> = 11928
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 3
  }
  _flags = 32804
  _occupied = 2

$13输出结果2

(bucket_t) $13 = {
  _sel = {
    std::__1::atomic<objc_selector *> = ""
  }
  _imp = {
    std::__1::atomic<unsigned long> = 11928
  }
}

$15输出结果3

(bucket_t) $15 = {
  _sel = {
    std::__1::atomic<objc_selector *> = ""
  }
  _imp = {
    std::__1::atomic<unsigned long> = 11944
  }
}

从上面的lldb的调试表格以及输出结果我们可以得知一下两点结论：第一：无论什么时候什么方法被调用后都会被cache缓存起来；第二：随着调用方法的数量增多，cache中的_occupied也会增加相应的数目。

注意：occupied 是如何递增的呢？cache又是如何缓存的呢？下面小节分析一下cache_t的底层原理。

cache_t的底层原理分析

前面小节我们发现当有多个方法被调用的时候，cache_t的值就会发生改变，那么是哪个函数引起的呢？在源码中发现了一个函数incrementOccupied，这个函数使得occupied的值进行递增

void cache_t::incrementOccupied() 
{
    _occupied++;
}

那么这个函数是在什么时候调用的呢？在源码781中搜索一下，找到了调用这个方法的地方

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
    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);
    }
    //当小于等于3/4时候不做处理
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) { // 4  3 + 1 bucket cache_t
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
        //超过了3/4进行原来容量的2倍扩容
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 扩容两倍 4
        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 because the
    // minimum size is 4 and we resized at 3/4 full.
    /*
     通过循环
     //扫描第一个未使用的插槽并插入。
     //保证有一个空槽，因为
     //最小尺寸是4，我们将大小调整为3/4满。
     */
    do {
        //如果当前哈希下标的sel未被存储
        if (fastpath(b[i].sel() == 0)) {
            //Occupied++
            incrementOccupied();
            //bucket对sel, imp进行set赋值
            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 (fastpath((i = cache_next(i, m)) != begin));
    //循环条件：当前哈希下标存储的sel不等于即将要插入的sel，通过cache_next方法重新计算得到新的哈希下标。

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

cache_t中insert流程图

` insert`流程图--来自简书style_月月

流程梳理

计算当前的缓存占用数量

    mask_t newOccupied = occupied() + 1;

根据当属性未赋值及无方法调用时，此时的occupied()为0，而newOccupied为1，

第一次进来创建，申请开辟空间；

if (slowpath(isConstantEmptyCache())) { //小概率发生的 即当 occupied() = 0时，即创建缓存，创建属于小概率事件
    // Cache is read-only. Replace it.
    if (!capacity) capacity = INIT_CACHE_SIZE; //初始化时，capacity = 4（1<<2 -- 100）
    reallocate(oldCapacity, capacity, /* freeOld */false); //开辟空间
    //到目前为止，if的流程的操作都是初始化创建
}

关于开辟空间的源码解析

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    bucket_t *oldBuckets = buckets();
    //向系统申请开辟内存，即开辟bucket，此时的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);

    //将newBuckets存入缓存中
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
        //如果有旧的oldBuckets，清理之前的缓存
        cache_collect_free(oldBuckets, oldCapacity);
    }
}

第一步：向系统申请开辟内存，即开辟bucket，此时的bucket只是一个临时变量；
第二步：将newBuckets存入缓存中，如果是真机，根据bucket和mask的位置存储，并将occupied占用设置为0，如果不是真机，正常存储bucket和mask，并将occupied占用设置为0。

//真机环境下
   _maskAndBuckets.store(((uintptr_t)newMask << maskShift) | (uintptr_t)newBuckets, std::memory_order_relaxed);
   _occupied = 0;

//模拟器环境下
   _maskAndBuckets.store(buckets | maskShift, memory_order::memory_order_relaxed);
   _occupied = 0;

第三步：如果有旧的buckets，需要清理之前的缓存，即调用cache_collect_free方法，其源码实现如下

   if (freeOld) {
        //如果有旧的oldBuckets，清理之前的缓存
        cache_collect_free(oldBuckets, oldCapacity);
    }

//cache_collect_free方法的具体实现
    _garbage_make_room ();//创建垃圾回收空间
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    garbage_refs[garbage_count++] = data;//记录缓存这一次的Bucket
    cache_collect(false);//垃圾回收，清理旧的Bucket缓存

不是第一次创建判断当前缓存占用数量，如果小于等于3/4不做处理，如果超过了3/4，对原来的容量进行两倍扩容并重新申请空间；

   //当小于等于3/4时候不做处理
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) { // 4  3 + 1 bucket cache_t
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
        //超过了3/4进行原来容量的2倍扩容
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 扩容两倍 4
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        //重新按照扩容后的大小进行开辟空间
        reallocate(oldCapacity, capacity, true);  // 内存 库容完毕
    }

针对需要存储的bucket进行内部的sel和imp赋值，首先需要计算此次的插入的哈希下标，然后通过do-while循环找到合适的下标操作（判断条件：当前哈希下标存储的sel不等于即将要插入的sel，通过cache_next方法重新计算得到新的哈希下标。），如果当前的哈希下标为存储sel，那么对占用数进行++，即ocuplied++;如果下标存在直接返回；

//计算此次插入的开始的哈希下标
mask_t begin = cache_hash(sel, m);

//具体实现
static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;
}


//do--while实现
 do {
        //如果当前哈希下标的sel未被存储
        if (fastpath(b[i].sel() == 0)) {
            //Occupied++
            incrementOccupied();
            //bucket对sel, imp进行set赋值
            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 (fastpath((i = cache_next(i, m)) != begin));
    //循环条件：当前哈希下标存储的sel不等于即将要插入的sel，通过cache_next方法重新计算得到新的哈希下标。