Lock free stack #2

이전 글 lock free stack에서 풀지 못한 메모리 누수현상을 해결해보자.

전체 코드는 아래와 같다.

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)
		{

		}

	}

	// 1) head를 읽는다.
	// 2) head->next 읽기
	// 3) head = head -> next
	// 4) 데이터 추출 반환
	// 5) 추출한 노드 삭제
	bool TryPop(T& value)
	{
		++_popCount;

		Node* oldHead = _head;

		while (oldHead && _head.compare_exchange_weak(oldHead, oldHead->next) == false)
		{

		}

		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)
			{
				// 끼어든 애가 없음 -> 삭제 진행
				// 이제와서 끼어들어도, 어차피 데이터는 분리해둔 상태~!
				DeleteNodes(node);
			}
			else if (node)
			{
				// 누가 끼어들었으니 다시 갖다 놓자
				ChainPendingNodeList(node);
			}

			// 내 데이터는 삭제
			delete oldHead;
		}
		else
		{
			// 누가 있네? 그럼 지금 삭제하지 않고, 삭제 예약만
			ChainPendingNode(oldHead);
			--_popCount;
		}
	}

	void ChainPendingNodeList(Node* first, Node* last)
	{
		last->next = _pendingList;

		while (_pendingList.compare_exchange_weak(last->next, first) == false)
		{

		}
	}

	void ChainPendingNodeList(Node* node)
	{
		Node* last = node;
		while (last->next)
			last = last->next;

		ChainPendingNodeList(node, last);
	}

	void ChainPendingNode(Node* node)
	{
		ChainPendingNodeList(node, node);
	}

	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; // 삭제 되어야 할 노드들 (첫 번째 노드)
};

 

새로 추가한 멤버변수 _popCount와 _pendingList가 있다. _popCount는 TryPop을 실행하는 쓰레드의 개수를 저장한다. _pendingList는 삭제해야할 노드정보를 저장한다.

 

TryDelete에서 _popCount가 1이면 현재 노드는 삭제가능하다. 하지만 _pendingList를 모두 삭제할 수 없다. 그 사이 다른 쓰레드가 _pendingList에 접근할 수 있기 때문이다.

 

if (_popCount == 1)
{
    // 나 혼자네?

    // 이왕 혼자인거, 삭제 예약된 다른 데이터들도 삭제해보자
    Node* node = _pendingList.exchange(nullptr);
    if (--_popCount == 0)
    {
        // 끼어든 애가 없음 -> 삭제 진행
        // 이제와서 끼어들어도, 어차피 데이터는 분리해둔 상태~!
        DeleteNodes(node);
    }
    else if (node)
    {
        // 누가 끼어들었으니 다시 갖다 놓자
        ChainPendingNodeList(node);
    }

    // 내 데이터는 삭제
    delete oldHead;
}

 

_pendingList에서 정보를 분리한 뒤에도 쓰레드가 나 혼자이면 이제 모든 삭제할 노드를 삭제할 수 있다.

static void DeleteNodes(Node* node)
{
    while (node)
    {
        Node* next = node->next;
        delete node;
        node = next;
    }
}

그러나 쓰레드가 중간에 들어와 tryPop을 시도하였다면 _pendingList를 다시 복구한다.

CAS연산을 하여 지우려한 node의 마지막 노드의 next노드를 pendingList가 가리키게 만들고  pendingList가 지우려한 node의 첫 번째 node를 가리키게 만든다.

void ChainPendingNodeList(Node* first, Node* last)
{
    last->next = _pendingList;

    while (_pendingList.compare_exchange_weak(last->next, first) == false)
    {

    }
}

void ChainPendingNodeList(Node* node)
{
    Node* last = node;
    while (last->next)
        last = last->next;

    ChainPendingNodeList(node, last);
}

만약 trydelete 시점에 여러 쓰레드가 pop을 시도했다면 node를 지우지 않고 예약만 해둔다.

 

참조 : [C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part4: 게임 서버 - 인프런 | 강의 (inflearn.com)