RunTime中SideTables, SideTable, w

在runtime中，有四个数据结构非常重要，分别是SideTables，SideTable，weak_table_t和weak_entry_t。它们和对象的引用计数，以及weak引用相关。

关系

先说一下这四个数据结构的关系，在runtime内存空间中，Sidetables是一个64个元素长度的hash数组，里面存放了SideTable，SideTable的hash键值就是一个对象obj的address。
因此可以说，一个obj，对应了一个SideTable，但是一个SideTable对应了多个obj，因为SideTable的数量只有64个，所以会有很多obj共用同一个SideTable。

而在一个SideTable中，又有两个成员，分别是

RefcountMap refcnts;        // 对象引用计数相关 map
weak_table_t weak_table;    // 对象弱引用相关 table

其中，refcents是一个hash map，其key是obj的地址，而value，则是obj对象的引用计数。

而weak_table则存储了弱引用obj的指针的地址，其本质是一个以obj地址为key，弱引用obj的指针的地址作为value的hash表。hash表的节点类型是weak_entry_t。

20180920175152461 (1).png

SideTables

先来说一下最外层的SideTables。SideTables可以理解为一个全局的hash数组，里面存储了SideTable类型的数据，其长度为64。
SideTabls可以通过全局的静态函数获取：

static StripedMap<SideTable>& SideTables() {
    return *reinterpret_cast<StripedMap<SideTable>*>(SideTableBuf);
}

可以看到，SideTabls 实质类型为模板类型StripedMap 。StripedMap直译过来是“有条纹的Map”，不知道为什么叫做这个鸟名字

SideTable

SideTable 翻译过来的意思是“边桌”，可以放一下小东西。这里，主要存放了OC对象的引用计数和弱引用相关信息。定义如下:

struct SideTable {
    spinlock_t slock;           // 自旋锁，防止多线程访问冲突
    RefcountMap refcnts;        // 对象引用计数map
    weak_table_t weak_table;    // 对象弱引用map

    SideTable() {
        memset(&weak_table, 0, sizeof(weak_table));
    }

    ~SideTable() {
        _objc_fatal("Do not delete SideTable.");
    }

    // 锁操作 符合StripedMap对T的定义
    void lock() { slock.lock(); }
    void unlock() { slock.unlock(); }
    void forceReset() { slock.forceReset(); }

    // Address-ordered lock discipline for a pair of side tables.

    template<HaveOld, HaveNew>
    static void lockTwo(SideTable *lock1, SideTable *lock2);
    template<HaveOld, HaveNew>
    static void unlockTwo(SideTable *lock1, SideTable *lock2);
};

SideTable的定义很清晰，有三个成员:

spinlock_t slock : 自旋锁，用于上锁/解锁 SideTable。
RefcountMap refcnts ：以DisguisedPtr<objc_object>为key的hash表，用来存储OC对象的引用计数(仅在未开启isa优化 或 在isa优化情况下isa_t的引用计数溢出时才会用到)。
weak_table_t weak_table : 存储对象弱引用指针的hash表。是OC weak功能实现的核心数据结构。
除了三个成员外，苹果为SideTable还写了构造和析构函数：
···
// 构造函数
SideTable() {
memset(&weak_table, 0, sizeof(weak_table));
}

//析构函数(看看函数体，苹果设计的SideTable其实不希望被析构，不然会引起fatal 错误)
~SideTable() {
    _objc_fatal("Do not delete SideTable.");
}

···
通过析构函数可以知道，SideTable是不能被析构的。

最后是一堆锁的操作，用于多线程访问SideTable， 同时，也符合我们上面提到的StripedMap中关于value的lock接口定义：

// 锁操作 符合StripedMap对T的定义
    void lock() { slock.lock(); }
    void unlock() { slock.unlock(); }
    void forceReset() { slock.forceReset(); }

    // Address-ordered lock discipline for a pair of side tables.

    template<HaveOld, HaveNew>
    static void lockTwo(SideTable *lock1, SideTable *lock2);
    template<HaveOld, HaveNew>
    static void unlockTwo(SideTable *lock1, SideTable *lock2);

