Memory ordering - establishing relationships

help
1

Hi, I have few questions to verify if my understanding of memory ordering and how the relationships are established is correct.

Is it sound to use Relaxed instead of Released in those scenarios?

struct SimpleLock<T> {
    locked: AtomicBool,
    data: UnsafeCell<T>,
}

impl<T> SimpleLock<T> {
    pub fn new(data: T) -> Self {
        Self {
            locked: AtomicBool::new(false),
            data: UnsafeCell::new(data),
        }
    }

    pub fn lock(&self) -> &mut T {
        while self
            .locked
            .compare_exchange(false, true, Acquire, Relaxed)
            .is_err()
        {
            std::hint::spin_loop();
        }
        unsafe { &mut *self.data.get() }
    }

    // At this point no reference returned from lock() must exist
    pub fn unlock(&self) {
        //@todo can Relaxed be used here?
        self.locked.store(false, Ordering::Relaxed);
    }
}

Acquire is used to make sure that unsafe { &mut *self.data.get() } is not reordered before the call to compare_exchange(..). However, when unlocking I don't see any other operation in the current scope to establish a relationship with, therefore I thought that using Relaxed is enough.
If that's unsound please let me know.

static DATA: AtomicU64 = AtomicU64::new(0);
static READY: AtomicBool = AtomicBool::new(false);

fn main() {
    thread::spawn(|| {
        DATA.store(123, Relaxed);
        READY.store(true, Release);
    });

    //@todo can Relaxed be used here?
    while !READY.load(Relaxed) {
        thread::sleep(Duration::from_millis(100));
        println!("waiting...");
    }
    println!("{}", DATA.load(Relaxed));
}

Similar reasoning as before, READY.store(true, Release) implies that DATA.store(123, Relaxed); has to be always executed before, therefore READY.load(Relaxed) in while !READY.load(Relaxed) can only see [false, false, ..., true]. When true is observed then it is guaranteed that DATA.store(123, Relaxed); must have already happened.

On the other hand, in Crust of Rust video I understand that both Acquire and Release must be used to fix the position of the unsafe get, otherwise with Relaxed it could be possible that the call to get is reordered to either before acquiring or releasing the "lock".

2

For SimpleLock it is not sound. It would be possible to reorder a write of the inner data after the unlock operation unless you use Ordering::Release (or stronger) when unlocking.

And in the second example the DATA load could be re-ordered to before READY reads as true.

While all memory operations on a single thread will observe each others writes sequentially consistent with each other, other threads may observe the loads and stores getting reordered with respect to each other unless you use a strong enough memory order.

1 Like
3

Here your reasoning is wrong. You need a "synchronises with" relation to ensure ordering.

1 Like
4

Thanks. Is my reasoning correct?

Let's assume a client uses SimpleLock

fn main() {
    let lock = SimpleLock::new(0i32);
    thread::scope(|s| {
        for _ in 0..1_000 {
            s.spawn(|| {
                let val = lock.lock();
                *val += 1;
                lock.unlock();
            });
        }
    });
    assert!(*lock.lock() == 1_000);
}

Whan compiler sees

fn main() {
    let lock = SimpleLock::new(0i32);
    thread::scope(|s| {
        for _ in 0..1_000 {
            s.spawn(|| {
                let val = lock.lock();
                *val += 1;
                lock.locked.store(false, Ordering::Relaxed); // this is not sound as might be reordered with line above
            });
        }
    });
    assert!(*lock.lock() == 1_000);
}

Sound version from compiler perspective:

fn main() {
    let lock = SimpleLock::new(0i32);
    thread::scope(|s| {
        for _ in 0..1_000 {
            s.spawn(|| {
                let val = {
                    while lock.locked.compare_exchange(false, true, Acquire, Relaxed).is_err()
                        {
                             std::hint::spin_loop();
                        }
                    unsafe { &mut *self.data.get() } // cannot be moved in front of `while` because of Ordering::Acquire
                 };
                *val += 1; // cannot be moved down because of Ordering::Release
                lock.locked.store(false, Release); 
            });
        }
    });
    assert!(*lock.lock() == 1_000);
}

Whereas for the second example

    while !READY.load(Acquire) {
        thread::sleep(Duration::from_millis(100));
        println!("waiting...");
    }
    println!("{}", DATA.load(Relaxed)); // cannot be moved in front of while due to Ordering::Acquire

My mental model of what's happening is now as follows:
When using Acquire and Release

----------------------
Acquire
op1
op2
op3

op4
op5
op6
Release
----------------------

If both Acquire and Release are used on the same atomic in the same scope, there is a fence and op1-op6 are trapped. For non-atomic and Relaxed atomic operations compiler and CPU are free to reorder them based on regular rules. However, if op3 and op5 are Acquire and Release respectively (on same atomic), then only op1 and op2 do not have fixed execution order.

Based on this reasoning I think in the sound SimpleLock example it would be wrong to think that *val += 1; is trapped because of lock.locked Acquire and Release fence, but it is rather a combination of one-side bound and scope.