6 ms·

Rust Atomics and Locks (2023)

209 points by 0xedb 2y ago

ra0x3 2y ago
If you're into Rust and need a solid, no-fluff intro to atomics and locks, Mara Bos has you covered. It’s straight to the point, helping you nail down concurrency without the usual headache. Worth checking out if you're serious about leveling up your Rust game.
hobofan 2y ago
Even if you are not into Rust, I'd recommend this book if you want to get into low-level and/or embedded programming. It's an exceptionally well written introduction into the most important topics there and ~80% of the book are not specific to Rust (or can be transferred just as well to other languages).
- throwaway17_17 2y ago
  Thanks for this comment. I’ve had this book sitting on my To Be Read stack for about 10 months but kept bumping it down because I don’t use Rust, but the title and ToC was compelling enough for me to buy it and hope for non-Rust specific content. Even if your 80% estimate is 20% to large a guess, I’m definitely going to pull it up to the top of the stack and read it instead of passing it over.
- self_awareness 2y ago
  They can be transferred, but other languages have also other concepts and other mechanisms of synchronization. This Rust book seems solid, but I would not assume other languages to have the same mechanisms as in Rust the same way I wouldn't recomment using programming patterns from other languages in Rust.
raphar 2y ago
Can you recommend any other book about the same subject but different programming language? Thanks!!!
- imron 2y ago
  This book! There’s Rust specific parts but the knowledge you gain will transfer across languages.
  - raphar 2y ago
    I'm reading this at the moment! but I also want to compare how well each language helps you develop concurrency solutions.
- npalli 2y ago
  "C++ Concurrency in Action" by Anthony Williams is solid. Make sure you get the second edition, it is updated for C++17. https://www.amazon.com/C-Concurrency-Action-Anthony-Williams-dp-1617294691/dp/1617294691/ https://www.amazon.com/C-Concurrency-Action-Anthony-Williams...
- deleted 2y ago
  [deleted]
- fanf2 2y ago
  I have used Rust a little, but this book was most useful to me when I was working on a concurrent data structure for an old C program. It’s a very good book for anyone writing low-level multi-threaded code in C or C++ as well as Rust, because they have basically the same primitives. The only places I know where it isn’t applicable are the Linux kernel and Java, because their memory models and concurrency primitives predate and significantly differ from the Rust/C++/C models. For the Linux memory model, there is Paul McKenney’s free book, “is parallel programming hard, and if so, what can you do about it?” https://cdn.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html https://cdn.kernel.org/pub/linux/kernel/people/paulmck/perfb...
- tialaramex 2y ago
  I guess there must be at least one book about the Java Memory Model, which is very different but fascinating? I don't know of any specific books to recommend. For many languages there is nothing resembling this, they tend to not get into the details Mara covers, if you get a mutex and maybe atomic arithmetic then they're done. If you wondered about C or C++, this book is the same content as for those languages but with Rust's syntax. The discrepancy between Rust's memory model and the memory model adopted in C++ 11 and subsequently C is mostly about a feature that's not available in your C or C++ compiler and (which is why Rust doesn't have it) probably won't ever be. C++ x.store(r1, std::memory_order_relaxed); is literally the same thing as Rust x.store(r1, std::sync::atomic::Ordering::Relaxed); The biggest syntax difference is that C++ x.store(r1) compiles, and in Rust it doesn't. But, chances are after reading Mara's book you will think it's weird not to specify the Ordering needed and never use this uh, convenience.
mbsai29 2y ago
If you are working with async rust, this book is a must-read. Clearly explains most of the primitives that are used in rust like Arc, Mutex, etc. The examples in the github repo are quite helpful and fairly intuitive if you follow along.
- freddierest 2y ago
  There's quite an escalation of topics for Rust. If you want to write a HTTP server, people are guided towards Axum/Tokio, and thus async rust. If you want to use async Rust, read this book? This books covers assembly level atomics, and creating your own channels, in beginner chapters. Is that necessary for writing a HTTP server in Rust? From the topics in the TOC, this book is useful of you want you write concurrency primitives. I wouldn't recommend it if you just want to _use_ Arc/Mutex/crossbeam-channel.
