Add Rwlock try_upgrade method

[devmitch]

Proposal

This proposal suggests to add a try_upgrade method on RwLockReadGuard that transforms it into a RwLockWriteGuard if it is immediately possible (ie if there are no read guards except for this one at this time)

Problem statement

There is currently no way to atomically change a RwLockReadGuard into a RwLockWriteGuard. A blocking upgrade method is problematic, since if there are two threads blocking on the upgrade at the same time, only one of them can succeed and the other will fail and must drop their read lock. There are a few ways to handle a blocking API.

However, it is much easier and more straightfoward to implement the non-blocking try_upgrade. If the read guard is the only one in existence (write guards cannot exist due to the existence of the read guard), we can immediately and atomically convert the read guard into a write guard. Otherwise, if there are other readers, the method will immediately fail, and the thread can continue with the read guard.

Motivating examples or use cases

Some B-Tree data structures use algorithms that optimistically acquire write locks on nodes (by upgrading read locks) if it is currently possible, and rebalance the tree, such as the Foster B-Tree. Currently this is not possible with the Rust standard library locks.

Solution sketch

// src/sync/rwlock.rs
impl<'a, T: ?Sized> RwLockReadGuard<'a, T> {
    // note: this function takes ownership of the read guard
    pub fn try_upgrade(orig: Self) -> Result<RwLockWriteGuard<'a, T>, RwLockReadGuard<'a, T>> {
        // call non-blocking `try_upgrade` on inner sys::RwLock
        // if successful, construct the resulting RwLockWriteGuard and return wrapped in Ok()
        // otherwise, re-construct the RwLockReadGuard that this function was called on, and return it in Err()      
    }
}

// src/sys/sync/rwlock/futex.rs
impl RwLock {
    pub fn try_upgrade(&self) -> bool {
        // I assume we use strong CAS since this function is not in a loop (though the guard caller could be...?)
        self.state.compare_exchange(READ_LOCKED, WRITE_LOCKED, Acquire, Relaxed).is_ok()
    }

Alternatives

I couldn't find any crates that implement this design.

Dropping the read guard and re-acquiring a write guard can lead to threads sneaking in after the read guard drop and before the write guard acquire, changing the protected data, and possibly invalidating any conclusions made about the protected data before the read guard was dropped.

Links and related work

RwLock downgrade was recently implemented:

• Add a RwLock downgrade method #392

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[tgross35]

This would mirror the unstable rwlock_downgrade API

[devmitch]

@tgross35 Sorry, clicked submit too quickly, have updated my proposal

[conradludgate]

I couldn't find any crates that implement this design.

Parking lot does have some upgrade support, but it's somewhat limited in that to use upgrade, the read lock guard still has some higher priority. What I mean here is that you cannot have 2 UpgradeableRead guards active at a time, but you can have 1 upgradeable guard + N non-upgradable guards active at the same time.

https://docs.rs/parking_lot/latest/parking_lot/type.RwLock.html#method.upgradable_read

[devmitch]

What I mean here is that you cannot have 2 UpgradeableRead guards active at a time

Indeed this is the bottleneck that prevents their use when using them on concurrent B-Trees. Any thread that wishes to potentially upgrade a node to a write lock will need to take an upgrade lock on the node, and the higher up this node is in the tree, the more it limits concurrent access to the nodes below, as only one can exist at a time.

The downside to the parking_lot approach is that having the option to upgrade limits concurrency, whether or not the upgrade is exercised. The downside to the approach in this proposal is that it is fallible with "try", similar to the existing try_write.

Also, if this was to be accepted, it should be made clear in the docs that threads shouldn't loop on try_upgrade forever without releasing the read locks, as 2 or more of these threads will deadlock.

[cuviper]

Can we support this on all targets?

Should this fail if another writer is already waiting?

[devmitch]

Can we support this on all targets?

Briefly looking through the other target versions, for teeos it should always succeed in upgrading, similar to the recent downgrade method:

// Since there is no difference between read-locked and write-locked on this platform, this
// function is simply a no-op as only 1 reader can read: the original writer.

I can't find anything regarding how SOLID works, maybe someone else who knows more about this platform can help? Otherwise, like other functions in the standard library not supported on SOLID, it can panic.

It should be supported in queue.rs with a CAS.

Should this fail if another writer is already waiting?

For the sake of simplicity I think the answer should be no. Therefore, priority will be implicitly given to upgraded reads over waiting writers.

[joshtriplett]

We discussed this in today's @rust-lang/libs-api meeting.

Approved, ship it.

Please make sure the documentation is very clear that this is opportunistic and code must not loop on it (because that will cause deadlocks).

[the8472]

I also suggest adding a cfg(miri) to the impl that spuriously fails the try so that people don't rely on it too much since it may fail on some platforms.

[ShrigmaDev]

Closing my tracking issue and PR since I don't know what I'm doing. Not sure how to deal with the ?Sized type bounds and creating a new UnsafeCell for the upgrade.

Someone else should implement this @.@

[tgross35]

This should still be possible. I think we can leave the tracking issue and just add the relevant help wanted labels so somebody else can pick it up, I'll reopen it.

[connortsui20]

I can pick this up!

To clarify semantics: try_upgrade succeeds if and only if the thread that calls it already has the shared read lock and also if there are no other readers currently reading the lock (reader count is equal to 1). Is this correct?

In this situation, we also don't care if there are writers waiting (because the writers wouldn't get a chance to write anyways if the current thread still has the read lock). This works out pretty nicely since in the futex impementation (and also the queue impl by default), readers will wait if there are any waiting writers, which means a try_upgrade has no overhead in the existing implementations.

