cooptex provides deadlock-free Mutexes.

Last update: Oct 10, 2022

Related tags

Overview

cooptex

cooptex provides deadlock-free Mutexes. The [CoopMutex::lock] method wraps the [std::sync::Mutex] return value with a Result that will request the caller to drop other held locks so another thread could make progress. This behavior is easily accomplished by using the [retry_loop] function.

use cooptex::*;
let a = CoopMutex::new(42);
let b = CoopMutex::new(43);

retry_loop(|| {
  let a_lock = a.lock()?.unwrap();
  let b_lock = b.lock()?.unwrap();
  assert_eq!(*a_lock + *b_lock, 85);
  Ok(())
});

Guarantees

This crate aims to guarantee that multiple threads cannot possibly deadlock by acquiring locks.

This crate also will prefer threads that have lived the "longest" without completing work. Meaning, when [retry_loop] successfully completes, it will move that thread to the end of the queue for acquiring future locks. This provides an approximately fair scheduler.

The crate is still in early development, so there may be cases that aren't covered. Please open an issue if you can reproduce a deadlock.

Non-Guarantees

This crate explicitly allows the following potentially undesired behavior:

[CoopMutex::lock] may return [Retry] when it could wait and acquire the lock without a deadlock.
[CoopMutex::lock] may wait arbitrarily long before returning [Retry].

Incomplete

We have not fully analyzed the behavior during panics. There is no unsafe code, so we could only possibly deadlock.

License: MIT

Comments

Possibility of RwLock version of CoopMutex?
Hello! This library looks quite useful, and I'll be trying it out over the next couple days in my project (which is currently suffering from occasional deadlocks).

Currently in my project I am using RwLock locks for my data, as most of the time there are not writes occurring, so allowing multiple read-locks simultaneously is beneficial. Naturally, I was wondering if a RwLock is possible for the approach cooptex is using to handle deadlocks.

If not, that's fine! I will try to rework using CoopMutex as written.

I just figured it was worth asking:

Whether a CoopRwLock struct were possible, given cooptex's deadlock resolution design.

How much work it would be to create such a struct. (as if it were straightforward enough, I may look into trying to develop the variant myself)

Anyway, thanks for releasing the library, as it gets the thought process going on other possibilities for handling deadlocks. :)

EDIT: For now, I am using this wrapper around RwLock that keeps track of all "living lock-guards", so that at least when a deadlock occurs, it is easy to see the name/location of any lock-guards it is waiting-for/deadlocked-with: https://gist.github.com/Venryx/64f822a9468bb6d76a8f6d63f0c3ae23
opened by Venryx 1

cooptex provides deadlock-free Mutexes.

Related tags

Overview

cooptex

Guarantees

Non-Guarantees

Incomplete

You might also like...

Provides a wrapper to deserialize clap app using serde.

A (mostly) drop-in replacement for Rust's Result that provides backtrace support

This repository provides an emulator for iterated prisoner's dilemma.

Memory.lol - a tiny web service that provides historical information about social media accounts

Deadlock freedom

Use free svg icons in your Dioxus projects easily with dioxus-free-icons.

A lock-free, partially wait-free, eventually consistent, concurrent hashmap.

Provides a single TUI-based registry for drm-free, wine and steam games on linux, accessed through a rofi launch menu.

Extra iterator adaptors, iterator methods, free functions, and macros.

Dear ImGui: Bloat-free Graphical User interface for C++ with minimal dependencies

A fast, boilerplate free, web framework for Rust

Local blockchain for Free TON DApp development and testing.

A dependency-free chess engine library built to run anywhere.

transmute-free Rust library to work with the Arrow format

Alternative Free Identity System

Fastest and safest Rust implementation of parquet. `unsafe` free. Integration-tested against pyarrow

Bloat-Free Browser Game in Rust (rustc-only challenge)

The Bloat-Free Browser Game in Rust but in C and in UEFI

Uindex is a data store, for data that can be parsed as sentences in some context-free language.

Comments

Possibility of RwLock version of CoopMutex?

Owner

Shelby Doolittle

This is a Telegram bot I'm working on in my free time to learn Rust.

🦜 A hassle-free, highly performant, host it yourself Discord music bot built with Serenity in Rust. Powered by youtube-dl and Genius.

A lock-free thread-owned queue whereby tasks are taken by stealers in entirety via buffer swapping

Quinine is a Rust library that implements atomic, lock-free, but write-once versions of containers like `Box` or `Arc`

This crate provides a convenient macro that allows you to generate type wrappers that promise to always uphold arbitrary invariants that you specified.

todo-or-die provides procedural macros that act as checked reminders.

Provides two APIs for easily cancelling futures, with the option to fallback to a timeout cancellation

global allocator that provides hooks for tracking allocation events

`fugit` provides a comprehensive library of `Duration` and `Instant` for the handling of time in embedded systems, doing all it can at compile time.

Provides a Suricata Eve output for Kafka with Suricate Eve plugin