All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Share

Description

Static Race Detection. Nov 19, 2012 CS 8803 FPL. The Hardware Concurrency Revolution. Clock speeds have peaked But #transistors continues to grow exponentially Vendors are shipping multi-core processors. Intel CPU Introductions . The Software Concurrency Revolution.

Transcript

Static Race DetectionNov 19, 2012CS 8803 FPLThe Hardware Concurrency RevolutionClock speeds have peaked But #transistors continues to grow exponentially Vendors are shipping multi-core processors Intel CPU Introductions The Software Concurrency RevolutionUntil now:Increasing clock speeds =>even sequential programs ran faster Henceforth:Increasing #CPU cores =>only concurrent programs will run faster Reasoning about Concurrent Programs is Hardt1 = x;t1 = t1 + 1;x = t1;t2 = x;t2 = t2 + 1;x = t2;x==kx==kx==kt1=xt2=xt1=xt1++t2++t2=xx=t1x=t2t2++. . .t2=xt1=xx=t2(20 total)t2++t1++t1++x=t2x=t1x=t1x==k+2 x==k+1x==k+2Race ConditionsThe same location may be accessed by different threads simultaneously.(And at least one access is a write.)Race ConditionsParticularly insidious concurrency bug Triggered non-deterministically No fail-stop behavior even in safe languages like Java Fundamental in concurrency theory and practice Lies at heart of many concurrency problems atomicity checking, deadlock detection, ... Today’s concurrent programs riddled with races “… most Java programs are so rife with concurrency bugs that they work only ‘by accident’.” – Brian Goetz, Java Concurrency in Practice, Addison-Wesley, 2006 ExampleLocking for Race Freedomsync (l) {t1 = x;t1 = t1 + 1;x = t1;sync (l) {The same location may be accessed by different threads simultaneously without holding a common lock.(And at least one access is a write.)The same location may be accessed by different threads simultaneously.(And at least one access is a write.)t2 = x;t2 = t2 + 1;x = t2;}}x==kx==kx==kt1=xt2=xt1=xt1++t2++t2=xx=t1x=t2t2++. . .t2=xt1=xx=t2(20 total)t2++t1++t1++x=t2x=t1x=t1x==k+2 x==k+1x==k+2Previous WorkAllen & Padua 1987; Miller & Choi 1988; Balasundaram & Kennedy 1989; Karam et al. 1989; Emrath et al. 1989; Schonberg 1989; … Dinning & Schonberg 1990; Hood et al. 1990; Choi & Min 1991; Choi et al. 1991; Netzer & Miller 1991; Netzer & Miller 1992; Sterling 1993; Mellor-Crummey 1993; Bishop & Dilger 1996; Netzer et al. 1996; Savage et al. 1997; Cheng et al. 1998; Richards & Larus 1998; Ronsse & De Bosschere 1999; Flanagan & Abadi 1999; … Aiken et al. 2000; Flanagan & Freund 2000; Christiaens & Bosschere 2001; Flanagan & Freund 2001; von Praun & Gross 2001; Choi et al. 2002; Engler & Ashcraft 2003; Grossman 2003; O’Callahan & Choi 2003; Pozniansky & Schuster 2003; von Praun & Gross 2003; Agarwal & Stoller 2004; Flanagan & Freund 2004; Henzinger et al. 2004; Nishiyama 2004; Qadeer & Wu 2004; Yu et al. 2005; Sasturkar et al. 2005; Elmas et al. 2006; Pratikakis et al. 2006; Sen & Agha 2006; Zhou et al. 2007; ... Observation: Existing techniques and tools findrelatively few bugsOur Results392 bugs in mature Java programs comprising 1.5 MLOC Many fixed within a week by developers Our Race Detection Approachall pairsracing pairsChallengesHandle multiple aspects Same location accessed … by different threads … simultaneously Correlate locks with locations they guard … without common lock held Same location accessedby different threadssimultaneouslywithout common lock heldPrecision Showed precise may alias analysisis central (PLDI’06) low false-positive rate (20%) Soundness Devised conditional must not alias analysis (POPL’07) Circumvents must alias analysis Our Race Detection Approachall pairsaliasing pairsshared pairsparallel pairsunlocked pairsracing pairsFalse Pos. Rate: 20% Same location accessedby different threadssimultaneouslywithout common lock heldAlias Analysis for Race DetectionField f is race-free if: // Thread 1:// Thread 2:sync (l1) {sync (l2) {… e1.f …… e2.f …}}e1 and e2never refer to the same value¬ MAY-ALIAS(e1, e2)MUST-NOT-ALIAS(e1, e2)k-Object-Sensitive May Alias AnalysisMay Alias AnalysisLarge body of work Idea #1: Context-insensitive analysis Abstract value = set of allocation sites foo() {bar() {… e1.f …… e2.f …}}¬ MAY-ALIAS(e1, e2) if Sites(e1) ∩Sites(e2) = ∅Idea #2: Context-sensitive analysis (k-CFA) Context (k=1) = call site foo() {bar() {e1.baz();e2.baz();}} Analyze function baz in two contextsRecent may alias analysis [Milanova et al. ISSTA’03] Solution: Problem: Too few abstract values! Abstract value = set of strings of ≤ k allocation sites Problem: Too few or too many contexts! Solution: Context (k=1) = allocation site of this parameter k-Object-Sensitive Analysis: Our ContributionsNo scalable implementations for even k = 1 Insights: Symbolic representation of relations BDDs [Whaley-Lam PLDI’04, Lhotak-Hendren PLDI’04] Demand-driven race detection algorithm Begin with k = 1 for all allocation sites Increment k only for those involved in races Allow scalability to k = 5 Our Race Detection Approachall pairsaliasing pairsshared pairsparallel pairsunlocked pairsracing pairs Same location accessedby different threadssimultaneouslywithout common lock heldAlias Analysis for Race DetectionField f is race-free if: // Thread 1:// Thread 2:sync (l1) {sync (l2) {… e1.f …… e2.f …}}e1 and e2never refer to the same value¬ MAY-ALIAS(e1, e2)ORl1 and l2always refer to the same valueMUST-ALIAS(l1, l2)Must Alias AnalysisSmall body of work Much harder problem than may alias analysis Impediment to many previous race detection approaches Folk wisdom: Static race detection is intractable Insight: Must alias analysis not necessary forrace detection!New Idea: Conditional Must Not Alias AnalysisField f is race-free if: // Thread 1:// Thread 2:sync (l1) {sync (l2) {… e1.f …… e2.f …}}Whenever l1 and l2 refer to different values, e1 and e2also refer to different valuesMUST-NOT-ALIAS(l1, l2) => MUST-NOT-ALIAS(e1, e2)a[0]a[N-1]a[i]h1h1……h1gggh2……h2h2Examplea = new h0[N];for (i = 0; i < N; i++) { a[i] = new h1; a[i].g = new h2;}h0x1 = a[*];sync (?) { x1.g.f = …;}x2 = a[*];sync (?) { x2.g.f = …;}h0a[0]a[N-1]a[i]h1h1……h1gggh2……h2h2Easy Case: Coarse-grained Lockinga = new h0[N];for (i = 0; i < N; i++) { a[i] = new h1; a[i].g = new h2;}x1 = a[*];sync (a) { x1.g.f = …;}x2 = a[*];sync (a) { x2.g.f = …;}Field f is race-free if:trueMUST-NOT-ALIAS(a, a) => MUST-NOT-ALIAS(x1.g, x2.g)MUST-NOT-ALIAS(l1, l2) => MUST-NOT-ALIAS(e1, e2)h0a[0]a[N-1]a[i]h1h1……h1gggh2……h2h2Examplea = new h0[N];for (i = 0; i < N; i++) { a[i] = new h1; a[i].g = new h2;}x1 = a[*];sync (?) { x1.g.f = …;}x2 = a[*];sync (?) { x2.g.f = …;}h0a[0]a[N-1]a[i]h1h1……h1gggh2……h2h2Easy Case: Fine-grained Lockinga = new h0[N];for (i = 0; i < N; i++) { a[i] = new h1; a[i].g = new h2;}x1 = a[*];sync (x1.g) { x1.g.f = …;}x2 = a[*];sync (x2.g) { x2.g.f = …;}Field f is race-free if:trueMUST-NOT-ALIAS(l1, l2) => MUST-NOT-ALIAS(e1, e2)MUST-NOT-ALIAS(x1.g, x2.g) => MUST-NOT-ALIAS(x1.g, x2.g)h0a[0]a[N-1]a[i]h1h1……h1gggh2……h2h2Examplea = new h0[N];for (i = 0; i < N; i++) { a[i] = new h1; a[i].g = new h2;}x1 = a[*];sync (?) { x1.g.f = …;}x2 = a[*];sync (?) { x2.g.f = …;}h0a[0]a[N-1]a[i]h1h1……h1gggh2……h2h2Hard Case: Medium-grained Lockinga = new h0[N];for (i = 0; i < N; i++) { a[i] = new h1; a[i].g = new h2;}x1 = a[*];sync (x1) { x1.g.f = …;}x2 = a[*];sync (x2) { x2.g.f = …;}Field f is race-free if:true(fieldg of distinct h1 values linked to distinct h2 values)MUST-NOT-ALIAS(x1, x2) => MUST-NOT-ALIAS(x1.g, x2.g)MUST-NOT-ALIAS(l1, l2) => MUST-NOT-ALIAS(e1, e2)h0a[0]a[N-1]a[i]h1h1…………h1gggh2…………h2h2h0►►►h1h1h1►►►h2h2h2Disjoint Reachabilityfrom distincth1 values we can reach (via 1 or more fields) only distincth2 values In every execution, if:then {h2} ⊆ DR({h1})Note: Values abstracted by sets of allocation sitesConditional Must Not Alias Analysis usingDisjoint ReachabilitySites(l1)Sites(l2)// Thread 1:// Thread 2:sync (l1) {sync (l2) { … e1.f …… e2.f …}}⊆ DRSites(e1)Sites(e2)Field f is race-free if:(Sites(e1) ∩Sites(e2)) ⊆ DR(Sites(l1) ∪Sites(l2)) e1 reachable from l1 and e2 reachable from l2 MUST-NOT-ALIAS(l1, l2) => MUST-NOT-ALIAS(e1, e2)h0a[0]a[N-1]a[i]h1h1……h1gggh2……h2h2Hard Case: Medium-grained Lockinga = new h0[N];for (i = 0; i < N; i++) { a[i] = new h1; a[i].g = new h2;}x1 = a[*];sync (x1) { x1.g.f = …;}x2 = a[*];sync (x2) { x2.g.f = …;}Field f is race-free if:(Sites(e1) ∩Sites(e2)) ⊆ DR(Sites(l1) ∪Sites(l2)) e1 reachable from l1 and e2 reachable from l2 (Sites(x1.g) ∩Sites(x2.g)) ⊆ DR(Sites(x1) ∪Sites(x2)) x1.g reachable from x1 and x2.g reachable from x2 true true ({h2}) ⊆ DR({h1}) x1.g reachable from x1 and x2.g reachable from x2 Experience with ChordExperimented with 12 multi-threaded Java programs smaller programs used in previous work larger, mature and widely-used open-source programs whole programs and libraries Tool output and developer discussions available at: http://www.cs.stanford.edu/~mhn/chord.html Programs being used by other researchers in race detection vect1.1htbl1.1htbl1.4vect1.4tsphedcftppooljdbmjdbfjtdsderbyBenchmarksclasses19213663703704224933884614655531746KLOC3375767683103124115122165646descriptionJDK 1.1 java.util.VectorJDK 1.1 java.util.HashtableJDK 1.4 java.util.HashtableJDK 1.4 java.util.VectorTraveling Salesman ProblemWeb crawlerApache FTP serverApache object pooling libraryTransaction managerO/R mapping systemJDBC driverApache RDBMStime0m28s0m27s2m04s2m02s3m03s9m10s11m17s10m29s9m33s9m42s10m23s36m03sPairs Retained After Each Stage (Log scale)vect1.1htbl1.1htbl1.4vect1.4tsphedcftppooljdbmjdbfjtdsderbyClassification of Unlocked Pairsharmful500071704510591130341018benign126900031000140false000044123137341778# bugs100016121721816319Developer Feedback16 bugs in jTDS Before: “As far as we know, there are no concurrency issues in jTDS …” After: “It is probably the case that the whole synchronization approach in jTDS should be revised from scratch ...” 17 bugs in Apache Commons Pool “Thanks to an audit by Mayur Naik many potential synchronization issues have been fixed” -- Release notes for Commons Pool 1.3 319 bugs in Apache Derby “This looks like *very* valuable information and I for one appreciate you using Derby … Could this tool be run on a regular basis? It is likely that new races could get introduced as new code is submitted ...” Related WorkStatic (compile-time) race detection Need to approximate multiple aspects Need to perform must alias analysis Sacrifice precision, soundness, scalability Dynamic (run-time) race detection Current state of the art Inherently unsound Cannot analyze libraries Shape Analysis much more expensive than disjoint reachability Summary of ContributionsPrecise race detection (PLDI’06) Key idea: k-object-sensitive may alias analysis Important client for may alias analyses Sound race detection (POPL’07) Key idea: Conditional must not alias analysis Has applications besides race detection Effective race detection 392 bugs in mature Java programs comprising 1.5 MLOC Many fixed within a week by developers

Related Search

Related Documents

Sep 20, 2017

Sep 20, 2017

Mar 8, 2018

Mar 17, 2018

Mar 19, 2018

Apr 1, 2018

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks