Memory Pool

본 포스팅은 인프런에 등록되어 있는 Rockiss 님의 강의를 보고 간단하게 정리한 글입니다.

---

Memory Pooling

 

메모리 공간을 특정 크기를 가진 여러 공간으로 나누어 미리 할당을 해 놓고 어떤 타입을 생성하거나 소멸시에 이 미리 할당된 공간을 활용하는 방법이다.

 

단순히 new/delete를 할때마다 kernel 레벨로 가서 직접 메모리 할당/해제를 요청하면 성능 저하가 일어날 수 있고, 메모리 단편화 (메모리가 해제되어 사용가능한 공간이 남아있는데도 불구하고 남은 공간이 연속적이지 않아 메모리 할당을 할 수 없는 문제)을 초래할 수 있다.

 

따라서 사용되지 않는 메모리 공간이 계속 할당되고 있는 상태이므로 메모리 할당/해제가 빈번히 일어날 경우에 사용하면 좋다.

 

Stomp Allocator and Memory Pooling ?

 

Stomp Allocator는 더 이상 메모리를 사용하지 않을 때 실제로 메모리가 해제되지만, Memory Pooling은 이미 할당되어 있는 메모리 공간 중 일부를 어떤 타입에 대해 빌려주었다가 회수하는 방식이라는 차이가 있다.

---

구현 전략

 

Pool로 사용할 메모리 공간을 할당을 받고, 참조할 구역을 나눈다.

 

나눈 공간을 크기에 맞게 링크시킨 후(연결 시킨 후), 처음 가리킬 공간에 header를 두어 가리키게 한다.

 

최대 풀의 크기를 4096바이트로 두고 이 보다 큰 할당이 필요한 경우에는 Stomp Allocator를 이용해 직접 할당을 한다.

 

할당/해제 시에는 헤더 포인터를 가진 Linked List와 비슷하다.

메모리 할당 시: 헤더 포인터가 가리키는 블록을 반환하고, 원래 그 블록이 가리키고 있던 블록을 헤더 포인터에 다시 연결을 해준다.

메모리 해제 시: 해제된 블록을 헤더 포인터가 가리키게 하고 헤더 포인터가 원래 가리키던 블록이 해제된 블록을 가리키게 한다. (사이에 끼워서 다시 연결)

 

추가적으로, LinkedList 처럼 사용 할 것이지만 멀티 쓰레드 환경에서 문제없이 작동이 되어야 하기 때문에 MS에서 제공하는 SList를 이용한다.

 

그 이유는 메모리 풀에 메모리를반환하거나 할당할 시에 다른 쓰레드가 그 중간에 개입을 해서 헤더 포인터가 엉뚱한 공간을 가리키게 하여 구조가 꼬여버릴 수 있기 때문이다.

 

그러면 단순히 lock으로 compare and swap을 이용하면 되지 않냐? (여기서는 interlockedCompareExchange)

 

맞긴하다. 하지만 어떤 쓰레드에서 compare and swap 과정에, 다른 쓰레드가 메모리풀로부터 메모리를 할당 받고 그 메모리를 다시 반납, 그리고 같은 포인터로 다시 할당을 받는다고 한다면 결과적으로 헤더 포인터가 엉뚱한 공간을 가리키게 된다. (ABA Problem)

 

좀 더 자세히 살펴보자.

 

기억해야할 것은 compare and swap은 주소값을 비교한다는 것이다.

 

