Terrible misuse of indexing (C anecdote)

[eekee]

A thread reminded me of a time when a very smart guy I know did something similar but, unlike the OP of that thread, angrily blamed gcc. It's funny for gcc's bizzarrely complex response to undefined behaviour as much as a smart guy's strange slip. Here's what he tried to do:

Code: Select all

	int a[16], b[16];
	...
	a[22] = 5;
	...
	x = b[6];

He disassembled the compiled code, and found gcc moved array b to a whole other place while the write took place, then moved it back. What... why... I have no words! Why would gcc do this? It's only detectable when the index is a literal constant, (am I right?) in which case it could be discovered by reading the code, couldn't it? It might be hard to find in a very large codebase, but simply changing the bug to a new form is hardly going to help!

Then there's the guy using this to hate on gcc. He likes simple things on principle but, had he been using a simple compiler on simple hardware without a MMU, he might have run into worse trouble. The arrays might have been separated, with MMIO in between. I guess he must have just had a brain fart or gone a little crazy for a moment. Most programmers seem to go a little crazy over tidyness, (including myself,) and the above initializers do look tidier than this:

Code: Select all

	int a[32];
	int *b = a+16;

(I'm actually trying to train myself to restrain my desire for tidiness and elegance because it causes problems, including demands for complexity, but I haven't made much progress. Part of the reason I decided to work in Forth was to help me get over it.)

[nullplan]

Yeah, this is just using C as a high-level assembler. It is sad that otherwise intelligent people can't seem to wrap their heads around the fact that if C is any kind of assembler, then for an abstract machine that doesn't exist. A machine where undefined behavior lurks behind every corner and pointers are an abstract thing, not just the number of a memory cell. The only pointers you can definitely form are into arrays, and one element behind an array. So technically even casting addresses (numbers) into pointers is UB.

The kind of UB I'm currently having a hard time with at work is data races. It's only been declared UB since C11, but before then there was no idea C had of multi-threading. If I understood it right, a data race occurs if two or more threads access the same memory location at the same time, and at least once for writing. Unless all accesses are atomic. So something as simple as one thread waiting on a variable set by another thread is a data race unless the accesses are made atomic.

On that note, I have noticed that a sleep function can work wonders unless compiler magic is acting up. Take this busy-wait loop:

Code: Select all

while (!(globvar->flags & FLAG_DONE)) ;

