1. 19
  1.  

  2. 4

    Nice article. The point is conveyed very well; it helps that the article is aptly named. However, I still miss the answers to the “why?” and “how?” questions.

    It is mentioned that this behavior is not implemented to annoy the user. I believe that, but I still can’t come up with any other reason. It seems like the compiler needs to detect access of uninitialized memory and chooses not to output an error or a warning, but chooses to implement all the logic on uninitialized values as “hah, I can do whatever I want here”. I expect the reality to be more nuanced, but I don’t see how from this article. Now, I am not the most careful reader in the world, and I may have missed something.

    On the other hand, you’d expect C compilers at least have an option to insert checks to avoid undefined behavior as well. For example, insert assert(x < 255); before the return in

    bool foo(uint8_t x) {
        return x < x + 1;
    }
    

    But C also chooses to not warn the user of undefined behavior. Again, there are probably reasons for this, but it doesn’t feel very sane to do this. Now you just can’t be sure that your program does not rely on undefined behavior to function correctly.

    1. 3

      I actually think an uninitialized value should be a random bit pattern. But here is an example of complications. Let’s call uninitialized value “poison”, and random bit pattern “undef”. One way to implement poison is to set output to poison if any of input is poison. But you can’t do that with undef! If undef is a random bit pattern, you are forced to do bit-level tracking. undef << 1 is not undef, because its LSB is 0, and (undef << 1) & 1 must be 0, not undef.

      These days, all optimizing compilers do bit-level tracking anyway, but it was a significant burden in the past.

      1. 2

        The “how?” is easy: C compilers track extra metadata about values when analyzing the program.

        The “why?” is optimization. Compilers first generate a naive unoptimized version of the program, and then optimize it in passes. Generating of fast code from the start has been tried, but multiple passes simplify the compiler and give faster output.

        So if we agreed that uninitialized memory isn’t “undefined”, but is some specific garbage pattern, then this:

        int x, y, z;
        

        in the first pass would have to generate some code that saves these random-but-specific values to make them behave non-magically later (e.g. allocates 3 registers or pushes 3 things to the stack). That’s obviously wasteful! So we’d like this to be optimized out (or moved to be an “accident” later), even if these values are not assigned to in all paths in the function. And the easiest way to explain that to the optimizer is to give them a magic “undef” value.

        Remember that when the code is being optimized, the machine code hasn’t been generated yet. Program sections haven’t been laid out yet. Registers haven’t been allocated yet. The only thing that exists is your program’s intermediate representation, so you can’t make the optimizer do “whatever the machine does”, because it’s in the process of deciding what the machine will be told to do.

        1. 1

          What if we agree that “unspecified” means that the memory is initialized to some unknown bit pattern and the compiler doesn’t need to know?

          1. 1

            Thanks, that helps a lot. Still, I don’t understand why a compiler would happily compile

            fn always_returns_true(x: u8) -> bool {
                x < 150 || x > 120
            }
            

            to a function that always returns true. Why would it be fine with comparing an uninitialized/undefined value? I still don’t see a sensible reason to not output an error or at least a warning. Unless I’m missing something, this is exactly the kind of reasoning that has lead to the abominable situation with undefined behavior in C.

            1. 2

              It’s an effect of the optimizer having only a local view of the problem. Optimizing anything-you-want < 150 makes sense on its own. Why generate a comparison instruction if you’re allowed to hardcode it to false?

              Such nonsense code may happen in legitimate situations. For example, it could have been if status < OK to do error handling in a function, and the function has been inlined in a place where the compiler can see the error won’t happen, so it can remove the whole error handling code.

              There’s UB in every correct C program. For example, int + int is UB if the values overflow. The compiler can’t warn about using +! But it does take advantage of the UB to avoid generating sign-extend instructions, simplify arithmetic and loop end conditions.

              https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759de5a7

              1. 2

                Thanks for your answer. I gave it some time but I’m still not convinced that this is useful behavior.

                It’s an effect of the optimizer having only a local view of the problem. Optimizing anything-you-want < 150 makes sense on its own. Why generate a comparison instruction if you’re allowed to hardcode it to false?

                I can see that in general, undefined behavior allows some optimizations. The particular case of comparing with a variable that is guaranteed to be uninitialized just seems to be something that deserves a hard error. I can’t imagine this being useful in any way.

        2. 2

          Don’t forget that there’s (er, usually) a whole OS between your program and the hardware. I remember reading once that Windows has a service that zeroes unallocated memory for later use, for security and bug-reproducibility. Another reason that “uninitialised” normally doesn’t mean “random bit pattern.”

          Also, shout-out to Zig for writing 0xAA to uninitialised memory in debug mode. Very easy to spot.

          1. 4

            When I write uninitialized memory with a value, I take pains to pick a value that’s useful for the CPU the code will run on. For x86 platforms, 0xCC is a better choice––it’s still a large negative number if read as a signed integer; a very large number if read as an unsigned number; and address of 0xCC… probably doesn’t exist, and if executed, it’s the INT3 opcode. I used to use 0xAB on Motorola 68k CPUs—it’s a large number, if used as an address it most likely doesn’t exist, and excluding a byte-read, it will trap as an unaligned access, and as an opcode, it’s undefined (as any opcode starting with 0xA is undefined).

            I used this method because I figured I could use all the help I could get.

            1. 3

              This is something the author was explicitly trying to suggest is not relevant.

              The OS guarantees to zero memory before giving it to your process. Why? Because previously that memory was from some other process, and it may have sensitive information which your process is not supposed to see.

              But then what? The moment your process allocates memory, frees it, and allocates again, there are now two legitimate outcomes: maybe the new allocation comes from adding pages to your process, which are guaranteed zero; or maybe it came from the previous allocation, which contains whatever garbage your process put there before. So your process can’t assume that memory that it allocates is zeroed.

              Without commenting on the rest of the article, this is yet another case of “virtual machine within a machine”, where the OS is doing things the hardware wouldn’t do, and those effects are observable.

              1. 1

                Mea culpa. I can’t tell you why I failed to ingest that information in the article.

            2. 0

              The real issue is the C and C++ languages are horrible languages. They’re too high-level to correspond to any real machine, yet so low-level so as to make such an abstract machine useful. The C language leaves the precise lengths of types up for grabs, as merely one example. As for Rust, I’d figure it’s poor as well, considering it follows in the footsteps of C++.

              I can compile an Ada program that has an uninitialized variable and use it, but I get a warning; there’s also a Valid attribute that acts as a predicate for whether a scalar value has an acceptable value or not.

              To @vyodaiken , you’re mistaken to believe the C has any ’‘brilliant’’ design behind it. There are many things where one requires a certain range of values and C forces the programmer to use a type that’s much larger than necessary and cope with unwanted values. The C language leaves details to the underlying machine, so long as that machine is determined to pretend it’s a PDP-11.

              Abstract language details are necessary for a high-level language and can work quite well if the language is designed well; this then leaves high-level features to be implemented in whichever way is best for the machine; the C language doesn’t do this well at all, however, and precisely specifies the nature of irrelevant details and so hinders the machine and implementation possibilities.

              The C language doesn’t even have true boolean values or arrays thereof. You’re expected to use an entire integer that’s zero or not and you’re left to your own devices if you want an array of these values that isn’t grotesque in its wastefulness. Meanwhile, most proper languages have the concept of types that only have two values and can easily use an underlying machine representation for efficiently representing these, without involving the programmer.

              In closing, you may argue that C is necessary because it permits specifying these low-level details, albeit required in every case instead of only where necessary. To that, I direct you to look at Ada, which permits the programmer to ignore such details wherever unneeded, and so leave them to the compiler’s discretion, but allows size, address, representation, bit-level organization, and more to be specified in those cases where it’s truly necessary.

              Here’s a link you or others may like for learning more about Ada and the deficiencies of C:

              https://annexi-strayline.com/blog

              1. 4

                In what ways does Rust “follow in the footsteps” of C++, except syntactically?

                1. 4

                  To @vyodaiken , you’re mistaken to believe the C has any ’‘brilliant’’ design behind it.

                  It’s perfectly understandably that people might think there are better alternatives to C and come up with arguments for that position. But C is an incredibly successful programming language, designed by some of the most brilliant Computer Scientists of the time. Dismissing it as a design botch, to me, is something one can do only on the basis of ignorance. There are compelling reasons why C, which began as an unloved stepchild of ATT was rapidly adopted by the systems programming community in place of really interesting corporate alternatives (e.g. Bliss) and Ada which was the DOD annointed future programming language. Those reasons do not include “everyone else is stupid”.

                  1. 1

                    Is the blog yours? I would be interested in following it but it does not appear to have an RSS feed. I tried to send a message via ‘contact us’, but, ironically for a reliability-focused consultancy, I got an error on submission.

                  2. [Comment removed by author]

                    1. [Comment removed by author]

                      1. 2

                        I think you are talking past each other. Ralf is of course correct about current C specification and current LLVM implementation. But that’s different from what they should be.

                        When Ralf says “Many people will tell you that uninitialized memory contains a random bit pattern. This is wrong.” (with proof!) or “What the hardware does considered harmful”, it is about status quo. It is a fully consistent position to hold that C specification should be updated such that “uninitialized memory contains a random bit pattern” is a correct way to reason about C programs, even if it is incorrect to do so now. I think it is even possible to support such position on the ground that “because that’s what the hardware does”. If such update is done, the proof in the post would be considered a bug in LLVM that should be fixed.

                        1. 5

                          I talk about this “talking past each other” pattern a bit in my blog post on UB, where, I talk about three camps. It’s obvious vyodaiken is in the “semi-portable” camp and Ralf’s post is rooted in the “standard C” camp. This debate comes up reliably enough I think it would be possible to fine-tune a GPT-2 model to generate a convincing comment thread on the subject.

                          1. 0

                            The C standard contradicts itself - as it clearly states that one of the design objectives of the language is to act as a portable assembler, but then provides a bunch of poorly specified “abstract machine” ideas that make use as a portable assembler impossible. Which is why Linux is developed in a C dialect that is closer to the K&R book than to the current standard.

                          2. 2

                            Imagine a program that uses a POSIX shared memory call to map to a shared memory segment provided by a server of some sort. According to the Abstract Machine, that memory is uninitialized, but according to engineering reality, it is not. I don’t know how, e.g. memory mapped file access even works in this model.

                            1. 3

                              POSIX modifies the C standard (kind of, in a manner of speaking). For instance, in C, a null pointer has no set value, but at the source level, a literal 0 in a pointer context is converted to whatever value is needed for a null pointer (it could be all 1s for instance). POSIX mandates that a null pointer be all 0s. C states you can’t assign a function pointer to a void pointer; POSIX lifts that requirement and says “yes you can.”

                              Now, does that mean a C compiler compiling POSIX code isn’t standards conforming is a good question, and one I do not have the answer to.

                              1. 1

                                Once you start looking at how the “abstract machine” of the C standard interacts with the OS/architecture, you see what an unfixable mess is created by gluing the abstract machine model to the C language. Threads totally fail with the abstract machine:

                                char x[2048]; ... create a thread and wait for it to send data
                                over a pipe after it has initialized x; reference x
                                

                                is x uninitialized when the main program reads it? not if the threading was done right. Can the compiler figure that out? No. I/O is similar. signals, longjmp/setjmp, … - not to mentionr references to device memory. The fundamental assumption of the abstract machine is that the program is a closed system, but that invalidates 50% or more of working C code.

                          3. 0

                            Oooh! An argument by someone else’s authority! Ralf is making the argument that C (and Rust) semantics should be defined in terms of an abstract machine - but that’ s because he rejects the basic design basis of C ( I dunno about Rust) which is to leave much of the semantics to the processor and OS. The “abstract machine” semantics replaces something well defined and easy to understand with a crappy semi-formal model that is inherently broken. For example, working C can call out to POSIX functions to remap the memory space, which is something the abstract machine described in the C11 standard cannot begin to represent. Similarly, C’s “volatile” type modifier has a completely well defined meaning that is poorly represented in the abstract machine. In order to write low level systems code in a higher level language, it is imperative to allow for interaction with hardware defined and OS defined components that are not subject to the ideas of whoever is designing the abstract machine. If Ralf’s point of view depends on his PhD on semantic models of system programming languages, it only illustrates the limitations of that field.