ocallahanHybridDynamicData2003

Motivation

A data race happens when two threads access the same memory with no ordering constraint, and one of the accesses is a write. Unpredictable behavior! It’s a dynamic occurrence. How do we automatically detect this?

Note

Can be mitigated with atomic operations. There are different consistency/memory ordering requirements you can impose: strict (operations seen by all threads simultaneously), sequential (operations should be seen in same order by all threads), weak (ops on synchronisation variables are sequentially consistent, no sync vars accessed until data ops complete, no data vars accessed until sync complete)

See the Rustonomicon and Wikipedia for more.

Prior (dynamic) approaches:

• Lockset-based detection: do two threads access common location without holding a lock? Efficient but coarse.
  • In depth, at each time step we keep track of the set of locks held by each thread
  • Then, if two different threads access the same memory location, and one of them is trying to do a write, if they aren’t holding a common lock, they’ve violated the lockset hypothesis.
  • Report a potential race at each memory location
  • But programmers can write safe code that mutates shared data without locks, e.g., using channels to pass objects between threads.
  • e.g., if you have a single memory arena shared between threads, and are allocating local objects in the arena.
• Happens-before detection: two threads access shared memory in a causally unordered way (a kind of consistency model where we keep track of what ops effect what other ops). No false positives but ~5x slower in practice, and more false negatives.
  • We say happens before if is before on the same thread, or is a thread sending a message, and is receiving that message.
    • A message is generated on Java method calls: thread.join(), thread.start(), etc.
    • We also generate a message on shared mem writes and reads. Mem write is write and send, subsequent access is recv.
  • means “e effects j.”
  • If two events access the same memory, and one is a write, but neither or , then there’s a race.
  • Reports subset of lockset-based reported. But sometimes misses things because generate too many messages.
    • 

Contribution

Combines performance of lockset-based with precision of happens-before. Basically, perform lockset detection, and when doing happens-before detection, only record messages for Java thread primitives—start(), join(), wait(), and notify(). A data race must be positive for both lockset and limited happens-before.

This hybrid approach reduces false positives of lockset, but is faster and more sensitive than happens-before.

To optimize, we basically avoid recording redundant events for already data-raced memory locations.

• “If the thread, access type, and timestamp of a previous event match those of a new event , and ’s lockset is a subset of the locks for , then the new event is redundant according to the theorem below.”

TODO

There’s more here but I’m not looking closely.