T-Rex: A Dynamic Race Detection Tool for C/C++ Transactional Memory Applications

Participant: Gokcen Kestor

Home Institution:
Barcelona Supercomputing Center - Microsoft Research Center

Home Country: Spain

Host: Prof. Serdar Tasiran

Host Institution: Koc University

Host Country: Turkey

Start Date:
2012-01-09

End Date: 2012-02-03

Description:
The dominance of multi-core processors has made concurrent programming essential to achieve peak performance from modern systems. Unfortunately, despite the performance benefit, parallel programming introduces high software complexity and is prone to synchronization bugs such as data races, atomicity violations, deadlock and livelock.
Transactional Memory (TM) is one of the suitable models that addresses ease of programmability of parallel programs while keeping up with performance expectations of multi-core processors. Using TM, programmers mark sections of code they intend to execute atomically, rather than protecting shared memory locations with locks, and need not worry about deadlocks. There have been significant efforts to develop TM systems, hardware (HTM) and software (STM) and compilers with TM support. However, there is still lack of software development tools and integrated environments that help programmers debug and analyze TM applications, such as race detection tools.
The purpose of this short term scientific mission (STSM) was to tackle the problem of identifying race conditions in C/C++ TM programs running on STM systems, independently of the particular STM implementation used by the programmer. Data race detection for lock-based applications has been intensively studied in the literature but, to the best of our knowledge, this work is the first to explicitly address race detection for real C/C++ TM applications. Informally, a data race is defined as a condition where multiple threads access a shared memory location without proper synchronization and there is at least one write among the memory operations. Data races are difficult to diagnose and reproduce because they often manifest under certain, likely to be very rare, thread interleavings. Although the definition of data race is orthogonal to the synchronization mechanism, critical sections protected by locks and transactions are semantically different and present distinct characteristics and requirements, thus race detection tools used for lock-based applications cannot be directly extended to transactional memory. With TM, a transaction either executes completely and atomically or should appear as if it were never executed. This means that transactions’ effects should be permanently visible, and thus can generate data races, only once a transaction has successfully committed.
We propose T-Rex, a novel dynamic race detection tool for C/C++ transactional memory applications. Our tool records read and write accesses to shared memory locations, both inside and outside transactions, into per-thread metadata and then detects races at synchronization points. Moreover, T-Rex is agnostic of thread interleavings, as it does not depend on the particular threads’ execution ordering to determine data races. T-Rex is transparent to the under- lying TM systems and track memory accesses through Pin, a dynamic binary instrumentation tool.
We evaluate T-Rex with a widely-used STM design, TL2, a lazy-acquiring, lazy-updating TM system, using applications from the STAMP benchmark suite on an 8-core Intel Nehalem server.

Report: here