==========================================================

Document: N2222

Related:

N2223: Clarifying the C Memory Object Model: Introduction to N2219 - N2222, N2089, Section 2 of N2012, Sections 3.1 and 3.2 (Q48-59) of N2013, DR338, DR451, N1793, N1818.

1 Summary

This document describes a collection of non-provenance pointer issues, complementing the provenance, trap-representation, and uninitialised-value discussion of N2219-N2221. It builds on N2012.

For these questions we make tentative proposals for the semantics, but do not spell out detailed changes to the ISO text.

2 Questions and Examples

2.1 Stability of pointer values

2.1.1 Q21 Are pointer values stable?

We assume, in both de facto and ISO standard semantics, that pointer values are stable over time, as are the results of comparisons of them (modulo nondeterministic choices as to whether their provenance is taken into account in those comparisons).

This follows our understanding of normal implementations and our reading of the ISO standard, which says (6.2.4p2): "[...] An object exists, has a constant address, 33) and retains its last-stored value throughout its lifetime. [...]" where footnote 33 is: "The term constant address" means that two pointers to the object constructed at possibly different times will compare equal. The address may be different during two different executions of the same program.''}. It rules out C implementations using a moving garbage collector.

For example, we believe the following should be guaranteed to print true:

Example pointer_stability_1.c

#include <stdio.h>
#include <inttypes.h>
int main() {
  int x=1;
  uintptr_t i = (uintptr_t) &x;
  uintptr_t j = (uintptr_t) &x;
  // is this guaranteed to be true?
  _Bool b = (i==j);
  printf("(i==j)=%s\n",b?"true":"false");
  return 0;
}

Proposed TC: none - we think the current text is clear.

2.2 Pointer Equality Comparison (with == and !=)

There are several notions of pointer equality which would coincide in a completely concrete semantics but which in a provenance-aware semantics can differ:

  1. comparison with ==
  2. comparison of their representations, e.g. with memcmp
  3. accessing the same memory
  4. giving rise to equally defined or undefined behaviour
  5. equivalent as far as alias analysis is concerned

As we note elsewhere, the standard appears to use compare equal to imply that the pointers are equally usable, but that is not the case in a post-DR260 semantics with provenance. Our first examples show cases where two pointers are memcmp-equal but ==-unequal, and where they are memcmp or == equal but accessing them is not equally defined.

In this document, we say that two pointer values are equivalent if they are interchangeable, satisfying all of (1-5). And we say that a pointer value is usable if accesses using it access the right memory and do not give rise to undefined behaviour.

Proposed TC: go through the occurrences of compare equal in ISO and check which should be replaced by compare equal and have the same provenance.

2.2.1 Q22 Can one do == comparison between pointers to objects of non-compatible types?

The ISO standard allows == comparison between pointers to different objects of compatible types (6.5.9). With provenance (see N2089 Q2) that should be nondeterministically allowed to be provenance-aware.

It is unclear whether the restriction to compatible types is needed for mainstream implementations. For the following, GCC and Clang both give warnings; GCC says that this comparison without a cast is enabled by default, perhaps suggesting that it is used in the de facto standard corpus of code and hence that our de facto standard semantics should allow it.

Example pointer_comparison_eq_1_global.c

#include <stdio.h>
#include <string.h> 
int  x=1;
float f=1.0;
int main() {
  int *p = &x; 
  float *q = &f;
  _Bool b = (p == q); // free of undefined behaviour?
  printf("(p==q) = %s\n", b?"true":"false");
  return 0;
}

Compilers might conceivably optimise such comparisons (between pointers of non-compatible type) to , but the following example suggests that GCC does not:

Example pointer_comparison_eq_2_global.c

#include <stdio.h>
#include <string.h> 
int  x=1;
float f=1.0;
int main() {
  int *p = (int *)&f; 
  float *q = &f;
  _Bool b = (p == q); // free of undefined behaviour?
  printf("(p==q) = %s\n", b?"true":"false");
  return 0;
}

