LeeWong
首页 标签 归档 关于我

SideTable结构

2020-08-16 Runtime

iOS开发者都知道，当一个对象被释放时，所有对这个对象弱引用的指针都会释放并置为nil，那么系统是如何存储这些弱引用对象的呢？又是如何在一个对象释放时，将这些指向即将释放对象的弱引用的指针置为nil的呢？下面我们通过分析SideTable的结构来进一步了解内存管理的弱引用存储细节。

结构

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

SideTables

下面我们看下SideTables的结构：

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

reinterpret_cast，是C++里的强制类型转换符,我们看下SideTableBuf的定义。上面代码，我们看到StripedMap实际上返回的是一个SideTableBuf对象，那么我们来看下SideTableBuf对象：

1
2
3
4
5
6
7
//alignas 字节对齐
// SideTableBuf 静态全局变量
// sizeof(StripedMap<SideTable>) = 4096
//alignas (StripedMap<SideTable>) 是字节对齐的意思，表示让数组中每一个元素的起始位置对齐到4096的倍数
// 因此下面这句话可以翻译为 static uint8_t SideTableBuf[4096]
alignas(StripedMap<SideTable>) static uint8_t 
    SideTableBuf[sizeof(StripedMap<SideTable>)];

SideTableBuf是一个外部不可见的静态内存区块，存储StripedMap<SideTable>对象。它是内存管理的基础。

我们接下来在看下StripedMap的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
enum { CacheLineSize = 64 };
// StripedMap<T> 是一个模板类，根据传递的实际参数决定其中 array 成员存储的元素类型
// 能通过对象的地址，运算出 Hash 值，通过该 hash 值找到对应的 value
template<typename T>
class StripedMap {
#if TARGET_OS_IPHONE && !TARGET_OS_SIMULATOR
    enum { StripeCount = 8 };
#else
    enum { StripeCount = 64 };
#endif
    // PaddedT 为一个结构体
    struct PaddedT {
        T value alignas(CacheLineSize);
    };

    // array 中存放着8个sidetable
    PaddedT array[StripeCount];
    //取得p的哈希值，p就是实例对象的地址
    static unsigned int indexForPointer(const void *p) {
        uintptr_t addr = reinterpret_cast<uintptr_t>(p);
        // 这里根据对象的地址经过左移和异或操作 最终结果 模 8 得到一个0-7的值
        // 即对应该地址对应array中下标的sidetable中
        return ((addr >> 4) ^ (addr >> 9)) % StripeCount;
    }

 public:
    // 重写了[]方法 即通过下标获取数组中对应下标的值
    // array[index] = array[indexForPointer(p)].value
    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 是一个以void *为hash key， T为vaule的hash 表。StripedMap的所有T类型数据都被封装到array中。

综上我们得出SideTables的机构实际是下图所示:

SideTable

下面来看下sideTable的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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.");
    }
};

上面是我们简化后的SideTable结构体，包含了:

  • 保证原子属性的自旋锁spinlock_t
  • 记录引用计数值的RefcountMap
  • 用于存储对象弱引用的哈希表 weak_table_t

自旋锁(slock)我们这里就不做过多介绍了,我们先来看下RefcountMap，看下RefcountMap结构

1
2
3
4
5
// RefcountMap 是一个模板类
// key,DisguisedPtr<objc_object>类型
// value，size_t类型
// 是否清除为vlaue==0的数据，true
typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap;

DenseMap是llvm库中的类，是一个简单的二次探测哈希表，擅长支持小的键和值。RefcountMap是一个hash map，其key是obj的DisguisedPtr<objc_object>，而value，则是obj对象的引用计数,同时，这个map还有个加强版功能，当引用计数为0时，会自动将对象数据清除。

上面我们知道了，refcnts是用来存放引用计数的，那么我们如何获取一个对象的引用计数呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 获取一个对象的retainCount
inline uintptr_t 
objc_object::rootRetainCount()
{
	//优化指针 直接返回
    if (isTaggedPointer()) return (uintptr_t)this;
    //没优化则 到SideTable 读取
    sidetable_lock();
	//isa指针
    isa_t bits = LoadExclusive(&isa.bits);
    ClearExclusive(&isa.bits);//啥都没做
    if (bits.nonpointer) {//优化过 isa 指针
        uintptr_t rc = 1 + bits.extra_rc;//计数数量
        if (bits.has_sidetable_rc) {
        //bits.has_sidetable_rc标志位为1 表明有存放在sidetable中的引用计数
			//读取table的值 相加
            rc += sidetable_getExtraRC_nolock();
        }
		//解锁
        sidetable_unlock();
        return rc;
    }

    sidetable_unlock();
	//：如果没采用优化的isa指针，则直接返回sidetable中的值
    return sidetable_retainCount();
}

从上面的代码我们可以得出:retainCount = isa.extra_rc + sidetable_getExtraRC_nolock,即引用计数=isa指针中存储的引用计数+sidetable中存储的引用计数

那么sidetable_getExtraRC_nolock是如何从sideTable中获取retainCount的呢？
下面我们来看下这个方法的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
size_t 
objc_object::sidetable_getExtraRC_nolock()
{
	//
    assert(isa.nonpointer);
	//key是 this，存储了每个对象的table
    SideTable& table = SideTables()[this];
	//找到 it 否则返回0
    RefcountMap::iterator it = table.refcnts.find(this);
    // 这里返回的it是RefcountMap类型 it == table.refcnts.end() 
    // 表示在sidetable中没有找到this对应的引用计数则直接返回0
    if (it == table.refcnts.end()) return 0;
    // RefcountMap 结构的second值为引用计数值 
    // DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap;
    else return it->second >> SIDE_TABLE_RC_SHIFT;
}

