【iOS】SideTable

用户云卷云舒  金牌会员 | 2024-9-12 15:18:18 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 793|帖子 793|积分 2379

objc4源码地址：
  1. SideTable& table = SideTables()[this];  // 获取对象的SideTable
  2. size_t& refcntStorage = table.refcnts[this];
复制代码
SideTables

查源码SideTables的结构如下：
  1. // SideTables在C++的initializers函数之前被调用，所以不能使用C++初始化函数来初始化SideTables
  2. // 不能使用全局指针来指向这个结构体，因为涉及到重定向问题；
  3. template <typename Type>
  4. class ExplicitInit {
  5.     alignas(Type) uint8_t _storage[sizeof(Type)];
  7. public:
  8.     template <typename... Ts>
  9.     void init(Ts &&... Args) {
  10.         new (_storage) Type(std::forward<Ts>(Args)...);
  11.     }
  13.     Type &get() {
  14.         return *reinterpret_cast<Type *>(_storage);
  15.     }
  16. };
  18. static objc::ExplicitInit<StripedMap<SideTable>> SideTablesMap;
  19. static StripedMap<SideTable>& SideTables() {
  20.     return SideTablesMap.get();
  21. }
复制代码
简化后：
  1. alignas(StripedMap<SideTable>) static uint8_t _storage[sizeof(StripedMap<SideTable>)];
  2. static StripedMap<SideTable>& SideTables() {
  3.     return *reinterpret_cast<StripedMap<SideTable> *>(_storage);
  4. }
复制代码


  • SideTables()使用static修饰，是一个静态函数
  • reinterpret_cast是一个强制范例转换符号
  • 终极返回一个_storage，是一个长度为sizeof(StripedMap)的unsigned char范例数组，其本质就是一个大小为和StripedMap<SideTable>对象同等的内存块，即_storage指一个StripedMap<SideTable>对象
StripedMap

StripedMap结构：
  1. enum { CacheLineSize = 64 };
  3. template<typename T>
  4. class StripedMap {
  5. #if TARGET_OS_IPHONE && !TARGET_OS_SIMULATOR
  6.     enum { StripeCount = 8 };
  7. #else
  8.     enum { StripeCount = 64 };
  9. #endif
  11.     struct PaddedT {
  12.         T value alignas(CacheLineSize);
  13.     };
  16.         //在整个项目中，如果只初始化一个SideTable和所有对象的weak_table_t表，这样的效率会很低，因为有spinlock_t加锁、解锁而造成低效的问题。但是如果每个对象都创建SideTable和weak_table_t表，效率是高了但是内存占用过高
  17.         // 来看看Apple是如何解决这个问题的
  18.     PaddedT array[StripeCount];
  20.     static unsigned int indexForPointer(const void *p) {
  21.             // 核心算法，均匀分配到真机8张表中
  22.         uintptr_t addr = reinterpret_cast<uintptr_t>(p);
  23.         return ((addr >> 4) ^ (addr >> 9)) % StripeCount;
  24.     }
  26. public:
  27.     T& operator[] (const void *p) {
  28.         return array[indexForPointer(p)].value;
  29.     }
  30.     const T& operator[] (const void *p) const {
  31.         return const_cast<StripedMap<T>>(this)[p];
  32.     }
  33. // ...省略了对象方法...
  34. };
复制代码


  • StripedMap是用做：缓存带有spinlock_t锁的本领的类大概是结构体。这个Map的个数是固定的，模拟器64个，真机是8个
  • CacheLineSize为 64，使用 T 定义了一个结构体，而 T 就是 SideTable 范例
  • 生成了一个长度为 8 范例为 SideTable 的数组
  • indexForPointer()逻辑为根据传入的对象指针，经过肯定的算法，计算出在array中存储该指针的位置index，即拿到Hash值，因为使用了取模运算，所以值的范围是 0 ~（StripeCount-1），所以不会出现数组越界
  • 此类对[]运算符举行了重载，所以从SideTables中取出SideTable的操作SideTables()[this]，实际就是SideTables().array[indexForPointer(this)].value
至此，SideTables 的含义已经很清楚了：


  • SideTables可以明白成一个范例为StripedMap静态全局对象，内部以数组（哈希表）的情势存储了StripeCount个SideTable
SideTable

之前学习的isa指针探究中有一个位域的值是用来存储引用计数的

