[C++/Game Server] Lock-Free Stack (with PopCount, PendingList)

Lock-Free Stack with PopCount

• Lock 없이 스택 구현
• lock-free 라도 완전히 대기를 안 할 순 없음 (Atomic 변수, CAS 함수 사용)
  • DeadLock이 아닌 LiveLock 비슷한 상황이 발생할 수 있음
    • 데드락 (Deadlock): 모두가 잠들어서 아무도 움직이지 않음. (진행도 0, CPU 0%)
    • 라이브락 (Livelock): 모두가 미친 듯이 제자리걸음을 하고 있음. (진행도 0, CPU 100%)
    • 사실상 Lock-Free를 사용했기 때문에 LiveLock이 일어날 순 없지만 각각의 스레드 입장에서 Starvation이 심해지면 LiveLock처럼 느껴질 수 있음

template<typename T>
class LockFreeStack
{
	struct Node {
		Node(const T& value) : data(value), next(nullptr) {}

		T data;
		Node* next;
	};
public:
	void Push(const T& value)
	{
		Node* node = new Node(value);
		node->next = _head;

		while (_head.compare_exchange_weak(node->next, node) == false) 
		{
			//node->next = _head; // 함수 안에서 자동으로 실행됨 (이 값이 바뀌었으니까 다시 알려줄게)
		} 
	}

	// 1) head 읽기
	// 2) head->next 읽기
	// 3) head = head->next
	// 4) data 추출해서 반환
	// 5) 추출한 노드를 삭제
	bool TryPop(T& value) 
	{
		++_popCount;
		Node* oldHead = _head;

		while (oldHead && _head.compare_exchange_weak(oldHead, oldHead->next) == false)
		{
			// oldHead=_head;
		}
		if (oldHead == nullptr) {
			--_popCount;
			return false;
		}

		value = oldHead->data;
		TryDelete(oldHead);
		
		return true;
	}

	// 1) 데이터 분리
	// 2) Count 체크
	// 3) 나 혼자면 삭제
	void TryDelete(Node* oldHead)
	{
		// 나 외에 누가 있는지
		if (_popCount == 1)
		{
			// 나 혼자임

			// 이왕 혼자인거, 삭제 예약된 다른 데이터들도 삭제
			Node* node = _pendingList.exchange(nullptr);

			if (--_popCount == 0) // ********************************
			{
				// if문 이후로 끼어든 애가 없음 >> 삭제 진행
				// 이제와서 끼어들어도, 데이터는 이미 분리해둔 상태
				DeleteNodes(node);
			}
			else if(node)
			{
				// 누가 끼어들었으니 다시 갖다 놓기
				ChainPendingNodeList(node);
			}

			// 내 데이터는 삭제
			delete oldHead;
		}
		else
		{
			// 누가 있네
			// 지금 당장 삭제하지 않고 pendingList에 넣어주기
			ChainPendingNode(oldHead);
			--_popCount;
		}
	}

	// nullptr을 넣어놨지만, 그새 다른 스레드가 pendingList에 node를 추가했을 수 있음
	// 내 스레드가 가지고 있는 pendingList 뒤에 넣어주고 CAS로 합친 List를 pendingList로 교체
	void ChainPendingNodeList(Node* first, Node* last)
	{
		last->next = _pendingList;
		
		while(_pendingList.compare_exchange_weak(last->next, first)==false)
		{
			//last->next = _pendingList;
		}
	}

	// pendingList의 first와 last를 구분하여 ChainPendingNodeList로 보내줌
	void ChainPendingNodeList(Node* node)
	{
		Node* last = node;
		while (last->next)
		{
			last = last->next;
		}
		ChainPendingNodeList(node, last);
	}

	// 기존 pendingList의 head로 node를 넣어주기 위함
	void ChainPendingNode(Node* node)
	{
		ChainPendingNodeList(node, node);
	}

	// pendingList를 탐색하며 delete 진행
	static void DeleteNodes(Node* node)
	{
		while (node)
		{
			Node* next = node->next;
			delete node;
			node = next;
		}
	}

private:
	atomic<Node*> _head;
	
	atomic<uint32> _popCount = 0; // Pop을 실행중인 쓰레드 개수
	atomic<Node*> _pendingList; // 삭제 되어야 할 노드들의 head (첫번째 노드)
};

 

"if(--_popCount == 0)" 과연 필요할까?

• (// **********************)로 체크한 부분
• 구조적으로 다른 스레드가 Pop에 접근한다고 해도 본 스레드가 _popCount를 증가시켜 놓은 상태이기 때문에 _pendingList에 있는 node들에 접근하지 못함
  • if(--_popCount==0)이 없더라도 다른 스레드들이 들어와서 pop을 한다고 해도 UAF 없이 delete가 가능한 거 아닌가?

• 재배치/가시성 문제로 Node* oldHead = _head 가 _popCount++ 보다 먼저 실행될 때, delete로 인해 UAF가 발생할 수 있다는 말

• 하지만, 현재 _popCount를 atomic 변수로 선언했으며 seq_cst(기본)라서 컴파일러가 마음대로 재배치할 수 없으므로 재배치/가시성 문제가 발생할 수 없음
  • memory_order_seq_cst가 아닌 memory_order_relaxed로 바뀐다면 재배치로 인해 문제가 발생할 수 있음

• 결국 중복되지만 Pop중인 스레드가 나밖에 없을 때만 free(delete) 하기 위한 안전 조건이라는 것
  • 나중에 코드 최적화등을 대비한 것이지 없어도 된다는 뜻
• 그렇다면 괜히 다른 스레드가 pop을 한다는 사실만으로 DeleteNodes를 진행하지 않고, ChainPendingNodeList(node)를 해서 성능을 낭비하는 건 아닌지?

• 경쟁이 심할수록 delete의 비용이 커지기 때문에, 성능은 별 차이가 없다고 함
• 그렇다면 pendingList에 모아놨다가 스레드 경쟁이 거의 없을 때 한 번에 delete 하는 로직이 효율적이지 않나?

• 대체로 그렇지만 때에 따라 다르다고 함
• 와 thread 재밌다 스트레스 많이 받는다 도움 많이 될 거야