Lock order reversals: how to prevent them?

It's well known that Rust has trouble representing backlinks in lists and trees. I just realized that this is really the same problem in a different context. The basic problem with backlinks is that you can't pass through the same struct twice in the call chain, because that would mean a double mutable borrow. The problem here with locks is also a constraint on the call chain. This also comes up with RefCell/.borrow().

As a language issue, this is worth thinking about. It's not really a type issue. It's more like what the borrow checker does. Some cases could be shown to be safe at compile time by analyzing the call graph. It's easy to check this at run time, as RefCell/borrow does. But can it be done at compile time?

For the lock case, if all paths lock the same lock types in the same order, the program is deadlock-free. For backlinks, it's harder, because you need to be able to have chains of the same type.

Worth thinking about. I don't have a solution at this time.

Right. In order to acquire the lock with priority p, you have to provide exclusive access to a token with priority q < p for the duration the lock is held. In return, you receive a token with priority p that is bound via lifetimes to hold the lock as long as it exists, just like MutexGuard does. This new token can then be used to acquire additional locks from farther down the hierarchy.

The only thing left is to provide the initial token to each thread, which will allow it to start acquiring locks. This is done via new_thread_root_unchecked().

One downside of this code is that it doesn't support releasing locks early— They must be released in reverse order of acquisition. This is more strict than necessary for preventing deadlocks, but it should be fixable some additional lifetime parameters and constraints.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.