iOS weak底层原理及源码解析

面试的时候，经常会问这个，之前面试回答的很简单，就是：底层有个hash表专门来维护存储weak指针，当指向的对象的引用计数为0的时候，就会从这张hash表中删除对应的weak指针，并将weak指针的值置为nil。这样回答也不知道面试官满不满意，虽然没毛病，但是总觉得没有深入回答，如果面试官继续深挖，可能就凉凉了，归其原因还是没有对底层原理及源码进行阅读研究。趁着公司项目不是很紧的时候，抽空阅读了下weak底层的源码，记录如下。

研究方法：

1. 拥有一份源码，这个可以在苹果开源网站下载 objc4，当然可以打开这个下载的工程进行编译调试，但是我目前用的Xcode11.2.1没办法链接下断点，最终还是走的系统自带的libobjc.dylib动态库，有解决办法的可以帮忙分享下，在此先表示感谢，所以这里也只能另外新建一个工程调试，找到weak实现相关的函数。
2. 调试方法，首先我们从调用栈看看weak干了什么，找到weak底层的入口函数。

• 新建一个工程，如下代码：

    NSObject* p = [NSObject new];
    NSObject* p1 = [NSObject new];
    __weak NSObject* weakP = p;
    weakP = p1;

• 下断点，并打开汇编，如下： 断点 打开汇编
• 运行，结果： 结果

  我们看到在viewDidLoad汇编代码上，我们看到了一些调用的函数符号，比如objc_msgSend、objc_initWeak、objc_storeWeak、objc_destroyWeak等等，结合写的测试代码看，objc_initWeak对应的应该是我们的__weak NSObject* weakP = p;这句代码，objc_storeWeak对应的应该是这句weakP = p1;当我们的viewDidLoad方法走完，由于我们声明的weakP是一个临时变量，所以还会调用objc_destroyWeak。我们一个一个的分析，这个就要用到源码了，我们在源码工程中全局搜索。

3. 源码分析

• objc_initWeak 全局搜索的到了如下结果 全局搜素objc_initWeak.png

  我们发现有一个.h文件和一个.mm文件，.h这个应该是系统动态库libobjc.dylib的对外的一个接口文件，.mm应该是对应的实现，我们直接到.mm文件，看到如下代码：

/** 
 * Initialize a fresh weak pointer to some object location. 
 * It would be used for code like: 
 *
 * (The nil case) 
 * __weak id weakPtr;
 * (The non-nil case) 
 * NSObject *o = ...;
 * __weak id weakPtr = o;
 * 
 * This function IS NOT thread-safe with respect to concurrent 
 * modifications to the weak variable. (Concurrent weak clear is safe.)
 *
 * @param location Address of __weak ptr. 
 * @param newObj Object ptr. 
 */
id
objc_initWeak(id *location, id newObj)
{
    if (!newObj) {
        *location = nil;
        return nil;
    }

    return storeWeak<DontHaveOld, DoHaveNew, DoCrashIfDeallocating>
        (location, (objc_object*)newObj);
}

注释翻译一下：这个函数是一个新的weak的指针初始化函数，比如

 __weak id weakPtr;
  NSObject *o = ...;
 __weak id weakPtr = o;

而我们的测试代码正好符合这点，说明我们上面的分析应该是没毛病的。再看看其他的，注释中对这个函数的两个参数，第一个就是location指针，对应weak指针，newObj就是指向的对象；函数里面，首先对对象进行的判断是否为空，若为空，直接将weak指针置为空，直接return，若不为空，调用了另外一个函数storeWeak，链接过去看看storeWeak的实现：

 template <HaveOld haveOld, HaveNew haveNew,
          CrashIfDeallocating crashIfDeallocating>