了解了SideTable的RefcountMap，下面我们接着看另外一个属性weak_table

weak_table

我们都知道weak_table是对象弱引用map，它记录了所有弱引用对象的集合。

我们先来看下weak_table_t的定义：

1
2
3
4
5
6
7
8
9
10
11
12
// 全局的弱引用表
struct weak_table_t {
    // hash数组，用来存储弱引用对象的相关信息weak_entry_t
    weak_entry_t *weak_entries;
    // hash数组中的元素个数
    size_t    num_entries;
    // hash数组长度-1，会参与hash计算。
    //（注意，这里是hash数组的长度，而不是元素个数。比如，数组长度可能是64，而元素个数仅存了2个）
    uintptr_t mask;
    // 最大哈希偏移值
    uintptr_t max_hash_displacement;
};

weak_entries实质上是一个hash数组，数组中存储weak_entry_t类型的元素。weak_entry_t的定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * The internal structure stored in the weak references table. 
 * It maintains and stores
 * a hash set of weak references pointing to an object.
 * If out_of_line_ness != REFERRERS_OUT_OF_LINE then the set
 * is instead a small inline array.
 */
 //inline_referrers数组中可以存放元素的最大个数 如果超过了这个个数就会使用referrers 存放
#define WEAK_INLINE_COUNT 4
// out_of_line_ness field overlaps with the low two bits of inline_referrers[1].
// inline_referrers[1] is a DisguisedPtr of a pointer-aligned address.
// The low two bits of a pointer-aligned DisguisedPtr will always be 0b00
// (disguised nil or 0x80..00) or 0b11 (any other address).
// Therefore out_of_line_ness == 0b10 is used to mark the out-of-line state.
// DisguisedPtr方法返回的hash值得最低2个字节应该是0b00或0b11，因此可以用out_of_line_ness 
// == 0b10来表明当前是否在使用数组或动态数组来保存引用该对象的列表。
#define REFERRERS_OUT_OF_LINE 2
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;
            // 用于hash确定动态数组index，值实际上是动态数组空间长度-1（它和num_refs不一样，
            // 这里是记录的是数组中位置的个数，而不是数组中实际存储的元素个数）。
            uintptr_t        mask;
            // 最大哈希偏移值
            uintptr_t        max_hash_displacement;
        };
        struct {
            // inline_referrers 数组 当不使用动态数组时使用 最大个数为4
            weak_referrer_t  inline_referrers[WEAK_INLINE_COUNT];
        };
    };
}

从上面的介绍我们可以总结SideTables和SideTable以及weak_table_t在层级上的关系图如下：

上图是从数据结构的角度来看弱引用的保存,下面我们来看下从垂直方向来看

从上面的总结中我们可以看到，弱引用的存储实际上一个三级的哈希表，通过一层层的索引找到或者存储对应的弱引用。那当向weak_table_t中插入或查找某个元素时是如何操作的呢？算法是什么样的呢？

weak_entry_for_referent

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/ 在weak_table中查找所有弱引用referent的对象
static weak_entry_t *
weak_entry_for_referent(weak_table_t *weak_table, objc_object *referent)
{
    assert(referent);
    //获取这个weak_table_t中所有的弱引用对象
    weak_entry_t *weak_entries = weak_table->weak_entries;

    if (!weak_entries) return nil;
    //hash_pointer 哈希函数 传入的是 objc_object *key
    // weak_table->mask = weaktable的容量-1
    size_t begin = hash_pointer(referent) & weak_table->mask;
    size_t index = begin;
    // 哈希冲突次数
    size_t hash_displacement = 0;
    // 判断根据index获取到的弱引用对象数组中对应的weak_entry_t的弱引用对象是否为
    // 外部传入的对象
    while (weak_table->weak_entries[index].referent != referent) {
        // 开放地址法解决哈希冲突
        // & weak_table->mask 是为了在下一个地址仍然没有找到外部传入对象时回到第一个对比的位置
        index = (index+1) & weak_table->mask;
        if (index == begin)
            // 对比了所有数据 仍没有找到 直接报错
            bad_weak_table(weak_table->weak_entries);
        // 哈希冲突次数++
        hash_displacement++;
        // 最大哈希偏移值 表示已经遍历了数组中所有的元素
        // 没有找到那么直接返回nil
        if (hash_displacement > weak_table->max_hash_displacement) {
            return nil;
        }
    }
    // 直接返回被弱引用的对象
    return &weak_table->weak_entries[index];
}

上面就是根据对象地址获取所有弱引用该对象的的数组，基本逻辑都比较清晰，我们在遍历weak_table->weak_entries中的时候发现判断是否遍历完一遍的时候使用的方法

1
index = (index+1) & weak_table->mask;

假设当前数组长度8，下标分别是0-7，上面weak_table->mask= 7 = 0111。

下标 计算后结果
index = 0 index & mask = 0000 & 0111 = 0000 = 0
index = 1 index & mask = 0001 & 0111 = 0001 = 1
index = 2 index & mask = 0010 & 0111 = 0010 = 2
index = 3 index & mask = 0011 & 0111 = 0011 = 3
index = 4 index & mask = 0100 & 0111 = 0100 = 4
index = 5 index & mask = 0101 & 0111 = 0101 = 5
index = 6 index & mask = 0110 & 0111 = 0110 = 6
index = 7 index & mask = 0111 & 0111 = 0111 = 7
index = 8 index & mask = 1000 & 0111 = 0000 = 0

