31 ms·

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

262 points by ChrisSD 6y ago

ChrisSD 6y ago
This is a standalone sequel to "Pointers Are Complicated, or: What's in a Byte?" (https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html). Which has been discussed on HN 2020: https://news.ycombinator.com/item?id=24376797 https://news.ycombinator.com/item?id=24376797 2018: https://news.ycombinator.com/item?id=17604402 https://news.ycombinator.com/item?id=17604402
- ralfj 6y ago
  Oh, there was a repost in 2020, that explains the sudden spike in page hits that I saw earlier this year and couldn't trace back. ;)
vlovich123 6y ago
Does this have implications about the safety guarantees even safe Rust can make? It seems like incorrect optimization passes could result in bugs/security issues that are a byproduct of the compiler rather than the language itself. I wonder how big of an issue this is for Rust (relatively probably a bigger issue than for C/C++ where basic resource ownership bugs are more common).
- jswrenn 6y ago
  Yes, the pointer issues Ralf raises has implications about what operations Rust can make safe. An example Ralf posed to the safe transmute working group: a transmutation from a reference (i.e., a pointer with provenance) to one without (e.g., a "raw" pointer) or to a `usize` number cannot be safe. (Rust can safely provide these conversions via the `as` keyword, just not via the more general framework of transmutations). More broadly: Rust is very sensitive to LLVM bugs that inadvertently generate UB. The longstanding issues with `noalias` optimizations is the prime example of this: https://stackoverflow.com/a/57259339/7501301 https://stackoverflow.com/a/57259339/7501301
  - Dylan16807 6y ago
    How could transmutation from a reference to a usize not be safe? Do you mean "and back"?
- steveklabnik 6y ago
  Yes, absolutely. https://github.com/rust-lang/rust/issues/28728 https://github.com/rust-lang/rust/issues/28728 is probably the most famous bug here, but many I-unsound bugs are similar. This would be the case even without this. Compilers are programs. Programs have bugs.
- dbaupp 6y ago
  It’s enough of an issue for C at least that a fully formally verified compiler exists: https://en.m.wikipedia.org/wiki/CompCert https://en.m.wikipedia.org/wiki/CompCert . That is, there’s proof that its (limited) optimisation passes are correct. There’s other approaches to assurance of compiled code too, such as seL4 which has proofs that the binary itself is correct, I believe.
  - astrange 6y ago
    Note that fuzzing CompCert has still found bugs in it - because the entire compiler actually isn't verified. They've extended the proof over time. (Note that "formally verified" still does not mean "bug free", it just means it's a refinement of a proof that is also a program which can have bugs in it. And "formally" sounds like a weasel word.)
    - dbaupp 6y ago
      Ah, thanks for the clarification!
    - ralfj 6y ago
      Yeah, there were some bugs in the frontend and I think one in the backend. But there were zero bugs in the optimization pipeline, which is where typically the most subtle bucks lurk. For more details, see https://www.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf https://www.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf
- gpm 6y ago
  This isn't the first soundness/compilations bug, it won't be the last. This bug can be fixed, hopefully with some work this whole class of bugs can be made rarer. If you were relying on your safety guarantees to include a bug free compiler - rust isn't there yet and you should stop. If you're relying on a bug free happy path, rust is as close as any other language implementation (with one or two exceptions pointed out in sibling comments). So, I mean, if you're arguing that C/C++ programmers are culturally less repulsed by bugs... you might be right about that. Other than that I think it's about the same scale for C/C++ and rust - a bug is a bug no matter what language you wrote it in. The only fundamental implications I think it has is that maybe we need to put more of an emphasis on formalizing the memory model if we want to reduce the number of soundness bugs (something that a number of people are already doing some awesome work towards).
siraben 6y ago
> However, to make the argument that an optimization is correct, the exact semantics of LLVM IR (what the behavior of all possible programs is and when they have UB) needs to be documented. This is a great point as to why formal semantics of programming languages matters. Even if an optimization seems "obviously" correct, finicky things like introducing the possibility of UB can, as the post outlines, cascade into compiler passes that change the program more and more drastically. The post mentions that one need not go overly formal with the semantics, but I'll demonstrate what could happen when one does. One possible formulation of semantics is denotational semantics, which describes how to map a program source syntax into values, i.e. eval : Expr -> Val. So when we have an optimization opt : Expr -> Expr, the desired correctness property for that optimization is that Definition opt_correct (opt : Expr -> Expr) := forall (e : Expr), eval e = eval (opt e). When we want to rewrite, say e + 0 ==> e, for any expression e, the correctness can be stated and proved Theorem e_plus_0_to_e_correct : opt_correct e_plus_0_to_e. One claim in the blog post that correct optimization passes, e.g. opt1 and opt2 compose into another correct optimization pass can be stated as: Theorem opt_correct_compose (opt1, opt2 : Expr -> Expr) : opt_correct opt1 -> opt_correct op2 -> opt_correct (opt1 ∘ opt2). Which means given any two optimization passes opt1 and opt2 such that they are correct, composing them preserves correctness. The proof is simply; eval (opt1 (opt2 e)) = { since opt1 is correct } eval (opt2 e) = { since opt2 is correct } eval e
- Dylan16807 6y ago
  Not sure why you wanted to spend the time to prove "correct optimizations can be combined", but I take issue with that proof. It only works for optimizations that give code exactly the same behavior, which is severely limiting.
  - mhh__ 6y ago
    Exactly the same as in the as-is rule or optimisations explicitly allowed by the standard?
    - Dylan16807 6y ago
dvt 6y ago
First of all: fantastic article. In-depth, insightful, and the examples are absolutely top-notch. On the razor's edge between accessible and profound. Hats off to the author. I will say that the problems seem to lie in a few interesting interlanguage quirks, and not so much on language specs. For example, LLVM and C have different definitions of "undefined behavior"[1] -- this is pointed out when looking at the `poison` identifier. In LLVM this might just be a weird side-effect we don't care about, but actually having an integer overflow is a big deal in C that introduces UB. Given the introduction, LLVM (incorrectly) introduces (C) UB at times. The second section, on pointer provenance, is much trickier, as there's no "obvious" UB introduced there. Further, I would argue that pointer provenance is a meta-language (or meta-computational) concept (which the Rust docs hint at), and logically speaking, might be intractable in the general case (I'd have to think about this more). Pointer arithmetic can fiddle with meta-state, whereas IRs like LLVM tend to focus purely on symbol manipulation. As a side note, I'd be curious what happens when LLVM sees something like: `void *p = &p` which is a self-referential pointer. What does it deduce about it? Does it optimize it away? Cool thought-provoking article. [1] https://www.cs.utah.edu/~regehr/llvm-ub.pdf https://www.cs.utah.edu/~regehr/llvm-ub.pdf
- mjevans 6y ago
  As usual; if a compiler knows about undefined behavior I would much rather it throw an error rather than optimize something the programmer didn't intend based on the compiler out-smarting a human's ability to be specific.
  - klodolph 6y ago
    I've heard this proposal thrown around a lot on HN, but how would that even work? Can you describe how the compiler would do this, what patterns it would look for, and what error messages it would produce? For example, consider this: int factorial(int n) { int r = 1; for (int i = 1; i <= n; i++) { r *= i; } return r; } Since there are two instances of possible UB in the above function, what error messages would you like the compiler to produce? First of all, the compiler can assume that the loop terminates. This is a reasonable assumption from a human perspective—the loop is almost certainly intended to run N times. However, if n = INT_MAX, then there’s UB… and there’s no real way to know that n ≠ INT_MAX. You could argue that you want -fsanitize=undefined, where the compiler inserts checks at runtime. I don’t think this proposal is well formulated enough to be viable. Or consider something like this: void puts_safe(const char *s) { puts(s == NULL ? "(null)" : s) } void puts_with_len(const char *s) { printf("len = %zu\n", strlen(s)); puts_safe(s); } Do you want something like, Warning: puts_safe replaced with puts, because s != NULL, because strlen(NULL) is undefined I suspect there would be a mountain of false positives, and I would rather just use a static analyzer.
samatman 6y ago
Excellent article. It seems to me (and this is somewhat off-the-cuff) that compilers have another option: integers which are cast from pointers have provenance. That is, provenance is a taint: you can't clean it off through casting. So casting from pointer means the user can do integer-things like addition, but it means the compiler can't do integer-things like constant folding.
- gizmo686 6y ago
  I don't think that works. Consider the following (contrived) program: char* q[1] = {0}; int iq = (uintptr_t)q; int ip = 0; while (iq>0) { iq--; ip++; } char* p = (char*) ip; You can make this more efficient (albeit no less contrived) by iterating through iq bit-wise. Less contrived would be sending a pointer through some IPC mechanism (allowing it to be used as an opaque handle externally, while the program will blindly dereference it when it is passed back in); or even passing it within a program across compilation units. If you treat provenance like a taint, you need to track every way it could be propagated, and that does not seem solvable.
  - samatman 6y ago
    So what are the optimizations here? iq is tainted, you can't hoist the loop out. You've said "I'm doing a weird thing here with an integer which used to be a pointer, you have to assume that it involves memory and treat it more like a pointer than an integer"
  - saagarjha 6y ago
    You can solve it by deoptimizing accesses to q once it has been casted to an integer.
gens 6y ago
Pointers are "just" integers (unsigned integers of a size, that is). Most languages treat them differently (C assigns them a type, and a stride with it), but that is usually on top of them being integers. Pointers "point" to (are addresses to) bytes, as he said. If you want you can pack data to a resolution of a bit, and some languages help you do that as well. You can also do whatever you want with pointers (in some languages, ofc), like do bitwise operations on them. Aliasing them can be useful as well, in more then one way. Why not just get rid of pointers ? You know you can. Also, a byte is 0 .. 255. The hardest problem; naming things, and off by one errors.
- steveklabnik 6y ago
  They are not always integers. See this comment from the previous discussions on the other posts, for example: https://news.ycombinator.com/item?id=17607595 https://news.ycombinator.com/item?id=17607595
  - gens 6y ago
    If 'b' is actually used then the compiler has to put 'a' in memory. Theoretically. He says that b is not changed, and does not "escape" (the scope of the code in question). In that case b is useless, and thus it doesn't really even exist. A compiler can "collapse" a lot of code into a fraction of it. That's a part of the "optimizing" part of "optimizing compiler". A compiler can put a value in a register. A compiler can do whatever it wants as long as the results are always the same as if it didn't do anything other then just translate to machine code. Pointer aliasing in C can be bad for the compiler as it can't be sure that it can optimize away something. That's why Fortran is faster, and why the restrict keyword was added to the C standard. And yea, i agree with him completely that a context should be made clear. Personally i'd like less voodoo in programming topics, but, on the other hand, this is still a young science and a lot of terminology is all around the place. ..Actually, scratch that, i found what i was interested in and don't really care about everything else.
    - klodolph 6y ago
      > If 'b' is actually used then the compiler has to put 'a' in memory. Theoretically, no—the “as if” rule applies. In practice, also no, because real compilers perform escape analysis and there are aggressive optimization passes for eliminating dead loads and dead stores. Just like the compiler can optimize out b and replace it with a reference to a, the compiler can optimize out the value stored in a but keep the reference to it stored in b. > In that case b is useless, and thus it doesn't really even exist. I don’t think this notion of “exist” has legs.
