intrusive circular doubly linked list

10 files changed, 191 insertions, 125 deletions

diff --git a/Makefile b/Makefile
index 00afb99..7f773d7 100644
--- a/Makefile
+++ b/Makefile
@@ -7,8 +7,8 @@ LD = $(ARCH)ld
 OBJDUMP = $(ARCH)objcopy
 OBJCOPY = $(ARCH)objdump
 
-W := -Wall -Werror -Wextra -Wshadow -Wpointer-arith -Wcast-align
-#W := -pedantic -Wmissing-prototypes -Wmissing-declarations
+W := -Wall -Werror -Wextra -Wshadow -Wcast-align
+# W:= -Wpointer-arith -pedantic -Wmissing-prototypes -Wmissing-declarations
 W += -Wwrite-strings -Wredundant-decls -Wnested-externs -Winline -Wno-long-long
 W += -Wconversion -Wstrict-prototypes
 WNO := -Wno-error=unused-parameter -Wno-error=unused-variable
diff --git a/kernel/include/containter_of.h b/kernel/include/containter_of.h
new file mode 100644
index 0000000..766847a
--- /dev/null
+++ b/kernel/include/containter_of.h
@@ -0,0 +1,40 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef CONTAINER_OF
+#define CONTAINER_OF
+
+#define static_assert(expr, ...) __static_assert(expr, ##__VA_ARGS__, #expr)
+#define __static_assert(expr, msg, ...) _Static_assert(expr, msg)
+#define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
+#define typeof_member(T, m)	typeof(((T*)0)->m)
+
+/**
+ * container_of - cast a member of a structure out to the containing structure
+ * @ptr:	the pointer to the member.
+ * @type:	the type of the container struct this is embedded in.
+ * @member:	the name of the member within the struct.
+ *
+ */
+#define container_of(ptr, type, member) ({				\
+	void *__mptr = (void *)(ptr);					\
+	static_assert(__same_type(*(ptr), ((type *)0)->member) ||	\
+		      __same_type(*(ptr), void),			\
+		      "pointer type mismatch in container_of()");	\
+	((type *)(__mptr - offsetof(type, member))); })
+
+/**
+ * container_of_safe - cast a member of a structure out to the containing structure
+ * @ptr:	the pointer to the member.
+ * @type:	the type of the container struct this is embedded in.
+ * @member:	the name of the member within the struct.
+ *
+ * If IS_ERR_OR_NULL(ptr), ptr is returned unchanged.
+ */
+#define container_of_safe(ptr, type, member) ({				\
+	void *__mptr = (void *)(ptr);					\
+	static_assert(__same_type(*(ptr), ((type *)0)->member) ||	\
+		      __same_type(*(ptr), void),			\
+		      "pointer type mismatch in container_of_safe()");	\
+	IS_ERR_OR_NULL(__mptr) ? ERR_CAST(__mptr) :			\
+		((type *)(__mptr - offsetof(type, member))); })
+
+#endif
diff --git a/kernel/include/ext2.h b/kernel/include/ext2.h
index 1acdb18..b9222df 100644
--- a/kernel/include/ext2.h
+++ b/kernel/include/ext2.h
@@ -121,6 +121,18 @@ struct ext2_dentry_t {
 };
 typedef struct ext2_dentry_t ext2_dentry_t;
 
+struct path_t {
+	char* name;
+	list_t list;
+};
+typedef struct path_t path_t;
+
+struct dentry_list_t {
+	ext2_dentry_t ext2_dentry;
+	list_t list;
+};
+typedef struct dentry_list_t dentry_list_t;
+
 extern ext2_superblock_t* ext2_superblock;
 
 // size of structs
@@ -135,9 +147,9 @@ void read_block(uint32_t block_num, void* block_ptr);
 void read_superblock(ext2_superblock_t* ext2_superblock);
 void read_bg_desc(uint32_t bg_desc, ext2_bg_desc_t* ext2_bg_desc);
 void read_inode(uint32_t starting_block_num, uint32_t inode_index, ext2_inode_t* ext2_inode);
