7 ms·

Maybe we should get rid of "abstract machine" and treat pointers as memory addresses?

by codedokode 2y ago

davidt84 2y ago
Congratulations, you've invented an entirely new language. Now, who's going to write the compiler for it?
- anticensor 2y ago
  No, it's C at -O0.
  - davidt84 2y ago
    No, it's not. Undefined behaviour is undefined behaviour whatever optimisation level you use. Some -f flags may extend the C standard and remove undefined behaviour in some cases (e.g. strict aliasing, signed integer overflow, writable string constants, etc.)
gpderetta 2y ago
int* oracle(); int foo() { int x = 1; *oracle() = 42; return x; } Is the above program allowed to return anything other than 1 in your language?
- kibwen 2y ago
  To elaborate, we treat pointers as more than just integers because it gives optimizers the latitude to reorder and eliminate pointer operations. In the example above we cannot do this, because we cannot prove at compile time that x doesn't live at the address returned by oracle. For some high-quality further discussion, see Ralf Jung's series of blog posts starting with https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html
  - shultays 2y ago
    However, given how low-level a language C++ is, we can actually break this assumption by setting i to y-x. Since &x[i] is the same as x+i, this means we are actually writing 23 to &y[0]. But that is undefined, you can't do x + (y - x) ie a pointer arithmetic that ends outside of bounds of an array. Since it is undefined, shouldn't C++ assume that changing x[..] can't change y[0] edit: welp, if I read a few more lines into article I would see that it also tells it is undefined
  - gpderetta 2y ago
    to be clear, in my example the result of oracle() cannot possibly alias with 'x' in C or C++ (and in fact gcc will optimize accordingly). In a different language where addresses are mere integers, things would be more complicated.
    - codedokode 2y ago
      The result of oracle can point to anything if you write it as return (int *)rand(); Note that rand() returns 32-bit value so you have to call it twice and merge the results to obtain a 64-bit pointer.
      - gpderetta 2y ago
        The numerical value returned by oracle might physically match the address of the stack slot for 'x', assuming that it exists, but it doesn't mean that, from a language point of view, it is a valid pointer. If forging pointers had defined behaviour, it would be impossible to use the language sanely or perform any kind of optimization.
- alerighi 2y ago
  Well even in C is not guaranteed to return anything other than 1, since oracle() may return the memory address of variable 1.
  - gpderetta 2y ago
    the literal 1 is not an object in C or C++ hence it does not have an address. If you meant 'x', then also no, oracle() can't return the address of 'x' because of pointer provenance rules.
- shultays 2y ago
  Is it allowed to return anything else in C? Is there anything in standard C that would allow oracle() to access memory address of x? Sure different compilers might allow inlining assembly or some other ways to access x on previous stack perhaps but then it is not really "C"
  - wat10000 2y ago
    That’s the point. C allows this function to be optimized to always return 1. A “pointers are addresses, just emit reads and writes and stop trying to be so clever” version of C would require x to be spilled to the stack, then the write, then reload x and return whatever it contained.
    - cv5005 2y ago
      Then use the register keyword or just reword the standard to assume the register behavior if a variables address hasn't been taken. The majority of useful optimizations can be kept in a "Sane C" with either code style changes (cache stuff in local vars to avoid aliasing for example) or with minor tweaks to the standard.
      - wat10000 2y ago
        Register behavior is what you want essentially all of the time. So we’d just have to write `register` all over the place for no gain. “Don’t optimize this, read and write it even if you think it’s not necessary” is a very rare case so it shouldn’t be the default. If you want it, use the volatile keyword. There’s no need to reword the standard to assume the register behavior if the variable’s address hasn’t been taken. That’s already how it works. In this example, if you escape the value of `&x`, it’s not legal to optimize this function to always return 1.
- codedokode 2y ago
  When using C, this can return anything (or crash of oracle function returns an invalid pointer, or rewrite its own code if the code section is writable). So if you get rid of "abstract machine", nothing changes - the program can return anything or crash.
  - wat10000 2y ago
    A conforming C compiler is allowed to emit that function to perform the write and then return the constant 1. Should that be allowed?
  - atq2119 2y ago
    The point is that the C standard does guarantee that the function returns 1 if the program is a valid C program - which means there is no UB. For example: If the oracle function returns an invalid pointer, then dereferencing that pointer is UB, and therefore the program isn't a valid C program.
