7 ms·

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

by 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.
  - mjevans 6y ago
    What I want is for the compiler to have a mode (which ideally would be enabled by default, at least with modern compile targets) that never optimizes based on undefined behavior. It would do this by handing any UB as an error and making the programmer write a correct program that lacks UB through informing the programmer where undefined behavior has been proven by the compiler. This would improve both the code and the programmer's skills, rather than trying to make each out-think the other.
    - ChrisSD 6y ago
      Detecting UB is far harder than the compiler simply assuming there is no UB. That said, there are already tools to do it for some cases (but far from all). They're not often used in C/C++, perhaps because they're slow.
    - GolDDranks 6y ago
      So, do you mean that in the above loop example, it would require you to prove somehow that the loop always finishes, or if the programmer fails to do that, fail with "possibly infinite loop" error? In what language/system you would require that proof?
    - klodolph 6y ago
      What you are describing is formal methods. You can take a subset of C, use a formally-verified toolchain, and write your own formally-verified C code using proof systems. Or perhaps what you want is a different language. It’s just that what you’re describing—having the compiler detect UB and warn you about it, but still letting you write C code—without the burden of also writing correctness proofs using some formalism—it’s just not a viable option. From a usability perspective, if you turn on aggressive static analysis / warning settings like this, what you usually end up with is programmers that just start ignoring warnings or turning them off, except for greenfield projects. C’s semantics don’t make this kind of thing easy. If you have a greenfield project and you are fighting the language this hard, that’s precisely the time when using a different language is the most viable option.
    - saagarjha 6y ago
- simias 6y ago
  It would sometimes work but I think this (very common comment) misses the general point, there's absolutely fine and non buggy on warning-worthy code that can be optimized away if the compiler relies on UB. A very simple example: void do_stuff(int *some_ptr) { do_substuff(some_ptr); *some_ptr += 2; } static void do_substuff(int *some_ptr) { if (some_ptr != NULL) { *some_ptr = 10; } } do_stuff calls a subroutine that does a NULL pointer check, then unconditionally dereferences the same pointer. From this the compiler, if it decides to inline that code, can decide to optimize the NULL check away since if the pointer is NULL it's guaranteed to trigger UB. The logic being "clearly the programmer assumes that the pointer can't be NULL here, so thanks to UB rules I can too". There's nothing wrong with this code, there's no reason to emit a warning. Distinguishing between "of course that's a reasonable optimization, that's probably what the developer intended" and "wow this compiler is so dumb, obviously I never meant for that to happen" is a very tough nut to crack. At this point you can push the blame to the C language not being expressive enough, in this case not giving us a way to express nullable vs. non-nullable pointers within the language, which forces the compiler to lean onto these UB heuristics to optimize.
  - dooglius 6y ago
    Even in your heavily contrived example, I can think of cases where the optimization isn't what the programmer wants. For instance, I might have a special handler via userfaultfd(2) that detects if I'm doing an increment of the null pointer and handles it in some special way, but can't handle just setting it to 10. For a more real example, I might have acquired a lock around do_substuff, and I might be okay with the thread segfaulting only if the lock wasn't held.
    - anderskaseorg 6y ago
      If the programmer really needs reads and writes through particular pointers to happen in a particular sequence, because the target memory follows different rules than the language ordinarily allows the compiler to assume, then it’s the programmer’s responsibility to use the annotation provided by the language for exactly that purpose: volatile. If the compiler had to assume that every pointer needs to be treated as volatile, just about all generated code would be be slowed down dramatically. As for locks, the language already has rules about which memory access are allowed to be reordered across lock acquire and release calls. Otherwise locks wouldn’t work correctly at all.
- Diggsey 6y ago
  The compiler very rarely knows that UB exists in the program. To give a concrete example: the compiler sees this: ``` while (<expr>) { if (p == 0) { do_thing(); } *p = 42; } ``` In this case, the compiler wants to move `do_thing()` outside the loop because it's expensive. It also knows that it would be UB for this branch to execute if `*p = 42` executes, because that would result in UB. Therefore the compiler can assume that if the loop runs at least once, then `p != 0`. At no point does the compiler have any information about whether the program is in fact UB.
