From 882e74b2191c059a9226cbd8bcb51c97da36247c Mon Sep 17 00:00:00 2001 From: Benji Dial Date: Fri, 12 Jan 2024 20:39:21 -0500 Subject: rewrite file system layer --- include/mercury/kernel/bd/memory.hpp | 23 ------ include/mercury/kernel/fs/tarfs.hpp | 45 ----------- include/mercury/kernel/storage.hpp | 107 ++++++++++---------------- include/mercury/kernel/storage/bd/memory.hpp | 22 ++++++ include/mercury/kernel/storage/fs/tarfs.hpp | 32 ++++++++ include/mercury/kernel/terminal.hpp | 4 +- include/mercury/kernel/utility.hpp | 108 +++++++-------------------- include/mercury/kernel/vfile.hpp | 62 +++++++++++++++ 8 files changed, 186 insertions(+), 217 deletions(-) delete mode 100644 include/mercury/kernel/bd/memory.hpp delete mode 100644 include/mercury/kernel/fs/tarfs.hpp create mode 100644 include/mercury/kernel/storage/bd/memory.hpp create mode 100644 include/mercury/kernel/storage/fs/tarfs.hpp create mode 100644 include/mercury/kernel/vfile.hpp (limited to 'include') 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 - -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 - -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 &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 &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_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 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 + +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 + +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 &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 &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 &out, directory_iter_t &iter_out); + fs_result get_next_child(node_id_t node, std::optional &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 +#include #include #include @@ -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 @@ -124,6 +136,14 @@ namespace mercury::kernel::utility { 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() { 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 string; - - template - struct trie { - - typedef vector key_t; - - struct child { - key_component_t component; - trie tr; - }; - - //really this should be a hashmap or something - vector 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_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 &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 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 +#include + +//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 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 &out) const; + + //dir_entry.type is assumed to be directory. + storage::fs_result get_child( + std::optional &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 &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 &out); + +} + +#endif -- cgit v1.2.3