How are the intrusive linked lists in tokio's semaphore and Mutex sound?

Hi!

Looking at how Tokio's Mutex is implemented, I have trouble understanding what makes them safe with regards to forget.

From what I understand, most of the logic of the Mutex comes from batch_semaphore.rs which uses intrusively linked lists to store the Wakers without needing allocation. What I don't understand is how can the Drop implementation of Acquire be enough to ensure there are no use-after-free in case one element is destroyed with forget?.

To explain what I mean, let's assume multiple tasks are trying to lock the Mutex concurrently. Because the Mutex is already locked, multiple Acquire structures are created for the underlying semaphore and after their first calls to poll, they're added to the intrusive waiting queue.
At one point, one of the tasks is cancelled, but instead of being dropped, its future is destroyed with forget and the memory it occupied is reclaimed. What prevents the other calls to Drop from accessing the forgotten Acquire structure causing UB?

Is there something I don't understand about Pin that prevents this?

Thanks!

To poll a future you need to pin it. One of the safety conditions for pinning is that a value is always dropped before it's memory is ever reused. As such it isn't possible to forget and then reclaim the memory. See std::pin - Rust

3 Likes

Thanks! I should have seen that :sweat_smile:

It's perhaps worth mentioning that an Pin<Box<TheFuture>> can still be forgotten, but that leaks the memory containing the future, so it remains valid.

1 Like