The question is basically asking whether one can assume that pointers to different types have the same representation.
Similarly to punning between pointer and integer values, in principle a de facto semantics should allow this iff the implementation-defined functions that map between the different pointer representation types are the identity. In practice, that holds for many or all `mainstream' implementations, for which we can just regard it as allowed.

Proposed TC (tentative): make it implementation-defined whether such comparisons are allowed or not. One might require a switch for this, but that could be costly for implementations that don't have common pointer representations.

2.2.2 Q23 Can one do == comparison between pointers (to objects of compatible types) with different provenances that are not strictly within their original allocations?

Example klw-itp14-2.c

#include <stdio.h>
int  x=1, y=2;
int main() {
  int *p = &x + 1; 
  int *q = &y;
  _Bool b = (p == q); // free of undefined behaviour?
  printf("(p==q) = %s\n", b?"true":"false");
  return 0;
}

This example is from Krebbers et al. [ITP 2014]. Their model forbids this, while the candidate de facto model we propose should allow arbitrary pointer comparison.

Proposed TC: none - ISO already clearly allows this.

2.2.3 Q24 Can one do == comparison of a pointer and (void*)-1?

#include <stdlib.h>
int main() { 
  void *p = mmap(...);
  _Bool b = (p == (void*)-1); // defined behaviour?
}

This is from Besson et al.[APLAS 2014]. Their 6.2 notes that system calls such as mmap return -1 on error, and so one must be able to compare pointers against that.
John Regehr observes that sqlite also compares against -2 and other error codes. In a semantics in which == nondeterministically respect provenance, the constant value should be constructed in a provenance-free fashion, otherwise such a comparison might mistakenly give false.

Proposed TC: none. This idiom relies on the implementation-defined conversion between integers and pointers, and also on the (in our proposal) implementation-defined set of trap representations at each type, so that converting -1 or -2 gives a useful pointer value. But given those, the ISO text is clear that the idiom is legal.

2.3 Pointer Relational Comparison (with <, >, <=, or >=)

Here the ISO standard seems to be significantly more restrictive than common practice. First, there is a type constraint, as for ==: 6.5.8p2 *"both operands are pointers to qualified or unqualified versions of compatible object types"&.

Then 6.5.8p5 allows comparison of pointers only to the same object (or one-past) or to members of the same array, structure, or union: 6.5.8p5 "When two pointers are compared, the result depends on the relative locations in the address space of the objects pointed to. If two pointers to object types both point to the same object, or both point one past the last element of the same array object, they compare equal. If the objects pointed to are members of the same aggregate object, pointers to structure members declared later compare greater than pointers to members declared earlier in the structure, and pointers to array elements with larger subscript values compare greater than pointers to elements of the same array with lower subscript values. All pointers to members of the same union object compare equal. If the expression P points to an element of an array object and the expression Q points to the last element of the same array object, the pointer expression Q+1 compares greater than P. In all other cases, the behavior is undefined."

(Similarly to 6.5.6p7 for pointer arithmetic, 6.5.8p4 treats all non-array element objects as arrays of size one for this: 6.5.8p4 "For the purposes of these operators, a pointer to an object that is not an element of an array behaves the same as a pointer to the first element of an array of length one with the type of the object as its element type.")

This rules out the following comparisons, between pointers to two separately allocated objects and between a pointer to a structure member and one to a sub-member of another member, but some of these seem to be relied upon in practice.

2.3.1 Q25 Can one do relational comparison (with <, >, <=, or >=) of two pointers to separately allocated objects (of compatible object types)?

Example pointer_comparison_rel_1_global.c

#include <stdio.h>
int  y = 2, x=1;
int main() {
  int *p = &x, *q = &y;
  _Bool b1 = (p < q); // defined behaviour?
  _Bool b2 = (p > q); // defined behaviour?
  printf("Addresses: p=%p  q=%p\n",(void*)p,(void*)q);
  printf("(p<q) = %s  (p>q) = %s\n",
         b1?"true":"false", b2?"true":"false");
}

In practice, comparison of pointers to different objects seems to be used heavily, e.g. in memory allocators and for a lock order in Linux, and we believe the de facto semantics should allow it (leaving aside segmented architectures). Though one respondent reported that this idiom "May produce inconsistent results in practice if p and q straddle the exact middle of the address space" and that code should always cast to intptr_t first.

Proposed TC: debatable: either (a) require a switch to make this allowed or UB, or (b) require it to be implementation-defined whether it is allowed or UB. Or (c) making it implementation-defined whether there is a switch, and forbidden if not.

One must then ask whether it should be permitted to be provenance-aware in some fashion, analogously to ==? A compiler that aggressively follows the ISO standard might exploit its static knowledge of the order in which the allocations lie in memory, and assume that no more-than-plus-one arithmetic is done on the pointers, and hence sometimes use that statically known order rather than actually comparing the numerical values of the pointer.
We have not as yet tested this; for the time being we suppose that compilers do not do that, and it seems undesirable for programmers, so we propose not.

Proposed TC: we should make clear that "to separately allocated objects" is a provenance identity check? No, it's more subtle: what about pointer values with wildcard or empty provenance? We think we should allow wildcards but not empty?

2.3.2 Q26 Can one do relational comparison (with <, >, <=, or >=) of a pointer to a structure member and one to a sub-member of another member, of compatible object types?

Example pointer_comparison_rel_substruct.c

#include <stdio.h>
typedef struct { int i1; float f1; } st1;
typedef struct { int i2; st1 s2; } st2;
int main() {
  st2 s = {.i2=2, .s2={.i1=1, .f1=1.0 } };
  int *p = &(s.i2), *q = &(s.s2.i1);
  _Bool b = (p < q); // does this have defined behaviour?
  printf("Addresses: p=%p  q=%p\n",(void*)p,(void*)q);
  printf("(p<q) = %s\n", b?"true":"false");
}

Whether this is allowed in the ISO standard depends on one's interpretation of 6.5.8p5 "If the objects pointed to are members of the same aggregate object". A literal reading suggests that it is not, as the object pointed to by q is not a member of the struct, but merely a part of a member of it. But we see no reason to forbid this in a de facto standard semantics. (The only possible issue we can imagine, rather hypothetically, is with objects that span multiple segments in a segmented architecture.)

Proposed TC: in 6.5.8p5, replace "If the objects pointed to are members of the same aggregate object," by "If the objects pointed to are (hereditarily) members of the same aggregate object," and explain what that means somewhere.

2.3.3 Q27 Can one do relational comparison (with <, >, <=, or >=) of pointers to two members of a structure that have incompatible types?

The ISO standard constraint also rules out comparison of pointers to two members of a structure with different types:

Example pointer_comparison_rel_different_type_members.c

#include <stdio.h>
typedef struct { int i; float f; } st;
int main() {
  st s = {.i=1, .f=1.0 };
  int *p = &(s.i);
  float *q = &(s.f);
  _Bool b = (p < q); // does this have defined behaviour?
  printf("Addresses: p=%p  q=%p\n",(void*)p,(void*)q);
  printf("(p<q) = %s\n", b?"true":"false");
}

As above, this is presumably similarly to let implementations use different representations for pointers to different types. In practice GCC gives the same warning, comparison of distinct pointer types lacks a cast [enabled by default], which weakly implies that this is used in practice and that our de facto semantics should allow it.

We are told that this is occasionally used in Linux, though normally after casts to void*, to compare locks of different types. In our de facto semantics, in principle this should be implementation-defined in the same way as == comparison between objects of incompatible types.

Proposed TC: follow Q25 PTC.

2.4 Null pointers

2.4.1 Q28 Can one make a null pointer by casting from a non-constant integer expression?

The ISO standard permits the construction of null pointers by casting from integer constant zero expressions, but not from other integer values that happen to be zero (6.3.2.3p3): "An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. (Footnote 66) If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function. 66) The macro NULL ` is defined in stddef.h (and other headers) as a null pointer constant; see 7.19."

Example null_pointer_1.c

