From 5b5eca5fabadb33923b40f2864300d66d549c2b4 Mon Sep 17 00:00:00 2001 From: Brendan Hansen Date: Fri, 23 Apr 2021 22:48:06 -0500 Subject: [PATCH] bug fixes with a better heap allocator --- core/alloc/heap.onyx | 157 +++++++++++++++++++++++++++++--------- core/container/array.onyx | 30 +++++++- core/stdio.onyx | 40 ++++++++++ tests/aoc-2020/day1.onyx | 2 - tests/aoc-2020/day19.onyx | 2 +- tests/aoc-2020/day21.onyx | 2 +- 6 files changed, 190 insertions(+), 43 deletions(-) diff --git a/core/alloc/heap.onyx b/core/alloc/heap.onyx index be78fd39..7861f070 100644 --- a/core/alloc/heap.onyx +++ b/core/alloc/heap.onyx @@ -1,5 +1,7 @@ package core.alloc.heap +enable_debug := false + // This is the implementation for the general purpose heap allocator. // It is a simple bump allocator, with a free list. It is not very good // but it suffices for the kinds of things being done in the early days @@ -8,42 +10,85 @@ package core.alloc.heap #load "core/intrinsics/wasm" +uintptr :: #type u32 + use package core.intrinsics.wasm { memory_size, memory_grow, - memory_copy, + memory_copy, memory_fill, } #private_file memory :: package core.memory +#private_file math :: package core.math // The global heap state #private_file heap_state : struct { - free_list : ^heap_block; + free_list : ^heap_freed_block; next_alloc : rawptr; remaining_space : u32; } #private_file heap_block :: struct { - size : u32; - next : ^heap_block; + size : u32; + magic_number : u32; +} + +#private_file +heap_freed_block :: struct { + use base: heap_block; + next : ^heap_freed_block; + prev : ^heap_freed_block; +} + +#private_file +heap_allocated_block :: struct { + use base: heap_block; } +#private_file Allocated_Flag :: 0x1 +#private_file Free_Block_Magic_Number :: 0xdeadbeef +#private_file Block_Split_Size :: 512 + // FIX: This does not respect the choice of alignment #private_file heap_alloc :: (size_: u32, align: u32) -> rawptr { if size_ == 0 do return null; size := size_ + sizeof heap_block; + size = math.max(size, sizeof heap_freed_block); memory.align(~~^size, ~~align); prev := ^heap_state.free_list; hb := heap_state.free_list; while hb != null { if hb.size >= size { - *prev = hb.next; - hb.next = null; + if enable_debug { + assert(hb.size & Allocated_Flag == 0, "Allocated block in free list."); + assert(hb.magic_number == Free_Block_Magic_Number, "Malformed free block in free list."); + } + + if hb.size - size >= Block_Split_Size { + hb.size = size; + + new_block := cast(^heap_freed_block) (cast(uintptr) hb + size); + new_block.size = hb.size - size; + new_block.next = hb.next; + new_block.prev = hb.prev; + new_block.magic_number = Free_Block_Magic_Number; + + if hb.next != null do hb.next.prev = new_block; + *prev = new_block; + + } else { + if hb.next != null do hb.next.prev = hb.prev; + *prev = hb.next; + } - return cast(rawptr) (cast(u32) hb + sizeof heap_block); + hb.next = null; + hb.prev = null; + hb.magic_number = 0; + hb.size |= Allocated_Flag; + return cast(rawptr) (cast(uintptr) hb + sizeof heap_allocated_block); } prev = ^hb.next; @@ -51,14 +96,14 @@ heap_alloc :: (size_: u32, align: u32) -> rawptr { } if size < heap_state.remaining_space { - ret := cast(^heap_block) heap_state.next_alloc; + ret := cast(^heap_allocated_block) heap_state.next_alloc; ret.size = size; - ret.next = null; + ret.size |= Allocated_Flag; - heap_state.next_alloc = cast(rawptr) (cast(u32) heap_state.next_alloc + size); + heap_state.next_alloc = cast(rawptr) (cast(uintptr) heap_state.next_alloc + size); heap_state.remaining_space -= size; - return cast(rawptr) (cast(u32) ret + sizeof heap_block); + return cast(rawptr) (cast(uintptr) ret + sizeof heap_allocated_block); } new_pages := ((size - heap_state.remaining_space) >> 16) + 1; @@ -68,42 +113,81 @@ heap_alloc :: (size_: u32, align: u32) -> rawptr { } heap_state.remaining_space += new_pages << 16; - ret := cast(^heap_block) heap_state.next_alloc; + ret := cast(^heap_allocated_block) heap_state.next_alloc; ret.size = size; - ret.next = null; + ret.size |= Allocated_Flag; - heap_state.next_alloc = cast(rawptr) (cast(u32) heap_state.next_alloc + size); + heap_state.next_alloc = cast(rawptr) (cast(uintptr) heap_state.next_alloc + size); heap_state.remaining_space -= size; - return cast(rawptr) (cast(u32) ret + sizeof heap_block); + return cast(rawptr) (cast(uintptr) ret + sizeof heap_allocated_block); } #private_file heap_free :: (ptr: rawptr) { - hb_ptr := cast(^heap_block) (cast(u32) ptr - sizeof heap_block); + if enable_debug do assert(ptr != null, "Trying to free a null pointer."); + + hb_ptr := cast(^heap_freed_block) (cast(uintptr) ptr - sizeof heap_allocated_block); + if enable_debug do assert(hb_ptr.size & Allocated_Flag == Allocated_Flag, "Corrupted heap on free. This could be due to a double free, or using memory past were you allocated it."); + + hb_ptr.size &= ~Allocated_Flag; + orig_size := hb_ptr.size - sizeof heap_allocated_block; + + if enable_debug do memory_fill(ptr, ~~0xcc, orig_size); - // DEBUGGING: Fills freed memory with 0's - // for i: 0, hb_ptr.size do (cast(^u8) ptr)[i] = cast(u8) 0; + // CLEANUP: This is not complete. This only checks if the block after the freed block is also free. + // There are three other cases related to the block before this one that need to be handled for + // the best efficiency and minimal fragmentation. + if cast(uintptr) hb_ptr + hb_ptr.size < cast(uintptr) heap_state.next_alloc { + next_block := cast(^heap_freed_block) (cast(uintptr) hb_ptr + hb_ptr.size); + + if next_block.size & Allocated_Flag == 0 && next_block.magic_number == Free_Block_Magic_Number { + hb_ptr.size += next_block.size; + + if next_block.next != null do next_block.next.prev = next_block.prev; + if next_block.prev != null do next_block.prev.next = next_block.next; + else do heap_state.free_list = next_block.next; + + next_block.next = null; + next_block.prev = null; + } + } + hb_ptr.magic_number = Free_Block_Magic_Number; + hb_ptr.prev = null; hb_ptr.next = heap_state.free_list; + + if heap_state.free_list != null do heap_state.free_list.prev = hb_ptr; heap_state.free_list = hb_ptr; } #private_file -heap_resize :: (ptr: rawptr, new_size: u32, align: u32) -> rawptr { +heap_resize :: (ptr: rawptr, new_size_: u32, align: u32) -> rawptr { if ptr == null do return null; + + new_size := new_size_ + sizeof heap_block; + new_size = math.max(new_size, sizeof heap_freed_block); + new_size = ~~memory.align(cast(u64) new_size, ~~align); - hb_ptr := cast(^heap_block) (cast(u32) ptr - sizeof heap_block); - old_size := hb_ptr.size - sizeof heap_block; + hb_ptr := cast(^heap_allocated_block) (cast(uintptr) ptr - sizeof heap_allocated_block); + if enable_debug do assert(hb_ptr.size & Allocated_Flag == Allocated_Flag, "Corrupted heap on resize."); + hb_ptr.size &= ~Allocated_Flag; + + old_size := hb_ptr.size; // If there is already enough space in the current allocated block, // just return the block that already exists and has the memory in it. - if old_size >= new_size do return ptr; + if old_size >= new_size { + hb_ptr.size |= Allocated_Flag; + return ptr; + } // If we are at the end of the allocation space, just extend it - if hb_ptr.size + cast(u32) ptr >= cast(u32) heap_state.next_alloc { - if new_size - old_size >= heap_state.remaining_space { - new_pages := ((new_size - old_size - heap_state.remaining_space) >> 16) + 1; + if cast(uintptr) hb_ptr + hb_ptr.size >= cast(uintptr) heap_state.next_alloc { + needed_size := cast(u32) memory.align(cast(u64) (new_size - old_size), 16); + + if needed_size >= heap_state.remaining_space { + new_pages := ((needed_size - heap_state.remaining_space) >> 16) + 1; if memory_grow(new_pages) == -1 { // out of memory return null; @@ -111,25 +195,26 @@ heap_resize :: (ptr: rawptr, new_size: u32, align: u32) -> rawptr { heap_state.remaining_space += new_pages << 16; } - hb_ptr.size = new_size + sizeof heap_block; - heap_state.next_alloc = cast(rawptr) (cast(u32) ptr + hb_ptr.size); - heap_state.remaining_space -= new_size - old_size; + hb_ptr.size = new_size; + hb_ptr.size |= Allocated_Flag; + heap_state.next_alloc = cast(rawptr) (cast(uintptr) heap_state.next_alloc + needed_size); + heap_state.remaining_space -= needed_size; return ptr; } - new_ptr := heap_alloc(new_size, align); - memory_copy(new_ptr, ptr, old_size); + hb_ptr.size |= Allocated_Flag; + new_ptr := heap_alloc(new_size_, align); + memory_copy(new_ptr, ptr, old_size - sizeof heap_block); heap_free(ptr); return new_ptr; } #private_file heap_alloc_proc :: (data: rawptr, aa: AllocationAction, size: u32, align: u32, oldptr: rawptr) -> rawptr { - if aa == .Alloc do return heap_alloc(size, align); - if aa == .Resize do return heap_resize(oldptr, size, align); - if aa == .Free { - heap_free(oldptr); - return null; + switch aa { + case .Alloc do return heap_alloc(size, align); + case .Resize do return heap_resize(oldptr, size, align); + case .Free do heap_free(oldptr); } return null; @@ -137,7 +222,7 @@ heap_alloc_proc :: (data: rawptr, aa: AllocationAction, size: u32, align: u32, o init :: () { heap_state.free_list = null; - heap_state.next_alloc = __heap_start; + heap_state.next_alloc = cast(rawptr) (cast(uintptr) __heap_start + 8); heap_state.remaining_space = (memory_size() << 16) - cast(u32) __heap_start; use package core.alloc { heap_allocator } diff --git a/core/container/array.onyx b/core/container/array.onyx index 20f5ac38..98ca56b8 100644 --- a/core/container/array.onyx +++ b/core/container/array.onyx @@ -1,5 +1,7 @@ package core.array +use package core.intrinsics.onyx { __zero_value } + // [..] T == Array(T) // where // Array :: struct (T: type_expr) { @@ -128,6 +130,8 @@ fast_delete :: (arr: ^[..] $T, idx: u32) { } pop :: (arr: ^[..] $T) -> T { + if arr.count == 0 do return __zero_value(T); + arr.count -= 1; return arr.data[arr.count]; } @@ -180,15 +184,35 @@ sort :: (arr: ^[..] $T, cmp: (T, T) -> i32) { x := arr.data[i]; j := i - 1; - while j >= 0 && cmp(arr.data[j], x) > 0 { - arr.data[j + 1] = arr.data[j]; - j -= 1; + // NOTE: This is written this way because '&&' does not short circuit right now. + while j >= 0 { + if cmp(arr.data[j], x) > 0 { + arr.data[j + 1] = arr.data[j]; + j -= 1; + } else { + break; + } } arr.data[j + 1] = x; } } +sort_ptr :: (arr: ^[..] $T, cmp: (^T, ^T) -> i32) { + for i: 1 .. arr.count { + j := i; + + while j > 0 { + if cmp(^arr.data[j - 1], ^arr.data[j]) > 0 { + arr.data[j], arr.data[j - 1] = arr.data[j - 1], arr.data[j]; + j -= 1; + } else { + break; + } + } + } +} + fold :: proc { (arr: ^[..] $T, init: $R, f: (T, R) -> R) -> R { val := init; diff --git a/core/stdio.onyx b/core/stdio.onyx index f92d4603..c0540a18 100644 --- a/core/stdio.onyx +++ b/core/stdio.onyx @@ -55,6 +55,46 @@ print_array :: proc { } } +byte_dump :: (ptr: rawptr, byte_count: u32) { + temp: [3] u8; + + u8_ptr := cast(^u8) ptr; + for i: byte_count { + val := u8_ptr[i]; + + temp[0] = map_to_ascii(val >> 4); + temp[1] = map_to_ascii(val & 15); + temp[2] = #char " "; + + runtime.__output_string(.{ ~~temp, 3 }); + + if i % 8 == 7 do runtime.__output_string("\n"); + } + + + map_to_ascii :: (x: u8) -> u8 { + switch x { + case 0 do return #char "0"; + case 1 do return #char "1"; + case 2 do return #char "2"; + case 3 do return #char "3"; + case 4 do return #char "4"; + case 5 do return #char "5"; + case 6 do return #char "6"; + case 7 do return #char "7"; + case 8 do return #char "8"; + case 9 do return #char "9"; + case 10 do return #char "A"; + case 11 do return #char "B"; + case 12 do return #char "C"; + case 13 do return #char "D"; + case 14 do return #char "E"; + case 15 do return #char "F"; + case #default do return #char "X"; + } + } +} + // // Private and internal things diff --git a/tests/aoc-2020/day1.onyx b/tests/aoc-2020/day1.onyx index e0cf261f..e3a570ec 100644 --- a/tests/aoc-2020/day1.onyx +++ b/tests/aoc-2020/day1.onyx @@ -4,8 +4,6 @@ use package core main :: (args: [] cstr) { contents := #file_contents "./tests/aoc-2020/input/day1.txt"; - contents_orig := contents; - defer cfree(contents_orig.data); nums := array.make(u32, 128); defer array.free(^nums); diff --git a/tests/aoc-2020/day19.onyx b/tests/aoc-2020/day19.onyx index 5b0ded1d..928e1d72 100644 --- a/tests/aoc-2020/day19.onyx +++ b/tests/aoc-2020/day19.onyx @@ -169,7 +169,7 @@ main :: (args: [] cstr) { while !reader.empty(^file) { line := reader.read_line(^file); if cyk_algorithm(^grammar, line) do valid_count += 1; - } + } printf("Valid count: %i\n", valid_count); } diff --git a/tests/aoc-2020/day21.onyx b/tests/aoc-2020/day21.onyx index 12fb70d1..5649e72a 100644 --- a/tests/aoc-2020/day21.onyx +++ b/tests/aoc-2020/day21.onyx @@ -162,7 +162,7 @@ main :: (args: [] cstr) { } } - array.sort(^matched_ingredients, (i1: Ingredient, i2: Ingredient) -> i32 { + array.sort_ptr(^matched_ingredients, (i1: ^Ingredient, i2: ^Ingredient) -> i32 { return string.compare(i1.allergen, i2.allergen); }); -- 2.25.1