←back to thread

Tree Borrows

(plf.inf.ethz.ch)
572 points zdw | 2 comments | | HN request time: 0.425s | source
Show context
jcalvinowens ◴[] No.44513250[source]
> On the one hand, compilers would like to exploit the strong guarantees of the type system—particularly those pertaining to aliasing of pointers—in order to unlock powerful intraprocedural optimizations.

How true is this really?

Torvalds has argued for a long time that strict aliasing rules in C are more trouble than they're worth, I find his arguments compelling. Here's one of many examples: https://lore.kernel.org/all/CAHk-=wgq1DvgNVoodk7JKc6BuU1m9Un... (the entire thread worth reading if you find this sort of thing interesting)

Is Rust somehow fundamentally different? Based on limited experience, it seems not (at least, when unsafe is involved...).

replies(11): >>44513333 #>>44513357 #>>44513452 #>>44513468 #>>44513936 #>>44514234 #>>44514867 #>>44514904 #>>44516742 #>>44516860 #>>44517860 #
ralfj ◴[] No.44513333[source]
I would agree that C's strict aliasing rules are terrible. The rules we are proposing for Rust are very different. They are both more useful for compilers and, in my opinion, less onerous for programmers. We also have an actual in-language opt-out: use raw pointers. And finally, we have a tool you can use to check your code.

But in the end, it's a trade-off, like everything in language design. (In life, really. ;) We think that in Rust we may have found a new sweet spot for this kind of optimizations. Time will tell whether we are right.

replies(3): >>44513873 #>>44514788 #>>44521382 #
NobodyNada ◴[] No.44514788[source]
As someone who has been writing a lot of unsafe Rust (mostly in an embedded context), I'm thrilled about and thankful for the work that you, your students, and the opsem team are doing.

When you're working with anything below the application level, C's confusing and underspecified rules about UB are almost impossible to keep track of, especially when it comes to aliasing and volatile/MMIO. The spec is so difficult to read and full of complicated cross-references that to actually get a practical answer you have to look for a random Stack Overflow post that may or may not have a correct interpretation of the spec, and may or may not address your specific problem.

Rust right now feels a lot harder to work with, because the spec isn't done. When you have a concrete question about a piece of code, like "is this conversion from an &mut to a *mut and back sound", and you try to look for documentation on it, you get either "Nobody knows, Rust aliasing model isn't defined"; a hand-wavy explanation that is not rigorous or specific; or a model like Stack Borrows or Tree Borrows that's defined a little too formally for easy digestion :)

But when I really started digging, I realized just how much cleaner Rust's semantics are. References aren't actually hard, Tree Borrows basically boils down to "while an &mut reference is live, you can only access the value through pointers or references derived from that reference". Pointer operations have straightforward semantics, there's no confusing notions of typed memory, and no UB "just because" for random things like integer overflow. It's just so much less complicated to understand than C's abstract machine.

I'm really looking forward to things like MiniRust, and to an aliasing model making it into the Reference / other documentation, because at that point I feel like unsafe Rust will be way easier to write confidently and correctly than C.

Congrats on the publication, and thanks again for the work you all have put into this.

replies(3): >>44517236 #>>44517279 #>>44518115 #
gronpi ◴[] No.44517236[source]
In C, you can alias pointers if they have compatible types. Not the case in Rust for mutable references. And the rules of Rust have tripped up even senior Rust developers.

https://github.com/rust-lang/rust/commit/71f5cfb21f3fd2f1740...

Without MIRI, a lot of Rust developers would be lost, as they do not even attempt to understand unsafe. And MIRI cannot and does not cover everything, no matter how good and beloved it is.

It should have been possible for senior Rust developers to write UB-free code without having to hope that MIRI saves them.

replies(3): >>44517796 #>>44518119 #>>44518365 #
ralfj ◴[] No.44518119[source]
C has an opt-out that works sometimes, if a compatible type exists. Rust has an opt-out that works always: use raw pointers (or interior mutable shared references) for all accesses, and you can stop worrying about aliasing altogether.
replies(2): >>44518264 #>>44518705 #
1. hamcocar ◴[] No.44518264[source]
I think that way of describing it is really weird.

In C, you do not use any special keywords to opt into or opt out of TBAA, instead it is the rule by default that one must follow. I do not consider that 'opting out'. One can disable that in some compilers by disabling 'strict aliasing', as the Linux kernel does, but that is usually on a whole-program basis and not standard.

In Rust, using raw pointers is using a different mechanism, and mutable references are always 'no aliasing'.

An example of opting in would be C's "restrict" keyword, where one opts into a similar constraint to that of Rust's 'no aliasing' for mutable references.

>use raw pointers (or interior mutable shared references) for all accesses, and you can stop worrying about aliasing altogether.

And dereferencing a raw pointer requires 'unsafe', right? And if one messee the rules up for it, theN UB.

Can you confirm that the interaction between raw pointers and mutable references still requires care? Is this comment accurate?

>It is safe to hold a raw pointer, const T or mut T, at the same time as a mutable reference, &mut T, to the same data. However, it is Undefined Behaviour if you deference that raw pointer while the mutable reference is still live.

replies(1): >>44518327 #
2. ralfj ◴[] No.44518327[source]
> Can you confirm that the interaction between raw pointers and mutable references still requires care?

Yes, that still requires care.

> In C, you do not use any special keywords to opt into or opt out of TBAA, instead it is the rule by default that one must follow

That's exactly the problem: sometimes you need to write code where there's more aliasing, and C just makes that impossible. It tells you to use memcpy instead, causing extra copies which cost performance.

In Rust, you can still write the code without the extra copies. Yes, it requires unsafe, but it's at least possible. (Remember that writing C is like having all code be unsafe, so in a comparison with C, if 10% of the Rust code needs to be unsafe that's still 90% less unsafe than C.)