#include <stdio.h> 
#include <stddef.h> 
#include <assert.h> 
int y=0;
int main() {
  assert(sizeof(long)==sizeof(int*));
  long x=0;
  int *p = (int *)x;
  // is the value of p a null pointer?
  _Bool b1 = (p == NULL);// guaranteed to be true?
  _Bool b2 = (p == &y);  // guaranteed to be false?
  printf("(p==NULL)=%s  (p==&y)=%s\n", b1?"true":"false", 
         b2?"true":"false");
}

The situation in practice is not completely clear. Chisnall et al.[ASPLOS 2015] observe that "this distinction is difficult to support in modern compilers" and points to an LLVM mailing list thread that suggests that lots of code depends on being able to form null pointers from non-constant zero expressions. It would be useful to know of current platforms in which the NULL pointer is not represented with a zero value.

A reasonable de facto semantics would be to introduce an implementation-defined specification of the set of null pointer values (typically the singleton set containing 0), and to allow construction of null pointers by casting any of these values. Does that sufficiently subsume current behaviour, or do we need to preserve the strict ISO behaviour by guarding this with another switch, in Cerberus and/or inthe standard? (eg -fallow_non_constant_null_casts)

There is also an interaction between null pointers and provenance: probably one should erase provenance information on a cast of a null pointer to or from an integer zero value; perhaps also on arithmetic that produces zero values. For comparisons of a null pointer and a non-null pointer, we need to guarantee that the result is false irrespective of provenance - that's easy. But for comparisons of two null pointers, should we guarantee that provenance is not taken into account?

2.4.2 Q29 Can one assume that all null pointers have the same representation?

The ISO standard 6.3.2.3p3 says this for comparison: "Conversion of a null pointer to another pointer type yields a null pointer of that type. Any two null pointers shall compare equal." but leaves open whether they have the same representation bytes.

Example null_pointer_2.c

#include <stdio.h> 
#include <stddef.h> 
#include <string.h>
#include <assert.h> 
int y=0;
int main() {
  assert(sizeof(int*)==sizeof(char*));
  int *p = NULL;
  char *q = NULL;
  // are two null pointers guaranteed to have the
  //  same representation?
  _Bool b = (memcmp(&p, &q, sizeof(p))==0);
  printf("p=%p q=%p\n",(void*)p,(void*)q);
  printf("%s\n",b?"equal":"unequal");
}

The de facto semantics should base this on the implementation-defined set of null-pointer values. Or, even more simply and consistent with the desire for calloc to initialise memory that will be used as pointer values to the representation of NULL, just fix on zero.

2.4.3 Q30 Can null pointers be assumed to have all-zero representation bytes?

Example null_pointer_3.c

#include <stdio.h> 
#include <stddef.h> 
#include <string.h>
#include <stdlib.h>
int y=0;
int main() {
  int *p = NULL;
  int **q = (int **) calloc(1,sizeof(int*));
  // is this guaranteed to be true?
  _Bool b = (memcmp(&p, q, sizeof(p))==0);
  printf("%s\n",b?"zero":"nonzero");
}

For our de facto semantics this should likewise be based on the implementation-defined set of null-pointer values.

2.5 Pointer Arithmetic

The ISO standard permits only very limited pointer arithmetic, restricting the formation of pointer values.

First, there is arithmetic within an array: 6.5.6 Additive operators} (6.5.6p{8,9}) permits one to add a pointer and integer (or subtract an integer from a pointer) only within the start and one past the end of an array object, inclusive.
6.5.6p7 adds "For the purposes of these operators, a pointer to an object that is not an element of an array behaves the same as a pointer to the first element of an array of length one with the type of the object as its element type." Subtraction of two pointers is permitted only if both are in a similar range (and only if the result is representable in the result type).

Second, 6.3.2.3p7 says that one can do pointer arithmetic on character-type pointers to access representation bytes: "[...] When a pointer to an object is converted to a pointer to a character type, the result points to the lowest addressed byte of the object. Successive increments of the result, up to the size of the object, yield pointers to the remaining bytes of the object."

2.5.1 Q31 Can one construct out-of-bounds (by more than one) pointer values by pointer arithmetic (without undefined behaviour)?

In practice it seems to be common to transiently construct out-of-bounds pointer values, e.g.with (px +11) -10 rather than px + (11-10), as below, and we are not aware of examples where this will go wrong in standard implementations, at least for small deltas that are not near the top of memory. There are cases where pointer arithmetic subtraction can overflow. There might conceivably be an issue on some platforms if the transient value is not aligned and only aligned values are representable at the particular pointer type, or if the hardware is doing bounds checking, but both of those seem exotic at present. There are also cases where pointer arithmetic might wrap at values less than the obvious word size, e.g. for "near" or "huge" pointers on 8086, but it is not clear if any of these are current.

Example cheri_03_ii.c

#include <stdio.h>
int main() {
  int x[2];
  int *p = &x[0];
  //is this free of undefined behaviour?
  int *q = p + 11;
  q = q - 10;
  *q = 1;
  printf("x[1]=%i  *q=%i\n",x[1],*q);
}

This is the invalid intermediate idiom of Chisnall et al.[ASPLOS 2015]. We (somewhat tentatively) propose that it be allowed in the de facto semantics.

Proposed TC: We guess the more liberal behaviour will not be universally acceptable, so this should be a switch (in Cerberus and in the standard) (e.g. -fallow-oob-pointer-arithmetic). What about subtraction overflow? C.f. also the recent C++ committee discussion towards fixing on two's complement arithmetic. In some implementations (CHERI in particular) pointer arithmetic can go somewhat out-of-bounds but not arbitrarily so; is there a useful way to define how much?

2.5.2 Q32 Can one form pointer values by pointer addition that overflows (without undefined behaviour)?

Example pointer_add_wrap_1.c

#include <stdio.h>
int main() {
  unsigned char x;
  unsigned char *p = &x;
  unsigned long long h = ( 1ull << 63 );
  //are the following free of undefined behaviour?
  unsigned char *q1 = p + h;
  unsigned char *q2 = q1 + h;
  printf("Addresses: p =%p  q1=%p\n",
         (void*)p,(void*)q1);
  printf("Addresses: q2=%p  h =0x%llx\n",
         (void*)q2,h);
}

