7 ms·

What Every C Programmer Should Know About Undefined Behavior (2011)

129 points by BuuQu9hu 10y ago

charles-salvia 10y ago
Not to mention that arithmetic operations (including division) that overflow signed integers result in undefined behavior.
- mnarayan01 10y ago
  That's mentioned in Part 1: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-....
new299 10y ago
Nice summary. If stability/security is important in your codebase. It's of course worth avoiding undefined behavior, and compiling with warnings as errors (-Werror in gcc). However it's also really worth running your test suite through Valgrind [1] too sometimes. This instruments your code to check for use for use of initialized variables/other non-deterministic behavior at runtime. I used to run this under continuous integration, and flag builds with issues. [1] http://valgrind.org/ http://valgrind.org/
- DSMan195276 10y ago
  I agree that all warnings should be generally be turned on and snuffed out (Though there are a few innocuous warnings that I turn off sometimes), however I wouldn't recommend the usage of -Werror to force that unless it's only enabled for dev builds. Warnings are generally impossible to fully predict: different compilers can give different warnings - from warnings enabled by default, warnings changed between versions, and warnings that differ between compilers. And of course, there's no wrong way for the compiler to do it because what to warn about is subjective in the first place. That can become really annoying for an end user looking to just compile and run your software, not debug why it fails to build because their setup outputs a warning somewhere that may not even be an error. And turning off -Werror tends to then require delving into Makefiles (or whatever other build system they chose to use), and at that point most people are probably just not going to bother and call it broken. Again, I'm not saying you shouldn't attempt to snuff out and find every warning that you can, but you shouldn't have your default build rely on compiling with no warnings. There's just too many variables uncounted for to expect your software to compile without warnings in every possible configuration. I also agree 100% with running test suites through valgrind - I do that as well and it's a very good way to guard against memory leaks being introduced (Of course, good structure and design techniques are always the best defense, but there's nothing wrong with a good check that things are doing good).
  - new299 10y ago
    Right, I think that's reasonable. Maybe just use it for debug or builds of test suites/CI builds.
  - ryandrake 10y ago
    Another reason to avoid -Werror is if you pull in third party code that you share your build options with. Even large stable open source projects regularly spew hundreds of warnings when you aggressively turn them on. I'll generally build my own code with all warnings, but use as close as I can to the package maintainer's build settings for their code. Even then, you can get warnings because the third party developer doesn't use your exact compiler.
- lomnakkus 10y ago
  AFAICT valgrind is mostly obsolete; use ASAN+UBSAN+... instead.
  - pjmlp 10y ago
    When gcc or clang are an option.
  - planteen 10y ago
    Is the thread sanitizer caught up to where valgrind (helgrind) was for detecting data races? I know a while back it wasn't but things may have changed.
- pjmlp 10y ago
  The problem with Valgrind is that not everyone is working on one of these platforms http://valgrind.org/info/platforms.html http://valgrind.org/info/platforms.html
  - abecedarius 10y ago
    It's also not enough. A medium-large program of mine that passed Valgrind had been working for years when it started blowing up on newer compiler releases. Maybe the newer static undefined-behavior analyses would have made that less of an awful pain, if they'd been available then.
- buserror 10y ago
  -Werror used to be the way to go, until compiler writers decided to add warnings for idiotic reasons. Like 'confusing indentation' or 'unused static const variables'. Seriously, these two are completely idiotic; why would the compiler decide that the fact I don't have a blank line 'might' be confusing? on whose criteria? Same with static const variables in C files. Lots of code is often #ifdef in/out, and lots of people would rather have a static const int than a #define!
  - mattkrause 10y ago
    The "confusing indentation" warning can be useful. For example, it would have flagged if ((err = SSLHashSHA1.update(&hashCtx, &signedParams)) != 0) goto fail; goto fail; Does any compiler try to indicate the severity of each warning. For example, using the value from an uninitialized variable is labeled as somehow "worse" than code-quality warnings like indentation or bare assignments inside conditionals?
oldgun 10y ago
Really nice summary of undefined behavior. Just realized this is posted by Chris Lattner himself.
mpweiher 10y ago
"You're holding it wrong", compiler-writer's version. IIRC, the Linux kernel has a rule that as a kernel developer, you are not allowed to break userspace, even if you think userspace is wrong. This is an apologia for why compiler writers think they should not have to be held to similar standards. The argument is always something along the lines that UB in the C standard means they get to do whatever they want, including such nonsense as eliminating entire loops because the last access is out of bounds or going down an if-else-branch other than what the if says. That this argumentation is specious in the extreme is shown by the fact that C compilers worked fine (and with less code breakages) before there even was a C standard, so all behavior was "UB". The unstated assumption is that the optimizations enabled by this are absolutely necessary. That overstates the importance of compiler optimizations in general, and certainly the importance of these particular optimizations. (see Proebsting's Law)[2]. There may be code-bases where these extra optimizations are beneficial or even essential, fine, let's add a -Ogoforit or -Oletsgocrazy flag. Rebuttal here: What every compiler writer should know about undefined behavior or "Optimization" based on undefined behavior hurts performance[1] Short summary is that this trend towards exploiting UB breaks a lot of code that has been working for decades, and the fixes required to bring them in-line with the new regime imposed in order to enable these new optimizations makes it slower than the old code without those optimization. Yay. [1] http://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_2015_submission_29.pdf http://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_201... [2] http://proebsting.cs.arizona.edu http://proebsting.cs.arizona.edu 'I may be best known for "Proebsting's Law", which asserts that compiler optimizations have yielded annual performance gains an order of magnitude worse than hardware performance gains. The law probably would have gone unnoticed had it not been for the protests by those receiving funds to do compiler optimization research.'
- haberman 10y ago
  Others have gone down this path and realized it's not as easy as it sounds: http://blog.regehr.org/archives/1287 http://blog.regehr.org/archives/1287
  - mpweiher 10y ago
    Yes, but it depends a lot what you consider "down this path". John's approach seemed to be to define the UB, and to me it looks like he found out why it was left as UB in the spec. Not exploiting the UB for optimizations in ways that break lots of code is actually trivially easy. We have been doing it for 30+ years and we just have to stop adding new optimizations that break, and possibly revert some of the ones that are already in there.
