Month: May 2021

Categories
C standard computer architecture programming languages

unfashionable C

In computer science academia, C  along with UNIX, and PDP11s, is as unfashionable as can be: the equivalent of other 1970’s relics, like polyester leisure suits and mullets.

In 2018 ACM Queue published an essay by David Chisnall called: C Is Not a Low-level Language: Your computer is not a fast PDP-11  that expresses many common misconceptions about C and also takes the time to make a bunch of incorrect claims about computer architecture.  The same authors 2015 ASPLOS paper  Beyond the PDP-11: Architectural Support for a Memory-Safe C Abstract Machine   has much more interesting information about how C is used in practice and about an alternative computer architecure, but I want to focus on the first, because I think the general tendency in academic Computer Science to dismiss C as an embarassing fashion faux-pas has important consequences.

Let’s go through some of Chisnall’s article, starting with  this  claim:

“Most of the complexity involved [in hardware caches] comes from supporting a language [C] in which data is expected to be both shared and mutable as a matter of course.”

Although the recent C11 standard tried to graft on some ideas about concurrency (not a good idea or well done either), historically C doesn’t have  have any notion of concurrency or data sharing1. The first wide use of “threading” in C applications involved UNIX fork/exec which doesn’t share any memory at all. The language designers made a conscious, and successful,  choice to leave such things outside the scope of the language.

