OC底层-Cache初探 缓存的插入与扩容

cache_t 源码

struct cache_t {
private:
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask; // 8
    union {
        struct {
            explicit_atomic<mask_t>    _maybeMask; // 4
#if __LP64__
            uint16_t                   _flags;  // 2
#endif
            uint16_t                   _occupied; // 2
        };
        explicit_atomic<preopt_cache_t *> _originalPreoptCache; // 8
    };
    ....  //一些static 方法 是对 bucket_t 的操作
    static bucket_t *emptyBuckets();
    static bucket_t *allocateBuckets(mask_t newCapacity);
    static bucket_t *emptyBucketsForCapacity(mask_t capacity, bool allocate = true);
    ....  //一些方法
   460  struct bucket_t *buckets() const; //获取bucket_t的方法
    ...
   486 void insert(SEL sel, IMP imp, id receiver);
    ....
}

复制代码

• cache : cache_t （16字节大小0xf）
  • explicit_atomic<uintptr_t> _bucketsAndMaybeMask; // 8 一个地址& 非0 掩码 得到了 buckets 哈希表的首地址。即存放了缓存链表的首地址
    • bucket_t
      • explicit_atomic<uintptr_t> _imp; //方法的地址 value
      • explicit_atomic _sel; //方法名 key

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

    static constexpr uintptr_t bucketsMask = ~0ul;
    
    复制代码

  • union(由于是联合体后面的两个子数据是互斥的)

    struct {
            explicit_atomic<mask_t>    _maybeMask; // 4  存放 最大访问数
    #if __LP64__
                uint16_t                   _flags;  // 2
    #endif
                uint16_t                   _occupied; // 2     //缓存中方法的数量
    };
    复制代码

    explicit_atomic<preopt_cache_t *> _originalPreoptCache; // 8

  • 结论个结构体存放着缓存的基本的信息和方法，信息中有缓存链表数据的首节点地址，然后就是缓存中方法的数量和缓存方法的最大访问数量。

缓存方法探究

• 1.void incrementOccupied(); 缓存数+1

      void cache_t::incrementOccupied() 
  {
      _occupied++;
  }
  
  复制代码

• 2.void insert(SEL sel, IMP imp, id receiver); //缓存方法插入 分2中情况

1.缓存刚开始创建时
2.和缓存方法过多扩容时。
方法的插入 函数 ： void insert(SEL sel, IMP imp, id receiver);
sel:方法名
imp:方法地址
receiver:消息的接收者

• 创建了一块合适长度的链表数据结构等待方法的插入

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
...
    mask_t newOccupied = occupied() + 1; // 1+1
    if (slowpath(isConstantEmptyCache())) {
        //判断缓存为空时
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE;//4  -> capacity = 0 时 则 为4.
        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. //缓存小于 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. //缓存允许100使用，给一些小的缓存使用时
    }
#endif
    else {// 4*2 = 8
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE; //缓存扩容
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);
    }
  ...
}

复制代码

• 取出缓存链表的首节点地址，并计算 方法的hash值，即下标表示我要插入的第几个节点中

bucket_t *b = buckets();   //取出链表首地址
mask_t m = capacity - 1; // 4-1=3    //链表最大访问数
mask_t begin = cache_hash(sel, m); //通过sel 和 m 计算hash 值，一个小于m 的值
mask_t i = begin;

复制代码

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));
//开始插入方法： 如果 sel() == 0 说明这个位置时可以插入的，占位+1，-set 方法插入
//bit[i].set() == sel ，说明这个位置已经在其他的线程中添加完成了直接结束
//如果两个都不符合，就再一次hash 
复制代码

• cache_next

cache_next 不同的架构采用不同的hash值计算

#if __arm__  ||  __x86_64__  ||  __i386__
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}
// i+1 & mask


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

复制代码

• 创建缓存空间缓存为空时传入参数

oldCapacity = 0
newCapacity = 4
freeOld = false

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    bucket_t *oldBuckets = buckets();  //这个oldBuckets 在这里是没有使用到的临时变量
    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);
    }
}

setBucketsAndMask 
_bucketsAndMaybeMask.store创建存储了 哈希表的首节点的地址，
新建插入时 freeold = false
--------------------------------------------------
setBucketsAndMask
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
...
   _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;
...
}
_bucketsAndMaybeMask   ： 存放链表的第一个节点地址
_maybeMask  ：存放 最大访问数
这个就是因为他是新创建的 所以是空的 没有方法存放的，扩容时也是将这个设置0 
_occupied = 0

复制代码

• 扩容缓存空间时传入参数

oldCapacity = 4
newCapacity = 8
freeOld = true
与上面的方法走的是一致的，唯一的差别就是这里

bucket_t *oldBuckets = buckets();  //这个oldBuckets 在这里是使用到的临时变量
其他的操作是一致的，可以理解为创建了一个新的长度为8的链表数据空间，重新设置的头结点地址，_occupied = 0
if (freeOld) {
    collect_free(oldBuckets, oldCapacity);
}


