Month: June 2018

Categories
C standard programming languages

Three modest proposals for the C standard WG14

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

 

Categories
programming languages

Vector optimization with C aliasing

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
Categories
C standard operating systems programming languages

Torvalds on aliasing

See also   Dennis Ritchie on aliasing, PLOS article,  pointer alias in C and remarks on the purpose of C. 

From: LKML

From Linus Torvalds <>
Date Tue, 5 Jun 2018 10:30:21 -0700
Subject Re: [GIT PULL] Device properties framework update for v4.18-rc1 
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
Categories
programming languages

Pointer alias analysis in C

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. – Dennis Ritchie, 1988

 

From the beginning of the C standards process, the standards committee has wanted to  break C pointer semantics in the cause of never quantified compiler optimizations.  In C, pointers are memory addresses with types to permit both pointer arithmetic scaled to the size of the data type and checking for unintentional misapplication – such as assigning the result of dereferencing an integer pointer to a structure.  Pointer aliasing (multiple pointers addressing  the same or overlapping memory objects) and “type punning” (pointing to the same memory block with pointers of different types) are fundamental operations in C. For example, the C library sorting utility relies on converting pointers to an array of some type to pointer “void *” so it can sort arrays of abitrary type.  Similarly the C library memory allocators return pointers of type “void *” that are generally converted to non-void typed pointers, e.g. “struct mystruct *m = malloc(sizeof(struct mystruct))”. In a sequence, “x  = malloc(n); … free(x)… y = malloc(m) …” that same pointer value may be reused multiple times to point to objects of different type. The memory copy utility is passed “void *”  pointers too, and then internally decides where it should copy byte by byte or using larger chunks of memory.

Compiler developers prefer to limit both pointer alias  and  type-punning.  The “noalias” discussion was ostensibly driven by the difficulty of vectorizing code given overlapping pointers – an issue that has been considered in FORTRAN almost since the dawn of time.  Essentially pointer-aliasing creates a classical consistency issue, like ones we have in distributed computing. Suppose we have code:

 *x += *y; *(x+1) += *(y+1)

Given a two element vector load, store, and addition instructions, the compiler could potentially get this done in parallel: maybe
“load2 v,x” to load *x and *(x+1) into the vector register and “add2 v,y” for the addition of (*y,*(y+1))  and “store v x” would complete it. But maybe the bad programmer has an overlapping alias and x = y+1. If y points to [10,20,30] then the step-by step produces [10,30,20] and then [10,30,50] but the parallel operation produces [10,40,40].  This gets more depressing for large scale matrix operations – which is where it was first encountered in FORTRAN.  So compiler writers would like to have unaliased pointers, but in C, aliased pointers are very useful. To move all the elements of a string left by one place is a simple application: “b = c+1; while( (*c++ = *b++))”.   Another obvious example is computing a checksum for a packet. Instead of worrying about the possibly complex structure of the packet, the programmer might want to think of it as a sequence of 64bit unsigned ints and just xor them, but this requires pointers to overlapping memory object that don’t have the same type. So these kinds of pointer operations are useful and customary in C code and, to make it more peculiar, the claimed optimizations are of such marginal utility and so dangerous that the Linux project specifically disables them (fno-strictalias).

If the only reason is to permit compilers to use vector instructions in loops, it seems like a simple opt-in could be used. C restrict is a solution, even though the standard description of it is terrible. The only other substantive optimization found in examples is where the compiler can substitute “memcpy” (which assumes non-overlapping pointers) for a loop, but surely that’s something the programmer should do where it’s an advantage.  Maybe there are other reasons for wanting unaliased pointers (the examples in Regehr’s post are not all that compelling)  and someone can tell me about them.

The compiler developers and standards authors, however, don’t want to leave it to the programmers. Instead they have made use of a loophole created in C99 which can be read as permitting compilers to do anything at all in the presence of “undefined behavior” and another change to the C standard that allows pointer casting and aliasing to be treated as undefined behavior.

Anyone who thinks the C Standard has a clear or even excusable model of type-punning and pointer alias could read this horrifying discussion    which ends with the understatement “The conclusion for the de facto semantics here is not completely clear. ” ( via @comex in twitter)  or look at John Regehr’s authoritative post with the even more understated title:

The Strict Aliasing Situation is Pretty Bad

And now, we can see that the standards committee is attempting to go way beyond these to make pointer rules even more opaque.

See this for a more optimistic take.