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

7 files changed, 706 insertions, 15 deletions

diff --git a/kernel/allocator.cpp b/kernel/allocator.cpp
new file mode 100644
index 0000000..b04078c
--- /dev/null
+++ b/kernel/allocator.cpp
@@ -0,0 +1,160 @@
+#include <mercury/kernel/paging.hpp>
+#include <cstddef>
+
+namespace mercury::kernel::allocator {
+
+  struct free_entry {
+    uint64_t start;
+    uint64_t len;//0 for unused
+  };
+
+  struct free_page {
+    free_page *next;
+    free_entry entries[255];
+  };
+
+  free_page *first_page;
+
+  static_assert(sizeof(free_page) == 4088);
+
+  free_entry *get_entry(uint64_t start, uint64_t len) {
+    for (free_page *fp = first_page; fp; fp = fp->next)
+      for (int i = 0; i < 255; ++i)
+        if (fp->entries[i].start == start && fp->entries[i].len == len)
+          return fp->entries + i;
+    return 0;
+  }
+
+  void add_entry(uint64_t start, uint64_t len) {
+    for (free_page *fp = first_page; fp; fp = fp->next)
+      for (int i = 0; i < 255; ++i)
+        if (fp->entries[i].len == 0) {
+          fp->entries[i].start = start;
+          fp->entries[i].len = len;
+          return;
+        }
+    free_page *new_page = (free_page *)paging::map_new_kernel_pages(1);
+    new_page->next = first_page;
+    first_page = new_page;
+    for (int i = 2; i < 255; ++i)
+      new_page->entries[i].len = 0;
+    new_page->entries[0].start = (uint64_t)new_page + 4088;
+    new_page->entries[0].len = 8;
+    new_page->entries[1].start = start;
+    new_page->entries[1].len = len;
+  }
+
+  //len is power of 2, start is len-aligned
+  void free_block(uint64_t start, uint64_t len) {
+    free_entry *buddy = get_entry(start ^ len, len);
+    if (buddy) {
+      buddy->start = start & ~len;
+      buddy->len = len * 2;
+    }
+    else
+      add_entry(start, len);
+  }
+
+  void free_region(uint64_t start, uint64_t len) {
+    uint64_t block_size = 1;
+    while (block_size <= len) {
+      if (start & block_size) {
+        free_block(start, block_size);
+        start += block_size;
+        len -= block_size;
+      }
+      block_size *= 2;
+    }
+    while (len) {
+      block_size /= 2;
+      if (block_size <= len) {
+        free_block(start, block_size);
+        start += block_size;
+        len -= block_size;
+      }
+    }
+    //testing
+    if (len != 0)
+      while (1)
+        ;
+  }
+
+  uint64_t take_region(uint64_t len) {
+
+    uint64_t min_size = 1;
+    while (min_size < len)
+      min_size *= 2;
+
+    free_entry *entry = 0;
+
+    for (free_page *fp = first_page; fp; fp = fp->next)
+      for (int i = 0; i < 255; ++i)
+        if (fp->entries[i].len >= min_size) {
+          if (fp->entries[i].len == min_size) {
+            entry = fp->entries + i;
+            goto loop_done;
+          }
+          if (entry == 0 || fp->entries[i].len < entry->len)
+            entry = fp->entries + i;
+        }
+
+  loop_done:
+    if (entry != 0) {
+      uint64_t start = entry->start;
+      uint64_t block_len = entry->len;
+      entry->len = 0;
+      if (block_len != len)
+        free_region(start + len, block_len - len);
+      return start;
+    }
+
+    uint64_t pages = (len - 1) / 4096 + 1;
+    uint64_t start = (uint64_t)paging::map_new_kernel_pages(pages);
+    if (pages * 4096 != len)
+      free_region(start + len, pages * 4096 - len);
+    return start;
+
+  }
+
+}
+
+using namespace mercury::kernel::allocator;
+
+void *_new(size_t len) {
+  if (len == 0)
+    return 0;
+  uint64_t vaddr = take_region(len + sizeof(size_t));
+  *(size_t *)vaddr = len;
+  return (void *)(vaddr + sizeof(size_t));
+}
+
+void _delete(void *ptr) {
+  if ((uint64_t)ptr == 0)
+    return;
+  uint64_t vaddr = (uint64_t)ptr - sizeof(size_t);
+  free_region(vaddr, *(size_t *)vaddr + sizeof(size_t));
+}
+
+void *operator new(size_t len) {
+  return _new(len);
+}
+
+void operator delete(void *ptr, size_t) {
+  return _delete(ptr);
+}
+
+void operator delete(void *ptr) {
+  return _delete(ptr);
+}
+
+void *operator new[](size_t len) {
+  return _new(len);
+}
+
+void operator delete[](void *ptr, size_t) {
+  return _delete(ptr);
+}
+
+void operator delete[](void *ptr) {
+  return _delete(ptr);
+}
diff --git a/kernel/bd/memory.cpp b/kernel/bd/memory.cpp
new file mode 100644
index 0000000..1015e40
--- /dev/null
+++ b/kernel/bd/memory.cpp
@@ -0,0 +1,27 @@
+#include <mercury/kernel/bd/memory.hpp>
+
+namespace mercury::kernel::bd {
+
+  memory::memory(void *buffer, size_t buffer_len) : buffer((uint8_t *)buffer) {
+    block_size = 1;
+    block_count = buffer_len;
+    //block cache will never be used, since the block size is 1.
+  }
+
+  storage::io_result memory::read_blocks_no_cache(
+    uint64_t start, uint64_t count, void *into
+  ) {
+    for (uint64_t i = 0; i < count; ++i)
+      ((uint8_t *)into)[i] = buffer[start + i];
+    return storage::io_result::success;
+  }
+
+  storage::io_result memory::write_blocks_no_cache(
+    uint64_t start, uint64_t count, const void *into
+  ) {
+    for (uint64_t i = 0; i < count; ++i)
+      buffer[start + i] = ((uint8_t *)into)[i];
+    return storage::io_result::success;
+  }
+
+}
diff --git a/kernel/entry.cpp b/kernel/entry.cpp
index c8f74c8..fb85ad2 100644
--- a/kernel/entry.cpp
+++ b/kernel/entry.cpp
@@ -1,4 +1,6 @@
 #include <mercury/kernel/framebuffer.hpp>
