realloc(), lifetime and UB

Question

There's a recent CppCon2016 talk My Little Optimizer: Undefined Behavior is Magic, which shows the following code (26 mins into the talk). I beautified it a bit:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
  int* p = malloc(sizeof(int));
  int* q = realloc(p, sizeof(int));
  *p = 1;
  *q = 2;
  if (p == q)
  {
    printf("%d %d\n", *p, *q);
  }
  return 0;
}

The code has undefined behavior (p becomes invalid after realloc() even if realloc() returns the same pointer) and when compiled may print not only "2 2", but also "1 2".

What about a slightly modified version of the code?:

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

int main(void)
{
  int* p = malloc(sizeof(int));
  uintptr_t ap = (uintptr_t)p;
  int* q = realloc(p, sizeof(int));
  *(int*)ap = 1;
  *q = 2;
  if ((int*)ap == q)
  {
    printf("%d %d\n", *(int*)ap, *q);
  }
  return 0;
}

Why can I still get "1 2" printed? Does the integer variable ap also somehow become invalid or "tainted"? If so, what's the logic here? Shouldn't ap become "decoupled" from p?

P.S. Added the C++ tag back. This code can be trivially rewritten as C++ and the same question applies in C++ as well. I'm interested in both C and C++.

Answer 1

As posted, in C, the code has undefined behaviour because realloc may return a different block of memory. In this case, *(int *)ap will form an invalid pointer.

A more interesting question would be what happens if we change the code so that it attempts to only proceed if the realloc didn't change the block:

int* p = malloc(sizeof(int));
uintptr_t ap = (uintptr_t)p;
int* q = realloc(p, sizeof(int));

if ( (uintptr_t)q == ap )
{
    *(int*)ap = 1;
    // ...
}

For C2X there is a proposal N2090 to specify pointer provenance when passed through integer types.

In the current C standard, there are some rules relating to pointer provenance but it does not say what happens to the provenance when the pointer is passed through integer types and back.

Under this proposal, my code would still be undefined behaviour: ap gets the same provenance token as p had, which becomes an invalid token when the block is freed. (int *)ap is then using a pointer with an invalid provenance.

