综合开发

iOS探索–类的结构分析(二)

微信扫一扫,分享到朋友圈

iOS探索–类的结构分析(二)

接上一篇 iOS探索–类的结构分析(一) , 在上一篇文章中, 我们进行类类的内部结构分析, 主要针对 class_rw_t 进行了一些研究, 发现了类当中的 属性成员变量类方法实例方法 是怎么存储的。但是还有一个东西我们没有去关注, 那就是 cache_t 部分, 在本次探索中我们一起来看一下。

cache_t 的结构

在我们的 objc_class 结构体找到 cache_t , 查看一下他的内部结构到底是什么样子的:

// objc_class
struct objc_class : objc_object {
// Class ISA;
Class superclass;
cache_t cache;             // formerly cache pointer and vtable
class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
class_rw_t *data() {
return bits.data();
}
/*
函数
*/
}
// cache_t
struct cache_t {
struct bucket_t *_buckets;
mask_t _mask;
mask_t _occupied;
public:
struct bucket_t *buckets(); // buckets() 函数, 返回
mask_t mask();
mask_t occupied();
void incrementOccupied();
void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
void initializeToEmpty();
mask_t capacity();
bool isConstantEmptyCache();
bool canBeFreed();
static size_t bytesForCapacity(uint32_t cap);
static struct bucket_t * endMarker(struct bucket_t *b, uint32_t cap);
void expand();
void reallocate(mask_t oldCapacity, mask_t newCapacity);
struct bucket_t * find(cache_key_t key, id receiver);
static void bad_cache(id receiver, SEL sel, Class isa) __attribute__((noreturn));
};
#if __LP64__
typedef uint32_t mask_t;  // x86_64 & arm64 asm are less efficient with 16-bits
#else
typedef uint16_t mask_t;
#endif
typedef uintptr_t cache_key_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__
MethodCacheIMP _imp;
cache_key_t _key;
#else
cache_key_t _key;
MethodCacheIMP _imp;
#endif
public:
inline cache_key_t key() const { return _key; }
inline IMP imp() const { return (IMP)_imp; }
inline void setKey(cache_key_t newKey) { _key = newKey; }
inline void setImp(IMP newImp) { _imp = newImp; }
void set(cache_key_t newKey, IMP newImp);
};
复制代码

可以看到 cache_t 结构体主要有三部分组成: _mask_occupied 和一个 bucket_t 类型的结构体指针, 且前面两个都是 unit32_t 类型的。

至于 bucket_t , 在里面发现了 _imp_key , 其实 _key 就是我们的 SEL , 通过这些其实可以看出, bucket_t 里面存放的就是我们的方法缓存。

关于 SELIMP

SEL: 类的成员方法 (实例方法) 的指针, 不同于C语言中的函数指针, 函数指针直接保存方法的地址, 但是 SEL 只是方法的符号

IMP: 一个函数指针, 保存了方法的地址

系统通过SEL在类里面找到对应的IMP然后再由IMP去调用方法。

关于 SEL 和 IMP, 有兴趣的可以去搜索一下, 这里有可能表达的不够好。

cache_t 探索

1. 初探

通过上面的分析, 我们判断 cache_t 其实就是对方法的一个缓存, 那么具体是怎么去缓存的, 我们一起来看一下:

// 准备
// 方法
- (void)sayHello;
- (void)sayGood;
- (void)sayByebye;
- (void)sayHappy;
// 调用
Person *person = [[Person alloc] init];
Class pClass = object_getClass(person);
[person sayHello];
[person sayHappy];
[person sayHappy];
[person sayGood];
[person sayByebye];
复制代码

上面准备了4个实例方法, 然后在调用过程中进行断点调试, 分别打印一下在调用方法的过程中 cache_t 的值是什么样子的。开搞:

  1. 首先类首地址偏移 16位(上图错别字请忽略:stuck_out_tongue_closed_eyes:), 得到 cache_t 的地址并打印
  2. 打印 cache_t 中的 _buckets 得到 bucket_t 结构体指针, 然后直接打印该指针的值, 发现结果是空的 bucket_t
  3. 根据命名 _buckets 我们猜测其是一个数组, 根据下标一次打印, 终于在第3个下标找到 init 方法缓存 (ps: init 对象方法同样会做缓存; 至于 alloc 在之前说过, 他是存储在元类里面的类方法)
  4. 继续往下走把所有方法执行完毕, 打印一下看看
  1. 执行结束依然接着上面的进行打印, 发现此时的 _mask = 7 , _occupied = 2 , 但是, 在方法缓存里面却只找到了两个方法, 其余 3个方法不见了。