nutate 2y ago
I wrote this in a review I believe, but this is one of the most comprehensive introductions to a good 80% of what could be considered a high performance computing education. It's extremely well written, in the weeds, but not lost in them. If you've done heavy atomics and or locks in C or C++ or with Fortran libraries, this will help show you how rust prevents so many footguns at compile time.
ridiculous_fish 2y ago
Any thoughts on the best way to express global locks in Rust? A classic example is a set of bank accounts, atomically transacting with each other. Fine-grained per-account locking is possible, but risks deadlock due to lock ordering inversion. A simple solution is to replace per-account locks with a singleton global lock, covering all accounts. Any transaction must first acquire this lock, and now deadlock is impossible. But this is an awkward fit for Rust, whose locks want to own the data they protect. What's the best way to express a global lock, enforcing that certain data may only be accessed while the global lock is held?
- lucasyvas 2y ago
  If I’m understanding correctly can’t you lock on some other account criteria, like IDs? A Mutex does have to own the data but you can still decide what it owns. When you lock, the returned MutexGuard is owned, so you can pass it around or return it and it’s only dropped when it ultimately goes out of scope.
- returningfory2 2y ago
  Maybe define a new type in a such way that only 1 value of that type can be instantiated, and then put that unique value in a mutex. Any function that needs to hold the global lock accepts a value of the new type. Calling the function involves providing the value, which is proof that you are holding the mutex.
- chc4 2y ago
  Use ghost_cell/qcell, and put the QCellOwner in a mutex. Acquiring the cell owner grants the ability to access the data, but doesn't tie ownership.
- tialaramex 2y ago
  I don't think this is an awkward fit. There's no reason it should be Mutex<CustomerBankAccount> it can be Mutex<MyTransferToken> or indeed Mutex<()> if you're really sure you don't actually want to lock any data. One piece of advice I'd suggest is, write APIs which take that MyTransferToken to signify that you must take the lock before calling them, it can be a unit type (a Zero Size type, a struct with no members) at the start if you like, but I suspect you'll find that across several functions which take that MyTransferToken you realise actually the data I was going to put in a separate parameter is really always accompanying that token, and so it might as well go inside the the MyTransferToken and before you know it your unit type that was just to ensure correct locking is in fact an object with important data protected by the lock.
tialaramex 2y ago
Because this book was written more than a year ago, it spends some time on Windows Slim Reader Writer Locks, SRWLocks which at that time of its writing were how Rust's Mutex and RwLock were implemented on Windows (by the author in fact IIRC). Since then, two important things happened. 1. On Windows 8 and beyond Rust moved to WaitOnAddress with an API similar to the futex on several other systems. 2. We found out SRWLocks have a significant (arguably fatal, but depending on your use case it may seem irrelevant) difference between how they actually work and what Microsoft's API said about them. This bug is fixed... in Microsoft's own version control, not in released Windows versions. Specifically SRWLocks may silently give you a Write Lock, even if you asked only for a Read Lock, in the case where the lock was just released at the moment you asked. If you were expecting other threads to also get a read lock, which would ordinarily be possible - too bad, you've secretly been given the exclusive write lock so read locks are unavailable until you release it. The actual reason seems to be this: SRWLocks are small (a single pointer, with some low bits stolen to hide metadata) and the authors forgot that they actually know (because it's a different function call) whether you asked for a read or a write lock. Since they didn't have anywhere to store this single bit (read or write) they just assumed they don't know in this edge case where the lock happens to be available immediately, and since they "don't know" they always give you a write lock anyway. Oops. [Edited to make minor clarifications]
- forrestthewoods 2y ago
  > Specifically SRWLocks may silently give you a Write Lock, even if you asked only for a Read Lock, in the case where the lock was just released at the moment you asked. Oh hey, I reported that bug and behavior! One of my proudest reports. Not too often you find a legit bug, or at least documentation oversight, in such a core API.
  - tialaramex 2y ago
    Yeah, I've also only very rarely seen real bugs in core system features (deadlock inside glibc's allocator a decade or more ago in my case IIRC) and I must say you got a much healthier reaction. It's definitely an actual bug not a doc bug. I've explained this a few times to people and it does seem like the natural inclination is to assume SRWLock must be supposed to do that, but I was glad to see internally Microsoft did fix this, because it's clearly the Wrong Thing™. I see two common defences for this bug. One is "Actually, it's supposed to be unfair, you don't understand why that's a good idea". Which assumes I'm expecting a fair lock and I'm unhappy not to get it. Giving a reader the reader lock when there's a writer waiting would be unfair - and probably a bad idea but I'm open to it if somebody presents benchmarks - but giving them the writer lock is just a bug. Another is "Actually, there is a writer waiting, and this way that writer gets the lock faster". As you wrote the example code you know that's false, there is no writer waiting, there are only readers and (in the buggy scenario) they're blocked forever for no reason.
