crossbeam ebr + michael scott queue의 버그 확인

[jeehoonkang]

https://github.com/crossbeam-rs/crossbeam/issues/238 이거 혹시 생각해보고, (1) three-epoch, (2) pebr에서 여전히 나타날 문제인지 생각해봐줄래요? 참고로 이건 crossbeam ebr + michael scott queue의 버그입니다.

[tomtomjhj]

MSQueue가 pebr페이퍼의 requirement 2.1을 위반하는 거 아닌가요?

[jeehoonkang]

그렇다고 ms queue가 틀렸다고 결론내리기엔 ms queue가 너무 중요한 application입니다. 어떻게 조건을 relax하고 구현을 고쳐야 ms queue를 지원할 수 있을지 고민해주시기 부탁드립니다!

[tomtomjhj]

일단 three-epoch을 적용하지 않는다고 가정하고, head가 tail을 추월하는 건 최대 1칸이니까 pop이 head를 바로 defer_destroy를 하는 대신에 이런식으로 한번 기다렸다가 defer_destroy를 하는 건 어떨까요?

pub struct Queue<T> {
    head: CachePadded<Atomic<Node<T>>>,
    tail: CachePadded<Atomic<Node<T>>>,
    deferred: AtomicUsize, // 원래 pop이 defer_destroy하려했던 Shared의 data. init to 0
}

fn pop_internal(&self, guard: &Guard) -> Result<Option<T>, ()> {
    let head = self.head.load(Acquire, guard);
    let h = unsafe { head.deref() };
    let next = h.next.load(Acquire, guard);
    match unsafe { next.as_ref() } {
        Some(n) => unsafe {
            self.head
                .compare_and_set(head, next, Release, guard)
                .map(|_| {
                    // guard.defer_destroy(head);
                    let deferred = self.deferred.load();
                    if self.deferred.compare_exchange(deferred, head.into_usize()).is_ok() {
                        // can safely defer_destroy since self.tail cannot point to
                        // `Shared::from_usize(deferred)`
                        if deferred != 0 {
                            guard.defer_destroy(Shared::from_usize(deferred));
                        }
                    }
                    Some(ManuallyDrop::into_inner(ptr::read(&n.data)))
                })
                .map_err(|_| ())
        },
        None => Ok(None),
    }
}