Pointers Are Complicated II, or: We need better language specs

46

Whether or not a program is broken is defined by the specification, not by "do real programs do this". The specification has no objections with this program.

Nothing an implementation does in response to an attempt to dereference a round-tripped pointer could render it non-conforming. An cases where two equal pointers could exist which would be usable only to access disjoint sets of objects, a capricious but conforming implementation could make any conversion of a round-tripped pointer yield a pointer which would compare equal to the original, but would not be usable to access any of the same objects. So in that sense, almost all programs that make use of integer-to-pointer conversions would be "broken" unless they are only intended for use on implementations that uphold guarantees stronger than what the Standard requires.

That having been said, if the example were changed slightly:

#include <stdint.h>
char x[1], y[1] = {0};
int test(unsigned char *p)
{
    uintptr_t ip = (uintptr_t)p;
    uintptr_t iq = (uintptr_t)(x+1);
    y[0] = 123;
    if (iq == ip) {
      *p = 45;
    }
    return y[0];
}

Here the code never dereferences the round-tripped pointer, but clang still processes the code nonsensically.

What's going on is similar to the way clang and gcc treat some goofy corner cases in the Standard involving restrict-qualified pointers, which would cause the C Standard would define the behavior of a construct of the form (someFlag && a || b) && doSomething) when a is 0 (meaning someFlag would be evaluated but doSomething would be unconditionally skipped) or when b is 1 (meaning someFlag would be evaluated but doSomething would be unconditionally executed), and yet not define program behavior in cases where execution of doSomething is conditioned on someFlag. I can't think of any reasonable abstraction model in which the reason for a compiler to decide to execute or skip a piece of code would play any role in determining whether its behavior is defined, but that's how the Standard specifies the behavior of restrict, and clang and LLVM are simply applying the same logic elsewhere.

47

C or C++? It seems C standard indeed says roundtripping is implementation-defined.

But the C++ standard (of which a draft is available) says:

It looks like the C++ standard does make round-tripping pointers through integers via reinterpret_cast a valid operation. It also does seem that a compiled application formatting the HDD in response to dereferencing a round-tripped pointer would in fact render a C++ compiler which produced such a compilation non-conformant.

What is your point though? My concern is that this topic ongoing may be putting too high a demand on Ralf's time..

In fact I think when a is 0 but b is 1 doSomething should get evaluated.

2 Likes
48

C or C++? It seems C standard indeed says roundtripping is implementation-defined.

Implementations may at their leisure define round-tripping in useful or useless fashion. The only behavioral requirement given in the Standard is that a round-tripped pointer must compare equal to the original. Is there anything in the Standard that would forbid an implementation from specifying that casting 42 to a char const* will yield a pointer to the string "WHAT DO YOU GET WHEN YOU MULTIPLY SIX BY NINE", but casting any other integer value will yield a pointer value which, even if it would compare equal to other pointers in some cases (including all where the Standard would mandate such behavior), cannot be dereferenced to access anything?

In fact I think when a is 0 but b is 1 doSomething should get evaluated.

Sorry, I should have said when both a and b are zero, but my point is that while one would expect that an the behavior of any particular execution of x && y would always be equivalent to either "execute x and then execute y" or "execute x and don't execute y", the way clang and gcc interpret the Standard means that such an expression could behave in ways which don't match either of the above. If one wants to allow such behavior, it could be be accommodated by an abstraction model which allows transformations based upon program structure, but I don't see any way to accommodate such behavior in an abstraction model that's based purely upon sequential program execution.

49

I think there is in C++ standard. LLVM being used to compile both C and C++ apparently needs to support a "union" of both standards.

50

I don't these these details of the C/C++ standard really matter here. The blog post is about the semantics of LLVM IR, and this is a Rust forum, so the rather vague wording of C/C++ around ptr-int-roundtrips is essentially irrelevant except as a way to maybe better understand the semantics of LLVM IR.

It is quite clear that a semantics where round-tripping the pointer doesn't work is useless. So I really have no idea what the point of the discussion here is currently. Is it just that the C/C++ standard is imprecise and vague? I agree, but... so what? None of the posts seem to even discuss the issue that the blog post brings up, so this all seems very far off-topic.