static id 
storeWeak(id *location, objc_object *newObj)
{
    assert(haveOld  ||  haveNew);
    if (!haveNew) assert(newObj == nil);

    Class previouslyInitializedClass = nil;
    id oldObj;
    SideTable *oldTable;
    SideTable *newTable;

    // Acquire locks for old and new values.
    // Order by lock address to prevent lock ordering problems. 
    // Retry if the old value changes underneath us.
 retry:
    if (haveOld) {
        oldObj = *location;
        oldTable = &SideTables()[oldObj];
    } else {
        oldTable = nil;
    }
    if (haveNew) {
        newTable = &SideTables()[newObj];
    } else {
        newTable = nil;
    }

    SideTable::lockTwo<haveOld, haveNew>(oldTable, newTable);

    if (haveOld  &&  *location != oldObj) {
        SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable);
        goto retry;
    }

    // Prevent a deadlock between the weak reference machinery
    // and the +initialize machinery by ensuring that no 
    // weakly-referenced object has an un-+initialized isa.
    if (haveNew  &&  newObj) {
        Class cls = newObj->getIsa();
        if (cls != previouslyInitializedClass  &&  
            !((objc_class *)cls)->isInitialized()) 
        {
            SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable);
            class_initialize(cls, (id)newObj);

            // If this class is finished with +initialize then we're good.
            // If this class is still running +initialize on this thread 
            // (i.e. +initialize called storeWeak on an instance of itself)
            // then we may proceed but it will appear initializing and 
            // not yet initialized to the check above.
            // Instead set previouslyInitializedClass to recognize it on retry.
            previouslyInitializedClass = cls;

            goto retry;
        }
    }

    // Clean up old value, if any.
    if (haveOld) {
        weak_unregister_no_lock(&oldTable->weak_table, oldObj, location);
    }

    // Assign new value, if any.
    if (haveNew) {
        newObj = (objc_object *)
            weak_register_no_lock(&newTable->weak_table, (id)newObj, location, 
                                  crashIfDeallocating);
        // weak_register_no_lock returns nil if weak store should be rejected

        // Set is-weakly-referenced bit in refcount table.
        if (newObj  &&  !newObj->isTaggedPointer()) {
            newObj->setWeaklyReferenced_nolock();
        }

        // Do not set *location anywhere else. That would introduce a race.
        *location = (id)newObj;
    }
    else {
        // No new value. The storage is not changed.
    }
    
    SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable);

    return (id)newObj;
}

我们可以看到，这个是一个模板函数，也是weak的核心函数，从这个函数可以看出整个weak的整个流程。函数实现里面一开始就声明了两个数据类型SideTable，我想应该是文章一开始提到的hash表，我们点进去看看：

struct SideTable {
    spinlock_t slock;
    RefcountMap refcnts;
    weak_table_t weak_table;

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

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

    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;//自旋锁，访问其他两个成员变量的时候加锁
• RefcountMap refcnts; //引用计数表，内存管理的引用计数
• weak_table_t weak_table; //弱引用hash表，这个就是目前研究的weak指针存放的地方
  从上面分析可以得出，SideTable是各种弱引用表和引用计数表的拥有者，也可以描述为管理者，而SideTable是存放在哪呢？这个问题后面再研究，先研究下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;
    size_t    num_entries;
    uintptr_t mask;
    uintptr_t max_hash_displacement;
};

同样可以看到weak_table_t结构体有四个成员变量：

• weak_entry_t *weak_entries;///存储weak指针的动态数组，类型是weak_entry_t
• size_t num_entries;///已经存放的指针数
• uintptr_t mask;///参与hash计算的辅助变量
• uintptr_t max_hash_displacement;///可能会发生的hash冲突的最大次数，用于判断是否出现了逻辑错误（hash表中的冲突次数绝不会超过改值）
  上面提到weak指针存储在weak_entries的动态数组中，类型是weak_entry_t，那看看weak_entry_t这个类型的定义：

/**
 * 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.
 */
#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.
#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;
            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;
        }
    }
};

weak_entry_t结构体里面有两个成员变量：
DisguisedPtr<objc_object> referent;//这个是一个将一个对象的指针地址进行特殊处理，就是取负值。另一个是一个union，上面的注释说明了，当存储的weak指针数量小于WEAK_INLINE_COUNT是就用包含静态数组inline_referrers的结构体存储，超过则用另外一个结构体（保含动态数组referrers）存储，这个结构体的成员变量是不是有点眼熟，跟上面的weak_table_t有点类似，所以这个也是一个hash表，他的插入跟查找如下：

• 插入：

/** 
 * Add the given referrer to set of weak pointers in this entry.
 * Does not perform duplicate checking (b/c weak pointers are never
 * added to a set twice). 
 *
 * @param entry The entry holding the set of weak pointers. 
 * @param new_referrer The new weak pointer to be added.
 */