zokier 6y ago
Intuitively I feel that the first optimization is incorrect as it introduces out of bound write. I'll admit that this is very much subjective thing
TrianguloY 6y ago
I'm sorry but I don't fully understand the problem and that 'provenance' thing. For me the third optimization is the wrong one, for the same reason as this char i,j='0'; *(&i+1)='1'; cout << j; can't be optimized to cout << '0'; even though the j variable is also never overwritten directly. This reminds me of paralelization of nested loops with pragmas, where you need to specifically say that two pointers will never point to the same space, otherwise the compiler won't optimize the loop because 'it could happen'.
- Someone 6y ago
  If you think that, you’re giving up lots and lots of optimization opportunities. There’s zero guarantee that i and j are adjacent on the stack or even on the stack (there isn’t even a guarantee that there is a stack, but that’s a different subject); a compiler can decide to keep j in a register. That is very common in short functions, and essential for performance. It also would mean the compiler would have to load data from memory way more often, as ¿about? every pointer write might overwrite any memory.
  - mehrdadn 6y ago
    But this is LLVM IR, not C. It feels like a trick question (hear me out). Either with IR semantics the code is already UB (as in C), or it isn't. If the code isn't UB, then why? The obvious assumption is that it's because LLVM IR treats this as a model of a concrete machine (where provenance isn't a thing), not as a C-like abstract machine with UB. In which case, the optimization #3 is clearly invalid. OTOH, if it is already UB, then the optimizations are fine, right? The only way I can see that we can implicate optimization #1 or #2 is by claiming LLVM IR has neither C semantics nor machine semantics, but with some kind of in-between wobbly semantics. There's nothing fundamentally wrong with that, but that's not what a reader would assume in the absence of other information. Especially not when the author writes "this program has two possible behaviors"—this clearly tells us there's no UB and that we should assume this is based on concrete machine semantics (where provenance isn't a thing). So, I would also say, given the info in the post prior to the conclusion, #3 has to be the culprit. I just can't implicate #1 or #2 based on the preceding text; to implicate those you'd have to pull assumptions out of thin air.
pierrebai 6y ago
The bug is clearly the writing past the end of an array. That is: *(p+1) = 10; If you start with a buggy program, that it stays buggy after optimizations is not surprising! Edit: what;s more, the original form of the program also did not write through the q pointer and could have had optimizer the print zero. In the first form, the author assumes the compiler can track the pointer q through q == qi and avoid the optimization that would print zero, but fail to track pointer q through pi + 1 == qi == q.
- mskslal 6y ago
  No, the original program writes through iq, which is well defined. Only the optimized program writes through p+1.
raverbashing 6y ago
Great article It just seems to me there's too much risk in "overoptimizing" especially in a weakly defined language like C with trigger happy optimizers and even more trigger happy "UB means let's go crazy" I take it as principle that no compilers should "throw their hands up" when detecting UB. Crash the program, don't just take that part out.
- gpderetta 6y ago
  Compilers don't detect UB (at least as optimizations are concerned), they assume no UB. If you want to detect UB, at least dynamically, compile with sanitizers.
mehrdadn 6y ago
If you enjoyed learning about pointer provenance (called "safely-derived pointer" in C++ [1]), you might find the recent addition of std::launder() [2] interesting. [1] https://en.cppreference.com/w/cpp/memory/gc/pointer_safety https://en.cppreference.com/w/cpp/memory/gc/pointer_safety [2] https://en.cppreference.com/w/cpp/utility/launder https://en.cppreference.com/w/cpp/utility/launder
- comex 6y ago
  Pointer safety is actually a separate concept from provenance. It was added to C++11 with the intent that it be used by garbage-collected implementations, but I'm not sure if anyone has ever properly implemented it. At least, the big three STL implementations have get_pointer_safety() always return pointer_safety::relaxed ("All pointers are considered valid and may be dereferenced or deallocated"), and there has been a proposal to remove pointer safety from future versions of the standard. [1] [1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2186r0.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p218...
  - mehrdadn 6y ago
    That seems like a non-sequitur. How do "the intention is GC support" and "the C++ standard may remove concept" imply "these two are not the same concept"? To my knowledge safely-derived pointers are entirely about the notion that the derivation of a pointer matters, not just its value. Which is why you can't legally subtract pointers belonging to different arrays, for example. Which is precisely what is the same concept that provenance refers too... right? I don't see any differences pointed out in my readings or in your comment.
brundolf 6y ago
Before reading this I thought working on compilers might be a fun career direction
- jcranmer 6y ago
  To be fair, this kind of complication is relatively rare in compiler work. On the other hand, when it does come up, it does tend to create several hours-long meetings where there are more opinions on what the "obvious" semantics should be than people present. I've always been a stickler for trying to actually specify the obvious semantics to try to forestall these conversations.
  - ralfj 6y ago
    Seeing how long the story of poison/undef is dragging out for LLVM, I'd say it's more of a years-long process than an hours-long one. ;) But still, the most important part is that there's a discussion at all, and the desire to properly solve this problem.
    - jcranmer 6y ago
      Oh, finishing the meetings may take months or years, but the meetings themselves are only a few hours long.
- lambdatronics 6y ago
  If more of the literature were written like this, I'd be more inclined to it.
deathanatos 6y ago
I am not 100% convinced on the third transformation, > The final optimization notices that q is never written to, so we can replace q[0] by its initial value 0: Can we? q is at a language level, possibly aliased with the write immediately above to (p+1), and we know it's aliased because of the if statement. Now, that's a C rule, and the article does note that it is only using C syntax to express LLVM. So, I guess, what are LLVM's aliasing rules? (Indeed, there was originally a write to q, which we replaced with an aliased write to q, so it seems to me that on the whole, the various optimizations are assuming different things about aliasing.)
- lmm 6y ago
  > Can we? q is at a language level, possibly aliased with the write immediately above to (p+1) It's not, because writing to a one-past-the-end pointer is UB. > Indeed, there was originally a write to q, which we replaced with an aliased write to q, so it seems to me that on the whole, the various optimizations are assuming different things about aliasing. That optimization pass doesn't know anything about aliasing, it just replaced an integer with another integer that's equal to the first.
Asooka 6y ago
Personally I just compile my code with "-fwrapv -fno-strict-aliasing". It's not standard C, but every compiler supports an analogue to those class and it saves so many headaches from UB-optimising passes, the tiny loss in performance is worth it. Integer overflow and pointer aliasing are way too easy to accidentally hit in a C program, the two should have never been made UB, but perhaps added as a pragma to annotate definitely safe code that can benefit from the optimisation.
- ralfj 6y ago
  Note that all of the optimizations I used in the main part (not the warm-up) of my post are still performed even with "-fwrapv -fno-strict-aliasing". So this does not avoid the issues I am talking about.
