资源竞争与死锁检测

多线程编程一直是一个非常难的话题，而资源竞争和死锁问题则是比较常见的多线程问题，这里我们来看看如何检测这些问题。

LLVM

其实llvm项目自身就有这两者的检测方法。而在xcode中也集成了该功能，要使用也非常简单，选中Thread Sanitizer，并且重新编译运行即可。

那么接下来我们来看看使用情况以及他们是如何实现的。

Data Race

数据竞争是我们非常容易犯的一个错误，而且出现问题了也非常难解决。因为出现的概率并不高，而且出现了问题也不会直接表现出来，而可能是通过其他方式表现出来。

首先我们来看一个非常简单的数据竞争问题：

char g_char;

- (void)viewDidLoad {
    [super viewDidLoad];
    
    dispatch_async(dispatch_get_global_queue(0, 0), ^{
        [self setCharB];
    });
    [self setCharA];
}

- (void)setCharA {
    g_char = 'a';
}

- (void)setCharB {
    g_char = 'b';
}

虽然更新一个字节这种操作非常简单，但依然需要在这里加上锁，如果没有加上则会报告如下错误：

==================
WARNING: ThreadSanitizer: data race (pid=62345)
  Write of size 1 at 0x0001032e0f10 by thread T2:
    #0 -[ViewController setCharB] ViewController.m:35 (MallocTest:x86_64+0x100001499)
    #1 __29-[ViewController viewDidLoad]_block_invoke ViewController.m:26 (MallocTest:x86_64+0x1000013da)
    #2 __tsan::invoke_and_release_block(void*) <null>:2136816 (libclang_rt.tsan_iossim_dynamic.dylib:x86_64+0x622bb)
    #3 _dispatch_client_callout <null>:2136816 (libdispatch.dylib:x86_64+0x3847)

  Previous write of size 1 at 0x0001032e0f10 by main thread:
    #0 -[ViewController setCharA] ViewController.m:32 (MallocTest:x86_64+0x100001472)
    #1 -[ViewController viewDidLoad] ViewController.m:28 (MallocTest:x86_64+0x100001381)
    #2 -[UIViewController loadViewIfRequired] <null>:2136816 (UIKit:x86_64+0x1ce190)
    #3 start <null>:2136816 (libdyld.dylib:x86_64+0x1954)

  Location is global 'g_char' at 0x0001032e0f10 (MallocTest+0x000100003f10)

  Thread T2 (tid=1422519, running) is a GCD worker thread

SUMMARY: ThreadSanitizer: data race ViewController.m:35 in -[ViewController setCharB]
==================

同时在左边的导航栏里会显示如下结果：

那么LLVM是怎么实现的呢？

资源竞争的检测其实分为两部分，一部分是编译期的处理，另一部分是运行期的监控。

编译期，编译器会在数据访问的时候插入一段代码，来告诉检测器具体的数据访问情况。这个效果可以看具体的汇编：

-[ViewController setCharA]:
    0x106bd4448 <+0>:  pushq  %rbp
    0x106bd4449 <+1>:  movq   %rsp, %rbp
    0x106bd444c <+4>:  movq   0x8(%rbp), %rdi
    0x106bd4450 <+8>:  callq  0x106bd4798               ; symbol stub for: __tsan_func_entry
    0x106bd4455 <+13>: leaq   0x2afc(%rip), %rdi        ; g_char
    0x106bd445c <+20>: callq  0x106bd47bc               ; symbol stub for: __tsan_write1
    0x106bd4461 <+25>: movb   $0x61, 0x2af0(%rip)       ; lock + 63
    0x106bd4468 <+32>: callq  0x106bd479e               ; symbol stub for: __tsan_func_exit
    0x106bd446d <+37>: popq   %rbp
    0x106bd446e <+38>: retq   

运行期的监控则是靠动态库来导入的（在早期是依赖于静态库）。

可以看到，需要做到在编译期插入代码，不禁会想已经编译好的二进制该怎么办？这里我们来看两个例子：

CoreFoundation`-[__NSArrayM addObject:]:
    ...
    0x10e5b0d82 <+18>: leaq   0x3a3fa7(%rip), %rax      ; __cf_tsanWriteFunction
    ...

在NSMutableArray的代码中，我们发现有一个方法很可疑__cf_tsanWriteFunction，这个方法似乎就是上面的__tsan_write1方法的objc版。同时这个方法在真机上是没有的。

pthread_mutex_lock(&lock)在该模式下实际对应的方法是libclang_rt.tsan_iossim_dynamic.dylib wrap_pthread_mutex_lock，同时dispatch_sync对应的方法是libclang_rt.tsan_iossim_dynamic.dylib wrap_dispatch_sync，可以知道他们都来源于一个非标准的动态库，这也就是说明在该模式下，系统会给我们链接一个已经编译好的，插入相应代码的动态库。这也代表着如果你引用了第三方二进制库，不一定能够检测出其中的竞争问题。

这里还需要检测到线程的状态，则是使用了pthread的一个公开接口：

typedef void (*pthread_introspection_hook_t)(unsigned int event, pthread_t thread, void *addr, size_t size);

enum {
  PTHREAD_INTROSPECTION_THREAD_CREATE = 1,
  PTHREAD_INTROSPECTION_THREAD_START,
  PTHREAD_INTROSPECTION_THREAD_TERMINATE,
  PTHREAD_INTROSPECTION_THREAD_DESTROY,
};

pthread_introspection_hook_install(pthread_introspection_hook);

算法

这个的检测算法较为复杂，这里简单的来描述一下。

• 首先每一个数据根据其内存地址与访问线程id都会有一个对应的内存区块来保存其访问数据，一般是8 bytes映射为1 bytes，所以这里的内存分配器也是需要进行相应的修改。
• 将当前状态和已保存的数据进行比较。
• 如果是非同一个线程，并且已保存的数据访问时间是在当前访问时间之后。
• 那么认为这是一次资源竞争。

Dead lock

死锁的检测相对比较简单了，他并不需要编译期的介入，而是纯运行时的检测。不过遗憾的是xcode上并没有集成，可能是觉得死锁本身就会严重阻碍程序运行，容易被察觉吧。

主要需要做的是hook掉所有锁相关的api，掌管willLock和didLock的消息，LLVM提供默认hook了pthread的相关接口。

每次加锁之前都会产生一个锁-线程的匹配，加锁之后释放该锁-线程的匹配。

如果A锁被某线程持有，同时B锁也被该线程持有，那么就形成了A=>B的一个关联，如果这样的关联形成了一个环，那么就说明产生了死锁。该方法可以利用邻接二维矩阵来实现高效的查找。

如果恢复产生的死锁问题呢？这里我没有找到更好的办法，只能做以下两种处理：

• 杀死某个非主线程的线程，这样能够解除死锁，但会引起资源泄露和逻辑缺失的问题。
• 直接返回，可能会引起资源竞争的问题。

参考

The “Double-Checked Locking is Broken” Declaration
Finding races and memory errors with compiler instrumentation.
ThreadSanitizerAlgorithm
llvm-compiler-rt
valgrind

Dynamic Race Detection with LLVM Compiler
ThreadSanitizer – data race detection in practice
AddressSanitizer: A Fast Address Sanity Checker