checkpoint - memory overhual including tests

2 files changed, 184 insertions, 56 deletions

diff --git a/src/memory.cpp b/src/memory.cpp
index 538ffd8..853c6fe 100644
--- a/src/memory.cpp
+++ b/src/memory.cpp
@@ -35,6 +35,12 @@ int64_t InitNewBucket(int64_t sz, bool transient = false) {
 	bkt.maxBlockCount = blockCount < 10 ? 10 : blockCount;
 	bkt.blocks = reinterpret_cast<char *>(std::malloc(sz));
 	bkt.ptr = bkt.blocks + (sizeof(MemBlock) * bkt.maxBlockCount);
+	size_t misalignment = reinterpret_cast<uint64_t>(bkt.ptr) % MAXIMUM_ALIGNMENT;
+	if (misalignment != 0) {
+		size_t moreBlocks = misalignment / sizeof(MemBlock);
+		bkt.maxBlockCount += moreBlocks;
+		bkt.ptr += (MAXIMUM_ALIGNMENT - misalignment);
+	}
 	bkt.transient = transient;
 	auto *memBlock = reinterpret_cast<MemBlock *>(bkt.blocks);
 	memBlock->data = bkt.ptr;
@@ -58,43 +64,86 @@ void DestroyBucket(MemBucket *bkt) {
 void *Pke_New(std::size_t sz, std::size_t alignment, MemBucket *bkt) {
 	MemBlock *blocks = reinterpret_cast<MemBlock *>(bkt->blocks);
 	std::size_t calculatedAlignment = alignment < MINIMUM_ALIGNMENT ? MINIMUM_ALIGNMENT : alignment;
-	int64_t availBlockIndex = -1;
+	std::size_t misalignment = 0;
+	long index = -1;
+	MemBlock *block = nullptr;
 	void *data = nullptr;
 	for (int64_t i = 0; i <= bkt->lastEmptyBlockIndex; ++i) {
-		auto blk = blocks[i];
-		std::size_t misalignment = reinterpret_cast<std::size_t>(blk.data) % calculatedAlignment;
-		if (misalignment != 0)
-			continue;
-		if (blk.size > sz) {
-			availBlockIndex = i;
+		auto &blk = blocks[i];
+		misalignment = reinterpret_cast<std::size_t>(blk.data) % calculatedAlignment;
+		misalignment = (calculatedAlignment - misalignment) % calculatedAlignment;
+		if (blk.size >= sz + misalignment) {
+			index = i;
+			block = &blk;
 			break;
 		}
 	}
-	if (availBlockIndex != -1) {
-		data = blocks[availBlockIndex].data;
-		blocks[availBlockIndex].data += sz;
-		blocks[availBlockIndex].size -= sz;
-		assert(blocks[availBlockIndex].size < bkt->size);
-		if (blocks[availBlockIndex].size == 0) {
-			if (availBlockIndex != bkt->lastEmptyBlockIndex) {
-				blocks[availBlockIndex].data = blocks[bkt->lastEmptyBlockIndex].data;
-				blocks[availBlockIndex].size = blocks[bkt->lastEmptyBlockIndex].size;
+	if (block != nullptr) {
+		MemBlock *nextBlock = &blocks[index + 1];
+		bool touchesValidNeighbor = index != bkt->lastEmptyBlockIndex && nextBlock->data == block->data + block->size; 
+		data = block->data + misalignment;
+		if (misalignment) {
+			size_t afterSize = block->size - misalignment - sz;
+			block->size = misalignment;
+			if (afterSize) {
+				if (index == bkt->maxBlockCount) {
+					bkt->lostBytes += afterSize;
+				} else if (touchesValidNeighbor) {
+					nextBlock->data -= afterSize;
+					nextBlock->size += afterSize;
+				} else {
+					if (index != bkt->lastEmptyBlockIndex) {
+						long moveCount = bkt->lastEmptyBlockIndex - index;
+						if (moveCount > 0) {
+							char *beforePos = bkt->blocks + (sizeof(MemBlock) * (index + 1));
+							char *afterPos = bkt->blocks + (sizeof(MemBlock) * (index + 2));
+							memmove(afterPos, beforePos, sizeof(MemBlock) * moveCount);
+						}
+					}
+					bkt->lastEmptyBlockIndex += 1;
+					nextBlock->data = block->data + misalignment + sz;
+					nextBlock->size = afterSize;
+				}
+			}
+		} else {
+			size_t afterSize = block->size - sz;
+			if (afterSize && !touchesValidNeighbor) {
+					block->data += sz;
+					block->size -= sz;
+			} else {
+				if (afterSize && touchesValidNeighbor) {
+					nextBlock->data -= afterSize;
+					nextBlock->size += afterSize;
+				}
+				long moveCount = bkt->lastEmptyBlockIndex - index;
+				if (moveCount > 0) {
+					char *beforePos = bkt->blocks + (sizeof(MemBlock) * (index + 1));
+					char *afterPos = bkt->blocks + (sizeof(MemBlock) * (index + 0));
+					memmove(afterPos, beforePos, sizeof(MemBlock) * moveCount);
+					bkt->lastEmptyBlockIndex -= 1;
+				}
 			}
-			bkt->lastEmptyBlockIndex -= 1;
 		}
 	} else {
 		assert(bkt->head + sz <= bkt->size && "memory bucket specified, but full");
-		std::size_t misalignment = reinterpret_cast<std::size_t>(bkt->ptr + bkt->head) % calculatedAlignment;
-		std::size_t padding = calculatedAlignment - misalignment;
+		misalignment = reinterpret_cast<std::size_t>(bkt->ptr + bkt->head) % calculatedAlignment;
+		misalignment = (calculatedAlignment - misalignment) % calculatedAlignment;
 		if (misalignment != 0) {
-			bkt->lastEmptyBlockIndex += 1;
-			blocks[bkt->lastEmptyBlockIndex].data = bkt->ptr + bkt->head;
-			blocks[bkt->lastEmptyBlockIndex].size = padding;
+			if (bkt->lastEmptyBlockIndex == bkt->maxBlockCount) {
+				bkt->lostBytes += misalignment;
+			} else {
+				bkt->lastEmptyBlockIndex += 1;
+				blocks[bkt->lastEmptyBlockIndex].data = bkt->ptr + bkt->head;
+				blocks[bkt->lastEmptyBlockIndex].size = misalignment;
+			}
+			bkt->head = bkt->head + misalignment;
 		}
-		data = bkt->ptr + bkt->head + padding;
-		bkt->head += sz + padding;
+		data = bkt->ptr + bkt->head;
+		bkt->head = bkt->head + sz;
 	}
 	bkt->allocs++;
+	assert(data >= bkt->ptr && "allocated data is before bucket data");
+	assert(data <= bkt->ptr + bkt->size && "allocated data is after bucket data");
 	return data;
 }
 
@@ -111,6 +160,52 @@ void *Pke_New(std::size_t sz, std::size_t alignment) {
 	return Pke_New(sz, alignment, bkt);
 }
 
+void inline Pke_CollapseEmptyBlocksToHead(MemBucket *bkt) {
+	MemBlock *blocks = reinterpret_cast<MemBlock *>(bkt->blocks);
+	while (bkt->lastEmptyBlockIndex > -1) {
+		MemBlock *lastBlock = &blocks[bkt->lastEmptyBlockIndex];
+		if (lastBlock->data + lastBlock->size != bkt->ptr + bkt->head) {
+			return;
+		}
+		bkt->head -= lastBlock->size;
+		lastBlock->data = 0;
+		lastBlock->size = 0;
+		bkt->lastEmptyBlockIndex -= 1;
+	}
+}
+
+void inline Pke_CollapseBlocks(MemBucket *bkt) {
+	MemBlock *blocks = reinterpret_cast<MemBlock *>(bkt->blocks);
+	long skipDistance = 1;
+	long lastStartingIndex = 0;
+	for (long i = 0; i <= bkt->lastEmptyBlockIndex - 1; ++i) {
+		lastStartingIndex = i;
+		MemBlock &block = blocks[i];
+		MemBlock &nextBlock = blocks[i + skipDistance];
+		if (block.data + block.size == nextBlock.data) {
+			block.size += nextBlock.size;
+			nextBlock.size = 0;
+			skipDistance += 1;
+			i -= 1;
+		} else {
+			if (skipDistance > 1) {
+				char *beforePos = bkt->blocks + (sizeof(MemBlock) * (i + skipDistance));
+				char *afterPos = bkt->blocks + (sizeof(MemBlock) * (i + 1));
+				memmove(afterPos, beforePos, sizeof(MemBlock) * (skipDistance - 1));
+				bkt->lastEmptyBlockIndex -= (skipDistance - 1);
+			}
+			i += skipDistance - 1;
+			skipDistance = 1;
+		}
+	}
+	if (skipDistance > 1) {
+		char *beforePos = bkt->blocks + (sizeof(MemBlock) * (lastStartingIndex + skipDistance));
+		char *afterPos = bkt->blocks + (sizeof(MemBlock) * (lastStartingIndex + 1));
+		memmove(afterPos, beforePos, sizeof(MemBlock) * (skipDistance - 1));
+		bkt->lastEmptyBlockIndex -= (skipDistance - 1);
+	}
+}
+
 void Pke_Delete(const void *ptr, std::size_t sz, MemBucket *bkt) {
 	assert(ptr >= bkt->ptr && ptr < bkt->ptr + bkt->size && "pointer not in memory bucket range");
 	bkt->allocs--;
@@ -121,28 +216,53 @@ void Pke_Delete(const void *ptr, std::size_t sz, MemBucket *bkt) {
 	}
 	if (ptr == bkt->ptr + bkt->head - sz) {
 		bkt->head -= sz;
-	} else {
-		MemBlock *blocks = reinterpret_cast<MemBlock *>(bkt->blocks);
-		for (int64_t i = 0; i < bkt->lastEmptyBlockIndex; ++i) {
-			auto &blk = blocks[i];
-			if (blk.data == reinterpret_cast<const char *>(ptr) + sz) {
-				blk.data -= sz;
-				blk.size += sz;
-				return;
-			}
-			if (reinterpret_cast<const char *>(ptr) == blk.data + blk.size ) {
-				blk.size += sz;
-				return;
-			}
+		Pke_CollapseEmptyBlocksToHead(bkt);
+		return;
+	}
+	MemBlock *blocks = reinterpret_cast<MemBlock *>(bkt->blocks);
+	size_t prevBlockIndex = 0xFFFFFFFFFFFFFFFF;
+	void *prevPointer = reinterpret_cast<void *>(prevBlockIndex);
+	bool found = false;
+	for (int64_t i = 0; i <= bkt->lastEmptyBlockIndex; ++i) {
+		auto &blk = blocks[i];
+		if (blk.data < ptr && prevPointer < blk.data) {
+			prevBlockIndex = i;
+			prevPointer = blk.data;
 		}
-		if (bkt->lastEmptyBlockIndex != bkt->maxBlockCount) {
-			bkt->lastEmptyBlockIndex += 1;
-			blocks[bkt->lastEmptyBlockIndex].data = reinterpret_cast<char *>(const_cast<void *>(ptr));
-			blocks[bkt->lastEmptyBlockIndex].size = sz;
-		} else {
+		if (blk.data == reinterpret_cast<const char *>(ptr) + sz) {
+			blk.data -= sz;
+			blk.size += sz;
+			found = true;
+			break;
+		}
+		if (reinterpret_cast<const char *>(ptr) == blk.data + blk.size ) {
+			blk.size += sz;
+			found = true;
+			break;
+		}
+	}
+	if (found == false) {
+		if (bkt->lastEmptyBlockIndex == bkt->maxBlockCount) {
 			bkt->lostBytes += sz;
+		} else {
+			MemBlock *targetBlock = nullptr;
+			if (prevBlockIndex < bkt->lastEmptyBlockIndex) {
+				long moveCount = bkt->lastEmptyBlockIndex - prevBlockIndex;
+				assert(moveCount > 0);
+				char *beforePos = bkt->blocks + (sizeof(MemBlock) * (prevBlockIndex + 1));
+				char *afterPos = bkt->blocks + (sizeof(MemBlock) * (prevBlockIndex + 2));
+				memmove(afterPos, beforePos, sizeof(MemBlock) * moveCount);
+				targetBlock = &blocks[prevBlockIndex + 1];
+			} else {
+				targetBlock = &blocks[bkt->lastEmptyBlockIndex + 1];
+			}
+			bkt->lastEmptyBlockIndex += 1;
+			targetBlock->data = reinterpret_cast<char *>(const_cast<void *>(ptr));
+			targetBlock->size = sz;
 		}
 	}
+	Pke_CollapseBlocks(bkt);
+	Pke_CollapseEmptyBlocksToHead(bkt);
 }
 
 void Pke_Delete(const void *ptr, std::size_t sz) {
@@ -207,7 +327,7 @@ uint64_t Buckets_NewHandle(std::size_t bucketBytes, std::size_t alignment, uint6
 }
 
 void Pke_DebugPrint() {
-	printf("Memory Manager printout:\nBucket count: %li\n", bucketHead + 1);
+	printf("Memory Manager printout:\nBucket count: %li\n", bucketHead);
 	for (long i = 0; i < bucketHead; ++i) {
 		printf("- bucket #%li\n", i);
 		printf("\tsize:                %li\n", buckets[i].size);
diff --git a/src/window.cpp b/src/window.cpp
index 480175a..3773643 100644
--- a/src/window.cpp
+++ b/src/window.cpp
@@ -242,6 +242,7 @@ unsigned int FindQueueFamilyIndex(VkPhysicalDevice device, short hasPresentSuppo
 
 void PKE_vkFreeFunction(void *pUserData, void *pMemory) {
 	pke_vkAllocData *chunk = nullptr;
+	if (pMemory == nullptr) return;
 	size_t index = -1;
 	size_t count = vulkanAllocs->Count();
 	for (long i = 0; i < count; ++i) {
@@ -257,11 +258,13 @@ void PKE_vkFreeFunction(void *pUserData, void *pMemory) {
 }
 
 void *PKE_vkAllocateFunction(void *pUserData, size_t size, size_t alignment, VkSystemAllocationScope allocScope) {
-	size_t alignedSize = size + ((size % alignment) == 0 ? 0 : (alignment - (size % alignment)));
-	void *ptr = Pke_New(alignedSize, alignment, MemBkt_Vulkan);
+	if (size == 0) {
+		return nullptr;
+	}
+	void *ptr = Pke_New(size, alignment, MemBkt_Vulkan);
 	vulkanAllocs->Push({
 		.data = ptr,
-		.size = alignedSize,
+		.size = size,
 	});
 	return ptr;
 }
@@ -269,22 +272,27 @@ void *PKE_vkAllocateFunction(void *pUserData, size_t size, size_t alignment, VkS
 void *PKE_vkReallocationFunction(void *pUserData, void *pOriginal, size_t size, size_t alignment, VkSystemAllocationScope allocScope) {
 	pke_vkAllocData *chunk = nullptr;
 	size_t index = -1;
-	if (pOriginal) {
-		size_t count = vulkanAllocs->Count();
-		for (long i = 0; i < count; ++i) {
-			if ((*vulkanAllocs)[i].data == pOriginal) {
-				chunk = &(*vulkanAllocs)[i];
-				index = i;
-				break;
-			}
+	if (pOriginal == nullptr) {
+		return PKE_vkAllocateFunction(pUserData, size, alignment, allocScope);
+	}
+	if (size == 0) {
+		PKE_vkFreeFunction(pUserData, pOriginal);
+		return nullptr;
+	}
+	size_t count = vulkanAllocs->Count();
+	for (long i = 0; i < count; ++i) {
+		if ((*vulkanAllocs)[i].data == pOriginal) {
+			chunk = &(*vulkanAllocs)[i];
+			index = i;
+			break;
 		}
 	}
 	assert(chunk != nullptr);
-	if (chunk->size > size) {
+	if (chunk->size >= size) {
 		return pOriginal;
 	}
 	void *newPtr = PKE_vkAllocateFunction(pUserData, size, alignment, allocScope);
-	memcpy(newPtr, chunk->data, chunk->size);
+	memcpy(newPtr, chunk->data, (chunk->size < size ? chunk->size : size) - 1);
 	Pke_Delete(chunk->data, chunk->size, MemBkt_Vulkan);
 	vulkanAllocs->Remove(index);
 	return newPtr;