導(dǎo)語(yǔ)

在上一篇中簡(jiǎn)單分析了 Weak 屬性是如何被存儲(chǔ)，獲取和銷(xiāo)毀的，其中的 SideTable 結(jié)構(gòu)體當(dāng)做黑盒進(jìn)行處理。本文嘗試對(duì) SideTable 的結(jié)構(gòu)進(jìn)行一些分析。

觀察

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 主要分為 3 部分

• weak_table_t: weak 引用的全局 hash 表
• RefcountMap : 引用計(jì)數(shù)的 hash 表
• slock: 保證原子操作的自旋鎖

在 static id storeWeak(id *location, objc_object *newObj) 方法中有

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

可知對(duì)于弱引用變量的保存，主要還是看 weak_table 這個(gè)屬性

測(cè)試代碼

#import <Foundation/Foundation.h>

@interface WeakProperty : NSObject

@property (nonatomic,weak) NSObject *obj;
@property (nonatomic,weak) NSObject *obj2;
@property (nonatomic,weak) NSObject *obj3;
@property (nonatomic,weak) NSObject *obj4;
@property (nonatomic,weak) NSObject *obj5;

@end

@implementation WeakProperty

- (void)dealloc {
    NSLog(@"%s",__func__);
}

@end


int main(int argc, const char * argv[]) {
    @autoreleasepool {
        WeakProperty *property = [[WeakProperty alloc] init];
        NSObject *obj = [[NSObject alloc] init];
        property.obj = obj;
        NSLog(@"%@",property.obj);
        
        // [1]
        property.obj2 = obj;
        
        // [2]
        property.obj3 = obj;
        property.obj4 = obj;
        property.obj5 = obj;
        
        // [3]
        property.obj = nil;        
    }
    return 0;
}

結(jié)構(gòu)體: weak_table_t

weak_table_t 的定義在 objc-weak.h 中

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

說(shuō)明:

• 一個(gè)指向 weak_entry_t 的指針
• size_t(即 unsigned ) 類(lèi)型的 num_entries ，用于描述 hash 表的長(zhǎng)度
• uintptr_t(即 unsigned long) 類(lèi)型的 mask(掩碼)
• uintptr_t(即 unsigned long) 類(lèi)型的 max_hash_displacement

結(jié)構(gòu)體: weak_entry_t

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

在 C++ 中，結(jié)構(gòu)體是由關(guān)鍵詞 struct 定義的一種數(shù)據(jù)類(lèi)型。他的成員和基類(lèi)默認(rèn)為公有的（public）。由關(guān)鍵詞 class 定義的成員和基類(lèi)默認(rèn)為私有的（private）。這是 C++ 中 結(jié)構(gòu)體和類(lèi)僅有的區(qū)別。

類(lèi): DisguisedPtr

// DisguisedPtr<T> acts like pointer type T*, except the 
// stored value is disguised to hide it from tools like `leaks`.
// nil is disguised as itself so zero-filled memory works as expected, 
// which means 0x80..00 is also disguised as itself but we don't care.
// Note that weak_entry_t knows about this encoding.
template <typename T>
class DisguisedPtr {
    uintptr_t value; // unsigned long

    static uintptr_t disguise(T* ptr) {
        return -(uintptr_t)ptr;
    }

    static T* undisguise(uintptr_t val) {
        return (T*)-val;
    }

 public:
    DisguisedPtr() { }
    DisguisedPtr(T* ptr) 
        : value(disguise(ptr)) { }
    DisguisedPtr(const DisguisedPtr<T>& ptr) 
        : value(ptr.value) { }

    DisguisedPtr<T>& operator = (T* rhs) {
        value = disguise(rhs);
        return *this;
    }
    DisguisedPtr<T>& operator = (const DisguisedPtr<T>& rhs) {
        value = rhs.value;
        return *this;
    }

     // 重載了一些指針的運(yùn)算符
    operator T* () const {
        return undisguise(value);
    }
    T* operator -> () const { 
        return undisguise(value);
    }
    T& operator * () const { 
        return *undisguise(value);
    }
    T& operator [] (size_t i) const {
        return undisguise(value)[i];
    }

    // pointer arithmetic operators omitted 
    // because we don't currently use them anywhere
};

// The address of a __weak variable.
// These pointers are stored disguised so memory analysis tools
// don't see lots of interior pointers from the weak table into objects.
typedef DisguisedPtr<objc_object *> weak_referrer_t;

小結(jié)

