aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/common/libkogata/region_alloc.c73
-rw-r--r--src/lib/include/stdio.h4
-rw-r--r--src/sysbin/giosrv/main.c2
-rw-r--r--src/sysbin/init/main.c2
-rw-r--r--src/sysbin/login/main.c1
-rw-r--r--src/sysbin/shell/main.c1
-rw-r--r--src/sysbin/terminal/main.c2
-rw-r--r--src/tests/ktests/region1/test.c19
-rwxr-xr-xsrc/tests/ktests/run_qemu_test.sh2
-rw-r--r--src/tests/utests/malloc/test.c2
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");
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 18:33:25 +0000