static void append_referrer(weak_entry_t *entry, objc_object **new_referrer)
{
    if (! entry->out_of_line()) {///没有超过out_of_line，使用静态数组存储
        // Try to insert inline.
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            if (entry->inline_referrers[i] == nil) {///找到空位存储
                entry->inline_referrers[i] = new_referrer;
                return;
            }
        }

        // Couldn't insert inline. Allocate out of line.///超过了out_of_line，使用动态数组存储
        weak_referrer_t *new_referrers = (weak_referrer_t *)
            calloc(WEAK_INLINE_COUNT, sizeof(weak_referrer_t));///new动态数组，大小为WEAK_INLINE_COUNT
        // This constructed table is invalid, but grow_refs_and_insert
        // will fix it and rehash it.
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            new_referrers[i] = entry->inline_referrers[i];///将之前的赋值到对应的位置
        }
///初始化其他参数
        entry->referrers = new_referrers;
        entry->num_refs = WEAK_INLINE_COUNT;
        entry->out_of_line_ness = REFERRERS_OUT_OF_LINE;
        entry->mask = WEAK_INLINE_COUNT-1;
        entry->max_hash_displacement = 0;
    }

    assert(entry->out_of_line());

    if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) {///当已存weak指针数量达到一定数量，动态数组扩容，具体是超过数组容量的3/4的时候扩容，例如存第5个的时候，就会出发动态数组扩容，这个时候是4>4*3/4成立，触发扩容。
        return grow_refs_and_insert(entry, new_referrer);///动态数组扩容
    }
    size_t begin = w_hash_pointer(new_referrer) & (entry->mask);///这里参与hash的key是对象的二级指针，就是weak指针所在的地址，也是动态数组中存的元素值，跟weak_table_t的hash算法一样，解决hash冲突方式也是一样，开放地址法
    size_t index = begin;
    size_t hash_displacement = 0;
    while (entry->referrers[index] != nil) {///找到为空的位置
        hash_displacement++;
        index = (index+1) & entry->mask;///解决hash冲突
        if (index == begin) bad_weak_table(entry);
    }
    if (hash_displacement > entry->max_hash_displacement) {
        entry->max_hash_displacement = hash_displacement;///改变最大冲突数
    }
    weak_referrer_t &ref = entry->referrers[index];
    ref = new_referrer;///存储weak指针所在的地址值
    entry->num_refs++;///已存空间加1
}

动态数组扩容：

/** 
 * Grow the entry's hash table of referrers. Rehashes each
 * of the referrers.
 * 
 * @param entry Weak pointer hash set for a particular object.
 */
__attribute__((noinline, used))
static void grow_refs_and_insert(weak_entry_t *entry, 
                                 objc_object **new_referrer)
{
    assert(entry->out_of_line());

    size_t old_size = TABLE_SIZE(entry);///拿到旧的容量
    size_t new_size = old_size ? old_size * 2 : 8;///默认是扩容到8，其他在原有容量基础上2倍

    size_t num_refs = entry->num_refs;///记录原有已存储的数量
    weak_referrer_t *old_refs = entry->referrers;
    entry->mask = new_size - 1;///更新mask
    
    entry->referrers = (weak_referrer_t *)
        calloc(TABLE_SIZE(entry), sizeof(weak_referrer_t));///根据最新容量，new一份新的数组
    entry->num_refs = 0;///初始化为0
    entry->max_hash_displacement = 0;///初始化为0
    
    for (size_t i = 0; i < old_size && num_refs > 0; i++) {
        if (old_refs[i] != nil) {
            append_referrer(entry, old_refs[i]);///将原有的数组重新经过hash值的运算放入的对应的位置
            num_refs--;
        }
    }
    // Insert
    append_referrer(entry, new_referrer);///将最新的weak指针地址插入动态数组中
    if (old_refs) free(old_refs);///释放掉旧的数组
}

• 移除对应的weak指针：

/** 
 * Remove old_referrer from set of referrers, if it's present.
 * Does not remove duplicates, because duplicates should not exist. 
 * 
 * @todo this is slow if old_referrer is not present. Is this ever the case? 
 *
 * @param entry The entry holding the referrers.
 * @param old_referrer The referrer to remove. 
 */
static void remove_referrer(weak_entry_t *entry, objc_object **old_referrer)
{
    if (! entry->out_of_line()) {///没有超过容量，静态数组中查找删除
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            if (entry->inline_referrers[i] == old_referrer) {
                entry->inline_referrers[i] = nil;
                return;
            }
        }
        _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);///已weak指针的地址作为key，hash
    size_t index = begin;
    size_t hash_displacement = 0;
    while (entry->referrers[index] != old_referrer) {///hash冲突
        index = (index+1) & entry->mask;///+1往下一个查找
        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] = nil;///查找到，置为nil
    entry->num_refs--;///数量-1
}

