3 ms·

Frankly, it always feels a bit wrong to me to get around Rust's strictness for pointers by just replacing them with IDs/indexes/offsets into some collection. Yo

by oersted 6mo ago

Frankly, it always feels a bit wrong to me to get around Rust's strictness for pointers by just replacing them with IDs/indexes/offsets into some collection. You can still have many of the same memory-safety issues as with pointers, except that now they become logic bugs that are undetectable by the compiler. Either use unsafe and think about using raw pointers carefully, respecting the soundness rules, or truly redesign it using idiomatic Rust constructs. But don't hide complexity under the rug by using indexes instead of pointers, it's mostly the same thing. I really enjoyed the write-up though, I learned a lot from it, not to discount that.

zozbot234 6mo ago
Logic bugs are not memory safety issues, they're logic bugs. They cannot result in undefined behavior for the program as a whole, at least in the absence of unsafe code.
- oersted 6mo ago
  As far as I understand, memory safety goes well beyond undefined behavior. It’s a loose term including common pointer manipulation, allocation/deallocation and data-race issues. Other than UB, using indexes instead of pointers can be exactly as error-prone and leads to the same kind of unexpected runtime crashes, memory corruption and security issues. It’s a false sense of security. If you inspect the OP implementation in detail, you’ll notice that it is still plenty open to use-after-free bugs and lots of places where it can panic in an equivalent way to a segmentation fault. It is quite unsafe while not being “unsafe”.
  - zozbot234 6mo ago
    > it can panic in an equivalent way to a segmentation fault. So, like bounds-checked array access? That's also a logic error. Common pointer manipulation (in the presence of discriminated union types), allocation/deallocation errors and data races (when involving array indexes, pointers or tagged data, not just simple valye types) can all lead to UB; bounds-checked array access on its own cannot.
  - adrian_b 6mo ago
    Bugs in the use of indexes can corrupt memory only inside the corresponding array, they cannot corrupt arbitrary memory locations, like pointers. Such a corrupted array should never cause a program crash, unless there is a second bug where unexpected values in the corrupted array can cause crashes or unless it is intended that any detected bug must abort the program, when it does not matter whether pointers or indexes were used. Thus using indexes should always be safer than using pointers. In modern CPUs, indexed addressing is as fast as addressing through a register that holds a pointer, which removes the main reason why pointers were preferred in the seventies of the last century, by the time of the C language design, when in most minicomputers and microcomputers using pointers was faster than using indexes.
    - oersted 6mo ago
      Here OP is implementing a full allocator and something close to a new abstract layer of virtual memory backed by vectors and addressed by offsets. For some use-cases, you will probably keep all dynamically allocated objects in this memory. At that point you have circumvented most of Rust’s protections and ergonomics. The user will effectively be working with raw pointers into this memory. The implementation itself also doesn’t have the proper checks because it is manipulating indexes instead of pointers. The post itself notes around the end how it is fairly easy to end up with a dangling pointer or one that points to a different object allocated to the same position after the old one was freed. It also has quite a few places where it can panic. And implementing its Trace trait wrong or not using Roots as intended can have complex consequences. And all that while feeling like this is the most safe GC because it has no unsafe. I don’t disagree with anything you said, and I also quite like the work from OP. But I hope you can see that this is not fully aligned with Rust’s philosophy.
afdbcreid 6mo ago
If we compare 1-to-1 indices to unsafe code, indices always win (assuming they are viable wrt. perf etc.). This is very simple: all else being equal, a mistake in unsafe code (can be) UB while a mistake in indices is at most a logic bug, and logic bug is always preferred to UB. Of course, it does mean we should compare them 1-to-1, which means we should treat the indices code like we would treat unsafe code. The most important conclusion is to encapsulate it in a data structure without business logic.
- kccqzy 6mo ago
  Yeah but logic bugs cannot be found by tools. Whereas for UB at least we have address sanitizer and UB sanitizer and valgrind and many similar tools. You can recreate what these tools do in your API, and that’s extra work: a use-after-free bug may be easily detected by these tools, but when you are managing indices yourself, you may have to add assertions yourself to check for things that are logically deleted but not actually deleted.
