partial (largely untested) memory block device and tar file system support

6 files changed, 394 insertions, 66 deletions

diff --git a/include/mercury/kernel/bd/memory.hpp b/include/mercury/kernel/bd/memory.hpp
new file mode 100644
index 0000000..079abee
--- /dev/null
+++ b/include/mercury/kernel/bd/memory.hpp
@@ -0,0 +1,23 @@
+#ifndef MERCURY_KERNEL_BD_MEMORY_HPP
+#define MERCURY_KERNEL_BD_MEMORY_HPP
+
+#include <mercury/kernel/storage.hpp>
+
+namespace mercury::kernel::bd {
+
+  class memory : public storage::block_device {
+
+  private:
+    uint8_t *buffer;
+
+  public:
+    memory(void *buffer, size_t buffer_len);
+
+    storage::io_result read_blocks_no_cache(uint64_t start, uint64_t count, void *into) override;
+    storage::io_result write_blocks_no_cache(uint64_t start, uint64_t count, const void *from) override;
+
+  };
+
+}
+
+#endif
diff --git a/include/mercury/kernel/fs/tarfs.hpp b/include/mercury/kernel/fs/tarfs.hpp
new file mode 100644
index 0000000..41773ee
--- /dev/null
+++ b/include/mercury/kernel/fs/tarfs.hpp
@@ -0,0 +1,40 @@
+#ifndef MERCURY_KERNEL_FS_TARFS_HPP
+#define MERCURY_KERNEL_FS_TARFS_HPP
+
+#include <mercury/kernel/storage.hpp>
+
+namespace mercury::kernel::fs {
+
+  class tarfs_instance : public storage::file_system_instance {
+
+  private:
+    storage::block_device *bd;
+
+    storage::io_result next_node(storage::node_id_t &node);
+    //name_buf must be at least 255 chars long.
+    storage::io_result read_name(storage::node_id_t node, char *name_buf, size_t &name_len_out);
+    //len <= 12
+    storage::io_result read_num(uint64_t offset, size_t len, uint64_t &out);
+
+  public:
+    tarfs_instance(storage::block_device *bd);
+
+    storage::io_result get_root_node(storage::node_id_t &out) override;
+    storage::io_result get_first_child(
+      storage::node_id_t node, storage::node_id_t &out, storage::directory_iter_t &iter_out) override;
+    storage::io_result get_next_child(
+      storage::node_id_t node, storage::node_id_t &out, storage::directory_iter_t &iter) override;
+    storage::io_result get_child(
+      storage::node_id_t node, storage::node_id_t &out, const char *name, size_t name_len) override;
+    storage::io_result get_name_length(storage::node_id_t node, size_t &length_out) override;
+    storage::io_result get_name(storage::node_id_t node, char *buffer, size_t &length_out) override;
+    storage::io_result get_file_length(storage::node_id_t node, uint64_t &length_out) override;
+    storage::io_result get_file_type(storage::node_id_t node, storage::file_type &out) override;
+
+  };
+
+  storage::io_result tarfs_mounter(storage::block_device *bd, storage::file_system_instance *&fs_out);
+
+}
+
+#endif
diff --git a/include/mercury/kernel/paging.hpp b/include/mercury/kernel/paging.hpp
index 9627162..4ba5fdf 100644
--- a/include/mercury/kernel/paging.hpp
+++ b/include/mercury/kernel/paging.hpp
@@ -26,6 +26,9 @@ namespace mercury::kernel::paging {
   void map_kernel_page(
     uint64_t paddr, uint64_t vaddr, bool write, bool execute);
 
+  //maps writable and not executable
+  void *map_new_kernel_pages(uint64_t count);
+
   uint64_t get_used_vram_page_count();
   uint64_t get_free_pram_page_count();
 
diff --git a/include/mercury/kernel/storage.hpp b/include/mercury/kernel/storage.hpp
new file mode 100644
index 0000000..1374766
--- /dev/null
+++ b/include/mercury/kernel/storage.hpp
@@ -0,0 +1,130 @@
+#ifndef MERCURY_KERNEL_STORAGE_HPP
+#define MERCURY_KERNEL_STORAGE_HPP
+
+#include <mercury/kernel/utility.hpp>
+#include <cstdint>
+
+namespace mercury::kernel::storage {
+
+  typedef uint64_t node_id_t;
+  typedef uint64_t directory_iter_t;
+
+  enum file_type {
+    regular_file,
+    directory,
+    symlink
+  };
+
+  enum io_result {
+    success,
+    mount_point_already_used,
+    not_a_directory,
+    not_supported,
+    out_of_bounds,
+    device_error,
+    fs_corrupt,
+    not_found,
+    bad_path,
+  };
+
+  class file_system_instance {
+
+  public:
+    virtual ~file_system_instance() {}
+
+    virtual io_result get_root_node(node_id_t &out) = 0;
+
+    //get_first_child sets iter_out to a "directory iterator" representing the
+    //first child of this node. get_next_child gets the child after the child
+    //represented by the value of iter passed in, and changes iter to represent
+    //that next child. for an empty directory node, get_first_child returns
+    //io_result::out_of_bounds. when iter represents the last child of a node,
+    //get_next_child also returns io_result::out_of_bounds.
+    virtual io_result get_first_child(node_id_t node, node_id_t &out, directory_iter_t &iter_out) = 0;
+    virtual io_result get_next_child(node_id_t node, node_id_t &out, directory_iter_t &iter) = 0;
+    virtual io_result get_child(node_id_t node, node_id_t &out, const char *name, size_t name_len) = 0;
+
+    virtual io_result get_name_length(node_id_t node, size_t &length_out) = 0;
+    //buffer is assumed to be long enough - call get_name_length first.
+    virtual io_result get_name(node_id_t node, char *buffer, size_t &length_out) = 0;
+
+    virtual io_result get_file_length(node_id_t node, uint64_t &length_out) = 0;
+
+    virtual io_result get_file_type(node_id_t node, file_type &out) = 0;
+  };
+
+  class block_device {
+
+  private:
+    uint8_t *block_cache;
+    uint64_t block_cache_i;
+    bool block_cache_dirty;
+
+    io_result load_cache_block(uint64_t i);
+
+  protected:
+    //implemented in driver, bounds not checked
+    virtual io_result read_blocks_no_cache(uint64_t start, uint64_t count, void *into) = 0;
+    virtual io_result write_blocks_no_cache(uint64_t start, uint64_t count, const void *from) = 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;
+    utility::uuid id;
+
+    //set by driver
+    uint64_t block_size;
+    uint64_t block_count;
+
+    virtual ~block_device() {
+      if (block_cache)
+        delete block_cache;
+    }
+
+    io_result read_bytes(uint64_t start, uint64_t count, void *into);
+    io_result write_bytes(uint64_t start, uint64_t count, const void *from);
+
+  };
+
+  typedef io_result (*file_system_mounter)(block_device *bd, file_system_instance *&fs_out);
+
+  extern utility::list<block_device *> *block_devices;
+
+  void init_storage();
+
+  //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;
+
+    void parent();
+    void rel(const canon_path &r);
+
+    utility::string to_string(bool trailing_slash) const;
+
+  };
+
+  void canonize_path(const char *str, size_t len, canon_path &out);
+
+  //path must be absolute.
+  io_result mount_device(block_device *bd, const canon_path &path, file_system_mounter mounter);
+
+  //path must be absolute. symlinks are always resolved on nodes other than the
+  //final one. they are resolved on the final node if and only if resolve final
+  //node is set to true. mount points are always traversed, including on the
+  //final node. this assumes that the path is under some mount point, and the
+  //same for any symlinks traversed (e.g. / is mounted).
+  io_result look_up_absolute_path(const canon_path &path, block_device *&bd_out,
+    node_id_t &node_out, bool resolve_final_node, canon_path &path_without_symlinks_out);
+
+}
+
+#endif
diff --git a/include/mercury/kernel/terminal.hpp b/include/mercury/kernel/terminal.hpp
index b9d9976..776ff64 100644
--- a/include/mercury/kernel/terminal.hpp
+++ b/include/mercury/kernel/terminal.hpp
@@ -1,6 +1,7 @@
 #ifndef MERCURY_KERNEL_TERMINAL_HPP
 #define MERCURY_KERNEL_TERMINAL_HPP
 
