title: Futex design and backoff
body: <p>I am writing something without <code>libc</code> and I need a mutex for synchronization (I used <code>#![cfg_attr(not(test), no_std)]</code>). Here is my code:</p>
  <pre class="lang-rust prettyprint-override"><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: &amp;AtomicU8, target_value: u8) {
      unsafe {
          match syscall!(SYS_futex, target as *const AtomicU8, FUTEX_WAIT_PRIVATE, target_value, 0, 0, 0) {
              _ =&gt; ()
          }
      }
  }
  
  #[inline(always)]
  pub fn futex_wake_one(target: &amp;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(&amp;mut self) -&gt; bool {
          unsafe {
              if self.counter &lt; BACKOFF_LIMIT {
                  for _ in 0..(1 &lt;&lt; self.counter) {
                      spin_loop_hint();
                  }
                  self.counter += 1;
                  true
              } else {
                  syscall!(SYS_sched_yield).unwrap();
                  false
              }
          }
      }
  }
  
  pub struct Futex&lt;T&gt; {
      _flag: AtomicU8,
      item: core::cell::UnsafeCell&lt;T&gt;,
  }
  
  pub struct FutexHandle&lt;'a, T&gt; {
      _futex: &amp;'a Futex&lt;T&gt;,
      item: &amp;'a mut T,
  }
  
  unsafe impl&lt;T&gt; Sync for Futex&lt;T&gt; {}
  
  unsafe impl&lt;T&gt; Send for Futex&lt;T&gt; {}
  
  impl&lt;T&gt; Futex&lt;T&gt; {
      pub fn new(item: T) -&gt; Self {
          Futex {
              _flag: AtomicU8::new(FREE),
              item: UnsafeCell::new(item),
          }
      }
  
      #[inline(always)]
      fn raw_lock(&amp;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(&amp;self._flag, FUTEX_MODE);
              }
              if self._flag.compare_and_swap(FREE, FUTEX_MODE, Ordering::SeqCst) == FREE {
                  break;
              }
          }
      }
  
      #[inline(always)]
      fn raw_unlock(&amp;self) {
          if self._flag.fetch_sub(1, Ordering::SeqCst) == FUTEX_MODE {
              self._flag.store(FREE, Ordering::Relaxed);
              futex_wake_one(&amp;self._flag);
          }
      }
  
      pub fn lock(&amp;self) -&gt; FutexHandle&lt;T&gt; {
          self.raw_lock();
          unsafe {
              FutexHandle {
                  _futex: &amp;self,
                  item: &amp;mut *self.item.get(),
              }
          }
      }
  }
  
  impl&lt;'a, T&gt; Drop for FutexHandle&lt;'a, T&gt; {
      fn drop(&amp;mut self) {
          self._futex.raw_unlock();
      }
  }
  
  impl&lt;'a, T&gt; Deref for FutexHandle&lt;'a, T&gt; {
      type Target = T;
  
      fn deref(&amp;self) -&gt; &amp;Self::Target {
          return self.item;
      }
  }
  
  impl&lt;'a, T&gt; DerefMut for FutexHandle&lt;'a, T&gt; {
      fn deref_mut(&amp;mut self) -&gt; &amp;mut Self::Target {
          return self.item;
      }
  }
  </code></pre>
  <p>The code has already passed some basic tests:</p>
  <pre class="lang-rust prettyprint-override"><code>#[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!(&quot;done: {}&quot;, *handle);
              }));
          }
          for i in handles {
              i.join();
          }
          {
              let handle = data.lock();
              assert_eq!(*handle, 100);
          }
      }
  }
  </code></pre>
  <p>But I am a little bit worried whether I am doing things right:</p>
  <ul>
  <li><p>I used two <code>Relaxed</code> memory order, it is okay for those positions?</p>
  </li>
  <li><p>I use an exponential backoff method, it is the right choice here?</p>
  </li>
  </ul>