Obviously this presumes that constructing an out-of-bounds (by more than one) pointer value by pointer arithmetic, as above, is itself allowed. We propose that this too be allowed, guarded by the same flag.

2.5.3 Q33 Can one assume pointer addition wraps on overflow?

Example pointer_add_wrap_2.c

#include <stdio.h>
int main() {
  unsigned char x;
  unsigned char *p = &x;
  unsigned long long h = ( 1ull << 63 );
  //are the following free of undefined behaviour?
  unsigned char *q1 = p + h;
  unsigned char *q2 = q1 + h;
  *q2 = 1;
  printf("Addresses: p =%p  q1=%p\n",
         (void*)p,(void*)q1);
  printf("Addresses: q2=%p  h =0x%llx\n",
         (void*)q2,h);
  printf("x=0x%x  *p=0x%x  *q2=0x%x\n",x,*p,*q2);
}

And this.

Proposed TC: likewise

2.5.4 Q34 Can one move among the members of a struct using representation-pointer arithmetic and casts?

The standard is ambiguous on the interaction between the allowable pointer arithmetic (on unsigned char* representation pointers) and subobjects. For example, consider:

Example cast_struct_inter_member_1.c

#include <stdio.h>
#include <stddef.h>
typedef struct { float f; int i; } st;
int main() {
  st s = {.f=1.0, .i=1};
  int *pi = &(s.i);
  unsigned char *pci = ((unsigned char *)pi);
  unsigned char *pcf = (pci - offsetof(st,i)) 
    + offsetof(st,f);
  float *pf = (float *)pcf;
  *pf = 2.0;  // is this free of undefined behaviour?
  printf("s.f=%f *pf=%f  s.i=%i\n",s.f,*pf,s.i);
}

This forms an unsigned char* pointer to the second member (i) of a struct, does arithmetic on that using offsetof to form an unsigned char* pointer to the first member, casts that into a pointer to the type of the first member (f), and uses that to write.

In practice we believe that this is all supported by most compilers and it is used in practice, e.g. as in the Container idiom of Chisnall et al. [ASPLOS 2015], where they discuss container macros that take a pointer to a structure member and compute a pointer to the structure as a whole. They see it heavily used by one of the example programs they studied. We are told that Intel's MPX compiler does not support the container macro idiom, while Linux, FreeBSD, and Windows all rely on it.

The standard says (6.3.2.3p7): "...When a pointer to an object is converted to a pointer to a character type, the result points to the lowest addressed byte of the object. Successive increments of the result, up to the size of the object, yield pointers to the remaining bytes of the object.". This licenses the construction of the unsigned char* pointer pci to the start of the representation of s.i (presuming that a structure member is itself an "object", which itself is ambiguous in the standard), but allows it to be used only to access the representation of s.i.

The offsetof definition in stddef.h, 7.19p3, " offsetof(type,member-designator) which expands to an integer constant expression that has type size_t, the value of which is the offset in bytes, to the structure member (designated by member-designator, from the beginning of its structure (designated by type", implies that the calculation of pcf gets the correct numerical address, but does not say that it can be used, e.g. to access the representation of s.f. As we saw in the discussion of provenance, in a post-DR260 world, the mere fact that a pointer has the correct address does not necessarily mean that it can be used to access that memory without giving rise to undefined behaviour.

Finally, if one deems pcf to be a legitimate char* pointer to the representation of s.f, then the standard says that it can be converted to a pointer to any object type if sufficiently aligned, which for float* it will be. 6.3.2.3p7: "A pointer to an object type may be converted to a pointer to a different object type. If the resulting pointer is not correctly aligned (68) for the referenced type, the behavior is undefined. Otherwise, when converted back again, the result shall compare equal to the original pointer....". But whether that pointer has the right value and is usable to access memory is left unclear.

This example should be allowed in our de facto semantics but is not clearly allowed in the ISO text.

What needs to be changed in the ISO text to clarify this?

More generally, the ISO text's use of "object" is unclear: does it refer to an allocation, or are struct members, union members, and array elements also "objects"?

2.5.5 Q35 Can one move between subobjects of the members of a struct using pointer arithmetic?

Example struct_inter_submember_1.c

#include <stdio.h>
#include <stddef.h>
struct S { int a[3]; int b[3]; } s;
int main() {
  s.b[2]=10;
  ptrdiff_t d;
  d = &(s.b[2]) - &(s.a[0]);  // defined behaviour?
  int *p;
  p = &(s.a[0]) + d;          // defined behaviour?
  *p = 11;                    // defined behaviour?
  printf("d=%td  s.b[2]=%d  *p=%d\n",d,s.b[2],*p);
}

This is based on an example of Krebbers [PhD]. In the very strong interpretation of effective types taken there, one can only do pointer manipulation within the same leaf subobject (or one-past). For de facto C, it seems necessary to allow it more generally, anywhere within the allocated object.

Another reasonable option, suggested by the RV-match documents, would allow inter-subobject pointer arithmetic only if mediated by some cast(s). That would forbid this example, but still allow the Q34 example.

2.5.6 Q36 Can one implement offsetof using the addresses of members of a NULL struct pointer?

Example ubc_addr_null_1.c

#include <stddef.h>
#include <inttypes.h>
#include <stdio.h>
struct s { uint8_t a; uint8_t b; };
int main () {
  struct s *f = NULL;
  uint8_t *p = &(f->b); // free of undefined behaviour?
  // and equal to the offsetof result? 
  printf("p=%p  offsetof(struct s,b)=0x%zx\n",
         (void*)p,offsetof(struct s, b));
}

This test is inspired by examples from Regehr's UB Canaries. It seems to be a common idiom in practice. If one views p->x as syntactic sugar for (*p).x (as stated by Jones but, interestingly, not the ISO standard) then this is undefined behaviour when p is null. CompCert seems to do this, while GCC seems to keep the -> at least as far as GIMPLE. Our de facto model should allow it, in any case.

2.6 Casts between pointer types

