5 ms·

Usually programmers expect to destroy objects in some specific location. For example, if a widget is removed from a window and then goes out of scope, then most

Usually programmers expect to destroy objects in some specific location. For example, if a widget is removed from a window and then goes out of scope, then most programmers would expect it to be destroyed shortly thereafter. If there are actually references to the object remaining, contrary to programmers' intent, then one of four things can happen: 1. Use-after-free (C, C++). This is a logic bug and a security problem. 2. "Logically" dangling pointers (safe languages with non-generational indices). This is a logic bug, but not a security problem. 3. A memory leak (safe languages with garbage collectors). This is a bug that can be difficult to track down. 4. Panic/exception (safe languages with generational indices or weak pointers). This is a runtime failure. I'd argue that, of these four options, (4) is generally the best. The ideal would of course be a static guarantee instead of any of these. However, static guarantees always come with restrictions of some kind. For the truly unrestricted case, in which your data references are completely irregular, I'm not sure you can really do better.

josephg 8y ago
The point still stands. If you hold an index into an array of widgets, and the widget you reference is removed or replaced in the array, you could get behaviours 1, 2 or 4 depending on your implementation. Rust's index-into-array pattern removes the possibility of memory leaks, but it also removes most of the benefit of having a borrow checker in the first place. Its basically a less performant, less ergonomic version of using raw C pointers. Less ergonomic because you need to write your own allocator for your array. And its less performant because fetching the associated struct from memory requires 2 fetches rather than 1. If you're convinced dynamic memory management is the only solution to your data structure, rust's unsafe{} seems a better choice. Its in the language for a reason.
- pcwalton 8y ago
  You can't get security vulnerabilities due to use-after-free if you use indices. Don't use unsafe for this.
  - pjmlp 8y ago
    Sure you can. If my index 2 now contains the contents of lets say index 5, due to array rearrangement after deletion of the element at 2, whatever happens with data[idx].is_data_valid() is not what the developer would be expecting.
    - Munksgaard 8y ago
      Easily solved with generational indexes as described in https://www.youtube.com/watch?v=aKLntZcp27M https://www.youtube.com/watch?v=aKLntZcp27M
      - pjmlp 8y ago
        I have seen that talk. To me it feels a bit like a workaround for something that cannot be validated by the borrow checker, because it is something that developers have to go the extra mile to implement, or get a third party library, which someone has to validate that actually works as expected. In a way, it isn't much different than expecting C and C++ developers to use static analysis for lifetime validations. Meaning, using a tool outside of the core language for added safety.
        kibwen 8y ago
        > To me it feels a bit like a workaround for something that cannot be validated by the borrow checker Is it so hard to believe that references are not the correct abstraction for 100% of use cases? Reaching for something other than references when references are the wrong tool for the job is not working around the borrow checker; it's choosing the right abstraction for the right task. Being hung up on the borrow checker is missing the forest for the trees. > get a third party library, which someone has to validate that actually works as expected. How is this different from using any third-party library, ever? > Meaning, using a tool outside of the core language for added safety. Rust explicitly supports users defining their own smart pointer types to provide pointer-like abstractions with custom semantics; using tools outside of the core language for added safety (for whatever definition of "safety" one wants) is completely expected and encouraged.
beagle3 8y ago
> 2. "Logically" dangling pointers (safe languages with non-generational indices). This is a logic bug, but not a security problem. Many logic bugs become security issues. This specific one -- by way of TOCTOU races -- is one of the richest sources of security issues in Unix. The proposed "dormant index" solution is likely to generate a lot of these as well.
- kibwen 8y ago
  > The proposed "dormant index" solution is likely to generate a lot of these as well. What is a dormant index? I've not seen anything like this proposed, or heard the terminology before.
  - beagle3 8y ago
    I borrowed the terminology from ryani’s comment above; it’s the same thing you are discussing iirc, weak reference expressed by an index into a container and some way to identify that container (expressed or implied). I like the “dormant” name because unlike a weak pointer (say, in Java or Python), you can’t use it directly - you have to borrow the actual object to use it; so it lies “dormant” until you wake it up. It’s not (necessarily) weak because there is no automatic destruction once all other references are gone.
esrauch 8y ago
I think the disconnect for me is that circular references just aren't "irregular", they are the natural expression for doubly linked lists, trees with references to parents, etc: these usage patterns are the primary cause of memory issues that I come across in C++. In other words, static safety in the face of circular references is what would provide me a major clear advantage for better-than-C++, and unfortunately that doesn't seem to be something that is even seen as an opportunity for Rust given all of the rhetoric about that being an abnormal pattern and index-into-array being safe enough under that world.
- littlestymaar 8y ago
  > In other words, static safety in the face of circular references is what would provide me a major clear advantage for better-than-C++, and unfortunately that doesn't seem to be something that is even seen as an opportunity for Rust. Having a compiler able to solve the halting problem would also be “a major clear advantage for better-than-C++”, but too bad it's impossible … Arbitrary circular graphs can't be statically managed, that's it. Your need a runtime support, and it will either be a garbage collector, or some kind of constructions with array an indices.
  - AstralStorm 8y ago
    Circular graphs are perfectly possible to detect and manage compile time. It just takes a massively not complex borrow checker to run full dependency analysis to find where and if the cycle is broken or the whole thing released. Checking for graph cycle is elementary CS - planning the entry/exit nodes is not. It is similar to link time optimization to implement.
    - staticassertion 8y ago
      > Checking for graph cycle is elementary CS Yeah, but that's for built graphs, not graphs that will be built at runtime? Seems really, really different.

