iOS弱引用表 SideTable weak

一、DisguisedPtr伪装指针类介绍

主要是用来把对象的指针映射到long类型的数值,来保存对象的指针,至于为什么不直接保存指针,估计是处于安全考虑,
防止空指针造成的坏的影响;

地层大量使用了DisguisedPtr,DisguisedPtr也不是很复杂;

可以看出DisguisedPtr是个模版类,可以看作是iOS中的范型,
里面定义了一个属性value,用来保存处理后的对象指针;是个unsigned long类型,
和其他几个函数;

template 
class DisguisedPtr {

    uintptr_t value;//用来保存处理后的对象指针;是个unsigned long类型,


    static uintptr_t disguise(T* ptr) {
    //把对象的指针转成unsigned long类型
        return -(uintptr_t)ptr;
    }

    static T* undisguise(uintptr_t val) {
    //还原对象指针
        return (T*)-val;
    }

 public:

    DisguisedPtr() { }
    //构造函数,通过disguise函数转换之后,把对象指针保存在value中
    DisguisedPtr(T* ptr) 
        : value(disguise(ptr)) { }
    DisguisedPtr(const DisguisedPtr& ptr) 
        : value(ptr.value) { }

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

//重载了几个运算符,使用undisguise函数转换后,用来获取保存的对象指针,
    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
};

二、StripedMap介绍
StripedMap中默认保存8张表,使用哈希计数对象对应的表

enum { CacheLineSize = 64 };

// StripedMap is a map of void* -> T, sized appropriately 
// for cache-friendly lock striping. 
// For example, this may be used as StripedMap
// or as StripedMap where SomeStruct stores a spin lock.
//保存8张SideTable表,通过哈希对象的指针,确定保存的表的位置,
template
class StripedMap {
#if TARGET_OS_IPHONE && !TARGET_OS_SIMULATOR
    enum { StripeCount = 8 };//苹果手机iOS系统默认8张
#else
    enum { StripeCount = 64 };
#endif

    //里面又定义一个结构体,value属性就是SideTable,使用64字节对齐
    struct PaddedT {
        T value alignas(CacheLineSize);
    };

    //保存8张表的数组
    PaddedT array[StripeCount];

    //通过哈希对象的指针计算出array的索引位置
    static unsigned int indexForPointer(const void *p) {
        uintptr_t addr = reinterpret_cast(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>(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对象所占的内存长度
//所以这个数据也可以看作是StripedMap对象
alignas(StripedMap) static uint8_t 
    SideTableBuf[sizeof(StripedMap)];
//初始化函数,StripedMap保存了8张SideTable表
static void SideTableInit() {
    new (SideTableBuf) StripedMap();
}
//获取StripedMap对象,一般都使用这个函数获取StripedMap对象,
//从而操作引用计数和所引用计数
static StripedMap& SideTables() {
    return *reinterpret_cast*>(SideTableBuf);
}

三、weak_table_t
用来保存弱引用,是个结构体,里面有4个属性,

struct weak_table_t {
    weak_entry_t *weak_entries;//保存每个对象的弱引用的数组,
    size_t    num_entries;//数组的元素个数
    uintptr_t mask;//weak_entries数组的长度-1,不是数组元素个数-1;因为数组的长度可能是100,但是元素个数可能是9个;
    这个属性另一个作用是参与到哈希运算,得到对象的对应的数组索引index;
    uintptr_t max_hash_displacement;最大冲突或者异常次数,如果运算过程中冲突或者异常次数超过这个值max_hash_displacement则有问题
};

四、weak_entry_t

弱引用实体,一个对象对应一个weak_entry_t,保存对象的弱引用;
保存弱应用的是个联合体,当弱引用小于等于4个的时候,直接用inline_referrers数组保存
大于四个时用referrers动态数组

typedef DisguisedPtr weak_referrer_t;
#if __LP64__
#define PTR_MINUS_2 62
#else
#define PTR_MINUS_2 30
#endif
#define WEAK_INLINE_COUNT 4
#define REFERRERS_OUT_OF_LINE 2

struct weak_entry_t {
    DisguisedPtr referent;//被弱引用的对象
    //
    union {
        struct {
            weak_referrer_t *referrers;//动态数组保存弱引用的指针
            uintptr_t        out_of_line_ness : 2;//记录是否需要使用动态数组
            uintptr_t        num_refs : PTR_MINUS_2;//动态数组中的元素个数
            uintptr_t        mask;//动态数组的长度-1,作用同weak_table_t的mask
            uintptr_t        max_hash_displacement;//最大冲突或者异常次数,如果运算过程中冲突或者异常次数超过这个值max_hash_displacement则有问题
        };
        struct {
            //初始化时默认使用的数组
            weak_referrer_t  inline_referrers[WEAK_INLINE_COUNT];
        };
    };

//判断是否大于4个,师傅需要动态数组
    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;
    }
//构造函数,里面默认使用inline_referrers数组,当数据大于4个时,会改成动态数组referrers
    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;
        }
    }
};

五、下面介绍的是对弱引用的操作函数,包括添加,删除弱引用
下面是objc-weak.mm文件全部内容

#include "objc-private.h"

#include "objc-weak.h"

#include 
#include 
#include 
#include 

//获取weak_entry_t保存的弱引用个数,保存在mask中的时候会-1,现在取出来的时候再+1,就是弱引用数组的长度了
#define TABLE_SIZE(entry) (entry->mask ? entry->mask + 1 : 0)

//提前声明函数,c语法
static void append_referrer(weak_entry_t *entry, objc_object **new_referrer);

//错误处理函数
BREAKPOINT_FUNCTION(
    void objc_weak_error(void)
);
//错误处理函数
static void bad_weak_table(weak_entry_t *entries)
{
    _objc_fatal("bad weak table at %p. This may be a runtime bug or a "
                "memory error somewhere else.", entries);
}