tsimionescu 6y ago
Thinking about this quite a bit, I see the second optimization as pretty obviously incorrect - not because of provenance, but because it acts as if pointer-to-integer-to-pointer casting is value-preserving, which is not at all guaranteed by the C abstract machine. In particular, `p != q && ((uintptr_t)p == (uintptr_t)q)` can be true according to the C standard. Instead of trying to track provenance, simply considering that the transformation between pointers and integers is not value preserving seems to be a simpler rule. If we want to reason about optimizations using the C abstract machine, we can't consider these transformations to be value-preserving, even if they happen to be in the real machines that LLVM targets (and if they start reasoning for the real machine instead of the C abstract machine, a lot of other optimizations are invalid).
- abra529 6y ago
  Is it not guaranteed? Looking at this question [1] on StackOverflow and the quotes from the standard included in the question, it seems that the value should be preserved. (It raises the issue of whether (char※)iq should technically be (char※)(void※)iq if this were C code, but the (void※) cast can be inserted without changing anything about the problems discussed in the article.) [1] https://stackoverflow.com/q/34291377 https://stackoverflow.com/q/34291377
  - tsimionescu 6y ago
    Yes, you are absolutely right, so my argument flies out the window. Thanks for finding the relevant C spec!
- magicalhippo 6y ago
  For me it is the third optimization which is incorrect. I mean, if you replace the pointers with array indexes, then you'd end up with something like this after the second optimization: char data[N]; uintptr_t p = rand_int(N); uintptr_t q = rand_int(N); data[q] = 0; data[p] = 0; uintptr_t ip = (p+1); uintptr_t iq = q; if (iq == ip) { data[p+1] = 10; print(data[q]); } Surely no sane compiler would replace the "data[q]" in the print statement with 0? Or did the caffeine not kick in yet?
fjfaase 6y ago
I think that the main problem is that pointers are a too low-level concept (like assembly language compared to high-level programming languages) that are used to implement various more high-level concepts. I have not come across a language that does have pointers (some functional languages lack pointers all together) and has these high-level concepts. There is a great difference between a pointer that points to a complex value and a pointer, that like a database cursor, points to a certain part in a complex value, either with the purpose to query this value or to make some change to the value.
andrewflnr 6y ago
For purposes of future language design: why not just ban conversion from integers to pointers? Pointers have metadata that integers can't provide, therefore the conversion is impossible, QED. What's the use case for it outside of, say, binary executable loaders?
- adwn 6y ago
  > What's the use case for it outside of, say, binary executable loaders? If you're doing low-level optimizations, and you know that your pointed-to objects are, say, 8-byte-aligned, then you can use the lower 3 bits of your pointer for storing metadata. In certain cases, that can be immensely useful. Some GC implementations use this trick, for example.
  - ralfj 6y ago
    One could imagine a specific primitive operation in the language that lets you adjust the low bits of a pointer without casting it to an integer and back.
einpoklum 6y ago
I remember a CppCon talk which covered how poison and UB work in LLVM IR, probably in 2018 or 2019, but I forget which one it was.
abra529 6y ago
Commenters here as well as the author seem content with asserting that under C semantics, the code after the second optimization exhibits UB when it dereferences (p+1). Is it really UB? Here's the snippet for reference: char p[1], q[1] = {0}; uintptr_t ip = (uintptr_t)(p+1); uintptr_t iq = (uintptr_t)q; if (iq == ip) { *(p+1) = 10; // <- This line changed print(q[0]); } From the article: "LLVM IR (just like C) does not permit memory accesses through one-past-the-end pointers." I think this is a mental shortcut we make that can lead us astray here. Of course, one-past-the-end pointers can't usually be dereferenced legally. But I think it's legal here because when (iq == ip), (p+1) points to a valid location. I don't see (at least in the C99 standard) why this code would be illegal. I realize that the code is not meant to represent C but rather LLVM IR, but surely, if this snippet is legal C code, then LLVM can't treat it as if it were UB? So that would mean the third optimization is incorrect here.
- ralfj 6y ago
  > if this snippet is legal C code, then LLVM can't treat it as if it were UB? It can in principle for the purpose of this example, since this is not the C code that the programmer originally wrote. This just means that if the snippet is legal C code, LLVM needs to do something extra during its translation to make this legal LLVM IR. But I am also happy to consider a different example, where this is the original C program. Is this legal C code? To my knowledge, basically everyone agrees that the answer is "no, this is UB". That includes both compilers (that will happily "miscompile" this code) and all formal semantics for C that I have seen so far. So I think you are in the minority with your interpretation of the standard. It's a shame that the standard is not precise enough to properly settle this question... If the standard were amended to explicitly make this code allowed in C, I think C compiler devs would revolt, as all major C compilers have some pretty crucial analysis that are fundamentally relying on this not being legal C code.
  - abra529 6y ago
    I see, thanks for the explanation. Just read your previous blog post that goes into more detail about this. [1] I don't know much about compilers, but I guess Defect Report #260 supports the interpretation that dereferencing q isn't the same as dereferencing (p+1), even inside an if block where p+1 == q: "[Implementations] may also treat pointers based on different origins as distinct even though they are bitwise identical." [2] [1] https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html [2] http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_260.htm http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_260.htm
Ericson2314 6y ago
I think the best solution is either `iq == ip` must be rewritten to false, or in the body of the branch the p and q regions are concatenated and then the alias analysis doesn't work. In general I like an approach of starting with the optomizations we want to do, and other sources non-determinism such as arbitrary layout we want to support, and then working backwards to fine the preconditions are program must abide by in order to for the compilation to not go wrong.
tsimionescu 6y ago
I wonder what the point of the first optimization in this specific case was. Why is LLVM replacing iq with ip in the body? I'm not questioning why it should be allowed to, but I don't understand why it would do it in this particular case. I also don't understand why that optimization is necessary to surface the problem. If we simply had a program that was doing char p[1], q[1] = {0}; uintptr_t ip = (uintptr_t)(p+1); *(char*)ip = 10; print(q[0]); Wouldn't applying just optimizations 2 and 3 on this code surface the same bug as discussed in the article?