-list_t* directory_to_entries(uint32_t inode);
+dentry_list_t* directory_to_entries(uint32_t inode);
 char* files_to_buffer(uint32_t inode);
-list_t* path_to_list(const char* path);
+path_t* path_to_list(const char* path);
 uint32_t path_to_inode(const char* path);
 void ls(uint32_t inode);
 void print(uint32_t inode);
diff --git a/kernel/include/libk/list.h b/kernel/include/libk/list.h
index f6a97f8..1cd9928 100644
--- a/kernel/include/libk/list.h
+++ b/kernel/include/libk/list.h
@@ -1,14 +1,37 @@
 #ifndef LIST_H
 #define LIST_H
 
+#include <containter_of.h>
+
 struct list_t {
 	struct list_t* next;
-	void* data;
+	struct list_t* prev;
 };
 typedef struct list_t list_t;
 
-void add_to_list_head(list_t** ptr, void* data);
-void add_to_list_tail(list_t** ptr, void* data);
-void free_list(list_t** ptr);
+void add_to_list(list_t* head, list_t* prev, list_t* next);
+void free_node(list_t* head);
+
+#define INIT_LIST(name) \
+	name.next = &name; \
+	name.prev = &name;
+
+#define list_for_each(pos, head) \
+	for (pos = head->next; pos != head; pos = pos->next)
+
+#define list_next_entry(pos, member) \
+	container_of(pos->member.next, typeof(*pos), member)
+
+#define list_prev_entry(pos, member) \
+	container_of(pos->member.prev, typeof(*pos), member)
+
+#define list_for_each_entry(pos, head, member) \
+        for (pos = container_of(head->next, typeof(*pos), member); pos != container_of(head, typeof(*pos), member); pos = container_of(pos->member.next, typeof(*pos), member))
+
+#define list_for_each_entry_prev(pos, head, member) \
+        for (pos = container_of(head->prev, typeof(*pos), member); pos != container_of(head, typeof(*pos), member); pos = container_of(pos->member.prev, typeof(*pos), member))
+
+#define list_is_empty(pos) \
+	(pos == pos->next)
 
 #endif
diff --git a/kernel/include/multiboot2.h b/kernel/include/multiboot2.h
index 994dbc5..ff91092 100644
--- a/kernel/include/multiboot2.h
+++ b/kernel/include/multiboot2.h
@@ -2,6 +2,7 @@
 #define MULTIBOOT2_H
 
 #include <types.h>