skoocda 2y ago
I've done a precursory skim of this and plan to start reading it in earnest next week. Looks comprehensive and accessible. Very excited.
quohort 2y ago
Why do programming books always have some random unrelated illustration on the front? Usually when you have a textbook, they will have some nice illustration that is tangentially related to the content of the book (like fibonacci spiral for a math book or some chemical reaction for a chemistry book for example). But I suppose that there isn't really such an equivalent unless it's a computer graphics book. I guess it's also like how every project has to have its own "cutesey" mascot.
- otteromkram 2y ago
  Yeah, especially that persnickety, "The Programming Language" book. Talk about obscure covers! /s I think it's just an O'Reilly thing. It keeps the people guessing. Actually, the covers also make the books easily recognizable. Animals, statues, etc., are all good memory association drivers.
- self_awareness 2y ago
  This is mostly an O'Reilly thing. https://www.oreilly.com/content/a-short-history-of-the-oreilly-animals/ https://www.oreilly.com/content/a-short-history-of-the-oreil... TL;DR: > Some of the people at O’Reilly were taken aback: they thought the animals were weird, ugly, and a bit scary. But Tim [O'Reilly] got it immediately—he liked the quirkiness of the animals, thought it would help to make the books stand out from other publishers’ offerings—and it just felt right. They even have a browser which helps you identify the animal: https://www.oreilly.com/animals.csp https://www.oreilly.com/animals.csp
pythops 2y ago
Amazing book !
bk496 2y ago
Why can't they distribute the edition as a PDF?
andrew_eu 2y ago
It's an excellent book and I agree with many of the comments -- while it's written for Rust, the vast majority of it is applicable to many languages. It's amazing to see the book published on their website for free (though I am still happy in having bought the book). One thing I found lacking in the book were the examples. It has tons, but all of them are extremely focused on the topic they are illustrating and most feel very contrived. Would anyone here have a suggestion for a small/medium-sized project (weekend sized) which would actually use the patterns discussed in the book?
volonoctu 2y ago
Really good book and fairly comprehensive like a course. Probably has the best explanation of memory ordering. The 'build your own' teaching method is useful for understanding how the different data structures work.

209 points by 0xedb 2y ago

If you're into Rust and need a solid, no-fluff intro to atomics and locks, Mara Bos has you covered. It’s straight to the point, helping you nail down concurrency without the usual headache. Worth checking out if you're serious about leveling up your Rust game.

hobofan 2y ago

Even if you are not into Rust, I'd recommend this book if you want to get into low-level and/or embedded programming. It's an exceptionally well written introduction into the most important topics there and ~80% of the book are not specific to Rust (or can be transferred just as well to other languages).

throwaway17_17 2y ago
Thanks for this comment. I’ve had this book sitting on my To Be Read stack for about 10 months but kept bumping it down because I don’t use Rust, but the title and ToC was compelling enough for me to buy it and hope for non-Rust specific content. Even if your 80% estimate is 20% to large a guess, I’m definitely going to pull it up to the top of the stack and read it instead of passing it over.
self_awareness 2y ago
They can be transferred, but other languages have also other concepts and other mechanisms of synchronization. This Rust book seems solid, but I would not assume other languages to have the same mechanisms as in Rust the same way I wouldn't recomment using programming patterns from other languages in Rust.

raphar 2y ago

Can you recommend any other book about the same subject but different programming language? Thanks!!!

imron 2y ago
This book! There’s Rust specific parts but the knowledge you gain will transfer across languages.
- raphar 2y ago
  I'm reading this at the moment! but I also want to compare how well each language helps you develop concurrency solutions.
