housekeeping 0.0.3

//! Integration tests using [`loom`].
//!
//! These tests are based on [`crossbeam-epoch`'s `test/loom.rs` test], which is
//! licensed under Apache-2.0 or MIT.
//!
//! [`crossbeam-epoch`'s `test/loom.rs` test]: https://github.com/crossbeam-rs/crossbeam/blob/03919fedb43cdbd0866aee0c77e0d6df8976b12f/crossbeam-epoch/tests/loom.rs

#![cfg(feature = "loom")]

use std::{mem::ManuallyDrop, ptr, sync::Arc};

use housekeeping::{Cleanups, Guard};
use loom::sync::atomic::{self, AtomicPtr};

#[test]
fn it_works() {
    loom::model(|| {
        let cleanups = Arc::new(Cleanups::new());
        let item = Box::into_raw(Box::new(String::from("boom")));

        let mut guard = Guard::new(cleanups.clone());

        let th = loom::thread::spawn({
            let cleanups = cleanups.clone();
            move || {
                let guard = Guard::new(cleanups);
                unsafe {
                    guard.defer_unchecked(move || {
                        (*item).retain(|c| c == 'o');
                        let _ = Box::from_raw(item);
                    })
                };
            }
        });

        // SAFETY: 'item' is guarded by 'guard'.
        assert_eq!(unsafe { &**item }, "boom");

        if let Some(batches) = guard.refresh() {
            batches.into_iter().for_each(|mut b| b.execute());
        }

        th.join().unwrap();

        std::mem::drop(guard);

        Arc::try_unwrap(cleanups)
            .unwrap_or_else(|_| panic!())
            .take_leftovers()
            .into_iter()
            .for_each(|mut b| b.execute());
    })
}

#[test]
fn treiber_stack() {
    /// Treiber's lock-free stack.
    ///
    /// Usable with any number of producers and consumers.
    struct TreiberStack<T> {
        head: AtomicPtr<Node<T>>,
    }

    struct Node<T> {
        data: ManuallyDrop<T>,
        next: AtomicPtr<Node<T>>,
    }

    impl<T> TreiberStack<T> {
        /// Create a new, empty [`TreiberStack`].
        fn new() -> Self {
            Self {
                head: AtomicPtr::new(ptr::null_mut()),
            }
        }

        /// Push a value on top of the stack.
        fn push(&self, item: T, _guard: &Guard) {
            let node = Box::into_raw(Box::new(Node {
                data: ManuallyDrop::new(item),
                next: AtomicPtr::new(ptr::null_mut()),
            }));

            let mut head = self.head.load(atomic::Ordering::Relaxed);

            loop {
                unsafe { (*node).next.store(head, atomic::Ordering::Relaxed) };

                match self.head.compare_exchange(
                    head,
                    node,
                    atomic::Ordering::Release,
                    atomic::Ordering::Relaxed,
                ) {
                    Ok(_) => break,
                    Err(new_head) => head = new_head,
                }
            }
        }

        /// Pop an element from the top of the stack.
        ///
        /// Returns `None` if the stack is empty.
        fn pop(&self, guard: &Guard) -> Option<T> {
            let mut head = self.head.load(atomic::Ordering::Acquire);
            loop {
                let Node { data, next } = unsafe { head.as_ref() }?;
                let next = next.load(atomic::Ordering::Relaxed);

                match self.head.compare_exchange(
                    head,
                    next,
                    atomic::Ordering::Relaxed,
                    atomic::Ordering::Acquire,
                ) {
                    Ok(_) => unsafe {
                        guard.defer_unchecked(move || {
                            let _ = Box::from_raw(head);
                        });
                        return Some(ManuallyDrop::into_inner(ptr::read(data)));
                    },
                    Err(new_head) => head = new_head,
                }
            }
        }

        /// Returns `true` if the stack is empty.
        fn is_empty(&self) -> bool {
            self.head.load(atomic::Ordering::Relaxed).is_null()
        }
    }

    impl<T> Drop for TreiberStack<T> {
        fn drop(&mut self) {
            let mut head = self.head.with_mut(|h| *h);
            while !head.is_null() {
                let mut node = unsafe { Box::from_raw(head) };
                unsafe {
                    ManuallyDrop::drop(&mut node.data);
                };
                head = node.next.with_mut(|h| *h);
            }
        }
    }

    loom::model(move || {
        let cleanups = Arc::new(Cleanups::new());
        let stack = Arc::new(TreiberStack::new());

        let th = loom::thread::spawn({
            let cleanups = cleanups.clone();
            let stack = stack.clone();
            move || {
                let guard = Guard::new(cleanups);

                // Cause enough actions to send a batch.
                for i in 0..5 {
                    stack.push(i, &guard);
                    assert!(stack.pop(&guard).is_some());
                }
            }
        });

        let guard = Guard::new(cleanups.clone());
        for i in 0..5 {
            stack.push(i, &guard);
            assert!(stack.pop(&guard).is_some());
        }

        th.join().unwrap();
        assert!(stack.pop(&guard).is_none());
        assert!(stack.is_empty());

        std::mem::drop(guard);
        Arc::try_unwrap(cleanups)
            .unwrap_or_else(|_| panic!())
            .take_leftovers()
            .into_iter()
            .for_each(|mut b| b.execute());
    });
}