From ff27e3d5ca61fb6234b0876dc3368d0e5dfc5a95 Mon Sep 17 00:00:00 2001 From: Alex Auvolat Date: Sat, 6 Dec 2014 18:39:12 +0100 Subject: Trying to track an annoying bug. --- .gitignore | 1 + kernel/Makefile | 2 +- kernel/config.h | 1 - kernel/include/idt.h | 2 ++ kernel/include/slab_alloc.h | 9 ++++++- kernel/l0/idt.c | 15 ++++++----- kernel/l0/kmain.c | 60 +++++++++++++++++++++++++----------------- kernel/l0/paging.c | 31 ++++++++++++++++++++-- kernel/l0/sys.c | 1 + kernel/lib/slab_alloc.c | 62 +++++++++++++++++++++++++++++++++----------- kernel/lib_tests/Makefile | 2 ++ kernel/lib_tests/slab_test.c | 42 ++++++++++++++++++++++++++++++ run_bochs_debug.sh | 2 +- run_qemu.sh | 2 +- run_qemu_debug.sh | 4 +-- 15 files changed, 182 insertions(+), 54 deletions(-) create mode 100644 kernel/lib_tests/Makefile create mode 100644 kernel/lib_tests/slab_test.c diff --git a/.gitignore b/.gitignore index 684f1ec..3593c08 100644 --- a/.gitignore +++ b/.gitignore @@ -3,6 +3,7 @@ *.o *.bin +*.map *.iso cdrom/ diff --git a/kernel/Makefile b/kernel/Makefile index 2adacbc..0db3d6b 100644 --- a/kernel/Makefile +++ b/kernel/Makefile @@ -7,7 +7,7 @@ CFLAGS = -ffreestanding -O2 -std=gnu99 -Wall -Wextra -I . -I ./include -g -Wno-u # 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 +LDFLAGS = -T linker.ld -ffreestanding -O2 -nostdlib -lgcc -Xlinker -Map=kernel.map OBJ = lib/string.o lib/printf.o lib/slab_alloc.o \ l0/loader.o l0/kmain.o l0/dbglog.o l0/sys.o \ diff --git a/kernel/config.h b/kernel/config.h index d198295..2de43af 100644 --- a/kernel/config.h +++ b/kernel/config.h @@ -13,7 +13,6 @@ #error "This kernel needs to be compiled with a ix86-elf compiler" #endif - #define K_HIGHHALF_ADDR ((size_t)0xC0000000) #define OS_NAME "macrO.Scope" diff --git a/kernel/include/idt.h b/kernel/include/idt.h index ba344c9..e054ed5 100644 --- a/kernel/include/idt.h +++ b/kernel/include/idt.h @@ -88,4 +88,6 @@ 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/slab_alloc.h b/kernel/include/slab_alloc.h index 5c575ba..5355a66 100644 --- a/kernel/include/slab_alloc.h +++ b/kernel/include/slab_alloc.h @@ -8,7 +8,14 @@ #include #include -#include +#if defined(__linux__) +//redefine necessary stuff +#include +#define ASSERT assert +#define PAGE_SIZE 0x1000 +#else +#include // this is macroscope +#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 diff --git a/kernel/l0/idt.c b/kernel/l0/idt.c index 3bfcfc5..2d7b3bc 100644 --- a/kernel/l0/idt.c +++ b/kernel/l0/idt.c @@ -66,12 +66,6 @@ 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) { - /*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);*/ - if (ex_handlers[regs->int_no] != 0) { ex_handlers[regs->int_no](regs); } @@ -194,4 +188,13 @@ void idt_set_ex_handler(int number, isr_handler_t 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/kmain.c b/kernel/l0/kmain.c index a935c9c..8cb370a 100644 --- a/kernel/l0/kmain.c +++ b/kernel/l0/kmain.c @@ -11,26 +11,37 @@ #include +extern char 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 test_pf_handler(pagedir_t *pd, region_info_t *i, void* addr) { - dbg_printf("0x%p", addr); + dbg_printf(" {0x%p", addr); uint32_t f = frame_alloc(1); if (f == 0) PANIC("Out Of Memory"); - dbg_printf(" -> %i", f); + dbg_printf(" -> %i} ", f); int error = pd_map_page(addr, f, 1); if (error) PANIC("Could not map frame (OOM)"); } void* page_alloc_fun_for_kmalloc(size_t bytes) { - return region_alloc(bytes, REGION_T_CORE_HEAP, test_pf_handler); + void* addr = region_alloc(bytes, REGION_T_CORE_HEAP, test_pf_handler); + return addr; } void page_free_fun_for_kmalloc(void* ptr) { + region_info_t *i = find_region(ptr); + 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); } slab_type_t slab_sizes[] = { @@ -47,8 +58,6 @@ slab_type_t slab_sizes[] = { { 0, 0, 0 } }; - -extern char k_end_addr; // defined in linker script : 0xC0000000 plus kernel stuff void kmain(struct multiboot_info_t *mbd, int32_t mb_magic) { dbglog_setup(); @@ -66,7 +75,6 @@ void kmain(struct multiboot_info_t *mbd, int32_t mb_magic) { size_t total_ram = ((mbd->mem_upper + mbd->mem_lower) * 1024); dbg_printf("Total ram: %d Kb\n", total_ram / 1024); - // paging_init(totalRam); // used for allocation of data structures before malloc is set up // a pointer to this pointer is passed to the functions that might have @@ -80,6 +88,8 @@ void kmain(struct multiboot_info_t *mbd, int32_t mb_magic) { paging_setup(kernel_data_end); dbg_printf("Paging seems to be working!\n"); + BOCHS_BREAKPOINT; + region_allocator_init(kernel_data_end); dbg_print_region_stats(); @@ -107,9 +117,10 @@ void kmain(struct multiboot_info_t *mbd, int32_t mb_magic) { region_free(s); dbg_printf("Freed region 0x%p\n", s); dbg_print_region_stats(); + BOCHS_BREAKPOINT; // allocate a big region and try to write into it - const size_t n = 1000; + const size_t n = 200; void* p0 = region_alloc(n * PAGE_SIZE, REGION_T_HW, test_pf_handler); for (size_t i = 0; i < n; i++) { uint32_t *x = (uint32_t*)(p0 + i * PAGE_SIZE); @@ -119,43 +130,44 @@ void kmain(struct multiboot_info_t *mbd, int32_t mb_magic) { x[1] = (i * 20422) % 122; dbg_printf("]\n", i); } + BOCHS_BREAKPOINT; // unmap memory for (size_t i = 0; i < n; i++) { - uint32_t *x = (uint32_t*)(p0 + i * PAGE_SIZE); + void* p = p0 + i * PAGE_SIZE; + uint32_t *x = (uint32_t*)p; ASSERT(x[1] == (i * 20422) % 122); - uint32_t f = pd_get_frame(x); + uint32_t f = pd_get_frame(p); ASSERT(f != 0); - pd_unmap_page(x); + pd_unmap_page(p); + ASSERT(pd_get_frame(p) == 0); frame_free(f, 1); } region_free(s); + BOCHS_BREAKPOINT; // TEST SLAB ALLOCATOR!!! mem_allocator_t *a = create_slab_allocator(slab_sizes, page_alloc_fun_for_kmalloc, page_free_fun_for_kmalloc); dbg_printf("Created slab allocator at 0x%p\n", a); - const int m = 100; - void* ptr[m]; - for (int i = 0; i < m; i++) { - size_t s = 1 << ((i * 7) % 12 + 1); - ptr[i] = slab_alloc(a, s); - dbg_printf("Alloc %i : 0x%p\n", s, ptr[i]); - dbg_print_region_stats(); - } - for (int i = 0; i < m; i++) { - slab_free(a, ptr[m - i - 1]); - } dbg_print_region_stats(); + const int m = 10000; + uint16_t* ptr[m]; for (int i = 0; i < m; i++) { - size_t s = 1 << ((i * 7) % 12 + 1); - ASSERT(slab_alloc(a, s) == ptr[i]); + size_t s = 1 << ((i * 7) % 12 + 2); + ptr[i] = (uint16_t*)slab_alloc(a, s); + ASSERT((void*)ptr[i] >= kernel_data_end && (size_t)ptr[i] < 0xFFC00000); + *ptr[i] = ((i * 211) % 1024); + dbg_printf("Alloc %i : 0x%p\n", s, ptr[i]); } dbg_print_region_stats(); for (int i = 0; i < m; i++) { - slab_free(a, ptr[m - i - 1]); + for (int j = i; j < m; j++) { + ASSERT(*ptr[j] == (j * 211) % 1024); + } + slab_free(a, ptr[i]); } dbg_print_region_stats(); dbg_printf("Destroying slab allocator.\n"); diff --git a/kernel/l0/paging.c b/kernel/l0/paging.c index ca217c6..adb076c 100644 --- a/kernel/l0/paging.c +++ b/kernel/l0/paging.c @@ -58,13 +58,32 @@ void page_fault_handler(registers_t *regs) { return; } + if ((size_t)vaddr >= PD_MIRROR_ADDR) { + dbg_printf("Fault on access to mirrorred PD at 0x%p\n", vaddr); + + uint32_t x = (size_t)vaddr - PD_MIRROR_ADDR; + uint32_t page = (x % PAGE_SIZE) / 4; + uint32_t pt = x / PAGE_SIZE; + dbg_printf("For pt 0x%p, page 0x%p -> addr 0x%p\n", pt, page, ((pt * 1024) + page) * PAGE_SIZE); + + for (int i = 0; i < N_PAGES_IN_PT; i++) { + dbg_printf("%i. 0x%p\n", i, kernel_pd.page[i]); + } + + dbg_dump_registers(regs); + dbg_print_region_stats(); + 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); PANIC("Unhandled kernel space page fault"); } i->pf(current_pd_d, i, vaddr); @@ -149,6 +168,8 @@ 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); + pagetable_t *pd = ((size_t)vaddr >= K_HIGHHALF_ADDR ? &kernel_pd : current_pd); if (!pd->page[pt] & PTE_PRESENT) { @@ -159,12 +180,16 @@ int pd_map_page(void* vaddr, uint32_t frame_id, bool rw) { (new_pt_frame << PTE_FRAME_SHIFT) | PTE_PRESENT | PTE_RW; invlpg(¤t_pt[pt]); } + dbg_printf("[%p,%i,%i,", vaddr, pt, page); current_pt[pt].page[page] = - frame_id << PTE_FRAME_SHIFT + (frame_id << PTE_FRAME_SHIFT) | PTE_PRESENT | ((size_t)vaddr < K_HIGHHALF_ADDR ? PTE_USER : PTE_GLOBAL) | (rw ? PTE_RW : 0); + invlpg(vaddr); + + dbg_printf("]"); return 0; } @@ -177,7 +202,9 @@ void pd_unmap_page(void* vaddr) { if (!pd->page[pt] & PTE_PRESENT) return; if (!current_pt[pt].page[page] & PTE_PRESENT) return; - current_pt[pt].page[page] &= ~PTE_PRESENT; + + current_pt[pt].page[page] = 0; + invlpg(vaddr); // TODO (?) : if pagetable is completely empty, free it } diff --git a/kernel/l0/sys.c b/kernel/l0/sys.c index b388eba..2b77463 100644 --- a/kernel/l0/sys.c +++ b/kernel/l0/sys.c @@ -10,6 +10,7 @@ static void panic_do(const char* type, const char *msg, const char* file, int li dbg_printf("| File: \t%s:%i\n", file, line); dbg_printf("| System halted -_-'\n"); dbg_printf("\\---------------------------------------------------------/"); + BOCHS_BREAKPOINT; asm volatile("hlt"); } diff --git a/kernel/lib/slab_alloc.c b/kernel/lib/slab_alloc.c index 9ec39b0..d9efc4f 100644 --- a/kernel/lib/slab_alloc.c +++ b/kernel/lib/slab_alloc.c @@ -32,7 +32,7 @@ struct mem_allocator { const slab_type_t *types; slab_t *slabs; cache_t *first_free_region_descriptor; - cache_t *all_regions; + cache_t *all_caches, *all_other_regions;; page_alloc_fun_t alloc_fun; page_free_fun_t free_fun; @@ -49,8 +49,13 @@ void add_free_region_descriptor(mem_allocator_t *a, cache_t *c) { cache_t *take_region_descriptor(mem_allocator_t *a) { if (a->first_free_region_descriptor == 0) { - // TODO : allocate more descriptors (not complicated) - return 0; + void* p = a->alloc_fun(PAGE_SIZE); + if (p == 0) return 0; + + void* end = p + PAGE_SIZE; + for (cache_t *i = (cache_t*)p; i + 1 <= (cache_t*)end; i++) { + add_free_region_descriptor(a, i); + } } cache_t *x = a->first_free_region_descriptor; a->first_free_region_descriptor = x->next_region; @@ -76,7 +81,7 @@ mem_allocator_t* create_slab_allocator(const slab_type_t *types, page_alloc_fun_ mem_allocator_t *a = ptr.a; ptr.a++; - a->all_regions = 0; + a->all_caches = a->all_other_regions = 0; a->alloc_fun = af; a->free_fun = ff; @@ -99,11 +104,13 @@ mem_allocator_t* create_slab_allocator(const slab_type_t *types, page_alloc_fun_ static void stack_and_destroy_regions(page_free_fun_t ff, cache_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) { - stack_and_destroy_regions(a->free_fun, a->all_regions); + stack_and_destroy_regions(a->free_fun, a->all_caches); + stack_and_destroy_regions(a->free_fun, a->all_other_regions); a->free_fun(a); } @@ -140,8 +147,8 @@ void* slab_alloc(mem_allocator_t* a, size_t sz) { } ASSERT(fc->n_free_objs == cache_size / obj_size); - fc->next_region = a->all_regions; - a->all_regions = fc; + fc->next_region = a->all_caches; + a->all_caches = fc; fc->c.next_cache = a->slabs[i].first_cache; a->slabs[i].first_cache = fc; } @@ -167,8 +174,8 @@ void* slab_alloc(mem_allocator_t* a, size_t sz) { r->is_a_cache = 0; r->sr.region_size = sz; - r->next_region = a->all_regions; - a->all_regions = r; + r->next_region = a->all_other_regions; + a->all_other_regions = r; return (void*)r->region_addr; } @@ -186,7 +193,32 @@ void slab_free(mem_allocator_t* a, void* addr) { o->next = r->c.first_free_obj; r->c.first_free_obj = o; r->n_free_objs++; - // TODO : if cache is empty, free it + + 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->c.next_cache; + } else { + for (cache_t *it = a->slabs[i].first_cache; it->c.next_cache != 0; it = it->c.next_cache) { + if (it->c.next_cache == r) { + it->c.next_cache = r->c.next_cache; + break; + } + } + } + if (a->all_caches == r) { + a->all_caches = r->next_region; + } else { + for (cache_t *it = a->all_caches; it->next_region != 0; it = it->next_region) { + if (it->next_region == r) { + it->next_region = r->next_region; + break; + } + } + } + a->free_fun(r->region_addr); + add_free_region_descriptor(a, r); + } return; } } @@ -194,15 +226,15 @@ void slab_free(mem_allocator_t* a, void* addr) { // otherwise the block was directly allocated : look for it in regions. a->free_fun(addr); - ASSERT(a->all_regions != 0); + ASSERT(a->all_other_regions != 0); - if (a->all_regions->region_addr == addr) { - cache_t *r = a->all_regions; + if (a->all_other_regions->region_addr == addr) { + cache_t *r = a->all_other_regions; ASSERT(r->is_a_cache == 0); - a->all_regions = r->next_region; + a->all_other_regions = r->next_region; add_free_region_descriptor(a, r); } else { - for (cache_t *i = a->all_regions; i->next_region != 0; i = i->next_region) { + for (cache_t *i = a->all_other_regions; i->next_region != 0; i = i->next_region) { if (i->next_region->region_addr == addr) { cache_t *r = i->next_region; ASSERT(r->is_a_cache == 0); diff --git a/kernel/lib_tests/Makefile b/kernel/lib_tests/Makefile new file mode 100644 index 0000000..4a21edf --- /dev/null +++ b/kernel/lib_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/kernel/lib_tests/slab_test.c b/kernel/lib_tests/slab_test.c new file mode 100644 index 0000000..4bfc6b0 --- /dev/null +++ b/kernel/lib_tests/slab_test.c @@ -0,0 +1,42 @@ +#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; +} diff --git a/run_bochs_debug.sh b/run_bochs_debug.sh index 848feb5..df6c0d4 100755 --- a/run_bochs_debug.sh +++ b/run_bochs_debug.sh @@ -2,6 +2,6 @@ cd `dirname $0` -make -C kernel +make -C kernel || exit 1 ./make_cdrom.sh bochs -f bochs_debug.cfg -q diff --git a/run_qemu.sh b/run_qemu.sh index 8649d92..6c76909 100755 --- a/run_qemu.sh +++ b/run_qemu.sh @@ -2,5 +2,5 @@ cd `dirname $0` -make -C kernel +make -C kernel || exit 1 qemu-system-i386 -kernel kernel/kernel.bin -serial stdio -m 16 diff --git a/run_qemu_debug.sh b/run_qemu_debug.sh index b429471..71ee6d3 100755 --- a/run_qemu_debug.sh +++ b/run_qemu_debug.sh @@ -2,6 +2,6 @@ cd `dirname $0` -make -C kernel +make -C kernel || exit 1 qemu-system-i386 -kernel kernel/kernel.bin -serial stdio -s -S & -(sleep 0.1; gdb kernel.bin -x gdb_cmd) +(sleep 0.1; gdb kernel/kernel.bin -x gdb_cmd) -- cgit v1.2.3