BSTJ 57: 6. July-August 1978: UNIX Time-Sharing System: The C Programming Language. (Ritchie, D.M.; Johnson, S.C.; Lesk, M.E.; Kernighan, B.W.

The poor judgment of the C11 authors didn’t really change that.

“Creating a new thread [in C ] is a library operation known to be expensive,

C has threading libraries, but none of them is required (otherwise you couldn’t develop operating systems in C or support multiple thread models).   C thread creation is also not known to be expensive. Determining factors are implementations,  processor architectures, and, for user threads, operating system interfaces.

so processors wishing to keep their execution units busy running C code rely on ILP (instruction-level parallelism).” 

Instruction level parallelism predates  C by 10 years and is not specific to any programming language. The first production computer  with ILP  was the CDC 6600, brought to market in 1964 and intended to run FORTRAN.

In the wake of the recent Meltdown and Spectre vulnerabilities, it’s worth spending some time looking at root causes. Both of these vulnerabilities involved processors speculatively executing instructions past some kind of access check and allowing the attacker to observe the results via a side channel. The features that led to these vulnerabilities, along with several others, were added to let C programmers continue to believe they were programming in a low-level language, when this hasn’t been the case for decades.

The CDC 6600 also had speculative branch prediction as did the IBM 360/91 (1967).  C was developed in the 1970s, well after and only became popular in the 1980s or later.

The root cause of the Spectre and Meltdown vulnerabilities was that processor architects were trying to build not just fast processors, but fast processors that expose the same abstract machine as a PDP-11. This is essential because it allows C programmers to continue in the belief that their language is close to the underlying hardware. In contrast, GPUs achieve very high performance without any of this logic, at the expense of requiring explicitly parallel programs.

Let’s go through these:

  • GPUs are primarily programmed in C dialects, so I’m not sure what is going on there. Using C was the easy choice for GPU makers  because of C’s deliberately incomplete nature (see below).
  • What C programmers believe about  C does not matter to computer architects.
  • The root cause of the Spectre and Meltdown failures is that it is really hard to do out-of-order pipelines with speculative execution and buffered memory access (there is way too much state moving too fast) but the performance advantage makes it hard to pass up.
  •  As for PDP-11s, this is a common error.  C was ported to  IBM/370, Honeywell 6000, Inter data 8/32, Sel86, Data General Nova, Vax and other processors in the mid 1970s – back in the days when there were multiple very different machine architectures.  By the mid 1980s,  when C  was becoming a popular language, and the ANSI standard was developed  the successor VAX architecture supported SMP and C was already highly popular on microprocessors. Much of what changed in C in that era was to make it portable to that wild profusion of architectures.

It’s worth noting that  Chisnall knows this last complaint is wrong, as he writes later:

The C model, in contrast, was intended to allow implementation on a variety of targets, including segmented architectures (where a pointer might be a segment ID and an offset) and even garbage-collected virtual machines.

In any case, although dismissing the PDP11 is  in vogue, the PDP-11 always had an MMU and caches and had parallel processing (with DMA capable devices and co-processors). Although the  article subhead is “Your computer is not a fast PDP-11”, really it is pretty much – just vastly larger (in terms of transistors ),  and faster.  Processor architectures today incorporate a lot of innovation, but use the same basic model programmers encountered 50 years ago and  X86-64 and ARM are both much closer to the PDP-11, for good or ill,  than to the 36 bit Honeywell 6000, the Interdata 8/32  ,  or the Intel 8086 and I486 for that matter.

Let Professor Hennessy explain:

 

From  John Hennessy https://p4.org/assets/P4WS_2019/Speaker_Slides/9_2.05pm_John_Hennessey.pdf

But Chisnall is not done with C.

We have a number of examples of designs that have not focused on traditional C code to provide some inspiration. For example, highly multithreaded chips, such as Sun/Oracle’s UltraSPARC Tx series, don’t require as much cache to keep their execution units full. Research processors2 have extended this concept to very large numbers of hardware-scheduled threads. The key idea behind these designs is that with enough high-level parallelism, you can suspend the threads that are waiting for data from memory and fill your execution units with instructions from others. The problem with such designs is that C programs tend to have few busy threads.

None of these are new or untested ideas. The Cray MTA architecture was a really interesting design that was even built and commercialized and it was designed to run C and Fortran.   The problem with such designs is that highly threaded algorithms are difficult and sometimes impossible (see Amdahl’s Law) in general. The exceptions are specialized processors such as GPUs (where C is used!).

For example, in C, processing a large amount of data means writing a loop that processes each element sequentially

In the Von Neumann style computer architecture (every single existing commercial processor), data is stored in memory and must be brought through the “Von Neumann bottleneck” into the processor. Caches help, and for certain types of processing, data can be moved and modified in larger chunks (vectors) which can be modified in parallel (SIMD processing is another 1960s innovation as explained in most intro computer architecture courses).   When the processor can operate on those longer vectors, it still relies on loops with the same characteristics as loops over bytes for large amounts of data.  Dennis Ritchie thought that C was too limited in its treatment of arrays, but being able to e.g. apply  a map to an array in the programming language just hides the loop.  Writing  \(A.map(x -> x*x)\) doesn’t magically transfer the whole array into the CPU vector unit which can, at best, multiply only a few elements at a time. For big arrays, it is still necessary to loop through the data, and for small arrays, there is not much to win ( here are some other ideas). Chisnall knows this too, because he’s unhappy at how hard it is to compile  vector loops in C.

To run this optimally on a modern CPU, the compiler must first determine that the loop iterations are independent. The C restrict keyword can help here. It guarantees that writes through one pointer do not interfere with reads via another (or if they do, that the programmer is happy for the program to give unexpected results). This information is far more limited than in a language such as Fortran, which is a big part of the reason that C has failed to displace Fortran in high-performance computing.

 Intel’s comments on the problems of vectorizing C and FORTRAN say the opposite. Vectorization is a hard problem – C’s restrict keyword is a good clue to the compiler, and possibly a vector data type would help (as the author argues)  but FORTRAN doesn’t have better information for the compiler. What FORTRAN has (a) no pointers which makes things simpler and (b) a whole lot of special purpose compiler directives and expert programmers who know how to exploit data parallelism.  FYI: C was not  intended by its designers  to displace Fortran in HPC.

Unfortunately, simple translation providing fast code is not true for C. In spite of the heroic efforts that processor architects invest in trying to design chips that can run C code fast, the levels of performance expected by C programmers are achieved only as a result of incredibly complex compiler transforms. The Clang compiler, including the relevant parts of LLVM, is around 2 million lines of code. Even just counting the analysis and transform passes required to make C run quickly adds up to almost 200,000 lines (excluding comments and blank lines).

Much of Clang’s complexity (and the same for GCC) comes from its role compiling C++ which is a gigantic language that  incorporates C as a sublanguage. Additionally, LLVM is designed as a general platform for a number of languages and  LLVM’s complexity is far from C specific.   What would be very interesting to know is how much of Clang’s C performance comes from anything past the 40 year old basic optimization methods like register coloring, peephole optimization, vectorizing and maybe unrolling loops. But here we turn to  real issues:

In C, a read from an uninitialized variable is an unspecified value and is allowed to be any value each time it is read. This is important, because it allows behavior such as lazy recycling of pages: for example, on FreeBSD the malloc implementation informs the operating system that pages are currently unused, and the operating system uses the first write to a page as the hint that this is no longer true. A read to newly malloced memory may initially read the old value; then the operating system may reuse the underlying physical page; and then on the next write to a different location in the page replace it with a newly zeroed page. The second read from the same location will then give a zero value.

This is an interesting point, because it reveals a common problem in current criticisms of C – and of the current efforts of the C Standards and C Compilers: a failure to understand the open border C design or maybe just dislike for it. C was intended as a systems and particularly operating systems language. Unlike Java and most other programming languages, a C program interacts directly with the hardware (and operating system) and other interfaces. Stephen Kell has a paper on precisely this point. That’s why C has no foreign function interface (FFI) but can directly call out to assembler or even support in-line assembler (and C doesn’t have an unsafe mode, because it is an unsafe mode).  Although the C standard document goes on about the “abstract machine”, C gets a lot of its utility from being able use operations that are semantically defined by hardware or other external interfaces. C benefits from incomplete semantics (which is why the ongoing mess about undefined behavior is so damaging to C programmers).  In the case mentioned by Chisnall, the FreeBSD operating system is playing games with the page allocator so allocated pages may not act like abstract store until a write operation2. This should not matter to a C program, because, especially in OS programming, this kind thing is not unusual.  Weird interactions with memory are one reason why C has the concept of intederminate values.  C code can even read device memory that changes its value on each read (think of a hardware fifo from a Analog-to-Digital sensor, for example). In these cases, the C compiler is supposed to let C operate as a high level assembly language and stay out of it.

And then Chisnall makes a really good point.

If an unspecified value for flow control is used (for example, using it as the condition in an if statement), then the result is undefined behavior: anything is allowed to happen. Consider the loop-unswitching optimization, this time in the case where the loop ends up being executed zero times. In the original version, the entire body of the loop is dead code. In the unswitched version, there is now a branch on the variable, which may be uninitialized. Some dead code has now been transformed into undefined behavior. This is just one of many optimizations that a close investigation of the C semantics shows to be unsound.

The important observation here is that  under the current interpretation of the C standard, a number of compiler optimizations are unsound and have been for some time. This has been tolerated because C is so very out of fashion and there is little appreciation of  the basic design concepts of the C language (except from people who use it.)  What is going on here is that standards contributors and compiler developers who start with the assumption that C is an obsolete and semantically confused language feel no obligation to play fair with the programmers who they believe are making a mistake even wanting to write code in the language.  This is why Chris Lattner of LLVM ends his gloomy (and insightful) analysis of the state of C compilation with a suggestion that programmers should switch to another language (like his own). And that is unfortunate because  C is far from a perfect language and slow changes in computer architecture are frustrating, but if you don’t know what works and what doesn’t work, you won’t be able to fix anything. And, finally, some things from the 1970s were pretty good.

 

NOTE 1: The unnecessary complexity of shared data in caches is unpleasant but that’s not C’s fault.

NOTE 2: The much loathed Bourne Shell, in addition to using the pre-processor to pretend it was written in ALGOL for unknown reasons, also implemented a user mode virtual memory with C/UNIX signals. It allocated virtual memory addresses without bothering to call the OS for more memory, and then caught write traps and tried to fix things.

Categories
C standard

Undefined behavior in C is a reading error.

Considering how important “undefined behavior” has become to C semantics and the ISO/IEC JTC1/SC22/WG14 Committee, the lack of any reference to it in the K&R ANSI book is notable and the description in the 1999 C Rationale was quite modest.

Undefined behavior gives the implementor license not to catch certain program errors that are difficult to diagnose. It also identifies areas of possible conforming language extension: the implementor may augment the language by providing a definition of the officially undefined behavior. – C Rationale

And yet, a misreading of C89 has turned this simple property into a serious threat to C semantics.

The destructive prevailing interpretation

The governing provision in C89 starts:

Undefined behavior — behavior, upon use of a nonportable or erroneous program construct, or of erroneous data, or of indeterminately-valued objects, for which the Standard imposes no requirements.

The obvious reading of this passage is that it simply naming the class of behaviors where the Standard doesn’t specify what happens as “undefined behavior”.  But almost immediately, this passage was interpreted by self-appointed experts on the comp.lang.c mailing list  to mean that  “the Standard imposes no requirements” on how compilers can implement undefined behavior. This became the prevailing interpretation and C compilers rely on it to justify all sorts of “optimizations” even though it is an unlikely reading of the text and damages the semantic coherence of the language.    John Regehr explains some consequences, using the example of the surprising  undefined behavior caused by shifting  by more than the number of bits in an “int”:

If any step in a program’s execution has undefined behavior, then the entire execution is without meaning. This is important: it’s not that evaluating (1<<32) has an unpredictable result, but rather that the entire execution of a program that evaluates this expression is meaningless. Also, it’s not that the execution is meaningful up to the point where undefined behavior happens: the bad effects can actually precede the undefined operation.

So, “i << 32” buried in a million lines of database code makes the entire program junk – supposedly as an “optimization”!  That is not the end of the destructive super powers of undefined behavior under the prevailing interpretation, because the compiler developers claim that no requirements are imposed on when they can change how they implement undefined behavior.  Chris Lattner of LLVM warned  that thanks to unrestricted undefined behavior, “huge bodies of C code are land mines just waiting to explode.” The argument is that maybe something  worked in one  way for 20 years, but it was always undefined behavior so the compiler is free to delete it, detonate it, replace it with something else or change behavior in any way, at any time (see this peculiar argument on the gcc bug list ).  Apparently, even then, the compiler could change its mind tomorrow or 5 minutes later!   Parsing it out, the prevailing interpretation reads the passage as follows (and note that we have to delete the comma after “behavior” to make it work):

behavior upon use of a nonportable or erroneous program construct, or of erroneous data, or of indeterminately-valued objects:  The Standard imposes no requirements on this behavior  (even as to stability!).

This reading would imply that use of any nonportable program construct or data error or indeterminately-valued object produces undefined behavior  but  WG14  is  not  ready to suppose that the ANSI C standard invalidated nearly every C  program (system calls are nonportable, for example, and malloc returns a pointer to indeterminately valued objects).  Under the  prevailing interpretation “imposes no requirements” is the only operative phrase: the WG14 Committee ignores “use of a nonportable or …”  from the text, and   has built out a long, ad-hoc list of uses that produce “undefined behavior” ( compiler developers have expanded  the list  on their own initiative without documenting much).  The WG14 Committee   also ignored the next sentence in C89, which is an apparent contradiction because it —  imposes requirements on how compilers may implement undefined behavior.

Permissible 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).

