4 ms·

Volatiles Are Miscompiled, and What to Do about It [pdf]

58 points by emkemp 13y ago

infogulch 13y ago
Quote from intro: "Although the symptoms of this compiler bug—spurious periodic reboots due to failure to reset the watchdog timer—may be relatively benign, the situation could be worse, for example, if the hardware register were used to lower control rods, cancel a missile launch, or open the pod bay doors." So that's what the problem was with those pod bay doors.
rjzzleep 13y ago
so, is this kind of quickcheck for c code generators? i'm a little surprised at how much worse clang fared.
- lstamour 13y ago
  Note the article was written in 2008 and clang was first released in 2007. "LLVM 2.2 was released on February 11, 2008, and LLVM r53339 is a snapshot of the source code from July 9, 2008." They later in that paragraph describe the improvements in clang over such a short time. Also, it seems there are quite a few compiler bugs being found, even today. This looks like a very productive field of study, though the same could likely be said for software correctness in general. http://blog.regehr.org/archives/1061 http://blog.regehr.org/archives/1061 This particular paper's software (its modern equivalent) is at https://github.com/csmith-project/voltest https://github.com/csmith-project/voltest
kenrose 13y ago
Looking at the generated code for their watchdog example and their workaround of forcing a function evaluation, it looks like the common cause of this bug amongst all of the compilers is the optimizer not respecting volatile. It's easy to understand how this could be the case. Imagine you work on a production quality C compiler. The pedestrian pieces (e.g., lexer, parser, AST) have been stable forever. The piece that you're very likely going to be working on is the optimizer (or maybe the code generator) to make use of new techniques or new instructions. While you're going about your business, you're probably not thinking about that arcane corner of the C language spec that discusses volatile. What's more, when you finally complete your feature, all of the compiler's test suites pass because there's insufficient coverage for volatile. The biggest contribution of this paper, besides the fact that it identified this issue across various compilers, is the notion of access summary testing and advocating for it to be included as part of the test suite for C compilers.
- jrockway 13y ago
  At least gcc's generated code has no possibility of working at all, and the system will reboot in a loop the first time it's powered up. So you're only 30 seconds away from finding that bug. (Of course, once you notice that the watchdog is being triggered it's going to be several hours of debugging before you realize that your compiler just optimized out the check.)
  - kenrose 13y ago
    Hours of debugging? Days even! Really, how often when you encounter a bug do you think it's a compiler bug? Never. It can't be. Compiler writers are infalliable. You'll first think it's your program, or maybe you misunderstood how volatile works, so you'll read the spec again. You'll write a poodle to isolate the problem. That will reboot each time too. Then you'll think it's some odd race condition related to volatile. But you're just doing a load and a store. The reboot happens every time, OK, that's promising. Then maybe, MAYBE, if you're awesome, you'll think to look at the generated assembly. And when you realize you have a no-op, you'll start to think if you maybe inadvertently specified something wrong in your -O parameters. Because how could the compiler be wrong? It's never wrong. Code generation bugs are the worst.
    - mikeash 13y ago
      I think it depends on how many compiler bugs you've previously encountered. I'm starting to suspect them more easily, these days. Practice at tracking them down has also made it easier to act on that suspicion. The thought of a compiler bug often gets people to throw up their hands in despair, but it's not so bad: just carefully verify the assembly output and see if it's actually correct. If it's not, then figure out some reasonably reliable way to tweak your code to avoid the bug (after you file a bug with the compiler people). Blaming the compiler (or the hardware or the OS or...) is only a problem if you do so without investigating to see if your blame is well placed. Once you can investigate properly, then it's just another possibility in your bag of tricks.
      - 13y ago