(Compare and swap 에서 현재 X라는 값이 A이고 무한 루프를 돌면서 X가 여전히 A일 때 X에 B를 넣게 되는 구조이다. 여기서 X 값에 대해 다른쓰레드에서 B를 넣어주었다가 다시 A를 넣을 수 있는 상황이 생긴다. 그러나 나중에 넣어진 A는 기존에 있던 A가 아니다. 즉, 같은 포인터를 가지고 있지만 같은 노드(공간)이 아니라는 것이다.

 

이 문제를 해결하기 위해, 헤더 포인터에 추가 적인 정보를 넣는데 이 것이 SListHeader이다.

PSLIST_HEADER를 실제로 살펴보면 단순히 포인터 값 외에도 추가적인 정보가 더 있다.

 

depth와 sequence로 루프 돌 때마다 값을 추가해주고 비교시에 이 값까지 비교 한다면 기존 A와 나중에 들어온 A를 구별할 수 있다.

메모리 구조상 16, 48, 4, 60으로 비트, 즉 16바이트로 고정시켜놓았기 때문에 위에서 반드시 16바이트로 해주어야 한다는 이유가 이것 때문이다.

 

(ULONGLONG 값이 unsinged long long 인데 이 값을 한바퀴 다 돌면 어떻할 거냐? -> 물론 오류가 발생하겠지만 depth와 sequence 모두 한 바퀴 돌고 일치할 확률은 없다고 바도 무방하다.)

typedef union DECLSPEC_ALIGN(16) _SLIST_HEADER {
    struct {  // original struct
        ULONGLONG Alignment;
        ULONGLONG Region;
    } DUMMYSTRUCTNAME;
    struct {  // x64 16-byte header
        ULONGLONG Depth:16;
        ULONGLONG Sequence:48;
        ULONGLONG Reserved:4;
        ULONGLONG NextEntry:60; // last 4 bits are always 0's
    } HeaderX64;
} SLIST_HEADER, *PSLIST_HEADER;

---

1. 메모리 풀 정의

 

SList 사용 위해서는 사용할 객체 구조를 16바이트로 고정시켜주어야 할 필요가 있다. (DECLSPEC_ALIGN 이용)

https://learn.microsoft.com/en-us/windows-hardware/drivers/kernel/eprocess

헤더를 이어주고 떼는 함수도 작성한다.

#pragma once

enum
{
	SLIST_ALIGNMENT = 16
};


// 객체를 만들때 앞에 메모리의 크기, 힙 주소등의 내용이 헤더에 들어감


// 메모리 구조상 상속받는 클래스가 메모리 앞에 오게된다.
// 즉, allocSize 보다 SLIST_ENTRY가 메모리 앞에 위치하게 된다.

DECLSPEC_ALIGN(SLIST_ALIGNMENT)
struct MemoryHeader : public SLIST_ENTRY
{
	// [MemoryHeader][Data] // 앞에 메모리헤더 놓기
	MemoryHeader(int size) : allocSize(size) {}

	static void* AttachHeader(MemoryHeader* header, int size)
	{
		new(header)MemoryHeader(size); // placement new
		// 메모리 헤더 크기만큼 건너뛰고(++) 메모리 시작 위치 반환 (data 부분부터)		
		return reinterpret_cast<void*>(++header);
	}

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

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


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

	void Push(MemoryHeader* ptr);
	MemoryHeader* Pop();
private:
	SLIST_HEADER _header; // 메모리 앞에 오도록!!!! 앞에다 선언하기
	int _allocSize = 0;
	atomic<int> _useCount = 0;
	atomic<int> _reserveCount = 0;
};

 

생성자에서는 InitializeSListHead()로 header를 초기화한다.

소멸자에서는 메모리풀에 할당되어 있떤 메모리를 실제로 모두 해제한다. (반복문을 통해 모든 공간의 메모리 해제)

 

Push는 메모리를 다시 메모리풀에 반환할 때 이용한다.

InterlockedPushEntrySList() 함수로 메모리를 반납하게 된다.

 

"MemoryPool.cpp"

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

MemoryPool::MemoryPool(int 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));

	_useCount.fetch_sub(1);
	_reserveCount.fetch_add(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);
		_reserveCount.fetch_sub(1);
	}
	_useCount.fetch_add(1);

	return memory;
}

 

 

2. 메모리에서 메모리풀 사용

 

4095 바이트의 공간을 사용하는데, 

1024까지는 32bit 단위로,

2048까지는 128bit 단위로,

4096까지는 256bit 단위로 사용한다.

 

Pool을 관리할 vector 방식 배열을 하나 만들어 주고, 메모리 크기로 메모리 풀을 바로 찾을 수 있게 할 poolTable이라는 배열을 하나 준비한다.

 

"Memory.h"

class MemoryPool;

class Memory
{
	enum
	{
		// ~1024까지 32단위,
		// ~2048까지 128단위,
		// ~4096까지 156단위
		POOL_COUNT = (1024 / 32) + (1024 / 128) + (2048 / 256),
		MAX_ALLOC_SIZE = 4096,
	};

public:
	Memory();
	~Memory();

	void* Allocate(int32 size);
	void Release(void* ptr);
private:
	vector<MemoryPool*> _pools;

	// 메모리 크기 <-> 메모리 풀
	// O(1) 로 빠르게 찾기 위한 테이블
	// 0-32
	MemoryPool* _poolTable[MAX_ALLOC_SIZE + 1];
};

 

"Memory.cpp"

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