看完上面的计算相信大家都明白了这么做的真是意图了：

1
if (index == begin)

可以理解为：数组遍历完成，已经和数组中所有的元素做了对比。

随着某个对象被越来越多的对象弱引用，那么这个存放弱引用该对象的所有对象的数组也会越来越大。

hash表自动扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//weak_table_t扩容
// 参数 weak_table 要扩容的table new_size 目标大小
static void weak_resize(weak_table_t *weak_table, size_t new_size)
{
    //weak_table的容量
    size_t old_size = TABLE_SIZE(weak_table);

    // 取出weak_table中存放的所有实体
    weak_entry_t *old_entries = weak_table->weak_entries;
    // 新创建一个weak_entry_t类型的数组
    // 数组的大小是new_size * sizeof(weak_entry_t)
    weak_entry_t *new_entries = (weak_entry_t *)
        calloc(new_size, sizeof(weak_entry_t));

    // 重置weak_table的mask的值
    weak_table->mask = new_size - 1;
    // 将weak_table->weak_entries指向新创建的内存区域 注意 此时weak_table中没有任何数据
    weak_table->weak_entries = new_entries;
    // 最大哈希偏移值重置为0
    weak_table->max_hash_displacement = 0;
    //weak_table 中存储实体个数为0
    weak_table->num_entries = 0;  // restored by weak_entry_insert below

    // 旧数据的搬迁
    if (old_entries) {
        weak_entry_t *entry;
        //old_entries看做数组中第一个元素的地址 由于数组是连续的存储空间 那么old_entries + old_size = 数组最后一个元素的地址
        weak_entry_t *end = old_entries + old_size;
        // 遍历这些旧数据
        for (entry = old_entries; entry < end; entry++) {
            //weak_entry_t的referent(referent是指被弱引用的对象)
            if (entry->referent) {
                // 将旧数据搬移到新的结构中
                weak_entry_insert(weak_table, entry);
            }
        }
        // 释放所有的旧数据
        free(old_entries);
    }
}

从上面的代码中我们可以看到，哈希表的扩容主要分为下面几个步骤:

  • 创建一个局部变量保存当前哈希表中保存的所有弱引用实体
  • 新建一个容量是旧哈希表大小2倍的哈希表，同时重置num_entries、max_hash_displacement、weak_entries、mask
  • 遍历之前保存的旧的数据 将数据按照顺序依次重新插入的新建的哈希表中
  • 释放旧数据

我们看到将旧数据插入新数据的主要方法是weak_entry_insert，下面我们来仔细介绍下它：

weak_entry_insert

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 向指定的weak_table_t中插入某个对象
// weak_table_t 目标 table
// new_entry 被弱引用的对象
static void weak_entry_insert(weak_table_t *weak_table, weak_entry_t *new_entry)
{
    // 取出weak_table中所有弱引用的对象
    weak_entry_t *weak_entries = weak_table->weak_entries;
    assert(weak_entries != nil);

    // 根据new_entry中被弱引用对象地址通过哈希算法 算出 弱引用new_entry->referent的对象存放的index
    size_t begin = hash_pointer(new_entry->referent) & (weak_table->mask);
    size_t index = begin;
    size_t hash_displacement = 0;
    // weak_entries[index].referent 如果不为空 表示已经有
    while (weak_entries[index].referent != nil) {
        // 计算下一个要遍历的index
        index = (index+1) & weak_table->mask;
        // 遍历了所有元素发现weak_entries[index].referent 都不为nil
        if (index == begin)
            // 直接报错
            bad_weak_table(weak_entries);
        // 哈希冲突次数++
        hash_displacement++;
    }

    // 如果走到这里 表明index位置的元素referent=nil
    // 直接插入
    weak_entries[index] = *new_entry;
    // 实体个数++
    weak_table->num_entries++;

    // 最大哈希偏移值大于之前的记录
    if (hash_displacement > weak_table->max_hash_displacement) {
        // 更新最大哈希偏移值
        weak_table->max_hash_displacement = hash_displacement;
    }
}

插入操作也很简单，主要分为下面几个步骤:

  • 取出哈希表中所有弱引用对象的数据
  • 遍历第一步取出的所有数据，找到第一个空位置
  • 将要插入的实体插入到这个位置，同时更新当前weak_table中弱引用实体个数
  • 重置weak_table中最大哈希冲突次数的值

插入的主要逻辑实际上并不复杂，但是我们发现最后一步

1
2
3
4
5
// 如果本次哈希偏移值大于之前记录的最大偏移值 则更新 
if (hash_displacement > weak_table->max_hash_displacement) {
    // 修改最大哈希偏移值
    weak_table->max_hash_displacement = hash_displacement;
}

通过上面的代码我们发现，假设weak_table的weak_entries最大容量为8,当前存放了3个被弱引用的对象且分别存放在下标为[0,1,2]中，同时要插入的对象new_entry不再weak_entries中，那么经过while循环，hash_displacement = 3。实际上如果在没有哈希冲突的情况下我们通过hash_pointer得到的index就应该是用来存放new_entry的，但是因为存在哈希冲突，所以后移了3位后才找到合适的位置来存放new_entry，因此hash_displacement也被理解为，本应存放的位置距离实际存放位置的差值。

综上，我们分析了哈希表中获取所有弱引用某个对象的对象数组，哈希表扩容方法，以及如何在哈希表中插入一个弱引用对象。

下面我们来看下新增和释放弱引用对象的方法

objc_initWeak

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 初始化一个weak 弱引用
// 参数location weak指针的地址  newObj weak指针指向的对象
id
objc_initWeak(id *location, id newObj)
{
    // 如果弱引用对象为空
    if (!newObj) {
        *location = nil;
        return nil;
    }
    // 调用storeWeak
    return storeWeak<DontHaveOld, DoHaveNew, DoCrashIfDeallocating>
        (location, (objc_object*)newObj);
}

  • id *location ：__weak指针的地址，即weak指针取地址： &weakObj 。它是一个指针的地址。之所以要存储指针的地址，是因为最后我们要讲__weak指针指向的内容置为nil，如果仅存储指针的话，是不能够完成这个功能的。

  • id newObj ：所引用的对象。即例子中的obj 。

从上面我们看出objc_initWeak实际上是调用了storeWeak方法，且方法调用我们可以翻译为

1
2
storeWeak<false, true, true>
        (location, (objc_object*)newObj)

storeWeak

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
enum CrashIfDeallocating {
    DontCrashIfDeallocating = false, DoCrashIfDeallocating = true
};
template <HaveOld haveOld, HaveNew haveNew,
          CrashIfDeallocating crashIfDeallocating>
// HaveOld= true weak ptr之前是否已经指向了一个弱引用
// haveNew = true weak ptr是否需要指向一个新引用
// crashIfDeallocating = true 如果被弱引用的对象正在析构，此时再弱引用该对象，是否应该crash
// crashIfDeallocating = false 将存储的数据置为nil
// *location 代表weak 指针的地址
// newObj 被weak引用的对象。
static id 
storeWeak(id *location, objc_object *newObj)
{
    assert(haveOld  ||  haveNew);
    // 如果没有新值赋值 判断newObj 是否为空 否则断言
    if (!haveNew)
        assert(newObj == nil);

    Class previouslyInitializedClass = nil;
    id oldObj;

    SideTable *oldTable;
    SideTable *newTable;


 retry:
    // 如果weak ptr之前弱引用过一个obj，则将这个obj所对应的SideTable取出，赋值给oldTable
    if (haveOld) {
        // 根据传入的地址获取到旧的值
        oldObj = *location;
        // 根据旧值的地址获取到旧值所存在的SideTable
        oldTable = &SideTables()[oldObj];
    } else {
        // 如果weak ptr之前没有弱引用过一个obj，则oldTable = nil
        oldTable = nil;
    }
    // 是否有新值 如果有
    if (haveNew) {
        // 如果weak ptr要weak引用一个新的obj，则将该obj对应的SideTable取出，赋值给newTable
        newTable = &SideTables()[newObj];
    } else {
        // 如果weak ptr不需要引用一个新obj，则newTable = nil
        newTable = nil;
    }

    // 加锁管理一对 side tables，防止多线程中竞争冲突
    SideTable::lockTwo<haveOld, haveNew>(oldTable, newTable);

    // location 应该与 oldObj 保持一致，如果不同，说明当前的 location 已经处理过 oldObj 可是又被其他线程所修改
    if (haveOld  &&  *location != oldObj) {
        // 解锁后重试
        SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable);
        goto retry;
    }

    // 保证弱引用对象的 isa 都被初始化，防止弱引用和 +initialize 之间发生死锁，
    // 也就是避免 +initialize 中调用了 storeWeak 方法，而在 storeWeak 方法中 weak_register_no_lock
    // 方法中用到对象的 isa 还没有初始化完成的情况
    if (haveNew  &&  newObj) {
        Class cls = newObj->getIsa();
        // 如果cls还没有初始化，先初始化，再尝试设置weak
        if (cls != previouslyInitializedClass  &&  
            !((objc_class *)cls)->isInitialized()) 
        {
            SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable);
            // 发送 +initialize 消息到未初始化的类
            _class_initialize(_class_getNonMetaClass(cls, (id)newObj));

            // 如果该类还没有初始化完成，例如在 +initialize 中调用了 storeWeak 方法，
            // 也就是会进入这里面，进而设置  previouslyInitializedClass  以在重试时识别它
            // 这里记录一下previouslyInitializedClass， 防止改if分支再次进入
            previouslyInitializedClass = cls;
            // 重新获取一遍newObj，这时的newObj应该已经初始化过了
            goto retry;
        }
    }

    // 如果weak_ptr之前弱引用过别的对象oldObj，则调用weak_unregister_no_lock，在oldObj的weak_entry_t中移除该weak_ptr地址
    if (haveOld) {
        weak_unregister_no_lock(&oldTable->weak_table, oldObj, location);
    }

    // 如果weak_ptr需要弱引用新的对象newObj
    if (haveNew) {
        // (1) 调用weak_register_no_lock方法，将weak ptr的地址记录到newObj对应的weak_entry_t中
        newObj = (objc_object *)
            weak_register_no_lock(&newTable->weak_table, (id)newObj, location, 
                                  crashIfDeallocating);

        // (2) 更新newObj的isa的weakly_referenced bit标志位
        if (newObj  &&  !newObj->isTaggedPointer()) {
            newObj->setWeaklyReferenced_nolock();
        }

        // （3）*location 赋值，也就是将weak ptr直接指向了newObj。可以看到，这里并没有将newObj的引用计数+1
        // 将weak ptr指向object
        *location = (id)newObj;
    }
    else {
        // No new value. The storage is not changed.
    }
    // 解锁，其他线程可以访问oldTable, newTable了
    SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable);
    // 返回newObj，此时的newObj与刚传入时相比，weakly-referenced bit位置1
    return (id)newObj;
}

storeWeak方法有点长，这也是weak引用的核心实现部分。其实核心也就实现了两个功能：

