initial commit: macros, memory, tests

1 files changed, 556 insertions, 0 deletions

diff --git a/pkmem.h b/pkmem.h
new file mode 100644
index 0000000..e0267c4
--- /dev/null
+++ b/pkmem.h
@@ -0,0 +1,556 @@
+#ifndef PK_MEM_H
+#define PK_MEM_H
+
+#include "pkmem-types.h"
+#include "pkmacros.h"
+
+#include <string.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#ifndef PK_DEFAULT_BUCKET_SIZE
+#  define PK_DEFAULT_BUCKET_SIZE (1ULL * 1024ULL * 1024ULL * 256ULL)
+#endif
+#ifndef PK_MINIMUM_ALIGNMENT
+#  define PK_MINIMUM_ALIGNMENT 1
+#endif
+#ifndef PK_MAXIMUM_ALIGNMENT
+#  define PK_MAXIMUM_ALIGNMENT 64
+#endif
+
+struct pk_membucket* pk_bucket_create(const char* description, int64_t sz, bool transient);
+void pk_bucket_destroy(struct pk_membucket* bkt);
+void pk_bucket_reset(struct pk_membucket* bkt);
+
+void pk_memory_debug_print();
+void pk_memory_flush();
+void pk_memory_teardown_all();
+bool pk_memory_is_in_bucket(const void* ptr, const struct pk_membucket* bkt);
+
+void* pk_new_base(size_t sz, size_t alignment);
+void* pk_new_bkt(size_t sz, size_t alignment, struct pk_membucket* bkt);
+void pk_delete_base(const void* ptr, size_t sz);
+void pk_delete_bkt(const void* ptr, size_t sz, struct pk_membucket* bkt);
+
+static inline void stupid_header_warnings() { (void)stdout; }
+
+#if defined(__cplusplus)
+
+#include <type_traits>
+
+static inline void stupid_header_warnings_cpp() { (void)std::is_const<void>::value; }
+
+template <typename T>
+inline T*
+pk_new(pk_membucket* bucket = nullptr)
+{
+	void* ptr = nullptr;
+	if (bucket) {
+		ptr = pk_new_bkt(sizeof(T), alignof(T), bucket);
+	} else {
+		ptr = pk_new_base(sizeof(T), alignof(T));
+	}
+	if IS_CONSTRUCTIBLE(T) {
+		return new (ptr) T{};
+	}
+	return reinterpret_cast<T*>(ptr);
+}
+
+template <typename T>
+inline T*
+pk_new(long count, pk_membucket* bucket = nullptr)
+{
+	char* ptr = nullptr;
+	if (bucket) {
+		ptr = static_cast<char*>(pk_new_bkt(sizeof(T) * count, alignof(T), bucket));
+	} else {
+		ptr = static_cast<char*>(pk_new_base(sizeof(T) * count, alignof(T)));
+	}
+	if IS_CONSTRUCTIBLE(T) {
+		for (long i = 0; i < count; ++i) {
+			new (ptr + (i * sizeof(T))) T{};
+		}
+	}
+	return reinterpret_cast<T*>(ptr);
+}
+
+template <typename T>
+inline void
+pk_delete(const T* ptr, pk_membucket* bucket = nullptr)
+{
+	if IS_DESTRUCTIBLE(T) {
+		reinterpret_cast<const T*>(ptr)->~T();
+	}
+	if (bucket) {
+		return pk_delete_bkt(static_cast<const void*>(ptr), sizeof(T), bucket);
+	} else {
+		return pk_delete_base(static_cast<const void*>(ptr), sizeof(T));
+	}
+}
+
+template <typename T>
+inline void
+pk_delete(const T* ptr, long count, pk_membucket* bucket = nullptr)
+{
+	if IS_DESTRUCTIBLE(T) {
+		for (long i = 0; i < count; ++i) {
+			reinterpret_cast<const T*>(reinterpret_cast<const char*>(ptr) + (i * sizeof(T)))->~T();
+		}
+	}
+	if (bucket) {
+		return pk_delete_bkt(static_cast<const void*>(ptr), sizeof(T) * count, bucket);
+	} else {
+		return pk_delete_base(static_cast<const void*>(ptr), sizeof(T) * count);
+	}
+}
+
+#endif /* __cplusplus */
+
+#endif /* PK_MEM */
+
+#ifdef PK_IMPLEMENTATION
+
+#include <threads.h>
+#include <assert.h>
+
+#if defined(PK_MEMORY_DEBUGGER)
+/*
+ * Note that certain aspects of this expect that you only have one non-transient bucket.
+ * If you need to track multiple non-transient buckets, these sections will need a refactor.
+ */
+#endif
+
+struct pk_memblock {
+	char* data;
+	size_t size;
+};
+
+struct pk_membucket {
+	// the total size of the bucket, `blocks+ptr`
+	int64_t size;
+	// the current head of the bucket: byte offset from `ptr`.
+	// All currently alloc'd data is before this offset
+	int64_t head;
+	// amount of lost bytes in this membucket, hopefully zero
+	int64_t lostBytes;
+	// the number of active allocations from this bucket
+	int64_t allocs;
+	// the index of the last empty block.
+	// Should always point to `pk_memblock{ .data = ptr+head, .size=size-head }`
+	int64_t lastEmptyBlockIndex;
+	// number of pk_memblocks in the `*blocks` array
+	int64_t maxBlockCount;
+	// ptr to an array of pk_memblock to track ALL free space between ptr and ptr+sz
+	struct pk_memblock* blocks;
+	// starting point for alloc'd data
+	union {
+		char* ptr;
+		void* raw;
+	};
+	const char* description;
+	mtx_t mtx;
+	bool transient;
+};
+
+static struct pk_membucket pk_buckets[8];
+static int64_t pk_bucket_head = 0;
+
+#ifdef PK_MEMORY_DEBUGGER
+static struct pk_memblock debug_all_allocs[1024 * 1024];
+static int64_t debug_alloc_head = 0;
+static bool has_init_debug = false;
+#endif
+
+bool
+pk_memory_is_in_bucket(const void* ptr, const struct pk_membucket* bkt)
+{
+	if (ptr >= bkt->raw && (const char*)ptr < bkt->ptr + bkt->size) return true;
+	return false;
+}
+
+void
+pk_memory_debug_print()
+{
+	PK_LOGV_INF("Memory Manager printout:\nBucket count: %li\n", pk_bucket_head);
+	for (long i = 0; i < pk_bucket_head; ++i) {
+		PK_LOGV_INF("- bucket #%li\n", i);
+		PK_LOGV_INF("\tdescription:         %s\n", pk_buckets[i].description);
+		PK_LOGV_INF("\tsize:                %li\n", pk_buckets[i].size);
+		PK_LOGV_INF("\thead:                %li\n", pk_buckets[i].head);
+		PK_LOGV_INF("\tlostBytes:           %li\n", pk_buckets[i].lostBytes);
+		PK_LOGV_INF("\tallocs:              %li\n", pk_buckets[i].allocs);
+		PK_LOGV_INF("\tlastEmptyBlockIndex: %li\n", pk_buckets[i].lastEmptyBlockIndex);
+		PK_LOGV_INF("\tmaxBlockCount:       %li\n", pk_buckets[i].maxBlockCount);
+		PK_LOGV_INF("\tblocks:              %p\n", pk_buckets[i].blocks);
+		PK_LOGV_INF("\tptr:                 %p\n", pk_buckets[i].ptr);
+		PK_LOGV_INF("\ttransient:           %i\n", pk_buckets[i].transient);
+#ifdef PK_MEMORY_DEBUGGER
+		uint64_t count = 0;
+		for (int64_t i = 0; i < debug_alloc_head; ++i) {
+			if (debug_all_allocs[i].size > 0) {
+				count += 1;
+			}
+		}
+		PK_LOGV_INF("\tdebug alloc count:   %lu\n", count);
+		PK_LOGV_INF("\tdebug alloc last:    %lu\n", debug_alloc_head);
+#endif
+	}
+}
+
+void
+pk_memory_flush()
+{
+	for (long i = pk_bucket_head - 2; i > -1; --i) {
+		if (pk_buckets[i].head != 0) break;
+		if (pk_buckets[i+1].head != 0) break;
+		if (pk_buckets[i].transient == true) break;
+		if (pk_buckets[i+1].transient == true) break;
+		pk_bucket_head--;
+		pk_bucket_destroy(&pk_buckets[i + 1]);
+	}
+}
+
+void
+pk_memory_teardown_all()
+{
+	for (int64_t i = pk_bucket_head - 1; i > 0; --i) {
+		if (pk_buckets[i].ptr == nullptr) continue;
+		pk_bucket_destroy(&pk_buckets[i]);
+	}
+	pk_bucket_head = 0;
+}
+
+static int64_t
+pk_bucket_create_inner(int64_t sz, bool transient, const char* description)
+{
+#ifdef PK_MEMORY_DEBUGGER
+	if (has_init_debug == false) {
+		has_init_debug = true;
+		memset(debug_all_allocs, 0, sizeof(struct pk_memblock) * 1024 * 1024);
+	}
+#endif
+	int64_t blockCount = sz * 0.01;
+	struct pk_membucket* bkt = &pk_buckets[pk_bucket_head];
+	bkt->size = sz;
+	bkt->head = 0;
+	bkt->lostBytes = 0;
+	bkt->allocs = 0;
+	bkt->lastEmptyBlockIndex = 0;
+	bkt->maxBlockCount = blockCount < 10 ? 10 : blockCount;
+	bkt->blocks = (struct pk_memblock*)malloc(sz);
+	assert(bkt->blocks != nullptr && "failed to allocate memory");
+#if 1
+	memset(bkt->blocks, 0, sz);
+#endif
+	bkt->ptr = ((char*)(bkt->blocks)) + (sizeof(struct pk_memblock) * bkt->maxBlockCount);
+	size_t misalignment = (uint64_t)(bkt->ptr) % PK_MAXIMUM_ALIGNMENT;
+	if (misalignment != 0) {
+		size_t moreBlocks = misalignment / sizeof(struct pk_memblock);
+		bkt->maxBlockCount += moreBlocks;
+		bkt->ptr += (PK_MAXIMUM_ALIGNMENT - misalignment);
+	}
+	bkt->description = description;
+	bkt->transient = transient;
+	struct pk_memblock* memBlock = (struct pk_memblock*)(bkt->blocks);
+	memBlock->data = bkt->ptr;
+	memBlock->size = sz - (sizeof(struct pk_memblock) * bkt->maxBlockCount);
+	return pk_bucket_head++;
+}
+
+struct pk_membucket*
+pk_bucket_create(const char* description, int64_t sz, bool transient)
+{
+	return &pk_buckets[pk_bucket_create_inner(sz, transient, description)];
+}
+
+void
+pk_bucket_destroy(struct pk_membucket* bkt)
+{
+	for (int64_t i = 0; i < pk_bucket_head; ++i) {
+		if (&pk_buckets[i] == bkt) {
+			if (pk_bucket_head == i)
+				pk_bucket_head--;
+			break;
+		}
+	}
+	free(bkt->blocks);
+	bkt->size = 0;
+	bkt->head = 0;
+	bkt->lostBytes = 0;
+	bkt->allocs = 0;
+	bkt->lastEmptyBlockIndex = -1;
+	bkt->maxBlockCount = 0;
+	bkt->blocks = CAFE_BABE(struct pk_memblock);
+	bkt->ptr = CAFE_BABE(char);
+	bkt->transient = false;
+}
+
+void
+pk_bucket_reset(struct pk_membucket* bkt)
+{
+	if (bkt->transient != true) {
+		PK_LOG_ERR("WARNING: pk_bucket_reset called on non-transient pk_membucket\n");
+	}
+	bkt->head = 0;
+	bkt->lostBytes = 0;
+	bkt->allocs = 0;
+	bkt->lastEmptyBlockIndex = 0;
+	bkt->blocks->data = bkt->ptr;
+	bkt->blocks->size = bkt->size - (sizeof(struct pk_memblock) * bkt->maxBlockCount);
+}
+
+void
+pk_bucket_insert_block(struct pk_membucket* bkt, const struct pk_memblock* block)
+{
+	int64_t index = bkt->lastEmptyBlockIndex;
+	while (index >= 0) {
+		struct pk_memblock* b = &bkt->blocks[index];
+		struct pk_memblock* nb = &bkt->blocks[index + 1];
+		if (b->data < block->data) {
+			break;
+		}
+		nb->data = b->data;
+		nb->size = b->size;
+		index -= 1;
+	}
+	struct pk_memblock *b = &bkt->blocks[index + 1];
+	b->data = block->data;
+	b->size = block->size;
+	bkt->lastEmptyBlockIndex += 1;
+}
+
+void
+pk_bucket_collapse_empty_blocks(struct pk_membucket* bkt) {
+	for (int64_t i = bkt->lastEmptyBlockIndex; i > -1; --i) {
+		struct pk_memblock* block = &bkt->blocks[i];
+		if (block->size == 0 && i == bkt->lastEmptyBlockIndex) {
+			block->data = nullptr;
+			bkt->lastEmptyBlockIndex -= 1;
+			continue;
+		}
+		if (block->size > 0) {
+			continue;
+		}
+		for (int64_t k = i; k < bkt->lastEmptyBlockIndex; ++k) {
+			bkt->blocks[k].data = bkt->blocks[k + 1].data;
+			bkt->blocks[k].size = bkt->blocks[k + 1].size;
+		}
+		bkt->lastEmptyBlockIndex -= 1;
+	}
+}
+
+void*
+pk_new_bkt(size_t sz, size_t alignment, struct pk_membucket* bkt)
+{
+#ifdef PK_MEMORY_FORCE_MALLOC
+	return malloc(sz);
+#endif
+	if (sz == 0) return nullptr;
+	size_t calculatedAlignment = alignment < PK_MINIMUM_ALIGNMENT ? PK_MINIMUM_ALIGNMENT : alignment;
+	size_t misalignment = 0;
+	struct pk_memblock* prevBlock = nullptr;
+	struct pk_memblock* block = nullptr;
+	struct pk_memblock* nextBlock = nullptr;
+	void* data = nullptr;
+	mtx_lock(&bkt->mtx);
+	for (int64_t i = 0; i <= bkt->lastEmptyBlockIndex; ++i) {
+		struct pk_memblock* blk = &bkt->blocks[i];
+		misalignment = (size_t)(blk->data) % calculatedAlignment;
+		misalignment = (calculatedAlignment - misalignment) % calculatedAlignment;
+		if (blk->size >= sz + misalignment) {
+			block = blk;
+			if (i < bkt->lastEmptyBlockIndex && bkt->blocks[i + 1].data == block->data + block->size) {
+				nextBlock = &bkt->blocks[i + 1];
+			}
+			if (i > 0 && i != bkt->lastEmptyBlockIndex && (bkt->blocks[i-1].data + bkt->blocks[i-1].size) == block->data) {
+				prevBlock = &bkt->blocks[i - 1];
+			}
+			break;
+		}
+	}
+	assert(block != nullptr && "memory corruption: failed to find bucket with enough space");
+	data = block->data + misalignment;
+#ifdef PK_MEMORY_DEBUGGER
+	bool handled = bkt->transient;
+	if (handled == false) {
+		for (int64_t i = 0; i < debug_alloc_head; ++i) {
+			struct pk_memblock* mb = &debug_all_allocs[i];
+			assert((mb->size == 0 || (void*)(mb->data) != data) && "mem address alloc'd twice!");
+			if (mb->size == 0) {
+				mb->data = (char*)(data);
+				mb->size = sz;
+				handled = true;
+				break;
+			}
+		}
+	}
+	if (handled == false) {
+		debug_all_allocs[debug_alloc_head++] = (struct pk_memblock){
+			.data = (char*)(data),
+			.size = sz,
+		};
+	}
+#endif
+	int64_t afterSize = block->size - (misalignment + sz);
+	if (block->data == bkt->ptr + bkt->head) {
+		bkt->head += (sz + misalignment);
+	}
+	if (afterSize > 0 && nextBlock == nullptr) {
+		struct pk_memblock newBlock;
+		memset(&newBlock, 0, sizeof(struct pk_memblock));
+		newBlock.data = block->data + misalignment + sz;
+		newBlock.size = afterSize;
+		pk_bucket_insert_block(bkt, &newBlock);
+	}
+	if (prevBlock == nullptr && nextBlock == nullptr) {
+		block->size = misalignment;
+	} else if (nextBlock != nullptr) {
+		block->size = misalignment;
+		nextBlock->data -= afterSize;
+		nextBlock->size += afterSize;
+	} else if (prevBlock != nullptr) {
+		prevBlock->size += misalignment;
+		block->data += misalignment + sz;
+		block->size = 0; // if you make it here, afterSize has already been handled
+	}
+	bkt->allocs++;
+	assert(data >= bkt->raw && "allocated data is before bucket data");
+	assert((char*)data <= bkt->ptr + bkt->size && "allocated data is after bucket data");
+	pk_bucket_collapse_empty_blocks(bkt);
+#ifdef PK_MEMORY_DEBUGGER
+	if (!bkt->transient) {
+		int64_t debug_tracked_alloc_size = 0;
+		int64_t debug_bucket_alloc_size = bkt->size - (sizeof(struct pk_memblock) * bkt->maxBlockCount);
+		for (int64_t i = 0; i < debug_alloc_head; ++i) {
+			debug_tracked_alloc_size += debug_all_allocs[i].size;
+		}
+		for (int64_t i = 0; i <= bkt->lastEmptyBlockIndex; ++i) {
+			debug_bucket_alloc_size -= bkt->blocks[i].size;
+		}
+		assert(debug_tracked_alloc_size == debug_bucket_alloc_size && "allocation size mismatch!");
+	}
+#endif
+	mtx_unlock(&bkt->mtx);
+	return data;
+}
+
+void*
+pk_new_base(size_t sz, size_t alignment)
+{
+	struct pk_membucket* bkt = nullptr;
+	for (long i = 0; i < pk_bucket_head; ++i) {
+		if (pk_buckets[i].transient == false && pk_buckets[i].size - pk_buckets[i].head > sz + PK_MAXIMUM_ALIGNMENT) {
+			bkt = &pk_buckets[i];
+			break;
+		}
+	}
+	if (bkt == nullptr) {
+		bkt = &pk_buckets[pk_bucket_create_inner(PK_DEFAULT_BUCKET_SIZE, false, "pk_bucket internally created")];
+	}
+	return pk_new_bkt(sz, alignment, bkt);
+}
+
+void
+pk_delete_bkt(const void* ptr, size_t sz, struct pk_membucket* bkt)
+{
+#ifdef PK_MEMORY_FORCE_MALLOC
+	return std::free(const_cast<void*>(ptr));
+#endif
+	assert(ptr >= bkt->raw && (char*)ptr < bkt->ptr + bkt->size && "pointer not in memory bucket range");
+	assert(sz > 0 && "attempted to free pointer of size 0");
+#ifdef PK_MEMORY_DEBUGGER
+	bool found = bkt->transient;
+	if (found == false) {
+		for (int64_t i = debug_alloc_head - 1; i > -1; --i) {
+			struct pk_memblock* mb = &debug_all_allocs[i];
+			if (mb->size == 0) continue;
+			if ((void*)(mb->data) == ptr) {
+				assert(mb->size == sz && "[pk_MEMORY_HPP] incorrect free size");
+				mb->size = 0;
+				found = true;
+				if (i == (debug_alloc_head - 1)) {
+					debug_alloc_head--;
+				}
+				break;
+			}
+		}
+	}
+	assert(found && "[pk_MEMORY_HPP] double free or invalid ptr");
+#endif
+	bkt->allocs--;
+	if (bkt->allocs == 0) {
+		bkt->head = 0;
+		bkt->lastEmptyBlockIndex = 0;
+		bkt->blocks[0].data = bkt->ptr;
+		bkt->blocks[0].size = bkt->size - (sizeof(struct pk_memblock) * bkt->maxBlockCount);
+		return;
+	}
+	char* afterPtr = ((char*)(ptr))+sz;
+	struct pk_memblock* beforeBlk = nullptr;
+	struct pk_memblock* afterBlk = nullptr;
+	for (int64_t i = bkt->lastEmptyBlockIndex; i > 0; --i) {
+		if (bkt->blocks[i-1].data + bkt->blocks[i-1].size == ptr) {
+			beforeBlk = &bkt->blocks[i-1];
+		}
+		if (bkt->blocks[i].data == afterPtr) {
+			afterBlk = &bkt->blocks[i];
+			break;
+		}
+		if (bkt->blocks[i-1].data < (char*)ptr) {
+			break;
+		}
+	}
+	if (ptr == bkt->ptr && afterBlk == nullptr && bkt->blocks[0].data == afterPtr) {
+		afterBlk = &bkt->blocks[0];
+	}
+	if (afterBlk != nullptr && afterBlk->data == bkt->ptr + bkt->head) {
+		bkt->head -= sz;
+		if (beforeBlk != nullptr) {
+			bkt->head -= beforeBlk->size;
+		}
+	}
+	if (beforeBlk == nullptr && afterBlk == nullptr) {
+		struct pk_memblock newBlock;
+		memset(&newBlock, 0, sizeof(struct pk_memblock));
+		newBlock.data = (char*)ptr;
+		newBlock.size = sz;
+		pk_bucket_insert_block(bkt, &newBlock);
+	} else if (beforeBlk != nullptr && afterBlk != nullptr) {
+		beforeBlk->size += sz + afterBlk->size;
+		afterBlk->size = 0;
+	} else if (beforeBlk != nullptr) {
+		beforeBlk->size += sz;
+	} else if (afterBlk != nullptr) {
+		afterBlk->data -= sz;
+		afterBlk->size += sz;
+	}
+	pk_bucket_collapse_empty_blocks(bkt);
+#ifdef PK_MEMORY_DEBUGGER
+	if (!bkt->transient) {
+		int64_t debug_tracked_alloc_size = 0;
+		int64_t debug_bucket_alloc_size = bkt->size - (sizeof(struct pk_memblock) * bkt->maxBlockCount);
+		for (int64_t i = 0; i < debug_alloc_head; ++i) {
+			debug_tracked_alloc_size += debug_all_allocs[i].size;
+		}
+		for (int64_t i = 0; i <= bkt->lastEmptyBlockIndex; ++i) {
+			debug_bucket_alloc_size -= bkt->blocks[i].size;
+		}
+		assert(debug_tracked_alloc_size == debug_bucket_alloc_size && "allocation size mismatch!");
+	}
+#endif
+}
+
+void
+pk_delete_base(const void* ptr, size_t sz)
+{
+	struct pk_membucket* bkt = nullptr;
+	for (long i = 0; i < pk_bucket_head; ++i) {
+		bkt = &pk_buckets[i];
+		if (ptr >= bkt->raw && (char*)ptr < bkt->ptr + bkt->size) break;
+	}
+	assert(bkt != nullptr && "failed to determine correct memory bucket");
+	pk_delete_bkt(ptr, sz, bkt);
+}
+
+#endif /* PK_IMPLEMENTATION */