9. 락프리 스택의 ABA 문제

// ============================================================================
// 시나리오
// ----------------------------------------------------------------------------
// 게임서버의 락프리 오브젝트 풀이다. 자주 빌리고 반납하는 작은 노드
// (예: 투사체/이펙트 핸들)를 위해, 프리리스트를 "락프리 스택"으로 구현했다.
//  - Push(반납), Pop(대여) 모두 head 참조를 Interlocked.CompareExchange 로 갱신한다.
//  - 여러 스레드(워커들)가 동시에 빌리고 반납한다.
//
// 운영 중 증상(드물고 비결정적, 재현 어려움):
//  - 아주 가끔 Pop 이 "이미 다른 스레드가 가져간 노드"를 또 반환하거나,
//    프리리스트의 중간 노드들이 통째로 사라진다(노드 유실).
//  - 가끔 같은 노드가 두 스레드에 동시 대여되어 상태가 깨진다.
//  - 부하가 높고 빌림/반납이 격렬할수록 빈도가 증가.
//
// 요구사항
// ----------------------------------------------------------------------------
//  - 락 없이 동시 Push/Pop 이 안전해야 한다.
//  - 같은 노드가 두 스레드에 동시에 대여되면 안 된다.
//  - 프리리스트 무결성(노드 유실/중복 없음)이 유지돼야 한다.
//
// 과제
// ----------------------------------------------------------------------------
// 이 코드를 코드리뷰하라.
//  1) 어떤 고전적 락프리 결함이 있는가? 정확한 이름과 발생 시퀀스를 설명하라.
//  2) (A)(B)(C) 각 지점이 그 결함에 어떻게 기여하는가?
//  3) 그 결함을 막도록 수정하라(여러 기법과 트레이드오프).
// ============================================================================

using System.Threading;

namespace LockFreePool
{
    public sealed class Node<T>
    {
        public T Value;
        public Node<T> Next;
    }

    public sealed class LockFreeStack<T>
    {
        private Node<T> _head; // 워커들이 CAS 로 갱신

        // 반납: 노드를 스택 맨 위에 올림
        public void Push(Node<T> n)
        {
            Node<T> oldHead;
            do
            {
                oldHead = _head;
                n.Next = oldHead;                       // (A)
            }
            while (Interlocked.CompareExchange(ref _head, n, oldHead) != oldHead);
        }

        // 대여: 맨 위 노드를 떼어 반환
        public Node<T> Pop()
        {
            // (B) oldHead 를 보고, 그 Next 를 읽어 새 head 후보로 삼는다
            Node<T> oldHead = _head;
            while (oldHead != null)
            {
                Node<T> next = oldHead.Next;            // (C) oldHead 역참조
                if (Interlocked.CompareExchange(ref _head, next, oldHead) == oldHead)
                    return oldHead;                     // 성공: 이 노드를 대여
                // 실패: head 가 갱신됨 → 다시 읽고 재시도
                oldHead = _head;
            }
            return null;
        }
    }

    // ---- 데모: 동시에 빌리고 반납 (개념용) ----
    public static class Demo
    {
        public static void Run()
        {
            var stack = new LockFreeStack<int>();

            // 초기 노드 채우기 (고정 풀처럼 재사용)
            const int N = 1000;
            var storage = new Node<int>[N];
            for (int i = 0; i < N; i++)
            {
                storage[i] = new Node<int> { Value = i };
                stack.Push(storage[i]);
            }

            long popped = 0;
            void Worker()
            {
                for (int k = 0; k < 100_000; k++)
                {
                    var n = stack.Pop();
                    if (n != null)
                    {
                        // 잠깐 쓰고 즉시 반납
                        n.Value ^= 1;
                        stack.Push(n);
                        Interlocked.Increment(ref popped);
                    }
                }
            }

            var ts = new Thread[8];
            for (int i = 0; i < 8; i++) { ts[i] = new Thread(Worker); ts[i].Start(); }
            foreach (var t in ts) t.Join();

            System.Console.WriteLine($"popped={popped}");
        }
    }
}