From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001
From: Daniel Baumann <daniel.baumann@progress-linux.org>
Date: Wed, 17 Apr 2024 14:02:58 +0200
Subject: Adding upstream version 1.64.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
---
 vendor/sharded-slab/src/page/stack.rs | 124 ++++++++++++++++++++++++++++++++++
 1 file changed, 124 insertions(+)
 create mode 100644 vendor/sharded-slab/src/page/stack.rs

(limited to 'vendor/sharded-slab/src/page/stack.rs')

diff --git a/vendor/sharded-slab/src/page/stack.rs b/vendor/sharded-slab/src/page/stack.rs
new file mode 100644
index 000000000..e28d9b1a7
--- /dev/null
+++ b/vendor/sharded-slab/src/page/stack.rs
@@ -0,0 +1,124 @@
+use crate::cfg;
+use crate::sync::atomic::{AtomicUsize, Ordering};
+use std::{fmt, marker::PhantomData};
+
+pub(super) struct TransferStack<C = cfg::DefaultConfig> {
+    head: AtomicUsize,
+    _cfg: PhantomData<fn(C)>,
+}
+
+impl<C: cfg::Config> TransferStack<C> {
+    pub(super) fn new() -> Self {
+        Self {
+            head: AtomicUsize::new(super::Addr::<C>::NULL),
+            _cfg: PhantomData,
+        }
+    }
+
+    pub(super) fn pop_all(&self) -> Option<usize> {
+        let val = self.head.swap(super::Addr::<C>::NULL, Ordering::Acquire);
+        test_println!("-> pop {:#x}", val);
+        if val == super::Addr::<C>::NULL {
+            None
+        } else {
+            Some(val)
+        }
+    }
+
+    fn push(&self, new_head: usize, before: impl Fn(usize)) {
+        // We loop to win the race to set the new head. The `next` variable
+        // is the next slot on the stack which needs to be pointed to by the
+        // new head.
+        let mut next = self.head.load(Ordering::Relaxed);
+        loop {
+            test_println!("-> next {:#x}", next);
+            before(next);
+
+            match self
+                .head
+                .compare_exchange(next, new_head, Ordering::Release, Ordering::Relaxed)
+            {
+                // lost the race!
+                Err(actual) => {
+                    test_println!("-> retry!");
+                    next = actual;
+                }
+                Ok(_) => {
+                    test_println!("-> successful; next={:#x}", next);
+                    return;
+                }
+            }
+        }
+    }
+}
+
+impl<C: cfg::Config> super::FreeList<C> for TransferStack<C> {
+    fn push<T>(&self, new_head: usize, slot: &super::Slot<T, C>) {
+        self.push(new_head, |next| slot.set_next(next))
+    }
+}
+
+impl<C> fmt::Debug for TransferStack<C> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_struct("TransferStack")
+            .field(
+                "head",
+                &format_args!("{:#0x}", &self.head.load(Ordering::Relaxed)),
+            )
+            .finish()
+    }
+}
+
+#[cfg(all(loom, test))]
+mod test {
+    use super::*;
+    use crate::{sync::UnsafeCell, test_util};
+    use loom::thread;
+    use std::sync::Arc;
+
+    #[test]
+    fn transfer_stack() {
+        test_util::run_model("transfer_stack", || {
+            let causalities = [UnsafeCell::new(999), UnsafeCell::new(999)];
+            let shared = Arc::new((causalities, TransferStack::<cfg::DefaultConfig>::new()));
+            let shared1 = shared.clone();
+            let shared2 = shared.clone();
+
+            let t1 = thread::spawn(move || {
+                let (causalities, stack) = &*shared1;
+                stack.push(0, |prev| {
+                    causalities[0].with_mut(|c| unsafe {
+                        *c = 0;
+                    });
+                    test_println!("prev={:#x}", prev)
+                });
+            });
+            let t2 = thread::spawn(move || {
+                let (causalities, stack) = &*shared2;
+                stack.push(1, |prev| {
+                    causalities[1].with_mut(|c| unsafe {
+                        *c = 1;
+                    });
+                    test_println!("prev={:#x}", prev)
+                });
+            });
+
+            let (causalities, stack) = &*shared;
+            let mut idx = stack.pop_all();
+            while idx == None {
+                idx = stack.pop_all();
+                thread::yield_now();
+            }
+            let idx = idx.unwrap();
+            causalities[idx].with(|val| unsafe {
+                assert_eq!(
+                    *val, idx,
+                    "UnsafeCell write must happen-before index is pushed to the stack!"
+                );
+            });
+
+            t1.join().unwrap();
+            t2.join().unwrap();
+        });
+    }
+}
-- 
cgit v1.2.3