Goldilocks: Efficiently Computing the Happens-Before Relation Using Locksets, 2006. Full version available at http://www.research.microsoft.com/~qadeer/fatesrv06-fullversion.ps

Abstract. We present a new lockset-based algorithm, Goldilocks, for precisely computing the happens-before relation and thereby detecting data-races at runtime. Dynamic race detection algorithms in the liter-ature are based on vector clocks or locksets. Vector-clock-based algo-rithms precisely compute the happens-before relation but have signifi-cantly more overhead. Previous lockset-based race detection algorithms, on the other hand, are imprecise. They check adherence to a particu-lar synchronization discipline, i.e., a sufficient condition for race freedom and may generate false race warnings. Our algorithm, like vector clocks, is precise, yet it is efficient since it is purely lockset based. We have implemented our algorithm inside the Kaffe Java Virtual Ma-chine. Our implementation incorporates lazy evaluation of locksets and certain “short-circuit checks ” which contribute significantly to its effi-ciency. Experimental results indicate that our algorithm’s overhead is much less than that of the vector-clock algorithm and is very close to our implementation of the Eraser lockset algorithm.