将weak指针的地址location存入到obj对应的weak_entry_t的数组（链表）中，用于在obj析构时，通过该数组（链表）找到所有其weak指针引用，并将指针指向的地址（location）置为nil。

如果启用了isa优化，则将obj的isa_t的weakly_referenced位置1。置位1的作用主要是为了标记obj被weak引用了，当dealloc时，runtime会根据weakly_referenced标志位来判断是否需要查找obj对应的weak_entry_t，并将引用置为nil。

上面的方法中，我们看到插入新值的方法为weak_register_no_lock,清除旧值的方法为weak_unregister_no_lock,下面我们来看下这两个方法：

weak_register_no_lock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/ 添加对某个对象的新的弱引用指针
// weak_table 目标被弱引用对象所存储的表
// referent_id 被所引用的对象
// referrer_id 要被添加的弱引用指针
// crashIfDeallocating 如果对象正在被释放时是否崩溃
id 
weak_register_no_lock(weak_table_t *weak_table, id referent_id, 
                      id *referrer_id, bool crashIfDeallocating)
{
    // 被弱引用的对象
    objc_object *referent = (objc_object *)referent_id;
    // 要添加的指向弱引用指针的对象
    objc_object **referrer = (objc_object **)referrer_id;

    // 如果referent为nil 或 referent 采用了TaggedPointer计数方式，直接返回，不做任何操作
    if (!referent  ||  referent->isTaggedPointer()) return referent_id;

    // 确保被引用的对象可用（没有在析构，同时应该支持weak引用）
    bool deallocating;
    // referent 是否有自定义的释放方法
    if (!referent->ISA()->hasCustomRR()) {
        deallocating = referent->rootIsDeallocating();
    }
    else {
        // referent是否支持weak引用
        BOOL (*allowsWeakReference)(objc_object *, SEL) = 
            (BOOL(*)(objc_object *, SEL))
            object_getMethodImplementation((id)referent, 
                                           SEL_allowsWeakReference);
        // 如果referent不能够被weak引用，则直接返回nil
        if ((IMP)allowsWeakReference == _objc_msgForward) {
            return nil;
        }
        // 调用referent的SEL_allowsWeakReference方法来判断是否正在被释放
        deallocating =
            ! (*allowsWeakReference)(referent, SEL_allowsWeakReference);
    }

    // 正在析构的对象，不能够被弱引用
    if (deallocating) {
        // 判断是否需要崩溃 如果需要则崩溃
        if (crashIfDeallocating) {
            _objc_fatal("Cannot form weak reference to instance (%p) of "
                        "class %s. It is possible that this object was "
                        "over-released, or is in the process of deallocation.",
                        (void*)referent, object_getClassName((id)referent));
        } else {
            return nil;
        }
    }

    // 对象没有被正在释放
    weak_entry_t *entry;
    // 在 weak_table中找到referent对应的weak_entry,并将referrer加入到weak_entry中
    // 如果能找到weak_entry,则讲referrer插入到weak_entry中
    if ((entry = weak_entry_for_referent(weak_table, referent))) {
        // 将referrer插入到weak_entry_t的引用数组中
        append_referrer(entry, referrer);
    } 
    else {
        // 创建一个新的weak_entry_t ，并将referrer插入到weak_entry_t的引用数组中
        weak_entry_t new_entry(referent, referrer);
        // weak_table的weak_entry_t 数组是否需要动态增长，若需要，则会扩容一倍
        weak_grow_maybe(weak_table);
        // 将weak_entry_t插入到weak_table中
        weak_entry_insert(weak_table, &new_entry);
    }

    // Do not set *referrer. objc_storeWeak() requires that the 
    // value not change.

    return referent_id;
}

上面方法主要功能是：添加对某个对象的新的弱引用指针

  • 过滤掉isTaggedPointer和弱引用对象正在被释放这两种情况后(这里需要判断是否有自定义的释放方法)，然后根据crashIfDeallocating参数确定是崩溃还是返回nil
  • 如果对象没有正在被释放，那么从weak_table中取出指向referent的弱引用指针实体，如果weak_table中存在指向referent的指针数组那么在这个数组中添加要新增的指针
  • 如果weak_table没有找到指向referent的弱指针数组，那么新建一个weak_entry_t对象，将这个对象拆入到weak_table中(需要判断weak_table是否需要扩容)

下面我们来看下具体的插入方法：

