【iOS】SideTable

SideTables

查源码SideTables的结构如下：

// SideTables在C++的initializers函数之前被调用，所以不能使用C++初始化函数来初始化SideTables
// 不能使用全局指针来指向这个结构体，因为涉及到重定向问题；
template <typename Type>
class ExplicitInit {alignas(Type) uint8_t _storage[sizeof(Type)];public:template <typename... Ts>void init(Ts &&... Args) {new (_storage) Type(std::forward<Ts>(Args)...);}Type &get() {return *reinterpret_cast<Type *>(_storage);}
};static objc::ExplicitInit<StripedMap<SideTable>> SideTablesMap;
static StripedMap<SideTable>& SideTables() {return SideTablesMap.get();
}

简化后：

alignas(StripedMap<SideTable>) static uint8_t _storage[sizeof(StripedMap<SideTable>)];
static StripedMap<SideTable>& SideTables() {return *reinterpret_cast<StripedMap<SideTable> *>(_storage);
}

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

StripedMap

StripedMap结构：

enum { CacheLineSize = 64 };template<typename T>
class StripedMap {
#if TARGET_OS_IPHONE && !TARGET_OS_SIMULATORenum { StripeCount = 8 };
#elseenum { StripeCount = 64 };
#endifstruct PaddedT {T value alignas(CacheLineSize);};//在整个项目中，如果只初始化一个SideTable和所有对象的weak_table_t表，这样的效率会很低，因为有spinlock_t加锁、解锁而造成低效的问题。但是如果每个对象都创建SideTable和weak_table_t表，效率是高了但是内存占用过高// 来看看Apple是如何解决这个问题的PaddedT array[StripeCount];static unsigned int indexForPointer(const void *p) {// 核心算法，均匀分配到真机8张表中uintptr_t addr = reinterpret_cast<uintptr_t>(p);return ((addr >> 4) ^ (addr >> 9)) % StripeCount;}public:T& operator[] (const void *p) { return array[indexForPointer(p)].value;}const T& operator[] (const void *p) const { return const_cast<StripedMap<T>>(this)[p]; }
// ...省略了对象方法...
};

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的类的属性中

// RefcountMap 伪装了它的指针，因为我们不希望表成为“泄漏”的根源
typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,RefcountMapValuePurgeable> RefcountMap;// 模版参数
enum HaveOld { DontHaveOld = false, DoHaveOld = true };
enum HaveNew { DontHaveNew = false, DoHaveNew = true };struct SideTable {// 保证原子操作的自旋锁spinlock_t slock;// 存储引用计数的 hash 表RefcountMap refcnts;// weak 引用全局 hash 表weak_table_t weak_table;SideTable() {memset(&weak_table, 0, sizeof(weak_table));}~SideTable() {_objc_fatal("Do not delete SideTable.");}void lock() { slock.lock(); }void unlock() { slock.unlock(); }void reset() { slock.reset(); }// 针对一对sidetables的地址有序锁定规则template<HaveOld, HaveNew>static void lockTwo(SideTable *lock1, SideTable *lock2);template<HaveOld, HaveNew>static void unlockTwo(SideTable *lock1, SideTable *lock2);
};

1. spinlock_t slock

spinlock_t底层是os_unfair_lock自旋锁，操作引用计数时对SideTable加锁，防止数据错乱

os_unfair_lock又是一个非公平锁，获取锁的顺序和申请的顺序无关，即可能 A 线程第一个申请锁，却在 B、C 获得锁之后 A 才获得锁

有关锁看此文：【iOS】线程同步&读写安全技术（锁、信号量、同步串行队列）

2. RefcountMap

RefcountMap就是DenseMap，一个模版类：

typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap;template <typename KeyT, typename ValueT,typename ValueInfoT = DenseMapValueInfo<ValueT>,typename KeyInfoT = DenseMapInfo<KeyT>,typename BucketT = detail::DenseMapPair<KeyT, ValueT>>
class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT>,
KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT> {// ...BucketT *Buckets;unsigned NumEntries;unsigned NumTombstones;unsigned NumBuckets;
public:// ...
};