klodolph 6y ago
> As a side note, I'd be curious what happens when LLVM sees something like: `void <asterisk>p = &p` which is a self-referential pointer. What does it deduce about it? Does it optimize it away? Why would it do anything special here? This is not really different from something like this: struct a { struct a *p; }; struct a x = { &a }; The only real difference is that the void version involves a cast, because the type is otherwise impossible to express in C.
- dvt 6y ago
  > Why would it do anything special here? This is not really different from something like this: Yeah, I suppose you're right. I was Googling potential interesting cases and ran across this one[1] which made me think of weird edge cases w.r.t. self-reference. [1] https://stackoverflow.com/questions/20596856/self-referential-pointer-arithmetic https://stackoverflow.com/questions/20596856/self-referentia...
  - anderskaseorg 6y ago
    There isn’t anything weird about this. A circularly linked list is a common data structure that, when empty, has a pointer pointing to itself. Self-referential structures can be optimized in accordance with all the usual rules. If there are no other references to them, they can be optimized away. (This optimization is implemented by using a flood fill to mark everything that’s used, and then removing everything else, so that circular references need no special treatment.)
sharpneli 6y ago
I'm pretty sure there is no UB in the second part. It's just LLVM bug. The pointer comparison is valid (pointer to and object and to an another object that's one past the end MAY compare equal). The write is valid. Reads and writes to char* always alias everything. Unless the compiler can prove that no writes happened it has to emit a read. So if it "forgets" due to the uintptr_t cast where the char* came from then it must assume that it can be pretty much arbitrary and must emit a read.
- rwj 6y ago
  Your comment about char* aliasing everything is for C, not LLVM.
- temac 6y ago
  Everybody seems to agree it is an LLVM bug, but "UB" is overloaded. There is no "C/C++ UB" in the original program, but the optimizers can introduce "LLVM UB" in IR form, which then results in something substantially equivalent to what the mock transformed source codes shown for illustration would probably be compiled to. And introducing UB when there was none in the source code means there is a compiler bug. On your remark about char*, it is an universal type alias, but I don't think it is an universal provenance alias, sadly I don't think such a thing even exist de-facto, and it will not even exist more formally when considering the PVNI-ae-ud model that is being cooked. Probably unwise to lean as usual on the aggressive optimisations side without even proving that the perf impact is that much interesting, evaluating the security / quality and education impact, if you ask me. And even more problematic without even providing an escape hatch (1). But I know very well that state of mind has just won for now and I have to cope with it. Even more C programs will be retroactively declared completely incorrect (and not even just not-portable) because the compilers went too agressive at one point and the standard just standardized their aggressiveness instead of telling implementers to just stop being crazy. (1) beyond, for some potential programs that would be otherwise impossible to express in C/C++, exposing all the pointers. Well exposing all the pointers would be cute but the result would not be that much different from not having that kind of "opti". Plus you would have to actually expose all your target pointers, so it is not really source compatible with unmodified existing codebases. So a per-access or at least per-pointer-doing-the-accesses universal provenance alias is needed to get a serious escape hatch. I'm also not extremely sure we can actually implement a memory allocator in C or C++ today (with whatever the modern compiler are "optimizing" with their partly informal provenance rules), nor that we will be able to with PVNI-ae-ud (broadly same thing except slightly debugged). (Or maybe it will merely constrain the implementation? not sure anyway)
Dylan16807 6y ago
> 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). Unless we define provenance to only work within certain easy-to-calculate boundaries. But for the general case, sure, just don't optimize when there's uncertainty.
jcranmer 6y ago
> 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. This doesn't matter. LLVM IR is not C, and it is not convertible to C, as it implements a superset of C semantics, which includes some cases where behavior that is undefined in C is well-defined in LLVM IR. Once C is lowered to LLVM IR, it doesn't matter what C says is or isn't undefined behavior, because there is no longer any C code being considered.
- dvt 6y ago
  > This doesn't matter. Maybe I expressed myself a bit too literally, but I wouldn't say that how LLVM handles UB "doesn't matter." Look at how Clang compiles undefined behavior vs GCC (for example)[1]. A bit tautological, but different ways of handling UB can lead to different ways UB behaves. > LLVM IR is not C, and it is not convertible to C... This isn't strictly true. There used to be an "official" C(pp) backend, which has been recently resurrected[2]. You can definitely go from LLVM to C -- probably won't be very readable, though. [1] https://blog.llvm.org/posts/2011-05-21-what-every-c-programmer-should-know_21/ https://blog.llvm.org/posts/2011-05-21-what-every-c-programm... [2] https://github.com/JuliaComputing/llvm-cbe https://github.com/JuliaComputing/llvm-cbe
  - lambdatronics 6y ago
    > different ways of handling UB can lead to different ways UB behaves. Ha! If something depends on how 'undefined behavior' behaves, then it's not really undefined, is it? :D
ralfj 6y ago
Thank you so much for the feedback :) . I spent more time on this than on my usual post, so it is great to hear that that has paid off.

