Initial vendor packages

Signed-off-by: Valentin Popov <valentin@popov.link>

1 files changed, 537 insertions, 0 deletions

diff --git a/vendor/spin/src/mutex/ticket.rs b/vendor/spin/src/mutex/ticket.rs
new file mode 100644
index 0000000..c14869e
--- /dev/null
+++ b/vendor/spin/src/mutex/ticket.rs
@@ -0,0 +1,537 @@
+//! A ticket-based mutex.
+//!
+//! Waiting threads take a 'ticket' from the lock in the order they arrive and gain access to the lock when their
+//! ticket is next in the queue. Best-case latency is slightly worse than a regular spinning mutex, but worse-case
+//! latency is infinitely better. Waiting threads simply need to wait for all threads that come before them in the
+//! queue to finish.
+
+use crate::{
+    atomic::{AtomicUsize, Ordering},
+    RelaxStrategy, Spin,
+};
+use core::{
+    cell::UnsafeCell,
+    fmt,
+    marker::PhantomData,
+    ops::{Deref, DerefMut},
+};
+
+/// A spin-based [ticket lock](https://en.wikipedia.org/wiki/Ticket_lock) providing mutually exclusive access to data.
+///
+/// A ticket lock is analogous to a queue management system for lock requests. When a thread tries to take a lock, it
+/// is assigned a 'ticket'. It then spins until its ticket becomes next in line. When the lock guard is released, the
+/// next ticket will be processed.
+///
+/// Ticket locks significantly reduce the worse-case performance of locking at the cost of slightly higher average-time
+/// overhead.
+///
+/// # Example
+///
+/// ```
+/// use spin;
+///
+/// let lock = spin::mutex::TicketMutex::<_>::new(0);
+///
+/// // Modify the data
+/// *lock.lock() = 2;
+///
+/// // Read the data
+/// let answer = *lock.lock();
+/// assert_eq!(answer, 2);
+/// ```
+///
+/// # Thread safety example
+///
+/// ```
+/// use spin;
+/// use std::sync::{Arc, Barrier};
+///
+/// let thread_count = 1000;
+/// let spin_mutex = Arc::new(spin::mutex::TicketMutex::<_>::new(0));
+///
+/// // We use a barrier to ensure the readout happens after all writing
+/// let barrier = Arc::new(Barrier::new(thread_count + 1));
+///
+/// for _ in (0..thread_count) {
+///     let my_barrier = barrier.clone();
+///     let my_lock = spin_mutex.clone();
+///     std::thread::spawn(move || {
+///         let mut guard = my_lock.lock();
+///         *guard += 1;
+///
+///         // Release the lock to prevent a deadlock
+///         drop(guard);
+///         my_barrier.wait();
+///     });
+/// }
+///
+/// barrier.wait();
+///
+/// let answer = { *spin_mutex.lock() };
+/// assert_eq!(answer, thread_count);
+/// ```
+pub struct TicketMutex<T: ?Sized, R = Spin> {
+    phantom: PhantomData<R>,
+    next_ticket: AtomicUsize,
+    next_serving: AtomicUsize,
+    data: UnsafeCell<T>,
+}
+
+/// A guard that protects some data.
+///
+/// When the guard is dropped, the next ticket will be processed.
+pub struct TicketMutexGuard<'a, T: ?Sized + 'a> {
+    next_serving: &'a AtomicUsize,
+    ticket: usize,
+    data: &'a mut T,
+}
+
+unsafe impl<T: ?Sized + Send, R> Sync for TicketMutex<T, R> {}
+unsafe impl<T: ?Sized + Send, R> Send for TicketMutex<T, R> {}
+
+impl<T, R> TicketMutex<T, R> {
+    /// Creates a new [`TicketMutex`] wrapping the supplied data.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use spin::mutex::TicketMutex;
+    ///
+    /// static MUTEX: TicketMutex<()> = TicketMutex::<_>::new(());
+    ///
+    /// fn demo() {
+    ///     let lock = MUTEX.lock();
+    ///     // do something with lock
+    ///     drop(lock);
+    /// }
+    /// ```
+    #[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),
+        }
+    }
+
+    /// Consumes this [`TicketMutex`] and unwraps the underlying data.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// let lock = spin::mutex::TicketMutex::<_>::new(42);
+    /// assert_eq!(42, lock.into_inner());
+    /// ```
+    #[inline(always)]
+    pub fn into_inner(self) -> T {
+        self.data.into_inner()
+    }
+    /// Returns a mutable pointer to the underying data.
+    ///
+    /// This is mostly meant to be used for applications which require manual unlocking, but where
+    /// storing both the lock and the pointer to the inner data gets inefficient.
+    ///
+    /// # Example
+    /// ```
+    /// let lock = spin::mutex::SpinMutex::<_>::new(42);
+    ///
+    /// unsafe {
+    ///     core::mem::forget(lock.lock());
+    ///
+    ///     assert_eq!(lock.as_mut_ptr().read(), 42);
+    ///     lock.as_mut_ptr().write(58);
+    ///
+    ///     lock.force_unlock();
+    /// }
+    ///
+    /// assert_eq!(*lock.lock(), 58);
+    ///
+    /// ```
+    #[inline(always)]
+    pub fn as_mut_ptr(&self) -> *mut T {
+        self.data.get()
+    }
+}
+
+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> {
+    /// Locks the [`TicketMutex`] and returns a guard that permits access to the inner data.
+    ///
+    /// The returned data may be dereferenced for data access
+    /// and the lock will be dropped when the guard falls out of scope.
+    ///
+    /// ```
+    /// let lock = spin::mutex::TicketMutex::<_>::new(0);
+    /// {
+    ///     let mut data = lock.lock();
+    ///     // The lock is now locked and the data can be accessed
+    ///     *data += 1;
+    ///     // The lock is implicitly dropped at the end of the scope
+    /// }
+    /// ```
+    #[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,
+            // Safety
+            // We know that we are the next ticket to be served,
+            // so there's no other thread accessing the data.
+            //
+            // Every other thread has another ticket number so it's
+            // definitely stuck in the spin loop above.
+            data: unsafe { &mut *self.data.get() },
+        }
+    }
+}
+
+impl<T: ?Sized, R> TicketMutex<T, R> {
+    /// Returns `true` if the lock is currently held.
+    ///
+    /// # Safety
+    ///
+    /// This function provides no synchronization guarantees and so its result should be considered 'out of date'
+    /// the instant it is called. Do not use it for synchronization purposes. However, it may be useful as a heuristic.
+    #[inline(always)]
+    pub fn is_locked(&self) -> bool {
+        let ticket = self.next_ticket.load(Ordering::Relaxed);
+        self.next_serving.load(Ordering::Relaxed) != ticket
+    }
+
+    /// Force unlock this [`TicketMutex`], by serving the next ticket.
+    ///
+    /// # Safety
+    ///
+    /// This is *extremely* unsafe if the lock is not held by the current
+    /// thread. However, this can be useful in some instances for exposing the
+    /// lock to FFI that doesn't know how to deal with RAII.
+    #[inline(always)]
+    pub unsafe fn force_unlock(&self) {
+        self.next_serving.fetch_add(1, Ordering::Release);
+    }
+
+    /// Try to lock this [`TicketMutex`], returning a lock guard if successful.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// let lock = spin::mutex::TicketMutex::<_>::new(42);
+    ///
+    /// let maybe_guard = lock.try_lock();
+    /// assert!(maybe_guard.is_some());
+    ///
+    /// // `maybe_guard` is still held, so the second call fails
+    /// let maybe_guard2 = lock.try_lock();
+    /// assert!(maybe_guard2.is_none());
+    /// ```
+    #[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,
+            // Safety
+            // We have a ticket that is equal to the next_serving ticket, so we know:
+            // - that no other thread can have the same ticket id as this thread
+            // - that we are the next one to be served so we have exclusive access to the data
+            data: unsafe { &mut *self.data.get() },
+        })
+    }
+
+    /// Returns a mutable reference to the underlying data.
+    ///
+    /// Since this call borrows the [`TicketMutex`] mutably, and a mutable reference is guaranteed to be exclusive in
+    /// Rust, no actual locking needs to take place -- the mutable borrow statically guarantees no locks exist. As
+    /// such, this is a 'zero-cost' operation.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// let mut lock = spin::mutex::TicketMutex::<_>::new(0);
+    /// *lock.get_mut() = 10;
+    /// assert_eq!(*lock.lock(), 10);
+    /// ```
+    #[inline(always)]
+    pub fn get_mut(&mut self) -> &mut T {
+        // Safety:
+        // We know that there are no other references to `self`,
+        // so it's safe to return a exclusive reference to the data.
+        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> {
+    /// Leak the lock guard, yielding a mutable reference to the underlying data.
+    ///
+    /// Note that this function will permanently lock the original [`TicketMutex`].
+    ///
+    /// ```
+    /// let mylock = spin::mutex::TicketMutex::<_>::new(0);
+    ///
+    /// let data: &mut i32 = spin::mutex::TicketMutexGuard::leak(mylock.lock());
+    ///
+    /// *data = 1;
+    /// assert_eq!(*data, 1);
+    /// ```
+    #[inline(always)]
+    pub fn leak(this: Self) -> &'a mut T {
+        let data = this.data as *mut _; // Keep it in pointer form temporarily to avoid double-aliasing
+        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) {
+        // Prevent guard destructor running
+        core::mem::forget(Self::lock(self));
+    }
+
+    fn try_lock(&self) -> bool {
+        // Prevent guard destructor running
+        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);
+
+        // First lock succeeds
+        let a = mutex.try_lock();
+        assert_eq!(a.as_ref().map(|r| **r), Some(42));
+
+        // Additional lock fails
+        let b = mutex.try_lock();
+        assert!(b.is_none());
+
+        // After dropping lock, it succeeds again
+        ::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() {
+        // Tests nested mutexes and access
+        // to underlying data.
+        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());
+    }
+}