Buckets为一个数组，数组类型为BucketT，这里把一个数组元素称为一个桶或槽
```
typedef std::pair<KeyT, ValueT> BucketT;
```
所以Buckets就是一个哈希桶，存储形式就是对象地址 : 引用计数
NumEntries：记录数组中非空桶的数量
NumTombstones：记录数组中墓碑桶的数量，墓碑桶就是存在过元素但已经被删除了的桶，其作用详见此文：（数据结构）散列表笔记
NumBuckets：桶的数量，即数组长度

桶数组开辟空间，决定数组大小：

inline uint64_t NextPowerOf2(uint64_t A) {A |= (A >> 1);A |= (A >> 2);A |= (A >> 4);A |= (A >> 8);A |= (A >> 16);A |= (A >> 32);return A + 1;
}

这个算法可以做到把最高位的 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：

bool LookupBucketFor(const LookupKeyT &Val,const BucketT *&FoundBucket) const {// ...if (NumBuckets == 0) { // 桶数是0FoundBucket = 0;return false; // 返回 false 回上层调用添加函数}// ...unsigned BucketNo = getHashValue(Val) & (NumBuckets-1); //将哈希值与数组最大下标按位与unsigned ProbeAmt = 1; // 哈希值重复的对象需要靠它来重新寻找位置while (1) {const BucketT *ThisBucket = BucketsPtr + BucketNo; // 头指针 + 下标, 类似于数组取值// 找到的桶中的 key 和对象地址相等, 则是找到if (KeyInfoT::isEqual(Val, ThisBucket->first)) {FoundBucket = ThisBucket;return true;}// 找到的桶中的 key 是空桶占位符, 则表示可插入if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { if (FoundTombstone) ThisBucket = FoundTombstone; // 如果曾遇到墓碑, 则使用墓碑的位置FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;return false; // 找到空占位符, 则表明表中没有已经插入了该对象的桶}// 如果找到了墓碑if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone)FoundTombstone = ThisBucket;  // 记录下墓碑// 这里涉及到最初定义 typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap, 传入的第三个参数 true// 这个参数代表是否可以清除 0 值, 也就是说这个参数为 true 并且没有墓碑的时候, 会记录下找到的 value 为 0 的桶if (ZeroValuesArePurgeable  && ThisBucket->second == 0  &&  !FoundTombstone) FoundTombstone = ThisBucket;// 用于计数的 ProbeAmt 如果大于了数组容量, 就会抛出异常if (ProbeAmt > NumBuckets) {_objc_fatal("...");}BucketNo += ProbeAmt++; // 本次哈希计算得出的下表不符合, 则利用 ProbeAmt 寻找下一个下标BucketNo&= (NumBuckets-1); // 得到新的数字和数组下标最大值按位与}
}

插入算法会先查看可用量, 如果哈希表的可用量(墓碑桶+空桶的数量)小于 1/4, 则需要为表重新开辟更大的空间, 如果表中的空桶位置少于 1/8 (说明墓碑桶过多), 则需要清理表中的墓碑. 以上两种情况下哈希查找算法会很难查找正确位置, 甚至可能会产生死循环, 所以要先处理表, 处理表之后还会重新分配所有桶的位置, 之后重新查找当前对象的可用位置并插入. 如果没有发生以上两种情况, 就直接把新的对象的引用计数放入调用者提供的桶里：

BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) {unsigned NewNumEntries = getNumEntries() + 1; //桶的使用量 +1unsigned NumBuckets = getNumBuckets(); //桶的总数if (NewNumEntries*4 >= NumBuckets*3) { //使用量超过 3/4this->grow(NumBuckets * 2); //数组大小 * 2做参数, grow 中会决定具体数值//grow 中会重新布置所有桶的位置, 所以将要插入的对象也要重新确定位置LookupBucketFor(Key, TheBucket);NumBuckets = getNumBuckets(); //获取最新的数组大小}//如果空桶数量少于 1/8, 哈希查找会很难定位到空桶的位置if (NumBuckets-(NewNumEntries+getNumTombstones()) <= NumBuckets/8) {//grow 以原大小重新开辟空间, 重新安排桶的位置并能清除墓碑this->grow(NumBuckets);LookupBucketFor(Key, TheBucket); //重新布局后将要插入的对象也要重新确定位置}assert(TheBucket);//找到的 BucketT 标记了 EmptyKey, 可以直接使用if (KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) {incrementNumEntries(); //桶使用量 +1}else if (KeyInfoT::isEqual(TheBucket->first, getTombstoneKey())) { //如果找到的是墓碑incrementNumEntries(); //桶使用量 +1decrementNumTombstones(); //墓碑数量 -1}else if (ZeroValuesArePurgeable  &&  TheBucket->second == 0) { //找到的位置是 value 为 0 的位置TheBucket->second.~ValueT(); //测试中这句代码被直接跳过并没有执行, value 还是 0} else {// 其它情况, 并没有成员数量的变化(官方注释是 Updating an existing entry.)}return TheBucket;}

哈希表的查找、插入和删除原理也请看此文：（数据结构）散列表笔记

3. weak_table_t

weak_table_t在SideTable结构体中，储存对象弱引用指针的哈希表（这张全局引用表也只有8个或64个），weak功能实现的核心数据结构：

struct weak_table_t {weak_entry_t *weak_entries;size_t    num_entries;uintptr_t mask;uintptr_t max_hash_displacement;
};

其中第一个成员weak_entries存放着若干个数据，即对象的弱引用，其余的成员都是用来做哈希定位的

上述第一个成员变量声明类型带*号，是用一个数组存储多个对象的弱引用

weak_entry_t

struct weak_entry_t {DisguisedPtr<objc_object> referent; //对象地址union {  //这里又是一个联合体, 苹果设计的数据结构的确很棒struct {// 因为这里要存储的又是一个 weak 指针数组, 所以苹果继续选择采用哈希算法weak_referrer_t *referrers; //指向 referent 对象的 weak 指针数组uintptr_t        out_of_line_ness : 2; //这里标记是否超过内联边界, 下面会提到uintptr_t        num_refs : PTR_MINUS_2; //数组中已占用的大小uintptr_t        mask; //数组下标最大值(数组大小 - 1)uintptr_t        max_hash_displacement; //最大哈希偏移值};struct {//这是一个取名叫内联引用的数组weak_referrer_t  inline_referrers[WEAK_INLINE_COUNT]; //宏定义的值是 4};};// 返回 true 表示使用 referrers 哈希数组 false 表示使用 inline_referrers 数组保存 weak_referrer_tbool out_of_line() {return (out_of_line_ness == REFERRERS_OUT_OF_LINE);}// weak_entry_t 的赋值操作，直接使用 memcpy 函数拷贝 other 内存里面的内容到 this 中，// 而不是用复制构造函数什么的形式实现，应该也是为了提高效率考虑的...weak_entry_t& operator=(const weak_entry_t& other) {memcpy(this, &other, sizeof(other));return *this;}// weak_entry_t 的构造函数// newReferent 是原始对象的指针，// newReferrer 则是指向 newReferent 的弱引用变量的指针。// 初始化列表 referent(newReferent) 会调用: DisguisedPtr(T* ptr) : value(disguise(ptr)) { } 构造函数，// 调用 disguise 函数把 newReferent 转化为一个整数赋值给 value。weak_entry_t(objc_object *newReferent, objc_object **newReferrer): referent(newReferent){// 把 newReferrer 放在数组 0 位，也会调用 DisguisedPtr 构造函数，把 newReferrer 转化为整数保存inline_referrers[0] = newReferrer;// 循环把 inline_referrers 数组的剩余 3 位都置为 nilfor (int i = 1; i < WEAK_INLINE_COUNT; i++) {inline_referrers[i] = nil;}}
}

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指针，省去了哈希操作的步骤