14 ms·

First, we take some of the safety into our own hands. While this approach won't result in corrupted memory, double frees or accessing freed pointers, it can lea

by rjeli 2y ago

First, we take some of the safety into our own hands. While this approach won't result in corrupted memory, double frees or accessing freed pointers, it can lead to run-time panics and other problems because we deal in "raw" indices to a vector. Yeah, I’ve often seen people in discussions about c/zig/rust memory saying “manual memory management is fine, just use an arena and handles!” It’s a strange statement to me because you’re just laundering the unsafe pointer arithmetic behind array indexing

bbatha 2y ago
The difference is that the array bounds are checked and the behavior is defined whereas bad unsafe pointer athematic if you’re lucky gives you a segfault and at worst an RCE.
- alexchamberlain 2y ago
  Array bounds are essentially unchecked in C, unless you go so far over as to hit a guard page.
empath-nirvana 2y ago
You can have bugs with that style of coding, but they're not going to be bugs of the "remote code execution" type.
- googh 2y ago
  If preventing remote code execution is the goal, then C/C++/Zig can also achieve this using isoheaps (see Fil-C[1] for example). Even without isoheaps, CFI mitigations are able to prevent jumps into code not known at compile time. Why bother with Rust or any other language with borrow checkers then? Just a honest question. [1] - https://github.com/pizlonator/llvm-project-deluge/blob/deluge/Manifesto.md https://github.com/pizlonator/llvm-project-deluge/blob/delug...
agalunar 2y ago
Using indices is a (slight) improvement over pointers, since in Rust you will benefit from bounds checking (restricting you to the memory allocated for that tree). (If you use u32 for the indices, you also save some space.)
- taeric 2y ago
  It is hilarious how much space you can save by using smaller indexes than a pointer. Especially on modern architectures.
  - burntsushi 2y ago
    Yes! The regex crate does this and it saves quite a bit of memory.
    - taeric 2y ago
      It is the kind of low hanging optimization that I used to think was greatly oversold. And, to be fair, for many programs I would still wager it probably is. If you are chasing a ton of pointers, though, it is definitely worth considering how many more you can hold in memory with smaller sizes. I think I remember a discussion a while back lamenting that we just tacitly accepted wide pointers. If anyone has a link going over that, I'd be delighted to read it again. I'm 90% sure I did not understand it when I first saw it. :D
- eclark 2y ago
  I am currently writing a CFR Tree that has nodes that can be self-referential. https://github.com/elliottneilclark/rs-poker/pull/92 https://github.com/elliottneilclark/rs-poker/pull/92 The idea is that every game of poker is a walk through a tree. Keeping track of probabilities and outcomes allows for exploration of the correct way to play. Using indices made building the tree easier (though I am still one bug away from it all working).
- deleted 2y ago
  [deleted]
