What every C programmer should know about Undefined Behavior. Part 3/3
Part 1
Part 2
Part 3
In the first part of the cycle, we looked at unspecified behavior in C and showed some cases that allow us to make C faster than “safe” languages. In Part 2, we looked at some unexpected bugs that could contradict the ideas of many C programmers about the C language. In this part, we look at the problems that the Clang compiler solves in order to achieve high performance and eliminate some surprises.
People often ask why the compiler does not generate warnings when it optimizes based on unspecified behavior, because each such case can be caused by a bug in the user code. The difficulties in this approach are as follows: 1) too many warnings will be generated to be useful - because these optimizations occur all the time, and in the absence of bugs, 2) it is really difficult to generate such warnings only when people want them, 3) several consecutive optimizations unite together. Consider each item in more detail:
Consider an example: although the bugs associated with incorrect type conversion often manifest themselves in TBBA (type based alias analysis), it will not be useful to generate messages like “the optimizer assumes that P and P [i] are not aliases” when optimizing the example "Zero_array" (from part 1 of the cycle).
')
In addition to the problem of “false positives,” there is a logistical problem, which is that the optimizer does not have enough information to generate meaningful warnings.
Firstly, it works on the basis of the abstract code representation (LLVM IR), which is completely different from C, and secondly, the compiler has many layers, and at the point where the optimizer tries to bring reading from P beyond the bounds of the loop, it does not know about the analysis of TBAA. This is a really difficult problem.
It is difficult to generate such warnings only because people want it.
Clang implements various warnings for simple and obvious cases of undefined behavior, such as going beyond the limits of a shift operation of type "x << 421". You may think that this is a simple and obvious thing, but it turns out to be difficult because people do not want to receive warnings about UB in a “dead code”.
The dead code has several forms, it can be, for example, macros that unfold in such a strange way when they are given a constant. There may be a situation when in the switch construction some variants (provably) are not executed, and the user will be dissatisfied if we issue warnings about the code located in these places. In addition, switch statements in C programs are not necessarily well structured.
The solution is that Clang collects warnings about runtime behavior, and then removes those that belong to blocks that will not be executed. The difficulty here is that there are idioms that we don’t expect, and doing such things in the front end means that we don’t catch every case that users want us to catch.
If the frontend is so hard to generate warnings, perhaps we can generate them from the optimizer! The biggest problem in generating useful messages is tracking the data. The compiler optimizer includes dozens of optimization passes, each of which changes the code, making it (we hope) faster. If the inliner decides to inline a function, this can open up new possibilities in order to remove, for example, expressions like "X * 2/2".
Although we are concerned with simple and limited examples to demonstrate such optimizations, most real-world cases occur in code that was formed when macros were deployed, inline functions, and other actions to remove high-level abstractions that the compiler takes. The reality is that people usually do not write stupid things directly. For warnings, this means that in order to refer to user code, you need to exactly reconstruct how the compiler received the intermediate code. We would need the opportunity to say something like this:
warning: after three levels of inline functions (possibly located in different files with Link Time Optimization), deleting common subexpressions, removing them from the loop, and proving that these 13 pointers are not aliases, we found a place where you do something unspecified . This may be because of a bug in your code, or because of a macro, or because of an inline, and the wrong code is actually unavailable, but we cannot prove that it is dead.
Unfortunately, we do not have the infrastructure to track this, and even if it were, the compiler does not have a user interface good enough to tell all this to the programmer.
In general, UB is valuable to the optimizer in that it says: “the operation is incorrect - it can be assumed that it will never happen.” In the case of "* P", this gives the optimizer a reason to believe that P is not invalid NULL. In the case of "* NULL" (for example, after substitution of constants and inline), this allows the optimizer to assume that such code is not reachable. An important assumption is that, since the stop problem cannot be solved, the compiler cannot know that the code is actually dead (as it should be according to the C standard) or is a bug resulting from a (possibly long) series of optimizations. Since there is generally no good way to distinguish between these two things, almost all of these warnings will be a false-positive noise.
Given the sad state of UB, you can ask what Clang and LLVM are doing to remedy the situation. I already mentioned a couple of things: Clang Static Analyzer, Klee and the -fcatch-undefined-behavior flag are useful tools for tracking some classes of such bugs. The problem is that they are not as widely used as the compiler, and all that we can do right in the compiler will be a much greater boon than what is done by individual tools. Remember that the compiler is limited and has no dynamic information, and is also limited by the fact that it can not spend too much time when compiling.
The first step of Clang to improve the code is to include more warnings by default than other compilers. Although some developers are disciplined and compile with "-Wall-Wextra" (for example), many do not know about these flags or do not bother to turn them on. By including more warnings by default, we catch more bugs.
The second step is that Clang generates warnings for many classes of undefined behavior (including zero dereferencing, shifts that are too large, etc.), which allows you to catch common errors in the code. The above are different
The third step is that the LLVM optimizer has much less freedom regarding UB than it could. Although the standard says that any instance of indefinite behavior can have an unlimited effect, it would not be friendly behavior in relation to the developer to benefit from it. Instead, the LLVM optimizer processes them in several different ways (links are given to the rules of LLVM IR, not C, unfortunately):
1. Some cases of indefinite behavior are simply converted to operations that cause an exception. For example, Clang for this C ++ function:
compiles the following X86-64 code:
instead of the code that GCC generates:
The difference is that we decide to spend several cycles on preventing a potentially serious bug from overflowing an integer number, which can lead to buffer overflow and vulnerability (the new operator itself is expensive, so the extra commands are almost imperceptible). GCC developers have been aware of this vulnerability since at least 2005, but have not fixed it at the time of this writing. ( Vulnerability resolved in GCC 4.8.1 and higher. approx. transl. )
Arithmetic operations on undefined values ​​can produce undefined values ​​instead of indefinite behavior. The difference is that an undefined value cannot format your hard drive, or lead to other unwanted effects. A positive effect occurs when an arithmetic expression leads to the same result for any possible variant of an undefined value. For example, the optimizer assumes that the “undef & 1” result has zeros in the high-order bits, leaving only the low-order bit undefined. This means that ((undef & 1) >> 1) will be equal to 0 in the LLVM, and will not be an undefined value.
Arithmetic expressions that dynamically perform unspecified operations (such as overflowing a signed integer) generate a “logical trap” (poison trap) that “poison” any calculations in which it is used, but does not destroy the rest of the program. This means that downstream logical operations from an undefined operation may be affected, but not the rest of the program. This is the reason why the optimizer does not remove the code that performs operations on uninitialized variables. Writing to null and calling the function at the null pointer turns into a call to __builtin_trap () (which, in turn, turns into a call to the “ud2” instruction on x86). This happens all the time in optimized code (as a result of other transformations, such as inline functions and the distribution of constants). and we remove the blocks containing such commands, because they are obviously unreachable.
If (from the point of view of pedantic execution of standards) they are really unattainable, in reality we understand that people sometimes dereference null-pointers, which causes code execution to fall in subsequent functions and makes it very difficult to understand the problem. In terms of speed, the most important aspect here is the compression of the subsequent code. Therefore, clang turns undefined operations into a runtime trap: if one of them is dynamically reached, the program will immediately stop and can be debugged. The disadvantage here is a slight swelling of the code due to these operations and the conditions governing their predicates.
The optimizer makes some efforts to “do it right” in cases where it is obvious what the programmer meant (for example, in the code "* (int *) P", where P indicates float). This helps in many cases, but you really shouldn't rely on it, and there are many examples of which you may think that they are “obvious”, but they are not so after a long series of transformations applied to your code.
Optimizations that do not fall into any of these categories, such as in the examples zero_array and set / call from part 1, are optimized as described, “silently”, without messages to the user. We do this because there is nothing useful that can be reported, and it is very unusual for a (booted) code of a real application, if these optimizations break it.
One of the main areas of improvement that we can do comes at the expense of such “traps”. I think it would be interesting to add (turned off by default) a warning flag that will cause the optimizer to make warnings when it inserts traps. This will give a lot of “noise” for some sources, but it will be useful for others. The first limiting factor here is that the operation of the infrastructure will force the optimizer to issue warnings: they will not have useful locations in the source code if the debugging information is disabled (but this can be fixed).
Another more significant limiting factor is that these warnings will not have any tracking information that would help explain that this operation was the result of deploying the loop three times and inline four levels of function calls. The best we can do is specify a file / row / column, which will be useful in most trivial cases, but will be very confusing in other cases. In any case, the implementation of this is not a priority for us because: a) it is unlikely to give a good experience b) we will not make this feature enabled by default and c) a lot of work will be required to implement it.
The last option you have, if you do not need maximum performance, is to use different compiler flags in order to use C dialect, which eliminates undefined behavior. For example, using the -fwrapv flag eliminates ambiguous behavior resulting from overflow of signed numbers (however, we note that this does not eliminate possible vulnerabilities and security holes related to overflow of signed numbers). The -fno-strict-aliasing flag disables Type Based Alias ​​Analysis, and you can ignore these rules for types. If necessary, we can add a flag to Clang, which by default will reset all local variables, a flag that inserts an “and” operation before each shift with a variable shift value, etc. Unfortunately, there is no way to completely get rid of the indefinite behavior in C, without breaking the ABI and completely killing speed. Another problem is that you will no longer write in C, you will write in a similar, but not compatible with C dialect.
If writing code in the intolerable C dialect is not yours, then the -ftrapv and -fcatch-undefined-behavior flags (along with the other things mentioned earlier) can be a useful weapon in your arsenal for tracking this kind of bugs. Enabling them in the debug build can be a good way to detect bugs early. These flags can also be useful in production if you build a security-critical application. Although there is no guarantee that you will find all the bugs, they find a useful subset of the bugs.
Basically, the real problem is that C is not a safe language and (despite its success and popularity) many people do not understand how the language actually works. Decades of development preceded its standardization in 1989, and C was transformed from a "low-level system programming language, which is a thin layer above the PDP assembler" to a "low-level system programming language, trying to achieve high performance, breaking people's expectations." On the one hand, all C tricks almost always work, and the code as a whole is more productive because of this (and in some cases, much more). On the other hand, the places of cheating tricks are often very surprising people and usually appear at the most inopportune moment.
C is much more than a portable assembler, sometimes it can surprise a lot. I hope that this discussion has clarified some issues regarding indefinite behavior with C, at least from the point of view of the compiler.
Part 2
Part 3
In the first part of the cycle, we looked at unspecified behavior in C and showed some cases that allow us to make C faster than “safe” languages. In Part 2, we looked at some unexpected bugs that could contradict the ideas of many C programmers about the C language. In this part, we look at the problems that the Clang compiler solves in order to achieve high performance and eliminate some surprises.
Why is a warning not issued that optimization is done based on UB?
People often ask why the compiler does not generate warnings when it optimizes based on unspecified behavior, because each such case can be caused by a bug in the user code. The difficulties in this approach are as follows: 1) too many warnings will be generated to be useful - because these optimizations occur all the time, and in the absence of bugs, 2) it is really difficult to generate such warnings only when people want them, 3) several consecutive optimizations unite together. Consider each item in more detail:
It’s very hard to make warnings really helpful.
Consider an example: although the bugs associated with incorrect type conversion often manifest themselves in TBBA (type based alias analysis), it will not be useful to generate messages like “the optimizer assumes that P and P [i] are not aliases” when optimizing the example "Zero_array" (from part 1 of the cycle).
')
float *P; void zero_array() { int i; for (i = 0; i < 10000; ++i) P[i] = 0.0f; } In addition to the problem of “false positives,” there is a logistical problem, which is that the optimizer does not have enough information to generate meaningful warnings.
Firstly, it works on the basis of the abstract code representation (LLVM IR), which is completely different from C, and secondly, the compiler has many layers, and at the point where the optimizer tries to bring reading from P beyond the bounds of the loop, it does not know about the analysis of TBAA. This is a really difficult problem.
It is difficult to generate such warnings only because people want it.
Clang implements various warnings for simple and obvious cases of undefined behavior, such as going beyond the limits of a shift operation of type "x << 421". You may think that this is a simple and obvious thing, but it turns out to be difficult because people do not want to receive warnings about UB in a “dead code”.
The dead code has several forms, it can be, for example, macros that unfold in such a strange way when they are given a constant. There may be a situation when in the switch construction some variants (provably) are not executed, and the user will be dissatisfied if we issue warnings about the code located in these places. In addition, switch statements in C programs are not necessarily well structured.
The solution is that Clang collects warnings about runtime behavior, and then removes those that belong to blocks that will not be executed. The difficulty here is that there are idioms that we don’t expect, and doing such things in the front end means that we don’t catch every case that users want us to catch.
Sequences of optimizations open up opportunities for new optimizations.
If the frontend is so hard to generate warnings, perhaps we can generate them from the optimizer! The biggest problem in generating useful messages is tracking the data. The compiler optimizer includes dozens of optimization passes, each of which changes the code, making it (we hope) faster. If the inliner decides to inline a function, this can open up new possibilities in order to remove, for example, expressions like "X * 2/2".
Although we are concerned with simple and limited examples to demonstrate such optimizations, most real-world cases occur in code that was formed when macros were deployed, inline functions, and other actions to remove high-level abstractions that the compiler takes. The reality is that people usually do not write stupid things directly. For warnings, this means that in order to refer to user code, you need to exactly reconstruct how the compiler received the intermediate code. We would need the opportunity to say something like this:
warning: after three levels of inline functions (possibly located in different files with Link Time Optimization), deleting common subexpressions, removing them from the loop, and proving that these 13 pointers are not aliases, we found a place where you do something unspecified . This may be because of a bug in your code, or because of a macro, or because of an inline, and the wrong code is actually unavailable, but we cannot prove that it is dead.
Unfortunately, we do not have the infrastructure to track this, and even if it were, the compiler does not have a user interface good enough to tell all this to the programmer.
In general, UB is valuable to the optimizer in that it says: “the operation is incorrect - it can be assumed that it will never happen.” In the case of "* P", this gives the optimizer a reason to believe that P is not invalid NULL. In the case of "* NULL" (for example, after substitution of constants and inline), this allows the optimizer to assume that such code is not reachable. An important assumption is that, since the stop problem cannot be solved, the compiler cannot know that the code is actually dead (as it should be according to the C standard) or is a bug resulting from a (possibly long) series of optimizations. Since there is generally no good way to distinguish between these two things, almost all of these warnings will be a false-positive noise.
Clang's approach to UB
Given the sad state of UB, you can ask what Clang and LLVM are doing to remedy the situation. I already mentioned a couple of things: Clang Static Analyzer, Klee and the -fcatch-undefined-behavior flag are useful tools for tracking some classes of such bugs. The problem is that they are not as widely used as the compiler, and all that we can do right in the compiler will be a much greater boon than what is done by individual tools. Remember that the compiler is limited and has no dynamic information, and is also limited by the fact that it can not spend too much time when compiling.
The first step of Clang to improve the code is to include more warnings by default than other compilers. Although some developers are disciplined and compile with "-Wall-Wextra" (for example), many do not know about these flags or do not bother to turn them on. By including more warnings by default, we catch more bugs.
The second step is that Clang generates warnings for many classes of undefined behavior (including zero dereferencing, shifts that are too large, etc.), which allows you to catch common errors in the code. The above are different
The third step is that the LLVM optimizer has much less freedom regarding UB than it could. Although the standard says that any instance of indefinite behavior can have an unlimited effect, it would not be friendly behavior in relation to the developer to benefit from it. Instead, the LLVM optimizer processes them in several different ways (links are given to the rules of LLVM IR, not C, unfortunately):
1. Some cases of indefinite behavior are simply converted to operations that cause an exception. For example, Clang for this C ++ function:
int *foo(long x) { return new int[x]; } compiles the following X86-64 code:
__Z3fool: movl $4, %ecx movq %rdi, %rax mulq %rcx movq $-1, %rdi # Set the size to -1 on overflow cmovnoq %rax, %rdi # Which causes 'new' to throw std::bad_alloc jmp __Znam instead of the code that GCC generates:
__Z3fool: salq $2, %rdi jmp __Znam # Security bug on overflow! The difference is that we decide to spend several cycles on preventing a potentially serious bug from overflowing an integer number, which can lead to buffer overflow and vulnerability (the new operator itself is expensive, so the extra commands are almost imperceptible). GCC developers have been aware of this vulnerability since at least 2005, but have not fixed it at the time of this writing. ( Vulnerability resolved in GCC 4.8.1 and higher. approx. transl. )
Arithmetic operations on undefined values ​​can produce undefined values ​​instead of indefinite behavior. The difference is that an undefined value cannot format your hard drive, or lead to other unwanted effects. A positive effect occurs when an arithmetic expression leads to the same result for any possible variant of an undefined value. For example, the optimizer assumes that the “undef & 1” result has zeros in the high-order bits, leaving only the low-order bit undefined. This means that ((undef & 1) >> 1) will be equal to 0 in the LLVM, and will not be an undefined value.
Arithmetic expressions that dynamically perform unspecified operations (such as overflowing a signed integer) generate a “logical trap” (poison trap) that “poison” any calculations in which it is used, but does not destroy the rest of the program. This means that downstream logical operations from an undefined operation may be affected, but not the rest of the program. This is the reason why the optimizer does not remove the code that performs operations on uninitialized variables. Writing to null and calling the function at the null pointer turns into a call to __builtin_trap () (which, in turn, turns into a call to the “ud2” instruction on x86). This happens all the time in optimized code (as a result of other transformations, such as inline functions and the distribution of constants). and we remove the blocks containing such commands, because they are obviously unreachable.
If (from the point of view of pedantic execution of standards) they are really unattainable, in reality we understand that people sometimes dereference null-pointers, which causes code execution to fall in subsequent functions and makes it very difficult to understand the problem. In terms of speed, the most important aspect here is the compression of the subsequent code. Therefore, clang turns undefined operations into a runtime trap: if one of them is dynamically reached, the program will immediately stop and can be debugged. The disadvantage here is a slight swelling of the code due to these operations and the conditions governing their predicates.
The optimizer makes some efforts to “do it right” in cases where it is obvious what the programmer meant (for example, in the code "* (int *) P", where P indicates float). This helps in many cases, but you really shouldn't rely on it, and there are many examples of which you may think that they are “obvious”, but they are not so after a long series of transformations applied to your code.
Optimizations that do not fall into any of these categories, such as in the examples zero_array and set / call from part 1, are optimized as described, “silently”, without messages to the user. We do this because there is nothing useful that can be reported, and it is very unusual for a (booted) code of a real application, if these optimizations break it.
One of the main areas of improvement that we can do comes at the expense of such “traps”. I think it would be interesting to add (turned off by default) a warning flag that will cause the optimizer to make warnings when it inserts traps. This will give a lot of “noise” for some sources, but it will be useful for others. The first limiting factor here is that the operation of the infrastructure will force the optimizer to issue warnings: they will not have useful locations in the source code if the debugging information is disabled (but this can be fixed).
Another more significant limiting factor is that these warnings will not have any tracking information that would help explain that this operation was the result of deploying the loop three times and inline four levels of function calls. The best we can do is specify a file / row / column, which will be useful in most trivial cases, but will be very confusing in other cases. In any case, the implementation of this is not a priority for us because: a) it is unlikely to give a good experience b) we will not make this feature enabled by default and c) a lot of work will be required to implement it.
Use safe C dialect (and other options)
The last option you have, if you do not need maximum performance, is to use different compiler flags in order to use C dialect, which eliminates undefined behavior. For example, using the -fwrapv flag eliminates ambiguous behavior resulting from overflow of signed numbers (however, we note that this does not eliminate possible vulnerabilities and security holes related to overflow of signed numbers). The -fno-strict-aliasing flag disables Type Based Alias ​​Analysis, and you can ignore these rules for types. If necessary, we can add a flag to Clang, which by default will reset all local variables, a flag that inserts an “and” operation before each shift with a variable shift value, etc. Unfortunately, there is no way to completely get rid of the indefinite behavior in C, without breaking the ABI and completely killing speed. Another problem is that you will no longer write in C, you will write in a similar, but not compatible with C dialect.
If writing code in the intolerable C dialect is not yours, then the -ftrapv and -fcatch-undefined-behavior flags (along with the other things mentioned earlier) can be a useful weapon in your arsenal for tracking this kind of bugs. Enabling them in the debug build can be a good way to detect bugs early. These flags can also be useful in production if you build a security-critical application. Although there is no guarantee that you will find all the bugs, they find a useful subset of the bugs.
Basically, the real problem is that C is not a safe language and (despite its success and popularity) many people do not understand how the language actually works. Decades of development preceded its standardization in 1989, and C was transformed from a "low-level system programming language, which is a thin layer above the PDP assembler" to a "low-level system programming language, trying to achieve high performance, breaking people's expectations." On the one hand, all C tricks almost always work, and the code as a whole is more productive because of this (and in some cases, much more). On the other hand, the places of cheating tricks are often very surprising people and usually appear at the most inopportune moment.
C is much more than a portable assembler, sometimes it can surprise a lot. I hope that this discussion has clarified some issues regarding indefinite behavior with C, at least from the point of view of the compiler.
Source: https://habr.com/ru/post/341154/
All Articles