EDIT: Also, for the sake of semantics and documentation, I think the situation in which two threads are running try_upgrade in a loop until they get the write latch is actually a livelock? try_upgrade is not blocking so both threads would loop infinitely instead of block infinitely. Makes more sense to call this a deadlock because no resource state is changing.

[connortsui20]

I'll put this here for visibility: rust-lang/rust#138559 (comment)

This seems to be a blocker for this feature, which means either the proposed API needs to change or the feature shouldn't be implemented.

CC @devmitch since you opened this ACP, not sure what the protocol is here with the @rust-lang/libs-api team.

[devmitch]

@connortsui20 Happy for you to take over this. Unsure on the correct API solution here, if it requires a different type, then so long as this type behaves in the same way as a typical read guard then I think its acceptable. If there are no other options then I suppose a new proposal can be created.

[connortsui20]

@connortsui20 Happy for you to take over this. Unsure on the correct API solution here, if it requires a different type, then so long as this type behaves in the same way as a typical read guard then I think its acceptable. If there are no other options then I suppose a new proposal can be created.

It's more that I think a new API and guard is essentially required here to keep soundness, which means I think it has to go back through the libs team?

The syntax would also have to be figured out, which is why I would be hesitant to even add this now. Do we need a method on RwLock like read_upgradeable that returns a new type of guard like RwLockUpgradeableReadGuard? Once you have that, then I think that brings back the question of if we want to support a blocking upgrade because now that would actually make sense.

Basically I think some more discussion (or even a new ACP) might be necessary before moving forwards.

[tgross35]

Ir is worth noting that we do have a second chance to design lock API since the version without poison exists unstably. We probably don’t want to deviate too much from the poison versions, but it is something to think about.

[connortsui20]

Here is a slightly modified proposal that should deal with the variance problem raised in rust-lang/rust#138559 (comment).

Basically, we can introduce a read_upgradable method on RwLock that returns an RwLockUpgradeableReadGuard. This guard would be identical to RwLockReadGuard, except that it is invariant over T (which allows it to be upgradeable into what is essentially a mutable reference).

// Ignoring the poison and nonpoison changes for clarity.

impl<T: ?Sized> RwLock<T> {
    pub fn read_upgradeable(&self) -> LockResult<RwLockUpgradeableReadGuard<'_, T>> {}
}

/// Essentially identical to `RwLockReadGuard`, the only difference would be making this invariant over `T`.
pub struct RwLockUpgradeableReadGuard<'a, T: ?Sized + 'a> {
    // <-- unknown, probably similar to `RwLockReadGuard` -->
}

/// This should have all of the same methods as `RwLockReadGuard`.
impl<'a, T: ?Sized> RwLockUpgradeableReadGuard<'a, T> {
    pub fn try_upgrade(orig: Self) -> Result<RwLockWriteGuard<'a, T>, RwLockUpgradeableReadGuard<'a, T>> {}
}

I believe having a dedicated upgradeable guard also opens the door for a potential blocking upgrade in the future, though that is out of scope for this issue.

---

I'm not entirely sure what the exact fields of this new struct should be, but it should probably be similar. Maybe even something as simple as this:

pub struct RwLockUpgradeableReadGuard<'a, T: ?Sized + 'a> {
    guard: RwLockReadGuard,
    _variance: PhantomData<&'a mut T>,
}

^ This would make the methods of the guard pretty easy to implement.

---

I would guess that we would want to follow parking_lot and only allow a single RwLockUpgradeableReadGuard to exist at any given time. The benefit of doing this is preventing any possible deadlocks that might occur. Of course, the downside is that you need to know in advance the exact read lock that you will potentially upgrade.

