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

71–80 of 135 posts

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

#71

Post by mehrdadn »

lmm wrote: post #69
mehrdadn wrote: post #52

Earlier quoted context omitted.

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…

> Either with IR semantics the code is already UB (as in C), or it isn't. If the code isn't UB, then why? With C-like semantics the code isn't UB. Why would it be? Taking a one-past-the-end pointer is legit, comparing it is legit, casting a pointer to an integer is legit.

Comparing pointers derived from entirely different objects (or arrays) isn't legit. See here: https://www.viva64.com/en/b/0576/

"Pointer arithmetic is only defined for pointers pointing into array objects or one past the last element. Comparing pointers for equality is defined if both pointers are derived from the same (multidimensional) array object. Thus, if two pointers point to different array objects, then these array objects must be subaggregates of the same multidimensional array object in order to compare them. Otherwise this leads to undefined behavior."

For the purpose of comparisons, C++ lets you partially work around this via std::less et al, which are nevertheless guaranteed to implemented in such a way as to give you a total ordering among all pointers. Even then, I don't think you can freely interchange pointers that compare "equal" in that sense; the same object may have pointers with different representations, all of which compare "equal" for ordering purposes but which don't have an identical representation. (See segmented memory models, for instance.) I also don't recall if C has a similar workaround (it might not).

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

#72

Post by GolDDranks »

mjevans wrote: post #65
klodolph wrote: post #23

Earlier quoted context omitted.

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 Since there are two instances of possible UB in the above function, what error messages would you like the compiler to produce? First…

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

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?

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

#73

Post by klodolph »

mjevans wrote: post #65
klodolph wrote: post #23

Earlier quoted context omitted.

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 Since there are two instances of possible UB in the above function, what error messages would you like the compiler to produce? First…

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

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.

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

#74

Post by klodolph »

SAI_Peregrinus wrote: post #67
anderskaseorg wrote: post #54

Earlier quoted context omitted.

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

To be extra pedantic, that's not what volatile does. Volatile ensures that access through the variable must behave strictly according to the rules of the C abstract machine, but the definition of access is implementation defined . A compiler author could define "access" to be "reads from the variable" or "writes to the variable", or neither, and make the entire keyword useless. As long as they document that somewhere…

Your comment is technically correct, but the original description of “volatile” in the parent comment is much clearer. It may be fun to imagine what would happen if the compiler writer were malicious, but it doesn’t really help us understand C.

Just like C compilers assume that the program is correct, the writers of the C standard assume that the people reading it are not insane or malicious.

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

#75

Post by saagarjha »

mjevans wrote: post #65
klodolph wrote: post #23

Earlier quoted context omitted.

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 Since there are two instances of possible UB in the above function, what error messages would you like the compiler to produce? First…

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

This is untenable in the general case. For example, consider this function:

  int dereference(int *p) {
      return *p;
  }
What should the compiler do in this case? If I pass (int *)0x1283412 into this function, that's undefined behavior…should it just always warn?

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

#76

Post by saagarjha »

gizmo686 wrote: post #14
samatman wrote: post #10

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.

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

You can solve it by deoptimizing accesses to q once it has been casted to an integer.

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

#77

Post by lmm »

mehrdadn wrote: post #71
lmm wrote: post #69

Earlier quoted context omitted.

> Either with IR semantics the code is already UB (as in C), or it isn't. If the code isn't UB, then why? With C-like semantics the code isn't UB. Why would it be? Taking a one-past-the-end pointer is legit, comparing it is legit, casting a pointer to an integer is legit.

Comparing pointers derived from entirely different objects (or arrays) isn't legit. See here: https://www.viva64.com/en/b/0576/ "Pointer arithmetic is only defined for pointers pointing into array objects or one past the last element. Comparing pointers for equality is defined if both pointers are derived from the same (multidimensional) array object. Thus, if two pointers point to different array objects, then these…

> Comparing pointers derived from entirely different objects (or arrays) isn't legit.

The quote from the standard in your article contradicts the part you quoted:

> Two pointers compare equal if and only if both are null pointers, both are pointers to the same object (including a pointer to an object and a subobject at its beginning) or function, both are pointers to one past the last element of the same array object, or one is a pointer to one past the end of one array object and the other is a pointer to the start of a different array object that happens to immediately follow the first array object in the address space.

But in any case the program in the article doesn't compare pointers; it casts the pointers to integers and then compares those integers, which is always legitimate.

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

#78

Post by dataflow »

lmm wrote: post #77
mehrdadn wrote: post #71

Earlier quoted context omitted.

Comparing pointers derived from entirely different objects (or arrays) isn't legit. See here: https://www.viva64.com/en/b/0576/ "Pointer arithmetic is only defined for pointers pointing into array objects or one past the last element. Comparing pointers for equality is defined if both pointers are derived from the same (multidimensional) array object. Thus, if two pointers point to different array objects, then these…

> Comparing pointers derived from entirely different objects (or arrays) isn't legit. The quote from the standard in your article contradicts the part you quoted: > Two pointers compare equal if and only if both are null pointers, both are pointers to the same object (including a pointer to an object and a subobject at its beginning) or function, both are pointers to one past the last element of the same array object…

They don't contradict to my understanding (see below).

