14 ms·
Pointers Are Complicated III, or: Pointer-integer casts exposed
- celeritascelery 5y agoThere are a few parts of this I still struggle to understand. I don’t get why ptr2int casts are a problem if you never try and cast the integer back to a ptr. It seems like int2ptr is the real issue. Also it’s said that casts to int are better then transmutes because cast have side effects. But ptr2int casts don’t actually have side effects, they are a No-op on the hardware.
- GolDDranks 5y agoThey are problem in the sense that the address of the pointer gets exposed. After you lose track of who has it and who might do what with it, you can't track the aliasing information of the pointer, so you have to suppress some optimizations. But you are correct in the sense that if int2ptr never happens, it's all good. About side effects: we are not talking about having side effects on hardware level, we are talking about side effects from the compiler's viewpoint. Again, the compiler might track aliasing information for optimizations, and casting has the side effect of "exposing" the pointer.
- mlindner 5y agoI'd assume because it has something to do with the idea is that an optimizing compiler can't completely delete the address entirely anymore if it's being used for "something". For example optimizing it away to a register only variable.
- kibwen 5y ago> I don’t get why ptr2int casts are a problem if you never try and cast the integer back to a ptr. AFAIK, you do understand. ptr2int casts are totally fine and defined behavior, as long as the program contains no int2ptr casts. Is there a passage from the OP that contradicts this?
- celeritascelery 5y agoFrom the section "Casts have a side-effect": > But in this case, the operation in question is (uintptr_t)x, which has no side-effect – right? Wrong. This is exactly the key lesson that this example teaches us: casting a pointer to an integer has a side-effect, and that side-effect has to be preserved even if we don’t care about the result of the cast. ... We have to lose some optimization, as the example shows. However, the crucial difference to the previous section is that only code which casts pointers to integers is affected. So even if we never even use the result, casting a pointer to an integer is problematic. But in the explanation he only talks about the problems of int2ptr cast, which I do undestand.
- comex 5y agoThe problem is that, if we assume that integers don’t have provenance, some far distant part of the code could guess the integer and do an int2ptr. If you can prove that nothing in the entire program could possibly do this for the entire lifetime of the original object, then sure, you could remove the ptr2int. But compiler optimizations usually work one function at a time. In some cases it might be feasible to prove this anyway, like if (a) you have a function that doesn’t call any other functions and (b) the object in question is a local variable that will go out of scope at the end of the function, making any further accesses UB regardless. But in most cases it’s not feasible.
- ralfj 5y agoIndeed int2ptr is the "evil" operation. If we banned it, we could get rid of all this "exposed" stuff and ptr2int would be fine. However, in order to make int2ptr work, we have to also make ptr2int a bit more complicated. That's what the example shows: removing a ptr2int introduced UB into the program. Rust now (experimentally) has an `ptr.addr()` operation that is like ptr2int without the "expose" part, i.e., the resulting integer cannot be cast back but still used for other purposes.
- kevin_thibedeau 5y ago> they are a No-op on the hardware. That is not guaranteed. The only guarantee is that you can round trip conversions via (u)intptr_t. The integer representation of a converted pointer can be completely different to accommodate hardware like the Symbolics lisp machine.
- celeritascelery 5y agoAre we losing optimization on x86/arm due to mere existence of other hardware (like symbolics or CHERI) that handles things differently?
- astrange 5y agoYou don't lose the optimizations because of UB and aliasing rules letting them stay in, but the people who want to make C safer by simply defining all UB would lose you all these optimizations. ARM already includes a small part of CHERI (pointer signing) and the rest is coming.
- kmonsen 5y agoI mean you are correct, but why else would a pointer be converted to it if not to cast it back at some point? I guess you can print it for debugging, but most other uses means it will be used as pointer at some point.
- Findecanor 5y agoIMHO, casts from integer to pointer should have been deprecated in C (and derivative languages) a long time ago. Not only do they encourage unsafe practices, being forbidden in most C/C++ style guides. They can also wreak havoc with any hardware or software-hardening that puts non-address bits in pointers. For instance, ARM PAC has been in Apple's CPUs for years now and support is mandatory in ARM v8.3 and up. Intel and AMD have also had experimental extensions that use those bits, and new ones are on the way. When an integer is cast to pointer in those schemes, the pointer can become invalid. Therefore, an integer cast to a pointer type should always result in an invalid pointer, IMHO. Integers are sometimes used to set alignment. I'd suggest that the macros in CHERI C be added to <stdalign.h>: align_up, align_down and is_aligned. Those can be expressed in normal C without having to cast an integer to pointer, or use faster expressions depending on the platform.
- andi999 5y agoHow do you do embedded then? I mean you need to specify the addrese of lets say the spi interface. Usually numbers are written as integers. So we would need a syntax for pointer literals?
- addaon 5y agoI don't particularly agree with the grandparent that getting rid of pointer-to-integer casts makes sense, but at least the specific question you're asking doesn't seem like a non-starter. Two options that come to mind immediately would be making a union { intptr_t; foo * } well-defined; or adding a 'p' or 'ptr' literal suffix so 0x80004000p has type void *.
- flohofwoe 5y agoAre there any experimental systems programming languages exploring the opposite of "pointer provenance" (and the resulting compiler complexity)? E.g. treat memory strictly as some sort of separate storage device, and do all computations in local register-like variables (which could be backed by a special invisible scratch space to allow variables to spill from registers to scratch space. Basically a language which would require explicit load/stores from and to regular memory, instead of trying to provide the illusion of an infinitely large register bank.
- saagarjha 5y agoAre you looking for a language that does function local, bounded optimization, and dumps state directly to memory at various well-defined boundaries?
- flohofwoe 5y agoI think more like a medium level language somewhere between assembly and C, with a clear distinction between a "virtual register bank" and "mass storage memory". Moving data between the two would be an explicit operation, not something the compiler would ever do automatically.
- saagarjha 5y agoSo, one way you can do this is to mark all your "memory" pointers as volatile, then load them into register variables and store them back manually. This would actually allow for very aggressive optimizations in the region that you've fenced off with "register" since the compiler can assume there is no aliasing, while letting you define the boundary where you'd like to writes to "go to the hardware". In C this might be a bit of boilerplate but in C++ once could assume you could RAII the boilerplate away…might be worth exploring.
- dmytrish 5y agoAssembly languages sound like what you describe, and they do not make the burden of memory management go away, just shift it. You still have to manage a separate storage device somehow (most often via file systems drivers). That's why GCs are so popular: you have a smart "driver" between your code and a RAM storage that makes life so much easier.
- rocqua 5y agoI am misunderstanding something about `restrict`. > the original program already had Undefined Behavior, or (at least) one of the optimizations is wrong. As far as I know, since the uwu function was declared with x and y as restrict, the way uwu is called in main is undefined behavior. Because they are both pointing into the same array, and are both 'derived' from the same array. I guess if I am wrong its because `restrict` does not care if both are derived from the same pointer. Instead it might only care if x was derived directly from y or y was derived directly from x. Is there a good reason to only care about this 'directly derived from' rather than 'shared derivation'? It would sorta suck if you can't use a function with to restrict arguments pointing into the same array, but this example seems to suggest that might be a reasonable requirement.
- dthul 5y agoIndeed I don't think C cares about how the pointers you mark as "restrict" were constructed, it just cares about how you actually use the pointers and in the example code they are never used in an "overlapping" way. I just checked cppreference and it says: "if some object that is accessible through P [marked restrict] (directly or indirectly) is modified, by any means, then all accesses to that object (both reads and writes) in that block must occur through P (directly or indirectly), otherwise the behavior is undefined" The only accesses I can see are "*x = 0;", "*ptr = 1;" and "return *x;". "*ptr" is an indirect access through "x" by way of an integer round trip. If the orignal program is indeed UB that would mean that pointers built from an integer round trip are not considered (indirect) accesses through the original pointer. The author assumes that it is an indirect access: "However, the only possibly suspicious part of the original program is a pointer-integer-pointer round-trip – and if casting integers to pointers is allowed, surely that must work. I will, for the rest of this post, assume that replacing x by (int*)(uintptr_t)x is always allowed."
- taintegral 5y ago`restrict` pointers have nothing to do with the underlying "object" they point into (an array in this case). `restrict` lets the compiler assume that reads through a restricted pointer or any pointer expressions derived from it are only affected by writes through that pointer or expressions derived from it. There are only two writes in this example: `*x = 0`, which is trivially correct; and `*ptr = 1`, where `ptr` is derived from `x` (via `ptr = (int *)(uintptr_t)x`) so this is also correct. However, it's now easy to see that the optimization replacing `xaddr` with `y2addr` causes undefined behavior since it changes `ptr` to be derived from `y`. The post addresses this in "The blame game" and mentions that integers could carry provenance but that it's infeasible to actually do this. The weak provenance solution is to ban optimizing the pointer to integer casts since they have a (conceptual) side-effect. The strict provenance proposal points out that the side effect is only observable if the integer is cast back to a pointer, so we can keep optimizing pointer to integer casts and instead ban integer to pointer casts. For example, an operation like `(int *)xaddr` is banned under strict provenance. Instead, we provide a casting operation that includes the pointer to assume the provenance of; something like `(int * with x)xaddr`. With this new provenance-preserving cast, we can see that the final optimization of replacing `*x` with its previously assigned value of `0` is no longer possible because the code in between involves `x`.
- xscott 5y ago> [...] restrict, a C keyword to promise that a given pointer x does not alias any other pointer not derived from x The author clearly states that restrict is a promise, and then immediately violates that promise. If you lie to the compiler, what do you expect to happen?. Declaring your pointers "restrict" is a promise from your code to the compiler, not from the compiler to your code. It seems like the entire rest of the article is based on this misunderstanding, and there are a whole bunch of strong statements and questionable conclusions drawn from it: > This is bad news. Our optimizations changed program behavior. That must not happen! > the only possibly suspicious part of the original program is a pointer-integer-pointer round-trip > while the details of defining “derived from” are nasty, it should be clear that doing a bunch of operations that literally don’t involve x at all cannot by any stretch of the imagination produce a result that is “derived from” x It's hard for me to make sense of the rest of the business about "provenance" when the problem it's supposed to solve are based on faulty reasoning. The part about casting to integer having side effects doesn't follow either. I've always liked C, and I'm coming to really like Rust. I hope mistaken arguments like the ones in this article aren't persuasive to anyone in the compiler camps.
- dthul 5y ago> The author clearly states that restrict is a promise, and then immediately violates that promise Which part of the program do you believe violates the restrict promise? I think it's not obvious that it is violated. The question is whether a pointer obtained through an integer round trip is considered to be derived from the original pointer. The author assumes that it is.
- deleted 5y ago[deleted]
- xscott 5y ago> Which part of the program do you believe violates the restrict promise? The part where they modify a piece of memory using `x` and then modify the same piece using `y`. That's a promise the programmer made inside that function and for anyone else who calls the function. This is C, so it's not the compiler's job to prove the implementer or caller got it right.
- xscott 5y agoI was wrong elsewhere in this discussion. I now think the problem isn't that the original code breaks any rules/promises, but that the transformation to the second version of the code is not valid. > So, which of the optimizations is the wrong one? In the original function, the code compares addresses but only modifies through `x`. But since it's a static function, and since it can see all the call sites, it eliminates a test it can prove is always true. So far so good. However, it's not valid to keep the `restrict` declarations after that rewrite. It changed a modification through `x` to a modification through `y`, so that clearly violates the promise.
- taintegral 5y agoThis analysis is correct but the solution is not feasible. Changing a modification through `x` to a modification through `y` does indeed violate the semantics of `restrict`. The problem is that in order to detect this situation, we'd have to track the provenance of integers. In this specific example, we'd have to know that replacing `xaddr` with `y2addr` affects `x` and `y`. There is general consensus that tracking provenance for integers causes many more problems than it solves, so although this would solve the problem it is not feasible. This is why weak and strict provenance are being pursued instead.
- xscott 5y agoWith regards to optimization passes, does it matter if the analysis is infeasible? We agree the optimization/transformation from the first version to the second isn't valid, so I think it shouldn't have been done. The original version with two stores and one load doesn't seem to have a problem. Having the optimizer punt when it gets confused by integer to pointer casts seems acceptable.
- jcranmer 5y agoIt's not sufficient to say "there's an int2ptr cast, so stop optimization." You can break the code up across several function calls, which means the code doing the optimization can't tell that there's an int2ptr cast around to shut down the optimization. (Most optimizations are intraprocedural, and even if they could look interprocedurally, there's no guarantee that the function body is even available for inspection--they could be in different C source files). Instead, you'd have to instead prove that there's no possible int2ptr cast around everywhere, which is generally an impossible analysis.
- benibela 5y agoIt is much simpler in Pascal When you write to a pointer, it writes into memory. And it does not optimize it away. As if all pointers are volatile.
- cryptonector 5y agoBut then you have to constantly work around that in your code, making it read more like assembly in a way.
- pjmlp 5y agoWhich Pascal?
- benibela 5y agoFreePascal: procedure x; var a: integer; b: pinteger; begin b := @a; b^ := 1; b^ := 2; end; becomes project1.lpr:15 begin 0000000000401090 50 push %rax project1.lpr:17 b^ := 1; 0000000000401091 c7042401000000 movl $0x1,(%rsp) project1.lpr:18 b^ := 2; 0000000000401098 c7042402000000 movl $0x2,(%rsp) project1.lpr:19 end; 000000000040109F 59 pop %rcx 00000000004010A0 c3 ret Perhaps Delphi, too Although I do not know how much is by design and how much comes from bugs in the optimizer. But they said that one reason why they maintain their own optimizer rather than switching to LLVM. LLVM would "break" this function
- tored 5y agoPureBasic's new C-backend had the same problem, declaring them volatile solved it. https://www.purebasic.fr/english/viewtopic.php?t=78859 https://www.purebasic.fr/english/viewtopic.php?t=78859
- deleted 5y ago[deleted]