by dvt 6y ago

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.
- mjevans 6y ago
  What I want is for the compiler to have a mode (which ideally would be enabled by default, at least with modern compile targets) that never optimizes based on undefined behavior. It would do this by handing any UB as an error and making the programmer write a correct program that lacks UB through informing the programmer where undefined behavior has been proven by the compiler. This would improve both the code and the programmer's skills, rather than trying to make each out-think the other.
  - ChrisSD 6y ago
    Detecting UB is far harder than the compiler simply assuming there is no UB. That said, there are already tools to do it for some cases (but far from all). They're not often used in C/C++, perhaps because they're slow.
  - GolDDranks 6y ago
    So, do you mean that in the above loop example, it would require you to prove somehow that the loop always finishes, or if the programmer fails to do that, fail with "possibly infinite loop" error? In what language/system you would require that proof?
  - klodolph 6y ago
    What you are describing is formal methods. You can take a subset of C, use a formally-verified toolchain, and write your own formally-verified C code using proof systems. Or perhaps what you want is a different language. It’s just that what you’re describing—having the compiler detect UB and warn you about it, but still letting you write C code—without the burden of also writing correctness proofs using some formalism—it’s just not a viable option. From a usability perspective, if you turn on aggressive static analysis / warning settings like this, what you usually end up with is programmers that just start ignoring warnings or turning them off, except for greenfield projects. C’s semantics don’t make this kind of thing easy. If you have a greenfield project and you are fighting the language this hard, that’s precisely the time when using a different language is the most viable option.
  - saagarjha 6y ago
simias 6y ago
It would sometimes work but I think this (very common comment) misses the general point, there's absolutely fine and non buggy on warning-worthy code that can be optimized away if the compiler relies on UB. A very simple example: void do_stuff(int *some_ptr) { do_substuff(some_ptr); *some_ptr += 2; } static void do_substuff(int *some_ptr) { if (some_ptr != NULL) { *some_ptr = 10; } } do_stuff calls a subroutine that does a NULL pointer check, then unconditionally dereferences the same pointer. From this the compiler, if it decides to inline that code, can decide to optimize the NULL check away since if the pointer is NULL it's guaranteed to trigger UB. The logic being "clearly the programmer assumes that the pointer can't be NULL here, so thanks to UB rules I can too". There's nothing wrong with this code, there's no reason to emit a warning. Distinguishing between "of course that's a reasonable optimization, that's probably what the developer intended" and "wow this compiler is so dumb, obviously I never meant for that to happen" is a very tough nut to crack. At this point you can push the blame to the C language not being expressive enough, in this case not giving us a way to express nullable vs. non-nullable pointers within the language, which forces the compiler to lean onto these UB heuristics to optimize.
- dooglius 6y ago
  Even in your heavily contrived example, I can think of cases where the optimization isn't what the programmer wants. For instance, I might have a special handler via userfaultfd(2) that detects if I'm doing an increment of the null pointer and handles it in some special way, but can't handle just setting it to 10. For a more real example, I might have acquired a lock around do_substuff, and I might be okay with the thread segfaulting only if the lock wasn't held.
  - anderskaseorg 6y ago
    If the programmer really needs reads and writes through particular pointers to happen in a particular sequence, because the target memory follows different rules than the language ordinarily allows the compiler to assume, then it’s the programmer’s responsibility to use the annotation provided by the language for exactly that purpose: volatile. If the compiler had to assume that every pointer needs to be treated as volatile, just about all generated code would be be slowed down dramatically. As for locks, the language already has rules about which memory access are allowed to be reordered across lock acquire and release calls. Otherwise locks wouldn’t work correctly at all.
Diggsey 6y ago
The compiler very rarely knows that UB exists in the program. To give a concrete example: the compiler sees this: ``` while (<expr>) { if (p == 0) { do_thing(); } *p = 42; } ``` In this case, the compiler wants to move `do_thing()` outside the loop because it's expensive. It also knows that it would be UB for this branch to execute if `*p = 42` executes, because that would result in UB. Therefore the compiler can assume that if the loop runs at least once, then `p != 0`. At no point does the compiler have any information about whether the program is in fact UB.

klodolph 6y ago

> As a side note, I'd be curious what happens when LLVM sees something like: `void <asterisk>p = &p` which is a self-referential pointer. What does it deduce about it? Does it optimize it away? Why would it do anything special here? This is not really different from something like this: struct a { struct a *p; }; struct a x = { &a }; The only real difference is that the void version involves a cast, because the type is otherwise impossible to express in C.