好了，到目前为止，我们把数据结构基本上理了一遍，有了基本的印象，我们回到storeWeak函数。
storeWeak这个是一个template函数，我们先看看template的参数：

• HaveOld haveOld, ///标记weak指针有指向的值
• HaveNew haveNew,///标记weak指针需要指向新值
• CrashIfDeallocating crashIfDeallocatin///标记当引用的对象dealloc的时候，weak指针不需要保存。
  继续看，一开始声明的两个SideTable类型的表进行了判断赋值：

 if (haveOld) {///有旧值
        oldObj = *location;///拿到旧对象，作为后面从旧hash表中移除weak指针的key值
        oldTable = &SideTables()[oldObj];///拿到旧的hash表
    } else {
        oldTable = nil;///没有旧值，旧hash表赋值为nil
    if (haveNew) {///有新值
        newTable = &SideTables()[newObj];///拿到新的hash表
    } else {
        newTable = nil;///没有新值，新hash表赋值为nil
    }

从上面的代码可以看到有个关键的函数SideTables()，可以进去看看：

// We cannot use a C++ static initializer to initialize SideTables because
// libc calls us before our C++ initializers run. We also don't want a global 
// pointer to this struct because of the extra indirection.
// Do it the hard way.
alignas(StripedMap<SideTable>) static uint8_t 
    SideTableBuf[sizeof(StripedMap<SideTable>)];///全局数组

static StripedMap<SideTable>& SideTables() {
    return *reinterpret_cast<StripedMap<SideTable>*>(SideTableBuf);///将全局数组强转为StripedMap<SideTable>*>类型
}

是一个全局函数，返回的是一个StripedMap<SideTable>类型的引用，从字面上理解，应该是一个value为SideTable类型的map，我们知道NSDictionary的底层就是hashMap实现的，我们看看StripedMap<SideTable>是不是：

enum { CacheLineSize = 64 };

// StripedMap<T> is a map of void* -> T, sized appropriately 
// for cache-friendly lock striping. 
// For example, this may be used as StripedMap<spinlock_t>
// or as StripedMap<SomeStruct> where SomeStruct stores a spin lock.
template<typename T>
class StripedMap {
#if TARGET_OS_IPHONE && !TARGET_OS_SIMULATOR
    enum { StripeCount = 8 };
#else
    enum { StripeCount = 64 };
#endif

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

    PaddedT array[StripeCount];

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

 public:
    T& operator[] (const void *p) { 
        return array[indexForPointer(p)].value; 
    }
    const T& operator[] (const void *p) const { 
        return const_cast<StripedMap<T>>(this)[p]; 
    }

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

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

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

    void defineLockOrder() {
        for (unsigned int i = 1; i < StripeCount; i++) {
            lockdebug_lock_precedes_lock(&array[i-1].value, &array[i].value);
        }
    }

    void precedeLock(const void *newlock) {
        // assumes defineLockOrder is also called
        lockdebug_lock_precedes_lock(&array[StripeCount-1].value, newlock);
    }

    void succeedLock(const void *oldlock) {
        // assumes defineLockOrder is also called
        lockdebug_lock_precedes_lock(oldlock, &array[0].value);
    }

    const void *getLock(int i) {
        if (i < StripeCount) return &array[i].value;
        else return nil;
    }
    
#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
};

StripedMap<T>是一个模板类，成员变量是一个数组，对iPhone而言是数组的count大小为64，数组元素的大小都是64位对齐，是一个void* -> T的map。那么，SideTables()全局函数，返回的就是一个静态全局是一个objc_object* -> SideTable的hashmap。
StripedMap类里面还定义了相关index的hash算法：

static unsigned int indexForPointer(const void *p) {
        uintptr_t addr = reinterpret_cast<uintptr_t>(p);
        return ((addr >> 4) ^ (addr >> 9)) % StripeCount;///确保不超过StripeCount，防止越界，当然就有可能，多个obj共用一个sideTable
    }

重新定义了[]：

 T& operator[] (const void *p) { 
        return array[indexForPointer(p)].value; 
    }

其他的是锁相关的操作函数，对访问sideTable的加锁，同一时间只能一个资源能访问同一个sideTable。
上面提到过，SideTables()的到的是一个大小固定为64的数组，那么肯定会出现，多个obj共用一个sideTable，具体到weakTable也会多个Obj就会共用一个，到了weakTable里面还会对objc的地址在次进行hash运算，具体到函数如下：

• 查找weak_entry_t

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;///hash算法
    size_t index = begin;
    size_t hash_displacement = 0;
    while (weak_table->weak_entries[index].referent != referent) {///找到对应对象的存放位置，需要处理hash冲突，如果存在hash冲突具体会往下一个查找，直到找到空位，这个就是开放地址法处理hash冲突
        index = (index+1) & weak_table->mask;
        if (index == begin) bad_weak_table(weak_table->weak_entries);
        hash_displacement++;///冲突处理次数加1
        if (hash_displacement > weak_table->max_hash_displacement) {
            return nil;///当超过了最大的冲突处理次数后，说明没有查找到，就会返回nil。
        }
    }
    
    return &weak_table->weak_entries[index];///查找到返回对应weak_entry_t
}

