OC|OC Runtime之Weak(1)---weak_table_t OCRuntime之Weak(1)---weak_table_t

众所周知，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_tnum_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 belowif (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); }