has_sidetable_rc：引用计数是否过大无法存储在isa中，假如为1，那么引用计数会存储在一个叫SideTable的类的属性中
  1. // RefcountMap 伪装了它的指针，因为我们不希望表成为“泄漏”的根源
  2. typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,RefcountMapValuePurgeable> RefcountMap;
  4. // 模版参数
  5. enum HaveOld { DontHaveOld = false, DoHaveOld = true };
  6. enum HaveNew { DontHaveNew = false, DoHaveNew = true };
  8. struct SideTable {
  9.         // 保证原子操作的自旋锁
  10.     spinlock_t slock;
  11.     // 存储引用计数的 hash 表
  12.     RefcountMap refcnts;
  13.     // weak 引用全局 hash 表
  14.     weak_table_t weak_table;
  16.     SideTable() {
  17.         memset(&weak_table, 0, sizeof(weak_table));
  18.     }
  20.     ~SideTable() {
  21.         _objc_fatal("Do not delete SideTable.");
  22.     }
  24.     void lock() { slock.lock(); }
  25.     void unlock() { slock.unlock(); }
  26.     void reset() { slock.reset(); }
  28.     // 针对一对sidetables的地址有序锁定规则
  30.     template<HaveOld, HaveNew>
  31.     static void lockTwo(SideTable *lock1, SideTable *lock2);
  32.     template<HaveOld, HaveNew>
  33.     static void unlockTwo(SideTable *lock1, SideTable *lock2);
  34. };
复制代码
1. spinlock_t slock

spinlock_t底层是os_unfair_lock自旋锁，操作引用计数时对SideTable加锁，防止数据错乱
os_unfair_lock又是一个非公平锁，获取锁的次序和申请的次序无关，即可能 A 线程第一个申请锁，却在 B、C 得到锁之后 A 才得到锁
有关锁看此文：【iOS】线程同步&读写安全技术（锁、信号量、同步串行队列）
2. RefcountMap

RefcountMap就是DenseMap，一个模版类：
  1. typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap;
  3. template <typename KeyT, typename ValueT,
  4.           typename ValueInfoT = DenseMapValueInfo<ValueT>,
  5.           typename KeyInfoT = DenseMapInfo<KeyT>,
  6.           typename BucketT = detail::DenseMapPair<KeyT, ValueT>>
  7. class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT>,
  8. KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT> {
  9.   // ...
  10.   BucketT *Buckets;
  11.   unsigned NumEntries;
  12.   unsigned NumTombstones;
  13.   unsigned NumBuckets;
  14. public:
  15.   // ...
  16. };
复制代码


  • Buckets为一个数组，数组范例为BucketT，这里把一个数组元素称为一个桶或槽
    1. typedef std::pair<KeyT, ValueT> BucketT;
    复制代码
    所以Buckets就是一个哈希桶，存储情势就是对象地址 : 引用计数
  • NumEntries：记载数组中非空桶的数目
  • NumTombstones：记载数组中墓碑桶的数目，墓碑桶就是存在过元素但已经被删除了的桶，其作用详见此文：（数据结构）散列表条记
  • NumBuckets：桶的数目，即数组长度
桶数组开辟空间，决定命组大小：
  1. inline uint64_t NextPowerOf2(uint64_t A) {
  2.   A |= (A >> 1);
  3.   A |= (A >> 2);
  4.   A |= (A >> 4);
  5.   A |= (A >> 8);
  6.   A |= (A >> 16);
  7.   A |= (A >> 32);
  8.   return A + 1;
  9. }
