Skip to main content

tuwunel_core/utils/
mutex_map.rs

1//! Per-key asynchronous mutual exclusion with automatic entry cleanup.
2//!
3//! Each key maps to a Tokio mutex shared by its current contenders. The last
4//! contender to release its claim removes the entry, whether it held the mutex
5//! or was canceled while waiting for it.
6
7use std::{
8	fmt::Debug,
9	hash::Hash,
10	sync::{Arc, TryLockError::WouldBlock},
11};
12
13use futures::StreamExt;
14use itertools::Itertools;
15use tokio::sync::OwnedMutexGuard as Omg;
16
17use crate::{Result, err, utils::IterStream};
18
19/// Provides independent asynchronous mutexes keyed by owned values.
20///
21/// Lock acquisition creates entries on demand, and callers contending for the
22/// same key serialize. An entry lives exactly as long as some caller holds or
23/// contends for it.
24#[derive(Debug)]
25pub struct MutexMap<Key, Val> {
26	map: Map<Key, Val>,
27}
28
29/// Keeps a keyed mutex locked until the guard is dropped.
30///
31/// The guard retains the parent map so cleanup remains possible. Dropping it
32/// releases the keyed mutex and then removes the entry when no other holder or
33/// contender references it.
34#[derive(Debug)]
35#[clippy::has_significant_drop]
36pub struct Guard<Key, Val> {
37	map: Map<Key, Val>,
38	entry: Option<Value<Val>>,
39	val: Option<Omg<Val>>,
40}
41
42type Map<Key, Val> = Arc<MapMutex<Key, Val>>;
43type MapMutex<Key, Val> = std::sync::Mutex<HashMap<Key, Val>>;
44type HashMap<Key, Val> = std::collections::HashMap<Key, Value<Val>>;
45type Value<Val> = Arc<tokio::sync::Mutex<Val>>;
46
47impl<Key, Val> MutexMap<Key, Val>
48where
49	Key: Clone + Eq + Hash + Send,
50	Val: Default + Send,
51{
52	/// Creates an empty keyed mutex map.
53	///
54	/// No per-key mutex is allocated until a lock method first sees its key.
55	/// The result is equivalent to [`Default::default`].
56	#[must_use]
57	pub fn new() -> Self {
58		Self {
59			map: Map::new(MapMutex::new(HashMap::new())),
60		}
61	}
62
63	/// Acquires the asynchronous mutex associated with a key.
64	///
65	/// The method creates an entry if absent and waits for the current holder
66	/// to release it. Cancellation while waiting releases the claim on the
67	/// entry, and a poisoned internal map mutex causes a panic.
68	#[tracing::instrument(level = "trace", skip(self))]
69	pub async fn lock<K>(&self, k: &K) -> Guard<Key, Val>
70	where
71		K: Debug + Send + ?Sized + Sync + ToOwned<Owned = Key>,
72	{
73		self.entry(k).lock().await
74	}
75
76	/// Acquires the asynchronous mutexes of several keys, one after another in
77	/// key order.
78	///
79	/// A key given more than once is locked once. Callers locking overlapping
80	/// sets this way wait for one another and never deadlock, since each takes
81	/// the keys they share in the same order.
82	#[tracing::instrument(level = "trace", skip_all)]
83	pub async fn lock_all<Keys, Guards>(&self, keys: Keys) -> Guards
84	where
85		Key: Debug + Ord + Sync,
86		Keys: IntoIterator<Item = Key>,
87		Keys::IntoIter: Send,
88		Guards: Default + Extend<Guard<Key, Val>> + Send,
89	{
90		keys.into_iter()
91			.sorted_unstable()
92			.dedup()
93			.stream()
94			.then(async move |key| self.lock(&key).await)
95			.collect()
96			.await
97	}
98
99	/// Attempts to acquire a key without waiting for its asynchronous mutex.
100	///
101	/// The key entry is created if absent, and contention returns an error
102	/// instead of yielding. Acquiring the internal map mutex can still block
103	/// and panics if that mutex is poisoned.
104	#[tracing::instrument(level = "trace", skip(self))]
105	pub fn try_lock<K>(&self, k: &K) -> Result<Guard<Key, Val>>
106	where
107		K: Debug + Send + ?Sized + Sync + ToOwned<Owned = Key>,
108	{
109		self.entry(k).try_lock()
110	}
111
112	/// Attempts to acquire a key without yielding, blocking only to release a
113	/// failed attempt.
114	///
115	/// Contention on either the internal map or keyed mutex returns an error.
116	/// The entry is created only after the map mutex is acquired, and releasing
117	/// a failed attempt blocks on that mutex again. A poisoned map mutex causes
118	/// a panic.
119	#[tracing::instrument(level = "trace", skip(self))]
120	pub fn try_try_lock<K>(&self, k: &K) -> Result<Guard<Key, Val>>
121	where
122		K: Debug + Send + ?Sized + Sync + ToOwned<Owned = Key>,
123	{
124		self.try_entry(k)?.try_lock()
125	}
126
127	/// Reports whether the map currently contains an entry for a key.
128	///
129	/// An entry represents a held mutex or contenders that still reference it.
130	/// The check locks the internal map and panics if that mutex is poisoned.
131	#[must_use]
132	pub fn contains(&self, k: &Key) -> bool { self.map.lock().expect("locked").contains_key(k) }
133
134	/// Reports whether no keyed mutex entries are currently tracked.
135	///
136	/// A false result implies at least one active holder or contender. The
137	/// check locks the internal map and panics if that mutex is poisoned.
138	#[must_use]
139	pub fn is_empty(&self) -> bool { self.map.lock().expect("locked").is_empty() }
140
141	/// Returns the number of keyed mutex entries currently tracked.
142	///
143	/// The count includes held mutexes and entries retained by contenders. The
144	/// check locks the internal map and panics if that mutex is poisoned.
145	#[must_use]
146	pub fn len(&self) -> usize { self.map.lock().expect("locked").len() }
147
148	/// Returns a copy of the keys currently tracked.
149	///
150	/// Each key has a held mutex or contenders still referencing it, and the
151	/// two are not told apart. The copy is taken under the internal map lock,
152	/// which panics if poisoned.
153	#[must_use]
154	pub fn keys(&self) -> impl ExactSizeIterator<Item = Key> + Send + use<Key, Val> {
155		self.map
156			.lock()
157			.expect("locked")
158			.keys()
159			.cloned()
160			.collect::<Vec<_>>()
161			.into_iter()
162	}
163
164	fn entry<K>(&self, k: &K) -> Guard<Key, Val>
165	where
166		K: ?Sized + ToOwned<Owned = Key>,
167	{
168		let val = self
169			.map
170			.lock()
171			.expect("locked")
172			.entry(k.to_owned())
173			.or_default()
174			.clone();
175
176		self.pending(val)
177	}
178
179	fn try_entry<K>(&self, k: &K) -> Result<Guard<Key, Val>>
180	where
181		K: ?Sized + ToOwned<Owned = Key>,
182	{
183		let val = self
184			.map
185			.try_lock()
186			.map_err(|e| match e {
187				| WouldBlock => err!("would block"),
188				| _ => panic!("{e:?}"),
189			})?
190			.entry(k.to_owned())
191			.or_default()
192			.clone();
193
194		Ok(self.pending(val))
195	}
196
197	fn pending(&self, val: Value<Val>) -> Guard<Key, Val> {
198		Guard {
199			map: Arc::clone(&self.map),
200			entry: Some(val),
201			val: None,
202		}
203	}
204}
205
206impl<Key, Val> Default for MutexMap<Key, Val>
207where
208	Key: Clone + Eq + Hash + Send,
209	Val: Default + Send,
210{
211	fn default() -> Self { Self::new() }
212}
213
214impl<Key, Val> Guard<Key, Val> {
215	async fn lock(mut self) -> Self {
216		// The in-flight claim must release before this guard, so a cancellation
217		// leaves the entry unreferenced.
218		let val = self.claim();
219
220		self.val = Some(val.lock_owned().await);
221		self
222	}
223
224	fn try_lock(mut self) -> Result<Self> {
225		self.val = self
226			.claim()
227			.try_lock_owned()
228			.map_err(|_| err!("would yield"))
229			.map(Some)?;
230
231		Ok(self)
232	}
233
234	fn claim(&self) -> Value<Val> { Arc::clone(self.entry.as_ref().expect("claimed")) }
235}
236
237impl<Key, Val> Drop for Guard<Key, Val> {
238	#[tracing::instrument(name = "unlock", level = "trace", skip_all)]
239	fn drop(&mut self) {
240		self.val.take();
241
242		// Releasing the claim under the map lock elects the last one out.
243		let mut map = self.map.lock().expect("locked");
244
245		if self
246			.entry
247			.take()
248			.is_some_and(|val| Arc::strong_count(&val) <= 2)
249		{
250			map.retain(|_, val| Arc::strong_count(val) > 1);
251		}
252	}
253}