Tracking Issue for `rwlock_downgrade`

[connortsui20]

Feature gate: #![feature(rwlock_downgrade)]

This is a tracking issue for a downgrade method for RwLock as discussed in rust-lang/libs-team#392.

The downgrade method on RwLockWriteGuard will transform a write-locked RwLock into a read-locked one.

Public API

impl<'a, T: ?Sized> RwLockWriteGuard<'a, T> {
    pub fn downgrade(s: Self) -> RwLockReadGuard<'a, T> {}
}

Steps / History

• ACP: Add a RwLock downgrade method libs-team#392
• Implementation: Rwlock downgrade #128219
  • downgrade implementation for futex.rs
  • downgrade implementation for no_threads.rs
  • downgrade implementation for queue.rs
  • downgrade implementation for solid.rs
  • downgrade implementation for teeos.rs
• Final comment period (FCP)¹
• Stabilization PR: Stabilize rwlock_downgrade library feature #143191

Unresolved Questions

• It is likely that the reader protocol for the futex implementation will need to change. See below.
• How to go about implementing downgrade for the queue.rs implementation?
• Does the solid_asp3 platform already have a downgrade method on their RwLock implementation?
• Does lock poisoning play into this at all?

Footnotes

1. https://std-dev-guide.rust-lang.org/feature-lifecycle/stabilization.html ↩

[connortsui20]

For the futex.rs implementation, it is likely that the protocol for waiting readers will have to change slightly. You can read it in the code changes, but I'll give a quick summary here.

When a call to downgrade occurs on the inner RwLock, it is arguably incorrect for just the single thread that initially held the write-lock to be the only one who is allowed to hold the read-lock. With no changes to the current implementation, this is what would happen, as we don't let readers (either waiting or very recently entered into the protocol) take the read lock if there are any readers or writers waiting (see the is_read_lockable function).

So a solution that is arguably less wrong would be to allow readers who have just been waken up after a call to futex_wait(&self.state) to take the read lock, regardless of if there are other readers or writers waiting. This means that the futex.rs implementation no longer always prioritizes writers over readers, and I'm not sure if this is acceptable.

It is hard to say if this is a good solution, if anyone would like to give their input that would be much appreciated!

[connortsui20]

@joboet Hi, I saw that you wrote the queue.rs implementation. Do you have an idea on how to go about implementing downgrade for the queue version? I believe it should be something along the lines of finding the tail of the queue and then changing the reader count from 0 to 1, but I am very unfamiliar with the code and I am probably missing something. I also assume that add_backlinks_and_find_tail is probably going to be necessary here?

[joboet]

Sure! There are two cases to consider:

1. no threads are waiting (fast path)
2. threads are waiting

The fast path is pretty easy, you just need to CAS the write-locked state (LOCKED) with the read-locked state for one thread (LOCKED + SINGLE).

For the contended case, I'd first of all change this line:

rust/library/std/src/sys/sync/rwlock/queue.rs

Lines 340 to 344 in 2d5a628

	// If there are threads queued, set the `next` field to a
	// pointer to the next node in the queue. Otherwise set it to
	// the lock count if the state is read-locked or to zero if it
	// is write-locked.
	node.next.0 = AtomicPtr::new(state.mask(MASK).cast());

so that the count is one if the lock is write-locked (try cmp::maxing the address). I'll get back to this later.

If the fast path above fails, you need to try to acquire the queue lock so that you can make modifications to the queue (try a CAS that sets the QUEUE_LOCKED bit, fail if the bit is already set). If this is unsuccessful, then return, as there is no way to wake up new threads. Since the last node contains a lock-count of one (with the change above), the read_unlock call will still work correctly.

If you acquired the QUEUE_LOCKED bit, then you need to wake up new threads. I'd modify unlock_queue so that it takes a downgrade argument, if that is true then skip the LOCKED check, do not remove the last node if it is a writer (this and this line need to be skipped) and use LOCKED + SINGLE as unlock value if the last node is a reader.

[connortsui20]

I think I understand your algorithm, though I was wondering if there might be another way to do it. This algorithm basically is an atomic unlock and place a reader node at the end of the queue, right? Do you think it is possible to implement downgrade without adding a node to the queue at all, and instead just mutating the current state so that we go from 0b0001 to 0b1001 for the fast path and for the waiting path simply incrementing the last queue node from a reader count of 0 to 1?

I'm not sure this is possible, but if it is, it would allow for more opportunities to potentially wake up readers as well.

[connortsui20]

I see the problem now after playing around with the code and trying to implement what I said above. In the queue implementation, if there are any waiters in the queue (writer or readers), we do not allow readers to take the read lock. So my idea of waking up readers after a call to downgrade is not exactly compatible with the current implementation.

However, that doesn't imply that this is completely impossible with the current implementation. I think what might work is forcing the writer who just downgraded to wake up the next readers in the queue AND remove them from the queue. Maybe the former writer thread can set a bit somewhere (probably stored in the Node struct) to let the awakened readers know that they have been awaken by a call to downgrade, and then there can be an extra case in lock_contended to handle readers who just woke up and observed that bit. However, there might be something I am missing that makes this not able to work.

@joboet Do you have any thoughts about this? (Sorry for all of the pings!)

(EDIT: resolved! see PR)