If you want to continue the discussion, please start with a clear problem statement.

I do not have the faintest idea what you are talking about here. If you have a concrete example in mind, please spell it out. There is no restrict-qualified pointer anywhere in the short bits of code you wrote here, so I do not see the connection.

5 Likes
51

"Also, real programs use one-past-the-end ptrs all the time (for iteration loops)."

AFAICT, this would require runtime evaluation of pointer equality so it wouldn't affect the static optimization being discussed here.

I do understand that while your initial example is contrived, useful code could theoretically have a similar effect. However, I can't imagine what that useful code would actually look like. I could certainly be persuaded that this is a real problem if you were to present a plausible example of this issue in useful code. So far I can't see it, but I'll allow for the possibility of that being my ignorance.

52

The optimizations just showcase certain features of the underlying operational semantics / Abstract Machine. So just because usually the ptr equality needs to be runtime-evaluated, doesn't make it any easier to solve this problem.

What would solve the problem is to disallow casting one-past-the-end ptrs to integers. But in Rust that's not an option as ptr-to-int casts are a safe operation.

53

The ability to convert between integers and pointers would be useless if they couldn't be round-tripped meaningfully in ways that would support at least the common use cases. It may be sometimes be useful for an implementation to support round-tripping of pointers in some cases even if would be some situations where such round-tripping wouldn't work as expected. I think the intention of the C Standard was that implementations would process the conversions meaningfully when practical, but they didn't want to brand as non-conforming implementations where some weird contrived corner cases might fail. I wouldn't be surprised if at least one of the Committee members responsible for the C Standard's failure to specify that round-tripped pointers should actually be useful, wanted to avoid characterizing optimizations like the one in your original post "incorrect". If the original program invoked UB, the question of which stage of optimization introduced UB would be moot.

I do not have the faintest idea what you are talking about here. If you have a concrete example in mind, please spell it out. There is no restrict -qualified pointer anywhere in the short bits of code you wrote here, so I do not see the connection.

