wasm/core/
rw_spinlock.rs

1//! Naive implementation of spin based locking mechanisms
2//!
3//! This module provides implementations for locking mechanisms required.
4//!
5//! # Acknowledgement
6//!
7//! This implementation is largely inspired by the book
8//! ["Rust Atomics and Locks" by Mara Bos](https://marabos.nl/atomics/).
9
10use core::cell::UnsafeCell;
11use core::hint::{self};
12use core::ops::{Deref, DerefMut};
13use core::sync::atomic::{AtomicU32, Ordering};
14
15/// A spinlock based, read-write lock which favours writers over readers
16///
17/// # Properties
18///
19/// - Read-write semantics allow for multiple readers at the same time, but require exclusive access
20///   for a writer
21/// - Spin based, e.g. waiting for the lock wastes CPU cycles in a busy loop
22///    - This design however enables an implementation independent of operating system features like
23///      condition variables, the only requirement are 32 bit atomics in the ISA
24/// - Biased towards writes: once a writer waits for the lock, all new reader wait until that writer
25///   got access
26pub struct RwSpinLock<T> {
27    /// The inner data protected by this lock
28    inner: UnsafeCell<T>,
29
30    /// Lock state (on ambiguity, the state closer to the top takes precedence)
31    ///
32    /// - `0` means there are no readers nor any writer
33    /// - `u32::MAX` means there is a single active writer
34    /// - `state % 2 == 0` means there are `state / 2` active readers
35    /// - `state % 2 != 0` means there are `(state - 1) / 2` active readers and at least one waiting
36    ///   writer
37    state: AtomicU32,
38}
39
40impl<T> RwSpinLock<T> {
41    /// Create a new instance of self, wrapping the `value` of type `T`
42    pub fn new(value: T) -> Self {
43        Self {
44            inner: UnsafeCell::new(value),
45            state: AtomicU32::new(0),
46        }
47    }
48
49    // Get read access to the value wrapped in this [`RwSpinLock`]
50    pub fn read(&self) -> ReadLockGuard<T> {
51        // get the current state
52        let mut s = self.state.load(Ordering::Relaxed); // ordering by the book
53
54        loop {
55            // s is even, so there are maybe active readers but no active or waiting writer
56            // -> reader can acquire read guard (as long as an overflow is avoided)
57            if s % 2 == 0 && s < u32::MAX - 2 {
58                match self.state.compare_exchange_weak(
59                    s,
60                    s + 2,
61                    Ordering::Acquire,
62                    Ordering::Relaxed,
63                ) {
64                    Ok(_) => return ReadLockGuard { lock: self },
65                    Err(update_s) => s = update_s,
66                }
67            }
68
69            // there is one active (`s == u32::MAX`) or at least one waiting (otherwise) writer
70            // -> spin, re-load s and try again
71            if s % 2 == 1 {
72                hint::spin_loop();
73                s = self.state.load(Ordering::Relaxed); // ordering by the book
74            }
75        }
76    }
77
78    // Get write access to the value wrapped in this [`RwSpinLock`]
79    pub fn write(&self) -> WriteLockGuard<T> {
80        let mut s = self.state.load(Ordering::Relaxed);
81
82        loop {
83            // there is no active reader (`s >= 2 && s % 2 == 0`) or writer (`s == u32::MAX`)
84            if s <= 1 {
85                match self
86                    .state
87                    .compare_exchange(s, u32::MAX, Ordering::Acquire, Ordering::Relaxed)
88                {
89                    Ok(_) => return WriteLockGuard { lock: self },
90                    Err(updated_s) => {
91                        s = updated_s;
92                        continue;
93                    }
94                }
95            }
96
97            // announce that a writer is waiting if this is not yet announced
98            if s % 2 == 0 {
99                match self
100                    .state
101                    // ordering by the book
102                    .compare_exchange(s, s + 1, Ordering::Relaxed, Ordering::Relaxed)
103                {
104                    Ok(_) => {}
105                    Err(updated_s) => {
106                        s = updated_s;
107                        continue;
108                    }
109                }
110            }
111
112            // wait was announced, there are still active readers
113            // -> spin, re-load s, continue from the start of the lop
114            hint::spin_loop();
115            s = self.state.load(Ordering::Relaxed);
116        }
117    }
118}
119
120unsafe impl<T> Sync for RwSpinLock<T> where T: Send + Sync {}
121
122/// Read guard for the [`RwSpinLock`]
123pub struct ReadLockGuard<'a, T> {
124    lock: &'a RwSpinLock<T>,
125}
126
127impl<T> Deref for ReadLockGuard<'_, T> {
128    type Target = T;
129    fn deref(&self) -> &T {
130        unsafe { &*self.lock.inner.get() }
131    }
132}
133
134impl<T> Drop for ReadLockGuard<'_, T> {
135    fn drop(&mut self) {
136        self.lock.state.fetch_sub(2, Ordering::Release); // ordering by the book
137    }
138}
139
140/// Write guard for the [`RwSpinLock`]
141pub struct WriteLockGuard<'a, T> {
142    lock: &'a RwSpinLock<T>,
143}
144
145impl<T> Deref for WriteLockGuard<'_, T> {
146    type Target = T;
147    fn deref(&self) -> &T {
148        unsafe { &*self.lock.inner.get() }
149    }
150}
151
152impl<T> DerefMut for WriteLockGuard<'_, T> {
153    fn deref_mut(&mut self) -> &mut T {
154        unsafe { &mut *self.lock.inner.get() }
155    }
156}
157
158impl<T> Drop for WriteLockGuard<'_, T> {
159    fn drop(&mut self) {
160        self.lock.state.store(0, Ordering::Release); // ordering by the book
161    }
162}
wasm/core/rw_spinlock.rs

wasm/core/
rw_spinlock.rs