+#include <cstddef>
 #include <cstdint>
 
 namespace mercury::kernel::terminal {
@@ -20,7 +21,7 @@ namespace mercury::kernel::terminal {
   extern framebuffer::color fg_color;
 
   void put_char(char ch);
-
+  void put_string(const char *str, size_t len);
   void put_string_sz(const char *str);
 
   void put_int_decimal(uint64_t n, bool with_commas = true);
diff --git a/include/mercury/kernel/utility.hpp b/include/mercury/kernel/utility.hpp
index dbf0cf9..f12101a 100644
--- a/include/mercury/kernel/utility.hpp
+++ b/include/mercury/kernel/utility.hpp
@@ -20,101 +20,232 @@ namespace mercury::kernel::utility {
     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;
+  }
+
   template <class value_t>
-  struct string_tree {
+  struct list {
 
-    std::optional<value_t> value_here = {};
-    string_tree<value_t> *parent = 0;
-    string_tree<value_t> *subtrees[256] = {};
+    struct node {
+      value_t value;
+      node *next;
+      node *prev;
+    };
 
-    //if there is a node whose key has a prefix in common with str, then this
-    //returns the deepest such node, and sets leftover_out to point to the
-    //character of str after the common prefix with that returned node. if
-    //there is no such node, this returns the current node and sets
-    //leftover_out to a null pointer.
-    string_tree &max_common_prefix(
-        const char *str, size_t str_len, const char *&leftover_out) {
+    node *first;
+    node *last;
 
-      string_tree<value_t> *last_with_value = 0;
-      const char *leftover_at_last_with_value = 0;
-      string_tree<value_t> *on = this;
-      size_t len_so_far = 0;
+    list() : first(0), last(0) {}
 
-      while (true) {
+    ~list() {
+      if (first) {
+        for (node *n = first->next; n; n = n->next)
+          delete n->prev;
+        delete last;
+      }
+    }
 
-        if (on->value_here) {
-          last_with_value = on;
-          leftover_at_last_with_value = str + len_so_far;
-        }
+    void insert_end(const value_t &value) {
+      node *n = new node {};
+      n->value = value;
+      n->next = 0;
+      n->prev = last;
+      last = n;
+    }
 
-        if (len_so_far == str_len)
-          break;
+    void insert_end(value_t &&value) {
+      node *n = new node {};
+      n->value = value;
+      n->next = 0;
+      n->prev = last;
+      last = n;
+    }
 
-        on = on->subtrees[(uint8_t)str[len_so_far]];
-        if (!on)
-          break;
+    void clear() {
+      for (node *n = first; n; n = n->next)
+        delete n;
+      first = 0;
+      last = 0;
+    }
 
-        ++len_so_far;
+    //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;
+    }
 
-      }
+  };
 
-      if (last_with_value) {
-        leftover_out = leftover_at_last_with_value;
-        return *last_with_value;
-      }
+  template <class value_t>
+  struct vector {
 
-      leftover_out = 0;
-      return *this;
+    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];
     }
 
-    bool try_insert(const char *str, size_t str_len, value_t value) {
+    ~vector() {
+      if (buffer)
+        delete[] buffer;
+    }
 
-      string_tree<value_t> *on = this;
-      for (size_t i = 0; i < str_len; ++i) {
-        string_tree<value_t> *&subtree = on->subtrees[(uint8_t)str[i]];
-        if (!subtree) {
-          subtree = new string_tree<value_t>();
-          subtree->parent = on;
-        }
-        on = subtree;
-      }
+    vector<value_t> &operator =(const vector<value_t> &other) {
+      if (buffer)
+        delete[] buffer;
+      buffer = new value_t[other.buffer_len];
+      buffer_len = other.buffer_len;
+      for (unsigned i = 0; i < other.count; ++i)
+        buffer[i] = other.buffer[i];
+      return *this;
+    }
 
-      if (on->value_here)
+    vector<value_t> &operator =(vector<value_t> &&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<value_t> &other) {
+      if (other.count != count)
         return false;
-      on->value_here = value;
+      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] = std::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] = std::move(v);
+      ++count;
+    }
+
+    void add_end(const value_t &v) {
+      verify_buffer_len(count + 1);
+      buffer[count] = v;
+      ++count;
     }
 
   };
 
