Objective-C 对象的内存管理-SideTables

前言

    在Objective-C 对象的内存管理-引用计数的管理中操作引用计数时，在下面情况都使用到了sidetable。

• 未开启 isa 优化的情况下，用到了 sidetable_tryRetain 和 sidetable_release 函数
• 开启 isa 优化的情况下，用到了 sidetable_addExtraRC_nolock 和sidetable_subExtraRC_nolock 函数。

查看 其中sidetable_tryRetain 源码函数如下：

bool
objc_object::sidetable_tryRetain()
{
#if SUPPORT_NONPOINTER_ISA
    ASSERT(!isa.nonpointer);
#endif
    SideTable& table = SideTables()[this];

    // NO SPINLOCK HERE
    // _objc_rootTryRetain() is called exclusively by _objc_loadWeak(), 
    // which already acquired the lock on our behalf.

    // fixme can't do this efficiently with os_lock_handoff_s
    // if (table.slock == 0) {
    //     _objc_fatal("Do not call -_tryRetain.");
    // }

    bool result = true;
    auto it = table.refcnts.try_emplace(this, SIDE_TABLE_RC_ONE);
    auto &refcnt = it.first->second;
    if (it.second) {
        // there was no entry
    } else if (refcnt & SIDE_TABLE_DEALLOCATING) {
        result = false;
    } else if (! (refcnt & SIDE_TABLE_RC_PINNED)) {
        refcnt += SIDE_TABLE_RC_ONE;
    }
    
    return result;
}

    可以看到上面函数使用 SideTables 获取 SideTable 从而操作引用计数。那么 SideTables 和 SideTable 都是什么呢？

SideTables

    为了管理所有对象的引用计数和 weak 指针，苹果创建了一个全局的 SideTables，查看 SideTables 源码如下：

static objc::ExplicitInit<StripedMap<SideTable>> SideTablesMap;

static StripedMap<SideTable>& SideTables() {
    return SideTablesMap.get();
}

    通过上面代码可以看到，SideTablesMap 是 一个 StripedMap，那么 StripedMap 又是什么呢？

StripedMap

    在 objc-private.h 中查看 StripedMap 源码如下：

// 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 是一个泛类型：template<typename T> class StripedMap，StripedMap 中的 PaddedT array在 iPhone 下它是固定长度为 8 的哈希数组，在 Mac 下是固定长度为 64 的哈希数组。
    StripedMap 正是根据对象的指针通过 indexForPointer 哈希函数获取索引，从 array 中找到对应存储的泛类型 value。阅读其内部实现然后从数据结构角度看的话，它其实是作为一个 Key 是 void *，Value 是 T 的 hash 表来用的，并且 StripedMap 提供了锁的操作，用于保证线程安全。
    因此,SideTables 对应类型是: StripedMap<SideTable>，SideTables 其实是一个全局的 Hash 表，在 array 中存储 SideTable，它使用结构体的内存地址当它的 key，并且提供了一些便捷的锁操作方法。

SideTable 结构体

SideTable 中存储着引用计数表以及弱引用表。SideTable 的结构体源码如下：

// Template parameters. 模版参数
enum HaveOld { DontHaveOld = false, DoHaveOld = true }; // 是否有旧值
enum HaveNew { DontHaveNew = false, DoHaveNew = true }; // 是否有新值

struct SideTable {
    spinlock_t slock; // 每张 SideTable 都自带一把锁，而这把锁也对应了上面抽象类型 T 必须为 StripedMap 提到的一些锁的接口函数
    RefcountMap refcnts; // 管理对象的引用计数
    weak_table_t weak_table; // 以 object ids 为 keys，以 weak_entry_t 为 values 的哈希表，如果 object ids 有弱引用存在，则可从中找到对象的 weak_entry_t。
    
    // 构造函数，只做了一件事把 weak_table 的空间置为 0
    SideTable() {
        // 把从 &weak_table 位置开始的长度为 sizeof(weak_table) 的内存空间置为 0
        memset(&weak_table, 0, sizeof(weak_table));
    }

    // 析构函数（不能进行析构）
    ~SideTable() {
        // 看到 SidetTable 是不能析构的，如果进行析构则会直接终止运行
        _objc_fatal("Do not delete SideTable.");
    }
    
    // 三个函数正对应了 StripedMap 中模版抽象类型 T 的接口要求，三个函数的内部都是直接调用 slock 的对应函数
    void lock() { slock.lock(); }
    void unlock() { slock.unlock(); }
    void forceReset() { slock.forceReset(); }

    // Address-ordered lock discipline for a pair of side tables.
    
    // HaveOld 和 HaveNew 分别表示 lock1 和 lock2 是否存在，
    // 表示 __weak 变量是否指向有旧值和目前要指向的新值。
    
    // lock1 代表旧值对象所处的 SideTable 
    // lock2 代表新值对象所处的 SideTable
    
    // lockTwo 是根据谁有值就调谁的锁，触发加锁 (C++ 方法重载)，
    // 如果两个都有值，那么两个都加锁，并且根据谁低，先给谁加锁，然后另一个后加锁
    template<HaveOld, HaveNew>
    static void lockTwo(SideTable *lock1, SideTable *lock2);
    
    // 同上，对 slock 解锁
    template<HaveOld, HaveNew>
    static void unlockTwo(SideTable *lock1, SideTable *lock2);
};

