From 6a56675851c16a0cefcf5a2d10a1227c37e9d886 Mon Sep 17 00:00:00 2001 From: Alex Auvolat Date: Tue, 2 Dec 2014 20:12:42 +0100 Subject: Implement kernel memory region allocator. --- kernel/Makefile | 2 +- kernel/include/region.h | 33 ++++++ kernel/l0/kmain.c | 29 +++++ kernel/l0/paging.c | 12 +- kernel/l0/region.c | 293 ++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 367 insertions(+), 2 deletions(-) create mode 100644 kernel/include/region.h create mode 100644 kernel/l0/region.c diff --git a/kernel/Makefile b/kernel/Makefile index dec8686..58a6339 100644 --- a/kernel/Makefile +++ b/kernel/Makefile @@ -12,7 +12,7 @@ LDFLAGS = -T linker.ld -ffreestanding -O2 -nostdlib -lgcc OBJ = lib/string.o lib/printf.o \ l0/loader.o l0/kmain.o l0/dbglog.o l0/sys.o \ l0/gdt.o l0/idt.o l0/interrupt.o \ - l0/frame.o l0/paging.o + l0/frame.o l0/paging.o l0/region.o OUT = kernel.bin all: $(OUT) diff --git a/kernel/include/region.h b/kernel/include/region.h new file mode 100644 index 0000000..701e2d9 --- /dev/null +++ b/kernel/include/region.h @@ -0,0 +1,33 @@ +#pragma once + +// Kernel virtual memory region allocator + +#include +#include + +// Region types +#define REGION_T_KERNEL_BASE 0x00000001 // base kernel code & data +#define REGION_T_DESCRIPTORS 0x00000002 // contains more region descriptors +#define REGION_T_PAGEDIR 0x00000010 // used to map a page directory +#define REGION_T_PAGETABLE 0x00000020 // used to map a page table +#define REGION_T_CORE_HEAP 0x00000100 // used for the core kernel heap +#define REGION_T_PROC_HEAP 0x00000200 // used for a kernel process' heap +#define REGION_T_CACHE 0x00001000 // used for cache +#define REGION_T_HW 0x00002000 // used for hardware access + +struct region_info; +typedef void (*page_fault_handler_t)(pagedir_t *pd, struct region_info *r, size_t addr); + +typedef struct region_info { + size_t addr, size; + uint32_t type; + page_fault_handler_t pf; +} region_info_t; + +void region_allocator_init(void* kernel_data_end); + +size_t region_alloc(size_t size, uint32_t type, page_fault_handler_t pf); // returns 0 on error +region_info_t *find_region(size_t addr); +void region_free(size_t addr); + +void dbg_print_region_stats(); diff --git a/kernel/l0/kmain.c b/kernel/l0/kmain.c index f6cda4e..cd84cf7 100644 --- a/kernel/l0/kmain.c +++ b/kernel/l0/kmain.c @@ -7,6 +7,7 @@ #include #include #include +#include void breakpoint_handler(registers_t *regs) { dbg_printf("Breakpoint! (int3)\n"); @@ -43,6 +44,34 @@ void kmain(struct multiboot_info_t *mbd, int32_t mb_magic) { paging_setup(kernel_data_end); dbg_printf("Paging seems to be working!\n"); + region_allocator_init(kernel_data_end); + dbg_print_region_stats(); + + size_t p = region_alloc(0x1000, REGION_T_HW, 0); + dbg_printf("Allocated one-page region: 0x%p\n", p); + dbg_print_region_stats(); + size_t q = region_alloc(0x1000, REGION_T_HW, 0); + dbg_printf("Allocated one-page region: 0x%p\n", q); + dbg_print_region_stats(); + size_t r = region_alloc(0x2000, REGION_T_HW, 0); + dbg_printf("Allocated two-page region: 0x%p\n", r); + dbg_print_region_stats(); + size_t s = region_alloc(0x10000, REGION_T_CORE_HEAP, 0); + dbg_printf("Allocated 16-page region: 0x%p\n", s); + dbg_print_region_stats(); + region_free(p); + dbg_printf("Freed region 0x%p\n", p); + dbg_print_region_stats(); + region_free(q); + dbg_printf("Freed region 0x%p\n", q); + dbg_print_region_stats(); + region_free(r); + dbg_printf("Freed region 0x%p\n", r); + dbg_print_region_stats(); + region_free(s); + dbg_printf("Freed region 0x%p\n", s); + dbg_print_region_stats(); + // TODO: // - setup allocator for physical pages (eg: buddy allocator, see OSDev wiki) // - setup allocator for virtual memory space diff --git a/kernel/l0/paging.c b/kernel/l0/paging.c index 9e9df6b..f076aa1 100644 --- a/kernel/l0/paging.c +++ b/kernel/l0/paging.c @@ -1,5 +1,7 @@ #include #include +#include +#include typedef union page { struct { @@ -38,6 +40,14 @@ static pagedir_t kernel_pd; static pagedir_t *current_pd; +void page_fault_handler(registers_t *regs) { + size_t addr; + asm volatile("movl %%cr2, %0":"=r"(addr)); + dbg_printf("Page fault at 0x%p\n", addr); + PANIC("PAGE FAULT"); + // not handled yet +} + void paging_setup(void* kernel_data_end) { size_t n_kernel_pages = PAGE_ALIGN_UP((size_t)kernel_data_end - K_HIGHHALF_ADDR)/PAGE_SIZE; @@ -76,7 +86,7 @@ void paging_setup(void* kernel_data_end) { cr4 &= ~0x00000010; asm volatile("movl %0, %%cr4":: "r"(cr4)); - // TODO : setup page fault handler + idt_set_ex_handler(EX_PAGE_FAULT, page_fault_handler); } pagedir_t *get_current_pagedir() { diff --git a/kernel/l0/region.c b/kernel/l0/region.c new file mode 100644 index 0000000..421a018 --- /dev/null +++ b/kernel/l0/region.c @@ -0,0 +1,293 @@ +#include +#include + +typedef union region_descriptor { + struct { + union region_descriptor *next; + } unused_descriptor; + struct { + size_t addr, size; + union region_descriptor *next_by_size, *first_bigger; + union region_descriptor *next_by_addr; + } free; + struct { + region_info_t i; + union region_descriptor *next_by_addr; + } used; +} descriptor_t; + +#define N_BASE_DESCRIPTORS 12 // pre-allocate memory for 12 descriptors +static descriptor_t base_descriptors[N_BASE_DESCRIPTORS]; + +static descriptor_t *first_unused_descriptor; +static descriptor_t *first_free_region_by_addr, *first_free_region_by_size; +static descriptor_t *first_used_region; + +// ========================================================= // +// HELPER FUNCTIONS FOR THE MANIPULATION OF THE REGION LISTS // +// ========================================================= // + +static void add_unused_descriptor(descriptor_t *d) { + d->unused_descriptor.next = first_unused_descriptor; + first_unused_descriptor = d; +} + +static descriptor_t *get_unused_descriptor() { + descriptor_t *r = first_unused_descriptor; + if (r != 0) first_unused_descriptor = r->unused_descriptor.next; + return r; +} + +static void remove_free_region(descriptor_t *d) { + if (first_free_region_by_size == d) { + first_free_region_by_size = d->free.next_by_size; + } else { + for (descriptor_t *i = first_free_region_by_size; i != 0; i = i->free.next_by_size) { + if (i->free.next_by_size == d) { + i->free.next_by_size = d->free.next_by_size; + break; + } + } + } + if (first_free_region_by_addr == d) { + first_free_region_by_addr = d->free.next_by_addr; + } else { + for (descriptor_t *i = first_free_region_by_addr; i != 0; i = i->free.next_by_addr) { + if (i->free.next_by_addr == d) { + i->free.next_by_addr = d->free.next_by_addr; + break; + } + } + } +} + +static void add_free_region(descriptor_t *d) { + /*dbg_printf("Add free region 0x%p - 0x%p\n", d->free.addr, d->free.size + d->free.addr);*/ + // Find position of region in address-ordered list + // Possibly concatenate free region + descriptor_t *i = first_free_region_by_addr; + if (i == 0) { + ASSERT(first_free_region_by_size == 0); + first_free_region_by_addr = first_free_region_by_size = d; + d->free.next_by_size = d->free.first_bigger = d->free.next_by_addr = 0; + return; + } else if (d->free.addr + d->free.size == i->free.addr) { + // concatenate d . i + remove_free_region(i); + d->free.size += i->free.size; + add_unused_descriptor(i); + add_free_region(d); + return; + } else if (i->free.addr > d->free.addr) { + // insert before i + d->free.next_by_addr = i; + first_free_region_by_addr = d; + } else { + while (i != 0) { + ASSERT(d->free.addr > i->free.addr); + if (i->free.addr + i->free.size == d->free.addr) { + // concatenate i . d + remove_free_region(i); + i->free.size += d->free.size; + add_unused_descriptor(d); + add_free_region(i); + return; + } else if (i->free.next_by_addr == 0) { + i->free.next_by_addr = d; + d->free.next_by_addr = 0; + break; + } else if (d->free.addr + d->free.size == i->free.next_by_addr->free.addr) { + // concatenate d . i->next_by_addr + descriptor_t *j = i->free.next_by_addr; + remove_free_region(j); + d->free.size += j->free.size; + add_unused_descriptor(j); + add_free_region(d); + return; + } else if (i->free.next_by_addr->free.addr > d->free.addr) { + // insert between i and i->next_by_addr + d->free.next_by_addr = i->free.next_by_addr; + i->free.next_by_addr = d; + break; + } else { + // continue + i = i->free.next_by_addr; + } + } + } + // Now add it in size-ordered list + i = first_free_region_by_size; + ASSERT(i != 0); + if (d->free.size <= i->free.size) { + d->free.next_by_size = i; + d->free.first_bigger = (i->free.size > d->free.size ? i : i->free.first_bigger); + first_free_region_by_size = d; + } else { + while (i != 0) { + ASSERT(d->free.size > i->free.size); + if (i->free.next_by_size == 0) { + i->free.next_by_size = d; + if (d->free.size > i->free.size) i->free.first_bigger = d; + d->free.next_by_size = 0; + d->free.first_bigger = 0; + break; + } else if (i->free.next_by_size->free.size >= d->free.size) { + i->free.next_by_size = d; + if (d->free.size > i->free.size) i->free.first_bigger = d; + d->free.next_by_size = i->free.next_by_size; + d->free.first_bigger = + (i->free.next_by_size->free.size > d->free.size + ? i->free.next_by_size + : i->free.next_by_size->free.first_bigger); + break; + } else { + // continue + i = i->free.next_by_size; + } + } + } +} + +static descriptor_t *find_used_region(size_t addr) { + for (descriptor_t *i = first_used_region; i != 0; i = i->used.next_by_addr) { + if (addr >= i->used.i.addr && addr < i->used.i.addr + i->used.i.size) return i; + if (i->used.i.addr > addr) break; + } + return 0; +} + +static void add_used_region(descriptor_t *d) { + descriptor_t *i = first_used_region; + ASSERT(i->used.i.addr < d->used.i.addr); // first region by address is never free + + while (i != 0) { + ASSERT(i->used.i.addr < d->used.i.addr); + if (i->used.next_by_addr == 0 || i->used.next_by_addr->used.i.addr > d->used.i.addr) { + d->used.next_by_addr = i->used.next_by_addr; + i->used.next_by_addr = d; + return; + } else { + i = i->used.next_by_addr; + } + } + ASSERT(false); +} + +static void remove_used_region(descriptor_t *d) { + if (first_used_region == d) { + first_used_region = d->used.next_by_addr; + } else { + for (descriptor_t *i = first_used_region; i != 0; i = i->used.next_by_addr) { + if (i->used.i.addr > d->used.i.addr) break; + if (i->used.next_by_addr == d) { + i->used.next_by_addr = d->used.next_by_addr; + break; + } + } + } +} + +// =============== // +// THE ACTUAL CODE // +// =============== // + +void region_allocator_init(void* kernel_data_end) { + descriptor_t *u0 = &base_descriptors[0]; + u0->used.i.addr = K_HIGHHALF_ADDR; + u0->used.i.size = PAGE_ALIGN_UP(kernel_data_end) - K_HIGHHALF_ADDR; + u0->used.i.type = REGION_T_KERNEL_BASE; + u0->used.i.pf = 0; + u0->used.next_by_addr = 0; + first_used_region = u0; + + descriptor_t *f0 = &base_descriptors[1]; + f0->free.addr = PAGE_ALIGN_UP(kernel_data_end); + f0->free.size = (0xFFFFF000-f0->free.addr); // last page cannot be used... + f0->free.next_by_size = 0; + f0->free.first_bigger = 0; + first_free_region_by_size = first_free_region_by_addr = f0; + + first_unused_descriptor = 0; + for (int i = 2; i < N_BASE_DESCRIPTORS; i++) { + add_unused_descriptor(&base_descriptors[i]); + } +} + +size_t region_alloc(size_t size, uint32_t type, page_fault_handler_t pf) { + size = PAGE_ALIGN_UP(size); + + for (descriptor_t *i = first_free_region_by_size; i != 0; i = i->free.first_bigger) { + if (i->free.size >= size) { + remove_free_region(i); + if (i->free.size > size) { + descriptor_t *x = get_unused_descriptor(); + if (x == 0) { + return 0; + // TODO: allocate more descriptors + } + x->free.size = i->free.size - size; + if (size >= 0x4000) { + x->free.addr = i->free.addr + size; + } else { + x->free.addr = i->free.addr; + i->free.addr += x->free.size; + } + add_free_region(x); + } + size_t addr = i->free.addr; + i->used.i.addr = addr; + i->used.i.size = size; + i->used.i.type = type; + i->used.i.pf = pf; + add_used_region(i); + return addr; + } + } + return 0; //Not found +} + +region_info_t *find_region(size_t addr) { + descriptor_t *d = find_used_region(addr); + if (d == 0) return 0; + return &d->used.i; +} + +void region_free(size_t addr) { + descriptor_t *d = find_used_region(addr); + if (d == 0) return; + + region_info_t i = d->used.i; + + remove_used_region(d); + d->free.addr = i.addr; + d->free.size = i.size; + add_free_region(d); +} + +void dbg_print_region_stats() { + dbg_printf("/ Free kernel regions, by address:\n"); + for (descriptor_t *d = first_free_region_by_addr; d != 0; d = d->free.next_by_addr) { + dbg_printf("| 0x%p - 0x%p\n", d->free.addr, d->free.addr + d->free.size); + ASSERT(d != d->free.next_by_addr); + } + dbg_printf("- Free kernel regions, by size:\n"); + for (descriptor_t *d = first_free_region_by_size; d != 0; d = d->free.next_by_size) { + dbg_printf("| 0x%p - 0x%p\n", d->free.addr, d->free.addr + d->free.size); + ASSERT(d != d->free.next_by_size); + } + dbg_printf("- Used kernel regions:\n"); + for (descriptor_t *d = first_used_region; d != 0; d = d->used.next_by_addr) { + dbg_printf("| 0x%p - 0x%p", d->used.i.addr, d->used.i.addr + d->used.i.size); + if (d->used.i.type & REGION_T_KERNEL_BASE) dbg_printf(" Kernel code & base data"); + if (d->used.i.type & REGION_T_DESCRIPTORS) dbg_printf(" Region descriptors"); + if (d->used.i.type & REGION_T_PAGEDIR) dbg_printf(" Mapped page directory"); + if (d->used.i.type & REGION_T_PAGETABLE) dbg_printf(" Mapped page table"); + if (d->used.i.type & REGION_T_CORE_HEAP) dbg_printf(" Core heap"); + if (d->used.i.type & REGION_T_PROC_HEAP) dbg_printf(" Kernel process heap"); + if (d->used.i.type & REGION_T_CACHE) dbg_printf(" Cache"); + if (d->used.i.type & REGION_T_HW) dbg_printf(" Hardware"); + dbg_printf("\n"); + ASSERT(d != d->used.next_by_addr); + } + dbg_printf("\\\n"); +} -- cgit v1.2.3