5 ms·

I’ve always thought this is a pretty big blindspot in Rust. Having a raw pointer and having an index into an array are essentially equivalent, and doing this in

by OskarS 3y ago

I’ve always thought this is a pretty big blindspot in Rust. Having a raw pointer and having an index into an array are essentially equivalent, and doing this in Rust is a way to turn off the borrow checker for this particular object. The index is bounds-checked, sure, but lifetime issues like “double free” or “use after free” are every bit as present with indexes. For instance, if you have an index in one place, but it’s deleted and/or reinitialized to some other place, you are now holding on to an object in an undefined state. Using it will cause the same issues “use-after-free” does in C. Best case scenario in that cases is that it crashes, but it’s just as likely your program will just silently be wrong. I’m not saying not to do it, I’m just saying this is something Rust developers needs to be aware of: storing indexes like that removes a whole bunch of safety guarantees the borrow checker checks for you, without any code marked “unsafe”.

hyperman1 3y ago
I'd say this is a case of the 'Inner platform' effect (Using a tool to build a poor replica of the tool) . Pointers are nothing more than indexes in the memory array. It turns out keeping track of what index does what is so hard, rust has a borrow checker to help with that. But sometimes it's annoying, so we create a workaround, and if we go too far with that workaround, we forget why we had a borrow checker to begin with. Notice how the array technique has parallels to memory: You can have multiple arrays of different types a.k.a segmented memory. You can mark unused array objects, a.k.a. overwrite free'd memory with 0xDEADBEEF.
- intelVISA 3y ago
  It's all memory in the end. Hide from it, fear it, run from it? It'll only cause you to develop maladative coping patterns like writing Go instead of beautiful C. Instead, attain Nirvana, open emacs and embrace Fearless Development.
- zokier 3y ago
  > Pointers are nothing more than indexes in the memory array. Pointers in C point to objects and not memory locations afaik, which has subtle semantic implications. See the whole discussion around pointer provenance.
gpderetta 3y ago
Reusing a dead index is bad, but not as bad as full memory unsafety. It can cause application errors for sure but the integrity of the runtime is preserved. Segregated, typed, heaps (never reuse the memory for a different type after a free) could allow similar safety.
- OskarS 3y ago
  I would say that this is an extremely narrow view of "memory safety", and totally ignores the broader concept of "lifetime safety". Yes, if the thing you want to prevent is crashes due to segfaults, indexes in Rust prevent that. But I would argue there's no practical difference between "crash due to segfault" and "panic due to index overflow" (which is definitely possible with the Rust model): both are just different ways of looking at "you dereferenced an invalid pointer". It does prevent the pointer writing into different data structures though, which is definitely an advantage of Rust (which comes with the runtime cost of bounds-checking, but that is probably worth it). But more generally: imagine you're making a game where you shoot a bunch of dudes, so you have a `std::Vec<Dude>` to store them, and elsewhere in the code, you reference this vec using indexes. When you shoot a dude, you want to remove it from this array, but being a programmer concerned about performance, you don't want to literally delete the entry, as that is an O(n) operation. Instead, you mark the dude as "despawned" or whatever, and then when you want to spawn a new dude, you keep a list of despawned dudes and just recreate the new dude in the same place in the array. If other places in the code are holding on to indexes to this array, the index is now invalid, but it will not be detectable: it'll just point to the wrong data, which can wreak all sorts of havoc. This is almost exactly equivalent to "use-after-free" issues in C. In most cases, `free()` will not literally free the memory, it will mark the memory as unused and stored in a free-list, to be available for the next `malloc()` call. If you're holding on to a pointer that has been free()d, it's not that the program will segfault, it's much more insidious than that: it will point to memory that is apparently valid, but actually garbage. This is precisely the kind of lifetime issue the Rust borrow checker was designed to solve, but by using indexes like this, you've basically just turned the borrow checker off without realizing it. If the borrow checker is intrusive enough that this becomes a very common pattern in Rust, I personally think it does serve as a pretty good counter-argument to a lot of things people say about Rust. Rust people are very quick to sing the borrow checker's praises and say that "as long as you learn to work with it, it stops becoming a problem!". If it stops becoming a problem only because you sneakily turn it off using tricks like this, maybe it's a bigger problem than people are willing to admit.
