Merge branch 'develop-BA-FS26' into 'develop'HEADdevelop

Merge of BA-FS26 branch into develop

See merge request teachos/kernel!49

1 files changed, 247 insertions, 0 deletions

diff --git a/kernel/src/filesystem/ext2/filesystem.cpp b/kernel/src/filesystem/ext2/filesystem.cpp
new file mode 100644
index 0000000..3180a19
--- /dev/null
+++ b/kernel/src/filesystem/ext2/filesystem.cpp
@@ -0,0 +1,247 @@
+#include <kernel/filesystem/ext2/filesystem.hpp>
+
+#include <kernel/filesystem/ext2/block_group_descriptor.hpp>
+#include <kernel/filesystem/ext2/inode.hpp>
+#include <kernel/filesystem/ext2/linked_directory_entry.hpp>
+#include <kernel/filesystem/ext2/superblock.hpp>
+#include <kernel/filesystem/filesystem.hpp>
+#include <kernel/filesystem/inode.hpp>
+#include <kernel/filesystem/type.hpp>
+
+#include <kstd/memory>
+#include <kstd/unikstd.h>
+#include <kstd/vector>
+
+#include <array>
+#include <cstddef>
+#include <cstdint>
+#include <string_view>
+
+namespace kernel::filesystem::ext2
+{
+
+  struct type final : kernel::filesystem::type
+  {
+    [[nodiscard]] auto name() const noexcept -> std::string_view override
+    {
+      return "ext2";
+    }
+
+    [[nodiscard]] auto requires_device() const noexcept -> bool override
+    {
+      return true;
+    }
+
+    [[nodiscard]] auto make_instance() const -> kstd::shared_ptr<kernel::filesystem::filesystem> override
+    {
+      return kstd::make_shared<filesystem>();
+    }
+  };
+
+  [[gnu::used]]
+  constexpr auto registration = type_registration<type>{};
+
+  auto filesystem::mount(kstd::shared_ptr<kernel::filesystem::inode> const & backing_inode) -> operation_result
+  {
+    kernel::filesystem::filesystem::mount(backing_inode);
+
+    m_backing_inode->read(&m_superblock, constants::superblock_offset, sizeof(m_superblock));
+
+    if (m_superblock.magic != constants::magic_number)
+    {
+      return operation_result::invalid_magic_number;
+    }
+
+    auto const blocks_per_group = m_superblock.blocks_per_group;
+    auto const num_block_groups = (m_superblock.blocks_count + blocks_per_group - 1) / blocks_per_group;
+
+    m_block_group_descriptors = kstd::vector<block_group_descriptor>(num_block_groups);
+
+    m_backing_inode->read(m_block_group_descriptors.data(), block_group_descriptor_table_offset(),
+                          num_block_groups * sizeof(block_group_descriptor));
+
+    m_root_inode = read_inode(constants::root_inode_number);
+
+    if (!m_root_inode || !m_root_inode->is_directory())
+    {
+      return operation_result::invalid_root_inode;
+    }
+    return operation_result::success;
+  }
+
+  auto filesystem::lookup(kstd::shared_ptr<kernel::filesystem::inode> const & parent, std::string_view name) const
+      -> kstd::shared_ptr<kernel::filesystem::inode>
+  {
+    if (!parent || !parent->is_directory())
+    {
+      return nullptr;
+    }
+
+    auto * ext2_parent = static_cast<inode *>(parent.get());
+    if (!ext2_parent)
+    {
+      return nullptr;
+    }
+
+    auto const & inode_data = ext2_parent->data();
+    kstd::vector<uint8_t> buffer(block_size());
+
+    for (uint32_t i = 0; i < inode_block_count(inode_data); ++i)
+    {
+      auto const global_block_number = map_inode_block_index_to_global_block_number(i, inode_data);
+      auto const block_offset = global_block_number * block_size();
+      m_backing_inode->read(buffer.data(), block_offset, block_size());
+
+      auto const * entry = reinterpret_cast<linked_directory_entry const *>(buffer.data());
+      auto bytes_read = 0uz;
+
+      while (bytes_read < block_size() && entry->inode != 0)
+      {
+        auto const entry_name = std::string_view{entry->name.data(), entry->name_len};
+        if (entry_name == name)
+        {
+          return read_inode(entry->inode);
+        }
+
+        bytes_read += entry->rec_len;
+        entry = reinterpret_cast<linked_directory_entry const *>(buffer.data() + bytes_read);
+      }
+    }
+
+    return nullptr;
+  }
+
+  auto filesystem::read_inode(uint32_t inode_number) const -> kstd::shared_ptr<inode>
+  {
+    auto const inodes_per_group = m_superblock.inodes_per_group;
+    auto const block_group_index = (inode_number - 1) / inodes_per_group;
+    auto const inode_index_within_group = (inode_number - 1) % inodes_per_group;
+
+    if (block_group_index >= m_block_group_descriptors.size())
+    {
+      return nullptr;
+    }
+
+    auto const & block_group_descriptor = m_block_group_descriptors.at(block_group_index);
+    auto const inode_table_start_block = block_group_descriptor.inode_table;
+    auto const inode_table_offset = static_cast<size_t>(inode_table_start_block) * block_size();
+    auto const inode_offset = inode_table_offset + inode_index_within_group * inode_size();
+
+    auto new_inode_data = inode_data{};
+    m_backing_inode->read(&new_inode_data, inode_offset, sizeof(inode_data));
+
+    return kstd::make_shared<inode>(this, new_inode_data);
+  }
+
+  auto filesystem::indirect_levels() const -> std::array<indirect_level, 3>
+  {
+    return {
+      {{constants::singly_indirect_block_index, block_numbers_per_singly_indirect_block()},
+       {constants::doubly_indirect_block_index, block_numbers_per_doubly_indirect_block()},
+       {constants::triply_indirect_block_index, block_numbers_per_triply_indirect_block()}}
+    };
+  }
+
+  auto filesystem::map_inode_block_index_to_global_block_number(size_t inode_block_index, inode_data data) const
+      -> kstd::ssize_t
+  {
+    if (inode_block_index < constants::direct_block_count)
+    {
+      return data.block.at(inode_block_index);
+    }
+
+    inode_block_index -= constants::direct_block_count;
+
+    for (auto const & level : indirect_levels())
+    {
+      if (inode_block_index >= level.capacity)
+      {
+        inode_block_index -= level.capacity;
+        continue;
+      }
+
+      auto block_number = data.block[level.slot_index];
+      if (block_number == 0)
+      {
+        return 0;
+      }
+
+      for (auto stride = level.capacity / block_numbers_per_block();; stride /= block_numbers_per_block())
+      {
+        auto const idx = inode_block_index / stride;
+        inode_block_index %= stride;
+
+        block_number = read_block_number_at_index(block_number, idx);
+        if (block_number == 0)
+        {
+          return 0;
+        }
+
+        if (stride == 1)
+        {
+          break;
+        }
+      }
+
+      return block_number;
+    }
+
+    return -1;
+  }
+
+  auto filesystem::read_block_number_at_index(uint32_t block_number, size_t index) const -> uint32_t
+  {
+    uint32_t block_number_buffer = 0;
+
+    auto const block_start_offset = block_number * block_size();
+    auto const number_start_address = block_start_offset + index * sizeof(uint32_t);
+    m_backing_inode->read(&block_number_buffer, number_start_address, sizeof(uint32_t));
+
+    return block_number_buffer;
+  }
+
+  auto filesystem::block_numbers_per_block() const -> size_t
+  {
+    return block_size() / sizeof(uint32_t);
+  }
+
+  auto filesystem::block_numbers_per_singly_indirect_block() const -> size_t
+  {
+    return block_numbers_per_block();
+  }
+
+  auto filesystem::block_numbers_per_doubly_indirect_block() const -> size_t
+  {
+    return block_numbers_per_singly_indirect_block() * block_numbers_per_block();
+  }
+
+  auto filesystem::block_numbers_per_triply_indirect_block() const -> size_t
+  {
+    return block_numbers_per_doubly_indirect_block() * block_numbers_per_block();
+  }
+
+  auto filesystem::block_size() const -> size_t
+  {
+    return constants::base_block_size << m_superblock.log_block_size;
+  }
+
+  auto filesystem::revision_level() const -> uint32_t
+  {
+    return m_superblock.rev_level;
+  }
+
+  auto filesystem::inode_size() const -> uint16_t
+  {
+    return revision_level() == constants::good_old_revision ? 128 : m_superblock.inode_size;
+  }
+
+  auto filesystem::inode_block_count(inode_data const & data) const -> uint32_t
+  {
+    return data.blocks / (2 << m_superblock.log_block_size);
+  }
+
+  auto filesystem::block_group_descriptor_table_offset() const -> size_t
+  {
+    return block_size() == 1024 ? 2 * block_size() : block_size();
+  }
+}  // namespace kernel::filesystem::ext2