Here, globvar is a global variable (file scope, I don't recall the linkage). A microblaze compiler I had pulled the test out of the loop and would go into an infinite loop if the test failed. An ARM compiler I had merely pulled the memory access out of the loop. Still, if the flag was not set by that time, it caused an infinite loop, since the variable was never reloaded. However, when replaced with the following code, the weirdness disappeared:

Code: Select all

while (!(globvar->flags & FLAG_DONE)) usleep(10000);

What's the difference? Yes, usleep() has no influence on the global variable, but gcc didn't know that. It only saw an external function call. External functions can change file scope variables with external linkage. In fact, even with static linkage, the external function might call any of the non-static functions in the current translation unit. Or any of the static functions whose addresses were taken. Point is, due to this function call, the compiler could no longer be certain that the flags would not change during the loop and the synchronization came back to life. Saved me from having to declare that whole structure as volatile.

[Solar]

Code: Select all

while (!(globvar->flags & FLAG_DONE)) ;

[...] A microblaze compiler I had pulled the test out of the loop and would go into an infinite loop if the test failed. An ARM compiler I had merely pulled the memory access out of the loop. Still, if the flag was not set by that time, it caused an infinite loop, since the variable was never reloaded.

Which is perfectly legit for non-volatile values.

[nullplan]

Which is perfectly legit for non-volatile values.

I know. But I found it interesting that adding an external function call -- any external function call -- to the loop body makes that not true anymore. Even if any programmer knows the function doesn't change the value tested, because the compiler doesn't know -- it can't know.

[Solar]

It being a busy loop completely aside, I intensely dislike relying on side effects like that. (And, by extension, showcasing them.)

Imagine, for example, someone rearranges the source and makes that global internal linkage...

[eekee]

Edit: I should have stopped typing when I started laughing too much, or when I got angry even though I made it into comedy rage. I wasted time here (mine and Solar's, evidently,) going with my feelings instead of taking a break so I could focus better later.

Yeah, this is just using C as a high-level assembler. It is sad that otherwise intelligent people can't seem to wrap their heads around the fact that if C is any kind of assembler, then for an abstract machine that doesn't exist. A machine where undefined behavior lurks behind every corner and pointers are an abstract thing, not just the number of a memory cell. The only pointers you can definitely form are into arrays, and one element behind an array. So technically even casting addresses (numbers) into pointers is UB.

Uh... It took me a while to understand more than a third of this paragraph. To cover the bit I understood first: pointers were just the number of a memory cell when many C programmers learned the language. In this century, (I guess,) programmers started to be taught not think of them that way. I guess it's become more of a hard fact now.

The rest of it I couldn't understand because what you describe is just not C, as I learned it. From this, I conclude the problem smart people have with C is not their failure to understand. Rather, C has been turned into a different language, and some people who were fine with the old form don't want to accept that.

So there are 3 languages called C: K&R C, ANSI C, and pointers-aren't-real C. What a mess!

I've figured out why my friend thought arrays should work like that. They were local variables, which are (in Real C ) allocated on the stack. There's no possibility of holes in the stack.

The kind of UB I'm currently having a hard time with at work is data races. It's only been declared UB since C11, but before then there was no idea C had of multi-threading. If I understood it right, a data race occurs if two or more threads access the same memory location at the same time, and at least once for writing. Unless all accesses are atomic. So something as simple as one thread waiting on a variable set by another thread is a data race unless the accesses are made atomic.

Uhm... something I picked up over the years, and heard over and over again, is that you should NEVER access the same memory location from different threads without some means of synchronization. It's all right to do it from coroutines, but NEVER from parallel-executing threads. I've heard over and over again, "this can't be emphasized strongly enough." I can understand why: it's basically undefineable behavior. If a language appears to support it, it must insert synchronization primitives automatically, making it much higher-level than C.

Code: Select all

while (!(globvar->flags & FLAG_DONE)) ;

[...] A microblaze compiler I had pulled the test out of the loop and would go into an infinite loop if the test failed. An ARM compiler I had merely pulled the memory access out of the loop. Still, if the flag was not set by that time, it caused an infinite loop, since the variable was never reloaded.

Which is perfectly legit for non-volatile values.

What? So it's all right for optimization to arbitrarily change the meaning of the code unless explicitly but cryptically told otherwise? And note the volatile declaration could be far from the loop. There's nothing at all ambiguous about a conditional expression as an argument to a loop; no language should arbitrarily change its meaning for any reason! *furious eekee is furious!* lol I'm so glad I chose not to use C! I can't get on with the older C code of Plan 9, latest C is like this, *rage!* lol, so just... burn it all, I'll use something else.

There have been times I've wanted to use the equivalent of i>strlen(foo) in a loop condition, and sort-of felt that I would like the length-finding to be optimized away, but it's not terribly hard to take the strlen and assign it to a variable on the previous line. If that's what I meant the code to mean, that's what I should do, not the optimizer! Besides, that wasn't in C, that was in a scripting language which really should have had a simpler, terser way to iterate over the elements of a string or array.

It being a busy loop completely aside, I intensely dislike relying on side effects like that. (And, by extension, showcasing them.)

Imagine, for example, someone rearranges the source and makes that global internal linkage...

You and me both!

With all this undefined behaviour, I wonder if pointers-aren't-real C may have introduced more pitfalls than just using pointers the way they were meant to be used.

[Solar]

The only pointers you can definitely form are into arrays, and one element behind an array. So technically even casting addresses (numbers) into pointers is UB.

Neither of which is strictly correct. You can form pointers to anything. You can't do pointer arithmetic on pointers that aren't into the same array (and one element beyond). You can cast pointers to intptr_t or an array of unsigned char (object representation) and back, no problem.

So there are 3 languages called C: K&R C, ANSI C, and pointers-aren't-real C. What a mess!

No. Actually, there is only one language, C. Which has been formed into the international standard ISO/IEC 9899, of which several iterations have been released. Any superceded version, as well as any pre-standard "version" (K&R), is considered outdated. Which doesn't mean that there isn't lots of code for that version still around, or that it would be "wrong" to code against that version. It's a choice you make, based on available tools and resources.

I've figured out why my friend thought arrays should work like that. They were local variables, which are (in Real C ) allocated on the stack. There's no possibility of holes in the stack.

Note that C has no concept of "stack". It simply isn't part of the language. You think of local variables as "being on the stack", you've fallen into the trap of assumptions. Know what the language actually guarantees. Do not rely on a given implementation. Things happen to change from time to time -- consciously and well-advertised in case the standard itself makes breaking changes (which it seldom does). Possibly surprising and non-obvious at first glance if you've made assumptions.

Uhm... something I picked up over the years, and heard over and over again, is that you should NEVER access the same memory location from different threads without some means of synchronization. It's all right to do it from coroutines, but NEVER from parallel-executing threads. I've heard over and over again, "this can't be emphasized strongly enough." I can understand why: it's basically undefineable behavior.

Amen.

So it's all right for optimization to arbitrarily change the meaning of the code unless explicitly but cryptically told otherwise?

No.

The meaning of the code is quite clear: There's a variable being tested with no way it could change between tests given the restraints layed out by the language definition, so the compiler is explicitly allowed to shift the logic around. The rule here is called "as if": As long as the resulting code behaves "as if" without the optimization, the optimization is fine.

Two things to note here:

• Prior to C11, the standard had no concept of multiple control flows. Any such mechanics and definitions were extensions, usually through third-party libraries. As a corollary, the optimizer didn't have to "worry" about what some other thread might do. (That's what your "never access memory..." advice is about -- unless you actually use the mechanics offered by such extensions, such as <pthread.h>, the compiler may play dumb and just ignore such a thing as multithreading exists.) With C11, the memory model was finally well-defined... but that just means the standard now tells you explicitly that you have to be specific if you intend to access memory from multiple control flows.
• The "volatile" keyword is anything but cryptic; it has the explicit and sole purpose of telling the compiler that this is a value that may chance outside the control flow of the program, and may as such not be optimized e.g. out of a loop's condition.

And note the volatile declaration could be far from the loop.

As would be the type declaration, of which "volatile" is a part. Your meaning?

There's nothing at all ambiguous about a conditional expression as an argument to a loop; no language should arbitrarily change its meaning for any reason!

Well, without "volatile" in there, the point is that optimizing the conditional out of the loop (for a massive performance increase!) is not changing the logic of the loop.

Consider:

Code: Select all

int get_max( void )
{
    // TODO: Change this later.
    return 100;
}

int main()
{
    for ( int i = 0; i < get_max(); ++i )
    {
        do_something();
    }
}

Let's say we've written it this way because we know get_max() will be replaced with something complicated later on, and wanted to avoid having to make changes everywhere this value is used when the time comes.

A compiler could have that code call get_max() a hundred times. Or it could be smart enough to realize that the return value of get_max() is a constant expression (for now), and thus optimize it away.

This is what makes C (much) better at optimizing than Assembler.

And it's the same with your loop over a condition of which the compiler knows that it is not volatile.

lol I'm so glad I chose not to use C!

Tell me which language you use, and I (or someone else here) will tell you some intricacies of that language that are just as not-quite-that-obvious to someone who doesn't know it well enough yet.

I can't get on with the older C code of Plan 9, latest C is like this, *rage!* lol, so just... burn it all, I'll use something else.

Let's get back to an earlier quote of you:

And note the volatile declaration could be far from the loop.

"Older" C required you to make all declarations at the top of a code block. Languages evolve. If you try to keep things like they were yesteryear, you'll be left by the roadside. C89, C99, C11, C17. C++98, C++11, C++14, C++17. Java 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. Python 1, 2, 3. And so on. Adapt.

With all this undefined behaviour, I wonder if pointers-aren't-real C may have introduced more pitfalls than just using pointers the way they were meant to be used.

Don't be fooled. The places where behavior of C code is "undefined" are usually well described, and well understood. The whole purpose here was efficiency, allowing for minimal implementation and runtime, and still relieving the programmer from having to think of every micro-optimization himself. It also allows the standard library to cut quite some corners, again adding to the efficiency of the implementation.

Compare, for example, memcpy() vs. memmove(). C is very much a language that requires you to bring your own safety net if you want one, because the language doesn't provide it. If you need a safety net on general principles, use a different language.

----

I looked up the relevant part of the language specs for your reading pleasure.

9 An implementation might define a one-to-one correspondence between abstract and actual semantics: at every sequence point, the values of the actual objects would agree with those specified by the abstract semantics. The keyword volatile would then be redundant.

10 Alternatively, an implementation might perform various optimizations within each translation unit, such that the actual semantics would agree with the abstract semantics only when making function calls across translation unit boundaries. In such an implementation, at the time of each function entry and function return where the calling function and the called function are in different translation units, the values of all externally linked objects and of all objects accessible via pointers therein would agree with the abstract semantics. Furthermore, at the time of each such function entry the values of the parameters of the called function and of all objects accessible via pointers therein would agree with the abstract semantics. [...]

At which point I have to mollify my earlier criticism -- the side-effect the usleep() call had on the program was actually well-defined. A volatile declaration would still have been better (and more stable).

[nullplan]

Uhm... something I picked up over the years, and heard over and over again, is that you should NEVER access the same memory location from different threads without some means of synchronization. It's all right to do it from coroutines, but NEVER from parallel-executing threads. I've heard over and over again, "this can't be emphasized strongly enough." I can understand why: it's basically undefineable behavior. If a language appears to support it, it must insert synchronization primitives automatically, making it much higher-level than C.

I heard the same thing, but only for multiple writes at the same time. C11 makes it undefined behavior even if only one thread is writing and all others are just reading.

Neither of which is strictly correct. You can form pointers to anything. You can't do pointer arithmetic on pointers that aren't into the same array (and one element beyond). You can cast pointers to intptr_t or an array of unsigned char (object representation) and back, no problem.

Oh... so I that's what I got wrong. However, I will point out that this only works if intptr_t exists. And yes, any pointer can be converted to pointer of character type or void and back without loss of information. Also, pointers to character type are allowed to alias anything. Not that you would want to do that unless you like endianess issues.

Note that C has no concept of "stack". It simply isn't part of the language. You think of local variables as "being on the stack", you've fallen into the trap of assumptions. Know what the language actually guarantees. Do not rely on a given implementation. Things happen to change from time to time -- consciously and well-advertised in case the standard itself makes breaking changes (which it seldom does). Possibly surprising and non-obvious at first glance if you've made assumptions.

Could not agree more. C merely requires that recursion works to some depth, and that depth wasn't all that deep if memory serves. So automatic variables and call sites need some kind of stack-like data structure. But no-one ever said it had to be the same structure, or that it had to be supported by the CPU. Or that it grows downwards.

Don't be fooled. The places where behavior of C code is "undefined" are usually well described, and well understood. The whole purpose here was efficiency, allowing for minimal implementation and runtime, and still relieving the programmer from having to think of every micro-optimization himself. It also allows the standard library to cut quite some corners, again adding to the efficiency of the implementation.

Also, flexibility. The standard never defined what it means to cast a number into a pointer, because it might have different meanings for different platforms (cf. DOS, real mode far pointers). An implementation is thinkable in which doing so is simply meaningless. Imagine something like segmented address space, but with opaque segments.

[Solar]

Neither of which is strictly correct. You can form pointers to anything. You can't do pointer arithmetic on pointers that aren't into the same array (and one element beyond). You can cast pointers to intptr_t or an array of unsigned char (object representation) and back, no problem.

Oh... so I that's what I got wrong. However, I will point out that this only works if intptr_t exists. And yes, any pointer can be converted to pointer of character type or void and back without loss of information. Also, pointers to character type are allowed to alias anything. Not that you would want to do that unless you like endianess issues.

I looked it up in the standard to make sure I don't screw this up:

• You may take the address of any function or object (6.2.5 Types 20)
• A pointer to void shall have the same representation and alignment requirements as a pointer to character type (6.2.5 Types 28). A footnote clarifies that this is "meant to imply interchangeability as arguments to functions, return values from functions, and members of unions", and effectively means you can cast one into the other, but the standard does not explicitly say so.
• You may cast a pointer to type T to pointer to void and back (6.3.2.3 Pointers 1).
• You can store the byte sequence of any object other than a bit-field in an array of unsigned char (e.g. by memcpy()) (6.2.6 Representation of Types, 6.2.6.1 General (4)). The ability to restore such an object from unsigned char[] is implied.

And yes, intptr_t is, in fact, an optional type. As you might derive from the above legalese, however, it's pretty hard to picture a platform where intptr_t couldn't exist. (That would require a platform were there is no integer value as wide or wider than a void pointer that doesn't have trap representations. I know of no such platform.)

C merely requires that recursion works to some depth, and that depth wasn't all that deep if memory serves.

Actually there is no mention of any minimums or maximums to recursion (while there are minimums defined for many other things). It is merely stated that recursion shall be possible.

[eekee]

I should have stopped composing my post when I started laughing too much, or when I got angry even though I tried to make it funny. I wasn't thinking clearly. I particularly wasn't thinking when I looked at nullplan's example. I somehow thought it was separate to the race condition, and didn't look at the code properly. My anger was just a mood; no foundation.

Regarding C, for years I spent all my time with a group of people who relied on a specific implementation. I had a good strong reason for doing so: I couldn't get my head around C pointers until they explained to me they're just addresses. (My friend who made the array assumption is one of them. ) Re-thinking all this, I understand pointers better now. Thanks for the replies, everyone, especially you Solar!

Everything I thought I knew about C comes down to relying on the same specific implementation my friends do. Their reports of Thompson and Ritchie fighting standardization committes over C and Unix didn't help my perspective. (T&R gave up in the end, and even used a lightly extended C89 for Plan 9.)

Tell me which language you use, and I (or someone else here) will tell you some intricacies of that language that are just as not-quite-that-obvious to someone who doesn't know it well enough yet.

Oh, this will be fun: Forth. I can tell a few tales of intricacy myself. One non-obvious thing which held me up was compiling vs. interpreting. The words can refer to the current state of the interpreter, or to the semantics of the word the interpreter is currently looking at. As if that weren't enough, some words have no interpreting semantics, and others retain interpreting semantics at compile time.

A few years ago, I was hopelessly confused by a tutorial on making a Forth interpreter of the "double-indirect threaded" variety. The tutorial 'lied' about a critical detail for the purposes of simplification, and then made the mistake of explaining the lie in too much detail.

Earlier still, I was of course confused and put off by excessive detail in describing stack operation. Tutorials focused heavily on this, neglecting the simple attractive neatness it enables: code is a simple stream of words in natural reading order.* Definitions make exceptions, but don't really spoil the reading order.

*: And that reminds me of the intricacies of "bidi" text!

Huh... I think every intricacy which has confused me in any language has done so because tutorials focus heavily on explaining only one side of certain things. They focus on the one side they think will be most confusing, ignoring the possibility of students not knowing anything about the other side, or of knowing too much; having too flexible an understanding to make assumptions about the other side.


Recalling bad tutorials, I have a Forth anecdote to share. There was this book which was highly recommended years ago. Early in the first chapter, it made laughably false statements about the memory models of Forth and just-about every other language in existence! And backed them up with a prominent, clear, incorrect diagram! It explained about memory being addressed linearly, and stated Forth makes better use of memory because it makes allocations from one end of memory and has a stack growing from the other end. "Better" was relative to all other languages, which this tutorial claimed used memory as just one amorphous blob. I think that was rarely true at the time! Most languages, by design or practice, use a stack and a heap in the manner this "tutorial" ascribed to Forth, while Forth itself is less neat because it has, at minimum, a dictionary and two stacks.


Shifting from ridicule to contemplativeness and sad irony, I realise now my goal in my language hunt has been to minimize intricacies, and it looks like an impossible goal. I think of David Hilbert's goal of producing a logical self-consistent foundation for all of mathematics. Despite decades of effort and the involvement of many other highly-qualified mathematicians, he couldn't do it. "Wir mussen wissen, wir werden wissen," "We must know, we will know." The words were inscribed on his tomb, but we're still a long way from knowing. The words, and the situation behinf them remind me of the limitations of human ability; an ironic reflection. Despite all this, I haven't given up my language quest. My operating system quest is basically the same thing.

[Solar]

Thanks for the replies, everyone, especially you Solar!

Shifting from ridicule to contemplativeness and sad irony, I realise now my goal in my language hunt has been to minimize intricacies, and it looks like an impossible goal.

Well, you absolutely can go for a language with a minimum of intricacies. But that is just one scale among multiple others which in combination make up the usefulness of a language.

My personal favorite is C++, which I consider the most powerful all-around language there is. But I will never, for one second, deny that it's an ugly beast, and great care has to be taken when teaching it as to not overwhelm students with too many details too soon, too quickly. If done right, you'll end up with students who can tap-dance on top of the volcano that is the depths of C++, without skipping a beat when encountering something new. If done wrong, your students will either run away screaming in terror, never to return -- or sit in a corner, drooling. It's the exact opposite of "being without intricacies", but makes up for that in many other areas.

Which is why I understand the desire for a clear-cut language, but also know that you probably won't be really happy once you found it, because you optimized for only that one scale while neglecting the others.