The standard (6.3.2.3p{1-4,7,8}) identifies various circumstances in which conversion between pointer types is legal, with some rather weak constraints on the results:

  1. "A pointer to void may be converted to or from a pointer to any object type. A pointer to any object type may be converted to a pointer to void and back again; the result shall compare equal to the original pointer."

  2. "For any qualifier q, a pointer to a non-q-qualified type may be converted to a pointer to the q-qualified version of the type; the values stored in the original and converted pointers shall compare equal."

  3. "A pointer to an object type may be converted to a pointer to a different object type. If the resulting pointer is not correctly aligned 68) for the referenced type, the behavior is undefined. Otherwise, when converted back again, the result shall compare equal to the original pointer. When a pointer to an object is converted to a pointer to a character type, the result points to the lowest addressed byte of the object. Successive increments of the result, up to the size of the object, yield pointers to the remaining bytes of the object."

  4. "A pointer to a function of one type may be converted to a pointer to a function of another type and back again; the result shall compare equal to the original pointer. If a converted pointer is used to call a function whose type is not compatible with the referenced type, the behavior is undefined."

Paragraphs 3 and 4 relate to null pointers and Paragraphs 5 and 6 relate to casts between pointer and integer types, discussed elsewhere. Footnote 68 just says that "correctly aligned" should be transitive.

This raises several questions. First, this *compare equal" is probably supposed to mean the the pointers are (in our sense discussed above) equivalent: that they not only compare equal with == but also are equally usable to access (the same) memory and have equal representations.
This text is probably pre-DR260, when these concepts arguably coincided.

Second, the standard only covers roundtrips of size two, via one other pointer type and back. This seems curiously irregular: there seems to be no reason not to give a roundtrip property for longer roundtrips via multiple pointer types, and both our ISO and de facto standard semantics should allow that.

Third, (7) gives undefined behaviour for a conversion between object types where the result value is not aligned for the new type, while (1) allows such a conversion via (void *), albeit with no guarantee on the result.

Fourth, it gives no guarantees for the usability of pointers constructed by a combination of casts and arithmetic.

Additionally, 6.7.2.1 Structure and union specifiers licenses conversions (in both directions) between pointers to structures and their initial members, and between unions and their members.

The Friendly C proposal (Point 4) by Cuoq et al. has a link which points to C committee discussion for DR195 in which they considered interconvertability of object and function pointers. POSIX apparently requires it, for dlsym.

2.6.1 Q37 Are usable pointers to a struct and to its first member interconvertable?

Example cast_struct_and_first_member_1.c

#include <stdio.h>
typedef struct { int  i; float f; } st;
int main() {
  st s = {.i = 1, .f = 1.0};
  int *pi = &(s.i);
  st* p = (st*) pi; // free of undefined behaviour?
  p->f = 2.0;       // and this?
  printf("s.f=%f  p->f=%f\n",s.f,p->f);
}

This is allowed in the standard: 6.7.2.1p15 "Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared. A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning."

2.6.2 Q38 Are usable pointers to a union and to its current member interconvertable?

Example cast_union_and_member_1.c

#include <stdio.h>
typedef union { int  i; float f; } un;
int main() {
  un u = {.i = 1};
  int *pi = &(u.i);
  un* p = (un*) pi; // free of undefined behaviour?
  p->f = 2.0;       // and this?
  printf("u.f=%f  p->f=%f\n",u.f,p->f);
}

This is also allowed in ISO: 6.7.2.1p16 "The size of a union is sufficient to contain the largest of its members. The value of at most one of the members can be stored in a union object at any time. A pointer to a union object, suitably converted, points to each of its members (or if a member is a bit-field, then to the unit in which it resides), and vice versa."

A strict ISO standard semantics should allow the conversion in exactly the cases picked out by 6.3.2.3p{1-4,7,8} and 6.7.2.1p{15,16}. If the result is aligned (a property of its numeric address, not of its original type, or of the static type we are casting from) for the new type it would be left unchanged, otherwise give undefined behaviour. The former is slightly more liberal than the standard text, allowing (e.g.) round-trips of length more than two and casts via an intermediate pointer type (with intermediate alignment constraints) to (char *).

A de facto semantics should allow all conversions except (optionally, controlled by a switch) between function pointers and pointers to object types. It should probably allow the formation of misaligned pointers by this or by pointer arithmetic (see Example provenance_tag_bits_via_uintptr_t_1.c) (though some survey responses from compiler developers suggest otherwise), though accesses using those pointers may give undefined behaviour. In particular, atomic accesses via misaligned pointers (especially to regions of memory that span cache lines) may not be supported by typical hardware, and so should give undefined behaviour at the language level.

Proposed TC: is this best dealt with by requiring the conversions to be implementation-defined functions?

If one only accesses structures via assignment and member projections, the standard treats structure types abstractly. Type declarations create new types (6.7.2.{1,3}), accessing a structure member requires the name of a member of the type (6.5.2.3p{1,2}), and assignment requires the left and right-hand-side types to be compatible (6.5.16.1p1b{2,3}), where (6.2.7p1) for two structure types to be compatible they have to be either the same or (if declared in separate translation units) very similar: broadly, with the same ordering, names, and compatible types of members.

But the standard permits several ways to break this type abstraction: conversion between pointers to object types, reading from a union of structures sharing a common initial sequence, and type punning by writing and reading different union members. Most simply, one can initialise a structure by initialising its individual members at their underlying types:

Example struct_initialise_members.c

#include <stdio.h>
void f(char* cp, float*fp) {
  *cp='A';
  *fp=1.0;
}
typedef struct { char c; float f; } st;
int main() {
  st s1;
  f(&s1.c, &s1.f);
  st s2;
  s2 = s1;
  printf("s2.c=0x%x  s2.f=%f\n",s2.c,s2.f);
}

This suggests that isomorphic structs could be interchangeable as memory objects, at least if one can cast from one pointer type to the other. This is reasonable in the de facto semantics, as struct layout is fixed by the ABI, but the standard's effective types make it false in ISO.

