Add a RwLock downgrade method

[connortsui20]

Proposal

This proposal advocates for adding a downgrade function on RwLock, specifically a method on RwLockWriteGuard that transforms it into a RwLockReadGuard.

Problem statement

With the current RwLock API, there is no way to atomically change the lock mode from an exclusive writer lock to a shared reader lock. The best you can do is take a RwLock in write mode, release the lock, and then retake the RwLock in read mode. This solution, however, is highly prone to race conditions, since another writer can get in between releasing the write lock and retaking the lock in read mode.

Motivating examples or use cases

The high-level example for downgrade is solving a lock-unlock-relock pattern.

Suppose you have some value protected by a RwLock. You want many threads observing the value, but once every thread has seen the value, you want to update it quickly. For example, you could have a RwLock<bool>. Let's say that the inner value starts as false, and we want a single thread to set the inner value to true while holding the RwLock in write mode. Once that thread has set it to true, we want lots of other threads to observe that this value is true in read mode. In this isolated situation, we can just drop the write lock and allow readers to execute.

Now suppose that there is another thread, let's call it an eviction thread, that will constantly attempt to write-lock the RwLock and set the inner value to false. Ideally, we want reading threads to observe the true before this eviction thread gets a hold of the write lock. However, there is no way to do this without a downgrade method.

The happy path is:

• T1 takes the write lock
• T1 changes the inner value from false to true
• T1 releases the write lock
• T2 and T3 take the lock in read mode and observe true

The sad path is:

• T1 takes the write lock
• T1 changes the inner value from false to true
• T1 releases the write lock
• T_evict takes the write lock
• T_evict changes the inner value from true to false
• T_evict releases the write lock
• T2 and T3 take the lock in read mode and observe false

Note that since the current RwLock implementation prioritizes writers over readers, it is possible that readers are completely starved of observing a true value.

This might seem like a very strange example, but imagine that instead of false and true, the inner structure is a cache object pointer, where we store either None or Some of a pointer to the cached object. We want lots of threads to observe the object in read mode when it is cached, but at the same time we want to make sure that the cache is not stale and evict old data (this example is boiled down from a buffer pool manager / cache, which is commonly used to manage database pages between storage and memory in a DBMS).

The main problem is when we want to read data that is not already in the cache. We need to access the cache in write/exclusive mode to bring in the data. Only once the data is present can we relax the permissions to read in shared mode. But if there is no downgrade function, how do we do this? While holding the write lock, we must first unlock it and then retake the lock in read mode. It is then possible that in between releasing the write lock and retaking the read lock, an eviction thread comes along and evicts the object before anything can read it. Even the thread that initially brought it into the cache might not be able to read it, and that is definitely a problem.

As a side note, there might be a nice feature that may come as a side effect of including a downgrade method: With the current RwLock futex implementation always preferring writers, there is no method on RwLock that will always make readers wake up before writers if there are any writers waiting (by design). A downgrade method intentionally changes the lock mode from writer to readers, so it is reasonable to assume the caller wants readers to execute before writers. Including a downgrade method could provide "reader-before-writer" functionality that is not available right now.

Solution sketch

The downgrade method would need to exist on RwLockWriteGuard, to prove that we have the lock in write mode. It will take full ownership of the RwLockWriteGuard and return back a RwLockReadGuard.

src/sync/rwlock.rs

impl<'a, T: ?Sized> RwLockWriteGuard<'a, T> {
    //               vvvv Follows `RwLockWriteGuard::map`, but could be named differently...
    pub fn downgrade(orig: Self) -> RwLockReadGuard<'a, T> {
        todo!("Call a `downgrade` function on the inner `sys::RwLock` and construct a `RwLockReadGuard")
    }
}

For the futex implementation of RwLock, downgrade should be as simple as this algorithm:

• Atomically:
  • Set the state to unlocked (remove all the write bits)
  • Increment the number of readers from 0 to 1 (turn on a single read bit)
• Wake up all readers (via the futex call)

I think something like the following should work, but I have not tested it myself:

src/sys/sync/rwlock/futex.rs

impl RwLock {
    /// SAFETY: The lock must be in write mode before calling this method.
    pub unsafe fn downgrade(&self) {
        // Removes all the write bits and adds a single read bit.
        let state =
            self.state.fetch_sub(WRITE_LOCKED - READ_LOCKED, Relaxed) - WRITE_LOCKED + READ_LOCKED;

        debug_assert!(!is_unlocked(state) && !is_write_locked(state));

        if has_readers_waiting(state) {
            self.state.futex_wake_all(&self.state);
        }
    }
}

For the queue implementation, I think that you can just increment the reader counter on the last node without unlocking, but I may be wrong about that. If that is true though, it shouldn't be too hard to wake up other reader threads. The other implementations shouldn't be that hard either.

Alternatives

I cannot think of any good alternatives within the standard library. The easy alternative outside of the standard library is to use a separate crate that has this functionality. parking_lot is a common example.

This is reasonable, but as of now I believe people would slightly prefer to use the standard library locks than rely on 3rd-party crates if they can. It seems like the number of reasons to choose parking_lot over the standard library are also getting smaller, so it is not ideal to have to switch to parking_lot for this one single feature.

Links and related work

• Implement downgrading for RwLock rust#32527
• RwLock: support upgrades and downgrades rust#69240
• Replace RwLock by a futex based one on Linux rust#95801
• Tracking issue for improving std::sync::{Mutex, RwLock, Condvar} rust#93740
• parking_lot's version of downgrade

Something important to note is that this ACP is not proposing an upgrade method to go from read-locked to write-locked. A method like that would likely need to be discussed heavily, as it is not immediately obvious what sort of protocol is should follow (for example, should the upgrade method wait for other writers or go first?).

However, with a downgrade method is pretty straightforward: We already have exclusive access, and we are giving up exclusive access in order to share our access with other threads. We definitely don't want to keep the readers waiting, since the writers are waiting as well and there is already a single reader after downgrade is called.

The main discussion around this in that second link is on the topic of compatibility with pthreads. Since the main implementation now seems to be the futex implementation, I think it is reasonable to add this feature on top of RwLock now.

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.

[Amanieu]

We discussed this in the libs-api meeting today and we're happy to accept this, assuming it is actually implementable for all existing platforms.

Feel free to open a tracking issue and open a PR to rust-lang/rust to add it as an unstable feature.

[connortsui20]

I've been made aware from rust-lang/rust#128219 (comment) that it is possible a lock can be poisoned on acquisition of the write lock through PoisonError::into_inner, which I was not aware of before. This means that the API will instead need to be this:

impl<'a, T: ?Sized> RwLockWriteGuard<'a, T> {
    //                           vvvvvvvvvv
    pub fn downgrade(s: Self) -> LockResult<RwLockReadGuard<'a, T>> {
        todo!("Call a `downgrade` function on the inner `sys::RwLock` and construct a `RwLockReadGuard")
    }
}

EDIT: I think that I don't really understand the problem statement myself entirely. It is also possible that we create the new read guard regardless of if the write guard is poisoned or not.

EDIT: Nevermind, since the mappable guards also carry along the poison, this should as well. Apologies for the ping 🙏