-  //if c appears in str, this returns the index of the first time it appears.
-  //otherwise, this returns len.
-  static inline size_t find(const char *str, size_t len, char c) {
-    for (size_t i = 0; i < len; ++i)
-      if (str[i] == c)
-        return i;
-    return len;
-  }
+  typedef vector<char> string;
 
-  template <class value_t>
-  struct flist {
+  template <class key_component_t, class value_t>
+  struct trie {
 
-    struct node {
-      value_t value;
-      node *next;
+    typedef vector<key_component_t> key_t;
+
+    struct child {
+      key_component_t component;
+      trie tr;
     };
 
-    node *first;
+    //really this should be a hashmap or something
+    vector<child> children;
+
+    trie *try_get_child(const key_component_t &component) const {
+      for (unsigned i = 0; i < children.count; ++i)
+        if (children.buffer[i].component == component)
+          return &children.buffer[i].tr;
+      return 0;
+    }
+
+    std::optional<value_t> value_here;
+
+    trie() : children(0) {}
 
-    flist() : first(0) {}
+    //prefix length is in key components, with the root node having a prefix
+    //length of 0. if no prefix of key has a value, then this just returns the
+    //root node and sets prefix length to 0.
+    const trie &longest_prefix_with_value(
+      const key_t &key, unsigned &prefix_length_out
+    ) const {
 
-    void insert(value_t value) {
-      first = new node {
-        .value = value,
-        .next = first
-      };
+      const trie *on = this;
+      unsigned with_i = 0;
+
+      const trie *longest_found = this;
+      prefix_length_out = 0;
+
+      while (true) {
+        if (with_i == key.count)
+          return *longest_found;
+        on = on->try_get_child(key.buffer[with_i]);
+        if (!on)
+          return *longest_found;
+        ++with_i;
+        if (on->value_here) {
+          longest_found = on;
+          prefix_length_out = with_i;
+        }
+      }
+
+    }
+
+    bool has_key(const key_t &key) {
+      const trie *on = this;
+      for (unsigned i = 0; i < key.count; ++i) {
+        on = on->try_get_child(key.buffer[i]);
+        if (!on)
+          return false;
+      }
+      return on->value_here.has_value();
+    }
+
+    //returns false if this key is already in use.
+    bool try_insert(const key_t &key, value_t value) {
+      trie *on = this;
+      for (unsigned i = 0; i < key.count; ++i) {
+        on = on->try_get_child(key.buffer[i]);
+        if (!on) {
+          child ch;
+          ch.component = key.buffer[i];
+          on->children.add_end(std::move(ch));
+          on = &on->children.buffer[on->children.count - 1].tr;
+        }
+      }
+      if (on->value_here)
+        return false;
+      *on->value_here = value;
+      return true;
     }
 
   };