The basic issue is whether it makes sense to have a language standard forbid any actions within a piece of code which is only executed if certain pointers are in some sense "equal", that would be allowed if the same code were executed unconditionally. The C Standard's definition of restrict, or at least the interpretation shared by clang and gcc, creates such corner cases, and I think that even though your doesn't use restrict, I think the compiler is attempting to broadly apply logic that assumes that if P can't alias some restrict-qualified pointer Q, and within a block of code some pointer R is known to be equal to P, then R can't alias Q either even if it's formed directly from Q, but it isn't limiting such logic to situations where Q is restrict-qualified (in your example it obviously isn't).

54

Uh, no. The mechanism the third optimization uses is some variation of memory dependence, which is ultimately based on a function called mayAlias, and, in this case, getUnderlyingObject. Because of the incorrect prior optimizations [1], mayAlias(p + 1, q) returns false because the underlying allocations of both pointers are firmly described, and they are different. So the optimizer concludes that p[1] cannot effect the result returned by q[0]. restrict isn't involved in the slightest.

[1] I believe the current majority opinion in the LLVM community is that it's the second optimization that is wrong, i.e., intoptr(ptrtoint(x)) => x is not a valid transformation. Note that, as RalfJung discusses, there are other potential answers to which transformation was incorrect.

3 Likes
55

This is a theoretical problem only, AFAICT. Is there any real world problem that could arise from this? I can't imagine one. Maybe if there was loop unwinding involved plus iterators checking one past the end? I still don't think this would trigger the issue, because if you were statically unwinding, you wouldn't need to check one past the end. It seems like intentionally deriving an out of bounds pointer is the only way to trigger this, so I remain unconvinced.

56

LLVM does have a couple ways of producing inttoptr where the original source code had no such casts--as I mentioned earlier (maybe it was moved to the other thread), strictly speaking every load/store of a pointer value implicitly acts as a inttoptr/ptrtoint, respectively, and SROA can make these implicit instructions explicit.

57

One of the primary goals of this exercise is to use proof assistants to check that the language definition and the desired optimizations for it are self-consistent, because that makes it possible to design subtle compiler passes and unsafe code with more confidence.

So the existence of this sort of edge case is a real-world problem, even if production code isn't hit by it, because the sort of constraint solvers that are employed to check the correctness of MutexGuard will be.

11 Likes
58

Maybe if there was loop unwinding involved plus iterators checking one past the end?

Some linkers have ways of allocating a chunk of memory whose size will be computed at link time or even load time. While the Standard does not specify any means by which a C source file could definitions for

extern char heap_start[], heap_end[];

which were known to identify consecutive regions of storage, thus allowing code to do something like:

char *p = heap_start;
while(p != heap_end)
  *p++ = 0;
heap_size = p - heap_start;

there are some tasks which would require a linker that has such an ability and a C compiler that is agnostic to the possibility that such a thing might occur (rather than actively assuming it cannot). Note that if the objects weren't declared volatile, I would not expect a compiler to allow for the possibility that an access to heap_end[i] might affect heap_start[j], but for a compiler to be suitable for the above tasks, it must refrain from making any inferences about p[i] being incapable of accessing heap_start[j].

If code is known not to rely upon such linker trickery, then it might be useful for a compiler to make the kinds of assumptions being discussed here, so language standards shouldn't necessarily rule them out entirely. On the other hand, there should be a means by which programmers who know more about object placement than the compiler does should be able to safely exploit that knowledge.

2 Likes
59

[1] I believe the current majority opinion in the LLVM community is that it's the second optimization that is wrong, i.e., intoptr(ptrtoint(x)) => x is not a valid transformation. Note that, as RalfJung discusses, there are other potential answers to which transformation was incorrect.

I think the vagueness in the C Standard was intended to allow implementations to transform intToPtr(ptrToInt(x))=>x in cases where their customers would find such transformations useful. I personally doubt there are many situations where customers would find such transformations more useful than a guarantee that they wouldn't occur, but I can imagine a few situations where that might be the case, such as functions that would sometimes need to return numbers and sometimes need to return pointers. Some calling conventions allow uintptr_t values to be returned more efficiently than unions, and if a compiler can in-line a function that returns a uintptr_t and see that it is returning a directly-cast pointer that is known not to alias p, it might be useful to have it ignore the possibility that the returned pointer might alias p.

A much more fundamental problem is the transformation if (p==q) doSomethingWith(p) => if (p==q) doSomethingWith(q). If the original code had been something like:

extern int x[], y[];

uintptr_t test1(int mode, int *p, int index)
{
  if (mode)
    return p[index];
  else
    return (uintptr_t)(p+index);
}
int test(void)
{
  y[0] = 1;
  *(int*)test1(0, x, 1) = 123;
  return y[0];
}

many people wouldn't have batted an eye if a compiler generated code equivalent to:

int test(void)
{
  y[0] = 1;
  x[1] = 123;
  return 1;
}

even if the only situations were test would ever get called would be when x was a single element and y immediately followed it. I would regard such a transform as inappropriate in an implementation intended for tasks involving some kinds of low-level memory management, but wouldn't regard it as generally erroneous outside implementations that claim to be suitable for such tasks.

A more fundamental problem is that clang and gcc both transform if (p==q) doSomethingWith(q); into if (p==q) doSomethingWith(p);.even in cases where p would be incapable of accessing an object which would have clearly been accessible via q. The only situations where the C Standard would allow such a transform to change the accessibility of pointer used by doSomethingWith are when p and/or q are a restrict-qualified pointers. I can't tell whether clang and gcc made the transform because it is sometimes valid, or whether they applied it without caring about whether it's ever valid, but I would think the fact that it sometimes valid should be relevant to the discussion.

PS--I think the C Standard should specify that stdint.h may, whether or not it defines uintptr_t, specify a macro which could either identify the same type as uintptr_t or a type which would be similar but for the fact that a compiler may elide round-trip conversions at its leisure. Functions like the above could thus return that type instead of uintptr_t, and if the type was specified as a macro, user code could safely use:

#ifdef uintoptr_t
#define uintoptr_t uintptr_t
#endif
60

Again, please show some code. I cannot follow what you are saying here. If there's a concrete problem, there should be concrete examples demonstrating them. I'd be interested in seeing those.

I am familiar with plenty of corner cases around restrict and have no idea which one you are referring to here.

(But also, as others said -- note that my example has nothing to do with restrict. Using restrict there is a whole suite of interesting examples to consider because provenance suddenly becomes more more complicated than it is when considering C without restrict. I only scratched the surface of this so far.)

I am convinced that each of these "purely theoretical" issues will inevitably come up in practice. The GCC and LLVM issue trackers contain plenty of examples of miscompilations related to alias analysis, most of which were discovered by people working on real code. The appendix of this paper contains some concrete C and (safe) Rust code that is miscompiled due to this problem. You may consider these examples artifical, but they demonstrate that the issue is "practical enough" to break the safety promise of Rust. Anecdotally, Microsoft once had a problem with a Windows build not booting that they tracked down to this bug, but there's no way to verify this story. It seems realistic to me. If that is not of concern to you, feel free to ignore this entire thread, so that the people that do care can work on fixing these problems. You'll thank us when your million-line Rust codebase works just as expected because other people tracked down the miscompilations that arise when optimizations are applied with not enough care. :wink:

It seems like intentionally deriving an out of bounds pointer is the only way to trigger this, so I remain unconvinced.

Program intentionally derive out-of-bounds pointers all the time, e.g. for every C++-style iteration loop (the end() ptr is out-of-bounds).

6 Likes
61

Yes, this is a bug -- closely related to the one I discussed in my post. Also see this LLVM bugreport.

I don't think this is right. restrict does not affect the behavior of ==, so if the pointers are restrict-qualified, then the transformation is even less correct! For example, the following program is well-defined: [*]

void nasty(restrict int *x, restrict int *y) {
  if (x == y) {
    *x = 0;
    *(y+1) = 1;
  }
  *(y+1) = 1;
}

void main() {
  int array[2] = {0,0};
  nasty(&array[0], &array[0]);
}

However, clearly, if you replace y by x inside the if, this program has UB. (Note that for lack of a precise restrict on the level of LLVM IR, I am considering C semantics here, which of course is not realistic. But it helps to demonstrate some of the subtlety around restrict.)

[*] If this is surprising to you -- note that restrict does not say anything about whether two pointers are equal or not. It is solely a promise that the accesses "performed through these pointers" do not alias with each other. Indeed, ptr equality is a rather useless concept when it comes to alias analysis, since ptrs can have different values but still point to overlapping regions of memory.

4 Likes
62

Also every time you write vec.iter() or slice.iter() in Rust.

2 Likes
63

The specification of restrict does not deliberately refer to the == operator, but consider the following function:

#include <stdint.h>
int test(int * restrict p, int * restrict q, int i)
{
  *p = 1;
  if ((uintptr_t)(p+i) == (uintptr_t)q)
    p[i] = 2;
  return *p;
}

The Standard's definition of the term "based upon", which is fundamental to the meaning of restrict specifies that a pointer expression is based upon a restrict-qualified pointer if replacing the latter pointer with a pointer to a copy of the applicable data would change the value of the pointer expression. If one were to replace p with a pointer to a copy of the array identified thereby, would that cause the value 2 to be written to a different address?

Personally, I think the definition of "based upon" is bad in just about every imaginable way. It's needlessly hard to understand, and yields corner cases which are absurd, ambiguous, nonsensical, and unworkable; I suspect the only compilers that handle all of the corner cases mandated by the Standard are those which ignore the qualifier altogether. As the Standard is written, however, it would not forbid clang from ignoring the possibility that the lvalue expression p[i] might be used to access p[0]. Some compiler writers might regard the fact that the definition of restrict would allow such an "optimization" as a good thing, but the way the Standard is written would imply that an expression like: array+(p==q) would be based upon p and q in the event that those pointers happen to be equal without being based upon each other.

Incidentally, while neither clang nor gcc makes any attempt to recognize situations where comparisons would expand aliasing sets, they seem to try to slavishly follow the Standard's wording in scenarios where comparisons can be used to shrink them. If they can determine that an expression will only be true in cases where p and q will be equal, but it doesn't actually make use of the restrict-qualified pointer p, then they will recognize that replacing p with a pointer to a copy of its associated data wouldn't change the value of such an expression, and thus not draw inferences based upon it.

64

Indeed, the C standard uses an "information-flow" kind of definition for restrict. And once you consider implicit flow (as in your example), that becomes very tricky. This is why I consider the C standard definition of restrict to be basically useless. I am not aware of any formalization that would actually match this spec; I am not even sure what such a formalization should look like.

So, I think the best thing we can do with this part of the spec is ignore it. Instead, someone should work out a spec for restrict that is actually precise and unambiguous and enables the kinds of optimizations compilers want to do. I once got started on it but then other, more interesting projects came along.

If you mean the C standard's definition here, we are in full agreement. :slight_smile:

I am not sure what this has to do with my blog post, though.^^ The C standard has many, many problems; that was not the point of this post. Your original point was along the lines of not using UB for optimizations; the argument you are making now has literally nothing to do with that. As I said before: just because the C standard is bad, and the C standard uses UB, doesn't mean that UB is bad.

Stacked Borrows is an example of a memory model that provides very strong aliasing guarantees (much stronger than restrict) without having to use this awful definition of "based upon". It is fully precise, mechanized in Coq with correctness proofs of optimizations, and implemented in Miri. It has none of the ambiguity issues that the approach in the C standard has. It can easily be combined with this approach to ptr-to-int casts.

4 Likes
65

So, I think the best thing we can do with this part of the spec is ignore it. Instead, someone should work out a spec for restrict that is actually precise and unambiguous and enables the kinds of optimizations compilers want to do. I once got started on it but then other, more interesting projects came along.

Defining restrict would not be difficult if one recognizes a three-way partition "definitely based upon", "definitely not based upon", and "at least potentially based upon", and is willing to accept that some things will fall into the third group and won't be optimizable. Saying that the result of an expression which form pointers from a pointer are based/not based/potentially-based upon the original,. and those which form a pointer from something that isn't a pointer are potentially based upon any pointer that may have leaked, would be simple, and would enable 90% of the useful optimizations that restrict could allow.

I am not sure what this has to do with my blog post, though

The only rationale I can see for a compiler ever judging the clang/gcc aliasing assumptions as appropriate would be if they were trying to aggressively implement the C Standard's semantics for "restrict". That is the only situation where the combining facts that (p is known not to alias r) and (p and q have the same address) could justify an assumption that q can't alias r. I suppose given the possibilities that:

  1. the auhors of both gcc and clang+llvm implemented logic to process aliasing assumptions for restrict in a way which is contrary to what the authors intended, but would at least be justifiable, or

  2. the authors of both gcc and clang+llvm thought it appropriate to invent and impose language rules which are directly contrary to what the Standard specifies, and not allow any way to disable them except by disabling all optimizations altogether.

I'll admit I think #2 is actually more likely, but would find such conduct on the part of a compiler development team as a sign that the team isn't interested in producing a sound compiler and nothing they do should be trusted. The only way I could see the clang/gcc misbehavior as an "honest mistake" would be if the authors were trying to implement something that was in the language spec.

Basically, my sticking to restrict is me bending over backward to view the behavior of gcc and clang+llvm in a light that doesn't present them as untrustworthy garbage. I'll readily admit that it's tenuous, but since many people don't want to view gcc and clang+llvm as untrustworthy garbage, I'm bending over backward to give them the benefit of the doubt. If there's some other way you see that their behavior could be viewed as an "honest mistake" I'd be glad to hear it.

It can easily be combined with [this approach to ptr-to-int casts]

Approaches involving tracking provenance through numbers would seem needlessly complex and dangerous. I would think the most practical approach would be to recognize a category of actions that "leak" pointers, and a category of actions that "synthesize" pointers, and say that every pointer that is synthesized is "at least potentially" based upon any and all pointers that have been leaked. In cases where one needs to have a type that can either hold a number or a pointer that will be converted back to an actual pointer without doing any arithmetic upon it, it might be useful to have an "integer or pointer" type which can be used as either a pointer or integer without the conversions being regarded as leakage and synthesis, or have an opt-in mode which would treat uintptr_t like that for use with code that was known not to use the type for any other purpose, but in most cases integer-to-pointer conversions tend to be rather rare outside situations that involve doing things that compilers shouldn't expect to fully understand, and which they should thus refrain from trying to optimize too aggressively.