8 ms·
Group Borrowing: Zero-cost memory safety with fewer restrictions
- kibwen 1y ago> In any language, when we hand a function a reference to an object, that function can't destroy the object, nor change its type This isn't quite true. While Rust doesn't currently support this, people have proposed the concept of `&own` references that take ownership of the object and free it when the reference goes out of scope (consider that Rust's standard destructor signature, `fn drop(&mut)`, should probably take one of these hypothetical owning references). I addition, I believe that languages with typestate can cause types to change as a result of function calls, although I don't quite understand the details.
- verdagon 1y agoGreat point =) That's true for a lot of languages (including Mojo too), so I should have said "non-owning reference" there. I'll update the post to clarify. Thanks for catching that!
- skywal_l 1y agoI don't understand your comment. `drop` takes a *mutable* reference. But by default, references in Rust are immutable.
- littlestymaar 1y agoshared references are immutable in Rust, mut references and shared references are both references.
- Ygg2 1y agoKibwen is saying that there was an idea to have `fn drop(&mut x)` from Drop trait become `fn drop_own(&own x)`. Then `&own` would do mutation and drop the owner of the reference. A regular &mut reference shouldn't do that outside of `drop(&mut x)`.
- codedokode 1y agoDrop takes an object itself ("owned reference"), as I remember. Mutable ref allows reading/writing but not destroying or passing the ownership. Owner = can read/write/destroy Mutable ref = can read/write Immutable ref = can only read, guarantered not to change
- steveklabnik 1y agohttps://doc.rust-lang.org/stable/std/ops/trait.Drop.html#tymethod.drop https://doc.rust-lang.org/stable/std/ops/trait.Drop.html#tym...
- codedokode 1y agoThat's the destructor function, that is written by you and called by Rust before actually destroying something. The function that you want to look at is [1]. If you read the docs at your link it even says: > This method is called implicitly when the value goes out of scope, and cannot be called explicitly (this is compiler error E0040). > However, the mem::drop function in the prelude can be used to call the argument’s Drop implementation. By the way the implementation of the function drop is just an empty function [2]; that's enough as local variables are destroyed on function return. Mutable reference is a "borrow" which means you take a value from an owner and promise to return it back, and you cannot destroy a thing that you must return. [1] https://doc.rust-lang.org/std/mem/fn.drop.html https://doc.rust-lang.org/std/mem/fn.drop.html [2] https://doc.rust-lang.org/src/core/mem/mod.rs.html#957 https://doc.rust-lang.org/src/core/mem/mod.rs.html#957
- steveklabnik 1y agoThe drop function being talked about here is the one I pointed to, not the one you pointed to. The Drop trait is built into the language (as a lang item), std::mem::drop is just a regular old function.
- codedokode 1y agoThe drop that you mention doesn't free memory, as I understand, it is called before actually destroying object's memory.
- littlestymaar 1y agoIntriguing, what would be the purpose of such owning references compared to just passing ownership? Is that to have a way to reliably avoid memcopying large objects when passing them by value?
- kibwen 1y ago> Is that to have a way to reliably avoid memcopying large objects when passing them by value? I believe so, yes. Currently the only way to transfer ownership is by-value, and LLVM might optimize away the memcpy, but also it might not.
- codedokode 1y agoI wonder what is the case when you cannot optimize away memcpy, but can work around it with an "owning reference"?
- wavemode 1y agoAn &own reference seems like it would just be equivalent to a Box.
- steveklabnik 1y agoBox heap allocates, references do not.
- wavemode 1y ago> `&own` references that take ownership of the object and free it when the reference goes out of scope How can you free something if it's not allocated
- steveklabnik 1y agoSorry, yeah that phrasing was bad: I kinda think an "owning reference" is a contradiction in terms but I didn't come up with the idea. What I meant was, creating a box creates a new allocation, whereas my understanding of &own would take over an existing allocation.
- modulared 1y ago> I believe that languages with typestate can cause types to change as a result of function calls Do you have any specific languages?
- kibwen 1y agoI've only heard of this concept in academic languages, I don't feel knowledgeable enough to recommend any specific one. In terms of mainstream languages, I think an analogous concept is the use-before-initialization analysis that languages like Rust employ, e.g. if I have a variable defined like this: let x: u8; I can't actually do anything with this variable: foo(x); // error Except I can apply the initialization operator: x = 42; And now I can do things with this variable as usual. But consider that the type of x hasn't changed as a result of the initialization. Beforehand it was a u8, and afterward it was still a u8, and yet something about the state of the variable changed my ability to use it in various contexts. I believe that typestate is something like this, generalized to allow variables to flow through states (like a compile-time state machine) to ensure that things happen in the correct order.
- nixpulvis 1y agoNo mention of how this is safe when operating on data across threads? One of the biggest wins for Rust is sane treatment of references when using parallelism.
- verdagon 1y agoGreat question! That's a big enough topic that I'd love to write a followup post about it. There's also a good thread on r/Compilers at https://www.reddit.com/r/Compilers/comments/1n2ay7g/comment/nb4mj9t/ https://www.reddit.com/r/Compilers/comments/1n2ay7g/comment/... about how Nick's model should support that. TL;DR: Mutability is tracked at the group level, so we can share an immutable group with any number of threads (especially good with structured concurrency) or lend a mutable group to a single other thread. References themselves are still aliasable, regardless of the group's mutability. Taking an existing (mutable, aliasing) group and temporarily interpreting it as immutable has precedent (I did it in Vale [0]) so I like the approach, but I might be biased ;) (This is from my memory of how Nick's proposal works, I'll ask him to give a better answer once morning hits his Australia timezone) [0] https://verdagon.dev/blog/zero-cost-borrowing-regions-part-1-immutable-borrowing https://verdagon.dev/blog/zero-cost-borrowing-regions-part-1...
- nmsmith 1y agoYep, that's an accurate summary! The model still features a form of "borrowing", it just happens at the granularity of groups. I wrote a more detailed answer here: https://news.ycombinator.com/item?id=45057636 https://news.ycombinator.com/item?id=45057636
- verdagon 1y agoHey all, this is a post explaining a new memory safety model by my friend Nick Smith (original proposal at https://gist.github.com/nmsmith/cdaa94aa74e8e0611221e65db8e41f7b https://gist.github.com/nmsmith/cdaa94aa74e8e0611221e65db8e4...) It was interesting enough that I knew I had to write a post about it. Happy to answer any questions!
- titzer 1y agoThanks for the detailed writeup, that must have been a lot of work. I think you guys should check out Verona (https://www.microsoft.com/en-us/research/project/project-verona/ https://www.microsoft.com/en-us/research/project/project-ver...).
- verdagon 1y agoBig fan of Verona, I love their memory safety approach as well. I wrote a bit about it in the Grimoire [0] too. IIRC they plan for the user to specify whether a region is backed by an arena allocator or GC, which sounds pretty nice. It's kind of hard to track down details though, most of my knowledge comes from reading David Chisnall's comments on lobste.rs. [0] https://verdagon.dev/grimoire/grimoire https://verdagon.dev/grimoire/grimoire
- wpollock 1y ago> But... we humans can easily conclude this is safe. After the evaluation of list_ref_a.push(5), my_list is still there, and it's still in a valid state. So there is no risk of memory errors when evaluating the second call to push. Is the always true? What with piplining, branch prediction, and maybe asymmetrical NUMA , isn't out of order instructions possible? If so, don't you still need locks or memory barriers to ensure safety? (I am most definitely not an expert, just curious.)
- nmsmith 1y agoHardware-based instruction reordering always preserves the behaviour of the original program. (Assuming the original program is valid.) For example, an Intel CPU won't reorder `x += 1` and `x *= 2`.
- mrkeen 1y ago> Because of those "inaccessible" rules, we can never have a readwrite reference and a readonly reference to an object at the same time. I can't not see this as a good thing. It's almost at the level of "the only thing an ownership system does". If my thread is operating on a struct of 4 int64s, do I now have to think about another read-only thread seeing that struct in an invalid partially-written state?
- wavemode 1y agoIdeally, the rules for single-threaded references and references that are allowed to be shared across threads would be different.
- zozbot234 1y agoThat's why Cell<T> and RefCell<T> are a thing. Both allow you to mutate shared references, but disable shared access across threads. The qcell crate even includes a version of Cell/RefCell that's "branded" by a region/lifetime, just like in this proposal.
- codedokode 1y agoAs I remember, Cell only allows moving/copying data from/to cell so if you have a 128-byte object inside do you have to copy it to modify? Or this can be optimized?
- kbolino 1y agoYes, that's how Cell works. If you want to work with the data in place, you need a RefCell instead.
- codedokode 1y agoBut it is expensive, because it does run-time checks? Or they are optimized out?
- estebarb 1y agoI'm not sure if I understand it correctly. So, if I have a hashtable, adding or removing an element would invalidate existing pointers to any other element in the hashtable? I guess it makes sense from a memory release POV, but... I end up thinking that for databases using GC or RC is a better approach. Maybe I'm biased, but I have found far easier to work on databases written in C or C#. For that kind of programs I felt Rust overrestrictive and forcing to more dangerous patterns such as replacing pointers with offsets.
- verdagon 1y agoYep, adding or removing an element would invalidate existing pointers to any other element in the hash table. This is generally regarded as a good thing if your elements are stored contiguously in the hash table, because a resize would cause any existing pointers to dangle. This should be true for C, and might be true for C# if you're using `struct`s which put the data inline (memory's a bit fuzzy on C#'s rules for references to structs though, maybe someone can chime in). This new approach still requires us to be mindful of our data layout. Not caring about data layout is still definitely a strength of GC and RC. I'm actually hoping to find a way to blend Nick's approach seamlessly with reference counting (preferably without risking panics or deadlocks) to get the best of both worlds, so that we can consider it for Mojo. I consider that the holy grail of memory safety, and some recent developments give me some hope for that! (Also, I probably shouldn't mention it since it's not ready, but Nick's newest model might have found a way to solve that for separate-chaining hash maps where addresses are stable. We might be able to express that to the type system, which would be pretty cool.)
- estebarb 1y agoThanks for the answer. For instance, usually those containers are used as indexes in DBs, so they contain pointers to data, not the data itself. That is an scenario where the references shouldn't be invalidated. Idk if it may be possible to introduce "semantic monitors". Say, a field within a class and an external container must be updated together. In practice the only time when I have needed to break the single ownership is for keeping internal data views. I know it is safe, but convincing Rust of that is painful.
- sirwhinesalot 1y agoI had a somewhat related idea to this which was simply to track reference stability (i.e., is there any operation beyond freeing the data outright that will invalidate them). A reference into a vector is unstable so you can only have 1 mut xor N read. A reference into an arena is stable so you can have all the muts you want, but they cannot be sent across threads. Reference to object vs reference to contents is also related, you can safely have multiple mut references to the same object that cannot invalidate each other, even if they invalidate references to the contents. This can be tracked with path analysis as employed by Hylo (Hylo only has second class references, but I mean the algorithm they use to track paths is applicable).
- Joker_vD 1y agoThere is also "Tree Borrows" [0] proposal for Rust, which is aimed at the same problem. [0] https://perso.crans.org/vanille/treebor/aux/preprint.pdf https://perso.crans.org/vanille/treebor/aux/preprint.pdf
- SkiFire13 1y agoNo, Tree Borrows is aimed at defining the semantics of memory accesses. It does not provide a way to statically check whether they are correct, which is what the borrow checker and this proposal aim to do.
- leoc 1y agoIn memory-safety discussions it needs to be borne in mind that 'simply fix the hardware' is also a viable approach; or at least it's a lot more viable than it was or seemed to be a few decades ago https://en.wikipedia.org/wiki/Capability_Hardware_Enhanced_RISC_Instructions https://en.wikipedia.org/wiki/Capability_Hardware_Enhanced_R... . Memory-safe BSD and applications running on real memory-safe RISC-V hardware apparently already exist, though obviously, yes, even in a best case existing architectures would not come close to being fully displaced for a long time. That said, I really hope the process isn't being further delayed by attempts to grub license money.
- comex 1y agoTrue. To be fair, CHERI guarantees only security, while borrow checking (when it works) guarantees both security and correctness. If you write to a freed pointer or out-of-bounds, CHERI guarantees that your write either crashes or lands somewhere harmless, rather than corrupting other data. But borrow checking guarantees you won't perform such writes in the first place. Yet while correctness may excite programmers, it's security that gets the decision makers' attention. At the end of the day, security is just much more impactful. We'll see if Morello ever makes its way to the types of CPUs used on phones and higher-performance devices.
- astrange 1y agoARMv9 is not Morello and MTE is not CHERI, but it is much better than nothing and already in a few phones. But it does require software adoption and I don't know how heavily they've adopted it.
- codedokode 1y agoYes but CHERI is supposed to work for every application, not only Rust, but your favourite game from Windows 95 era as well.
- astrange 1y agoSecure hardware needs software cooperation to work - for instance to avoid type confusion you need to tag memory with types, but malloc() doesn't know the type of memory it's allocating.
- comex 1y agoI’m pretty impressed, but also skeptical. There’s a contradiction in this post. Near the beginning of the post is a list of use cases for mutable aliasing. "Back-references", "doubly-linked lists", "delegates" - all cases where you have persistent objects with references to each other, i.e. a cyclic graph of objects. Near the end, the post says: “The mutual isolation restriction will influence our programs' data to look like trees, similar to how Rust's borrow checker does.” In other words, the proposed approach can’t actually support those use cases! The post continues by saying it improves on Rust’s borrow checker by having “much more relaxed rules around how we access those trees from the outside”. That may be true, and I’m legitimately looking forward to playing with this in Mojo. But it’s a much smaller improvement (while still coming at the cost of added complexity). It doesn’t really “get the best of both worlds” as the post says earlier. To be fair, there may be ways to apply similar ideas to get some subset of use cases for cyclic object graphs to work. Some of verdagon’s past blog posts have proposed mechanisms that do something like that. But that would be a whole different thing from what’s being proposed here.
- pklausler 1y agoIt could be made to work in a language like Haskell, where cyclic structures can arise only in limited circumstances (recursive `let` groups) and can be given a distinct runtime representation.
- comex 1y agoWell, if everything is immutable like in Haskell, then you don't really run into the problems described in the blog post in the first place. You can live with Rust's "no mutable aliasing" rule instead.
- pklausler 1y agoObviously; but the point was, if the language were to limit the circumstances in which circular structures can arise, one could exploit that fact.