复制代码
这个算法可以做到把最高位的 1 覆盖到所有低位
比方A = 0b10000，
(A >> 1) = 0b01000, 按位或就会得到A = 0b11000，
(A >> 2) = 0b00110, 按位或就会得到A = 0b11110。
以此类推 A 的最高位的 1，会一直覆盖到高 2 位、高 4 位、高 8 位, 直到最低位.，最后这个充满 1 的二进制数会再加 1，得到一个 0b1000…(N 个 0)。 也就是说, 桶数组的大小会是 2^n
RefCountMap工作流程
根据对象地址的哈希值从SideTables中获取对应的SideTable（哈希值重复的对象引用计数存储在同一个SideTable里）
SideTable使用RefCountMap（Buckets数组）中的find()方法和重载[]运算符的方式（table.refcnts.find(this)或table.refcnts[this]），根据对象地址来确定桶的位置，查找算法终极会调用函数LookupBucketFor
查找算法会先对桶的个数举行判断, 假如桶数为 0 则 return false 回上一级调用插入方法. 假如查找算法找到空桶大概墓碑桶, 同样 return false 回上一级调用插入算法, 不外会先记载下找到的桶. 假如找到了对象对应的桶, 只需要对其引用计数 + 1 大概 - 1. 假如引用计数为 0 需要销毁对象, 就将这个桶中的 key 设置为 TombstoneKey：
  1. bool LookupBucketFor(const LookupKeyT &Val,
  2.                        const BucketT *&FoundBucket) const {
  3.     // ...
  4.     if (NumBuckets == 0) { // 桶数是0
  5.       FoundBucket = 0;
  6.       return false; // 返回 false 回上层调用添加函数
  7.     }
  8.     // ...
  9.     unsigned BucketNo = getHashValue(Val) & (NumBuckets-1); //将哈希值与数组最大下标按位与
  10.     unsigned ProbeAmt = 1; // 哈希值重复的对象需要靠它来重新寻找位置
  11.     while (1) {
  12.       const BucketT *ThisBucket = BucketsPtr + BucketNo; // 头指针 + 下标, 类似于数组取值
  13.       // 找到的桶中的 key 和对象地址相等, 则是找到
  14.       if (KeyInfoT::isEqual(Val, ThisBucket->first)) {
  15.         FoundBucket = ThisBucket;
  16.         return true;
  17.       }
  18.       // 找到的桶中的 key 是空桶占位符, 则表示可插入
  19.       if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) {
  20.         if (FoundTombstone) ThisBucket = FoundTombstone; // 如果曾遇到墓碑, 则使用墓碑的位置
  21.         FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
  22.         return false; // 找到空占位符, 则表明表中没有已经插入了该对象的桶
  23.       }
  24.       // 如果找到了墓碑
  25.       if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone)
  26.         FoundTombstone = ThisBucket;  // 记录下墓碑
  27.       // 这里涉及到最初定义 typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap, 传入的第三个参数 true
  28.       // 这个参数代表是否可以清除 0 值, 也就是说这个参数为 true 并且没有墓碑的时候, 会记录下找到的 value 为 0 的桶
  29.       if (ZeroValuesArePurgeable  &&
  30.           ThisBucket->second == 0  &&  !FoundTombstone)
  31.         FoundTombstone = ThisBucket;
  33.       // 用于计数的 ProbeAmt 如果大于了数组容量, 就会抛出异常
  34.       if (ProbeAmt > NumBuckets) {
  35.           _objc_fatal("...");
  36.       }
  37.       BucketNo += ProbeAmt++; // 本次哈希计算得出的下表不符合, 则利用 ProbeAmt 寻找下一个下标
  38.       BucketNo&= (NumBuckets-1); // 得到新的数字和数组下标最大值按位与
  39.     }
  40. }
复制代码
插入算法会先查看可用量, 假如哈希表的可用量(墓碑桶+空桶的数目)小于 1/4, 则需要为表重新开辟更大的空间, 假如表中的空桶位置少于 1/8 (说明墓碑桶过多), 则需要清理表中的墓碑. 以上两种环境下哈希查找算法会很难查找准确位置, 甚至可能会产存亡循环, 所以要先处理表, 处理表之后还会重新分配所有桶的位置, 之后重新查找当前对象的可用位置并插入. 假如没有发生以上两种环境, 就直接把新的对象的引用计数放入调用者提供的桶里：
  1. BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) {
  2.     unsigned NewNumEntries = getNumEntries() + 1; //桶的使用量 +1
  3.     unsigned NumBuckets = getNumBuckets(); //桶的总数
  4.     if (NewNumEntries*4 >= NumBuckets*3) { //使用量超过 3/4
  5.       this->grow(NumBuckets * 2); //数组大小 * 2做参数, grow 中会决定具体数值
  6.       //grow 中会重新布置所有桶的位置, 所以将要插入的对象也要重新确定位置
  7.       LookupBucketFor(Key, TheBucket);
  8.       NumBuckets = getNumBuckets(); //获取最新的数组大小
  9.     }
  10.     //如果空桶数量少于 1/8, 哈希查找会很难定位到空桶的位置
  11.     if (NumBuckets-(NewNumEntries+getNumTombstones()) <= NumBuckets/8) {
  12.       //grow 以原大小重新开辟空间, 重新安排桶的位置并能清除墓碑
  13.       this->grow(NumBuckets);
  14.       LookupBucketFor(Key, TheBucket); //重新布局后将要插入的对象也要重新确定位置
  15.     }
  16.     assert(TheBucket);
  17.     //找到的 BucketT 标记了 EmptyKey, 可以直接使用
  18.     if (KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) {
  19.       incrementNumEntries(); //桶使用量 +1
  20.     }
  21.     else if (KeyInfoT::isEqual(TheBucket->first, getTombstoneKey())) { //如果找到的是墓碑
  22.       incrementNumEntries(); //桶使用量 +1
  23.       decrementNumTombstones(); //墓碑数量 -1
  24.     }
  25.     else if (ZeroValuesArePurgeable  &&  TheBucket->second == 0) { //找到的位置是 value 为 0 的位置
  26.       TheBucket->second.~ValueT(); //测试中这句代码被直接跳过并没有执行, value 还是 0
  27.     } else {
  28.       // 其它情况, 并没有成员数量的变化(官方注释是 Updating an existing entry.)
  29.     }
  30.     return TheBucket;
  31.   }
