aboutsummaryrefslogtreecommitdiff
path: root/kernel
diff options
context:
space:
mode:
Diffstat (limited to 'kernel')
-rw-r--r--kernel/Makefile2
-rw-r--r--kernel/config.h2
-rw-r--r--kernel/include/hashtbl.h31
-rw-r--r--kernel/l0/kmain.c61
-rw-r--r--kernel/lib/hashtbl.c166
5 files changed, 251 insertions, 11 deletions
diff --git a/kernel/Makefile b/kernel/Makefile
index 5571543..a981c72 100644
--- a/kernel/Makefile
+++ b/kernel/Makefile
@@ -9,7 +9,7 @@ CFLAGS = -ffreestanding -O2 -std=gnu99 -Wall -Wextra -I . -I ./include -g -Wno-u
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 \
+OBJ = lib/string.o lib/printf.o lib/slab_alloc.o lib/mutex.o lib/hashtbl.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
diff --git a/kernel/config.h b/kernel/config.h
index 2de43af..a0e59d3 100644
--- a/kernel/config.h
+++ b/kernel/config.h
@@ -13,6 +13,8 @@
#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"
diff --git a/kernel/include/hashtbl.h b/kernel/include/hashtbl.h
new file mode 100644
index 0000000..984aa70
--- /dev/null
+++ b/kernel/include/hashtbl.h
@@ -0,0 +1,31 @@
+#pragma once
+
+#include <stdint.h>
+#include <stddef.h>
+#include <stdbool.h>
+
+// 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
+
+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/l0/kmain.c b/kernel/l0/kmain.c
index 140a09f..f0ce014 100644
--- a/kernel/l0/kmain.c
+++ b/kernel/l0/kmain.c
@@ -13,6 +13,7 @@
#include <thread.h>
#include <slab_alloc.h>
+#include <hashtbl.h>
extern const void k_end_addr; // defined in linker script : 0xC0000000 plus kernel stuff
@@ -100,25 +101,65 @@ void kmalloc_test(void* kernel_data_end) {
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) {
- int i = 0;
- while(1) {
+ 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) {
- yield();
- i = 0;
- }
+ if (i % 8 == 0) yield();
}
}
void kernel_init_stage2(void* data) {
- thread_t *tb = new_thread(test_thread);
- resume_thread_with_result(tb, 0, false);
-
dbg_print_region_info();
dbg_print_frame_stats();
- while(1) {
+ test_hashtbl_1();
+ test_hashtbl_2();
+
+ thread_t *tb = new_thread(test_thread);
+ resume_thread_with_result(tb, 0, false);
+
+ for (int i = 0; i < 120; i++) {
dbg_printf("a");
for (int x = 0; x < 100000; x++) asm volatile("xor %%ebx, %%ebx":::"%ebx");
}
diff --git a/kernel/lib/hashtbl.c b/kernel/lib/hashtbl.c
new file mode 100644
index 0000000..91fb3cb
--- /dev/null
+++ b/kernel/lib/hashtbl.c
@@ -0,0 +1,166 @@
+#include <hashtbl.h>
+#include <kmalloc.h>
+#include <string.h>
+
+#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 :*/
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 16:43:34 +0000