SList(C++) 불완전

#pragma once



//template<typename T>
//struct Node {
//	T data;
//	Node* 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 InitializeHeader(SListHeader* header);

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

SListEntry* PopEntrySList(SListHeader* header);

 

#include "pch.h"
#include "LockFreeStack.h"

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

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;

	// ABA Problem
	
	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;

}

ABA문제를 해결하기 위한 코드이나, user-after-free는 해결하지 못함.

 Microsoft에 SList를 쓰자!