rewrite file system layer

8 files changed, 186 insertions, 217 deletions

diff --git a/include/mercury/kernel/bd/memory.hpp b/include/mercury/kernel/bd/memory.hpp
deleted file mode 100644
index 079abee..0000000
--- a/include/mercury/kernel/bd/memory.hpp
+++ /dev/null
@@ -1,23 +0,0 @@
-#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
deleted file mode 100644
index 64ee481..0000000
--- a/include/mercury/kernel/fs/tarfs.hpp
+++ /dev/null
@@ -1,45 +0,0 @@
-#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, unsigned &name_len_out);
-    //len <= 12
-    storage::io_result read_num(uint64_t offset, unsigned 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, unsigned name_len) override;
-    storage::io_result get_name_length(storage::node_id_t node, unsigned &length_out) override;
-    storage::io_result get_name(storage::node_id_t node, char *buffer, unsigned &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 resize_file(storage::node_id_t node, uint64_t new_length) override;
-    storage::io_result read_bytes_from_file(
-      storage::node_id_t node, uint64_t start, uint64_t count, void *into) override;
-    storage::io_result write_bytes_into_file(
-      storage::node_id_t node, uint64_t start, uint64_t count, const void *from) override;
-
-  };
-
-  storage::io_result tarfs_mounter(storage::block_device *bd, storage::file_system_instance *&fs_out);
-
-}
-
-#endif
diff --git a/include/mercury/kernel/storage.hpp b/include/mercury/kernel/storage.hpp
index 0df0829..61e7d3b 100644
--- a/include/mercury/kernel/storage.hpp
+++ b/include/mercury/kernel/storage.hpp
@@ -9,22 +9,32 @@ namespace mercury::kernel::storage {
   typedef uint64_t node_id_t;
   typedef uint64_t directory_iter_t;
 
-  enum file_type {
+  enum class file_type {
     regular_file,
     directory,
     symlink
   };
 
-  enum io_result {
+  enum class bd_result {
     success,
-    mount_point_already_used,
-    not_a_directory,
-    not_supported,
     out_of_bounds,
+    device_error
+  };
+
+  enum class fs_result {
+    success,
     device_error,
-    fs_corrupt,
-    not_found,
-    bad_path,
+    fs_corrupt
+  };
+
+  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 {
@@ -32,27 +42,21 @@ namespace mercury::kernel::storage {
   public:
     virtual ~file_system_instance() {}
 
-    virtual io_result get_root_node(node_id_t &out) = 0;
+    virtual fs_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::not_found. when iter represents the last child of a node,
-    //get_next_child also returns io_result::not_found.
-    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, unsigned name_len) = 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, std::optional<dir_entry> &out, directory_iter_t &iter_out) = 0;
 
-    virtual io_result get_name_length(node_id_t node, unsigned &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, unsigned &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;
+    //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, std::optional<dir_entry> &out, directory_iter_t &iter) = 0;
 
-    virtual io_result resize_file(node_id_t node, uint64_t new_length) = 0;
-    virtual io_result read_bytes_from_file(node_id_t node, uint64_t start, uint64_t count, void *into) = 0;
-    virtual io_result write_bytes_into_file(node_id_t node, uint64_t start, uint64_t count, const void *from) = 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;
 
   };
 
@@ -61,27 +65,29 @@ namespace mercury::kernel::storage {
   private:
     uint8_t *block_cache;
     uint64_t block_cache_i;
-    bool block_cache_dirty;
 
-    io_result load_cache_block(uint64_t 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, 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;
+    //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)
+    //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() {
@@ -89,45 +95,10 @@ namespace mercury::kernel::storage {
         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);
+    bd_result read_bytes(uint64_t start, uint64_t count, void *into);
 
   };
 
-  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, unsigned 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/storage/bd/memory.hpp b/include/mercury/kernel/storage/bd/memory.hpp
new file mode 100644
index 0000000..e12d565
--- /dev/null
+++ b/include/mercury/kernel/storage/bd/memory.hpp
@@ -0,0 +1,22 @@
+#ifndef MERCURY_KERNEL_STORAGE_BD_MEMORY_HPP
+#define MERCURY_KERNEL_STORAGE_BD_MEMORY_HPP
+
+#include <mercury/kernel/storage.hpp>
+
+namespace mercury::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;
+
+  };
+
+}
+
+#endif
diff --git a/include/mercury/kernel/storage/fs/tarfs.hpp b/include/mercury/kernel/storage/fs/tarfs.hpp
new file mode 100644
index 0000000..9e16207
--- /dev/null
+++ b/include/mercury/kernel/storage/fs/tarfs.hpp
@@ -0,0 +1,32 @@
+#ifndef MERCURY_KERNEL_STORAGE_FS_TARFS_HPP
+#define MERCURY_KERNEL_STORAGE_FS_TARFS_HPP
+
+#include <mercury/kernel/storage.hpp>
+
+namespace mercury::kernel::storage::fs {
+
+  class tarfs_instance : public file_system_instance {
+
+  private:
+    block_device *bd;
+
+    fs_result next_node(node_id_t node, std::optional<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, std::optional<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, std::optional<dir_entry> &out, directory_iter_t &iter_out);
+    fs_result get_next_child(node_id_t node, std::optional<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);
+
+  };
+
+}
+
+#endif
diff --git a/include/mercury/kernel/terminal.hpp b/include/mercury/kernel/terminal.hpp
index 776ff64..8efbcac 100644
--- a/include/mercury/kernel/terminal.hpp
+++ b/include/mercury/kernel/terminal.hpp
@@ -1,6 +1,8 @@
 #ifndef MERCURY_KERNEL_TERMINAL_HPP
 #define MERCURY_KERNEL_TERMINAL_HPP
 
+#include <mercury/kernel/framebuffer.hpp>
+#include <mercury/kernel/utility.hpp>
 #include <cstddef>
 #include <cstdint>
 
@@ -21,7 +23,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(const utility::string &str);
   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 1648e67..3edd7d4 100644
--- a/include/mercury/kernel/utility.hpp
+++ b/include/mercury/kernel/utility.hpp
@@ -106,6 +106,18 @@ namespace mercury::kernel::utility {
       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>
@@ -124,6 +136,14 @@ namespace mercury::kernel::utility {
         buffer[i] = copy_from[i];
     }
 
+    vector(const vector<value_t> &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() {
       if (buffer)
         delete[] buffer;
@@ -134,6 +154,7 @@ namespace mercury::kernel::utility {
         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;
@@ -185,92 +206,19 @@ namespace mercury::kernel::utility {
       ++count;
     }
 
-  };
-
-  typedef vector<char> string;
-
-  template <class key_component_t, class value_t>
-  struct trie {
-
-    typedef vector<key_component_t> key_t;
-
-    struct child {
-      key_component_t component;
-      trie tr;
-    };
-
-    //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) {}
-
-    //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 {
-
-      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)
+    bool starts_with(const vector<value_t> &other) {
+      if (count < other.count)
         return false;
-      *on->value_here = value;
+      for (unsigned i = 0; i < other.count; ++i)
+        if (buffer[i] != other.buffer[i])
+          return false;
       return true;
     }
 
   };
 
+  typedef vector<char> string;
+
 }
 
 #endif
diff --git a/include/mercury/kernel/vfile.hpp b/include/mercury/kernel/vfile.hpp
new file mode 100644
index 0000000..43dff96
--- /dev/null
+++ b/include/mercury/kernel/vfile.hpp
@@ -0,0 +1,62 @@
+#ifndef MERCURY_KERNEL_VFILE_HPP
+#define MERCURY_KERNEL_VFILE_HPP
+
+#include <mercury/kernel/storage.hpp>
+#include <mercury/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 mercury::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;
+
+    //TODO: instead of passing root, use saved mount points.
+    storage::fs_result follow_symlinks(
+      const vfile &root, std::optional<vfile> &out) const;
+
+    //dir_entry.type is assumed to be directory.
+    storage::fs_result get_child(
+      std::optional<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;
+
+  };
+
+  //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.
+  //TODO: instead of passing root, use saved mount points.
+  storage::fs_result lookup_path(
+    const vfile &root, const canon_path &path, std::optional<vfile> &out);
+
+}
+
+#endif