上篇文章介绍了内存管理方案中的Tagged Pointer 小对象类型，这篇文章来介绍下另一种方案sideTable 散列表

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);
};

由上述代码得知散列表其实就是个结构体,我们发现有refcnts和weak_table这两张表

引用计数

retain源码分析

进入objc_retain -> retain -> rootRetain源码实现

ALWAYS_INLINE id 
objc_object::rootRetain(bool tryRetain, bool handleOverflow)
{
    if (isTaggedPointer()) return (id)this;

    bool sideTableLocked = false;
    bool transcribeToSideTable = false;
    //需要对引用计数+1，即retain+1，而引用计数存储在isa的bits中，需要进行新旧isa的替换,所以这里需要isa
    isa_t oldisa;
    isa_t newisa;
    do {
        transcribeToSideTable = false;
        oldisa = LoadExclusive(&isa.bits);
        newisa = oldisa;
        //判断是否为nonpointer isa
        if (slowpath(!newisa.nonpointer)) {
            //如果不是 nonpointer isa，直接操作散列表sidetable
            ClearExclusive(&isa.bits);
            if (rawISA()->isMetaClass()) return (id)this;
            if (!tryRetain && sideTableLocked) sidetable_unlock();
            if (tryRetain) return sidetable_tryRetain() ? (id)this : nil;
            else return sidetable_retain();
        }
        // don't check newisa.fast_rr; we already called any RR overrides
        //是否正在析构
        if (slowpath(tryRetain && newisa.deallocating)) {
            ClearExclusive(&isa.bits);
            if (!tryRetain && sideTableLocked) sidetable_unlock();
            return nil;
        }
        
        
        uintptr_t carry;
        //执行引用计数+1操作，即对bits中的 1ULL<<45（arm64） 即extra_rc，用于该对象存储引用计数值
        newisa.bits = addc(newisa.bits, RC_ONE, 0, &carry);  // extra_rc++
        //判断extra_rc是否满了，carry是标识符
        if (slowpath(carry)) {
            // newisa.extra_rc++ overflowed
            if (!handleOverflow) {
                ClearExclusive(&isa.bits);
                return rootRetain_overflow(tryRetain);
            }
            // Leave half of the retain counts inline and 
            // prepare to copy the other half to the side table.
            if (!tryRetain && !sideTableLocked) sidetable_lock();
            sideTableLocked = true;
            transcribeToSideTable = true;
            //如果extra_rc满了，则直接将满状态的一半拿出来存到extra_rc
            newisa.extra_rc = RC_HALF;
            //给一个标识符为YES，表示需要存储到散列表
            newisa.has_sidetable_rc = true;
        }
    } while (slowpath(!StoreExclusive(&isa.bits, oldisa.bits, newisa.bits)));

    if (slowpath(transcribeToSideTable)) {
        // Copy the other half of the retain counts to the side table.
        //将另一半存在散列表中
        sidetable_addExtraRC_nolock(RC_HALF);
    }

    if (slowpath(!tryRetain && sideTableLocked)) sidetable_unlock();
    return (id)this;
}

• 判断是否是Nonpointer_isa，如果不是直接往散列表中存
• 判断是否正在释放，如果正在释放，执行dealloc流程
• 执行extra_rc+1，即引用计数+1操作，并给一个引用计数的状态标识carry，用于表示extra_rc是否满了
• 如果是carray状态，表示extra_rc已经存满，这时需要忘散列表中存。即将满状态的计数一半存入extra_rc，一半存入散列表。这样做是因为都存入散列表中，每次对散列表操作都需要开解锁，操作耗时，消耗性能大，这么对半分操作的目的在于提高性能

release源码分析