tialaramex 3y ago
> I’ve always thought this is a pretty big blindspot in Rust. Having a raw pointer and having an index into an array are essentially equivalent, and doing this in Rust is a way to turn off the borrow checker for this particular object. You've been poisoned by C, where this is literally how arrays work, they're just pointer arithmetic plus syntax sugar (which is why arr[x] == x[arr]) Rust's array type is an actual array, and so a lot of the problems you're worried about (which would be big pitfalls out of the box in C) only happen in Rust if you went to some effort to dig a hole for yourself so you could fall into it. > For instance, if you have an index in one place, but it’s deleted and/or reinitialized to some other place, you are now holding on to an object in an undefined state This idea of "objects in an undefined state" is a normal part of C, but Rust doesn't have it. So you'll have to go invent it for your types, so as to inflict this injury on yourself, and I have no doubt you'd eagerly do so maybe even persuading yourself that this way is "faster" or some such nonsense. You might sensibly store the indices as owned pseudo-reference types, akin to Unix file descriptors and various Windows handle types, both of which Rust manages as opaque owned objects (ie they don't implement Copy) and borrowed objects (which do Copy) Contrast: https://doc.rust-lang.org/std/os/fd/struct.OwnedFd.html https://doc.rust-lang.org/std/os/fd/struct.OwnedFd.html https://doc.rust-lang.org/std/os/windows/io/struct.BorrowedHandle.html https://doc.rust-lang.org/std/os/windows/io/struct.BorrowedH... When you treat them as opaque handles, it becomes more apparent whose job it is to ensure the handles work as intended. Nobody would say "Oh that's your problem, you used it wrong" if your open file handle to the settings file suddenly morphed into stdin because of unrelated code.
- OskarS 3y ago
  I wrote a longer response to a sibling comment, but I highly dispute this: > Rust's array type is an actual array, and so a lot of the problems you're worried about (which would be big pitfalls out of the box in C) only happen in Rust if you went to some effort to dig a hole for yourself so you could fall into it. It is an extremely easy hole to fall into. If you hold on to an index X into an array, and some different part of the program deleted an entry in the array with an index smaller than X, your X is now no longer valid, it's pointing to the wrong object. This is exactly equivalent to an "invalidated pointer", which is an issue the borrow checker was designed to solve. But there is no way for it to know this, because by using indexes instead of pointers, you've disabled its ability to analyze this situation. I agree that pointers in C and indexes in Rust are not the same thing, and there are other issues with C pointers that Rust's borrow checker solves. But imagining that you're magically safe from any lifetime issues "because Rust" is foolish.
dwattttt 3y ago
I haven't had need to use it, but an improvement on the "I have an index to an object which has been replaced" has been to add a generation to the collection & index, a la the generational_arena crate. If the generation attached to your index doesn't match the generation in the collection at that index, your index is stale.
pyjarrett 3y ago
> Having a raw pointer and having an index into an array are essentially equivalent You can split the handle (index) into an upper "magic" and lower "index" part, with the handle being an opaque type, only being able to be accessed and modified by the container giving out handles. In C++, you'd likely see operator* and operator-> overloaded for usage. This technique is described in the original "Game Programming Gems" book. Not 100%, but on usage, the handle checks the magic against what's currently in the data-structure to let you know if the handle has been freed and/or reused. Since handles are opaque, you can muck with the underlying objects as you want, e.g relocate them in memory, having multiple internal arrays, etc.

by OskarS 3y ago

hyperman1 3y ago

I'd say this is a case of the 'Inner platform' effect (Using a tool to build a poor replica of the tool) . Pointers are nothing more than indexes in the memory array. It turns out keeping track of what index does what is so hard, rust has a borrow checker to help with that. But sometimes it's annoying, so we create a workaround, and if we go too far with that workaround, we forget why we had a borrow checker to begin with. Notice how the array technique has parallels to memory: You can have multiple arrays of different types a.k.a segmented memory. You can mark unused array objects, a.k.a. overwrite free'd memory with 0xDEADBEEF.

intelVISA 3y ago
It's all memory in the end. Hide from it, fear it, run from it? It'll only cause you to develop maladative coping patterns like writing Go instead of beautiful C. Instead, attain Nirvana, open emacs and embrace Fearless Development.
zokier 3y ago
> Pointers are nothing more than indexes in the memory array. Pointers in C point to objects and not memory locations afaik, which has subtle semantic implications. See the whole discussion around pointer provenance.

gpderetta 3y ago

Reusing a dead index is bad, but not as bad as full memory unsafety. It can cause application errors for sure but the integrity of the runtime is preserved. Segregated, typed, heaps (never reuse the memory for a different type after a free) could allow similar safety.