- deleted 2y ago
  [deleted]
sixfiveotwo 2y ago
How would you define what a memory address is without first defining in which context it has a meaning?
- codedokode 2y ago
  C was written as a portable assembly language, so I think a memory address is a number that CPU considers to be a memory address.
  - layer8 2y ago
    That’s currently the case in C, in that you can convert pointers to and from uintptr_t. However, not every number representable in that type needs to be valid memory (that’s true on the assembly level as well), hence it’s only defined for valid pointers.
  - sixfiveotwo 2y ago
    > I think a memory address is a number that CPU considers to be a memory address I meant to say that, indeed, there must be some concept of CPU for a memory address to have a meaning, and for this concept of CPU to be as widely applicable as possible, surely defining it as abstract as possible is the way to go. Ergo, the idea of a C abstract machine. Anyway, other people in this thread are discussing the matter more accurately and in more details than I could hope to do, so I'll leave it like that.
lmm 2y ago
20 years ago, making a C compiler that provided sane behaviour and better guarantees (going beyond the minimum defined in the standard) to make code safer and programmers' lives easier, even at the cost of some performance, might have been a good idea. Today any programmer who thinks things like not having security bugs are more important than having bigger numbers on microbenchmarks has already moved on from C.
- uecker 2y ago
  This is certainly not true. Many programmers also learned to the use tools available to write reasonably safe code in C. I do not personally find this problematic.
  - quotemstr 2y ago
    > safe code in C You're like a Japanese holdout in the 60s refusing to leave his bunker long after the war is over. C lost. Memory safety is a huge boon for security. Human beings, even the best of them, cannot consistently write correct C code. (Look at OpenBSD.) You can keep fighting the war your side has already lost or you can move on.
    - uecker 2y ago
      Well, memory safety is great but it seems Rust programmers also manage to create memory safety issues just fine: https://rustsec.org/advisories/RUSTSEC-2024-0401.html https://rustsec.org/advisories/RUSTSEC-2024-0401.html https://rustsec.org/advisories/RUSTSEC-2024-0400.html https://rustsec.org/advisories/RUSTSEC-2024-0400.html https://rustsec.org/advisories/RUSTSEC-2024-0377.html https://rustsec.org/advisories/RUSTSEC-2024-0377.html https://rustsec.org/advisories/RUSTSEC-2024-0374.html https://rustsec.org/advisories/RUSTSEC-2024-0374.html etc.
      - whytevuhuni 2y ago
        I think the first one, stack overflow, is technically not a memory safety issue, just denial-of-service on resource exhaustion. Stack overflow is well defined as far as I know. The other three are definitely memory safety issues.
