From 391ed256d21a6ae2e2456d1809f357e6e96e15d1 Mon Sep 17 00:00:00 2001 From: Marvin Borner Date: Mon, 20 Jan 2020 23:12:54 +0100 Subject: Added pure awesomeness Actually quite some days of work but ok --- src/kernel/memory/kheap.c | 311 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 311 insertions(+) create mode 100644 src/kernel/memory/kheap.c (limited to 'src/kernel/memory/kheap.c') diff --git a/src/kernel/memory/kheap.c b/src/kernel/memory/kheap.c new file mode 100644 index 0000000..def9ca2 --- /dev/null +++ b/src/kernel/memory/kheap.c @@ -0,0 +1,311 @@ +#include +#include +#include +#include + +uint32_t placement_address = (uint32_t) &ASM_KERNEL_END; +extern page_directory_t *kernel_directory; +heap_t *kheap = 0; + +uint32_t kmalloc_int(uint32_t sz, int align, uint32_t *phys) +{ + if (kheap != 0) { + void *addr = alloc(sz, (uint8_t) align, kheap); + if (phys != 0) { + page_t *page = get_page((uint32_t) addr, 0, kernel_directory); + *phys = page->frame * 0x1000 + ((uint32_t) addr & 0xFFF); + } + return (uint32_t) addr; + } else { + if (align == 1 && (placement_address & 0xFFFFF000)) { + placement_address &= 0xFFFFF000; + placement_address += 0x1000; + } + if (phys) { + *phys = placement_address; + } + uint32_t tmp = placement_address; + placement_address += sz; + return tmp; + } +} + +void kfree(void *p) +{ + free(p, kheap); +} + +uint32_t kmalloc_a(uint32_t sz) +{ + return kmalloc_int(sz, 1, 0); +} + +uint32_t kmalloc_p(uint32_t sz, uint32_t *phys) +{ + return kmalloc_int(sz, 0, phys); +} + +uint32_t kmalloc_ap(uint32_t sz, uint32_t *phys) +{ + return kmalloc_int(sz, 1, phys); +} + +uint32_t kmalloc(uint32_t sz) +{ + return kmalloc_int(sz, 0, 0); +} + +static void expand(uint32_t new_size, heap_t *heap) +{ + assert(new_size > heap->end_address - heap->start_address); + + if ((new_size & 0xFFFFF000) != 0) { + new_size &= 0xFFFFF000; + new_size += 0x1000; + } + + assert(heap->start_address + new_size <= heap->max_address); + + uint32_t old_size = heap->end_address - heap->start_address; + + uint32_t i = old_size; + while (i < new_size) { + alloc_frame(get_page(heap->start_address + i, 1, kernel_directory), + (heap->supervisor) ? 1 : 0, (heap->readonly) ? 0 : 1); + i += 0x1000; + } + heap->end_address = heap->start_address + new_size; +} + +static uint32_t contract(uint32_t new_size, heap_t *heap) +{ + assert(new_size < heap->end_address - heap->start_address); + + if (new_size & 0x1000) { + new_size &= 0x1000; + new_size += 0x1000; + } + + if (new_size < HEAP_MIN_SIZE) + new_size = HEAP_MIN_SIZE; + + uint32_t old_size = heap->end_address - heap->start_address; + uint32_t i = old_size - 0x1000; + while (new_size < i) { + free_frame(get_page(heap->start_address + i, 0, kernel_directory)); + i -= 0x1000; + } + + heap->end_address = heap->start_address + new_size; + return new_size; +} + +static int32_t find_smallest_hole(uint32_t size, uint8_t page_align, heap_t *heap) +{ + uint32_t iterator = 0; + while (iterator < heap->index.size) { + header_t *header = (header_t *) lookup_ordered_array(iterator, &heap->index); + if (page_align > 0) { + uint32_t location = (uint32_t) header; + int32_t offset = 0; + if (((location + sizeof(header_t)) & 0xFFFFF000) != 0) + offset = 0x1000 - (location + sizeof(header_t)) % 0x1000; + int32_t hole_size = (int32_t) header->size - offset; + if (hole_size >= (int32_t) size) + break; + } else if (header->size >= size) + break; + iterator++; + } + if (iterator == heap->index.size) + return -1; + else + return iterator; +} + +static int8_t header_t_less_than(void *a, void *b) +{ + return (int8_t) ((((header_t *) a)->size < ((header_t *) b)->size) ? 1 : 0); +} + +heap_t *create_heap(uint32_t start, uint32_t end_addr, uint32_t max, uint8_t supervisor, uint8_t readonly) +{ + heap_t *heap = (heap_t *) kmalloc(sizeof(heap_t)); + + assert(start % 0x1000 == 0); + assert(end_addr % 0x1000 == 0); + + heap->index = place_ordered_array((void *) start, HEAP_INDEX_SIZE, &header_t_less_than); + + start += sizeof(type_t) * HEAP_INDEX_SIZE; + + if ((start & 0xFFFFF000) != 0) { + start &= 0xFFFFF000; + start += 0x1000; + } + + heap->start_address = start; + heap->end_address = end_addr; + heap->max_address = max; + heap->supervisor = supervisor; + heap->readonly = readonly; + + header_t *hole = (header_t *) start; + hole->size = end_addr - start; + hole->magic = HEAP_MAGIC; + hole->is_hole = 1; + insert_ordered_array((void *) hole, &heap->index); + + return heap; +} + +void *alloc(uint32_t size, uint8_t page_align, heap_t *heap) +{ + uint32_t new_size = size + sizeof(header_t) + sizeof(footer_t); + int32_t iterator = find_smallest_hole(new_size, page_align, heap); + + if (iterator == -1) { + uint32_t old_length = heap->end_address - heap->start_address; + uint32_t old_end_address = heap->end_address; + + expand(old_length + new_size, heap); + uint32_t new_length = heap->end_address - heap->start_address; + + iterator = 0; + uint32_t idx = (uint32_t) -1; + uint32_t value = 0x0; + while ((uint32_t) iterator < heap->index.size) { + uint32_t tmp = (uint32_t) lookup_ordered_array((uint32_t) iterator, &heap->index); + if (tmp > value) { + value = tmp; + idx = (uint32_t) iterator; + } + iterator++; + } + + if ((int) idx == -1) { + header_t *header = (header_t *) old_end_address; + header->magic = HEAP_MAGIC; + header->size = new_length - old_length; + header->is_hole = 1; + footer_t *footer = (footer_t *) (old_end_address + header->size - sizeof(footer_t)); + footer->magic = HEAP_MAGIC; + footer->header = header; + insert_ordered_array((void *) header, &heap->index); + } else { + header_t *header = lookup_ordered_array(idx, &heap->index); + header->size += new_length - old_length; + footer_t *footer = (footer_t *) ((uint32_t) header + header->size - sizeof(footer_t)); + footer->header = header; + footer->magic = HEAP_MAGIC; + } + return alloc(size, page_align, heap); + } + + header_t *orig_hole_header = (header_t *) lookup_ordered_array((uint32_t) iterator, &heap->index); + uint32_t orig_hole_pos = (uint32_t) orig_hole_header; + uint32_t orig_hole_size = orig_hole_header->size; + if (orig_hole_size - new_size < sizeof(header_t) + sizeof(footer_t)) { + size += orig_hole_size - new_size; + new_size = orig_hole_size; + } + + if (page_align && orig_hole_pos & 0xFFFFF000) { + uint32_t new_location = orig_hole_pos + 0x1000 - (orig_hole_pos & 0xFFF) - sizeof(header_t); + header_t *hole_header = (header_t *) orig_hole_pos; + hole_header->size = 0x1000 - (orig_hole_pos & 0xFFF) - sizeof(header_t); + hole_header->magic = HEAP_MAGIC; + hole_header->is_hole = 1; + footer_t *hole_footer = (footer_t *) ((uint32_t) new_location - sizeof(footer_t)); + hole_footer->magic = HEAP_MAGIC; + hole_footer->header = hole_header; + orig_hole_pos = new_location; + orig_hole_size = orig_hole_size - hole_header->size; + } else { + remove_ordered_array((uint32_t) iterator, &heap->index); + } + + header_t *block_header = (header_t *) orig_hole_pos; + block_header->magic = HEAP_MAGIC; + block_header->is_hole = 0; + block_header->size = new_size; + footer_t *block_footer = (footer_t *) (orig_hole_pos + sizeof(header_t) + size); + block_footer->magic = HEAP_MAGIC; + block_footer->header = block_header; + + if (orig_hole_size - new_size > 0) { + header_t *hole_header = (header_t *) (orig_hole_pos + sizeof(header_t) + size + sizeof(footer_t)); + hole_header->magic = HEAP_MAGIC; + hole_header->is_hole = 1; + hole_header->size = orig_hole_size - new_size; + footer_t *hole_footer = (footer_t *) ((uint32_t) hole_header + orig_hole_size - new_size - sizeof(footer_t)); + if ((uint32_t) hole_footer < heap->end_address) { + hole_footer->magic = HEAP_MAGIC; + hole_footer->header = hole_header; + } + insert_ordered_array((void *) hole_header, &heap->index); + } + + return (void *) ((uint32_t) block_header + sizeof(header_t)); +} + +void free(void *p, heap_t *heap) +{ + if (p == 0) + return; + + header_t *header = (header_t *) ((uint32_t) p - sizeof(header_t)); + footer_t *footer = (footer_t *) ((uint32_t) header + header->size - sizeof(footer_t)); + + assert(header->magic == HEAP_MAGIC); + assert(footer->magic == HEAP_MAGIC); + + header->is_hole = 1; + + char do_add = 1; + + footer_t *test_footer = (footer_t *) ((uint32_t) header - sizeof(footer_t)); + if (test_footer->magic == HEAP_MAGIC && + test_footer->header->is_hole == 1) { + uint32_t cache_size = header->size; + header = test_footer->header; + footer->header = header; + header->size += cache_size; + do_add = 0; + } + + header_t *test_header = (header_t *) ((uint32_t) footer + sizeof(footer_t)); + if (test_header->magic == HEAP_MAGIC && + test_header->is_hole) { + header->size += test_header->size; + test_footer = (footer_t *) ((uint32_t) test_header + test_header->size - sizeof(footer_t)); + footer = test_footer; + uint32_t iterator = 0; + while ((iterator < heap->index.size) && (lookup_ordered_array(iterator, &heap->index) != (void *) test_header)) + iterator++; + + assert(iterator < heap->index.size); + remove_ordered_array(iterator, &heap->index); + } + + if ((uint32_t) footer + sizeof(footer_t) == heap->end_address) { + uint32_t old_length = heap->end_address - heap->start_address; + uint32_t new_length = contract((uint32_t) header - heap->start_address, heap); + if (header->size - (old_length - new_length) > 0) { + header->size -= old_length - new_length; + footer = (footer_t *) ((uint32_t) header + header->size - sizeof(footer_t)); + footer->magic = HEAP_MAGIC; + footer->header = header; + } else { + uint32_t iterator = 0; + while ((iterator < heap->index.size) && + (lookup_ordered_array(iterator, &heap->index) != (void *) test_header)) + iterator++; + if (iterator < heap->index.size) + remove_ordered_array(iterator, &heap->index); + } + } + + if (do_add == 1) + insert_ordered_array((void *) header, &heap->index); +} \ No newline at end of file -- cgit v1.2.3 From 3fa449276364389137a7154a9971594816d86362 Mon Sep 17 00:00:00 2001 From: Marvin Borner Date: Tue, 21 Jan 2020 22:10:16 +0100 Subject: Naming scheme and page fault improvements --- src/kernel/graphics/vesa.c | 6 +++--- src/kernel/interrupts/isr.c | 8 +++++++- src/kernel/memory/kheap.c | 8 ++++---- src/kernel/memory/paging.c | 43 ++++++++++++++++++++++--------------------- src/kernel/memory/paging.h | 12 +++++------- 5 files changed, 41 insertions(+), 36 deletions(-) (limited to 'src/kernel/memory/kheap.c') diff --git a/src/kernel/graphics/vesa.c b/src/kernel/graphics/vesa.c index d941413..15d953a 100644 --- a/src/kernel/graphics/vesa.c +++ b/src/kernel/graphics/vesa.c @@ -7,7 +7,7 @@ #include #include -extern page_directory_t *kernel_directory; +extern page_directory_t *current_directory; void switch_to_vga() { @@ -184,9 +184,9 @@ void set_optimal_resolution() uint32_t fb_size = vbe_width * vbe_height * vbe_bpl; cursor_buffer = (unsigned char *) kmalloc(fb_size); for (uint32_t z = 0; z < fb_size; z += 0x1000) { - alloc_frame(get_page((uint32_t) fb + z, 1, kernel_directory), 0, 1); - alloc_frame(get_page((uint32_t) cursor_buffer + z, 1, kernel_directory), 0, 1); + paging_alloc_frame(paging_get_page((uint32_t) fb + z, 1, current_directory), 0, 1); } + serial_printf("0x%x", fb); if (vbe_height > 1440) vesa_set_font(32); else if (vbe_height > 720) vesa_set_font(24); diff --git a/src/kernel/interrupts/isr.c b/src/kernel/interrupts/isr.c index eb932b2..d89f581 100644 --- a/src/kernel/interrupts/isr.c +++ b/src/kernel/interrupts/isr.c @@ -3,6 +3,7 @@ #include #include #include +#include // Install ISRs in IDT void isrs_install() @@ -119,6 +120,11 @@ void fault_handler(struct regs *r) // halt_loop(); // Idk loop? char *message = (char *) exception_messages[r->int_no]; strcat(message, " Exception"); - panic(message); + + // Show message if there wasn't an error in video memory + if (faulting_address != (uint32_t) fb) + panic(message); + else + halt_loop(); } } \ No newline at end of file diff --git a/src/kernel/memory/kheap.c b/src/kernel/memory/kheap.c index def9ca2..40551bc 100644 --- a/src/kernel/memory/kheap.c +++ b/src/kernel/memory/kheap.c @@ -12,7 +12,7 @@ uint32_t kmalloc_int(uint32_t sz, int align, uint32_t *phys) if (kheap != 0) { void *addr = alloc(sz, (uint8_t) align, kheap); if (phys != 0) { - page_t *page = get_page((uint32_t) addr, 0, kernel_directory); + page_t *page = paging_get_page((uint32_t) addr, 0, kernel_directory); *phys = page->frame * 0x1000 + ((uint32_t) addr & 0xFFF); } return (uint32_t) addr; @@ -70,8 +70,8 @@ static void expand(uint32_t new_size, heap_t *heap) uint32_t i = old_size; while (i < new_size) { - alloc_frame(get_page(heap->start_address + i, 1, kernel_directory), - (heap->supervisor) ? 1 : 0, (heap->readonly) ? 0 : 1); + paging_alloc_frame(paging_get_page(heap->start_address + i, 1, kernel_directory), + (heap->supervisor) ? 1 : 0, (heap->readonly) ? 0 : 1); i += 0x1000; } heap->end_address = heap->start_address + new_size; @@ -92,7 +92,7 @@ static uint32_t contract(uint32_t new_size, heap_t *heap) uint32_t old_size = heap->end_address - heap->start_address; uint32_t i = old_size - 0x1000; while (new_size < i) { - free_frame(get_page(heap->start_address + i, 0, kernel_directory)); + paging_free_frame(paging_get_page(heap->start_address + i, 0, kernel_directory)); i -= 0x1000; } diff --git a/src/kernel/memory/paging.c b/src/kernel/memory/paging.c index e050861..ad19091 100644 --- a/src/kernel/memory/paging.c +++ b/src/kernel/memory/paging.c @@ -2,6 +2,7 @@ #include #include #include +#include int paging_enabled = 0; @@ -19,7 +20,7 @@ extern void copy_page_physical(); #define INDEX_FROM_BIT(a) (a/(8*4)) #define OFFSET_FROM_BIT(a) (a%(8*4)) -static void set_frame(uint32_t frame_addr) +static void paging_set_frame(uint32_t frame_addr) { uint32_t frame = frame_addr / 0x1000; uint32_t idx = INDEX_FROM_BIT(frame); @@ -27,7 +28,7 @@ static void set_frame(uint32_t frame_addr) frames[idx] |= (0x1 << off); } -static void clear_frame(uint32_t frame_addr) +static void paging_clear_frame(uint32_t frame_addr) { uint32_t frame = frame_addr / 0x1000; uint32_t idx = INDEX_FROM_BIT(frame); @@ -35,7 +36,7 @@ static void clear_frame(uint32_t frame_addr) frames[idx] &= ~(0x1 << off); } -static uint32_t first_frame() +static uint32_t paging_first_frame() { uint32_t i, j; for (i = 0; i < INDEX_FROM_BIT(nframes); i++) { @@ -51,15 +52,15 @@ static uint32_t first_frame() return 0; } -void alloc_frame(page_t *page, int is_kernel, int is_writeable) +void paging_alloc_frame(page_t *page, int is_kernel, int is_writeable) { if (page->frame != 0) { return; } else { - uint32_t idx = first_frame(); + uint32_t idx = paging_first_frame(); if (idx == (uint32_t) -1) panic("No free frames!"); - set_frame(idx * 0x1000); + paging_set_frame(idx * 0x1000); page->present = 1; page->rw = (is_writeable == 1) ? 1 : 0; page->user = (is_kernel == 1) ? 0 : 1; @@ -67,13 +68,13 @@ void alloc_frame(page_t *page, int is_kernel, int is_writeable) } } -void free_frame(page_t *page) +void paging_free_frame(page_t *page) { uint32_t frame; if (!(frame = page->frame)) { return; } else { - clear_frame(frame); + paging_clear_frame(frame); page->frame = 0x0; } } @@ -91,27 +92,27 @@ void paging_install() kernel_directory->physicalAddr = (uint32_t) kernel_directory->tablesPhysical; for (uint32_t i = KHEAP_START; i < KHEAP_START + KHEAP_INITIAL_SIZE; i += 0x1000) - get_page((uint32_t) i, 1, kernel_directory); + paging_get_page((uint32_t) i, 1, kernel_directory); int i = 0; while (i < 0x400000) { - alloc_frame(get_page((uint32_t) i, 1, kernel_directory), 0, 0); + paging_alloc_frame(paging_get_page((uint32_t) i, 1, kernel_directory), 0, 0); i += 0x1000; } for (i = KHEAP_START; i < (int) (KHEAP_START + KHEAP_INITIAL_SIZE); i += 0x1000) - alloc_frame(get_page((uint32_t) i, 1, kernel_directory), 0, 0); + paging_alloc_frame(paging_get_page((uint32_t) i, 1, kernel_directory), 0, 0); - switch_page_directory(kernel_directory); + paging_switch_directory(kernel_directory); kheap = create_heap(KHEAP_START, KHEAP_START + KHEAP_INITIAL_SIZE, 0xCFFFF000, 0, 0); - current_directory = clone_directory(kernel_directory); - switch_page_directory(current_directory); + current_directory = paging_clone_directory(kernel_directory); + paging_switch_directory(current_directory); vga_log("Installed Paging"); } -void switch_page_directory(page_directory_t *dir) +void paging_switch_directory(page_directory_t *dir) { current_directory = dir; asm volatile("mov %0, %%cr3"::"r"(dir->physicalAddr)); @@ -123,7 +124,7 @@ void switch_page_directory(page_directory_t *dir) void paging_enable() { - switch_page_directory(kernel_directory); + paging_switch_directory(kernel_directory); paging_enabled = 1; } @@ -136,7 +137,7 @@ void paging_disable() paging_enabled = 0; } -page_t *get_page(uint32_t address, int make, page_directory_t *dir) +page_t *paging_get_page(uint32_t address, int make, page_directory_t *dir) { address /= 0x1000; uint32_t table_idx = address / 1024; @@ -154,7 +155,7 @@ page_t *get_page(uint32_t address, int make, page_directory_t *dir) } } -static page_table_t *clone_table(page_table_t *src, uint32_t *physAddr) +static page_table_t *paging_clone_table(page_table_t *src, uint32_t *physAddr) { page_table_t *table = (page_table_t *) kmalloc_ap(sizeof(page_table_t), physAddr); memset(table, 0, sizeof(page_directory_t)); @@ -163,7 +164,7 @@ static page_table_t *clone_table(page_table_t *src, uint32_t *physAddr) if (!src->pages[i].frame) continue; - alloc_frame(&table->pages[i], 0, 0); + paging_alloc_frame(&table->pages[i], 0, 0); if (src->pages[i].present) table->pages[i].present = 1; if (src->pages[i].rw) table->pages[i].rw = 1; @@ -176,7 +177,7 @@ static page_table_t *clone_table(page_table_t *src, uint32_t *physAddr) return table; } -page_directory_t *clone_directory(page_directory_t *src) +page_directory_t *paging_clone_directory(page_directory_t *src) { uint32_t phys; page_directory_t *dir = (page_directory_t *) kmalloc_ap(sizeof(page_directory_t), &phys); @@ -195,7 +196,7 @@ page_directory_t *clone_directory(page_directory_t *src) dir->tablesPhysical[i] = src->tablesPhysical[i]; } else { uint32_t phys; - dir->tables[i] = clone_table(src->tables[i], &phys); + dir->tables[i] = paging_clone_table(src->tables[i], &phys); dir->tablesPhysical[i] = phys | 0x07; } } diff --git a/src/kernel/memory/paging.h b/src/kernel/memory/paging.h index 285cb6f..bb6ee4f 100644 --- a/src/kernel/memory/paging.h +++ b/src/kernel/memory/paging.h @@ -26,22 +26,20 @@ typedef struct page_directory { int paging_enabled; -void alloc_frame(page_t *page, int is_kernel, int is_writeable); +void paging_alloc_frame(page_t *page, int is_kernel, int is_writeable); -void free_frame(page_t *page); +void paging_free_frame(page_t *page); void paging_install(); -void switch_page_directory(page_directory_t *new); +void paging_switch_directory(page_directory_t *dir); void paging_enable(); void paging_disable(); -page_t *get_page(uint32_t address, int make, page_directory_t *dir); +page_t *paging_get_page(uint32_t address, int make, page_directory_t *dir); -void page_fault(struct regs *regs); - -page_directory_t *clone_directory(page_directory_t *src); +page_directory_t *paging_clone_directory(page_directory_t *src); #endif -- cgit v1.2.3