4 ms·

The MINIMUM baseline is probably somewhere around ASAN/UBSAN/etc. and those aren't exactly cheap... and they don't even promise to catch all the problems. The p

The MINIMUM baseline is probably somewhere around ASAN/UBSAN/etc. and those aren't exactly cheap... and they don't even promise to catch all the problems. The problem is that almost every single little thing you can do in C has potential for UB, even just the + operator. So it would absolutely come at a HUGE performance cost, unfortunately. More esoteric stuff is: If you do pointer arithmetic that technically goes out of bounds and then in bounds again... that's technically UB (can't remember if this is C++ only or both), so you can't rely on knowing where everything is + bounds checks.

CryZe 3y ago
I'd say that those are not actually the minimum. You don't need to detect undefined behavior, you just need to "make it implementation defined", so integers could just wrap around without needing to check for overflow, unitialized memory would just be random bytes, and so on. At least that would be one way to do it. Of course the checks would ensure the program shuts down more cleanly.
- celrod 3y ago
  The nice thing about integer overflow being UB is that UBsan (or even compiler flags without it) can make it throw, so it's easy to catch. Defining it as wrapping means you still have bugs, they're just harder to catch. Define it as wrapping, and there will be programs relying on it (that are currently using unsigned).
twoodfin 3y ago
Aliasing is a real problem. If any pointer of any type can write though to any value of any other type with some defined behavior, many key optimizations—moving a value into a register!—become impossible.
- Dylan16807 3y ago
  In general I don't know how you make currently-UB aliasing safe. But in that specific case you can just say that the value not showing up through the bad alias is a possible defined behavior.
  - twoodfin 3y ago
    But whether it shows up or not is a function of the optimization decision, which might have gone the other way for any number of hard-to-define reasons.
    - Dylan16807 3y ago
      Is that a problem, though? I would have thought the best case scenario for a bad alias is that you safely corrupt some other piece of data. (Assuming you let those writes go through.) So "it might not do that" seems like an improvement to me. If you don't let those writes go through, then we're in a different happier situation, and the register optimization causes no change in behavior.
      - twoodfin 3y ago
        I guess I'm not sure which definition you're proposing: a) Writes through "bad" aliases never take effect. or b) Writes through "bad" aliases take effect sometimes, no guarantees. I don't think either makes the point you're hoping to. b) is just bog standard undefined behavior. I guess you could be intending to constrain the range of what effects compiler-emitted code can have in bad-aliasing situations (no nasal daemons!) but it's not clear how much additional optimization latitude constraining only nasal daemons provides. Compilers often save local stack space by reusing stack entries for multiple local variables. A bad alias to one could corrupt an unrelated value, and you've got nasal daemons again. a) requires massive compile-time and run-time effort to dynamically distinguish "bad" aliases from "good" ones. This is along the lines of what valgrind does at great cost.
        Dylan16807 3y ago
        I thought the premise was that Someone Else already took care of those nasal demons somehow, and we're just worried about putting the register optimization back into place. So the range of effects has already been constrained to something safe. We're just adding in "sometimes it doesn't have those bad effects" to enable some optimizations, and that should have very little downside. Options a and b are just the different ways Someone Else could have implemented their solution. I'm not suggesting how they did that, I'm taking it as the premise. The problem of "how do we make bad aliasing safe" is much much much harder than "how do we still enable normal optimizations like this after we make bad aliasing safe".
- JonChesterfield 3y ago
  That's the general consensus. However, much the same key optimisations are useful when both pointers have the same type. Given multiple float* pointers, you still want to know whether they alias for load/store forwarding and the like. Once you've written the analysis to partition values of the same type into separate alias sets, that same analysis runs fine on values of different types. Distinct types implying distinct alias sets does tolerate separate compilation well and is cheap to compute. The belief that it is the only way to achieve said key optimisations is worth some scepticism now that link time optimisation and interprocedural analysis are fairly common.
  - twoodfin 3y ago
    You can have the most sophisticated analysis imaginable, but then I cast rand() to a pointer and …
Dylan16807 3y ago
> More esoteric stuff is: If you do pointer arithmetic that technically goes out of bounds and then in bounds again... that's technically UB (can't remember if this is C++ only or both), so you can't rely on knowing where everything is + bounds checks. When the goal is preventing UB, you can simply define things like that as not-UB. At least on the vast majority of architectures where the numbers work fine at runtime, and only the compiler sees it as invalid behavior.
saagarjha 3y ago
Not really. Address Sanitizer must work with the existing ABI, which means it has a lot of overhead for an imperfect result.
- jenadine 3y ago
  What could be done better if it could break the ABI?
  - saagarjha 3y ago
    You could pass around fat pointers everywhere. This is more efficient than probabilistically setting up redzones.
    - Quekid5 3y ago
      True, but that doesn't address (heh) the briefly-goes-out-of-bounds-and-then-in-bounds scenario. Again, I'm not 100% that that's technically UB, but I think so? (It would have be to be for very esoteric addressing modes, maybe relevant on ancient pre-linear address space architectures?)
      - saagarjha 3y ago
        That would be a check on each arithmetic operation.

