1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

use core::cell::UnsafeCell;
use core::ops::{Deref, DerefMut};
use core::sync::atomic::{AtomicUsize, Ordering::*};

/// By the use of Ticketlocks, it is possible to serialize blocks of code
/// that might run parallel on multiple CPU cores.
///
/// Synchronization is implemented using a lock and a ticket variable.
/// Once a thread tries to enter the critical area, it obtains a ticket by
/// atomic increment of the ticket variable and waits until the lock variable
/// is equal to its ticket.
/// When a thread leaves the critical area, it increments the lock variable by
/// one and thereby allows the next thread to enter the critical area.
#[derive(Debug, Default)]
pub struct Ticket<T> {
    serving: AtomicUsize,
    ticket: AtomicUsize,
    /// Wrap the mutable data inside an unsafe cell, so that the compiler doesn't optimize it away
    value: UnsafeCell<T>,
}

unsafe impl<T> Sync for Ticket<T> {}
unsafe impl<T> Send for Ticket<T> {}

impl<T> Ticket<T> {
    /// Create a new ticket lock, protecting `value`
    pub const fn new(value: T) -> Self {
        Self {
            serving: AtomicUsize::new(0),
            ticket: AtomicUsize::new(0),
            value: UnsafeCell::new(value),
        }
    }
    /// Locks the lock and returns the protected data.
    ///
    /// The data is wrapped in a guard, that unlocks the lock if it goes out of scope.
    #[must_use]
    pub fn lock(&self) -> TicketGuard<T> {
        let ticket = self.ticket.fetch_add(1, Relaxed);
        while ticket != self.serving.load(Acquire) {
            // pausing the cpu
            core::hint::spin_loop();
        }
        TicketGuard { lock: self }
    }
    /// If you really want to unlock it. This is not protected by race conditions!
    pub unsafe fn unlock(&self) {
        self.serving.fetch_add(1, Release);
    }
    /// If you really want to access the contents. This is not protected by race conditions!
    #[allow(clippy::mut_from_ref)]
    pub unsafe fn raw(&self) -> &mut T {
        &mut *self.value.get()
    }
}

/// Accessor for the locks data, that unlocks if it goes out of scope.
pub struct TicketGuard<'a, T> {
    lock: &'a Ticket<T>,
}
impl<'a, T> Deref for TicketGuard<'a, T> {
    type Target = T;

    fn deref(&self) -> &Self::Target {
        unsafe { self.lock.raw() }
    }
}
impl<'a, T> DerefMut for TicketGuard<'a, T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        unsafe { self.lock.raw() }
    }
}
impl<'a, T> Drop for TicketGuard<'a, T> {
    fn drop(&mut self) {
        unsafe { self.lock.unlock() };
    }
}