Open connortsui20 opened 3 months ago
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!
@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?
Sure! There are two cases to consider:
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: https://github.com/rust-lang/rust/blob/2d5a628a1de1d38318909a710ef37da6251e362e/library/std/src/sys/sync/rwlock/queue.rs#L340-L344
so that the count is one if the lock is write-locked (try cmp::max
ing 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.
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.
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)
Feature gate:
#![feature(rwlock_downgrade)]
This is a tracking issue for a
downgrade
method forRwLock
as discussed in https://github.com/rust-lang/libs-team/issues/392.The
downgrade
method onRwLockWriteGuard
will transform a write-lockedRwLock
into a read-locked one.Public API
Steps / History
downgrade
implementation forfutex.rs
downgrade
implementation forno_threads.rs
downgrade
implementation forqueue.rs
downgrade
implementation forsolid.rs
downgrade
implementation forteeos.rs
Unresolved Questions
downgrade
for thequeue.rs
implementation?Does thesolid_asp3
platform already have adowngrade
method on theirRwLock
implementation?Does lock poisoning play into this at all?