[C++/Game Server] Lock-Free Stack (with Smart Pointer, Reference Counting)

Lock-Free Stack with Smart Pointer

• Garbage Collector의 기능을 스마트 포인터로 대체하는 방법
• 사실 스마트 포인터가 내부적으로 lock을 사용하기 때문에 엄밀히 말해서 Lock-Free 방식은 아님
  • shared_ptr<int> ptr;
    atomic_is_lock_free(&ptr); 로 CPU가 lock을 사용하는지 검사해 보면 false 나옴

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

		shared_ptr<T> data;
		shared_ptr<Node> next;
	};
public:
	void Push(const T& value)
	{
		shared_ptr<Node> node = make_shared<Node>(value);
		node->next = std::atomic_load(&_head);

		while (std::atomic_compare_exchange_weak(&_head, &node->next, node) == false) // 기능은 똑같은데 C언어 스타일의 전역 함수
		{
			//node->next = _head; // 함수 안에서 자동으로 실행됨 (이 값이 바뀌었으니까 다시 알려줄게)
		} 
	}
	
	shared_ptr<T> TryPop() 
	{
		shared_ptr<Node> oldHead = std::atomic_load(&_head);

		while (oldHead && std::atomic_compare_exchange_weak(&_head, &oldHead, oldHead->next) == false) 
		{

		}

		if (oldHead == nullptr)
			return shared_ptr<T>();
		
		return oldHead->data;

	}

private:
	shared_ptr<Node> _head;
	
};

 

Lock-Free Stack with Reference Counting

• 이중 참조 횟수 기록(Split Reference Counting) 기법을 활용한 Lock-Free Stack
• 단순히 head 포인터만 CAS로 바꾸는 방식이 아니라, 메모리 해제 시점의 안정성을 확보하기 위해 외부 참조 횟수(External Count)와 내부 참조 횟수(Internal Count)를 나누어 관리하는 것이 핵심임
  • CountedNodePtr(외부 참조 함수): head에 직접 붙어 있는 참조 횟수로, 현재 이 Node가 head로서 얼마나 많은 스레드에 의해 읽히고(참조되고) 있는가를 나타냄
    • IncreaseHeadCount() 함수에서 노드에 접근하기 전에 일단 externalCount를 1 올리고 시작하는 것은 "내가 지금 이 노드를 보고 있으니 아무도 지우지 마!"라고 선언하는 것과 같음
  • internalCount(내부 참조 횟수): Node 구조체 안에 위치한 참조 횟수로, "노드가 head에서 떨어져 나온 뒤, 아직 이 노드를 붙잡고 남은(참조권은 얻었지만 소유권은 얻지 못한) 스레드가 몇 개인가"를 나타냄
    • Trypop에서 소유권 획득에 성공한 스레드는 externalCount에서 자신이 점유했던 몫을 빼고, 그 나머지를 internalCount에 더해줌
  • 삭제 조건: $externalCount + internalCount = 0$
    • fetch_add의 결괏값이 특정 조건(-countIncrease)과 일치할 때 delete ptr;을 수행하여 마지막으로 노드를 나가는 스레드가 청소를 담당하게 설계하였음

template<typename T>
class LockFreeStack
{
	struct Node;
	struct CountedNodePtr
	{
		int32 externalCount = 0; // 32bit
		Node* ptr = nullptr; // 64bit
		// 구조체를 64bit 크기로 맞춰서 lock-free가 되게끔 조절하는 꼼수가 필요함
		// lock-free가 된다고 가정하고 코드를 작성
	};

	struct Node {
		Node(const T& value) : data(make_shared<T>(value))
		{
		
		}

		shared_ptr<T> data;
		atomic<int32> internalCount = 0;
		CountedNodePtr next;
	};
public:
	void Push(const T& value)
	{
		CountedNodePtr node;
		node.ptr = new Node(value);
		node.externalCount = 1;
		node.ptr->next = _head;

		while (_head.compare_exchange_weak(node.ptr->next, node) == false)
		{

		}
	}

	shared_ptr<T> TryPop()
	{
		CountedNodePtr oldHead = _head;

		while (1)
		{
			// 참조권 획득 (externalCount를 현 시점 기준 +1한 스레드가 이김)
			IncreaseHeadCount(oldHead);
			// 최소 externalCount >= 2 일테니 삭제 X (안전하게 접근 가능 상태)
			Node* ptr = oldHead.ptr;

			if (ptr == nullptr)return shared_ptr<T>();

			// 소유권 획득 (head를 ptr->next로 바꿔치긱 한 애가 이김 == externalCount까지 똑같아야 함)
			if (_head.compare_exchange_strong(oldHead, ptr->next))
			{
				shared_ptr<T> res;
				res.swap(ptr->data);

				// external : 1
				// internal : 0

				// 나 말고 또 누가 있는가?
				const int32 countIncrease = oldHead.externalCount - 2;

				// fetch_add는 더해주고 이전의 값을 뱉어줌 a++ 같은 거
				if (ptr->internalCount.fetch_add(countIncrease) == -countIncrease)
					delete ptr;

				return res;
			}
			// 소유권 획득에 실패한 스레드중 마지막 스레드가 나가기 전에 delete 실행
			else if (ptr->internalCount.fetch_sub(1) == 1)
			{
				// 참조권은 얻었으나, 소유권은 실패 -> 뒷수습 직접 진행
				delete ptr;

			}

		}
	}

private:

	void IncreaseHeadCount(CountedNodePtr& oldCounter)
	{
		// Speen Lock 느낌으로 참조할 권리 다들 획득 시도 중
		while (1)
		{
			CountedNodePtr newCounter = oldCounter;
			newCounter.externalCount++;
			// externalCount를 1 증가 시켜서 head로 넣으려고 시도
			if (_head.compare_exchange_strong(oldCounter, newCounter))
			{
				oldCounter.externalCount = newCounter.externalCount; // 증가된 externalCount를 oldHead에도 저장 후 탈출
				break;
			}
		}
	}


private:
	atomic<CountedNodePtr> _head;
	// 진짜 lock-free인지? is_lock_free로 봐봐야 함

};

 

• 어렵다.. lock-free queue는 더 어렵다는데 나중에 공부해야겠다