From f2c51bc81d2aa618b29ddbeaae5ac1c5308821f0 Mon Sep 17 00:00:00 2001 From: Alex Auvolat Date: Mon, 9 Feb 2015 17:39:41 +0100 Subject: Reorganize all. --- .gitignore | 4 + .vimrc | 14 ++ kernel/Makefile | 38 ---- kernel/config.h | 27 --- kernel/include/buffer.h | 40 ---- kernel/include/dbglog.h | 9 - kernel/include/frame.h | 14 -- kernel/include/gdt.h | 17 -- kernel/include/hashtbl.h | 34 ---- kernel/include/idt.h | 79 -------- kernel/include/kmalloc.h | 14 -- kernel/include/multiboot.h | 63 ------- kernel/include/mutex.h | 21 --- kernel/include/paging.h | 31 --- kernel/include/printf.h | 10 - kernel/include/region.h | 38 ---- kernel/include/slab_alloc.h | 44 ----- kernel/include/string.h | 17 -- kernel/include/sys.h | 57 ------ kernel/include/thread.h | 46 ----- kernel/l0/context_switch.s | 58 ------ kernel/l0/dbglog.c | 159 ---------------- kernel/l0/frame.c | 85 --------- kernel/l0/gdt.c | 90 --------- kernel/l0/idt.c | 253 ------------------------- kernel/l0/interrupt.s | 126 ------------- kernel/l0/kmain.c | 214 --------------------- kernel/l0/kmalloc.c | 52 ----- kernel/l0/loader.s | 86 --------- kernel/l0/paging.c | 298 ----------------------------- kernel/l0/region.c | 397 --------------------------------------- kernel/l0/sys.c | 25 --- kernel/l0/thread.c | 208 -------------------- kernel/lib/buffer.c | 167 ---------------- kernel/lib/hashtbl.c | 166 ---------------- kernel/lib/mutex.c | 27 --- kernel/lib/printf.c | 120 ------------ kernel/lib/slab_alloc.c | 283 ---------------------------- kernel/lib/string.c | 90 --------- kernel/lib_tests/Makefile | 2 - kernel/lib_tests/slab_test.c | 44 ----- kernel/linker.ld | 43 ----- make_cdrom.sh | 2 +- run_bochs_debug.sh | 3 +- run_qemu.sh | 5 +- run_qemu_debug.sh | 7 +- src/common/Makefile | 11 ++ src/common/README | 18 ++ src/common/buffer.c | 167 ++++++++++++++++ src/common/common.lib | Bin 0 -> 41450 bytes src/common/hashtbl.c | 166 ++++++++++++++++ src/common/include/buffer.h | 41 ++++ src/common/include/debug.h | 14 ++ src/common/include/hashtbl.h | 34 ++++ src/common/include/malloc.h | 11 ++ src/common/include/mutex.h | 21 +++ src/common/include/printf.h | 10 + src/common/include/slab_alloc.h | 45 +++++ src/common/include/string.h | 17 ++ src/common/mutex.c | 27 +++ src/common/printf.c | 120 ++++++++++++ src/common/slab_alloc.c | 283 ++++++++++++++++++++++++++++ src/common/string.c | 90 +++++++++ src/kernel/Makefile | 14 ++ src/kernel/config.h | 27 +++ src/kernel/core/context_switch.s | 58 ++++++ src/kernel/core/dbglog.c | 159 ++++++++++++++++ src/kernel/core/frame.c | 85 +++++++++ src/kernel/core/gdt.c | 90 +++++++++ src/kernel/core/idt.c | 253 +++++++++++++++++++++++++ src/kernel/core/interrupt.s | 126 +++++++++++++ src/kernel/core/kmain.c | 215 +++++++++++++++++++++ src/kernel/core/kmalloc.c | 52 +++++ src/kernel/core/loader.s | 86 +++++++++ src/kernel/core/paging.c | 298 +++++++++++++++++++++++++++++ src/kernel/core/region.c | 397 +++++++++++++++++++++++++++++++++++++++ src/kernel/core/sys.c | 25 +++ src/kernel/core/thread.c | 208 ++++++++++++++++++++ src/kernel/include/config.h | 1 + src/kernel/include/dbglog.h | 8 + src/kernel/include/frame.h | 14 ++ src/kernel/include/gdt.h | 17 ++ src/kernel/include/idt.h | 79 ++++++++ src/kernel/include/kmalloc.h | 11 ++ src/kernel/include/multiboot.h | 63 +++++++ src/kernel/include/paging.h | 31 +++ src/kernel/include/process.h | 43 +++++ src/kernel/include/region.h | 38 ++++ src/kernel/include/sys.h | 53 ++++++ src/kernel/include/thread.h | 46 +++++ src/kernel/linker.ld | 43 +++++ src/kernel/user/process.c | 30 +++ src/rules.make | 34 ++++ src/tests/Makefile | 2 + src/tests/slab_test.c | 44 +++++ 95 files changed, 3753 insertions(+), 3599 deletions(-) create mode 100644 .vimrc delete mode 100644 kernel/Makefile delete mode 100644 kernel/config.h delete mode 100644 kernel/include/buffer.h delete mode 100644 kernel/include/dbglog.h delete mode 100644 kernel/include/frame.h delete mode 100644 kernel/include/gdt.h delete mode 100644 kernel/include/hashtbl.h delete mode 100644 kernel/include/idt.h delete mode 100644 kernel/include/kmalloc.h delete mode 100644 kernel/include/multiboot.h delete mode 100644 kernel/include/mutex.h delete mode 100644 kernel/include/paging.h delete mode 100644 kernel/include/printf.h delete mode 100644 kernel/include/region.h delete mode 100644 kernel/include/slab_alloc.h delete mode 100644 kernel/include/string.h delete mode 100644 kernel/include/sys.h delete mode 100644 kernel/include/thread.h delete mode 100644 kernel/l0/context_switch.s delete mode 100644 kernel/l0/dbglog.c delete mode 100644 kernel/l0/frame.c delete mode 100644 kernel/l0/gdt.c delete mode 100644 kernel/l0/idt.c delete mode 100644 kernel/l0/interrupt.s delete mode 100644 kernel/l0/kmain.c delete mode 100644 kernel/l0/kmalloc.c delete mode 100644 kernel/l0/loader.s delete mode 100644 kernel/l0/paging.c delete mode 100644 kernel/l0/region.c delete mode 100644 kernel/l0/sys.c delete mode 100644 kernel/l0/thread.c delete mode 100644 kernel/lib/buffer.c delete mode 100644 kernel/lib/hashtbl.c delete mode 100644 kernel/lib/mutex.c delete mode 100644 kernel/lib/printf.c delete mode 100644 kernel/lib/slab_alloc.c delete mode 100644 kernel/lib/string.c delete mode 100644 kernel/lib_tests/Makefile delete mode 100644 kernel/lib_tests/slab_test.c delete mode 100644 kernel/linker.ld create mode 100644 src/common/Makefile create mode 100644 src/common/README create mode 100644 src/common/buffer.c create mode 100644 src/common/common.lib create mode 100644 src/common/hashtbl.c create mode 100644 src/common/include/buffer.h create mode 100644 src/common/include/debug.h create mode 100644 src/common/include/hashtbl.h create mode 100644 src/common/include/malloc.h create mode 100644 src/common/include/mutex.h create mode 100644 src/common/include/printf.h create mode 100644 src/common/include/slab_alloc.h create mode 100644 src/common/include/string.h create mode 100644 src/common/mutex.c create mode 100644 src/common/printf.c create mode 100644 src/common/slab_alloc.c create mode 100644 src/common/string.c create mode 100644 src/kernel/Makefile create mode 100644 src/kernel/config.h create mode 100644 src/kernel/core/context_switch.s create mode 100644 src/kernel/core/dbglog.c create mode 100644 src/kernel/core/frame.c create mode 100644 src/kernel/core/gdt.c create mode 100644 src/kernel/core/idt.c create mode 100644 src/kernel/core/interrupt.s create mode 100644 src/kernel/core/kmain.c create mode 100644 src/kernel/core/kmalloc.c create mode 100644 src/kernel/core/loader.s create mode 100644 src/kernel/core/paging.c create mode 100644 src/kernel/core/region.c create mode 100644 src/kernel/core/sys.c create mode 100644 src/kernel/core/thread.c create mode 120000 src/kernel/include/config.h create mode 100644 src/kernel/include/dbglog.h create mode 100644 src/kernel/include/frame.h create mode 100644 src/kernel/include/gdt.h create mode 100644 src/kernel/include/idt.h create mode 100644 src/kernel/include/kmalloc.h create mode 100644 src/kernel/include/multiboot.h create mode 100644 src/kernel/include/paging.h create mode 100644 src/kernel/include/process.h create mode 100644 src/kernel/include/region.h create mode 100644 src/kernel/include/sys.h create mode 100644 src/kernel/include/thread.h create mode 100644 src/kernel/linker.ld create mode 100644 src/kernel/user/process.c create mode 100644 src/rules.make create mode 100644 src/tests/Makefile create mode 100644 src/tests/slab_test.c diff --git a/.gitignore b/.gitignore index 084889f..4fcbaae 100644 --- a/.gitignore +++ b/.gitignore @@ -1,8 +1,11 @@ *~ *.swp +tags + *.o *.bin +*.lib *.map *.iso @@ -18,3 +21,4 @@ doc/html # bochs debugger bx_enh_dbg.ini + diff --git a/.vimrc b/.vimrc new file mode 100644 index 0000000..06a0ef4 --- /dev/null +++ b/.vimrc @@ -0,0 +1,14 @@ +autocmd VimEnter * NERDTree +autocmd VimEnter * wincmd p + +map :!ctags -R --sort=yes --c-kinds=+pl --fields=+iaS --extra=+q kernel + + +let g:syntastic_always_populate_loc_list = 1 +let g:syntastic_auto_loc_list = 1 +let g:syntastic_check_on_open = 1 +let g:syntastic_check_on_wq = 0 + +let g:syntastic_c_gcc_exec = 'i586-elf-gcc' +let g:syntastic_c_include_dirs = [ 'src/kernel/include', 'src/kernel', 'src/common/include' ] +let g:syntastic_c_compiler_options = '-ffreestanding -Wall -Wextra -std=gnu99 -Wno-unused-parameter' diff --git a/kernel/Makefile b/kernel/Makefile deleted file mode 100644 index 1764764..0000000 --- a/kernel/Makefile +++ /dev/null @@ -1,38 +0,0 @@ - -AS = nasm -ASFLAGS = -felf -g - -CC = i586-elf-gcc -CFLAGS = -ffreestanding -O2 -std=gnu99 -Wall -Wextra -I . -I ./include -g -Wno-unused-parameter -# CXX = i586-elf-g++ -# CXFLAGS = -ffreestanding -O3 -Wall -Wextra -I . -I ./include -fno-exceptions -fno-rtti -LD = i586-elf-gcc -LDFLAGS = -T linker.ld -ffreestanding -O2 -nostdlib -lgcc -Xlinker -Map=kernel.map - -OBJ = lib/string.o lib/printf.o lib/slab_alloc.o lib/mutex.o \ - lib/hashtbl.o lib/buffer.o\ - l0/loader.o l0/kmain.o l0/dbglog.o l0/sys.o \ - l0/gdt.o l0/idt.o l0/interrupt.o l0/context_switch.o l0/thread.o \ - l0/frame.o l0/paging.o l0/region.o l0/kmalloc.o -OUT = kernel.bin - -all: $(OUT) - -$(OUT): $(OBJ) - $(LD) $(LDFLAGS) -o $@ $^ - -%.o: %.s - $(AS) $(ASFLAGS) -o $@ $< - -%.o: %.c - $(CC) -c $< -o $@ $(CFLAGS) - -# %.o: %.cpp -# $(CXX) -c $< -o $@ $(CXFLAGS) - -clean: - rm */*.o || true -mrproper: clean - rm $(OUT) || true - -rebuild: mrproper all diff --git a/kernel/config.h b/kernel/config.h deleted file mode 100644 index a0e59d3..0000000 --- a/kernel/config.h +++ /dev/null @@ -1,27 +0,0 @@ -#if !defined(__cplusplus) -#include -#endif - -#include -#include - -#if defined(__linux__) -#error "This kernel needs to be compiled with a cross-compiler." -#endif - -#if !defined(__i386__) -#error "This kernel needs to be compiled with a ix86-elf compiler" -#endif - -#define IN_KERNEL - -#define K_HIGHHALF_ADDR ((size_t)0xC0000000) - -#define OS_NAME "macrO.Scope" -#define OS_VERSION "0.0.1" - -// Comment to disable either form of debug log output -#define DBGLOG_TO_SERIAL -#define DBGLOG_TO_SCREEN - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/include/buffer.h b/kernel/include/buffer.h deleted file mode 100644 index c47e2b4..0000000 --- a/kernel/include/buffer.h +++ /dev/null @@ -1,40 +0,0 @@ -#pragma once - -#include -#include - -// The buffer_t type is a simple reference-counted buffer type -// enabling the creation, sharing, slicing and concatenation of buffers -// without having to copy everything each time - -// Buffers are always allocated on the core kernel heap (kmalloc/kfree) - -// Once a buffer is allocated, its contents is immutable - -// Encoding and decoding functions for buffer contents are provided in -// a separate file (encode.h) - -struct buffer; -typedef struct buffer buffer_t; - -void buffer_ref(buffer_t*); // increase reference counter -void buffer_unref(buffer_t*); // decrease reference counter - -size_t buffer_len(buffer_t* buf); -size_t read_buffer(buffer_t* buf, char* to, size_t begin, size_t n); // returns num of bytes read - -buffer_t* buffer_from_bytes(const char* data, size_t n); // bytes are COPIED -buffer_t* buffer_from_bytes_nocopy(const char* data, size_t n, bool own_bytes); // bytes are NOT COPIED - -// these functions GIVE the buffer in order to create the new buffer, ie they do not increase RC -// the buffer is NOT GIVED if the new buffer could not be created (ie retval == 0) -buffer_t* buffer_slice(buffer_t* b, size_t begin, size_t n); -buffer_t* buffer_concat(buffer_t* a, buffer_t* b); - -// these functions KEEP a reference on the buffer (ie RC is incremented) -// the RC is NOT INCREMENTED if the new buffer cannot be created -buffer_t* buffer_slice_k(buffer_t* b, size_t begin, size_t n); -buffer_t* buffer_concat_k(buffer_t* a, buffer_t* b); - - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/include/dbglog.h b/kernel/include/dbglog.h deleted file mode 100644 index 2f670e8..0000000 --- a/kernel/include/dbglog.h +++ /dev/null @@ -1,9 +0,0 @@ -#pragma once - -#include - -void dbglog_setup(); -void dbg_print(const char* str); -void dbg_printf(const char* format, ...); - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/include/frame.h b/kernel/include/frame.h deleted file mode 100644 index 9ffafb3..0000000 --- a/kernel/include/frame.h +++ /dev/null @@ -1,14 +0,0 @@ -#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/gdt.h b/kernel/include/gdt.h deleted file mode 100644 index a62d0db..0000000 --- a/kernel/include/gdt.h +++ /dev/null @@ -1,17 +0,0 @@ -#pragma once - -#include -#include - -/* The GDT is one of the x86's descriptor tables. It is used for memory segmentation. - Here, we don't use segmentation to separate processes from one another (this is done with paging). - We only use segmentation to make the difference between kernel mode (ring 3) and user mode (ring 0) */ - -void gdt_init(); - -#define K_CODE_SEGMENT 0x08 -#define K_DATA_SEGMENT 0x10 -#define U_CODE_SEGMENT 0x18 -#define U_DATA_SEGMENT 0x20 - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/include/hashtbl.h b/kernel/include/hashtbl.h deleted file mode 100644 index 16dfefb..0000000 --- a/kernel/include/hashtbl.h +++ /dev/null @@ -1,34 +0,0 @@ -#pragma once - -#include -#include -#include - -// Simple hashtable structure (key -> void*) -// Supports adding, seeking, removing -// When adding a binding to the table, the previous binding for same key (if exists) is removed - -// TODO : possibility to allocate the hashtbl structure on any heap -// (currently uses kmalloc/kfree) - -struct hashtbl; -typedef struct hashtbl hashtbl_t; - -typedef size_t hash_t; -typedef hash_t (*hash_fun_t)(const void*); -typedef bool (*key_eq_fun_t)(const void*, const void*); - -hashtbl_t* create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, size_t initial_size); // 0 -> default size -void delete_hashtbl(hashtbl_t* ht); - -int hashtbl_add(hashtbl_t* ht, void* key, void* v); // non-null on error (OOM for instance) -void* hashtbl_find(hashtbl_t* ht, void* key); // null when not found -void hashtbl_remove(hashtbl_t* ht, void* key); -size_t hashtbl_count(hashtbl_t* ht); - -hash_t id_hash_fun(const void* v); -hash_t str_hash_fun(const void* v); -bool id_key_eq_fun(const void* a, const void* b); -bool str_key_eq_fun(const void* a, const void* b); - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/include/idt.h b/kernel/include/idt.h deleted file mode 100644 index 8e84cea..0000000 --- a/kernel/include/idt.h +++ /dev/null @@ -1,79 +0,0 @@ -#pragma once - -/* The IDT is the system descriptor table that tells the CPU what to do when an interrupt fires. - There are three categories of interrupts : - - Exceptions ; eg page fault, divide by 0 - - IRQ : interrupts caused by hardware - - System calls : when an applications asks the system to do something */ - -#include - -#define IRQ0 0 -#define IRQ1 1 -#define IRQ2 2 -#define IRQ3 3 -#define IRQ4 4 -#define IRQ5 5 -#define IRQ6 6 -#define IRQ7 7 -#define IRQ8 8 -#define IRQ9 9 -#define IRQ10 10 -#define IRQ11 11 -#define IRQ12 12 -#define IRQ13 13 -#define IRQ14 14 -#define IRQ15 15 - -#define EX_DIVIDE_ERROR 0 // No error code -#define EX_DEBUG 1 // No error code -#define EX_NMI_INTERRUPT 2 // No error code -#define EX_BREAKPOINT 3 // No error code -#define EX_OVERFLOW 4 // No error code -#define EX_BOUND_RANGE_EXCEDEED 5 // No error code -#define EX_INVALID_OPCODE 6 // No error code -#define EX_DEVICE_NOT_AVAILABLE 7 // No error code -#define EX_DOUBLE_FAULT 8 // Yes (Zero) -#define EX_COPROCESSOR_SEGMENT_OVERRUN 9 // No error code -#define EX_INVALID_TSS 10 // Yes -#define EX_SEGMENT_NOT_PRESENT 11 // Yes -#define EX_STACK_SEGMENT_FAULT 12 // Yes -#define EX_GENERAL_PROTECTION 13 // Yes -#define EX_PAGE_FAULT 14 // Yes -#define EX_INTEL_RESERVED_1 15 // No -#define EX_FLOATING_POINT_ERROR 16 // No -#define EX_ALIGNEMENT_CHECK 17 // Yes (Zero) -#define EX_MACHINE_CHECK 18 // No -#define EX_INTEL_RESERVED_2 19 // No -#define EX_INTEL_RESERVED_3 20 // No -#define EX_INTEL_RESERVED_4 21 // No -#define EX_INTEL_RESERVED_5 22 // No -#define EX_INTEL_RESERVED_6 23 // No -#define EX_INTEL_RESERVED_7 24 // No -#define EX_INTEL_RESERVED_8 25 // No -#define EX_INTEL_RESERVED_9 26 // No -#define EX_INTEL_RESERVED_10 27 // No -#define EX_INTEL_RESERVED_11 28 // No -#define EX_INTEL_RESERVED_12 29 // No -#define EX_INTEL_RESERVED_13 30 // No -#define EX_INTEL_RESERVED_14 31 // No - -#define EFLAGS_IF (0x1 << 9) - -typedef struct registers { - uint32_t ds; // Data segment selector - uint32_t edi, esi, ebp, useless_esp, ebx, edx, ecx, eax; // Pushed by pusha. - uint32_t int_no, err_code; // Interrupt number and error code (if applicable) - uint32_t eip, cs, eflags, esp, ss; // Pushed by the processor automatically. -} registers_t; - -typedef void (*isr_handler_t)(registers_t*); - -void idt_init(); - -void idt_set_ex_handler(int number, isr_handler_t func); //Set exception handler -void idt_set_irq_handler(int number, isr_handler_t func); //Set IRQ handler - -void dbg_dump_registers(registers_t*); - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/include/kmalloc.h b/kernel/include/kmalloc.h deleted file mode 100644 index a409865..0000000 --- a/kernel/include/kmalloc.h +++ /dev/null @@ -1,14 +0,0 @@ -#pragma once - -#include -#include - -// Kernel memory allocator : one slab allocator for shared memory -// Thread-safe. - -void kmalloc_setup(); - -void* kmalloc(size_t sz); -void kfree(void* ptr); - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/include/multiboot.h b/kernel/include/multiboot.h deleted file mode 100644 index 581337a..0000000 --- a/kernel/include/multiboot.h +++ /dev/null @@ -1,63 +0,0 @@ -#pragma once - -#define MULTIBOOT_HEADER_MAGIC 0x1BADB002 -#define MULTIBOOT_BOOTLOADER_MAGIC 0x2BADB002 - -struct multiboot_header_t{ - unsigned long magic; - unsigned long flags; - unsigned long checksum; - unsigned long header_addr; - unsigned long load_addr; - unsigned long load_end_addr; - unsigned long bss_end_addr; - unsigned long entry_addr; -}; - -struct aout_symbol_table_t { - unsigned long tabsize; - unsigned long strsize; - unsigned long addr; - unsigned long reserved; -}; - -struct elf_section_header_table_t { - unsigned long num; - unsigned long size; - unsigned long addr; - unsigned long shndx; -}; - -struct multiboot_info_t { - unsigned long flags; - unsigned long mem_lower; - unsigned long mem_upper; - unsigned long boot_device; - unsigned long cmdline; - unsigned long mods_count; - unsigned long mods_addr; - union { - struct aout_symbol_table_t aout_sym; - struct elf_section_header_table_t elf_sec; - } u; - unsigned long mmap_length; - unsigned long mmap_addr; -}; - -struct module_t { - unsigned long mod_start; - unsigned long mod_end; - unsigned long string; - unsigned long reserved; -}; - -struct memory_map_t { - unsigned long size; - unsigned long base_addr_low; - unsigned long base_addr_high; - unsigned long length_low; - unsigned long length_high; - unsigned long type; -}; - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/include/mutex.h b/kernel/include/mutex.h deleted file mode 100644 index 6814adf..0000000 --- a/kernel/include/mutex.h +++ /dev/null @@ -1,21 +0,0 @@ -#pragma once - -#include - -#define MUTEX_LOCKED 1 -#define MUTEX_UNLOCKED 0 - - -typedef uint32_t mutex_t; - -void mutex_lock(mutex_t* mutex); //wait for mutex to be free -int mutex_try_lock(mutex_t* mutex); //lock mutex only if free, returns !0 if locked, 0 if was busy -void mutex_unlock(mutex_t* mutex); - -// the mutex code assumes a yield() function is defined somewhere -void yield(); - -#define STATIC_MUTEX(name) static mutex_t name __attribute__((section("locks"))) = MUTEX_UNLOCKED; - - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/include/paging.h b/kernel/include/paging.h deleted file mode 100644 index 44014a2..0000000 --- a/kernel/include/paging.h +++ /dev/null @@ -1,31 +0,0 @@ -#pragma once - -#include -#include - -struct page_directory; -typedef struct page_directory pagedir_t; - - -void paging_setup(void* kernel_data_end); - -pagedir_t *get_current_pagedir(); -pagedir_t *get_kernel_pagedir(); - -void switch_pagedir(pagedir_t *pd); - -// these functions are always relative to the currently mapped page directory -uint32_t pd_get_frame(void* vaddr); // get physical frame for virtual address -int pd_map_page(void* vaddr, uint32_t frame_id, bool rw); // returns nonzero on error -void pd_unmap_page(void* vaddr); // does nothing if page not mapped - -// Note on concurrency : we expect that multiple threads will not try to map/unmap -// pages in the same region at the same time. It can nevertheless happen that -// several threads try to map pages that belong to the same 4M-section, and in that -// case both might require the allocation of a new PT at the same location. These -// cases are well-handled (the pagedir_t type contains a mutex used for this) - -pagedir_t *create_pagedir(); // returns zero on error -void delete_pagedir(pagedir_t *pd); - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/include/printf.h b/kernel/include/printf.h deleted file mode 100644 index b4e1c1b..0000000 --- a/kernel/include/printf.h +++ /dev/null @@ -1,10 +0,0 @@ -#pragma once - -#include -#include -#include - -int snprintf(char* s, size_t n, const char* format, ...); -int vsnprintf(char* s, size_t n, const char* format, va_list arg); - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/include/region.h b/kernel/include/region.h deleted file mode 100644 index 1fef582..0000000 --- a/kernel/include/region.h +++ /dev/null @@ -1,38 +0,0 @@ -#pragma once - -// Kernel virtual memory region allocator - -// This is entirely thread-safe - -#include -#include - -struct region_info; -typedef void (*page_fault_handler_t)(pagedir_t *pd, struct region_info *r, void* addr); - -typedef struct region_info { - void* addr; - size_t size; - char* type; - page_fault_handler_t pf; -} region_info_t; - -void region_allocator_init(void* kernel_data_end); - -void* region_alloc(size_t size, char* type, page_fault_handler_t pf); // returns 0 on error -region_info_t *find_region(void* addr); -void region_free(void* addr); - -// some usefull PF handlers -// default_allocator_pf_handler : just allocates new frames on page faults -void default_allocator_pf_handler(pagedir_t *pd, struct region_info *r, void* addr); - -// some functions for freeing regions and frames -// region_free_unmap_free : deletes a region and frees all frames that were mapped in it -void region_free_unmap_free(void* addr); -// region_free_unmap : deletes a region and unmaps all frames that were mapped in it, without freeing them -void region_free_unmap(void* addr); - -void dbg_print_region_info(); - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/include/slab_alloc.h b/kernel/include/slab_alloc.h deleted file mode 100644 index eb9588d..0000000 --- a/kernel/include/slab_alloc.h +++ /dev/null @@ -1,44 +0,0 @@ -#pragma once - -// Self-contained piece of library : a slab allocator... -// Depends on page_alloc_fun_t and page_free_fun_t : a couple of functions -// that can allocate/free multiples of one page at a time - -#include -#include -#include - -#if defined(__linux__) -//redefine necessary stuff -#include -#define ASSERT assert -#define PAGE_SIZE 0x1000 -#include -#define dbg_printf printf -#else -#include // this is macroscope -#include -#endif - -// expected format for the array of slab_type_t given to slab_create : -// an array of slab_type descriptors, with last descriptor full of zeroes -// and with obj_size increasing (strictly) in the array -typedef struct slab_type { - const char *descr; - size_t obj_size; - size_t pages_per_cache; -} slab_type_t; - -struct mem_allocator; -typedef struct mem_allocator mem_allocator_t; - -typedef void* (*page_alloc_fun_t)(size_t bytes); -typedef void (*page_free_fun_t)(void* ptr); - -mem_allocator_t* create_slab_allocator(const slab_type_t *types, page_alloc_fun_t af, page_free_fun_t ff); -void destroy_slab_allocator(mem_allocator_t*); - -void* slab_alloc(mem_allocator_t* a, size_t sz); -void slab_free(mem_allocator_t* a, void* ptr); - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/include/string.h b/kernel/include/string.h deleted file mode 100644 index 682b25a..0000000 --- a/kernel/include/string.h +++ /dev/null @@ -1,17 +0,0 @@ -#pragma once - -#include -#include - -void *memcpy(void *dest, const void *src, size_t count); -void *memset(void *dest, int val, size_t count); -int memcmp(const void *s1, const void *s2, size_t n); -void *memmove(void *dest, const void *src, size_t count); - -size_t strlen(const char *str); -char *strchr(const char *str, char c); -char *strcpy(char *dest, const char *src); -char *strcat(char *dest, const char *src); -int strcmp(const char *s1, const char *s2); - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/include/sys.h b/kernel/include/sys.h deleted file mode 100644 index c8721ec..0000000 --- a/kernel/include/sys.h +++ /dev/null @@ -1,57 +0,0 @@ -#pragma once - -#include - -static inline void outb(uint16_t port, uint8_t value) { - asm volatile("outb %1, %0" : : "dN"(port), "a"(value)); -} - -static inline void outw(uint16_t port, uint16_t value) { - asm volatile("outw %1, %0" : : "dN"(port), "a"(value)); -} - -static inline uint8_t inb(uint16_t port) { - uint8_t ret; - asm volatile("inb %1, %0" : "=a"(ret) : "dN"(port)); - return ret; -} - -static inline uint16_t inw(uint16_t port) { - uint16_t ret; - asm volatile("inw %1, %0" : "=a"(ret) : "dN"(port)); - return ret; -} - -static inline void invlpg(void* addr) { - asm volatile("invlpg (%0)" : : "r"(addr) : "memory"); -} - -void panic(const char* message, const char* file, int line); -void panic_assert(const char* assertion, const char* file, int line); -#define PANIC(s) panic(s, __FILE__, __LINE__); -#define ASSERT(s) { if (!(s)) panic_assert(#s, __FILE__, __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 PAGE_SHIFT 12 -#define PT_SHIFT 10 -// PAGE_SHIFT + PT_SHIFT + PT_SHIFT = 32 -#define N_PAGES_IN_PT 1024 -#define PD_MIRROR_ADDR 0xFFC00000 // last 4MB used for PD mirroring -#define LAST_KERNEL_ADDR PD_MIRROR_ADDR -#define FIRST_KERNEL_PT (K_HIGHHALF_ADDR >> (PAGE_SHIFT+PT_SHIFT)) // must be 768 - -#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/include/thread.h b/kernel/include/thread.h deleted file mode 100644 index 757ba00..0000000 --- a/kernel/include/thread.h +++ /dev/null @@ -1,46 +0,0 @@ -#pragma once - -#include -#include -#include - -#define T_STATE_RUNNING 1 -#define T_STATE_PAUSED 2 -#define T_STATE_FINISHED 3 - -#define KPROC_STACK_SIZE 0x8000 // 8Kb - -#define TASK_SWITCH_FREQUENCY 100 // in herz - -typedef struct saved_context { - uint32_t *esp; - void (*eip)(); -} saved_context_t; - -struct process; -typedef struct thread { - saved_context_t ctx; - pagedir_t *current_pd_d; - - uint32_t state; - - region_info_t *stack_region; - - struct process *proc; // process : L1 data structure - - struct thread *next_in_queue; -} thread_t; - -typedef void (*entry_t)(void*); - -void threading_setup(entry_t cont, void* data); // never returns -thread_t *new_thread(entry_t entry, void* data); // thread is PAUSED, and must be resume_thread'ed - -extern thread_t *current_thread; - -void yield(); -void pause(); - -void resume_thread(thread_t *thread, bool run_at_once); - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/l0/context_switch.s b/kernel/l0/context_switch.s deleted file mode 100644 index 6738a03..0000000 --- a/kernel/l0/context_switch.s +++ /dev/null @@ -1,58 +0,0 @@ -[EXTERN kernel_stack_top] -[EXTERN run_scheduler] - -[GLOBAL save_context_and_enter_scheduler] -; void save_context_and_enter_scheduler(struct saved_context *ctx); -save_context_and_enter_scheduler: - pushf - cli - pusha ; Pushes edi,esi,ebp,esp,ebx,edx,ecx,eax - - mov eax, cr3 - push eax - - mov eax, [esp+44] ; get address of saved_context structure - mov [eax], esp ; save esp - mov dword [eax+4], resume_saved_context ; save eip - - mov esp, kernel_stack_top - jmp run_scheduler - -resume_saved_context: - pop eax - mov cr3, eax - - popa - popf - ret - -[GLOBAL irq0_save_context_and_enter_scheduler] -; meant to be called on IRQ0 -; general registers already saved by IRQ handler stub -; flags already saved by interruption and interruptions disabled -; only saves CR3 -irq0_save_context_and_enter_scheduler: - mov eax, cr3 - push eax - - mov eax, [esp+8] ; get address of saved_context structure - mov [eax], esp ; save esp - mov dword [eax+4], resume_saved_irq0_context ; save eip - - mov esp, kernel_stack_top - jmp run_scheduler - -resume_saved_irq0_context: - pop eax - mov cr3, eax - ret - - -[GLOBAL resume_context] -resume_context: - mov eax, [esp+4] ; get address of saved context - mov esp, [eax] ; resume esp - mov ecx, [eax+4] ; jump to specified eip - jmp ecx - -; vim: set ts=4 sw=4 tw=0 noet : diff --git a/kernel/l0/dbglog.c b/kernel/l0/dbglog.c deleted file mode 100644 index e042625..0000000 --- a/kernel/l0/dbglog.c +++ /dev/null @@ -1,159 +0,0 @@ -#include -#include -#include -#include - -#include -#include -#include - -// ================================================================== - -#ifdef DBGLOG_TO_SCREEN - -static const size_t VGA_WIDTH = 80; -static const size_t VGA_HEIGHT = 25; - -static uint8_t vga_color = 7; -static uint16_t* vga_buffer = 0; -static uint16_t vga_row = 0, vga_column = 0; - -static uint16_t make_vgaentry(char c, uint8_t color) { - uint16_t c16 = c; - uint16_t color16 = color; - return c16 | color16 << 8; -} - -static void vga_putentryat(char c, uint8_t color, size_t x, size_t y) { - const size_t index = y * VGA_WIDTH + x; - vga_buffer[index] = make_vgaentry(c, color); -} - -static void vga_update_cursor() { - uint16_t cursor_location = vga_row * 80 + vga_column; - outb(0x3D4, 14); //Sending high cursor byte - outb(0x3D5, cursor_location >> 8); - outb(0x3D4, 15); //Sending high cursor byte - outb(0x3D5, cursor_location); -} - -static void vga_init() { - vga_row = 0; - vga_column = 0; - vga_buffer = (uint16_t*) (K_HIGHHALF_ADDR + 0xB8000); - - for (size_t y = 0; y < VGA_HEIGHT; y++) { - for (size_t x = 0; x < VGA_WIDTH; x++) { - vga_putentryat(' ', vga_color, x, y); - } - } - - vga_update_cursor(); -} - -static void vga_scroll() { - for (size_t i = 0; i < VGA_WIDTH * (VGA_HEIGHT - 1); i++) { - vga_buffer[i] = vga_buffer[i + VGA_WIDTH]; - } - for (size_t x = 0; x < VGA_WIDTH; x++) { - vga_putentryat(' ', vga_color, x, VGA_HEIGHT - 1); - } - vga_row--; -} - -static void vga_newline() { - vga_column = 0; - if (++vga_row == VGA_HEIGHT) { - vga_scroll(); - } -} - -static void vga_putc(char c) { - if (c == '\n') { - vga_newline(); - } else if (c == '\t') { - vga_putc(' '); - while (vga_column % 4 != 0) vga_putc(' '); - } else { - vga_putentryat(c, vga_color, vga_column, vga_row); - if (++vga_column == VGA_WIDTH) { - vga_newline(); - } - } -} - -static void vga_puts(const char* data) { - size_t datalen = strlen(data); - for (size_t i = 0; i < datalen; i++) - vga_putc(data[i]); - - vga_update_cursor(); -} - -#endif // DBGLOG_TO_SCREEN - -// ================================================================== - -#ifdef DBGLOG_TO_SERIAL - -#define SER_PORT 0x3F8 // COM1 - -static void serial_init() { - outb(SER_PORT + 1, 0x00); // disable interrupts - outb(SER_PORT + 3, 0x80); // set baud rate - outb(SER_PORT + 0, 0x03); // set divisor to 3 (38400 baud) - outb(SER_PORT + 1, 0x00); - outb(SER_PORT + 3, 0x03); // 8 bits, no parity, one stop bit - outb(SER_PORT + 2, 0xC7); // enable FIFO, clear them, with 14-byte threshold -} - -static void serial_putc(const char c) { - while (!(inb(SER_PORT + 5) & 0x20)); - outb(SER_PORT, c); -} - -static void serial_puts(const char *c) { - while (*c) { - serial_putc(*c); - c++; - } -} - -#endif // DBGLOG_TO_SERIAL - -// ================================================================== - -STATIC_MUTEX(dbglog_mutex); - -void dbglog_setup() { - mutex_lock(&dbglog_mutex); -#ifdef DBGLOG_TO_SCREEN - vga_init(); -#endif -#ifdef DBGLOG_TO_SERIAL - serial_init(); -#endif - mutex_unlock(&dbglog_mutex); -} - -void dbg_print(const char* str) { -#ifdef DBGLOG_TO_SCREEN - vga_puts(str); -#endif -#ifdef DBGLOG_TO_SERIAL - serial_puts(str); -#endif -} - -void dbg_printf(const char* fmt, ...) { - va_list ap; - char buffer[256]; - - va_start(ap, fmt); - vsnprintf(buffer, 256, fmt, ap); - va_end(ap); - - dbg_print(buffer); -} - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/l0/frame.c b/kernel/l0/frame.c deleted file mode 100644 index 489d010..0000000 --- a/kernel/l0/frame.c +++ /dev/null @@ -1,85 +0,0 @@ -#include -#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); -} - -STATIC_MUTEX(frame_allocator_mutex); - -uint32_t frame_alloc(size_t n) { - if (n > 32) return 0; - - mutex_lock(&frame_allocator_mutex); - 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; - - mutex_unlock(&frame_allocator_mutex); - return i * 32 + j; - } - } - } - mutex_unlock(&frame_allocator_mutex); - return 0; -} - -void frame_free(uint32_t base, size_t n) { - mutex_lock(&frame_allocator_mutex); - - for (size_t i = 0; i < n; i++) { - uint32_t idx = INDEX_FROM_BIT(base + i); - uint32_t ofs = OFFSET_FROM_BIT(base + i); - 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); - - mutex_unlock(&frame_allocator_mutex); -} - -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/gdt.c b/kernel/l0/gdt.c deleted file mode 100644 index eadde5f..0000000 --- a/kernel/l0/gdt.c +++ /dev/null @@ -1,90 +0,0 @@ -#include -#include - -#define GDT_ENTRIES 6 // The contents of each entry is defined in gdt_init. - -/* One entry of the table */ -struct gdt_entry { - uint16_t limit_low; - uint16_t base_low; - uint8_t base_middle; - uint8_t access; - uint8_t granularity; - uint8_t base_high; -} __attribute__((packed)); -typedef struct gdt_entry gdt_entry_t; - -/* Structure defining the whole table : address and size (in bytes). */ -struct gdt_ptr { - uint16_t limit; - uint32_t base; -} __attribute__((packed)); -typedef struct gdt_ptr gdt_ptr_t; - -/* The TSS is used for hardware multitasking. - We don't use that, but we still need a TSS so that user mode process exceptions - can be handled correctly by the kernel. */ -struct tss_entry { - uint32_t prev_tss; // The previous TSS - if we used hardware task switching this would form a linked list. - uint32_t esp0; // The stack pointer to load when we change to kernel mode. - uint32_t ss0; // The stack segment to load when we change to kernel mode. - uint32_t esp1; // Unused... - uint32_t ss1; - uint32_t esp2; - uint32_t ss2; - uint32_t cr3; - uint32_t eip; - uint32_t eflags; - uint32_t eax; - uint32_t ecx; - uint32_t edx; - uint32_t ebx; - uint32_t esp; - uint32_t ebp; - uint32_t esi; - uint32_t edi; - uint32_t es; // The value to load into ES when we change to kernel mode. - uint32_t cs; // The value to load into CS when we change to kernel mode. - uint32_t ss; // The value to load into SS when we change to kernel mode. - uint32_t ds; // The value to load into DS when we change to kernel mode. - uint32_t fs; // The value to load into FS when we change to kernel mode. - uint32_t gs; // The value to load into GS when we change to kernel mode. - uint32_t ldt; // Unused... - uint16_t trap; - uint16_t iomap_base; -} __attribute__((packed)); -typedef struct tss_entry tss_entry_t; - -// ========================= // -// Actual definitions - -static gdt_entry_t gdt_entries[GDT_ENTRIES]; -static gdt_ptr_t gdt_ptr; - -/* For internal use only. Writes one entry of the GDT with given parameters. */ -static void gdt_set_gate(int num, uint32_t base, uint32_t limit, uint8_t access, uint8_t gran) { - gdt_entries[num].base_low = (base & 0xFFFF); - gdt_entries[num].base_middle = (base >> 16) & 0xFF; - gdt_entries[num].base_high = (base >> 24) & 0xFF; - - gdt_entries[num].limit_low = (limit & 0xFFFF); - gdt_entries[num].granularity = (limit >> 16) & 0x0F; - gdt_entries[num].granularity |= gran & 0xF0; - gdt_entries[num].access = access; -} - -/* Write data to the GDT and enable it. */ -void gdt_init() { - gdt_ptr.limit = (sizeof(gdt_entry_t) * GDT_ENTRIES) - 1; - gdt_ptr.base = (uint32_t)&gdt_entries; - - gdt_set_gate(0, 0, 0, 0, 0); //Null segment - gdt_set_gate(1, 0, 0xFFFFFFFF, 0x9A, 0xCF); //Kernel code segment 0x08 - gdt_set_gate(2, 0, 0xFFFFFFFF, 0x92, 0xCF); //Kernel data segment 0x10 - gdt_set_gate(3, 0, 0xFFFFFFFF, 0xFA, 0xCF); //User code segment 0x18 - gdt_set_gate(4, 0, 0xFFFFFFFF, 0xF2, 0xCF); //User data segment 0x20 - - asm volatile ("lgdt %0"::"m"(gdt_ptr):"memory"); -} - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/l0/idt.c b/kernel/l0/idt.c deleted file mode 100644 index 2f244e3..0000000 --- a/kernel/l0/idt.c +++ /dev/null @@ -1,253 +0,0 @@ -#include -#include -#include -#include -#include - -struct idt_entry { - uint16_t base_lo; //Low part of address to jump to - uint16_t sel; //Kernel segment selector - uint8_t always0; - uint8_t type_attr; //Type - uint16_t base_hi; //High part of address to jump to -} __attribute__((packed)); -typedef struct idt_entry idt_entry_t; - -struct idt_ptr { - uint16_t limit; - uint32_t base; -} __attribute__((packed)); -typedef struct idt_ptr idt_ptr_t; - -#define GATE_TYPE_INTERRUPT 14 // IF is cleared on interrupt -#define GATE_TYPE_TRAP 15 // IF stays as is - -#define GATE_PRESENT (1<<7) -#define GATE_DPL_SHIFT 5 - - -void isr0(); -void isr1(); -void isr2(); -void isr3(); -void isr4(); -void isr5(); -void isr6(); -void isr7(); -void isr8(); -void isr9(); -void isr10(); -void isr11(); -void isr12(); -void isr13(); -void isr14(); -void isr15(); -void isr16(); -void isr17(); -void isr18(); -void isr19(); -void isr20(); -void isr21(); -void isr22(); -void isr23(); -void isr24(); -void isr25(); -void isr26(); -void isr27(); -void isr28(); -void isr29(); -void isr30(); -void isr31(); - -void irq0(); -void irq1(); -void irq2(); -void irq3(); -void irq4(); -void irq5(); -void irq6(); -void irq7(); -void irq8(); -void irq9(); -void irq10(); -void irq11(); -void irq12(); -void irq13(); -void irq14(); -void irq15(); - -void syscall64(); - -// ************************************************************ -// Handler code - -static idt_entry_t idt_entries[256]; -static idt_ptr_t idt_ptr; - -static isr_handler_t irq_handlers[16] = {0}; -static isr_handler_t ex_handlers[32] = {0}; - -/* Called in interrupt.s when an exception fires (interrupt 0 to 31) */ -void idt_exHandler(registers_t *regs) { - if (ex_handlers[regs->int_no] != 0) { - ex_handlers[regs->int_no](regs); - } else { - //TODO: make sure all exceptions happenning in userspace do not cause kernel panic... - dbg_printf("Unhandled exception: %i\n", regs->int_no); - dbg_dump_registers(regs); - PANIC("Unhandled exception"); - } -} - -/* Called in interrupt.s when an IRQ fires (interrupt 32 to 47) */ -void idt_irqHandler(registers_t *regs) { - if (regs->err_code > 7) { - outb(0xA0, 0x20); - } - outb(0x20, 0x20); - - dbg_printf("IRQ %i\n", regs->err_code); - if (irq_handlers[regs->err_code] != 0) { - irq_handlers[regs->err_code](regs); - } -} - -/* Caled in interrupt.s when a syscall is called */ -void idt_syscallHandler(registers_t *regs) { - dbg_printf("Syscall %i\n", regs->int_no); - // do nothing, yet. -} - -/* For internal use only. Sets up an entry of the IDT with given parameters. */ -static void idt_set_gate(uint8_t num, void (*fun)(), uint8_t type) { - uint32_t base = (uint32_t)fun; - - idt_entries[num].base_lo = base & 0xFFFF; - idt_entries[num].base_hi = (base >> 16) & 0xFFFF; - - idt_entries[num].sel = K_CODE_SEGMENT; - idt_entries[num].always0 = 0; - idt_entries[num].type_attr = GATE_PRESENT - | (3 << GATE_DPL_SHIFT) // accessible from user mode - | type; -} - -static const struct { - uint8_t num; - void (*fun)(); - uint8_t type; -} gates[] = { - // Most processor exceptions are traps and handling them - // should be preemptible - { 0, isr0, GATE_TYPE_TRAP }, - { 1, isr1, GATE_TYPE_TRAP }, - { 2, isr2, GATE_TYPE_TRAP }, - { 3, isr3, GATE_TYPE_TRAP }, - { 4, isr4, GATE_TYPE_TRAP }, - { 5, isr5, GATE_TYPE_TRAP }, - { 6, isr6, GATE_TYPE_TRAP }, - { 7, isr7, GATE_TYPE_TRAP }, - { 8, isr8, GATE_TYPE_TRAP }, - { 9, isr9, GATE_TYPE_TRAP }, - { 10, isr10, GATE_TYPE_TRAP }, - { 11, isr11, GATE_TYPE_TRAP }, - { 12, isr12, GATE_TYPE_TRAP }, - { 13, isr13, GATE_TYPE_TRAP }, - { 14, isr14, GATE_TYPE_INTERRUPT }, // reenables interrupts later on - { 15, isr15, GATE_TYPE_TRAP }, - { 16, isr16, GATE_TYPE_TRAP }, - { 17, isr17, GATE_TYPE_TRAP }, - { 18, isr18, GATE_TYPE_TRAP }, - { 19, isr19, GATE_TYPE_TRAP }, - { 20, isr20, GATE_TYPE_TRAP }, - { 21, isr21, GATE_TYPE_TRAP }, - { 22, isr22, GATE_TYPE_TRAP }, - { 23, isr23, GATE_TYPE_TRAP }, - { 24, isr24, GATE_TYPE_TRAP }, - { 25, isr25, GATE_TYPE_TRAP }, - { 26, isr26, GATE_TYPE_TRAP }, - { 27, isr27, GATE_TYPE_TRAP }, - { 28, isr28, GATE_TYPE_TRAP }, - { 29, isr29, GATE_TYPE_TRAP }, - { 30, isr30, GATE_TYPE_TRAP }, - { 31, isr31, GATE_TYPE_TRAP }, - - // IRQs are not preemptible ; an IRQ handler should do the bare minimum - // (communication with the hardware), and then pass a message to a worker - // process in order to do further processing - { 32, irq0, GATE_TYPE_INTERRUPT }, - { 33, irq1, GATE_TYPE_INTERRUPT }, - { 34, irq2, GATE_TYPE_INTERRUPT }, - { 35, irq3, GATE_TYPE_INTERRUPT }, - { 36, irq4, GATE_TYPE_INTERRUPT }, - { 37, irq5, GATE_TYPE_INTERRUPT }, - { 38, irq6, GATE_TYPE_INTERRUPT }, - { 39, irq7, GATE_TYPE_INTERRUPT }, - { 40, irq8, GATE_TYPE_INTERRUPT }, - { 41, irq9, GATE_TYPE_INTERRUPT }, - { 42, irq10, GATE_TYPE_INTERRUPT }, - { 43, irq11, GATE_TYPE_INTERRUPT }, - { 44, irq12, GATE_TYPE_INTERRUPT }, - { 45, irq13, GATE_TYPE_INTERRUPT }, - { 46, irq14, GATE_TYPE_INTERRUPT }, - { 47, irq15, GATE_TYPE_INTERRUPT }, - - // Of course, syscalls are preemptible - { 64, syscall64, GATE_TYPE_TRAP }, - - { 0, 0, 0 } -}; - -/* Remaps the IRQs. Sets up the IDT. */ -void idt_init() { - memset((uint8_t*)&idt_entries, 0, sizeof(idt_entry_t) * 256); - - //Remap the IRQ table - outb(0x20, 0x11); - outb(0xA0, 0x11); - outb(0x21, 0x20); - outb(0xA1, 0x28); - outb(0x21, 0x04); - outb(0xA1, 0x02); - outb(0x21, 0x01); - outb(0xA1, 0x01); - outb(0x21, 0x0); - outb(0xA1, 0x0); - - for (int i = 0; gates[i].type != 0; i++) { - idt_set_gate(gates[i].num, gates[i].fun, gates[i].type); - } - - idt_ptr.limit = (sizeof(idt_entry_t) * 256) - 1; - idt_ptr.base = (uint32_t)&idt_entries; - - asm volatile ("lidt %0"::"m"(idt_ptr):"memory"); - - // Some setup calls that come later on are not preemptible, - // so we wait until then to enable interrupts. -} - -/* Sets up an IRQ handler for given IRQ. */ -void idt_set_irq_handler(int number, isr_handler_t func) { - if (number < 16 && number >= 0) { - irq_handlers[number] = func; - } -} - -/* Sets up a handler for a processor exception */ -void idt_set_ex_handler(int number, isr_handler_t func) { - if (number >= 0 && number < 32) { - ex_handlers[number] = func; - } -} - -void dbg_dump_registers(registers_t *regs) { - dbg_printf("/ Exception %i\n", regs->int_no); - dbg_printf("| EAX: 0x%p EBX: 0x%p ECX: 0x%p EDX: 0x%p\n", regs->eax, regs->ebx, regs->ecx, regs->edx); - dbg_printf("| EDI: 0x%p ESI: 0x%p ESP: 0x%p EBP: 0x%p\n", regs->edi, regs->esi, regs->esp, regs->ebp); - dbg_printf("| EIP: 0x%p CS : 0x%p DS : 0x%p SS : 0x%p\n", regs->eip, regs->cs, regs->ds, regs->ss); - dbg_printf("\\ EFl: 0x%p I# : 0x%p Err: 0x%p\n", regs->eflags, regs->int_no, regs->err_code); -} - -/* vim: set ts=4 sw=4 tw=0 noet :*/ - diff --git a/kernel/l0/interrupt.s b/kernel/l0/interrupt.s deleted file mode 100644 index d40fff0..0000000 --- a/kernel/l0/interrupt.s +++ /dev/null @@ -1,126 +0,0 @@ -;************************************************************************************ - -%macro COMMONSTUB 1 -[EXTERN idt_%1Handler] -%1_common_stub: - - pusha ; Pushes edi,esi,ebp,esp,ebx,edx,ecx,eax - - mov ax, ds ; Lower 16-bits of eax = ds. - push eax ; save the data segment descriptor - - mov ax, 0x10 ; load the kernel data segment descriptor - mov ds, ax - mov es, ax - mov fs, ax - mov gs, ax - - ; pass the register data structure as a pointer to the function - ; (passing it directly results in GCC trashing the data when doing optimisations) - mov eax, esp - push eax - call idt_%1Handler - add esp, 4 - - pop eax ; reload the original data segment descriptor - mov ds, ax - mov es, ax - mov fs, ax - mov gs, ax - - popa ; Pops edi,esi,ebp... - add esp, 8 ; Cleans up the pushed error code and pushed ISR number - iret -%endmacro - -COMMONSTUB ex -COMMONSTUB irq -COMMONSTUB syscall - -;************************************************************************************ - -%macro EX_NOERRCODE 1 ; define a macro, taking one parameter - [GLOBAL isr%1] ; %1 accesses the first parameter. - isr%1: - push byte 0 - push byte %1 - jmp ex_common_stub -%endmacro - -%macro EX_ERRCODE 1 - [GLOBAL isr%1] - isr%1: - push byte %1 - jmp ex_common_stub -%endmacro - -%macro IRQ 2 - [GLOBAL irq%1] - irq%1: - push byte %1 ;push irq number - push byte %2 ;push int number - jmp irq_common_stub -%endmacro - -%macro SYSCALL 1 - [GLOBAL syscall%1] - syscall%1: - cli - push byte 0 - push byte %1 - jmp syscall_common_stub -%endmacro - -EX_NOERRCODE 0 -EX_NOERRCODE 1 -EX_NOERRCODE 2 -EX_NOERRCODE 3 -EX_NOERRCODE 4 -EX_NOERRCODE 5 -EX_NOERRCODE 6 -EX_NOERRCODE 7 -EX_ERRCODE 8 -EX_NOERRCODE 9 -EX_ERRCODE 10 -EX_ERRCODE 11 -EX_ERRCODE 12 -EX_ERRCODE 13 -EX_ERRCODE 14 -EX_NOERRCODE 15 -EX_NOERRCODE 16 -EX_NOERRCODE 17 -EX_NOERRCODE 18 -EX_NOERRCODE 19 -EX_NOERRCODE 20 -EX_NOERRCODE 21 -EX_NOERRCODE 22 -EX_NOERRCODE 23 -EX_NOERRCODE 24 -EX_NOERRCODE 25 -EX_NOERRCODE 26 -EX_NOERRCODE 27 -EX_NOERRCODE 28 -EX_NOERRCODE 29 -EX_NOERRCODE 30 -EX_NOERRCODE 31 - -IRQ 0, 32 -IRQ 1, 33 -IRQ 2, 34 -IRQ 3, 35 -IRQ 4, 36 -IRQ 5, 37 -IRQ 6, 38 -IRQ 7, 39 -IRQ 8, 40 -IRQ 9, 41 -IRQ 10, 42 -IRQ 11, 43 -IRQ 12, 44 -IRQ 13, 45 -IRQ 14, 46 -IRQ 15, 47 - -SYSCALL 64 - -; vim: set ts=4 sw=4 tw=0 noet : diff --git a/kernel/l0/kmain.c b/kernel/l0/kmain.c deleted file mode 100644 index 826fa14..0000000 --- a/kernel/l0/kmain.c +++ /dev/null @@ -1,214 +0,0 @@ -#include -#include -#include -#include - -#include -#include -#include -#include -#include -#include - -#include - -#include -#include - -extern const void k_end_addr; // defined in linker script : 0xC0000000 plus kernel stuff - -void breakpoint_handler(registers_t *regs) { - dbg_printf("Breakpoint! (int3)\n"); - BOCHS_BREAKPOINT; -} - -void region_test1() { - void* p = region_alloc(0x1000, "Test region", 0); - dbg_printf("Allocated one-page region: 0x%p\n", p); - dbg_print_region_info(); - void* q = region_alloc(0x1000, "Test region", 0); - dbg_printf("Allocated one-page region: 0x%p\n", q); - dbg_print_region_info(); - void* r = region_alloc(0x2000, "Test region", 0); - dbg_printf("Allocated two-page region: 0x%p\n", r); - dbg_print_region_info(); - void* s = region_alloc(0x10000, "Test region", 0); - dbg_printf("Allocated 16-page region: 0x%p\n", s); - dbg_print_region_info(); - region_free(p); - dbg_printf("Freed region 0x%p\n", p); - dbg_print_region_info(); - region_free(q); - dbg_printf("Freed region 0x%p\n", q); - dbg_print_region_info(); - region_free(r); - dbg_printf("Freed region 0x%p\n", r); - dbg_print_region_info(); - region_free(s); - dbg_printf("Freed region 0x%p\n", s); - dbg_print_region_info(); -} - -void region_test2() { - // allocate a big region and try to write into it - dbg_printf("Begin region test 2..."); - const size_t n = 200; - void* p0 = region_alloc(n * PAGE_SIZE, "Test big region", default_allocator_pf_handler); - for (size_t i = 0; i < n; i++) { - uint32_t *x = (uint32_t*)(p0 + i * PAGE_SIZE); - x[0] = 12; - x[1] = (i * 20422) % 122; - } - // unmap memory - for (size_t i = 0; i < n; i++) { - void* p = p0 + i * PAGE_SIZE; - uint32_t *x = (uint32_t*)p; - ASSERT(x[1] == (i * 20422) % 122); - - uint32_t f = pd_get_frame(p); - ASSERT(f != 0); - pd_unmap_page(p); - ASSERT(pd_get_frame(p) == 0); - - frame_free(f, 1); - } - region_free(p0); - dbg_printf("OK\n"); -} - -void kmalloc_test(void* kernel_data_end) { - // Test kmalloc ! - dbg_print_region_info(); - dbg_printf("Begin kmalloc test...\n"); - const int m = 200; - uint16_t** ptr = kmalloc(m * sizeof(uint32_t)); - for (int i = 0; i < m; i++) { - size_t s = 1 << ((i * 7) % 11 + 2); - ptr[i] = (uint16_t*)kmalloc(s); - ASSERT((void*)ptr[i] >= kernel_data_end && (size_t)ptr[i] < 0xFFC00000); - *ptr[i] = ((i * 211) % 1024); - } - dbg_printf("Fully allocated.\n"); - dbg_print_region_info(); - for (int i = 0; i < m; i++) { - for (int j = i; j < m; j++) { - ASSERT(*ptr[j] == (j * 211) % 1024); - } - kfree(ptr[i]); - } - kfree(ptr); - dbg_printf("Kmalloc test OK.\n"); - dbg_print_region_info(); -} - -void test_hashtbl_1() { - // hashtable test - hashtbl_t *ht = create_hashtbl(str_key_eq_fun, str_hash_fun, 0); - hashtbl_add(ht, "test1", "Hello, world [test1]"); - hashtbl_add(ht, "test2", "Hello, world [test2]"); - dbg_printf("ht[test1] = %s\n", hashtbl_find(ht, "test1")); - dbg_printf("ht[test] = %s\n", hashtbl_find(ht, "test")); - dbg_printf("ht[test2] = %s\n", hashtbl_find(ht, "test2")); - dbg_printf("adding test...\n"); - hashtbl_add(ht, "test", "Forever alone"); - dbg_printf("ht[test1] = %s\n", hashtbl_find(ht, "test1")); - dbg_printf("ht[test] = %s\n", hashtbl_find(ht, "test")); - dbg_printf("ht[test2] = %s\n", hashtbl_find(ht, "test2")); - dbg_printf("removing test1...\n"); - hashtbl_remove(ht, "test1"); - dbg_printf("ht[test1] = %s\n", hashtbl_find(ht, "test1")); - dbg_printf("ht[test] = %s\n", hashtbl_find(ht, "test")); - dbg_printf("ht[test2] = %s\n", hashtbl_find(ht, "test2")); - delete_hashtbl(ht); -} - -void test_hashtbl_2() { - hashtbl_t *ht = create_hashtbl(id_key_eq_fun, id_hash_fun, 0); - hashtbl_add(ht, (void*)12, "Hello, world [12]"); - hashtbl_add(ht, (void*)777, "Hello, world [777]"); - dbg_printf("ht[12] = %s\n", hashtbl_find(ht, (void*)12)); - dbg_printf("ht[144] = %s\n", hashtbl_find(ht, (void*)144)); - dbg_printf("ht[777] = %s\n", hashtbl_find(ht, (void*)777)); - dbg_printf("adding 144...\n"); - hashtbl_add(ht, (void*)144, "Forever alone"); - dbg_printf("ht[12] = %s\n", hashtbl_find(ht, (void*)12)); - dbg_printf("ht[144] = %s\n", hashtbl_find(ht, (void*)144)); - dbg_printf("ht[777] = %s\n", hashtbl_find(ht, (void*)777)); - dbg_printf("removing 12...\n"); - hashtbl_remove(ht, (void*)12); - dbg_printf("ht[12] = %s\n", hashtbl_find(ht, (void*)12)); - dbg_printf("ht[144] = %s\n", hashtbl_find(ht, (void*)144)); - dbg_printf("ht[777] = %s\n", hashtbl_find(ht, (void*)777)); - delete_hashtbl(ht); -} - -void test_thread(void* a) { - for(int i = 0; i < 120; i++) { - dbg_printf("b"); - for (int x = 0; x < 100000; x++) asm volatile("xor %%ebx, %%ebx":::"%ebx"); - if (i % 8 == 0) yield(); - } -} -void kernel_init_stage2(void* data) { - dbg_print_region_info(); - dbg_print_frame_stats(); - - test_hashtbl_1(); - test_hashtbl_2(); - - thread_t *tb = new_thread(test_thread, 0); - resume_thread(tb, false); - - for (int i = 0; i < 120; i++) { - dbg_printf("a"); - for (int x = 0; x < 100000; x++) asm volatile("xor %%ebx, %%ebx":::"%ebx"); - } - PANIC("Reached kmain end! Falling off the edge."); -} - -void kmain(struct multiboot_info_t *mbd, int32_t mb_magic) { - dbglog_setup(); - - dbg_printf("Hello, kernel world!\n"); - dbg_printf("This is %s, version %s.\n", OS_NAME, OS_VERSION); - - ASSERT(mb_magic == MULTIBOOT_BOOTLOADER_MAGIC); - - gdt_init(); dbg_printf("GDT set up.\n"); - - idt_init(); dbg_printf("IDT set up.\n"); - idt_set_ex_handler(EX_BREAKPOINT, breakpoint_handler); - 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); - - // 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(); - - paging_setup(kernel_data_end); - dbg_printf("Paging seems to be working!\n"); - - BOCHS_BREAKPOINT; - - region_allocator_init(kernel_data_end); - region_test1(); - region_test2(); - - kmalloc_setup(); - kmalloc_test(kernel_data_end); - - // enter multi-threading mode - // interrupts are enabled at this moment, so all - // code run from now on should be preemtible (ie thread-safe) - threading_setup(kernel_init_stage2, 0); - PANIC("Should never come here."); -} - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/l0/kmalloc.c b/kernel/l0/kmalloc.c deleted file mode 100644 index e356ada..0000000 --- a/kernel/l0/kmalloc.c +++ /dev/null @@ -1,52 +0,0 @@ -#include - -#include -#include - -#include -#include -#include - -static void* page_alloc_fun_for_kmalloc(size_t bytes) { - void* addr = region_alloc(bytes, "Core kernel heap", default_allocator_pf_handler); - return addr; -} - -static slab_type_t slab_sizes[] = { - { "8B kmalloc objects", 8, 2 }, - { "16B kmalloc objects", 16, 2 }, - { "32B kmalloc objects", 32, 2 }, - { "64B kmalloc objects", 64, 4 }, - { "128B kmalloc objects", 128, 4 }, - { "256B kmalloc objects", 256, 4 }, - { "512B kmalloc objects", 512, 8 }, - { "1KB kmalloc objects", 1024, 8 }, - { "2KB kmalloc objects", 2048, 16 }, - { "4KB kmalloc objects", 4096, 16 }, - { 0, 0, 0 } -}; - -static mem_allocator_t *kernel_allocator = 0; -STATIC_MUTEX(kmalloc_mutex); - -void kmalloc_setup() { - kernel_allocator = - create_slab_allocator(slab_sizes, page_alloc_fun_for_kmalloc, - region_free_unmap_free); -} - -void* kmalloc(size_t sz) { - void* res = 0; - - mutex_lock(&kmalloc_mutex); - res = slab_alloc(kernel_allocator, sz); - mutex_unlock(&kmalloc_mutex); - - return res; -} - -void kfree(void* ptr) { - mutex_lock(&kmalloc_mutex); - slab_free(kernel_allocator, ptr); - mutex_unlock(&kmalloc_mutex); -} diff --git a/kernel/l0/loader.s b/kernel/l0/loader.s deleted file mode 100644 index 447d82d..0000000 --- a/kernel/l0/loader.s +++ /dev/null @@ -1,86 +0,0 @@ -[EXTERN kmain] ; kmain is defined in kmain.c -[GLOBAL loader] ; making entry point visible to linker -[GLOBAL kernel_pd] ; make kernel page directory visible -[GLOBAL kernel_stack_protector] ; used to detect kernel stack overflow -[GLOBAL kernel_stack_top] ; stack re-used by scheduler - -; higher-half kernel setup -K_HIGHHALF_ADDR equ 0xC0000000 -K_PAGE_NUMBER equ (K_HIGHHALF_ADDR >> 22) - -; loader stack size -LOADER_STACK_SIZE equ 0x8000 ; 8Kb - -; setting up the Multiboot header - see GRUB docs for details -MODULEALIGN equ 1<<0 ; align loaded modules on page boundaries -MEMINFO equ 1<<1 ; provide memory map -FLAGS equ MODULEALIGN | MEMINFO ; this is the Multiboot 'flag' field -MAGIC equ 0x1BADB002 ; 'magic number' lets bootloader find the header -CHECKSUM equ -(MAGIC + FLAGS) ; checksum required - -[section .setup] -align 4 -multiboot_header: - dd MAGIC - dd FLAGS - dd CHECKSUM - -loader: - ; setup the boot page directory used for higher-half - mov ecx, kernel_pd - sub ecx, K_HIGHHALF_ADDR ; access its lower-half address - mov cr3, ecx - - ; Set PSE bit in CR4 to enable 4MB pages. - mov ecx, cr4 - or ecx, 0x00000010 - mov cr4, ecx - - ; Set PG bit in CR0 to enable paging. - mov ecx, cr0 - or ecx, 0x80000000 - mov cr0, ecx - - ; long jump required - lea ecx, [higherhalf] - jmp ecx - -[section .data] -align 0x1000 -kernel_pd: - ; uses 4MB pages - ; identity-maps the first 4Mb of RAM, and also maps them with offset += k_highhalf_addr - dd 0x00000083 - times (K_PAGE_NUMBER - 1) dd 0 - dd 0x00000083 - times (1024 - K_PAGE_NUMBER - 1) dd 0 - -[section .text] -higherhalf: ; now we're running in higher half - ; unmap first 4Mb - mov dword [kernel_pd], 0 - invlpg [0] - - mov esp, kernel_stack_top ; set up the stack - - push eax ; pass Multiboot magic number - add ebx, K_HIGHHALF_ADDR ; update the MB info structure so that it is in higher half - push ebx ; pass Multiboot info structure - - call kmain ; call kernel proper - -hang: - ; halt machine should kernel return - cli - hlt - jmp hang - -[section .bss] -align 0x1000 -kernel_stack_protector: - resb 0x1000 ; as soon as we have efficient paging, we WON'T map this page -kernel_stack_bottom: - resb LOADER_STACK_SIZE -kernel_stack_top: - -; vim: set ts=4 sw=4 tw=0 noet : diff --git a/kernel/l0/paging.c b/kernel/l0/paging.c deleted file mode 100644 index 683abe6..0000000 --- a/kernel/l0/paging.c +++ /dev/null @@ -1,298 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include - -#define PAGE_OF_ADDR(x) (((size_t)x >> PAGE_SHIFT) % N_PAGES_IN_PT) -#define PT_OF_ADDR(x) ((size_t)x >> (PAGE_SHIFT + PT_SHIFT)) - -#define PTE_PRESENT (1<<0) -#define PTE_RW (1<<1) -#define PTE_USER (1<<2) -#define PTE_WRITE_THROUGH (1<<3) -#define PTE_DISABLE_CACHE (1<<4) -#define PTE_ACCESSED (1<<5) -#define PTE_DIRTY (1<<6) // only PTE -#define PTE_SIZE_4M (1<<7) // only PDE -#define PTE_GLOBAL (1<<8) // only PTE -#define PTE_FRAME_SHIFT 12 - -typedef struct page_table { - uint32_t page[1024]; -} pagetable_t; - -struct page_directory { - uint32_t phys_addr; // physical address of page directory - // to modify a page directory, we first map it - // then we can use mirroring to edit it - // (the last 4M of the address space are mapped to the PD itself) - - mutex_t mutex; -}; - - -// access kernel page directory page defined in loader.s -// (this is a correct higher-half address) -extern pagetable_t kernel_pd; - -// pre-allocate a page table so that we can map the first 4M of kernel memory -static pagetable_t __attribute__((aligned(PAGE_SIZE))) kernel_pt0; - -extern char kernel_stack_protector; - -static pagedir_t kernel_pd_d; - -#define current_pt ((pagetable_t*)PD_MIRROR_ADDR) -#define current_pd ((pagetable_t*)(PD_MIRROR_ADDR + (N_PAGES_IN_PT-1)*PAGE_SIZE)) - -void page_fault_handler(registers_t *regs) { - void* vaddr; - asm volatile("movl %%cr2, %0":"=r"(vaddr)); - - if ((size_t)vaddr >= K_HIGHHALF_ADDR) { - uint32_t pt = PT_OF_ADDR(vaddr); - - if (current_pd != &kernel_pd && current_pd->page[pt] != kernel_pd.page[pt]) { - current_pd->page[pt] = kernel_pd.page[pt]; - invlpg(¤t_pt[pt]); - return; - } - if (regs->eflags & EFLAGS_IF) asm volatile("sti"); // from now on we are preemptible - - if (vaddr >= (void*)&kernel_stack_protector && vaddr < (void*)&kernel_stack_protector + PAGE_SIZE) { - dbg_printf("Kernel stack overflow at 0x%p\n", vaddr); - PANIC("Kernel stack overflow."); - } - - if ((size_t)vaddr >= PD_MIRROR_ADDR) { - dbg_printf("Fault on access to mirrorred PD at 0x%p\n", vaddr); - dbg_print_region_info(); - PANIC("Unhandled kernel space page fault"); - } - - region_info_t *i = find_region(vaddr); - if (i == 0) { - dbg_printf("Kernel pagefault in non-existing region at 0x%p\n", vaddr); - dbg_dump_registers(regs); - PANIC("Unhandled kernel space page fault"); - } - if (i->pf == 0) { - dbg_printf("Kernel pagefault in region with no handler at 0x%p\n", vaddr); - dbg_dump_registers(regs); - dbg_print_region_info(); - PANIC("Unhandled kernel space page fault"); - } - i->pf(get_current_pagedir(), i, vaddr); - } else { - if (regs->eflags & EFLAGS_IF) asm volatile("sti"); // userspace PF handlers should always be preemptible - - dbg_printf("Userspace page fault at 0x%p\n", vaddr); - PANIC("Unhandled userspace page fault"); - // not handled yet - // TODO - } -} - -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; - - ASSERT(n_kernel_pages <= 1024); // we use less than 4M for kernel - - // setup kernel_pd_d structure - kernel_pd_d.phys_addr = (size_t)&kernel_pd - K_HIGHHALF_ADDR; - kernel_pd_d.mutex = MUTEX_UNLOCKED; - - // setup kernel_pt0 - ASSERT(PAGE_OF_ADDR(K_HIGHHALF_ADDR) == 0); // kernel is 4M-aligned - ASSERT(FIRST_KERNEL_PT == 768); - for (size_t i = 0; i < n_kernel_pages; i++) { - if ((i * PAGE_SIZE) + K_HIGHHALF_ADDR == (size_t)&kernel_stack_protector) { - kernel_pt0.page[i] = 0; // don't map kernel stack protector page - frame_free(i, 1); - } else { - kernel_pt0.page[i] = (i << PTE_FRAME_SHIFT) | PTE_PRESENT | PTE_RW | PTE_GLOBAL; - } - } - for (size_t i = n_kernel_pages; i < 1024; i++){ - kernel_pt0.page[i] = 0; - } - - // replace 4M mapping by kernel_pt0 - kernel_pd.page[FIRST_KERNEL_PT] = - (((size_t)&kernel_pt0 - K_HIGHHALF_ADDR) & PAGE_MASK) | PTE_PRESENT | PTE_RW; - // set up mirroring - kernel_pd.page[N_PAGES_IN_PT-1] = - (((size_t)&kernel_pd - K_HIGHHALF_ADDR) & PAGE_MASK) | PTE_PRESENT | PTE_RW; - - invlpg((void*)K_HIGHHALF_ADDR); - - // paging already enabled in loader, nothing to do. - - // disable 4M pages (remove PSE bit in CR4) - uint32_t cr4; - asm volatile("movl %%cr4, %0": "=r"(cr4)); - cr4 &= ~0x00000010; - asm volatile("movl %0, %%cr4":: "r"(cr4)); - - idt_set_ex_handler(EX_PAGE_FAULT, page_fault_handler); -} - -pagedir_t *get_current_pagedir() { - if (current_thread == 0) return &kernel_pd_d; - return current_thread->current_pd_d; -} - -pagedir_t *get_kernel_pagedir() { - return &kernel_pd_d; -} - -void switch_pagedir(pagedir_t *pd) { - asm volatile("movl %0, %%cr3":: "r"(pd->phys_addr)); - if (current_thread != 0) current_thread->current_pd_d = pd; -} - -// ============================== // -// Mapping and unmapping of pages // -// ============================== // - -uint32_t pd_get_frame(void* vaddr) { - uint32_t pt = PT_OF_ADDR(vaddr); - uint32_t page = PAGE_OF_ADDR(vaddr); - - pagetable_t *pd = ((size_t)vaddr >= K_HIGHHALF_ADDR ? &kernel_pd : current_pd); - - if (!pd->page[pt] & PTE_PRESENT) return 0; - if (!current_pt[pt].page[page] & PTE_PRESENT) return 0; - return current_pt[pt].page[page] >> PTE_FRAME_SHIFT; -} - -int pd_map_page(void* vaddr, uint32_t frame_id, bool rw) { - uint32_t pt = PT_OF_ADDR(vaddr); - uint32_t page = PAGE_OF_ADDR(vaddr); - - ASSERT((size_t)vaddr < PD_MIRROR_ADDR); - - pagedir_t *pdd = ((size_t)vaddr >= K_HIGHHALF_ADDR || current_thread == 0 - ? &kernel_pd_d : current_thread->current_pd_d); - pagetable_t *pd = ((size_t)vaddr >= K_HIGHHALF_ADDR ? &kernel_pd : current_pd); - mutex_lock(&pdd->mutex); - - if (!pd->page[pt] & PTE_PRESENT) { - uint32_t new_pt_frame = frame_alloc(1); - if (new_pt_frame == 0) { - mutex_unlock(&pdd->mutex); - return 1; // OOM - } - - current_pd->page[pt] = pd->page[pt] = - (new_pt_frame << PTE_FRAME_SHIFT) | PTE_PRESENT | PTE_RW; - invlpg(¤t_pt[pt]); - } - current_pt[pt].page[page] = - (frame_id << PTE_FRAME_SHIFT) - | PTE_PRESENT - | ((size_t)vaddr < K_HIGHHALF_ADDR ? PTE_USER : PTE_GLOBAL) - | (rw ? PTE_RW : 0); - invlpg(vaddr); - - mutex_unlock(&pdd->mutex); - return 0; -} - -void pd_unmap_page(void* vaddr) { - uint32_t pt = PT_OF_ADDR(vaddr); - uint32_t page = PAGE_OF_ADDR(vaddr); - - pagetable_t *pd = ((size_t)vaddr >= K_HIGHHALF_ADDR ? &kernel_pd : current_pd); - // no need to lock the PD's mutex - - if (!pd->page[pt] & PTE_PRESENT) return; - if (!current_pt[pt].page[page] & PTE_PRESENT) return; - - current_pt[pt].page[page] = 0; - invlpg(vaddr); - - // If the page table is completely empty we might want to free - // it, but we would actually lose a lot of time checking if - // the PT is really empty (since we don't store the - // number of used pages in each PT), so it's probably not worth it -} - -// Creation and deletion of page directories - -pagedir_t *create_pagedir() { - uint32_t pd_phys = 0; - pagedir_t *pd = 0; - void* temp = 0; - - pd_phys = frame_alloc(1); - if (pd_phys == 0) goto error; - - pd = (pagedir_t*)kmalloc(sizeof(pagedir_t)); - if (pd == 0) goto error; - - temp = region_alloc(PAGE_SIZE, 0, 0); - if (temp == 0) goto error; - - int error = pd_map_page(temp, pd_phys, true); - if (error) goto error; - - pd->phys_addr = pd_phys * PAGE_SIZE; - pd->mutex = MUTEX_UNLOCKED; - - // initialize PD with zeroes - pagetable_t *pt = (pagetable_t*)temp; - for (size_t i = 0; i < N_PAGES_IN_PT; i++) { - pt->page[i] = 0; - } - // use kernel page tables - for(size_t i = FIRST_KERNEL_PT; i < N_PAGES_IN_PT-1; i++) { - pt->page[i] = kernel_pd.page[i]; - } - // set up mirroring - pt->page[N_PAGES_IN_PT-1] = pd->phys_addr | PTE_PRESENT | PTE_RW; - - region_free_unmap(temp); - - return pd; - - error: - if (pd_phys != 0) frame_free(pd_phys, 1); - if (pd != 0) kfree(pd); - if (temp != 0) region_free(temp); - return 0; -} - -void delete_pagedir(pagedir_t *pd) { - pagedir_t *restore_pd = get_current_pagedir(); - if (restore_pd == pd) restore_pd = &kernel_pd_d; - - // make a copy of page directory on the stack - switch_pagedir(pd); - pagetable_t backup; - for (size_t i = 0; i < N_PAGES_IN_PT; i++) { - backup.page[i] = current_pd->page[i]; - } - switch_pagedir(restore_pd); - - // free the page tables - for (size_t i = 0; i < FIRST_KERNEL_PT; i++) { - if (backup.page[i] & PTE_PRESENT) - frame_free(backup.page[i] >> PTE_FRAME_SHIFT, 1); - } - // free the page directory page - uint32_t pd_phys = pd->phys_addr / PAGE_SIZE; - ASSERT(pd_phys == (backup.page[N_PAGES_IN_PT-1] >> PTE_FRAME_SHIFT)); - frame_free(pd_phys, 1); - // free the pagedir_t structure - kfree(pd); - - return; -} - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/l0/region.c b/kernel/l0/region.c deleted file mode 100644 index 3127048..0000000 --- a/kernel/l0/region.c +++ /dev/null @@ -1,397 +0,0 @@ -#include -#include -#include -#include - -typedef union region_descriptor { - struct { - union region_descriptor *next; - } unused_descriptor; - struct { - void* addr; - size_t 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_RESERVE_DESCRIPTORS 2 // always keep at least 2 unused descriptors - -#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; -uint32_t n_unused_descriptors; -static descriptor_t *first_free_region_by_addr, *first_free_region_by_size; -static descriptor_t *first_used_region; - -STATIC_MUTEX(ra_mutex); // region allocator mutex - -// ========================================================= // -// HELPER FUNCTIONS FOR THE MANIPULATION OF THE REGION LISTS // -// ========================================================= // - -static void add_unused_descriptor(descriptor_t *d) { - n_unused_descriptors++; - 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; - n_unused_descriptors--; - } - 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->free.addr > d->free.addr) { - d->free.next_by_addr = i->free.next_by_addr; - i->free.next_by_addr = d; - 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 { - // 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) { - d->free.next_by_size = 0; - d->free.first_bigger = 0; - i->free.next_by_size = d; - if (d->free.size > i->free.size) i->free.first_bigger = d; - break; - } else if (i->free.next_by_size->free.size >= d->free.size) { - 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); - i->free.next_by_size = d; - if (d->free.size > i->free.size) i->free.first_bigger = d; - break; - } else { - // continue - i = i->free.next_by_size; - } - } - } -} - -static descriptor_t *find_used_region(void* 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) { - n_unused_descriptors = 0; - first_unused_descriptor = 0; - for (int i = 0; i < N_BASE_DESCRIPTORS; i++) { - add_unused_descriptor(&base_descriptors[i]); - } - - descriptor_t *f0 = get_unused_descriptor(); - f0->free.addr = (void*)PAGE_ALIGN_UP(kernel_data_end); - f0->free.size = ((void*)LAST_KERNEL_ADDR - f0->free.addr); - f0->free.next_by_size = 0; - f0->free.first_bigger = 0; - first_free_region_by_size = first_free_region_by_addr = f0; - - descriptor_t *u0 = get_unused_descriptor(); - u0->used.i.addr = (void*)K_HIGHHALF_ADDR; - u0->used.i.size = PAGE_ALIGN_UP(kernel_data_end) - K_HIGHHALF_ADDR; - u0->used.i.type = "Kernel code & data"; - u0->used.i.pf = 0; - u0->used.next_by_addr = 0; - first_used_region = u0; -} - -static void region_free_inner(void* 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 region_free(void* addr) { - mutex_lock(&ra_mutex); - region_free_inner(addr); - mutex_unlock(&ra_mutex); -} - -static void* region_alloc_inner(size_t size, char* type, page_fault_handler_t pf, bool use_reserve) { - 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) { - // region i is the one we want to allocate in - descriptor_t *x = 0; - if (i->free.size > size) { - if (n_unused_descriptors <= N_RESERVE_DESCRIPTORS && !use_reserve) { - return 0; - } - - // this assert basically means that the allocation function - // is called less than N_RESERVE_DESCRIPTORS times with - // the use_reserve flag before more descriptors - // are allocated. - x = get_unused_descriptor(); - ASSERT(x != 0); - - 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; - } - } - // do the allocation - remove_free_region(i); - if (x != 0) add_free_region(x); - - void* 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; //No big enough block found -} - -void* region_alloc(size_t size, char* type, page_fault_handler_t pf) { - void* result = 0; - mutex_lock(&ra_mutex); - - if (n_unused_descriptors <= N_RESERVE_DESCRIPTORS) { - uint32_t frame = frame_alloc(1); - if (frame == 0) goto try_anyway; - - void* descriptor_region = region_alloc_inner(PAGE_SIZE, "Region descriptors", 0, true); - ASSERT(descriptor_region != 0); - - int error = pd_map_page(descriptor_region, frame, 1); - if (error) { - // this can happen if we weren't able to allocate a frame for - // a new pagetable - frame_free(frame, 1); - region_free_inner(descriptor_region); - goto try_anyway; - } - - for (descriptor_t *d = (descriptor_t*)descriptor_region; - (void*)(d+1) <= (descriptor_region + PAGE_SIZE); - d++) { - add_unused_descriptor(d); - } - } - try_anyway: - // even if we don't have enough unused descriptors, we might find - // a free region that has exactly the right size and therefore - // does not require splitting, so we try the allocation in all cases - result = region_alloc_inner(size, type, pf, false); - - mutex_unlock(&ra_mutex); - return result; -} - -region_info_t *find_region(void* addr) { - region_info_t *r = 0; - mutex_lock(&ra_mutex); - - descriptor_t *d = find_used_region(addr); - if (d != 0) r = &d->used.i; - - mutex_unlock(&ra_mutex); - return r; -} - -// ========================================================= // -// HELPER FUNCTIONS : SIMPLE PF HANDLERS ; FREEING FUNCTIONS // -// ========================================================= // - -void default_allocator_pf_handler(pagedir_t *pd, struct region_info *r, void* addr) { - ASSERT(pd_get_frame(addr) == 0); // if error is of another type (RO, protected), we don't do anyting - - uint32_t f = frame_alloc(1); - if (f == 0) PANIC("Out Of Memory"); - - int error = pd_map_page(addr, f, 1); - if (error) PANIC("Could not map frame (OOM)"); -} - -void region_free_unmap_free(void* ptr) { - region_info_t *i = find_region(ptr); - ASSERT(i != 0); - - for (void* x = i->addr; x < i->addr + i->size; x += PAGE_SIZE) { - uint32_t f = pd_get_frame(x); - if (f != 0) { - pd_unmap_page(x); - frame_free(f, 1); - } - } - region_free(ptr); -} - -void region_free_unmap(void* ptr) { - region_info_t *i = find_region(ptr); - ASSERT(i != 0); - - for (void* x = i->addr; x < i->addr + i->size; x += PAGE_SIZE) { - pd_unmap_page(x); - } - region_free(ptr); -} - -// =========================== // -// DEBUG LOG PRINTING FUNCTION // -// =========================== // - -void dbg_print_region_info() { - mutex_lock(&ra_mutex); - - 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 %s\n", d->used.i.addr, d->used.i.addr + d->used.i.size, d->used.i.type); - ASSERT(d != d->used.next_by_addr); - } - dbg_printf("\\\n"); - - mutex_unlock(&ra_mutex); -} - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/l0/sys.c b/kernel/l0/sys.c deleted file mode 100644 index 2b77463..0000000 --- a/kernel/l0/sys.c +++ /dev/null @@ -1,25 +0,0 @@ -#include -#include - - -// Kernel panic and kernel assert failure - -static void panic_do(const char* type, const char *msg, const char* file, int line) { - asm volatile("cli;"); - dbg_printf("/\n| %s:\t%s\n", type, msg); - dbg_printf("| File: \t%s:%i\n", file, line); - dbg_printf("| System halted -_-'\n"); - dbg_printf("\\---------------------------------------------------------/"); - BOCHS_BREAKPOINT; - asm volatile("hlt"); -} - -void panic(const char* message, const char* file, int line) { - panic_do("PANIC", message, file, line); -} - -void panic_assert(const char* assertion, const char* file, int line) { - panic_do("ASSERT FAILED", assertion, file, line); -} - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/l0/thread.c b/kernel/l0/thread.c deleted file mode 100644 index 0f5c209..0000000 --- a/kernel/l0/thread.c +++ /dev/null @@ -1,208 +0,0 @@ -#include -#include -#include -#include - -#include -#include - -void save_context_and_enter_scheduler(saved_context_t *ctx); -void irq0_save_context_and_enter_scheduler(saved_context_t *ctx); -void resume_context(saved_context_t *ctx); - -thread_t *current_thread = 0; - -// ====================== // -// THE PROGRAMMABLE TIMER // -// ====================== // - -void set_pit_frequency(uint32_t freq) { - uint32_t divisor = 1193180 / freq; - ASSERT(divisor < 65536); // must fit on 16 bits - - uint8_t l = (divisor & 0xFF); - uint8_t h = ((divisor >> 8) & 0xFF); - - outb(0x43, 0x36); - outb(0x40, l); - outb(0x40, h); -} - -// ============================= // -// HELPER : IF FLAG MANIPULATION // -// ============================= // - -static inline bool disable_interrupts() { - uint32_t eflags; - asm volatile("pushf; pop %0" : "=r"(eflags)); - asm volatile("cli"); - return (eflags & EFLAGS_IF) != 0; -} - -static inline void resume_interrupts(bool st) { - if (st) asm volatile("sti"); -} - -// ================== // -// THE TASK SCHEDULER // -// ================== // - -static thread_t *queue_first_thread = 0, *queue_last_thread = 0; - -void enqueue_thread(thread_t *t, bool just_ran) { - ASSERT(t->state == T_STATE_RUNNING); - if (queue_first_thread == 0) { - queue_first_thread = queue_last_thread = t; - t->next_in_queue = 0; - } else if (just_ran) { - t->next_in_queue = 0; - queue_last_thread->next_in_queue = t; - queue_last_thread = t; - } else { - t->next_in_queue = queue_first_thread; - queue_first_thread = t; - } -} - -thread_t* dequeue_thread() { - thread_t *t = queue_first_thread; - if (t == 0) return 0; - - queue_first_thread = t->next_in_queue; - if (queue_first_thread == 0) queue_last_thread = 0; - - return t; -} - -// ================ // -// THE TASKING CODE // -// ================ // - -void run_scheduler() { - // At this point, interrupts are disabled - // This function is expected NEVER TO RETURN - - if (current_thread != 0 && current_thread->state == T_STATE_RUNNING) { - enqueue_thread(current_thread, true); - } - - current_thread = dequeue_thread(); - if (current_thread != 0) { - resume_context(¤t_thread->ctx); - } else { - // Wait for an IRQ - asm volatile("sti; hlt"); - // At this point an IRQ has happenned - // and has been processed. Loop around. - run_scheduler(); - ASSERT(false); - } -} - -static void run_thread(void (*entry)(void*), void* data) { - ASSERT(current_thread->state == T_STATE_RUNNING); - - switch_pagedir(get_kernel_pagedir()); - - asm volatile("sti"); - entry(data); - - current_thread->state = T_STATE_FINISHED; - // TODO : add job for deleting the thread, or whatever - yield(); // expected never to return! - ASSERT(false); -} -thread_t *new_thread(entry_t entry, void* data) { - thread_t *t = (thread_t*)kmalloc(sizeof(thread_t)); - if (t == 0) return 0; - - void* stack = region_alloc(KPROC_STACK_SIZE, "Stack", 0); - if (stack == 0) { - kfree(t); - return 0; - } - - for (void* i = stack + PAGE_SIZE; i < stack + KPROC_STACK_SIZE; i += PAGE_SIZE) { - uint32_t f = frame_alloc(1); - if (f == 0) { - region_free_unmap_free(stack); - kfree(t); - return 0; - } - pd_map_page(i, f, true); - } - - t->stack_region = find_region(stack); - - t->ctx.esp = (uint32_t*)(t->stack_region->addr + t->stack_region->size); - *(--t->ctx.esp) = (uint32_t)data; // push second argument : data - *(--t->ctx.esp) = (uint32_t)entry; // push first argument : entry point - *(--t->ctx.esp) = 0; // push invalid return address (the run_thread function never returns) - - t->ctx.eip = (void(*)())run_thread; - t->state = T_STATE_PAUSED; - - t->current_pd_d = get_kernel_pagedir(); - - t->proc = 0; // used by L1 functions - - return t; -} - -// ========== // -// SETUP CODE // -// ========== // - -static void irq0_handler(registers_t *regs) { - if (current_thread != 0) - irq0_save_context_and_enter_scheduler(¤t_thread->ctx); -} -void threading_setup(entry_t cont, void* arg) { - set_pit_frequency(TASK_SWITCH_FREQUENCY); - idt_set_irq_handler(IRQ0, irq0_handler); - - thread_t *t = new_thread(cont, arg); - ASSERT(t != 0); - - resume_thread(t, false); - - run_scheduler(); // never returns - ASSERT(false); -} - -// ======================= // -// TASK STATE MANIPULATION // -// ======================= // - -void yield() { - if (current_thread == 0) { - // might happen before threading is initialized - // (but should not...) - dbg_printf("Warning: probable deadlock.\n"); - } else { - save_context_and_enter_scheduler(¤t_thread->ctx); - } -} - -void pause() { - bool st = disable_interrupts(); - - current_thread->state = T_STATE_PAUSED; - save_context_and_enter_scheduler(¤t_thread->ctx); - - resume_interrupts(st); -} - -void resume_thread(thread_t *thread, bool run_at_once) { - bool st = disable_interrupts(); - - if (thread->state == T_STATE_PAUSED) { - thread->state = T_STATE_RUNNING; - enqueue_thread(thread, false); - } - if (run_at_once) yield(); - - resume_interrupts(st); -} - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/lib/buffer.c b/kernel/lib/buffer.c deleted file mode 100644 index d2f9644..0000000 --- a/kernel/lib/buffer.c +++ /dev/null @@ -1,167 +0,0 @@ -#include - -#include -#include - -#include - -// three types of buffers -#define T_BYTES 1 -#define T_SLICE 2 -#define T_CONCAT 3 - -struct buffer { - uint16_t rc, type; // takes less space like this - size_t len; - union { - struct { - const char* data; - bool owned; - } bytes; - struct { - struct buffer *buf; - size_t begin; - } slice; - struct { - struct buffer *a, *b; - } concat; - }; -}; - -void buffer_ref(buffer_t *b) { - b->rc++; -} - -void buffer_unref(buffer_t *b) { - b->rc--; - if (b->rc == 0) { - switch (b->type) { - case T_BYTES: - if (b->bytes.owned) kfree((void*)b->bytes.data); - break; - case T_SLICE: - buffer_unref(b->slice.buf); - break; - case T_CONCAT: - buffer_unref(b->concat.a); - buffer_unref(b->concat.b); - break; - default: - ASSERT(false); - } - kfree(b); - } -} - -size_t buffer_size(buffer_t *b) { - return b->len; -} - -size_t read_buffer(buffer_t *b, char* dest, size_t begin, size_t n) { - if (begin >= b->len) return 0; - if (begin + n >= b->len) n = b->len - begin; - - switch (b->type) { - case T_BYTES: - memcpy(dest, b->bytes.data + begin, n); - break; - case T_SLICE: - read_buffer(b->slice.buf, dest, begin + b->slice.begin, n); - break; - case T_CONCAT: { - size_t la = b->concat.a->len; - if (begin < la) { - size_t r = read_buffer(b->concat.a, dest, begin, n); - if (r < n) { - ASSERT(read_buffer(b->concat.b, dest, 0, n - r) == n - r); - } - } else { - ASSERT(read_buffer(b->concat.b, dest, begin - la, n) == n); - } - break; - } - default: - ASSERT(false); - } - - return n; -} - -// ========================= // -// BUFFER CREATION FUNCTIONS // -// ========================= // - -buffer_t *buffer_from_bytes_nocopy(const char* data, size_t n, bool own_bytes) { - buffer_t *b = (buffer_t*)kmalloc(sizeof(buffer_t)); - if (b == 0) return 0; - - b->rc = 1; - b->type = T_BYTES; - b->len = n; - b->bytes.data = data; - b->bytes.owned = own_bytes; - - return b; -} -buffer_t *buffer_from_bytes(const char* data, size_t n) { - char* data2 = (char*)kmalloc(n); - if (data2 == 0) return 0; - - memcpy(data2, data, n); - - buffer_t *b = buffer_from_bytes_nocopy(data2, n, true); - if (b == 0) { - kfree(data2); - return 0; - } - - return b; -} - - -buffer_t* buffer_slice(buffer_t* src, size_t begin, size_t n) { - if (begin + n > src->len) return 0; // invalid request - - buffer_t *b = (buffer_t*)kmalloc(sizeof(buffer_t)); - if (b == 0) return 0; - - b->rc = 1; - b->type = T_SLICE; - b->len = n; - b->slice.buf = src; - b->slice.begin = begin; - - return b; -} - -buffer_t* buffer_concat(buffer_t* a, buffer_t* b) { - buffer_t *r = (buffer_t*)kmalloc(sizeof(buffer_t)); - if (r == 0) return r; - - r->rc = 1; - r->type = T_CONCAT; - r->len = a->len + b->len; - r->concat.a = a; - r->concat.b = b; - - return r; -} - -buffer_t* buffer_slice_k(buffer_t *b, size_t begin, size_t n) { - buffer_t *r = buffer_slice(b, begin, n); - if (r != 0) { - buffer_ref(b); - } - return r; -} - -buffer_t* buffer_concat_k(buffer_t *a, buffer_t *b) { - buffer_t *r = buffer_concat(a, b); - if (r != 0) { - buffer_ref(a); - buffer_ref(b); - } - return r; -} - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/lib/hashtbl.c b/kernel/lib/hashtbl.c deleted file mode 100644 index 91fb3cb..0000000 --- a/kernel/lib/hashtbl.c +++ /dev/null @@ -1,166 +0,0 @@ -#include -#include -#include - -#define DEFAULT_INIT_SIZE 16 -#define SLOT_OF_HASH(k, nslots) (((size_t)(k)*21179)%(size_t)(nslots)) - -typedef struct hashtbl_item { - void* key; - void* val; - struct hashtbl_item *next; -} hashtbl_item_t; - -// When nitems > size * 3/4, size is multiplied by two -// When nitems < size * 1/4, size is divided by two -struct hashtbl { - key_eq_fun_t ef; - hash_fun_t hf; - size_t size, nitems; - hashtbl_item_t **items; -}; - -hashtbl_t *create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, size_t initial_size) { - hashtbl_t *ht = (hashtbl_t*)kmalloc(sizeof(hashtbl_t)); - if (ht == 0) return 0; - - ht->ef = ef; - ht->hf = hf; - - ht->size = (initial_size == 0 ? DEFAULT_INIT_SIZE : initial_size); - ht->nitems = 0; - - ht->items = (hashtbl_item_t**)kmalloc(ht->size * sizeof(hashtbl_item_t*)); - if (ht->items == 0) { - kfree(ht); - return 0; - } - - for (size_t i = 0; i < ht->size; i++) ht->items[i] = 0; - - return ht; -} - -void delete_hashtbl(hashtbl_t *ht) { - // Free items - for (size_t i = 0; i < ht->size; i++) { - while (ht->items[i] != 0) { - hashtbl_item_t *n = ht->items[i]->next; - kfree(ht->items[i]); - ht->items[i] = n; - } - } - - // Free table - kfree(ht->items); - kfree(ht); -} - -static void hashtbl_check_size(hashtbl_t *ht) { - size_t nsize = 0; - if (4 * ht->nitems < ht->size) nsize = ht->size / 2; - if (4 * ht->nitems > 3 * ht->size) nsize = ht->size * 2; - - if (nsize != 0) { - hashtbl_item_t **nitems = (hashtbl_item_t**)kmalloc(nsize * sizeof(hashtbl_item_t*)); - if (nitems == 0) return; // if we can't realloc, too bad, we just lose space - - for (size_t i = 0; i < nsize; i++) nitems[i] = 0; - - // rehash - for (size_t i = 0; i < ht->size; i++) { - while (ht->items[i] != 0) { - hashtbl_item_t *x = ht->items[i]; - ht->items[i] = x->next; - - size_t slot = SLOT_OF_HASH(ht->hf(x->key), nsize); - x->next = nitems[slot]; - nitems[slot] = x; - } - } - kfree(ht->items); - ht->size = nsize; - ht->items = nitems; - } -} - -int hashtbl_add(hashtbl_t *ht, void* key, void* v) { - size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size); - - hashtbl_item_t *i = (hashtbl_item_t*)kmalloc(sizeof(hashtbl_item_t)); - if (i == 0) return 1; // OOM - - // make sure item is not already present - hashtbl_remove(ht, key); - - i->key = key; - i->val = v; - i->next = ht->items[slot]; - ht->items[slot] = i; - ht->nitems++; - - hashtbl_check_size(ht); - - return 0; -} - -void* hashtbl_find(hashtbl_t* ht, void* key) { - size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size); - - for (hashtbl_item_t *i = ht->items[slot]; i != 0; i = i->next) { - if (ht->ef(i->key, key)) return i->val; - } - - return 0; -} - -void hashtbl_remove(hashtbl_t* ht, void* key) { - size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size); - - if (ht->items[slot] == 0) return; - - if (ht->ef(ht->items[slot]->key, key)) { - hashtbl_item_t *x = ht->items[slot]; - ht->items[slot] = x->next; - kfree(x); - ht->nitems--; - } else { - for (hashtbl_item_t *i = ht->items[slot]; i->next != 0; i = i->next) { - if (ht->ef(i->next->key, key)) { - hashtbl_item_t *x = i->next; - i->next = x->next; - kfree(x); - ht->nitems--; - break; - } - } - } - - hashtbl_check_size(ht); -} - -size_t hashtbl_count(hashtbl_t* ht) { - return ht->nitems; -} - -hash_t id_hash_fun(const void* v) { - return (hash_t)v; -} - -hash_t str_hash_fun(const void* v) { - hash_t h = 712; - for (char* s = (char*)v; *s != 0; s++) { - h = h * 101 + *s; - } - return h; -} - -bool id_key_eq_fun(const void* a, const void* b) { - return a == b; -} - -bool str_key_eq_fun(const void* a, const void* b) { - return strcmp((const char*)a, (const char*)b) == 0; -} - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/lib/mutex.c b/kernel/lib/mutex.c deleted file mode 100644 index cda8049..0000000 --- a/kernel/lib/mutex.c +++ /dev/null @@ -1,27 +0,0 @@ -#include - -/* Internal use only. This function is atomic, meaning it cannot be interrupted by a system task switch. */ -static uint32_t atomic_exchange(uint32_t* ptr, uint32_t newval) { - uint32_t r; - asm volatile("xchg (%%ecx), %%eax" : "=a"(r) : "c"(ptr), "a"(newval)); - return r; -} - -void mutex_lock(uint32_t* mutex) { - while (atomic_exchange(mutex, MUTEX_LOCKED) == MUTEX_LOCKED) { - yield(); - } -} - -int mutex_try_lock(uint32_t* mutex) { - if (atomic_exchange(mutex, MUTEX_LOCKED) == MUTEX_LOCKED) { - return 0; - } - return 1; -} - -void mutex_unlock(uint32_t* mutex) { - *mutex = MUTEX_UNLOCKED; -} - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/lib/printf.c b/kernel/lib/printf.c deleted file mode 100644 index 68e08d8..0000000 --- a/kernel/lib/printf.c +++ /dev/null @@ -1,120 +0,0 @@ -#include -#include - -int snprintf(char * buff, size_t len, const char *format, ...) { - va_list ap; - - va_start(ap, format); - len = vsnprintf(buff, len, format, ap); - va_end(ap); - - return len; -} - -int vsnprintf(char *buff, size_t len, const char* format, va_list ap){ - size_t i, result; - - if (!buff || !format) - return -1; - -#define PUTCHAR(thechar) \ - do { \ - if (result < len-1) \ - *buff++ = (thechar); \ - result++; \ - } while (0) - - result = 0; - for(i = 0; format[i] != '\0' ; i++) { - if (format[i] == '%') { - i++; - switch(format[i]) { - case '%': - PUTCHAR('%'); - break; - - case 'i':; - case 'd': { - int integer = va_arg(ap,int); - int cpt2 = 0; - char buff_int[16]; - - if (integer<0) - PUTCHAR('-'); - - do { - int m10 = integer%10; - m10 = (m10 < 0)? -m10:m10; - buff_int[cpt2++] = (char)('0'+ m10); - integer = integer/10; - } while(integer != 0); - - for(cpt2 = cpt2 - 1; cpt2 >= 0; cpt2--) - PUTCHAR(buff_int[cpt2]); - - break; - } - case 'c': { - int value = va_arg(ap,int); - PUTCHAR((char)value); - break; - } - case 's': { - char *string = va_arg(ap,char *); - if (!string) - string = "(null)"; - for(; *string != '\0' ; string++) - PUTCHAR(*string); - break; - } - case 'x': { - unsigned int hexa = va_arg(ap,int); - unsigned int nb; - int j, had_nonzero = 0; - for(j = 0; j < 8; j++) { - nb = (unsigned int)(hexa << (j*4)); - nb = (nb >> 28) & 0xf; - // Skip the leading zeros - if (nb == 0) { - if (had_nonzero) - PUTCHAR('0'); - } else { - had_nonzero = 1; - if (nb < 10) - PUTCHAR('0'+nb); - else - PUTCHAR('a'+(nb-10)); - } - } - if (!had_nonzero) - PUTCHAR('0'); - break; - } - case 'p': { - unsigned int hexa = va_arg(ap,int); - unsigned int nb; - int j; - for (j = 0; j < 8; j++) { - nb = (unsigned int)(hexa << (j*4)); - nb = (nb >> 28) & 0xf; - if (nb < 10) - PUTCHAR('0'+nb); - else - PUTCHAR('a'+(nb-10)); - } - break; - } - default: - PUTCHAR('%'); - PUTCHAR(format[i]); - } - } else { - PUTCHAR(format[i]); - } - } - - *buff = '\0'; - return result; -} - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/lib/slab_alloc.c b/kernel/lib/slab_alloc.c deleted file mode 100644 index 714c49f..0000000 --- a/kernel/lib/slab_alloc.c +++ /dev/null @@ -1,283 +0,0 @@ -#include - -typedef struct object { - struct object *next; -} object_t; - -typedef struct cache { - void* region_addr; - - uint32_t n_free_objs; - object_t* first_free_obj; - - struct cache *next_cache; // next cache in this slab -} cache_t; - -typedef struct region { - void* region_addr; - size_t region_size; - struct region *next_region; - bool contains_descriptors; -} region_t; - -typedef union descriptor { - cache_t c; - region_t r; - union descriptor *next_free; -} descriptor_t; - -typedef struct slab { - cache_t *first_cache; // linked list of caches -} slab_t; - -struct mem_allocator { - const slab_type_t *types; - slab_t *slabs; - - descriptor_t *first_free_descriptor; - region_t *all_regions; - - page_alloc_fun_t alloc_fun; - page_free_fun_t free_fun; -}; - -// ============================================== // -// Helper functions for the manipulation of lists // -// ============================================== // - -static void add_free_descriptor(mem_allocator_t *a, descriptor_t *c) { - c->next_free = a->first_free_descriptor; - a->first_free_descriptor = c; -} - -static descriptor_t *take_descriptor(mem_allocator_t *a) { - if (a->first_free_descriptor == 0) { - void* p = a->alloc_fun(PAGE_SIZE); - if (p == 0) return 0; - - const void* end = p + PAGE_SIZE; - for (descriptor_t *i = (descriptor_t*)p; i + 1 <= (descriptor_t*)end; i++) { - add_free_descriptor(a, i); - } - - // register the descriptor region - descriptor_t *dd = a->first_free_descriptor; - ASSERT(dd != 0); - a->first_free_descriptor = dd->next_free; - - region_t *drd = &dd->r; - drd->region_addr = p; - drd->region_size = PAGE_SIZE; - drd->contains_descriptors = true; - drd->next_region = a->all_regions; - a->all_regions = drd; - } - - descriptor_t *x = a->first_free_descriptor; - ASSERT(x != 0); - a->first_free_descriptor = x->next_free; - return x; -} - -// ============================== // -// The actual allocator functions // -// ============================== // - -mem_allocator_t* create_slab_allocator(const slab_type_t *types, page_alloc_fun_t af, page_free_fun_t ff) { - union { - void* addr; - mem_allocator_t *a; - slab_t *s; - descriptor_t *d; - } ptr; - - ptr.addr = af(PAGE_SIZE); - if (ptr.addr == 0) return 0; // could not allocate - const void* end_addr = ptr.addr + PAGE_SIZE; - - mem_allocator_t *a = ptr.a; - ptr.a++; - - a->all_regions = 0; - a->alloc_fun = af; - a->free_fun = ff; - - a->types = types; - a->slabs = ptr.s; - for (const slab_type_t *t = types; t->obj_size != 0; t++) { - ASSERT(t->obj_size >= sizeof(object_t)); - ptr.s->first_cache = 0; - ptr.s++; - } - - a->first_free_descriptor = 0; - while (ptr.d + 1 <= (descriptor_t*)end_addr) { - add_free_descriptor(a, ptr.d); - ptr.d++; - } - - return a; -} - -static void stack_and_destroy_regions(page_free_fun_t ff, region_t *r) { - if (r == 0) return; - void* addr = r->region_addr; - ASSERT(r != r->next_region); - stack_and_destroy_regions(ff, r->next_region); - ff(addr); -} -void destroy_slab_allocator(mem_allocator_t *a) { - for (int i = 0; a->types[i].obj_size != 0; i++) { - for (cache_t *c = a->slabs[i].first_cache; c != 0; c = c->next_cache) { - a->free_fun(c->region_addr); - } - } - region_t *dr = 0; - region_t *i = a->all_regions; - while (i != 0) { - region_t *r = i; - i = r->next_region; - if (r->contains_descriptors) { - r->next_region = dr; - dr = r; - } else { - a->free_fun(r->region_addr); - } - } - stack_and_destroy_regions(a->free_fun, dr); - a->free_fun(a); -} - -void* slab_alloc(mem_allocator_t* a, size_t sz) { - for (int i = 0; a->types[i].obj_size != 0; i++) { - const size_t obj_size = a->types[i].obj_size; - if (sz <= obj_size) { - // find a cache with free space - cache_t *fc = a->slabs[i].first_cache; - while (fc != 0 && fc->n_free_objs == 0) { - ASSERT(fc->first_free_obj == 0); // make sure n_free == 0 iff no object in the free stack - fc = fc->next_cache; - } - // if none found, try to allocate a new one - if (fc == 0) { - descriptor_t *fcd = take_descriptor(a); - if (fcd == 0) return 0; - - fc = &fcd->c; - ASSERT((descriptor_t*)fc == fcd); - - const size_t cache_size = a->types[i].pages_per_cache * PAGE_SIZE; - fc->region_addr = a->alloc_fun(cache_size); - if (fc->region_addr == 0) { - add_free_descriptor(a, fcd); - return 0; - } - - fc->n_free_objs = 0; - fc->first_free_obj = 0; - for (void* p = fc->region_addr; p + obj_size <= fc->region_addr + cache_size; p += obj_size) { - object_t *x = (object_t*)p; - x->next = fc->first_free_obj; - fc->first_free_obj = x; - fc->n_free_objs++; - } - ASSERT(fc->n_free_objs == cache_size / obj_size); - - fc->next_cache = a->slabs[i].first_cache; - a->slabs[i].first_cache = fc; - } - // allocate on fc - ASSERT(fc != 0 && fc->n_free_objs > 0); - - object_t *x = fc->first_free_obj; - fc->first_free_obj = x->next; - fc->n_free_objs--; - - ASSERT((fc->n_free_objs == 0) == (fc->first_free_obj == 0)); - - // TODO : if fc is full, put it at the end - return x; - } - } - - // otherwise directly allocate using a->alloc_fun - descriptor_t *rd = take_descriptor(a); - if (rd == 0) return 0; - region_t *r = &rd->r; - ASSERT((descriptor_t*)r == rd); - - r->region_addr = a->alloc_fun(sz); - if (r->region_addr == 0) { - add_free_descriptor(a, rd); - return 0; - } else { - r->region_size = sz; - r->contains_descriptors = false; - - r->next_region = a->all_regions; - a->all_regions = r; - - return (void*)r->region_addr; - } -} - -void slab_free(mem_allocator_t* a, void* addr) { - - for (int i = 0; a->types[i].obj_size != 0; i++) { - size_t region_size = PAGE_SIZE * a->types[i].pages_per_cache; - for (cache_t *r = a->slabs[i].first_cache; r != 0; r = r->next_cache) { - if (addr >= r->region_addr && addr < r->region_addr + region_size) { - ASSERT((addr - r->region_addr) % a->types[i].obj_size == 0); - - object_t *o = (object_t*)addr; - o->next = r->first_free_obj; - r->first_free_obj = o; - r->n_free_objs++; - - if (r->n_free_objs == region_size / a->types[i].obj_size) { - // region is completely unused, free it. - if (a->slabs[i].first_cache == r) { - a->slabs[i].first_cache = r->next_cache; - } else { - for (cache_t *it = a->slabs[i].first_cache; it->next_cache != 0; it = it->next_cache) { - if (it->next_cache == r) { - it->next_cache = r->next_cache; - break; - } - } - } - a->free_fun(r->region_addr); - add_free_descriptor(a, (descriptor_t*)r); - } - return; - } - } - } - - // otherwise the block was directly allocated : look for it in regions. - ASSERT(a->all_regions != 0); - - if (a->all_regions->region_addr == addr) { - a->free_fun(addr); // found it, free it - - region_t *r = a->all_regions; - a->all_regions = r->next_region; - add_free_descriptor(a, (descriptor_t*)r); - } else { - for (region_t *i = a->all_regions; i->next_region != 0; i = i->next_region) { - if (i->next_region->region_addr == addr) { - a->free_fun(addr); // found it, free it - - region_t *r = i->next_region; - ASSERT(!r->contains_descriptors); - i->next_region = r->next_region; - add_free_descriptor(a, (descriptor_t*)r); - return; - } - } - ASSERT(false); - } -} - -/* vim: set ts=4 sw=4 tw=0 noet :*/ - diff --git a/kernel/lib/string.c b/kernel/lib/string.c deleted file mode 100644 index 9dce27b..0000000 --- a/kernel/lib/string.c +++ /dev/null @@ -1,90 +0,0 @@ -#include - - -size_t strlen(const char* str) { - size_t ret = 0; - while (str[ret] != 0) - ret++; - return ret; -} - -char *strchr(const char *str, char c) { - while (*str) { - if (*str == c) return (char*)str; - str++; - } - return NULL; -} - -char *strcpy(char *dest, const char *src) { - memcpy(dest, src, strlen(src) + 1); - return (char*)src; -} - -char *strcat(char *dest, const char *src) { - char *dest2 = dest; - dest2 += strlen(dest) - 1; - while (*src) { - *dest2 = *src; - src++; - dest2++; - } - *dest2 = 0; - return dest; -} - -int strcmp(const char *s1, const char *s2) { - while ((*s1) && (*s1 == *s2)) { - s1++; - s2++; - } - return (*(unsigned char*)s1 - *(unsigned char*)s2); -} - -void *memcpy(void *vd, const void *vs, size_t count) { - uint8_t *dest = (uint8_t*)vd, *src = (uint8_t*)vs; - size_t f = count % 4, n = count / 4, i; - const uint32_t* s = (uint32_t*)src; - uint32_t* d = (uint32_t*)dest; - for (i = 0; i < n; i++) { - d[i] = s[i]; - } - if (f != 0) { - for (i = count - f; i < count; i++) { - dest[i] = src[i]; - } - } - return vd; -} - -void *memmove(void *vd, const void *vs, size_t count) { - uint8_t *dest = (uint8_t*)vd, *src = (uint8_t*)vs; - - if (vd < vs) { - for (size_t i = 0; i < count; i++) - dest[i] = src[i]; - } else { - for (size_t i = 0; i < count; i++) - dest[count - i] = src[count - i]; - } - return vd; -} - -int memcmp(const void *va, const void *vb, size_t count) { - uint8_t *a = (uint8_t*)va; - uint8_t *b = (uint8_t*)vb; - for (size_t i = 0; i < count; i++) { - if (a[i] != b[i]) return (int)a[i] - (int)b[i]; - } - return 0; -} - -void *memset(void *dest, int val, size_t count) { - uint8_t *dest_c = (uint8_t*)dest; - for (size_t i = 0; i < count; i++) { - dest_c[i] = val; - } - return dest; -} - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/lib_tests/Makefile b/kernel/lib_tests/Makefile deleted file mode 100644 index 4a21edf..0000000 --- a/kernel/lib_tests/Makefile +++ /dev/null @@ -1,2 +0,0 @@ -slab_test.bin: slab_test.c ../include/slab_alloc.h ../lib/slab_alloc.c - gcc -m32 -o $@ -std=c99 -I ../include slab_test.c ../lib/slab_alloc.c diff --git a/kernel/lib_tests/slab_test.c b/kernel/lib_tests/slab_test.c deleted file mode 100644 index 747c785..0000000 --- a/kernel/lib_tests/slab_test.c +++ /dev/null @@ -1,44 +0,0 @@ -#include -#include -#include - -slab_type_t slab_sizes[] = { - { "8B obj", 8, 1 }, - { "16B obj", 16, 2 }, - { "32B obj", 32, 2 }, - { "64B obj", 64, 2 }, - { "128B obj", 128, 2 }, - { "256B obj", 256, 4 }, - { "512B obj", 512, 4 }, - { "1KB obj", 1024, 8 }, - { "2KB obj", 2048, 8 }, - { "4KB obj", 4096, 16 }, - { 0, 0, 0 } -}; - - -int main(int argc, char *argv[]) { - mem_allocator_t *a = - create_slab_allocator(slab_sizes, malloc, free); - - const int m = 10000; - uint32_t* ptr[m]; - for (int i = 0; i < m; i++) { - size_t s = 1 << ((i * 7) % 12 + 2); - ptr[i] = (uint32_t*)slab_alloc(a, s); - ASSERT(ptr[i] != 0); - *ptr[i] = ((i * 2117) % (1<<30)); - printf("Alloc %i : 0x%p\n", s, ptr[i]); - } - for (int i = 0; i < m; i++) { - for (int j = i; j < m; j++) { - ASSERT(*ptr[j] == (j * 2117) % (1<<30)); - } - slab_free(a, ptr[i]); - } - destroy_slab_allocator(a); - - return 0; -} - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/kernel/linker.ld b/kernel/linker.ld deleted file mode 100644 index 1203950..0000000 --- a/kernel/linker.ld +++ /dev/null @@ -1,43 +0,0 @@ -ENTRY (loader) - -SECTIONS{ - k_highhalf_addr = 0xC0000000; - - . = 0x00100000; - - .setup : { - *(.setup) - } - - . += k_highhalf_addr; - - .text : AT(ADDR(.text) - k_highhalf_addr) { - *(.text) - } - - .rodata ALIGN (0x1000) : AT(ADDR(.rodata) - k_highhalf_addr) { - *(.rodata) - } - - .data ALIGN (0x1000) : AT(ADDR(.data) - k_highhalf_addr) { - start_ctors = .; - *(.ctor*) - end_ctors = .; - start_dtors = .; - *(.dtor*) - end_dtors = .; - *(.data) - *(.locks) - } - - .bss : AT(ADDR(.bss) - k_highhalf_addr) { - sbss = .; - *(COMMON) - *(.bss) - ebss = .; - } - - k_end_addr = .; -} - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/make_cdrom.sh b/make_cdrom.sh index ef9e5f7..82a3bd2 100755 --- a/make_cdrom.sh +++ b/make_cdrom.sh @@ -8,7 +8,7 @@ if [ ! -e cdrom/boot/grub/stage2_eltorito ]; then fi cp menu_cdrom.lst cdrom/boot/grub/menu.lst -cp kernel/kernel.bin cdrom; strip cdrom/kernel.bin +cp src/kernel/kernel.bin cdrom; strip cdrom/kernel.bin genisoimage -R -b boot/grub/stage2_eltorito -no-emul-boot \ -boot-load-size 4 -boot-info-table -input-charset ascii \ diff --git a/run_bochs_debug.sh b/run_bochs_debug.sh index df6c0d4..335b810 100755 --- a/run_bochs_debug.sh +++ b/run_bochs_debug.sh @@ -2,6 +2,7 @@ cd `dirname $0` -make -C kernel || exit 1 +make -C src/common || exit 1 +make -C src/kernel || exit 1 ./make_cdrom.sh bochs -f bochs_debug.cfg -q diff --git a/run_qemu.sh b/run_qemu.sh index 6c76909..59f1f19 100755 --- a/run_qemu.sh +++ b/run_qemu.sh @@ -2,5 +2,6 @@ cd `dirname $0` -make -C kernel || exit 1 -qemu-system-i386 -kernel kernel/kernel.bin -serial stdio -m 16 +make -C src/common || exit 1 +make -C src/kernel || exit 1 +qemu-system-i386 -kernel src/kernel/kernel.bin -serial stdio -m 16 diff --git a/run_qemu_debug.sh b/run_qemu_debug.sh index 71ee6d3..9e84613 100755 --- a/run_qemu_debug.sh +++ b/run_qemu_debug.sh @@ -2,6 +2,7 @@ cd `dirname $0` -make -C kernel || exit 1 -qemu-system-i386 -kernel kernel/kernel.bin -serial stdio -s -S & -(sleep 0.1; gdb kernel/kernel.bin -x gdb_cmd) +make -C src/common || exit 1 +make -C src/kernel || exit 1 +qemu-system-i386 -kernel src/kernel/kernel.bin -serial stdio -s -S & +(sleep 0.1; gdb src/kernel/kernel.bin -x gdb_cmd) diff --git a/src/common/Makefile b/src/common/Makefile new file mode 100644 index 0000000..d27c6d5 --- /dev/null +++ b/src/common/Makefile @@ -0,0 +1,11 @@ +OBJ = string.o printf.o slab_alloc.o mutex.o hashtbl.o buffer.o + +LIB = + +CFLAGS = -I ./include + +LDFLAGS = + +OUT = common.lib + +include ../rules.make diff --git a/src/common/README b/src/common/README new file mode 100644 index 0000000..deae76f --- /dev/null +++ b/src/common/README @@ -0,0 +1,18 @@ +This directory contains the library functions common to userland +and kernel code. + +It relies on a few functions being exported : + +- panic(char* msg, char* file, int line) +- panic_assert(char* assert, char* file, int line) +- dbg_print(const char* str) +- void* malloc(size_t size) +- free(void* ptr) + +These function are supposed to be defined in the code that calls +the common functions. The headers for these functions are to be +found in `assert.h` and `malloc.h`. + +Panic and panic_assert end the execution of the current program +(or of the kernel when in kernel-mode). + diff --git a/src/common/buffer.c b/src/common/buffer.c new file mode 100644 index 0000000..21f1ec4 --- /dev/null +++ b/src/common/buffer.c @@ -0,0 +1,167 @@ +#include + +#include +#include + +#include + +// three types of buffers +#define T_BYTES 1 +#define T_SLICE 2 +#define T_CONCAT 3 + +struct buffer { + uint16_t rc, type; // takes less space like this + size_t len; + union { + struct { + const char* data; + bool owned; + } bytes; + struct { + struct buffer *buf; + size_t begin; + } slice; + struct { + struct buffer *a, *b; + } concat; + }; +}; + +void buffer_ref(buffer_t *b) { + b->rc++; +} + +void buffer_unref(buffer_t *b) { + b->rc--; + if (b->rc == 0) { + switch (b->type) { + case T_BYTES: + if (b->bytes.owned) free((void*)b->bytes.data); + break; + case T_SLICE: + buffer_unref(b->slice.buf); + break; + case T_CONCAT: + buffer_unref(b->concat.a); + buffer_unref(b->concat.b); + break; + default: + ASSERT(false); + } + free(b); + } +} + +size_t buffer_size(buffer_t *b) { + return b->len; +} + +size_t read_buffer(buffer_t *b, char* dest, size_t begin, size_t n) { + if (begin >= b->len) return 0; + if (begin + n >= b->len) n = b->len - begin; + + switch (b->type) { + case T_BYTES: + memcpy(dest, b->bytes.data + begin, n); + break; + case T_SLICE: + read_buffer(b->slice.buf, dest, begin + b->slice.begin, n); + break; + case T_CONCAT: { + size_t la = b->concat.a->len; + if (begin < la) { + size_t r = read_buffer(b->concat.a, dest, begin, n); + if (r < n) { + ASSERT(read_buffer(b->concat.b, dest, 0, n - r) == n - r); + } + } else { + ASSERT(read_buffer(b->concat.b, dest, begin - la, n) == n); + } + break; + } + default: + ASSERT(false); + } + + return n; +} + +// ========================= // +// BUFFER CREATION FUNCTIONS // +// ========================= // + +buffer_t *buffer_from_bytes_nocopy(const char* data, size_t n, bool own_bytes) { + buffer_t *b = (buffer_t*)malloc(sizeof(buffer_t)); + if (b == 0) return 0; + + b->rc = 1; + b->type = T_BYTES; + b->len = n; + b->bytes.data = data; + b->bytes.owned = own_bytes; + + return b; +} +buffer_t *buffer_from_bytes(const char* data, size_t n) { + char* data2 = (char*)malloc(n); + if (data2 == 0) return 0; + + memcpy(data2, data, n); + + buffer_t *b = buffer_from_bytes_nocopy(data2, n, true); + if (b == 0) { + free(data2); + return 0; + } + + return b; +} + + +buffer_t* buffer_slice(buffer_t* src, size_t begin, size_t n) { + if (begin + n > src->len) return 0; // invalid request + + buffer_t *b = (buffer_t*)malloc(sizeof(buffer_t)); + if (b == 0) return 0; + + b->rc = 1; + b->type = T_SLICE; + b->len = n; + b->slice.buf = src; + b->slice.begin = begin; + + return b; +} + +buffer_t* buffer_concat(buffer_t* a, buffer_t* b) { + buffer_t *r = (buffer_t*)malloc(sizeof(buffer_t)); + if (r == 0) return r; + + r->rc = 1; + r->type = T_CONCAT; + r->len = a->len + b->len; + r->concat.a = a; + r->concat.b = b; + + return r; +} + +buffer_t* buffer_slice_k(buffer_t *b, size_t begin, size_t n) { + buffer_t *r = buffer_slice(b, begin, n); + if (r != 0) { + buffer_ref(b); + } + return r; +} + +buffer_t* buffer_concat_k(buffer_t *a, buffer_t *b) { + buffer_t *r = buffer_concat(a, b); + if (r != 0) { + buffer_ref(a); + buffer_ref(b); + } + return r; +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/common.lib b/src/common/common.lib new file mode 100644 index 0000000..16259e6 Binary files /dev/null and b/src/common/common.lib differ diff --git a/src/common/hashtbl.c b/src/common/hashtbl.c new file mode 100644 index 0000000..47072b4 --- /dev/null +++ b/src/common/hashtbl.c @@ -0,0 +1,166 @@ +#include +#include +#include + +#define DEFAULT_INIT_SIZE 16 +#define SLOT_OF_HASH(k, nslots) (((size_t)(k)*21179)%(size_t)(nslots)) + +typedef struct hashtbl_item { + void* key; + void* val; + struct hashtbl_item *next; +} hashtbl_item_t; + +// When nitems > size * 3/4, size is multiplied by two +// When nitems < size * 1/4, size is divided by two +struct hashtbl { + key_eq_fun_t ef; + hash_fun_t hf; + size_t size, nitems; + hashtbl_item_t **items; +}; + +hashtbl_t *create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, size_t initial_size) { + hashtbl_t *ht = (hashtbl_t*)malloc(sizeof(hashtbl_t)); + if (ht == 0) return 0; + + ht->ef = ef; + ht->hf = hf; + + ht->size = (initial_size == 0 ? DEFAULT_INIT_SIZE : initial_size); + ht->nitems = 0; + + ht->items = (hashtbl_item_t**)malloc(ht->size * sizeof(hashtbl_item_t*)); + if (ht->items == 0) { + free(ht); + return 0; + } + + for (size_t i = 0; i < ht->size; i++) ht->items[i] = 0; + + return ht; +} + +void delete_hashtbl(hashtbl_t *ht) { + // Free items + for (size_t i = 0; i < ht->size; i++) { + while (ht->items[i] != 0) { + hashtbl_item_t *n = ht->items[i]->next; + free(ht->items[i]); + ht->items[i] = n; + } + } + + // Free table + free(ht->items); + free(ht); +} + +static void hashtbl_check_size(hashtbl_t *ht) { + size_t nsize = 0; + if (4 * ht->nitems < ht->size) nsize = ht->size / 2; + if (4 * ht->nitems > 3 * ht->size) nsize = ht->size * 2; + + if (nsize != 0) { + hashtbl_item_t **nitems = (hashtbl_item_t**)malloc(nsize * sizeof(hashtbl_item_t*)); + if (nitems == 0) return; // if we can't realloc, too bad, we just lose space + + for (size_t i = 0; i < nsize; i++) nitems[i] = 0; + + // rehash + for (size_t i = 0; i < ht->size; i++) { + while (ht->items[i] != 0) { + hashtbl_item_t *x = ht->items[i]; + ht->items[i] = x->next; + + size_t slot = SLOT_OF_HASH(ht->hf(x->key), nsize); + x->next = nitems[slot]; + nitems[slot] = x; + } + } + free(ht->items); + ht->size = nsize; + ht->items = nitems; + } +} + +int hashtbl_add(hashtbl_t *ht, void* key, void* v) { + size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size); + + hashtbl_item_t *i = (hashtbl_item_t*)malloc(sizeof(hashtbl_item_t)); + if (i == 0) return 1; // OOM + + // make sure item is not already present + hashtbl_remove(ht, key); + + i->key = key; + i->val = v; + i->next = ht->items[slot]; + ht->items[slot] = i; + ht->nitems++; + + hashtbl_check_size(ht); + + return 0; +} + +void* hashtbl_find(hashtbl_t* ht, void* key) { + size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size); + + for (hashtbl_item_t *i = ht->items[slot]; i != 0; i = i->next) { + if (ht->ef(i->key, key)) return i->val; + } + + return 0; +} + +void hashtbl_remove(hashtbl_t* ht, void* key) { + size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size); + + if (ht->items[slot] == 0) return; + + if (ht->ef(ht->items[slot]->key, key)) { + hashtbl_item_t *x = ht->items[slot]; + ht->items[slot] = x->next; + free(x); + ht->nitems--; + } else { + for (hashtbl_item_t *i = ht->items[slot]; i->next != 0; i = i->next) { + if (ht->ef(i->next->key, key)) { + hashtbl_item_t *x = i->next; + i->next = x->next; + free(x); + ht->nitems--; + break; + } + } + } + + hashtbl_check_size(ht); +} + +size_t hashtbl_count(hashtbl_t* ht) { + return ht->nitems; +} + +hash_t id_hash_fun(const void* v) { + return (hash_t)v; +} + +hash_t str_hash_fun(const void* v) { + hash_t h = 712; + for (char* s = (char*)v; *s != 0; s++) { + h = h * 101 + *s; + } + return h; +} + +bool id_key_eq_fun(const void* a, const void* b) { + return a == b; +} + +bool str_key_eq_fun(const void* a, const void* b) { + return strcmp((const char*)a, (const char*)b) == 0; +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/buffer.h b/src/common/include/buffer.h new file mode 100644 index 0000000..0d6cfbf --- /dev/null +++ b/src/common/include/buffer.h @@ -0,0 +1,41 @@ +#pragma once + +#include +#include +#include + +// The buffer_t type is a simple reference-counted buffer type +// enabling the creation, sharing, slicing and concatenation of buffers +// without having to copy everything each time + +// Buffers are always allocated on the core kernel heap (kmalloc/kfree) + +// Once a buffer is allocated, its contents is immutable + +// Encoding and decoding functions for buffer contents are provided in +// a separate file (encode.h) + +struct buffer; +typedef struct buffer buffer_t; + +void buffer_ref(buffer_t*); // increase reference counter +void buffer_unref(buffer_t*); // decrease reference counter + +size_t buffer_len(buffer_t* buf); +size_t read_buffer(buffer_t* buf, char* to, size_t begin, size_t n); // returns num of bytes read + +buffer_t* buffer_from_bytes(const char* data, size_t n); // bytes are COPIED +buffer_t* buffer_from_bytes_nocopy(const char* data, size_t n, bool own_bytes); // bytes are NOT COPIED + +// these functions GIVE the buffer in order to create the new buffer, ie they do not increase RC +// the buffer is NOT GIVED if the new buffer could not be created (ie retval == 0) +buffer_t* buffer_slice(buffer_t* b, size_t begin, size_t n); +buffer_t* buffer_concat(buffer_t* a, buffer_t* b); + +// these functions KEEP a reference on the buffer (ie RC is incremented) +// the RC is NOT INCREMENTED if the new buffer cannot be created +buffer_t* buffer_slice_k(buffer_t* b, size_t begin, size_t n); +buffer_t* buffer_concat_k(buffer_t* a, buffer_t* b); + + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/debug.h b/src/common/include/debug.h new file mode 100644 index 0000000..a4b8b6f --- /dev/null +++ b/src/common/include/debug.h @@ -0,0 +1,14 @@ +#pragma once + +#include +#include + +void panic(const char* message, const char* file, int line); +void panic_assert(const char* assertion, const char* file, int line); +#define PANIC(s) panic(s, __FILE__, __LINE__); +#define ASSERT(s) { if (!(s)) panic_assert(#s, __FILE__, __LINE__); } + +void dbg_print(const char* str); +void dbg_printf(const char* format, ...); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/hashtbl.h b/src/common/include/hashtbl.h new file mode 100644 index 0000000..16dfefb --- /dev/null +++ b/src/common/include/hashtbl.h @@ -0,0 +1,34 @@ +#pragma once + +#include +#include +#include + +// Simple hashtable structure (key -> void*) +// Supports adding, seeking, removing +// When adding a binding to the table, the previous binding for same key (if exists) is removed + +// TODO : possibility to allocate the hashtbl structure on any heap +// (currently uses kmalloc/kfree) + +struct hashtbl; +typedef struct hashtbl hashtbl_t; + +typedef size_t hash_t; +typedef hash_t (*hash_fun_t)(const void*); +typedef bool (*key_eq_fun_t)(const void*, const void*); + +hashtbl_t* create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, size_t initial_size); // 0 -> default size +void delete_hashtbl(hashtbl_t* ht); + +int hashtbl_add(hashtbl_t* ht, void* key, void* v); // non-null on error (OOM for instance) +void* hashtbl_find(hashtbl_t* ht, void* key); // null when not found +void hashtbl_remove(hashtbl_t* ht, void* key); +size_t hashtbl_count(hashtbl_t* ht); + +hash_t id_hash_fun(const void* v); +hash_t str_hash_fun(const void* v); +bool id_key_eq_fun(const void* a, const void* b); +bool str_key_eq_fun(const void* a, const void* b); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/malloc.h b/src/common/include/malloc.h new file mode 100644 index 0000000..0ba5572 --- /dev/null +++ b/src/common/include/malloc.h @@ -0,0 +1,11 @@ +#pragma once + +#include +#include + +// Header is in common/, but implementation is not. + +void* malloc(size_t sz); +void free(void* ptr); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/mutex.h b/src/common/include/mutex.h new file mode 100644 index 0000000..6814adf --- /dev/null +++ b/src/common/include/mutex.h @@ -0,0 +1,21 @@ +#pragma once + +#include + +#define MUTEX_LOCKED 1 +#define MUTEX_UNLOCKED 0 + + +typedef uint32_t mutex_t; + +void mutex_lock(mutex_t* mutex); //wait for mutex to be free +int mutex_try_lock(mutex_t* mutex); //lock mutex only if free, returns !0 if locked, 0 if was busy +void mutex_unlock(mutex_t* mutex); + +// the mutex code assumes a yield() function is defined somewhere +void yield(); + +#define STATIC_MUTEX(name) static mutex_t name __attribute__((section("locks"))) = MUTEX_UNLOCKED; + + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/printf.h b/src/common/include/printf.h new file mode 100644 index 0000000..b4e1c1b --- /dev/null +++ b/src/common/include/printf.h @@ -0,0 +1,10 @@ +#pragma once + +#include +#include +#include + +int snprintf(char* s, size_t n, const char* format, ...); +int vsnprintf(char* s, size_t n, const char* format, va_list arg); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/slab_alloc.h b/src/common/include/slab_alloc.h new file mode 100644 index 0000000..c8d5d6c --- /dev/null +++ b/src/common/include/slab_alloc.h @@ -0,0 +1,45 @@ +#pragma once + +// Self-contained piece of library : a slab allocator... +// Depends on page_alloc_fun_t and page_free_fun_t : a couple of functions +// that can allocate/free multiples of one page at a time + +#include +#include +#include + + +#if defined(__linux__) +//redefine necessary stuff +#include // standard linux assert.h +#define ASSERT assert +#include +#define dbg_printf printf +#else +#include +#endif + +#define PAGE_SIZE 0x1000 + +// expected format for the array of slab_type_t given to slab_create : +// an array of slab_type descriptors, with last descriptor full of zeroes +// and with obj_size increasing (strictly) in the array +typedef struct slab_type { + const char *descr; + size_t obj_size; + size_t pages_per_cache; +} slab_type_t; + +struct mem_allocator; +typedef struct mem_allocator mem_allocator_t; + +typedef void* (*page_alloc_fun_t)(size_t bytes); +typedef void (*page_free_fun_t)(void* ptr); + +mem_allocator_t* create_slab_allocator(const slab_type_t *types, page_alloc_fun_t af, page_free_fun_t ff); +void destroy_slab_allocator(mem_allocator_t*); + +void* slab_alloc(mem_allocator_t* a, size_t sz); +void slab_free(mem_allocator_t* a, void* ptr); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/string.h b/src/common/include/string.h new file mode 100644 index 0000000..682b25a --- /dev/null +++ b/src/common/include/string.h @@ -0,0 +1,17 @@ +#pragma once + +#include +#include + +void *memcpy(void *dest, const void *src, size_t count); +void *memset(void *dest, int val, size_t count); +int memcmp(const void *s1, const void *s2, size_t n); +void *memmove(void *dest, const void *src, size_t count); + +size_t strlen(const char *str); +char *strchr(const char *str, char c); +char *strcpy(char *dest, const char *src); +char *strcat(char *dest, const char *src); +int strcmp(const char *s1, const char *s2); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/mutex.c b/src/common/mutex.c new file mode 100644 index 0000000..cda8049 --- /dev/null +++ b/src/common/mutex.c @@ -0,0 +1,27 @@ +#include + +/* Internal use only. This function is atomic, meaning it cannot be interrupted by a system task switch. */ +static uint32_t atomic_exchange(uint32_t* ptr, uint32_t newval) { + uint32_t r; + asm volatile("xchg (%%ecx), %%eax" : "=a"(r) : "c"(ptr), "a"(newval)); + return r; +} + +void mutex_lock(uint32_t* mutex) { + while (atomic_exchange(mutex, MUTEX_LOCKED) == MUTEX_LOCKED) { + yield(); + } +} + +int mutex_try_lock(uint32_t* mutex) { + if (atomic_exchange(mutex, MUTEX_LOCKED) == MUTEX_LOCKED) { + return 0; + } + return 1; +} + +void mutex_unlock(uint32_t* mutex) { + *mutex = MUTEX_UNLOCKED; +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/printf.c b/src/common/printf.c new file mode 100644 index 0000000..68e08d8 --- /dev/null +++ b/src/common/printf.c @@ -0,0 +1,120 @@ +#include +#include + +int snprintf(char * buff, size_t len, const char *format, ...) { + va_list ap; + + va_start(ap, format); + len = vsnprintf(buff, len, format, ap); + va_end(ap); + + return len; +} + +int vsnprintf(char *buff, size_t len, const char* format, va_list ap){ + size_t i, result; + + if (!buff || !format) + return -1; + +#define PUTCHAR(thechar) \ + do { \ + if (result < len-1) \ + *buff++ = (thechar); \ + result++; \ + } while (0) + + result = 0; + for(i = 0; format[i] != '\0' ; i++) { + if (format[i] == '%') { + i++; + switch(format[i]) { + case '%': + PUTCHAR('%'); + break; + + case 'i':; + case 'd': { + int integer = va_arg(ap,int); + int cpt2 = 0; + char buff_int[16]; + + if (integer<0) + PUTCHAR('-'); + + do { + int m10 = integer%10; + m10 = (m10 < 0)? -m10:m10; + buff_int[cpt2++] = (char)('0'+ m10); + integer = integer/10; + } while(integer != 0); + + for(cpt2 = cpt2 - 1; cpt2 >= 0; cpt2--) + PUTCHAR(buff_int[cpt2]); + + break; + } + case 'c': { + int value = va_arg(ap,int); + PUTCHAR((char)value); + break; + } + case 's': { + char *string = va_arg(ap,char *); + if (!string) + string = "(null)"; + for(; *string != '\0' ; string++) + PUTCHAR(*string); + break; + } + case 'x': { + unsigned int hexa = va_arg(ap,int); + unsigned int nb; + int j, had_nonzero = 0; + for(j = 0; j < 8; j++) { + nb = (unsigned int)(hexa << (j*4)); + nb = (nb >> 28) & 0xf; + // Skip the leading zeros + if (nb == 0) { + if (had_nonzero) + PUTCHAR('0'); + } else { + had_nonzero = 1; + if (nb < 10) + PUTCHAR('0'+nb); + else + PUTCHAR('a'+(nb-10)); + } + } + if (!had_nonzero) + PUTCHAR('0'); + break; + } + case 'p': { + unsigned int hexa = va_arg(ap,int); + unsigned int nb; + int j; + for (j = 0; j < 8; j++) { + nb = (unsigned int)(hexa << (j*4)); + nb = (nb >> 28) & 0xf; + if (nb < 10) + PUTCHAR('0'+nb); + else + PUTCHAR('a'+(nb-10)); + } + break; + } + default: + PUTCHAR('%'); + PUTCHAR(format[i]); + } + } else { + PUTCHAR(format[i]); + } + } + + *buff = '\0'; + return result; +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/slab_alloc.c b/src/common/slab_alloc.c new file mode 100644 index 0000000..714c49f --- /dev/null +++ b/src/common/slab_alloc.c @@ -0,0 +1,283 @@ +#include + +typedef struct object { + struct object *next; +} object_t; + +typedef struct cache { + void* region_addr; + + uint32_t n_free_objs; + object_t* first_free_obj; + + struct cache *next_cache; // next cache in this slab +} cache_t; + +typedef struct region { + void* region_addr; + size_t region_size; + struct region *next_region; + bool contains_descriptors; +} region_t; + +typedef union descriptor { + cache_t c; + region_t r; + union descriptor *next_free; +} descriptor_t; + +typedef struct slab { + cache_t *first_cache; // linked list of caches +} slab_t; + +struct mem_allocator { + const slab_type_t *types; + slab_t *slabs; + + descriptor_t *first_free_descriptor; + region_t *all_regions; + + page_alloc_fun_t alloc_fun; + page_free_fun_t free_fun; +}; + +// ============================================== // +// Helper functions for the manipulation of lists // +// ============================================== // + +static void add_free_descriptor(mem_allocator_t *a, descriptor_t *c) { + c->next_free = a->first_free_descriptor; + a->first_free_descriptor = c; +} + +static descriptor_t *take_descriptor(mem_allocator_t *a) { + if (a->first_free_descriptor == 0) { + void* p = a->alloc_fun(PAGE_SIZE); + if (p == 0) return 0; + + const void* end = p + PAGE_SIZE; + for (descriptor_t *i = (descriptor_t*)p; i + 1 <= (descriptor_t*)end; i++) { + add_free_descriptor(a, i); + } + + // register the descriptor region + descriptor_t *dd = a->first_free_descriptor; + ASSERT(dd != 0); + a->first_free_descriptor = dd->next_free; + + region_t *drd = &dd->r; + drd->region_addr = p; + drd->region_size = PAGE_SIZE; + drd->contains_descriptors = true; + drd->next_region = a->all_regions; + a->all_regions = drd; + } + + descriptor_t *x = a->first_free_descriptor; + ASSERT(x != 0); + a->first_free_descriptor = x->next_free; + return x; +} + +// ============================== // +// The actual allocator functions // +// ============================== // + +mem_allocator_t* create_slab_allocator(const slab_type_t *types, page_alloc_fun_t af, page_free_fun_t ff) { + union { + void* addr; + mem_allocator_t *a; + slab_t *s; + descriptor_t *d; + } ptr; + + ptr.addr = af(PAGE_SIZE); + if (ptr.addr == 0) return 0; // could not allocate + const void* end_addr = ptr.addr + PAGE_SIZE; + + mem_allocator_t *a = ptr.a; + ptr.a++; + + a->all_regions = 0; + a->alloc_fun = af; + a->free_fun = ff; + + a->types = types; + a->slabs = ptr.s; + for (const slab_type_t *t = types; t->obj_size != 0; t++) { + ASSERT(t->obj_size >= sizeof(object_t)); + ptr.s->first_cache = 0; + ptr.s++; + } + + a->first_free_descriptor = 0; + while (ptr.d + 1 <= (descriptor_t*)end_addr) { + add_free_descriptor(a, ptr.d); + ptr.d++; + } + + return a; +} + +static void stack_and_destroy_regions(page_free_fun_t ff, region_t *r) { + if (r == 0) return; + void* addr = r->region_addr; + ASSERT(r != r->next_region); + stack_and_destroy_regions(ff, r->next_region); + ff(addr); +} +void destroy_slab_allocator(mem_allocator_t *a) { + for (int i = 0; a->types[i].obj_size != 0; i++) { + for (cache_t *c = a->slabs[i].first_cache; c != 0; c = c->next_cache) { + a->free_fun(c->region_addr); + } + } + region_t *dr = 0; + region_t *i = a->all_regions; + while (i != 0) { + region_t *r = i; + i = r->next_region; + if (r->contains_descriptors) { + r->next_region = dr; + dr = r; + } else { + a->free_fun(r->region_addr); + } + } + stack_and_destroy_regions(a->free_fun, dr); + a->free_fun(a); +} + +void* slab_alloc(mem_allocator_t* a, size_t sz) { + for (int i = 0; a->types[i].obj_size != 0; i++) { + const size_t obj_size = a->types[i].obj_size; + if (sz <= obj_size) { + // find a cache with free space + cache_t *fc = a->slabs[i].first_cache; + while (fc != 0 && fc->n_free_objs == 0) { + ASSERT(fc->first_free_obj == 0); // make sure n_free == 0 iff no object in the free stack + fc = fc->next_cache; + } + // if none found, try to allocate a new one + if (fc == 0) { + descriptor_t *fcd = take_descriptor(a); + if (fcd == 0) return 0; + + fc = &fcd->c; + ASSERT((descriptor_t*)fc == fcd); + + const size_t cache_size = a->types[i].pages_per_cache * PAGE_SIZE; + fc->region_addr = a->alloc_fun(cache_size); + if (fc->region_addr == 0) { + add_free_descriptor(a, fcd); + return 0; + } + + fc->n_free_objs = 0; + fc->first_free_obj = 0; + for (void* p = fc->region_addr; p + obj_size <= fc->region_addr + cache_size; p += obj_size) { + object_t *x = (object_t*)p; + x->next = fc->first_free_obj; + fc->first_free_obj = x; + fc->n_free_objs++; + } + ASSERT(fc->n_free_objs == cache_size / obj_size); + + fc->next_cache = a->slabs[i].first_cache; + a->slabs[i].first_cache = fc; + } + // allocate on fc + ASSERT(fc != 0 && fc->n_free_objs > 0); + + object_t *x = fc->first_free_obj; + fc->first_free_obj = x->next; + fc->n_free_objs--; + + ASSERT((fc->n_free_objs == 0) == (fc->first_free_obj == 0)); + + // TODO : if fc is full, put it at the end + return x; + } + } + + // otherwise directly allocate using a->alloc_fun + descriptor_t *rd = take_descriptor(a); + if (rd == 0) return 0; + region_t *r = &rd->r; + ASSERT((descriptor_t*)r == rd); + + r->region_addr = a->alloc_fun(sz); + if (r->region_addr == 0) { + add_free_descriptor(a, rd); + return 0; + } else { + r->region_size = sz; + r->contains_descriptors = false; + + r->next_region = a->all_regions; + a->all_regions = r; + + return (void*)r->region_addr; + } +} + +void slab_free(mem_allocator_t* a, void* addr) { + + for (int i = 0; a->types[i].obj_size != 0; i++) { + size_t region_size = PAGE_SIZE * a->types[i].pages_per_cache; + for (cache_t *r = a->slabs[i].first_cache; r != 0; r = r->next_cache) { + if (addr >= r->region_addr && addr < r->region_addr + region_size) { + ASSERT((addr - r->region_addr) % a->types[i].obj_size == 0); + + object_t *o = (object_t*)addr; + o->next = r->first_free_obj; + r->first_free_obj = o; + r->n_free_objs++; + + if (r->n_free_objs == region_size / a->types[i].obj_size) { + // region is completely unused, free it. + if (a->slabs[i].first_cache == r) { + a->slabs[i].first_cache = r->next_cache; + } else { + for (cache_t *it = a->slabs[i].first_cache; it->next_cache != 0; it = it->next_cache) { + if (it->next_cache == r) { + it->next_cache = r->next_cache; + break; + } + } + } + a->free_fun(r->region_addr); + add_free_descriptor(a, (descriptor_t*)r); + } + return; + } + } + } + + // otherwise the block was directly allocated : look for it in regions. + ASSERT(a->all_regions != 0); + + if (a->all_regions->region_addr == addr) { + a->free_fun(addr); // found it, free it + + region_t *r = a->all_regions; + a->all_regions = r->next_region; + add_free_descriptor(a, (descriptor_t*)r); + } else { + for (region_t *i = a->all_regions; i->next_region != 0; i = i->next_region) { + if (i->next_region->region_addr == addr) { + a->free_fun(addr); // found it, free it + + region_t *r = i->next_region; + ASSERT(!r->contains_descriptors); + i->next_region = r->next_region; + add_free_descriptor(a, (descriptor_t*)r); + return; + } + } + ASSERT(false); + } +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ + diff --git a/src/common/string.c b/src/common/string.c new file mode 100644 index 0000000..9dce27b --- /dev/null +++ b/src/common/string.c @@ -0,0 +1,90 @@ +#include + + +size_t strlen(const char* str) { + size_t ret = 0; + while (str[ret] != 0) + ret++; + return ret; +} + +char *strchr(const char *str, char c) { + while (*str) { + if (*str == c) return (char*)str; + str++; + } + return NULL; +} + +char *strcpy(char *dest, const char *src) { + memcpy(dest, src, strlen(src) + 1); + return (char*)src; +} + +char *strcat(char *dest, const char *src) { + char *dest2 = dest; + dest2 += strlen(dest) - 1; + while (*src) { + *dest2 = *src; + src++; + dest2++; + } + *dest2 = 0; + return dest; +} + +int strcmp(const char *s1, const char *s2) { + while ((*s1) && (*s1 == *s2)) { + s1++; + s2++; + } + return (*(unsigned char*)s1 - *(unsigned char*)s2); +} + +void *memcpy(void *vd, const void *vs, size_t count) { + uint8_t *dest = (uint8_t*)vd, *src = (uint8_t*)vs; + size_t f = count % 4, n = count / 4, i; + const uint32_t* s = (uint32_t*)src; + uint32_t* d = (uint32_t*)dest; + for (i = 0; i < n; i++) { + d[i] = s[i]; + } + if (f != 0) { + for (i = count - f; i < count; i++) { + dest[i] = src[i]; + } + } + return vd; +} + +void *memmove(void *vd, const void *vs, size_t count) { + uint8_t *dest = (uint8_t*)vd, *src = (uint8_t*)vs; + + if (vd < vs) { + for (size_t i = 0; i < count; i++) + dest[i] = src[i]; + } else { + for (size_t i = 0; i < count; i++) + dest[count - i] = src[count - i]; + } + return vd; +} + +int memcmp(const void *va, const void *vb, size_t count) { + uint8_t *a = (uint8_t*)va; + uint8_t *b = (uint8_t*)vb; + for (size_t i = 0; i < count; i++) { + if (a[i] != b[i]) return (int)a[i] - (int)b[i]; + } + return 0; +} + +void *memset(void *dest, int val, size_t count) { + uint8_t *dest_c = (uint8_t*)dest; + for (size_t i = 0; i < count; i++) { + dest_c[i] = val; + } + return dest; +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/Makefile b/src/kernel/Makefile new file mode 100644 index 0000000..3fc7e9c --- /dev/null +++ b/src/kernel/Makefile @@ -0,0 +1,14 @@ + +OBJ = core/loader.o core/kmain.o core/dbglog.o core/sys.o \ + core/gdt.o core/idt.o core/interrupt.o core/context_switch.o core/thread.o \ + core/frame.o core/paging.o core/region.o core/kmalloc.o + +LIB = ../common/common.lib + +CFLAGS = -I ./include -I ../common/include + +LDFLAGS = -T linker.ld -Xlinker -Map=kernel.map + +OUT = kernel.bin + +include ../rules.make diff --git a/src/kernel/config.h b/src/kernel/config.h new file mode 100644 index 0000000..a0e59d3 --- /dev/null +++ b/src/kernel/config.h @@ -0,0 +1,27 @@ +#if !defined(__cplusplus) +#include +#endif + +#include +#include + +#if defined(__linux__) +#error "This kernel needs to be compiled with a cross-compiler." +#endif + +#if !defined(__i386__) +#error "This kernel needs to be compiled with a ix86-elf compiler" +#endif + +#define IN_KERNEL + +#define K_HIGHHALF_ADDR ((size_t)0xC0000000) + +#define OS_NAME "macrO.Scope" +#define OS_VERSION "0.0.1" + +// Comment to disable either form of debug log output +#define DBGLOG_TO_SERIAL +#define DBGLOG_TO_SCREEN + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/core/context_switch.s b/src/kernel/core/context_switch.s new file mode 100644 index 0000000..6738a03 --- /dev/null +++ b/src/kernel/core/context_switch.s @@ -0,0 +1,58 @@ +[EXTERN kernel_stack_top] +[EXTERN run_scheduler] + +[GLOBAL save_context_and_enter_scheduler] +; void save_context_and_enter_scheduler(struct saved_context *ctx); +save_context_and_enter_scheduler: + pushf + cli + pusha ; Pushes edi,esi,ebp,esp,ebx,edx,ecx,eax + + mov eax, cr3 + push eax + + mov eax, [esp+44] ; get address of saved_context structure + mov [eax], esp ; save esp + mov dword [eax+4], resume_saved_context ; save eip + + mov esp, kernel_stack_top + jmp run_scheduler + +resume_saved_context: + pop eax + mov cr3, eax + + popa + popf + ret + +[GLOBAL irq0_save_context_and_enter_scheduler] +; meant to be called on IRQ0 +; general registers already saved by IRQ handler stub +; flags already saved by interruption and interruptions disabled +; only saves CR3 +irq0_save_context_and_enter_scheduler: + mov eax, cr3 + push eax + + mov eax, [esp+8] ; get address of saved_context structure + mov [eax], esp ; save esp + mov dword [eax+4], resume_saved_irq0_context ; save eip + + mov esp, kernel_stack_top + jmp run_scheduler + +resume_saved_irq0_context: + pop eax + mov cr3, eax + ret + + +[GLOBAL resume_context] +resume_context: + mov eax, [esp+4] ; get address of saved context + mov esp, [eax] ; resume esp + mov ecx, [eax+4] ; jump to specified eip + jmp ecx + +; vim: set ts=4 sw=4 tw=0 noet : diff --git a/src/kernel/core/dbglog.c b/src/kernel/core/dbglog.c new file mode 100644 index 0000000..e042625 --- /dev/null +++ b/src/kernel/core/dbglog.c @@ -0,0 +1,159 @@ +#include +#include +#include +#include + +#include +#include +#include + +// ================================================================== + +#ifdef DBGLOG_TO_SCREEN + +static const size_t VGA_WIDTH = 80; +static const size_t VGA_HEIGHT = 25; + +static uint8_t vga_color = 7; +static uint16_t* vga_buffer = 0; +static uint16_t vga_row = 0, vga_column = 0; + +static uint16_t make_vgaentry(char c, uint8_t color) { + uint16_t c16 = c; + uint16_t color16 = color; + return c16 | color16 << 8; +} + +static void vga_putentryat(char c, uint8_t color, size_t x, size_t y) { + const size_t index = y * VGA_WIDTH + x; + vga_buffer[index] = make_vgaentry(c, color); +} + +static void vga_update_cursor() { + uint16_t cursor_location = vga_row * 80 + vga_column; + outb(0x3D4, 14); //Sending high cursor byte + outb(0x3D5, cursor_location >> 8); + outb(0x3D4, 15); //Sending high cursor byte + outb(0x3D5, cursor_location); +} + +static void vga_init() { + vga_row = 0; + vga_column = 0; + vga_buffer = (uint16_t*) (K_HIGHHALF_ADDR + 0xB8000); + + for (size_t y = 0; y < VGA_HEIGHT; y++) { + for (size_t x = 0; x < VGA_WIDTH; x++) { + vga_putentryat(' ', vga_color, x, y); + } + } + + vga_update_cursor(); +} + +static void vga_scroll() { + for (size_t i = 0; i < VGA_WIDTH * (VGA_HEIGHT - 1); i++) { + vga_buffer[i] = vga_buffer[i + VGA_WIDTH]; + } + for (size_t x = 0; x < VGA_WIDTH; x++) { + vga_putentryat(' ', vga_color, x, VGA_HEIGHT - 1); + } + vga_row--; +} + +static void vga_newline() { + vga_column = 0; + if (++vga_row == VGA_HEIGHT) { + vga_scroll(); + } +} + +static void vga_putc(char c) { + if (c == '\n') { + vga_newline(); + } else if (c == '\t') { + vga_putc(' '); + while (vga_column % 4 != 0) vga_putc(' '); + } else { + vga_putentryat(c, vga_color, vga_column, vga_row); + if (++vga_column == VGA_WIDTH) { + vga_newline(); + } + } +} + +static void vga_puts(const char* data) { + size_t datalen = strlen(data); + for (size_t i = 0; i < datalen; i++) + vga_putc(data[i]); + + vga_update_cursor(); +} + +#endif // DBGLOG_TO_SCREEN + +// ================================================================== + +#ifdef DBGLOG_TO_SERIAL + +#define SER_PORT 0x3F8 // COM1 + +static void serial_init() { + outb(SER_PORT + 1, 0x00); // disable interrupts + outb(SER_PORT + 3, 0x80); // set baud rate + outb(SER_PORT + 0, 0x03); // set divisor to 3 (38400 baud) + outb(SER_PORT + 1, 0x00); + outb(SER_PORT + 3, 0x03); // 8 bits, no parity, one stop bit + outb(SER_PORT + 2, 0xC7); // enable FIFO, clear them, with 14-byte threshold +} + +static void serial_putc(const char c) { + while (!(inb(SER_PORT + 5) & 0x20)); + outb(SER_PORT, c); +} + +static void serial_puts(const char *c) { + while (*c) { + serial_putc(*c); + c++; + } +} + +#endif // DBGLOG_TO_SERIAL + +// ================================================================== + +STATIC_MUTEX(dbglog_mutex); + +void dbglog_setup() { + mutex_lock(&dbglog_mutex); +#ifdef DBGLOG_TO_SCREEN + vga_init(); +#endif +#ifdef DBGLOG_TO_SERIAL + serial_init(); +#endif + mutex_unlock(&dbglog_mutex); +} + +void dbg_print(const char* str) { +#ifdef DBGLOG_TO_SCREEN + vga_puts(str); +#endif +#ifdef DBGLOG_TO_SERIAL + serial_puts(str); +#endif +} + +void dbg_printf(const char* fmt, ...) { + va_list ap; + char buffer[256]; + + va_start(ap, fmt); + vsnprintf(buffer, 256, fmt, ap); + va_end(ap); + + dbg_print(buffer); +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/core/frame.c b/src/kernel/core/frame.c new file mode 100644 index 0000000..489d010 --- /dev/null +++ b/src/kernel/core/frame.c @@ -0,0 +1,85 @@ +#include +#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); +} + +STATIC_MUTEX(frame_allocator_mutex); + +uint32_t frame_alloc(size_t n) { + if (n > 32) return 0; + + mutex_lock(&frame_allocator_mutex); + 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; + + mutex_unlock(&frame_allocator_mutex); + return i * 32 + j; + } + } + } + mutex_unlock(&frame_allocator_mutex); + return 0; +} + +void frame_free(uint32_t base, size_t n) { + mutex_lock(&frame_allocator_mutex); + + for (size_t i = 0; i < n; i++) { + uint32_t idx = INDEX_FROM_BIT(base + i); + uint32_t ofs = OFFSET_FROM_BIT(base + i); + 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); + + mutex_unlock(&frame_allocator_mutex); +} + +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/src/kernel/core/gdt.c b/src/kernel/core/gdt.c new file mode 100644 index 0000000..eadde5f --- /dev/null +++ b/src/kernel/core/gdt.c @@ -0,0 +1,90 @@ +#include +#include + +#define GDT_ENTRIES 6 // The contents of each entry is defined in gdt_init. + +/* One entry of the table */ +struct gdt_entry { + uint16_t limit_low; + uint16_t base_low; + uint8_t base_middle; + uint8_t access; + uint8_t granularity; + uint8_t base_high; +} __attribute__((packed)); +typedef struct gdt_entry gdt_entry_t; + +/* Structure defining the whole table : address and size (in bytes). */ +struct gdt_ptr { + uint16_t limit; + uint32_t base; +} __attribute__((packed)); +typedef struct gdt_ptr gdt_ptr_t; + +/* The TSS is used for hardware multitasking. + We don't use that, but we still need a TSS so that user mode process exceptions + can be handled correctly by the kernel. */ +struct tss_entry { + uint32_t prev_tss; // The previous TSS - if we used hardware task switching this would form a linked list. + uint32_t esp0; // The stack pointer to load when we change to kernel mode. + uint32_t ss0; // The stack segment to load when we change to kernel mode. + uint32_t esp1; // Unused... + uint32_t ss1; + uint32_t esp2; + uint32_t ss2; + uint32_t cr3; + uint32_t eip; + uint32_t eflags; + uint32_t eax; + uint32_t ecx; + uint32_t edx; + uint32_t ebx; + uint32_t esp; + uint32_t ebp; + uint32_t esi; + uint32_t edi; + uint32_t es; // The value to load into ES when we change to kernel mode. + uint32_t cs; // The value to load into CS when we change to kernel mode. + uint32_t ss; // The value to load into SS when we change to kernel mode. + uint32_t ds; // The value to load into DS when we change to kernel mode. + uint32_t fs; // The value to load into FS when we change to kernel mode. + uint32_t gs; // The value to load into GS when we change to kernel mode. + uint32_t ldt; // Unused... + uint16_t trap; + uint16_t iomap_base; +} __attribute__((packed)); +typedef struct tss_entry tss_entry_t; + +// ========================= // +// Actual definitions + +static gdt_entry_t gdt_entries[GDT_ENTRIES]; +static gdt_ptr_t gdt_ptr; + +/* For internal use only. Writes one entry of the GDT with given parameters. */ +static void gdt_set_gate(int num, uint32_t base, uint32_t limit, uint8_t access, uint8_t gran) { + gdt_entries[num].base_low = (base & 0xFFFF); + gdt_entries[num].base_middle = (base >> 16) & 0xFF; + gdt_entries[num].base_high = (base >> 24) & 0xFF; + + gdt_entries[num].limit_low = (limit & 0xFFFF); + gdt_entries[num].granularity = (limit >> 16) & 0x0F; + gdt_entries[num].granularity |= gran & 0xF0; + gdt_entries[num].access = access; +} + +/* Write data to the GDT and enable it. */ +void gdt_init() { + gdt_ptr.limit = (sizeof(gdt_entry_t) * GDT_ENTRIES) - 1; + gdt_ptr.base = (uint32_t)&gdt_entries; + + gdt_set_gate(0, 0, 0, 0, 0); //Null segment + gdt_set_gate(1, 0, 0xFFFFFFFF, 0x9A, 0xCF); //Kernel code segment 0x08 + gdt_set_gate(2, 0, 0xFFFFFFFF, 0x92, 0xCF); //Kernel data segment 0x10 + gdt_set_gate(3, 0, 0xFFFFFFFF, 0xFA, 0xCF); //User code segment 0x18 + gdt_set_gate(4, 0, 0xFFFFFFFF, 0xF2, 0xCF); //User data segment 0x20 + + asm volatile ("lgdt %0"::"m"(gdt_ptr):"memory"); +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/core/idt.c b/src/kernel/core/idt.c new file mode 100644 index 0000000..2f244e3 --- /dev/null +++ b/src/kernel/core/idt.c @@ -0,0 +1,253 @@ +#include +#include +#include +#include +#include + +struct idt_entry { + uint16_t base_lo; //Low part of address to jump to + uint16_t sel; //Kernel segment selector + uint8_t always0; + uint8_t type_attr; //Type + uint16_t base_hi; //High part of address to jump to +} __attribute__((packed)); +typedef struct idt_entry idt_entry_t; + +struct idt_ptr { + uint16_t limit; + uint32_t base; +} __attribute__((packed)); +typedef struct idt_ptr idt_ptr_t; + +#define GATE_TYPE_INTERRUPT 14 // IF is cleared on interrupt +#define GATE_TYPE_TRAP 15 // IF stays as is + +#define GATE_PRESENT (1<<7) +#define GATE_DPL_SHIFT 5 + + +void isr0(); +void isr1(); +void isr2(); +void isr3(); +void isr4(); +void isr5(); +void isr6(); +void isr7(); +void isr8(); +void isr9(); +void isr10(); +void isr11(); +void isr12(); +void isr13(); +void isr14(); +void isr15(); +void isr16(); +void isr17(); +void isr18(); +void isr19(); +void isr20(); +void isr21(); +void isr22(); +void isr23(); +void isr24(); +void isr25(); +void isr26(); +void isr27(); +void isr28(); +void isr29(); +void isr30(); +void isr31(); + +void irq0(); +void irq1(); +void irq2(); +void irq3(); +void irq4(); +void irq5(); +void irq6(); +void irq7(); +void irq8(); +void irq9(); +void irq10(); +void irq11(); +void irq12(); +void irq13(); +void irq14(); +void irq15(); + +void syscall64(); + +// ************************************************************ +// Handler code + +static idt_entry_t idt_entries[256]; +static idt_ptr_t idt_ptr; + +static isr_handler_t irq_handlers[16] = {0}; +static isr_handler_t ex_handlers[32] = {0}; + +/* Called in interrupt.s when an exception fires (interrupt 0 to 31) */ +void idt_exHandler(registers_t *regs) { + if (ex_handlers[regs->int_no] != 0) { + ex_handlers[regs->int_no](regs); + } else { + //TODO: make sure all exceptions happenning in userspace do not cause kernel panic... + dbg_printf("Unhandled exception: %i\n", regs->int_no); + dbg_dump_registers(regs); + PANIC("Unhandled exception"); + } +} + +/* Called in interrupt.s when an IRQ fires (interrupt 32 to 47) */ +void idt_irqHandler(registers_t *regs) { + if (regs->err_code > 7) { + outb(0xA0, 0x20); + } + outb(0x20, 0x20); + + dbg_printf("IRQ %i\n", regs->err_code); + if (irq_handlers[regs->err_code] != 0) { + irq_handlers[regs->err_code](regs); + } +} + +/* Caled in interrupt.s when a syscall is called */ +void idt_syscallHandler(registers_t *regs) { + dbg_printf("Syscall %i\n", regs->int_no); + // do nothing, yet. +} + +/* For internal use only. Sets up an entry of the IDT with given parameters. */ +static void idt_set_gate(uint8_t num, void (*fun)(), uint8_t type) { + uint32_t base = (uint32_t)fun; + + idt_entries[num].base_lo = base & 0xFFFF; + idt_entries[num].base_hi = (base >> 16) & 0xFFFF; + + idt_entries[num].sel = K_CODE_SEGMENT; + idt_entries[num].always0 = 0; + idt_entries[num].type_attr = GATE_PRESENT + | (3 << GATE_DPL_SHIFT) // accessible from user mode + | type; +} + +static const struct { + uint8_t num; + void (*fun)(); + uint8_t type; +} gates[] = { + // Most processor exceptions are traps and handling them + // should be preemptible + { 0, isr0, GATE_TYPE_TRAP }, + { 1, isr1, GATE_TYPE_TRAP }, + { 2, isr2, GATE_TYPE_TRAP }, + { 3, isr3, GATE_TYPE_TRAP }, + { 4, isr4, GATE_TYPE_TRAP }, + { 5, isr5, GATE_TYPE_TRAP }, + { 6, isr6, GATE_TYPE_TRAP }, + { 7, isr7, GATE_TYPE_TRAP }, + { 8, isr8, GATE_TYPE_TRAP }, + { 9, isr9, GATE_TYPE_TRAP }, + { 10, isr10, GATE_TYPE_TRAP }, + { 11, isr11, GATE_TYPE_TRAP }, + { 12, isr12, GATE_TYPE_TRAP }, + { 13, isr13, GATE_TYPE_TRAP }, + { 14, isr14, GATE_TYPE_INTERRUPT }, // reenables interrupts later on + { 15, isr15, GATE_TYPE_TRAP }, + { 16, isr16, GATE_TYPE_TRAP }, + { 17, isr17, GATE_TYPE_TRAP }, + { 18, isr18, GATE_TYPE_TRAP }, + { 19, isr19, GATE_TYPE_TRAP }, + { 20, isr20, GATE_TYPE_TRAP }, + { 21, isr21, GATE_TYPE_TRAP }, + { 22, isr22, GATE_TYPE_TRAP }, + { 23, isr23, GATE_TYPE_TRAP }, + { 24, isr24, GATE_TYPE_TRAP }, + { 25, isr25, GATE_TYPE_TRAP }, + { 26, isr26, GATE_TYPE_TRAP }, + { 27, isr27, GATE_TYPE_TRAP }, + { 28, isr28, GATE_TYPE_TRAP }, + { 29, isr29, GATE_TYPE_TRAP }, + { 30, isr30, GATE_TYPE_TRAP }, + { 31, isr31, GATE_TYPE_TRAP }, + + // IRQs are not preemptible ; an IRQ handler should do the bare minimum + // (communication with the hardware), and then pass a message to a worker + // process in order to do further processing + { 32, irq0, GATE_TYPE_INTERRUPT }, + { 33, irq1, GATE_TYPE_INTERRUPT }, + { 34, irq2, GATE_TYPE_INTERRUPT }, + { 35, irq3, GATE_TYPE_INTERRUPT }, + { 36, irq4, GATE_TYPE_INTERRUPT }, + { 37, irq5, GATE_TYPE_INTERRUPT }, + { 38, irq6, GATE_TYPE_INTERRUPT }, + { 39, irq7, GATE_TYPE_INTERRUPT }, + { 40, irq8, GATE_TYPE_INTERRUPT }, + { 41, irq9, GATE_TYPE_INTERRUPT }, + { 42, irq10, GATE_TYPE_INTERRUPT }, + { 43, irq11, GATE_TYPE_INTERRUPT }, + { 44, irq12, GATE_TYPE_INTERRUPT }, + { 45, irq13, GATE_TYPE_INTERRUPT }, + { 46, irq14, GATE_TYPE_INTERRUPT }, + { 47, irq15, GATE_TYPE_INTERRUPT }, + + // Of course, syscalls are preemptible + { 64, syscall64, GATE_TYPE_TRAP }, + + { 0, 0, 0 } +}; + +/* Remaps the IRQs. Sets up the IDT. */ +void idt_init() { + memset((uint8_t*)&idt_entries, 0, sizeof(idt_entry_t) * 256); + + //Remap the IRQ table + outb(0x20, 0x11); + outb(0xA0, 0x11); + outb(0x21, 0x20); + outb(0xA1, 0x28); + outb(0x21, 0x04); + outb(0xA1, 0x02); + outb(0x21, 0x01); + outb(0xA1, 0x01); + outb(0x21, 0x0); + outb(0xA1, 0x0); + + for (int i = 0; gates[i].type != 0; i++) { + idt_set_gate(gates[i].num, gates[i].fun, gates[i].type); + } + + idt_ptr.limit = (sizeof(idt_entry_t) * 256) - 1; + idt_ptr.base = (uint32_t)&idt_entries; + + asm volatile ("lidt %0"::"m"(idt_ptr):"memory"); + + // Some setup calls that come later on are not preemptible, + // so we wait until then to enable interrupts. +} + +/* Sets up an IRQ handler for given IRQ. */ +void idt_set_irq_handler(int number, isr_handler_t func) { + if (number < 16 && number >= 0) { + irq_handlers[number] = func; + } +} + +/* Sets up a handler for a processor exception */ +void idt_set_ex_handler(int number, isr_handler_t func) { + if (number >= 0 && number < 32) { + ex_handlers[number] = func; + } +} + +void dbg_dump_registers(registers_t *regs) { + dbg_printf("/ Exception %i\n", regs->int_no); + dbg_printf("| EAX: 0x%p EBX: 0x%p ECX: 0x%p EDX: 0x%p\n", regs->eax, regs->ebx, regs->ecx, regs->edx); + dbg_printf("| EDI: 0x%p ESI: 0x%p ESP: 0x%p EBP: 0x%p\n", regs->edi, regs->esi, regs->esp, regs->ebp); + dbg_printf("| EIP: 0x%p CS : 0x%p DS : 0x%p SS : 0x%p\n", regs->eip, regs->cs, regs->ds, regs->ss); + dbg_printf("\\ EFl: 0x%p I# : 0x%p Err: 0x%p\n", regs->eflags, regs->int_no, regs->err_code); +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ + diff --git a/src/kernel/core/interrupt.s b/src/kernel/core/interrupt.s new file mode 100644 index 0000000..d40fff0 --- /dev/null +++ b/src/kernel/core/interrupt.s @@ -0,0 +1,126 @@ +;************************************************************************************ + +%macro COMMONSTUB 1 +[EXTERN idt_%1Handler] +%1_common_stub: + + pusha ; Pushes edi,esi,ebp,esp,ebx,edx,ecx,eax + + mov ax, ds ; Lower 16-bits of eax = ds. + push eax ; save the data segment descriptor + + mov ax, 0x10 ; load the kernel data segment descriptor + mov ds, ax + mov es, ax + mov fs, ax + mov gs, ax + + ; pass the register data structure as a pointer to the function + ; (passing it directly results in GCC trashing the data when doing optimisations) + mov eax, esp + push eax + call idt_%1Handler + add esp, 4 + + pop eax ; reload the original data segment descriptor + mov ds, ax + mov es, ax + mov fs, ax + mov gs, ax + + popa ; Pops edi,esi,ebp... + add esp, 8 ; Cleans up the pushed error code and pushed ISR number + iret +%endmacro + +COMMONSTUB ex +COMMONSTUB irq +COMMONSTUB syscall + +;************************************************************************************ + +%macro EX_NOERRCODE 1 ; define a macro, taking one parameter + [GLOBAL isr%1] ; %1 accesses the first parameter. + isr%1: + push byte 0 + push byte %1 + jmp ex_common_stub +%endmacro + +%macro EX_ERRCODE 1 + [GLOBAL isr%1] + isr%1: + push byte %1 + jmp ex_common_stub +%endmacro + +%macro IRQ 2 + [GLOBAL irq%1] + irq%1: + push byte %1 ;push irq number + push byte %2 ;push int number + jmp irq_common_stub +%endmacro + +%macro SYSCALL 1 + [GLOBAL syscall%1] + syscall%1: + cli + push byte 0 + push byte %1 + jmp syscall_common_stub +%endmacro + +EX_NOERRCODE 0 +EX_NOERRCODE 1 +EX_NOERRCODE 2 +EX_NOERRCODE 3 +EX_NOERRCODE 4 +EX_NOERRCODE 5 +EX_NOERRCODE 6 +EX_NOERRCODE 7 +EX_ERRCODE 8 +EX_NOERRCODE 9 +EX_ERRCODE 10 +EX_ERRCODE 11 +EX_ERRCODE 12 +EX_ERRCODE 13 +EX_ERRCODE 14 +EX_NOERRCODE 15 +EX_NOERRCODE 16 +EX_NOERRCODE 17 +EX_NOERRCODE 18 +EX_NOERRCODE 19 +EX_NOERRCODE 20 +EX_NOERRCODE 21 +EX_NOERRCODE 22 +EX_NOERRCODE 23 +EX_NOERRCODE 24 +EX_NOERRCODE 25 +EX_NOERRCODE 26 +EX_NOERRCODE 27 +EX_NOERRCODE 28 +EX_NOERRCODE 29 +EX_NOERRCODE 30 +EX_NOERRCODE 31 + +IRQ 0, 32 +IRQ 1, 33 +IRQ 2, 34 +IRQ 3, 35 +IRQ 4, 36 +IRQ 5, 37 +IRQ 6, 38 +IRQ 7, 39 +IRQ 8, 40 +IRQ 9, 41 +IRQ 10, 42 +IRQ 11, 43 +IRQ 12, 44 +IRQ 13, 45 +IRQ 14, 46 +IRQ 15, 47 + +SYSCALL 64 + +; vim: set ts=4 sw=4 tw=0 noet : diff --git a/src/kernel/core/kmain.c b/src/kernel/core/kmain.c new file mode 100644 index 0000000..2169b7d --- /dev/null +++ b/src/kernel/core/kmain.c @@ -0,0 +1,215 @@ +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include + +#include + +#include +#include + +extern const void k_end_addr; // defined in linker script : 0xC0000000 plus kernel stuff + +void breakpoint_handler(registers_t *regs) { + dbg_printf("Breakpoint! (int3)\n"); + BOCHS_BREAKPOINT; +} + +void region_test1() { + void* p = region_alloc(0x1000, "Test region", 0); + dbg_printf("Allocated one-page region: 0x%p\n", p); + dbg_print_region_info(); + void* q = region_alloc(0x1000, "Test region", 0); + dbg_printf("Allocated one-page region: 0x%p\n", q); + dbg_print_region_info(); + void* r = region_alloc(0x2000, "Test region", 0); + dbg_printf("Allocated two-page region: 0x%p\n", r); + dbg_print_region_info(); + void* s = region_alloc(0x10000, "Test region", 0); + dbg_printf("Allocated 16-page region: 0x%p\n", s); + dbg_print_region_info(); + region_free(p); + dbg_printf("Freed region 0x%p\n", p); + dbg_print_region_info(); + region_free(q); + dbg_printf("Freed region 0x%p\n", q); + dbg_print_region_info(); + region_free(r); + dbg_printf("Freed region 0x%p\n", r); + dbg_print_region_info(); + region_free(s); + dbg_printf("Freed region 0x%p\n", s); + dbg_print_region_info(); +} + +void region_test2() { + // allocate a big region and try to write into it + dbg_printf("Begin region test 2..."); + const size_t n = 200; + void* p0 = region_alloc(n * PAGE_SIZE, "Test big region", default_allocator_pf_handler); + for (size_t i = 0; i < n; i++) { + uint32_t *x = (uint32_t*)(p0 + i * PAGE_SIZE); + x[0] = 12; + x[1] = (i * 20422) % 122; + } + // unmap memory + for (size_t i = 0; i < n; i++) { + void* p = p0 + i * PAGE_SIZE; + uint32_t *x = (uint32_t*)p; + ASSERT(x[1] == (i * 20422) % 122); + + uint32_t f = pd_get_frame(p); + ASSERT(f != 0); + pd_unmap_page(p); + ASSERT(pd_get_frame(p) == 0); + + frame_free(f, 1); + } + region_free(p0); + dbg_printf("OK\n"); +} + +void kmalloc_test(void* kernel_data_end) { + // Test kmalloc ! + dbg_print_region_info(); + dbg_printf("Begin kmalloc test...\n"); + const int m = 200; + uint16_t** ptr = malloc(m * sizeof(uint32_t)); + for (int i = 0; i < m; i++) { + size_t s = 1 << ((i * 7) % 11 + 2); + ptr[i] = (uint16_t*)malloc(s); + ASSERT((void*)ptr[i] >= kernel_data_end && (size_t)ptr[i] < 0xFFC00000); + *ptr[i] = ((i * 211) % 1024); + } + dbg_printf("Fully allocated.\n"); + dbg_print_region_info(); + for (int i = 0; i < m; i++) { + for (int j = i; j < m; j++) { + ASSERT(*ptr[j] == (j * 211) % 1024); + } + free(ptr[i]); + } + free(ptr); + dbg_printf("Kmalloc test OK.\n"); + dbg_print_region_info(); +} + +void test_hashtbl_1() { + // hashtable test + hashtbl_t *ht = create_hashtbl(str_key_eq_fun, str_hash_fun, 0); + hashtbl_add(ht, "test1", "Hello, world [test1]"); + hashtbl_add(ht, "test2", "Hello, world [test2]"); + dbg_printf("ht[test1] = %s\n", hashtbl_find(ht, "test1")); + dbg_printf("ht[test] = %s\n", hashtbl_find(ht, "test")); + dbg_printf("ht[test2] = %s\n", hashtbl_find(ht, "test2")); + dbg_printf("adding test...\n"); + hashtbl_add(ht, "test", "Forever alone"); + dbg_printf("ht[test1] = %s\n", hashtbl_find(ht, "test1")); + dbg_printf("ht[test] = %s\n", hashtbl_find(ht, "test")); + dbg_printf("ht[test2] = %s\n", hashtbl_find(ht, "test2")); + dbg_printf("removing test1...\n"); + hashtbl_remove(ht, "test1"); + dbg_printf("ht[test1] = %s\n", hashtbl_find(ht, "test1")); + dbg_printf("ht[test] = %s\n", hashtbl_find(ht, "test")); + dbg_printf("ht[test2] = %s\n", hashtbl_find(ht, "test2")); + delete_hashtbl(ht); +} + +void test_hashtbl_2() { + hashtbl_t *ht = create_hashtbl(id_key_eq_fun, id_hash_fun, 0); + hashtbl_add(ht, (void*)12, "Hello, world [12]"); + hashtbl_add(ht, (void*)777, "Hello, world [777]"); + dbg_printf("ht[12] = %s\n", hashtbl_find(ht, (void*)12)); + dbg_printf("ht[144] = %s\n", hashtbl_find(ht, (void*)144)); + dbg_printf("ht[777] = %s\n", hashtbl_find(ht, (void*)777)); + dbg_printf("adding 144...\n"); + hashtbl_add(ht, (void*)144, "Forever alone"); + dbg_printf("ht[12] = %s\n", hashtbl_find(ht, (void*)12)); + dbg_printf("ht[144] = %s\n", hashtbl_find(ht, (void*)144)); + dbg_printf("ht[777] = %s\n", hashtbl_find(ht, (void*)777)); + dbg_printf("removing 12...\n"); + hashtbl_remove(ht, (void*)12); + dbg_printf("ht[12] = %s\n", hashtbl_find(ht, (void*)12)); + dbg_printf("ht[144] = %s\n", hashtbl_find(ht, (void*)144)); + dbg_printf("ht[777] = %s\n", hashtbl_find(ht, (void*)777)); + delete_hashtbl(ht); +} + +void test_thread(void* a) { + for(int i = 0; i < 120; i++) { + dbg_printf("b"); + for (int x = 0; x < 100000; x++) asm volatile("xor %%ebx, %%ebx":::"%ebx"); + if (i % 8 == 0) yield(); + } +} +void kernel_init_stage2(void* data) { + dbg_print_region_info(); + dbg_print_frame_stats(); + + test_hashtbl_1(); + test_hashtbl_2(); + + thread_t *tb = new_thread(test_thread, 0); + resume_thread(tb, false); + + for (int i = 0; i < 120; i++) { + dbg_printf("a"); + for (int x = 0; x < 100000; x++) asm volatile("xor %%ebx, %%ebx":::"%ebx"); + } + PANIC("Reached kmain end! Falling off the edge."); +} + +void kmain(struct multiboot_info_t *mbd, int32_t mb_magic) { + dbglog_setup(); + + dbg_printf("Hello, kernel world!\n"); + dbg_printf("This is %s, version %s.\n", OS_NAME, OS_VERSION); + + ASSERT(mb_magic == MULTIBOOT_BOOTLOADER_MAGIC); + + gdt_init(); dbg_printf("GDT set up.\n"); + + idt_init(); dbg_printf("IDT set up.\n"); + idt_set_ex_handler(EX_BREAKPOINT, breakpoint_handler); + 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); + + // 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(); + + paging_setup(kernel_data_end); + dbg_printf("Paging seems to be working!\n"); + + BOCHS_BREAKPOINT; + + region_allocator_init(kernel_data_end); + region_test1(); + region_test2(); + + kmalloc_setup(); + kmalloc_test(kernel_data_end); + + // enter multi-threading mode + // interrupts are enabled at this moment, so all + // code run from now on should be preemtible (ie thread-safe) + threading_setup(kernel_init_stage2, 0); + PANIC("Should never come here."); +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/core/kmalloc.c b/src/kernel/core/kmalloc.c new file mode 100644 index 0000000..e15572a --- /dev/null +++ b/src/kernel/core/kmalloc.c @@ -0,0 +1,52 @@ +#include + +#include +#include + +#include +#include +#include + +static void* page_alloc_fun_for_kmalloc(size_t bytes) { + void* addr = region_alloc(bytes, "Core kernel heap", default_allocator_pf_handler); + return addr; +} + +static slab_type_t slab_sizes[] = { + { "8B kmalloc objects", 8, 2 }, + { "16B kmalloc objects", 16, 2 }, + { "32B kmalloc objects", 32, 2 }, + { "64B kmalloc objects", 64, 4 }, + { "128B kmalloc objects", 128, 4 }, + { "256B kmalloc objects", 256, 4 }, + { "512B kmalloc objects", 512, 8 }, + { "1KB kmalloc objects", 1024, 8 }, + { "2KB kmalloc objects", 2048, 16 }, + { "4KB kmalloc objects", 4096, 16 }, + { 0, 0, 0 } +}; + +static mem_allocator_t *kernel_allocator = 0; +STATIC_MUTEX(malloc_mutex); + +void kmalloc_setup() { + kernel_allocator = + create_slab_allocator(slab_sizes, page_alloc_fun_for_kmalloc, + region_free_unmap_free); +} + +void* malloc(size_t sz) { + void* res = 0; + + mutex_lock(&malloc_mutex); + res = slab_alloc(kernel_allocator, sz); + mutex_unlock(&malloc_mutex); + + return res; +} + +void free(void* ptr) { + mutex_lock(&malloc_mutex); + slab_free(kernel_allocator, ptr); + mutex_unlock(&malloc_mutex); +} diff --git a/src/kernel/core/loader.s b/src/kernel/core/loader.s new file mode 100644 index 0000000..447d82d --- /dev/null +++ b/src/kernel/core/loader.s @@ -0,0 +1,86 @@ +[EXTERN kmain] ; kmain is defined in kmain.c +[GLOBAL loader] ; making entry point visible to linker +[GLOBAL kernel_pd] ; make kernel page directory visible +[GLOBAL kernel_stack_protector] ; used to detect kernel stack overflow +[GLOBAL kernel_stack_top] ; stack re-used by scheduler + +; higher-half kernel setup +K_HIGHHALF_ADDR equ 0xC0000000 +K_PAGE_NUMBER equ (K_HIGHHALF_ADDR >> 22) + +; loader stack size +LOADER_STACK_SIZE equ 0x8000 ; 8Kb + +; setting up the Multiboot header - see GRUB docs for details +MODULEALIGN equ 1<<0 ; align loaded modules on page boundaries +MEMINFO equ 1<<1 ; provide memory map +FLAGS equ MODULEALIGN | MEMINFO ; this is the Multiboot 'flag' field +MAGIC equ 0x1BADB002 ; 'magic number' lets bootloader find the header +CHECKSUM equ -(MAGIC + FLAGS) ; checksum required + +[section .setup] +align 4 +multiboot_header: + dd MAGIC + dd FLAGS + dd CHECKSUM + +loader: + ; setup the boot page directory used for higher-half + mov ecx, kernel_pd + sub ecx, K_HIGHHALF_ADDR ; access its lower-half address + mov cr3, ecx + + ; Set PSE bit in CR4 to enable 4MB pages. + mov ecx, cr4 + or ecx, 0x00000010 + mov cr4, ecx + + ; Set PG bit in CR0 to enable paging. + mov ecx, cr0 + or ecx, 0x80000000 + mov cr0, ecx + + ; long jump required + lea ecx, [higherhalf] + jmp ecx + +[section .data] +align 0x1000 +kernel_pd: + ; uses 4MB pages + ; identity-maps the first 4Mb of RAM, and also maps them with offset += k_highhalf_addr + dd 0x00000083 + times (K_PAGE_NUMBER - 1) dd 0 + dd 0x00000083 + times (1024 - K_PAGE_NUMBER - 1) dd 0 + +[section .text] +higherhalf: ; now we're running in higher half + ; unmap first 4Mb + mov dword [kernel_pd], 0 + invlpg [0] + + mov esp, kernel_stack_top ; set up the stack + + push eax ; pass Multiboot magic number + add ebx, K_HIGHHALF_ADDR ; update the MB info structure so that it is in higher half + push ebx ; pass Multiboot info structure + + call kmain ; call kernel proper + +hang: + ; halt machine should kernel return + cli + hlt + jmp hang + +[section .bss] +align 0x1000 +kernel_stack_protector: + resb 0x1000 ; as soon as we have efficient paging, we WON'T map this page +kernel_stack_bottom: + resb LOADER_STACK_SIZE +kernel_stack_top: + +; vim: set ts=4 sw=4 tw=0 noet : diff --git a/src/kernel/core/paging.c b/src/kernel/core/paging.c new file mode 100644 index 0000000..e60ca53 --- /dev/null +++ b/src/kernel/core/paging.c @@ -0,0 +1,298 @@ +#include +#include +#include +#include +#include +#include +#include +#include + +#define PAGE_OF_ADDR(x) (((size_t)x >> PAGE_SHIFT) % N_PAGES_IN_PT) +#define PT_OF_ADDR(x) ((size_t)x >> (PAGE_SHIFT + PT_SHIFT)) + +#define PTE_PRESENT (1<<0) +#define PTE_RW (1<<1) +#define PTE_USER (1<<2) +#define PTE_WRITE_THROUGH (1<<3) +#define PTE_DISABLE_CACHE (1<<4) +#define PTE_ACCESSED (1<<5) +#define PTE_DIRTY (1<<6) // only PTE +#define PTE_SIZE_4M (1<<7) // only PDE +#define PTE_GLOBAL (1<<8) // only PTE +#define PTE_FRAME_SHIFT 12 + +typedef struct page_table { + uint32_t page[1024]; +} pagetable_t; + +struct page_directory { + uint32_t phys_addr; // physical address of page directory + // to modify a page directory, we first map it + // then we can use mirroring to edit it + // (the last 4M of the address space are mapped to the PD itself) + + mutex_t mutex; +}; + + +// access kernel page directory page defined in loader.s +// (this is a correct higher-half address) +extern pagetable_t kernel_pd; + +// pre-allocate a page table so that we can map the first 4M of kernel memory +static pagetable_t __attribute__((aligned(PAGE_SIZE))) kernel_pt0; + +extern char kernel_stack_protector; + +static pagedir_t kernel_pd_d; + +#define current_pt ((pagetable_t*)PD_MIRROR_ADDR) +#define current_pd ((pagetable_t*)(PD_MIRROR_ADDR + (N_PAGES_IN_PT-1)*PAGE_SIZE)) + +void page_fault_handler(registers_t *regs) { + void* vaddr; + asm volatile("movl %%cr2, %0":"=r"(vaddr)); + + if ((size_t)vaddr >= K_HIGHHALF_ADDR) { + uint32_t pt = PT_OF_ADDR(vaddr); + + if (current_pd != &kernel_pd && current_pd->page[pt] != kernel_pd.page[pt]) { + current_pd->page[pt] = kernel_pd.page[pt]; + invlpg(¤t_pt[pt]); + return; + } + if (regs->eflags & EFLAGS_IF) asm volatile("sti"); // from now on we are preemptible + + if (vaddr >= (void*)&kernel_stack_protector && vaddr < (void*)&kernel_stack_protector + PAGE_SIZE) { + dbg_printf("Kernel stack overflow at 0x%p\n", vaddr); + PANIC("Kernel stack overflow."); + } + + if ((size_t)vaddr >= PD_MIRROR_ADDR) { + dbg_printf("Fault on access to mirrorred PD at 0x%p\n", vaddr); + dbg_print_region_info(); + PANIC("Unhandled kernel space page fault"); + } + + region_info_t *i = find_region(vaddr); + if (i == 0) { + dbg_printf("Kernel pagefault in non-existing region at 0x%p\n", vaddr); + dbg_dump_registers(regs); + PANIC("Unhandled kernel space page fault"); + } + if (i->pf == 0) { + dbg_printf("Kernel pagefault in region with no handler at 0x%p\n", vaddr); + dbg_dump_registers(regs); + dbg_print_region_info(); + PANIC("Unhandled kernel space page fault"); + } + i->pf(get_current_pagedir(), i, vaddr); + } else { + if (regs->eflags & EFLAGS_IF) asm volatile("sti"); // userspace PF handlers should always be preemptible + + dbg_printf("Userspace page fault at 0x%p\n", vaddr); + PANIC("Unhandled userspace page fault"); + // not handled yet + // TODO + } +} + +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; + + ASSERT(n_kernel_pages <= 1024); // we use less than 4M for kernel + + // setup kernel_pd_d structure + kernel_pd_d.phys_addr = (size_t)&kernel_pd - K_HIGHHALF_ADDR; + kernel_pd_d.mutex = MUTEX_UNLOCKED; + + // setup kernel_pt0 + ASSERT(PAGE_OF_ADDR(K_HIGHHALF_ADDR) == 0); // kernel is 4M-aligned + ASSERT(FIRST_KERNEL_PT == 768); + for (size_t i = 0; i < n_kernel_pages; i++) { + if ((i * PAGE_SIZE) + K_HIGHHALF_ADDR == (size_t)&kernel_stack_protector) { + kernel_pt0.page[i] = 0; // don't map kernel stack protector page + frame_free(i, 1); + } else { + kernel_pt0.page[i] = (i << PTE_FRAME_SHIFT) | PTE_PRESENT | PTE_RW | PTE_GLOBAL; + } + } + for (size_t i = n_kernel_pages; i < 1024; i++){ + kernel_pt0.page[i] = 0; + } + + // replace 4M mapping by kernel_pt0 + kernel_pd.page[FIRST_KERNEL_PT] = + (((size_t)&kernel_pt0 - K_HIGHHALF_ADDR) & PAGE_MASK) | PTE_PRESENT | PTE_RW; + // set up mirroring + kernel_pd.page[N_PAGES_IN_PT-1] = + (((size_t)&kernel_pd - K_HIGHHALF_ADDR) & PAGE_MASK) | PTE_PRESENT | PTE_RW; + + invlpg((void*)K_HIGHHALF_ADDR); + + // paging already enabled in loader, nothing to do. + + // disable 4M pages (remove PSE bit in CR4) + uint32_t cr4; + asm volatile("movl %%cr4, %0": "=r"(cr4)); + cr4 &= ~0x00000010; + asm volatile("movl %0, %%cr4":: "r"(cr4)); + + idt_set_ex_handler(EX_PAGE_FAULT, page_fault_handler); +} + +pagedir_t *get_current_pagedir() { + if (current_thread == 0) return &kernel_pd_d; + return current_thread->current_pd_d; +} + +pagedir_t *get_kernel_pagedir() { + return &kernel_pd_d; +} + +void switch_pagedir(pagedir_t *pd) { + asm volatile("movl %0, %%cr3":: "r"(pd->phys_addr)); + if (current_thread != 0) current_thread->current_pd_d = pd; +} + +// ============================== // +// Mapping and unmapping of pages // +// ============================== // + +uint32_t pd_get_frame(void* vaddr) { + uint32_t pt = PT_OF_ADDR(vaddr); + uint32_t page = PAGE_OF_ADDR(vaddr); + + pagetable_t *pd = ((size_t)vaddr >= K_HIGHHALF_ADDR ? &kernel_pd : current_pd); + + if (!pd->page[pt] & PTE_PRESENT) return 0; + if (!current_pt[pt].page[page] & PTE_PRESENT) return 0; + return current_pt[pt].page[page] >> PTE_FRAME_SHIFT; +} + +int pd_map_page(void* vaddr, uint32_t frame_id, bool rw) { + uint32_t pt = PT_OF_ADDR(vaddr); + uint32_t page = PAGE_OF_ADDR(vaddr); + + ASSERT((size_t)vaddr < PD_MIRROR_ADDR); + + pagedir_t *pdd = ((size_t)vaddr >= K_HIGHHALF_ADDR || current_thread == 0 + ? &kernel_pd_d : current_thread->current_pd_d); + pagetable_t *pd = ((size_t)vaddr >= K_HIGHHALF_ADDR ? &kernel_pd : current_pd); + mutex_lock(&pdd->mutex); + + if (!pd->page[pt] & PTE_PRESENT) { + uint32_t new_pt_frame = frame_alloc(1); + if (new_pt_frame == 0) { + mutex_unlock(&pdd->mutex); + return 1; // OOM + } + + current_pd->page[pt] = pd->page[pt] = + (new_pt_frame << PTE_FRAME_SHIFT) | PTE_PRESENT | PTE_RW; + invlpg(¤t_pt[pt]); + } + current_pt[pt].page[page] = + (frame_id << PTE_FRAME_SHIFT) + | PTE_PRESENT + | ((size_t)vaddr < K_HIGHHALF_ADDR ? PTE_USER : PTE_GLOBAL) + | (rw ? PTE_RW : 0); + invlpg(vaddr); + + mutex_unlock(&pdd->mutex); + return 0; +} + +void pd_unmap_page(void* vaddr) { + uint32_t pt = PT_OF_ADDR(vaddr); + uint32_t page = PAGE_OF_ADDR(vaddr); + + pagetable_t *pd = ((size_t)vaddr >= K_HIGHHALF_ADDR ? &kernel_pd : current_pd); + // no need to lock the PD's mutex + + if (!pd->page[pt] & PTE_PRESENT) return; + if (!current_pt[pt].page[page] & PTE_PRESENT) return; + + current_pt[pt].page[page] = 0; + invlpg(vaddr); + + // If the page table is completely empty we might want to free + // it, but we would actually lose a lot of time checking if + // the PT is really empty (since we don't store the + // number of used pages in each PT), so it's probably not worth it +} + +// Creation and deletion of page directories + +pagedir_t *create_pagedir() { + uint32_t pd_phys = 0; + pagedir_t *pd = 0; + void* temp = 0; + + pd_phys = frame_alloc(1); + if (pd_phys == 0) goto error; + + pd = (pagedir_t*)malloc(sizeof(pagedir_t)); + if (pd == 0) goto error; + + temp = region_alloc(PAGE_SIZE, 0, 0); + if (temp == 0) goto error; + + int error = pd_map_page(temp, pd_phys, true); + if (error) goto error; + + pd->phys_addr = pd_phys * PAGE_SIZE; + pd->mutex = MUTEX_UNLOCKED; + + // initialize PD with zeroes + pagetable_t *pt = (pagetable_t*)temp; + for (size_t i = 0; i < N_PAGES_IN_PT; i++) { + pt->page[i] = 0; + } + // use kernel page tables + for(size_t i = FIRST_KERNEL_PT; i < N_PAGES_IN_PT-1; i++) { + pt->page[i] = kernel_pd.page[i]; + } + // set up mirroring + pt->page[N_PAGES_IN_PT-1] = pd->phys_addr | PTE_PRESENT | PTE_RW; + + region_free_unmap(temp); + + return pd; + + error: + if (pd_phys != 0) frame_free(pd_phys, 1); + if (pd != 0) free(pd); + if (temp != 0) region_free(temp); + return 0; +} + +void delete_pagedir(pagedir_t *pd) { + pagedir_t *restore_pd = get_current_pagedir(); + if (restore_pd == pd) restore_pd = &kernel_pd_d; + + // make a copy of page directory on the stack + switch_pagedir(pd); + pagetable_t backup; + for (size_t i = 0; i < N_PAGES_IN_PT; i++) { + backup.page[i] = current_pd->page[i]; + } + switch_pagedir(restore_pd); + + // free the page tables + for (size_t i = 0; i < FIRST_KERNEL_PT; i++) { + if (backup.page[i] & PTE_PRESENT) + frame_free(backup.page[i] >> PTE_FRAME_SHIFT, 1); + } + // free the page directory page + uint32_t pd_phys = pd->phys_addr / PAGE_SIZE; + ASSERT(pd_phys == (backup.page[N_PAGES_IN_PT-1] >> PTE_FRAME_SHIFT)); + frame_free(pd_phys, 1); + // free the pagedir_t structure + free(pd); + + return; +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/core/region.c b/src/kernel/core/region.c new file mode 100644 index 0000000..3127048 --- /dev/null +++ b/src/kernel/core/region.c @@ -0,0 +1,397 @@ +#include +#include +#include +#include + +typedef union region_descriptor { + struct { + union region_descriptor *next; + } unused_descriptor; + struct { + void* addr; + size_t 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_RESERVE_DESCRIPTORS 2 // always keep at least 2 unused descriptors + +#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; +uint32_t n_unused_descriptors; +static descriptor_t *first_free_region_by_addr, *first_free_region_by_size; +static descriptor_t *first_used_region; + +STATIC_MUTEX(ra_mutex); // region allocator mutex + +// ========================================================= // +// HELPER FUNCTIONS FOR THE MANIPULATION OF THE REGION LISTS // +// ========================================================= // + +static void add_unused_descriptor(descriptor_t *d) { + n_unused_descriptors++; + 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; + n_unused_descriptors--; + } + 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->free.addr > d->free.addr) { + d->free.next_by_addr = i->free.next_by_addr; + i->free.next_by_addr = d; + 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 { + // 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) { + d->free.next_by_size = 0; + d->free.first_bigger = 0; + i->free.next_by_size = d; + if (d->free.size > i->free.size) i->free.first_bigger = d; + break; + } else if (i->free.next_by_size->free.size >= d->free.size) { + 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); + i->free.next_by_size = d; + if (d->free.size > i->free.size) i->free.first_bigger = d; + break; + } else { + // continue + i = i->free.next_by_size; + } + } + } +} + +static descriptor_t *find_used_region(void* 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) { + n_unused_descriptors = 0; + first_unused_descriptor = 0; + for (int i = 0; i < N_BASE_DESCRIPTORS; i++) { + add_unused_descriptor(&base_descriptors[i]); + } + + descriptor_t *f0 = get_unused_descriptor(); + f0->free.addr = (void*)PAGE_ALIGN_UP(kernel_data_end); + f0->free.size = ((void*)LAST_KERNEL_ADDR - f0->free.addr); + f0->free.next_by_size = 0; + f0->free.first_bigger = 0; + first_free_region_by_size = first_free_region_by_addr = f0; + + descriptor_t *u0 = get_unused_descriptor(); + u0->used.i.addr = (void*)K_HIGHHALF_ADDR; + u0->used.i.size = PAGE_ALIGN_UP(kernel_data_end) - K_HIGHHALF_ADDR; + u0->used.i.type = "Kernel code & data"; + u0->used.i.pf = 0; + u0->used.next_by_addr = 0; + first_used_region = u0; +} + +static void region_free_inner(void* 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 region_free(void* addr) { + mutex_lock(&ra_mutex); + region_free_inner(addr); + mutex_unlock(&ra_mutex); +} + +static void* region_alloc_inner(size_t size, char* type, page_fault_handler_t pf, bool use_reserve) { + 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) { + // region i is the one we want to allocate in + descriptor_t *x = 0; + if (i->free.size > size) { + if (n_unused_descriptors <= N_RESERVE_DESCRIPTORS && !use_reserve) { + return 0; + } + + // this assert basically means that the allocation function + // is called less than N_RESERVE_DESCRIPTORS times with + // the use_reserve flag before more descriptors + // are allocated. + x = get_unused_descriptor(); + ASSERT(x != 0); + + 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; + } + } + // do the allocation + remove_free_region(i); + if (x != 0) add_free_region(x); + + void* 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; //No big enough block found +} + +void* region_alloc(size_t size, char* type, page_fault_handler_t pf) { + void* result = 0; + mutex_lock(&ra_mutex); + + if (n_unused_descriptors <= N_RESERVE_DESCRIPTORS) { + uint32_t frame = frame_alloc(1); + if (frame == 0) goto try_anyway; + + void* descriptor_region = region_alloc_inner(PAGE_SIZE, "Region descriptors", 0, true); + ASSERT(descriptor_region != 0); + + int error = pd_map_page(descriptor_region, frame, 1); + if (error) { + // this can happen if we weren't able to allocate a frame for + // a new pagetable + frame_free(frame, 1); + region_free_inner(descriptor_region); + goto try_anyway; + } + + for (descriptor_t *d = (descriptor_t*)descriptor_region; + (void*)(d+1) <= (descriptor_region + PAGE_SIZE); + d++) { + add_unused_descriptor(d); + } + } + try_anyway: + // even if we don't have enough unused descriptors, we might find + // a free region that has exactly the right size and therefore + // does not require splitting, so we try the allocation in all cases + result = region_alloc_inner(size, type, pf, false); + + mutex_unlock(&ra_mutex); + return result; +} + +region_info_t *find_region(void* addr) { + region_info_t *r = 0; + mutex_lock(&ra_mutex); + + descriptor_t *d = find_used_region(addr); + if (d != 0) r = &d->used.i; + + mutex_unlock(&ra_mutex); + return r; +} + +// ========================================================= // +// HELPER FUNCTIONS : SIMPLE PF HANDLERS ; FREEING FUNCTIONS // +// ========================================================= // + +void default_allocator_pf_handler(pagedir_t *pd, struct region_info *r, void* addr) { + ASSERT(pd_get_frame(addr) == 0); // if error is of another type (RO, protected), we don't do anyting + + uint32_t f = frame_alloc(1); + if (f == 0) PANIC("Out Of Memory"); + + int error = pd_map_page(addr, f, 1); + if (error) PANIC("Could not map frame (OOM)"); +} + +void region_free_unmap_free(void* ptr) { + region_info_t *i = find_region(ptr); + ASSERT(i != 0); + + for (void* x = i->addr; x < i->addr + i->size; x += PAGE_SIZE) { + uint32_t f = pd_get_frame(x); + if (f != 0) { + pd_unmap_page(x); + frame_free(f, 1); + } + } + region_free(ptr); +} + +void region_free_unmap(void* ptr) { + region_info_t *i = find_region(ptr); + ASSERT(i != 0); + + for (void* x = i->addr; x < i->addr + i->size; x += PAGE_SIZE) { + pd_unmap_page(x); + } + region_free(ptr); +} + +// =========================== // +// DEBUG LOG PRINTING FUNCTION // +// =========================== // + +void dbg_print_region_info() { + mutex_lock(&ra_mutex); + + 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 %s\n", d->used.i.addr, d->used.i.addr + d->used.i.size, d->used.i.type); + ASSERT(d != d->used.next_by_addr); + } + dbg_printf("\\\n"); + + mutex_unlock(&ra_mutex); +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/core/sys.c b/src/kernel/core/sys.c new file mode 100644 index 0000000..2b77463 --- /dev/null +++ b/src/kernel/core/sys.c @@ -0,0 +1,25 @@ +#include +#include + + +// Kernel panic and kernel assert failure + +static void panic_do(const char* type, const char *msg, const char* file, int line) { + asm volatile("cli;"); + dbg_printf("/\n| %s:\t%s\n", type, msg); + dbg_printf("| File: \t%s:%i\n", file, line); + dbg_printf("| System halted -_-'\n"); + dbg_printf("\\---------------------------------------------------------/"); + BOCHS_BREAKPOINT; + asm volatile("hlt"); +} + +void panic(const char* message, const char* file, int line) { + panic_do("PANIC", message, file, line); +} + +void panic_assert(const char* assertion, const char* file, int line) { + panic_do("ASSERT FAILED", assertion, file, line); +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/core/thread.c b/src/kernel/core/thread.c new file mode 100644 index 0000000..7f0bb5b --- /dev/null +++ b/src/kernel/core/thread.c @@ -0,0 +1,208 @@ +#include +#include +#include +#include + +#include +#include + +void save_context_and_enter_scheduler(saved_context_t *ctx); +void irq0_save_context_and_enter_scheduler(saved_context_t *ctx); +void resume_context(saved_context_t *ctx); + +thread_t *current_thread = 0; + +// ====================== // +// THE PROGRAMMABLE TIMER // +// ====================== // + +void set_pit_frequency(uint32_t freq) { + uint32_t divisor = 1193180 / freq; + ASSERT(divisor < 65536); // must fit on 16 bits + + uint8_t l = (divisor & 0xFF); + uint8_t h = ((divisor >> 8) & 0xFF); + + outb(0x43, 0x36); + outb(0x40, l); + outb(0x40, h); +} + +// ============================= // +// HELPER : IF FLAG MANIPULATION // +// ============================= // + +static inline bool disable_interrupts() { + uint32_t eflags; + asm volatile("pushf; pop %0" : "=r"(eflags)); + asm volatile("cli"); + return (eflags & EFLAGS_IF) != 0; +} + +static inline void resume_interrupts(bool st) { + if (st) asm volatile("sti"); +} + +// ================== // +// THE TASK SCHEDULER // +// ================== // + +static thread_t *queue_first_thread = 0, *queue_last_thread = 0; + +void enqueue_thread(thread_t *t, bool just_ran) { + ASSERT(t->state == T_STATE_RUNNING); + if (queue_first_thread == 0) { + queue_first_thread = queue_last_thread = t; + t->next_in_queue = 0; + } else if (just_ran) { + t->next_in_queue = 0; + queue_last_thread->next_in_queue = t; + queue_last_thread = t; + } else { + t->next_in_queue = queue_first_thread; + queue_first_thread = t; + } +} + +thread_t* dequeue_thread() { + thread_t *t = queue_first_thread; + if (t == 0) return 0; + + queue_first_thread = t->next_in_queue; + if (queue_first_thread == 0) queue_last_thread = 0; + + return t; +} + +// ================ // +// THE TASKING CODE // +// ================ // + +void run_scheduler() { + // At this point, interrupts are disabled + // This function is expected NEVER TO RETURN + + if (current_thread != 0 && current_thread->state == T_STATE_RUNNING) { + enqueue_thread(current_thread, true); + } + + current_thread = dequeue_thread(); + if (current_thread != 0) { + resume_context(¤t_thread->ctx); + } else { + // Wait for an IRQ + asm volatile("sti; hlt"); + // At this point an IRQ has happenned + // and has been processed. Loop around. + run_scheduler(); + ASSERT(false); + } +} + +static void run_thread(void (*entry)(void*), void* data) { + ASSERT(current_thread->state == T_STATE_RUNNING); + + switch_pagedir(get_kernel_pagedir()); + + asm volatile("sti"); + entry(data); + + current_thread->state = T_STATE_FINISHED; + // TODO : add job for deleting the thread, or whatever + yield(); // expected never to return! + ASSERT(false); +} +thread_t *new_thread(entry_t entry, void* data) { + thread_t *t = (thread_t*)malloc(sizeof(thread_t)); + if (t == 0) return 0; + + void* stack = region_alloc(KPROC_STACK_SIZE, "Stack", 0); + if (stack == 0) { + free(t); + return 0; + } + + for (void* i = stack + PAGE_SIZE; i < stack + KPROC_STACK_SIZE; i += PAGE_SIZE) { + uint32_t f = frame_alloc(1); + if (f == 0) { + region_free_unmap_free(stack); + free(t); + return 0; + } + pd_map_page(i, f, true); + } + + t->stack_region = find_region(stack); + + t->ctx.esp = (uint32_t*)(t->stack_region->addr + t->stack_region->size); + *(--t->ctx.esp) = (uint32_t)data; // push second argument : data + *(--t->ctx.esp) = (uint32_t)entry; // push first argument : entry point + *(--t->ctx.esp) = 0; // push invalid return address (the run_thread function never returns) + + t->ctx.eip = (void(*)())run_thread; + t->state = T_STATE_PAUSED; + + t->current_pd_d = get_kernel_pagedir(); + + t->proc = 0; // used by L1 functions + + return t; +} + +// ========== // +// SETUP CODE // +// ========== // + +static void irq0_handler(registers_t *regs) { + if (current_thread != 0) + irq0_save_context_and_enter_scheduler(¤t_thread->ctx); +} +void threading_setup(entry_t cont, void* arg) { + set_pit_frequency(TASK_SWITCH_FREQUENCY); + idt_set_irq_handler(IRQ0, irq0_handler); + + thread_t *t = new_thread(cont, arg); + ASSERT(t != 0); + + resume_thread(t, false); + + run_scheduler(); // never returns + ASSERT(false); +} + +// ======================= // +// TASK STATE MANIPULATION // +// ======================= // + +void yield() { + if (current_thread == 0) { + // might happen before threading is initialized + // (but should not...) + dbg_printf("Warning: probable deadlock.\n"); + } else { + save_context_and_enter_scheduler(¤t_thread->ctx); + } +} + +void pause() { + bool st = disable_interrupts(); + + current_thread->state = T_STATE_PAUSED; + save_context_and_enter_scheduler(¤t_thread->ctx); + + resume_interrupts(st); +} + +void resume_thread(thread_t *thread, bool run_at_once) { + bool st = disable_interrupts(); + + if (thread->state == T_STATE_PAUSED) { + thread->state = T_STATE_RUNNING; + enqueue_thread(thread, false); + } + if (run_at_once) yield(); + + resume_interrupts(st); +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/include/config.h b/src/kernel/include/config.h new file mode 120000 index 0000000..93307d9 --- /dev/null +++ b/src/kernel/include/config.h @@ -0,0 +1 @@ +../config.h \ No newline at end of file diff --git a/src/kernel/include/dbglog.h b/src/kernel/include/dbglog.h new file mode 100644 index 0000000..8bf6962 --- /dev/null +++ b/src/kernel/include/dbglog.h @@ -0,0 +1,8 @@ +#pragma once + +#include +#include + +void dbglog_setup(); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/include/frame.h b/src/kernel/include/frame.h new file mode 100644 index 0000000..9ffafb3 --- /dev/null +++ b/src/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/src/kernel/include/gdt.h b/src/kernel/include/gdt.h new file mode 100644 index 0000000..a62d0db --- /dev/null +++ b/src/kernel/include/gdt.h @@ -0,0 +1,17 @@ +#pragma once + +#include +#include + +/* The GDT is one of the x86's descriptor tables. It is used for memory segmentation. + Here, we don't use segmentation to separate processes from one another (this is done with paging). + We only use segmentation to make the difference between kernel mode (ring 3) and user mode (ring 0) */ + +void gdt_init(); + +#define K_CODE_SEGMENT 0x08 +#define K_DATA_SEGMENT 0x10 +#define U_CODE_SEGMENT 0x18 +#define U_DATA_SEGMENT 0x20 + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/include/idt.h b/src/kernel/include/idt.h new file mode 100644 index 0000000..8e84cea --- /dev/null +++ b/src/kernel/include/idt.h @@ -0,0 +1,79 @@ +#pragma once + +/* The IDT is the system descriptor table that tells the CPU what to do when an interrupt fires. + There are three categories of interrupts : + - Exceptions ; eg page fault, divide by 0 + - IRQ : interrupts caused by hardware + - System calls : when an applications asks the system to do something */ + +#include + +#define IRQ0 0 +#define IRQ1 1 +#define IRQ2 2 +#define IRQ3 3 +#define IRQ4 4 +#define IRQ5 5 +#define IRQ6 6 +#define IRQ7 7 +#define IRQ8 8 +#define IRQ9 9 +#define IRQ10 10 +#define IRQ11 11 +#define IRQ12 12 +#define IRQ13 13 +#define IRQ14 14 +#define IRQ15 15 + +#define EX_DIVIDE_ERROR 0 // No error code +#define EX_DEBUG 1 // No error code +#define EX_NMI_INTERRUPT 2 // No error code +#define EX_BREAKPOINT 3 // No error code +#define EX_OVERFLOW 4 // No error code +#define EX_BOUND_RANGE_EXCEDEED 5 // No error code +#define EX_INVALID_OPCODE 6 // No error code +#define EX_DEVICE_NOT_AVAILABLE 7 // No error code +#define EX_DOUBLE_FAULT 8 // Yes (Zero) +#define EX_COPROCESSOR_SEGMENT_OVERRUN 9 // No error code +#define EX_INVALID_TSS 10 // Yes +#define EX_SEGMENT_NOT_PRESENT 11 // Yes +#define EX_STACK_SEGMENT_FAULT 12 // Yes +#define EX_GENERAL_PROTECTION 13 // Yes +#define EX_PAGE_FAULT 14 // Yes +#define EX_INTEL_RESERVED_1 15 // No +#define EX_FLOATING_POINT_ERROR 16 // No +#define EX_ALIGNEMENT_CHECK 17 // Yes (Zero) +#define EX_MACHINE_CHECK 18 // No +#define EX_INTEL_RESERVED_2 19 // No +#define EX_INTEL_RESERVED_3 20 // No +#define EX_INTEL_RESERVED_4 21 // No +#define EX_INTEL_RESERVED_5 22 // No +#define EX_INTEL_RESERVED_6 23 // No +#define EX_INTEL_RESERVED_7 24 // No +#define EX_INTEL_RESERVED_8 25 // No +#define EX_INTEL_RESERVED_9 26 // No +#define EX_INTEL_RESERVED_10 27 // No +#define EX_INTEL_RESERVED_11 28 // No +#define EX_INTEL_RESERVED_12 29 // No +#define EX_INTEL_RESERVED_13 30 // No +#define EX_INTEL_RESERVED_14 31 // No + +#define EFLAGS_IF (0x1 << 9) + +typedef struct registers { + uint32_t ds; // Data segment selector + uint32_t edi, esi, ebp, useless_esp, ebx, edx, ecx, eax; // Pushed by pusha. + uint32_t int_no, err_code; // Interrupt number and error code (if applicable) + uint32_t eip, cs, eflags, esp, ss; // Pushed by the processor automatically. +} registers_t; + +typedef void (*isr_handler_t)(registers_t*); + +void idt_init(); + +void idt_set_ex_handler(int number, isr_handler_t func); //Set exception handler +void idt_set_irq_handler(int number, isr_handler_t func); //Set IRQ handler + +void dbg_dump_registers(registers_t*); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/include/kmalloc.h b/src/kernel/include/kmalloc.h new file mode 100644 index 0000000..d4a9272 --- /dev/null +++ b/src/kernel/include/kmalloc.h @@ -0,0 +1,11 @@ +#pragma once + +#include +#include + +// Kernel memory allocator : one slab allocator for shared memory +// Thread-safe. + +void kmalloc_setup(); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/include/multiboot.h b/src/kernel/include/multiboot.h new file mode 100644 index 0000000..581337a --- /dev/null +++ b/src/kernel/include/multiboot.h @@ -0,0 +1,63 @@ +#pragma once + +#define MULTIBOOT_HEADER_MAGIC 0x1BADB002 +#define MULTIBOOT_BOOTLOADER_MAGIC 0x2BADB002 + +struct multiboot_header_t{ + unsigned long magic; + unsigned long flags; + unsigned long checksum; + unsigned long header_addr; + unsigned long load_addr; + unsigned long load_end_addr; + unsigned long bss_end_addr; + unsigned long entry_addr; +}; + +struct aout_symbol_table_t { + unsigned long tabsize; + unsigned long strsize; + unsigned long addr; + unsigned long reserved; +}; + +struct elf_section_header_table_t { + unsigned long num; + unsigned long size; + unsigned long addr; + unsigned long shndx; +}; + +struct multiboot_info_t { + unsigned long flags; + unsigned long mem_lower; + unsigned long mem_upper; + unsigned long boot_device; + unsigned long cmdline; + unsigned long mods_count; + unsigned long mods_addr; + union { + struct aout_symbol_table_t aout_sym; + struct elf_section_header_table_t elf_sec; + } u; + unsigned long mmap_length; + unsigned long mmap_addr; +}; + +struct module_t { + unsigned long mod_start; + unsigned long mod_end; + unsigned long string; + unsigned long reserved; +}; + +struct memory_map_t { + unsigned long size; + unsigned long base_addr_low; + unsigned long base_addr_high; + unsigned long length_low; + unsigned long length_high; + unsigned long type; +}; + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/include/paging.h b/src/kernel/include/paging.h new file mode 100644 index 0000000..44014a2 --- /dev/null +++ b/src/kernel/include/paging.h @@ -0,0 +1,31 @@ +#pragma once + +#include +#include + +struct page_directory; +typedef struct page_directory pagedir_t; + + +void paging_setup(void* kernel_data_end); + +pagedir_t *get_current_pagedir(); +pagedir_t *get_kernel_pagedir(); + +void switch_pagedir(pagedir_t *pd); + +// these functions are always relative to the currently mapped page directory +uint32_t pd_get_frame(void* vaddr); // get physical frame for virtual address +int pd_map_page(void* vaddr, uint32_t frame_id, bool rw); // returns nonzero on error +void pd_unmap_page(void* vaddr); // does nothing if page not mapped + +// Note on concurrency : we expect that multiple threads will not try to map/unmap +// pages in the same region at the same time. It can nevertheless happen that +// several threads try to map pages that belong to the same 4M-section, and in that +// case both might require the allocation of a new PT at the same location. These +// cases are well-handled (the pagedir_t type contains a mutex used for this) + +pagedir_t *create_pagedir(); // returns zero on error +void delete_pagedir(pagedir_t *pd); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/include/process.h b/src/kernel/include/process.h new file mode 100644 index 0000000..00ed1d7 --- /dev/null +++ b/src/kernel/include/process.h @@ -0,0 +1,43 @@ +#pragma once + +// Things described in this file are essentially a public interface +// All implementation details are hidden in process.c + +#include + +#include +#include + +#define PW_NOT_WAITING 0 +#define PW_WAIT_ANY_MSG 1 +#define PW_WAIT_MSG_ON_CHAN 2 + +#define PROCESS_MAILBOX_SIZE 42 + +typedef int chan_id_t; + +typedef struct chan_pair { + chan_id_t fst, snd; +} chan_pair_t; + +typedef struct message { + buffer_t *data; + chan_id_t chan_id; +} message_t; + +struct process; +typedef struct process process_t; + +process_t *new_process(entry_t entry, void* data, chan_pair_t *give_chans); + +chan_pair_t new_chan(); // not used very often, but still usefull +chan_id_t unbox_chan(chan_id_t chan, chan_id_t subchan); +void detach_chan(chan_id_t chan); // chan ID is freed + +int send_message(chan_id_t chan, buffer_t *msg); // nonnull on error (recipient queue is full) + +size_t await_message(); // returns the size of the first message to come +size_t await_message_on_chan(chan_id_t chan); // returns the size of the first message to come +message_t get_message(); // gets the first message in the queue (or nothing when queue is empty) + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/include/region.h b/src/kernel/include/region.h new file mode 100644 index 0000000..1fef582 --- /dev/null +++ b/src/kernel/include/region.h @@ -0,0 +1,38 @@ +#pragma once + +// Kernel virtual memory region allocator + +// This is entirely thread-safe + +#include +#include + +struct region_info; +typedef void (*page_fault_handler_t)(pagedir_t *pd, struct region_info *r, void* addr); + +typedef struct region_info { + void* addr; + size_t size; + char* type; + page_fault_handler_t pf; +} region_info_t; + +void region_allocator_init(void* kernel_data_end); + +void* region_alloc(size_t size, char* type, page_fault_handler_t pf); // returns 0 on error +region_info_t *find_region(void* addr); +void region_free(void* addr); + +// some usefull PF handlers +// default_allocator_pf_handler : just allocates new frames on page faults +void default_allocator_pf_handler(pagedir_t *pd, struct region_info *r, void* addr); + +// some functions for freeing regions and frames +// region_free_unmap_free : deletes a region and frees all frames that were mapped in it +void region_free_unmap_free(void* addr); +// region_free_unmap : deletes a region and unmaps all frames that were mapped in it, without freeing them +void region_free_unmap(void* addr); + +void dbg_print_region_info(); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/include/sys.h b/src/kernel/include/sys.h new file mode 100644 index 0000000..29735fa --- /dev/null +++ b/src/kernel/include/sys.h @@ -0,0 +1,53 @@ +#pragma once + +#include // common header +#include + +static inline void outb(uint16_t port, uint8_t value) { + asm volatile("outb %1, %0" : : "dN"(port), "a"(value)); +} + +static inline void outw(uint16_t port, uint16_t value) { + asm volatile("outw %1, %0" : : "dN"(port), "a"(value)); +} + +static inline uint8_t inb(uint16_t port) { + uint8_t ret; + asm volatile("inb %1, %0" : "=a"(ret) : "dN"(port)); + return ret; +} + +static inline uint16_t inw(uint16_t port) { + uint16_t ret; + asm volatile("inw %1, %0" : "=a"(ret) : "dN"(port)); + return ret; +} + +static inline void invlpg(void* addr) { + asm volatile("invlpg (%0)" : : "r"(addr) : "memory"); +} + +#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 PAGE_SHIFT 12 +#define PT_SHIFT 10 +// PAGE_SHIFT + PT_SHIFT + PT_SHIFT = 32 +#define N_PAGES_IN_PT 1024 +#define PD_MIRROR_ADDR 0xFFC00000 // last 4MB used for PD mirroring +#define LAST_KERNEL_ADDR PD_MIRROR_ADDR +#define FIRST_KERNEL_PT (K_HIGHHALF_ADDR >> (PAGE_SHIFT+PT_SHIFT)) // must be 768 + +#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/src/kernel/include/thread.h b/src/kernel/include/thread.h new file mode 100644 index 0000000..757ba00 --- /dev/null +++ b/src/kernel/include/thread.h @@ -0,0 +1,46 @@ +#pragma once + +#include +#include +#include + +#define T_STATE_RUNNING 1 +#define T_STATE_PAUSED 2 +#define T_STATE_FINISHED 3 + +#define KPROC_STACK_SIZE 0x8000 // 8Kb + +#define TASK_SWITCH_FREQUENCY 100 // in herz + +typedef struct saved_context { + uint32_t *esp; + void (*eip)(); +} saved_context_t; + +struct process; +typedef struct thread { + saved_context_t ctx; + pagedir_t *current_pd_d; + + uint32_t state; + + region_info_t *stack_region; + + struct process *proc; // process : L1 data structure + + struct thread *next_in_queue; +} thread_t; + +typedef void (*entry_t)(void*); + +void threading_setup(entry_t cont, void* data); // never returns +thread_t *new_thread(entry_t entry, void* data); // thread is PAUSED, and must be resume_thread'ed + +extern thread_t *current_thread; + +void yield(); +void pause(); + +void resume_thread(thread_t *thread, bool run_at_once); + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/linker.ld b/src/kernel/linker.ld new file mode 100644 index 0000000..1203950 --- /dev/null +++ b/src/kernel/linker.ld @@ -0,0 +1,43 @@ +ENTRY (loader) + +SECTIONS{ + k_highhalf_addr = 0xC0000000; + + . = 0x00100000; + + .setup : { + *(.setup) + } + + . += k_highhalf_addr; + + .text : AT(ADDR(.text) - k_highhalf_addr) { + *(.text) + } + + .rodata ALIGN (0x1000) : AT(ADDR(.rodata) - k_highhalf_addr) { + *(.rodata) + } + + .data ALIGN (0x1000) : AT(ADDR(.data) - k_highhalf_addr) { + start_ctors = .; + *(.ctor*) + end_ctors = .; + start_dtors = .; + *(.dtor*) + end_dtors = .; + *(.data) + *(.locks) + } + + .bss : AT(ADDR(.bss) - k_highhalf_addr) { + sbss = .; + *(COMMON) + *(.bss) + ebss = .; + } + + k_end_addr = .; +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/user/process.c b/src/kernel/user/process.c new file mode 100644 index 0000000..7519dae --- /dev/null +++ b/src/kernel/user/process.c @@ -0,0 +1,30 @@ +#include +#include + +typedef struct process { + thread_t *thread; + int pid; + + mutex_t com_mutex; + + hashtbl_t *chans; + chan_id_t next_chan_id; + + message_t mbox[PROCESS_MAILBOX_SIZE]; + int mbox_size; // number of messages in queue + int mbox_first; // first message in queue (circular buffer) + + // a process can be in several waiting states : + // - wait for any message + // - wait for a message on a particular channel + // in this case, if a message is pushed on this particular channel, + // then it is put in front of the queue, so that it is the next message read + // (it is guaranteed that doing await_message_on_chan() immediately followed by get_message() + // gets the message whose size was returned by await_...) + int wait_state; + chan_id_t wait_chan_id; // when waiting for a message on a particular channel +} process_t; + +int push_message(process_t *proc, message_t msg); // nonnull on error (process queue is full) + +/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/rules.make b/src/rules.make new file mode 100644 index 0000000..e3840dd --- /dev/null +++ b/src/rules.make @@ -0,0 +1,34 @@ + +AS = nasm +ASFLAGS = -felf -g + +CC = i586-elf-gcc +CFLAGS += -ffreestanding -O2 -std=gnu99 -Wall -Wextra -I . -I ./include -g -Wno-unused-parameter +# CXX = i586-elf-g++ +# CXFLAGS = -ffreestanding -O3 -Wall -Wextra -I . -I ./include -fno-exceptions -fno-rtti +LD = i586-elf-gcc +LDFLAGS += -ffreestanding -O2 -nostdlib -lgcc + +all: $(OUT) + +%.bin: $(OBJ) + $(LD) $(LDFLAGS) -o $@ $^ $(LIB) + +%.lib: $(OBJ) + $(LD) $(LDFLAGS) -r -o $@ $^ $(LIB) + +%.o: %.s + $(AS) $(ASFLAGS) -o $@ $< + +%.o: %.c + $(CC) -c $< -o $@ $(CFLAGS) + +# %.o: %.cpp +# $(CXX) -c $< -o $@ $(CXFLAGS) + +clean: + rm */*.o || true +mrproper: clean + rm $(OUT) || true + +rebuild: mrproper all diff --git a/src/tests/Makefile b/src/tests/Makefile new file mode 100644 index 0000000..4a21edf --- /dev/null +++ b/src/tests/Makefile @@ -0,0 +1,2 @@ +slab_test.bin: slab_test.c ../include/slab_alloc.h ../lib/slab_alloc.c + gcc -m32 -o $@ -std=c99 -I ../include slab_test.c ../lib/slab_alloc.c diff --git a/src/tests/slab_test.c b/src/tests/slab_test.c new file mode 100644 index 0000000..747c785 --- /dev/null +++ b/src/tests/slab_test.c @@ -0,0 +1,44 @@ +#include +#include +#include + +slab_type_t slab_sizes[] = { + { "8B obj", 8, 1 }, + { "16B obj", 16, 2 }, + { "32B obj", 32, 2 }, + { "64B obj", 64, 2 }, + { "128B obj", 128, 2 }, + { "256B obj", 256, 4 }, + { "512B obj", 512, 4 }, + { "1KB obj", 1024, 8 }, + { "2KB obj", 2048, 8 }, + { "4KB obj", 4096, 16 }, + { 0, 0, 0 } +}; + + +int main(int argc, char *argv[]) { + mem_allocator_t *a = + create_slab_allocator(slab_sizes, malloc, free); + + const int m = 10000; + uint32_t* ptr[m]; + for (int i = 0; i < m; i++) { + size_t s = 1 << ((i * 7) % 12 + 2); + ptr[i] = (uint32_t*)slab_alloc(a, s); + ASSERT(ptr[i] != 0); + *ptr[i] = ((i * 2117) % (1<<30)); + printf("Alloc %i : 0x%p\n", s, ptr[i]); + } + for (int i = 0; i < m; i++) { + for (int j = i; j < m; j++) { + ASSERT(*ptr[j] == (j * 2117) % (1<<30)); + } + slab_free(a, ptr[i]); + } + destroy_slab_allocator(a); + + return 0; +} + +/* vim: set ts=4 sw=4 tw=0 noet :*/ -- cgit v1.2.3