数据结构的魅力｜iOS@synchronized源码解析与单向链表的妙用

前言

阅读源码一方面能够使我们认识到一些东西的实现原理，更能从中看到一些精妙的设计。本文就将结合 @synchronized 源码感受苹果工程师对单向链表的妙用。本文基于 objc4-818.2 源码。

?

• Wechat: RyukieW
• 微信公众号：LabLawliet
• ? 技术文章归档
• ? Github

一、 定位到 synchronized 相关源码

那么 synchronized 是怎么实现的呢？在 Xcode 中 @synchronized 是无法直接点进去的。我们尝试在 objc 源码中找线索。

这里找到了成对出现的 objc_sync_exit / objc_sync_enter。怀疑他就是 @synchronized 的底层实现。那么如何来验证一下呢？

这里我决定将 OC 代码还原为 C++ 代码来看看。

通过 clang -rewrite-objc main.m -o main.cpp 来进行还原。定位到 main 函数，其中的确成对出现了 objc_sync_exit / objc_sync_enter。

int main(int argc, const char * argv[]) {
    /* @autoreleasepool */ { __AtAutoreleasePool __autoreleasepool;
        NSObject *obj = ((NSObject *(*)(id, SEL))(void *)objc_msgSend)((id)objc_getClass("NSObject"), sel_registerName("new"));
        { id _rethrow = 0; id _sync_obj = (id)obj; objc_sync_enter(_sync_obj);
            try {
                struct _SYNC_EXIT { _SYNC_EXIT(id arg) : sync_exit(arg) {}
                    ~_SYNC_EXIT() {objc_sync_exit(sync_exit);}
                    id sync_exit;
                } _sync_exit(_sync_obj);
                
                NSLog((NSString *)&__NSConstantStringImpl__var_folders_py_7v1wvf813z5bmw0hr97yplwc0000gn_T_main_7d2c6c_mi_0);
            } catch (id e) {_rethrow = e;}
            { struct _FIN { _FIN(id reth) : rethrow(reth) {}
                ~_FIN() { if (rethrow) objc_exception_throw(rethrow); }
                id rethrow;
            } _fin_force_rethow(_rethrow);}
        }
        
    }
    return 0;
}
复制代码

接下来我们可以放心的在 objc 源码中继续探索了。

二、 objc_sync_enter

int objc_sync_enter(id obj)
{
    int result = OBJC_SYNC_SUCCESS;
    if (obj) {
        // 通过传入的 obj 创建一个 SyncData
        SyncData* data = id2data(obj, ACQUIRE);
        ASSERT(data);
        data->mutex.lock();
    } else {
        /// 如果传入的 obj 为空的话什么都不做
        // @synchronized(nil) does nothing
        if (DebugNilSync) {
            _objc_inform("NIL SYNC DEBUG: @synchronized(nil); set a breakpoint on objc_sync_nil to debug");
        }
        objc_sync_nil();
    }
    return result;
}
复制代码

• 这里会利用传入的 obj 通过 id2data 获取一个 SyncData 结构体指针
• 如果传入的 obj 为空，什么都不做

三、 objc_sync_exit

int objc_sync_exit(id obj)
{
    int result = OBJC_SYNC_SUCCESS;
    if (obj) {
        SyncData* data = id2data(obj, RELEASE); 
        if (!data) {
            result = OBJC_SYNC_NOT_OWNING_THREAD_ERROR;
        } else {
            // 尝试解锁
            bool okay = data->mutex.tryUnlock();
            if (!okay) {
                // 解锁失败
                result = OBJC_SYNC_NOT_OWNING_THREAD_ERROR;
            }
        }
    } else {
        // @synchronized(nil) does nothing
    }
    return result;
}
复制代码

四、 SyncData 的数据结构

typedef struct alignas(CacheLineSize) SyncData {
    struct SyncData* nextData;
    DisguisedPtr<objc_object> object;
    int32_t threadCount;  // number of THREADS using this block
    recursive_mutex_t mutex;
} SyncData;
复制代码

• nextData
  • SyncData 指针，可见是个 单向链表 的结构
  • 这个结构是 synchronized 可嵌套使用的关键点，后续会讲到
• object
  • 传入的 obj
• threadCount
  • 有多少个线程在使用当前 block
• mutex
  • 递归锁

五、 id2data

static SyncData* id2data(id object, enum usage why)
{
    spinlock_t *lockp = &LOCK_FOR_OBJ(object);
    SyncData **listp = &LIST_FOR_OBJ(object);
    SyncData* result = NULL;

    。。。
}
复制代码

5.1 找到 object 对应的数据结构

• LOCK_FOR_OBJ
  • 找到对应的锁 spinlock_t
• LIST_FOR_OBJ
  • 找到对应的 SyncData 的指针的指针

通过源码是从一个全剧静态哈希表 static StripedMap<SyncList> sDataLists 中获取的。

5.2 sDataLists 全剧静态哈希表

通过源码可以发现，貌似一个Hash表的结构。

容量大小 StripeCount

真机容量为 8，其他为 64

#if TARGET_OS_IPHONE && !TARGET_OS_SIMULATOR
    enum { StripeCount = 8 };
#else
    enum { StripeCount = 64 };
#endif
复制代码

范型容器 array

这里容器的类型为 SyncList

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

PaddedT array[StripeCount];
复制代码

容器元素 SyncList

struct SyncList {
    SyncData *data;
    spinlock_t lock;
    constexpr SyncList() : data(nil), lock(fork_unsafe_lock) { }
};
复制代码

哈希下标算法 indexForPointer

• 地址 addr 右移 4位 得到 A
• 地址 addr 右移 9位 得到 B
• A 异或 B 得到 C
• 用 C 模 容量 得到下标
  • 保证了不会越界

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

思考一下：下标冲突了怎么办？

哈希冲突：拉链法（单向链表）

下面的图很好的描绘了哈希冲突时的情况

5.3 查找TLS快速缓存（如果支持的话）

通过 线程局部存储（TLS：Thread Local Storage） 查找快速缓存。

5.4 fetch_cache 查找缓存

内部操作和 查找TLS快速缓存 基本一致。

5.5 未命中缓存

遍历链表查找

5.6 第一次进入 及 链表操作

这里通过头插法插入解决哈希冲突

到这里再回头看拉链法的那张图是否就更清楚了？

六、 SyncCacheItem

作为缓存的数据结构，其中的 lockCount 代表了，这个一个 Block 在 当前线程 锁了多少次（即嵌套锁）。

typedef struct {
    SyncData *data;
    unsigned int lockCount;  // number of times THIS THREAD locked this block
} SyncCacheItem;
复制代码

七、 总结

这里的设计十分巧妙，刚开始发现在真机下容器的大小只有 8 的时候还在想，难道最多只能有 8 个锁么？结果其中还存在单向链表的数据结构，同时使用单向链表还解决了哈希冲突。赞叹真的是很精妙的设计呀！?

• 从源码中我们也可以注意到一些点：
  • 锁的对象不要为空
  • 锁的对象的生命周期要合适，不要中途就被释放了
    • 这也是平时我们用 self 的原因
  • 尽量选择一样的 obj 来加锁，可以使 sDataLists 结构更简单

参考

• 关于 @synchronized，这儿比你想知道的还要多
• 不再安全的 OSSpinLock