aboutsummaryrefslogtreecommitdiff
path: root/src/lib/libkogata
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libkogata')
-rw-r--r--src/lib/libkogata/Makefile2
-rw-r--r--src/lib/libkogata/draw.c2
-rw-r--r--src/lib/libkogata/malloc.c8
-rw-r--r--src/lib/libkogata/user_region.c363
4 files changed, 8 insertions, 367 deletions
diff --git a/src/lib/libkogata/Makefile b/src/lib/libkogata/Makefile
index 95de086..7a1a2ee 100644
--- a/src/lib/libkogata/Makefile
+++ b/src/lib/libkogata/Makefile
@@ -1,4 +1,4 @@
-OBJ = start.o malloc.o debug.o syscall.o user_region.o \
+OBJ = start.o malloc.o debug.o syscall.o \
mainloop.o gip.o draw.o keyboard.o \
stdio.o unistd.o
diff --git a/src/lib/libkogata/draw.c b/src/lib/libkogata/draw.c
index 0536c03..53070ad 100644
--- a/src/lib/libkogata/draw.c
+++ b/src/lib/libkogata/draw.c
@@ -5,7 +5,7 @@
#include <proto/font_file.h>
-#include <user_region.h>
+#include <region_alloc.h>
#include <draw.h>
diff --git a/src/lib/libkogata/malloc.c b/src/lib/libkogata/malloc.c
index 56a5397..2a3345f 100644
--- a/src/lib/libkogata/malloc.c
+++ b/src/lib/libkogata/malloc.c
@@ -2,7 +2,7 @@
#include <slab_alloc.h>
#include <syscall.h>
-#include <user_region.h>
+#include <region_alloc.h>
static void* heap_alloc_pages(size_t s) {
void* addr = region_alloc(s, "Heap");
@@ -37,8 +37,12 @@ static slab_type_t slab_sizes[] = {
{ 0, 0, 0 }
};
+bool mmap_single_page(void* addr) {
+ return mmap(addr, PAGE_SIZE, MM_READ | MM_WRITE);
+}
+
void malloc_setup() {
- region_allocator_init((void*)0x40000000, (void*)0xB0000000);
+ region_allocator_init((void*)0x40000000, (void*)0x40000000, (void*)0xB0000000, mmap_single_page);
mem_allocator = create_slab_allocator(slab_sizes, heap_alloc_pages, heap_free_pages);
diff --git a/src/lib/libkogata/user_region.c b/src/lib/libkogata/user_region.c
deleted file mode 100644
index 14c0898..0000000
--- a/src/lib/libkogata/user_region.c
+++ /dev/null
@@ -1,363 +0,0 @@
-#include <user_region.h>
-#include <debug.h>
-#include <mutex.h>
-
-#include <syscall.h>
-
-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.first_bigger == d) {
- i->free.first_bigger = d->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) {
- if (first_used_region == 0 || d->used.i.addr < first_used_region->used.i.addr) {
- d->used.next_by_addr = first_used_region;
- first_used_region = d;
- } else {
- 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* begin, void* 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(begin);
- f0->free.size = ((void*)PAGE_ALIGN_DOWN(end) - 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;
-
- first_used_region = 0;
-}
-
-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, 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;
- add_used_region(i);
-
- return addr;
- }
- }
- return 0; //No big enough block found
-}
-
-void* region_alloc(size_t size, char* type) {
- void* result = 0;
- mutex_lock(&ra_mutex);
-
- if (n_unused_descriptors <= N_RESERVE_DESCRIPTORS) {
- void* descriptor_region = region_alloc_inner(PAGE_SIZE, "Region descriptors", true);
- ASSERT(descriptor_region != 0);
-
- bool map_ok = mmap(descriptor_region, PAGE_SIZE, MM_READ | MM_WRITE);
- if (!map_ok) {
- // this can happen if we weren't able to mmap the region (for whatever reason)
- 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, 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;
-}
-
-// =========================== //
-// DEBUG LOG PRINTING FUNCTION //
-// =========================== //
-
-void dbg_print_region_info() {
- mutex_lock(&ra_mutex);
-
- dbg_printf("/ Free process 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 process 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 process 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);
- }
-
- int nfreerd = 0;
- for (descriptor_t *i = first_unused_descriptor; i != 0; i = i->unused_descriptor.next)
- nfreerd++;
-
- dbg_printf("\\ Free region descriptors: %d (%d)\n", nfreerd, n_unused_descriptors);
-
- mutex_unlock(&ra_mutex);
-}
-
-/* vim: set ts=4 sw=4 tw=0 noet :*/
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-24 13:10:34 +0000