--------------------
- 将老缓存的首节点地址，和长度传入，将这块的内存空间释放掉
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);
    garbage_refs[garbage_count++] = data;
    cache_t::collectNolock(false);
}


//将old 的缓存的bucket 的内存清空，内存回收，即将以前缓存起来的方法全部清空了。
//为什么扩容要将原来的缓存清空
1.如果我们保留原来缓存，这样一点一点去插入是相当耗费性能的，要一边插入一边扩充，影响效率。
2.且缓存的方法只保存最新的，扩容后会将以前的缓存清空，是为了缓存的快速，同时也是为了保存常用方法的记录，加入一个方法并不会被经常使用到，就是一次创建使用到时，扩容后这个方法就不会放在缓存。
复制代码

• 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;   //方法的地址  value
    explicit_atomic<SEL> _sel;         //方法名     key
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
    ...
    inline SEL sel() const { return _sel.load(memory_order_relaxed); }
    ...

    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
    }

    template <Atomicity, IMPEncoding>
    void set(bucket_t *base, SEL newSel, IMP newImp, Class cls);
};

复制代码

LLDB调试找到缓存中的方法

cache_t 为地址偏移 16字节 所以 +0x10
(lldb) p [p saySomething]  //调用一下方法
2021-06-23 23:27:42.232996+0800 KCObjcBuild[10806:722795] -[LGPerson saySomething]
(lldb) p/x LGPerson.class
(Class) $6 = 0x0000000100008428 LGPerson
(lldb) p (cache_t *)0x0000000100008438
(cache_t *) $7 = 0x0000000100008438
(lldb) p *$7
(cache_t) $8 = {
  _bucketsAndMaybeMask = {
    std::__1::atomic<unsigned long> = {
      Value = 4302373472
    }
  }
   = {
     = {
      _maybeMask = {
        std::__1::atomic<unsigned int> = {
          Value = 7
        }
      }
      _flags = 32808
      _occupied = 1
    }
    _originalPreoptCache = {
      std::__1::atomic<preopt_cache_t *> = {
        Value = 0x0001802800000007
      }
    }
  }
}
(lldb) p $8.buckets()   //哈希表数据第一个不一定有值
(bucket_t *) $9 = 0x0000000100710260
(lldb) p *$9
(bucket_t) $10 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null) {
      Value = nil
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 0
    }
  }
}
(lldb) p $8.buckets()[1]
(bucket_t) $11 = {
  _sel = {
    std::__1::atomic<objc_selector *> = "" {
      Value = ""
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 47112
    }
  }
}
(lldb) p $8.buckets()[2]
(bucket_t) $12 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null) {
      Value = nil
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 0
    }
  }
}
(lldb) p $11.sel()  //调用sel()方法获取 _sel值
(SEL) $13 = "saySomething"  
(lldb) p $11.imp(nil,[LGPerson class]) //调用 imp(base,cls) 获取 _imp
(IMP) $14 = 0x0000000100003c20 (KCObjcBuild`-[LGPerson saySomething])
(lldb) 
复制代码

脱离源码小练习

#import <Foundation/Foundation.h>
#import "LGPerson.h"
#import <objc/runtime.h>
typedef uint32_t mask_t;  // x86_64 & arm64 asm are less efficient with 16-bits
struct test_class_data_bits_t {
    uintptr_t bits;
};


struct test_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct test_cache_t {
    struct test_bucket_t *_bukets; // 8
    mask_t    _maybeMask; // 4
    uint16_t  _flags;  // 2
    uint16_t  _occupied; // 2
};


/// class
struct test_objc_class {
    Class isa;
    Class superclass;
    struct test_cache_t cache;
    struct test_class_data_bits_t bits;
};


int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        LGPerson *p  = [LGPerson alloc];
        Class pClass = p.class;  // objc_clas
        [p say1];
        [p say2];
        [p say3];
        [p say4];
        [p say1];
        [p say2];
//        [p say3];

        [pClass sayHappy];
        struct test_objc_class *test_class = (__bridge struct test_objc_class *)(pClass);
        NSLog(@"%hu - %u",test_class->cache._occupied,test_class->cache._maybeMask);

        
        for (mask_t i = 0; i<test_class->cache._maybeMask; i++) {
            struct test_bucket_t bucket = test_class->cache._bukets[i];
            NSLog(@"%@ - %pf",NSStringFromSelector(bucket._sel),bucket._imp);
        }
        NSLog(@"Hello, World!");    }
    return 0;
}
复制代码

方法的插入的流程图

cache 读取流程分析

• 1.在 insert方法中打上断点
• 2.LLDB 指令 bt
• 3.在log_and_fill_cache 方法中调用了 缓存的插入方法

• 4.IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)中调用了 log_and_fill_cache
• 5.缓存的读取，在缓存读取之前调用了objc_msgSend 消息发送