9 ms·

How to trigger races reliably in the Linux kernel

113 points by sohkamyung 7y ago

chrisseaton 7y ago
> Race condition, in terms of a computer programming, is a bug where two pieces of code cause an error if executed concurrently. This article makes the common mistake of saying that a race condition is inherently a bug. A race condition just means that observable program behaviour is dependent on the interleaving of two tasks. A race condition is only a bug if you don't want one of the possible interleavings. You can often find great performance optimisations by working out how to work with race conditions rather than disallowing them.
- wiremine 7y ago
  I was about to say "that's wrong!" but checked the Wikipedia article on it. [1] Thanks! I learned something today: I always thought it was a bug. [1] https://en.wikipedia.org/wiki/Race_condition https://en.wikipedia.org/wiki/Race_condition
  - MiroF 7y ago
    I do not think that this is a settled issue in any way- there are quite a few people who do not use race condition to mean what wiki says. Indeed, there is even a debate about this issue in the talk page of wikipedia [https://en.wikipedia.org/wiki/Talk:Race_condition#Race_conditions_between_systems https://en.wikipedia.org/wiki/Talk:Race_condition#Race_condi...]
    - chrisseaton 7y ago
      I didn't link to Wikipedia myself - and I don't know what knowledge these people posting comments have - maybe they know more than I do - but I'd normally refer people to the Encyclopedia of Parallel Computing as the field's authoritative reference. It's written by a large number of experts and edited by an acknowledged leader in the field. https://link.springer.com/referenceworkentry/10.1007%2F978-0-387-09766-4_36 https://link.springer.com/referenceworkentry/10.1007%2F978-0... It says "Race conditions that can cause unintended non-determinacy are programming errors." and provides 23 references to the literature that you can follow for more history on it.
      - MiroF 7y ago
        That's a good reference and I'll definitely look to that going forward. Worth noting however, that the first article I found in those 23 references that actually used the phrase 'race condition' (in "What are race conditions? Some issues and formalizations") explicitly stated: > However, in the literature, there seems to be little agreement as to precisely what constitutes a race condition. Indeed, two different notions have been used, but the distinction between them has not been previously recognized. Because no consistent terminology has appeared, several terms have been used with different intended meanings... [0] Further, > Data races cause nonatomic execution of critical sections and are failures in (nondeterministic) programs All I'm trying to suggest is that colloquially, people will use this phrase to mean a lot of things, and I'm not sure the literature is entirely clear cut. [0]: https://dl.acm.org/doi/pdf/10.1145/130616.130623 https://dl.acm.org/doi/pdf/10.1145/130616.130623
        chrisseaton 7y ago
        > Data races... Yes data races are always bugs, according to Padua et al.
- adtac 7y ago
  is there any situation where a data race might be useful or accommodatable?
  - bflesch 7y ago
    Querying multiple backends and responding with the data that has been received first. Not sure if this technique is really in use, but I figure this could be an optimization for dns queries and the like.
    - Znafon 7y ago
      This is exactly how the "Happy Eyeballs" algorithm in RFC 8305 works: https://en.wikipedia.org/wiki/Happy_Eyeballs https://en.wikipedia.org/wiki/Happy_Eyeballs
    - PudgePacket 7y ago
      Definitely in use, I know at least Google does this internally.
  - chrisseaton 7y ago
    For example, some profilers that count the number of times something is run will update a counter without any synchronisation. This risks lost updates, but since you really just need to know if the counter is very low or very high a few lost updates here or there don't really matter. But I think from some accepted definitions (such as Padua et al) a data race specifically is a bug, so this data interleaving if we're happy with it isn't a data race because it isn't a bug.
    - jfkebwjsbx 7y ago
      +1, at $DAYJOB we use intentional data races all the time for similar purposes.
    - robocat 7y ago
      > a few lost updates here or there don't really matter jerf disagrees in last sentence of other comment: https://news.ycombinator.com/item?id=23079788 https://news.ycombinator.com/item?id=23079788
- _nalply 7y ago
  In other words, for Rust you'll need unsafe to exploit race conditions for performance optimisations.
  - zozbot234 7y ago
    Safe Rust only protects against data races (which imply memory unsafety, hence a "bug") not general race conditions.
    - jfkebwjsbx 7y ago
      Data races don't imply memory unsafety (in the sense of having OOB accesses etc.). It is possible (and in rare cases, desirable) to have data races while still having a perfectly safe program.
      - ChrisSD 7y ago
        Could you explain that? Surely either it's dangerous to read and write simultaneously to a memory location or the operations are atomic (albeit perhaps unordered) and thus there is no data race?
        zozbot234 7y ago
        Well, your memory model might fail to properly expose "atomic" access at the level you're actually relying on to prove that your 'data race' is safe. (Or using such fine-grained atomic accesses might have bad performance implications that can't be worked around using relaxed operations, etc.) But I don't think that's going to be a common case.
        ChrisSD 7y ago
        But any optimizing compiler is surely going to assume its memory model is adhered to, no? Therefore any "data races" will be undefined behaviour (even if they're atomic on physical hardware).
- jerf 7y ago
  While true, it is still generally a mistake to leave a race condition in your code, because your human understanding of the possible interleavings is very unlikely to be correct. In addition to the way the code appears to be written, understanding the impact of a race condition requires you to fully understand the memory model in play, fully understanding all compiler optimizations that may have been made, which may include instruction reordering, fully understand all memory alignment issues on all machines you may execute this on and all their little differences, including on machines that don't exist yet that your code may run on in the future, and fully understand the entire stack of code involved in the race condition from the level of abstraction you're using pretty much all the way down to the compiled and optimized assembler. It also makes testing harder... all kinds of testing, automated and otherwise, because whether or not your tests can get to a given part of the state space becomes nondeterministic. The average developer assessment that some race condition is completely harmless is wrong; there's usually a bug in the complicated state space somewhere. A performance optimization involving a deliberate race condition should be pretty much your last resort. Even the obvious ones are often less of a good idea than they may look, like a leaky incrementing counter for logging purposes. You might model that as being unlikely to lose more than a couple of percent, but I've seen cases where it lost the majority of logged events. Granted, this probably won't crash your program, but it can still result in surprisingly deceptive logging.
  - jfkebwjsbx 7y ago
    Not all race conditions are as complex as you make them to be, in particular if they are done on purpose. And many race conditions don't have anything to do with the memory model or compiler optimizations.
    - MaxBarraclough 7y ago
      > And many race conditions don't have anything to do with the memory model or compiler optimizations. For example, poorly structured response-handlers in JavaScript. If the code assumes that request R1 always returns before request R2, things may misbehave if that assumption is violated. That's a race condition, but as you say, it's nothing to do with memory models or compiler trickery, as JavaScript gives you just the one thread (not counting workers).
- pjc50 7y ago
  I feel that leaning on a formal definition of a term in a way that's different from the normal usage that only matters in very rare circumstances is sniping rather than communication. You're only doing this so you can call it a mistake. Especially since you've not provided any examples. (Code that is proven to work correctly without using synchronisation primitives, ie across the possible interleavings, is generally called "lock free") Scheduler-dependent behaviour ends up being an absolute nightmare for automated testing and hunting of other bugs. It's not unreasonable to declare that all race conditions are bugs just for that reason.
  - chrisseaton 7y ago
    What terminology do you use to describe something that is non-deterministic due to timing, but correct? I use 'race condition', but if you reserve that for something with bugs you'll need to invent a new term for the benign version.
    - dnautics 7y ago
      Since pjc wanted a example that isn't explicitly a bug (a 'benign' race condition) I'll provide one that can be a major pita, two concurrent tasks are logging their event stream. Logs may not hit in exactly the order that you expect in your mind, forcing you to stop and think each time you're going over the logs. Definitely a race condition. Definitely expected behaviour. Not sure you can call that a bug. More than once in my life I have thought that this was a bug, tried to correct it, and introduced another bug, followed by teeth gnashing, hair pulling, swearing, and then a revert.
    - amenod 7y ago
      > ...is generally called "lock free"
      - chrisseaton 7y ago
        No that doesn't always apply. Think of two worker threads pushing entires to a synchronised log. It's non-deterministic which order they arrive in the log, as different schedulings and other things will cause the threads to run in different orders (they 'race' to put entries in the log, we say), but it's not a bug, and it's not lock-free because the log is synchronised.
- pdonis 7y ago
  > This article makes the common mistake of saying that a race condition is inherently a bug. No, it defines race condition, for purposes of the article, as something which is a bug. The author is only concerned with cases in which non-deterministic behavior causes errors. When you write your own article, you are free to define "race condition" to include non-deterministic behavior that does not cause errors. But I don't think you can claim that the author's usage is simply wrong.
klysm 7y ago
If you manage to reproduce a race, is there some way to capture exactly what the scheduler did and force it to do that again?
- jfk13 7y ago
  For debugging purposes, for example? You might be interested in https://rr-project.org https://rr-project.org.
  - throwaway2048 7y ago
    rr isn't going to work on a kernel.
    - Hello71 7y ago
      I'm inclined to say that it will work on User Mode Linux, and it looks like QEMU does have record/replay functionality.
      - loeg 7y ago
        Yes, it works as long as you don't have any real devices that cannot be captured in a reverse-debugger's state history.
      - ndesaulniers 7y ago
        That won't help with data races in drivers. MMIO can even race and isn't well specified.
- muricula 7y ago
  Try reproducing the race under an emulator like bochs. Bochs can be made fully deterministic, and you can take a snapshot at the beginning of the race and reproduce it every time from the snapshot. One downside is that bochs is very slow.
loeg 7y ago
In the FreeBSD kernel, we've got fail(9) for this exact use (since 2009). Check out the EXAMPLES section of the manual page. You can use the mechanisms to inject delay on some percentage of executions, and more generally some integer value can be injected, which can be used to simulate device failures (EIO) or whatever. It's very powerful for creating reliable reproducers for all kinds of failures, including race conditions. And the KPI is not quite as verbose as the one presented in TFA. https://www.freebsd.org/cgi/man.cgi?query=fail&sektion=9 https://www.freebsd.org/cgi/man.cgi?query=fail&sektion=9
EvgeniyZh 7y ago
there is a gsoc project regarding race conditions in Linux https://summerofcode.withgoogle.com/projects/#6540063556501504 https://summerofcode.withgoogle.com/projects/#65400635565015...
georgianar 7y ago
This kind Man brought my Lover back In less than 3 days, i saw wonders, my Lover came back to me and my life got back just like a completed puzzle… am so happy.. thanks to Robinsonbucler@ { gmail }. com for saving my life. Mr Robinson is the best I’ve ever met! Thanks, thanks thanks_____________

113 points by sohkamyung 7y ago

> Race condition, in terms of a computer programming, is a bug where two pieces of code cause an error if executed concurrently. This article makes the common mistake of saying that a race condition is inherently a bug. A race condition just means that observable program behaviour is dependent on the interleaving of two tasks. A race condition is only a bug if you don't want one of the possible interleavings. You can often find great performance optimisations by working out how to work with race conditions rather than disallowing them.

wiremine 7y ago
I was about to say "that's wrong!" but checked the Wikipedia article on it. [1] Thanks! I learned something today: I always thought it was a bug. [1] https://en.wikipedia.org/wiki/Race_condition https://en.wikipedia.org/wiki/Race_condition
- MiroF 7y ago
  I do not think that this is a settled issue in any way- there are quite a few people who do not use race condition to mean what wiki says. Indeed, there is even a debate about this issue in the talk page of wikipedia [https://en.wikipedia.org/wiki/Talk:Race_condition#Race_conditions_between_systems https://en.wikipedia.org/wiki/Talk:Race_condition#Race_condi...]
  - chrisseaton 7y ago
    I didn't link to Wikipedia myself - and I don't know what knowledge these people posting comments have - maybe they know more than I do - but I'd normally refer people to the Encyclopedia of Parallel Computing as the field's authoritative reference. It's written by a large number of experts and edited by an acknowledged leader in the field. https://link.springer.com/referenceworkentry/10.1007%2F978-0-387-09766-4_36 https://link.springer.com/referenceworkentry/10.1007%2F978-0... It says "Race conditions that can cause unintended non-determinacy are programming errors." and provides 23 references to the literature that you can follow for more history on it.
    - MiroF 7y ago
      That's a good reference and I'll definitely look to that going forward. Worth noting however, that the first article I found in those 23 references that actually used the phrase 'race condition' (in "What are race conditions? Some issues and formalizations") explicitly stated: > However, in the literature, there seems to be little agreement as to precisely what constitutes a race condition. Indeed, two different notions have been used, but the distinction between them has not been previously recognized. Because no consistent terminology has appeared, several terms have been used with different intended meanings... [0] Further, > Data races cause nonatomic execution of critical sections and are failures in (nondeterministic) programs All I'm trying to suggest is that colloquially, people will use this phrase to mean a lot of things, and I'm not sure the literature is entirely clear cut. [0]: https://dl.acm.org/doi/pdf/10.1145/130616.130623 https://dl.acm.org/doi/pdf/10.1145/130616.130623
      - chrisseaton 7y ago
        > Data races... Yes data races are always bugs, according to Padua et al.
adtac 7y ago
is there any situation where a data race might be useful or accommodatable?
- bflesch 7y ago
  Querying multiple backends and responding with the data that has been received first. Not sure if this technique is really in use, but I figure this could be an optimization for dns queries and the like.
  - Znafon 7y ago
    This is exactly how the "Happy Eyeballs" algorithm in RFC 8305 works: https://en.wikipedia.org/wiki/Happy_Eyeballs https://en.wikipedia.org/wiki/Happy_Eyeballs
  - PudgePacket 7y ago
    Definitely in use, I know at least Google does this internally.
- chrisseaton 7y ago
  For example, some profilers that count the number of times something is run will update a counter without any synchronisation. This risks lost updates, but since you really just need to know if the counter is very low or very high a few lost updates here or there don't really matter. But I think from some accepted definitions (such as Padua et al) a data race specifically is a bug, so this data interleaving if we're happy with it isn't a data race because it isn't a bug.
  - jfkebwjsbx 7y ago
    +1, at $DAYJOB we use intentional data races all the time for similar purposes.
  - robocat 7y ago
    > a few lost updates here or there don't really matter jerf disagrees in last sentence of other comment: https://news.ycombinator.com/item?id=23079788 https://news.ycombinator.com/item?id=23079788
_nalply 7y ago
In other words, for Rust you'll need unsafe to exploit race conditions for performance optimisations.
- zozbot234 7y ago
  Safe Rust only protects against data races (which imply memory unsafety, hence a "bug") not general race conditions.
  - jfkebwjsbx 7y ago
    Data races don't imply memory unsafety (in the sense of having OOB accesses etc.). It is possible (and in rare cases, desirable) to have data races while still having a perfectly safe program.
    - ChrisSD 7y ago
      Could you explain that? Surely either it's dangerous to read and write simultaneously to a memory location or the operations are atomic (albeit perhaps unordered) and thus there is no data race?
      - zozbot234 7y ago
        Well, your memory model might fail to properly expose "atomic" access at the level you're actually relying on to prove that your 'data race' is safe. (Or using such fine-grained atomic accesses might have bad performance implications that can't be worked around using relaxed operations, etc.) But I don't think that's going to be a common case.
        ChrisSD 7y ago
        But any optimizing compiler is surely going to assume its memory model is adhered to, no? Therefore any "data races" will be undefined behaviour (even if they're atomic on physical hardware).
jerf 7y ago
While true, it is still generally a mistake to leave a race condition in your code, because your human understanding of the possible interleavings is very unlikely to be correct. In addition to the way the code appears to be written, understanding the impact of a race condition requires you to fully understand the memory model in play, fully understanding all compiler optimizations that may have been made, which may include instruction reordering, fully understand all memory alignment issues on all machines you may execute this on and all their little differences, including on machines that don't exist yet that your code may run on in the future, and fully understand the entire stack of code involved in the race condition from the level of abstraction you're using pretty much all the way down to the compiled and optimized assembler. It also makes testing harder... all kinds of testing, automated and otherwise, because whether or not your tests can get to a given part of the state space becomes nondeterministic. The average developer assessment that some race condition is completely harmless is wrong; there's usually a bug in the complicated state space somewhere. A performance optimization involving a deliberate race condition should be pretty much your last resort. Even the obvious ones are often less of a good idea than they may look, like a leaky incrementing counter for logging purposes. You might model that as being unlikely to lose more than a couple of percent, but I've seen cases where it lost the majority of logged events. Granted, this probably won't crash your program, but it can still result in surprisingly deceptive logging.
- jfkebwjsbx 7y ago
  Not all race conditions are as complex as you make them to be, in particular if they are done on purpose. And many race conditions don't have anything to do with the memory model or compiler optimizations.
  - MaxBarraclough 7y ago
    > And many race conditions don't have anything to do with the memory model or compiler optimizations. For example, poorly structured response-handlers in JavaScript. If the code assumes that request R1 always returns before request R2, things may misbehave if that assumption is violated. That's a race condition, but as you say, it's nothing to do with memory models or compiler trickery, as JavaScript gives you just the one thread (not counting workers).
pjc50 7y ago
I feel that leaning on a formal definition of a term in a way that's different from the normal usage that only matters in very rare circumstances is sniping rather than communication. You're only doing this so you can call it a mistake. Especially since you've not provided any examples. (Code that is proven to work correctly without using synchronisation primitives, ie across the possible interleavings, is generally called "lock free") Scheduler-dependent behaviour ends up being an absolute nightmare for automated testing and hunting of other bugs. It's not unreasonable to declare that all race conditions are bugs just for that reason.
- chrisseaton 7y ago
  What terminology do you use to describe something that is non-deterministic due to timing, but correct? I use 'race condition', but if you reserve that for something with bugs you'll need to invent a new term for the benign version.
  - dnautics 7y ago
    Since pjc wanted a example that isn't explicitly a bug (a 'benign' race condition) I'll provide one that can be a major pita, two concurrent tasks are logging their event stream. Logs may not hit in exactly the order that you expect in your mind, forcing you to stop and think each time you're going over the logs. Definitely a race condition. Definitely expected behaviour. Not sure you can call that a bug. More than once in my life I have thought that this was a bug, tried to correct it, and introduced another bug, followed by teeth gnashing, hair pulling, swearing, and then a revert.
  - amenod 7y ago
    > ...is generally called "lock free"
    - chrisseaton 7y ago
      No that doesn't always apply. Think of two worker threads pushing entires to a synchronised log. It's non-deterministic which order they arrive in the log, as different schedulings and other things will cause the threads to run in different orders (they 'race' to put entries in the log, we say), but it's not a bug, and it's not lock-free because the log is synchronised.
pdonis 7y ago
> This article makes the common mistake of saying that a race condition is inherently a bug. No, it defines race condition, for purposes of the article, as something which is a bug. The author is only concerned with cases in which non-deterministic behavior causes errors. When you write your own article, you are free to define "race condition" to include non-deterministic behavior that does not cause errors. But I don't think you can claim that the author's usage is simply wrong.

klysm 7y ago

If you manage to reproduce a race, is there some way to capture exactly what the scheduler did and force it to do that again?

jfk13 7y ago
For debugging purposes, for example? You might be interested in https://rr-project.org https://rr-project.org.
- throwaway2048 7y ago
  rr isn't going to work on a kernel.
  - Hello71 7y ago
    I'm inclined to say that it will work on User Mode Linux, and it looks like QEMU does have record/replay functionality.
    - loeg 7y ago
      Yes, it works as long as you don't have any real devices that cannot be captured in a reverse-debugger's state history.
    - ndesaulniers 7y ago
      That won't help with data races in drivers. MMIO can even race and isn't well specified.
muricula 7y ago
Try reproducing the race under an emulator like bochs. Bochs can be made fully deterministic, and you can take a snapshot at the beginning of the race and reproduce it every time from the snapshot. One downside is that bochs is very slow.

loeg 7y ago

In the FreeBSD kernel, we've got fail(9) for this exact use (since 2009). Check out the EXAMPLES section of the manual page. You can use the mechanisms to inject delay on some percentage of executions, and more generally some integer value can be injected, which can be used to simulate device failures (EIO) or whatever. It's very powerful for creating reliable reproducers for all kinds of failures, including race conditions. And the KPI is not quite as verbose as the one presented in TFA. https://www.freebsd.org/cgi/man.cgi?query=fail&sektion=9 https://www.freebsd.org/cgi/man.cgi?query=fail&sektion=9

EvgeniyZh 7y ago

there is a gsoc project regarding race conditions in Linux https://summerofcode.withgoogle.com/projects/#6540063556501504 https://summerofcode.withgoogle.com/projects/#65400635565015...

georgianar 7y ago

This kind Man brought my Lover back In less than 3 days, i saw wonders, my Lover came back to me and my life got back just like a completed puzzle… am so happy.. thanks to Robinsonbucler@ { gmail }. com for saving my life. Mr Robinson is the best I’ve ever met! Thanks, thanks thanks_____________