3 ms·

Its a bad idea to use a mutex inside of interrupt code. seq_cst / atomics / barriers are for writing lock-free code, which is fully compatible with interrupts

Its a bad idea to use a mutex inside of interrupt code. seq_cst / atomics / barriers are for writing lock-free code, which is fully compatible with interrupts and other system-call level details. Its about correctness, not about speed. -------- I had a discussion elsewhere where people seem to think that these constructs are for speed. They... really aren't. Atomics are about lock-free code, and lock-free code might be slower than locked-code/mutex code. Lock-free code is about forward progress in all conditions. Sometimes its faster, but its an independent axis as far as software design is concerned. I guess acquire is faster than seq_cst, and consume/relaxed would be even faster than acquire. But correctness comes first, and proving correctness in consume-style code is seemingly too difficult in practice. So acquire is where the sweet spot seems to be... at least with today's tech and understanding of multithreaded issues.

gpderetta 3y ago
The thing is, seq-cst does not guarantee correctness, far from it. And you write down a proof, using the happen-before rules, the acquire/release edges are fairly obvious. So I don't think seq-cst buys you a significant amount of safety.
kccqzy 3y ago
The whole construct of atomics is for speed. I've never seen an argument against it. On the contrary, there are plenty of misguided arguments for speed that doesn't hold in reality; badly written atomics is often slower than mutex. Lock-free code by itself doesn't guarantee forward progress. I've seen way too much atomic code where the author sprinkles a seemingly infinite loop that only breaks when compare_exchange_strong succeeds. How would you reason that those loops will in fact terminate? When you use a mutex, there are no loops anywhere. Afraid of deadlocks making in mutex code? There are many good deadlock detection tools that you can use without directly reasoning about each section of atomic code. That's infinitely better in terms of productivity.
- dragontamer 3y ago
  > Afraid of deadlocks making in mutex code? No. You literally cannot use a mutex in interrupt service routines. If you fail to understand why, then you don't understand fundamental OS and/or device driver issues and need to study up on that a bit more. This isn't something you use userland tools to solve either. You're arguing for a methodology in a use case where its literally impossible to use mutexes and/or locking. The only reasonable software engineering decision here is to write lock-free code with guarantees of forward progress in these situations. Its not easy. A lot of people mess it up. But that's what you have to do. No one ever said kernel hacking was easy. Someone has to write this code, and whoever does will likely use a lock-free methodology. This is where atomics and barriers shine. > Lock-free code by itself doesn't guarantee forward progress. I don't think you understand what lock-free code means. It literally means code that has guarantees for forward progress. Its very difficult to write lock-free code. Very, very difficult. But the methodology is well known and well documented. (https://preshing.com/20120612/an-introduction-to-lock-free-programming/ https://preshing.com/20120612/an-introduction-to-lock-free-p...) You use these guarantees of forward progress (ex: on a 128-core computer, if all are doing compare_exchange_strong at the same time, then 1x of them will succeed, and 127x of them will fail. This is guaranteed, _SOMEONE_ succeeds and makes forward progress with lock-free primitives like compare_exchange_strong). That means that if all 128x threads/cores call "compare_exchange_strong" 1x each, then after 128x calls every thread will have succeeded (ie: worst case, one thread will have to call it 128x times). No. This isn't sufficient to have lock-free code yet. You now need to prove that you don't deal with live-lock issues or other such complex issues that come up (and you'll only get here in the first place if you wrote your memory-barriers correctly and lined everything else up perfectly). But its a start. And with enough effort, study, sweat and tears, you'll be able to write a lock-free something and have a good functioning interrupt service routine.
  - kccqzy 3y ago
    Ah I had a reading comprehension fail. I never noticed in your first sentence you said interrupt code. Well then I do not profess to understand much about that. > Lock-free code by itself doesn't guarantee forward progress. I think we have some definition differences here. What I have seen and have alluded to previously when you use tools like compare_exchange_strong is that the underlying machine does not guarantee forward progress. When you have 128 cores calling compare_exchange_strong at the same time, yes 1 of them will succeed and 127 of them will fail. But there is no guarantee that for a particular core, it will eventually succeed; it could always be among the 127 failing ones. I often see that on NUMA systems where many cores running on a single CPU are competing against one core running on a remote CPU. Due to the way hardware works, that remote CPU consistently takes longer to do each atomic operation, leading it to always fail. So no, after 128x calls not every thread will succeed.

gpderetta 3y ago

The thing is, seq-cst does not guarantee correctness, far from it. And you write down a proof, using the happen-before rules, the acquire/release edges are fairly obvious. So I don't think seq-cst buys you a significant amount of safety.

kccqzy 3y ago

The whole construct of atomics is for speed. I've never seen an argument against it. On the contrary, there are plenty of misguided arguments for speed that doesn't hold in reality; badly written atomics is often slower than mutex. Lock-free code by itself doesn't guarantee forward progress. I've seen way too much atomic code where the author sprinkles a seemingly infinite loop that only breaks when compare_exchange_strong succeeds. How would you reason that those loops will in fact terminate? When you use a mutex, there are no loops anywhere. Afraid of deadlocks making in mutex code? There are many good deadlock detection tools that you can use without directly reasoning about each section of atomic code. That's infinitely better in terms of productivity.

dragontamer 3y ago
> Afraid of deadlocks making in mutex code? No. You literally cannot use a mutex in interrupt service routines. If you fail to understand why, then you don't understand fundamental OS and/or device driver issues and need to study up on that a bit more. This isn't something you use userland tools to solve either. You're arguing for a methodology in a use case where its literally impossible to use mutexes and/or locking. The only reasonable software engineering decision here is to write lock-free code with guarantees of forward progress in these situations. Its not easy. A lot of people mess it up. But that's what you have to do. No one ever said kernel hacking was easy. Someone has to write this code, and whoever does will likely use a lock-free methodology. This is where atomics and barriers shine. > Lock-free code by itself doesn't guarantee forward progress. I don't think you understand what lock-free code means. It literally means code that has guarantees for forward progress. Its very difficult to write lock-free code. Very, very difficult. But the methodology is well known and well documented. (https://preshing.com/20120612/an-introduction-to-lock-free-programming/ https://preshing.com/20120612/an-introduction-to-lock-free-p...) You use these guarantees of forward progress (ex: on a 128-core computer, if all are doing compare_exchange_strong at the same time, then 1x of them will succeed, and 127x of them will fail. This is guaranteed, _SOMEONE_ succeeds and makes forward progress with lock-free primitives like compare_exchange_strong). That means that if all 128x threads/cores call "compare_exchange_strong" 1x each, then after 128x calls every thread will have succeeded (ie: worst case, one thread will have to call it 128x times). No. This isn't sufficient to have lock-free code yet. You now need to prove that you don't deal with live-lock issues or other such complex issues that come up (and you'll only get here in the first place if you wrote your memory-barriers correctly and lined everything else up perfectly). But its a start. And with enough effort, study, sweat and tears, you'll be able to write a lock-free something and have a good functioning interrupt service routine.
- kccqzy 3y ago
  Ah I had a reading comprehension fail. I never noticed in your first sentence you said interrupt code. Well then I do not profess to understand much about that. > Lock-free code by itself doesn't guarantee forward progress. I think we have some definition differences here. What I have seen and have alluded to previously when you use tools like compare_exchange_strong is that the underlying machine does not guarantee forward progress. When you have 128 cores calling compare_exchange_strong at the same time, yes 1 of them will succeed and 127 of them will fail. But there is no guarantee that for a particular core, it will eventually succeed; it could always be among the 127 failing ones. I often see that on NUMA systems where many cores running on a single CPU are competing against one core running on a remote CPU. Due to the way hardware works, that remote CPU consistently takes longer to do each atomic operation, leading it to always fail. So no, after 128x calls not every thread will succeed.