Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Group Borrowing: Zero-cost memory safety with fewer restrictions

verdagon.dev

Post reply on HN
Print view View original

41–50 of 87 posts

Re: Group Borrowing: Zero-cost memory safety with fewer restrictions

#41

Post by thomasmg »

comex wrote: post #38
thomasmg wrote: post #35

Earlier quoted context omitted.

I think you are right. The post talks about mutable vs immutable borrows, and how to have multiple mutable borrows, safely. But doubly-linked list are hard in Rust due to ownership, and not borrowing. (Doubly linked lists could be supported by "splitting" and "merging" ownership: having "half"-owners, and then you can merge ownership.) I understand the reason for having 1 mutable xor n immutable references... but I t…

But how would you prevent use-after-free? In other words, how do you prevent a child object's method from reaching out to its parent object and, say, clearing the container that contains the child object? Specifically, how do you do that without reference counting or garbage collection.

Well the distinction between mutable and immutable borrows doesn't solve use-after-free. What prevents use-after-free is ownership. There is one owner, and the owner can not free the memory as long as there is a borrower (it doesn't matter whether the borrower is mutable or not). So that's the task of the borrow checker.

For my own programming language [1], I have only mutable borrowers (similar to Java), and a much simpler borrow checker: a method that holds a borrow can not call a method that potentially frees an object of the same type (directly or indirectly). I'm not sure yet if this is sufficient; it's still a borrow checker, just a very simple one. (My language uses reference counting by default, but does support single ownership + borrowing.)

[1] https://github.com/thomasmueller/bau-lang

Re: Group Borrowing: Zero-cost memory safety with fewer restrictions

#42

Post by pklausler »

comex wrote: post #36
pklausler wrote: post #32

Earlier quoted context omitted.

It 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.

Well, 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.

Obviously; but the point was, if the language were to limit the circumstances in which circular structures can arise, one could exploit that fact.

Re: Group Borrowing: Zero-cost memory safety with fewer restrictions

#43

Post by codedokode »

comex wrote: post #31

I’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 l…

For back links, can we have a special pointer type (back link to owner) that automatically gets updated when the object is moved/copied? Also auto-initialized when object is created.

Re: Group Borrowing: Zero-cost memory safety with fewer restrictions

#44

Post by codedokode »

titzer wrote: post #37
codedokode wrote: post #34

Earlier quoted context omitted.

> Time is a slippery notion in concurrency. Most language-level memory models (e.g. Java) or even hardware-level concurrency models focus on happens-before relations, which are induced by executing certain operations You are correct, but for simplicity we can assume that the CPU executes one operation at a time and still have a valid model for reasoning about data races. > But ultimately, all inter-thread communicati…

> Also it seems that it requires locking? That's not very good given that locks often need syscalls. AFAIU in most STMs all the fast paths are implemented using lock-free algorithms with just barriers.

How do you implement "commit" part safely (writing changes to the object) without locking the object?

Re: Group Borrowing: Zero-cost memory safety with fewer restrictions

#45

Post by codedokode »

zozbot234 wrote: post #16
wavemode wrote: post #13

Earlier quoted context omitted.

Ideally, the rules for single-threaded references and references that are allowed to be shared across threads would be different.

That's why Cell and RefCell 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.

As 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?

Re: Group Borrowing: Zero-cost memory safety with fewer restrictions

#46

Post by codedokode »

skywal_l wrote: post #4
kibwen wrote: post #2

> 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 ta…

I don't understand your comment. `drop` takes a *mutable* reference. But by default, references in Rust are immutable.

Drop 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

Re: Group Borrowing: Zero-cost memory safety with fewer restrictions

#47

Post by mrkeen »

codedokode wrote: post #34
titzer wrote: post #29

Earlier quoted context omitted.

> And by the way if you know more methods or ideas please share them! Use a transaction manager (HTM or STM). The STM is going to boil down to lockfree synchronization, logging, and retry. Transactions can fail and retry. But ultimately, all inter-thread communication boils down to programs (or libraries) using barriers for acquire/release semantics and/or using compare/swap and atomic read-modify-write. > at any poi…

> Time is a slippery notion in concurrency. Most language-level memory models (e.g. Java) or even hardware-level concurrency models focus on happens-before relations, which are induced by executing certain operations You are correct, but for simplicity we can assume that the CPU executes one operation at a time and still have a valid model for reasoning about data races. > But ultimately, all inter-thread communicati…

> Also it seems that it requires locking?

STM requires locking in the same way that GC requires malloc. It gets it right so that the programmer doesn't mess it up.

Re: Group Borrowing: Zero-cost memory safety with fewer restrictions

#48

Post by steveklabnik »

codedokode wrote: post #46
skywal_l wrote: post #4

Earlier quoted context omitted.

I don't understand your comment. `drop` takes a *mutable* reference. But by default, references in Rust are immutable.

Drop 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

https://doc.rust-lang.org/stable/std/ops/trait.Drop.html#tym...

Re: Group Borrowing: Zero-cost memory safety with fewer restrictions

#49

Post by steveklabnik »

wavemode wrote: post #14
kibwen wrote: post #2

> 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 ta…

An &own reference seems like it would just be equivalent to a Box.

Box heap allocates, references do not.

Re: Group Borrowing: Zero-cost memory safety with fewer restrictions

#50

Post by gf000 »

thomasmg wrote: post #41
comex wrote: post #38

Earlier quoted context omitted.

But how would you prevent use-after-free? In other words, how do you prevent a child object's method from reaching out to its parent object and, say, clearing the container that contains the child object? Specifically, how do you do that without reference counting or garbage collection.

Well the distinction between mutable and immutable borrows doesn't solve use-after-free. What prevents use-after-free is ownership. There is one owner, and the owner can not free the memory as long as there is a borrower (it doesn't matter whether the borrower is mutable or not). So that's the task of the borrow checker. For my own programming language [1], I have only mutable borrowers (similar to Java), and a much…

I'm looking forward to your experience with this approach!

Bit off topic, but is there any particular reason you went with a go-like `ident type` syntax over the more common ones like the C or the ML one?

Post reply on HN