阅读量:0
目录
objc4源码地址：
SideTable& table = SideTables()[this]; // 获取对象的SideTable size_t& refcntStorage = table.refcnts[this]; 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_SIMULATOR enum { StripeCount = 8 }; #else enum { StripeCount = 64 }; #endif struct 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) { // 桶数是0 FoundBucket = 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; //桶的使用量 +1 unsigned NumBuckets = getNumBuckets(); //桶的总数 if (NewNumEntries*4 >= NumBuckets*3) { //使用量超过 3/4 this->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(); //桶使用量 +1 decrementNumTombstones(); //墓碑数量 -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_t bool 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 位都置为 nil for (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指针，省去了哈希操作的步骤
总结
一张图理解SideTable的结构：