prodigal_erik 10y ago
Are these all undefined rather than merely unspecified or implementation-defined? I'm a little suspicious that they don't explain the difference, but I'm having trouble finding a definitive list of the places where the standard allows nasal demons.
- lomnakkus 10y ago
  They're undefined. (From a quick skim.) However, an implementation could define various UBs however it wants. The difference between "undefined" and "implement-defined" is really that an implementation doesn't have to anything even remotely sensible for "undefined" behavior, but it has do define some ("sensible") behavior for "implementation-defined" behavior. Usually, "implementation-defined" behavior also tends to remain consistent across versions whereas "undefined" behavior usually has no such constraints. For example, for "undefined" behavior, version 5.1.2.3 of the compiler may differ drastically from 5.1.2.4 in terms of optimizations which rely on UB.
  - Sharlin 10y ago
    Basically: Undefined - the compiler may assume this can never happen, and if it does happen, it can "poison" the whole execution including whatever logically happens before the undefined part. Unspecified - the behavior must be deterministic and cannot affect the semantics of other well-defined parts of the program, but the implementation need not guarantee any single behavior. Implementation-specified - like above, but the implementation must specify the exact behavior.
    - to3m 10y ago
      The compiler may also assume undefined behaviour can happen, and do something documented, that programmers would probably expect. Even though the standard imposes no specific requirements, it explicitly calls that out at something you could do: http://port70.net/~nsz/c/c11/n1570.html#3.4.3 http://port70.net/~nsz/c/c11/n1570.html#3.4.3 But for some reason nobody seems to ever think this is an option.
