전 포스팅에서 보였던 메모리풀은 Lock을 사용했습니다. 그래서 MemoryPool의 큐에 메모리 공간을 빼거나 넣는 과정을 한번에 진행하지 못하는 아쉬움이 존재했습니다.
그래서 이번에는 Lock 없이 구현하는 방법을 알아볼 것입니다.
전에 했던 LockFree-Stack을 큐 대신에 사용할 것입니다.
그래서 우선 LockFree Stack을 먼저 구현해보겠습니다.
이전과 다른 점은 이번에는 Node를 사용하지 않고 데이터 자체를 연결할 것입니다.
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) {
header->alignment = 0;
header->region = 0;
}틀을 이렇습니다. 여기서 가장 중요한 것은 16바이트 정렬입니다. DECLSPEC_ALIGN이 16바이트 정렬을 해주는 기능입니다. 이러면 할당해주는 주솟값의 끝의 4비트가 항상 0000으로 됩니다.
그렇다면 항상 끝의 4비트는 0000이므로 4비트 >> 연산을 해준 다음 다시 4비트 << 해줘도 똑같은 주솟값을 얻을 수 있습니다. 그러면 남은 4비트는 자유롭게 사용할 수 있는 것입니다. 이번에는 4비트를 활용하지는 않기는 합니다.
우리는 이제 SListEntry를 항상 데이터 앞부분에 삽입하여 타입캐스팅을 하며 사용할 것입니다.
void PushEntrySList(SListHeader* header, SListEntry* entry) {
SListHeader expected = {};
SListHeader desired = {};
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;
}
}
SListEntry* PopEntrySList(SListHeader* header) {
SListHeader expected = {};
SListHeader desired = {};
SListEntry* entry = nullptr;
while (true) {
expected = *header;
entry = (SListEntry*)(((uint64)header->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;
}큰 틀은 이전의 LockFree 스택과 비슷합니다. 다만 depth, sequence라는 것이 보일 것입니다. 이는 ABA 문제를 해결하기 위한 방법입니다.
여기서 ABA 문제가 뭐냐면 스택에 A, B, C라는 데이터가 들어있고 메모리 주소로 이들을 구분한다고 가정해봅시다.
쓰레드1이 Pop을 하려고 합니다. 그런데 Pop을 하기 직전에 쓰레드 2, 쓰레드 3이 Pop을 했다고 생각해봅시다.
그러면 쓰레드2가 A를 Pop했고 쓰레드3이 B를 Pop 했습니다. 그리고 쓰레드2가 A를 할당 해제했습니다.
그 이후에 쓰레드4가 D라는 데이터를 Push를 했습니다. 그런데 우연히 D라는 데이터가 해제된 A가 들어있던 메모리 주소에 할당되었다고 생각해봅시다.
쓰레드1이 스택을 볼 때 첫부분이 A의 메모리 주소와 똑같기 때문에 이상함을 느끼지 못하고 통과시킬 것입니다.
왜냐하면 데이터로 구분하는 것이 아니라 데이터가 할당된 메모리 주소로 구분하기 때문입니다. 이러면 문제가 쓰레드1은 A라고 생각하고 진행하지만 사실 그 메모리 주소에 들어간 값은 A가 아닌 D이기에 프로그램의 흐름이 이상하게 되는 잠재적인 위협이 될 것입니다.
이러한 문제를 해결하기 위해서 A라는 데이터뿐만이 아니라 Push와 Pop을 할 때마다 증가하거나 줄어드는 depth를 만들고 명령어가 실행될 때마다 1씩 오르는 sequence를 넣은 것입니다.
A라는 데이터는 똑같을 수 있지만 depth와 sequence마저 같아지려면 Push와 Pop한 횟수가 동일해야하고 명령어를 실행한 횟수마저 허가된 용량이 초과해서 다시 0부터 시작하는 것이 아닌 이상 불가능할 것입니다.
DECLSPEC_ALIGN(16)
class Data {
public:
SListEntry _entry;
int64 _rand = rand() % 1000;
};
SListHeader* GHeader;
int main() {
GHeader = new SListHeader();
InitializeHead(GHeader);
for (int32 i = 0; i < 3; i++) {
GThreadManager->Launch([]() {
while (true) {
Data* data = new Data();
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();
}실제로는 이런 식으로 사용될 것입니다.
사실 이렇게 힘들게 구현을 했지만 코드의 주석에 써있는 것처럼 Use-After-Free 문제가 있습니다. 그래서 이러한 문제가 해결된 라이브러리가 있습니다. 이를 이용하여 앞에서 만든 MemoryPool을 바꿔보겠습니다.
DECLSPEC_ALIGN(16)
struct MyMemoryHeader : public SLIST_ENTRY {
MyMemoryHeader(int32 size) : allocSize(size) {
}
static void* AttachHeader(MyMemoryHeader* header, int32 size) {
new(header)MyMemoryHeader(size);
return reinterpret_cast<void*>(++header);
}
static MyMemoryHeader* DetachHeader(void* ptr) {
MyMemoryHeader* header = reinterpret_cast<MyMemoryHeader*>(ptr) - 1;
return header;
}
int32 allocSize;
};
DECLSPEC_ALIGN(16)
class MyMemoryPool {
public:
MyMemoryPool(int32 allocSize) : _allocSize(allocSize) {
InitializeSListHead(&_header);
}
~MyMemoryPool() {
while (MyMemoryHeader* memory = static_cast<MyMemoryHeader*>(::InterlockedPopEntrySList(&_header))) {
::_aligned_free(memory);
}
}
void Push(MyMemoryHeader* ptr) {
ptr->allocSize = 0;
InterlockedPushEntrySList(&_header, static_cast<PSLIST_ENTRY>(ptr));
_allocCount.fetch_sub(1);
}
MyMemoryHeader* Pop() {
MyMemoryHeader* memory = static_cast<MyMemoryHeader*>(::InterlockedPopEntrySList(&_header));
if (memory == nullptr) {
memory = reinterpret_cast<MyMemoryHeader*>(_aligned_malloc(_allocSize, SLIST_ALIGNMENT));
}
_allocCount.fetch_add(1);
return memory;
}
private:
SLIST_HEADER _header;
int32 _allocSize = 0;
atomic<int32> _allocCount = 0;
};
class MyMemory {
enum {
POOL_COUNT = (1024 / 32) + (1024 / 128) + (2048 / 256),
MAX_ALLOC_SIZE = 4096
};
public:
MyMemory() {
int32 size = 0;
int32 tableIndex = 0;
for (size = 32; size <= 1024; size += 32) {
MyMemoryPool* pool = new MyMemoryPool(size);
_pools.push_back(pool);
while (tableIndex <= size) {
_poolTable[tableIndex] = pool;
tableIndex++;
}
}
for (size = 1024; size <= 2048; size += 128) {
MyMemoryPool* pool = new MyMemoryPool(size);
_pools.push_back(pool);
while (tableIndex <= size) {
_poolTable[tableIndex] = pool;
tableIndex++;
}
}
for (size = 2048; size <= 4096; size += 256) {
MyMemoryPool* pool = new MyMemoryPool(size);
_pools.push_back(pool);
while (tableIndex <= size) {
_poolTable[tableIndex] = pool;
tableIndex++;
}
}
}
~MyMemory() {
for (MyMemoryPool* pool : _pools) {
delete pool;
}
_pools.clear();
}
void* Allocate(int32 size) {
MyMemoryHeader* header = nullptr;
const int32 allocSize = size + sizeof(MyMemoryHeader);
if (allocSize > MAX_ALLOC_SIZE) {
header = reinterpret_cast<MyMemoryHeader*>(_aligned_malloc(allocSize, 16));
}
else {
header = _poolTable[allocSize]->Pop();
}
return MyMemoryHeader::AttachHeader(header, allocSize);
}
void Release(void* ptr) {
MyMemoryHeader* header = MyMemoryHeader::DetachHeader(ptr);
const int32 allocSize = header->allocSize;
if (allocSize > MAX_ALLOC_SIZE) {
_aligned_free(header);
}
else {
_poolTable[allocSize]->Push(header);
}
}
private:
vector<MyMemoryPool*> _pools;
MyMemoryPool* _poolTable[MAX_ALLOC_SIZE + 1];
};
MyMemory* MyGMemory = new MyMemory();
SLIST_HEADER* GHeader;
int main() {
GHeader = new SLIST_HEADER();
InitializeSListHead(GHeader);
for (int i = 0; i < 5; i++) {
GThreadManager->Launch([]() {
while (true) {
Person* person = xxnew<Person>();
cout << person->_hp << endl;
this_thread::sleep_for(10ms);
xxdelete<Person>(person);
}
});
}
GThreadManager->Join();
}