use core::{
cell::UnsafeCell,
fmt,
ops::{Deref, DerefMut},
sync::atomic::{AtomicUsize, Ordering},
marker::PhantomData,
};
use crate::{RelaxStrategy, Spin};
pub struct TicketMutex<T: ?Sized, R = Spin> {
phantom: PhantomData<R>,
next_ticket: AtomicUsize,
next_serving: AtomicUsize,
data: UnsafeCell<T>,
}
pub struct TicketMutexGuard<'a, T: ?Sized + 'a> {
next_serving: &'a AtomicUsize,
ticket: usize,
data: &'a mut T,
}
unsafe impl<T: ?Sized + Send> Sync for TicketMutex<T> {}
unsafe impl<T: ?Sized + Send> Send for TicketMutex<T> {}
impl<T, R> TicketMutex<T, R> {
#[inline(always)]
pub const fn new(data: T) -> Self {
Self {
phantom: PhantomData,
next_ticket: AtomicUsize::new(0),
next_serving: AtomicUsize::new(0),
data: UnsafeCell::new(data),
}
}
#[inline(always)]
pub fn into_inner(self) -> T {
self.data.into_inner()
}
}
impl<T: ?Sized + fmt::Debug, R> fmt::Debug for TicketMutex<T, R> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match self.try_lock() {
Some(guard) => write!(f, "Mutex {{ data: ")
.and_then(|()| (&*guard).fmt(f))
.and_then(|()| write!(f, "}}")),
None => write!(f, "Mutex {{ <locked> }}"),
}
}
}
impl<T: ?Sized, R: RelaxStrategy> TicketMutex<T, R> {
#[inline(always)]
pub fn lock(&self) -> TicketMutexGuard<T> {
let ticket = self.next_ticket.fetch_add(1, Ordering::Relaxed);
while self.next_serving.load(Ordering::Acquire) != ticket {
R::relax();
}
TicketMutexGuard {
next_serving: &self.next_serving,
ticket,
data: unsafe { &mut *self.data.get() },
}
}
}
impl<T: ?Sized, R> TicketMutex<T, R> {
#[inline(always)]
pub fn is_locked(&self) -> bool {
let ticket = self.next_ticket.load(Ordering::Relaxed);
self.next_serving.load(Ordering::Relaxed) != ticket
}
#[inline(always)]
pub unsafe fn force_unlock(&self) {
self.next_serving.fetch_add(1, Ordering::Release);
}
#[inline(always)]
pub fn try_lock(&self) -> Option<TicketMutexGuard<T>> {
let ticket = self
.next_ticket
.fetch_update(Ordering::SeqCst, Ordering::SeqCst, |ticket| {
if self.next_serving.load(Ordering::Acquire) == ticket {
Some(ticket + 1)
} else {
None
}
});
ticket.ok().map(|ticket| TicketMutexGuard {
next_serving: &self.next_serving,
ticket,
data: unsafe { &mut *self.data.get() },
})
}
#[inline(always)]
pub fn get_mut(&mut self) -> &mut T {
unsafe { &mut *self.data.get() }
}
}
impl<T: ?Sized + Default, R> Default for TicketMutex<T, R> {
fn default() -> Self {
Self::new(Default::default())
}
}
impl<T, R> From<T> for TicketMutex<T, R> {
fn from(data: T) -> Self {
Self::new(data)
}
}
impl<'a, T: ?Sized> TicketMutexGuard<'a, T> {
#[inline(always)]
pub fn leak(this: Self) -> &'a mut T {
let data = this.data as *mut _; core::mem::forget(this);
unsafe { &mut *data }
}
}
impl<'a, T: ?Sized + fmt::Debug> fmt::Debug for TicketMutexGuard<'a, T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
fmt::Debug::fmt(&**self, f)
}
}
impl<'a, T: ?Sized + fmt::Display> fmt::Display for TicketMutexGuard<'a, T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
fmt::Display::fmt(&**self, f)
}
}
impl<'a, T: ?Sized> Deref for TicketMutexGuard<'a, T> {
type Target = T;
fn deref(&self) -> &T {
self.data
}
}
impl<'a, T: ?Sized> DerefMut for TicketMutexGuard<'a, T> {
fn deref_mut(&mut self) -> &mut T {
self.data
}
}
impl<'a, T: ?Sized> Drop for TicketMutexGuard<'a, T> {
fn drop(&mut self) {
let new_ticket = self.ticket + 1;
self.next_serving.store(new_ticket, Ordering::Release);
}
}
#[cfg(feature = "lock_api")]
unsafe impl<R: RelaxStrategy> lock_api_crate::RawMutex for TicketMutex<(), R> {
type GuardMarker = lock_api_crate::GuardSend;
const INIT: Self = Self::new(());
fn lock(&self) {
core::mem::forget(Self::lock(self));
}
fn try_lock(&self) -> bool {
Self::try_lock(self).map(core::mem::forget).is_some()
}
unsafe fn unlock(&self) {
self.force_unlock();
}
fn is_locked(&self) -> bool {
Self::is_locked(self)
}
}
#[cfg(test)]
mod tests {
use std::prelude::v1::*;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::mpsc::channel;
use std::sync::Arc;
use std::thread;
type TicketMutex<T> = super::TicketMutex<T>;
#[derive(Eq, PartialEq, Debug)]
struct NonCopy(i32);
#[test]
fn smoke() {
let m = TicketMutex::<_>::new(());
drop(m.lock());
drop(m.lock());
}
#[test]
fn lots_and_lots() {
static M: TicketMutex<()> = TicketMutex::<_>::new(());
static mut CNT: u32 = 0;
const J: u32 = 1000;
const K: u32 = 3;
fn inc() {
for _ in 0..J {
unsafe {
let _g = M.lock();
CNT += 1;
}
}
}
let (tx, rx) = channel();
for _ in 0..K {
let tx2 = tx.clone();
thread::spawn(move || {
inc();
tx2.send(()).unwrap();
});
let tx2 = tx.clone();
thread::spawn(move || {
inc();
tx2.send(()).unwrap();
});
}
drop(tx);
for _ in 0..2 * K {
rx.recv().unwrap();
}
assert_eq!(unsafe { CNT }, J * K * 2);
}
#[test]
fn try_lock() {
let mutex = TicketMutex::<_>::new(42);
let a = mutex.try_lock();
assert_eq!(a.as_ref().map(|r| **r), Some(42));
let b = mutex.try_lock();
assert!(b.is_none());
::core::mem::drop(a);
let c = mutex.try_lock();
assert_eq!(c.as_ref().map(|r| **r), Some(42));
}
#[test]
fn test_into_inner() {
let m = TicketMutex::<_>::new(NonCopy(10));
assert_eq!(m.into_inner(), NonCopy(10));
}
#[test]
fn test_into_inner_drop() {
struct Foo(Arc<AtomicUsize>);
impl Drop for Foo {
fn drop(&mut self) {
self.0.fetch_add(1, Ordering::SeqCst);
}
}
let num_drops = Arc::new(AtomicUsize::new(0));
let m = TicketMutex::<_>::new(Foo(num_drops.clone()));
assert_eq!(num_drops.load(Ordering::SeqCst), 0);
{
let _inner = m.into_inner();
assert_eq!(num_drops.load(Ordering::SeqCst), 0);
}
assert_eq!(num_drops.load(Ordering::SeqCst), 1);
}
#[test]
fn test_mutex_arc_nested() {
let arc = Arc::new(TicketMutex::<_>::new(1));
let arc2 = Arc::new(TicketMutex::<_>::new(arc));
let (tx, rx) = channel();
let _t = thread::spawn(move || {
let lock = arc2.lock();
let lock2 = lock.lock();
assert_eq!(*lock2, 1);
tx.send(()).unwrap();
});
rx.recv().unwrap();
}
#[test]
fn test_mutex_arc_access_in_unwind() {
let arc = Arc::new(TicketMutex::<_>::new(1));
let arc2 = arc.clone();
let _ = thread::spawn(move || -> () {
struct Unwinder {
i: Arc<TicketMutex<i32>>,
}
impl Drop for Unwinder {
fn drop(&mut self) {
*self.i.lock() += 1;
}
}
let _u = Unwinder { i: arc2 };
panic!();
})
.join();
let lock = arc.lock();
assert_eq!(*lock, 2);
}
#[test]
fn test_mutex_unsized() {
let mutex: &TicketMutex<[i32]> = &TicketMutex::<_>::new([1, 2, 3]);
{
let b = &mut *mutex.lock();
b[0] = 4;
b[2] = 5;
}
let comp: &[i32] = &[4, 2, 5];
assert_eq!(&*mutex.lock(), comp);
}
#[test]
fn is_locked() {
let mutex = TicketMutex::<_>::new(());
assert!(!mutex.is_locked());
let lock = mutex.lock();
assert!(mutex.is_locked());
drop(lock);
assert!(!mutex.is_locked());
}
}