Commit 6a64487

@@ -0,0 +1,142 @@
+#ifndef NOTLIBC_HEADER_MEMORY_HEAP_DEBUG_INCLUDED
+#define NOTLIBC_HEADER_MEMORY_HEAP_DEBUG_INCLUDED
+
+#include "memory/arena.h"
+
+STRUCT( HeapEntry,
+	u64 header_start_guard;
+	usize allowed_size;
+	struct _HeapEntry *next; /* unlike in release, in debug we have a separate next pointer for linking into the freelist */
+	u64 checksum; /* size xor'd with next, allowed size and the guard magic number - (likely) detects overwriting of metadata */
+	usize size;
+	u64 header_end_guard;
+);
+
+
+STRUCT( Heap,
+	Arena arena; /* Heap is built on top of arena. It's just an arena + a freelist with metadata */
+	HeapEntry freelist;
+	HeapEntry blocklist; /* The existing blocks in a list */
+);
+
+Status Heap_create( Heap *out, usize size ) {
+	assert( out != 0 );
+	assert( size != 0 );
+	TRY( Arena_create( &out->arena, size ) );
+	out->freelist = (HeapEntry){0};
+	out->blocklist = (HeapEntry){0};
+	return S_SUCCESS;
+}
+
+Status Heap_destroy( Heap *h ) {
+	assert( h != 0 );
+	TRY( Arena_destroy( &h->arena ) );
+	mem_set( h, sizeof(*h), 0 );
+	return S_SUCCESS;
+}
+
+Status Heap_alloc( Heap *h, usize amount, u8 **out ) {
+	assert( h != 0 );
+	assert( amount > 0 ); /* If your code can try to allocate 0 amount of memory you should consider rewriting it (or getting some help) */
+
+	TRY( usize_round_up( amount, sizeof(usize), &amount ) );
+	usize total_amount = amount + sizeof(HeapEntry) + sizeof(usize); /* usize for end guard */
+
+	HeapEntry *new = 0;
+	HeapEntry *prev  = &h->freelist;
+
+	usize max_size = 0;
+	TRY( usize_mul(total_amount, 4, &max_size) );
+
+	
+	for( HeapEntry *i = h->freelist.next; i != 0; i = i->next ) {
+
+		u8* data = (u8*)(&i->header_end_guard + 1);
+		/* If any of these fails, then your freelist has been corrupted somehow - it should not be iterated */
+		assert( i->header_start_guard == HEAP_HEADER_GUARD_NUMBER );
+		assert( i->header_end_guard == HEAP_HEADER_GUARD_NUMBER );
+		assert( i->checksum == (i->size ^ i->allowed_size ^ (usize)i->next ^ HEAP_XOR_KEY) );
+		assert( i->allowed_size >= i->size );
+		assert( *(usize*)(data + i->allowed_size) == HEAP_OVERRUN_GUARD_NUMBER );
+
+		if( i->allowed_size >= amount && i->allowed_size <= max_size ) {
+			new = i;
+			for( usize i = 0; i < new->allowed_size; ++i ) {
+				assert( data[i] == MAGIC_FREED_MEM );
+			}
+			prev->next = new->next;
+			prev->checksum = (prev->size ^ prev->allowed_size ^ (usize)prev->next ^ HEAP_XOR_KEY);
+			new->next = 0;
+			break;
+		}
+		prev = i;
+	}
+
+	if( !new ) {
+		TRY( Arena_take( &h->arena, total_amount, (u8**)&new ) );
+		new->allowed_size = amount;
+	}
+
+	new->size = amount;
+
+	u8 *data = (u8*)(&new->header_end_guard + 1);
+	mem_set( data, new->size, MAGIC_UNINITIALIZED_MEM );
+	mem_set( data + new->size, new->allowed_size - new->size, MAGIC_POISONED_MEM );
+
+	*(usize*)(data + new->allowed_size) = HEAP_OVERRUN_GUARD_NUMBER;
+
+	new->next = h->blocklist.next;
+	h->blocklist.next = new;
+	new->size = amount;
+	new->checksum = new->size ^ new->allowed_size ^ (usize)new->next ^ HEAP_XOR_KEY;
+	new->header_start_guard = HEAP_HEADER_GUARD_NUMBER;
+	new->header_end_guard = HEAP_HEADER_GUARD_NUMBER;
+
+	*out = data;
+
+	return S_SUCCESS;
+}
+
+Status Heap_free( Heap *h, u8 **ptr ) {
+	assert( h != 0 );
+	assert( ptr != 0 );
+
+	HeapEntry *e = (HeapEntry*)( (u8*)*ptr - sizeof(HeapEntry) );
+
+	u8 ptr_correct = 0;
+	HeapEntry *prev = &h->blocklist;
+
+	for( HeapEntry *i = h->blocklist.next; i != 0; i = i->next ) {
+		if( e == i ) {
+			ptr_correct = 1;
+			break;
+		}
+		prev = i;
+	}
+
+	/* The pointer is not pointing to a previously allocated block if this fails or perhaps it is a double-free. */
+	assert(ptr_correct);
+
+	/* Check header corruption */
+	assert( e->checksum == (e->size ^ e->allowed_size ^ (usize)e->next ^ HEAP_XOR_KEY) );
+	assert( e->header_start_guard == HEAP_HEADER_GUARD_NUMBER );
+	assert( e->header_end_guard == HEAP_HEADER_GUARD_NUMBER );
+
+	prev->next = e->next;
+	prev->checksum = prev->size ^ prev->allowed_size ^ (usize)prev->next ^ HEAP_XOR_KEY;
+
+	e->next = h->freelist.next;
+	h->freelist.next = e;
+	e->checksum = e->size ^ e->allowed_size ^ (usize)e->next ^ HEAP_XOR_KEY;
+
+	u8* data = (u8*)(&e->header_end_guard + 1);
+	mem_set( data, e->allowed_size, MAGIC_FREED_MEM );
+	*(usize*)(data + e->allowed_size) = HEAP_OVERRUN_GUARD_NUMBER;
+
+	*ptr = 0;
+
+	return S_SUCCESS;
+}
+
+
+#endif

