3. 락프리 스택의 문제 추론 (문제점 정리와 사고실험, 로깅)

---

이전 테스트의 문제점 정리

 

Java 예제코드를 c++로 포팅하여 구현한 락프리 스택을 테스트해 본 결과 다음과 같은 문제점이 발생했다.

1. N회 push한 뒤, N회 pop을 하였으나 pop에 실패했다. (= popNode 가 nullptr이 되었다.)

2. pop 과정에서 node를 반환하는 과정에서 힙이 손상되었다는 런타임 에러가 발생했다.

3. pop한 결과에 중복된 값이 포함되어 있다.

 

이 문제점을 대상으로 추론 및 사고실험을 진행한다.

atomic 보다는 interlocked 쪽이 조금 더 동작을 하나씩 뜯기도 쉽고, 기존 둘중 한가지만 알고 있다면 interlocked만 이해한 채로 atomic을 보는 것 보다 atomic만 이해한채로 interlocked를 보는 것이 더 쉽기 때문에 interlocked를 이용해 설명을 진행한다.

 

InterlockedCompareExchangePointer 함수(wdm.h) - Windows drivers

 

---

1번 문제

 

popNode가 null이 된다는 것은 push 횟수보다 많은 pop이 발생하였거나. 모종의 이유로 push 된 노드가 제대로 연결되지 못하였다는 의미이다. push 단계에서 문제가 발생하였을 수 있고, pop 단계에서 문제가 발생하였을 수 도 있다. push와 pop 단계를 나누어 생각해 본다.

 

 

push 과정의 시나리오는 다음과 같다.

1. push 할 값을 얻은 뒤 새로운 newNode를 할당받아 세팅한다.
2. 현재 stack의 top인 oldTop을 얻는다.
3. newNode의 next에 oldTop의 값을 넣는다.
4. 현재 stack의 top과 oldTop이 같다면 현재 stack의 top을 newNode로 바꾼다.

		void push(T v)
		{
			node<T>* newNode = new node<T>(v); //[1]
			node<T>* oldTop;

			while (true)
			{
				oldTop = top; //[2]
				newNode->next = oldTop; //[3]

				if (InterlockedCompareExchangePointer((PVOID*)&top, newNode, oldTop) == oldTop) //[4]
				{
					InterlockedIncrement(&_size);
					break;
				}

			}
		}

 

이 상황에서 문제가 발생할 여지가 있는 단계는 2, 4 단계이다.

A. 2단계 에서 현재 stack의 top이 아닌 과거의 top, 또는 이상한 값을 획득했다.

B. 4단계에서 현재의 top을 저장한 oldTop과 CAS 시점의 top이 다른 top이지만 CAS를 통과했다.

C. 4단계에서 CAS를 통과했지만 oldTop이 이상한 값이었다.

D. 모종의 이유로 메모리가 변조되어 oldTop 또는 top이 바뀌었다. (우선은 배제)

 

 

A : 잘못된 top의 값을 얻은 A의 케이스는 일시적으로 잘못된 값을 얻었다고 하여도 현재의 top과 CAS 연산을 하는 시점에서 실패하여 발생 불가능하다.

 

B : oldTop과 비교시점의 top 다른 노드지만 CAS를 통과하는 케이스는 다음과 같은 특수한 상황에서 발생 가능하다.

(괄호 속 a는 노드의 주소값, v는 해당 노드가 담고 있는 값이다)

 

 

 

이 내용을 조금 더 쉽게 풀어 설명하면 아래와 같다.

 

 

 

C : 잘못된 값을 top에 넣는 C의 케이스는 A의 케이스와 마찬가지로 CAS 연산이 실패할 것이므로 불가능하다.

 

결국 같은 메모리가 재활용되어 다시 top으로 올라오는 경우에만 push에서 의도치 않은 동작이 발생할 수 있다.

그렇다면 재활용된 주소가 다시 top으로 온 경우가 궁극적으로 테스트의 1번 문제를 발생시킬 수 있을까? top의 값이 어떻게 바뀌었든, 현재 top의 주소가 CAS 직전에 확인한 top의 값과 같다면 newNode는 현재 top 위로 올라갈 것이다.

