7. Memory Pool #2

ABA Problem이라는 것이 있다. CAS(Compare And Swap)에서 오류를 감지하지 못하는 것인데 쉽게 예시를 설명하자면 이렇다.

 

10 -> 20 -> 30 과 같이 리스트로 연결된 데이터가 있다고 하자.

A 스레드가 CAS를 이용하여 제일 앞의 10을 40으로 바꾼다고 해보자. 그렇다면 10 -> 20 -> 30이라는 리스트를 저장 후 '만약 제일 앞의 데이터가 10이면 40으로 바꾸어라' 이렇게 작동할 것이다.

 

하지만 멀티스레드 환경에서 CAS를 실행하기 전 다른 여러 스레드에서 pop 2번이 일어나 10과 20의 메모리가 반환 되고, push 1번 일어나서 10이라는 메모리를 재활용해 다시 할당 받았다고 가정하여 10 -> 30이 되었다고 생각해보자.

 

그렇게 되면 제일 앞의 데이터는 10이 맞으므로 CAS는 정상적으로 수행이 될 것이다. 하지만 A 스레드는 데이터 구조가 40 -> 20 -> 30이라고 알고 있기 때문에 이미 반환되어 유효하지 않은 20이라는 메모리에 접근을 시도하는 오류가 생기게 된다.

 

해결방법은 생각보다 단순하다. push와 pop을 할 때마다 계속 증가하는 변수 1개와 push할 때 증가, pop할 때 감소하는 변수 1개 총 2개를 두어 CAS에서 함께 비교하는 것이다. 그럼 도대체 코드를 어떻게 작성해야 하나 할 수 있지만 마이크로소프트에서 제공하는 구조체와 함수가 이미 있다.

 

Main.cpp

#include "pch.h"
#include "CorePch.h"
#include <Windows.h>
#include "ThreadManager.h"
#include "RefCounting.h"
#include "Memory.h"
#include "Allocator.h"

class Data
{
public:
	SLIST_ENTRY _entry;

	int32 data = rand() % 100;
};

SLIST_HEADER* _header;

int main()
{
	_header = new SLIST_HEADER();

	InitializeSListHead(_header);

	for (int32 i = 0; i < 3; i++)
	{
		GThreadManager->Launch([]()
			{
				while (true)
				{
					Data* data = new Data();

					InterlockedPushEntrySList(_header, (SLIST_ENTRY*)data);

					this_thread::sleep_for(10ms);
				}
			});
	}

	for (int32 i = 0; i < 2; i++)
	{
		GThreadManager->Launch([]()
			{
				while (true)
				{
					Data* data = nullptr;
					data = (Data*)InterlockedPopEntrySList(_header);

					if (data)
					{
						cout << data->data << endl;
					}
					else
					{
						cout << "NONE" << endl;
					}

					this_thread::sleep_for(10ms);
				}
			});
	}

	GThreadManager->Join();
}

처음보는 것들이 몇 개 있을 것이다.

 

SLIST_ENTRY : 일반적인 자료구조에서 노드를 생성하고 데이터를 넣은 후 해당 노드는 다음 노드를 가르키는 식으로 구조가 만들어져 있다. 근데 생각해보면 우리는 결국 데이터를 생성하고 싶은데 이를 위해서 노드를 생성하는 과정을 반드시 거쳐야 한다. 여기서 조금 더 좋은 방법이 있는데 데이터에 노드에 관련된 부분을 넣는 것이다.

 

위 코드를 보면 데이터의 가장 첫 맴버로 SLIST_ENTRY가 있는 것을 알 수 있다. 이것이 바로 노드에서 next의 역할을 하는 것이다. (반드시 첫 번째 맴버여야 한다!! 이것을 이용해 해당 객체의 주소를 찾기 때문)

 

단점이라고 한다면 노드는 모든 자료구조에 대해 템플릿으로 간편하게 만들 수 있지만 SLIST_ENTRY는 데이터 구조를 만들 때 넣어야 하므로 이미 잘 만들어진 외부의 클래스에 대해선 사용할 수 없다.

 

SLIST_HEADER : 우리가 일반적인 스택이나 큐 등 자료구조를 사용할 때 head를 놓고 사용하는데 그냥 그 역할이다.

 

InitializeSListHead : head를 초기화하는 함수다.

 

InterlockedPushEntrySList

InterlockedPopEntrySList

이름에서 알 수 있드시 push와 pop을 담당하는 함수다.

 