ALWAYS_INLINE bool 
objc_object::rootRelease(bool performDealloc, bool handleUnderflow)
{
    if (isTaggedPointer()) return false;

    bool sideTableLocked = false;

    isa_t oldisa;
    isa_t newisa;

 retry:
    do {
        oldisa = LoadExclusive(&isa.bits);
        newisa = oldisa;
        //判断是否是Nonpointer isa
        if (slowpath(!newisa.nonpointer)) {
            //如果不是，则直接操作散列表-1
            ClearExclusive(&isa.bits);
            if (rawISA()->isMetaClass()) return false;
            if (sideTableLocked) sidetable_unlock();
            return sidetable_release(performDealloc);
        }
        // don't check newisa.fast_rr; we already called any RR overrides
        uintptr_t carry;
        //进行引用计数-1操作，即extra_rc-1
        newisa.bits = subc(newisa.bits, RC_ONE, 0, &carry);  // extra_rc--
        //如果此时extra_rc的值为0了，则走到underflow
        if (slowpath(carry)) {
            // don't ClearExclusive()
            goto underflow;
        }
    } while (slowpath(!StoreReleaseExclusive(&isa.bits, 
                                             oldisa.bits, newisa.bits)));

    if (slowpath(sideTableLocked)) sidetable_unlock();
    return false;

 underflow:
    // newisa.extra_rc-- underflowed: borrow from side table or deallocate

    // abandon newisa to undo the decrement
    newisa = oldisa;
    //散列表中是否存储了一半的引用计数
    if (slowpath(newisa.has_sidetable_rc)) {
        if (!handleUnderflow) {
            ClearExclusive(&isa.bits);
            return rootRelease_underflow(performDealloc);
        }

        // Transfer retain count from side table to inline storage.

        if (!sideTableLocked) {
            ClearExclusive(&isa.bits);
            sidetable_lock();
            sideTableLocked = true;
            // Need to start over to avoid a race against 
            // the nonpointer -> raw pointer transition.
            goto retry;
        }

        // Try to remove some retain counts from the side table.
        //从散列表中取出存储的一半引用计数
        size_t borrowed = sidetable_subExtraRC_nolock(RC_HALF);

        // To avoid races, has_sidetable_rc must remain set 
        // even if the side table count is now zero.

        if (borrowed > 0) {
            // Side table retain count decreased.
            // Try to add them to the inline count.
            //进行-1操作，然后存储到extra_rc中
            newisa.extra_rc = borrowed - 1;  // redo the original decrement too
            bool stored = StoreReleaseExclusive(&isa.bits, 
                                                oldisa.bits, newisa.bits);
            if (!stored) {
                // Inline update failed. 
                // Try it again right now. This prevents livelock on LL/SC 
                // architectures where the side table access itself may have 
                // dropped the reservation.
                isa_t oldisa2 = LoadExclusive(&isa.bits);
                isa_t newisa2 = oldisa2;
                if (newisa2.nonpointer) {
                    uintptr_t overflow;
                    newisa2.bits = 
                        addc(newisa2.bits, RC_ONE * (borrowed-1), 0, &overflow);
                    if (!overflow) {
                        stored = StoreReleaseExclusive(&isa.bits, oldisa2.bits, 
                                                       newisa2.bits);
                    }
                }
            }

            if (!stored) {
                // Inline update failed.
                // Put the retains back in the side table.
                sidetable_addExtraRC_nolock(borrowed);
                goto retry;
            }

            // Decrement successful after borrowing from side table.
            // This decrement cannot be the deallocating decrement - the side 
            // table lock and has_sidetable_rc bit ensure that if everyone 
            // else tried to -release while we worked, the last one would block.
            sidetable_unlock();
            return false;
        }
        else {
            // Side table is empty after all. Fall-through to the dealloc path.
        }
    }
    //此时extra_rc中值为0，散列表中也是空的，则直接进行析构，即自动触发dealloc流程
    if (slowpath(newisa.deallocating)) {
        ClearExclusive(&isa.bits);
        if (sideTableLocked) sidetable_unlock();
        return overrelease_error();
        // does not actually return
    }
    newisa.deallocating = true;
    if (!StoreExclusive(&isa.bits, oldisa.bits, newisa.bits)) goto retry;

    if (slowpath(sideTableLocked)) sidetable_unlock();

    __c11_atomic_thread_fence(__ATOMIC_ACQUIRE);

    if (performDealloc) {
        //发送一个dealloc消息
        ((void(*)(objc_object *, SEL))objc_msgSend)(this, @selector(dealloc));
    }
    return true;
}