dwroberts 6mo ago
> But don't hide complexity under the rug by using indexes instead of pointers, it's mostly the same thing. I think the simple fact that pointers are not guaranteed aligned/valid even if they are in range of a particular slice/collection etc. actually makes it very different

by oersted 6mo ago

zozbot234 6mo ago

Logic bugs are not memory safety issues, they're logic bugs. They cannot result in undefined behavior for the program as a whole, at least in the absence of unsafe code.

oersted 6mo ago
As far as I understand, memory safety goes well beyond undefined behavior. It’s a loose term including common pointer manipulation, allocation/deallocation and data-race issues. Other than UB, using indexes instead of pointers can be exactly as error-prone and leads to the same kind of unexpected runtime crashes, memory corruption and security issues. It’s a false sense of security. If you inspect the OP implementation in detail, you’ll notice that it is still plenty open to use-after-free bugs and lots of places where it can panic in an equivalent way to a segmentation fault. It is quite unsafe while not being “unsafe”.
- zozbot234 6mo ago
  > it can panic in an equivalent way to a segmentation fault. So, like bounds-checked array access? That's also a logic error. Common pointer manipulation (in the presence of discriminated union types), allocation/deallocation errors and data races (when involving array indexes, pointers or tagged data, not just simple valye types) can all lead to UB; bounds-checked array access on its own cannot.
- adrian_b 6mo ago
  Bugs in the use of indexes can corrupt memory only inside the corresponding array, they cannot corrupt arbitrary memory locations, like pointers. Such a corrupted array should never cause a program crash, unless there is a second bug where unexpected values in the corrupted array can cause crashes or unless it is intended that any detected bug must abort the program, when it does not matter whether pointers or indexes were used. Thus using indexes should always be safer than using pointers. In modern CPUs, indexed addressing is as fast as addressing through a register that holds a pointer, which removes the main reason why pointers were preferred in the seventies of the last century, by the time of the C language design, when in most minicomputers and microcomputers using pointers was faster than using indexes.
  - oersted 6mo ago
    Here OP is implementing a full allocator and something close to a new abstract layer of virtual memory backed by vectors and addressed by offsets. For some use-cases, you will probably keep all dynamically allocated objects in this memory. At that point you have circumvented most of Rust’s protections and ergonomics. The user will effectively be working with raw pointers into this memory. The implementation itself also doesn’t have the proper checks because it is manipulating indexes instead of pointers. The post itself notes around the end how it is fairly easy to end up with a dangling pointer or one that points to a different object allocated to the same position after the old one was freed. It also has quite a few places where it can panic. And implementing its Trace trait wrong or not using Roots as intended can have complex consequences. And all that while feeling like this is the most safe GC because it has no unsafe. I don’t disagree with anything you said, and I also quite like the work from OP. But I hope you can see that this is not fully aligned with Rust’s philosophy.

afdbcreid 6mo ago

If we compare 1-to-1 indices to unsafe code, indices always win (assuming they are viable wrt. perf etc.). This is very simple: all else being equal, a mistake in unsafe code (can be) UB while a mistake in indices is at most a logic bug, and logic bug is always preferred to UB. Of course, it does mean we should compare them 1-to-1, which means we should treat the indices code like we would treat unsafe code. The most important conclusion is to encapsulate it in a data structure without business logic.

kccqzy 6mo ago
Yeah but logic bugs cannot be found by tools. Whereas for UB at least we have address sanitizer and UB sanitizer and valgrind and many similar tools. You can recreate what these tools do in your API, and that’s extra work: a use-after-free bug may be easily detected by these tools, but when you are managing indices yourself, you may have to add assertions yourself to check for things that are logically deleted but not actually deleted.

dwroberts 6mo ago

> But don't hide complexity under the rug by using indexes instead of pointers, it's mostly the same thing. I think the simple fact that pointers are not guaranteed aligned/valid even if they are in range of a particular slice/collection etc. actually makes it very different