From c7b599f29d237f59f2654bf6ec0716b85a9bfb45 Mon Sep 17 00:00:00 2001 From: Ralf Jung Date: Wed, 31 May 2023 18:02:14 +0200 Subject: [PATCH 1/1] tree borrows editing --- personal/_drafts/tree-borrows.md | 49 ++++++++++++++++++-------------- 1 file changed, 28 insertions(+), 21 deletions(-) diff --git a/personal/_drafts/tree-borrows.md b/personal/_drafts/tree-borrows.md index d08b88c..ede3c0f 100644 --- a/personal/_drafts/tree-borrows.md +++ b/personal/_drafts/tree-borrows.md @@ -9,15 +9,13 @@ Isn't there this "Stacked Borrows" that Ralf keeps talking about? Indeed there is, but Stacked Borrows is just one proposal for a possible aliasing model -- and it [has its problems](https://github.com/rust-lang/unsafe-code-guidelines/issues?q=is%3Aopen+is%3Aissue+label%3AA-stacked-borrows). The purpose of Tree Borrows is to take the lessons learned from Stacked Borrows to build a new model with fewer issues, and to take some different design decisions such that we get an idea of some of the trade-offs and fine-tuning we might do with these models before deciding on the official model for Rust. -Neven has written a detailed introduction to Tree Borrows [on his blog](https://perso.crans.org/vanille/treebor/), so I won't repeat that here. -Instead I will focus on the differences to Stacked Borrows: if you already know Stacked Borrows and want to understand how Tree Borrows is different, this is for you. -If you don't know Stacked Borrows, just read Neven's blog post. -(And even if you do know Stacked Borrows, it's probably worth the read, since I will not be going into a lot of detail here.) +Neven has written a detailed introduction to Tree Borrows [on his blog](https://perso.crans.org/vanille/treebor/), which you should go read first. +In this post, I will focus on the differences to Stacked Borrows. +I assume you already know Stacked Borrows and want to understand what changes with Tree Borrows and why. As a short-hand, I will sometimes write SB for Stacked Borrows and TB for Tree Borrows. -Now let's go over the major differences. ## Two-phase borrows @@ -40,7 +38,7 @@ fn two_phase(mut x: Vec) { } ``` -This code clearly violates the regular borrow checking rules since `x` is mutably borrowing to `arg0` when we call `x.len()`! +This code clearly violates the regular borrow checking rules since `x` is mutably borrowed to `arg0` when we call `x.len()`! And yet, the compiler will accept this code. The way this works is that the `&mut x` stored in `arg0` is split into two phases: in the *reservation* phase, `x` can still be read via other references. @@ -70,7 +68,7 @@ For example, the following code is illegal under Stacked Borrows: ```rust let mut a = [0, 1]; let from = a.as_ptr(); -let to = a.as_mut_ptr().add(1); +let to = a.as_mut_ptr().add(1); // `from` gets invalidated here std::ptr::copy_nonoverlapping(from, to, 1); ``` @@ -85,7 +83,7 @@ Basically, raw pointers can live longer than the mutable references they are der With TB, the swapped program is still fine, but for a different reason: when `to` gets created first, it remains a reserved two-phase borrow. This means that creating a shared reference and deriving `from` from it (which acts like a read on `self`) is fine; reserved two-phase borrows tolerate reads via unrelated pointers. -Only when `to` is written to does it (or rather the `&mut self` it was created from) become an active mutable reference that requires uniqueness, but that is after `as_ptr` returns so the program is accepted. +Only when `to` is written to does it (or rather the `&mut self` it was created from) become an active mutable reference that requires uniqueness, but that is after `as_ptr` returns so there is no conflicting `&self` reference. It turns out that consistently using two-phase borrows lets us entirely eliminate this hacky SB rule and also fix one of the most common sources of UB under SB. I didn't expect this at all, so this is a happy little accident. :) @@ -104,19 +102,19 @@ Here, the write to `to` activates the two-phase borrow, so uniqueness is enforce That means the `&self` created for `as_ptr` (which is considered reading all of `self`) is incompatible with `to`, and so `to` is invalidated (well, it is made read-only) when `from` gets created. So far, we do not have evidence that this pattern is common in the wild. The way to avoid issues like the code above is to *set up all your raw pointers before you start doing anything*. -Under TB, calling reference-receiving methods like `as_ptr` and `as_mut_ptr` is fine even if these references overlap, but you must call all those methods before the first write to a raw pointer. +Under TB, calling reference-receiving methods like `as_ptr` and `as_mut_ptr` and using the raw pointers they return on disjoint locations is fine even if these references overlap, but you must call all those methods before the first write to a raw pointer. Once the first write happens, creating more references can cause aliasing violations. ## No strict confinement of the accessible memory range The other major source of trouble with Stacked Borrows is [restricting raw pointers to the type and mutability they are initially created with](https://github.com/rust-lang/unsafe-code-guidelines/issues/134). Under SB, when a reference is cast to `*mut T`, the resulting raw pointer is confined to access only the memory covered by `T`. -This regularly trips people when they take a raw pointer to one element of an array (or one field of a struct) and then use pointer arithmetic to access neighboring elements. +This regularly trips people up when they take a raw pointer to one element of an array (or one field of a struct) and then use pointer arithmetic to access neighboring elements. Moreover, when a reference is cast to `*const T`, it is actually read-only, even if the reference was mutable! Many people expect `*const` vs `*mut` not to matter for aliasing, so this is a regular source of confusion. Under TB, we resolve this by no longer doing any retagging for reference-to-raw-pointer casts. -A raw pointer simply uses the same tag as its parent reference it is derived from, thereby inheriting its mutability and the range of addresses it can access. +A raw pointer simply uses the same tag as the parent reference it is derived from, thereby inheriting its mutability and the range of addresses it can access. Moreover, references are not strictly confined to the memory range described by their type: when an `&mut T` (or `&T`) gets created from a parent pointer, we initially record the new reference to be allowed to access the memory range describe by `T` (and we consider this a read access for that memory range). However, we also perform *lazy initialization*: when a memory location outside this initial range is accessed, we check if the parent pointer would have had access to that location, and if so then we also give the child the same access. @@ -135,14 +133,15 @@ ptr.read(); Under SB, `ptr` and direct access to the local `x` used two different tags, so writing to the local invalidated all pointers to it. Under TB, this is no longer the case; a raw pointer directly created to the local is allowed to alias arbitrarily with direct accesses to the local. -This is more intuitive, but it means we can no longer use writes to local variables as a signal that all possible aliases have been invalidated. -We might have to reconsider this decision if it turns out that some program analyses would greatly benefit from making local variables "unique again" after a pointer has been created. + +Arguably the TB behavior is more intuitive, but it means we can no longer use writes to local variables as a signal that all possible aliases have been invalidated. However, note that TB only allows this if there is an `addr_of_mut` (or `addr_of`) immediately in the body of a function! If a reference `&mut x` is created, and then some other function derives a raw pointer from that, those raw pointers *do* get invalidated on the next write to `x`. So to me this is a perfect compromise: code that uses raw pointers has a lower risk of UB, but code that does not use raw pointers (which is easy to see syntactically) can be optimized as much as with SB. -Note that this entire approach in TB relies on TB *not* having the stack-violating hack mentioned in the previous section. -This also means that backporting these improvements to SB is unlikely to be possible. +Note that this entire approach in TB relies on TB *not* needing the stack-violating hack mentioned in the previous section. +If raw pointers in SB just inherited their parent tag, then they would get invalidated together with the unique pointer they are derived from, disallowing all the code that this hack was specifically added to support. +This means that backporting these improvements to SB is unlikely to be possible. ## `UnsafeCell` @@ -161,9 +160,9 @@ And it turns out that under these constraints, we can support `UnsafeCell` with Either there is no `UnsafeCell` anywhere, then this reference is read-only, or else the reference allows aliasing. As someone who thinks a lot about proving theorems about the full Rust semantics including its aliasing model, this approach seemed pleasingly simple. :) -I expected this decision to be somewhat controversial, but the amount of pushback we received had still been surprising. +I expected this decision to be somewhat controversial, but the amount of pushback we received has still been surprising. The good news is that this is far from set in stone: we can [change TB to treat `UnsafeCell` more like SB did](https://github.com/rust-lang/unsafe-code-guidelines/issues/403). -Unlike the previously described differences, this one is really independent from our other design choices. +Unlike the previously described differences, this one is entirely independent of our other design choices. While I prefer the TB approach, the way things currently stand, I do expect that we will end up with SB-like `UnsafeCell` treatment eventually. ## What about optimizations? @@ -177,8 +176,8 @@ Given how common of a problem "overeager uniqueness" is, my current inclination We still have extremely powerful optimization principles around reads, and when the code *does* perform a write that gives rise to even more optimizations, so my feeling is that insisting on speculative writes is just pushing things too far. On another front, TB actually allows a set of crucial optimizations that SB ruled out by accident: reordering of reads! -The issue is that if we start with "read mutable reference, then read shared reference", and then reorder to "read shared reference, then read mutable reference", then in the new program, reading the shared reference might invalidate the mutable reference -- so the reordering might have introduced UB! -This is obviously very important and does not even require a fancy aliasing model, so this is a rather embarrassing problem for SB to have. +The issue with SB is that if we start with "read mutable reference, then read shared reference", and then reorder to "read shared reference, then read mutable reference", then in the new program, reading the shared reference might invalidate the mutable reference -- so the reordering might have introduced UB! +This optimization is possible without having any special aliasing model, so SB not allowing it is a rather embarrassing problem. If it weren't for the stack-violating hack that already came up several times above, I think there would be a fairly easy way of fixing this problem in SB, but alas, that hack is load-bearing and too much existing code is UB if we remove it. Meanwhile, TB does not need any such hack, so we can do the Right Thing (TM): when doing a read, unrelated mutable references are not entirely disabled, they are just made read-only. This means that "read shared reference, then read mutable reference" is equivalent to "read mutable reference, then read shared reference" and the optimization is saved. @@ -202,11 +201,19 @@ I think the best way to find out is to implement `Unique` semantics behind a fla If that works out, we might even be able to remove all special handling of `Box` and rely on the fact that `Box` is defined as a newtype over `Unique`. This would slightly reduce the optimization potential (`Box` is known to point to a memory range at least the size of `T`, whereas `Unique` has no such information), but making `Box` less magic is a long-standing quest so this might be an acceptable trade-off. +I should note that there are many people who think neither `Box` nor `Vec` should have any aliasing requirements. I think it's worth first exploring whether we can have aliasing requirements which are sufficiently light-weight that they are compatible with common coding patterns, but even if we end up saying `Box` and `Vec` behave like raw pointers, it can still be useful to have `Unique` in our toolbox and expose it for unsafe code authors to eke out the last bits of performance. + ## Conclusion These are the major differences between Stacked Borrows and Tree Borrows. As you can see, almost all of them are cases where TB allows more code than SB, and indeed TB fixes what I consider to be SB's two biggest problems: overeager uniqueness for mutable references, and confining references and raw pointers to the size of the type they are created with. -hat TB *doesn't* change is the presence of "protectors" to enforce that certain references remain valid for the duration of an entire function call (whether they are used again or not); protectors are absolutely required to justify the LLVM `noalias` annotations we would like to emit and they also do enable some stronger optimizations than what would otherwise be possible. +These are great news for unsafe code authors! + +What TB *doesn't* change is the presence of "protectors" to enforce that certain references remain valid for the duration of an entire function call (whether they are used again or not); protectors are absolutely required to justify the LLVM `noalias` annotations we would like to emit and they also do enable some stronger optimizations than what would otherwise be possible. I do expect protectors to be the main remaining source of unexpected UB from Tree Borrows, and I don't think there is a lot of wiggle-room that we have here, so this might just be a case where we have to tell programmers to adjust their code, and invest in documentation material to make this subtle issue as widely known as possible. -That's all I got, thanks for reading! +Neven has implemented Tree Borrows in Miri, so you can play around with it and check your own code by setting `MIRIFLAGS=-Zmiri-tree-borrows`. +If you run into any surprises or concerns, please let us know! +The [t-opsem Zulip](https://rust-lang.zulipchat.com/#narrow/stream/136281-t-opsem) and the [UCG issue tracker](https://github.com/rust-lang/unsafe-code-guidelines/) are good places for such questions. + +That's all I got, thanks for reading -- and shout outs to Neven for doing all the actual work here, supervising this project has been a lot of fun! -- 2.30.2