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

ext2 and tests

See merge request teachos/kernel!22

1 files changed, 200 insertions, 41 deletions

diff --git a/kernel/src/filesystem/ext2/filesystem.cpp b/kernel/src/filesystem/ext2/filesystem.cpp
index eb9edc4..0ad5c97 100644
--- a/kernel/src/filesystem/ext2/filesystem.cpp
+++ b/kernel/src/filesystem/ext2/filesystem.cpp
@@ -1,13 +1,17 @@
 #include "kernel/filesystem/ext2/filesystem.hpp"
 
-#include "kernel/devices/block_device_utils.hpp"
 #include "kapi/devices/device.hpp"
+
+#include "kernel/devices/block_device_utils.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 <kstd/memory>
+#include <kstd/vector>
 
 #include <cstddef>
 #include <cstdint>
@@ -17,56 +21,211 @@ namespace kernel::filesystem::ext2
 {
   namespace
   {
-    // constexpr size_t SUPERBLOCK_OFFSET = 1024;
-    // constexpr uint16_t EXT2_MAGIC = 0xEF53;
-
-    // // Mode bits
-    // constexpr uint16_t S_IFMT = 0xF000;
-    // constexpr uint16_t S_IFREG = 0x8000;
-    // constexpr uint16_t S_IFDIR = 0x4000;
-
-    // auto S_ISREG(uint16_t mode) -> bool
-    // {
-    //   return (mode & S_IFMT) == S_IFREG;
-    // }
-    // auto S_ISDIR(uint16_t mode) -> bool
-    // {
-    //   return (mode & S_IFMT) == S_IFDIR;
-    // }
-
-    // auto get_block_size(superblock const & superblock) -> size_t
-    // {
-    //   return 1024U << superblock.log_block_size;
-    // }
-
-    // auto get_inode_size(superblock const & superblock) -> size_t
-    // {
-    //   return superblock.rev_level == 0 ? 128 : superblock.inode_size;
-    // }
+    auto S_ISREG(uint16_t mode) -> bool
+    {
+      return (mode & constants::mode_mask) == constants::mode_regular;
+    }
+
+    auto S_ISDIR(uint16_t mode) -> bool
+    {
+      return (mode & constants::mode_mask) == constants::mode_directory;
+    }
   }  // namespace
 
-  auto filesystem::mount(kstd::shared_ptr<kapi::devices::device> const & device) -> int
+  auto filesystem::mount(kstd::shared_ptr<kapi::devices::device> const & device) -> operation_result
   {
-    kernel::filesystem::filesystem::mount(device);  // TODO BA-FS26 error handling?
-    // TODO BA-FS26 load proper root inode from ext2 metadata
-    // m_root_inode = inode{inode_kind::directory};
-
-    // TODO BA-FS26 implement
-    m_root_inode = kstd::make_shared<inode>();
-    // devices::block_device_utils::read(device, nullptr, 0, 0);  // TODO BA-FS26 just for testing
-    return 0;
+    kernel::filesystem::filesystem::mount(device);
+
+    kernel::devices::block_device_utils::read(m_device, &m_superblock, constants::superblock_offset,
+                                              sizeof(m_superblock));
+
+    if (m_superblock.magic != constants::magic_number)
+    {
+      return operation_result::invalid_magic_number;
+    }
+
+    auto const block_size = get_block_size();
+    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);
+
+    auto const block_group_descriptor_table_offset = block_size == 1024 ? 2 * block_size : block_size;
+    kernel::devices::block_device_utils::read(m_device, 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)
+  auto filesystem::lookup(kstd::shared_ptr<kernel::filesystem::inode> const & parent, std::string_view name)
       -> kstd::shared_ptr<kernel::filesystem::inode>
   {
-    // TODO BA-FS26 implement ext2 directory traversal and inode loading
-    if (name == "dev")
+    if (!parent || !parent->is_directory())
+    {
+      return nullptr;
+    }
+
+    auto * ext2_parent = static_cast<inode *>(parent.get());
+    if (!ext2_parent)
+    {
+      return nullptr;
+    }
+
+    auto const block_size = get_block_size();
+    auto const & inode_data = ext2_parent->m_data;
+    kstd::vector<uint8_t> buffer(block_size);
+
+    for (uint32_t i = 0; i < get_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;
+      kernel::devices::block_device_utils::read(m_device, 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) -> kstd::shared_ptr<inode>
+  {
+    auto const block_size = get_block_size();
+    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())
     {
-      // TODO BA-FS26 just for testing
       return nullptr;
     }
 
-    return kstd::make_shared<inode>();
+    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 * get_inode_size();
+
+    auto new_inode = kstd::make_shared<inode>(this);
+    kernel::devices::block_device_utils::read(m_device, &new_inode->m_data, inode_offset, sizeof(inode_data));
+
+    // TODO BA-FS26 improve inode_kind really needed? or just map it to the mode bits?
+    if (S_ISREG(new_inode->m_data.mode))
+    {
+      new_inode->m_kind = inode::inode_kind::regular;
+    }
+    else if (S_ISDIR(new_inode->m_data.mode))
+    {
+      new_inode->m_kind = inode::inode_kind::directory;
+    }
+    else
+    {
+      // TODO BA-FS26 really correct??
+      return nullptr;
+    }
+
+    return new_inode;
+  }
+
+  auto filesystem::map_inode_block_index_to_global_block_number(uint32_t inode_block_index, inode_data data) -> uint32_t
+  {
+    if (inode_block_index < constants::direct_block_count)
+    {
+      return data.block.at(inode_block_index);
+    }
+    inode_block_index -= constants::direct_block_count;
+
+    auto const block_size = get_block_size();
+    auto const numbers_per_block = block_size / sizeof(uint32_t);
+
+    auto const block_numbers_per_singly_indirect_block = numbers_per_block;
+    auto const block_numbers_per_doubly_indirect_block = numbers_per_block * block_numbers_per_singly_indirect_block;
+    auto const block_numbers_per_triply_indirect_block = numbers_per_block * block_numbers_per_doubly_indirect_block;
+
+    if (inode_block_index < block_numbers_per_singly_indirect_block)
+    {
+      auto const singly_indirect_block_number = data.block.at(constants::singly_indirect_block_index);
+      return read_block_number_at_index(singly_indirect_block_number, inode_block_index);
+    }
+    inode_block_index -= block_numbers_per_singly_indirect_block;
+
+    if (inode_block_index < block_numbers_per_doubly_indirect_block)
+    {
+      auto const doubly_indirect_block_number = data.block.at(constants::doubly_indirect_block_index);
+      auto const singly_indirect_block_index_in_doubly_indirect_block =
+          inode_block_index / block_numbers_per_singly_indirect_block;
+      auto const singly_indirect_block_number = read_block_number_at_index(
+          doubly_indirect_block_number, singly_indirect_block_index_in_doubly_indirect_block);
+
+      auto const block_index_in_singly_indirect_block = inode_block_index % block_numbers_per_singly_indirect_block;
+      return read_block_number_at_index(singly_indirect_block_number, block_index_in_singly_indirect_block);
+    }
+    inode_block_index -= block_numbers_per_doubly_indirect_block;
+
+    if (inode_block_index < block_numbers_per_triply_indirect_block)
+    {
+      auto const triply_indirect_block_number = data.block.at(constants::triply_indirect_block_index);
+      auto const doubly_indirect_block_index_in_triply_indirect_block =
+          inode_block_index / block_numbers_per_doubly_indirect_block;
+      auto const doubly_indirect_block_number = read_block_number_at_index(
+          triply_indirect_block_number, doubly_indirect_block_index_in_triply_indirect_block);
+
+      auto const remaining_block_numbers = inode_block_index % block_numbers_per_doubly_indirect_block;
+
+      auto const singly_indirect_block_index_in_doubly_indirect_block =
+          remaining_block_numbers / block_numbers_per_singly_indirect_block;
+      auto const singly_indirect_block_number = read_block_number_at_index(
+          doubly_indirect_block_number, singly_indirect_block_index_in_doubly_indirect_block);
+
+      auto const block_index_in_singly_indirect_block =
+          remaining_block_numbers % block_numbers_per_singly_indirect_block;
+      return read_block_number_at_index(singly_indirect_block_number, block_index_in_singly_indirect_block);
+    }
+
+    return 0;  // TODO BA-FS26 really correct??
+  }
+
+  auto filesystem::read_block_number_at_index(uint32_t block_number, uint32_t index) -> uint32_t
+  {
+    uint32_t block_number_buffer = 0;
+
+    auto const block_start_offset = block_number * get_block_size();
+    auto const number_start_address = block_start_offset + index * sizeof(uint32_t);
+    kernel::devices::block_device_utils::read(m_device, &block_number_buffer, number_start_address, sizeof(uint32_t));
+
+    return block_number_buffer;
+  }
+
+  auto filesystem::get_block_size() -> size_t
+  {
+    return constants::base_block_size << m_superblock.log_block_size;
+  }
+
+  auto filesystem::get_inode_size() -> size_t
+  {
+    return m_superblock.rev_level == 0 ? 128 : m_superblock.inode_size;
+  }
+
+  auto filesystem::get_inode_block_count(inode_data const & data) -> uint32_t
+  {
+    return data.blocks / (2 << m_superblock.log_block_size);
   }
 }  // namespace kernel::filesystem::ext2