The proposal seeks to avoid pointer provenance being "hacked around" by intermediate operations with uintptr_t and so on. In this case it specifies that (int *)ap has exactly the same behaviour as p. (Which is undefined even if the block didn't move, since p is an invalid pointer after the realloc whether or not it physically moved the block). In the C abstract machine, the intent is that it's not possible to tell whether or not the block was moved by realloc.

Background on pointer provenance

"Pointer provenance" means an association between pointer values and the memory block that they point to. If a pointer value points to an object, then other pointer values derived from that value (e.g. by pointer arithmetic) must stay within the bounds of that object.

(Of course, a pointer variable may be reassigned to point to a different object - and thereby gain a new provenance - that's not what we're talking about).

This is not something that appears in a compiled executable, but is something that compilers may track during compilation, in order to perform optimizations. Two pointers with different provenances might have the same memory representation (for example, p and q in the case that the implementation used the same physical memory block).

A simple example of why pointer provenance provides useful optimization opportunities would be the following snippet:

char p[8];
int q = 5;

*(p+10) = 123;
printf("%d\n", q);

The idea of provenance allows the optimizer to register undefined behaviour on the code p + 10, so it could translate this snippet to puts("5") for example, even if q happens to immediately follow p in memory. (Aside - I wonder if DJ Bernstein's boringcc compiler would in fact not be able to perform this optimization).

The existing rules about pointer bounds checking (C11 6.5.6/8) do cover this case already, but in more complicated cases they are unclear, hence the N2090 proposal. For example, if ( p + 8 == (void *)&q ) *(char *)((uintptr_t)p + 10) = 123; would, under N2090, still be undefined behaviour.

Answer 2

The code as given in the original question invokes Undefined Behavior, so a compiler is entitled to do whatever it wants. Some background on that form of Undefined Behavior is given below.

Clang would behave oddly, however, given code which is similar to yours but does not invoke Undefined Behavior. Unless one regards certain language in the Standard as meaningless, clang appears to be non-conforming in this regard. Some people would like to change the Standard to make the following invoke UB, thus justifying clang's behavior, but I would regard such proposals as being fundamentally wrongheaded.

#include <stddef.h>
#include <stdlib.h>
#include <stdint.h>

uintptr_t gap,gaq;
int test(void)
{
  int x=0;
  uint8_t *p = calloc(4,1);
  uintptr_t ap = (uintptr_t)p;
  uint8_t *q = realloc(p,4);
  // p is no longer valid after this, but ap still holds some number.
  uintptr_t aq = (uintptr_t)q;
  *q=1;
  if (ap == aq)
  {
    x=256;
    // Nothing in the Standard would say that the result of casting a
    // uintptr_t to a pointer is affected by anything other than the
    // numerical value of the uintptr_t in question.  If aq happened
    // to equal e.g. 8675309, then casting any expression equal to
    // 8675309 into an int* should yield the same value as casting aq;
    // since were here, we'd know that ap was also equal to 8675309, and
    // thus that (int*)ap is equivalent to (int*)aq.
    *(uint8_t*)ap = 123;
  }
  gap=ap;
  gaq=aq;
  return *q+x;
}

Clang 3.9.0 invoked on godbolt with options -xc -O3 -pedantic generates code which will either return 1 or 257 depending upon whether ap and aq compare equal, even though nothing in the present Standard would allow ap to be treated any differently from any other variable of type uintptr_t which happens to hold the same value. The way the code is written, because no outside code is ever entitled to observe p, it would have been permissible for the compiler to generate code that set ap to any arbitrary value which doesn't equal aq and then ignored the comparison altogether, but nothing in the Standard would allow an implementation to do anything other than write the same value to gap and gaq and return 379 (123+256) or write different values to gap and gaq and return 1.

Background on the UB-ness of comparing an invalid pointer to a valid one

On some processors, attempting to load a pointer into a register will cause the processor to do some validation regarding its validity. On the 80286, for example, every pointer includes a segment selector and an offset, and loading a segment selector will cause the processor to fetch some information from a table of valid segments.

Some C implementations will load pointers into registers whenever anything is done with them, whether or not they will be used to access memory, and some C implementations for the 80286 might invalidate a segment descriptor if the only thing in the corresponding segment is a block of memory that has been freed. The authors of the C Standard did not wish to require C implementations to expend effort avoiding register loads in cases where pointers are not dereferenced, nor did they wish to require that implementations maintain valid segment descriptors for pointers that had been freed. The simplest way to imposing either requirement was to refrain from requiring anything in cases where code does anything that could free a pointer and then does anything that could cause the pointer to be loaded into a register.

There are many implementations where loading a pointer into a register would be safe even if the storage occupied thereby had been freed, or which would avoid "trappable" register loads in cases where a pointer was not going to be dereferenced (loading pointers into general-purpose registers for comparison would be cheaper than loading them into segment registers and transferring them to general-purpose registers for comparison), and I see no reason to believe that the authors of the Standard intended that code which targeted exclusively implementations implementations where either of the above should not be able to exploit techniques like:

void do_realloc(int new_size)
{
  void *new_ptr = realloc(old_ptr, new_size);
  if (!new_ptr) fatal_error;
  if (new_ptr != old_pointer)
    update_pointers();
}

in situations where the realloc was very likely to succeed "in-place" (e.g. because the block was being shrunk) and where it would be possible--but expensive--to regenerate pointers to things within the allocated storage if the object ended up being moved. Nonetheless, because the Standard does not require any implementations to support such techniques even in cases where doing so would cost nothing, some implementations (even those where such support would cost nothing) go out of their way not to provide it.