Even in the de facto semantics, isomorphic struct types are not directly interchangeable. The following example gives a static type error in GCC and Clang, and is clearly forbidden in the standard (for the two struct types to be compatible they have to be almost identical).

Example use_struct_isomorphic.c

#include <stdio.h>
typedef struct { int  i1; float f1; } st1;
typedef struct { int  i2; float f2; } st2;
int main() {
  st1 s1 = {.i1 = 1, .f1 = 1.0 };
  st2 s2;
  s2 = s1; 
  printf("s2.i2=%i2  s2.f2=%f\n",s2.i2,s2.f2);
}

Most generally, 6.3.2.3p7 says that "A pointer to an object type may be converted to a pointer to a different object type", if "the resulting pointer is correctly aligned" otherwise undefined behaviour results. (6.5.4 Cast operators does not add any type restrictions to this.)

There are two interesting cases here: conversion to a char * pointer and conversion to a related structure type. In the former, 6.3.2.3p7 (as discussed elsewhere) goes on to specify enough about the value of the resulting pointer to make it usable for accessing the representation bytes of the original object. In the latter, the standard says little about the resulting value, but it might be used to access related structures without going via a union type.

2.7.1 Q39 Given two different structure types sharing a prefix of members that have compatible types, can one cast a usable pointer to an object of the first to a pointer to the second, that can be used to read and write members of that prefix (with strict-aliasing disabled and without packing variation)?

First we consider a case with two isomorphic structure types:

Example cast_struct_isomorphic.c

#include <stdio.h>
typedef struct { int  i1; float f1; } st1;
typedef struct { int  i2; float f2; } st2;
int main() {
  st1 s1 = {.i1 = 1, .f1 = 1.0 };
  st2 *p2 = (st2 *) (&s1);// is this free of undef.beh.?
  p2->f2=2.0;             // and this?
  printf("s1.f1=%f  p2->f2=%f\n",s1.f1,p2->f2);
}

And now with a common prefix but differing after that:

Example cast_struct_same_prefix.c

#include <stdio.h>
typedef struct { int  i1; float f1; char c1; double d1; } 
  st1;
typedef struct { int  i2; float f2; double d2; char c2; } 
  st2;
int main() {
  st1 s1 = {.i1 = 1, .f1 = 1.0, .c1 = 'a', .d1 = 1.0};
  st2 *p2 = (st2 *) (&s1);// is this free of undef.beh.?
  p2->f2=2.0;             // and this?
  printf("s1.f1=%f  p2->f2=%f\n",s1.f1,p2->f2);
}

ISO does not specify semantics with strict aliasing disabled, and effective types arguably forbid these.

But for de facto C (especially though not always with -fno-strict-aliasing), it seems this is a common idiom that must be supported.

For it to work in implementations,

  1. the offsets of f1 and f2 have to be equal,
  2. the code emitted by the compiler for the f2 access has to be independent of the subsequent members of the structure (in particular, it cannot use an over-wide write that would only hit padding in one structure but hit data in the other). Or we need a more elaborate condition: the last member of the common prefix is only writable if it is aligned and sized such that wide writes will never be used (an implementation-defined property).
  3. either the alignments of st1 and st2 have to be equal or the code emitted by the compiler for the f2 access has to be independent of the structure alignment (we imagine that the latter holds in practice), and
  4. the compiler has to not be doing some alias analysis that assumes that it is illegal.

For the offsets, the standard implies that within the scope of each compilation, there is a fixed layout for the members of each structure, and that that is available to the programmer via offsetof(type,member-designator), "the offset in bytes, to the structure member (designated by member-designator), from the beginning of its structure (designated by type)" (7.19p3, in Common definitions, <stddef.h>), and via the the 6.5.3.4 sizeof and _Alignof operators. The C standard provides only weak constraints for these layout values (e.g. that they increase along a structure, per 6.7.2.1p15); it does not guarantee that st1 and st2 have the same offsets for f1 and f2. DR074CR confirms this.

In practice, however, these values are typically completely determined by the ABI, with constant sizes and alignments for the fundamental types and the algorithm "Each member is assigned to the lowest available offset with the appropriate alignment." for structures, from the x86-64 Unix ABI. There is similar text for Power, MIPS, and Visual Studio. The ARM ABI is an exception in that it does not clearly state this, but the wording suggests that the writers may well have had the same algorithm in mind. This algorithm will guarantee that the offsets are equal.

W.r.t. the (hypothetical) use of wide writes, the situation is unclear to us.

We should recall also that there are various compiler flags and pragmas to control packing, so it can (and does) happen that the same type (and code manipulating it) is compiled with different packing in different compilation units, relying on the programmer to not intermix them.
We currently ignore this possibility but it should be relatively straightforward to add the packing flags to the structure name used within the semantics.

Without -fno-strict-aliasing, if one wanted to argue that this example should be illegal (e.g. to license an otherwise-unsound analysis), in terms of the effective types of 6.5p{6,7}: The key question here is whether one considers the effective type of a structure member to be simply the type of the member itself or also to involve the structure type that it is part of, which the text (with its ambiguous use of "object") leaves unclear. In the former case the example would be allowed, while in the latter it would not.

2.7.2 Q40 Can one read from the initial part of a union of structures sharing a common initial sequence via any union member (if the union type is visible)?

Next we have 6.5.2.3p6, which unambiguously licenses reading from a common initial sequence of two structure types which are members of a union type declaration: "One special guarantee is made in order to simplify the use of unions: if a union contains several structures that share a common initial sequence (see below), and if the union object currently contains one of these structures, it is permitted to inspect the common initial part of any of them anywhere that a declaration of the completed type of the union is visible. Two structures share a common initial sequence if corresponding members have compatible types (and, for bit-fields, the same widths) for a sequence of one or more initial members."

Example read_union_same_prefix_visible.c

#include <stdio.h>
typedef struct { int  i1; float f1; char c1; } st1;
typedef struct { int  i2; float f2; double d2; } st2;
typedef union { st1 m1; st2 m2; } un;
int main() {
  un u = {.m1 = {.i1 = 1, .f1 = 1.0, .c1 = 'a'}};
  int i = u.m2.i2; // is this free of undef.beh.?
  printf("i=%i\n",i);
}

