3 ms·

I think the twitter thread I linked answers your questions? "use after free" is an instance of a memory access pattern that is considered invalid from the prog

• raphlinus 4y ago
  The point of the C11 memory model is that it gives formal bounds on what optimizations the compiler is and is not able to do. In particular, it is free to reorder memory operations as if the program was single-threaded, unless the memory operations are explicitly marked as atomic. My assertion is that if you do these optimizations and then have a data race, it's functionally equivalent to undefined behavior, even if you call it something different and loudly proclaim that your language doesn't have UB.
  • jessermeyer 4y ago
    Obviously Odin does not use C's memory model. And in instances where LLVM optimizes Odin for UB, it is a bug, and not a feature. Odin explicitly opts out of all optimization passes that depend or leverage UB, but that's a moving target. For example, as mentioned in the article, Odin does not leverage LLVM's poison value optimizations, which are derived from optimizations exploiting undefined behavior. Sure, some code is slowed. But can you point to a well known and well used algorithm whose runtime characteristics depend upon exploiting UB? If you code goes fast because it's doing undefined things the compiler strips away, that's a structural bug in the application, in my view.
    • spacechild1 4y ago
      > Obviously Odin does not use C's memory model. How is that obvious? And which memory model does Odin use? Just to be clear: a "memory model" is not about memory management, it is about the behaviour of multithreaded programs: https://en.m.wikipedia.org/wiki/Memory_model_(programming) https://en.m.wikipedia.org/wiki/Memory_model_(programming)
      • jessermeyer 4y ago
        Thanks. I was thinking of strict-aliasing and the associated undefined behavior, which Odin forbids. Odin's atomic intrinsics model after C11 closely (and require the programmer to emit memory barriers when cache behavior must be controlled by instructions). I believe the final memory model will be platform defined. There is no built-in atomic data type in Odin. Only atomic operations are available, and most sync primitives are implemented in the standard library wrapping OS capabilities (WaitOnAddress), etc. The parent comment said: >then have a data race, it's functionally equivalent to undefined behavior This is a matter of interpretation but there is a categorical difference between "this read is undefined so the compiler will silently omit it" and "this read will read whatever value is in the CPU cache at this address, even if the cache is stale". The difference is a matter of undefined behavior from the language versus the application being in an undefined state.
        • spacechild1 4y ago
          > This is a matter of interpretation but there is a categorical difference between "this read is undefined so the compiler will silently omit it" and "this read will read whatever value is in the CPU cache at this address, even if the cache is stale". The difference is a matter of undefined behavior from the language versus the application being in an undefined state. I totally agree.
    • raphlinus 4y ago
      I'll give a concrete example. It's not the most compelling optimization in the world, but I think illustrates the tradeoffs clearly. The following is pseudocode, not any particular language, but hopefully will be clear. let i = mystruct.i; if (i < array.length) { let x = expensive_computation(i); array[i] = x; } For the purpose of this example, let's say that the expensive computation is register-intensive but doesn't write any memory (so we don't need to get into alias analysis issues). Because it is register-intensive, our optimizer would like to free up the register occupied by i, replacing the second use of i by another load from mystruct.i. In C or unsafe Rust, this would be a perfectly fine optimization. If another thread writes struct.i concurrently, we have a time of check to time of use (TOCTOU) error. In C or unsafe Rust, that's accounted for by the fact that a data race is undefined behavior. One of the behaviors that's allowed (because basically all behavior are allowed) is for the two uses of i to differ, invalidating the bounds check. Different languages deal with this in different ways. Java succeeds in its goal of avoiding UB, disallowing this optimization; the mechanism for doing so in LLVM is to consider most memory accesses to have "unordered" semantics. However, this comes with its own steep tradeoff. To avoid tearing, all pointers must be "thin," specifically disallowing slices. Go, by contrast, has slices among its fat pointer types, so incurs UB when there's a data race. It's otherwise a fairly safe language, but this is one of the gaps in that promise. Basically, my argument is this. If you're really rigorous about avoiding UB, you essentially have to define a memory model, then make sure your use of LLVM (or whatever code generation technique) is actually consistent with that memory model. That's potentially an enormous amount of work, very easy to get subtly wrong, and at the end of the day gives you fewer optimization opportunities than C or unsafe Rust. Thus, it's certainly not a tradeoff I personally would make.
      • jessermeyer 4y ago
        Thanks. Currently Odin would cache i on the stack for retrieval later, granting LLVM the ability to load it into a register if profitable with knowledge that after the read, `i` is constant, which bypasses the RAW hazard after the initial read. My view is that undefined behavior is a trash fire and serious effort should be undertaken to fix the situation before it gets even more out of hand.
      • 4y ago
    • kristoff_it 4y ago
      > If you code goes fast because it's doing undefined things the compiler strips away, that's a structural bug in the application, in my view. I think that's the inverse of what UB-based optimizations do. Those optimizations rely on you _never_ doing what is considered UB. That's what makes the optimization correct. The problem is that, in practice, what's usually considered UB is not something that the language can always statically ensure you're not doing, and so when you do make a mistake, you land in a situation where the optimization seems to make things worse, instead of protecting you.
• kaba0 4y ago
  How is that different from specifying the behavior of addition only when it won’t overflow? The C spec might as well say that it is invalid to overflow, and you are responsible for checking for that (and that’s kind of what they do), but that’s what UB is afaik.
• lifthrasiir 4y ago
  Borrowing gingerbill's terminology, your "mini spec" is still incomplete. And it is unclear how an implicit or incomplete mini spec is different from UB, except for the fact that the compiler can't take advantage of that. From the user's perspective a gap in the mini spec is still a gap that needs to be memorized, considered and avoided much like UB. If you do somehow manage to define every "mini spec", this poses another problem that your specification limits what you can do in the future---for example you would be unable to switch the memory allocator.
  • hsn915 4y ago
    The difference is that in the case of UB in C the compiler will say "aha! I will just assume this can never happen", where as with platform-dependent behavior, the compiler can never make such assumption, so has to be conservative about its assumptions.
    • lifthrasiir 4y ago
      You can already order a C compiler not to make an assumption based on UB, e.g. -fno-strict-aliasing, -ftrapv and others. Did that make C users happy? Not sure.
• glowcoil 4y ago
  This is fundamentally the same thing as undefined behavior, regardless of whether Odin insists on calling it by a different name. If you don't want behavior to be undefined, you have to define it, and every part of the compiler has to respect that definition. If a use-after-free is not undefined behavior in Odin, what behavior is it defined to have? As a basic example, if the compiler guarantees that the write will result in a deterministic segmentation fault, then that address must never be reused by future allocations (including stack allocations!), and the compiler is not allowed to perform basic optimizations like dead store elimination and register promotion for accesses to that address, because those can prevent the segfault from occurring. If the compiler guarantees that the write will result in either a segfault or a valid write to that memory location, depending on the current state of the allocator, what guarantees does the compiler make about those writes? If some other piece of code is also performing reads and writes at that location, is the write guaranteed to be visible to that code? This essentially rules out dead store elimination, register promotion, constant folding, etc. for both pieces of code, because those optimizations can prevent one piece of code from observing the other's writes. Worse, what if the two pieces of code are on different threads? And so on. If the compiler doesn't guarantee a deterministic crash, and it doesn't guarantee whether or not the write is visible to other code using the same region of memory, and it doesn't provide any ordering or atomicity guarantees for the write if it does end up being visible to other code, and then it performs a bunch of optimizations that can affect all of those things in surprising ways: congratulations, your language has undefined behavior. You can insist on calling it something else, but you haven't changed the fundamental situation.
  • naniwaduni 4y ago
    You language has behavior not defined within the language, sure. What it does not now have is permission for the compiler to presume that the code never executes with input that would cause the behavior not defined to occur.
    • glowcoil 4y ago
      The compiler is already doing that when it performs any of the optimizations I mentioned above. When the compiler takes a stack-allocated variable (whose address is never directly taken) and promotes it to a register, removes dead stores to it, or constant-folds it out of existence, it does so under the assumption that the program is not performing aliasing loads and stores to that location on the stack. In other words, it is leaving the behavior of a program that performs such loads and stores undefined, and in doing so it is directly enabling some of the most basic, pervasive optimizations that we expect a compiler to perform. In a language with raw pointers, essentially all optimizations rely on this type of assumption. Forbidding the compiler from making the assumption that undefined behavior will not occur essentially amounts to forbidding the compiler from optimizing at all. If that is indeed what you want, then what you want is something closer to a macro assembler than a high-level language with an optimizing compiler like C. It's a valid thing to want, but you can't have your cake and eat it too.