summaryrefslogtreecommitdiff
path: root/include/mercury/kernel
diff options
context:
space:
mode:
Diffstat (limited to 'include/mercury/kernel')
-rw-r--r--include/mercury/kernel/bd/memory.hpp23
-rw-r--r--include/mercury/kernel/fs/tarfs.hpp40
-rw-r--r--include/mercury/kernel/paging.hpp3
-rw-r--r--include/mercury/kernel/storage.hpp130
-rw-r--r--include/mercury/kernel/terminal.hpp3
-rw-r--r--include/mercury/kernel/utility.hpp261
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;
}
};
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-21 17:23:26 +0000