• 判断是否是Nonpointer isa，如果不是，则直接对散列表进行-1操作
• 对extra_rc中的引用计数值进行-1操作，并存储此时的extra_rc状态到carry中
• 如果此时的状态carray为0，则走到underflow流程
• 判断散列表中是否存储了一半的引用计数`
• 如果是，则从散列表中取出存储的一半引用计数，进行-1操作，然后存储到extra_rc中
• 如果此时extra_rc没有值，散列表中也是空的，则直接进行析构

弱引用分析

先来看一个案例

    NSObject *shObjc = [[NSObject alloc] init];
    NSLog(@"%zd---%@---%p",CFGetRetainCount((__bridge CFTypeRef)(shObjc)),shObjc,&shObjc);
    __weak typeof(id) weakObj = shObjc;
    NSLog(@"%zd---%@---%p",CFGetRetainCount((__bridge CFTypeRef)(shObjc)),shObjc,&shObjc);
    NSLog(@"%zd---%@---%p",CFGetRetainCount((__bridge CFTypeRef)(weakObj)),weakObj,&weakObj);

image.png

接下来分析下这个案例

• 第一个NSLog,引用计数等于1这里没有问题
• 第二个NSLog,引用计数等于1这里也没有问题
• 第三个NSLog,引用计数等于2这里就有问题了。我们知道weak修饰的变量，是弱引用，引用计数是不增加的，那么这里为什么等于2呢？

接下来分析下源码，在weak声明处下一个断点

image.png
在汇编处发现了objc_initWeak方法
image.png
查看源码，进入objc_initWeak方法，在这里发现不论是初始化weak,置空还是销毁方法，都调用了storeWeak方法，所以这个方法是个高度封装的方法
image.png

进入storeWeak

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 ? CrashIfDeallocating : ReturnNilIfDeallocating);
        // weak_register_no_lock returns nil if weak store should be rejected

        // Set is-weakly-referenced bit in refcount table.
        if (!newObj->isTaggedPointerOrNil()) {
            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);

    // This must be called without the locks held, as it can invoke
    // arbitrary code. In particular, even if _setWeaklyReferenced
    // is not implemented, resolveInstanceMethod: may be, and may
    // call back into the weak reference machinery.
    callSetWeaklyReferenced((id)newObj);

    return (id)newObj;
}

• 这里有两个入参location （声明的weakObj的指针地址）和newObj （需要绑定的对象）
• 如果haveOld存在，则对弱引用表进行移出，说明haveOld代表的是移出操作。如果haveNew存在,则进行对象注册进弱引用表
  image.png

进入weak_register_no_lock方法

id 
weak_register_no_lock(weak_table_t *weak_table, id referent_id, 
                      id *referrer_id, WeakRegisterDeallocatingOptions deallocatingOptions)
{
    // 对象
    objc_object *referent = (objc_object *)referent_id;
    // 对象的弱引用指针地址
    objc_object **referrer = (objc_object **)referrer_id;
    /// 如果是小对象类型直接返回对象
    if (referent->isTaggedPointerOrNil()) return referent_id;

    // ensure that the referenced object is viable
    // 如果正在析构，进行析构处理
    if (deallocatingOptions == ReturnNilIfDeallocating ||
        deallocatingOptions == CrashIfDeallocating) {
        bool deallocating;
        if (!referent->ISA()->hasCustomRR()) {
            deallocating = referent->rootIsDeallocating();
        }
        else {
            // Use lookUpImpOrForward so we can avoid the assert in
            // class_getInstanceMethod, since we intentionally make this
            // callout with the lock held.
            auto allowsWeakReference = (BOOL(*)(objc_object *, SEL))
            lookUpImpOrForwardTryCache((id)referent, @selector(allowsWeakReference),
                                       referent->getIsa());
            if ((IMP)allowsWeakReference == _objc_msgForward) {
                return nil;
            }
            deallocating =
            ! (*allowsWeakReference)(referent, @selector(allowsWeakReference));
        }

        if (deallocating) {
            if (deallocatingOptions == 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
    //entry 是个数组，里面存储对象
    weak_entry_t *entry;
    // 如果entry 中有这个对象，将这个弱引用指针加入到对象中
    if ((entry = weak_entry_for_referent(weak_table, referent))) {
        append_referrer(entry, referrer);
    } 
    else {
        // 否则创建一个新的entry,将对象加入entry，并将弱引用指针添加到对象中
        weak_entry_t new_entry(referent, referrer);
        weak_grow_maybe(weak_table);
        // 将entry添加到弱引用表中
        weak_entry_insert(weak_table, &new_entry);
    }

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

    return referent_id;
}

• 这里首先将传入的参数转换成objc_object的对象和 弱引用指针
• 如果是小对象类型直接return
• 接下来判断是否正在析构
• 判断entry是否有传入的对象
• 如果有则将这个弱引用指针加入到对象中
• 如果没有，则创建一个entry,并将对象加入到entry中，弱引用指针加入到对象中

查看append_referrer

static void append_referrer(weak_entry_t *entry, objc_object **new_referrer)
{
    if (! entry->out_of_line()) {
        // Try to insert inline.`
        
        // 将 对象放入entry 中空闲的节点
        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.
        weak_referrer_t *new_referrers = (weak_referrer_t *)
            calloc(WEAK_INLINE_COUNT, sizeof(weak_referrer_t));
        // 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());

    // 对 entry 进行扩容
    if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) {
        return grow_refs_and_insert(entry, new_referrer);
    }
    size_t begin = w_hash_pointer(new_referrer) & (entry->mask);
    size_t index = begin;
    size_t hash_displacement = 0;
    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;
    }
    //
    weak_referrer_t &ref = entry->referrers[index];
    ref = new_referrer;
    entry->num_refs++;
}