2.7.3 Q41 Is writing to the initial part of a union of structures sharing a common initial sequence allowed via any union member (if the union type is visible)?

We presume the above is restricted to reading to avoid the case in which a write to one structure type might overwrite what is padding there but not padding in the other structure type.

Example write_union_same_prefix_visible.c

#include <stdio.h>
typedef struct { int  i1; float f1; char c1; } st1;
typedef struct { int  i2; float f2; double d2; } st2;
typedef union { st1 m1; st2 m2; } un;
int main() {
  un u = {.m1 = {.i1 = 1, .f1 = 1.0, .c1 = 'a'}};
  u.m2.i2 = 2; // is this free of undef.beh.?
  printf("u.m1.i1=%i  u.m2.i2=%i\n",u.m1.i1,u.m2.i2);
}

For the de facto semantics, we really need a better understanding of when compilers might do wide writes. For the moment, we tentatively propose to use the "more elaborate condition" of Q39 and permit writing in such cases.

2.7.4 Q42 Is type punning by writing and reading different union members allowed (if the lvalue is syntactically obvious)?

Finally, in some cases subsuming the previous clause, 6.5.2.3p3 and Footnote 95 explicitly license much more general type punning for union members, allowing the representation of one member to be reinterpreted as another member. 6.5.2.3p3 "A postfix expression followed by the . operator and an identifier designates a member of a structure or union object. The value is that of the named member (95) and is an lvalue if the first expression is an lvalue. If the first expression has qualified type, the result has the so-qualified version of the type of the designated member."

Footnote 95) "If the member used to read the contents of a union object is not the same as the member last used to store a value in the object, the appropriate part of the object representation of the value is reinterpreted as an object representation in the new type as described in 6.2.6 (a process sometimes called "type punning"). This might be a trap representation."

