A note for C programmers

[syzygy]

So how about stopping with the hand waving and simply explain how to break a hash probe where I get an 8 byte signature that does not go with the corresponding 8 bytes of score and stuff. Then we can talk.

No, the burden of proof is on you. You claim that the compiler has no choice but to emit a sane set of instructions that give you the expected result. However, both the C11 and C++11 Standard leave no doubt that reads and writes from different threads to the same variable constitute undefined behavior.

I made no such claim. My claim is that the compiler is required to semantically do EXACTLY what I say.

Show me what in the C99 standard requires the compiler to let two different threads write into the same memory location.

[syzygy]

I don't care what the compiler does, it can't break the lockless hashing code. It is as simple as that. If you want to even try to convince me otherwise, here's the challenge:

You certainly do care what the compiler does.

a hash entry is 16 bytes. I have to write it as 2 8-byte blocks, each of which is certainly guaranteed to be atomic in x86 since that is what is written across the bus in one cycle.

Nope, the compiler is free to implement storing an uint64 as 8x storing a byte. Nothing in the standard stops the compiler from doing just that.

The compiler most likely won't do that, but here you are depending on the compiler and not on the C language.

And if you read what I wrote

Read what you wrote, I quoted it. "I have to write it as 2 8-byte blocks, each of which is certainly guaranteed to be atomic in x86[sic] since that is what is written across the bus in one cycle."

[Rein Halbersma]

I'm neither supporting OR railing against using undefined behavior if one is careful.

There you go again. There is no "if one is careful" provision for UB. All bets are off once you go there. That's the part you have been wrong about for all this time, and too stubborn and proud to admit it.

[syzygy]

Code: Select all

#include <stdio.h> 

int main&#40;) 
&#123; 
  int i, k = 0; 

  for &#40;i = 1; i > 0; i += i&#41; 
    k++; 
  printf&#40;"k = %d\n", k&#41;; 
  return 0; 
&#125;

Running gcc -O0 will produce 31 on architectures where an int is 32-bits. However, with gcc -O2 and higher, the compiler will recognize that "i += i" yields signed overflow UB. It will then eliminate the entire expression, and further optimize this code to an infinite loop. Such a scenario is also possible to happen with your XOR trick on multicore machines. Compiler routinely optimize away UB code instructions. You need extra compiler instructions or code modifcations to get the compiler to do what you intended.

Don't know what planet you compile on. Here's that run on my macbook:

scrappy% cc -O -o tst tst.c
.scrappy% ./tst
k = 31
scrappy% cc -O2 -o tst tst.c
scrappy% ./tst
k = 31
scrappy% cc -O3 -o tst tst.c
scrappy% ./tst
k = 31

gcc version 4.7.3 (MacPorts gcc47 4.7.3_3)

Online example using gcc -O3 (gcc 4.6.4 on Linux)

Funny, it even optimises away the loop variable.

Note that C11 now allows the compiler to eliminate the infinite loop, reducing the program to nothing:

An iteration statement whose controlling expression is not a constant expression, that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a for statement) its expression-3, may be assumed by the implementation to terminate.

(Of course a C99-compliant compiler may also do this once it has detected that the original program is guaranteed to exhibit undefined behavior.)

[bob]

I'm neither supporting OR railing against using undefined behavior if one is careful.

There you go again. There is no "if one is careful" provision for UB. All bets are off once you go there. That's the part you have been wrong about for all this time, and too stubborn and proud to admit it.

Stick to repeating that over and over. Perhaps one day you can make it true. Meanwhile, integer overflow CAN be used. Race conditions CAN be dealt with. Some strcpy() overlap can be handled. etc...

I'm not "too proud" to admit it. I am simply "too knowledgeable" because I have dealt with it in the past. You can give up, or you can try to work around. I tend to not give up except as a last resort...

[bob]

Code: Select all

#include <stdio.h> 

int main&#40;) 
&#123; 
  int i, k = 0; 

  for &#40;i = 1; i > 0; i += i&#41; 
    k++; 
  printf&#40;"k = %d\n", k&#41;; 
  return 0; 
&#125;