10000truths 2y ago
The laundering is the point. It's much easier for the user to handle out-of-bounds array accesses and uninitialized array elements, compared to tracking the lifetime and validity of data at arbitrary memory addresses.
favorited 2y ago
The arena + handles approach doesn't solve the memory management issue, but it can be beneficial for storing nodes in a list, graph, etc. from a data locality perspective.
burntsushi 2y ago
> you’re just laundering the unsafe pointer arithmetic behind array indexing Perhaps true in a very narrow sense, but you could say the same thing about all of Rust. "It's just laundering unsafe stuff behind a safe interface." And indeed, the ability to encapsulate unsafe internals inside a safe interface is one of the primary selling points of the language. It is also one of the key characteristics that differentiate it from languages that do not currently have this ability, such as C and C++. Whether you think this is an actual advantage or not is I suppose up to you, but I certainly think it is. And I think your use of the word "just" is papering over a lot of stuff. For a more concrete code-level comparison with C, I did the leg work to translate a C program to a number of different Rust programs by varying some constraints. One of those Rust programs does indeed use indices instead of pointers. The README talks about the trade offs. See: https://github.com/BurntSushi/rsc-regexp/ https://github.com/BurntSushi/rsc-regexp/
- Chabsff 2y ago
  > languages that do not currently have this ability That seems to be a very common position, and one that's super weird to me. C and particularly C++ absolutely have that ability with library support if you know what you are doing. The only material difference, from my point of view, is that the default behavior of the language is different. I will fully grant that the path of least resistance being dangerous is a huge issue in C/C++, and one that Rust addresses, but extending that all the way to saying that the language lacks the ability is really excessive.
  - tialaramex 2y ago
    There's a big cultural problem and there are several big technical problems. Rust has a safety culture, and C++ does not. In Rust's safety culture it was obvious that std::mem::unintialized (an unsafe function) should be deprecated because it's more dangerous than it appears, it's actually hard to use it correctly. That's why today we have the MaybeUninit type. In C++ it was apparently equally obvious that std::span, a brand new type in C++ 20, should not have a safe index operation. Technically the safe/ unsafe distinction being at the language level makes it hard to fake. You can say your C++ only uses your safe abstractions, but the language itself doesn't care, so without inspecting every part of it to check you're never more than one slip away from catastrophe. Most importantly in this context, at the language level Rust is committed to this safety distinction. If you write code where Rust's compiler can't see why it's OK, the compiler rejects your program. C++ requires that a conforming compiler must instead accept programs unless it can show why they're wrong. These are two possible ways to cut the Gordion knot of Rice's Theorem, but they have very different consequences.
akavel 2y ago
There's a huge difference in the outcomes those can lead to, that's why it's not just a simple "laundering", but a serious gain. On top of that, C vs. Zig vs. Rust give you a different level of that gain still. The particular difference is noted in the fragment you quoted. What may not be obvious, is why corrupted memory etc. are a much bigger problem than panics. In fact it is usually the _lack_ of panics that is problem in them: they will lead to silent memory corruption. This will lead to unexpected behaviors of your code. Ones you just never even assumed possible - due to basic contracts being broken. Such problems with then silently propagate through your system, poisoning it without you knowing. Whereas a panic is a clear cut alarm/canary behavior: something's wrong, let's crash loudly and make it immediately visible. This will protect against the corruption spreading out. And in a typical system, will restart the panicked binary, allowing the system to resume operation with minimal disruption.
deleted 2y ago
[deleted]
kelnos 2y ago
There's a big difference, though: the array indexing code is still safe from memory errors. I would much prefer a panic over a segfault.

by rjeli 2y ago

bbatha 2y ago

The difference is that the array bounds are checked and the behavior is defined whereas bad unsafe pointer athematic if you’re lucky gives you a segfault and at worst an RCE.

alexchamberlain 2y ago
Array bounds are essentially unchecked in C, unless you go so far over as to hit a guard page.

empath-nirvana 2y ago

You can have bugs with that style of coding, but they're not going to be bugs of the "remote code execution" type.

googh 2y ago
If preventing remote code execution is the goal, then C/C++/Zig can also achieve this using isoheaps (see Fil-C[1] for example). Even without isoheaps, CFI mitigations are able to prevent jumps into code not known at compile time. Why bother with Rust or any other language with borrow checkers then? Just a honest question. [1] - https://github.com/pizlonator/llvm-project-deluge/blob/deluge/Manifesto.md https://github.com/pizlonator/llvm-project-deluge/blob/delug...

agalunar 2y ago

Using indices is a (slight) improvement over pointers, since in Rust you will benefit from bounds checking (restricting you to the memory allocated for that tree). (If you use u32 for the indices, you also save some space.)

taeric 2y ago
It is hilarious how much space you can save by using smaller indexes than a pointer. Especially on modern architectures.
- burntsushi 2y ago
  Yes! The regex crate does this and it saves quite a bit of memory.
  - taeric 2y ago
    It is the kind of low hanging optimization that I used to think was greatly oversold. And, to be fair, for many programs I would still wager it probably is. If you are chasing a ton of pointers, though, it is definitely worth considering how many more you can hold in memory with smaller sizes. I think I remember a discussion a while back lamenting that we just tacitly accepted wide pointers. If anyone has a link going over that, I'd be delighted to read it again. I'm 90% sure I did not understand it when I first saw it. :D