• 在entry默认是开辟了4个空间
• 遍历ntry->inline_referrers是否有空闲的，如果有直接将new_referrer放入
• 如果没有则要对entry进行扩容

WX20210914-111843@2x.png

由上图得知弱引用表的结构为，且都是1对多的关系
散列表->弱引用表->entry -> 对象->弱引用指针

• 通过SideTable得到weakTable
• 判断weakTable是否有该对象的weak_entry_t
• 如果没有，创建weak_entry_t
• 把referrer 弱引用指针地址加入到weak_entry_t 数组中inline_referrers `
• 如果weak_entry_t空间不够，则进行扩容
• 并把new_entry加入到weak_table中

回到刚开始介绍弱引用表的案例，并在第三个NSLog处打一个断点

image.png
在汇编代码中发现了objc_loadWeakRetained这个方法
image.png

进入objc_loadWeakRetained

id
objc_loadWeakRetained(id *location)
{
    id obj;
    id result;
    Class cls;

    SideTable *table;
    
 retry:
    // fixme std::atomic this load
    obj = *location;
    if (obj->isTaggedPointerOrNil()) return obj;
    
    table = &SideTables()[obj];
    
    table->lock();
    if (*location != obj) {
        table->unlock();
        goto retry;
    }
    
    result = obj;

    cls = obj->ISA();
    if (! cls->hasCustomRR()) {
        // Fast case. We know +initialize is complete because
        // default-RR can never be set before then.
        ASSERT(cls->isInitialized());
        if (! obj->rootTryRetain()) {
            result = nil;
        }
    }
    else {
        // Slow case. We must check for +initialize and call it outside
        // the lock if necessary in order to avoid deadlocks.
        // Use lookUpImpOrForward so we can avoid the assert in
        // class_getInstanceMethod, since we intentionally make this
        // callout with the lock held.
        if (cls->isInitialized() || _thisThreadIsInitializingClass(cls)) {
            BOOL (*tryRetain)(id, SEL) = (BOOL(*)(id, SEL))
                lookUpImpOrForwardTryCache(obj, @selector(retainWeakReference), cls);
            if ((IMP)tryRetain == _objc_msgForward) {
                result = nil;
            }
            else if (! (*tryRetain)(obj, @selector(retainWeakReference))) {
                result = nil;
            }
        }
        else {
            table->unlock();
            class_initialize(cls, obj);
            goto retry;
        }
    }
        
    table->unlock();
    return result;
}

• 传入的location是我们的weakObj
• obj = *location;是weakObj 指向的内存，也就是shObjc

我们在这打个断点，并打印obj的引用计数，这个时候为1

image.png
在经过rootTryRetain方法后引用计数就变为了2
image.png

进入rootTryRetain,发现这里进入了rootRetain，这里我们在引用计数时已经分析了

image.png

• 也就是说弱引用对象也会造成引用计数的增加
• 但是这里和我们平时所掌握的weak修饰的对象，引用计数不会增加，有出入

接下来我们打印多次weakObj，发现引用计数始终为2，这里并没有增加

image.png

是因为objc_loadWeakRetained调用这个方法时,result是一个临时变量，该方法最终也是return result,这也就导致当去打印weakObj的引用计数为2,但是当离开作用域后，就会去释放引用计数

id
objc_loadWeakRetained(id *location)
{
    id obj;
    id result;
    Class cls;

    SideTable *table;
    
 retry:
    // fixme std::atomic this load
    obj = *location;
    ...
    table = &SideTables()[obj];
    ...
    result = obj;
...
    return result;
}

再来看一个案例

    __weak typeof(id) weakSelfObj ;
    
    {
        NSObject *objc = [[NSObject alloc] init];
        weakSelfObj = objc;
        NSLog(@"%zd---%@---%p",CFGetRetainCount((__bridge CFTypeRef)(objc)),objc,&objc);
        
        weakSelfObj = objc;
        NSLog(@"%zd---%@---%p",CFGetRetainCount((__bridge CFTypeRef)(objc)),objc,&objc);
        NSLog(@"%zd---%@---%p",CFGetRetainCount((__bridge CFTypeRef)(weakSelfObj)),weakSelfObj,&weakSelfObj);
        

        
    }
    NSLog(@"%zd---%@---%p",CFGetRetainCount((__bridge CFTypeRef)(weakSelfObj)),weakSelfObj,&weakSelfObj);
    

运行后发现崩溃了

image.png

是因为在作用域内部时，weakSelfObj 和objc指向同一片内存

image.png
出了作用域weakSelfObj指向的内存已经被释放，因为这里weakSelfObj是弱持有指向的内存，objc是强持有内存，但是objc是在作用域内部声明，所以出了作用域指向的内存会被释放，所以这里也就崩溃了
image.png