rust-unofficial / too-many-lists

Learn Rust by writing Entirely Too Many linked lists
https://rust-unofficial.github.io/too-many-lists/
MIT License
3.16k stars 276 forks source link

Race condition in `Arc`-ified ”Persistent Stack“, and the new `Arc::into_inner` API #271

Open steffahn opened 1 year ago

steffahn commented 1 year ago

All we need to do to make our list is replace every reference to Rc with std::sync::Arc. That's it. We're thread safe. Done!

But this raises an interesting question: how do we know if a type is thread-safe or not? Can we accidentally mess up?

No! You can't mess up thread-safety in Rust!

(source)

Except we did mess up 😅 – well, maybe not in a “safety” sense, but there is actually a race condition. If I recall correctly, spotting this very race condition (that was hard or impossible to fix without any new API) was one of the motivations for me to add the new API Arc::into_inner to the standard library, which is finally (after some time in the making) due to reach stable Rust in about 4 weeks. See the documentation of Arc::into_inner for more details; it essentially features a copy of this kind of linked list code as a demonstrative example 🙂


As for how best to incorporate this into this book, I’m not sure yet. Two points of concern are that this book claims to work from Rust 1.31, so it may be a bad idea to just incorporate usage of a brand new API into the code. (By the way, Rc has a into_inner method, too, for consistency, which could in principle simply replace the try_unwrap call on this page and the issue is done.) On the other hand there’s the “You can't mess up thread-safety in Rust!” claim, which is (partially) falsified; not by unsafety in a memory-safety sense, but at least by a hard to spot race-condition that can lead to a stack overflow. So unless we really wanted to silently fix the issue and keep up the claim that “you can’t mess up” nonetheless, the best approach would probably involve some clarification what thread-safety is, and some additional text mentioning (and/or at least having a link to the docs for further reading of) the problem of try_unwrap was used with Arc for this list in a multi-threaded context. On second read, I noticed, as a good starting point, the relevant distinction is actually already mentioned in the book

Safe in this case means it's impossible to cause data races, (not to be mistaken with the more general issue of race conditions).

(same page as the first quote)

so maybe we’ve just gotten the perfect example to further explain and demonstrate this very point of “data race ≠ race condition”?