Detectors for memory-related undefined behaviors in C/C++, while being imperfect, are at least something that smart people have spent a lot of time thinking about. Integer-related undefined behaviors have received much less attention, but then again they are a lot simpler than memory unsafety.
Today’s question is: What other checkers should we create? Here are a few. I’m not sure that any of these are really pressing problems in practice, but I think it would be far from useless to test important C/C++ codes under these tools. I’d be happy to hear suggestions for other tools that might be useful.
This discussion of undefined behavior checkers for Clang is useful.
Unspecified order of evaluation of arguments to a function
When you write something like f(g(),h()), the arguments can be evaluated in any order. This matters when the arguments perform I/O or when they modify overlapping state.
Writing a rigorous tool for dynamically finding programs whose behavior is sensitive to argument evaluation order would be difficult and its performance would likely be bad. In contrast, it would be simple to hack a compiler to randomize (either at compile time or at run time) the order in which arguments are evaluated, at which point we would simply look for test cases to fail when the option to do this is turned on.
In a sensible world, left-to-right evaluation would be specified by the standards. Failing that, individual compilers should specify this. Sometimes people say that the unspecified order of evaluation permits the generation of more efficient code but it is very hard to believe that this effect is ever usefully exploited. A recent version of gcc that I checked consistently evaluates arguments right-to-left; a recent Clang consistently evaluates them left-to-right. Older versions of gcc would switch orders depending on optimization option.
Unsequenced modifications to lvalues
Modifying an object multiple times within a C/C++ expression, or accessing an lvalue “other than to determine the new value” is undefined. Here’s a program with unsequenced modifications to x:
#include <stdio.h>
#include <limits.h>
int main (void)
{
unsigned x;
unsigned *p = &x;
x = 0;
printf ("%u\n", x++ + --x);
return 0;
}
And the result:
$ gcc -w side_effect.c ; ./a.out 4294967295 $ gcc -w -O side_effect.c ; ./a.out 4294967294 $ clang -w side_effect.c ; ./a.out 0
For some examples (such as this program) GCC and Clang provide good warnings, but minor modifications such as accessing a variable through a pointer will suppress the warnings without making the underlying problem go away.
I think a dynamic checker for this kind of undefined behavior could be pretty efficient because the total number of objects touched while evaluating an expression is usually pretty small.
Strict aliasing violations
The strict aliasing rules in C/C++ require basically that if you cast a pointer into any kind of pointer besides char *, you don’t dereference the new pointer. Unfortunately I’m not sure how to check for violations short of a full type safety implementation, which is no fun for anyone.
Compiler warnings for strict aliasing violations exist, but seem to be unpredictable. For example, neither GCC nor Clang warns about either c1() or check() in this post. These are both extremely simple and obvious violations of strict aliasing. So it’s hard to see how these compilers could be providing robust warnings about more difficult examples found in real code.
9 responses to “What Other Dynamic Checkers for C/C++ are Needed?”
Perhaps slides #28-33 from the following can be an inspiration: http://www.slideshare.net/Coverity/the-psychology-of-c-analysis-24025354
Are we still missing anything? Critical sections in particular and multithreading (race conditions, etc) in general could be nice, I suppose?
Again from slide #33, checkers for non-resource leaks could be interesting, too.
Or perhaps “just” (I know… ;]) deprecate “new” (and the consequent need for “delete”) outside of constructors (and destructors, respectively) to leave an escape valve for implementing RAII, and require make_unique (and make_shared, as a last resort) anywhere else? 😀
*non-memory resource leaks
Matt, nice slide deck, I bet that was an entertaining talk.
I meant to talk about races a bit! It’s another one like memory safety where people have thought a lot about checkers but still the situation isn’t exactly solved.
Non-memory resource leaks would be great, I agree.
That (leaks and races, I mean) reminds me, what do you think of the following:
http://smallcultfollowing.com/babysteps/blog/2013/06/11/on-the-connection-between-memory-management-and-data-race-freedom/
?
Matt that is a pretty interesting post. I certainly hope to try out Rust sometime. I love the kinds of ideas that are going into it.
I agree that there’s a solid connection between memory management and concurrency correctness. It’s all about knowing who owns what, I think. If you get a chance, give this a read:
http://www0.cs.ucl.ac.uk/staff/p.ohearn/papers/concurrency.pdf
It’s been a few years since I read it but I remember finding it to be a great source of thoughts along these lines.
The basic idea is that separation logic was proposed some time ago as a method for helping people reason about the effects of pieces of sequential code that do not share memory. This seems easy to do but it can be annoying and unweildy to show that they don’t in fact stomp on each other. Then concurrent separation logic is based on the idea that if two pieces of code touch disjoint memory, you can reason about their concurrency correctness as well. There’s a lot of stuff written on these topics that I don’t want to try to read (and I’m guessing that you don’t either) but this particular paper is quite accessible.
Maybe something on iterator invalidation for the C++ STL? I know there are some debug versions of these libraries that detect iterator invalidation, but I suspect it could be made faster or more thorough.
Re gcc’s order of evaluation, I think it’s architecture-dependent, with SPARC evaluating left-to-right and x86 evaluating right-to-left. I definitely remember being asked to track down a bug on a toy joke program where it worked on the x86 machines and not the sparc machines, but I don’t remember if we were using gcc on both machines.
I like how newer languages tighten up evaluation order a lot better compared to C (both the left-to-right and the x = x++ problem). I suspect C left it originally unspecified in part because not all ABIs agree on the order to push things on the call stack. Outside of function calls, most reordering of expressions is legal due to unobservability or other undefined behaviors (e.g., order of accessing money); finding optimal order of function calls is probably near-impossible in optimizers anyways, so I don’t think the evaluation order unspecified nature can actually help performance in the first place.
Strict aliasing, as I’ve mentioned before, I think should just be abolished. Building a checker for violations on vtable’d types is as simple as “implement RTTI”; building it on POD types… is very hard. Since compilers refuse to warn on strict-aliasing problems even in cases where it’s obviously not going to work (uint32_t u = 0; float f = *(float*)&u;), let alone the cases where you might be violating unexpectedly. I wonder if anyone has done a case study in the benefits of strict aliasing in terms of performance on large, non-trivial codebases in a whole-program analysis as compared to a Steensgard or an Andersen’s style analysis. Also interesting would be to know how many projects explicitly turn off strict aliasing.
Interesting to note that all of these happened to be behaviors that I think oughtn’t be undefined.
John, I’ll take a look, thanks!