In terms of ISO/ANSI conventions, this second sentence is “normative” (imposes requirements) and “Permissible” is a “shall” word (meaning “must” ). The permissible range of undefined behavior went from ignoring the situation (for those difficult to diagnose errors per the Rationale)  to behaving in a documented manner characteristic of the environment, to flagging an error. What is conspicuously missing from this list of permissible undefined behaviors is any hint that undefined behavior renders the entire program meaningless,  any  license for the kinds of  dramatic and unintuitive transformations we’ve seen from the compilers, and any indication that undefined behavior should be a vehicle for permitting optimizations.

A constructive interpretation.

The more constructive interpretation is that the intention of the first sentence was specify that “undefined behavior”  was what happened when the programmer used certain constructs and data, not otherwise defined by the Standard.

Undefined behavior — behavior,  upon use of those particular nonportable or erroneous program constructs, or of erroneous data, or of indeterminately-valued objects, for which the Standard imposes no requirements.

That is, we take the comma seriously so  that the sentence is read to be limiting the category of “undefined behavior” to uses of certain constructs and data that have not been otherwise defined in the Standard. The sentence doesn’t say anything about implementation, because that is covered in the next sentence with the permissible list. Returning a pointer to indeterminate value data, surely a “use”, is not undefined behavior because the standard mandates that malloc will do that.  Use of “asm” does not cause undefined behavior although it is  nonportable because the standard (glancingly) mentions using asm.  Instead of unleashing the compiler to make arbitrary changes, the provision limits what the standards process could dump into the  undefined behavior bucket.  With this interpretation, the passage as a whole makes sense – and is in agreement with the Rationale. We don’t have to ignore the list of uses that can trigger undefined behavior, we don’t have to ignore the range requirements of the second sentence, we can get some intuition about what should be undefined and what should not be, and undefined behavior stays  a manageable concept, instead of creating a giant breach in the hull of the semantics. In retrospect, it may have been an error to  believe everything claimed  in internet discussion forums like comp.lang.c.

