【iOS】SideTable

目录

• • SideTables
  • StripedMap
  • SideTable
  • • 1. spinlock_t slock
    • 2. RefcountMap
    • 3. weak_table_t
  • 总结

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的结构：