How to implement a SpinLock

Question

I was trying to implement my own custom SpinLock, but the SpinLock seems to misbehave.

I have two files, main.rs and safe.rs.

The test was done in Ubuntu 22.04.3LTS and the system specs are 4GB RAM, 64bit processor, AMD® Pro a4-3350b APU with Radeon r4 graphics.

Here is the error message:

loki@loki:~/main/vs/actic/rust-nomic/spin-lock$ cargo run RUST_BACKTRACE=1
   Compiling spin-lock v0.1.0 (/home/loki/main/vs/actic/rust-nomic/spin-lock)
    Finished dev [unoptimized + debuginfo] target(s) in 0.98s
     Running `target/debug/spin-lock RUST_BACKTRACE=1`
Hello, world!
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `9999995`,
 right: `10000000`', src/main.rs:15:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

safe.rs:

use core::ops::{Deref,DerefMut};
use core::sync::atomic::{AtomicBool,Ordering::{Acquire,Release}};
use core::cell::UnsafeCell;
use core::hint::spin_loop;

#[derive(Debug)]
pub struct SpinLock<T>{
    // Status true -> its locked ||  Status false -> its un_locked(ready to lock)
    status:AtomicBool,
    pub data:UnsafeCell<T>
}

pub struct SpinGuard<'a,T>{
    lock:&'a SpinLock<T>
}
unsafe impl<T> Sync for SpinLock<T> where T:Send{}

impl<T> SpinLock<T>{
    #[inline]
    pub const fn new(data:T)->Self{
        Self { status: AtomicBool::new(false), data: UnsafeCell::new(data) }
    }
    pub fn lock(&self)->SpinGuard<T>{
        while self.status.swap(true,Acquire){
            spin_loop();
        }
        SpinGuard { lock: self }
    }
}


impl<'a,T> SpinGuard<'a,T>{
    pub fn release(self){
        self.lock.status.store(false, Release)
    }
}

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

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

impl<T> Drop for SpinGuard<'_,T>{
    fn drop(&mut self) {
        self.lock.status.store(false, Release)
    }
}

main.rs:

use std::thread;
mod safe;
fn main() {
    println!("Hello, world!");
    let mut  x=safe::SpinLock::new(0);
    thread::scope(|t|{
        for _  in 0..10000000{
            t.spawn(||{
                let mut q=x.lock();
                *q+=1;
                q.release();
            });
        }
    });
    assert_eq!(x.data.get_mut(),&mut 10000000);
    println!("{:?}",x);
}

Answer 1

By adding a couple of sleeps, you can make your error a lot more reproducible:

use std::thread;

fn main() {
    println!("Hello, world!");
    let mut x = safe::SpinLock::new(0);
    thread::scope(|t| {
        for _ in 0..100 {
            t.spawn(|| {
                let mut q = x.lock();
                let q_prev = *q;
                std::thread::sleep(std::time::Duration::from_millis(1));
                *q = q_prev + 1;
                q.release();
            });
        }
    });
    assert_eq!(x.data.get_mut(), &mut 100);
    println!("{:?}", x.data.get_mut());
}

mod safe {
    use core::cell::UnsafeCell;
    use core::hint::spin_loop;
    use core::ops::{Deref, DerefMut};
    use core::sync::atomic::{
        AtomicBool,
        Ordering::{Acquire, Release},
    };

    #[derive(Debug)]
    pub struct SpinLock<T> {
        // Status true -> its locked ||  Status false -> its un_locked(ready to lock)
        status: AtomicBool,
        pub data: UnsafeCell<T>,
    }

    pub struct SpinGuard<'a, T> {
        lock: &'a SpinLock<T>,
    }
    unsafe impl<T> Sync for SpinLock<T> where T: Send {}

    impl<T> SpinLock<T> {
        #[inline]
        pub const fn new(data: T) -> Self {
            Self {
                status: AtomicBool::new(false),
                data: UnsafeCell::new(data),
            }
        }
        pub fn lock(&self) -> SpinGuard<T> {
            while self.status.swap(true, Acquire) {
                spin_loop();
            }
            SpinGuard { lock: self }
        }
    }

    impl<'a, T> SpinGuard<'a, T> {
        pub fn release(self) {
            self.lock.status.store(false, Release);
            std::thread::sleep(std::time::Duration::from_millis(1));
        }
    }

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

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

    impl<T> Drop for SpinGuard<'_, T> {
        fn drop(&mut self) {
            self.lock.status.store(false, Release)
        }
    }
}

Hello, world!
thread 'main' panicked at src\main.rs:17:5:
assertion `left == right` failed
  left: 29
 right: 100

The reason is that you unlock twice. It's a little hidden, but the .release() function actually unlocks once directly, and once in the drop() function.

Simply delete the first unlock in the .release() function, then it works :)

As another nitpick, I would replace the Acquire in swap with an AcqRel. But I'm not 100% sure that it makes a difference.

use std::thread;

fn main() {
    println!("Hello, world!");
    let mut x = safe::SpinLock::new(0);
    thread::scope(|t| {
        for _ in 0..100 {
            t.spawn(|| {
                let mut q = x.lock();
                let q_prev = *q;
                std::thread::sleep(std::time::Duration::from_millis(1));
                *q = q_prev + 1;
                q.release();
            });
        }
    });
    assert_eq!(x.data.get_mut(), &mut 100);
    println!("{:?}", x.data.get_mut());
}

mod safe {
    use core::cell::UnsafeCell;
    use core::hint::spin_loop;
    use core::ops::{Deref, DerefMut};
    use core::sync::atomic::{
        AtomicBool,
        Ordering::{AcqRel, Release},
    };

    #[derive(Debug)]
    pub struct SpinLock<T> {
        // Status true -> its locked ||  Status false -> its un_locked(ready to lock)
        status: AtomicBool,
        pub data: UnsafeCell<T>,
    }

    pub struct SpinGuard<'a, T> {
        lock: &'a SpinLock<T>,
    }
    unsafe impl<T> Sync for SpinLock<T> where T: Send {}

    impl<T> SpinLock<T> {
        #[inline]
        pub const fn new(data: T) -> Self {
            Self {
                status: AtomicBool::new(false),
                data: UnsafeCell::new(data),
            }
        }
        pub fn lock(&self) -> SpinGuard<T> {
            while self.status.swap(true, AcqRel) {
                spin_loop();
            }
            SpinGuard { lock: self }
        }
    }

    impl<'a, T> SpinGuard<'a, T> {
        pub fn release(self) {
            // Nothing to do here, `drop` will perform the unlock
        }
    }

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

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

    impl<T> Drop for SpinGuard<'_, T> {
        fn drop(&mut self) {
            self.lock.status.store(false, Release)
        }
    }
}

Hello, world!
100