DannyBee 13y ago
This paper misstates the proper behavior of volatile to start In particular, it says "For every read from or write to a volatile variable that would be performed by a straightforward interpreter for C, exactly one load from or store to the memory location(s) allocated to the variable must be performed." This is wrong. It later kind of gets it right for C, explaining about sequence points, but it entirely misses that implementations are free to combine and eliminate multiple volatile accesses within the same sequence point. Now certainly, most of what was reported were genuine bugs (and John reports a lot of correctness issues). But it does/did nobody favors to start with an incorrect definition.
- cnvogel 13y ago
  I think if you replace "straightforward interpreter for C" with the "abstract state machine" in the standard (I'm looking at ISO/IEC 9899:1999 right now), at least the first half of the sentence you qoute it's pretty much what the standard says: ❝An object that has volatile-qualified type may be modified in ways unknown to the implementation or have other unknown side effects. Therefore any expression referring to such an object shall be evaluated strictly according to the rules of the abstract machine...❞ (§6.7.3) For combining multiple volatile accesses within the same statement, I think I cannot find an answer in the standard.
zurn 13y ago
Related: https://www.kernel.org/doc/Documentation/volatile-considered-harmful.txt https://www.kernel.org/doc/Documentation/volatile-considered... Sounds like "volatile" variables don't really provide good semantics for most uses even without considering compiler bugs, so it's better to just use explicit load and store macros or functions.
- acqq 13y ago
  That is the reason the compilers mostly didn't care: the semantics of the language "volatile" is seldom what is needed "in the real world programs."
  - avian 13y ago
    As the paper notes in the introduction, "volatile" is heavily used in embedded software where synchronization primitives like kernel's spinlocks aren't readily available. The "buffer_ready" in the paper is a very good example that I have seen many times in the real world. If anyone can share the "better solution" that avoids "volatile" (and works on a bare-bone ARM microcontroller for example), I would love to see it.
    - _delirium 13y ago
      The "buffer_ready" example was given as an incorrect use, though, which won't necessarily work even in a standards-conforming compiler, because the semantics of volatile don't forbid reordering the loop (which has no volatile accesses) to go after the buffer_ready write.
    - cnvogel 13y ago
      The solution to this problem is a memory barrier. The short version of such a barrier is: Define a class of transactions (e.g. memory writes). Then all transactions before the barrier must conclude before any transaction after the barrier starts. But this doesn't give you any guarantee about transactions of other types. http://en.wikipedia.org/wiki/Memory_barrier http://en.wikipedia.org/wiki/Memory_barrier https://www.kernel.org/doc/Documentation/memory-barriers.txt https://www.kernel.org/doc/Documentation/memory-barriers.txt

58 points by emkemp 13y ago

Quote from intro: "Although the symptoms of this compiler bug—spurious periodic reboots due to failure to reset the watchdog timer—may be relatively benign, the situation could be worse, for example, if the hardware register were used to lower control rods, cancel a missile launch, or open the pod bay doors." So that's what the problem was with those pod bay doors.

rjzzleep 13y ago

so, is this kind of quickcheck for c code generators? i'm a little surprised at how much worse clang fared.

lstamour 13y ago
Note the article was written in 2008 and clang was first released in 2007. "LLVM 2.2 was released on February 11, 2008, and LLVM r53339 is a snapshot of the source code from July 9, 2008." They later in that paragraph describe the improvements in clang over such a short time. Also, it seems there are quite a few compiler bugs being found, even today. This looks like a very productive field of study, though the same could likely be said for software correctness in general. http://blog.regehr.org/archives/1061 http://blog.regehr.org/archives/1061 This particular paper's software (its modern equivalent) is at https://github.com/csmith-project/voltest https://github.com/csmith-project/voltest

kenrose 13y ago

Looking at the generated code for their watchdog example and their workaround of forcing a function evaluation, it looks like the common cause of this bug amongst all of the compilers is the optimizer not respecting volatile. It's easy to understand how this could be the case. Imagine you work on a production quality C compiler. The pedestrian pieces (e.g., lexer, parser, AST) have been stable forever. The piece that you're very likely going to be working on is the optimizer (or maybe the code generator) to make use of new techniques or new instructions. While you're going about your business, you're probably not thinking about that arcane corner of the C language spec that discusses volatile. What's more, when you finally complete your feature, all of the compiler's test suites pass because there's insufficient coverage for volatile. The biggest contribution of this paper, besides the fact that it identified this issue across various compilers, is the notion of access summary testing and advocating for it to be included as part of the test suite for C compilers.

jrockway 13y ago
At least gcc's generated code has no possibility of working at all, and the system will reboot in a loop the first time it's powered up. So you're only 30 seconds away from finding that bug. (Of course, once you notice that the watchdog is being triggered it's going to be several hours of debugging before you realize that your compiler just optimized out the check.)
- kenrose 13y ago
  Hours of debugging? Days even! Really, how often when you encounter a bug do you think it's a compiler bug? Never. It can't be. Compiler writers are infalliable. You'll first think it's your program, or maybe you misunderstood how volatile works, so you'll read the spec again. You'll write a poodle to isolate the problem. That will reboot each time too. Then you'll think it's some odd race condition related to volatile. But you're just doing a load and a store. The reboot happens every time, OK, that's promising. Then maybe, MAYBE, if you're awesome, you'll think to look at the generated assembly. And when you realize you have a no-op, you'll start to think if you maybe inadvertently specified something wrong in your -O parameters. Because how could the compiler be wrong? It's never wrong. Code generation bugs are the worst.
  - mikeash 13y ago
    I think it depends on how many compiler bugs you've previously encountered. I'm starting to suspect them more easily, these days. Practice at tracking them down has also made it easier to act on that suspicion. The thought of a compiler bug often gets people to throw up their hands in despair, but it's not so bad: just carefully verify the assembly output and see if it's actually correct. If it's not, then figure out some reasonably reliable way to tweak your code to avoid the bug (after you file a bug with the compiler people). Blaming the compiler (or the hardware or the OS or...) is only a problem if you do so without investigating to see if your blame is well placed. Once you can investigate properly, then it's just another possibility in your bag of tricks.
    - 13y ago