Kenji 10y ago
//int dead = *P; // deleted by the optimizer. If a compiler does that, it is broken. Dereferencing P clearly has side effects (i.e. segfault if P does not point into valid memory). A compiler must prove that its optimisation does not affect the program execution. This is clearly a change that does. It cannot optimize away operations with side effects. And if this is a valid optimisation according to the standard, then the standard is broken. EDIT: If segfaulting is not a part of C, but a part of the hardware architecture, then the compiler shouldn't assume that a dereferenced pointer is not NULL. Either way, the compiler should behave in a way to avoid the least expected outcomes.
- bodyfour 10y ago
  Well, by your standard most compilers used today are "broken". Possibly causing a segfault is not a side effect the compiler is required to respect. If you want to force the compiler to not remove a memory operation in C, you need to define the pointer as "volatile"
- Unklejoe 10y ago
  Does this actually count as a side effect? I didn't think that dereferencing a variable could ever be the sole cause of a side effect. I thought that side effects were only relevant in the context of a store (except for maybe volatile variables in which there are some ordering/barrier constraints applied as well). I realize that in practice, deferencing NULL can definitely cause a crash, but I don't know if it counts as a "side effect" in the typical "C" sense of the phrase. I know that modifying the value of a variable which is accessed by means of a reference passed as an argument could definitely have side effects (since another unrelated function might read that data) and thus a store can’t be completely optimized away (but still can be reordered), but I don’t see why “dead” can’t be optimized away in this case. In this case “dead” is a local variable, thus it can never be accessed by anyone outside of the function. Therefore, if there are no reads of the variable after that single store, I don’t see why the store can’t be completely eliminated. In fact, this is a common issue when dealing with microcontrollers where configuration registers are sometimes written by assigning a value to a dereferenced address constant. That's why they get casted as volatile.
Unklejoe 10y ago
Two things: 1. What's the proper way to do a NULL check? In the first example, they show how a NULL check could be optimized away, but I didn't see where they explained how to do it the right way. I might have just missed it though. 2. It would be nice if compilers offered a special optimization flag that performs most optimizations, but also “fills in the gaps” for non standard behavior by behaving how people expect. I realize that this would essentially be like each compiler implementing its own version of the standard in a way, but the reality is that if 99% of the people are making an assumption about how the compiler is going to do something, maybe that’s how the compiler should do it? Perhaps like a “speed+security” optimization flag. GCC already has some flags to handle certain questionable things such as strict aliasing, etc… Maybe something already exists, IDK. I guess the real solution would be to change the actual standard. EDIT: A comment elsewhere provides a good response to my second point. It was along the lines of "which optimizations are okay then? Most optimizations broke code at some point". I guess my response would be to only disable the ones that are the most common trouble makers. Another factor could be the performance gain vs amount of bugs it causes. I am reconsidering my second point though...
- hardlianotion 10y ago
  To 1. I think if you were to do the null check and then dereference, the problem would go away. Oh - and use the variable holding the dereferenced data.
- lmm 10y ago
  > 1. What's the proper way to do a NULL check? In the first example, they show how a NULL check could be optimized away, but I didn't see where they explained how to do it the right way. I might have just missed it though. You need to not do * p at all if p is NULL (i.e. move the "int dead = * p" after the early return).
- EpicEng 10y ago
  If the pointer is null and you go ahead and dereference it anyway then yes, that's dumb, and the compiler is free to remove the null check.
throwaw190ay 10y ago
Let's tell it like it is, the only reason C was more popular than anything else in the 70/80's is because unlike its competition, implementing a C compiler didn't require to pay a big license fee to a vendor. C is a horrible language and now most developers are stuck with it, because the Linux kernel like most system is built with C. Rust might save us from C ultimately, but that's clearly not for tomorrow.
- zzzcpan 10y ago
  Let's try this again. As a language C is not that horrible and it doesn't have to be as sloppy and as insecure as it is in popular compilers. In fact, I believe 99% of the C code is not performance critical and can benefit from simple runtime checks to ensure memory safety. Not that much needed to "save us from C". But ultimately no one cares, inventing and playing with new languages is way more fun.

