It's currently not possible to implement an efficient and perfectly (theoretically) correct sequence lock in Rust.
-- RFC#3301 AtomicPerByte

If the RFC be implemented, is this implementation of SeqLock sound？

use std::{
    cell::UnsafeCell,
    hint::spin_loop,
    marker::PhantomData,
    sync::atomic::{AtomicUsize, Ordering},
};

// As a implementation  of https://github.com/rust-lang/rfcs/pull/3301
use atomic_memcpy::{atomic_load, atomic_store};

pub struct SeqLockWriter<'a, T>
where
    T: zerocopy::IntoBytes + Sized,
{
    seq: &'a AtomicUsize,
    data: *const UnsafeCell<T>,
    _marker: PhantomData<&'a mut T>,
}

pub struct SeqLockReader<'a, T>
where
    T: zerocopy::FromBytes + Sized,
{
    seq: &'a AtomicUsize,
    data: *const UnsafeCell<T>,
    _marker: PhantomData<&'a T>,
}

unsafe impl<'a, T> Send for SeqLockReader<'a, T> where T: zerocopy::FromBytes + Sized {}
unsafe impl<'a, T> Send for SeqLockWriter<'a, T> where T: zerocopy::IntoBytes + Sized {}

impl<'a, T> SeqLockWriter<'a, T>
where
    T: zerocopy::IntoBytes + Sized,
{
    pub unsafe fn new(seq: &'a AtomicUsize, data: *const T) -> Self {
        seq.store(0, Ordering::Relaxed);
        Self {
            seq,
            data: data as *mut UnsafeCell<T>,
            _marker: PhantomData,
        }
    }

    pub fn write(&mut self, data: T) {
        let seq_begin = self.seq.fetch_add(1, Ordering::Relaxed);
        assert_eq!(seq_begin % 2, 0);
        unsafe { atomic_store(UnsafeCell::raw_get(self.data), data, Ordering::Release) };
        let seq_end = self.seq.fetch_add(1, Ordering::Release);
        assert_eq!(seq_end % 2, 1);
    }
}

impl<'a, T> SeqLockReader<'a, T>
where
    T: zerocopy::FromBytes + Sized,
{
    pub unsafe fn new(seq: &'a AtomicUsize, data: *const T) -> Self {
        seq.store(0, Ordering::Relaxed);
        Self {
            seq,
            data: data as *const UnsafeCell<T>,
            _marker: PhantomData,
        }
    }

    pub fn read(&self) -> T {
        let data = loop {
            let seq_begin = self.seq.load(Ordering::Acquire);
            if !seq_begin.is_multiple_of(2) {
                spin_loop();
                continue;
            }
            let data = unsafe { atomic_load(UnsafeCell::raw_get(self.data), Ordering::Acquire) };
            let seq_end = self.seq.load(Ordering::Relaxed);
            if seq_begin == seq_end {
                break data;
            }
            spin_loop();
        };
        unsafe { data.assume_init() }
    }
}

#[cfg(test)]
mod tests {
    use std::{
        thread::{sleep, spawn},
        time::Duration,
    };

    use super::*;

    #[derive(
        Debug, PartialEq, Eq, zerocopy_derive::FromBytes, zerocopy_derive::IntoBytes, Default,
    )]
    #[repr(C)]
    struct Data {
        a: u32,
        b: u32,
        c: [u8; 16],
        d: u64,
    }

    #[test]
    fn test_seq_lock() {
        let seq = Box::leak(Box::new(AtomicUsize::new(0)));
        let seq = &*seq;
        let data = Box::into_raw(Box::new(Data {
            a: 1,
            b: 2,
            c: [3; 16],
            d: 4,
        })) as *const Data;

        let mut writer = unsafe { SeqLockWriter::new(seq, data) };
        let reader = unsafe { SeqLockReader::new(seq, data) };

        let writer = spawn(move || {
            sleep(Duration::from_secs(1));
            writer.write(Data {
                a: 0xcafe,
                b: 0xbeef,
                c: [0x11; 16],
                d: 0x1234567890abcdef,
            });
        });

        let reader = spawn(move || {
            loop {
                const ORIGINAL: Data = Data {
                    a: 1,
                    b: 2,
                    c: [3; 16],
                    d: 4,
                };
                const EXPECTED: Data = Data {
                    a: 0xcafe,
                    b: 0xbeef,
                    c: [0x11; 16],
                    d: 0x1234567890abcdef,
                };
                let data: Data = reader.read();
                if data == EXPECTED {
                    break;
                }
                assert_eq!(data, ORIGINAL);
                spin_loop();
            }
        });

        writer.join().unwrap();
        reader.join().unwrap();

        unsafe { drop(Box::from_raw(data as *mut Data)) };
        unsafe { drop(Box::from_raw(seq as *const AtomicUsize as *mut AtomicUsize)) };
    }
}

And more questions:

1. can we replace the *const UnsafeCell<T> with reference of UnsafeCell or UnsafePinned?
2. Is it safe to remove the zerocopy::FromBytes or zerocopy::IntoBytes constraint?
3. Is it safe to use this accross process, i.e. allocate seq and data on shared memory and use Reader and Writer in different process?
4. If the data pointer was not properly aligned to T, is the following safe: Playground for data: *const [u8; size_of::<T>()] ?

1 post - 1 participant

Read full topic