262 points by ChrisSD 6y ago

This is a standalone sequel to "Pointers Are Complicated, or: What's in a Byte?" (https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html). Which has been discussed on HN 2020: https://news.ycombinator.com/item?id=24376797 https://news.ycombinator.com/item?id=24376797 2018: https://news.ycombinator.com/item?id=17604402 https://news.ycombinator.com/item?id=17604402

ralfj 6y ago
Oh, there was a repost in 2020, that explains the sudden spike in page hits that I saw earlier this year and couldn't trace back. ;)

vlovich123 6y ago

Does this have implications about the safety guarantees even safe Rust can make? It seems like incorrect optimization passes could result in bugs/security issues that are a byproduct of the compiler rather than the language itself. I wonder how big of an issue this is for Rust (relatively probably a bigger issue than for C/C++ where basic resource ownership bugs are more common).

jswrenn 6y ago
Yes, the pointer issues Ralf raises has implications about what operations Rust can make safe. An example Ralf posed to the safe transmute working group: a transmutation from a reference (i.e., a pointer with provenance) to one without (e.g., a "raw" pointer) or to a `usize` number cannot be safe. (Rust can safely provide these conversions via the `as` keyword, just not via the more general framework of transmutations). More broadly: Rust is very sensitive to LLVM bugs that inadvertently generate UB. The longstanding issues with `noalias` optimizations is the prime example of this: https://stackoverflow.com/a/57259339/7501301 https://stackoverflow.com/a/57259339/7501301
- Dylan16807 6y ago
  How could transmutation from a reference to a usize not be safe? Do you mean "and back"?
steveklabnik 6y ago
Yes, absolutely. https://github.com/rust-lang/rust/issues/28728 https://github.com/rust-lang/rust/issues/28728 is probably the most famous bug here, but many I-unsound bugs are similar. This would be the case even without this. Compilers are programs. Programs have bugs.
dbaupp 6y ago
It’s enough of an issue for C at least that a fully formally verified compiler exists: https://en.m.wikipedia.org/wiki/CompCert https://en.m.wikipedia.org/wiki/CompCert . That is, there’s proof that its (limited) optimisation passes are correct. There’s other approaches to assurance of compiled code too, such as seL4 which has proofs that the binary itself is correct, I believe.
- astrange 6y ago
  Note that fuzzing CompCert has still found bugs in it - because the entire compiler actually isn't verified. They've extended the proof over time. (Note that "formally verified" still does not mean "bug free", it just means it's a refinement of a proof that is also a program which can have bugs in it. And "formally" sounds like a weasel word.)
  - dbaupp 6y ago
    Ah, thanks for the clarification!
  - ralfj 6y ago
    Yeah, there were some bugs in the frontend and I think one in the backend. But there were zero bugs in the optimization pipeline, which is where typically the most subtle bucks lurk. For more details, see https://www.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf https://www.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf
gpm 6y ago
This isn't the first soundness/compilations bug, it won't be the last. This bug can be fixed, hopefully with some work this whole class of bugs can be made rarer. If you were relying on your safety guarantees to include a bug free compiler - rust isn't there yet and you should stop. If you're relying on a bug free happy path, rust is as close as any other language implementation (with one or two exceptions pointed out in sibling comments). So, I mean, if you're arguing that C/C++ programmers are culturally less repulsed by bugs... you might be right about that. Other than that I think it's about the same scale for C/C++ and rust - a bug is a bug no matter what language you wrote it in. The only fundamental implications I think it has is that maybe we need to put more of an emphasis on formalizing the memory model if we want to reduce the number of soundness bugs (something that a number of people are already doing some awesome work towards).

siraben 6y ago

> However, to make the argument that an optimization is correct, the exact semantics of LLVM IR (what the behavior of all possible programs is and when they have UB) needs to be documented. This is a great point as to why formal semantics of programming languages matters. Even if an optimization seems "obviously" correct, finicky things like introducing the possibility of UB can, as the post outlines, cascade into compiler passes that change the program more and more drastically. The post mentions that one need not go overly formal with the semantics, but I'll demonstrate what could happen when one does. One possible formulation of semantics is denotational semantics, which describes how to map a program source syntax into values, i.e. eval : Expr -> Val. So when we have an optimization opt : Expr -> Expr, the desired correctness property for that optimization is that Definition opt_correct (opt : Expr -> Expr) := forall (e : Expr), eval e = eval (opt e). When we want to rewrite, say e + 0 ==> e, for any expression e, the correctness can be stated and proved Theorem e_plus_0_to_e_correct : opt_correct e_plus_0_to_e. One claim in the blog post that correct optimization passes, e.g. opt1 and opt2 compose into another correct optimization pass can be stated as: Theorem opt_correct_compose (opt1, opt2 : Expr -> Expr) : opt_correct opt1 -> opt_correct op2 -> opt_correct (opt1 ∘ opt2). Which means given any two optimization passes opt1 and opt2 such that they are correct, composing them preserves correctness. The proof is simply; eval (opt1 (opt2 e)) = { since opt1 is correct } eval (opt2 e) = { since opt2 is correct } eval e

Dylan16807 6y ago
Not sure why you wanted to spend the time to prove "correct optimizations can be combined", but I take issue with that proof. It only works for optimizations that give code exactly the same behavior, which is severely limiting.
- mhh__ 6y ago
  Exactly the same as in the as-is rule or optimisations explicitly allowed by the standard?
  - Dylan16807 6y ago

dvt 6y ago

First of all: fantastic article. In-depth, insightful, and the examples are absolutely top-notch. On the razor's edge between accessible and profound. Hats off to the author. I will say that the problems seem to lie in a few interesting interlanguage quirks, and not so much on language specs. For example, LLVM and C have different definitions of "undefined behavior"[1] -- this is pointed out when looking at the `poison` identifier. In LLVM this might just be a weird side-effect we don't care about, but actually having an integer overflow is a big deal in C that introduces UB. Given the introduction, LLVM (incorrectly) introduces (C) UB at times. The second section, on pointer provenance, is much trickier, as there's no "obvious" UB introduced there. Further, I would argue that pointer provenance is a meta-language (or meta-computational) concept (which the Rust docs hint at), and logically speaking, might be intractable in the general case (I'd have to think about this more). Pointer arithmetic can fiddle with meta-state, whereas IRs like LLVM tend to focus purely on symbol manipulation. As a side note, I'd be curious what happens when LLVM sees something like: `void *p = &p` which is a self-referential pointer. What does it deduce about it? Does it optimize it away? Cool thought-provoking article. [1] https://www.cs.utah.edu/~regehr/llvm-ub.pdf https://www.cs.utah.edu/~regehr/llvm-ub.pdf

