Footguns

It's done in the compiler sources. The same way as with memcpy. You can even disable it the exact same way, by specifying -fno-builtin-realloc. And then, of course, everything works.

That's MSVC. Don't mix them. Clang, at least, looks on the function name…

Indeed. But you would be naive you C compiler developers agreed. When I talked about this I was assured that it's absolutely not possible to do that. And if object is actually moved you can not traverse it and update insider pointers, too.

Instead you have to convert all insider pointers into indexes, store these indexes somewhere (but you can use unions to save space so could just copy then into uintptr_t which resides in the exact same place) and then turn indexes back into pointers (properly adjusted now).

And no, it's not a joke.

Irrelevant (according to compiler developers). Existing code must be fixed as described above. The fact that it may force it to become slower (and much slower in some cases) is irrelevant, again. Unless it's part of some well-known benchmark, of course.

C standard says something which is, as Linus would would say, is “total and utter crap”. On one hand it says this:

Two pointers compare equal if and only if both are null pointers, both are pointers to the same object (including a pointer to an object and a subobject at its beginning) or function,both are pointers to one past the last element of the same array object, or one is a pointer to one past the end of one array object and the other is a pointer to the start of a different array object that happens to immediately follow the first array object in the address space¹⁰⁹).

But if you notice there's a footnote ¹⁰⁹). It says this:

Two objects may be adjacent in memory because they are adjacent elements of a larger array oradjacent members of a structure with no padding between them, or because the implementation choseto place them so, even though they are unrelated. If prior invalid pointer operations (such as accesses outside array bounds) produced undefined behavior, subsequent comparisons also produce undefined behavior.

If you read it carefully you will realize that since accessing one-past-end-element is forbidden it also means that what the main body of the standard says is just not possible… but then why is it there?

The answer: C compiler developers got an approval from C standards committee to add what they call “pointer provenance” to the C standard but since in 15 years they still were unable to invent sane rules which people would be able to understand… they only managed to add that one tiny footnote.

And they were unable to put anything else to the standard because C committee (unlike C++ committee) actually cares about correctness and just doesn't want to add complete an utter garbage to the standard (you can read about why it's complete and utter garbage here). > The claim that comparing these two pointers can possibly be illegal makes no sense whatsoever IMHO, and I very much doubt that that was the intent of the C standards people. They might be misguided but they're not *that* stupid.

True. They resisted more-or-less succesfully with both C11 and C18. But C/C++ compiler developers are that stupid. This now they are trying again.

And what is their reasoning, pray tell? Why, of course: existing compilers already rely on the properties and thus standard have to be changed!

I would have been somewhat sympathetic if the exact same prompt by C/C++ users WRT other controversial parts of the standard would not have been meet with derision and prompts to burn the heretics rewrite all the programs.

No. It was neither consistent nor complete. That's why they weren't able to add pointer provenance neither to C11 nor to C18. The latest attempt is here. Please note the dates.

Nope. Not even close. Kinda-sorta coherent models were developed (here is one attempt) — but they don't match what the compilers are actually doing (the new model requires a handful of problematic IR-level optimizations to be removed, but it also supports the addition of new optimizations that were not previously legal is pretty telling, isn't it?) and, more importantly, it's not clear why they are supposed to be applicable to C89 or even C99 programs.

It haven't done that yet. Pointer provenance is not a thing — even in C18 version of C standard.

Good for whom? Compiler writers? Maybe. It's bad for C users, definitely, but since they couldn't present anything better they had only one option: accept the standard or live without a compiler.

But now it looks as if accepting standard is not enough. That is the problem.

When the story was presented as “Semi-portable C” vs “Standard C” this sounded like a sensible compromise: sure standard maybe harsh is some places, but hey, it's a standard!

Now, then we know that compiler developers don't feel themselves restricted by requirements of the standard the question arises: why then C users demands to change the standard are ignored? Hmm?

What kind of reality?

Yes. Compilers are broken. And now we even know there broken not as an accident. So?

Indeed. Instead of throwing away premature and unfinished ideas about how the so-called “pointer provenance” have to work they acquiesced to compiler writers demands (or, more likely, an ultimatum, but I wasn't there and couldn't say for sure). Yet instead of saying that standard is wrong they just “came to a number of conclusions as to what it would be desirable for the Standard to mean”. IOW: they proposed that compiler developer would start developing some sane set of rules for the C users to follow.

Instead of doing that compiler developers went on to invent unproven, buggy and half-specified schemes which were, as they claim, permitted by DR260. Indeed even latest proposal from last year explicitly says DR260 CR has never been incorporated in the standard text and lament about the sad fact that DR260 only explicitly permits track the origins of a bit-pattern and [...] may also treat pointers based on different origins as distinct even though they are bitwise identical