通过上面的打印, 发现 _buckets 类似一个数组, 可以通过下标打印里面的内容, 而且我们在里面找到了方法的缓存数据。但是在第二次打印的时候发生了奇怪的事情, _buckets 的存储数量变大了 (_mask 和 _occupied都发生了变化, _mask变大了, _occupied好像是缓存的方法数量), 但是里面并没有包含我们调用的所有方法, 并且缓存的排布也是不规律的。 这中间到底发生了什么不可告人的秘密, 接下来深入探索一下吧。

2. 深入探索

上面的过程我们一直针对 _buckets 进行了打印, 但是忽略了另外两个东西 _mask_occupied 。既然存在肯定有他的价值的, 并且他们两个的值也在变化。下面先从方法的角度一起来寻找一下他们两个的用途:

2.1 cache_fill_nolock

首先查看方法, 发现 mask() 和 occupied() 方法, 查看其内部实现发现都是返回其本身, 应该是 get 方法

mask_t cache_t::mask() {
return _mask;
}
mask_t cache_t::occupied() {
return _occupied;
}
复制代码

接下来全局搜索一下 mask()occupied() 方法, 看看都在哪里用到了

// mask() 搜索
mask_t cache_t::capacity() {
return mask() ? mask()+1 : 0;
}
// occupied() 搜索
static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver) {
cacheUpdateLock.assertLocked();
// Never cache before +initialize is done
if (!cls->isInitialized()) return;
// Make sure the entry wasn't added to the cache by some other thread
// before we grabbed the cacheUpdateLock.
if (cache_getImp(cls, sel)) return;
cache_t *cache = getCache(cls);
cache_key_t key = getKey(sel);
// Use the cache as-is if it is less than 3/4 full
mask_t newOccupied = cache->occupied() + 1;
mask_t capacity = cache->capacity();
if (cache->isConstantEmptyCache()) {
// Cache is read-only. Replace it.
cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
}
else if (newOccupied <= capacity / 4 * 3) {
// Cache is less than 3/4 full. Use it as-is.
}
else {
// Cache is too full. Expand it.
cache->expand();
}
// 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.
bucket_t *bucket = cache->find(key, receiver);
if (bucket->key() == 0) cache->incrementOccupied();
bucket->set(key, imp);
}
复制代码

全局搜索发现用的地方不多, 这里没有一一列举, 首先发现 capacity() 方法中使用 了 mask() , 并且如果 mask 有值的话, 取出时进行了 + 1 操作。然后在 cache_fill_nolock 方法中使用了 capacity() 和 occupied() 方法, 仔细查看该方法名, 猜测该方法就是用来进行做方法 缓存 的。下面来分步看一下里面的操作:

  1. if (!cls->isInitialized()) return;

    判断类是否已经初始化对象, 没有就直接返回

  2. if (cache_getImp(cls, sel)) return;

    根据传入的 类 cls 和 方法的 sel 查找 imp 的缓存数据, 如果过去到就返回, 避免重复缓存

  3. 获取当前缓存 cache , 将传入的 sel 转化成存储需要的 key ; 并且从 cache 中获取到 mask + 1 的结果(即 capacity 总容量) 和 occupied 的值做 +1 处理( 即 newOccupied 新的缓存数量)

    cache_t *cache = getCache(cls);
    cache_key_t key = getKey(sel);
    mask_t newOccupied = cache->occupied() + 1; // 旧的缓存 +1, 得到新的缓存数量
    mask_t capacity = cache->capacity(); // 缓存的总容量
    复制代码
  4. 使用上面获取到的结果进行判断

    if (cache->isConstantEmptyCache()) {
    // Cache is read-only. Replace it.
    cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
    }
    else if (newOccupied <= capacity / 4 * 3) {
    // Cache is less than 3/4 full. Use it as-is.
    }
    else {
    // Cache is too full. Expand it.
    cache->expand();
    }
    // INIT_CACHE_SIZE
    /* Initial cache bucket count. INIT_CACHE_SIZE must be a power of two. */
    enum {
    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2)
    };
    复制代码

    首先判断 cache 是否为空, 如果是空就根据传进来的 capacity 进行空间开辟, 这里的 INIT_CACHE_SIZE 需要说明一下, 可以看下面的枚举, 他的值默认是 1 << 2 , 也就是 4 (二进制的 100) , 上面的注释的意思 INIT_CACHE_SIZE 必须是 2的多少次方的结果。

    然后判断 newOccupied <= capacity / 4 * 3 , 如果 新的缓存占用大小 小于 缓存总容量的四分之三 的话, 可以进行缓存

    如果 大于缓存总容量的四分之三 , 执行 cache->expand() 扩容操作。

  5. 执行缓存

    // 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.
    bucket_t *bucket = cache->find(key, receiver);
    if (bucket->key() == 0) cache->incrementOccupied();
    bucket->set(key, imp);
    // incrementOccupied()
    void cache_t::incrementOccupied() {
    _occupied++;
    }
    复制代码

    通过 keycache 中找到对应的 bucket , 判断如果 bucket->key() == 0 (也就是还没有存储进去) , 执行 _occupied++ , 把 keyimp 存储到该 bucket 中去。

