2 ms·

>Tried to put together an argument about the high bits of (common) address spaces being zero and therefore it's safe but I don't think that works. Yep; on AMD6

>Tried to put together an argument about the high bits of (common) address spaces being zero and therefore it's safe but I don't think that works. Yep; on AMD64, bits 48 through 63 must be identical to bit 47, which can be 1 or 0, akin to sign extension. In practice, I don't think any sane OS would let you reserve the very last n bytes of memory, especially not with an address space as large as that of AMD64, but you can't assume the architecture, and you don't always have an operating system. And yeah, you could see the same bug with integer array indices, if signed integers wrap. /* Endless loop if end == INT_MAX */ for (int i = 0; i < end; ++i) /* code */;

JonChesterfield 3y ago
Linux kernel space on x64 uses "negative" pointer values so the high bits are set there. Which is probably the more interesting place to find this bug. Needs to be unsigned to get this failure mode, any signed loop gets compiled assuming no overflow for a different (though similar!) failure mode. I'm leaning towards "C is surprising". Didn't have to be but as presently implemented is very full of hazards.
- trealira 3y ago
  > Needs to be unsigned to get this failure mode, any signed loop gets compiled assuming no overflow for a different (though similar!) failure mode. In C and C++, compilers will optimize assuming that signed integer overflow doesn't happen, but that doesn't stop it from actually happening. Unless you set it to trap on overflow, signed integers still wrap; it's just that compilers make (incorrect) optimizations assuming that it doesn't happen. You know, this makes me wonder whether it's better pointers to be compared with signed or unsigned comparisons. Currently, my compiler emits unsigned comparison instructions for them.
  - Joker_vD 3y ago
    Do you mean unsigned branches? JB/JBE/JA/JAE instead of JL/JLE/JG/JGE? Are there actually code patterns where it's preferable to just JE/JNE? AFAIK, computing a pointer outside of the underlying array's boundaries (except for computing the one-past-the-last-element pointer) is UB so e.g. for (SomeStruct * curr = p, * end = &p[N]; curr < end; curr += 2) { // processing the pair of curr[0] and curr[1], with care // in case when curr[1] doesn't exist } is an invalid optimization of for (SomeStruct * curr = p, * end = &p[N]; curr != end; ) { // processing the pair of curr[0] and curr[1], with care // in case when curr[1] doesn't exist if (++curr != end) { ++curr; } }
    - trealira 3y ago
      > Do you mean unsigned branches? JB/JBE/JA/JAE instead of JL/JLE/JG/JGE? Yeah, that's what I meant. Thanks for speaking more clearly. > Are there actually code patterns where it's preferable to just JE/JNE? That's a good point, and sidesteps the issue of pointer signedness. I think sometimes JE / JNE isn't enough. For example, if you want to process a buffer in reverse order using pointer arithmetic: /* p starts off one past the end of the buffer */ char *p = buffer + bufsize; while (--p >= buffer) { /* ... */ } I'm not sure if this would technically be undefined behavior, though, as the C standard only explicitly permits computing a pointer one past the end of the array, and other out-of-bounds computations are undefined, IIRC. In practice, I don't think any compiler would miscompile this.
trealira 3y ago
Actually, this isn't true. The loop ends as soon as i == INT_MAX. It would only be endless if the loop condition were "i <= end" and end were equal to INT_MAX.

JonChesterfield 3y ago

Linux kernel space on x64 uses "negative" pointer values so the high bits are set there. Which is probably the more interesting place to find this bug. Needs to be unsigned to get this failure mode, any signed loop gets compiled assuming no overflow for a different (though similar!) failure mode. I'm leaning towards "C is surprising". Didn't have to be but as presently implemented is very full of hazards.

trealira 3y ago
> Needs to be unsigned to get this failure mode, any signed loop gets compiled assuming no overflow for a different (though similar!) failure mode. In C and C++, compilers will optimize assuming that signed integer overflow doesn't happen, but that doesn't stop it from actually happening. Unless you set it to trap on overflow, signed integers still wrap; it's just that compilers make (incorrect) optimizations assuming that it doesn't happen. You know, this makes me wonder whether it's better pointers to be compared with signed or unsigned comparisons. Currently, my compiler emits unsigned comparison instructions for them.
- Joker_vD 3y ago
  Do you mean unsigned branches? JB/JBE/JA/JAE instead of JL/JLE/JG/JGE? Are there actually code patterns where it's preferable to just JE/JNE? AFAIK, computing a pointer outside of the underlying array's boundaries (except for computing the one-past-the-last-element pointer) is UB so e.g. for (SomeStruct * curr = p, * end = &p[N]; curr < end; curr += 2) { // processing the pair of curr[0] and curr[1], with care // in case when curr[1] doesn't exist } is an invalid optimization of for (SomeStruct * curr = p, * end = &p[N]; curr != end; ) { // processing the pair of curr[0] and curr[1], with care // in case when curr[1] doesn't exist if (++curr != end) { ++curr; } }
  - trealira 3y ago
    > Do you mean unsigned branches? JB/JBE/JA/JAE instead of JL/JLE/JG/JGE? Yeah, that's what I meant. Thanks for speaking more clearly. > Are there actually code patterns where it's preferable to just JE/JNE? That's a good point, and sidesteps the issue of pointer signedness. I think sometimes JE / JNE isn't enough. For example, if you want to process a buffer in reverse order using pointer arithmetic: /* p starts off one past the end of the buffer */ char *p = buffer + bufsize; while (--p >= buffer) { /* ... */ } I'm not sure if this would technically be undefined behavior, though, as the C standard only explicitly permits computing a pointer one past the end of the array, and other out-of-bounds computations are undefined, IIRC. In practice, I don't think any compiler would miscompile this.

trealira 3y ago

Actually, this isn't true. The loop ends as soon as i == INT_MAX. It would only be endless if the loop condition were "i <= end" and end were equal to INT_MAX.