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

51–60 of 87 posts

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

#51

Post by gf000 »

pklausler wrote: post #42
comex wrote: post #36

Earlier quoted context omitted.

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.

I was thinking that the type system can in certain cases determine that no circular reference is possible for an instance of this type - in that case it could e.g. use an RC (for a region only having that type of objects), and fallback to either an arena-like pattern of freeing everything at once (if only internal circular references exist), or a tracing GC.

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

#52

Post by wavemode »

steveklabnik wrote: post #49
wavemode wrote: post #14

Earlier quoted context omitted.

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

Box heap allocates, references do not.

> `&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

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

#53

Post by astrange »

leoc wrote: post #24

In 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_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 ar…

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

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

#54

Post by astrange »

mrkeen wrote: post #47
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? STM requires locking in the same way that GC requires malloc. It gets it right so that the programmer doesn't mess it up.

A non-compacting GC still needs a good malloc because it needs to avoid heap fragmentation.

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

#55

Post by kbolino »

codedokode wrote: post #45
zozbot234 wrote: post #16

Earlier quoted context omitted.

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?

Yes, that's how Cell works. If you want to work with the data in place, you need a RefCell instead.

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

#56

Post by nmsmith »

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…

Hi there, I am the Nick whose design we're discussing. You raise some valid points: the blog post enumerates some limitations with Rust's model, but my design (as written) only resolves a subset of those limitations. We probably should have made that a bit clearer.

That said, there is still hope! I have been iterating on the design over the last 9 months and am fairly confident that I can model graphs, as long as a few restrictions are imposed, such as not being able to delete nodes. But I can't prove this will work yet, so we will need to wait and see what the next design iteration looks like. I'm fairly confident that the next iteration will be more powerful than the version presented in OP's blog post.

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

#57

Post by nmsmith »

mrkeen wrote: post #7

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

The "Group Borrowing" concept that we're discussing still imposes aliasing restrictions to prevent unsynchronized concurrent access, and also to prevent "unplanned" aliasing. For example, for the duration of a function call, the default restriction is that a mut argument can only be mutated through the argument's identifier. The caller may be holding other aliases, but the callee doesn't need to be concerned about that, because the mut argument's group is "borrowed" for the duration of the function call.

I suppose you could describe the differences from Rust as follows:

- Borrowing happens for the duration of a function call, rather than the lifetime of a reference.

- We borrow entire groups, rather than individual references.

The latter trick is what allows a function to receive mutably aliasing references. Although it receives multiple such references, it only receives one group parameter, and that is what it borrows.

Hope that makes sense!

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

#58

Post by astrange »

comex wrote: post #33
leoc wrote: post #24

In 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_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 ar…

True. 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, i…

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

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

#59

Post by nmsmith »

verdagon wrote: post #8
nixpulvis wrote: post #6

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

Great 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/... 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 g…

Yep, 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

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

#60

Post by wpollock »

verdagon wrote: post #5

Hey all, this is a post explaining a new memory safety model by my friend Nick Smith (original proposal at 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!

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

Post reply on HN