I am trying to implement SeqLock-inspired data structure: non-blocking writer relying on reader to discard data if tampered with.

My understanding is that every SeqLock implementation is by denifition UB in both Rust and C++, as it assumes a possibility of data race. Yet, SeqLock is still used out there—everyone just shrugs it off as long as it works in practice.

I took a look at multiple implementations in both Rust and C++ and it seems like everybody relying on some different magic to keep it altogether. Someone using volatile_read, others using acq_rel fences.

For example, let's look at the implementation in seqlock crate:

#[inline]
    pub fn read(&self) -> T {
        loop {
            // Load the first sequence number. The acquire ordering ensures that
            // this is done before reading the data.
            let seq1 = self.seq.load(Ordering::Acquire);

            // If the sequence number is odd then it means a writer is currently
            // modifying the value.
            if seq1 & 1 != 0 {
                // Yield to give the writer a chance to finish. Writing is
                // expected to be relatively rare anyways so this isn't too
                // performance critical.
                thread::yield_now();
                continue;
            }

            // We need to use a volatile read here because the data may be
            // concurrently modified by a writer. We also use MaybeUninit in
            // case we read the data in the middle of a modification.
            let result = unsafe { ptr::read_volatile(self.data.get() as *mut MaybeUninit<T>) };

            // Make sure the seq2 read occurs after reading the data. What we
            // ideally want is a load(Release), but the Release ordering is not
            // available on loads.
            fence(Ordering::Acquire);

            // If the sequence number is the same then the data wasn't modified
            // while we were reading it, and can be returned.
            let seq2 = self.seq.load(Ordering::Relaxed);
            if seq1 == seq2 {
                return unsafe { result.assume_init() };
            }
        }
    }

Is the read_volatile necessary there? Wouldn't normal read or copy_nonoverlapping work just as well? Sure, in theory all of this is UB, but it seems to me that compiler has no way of "catching me" doing UB here, or not? Here is my reasoning why it should work:

1. Compiler can not reorder ptr::read(self.data.get()... before seq1 load because that load is Acquire and the read is conditional on value of seq1, namely it must be even.
2. Compiler can not reorder ptr::read(self.data.get()... with seq2 load because (according to preshing) "An acquire fence prevents the memory reordering of any read which precedes it in program order with any read or write which follows it in program order."
3. Compiler can potentially load the same data multiple times (which volatile would prevent), in parts, whatever, but that doesn't concern us, as long as all those loads happen between seq1 and seq2.

What am I missing? Is there some other hidden way compiler could exploit this UB and make this not working?

Also, is preshing's explanation correct? I wasn't really able to comprehend the fence documentation in current rustdocs.

Thanks!

2 posts - 2 participants

Read full topic