KoreanFoodie's Study
[C++ 게임 서버] 2-7. 메모리 풀 #2 본문
[C++ 게임 서버] 2-7. 메모리 풀 #2
핵심 :
1. LockFreeStack 을 이용하여 Stack 을 관리해 보자. 이제 Entry 에 대한 메타 정보는 Header 가 관리한다!
이전 글에서는 메모리 풀을 사용함에 있어 크기별로 풀을 만들고,각 풀의 큐에 접근할 때 Lock 을 거는 방식을 사용했다.
한 발 더 나아가, 이번 글에서는 LockFreeStack 을 사용하면서 메모리 효율성을 고려한 구현을 선보이고자 한다.
사실 main 함수에서의 사용은 이전 글에서 했던 것과 거의 동일하다. 음.. 차이가 있다면, 메모리 풀을 간접적으로 거치지 않고 직접 Stack 을 만들어서 사용한다는 것인데, 일단 코드를 보자.
LockFreeStack.h
DECLSPEC_ALIGN(16)
struct SListEntry
{
SListEntry* next;
};
DECLSPEC_ALIGN(16)
struct SListHeader
{
SListHeader()
{
alignment = 0;
region = 0;
}
union
{
struct
{
uint64 alignment;
uint64 region;
} DUMMYSTRUCTNAME;
struct
{
uint64 depth : 16;
uint64 sequence : 48;
uint64 reserved : 4;
uint64 next : 60;
} HeaderX64;
};
};
void InitializeHead(SListHeader* header);
void PushEntrySList(SListHeader* header, SListEntry* entry);
SListEntry* PopEntrySList(SListHeader* header);시작부터.. 음, 다소 낯선 매크로가 보인다.
DECLSPEC_ALIGN(16)
// 위는 아래와 동치
#define DECLSPEC_ALIGN(x) __declspec(align(x))이 매크로는, 주소 배열을 16 바이트 간격으로 정렬 시킬 것이라는 걸 의미한다. 물론 __declspec(align(16)) 을 써도 되기는 하겠다 😅
StackOverFlow 에 올라온 예시를 보면...
__declspec(align(32))
struct aType
{
int a[12];
};위에서, aType 은 실제로 48 바이트 만큼을 차지(4 * 12. int 는 4 바이트 이니까)하는데, align offset 이 32 이므로 실제로는 64 바이트를 사용하여 aType 을 나열할 것이다.
굳이 SListEntry 와 SListHeader 의 주소값을 16 바이트로 정렬한 것은 추후 나머지 비트에 대한 활용성을 높이고, 메모리 효율을 높이기 위함이라는데... 실제로, 윈도우도 내부적으로 위와 비슷한 방식을 활용한다고 한다. 물론 이 글에 나오는 예시는 매우 조악한 수준이지만 😂
그리고 신기하게(?) union 을 사용한 부분이 있는데...
union
{
struct
{
uint64 alignment;
uint64 region;
} DUMMYSTRUCTNAME;
struct
{
uint64 depth : 16;
uint64 sequence : 48;
uint64 reserved : 4;
uint64 next : 60;
} HeaderX64;
};일단 union 안에 왜 DUMMYSTRUCTNAME 과 HeaderX64 라는 이름으로 두 개의 구조체가 들어가 있을까?
그 의도는, 128 비트 짜리 데이터를 다룰 때, 각각 다른 이름으로 접근할 수 있도록 하기 위함이다. 즉, 128 비트짜리 데이터를 접근할 때, 상위 64 비트는 alignment 로, 하위 64 비트는 region 으로, 상위 16 비트는 depth 로... 같은 식이다.
alignment 의 값은, 실제로 depth 와 sequence 를 합친 것과 동일할 것이다.
잘 보면, HeaderX64 의 요소들이 각각 16, 48, 4, 60 비트로 쪼개져 있는 것을 볼 수 있다. 위처럼 표현하면, depth 와 sequence 가 각각 uint64 만큼의 공간을 차지하지 않고, alignment 간격만큼 알아서 잘(?) 합쳐져서 메모리에 나열되게 된다.
즉, HeaderX64 의 경우, 멤버가 4개이지만, 실제로는 64 * 2 = 128 비트, 즉 16 바이트 크기의 공간을 사용할 것이다. 이는 DUMMYSTRUCTNAME 의 크기와 동일하다.
다시 돌아와서 전체적인 구조를 보자. 일단... Entry 가 있고, Header 가 있다.
Entry 는 나중에 실제 Data 를 담고 있는 클래스의 부모 격으로 사용될 것이고, Header 의 경우, 메타 데이터를 담는 등의 목적으로 활용횔 것이다. 예를 들면, Data 클래스는 다음과 같을 것이다 :
DECLSPEC_ALIGN(16)
class Data // : public SListEntry
{
public:
SListEntry _entry;
int64 _rand = rand() % 1000;
};
이제 LockFreeStack 에서 사용할... 엄밀히 예기하면, SListHeader 와 SListEntry 를 활용해서 만들 동작의 구현을 하나씩 제대로 알아보자.
void InitializeHead(SListHeader* header)
{
header->alignment = 0;
header->region = 0;
}일단 InitializeHead 는 header 의 alignment 와 region 값을 초기화해 준다.
음.. 갑자기 alignment 와 region 이 왜 등장했을까? Push 와 Pop 동작을 보면, 이게 왜 필요한지 알 수 있을 것이다. 미리 살짝 얘기하자면, depth 와 sequence 값을 변경하면서, alignment 와 region 을 identifier 처럼 사용할 것이다 🙂
void PushEntrySList(SListHeader* header, SListEntry* entry)
{
SListHeader expected = {};
SListHeader desired = {};
// 16 바이트 정렬
desired.HeaderX64.next = (((uint64)entry) >> 4);
while (true)
{
expected = *header;
// 이 사이에 변경될 수 있다
entry->next = (SListEntry*)(((uint64)expected.HeaderX64.next) << 4);
desired.HeaderX64.depth = expected.HeaderX64.depth + 1;
desired.HeaderX64.sequence = expected.HeaderX64.sequence + 1;
if (::InterlockedCompareExchange128((int64*)header, desired.region, desired.alignment, (int64*)&expected) == 1)
break;
}
}일단 desired.HeaderX64.next 를 entry 에서 '>> 4' 를 한 값을 넣어 주는데... desired 의 정체는, 사실 갈아끼울 header 의 초안(?)이다. Stack 에서 새로운 요소를 넣으면 header 쪽으로 들어가니까, header 를 갈아낄 녀석을 미리 준비해 놓는 것이다.
+ 16 바이트로 정렬하게 되면, 하위 4비트가 비어있다는 것을 알 수 있으므로 그렇게 쓸 수 있는 것이다. 애초에 하위 60 비트를 쓰는 것도 있고.
다음 while 문에서는 루프를 돌면서, expected 가 header 를 가리키게 하면서 entry 를 추가하려고 시도를 하는데..
일단, 인자로 주어지는 entry 의 next 에는, header 의 next 에 들어간 녀석에서 4 비트를 left shift 한 값을 채운다. depth 와 sequence 는, 그냥 1씩 중가시켜 준다.
그리고 대망의 체크를 하는데...
if (::InterlockedCompareExchange128(
(int64*)header,
desired.region,
desired.alignment,
(int64*)&expected) == 1
)
break;일단 InterlockedCompareExchange128 이 무엇인지부터 알아볼 필요가 있다. 일단 정의는 아래와 같이 되어 있는데...
BOOLEAN
InterlockedCompareExchange128 (
_Inout_ _Interlocked_operand_ LONG64 volatile *Destination,
_In_ LONG64 ExchangeHigh,
_In_ LONG64 ExchangeLow,
_Inout_ LONG64 *ComparandResult
);Destination 포인터가 가리키는 값(int64 비트짜리 배열 2개로 구성되어 있어야 한다. 그래야 128 비트가 될 것이니까)을, 상위 64 비트는 ExchangeHigh 와 비교하고, 하위 64 비트는 ExchangeLow 와 비교하여, 그 결과값을 *CompareandResult 에 넣어주는 식이다. 만약 일치하면, exptected 는 1이 될 것이다(true 니까).
여기서 region 과 alignment 를 비교하는데, 떠올려보면 코드에서 직접적으로 region 과 alignment 를 바꾸지는 않았다는 것을 알 수 있다. 그런데 왜 region 과 alignment 를 비교할까?
그 이유는, 바로 union 에 있다.
보물 말고 비트를 보자.
아까 DUMMYSTRUCTNAME 의 비트와, HeaderX64 의 비트는 동일하다고 말했더랬다. 근데 아까 depth 와 sequence 에 1씩 더하면서 Push 를 시도했으니까...
사실 alignment 와 region 또한, Push 를 할 때마다 바뀔 것이다! 아, 물론 depth 와 sequence 는 alignment 에 영향을 끼치고, reserved 와 next 가 region 에 영향을 끼치는데, 아까 desired 의 next 를 entry 의 next 로 넣어줬으니까... 둘 다 검사하는 게 도리에 맞을 것이다 😄
그럼 이제 Pop 을 보자.
SListEntry* PopEntrySList(SListHeader* header)
{
SListHeader expected = {};
SListHeader desired = {};
SListEntry* entry = nullptr;
while (true)
{
expected = *header;
entry = (SListEntry*)(((uint64)expected.HeaderX64.next) << 4);
if (entry == nullptr)
break;
// Use-After-Free
desired.HeaderX64.next = ((uint64)entry->next) >> 4;
desired.HeaderX64.depth = expected.HeaderX64.depth - 1;
desired.HeaderX64.sequence = expected.HeaderX64.sequence - 1;
if (::InterlockedCompareExchange128((int64*)header, desired.region, desired.alignment, (int64*)&expected) == 1)
break;
}
return entry;
}Pop 도 Push 와 비슷한 방식으로 작동할 것이다.
다만, bit shift 를 하는 방향이 반대로 바뀐다거나, + 대신 - 를 하는 자잘한 차이는 있다.
자, 이 글에서는 LockFreeStack 을 이용해 비트를 쪼개어 Push/Pop 을 하는 방식을 살펴 보았는데... while 문에서 보면, 다른 쓰레드가 중간에 개입할 여지가 있다 😢 그래서 다음 글에서는 그런 부분을 보완해 보도록 하자 😉
아, 참고로 메인함수는 다음 처럼 사용할 것이다 :
SListHeader* GHeader;
int main()
{
GHeader = new SListHeader();
ASSERT_CRASH(((uint64)GHeader % 16) == 0);
InitializeHead(GHeader);
for (int32 i = 0; i < 3; i++)
{
GThreadManager->Launch([]()
{
while (true)
{
Data* data = new Data();
ASSERT_CRASH(((uint64)data % 16) == 0);
PushEntrySList(GHeader, (SListEntry*)data);
this_thread::sleep_for(10ms);
}
});
}
for (int32 i = 0; i < 2; i++)
{
GThreadManager->Launch([]()
{
while (true)
{
Data* pop = nullptr;
pop = (Data*)PopEntrySList(GHeader);
if (pop)
{
cout << pop->_rand << endl;
delete pop;
}
else
{
cout << "NONE" << endl;
}
}
});
}
GThreadManager->Join();
}'Game Dev > Game Server' 카테고리의 다른 글
| [C++ 게임 서버] 2-9. Object Pool (0) | 2023.09.15 |
|---|---|
| [C++ 게임 서버] 2-8. 메모리 풀 #3 (0) | 2023.09.14 |
| [C++ 게임 서버] 2-6. 메모리 풀 #1 (0) | 2023.09.11 |
| [C++ 게임 서버] 2-5. STL Allocator (0) | 2023.08.25 |
| [C++ 게임 서버] 2-4. StompAllocator (0) | 2023.08.24 |
