Futex design and backoff

I am writing something without libc and I need a mutex for synchronization (I used #![cfg_attr(not(test), no_std)]). Here is my code:

const FREE: u8 = 0;
const LOCKED: u8 = 1;
const FUTEX_MODE: u8 = 2;
const BACKOFF_LIMIT: usize = 6;

#[inline(always)]
pub fn futex_wait(target: &AtomicU8, target_value: u8) {
    unsafe {
        match syscall!(SYS_futex, target as *const AtomicU8, FUTEX_WAIT_PRIVATE, target_value, 0, 0, 0) {
            _ => ()
        }
    }
}

#[inline(always)]
pub fn futex_wake_one(target: &AtomicU8) {
    unsafe {
        syscall!(SYS_futex, target as *const AtomicU8, FUTEX_WAKE_PRIVATE, 1, 0, 0, 0).unwrap();
    }
}

#[derive(Default)]
pub struct Backoff {
    counter: usize,
}

impl Backoff {
    #[inline(always)]
    pub fn wait(&mut self) -> bool {
        unsafe {
            if self.counter < BACKOFF_LIMIT {
                for _ in 0..(1 << self.counter) {
                    spin_loop_hint();
                }
                self.counter += 1;
                true
            } else {
                syscall!(SYS_sched_yield).unwrap();
                false
            }
        }
    }
}

pub struct Futex<T> {
    _flag: AtomicU8,
    item: core::cell::UnsafeCell<T>,
}

pub struct FutexHandle<'a, T> {
    _futex: &'a Futex<T>,
    item: &'a mut T,
}

unsafe impl<T> Sync for Futex<T> {}

unsafe impl<T> Send for Futex<T> {}

impl<T> Futex<T> {
    pub fn new(item: T) -> Self {
        Futex {
            _flag: AtomicU8::new(FREE),
            item: UnsafeCell::new(item),
        }
    }

    #[inline(always)]
    fn raw_lock(&self) {
        let mut backoff = Backoff::default();
        loop {
            if self._flag.compare_and_swap(FREE, LOCKED, Ordering::Relaxed) == FREE {
                return;
            }
            if !backoff.wait() {
                break;
            }
        }
        loop {
            if self._flag.load(Ordering::Relaxed) == FUTEX_MODE
                || self._flag.compare_and_swap(LOCKED, FUTEX_MODE, Ordering::SeqCst) == LOCKED {
                futex_wait(&self._flag, FUTEX_MODE);
            }
            if self._flag.compare_and_swap(FREE, FUTEX_MODE, Ordering::SeqCst) == FREE {
                break;
            }
        }
    }

    #[inline(always)]
    fn raw_unlock(&self) {
        if self._flag.fetch_sub(1, Ordering::SeqCst) == FUTEX_MODE {
            self._flag.store(FREE, Ordering::Relaxed);
            futex_wake_one(&self._flag);
        }
    }

    pub fn lock(&self) -> FutexHandle<T> {
        self.raw_lock();
        unsafe {
            FutexHandle {
                _futex: &self,
                item: &mut *self.item.get(),
            }
        }
    }
}

impl<'a, T> Drop for FutexHandle<'a, T> {
    fn drop(&mut self) {
        self._futex.raw_unlock();
    }
}

impl<'a, T> Deref for FutexHandle<'a, T> {
    type Target = T;

    fn deref(&self) -> &Self::Target {
        return self.item;
    }
}

impl<'a, T> DerefMut for FutexHandle<'a, T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        return self.item;
    }
}

The code has already passed some basic tests:

#[cfg(test)]
mod test {
    use std::sync::Arc;

    use super::*;

    #[test]
    fn test_futex() {
        let data = Arc::new(Futex::new(0));
        let mut handles = Vec::new();
        for _ in 0..100 {
            let data = data.clone();
            handles.push(std::thread::spawn(move || {
                let mut handle = data.lock();
                *handle += 1;
                std::thread::sleep(std::time::Duration::from_micros(50));
                println!("done: {}", *handle);
            }));
        }
        for i in handles {
            i.join();
        }
        {
            let handle = data.lock();
            assert_eq!(*handle, 100);
        }
    }
}

But I am a little bit worried whether I am doing things right:

  • I used two Relaxed memory order, it is okay for those positions?

  • I use an exponential backoff method, it is the right choice here?