append_referrer追加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// 在entry对象的弱引用数组中追加一个新的弱引用指针new_referrer
// entry 被弱引用的对象
// new_referrer 弱引用entry的指针
static void append_referrer(weak_entry_t *entry, objc_object **new_referrer)
{
    // 如果entry中弱引用指针没有超过了4个 表示弱引用指针存放在inline_referrers中
    // weak_entry 尚未使用动态数组
    if (! entry->out_of_line()) {
        // 遍历inline_referrers数组找到第一个为空的位置 将目标指针插入 尾部追加
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            if (entry->inline_referrers[i] == nil) {
                entry->inline_referrers[i] = new_referrer;
                return;
            }
        }

        // 如果entry中弱引用指针==4个
        // 新创建一个weak_referrer_t数组 大小为4(WEAK_INLINE_COUNT)
        // 如果inline_referrers的位置已经存满了，则要转型为referrers，做动态数组。
        weak_referrer_t *new_referrers = (weak_referrer_t *)
            calloc(WEAK_INLINE_COUNT, sizeof(weak_referrer_t));
        // 遍历inline_referrers 将数据放在新创建的临时数组中
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            new_referrers[i] = entry->inline_referrers[i];
        }
        // 弱引用指针的存储改为存放到entry->referrers(entry->inline_referrers -> entry->referrers)
        entry->referrers = new_referrers;
        // 更新弱引用个数
        entry->num_refs = WEAK_INLINE_COUNT;
        //更新是否使用动态数组标记位
        entry->out_of_line_ness = REFERRERS_OUT_OF_LINE;
        // 更新mask和最大哈希偏移值
        entry->mask = WEAK_INLINE_COUNT-1;
        entry->max_hash_displacement = 0;
    }

    assert(entry->out_of_line());

    // 如果只想entry的弱引用个数大于4
    // 弱引用个数是否已超过数组容量的3/4
    if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) {
        // 如果已超过 那么先扩容在插入
        return grow_refs_and_insert(entry, new_referrer);
    }

    // 如果不需要扩容，直接插入到weak_entry中
    // 注意，weak_entry是一个哈希表，key：w_hash_pointer(new_referrer) value: new_referrer
    size_t begin = w_hash_pointer(new_referrer) & (entry->mask);
    size_t index = begin;
    size_t hash_displacement = 0;
    // 由低到高遍历entry->referrers 找到第一个空位置
    while (entry->referrers[index] != nil) {
        hash_displacement++;
        index = (index+1) & entry->mask;
        // 如果遍历了所有元素后都没有找到 那么报错
        if (index == begin)
            bad_weak_table(entry);
    }
    // 更新最大哈希偏移值
    if (hash_displacement > entry->max_hash_displacement) {
        entry->max_hash_displacement = hash_displacement;
    }
    // 将new_referrer插入到数组的第index个位置
    weak_referrer_t &ref = entry->referrers[index];
    ref = new_referrer;
    // 弱引用计个数+1
    entry->num_refs++;
}

插入的过程主要分下面三种情况:

  • 如果inline_referrers没有存储满，直接存储到inline_referrers中
  • 如果inline_referrers个数是4个了，在插入，就需要将inline_referrers拷贝到referrers，然后进入第三步。
  • 如果inline_referrers存储满了，判断是否需要扩容，然后将数据存储到referrers中。

下面我们来看下扩容的方法:

grow_refs_and_insert

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// entry 中存放弱引用指针数组 扩容
// weak_entry_t 要扩容的对象
// new_referrer 要插入的指向entry->referent弱引用指针
__attribute__((noinline, used))
static void grow_refs_and_insert(weak_entry_t *entry, 
                                 objc_object **new_referrer)
{
    assert(entry->out_of_line());
    // 获取entry当前的大小
    size_t old_size = TABLE_SIZE(entry);
    // 新的大小为旧的大小的2倍
    size_t new_size = old_size ? old_size * 2 : 8;

    // 获取weak_entry_t中存储的弱引用指针个数
    size_t num_refs = entry->num_refs;
    //获取entry中旧的引用数组
    weak_referrer_t *old_refs = entry->referrers;
    // 更新entry->mask 这里是为了后续申请内存空间使用
    entry->mask = new_size - 1;

    // 创建一个新的entry->referrers数组
    // #define TABLE_SIZE(entry) (entry->mask ? entry->mask + 1 : 0)
    // TABLE_SIZE 获取的数组大小是 mask+1 = new_size
    entry->referrers = (weak_referrer_t *)
        calloc(TABLE_SIZE(entry), sizeof(weak_referrer_t));
    // 重置num_refs和max_hash_displacement
    entry->num_refs = 0;
    entry->max_hash_displacement = 0;

    // 将old_refs中的数据重新插入到新创建entry->referrers中
    for (size_t i = 0; i < old_size && num_refs > 0; i++) {
        if (old_refs[i] != nil) {
            append_referrer(entry, old_refs[i]);
            num_refs--;
        }
    }
    // 将new_referrer插入到扩容后的entry中
    append_referrer(entry, new_referrer);
    if (old_refs) free(old_refs);
}

看完了新增弱引用指针的操作，接下来我们看下如何删除弱引用指针即weak_unregister_no_lock

weak_unregister_no_lock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 将 weak ptr地址 从obj的weak_entry_t中移除
// 参数weak_table 全局弱引用表
// referent_id 弱引用所指向的对象
// referrer_id 弱引用指针地址
void
weak_unregister_no_lock(weak_table_t *weak_table, id referent_id, 
                        id *referrer_id)
{
    // 被弱引用的对象
    objc_object *referent = (objc_object *)referent_id;
    // 指向被弱引用对象的指针的地址
    objc_object **referrer = (objc_object **)referrer_id;

    weak_entry_t *entry;

    if (!referent) return;

    // 找到weak_table中指向被弱引用对象的所有指针 类型为 weak_entry_t
    if ((entry = weak_entry_for_referent(weak_table, referent))) {
        // 从数组中删除当前这个弱引用指针
        remove_referrer(entry, referrer);
        bool empty = true;
        // 弱引用referent对象的弱引用指针是否为空
        if (entry->out_of_line()  &&  entry->num_refs != 0) {
            empty = false;
        }
        else {
            // 如果referrer数组中为空 那么判断inline_referrers中是否为空 如果为空empty=true
            for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
                if (entry->inline_referrers[i]) {
                    empty = false; 
                    break;
                }
            }
        }

        // 如果为空 则证明没有其他指针指向这个被所引用的对象
        if (empty) {
            // 将这个实体从weak_table中移除
            weak_entry_remove(weak_table, entry);
        }
    }

    // Do not set *referrer = nil. objc_storeWeak() requires that the 
    // value not change.
}

