From 76795abc2f08f180b7a895aaf26e80b971caa81c Mon Sep 17 00:00:00 2001 From: Alex Auvolat Date: Tue, 2 Dec 2014 16:43:34 +0100 Subject: Add physical page (frame) allocator. --- kernel/Makefile | 3 ++- kernel/config.h | 7 ++--- kernel/include/frame.h | 14 ++++++++++ kernel/include/sys.h | 14 ++++++++++ kernel/l0/frame.c | 73 ++++++++++++++++++++++++++++++++++++++++++++++++++ kernel/l0/kmain.c | 17 ++++++++++-- kernel/linker.ld | 2 +- 7 files changed, 123 insertions(+), 7 deletions(-) create mode 100644 kernel/include/frame.h create mode 100644 kernel/l0/frame.c diff --git a/kernel/Makefile b/kernel/Makefile index 34e6a2e..572bb3a 100644 --- a/kernel/Makefile +++ b/kernel/Makefile @@ -11,7 +11,8 @@ 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/gdt.o l0/idt.o l0/interrupt.o \ + l0/frame.o OUT = kernel.bin all: $(OUT) diff --git a/kernel/config.h b/kernel/config.h index b1a97b2..ad3dfb2 100644 --- a/kernel/config.h +++ b/kernel/config.h @@ -14,10 +14,11 @@ #endif -extern char k_highhalf_addr; // defined in linker script : 0xC0000000 -#define K_HIGHHALF_ADDR ((void*)&k_highhalf_addr) +extern char k_highhalf_addr, k_end_addr; // defined in linker script : 0xC0000000 +#define K_HIGHHALF_ADDR ((size_t)&k_highhalf_addr) +#define K_END_ADDR ((size_t)&k_end_addr) -#define OS_NAME "Macroscope" +#define OS_NAME "macrO.Scope" #define OS_VERSION "0.0.1" // Comment to disable either form of debug log output diff --git a/kernel/include/frame.h b/kernel/include/frame.h new file mode 100644 index 0000000..9ffafb3 --- /dev/null +++ b/kernel/include/frame.h @@ -0,0 +1,14 @@ +#pragma once + +#include + +// frame.h : physical memory allocator + +void frame_init_allocator(size_t total_ram, void** kernel_data_end); + +uint32_t frame_alloc(size_t n); // allocate n consecutive frames (returns 0 on failure) +void frame_free(uint32_t base, size_t n); + +void dbg_print_frame_stats(); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/include/sys.h b/kernel/include/sys.h index 2304eec..a9d2d4c 100644 --- a/kernel/include/sys.h +++ b/kernel/include/sys.h @@ -29,4 +29,18 @@ void panic_assert(const char* assertion, const char* file, int line); #define BOCHS_BREAKPOINT asm volatile("xchg %bx, %bx") + +// Utility functions for memory alignment + +#define PAGE_SIZE 0x1000 +#define PAGE_MASK 0xFFFFF000 +#define PAGE_ALIGN_DOWN(x) (((size_t)x) & PAGE_MASK) +#define PAGE_ALIGN_UP(x) ((((size_t)x)&(~PAGE_MASK)) == 0 ? ((size_t)x) : (((size_t)x) & PAGE_MASK) + PAGE_SIZE) +#define PAGE_ID(x) (((size_t)x) / PAGE_SIZE) + +#define MASK4 0xFFFFFFFC +#define ALIGN4_UP(x) ((((size_t)x)&(~MASK4)) == 0 ? ((size_t)x) : (((size_t)x) & MASK4) + 4) +#define ALIGN4_DOWN(x) (((size_t)x)&MASK4) + + /* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/l0/frame.c b/kernel/l0/frame.c new file mode 100644 index 0000000..1f16eaf --- /dev/null +++ b/kernel/l0/frame.c @@ -0,0 +1,73 @@ +#include +#include + +// TODO: buddy allocator +// this is a simple bitmap allocator + +#define INDEX_FROM_BIT(a) (a/(8*4)) +#define OFFSET_FROM_BIT(a) (a%(8*4)) + +static uint32_t *frame_bitset; +static uint32_t nframes, nused_frames; +static uint32_t begin_search_at; + +void frame_init_allocator(size_t total_ram, void** kernel_data_end) { + nframes = PAGE_ID(total_ram); + + frame_bitset = (uint32_t*)ALIGN4_UP((size_t)*kernel_data_end); + *kernel_data_end = (void*)frame_bitset + ALIGN4_UP(nframes / 8); + + for (size_t i = 0; i < ALIGN4_UP(nframes / 8)/4; i++) + frame_bitset[i] = 0; + + nused_frames = 0; + + size_t kernel_pages = PAGE_ALIGN_UP((size_t)*kernel_data_end - K_HIGHHALF_ADDR)/PAGE_SIZE; + for (size_t i = 0; i < kernel_pages; i++) { + size_t idx = INDEX_FROM_BIT(i); + size_t ofs = OFFSET_FROM_BIT(i); + frame_bitset[idx] |= (0x1 << ofs); + nused_frames++; + } + begin_search_at = INDEX_FROM_BIT(kernel_pages); +} + +uint32_t frame_alloc(size_t n) { + if (n > 32) return 0; + + for (uint32_t i = begin_search_at; i < INDEX_FROM_BIT(nframes); i++) { + if (frame_bitset[i] == 0xFFFFFFFF) { + if (i == begin_search_at) begin_search_at++; + continue; + } + + for (uint32_t j = 0; j < 32 - n + 1; j++) { + uint32_t to_test = (0xFFFFFFFF >> (32 - n)) << j; + if (!(frame_bitset[i]&to_test)) { + frame_bitset[i] |= to_test; + nused_frames += n; + return i * 32 + j; + } + } + } + return 0; +} + +void frame_free(uint32_t base, size_t n) { + for (size_t x = 0; x < n; x++) { + uint32_t idx = INDEX_FROM_BIT(base + n); + uint32_t ofs = OFFSET_FROM_BIT(base + n); + if (frame_bitset[idx] & (0x1 << ofs)) { + frame_bitset[idx] &= ~(0x1 << ofs); + nused_frames--; + } + } + if (INDEX_FROM_BIT(base) < begin_search_at) + begin_search_at = INDEX_FROM_BIT(base); +} + +void dbg_print_frame_stats() { + dbg_printf("Used frames: %d/%d\n", nused_frames, nframes); +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/l0/kmain.c b/kernel/l0/kmain.c index 7665cb0..b4e2ef1 100644 --- a/kernel/l0/kmain.c +++ b/kernel/l0/kmain.c @@ -5,6 +5,7 @@ #include #include +#include void breakpoint_handler(registers_t *regs) { dbg_printf("Breakpoint! (int3)\n"); @@ -23,13 +24,25 @@ void kmain(struct multiboot_info_t *mbd, int32_t mb_magic) { idt_init(); dbg_printf("IDT set up.\n"); idt_set_ex_handler(EX_BREAKPOINT, breakpoint_handler); - - asm volatile("int $0x3"); + asm volatile("int $0x3"); // test breakpoint size_t total_ram = ((mbd->mem_upper + mbd->mem_lower) * 1024); dbg_printf("Total ram: %d Kb\n", total_ram / 1024); // paging_init(totalRam); + // used for allocation of data structures before malloc is set up + // a pointer to this pointer is passed to the functions that might have + // to allocate memory ; they just increment it of the allocated quantity + void* kernel_data_end = (void*)K_END_ADDR; + frame_init_allocator(total_ram, &kernel_data_end); + dbg_printf("kernel_data_end: 0x%p\n", kernel_data_end); + dbg_print_frame_stats(); + + // TODO: + // - setup allocator for physical pages (eg: buddy allocator, see OSDev wiki) + // - setup allocator for virtual memory space + // - setup paging + PANIC("Reached kmain end! Falling off the edge."); } diff --git a/kernel/linker.ld b/kernel/linker.ld index 8ea7854..c92155c 100644 --- a/kernel/linker.ld +++ b/kernel/linker.ld @@ -36,7 +36,7 @@ SECTIONS{ ebss = .; } - end = .; _end = .; __end = .; + k_end_addr = .; } /* vim: set ts=4 sw=4 tw=0 noet :*/ -- cgit v1.2.3