CryZe 3y ago

I'd say that those are not actually the minimum. You don't need to detect undefined behavior, you just need to "make it implementation defined", so integers could just wrap around without needing to check for overflow, unitialized memory would just be random bytes, and so on. At least that would be one way to do it. Of course the checks would ensure the program shuts down more cleanly.

celrod 3y ago
The nice thing about integer overflow being UB is that UBsan (or even compiler flags without it) can make it throw, so it's easy to catch. Defining it as wrapping means you still have bugs, they're just harder to catch. Define it as wrapping, and there will be programs relying on it (that are currently using unsigned).

twoodfin 3y ago

Aliasing is a real problem. If any pointer of any type can write though to any value of any other type with some defined behavior, many key optimizations—moving a value into a register!—become impossible.

Dylan16807 3y ago
In general I don't know how you make currently-UB aliasing safe. But in that specific case you can just say that the value not showing up through the bad alias is a possible defined behavior.
- twoodfin 3y ago
  But whether it shows up or not is a function of the optimization decision, which might have gone the other way for any number of hard-to-define reasons.
  - Dylan16807 3y ago
    Is that a problem, though? I would have thought the best case scenario for a bad alias is that you safely corrupt some other piece of data. (Assuming you let those writes go through.) So "it might not do that" seems like an improvement to me. If you don't let those writes go through, then we're in a different happier situation, and the register optimization causes no change in behavior.
    - twoodfin 3y ago
      I guess I'm not sure which definition you're proposing: a) Writes through "bad" aliases never take effect. or b) Writes through "bad" aliases take effect sometimes, no guarantees. I don't think either makes the point you're hoping to. b) is just bog standard undefined behavior. I guess you could be intending to constrain the range of what effects compiler-emitted code can have in bad-aliasing situations (no nasal daemons!) but it's not clear how much additional optimization latitude constraining only nasal daemons provides. Compilers often save local stack space by reusing stack entries for multiple local variables. A bad alias to one could corrupt an unrelated value, and you've got nasal daemons again. a) requires massive compile-time and run-time effort to dynamically distinguish "bad" aliases from "good" ones. This is along the lines of what valgrind does at great cost.
      - Dylan16807 3y ago
        I thought the premise was that Someone Else already took care of those nasal demons somehow, and we're just worried about putting the register optimization back into place. So the range of effects has already been constrained to something safe. We're just adding in "sometimes it doesn't have those bad effects" to enable some optimizations, and that should have very little downside. Options a and b are just the different ways Someone Else could have implemented their solution. I'm not suggesting how they did that, I'm taking it as the premise. The problem of "how do we make bad aliasing safe" is much much much harder than "how do we still enable normal optimizations like this after we make bad aliasing safe".
JonChesterfield 3y ago
That's the general consensus. However, much the same key optimisations are useful when both pointers have the same type. Given multiple float* pointers, you still want to know whether they alias for load/store forwarding and the like. Once you've written the analysis to partition values of the same type into separate alias sets, that same analysis runs fine on values of different types. Distinct types implying distinct alias sets does tolerate separate compilation well and is cheap to compute. The belief that it is the only way to achieve said key optimisations is worth some scepticism now that link time optimisation and interprocedural analysis are fairly common.
- twoodfin 3y ago
  You can have the most sophisticated analysis imaginable, but then I cast rand() to a pointer and …

Dylan16807 3y ago

> More esoteric stuff is: If you do pointer arithmetic that technically goes out of bounds and then in bounds again... that's technically UB (can't remember if this is C++ only or both), so you can't rely on knowing where everything is + bounds checks. When the goal is preventing UB, you can simply define things like that as not-UB. At least on the vast majority of architectures where the numbers work fine at runtime, and only the compiler sees it as invalid behavior.

saagarjha 3y ago

Not really. Address Sanitizer must work with the existing ABI, which means it has a lot of overhead for an imperfect result.

jenadine 3y ago
What could be done better if it could break the ABI?
- saagarjha 3y ago
  You could pass around fat pointers everywhere. This is more efficient than probabilistically setting up redzones.
  - Quekid5 3y ago
    True, but that doesn't address (heh) the briefly-goes-out-of-bounds-and-then-in-bounds scenario. Again, I'm not 100% that that's technically UB, but I think so? (It would have be to be for very esoteric addressing modes, maybe relevant on ancient pre-linear address space architectures?)
    - saagarjha 3y ago
      That would be a check on each arithmetic operation.