+#include <mercury/kernel/bd/memory.hpp>
+#include <mercury/kernel/fs/tarfs.hpp>
 #include <mercury/kernel/terminal.hpp>
 #include <mercury/kernel/limine.hpp>
 #include <mercury/kernel/paging.hpp>
@@ -177,9 +179,28 @@ extern "C" [[noreturn]] void entry() {
 
 }
 
+[[noreturn]] static void halt() {
+  while (1)
+    ;
+}
+
 [[noreturn]] static void with_kernel_p4() {
 
   terminal::init_terminal();
+  storage::init_storage();
+
+  storage::block_device *initfs_bd = new bd::memory(initfs, initfs_len);
+  storage::block_devices->insert_end(initfs_bd);
+
+  storage::canon_path root;
+  storage::canonize_path("/", 1, root);
+
+  if (storage::mount_device(initfs_bd, root, &fs::tarfs_mounter) !=
+      storage::io_result::success) {
+    terminal::put_string_sz("failed to mount initfs.");
+    halt();
+  }
+
   terminal::put_string_sz("kernel initialization complete.\n");
 
   int used_vram_kib = paging::get_used_vram_page_count() * 4;
@@ -190,23 +211,24 @@ extern "C" [[noreturn]] void entry() {
   terminal::put_int_decimal(free_pram_kib);
   terminal::put_string_sz(" kiB physical memory free.\n");
 
-  terminal::put_string_sz("initfs first sector:");
-  for (int y = 0; y < 8; ++y) {
-    terminal::put_string_sz("\n  ");
-    for (int x = 0; x < 64; ++x)
-      terminal::put_char((char)initfs[y * 64 + x]);
-  }
+  storage::canon_path test_path;
+  storage::canonize_path("/test.txt", 9, test_path);
 
-  terminal::put_string_sz("\ninitfs second sector:");
-  for (int y = 0; y < 8; ++y) {
-    terminal::put_string_sz("\n  ");
-    for (int x = 0; x < 64; ++x)
-      terminal::put_char((char)initfs[512 + y * 64 + x]);
+  storage::block_device *test_bd;
+  storage::node_id_t test_node_id;
+  storage::canon_path test_path_without_symlinks;
+
+  if (storage::look_up_absolute_path(
+        test_path, test_bd, test_node_id, true, test_path_without_symlinks) !=
+      storage::io_result::success) {
+    terminal::put_string_sz("failed to look up /test.txt in vfs.");
+    halt();
   }
 
-  while (1)
-    ;
+  terminal::put_string_sz("/test.txt has node id ");
+  terminal::put_int_decimal(test_node_id);
+  terminal::put_string_sz(" in its file system.");
 
-  //TODO
+  halt();
 
 }
diff --git a/kernel/fs/tarfs.cpp b/kernel/fs/tarfs.cpp
new file mode 100644
index 0000000..706280e
--- /dev/null
+++ b/kernel/fs/tarfs.cpp
@@ -0,0 +1,224 @@
+#include <mercury/kernel/fs/tarfs.hpp>
+
+//in fs::tarfs_instance, storage::node_id_t refers to the number
+//of bytes into the block device that the info sector is located
+
+namespace mercury::kernel::fs {
+
+  storage::io_result tarfs_mounter(
+    storage::block_device *bd, storage::file_system_instance *&fs_out
+  ) {
+    fs_out = new tarfs_instance(bd);
+    return storage::io_result::success;
+  }
+
+  tarfs_instance::tarfs_instance(storage::block_device *bd) : bd(bd) {}
+
+  storage::io_result tarfs_instance::next_node(storage::node_id_t &node) {
+    uint64_t file_length;
+    storage::io_result result = read_num(node + 124, 12, file_length);
+    if (result != storage::io_result::success)
+      return result;
+    node += ((file_length - 1) / 512 + 2) * 512;
+    return storage::io_result::success;
+  }
+
+  storage::io_result tarfs_instance::read_name(
+    storage::node_id_t node, char *name_buf, size_t &name_len_out
+  ) {
+    name_len_out = 0;
+    storage::io_result result = bd->read_bytes(node + 345, 155, name_buf);
+    if (result != storage::io_result::success)
+      return result;
+    while (name_buf[name_len_out] && name_len_out < 155)
+      ++name_len_out;
+    result = bd->read_bytes(node, 100, name_buf + name_len_out);
+    if (result != storage::io_result::success)
+      return result;
+    size_t new_limit = name_len_out + 100;
+    while (name_buf[name_len_out] && name_len_out < new_limit)
+      ++name_len_out;
+    return storage::io_result::success;
+  }
+
+  storage::io_result tarfs_instance::read_num(
+    uint64_t offset, size_t len, uint64_t &out
+  ) {
+
+    //len <= 12
+    char buffer[12];
+    storage::io_result result = bd->read_bytes(offset, len, buffer);
+    out = 0;
+
+    for (size_t i = 0; i < len; ++i) {
+      if (!buffer[i])
+        return i == 0 ? storage::io_result::fs_corrupt
+                      : storage::io_result::success;
+      if (buffer[i] < '0' || buffer[i] > '7')
+        return storage::io_result::fs_corrupt;
+      out = out * 8 + buffer[i] - '0';
+    }
+
+    return storage::io_result::success;
+
+  }
+
+#define RETURN_MAYBE_NOT_FOUND(expr) \
+  { \
+    storage::io_result _result = expr; \
+    if (_result == storage::io_result::out_of_bounds) \
+      return storage::io_result::not_found; \
+    if (_result != storage::io_result::success) \
+      return _result; \
+  }
+
+  storage::io_result tarfs_instance::get_root_node(storage::node_id_t &out) {
+    out = 0;
+    while (true) {
+      char name_buf[255];
+      size_t name_len;
+      RETURN_MAYBE_NOT_FOUND(read_name(out, name_buf, name_len))
+      if (name_len == 2 && name_buf[0] == '.' && name_buf[1] == '/')
+        return storage::io_result::success;
+      RETURN_MAYBE_NOT_FOUND(next_node(out))
+    }
+  }
+
+  storage::io_result tarfs_instance::get_first_child(storage::node_id_t node,
+    storage::node_id_t &out, storage::directory_iter_t &iter_out
+  ) {
+
+    out = 0;
+    while (true) {
+
+      char name_buf[255];
+      size_t name_len;
+      RETURN_MAYBE_NOT_FOUND(read_name(out, name_buf, name_len))
+
+      //TODO
+      while (1)
+        ;
+
+      RETURN_MAYBE_NOT_FOUND(next_node(out))
+
+    }
+
+  }
+
+  storage::io_result tarfs_instance::get_next_child(storage::node_id_t node,
+    storage::node_id_t &out, storage::directory_iter_t &iter
+  ) {
+
+    out = iter;
+    while (true) {
+
+      char name_buf[255];
+      size_t name_len;
+      RETURN_MAYBE_NOT_FOUND(read_name(out, name_buf, name_len))
+
+      //TODO
+      //NOTE: before return, do iter = out.
+      while (1)
+        ;
+
+
+      RETURN_MAYBE_NOT_FOUND(next_node(out))
+
+    }
+
+  }
+
+  storage::io_result tarfs_instance::get_child(storage::node_id_t node,
+    storage::node_id_t &out, const char *name, size_t name_len
+  ) {
+
+    char full_name[255];
+    size_t full_name_len;
+    RETURN_MAYBE_NOT_FOUND(read_name(out, full_name, full_name_len))
+
+    if (full_name_len + name_len > 255)
+      return storage::io_result::not_supported;
+
+    for (size_t i = 0; i < name_len; ++i)
+      full_name[full_name_len + i] = name[i];
+    full_name_len += name_len;
+
+    out = 0;
+    while (true) {
+
+      char cand_name[255];
+      size_t cand_name_len;
+      RETURN_MAYBE_NOT_FOUND(read_name(out, cand_name, cand_name_len))
+
+      if (cand_name_len != full_name_len)
+        goto next_iter;
+      for (size_t i = 0; i < full_name_len; ++i)
+        if (cand_name[i] != full_name[i])
+          goto next_iter;
+
+      return storage::io_result::success;
+
+    next_iter:
+      RETURN_MAYBE_NOT_FOUND(next_node(out))
+
+    }
+
+  }
+
+  storage::io_result tarfs_instance::get_name_length(
+    storage::node_id_t node, size_t &length_out
+  ) {
+
+    //TODO
+    while (1)
+      ;
+
+  }
+
+  storage::io_result tarfs_instance::get_name(
+    storage::node_id_t node, char *buffer, size_t &length_out
+  ) {
+
+    //TODO
+    while (1)
+      ;
+
+  }
+
+  storage::io_result tarfs_instance::get_file_length(
+    storage::node_id_t node, uint64_t &length_out
+  ) {
+
+    //TODO
+    while (1)
+      ;
+
+  }
+
+  storage::io_result tarfs_instance::get_file_type(
+    storage::node_id_t node, storage::file_type &out
+  ) {
+
+    uint64_t ft;
+    storage::io_result result = read_num(node + 156, 1, ft);
+    if (result != storage::io_result::success)
+      return result;
+
+    switch (ft) {
+    case 0:
+      out = storage::file_type::regular_file;
+      return storage::io_result::success;
+    case 2:
+      out = storage::file_type::symlink;
+      return storage::io_result::success;
+    case 5:
+      out = storage::file_type::directory;
+      return storage::io_result::success;
+    default:
+      return storage::io_result::not_supported;
+    }
+
+  }
+
+
+}
diff --git a/kernel/paging.cpp b/kernel/paging.cpp
index 3bd27d0..8c27abc 100644
--- a/kernel/paging.cpp
+++ b/kernel/paging.cpp
@@ -96,6 +96,13 @@ namespace mercury::kernel::paging {
     return 0;
   }
 
+  void *map_new_kernel_pages(uint64_t count) {
+    uint64_t vaddr = find_unmapped_vram_region(count);
+    for (uint64_t i = 0; i < count; ++i)
+      map_kernel_page(take_pram_page(), vaddr + i * 4096, true, false);
+    return (void *)vaddr;
+  }
+
   uint64_t get_used_vram_page_count() {
     uint64_t count = 0;
     for (uint64_t i = 0; i < kernel_vram_pages; ++i)
diff --git a/kernel/storage.cpp b/kernel/storage.cpp
new file mode 100644
index 0000000..ff86896
--- /dev/null
+++ b/kernel/storage.cpp
@@ -0,0 +1,246 @@
+#include <mercury/kernel/storage.hpp>
+
+#define RETURN_IF_NOT_SUCCESS(expr) \
+  { \
+    io_result _result = expr; \
+    if (_result != io_result::success) \
+      return _result; \
+  }
+
+namespace mercury::kernel::storage {
+
+  io_result block_device::load_cache_block(uint64_t i) {
+
+    if (block_cache_i == i)
+      return io_result::success;
+
+    if (block_cache_dirty) {
+      RETURN_IF_NOT_SUCCESS(
+        write_blocks_no_cache(block_cache_i, 1, block_cache))
+      block_cache_dirty = false;
+    }
+
+    io_result result = read_blocks_no_cache(i, 1, block_cache);
+
+    if (result != io_result::success) {
+      block_cache_i = block_count;
+      return result;
+    }
+
+    block_cache_i = i;
+    return io_result::success;
+
+  }
+
+  io_result block_device::read_bytes(
+    uint64_t start, uint64_t count, void *into
+  ) {
+
+    if (start + count > block_size * block_count)
+      return io_result::out_of_bounds;
+
+    uint8_t *into_u8 = (uint8_t *)into;
+
+    if (start % block_size != 0) {
+      uint64_t prefix_len = block_size - start % block_size;
+      RETURN_IF_NOT_SUCCESS(load_cache_block(start / block_size))
+      for (uint64_t i = 0; i < prefix_len; ++i)
+        into_u8[i] = block_cache[start % block_size + i];
+      into_u8 += prefix_len;
+      start += prefix_len;
+      count -= prefix_len;
+    }
+
+    uint64_t postfix_start = ((start + count) / block_size) * block_size;
+
+    if (postfix_start != start) {
+      RETURN_IF_NOT_SUCCESS(read_blocks_no_cache(
+        start / block_size, (postfix_start - start) / block_size, into_u8))
+      count -= postfix_start - start;
+      into_u8 += postfix_start - start;
+      start = postfix_start;
+    }
+
+    if (count != 0) {
+      RETURN_IF_NOT_SUCCESS(load_cache_block(start / block_size))
+      for (uint64_t i = 0; i < count; ++i)
+        into_u8[i] = block_cache[i];
+    }
+
+    return io_result::success;
+
+  }
+
+  utility::list<block_device *> *block_devices;
+
+  static utility::trie<utility::string, block_device *> *mounted_devices;
+
+  void init_storage() {
+    block_devices = new utility::list<block_device *>();
+    mounted_devices = new utility::trie<utility::string, block_device *>();
+  }
+
+  void canon_path::parent() {
+    if (segments.count != 0)
+      --segments.count;
+    else if (!absolute)
+      ++parent_count;
+  }
+
+  void canon_path::rel(const canon_path &r) {
+    if (r.absolute) {
+      segments.count = 0;
+      absolute = true;
+      parent_count = 0;
+    }
+    for (unsigned i = 0; i < r.parent_count; ++i)
+      parent();
+    for (unsigned i = 0; i < r.segments.count; ++i)
+      segments.add_end(r.segments.buffer[i]);
+  }
+
+  void canonize_path(const char *str, size_t len, canon_path &out) {
+
+    out.absolute = false;
+    out.parent_count = 0;
+    out.segments.count = 0;
+
+    if (len == 0)
+      return;
+
+    if (len == 1 && str[0] == '/') {
+      out.absolute = true;
+      return;
+    }
+
+    if (str[0] == '/') {
+      out.absolute = true;
+      ++str;
+      --len;
+    }
+
+    while (len != 0) {
+
+      size_t segment_len = utility::find(str, len, '/');
+      size_t to_skip = segment_len == len ? len : len + 1;
+
+      if (segment_len == 0)
+        ;
+
+      else if (segment_len == 1 && str[0] == '.')
+        ;
+
+      else if (segment_len == 2 && str[0] == '.' && str[1] == '.')
+        out.parent();
+
+      else {
+        utility::string segment(str, segment_len);
+        out.segments.add_end(std::move(segment));
+      }
+
+      str += to_skip;
+      len -= to_skip;
+
+    }
+
+  }
+
+  io_result mount_device(
+    block_device *bd, const canon_path &path, file_system_mounter mounter
+  ) {
+
+    if (!path.absolute)
+      return io_result::bad_path;
+
+    if (mounted_devices->has_key(path.segments))
+      return io_result::mount_point_already_used;
+
+    file_system_instance *fs;
+    RETURN_IF_NOT_SUCCESS(mounter(bd, fs));
+    bd->mounted_as = fs;
+    mounted_devices->try_insert(path.segments, bd);
+    return io_result::success;
+
+  }
+
+  static io_result symlink_contents(
+    block_device *bd, node_id_t node, canon_path &out
+  ) {
+    //TODO
+    while (1)
+      ;
+  }
+
+  static io_result resolve_symlinks(
+    block_device *&bd, node_id_t &node, canon_path &path
+  ) {
+
+    file_type ft;
+    RETURN_IF_NOT_SUCCESS(bd->mounted_as->get_file_type(node, ft))
+
+    if (ft != file_type::symlink)
+      return io_result::success;
+
+    canon_path contents;
+    RETURN_IF_NOT_SUCCESS(symlink_contents(bd, node, contents))
+    path.parent();
+    path.rel(contents);
+
+    return look_up_absolute_path(path, bd, node, true, path);
+
+  }
+
+  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
+  ) {
+
+    if (!path.absolute)
+      return io_result::bad_path;
+
+    unsigned prefix_length;
+    bd_out =
+      *mounted_devices->longest_prefix_with_value(path.segments, prefix_length)
+        .value_here;
+    RETURN_IF_NOT_SUCCESS(bd_out->mounted_as->get_root_node(node_out))
+
+    path_without_symlinks_out.absolute = true;
+    path_without_symlinks_out.parent_count = 0;
+    path_without_symlinks_out.segments.count = 0;
+
+    for (unsigned i = 0; i < prefix_length; ++i)
+      path_without_symlinks_out.segments.add_end(path.segments.buffer[i]);
+
+    for (unsigned i = prefix_length; i < path.segments.count - 1; ++i) {
+
+      path_without_symlinks_out.segments.add_end(path.segments.buffer[i]);
+
+      RETURN_IF_NOT_SUCCESS(bd_out->mounted_as->get_child(node_out, node_out,
+        path.segments.buffer[i].buffer, path.segments.buffer[i].count))
+      RETURN_IF_NOT_SUCCESS(resolve_symlinks(
+        bd_out, node_out, path_without_symlinks_out))
+
+      file_type ft;
+      RETURN_IF_NOT_SUCCESS(bd_out->mounted_as->get_file_type(node_out, ft))
+
+      if (ft != file_type::directory)
+        return io_result::not_a_directory;
+
+    }
+
+    const utility::string &last_segment =
+      path.segments.buffer[path.segments.count - 1];
+    path_without_symlinks_out.segments.add_end(last_segment);
+
+    RETURN_IF_NOT_SUCCESS(bd_out->mounted_as->get_child(
+      node_out, node_out, last_segment.buffer, last_segment.count))
+
+    if (resolve_final_node)
+      RETURN_IF_NOT_SUCCESS(resolve_symlinks(
+        bd_out, node_out, path_without_symlinks_out))
+
+    return io_result::success;
+
+  }
+
+}
diff --git a/kernel/terminal.cpp b/kernel/terminal.cpp
index f017cad..7a878ee 100644
--- a/kernel/terminal.cpp
+++ b/kernel/terminal.cpp
@@ -74,8 +74,13 @@ namespace mercury::kernel::terminal {
     }
   }
 
+  void put_string(const char *str, size_t len) {
+    for (size_t i = 0; i < len; ++i)
+      put_char(str[i]);
+  }
+
   void put_string_sz(const char *str) {
-    for (int i = 0; str[i]; ++i)
+    for (size_t i = 0; str[i]; ++i)
       put_char(str[i]);
   }