6 ms·

How does this work in practice? Is the behavior of a use-after-free defined? Data races? The latter even more so for objects that don't fit in one machine word,

How does this work in practice? Is the behavior of a use-after-free defined? Data races? The latter even more so for objects that don't fit in one machine word, such as slices. While avoiding undefined behavior is a noble goal, my personal feeling is that actually achieving that will be much harder than it might first seem, and will probably end up precluding a good deal of optimization. Of course, C has an entire class of UB that is much more excessive than useful, for example left shift of a negative integer. It's clearly and obviously possible to do much better than C. I'm just skeptical that "no UB at all" is in reach for a low-level, systems programming language that is also portable and can be compiled with optimization comparable to C.

hsn915 4y ago
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 program's point of view. What happens depends on the situation: Was the memory returned to the operating system? If so it will probably result in a page fault and if you don't have a thing to handle the signal then the OS will crash your program. Was the memory part of an arena managed by the custom allocator that still owns it? If so it will return whatever value is contained in the address being dereferenced.
- 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
- 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.
guenthert 4y ago
> for example left shift of a negative integer. It's clearly and obviously possible to do much better than C. If you want to allow machine architectures using other than two's complement while simultaneously striving for efficient translations, that isn't all that obvious to me.
- gingerBill 4y ago
  Name a machine that people still program for that is NOT two's complement. And the latest version of C now requires two's complement too!
  - astrange 4y ago
    Left shift with a negative shift count still has UB issues unless you generate inefficient code. The way the shift count is read is different on ARM, x86 scalar, and x86 SIMD… so you can't autovectorize it without UB.
    - jessermeyer 4y ago
      Odin forbids negative shifts.
      - astrange 4y ago
        It's not a genuine negative shift, because the CPU doesn't implement negative shifts either. It's a trick to simplify eg 'x << (32 - y)' to 'x << (-y)' and save an instruction, seen in ffmpeg, because the compilers don't always do it themselves. This works because of the shift masking behavior.
        gingerBill 4y ago
        Odin's shift behaviour is different to that of C's undefined behaviour. To copy from the Overview[1]: > The right operand in a shift expression must have an unsigned integer type or be an untyped constant representable by a typed unsigned integer. and [2]: > The shift operators shift the left operand by the shift count specified by the right operand, which must be non-negative. The shift operators implement arithmetic shifts if the left operand a signed integer and logical shifts if the it is an unsigned integer. There is not an upper limit on the shift count. Shifts behave as if the left operand is shifted `n` times by `1` for a shift count of `n`. Therefore, `x<<1` is the same as `x2` and `x>>1` is the same as `x/2` but truncated towards negative infinity. In the case of overshift, the value is zeroed. Empirically I have found that the vast majority of shift factors can be known at compile time (or at least the valid range of integer), meaning it will compile to 1 instruction rather 2/3. In naïve C, the shift would look like this: (y < 8*sizeof(x)) > (x << y) : 0 In practice, the "select" instruction is never needed. This approach to shifting also places never in that it feels more like 2's complement in that `x << y` is now equivalent to `x (2*y)`. This means that `(a << b) << c` is equivalent to `a << (b + c)`. In your example of `x << (32 - y)`, that logic works as what people intuitively intent it to mean, unlike in C where when `y` is 0, the shift behaviour is platform defined (nothing on x86 (5 bit shift) but zeros on powerpc (6 bit shift)). [1] https://odin-lang.org/docs/overview/#arithmetic-operators https://odin-lang.org/docs/overview/#arithmetic-operators [2] https://odin-lang.org/docs/overview/#integer-operators https://odin-lang.org/docs/overview/#integer-operators

hsn915 4y ago

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 program's point of view. What happens depends on the situation: Was the memory returned to the operating system? If so it will probably result in a page fault and if you don't have a thing to handle the signal then the OS will crash your program. Was the memory part of an arena managed by the custom allocator that still owns it? If so it will return whatever value is contained in the address being dereferenced.

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
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.

guenthert 4y ago

> for example left shift of a negative integer. It's clearly and obviously possible to do much better than C. If you want to allow machine architectures using other than two's complement while simultaneously striving for efficient translations, that isn't all that obvious to me.

gingerBill 4y ago
Name a machine that people still program for that is NOT two's complement. And the latest version of C now requires two's complement too!
- astrange 4y ago
  Left shift with a negative shift count still has UB issues unless you generate inefficient code. The way the shift count is read is different on ARM, x86 scalar, and x86 SIMD… so you can't autovectorize it without UB.
  - jessermeyer 4y ago
    Odin forbids negative shifts.
    - astrange 4y ago
      It's not a genuine negative shift, because the CPU doesn't implement negative shifts either. It's a trick to simplify eg 'x << (32 - y)' to 'x << (-y)' and save an instruction, seen in ffmpeg, because the compilers don't always do it themselves. This works because of the shift masking behavior.
      - gingerBill 4y ago
        Odin's shift behaviour is different to that of C's undefined behaviour. To copy from the Overview[1]: > The right operand in a shift expression must have an unsigned integer type or be an untyped constant representable by a typed unsigned integer. and [2]: > The shift operators shift the left operand by the shift count specified by the right operand, which must be non-negative. The shift operators implement arithmetic shifts if the left operand a signed integer and logical shifts if the it is an unsigned integer. There is not an upper limit on the shift count. Shifts behave as if the left operand is shifted `n` times by `1` for a shift count of `n`. Therefore, `x<<1` is the same as `x2` and `x>>1` is the same as `x/2` but truncated towards negative infinity. In the case of overshift, the value is zeroed. Empirically I have found that the vast majority of shift factors can be known at compile time (or at least the valid range of integer), meaning it will compile to 1 instruction rather 2/3. In naïve C, the shift would look like this: (y < 8*sizeof(x)) > (x << y) : 0 In practice, the "select" instruction is never needed. This approach to shifting also places never in that it feels more like 2's complement in that `x << y` is now equivalent to `x (2*y)`. This means that `(a << b) << c` is equivalent to `a << (b + c)`. In your example of `x << (32 - y)`, that logic works as what people intuitively intent it to mean, unlike in C where when `y` is 0, the shift behaviour is platform defined (nothing on x86 (5 bit shift) but zeros on powerpc (6 bit shift)). [1] https://odin-lang.org/docs/overview/#arithmetic-operators https://odin-lang.org/docs/overview/#arithmetic-operators [2] https://odin-lang.org/docs/overview/#integer-operators https://odin-lang.org/docs/overview/#integer-operators