Consider the shift example from Linux that Regehr mentioned. Under the constructive interpretation, compilers would have to choose some  “in range” option in place of an “optimization” that doesn’t optimize anything:

  1. ignore the situation, generate a “shl” instruction for x86 or the appropriate instruction for other architectures and let the machine architecture determine the semantics. In this case, the programmers screwed up because x86 will truncate the shift value to 5 bits but the “permissible range” allows the compiler to escape all blame and let the programmers either find the problem or not.
  2. behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message) – warn the programmer on an X86 and just compile on ARM.
  3. terminating a translation or execution (with the issuance of a diagnostic message) – “Error: Guard your shift left to a machine appropriate number”.

Explaining why the Standard text would decree that  no requirements are imposed in one sentence and then go on to  impose requirements in the next sentence was apparently awkward, so the WG14 committee solved the problem by making a submarine change to the passage in C99.

Undefined behavior —

behavior, upon use of a nonportable or erroneous program construct, of erroneous data, or of indeterminately-valued objects, for which the Standard imposes no requirements. [insert newline]

2 NOTE Permissible 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).

Thanks to Eskil Steenberg for pointing out the difference between C89 and C99 on this point.  Under ISO rules, inserting the word “NOTE” changed the second sentence from “normative” (mandatory) to non-normative (advisory or informational), and  replacing the requirement word “Permissible” with the informational word “Possible” emphasized the optional nature of the range of behaviors. Currently, this second sentence is completely ignored in WG14 deliberations and apparently is also ignored as even a suggestion by compiler developers. Someone felt the need to weaken this sentence, I can’t find any records of the discussion.