weak_unregister_no_lock的实现逻辑比较简单,其实主要的操作为:

  • 首先，它会在weak_table中找出referent对应的weak_entry_t
  • 在weak_entry_t中移除referrer
  • 移除元素后，判断此时weak_entry_t中是否还有元素 （empty==true？）
  • 如果此时weak_entry_t已经没有元素了，则需要将weak_entry_t从weak_table中移除

而对于remove_referrer方法，我们来简单的看下他的实现:

remove_referrer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 删除old_referrer集合中的referrers
// 参数 entry 被弱引用对象
// 参数 old_referrer 要删除的弱引用指针
static void remove_referrer(weak_entry_t *entry, objc_object **old_referrer)
{
    // 指向entry的弱引用指针不超过4个
    if (! entry->out_of_line()) {
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            // 遍历inline_referrers数组如果找到直接置空
            if (entry->inline_referrers[i] == old_referrer) {
                entry->inline_referrers[i] = nil;
                return;
            }
        }
        // 如果没有找到 则报错 弱引用指针小于4个且在inline_referrers中没有找到
        _objc_inform("Attempted to unregister unknown __weak variable "
                     "at %p. This is probably incorrect use of "
                     "objc_storeWeak() and objc_loadWeak(). "
                     "Break on objc_weak_error to debug.\n", 
                     old_referrer);
        objc_weak_error();
        return;
    }

    // 哈希函数 判断这个旧的弱引用指针存放的位置
    size_t begin = w_hash_pointer(old_referrer) & (entry->mask);
    size_t index = begin;
    size_t hash_displacement = 0;
    // 遍历entry->referrers数组查找old_referrer
    while (entry->referrers[index] != old_referrer) {
        // 如果没有在指定index找到 那么取下一个位置的值比较
        index = (index+1) & entry->mask;
        // 如果找了一圈仍然没有找到 那么报错
        if (index == begin)
            bad_weak_table(entry);
        // 更新最大哈希偏移值
        hash_displacement++;
        // 如果最大哈希偏移值 超过了预定的限制 那么报错
        if (hash_displacement > entry->max_hash_displacement) {
            _objc_inform("Attempted to unregister unknown __weak variable "
                         "at %p. This is probably incorrect use of "
                         "objc_storeWeak() and objc_loadWeak(). "
                         "Break on objc_weak_error to debug.\n", 
                         old_referrer);
            objc_weak_error();
            return;
        }
    }

    // 走到这一步说明在entry->referrers中的index位置找到了值为old_referrer的引用
    // 将数组的这个位置置空
    entry->referrers[index] = nil;
    // 弱引用个数-1
    entry->num_refs--;
}

上面的描述也很简单，大概的流程为：

  • 在entry->inline_referrers中一次查找值为old_referrer的指针 如果找到就清空如果没找到报错
  • 在entry->referrers中查找值为old_referrer的指针，如果找到则置空同时entry->num_refs做-1操作(使用inline_referrers存储时不会更新num_refs值因此移除也不用-1)

我们在删除指向某个对象的某个弱引用指针之后，还会对存储指向该对象的弱引用指针数组做判空操作，如果发现数组为空，那表示目前没有弱引用指针指向这个对象，那我们需要将这个对象从weak_table中移除。下面我们来看下移除方法weak_entry_remove。

weak_entry_remove

1
2
3
4
5
6
7
8
9
10
11
12
13
//从weak_table中移除entry (指向entry的弱引用指针数为0)
static void weak_entry_remove(weak_table_t *weak_table, weak_entry_t *entry)
{
    // 如果弱引用指针超过4个(弱引用指针存放在entry->referrers中)
    if (entry->out_of_line())
        // 释放entry->referrers中所有数据
        free(entry->referrers);
    bzero(entry, sizeof(*entry));
    //num_entries-1
    weak_table->num_entries--;
    //weak_table是否需要锁绒
    weak_compact_maybe(weak_table);
}

上面方法的主要操作为:

  • 将没有弱引用的对象从全局的weak_table中移除
  • 减少weak_table中存储的弱引用对象个数
  • 判断weak_table是否需要缩小容量

上面的所有就是当我们将一个obj作weak引用时，所发生的事情。那么，当obj释放时，所有weak引用它的指针又是如何自动设置为nil的呢？接下来我们来看一下obj释放时，所发生的事情。

Dealloc

当对象引用计数为0时，runtime会调用_objc_rootDealloc方法来析构对象，实现如下：

1
2
3
4
5
6
7
8
9
10
11
- (void)dealloc {
    _objc_rootDealloc(self);
}

void
_objc_rootDealloc(id obj)
{
    assert(obj);

    obj->rootDealloc();
}

_objc_rootDealloc又会调用objc_object的rootDealloc方法

rootDealloc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
inline void
objc_object::rootDealloc()
{
//    判断object是否采用了Tagged Pointer计数，如果是，则不进行任何析构操作。
    if (isTaggedPointer()) return;  // fixme necessary?

    //接下来判断对象是否采用了优化的isa计数方式（isa.nonpointer）
    // 对象没有被weak引用!isa.weakly_referenced
    // 没有关联对象!isa.has_assoc
    // 没有自定义的C++析构方法!isa.has_cxx_dtor
    // 没有用到sideTable来做引用计数 !isa.has_sidetable_rc
    // 如果满足条件 则可以快速释放
    if (fastpath(isa.nonpointer  &&  
                 !isa.weakly_referenced  &&  
                 !isa.has_assoc  &&  
                 !isa.has_cxx_dtor  &&  
                 !isa.has_sidetable_rc))
    {
        assert(!sidetable_present());
        free(this);
    } 
    else {
        // 慢速释放
        object_dispose((id)this);
    }
}