@@ -0,0 +1,82 @@
+#ifndef NOTLIBC_HEADER_MEMORY_HEAP_RELEASE_INCLUDED
+#define NOTLIBC_HEADER_MEMORY_HEAP_RELEASE_INCLUDED
+
+#include "memory/arena.h"
+
+STRUCT( HeapEntry,
+	usize size; /* The next pointer is stored in the data when the block is added to the freelist */
+);
+
+STRUCT( Heap,
+	Arena arena; /* Heap is built on top of arena. It's just an arena + a freelist with metadata */
+	HeapEntry freelist;
+	HeapEntry *freelist_data;
+);
+
+Status Heap_create( Heap *out, usize size ) {
+	TRY( Arena_create( &out->arena, size ) );
+	out->freelist = (HeapEntry){0};
+	out->freelist_data = 0;
+	return S_SUCCESS;
+}
+
+Status Heap_destroy( Heap *h ) {
+	TRY( Arena_destroy( &h->arena ) );
+	h->freelist = (HeapEntry){0};
+	h->freelist_data = 0;
+	return S_SUCCESS;
+}
+
+Status Heap_alloc( Heap *h, usize amount, u8 **out ) {
+	if( amount == 0 ) return S_FAILURE | ERR_INVALID_ARGUMENT | ERRSRC_ARG_2;
+
+	usize required_amount = usize_max(amount, sizeof(void*)); /* A pointer must fit into data, otherwise it can not be linked into the freelist when freed. */
+	TRY( usize_add( required_amount, sizeof(HeapEntry), &required_amount ) );
+	TRY( usize_round_up( required_amount, sizeof(usize), &required_amount ) ); /* word-align */
+
+	HeapEntry *new = 0;
+	
+	/* Check freelist */
+	HeapEntry *prev  = &h->freelist;
+
+	usize max_size = 0;
+	TRY( usize_mul(required_amount, 4, &max_size) );
+
+	for( HeapEntry *i = h->freelist_data; i != 0; i = *(HeapEntry**)(&i->size + 1) ) {
+		if( i->size >= required_amount && i->size <= max_size ) {
+			new = i;
+			*(HeapEntry**)(&prev->size + 1) = *(HeapEntry**)(&new->size + 1); /* unlink entry */
+			break;
+		}
+		prev = i;
+	}
+
+	/* New allocation */
+	if( !new ) {
+		TRY( Arena_take( &h->arena, required_amount, (u8**)&new ) );
+		new->size = required_amount;
+	}
+	/* otherwise we leave original size */
+
+	*out = (u8*)(&new->size + 1);
+
+	return S_SUCCESS;
+}
+
+Status Heap_free( Heap *h, u8 **ptr ) {
+	if( h == 0 ) return S_FAILURE | ERR_INVALID_ARGUMENT | ERRSRC_ARG_1;
+	if( ptr == 0 ) return S_FAILURE | ERR_INVALID_ARGUMENT | ERRSRC_ARG_2;
+
+	HeapEntry *e = (HeapEntry*)( (u8*)*ptr - sizeof(HeapEntry) );
+
+	/* Link into freelist */
+	*((HeapEntry**)(&e->size + 1)) = h->freelist_data;
+	h->freelist_data = e;
+
+	*ptr = 0;
+
+	return S_SUCCESS;
+}
+
+
+#endif

@@ -1,23 +1,26 @@
 #ifndef NOTLIBC_HEADER_MEMORY_HEAP_INCLUDED
 #define NOTLIBC_HEADER_MEMORY_HEAP_INCLUDED
 
