update

9 files changed, 701 insertions, 0 deletions

diff --git a/kernel/include/hilbert/kernel/application.hpp b/kernel/include/hilbert/kernel/application.hpp
new file mode 100644
index 0000000..51f304d
--- /dev/null
+++ b/kernel/include/hilbert/kernel/application.hpp
@@ -0,0 +1,77 @@
+#pragma once
+
+#include <hilbert/kernel/vfile.hpp>
+#include <stdint.h>
+
+//TODO: end application, threading.
+
+namespace hilbert::kernel::application {
+
+  void init_syscalls();
+
+  enum class app_state {
+    running,
+    paused,
+    zombie
+  };
+
+  struct app_instance {
+
+    utility::id_allocator<vfile::vfile> open_files;
+
+    vfile::vfile working_dir;
+
+    app_state state;
+
+    uint64_t *p4;
+    uint64_t *p3;
+    uint64_t *p2s[512];
+    uint64_t **p1s[512];
+
+    bool **p1es_to_free_on_exit[512];
+
+    uint64_t p4_paddr;
+
+    //set to 0 if none
+    uint64_t framebuffer_vaddr;
+
+    //only valid if state is zombie
+    int32_t exit_code;
+
+    //only valid if state is paused
+    struct {
+      uint64_t rip;
+      uint64_t rsp;
+      //TODO: etc.
+    } saved_regs;
+
+    app_instance();
+
+    //vaddr and paddr must be aligned, and vaddr must be < 0x0080.0000.0000
+    void map_page(uint64_t vaddr, uint64_t paddr,
+      bool write, bool execute, bool free_pram_on_exit);
+
+    //where "owned" means in lower half and marked free on exit
+    bool is_page_owned(uint64_t vaddr);
+
+    //returns start of first page
+    uint64_t get_free_vaddr_pages(uint64_t count);
+
+    //in lower half
+    uint64_t count_mapped_vram_pages();
+
+  };
+
+  extern app_instance *running_app;
+
+  enum class create_app_result {
+    success,
+    device_error,
+    app_corrupt,
+    fs_corrupt
+  };
+
+  create_app_result create_app(const vfile::vfile &file,
+    app_instance *&out, const vfile::vfile &working_dir);
+
+}
diff --git a/kernel/include/hilbert/kernel/framebuffer.hpp b/kernel/include/hilbert/kernel/framebuffer.hpp
new file mode 100644
index 0000000..fb28462
--- /dev/null
+++ b/kernel/include/hilbert/kernel/framebuffer.hpp
@@ -0,0 +1,31 @@
+#pragma once
+
+#include <stdint.h>
+
+namespace hilbert::kernel::framebuffer {
+
+  extern uint64_t paddr;
+  extern int width;
+  extern int height;
+  extern int dword_pitch;
+
+  void init_framebuffer(
+    uint64_t paddr, uint64_t vaddr, uint64_t width,
+    uint64_t height, uint64_t pitch);
+
+  typedef uint32_t color;
+  color encode_color(uint8_t r, uint8_t g, uint8_t b);
+
+  void set_pixel(int x, int y, color c);
+
+  //[from_start_x, from_end_x) x [from_start_y, from_end_y)
+  //  -> [to_start_x, ...) x [to_start_y, ...).
+  //we assume from_start_x < from_end_x and from_start_y < from_end_y.
+  void move_region(
+    int from_start_x, int from_start_y, int from_end_x,
+    int from_end_y, int to_start_x, int to_start_y);
+
+  //[start_x, end_x) x [start_y, end_y)
+  void fill_region(int start_x, int start_y, int end_x, int end_y, color c);
+
+}
diff --git a/kernel/include/hilbert/kernel/paging.hpp b/kernel/include/hilbert/kernel/paging.hpp
new file mode 100644
index 0000000..91ab5f7
--- /dev/null
+++ b/kernel/include/hilbert/kernel/paging.hpp
@@ -0,0 +1,42 @@
+#pragma once
+
+#include <stdint.h>
+
+//in paging.asm
+extern "C" [[noreturn]] void switch_to_kernel_p4(void (*and_then_jump_to)());
+
+namespace hilbert::kernel::paging {
+
+  void mark_all_pram_used();
+  void mark_all_vram_free();
+
+  void mark_pram_region_free(uint64_t start_addr, uint64_t end_addr);
+  void mark_vram_region_used(uint64_t start_addr, uint64_t end_addr);
+
+  uint64_t find_unmapped_vram_region(uint64_t page_count);
+
+  uint64_t encode_pte(uint64_t addr, bool user, bool write, bool execute);
+
+  void init_kernel_page_tables(uint64_t kernel_offset);
+
+  uint64_t take_pram_page();
+
+  void map_kernel_stacks();
+
+  void map_kernel_page(
+    uint64_t paddr, uint64_t vaddr, bool write, bool execute);
+
+  void unmap_kernel_page(uint64_t vaddr);
+
+  //maps writable and not executable
+  void *map_new_kernel_pages(uint64_t count);
+
+  //maps writable and not executable
+  void map_new_kernel_page(uint64_t &vaddr_out, uint64_t &paddr_out);
+
+  uint64_t get_used_vram_page_count();
+  uint64_t get_free_pram_page_count();
+
+  extern uint64_t kernel_p4e;
+
+}
diff --git a/kernel/include/hilbert/kernel/storage.hpp b/kernel/include/hilbert/kernel/storage.hpp
new file mode 100644
index 0000000..2e2169e
--- /dev/null
+++ b/kernel/include/hilbert/kernel/storage.hpp
@@ -0,0 +1,106 @@
+#pragma once
+
+#include <hilbert/kernel/utility.hpp>
+#include <stdint.h>
+
+namespace hilbert::kernel::storage {
+
+  typedef uint64_t node_id_t;
+  typedef uint64_t directory_iter_t;
+
+  enum class file_type {
+    regular_file,
+    directory,
+    symlink
+  };
+
+  enum class bd_result {
+    success,
+    out_of_bounds,
+    device_error
+  };
+
+  enum class fs_result {
+    success,
+    device_error,
+    fs_corrupt,
+    does_not_exist
+  };
+
+  struct dir_entry {
+    utility::string name;
+    node_id_t node;
+    file_type type;
+    //only used if type is regular_file.
+    uint64_t length;
+    //only used if type is symlink.
+    utility::string target;
+  };
+
+  class file_system_instance {
+
+  public:
+    virtual ~file_system_instance() {}
+
+    virtual fs_result get_root_node(node_id_t &out) = 0;
+
+    //it is assumed that this is a directory. sets iter_out
+    //to a value that can be passed to subsequent calls
+    //to get_next_child with the same argument for node.
+    virtual fs_result get_first_child(
+      node_id_t node, dir_entry &out, directory_iter_t &iter_out) = 0;
+
+    //it is assumed that this is a directory. sets iter_out
+    //to a value that can be passed to subsequent calls
+    //to get_next_child with the same argument for node.
+    virtual fs_result get_next_child(
+      node_id_t node, dir_entry &out, directory_iter_t &iter) = 0;
+
+    //it is assumed that this is a regular file and that
+    //the region requested is within the bounds of the file.
+    virtual fs_result read_bytes_from_file(
+      node_id_t node, uint64_t start, uint64_t count, void *into) = 0;
+
+  };
+
+  class block_device {
+
+  private:
+    uint8_t *block_cache;
+    uint64_t block_cache_i;
+
+    //it is assumed that this block is within the bounds of the device.
+    bd_result load_cache_block(uint64_t i);
+
+  protected:
+    //implemented in driver. it is assumed that the
+    //blocks are within the bounds of the device.
+    virtual bd_result read_blocks_no_cache(
+      uint64_t start, uint64_t count, void *into) = 0;
+
+    //it is assumed that this is only called once, by the driver, after
+    //block_size and block_count have been set, and before read_bytes or
+    //write_bytes can be called (e.g. in the derived class's constructor).
+    void allocate_block_cache();
+
+  public:
+    //set by storage component
+    file_system_instance *mounted_as;
+    //set by storage component
+    utility::uuid id;
+
+    //set by driver
+    uint64_t block_size;
+    //set by driver
+    uint64_t block_count;
+
+    virtual ~block_device() {
+      if (block_cache)
+        delete block_cache;
+    }
+
+    bd_result read_bytes(uint64_t start, uint64_t count, void *into);
+
+  };
+
+}
diff --git a/kernel/include/hilbert/kernel/storage/bd/memory.hpp b/kernel/include/hilbert/kernel/storage/bd/memory.hpp
new file mode 100644
index 0000000..e057241
--- /dev/null
+++ b/kernel/include/hilbert/kernel/storage/bd/memory.hpp
@@ -0,0 +1,20 @@
+#pragma once
+
+#include <hilbert/kernel/storage.hpp>
+
+namespace hilbert::kernel::storage::bd {
+
+  class memory : public block_device {
+
+  private:
+    uint8_t *buffer;
+
+  public:
+    memory(void *buffer, uint64_t buffer_len);
+
+    bd_result read_blocks_no_cache(
+      uint64_t start, uint64_t count, void *into) override;
+
+  };
+
+}
diff --git a/kernel/include/hilbert/kernel/storage/fs/tarfs.hpp b/kernel/include/hilbert/kernel/storage/fs/tarfs.hpp
new file mode 100644
index 0000000..cef35f2
--- /dev/null
+++ b/kernel/include/hilbert/kernel/storage/fs/tarfs.hpp
@@ -0,0 +1,33 @@
+#pragma once
+
+#include <hilbert/kernel/storage.hpp>
+
+namespace hilbert::kernel::storage::fs {
+
+  class tarfs_instance : public file_system_instance {
+
+  private:
+    block_device *bd;
+
+    fs_result next_node(node_id_t node, node_id_t &out);
+    fs_result read_full_name(node_id_t node, utility::string &out);
+    //len <= 12
+    fs_result read_num(uint64_t offset, unsigned len, uint64_t &out);
+    fs_result first_child_starting_at(
+      node_id_t parent, node_id_t start, node_id_t &out);
+    fs_result get_dir_entry(node_id_t node, dir_entry &entry);
+
+  public:
+    tarfs_instance(block_device *bd);
+
+    fs_result get_root_node(node_id_t &out);
+    fs_result get_first_child(node_id_t node,
+      dir_entry &out, directory_iter_t &iter_out);
+    fs_result get_next_child(
+      node_id_t node, dir_entry &out, directory_iter_t &iter);
+    fs_result read_bytes_from_file(
+      node_id_t node, uint64_t start, uint64_t count, void *into);
+
+  };
+
+}
diff --git a/kernel/include/hilbert/kernel/terminal.hpp b/kernel/include/hilbert/kernel/terminal.hpp
new file mode 100644
index 0000000..350d79b
--- /dev/null
+++ b/kernel/include/hilbert/kernel/terminal.hpp
@@ -0,0 +1,32 @@
+#pragma once
+
+#include <hilbert/kernel/framebuffer.hpp>
+#include <hilbert/kernel/utility.hpp>
+#include <stddef.h>
+#include <stdint.h>
+
+namespace hilbert::kernel::terminal {
+
+  extern uint8_t *termfont;
+  extern uint64_t termfont_len;
+
+  void init_terminal();
+
+  extern int width;
+  extern int height;
+
+  extern int cursor_x;
+  extern int cursor_y;
+
+  extern framebuffer::color bg_color;
+  extern framebuffer::color fg_color;
+
+  void put_char(char ch);
+  void put_string(const utility::string &str);
+  void put_string_sz(const char *str);
+
+  void put_int_decimal(uint64_t n, bool with_commas = true);
+
+  void put_int_hex(uint64_t n, int digits, bool with_dots = true);
+
+}
diff --git a/kernel/include/hilbert/kernel/utility.hpp b/kernel/include/hilbert/kernel/utility.hpp
new file mode 100644
index 0000000..2df1d65
--- /dev/null
+++ b/kernel/include/hilbert/kernel/utility.hpp
@@ -0,0 +1,297 @@
+#pragma once
+
+#include <stddef.h>
+#include <stdint.h>
+
+void *operator new(size_t, void *ptr);
+void operator delete(void *, void *);
+
+namespace hilbert::kernel::utility {
+
+  template <class t>
+  struct no_ref;
+  template <class t>
+  struct no_ref<t &&> {
+    typedef t _t;
+  };
+  template <class t>
+  struct no_ref<t &> {
+    typedef t _t;
+  };
+  template <class t>
+  struct no_ref {
+    typedef t _t;
+  };
+
+  template <class t>
+  constexpr typename no_ref<t>::_t &&move(t &&v) {
+    return static_cast<typename no_ref<t>::_t &&>(v);
+  }
+
+  template <class t>
+  static inline t min(t a, t b) {
+    return a < b ? a : b;
+  }
+
+  //includes start_i, does not include end_i
+  void mark_bitmap_region_zero(
+    uint64_t *bitmap, uint64_t start_i, uint64_t end_i);
+  //includes start_i, does not include end_i
+  void mark_bitmap_region_one(
+    uint64_t *bitmap, uint64_t start_i, uint64_t end_i);
+
+  struct uuid {
+    uint8_t bytes[16];
+  };
+
+  //if c appears in str, this returns the index of the first time it appears.
+  //otherwise, this returns len.
+  static inline unsigned find(const char *str, unsigned len, char c) {
+    for (unsigned i = 0; i < len; ++i)
+      if (str[i] == c)
+        return i;
+    return len;
+  }
+
+  //if c appears in str, this returns the index of the last time it appears.
+  //otherwise, this returns len.
+  static inline unsigned find_last(const char *str, unsigned len, char c) {
+    for (unsigned i = len; i > 0; --i)
+      if (str[i - 1] == c)
+        return i - 1;
+    return len;
+  }
+
+  //str1 starts with str2
+  static inline bool starts_with(
+    const char *str1, unsigned str1_len, const char *str2, unsigned str2_len
+  ) {
+    if (str1_len < str2_len)
+      return false;
+    for (unsigned i = 0; i < str2_len; ++i)
+      if (str1[i] != str2[i])
+        return false;
+    return true;
+  }
+
+  template <class value_t>
+  struct list {
+
+    struct node {
+      value_t value;
+      node *next;
+      node *prev;
+    };
+
+    node *first;
+    node *last;
+
+    list() : first(0), last(0) {}
+
+    list(const list &other) = delete;
+    list(list &&other) = delete;
+
+    ~list() {
+      if (first) {
+        for (node *n = first->next; n; n = n->next)
+          delete n->prev;
+        delete last;
+      }
+    }
+
+    list &operator =(const list &other) = delete;
+    list &operator =(list &&other) = delete;
+
+    void insert_end(const value_t &value) {
+      node *n = new node {};
+      n->value = value;
+      n->next = 0;
+      n->prev = last;
+      last = n;
+    }
+
+    void insert_end(value_t &&value) {
+      node *n = new node {};
+      n->value = value;
+      n->next = 0;
+      n->prev = last;
+      last = n;
+    }
+
+    void clear() {
+      for (node *n = first; n; n = n->next)
+        delete n;
+      first = 0;
+      last = 0;
+    }
+
+    //assumes there is a last.
+    void remove_last() {
+      node *new_last = last->prev;
+      if (new_last)
+        new_last->next = 0;
+      else
+        first = 0;
+      delete last;
+      last = new_last;
+    }
+
+    void remove(node *n) {
+      if (n->prev)
+        n->prev->next = n->next;
+      else
+        first = n->next;
+      if (n->next)
+        n->next->prev = n->prev;
+      else
+        last = n->prev;
+      delete n;
+    }
+
+  };
+
+  template <class value_t>
+  struct vector {
+
+    value_t *buffer;
+    unsigned buffer_len;
+    unsigned count;
+
+    vector(unsigned buffer_len = 16)
+      : buffer(new value_t[buffer_len]), buffer_len(buffer_len), count(0) {}
+
+    vector(const value_t *copy_from, unsigned len)
+      : buffer(new value_t[len]), buffer_len(len), count(len) {
+      for (unsigned i = 0; i < len; ++i)
+        buffer[i] = copy_from[i];
+    }
+
+    vector(const vector &other)
+      : buffer(new value_t[other.buffer_len]),
+        buffer_len(other.buffer_len), count(other.count)
+    {
+      for (unsigned i = 0; i < count; ++i)
+        buffer[i] = other.buffer[i];
+    }
+
+    vector(vector &&other) = delete;
+
+    ~vector() {
+      if (buffer)
+        delete[] buffer;
+    }
+
+    vector &operator =(const vector &other) {
+      if (buffer)
+        delete[] buffer;
+      buffer = new value_t[other.buffer_len];
+      buffer_len = other.buffer_len;
+      count = other.count;
+      for (unsigned i = 0; i < other.count; ++i)
+        buffer[i] = other.buffer[i];
+      return *this;
+    }
+
+    vector &operator =(vector &&other) {
+      if (buffer)
+        delete[] buffer;
+      buffer = other.buffer;
+      buffer_len = other.buffer_len;
+      count = other.count;
+      other.buffer = 0;
+      return *this;
+    }
+
+    bool operator ==(const vector &other) {
+      if (other.count != count)
+        return false;
+      for (unsigned i = 0; i < count; ++i)
+        if (other.buffer[i] != buffer[i])
+          return false;
+      return true;
+    }
+
+    void verify_buffer_len(unsigned target_len) {
+      if (buffer_len >= target_len)
+        return;
+      unsigned new_buffer_len = buffer_len;
+      do
+        new_buffer_len *= 2;
+      while (new_buffer_len < target_len);
+      value_t *new_buffer = new value_t[new_buffer_len];
+      for (unsigned i = 0; i < count; ++i)
+        new_buffer[i] = move(buffer[i]);
+      delete[] buffer;
+      buffer = new_buffer;
+      buffer_len = new_buffer_len;
+    }
+
+    void add_end(value_t &&v) {
+      verify_buffer_len(count + 1);
+      buffer[count] = move(v);
+      ++count;
+    }
+
+    void add_end(const value_t &v) {
+      verify_buffer_len(count + 1);
+      buffer[count] = v;
+      ++count;
+    }
+
+    bool starts_with(const vector &other) {
+      if (count < other.count)
+        return false;
+      for (unsigned i = 0; i < other.count; ++i)
+        if (buffer[i] != other.buffer[i])
+          return false;
+      return true;
+    }
+
+  };
+
+  typedef vector<char> string;
+
+  template <class value_t>
+  struct id_allocator {
+
+    vector<value_t *> the_vector;
+
+  public:
+    id_allocator() : the_vector() {}
+    id_allocator(const id_allocator &other) = delete;
+    id_allocator(id_allocator &&other) = delete;
+    id_allocator &operator =(const id_allocator &other) = delete;
+    id_allocator &operator =(id_allocator &&other) = delete;
+
+    //returns id; pointer becomes owned by id_allocator
+    unsigned add(value_t *v) {
+      for (unsigned i = 0; i < the_vector.count; ++i)
+        if (the_vector.buffer[i] == 0) {
+          the_vector.buffer[i] = v;
+          return i;
+        }
+      the_vector.add_end(v);
+      return the_vector.count - 1;
+    }
+
+    //returns id
+    unsigned add_new(value_t &&v) {
+      return add(new value_t(move(v)));
+    }
+
+    bool has_id(unsigned i) {
+      return i < the_vector.count && the_vector.buffer[i] != 0;
+    }
+
+    value_t &get(unsigned i) {
+      return *the_vector.buffer[i];
+    }
+
+    void remove_id(unsigned i) {
+      delete the_vector.buffer[i];
+      the_vector.buffer[i] = 0;
+    }
+
+  };
+
+}
diff --git a/kernel/include/hilbert/kernel/vfile.hpp b/kernel/include/hilbert/kernel/vfile.hpp
new file mode 100644
index 0000000..f8a387d
--- /dev/null
+++ b/kernel/include/hilbert/kernel/vfile.hpp
@@ -0,0 +1,63 @@
+#pragma once
+
+#include <hilbert/kernel/storage.hpp>
+#include <hilbert/kernel/utility.hpp>
+
+//TODO: mounts points.
+//maybe a two-way map between mount points and targets? one mount point per
+//target and vice versa. only directories may be mount points, and only file
+//system roots (which must be directories) may be targets.
+
+namespace hilbert::kernel::vfile {
+
+  //a canon path contains no . or empty directory names, and
+  //contains no .. except for at the start of a relative path.
+  struct canon_path {
+
+    bool absolute;
+    unsigned parent_count;
+    utility::vector<utility::string> segments;
+
+    canon_path() : absolute(false), parent_count(0), segments(8) {}
+
+    void parent();
+    void rel(const canon_path &r);
+
+    utility::string to_string(bool trailing_slash) const;
+
+  };
+
+  void canonize_path(const utility::string &name, canon_path &out);
+
+  struct vfile {
+
+    //on followed symlinks, path is the source of the symlink and the
+    //rest of these are the target. in any case, path should be absolute.
+    canon_path path;
+    storage::block_device *bd;
+    storage::dir_entry dir_entry;
+
+    storage::fs_result follow_symlinks(vfile &out) const;
+
+    //dir_entry.type is assumed to be directory.
+    storage::fs_result get_child(
+      vfile &out, const utility::string &name) const;
+    //dir_entry.type is assumed to be directory. out must be empty on entry.
+    storage::fs_result get_children(utility::vector<vfile> &out) const;
+
+    //assumes file is a regular file and [start, start + length)
+    //is in bounds of file. start and length are in bytes.
+    storage::fs_result read_file(
+      uint64_t start, uint64_t length, void *into) const;
+
+  };
+
+  //TODO: see comment at top of file.
+  void set_root(const vfile &root);
+
+  //path must be absolute. follows symlinks on all but the last node.
+  //relative_to should be a directory to do the lookup inside; e.g.,
+  //if relative_to is /a/b and path is c, then out becomes /a/b/c.
+  storage::fs_result lookup_path(const canon_path &path, vfile &out);
+
+}