SideTables分析

SideTables与iOS内存管理息息相关，今天就来研究一下SideTables，先看一下SideTables的定义

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

SideTablesde的实质类型是存储SideTable的StripedMap。在StripedMap类中有StripeCount定义存储sidetable的最大数量，所以每个SideTablesdes可以对应多个对象，而每个对象对应一个sidetable。

SideTable中包含三个成员，自旋锁，引用计数表，弱引用表。

- spinlock_t slock;
- RefcountMap refcnts;
- weak_table_t weak_table;

这里的slock是一个自旋锁，就是为了保证多线程访问安全性

refcnts本质是一个存储对象引用计数的hash表，key为对象，value为引用计数（优化过得isa中，引用计数主要存储在isa中）

weak_table是存储对象弱引用的一个结构体，该结构体内成员如下

- weak_entry_t *weak_entries;
- size_t    num_entries;
- uintptr_t mask;
- uintptr_t max_hash_displacement;

简单介绍完SideTables相关数据结构关系，下面来逐个分析分析一下

StripedMap

StripedMap是定义在objc-private.h中的一个类，具体代码太长，不再这里贴了，只介绍里面重要的内容

1、StripeCount定义了里面存储对象最大数量。

enum { StripeCount = 8 };

2、定义结构体PaddedT包装传入泛型(这里指的是SideTable)，这里使alignas(CacheLineSize)方法使字节对齐。猜测字节对齐的目的是提高存取hash值时的效率。

struct PaddedT {
    T value alignas(CacheLineSize);
};

3、实现了index计算的hash算法indexForPointer

static unsigned int indexForPointer(const void *p) {
    uintptr_t addr = reinterpret_cast<uintptr_t>(p);
    return ((addr >> 4) ^ (addr >> 9)) % StripeCount;
}

4、获取sidetable的操作getLock方法

const void *getLock(int i) {
    if (i < StripeCount) return &array[i].value;
    else return nil;
}

5、其他锁操作array[i].value.lock，或者array[i].value.unlock(),调用的是sidetable中的锁

void lockAll() {
    for (unsigned int i = 0; i < StripeCount; i++) {
        array[i].value.lock();
    }
}

6、构造方法StripedMap(),具体实现没有开元，只能看出DEBUG模式下有部分操作

#if DEBUG
StripedMap() {
    // Verify alignment expectations.
    uintptr_t base = (uintptr_t)&array[0].value;
    uintptr_t delta = (uintptr_t)&array[1].value - base;
    assert(delta % CacheLineSize == 0);
    assert(base % CacheLineSize == 0);
}
#else
constexpr StripedMap() {}
#endif

引用计数refcnts 存储结构RefcountMap

RefcountMap定义如下，他的类型是objc::DenseMap。

typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap;

三个参数分别代表对象的hash key，引用计数，是否需要在引用计数为0的时候自动释放相应的hash节点。这里默认传true。所以对象的引用计数refcnts不一定存在。在优化过得isa中由extra_rc来存储引用计数，只有其存储计数上溢出的时候才会存入sidetable中的refcnts。

弱引用表 weak_table_t weak_table

上面有说过一个sidetable中存储多个对象的信息，弱引用表weak_table_t又是一个结构体，所以在weak_table_t里面也存储着多个对象信息。其中weak_entries是一个hash数组，存储弱引用对象的相关信息weak_entry_t。num_entries表示weak_entries数组中元素个数。另外两个参数mask和 max_hash_displacement 都是uintptr_t(无符号long)类型的，mask一般是做位运算定义的值。max_hash_displacement则表示hash冲突的最大次数

下面的代码是weak_table中通过对象获取weak_entry_t的方法。在这个方法中可以看出mask餐椅了hash值的计算，hash冲突次数超过max_hash_displacement之后，就直接返回nil。

使用hash_pointer(referent) 和 weak_table->mask进行与运算。通过&运算保证index不会越界，所以可以推测出mask的值为hash数组长度-1。