// 源文件中下面是 lockTwo 和 unlockTwo 函数根据模版参数的重载，很清晰，这里就不再贴代码了。

spinlock_t slock

    SideTable 本身有一把自旋锁，spinlock_t slock。它的作用是在操作引用技术的时候对 SideTable 加锁，避免数据错误。对于引用计数的操作其实是非常快的。所以选择了虽然不是那么高级但是确实效率高的自旋锁。

自旋锁，比较适用于锁使用者保持锁时间比较短的情况。正是由于自旋锁使用者一般保持锁时间非常短，因此选择自旋而不是睡眠是非常必要的，自旋锁的效率远高于互斥锁。

RefcountMap refcnts

    RefcountMap refcnts 用来存储对象的引用计数(仅在未开启 isa 优化 或 在 isa 优化情况下 extra_rc 溢出时才会用到)。RefcountMap 声明源码如下：

typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,RefcountMapValuePurgeable> RefcountMap;

    可以看到 RefcountMap 其实是个 C++ 的 DenseMap。

weak_table_t weak_table

     weak_table_t 是用于维护 weak 指针的结构体，源码如下：

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 数组 与 num_entries 数值。

    weak_table_t 的 hash 定位操作函数是 weak_entry_for_referent ，通过遍历查找对应的 weak_entry_t，源码如下：

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

weak_entry_t

    weak_entry_t 类型对应了一个对象的弱引用信息。 weak_entry_t结构如下：

typedef DisguisedPtr<objc_object *> weak_referrer_t;
struct weak_entry_t {
    // referent 中存放的是化身为整数的 objc_object 实例的地址，下面保存的一众弱引用变量都指向这个 objc_object 实例
    DisguisedPtr<objc_object> referent;
    
    // 当指向 referent 的弱引用个数小于等于 4 时使用 inline_referrers 数组保存这些弱引用变量的地址，
    // 大于 4 以后用 referrers 这个哈希数组保存。
    
    // 共用 32 个字节内存空间的联合体
    union {
        struct {
            weak_referrer_t *referrers; // 保存 weak_referrer_t 的哈希数组
            
            // out_of_line_ness 和 num_refs 构成位域存储，共占 64 位
            uintptr_t        out_of_line_ness : 2; // 标记使用哈希数组还是 inline_referrers 保存 weak_referrer_t
            uintptr_t        num_refs : PTR_MINUS_2; // 当前 referrers 内保存的 weak_referrer_t 的数量
            uintptr_t        mask; // referrers 哈希数组总长度减 1，会参与哈希函数计算
            
            // 可能会发生 hash 冲突的最大次数，用于判断是否出现了逻辑错误，（hash 表中的冲突次数绝对不会超过该值）
            // 该值在新建 weak_entry_t 和插入新的 weak_referrer_t 时会被更新，它一直记录的都是最大偏移值
            uintptr_t        max_hash_displacement;
        };
        struct {
            // out_of_line_ness 和 inline_referrers[1] 的低两位的内存空间重合
            // 长度为 4 的 weak_referrer_t（Dsiguised<objc_object *>）数组
            weak_referrer_t  inline_referrers[WEAK_INLINE_COUNT];
        };
    };
    
    // 返回 true 表示使用 referrers 哈希数组 false 表示使用 inline_referrers 数组保存 weak_referrer_t
    bool out_of_line() {
        return (out_of_line_ness == REFERRERS_OUT_OF_LINE);
    }
    
    // weak_entry_t 的赋值操作，直接使用 memcpy 函数拷贝 other 内存里面的内容到 this 中，
    // 而不是用复制构造函数什么的形式实现，应该也是为了提高效率考虑的...
    weak_entry_t& operator=(const weak_entry_t& other) {
        memcpy(this, &other, sizeof(other));
        return *this;
    }

    // weak_entry_t 的构造函数
    
    // newReferent 是原始对象的指针，
    // newReferrer 则是指向 newReferent 的弱引用变量的指针。
    
    // 初始化列表 referent(newReferent) 会调用: DisguisedPtr(T* ptr) : value(disguise(ptr)) { } 构造函数，
    // 调用 disguise 函数把 newReferent 转化为一个整数赋值给 value。
    weak_entry_t(objc_object *newReferent, objc_object **newReferrer)
        : referent(newReferent)
    {
        // 把 newReferrer 放在数组 0 位，也会调用 DisguisedPtr 构造函数，把 newReferrer 转化为整数保存
        inline_referrers[0] = newReferrer;
        // 循环把 inline_referrers 数组的剩余 3 位都置为 nil
        for (int i = 1; i < WEAK_INLINE_COUNT; i++) {
            inline_referrers[i] = nil;
        }
    }
};

• referent
  对象的地址。前面循环遍历查找的时候就是判断目标地址是否和它相等。

• referrers
  可变数组，里面保存着所有指向这个对象的弱引用的地址。当这个对象被释放的时候，referrers 里的所有指针都会被设置成 nil

• inline_referrers
  容量为 WEAK_INLINE_COUNT 的数组，目前 WEAK_INLINE_COUNT 等于 4。 默认情况下用它来存储弱引用的指针。

     weak_entry_t 的哈希数组内存储的数据是 weak_referrer_t，实质上是弱引用变量的地址，即 objc_object **new_referrer，通过操作指针的指针，就可以使得弱引用变量在对象析构后指向 nil。这里必须保存弱引用变量的地址，才能把它的指向置为 nil。