diff options
Diffstat (limited to 'libc')
| -rw-r--r-- | libc/Makefile | 1 | ||||
| -rw-r--r-- | libc/inc/assert.h | 3 | ||||
| -rw-r--r-- | libc/inc/mem.h | 20 | ||||
| -rw-r--r-- | libc/inc/stack.h | 28 | ||||
| -rw-r--r-- | libc/inc/sys.h | 38 | ||||
| -rw-r--r-- | libc/mem.c | 355 | ||||
| -rw-r--r-- | libc/stack.c | 125 |
7 files changed, 465 insertions, 105 deletions
diff --git a/libc/Makefile b/libc/Makefile index 1a8e0f0..a3d1300 100644 --- a/libc/Makefile +++ b/libc/Makefile @@ -10,6 +10,7 @@ COBJS = str.o \ cpu.o \ sys.o \ list.o \ + stack.o \ random.o CC = ccache ../cross/opt/bin/i686-elf-gcc LD = ccache ../cross/opt/bin/i686-elf-ld diff --git a/libc/inc/assert.h b/libc/inc/assert.h index 3e45f44..e42fc5a 100644 --- a/libc/inc/assert.h +++ b/libc/inc/assert.h @@ -9,7 +9,8 @@ #include <proc.h> #define assert(exp) \ if (!(exp)) { \ - printf("%s:%d: %s: Assertion '%s' failed\n", __FILE__, __LINE__, __func__, #exp); \ + printf("%s:%d: %s: Kernel assertion '%s' failed\n", __FILE__, __LINE__, __func__, \ + #exp); \ struct proc *assert_proc = proc_current(); \ if (assert_proc) \ proc_exit(assert_proc, 1); \ diff --git a/libc/inc/mem.h b/libc/inc/mem.h index 15505fd..e35ee62 100644 --- a/libc/inc/mem.h +++ b/libc/inc/mem.h @@ -5,16 +5,21 @@ #include <def.h> -// Huh +int malloc_allocated; + +void *malloc_debug(u32 size, const char *file, int line, const char *func, const char *inp); +void free_debug(void *ptr, const char *file, int line, const char *func, const char *inp); +#define malloc(size) malloc_debug(size, __FILE__, __LINE__, __func__, #size) +#define free(ptr) free_debug(ptr, __FILE__, __LINE__, __func__, #ptr) + +/* void *_malloc(u32 size); */ +/* void _free(void *ptr); */ +/* #define malloc(size) _malloc(size) */ +/* #define free(ptr) _free(ptr) */ + #ifdef kernel -#define HEAP_SIZE 0x10000 -#define HEAP_MAGIC 0x42 void heap_init(u32 start); -void *malloc(u32 size); -void free(void *ptr); #elif defined(userspace) -void *malloc(u32 size); -void free(void *ptr); #else #error "No lib target specified. Please use -Dkernel or -Duserspace" #endif @@ -23,5 +28,6 @@ void *memcpy(void *dest, const void *src, u32 n); void *memset(void *dest, int val, u32 n); void *memchr(void *src, int c, u32 n); int memcmp(const void *s1, const void *s2, u32 n); +int mememp(const u8 *buf, u32 n); #endif diff --git a/libc/inc/stack.h b/libc/inc/stack.h new file mode 100644 index 0000000..16725f8 --- /dev/null +++ b/libc/inc/stack.h @@ -0,0 +1,28 @@ +// MIT License, Copyright (c) 2020 Marvin Borner + +#ifndef STACK_H +#define STACK_H + +#include <def.h> + +struct stack_node { + void *data; + int nonce; + struct stack_node *next; + struct stack_node *prev; +}; + +struct stack { + struct stack_node *tail; +}; + +struct stack *stack_new(); +void stack_destroy(struct stack *stack); +u32 stack_empty(struct stack *stack); +u32 stack_push_bot(struct stack *stack, void *data); +u32 stack_push(struct stack *stack, void *data); +void *stack_pop(struct stack *stack); +void *stack_peek(struct stack *stack); +void stack_clear(struct stack *stack); + +#endif diff --git a/libc/inc/sys.h b/libc/inc/sys.h index 3145432..14f83dd 100644 --- a/libc/inc/sys.h +++ b/libc/inc/sys.h @@ -20,11 +20,6 @@ enum sys { SYS_EXIT, // Exit current process // TODO: Free all memory of process SYS_YIELD, // Switch to next process SYS_TIME, // Get kernel time - SYS_REGISTER, // Register for event - SYS_UNREGISTER, // Unregister event - SYS_SEND, // Send message to process - SYS_RECEIVE, // Receive message (non-blocking/sync) - SYS_GETPID, // Get the process ID SYS_NET_OPEN, // Open network socket SYS_NET_CLOSE, // Close network socket SYS_NET_CONNECT, // Connect to destination @@ -94,22 +89,33 @@ int sysv(enum sys num, ...); #define yield() (int)sys0(SYS_YIELD) #define time() (u32) sys0(SYS_TIME) -#define event_register(id) sys1(SYS_REGISTER, (int)(id)) -#define event_unregister(id) sys1(SYS_UNREGISTER, (int)(id)) +static inline u32 getpid() +{ + u32 buf = 0; + read("/proc/self/pid", &buf, 0, sizeof(buf)); + return buf; +} -#define msg_send(pid, type, msg) sys3(SYS_SEND, (int)(pid), (int)(type), (int)(msg)) -#define msg_receive() (struct message *)sys0(SYS_RECEIVE) -#define getpid() (int)sys0(SYS_GETPID) -static inline struct message *msg_receive_loop() +// Hacky one-digit solution - TODO! +#include <mem.h> +#include <str.h> +static inline u32 pidof(const char *name) { - struct message *msg; - while (!(msg = msg_receive())) - yield(); - return msg; + u32 curr = 1; + char buf[32] = { 0 }; + char *path = (char *)"/proc/1/name"; // AAH + while (read(path, buf, 0, 32)) { + if (!strcmp(name, buf)) + return curr; + + curr++; + path[7]++; + } + + return 0; } // Simple read wrapper -#include <mem.h> static inline void *sread(const char *path) { struct stat s = { 0 }; @@ -1,5 +1,6 @@ // MIT License, Copyright (c) 2020 Marvin Borner +#include <assert.h> #include <def.h> #include <mem.h> #include <sys.h> @@ -68,126 +69,318 @@ int memcmp(const void *s1, const void *s2, u32 n) return 0; } -#define ALIGNMENT 16ul -#define ALIGN_TYPE char -#define ALIGN_INFO sizeof(ALIGN_TYPE) * 16 +int mememp(const u8 *buf, u32 n) +{ + return buf[0] == 0 && !memcmp(buf, buf + 1, n - 1); +} -#define ALIGN(ptr) \ - if (ALIGNMENT > 1) { \ - u32 diff; \ - ptr = (void *)((u32)ptr + ALIGN_INFO); \ - diff = (u32)ptr & (ALIGNMENT - 1); \ - if (diff != 0) { \ - diff = ALIGNMENT - diff; \ - ptr = (void *)((u32)ptr + diff); \ - } \ - *((ALIGN_TYPE *)((u32)ptr - ALIGN_INFO)) = diff + ALIGN_INFO; \ - } +/** + * Heap allocator + */ + +#ifdef kernel -#define UNALIGN(ptr) \ - if (ALIGNMENT > 1) { \ - u32 diff = *((ALIGN_TYPE *)((u32)ptr - ALIGN_INFO)); \ - if (diff < (ALIGNMENT + ALIGN_INFO)) { \ - ptr = (void *)((u32)ptr - diff); \ - } \ +int malloc_allocated = 0; + +#define HEAP_MAGIC 0x42424242 +#define HEAP_INIT_SIZE 0xff000000 +#define HEAP_MIN_SIZE HEAP_INIT_SIZE +#define MIN_ALLOC_SZ 4 +#define BIN_COUNT 9 +#define BIN_MAX_IDX (BIN_COUNT - 1) +#define OVERHEAD (sizeof(struct h_footer) + sizeof(struct h_node)) +/* #define MIN_WILDERNESS 0x2000 */ +/* #define MAX_WILDERNESS 0x1000000 */ + +struct h_node { + u32 magic; + u32 hole; + u32 size; + struct h_node *next; + struct h_node *prev; +}; + +struct h_footer { + struct h_node *header; +}; + +struct h_bin { + struct h_node *head; +}; + +struct heap { + u32 start; + u32 end; + struct h_bin bins[BIN_COUNT]; +}; + +void node_add(struct h_bin *bin, struct h_node *node) +{ + node->magic = HEAP_MAGIC; + node->next = NULL; + node->prev = NULL; + if (!bin->head) { + bin->head = node; + return; + } + struct h_node *curr = bin->head; + struct h_node *prev = NULL; + while (curr && curr->size <= node->size) { + prev = curr; + curr = curr->next; } + if (!curr) { + prev->next = node; + node->prev = prev; + } else if (prev) { + node->next = curr; + prev->next = node; + node->prev = prev; + curr->prev = node; + } else { + node->next = bin->head; + bin->head->prev = node; + bin->head = node; + } +} -#ifdef kernel +void node_remove(struct h_bin *bin, struct h_node *node) +{ + if (!bin->head) + return; + if (bin->head == node) { + bin->head = bin->head->next; + return; + } -static u32 *heap; -static u32 index; + struct h_node *temp = bin->head->next; + while (temp) { + if (temp == node) { + if (!temp->next) { + temp->prev->next = NULL; + } else { + temp->prev->next = temp->next; + temp->next->prev = temp->prev; + } + return; + } + temp = temp->next; + } +} -void heap_init(u32 start) +struct h_node *node_best_fit(struct h_bin *bin, u32 size) { - heap = (u32 *)start; - for (int i = 0; i < HEAP_SIZE; i++) - heap[i] = 0; - heap[0] = HEAP_MAGIC; - index = 1; + if (!bin->head) + return NULL; + + struct h_node *temp = bin->head; + while (temp) { + if (temp->size >= size) + return temp; + temp = temp->next; + } + return NULL; } -int count() +struct h_node *node_last(struct h_bin *bin) { - int i = 0; - u32 *iterator = heap + 1; - do { - iterator += iterator[0] + 1; - i++; - } while (iterator[0] != 0); - return i; + struct h_node *temp = bin->head; + while (temp->next) + temp = temp->next; + return temp; } -// TODO: Identify by pid (for freeing) -void *malloc(u32 size) +struct h_footer *node_foot(struct h_node *node) { - if (size < 1) - return NULL; + return (struct h_footer *)((char *)node + sizeof(*node) + node->size); +} - size = size + ALIGNMENT + ALIGN_INFO; +void node_create_foot(struct h_node *head) +{ + struct h_footer *foot = node_foot(head); + foot->header = head; +} - heap[index] = size; - index += size + 1; +u32 bin_index(u32 sz) +{ + u32 index = 0; + sz = sz < 4 ? 4 : sz; + while (sz >>= 1) + index++; + index -= 2; + if (index > BIN_MAX_IDX) + index = BIN_MAX_IDX; + return index; +} - void *p = (void *)(heap + index - size); - ALIGN(p); +/* struct h_node *wilderness_get(struct heap *heap) */ +/* { */ +/* struct h_footer *wild_foot = (struct h_footer *)((char *)heap->end - sizeof(*wild_foot)); */ +/* return wild_foot->header; */ +/* } */ - return p; +u32 expand(struct heap *heap, u32 sz) +{ + (void)heap; + (void)sz; + return 0; } -// TODO: Implement free, realloc and find_smallest_hole -void free(void *ptr) +u32 contract(struct heap *heap, u32 sz) { - (void)ptr; - /* UNALIGN(ptr); */ + (void)heap; + (void)sz; + return 0; } -void *realloc(void *ptr, u32 size) +static struct heap heap = { 0 }; +void heap_init(u32 start) { - (void)size; - return ptr; + struct h_node *init_region = (struct h_node *)start; + init_region->hole = 1; + init_region->size = HEAP_INIT_SIZE - OVERHEAD; + node_create_foot(init_region); + node_add(&heap.bins[bin_index(init_region->size)], init_region); + heap.start = start; + heap.end = start + HEAP_INIT_SIZE; } -#elif defined(userspace) +void *_malloc(u32 size) +{ + malloc_allocated += size; + u32 index = bin_index(size); + struct h_bin *temp = (struct h_bin *)&heap.bins[index]; + struct h_node *found = node_best_fit(temp, size); -#define HEAP_SIZE 100000 + while (!found) { + assert(index + 1 < BIN_COUNT); -#define kmalloc(n) (void *)sys1(SYS_MALLOC, n) -#define kfree(ptr) (void)(sys1(SYS_FREE, (int)ptr)) + temp = &heap.bins[++index]; + found = node_best_fit(temp, size); + } -/* static u32 *heap = NULL; */ -/* static u32 index = 0; */ -/* static u32 malloced = 0; */ + assert(found->magic == HEAP_MAGIC); -// TODO: Fix userspace malloc (for size > HEAP_SIZE)! -void *malloc(u32 size) -{ - return kmalloc(size); + if ((found->size - size) > (OVERHEAD + MIN_ALLOC_SZ)) { + struct h_node *split = (struct h_node *)(((char *)found + OVERHEAD) + size); + split->magic = HEAP_MAGIC; + split->size = found->size - size - OVERHEAD; + split->hole = 1; - /* if (size < 1) */ - /* return NULL; */ + node_create_foot(split); - /* size = size + ALIGNMENT + ALIGN_INFO; */ + u32 new_idx = bin_index(split->size); - /* if (!malloced || size > malloced) { */ - /* heap = kmalloc(HEAP_SIZE); */ - /* malloced = HEAP_SIZE; */ + node_add(&heap.bins[new_idx], split); + + found->size = size; + node_create_foot(found); + } + + found->hole = 0; + node_remove(&heap.bins[index], found); + + // TODO: Implement expand/contract + /* struct h_node *wild = wilderness_get(&heap); */ + /* if (wild->size < MIN_WILDERNESS) { */ + /* assert(expand(&heap, 0x1000)); */ + /* } else if (wild->size > MAX_WILDERNESS) { */ + /* assert(contract(&heap, 0x1000)); */ /* } */ - /* malloced -= size; */ - /* heap[index] = size; */ - /* index += size + 1; */ + found->prev = NULL; + found->next = NULL; + return &found->next; +} + +void _free(void *p) +{ + if (!p) + return; + + struct h_bin *list; + struct h_footer *new_foot, *old_foot; + + struct h_node *head = (struct h_node *)((char *)p - 12); + assert(head->magic == HEAP_MAGIC && head->hole == 0); + malloc_allocated -= head->size; + if (head == (struct h_node *)(u32 *)heap.start) { + head->hole = 1; + node_add(&heap.bins[bin_index(head->size)], head); + return; + } + + struct h_node *next = (struct h_node *)((char *)node_foot(head) + sizeof(struct h_footer)); + struct h_footer *f = (struct h_footer *)((char *)head - sizeof(struct h_footer)); + struct h_node *prev = f->header; + + if (prev->hole) { + list = &heap.bins[bin_index(prev->size)]; + node_remove(list, prev); + + prev->size += OVERHEAD + head->size; + new_foot = node_foot(head); + new_foot->header = prev; + + head = prev; + } + + if (next->hole) { + list = &heap.bins[bin_index(next->size)]; + node_remove(list, next); + + head->size += OVERHEAD + next->size; + + old_foot = node_foot(next); + old_foot->header = 0; + next->size = 0; + next->hole = 0; + + new_foot = node_foot(head); + new_foot->header = head; + } + + head->hole = 1; + node_add(&heap.bins[bin_index(head->size)], head); +} - /* void *p = (void *)(heap + index - size); */ - /* ALIGN(p); */ +#elif defined(userspace) + +#define kmalloc(n) (void *)sys1(SYS_MALLOC, n) +#define kfree(ptr) (void)(sys1(SYS_FREE, (int)ptr)) + +void *_malloc(u32 size) +{ + return kmalloc(size); +} - /* return p; */ +void _free(void *ptr) +{ + kfree(ptr); } -// TODO: Implement free, realloc and find_smallest_hole -void free(void *ptr) +#endif + +void *malloc_debug(u32 size, const char *file, int line, const char *func, const char *inp) { - (void)ptr; - /* UNALIGN(ptr); */ + void *ret = _malloc(size); +#ifdef kernel + printf("K"); +#else + printf("U"); +#endif + printf("MALLOC\t%s:%d: %s: 0x%x %dB (%s)\n", file, line, func, ret, size, inp); + return ret; } +void free_debug(void *ptr, const char *file, int line, const char *func, const char *inp) +{ +#ifdef kernel + printf("K"); +#else + printf("U"); #endif + printf("FREE\t%s:%d: %s: 0x%x (%s)\n", file, line, func, ptr, inp); + if (ptr) + _free(ptr); +} diff --git a/libc/stack.c b/libc/stack.c new file mode 100644 index 0000000..c47dd59 --- /dev/null +++ b/libc/stack.c @@ -0,0 +1,125 @@ +// MIT License, Copyright (c) 2020 Marvin Borner + +#include <def.h> +#include <mem.h> +#include <stack.h> + +static int nonce = 0; + +struct stack *stack_new() +{ + struct stack *stack = malloc(sizeof(*stack)); + stack->tail = NULL; + return stack; +} + +void stack_destroy(struct stack *stack) +{ + struct stack_node *iterator = stack->tail; + while (iterator) { + if (!iterator->prev) { + free(iterator); + break; + } + iterator = iterator->prev; + free(iterator->next); + } + stack->tail = NULL; + free(stack); + stack = NULL; +} + +struct stack_node *stack_new_node() +{ + struct stack_node *node = malloc(sizeof(*node)); + node->data = NULL; + node->prev = NULL; + node->next = NULL; + node->nonce = nonce++; + return node; +} + +u32 stack_push_bot_node(struct stack *stack, struct stack_node *node) +{ + if (!stack || !node) + return 0; + + if (stack->tail) { + struct stack_node *iterator = stack->tail; + while (iterator) { + if (!iterator->prev) + break; + iterator = iterator->prev; + } + iterator->prev = node; + node->next = iterator; + } else { + stack->tail = node; + } + + return 1; +} + +u32 stack_push_node(struct stack *stack, struct stack_node *node) +{ + if (!stack || !node) + return 0; + + if (stack->tail) { + stack->tail->next = node; + node->prev = stack->tail; + stack->tail = node; + } else { + stack->tail = node; + } + + return 1; +} + +u32 stack_empty(struct stack *stack) +{ + return !stack->tail; +} + +u32 stack_push_bot(struct stack *stack, void *data) +{ + struct stack_node *node = stack_new_node(); + node->data = data; + return stack_push_bot_node(stack, node); +} + +u32 stack_push(struct stack *stack, void *data) +{ + struct stack_node *node = stack_new_node(); + node->data = data; + return stack_push_node(stack, node); +} + +void *stack_pop(struct stack *stack) +{ + if (!stack || !stack->tail) + return NULL; + + struct stack_node *prev = stack->tail; + + stack->tail->prev->next = NULL; + stack->tail = stack->tail->prev; + + void *data = prev->data; + free(prev); + return data; +} + +void *stack_peek(struct stack *stack) +{ + if (!stack || !stack->tail) + return NULL; + + return stack->tail; +} + +void stack_clear(struct stack *stack) +{ + while (stack_pop(stack)) + ; +} |