2.2 reallocate ( )

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity) {
bool freeOld = canBeFreed();
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) {
cache_collect_free(oldBuckets, oldCapacity);
cache_collect(false);
}
}
// canBeFreed()
bool cache_t::canBeFreed() {
return !isConstantEmptyCache();
}
// allocateBuckets()
bucket_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.
// fixme instead put the end mark inline when +1 is malloc-inefficient
bucket_t *newBuckets = (bucket_t *)
calloc(cache_t::bytesForCapacity(newCapacity), 1);
bucket_t *end = cache_t::endMarker(newBuckets, newCapacity);
#if __arm__
// End marker's key is 1 and imp points BEFORE the first bucket.
// This saves an instruction in objc_msgSend.
end->setKey((cache_key_t)(uintptr_t)1);
end->setImp((IMP)(newBuckets - 1));
#else
// End marker's key is 1 and imp points to the first bucket.
end->setKey((cache_key_t)(uintptr_t)1);
end->setImp((IMP)newBuckets);
#endif
if (PrintCaches) recordNewCache(newCapacity);
return newBuckets;
}
// setBucketsAndMask()
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.
// ensure other threads see buckets contents before buckets pointer
mega_barrier();
_buckets = newBuckets;
// ensure other threads see new buckets before new mask
mega_barrier();
_mask = newMask;
_occupied = 0;
}
复制代码

以上的代码是执行 reallocate ( ) , 也就是开辟 cache 空间的操作。

  • 首先 canBeFreed() , 是用来判断 cache 是否有值, 可以看到实现里是用的 !isConstantEmptyCache() , 如果是有值的, 在方法的最后做了 freeOld 操作, 清空了旧的缓存数据
  • 使用传进来的 newCapacity 调用 allocateBuckets() 方法创建新的 bucket_t
  • 调用 setBucketsAndMask() 方法, 设置新的 bucket , 并且 _mask = newCapacity - 1, _occupied = 0 (所以我们打印的 mask的值 其实是 最大数量 – 1)

这里在创建完新的之后把旧的缓存直接删除了, 而不是读取出来重新存到新的缓存中去。

一 是因为如果重新读出来再缓存进去浪费时间, 直接抹掉速度更快

二 是因为读写操作不安全

2.3 expand( )

void cache_t::expand()
{
cacheUpdateLock.assertLocked();
uint32_t oldCapacity = capacity();
uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;
if ((uint32_t)(mask_t)newCapacity != newCapacity) {
// mask overflow - can't grow further
// fixme this wastes one bit of mask
newCapacity = oldCapacity;
}
reallocate(oldCapacity, newCapacity);
}
复制代码

expand() 从名字意思也可以判断出, 这个方法是用来扩容的

  • 可以看到在扩容之前, 首先获取到了旧的 capacity , 也就是 mask + 1
  • 然后判断, 如果旧的 capacity 有值的话 直接乘以2, 增加一倍 , 如果没有值的话, 就给他赋值为 4 (INIT_CACHE_SIZE 为 4)
  • 最后进行 reallocate() 方法开辟新的空间

2.4 find( )

