Dynamic race detection in parallel programs [Elektronische Ressource] / von Ali Jannesari Ladani

Autor

Sujets

• Informatik

Informations

• Publié par: karlsruher_institut_fur_technologie
• Publié le: 01 janvier 2010
• Nombre de lectures: 21
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Dynamic Race Detection
in Parallel Programs
Zur Erlangung des akademischen Grades eines
Doktors der Ingenieurwissenschaften
der Fakult¨at fur¨ Informatik
des Karlsruher Instituts fur¨ Technologie (KIT)
genehmigte
Dissertation
von
Ali Jannesari Ladani
Dezember 2010
Tag der mundlic¨ henPrufung:¨ 03. November 2010
Erstgutachter: Prof. Dr. Walter F. Tichy
Zweitgutachter: Prof. Dr. Andreas Zeller
(Universit¨at des Saarlandes)

KIT-UniversityoftheStateofBaden-WuerttembergandNationalResearchCenteroftheHelmholtzAssociation www.kit.eduIIAbstract
Recent hardware developments have pushed parallel computing out of the niche
of numeric applications into the mainstream. Unfortunately, parallel programs
may contain synchronization defects, a class of defect which is difficult to de-
tect. A significant source of these defects is the phenomenon of data races, i.e.,
unsynchronized accesses to shared data. Since parallel programs are schedule-
dependent,reproducingdataracesisoftendifficult. Programsencounteringdata
races often do not crash immediately, resulting in mysterious and unpredictable
behavior.
Currently, available tools tend to miss many data races, or to produce an over-
whelming number of false alarms, regardless of whether they are based on static
analysis or dynamic analysis. Both types of analysis also have their own specific
problems. Static analysis, due to the state explosion problem, is not applicable
to large programs, or, alternatively, the analysis has to focus on a small subset
of fault types. Dynamic analysis, on the other hand, is limited to finding faults
in the code which is actually executed. Additionally, dynamic analysis is either
very slow or reports numerous false warnings.
In this work, we propose a dynamic approach for race detection based on a
synthesis of lockset and happens-before analyses. The approach provides a lower
rateofbothfalsepositivesandfalsenegatives(missedraces). Thebasicideaisto
consult the happens-before relation whenever the lockset algorithm indicates a
possiblerace. Theincreasedprecisionisduetomoredetailedstatemachinesand
adjustment of the sensitivity of the detector for different kinds of applications.
Additionally, a technique to correctly handle inter-thread event notifications
further improves the accuracy of the detector.
Furthermore, we present a new method to deal with ad-hoc synchronizations,
i.e., programmer-defined synchronizations in source code. The method is also
able to identify synchronization operations from unknown libraries, resulting in
a universal race detector.
Our race detection approach is automatic, without any user intervention or
reliance on source code annotation, and has been implemented as a tool, which
+wenamedHelgrind . Resultsfromseveralbenchmarksdemonstrateasignificant
reduction in false positive rates and false negative rates compared to existing
race detectors, with a negligible increase in overhead.
IIIIVKurzfassung
Parallele Programme sind anf¨allig fur¨ Synchronisierungsfehler, die schwierig
aufzuspuren¨ sind. Ursache sind meist sog. Wettlaufsituationen, d.h. unsyn-
chronisierte Zugriffe auf gemeinsam genutzte Daten. Solche Wettlaufsituatio-
nen lassen sich nicht zuverl¨assig reproduzieren, da ihr Auftreten in der Regel
abh¨angig von einer konkreten Ausfuhrungsreihenfolge¨ ist. Erschwerend kommt
hinzu, dass sie sich oft nicht in unmittelbaren Programmfehlern manifestieren,
sondern zu unvorhersehbarem Programmverhalten fuhren,¨ dessen Ursache dann
nur noch schwer zuruc¨ kzuverfolgen ist.
Verfugbare¨ Wettlauferkenner,sowohlstatischealsauchdynamische,neigendazu,
Wettl¨aufe zu ub¨ ersehen, oder eine Flut von Falschmeldungen zu liefern. Hinzu
kommen Probleme, die in der Art der Analyse selbst begrundet¨ sind: Die statis-
che Analyse kann h¨aufig nicht auf gr¨oßere Probleme angewendet werden, da die
Anzahl der zu untersuchenden Programmzust¨ande exponentiell w¨achst. Dy-
namische Analyse hingegen kann nur Fehler in solchen Programmteilen finden,
die tats¨achlich ausgefuhrt¨ werden. Auch wird durch dynamische Analyse die
Programmausfuhrung¨ erheblich verlangsamt.
+Mit Helgrind stellen wir einen neuen, dynamischen Ansatz vor, der Lockset-
undGeschieht-Vorher-Analysekombiniert: DieGeschieht-Vorher-Beziehungwird
immerdannherangezogen,wennderLockset-AlgorithmuseinenWettlaufmeldet.
Durch Anpassen der internen Zustandsautomaten – auch unter Beruc¨ ksichti-
gung verschiedener Programmklassen – konnen¨ wir Genauigkeit und Qualit¨at
der Wettlauferkennung deutlich erh¨ohen. Dazu tr¨agt auch eine neue Technik
bei, die den Signalaustausch zwischen parallelen F¨aden korrekt handhabt.
Nichtzuletztgelingtesuns,benutzerdefinierteSynchronisierung,sogenanntead-
hoc-Synchronisierung,zuberuc¨ ksichtigen. DawirsoauchSynchronisierungsprim-
itive von nicht direkt unterstutzen¨ Bibliotheken zu erkennen verm¨ogen, stellt
unser Ansatz den ersten universellen Wettlauferkenner dar.
F¨ ur die Analyse sind keine weiteren Benutzereingaben und keine Annotationen
des Quellcodes erforderlich. Anhand von Benchmarks k¨onnen wir im Vergleich
zu existierenden Wettlauferkennern eine deutliche Reduzierung sowohl der Zahl
der nicht gemeldeten Wettl¨aufe als auch der Zahl der Falschmeldungen nach-
weisen. Dabei bleibt der zus¨atzliche Mehraufwand bei Speicherverbrauch und
Ausfuhrungszeit¨ vernachl¨assigbar.
VVIContents
List of Figures XI
List of Tables XV
1. Introduction 1
1.1. Motivation.............................. 1
1.2. Problem Statement ......................... 4
1.3. Structure of the Thesis ....................... 7
2. Objectives and Contributions 9
2.1. Objectives 9
2.2. Contribution............................. 9
2.3. Hypotheses 10
3. Basic Concepts of Race Detection 13
3.1. Definitions.............................. 13
3.2. Data Race Classifications...................... 15
3.3. Synchronization........................... 17
3.4. Dynamic Data Race Detection................... 18
3.4.1. The Lockset Algorithm 18
3.4.2. Happens-Before Relation.................. 21
3.4.2.1. Thread Segments................. 21
3.4.2.2. Vector Clocks 2
4. Related Work 27
4.1. Static Analysis ........................... 27
4.2. Model Checking 28
4.3. Dynamic Analysis.......................... 29
4.4. Post-mortem............................. 32
4.5. Software Transactional Memory .................. 3
4.6. Hardware Tr ................. 3
+5. Helgrind Race Detection 35
5.1. The Algorithm 35
VIIContents
5.1.1. Lock Operations ...................... 36
5.1.2. Happens-Before Analysis.................. 37
5.2. Memory State Machines 38
5.2.1. Memory State Machine for Long-running Applications .38
5.2.2. Principles of MSM-long................... 40
5.2.3. States of MSM-long..................... 41
5.2.4. Memory State Machine for Short-running Applications.48
5.2.5. Principles of MSM-short .................. 50
5.2.6. States of MSM-short .................... 50
5.2.7. Discussion and Comparison of Memory State Machines.55
5.3. Limitations ............................. 56
5.3.1. Imprecise Happens-Before Detection ........... 57
6. Detecting Inter-thread Event Notifications 59
6.1. Motivating Example ........................ 60
6.2. Spurious Wake ups ......................... 61
6.3. Detecting Lost Signals ....................... 62
6.3.1. Source Code Annotation .................. 63
6.3.2. Binary Instrumentation 64
6.4. Data Dependency.......................... 6
6.4.1. WR-Relation 67
6.5. Summing-up............................. 70
6.5.1. Pre-instrumentation Phase................. 70
6.5.2. Instrumentation phase ................... 71
6.5.3. Runtime phase ....................... 72
6.6. Limitations 76
7. Identifying Ad-hoc Synchronization 79
7.1. Synchronization Operations .................... 80
7.1.1. True and False Data Races................. 80
7.2. Ad-hoc Synchronizations ...................... 82
7.2.1. Common Pattern in Ad-hoc Synchronization....... 83
7.2.2. Detecting Spinning Read Loops .............. 84
7.2.3. The Algorithm ....................... 86
7.2.4. Limitations ......................... 89
7.3. Universal Race Detector 90
7.3.1. Detecting Synchronization Primitives ........... 91
+8. Implementation of Helgrind 93
8.1. Valgrind Framework ........................ 93
8.2. Machine Code and Intermediate Representation (IR) ...... 95
8.3. Shadow Memory .......................... 9
VIIIContents
8.3.1. Shadow memory for MSM-long ..............10
8.3.2.w m for MSM-short101
8.4. Control Flow Analysis .......................102
8.4.1. Branch Analysis102
8.5. Instrumenting Loops in IR .....................103
8.5.1. Look Ahead Instrumentation ...............106
8.5.2. Identifying Function Calls in IR ..............107
8.5.2.1. Function Pointers.................109
8.6. Data Dependency Analysis11
8.7. Limitations .............................112
9. Experiments and Evaluation 115
9.1. Experimental Setup.........................15
9.2. Results................................16
9.2.1. Unit Test Sui