复制代码
哈希表的查找、插入和删除原理也请看此文：（数据结构）散列表条记
3. weak_table_t

weak_table_t在SideTable结构体中，储存对象弱引用指针的哈希表（这张全局引用表也只有8个或64个），weak功能实现的焦点数据结构：
  1. struct weak_table_t {
  2.     weak_entry_t *weak_entries;
  3.     size_t    num_entries;
  4.     uintptr_t mask;
  5.     uintptr_t max_hash_displacement;
  6. };
复制代码
其中第一个成员weak_entries存放着若干个数据，即对象的弱引用，其余的成员都是用来做哈希定位的
上述第一个成员变量声明范例带*号，是用一个数组存储多个对象的弱引用
weak_entry_t
  1. struct weak_entry_t {
  2.     DisguisedPtr<objc_object> referent; //对象地址
  3.     union {  //这里又是一个联合体, 苹果设计的数据结构的确很棒
  4.         struct {
  5.             // 因为这里要存储的又是一个 weak 指针数组, 所以苹果继续选择采用哈希算法
  6.             weak_referrer_t *referrers; //指向 referent 对象的 weak 指针数组
  7.             uintptr_t        out_of_line_ness : 2; //这里标记是否超过内联边界, 下面会提到
  8.             uintptr_t        num_refs : PTR_MINUS_2; //数组中已占用的大小
  9.             uintptr_t        mask; //数组下标最大值(数组大小 - 1)
  10.             uintptr_t        max_hash_displacement; //最大哈希偏移值
  11.         };
  12.         struct {
  13.             //这是一个取名叫内联引用的数组
  14.             weak_referrer_t  inline_referrers[WEAK_INLINE_COUNT]; //宏定义的值是 4
  15.         };
  16.     };
  18.     // 返回 true 表示使用 referrers 哈希数组 false 表示使用 inline_referrers 数组保存 weak_referrer_t
  19.     bool out_of_line() {
  20.         return (out_of_line_ness == REFERRERS_OUT_OF_LINE);
  21.     }
  23.         // weak_entry_t 的赋值操作，直接使用 memcpy 函数拷贝 other 内存里面的内容到 this 中，
  24.     // 而不是用复制构造函数什么的形式实现，应该也是为了提高效率考虑的...
  25.     weak_entry_t& operator=(const weak_entry_t& other) {
  26.         memcpy(this, &other, sizeof(other));
  27.         return *this;
  28.     }
  30.     // weak_entry_t 的构造函数
  31.    
  32.     // newReferent 是原始对象的指针，
  33.     // newReferrer 则是指向 newReferent 的弱引用变量的指针。
  34.    
  35.     // 初始化列表 referent(newReferent) 会调用: DisguisedPtr(T* ptr) : value(disguise(ptr)) { } 构造函数，
  36.     // 调用 disguise 函数把 newReferent 转化为一个整数赋值给 value。
  37.     weak_entry_t(objc_object *newReferent, objc_object **newReferrer)
  38.         : referent(newReferent)
  39.     {
  40.         // 把 newReferrer 放在数组 0 位，也会调用 DisguisedPtr 构造函数，把 newReferrer 转化为整数保存
  41.         inline_referrers[0] = newReferrer;
  42.         // 循环把 inline_referrers 数组的剩余 3 位都置为 nil
  43.         for (int i = 1; i < WEAK_INLINE_COUNT; i++) {
  44.             inline_referrers[i] = nil;
  45.         }
  46.     }
  47. }
复制代码


  • referent：弱引用对象指针择要，其实可以明白为弱引用对象的指针，只不外这里使用了择要的情势存储（所谓择要，其实是把地址取负）
  • 看下面这个共用体：

    • referrers：指向referent对象的weak指针数组，分动态数组和固定长度数组两种环境
    • out_of_line_ness：标记是否超过了内联界限
    • 其余变量代码片中均有解释
    • inline_referrers：表现一个长度为4的数组，也用来存放weak指针
    • 在这段共用体中，第一个结构体中 out_of_line_ness 占用 2bit, num_refs 在 64 位环境下占用了 62bit, 所以实际上两个结构体都是32字节, 共用一段地址

  • bool out_of_line()：返回true，表明指向对象的weak指针超过了4个，就使用哈希数组referrers；返回false，表明指向对象的weak指针不超过4个，就使用inline_referrers数组存放weak_referrer_t范例weak指针，省去了哈希操作的步骤
总结

一张图明白SideTable的结构：


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？立即注册

x
回复

使用道具 举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

用户云卷云舒

金牌会员
这个人很懒什么都没写!

楼主热帖

标签云

挺好的 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表