iOS底层探索之方法缓存

在分析类的时候，objc_class 结构体里面有个 cache_t cache 成员变量。

一、cache 存的是什么

先看下 cache 里面存的是什么

1.1 源码查看

struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED  // MacOS、模拟器
    explicit_atomic<struct bucket_t *> _buckets;
    explicit_atomic<mask_t> _mask;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16  // 64位真机
    explicit_atomic<uintptr_t> _maskAndBuckets;  // 可以联想isa的存储，优化空间
    mask_t _mask_unused;
    static constexpr uintptr_t maskShift = 48;
    static constexpr uintptr_t maskZeroBits = 4;
    static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4 // 非64位的真机
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;
    static constexpr uintptr_t maskBits = 4;
    static constexpr uintptr_t maskMask = (1 << maskBits) - 1;
    static constexpr uintptr_t bucketsMask = ~maskMask;
#else
#error Unknown cache mask storage type.
#endif
    
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;

public:
    static bucket_t *emptyBuckets();
    
    struct bucket_t *buckets();
    mask_t mask();
    mask_t occupied();
    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    // 省略很多方法...
}

发现比较重要的成员 _buckets

struct bucket_t {
private:
#if __arm64__      //  真机
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
// 省略部分方法...
public:
    inline SEL sel() const { return _sel.load(memory_order::memory_order_relaxed); }

    inline IMP imp(Class cls) const {
        // 省略实现...
        return (IMP)imp;
    }
};

bucket_t 里面就2个成员变量，可见cache中有我们要找的方法。

_imp : 方法实现
_sel ：方法指针

1.2 打印cache_t

实践代码：

@interface GLPerson : NSObject

@property (nonatomic, strong) NSString *name; /**<  8个字节  */
@property (nonatomic, strong) NSString *nickName; /**<  8个字节  */

- (void)sayHello1;
- (void)sayHello2;
- (void)sayHello3;
- (void)sayHello4;

@end
---
        GLPerson *p = [GLPerson alloc];
        [p sayHello1];
        [p sayHello2];
        [p sayHello3];
        [p sayHello4];

断点打印 [GLPerson class] 的内存，然后通过内存偏移找到 cache_t。

在分析类的时候，知道 cache_t 偏移 16 字节。所以可通过如下调试打印出 cache_t。

第一次我先在调用第一个实例方法之前打断点，[p sayHello1]; 打个断点，然后打印：

(lldb) x/4gx GLPerson.class
0x1000022f8: 0x00000001000022d0 0x0000000100334140
0x100002308: 0x000000010032e440 0x0000802400000000
(lldb) p 0x1000022f8 + 0x10
(long) $1 = 4294976264
(lldb) p (cache_t *)$1
(cache_t *) $2 = 0x0000000100002308
(lldb) p *$2
(cache_t) $3 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x000000010032e440 {
      _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
}

然后调用 [p sayHello1] 之后：

(lldb) p *$2
(cache_t) $4 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x0000000101c8e800 {
      _sel = {
        std::__1::atomic<objc_selector *> = (null)
      }
      _imp = {
        std::__1::atomic<unsigned long> = 0
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 3
  }
  _flags = 32804
  _occupied = 1
}

再往下调用

// 调用 sayHello2 之后
(lldb) p *$2
(cache_t) $6 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x0000000101c8e800 {
      _sel = {
        std::__1::atomic<objc_selector *> = ""
      }
      _imp = {
        std::__1::atomic<unsigned long> = 12200
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 3
  }
  _flags = 32804
  _occupied = 2
}
// 调用完4个方法
(lldb) p *$2
(cache_t) $7 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x0000000101a0c160 {
      _sel = {
        std::__1::atomic<objc_selector *> = (null)
      }
      _imp = {
        std::__1::atomic<unsigned long> = 0
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 7
  }
  _flags = 32804
  _occupied = 2
}

可以看出调用方法之后，类的 cache_t 成员变量变化了。

1.3 打印方法名

再回到调用第一个方法之后