129 points by BuuQu9hu 10y ago

Not to mention that arithmetic operations (including division) that overflow signed integers result in undefined behavior.

mnarayan01 10y ago
That's mentioned in Part 1: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-....

new299 10y ago

Nice summary. If stability/security is important in your codebase. It's of course worth avoiding undefined behavior, and compiling with warnings as errors (-Werror in gcc). However it's also really worth running your test suite through Valgrind [1] too sometimes. This instruments your code to check for use for use of initialized variables/other non-deterministic behavior at runtime. I used to run this under continuous integration, and flag builds with issues. [1] http://valgrind.org/ http://valgrind.org/

DSMan195276 10y ago
I agree that all warnings should be generally be turned on and snuffed out (Though there are a few innocuous warnings that I turn off sometimes), however I wouldn't recommend the usage of -Werror to force that unless it's only enabled for dev builds. Warnings are generally impossible to fully predict: different compilers can give different warnings - from warnings enabled by default, warnings changed between versions, and warnings that differ between compilers. And of course, there's no wrong way for the compiler to do it because what to warn about is subjective in the first place. That can become really annoying for an end user looking to just compile and run your software, not debug why it fails to build because their setup outputs a warning somewhere that may not even be an error. And turning off -Werror tends to then require delving into Makefiles (or whatever other build system they chose to use), and at that point most people are probably just not going to bother and call it broken. Again, I'm not saying you shouldn't attempt to snuff out and find every warning that you can, but you shouldn't have your default build rely on compiling with no warnings. There's just too many variables uncounted for to expect your software to compile without warnings in every possible configuration. I also agree 100% with running test suites through valgrind - I do that as well and it's a very good way to guard against memory leaks being introduced (Of course, good structure and design techniques are always the best defense, but there's nothing wrong with a good check that things are doing good).
- new299 10y ago
  Right, I think that's reasonable. Maybe just use it for debug or builds of test suites/CI builds.
- ryandrake 10y ago
  Another reason to avoid -Werror is if you pull in third party code that you share your build options with. Even large stable open source projects regularly spew hundreds of warnings when you aggressively turn them on. I'll generally build my own code with all warnings, but use as close as I can to the package maintainer's build settings for their code. Even then, you can get warnings because the third party developer doesn't use your exact compiler.
lomnakkus 10y ago
AFAICT valgrind is mostly obsolete; use ASAN+UBSAN+... instead.
- pjmlp 10y ago
  When gcc or clang are an option.
- planteen 10y ago
  Is the thread sanitizer caught up to where valgrind (helgrind) was for detecting data races? I know a while back it wasn't but things may have changed.
pjmlp 10y ago
The problem with Valgrind is that not everyone is working on one of these platforms http://valgrind.org/info/platforms.html http://valgrind.org/info/platforms.html
- abecedarius 10y ago
  It's also not enough. A medium-large program of mine that passed Valgrind had been working for years when it started blowing up on newer compiler releases. Maybe the newer static undefined-behavior analyses would have made that less of an awful pain, if they'd been available then.
buserror 10y ago
-Werror used to be the way to go, until compiler writers decided to add warnings for idiotic reasons. Like 'confusing indentation' or 'unused static const variables'. Seriously, these two are completely idiotic; why would the compiler decide that the fact I don't have a blank line 'might' be confusing? on whose criteria? Same with static const variables in C files. Lots of code is often #ifdef in/out, and lots of people would rather have a static const int than a #define!
- mattkrause 10y ago
  The "confusing indentation" warning can be useful. For example, it would have flagged if ((err = SSLHashSHA1.update(&hashCtx, &signedParams)) != 0) goto fail; goto fail; Does any compiler try to indicate the severity of each warning. For example, using the value from an uninitialized variable is labeled as somehow "worse" than code-quality warnings like indentation or bare assignments inside conditionals?

oldgun 10y ago

Really nice summary of undefined behavior. Just realized this is posted by Chris Lattner himself.

mpweiher 10y ago

"You're holding it wrong", compiler-writer's version. IIRC, the Linux kernel has a rule that as a kernel developer, you are not allowed to break userspace, even if you think userspace is wrong. This is an apologia for why compiler writers think they should not have to be held to similar standards. The argument is always something along the lines that UB in the C standard means they get to do whatever they want, including such nonsense as eliminating entire loops because the last access is out of bounds or going down an if-else-branch other than what the if says. That this argumentation is specious in the extreme is shown by the fact that C compilers worked fine (and with less code breakages) before there even was a C standard, so all behavior was "UB". The unstated assumption is that the optimizations enabled by this are absolutely necessary. That overstates the importance of compiler optimizations in general, and certainly the importance of these particular optimizations. (see Proebsting's Law)[2]. There may be code-bases where these extra optimizations are beneficial or even essential, fine, let's add a -Ogoforit or -Oletsgocrazy flag. Rebuttal here: What every compiler writer should know about undefined behavior or "Optimization" based on undefined behavior hurts performance[1] Short summary is that this trend towards exploiting UB breaks a lot of code that has been working for decades, and the fixes required to bring them in-line with the new regime imposed in order to enable these new optimizations makes it slower than the old code without those optimization. Yay. [1] http://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_2015_submission_29.pdf http://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_201... [2] http://proebsting.cs.arizona.edu http://proebsting.cs.arizona.edu 'I may be best known for "Proebsting's Law", which asserts that compiler optimizations have yielded annual performance gains an order of magnitude worse than hardware performance gains. The law probably would have gone unnoticed had it not been for the protests by those receiving funds to do compiler optimization research.'