NobodyNada 2y ago
If you do this, your C code will run significantly slower than, say, Java, Go, or C#, because the compiler is unable to apply even the most basic optimizations (which it can do still in all those other languages). So, at that point why even use C at all? Today, C is used where the overhead of a managed language is unacceptable. If you could just eat the performance cost, you'd probably already be using a managed language. There's not much desire for a variant of C with what would be at least a 10x slowdown in many workloads.
- cv5005 2y ago
  Or it could be made faster because certain manual optimizations become possible. An example would a table of interned strings that you wanna match against (say you're writing a parser). Since standard C says thou shall not compare pointers with < or > unless they both point into the same 'object' you are forbidden from doing the speed of light code: char *keywords_begin, *keywords_end; if(some_str >= keywords_begin && some_str < keywords_end) ... Official standard sanctioned workarounds would require extra indirection (using indices for example) which is suboptimal.
  - gpderetta 2y ago
    You can cast them to uintptr_t and compare them to your heart's desire.
layer8 2y ago
That would restrict C to memory models with a linear address space. That is usually the case nowadays for C implementations, but maybe we don’t want to set that in stone, because it would be virtually impossible to revert such a guarantee. There’s also cases like memory address ranges that map to non-memory hardware (i.e. that don’t behave like “dumb” memory), and how would you have the C standard define behavior for those? Lastly, CPU caches require some sort of abstract model as soon as you have multi-threading.
Measter 2y ago
The value of an abstract machine is that it allows you to specify how a given program behaves without needing to point to a specific piece of hardware. Compilers then have this as a target when compiling a program for a specific piece of hardware so that they know when the compiler's output is correct. The issue here is that the abstract machine is under or badly specified.

Maybe we should get rid of "abstract machine" and treat pointers as memory addresses?

davidt84 2y ago

Congratulations, you've invented an entirely new language. Now, who's going to write the compiler for it?

anticensor 2y ago
No, it's C at -O0.
- davidt84 2y ago
  No, it's not. Undefined behaviour is undefined behaviour whatever optimisation level you use. Some -f flags may extend the C standard and remove undefined behaviour in some cases (e.g. strict aliasing, signed integer overflow, writable string constants, etc.)

gpderetta 2y ago

int* oracle(); int foo() { int x = 1; *oracle() = 42; return x; } Is the above program allowed to return anything other than 1 in your language?

kibwen 2y ago
To elaborate, we treat pointers as more than just integers because it gives optimizers the latitude to reorder and eliminate pointer operations. In the example above we cannot do this, because we cannot prove at compile time that x doesn't live at the address returned by oracle. For some high-quality further discussion, see Ralf Jung's series of blog posts starting with https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html
- shultays 2y ago
  However, given how low-level a language C++ is, we can actually break this assumption by setting i to y-x. Since &x[i] is the same as x+i, this means we are actually writing 23 to &y[0]. But that is undefined, you can't do x + (y - x) ie a pointer arithmetic that ends outside of bounds of an array. Since it is undefined, shouldn't C++ assume that changing x[..] can't change y[0] edit: welp, if I read a few more lines into article I would see that it also tells it is undefined
- gpderetta 2y ago
  to be clear, in my example the result of oracle() cannot possibly alias with 'x' in C or C++ (and in fact gcc will optimize accordingly). In a different language where addresses are mere integers, things would be more complicated.
  - codedokode 2y ago
    The result of oracle can point to anything if you write it as return (int *)rand(); Note that rand() returns 32-bit value so you have to call it twice and merge the results to obtain a 64-bit pointer.
    - gpderetta 2y ago
      The numerical value returned by oracle might physically match the address of the stack slot for 'x', assuming that it exists, but it doesn't mean that, from a language point of view, it is a valid pointer. If forging pointers had defined behaviour, it would be impossible to use the language sanely or perform any kind of optimization.
alerighi 2y ago
Well even in C is not guaranteed to return anything other than 1, since oracle() may return the memory address of variable 1.
- gpderetta 2y ago
  the literal 1 is not an object in C or C++ hence it does not have an address. If you meant 'x', then also no, oracle() can't return the address of 'x' because of pointer provenance rules.
shultays 2y ago
Is it allowed to return anything else in C? Is there anything in standard C that would allow oracle() to access memory address of x? Sure different compilers might allow inlining assembly or some other ways to access x on previous stack perhaps but then it is not really "C"
- wat10000 2y ago
  That’s the point. C allows this function to be optimized to always return 1. A “pointers are addresses, just emit reads and writes and stop trying to be so clever” version of C would require x to be spilled to the stack, then the write, then reload x and return whatever it contained.
  - cv5005 2y ago
    Then use the register keyword or just reword the standard to assume the register behavior if a variables address hasn't been taken. The majority of useful optimizations can be kept in a "Sane C" with either code style changes (cache stuff in local vars to avoid aliasing for example) or with minor tweaks to the standard.
    - wat10000 2y ago
      Register behavior is what you want essentially all of the time. So we’d just have to write `register` all over the place for no gain. “Don’t optimize this, read and write it even if you think it’s not necessary” is a very rare case so it shouldn’t be the default. If you want it, use the volatile keyword. There’s no need to reword the standard to assume the register behavior if the variable’s address hasn’t been taken. That’s already how it works. In this example, if you escape the value of `&x`, it’s not legal to optimize this function to always return 1.
codedokode 2y ago
When using C, this can return anything (or crash of oracle function returns an invalid pointer, or rewrite its own code if the code section is writable). So if you get rid of "abstract machine", nothing changes - the program can return anything or crash.
- wat10000 2y ago
  A conforming C compiler is allowed to emit that function to perform the write and then return the constant 1. Should that be allowed?
- atq2119 2y ago
  The point is that the C standard does guarantee that the function returns 1 if the program is a valid C program - which means there is no UB. For example: If the oracle function returns an invalid pointer, then dereferencing that pointer is UB, and therefore the program isn't a valid C program.
deleted 2y ago
[deleted]

sixfiveotwo 2y ago

How would you define what a memory address is without first defining in which context it has a meaning?

codedokode 2y ago
C was written as a portable assembly language, so I think a memory address is a number that CPU considers to be a memory address.
- layer8 2y ago
  That’s currently the case in C, in that you can convert pointers to and from uintptr_t. However, not every number representable in that type needs to be valid memory (that’s true on the assembly level as well), hence it’s only defined for valid pointers.
- sixfiveotwo 2y ago
  > I think a memory address is a number that CPU considers to be a memory address I meant to say that, indeed, there must be some concept of CPU for a memory address to have a meaning, and for this concept of CPU to be as widely applicable as possible, surely defining it as abstract as possible is the way to go. Ergo, the idea of a C abstract machine. Anyway, other people in this thread are discussing the matter more accurately and in more details than I could hope to do, so I'll leave it like that.

lmm 2y ago

20 years ago, making a C compiler that provided sane behaviour and better guarantees (going beyond the minimum defined in the standard) to make code safer and programmers' lives easier, even at the cost of some performance, might have been a good idea. Today any programmer who thinks things like not having security bugs are more important than having bigger numbers on microbenchmarks has already moved on from C.

uecker 2y ago
This is certainly not true. Many programmers also learned to the use tools available to write reasonably safe code in C. I do not personally find this problematic.
- quotemstr 2y ago
  > safe code in C You're like a Japanese holdout in the 60s refusing to leave his bunker long after the war is over. C lost. Memory safety is a huge boon for security. Human beings, even the best of them, cannot consistently write correct C code. (Look at OpenBSD.) You can keep fighting the war your side has already lost or you can move on.
  - uecker 2y ago
    Well, memory safety is great but it seems Rust programmers also manage to create memory safety issues just fine: https://rustsec.org/advisories/RUSTSEC-2024-0401.html https://rustsec.org/advisories/RUSTSEC-2024-0401.html https://rustsec.org/advisories/RUSTSEC-2024-0400.html https://rustsec.org/advisories/RUSTSEC-2024-0400.html https://rustsec.org/advisories/RUSTSEC-2024-0377.html https://rustsec.org/advisories/RUSTSEC-2024-0377.html https://rustsec.org/advisories/RUSTSEC-2024-0374.html https://rustsec.org/advisories/RUSTSEC-2024-0374.html etc.
    - whytevuhuni 2y ago
      I think the first one, stack overflow, is technically not a memory safety issue, just denial-of-service on resource exhaustion. Stack overflow is well defined as far as I know. The other three are definitely memory safety issues.

NobodyNada 2y ago

If you do this, your C code will run significantly slower than, say, Java, Go, or C#, because the compiler is unable to apply even the most basic optimizations (which it can do still in all those other languages). So, at that point why even use C at all? Today, C is used where the overhead of a managed language is unacceptable. If you could just eat the performance cost, you'd probably already be using a managed language. There's not much desire for a variant of C with what would be at least a 10x slowdown in many workloads.

cv5005 2y ago
Or it could be made faster because certain manual optimizations become possible. An example would a table of interned strings that you wanna match against (say you're writing a parser). Since standard C says thou shall not compare pointers with < or > unless they both point into the same 'object' you are forbidden from doing the speed of light code: char *keywords_begin, *keywords_end; if(some_str >= keywords_begin && some_str < keywords_end) ... Official standard sanctioned workarounds would require extra indirection (using indices for example) which is suboptimal.
- gpderetta 2y ago
  You can cast them to uintptr_t and compare them to your heart's desire.

layer8 2y ago

That would restrict C to memory models with a linear address space. That is usually the case nowadays for C implementations, but maybe we don’t want to set that in stone, because it would be virtually impossible to revert such a guarantee. There’s also cases like memory address ranges that map to non-memory hardware (i.e. that don’t behave like “dumb” memory), and how would you have the C standard define behavior for those? Lastly, CPU caches require some sort of abstract model as soon as you have multi-threading.

Measter 2y ago

The value of an abstract machine is that it allows you to specify how a given program behaves without needing to point to a specific piece of hardware. Compilers then have this as a target when compiling a program for a specific piece of hardware so that they know when the compiler's output is correct. The issue here is that the abstract machine is under or badly specified.