From ebec2a9fe107ff6c8e97b579cba6569f116ff822 Mon Sep 17 00:00:00 2001 From: Moon Flower Date: Wed, 5 Mar 2025 20:11:24 +0330 Subject: Garbage collector and minor updates --- Makefile | 2 +- README.md | 16 +-- main.c | 44 ++++++-- moonshine.h | 340 ++++++++++++++++++++++++++++++++++++++++++++++++++++-------- 4 files changed, 342 insertions(+), 60 deletions(-) diff --git a/Makefile b/Makefile index a763c2a..135e0a6 100644 --- a/Makefile +++ b/Makefile @@ -11,7 +11,7 @@ m4: m4 moonshine.m4 > moonshine.m4.h c: - clang main.c -o out.bin $(FLAGS) -O3 + clang main.c -o out.bin $(FLAGS) test: ./out.bin diff --git a/README.md b/README.md index 48287d4..b6877ea 100644 --- a/README.md +++ b/README.md @@ -4,28 +4,30 @@ This library aims to be a drop-in libc replacement for most C projects, whilst a It already supports the system calls and library functions which were necessary for its functionality, but more stdlib support should come soon. This library relies upon nothing but the C language itself, not even the standard library headers that C often uses, such as stdlib.h, unistd.h, etc. Its current features are: -- Self-defined types such as `var` for `void*`, `string` for `char*`, `u8` for `uint64_t`, and const-correct types such as `car` for `const void*` and `ctring` for `const char*` -- Global print statement, takes up to 512 arguments of any type, and figures out how to print them out by itself. (Currently does not support custom structs). Example: `print("hello, ", "world!")`, `print("The sum is: ", 2 + 5)`, `print("I have a pointer with size ", pointer_size, " and address ", pointer)` +- Mark & Sweep garbage collector for responsible memory management (must be manually called, for now) - Easy array creation: `new(int)`, `new(char, 4)`, `fill(int, 2, 4, 5)`, `fill(string, "hello", "world")`, `single("string")`, `single(22.4)` +- Global print statement, takes up to 512 arguments of any type, and figures out how to print them out by itself. (Currently does not support custom structs). Example: `print("hello, ", "world!")`, `print("The sum is: ", 2 + 5)`, `print("I have a pointer with size ", pointer_size, " and address ", pointer)` +- Algebraic data types using the `datatype` macro, eg. `datatype(binarytree, ((leaf, int), (node, binarytree *, int, binarytree *) ));` +- Self-defined types such as `var` for `void*`, `string` for `char*`, `u8` for `uint64_t`, and const-correct types such as `car` for `const void*` and `ctring` for `const char*` - Basic type coercion: `auto x = 4; auto y = 9.0; auto z = "Hello!";` +- Custom float type for more accuracy and ease-of-use +- Convert file sizes to a human readable format +- Array processing macros such as `map` and `reduce` which can be used such as `map((output_type, array), item_name, ({ expression; }))` - Easy system calls: `syscall2(60, 0); // 60 = SYS_exit` - Const-correct stdlib functions: `exit`, `fork`, `getchar`, `putchar`, `strlen`, `memset`, `memmove`, etc - Made-from-scratch stdout buffer management: `write`, `flush`, etc - Deprecation warnings for functions such as `malloc`, `realloc` and `free` - Intelligent and safe memory management using `alloc`, `remap` and `release` -- Pointer ownership trick, using `mine(var ptr)` +- Performant hash array implementation +- Pointer ownership trick, using `mine(var ptr)` (requires a revamp) - Easy array manipulation with `push(array, item)` - Array bounds checking using `get(array, index)`, `set(array, index, value)`, `count(array)`, `last(array)` and metadata using `element_size(array)` - Foreach loops using `foreach(item in array) { print(item); }` - Revamped stdlib functions such as `char* strdup(const char* str) -> t(char) strdup(ctring str)` - Array manipulation using `reverse_array(array)` which returns the reversed array and also reverses it in-place. - Custom `_start` function that initializes moonshine functionality whilst still keeping the ease of use of the libc `main` function. -- Algebraic data types using the `datatype` macro, eg. `datatype(binarytree, ((leaf, int), (node, binarytree *, int, binarytree *) ));` - Pattern matching using algebraic data types. -- Performant hash array implementation -- Array processing macros such as `map` and `reduce` which can be used such as `map((output_type, array), item_name, ({ expression; }))` The roadmap for moonshine is: -- Implementing Garbage collection - Achieving more libc compatibility - Moving common operations to macros for reduced code size and increased conciseness diff --git a/main.c b/main.c index ccb5f11..8b95eb5 100644 --- a/main.c +++ b/main.c @@ -2,7 +2,17 @@ #include "moonshine.h" -const enum { test_datatype, test_linkedlist, test_hashtable, test_alloc, test_array, test_hashtable_2 } current_test = test_hashtable; +const enum { + test_datatype, + test_linkedlist, + test_hashtable, + test_alloc, + test_array, + test_hashtable_2, + test_garbage_collector, + test_minor_features +} current_test + = test_minor_features; int main() { if (current_test == test_alloc) { @@ -26,15 +36,13 @@ int main() { push(arr, 5); set(arr, 0, 2); - println("Original"); + foreach (i in arr) println("[", (u8) i_index, "] ", i); - foreach(i in arr) println("[", (u8)i_index, "] ", i); + reverse_array(arr); println("Reversed"); - reverse_array(arr); - - foreach(i in arr) println("[", (u8)i_index, "] ", i); + foreach (i in arr) println("[", (u8) i_index, "] ", i); } else if (current_test == test_datatype) { datatype(binarytree, ((leaf, int), (node, binarytree *, int, binarytree *) )); const auto tree = instance(binarytree, leaf, 3); @@ -53,8 +61,7 @@ int main() { print((u8) index_to_ptr(ll, 12)->data); } else if (current_test == test_hashtable) { - const auto ht = create_hasharray( - table_hash_2); + const auto ht = create_hasharray(table_hash_2); for (u8 i = 0; i < 10000000; i++) { if (i % 1000000 == 0) println("I ", i); @@ -67,9 +74,26 @@ int main() { const auto ht = create_hasharray(table_hash_2); set_hasharray(ht, "hello", "hi"); - println("Value: ", (string)get_hasharray(ht, "hello")); + println("Value: ", (string) get_hasharray(ht, "hello")); set_hasharray(ht, "hello", "meow"); - println("Value after: ", (string)get_hasharray(ht, "hello")); + println("Value after: ", (string) get_hasharray(ht, "hello")); + } else if (current_test == test_garbage_collector) { + auto v1 = new (int, 5); + auto v2 = obj(int); + auto v3 = alloc(25); + auto v4 = create_linkedlist(); + auto v5 = create_hasharray(table_hash_2); + + set_hasharray(v5, "hello", "world"); + println("Hash ", v5); + + collect_garbage(true); + } else if (current_test == test_minor_features) { + // Minor feature: Custom, better designed float representation + auto x = (struct moonshine_float) { .number = 1234, .decimal = 2 }; + println(x); + // Normal float enhancement + println(12.34); } else { diff --git a/moonshine.h b/moonshine.h index 241f365..d560ddc 100644 --- a/moonshine.h +++ b/moonshine.h @@ -98,6 +98,7 @@ int errno = 0; #endif #define __WORDSIZE_TIME64_COMPAT32 1 +typedef long unsigned int size_t; #ifdef __x86_64__ #define __syscall_WORDSIZE 64 @@ -224,6 +225,13 @@ const bool false = 0; static char buffer[ BUFFER_SIZE ]; static int buffer_index = 0; +__attribute__((diagnose_as_builtin(__builtin_memcpy, 1, 2, 3))) void memcpy(var _dest, car _src, const unsigned long n) { + string dest = _dest; + ctring src = _src; + + for (u8 i = 0; i < n; i++) dest[ i ] = src[ i ]; +} + int flush(int fd); int flush(int fd) { @@ -310,31 +318,72 @@ void puts_number(const int64_t number, const bool is_signed) { for (int i = pos; i < 20; ++i) { putchar(buffer[ i ]); } } -void puts_float(const float number) { - int int_part = (int) number; - float frac_part = number - int_part; +int sign_bit(float f) { + u4 bits; + memcpy(&bits, &f, sizeof(bits)); + return (bits >> 31) & 1; +} - if (int_part < 0) { - putchar('-'); - int_part = -int_part; +bool is_infinity(float f) { + u4 bits; + memcpy(&bits, &f, sizeof(bits)); + return (bits & 0x7fffffff) == 0x7f800000; +} + +bool is_nan(float f) { + u4 bits; + memcpy(&bits, &f, sizeof(bits)); + return (bits & 0x7f800000) == 0x7f800000 && (bits & 0x007fffff) != 0; +} + +void puts_float(const double number) { + if (is_nan(number)) { + puts_static("nan"); + return; + } + if (is_infinity(number)) { + if (sign_bit(number)) putchar('-'); + puts_static("inf"); + return; } - char int_buffer[ 12 ]; - int i = 0; - do { - int_buffer[ i++ ] = (int_part % 10) + '0'; - int_part /= 10; - } while (int_part > 0); + double num = number; + + bool is_negative = number < 0; + if (is_negative) num = -num; + + int64_t int_part = (int64_t) num; + double frac_part = num - (double) int_part; + + int64_t frac_scaled = (int64_t) (frac_part * 1000000.0 + 0.5); + if (frac_scaled >= 1000000) { + int_part++; + frac_scaled = 0; + } + + if (is_negative) putchar('-'); - while (i > 0) { putchar(int_buffer[ --i ]); } + puts_number(int_part, false); - putchar('.'); + if (frac_scaled == 0) return; - for (int j = 0; j < 6; j++) { - frac_part *= 10; - int frac_digit = (int) frac_part; - putchar(frac_digit + '0'); - frac_part -= frac_digit; + char frac_digits[ 6 ]; + for (int i = 5; i >= 0; i--) { + frac_digits[ i ] = (frac_scaled % 10) + '0'; + frac_scaled /= 10; + } + + int last_non_zero = -1; + for (int i = 5; i >= 0; i--) { + if (frac_digits[ i ] != '0') { + last_non_zero = i; + break; + } + } + + if (last_non_zero >= 0) { + putchar('.'); + for (int i = 0; i <= last_non_zero; i++) { putchar(frac_digits[ i ]); } } } @@ -455,9 +504,21 @@ int wait(const int *status) { return result; } +struct FoundPointer { + i8 page_index; + i8 allocation_size; + struct AllocatedPointer *pointer_ref; + struct Page *page_ref; +}; + +fn_line struct FoundPointer find_pointer(const var addr, bool throw_on_error); + +// TODO: Replace this with a pointer finder by borrowing logic from the GC + // Check if the current process tree owns a pointer. Expensive, do not use // sparingly. bool mine(const ptr pointer) { + // Old approach, slow bool *glob_var = __bare_alloc(sizeof(bool)); (void) demon({ @@ -477,6 +538,53 @@ bool mine(const ptr pointer) { return output; } +enum human_readable_size { hrs_byte, hrs_kilobyte, hrs_megabyte, hrs_gigabyte }; +string human_readable_size_names[] = { "byte", "kilobyte", "megabyte", "gigabyte" }; + +struct human_readable_size_layout { + enum human_readable_size size; + float count; +}; + +struct human_readable_size_layout calculate_human_readable_size(u8 size) { + if (size < 1000) return (struct human_readable_size_layout) { .count = size, .size = hrs_byte }; + if (size < 1000000) { + return (struct human_readable_size_layout) { .count = (float) ((u8) size / 10) / 100, .size = hrs_kilobyte }; + } + if (size < 1000000000) { + return (struct human_readable_size_layout) { .count = (float) ((u8) size / 10000) / 100, .size = hrs_megabyte }; + } + return (struct human_readable_size_layout) { .count = (float) ((u8) size / 10000000) / 100, .size = hrs_gigabyte }; +} + +struct moonshine_float { + u8 number; + byte decimal; +}; + +fn_line void printer(struct human_readable_size_layout x, ctring attr_unused text) { + puts_float(x.count); + putchar(' '); + puts(human_readable_size_names[ x.size ]); + if (x.count != 1.0) putchar('s'); +} +fn_line void printer(struct moonshine_float x, ctring attr_unused text) { + u8 value = x.number; + char buffer[ 20 ]; + byte index = 20; + byte index_1 = 0; + + while (value > 0) { + buffer[ --index ] = value % 10; + value /= 10; + } + + for (byte i = index; i < 20; i++) { + if (i == index && (20 - index) - x.decimal == 0) putchar('0'); + if (index_1++ == (20 - index) - x.decimal) putchar('.'); + putchar(buffer[ i ] + '0'); + } +} fn_line void printer(const char x, ctring attr_unused text) { putchar(x); } fn_line void printer(ctring x, ctring attr_unused text) { puts(x); } fn_line void printer(const int x, ctring text) { @@ -500,6 +608,8 @@ fn_line void printer(const bool x, ctring attr_unused text) { } } fn_line void printer(var x, ctring attr_unused text) { + goto UNKNOWN; + if (mine(x)) { if (mine(*(var *) x)) { // handle array @@ -600,13 +710,6 @@ __attribute__((diagnose_as_builtin(__builtin_memmove, 1, 2, 3))) void *memmove(v return dest; } -__attribute__((diagnose_as_builtin(__builtin_memcpy, 1, 2, 3))) void memcpy(var _dest, car _src, const unsigned long n) { - string dest = _dest; - ctring src = _src; - - for (u8 i = 0; i < n; i++) dest[ i ] = src[ i ]; -} - #define SYS_getpid 39 #define SYS_kill 62 @@ -685,6 +788,7 @@ struct PageTable { u8 size; u8 capacity; struct Page *pages; + u8 pointer_count; }; #define AllocatedPointer(size, location) \ @@ -700,12 +804,10 @@ struct PageTable { .pointers = PageArray() }) #define PageTable() \ - ((struct PageTable) { 0, BASE_PAGE_TABLE_CAPACITY, __bare_alloc(sizeof(struct Page) * BASE_PAGE_TABLE_CAPACITY) }) + ((struct PageTable) { 0, BASE_PAGE_TABLE_CAPACITY, __bare_alloc(sizeof(struct Page) * BASE_PAGE_TABLE_CAPACITY), 0 }) struct PageTable global_page_table; -typedef unsigned int size_t; - static void swap(char *a, char *b, size_t size) { while (size--) { char tmp = *a; @@ -803,8 +905,6 @@ struct FreeBlock find_free_space(struct Page *page) { return max_free; } -#define max(a, b) ((a) > (b) ? (a) : (b)) - void clean_pages() { for (u8 i = 0; i < global_page_table.size; i++) { auto page = &global_page_table.pages[ i ]; @@ -824,6 +924,9 @@ void clean_pages() { } } +#define max(a, b) ((a) > (b) ? (a) : (b)) +#define min(a, b) ((a) < (b) ? (a) : (b)) + // TODO: Place page pointer and pointer size behind the allocated pointer __attribute__((diagnose_as_builtin(__builtin_malloc, 1))) __attribute__((malloc)) var alloc(const u8 len) @@ -872,10 +975,10 @@ __attribute__((diagnose_as_builtin(__builtin_malloc, 1))) __attribute__((malloc) END: - global_page_table.pages[ place ] = Page(max(len, 512)); + global_page_table.pages[ place ] = Page(max(len, 4096)); page = &global_page_table.pages[ place ]; biggest_free_page = place; - max_biggest_free.size = max(len, 512); + max_biggest_free.size = max(len, 4096); max_biggest_free.start = 0; } @@ -906,17 +1009,18 @@ ABYSS:; page->pointers.data[ pointer_place ] = (struct AllocatedPointer) { .size = len, .location = max_biggest_free.start, .allocated = true }; + global_page_table.pointer_count++; return (var) new_location; } -struct FoundPointer { - u8 page_index; - u8 allocation_size; - struct AllocatedPointer *pointer_ref; - struct Page *page_ref; -}; +enum GC_STATUS { GC_ALIVE, GC_DEAD }; -struct FoundPointer find_pointer(const var addr) { +// TODO: find_pointer only handles absolute pointers, whilst mine() needs to handle forward-facing pointers as well, which have +// been altered by pointer arithmetic. +// TODO: Add safeguards to dismiss invalid pointers, fast (like the ones in the GC) + +// Finds a pointer's reference in the page table. +fn_line struct FoundPointer find_pointer(const var addr, bool throw_on_error) { for (u8 i = 0; i < global_page_table.size; i++) { struct Page *page = &global_page_table.pages[ i ]; const u8 location = (u8) addr - (u8) page->start; @@ -933,8 +1037,20 @@ struct FoundPointer find_pointer(const var addr) { } } - if (!best_ptr->allocated) throw("Unallocated pointer? ", addr); - if (best_ptr == NULL) throw("Pointer for location does not exist in page"); + if (best_ptr == NULL) { + if (!throw_on_error) { + return ( + struct FoundPointer) { .page_index = -1, .page_ref = NULL, .pointer_ref = NULL, .allocation_size = -1 }; + } + throw("Pointer for location does not exist in page"); + } + if (!best_ptr->allocated) { + if (!throw_on_error) { + return ( + struct FoundPointer) { .page_index = -1, .page_ref = NULL, .pointer_ref = NULL, .allocation_size = -1 }; + } + throw("Unallocated pointer? ", addr); + } return (struct FoundPointer) { .allocation_size = best_ptr->size, .pointer_ref = best_ptr, .page_ref = page, .page_index = i @@ -942,14 +1058,20 @@ struct FoundPointer find_pointer(const var addr) { } } + if (!throw_on_error) { + return (struct FoundPointer) { .page_index = -1, .page_ref = NULL, .pointer_ref = NULL, .allocation_size = -1 }; + } throw("Invalid pointer!"); } +fn_line struct FoundPointer find_pointer(const var addr) { return find_pointer(addr, true); } + void unmap(const struct FoundPointer ptr, const var addr) { if (!ptr.pointer_ref->allocated) throw("unmap double-free for pointer ", addr); ptr.pointer_ref->allocated = false; ptr.page_ref->dirty = true; + global_page_table.pointer_count--; } __attribute__((diagnose_as_builtin(__builtin_free, 1))) void release(const var addr) { @@ -966,6 +1088,138 @@ __attribute__((diagnose_as_builtin(__builtin_realloc, 1, 2))) var remap(const va return new_ptr; } +u8 start_of_stack; + +// Basic Mark & Sweep garbage collector. Slow, use with caution. +void collect_garbage(bool debug) { + u8 end_of_stack = (u8) &debug; + + u8 start = min(start_of_stack, end_of_stack); + u8 end = max(start_of_stack, end_of_stack); + + struct GC_Ptr { + enum GC_STATUS status; + var ptr; + u8 size; + } marks[ global_page_table.pointer_count ]; + memset(marks, 0, global_page_table.pointer_count * sizeof(typeof(marks[ 0 ]))); + u8 marks_index = 0; + + struct GC_Page_Range { + var start_location; + var end_location; + u8 marks_position; + u8 marks_end; + } page_ranges[ global_page_table.size ]; + u8 ranges_index = 0; + + u8 min_page_start = ~(u8) NULL; + u8 max_page_end = 0; + + for (u8 page_index = 0; page_index < global_page_table.size; page_index++) { + auto page = global_page_table.pages[ page_index ]; + + if (page.start == NULL) continue; + + if ((u8) page.start < min_page_start) min_page_start = (u8) page.start; + if ((u8) (page.start + page.size) > max_page_end) max_page_end = (u8) page.start + page.size; + + u8 marks_start = marks_index; + + for (u8 ptr_index = 0; ptr_index < page.pointers.size; ptr_index++) { + auto ptr = page.pointers.data[ ptr_index ]; + if (!ptr.allocated) continue; + + marks[ marks_index++ ] = (struct GC_Ptr) { .ptr = page.start + ptr.location, .size = ptr.size, .status = GC_DEAD }; + } + + page_ranges[ ranges_index++ ] = (struct GC_Page_Range) { .start_location = page.start, + .end_location = page.start + page.size, + .marks_position = marks_start, + .marks_end = marks_index }; + } + + // Check stack values for references + for (u8 st = start; st < end; st++) { + auto ptr = (var) st; + auto value = *(u8 *) ptr; + + if (value < min_page_start || value > max_page_end) continue; + + // Value is in range of page data + for (u8 page_idx = 0; page_idx < ranges_index; page_idx++) { + auto page = page_ranges[ page_idx ]; + if (value < (u8) page.start_location || value > (u8) page.end_location) continue; + + // Value is in this page! + for (u8 marks_idx = page.marks_position; marks_idx <= page.marks_end; marks_idx++) { + auto mark = marks[ marks_idx ]; + + if (((var) value < mark.ptr) || ((var) value >= (mark.ptr + mark.size))) continue; + // We found the pointer! Woohoo! + marks[ marks_idx ].status = GC_ALIVE; + st += sizeof(var) - 1; // Increment the stack pointer, since we've already found a pointer there + goto TOP_LEVEL_CONTINUE; + } + } + TOP_LEVEL_CONTINUE:; + } + + // Iterate over living pointers, and mark other living pointers inside, until we run out of newly marked pointers + bool all_marked = false; + + while (!all_marked) { + all_marked = true; + for (u8 ptr_idx = 0; ptr_idx < marks_index; ptr_idx++) { + if (marks[ ptr_idx ].status == GC_DEAD) continue; + + // Pointer is alive. Get value. + auto ptr = marks[ ptr_idx ]; + + for (u8 ptr_var = 0; ptr_var < ptr.size; ptr_var++) { + u8 *pointer = ptr.ptr + ptr_var; + u8 value = *(u8 *) pointer; + + if (value < min_page_start || value > max_page_end) continue; + + // Value is in range of page data + for (u8 page_idx = 0; page_idx < ranges_index; page_idx++) { + auto page = page_ranges[ page_idx ]; + if (value < (u8) page.start_location || value > (u8) page.end_location) continue; + + // Value is in this page! + for (u8 marks_idx = page.marks_position; marks_idx < marks_index; marks_idx++) { + auto mark = marks[ marks_idx ]; + + if ((var) value < mark.ptr || (var) value >= mark.ptr + mark.size) continue; + // We found the pointer! Woohoo! + if (mark.status != GC_ALIVE) { + marks[ marks_idx ].status = GC_ALIVE; + all_marked = false; + } + ptr_var += sizeof(var) - 1; // Increment the pointer value, since we've already found a pointer there + goto NEXT_CONTINUE; + } + } + + NEXT_CONTINUE:; + } + } + } + + u8 total_saved = 0; + + for (u8 m = 0; m < marks_index; m++) { + auto mark = marks[ m ]; + if (mark.status == GC_DEAD) { + release(mark.ptr); + total_saved += mark.size; + } + } + + if (debug) println("Saved ", calculate_human_readable_size(total_saved), " of memory"); +} + #define de(obj) (*(obj)) const var *__new_array(const string type_name, const u4 type_size, const u4 count) [[clang::allocating]] { @@ -1624,6 +1878,8 @@ extern void __llvm_profile_set_filename(const char *name); #endif [[noreturn]] __attribute__((used)) void __moonshine_start(int argc, string *argv, string *envp) { + start_of_stack = (u8) &argc; + #ifdef __MOONSHINE_PROFILER static const char profile_filename[] __attribute__((used)) = "profile.profraw"; __llvm_profile_reset_counters(); -- cgit v1.2.3