New Research from the University of Michigan duo Jie Yu and Satish Narayanasamy looks into encoding a set of tested correct interleavings in a program’s binary executable using Predecessor Set (PSet) constraints. These constraints are efficiently enforced at runtime using processor support, which ensures that the runtime follows a tested interleaving. They analyze several bugs in open source applications such as MySQL, Apache, Mozilla, etc., and show that, by enforcing PSet constraints, one can avoid not only data races and atomicity violations, but also other forms of concurrency bugs.
Source: A Case for Interleaving Constrained Shared Memory
Conclusions:
Testing and verifying a multi-threaded program is more difficult than a single-threaded program, because the number of possible interleavings is exponential over the number of memory operations executed by different threads. They make a case for an interleaving constrained shared-memory multi-processor which avoids untested interleavings.
This paper makes the first step towards designing an interleaving constrained multi-processor. To detect untested interleavings one needs a set of invariants fundamentally different from the ones used to detect incorrect interleavings such as a data race invariant or AVIO. They focused on constraining the runtime interleaving such that, no two remote memory operations are allowed to depend on each other at runtime, unless that dependency was observed in at least one of the test runs. They built a software tool to detect PSet constraints and enforce them, but as expected, it incurs significant runtime slowdown. They proposed extensions to a multi-processor design, which enables efficient detection of PSet constraint violations. On detecting a violation, checkpoint support is used for re-executing the program with an alternative interleaving and resolve the PSet constraint violations.
They analyzed several bugs in real applications, and showed that the proposed system can avoid not only data races and atomicity violations, but also other unstructured memory order related concurrency bugs. The number of false constraint violations in a well tested program is very small, and as a result, the resulting performance overhead is also negligible.
Thanks for the great read!
Jeff Loucks
Available Technology