(lldb) p *$1   // 打印cache_t
(cache_t) $3 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x0000000100645710 {
      _sel = {
        std::__1::atomic<objc_selector *> = ""
      }
      _imp = {
        std::__1::atomic<unsigned long> = 11824
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 3
  }
  _flags = 32804
  _occupied = 1
}
(lldb) p $3.buckets()
(bucket_t *) $4 = 0x0000000100645710
(lldb) p *$4
(bucket_t) $5 = {
  _sel = {
    std::__1::atomic<objc_selector *> = ""
  }
  _imp = {
    std::__1::atomic<unsigned long> = 11824
  }
}
(lldb) p $5.sel()   // bucket_t的sel()方法
(SEL) $6 = "sayHello1"
(lldb) p $5.imp(pClass)   // bucket_t的imp(Class)方法
(IMP) $7 = 0x0000000100000d30 (KCObjc`-[GLPerson sayHello1])

总结:

先得到 (cache_t *)$1;
p *$1 得到 (cache_t) $3;
调用 cache_t的 buckets 方法，p $3.buckets()，得到 (bucket_t *) $4;
p *$4 得到 (bucket_t) $5;
调用 bucket_t 的 sel() 方法，打印出 (SEL) $6 = "sayHello1" SEL 名称；
调用 bucket_t 的 imp(Class cls) 方法，打印出 (IMP) $7 = 0x0000000100000d30 (-[GLPerson sayHello1]) IMP实现地址；

然后调用完四个方法之后再打印：

(lldb) p $9.buckets()
(bucket_t *) $10 = 0x0000000101a07960
(lldb) p *$10
(bucket_t) $11 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null)
  }
  _imp = {
    std::__1::atomic<unsigned long> = 0
  }
}
(lldb) p $11.sel()
(SEL) $12 = <no value available>
(lldb) p *($10+1)
(bucket_t) $13 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null)
  }
  _imp = {
    std::__1::atomic<unsigned long> = 0
  }
}
(lldb) p *($10+2)
(bucket_t) $14 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null)
  }
  _imp = {
    std::__1::atomic<unsigned long> = 0
  }
}
(lldb) p *($10+3)
(bucket_t) $15 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null)
  }
  _imp = {
    std::__1::atomic<unsigned long> = 0
  }
}
(lldb) p *($10+4)
(bucket_t) $16 = {
  _sel = {
    std::__1::atomic<objc_selector *> = ""
  }
  _imp = {
    std::__1::atomic<unsigned long> = 11856
  }
}
(lldb) p $15.sel()
(SEL) $17 = <no value available>
(lldb) p $16.sel()
(SEL) $18 = "sayHello3"
(lldb) p *($10+5)
(bucket_t) $19 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null)
  }
  _imp = {
    std::__1::atomic<unsigned long> = 0
  }
}
(lldb) p *($10+6)
(bucket_t) $20 = {
  _sel = {
    std::__1::atomic<objc_selector *> = ""
  }
  _imp = {
    std::__1::atomic<unsigned long> = 11872
  }
}
(lldb) p $19.sel()
(SEL) $21 = <no value available>
(lldb) p $20.sel()
(SEL) $22 = "sayHello4"
 // 再往下继续加，不是null就是其他东西了

可以知道，_buckets里面就是存已经调用的方法的，调用完四个方法之后，发现这个_buckets里面存的方法却不是按顺序排的，而是随机的，中间可能还为空。

cache_t结构分析.jpeg

二、cache 是怎么存的

上面在打印 cache_t 的时候，发现有个变量 _occupied 是不是也在改变，还有 _mask 变量。

2.1 _occupied追踪

objc 源码全局搜索一下 _occupied，发现用到的地方很少，其中只有下面一个方法能让 _occupied 增加。

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

只有 cache_t 的 incrementOccupied 方法可增加 _occupied 的值。

再搜索 incrementOccupied 的调用地方，

只有 cache_t 的 insert 方法调用 incrementOccupied。

void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
    runtimeLock.assertLocked();

#if !DEBUG_TASK_THREADS
    // Never cache before +initialize is done
    if (cls->isInitialized()) {
        cache_t *cache = getCache(cls);
#if CONFIG_USE_CACHE_LOCK
        mutex_locker_t lock(cacheUpdateLock);
#endif
        cache->insert(cls, sel, imp, receiver);
    }
#else
    _collecting_in_critical();
#endif
}

只有 cache_fill 方法调用 cache->insert。
再网上追溯，就脱离 cache 了，通过打断点可见调用方法

_occupied追溯源头.png

发送方法以后再分析，先继续关注 cache_t。

2.2 cache->insert 存方法

ALWAYS_INLINE
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);
    }
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) {
        // Cache is less than 3/4 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);
    }

    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.
    do {
        if (fastpath(b[i].sel() == 0)) {
            incrementOccupied();
            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));

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

bool cache_t::isConstantEmptyCache()
{
    return 
        occupied() == 0  &&  
        buckets() == emptyBucketsForCapacity(capacity(), false);
}
---
static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;
}
---
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}
---
enum {
    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2),
    MAX_CACHE_SIZE_LOG2  = 16,
    MAX_CACHE_SIZE       = (1 << MAX_CACHE_SIZE_LOG2),
};
---
#define CACHE_END_MARKER 1

流程分析：

赋值 newOccupied = occupied() + 1，oldCapacity = capacity = capacity()；;
判断 cache 是否为空，为空的话释放旧的，开辟新的大小，新的为4;
newOccupied + CACHE_END_MARKER <= capacity / 4 * 3，如果 occupied + 1 之后还小于等于 occupied 的 3/4 的话，就还用他自己；
最后就是超过了 3/4 之后，会做 2 倍扩容，capacity * 2, 但是最大不超过 2¹⁶；
声明一个 buckets() 数组，m = capacity - 1，begin = cache_hash(sel, m), i = begin；
加入m = 3, 可知任何一个数 & 3 得到的肯定小于等于3，也就是 begin 肯定会小于capacity，capacity 既可以理解为 buckets 的边界大小；
do while 循环中，判断 b[i].sel() 是否存在；
等于0，说明不存在，调用 incrementOccupied 使 _occupied++，b[i].set<Atomic, Encoded>(sel, imp, cls) 缓存方法，结束；
存在并且等于要存的方法，说明在其它线程已经存了，结束；
b[i].sel() 既不等于0，也不等于要存的方法；
(i = cache_next(i, m)) != begin) , 把 i = (i + 1) & m，判断 i 是否等于 begin，如果等于，重复 步骤11，如果不等于回到 步骤7；

cache_t方法缓存流程.001.jpeg

2.3 真机环境的代码

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);
    
    _maskAndBuckets.store(((uintptr_t)newMask << maskShift) | (uintptr_t)newBuckets, std::memory_order_relaxed);
    _occupied = 0;
}

struct bucket_t *cache_t::buckets()
{
    uintptr_t maskAndBuckets = _maskAndBuckets.load(memory_order::memory_order_relaxed);
    return (bucket_t *)(maskAndBuckets & bucketsMask);
}

mask_t cache_t::mask()
{
    uintptr_t maskAndBuckets = _maskAndBuckets.load(memory_order::memory_order_relaxed);
    return maskAndBuckets >> maskShift;
}

在64位真机真机中，没有 _buckets 和 _mask 成员变量。但是有_maskAndBuckets 成员变量，从名字是不是能看出来，这里面存了前面2个变量值，就和 isa 的时候用位域，不同的内容存的位不一样。

从 setBucketsAndMask 方法中可以看出来：

_maskAndBuckets.store(((uintptr_t)newMask << maskShift) | (uintptr_t)newBuckets, std::memory_order_relaxed);

<uintptr_t> _maskAndBuckets : long 类型，8字节，64位；
mask_t newMask : int 类型；
maskShift : 48;

(newMask << maskShift) | newBuckets
(newMask << 48) | newBuckets

即：newMask 存在高 16 位，newBuckets 存在低 48 位上。

三、取方法

通过 clang 把调用方法的代码转成 cpp 源文件，查看调用的时候用的什么方法，可以发现是 _objc_msgSend，源码中搜索 _objc_msgSend

_objc_msgSend.png

arm64_objc_msgSend.png

发现是汇编实现的，😳

    ENTRY _objc_msgSend
    UNWIND _objc_msgSend, NoFrame

    cmp p0, #0          // nil check and tagged pointer check
#if SUPPORT_TAGGED_POINTERS
    b.le    LNilOrTagged        //  (MSB tagged pointer looks negative)
#else
    b.eq    LReturnZero
#endif
    ldr p13, [x0]       // p13 = isa
    GetClassFromIsa_p16 p13     // p16 = class
LGetIsaDone:
    // calls imp or objc_msgSend_uncached
    CacheLookup NORMAL, _objc_msgSend

#if SUPPORT_TAGGED_POINTERS
LNilOrTagged:
    b.eq    LReturnZero     // nil check

    // tagged
    adrp    x10, _objc_debug_taggedpointer_classes@PAGE
    add x10, x10, _objc_debug_taggedpointer_classes@PAGEOFF
    ubfx    x11, x0, #60, #4
    ldr x16, [x10, x11, LSL #3]
    adrp    x10, _OBJC_CLASS_$___NSUnrecognizedTaggedPointer@PAGE
    add x10, x10, _OBJC_CLASS_$___NSUnrecognizedTaggedPointer@PAGEOFF
    cmp x10, x16
    b.ne    LGetIsaDone

    // ext tagged
    adrp    x10, _objc_debug_taggedpointer_ext_classes@PAGE
    add x10, x10, _objc_debug_taggedpointer_ext_classes@PAGEOFF
    ubfx    x11, x0, #52, #8
    ldr x16, [x10, x11, LSL #3]
    b   LGetIsaDone
// SUPPORT_TAGGED_POINTERS
#endif

LReturnZero:
    // x0 is already zero
    mov x1, #0
    movi    d0, #0
    movi    d1, #0
    movi    d2, #0
    movi    d3, #0
    ret

    END_ENTRY _objc_msgSend

里面有一句代码

    // calls imp or objc_msgSend_uncached
    CacheLookup NORMAL, _objc_msgSend

感觉有点对上了，看注释要么调用imp，要么调用 objc_msgSend_uncached，调用 objc_msgSend_uncached 的话，就走到了上面分析的存方法的流程了。

找到 CacheLookup 发现还是汇编：

.macro CacheLookup
    //
    // Restart protocol:
    //
    //   As soon as we're past the LLookupStart$1 label we may have loaded
    //   an invalid cache pointer or mask.
    //
    //   When task_restartable_ranges_synchronize() is called,
    //   (or when a signal hits us) before we're past LLookupEnd$1,
    //   then our PC will be reset to LCacheMiss$1 which forcefully
    //   jumps to the cache-miss codepath.
    //
    //   It is assumed that the CacheMiss codepath starts right at the end
    //   of CacheLookup2 and will re-setup the registers to meet the cache-miss
    //   requirements:
    //
    //   GETIMP:
    //     The cache-miss is just returning NULL (setting r9 to 0)
    //
    //   NORMAL and STRET:
    //   - r0 or r1 (STRET) contains the receiver
    //   - r1 or r2 (STRET) contains the selector
    //   - r9 contains the isa (reloaded from r0/r1)
    //   - other registers are set as per calling conventions
    //
LLookupStart$1:

    ldrh    r12, [r9, #CACHE_MASK]  // r12 = mask
    ldr r9, [r9, #CACHE]    // r9 = buckets
.if $0 == STRET
    and r12, r12, r2        // r12 = index = SEL & mask
.else
    and r12, r12, r1        // r12 = index = SEL & mask
.endif
    add r9, r9, r12, LSL #3 // r9 = bucket = buckets+index*8
    ldr r12, [r9, #CACHED_SEL]  // r12 = bucket->sel
6:
.if $0 == STRET
    teq r12, r2
.else
    teq r12, r1
.endif
    bne 8f
    ldr r12, [r9, #CACHED_IMP]  // r12 = bucket->imp

.if $0 == STRET
    tst r12, r12        // set ne for stret forwarding
.else
    // eq already set for nonstret forwarding by `teq` above
.endif

.endmacro

.macro CacheLookup2
#if CACHED_SEL != 0
#   error this code requires that SEL be at offset 0
#endif
8:  
    cmp r12, #1
    blo LCacheMiss$1        // if (bucket->sel == 0) cache miss
    it  eq          // if (bucket->sel == 1) cache wrap
    ldreq   r9, [r9, #CACHED_IMP]   // bucket->imp is before first bucket
    ldr r12, [r9, #8]!      // r12 = (++bucket)->sel
    b   6b

LLookupEnd$1:
LCacheMiss$1:

.endmacro

汇编代码，看右边注释就行。