The Prevailing interpretation is fatal to C

So what does it matter that 40 years ago, a murky section of an often murky document could have been misinterpreted?  It matters because over time the Standard and the common compilers have  made C an unsuitable language for developing a range of applications, from memory allocators, to cryptography applications, to threading libraries and, especially operating systems. We have the absurd situation that C, specifically constructed to write the UNIX kernel, cannot be used to write operating systems. In fact, Linux and other operating systems are written in an unstable dialect of C that is produced by using a number of special flags that turn off compiler transformations based on undefined behavior (with no guarantees about future “optimizations”).  The Postgres database also needs some of these flags as does the libsodium encryption library and even the machine learning tensor-flow package.

Because the prevailing interpretation of undefined behavior is so powerful, WG14 and the compiler developers have made it their goto method to  enable  “optimization” and  add to type safety and other rules. Instead of adding rules for optimization in the optimization section of the standard, WG14  has preferred to expand the domain of undefined behavior (often based on completely unsupported assumptions about efficacy) so compilers have a free hand. Instead of coming up with coherent rules for how to access memory via pointers, WG14 has simply declared a large part of customary C usage to be undefined behavior and left it to the compilers to figure out what that means.  As a result, as Lattner pointed out this means the C code base is unstable and:

There is No Reliable Way to Determine if a Large Codebase Contains Undefined Behavior

Compilers have become more powerful (opening up new ways to exploit undefined behavior) and the primary C compilers are free software with corporate sponsors, not programmer customers (or else perhaps Andrew Pinski would not have been so blithe about ignoring his customer Felix-gcc  in the GCC bug report cited above). All these help C semantics continue to degrade. There is even  a widely supported (within the standards body) proposed addition to the C Standard which will radically expand the application of undefined behavior to pointers.

