Brussels / 1 & 2 February 2014


Helgrind: a constraint-based data race detector

This talk will present the basic algorithm, the metadata compression scheme, and the scheme for collecting both stacks of a race. I'd also like to talk about the relationship between this and "traditional" h-b implementations since both schemes have advantages and disadvantages.

Helgrind, one of the Valgrind tools, provides data race detection using a pure happens-before algorithm. Unlike many happens-before implementations, Helgrind does not detect races by creating address-indexed bitmaps and checking them at inter-thread synchronisation points. Instead, Helgrind maintains, for each byte in the address space, two vector timestamps that specify the constraints for future race-free reads and writes to that location. This presents major difficulties in storing so much information, but also makes it possible to provide exact backtraces for both accesses in a race.

This talk does not cover Helgrind's lock-order checking algorithm. Although also interesting, that is a different piece of functionality.


Julian Seward