위 구조체에 F12를 타고 들어가보면 DECLSPEC_ALIGN(16)라고 적힌 부분이 있을 것이다. 10진수로 16, 2진수로 1'0000 즉 하위 4비트를 0000으로 정렬하라는 것이다. 쉽게 말해 주소의 하위 4비트가 반드시 0000이라는 것이다. 굳이 왜 정렬을 해야할까 싶지만 Push, Pop 등 내부 함수에서 주소를 4비트 시프트하여 사용하기 때문이다. 이렇게 확보한 4비트는 필요한 경우 다른 정보를 전달하는데 사용할 수도 있다.

 

MemoryPool.h

#pragma once

enum
{
	SLIST_ALIGNMENT = 16
};

//-----------------
//  MemoryHeader
//-----------------

DECLSPEC_ALIGN(SLIST_ALIGNMENT)
struct MemoryHeader : public SLIST_ENTRY
{
	// [MemoryHeader][Memory]
	MemoryHeader(int32 size) : allocSize(size) {}

	static void* AttachHeader(MemoryHeader* header, int32 size)
	{
		new(header)MemoryHeader(size); // placement new

		return reinterpret_cast<void*>(++header);
	}

	static MemoryHeader* DetachHeader(void* ptr)
	{
		MemoryHeader* header = reinterpret_cast<MemoryHeader*>(ptr) - 1;

		return header;
	}

	int32 allocSize;
	// TODO : 필요 추가 정보
};

//---------------
//  MemoryPool
//---------------

DECLSPEC_ALIGN(SLIST_ALIGNMENT)
class MemoryPool
{
public:
	MemoryPool(int32 allocSize);
	~MemoryPool();

	void		Push(MemoryHeader* ptr);
	MemoryHeader*	Pop();

private:
	SLIST_HEADER	_header;
	int32		_allocSize = 0;
	atomic<int32>	_allocCount = 0;
};

MemoryPool.cpp

#include "pch.h"
#include "MemoryPool.h"

//---------------
//  MemoryPool
//---------------

MemoryPool::MemoryPool(int32 allocSize) : _allocSize(allocSize)
{
	::InitializeSListHead(&_header);
}

MemoryPool::~MemoryPool()
{
	while (MemoryHeader* memory = static_cast<MemoryHeader*>(::InterlockedPopEntrySList(&_header)))
	{
		::_aligned_free(memory);
	}
}

void MemoryPool::Push(MemoryHeader* ptr)
{
	ptr->allocSize = 0;

	// Pool에 메모리 반납
	::InterlockedPushEntrySList(&_header, static_cast<PSLIST_ENTRY>(ptr));

	_allocCount.fetch_sub(1);
}

MemoryHeader* MemoryPool::Pop()
{
	MemoryHeader* memory = static_cast<MemoryHeader*>(::InterlockedPopEntrySList(&_header));

	// 없으면 새로 만듦
	if (memory == nullptr)
	{
		memory = reinterpret_cast<MemoryHeader*>(::_aligned_malloc(_allocSize, SLIST_ALIGNMENT));
	}
	else
	{
		ASSERT_CRASH(memory->allocSize == 0);
	}

	_allocCount.fetch_add(1);

	return memory;
}

원래 큐를 사용하여 구현하였던 메모리 풀을 전부 수정해주었다. 16바이트 단위로 정렬해주어야 하기 때문에 _aligned_malloc, _aligned_free를 통해 할당하고 해제했다. 

 

Memory.cpp의 할당 부분도 위처럼 교체해주자.

 

Main.cpp

#include "pch.h"
#include "CorePch.h"
#include <Windows.h>
#include "ThreadManager.h"

#include "RefCounting.h"
#include "Memory.h"
#include "Allocator.h"

class Player
{
public:
	int32 _hp = 100;
};

int main()
{
	for (int32 i = 0; i < 5; i++)
	{
		GThreadManager->Launch([]()
			{
				while (true)
				{
					Player* player = Xnew<Player>();
					
					cout << player->_hp << endl;

					this_thread::sleep_for(10ms);

					Xdelete(player);
				}
			});
	}

	GThreadManager->Join();
}

전부 수정하고나니 코드가 단순해졌다. Xnew와 Xdelete는 메크로에서 PoolAllocator로 바꿔놓았기 때문에 이렇게만 바꾸어도 잘 실행되는 것을 볼 수 있다.