Implement downgrading for RwLock

[Yoric]

Some implementations of RwLock implement a downgrading primitive that makes it possible to atomically release a write and enter a read, without letting any other writer grab the lock in the meantime.

This is sometimes very useful, so I'd like some such feature for RwLock.

For instance:

struct RwLockWriteGuard<'a, T> {
  // ...
}

/// Drop the write lock in favor of a read lock, atomically.
///
/// Returns an error if, for some reason, the lock cannot be reacquired, in which case the lock is only dropped.
fn downgrade(self) -> LockResult<RwLockReadGuard<'a, T>> {
  // ...
}

[retep998]

Note that Windows SRW locks do not expose this sort of functionality.

[Yoric]

Nor does Posix, now that I have checked. To do this, one needs a companion Mutex and double-locking, so implementing this without loss of performance might be a tad tricky. So perhaps it should be a new struct, say RwLock2. I'm not sure.

[rphmeier]

http://cursuri.cs.pub.ro/~apc/2003/resources/pthreads/uguide/concep26.htm#293561

"If a thread currently holds an exclusive write lock, an attempt by the thread to acquire a shared read lock will succeed. The thread then holds both an exclusive write lock and a shared read lock"

Assuming the above is true, on posix, a simple implementation like this would work:

impl<'rwlock, T: 'rwlock> RwLockWriteGuard<'rwlock, T> {
    pub fn downgrade(self) -> LockResult<RwLockReadGuard<'rwlock, T>> {
        // maps to pthread_rwlock_rdlock(), which is supposed to succeed unconditionally.
        poison::map_result(self.poison.borrow(), |_| {
            self.__lock.lock.read();
            RwLockReadGuard {
                __lock: self.__lock,
                __data: &*self.__data,
            }
        }

        // write guard dropped here, maps to pthread_rwlock_unlock()
        // which is supposed to release the write lock first.
    }
}

However, as @retep998 points out, this would just lead to deadlock with Windows SRW locks.
We could add a function downgrade to sys_common::RwLock, implemented on Posix as

pub unsafe fn downgrade(&self) {
    self.read();
    self.unlock_write();
}

which will have the desired behavior.
On windows, we could implement it simply in a blocking manner as

pub unsafe fn downgrade(&self) {
    self.unlock_write();
    self.read();
}

Unfortunately, this doesn't hold with the property that no other writer could grab the lock. We could alter the implementation of sys::windows::rwlock::RwLock to use an atomic flag, but this might be overkill:

use sync::atomic::{AtomicBool, Ordering};

pub struct RWLock { 
    inner: UnsafeCell<c::SRWLOCK> ,
    downgrade_flag: AtomicBool,
}

unsafe impl Send for RWLock {}
unsafe impl Sync for RWLock {}

impl RWLock {
    pub const fn new() -> RWLock {
        RWLock { 
            inner: UnsafeCell::new(c::SRWLOCK_INIT) ,
            downgrade_flag: AtomicBool::new(false),
        }
    }

    // ...

    #[inline]
    pub unsafe fn write(&self) {
        // loop until we both acquire the lock and the downgrade flag is not set.
        loop {
            c::AcquireSRWLockExclusive(self.inner.get())
            if !self.downgrade_flag.load(Ordering::SeqCst) {
                return;
            }

            self.write_unlock();
        }
    }
    #[inline]
    pub unsafe fn try_write(&self) -> bool {
        // if we manage to acquire the write lock but the downgrade flag is set, unlock and
        // return. could also do a loop here, though.
        if c::TryAcquireSRWLockExclusive(self.inner.get()) != 0 {
            if !self.downgrade_flag.load(Ordering::SeqCst) {
                return true;
            }
            self.write_unlock();
        }
        false
    }

    #[inline]
    pub unsafe fn downgrade(&self) {
        self.downgrade_flag.store(true, Ordering::SeqCst);
        self.write_unlock();
        self.read();
        self.downgrade_flag.store(false, Ordering::SeqCst);
    }

    // ...
}

This adds the overhead of an atomic operation to every (try)-lock-write operation, but that might be
acceptable. The atomics might be able to be relaxed to Acquire and Release, but I am not sure of this. Maybe some kind of fences are needed in downgrade as well? I also don't know how SRWLock handles writer starvation, so it is possible that the call to self.read() in downgrade would not be guaranteed to succeed, in which case this strategy would probably not work. We could have all pending writers loop until the downgrade flag is not set before attempting to lock again, but that seems likely to waste a lot of cycles.

Then the downgrade implementation would change to

impl<'rwlock, T: 'rwlock> RwLockWriteGuard<'rwlock, T> {
    pub fn downgrade(self) -> LockResult<RwLockReadGuard<'rwlock, T>> {
        poison::map_result(self.poison.borrow(), |_| {
            self.__lock.lock.downgrade();
            RwLockReadGuard {
                __lock: self.__lock,
                __data: &*self.__data,
            }
        }
    }
}

We would have to document the function approprately, maybe something like:

/// Downgrades the write lock to a read lock without allowing any other 
/// writers to grab the lock, only blocking if necessary.
///
/// On Windows systems, the underlying SRWLock does not support
/// non-blocking downgrades.
/// On Unix systems, this should return instantly.
pub fn downgrade(self) -> LockResult<RwLockReadGuard<'rwlock, T>> { ... }

[rphmeier]

SInce those are some pretty substantial changes, this might be something to open an RFC for. I am open to drafting one.

[retep998]

"If a thread currently holds an exclusive write lock, an attempt by the thread to acquire a shared read lock will succeed. The thread then holds both an exclusive write lock and a shared read lock"

If the above is true, then that is a memory safety issue, as having both a write lock and a read lock will give you a &mut T and a &T at the same time which would result in UB. Fortunately a quick test on playpen indicates that isn't the case on linux at least.

[rphmeier]

Well, I guess that's to be expected of a 13 year-old source.

I think an atomic-based yielding solution might be practical enough to work, so I will try an implementation of that and see how it benchmarks.

edit: up at https://github.com/rphmeier/rust/tree/rwlock_downgrade. I will write some benchmarks tomorrow.

[dtolnay]

I agree that a downgrading primitive would be useful! Thanks for the insightful discussion. I would like to see this explored further in an RFC. Some points to make in the RFC:

• What platforms would be able to support downgrade efficiently?
• On platforms that do not support this directly, is there a consistent way that we emulate it?
• Benchmarks on the platforms that need to emulate this.
• Is it better to expose this in a fallible way that is consistent across platforms but never fails on some, or as an infallible extension trait like we do for OsStrExt for example?

[retep998]

If std switched to parking_lot then we'd get downgrading very efficiently on all platforms.