这里hash冲突的解决方案是计算出hash位置index，判断index中存储referent是否与目标referent相等，不相等的话后移一位继续判断，并将hash_displacement++，记录移动次数。当hash_displacement的值大于max_hash_displacement时，直接返回nil。当index == begin时，即遍历一圈也没找到目标对象，直接调用bad_weak_table报错。

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;
    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);
        hash_displacement++;
        if (hash_displacement > weak_table->max_hash_displacement) {
            return nil;
        }
    }
    
    return &weak_table->weak_entries[index];
}

weak_entry_t

weak_entry_t存储着某个对象的弱引用信息，又是一个结构体。跟weak_table_t类似，里面存储一个hash表weak_referrer_t，弱引用该"对象的指针"的指针。通过weak_referrer_t的操作，可以使该对象的弱引用指针在对象释放后，置为nil。

weak_entry_t的定义如下：

struct weak_entry_t {
    DisguisedPtr<objc_object> referent;
    union {
        struct {
            weak_referrer_t *referrers;
            uintptr_t        out_of_line_ness : 2;
            uintptr_t        num_refs : PTR_MINUS_2;
            uintptr_t        mask;
            uintptr_t        max_hash_displacement;
        };
        struct {
            // out_of_line_ness field is low bits of inline_referrers[1]
            weak_referrer_t  inline_referrers[WEAK_INLINE_COUNT];
        };
    };

    bool out_of_line() {
        return (out_of_line_ness == REFERRERS_OUT_OF_LINE);
    }

    weak_entry_t& operator=(const weak_entry_t& other) {
        memcpy(this, &other, sizeof(other));
        return *this;
    }

    weak_entry_t(objc_object *newReferent, objc_object **newReferrer)
        : referent(newReferent)
    {
        inline_referrers[0] = newReferrer;
        for (int i = 1; i < WEAK_INLINE_COUNT; i++) {
            inline_referrers[i] = nil;
        }
    }
};

DisguisedPtr<objc_object> referent ：弱引用对象指针摘要。其实可以理解为弱引用对象的指针，只不过这里使用了摘要的形式存储。（所谓摘要，其实是把地址取负）。

weak_referrer_t：这是一个共用体，分动态数组和固定长度数组两种情况，

out_of_line：bool类型区分是weak_referrer_t中数组类型

weak_entry_t& operator=(const weak_entry_t& other)：赋值

weak_entry_t(objc_object *newReferent, objc_object **newReferrer) 构造

指针数组weak_referrer_t

typedef DisguisedPtr<objc_object *> weak_referrer_t;

weak_referrer_t以指针摘要的形式，存储 弱引用指针 的指针。weak_referrer_t数组这里设置了两种模式，毕竟动态数组涉及到更多的操作，在小数据量的情况下，使用定长数组效率更高。

总结

全局维护一个sidetables，

sidetables里面包含多个sidetabl，可以通过对象的hash查找到对象存在的sidetable。

一个sidetable对应多个对象。里面有一个引用计数表，一个弱引用表

再次对对象hash计算值可以从sidetable中RefcountMap中获取对象引用计数

从weak_table_t中保存着的一个sidetable中所有weak_entries表

从weak_entries中通过对象查找着某个对象对应的弱引用信息weak_entry_t

weak_entry_t中保存着弱引用该对象的 指针地址的hash数组

弱引用表使用举例

其他还好理解，弱引用比较绕。这里举个实例

NSObject *obj = [[NSObject alloc] init];
__weak id  weakObj = obj;

在这段代码里，用weakObj指向obj时

1、会通过obj从sidetables中找到sidetable
2、找到sidetable中的弱引用表weak_table_t
3、通过obj从weak_table_t中的weak_entries找到obj对应的weak_entry_t
4、在obj对应的weak_entry_t的weak_referrer_t中加入weakObj指针

当obj释放时，会判断obj的weakly_referenced是否为1，即obj是否被弱引用。如果被弱引用，则进行下面的操作

1、会通过obj从sidetables中找到sidetable
2、找到sidetable中的弱引用表weak_table_t
3、通过obj从weak_table_t中的weak_entries找到obj对应的weak_entry_t
4、查找weak_entry_t中的weak_referrer_t数组，并将weak_referrer_t中存储的指针（这里指weakObj）指向nil