• 而插入新的weak_entry_t就是如下的逻辑：

/** 
 * Add new_entry to the object's table of weak references.
 * Does not check whether the referent is already in the table.
 */
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);///跟查找一样的hash算法
    size_t index = begin;
    size_t hash_displacement = 0;
    while (weak_entries[index].referent != nil) {///找到为nil的位置
        index = (index+1) & weak_table->mask;
        if (index == begin) bad_weak_table(weak_entries);
        hash_displacement++;///当前的最大冲突次数
    }

    weak_entries[index] = *new_entry;///存储weak_entry_t
    weak_table->num_entries++;///已存储位置数+1

    if (hash_displacement > weak_table->max_hash_displacement) {
        weak_table->max_hash_displacement = hash_displacement;///与max_hash_displacement当前冲突次数大，则赋值给max_hash_displacement
    }
}

• 当然，插入新的weak_entry_t的时候，会先判断weak_table_t是否需要扩容：

// Grow the given zone's table of weak references if it is full.
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) {///超过最大容量的3/4
        weak_resize(weak_table, old_size ? old_size*2 : 64);///在原来的容量基础上*2，默认初始值是64
    }
}

• 移除weak_entry_t：

/** 
 * Remove old_referrer from set of referrers, if it's present.
 * Does not remove duplicates, because duplicates should not exist. 
 * 
 * @todo this is slow if old_referrer is not present. Is this ever the case? 
 *
 * @param entry The entry holding the referrers.
 * @param old_referrer The referrer to remove. 
 */
static void remove_referrer(weak_entry_t *entry, objc_object **old_referrer)
{
    if (! entry->out_of_line()) {///从静态数组中移除
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            if (entry->inline_referrers[i] == old_referrer) {
                entry->inline_referrers[i] = nil;
                return;
            }
        }
        _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;
    while (entry->referrers[index] != old_referrer) {
        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] = nil;
    entry->num_refs--;
}

好了到目前为止，我们可以清晰的看到weak存储的整个数据结构及关系，如下： weak的存储的数据结构及关系

再次回到storeWeak函数：

// Clean up old value, if any.
    if (haveOld) {
        weak_unregister_no_lock(&oldTable->weak_table, oldObj, location);///如果有旧指向，从旧表中移除weak地址值
    }

    // Assign new value, if any.
    if (haveNew) {
        newObj = (objc_object *)
            weak_register_no_lock(&newTable->weak_table, (id)newObj, location, 
                                  crashIfDeallocating);///在新表中插入weak指针的地址，成功返回newObj，否则返回nil
        // weak_register_no_lock returns nil if weak store should be rejected

        // Set is-weakly-referenced bit in refcount table.
        if (newObj  &&  !newObj->isTaggedPointer()) {///Tagged Pointer是苹果在64位系统之后，用来优化内存的，下一个内存管理篇研究下
            newObj->setWeaklyReferenced_nolock();///在引用计数表（下一个研究对象）中标记有弱引用指向，当引用计数为0时，触发移除相对应的weak指针。
        }

        // Do not set *location anywhere else. That would introduce a race.
        *location = (id)newObj;///将weak指针指向新的对象
    }
    else {
        // No new value. The storage is not changed.
    }

这里需要研究两个函数：

• weak_register_no_lock(&newTable->weak_table, (id)newObj, location,
  crashIfDeallocating);///插入weak指针