weak_entry_t 包含一個(gè) DisguisedPtr<objc_object>,Disguised 是偽裝的意思，根據(jù)注釋可知，可以將 DisguisedPtr<T> 當(dāng)成 T * 指針類(lèi)型即可，在當(dāng)前場(chǎng)景可看作是一個(gè)指向 objc_object 的指針類(lèi)型

weak_referrer_t 是 DisguisedPtr<objc_object *> 可以看成是 objc_object 指針的地址

接著是一個(gè) union ，out_of_line_ness 與 inline_referrers[1] 共用了低 2 位，因?yàn)?/p>

// 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

注釋說(shuō)明了 DisuisedPtr 的低 2 位不是 0b00 就是 0b11，所以要表示 out-of-line 只能使用 out_of_line_ness == 0b10 (當(dāng) out_of_line_ness 為 0b01 或 0b10 會(huì)分別得到 false 和 true )

num_refs 占 30 (32位系統(tǒng)) / 62(64位系統(tǒng)) 位
mask 和 max_hash_displacement 在 weak_table_t 中也有。

out_of_line() 方法在上面算是已經(jīng)說(shuō)過(guò)了

weak_entry_t& operator=(const weak_entry_t& other) {...} 重載運(yùn)算符 =

The memcpy() function copies n bytes from memory area src
to memory area dest. The memory areas may not overlap.
Use memmove(3) if the memory areas do overlap.

從參數(shù) other 所指的內(nèi)存地址的起始位置開(kāi)始拷貝 sizeof(other) 字節(jié)到 this 指針指向的當(dāng)前對(duì)象的起始地址。

weak_entry_t(objc_object *newReferent, objc_object **newReferrer) : referent(newReferent)

: referent(newReferent) 是初始化列表，代表用參數(shù) newReferent來(lái)初始化結(jié)構(gòu)體中的 referent 屬性。聯(lián)合類(lèi)型中的 inline_referrers[0] 接收參數(shù) newReferrer ，并將剩下的 1，2，3 都置為 nil

函數(shù): weak_register_no_lock

注釋 [2] & [3]

/// Adds an (object, weak pointer) pair to the weak table.
/// 添加一個(gè) (對(duì)象，弱引用指針）到 weak hash 表中
id weak_register_no_lock(weak_table_t *weak_table, id referent, 
                         id *referrer, bool crashIfDeallocating);

具體實(shí)現(xiàn)如下:

/** 
 * Registers a new (object, weak pointer) pair. Creates a new weak
 * object entry if it does not exist.
 * 
 * @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;

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

弱引用屬性 obj 在函數(shù) weak_register_no_lock 中傳遞給行參 referent_id， 賦值給局部變量 referent ，location 傳遞給形參 referrer_id，賦值給局部變量 referrer。

經(jīng)過(guò)一些檢查，比如是否允許弱引用，弱引用對(duì)象是否可用。

/** 
 * Return the weak reference table entry for the given referent. 
 * If there is no entry for referent, return NULL. 
 * Performs a lookup.
 *
 * @param weak_table 
 * @param referent The object. Must not be nil.
 * 
 * @return The table of weak referrers to this object. 
 */
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];
}

根據(jù) referent 為 key ，在 weak_table 中通過(guò)遍歷 weak_entries 數(shù)組，對(duì)referent 屬性值進(jìn)行比較的方式來(lái)查找元素，未找到，走 else

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

執(zhí)行 weak_entry_t 結(jié)構(gòu)體的初始化

通過(guò)強(qiáng)轉(zhuǎn)操作來(lái)偽裝指針。接收 newReferrer 即 referrer 為 inline_referrers[0] 在這里 *referrer 等于 nil 所以 inline_referres 數(shù)組元素全指向 nil，因?yàn)槭菬o(wú)符號(hào)長(zhǎng)整數(shù)，因此就是 0。

函數(shù): weak_grow_maybe

當(dāng)弱引用的 hash 表的空間使用率達(dá)到 3/4 后，擴(kuò)充 hash 表

// 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) {
        weak_resize(weak_table, old_size ? old_size*2 : 64);
    }
}

函數(shù): weak_entry_insert

添加元素到弱引用的 hash 表中

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

獲取 new_entry 的 referent 屬性，即弱引用的 obj 屬性，以其地址的無(wú)符號(hào)長(zhǎng)整數(shù)取相反數(shù)來(lái)做參數(shù)，通過(guò)移位與位移進(jìn)行 hash 操作，通過(guò) weak_table->mask(63 = 0b111111) 掩碼保留 hash 操作后的低 6 位( 64 位系統(tǒng)),作為索引，接下來(lái)用 while (weak_entries[index].referent != nil) {...} ，解決 hash 碰撞的問(wèn)題。然后添加到 hash 表中，修改表的長(zhǎng)度

