Hacker News Reader

Comment by ohazi | Hacker News Reader

This is a little misleading.

Yes, when you see something like this, changing the optimization level may indeed influence whether or not the bug is visible, and is a useful tool for figuring out what went wrong. But these days it's pretty rare that the optimizer is at fault. Usually what you'll find is that the optimizer is indeed making a valid optimization, but your code is relying on unspecified C or C++ behavior that just happens to work when you're at -O0.

Your code is still the thing that's technically incorrect.

View on HN

Ordering is basically an unspecified behavior in C. An optimizers best friend is the ability to reorder, perform CSE, etc.

C and C++ are specified as the behavior of a straight-line sequence of code run in isolation. Basically, any concurrent C/C++ program treads into the unspecified behavior area. Thusly it's not the optimizers fault, but C/C++ certainly aren't helping out at all.

Even the mechanisms that are common place to make a concurrent C/C++ program run correctly basically wade into unspecified behavior, for instance using asm("lock esp"), asm("mfence"), etc.

TL;DR: concurrency is unspecified in C.

> TL;DR: concurrency is unspecified in C.

One of the many reasons I'm eagerly the 1.0 release of Rust.

I think you accidentally a word.

Just a Heisenbug, he was using a browser written in C or C++.

Looks like we've found a compiler bug. Who has Stallman's email?

sigh Yeah, my edit window expired. Very eagerly awaiting. :-P

>TL;DR: concurrency is unspecified in C.

Does the same argument apply to binary code ran on a preemptive operating systems? The actual execution order of your code is still unspecified, as the OS an interrupt it whenever it wants.

Mostly. The OS and hardware will make certain guarantees about ordering and concurrency, and if you want more you need to specifically ask them for more. C makes almost no guarantees, but the basic concept is the same. Use the provided extensions to get safe order and concurrency.

C11/C++11 define a memory model and provide assorted primitives.

Indeed. It should be:

>TL;DR: concurrency is unspecified in _C99_.

Since it is specified in C11's memory model.

This is absolutely correct, and the article worries me for that reason. C programmers shouldn't learn "Heisenbug == compiler error" -- that's rarely the case. Compilers aren't generally formally verified, but they're also very heavily tested, and it will rarely happen that you expose a compiler bug. It's far more likely you're relying on UB in some way.

The author states that this has only happened 3-4 times in 30 years. I don't see anything that would make a reasonable programmer suspect that this is always the case or even usually the case.

Indeed, if you re-interpret the article's usage of the phrase "optimizer bug", then the advice becomes useful: if changing the optimization level fixes your broken code, you have an undefined-behavior bug.

Either that, or a race condition.

I'm not sure that's necessarily the case. See my comment above about sequential consistency.

Aren't those undefined behavior bugs?

Imagine two threads that safely lock a resource, increment it, copy the value, and then unlock it. This is entirely defined, but also a race condition.

Race conditions are a lot like unsanitized input. They don't cause problems by themselves, but if you make incorrect assumptions it's easy to write incorrect code.

It's data races specifically that are undefined behaviour.

Technically yes, but the C++ spec gives the optimizer a lot of leeway, in ways that aren't necessarily safe.

Few programmers have a deep enough understanding of the C++ spec to realize things like how the optimizer is free to ignore NULL checks after a memory location has been accessed. They just see a `pointer == NULL` passing, then code failing on a null pointer.

And the problem is that they shouldn't need that level of understanding to write C++. The optimizer should be doing things like warning about unnecessary null checks that could degrade performance, it would notify the developer that there's a problem.

But that would cause issues for people working with large amounts of legacy code, so it's not done.

"Ignoring NULL checks after a memory location has been accessed" -- what do you mean by that?

Standard example:

    void f(struct some_struct* p) {
        int x = p->some_field;
        
        /* ... */
        
        if (p != NULL) {
            /* this block might be executed even if p = NULL */
        }
    }

Because reading `p->some_field` is already undefined behavior unless `p != NULL`, the compiler is free to assume that `p != NULL` is always true, and might avoid the check.

