diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/common/libkogata/region_alloc.c | 73 | ||||
| -rw-r--r-- | src/lib/include/stdio.h | 4 | ||||
| -rw-r--r-- | src/sysbin/giosrv/main.c | 2 | ||||
| -rw-r--r-- | src/sysbin/init/main.c | 2 | ||||
| -rw-r--r-- | src/sysbin/login/main.c | 1 | ||||
| -rw-r--r-- | src/sysbin/shell/main.c | 1 | ||||
| -rw-r--r-- | src/sysbin/terminal/main.c | 2 | ||||
| -rw-r--r-- | src/tests/ktests/region1/test.c | 19 | ||||
| -rwxr-xr-x | src/tests/ktests/run_qemu_test.sh | 2 | ||||
| -rw-r--r-- | src/tests/utests/malloc/test.c | 2 |
10 files changed, 77 insertions, 31 deletions
diff --git a/src/common/libkogata/region_alloc.c b/src/common/libkogata/region_alloc.c index 8594643..96a0f07 100644 --- a/src/common/libkogata/region_alloc.c +++ b/src/common/libkogata/region_alloc.c @@ -10,7 +10,6 @@ #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) - typedef union region_descriptor { struct { union region_descriptor *next; @@ -18,7 +17,8 @@ typedef union region_descriptor { struct { void* addr; size_t size; - union region_descriptor *next_by_size, *first_bigger; + union region_descriptor *next_by_size; + union region_descriptor *first_bigger; union region_descriptor *next_by_addr; } free; struct { @@ -91,19 +91,30 @@ void add_free_region(descriptor_t *d) { // Find position of region in address-ordered list // Possibly concatenate free region descriptor_t *i = first_free_region_by_addr; + if (i == 0) { + // we are the only free region, this is easy 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; + d->free.next_by_size = d->free.next_by_addr = 0; + d->free.first_bigger = 0; + return; - } else if (d->free.addr + d->free.size == i->free.addr) { + } + + if (d->free.addr + d->free.size == i->free.addr) { // concatenate d . i - remove_free_region(i); d->free.size += i->free.size; + + remove_free_region(i); add_unused_descriptor(i); - add_free_region(d); + + add_free_region(d); // restart from beginning return; - } else if (i->free.addr > d->free.addr) { + } + + if (i->free.addr > d->free.addr) { // insert before i d->free.next_by_addr = i; first_free_region_by_addr = d; @@ -112,29 +123,37 @@ void add_free_region(descriptor_t *d) { 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; + + remove_free_region(i); add_unused_descriptor(d); - add_free_region(i); + + add_free_region(i); // restart from beginning 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; + // this is where we want to add 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; + + remove_free_region(j); add_unused_descriptor(j); - add_free_region(d); + + add_free_region(d); // restart from beginning return; } else { // continue i = i->free.next_by_addr; } } + + d->free.next_by_addr = i->free.next_by_addr; + i->free.next_by_addr = d; } + // Now add it in size-ordered list i = first_free_region_by_size; ASSERT(i != 0); @@ -148,8 +167,9 @@ void add_free_region(descriptor_t *d) { 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; + 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; @@ -161,11 +181,25 @@ void add_free_region(descriptor_t *d) { if (d->free.size > i->free.size) i->free.first_bigger = d; break; } else { + if (i->free.first_bigger == 0 || i->free.first_bigger->free.size > d->free.size) + i->free.first_bigger = d; // continue i = i->free.next_by_size; } } } + + // Sanity check, could be deleted for performance but this doesn't necessarily cost much at the moment. + // Explanation: the first_bigger field is meant to point at the first free descriptor with strictly + // superior size, intending to make the finding a suitable free region faster, but this field + // is a bit complicated to keep up to date (see the messy code above...) + descriptor_t *rec_check_first_bigger(descriptor_t *it, size_t sz) { + if (it == 0) return 0; + ASSERT(rec_check_first_bigger(it->free.next_by_size, it->free.size) == it->free.first_bigger); + if (it->free.size > sz) return it; + return it->free.first_bigger; + } + ASSERT(rec_check_first_bigger(first_free_region_by_size, 0) == first_free_region_by_size); } descriptor_t *find_used_region(void* addr) { @@ -230,9 +264,8 @@ void region_allocator_init(void* begin, void* rsvd_end, void* end, map_page_fun_ descriptor_t *f0 = get_unused_descriptor(); f0->free.addr = rsvd_end; f0->free.size = ((void*)end - rsvd_end); - f0->free.next_by_size = 0; - f0->free.first_bigger = 0; - first_free_region_by_size = first_free_region_by_addr = f0; + first_free_region_by_size = first_free_region_by_addr = 0; + add_free_region(f0); if (rsvd_end > begin) { descriptor_t *u0 = get_unused_descriptor(); @@ -359,19 +392,19 @@ region_info_t *find_region(void* addr) { void dbg_print_region_info() { mutex_lock(&ra_mutex); - dbg_printf("/ Free kernel regions, by address:\n"); + dbg_printf("/ Free VM 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"); + dbg_printf("- Free VM 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 ", d->free.addr, d->free.addr + d->free.size); dbg_printf("(0x%p, next in size: 0x%p)\n", d->free.size, (d->free.first_bigger == 0 ? 0 : d->free.first_bigger->free.addr)); ASSERT(d != d->free.next_by_size); } - dbg_printf("- Used kernel regions:\n"); + dbg_printf("- Used VM 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); diff --git a/src/lib/include/stdio.h b/src/lib/include/stdio.h index b51bee4..a0d741f 100644 --- a/src/lib/include/stdio.h +++ b/src/lib/include/stdio.h @@ -1,8 +1,8 @@ #pragma once -#include <stddef.h> #include <stdarg.h> -#include <stdint.h> + +#include <syscall.h> extern fd_t stdio; diff --git a/src/sysbin/giosrv/main.c b/src/sysbin/giosrv/main.c index 6e3378b..e0b76f5 100644 --- a/src/sysbin/giosrv/main.c +++ b/src/sysbin/giosrv/main.c @@ -4,7 +4,7 @@ #include <syscall.h> #include <debug.h> -#include <user_region.h> +#include <region_alloc.h> #include <proto/keyboard.h> diff --git a/src/sysbin/init/main.c b/src/sysbin/init/main.c index 6ac003b..f1cb77a 100644 --- a/src/sysbin/init/main.c +++ b/src/sysbin/init/main.c @@ -5,7 +5,7 @@ #include <syscall.h> #include <debug.h> -#include <user_region.h> +#include <region_alloc.h> #include <btree.h> diff --git a/src/sysbin/login/main.c b/src/sysbin/login/main.c index 359d677..dfc5dfa 100644 --- a/src/sysbin/login/main.c +++ b/src/sysbin/login/main.c @@ -1,6 +1,5 @@ #include <string.h> #include <malloc.h> -#include <user_region.h> #include <debug.h> #include <syscall.h> diff --git a/src/sysbin/shell/main.c b/src/sysbin/shell/main.c index e35d700..3f37ff8 100644 --- a/src/sysbin/shell/main.c +++ b/src/sysbin/shell/main.c @@ -1,6 +1,5 @@ #include <string.h> #include <malloc.h> -#include <user_region.h> #include <debug.h> #include <stdio.h> diff --git a/src/sysbin/terminal/main.c b/src/sysbin/terminal/main.c index f0e77e3..a0d8855 100644 --- a/src/sysbin/terminal/main.c +++ b/src/sysbin/terminal/main.c @@ -1,6 +1,6 @@ #include <string.h> #include <malloc.h> -#include <user_region.h> +#include <region_alloc.h> #include <debug.h> #include <gip.h> diff --git a/src/tests/ktests/region1/test.c b/src/tests/ktests/region1/test.c index 58b4933..b5367d9 100644 --- a/src/tests/ktests/region1/test.c +++ b/src/tests/ktests/region1/test.c @@ -5,24 +5,39 @@ void test_region_1() { void* p = region_alloc(0x1000, "Test region"); dbg_printf("Allocated one-page region: 0x%p\n", p); dbg_print_region_info(); + void* q = region_alloc(0x1000, "Test region"); dbg_printf("Allocated one-page region: 0x%p\n", q); dbg_print_region_info(); + void* r = region_alloc(0x2000, "Test region"); dbg_printf("Allocated two-page region: 0x%p\n", r); dbg_print_region_info(); + void* s = region_alloc(0x10000, "Test region"); 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(r); + dbg_printf("Freed region 0x%p\n", r); + dbg_print_region_info(); + + p = region_alloc(0x1000, "Test region"); + dbg_printf("Allocated one-page 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); + + region_free(p); + dbg_printf("Freed region 0x%p\n", p); dbg_print_region_info(); + region_free(s); dbg_printf("Freed region 0x%p\n", s); dbg_print_region_info(); diff --git a/src/tests/ktests/run_qemu_test.sh b/src/tests/ktests/run_qemu_test.sh index 0e7b83e..5f7df83 100755 --- a/src/tests/ktests/run_qemu_test.sh +++ b/src/tests/ktests/run_qemu_test.sh @@ -1,6 +1,6 @@ #!/bin/bash -(qemu-system-i386 -kernel test_kernel.bin -initrd ../../kernel/kernel.map -serial stdio -m 16 -display none & echo $! >pid) \ +(qemu-system-i386 -kernel test_kernel.bin -initrd ../../../kernel/kernel.map -serial stdio -m 16 -display none & echo $! >pid) \ | tee >(grep -m 1 "TEST-" >result; kill -INT `cat pid`) \ RESULT=`cat result` diff --git a/src/tests/utests/malloc/test.c b/src/tests/utests/malloc/test.c index b55d28a..fb2f3b9 100644 --- a/src/tests/utests/malloc/test.c +++ b/src/tests/utests/malloc/test.c @@ -4,7 +4,7 @@ #include <syscall.h> #include <debug.h> -#include <user_region.h> +#include <region_alloc.h> int main(int argc, char **argv) { dbg_print("(BEGIN-USER-TEST malloc-test)\n"); |