DannyBee 13y ago

This paper misstates the proper behavior of volatile to start In particular, it says "For every read from or write to a volatile variable that would be performed by a straightforward interpreter for C, exactly one load from or store to the memory location(s) allocated to the variable must be performed." This is wrong. It later kind of gets it right for C, explaining about sequence points, but it entirely misses that implementations are free to combine and eliminate multiple volatile accesses within the same sequence point. Now certainly, most of what was reported were genuine bugs (and John reports a lot of correctness issues). But it does/did nobody favors to start with an incorrect definition.

cnvogel 13y ago
I think if you replace "straightforward interpreter for C" with the "abstract state machine" in the standard (I'm looking at ISO/IEC 9899:1999 right now), at least the first half of the sentence you qoute it's pretty much what the standard says: ❝An object that has volatile-qualified type may be modified in ways unknown to the implementation or have other unknown side effects. Therefore any expression referring to such an object shall be evaluated strictly according to the rules of the abstract machine...❞ (§6.7.3) For combining multiple volatile accesses within the same statement, I think I cannot find an answer in the standard.

zurn 13y ago

Related: https://www.kernel.org/doc/Documentation/volatile-considered-harmful.txt https://www.kernel.org/doc/Documentation/volatile-considered... Sounds like "volatile" variables don't really provide good semantics for most uses even without considering compiler bugs, so it's better to just use explicit load and store macros or functions.

acqq 13y ago
That is the reason the compilers mostly didn't care: the semantics of the language "volatile" is seldom what is needed "in the real world programs."
- avian 13y ago
  As the paper notes in the introduction, "volatile" is heavily used in embedded software where synchronization primitives like kernel's spinlocks aren't readily available. The "buffer_ready" in the paper is a very good example that I have seen many times in the real world. If anyone can share the "better solution" that avoids "volatile" (and works on a bare-bone ARM microcontroller for example), I would love to see it.
  - _delirium 13y ago
    The "buffer_ready" example was given as an incorrect use, though, which won't necessarily work even in a standards-conforming compiler, because the semantics of volatile don't forbid reordering the loop (which has no volatile accesses) to go after the buffer_ready write.
  - cnvogel 13y ago
    The solution to this problem is a memory barrier. The short version of such a barrier is: Define a class of transactions (e.g. memory writes). Then all transactions before the barrier must conclude before any transaction after the barrier starts. But this doesn't give you any guarantee about transactions of other types. http://en.wikipedia.org/wiki/Memory_barrier http://en.wikipedia.org/wiki/Memory_barrier https://www.kernel.org/doc/Documentation/memory-barriers.txt https://www.kernel.org/doc/Documentation/memory-barriers.txt