npalli 2y ago
"C++ Concurrency in Action" by Anthony Williams is solid. Make sure you get the second edition, it is updated for C++17. https://www.amazon.com/C-Concurrency-Action-Anthony-Williams-dp-1617294691/dp/1617294691/ https://www.amazon.com/C-Concurrency-Action-Anthony-Williams...
deleted 2y ago
[deleted]
fanf2 2y ago
I have used Rust a little, but this book was most useful to me when I was working on a concurrent data structure for an old C program. It’s a very good book for anyone writing low-level multi-threaded code in C or C++ as well as Rust, because they have basically the same primitives. The only places I know where it isn’t applicable are the Linux kernel and Java, because their memory models and concurrency primitives predate and significantly differ from the Rust/C++/C models. For the Linux memory model, there is Paul McKenney’s free book, “is parallel programming hard, and if so, what can you do about it?” https://cdn.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html https://cdn.kernel.org/pub/linux/kernel/people/paulmck/perfb...
tialaramex 2y ago
I guess there must be at least one book about the Java Memory Model, which is very different but fascinating? I don't know of any specific books to recommend. For many languages there is nothing resembling this, they tend to not get into the details Mara covers, if you get a mutex and maybe atomic arithmetic then they're done. If you wondered about C or C++, this book is the same content as for those languages but with Rust's syntax. The discrepancy between Rust's memory model and the memory model adopted in C++ 11 and subsequently C is mostly about a feature that's not available in your C or C++ compiler and (which is why Rust doesn't have it) probably won't ever be. C++ x.store(r1, std::memory_order_relaxed); is literally the same thing as Rust x.store(r1, std::sync::atomic::Ordering::Relaxed); The biggest syntax difference is that C++ x.store(r1) compiles, and in Rust it doesn't. But, chances are after reading Mara's book you will think it's weird not to specify the Ordering needed and never use this uh, convenience.

mbsai29 2y ago

If you are working with async rust, this book is a must-read. Clearly explains most of the primitives that are used in rust like Arc, Mutex, etc. The examples in the github repo are quite helpful and fairly intuitive if you follow along.

freddierest 2y ago
There's quite an escalation of topics for Rust. If you want to write a HTTP server, people are guided towards Axum/Tokio, and thus async rust. If you want to use async Rust, read this book? This books covers assembly level atomics, and creating your own channels, in beginner chapters. Is that necessary for writing a HTTP server in Rust? From the topics in the TOC, this book is useful of you want you write concurrency primitives. I wouldn't recommend it if you just want to _use_ Arc/Mutex/crossbeam-channel.

nutate 2y ago

I wrote this in a review I believe, but this is one of the most comprehensive introductions to a good 80% of what could be considered a high performance computing education. It's extremely well written, in the weeds, but not lost in them. If you've done heavy atomics and or locks in C or C++ or with Fortran libraries, this will help show you how rust prevents so many footguns at compile time.

ridiculous_fish 2y ago

Any thoughts on the best way to express global locks in Rust? A classic example is a set of bank accounts, atomically transacting with each other. Fine-grained per-account locking is possible, but risks deadlock due to lock ordering inversion. A simple solution is to replace per-account locks with a singleton global lock, covering all accounts. Any transaction must first acquire this lock, and now deadlock is impossible. But this is an awkward fit for Rust, whose locks want to own the data they protect. What's the best way to express a global lock, enforcing that certain data may only be accessed while the global lock is held?

lucasyvas 2y ago
If I’m understanding correctly can’t you lock on some other account criteria, like IDs? A Mutex does have to own the data but you can still decide what it owns. When you lock, the returned MutexGuard is owned, so you can pass it around or return it and it’s only dropped when it ultimately goes out of scope.
returningfory2 2y ago
Maybe define a new type in a such way that only 1 value of that type can be instantiated, and then put that unique value in a mutex. Any function that needs to hold the global lock accepts a value of the new type. Calling the function involves providing the value, which is proof that you are holding the mutex.
chc4 2y ago
Use ghost_cell/qcell, and put the QCellOwner in a mutex. Acquiring the cell owner grants the ability to access the data, but doesn't tie ownership.
tialaramex 2y ago
I don't think this is an awkward fit. There's no reason it should be Mutex<CustomerBankAccount> it can be Mutex<MyTransferToken> or indeed Mutex<()> if you're really sure you don't actually want to lock any data. One piece of advice I'd suggest is, write APIs which take that MyTransferToken to signify that you must take the lock before calling them, it can be a unit type (a Zero Size type, a struct with no members) at the start if you like, but I suspect you'll find that across several functions which take that MyTransferToken you realise actually the data I was going to put in a separate parameter is really always accompanying that token, and so it might as well go inside the the MyTransferToken and before you know it your unit type that was just to ensure correct locking is in fact an object with important data protected by the lock.

tialaramex 2y ago

