Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

ralfj.de

Post reply on HN
Print view View original

51–60 of 135 posts

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

#51

Post by Dylan16807 »

jswrenn wrote: post #4
vlovich123 wrote: post #3

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).

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 transmutation…

How could transmutation from a reference to a usize not be safe? Do you mean "and back"?

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

#52

Post by mehrdadn »

Someone wrote: post #18
TrianguloY wrote: post #15

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 can't be optimized to cout 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 s…

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 d…

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.

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

#53

Post by mehrdadn »

comex wrote: post #48
mehrdadn wrote: post #42

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 [2] https://en.cppreference.com/w/cpp/utility/launder

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…

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.

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

#54

Post by anderskaseorg »

dooglius wrote: post #45
simias wrote: post #40

Earlier quoted context omitted.

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…

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 t…

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.

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

#55

Post by deathanatos »

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.)

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

#56

Post by MaxBarraclough »

badsectoracula wrote: post #39
steveklabnik wrote: post #12

Earlier quoted context omitted.

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

> What happens when 'a' is allocated to a CPU register? When the & operator is used on 'a' it should mark it as unsafe to place the 'a' on a CPU register - CPU allocation is an optimization and optimizations should never affect how the program behaves (except making it run faster, of course) and as such they should only be applied when the compiler can be sure that they're safe to do so. (and yes, the same applies on…

> When the & operator is used on 'a' it should mark it as unsafe to place the 'a' on a CPU register

Not necessarily, as the compiler might be smart enough to adjust the other operations and enregister the a variable anyway. There's no ceiling on how smart the optimiser can be. An extreme case:

    int a = 42;
    &a;
    // do things with 'a'
This uses the & operator but doesn't even save the result of the expression, so the compiler will presumably chop that whole second statement as dead code, and may still be able to enregister a.

> optimizations should never affect how the program behaves (except making it run faster, of course)

Most of the time a C++ compiler's optimiser must preserve observable behaviour, provided undefined behaviour is not invoked, but not always. C++ permits elision of certain copy/move operations even if this changes observable behaviour. [0]

Also, if the program is multithreaded and has race conditions, an optimiser isn't required to ensure that the relative speeds of different threads remains unchanged, which may lead to a change in observed behaviour. Of course, in such a case, except making it run faster contradicts never affect how the program behaves, so you've sort of covered that anyway.

[0] https://stackoverflow.com/a/12953129/

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

#57

Post by simias »

dooglius wrote: post #45
simias wrote: post #40

Earlier quoted context omitted.

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…

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 t…

I don't find my example contrived at all, having functions assuming non-NULL pointers call other subroutines that defend against such a thing is definitely a routine thing in my experience. Maybe "do_substuff" is called in contexts where the pointer could be NULL, or maybe its developer was paranoid.

I don't think it's reasonable to expect compilers to issue less optimized code to defend against coders doing smart things that are well beyond the scope of the standard. If you want to play fast and loose with segfault handlers then be my guest, but if you want to play with fire you better know what you're doing.

Note that many of C's UBs are also generally effectively unportable, different systems will react differently to things like NULL pointer dereferences (segfault, access to some mapped memory, access to nothing at all or a special handler like the one you described) and signed overflow (overflow to 2s complement, saturation, trap etc...).

I think blaming UBs is frankly the wrong target. The problem with C is that it doesn't let you express those constraints to let the compiler enforce them and let you know when you're doing something wrong. I can't tell the compiler "this pointer is not nullable" and have it keep track of it for me, warning me if I mess up. In contrast in a language like Rust I could use an Option type to encode this, and I get a compilation error if I have a mismatch.

That's what I want to see in a more modern C, not a babysitting compiler that emits suboptimal code because it's trying to make my coding mistakes somewhat less mistakeful.

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

#58

Post by anderskaseorg »

dvt wrote: post #34
klodolph wrote: post #22

Earlier quoted context omitted.

> 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? 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 otherwi…

> 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-referentia...

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.)

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

#59

Post by jcranmer »

dvt wrote: post #8

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 `po…

> 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.

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

#60

Post by rwj »

sharpneli wrote: post #35
dvt wrote: post #8

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 `po…

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 i…

Your comment about char* aliasing everything is for C, not LLVM.
Post reply on HN