EraserEraser: A Dynamic Data Race Detector for Multi-Threaded ProgramsS. Savage, M. Burrows, G. Nelson, P. Sobalvarro, T. AndersonSerge KorenCMSC714Outline➲Introduction➲Related approaches➲Eraser's approach➲Implementation/Experience➲Conclusion10/25/2005 2 of 14Introduction●Threaded programming is everywhere●Hard to debug, “Threads are a bad idea” (Osterhout 96)●Data Race●Two concurrent threads access shared variable●At least one access is a write●No mechanism to prevent accesses from being concurrent10/25/2005 3 of 14Related Approaches●Monitors – state and procedures together●Happens-before●Events ordered between threads based on synchronization objects they access●More general, more costly●Less thorough10/25/2005 4 of 14Happens-before10/25/2005 5 of 14Lockset Algorithm●Support only lock-based synchronization●Check all read/writes as program runs●Infer protection from execution history●On each access to variable, v, by thread, t●Set C(v) = C(v) ∩ locks_held(t)●If C(v) = {}, issue warning10/25/2005 6 of 14Example●Program Locks_held C(v) {} {mu1, mu2}lock(mu1);v = v + 1; {mu1} {mu1}unlock(mu1); {}lock(mu2);v = v + 1; {mu2}unlock(mu2); {}, WARNING10/25/2005 7 of 14Improving Lockset●Initialization – initialize a shared variable without holding lock●Read-shared data – written only at initialization and then read (no need for locks)●Read-write locks – read by multiple threads, written by only one at a time10/25/2005 8 of 14Improved Lockset ExampleVirginExclusiveSharedShared-Modified10/25/2005 9 of 14rd/wr,first threadwr, new threadrdwrwrrd, new threadRead-Write Locks●Lock m protects v if m held in write for writes and in read/write for read●On each read of variable, v, by thread, t●Set C(v) = C(v) ∩ locks_held(t)●If C(v) = {}, issue warning●On each write of variable, v, by thread, t●Set C(v) = C(v) ∩ write_locks_held(t)●If C(v) = {}, issue warning10/25/2005 10 of 14Implementation●Instrument program●Indexed table of lock sets (hashed and sorted)●Shadow word●Exists for every 32-bit data segment●State condition●Lockset index●10-30 times slower than without10/25/2005 11 of 14Annotations●Memory reuse – private allocators/free lists●EraserReuse●Private locks – private implementations of locks●EraserRead/WriteLock/Unlock●Benign races – race that does not affect correctness●EraserIgnoreOn/Off10/25/2005 12 of 14Experience●Tested on different code bases●Found true data races, found false alarms●Effectiveness/Sensitivity●Found data races that had existed before●Works the same on two or ten threads●Multiple locks●Many read locks, write takes all read locks●Deadlock detection using ordering of locks10/25/2005 13 of 14Conclusion●Little data on sensitivity●Only works for locks (pthreads)●Annotations needed●Slow/doubled memory usage●Multiple lock fix incorrect/unclear●http://valgrind.org (Helgrind: a data-race detector)10/25/2005 14 of
View Full Document
Unlocking...