 //哈希运算,把对象的指针进行哈希运算,用来计算哈希表的key
static inline uintptr_t hash_pointer(objc_object *key) {
    return ptr_hash((uintptr_t)key);
}


 //哈希运算,把对象的指针进行哈希运算,用来计算哈希表的key
static inline uintptr_t w_hash_pointer(objc_object **key) {
    return ptr_hash((uintptr_t)key);
}


 //用来对weak_entry_t中的数组进行扩容,
 //如果数组元素大于4个,或者大于数组长度的3/4时,调用此函数进行扩容;
 //数组扩容后的长度是原来长度的1倍
__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;//进行扩容,长度变成原来的2倍

    size_t num_refs = entry->num_refs;//原来的弱引用个数
    weak_referrer_t *old_refs = entry->referrers;//获取原来的数组指针,暂时保存在old_refs中
    entry->mask = new_size - 1;//把新的长度-1保存在mask,;
    
    entry->referrers = (weak_referrer_t *)
        calloc(TABLE_SIZE(entry), sizeof(weak_referrer_t));//重新创建一块内存,用来存储弱引用指针,并设置给referrers属性
    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]);
            num_refs--;
        }
    }
    // Insert
    append_referrer(entry, new_referrer);把新的弱引用保存新的数组中
    if (old_refs) free(old_refs);//最后释放旧的弱引用内存
}


 //添加新的弱引用指针
static void append_referrer(weak_entry_t *entry, objc_object **new_referrer)
{
    //先判断弱引用数组是否大于大于4个,如果不大于4,就走这里
    if (! entry->out_of_line()) {

        // Try to insert inline.
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
        //先判断数组中对应的元素是否为nil,如果是nil,说明弱引用的指针还不到4个,就直接保存,然后return;
        //如果都不是nil,说明默认的数组已经存了4个元素了,就进行下一步;
            if (entry->inline_referrers[i] == nil) {
            //直接保存到默认的固定长度为4的数组中
                entry->inline_referrers[i] = new_referrer;
                //返回
                return;
            }
        }

        //到这里,说明弱引用的数组超过4个了,
        //从新申请一块内存,用来保存弱引用指针;
        weak_referrer_t *new_referrers = (weak_referrer_t *)
            calloc(WEAK_INLINE_COUNT, sizeof(weak_referrer_t));
        
        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;//最大异常次数0
    }

    assert(entry->out_of_line());

    //在这里判断是否需要扩容
    //如果元素个数大于数组长度的3/4时,就需要扩容
    if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) {
    //调这个方法去扩容
        return grow_refs_and_insert(entry, new_referrer);
    }
    //通过哈希计算对象的指针对应的key,& (entry->mask)这个运算是为了防止计算的key超过数组的长度
    size_t begin = w_hash_pointer(new_referrer) & (entry->mask);
    size_t index = begin;//保存哈希后的key
    size_t hash_displacement = 0;//保存最大异常次数
    
    //这一步是计算,找到一个索引为index的位置上元素为nil的空位置,用来保存这个对象的弱引用指针
    while (entry->referrers[index] != nil) {
        //如果不等nil,说明有这个key,然后就hash_displacement+1,
        hash_displacement++;
        //然后在把key+1计算新的key,直到找到空的位置,否则下面抱错
        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++;
}


 //删除弱引用指针,分为从固定数组删除还是从动态数组删除
static void remove_referrer(weak_entry_t *entry, objc_object **old_referrer)
{
	//如果弱引用指针的个数小于等于4个,直接从固定数组中删除
    if (! entry->out_of_line()) {
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            if (entry->inline_referrers[i] == old_referrer) {
            //在这里找到指针,直接设置nil
                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;
    }
//如果大于4,就需要从动态数组删除

	//哈希计算出对象的key
    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;
        }
    }
    //找到之后,直接设置nil,并把num_refs减1,说明元素个数少一个
    entry->referrers[index] = nil;
    entry->num_refs--;
}


 //当一个对象第一次被弱引用时,需要把把生成的weak_entry_t保存在weak_table_t表中
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);

	//哈希referent计算出对象的key,& (weak_table->mask)是为了防止key超出弱引用数组的长度
    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;
    }
}

//修改弱引用表的大小,因为多出来的用不到表,太占内存,可以清除掉不用的表
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;//保存数组长度,保存时进行了-1,获取时需要+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);
    }
}

// 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.
    //如果弱引用表中的元素个数大于3/4时,就扩容一倍,
    if (weak_table->num_entries >= old_size * 3 / 4) {
    //调这个方法扩容
        weak_resize(weak_table, old_size ? old_size*2 : 64);
    }
}

// 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.
    //如果弱引用表的长度大于1024,并且元素只有不到1/16,就进行缩减,把空表清除
    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
    }
}



 //删除表,当一个对象释放时,没有弱引用了,就把这个表删掉
static void weak_entry_remove(weak_table_t *weak_table, weak_entry_t *entry)
{
    // remove entry
    //如果弱引用小于4,直接释放
    if (entry->out_of_line()) free(entry->referrers);
    bzero(entry, sizeof(*entry));//清空数据

    weak_table->num_entries--;//减1
    //判断是否需要缩减表
    weak_compact_maybe(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;
    //通过循环找到key
    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];
}


 //注销这个对象的弱引用表
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.
}


 //给一个对象添加新的弱引用指针
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;

    //前面这些判断是不是一个OC对象
    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;
}


#if DEBUG
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);
}
#endif



 //清空一个对象的所有弱引用指针,对象释放的时候会调用这个方法
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 %pn", 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) {
        //通过循环,把弱引用指针设置为nil
            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);
}