SideTrack:
Generalizing Dynamic
Atomicity Analysis
Caitlin Sadowski
Jaeheon Yi
Cormac Flanagan
University of California, Santa Cruz
Monday, July 27, 2009
2
Atomicity
The effect of an atomic code block can be
considered in isolation from the rest of a running
program.
• enables sequential reasoning
• atomicity violations often represent
synchronization errors
• most methods are atomic
Monday, July 27, 2009
3
Analyzing for Atomicity
Generalization
Precision
• online/dynamic
• generalizes
• no false alarms
Monday, July 27, 2009
4
Thread 1
atomic{
synchronized(n){
tmp = bal;
}
synchronized(n){
bal = tmp + 1;
}
}
Thread 1
Thread 2
acquire(m)
newVar = 0
begin
acquire(n)
t1 = bal
release(n)
acquire(n)
Thread 2
synchronized(m){
newVar = 0;
}
bal = t + 1
release(n)
end
release(m)
Serial Trace: Each atomic block
executes contiguously
Monday, July 27, 2009
5
Thread 1
atomic{
synchronized(n){
tmp = bal;
}
synchronized(n){
bal = tmp + 1;
}
}
Thread 1
Thread 2
begin
acquire(n)
acquire(m)
newVar = 0
t1 = bal
release(n)
release(m)
Thread 2
synchronized(m){
newVar = 0;
}
acquire(n)
bal = t + 1
release(n)
end
Atomicity = Serializability
Monday, July 27, 2009
6
Thread 1
atomic{
synchronized(n){
tmp = bal;
}
synchronized(n){
bal = tmp + 1;
}
}
Thread 1
Thread 2
begin
acquire(n)
t1 = bal
release(n)
acquire(n)
bal = 0
release(n)
Thread 2
synchronized(n){
bal
}
Monday, July 27, 2009
= 0;
acquire(n)
bal = t + 1
release(n)
end
7
Happens-Before
Thread 1
Thread 2
begin
acquire(n)
t1 = bal
release(n)
acquire(n)
bal = 0
Enables Relation
release(n)
acquire(n)
bal = t + 1
release(n)
end
Monday, July 27, 2009
8
Happens-Before
•program order
Thread 1
Thread 2
begin
acquire(n)
t1 = bal
release(n)
acquire(n)
bal = 0
Enables Relation
•program order
release(n)
acquire(n)
bal = t + 1
release(n)
end
Monday, July 27, 2009
9
Happens-Before
•program order
•fork/join order
Thread 1
Thread 2
begin
acquire(n)
t1 = bal
release(n)
acquire(n)
bal = 0
Enables Relation
•program order
•fork/join order
Thread 0
release(n)
acquire(n)
bal = t + 1
release(n)
end
fork T0
newV = 0
Monday, July 27, 2009
10
Happens-Before
•program order
•fork/join order
•synchronization order
Thread 1
Thread 2
begin
acquire(n)
t1 = bal
release(n)
acquire(n)
bal = 0
Enables Relation
•program order
•fork/join order
Monday, July 27, 2009
release(n)
acquire(n)
bal = t + 1
release(n)
end
11
Thread 1
Thread 2
begin
acquire(n)
happens-before
atomicity violation
t1 = bal
release(n)
acquire(n)
bal = 0
feasible
atomicity violation
release(n)
acquire(n)
bal = t + 1
Concurrent
release(n)
end
Monday, July 27, 2009
12
Thread 1
Thread 2
begin
acquire(n)
t1 = bal
release(n)
acquire(n)
bal = 0
release(n)
acquire(n)
t1 = bal
release(n)
end
Monday, July 27, 2009
13
Thread 1
Thread 2
begin
acquire(n)
...
release(n)
acquire(n)
...
release(n)
acquire(n)
...
release(n)
end
Monday, July 27, 2009
14
Thread 1
Thread 2
begin
acquire(n)
...
release(n)
acquire(n)
...
release(n)
NOT Concurrent
end
fork T2
acquire(n)
...
Monday, July 27, 2009
15
• In a trace, a lock operation a is concurrent
with a later lock operation b if there are
no intermediate operations which both
enable b and happen-after a.
a
happens-beforeprogram order
c
b
•
•
•
fork/join order
sync order
enablesprogram order
•
•
fork/join order
a and b not concurrent
Monday, July 27, 2009
16
Thread 1
Thread 2
begin
NOT Concurrent:
a
happens-before
acquire(n)
...
release(n)
c
enables
acquire(n)
...
b
release(n)
end
fork T2
acquire(n)
...
Monday, July 27, 2009
17
Thread 1
Thread 2
begin
acquire(n)
no C
a
...
release(n)
happens-before
c
acquire(n)
enables
...
release(n)
b
end
Concurrent
acquire(n)
...
release(n)
Monday, July 27, 2009
18
Thread 1
In-Error
Thread 2
begin
acquire(n)
...
release(n)
vulnerable
window
acquire(n)
...
release(n)
acquire(n)
...
last release was
by another thread
Monday, July 27, 2009
release(n)
end
19
Thread 1
After-Error
Thread 2
begin
acquire(n)
...
release(n)
vulnerable
window
acquire(n)
...
release(n)
end
red acquire could
have occurred in
vulnerable window
Monday, July 27, 2009
Concurrent
acquire(n)
...
release(n)
20
Thread 1
Thread 2
Before-Error
acquire(n)
...
release(n)
begin
acquire(n)
...
release(n)
vulnerable
window
acquire(n)
...
release(n)
Monday, July 27, 2009
21
Thread 1
Before-Error
Thread 2
acquire(n)
Concurrent
...
release(n)
begin
acquire(n)
...
release(n)
vulnerable
window
watched locks
for thread 1
n
Monday, July 27, 2009
acquire(n)
...
2nd acquire of
watched lock
22
Blame Assignment
Thread 1
atomic b(){
d();
Not
Concurrent
c();
Atomic!
Call Stack
begin
}
atomic c(){
d();
Atomic!
}
b
b:d
b
b:c
b:c:d
atomic d(){
sync(m) {...}
Atomic!
}
Monday, July 27, 2009
enter b
enter d
Thread 2
enter d
acq/rel(m)
exit d
BeforeError!
acq/rel(m)
exit d
enter c
enter d
vulnerable
window
acquire(m)
23
Blame Assignment
Thread 1
atomic b(){
d();
c();
}
atomic c(){
d();
}
atomic d(){
sync(m) {...}
}
Monday, July 27, 2009
b is not atomic
Call Stack
b
b:c
b:c:d
enter d
acq/rel(m)
exit d
begin
b
b:d
Thread 2
enter b
enter d
BeforeError!
acq/rel(m)
exit d
enter c
enter d
vulnerable
window
acquire(m)
24
SideTrack Implementation
Instrumented
bytecode
RoadRunner
Instrumenter
events
T1:
T2:
T2:
T1:
T1:
T2:
begin_atomic
acquire(lock3)
read(x,5)
write(y,3)
end_atomic
release(lock3)
JVM
Before-Errors
SideTrack
In-Errors
After-Errors
FastTrack
Velodrome
Velodrome-Errors
Data Race Errors
Java bytecode
plus atomic
annotations
Monday, July 27, 2009
25
Errors Found:
40% improvement with prediction
BeforeIn-Errors
Errors
elevator
colt
jbb
hedc
barrier
philo
tsp
sync
Monday, July 27, 2009
1
7
5
4
1
1
4
4
3
4
7
1
1
1
4
4
27
25
After- Predicted Errors
After)/In
Errors (Before ∪ After)/In
5
9
10
4
1
1
4
4
4
2
5
0
0
0
0
0
38
11
26
Slowdown (x Base)
12
Experimental Results:
Performance
9
8.1
6.8
6
4.5
3.3
3
1.0
0
Monday, July 27, 2009
Base
Instrumentation
Framework
SideTrack
Instrumentation SideTrack
Framework
w/o forkjoin
w/o forkjoin
27
Slowdown (x Base)
12
Experimental Results:
Performance
10.3
10.4
Velodrome
(PLDI 2008)
SingleTrack
(ESOP 2009)
9
6
4.5
3.3
3
1.0
0
Monday, July 27, 2009
Base
Instrumentation
Framework
SideTrack
28
Related Work:
Predictive Approaches
• Wang & Stoller et al. (2006, 2009)
•
analyze traces offline; add static info (HAVE)
•
offline causality slicing, violation patterns
•
time bounds & algorithms, no implementation
•
drive scheduler to produce violation, probabilistic
• JPredictor (Chen et al. 2008)
• Farzan & Madhusudan (2009)
• AtomFuzzer (Sen & Park 2008)
Monday, July 27, 2009
29
Conclusion: SideTrack
• no false alarms
• predicts feasible atomicity violations
• 40% increase in atomicity violations
detected
• competitive performance
• chain with other tools (Velodrome, FastTrack)
Monday, July 27, 2009
30
SideTrack:
• no false alarms
• predicts feasible
atomicity violations
Future Work
• 40% increase in atomicity • volatiles, wait/notify,
violations detected
barriers, etc.
• competitive performance • direct comparison
with
other
tools
• chain with other tools
• more benchmarks
• formal proofs
Monday, July 27, 2009
31