`Mutex`' does not guarantee FIFO locking order

[kawadakk]

Version

• tokio v1.53.1

Platform
Linux $hostname 6.18.35 #1-NixOS SMP PREEMPT_DYNAMIC Tue Jun 9 10:28:53 UTC 2026 x86_64 GNU/Linux

Description
Mutex's documentation says:

Tokio’s Mutex operates on a guaranteed FIFO basis. This means that the order in which tasks call the lock method is the exact order in which they will acquire the lock.

However, the future returned by lock checks its cooperative-scheduling budget first. If the budget is exhausted, wait queue insertion is delayed until the next poll. Since this process is invisible to the caller, it's impossible to enforce any specific lock acquisition order.

tokio/tokio/src/sync/mutex.rs

Lines 434 to 436 in 625954f

	pub async fn lock(&self) -> MutexGuard<'_, T> {
	let acquire_fut = async {
	self.acquire().await;

tokio/tokio/src/sync/mutex.rs

Lines 655 to 658 in 625954f

	async fn acquire(&self) {
	crate::trace::async_trace_leaf().await;
	self.s.acquire(1).await.unwrap_or_else(|_| {

tokio/tokio/src/sync/semaphore.rs

Line 624 in 625954f

let inner = self.ll_sem.acquire(1);

tokio/tokio/src/sync/batch_semaphore.rs

Lines 597 to 598 in 625954f

	#[cfg(not(all(tokio_unstable, feature = "tracing")))]
	let coop = ready!(crate::task::coop::poll_proceed(cx));

This Codex-generated test program (unrelated to the production code where we found the issue) reliably reproduces lock order inversion: Playground

first lock-future poll order: [A, B]
lock().await completion order: ['B', 'A']

[RoseWrightdev]

Hi @Darksonn this looks interesting, can I work on this?

[EbrahimEldesoky]

Hi @Darksonn this looks interesting, can I work on this?

Hi @RoseWrightdev! Thanks for your interest. I'm actually already working on a fix for this issue and preparing a pull request. Feel free to check out other open issues though