First, regarding comparing pointers vs. integers, that goes back to what I said about identical pointer representations as an integer. Just because two pointers point to the same memory location, it does not mean they have an identical representation as an integer. This might be difficult to understand if you think of a linear address space, but it's easier to understand once you're familiar with segmentation. Pointers derived in different ways can ostensibly have different representations due to nonlinear (e.g., segmented) memory models, and yet nevertheless point to the same memory location. Hence it is actually undefined whether they compare equal. There is no canonicalization procedure that ensures they result in the same integer representation.

One pointer (not sure if pun intended) that might help you see this: consider words like "follows" aren't even necessarily well-defined for nonlinear address spaces—IIRC they're defined not with respect to the physical machine, but respect to struct/object layout in the language, implying there is a larger object/array containing both of these adjacent arrays to begin with. That's what they're talking about in that quote: if you start from a pointer to an array and go to another array that follows it, then it's fine to compare the pointer. To do that, you have to be able to first prove (via the language's abstract machine semantics—not by putting your linear DRAM under a microscope!) one follows the other one, and you cannot do that unless you know they're part of the same aggregate structure.

Anyway, all of this is my understanding of what's going on (and apparently others', as you see on that page). The entire page is a longer discussion on the meaning of these quotes. You can't ignore the rest of the entire page and just quote the first part, since this is exactly what they're dissecting. Read the whole thing, and look at the links they point to. What I quoted is the conclusion they come to based on the preceding quotes (including yours). The standard is not 100% explicit on the issue (hence the discussion and requests for clarification), but many of those who've looked into the issue so far have come to the conclusion I quoted. You need to read it extremely carefully, and (again) if you look at nonlinear address spaces, this should make more sense.

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

#79

Post by lmm »

dataflow wrote: post #78
lmm wrote: post #77

Earlier quoted context omitted.

> Comparing pointers derived from entirely different objects (or arrays) isn't legit. The quote from the standard in your article contradicts the part you quoted: > Two pointers compare equal if and only if both are null pointers, both are pointers to the same object (including a pointer to an object and a subobject at its beginning) or function, both are pointers to one past the last element of the same array object…

They don't contradict to my understanding (see below). First, regarding comparing pointers vs. integers, that goes back to what I said about identical pointer representations as an integer. Just because two pointers point to the same memory location, it does not mean they have an identical representation as an integer. This might be difficult to understand if you think of a linear address space, but it's easier to un…

> Just because two pointers point to the same memory location, it does not mean they have an identical representation as an integer.

Yes, I know. That's irrelevant here for two reasons: firstly, the pointers might compare equal (which is all that matters for this argument), and secondly, once again, the comparison isn't being made between pointers, the comparison is being made between integers.

> The entire page is a longer discussion on the meaning of these quotes. You can't ignore the rest of the entire page and just quote the first part, since this is exactly what they're dissecting. Read the whole thing, and look at the links they point to.What I quoted is the conclusion they come to based on the preceding quotes (including yours). The standard is not 100% explicit on the issue (hence the discussion and requests for clarification), but many of those who've looked into the issue so far have come to the conclusion I quoted.

Yeah, no, their conclusion is wrong (and frankly I don't consider those guys a reputable source; they've said plenty of false things before, and they're prone to exaggerating the extent of undefined behaviour because they have a vested interest in portraying it as more common than it is). They claim that making equality comparisons is undefined behaviour but their only basis for that is a quote from the section on relational operators which is obviously only talking about relational operators. Read the actual standard quotations in context and there is no confusion.

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

#80

Post by mehrdadn »

lmm wrote: post #79
dataflow wrote: post #78

Earlier quoted context omitted.

They don't contradict to my understanding (see below). First, regarding comparing pointers vs. integers, that goes back to what I said about identical pointer representations as an integer. Just because two pointers point to the same memory location, it does not mean they have an identical representation as an integer. This might be difficult to understand if you think of a linear address space, but it's easier to un…

> Just because two pointers point to the same memory location, it does not mean they have an identical representation as an integer. Yes, I know. That's irrelevant here for two reasons: firstly, the pointers might compare equal (which is all that matters for this argument), and secondly, once again, the comparison isn't being made between pointers , the comparison is being made between integers. > The entire page is…

> Yes, I know. That's irrelevant here for two reasons: firstly, the pointers might compare equal (which is all that matters for this argument), and secondly, once again, the comparison isn't being made between pointers, the comparison is being made between integers.

You know what, I think you're right, at least on the second point. I guess the code isn't UB after all then. Somehow I kept reading it as if it's comparing pointers.

Regarding the other point about following something in memory:

> I don't consider those guys a reputable source [...] they claim that making equality comparisons is undefined behaviour but their only basis for that is a quote from the section on relational operators which is obviously only talking about relational operators.

There are multiple entities here, in agreement with each other. The author links to bug #61502 in GCC, where you'll see the compiler devs agree with the author of that page: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502#c15

You might disagree with their stances for whatever reasons you might have, but firing reputational shots at them when there are clearly other experts disagreeing with them isn't really helping make your position more convincing.

> Read the actual standard quotations in context and there is no confusion.

There was no "confusion" on this point to begin with (on my end anyway). Again, as I explained: they might not be intuitive if you're assuming a linear address space, but they're quite fine to interpret. You just need to avoid bringing your own extra assumptions into the table. The notion of "following" in memory hinges on your assumption that the address space is linear. This is pretty similar to how to be able to say your house "follows" another house, you need to first make nontrivial assumptions (e.g., that they're on the same street). To my knowledge C does not make such assumptions globally; all it does is lets you satisfy that criterion by putting them in the same aggregate structure ("street") to begin with, but if you can't do that, you can't satisfy that assumption.

Post reply on HN