intrusive circular doubly linked list

5 files changed, 99 insertions, 117 deletions

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;
 }