재활용된 주소가 현재의 top이 아니라면 CAS에 의해 걸러질 것이므로 CAS에 성공했다면 oldTop가 가르키는 노드의 value와 top이 가르키는 노드에 저장된 value의 일치 여부와 상관없이 newNode는 현재의 top 위에 올라가게 됨이 보장된다.

 

즉 push 단계에서는 문제 발생이 불가능하다.

 

 

그렇다면 pop 과정의 시나리오를 보자

1. 현재의 top을 oldTop에 저장한다.
2. popNode에 oldTop을 저장한다.
3. 현재의 top이 oldTop과 같다면 현재의 top을 popNode의 next로 변경한다.

		T pop()
		{
			node<T>* popNode;
			node<T>* oldTop;
			T ret;

			while (true)
			{
				oldTop = top; //[1]
				if (oldTop == nullptr)
					throw;

				popNode = oldTop; //[2]
				if (InterlockedCompareExchangePointer((PVOID*)&top, popNode->next, oldTop) == oldTop) //[3]
				{
					ret = popNode->value;
					InterlockedDecrement(&_size);
					break;
				}

			}

			delete popNode;
			return ret;
		}

 

pop 시나리오상 3번 단계에서 push와 마찬가지의 문제 발생 여지가 있다.

 

 

정확히 아래 캡처 위치에서 컨텍스트 스위칭이 발생하면, CAS 연산으로 넘길 매개변수는 과거의 top에 대한 정보가 레지스터로 올라간 이후 컨텍스트 스위칭이 발생하게 된다.

상태로 top이 재사용되어 oldTop과 같은 주소를 갖게 되면 CAS를 통과하게 된다. 그러면 갑자기 top이 이미 pop 된 노드인 0x0017 위치가 되어버린다.

 

 

push때와는 다르게 pop상황에서 메모리의 재사용으로 인한 문제는 스택의 순서를 꼬아버리는 문제를 야기한다.

 

---

2번 문제인 힙 손상 문제 또한 1번 문제와 동일한 원인에 의해 발생 가능하다. (1번 문제를 해결했을 때 2번 문제가 해결되리라는 보장은 없지만, 1번 문제가 있다면 2번 문제는 100% 발생한다. 같은 메모리를 2번 해제 시도하게 되기 때문이다.)

 

3번 문제인 중복되는 노드 문제 또한 스택의 구조 자체를 꼬아버리는 1번을 해결하지 않는다면 문제의 원인을 찾아가기 힘들다. 애초 스택의 구조가 꼬여버렸으므로 이미 pop 된 노드를 다시 pop 하게 되어 2번 문제도 발생하는 것 이기 때문에 3번 문제 또한 1번을 우선 해결한 뒤 다시 확인하도록 한다.

 

---

발생한 순간 포착

 

위의 사고실험 과정에서 논리적으로 문제가 발생 가능한 상황을 파악했다. 하지만 상상으로 찾은 가능성이 실제로 보고 싶다면 어떻게 해야 할까?

스택에 push / pop 되는 value를 메모리에 로깅한 방법처럼 push 되는 노드, pop 되는 노드의 주소까지 로깅한다면 뭔가 볼 수 있지 않을까?

 

다음과 같은 로깅용 구조체를 사용하기로 하였다.

struct LoggingStruct
{
	unsigned long long int seqNo;
	unsigned long long int pushPopValue;
	unsigned long long int pushNodePtr;
	unsigned long long int topPtr;
	unsigned long long int popNodePtr;
	unsigned long long int threadID;
};

code

GitHub - YoungWoo93/lockFreeStack-Queue-sample: 블로그 포스팅 내용과 연계

 

 

 

 

이렇게 얻어낸 로깅 데이터를 엑셀로 다음과 같이 분류하였다

 

push와 pop이 진행되며 각 노드와 top의 값을 추적할 수 있게 되었다

 

그 결과 우리가 논리로만 추론했던 실제 top의 next가 꼬여있는 장면을 볼 수 있었다.

같은 노드가 2번 pop된 현장

lockFreeStack_test_2.xlsx

2.66MB

 

---

이러한 문제를 ABA 문제라고 부르며 이는 이미 잘 알려진 문제이다. 하지만 이 글에서는 ABA 문제를 논리적으로 생각할 수 있고, 그 증거를 찾을 수 있다는 것을 적고 싶었다.

 

다음 포스팅에서는 이 ABA를 문제와 자잘한 버그들을 수정하고자 한다.