rust - 无锁堆栈，将 is_empty() 中的 Acquire 替换为 Relaxed

Question

有一个无锁堆栈here基于来自 Crossbeam 的基于纪元的回收。

我添加了一些注释来帮助我理解这个实现。

#[derive(Debug)] 
pub struct TreiberStack<T> { 
    head: Atomic<Node<T>>, 
} 


#[derive(Debug)] 
struct Node<T> { 
    data: ManuallyDrop<T>, 
    next: Atomic<Node<T>>, 
} 


impl<T> TreiberStack<T> { 
    pub fn new() -> TreiberStack<T> { 
        TreiberStack { 
            head: Atomic::null(), 
        } 
    } 


    pub fn push(&self, t: T) { 
        let mut n = Owned::new(Node { 
            data: ManuallyDrop::new(t), 
            next: Atomic::null(), 
        }); 


        let guard = epoch::pin(); 


        loop { 
            let head = self.head.load(Relaxed, &guard);   // (1) ’Relaxed’ only provides atomicity
            n.next.store(head, Relaxed);  // (2) ‘Relaxed’ only provides atomicity
        // (2) uses ‘head’ from (1). so (2) and (1)’s partial order won’t be rotated by CPU and compiler

            // it seems that compare_and_set behaves just like compare_and_swap.
            // It guarantees that all
            // memory operations before the RELEASE operation will appear to happen
            // before the RELEASE operation with respect to the other components of the system.
       //  So (1) and (2) always execute before (3)
            match self.head.compare_and_set(head, n, Release, &guard) {   // (3)
                Ok(_) => break, 
                Err(e) => n = e.new, 
            } 
        } 
    } 



    pub fn pop(&self) -> Option<T> { 
        let guard = epoch::pin();  
        loop { 

            // It guarantees that all memory
            // operations after the ACQUIRE operation will appear to happen after the
            // ACQUIRE operation with respect to the other components of the system.
            let head = self.head.load(Acquire, &guard);    // (4)


            match unsafe { head.as_ref() } { 
                Some(h) => { 
                    let next = h.next.load(Relaxed, &guard); // (5) ’Relaxed’ only provides atomicity


                    if self 
                        .head 
                        .compare_and_set(head, next, Release, &guard)   
                        .is_ok() // (6)
                    // This RELEASE matches the ACQUIRE in (4). Code between them won’t be reordered by CPU and compiler
                    { 
                        unsafe { 
                            guard.defer_destroy(head);  
                            return Some(ManuallyDrop::into_inner(ptr::read(&(*h).data))); 
                        } 
                    } 
                } 
                None => return None, 
            } 
        } 
    } 


    // Returns `true` if the stack is empty. 
    pub fn is_empty(&self) -> bool { 
        let guard = epoch::pin(); 
        self.head.load(Acquire, &guard).is_null()   // (7)
    } 
} 


impl<T> Drop for TreiberStack<T> { 
    fn drop(&mut self) { 
        while self.pop().is_some() {} 
    } 
} 

我的问题是:我可以将 (7) 的 Acquire 替换为“Relaxed”吗？似乎 (7) 处的 Atomicity 足以使其工作。 Acquire 通常与 Release 配对以提供 Visibility:

after an ACQUIRE on a given variable, all memory accesses preceding any prior RELEASE on that same variable are guaranteed to be visible. In other words, within a given variable's critical section, all accesses of all previous critical sections for that variable are guaranteed to have completed.

Visibility 在此代码中扮演什么角色？看起来代码的顺序和原子性是我需要使这段代码工作的唯一保证。如果没有 Visibility，其他线程最终将看到 store 的结果。所以代码仍然可以正常工作。

我主要从 Linux Kernel 的文档中学习无锁 here

Answer 1

My question is: Can I replace (7)'s Acquire with 'Relaxed'? It seems that Atomicity at (7) is sufficient enough to make it work.

假设我们使用 Relaxed 而不是建议的 Acquire。 (3) 处的 Release 不保证 is_empty() 会看到调用 push() 的线程的内存访问。对于像

这样使用 Treiber 堆栈的消费者线程，它可能变得特别重要

if !my_stack.is_empty() {
  let elem = my_stack.pop().unwrap();
  // Do things with elem...
} else {
  // Do something expensive...
}

[...] the other thread will see the outcome of store eventually.

你是对的。但是，我想尽量减少执行昂贵操作的时间。在上面的代码片段中，我希望 is_empty() 和 pop() 始终指示我的堆栈处于相同状态。如果这些方法使用不同的原子顺序，我们将失去这种保证，并且我们可能最终会因为 is_empty() 尚未同步而完成更昂贵的工作。

此外，Treiber 的无锁堆栈可用于多消费者、多生产者上下文。假设一个线程正在调用 push()，第二个线程正在调用 pop()，第三个线程通过 is_empty() 观察堆栈的状态>。如果没有 Acquire 内存顺序，第三个线程无法保证观察到推送或弹出线程观察到的相同状态。