eclark 2y ago
I am currently writing a CFR Tree that has nodes that can be self-referential. https://github.com/elliottneilclark/rs-poker/pull/92 https://github.com/elliottneilclark/rs-poker/pull/92 The idea is that every game of poker is a walk through a tree. Keeping track of probabilities and outcomes allows for exploration of the correct way to play. Using indices made building the tree easier (though I am still one bug away from it all working).
deleted 2y ago
[deleted]

10000truths 2y ago

The laundering is the point. It's much easier for the user to handle out-of-bounds array accesses and uninitialized array elements, compared to tracking the lifetime and validity of data at arbitrary memory addresses.

favorited 2y ago

The arena + handles approach doesn't solve the memory management issue, but it can be beneficial for storing nodes in a list, graph, etc. from a data locality perspective.

burntsushi 2y ago

> you’re just laundering the unsafe pointer arithmetic behind array indexing Perhaps true in a very narrow sense, but you could say the same thing about all of Rust. "It's just laundering unsafe stuff behind a safe interface." And indeed, the ability to encapsulate unsafe internals inside a safe interface is one of the primary selling points of the language. It is also one of the key characteristics that differentiate it from languages that do not currently have this ability, such as C and C++. Whether you think this is an actual advantage or not is I suppose up to you, but I certainly think it is. And I think your use of the word "just" is papering over a lot of stuff. For a more concrete code-level comparison with C, I did the leg work to translate a C program to a number of different Rust programs by varying some constraints. One of those Rust programs does indeed use indices instead of pointers. The README talks about the trade offs. See: https://github.com/BurntSushi/rsc-regexp/ https://github.com/BurntSushi/rsc-regexp/

Chabsff 2y ago
> languages that do not currently have this ability That seems to be a very common position, and one that's super weird to me. C and particularly C++ absolutely have that ability with library support if you know what you are doing. The only material difference, from my point of view, is that the default behavior of the language is different. I will fully grant that the path of least resistance being dangerous is a huge issue in C/C++, and one that Rust addresses, but extending that all the way to saying that the language lacks the ability is really excessive.
- tialaramex 2y ago
  There's a big cultural problem and there are several big technical problems. Rust has a safety culture, and C++ does not. In Rust's safety culture it was obvious that std::mem::unintialized (an unsafe function) should be deprecated because it's more dangerous than it appears, it's actually hard to use it correctly. That's why today we have the MaybeUninit type. In C++ it was apparently equally obvious that std::span, a brand new type in C++ 20, should not have a safe index operation. Technically the safe/ unsafe distinction being at the language level makes it hard to fake. You can say your C++ only uses your safe abstractions, but the language itself doesn't care, so without inspecting every part of it to check you're never more than one slip away from catastrophe. Most importantly in this context, at the language level Rust is committed to this safety distinction. If you write code where Rust's compiler can't see why it's OK, the compiler rejects your program. C++ requires that a conforming compiler must instead accept programs unless it can show why they're wrong. These are two possible ways to cut the Gordion knot of Rice's Theorem, but they have very different consequences.

akavel 2y ago

There's a huge difference in the outcomes those can lead to, that's why it's not just a simple "laundering", but a serious gain. On top of that, C vs. Zig vs. Rust give you a different level of that gain still. The particular difference is noted in the fragment you quoted. What may not be obvious, is why corrupted memory etc. are a much bigger problem than panics. In fact it is usually the _lack_ of panics that is problem in them: they will lead to silent memory corruption. This will lead to unexpected behaviors of your code. Ones you just never even assumed possible - due to basic contracts being broken. Such problems with then silently propagate through your system, poisoning it without you knowing. Whereas a panic is a clear cut alarm/canary behavior: something's wrong, let's crash loudly and make it immediately visible. This will protect against the corruption spreading out. And in a typical system, will restart the panicked binary, allowing the system to resume operation with minimal disruption.

deleted 2y ago

[deleted]

kelnos 2y ago

There's a big difference, though: the array indexing code is still safe from memory errors. I would much prefer a panic over a segfault.