With the B-tree example from the original post, there is already a situation where you might want multiple upgradeable guards. The case would be when two insertion operations happen at the same time to two sibling leaf pages that share a parent. The insertion algorithm would want both operations to take an upgradeable read latch on the parent (in case it needs to rebalance). This is easy to get around (if you can't get an upgradeable read latch, then fail immediately on the rebalance case), but it is still a case where you would want multiple.

[devmitch]

I would guess that we would want to follow parking_lot and only allow a single RwLockUpgradeableReadGuard to exist at any given time.

This restriction only exists because the upgrade on parking_lot upgradeable read guards is blocking right? Since it gets around the issue when two blocking upgrades happen at the same time and one of them must fail. I don't think its necessary for the non-blocking try_upgrade function, since it will fail anyway if there is more than one reader.

[connortsui20]

I would guess that we would want to follow parking_lot and only allow a single RwLockUpgradeableReadGuard to exist at any given time.

This restriction only exists because the upgrade on parking_lot upgradeable read guards is blocking right? Since it gets around the issue when two blocking upgrades happen at the same time and one of them must fail. I don't think its necessary for the non-blocking try_upgrade function, since it will fail anyway if there is more than one reader.

The reason I bring this up is because adding a blocking upgrade could be a future addition and would require yet another breaking change. If this is something that people do not want though, then this becomes a much easier problem.

[programmerjake]

maybe there should be a RwLockTryUpgradeableReadLock which allows multiple locks simultaneously and RwLockUpgradeableReadLock which allows only one lock at a time.

[connortsui20]

maybe there should be a RwLockTryUpgradeableReadLock which allows multiple locks simultaneously and RwLockUpgradeableReadLock which allows only one lock at a time.

I think I like this, the only worry I have it this becomes verbose and complicated to understand (even more than it already is for people new to Rust). If we're confident that the documentation for this can be easy to follow, then I think this is a great idea, and I don't see any other downsides!

[joshtriplett]

We talked about this again in today's @rust-lang/libs-api meeting.

With the added complexity of needing a separate type for variance reasons, and needing to have the try_upgrade version only to avoid deadlock, we found ourselves wondering how often this would be usable and performant.

@devmitch, would you be up for demonstrating the performance benefit of this, e.g. by using a modified parking_lot that allows multiple upgradable locks at once but only allows try_upgrade? (Or, if you prefer, by drafting a std PR following that approach and demonstrating the performance of a crate using that?)

In particular, could you show that the performance is actually substantially better than dropping the read lock and then acquiring a write lock?

(Prior art for other rwlocks that support upgrading would also be helpful.)

[programmerjake]

In particular, could you show that the performance is actually substantially better than dropping the read lock and then acquiring a write lock?

that's not a replacement for upgrading a read lock regardless of performance because by dropping the read lock you allow intervening modifications that an upgrade doesn't.

[connortsui20]

@devmitch, would you be up for demonstrating the performance benefit of this, e.g. by using a modified parking_lot that allows multiple upgradable locks at once but only allows try_upgrade? (Or, if you prefer, by drafting a std PR following that approach and demonstrating the performance of a crate using that?)

To be honest, I'm not sure that coming up with a performance benchmark is a good justifier for determining if this feature should be added to the standard library. In addition to @programmerjake's comment that this does not correctly solve the problem of atomically switching to a write lock, a performance benefit is highly dependent on the algorithm that makes use of the try_upgrade.

In the original post, @devmitch used the example of a B+ tree optimistic upgrade. As a TLDR, upgrades potentially allow access methods of the B+ tree to skip re-traversing the entire tree. This is obviously a "good" thing, but how much better this optimization is can be dependent on many different things.

For example, this optimization is far better for on-disk B+ tree database indexes (arguably the most common use case for B+ trees in production) than in-memory ones because you could be skipping a substantial number of IOs.

Additionally, the speedup is completely dependent on access patterns: how do incoming reads and writes mutate the tree, how do they rebalance the tree, while all in parallel, etc.

So I could come up with a scenario where upgrading could reduce the runtime by 99%, and yet that number is not super meaningful in isolation.

So really I think the discussion should be whether the standard library RwLock should try to encompass all possible operations (including try_upgrade and maybe even an upgrade) or if users should be forced to use a third-party crate to get that behavior if they want it. I feel that functionality should be the deciding factor (over potential performance).

---

Also, here is another relevant paper that shows optimistic upgrades in action more clearly (see pseudocode at the very end): https://db.in.tum.de/~leis/papers/artsync.pdf

[Amanieu]

We discussed this in the @rust-lang/libs-api meeting today. We agreed that there is a good use case for having this, however since the API surface is larger than expected (due to the need for a separate lock guard) we would like this to be prototyped in a separate crate first (such as parking_lot).