Categories
Tag: c standard
Categories
don’t defer
There is a proposal to add “defer” to C. Its biggest example is taken from code that was originally designed to not manage storage at all, but to run once and exit – delegating all the cleanup to exit. The proposal authors show a complex solution to make the code free storage and then show how it can be “simplified” using defer. But it is trivial to centralize cleanup in one function, no new features needed. If I was developing this code for real, I’d take the next step and make it single exit. Here is is with a simple function to free all storage on exit.
struct plugins {
char *pluginsdir;
char *outpluginsdirphp;
char *outpluginsdirmisc;
char *dirpath;
char *outdirphp;
char *outdirmisc;
int n;
struct dirent **namelist;
};
void freeall(struct plugins *x)
{
if (x->pluginsdir)
free(x->pluginsdir);
if (x->outpluginsdirphp)
free(x->outpluginsdirphp);
if (x->outpluginsdirmisc)
free(x->outpluginsdirmisc);
if (x->dirpath)
free(x->dirpath);
if (x->outdirphp)
free(x->outdirphp);
if (x->outdirmisc)
free(x->outdirmisc);
for (int i = 0; i < x->n; i++) {
free(x->namelist[i]);
}
}
h_err *h_build_plugins(const char *rootdir, h_build_outfiles outfiles,
const h_conf * conf)
{
struct plugins x = { 0, };
x.pluginsdir = h_util_path_join(rootdir, H_FILE_PLUGINS);
if (pluginsdir == NULL)
return h_err_create(H_ERR_ALLOC, NULL);
x.outpluginsdirphp = h_util_path_join(rootdir,
H_FILE_OUTPUT "/" H_FILE_OUT_META
"/" H_FILE_OUT_PHP);
if (outpluginsdirphp == NULL) {
freeall(&x);
return h_err_create(H_ERR_ALLOC, NULL);
}
x.outpluginsdirmisc = h_util_path_join(rootdir,
H_FILE_OUTPUT "/" H_FILE_OUT_META
"/" H_FILE_OUT_MISC);
if (x.outpluginsdirmisc == NULL) {
freeall(&x);
return h_err_create(H_ERR_ALLOC, NULL);
}
//Check status of rootdir/plugins, returning if it doesn’t exist
{
int err = h_util_file_err(x.pluginsdir);
if (err == ENOENT) {
freeall(&x);
return NULL;
}
if (err && err != EEXIST) {
freeall(&x);
return h_err_from_errno(err, x.pluginsdir);
}
}
//Create dirs if they don’t exist
if (mkdir(x.outpluginsdirphp, 0777) == -1 && errno != EEXIST) {
freeall(&x);
return h_err_from_errno(errno, x.outpluginsdirphp);
}
if (mkdir(outpluginsdirmisc, 0777) == -1 && errno != EEXIST) {
freeall(&x);
return h_err_from_errno(errno, outpluginsdirmisc);
}
//Loop through plugins, building them
x.n = scandir(x.pluginsdir, &x.namelist, NULL, alphasort);
if (n == -1) {
freeall(&x);
return h_err_from_errno(errno, x.namelist);
}
for (int i = 0; i < n; ++i) {
struct dirent *ent = namelist[i];
if (ent->d_name[0] == '.') {
continue;
}
x.dirpath = h_util_path_join(x.pluginsdir, ent->d_name);
if (dirpath == NULL) {
freeall(&x);
return h_err_create(H_ERR_ALLOC, NULL);
}
x.outdirphp = h_util_path_join(outpluginsdirphp, ent->d_name);
if (x.outdirphp == NULL) {
freeall(&x);
return h_err_create(H_ERR_ALLOC, NULL);
}
x.outdirmisc =
h_util_path_join(x.outpluginsdirmisc, ent->d_name);
if (x.outdirmisc == NULL) {
freeall(&x);
return h_err_create(H_ERR_ALLOC, NULL);
}
h_err *err;
err =
build_plugin(dirpath, outdirphp, outdirmisc, outfiles,
conf);
if (err) {
freeall(&x);
return err;
}
}
freeall(&x);
return NULL;
}
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:
- 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.
- 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.
- 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
PermissiblePossible 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.
This 1998 note by Dennis Ritchie from comp.lang.c (and also here ) is very current since the concept of noalias has definitely crept back into the standard. I have reproduced it verbatim, but lightly formatted for readability. For further reading try Linus Torvalds (pre-nice ) note, John Regehr’s paper on alias and this proposal for the C 2x standard.
noalias comments to X3J11
d…@alice.uucp
Mar 20, 1988, 2:37:58 AM
Reproduced below is the long essay I sent as an official comment to X3J11. It is in two parts; the first points out some problems in the current definition of `const,’ and the second is a diatribe about `noalias.’ By way of introduction, the important thing about `const’ is that the current wording says, in section 3.3.4, that a pointer to a const-qualified object may be cast to a pointer to the plain object, but “If an attempt is made to modify the pointed-to object by means of the converted pointer, the behavior is undefined.” Because function prototypes tend to convert your pointers to const-qualified pointers, difficulties arise.In discussion with various X3J11 members, I learned that this section is now regarded as an inadvertant error, and no one thinks that it will last in its current form. Nevertheless, it seemed wisest to keep my comments in their original strong form. The intentions of the committee are irrelevant; only their document matters.
The second part of the essay is about noalias as such. It seems likely that even the intentions of the committee on this subject are confused.
Here’s the jeremiad.
Dennis Ritchie
research!dmr
d…@research.att.com
———-
This is an essay on why I do not like X3J11 type qualifiers. It is my own opinion; I am not speaking for AT&T.
Let me begin by saying that I’m not convinced that even the pre-December qualifiers (`const’ and `volatile’) carry their weight; I suspect that what they add to the cost of learning and using the language is not repaid in greater expressiveness. `Volatile,’ in particular, is a frill for esoteric applications, and much better expressed by other means. Its chief virtue is that nearly everyone can forget about it. `Const’ is simultaneously more useful and more obtrusive; you can’t avoid learning about it, because of its presence in the library interface. Nevertheless, I don’t argue for the extirpation of qualifiers, if only because it is too late.
The fundamental problem is that it is not possible to write real programs using the X3J11 definition of C. The committee has created an unreal language that no one can or will actually use. While the problems of `const’ may owe to careless drafting of the specification, `noalias’ is an altogether mistaken notion, and must not survive.
1. The qualifiers create an inconsistent language
A substantial fraction of the library cannot be expressed in the proposed language.
One of the simplest routines,
char *strchr(const noalias char *s, int c);
can return its first parameter. This first parameter must be declared with `const noalias;’ otherwise, it would be illegal (by the constraints on assignment, 3.3.16.1) to pass the address of a const or noalias object. That is, the type qualifiers in the prototype are not merely an optional pleasantry of the interface; they are required, if one is to pass some kinds of data to this or most other library routines.
Unfortunately, there is no way in X3J11’s language for strchr to return the value it promises to, because of the semantics of return (3.6.6.4) and casts (3.3.4). Whether the stripping of the const and noalias qualifiers is done by cast inside strchr, or implicitly by its return statement, strchr returns a pointer that (because of `const’) cannot be stored through, and (because of `noalias’) cannot even be dereferenced; by the rules, it is useless. (Incidentally, I think this observation was made by Tom Plum several years ago; it’s disconcerting that the inconsistency remains.)
Although the plain words of the Standard deny it, plastering the appropriate `non-const’ cast on an expression to silence a compiler is sometimes safe, because the most probable implementation of `const’ objects will allow them to be read through any access path, and will diagnose attempts to change them by generating an access violation fault at run time. That is, in common implementations, adding or taking away the `const’ qualifier of a pointer can never create any bugs not implicit in the rule `do not modify a genuine const object through any access path.’
Nevertheless, I must emphasize that this is NOT the rule that X3J11 has written, and that its library is inconsistent with its language. Someone writing an interpreter
using X3J11/88-001 is perfectly at liberty to (indeed, is advised to) carry with each pointer a `modifiable’ bit, that (following 3.3.4) remains off when a pointer to a const-
qualified object is cast into a plain pointer. This implementation will prevent many of the real uses of strchr, for example. I’m thinking of things like
if (p = strchr(q, ‘/’))
*p = ‘ ‘;
which are common and innocuous in C, but undefined by X3J11’s language.
A related observation is that string literals are not of type `array of const char.’ Indeed, the Rationale (88-004 version) says, `However, string literals do not have [this type], in order to avoid the problems of pointer type checking, particularly with library functions….’ Should this bald statement be considered anything other than an admission that X3J11’s rules are screwy? It is ludicrous that the committee introduces the `const’ qualifier, and also makes strings unwritable, yet is unable to connect the two conceptions.
2. Noalias is an abomination
`Noalias’ is much more dangerous; the committee is planting timebombs that are sure to explode in people’s faces. Assigning an ordinary pointer to a pointer to a `noalias’ object is a license for the compiler to undertake aggressive optimizations that are completely legal by the committee’s rules, but make hash of apparently safe programs. Again, the problem is most visible in the library; parameters declared `noalias type *’ are especially problematical.
In order to write such a library routine using the new parameter declarations, it is in practice necessary to violate 3.3.4: `A pointer to a noalias-qualified type … may be converted to … the non-noalias-qualified type. If the pointed to object is referred to by means of the converted pointer, the behavior is undefined.’ Thus, the problem that occurs with `const’ is now much worse; there are no interesting and legal uses of strchr.
How do you code a routine whose prototype specifies a noalias pointer? If you fail to violate 3.3.4, but instead try to rewrite the declarations of temporary variables to make them agree in type with parameters, it becomes hard to be sure that the routine works. Consider the specification of strtok:
char *strtok(noalias char *s1, noalias const char *s2);
It retains a static pointer to its writable, `noalias’ first argument. Can you be sure that this routine can be made safe under the rules? I have studied it, and the answer is conditionally yes, provided one accepts certain parts of the
Standard as gospel (for example that `noalias’ handles will
NOT be synchronized at certain times) while ignoring other parts. It is a very dodgy thing. For other routines, it is certain that complete rewriting is necessary: qsort, for example, is full of pointers that rove the argument array and change it here and there. If these local pointers are qualified with `noalias,’ they may all be pointing to different virtual copies of parts of the array; in any event, the argument itself may have a virtual object that might be completely untouched by the attempt to sort it.
The `noalias’ rules have the assignment and cast restrictions backwards. Assigning a plain pointer to a const- qualified pointer (pc = p) is well-defined by the rules and is safe, in that it restricts what you can do with pc. The other way around (p = pc) is forbidden, presumably because it creates a writable access path to an unwritable object. With `noalias,’ the rules are the same (pna = p is OK, p = pna is forbidden), but the realistic safety requirements are completely different. Both of these assignments are equally suspicious, in that both create two access paths to an object, one manifestation of which might be virtual.
Here is another way of observing the asymmetry: the presence of `const type *’ in a parameter list is a useful piece of interface information, but `noalias type *’ most assuredly is not. Given the declaration
memcpy(noalias void *s1, const noalias void *s2, size_t n);
what information can one glean from it? Some committee members apparently believe that it conveys either to the reader or to the compiler that the routine is safe, provided that the strings do not overlap. They are mistaken. Perhaps the committee’s intent is not reflected in the current words of the Standard, but I can find nothing there that justifies their belief. The rules (page 65, lines 19-20) specify `all objects accessible by these [noalias] lvalues,’ which is the entirety of both array arguments.
More generally, suppose I see a prototype
char *magicfunction(noalias char *, noalias char *);
Is there anything at all I can conclude about the requirements of magic function? Is there anything at all I can conclude about things it promises to do or not to do? All I learn from the Rationale (page 52) is that such a routine enjoins me from letting the arguments overlap, but this is at variance with the Standard, which gives a stronger injunction.
Within the function itself, things are equally bad. A `const type *’ parameter, though it presents problems for strchr and other routines, does usefully constrain the function: it’s not allowed to store through the pointer. However, within a function with a `noalias type *’ parameter, nothing is gained except bizarre restrictions: it can’t cast the parameter to a plain pointer, and it can’t assign the parameter to another noalias pointer without creating unwanted handles and potential virtual objects. The interface MUST say noalias, or at any rate DOES say noalias, so the author of the routine has all the grotesque inventions of 3.5.3 (handles, virtual objects) rubbed in his face, like or not. The utter wrongness of `noalias’ is that the information it seeks to convey is not a property of an object at all. `Const,’ for all its technical faults, is at least a genuine property of objects; `noalias’ is not, and the committee’s confused attempt to improve optimization by pinning a new qualifier on objects spoils the language. `Noalias’ is a bogus invention that is not necessary, and not in any case sufficient for its apparent purpose.
Earlier languages flirted with gizmos intended to help optimization, and generally abandoned them. The original Fortran, for example, had a FREQUENCY statement that didn’t help much, confused people, and was dropped. PL/1 had
`normal/abnormal’ and `uses/sets’ attributes that suffered a similar fate. Today, these are generally looked on as adolescent experiments.
On the other hand, the insufficiency of `noalias’ is suggested by Cray’s Fortran compiler, which has 20 separate keywords that control various details of optimization. The are specified by an equivalent of #pragma, and thus, despite their oddness, can be ignored when trying to understand the meaning of a program. Perhaps there is some reason to provide a mechanism for asserting, in a particular patch of code, that the compiler is free to make optimistic assumptions about the kinds of aliasing that can occur. I don’t know any acceptable way of changing the language specification to express the possibility of this kind of optimization, and I don’t know how much performance improvement is likely to result. I would encourage compiler-writers to experiment with extensions, by #pragma or otherwise, to see what ideas and improvements they can come up with, but I am certain that nothing resembling the noalias proposal should be in the Standard.
3. The cost of inconsistency
K&R C has one important internal contradiction (variadic functions are forbidden, yet printf exists) and
one important divergence between rule and reality (common vs. ref/def external data definitions). These contradictions have been an embarrassment to me throughout the years, and resolving them was high on X3J11’s agenda. X3J11 did manage to come up with an adequate, if awkward, solution to the first problem. Their solution to the second was the same as mine (make a rule, then issue a blanket license to violate it).
I’m aware that there are distinctions to be made between `conforming’ and `strictly conforming’ programs. Although the X3J11 rules for qualifiers are inconsistent, and therefore most nominally X3J11 compilers will ignore, or
only warn about, casts and assignments that X3J11 says are undefined, people will somehow survive. C has, after all, survived the vararg and the extern problems.
Nevertheless, I advise strongly against sanctifying a language specification that no one can possibly embody in a useful compiler. This advice is based on bitter experience.
4. What to do?
Noalias must go. This is non-negotiable.
It must not be reworded, reformulated or reinvented. The draft’s description is badly flawed, but that is not the problem. The concept is wrong from start to finish. It negates every brave promise X3J11 ever made about codifying existing practices, preserving the existing body of code, and keeping (dare I say it?) `the spirit of C.’
Const has two virtues: putting things in read-only memory, and expressing interface restrictions. For example, saying
char *strchr(const char *s, int c);
is a reasonable way of expressing that the routine cannot change the object referred to by its first argument. I think that minor changes in wording preserve the virtues, yet eliminate the contradictions in the current scheme.
1) Reword page 47, lines 3-5 of 3.3.4 (Cast operators), to remove the undefinedness of modifying pointed-to objects, or remove these lines altogether (since casting non-qualified to qualified isn’t discussed explicitly either.)
2) Rewrite the constraint on page 54, lines 14-15, to say that pointers may be assigned without taking qualifiers into account.
3) Preserve all current constraints against modifying non-modifiable lvalues, that is things of manifestlyconst-qualified type.
4) String literals have type `const char []’.
5) Add a constraint (or discussion or example) to assignment that makes clear the illegality of assigning to an object whose actual type is const-qualified, no matter what access path is used. There is a manifest constraint that is easy to check (left side is not const-
qualified), but also a non-checkable constraint (left side is not secretly const-qualified). The effect should be that converting between pointers to const- qualified and plain objects is legal and well-defined; avoiding assignment through pointers that derive ultimately from `const’ objects is the programmer’s responsibility.
These rules give up a certain amount of checking, but they save the consistency of the language.
Note: these were sent to WG14 as official proposals. See also a longer paper, something on alias and Torvalds remarks and Regehr’s paper.
6.12 Proposal to clarify undefined behavior range for implementations [N 2278]
6.13 Proposal to make aliasing consistent [N 2279]
6.14 Proposal to limit optimization to C semantics [N 2280]
I’m going to write up my experiences at the Pittsburgh meeting when I have time, but it was informative and kind of depressing. Pittsburgh was nice though, and I had a fun visit at U. Pitt and with my old friend from grad school.
Proposal on Alias
Rationale:
The limitation of lvalue access by types was not properly completed or clarified in the Standard. Neither temporary change of effective type for “type punning” or type assignment/erasure which is necessary for allocators were clearly specified. The exception for character pointers was added when it was realized that the Standard would otherwise completely prohibit implementation of memcpy. It still appears to be impossible to write an efficient “memcpy” without optimizer intervention or to write a memory allocator at all in conforming C with the existing Standard. For example: consider an allocator of device local memory in a GPU and how freed objects of one type could be combined or divided and reassigned a new effective type when allocated again – the Standard appears to consider malloc/free as primitives not C implementable library functions. Furthermore, common operations in longstanding common practice, such as using an int type to compute a checksum on a message structure may be forbidden.
Part of the lack of clarity comes from an apparent contradiction in the Standard. Section 6.3.2.3.7 permits a pointer to an object type to be converted to a pointer to a different object type and 6.3.2.1 permits any pointer to be converted to a void pointer type and then converted to any other type but the current language in 6.5.7 seems to imply that dereferencing those pointers may be undefined behavior even if the pointers are properly aligned – which would make the conversion useless at best.
This change is not a complete cure. A memory allocator needs to be able to consolidate or divide objects and the Standard provides no mechanism for that process other than customary practice. Access to the underlying binary representation of a type is a fundamental capability of C programming. There are less complex routes towards helping compilers identify absence of aliasing.
Proposed change
7 An object shall have its stored value accessed only by an lvalue expression that has one of the following types:88)
— a type compatible with the effective type of the object,
— a qualified version of a type compatible with the effective type of the object,
— a type that is the signed or unsigned type corresponding to the effective type of the object, — a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object,
— an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union), or
— a character type
— a properly aligned pointer of any object type that has been converted from a valid pointer of the effective object type.
Proposal on Undefined Behavior.
Rationale:
This Standard’s treatment of “undefined behavior”, like the rest of the Standard, relies on an expectation that implementations are cooperating with the programmer and respecting the C abstract semantics. For example, overflow is undefined behavior, yet 5.1.2.3 Example 6, the Standard limits reordering certain expressions when the implementation produces traps on arithmetic overflows. The purpose of “undefined behavior” is to relieve the translator from the burden of hiding implementation differences and from making safety checks that are the responsibility of the C programmer. Unfortunately, some implementations are interpreting undefined behavior to license arbitrary transformations that violate the abstract semantics.
As an example, some implementations will roll-over on arithmetic overflow but at the same time, delete programmer checks for roll-over as an “optimization” because overflow is “undefined behavior”. The wording of the Standard does not support this interpretation: “possible undefined behavior ranges from”
- ignoring the situation completely with unpredictable results” – which case the underlying processor architecture might increment in modular arithmetic or trap (which may or may not be handled) or do something else, but the translation “ignore[s] the situation” and produces code without making use of knowledge of any undefined behavior;
- “to behaving during translation in a documented manner characteristic of the environment“;
- ” to terminating a translation or execution (with the issuance of a diagnostic message)“.
This range is very wide and provides implementations with latitude for optimization but
it does not support conforming implementations that do not ignore the situation but neither behave in a documented manner characteristic of the environment nor terminate the translation and instead produce essentially arbitrary translation..
Arbitrary code translation justified by undefined behavior makes C programming a hazardous endeavor where the implementation is full of unpleasant surprises. Additionally, the more radical interpretations of undefined behavior are causing a fork in the language. Currently, the Linux Operating System requires its translators to respect flags to turn off a number of “optimizations” that are at least partially based on detecting undefined behavior. The existence of these flags and their wide use indicates both that a great deal of existing practice depends on disabling undefined behavior based “optimization” and that accommodating a more modest use of UB directed translation is acceptable to developers of implementations.
It has been argued that permitting implementations to violate the constraints of the abstract machine in the presence of undefined behavior is necessary for high levels of optimization, but there are no published studies validating that claim, and, indeed, the Linux kernel code is highly optimized despite its extensive use of the translator options described in the preceding paragraph. Limiting UB directed “optimizations” will incentivize implementations to optimize within the C semantics and make C more reliable without requiring the major rewrite of the Standard suggested in https://blog.regehr.org/archives/1180 (which motivated this proposal).
Proposed change.
undefined behavior
1 behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements. Note that the use of a nonportable or erroneous program construct or use of erroneous data should not affect the translation or implementation of conforming constructs in the program or the uses of acceptable data.
2 NOTE Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message). This range is exhaustive, not inclusive. Conforming implementations cannot violate semantics of the C abstract machine in conforming program constructs using acceptable data due to the presence of undefined behavior somewhere else in the program. Use of a nonportable or erroneous program construct should only affect the translation of that construct. By 5.1.2.3.4 “An actual implementation need not evaluate part of an expression if it can deduce that its value is not used “ but merely deducing that undefined behavior follows from use of a value does not allow the implementation to assume that the value is not used.
3 EXAMPLE An example of undefined behavior is the behavior on integer overflow.
4 EXAMPLE Program constructs that check to see if an integer value has overflowed or an array index is past the limit of the array cannot be deleted or otherwise ignored during translation unless the overflow or out of bounds index is actually impossible in the implementation. 5.1.2.3 applies to conforming program constructs even if other program constructs produce undefined behavior.
5 EXAMPLE If the value of the right operand of a shift is negative, the result is undefined but a conforming implementation cannot deduce that the value of a conforming expression is not negative merely from its use as the right operand of a shift instruction.
6 EXAMPLE Code that checks to see if a pointer value is null cannot be omitted during translation solely on the basis that the pointer is dereferenced before the check and that earlier dereference would produce undefined behavior if the pointer value was null.
7 NOTE Implementation of signed integer addition in an environment that generated overflow traps on overflow follows the specification as would implementations where the addition simply rolled over the integer value. However injecting for example, an infinite loop that would be software triggered on overflow would not fit into the range of possible undefined behaviors because it would not be “characteristic of the environment” even if documented (as required).
Proposal on Optimization
Rationale:
It is specified in the Standard that “optimization” in a conforming implementation must produce behavior that conforms to the semantics of the language. Advances in optimization technology in translators have lead to the development of multi-pass translators in which semantics of programs can be modified – possibly unintentionally – without some care to preserve semantics over optimization passes. This change calls for conforming implementations to take that care.
Proposed change
1 The semantic descriptions in this International Standard describe the behavior of an
abstract machine in which issues of optimization are irrelevant. A conforming implementation may not change semantics of a program as an “optimization” except as described in 5.1.2.3.4
One of the common defenses of the abuse of “undefined behavior” by C compilers, and the stupid aliasing rules in the standard is that those things are necessary for optimizations, like using vector operations. Here’s an example of where gcc ignores the standard and does what the C language semantics require while taking advantage of Intel SIMD instructions. The C code is an example of a common technique in network code.
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
struct message { int code; int value; float data[20]; int checkval; };
int checksum(struct message *m){
int i, *p = (int *)m;
int lim = sizeof(struct message) / sizeof i;
int c = 0;
for (i=0 ; i < lim; i++) { c ^= *(p+i); }
return c;
}
int main (int argc, char **argv)
{
struct message m;
int v;
fread((char *)&m, sizeof(char), sizeof(m), stdin);
v = checksum(&m);
printf("Checksum was %d\n",v);
}
The translation.
checksum: movdquxmm0, XMMWORDPTR [rdi+32] movdquxmm2, XMMWORDPTR [rdi+48] movdquxmm1, XMMWORDPTR [rdi] movdquxmm3, XMMWORDPTR [rdi+16] pxorxmm0, xmm2 movdquxmm4, XMMWORDPTR [rdi+64] moveax, DWORDPTR [rdi+80] pxorxmm1, xmm3 xoreax, DWORDPTR [rdi+84] xoreax, DWORDPTR [rdi+88] pxorxmm0, xmm1 movedx, eax pxorxmm0, xmm4 movdqaxmm1, xmm0 psrldqxmm1, 8 pxorxmm0, xmm1 movdqaxmm1, xmm0 psrldqxmm1, 4 pxorxmm0, xmm1 movdeax, xmm0 xoreax, edx ret
See the godbolt page
See also Dennis Ritchie on aliasing, PLOS article, pointer alias in C and remarks on the purpose of C.
From: LKML
|
On Mon, Jun 4, 2018 at 4:31 AM Rafael J. Wysocki <rafael@kernel.org> wrote:
>
> device property: Get rid of union aliasing
Honestly, this looks questionable to me.
I'm not talking about the changes themselves - I can live with them.
But the _rationale_ is pure and utter garbage, and dangerously so.
The fact is, using a union to do type punning is the traditional AND
STANDARD way to do type punning in gcc. In fact, it is the
*documented* way to do it for gcc, when you are a f*cking moron and
use "-fstrict-aliasing" and need to undo the braindamage that that
piece of garbage C standard imposes.
So the commit message that talks about how horrible union aliasing is
is pushing a story that is simply wrong. Using the standard to push it
- the same standard that came up with the completely mis-guided
aliasing rules - is not a valid argument.
Andy, what is the background for trying to push this idiocy? Don't
tell me "the C standard is unclear". The C standard is _clearly_ bogus
shit (see above on strict aliasing rules), and when it is bogus
garbage, it needs to be explicitly ignored, and it needs per-compiler
workarounds for braindamage. The exact same situation is true when
there is some lack of clarity.
This is why we use -fwrapv, -fno-strict-aliasing etc. The standard
simply is not *important*, when it is in direct conflict with reality
and reliable code generation.
The *fact* is that gcc documents type punning through unions as the
"right way". You may disagree with that, but putting some theoretical
standards language over the *explicit* and long-time documentation of
the main compiler we use is pure and utter bullshit.
I've said this before, and I'll say it again: a standards paper is
just so much toilet paper when it conflicts with reality. It has
absolutely _zero_ relevance. In fact, I'll take real toilet paper over
standards any day, because at least that way I won't have splinters
and ink up my arse.
So I want to see actual real arguments, not "the standard is unclear".
When documented gcc behavior says one thing, and the standard might be
unclear, we really don't care one whit about the lack of clarity in
some standard.
So what's the _real_ reason for avoiding union aliasing?
There are competent people on standards bodies. But they aren't
_always_ competent, and the translation of intent to English isn't
always perfect either. So standards are not some kind of holy book
that has to be revered. Standards too need to be questioned.
Linus
C STANDARD UNDEFINED BEHAVIOR VERSUS WITTGENSTEIN
1. DEPRESSING AND FAINTLY TERRIFYING
Chris Lattner, the architect of the Clang/LLVM C compiler explained the effects of the C standard’s “undefined behavior”(UB):
UB is an inseperable part of C programming, […] this is a depressing and faintly terrifying thing. The tooling built around the C family of languages helps make the situation less bad, but it is still pretty bad. The only solution is to move to new programming languages that dont inherit the problem of C. Im a fan of Swift, but there are others.[4]
Also from Lattner[5]:
[…] many seemingly reasonable things in C actually have undefined behavior, and this is a common source of bugs in programs. Beyond that, any undefined behavior in C gives license to the implementation (the compiler and runtime) to produce code that formats your hard drive, does completely unexpected things, or worse
Undefined behavior is defined by the C Standard as “behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements.” You might think that having the architect of a major compiler point out that the result of your standard is “depressing and faintly terrifying” and curable only by switching to another programming language would cause some consternation at the standards committee, but no. The WG14 C Standards organization appears to be unconcerned despite the warnings of compiler developers and the objections of the most prominent C developers and academics.
- Dennis Ritchie called an early version of UB “a license for the compiler to undertake aggressive optimizations that are completely legal by the committee’s rules, but make hash of apparently safe programs“[7].
- One of the most important developers of cryptography code wrote: “Pretty much every real-world C program is “undefined” according to the C “standard”, and new compiler “optimizations” often produce new security holes in the resulting object code” [1].
- In summary that leans over backwards to find excuses for UB, John Regehr wrote: One suspects that the C standard body simply got used to throwing behaviors into the undefined bucket and got a little carried away. Actually, since the C99 standard lists 191 different kinds of undefined behavior, its fair to say they got a lot carried away.[6].
- And Linus Torvalds wrote: The fact is, undefined compiler behavior is never a good idea. Not for serious projects. [8].
2. SLOW MOVING TRAIN WRECK
Discussion of this issue or of practitioner objections in WG14 records is hard to find. What we do find are proposals to greatly expand the realm of undefined behavior[3]. And there is no doubt that the standards embrace of UB has created a slow motion train wreck.
- A security failure in the Linux kernel was generated by the compiler silently removing a check for a null pointer several lines below a UB reference to a null pointer.
- Code that checks for overflow in a signed variable can be silently “optimized” to remove the check because overflow of integer variables is UB.
- The C standard committee had to hack up its own standard with a special case when it realized it had made it impossible to write “memcpy” in C[2].
- Under pressure from, particularly Linux, the GCC compiler has introduced a number of flags to turn off UB behavior – essentially forking the language.
As Lattner wrote, C code that appears reasonable, that causes no compiler errors or warning and that conforms to wide practice can be arbitrarily changed once the compiler believes it has detected UB somewhere in the same neighborhood. But this is a bizarre interpretation of UB and it’s remarkable that the WG14 C Standards Committee has not made efforts to ban such an interpretation. Originally, UB is simply there to mark the borders of what C specifies: C does not specify what happens when the result of integer arithmetic can’t fit in a signed int – because the language designers wanted to permit compilers to leave off expensive checks. But currently compiler developers claim they can,for example, assume that UB never happens and, for example, delete programmer checks for overflow. The rationale for this perverse UB is that it opens up compiler optimizations that would be otherwise impossible. This claim is not supported by any actual studies. Even for the kinds of trivial micro-benchmarks that are often cited, it looks like absolutely nobody is doing any tests. For example, an unsigned and signed variable in a C “for loop” have no performance difference despite the advantage that the undefined nature of signed overflow supposedly provides the compiler. Even though UB has been around since Ritchie first objected to it, it has grown in scope as the C standard has grown in scope and complexity. Here’s a good example from C11 in some typically opaque language :
(6.5 Para7) An object shall have its stored value accessed only by an lvalue expression that has one of the following types: a type compatible with the effective type of the object, a qualified version of a type compatible with the effective type of the object, a type that is the signed or unsigned type corresponding to the effective type of the object, a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object, an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union), or a character type
I had to read the footnote to to have any idea at all what is being “specified” by this murk
” The intent of this list is to specify those circumstances in which an object may or may not be aliased.“
That last sentence in 6.5 Para7 is a hack added when the Committee realized it had made it impossible to write memcpy in C – you have to pretend that memcpy copies character by character or is written in some other language in order to make it consistent. And you also need footnote 75 (“Allocated objects have no declared type.”).
No wonder that Linus Torvalds was not impressed.
The idiotic C alias rules aren’t even worth discussing. They were a mistake. The kernel doesn’t use some “C dialect pretty far from standard C”. Yeah, let’s just say that the original C designers were better at their job than a gaggle of standards people who were making bad crap up to make some Fortran-style programs go faster. They don’t speed up normal code either, they just introduce undefined behavior in a lot of code. And deleting NULL pointer checks because somebody made a mistake, and then turning that small mistake into a real and exploitable security hole? Not so smart either. [8]
Brian Kernighan didn’t like it either, back when this design error was part of Pascal and not part of C [10]:
2.6. There is no escape
There is no way to override the type mechanism when necessary, nothing analogous to the “cast” mechanism in C. This means that it is not possible to write programs like storage allocators or I/O systems in Pascal, because there is no way to talk about the type of object that they return, and no way to force such objects into an arbitrary type for another use.
Yes, according to the C Standard, malloc cannot be written in C. In fact, the example of malloc in K&R 2cd edition is not written in C according to the standard under current interpretations. Instead there is special treatment for malloc as a mystery library function so it can return pointers to data of “no declared type” even though malloc is defined to return pointers to void. What if you want to write an allocator, not called malloc/free? I don’t know, perhaps you are supposed to use Rust or Swift. What about mmap/mfree ? Nope. It’s hard to imagine even how those functions can be used in Standard C. Reference I/O or device registers? Nope again. You have Pseudo-Pascal and you better learn to like it. Want to treat a packet as an array of ints so you can checksum it? Nope. According to proponents of the C Standard the correct way to do this is to use memcpy to copy the packet to an integer array, compute the value, copy back, and then hope the optimizer figures it out and removes the copying because there is, you guessed it, another special exception for memcpy used to copy data to memory of “no declared type”.
(6.5 6) […]. If a value is copied into an object having no declared type using memcpy or memmove, or is copied as an array of character type, then the effective type of the modified object for that access and for subsequent accesses that do not modify the value is the effective type of the object from which the value is copied, if it has one. For all other accesses to an object having no declared type, the effective type of the object is simply the type of the lvalue used for the access.
So the sequence looks like this: (1)Allocate a packet sized block of memory using malloc – this has “no declared type”; (2) Copy the packet to this memory using memcpy; (3) The new block of memory has the effective type of the packet structure; (4) Then modify the new block of memory using an int pointer; (5) And magically, the memory block is now an array of ints”. Doesn’t step (4) violate the effective type rules in the very next paragraph? Yes, but pretend otherwise. Basically, memcpy/memmove and malloc plus character arrays are giant hacks to the type system that kind of make things sort-of work. To make matters worse, another part of the standard provides rules for casting pointer types which, according to this part, provide a Standards Conformant way for changing the type of a pointer, but at the same time making it undefined behavior to de-reference the pointer. Section 6.3.2.3.7 permits a pointer to an object type to be converted to a pointer to a different object type and 6.3.2.1 permits any pointer to be converted to a void pointer type and then converted to any other type but the current language in 6.5.7 seems to imply that dereferencing those pointers may be undefined behavior even if the pointers are properly aligned – which would make the conversion useless at best.
3. MORE IS BETTER, NO ?
There’s a unfortunate dynamic in the WG14 process in which the language definition expands in scope while shrinking in clarity. This dynamic comes from a lack of appreciation for the frugal semantics of the C language. In software, as in much other forms of engineering, only the most brilliant or lucky designers manage to leave the right things out. In particular, C and UNIX were so successful as much because of what was left out as because of what was put in. The injunction of Wittgenstein[9] is almost a cliche in programming design, but it is on point: What can be said at all can be said clearly; and whereof one cannot speak thereof one must be silent. The approach of the WG14 committee has appears to have been based on the misconception that this economy in specification was a problem to be solved by expanding the scope of things covered by the standard. The alias rules above are a good example. C had no aliasing rules because it gained an advantage by permitting programmers to use pointers flexibly. Lack of aliasing rules could have been argued as too costly in terms of both programmer errors and forsaken compiler optimizations, but that could have been addressed by refining the restrict keyword or providing some other opt-in semantics instead of trying to back up a half-baked notion of strict typing into C.
As another example, C did not define anything about concurrent tasks and parallelism, even though the designers of C intended to use it with interrupt handlers and processes and multi-processors, and did so with great success. By omitting the semantics of concurrent and parallel computation, the C design licensed programmers to develop many different solutions outside the framework of the language. Interrupt handlers, POSIX processes and threads, coroutines, SMP, the event models of current generation web servers, GPUs and vector processing: the minimalist design of the language meant that it did not get in the way of system designers and programmers. But the WG14 committee is now attempting to grow the language to cover the semantics of threaded code. Necessarily, this specification will have imprecision, opening the way to even more UB and it looks like it will tie the language to an awkward model of synchronization (via mutexes) and import into the language information about processor design that may well be obsolete in a few years.
The situation is only going to get worse as link time optimization becomes common in compilers – extending the ability of the compilers to find UB across separate compilation borders. Either C will fade away as Lattner and many others hope, the standard will change, or there will be a successful fork to produce a more precise and flexible standard.
REFERENCES
[1] D.J. Bernstein. boringcc., https://groups.google.com/forum/m/#!msg/
boring-crypto/48qa1kWignU/o8GGp2K1DAAJ.
[2] Derek Jones. How indeterminate is an indeterminate value. http://shape-ofcode.coding-guidelines.com/2017/06/18/how-indeterminate-isan-indeterminate-value/.
[3] David Keaton. Implicit Undefined Behavior in C. http://www.open-std.org/ jtc1/sc22/wg14/www/docs/n2248.pdf.
[4] Chris Lattner. GEP with a null pointer base. http://lists.llvm.org/pipermail/ llvm-dev/2017-July/115149.html. 2016.
[5] Chris Lattner. What every C programmers should know about undefined behavior 1/3. http://blog.llvm.org/2011/05/what- every- c- programmershould-know.html.
[6] John Regehr. A Guide to Undefined Behavior in C and C++, Part 1. https:// blog.regehr.org/archives/213.
[7] Dennis Ritchie. noalias comments to X3J11. http://www.lysator.liu.se/ c/dmr-on-noalias.html.
[8] Linus Torvalds. Re: [isocpp-parallel] Proposal for a new memory order. https: //gcc.gnu.org/ml/gcc/2016-02/msg00381.html.
[9] L. Wittgenstein and C.K. Ogden. Tractatus Logico-philosophicus. International library of psychology, philosophy, and scientific method. Routledge, 1990. ISBN: 9780415051866. URL: https://books.google.com/books?id=TE0nCMfRz4C.
[10] Brian Kernighan, Why Pascal is not my favorite language, Bell Labs, 1981, http://www.lysator.liu.se/c/bwk-on-pascal.html
AUSTIN TEXAS. E-mail address: victor.yodaiken@gmail.com
[gview file=”https://www.yodaiken.com/wp-content/uploads/2018/05/ub-1.pdf”]
The Kafkaesque interaction of the C standard and the main open source C compilers was concisely outlined by one of the main LLVM authors back in 2011:
“knowing that
INT_MAX+1is undefined allows optimizingX+1 > Xto “true”. Knowing the multiplication “cannot” overflow (because doing so would be undefined) allows optimizingX*2/2to X ( Chris Lattner)
The C standard defines signed integer types to be fixed length chunks of binary data in either 1s or 2s complement format so x+1 > x is not a theorem and neither is x*2/2= x. Those are elementary mathematical facts – facts that make some kinds of optimizations harder. Instead of trying to work with that reality, C compiler developers have chosen to use a loophole in the C Standard to insist that they can transform code using false theorems. Both the default versions of the GCC and clang compilers that come with current Ubuntu Linux compile the following program so that it works differently depending on optimizations level.
for (i = 0; i < i + 1; i++) {
if (i == INT_MAX) { flag = 1; }
if (flag > 0) {printf("%d |", i);flag++; }
if (flag > 5) { putchar('\n'); exit(0);}
}
exit(0);When compiled without optimization, there is no output. When compiled with optimization output is:
2147483647 |-2147483648 |-2147483647 |-2147483646 |-2147483645 |
Deducing that i < i + 1 is always true, the “optimizer” omits the test and then produces code that calculates it was wrong. The compiler is deducing that it won’t produce the executable code that the compiler produces! Nice. According to the C standard, correct code would have used unsigned integers for the comparison because integer overflow is “undefined behavior” even though using signed integers infor loops is ubiquitous in C programming. The curious thing here is that the compilers don’t warn, complain or reject the signed comparison, instead they generate a paradoxical executable that refutes itself. The program could run correctly for years until someone turns on the optimizer and finds paradoxical results. Similar compiler innovations have produced all sorts of failures in working code including security failures. This stupid technology is constructed from the interaction of two reasonable projects that went wrong and then amplified each others difficulties. One project is the C standard committee tightening up C’s loose semantics. The other project is an effort to import new optimization methods into the C compilers. The flaws in each project have resonated with each other. In this case, different processor architectures (or processing modes) will produce different behavior when signed words overflow and C is designed to allow use of native arithmetic close to the machine level for utmost efficiency. But instead of finding ways to make signed integer overflow alternatives precise, the standards committee tossed signed overflow into special category of things labeled “undefined behavior” which is different from “indeterminate” or not specified in that undefined behavior makes C code “non-conforming” and “this International Standard imposes no requirements” for undefined behavior. Then, in a ghastly miscalculation, compiler developers interpreted “imposes no requirements” as a license to produce incorrect code and call it optimization. The standard imposes no requirements and it is convenient to assume there will not be overflows, so QED we can conclude that FALSE is TRUE. In fact, the position seems to be that if the compiler produces code that encrypts all your files, mails the password to Moldavia, and prints a cryptic message about end times, it’s all good. No requirements means no requirements and you should have declared those variables unsigned. This is no exaggeration. Discussing the undefined behavior of shift operations Lattner writes: ” shifting by 32-bits on PowerPC could format your hard drive, it is not guaranteed to produce zero.”
The unsound logic of the compilers has drawn complaints for decades: from the most prominent author of cryptography code ( DJB ), former members of the C standards committee ( Derek Jones), groups of researchers and academics (Regehr) and many C programmers (this one is like horror movie about an engineer trapped in a department of motor vehicles office). As Derek Jones observed, the main C compiler groups don’t sell software to application developers, so they don’t have to care. And the compiler developers don’t have anyone who can do what Linus Torvalds did for Linux so many times: politely and humbly reject innovations that break applications without compelling justification. Even worse, the standards committee and compiler developers split responsibility – so they can and do blame each other. The example cited by DJB is truly horrendous and is based on the standards edict that dereferencing a null pointer is undefined behavior (even though it’s widely used in embedded code and in some UNIX distributions).
- The code erroneously, but harmlessly in this case, dereferences a pointer before checking whether the pointer is null.
- The compiler considers two possibilities: either the pointer is not null, in which case the null check that follows is redundant, or the pointer is null in which case undefined behavior has been detected.
- The compiler “optimizes” by removing the null check (silently). Note that the code deleted is not “undefined behavior” code, it just follows the offending null pointer dereference so all rules are off.
- A security breach is discovered as someone exploited the failure of the code to check for null pointers.
All programming languages have some places where they run into machine or architecture or resource dependencies. If you take the most over-the-top mathematically pretentious highest level programming language and write code to compute factorial, a fairly small input will cause the program run out of time or memory and produce some error. Because C is so close to the machine, it bumps into hardware a lot. Pointers are machine addresses – just numbers, shift operations are specified to compile down to single machine instructions, and arithmetic is so close to the hardware that number representation schemes are programmer visible. As another example, C structures may contain “padding” bytes added by the compiler to accommodate processor alignment requirements. A structure struct x{ char c; int i;}; could have 3 bytes of padding inserted after the 1 byte character so that the integer is on a 4 byte boundary. For efficiency, padding bytes are generally uninitialized – not set to any particular value – so copying the structure may involve copying uninitialized data. The C90 standard declared that reading uninitialized bytes was undefined behavior. The unintentional consequence was that it became impossible to write the C library in conforming C because copying a structure in the memcpy routine might involve copying (reading and writing) uninitialized data. The standards committee “solved” the problem with a dismally giant hack by making unsigned characters specially immune from undefined behavior. If you copy indeterminate bytes via unsigned character pointers, that’s ok, but otherwise it’s undefined behavior. Here’s Chris Lattner explaining a small part of the resulting mess:
It is undefined behavior to cast an int* to a float* and dereference it (accessing the “int” as if it were a “float”). C requires that these sorts of type conversions happen through memcpy: using pointer casts is not correct and undefined behavior results. The rules for this are quite nuanced and I don’t want to go into the details here (there is an exception for char*, vectors have special properties, unions change things, etc). – Chris Lattner
To anyone who has ever managed a programming project, the signs of a fatally broken design decision are unmistakable (a cascade of special cases is never good). Nuance is nice in poetry, not in engineering. But the C standards committee was not piling whole categories of C code into the undefined behavior basket for no reason. They were trying to deal with two different types of pressure. The first is that the definition of C had too many holes in it so that C code was often way too machine or compiler dependent or just sloppy. The second problem was that C is resistant to a number of useful types of optimization and compiler developers pushed for changes that would allow them to assume things about code that made certain optimizations more widely applicable. It seems like the idea was that by ruling certain types of constructions to be “non-conforming”, the standard would discourage their use and make the language more consistent and more suited to modern optimization methods. As an example, certain widely used crypto code apparently uses uninitialized variables to inject randomness into low level encryption code – relying on the variable to be allocated from the leftover garbage on the stack. That code will fail dismally if stack allocation changes or automatic variables are not allocated from the stack (or the previously called process filled the stack with something predictable). So warning about that code or even refusing to compile it might improve applications, but because of the nice split in responsibilities, the Standards body can rule such code non-conforming and look away as the compiler writers then perform arbitrary transformations on that code.
And all of this is so unnecessary. As Jones points out, some sort of undefined behavior is intrinsic to C, but implementations are not required to treat it as an excuse for sabotaging programs:
A willingness to accept whatever behavior happens to occur, in an error situation, is the price that has to be paid for efficient execution on a wide range of disparate processors. The C/C++ designers were willing to pay this price while the Java designers were not, with the Ada designers willing to tolerate less variability than C/C++.
Undefined behavior need not be nasty behavior, an implementation could choose to generate a helpful message or try to recover from it.
Changes to the C standard could be used to make it more optimizable. C would definitely benefit from increased use of “restricted pointers” (the definitions needs to be clarified but it’s a great step forward.) And the gcc “pure” modifier on function types is interesting and should be considered for the standard. The standard could promote methods of writing verifiable, optimizable code as opt-in. An additional easy step would be to move things like reading uninitialized data from “undefined” to “indeterminate” and make pointer casting well-defined whenever alignment and object size are compatible. The Committee could also modify the definition of undefined behavior by specifically limiting the freedom of conforming implementations. Replacing “this International Standard imposes no requirements” with “conforming implementations may reject non-conforming constructs or implement in a consistent implementation dependent manner.” C already provides machine dependent information to the programmer. The file limits.h tells the programmer about the native word sizes and number ranges on the target computer. There is no reason why that cannot be extended to specify signed integer overflow behavior (and in 99.999% of cases that behavior is rollover). The language has intrinsic access to nonportable machine dependent and/or implementation dependent information. Pretending otherwise only creates too much – well – nuance. Underlying all of this, it’s easy to get the feeling that the C standards process and C compiler development has lost the plot – that the objective has become a doomed effort to recreate C as a kind of low grade patched up Ada or (forgive me) Rust. Consider this note on uninitialized data from Lattner
Use of an uninitialized variable: This is commonly known as source of problems in C programs and there are many tools to catch these: from compiler warnings to static and dynamic analyzers. This improves performance by not requiring that all variables be zero initialized when they come into scope (as Java does). For most scalar variables, this would cause little overhead, but stack arrays and malloc’d memory would incur a memset of the storage, which could be quite costly, particularly since the storage is usually completely overwritten.
But the alternatives are not only to either impose mandatory initialization of variables or to allow the compiler to treat use of uninitialized memory as permission to arbitrarily rewrite code. Where compilers and tools can warn about use of uninitialized variables – that’s good. Where they cannot, it should be up to the programmer. The intent of C is to give the programmer enormous flexibility. C developers are not supposed to need to escape the language and invoke pragmas or “unsafe” keywords (or call out to libraries written in some scorned low level language). The Linux networking code (lib/checksum) below shows off one of the compelling things about C – the ability to work directly with memory and control the mapping from bit patterns to denotations. The code is computing a checksum for a network packet. Starting with the packet data structure it first looks at it as a sequences of unsigned characters and then does a type coercion to map sequences of 4 unsigned characters into “int” types so it can run through and compute the checksum.
do {
unsigned int w = *(unsigned int *) buff;
buff += 4; result += carry;
result += w;
carry = (w > result); }
while (buff < end);
result += carry;
result = (result & 0xffff) + (result >> 16);This type of code makes it easy to screw up and can complicate optimization for compilers and everything for static analyzers (changes in type, aliased pointers, demonical possession … ) but it’s the essence of systems programming and a lot of application programming too. It’s what C was designed to do and for expert C programmers gives C programming a flexible and fluid character. Is this code legal C under the current C standard? It appears not. But if the standard requires the mother of all hacks to make memcpy implementation conform to spec (and not a real one either, it actually seems to force C compilers to use escape to assembler) it’s going to trip up C. And if the implementations are going to claim that unsound deduction is a legitimate optimization then C is really doomed.
Bonus – from the C89 standard.
A pointer to an object or incomplete type may be converted to a pointer to a different object type or a different incomplete type. The resulting pointer might not be valid if it is improperly aligned for the type pointed to. It is guaranteed, however, that a pointer to an object of a given alignment may be converted to a pointer to an object of the same alignment or a less strict alignment and back again; the result shall compare equal to the original pointer.
rough notes for this are at https://www.yodaiken.com/2017/06/16/the-c-standard-committee-effort-to-kill-c-continues/
Consider the following code:
void f(void) {
unsigned char x[1]; /* intentionally uninitialized */
x[0] ^= x[0];
printf("%d\n", x[0]);
printf("%d\n", x[0]);
return;
}In this example, the
unsigned chararrayxis intentionally uninitialized but cannot contain a trap representation because it has a character type. Consequently, the value is both indeterminate and an unspecified value. The bitwise exclusive OR operation, which would produce a zero on an initialized value, will produce an indeterminate result, which may or may not be zero. An optimizing compiler has the license to remove this code because it has undefined behavior. The twoprintfcalls exhibit undefined behavior and, consequently, might do anything, including printing two different values forx[0].
The programmer has clearly attempted to set x[0]=0. The compiler here is claimed to be “optimizing” by removing the xor. So what is exactly made faster or more efficient by this “optimization” ? (Note that there is no “volatile” used on the variable, so the compiler is permitted to optimize using the result of the first read.) Let me ask an easier question: is there an example of a program in which such an “optimization” results in a better executable by some sensible measure? If all we care about is execution speed, without regard to program correctness, compilers could optimize by generating nothing at all. Wow, that null program sure runs fast!
Some compiler writers would prefer to eliminate trap representations altogether and simply make any uninitialized read undefined behavior—the theory being, why prevent compiler optimizations because of obviously broken code? The counter argument is, why optimize obviously broken code and not simply issue a fatal diagnostic?
Why optimize obviously broken code? Why declare a working and common usage in C to be broken in the first place?
According to the current WG14 Convener, David Keaton, reading an indeterminate value of any storage duration is implicit undefined behavior in C, and the description in Annex J.2 (which is non-normative) is incomplete. This revised definition of the undefined behavior might be stated as “The value of an object is read while it is indeterminate.”
And yet:
Uninitialized memory has been used as a source of entropy to seed random number generators in OpenSSL, DragonFly BSD, OpenBSD, and elsewhere.10 If accessing an indeterminate value is undefined behavior, however, compilers may optimize out these expressions, resulting in predictable values.1
So the intent of at least some members of the C standard committee is to make production C code fail in some unpredictable manner as an “optimization”. Despite the best efforts of developers of rival programming languages, C’s advantages have preserved it as an indispensable systems and applications programming language. Whether it can survive the C standards process is a different question.
As a final note: this type of design failure is not all that unusual, but it’s the job of engineering management to block it. The proposal to silently make working crypto code fail in order to enable some type of efficiency for the compiler should be a non-starter.
Thanks to John Regehr for bringing this report from the weird underworld of C standard development to my attention. Also this