haberman 10y ago
Others have gone down this path and realized it's not as easy as it sounds: http://blog.regehr.org/archives/1287 http://blog.regehr.org/archives/1287
- mpweiher 10y ago
  Yes, but it depends a lot what you consider "down this path". John's approach seemed to be to define the UB, and to me it looks like he found out why it was left as UB in the spec. Not exploiting the UB for optimizations in ways that break lots of code is actually trivially easy. We have been doing it for 30+ years and we just have to stop adding new optimizations that break, and possibly revert some of the ones that are already in there.

prodigal_erik 10y ago

Are these all undefined rather than merely unspecified or implementation-defined? I'm a little suspicious that they don't explain the difference, but I'm having trouble finding a definitive list of the places where the standard allows nasal demons.

lomnakkus 10y ago
They're undefined. (From a quick skim.) However, an implementation could define various UBs however it wants. The difference between "undefined" and "implement-defined" is really that an implementation doesn't have to anything even remotely sensible for "undefined" behavior, but it has do define some ("sensible") behavior for "implementation-defined" behavior. Usually, "implementation-defined" behavior also tends to remain consistent across versions whereas "undefined" behavior usually has no such constraints. For example, for "undefined" behavior, version 5.1.2.3 of the compiler may differ drastically from 5.1.2.4 in terms of optimizations which rely on UB.
- Sharlin 10y ago
  Basically: Undefined - the compiler may assume this can never happen, and if it does happen, it can "poison" the whole execution including whatever logically happens before the undefined part. Unspecified - the behavior must be deterministic and cannot affect the semantics of other well-defined parts of the program, but the implementation need not guarantee any single behavior. Implementation-specified - like above, but the implementation must specify the exact behavior.
  - to3m 10y ago
    The compiler may also assume undefined behaviour can happen, and do something documented, that programmers would probably expect. Even though the standard imposes no specific requirements, it explicitly calls that out at something you could do: http://port70.net/~nsz/c/c11/n1570.html#3.4.3 http://port70.net/~nsz/c/c11/n1570.html#3.4.3 But for some reason nobody seems to ever think this is an option.

Kenji 10y ago