josephg 8y ago

The point still stands. If you hold an index into an array of widgets, and the widget you reference is removed or replaced in the array, you could get behaviours 1, 2 or 4 depending on your implementation. Rust's index-into-array pattern removes the possibility of memory leaks, but it also removes most of the benefit of having a borrow checker in the first place. Its basically a less performant, less ergonomic version of using raw C pointers. Less ergonomic because you need to write your own allocator for your array. And its less performant because fetching the associated struct from memory requires 2 fetches rather than 1. If you're convinced dynamic memory management is the only solution to your data structure, rust's unsafe{} seems a better choice. Its in the language for a reason.

pcwalton 8y ago
You can't get security vulnerabilities due to use-after-free if you use indices. Don't use unsafe for this.
- pjmlp 8y ago
  Sure you can. If my index 2 now contains the contents of lets say index 5, due to array rearrangement after deletion of the element at 2, whatever happens with data[idx].is_data_valid() is not what the developer would be expecting.
  - Munksgaard 8y ago
    Easily solved with generational indexes as described in https://www.youtube.com/watch?v=aKLntZcp27M https://www.youtube.com/watch?v=aKLntZcp27M
    - pjmlp 8y ago
      I have seen that talk. To me it feels a bit like a workaround for something that cannot be validated by the borrow checker, because it is something that developers have to go the extra mile to implement, or get a third party library, which someone has to validate that actually works as expected. In a way, it isn't much different than expecting C and C++ developers to use static analysis for lifetime validations. Meaning, using a tool outside of the core language for added safety.
      - kibwen 8y ago
        > To me it feels a bit like a workaround for something that cannot be validated by the borrow checker Is it so hard to believe that references are not the correct abstraction for 100% of use cases? Reaching for something other than references when references are the wrong tool for the job is not working around the borrow checker; it's choosing the right abstraction for the right task. Being hung up on the borrow checker is missing the forest for the trees. > get a third party library, which someone has to validate that actually works as expected. How is this different from using any third-party library, ever? > Meaning, using a tool outside of the core language for added safety. Rust explicitly supports users defining their own smart pointer types to provide pointer-like abstractions with custom semantics; using tools outside of the core language for added safety (for whatever definition of "safety" one wants) is completely expected and encouraged.

beagle3 8y ago

> 2. "Logically" dangling pointers (safe languages with non-generational indices). This is a logic bug, but not a security problem. Many logic bugs become security issues. This specific one -- by way of TOCTOU races -- is one of the richest sources of security issues in Unix. The proposed "dormant index" solution is likely to generate a lot of these as well.

kibwen 8y ago
> The proposed "dormant index" solution is likely to generate a lot of these as well. What is a dormant index? I've not seen anything like this proposed, or heard the terminology before.
- beagle3 8y ago
  I borrowed the terminology from ryani’s comment above; it’s the same thing you are discussing iirc, weak reference expressed by an index into a container and some way to identify that container (expressed or implied). I like the “dormant” name because unlike a weak pointer (say, in Java or Python), you can’t use it directly - you have to borrow the actual object to use it; so it lies “dormant” until you wake it up. It’s not (necessarily) weak because there is no automatic destruction once all other references are gone.

esrauch 8y ago

I think the disconnect for me is that circular references just aren't "irregular", they are the natural expression for doubly linked lists, trees with references to parents, etc: these usage patterns are the primary cause of memory issues that I come across in C++. In other words, static safety in the face of circular references is what would provide me a major clear advantage for better-than-C++, and unfortunately that doesn't seem to be something that is even seen as an opportunity for Rust given all of the rhetoric about that being an abnormal pattern and index-into-array being safe enough under that world.

littlestymaar 8y ago
> In other words, static safety in the face of circular references is what would provide me a major clear advantage for better-than-C++, and unfortunately that doesn't seem to be something that is even seen as an opportunity for Rust. Having a compiler able to solve the halting problem would also be “a major clear advantage for better-than-C++”, but too bad it's impossible … Arbitrary circular graphs can't be statically managed, that's it. Your need a runtime support, and it will either be a garbage collector, or some kind of constructions with array an indices.
- AstralStorm 8y ago
  Circular graphs are perfectly possible to detect and manage compile time. It just takes a massively not complex borrow checker to run full dependency analysis to find where and if the cycle is broken or the whole thing released. Checking for graph cycle is elementary CS - planning the entry/exit nodes is not. It is similar to link time optimization to implement.
  - staticassertion 8y ago
    > Checking for graph cycle is elementary CS Yeah, but that's for built graphs, not graphs that will be built at runtime? Seems really, really different.