Memory::Memory()
{
	int size = 0;
	int tableIndex = 0;

	// 참조 구역 나누기

	for (size = 32; size <= 1024; size += 32)
	{
		MemoryPool* pool = new MemoryPool(size);
		_pools.push_back(pool);

		while (tableIndex <= size)
		{
			_poolTable[tableIndex] = pool;
			tableIndex++;
		}
	}

	for (; size <= 2048; size += 128)
	{
		MemoryPool* pool = new MemoryPool(size);
		_pools.push_back(pool);

		while (tableIndex <= size)
		{
			_poolTable[tableIndex] = pool;
			tableIndex++;
		}
	}

	for (; size <= 4096; size += 256)
	{
		MemoryPool* pool = new MemoryPool(size);
		_pools.push_back(pool);

		while (tableIndex <= size)
		{
			_poolTable[tableIndex] = pool;
			tableIndex++;
		}
	}
}

Memory::~Memory()
{
	for (MemoryPool* pool : _pools)
	{
		delete pool;
	}

	_pools.clear();
}

void* Memory::Allocate(int size)
{
	MemoryHeader* header = nullptr;
	const int allocSize = size + sizeof(MemoryHeader);

	if (allocSize > MAX_ALLOC_SIZE)
	{
		// 메모리 풀링 최대 크기 벗어나면 일반 할당
		header = reinterpret_cast<MemoryHeader*>(::_aligned_malloc(allocSize, SLIST_ALIGNMENT));
	}
	else
	{
		// 메모리 풀에서 꺼내온다
		header = _poolTable[allocSize]->Pop();
	}

	return MemoryHeader::AttachHeader(header, allocSize);
}

void Memory::Release(void* ptr)
{
	MemoryHeader* header = MemoryHeader::DetachHeader(ptr);

	const int allocSize = header->allocSize;
	ASSERT_CRASH(allocSize > 0);

	if (allocSize > MAX_ALLOC_SIZE)
	{
		// 메모리 풀링 최대 크기를 벗어나면 일반 해제
		::_aligned_free(header);
	}
	else
	{
		// 메모리 풀에 반납한다
		_poolTable[allocSize]->Push(header);
	}
}

 

3. 메모리 풀을 사용할 MemoryPoolAllocator 정의

 

"Allocator.h"

class PoolAllocator
{
public:
	static void* Alloc(int size);
	static void Release(void* ptr);
};

"Memory.h"에 있는 static 함수를 직접 사용할 것이므로, extern 키워드로 Memory 객체를 생성하자.

"CoreGlobal.h"

extern class Memory* GMemory;

"CoreGlobal.cpp"

Memory* GMemory = nullptr;

class CoreGlobal
{
public:
	CoreGlobal()
	{
		GMemory = new Memory();
	}
	~CoreGlobal()
	{
		delete GMemory;
	}
} GCoreGlobal;

 

이후 cpp 파일에서 이 객체를 이용하면 된다.

 

"Allocator.cpp"

void* PoolAllocator::Alloc(int size)
{
	return GMemory->Allocate(size);
}

void PoolAllocator::Release(void* ptr)
{
	GMemory->Release(ptr);
}

---

테스트

#pragma once
#include "pch.h"
#include "CoreMacro.h"
#include "Memory.h"

#include <iostream>

using namespace std;

class Unit
{
public:
	int _hp = rand() % 1000;
};

void thread1()
{
	while (true)
	{
		Unit* unit = xxnew<Unit>();

		cout << unit->_hp << '\n';

		this_thread::sleep_for(100ms);

		xxdelete(unit);
	}
}

int main()
{
	Vector<thread> v;
	for (int i = 0; i < 5; i++)
	{
		v.push_back(thread(thread1));
	}

	for (thread& t : v)
	{
		if (t.joinable()) t.join();
	}
}

#pragma once
#include "pch.h"
#include "CoreMacro.h"
#include "Memory.h"

#include <iostream>

using namespace std;

class Unit
{
public:
	int _hp = rand() % 1000;
};

void thread1()
{
	while (true)
	{
		Unit* unit = xxnew<Unit>();

		cout << unit->_hp << '\n';

		this_thread::sleep_for(100ms);

		xxdelete(unit);
	}
}

int main()
{
	Vector<thread> v;
	for (int i = 0; i < 5; i++)
	{
		v.push_back(thread(thread1));
	}

	for (thread& t : v)
	{
		if (t.joinable()) t.join();
	}
}

 

---