//int dead = *P; // deleted by the optimizer. If a compiler does that, it is broken. Dereferencing P clearly has side effects (i.e. segfault if P does not point into valid memory). A compiler must prove that its optimisation does not affect the program execution. This is clearly a change that does. It cannot optimize away operations with side effects. And if this is a valid optimisation according to the standard, then the standard is broken. EDIT: If segfaulting is not a part of C, but a part of the hardware architecture, then the compiler shouldn't assume that a dereferenced pointer is not NULL. Either way, the compiler should behave in a way to avoid the least expected outcomes.

bodyfour 10y ago
Well, by your standard most compilers used today are "broken". Possibly causing a segfault is not a side effect the compiler is required to respect. If you want to force the compiler to not remove a memory operation in C, you need to define the pointer as "volatile"
Unklejoe 10y ago
Does this actually count as a side effect? I didn't think that dereferencing a variable could ever be the sole cause of a side effect. I thought that side effects were only relevant in the context of a store (except for maybe volatile variables in which there are some ordering/barrier constraints applied as well). I realize that in practice, deferencing NULL can definitely cause a crash, but I don't know if it counts as a "side effect" in the typical "C" sense of the phrase. I know that modifying the value of a variable which is accessed by means of a reference passed as an argument could definitely have side effects (since another unrelated function might read that data) and thus a store can’t be completely optimized away (but still can be reordered), but I don’t see why “dead” can’t be optimized away in this case. In this case “dead” is a local variable, thus it can never be accessed by anyone outside of the function. Therefore, if there are no reads of the variable after that single store, I don’t see why the store can’t be completely eliminated. In fact, this is a common issue when dealing with microcontrollers where configuration registers are sometimes written by assigning a value to a dereferenced address constant. That's why they get casted as volatile.

Unklejoe 10y ago

Two things: 1. What's the proper way to do a NULL check? In the first example, they show how a NULL check could be optimized away, but I didn't see where they explained how to do it the right way. I might have just missed it though. 2. It would be nice if compilers offered a special optimization flag that performs most optimizations, but also “fills in the gaps” for non standard behavior by behaving how people expect. I realize that this would essentially be like each compiler implementing its own version of the standard in a way, but the reality is that if 99% of the people are making an assumption about how the compiler is going to do something, maybe that’s how the compiler should do it? Perhaps like a “speed+security” optimization flag. GCC already has some flags to handle certain questionable things such as strict aliasing, etc… Maybe something already exists, IDK. I guess the real solution would be to change the actual standard. EDIT: A comment elsewhere provides a good response to my second point. It was along the lines of "which optimizations are okay then? Most optimizations broke code at some point". I guess my response would be to only disable the ones that are the most common trouble makers. Another factor could be the performance gain vs amount of bugs it causes. I am reconsidering my second point though...

hardlianotion 10y ago
To 1. I think if you were to do the null check and then dereference, the problem would go away. Oh - and use the variable holding the dereferenced data.
lmm 10y ago
> 1. What's the proper way to do a NULL check? In the first example, they show how a NULL check could be optimized away, but I didn't see where they explained how to do it the right way. I might have just missed it though. You need to not do * p at all if p is NULL (i.e. move the "int dead = * p" after the early return).
EpicEng 10y ago
If the pointer is null and you go ahead and dereference it anyway then yes, that's dumb, and the compiler is free to remove the null check.

throwaw190ay 10y ago

Let's tell it like it is, the only reason C was more popular than anything else in the 70/80's is because unlike its competition, implementing a C compiler didn't require to pay a big license fee to a vendor. C is a horrible language and now most developers are stuck with it, because the Linux kernel like most system is built with C. Rust might save us from C ultimately, but that's clearly not for tomorrow.

zzzcpan 10y ago
Let's try this again. As a language C is not that horrible and it doesn't have to be as sloppy and as insecure as it is in popular compilers. In fact, I believe 99% of the C code is not performance critical and can benefit from simple runtime checks to ensure memory safety. Not that much needed to "save us from C". But ultimately no one cares, inventing and playing with new languages is way more fun.