bucket_t * cache_t::find(cache_key_t k, id receiver) {
assert(k != 0);
bucket_t *b = buckets();
mask_t m = mask();
// 通过cache_hash函数【begin  = k & m】计算出key值 k 对应的 index值 begin,用来记录查询起始索引
mask_t begin = cache_hash(k, m);
// begin 赋值给 i,用于切换索引
mask_t i = begin;
do {
if (b[i].key() == 0  ||  b[i].key() == k) {
//用这个i从散列表取值,如果取出来的bucket_t的 key = k,则查询成功,返回该bucket_t,
//如果key = 0,说明在索引i的位置上还没有缓存过方法,同样需要返回该bucket_t,用于中止缓存查询。
return &b[i];
}
} while ((i = cache_next(i, m)) != begin);
// 这一步其实相当于 i = i-1,回到上面do循环里面,相当于查找散列表上一个单元格里面的元素,再次进行key值 k的比较,
//当i=0时,也就i指向散列表最首个元素索引的时候重新将mask赋值给i,使其指向散列表最后一个元素,重新开始反向遍历散列表,
//其实就相当于绕圈,把散列表头尾连起来,不就是一个圈嘛,从begin值开始,递减索引值,当走过一圈之后,必然会重新回到begin值,
//如果此时还没有找到key对应的bucket_t,或者是空的bucket_t,则循环结束,说明查找失败,调用bad_cache方法。
// hack
Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
cache_t::bad_cache(receiver, (SEL)k, cls);
}
// cache_hask()
// Class points to cache. SEL is key. Cache buckets store SEL+IMP.
// Caches are never built in the dyld shared cache.
static inline mask_t cache_hash(cache_key_t key, mask_t mask) {
return (mask_t)(key & mask);
}
// cache_next()
#if __arm__  ||  __x86_64__  ||  __i386__
// objc_msgSend has few registers available.
// Cache scan increments and wraps at special end-marking bucket.
#define CACHE_END_MARKER 1
static inline mask_t cache_next(mask_t i, mask_t mask) {
return (i+1) & mask;
}
#elif __arm64__
// objc_msgSend has lots of registers available.
// Cache scan decrements. No end marker needed.
#define CACHE_END_MARKER 0
static inline mask_t cache_next(mask_t i, mask_t mask) {
return i ? i-1 : mask;
}
#else
#error unknown architecture
#endif
复制代码

前面的几个方法一直围绕 插入缓存 和 重新开辟 新的缓存区域做处理, 那么既然存储进去了就肯定有读取的地方。下面我们来看看 find() 是如何实现读取的

注意: 在这里我们终于发现 bucket_t 到底是什么了, 他其实是一个 哈希表(散列表), 所以里面存储的数据是随机存储的

  • 先通过 buckets() 方法, 获取到 _buckets ; 使用 mask() 获取到 _mask
  • 调用 cache_hask() 也就是 key & mask 得到一个起始的索引 begin
  • begin 赋值给 i , 进行一个 do-while 循环, 看一下循环的条件 cache_next() , 这里其实是在做 i-1 操作, 当 i-10 时, 返回的是 mask (也就是最后一个元素) , 然后进行反向循环, 从而达到查询每一个元素
  • 最后如果在这过程中找到就没有问题, 如果一直执行到 回到 begin 都没有找到, 就继续往下走调用 bad_cache 错误处理

总结

至此我们对 cache_t 的探索基本结束了, 下面一起来总结一下关于 cache 都有哪些内容:

  1. cache_t 是对实例方法进行的缓存操作, 包含 _mask_occupied_buckets 三部分

  2. mask 的大小为 缓存容量的大小 – 1 , 主要使用在查找缓存时的 哈希算法 中; occupied 存储的是 缓存的方法的数量

  3. capacity 可以通过 capacity() 方法获取到, 表示当前缓存的大小, 初始大小为 4 , 如果进行 cache_fill_nolock() 缓存操作时, 判断到缓存后的 occupied 大于 capacity四分之三 , 就会对其进行扩容为原来的 2倍

    至于为什么是 四分之三扩容, 这里牵扯到哈希冲突, 有兴趣的可以去网上搜索一下

  4. 还有一点需要说明的是在进行扩容以后, 系统将之前的缓存数据全部清除了 , 这里涉及到 LRU算法 (最近最少使用原则)

    这里我觉得应该算是相似吧, 因为我们这里是在扩容之后把 之前的所有数据删除 , 而 LRU 的原则是 当空间存满时, 把最久没有被访问到的数据淘汰

    因为对算法不是很熟悉, 关于这一点, 希望能有大佬帮我解惑一下, 是不是这样子的。

以上就是本次的全部内容了, 如果有什么不足的地方或者有疑问的地方, 欢迎各大佬指正和提出, 感谢阅读~~~!

【剑指offer:和为s的连续正数序列】巧用快慢指针

上一篇

万字实践|UNI-APP

下一篇

你也可能喜欢

评论已经被关闭。

插入图片

热门栏目

iOS探索–类的结构分析(二)

长按储存图像,分享给朋友