OC Runtime之Weak(1)---weak_table_
2017-08-03 本文已影响145人
08a2d4bd26c9
众所周知，weak，strong都是OC的修饰符，然而两者有很大的区别。strong会导致引用计数变化，而weak则不会。与此同时，weak引用在被指向的对象析构后，会自动的变为nil而不是野指针，从而可以避免程序崩溃。那么weak在runtime层是如何实现的呢？本系列文章会结合源码，详细分析weak的实现。
抛开苹果开源的runtime源码不谈，我们可以首先思考一下，如果需要我们来实现一套weak机制，那应该如何实现呢？假设目前有个object O，有一个weak引用W指向O，在O析构后，W会指向nil，说明runtime使用了某种数据结构记录的W和O的映射关系。这种映射关系应该是一对多的，即一个weak引用只能指向一个object，而一个object可以同时有很多weak引用指向。可以支持一对多映射的数据结构有很多，但如何快速的通过object O，找到其对应的一个或多个weak引用呢？无疑，HashTable是最优的解决方式，可以在O(1)的时间复杂度内进行快速查找。果不其然，在我们查看源码后发现，苹果正是使用了HashTable来维护对象和弱引用的映射关系。
struct weak_table_t {
weak_entry_t *weak_entries;
size_t num_entries;
uintptr_t mask;
uintptr_t max_hash_displacement;
};
上面的weak_table_t是一个c语言的结构体，是runtime对于HashTable的具体实现。weak_entry_t也是一个c语言的结构体，是weak_table_t中具体存储的值的类型，负责记录一个对象和其弱引用的对应关系。weak_entry_t的结构本文暂且不表，不影响对于weak_table_t的理解。num_entries负责记录weak_table_t目前保存的entry的数目，mask记录weak_table_t的总容量，max_hash_displacement记录weak_table_t所有项的最大偏移量，因为会有hash碰撞的情况，而weak_table_t采用了开放寻址来解决，所以某个entry实际存储的位置并不一定是hash函数计算出来的位置。mask和max_hash_displacement的作用后续会详细介绍。
Runtime实现了weak_grow_maybe，weak_compact_maybe这两个函数，用来在weak_table_t过满或者过空的情况下，及时调整其大小，以优化内存的使用率，提高运行效率。这两个函数通过调用weak_resize来调整weak_table_t大小。
static void weak_grow_maybe(weak_table_t *weak_table)
{
size_t old_size = TABLE_SIZE(weak_table);
// Grow if at least 3/4 full.
if (weak_table->num_entries >= old_size * 3 / 4) {
weak_resize(weak_table, old_size ? old_size*2 : 64);
}
}
- 该函数的目的是扩充HashTable的空间，扩充的条件是Table 3/4及以上的空间已经被使用。可以看出HashTable的初始化大小是64个weak_entry_t的空间，每次扩充后的空间都是当前空间的两倍，即2的N次方(N>=6)。
static void weak_compact_maybe(weak_table_t *weak_table)
{
size_t old_size = TABLE_SIZE(weak_table);
// Shrink if larger than 1024 buckets and at most 1/16 full.
if (old_size >= 1024 && old_size / 16 >= weak_table->num_entries) {
weak_resize(weak_table, old_size / 8);
// leaves new table no more than 1/2 full
}
}
- 该函数的目的是缩小HashTable的空间，缩小的条件是HashTable目前的大小不小于1024个weak_entry_t的空间，并且低于1/16的空间被占用。缩小后的空间是当前空间的1/8。
static void weak_resize(weak_table_t *weak_table, size_t new_size)
{
size_t old_size = TABLE_SIZE(weak_table);
weak_entry_t *old_entries = weak_table->weak_entries;
weak_entry_t *new_entries = (weak_entry_t *)
calloc(new_size, sizeof(weak_entry_t));
weak_table->mask = new_size - 1;
weak_table->weak_entries = new_entries;
weak_table->max_hash_displacement = 0;
weak_table->num_entries = 0; // restored by weak_entry_insert below
if (old_entries) {
weak_entry_t *entry;
weak_entry_t *end = old_entries + old_size;
for (entry = old_entries; entry < end; entry++) {
if (entry->referent) {
weak_entry_insert(weak_table, entry);
}
}
free(old_entries);
}
}
- 这个函数具体执行HashTable空间扩充和缩小，代码很容易看懂。首先根据new_size申请相应大小的内存，new_entries指针指向这块新申请的内存。设置weak_table的mask为new_size - 1。此处mask的作用是记录weak_table实际占用的内存边界，此外mask还有另一个重要的作用，之后会再次提及。
- 众所周知，HashTable可能会有hash碰撞，而weak_table_t使用了开放寻址法来处理碰撞。如果发生碰撞的话，将寻找相邻(如果已经到最尾端的话，则从头开始)的下一个空位。max_hash_displacement记录当前weak_table最大的偏移值，即hash函数计算的位置和实际存储位置的最大偏差。
众所周知，HashTable有一些标准的操作，比如插入，查询和删除等。weak_entry_insert，weak_entry_for_referent，weak_entry_remove分别对应这几种操作的实现。
static void weak_entry_insert(weak_table_t *weak_table, weak_entry_t *new_entry)
{
weak_entry_t *weak_entries = weak_table->weak_entries;
assert(weak_entries != nil);
size_t begin = hash_pointer(new_entry->referent) & (weak_table->mask);
size_t index = begin;
size_t hash_displacement = 0;
while (weak_entries[index].referent != nil) {
index = (index+1) & weak_table->mask;
if (index == begin) bad_weak_table(weak_entries);
hash_displacement++;
}
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_entry_t结构的entry(即对象和弱引用的映射关系)到weak_table中。hash_pointer是对引用(指针)的hash函数，具体的实现是对指针的地址，进行一系列的移位，异或等运算并返回。begin是hash_pointer的返回值和mask与运算的结果。上文提到的mask的第二个作用就是这里，之前提到，weak_table的size保持是2的N次方，而mask的值为size - 1，所以mask的二进制后N位都是1，而之前都是0，类似于00000111。所以与mask与操作后的值肯定会在[0,mask]这个区间内，也正好是weak_table实际的合法内存空间。
- 可以看出，如果发生了hash碰撞的话，将会依次向下寻找空位，并且用max_hash_displacement来记录整个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_table中的位置，查询过程和插入过程基本类似。
static void weak_entry_remove(weak_table_t *weak_table, weak_entry_t *entry)
{
// remove entry
if (entry->out_of_line()) free(entry->referrers);
bzero(entry, sizeof(*entry));
weak_table->num_entries--;
weak_compact_maybe(weak_table);
}
- 该函数的目的是从weak_table中删除某一项entry，即某个object和其weak引用的映射关系。函数的实现比较简单，首先将相应的内存清零，而后将weak_table的计数减一，然后调用weak_compact_maybe方法来判断是否需要缩小weak_table的空间。值得注意的是out_of_line()这个函数，与weak_entry_t的结构有密切的关系，后续的文章会继续讲解。
以上是weak_table_t内部的实现。此外runtime提供了四个供外部调用的函数。值得注意的是，这些函数没有加锁，都不是线程安全的。
id weak_register_no_lock(weak_table_t *weak_table, id referent,
id *referrer, bool crashIfDeallocating);
void weak_unregister_no_lock(weak_table_t *weak_table, id referent, id *referrer);
bool weak_is_registered_no_lock(weak_table_t *weak_table, id referent);
void weak_clear_no_lock(weak_table_t *weak_table, id referent);
四个函数的功能分别是，记录一对弱引用关系，删除一对弱引用关系，判断一个对象是否存在弱引用，和删除一个对象所有的弱引用。下面逐个分析每个函数的源码和实现。
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;
if (!referent || referent->isTaggedPointer()) return referent_id;
// ensure that the referenced object is viable
bool deallocating;
if (!referent->ISA()->hasCustomRR()) {
deallocating = referent->rootIsDeallocating();
}
else {
BOOL (*allowsWeakReference)(objc_object *, SEL) =
(BOOL(*)(objc_object *, SEL))
object_getMethodImplementation((id)referent,
SEL_allowsWeakReference);
if ((IMP)allowsWeakReference == _objc_msgForward) {
return nil;
}
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;
}
}
// now remember it and where it is being stored
weak_entry_t *entry;
if ((entry = weak_entry_for_referent(weak_table, referent))) {
append_referrer(entry, referrer);
}
else {
weak_entry_t new_entry(referent, referrer);
weak_grow_maybe(weak_table);
weak_entry_insert(weak_table, &new_entry);
}
// Do not set *referrer. objc_storeWeak() requires that the
// value not change.
return referent_id;
}
- 函数首先处理了Tagged Pointer和object正在析构这两种特殊情况。Tagged Pointer是苹果在64位环境下为了节约内存使用，提升效率而引入的一种新的“指针”，具体的实现此处不表，有兴趣的读者可以自行查阅相关资料，后续的文章也有可能对此进行讲解。此外object正在dealloc时，也是不可以建立weak引用的映射关系的。
- append_referrer的目的是对weak_entry_t类型的entry进行操作，添加一个Object的弱引用。后续讲解weak_entry_t的时候会再次提到。
- 函数的整体逻辑比较简单，首先查找weak_table中有没有该object对应的entry，如果没有就添加并且记录weak引用，并且判断是否需要扩充HashTable，如果有的话就直接记录weak引用。
bool
weak_is_registered_no_lock(weak_table_t *weak_table, id referent_id)
{
return weak_entry_for_referent(weak_table, (objc_object *)referent_id);
}
- Debug时判断当前weak_table中是否有对应某个object的entry。
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;
if ((entry = weak_entry_for_referent(weak_table, referent))) {
remove_referrer(entry, referrer);
bool empty = true;
if (entry->out_of_line() && entry->num_refs != 0) {
empty = false;
}
else {
for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
if (entry->inline_referrers[i]) {
empty = false;
break;
}
}
}
if (empty) {
weak_entry_remove(weak_table, entry);
}
}
// Do not set *referrer = nil. objc_storeWeak() requires that the
// value not change.
}
- 该函数的整体逻辑也相对简单，首先找到object对应的entry，并且删除对应的weak引用，而后判断entry中的weak引用是否已经为空，如果是则从weak_table中将其删除。如何判断entry中weak引用是否为空，之后介绍weak_entry_t的文章会详细讲解，此处不表。
void
weak_clear_no_lock(weak_table_t *weak_table, id referent_id)
{
objc_object *referent = (objc_object *)referent_id;
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;
}
// zero out references
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;
}
for (size_t i = 0; i < count; ++i) {
objc_object **referrer = referrers[i];
if (referrer) {
if (*referrer == referent) {
*referrer = nil;
}
else if (*referrer) {
_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();
}
}
}
weak_entry_remove(weak_table, entry);
}
- 该函数的目的是删除一个object所有的weak引用，并且清理其空间。最后从weak_table中将其对应的entry删除。同样，清理weak_entry_t内存的部分此处不表，后续再进行讲解。
至此，weak_table_t的基本结构和实现已经全部介绍完毕。后续会详细讲解weak_entry_t的结构和实现，以及NSObject如何和weak_table_t进行交互。这些加起来构成了完整的弱引用实现。