If the memory access doesn't crash the program for whatever reason (maybe it got reordered somewhere else or eliminated as dead code or whatever, I dunno), then if you call that function with a NULL pointer, you fall into undefined behavior that might manifest as that check that you put right there being skipped.

That would've already crashed at the p->some_field if p == NULL.

> the compiler is free to assume that `p != NULL` is always true

Only until the first point in the "..." part where it cannot prove that p has not been modified.

If x is unused, the compiler is allowed to remove the assignment. If it does that optimization after it removes the "redundant" null pointer test, the optimizer has legally altered your program to remove the null pointer check you thought you had.

http://blog.llvm.org/2011/05/what-every-c-programmer-should-...

Please read that article, and the rest in the series. Undefined behavior is far more pervasive than you think.

> If x is unused, the compiler is allowed to remove the assignment

This and the Apple SSL bug makes me think that optimising compilers should be far more explicit (i.e. emitting messages or even warnings) about what they're doing than they are now, because it seems far too much about the optimisation process is being hidden and not transparent enough. Not only unreachable code, messages like "result of computation x is never used", "if-condition assumed to be {false, true}", "while-loop condition always false - body removed", etc. would be extremely useful for detecting and fixing these problems.

GCC can produce all of those warnings.

Why would you expect the NULL pointer check to do anything? The function, as given, is meaningless if `p` is NULL. The problem isn't that compilers are too aggressive in their optimization -- the problem is that people who are learning C don't usually learn what it means for the behavior of a program to be undefined.

> That would've already crashed at the p->some_field if p == NULL.

1. Typically yes, and that is exactly why the compiler can remove the check after it, it's already undefined behavior so it can assume the optimistic case (and remove the check).

2. But it is not always true that it would crash. p->some_field might happen to be in a valid memory location to be accessed. This doesn't happen normally because low memory addresses (0-1024, say) tend to not be accessible by userspace programs. But I am not aware of a spec ensuring that. An OS could in theory let your program map memory at address 4, in which case p->some_field would succeed if p is NULL and the offset if 4.

There have been Linux kernel security bugs where a NULL dereference might not result in a crash, because a malicious user-space program had mapped some accessible memory at address zero. The kernel then went on to skip the optimized-out null check, use vtable pointers in this null page and eventually execute arbitrary code in ring 0.

See a certain Linux kernel exploit: http://lwn.net/Articles/342330/

> If the memory access doesn't crash the program for whatever reason (maybe it got reordered somewhere else or eliminated as dead code or whatever, I dunno), then if you call that function with a NULL pointer, you fall into undefined behavior that might manifest as that check that you put right there being skipped.

No; if `p` is NULL, this function has undefined behavior. Full-stop. It is a 100% meaningless function as soon as `p` is NULL, because the "NULL check" happens after the pointer is dereferenced.

So the issue isn't that the compiler can make incorrect optimizations -- the compiler makes optimizations that are entirely correct, assuming that the code that you wrote isn't meaningless.

The code isn't meaningless, it just exhibits undefined behaviour. This doesn't make the program wrong, it just means the standard has nothing to say about what precisely might happen. If the compiler chooses to infer the presence of an equivalent to VC++'s __assume (http://msdn.microsoft.com/en-us/library/1b3fsfxw%28v=vs.90%2...) from the presence of undefined behaviour, it's within its rights to do so, but this particular approach is by no means mandatory.

In fact, most of the compilers I've used actually don't do this, and are (in my view) all the better for it.

See also this rant on gcc's strict aliasing, borne of the same philosophy: http://robertoconcerto.blogspot.co.uk/2010/10/strict-aliasin...

> The code isn't meaningless, it just exhibits undefined behaviour.

That's what undefined behavior means. Semantically speaking, the C language assigns no meaning to that function if the input pointer is NULL, and is therefore "wrong" by any reasonable definition of the word if it is NULL -- so the compiler is free to make an array of optimizations based on the fact that the input pointer is not NULL.

I think that interpretation is too strict. The standard is fairly clear on what the result of undefined behaviour might be, defining it as:

``behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements.

``NOTE Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).'' (italics mine)

This sounds like a long way from "meaningless" in my book. To my reading, the purpose of undefined behaviour appears to be to avoid unduly constraining implementations by not mandating behaviour that could be inefficient, costly or impossible to provide.