Running gcc -O0 will produce 31 on architectures where an int is 32-bits. However, with gcc -O2 and higher, the compiler will recognize that "i += i" yields signed overflow UB. It will then eliminate the entire expression, and further optimize this code to an infinite loop. Such a scenario is also possible to happen with your XOR trick on multicore machines. Compiler routinely optimize away UB code instructions. You need extra compiler instructions or code modifcations to get the compiler to do what you intended.

Don't know what planet you compile on. Here's that run on my macbook:

scrappy% cc -O -o tst tst.c
.scrappy% ./tst
k = 31
scrappy% cc -O2 -o tst tst.c
scrappy% ./tst
k = 31
scrappy% cc -O3 -o tst tst.c
scrappy% ./tst
k = 31

gcc version 4.7.3 (MacPorts gcc47 4.7.3_3)

Online example using gcc -O3 (gcc 4.6.4 on Linux)

So? 4.7.3 newer than 4.6.4... perhaps they realized such an optimization is a mistake.

[bob]

So how about stopping with the hand waving and simply explain how to break a hash probe where I get an 8 byte signature that does not go with the corresponding 8 bytes of score and stuff. Then we can talk.

No, the burden of proof is on you. You claim that the compiler has no choice but to emit a sane set of instructions that give you the expected result. However, both the C11 and C++11 Standard leave no doubt that reads and writes from different threads to the same variable constitute undefined behavior.

I made no such claim. My claim is that the compiler is required to semantically do EXACTLY what I say.

Show me what in the C99 standard requires the compiler to let two different threads write into the same memory location.

Show me explicitly where it does not. Show me specifically how it can even determine that that will happen in a place where it can then wreck the code. You can't. Which makes this race discussion completely ridiculous, in the extreme. If the compiler breaks my code, it will break ALL stores to memory, because it can't tell which will result in a race and which will not. If you believe the compiler can produce code which does NOT do exactly what I say, when the code does not violate any practical standard, then that compiler is broken.

Why are we discussing such nonsense???

[wgarvin]

Okay, we get that you're still annoyed about it, although I'm surprised that two weeks have passed and you still haven't admitted yet that you're completely wrong!

You're probably the only person who is surprised.

WHAT am I "wrong" about?

Certainly not my original point, namely that Apple broke something that did not need to be broken. That Apple, in doing so, caused a lot of debugging effort on my part, and on the part of many others, unnecessarily.

I'm neither supporting OR railing against using undefined behavior if one is careful. I do believe the compiler should "do the best thing" as opposed to "let's be anal and break the code..."

I think you are wrong to the extent that you are trying to assign blame to Apple (or the glibc maintainers, or whoever). There was an explicit contract about how strcpy would behave; you and the authors of all those other broken programs that other people are whining about, were 100% in the wrong by using strcpy in an illegal manner. The behavior of strcpy when used that way has been undefined for 25 years, and there is no possible justification--none--for using it in that undefined fashion anyway.

Is it annoying to have programs broken by a change by somebody else? Sure.

Was it a dick move for them to start enforcing the requirement by adding this explicit check and abort? Perhaps. I'm actually quite sympathetic to that argument, but neither you nor I knows exactly what their motivation was and it doesn't matter, their freedom to do that was explicitly reserved by the standard 25 years ago.

So we need to apportion blame for the broken programs. You seem to think some, most, or perhaps even all of the blame belongs to glibc/Apple. If so, you are completely wrong. 100% of the blame here belongs to the programmers who didn't write code that followed the standard. In each case, that incorrect code was always a time-bomb waiting to blow up their programs. In your case you got away with it for at least 25 years, which perhaps was extremely lucky. But finally your luck ran out.

So to be clear, I think you are wrong in that you think your experience this week was somebody else's fault when an impartial review of the facts makes clear that it was 100% your fault. Only one party here was violating their obligations under the language contract. Glibc was 100% entitled to do what they did (although they will still take some flak for it because of the "dick move" angle).

When a program invokes undefined behavior according to the spec, there is no other possible outcome. The implementation can do anything it wants, no matter how ludicrous or unintuitive. The implementor might change their mind from one week to the next, and whatever happens is still 100% the programmer's fault.

