From d1ff7bcc91886626dc9060ec5fb67ee102ab7c1d Mon Sep 17 00:00:00 2001 From: Jon Santmyer Date: Mon, 11 Mar 2024 21:30:31 -0400 Subject: usermode capable kernel with logging syscall --- lib/format.h | 13 +++++++ lib/hashtable.c | 109 +++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/hashtable.d | 2 + lib/hashtable.h | 34 +++++++++++++++++ lib/jove.h | 15 ++++++++ lib/kpanic.c | 15 ++++++++ lib/kpanic.d | 1 + lib/linkedlist.c | 34 +++++++++++++++++ lib/linkedlist.d | 1 + lib/linkedlist.h | 26 +++++++++++++ lib/ltostr.c | 26 +++++++++++++ lib/ltostr.d | 1 + lib/mem.c | 52 ++++++++++++++++++++++++++ lib/mem.d | 1 + lib/sfmt.c | 112 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/sfmt.d | 1 + lib/string.c | 16 ++++++++ lib/string.d | 1 + lib/string.h | 18 +++++++++ lib/toupper.c | 26 +++++++++++++ lib/toupper.d | 1 + 21 files changed, 505 insertions(+) create mode 100644 lib/format.h create mode 100644 lib/hashtable.c create mode 100644 lib/hashtable.d create mode 100644 lib/hashtable.h create mode 100644 lib/jove.h create mode 100644 lib/kpanic.c create mode 100644 lib/kpanic.d create mode 100644 lib/linkedlist.c create mode 100644 lib/linkedlist.d create mode 100644 lib/linkedlist.h create mode 100644 lib/ltostr.c create mode 100644 lib/ltostr.d create mode 100644 lib/mem.c create mode 100644 lib/mem.d create mode 100644 lib/sfmt.c create mode 100644 lib/sfmt.d create mode 100644 lib/string.c create mode 100644 lib/string.d create mode 100644 lib/string.h create mode 100644 lib/toupper.c create mode 100644 lib/toupper.d (limited to 'lib') diff --git a/lib/format.h b/lib/format.h new file mode 100644 index 0000000..5a2b75c --- /dev/null +++ b/lib/format.h @@ -0,0 +1,13 @@ +#ifndef JOVE_LIB_FORMAT_H +#define JOVE_LIB_FORMAT_H 1 + +#include +#include + +size_t ltostr(char *s, size_t limit, unsigned long l, bool sgn, int radix); + +char *sfmt(char *s, size_t limit, const char *fmt, ...); +#include +char *svfmt(char *s, size_t limit, const char *fmt, va_list ap); + +#endif diff --git a/lib/hashtable.c b/lib/hashtable.c new file mode 100644 index 0000000..17f1e74 --- /dev/null +++ b/lib/hashtable.c @@ -0,0 +1,109 @@ +#include "hashtable.h" +#include "string.h" +#include "mem/memory.h" + +static size_t +s_hash_function_mul(const void *data, size_t len) +{ + size_t hash = 1; + const char *cdata = (const char*)data; + for(size_t i = 0; i < len; i++) { + hash *= ((size_t)cdata[i]) + 1; + } + return hash; +} + +static size_t +s_hash_function_mul_s(const void *data, size_t _) +{ + return s_hash_function_mul(data, strlen(data)); +} + +void +_hashtable_new(struct HashTable *table, size_t obj_size, size_t key_size) +{ + *table = (struct HashTable){ + .buckets = NULL, + .bucket_count = 0, + .bucket_capacity = 2, + .obj_size = obj_size, + .key_size = key_size, + .hash_function = s_hash_function_mul + }; + table->buckets = mem_alloc(sizeof(struct SLinkedList) * 2); +} + +void +_hashtable_news(struct HashTable *table, size_t obj_size) +{ + *table = (struct HashTable){ + .buckets = NULL, + .bucket_count = 0, + .bucket_capacity = 2, + .obj_size = obj_size, + .key_size = -1, + .hash_function = s_hash_function_mul_s + }; + table->buckets = mem_alloc(sizeof(struct SLinkedList) * 2); +} + +void +hashtable_insert(struct HashTable *table, const void *key, void *data) +{ + size_t hash = table->hash_function(key, table->key_size); + if(table->bucket_capacity == table->bucket_count) { + struct SLinkedList *old_buckets = table->buckets; + size_t old_buckets_count = table->bucket_count; + + table->bucket_capacity *= 2; + table->bucket_count = 0; + table->buckets = mem_alloc(sizeof(struct SLinkedList) * table->bucket_capacity); + for(size_t i = 0; i < old_buckets_count; i++) { + for(struct SLLNode *node = old_buckets[i].head; node != NULL; node = node->next) { + struct HashTableValue *value = (struct HashTableValue*)(&node->data); + hashtable_insert(table, value->key, value->value); + mem_free(node); + } + } + } + + size_t index = hash % table->bucket_capacity; + struct SLinkedList *bucket = &table->buckets[index]; + struct SLLNode *node = mem_alloc(sizeof(struct SLLNode) + sizeof(struct HashTableValue) + table->obj_size); + struct HashTableValue *value = (struct HashTableValue*)(node->data); + + value->key = key; + memcpy(value->value, data, table->obj_size); + + table->bucket_count++; + if(bucket->count == 0) { + sll_new(bucket, table->obj_size); + sll_push(bucket, node); + return; + } + for(struct SLLNode *onode = bucket->head; onode != NULL; onode = onode->next) + { + struct HashTableValue *ovalue = (struct HashTableValue*)onode->data; + size_t keylen = table->key_size > 0 ? table->key_size : strlen((const char*)key) + 1; + if(memcmp(ovalue->key, value->key, keylen) == 0) { + memcpy(ovalue->value, value->value, table->obj_size); + return; + } + } + sll_push(bucket, node); +} + +void* +_hashtable_get(struct HashTable *table, const void *key) +{ + size_t hash = table->hash_function(key, table->key_size); + size_t index = hash % table->bucket_capacity; + struct SLinkedList *bucket = &table->buckets[index]; + for(struct SLLNode *node = bucket->head; node != NULL; node = node->next) + { + struct HashTableValue *value = (struct HashTableValue*)node->data; + size_t keylen = table->key_size > 0 ? table->key_size : strlen((const char*)value->key); + if(memcmp(key, value->key, keylen) == 0) return value->value; + } + return NULL; +} diff --git a/lib/hashtable.d b/lib/hashtable.d new file mode 100644 index 0000000..791f457 --- /dev/null +++ b/lib/hashtable.d @@ -0,0 +1,2 @@ +lib/hashtable.o: lib/hashtable.c lib/hashtable.h lib/linkedlist.h \ + lib/string.h mem/memory.h mem/slab.h diff --git a/lib/hashtable.h b/lib/hashtable.h new file mode 100644 index 0000000..fe6f5c3 --- /dev/null +++ b/lib/hashtable.h @@ -0,0 +1,34 @@ +#ifndef JOVE_LIB_HASHTABLE_H +#define JOVE_LIB_HASHTABLE_H 1 + +#include +#include +#include "linkedlist.h" + +struct HashTableValue +{ + const void *key; + char value[]; +}; + +struct HashTable { + struct SLinkedList *buckets; + size_t bucket_count; + size_t bucket_capacity; + + size_t obj_size; + int key_size; + size_t (*hash_function)(const void*, size_t); +}; + +void _hashtable_new(struct HashTable *table, size_t obj_size, size_t key_size); +#define hashtable_new(table, type, keytype) _hashtable_new(table, sizeof(type), sizeof(keytype)) + +void _hashtable_news(struct HashTable *table, size_t obj_size); +#define hashtable_news(table, type) _hashtable_news(table, sizeof(type)) + +void hashtable_insert(struct HashTable *table, const void *key, void *data); +void *_hashtable_get(struct HashTable *table, const void *key); +#define hashtable_get(table, key, type) (type*)_hashtable_get(table, key) + +#endif diff --git a/lib/jove.h b/lib/jove.h new file mode 100644 index 0000000..4aa60ed --- /dev/null +++ b/lib/jove.h @@ -0,0 +1,15 @@ +#ifndef JOVE_LIB_JOVE_H +#define JOVE_LIB_JOVE_H 1 + +#define ALWAYS_INLINE inline __attribute__((always_inline)) +#define PAGEALIGN __attribute__((aligned(0x1000))) + +//#define LOG2(n) (__builtin_clz(n) ^ 31) + +extern void *_kernel_start; +extern void *_kernel_end; + +__attribute__((noreturn)) void _kpanic(const char *file, int line, const char *fmt, ...); +#define kpanic(...) _kpanic(__FILE__, __LINE__, __VA_ARGS__) + +#endif diff --git a/lib/kpanic.c b/lib/kpanic.c new file mode 100644 index 0000000..97e42eb --- /dev/null +++ b/lib/kpanic.c @@ -0,0 +1,15 @@ +#include "jove.h" +#include "io/log.h" + +#include + +__attribute__((noreturn)) +void _kpanic(const char *file, int line, const char *fmt, ...) +{ + va_list ap; + va_start(ap, fmt); + klogf("!!! PANIC !!!\n%s:%i\n", file, line); + kvlogf(fmt, ap); + va_end(ap); + for(;;) __asm__ volatile("hlt"); +} diff --git a/lib/kpanic.d b/lib/kpanic.d new file mode 100644 index 0000000..bf4ed9e --- /dev/null +++ b/lib/kpanic.d @@ -0,0 +1 @@ +lib/kpanic.o: lib/kpanic.c lib/jove.h io/log.h diff --git a/lib/linkedlist.c b/lib/linkedlist.c new file mode 100644 index 0000000..6cc6403 --- /dev/null +++ b/lib/linkedlist.c @@ -0,0 +1,34 @@ +#include "linkedlist.h" + +void +sll_new(struct SLinkedList *list, size_t obj_size) +{ + list->obj_size = obj_size; + list->count = 0; + list->head = list->tail = NULL; +}; + +void +sll_push(struct SLinkedList *list, void *data) +{ + struct SLLNode *node = (struct SLLNode*)data; + if(list->tail != NULL) { + list->tail->next = node; + } + if(list->head == NULL) + list->head = node; + list->tail = node; + list->count++; +} + +void* +sll_get(struct SLinkedList *list, size_t index) +{ + struct SLLNode *node = list->head; + if(node == NULL) return NULL; + if(index > list->count) return list->tail; + for(size_t i = 0; i < index; i++) { + node = node->next; + } + return node; +} diff --git a/lib/linkedlist.d b/lib/linkedlist.d new file mode 100644 index 0000000..a06a9df --- /dev/null +++ b/lib/linkedlist.d @@ -0,0 +1 @@ +lib/linkedlist.o: lib/linkedlist.c lib/linkedlist.h diff --git a/lib/linkedlist.h b/lib/linkedlist.h new file mode 100644 index 0000000..26c148e --- /dev/null +++ b/lib/linkedlist.h @@ -0,0 +1,26 @@ +#ifndef JOVE_LIB_LINKEDLIST_H +#define JOVE_LIB_LINKEDLIST_H 1 + +#include +#include + +struct SLLNode { + struct SLLNode *next; + char data[]; +}; + +/*Singly Linked List*/ +struct SLinkedList +{ + struct SLLNode *head; + struct SLLNode *tail; + + size_t obj_size; + size_t count; +}; + +void sll_new(struct SLinkedList *list, size_t obj_size); +void sll_push(struct SLinkedList *list, void *node); +void *sll_get(struct SLinkedList *list, size_t index); + +#endif diff --git a/lib/ltostr.c b/lib/ltostr.c new file mode 100644 index 0000000..e28be31 --- /dev/null +++ b/lib/ltostr.c @@ -0,0 +1,26 @@ +#include "format.h" + +size_t +ltostr(char *s, size_t limit, unsigned long l, bool sgn, int radix) +{ + size_t si = 0; + size_t digits = 0; + if((long)l < 0 && sgn) { + l = -((long)l); + s[0] = '-'; + } + for(unsigned long lv = l; lv != 0; lv /= radix) + digits++; + digits = digits > limit ? limit : digits; + + if(digits-- == 0) + s[si++] = '0'; + for(unsigned long lv = l; lv != 0; lv /= radix) + { + if(si >= limit) return si; + int digit = lv % radix; + s[(digits - si)] = (digit >= 10 ? (digit + 'a' - 10) : digit + '0'); + si++; + } + return si; +} diff --git a/lib/ltostr.d b/lib/ltostr.d new file mode 100644 index 0000000..fecc225 --- /dev/null +++ b/lib/ltostr.d @@ -0,0 +1 @@ +lib/ltostr.o: lib/ltostr.c lib/format.h diff --git a/lib/mem.c b/lib/mem.c new file mode 100644 index 0000000..b60fbbd --- /dev/null +++ b/lib/mem.c @@ -0,0 +1,52 @@ +#include "string.h" +#include "mem/memory.h" + +void* +memset(void *dest, int c, size_t n) +{ + char *destc = (char*)dest; + for(size_t i = 0; i < n; i++) + destc[i] = c; + return dest; +} + +void* +memcpy(void *dest, const void *src, size_t n) +{ + char *destc = (char*)dest; + const char *srcc = (const char*)src; + for(size_t i = 0; i < n; i++) + destc[i] = srcc[i]; + return dest; +} + +void* +memmove(void *dest, const void *src, size_t n) +{ + char *destc = (char*)dest; + const char *srcc = (const char*)src; + if(destc + n < srcc) return memcpy(dest, src, n); + char buffer[n]; + memcpy(buffer, src, n); + return memcpy(destc, buffer, n); +} + +int +memcmp(const void *a, const void *b, size_t n) +{ + const char *ac = (const char*)a; + const char *bc = (const char*)b; + for(size_t i = 0; i < n; i++) { + if(ac[i] != bc[i]) return ac[i] - bc[i]; + } + return 0; +} + +char* +strdup(const char *s) +{ + size_t slen = strlen(s); + char *ret = mem_alloc(slen); + memcpy(ret, s, slen); + return ret; +} diff --git a/lib/mem.d b/lib/mem.d new file mode 100644 index 0000000..232ecd5 --- /dev/null +++ b/lib/mem.d @@ -0,0 +1 @@ +lib/mem.o: lib/mem.c lib/string.h mem/memory.h mem/slab.h diff --git a/lib/sfmt.c b/lib/sfmt.c new file mode 100644 index 0000000..f903cbf --- /dev/null +++ b/lib/sfmt.c @@ -0,0 +1,112 @@ +#include "string.h" +#include "format.h" + +char* +sfmt(char *s, size_t limit, const char *fmt, ...) +{ + va_list ap; + va_start(ap, fmt); + + s = svfmt(s, limit, fmt, ap); + + va_end(ap); + return s; +} + +char* +svfmt(char *s, size_t limit, const char *fmt, va_list ap) +{ + + size_t fmtlen = strlen(fmt); + size_t si = 0; + for(size_t fmti = 0; fmti < fmtlen; fmti++) + { + if(si >= limit) break; + if(fmt[fmti] != '%') { + s[si++] = fmt[fmti]; + continue; + } + // TODO: Format flags + fmti++; + + bool alt = false; + bool zpad = false; + for(;;fmti++){ + if(fmt[fmti] == '#') { alt = true; continue; } + if(fmt[fmti] == '0') { zpad = true; continue; } + break; + } + int fwidth = 0; + if(fmt[fmti] >= '1' && fmt[fmti] <= '9') + { + for(;fmt[fmti] >= '0' && fmt[fmti] <= '9';fmti++) { + fwidth *= 10; + fwidth += fmt[fmti] - '0'; + } + } + int precision = 0; + if(fmt[fmti] == '.') + { + fmti++; + for(;fmt[fmti] >= '0' && fmt[fmti] <= '9';fmti++) { + precision *= 10; + precision += fmt[fmti] - '0'; + } + } + + bool sgn = true; + bool upper = false; + int radix = 10; + switch(fmt[fmti]) + { + case '%': + s[si++] = '%'; + break; + case 'b': + radix = 2; + case 'X': + upper = true; + case 'x': + if(radix == 10) + radix = 16; + case 'o': + if(radix == 10) + radix = 8; + case 'u': + sgn = false; + case 'i': { + if((radix == 8 || radix == 16) && alt) { + s[si++] = '0'; + if(radix == 16) { + s[si++] = 'x'; + } + if(radix == 2) { + s[si++] = 'b'; + } + } + size_t osi = si; + size_t nlen = ltostr(&s[si], limit - si, va_arg(ap, long), sgn, radix); + if(upper) sntoupper(&s[si], nlen); + si += nlen; + + int lpad = fwidth - (int)nlen; + if(lpad > 0) + { + if(lpad + osi >= limit) lpad = (limit - osi - 1); + memmove(&s[osi + lpad], &s[osi], nlen); + memset(&s[osi], zpad ? '0' : ' ', lpad); + si += lpad; + } + } break; + case 's': { + const char *str = va_arg(ap, char*); + size_t slen = strlen(str); + size_t wlen = slen > limit - si ? limit - si : slen; + for(size_t i = 0; i < wlen; i++) + s[si++] = str[i]; + } break; + } + } + s[si] = 0; + return s; +} diff --git a/lib/sfmt.d b/lib/sfmt.d new file mode 100644 index 0000000..f462cea --- /dev/null +++ b/lib/sfmt.d @@ -0,0 +1 @@ +lib/sfmt.o: lib/sfmt.c lib/string.h lib/format.h diff --git a/lib/string.c b/lib/string.c new file mode 100644 index 0000000..4bb1bad --- /dev/null +++ b/lib/string.c @@ -0,0 +1,16 @@ +#include "string.h" + +size_t strlen(const char *s) { + size_t l = 0; + for(; *s != 0; s++, l++); + return l; +} + +int strcmp(const char *a, const char *b) +{ + size_t i = 0; + for(; a[i] != 0 && b[i] != 0; i++) { + if(a[i] != b[i]) return a[i] - b[i]; + } + return a[i] - b[i]; +} diff --git a/lib/string.d b/lib/string.d new file mode 100644 index 0000000..dae7158 --- /dev/null +++ b/lib/string.d @@ -0,0 +1 @@ +lib/string.o: lib/string.c lib/string.h diff --git a/lib/string.h b/lib/string.h new file mode 100644 index 0000000..a91ec94 --- /dev/null +++ b/lib/string.h @@ -0,0 +1,18 @@ +#ifndef JOVE_LIB_STRING_H +#define JOVE_LIB_STRING_H 1 + +#include + +int toupper(int c); +char *stoupper(char *s); +char *sntoupper(char *s, size_t limit); + +size_t strlen(const char *s); + +void *memset(void *dest, int c, size_t n); +void *memcpy(void *dest, const void *src, size_t n); +void *memmove(void *dest, const void *src, size_t n); +int memcmp(const void *a, const void *b, size_t n); +int strcmp(const char *a, const char *b); + +#endif diff --git a/lib/toupper.c b/lib/toupper.c new file mode 100644 index 0000000..807eb38 --- /dev/null +++ b/lib/toupper.c @@ -0,0 +1,26 @@ +#include "string.h" + +int +toupper(int c) +{ + if(c >= 'a' && c <= 'z') + c -= ('a' - 'A'); + return c; +} + +char* +stoupper(char *s) +{ + char *o = s; + for(; *s != 0; s++) + *s = toupper(*s); + return o; +} + +char* +sntoupper(char *s, size_t limit) +{ + for(size_t i = 0; i < limit; i++) + s[i] = toupper(s[i]); + return s; +} diff --git a/lib/toupper.d b/lib/toupper.d new file mode 100644 index 0000000..72e73f9 --- /dev/null +++ b/lib/toupper.d @@ -0,0 +1 @@ +lib/toupper.o: lib/toupper.c lib/string.h -- cgit v1.2.1