-#include "memory/arena.h"
+#include "datatypes/error.h"
+#include "platform/info/build.h"
 
-STRUCT( HeapEntry,
-	DEBUG( usize checksum; ) /* for detecting heap corruption and bad pointers */
-	usize size;
-	struct _HeapEntry *next;
-	u8 data[]; /* The above pointer should gives a sane alignment here despite this being u8 */
-);
+#ifdef NOTLIBC_IMPLEMENT
+	#if BUILD_TYPE == BUILD_RELEASE
+		#include "./heap/heap_release.h"
+	#elif BUILD_TYPE == BUILD_DEBUG
+		#include "./heap/heap_debug.h"
+	#endif
+#endif
+
+ASSERT( sizeof(HeapEntry)%sizeof(usize) == 0 );
 
-STRUCT( Heap,
-	Arena arena; /* Heap is built on top of arena. It's just an arena + a freelist with metadata */
-	HeapEntry *freelist;
-);
+typedef struct _Heap Heap;
 
 Status Heap_create( Heap *out, usize size ); /* size - size of underlying arena. The heap will hold less, due to bookkeeping overhead for allocations. */
 
-Status Heap_take( Heap *h, usize amount, u8 **out );
-Status Heap_give( Heap *h, u8 *ptr );
+Status Heap_alloc( Heap *h, usize amount, u8 **out );
+Status Heap_free( Heap *h, u8 **ptr ); /* u8** cause it zeroes the pointer on success automatically. */
+
+Status Heap_destroy( Heap *h );
 
 #endif

@@ -32,7 +32,6 @@ static inline void* mem_copy( void *source, void *destination, u64 len ) {
 
 static inline void* mem_set( void *start, u64 len, u8 value ) {
 	assert(start != 0);
-	assert(len != 0);
 	u8 *s = start;
 	u64 i = 0;
 
@@ -59,6 +58,16 @@ void *memset( void* ptr, int value, unsigned long count ) {
 	return ptr;
 }
 
+ void *memcpy( void *dest, const void *src, unsigned long n );
+
+void *memcpy( void *dest, const void *src, unsigned long n ) {
+	char *d = dest;
+	const char *s = src;
+	while(n--)
+		*d++ = *s++;
+	return dest;
+}
+
 #endif
 
 

@@ -113,6 +113,10 @@ typedef struct _##name { \
 	__VA_ARGS__ \
 } name
 
+
+#define STRUCT_FIELD_OFFSET( T, fieldname ) \
+	((usize)&(((T*)0)->fieldname))
+
 /* Cross-compiler packed struct declarator */
 #if COMPILER == COMPILER_GCC || COMPILER == COMPILER_CLANG || COMPILER == COMPILER_TCC
 

@@ -15,6 +15,13 @@
 	#include PLATFORM_FILE_HEADER
 #endif
 
+#define HEAP_HEADER_GUARD_NUMBER  0xc0dedeaddeadc0de
+#define HEAP_OVERRUN_GUARD_NUMBER 0xeeeedeaddeadeeee
+#define HEAP_XOR_KEY              0x0e0e0e0e0e0e0e0e
+#define MAGIC_UNINITIALIZED_MEM 0xf0
+#define MAGIC_POISONED_MEM 0xfc
+#define MAGIC_FREED_MEM 0xfe
+
 
 /* Compiler-specific debugging/checking system implementations */
 #if (COMPILER == COMPILER_GCC || COMPILER == COMPILER_CLANG) && defined(NOTLIBC_IMPLEMENT) 

@@ -0,0 +1,38 @@
+#include "notlibc/core.h"
+
+void entry(void) {
+
+	Heap h = {0};
+
+	assert(S_OK( Heap_create( &h, KiB(8) ) ));
+
+	u8 *ptr1 = 0;
+	u8 *ptr2 = 0;
+	assert(S_OK( Heap_alloc( &h, 32, &ptr1 ) ));
+	assert(S_OK( Heap_alloc( &h, 32, &ptr2 ) ));
+
+	u8 *original_ptr1 = ptr1;
+
+	for( usize i = 0; i < 32; ++i ) {
+		ptr1[i] = 'h';
+		ptr2[i] = 'i';
+	}
+
+	assert(S_OK( Heap_free( &h, &ptr1 ) ));
+
+	#if BUILD_TYPE == BUILD_RELEASE
+		assert(S_NOK( Heap_alloc( &h, 0, &ptr1 ) ));
+	#endif
+
+	u8 *ptr3 = 0;
+	assert(S_OK( Heap_alloc( &h, 32, &ptr3 ) ));
+
+	assert( ptr3 == original_ptr1 );
+
+	assert(S_OK( Heap_free( &h, &ptr3 ) ));
+	assert(S_OK( Heap_free( &h, &ptr2 ) ));
+
+	assert(S_OK( Heap_destroy( &h ) ));
+
+	terminate(0);
+}