效果如上圖所示，static id storeWeak(id *location, objc_object *newObj) 的 location 和 newObj 分別被保存到 weak_table_t 結(jié)構(gòu)體的 referent ，inline_referrers 數(shù)組的首位。

查找 referent 是否存在的條件是

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

注釋 [2] & [3]

進(jìn)入 append_referrer 函數(shù)后

if (! entry->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;
       }
   }

因?yàn)?entry-> out_of_line() 等于 false 會(huì)嘗試添加到 (entry->inline_referrers 數(shù)組中。

取消 [2] 的注釋?zhuān)驗(yàn)橐呀?jīng)達(dá)到 4 個(gè)，所以在 obj5 時(shí)，會(huì)擴(kuò)充。

// 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;

會(huì)設(shè)置 entry->out_of_line_ness 為 REFERRERS_OUT_OF_LINE

結(jié)合注釋

/**
 * 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.
 */

可知當(dāng) weak 變量引用數(shù)量不多于 4 個(gè)時(shí)，會(huì)使用數(shù)組方式進(jìn)行存儲(chǔ)，而多于 4 個(gè)后會(huì)用 hash 表的方式進(jìn)行存儲(chǔ)。

函數(shù): weak_unregister_no_lock

/// Removes an (object, weak pointer) pair from the weak table.
/// 從 weak hash 表中移除一個(gè)(對(duì)象，弱引用指針）
void weak_unregister_no_lock(weak_table_t *weak_table, id referent, id *referrer);

具體實(shí)現(xiàn)如下:

/** 
 * 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))) {
        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.
}

同樣是使用 weak_entry_for_referent 函數(shù)查找弱引用是否存在

注釋 [1] & [2] ，取消注釋 [3]

/** 
 * 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_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) {
            ...
            return;
        }
    }
    entry->referrers[index] = nil;
    entry->num_refs--;
}

移除時(shí)，是以 referrer 屬性來(lái)比較，發(fā)現(xiàn)地址相同，將其置為 nil 來(lái)實(shí)現(xiàn)移除的效果。

函數(shù): weak_clear_no_lock

/// Called on object destruction. Sets all remaining weak pointers to nil.
/// 在對(duì)象調(diào)用析構(gòu)方法時(shí)，設(shè)置所有留下的弱引用指針為nil
void weak_clear_no_lock(weak_table_t *weak_table, id referent);

具體實(shí)現(xiàn)如下:

/** 
 * Called by dealloc; nils out all weak pointers that point to the 
 * provided object so that they can no longer be used.
 * 
 * @param weak_table 
 * @param referent The object being deallocated. 
 */
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);
}

會(huì)被 dealloc 調(diào)用，根據(jù)注釋和代碼可知同樣以 referent 為 key 遍歷,然后依次將置為 nil，但是測(cè)試時(shí)，走的都是 if (entry == nil) 然后直接 return。

總結(jié)

弱引用查找根據(jù) referent 屬性，首次會(huì)被存儲(chǔ)到 weak_table_t 結(jié)構(gòu)體 referent 和 inline_referrers[0],當(dāng)繼續(xù)添加時(shí)，如果引用次數(shù)不大于 4 個(gè)保存在數(shù)組inline_referrers 中，當(dāng)超過(guò) 4 個(gè)后以 hash 表的形式進(jìn)行存儲(chǔ)。移除時(shí)，根據(jù) referrer 從 inline_referrers 中移除。

參考

1. int - What is size_t in C? - Stack Overflow
2. wiki - C++類(lèi)
3. wiki - 位段
4. Linux Programmer's Manual memcpy
5. inline bool objc_object::isTaggedPointer(); How does the function work?
6. PHP哈希表碰撞攻擊原理
7. wiki - 掩碼
8. wiki - 哈希表
9. When to use reinterpret_cast?
10. OSObject
11. c++ operator操作符的兩種用法：重載和隱式類(lèi)型轉(zhuǎn)換，string轉(zhuǎn)其他基本數(shù)據(jù)類(lèi)型的簡(jiǎn)潔實(shí)現(xiàn)string_cast
12. c++中冒號(hào)（:）和雙冒號(hào)（::）的用法
13. ARC 引用計(jì)數(shù)之weak