Efficient Virtualization-based Tracing for Dynamic Locking Analysis

In systems programming, employing proper synchronization is an 
ever-demanding task. The absence or misuse of locking primitives could 
subtly cause regressions, data corruptions, or system malfunctions that 
are tricky to debug.  Many tools have been developed to aid the 
debugging of synchronization problems in operating system kernels. Among 
those, LockDoc [1] is a novel approach that automatically generates lock 
rule documentation and identifies bugs by analyzing runtime execution 
traces.

To generate the trace, LockDoc runs an instrumented kernel in a 
simulator. FAIL* [2] is a versatile tracing and fault injection platform 
that provides a simulation environment with various APIs to instrument 
the emulated hardware.  LockDoc builds its tracing tools on top of 
FAIL*. However, there is a mismatch between the designs of LockDoc and 
FAIL*. The tracing tool suffers a severe performance bottleneck, which 
makes it harder to apply LockDoc to larger systems. For example, a 
benchmark that takes a few seconds on native machines would cost tens of 
hours when instrumented and traced with LockDoc.

This thesis systematically analyzes the tracing facilities of LockDoc, 
designing and implementing various optimizations that gain more than a 
26×speedup. Orthogonally, this work presents a dynamic instrumentation 
mechanism that can be seamlessly integrated into the current LockDoc. 
This design could broaden the application of LockDoc and enhance its 
flexibility.

[1] https://dl.acm.org/doi/10.1145/3302424.3303948
[2] https://ieeexplore.ieee.org/document/737197