Please review my RwLock :)

code review
1

I am trying to write an RwLock to understand atomics and memory ordering. This obviously a bad implementation and the very first problem that I've noticed is: If I call read and write concurrently from two separate threads, the call to write may execute between the load and store present inside read which is a problem...could you please suggest a solution for this?

also, please point out other aspects I could improve. Thanks!

use std::cell::UnsafeCell;
use std::ops::{Deref, DerefMut};
use std::sync::atomic::AtomicBool;
use std::sync::atomic::Ordering::Relaxed;

pub struct Rw<T> {
    data: UnsafeCell<T>,
    writeable: AtomicBool,
    readable: AtomicBool,
}

unsafe impl<T> Send for Rw<T> where T: Send {}
unsafe impl<T> Sync for Rw<T> where T: Send + Sync {}

impl<T> Rw<T> {
    pub fn new(data: T) -> Self {
        Self {
            data: UnsafeCell::new(data),
            writeable: AtomicBool::new(true),
            readable: AtomicBool::new(true),
        }
    }

    pub fn read<'read>(&'read self) -> RwReadGuard<'read, T> {
        while !self.readable.load(Relaxed) {
            std::hint::spin_loop();
        }

        self.writeable.store(false, Relaxed);

        RwReadGuard { rw: self }
    }

    pub fn write<'write>(&'write self) -> RwWriteGuard<'write, T> {
        while self
            .writeable
            .compare_exchange_weak(true, false, Relaxed, Relaxed)
            .is_err()
        {
            std::hint::spin_loop();
        }

        self.readable.store(false, Relaxed);

        RwWriteGuard { rw: self }
    }
}

pub struct RwReadGuard<'read, T> {
    rw: &'read Rw<T>,
}

impl<T> Deref for RwReadGuard<'_, T> {
    type Target = T;
    fn deref(&self) -> &Self::Target {
        unsafe { &*self.rw.data.get() }
    }
}

impl<T> Drop for RwReadGuard<'_, T> {
    fn drop(&mut self) {
        self.rw.writeable.store(true, Relaxed);
    }
}

pub struct RwWriteGuard<'write, T> {
    rw: &'write Rw<T>,
}

impl<T> Deref for RwWriteGuard<'_, T> {
    type Target = T;
    fn deref(&self) -> &Self::Target {
        unsafe { &*self.rw.data.get() }
    }
}

impl<T> DerefMut for RwWriteGuard<'_, T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        unsafe { &mut *self.rw.data.get() }
    }
}

impl<T> Drop for RwWriteGuard<'_, T> {
    fn drop(&mut self) {
        self.rw.readable.store(true, Relaxed);
        self.rw.writeable.store(true, Relaxed);
    }
}
2

Your observation is correct. My suggestion (without giving you full solution :smiley:) is to use AtomicISize. You can use -1 to represent that an exclusive lock is being held, 0 to represent that no locks are taken and positive number to indicate number of shared locks. Then you could in a loop use load to check if taking requested lock is allowed and compare_exchange to try to atomically set new state.

3 Likes
3

I am not a master, but this is my idea:

  1. lock for read/write which needs a completely atomic op, was splited to two AtomicBool ops, this is fake atomic in fact. You must use a single atomic type to implement it(AtomicU8 at least, for single atomic op).

  2. All you used are Relaxed. Obviously there was nothing about memory ordering. You need to learn to use Acquire and Release in conjunction to achieve data synchronization.

  3. RwLock usually means a single writer or multiply readers, of course here is the same. So you shouldn't simply set 'writeable' true for every RwReadGuard drop, as you have no idea if this is the last reader. You need some way to record how many readers are still alive here.

    Luckly, earlier in 1, we just mentioned AtomicU8(AtomicU32 in std). It can represent up to 256 states, but only few are used. So we can use the remaining state to count alive readers. For example, u8::MAX for write-lock, and the others for read-locks, 0 means both locks are free. All the operations with AtomicU8 are atomic, nothing is bad.

Perfect!

4

Unless you call mem::forget on reader locks in a loop in order to test what happens when std::sync::RwLock has too many readers.

(When std::sync::RwLock has too many readers, the result ranges from "panics with a useful error message" to "I'll just abort the runtime without calling the global panic handler or even printing anything :)" or "how about I abort the runtime without calling the global panic handler, but at least print out an incorrect error message about the RwLock being write-locked (because we forgot to consider that the reader count can overflow)".)

5

Yes, you're right, and I know about it too, but I think it belongs to a higher level of content (as far as this post is concerned), so I didn't mention it here. At the same time, I believe that after truly understanding Rwlock, this point is also easily thought of, as mentioned earlier, 'up to 256 states' limit.

6

It may be easily thought of, but it's also an easy enough mistake to make that std::sync falls victim to it. (In particular, the no-threads RwLock implementation.)