None of this is necessary. C can accommodate significant optimization while regaining semantic coherence – if only the standard and the compilers stop a lazy reliance on a mistaken reading of “impose no requirements”.  A standard is supposed to impose requirements and provide clear guidance to programmers and implementors.

See also:   the PLOS paper, or Undefined Behavior and the Purpose of C” , Torvalds on alias, Dennis Ritchie on noalias, and a really simple example

Thanks to Robert Seacord and Eskil Steenberg for reading early versions of this note and providing suggestions.

Categories
C standard programming languages software security

C is not a serious programming language

The C Standards process over the last few decades has addressed both optimization and pointer type safety largely through a concept called “undefined behavior”.  The idea is that instead of  positive rules for what compilers and programmers can do, the Standard will identify some program behavior as something compilers can interpret how they want — really without any guidance at all. These things are not syntax errors that must cause the compiler to reject code or even, necessarily things the compiler must warn about, but are instances of behavior that are outside the standard. It is not even clear whether “undefined behavior” is erroneous at all or even avoidable.  I think this whole process is due to a misreading of the C89 standard, but more importantly, it’s sloppy, makes it hard for programmers to have an intuition about the language, and leads to paradoxical results or nasty surprises.  For example, writing a value to a  variable from a pointer that has been advanced past the end of the object it was supposed to point to has been sort-of-kind-of designated as “undefined behavior”. Here’s  an example: the output of a simple C program compiled and “optimized” by gcc 11

pointer1 = 0x404039 pointer2=0x404039 they are not equal

They look equal, don’t they? Clang 12, on the same code uses  normal arithmetic to compare numbers.

pointer1 = 0x404039 pointer2=0x404039 they are equal

An earlier version of gcc, gcc 4.8.3 also knew how to compare numbers:

pointer1 = 0x404039 pointer2=0x404039 they are equal

And Gcc 11 again, but this time with the optimizer turned off (-O0):

pointer1 = 0x40403a pointer2=0x40403a they are equal

Here’s the code ( see NOTE1 in the code )

#include <stdint.h>
#include <stdio.h>

typedef char T;
T p[1], q[1] = {0};
int main(){
        T *ip = (p-1);//NOTE1. change +1 to -1 if gcc -O0
        T *iq = q;
        printf("pointer1 = %p pointer2=%p ",ip,iq);
        if (iq == ip) {
              printf("they are equal");
             }else printf("they are not equal\n");
}

The explanation is that gcc notices that ip has been set to a fishy address

:6:8: warning: array subscript -1 is outside array bounds of 'T[1]' {aka 'char[1]'} [-Warray-bounds]
6 | T *ip = (p-1);//add if gcc -O0
|  ^~

and, gcc 12 helpfully “optimizes” on the basis of “ip”  holding an “invalid” address, perhaps reasoning that the two pointers “cannot” be equal. Under the prevailing interpretation of the C Standard, compilers can assume “undefined behavior” cannot happen, even if they generate code that makes it happen  At least, in this case, there is a warning, but often these “optimizations” are silent. The rationale is that programmers should not be messing about looking at the order of variables in memory (even though that’s not unusual in C) and that compilers should be able to optimize under the assumption that pointer arithmetic does not ever steer a pointer between objects.  To be fair, most of the time that a pointer goes beyond the boundary of an array, it is an error.

Here’s the link on Compiler Explorer. The example is modified from one given in a post by  Ralf Jung  who attributes it to Chung-Kil Hur (I’m sure both disagree with my reaction).

If C was a new programming language, you might decide that the %p output should provide the address and some additional data.

pointer1 = 0x404039 (int) pointer2=0x404039 (int, invalid)  they are not equal

That would make some sense. But in this case, you’d also have to think through all the implications of this design decision, which nobody has done (see below).  For example, since the 1990s, C Standard has made it impossible to write memory allocators in conforming C. Suppose we have a network application that is performance constrained by “malloc” and we want to put a caching allocator for small and jumbo packets on top of malloc:

(small_packet_t *)newsmall();  (large_packet_t *)newjumbo();  freepacket(void *);

The idea is that when either allocator has too little memory, it calls malloc (or something else) to get a big chunk of memory, puts it into a list of free storage, and slices it up when it is asked to allocate. Maybe something like

