10 ms·

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

169 points by ksec 2y ago

quuxplusone 2y ago
(2020)
- dang 2y ago
  Added. Thanks!
kibwen 2y ago
Great series of blog posts, I link them every chance I get. Important to note that in the years since this post was written, provenance has become an explicitly accepted consideration of the Rust memory model ( https://doc.rust-lang.org/std/ptr/index.html#provenance https://doc.rust-lang.org/std/ptr/index.html#provenance ), and standard APIs have been stabilized for working with pointers in ways that preserve provenance: https://doc.rust-lang.org/std/ptr/index.html#strict-provenance https://doc.rust-lang.org/std/ptr/index.html#strict-provenan...
- tialaramex 2y ago
  More specifically Aria's Experiment (the provenance APIs) was stabilized in 1.84 which actually shipped as a release only last month, January. Socializing these APIs is important = if you write or review unsafe Rust, especially unsafe Rust which does stuff with pointers, knowing these APIs exist makes it less likely you will write or wave through unsound software that treats integers as having provenance, sometimes you would get away with that, other times you would not, good Rust programmers shouldn't let other Rust programmers use a usize where a pointer was the correct type, just as you wouldn't use u32 where IPv4Addr is the correct type.
grandempire 2y ago
Certain C optimizations are difficult to implement due to pointers. But that doesn't make pointers themselves complicated. Most of the C community agrees that strict aliasing assumptions are more trouble than they are worth.
- kibwen 2y ago
  Strict aliasing isn't the root problem here, because Rust, which doesn't have C-style strict aliasing, would similarly exhibit the same theoretical miscompilation in the absence of provenance.
  - grandempire 2y ago
    strict aliasing is an example of questionable optimizations from hard to verify assumptions.
- deleted 2y ago
  [deleted]
dataflow 2y ago
> one of the three optimizations is incorrect ... but which one is it? > The final optimization notices that q is never written to Isn't it obviously this assumption that's blatantly wrong? You have no clue q is never written to because the address was saved somewhere and you clearly have no idea what happened to the address afterward. It could've obviously been used to write to the variable. Is that so complicated? This feels like saying "I closed my eyes. I no longer see you. You are clearly not in front of me anymore, so I punch into the air and hit you. Which of my assumptions was wrong?" Such a mystery!
- nine_k 2y ago
  How come? Assuming we're in a function, the `q` in question has just been allocated on the stack, and its address never left the context of the fragment, e.g. was never used as an argument of any function call; even the `print` receives the value of `q[0]`, not the address. Nothing else should know where `q` even is, let alone modify it behind the scenes. What am I missing?
  - dataflow 2y ago
    > Nothing else should know where `q` even is, let alone modify it behind the scenes. What am I missing? The variable iq knows where q is, no? uintptr_t iq = (uintptr_t)q; If you (the compiler) can't analyze beyond that, that's the end of the story: the address escaped somewhere. If you can... well then not only that, but a decision was made on it: if (iq == ip) And then a write was performed on an address that you clearly can't prove was uncontaminated with q's address: *(char*)iq = 10;
    - jcranmer 2y ago
      That's sort of the crux of the issue: what constitutes exposing a pointer? Half the time, within the compiler, a pointer-to-integer conversion is essentially a nop cast instruction that can be optimized away if unused or freely deleted (e.g., roundtrip pointer-to-integer-to-pointer) or slide addressing information before and after the pointer. The other half the time, it's an important leaks-the-address operation that can't be triggered because, you know, that causes things to be leaked. It's Schrödinger's side effects, they both matter and don't matter, and you don't know if it ends up doing so or not until you open the box. It's a complete mess, and ultimately entirely incoherent, inconsistent semantics that is begging for a fix. Even worse, if you read all the compiler documentation, you'll find strong assertions that provenance is carried solely by data dependence (including through integers). The compiler optimizations for integers explicitly disclaim preservation of data dependence, which is why the leading model for pointer provenance (PVNI) is "integers don't have provenance, therefore pointer-to-int is an address-exposing operation." But even more annoyingly, the semantics at the IR level imply that memory is untyped, which kind of means every load or store of a pointer is an implicit integer conversion, but that doesn't actually happen in practice, except that memory is frequently converted to an integer if you're just copying from one block of memory to another and it's just a mess of several optimizations are broken in weird, unexpected ways that no one really realized until people started trying to apply formal semantics to compiler optimizations and found these soundness holes. And the most annoying part of all are the people sitting on the sidelines yelling at us "pointers are integers, why are you guys making this all so complicated?"
IgorPartola 2y ago
I have some questions. First, do pointers that do not come from specifying a statically sized array also have provenance? That is if I say `char* c; size_t n = get_user_input(); c = malloc(n);` does c have provenance? If after the above I created an array like so `char str[n]` and then assigned such that it pointed to the same region of memory that malloc() returned, then would the provenance of both pointer be equal? Also, in Rust why are pointer to integer casts allowed at all if they lose provenance? Also, why exactly is one past end of bounds a valid pointer you can calculate? Also, it seems like you cannot just create a random pointer to an unallocated address, not just that you can’t write to it. Is that correct? Lastly, is provenance just a fancy way of saying metadata? Is there a reason something like “pointer metadata” or “object metadata” wasn’t used?
- Arnavion 2y ago
  >That is if I say `char* c; size_t n = get_user_input(); c = malloc(n);` does c have provenance? Yes. >If after the above I created an array like so `char str[n]` and then assigned such that it pointed to the same region of memory that malloc() returned, then would the provenance of both pointer be equal? Yes. >Also, in Rust why are pointer to integer casts allowed at all if they lose provenance? It would be a breaking change to remove the ability to cast. Instead Rust added API to extract the provenance when casting from ptr to int and then add provenance back when casting from int to ptr. >Also, why exactly is one past end of bounds a valid pointer you can calculate? It's useful to allow it to make `if (ptr < end)` with exclusive `end` possible. The alternative of only allowing `if (ptr <= end)` with inclusive `end` is not as trivial if it needs to handle empty ranges (the exclusive version can just use `end = start` to denote an empty range). >Lastly, is provenance just a fancy way of saying metadata? Pointer metadata in Rust at least refers to a different thing, namely the second half of fat pointers. For slice pointers the fat pointer contains data ptr and length, so the length is the metadata. For trait object pointers the fat pointer contains data ptr and vtable ptr, so the vtable ptr is the metadata.
  - josephg 2y ago
    > It's useful to allow it to make `if (ptr < end)` with exclusive `end` possible. The alternative of only allowing `if (ptr <= end)` with inclusive `end` is not as trivial if it needs to handle empty ranges (the exclusive version can just use `end = start` to denote an empty range). As an aside: I find it fascinating that half-open ranges turn out to be - universally as far as I can tell - the right choice for ranges in software. As well as being able to store an empty range, they also allow you to calculate the length of the range by trivially subtracting end - start.
Animats 2y ago
What this really says is that C giving one-past-the-end pointers meaningful semantics may have been a mistake. So was trying to give aliasing of writable objects meaningful semantics.
IshKebab 2y ago
I found provenance easiest to think about after learning CHERI, since there the provenance isn't just an abstract concept that allows better optimisation; it's actually real data in the capability that affects whether it works at all, irrespective of optimisations. You literally can't cast an integer to a pointer, even in assembly.
- tialaramex 2y ago
  Well, you can't "just" cast any of Rust's integers to a pointer because they're not necessarily the same size (one of the changes to Rust is the decision that usize is not the same size as a pointer only the same size as the pointer address), but C++ uintptr_t is in fact guaranteed to be the same size and presumably the compiler might just model it as an address the same as a pointer. Today there are no settled provenance rules for C or C++ but there is a TS for C explaining PNVI-ae-udi. Under that model if we cast a pointer to uintptr_t we're exposing the provenance of that pointer. In Rust's Exposed Provenance API we're not promised that this is even possible on every target (if we imagine compiling Rust for a CHERI target clearly expose_provenance may not compile to any actual code, maybe the compiler barfs) but in C we're guaranteed the actual raw bits so we're allowed to, for example, display them to the user and under this TS the associated provenance is thereby exposed - so we can have the user later input an arbitrary integer, turn it into a pointer and the resulting pointer must work if they gave us the right number and that pointer would still be valid! Is that a good idea? No. But it's very on brand for C and might become the de facto or even de jure semantic for pointer provenance in C++ too.
  - uecker 2y ago
    The reason this is a really good idea is because is sometimes needed in the real world and with PNVI-ae-udi is just works. Also the alternative models have horrible semantics, e.g. either because you have provenance via integers (where algebraic properties of mathematics breaks) or because you get really subtle semantics that is hard to reason about (all the angelic / demonic indeterminism ideas).
    - 2y ago
James_K 2y ago
char p[1], q[1] = {0}; uintptr_t ip = (uintptr_t)(p+1); uintptr_t iq = (uintptr_t)q; if (iq == ip) { *(char*)iq = 10; print(q[0]); } I am genuinely a little scared of this C program.
- shakna 2y ago
  As a C program, it doesn't actually work. [0] It's just C-as-pseudocode for LLVM IR. And LLVM has different semantics for what is allowed and denied, than C. [0] https://godbolt.org/z/58GcP1d9j https://godbolt.org/z/58GcP1d9j
  - James_K 2y ago
    The only reason it doesn't work is because the stack grows downwards on x86 targets so p is at a higher address than q. If you swap the variables round, it compiles and runs printing the value assigned. https://godbolt.org/z/bedb7cvY8 https://godbolt.org/z/bedb7cvY8
    - shakna 2y ago
      As the compiler is free to reorganise the variable order, that means you're relying on Undefined Behaviour for it to compile and do what you want. That's not something inherent to the way pointers work.
      - James_K 2y ago
        It is valid C program. Undefined behaviour occurs at runtime, but it is valid and should be compiled by a conformant C compiler.
    - spaqin 2y ago
      [dead]
- chongli 2y ago
  Section 6.3.2.3 of the C11 standard [1] reads: 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. ... 6 Any pointer type may be converted to an integer type. Except as previously specified, the result is implementation-defined. If the result cannot be represented in the integer type, the behavior is undefined. The result need not be in the range of values of any integer type. The issue for your code is that on line 2 you cast to uintptr_t the pointer (p+1) to type char, which is not a pointer to void (and not a null pointer). So the result of your conversion is implementation-defined and the result need not be in the range of values of any integer type. Thus an implementation can assume that the result of the comparison (iq == ip) is always false and even omit the entire if-block. [1] http://port70.net/%7Ensz/c/c11/n1570.pdf http://port70.net/%7Ensz/c/c11/n1570.pdf
captainmuon 2y ago
The downside of defining things like pointer provenance in the IL is that it ties the semantics of your IL to C. If you are writing another language and want to have very different symantics - say a flat memory model where pointers are integer indicies into memory, or definied signed overflow - then you will have to be very careful and constantly have to fight or work around the C semantics. Basically the same downside as when you use C as a compilation target (like for example Nim does/did).
- Rusky 2y ago
  The IR doesn't have to cater to programmers in the same way, and can support many choices of semantics simultaneously in a single program. For example, LLVM IR is used to compile C both with and without strict aliasing. The choice is lowered into metadata applied to individual pointer operations. Similarly with signed integer overflow. Nim could even have gotten some of this benefit when compiling to C if it had been willing to target a specific set of C compilers, rather than standard C.
- nikic 2y ago
  Where possible, undefined behavior at the LLVM IR level is always optional, controlled by various flags, attributes and metadata. Things like signed integer overflow, or even the forward progress guarantee are controlled that way, and admit a wide range of possible language semantics. Provenance (and to some degree the entire memory model) is the big exception to this. It's a very core part of the IR semantics, and an optimizing compiler without provenance would have to use entirely different methodology to justify many optimizations. I don't believe that anyone has yet been able to demonstrate the feasibility of highly optimizing compiler without provenance.
saurik 2y ago
> ...another pass might notice the INT_MAX+1 and replace it by unreachable since UB code is “by definition” unreachable... I would love to see the concrete example where this actually makes the program faster, to give me a better understanding of what I'm up against if I prefer to make integer field arithmetic well-defined. AFAIK, the main reason these loops are so frustrating in C is because no one wanted to bite the bullet and insist that fast loops all use size_t instead of int--as otherwise on systems where int isn't native (which is, today, most of them) you have to emulate the wrap by adding a mask to the iteration--and so the compilers started inferring stuff and the language spec got damaged to let them work around it instead.
- gpm 2y ago
  For what it's worth rust has made all integer arithmetic well-defined unless you explicitly opt in to the alternative on a case by case basis. Opting into the alternative is not something I've seen people having to do for performance. Specifically in release builds it's defined to be 2s complement arithmetic. In debug builds it's defined to panic (in non rust speak that is basically throw an exception) on overflows, and the language theoretically reserves the right to change the behavior on release builds to do the same, but that hasn't been done because the exception route does actually incur a non-negligible performance penalty.
  - steveklabnik 2y ago
    I agree with you that I don't see people opting in for performance, but it's also the case that C relies on this behavior a lot more than Rust does, since it doesn't have iterators. If more Rust programmers wrote "raw" for loops, maybe the overhead would be more significant. I don't know if there's any way to qualify this. Also, it' not done by default because it's believed to incur the penalty. We didn't try to do any significant analysis here, mostly relying on the widespread belief. If we wanted to go against the grain, we'd have to demonstrate that it's incorrect, and that's difficult, time consuming, and there's other things to spend time on. Google recently demonstrated pretty convincingly that bounds checks on array access in their C and C++ code has a very minor penalty that's absolutely worth it. I wonder if maybe we'll see something similar with this semantic in the future. I think it's lower priority because it's not a safety issue on its own to have the "maybe this, maybe that" behavior, since it's not undefined behavior.
varispeed 2y ago
I could never understand why "pointers are complicated" or "hard"? They just point at things. Sure there are some semantic quirks if you want to go there, to idk obfuscate the code or to make things more complex than they really are. I just don't get it. Been programming in C for decades now and never had any issues with this.
- nynx 2y ago
  Depending on what kind of software you tend to work on, you may have written a lot of subtly incorrect C.
  - varispeed 2y ago
    Yes, I've done fair share of these, but I don't see them as different from any other incorrect code I may write. I agree that sometimes it may be more challenging to debug, as it may not be immediately obvious that e.g. I am writing memory I am not supposed to.
serbuvlad 2y ago
It seems to me like the final optimization is the only one that is not correct and obviously so. > The final optimization notices that q is never written to, so we can replace q[0] by its initial value 0. However the line right above is *(p+1) = 10; The type of p is char[] which decays into a pointer and the type of (p+1) is char *. Because it is char * and not char * restrict, any assignment through such a pointer can be assumed to modify any and all data in a program. Therefore, the assumption that p[0] does not change and can be swapped out is not somehow surprisingly wrong, but simply entirely unfounded. It is up to the compiler to prove for itself that assignment through pointers does not change data it's interested in from before to after the assignment. (except, of course, in the case of restrict pointers, where the programmer makes this guarantee). This is not very difficult, at least conceptually. If the assignment was *p = 10; Well, we know that *p means p[0], which is within the bounds of the array, and we know that p and q do not overlap. Therefore, this assignment can not modify q. In the case of the first assignment, we know that *(p+1) means p[1], which is out of bounds for the array. So we do not know whether or not an assignment through *(p+1) modifies q, and we can not assume it does not.
- Groxx 2y ago
  It's not always correct, but that's kinda the tradeoff with undefined behavior. It's your responsibility to know the defined spec and stay within it, not the compiler's to prove you did it correctly in all cases. >Since q and p point to different local variables, a pointer derived from p cannot alias q[0], and hence we know that this write cannot affect the value stored at q[0]. Pointer math outside the array bounds isn't defined, so it can be treated as anything, including "cannot possibly do X, so we can optimize it out". A compiler that preferred to spend memory to improve correctness (e.g. Valgrind) might add padding between variables to prevent this kind of small-OOB action, which would make the output change again, which is why this is undefined and you can't rely on it. A compiler that was feeling moody could put that array at the end of your page of addressable memory, and cause a segfault when you try to write to it.
  - serbuvlad 2y ago
    In the actual code *(p+1) is only ever accessed if it has been verified to be the same address as q[0], which is an object which we know exists and we have full access to. The problem is that pointers of the same type to the same address but originating from pointer arithmetic on the pointers obtained by dereferencing different objects have different semantics. In other words, the following is not semantically a NOP. char *p = /*some valid pointer*/; { char x; char *q = &x; while ((uintptr_t) q != (uintptr_t) p) q++; p = q; } I believe this goes against the principle of least astonishment (I find it quite astonishing, personally). I believe, even if the standard not does not guarantee the expected behavior, that implementations should still guarantee it. And they can do the optimizations they want in other ways, as I have outlined.
garaetjjte 2y ago
>Clearly, one of the three optimizations is incorrect in the sense that it introduced a change in program behavior. What about declaring that all three optimizations are correct, and this program invokes UB? More precisely, it compares object one-past-the-end pointer with pointer pointing into entirely another object. one-past-the-end pointer is special because numerically it points outside the object. I think declaring that one-past-the-end pointer could be compared only with itself, valid pointer into the same object or NULL wouldn't be too unreasonable (comparing one-past-the-end pointer with pointer to another object would invoke UB).
- afdbcreid 2y ago
  But it does not. It compares integers. Comparing integers is always well-defined. If you want to declare it UB, you will have to say that the integers are not simple bits, they also "remember" which pointer they came from. This is essentially what we mean when we say that integers has provenance, and it's not a good idea because it doesn't let you do some very common optimizations on integers.
James_K 2y ago
I don't see how the proposed solution improves matters. Even without the second optimisation, it seems that the third could still occur and cause issues. I suppose the compiler must only recognise the potential for a pointer writing arbitrary data when it is first cast to an integer.
Koshkin 2y ago
Did Rust make pointers complicated?

169 points by ksec 2y ago

quuxplusone 2y ago

(2020)

dang 2y ago
Added. Thanks!

kibwen 2y ago

Great series of blog posts, I link them every chance I get. Important to note that in the years since this post was written, provenance has become an explicitly accepted consideration of the Rust memory model ( https://doc.rust-lang.org/std/ptr/index.html#provenance https://doc.rust-lang.org/std/ptr/index.html#provenance ), and standard APIs have been stabilized for working with pointers in ways that preserve provenance: https://doc.rust-lang.org/std/ptr/index.html#strict-provenance https://doc.rust-lang.org/std/ptr/index.html#strict-provenan...

tialaramex 2y ago
More specifically Aria's Experiment (the provenance APIs) was stabilized in 1.84 which actually shipped as a release only last month, January. Socializing these APIs is important = if you write or review unsafe Rust, especially unsafe Rust which does stuff with pointers, knowing these APIs exist makes it less likely you will write or wave through unsound software that treats integers as having provenance, sometimes you would get away with that, other times you would not, good Rust programmers shouldn't let other Rust programmers use a usize where a pointer was the correct type, just as you wouldn't use u32 where IPv4Addr is the correct type.

grandempire 2y ago

Certain C optimizations are difficult to implement due to pointers. But that doesn't make pointers themselves complicated. Most of the C community agrees that strict aliasing assumptions are more trouble than they are worth.

kibwen 2y ago
Strict aliasing isn't the root problem here, because Rust, which doesn't have C-style strict aliasing, would similarly exhibit the same theoretical miscompilation in the absence of provenance.
- grandempire 2y ago
  strict aliasing is an example of questionable optimizations from hard to verify assumptions.
deleted 2y ago
[deleted]

dataflow 2y ago

> one of the three optimizations is incorrect ... but which one is it? > The final optimization notices that q is never written to Isn't it obviously this assumption that's blatantly wrong? You have no clue q is never written to because the address was saved somewhere and you clearly have no idea what happened to the address afterward. It could've obviously been used to write to the variable. Is that so complicated? This feels like saying "I closed my eyes. I no longer see you. You are clearly not in front of me anymore, so I punch into the air and hit you. Which of my assumptions was wrong?" Such a mystery!

nine_k 2y ago
How come? Assuming we're in a function, the `q` in question has just been allocated on the stack, and its address never left the context of the fragment, e.g. was never used as an argument of any function call; even the `print` receives the value of `q[0]`, not the address. Nothing else should know where `q` even is, let alone modify it behind the scenes. What am I missing?
- dataflow 2y ago
  > Nothing else should know where `q` even is, let alone modify it behind the scenes. What am I missing? The variable iq knows where q is, no? uintptr_t iq = (uintptr_t)q; If you (the compiler) can't analyze beyond that, that's the end of the story: the address escaped somewhere. If you can... well then not only that, but a decision was made on it: if (iq == ip) And then a write was performed on an address that you clearly can't prove was uncontaminated with q's address: *(char*)iq = 10;
  - jcranmer 2y ago
    That's sort of the crux of the issue: what constitutes exposing a pointer? Half the time, within the compiler, a pointer-to-integer conversion is essentially a nop cast instruction that can be optimized away if unused or freely deleted (e.g., roundtrip pointer-to-integer-to-pointer) or slide addressing information before and after the pointer. The other half the time, it's an important leaks-the-address operation that can't be triggered because, you know, that causes things to be leaked. It's Schrödinger's side effects, they both matter and don't matter, and you don't know if it ends up doing so or not until you open the box. It's a complete mess, and ultimately entirely incoherent, inconsistent semantics that is begging for a fix. Even worse, if you read all the compiler documentation, you'll find strong assertions that provenance is carried solely by data dependence (including through integers). The compiler optimizations for integers explicitly disclaim preservation of data dependence, which is why the leading model for pointer provenance (PVNI) is "integers don't have provenance, therefore pointer-to-int is an address-exposing operation." But even more annoyingly, the semantics at the IR level imply that memory is untyped, which kind of means every load or store of a pointer is an implicit integer conversion, but that doesn't actually happen in practice, except that memory is frequently converted to an integer if you're just copying from one block of memory to another and it's just a mess of several optimizations are broken in weird, unexpected ways that no one really realized until people started trying to apply formal semantics to compiler optimizations and found these soundness holes. And the most annoying part of all are the people sitting on the sidelines yelling at us "pointers are integers, why are you guys making this all so complicated?"

IgorPartola 2y ago

I have some questions. First, do pointers that do not come from specifying a statically sized array also have provenance? That is if I say `char* c; size_t n = get_user_input(); c = malloc(n);` does c have provenance? If after the above I created an array like so `char str[n]` and then assigned such that it pointed to the same region of memory that malloc() returned, then would the provenance of both pointer be equal? Also, in Rust why are pointer to integer casts allowed at all if they lose provenance? Also, why exactly is one past end of bounds a valid pointer you can calculate? Also, it seems like you cannot just create a random pointer to an unallocated address, not just that you can’t write to it. Is that correct? Lastly, is provenance just a fancy way of saying metadata? Is there a reason something like “pointer metadata” or “object metadata” wasn’t used?

Arnavion 2y ago
>That is if I say `char* c; size_t n = get_user_input(); c = malloc(n);` does c have provenance? Yes. >If after the above I created an array like so `char str[n]` and then assigned such that it pointed to the same region of memory that malloc() returned, then would the provenance of both pointer be equal? Yes. >Also, in Rust why are pointer to integer casts allowed at all if they lose provenance? It would be a breaking change to remove the ability to cast. Instead Rust added API to extract the provenance when casting from ptr to int and then add provenance back when casting from int to ptr. >Also, why exactly is one past end of bounds a valid pointer you can calculate? It's useful to allow it to make `if (ptr < end)` with exclusive `end` possible. The alternative of only allowing `if (ptr <= end)` with inclusive `end` is not as trivial if it needs to handle empty ranges (the exclusive version can just use `end = start` to denote an empty range). >Lastly, is provenance just a fancy way of saying metadata? Pointer metadata in Rust at least refers to a different thing, namely the second half of fat pointers. For slice pointers the fat pointer contains data ptr and length, so the length is the metadata. For trait object pointers the fat pointer contains data ptr and vtable ptr, so the vtable ptr is the metadata.
- josephg 2y ago
  > It's useful to allow it to make `if (ptr < end)` with exclusive `end` possible. The alternative of only allowing `if (ptr <= end)` with inclusive `end` is not as trivial if it needs to handle empty ranges (the exclusive version can just use `end = start` to denote an empty range). As an aside: I find it fascinating that half-open ranges turn out to be - universally as far as I can tell - the right choice for ranges in software. As well as being able to store an empty range, they also allow you to calculate the length of the range by trivially subtracting end - start.

Animats 2y ago

What this really says is that C giving one-past-the-end pointers meaningful semantics may have been a mistake. So was trying to give aliasing of writable objects meaningful semantics.

IshKebab 2y ago

I found provenance easiest to think about after learning CHERI, since there the provenance isn't just an abstract concept that allows better optimisation; it's actually real data in the capability that affects whether it works at all, irrespective of optimisations. You literally can't cast an integer to a pointer, even in assembly.

tialaramex 2y ago
Well, you can't "just" cast any of Rust's integers to a pointer because they're not necessarily the same size (one of the changes to Rust is the decision that usize is not the same size as a pointer only the same size as the pointer address), but C++ uintptr_t is in fact guaranteed to be the same size and presumably the compiler might just model it as an address the same as a pointer. Today there are no settled provenance rules for C or C++ but there is a TS for C explaining PNVI-ae-udi. Under that model if we cast a pointer to uintptr_t we're exposing the provenance of that pointer. In Rust's Exposed Provenance API we're not promised that this is even possible on every target (if we imagine compiling Rust for a CHERI target clearly expose_provenance may not compile to any actual code, maybe the compiler barfs) but in C we're guaranteed the actual raw bits so we're allowed to, for example, display them to the user and under this TS the associated provenance is thereby exposed - so we can have the user later input an arbitrary integer, turn it into a pointer and the resulting pointer must work if they gave us the right number and that pointer would still be valid! Is that a good idea? No. But it's very on brand for C and might become the de facto or even de jure semantic for pointer provenance in C++ too.
- uecker 2y ago
  The reason this is a really good idea is because is sometimes needed in the real world and with PNVI-ae-udi is just works. Also the alternative models have horrible semantics, e.g. either because you have provenance via integers (where algebraic properties of mathematics breaks) or because you get really subtle semantics that is hard to reason about (all the angelic / demonic indeterminism ideas).
  - 2y ago

James_K 2y ago

char p[1], q[1] = {0}; uintptr_t ip = (uintptr_t)(p+1); uintptr_t iq = (uintptr_t)q; if (iq == ip) { *(char*)iq = 10; print(q[0]); } I am genuinely a little scared of this C program.

shakna 2y ago
As a C program, it doesn't actually work. [0] It's just C-as-pseudocode for LLVM IR. And LLVM has different semantics for what is allowed and denied, than C. [0] https://godbolt.org/z/58GcP1d9j https://godbolt.org/z/58GcP1d9j
- James_K 2y ago
  The only reason it doesn't work is because the stack grows downwards on x86 targets so p is at a higher address than q. If you swap the variables round, it compiles and runs printing the value assigned. https://godbolt.org/z/bedb7cvY8 https://godbolt.org/z/bedb7cvY8
  - shakna 2y ago
    As the compiler is free to reorganise the variable order, that means you're relying on Undefined Behaviour for it to compile and do what you want. That's not something inherent to the way pointers work.
    - James_K 2y ago
      It is valid C program. Undefined behaviour occurs at runtime, but it is valid and should be compiled by a conformant C compiler.
  - spaqin 2y ago
    [dead]
chongli 2y ago
Section 6.3.2.3 of the C11 standard [1] reads: 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. ... 6 Any pointer type may be converted to an integer type. Except as previously specified, the result is implementation-defined. If the result cannot be represented in the integer type, the behavior is undefined. The result need not be in the range of values of any integer type. The issue for your code is that on line 2 you cast to uintptr_t the pointer (p+1) to type char, which is not a pointer to void (and not a null pointer). So the result of your conversion is implementation-defined and the result need not be in the range of values of any integer type. Thus an implementation can assume that the result of the comparison (iq == ip) is always false and even omit the entire if-block. [1] http://port70.net/%7Ensz/c/c11/n1570.pdf http://port70.net/%7Ensz/c/c11/n1570.pdf

captainmuon 2y ago

The downside of defining things like pointer provenance in the IL is that it ties the semantics of your IL to C. If you are writing another language and want to have very different symantics - say a flat memory model where pointers are integer indicies into memory, or definied signed overflow - then you will have to be very careful and constantly have to fight or work around the C semantics. Basically the same downside as when you use C as a compilation target (like for example Nim does/did).

Rusky 2y ago
The IR doesn't have to cater to programmers in the same way, and can support many choices of semantics simultaneously in a single program. For example, LLVM IR is used to compile C both with and without strict aliasing. The choice is lowered into metadata applied to individual pointer operations. Similarly with signed integer overflow. Nim could even have gotten some of this benefit when compiling to C if it had been willing to target a specific set of C compilers, rather than standard C.
nikic 2y ago
Where possible, undefined behavior at the LLVM IR level is always optional, controlled by various flags, attributes and metadata. Things like signed integer overflow, or even the forward progress guarantee are controlled that way, and admit a wide range of possible language semantics. Provenance (and to some degree the entire memory model) is the big exception to this. It's a very core part of the IR semantics, and an optimizing compiler without provenance would have to use entirely different methodology to justify many optimizations. I don't believe that anyone has yet been able to demonstrate the feasibility of highly optimizing compiler without provenance.

saurik 2y ago

> ...another pass might notice the INT_MAX+1 and replace it by unreachable since UB code is “by definition” unreachable... I would love to see the concrete example where this actually makes the program faster, to give me a better understanding of what I'm up against if I prefer to make integer field arithmetic well-defined. AFAIK, the main reason these loops are so frustrating in C is because no one wanted to bite the bullet and insist that fast loops all use size_t instead of int--as otherwise on systems where int isn't native (which is, today, most of them) you have to emulate the wrap by adding a mask to the iteration--and so the compilers started inferring stuff and the language spec got damaged to let them work around it instead.

gpm 2y ago
For what it's worth rust has made all integer arithmetic well-defined unless you explicitly opt in to the alternative on a case by case basis. Opting into the alternative is not something I've seen people having to do for performance. Specifically in release builds it's defined to be 2s complement arithmetic. In debug builds it's defined to panic (in non rust speak that is basically throw an exception) on overflows, and the language theoretically reserves the right to change the behavior on release builds to do the same, but that hasn't been done because the exception route does actually incur a non-negligible performance penalty.
- steveklabnik 2y ago
  I agree with you that I don't see people opting in for performance, but it's also the case that C relies on this behavior a lot more than Rust does, since it doesn't have iterators. If more Rust programmers wrote "raw" for loops, maybe the overhead would be more significant. I don't know if there's any way to qualify this. Also, it' not done by default because it's believed to incur the penalty. We didn't try to do any significant analysis here, mostly relying on the widespread belief. If we wanted to go against the grain, we'd have to demonstrate that it's incorrect, and that's difficult, time consuming, and there's other things to spend time on. Google recently demonstrated pretty convincingly that bounds checks on array access in their C and C++ code has a very minor penalty that's absolutely worth it. I wonder if maybe we'll see something similar with this semantic in the future. I think it's lower priority because it's not a safety issue on its own to have the "maybe this, maybe that" behavior, since it's not undefined behavior.

varispeed 2y ago

I could never understand why "pointers are complicated" or "hard"? They just point at things. Sure there are some semantic quirks if you want to go there, to idk obfuscate the code or to make things more complex than they really are. I just don't get it. Been programming in C for decades now and never had any issues with this.

nynx 2y ago
Depending on what kind of software you tend to work on, you may have written a lot of subtly incorrect C.
- varispeed 2y ago
  Yes, I've done fair share of these, but I don't see them as different from any other incorrect code I may write. I agree that sometimes it may be more challenging to debug, as it may not be immediately obvious that e.g. I am writing memory I am not supposed to.

serbuvlad 2y ago

It seems to me like the final optimization is the only one that is not correct and obviously so. > The final optimization notices that q is never written to, so we can replace q[0] by its initial value 0. However the line right above is *(p+1) = 10; The type of p is char[] which decays into a pointer and the type of (p+1) is char *. Because it is char * and not char * restrict, any assignment through such a pointer can be assumed to modify any and all data in a program. Therefore, the assumption that p[0] does not change and can be swapped out is not somehow surprisingly wrong, but simply entirely unfounded. It is up to the compiler to prove for itself that assignment through pointers does not change data it's interested in from before to after the assignment. (except, of course, in the case of restrict pointers, where the programmer makes this guarantee). This is not very difficult, at least conceptually. If the assignment was *p = 10; Well, we know that *p means p[0], which is within the bounds of the array, and we know that p and q do not overlap. Therefore, this assignment can not modify q. In the case of the first assignment, we know that *(p+1) means p[1], which is out of bounds for the array. So we do not know whether or not an assignment through *(p+1) modifies q, and we can not assume it does not.

Groxx 2y ago
It's not always correct, but that's kinda the tradeoff with undefined behavior. It's your responsibility to know the defined spec and stay within it, not the compiler's to prove you did it correctly in all cases. >Since q and p point to different local variables, a pointer derived from p cannot alias q[0], and hence we know that this write cannot affect the value stored at q[0]. Pointer math outside the array bounds isn't defined, so it can be treated as anything, including "cannot possibly do X, so we can optimize it out". A compiler that preferred to spend memory to improve correctness (e.g. Valgrind) might add padding between variables to prevent this kind of small-OOB action, which would make the output change again, which is why this is undefined and you can't rely on it. A compiler that was feeling moody could put that array at the end of your page of addressable memory, and cause a segfault when you try to write to it.
- serbuvlad 2y ago
  In the actual code *(p+1) is only ever accessed if it has been verified to be the same address as q[0], which is an object which we know exists and we have full access to. The problem is that pointers of the same type to the same address but originating from pointer arithmetic on the pointers obtained by dereferencing different objects have different semantics. In other words, the following is not semantically a NOP. char *p = /*some valid pointer*/; { char x; char *q = &x; while ((uintptr_t) q != (uintptr_t) p) q++; p = q; } I believe this goes against the principle of least astonishment (I find it quite astonishing, personally). I believe, even if the standard not does not guarantee the expected behavior, that implementations should still guarantee it. And they can do the optimizations they want in other ways, as I have outlined.

garaetjjte 2y ago

>Clearly, one of the three optimizations is incorrect in the sense that it introduced a change in program behavior. What about declaring that all three optimizations are correct, and this program invokes UB? More precisely, it compares object one-past-the-end pointer with pointer pointing into entirely another object. one-past-the-end pointer is special because numerically it points outside the object. I think declaring that one-past-the-end pointer could be compared only with itself, valid pointer into the same object or NULL wouldn't be too unreasonable (comparing one-past-the-end pointer with pointer to another object would invoke UB).

afdbcreid 2y ago
But it does not. It compares integers. Comparing integers is always well-defined. If you want to declare it UB, you will have to say that the integers are not simple bits, they also "remember" which pointer they came from. This is essentially what we mean when we say that integers has provenance, and it's not a good idea because it doesn't let you do some very common optimizations on integers.

James_K 2y ago

I don't see how the proposed solution improves matters. Even without the second optimisation, it seems that the third could still occur and cause issues. I suppose the compiler must only recognise the potential for a pointer writing arbitrary data when it is first cast to an integer.

Koshkin 2y ago

Did Rust make pointers complicated?