4 ms·

Undefined behavior can result in time travel (2014)

80 points by pcr910303 7y ago

deleted 7y ago
[deleted]
dang 7y ago
Discussed at the time: https://news.ycombinator.com/item?id=7954944 https://news.ycombinator.com/item?id=7954944
- JadeNB 7y ago
  Or maybe the discussion time travelled …?
SloopJon 7y ago
I don't remember what UBSan looked like in 2014, but it does something not entirely unhelpful for each of these examples, although they are caught at run time, not compile time: runtime error: index 4 out of bounds for type 'int [4]' UndefinedBehaviorSanitizer: SEGV on unknown addres runtime error: reference binding to null pointer of type 'int'
- logicchop 7y ago
  > although they are caught at run time, not compile time Not if the compiler got to it first. If the compiler does what Chen points out it can do, you won't be indexing anything at run time.
  - saagarjha 7y ago
    At -O0, the compiler will generally not do any of that analysis.
    - klodolph 7y ago
      GCC doesn’t enable -fdelete-null-pointer-checks until -O2, so even -O1 might work fairly well.
  - klodolph 7y ago
    Is that true? The compiler is being explicitly instructed to (try to) detect undefined behavior where it happens. This is the difference between tools like UBSan and tools like Valgrind. Valgrind is low-level, it’s a virtual x86, so the optimizer runs first. UBSan is high-level, it instruments the code using the compiler, and presumably the compiler can be directed to preserve the instrumentation.
  - SloopJon 7y ago
    I see the same errors using Clang with -O1, -O2, and -O3.
  - CodesInChaos 7y ago
    UBsan is part of the compiler, so it inserts runtime checks before the optimization passes which rely on undefined behaviour run.