OskarS 3y ago
I would say that this is an extremely narrow view of "memory safety", and totally ignores the broader concept of "lifetime safety". Yes, if the thing you want to prevent is crashes due to segfaults, indexes in Rust prevent that. But I would argue there's no practical difference between "crash due to segfault" and "panic due to index overflow" (which is definitely possible with the Rust model): both are just different ways of looking at "you dereferenced an invalid pointer". It does prevent the pointer writing into different data structures though, which is definitely an advantage of Rust (which comes with the runtime cost of bounds-checking, but that is probably worth it). But more generally: imagine you're making a game where you shoot a bunch of dudes, so you have a `std::Vec<Dude>` to store them, and elsewhere in the code, you reference this vec using indexes. When you shoot a dude, you want to remove it from this array, but being a programmer concerned about performance, you don't want to literally delete the entry, as that is an O(n) operation. Instead, you mark the dude as "despawned" or whatever, and then when you want to spawn a new dude, you keep a list of despawned dudes and just recreate the new dude in the same place in the array. If other places in the code are holding on to indexes to this array, the index is now invalid, but it will not be detectable: it'll just point to the wrong data, which can wreak all sorts of havoc. This is almost exactly equivalent to "use-after-free" issues in C. In most cases, `free()` will not literally free the memory, it will mark the memory as unused and stored in a free-list, to be available for the next `malloc()` call. If you're holding on to a pointer that has been free()d, it's not that the program will segfault, it's much more insidious than that: it will point to memory that is apparently valid, but actually garbage. This is precisely the kind of lifetime issue the Rust borrow checker was designed to solve, but by using indexes like this, you've basically just turned the borrow checker off without realizing it. If the borrow checker is intrusive enough that this becomes a very common pattern in Rust, I personally think it does serve as a pretty good counter-argument to a lot of things people say about Rust. Rust people are very quick to sing the borrow checker's praises and say that "as long as you learn to work with it, it stops becoming a problem!". If it stops becoming a problem only because you sneakily turn it off using tricks like this, maybe it's a bigger problem than people are willing to admit.

tialaramex 3y ago

> I’ve always thought this is a pretty big blindspot in Rust. Having a raw pointer and having an index into an array are essentially equivalent, and doing this in Rust is a way to turn off the borrow checker for this particular object. You've been poisoned by C, where this is literally how arrays work, they're just pointer arithmetic plus syntax sugar (which is why arr[x] == x[arr]) Rust's array type is an actual array, and so a lot of the problems you're worried about (which would be big pitfalls out of the box in C) only happen in Rust if you went to some effort to dig a hole for yourself so you could fall into it. > For instance, if you have an index in one place, but it’s deleted and/or reinitialized to some other place, you are now holding on to an object in an undefined state This idea of "objects in an undefined state" is a normal part of C, but Rust doesn't have it. So you'll have to go invent it for your types, so as to inflict this injury on yourself, and I have no doubt you'd eagerly do so maybe even persuading yourself that this way is "faster" or some such nonsense. You might sensibly store the indices as owned pseudo-reference types, akin to Unix file descriptors and various Windows handle types, both of which Rust manages as opaque owned objects (ie they don't implement Copy) and borrowed objects (which do Copy) Contrast: https://doc.rust-lang.org/std/os/fd/struct.OwnedFd.html https://doc.rust-lang.org/std/os/fd/struct.OwnedFd.html https://doc.rust-lang.org/std/os/windows/io/struct.BorrowedHandle.html https://doc.rust-lang.org/std/os/windows/io/struct.BorrowedH... When you treat them as opaque handles, it becomes more apparent whose job it is to ensure the handles work as intended. Nobody would say "Oh that's your problem, you used it wrong" if your open file handle to the settings file suddenly morphed into stdin because of unrelated code.

OskarS 3y ago
I wrote a longer response to a sibling comment, but I highly dispute this: > Rust's array type is an actual array, and so a lot of the problems you're worried about (which would be big pitfalls out of the box in C) only happen in Rust if you went to some effort to dig a hole for yourself so you could fall into it. It is an extremely easy hole to fall into. If you hold on to an index X into an array, and some different part of the program deleted an entry in the array with an index smaller than X, your X is now no longer valid, it's pointing to the wrong object. This is exactly equivalent to an "invalidated pointer", which is an issue the borrow checker was designed to solve. But there is no way for it to know this, because by using indexes instead of pointers, you've disabled its ability to analyze this situation. I agree that pointers in C and indexes in Rust are not the same thing, and there are other issues with C pointers that Rust's borrow checker solves. But imagining that you're magically safe from any lifetime issues "because Rust" is foolish.

dwattttt 3y ago

I haven't had need to use it, but an improvement on the "I have an index to an object which has been replaced" has been to add a generation to the collection & index, a la the generational_arena crate. If the generation attached to your index doesn't match the generation in the collection at that index, your index is stale.

pyjarrett 3y ago

> Having a raw pointer and having an index into an array are essentially equivalent You can split the handle (index) into an upper "magic" and lower "index" part, with the handle being an opaque type, only being able to be accessed and modified by the container giving out handles. In C++, you'd likely see operator* and operator-> overloaded for usage. This technique is described in the original "Game Programming Gems" book. Not 100%, but on usage, the handle checks the magic against what's currently in the data-structure to let you know if the handle has been freed and/or reused. Since handles are opaque, you can muck with the underlying objects as you want, e.g relocate them in memory, having multiple internal arrays, etc.