+#include <libk/list.h>
 
 struct mb2_tag_header {
 	uint32_t type;
@@ -46,6 +47,14 @@ struct mb2_tag_module {
 };
 typedef struct mb2_tag_module mb2_tag_module;
 
+struct mmap_t {
+	mb2_tag_mmap_entry mmap_entry;
+	list_t list;
+};
+typedef struct mmap_t mmap_t;
+
+extern mmap_t mmap;
+
 
 // multiboot2 magic check
 #define MB2_MAGIC		0x36D76289
diff --git a/kernel/src/boot/multiboot2.c b/kernel/src/boot/multiboot2.c
index 21da783..3e6c6d4 100644
--- a/kernel/src/boot/multiboot2.c
+++ b/kernel/src/boot/multiboot2.c
@@ -14,6 +14,8 @@
 
 mb2_tag_module* ext2_module;
 
+mmap_t mmap;
+
 void init_fb(mb2_tag_fb* tag_fb)
 {
 	main_fb.addr = tag_fb->framebuffer_addr;
@@ -31,31 +33,14 @@ void init_fb(mb2_tag_fb* tag_fb)
 
 void init_mmap(mb2_tag_mmap* tag_mmap)
 {
-	list_t* mmap = NULL;
+	INIT_LIST(mmap.list)
 
 	// get data and store it into list
 	for (size_t i = sizeof(mb2_tag_mmap); i < tag_mmap->size; i += sizeof(mb2_tag_mmap_entry)) {
-		mb2_tag_mmap_entry* mmap_entry;
-		mmap_entry = (mb2_tag_mmap_entry*)kalloc(sizeof(mb2_tag_mmap_entry));
-		memcpy(mmap_entry, (char*)tag_mmap + i, sizeof(mb2_tag_mmap_entry));
-		add_to_list_head(&mmap, mmap_entry);
-	}
-
-	// print data from list
-	for (list_t* tmp = mmap; tmp != NULL; tmp = tmp->next) {
-		mb2_tag_mmap_entry* mmap_entry;
-		mmap_entry = tmp->data;
-//		printf("base_addr: 0x%x, length: 0x%x, type: %d\n", mmap_entry->base_addr, mmap_entry->length, mmap_entry->type);
-		mmap_entry = mmap_entry;
+		mmap_t* curr_mmap_entry = (mmap_t*)kalloc(sizeof(mmap_t));
+		memcpy(&curr_mmap_entry->mmap_entry, (char*)tag_mmap + i, sizeof(mb2_tag_mmap_entry));
+		add_to_list(&curr_mmap_entry->list, &mmap.list, mmap.list.next);
 	}
-
-	// free data
-	for (list_t* tmp = mmap; tmp != NULL; tmp = tmp->next) {
-		kfree(tmp->data);
-	}
-
-	// free list
-	free_list(&mmap);
 }
 
 void init_module(mb2_tag_module* tag_module)
diff --git a/kernel/src/fs/ext2.c b/kernel/src/fs/ext2.c
index d38a57e..2f003ef 100644
--- a/kernel/src/fs/ext2.c
+++ b/kernel/src/fs/ext2.c
@@ -52,9 +52,15 @@ void read_inode(uint32_t starting_block_num, uint32_t inode_index, ext2_inode_t*
 	memcpy(ext2_inode, (char*)block + block_index * INODE_SIZE, sizeof(ext2_inode_t));
 }
 
-list_t* directory_to_entries(uint32_t inode)
+dentry_list_t* directory_to_entries(uint32_t inode)
 {
-	list_t* list = NULL;
+	dentry_list_t* dentry_list = (dentry_list_t*)kalloc(sizeof(dentry_list_t));
+	INIT_LIST(dentry_list->list);
+
+	if (inode < 2) {
+		return dentry_list;
+	}
+
 
 	uint32_t bg_desc = (inode - 1) / ext2_superblock->inodes_per_group;
 	uint32_t inode_index = (inode - 1) % ext2_superblock->inodes_per_group;
@@ -71,7 +77,7 @@ list_t* directory_to_entries(uint32_t inode)
 
 	// if it is not directory
 	if (!(ext2_inode->type_perms & TYPE_DIR))
-		return list;
+		return dentry_list;
 
 	// read inode contents
 	for (size_t i = 0; i < 12; i++) {
@@ -85,26 +91,25 @@ list_t* directory_to_entries(uint32_t inode)
 		// parse block
 		for (size_t block_offset = 0; block_offset < BLOCK_SIZE;) {
 			// get dentry header
-			ext2_dentry_t* ext2_dentry;
-			ext2_dentry = (ext2_dentry_t*)kalloc(sizeof(ext2_dentry_t));
-			memcpy(ext2_dentry, (char*)block + block_offset, sizeof(ext2_dentry_t) - sizeof(char*));
+			dentry_list_t* ext2_dentry_list = (dentry_list_t*)kalloc(sizeof(dentry_list_t));
+			memcpy(&ext2_dentry_list->ext2_dentry, (char*)block + block_offset, sizeof(ext2_dentry_t) - sizeof(char*));
 
 			// dentry is unused
-			if (ext2_dentry->inode == 0) {
-				kfree(ext2_dentry);
+			if (ext2_dentry_list->ext2_dentry.inode == 0) {
+				kfree(ext2_dentry_list);
 				continue;
 			}
 
 			// get dentry name
-			ext2_dentry->name = (char*)kalloc(ext2_dentry->name_length_lower + 1);
-			memcpy(ext2_dentry->name, (char*)block + block_offset + sizeof(ext2_dentry_t) - sizeof(char*), ext2_dentry->name_length_lower);
-			ext2_dentry->name[ext2_dentry->name_length_lower] = '\0';
+			ext2_dentry_list->ext2_dentry.name = (char*)kalloc(ext2_dentry_list->ext2_dentry.name_length_lower + 1);
+			memcpy(ext2_dentry_list->ext2_dentry.name, (char*)block + block_offset + sizeof(ext2_dentry_t) - sizeof(char*), ext2_dentry_list->ext2_dentry.name_length_lower);
+			ext2_dentry_list->ext2_dentry.name[ext2_dentry_list->ext2_dentry.name_length_lower] = '\0';
 
 			// put dentry in list
-			add_to_list_head(&list, ext2_dentry);
+			add_to_list(&ext2_dentry_list->list, &dentry_list->list, dentry_list->list.next);
 
 			// offset
-			block_offset += ext2_dentry->size;
+			block_offset += ext2_dentry_list->ext2_dentry.size;
 		}
 	}
 
@@ -112,7 +117,7 @@ list_t* directory_to_entries(uint32_t inode)
 	kfree(ext2_bg_desc);
 	kfree(ext2_inode);
 
-	return list;
+	return dentry_list;
 }
 
 char* files_to_buffer(uint32_t inode)
@@ -145,27 +150,30 @@ char* files_to_buffer(uint32_t inode)
 	return data;
 }
 
-list_t* path_to_list(const char* path)
+path_t* path_to_list(const char* path)
 {
 	size_t i, j;
-	list_t* divided_path = NULL;
+	path_t* divided_path = (path_t*)kalloc(sizeof(path_t));
+	INIT_LIST(divided_path->list)
 
 	size_t n = strlen(path);
 	for (i = 0, j = 0; i <= n; i++) {
 		if (i == n || path[i] == '/') {
 			// add data before slash
 			if (i != j) {
-				char* ptr = (char*)kalloc(sizeof(char) * (uint32_t)(i - j + 1));
-				memcpy(ptr, path + j, i - j);
-				ptr[i - j] = '\0';
-				add_to_list_tail(&divided_path, ptr);
+				path_t* curr_path = (path_t*)kalloc(sizeof(path_t));
+				curr_path->name = (char*)kalloc(sizeof(char) * (uint32_t)(i - j + 1));
+				memcpy(curr_path->name, path + j, i - j);
+				curr_path->name[i - j] = '\0';
+				add_to_list(&curr_path->list, &divided_path->list, divided_path->list.next);
 			}
 			// add slash
 			if (i != n) {
-				char* ptr = (char*)kalloc(sizeof(char) * 2);
-				ptr[0] = '/';
-				ptr[1] = '\0';
-				add_to_list_tail(&divided_path, ptr);
+				path_t* curr_path = (path_t*)kalloc(sizeof(path_t));
+				curr_path->name = (char*)kalloc(sizeof(char) * 2);
+				curr_path->name[0] = '/';
+				curr_path->name[1] = '\0';
+				add_to_list(&curr_path->list, &divided_path->list, divided_path->list.next);
 				j = i + 1;
 			}
 		}
@@ -174,37 +182,33 @@ list_t* path_to_list(const char* path)
 	return divided_path;
 }
 
-// only supports absolute path for now
 uint32_t path_to_inode(const char* path)
 {
 	uint32_t inode = 0;
-	list_t* divided_path = path_to_list(path);
-
-	list_t* curr_dir = divided_path;
+	path_t* divided_path = path_to_list(path);
 
 	// first entry is /
-	curr_dir = curr_dir->next;
+	path_t* curr_path = list_prev_entry(divided_path, list);
+	curr_path = list_prev_entry(curr_path, list);
 	inode = 2;
 
-	while (curr_dir != NULL) {
+	while (curr_path != divided_path) {
 		// list of dentry
-		list_t* list = directory_to_entries(inode);
+		dentry_list_t* dentry_list = directory_to_entries(inode);
 
 		// check if inode is actually a dir
-		if (list == NULL) {
+		if (list_is_empty((&dentry_list->list))) {
 			printf("not a directory\n");
 			return 0;
 		}
 
 		// iterate through all direntries
 		uint8_t ind = 1;
-		for (list_t* curr_list = list; curr_list != NULL; curr_list = curr_list->next) {
-			ext2_dentry_t* ext2_dentry;
-			ext2_dentry = curr_list->data;
-
-			if (!memcmp(curr_dir->data, ext2_dentry->name)) {
+		dentry_list_t* curr_dir;
+		list_for_each_entry_prev (curr_dir, (&dentry_list->list), list) {
+			if (!memcmp(curr_dir->ext2_dentry.name, curr_path->name)) {
 				ind = 0;
-				inode = ext2_dentry->inode;
+				inode = curr_dir->ext2_dentry.inode;
 				break;
 			}
 		}
@@ -216,9 +220,9 @@ uint32_t path_to_inode(const char* path)
 		}
 
 		// next dir
-		curr_dir = curr_dir->next;
-		if (curr_dir != NULL)
-			curr_dir = curr_dir->next;
+		curr_path = list_prev_entry(curr_path, list);
+		if (curr_path != divided_path)
+			curr_path = list_prev_entry(curr_path, list);
 	}
 
 	return inode;
@@ -226,13 +230,15 @@ uint32_t path_to_inode(const char* path)
 
 void ls(uint32_t inode)
 {
-	list_t* dir = directory_to_entries(inode);
+	dentry_list_t* dir = directory_to_entries(inode);
+	if (list_is_empty((&dir->list))) {
+		return;
+	}
 
 	printf("ls dir with inode %d:\n", inode);
-	for (list_t* tmp = dir; tmp != NULL; tmp = tmp->next) {
-		ext2_dentry_t* ext2_dentry;
-		ext2_dentry = tmp->data;
-		printf("inode: %d, name: %s\n", ext2_dentry->inode, ext2_dentry->name);
+	dentry_list_t* pos;
+	list_for_each_entry(pos, (&dir->list), list) {
+		printf("inode: %d, name: %s\n", pos->ext2_dentry.inode, pos->ext2_dentry.name);
 	}
 }
 
diff --git a/kernel/src/libk/list.c b/kernel/src/libk/list.c
index be2e4e5..cb916ab 100644
--- a/kernel/src/libk/list.c
+++ b/kernel/src/libk/list.c
@@ -1,38 +1,22 @@
 #include <libk/list.h>
 #include <heap.h>
 
-void add_to_list_head(list_t** ptr, void* data)
+void add_to_list(list_t* head, list_t* prev, list_t* next)
 {
-	list_t* node = (list_t*)kalloc(sizeof(list_t));
-	node->data = data;
-
-	node->next = *ptr;
-	*ptr = node;
-}
-
-void add_to_list_tail(list_t** ptr, void* data)
-{
-	list_t* node = (list_t*)kalloc(sizeof(list_t));
-	node->data = data;
-	node->next = NULL;
-
-	if (*ptr == NULL) {
-		*ptr = node;
-	} else {
-		list_t* tmp = *ptr;
-		while (tmp->next != NULL)
-			tmp = tmp->next;
-		tmp->next = node;
-	}
+	head->prev = prev;
+	head->next = next;
+	prev->next = head;
+	next->prev = head;
 }
 
-void free_list(list_t** ptr)
+void free_node(list_t* head)
 {
-	if (*ptr == NULL)
+	if (head->prev == head->next) {
+		head = NULL;
 		return;
-
-	for (list_t* tmp = (*ptr)->next; tmp != NULL; tmp = tmp->next) {
-		kfree(*ptr);
-		*ptr = tmp;
 	}
+
+	head->next->prev = head->prev;
+	head->prev->next = head->next;
+	head = NULL;
 }
diff --git a/kernel/src/main.c b/kernel/src/main.c
index b568f8f..ee240ae 100644
--- a/kernel/src/main.c
+++ b/kernel/src/main.c
@@ -9,6 +9,7 @@
 #include <libk/stdio.h>
 #include <libk/string.h>
 #include <libk/math.h>
+#include <libk/list.h>
 #include <disc.h>
 #include <ext2.h>
 #include <timer.h>
@@ -16,6 +17,7 @@
 #include <userspace.h>
 #include <tss.h>
 #include <serial.h>
+#include <containter_of.h>
 
 int kernel_main(mb2_tag_header* multiboot_bootinfo, uint32_t multiboot_magic);
 int kernel_main(mb2_tag_header* multiboot_bootinfo, uint32_t multiboot_magic)
@@ -28,6 +30,11 @@ int kernel_main(mb2_tag_header* multiboot_bootinfo, uint32_t multiboot_magic)
 	read_mb2(multiboot_bootinfo, multiboot_magic);
 	clear_screen(main_fb);
 // framebuffer is enabled from this point
+	mmap_t* pos;
+        list_for_each_entry(pos, (&mmap.list), list) {
+		printf("base_addr: 0x%x\n", pos->mmap_entry.base_addr);
+	}
+
 	init_keyboard();
 	init_timer(TICKS_PER_SECOND);
 	init_idt();
diff --git a/kernel/src/scheduler/process.c b/kernel/src/scheduler/process.c
index a8de836..92c6ab3 100644
--- a/kernel/src/scheduler/process.c
+++ b/kernel/src/scheduler/process.c
@@ -9,30 +9,30 @@ process_t current_process;
 void create_process(uint64_t rip, uint64_t param1, uint64_t param2)
 {
 	process_t* process = (process_t*)kalloc(sizeof(process_t));
-	registers_t regs = process->registers;
-	regs.rax = 0;
-	regs.rbx = 0;
-	regs.rcx = 0;
-	regs.rdx = 0;
-	regs.rsi = 0;
-	regs.rdi = 0;
-	regs.rsp = 0;
-	regs.rbp = 0;
-	regs.r8 = 0;
-	regs.r9 = 0;
-	regs.r10 = 0;
-	regs.r11 = 0;
-	regs.r12 = 0;
-	regs.r13 = 0;
-	regs.r14 = 0;
-	regs.r15 = 0;
-	regs.rflags = 0;
+	registers_t* regs = &process->registers;
+	regs->rax = 0;
+	regs->rbx = 0;
+	regs->rcx = 0;
+	regs->rdx = 0;
+	regs->rsi = 0;
+	regs->rdi = 0;
+	regs->rsp = 0;
+	regs->rbp = 0;
+	regs->r8 = 0;
+	regs->r9 = 0;
+	regs->r10 = 0;
+	regs->r11 = 0;
+	regs->r12 = 0;
+	regs->r13 = 0;
+	regs->r14 = 0;
+	regs->r15 = 0;
+	regs->rflags = 0;
 
 	uint64_t stack_size = 4*4096;
-	regs.rsp = (uint64_t)kalloc(4*4096) + stack_size - 8;
-	regs.rip = rip;
-	regs.rdi = param1;
-	regs.rsi = param2;
+	regs->rsp = (uint64_t)kalloc(4*4096) + stack_size - 8;
+	regs->rip = rip;
+	regs->rdi = param1;
+	regs->rsi = param2;
 	process->status = STATUS_READY;
 	process->time_using_cpu = 0;
 }