logicchop 7y ago
I used to work on lower level stuff a place with a large C++ codebase designed by a bunch of C guys. We had tight memory requirements, so a custom operator new (not nothrow) was supplied; but exceptions were also disabled, so the supplier of operator new couldn't throw in their implementation. So that's how it was, and the code base was littered with lots of little checks on what new expressions were returning, things like: int *p = new int[1024]; if (!p) return SOME_ERROR; doSomething(*p); Of course, the C++ standard says that operator new will never return null (it's supposed to throw if it fails). So the compiler sees this code and says "hey, that if (!p) check isn't necessary.." and so none of those little checks gets emitted. Sure enough, it happens that the operator new returns null now and then because everyone is on a tight memory budget, but instead of catching it and returning an error, the code just goes on to crash.
- MaxBarraclough 7y ago
  The answer seems to be to use std::nothrow, which looks like: [0] int *p = new (std::nothrow) int[5]; // gives null if alloc fails A related question: Many C++ coding standards, including Google's, prohibit use of C++ exceptions. Do they have to use the nothrow syntax everywhere the new operator is used? [0] https://www.cplusplus.com/reference/new/operator%20new[]/ https://www.cplusplus.com/reference/new/operator%20new[]/
  - jfkebwjsbx 7y ago
    You can also abort the program, which is what most programs do on OOM anyway.
  - twic 7y ago
    My guess would be that they lean on the fact that "malloc never fails" [1]. Under that model, new and malloc always give you a pointer you can use, it's just that sometimes, using it will give you a segfault. [1] https://scvalex.net/posts/6/ https://scvalex.net/posts/6/
    - MaxBarraclough 7y ago
wtetzner 7y ago
I feel like I'm missing something. Even if we assume i is never 4 or 5, why can we assume that v is contained in the table? Even with undefined behavior, it seems like that's bugger compiler behavior. By the author's logic, even if the undefined behavior didn't exist, you can still assume i is never 4 or 5, but that doesn't meant the function always returns true. Is there something I'm not understanding here?
- Arnavion 7y ago
  Once the i == 4 and i > 4 cases have been eliminated, all code paths in the function return true. It's helpful to remember that the if (table[i] == v) return true; line has an implicit `else continue;` clause, not an `else return false;` clause.
  - wtetzner 7y ago
    Ok, so because i never reaches 4, it assumes the loop doesn't exit due to the 'for' condtion, so it must return true. That makes sense, but still feels like a broken way to do optimizations.

80 points by pcr910303 7y ago

deleted 7y ago

[deleted]

dang 7y ago

Discussed at the time: https://news.ycombinator.com/item?id=7954944 https://news.ycombinator.com/item?id=7954944

JadeNB 7y ago
Or maybe the discussion time travelled …?

SloopJon 7y ago

I don't remember what UBSan looked like in 2014, but it does something not entirely unhelpful for each of these examples, although they are caught at run time, not compile time: runtime error: index 4 out of bounds for type 'int [4]' UndefinedBehaviorSanitizer: SEGV on unknown addres runtime error: reference binding to null pointer of type 'int'

logicchop 7y ago
> although they are caught at run time, not compile time Not if the compiler got to it first. If the compiler does what Chen points out it can do, you won't be indexing anything at run time.
- saagarjha 7y ago
  At -O0, the compiler will generally not do any of that analysis.
  - klodolph 7y ago
    GCC doesn’t enable -fdelete-null-pointer-checks until -O2, so even -O1 might work fairly well.
- klodolph 7y ago
  Is that true? The compiler is being explicitly instructed to (try to) detect undefined behavior where it happens. This is the difference between tools like UBSan and tools like Valgrind. Valgrind is low-level, it’s a virtual x86, so the optimizer runs first. UBSan is high-level, it instruments the code using the compiler, and presumably the compiler can be directed to preserve the instrumentation.
- SloopJon 7y ago
  I see the same errors using Clang with -O1, -O2, and -O3.
- CodesInChaos 7y ago
  UBsan is part of the compiler, so it inserts runtime checks before the optimization passes which rely on undefined behaviour run.

logicchop 7y ago

I used to work on lower level stuff a place with a large C++ codebase designed by a bunch of C guys. We had tight memory requirements, so a custom operator new (not nothrow) was supplied; but exceptions were also disabled, so the supplier of operator new couldn't throw in their implementation. So that's how it was, and the code base was littered with lots of little checks on what new expressions were returning, things like: int *p = new int[1024]; if (!p) return SOME_ERROR; doSomething(*p); Of course, the C++ standard says that operator new will never return null (it's supposed to throw if it fails). So the compiler sees this code and says "hey, that if (!p) check isn't necessary.." and so none of those little checks gets emitted. Sure enough, it happens that the operator new returns null now and then because everyone is on a tight memory budget, but instead of catching it and returning an error, the code just goes on to crash.

MaxBarraclough 7y ago
The answer seems to be to use std::nothrow, which looks like: [0] int *p = new (std::nothrow) int[5]; // gives null if alloc fails A related question: Many C++ coding standards, including Google's, prohibit use of C++ exceptions. Do they have to use the nothrow syntax everywhere the new operator is used? [0] https://www.cplusplus.com/reference/new/operator%20new[]/ https://www.cplusplus.com/reference/new/operator%20new[]/
- jfkebwjsbx 7y ago
  You can also abort the program, which is what most programs do on OOM anyway.
- twic 7y ago
  My guess would be that they lean on the fact that "malloc never fails" [1]. Under that model, new and malloc always give you a pointer you can use, it's just that sometimes, using it will give you a segfault. [1] https://scvalex.net/posts/6/ https://scvalex.net/posts/6/
  - MaxBarraclough 7y ago

wtetzner 7y ago

I feel like I'm missing something. Even if we assume i is never 4 or 5, why can we assume that v is contained in the table? Even with undefined behavior, it seems like that's bugger compiler behavior. By the author's logic, even if the undefined behavior didn't exist, you can still assume i is never 4 or 5, but that doesn't meant the function always returns true. Is there something I'm not understanding here?

Arnavion 7y ago
Once the i == 4 and i > 4 cases have been eliminated, all code paths in the function return true. It's helpful to remember that the if (table[i] == v) return true; line has an implicit `else continue;` clause, not an `else return false;` clause.
- wtetzner 7y ago
  Ok, so because i never reaches 4, it assumes the loop doesn't exit due to the 'for' condtion, so it must return true. That makes sense, but still feels like a broken way to do optimizations.