Which basically means: output from that realloc example is still buggy. Even if you would incorporate DR260 resolution into the standard — you still couldn't get output 1 2 in question. The most you can get is elimination of comparison and the whole code which does operations after that branch.

Now, you may try to argue that compiler was clever enough to notice that the only situation where p is equal to q and both are valid… nope, no cigar

Yes, but at least there some memory model was actually accepted and added to the text of standard. Nothing like that happened with DR260.

And I would argue that “pointer provenance” was a very bad idea and shouldn't brought to the realms of C as unconditional property. Previous proposal at least tried to acknowledged that and proposed two modes, test macros and so on.

But it was rejected. Most likely because it was “too much work” to implement.

So… it's too much work for the compiler writers to implement -fno-provenance switch yet reviewing and rewriting billions lines of code to make them compliant with new “optimizations” (which break code which was acceptable for decades) is not “too much work”? WTH?

Why is not not the same? On the contrary: it is the same. I have verified that.

And I'm talking about explicit mention about the possibility of in pointer being the same as out pointer. Why is it there? What can one do with that information? How can I use it?

I assume that standard writers weren't insane and haven't been adding some notes just to make standard bigger and more complex. So what's the reason to include that note as part of the interface?

But these are just wet dreams of C/C++ compiler developers. Right now standard doesn't allow for the possibility of two pointers being equal and comparable and yet them being different.

One concession which standard did in C11 was to declare some pointer comparisons as being UB (e.g. you are not supposed to compare one-past-the-end-pointer to “normal” pointer… that comparison is UB).

Except to claim this they would need to show at least one real-world example where it have improved performance. So far nothing was shown thus we may safely assume all that code was added specifically to break otherwise good programs and there are no other reason.

I think we are talking past each other. When I'm asking about “optimization” I'm not talking about realloc implementation.

I know when realloc can leave things untouched and why. That's not the interesting case.

The interesting case is an “optimization” enabled with -fbuiltin-realloc. The one which forbids user to compare p and q and says that you can't use pointers to the “old” realloced object. What does that one improve?

Precisely. And now I can't just do a simple q == p check to see if object is unmoved. I have to, basically, always do p = q assignment (if q is not nullptr) but what's more important: I can't keep pointers to “old” realloced object anywhere. If I have some other pointers (besides p) and, especially, if I have “internal” pointers (which point to the inside of that object) then I have to turn them all into indexes and then traverse everything after realloc again and turn these indexes back to pointers!

Now, I can easily imagine where such “compiler appease dance” can introduce slowdowns (even if realloc is clever and allocates exponentially for bigger buffers, etc).

But where the heck that dance imposed on me by C compiler developers helps? What kind of program? What benchmark? Can you show me anything at all where -fbuiltin-realloc is faster than -fno-builtin-realloc?

It has everything to do with the concept of provenance. What -fbuiltin-realloc option does is tells the compiler: “if someone does q = realloc(p, …) then you can assume that p and q have different provenance, they could never alias (not even after explicit p == q check) and you can optimize on basis of that”.

The one thing (and very big thing for me): WTH can you use that assertion for? What kind of code should we observe for that rule to speed up anything?

Casting itself is free. But because new “optimized” rules demand that you find and convert all pointers before you call realloc you would need additional code which would traverse additional data structures and scans all these pointers.

And after realloc you have to traverse all these data structures again and turn indexes back into pointers.

Not only that adds additional code which complicates logic, there are no guarantee that this code would be optimized away by the compiler (and in some cases, when external functions are involved, it couldn't be removed).

It's not the same. Version with -fbuiltin-realloc does this:

 mov esi,0x1
 mov edx,0x2
 xor eax,eax
 call 401030 <printf@plt>

Version with -fno-builtin-realloc does this:

 mov esi,0x2
 mov edx,0x2
 xor eax,eax
 call 401030 <printf@plt>

But lots of people claim it's “an optimization”. It's supposed to “improve” something. So… what, where and how does it improve?

If that's a paranoia then surely it would be easy for you to show something which benefits from -fbuiltin-realloc. Anything at all, I'm not that picky, if you don't have a real-world app I can even accept some contrived artificial example for the start.

struct Context { int initial; };

int *test(Context *ctx, int *p, int n) {
    int *q = (int *)realloc(p, n * sizeof(int));
    for (int i = 0; i < n; ++i)
        q[i] = ctx->initial + 1;
    return q;
}