mjevans 6y ago
As usual; if a compiler knows about undefined behavior I would much rather it throw an error rather than optimize something the programmer didn't intend based on the compiler out-smarting a human's ability to be specific.
- klodolph 6y ago
  I've heard this proposal thrown around a lot on HN, but how would that even work? Can you describe how the compiler would do this, what patterns it would look for, and what error messages it would produce? For example, consider this: int factorial(int n) { int r = 1; for (int i = 1; i <= n; i++) { r *= i; } return r; } Since there are two instances of possible UB in the above function, what error messages would you like the compiler to produce? First of all, the compiler can assume that the loop terminates. This is a reasonable assumption from a human perspective—the loop is almost certainly intended to run N times. However, if n = INT_MAX, then there’s UB… and there’s no real way to know that n ≠ INT_MAX. You could argue that you want -fsanitize=undefined, where the compiler inserts checks at runtime. I don’t think this proposal is well formulated enough to be viable. Or consider something like this: void puts_safe(const char *s) { puts(s == NULL ? "(null)" : s) } void puts_with_len(const char *s) { printf("len = %zu\n", strlen(s)); puts_safe(s); } Do you want something like, Warning: puts_safe replaced with puts, because s != NULL, because strlen(NULL) is undefined I suspect there would be a mountain of false positives, and I would rather just use a static analyzer.

samatman 6y ago

Excellent article. It seems to me (and this is somewhat off-the-cuff) that compilers have another option: integers which are cast from pointers have provenance. That is, provenance is a taint: you can't clean it off through casting. So casting from pointer means the user can do integer-things like addition, but it means the compiler can't do integer-things like constant folding.

gizmo686 6y ago
I don't think that works. Consider the following (contrived) program: char* q[1] = {0}; int iq = (uintptr_t)q; int ip = 0; while (iq>0) { iq--; ip++; } char* p = (char*) ip; You can make this more efficient (albeit no less contrived) by iterating through iq bit-wise. Less contrived would be sending a pointer through some IPC mechanism (allowing it to be used as an opaque handle externally, while the program will blindly dereference it when it is passed back in); or even passing it within a program across compilation units. If you treat provenance like a taint, you need to track every way it could be propagated, and that does not seem solvable.
- samatman 6y ago
  So what are the optimizations here? iq is tainted, you can't hoist the loop out. You've said "I'm doing a weird thing here with an integer which used to be a pointer, you have to assume that it involves memory and treat it more like a pointer than an integer"
- saagarjha 6y ago
  You can solve it by deoptimizing accesses to q once it has been casted to an integer.

gens 6y ago

Pointers are "just" integers (unsigned integers of a size, that is). Most languages treat them differently (C assigns them a type, and a stride with it), but that is usually on top of them being integers. Pointers "point" to (are addresses to) bytes, as he said. If you want you can pack data to a resolution of a bit, and some languages help you do that as well. You can also do whatever you want with pointers (in some languages, ofc), like do bitwise operations on them. Aliasing them can be useful as well, in more then one way. Why not just get rid of pointers ? You know you can. Also, a byte is 0 .. 255. The hardest problem; naming things, and off by one errors.

steveklabnik 6y ago
They are not always integers. See this comment from the previous discussions on the other posts, for example: https://news.ycombinator.com/item?id=17607595 https://news.ycombinator.com/item?id=17607595
- gens 6y ago
  If 'b' is actually used then the compiler has to put 'a' in memory. Theoretically. He says that b is not changed, and does not "escape" (the scope of the code in question). In that case b is useless, and thus it doesn't really even exist. A compiler can "collapse" a lot of code into a fraction of it. That's a part of the "optimizing" part of "optimizing compiler". A compiler can put a value in a register. A compiler can do whatever it wants as long as the results are always the same as if it didn't do anything other then just translate to machine code. Pointer aliasing in C can be bad for the compiler as it can't be sure that it can optimize away something. That's why Fortran is faster, and why the restrict keyword was added to the C standard. And yea, i agree with him completely that a context should be made clear. Personally i'd like less voodoo in programming topics, but, on the other hand, this is still a young science and a lot of terminology is all around the place. ..Actually, scratch that, i found what i was interested in and don't really care about everything else.
  - klodolph 6y ago
    > If 'b' is actually used then the compiler has to put 'a' in memory. Theoretically, no—the “as if” rule applies. In practice, also no, because real compilers perform escape analysis and there are aggressive optimization passes for eliminating dead loads and dead stores. Just like the compiler can optimize out b and replace it with a reference to a, the compiler can optimize out the value stored in a but keep the reference to it stored in b. > In that case b is useless, and thus it doesn't really even exist. I don’t think this notion of “exist” has legs.

zokier 6y ago

Intuitively I feel that the first optimization is incorrect as it introduces out of bound write. I'll admit that this is very much subjective thing

TrianguloY 6y ago

I'm sorry but I don't fully understand the problem and that 'provenance' thing. For me the third optimization is the wrong one, for the same reason as this char i,j='0'; *(&i+1)='1'; cout << j; can't be optimized to cout << '0'; even though the j variable is also never overwritten directly. This reminds me of paralelization of nested loops with pragmas, where you need to specifically say that two pointers will never point to the same space, otherwise the compiler won't optimize the loop because 'it could happen'.