因此根据上面代码判断，如果obj被weak引用了，应该进入object_dispose((id)this)分支，下面我们来看下object_dispose方法：

object_dispose

1
2
3
4
5
6
7
8
9
10
11
id 
object_dispose(id obj)
{
    if (!obj) return nil;
    // 析构obj
    objc_destructInstance(obj);
    // 释放内存
    free(obj);

    return nil;
}

析构obj主要是看objc_destructInstance方法，下面我们来看下这个方法的实现

objc_destructInstance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void *objc_destructInstance(id obj) 
{
    if (obj) {
        // Read all of the flags at once for performance.
		//c++析构函数
        bool cxx = obj->hasCxxDtor();
		//关联函数
        bool assoc = obj->hasAssociatedObjects();

        // 如果有c++析构函数 则调用c++析构函数.
        if (cxx)
            object_cxxDestruct(obj);

        // 如果有关联对象则移除关联对象
        if (assoc)
            _object_remove_assocations(obj);
        // 清理相关的引用
        obj->clearDeallocating();
    }

    return obj;
}

清理相关引用方法主要是在clearDeallocating中实现的，下面我们再来看下这个方法：

clearDeallocating

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//正在清除side table 和weakly referenced
inline void 
objc_object::clearDeallocating()
{
    // obj是否采用了优化isa引用计数
    if (slowpath(!isa.nonpointer)) {
		//没有采用优化isa引用计数 清理obj存储在sideTable中的引用计数等信息
        sidetable_clearDeallocating();
    }
    // 启用了isa优化，则判断是否使用了sideTable
    // 使用的原因是因为做了weak引用（isa.weakly_referenced ） 或 使用了sideTable的辅助引用计数（isa.has_sidetable_rc）
    else if (slowpath(isa.weakly_referenced  ||  isa.has_sidetable_rc)) {
        // Slow path for non-pointer isa with weak refs and/or side table data.
		//释放weak 和引用计数
        clearDeallocating_slow();
    }

    assert(!sidetable_present());
}

这里的清理方法有两个分别为sidetable_clearDeallocating和clearDeallocating_slow,

我们先来看下clearDeallocating_slow：

clearDeallocating_slow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
NEVER_INLINE void
objc_object::clearDeallocating_slow()
{
    assert(isa.nonpointer  &&  (isa.weakly_referenced || isa.has_sidetable_rc));

    // 在全局的SideTables中，以this指针为key，找到对应的SideTable
    SideTable& table = SideTables()[this];
    table.lock();
    	//// 如果obj被弱引用
    if (isa.weakly_referenced) {
		//// 在SideTable的weak_table中对this进行清理工作
        weak_clear_no_lock(&table.weak_table, (id)this);
    }
	// 如果采用了SideTable做引用计数
    if (isa.has_sidetable_rc) {
		//在SideTable的引用计数中移除this
        table.refcnts.erase(this);
    }
    table.unlock();
}

这里调用了weak_clear_no_lock来做weak_table的清理工作，同时将所有weak引用该对象的ptr置为nil。

weak_clear_no_lock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//清理weak_table，同时将所有weak引用该对象的ptr置为nil
void 
weak_clear_no_lock(weak_table_t *weak_table, id referent_id) 
{
    objc_object *referent = (objc_object *)referent_id;

    // 找到referent在weak_table中对应的weak_entry_t
    weak_entry_t *entry = weak_entry_for_referent(weak_table, referent);

    if (entry == nil) {
        /// XXX shouldn't happen, but does with mismatched CF/objc
        //printf("XXX no entry for clear deallocating %p\n", referent);
        return;
    }

    // 找出weak引用referent的weak 指针地址数组以及数组长度
    weak_referrer_t *referrers;
    size_t count;
    // 是否使用动态数组
    if (entry->out_of_line()) {
        referrers = entry->referrers;
        count = TABLE_SIZE(entry);
    } 
    else {
        referrers = entry->inline_referrers;
        count = WEAK_INLINE_COUNT;
    }

    // 遍历所有的所引用weak指针
    for (size_t i = 0; i < count; ++i) {
        // 取出每个weak ptr的地址
        objc_object **referrer = referrers[i];

        if (referrer) {
            // 如果weak ptr确实weak引用了referent，则将weak ptr设置为nil，这也就是为什么weak 指针会自动设置为nil的原因
            if (*referrer == referent) {
                *referrer = nil;
            }
            else if (*referrer) {
                // 如果所存储的weak ptr没有weak 引用referent，这可能是由于runtime代码的逻辑错误引起的，报错
                _objc_inform("__weak variable at %p holds %p instead of %p. "
                             "This is probably incorrect use of "
                             "objc_storeWeak() and objc_loadWeak(). "
                             "Break on objc_weak_error to debug.\n", 
                             referrer, (void*)*referrer, (void*)referent);
                objc_weak_error();
            }
        }
    }
    // 由于referent要被释放了，因此referent的weak_entry_t也要移除出weak_table
    weak_entry_remove(weak_table, entry);
}

上面就是为什么当对象析构时，所有弱引用该对象的指针都会被设置为nil的原因。

总结

综上我们讲述了SideTable的结构，以及如何使用SideTable存储和清除对象和指向这些对象的指针地址。从而在侧面验证了弱引用的存储方式以及在对象释放时如何将弱引用的指针置空。读完这篇文章相信你对于SideTable结构和弱引用已经有了一个比较全面的认识。

更新于 2020-12-05

Runtime# Runtime SideTable
Previous Post
RunTime解析--Category(分类)实现
Next Post
内存管理之Tagged pointer