Bazel build

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