free_block_t *p; …. p =malloc(K); p->size = K; p->next = Head; Head = p;

But according to the sloppy type rules in the Standard, after writing through a “free_block_t” pointer, that block now has “effective type”  of “free_block_t” and if we allocate part of it to a caller that then writes to it as a small_packet_t, the behavior is undefined and all bets are off because we have tried to store a value to an object with a different effective type. Even worse, imagine that “freepacket” tries to merge freed packets into blocks again! Suppose 4 small packets can be freed and then consolidated and allocated as a single jumbo packet.  Nope. No can do.  Once storage has an effective type, it is frozen to that type.  How does malloc/free work then? Oh, easy, it is special cased in the standard. Similarly, there is a special case for char pointers so that memcpy can be implemented, even if not very efficiently. To get other allocators to work, C programmers rely on “opaque” interfaces. If the allocators are in a separate file, and we do not have link time optimizers, then probably the compilers won’t be able to learn that the type rules are being violated. But then as link time optimization (LTO) comes in, the whole thing may silently be “optimized” to fail.   One of the other ridiculous  properties of the undefined behavior rules is that they are unstable or ephemeral and depend on the current capabilities of the compiler to see through opaque interfaces or otherwise figure out about some particular instance of undefined behavior.  That is, the rule is something like: “this will work as expected until the compiler figures out that it is undefined behavior”. As you can see above, gcc learned to recognize the undefined behavior somewhere between versions 4.8 and 11 and still can’t figure it out at lower levels of optimization.

Here’s another “optimization” from Clang-C

int are_we_out_of_memory(void) {
        int *y = malloc(2);
        return y == (int*)NULL;
}

Under -O3 optimization, this always returns 0 in Clang-C. Why?  Perhaps in this case Clang is reasoning that the pointer becomes invalid when the function returns because the storage, if any, returned by malloc is now inaccessible, so the comparison is invalid. Who knows? Optimization is easier if we don’t have to care about correctness.

Here’s a question  I asked some compiler and standards developers: can the compiler assume “b” is false and delete the whole branch?

int getadata(int b, char *buf, int n){
       int *p; //forget to initialize
       if(b){
           read(0,buf,n);
           *p =0;
       }
       return 1;
}

Since p is uninitialized, the compiler may decide the assignment, which is “undefined behavior” can’t happen, so the whole branch can be assumed away – and this reasoning would apply no matter what else we do inside the branch. So the code that calls “getdata(1,buff, 1000)” over and over will get nothing done and might even itself be “optimized” away.  Imagine:

char *buf = malloc(1000); getdata(1,buf,1000); if(buf[23]== 'x'){ ....}

 

On the basis of the first “optimization”, the compiler may see that the “if” depends on reading uninitialized memory and delete that case too. With a low level of optimization, the compiler may generate those reads and then silently delete on a higher level of analysis – and different C compilers can make different choices. Effectively, programmers have to guess.

Here is a hypothetical case:

char *b,good;
n = read(fd,b,m);
good = b[m-1];// undefined if n < m
if(n == m  )dosomething(good);
else badread(good);//can we delete this case

Right now, code  like this will compile as expected. But that’s only because the compilers do not incorporate knowledge about “read”. Suppose the compiler understands that if n != m, then b[m-1] is uninitialized and deletes the badread case, because otherwise “good” is the result of reading uninitialized memory which “can’t happen”? So this code may work, contingent on the compilers not figuring out what “read” does.

There is right now in the C Standards process an effort to incorporate pointer “provenance” so that compilers are permitted to consider pointers as pairs (provenance, abstract address) and an 80 page proposal that appears to have a lot of support.  You can read some of the ongoing discussion about this proposal in the message archive. One of the interesting things about this proposal, in the current state, is that it doesn’t provide any solution to the malloc issue – but suggests some solution should be found.  Similarly, it doesn’t discuss how mmap can work with the proposal. The proposal text is also ambivalent about how == should work for pointers. Why? Because it’s impossible for compilers to always correctly figure out the provenance of a pointer, however the proposers want the compilers to enforce provenance rules when they can. Programmers are supposed to just figure it out.

 

See also the purpose of C.