The GCC documentation suggests that for this to work the union must be somehow syntactically visible in the access, in the construction of the lvalue, or in other words that GCC pays attention to more of the lvalue than just the lvalue type (at least with -fstrict-aliasing; without that, it's not clear):

Example union_punning_gcc_1.c

// adapted from GCC docs
#include <stdio.h>
union a_union {
  int i;
  double d;
};
int main() {
  union a_union t;
  t.d = 3.1415;
  int j = t.i; // is this defined behaviour?
  printf("j=%d\n",j);
}

"The practice of reading from a different union member than the one most recently written to (called "type-punning") is common. Even with -fstrict-aliasing, type-punning is allowed, provided the memory is accessed through the union type. So, the code above works as expected. See Structures unions enumerations and bit-fields implementation. However, this code might not:"

Example union_punning_gcc_2.c

// adapted from GCC docs
#include <stdio.h>
union a_union {
  int i;
  double d;
};
int main() {
  union a_union t;
  int* ip;
  t.d = 3.1415;
  ip = &t.i;   // is this defined behaviour?
  int j = *ip; // is this defined behaviour?
  printf("j=%d\n",j);
}

See also the LLVM mailing list thread on the same topic. As Chisnall writes (private communication): "The crux of the issue is the text in the spec that (possibly, depending on how you read it), appears to say that if you have a union of X and Y then any pointer to X may alias a pointer to Y. This is not something that makes compilers happy: if you have a compilation unit with a union of int and float then any int and float pointers may alias in any compilation units, meaning that you can't rely on type information at all for alias analysis, but appears to be something that some real code depends on."

See for example this "If you use an explicit union access, it assumes they alias, otherwise, all bets are off. Note: As you all know, I have really no dog in this fight, nor am i a language lawyer. Among other things, i'm an aliasing guy. I just do the edge of what the language lawyers tell me is allowed :)" and this "FWIW: I'm perfectly fine with this, as it lets me optimize more. :)" [Daniel Berlin]

This (and the later struct padding) means that a de facto semantics has to pay attention to the lvalue construction, not merely its type. The GCC documentation suggests that only the local lvalue expression is relevant, however.

Again from the GCC documentation: "Similarly, access by taking the address, casting the resulting pointer and dereferencing the result has undefined behavior, even if the cast uses a union type, e.g.:"

Example union_punning_gcc_3.c

// adapted from GCC docs
#include <stdio.h>
union a_union {
  int i;
  double d;
};
int main() {
  double d = 3.1415;
  int j = ((union a_union * ) &d)->i;
  printf("j=%d\n",j);
}

For reference: a GCC mailing list post observes that upcasts from int to union can go wrong in practice, and another says that GCC conforms to TC3 with respect to type punning through union accesses.

The conclusion for the de facto semantics here is not completely clear. Probably it should allow such accesses where the lvalue makes it "obvious" that type punning is intended.

2.8 Pointer lifetime end

After the end of the lifetime of an object, one can ask whether pointers to that object retain their values, or, in more detail, whether:

  1. they can be compared (with == and !=) against other pointers,
  2. they can be compared (with <, >, <=, or >=) against other pointers,
  3. their representation bytes can be inspected and still contain their address values,
  4. pointer arithmetic and member offset calculations can be performed,
  5. they can be used to access a newer object that happens to be allocated at the same address, or
  6. they can be used to access the memory that was used for the lifetime-ended object.

(For an object of thread storage duration, the lifetime ends at the termination of the thread (6.2.4p4). For an object of automatic storage duration (leaving aside those that "have a variable length array type" for the moment), the lifetime ends when "execution of that block ends in any way" (6.2.4p6). For an object of allocated storage duration, the lifetime ends at the deallocation of an associated free or realloc call (7.22.3p1).)

The ISO standard is clear that these are not allowed in a useful way: 6.2.4 Storage durations of objects says (6.4.2p2) "If an object is referred to outside of its lifetime, the behavior is undefined. The value of a pointer becomes indeterminate when the object it points to (or just past) reaches the end of its lifetime." % More precisely, the first sentence makes 6 and 5 undefined behaviour. The second sentence means that 1, 2, 3, and 4 are not guaranteed to have useful results, but (in our reading, and in the absence of trap representations) the standard text does not make these operations undefined behaviour.
Other authors differ on this point.

This side-effect of lifetime end on all pointer values that point to the object, wherever they may be in the abstract-machine state, is a highly unusual aspect of C when compared with other programming language definitions.

Note that there is no analogue of this *lifetime-end zap" in the standard text for pointers to objects stored within a malloc'd region when those objects are overwritten (with a strong update) with something of a different type; the lifetime end zap is not sufficient to maintain the invariant that all extant pointer values point to something live of the appropriate type.

In practice the situation is less clear:

  1. some debugging environments null out the pointer being freed (though presumably not other pointers to the same object)
  2. one respondent notes "After a pointer is freed, its value is undefined. A fairly common optimisation is to reuse the stack slot used for a pointer in between it being freed and it having a defined value assigned to it." though it is not clear whether this actually happens.

On the other hand, several respondents suggest that checking equality (with == or !=) against a pointer to an object whose lifetime has ended is used and is supported by implementations. One remarks that whether the object has gone out of scope or been free'd may be significant here, and so we give an example below for each.

In a TrustInSoft blog post, Julian Cretin gives examples showing GCC giving surprising results for comparisons between lifetime-ended pointers. He argues that those pointers have indeterminate values and hence that any uses of them, even in a == comparison, give undefined behaviour. The first is clear in the ISO standard; the second is not, at least in our reading - especially in implementations where there are no trap representations at pointer types. The behaviour he observes for pointer comparison could also be explained by the semantics we envision that nondeterministically takes pointer provenance into account, without requiring an appeal to undefined behaviour. The behaviour of the corresponding integers (cast from pointers to uintptr_t is less clear, but that could arguably be a compiler bug.

2.8.1 Q43 Can one inspect the value, (e.g. by testing equality with ==) of a pointer to an object whose lifetime has ended (either at a free() or block exit)?

Example pointer_comparison_eq_zombie_1.c

#include <stdio.h>
#include <stdlib.h>
int main() {
  int i=0;
  int *pj = (int *)(malloc(sizeof(int))); 
  *pj=1;
  printf("(&i==pj)=%s\n",(&i==pj)?"true":"false");
  free(pj);
  printf("(&i==pj)=%s\n",(&i==pj)?"true":"false");
  // is the == comparison above defined behaviour?
  return 0;
}

Here the comparison against pj after the free() is undefined behaviour according to the ISO standard. GCC -O2 gives a misleading warning about the free() itself (the warning goes away if one omits either printf() or with -O0); that might be a GCC bug.

One could construct similar examples for rest of the first four items above (relational comparison, access to representation bytes, and pointer arithmetic). We do not expect the last two of the six (access to newly allocated objects or to now-deallocated memory) are used in practice, at least in non-malicious code.

The de facto semantics is thus debatable, and perhaps should have an explicit switch between the two options. We can see two ways to model the ISO standard ("pointer lifetime end zap") semantics, observationally equivalent but technically rather different:

  1. do a lifetime check at every usage (not just every access) of a pointer value (or its representation bytes), adding a new action to the concurrency model and checking that it is happens-before-live, or
  2. on each deallocation, finding all writes in the abstract-machine state that contain that pointer value and that are not subsumed by a coherence-later write, and for each synthesise a new write of an unspecified (or indeterminate) value.

One must also consider how this relates to pointer values (or bare provenance IDs) occuring within provenance-tracking data, and to integers that may later be cast to a since-deallocated pointer value. Presumably the latter should be left alone at lifetime end, and old provenance IDs can just be left in situ.

2.8.2 Q44 Is the dynamic reuse of allocation addresses permitted?

Example compcertTSO-2.c

#include <stdio.h>
#include <inttypes.h>
uintptr_t f() { 
  int a; 
  return (uintptr_t)&a; }
uintptr_t g() { 
  int a; 
  return (uintptr_t)&a; }
int main() { 
  _Bool b = (f() == g()); // can this be true?
  printf("(f()==g())=%s\n",b?"true":"false"); 
}

This example based on one from CompCertTSO. This version casts to uintptr_t to make the out-of-lifetime == comparison permitted (at least w.r.t. our reading of ISO), though GCC 4.8 -O2 still warns that the functions return addresses of local variables. One could write analogous tests using other constructs that expose the concrete address of a pointer value, e.g. casting to an integer type, examining the pointer representation bytes, or using printf with %p. The CompCertTSO example compcertTSO-1.cuses==` on the pointer values directly because (as in CompCert 1.5) none of those are supported there, while CompCertTSO does allow that comparison.

A de facto semantics should allow this, to accommodate reasonable implementation behaviour.

2.9 Invalid Accesses

In the ISO standard, reads and writes to invalid pointers give undefined behaviour, and likewise in typical implementations.
For a conventional C implementation, undefined behaviour for general invalid writes is essentially forced, given that they might (e.g.) write over return addresses on the stack.
But accesses to NULL pointers and reads from an invalid pointer could conceivably be strengthened, as in the following two questions.

2.9.1 Q45 Can accesses via a null pointer be assumed to give runtime errors, rather than give rise to undefined behaviour?

Example null_pointer_4.c

#include <stdio.h>
int main() {
  int x;
  // is this guaranteed to trap (rather than be
  // undefined behaviour)?
  x = *(int*)NULL;
  printf("x=%i\n",x);
}

This is inspired by the fifth example of [Wang et al.].

For de facto C, the answer is no.

2.9.2 Q46 Can reads via invalid pointers be assumed to give runtime errors or unspecified values, rather than undefined behaviour?

Example read_via_invalid_1.c

#include <stdio.h>
int main() {
  int x;
  // is this free of undefined behaviour?
  x = *(int*)0x654321;
  printf("x=%i\n",x);
}

This is from the Friendly C proposal (Point 4) by Cuoq et al.
Here too the de facto C answer is no. For such a semantics one would nonetheless want to identify a (different, not expressed in terms of undefined behaviour) sense in which such reads indicate programmer errors.