diff options
| -rw-r--r-- | README.md | 53 | ||||
| -rw-r--r-- | src/common/Makefile | 2 | ||||
| -rw-r--r-- | src/common/buffer.c | 167 | ||||
| -rw-r--r-- | src/common/common.lib | bin | 41450 -> 35275 bytes | |||
| -rw-r--r-- | src/common/hashtbl.c | 7 | ||||
| -rw-r--r-- | src/common/include/buffer.h | 41 | ||||
| -rw-r--r-- | src/common/include/hashtbl.h | 9 | ||||
| -rw-r--r-- | src/common/include/string.h | 2 | ||||
| -rw-r--r-- | src/common/string.c | 11 | ||||
| -rw-r--r-- | src/kernel/core/kmain.c | 4 |
10 files changed, 30 insertions, 266 deletions
@@ -1,52 +1,3 @@ -Extracted from the [NARP protocol specification v2](http://adnab.me/cgi-bin/cgit.cgi/NARP.git/plain/doc/spec-2.html) : - -### Architecture of the OS - -The basic primitive of the system being message-passing, the system looks a lot like a micro-kernel. Only the message format has a complex semantic and the communication layer is not really “simple”. Furthermore, the system has device drivers, file system and networking running as kernel-mode processes, making the kernel more monolithic (but still having a micro-kernel spirit). It should be easy to make any user mode process run as a kernel mode process instead, for the sake of performance (eg : graphical server & compositor). - -The kernel land is divided in three major parts, with strict dependency order: - -- Level 0 : System ressource managment : physical memory, virtual memory, hardware interaction (IRQ, v86), debug output - -- Level 1 : Scheduler, IPC & NARP core server : builds on top of level 0, adds support for processes and communication between them restricted to NARP protocol data. - -- Level 2 : System processes : hardware, file systems, network, … (may access level 0 and level 1 features) - -User processes are restricted to syscalls that call level 1 primitives. - -Here are a few basic principles for the design of these three levels : - -- Level 2 processes may not communicate directly nor share memory : they must go through level 0 and level 1 primitives to achieve such a goal. Each level 2 process has a separate heap, which is completely freed when the process dies. Level 2 processes do not use separate virtual memory spaces : since the kernel memory space is mapped in all page directories, a level 2 process may run with any page directory. - -- Benefits : critical system parts are restricted to level 0 and level 1. Level 2 components may leak or crash with less consequences. - - All synchronization & locking is handle by level 1, except for level 0 that must implement its own locking devices (since it cannot rely on level 1). - -- Benefits : no complex synchronization in most of the code (which is either level 2 or userland), only simple message passing and waiting for stuff to happen - -- No concept of “threads” : system processes are actually kernel threads, but we call them processes since they use separate parts of memory. Userlands processes cannot spawn multiple threads of execution either : they must fork and communicate through NARP if they want to do so (eg: launching an expensive communication in the background). - - (since fork is a complicated system call, and features such as copy-on-write depend on processes using different paging directories, the fork system call is accessible only to userland processes : level 2 processes may not fork, but only create new processes) - -- Level 1 also has a memory heap ; it is used with `core_malloc/core_free`. Level 2 proceses use standard malloc/free, which are modified to act on the heap of the current process. - -- Each process (system or user) has a mailbox, ie a queue of incoming NARP messages waiting to be transferred. The mailbox has a maximum size (buffer size), and a send call may fail with a no space left in queue error. This is the only possible failure for a send call. - - System processes (level 2) spend most of their time in waiting mode ; they may be waked up by either recieving a NARP messsage or by a hardware event. Therefore the `wait_for_event` function that composes the main loop may return either : a message was recieved or a system event happenned. If the reason is a message was recieved, the process is free not to read the message immediately. - - On the other hand, user processes can wait for only one thing : recieving a NARP message. Each user process has a message zone in its memory space, and the wait for message function just copies the first message of the mailbox into this zone (overwriting whatever was there before) and returns control to the process (returning the length of the message). - -- Handling of IRQs : some hardware stuff requires action as soon as the interrupt is fired, therefore a specifi IRQ handler may be used. Such a handler must do as little as possible, and when it is done signal level 1 that an IRQ has happenned (it may add specific data to the “IRQ happenned” message). Level 1 adds a message to the queue of the recipient process (if there is one) and returns immediately : the IRQ handler must leave as soon as possible. An IRQ is handled on whatever stack is currently used, and the IF flag is constantly off while the IRQ handler is running. The timer IRQ is the only one that behaves differently, since it has to trigger a task switch. - -### Steps of the developpment of the OS - -1. Develop level 0 completely and with cleanest possible design - -2. Develop level 1 with only basic funcionnality - -3. Develop some basic applications in level 2 : display, keyboard, mini kernel shell, mini file system, … - -4. Improve level 1 with more complex stuff ; try to quickly attain a complete level 1 - -5. Work on the rest of the stuff +kogata operating system : small and <del>beautiful</del>small. +No explanation (sorry, maybe later). diff --git a/src/common/Makefile b/src/common/Makefile index d27c6d5..40b8ba9 100644 --- a/src/common/Makefile +++ b/src/common/Makefile @@ -1,4 +1,4 @@ -OBJ = string.o printf.o slab_alloc.o mutex.o hashtbl.o buffer.o +OBJ = string.o printf.o slab_alloc.o mutex.o hashtbl.o LIB = diff --git a/src/common/buffer.c b/src/common/buffer.c deleted file mode 100644 index 21f1ec4..0000000 --- a/src/common/buffer.c +++ /dev/null @@ -1,167 +0,0 @@ -#include <malloc.h> - -#include <buffer.h> -#include <string.h> - -#include <debug.h> - -// three types of buffers -#define T_BYTES 1 -#define T_SLICE 2 -#define T_CONCAT 3 - -struct buffer { - uint16_t rc, type; // takes less space like this - size_t len; - union { - struct { - const char* data; - bool owned; - } bytes; - struct { - struct buffer *buf; - size_t begin; - } slice; - struct { - struct buffer *a, *b; - } concat; - }; -}; - -void buffer_ref(buffer_t *b) { - b->rc++; -} - -void buffer_unref(buffer_t *b) { - b->rc--; - if (b->rc == 0) { - switch (b->type) { - case T_BYTES: - if (b->bytes.owned) free((void*)b->bytes.data); - break; - case T_SLICE: - buffer_unref(b->slice.buf); - break; - case T_CONCAT: - buffer_unref(b->concat.a); - buffer_unref(b->concat.b); - break; - default: - ASSERT(false); - } - free(b); - } -} - -size_t buffer_size(buffer_t *b) { - return b->len; -} - -size_t read_buffer(buffer_t *b, char* dest, size_t begin, size_t n) { - if (begin >= b->len) return 0; - if (begin + n >= b->len) n = b->len - begin; - - switch (b->type) { - case T_BYTES: - memcpy(dest, b->bytes.data + begin, n); - break; - case T_SLICE: - read_buffer(b->slice.buf, dest, begin + b->slice.begin, n); - break; - case T_CONCAT: { - size_t la = b->concat.a->len; - if (begin < la) { - size_t r = read_buffer(b->concat.a, dest, begin, n); - if (r < n) { - ASSERT(read_buffer(b->concat.b, dest, 0, n - r) == n - r); - } - } else { - ASSERT(read_buffer(b->concat.b, dest, begin - la, n) == n); - } - break; - } - default: - ASSERT(false); - } - - return n; -} - -// ========================= // -// BUFFER CREATION FUNCTIONS // -// ========================= // - -buffer_t *buffer_from_bytes_nocopy(const char* data, size_t n, bool own_bytes) { - buffer_t *b = (buffer_t*)malloc(sizeof(buffer_t)); - if (b == 0) return 0; - - b->rc = 1; - b->type = T_BYTES; - b->len = n; - b->bytes.data = data; - b->bytes.owned = own_bytes; - - return b; -} -buffer_t *buffer_from_bytes(const char* data, size_t n) { - char* data2 = (char*)malloc(n); - if (data2 == 0) return 0; - - memcpy(data2, data, n); - - buffer_t *b = buffer_from_bytes_nocopy(data2, n, true); - if (b == 0) { - free(data2); - return 0; - } - - return b; -} - - -buffer_t* buffer_slice(buffer_t* src, size_t begin, size_t n) { - if (begin + n > src->len) return 0; // invalid request - - buffer_t *b = (buffer_t*)malloc(sizeof(buffer_t)); - if (b == 0) return 0; - - b->rc = 1; - b->type = T_SLICE; - b->len = n; - b->slice.buf = src; - b->slice.begin = begin; - - return b; -} - -buffer_t* buffer_concat(buffer_t* a, buffer_t* b) { - buffer_t *r = (buffer_t*)malloc(sizeof(buffer_t)); - if (r == 0) return r; - - r->rc = 1; - r->type = T_CONCAT; - r->len = a->len + b->len; - r->concat.a = a; - r->concat.b = b; - - return r; -} - -buffer_t* buffer_slice_k(buffer_t *b, size_t begin, size_t n) { - buffer_t *r = buffer_slice(b, begin, n); - if (r != 0) { - buffer_ref(b); - } - return r; -} - -buffer_t* buffer_concat_k(buffer_t *a, buffer_t *b) { - buffer_t *r = buffer_concat(a, b); - if (r != 0) { - buffer_ref(a); - buffer_ref(b); - } - return r; -} - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/common.lib b/src/common/common.lib Binary files differindex 16259e6..058abeb 100644 --- a/src/common/common.lib +++ b/src/common/common.lib diff --git a/src/common/hashtbl.c b/src/common/hashtbl.c index 47072b4..d034ff5 100644 --- a/src/common/hashtbl.c +++ b/src/common/hashtbl.c @@ -16,16 +16,18 @@ typedef struct hashtbl_item { struct hashtbl { key_eq_fun_t ef; hash_fun_t hf; + key_free_fun_t kff; 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 *create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, key_free_fun_t kff, size_t initial_size) { hashtbl_t *ht = (hashtbl_t*)malloc(sizeof(hashtbl_t)); if (ht == 0) return 0; ht->ef = ef; ht->hf = hf; + ht->kff = kff; ht->size = (initial_size == 0 ? DEFAULT_INIT_SIZE : initial_size); ht->nitems = 0; @@ -46,6 +48,7 @@ void delete_hashtbl(hashtbl_t *ht) { for (size_t i = 0; i < ht->size; i++) { while (ht->items[i] != 0) { hashtbl_item_t *n = ht->items[i]->next; + if (ht->kff) ht->kff(ht->items[i]->key); free(ht->items[i]); ht->items[i] = n; } @@ -122,6 +125,7 @@ void hashtbl_remove(hashtbl_t* ht, void* key) { if (ht->ef(ht->items[slot]->key, key)) { hashtbl_item_t *x = ht->items[slot]; ht->items[slot] = x->next; + if (ht->kff) ht->kff(x->key); free(x); ht->nitems--; } else { @@ -129,6 +133,7 @@ void hashtbl_remove(hashtbl_t* ht, void* key) { if (ht->ef(i->next->key, key)) { hashtbl_item_t *x = i->next; i->next = x->next; + if (ht->kff) ht->kff(x->key); free(x); ht->nitems--; break; diff --git a/src/common/include/buffer.h b/src/common/include/buffer.h deleted file mode 100644 index 0d6cfbf..0000000 --- a/src/common/include/buffer.h +++ /dev/null @@ -1,41 +0,0 @@ -#pragma once - -#include <stdint.h> -#include <stddef.h> -#include <stdbool.h> - -// The buffer_t type is a simple reference-counted buffer type -// enabling the creation, sharing, slicing and concatenation of buffers -// without having to copy everything each time - -// Buffers are always allocated on the core kernel heap (kmalloc/kfree) - -// Once a buffer is allocated, its contents is immutable - -// Encoding and decoding functions for buffer contents are provided in -// a separate file (encode.h) - -struct buffer; -typedef struct buffer buffer_t; - -void buffer_ref(buffer_t*); // increase reference counter -void buffer_unref(buffer_t*); // decrease reference counter - -size_t buffer_len(buffer_t* buf); -size_t read_buffer(buffer_t* buf, char* to, size_t begin, size_t n); // returns num of bytes read - -buffer_t* buffer_from_bytes(const char* data, size_t n); // bytes are COPIED -buffer_t* buffer_from_bytes_nocopy(const char* data, size_t n, bool own_bytes); // bytes are NOT COPIED - -// these functions GIVE the buffer in order to create the new buffer, ie they do not increase RC -// the buffer is NOT GIVED if the new buffer could not be created (ie retval == 0) -buffer_t* buffer_slice(buffer_t* b, size_t begin, size_t n); -buffer_t* buffer_concat(buffer_t* a, buffer_t* b); - -// these functions KEEP a reference on the buffer (ie RC is incremented) -// the RC is NOT INCREMENTED if the new buffer cannot be created -buffer_t* buffer_slice_k(buffer_t* b, size_t begin, size_t n); -buffer_t* buffer_concat_k(buffer_t* a, buffer_t* b); - - -/* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/include/hashtbl.h b/src/common/include/hashtbl.h index 16dfefb..3b5a44d 100644 --- a/src/common/include/hashtbl.h +++ b/src/common/include/hashtbl.h @@ -8,8 +8,10 @@ // Supports adding, seeking, removing // When adding a binding to the table, the previous binding for same key (if exists) is removed -// TODO : possibility to allocate the hashtbl structure on any heap -// (currently uses kmalloc/kfree) +// The hashtbl is allocated with malloc/free +// The keys are not copied in any way by the hashtbl, but there might still be something +// to free, so the create_hashtbl function is given a key freeing function, usually +// null when no freeing is required, or the standard free function. struct hashtbl; typedef struct hashtbl hashtbl_t; @@ -17,8 +19,9 @@ 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*); +typedef void (*key_free_fun_t)(void*); -hashtbl_t* create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, size_t initial_size); // 0 -> default size +hashtbl_t* create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, key_free_fun_t ff, 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) diff --git a/src/common/include/string.h b/src/common/include/string.h index 682b25a..a7a5253 100644 --- a/src/common/include/string.h +++ b/src/common/include/string.h @@ -14,4 +14,6 @@ char *strcpy(char *dest, const char *src); char *strcat(char *dest, const char *src); int strcmp(const char *s1, const char *s2); +char *strdup(const char* str); + /* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/common/string.c b/src/common/string.c index 9dce27b..2c73900 100644 --- a/src/common/string.c +++ b/src/common/string.c @@ -1,4 +1,5 @@ #include <string.h> +#include <malloc.h> size_t strlen(const char* str) { @@ -87,4 +88,14 @@ void *memset(void *dest, int val, size_t count) { return dest; } +char *strdup(const char* str) { + int len = strlen(str) + 1; + + char* ret = (char*)malloc(len); + if (ret == 0) return 0; + + memcpy(ret, str, len); + return ret; +} + /* vim: set ts=4 sw=4 tw=0 noet :*/ diff --git a/src/kernel/core/kmain.c b/src/kernel/core/kmain.c index 2169b7d..6024b77 100644 --- a/src/kernel/core/kmain.c +++ b/src/kernel/core/kmain.c @@ -104,7 +104,7 @@ void kmalloc_test(void* kernel_data_end) { void test_hashtbl_1() { // hashtable test - hashtbl_t *ht = create_hashtbl(str_key_eq_fun, str_hash_fun, 0); + hashtbl_t *ht = create_hashtbl(str_key_eq_fun, str_hash_fun, 0, 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")); @@ -124,7 +124,7 @@ void test_hashtbl_1() { } void test_hashtbl_2() { - hashtbl_t *ht = create_hashtbl(id_key_eq_fun, id_hash_fun, 0); + hashtbl_t *ht = create_hashtbl(id_key_eq_fun, id_hash_fun, 0, 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)); |