Someone 6y ago
If you think that, you’re giving up lots and lots of optimization opportunities. There’s zero guarantee that i and j are adjacent on the stack or even on the stack (there isn’t even a guarantee that there is a stack, but that’s a different subject); a compiler can decide to keep j in a register. That is very common in short functions, and essential for performance. It also would mean the compiler would have to load data from memory way more often, as ¿about? every pointer write might overwrite any memory.
- mehrdadn 6y ago
  But this is LLVM IR, not C. It feels like a trick question (hear me out). Either with IR semantics the code is already UB (as in C), or it isn't. If the code isn't UB, then why? The obvious assumption is that it's because LLVM IR treats this as a model of a concrete machine (where provenance isn't a thing), not as a C-like abstract machine with UB. In which case, the optimization #3 is clearly invalid. OTOH, if it is already UB, then the optimizations are fine, right? The only way I can see that we can implicate optimization #1 or #2 is by claiming LLVM IR has neither C semantics nor machine semantics, but with some kind of in-between wobbly semantics. There's nothing fundamentally wrong with that, but that's not what a reader would assume in the absence of other information. Especially not when the author writes "this program has two possible behaviors"—this clearly tells us there's no UB and that we should assume this is based on concrete machine semantics (where provenance isn't a thing). So, I would also say, given the info in the post prior to the conclusion, #3 has to be the culprit. I just can't implicate #1 or #2 based on the preceding text; to implicate those you'd have to pull assumptions out of thin air.

pierrebai 6y ago

The bug is clearly the writing past the end of an array. That is: *(p+1) = 10; If you start with a buggy program, that it stays buggy after optimizations is not surprising! Edit: what;s more, the original form of the program also did not write through the q pointer and could have had optimizer the print zero. In the first form, the author assumes the compiler can track the pointer q through q == qi and avoid the optimization that would print zero, but fail to track pointer q through pi + 1 == qi == q.

mskslal 6y ago
No, the original program writes through iq, which is well defined. Only the optimized program writes through p+1.

raverbashing 6y ago

Great article It just seems to me there's too much risk in "overoptimizing" especially in a weakly defined language like C with trigger happy optimizers and even more trigger happy "UB means let's go crazy" I take it as principle that no compilers should "throw their hands up" when detecting UB. Crash the program, don't just take that part out.

gpderetta 6y ago
Compilers don't detect UB (at least as optimizations are concerned), they assume no UB. If you want to detect UB, at least dynamically, compile with sanitizers.

mehrdadn 6y ago

If you enjoyed learning about pointer provenance (called "safely-derived pointer" in C++ [1]), you might find the recent addition of std::launder() [2] interesting. [1] https://en.cppreference.com/w/cpp/memory/gc/pointer_safety https://en.cppreference.com/w/cpp/memory/gc/pointer_safety [2] https://en.cppreference.com/w/cpp/utility/launder https://en.cppreference.com/w/cpp/utility/launder

comex 6y ago
Pointer safety is actually a separate concept from provenance. It was added to C++11 with the intent that it be used by garbage-collected implementations, but I'm not sure if anyone has ever properly implemented it. At least, the big three STL implementations have get_pointer_safety() always return pointer_safety::relaxed ("All pointers are considered valid and may be dereferenced or deallocated"), and there has been a proposal to remove pointer safety from future versions of the standard. [1] [1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2186r0.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p218...
- mehrdadn 6y ago
  That seems like a non-sequitur. How do "the intention is GC support" and "the C++ standard may remove concept" imply "these two are not the same concept"? To my knowledge safely-derived pointers are entirely about the notion that the derivation of a pointer matters, not just its value. Which is why you can't legally subtract pointers belonging to different arrays, for example. Which is precisely what is the same concept that provenance refers too... right? I don't see any differences pointed out in my readings or in your comment.

brundolf 6y ago

Before reading this I thought working on compilers might be a fun career direction

jcranmer 6y ago
To be fair, this kind of complication is relatively rare in compiler work. On the other hand, when it does come up, it does tend to create several hours-long meetings where there are more opinions on what the "obvious" semantics should be than people present. I've always been a stickler for trying to actually specify the obvious semantics to try to forestall these conversations.
- ralfj 6y ago
  Seeing how long the story of poison/undef is dragging out for LLVM, I'd say it's more of a years-long process than an hours-long one. ;) But still, the most important part is that there's a discussion at all, and the desire to properly solve this problem.
  - jcranmer 6y ago
    Oh, finishing the meetings may take months or years, but the meetings themselves are only a few hours long.
lambdatronics 6y ago
If more of the literature were written like this, I'd be more inclined to it.

deathanatos 6y ago

I am not 100% convinced on the third transformation, > The final optimization notices that q is never written to, so we can replace q[0] by its initial value 0: Can we? q is at a language level, possibly aliased with the write immediately above to (p+1), and we know it's aliased because of the if statement. Now, that's a C rule, and the article does note that it is only using C syntax to express LLVM. So, I guess, what are LLVM's aliasing rules? (Indeed, there was originally a write to q, which we replaced with an aliased write to q, so it seems to me that on the whole, the various optimizations are assuming different things about aliasing.)

lmm 6y ago
> Can we? q is at a language level, possibly aliased with the write immediately above to (p+1) It's not, because writing to a one-past-the-end pointer is UB. > Indeed, there was originally a write to q, which we replaced with an aliased write to q, so it seems to me that on the whole, the various optimizations are assuming different things about aliasing. That optimization pass doesn't know anything about aliasing, it just replaced an integer with another integer that's equal to the first.

Asooka 6y ago

Personally I just compile my code with "-fwrapv -fno-strict-aliasing". It's not standard C, but every compiler supports an analogue to those class and it saves so many headaches from UB-optimising passes, the tiny loss in performance is worth it. Integer overflow and pointer aliasing are way too easy to accidentally hit in a C program, the two should have never been made UB, but perhaps added as a pragma to annotate definitely safe code that can benefit from the optimisation.

ralfj 6y ago
Note that all of the optimizations I used in the main part (not the warm-up) of my post are still performed even with "-fwrapv -fno-strict-aliasing". So this does not avoid the issues I am talking about.