dvt 6y ago
> Why would it do anything special here? This is not really different from something like this: Yeah, I suppose you're right. I was Googling potential interesting cases and ran across this one[1] which made me think of weird edge cases w.r.t. self-reference. [1] https://stackoverflow.com/questions/20596856/self-referential-pointer-arithmetic https://stackoverflow.com/questions/20596856/self-referentia...
- anderskaseorg 6y ago
  There isn’t anything weird about this. A circularly linked list is a common data structure that, when empty, has a pointer pointing to itself. Self-referential structures can be optimized in accordance with all the usual rules. If there are no other references to them, they can be optimized away. (This optimization is implemented by using a flood fill to mark everything that’s used, and then removing everything else, so that circular references need no special treatment.)

sharpneli 6y ago

I'm pretty sure there is no UB in the second part. It's just LLVM bug. The pointer comparison is valid (pointer to and object and to an another object that's one past the end MAY compare equal). The write is valid. Reads and writes to char* always alias everything. Unless the compiler can prove that no writes happened it has to emit a read. So if it "forgets" due to the uintptr_t cast where the char* came from then it must assume that it can be pretty much arbitrary and must emit a read.

rwj 6y ago
Your comment about char* aliasing everything is for C, not LLVM.
temac 6y ago
Everybody seems to agree it is an LLVM bug, but "UB" is overloaded. There is no "C/C++ UB" in the original program, but the optimizers can introduce "LLVM UB" in IR form, which then results in something substantially equivalent to what the mock transformed source codes shown for illustration would probably be compiled to. And introducing UB when there was none in the source code means there is a compiler bug. On your remark about char*, it is an universal type alias, but I don't think it is an universal provenance alias, sadly I don't think such a thing even exist de-facto, and it will not even exist more formally when considering the PVNI-ae-ud model that is being cooked. Probably unwise to lean as usual on the aggressive optimisations side without even proving that the perf impact is that much interesting, evaluating the security / quality and education impact, if you ask me. And even more problematic without even providing an escape hatch (1). But I know very well that state of mind has just won for now and I have to cope with it. Even more C programs will be retroactively declared completely incorrect (and not even just not-portable) because the compilers went too agressive at one point and the standard just standardized their aggressiveness instead of telling implementers to just stop being crazy. (1) beyond, for some potential programs that would be otherwise impossible to express in C/C++, exposing all the pointers. Well exposing all the pointers would be cute but the result would not be that much different from not having that kind of "opti". Plus you would have to actually expose all your target pointers, so it is not really source compatible with unmodified existing codebases. So a per-access or at least per-pointer-doing-the-accesses universal provenance alias is needed to get a serious escape hatch. I'm also not extremely sure we can actually implement a memory allocator in C or C++ today (with whatever the modern compiler are "optimizing" with their partly informal provenance rules), nor that we will be able to with PVNI-ae-ud (broadly same thing except slightly debugged). (Or maybe it will merely constrain the implementation? not sure anyway)

Dylan16807 6y ago

> 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). Unless we define provenance to only work within certain easy-to-calculate boundaries. But for the general case, sure, just don't optimize when there's uncertainty.

jcranmer 6y ago

> 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. This doesn't matter. LLVM IR is not C, and it is not convertible to C, as it implements a superset of C semantics, which includes some cases where behavior that is undefined in C is well-defined in LLVM IR. Once C is lowered to LLVM IR, it doesn't matter what C says is or isn't undefined behavior, because there is no longer any C code being considered.

dvt 6y ago
> This doesn't matter. Maybe I expressed myself a bit too literally, but I wouldn't say that how LLVM handles UB "doesn't matter." Look at how Clang compiles undefined behavior vs GCC (for example)[1]. A bit tautological, but different ways of handling UB can lead to different ways UB behaves. > LLVM IR is not C, and it is not convertible to C... This isn't strictly true. There used to be an "official" C(pp) backend, which has been recently resurrected[2]. You can definitely go from LLVM to C -- probably won't be very readable, though. [1] https://blog.llvm.org/posts/2011-05-21-what-every-c-programmer-should-know_21/ https://blog.llvm.org/posts/2011-05-21-what-every-c-programm... [2] https://github.com/JuliaComputing/llvm-cbe https://github.com/JuliaComputing/llvm-cbe
- lambdatronics 6y ago
  > different ways of handling UB can lead to different ways UB behaves. Ha! If something depends on how 'undefined behavior' behaves, then it's not really undefined, is it? :D

ralfj 6y ago

Thank you so much for the feedback :) . I spent more time on this than on my usual post, so it is great to hear that that has paid off.