/** 
 * Registers a new (object, weak pointer) pair. Creates a new weak
 * object entry if it does not exist.///是否存在弱引用weak_entry_t，有，则在对应的数组中插入当前需要插入的weak指针，没有，新建一个weak_entry_t数据插入到弱引用表中
 * 
 * @param weak_table The global weak table.
 * @param referent The object pointed to by the weak reference.
 * @param referrer The weak pointer address.
 */
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;///运用TaggedPointer计数，无需维护weak_table_t弱引用表

    // 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))) {///在弱引用表中查找weak_entry_t，存在
        append_referrer(entry, referrer);///插入weak指针，上面分析过
    } 
    else {///没有weak_entry_t
        weak_entry_t new_entry(referent, referrer);///new一份weak_entry_t
        weak_grow_maybe(weak_table);///判断weak_table是否需要扩容，上面提到过
        weak_entry_insert(weak_table, &new_entry);///插入weak指针，上面提到过
    }

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

    return referent_id;
}

• weak_unregister_no_lock(&oldTable->weak_table, oldObj, location);///移除weak指针

/** 
 * Unregister an already-registered weak reference.
 * This is used when referrer's storage is about to go away, but referent
 * isn't dead yet. (Otherwise, zeroing referrer later would be a
 * bad memory access.)
 * Does nothing if referent/referrer is not a currently active weak reference.
 * Does not zero referrer.
 * 
 * FIXME currently requires old referent value to be passed in (lame)
 * FIXME unregistration should be automatic if referrer is collected
 * 
 * @param weak_table The global weak table.
 * @param referent The object.
 * @param referrer The weak reference.
 */
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))) {///查找weak_entry_t
        remove_referrer(entry, referrer);///移除对应的weak指针
        bool empty = true;///对应的weak_entry_t是否移除空了
        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);///如果entry里面的数组被移除空了，就要从weak_table表中将对应的entry移除
        }
    }

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

• 这里需要看下从weak_table表中将对应的entry移除：

/**
 * Remove entry from the zone's table of weak references.
 */
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));///释放entry

    weak_table->num_entries--;///对应的已存数量-1

    weak_compact_maybe(weak_table);///这里会查看下weakTable的容量是否需要减容，上面讲到过扩容
}

• weak_compact_maybe

// Shrink the table if it is mostly empty.
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) {当就容量超过1024且，是利用率不及1/16的时候，减容
        weak_resize(weak_table, old_size / 8);///在原有的基础上除以8
        // leaves new table no more than 1/2 full
    }
}

总结下：

• 底层数据结构

1. weak的底层的实现的数据结构是嵌套的hash表，首先是在全局的散列表SideTables中（hashMap）管理了固定的64份sideTble，key是object，这样就会出现多个object对应同一个sideTble，SideTables解决hash冲突是类似拉链方式，每个sideTble对应着一张弱引用表weak_table，这里的弱引用类似于一个链表，实际是动态数组方式；
   2、在weak_table中通过对object的地址再次hash找到真正的所在动态数组的位置，然后每个位置存放的是weak_entry_t，在插入新的weak_entry_t的时候可能会扩容，反之，当weak_entry_t的nums为空的时候，需要移除weak_entry_t，这个时候可能会减容；
   3、这里的weak_entry_t也是一张hash表，是weak指针的地址作为key，hash后，计算到对应数组的下标index，将weak指针的地址保存起来，当数据小于4个的时候，使用的是静态数组，超过这个数的时候，会使用动态数组，跟上面的weak_table一样，也是会涉及到扩容，默认是8，其他情况是*2。

• 流程：
  1、初始化一个weak指针并赋值时，会调用id
  objc_initWeak(id *location, id newObj)；
  2、将weak指针指向另外一个对象时，会调用id
  objc_storeWeak(id *location, id newObj)；
  3、释放一个weak指针时，会调用void
  objc_destroyWeak(id *location)；
  上面三个都会调用template <HaveOld haveOld, HaveNew haveNew,
  CrashIfDeallocating crashIfDeallocating>
  static id
  storeWeak(id *location, objc_object *newObj)；这个模板函数，只不过传的参数有区别，初始化，没有旧值需要处理，重新指向跟释放，有旧值需要处理，后面两个的区别是，释放没有新值需要处理。这些具体到函数是：
  a. 移除旧值void
  weak_unregister_no_lock(weak_table_t *weak_table, id referent_id,
  id *referrer_id)
  b. 插入新值id
  weak_register_no_lock(weak_table_t *weak_table, id referent_id,
  id *referrer_id, bool crashIfDeallocating)
  以上，欢迎指正。