Crate tracing_mutex
source · [−]Expand description
Mutexes can deadlock each other, but you can avoid this by always acquiring your locks in a consistent order. This crate provides tracing to ensure that you do.
This crate tracks a virtual “stack” of locks that the current thread holds, and whenever a new lock is acquired, a dependency is created from the last lock to the new one. These dependencies together form a graph. As long as that graph does not contain any cycles, your program is guaranteed to never deadlock.
Panics
The primary method by which this crate signals an invalid lock acquisition order is by panicking. When a cycle is created in the dependency graph when acquiring a lock, the thread will instead panic. This panic will not poison the underlying mutex.
This conflicting dependency is not added to the graph, so future attempts at locking should succeed as normal.
Structure
Each module in this crate exposes wrappers for a specific base-mutex with dependency trakcing
added. For now, that is limited to stdsync which provides wrappers for the base locks in the
standard library. More back-ends may be added as features in the future.
Performance considerations
Tracing a mutex adds overhead to certain mutex operations in order to do the required bookkeeping. The following actions have the following overhead.
-
Acquiring a lock locks the global dependency graph temporarily to check if the new lock would introduce a cyclic dependency. This crate uses the algorithm proposed in “A Dynamic Topological Sort Algorithm for Directed Acyclic Graphs” by David J. Pearce and Paul H.J. Kelly to detect cycles as efficently as possible. In addition, a thread local lock set is updated with the new lock.
-
Releasing a lock updates a thread local lock set to remove the released lock.
-
Allocating a lock performs an atomic update to a shared counter.
-
Deallocating a mutex temporarily locks the global dependency graph to remove the lock entry in the dependency graph.
These operations have been reasonably optimized, but the performance penalty may yet be too much
for production use. In those cases, it may be beneficial to instead use debug-only versions
(such as stdsync::DebugMutex) which evaluate to a tracing mutex when debug assertions are
enabled, and to the underlying mutex when they’re not.
Modules
Tracing mutex wrappers for locks found in std::sync.