Because this book was written more than a year ago, it spends some time on Windows Slim Reader Writer Locks, SRWLocks which at that time of its writing were how Rust's Mutex and RwLock were implemented on Windows (by the author in fact IIRC). Since then, two important things happened. 1. On Windows 8 and beyond Rust moved to WaitOnAddress with an API similar to the futex on several other systems. 2. We found out SRWLocks have a significant (arguably fatal, but depending on your use case it may seem irrelevant) difference between how they actually work and what Microsoft's API said about them. This bug is fixed... in Microsoft's own version control, not in released Windows versions. Specifically SRWLocks may silently give you a Write Lock, even if you asked only for a Read Lock, in the case where the lock was just released at the moment you asked. If you were expecting other threads to also get a read lock, which would ordinarily be possible - too bad, you've secretly been given the exclusive write lock so read locks are unavailable until you release it. The actual reason seems to be this: SRWLocks are small (a single pointer, with some low bits stolen to hide metadata) and the authors forgot that they actually know (because it's a different function call) whether you asked for a read or a write lock. Since they didn't have anywhere to store this single bit (read or write) they just assumed they don't know in this edge case where the lock happens to be available immediately, and since they "don't know" they always give you a write lock anyway. Oops. [Edited to make minor clarifications]

forrestthewoods 2y ago
> Specifically SRWLocks may silently give you a Write Lock, even if you asked only for a Read Lock, in the case where the lock was just released at the moment you asked. Oh hey, I reported that bug and behavior! One of my proudest reports. Not too often you find a legit bug, or at least documentation oversight, in such a core API.
- tialaramex 2y ago
  Yeah, I've also only very rarely seen real bugs in core system features (deadlock inside glibc's allocator a decade or more ago in my case IIRC) and I must say you got a much healthier reaction. It's definitely an actual bug not a doc bug. I've explained this a few times to people and it does seem like the natural inclination is to assume SRWLock must be supposed to do that, but I was glad to see internally Microsoft did fix this, because it's clearly the Wrong Thing™. I see two common defences for this bug. One is "Actually, it's supposed to be unfair, you don't understand why that's a good idea". Which assumes I'm expecting a fair lock and I'm unhappy not to get it. Giving a reader the reader lock when there's a writer waiting would be unfair - and probably a bad idea but I'm open to it if somebody presents benchmarks - but giving them the writer lock is just a bug. Another is "Actually, there is a writer waiting, and this way that writer gets the lock faster". As you wrote the example code you know that's false, there is no writer waiting, there are only readers and (in the buggy scenario) they're blocked forever for no reason.

skoocda 2y ago

I've done a precursory skim of this and plan to start reading it in earnest next week. Looks comprehensive and accessible. Very excited.

quohort 2y ago

Why do programming books always have some random unrelated illustration on the front? Usually when you have a textbook, they will have some nice illustration that is tangentially related to the content of the book (like fibonacci spiral for a math book or some chemical reaction for a chemistry book for example). But I suppose that there isn't really such an equivalent unless it's a computer graphics book. I guess it's also like how every project has to have its own "cutesey" mascot.

otteromkram 2y ago
Yeah, especially that persnickety, "The Programming Language" book. Talk about obscure covers! /s I think it's just an O'Reilly thing. It keeps the people guessing. Actually, the covers also make the books easily recognizable. Animals, statues, etc., are all good memory association drivers.
self_awareness 2y ago
This is mostly an O'Reilly thing. https://www.oreilly.com/content/a-short-history-of-the-oreilly-animals/ https://www.oreilly.com/content/a-short-history-of-the-oreil... TL;DR: > Some of the people at O’Reilly were taken aback: they thought the animals were weird, ugly, and a bit scary. But Tim [O'Reilly] got it immediately—he liked the quirkiness of the animals, thought it would help to make the books stand out from other publishers’ offerings—and it just felt right. They even have a browser which helps you identify the animal: https://www.oreilly.com/animals.csp https://www.oreilly.com/animals.csp

pythops 2y ago

Amazing book !

bk496 2y ago

Why can't they distribute the edition as a PDF?

andrew_eu 2y ago

It's an excellent book and I agree with many of the comments -- while it's written for Rust, the vast majority of it is applicable to many languages. It's amazing to see the book published on their website for free (though I am still happy in having bought the book). One thing I found lacking in the book were the examples. It has tons, but all of them are extremely focused on the topic they are illustrating and most feel very contrived. Would anyone here have a suggestion for a small/medium-sized project (weekend sized) which would actually use the patterns discussed in the book?

volonoctu 2y ago

Really good book and fairly comprehensive like a course. Probably has the best explanation of memory ordering. The 'build your own' teaching method is useful for understanding how the different data structures work.