(C++ : IOCP-22) Memory Pool-2

Posted by : C++ at Jul 24, 2021

Category : Cpp iocp

Get Code

개선했으면 하는 사항

Memory Pool에서 Lock을 건다
queue에 메모리 헤더를 넣는데, queue자체가 동적할당을 쓰기에 이 부분도 Memory Pool에 넣고 싶다

#pragma once

// -------------------
//		1차 시도
// -------------------

struct SListEntry
{
	SListEntry* next;
};

struct SListHeader
{
	SListEntry* next = nullptr;
};

void InitializeHead(SListHeader* header);
void PushEntrySList(SListHeader* header, SListEntry* entry);
SListEntry* PopEntrySList(SListHeader* header);

// []
// Header[ next ]
void InitializeHead(SListHeader* header)
{
	header->next = nullptr;
}

void PushEntrySList(SListHeader* header, SListEntry* entry)
{
    // [1(header)][2][3][4] 가 기존에 있었다고 가정하면
    // [5]가 새로 들어올 경우
    // [5(header)][1][2][3][4]
	entry->next = header->next; // header->next때문에 헷갈리는데 header를 의미함.
	header->next = entry;       // header를 entry로 바꿔달라
}

SListEntry* PopEntrySList(SListHeader* header)
{
	SListEntry* first = header->next;

	if (first != nullptr)
		header->next = first->next;

	return first;
}

// 실 사용은 이렇게
class Data // : public SListEntry
{
public:
	SListEntry _entry;
	
    int32 _hp;
    int32 _mp;
};

int main()
{
	SListHeader header;
	InitializeHead(&header);

    Data* data = new Data();
    PushEntrySList(&header, (SListEntry*)data);

    Data* popData = (Data*)PopEntrySList(&header);
}

좋긴한데 멀티쓰레드 환경에 적합하진 않다.

// -------------------
//		2차 시도
// -------------------

struct SListEntry
{
	SListEntry* next;
};

struct SListHeader
{
	SListEntry* next = nullptr;
};

void InitializeHead(SListHeader* header);
void PushEntrySList(SListHeader* header, SListEntry* entry);
SListEntry* PopEntrySList(SListHeader* header);

void InitializeHead(SListHeader* header)
{
	header->next = nullptr;
}

void PushEntrySList(SListHeader* header, SListEntry* entry)
{
	entry->next = header->next;

    // header->next = entry 하는 과정에서 다른 Thread가 영향을 줄까 두렵다.
	while (::InterlockedCompareExchange64((int64*)&header->next, 
                                        (int64)entry, 
                                        (int64)entry->next) == 0)
    /*
    if(header->next == entry->next) {
        header->next = entry;
    }
    else {
        entry->next = header->next;
    }
    */
	{

	}
}

// [][]
// Header[ next ]
SListEntry* PopEntrySList(SListHeader* header)
{
	SListEntry* expected = header->next;

	// ABA Problem
    // 이런 상황이 극적으로 발생할 수 있다.
    // header->next == expected 를 체크하는데 expected가 우연히 아주 우연히 삭제되었다 동일한 주소에 할당된 경우,
    // 단순 주소체크만으론 완벽하게 멀티쓰레드 프리하다고 말 할 수 없다.
	while (expected && ::InterlockedCompareExchange64((int64*)&header->next, 
                                                    (int64)expected->next, 
                                                    (int64)expected) == 0)
    /*
    if(header->next == expected) {
        header->next = expected->next;
    }
    else {
        expected = header->next;
    }
    */
	{

	}

	return expected;
}

단일 포인터만을 Compare And Swap을 하지말라!

// -------------------
//		3차 시도
// -------------------

#ifndef DECLSPEC_ALIGN
#if (_MSC_VER >= 1300) && !defined(MIDL_PASS)
#define DECLSPEC_ALIGN(x)   __declspec(align(x))        // x 바이트 정렬
#else
#define DECLSPEC_ALIGN(x)
#endif
#endif

// ...

DECLSPEC_ALIGN(16)      //16 바이트 정렬
struct SListEntry
{
	SListEntry* next;
};

DECLSPEC_ALIGN(16)
struct SListHeader
{
	SListHeader()
	{
		alignment = 0;
		region = 0;
	}

	union
	{
		struct
		{
			uint64 alignment;       // 64 bits
			uint64 region;          // 64 bits
		} DUMMYSTRUCTNAME;
		struct
		{
			uint64 depth : 16;      // 16 bits
			uint64 sequence : 48;   // 48 bits
			uint64 reserved : 4;    // 4 bits
			uint64 next : 60;       // 60 bits
		} HeaderX64;
	};
};

void InitializeHead(SListHeader* header);
void PushEntrySList(SListHeader* header, SListEntry* entry);
SListEntry* PopEntrySList(SListHeader* header);

void InitializeHead(SListHeader* header)
{
	header->alignment = 0;
	header->region = 0;
}

void PushEntrySList(SListHeader* header, SListEntry* entry)
{
	SListHeader expected = {};
	SListHeader desired = {};
	
	// SListEntry는 16 바이트 정렬이 되어있다.
    // 16 바이트 정렬이 되어있단 말은 최하위 4비트는 0000이 되어있을것이다.
    // why? 0001 0000 = 16 / 0010 0000 = 32 ...

    // desired.HeaderX64.next는 60bits이기에 사용안되는 최하위 4비트를 민다
	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)
        /*
        if(header == expected)
        {
            header = desired;
        }
        else
        {
            header = expected;
        }
        */
			break;
	}
}

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;
}