As programmers we might find this to be more than a little unfair, but its the way the language works. Undefined behavior exists to preserve optimization freedoms for implementors and/or to simplify some parts of their task, and the programmers just have to avoid it as best they can. As long as we avoid invoking undefined behavior, we get to rely on the program semantics promised by the standard. But if we accidentally invoke undefined behavior then the nasal demons can and sometimes do result.

[bob]

I don't care what the compiler does, it can't break the lockless hashing code. It is as simple as that. If you want to even try to convince me otherwise, here's the challenge:

You certainly do care what the compiler does.

a hash entry is 16 bytes. I have to write it as 2 8-byte blocks, each of which is certainly guaranteed to be atomic in x86 since that is what is written across the bus in one cycle.

Nope, the compiler is free to implement storing an uint64 as 8x storing a byte. Nothing in the standard stops the compiler from doing just that.

The compiler most likely won't do that, but here you are depending on the compiler and not on the C language.

And if you read what I wrote

Read what you wrote, I quoted it. "I have to write it as 2 8-byte blocks, each of which is certainly guaranteed to be atomic in x86[sic] since that is what is written across the bus in one cycle."

How about the REST of that sentence you quoted:

And if you read what I wrote, that won't bother my code one scintilla. Nor if the compiler decides to store bit by bit somehow. Still works perfectly.

Do you see the end of that statement? NO requirement that it write 'em atomically, that is simply the way X86 accesses memory. But if memory becomes a bit-by-bit read/write, it won't change a thing... So let the compiler write that 128 bit entity bit by bit, byte by byte, word by word, sword by sword, in left-to-right order, in right-to-left order, in random order, in shuffled order. None of it matters. So long as it writes the 128 bits to the correct address, this works.

Simple enough NOW?

[bob]

The standard defines "unspecified behavior", not "unspecified". Similarly with "undefined behavior". You may not like these names, but they are used every day by a lot of people.

"Undefined behavior" means it works when you first run it, it passes all your tests and it explodes in your face when you show it to your boss or your most important customer.

Although you are generally right that people shouldn't go around breaking code that has worked forever, I recommend you just fix the code and move on.

Undefined behavior does NOT mean it will explode. Not one single instance of strcpy() will break on the example I gave where you do strcpy(st, st+n). Integer overflow does NOT make checksum break.

It means it MAY explode. The standard allows it. Compiler writers are making more and more use of this freedom. It makes programs faster.

Code: Select all

#include <stdio.h>

int main&#40;)
&#123;
  int i, k = 0;

  for &#40;i = 1; i > 0; i += i&#41;
    k++;
  printf&#40;"k = %d\n", k&#41;;
  return 0;
&#125;

What do you expect as output?

back to my point. Apple MADE it explode. If the source and destination overlap, the program crashes, period.

As far as the above, it would depend on word size. On my mac, where int defaults to 32 bits, I'd expect 31. On a Cray, I would expect 63. On an old 8086, I would expect 7.

Wrong. Compiled with gcc, you get no output at all. The program hangs in an infinite loop.

With gcc 4.7.3 I get perfectly normal output, for O, O1, O2 and O3. No difference whatsoever. Works on gcc 4.5.1 on an older linux box at the office. In fact, NO version of gcc I have anywhere on any box, going back to gcc 3.6.4-8 on an old cluster all work perfectly. So you found one broken compiler. Good. The original macbook clang I had was ALSO broken, and not due to undefined behavior.

If the compiler can't deal with the overflow/underflow, it is broken.

If a compiler complies with the standard, then by definition it is not broken.

Until they take the "undefined behavior" way too far. When it notices I use threads, can it then optimize away EVERY shared memory write that might possibly result in a race? If it did, NOTHING would work. "Complying" with a standard that doesn't specifically address multiple issues is not exactly a glowing endorsement. I simply do not, and never will agree with the retarded concept that says "you can do anything if there is any possibility of undefined behavior." Fortunately, many of us would not write such a compiler, we would attempt to "do the right thing". And let programs work if they can cope with the result. As opposed to intentionally and maliciously breaking code "just because."