You (or anybody else!) may disagree on how far this inch given could or should be taken. But I think the fact the standard explicitly suggests that undefined behaviour could do something reasonable is evidence that programs producing undefined behaviour do not necessarily have to be considered meaningless.

(As a concrete example I have worked on one system where NULL was a pointer to address 0, and where address 0 was readable. Not only that, but in fact address 0 actually contained useful information, and some system macros used it. It was some kind of process information block and so there was a whole family of macros that looked like "#define getpid() (((uint32_t * )0)[0])", "#define getppid() (((uint32_t * )0)[1])", that sort of thing. I'd say this is rather odd, but the standard would appear to allow it. (However, perhaps needless to say, gcc was not the system compiler.))

(See also, the approved manner for using objc_msgSend, since time immemorial.)

On the contrary. The standard is perfectly clear that anything can happen when you write code that employs UB.

> behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements.

NO REQUIREMENTS -- so, semantically, programs that employ undefined behavior are completely meaningless.

With regard to the second quotation, the part you italicized is nice, but the part you didn't is just as important:

> Possible undefined behavior ranges from ignoring the situation completely with unpredictable results

The entire quotation basically says "when you write code with undefined behavior, anything can happen; the results can be unpredictable, or they can appear to be sensible. An error could also be triggered." But that's the point: no behavior is specified. There's no restriction to what might happen.

Take the function above that has a NULL dereference when the input pointer is NULL. That function could be compiled in such a way that it writes an ASCII penguin to stdout if the input pointer is NULL; it's totally within its rights to do that. Your mental model of how C programs work is entirely inaccurate if you expect undefined behavior in C to do something that you deem sensible.

With your summing up of the quotation, I think you're again being too strict. If the standard doesn't define undefined behaviour, which it doesn't - well, what then? You claim this renders any program that invokes undefined behaviour meaningless; I claim (as I think the standard wording implies) that this simply means the standard doesn't define the results, which then necessarily depend on the implementation in question.

(It may be OK for anything to then happen, but as a simple question of quality - and common decency ;) - an implementation should strive to ensure that the result is not terribly surprising to anybody familiar with the system in question. And I'm not really sure that what gcc does in the face of undefined behaviour, conformant though it may be, passes that test.)

In C99 there are three levels of not fully specified behaviour:

1. Undefined: anything is permitted, the standard imposes no requirement whatsoever. A typical example is what happens when a null pointer is dereferenced.

2. Unspecified: anything from a constrained set is permitted. Examples include the order of evaluation of function arguments (all must be evaluated once though any order is allowed).

3. Implementation-defined: the implementation is free to choose the behaviour (possibly from a given set), but must document its choice. An example is the representation of signed integers.

Isn't it often the case that the optimizations throw out sequential consistency guarantees?

That would introduce non-determinism in concurrent executions that might have nothing to do with the semantics of the program.

For example, I'm under the impression that the most recent C++ standard basically says "if you have no data races then all will be well" even though they may be benign data races like dual assignments of the same value.

C doesn't have any sequential consistency. Even without any compiler optimizations, the hardware will reorder things across cores. Subtly on x86, massively on Alpha. You can't use multiprocessing without some kind of external guarantees.

In the embedded industry, the most common reason for things working when disabling optimizations is violating the ANSI aliasing rules. Embedded programmers type-pun all the time and don't realize it's undefined behavior in C. Most compilers have an option to disable the ANSI aliasing rules, but it really hurts optimization opportunities.

I saw a large codebase completely break when turning on intermodule inlining. The cause: more opportunities for the compiler to find pointers that aren't allowed to alias.

Yes, and most often it's clearly warned about, up to the point where lines are completely burried in type-casts, just to shut up the (well meaning) compiler. Because, you know, we thrive for 0-warning compilations!

In this case it might be useful if compilers (or a test compiling tool) had a "go crazy for undefined behaviour option". This might be difficult to implement but could do things like randomise sort order where it's undefined. Similar to how fuzz testing an application's input, this would fuzz test the compilation phase.

Reply on news.ycombinator.com