偵測 Race Condition 的方法

在並行運算領域，哲學家就餐問題（英語：Dining philosophers problem）是一個經典問題，此問題可能會導致死結(deadlock)或飢餓(starvation)。

常見的解決方式有服務生解法，資源分級解法，Chandy/Misra解法。細節可參考 wiki 的 哲學家就餐問題。

解決此問題的基本概念，便是讓共享的資源在不同執行緒內可以受到控制，但有時因為設計不良，便會出現競爭危害（race hazard）。又稱為競爭條件（race condition）

本篇將針對 race condition 的偵測及解決方式作一介紹。

如何偵測 race condition 

Helgrind's Race Detection Algorithm 提出一個可行的方法，此處摘錄官方文件範例，翻成中文方便以後複習，如下：

1. 首先，需了解 "happens-before relation"

參考 https://en.wikipedia.org/wiki/Happened-before，定義如下：

• If events a and b occur on the same process, a→b if the occurrence of event a preceded the occurrence of event b.
• If event a is the sending of a message and event b is the reception of the message sent in event a, a→b.

2. 以實例進行說明，較易了解。

2.1 下列程式會產生 race codition問題，我們無法確定最後 var 的值是 10 或是 20?

Parent thread:                         Child thread:

int var; // global variable

// create child thread
pthread_create(...)                          
var = 20;                              var = 10;
                                       exit

// wait for child
pthread_join(...)
printf("%d\n", var);

2.2 直覺的解法便是讓兩段設定var的程序有先後關係，如下例，透過訊息的傳遞會讓設定 var 值的程序有 "happens-before" 關係，也就是 var = 20; 一定會在 var = 10; 之前發生。因此最後的結果固定會是10。

Parent thread:                         Child thread:

int var;

// create child thread
pthread_create(...)                          
var = 20;
// send message to child
                                       // wait for message to arrive
                                       var = 10;
                                       exit

// wait for child
pthread_join(...)
printf("%d\n", var);

2.3 所以，若是某個記憶體內的資料，會同時被兩個不同的 thread進行存取，我們可以先檢查這兩個 thread 寫入同份資料時是否存在 "happens-before relation"，若不存在此關係，便存在 race condition. 原文如下： 

Helgrind's algorithm is (conceptually) very simple. It monitors all accesses to memory locations. If a location -- in this example, var, is accessed by two different threads, Helgrind checks to see if the two accesses are ordered by the happens-before relation. If so, that's fine; if not, it reports a race. 

It is important to understand that the happens-before relation creates only a partial ordering, not a total ordering. An example of a total ordering is comparison of numbers: for any two numbers x and y, either x is less than, equal to, or greater than y. A partial ordering is like a total ordering, but it can also express the concept that two elements are neither equal, less or greater, but merely unordered with respect to each other. 

3. 所以若要實作此演算法，便需要偵測所有記憶體存取，並且判斷是否某個記憶體位置會被多個 thread 存取，這些存取關係之間是否存在 happens-before relation。聽起來是有點麻煩，有點像是我的論文題目 causal ordering，還好早就有人幫忙完成此項工作了，真是萬幸。

偵測 race condition 的工具

1. ThreadSanitizer

GCC 與 LLVM 編譯器已經支援此功能，只要在編譯程式時加入 -fsanitize=thread 即可，範例如下：(-fsanitize=thread is only supported on 64 bit CPU)

$ cat race.c
#include "pthread.h"

int var = 0;

void* child_fn ( void* arg ) {
   var++; /* Unprotected relative to parent */ /* this is line 6 */
   return NULL;
}

int main ( void ) {
   pthread_t child;
   pthread_create(&child, NULL, child_fn, NULL);
   var++; /* Unprotected relative to child */ /* this is line 13 */
   pthread_join(child, NULL);
   return 0;
}
$ gcc -fsanitize=thread -fPIE -g -O1 -lpthread race.c

 

執行結果如下：

需特別注意的是使用此方法時，會比一般執行程式時需要高達5倍的記憶體，對於記憶體非常有限的平台而言，也許無法適用，官方文件列出的限制如下：

• ThreadSanitizer uses more real memory than a native run. At the default settings the memory overhead is 5x plus 1Mb per each thread. Settings with 3x (less accurate analysis) and 9x (more accurate analysis) overhead are also available.
• ThreadSanitizer maps (but does not reserve) a lot of virtual address space. This means that tools like ulimit may not work as usually expected.
• Libc/libstdc++ static linking is not supported.
• Non-position-independent executables are not supported. Therefore, the fsanitize=thread flag will cause Clang to act as though the -fPIE flag had been supplied if compiling without -fPIC, and as though the -pie flag had been supplied if linking an executable.