tsimionescu 6y ago

Thinking about this quite a bit, I see the second optimization as pretty obviously incorrect - not because of provenance, but because it acts as if pointer-to-integer-to-pointer casting is value-preserving, which is not at all guaranteed by the C abstract machine. In particular, `p != q && ((uintptr_t)p == (uintptr_t)q)` can be true according to the C standard. Instead of trying to track provenance, simply considering that the transformation between pointers and integers is not value preserving seems to be a simpler rule. If we want to reason about optimizations using the C abstract machine, we can't consider these transformations to be value-preserving, even if they happen to be in the real machines that LLVM targets (and if they start reasoning for the real machine instead of the C abstract machine, a lot of other optimizations are invalid).

abra529 6y ago
Is it not guaranteed? Looking at this question [1] on StackOverflow and the quotes from the standard included in the question, it seems that the value should be preserved. (It raises the issue of whether (char※)iq should technically be (char※)(void※)iq if this were C code, but the (void※) cast can be inserted without changing anything about the problems discussed in the article.) [1] https://stackoverflow.com/q/34291377 https://stackoverflow.com/q/34291377
- tsimionescu 6y ago
  Yes, you are absolutely right, so my argument flies out the window. Thanks for finding the relevant C spec!
magicalhippo 6y ago
For me it is the third optimization which is incorrect. I mean, if you replace the pointers with array indexes, then you'd end up with something like this after the second optimization: char data[N]; uintptr_t p = rand_int(N); uintptr_t q = rand_int(N); data[q] = 0; data[p] = 0; uintptr_t ip = (p+1); uintptr_t iq = q; if (iq == ip) { data[p+1] = 10; print(data[q]); } Surely no sane compiler would replace the "data[q]" in the print statement with 0? Or did the caffeine not kick in yet?

fjfaase 6y ago

I think that the main problem is that pointers are a too low-level concept (like assembly language compared to high-level programming languages) that are used to implement various more high-level concepts. I have not come across a language that does have pointers (some functional languages lack pointers all together) and has these high-level concepts. There is a great difference between a pointer that points to a complex value and a pointer, that like a database cursor, points to a certain part in a complex value, either with the purpose to query this value or to make some change to the value.

andrewflnr 6y ago

For purposes of future language design: why not just ban conversion from integers to pointers? Pointers have metadata that integers can't provide, therefore the conversion is impossible, QED. What's the use case for it outside of, say, binary executable loaders?

adwn 6y ago
> What's the use case for it outside of, say, binary executable loaders? If you're doing low-level optimizations, and you know that your pointed-to objects are, say, 8-byte-aligned, then you can use the lower 3 bits of your pointer for storing metadata. In certain cases, that can be immensely useful. Some GC implementations use this trick, for example.
- ralfj 6y ago
  One could imagine a specific primitive operation in the language that lets you adjust the low bits of a pointer without casting it to an integer and back.

einpoklum 6y ago

I remember a CppCon talk which covered how poison and UB work in LLVM IR, probably in 2018 or 2019, but I forget which one it was.

abra529 6y ago

Commenters here as well as the author seem content with asserting that under C semantics, the code after the second optimization exhibits UB when it dereferences (p+1). Is it really UB? Here's the snippet for reference: char p[1], q[1] = {0}; uintptr_t ip = (uintptr_t)(p+1); uintptr_t iq = (uintptr_t)q; if (iq == ip) { *(p+1) = 10; // <- This line changed print(q[0]); } From the article: "LLVM IR (just like C) does not permit memory accesses through one-past-the-end pointers." I think this is a mental shortcut we make that can lead us astray here. Of course, one-past-the-end pointers can't usually be dereferenced legally. But I think it's legal here because when (iq == ip), (p+1) points to a valid location. I don't see (at least in the C99 standard) why this code would be illegal. I realize that the code is not meant to represent C but rather LLVM IR, but surely, if this snippet is legal C code, then LLVM can't treat it as if it were UB? So that would mean the third optimization is incorrect here.

ralfj 6y ago
> if this snippet is legal C code, then LLVM can't treat it as if it were UB? It can in principle for the purpose of this example, since this is not the C code that the programmer originally wrote. This just means that if the snippet is legal C code, LLVM needs to do something extra during its translation to make this legal LLVM IR. But I am also happy to consider a different example, where this is the original C program. Is this legal C code? To my knowledge, basically everyone agrees that the answer is "no, this is UB". That includes both compilers (that will happily "miscompile" this code) and all formal semantics for C that I have seen so far. So I think you are in the minority with your interpretation of the standard. It's a shame that the standard is not precise enough to properly settle this question... If the standard were amended to explicitly make this code allowed in C, I think C compiler devs would revolt, as all major C compilers have some pretty crucial analysis that are fundamentally relying on this not being legal C code.
- abra529 6y ago
  I see, thanks for the explanation. Just read your previous blog post that goes into more detail about this. [1] I don't know much about compilers, but I guess Defect Report #260 supports the interpretation that dereferencing q isn't the same as dereferencing (p+1), even inside an if block where p+1 == q: "[Implementations] may also treat pointers based on different origins as distinct even though they are bitwise identical." [2] [1] https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html [2] http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_260.htm http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_260.htm

Ericson2314 6y ago

I think the best solution is either `iq == ip` must be rewritten to false, or in the body of the branch the p and q regions are concatenated and then the alias analysis doesn't work. In general I like an approach of starting with the optomizations we want to do, and other sources non-determinism such as arbitrary layout we want to support, and then working backwards to fine the preconditions are program must abide by in order to for the compilation to not go wrong.

tsimionescu 6y ago

I wonder what the point of the first optimization in this specific case was. Why is LLVM replacing iq with ip in the body? I'm not questioning why it should be allowed to, but I don't understand why it would do it in this particular case. I also don't understand why that optimization is necessary to surface the problem. If we simply had a program that was doing char p[1], q[1] = {0}; uintptr_t ip = (uintptr_t)(p+1); *(char*)ip = 10; print(q[0]); Wouldn't applying just optimizations 2 and 3 on this code surface the same bug as discussed in the article?