`RwLock` analogy for aliasing models

language design Unsafe Code Guidelines
1

Rust's borrow checker is often described as a compile-time reader-writer lock. Stacked and Tree Borrows admit a similar analogy:

RwLock Safe Rust borrow checker Stacked Borrows Tree Borrows
read & borrow SharedReadOnly borrow New Frozen pointer
drop(ReadGuard) & leaves scope Pop [¬P]SharedReadOnly upon lower write [¬P]Frozen → Disabled upon foreign write
write &mut borrow New Unique pointer - [1]
WriteGuard::downgrade :x: :x: [¬P]Active → [¬P]Frozen upon foreign read
drop(WriteGuard) &mut leaves scope [¬P]Unique → Disabled upon lower read, or pop upon lower write [¬P]Active → Disabled upon foreign write
upgradable_read Two-phase borrow reservation New SharedReadWrite pointer [2] New Reserved pointer
upgrade Two-phase borrow activation - [2:1] Unconflicted Reserved → Active upon child write
downgrade_to_upgradable :x: :x: :x:
UpgradableReadGuard::downgrade - - [2:2] - [3]
drop(UpgradableReadGuard) Reserved two-phase borrow leaves scope - [2:3] Non-interior-mutable [¬P]Active → Disabled upon foreign write

First, I'll admit that my understanding of Stacked Borrows is shaky compared to the other models, and it's also the model where the RwLock analogy works least well. So I may have made mistakes in that column. That said, my main takeaways:

  • The equivalent of WriteGuard::downgrade would be a very nice operation to have in safe Rust. See this recent topic for more discussion.
    • Of course, this requires the underlying aliasing model to support it. Tree Borrows does and Stacked Borrows doesn't, so this is a point in favor of Tree Borrows.
  • In Stacked Borrows, &mut immediately asserts uniqueness (corresponds to write()); in Tree Borrows, this assertion is delayed (corresponds to upgradable_read()). Whichever of the two options is eventually chosen as the "default" behavior of &mut, it might be desirable to make the other behavior also available with a secondary syntax.
  • No model supports the equivalent of WriteGuard::downgrade_to_upgradable. Is this something that can or should be provided? Does it make any sense?
  • Two-phased borrows (equivalent of upgradable_read) are only supported by the safe Rust borrow checker in the limited case of method call receivers. Is it possible or desirable to expose them to safe code more generally?

  1. You can just make a Reserved and write immediately after ↩︎

  2. The RwLock analogy breaks down here. Stacked Borrows SharedReadWrite never transitions to Unique even upon non-interior-mutable writes. ↩︎ ↩︎ ↩︎ ↩︎

  3. In the original Tree Borrows, this cell would correspond to the [P]Reserved → [P]Frozen transition upon a foreign read. However, that part of the model was changed; foreign reads now set the conflicted flag of [P]Reserved, but this only matters until function exit. ↩︎

4 Likes
2

You can do this in Tree Borrows by simply immediately doing a write.

I think the vast majority of &mut-taking functions are probably fine with doing an upgrade immediately, and some could benefit from the associated optimizations. Unfortunately however, we have to support functions like fn as_mut_ptr(&mut self) -> *mut _ (in particular on slices and arrays).

If we had some way to distinguish such "functions that don't actually want to perform any writes, just derive a raw ptr that we can later write to" from regular &mut-taking functions, designing an aliasing model would be a lot simpler. But it's too late for that; we can add such syntax now but we have to support old code written before it exists. I think your proposal here amounts to having exactly such an annotation, opting-in for a mutable reference to be considered "immediately active".

RwLock has no such operation, where can I find out more about it?

(I have no idea what the [¬P] means.)

This analogy doesn't quite work. downgrade is something that the owner of the WriteGuard does. Having the permissions changed from Active to Frozen happens when someone else performs a conflicting access. This makes a huge difference since different parties are taking the initiative here.

What Tree Borrows does is more like, every WriteGuard is implicitly downgradeable (when someone else does a read) and when you try to use it you may find that it has been downgraded. That makes little sense, showing that the entire analogy is a bit of a stretch IMO.

1 Like
3

The table has a link to its documentation you can click. The standard library's RwLock lacks upgradable guards, so you have to go to parking-lot or another third-party library. In TB terms, this would be an Active -> Reserved transition.

"Not protected"

4

I tried clicking. :joy: Nothing happens when I click those links. :person_shrugging: So I figured maybe those aren't links after all. But maybe links-in-tables are just broken in Discourse? (I tried a different browser, same result. Does it work for you?)

2 Likes
5

Fixed, sorry (my Markdown was just broken).

1 Like
6

Is it possible to change it in a future edition? Changing subtle rules around unsafe code in a new edition is not great, but I think it may be acceptable.

What are failure modes of using fn as_mut_ptr(&mut self) -> *mut _ which does immediate upgrade instead of a hypothetical fn as_mut_ptr(*mut self) -> *mut _ syntax? On the first glance it looks like only a matter of missed potential optimizations.

7

An immediately-upgrading fn as_mut_ptr(&mut self) -> *mut _ produces a pointer that will be downgraded (and thus become UB to write to) as soon as a foreign read occurs. Also, any pre-existing pointers will be invalidated, except for ancestors and interior-mutable Reserved.

8

Ah, yes. I thought about it in the context of Vec, which returns a pointer to heap-allocated memory, i.e. &mut self acts only on pointer, length, and capacity, but not (at least directly) on heap-allocated data. But for arrays and slices it indeed can be an issue.

9

Yeah, slices and arrays are the main problem, not Vec. I fixed my comment above.