除了偵測 thread 問題之外，編譯器還提供了以下功能

• AddressSanitizer
• ThreadSanitizer
• MemorySanitizer
• UndefinedBehaviorSanitizer (這個檢查挺不賴的，值得一試)
• LeakSanitizer
• DataFlowSanitizer (LLVM才有)

詳情可自行參閱編譯器說明文件

• https://gcc.gnu.org/onlinedocs/gcc/Instrumentation-Options.html
• https://clang.llvm.org/docs/index.html

2. Helgrind: a thread error detector

Helgrind是 valgrind 的一個工具。官方範例描述的很清楚。如下：

#include "pthread.h"

int var = 0;

void* child_fn ( void* arg ) {
   var++; /* Unprotected relative to parent */ /* this is line 6 */
   return NULL;
}

int main ( void ) {
   pthread_t child;
   pthread_create(&child, NULL, child_fn, NULL);
   var++; /* Unprotected relative to child */ /* this is line 13 */
   pthread_join(child, NULL);
   return 0;
} 

測試結果

Thread #1 is the program's root thread

Thread #2 was created
   at 0x511C08E: clone (in /lib64/libc-2.8.so)
   by 0x4E333A4: do_clone (in /lib64/libpthread-2.8.so)
   by 0x4E33A30: pthread_create@@GLIBC_2.2.5 (in /lib64/libpthread-2.8.so)
   by 0x4C299D4: pthread_create@* (hg_intercepts.c:214)
   by 0x400605: main (simple_race.c:12)

Possible data race during read of size 4 at 0x601038 by thread #1
Locks held: none
   at 0x400606: main (simple_race.c:13)

This conflicts with a previous write of size 4 by thread #2
Locks held: none
   at 0x4005DC: child_fn (simple_race.c:6)
   by 0x4C29AFF: mythread_wrapper (hg_intercepts.c:194)
   by 0x4E3403F: start_thread (in /lib64/libpthread-2.8.so)
   by 0x511C0CC: clone (in /lib64/libc-2.8.so)

Location 0x601038 is 0 bytes inside global var "var"
declared at simple_race.c:3

3. DRD: a thread error detector

以下為官方使用範例： 

$ valgrind --tool=drd --read-var-info=yes drd/tests/rwlock_race
...
==9466== Thread 3:
==9466== Conflicting load by thread 3 at 0x006020b8 size 4
==9466==    at 0x400B6C: thread_func (rwlock_race.c:29)
==9466==    by 0x4C291DF: vg_thread_wrapper (drd_pthread_intercepts.c:186)
==9466==    by 0x4E3403F: start_thread (in /lib64/libpthread-2.8.so)
==9466==    by 0x53250CC: clone (in /lib64/libc-2.8.so)
==9466== Location 0x6020b8 is 0 bytes inside local var "s_racy"
==9466== declared at rwlock_race.c:18, in frame #0 of thread 3
==9466== Other segment start (thread 2)
==9466==    at 0x4C2847D: pthread_rwlock_rdlock* (drd_pthread_intercepts.c:813)
==9466==    by 0x400B6B: thread_func (rwlock_race.c:28)
==9466==    by 0x4C291DF: vg_thread_wrapper (drd_pthread_intercepts.c:186)
==9466==    by 0x4E3403F: start_thread (in /lib64/libpthread-2.8.so)
==9466==    by 0x53250CC: clone (in /lib64/libc-2.8.so)
==9466== Other segment end (thread 2)
==9466==    at 0x4C28B54: pthread_rwlock_unlock* (drd_pthread_intercepts.c:912)
==9466==    by 0x400B84: thread_func (rwlock_race.c:30)
==9466==    by 0x4C291DF: vg_thread_wrapper (drd_pthread_intercepts.c:186)
==9466==    by 0x4E3403F: start_thread (in /lib64/libpthread-2.8.so)
==9466==    by 0x53250CC: clone (in /lib64/libc-2.8.so)
...

4. Intel Inspector

此工具要價 $1649，且提供30天試用期，如果是學生或研究人員的話，可能可以免費取得此工具。我想若可以免費取得，這應該是個很棒的工具。

註：造成執行順序不如預期的可能原因除了 race condition 之外，若使用舊版本的作業系統，也許"Priority Inversion"也是個可能原因。

參考資料：

• https://zh.wikipedia.org/wiki/哲学家就餐问题
• https://clang.llvm.org/docs/ThreadSanitizer.html
• http://scattered-thoughts.net/blog/2012/08/16/causal-ordering/