spinlock_t slock
spinlock_t的最终定义实际上是一个uint32_t类型的非公平的自旋锁。所谓非公平，就是说获得锁的顺序和申请锁的顺序无关，也就是说，第一个申请锁的线程有可能会是最后一个获得到该锁，或者是刚获得锁的线程会再次立刻获得到该锁，造成饥饿等待。 同时，在OC中，_os_unfair_lock_opaque也记录了获取它的线程信息，只有获得该锁的线程才能够解开这把锁

typedef struct os_unfair_lock_s {
    uint32_t _os_unfair_lock_opaque;
} os_unfair_lock, *os_unfair_lock_t;

关于自旋锁的实现，苹果并未公布，但是大体上应该是通过操作_os_unfair_lock_opaque 这个uint32_t的值，当大于0时，锁可用，当等于或小于0时，需要锁等待。

RefcountMap refcnts

RefcountMap refcnts 用来存储OC对象的引用计数。它实质上是一个以objc_object为key的hash表，其vaule就是OC对象的引用计数。同时，当OC对象的引用计数变为0时，会自动将相关的信息从hash表中剔除。RefcountMap的定义如下

// RefcountMap disguises its pointers because we 
// don't want the table to act as a root for `leaks`.
typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap;

实质上是模板类型objc::DenseMap。模板的三个类型参数DisguisedPtr<objc_object>，size_t, true 分别表示DenseMap的hash key类型，value类型，是否需要在value==0的时候自动释放掉响应的hash节点，这里是true。

而DenseMap这个模板类型又继承与另一个Base 模板类型DenseMapBase

template<typename KeyT, typename ValueT,
         bool ZeroValuesArePurgeable = false, 
         typename KeyInfoT = DenseMapInfo<KeyT> >
class DenseMap
    : public DenseMapBase<DenseMap<KeyT, ValueT, ZeroValuesArePurgeable, KeyInfoT>,
                          KeyT, ValueT, KeyInfoT, ZeroValuesArePurgeable> 

关于DenseMap的定义，苹果写了一大坨，有些复杂，这里就不去深究了，有兴趣的同学可以自己去看下相关的源码部分。

weak_table_t weak_table

重点来了，weak_table_t weak_table 用来存储OC对象弱引用的相关信息。我们知道，SideTables一共只有64个节点，而在我们的APP中，一般都会不只有64个对象，因此，多个对象一定会重用同一个SideTable节点，也就是说，一个weak_table会存储多个对象的弱引用信息。因此在一个SideTable中，又会通过weak_table作为hash表再次分散存储每一个对象的弱引用信息。

weak_table_t的定义如下：

/**
 * The global weak references table. Stores object ids as keys,
 * and weak_entry_t structs as their values.
 */
struct weak_table_t {
    weak_entry_t *weak_entries;        // hash数组，用来存储弱引用对象的相关信息weak_entry_t
    size_t    num_entries;             // hash数组中的元素个数
    uintptr_t mask;                    // hash数组长度-1，会参与hash计算。（注意，这里是hash数组的长度，而不是元素个数。比如，数组长度可能是64，而元素个数仅存了2个）
    uintptr_t max_hash_displacement;   // 可能会发生的hash冲突的最大次数，用于判断是否出现了逻辑错误（hash表中的冲突次数绝不会超过改值）
};

weak_table_t是一个典型的hash结构。其中 weak_entry_t *weak_entries是一个动态数组，用来存储weak_table_t的数据元素weak_entry_t。
剩下的三个元素将会用于hash表的相关操作。weak_table的hash定位操作如下所示：

static weak_entry_t *
weak_entry_for_referent(weak_table_t *weak_table, objc_object *referent)
{
    assert(referent);

    weak_entry_t *weak_entries = weak_table->weak_entries;

    if (!weak_entries) return nil;

    size_t begin = hash_pointer(referent) & weak_table->mask;  // 这里通过 & weak_table->mask的位操作，来确保index不会越界
    size_t index = begin;
    size_t hash_displacement = 0;
    while (weak_table->weak_entries[index].referent != referent) {
        index = (index+1) & weak_table->mask;
        if (index == begin) bad_weak_table(weak_table->weak_entries); // 触发bad weak table crash
        hash_displacement++;
        if (hash_displacement > weak_table->max_hash_displacement) { // 当hash冲突超过了可能的max hash 冲突时，说明元素没有在hash表中，返回nil 
            return nil;
        }
    }
    
    return &weak_table->weak_entries[index];
}