aboutsummaryrefslogtreecommitdiff
path: root/kernel
diff options
context:
space:
mode:
Diffstat (limited to 'kernel')
-rw-r--r--kernel/BUILD.bazel37
-rw-r--r--kernel/boot.h21
-rw-r--r--kernel/conf.h.in4
-rw-r--r--kernel/kernel.c57
-rw-r--r--kernel/mem.h4
-rw-r--r--kernel/mem/vmm.c47
-rw-r--r--kernel/mmap.c51
-rw-r--r--kernel/mmap.h7
-rw-r--r--kernel/multiboot2.c50
-rw-r--r--kernel/sched.hpp8
-rw-r--r--kernel/sched/roundrobin.cpp21
-rw-r--r--kernel/sched/test_roundrobin.cc50
-rw-r--r--kernel/sched/test_taskqueue.cc122
-rw-r--r--kernel/task.h78
14 files changed, 557 insertions, 0 deletions
diff --git a/kernel/BUILD.bazel b/kernel/BUILD.bazel
new file mode 100644
index 0000000..e7ed087
--- /dev/null
+++ b/kernel/BUILD.bazel
@@ -0,0 +1,37 @@
+load("//tools:configure_file.bzl", "configure_file")
+
+configure_file(
+ name = "conf",
+ template = "conf.h.in",
+)
+
+cc_binary(
+ name = "glitch.elf",
+ srcs = [
+ "boot.h",
+ "kernel.c",
+ "mem.h",
+ "mem/vmm.c",
+ "mmap.c",
+ "mmap.h",
+ "multiboot2.c",
+ "task.h",
+ ":conf.h",
+ ],
+ includes = ["."],
+ linkopts = [
+ "-T",
+ "$(location //arch/i386:linker.ld)",
+ ],
+ target_compatible_with = [
+ "@platforms//os:none",
+ ],
+ visibility = ["//visibility:public"],
+ deps = [
+ "//arch/i386:arch",
+ "//arch/i386:linker.ld",
+ "//devices:drivers",
+ "//grub:multiboot2",
+ "//lib/libk:k",
+ ],
+)
diff --git a/kernel/boot.h b/kernel/boot.h
new file mode 100644
index 0000000..646fb4c
--- /dev/null
+++ b/kernel/boot.h
@@ -0,0 +1,21 @@
+/* *** glitch kernel ***
+ * spdx-license-identifier: ISC
+ * description: kernel boot information
+ * */
+
+#pragma once
+
+typedef struct {
+ /* kernel command line */
+ char cmdline[64];
+
+ /* memory map */
+ unsigned bitmap[1024 * 32];
+
+ /* module */
+ unsigned module_start;
+ unsigned module_end;
+ char module_cmdline[64];
+} boot_info_t;
+
+/* TODO _Static_assert((1024 * 32 * sizeof(unsigned) * 8) == (1024 * 1024), "bitmap size check"); */
diff --git a/kernel/conf.h.in b/kernel/conf.h.in
new file mode 100644
index 0000000..61352d7
--- /dev/null
+++ b/kernel/conf.h.in
@@ -0,0 +1,4 @@
+#pragma once
+
+#define VERSION {VERSION}
+#define CC {CC}
diff --git a/kernel/kernel.c b/kernel/kernel.c
new file mode 100644
index 0000000..98269c1
--- /dev/null
+++ b/kernel/kernel.c
@@ -0,0 +1,57 @@
+/* *** glitch kernel ***
+ * spdx-license-identifier: ISC
+ * description: kernel entry point
+ * */
+
+#include "conf.h"
+#include "mem.h"
+#include <keyboard.h>
+#include <mouse.h>
+#include <pic.h>
+#include <ps2_controller.h>
+#include <stdio.h>
+#include <sys/cpuid.h>
+#include <uart.h>
+#include <vga.h>
+
+FILE *stdin;
+FILE *stdout;
+FILE *stderr;
+
+void
+kmain(void)
+{
+ stderr = uart_init(COM1);
+ vmm_map(0xb8000, 0xc03ff000);
+ stdout = vga_init((void *)0xc03ff000);
+
+ printf("glitch [version " VERSION "] [" CC "]\n");
+ fprintf(stderr, "glitch [version " VERSION "] [" CC "]\n");
+ {
+ struct CPUVersion v;
+
+ char vendor[13] = {'\0'};
+ unsigned int eax;
+ __get_cpuid(0, &eax, (unsigned int *)vendor, (unsigned int *)(vendor + 8), (unsigned int *)(vendor + 4));
+ __get_cpuid(1, (unsigned int *)&v, &eax, &eax, &eax);
+ printf("cpuid: %s family %u model %u stepping %u\n", vendor, family(v), model(v), v.stepping);
+ fprintf(stderr, "cpuid: %s family %u model %u stepping %u\n", vendor, family(v), model(v), v.stepping);
+ }
+
+ pic_init();
+
+ ps2_ctrl_init();
+ ps2_keyboard_init();
+ mouse_init();
+
+ pic_enable();
+ fprintf(stderr, "interrupts enabled\n");
+
+ /*
+ alloc4M();
+ char *c = (char *)0xc0700000;
+ if (*c == 0) printf("c is 0\r\n");
+ */
+
+ while (1) {}
+}
diff --git a/kernel/mem.h b/kernel/mem.h
new file mode 100644
index 0000000..e06dd21
--- /dev/null
+++ b/kernel/mem.h
@@ -0,0 +1,4 @@
+#pragma once
+
+unsigned int vmm_map(unsigned int paddr, unsigned int vaddr);
+void alloc4M();
diff --git a/kernel/mem/vmm.c b/kernel/mem/vmm.c
new file mode 100644
index 0000000..a07dd72
--- /dev/null
+++ b/kernel/mem/vmm.c
@@ -0,0 +1,47 @@
+#include "../mem.h"
+#include <paging.h>
+
+extern struct DirectoryEntry k_pagedir[1024];
+extern struct TableEntry k_ptable0x300[1024];
+
+extern const unsigned MULTIBOOT_SIZE;
+extern const unsigned VADDR_BASE;
+
+unsigned
+to_vaddr(unsigned paddr)
+{
+ return paddr + (unsigned)&VADDR_BASE - (unsigned)&MULTIBOOT_SIZE;
+}
+
+unsigned int
+vmm_map(unsigned int paddr, unsigned int vaddr)
+{
+ struct TableEntry *table;
+ const unsigned table_idx = vaddr >> 22; /* high 10 bits */
+ const unsigned entry_idx = (vaddr >> 12) & 0x3ff; /* low 10 bits */
+
+ if (paddr & 0xfff || vaddr & 0xfff) return 0;
+
+ if (k_pagedir[table_idx].present == 0) return 0;
+ table = (struct TableEntry *)to_vaddr(k_pagedir[table_idx].address << 12);
+ table[entry_idx].address = (paddr >> 12) & 0xfffff;
+ table[entry_idx].present = 1;
+ table[entry_idx].writeable = 1;
+
+ return vaddr;
+}
+
+void
+alloc4M()
+{
+ struct DirectoryEntry4MB *directory;
+
+ /* enable pse in cr4 */
+ __asm__("movl %cr4, %eax; orl $0x10, %eax; movl %eax, %cr4");
+
+ directory = (struct DirectoryEntry4MB *)&k_pagedir[0x301];
+ directory->address_low = 0x1;
+ directory->present = 1;
+ directory->writeable = 1;
+ directory->pagesize = 1;
+}
diff --git a/kernel/mmap.c b/kernel/mmap.c
new file mode 100644
index 0000000..e5d4be6
--- /dev/null
+++ b/kernel/mmap.c
@@ -0,0 +1,51 @@
+#include "mmap.h"
+#include <multiboot2.h>
+
+#ifdef DEBUG
+#include <stdio.h>
+#endif
+
+__attribute__((section(".multiboot.text"))) unsigned
+multiboot2_mmap(const struct multiboot_mmap_entry entries[], unsigned entry_count, unsigned bitmap[1024 * 32])
+{
+ unsigned i, l;
+ multiboot_uint64_t avail_frames = 0;
+ multiboot_uint64_t n_frames;
+ multiboot_uint64_t table_idx;
+
+ /* clear out the bitmap */
+ for (i = 0; i < 1024 * 32; ++i) bitmap[i] = 0;
+
+ /* loop through all the mmap_entry structures where type is MULTIBOOT_MEMORY_AVAILABLE */
+ for (i = 0; i < entry_count; ++i) {
+ if (entries[i].type != MULTIBOOT_MEMORY_AVAILABLE) continue;
+
+ /* number of frames in this entry */
+ n_frames = entries[i].len / 4096;
+ avail_frames += n_frames;
+
+#ifdef DEBUG
+ printf("mmap_entry: 0x%16llx\tlen=%12llu\t%d frames (%d blocks + %d)\n", entries[i].addr, entries[i].len, n_frames,
+ n_frames / 32, n_frames % 32);
+#endif
+
+ /* the bitmap is an array of blocks, each holding 32 (2^5) values */
+ table_idx = (entries[i].addr >> 17); /* get the upper 15 bits */
+
+ while (n_frames != 0) {
+ if (n_frames >= 32) {
+ bitmap[table_idx] = 0xffffffff;
+ table_idx++;
+ n_frames -= 32;
+ }
+ else {
+ unsigned block = bitmap[table_idx];
+ for (l = 0; l < n_frames; ++l) block |= (1 << l);
+ bitmap[table_idx] = block;
+ n_frames = 0;
+ }
+ }
+ }
+
+ return avail_frames;
+}
diff --git a/kernel/mmap.h b/kernel/mmap.h
new file mode 100644
index 0000000..13f40f2
--- /dev/null
+++ b/kernel/mmap.h
@@ -0,0 +1,7 @@
+#pragma once
+
+#include "boot.h"
+#include <multiboot2.h>
+
+__attribute__((section(".multiboot.text"))) unsigned multiboot2_mmap(const struct multiboot_mmap_entry entries[],
+ unsigned entry_count, unsigned bitmap[1024 * 32]);
diff --git a/kernel/multiboot2.c b/kernel/multiboot2.c
new file mode 100644
index 0000000..bd6250f
--- /dev/null
+++ b/kernel/multiboot2.c
@@ -0,0 +1,50 @@
+#include "mmap.h"
+
+#define ADDR(x) ((unsigned)&x - 0xc0000000 + 0x2000)
+
+boot_info_t info __attribute__((section(".init")));
+
+__attribute__((section(".multiboot.text"))) void
+multiboot_strncpy(char *dest, const char *src, unsigned n)
+{
+ unsigned i;
+ for (i = 0; i < n && src[i] != '\0'; ++i) dest[i] = src[i];
+}
+
+__attribute__((section(".multiboot.text"))) void
+multiboot2_module(struct multiboot_tag_module *tag, boot_info_t *tag_info)
+{
+ tag_info->module_start = tag->mod_start;
+ tag_info->module_end = tag->mod_end;
+ multiboot_strncpy(tag_info->module_cmdline, tag->cmdline, 64);
+}
+
+/**
+ * parse multiboot2 structures
+ */
+__attribute__((section(".multiboot.text"))) void
+__multiboot2(multiboot_uint32_t addr)
+{
+ boot_info_t *__info = (boot_info_t *)ADDR(info);
+
+ struct multiboot_tag *tag;
+ for (tag = (struct multiboot_tag *)(addr + 8); tag->type != MULTIBOOT_TAG_TYPE_END;
+ tag = (struct multiboot_tag *)((multiboot_uint8_t *)tag + ((tag->size + 7u) & ~7u))) {
+
+ switch (tag->type) {
+ case MULTIBOOT_TAG_TYPE_CMDLINE:
+ multiboot_strncpy(__info->cmdline, ((struct multiboot_tag_string *)tag)->string, 64);
+ break;
+ case MULTIBOOT_TAG_TYPE_MODULE:
+ multiboot2_module((struct multiboot_tag_module *)tag, __info);
+ break;
+ case MULTIBOOT_TAG_TYPE_MMAP:
+ multiboot2_mmap(((struct multiboot_tag_mmap *)tag)->entries,
+ ((struct multiboot_tag_mmap *)tag)->size / ((struct multiboot_tag_mmap *)tag)->entry_size,
+ __info->bitmap);
+ break;
+ default:
+ break;
+ }
+ }
+}
diff --git a/kernel/sched.hpp b/kernel/sched.hpp
new file mode 100644
index 0000000..cfa3ff0
--- /dev/null
+++ b/kernel/sched.hpp
@@ -0,0 +1,8 @@
+#pragma once
+
+#include "task.h"
+
+class RoundRobinQueue : public Queue<Task> {
+public:
+ [[nodiscard]] Task *next(int slice);
+};
diff --git a/kernel/sched/roundrobin.cpp b/kernel/sched/roundrobin.cpp
new file mode 100644
index 0000000..c3d6cb6
--- /dev/null
+++ b/kernel/sched/roundrobin.cpp
@@ -0,0 +1,21 @@
+#include "../sched.hpp"
+
+/// Each task is run for a time quantum or the remainder of its cpu burst
+Task *
+RoundRobinQueue::next(int slice)
+{
+ if (head == nullptr) return nullptr;
+ if (head->node->burst <= 0) {
+ delete head->node;
+ remove(head->node);
+ return next(slice);
+ }
+
+ auto *it = head;
+ it->node->burst -= slice;
+ if (head->next) head = head->next;
+ it->next = nullptr;
+ tail->next = it;
+ tail = it;
+ return it->node;
+}
diff --git a/kernel/sched/test_roundrobin.cc b/kernel/sched/test_roundrobin.cc
new file mode 100644
index 0000000..89f60bf
--- /dev/null
+++ b/kernel/sched/test_roundrobin.cc
@@ -0,0 +1,50 @@
+#include <chrono>
+#include <gtest/gtest.h>
+#include <iomanip>
+#include <iostream>
+#include <valgrind/valgrind.h>
+
+#include "../sched/roundrobin.cpp"
+
+void
+run(Task *task, int slice)
+{
+ std::cout << "Running task " << task->name << " id=" << std::setw(2) << task->id << " prio=" << std::setw(2)
+ << task->priority << " burst=" << std::setw(2) << task->burst << " slice=" << slice << " ";
+}
+
+struct DebugRoundRobinQueue : public RoundRobinQueue {
+public:
+ void
+ print() const
+ {
+ for (auto *it = head; it != nullptr; it = it->next) {
+ std::cout << it->node->name << '(' << std::setw(2) << it->node->burst << ") ";
+ }
+ std::cout << std::endl;
+ }
+};
+
+TEST(roundrobin, RoundRobinQueue)
+{
+ DebugRoundRobinQueue queue;
+ queue.insert(new Task{"P1", 1, 1, 50});
+ queue.insert(new Task{"P2", 2, 1, 40});
+ queue.insert(new Task{"P3", 3, 1, 50});
+ queue.insert(new Task{"P4", 4, 1, 40});
+
+ const auto begin = std::chrono::system_clock::now();
+ for (auto *t = queue.next(10); t != nullptr; t = queue.next(10)) {
+ run(t, 10);
+ queue.print();
+ }
+ const auto end = std::chrono::system_clock::now();
+ const auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count();
+
+ std::cout << "Completed in (us): " << duration << std::endl;
+ // test should complete in 250us unless running on valgrind
+ if (!RUNNING_ON_VALGRIND) { EXPECT_LE(duration, 250); }
+
+ EXPECT_EQ(queue.head, nullptr);
+ EXPECT_EQ(queue.tail, nullptr);
+}
diff --git a/kernel/sched/test_taskqueue.cc b/kernel/sched/test_taskqueue.cc
new file mode 100644
index 0000000..217c44d
--- /dev/null
+++ b/kernel/sched/test_taskqueue.cc
@@ -0,0 +1,122 @@
+#include <gtest/gtest.h>
+
+#include "../sched.hpp"
+
+struct DebugQueue : public Queue<Task> {
+public:
+ void
+ expect_ordered() const
+ {
+ int id = 1;
+ for (auto *it = head; it != nullptr; it = it->next) {
+ // std::cout << it->node->name << std::endl;
+ EXPECT_EQ(it->node->id, id++);
+ }
+ }
+};
+
+TEST(taskqueue, insert)
+{
+ DebugQueue queue;
+ auto *p1 = new Task{"P1", 1, 1, 10};
+ queue.insert(p1);
+ queue.insert(new Task{"P2", 2, 1, 10});
+ queue.insert(new Task{"P3", 3, 1, 10});
+ auto *p4 = new Task{"P4", 4, 1, 10};
+ queue.insert(p4);
+ queue.expect_ordered();
+
+ EXPECT_EQ(queue.head->node, p1);
+ EXPECT_EQ(queue.tail->node, p4);
+}
+
+TEST(taskqueue, removeHead)
+{
+ DebugQueue queue;
+ auto *p0 = new Task{"P0", 0, 1, 10};
+ queue.insert(p0);
+ auto *p1 = new Task{"P1", 1, 1, 10};
+ queue.insert(p1);
+ queue.insert(new Task{"P2", 2, 1, 10});
+ queue.insert(new Task{"P3", 3, 1, 10});
+ auto *p4 = new Task{"P4", 4, 1, 10};
+ queue.insert(p4);
+ queue.remove(p0);
+ delete p0;
+
+ EXPECT_EQ(queue.head->node, p1);
+ EXPECT_EQ(queue.tail->node, p4);
+ queue.expect_ordered();
+}
+
+TEST(taskqueue, removeTail)
+{
+ DebugQueue queue;
+ auto *p1 = new Task{"P1", 1, 1, 10};
+ queue.insert(p1);
+ queue.insert(new Task{"P2", 2, 1, 10});
+ queue.insert(new Task{"P3", 3, 1, 10});
+ auto *p4 = new Task{"P4", 4, 1, 10};
+ queue.insert(p4);
+ auto *p5 = new Task{"P5", 5, 1, 10};
+ queue.insert(p5);
+ EXPECT_EQ(queue.head->node, p1);
+ EXPECT_EQ(queue.tail->node, p5);
+
+ queue.remove(p5);
+ delete p5;
+
+ EXPECT_EQ(queue.head->node, p1);
+ EXPECT_EQ(queue.tail->node, p4);
+ queue.expect_ordered();
+}
+
+TEST(taskqueue, removeLast)
+{
+ DebugQueue queue;
+
+ auto *p0 = new Task{"P0", 0, 1, 10};
+ queue.insert(p0);
+ EXPECT_EQ(queue.head->node, p0);
+ EXPECT_EQ(queue.tail->node, p0);
+
+ queue.remove(p0);
+ delete p0;
+
+ EXPECT_EQ(queue.head, nullptr);
+ EXPECT_EQ(queue.tail, nullptr);
+}
+
+TEST(taskqueue, removeNullptr)
+{
+ DebugQueue queue;
+ queue.insert(new Task{"P1", 1, 1, 10});
+ queue.insert(new Task{"P2", 2, 1, 10});
+ queue.insert(new Task{"P3", 3, 1, 10});
+ queue.insert(new Task{"P4", 4, 1, 10});
+ queue.remove(nullptr);
+ queue.expect_ordered();
+}
+
+TEST(taskqueue, remove)
+{
+ DebugQueue queue;
+ auto *p1 = new Task{"P1", 1, 1, 10};
+ queue.insert(p1);
+ queue.insert(new Task{"P2", 2, 1, 10});
+ auto *p0 = new Task{"P0", 0, 1, 10};
+ queue.insert(p0);
+ queue.insert(new Task{"P3", 3, 1, 10});
+ auto *p4 = new Task{"P4", 4, 1, 10};
+ queue.insert(p4);
+
+ EXPECT_EQ(queue.head->node, p1);
+ EXPECT_EQ(queue.tail->node, p4);
+
+ queue.remove(p0);
+ delete p0;
+
+ EXPECT_EQ(queue.head->node, p1);
+ EXPECT_EQ(queue.tail->node, p4);
+ queue.expect_ordered();
+}
diff --git a/kernel/task.h b/kernel/task.h
new file mode 100644
index 0000000..0d59bb1
--- /dev/null
+++ b/kernel/task.h
@@ -0,0 +1,78 @@
+#pragma once
+
+/**
+ * Representation of a task in the system
+ */
+struct Task {
+ const char *name;
+ int id;
+ int priority;
+ int burst;
+};
+
+#ifdef __cplusplus
+template <typename T> struct Queue {
+ struct Item {
+ Item(T *p_node) : node(p_node) {}
+ T *node;
+ Item *next = nullptr;
+
+ [[nodiscard]] bool
+ operator==(const T *other) const
+ {
+ return node == other;
+ }
+ };
+
+ ~Queue() noexcept
+ {
+ for (auto *it = head; it != nullptr;) {
+ auto *current = it;
+ it = it->next;
+ delete current->node;
+ delete current;
+ }
+ }
+
+ /// Insert item at the end of the queue
+ void
+ insert(T *item)
+ {
+ if (head == nullptr) {
+ head = new Item(item);
+ tail = head;
+ }
+ else {
+ tail->next = new Item(item);
+ tail = tail->next;
+ }
+ }
+
+ void
+ remove(T *item)
+ {
+ if (head == nullptr) return;
+ if (item == head->node) {
+ auto *it = head;
+ head = head->next;
+ if (*tail == item) tail = nullptr;
+ delete it;
+ return;
+ }
+
+ Item *prev = nullptr;
+ for (auto *it = head; it != nullptr; it = it->next) {
+ if (it->node == item) {
+ if (prev) { prev->next = it->next; }
+ if (tail == it) { tail = prev; }
+ delete it;
+ return;
+ }
+ prev = it;
+ }
+ }
+
+ Item *head = nullptr;
+ Item *tail = nullptr;
+};
+#endif
generated by cgit v1.2.1 (git 2.18.0) at 2025-06-19 10:10:39 +0000