implement map_inode_block_index_to_global_block_number and lookup

2 files changed, 98 insertions, 24 deletions

diff --git a/kernel/include/kernel/filesystem/ext2/filesystem.hpp b/kernel/include/kernel/filesystem/ext2/filesystem.hpp
index ccee172..dea059f 100644
--- a/kernel/include/kernel/filesystem/ext2/filesystem.hpp
+++ b/kernel/include/kernel/filesystem/ext2/filesystem.hpp
@@ -26,9 +26,11 @@ namespace kernel::filesystem::ext2
 
   private:
     auto read_inode(uint32_t inode_number) -> kstd::shared_ptr<kernel::filesystem::ext2::inode>;
+    auto map_inode_block_index_to_global_block_number(uint32_t inode_block_index, inode_data data) -> uint32_t;
 
     auto get_block_size() -> size_t;
     auto get_inode_size() -> size_t;
+    auto get_inode_block_count(inode_data const & data) -> uint32_t;
 
     superblock m_superblock;
     kstd::vector<block_group_descriptor> m_block_group_descriptors;
diff --git a/kernel/src/filesystem/ext2/filesystem.cpp b/kernel/src/filesystem/ext2/filesystem.cpp
index 82fcba9..a84414f 100644
--- a/kernel/src/filesystem/ext2/filesystem.cpp
+++ b/kernel/src/filesystem/ext2/filesystem.cpp
@@ -11,6 +11,7 @@
 #include "kernel/filesystem/inode.hpp"
 
 #include <kstd/memory>
+#include <kstd/print>
 #include <kstd/string>
 #include <kstd/vector>
 
@@ -26,7 +27,11 @@ namespace kernel::filesystem::ext2
     constexpr uint16_t MAGIC_NUMBER = 0xEF53;
 
     constexpr uint32_t ROOT_INODE_NUMBER = 2;
+
     constexpr size_t DIRECT_BLOCK_COUNT = 12;
+    constexpr size_t INDIRECT_BLOCK_INDEX = DIRECT_BLOCK_COUNT;
+    constexpr size_t DOUBLY_INDIRECT_BLOCK_INDEX = INDIRECT_BLOCK_INDEX + 1;
+    constexpr size_t TRIPLY_INDIRECT_BLOCK_INDEX = DOUBLY_INDIRECT_BLOCK_INDEX + 1;
 
     // Mode bits
     constexpr uint16_t S_IFMT = 0xF000;
@@ -37,6 +42,7 @@ namespace kernel::filesystem::ext2
     {
       return (mode & S_IFMT) == S_IFREG;
     }
+
     auto S_ISDIR(uint16_t mode) -> bool
     {
       return (mode & S_IFMT) == S_IFDIR;
@@ -88,42 +94,29 @@ namespace kernel::filesystem::ext2
     auto const & inode_data = ext2_parent->m_data;
     kstd::vector<uint8_t> buffer(block_size);
 
-    for (size_t i = 0; i < DIRECT_BLOCK_COUNT && inode_data.block[i] != 0; ++i)
+    for (uint32_t i = 0; i < get_inode_block_count(inode_data); ++i)
     {
-      kernel::devices::block_device_utils::read(m_device, buffer.data(), inode_data.block[i] * block_size, block_size);
-
-      size_t offset = 0;
-      while (offset < block_size)
-      {
-        auto * entry = reinterpret_cast<linked_directory_entry const *>(buffer.data() + offset);
-        if (entry->inode == 0)
-          break;
+      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);
 
-        // Stop if the directory entry is malformed to avoid overruns/loops.
-        // if (entry->rec_len < sizeof(linked_directory_entry) || offset + entry->rec_len > block_size)
-        // {
-        //   break;
-        // }
+      auto const * entry = reinterpret_cast<linked_directory_entry const *>(buffer.data());
+      auto bytes_read = 0uz;
 
-        std::string_view entry_name(reinterpret_cast<char const *>(entry->name.data()), entry->name_len);
+      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);
         }
 
-        offset += entry->rec_len;
+        bytes_read += entry->rec_len;
+        entry = reinterpret_cast<linked_directory_entry const *>(buffer.data() + bytes_read);
       }
     }
 
     return nullptr;
-    // TODO BA-FS26 implement ext2 directory traversal and inode loading
-    if (name == "dev")
-    {
-      // TODO BA-FS26 just for testing
-      return nullptr;
-    }
-
-    return kstd::make_shared<inode>();
   }
 
   auto filesystem::read_inode(uint32_t inode_number) -> kstd::shared_ptr<inode>
@@ -164,6 +157,80 @@ namespace kernel::filesystem::ext2
     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 < DIRECT_BLOCK_COUNT)
+    {
+      return data.block.at(inode_block_index);
+    }
+    inode_block_index -= DIRECT_BLOCK_COUNT;
+
+    auto const block_size = get_block_size();
+    auto const numbers_per_block = block_size / sizeof(uint32_t);
+    uint32_t block_number_buffer = 0;
+
+    auto const number_of_singly_indirect_blocks = numbers_per_block;
+    if (inode_block_index < number_of_singly_indirect_blocks)
+    {
+      auto const indirect_block_start_offset = data.block.at(INDIRECT_BLOCK_INDEX) * block_size;
+      auto const direct_block_number_index = inode_block_index;
+      auto const direct_block_number_offset =
+          indirect_block_start_offset + direct_block_number_index * sizeof(uint32_t);
+      kernel::devices::block_device_utils::read(m_device, &block_number_buffer, direct_block_number_offset,
+                                                sizeof(uint32_t));
+      return block_number_buffer;
+    }
+    inode_block_index -= number_of_singly_indirect_blocks;
+
+    auto const number_of_doubly_indirect_blocks = numbers_per_block * numbers_per_block;
+    if (inode_block_index < number_of_doubly_indirect_blocks)
+    {
+      auto const doubly_indirect_block_start_offset = data.block.at(DOUBLY_INDIRECT_BLOCK_INDEX) * block_size;
+      auto const indirect_block_number_index = inode_block_index / numbers_per_block;
+      auto const indirect_block_number_offset =
+          doubly_indirect_block_start_offset + indirect_block_number_index * sizeof(uint32_t);
+      kernel::devices::block_device_utils::read(m_device, &block_number_buffer, indirect_block_number_offset,
+                                                sizeof(uint32_t));
+
+      auto const indirect_block_start_offset = block_number_buffer * block_size;
+      auto const direct_block_number_index = inode_block_index % numbers_per_block;
+      auto const direct_block_number_offset =
+          indirect_block_start_offset + direct_block_number_index * sizeof(uint32_t);
+      kernel::devices::block_device_utils::read(m_device, &block_number_buffer, direct_block_number_offset,
+                                                sizeof(uint32_t));
+      return block_number_buffer;
+    }
+    inode_block_index -= number_of_doubly_indirect_blocks;
+
+    auto const number_of_triply_indirect_blocks = numbers_per_block * numbers_per_block * numbers_per_block;
+    if (inode_block_index < number_of_triply_indirect_blocks)
+    {
+      auto const triply_indirect_block_start_offset = data.block.at(TRIPLY_INDIRECT_BLOCK_INDEX) * block_size;
+      auto const doubly_indirect_block_number_index = inode_block_index / (numbers_per_block * numbers_per_block);
+      auto const doubly_indirect_block_number_offset =
+          triply_indirect_block_start_offset + doubly_indirect_block_number_index * sizeof(uint32_t);
+      kernel::devices::block_device_utils::read(m_device, &block_number_buffer, doubly_indirect_block_number_offset,
+                                                sizeof(uint32_t));
+
+      auto const doubly_indirect_block_start_offset = block_number_buffer * block_size;
+      auto const indirect_block_number_index = (inode_block_index / numbers_per_block) % numbers_per_block;
+      auto const indirect_block_number_offset =
+          doubly_indirect_block_start_offset + indirect_block_number_index * sizeof(uint32_t);
+      kernel::devices::block_device_utils::read(m_device, &block_number_buffer, indirect_block_number_offset,
+                                                sizeof(uint32_t));
+
+      auto const indirect_block_start_offset = block_number_buffer * block_size;
+      auto const direct_block_number_index = inode_block_index % numbers_per_block;
+      auto const direct_block_number_offset =
+          indirect_block_start_offset + direct_block_number_index * sizeof(uint32_t);
+      kernel::devices::block_device_utils::read(m_device, &block_number_buffer, direct_block_number_offset,
+                                                sizeof(uint32_t));
+      return block_number_buffer;
+    }
+
+    return 0;  // TODO BA-FS26 really correct??
+  }
+
   auto filesystem::get_block_size() -> size_t
   {
     return 1024U << m_superblock.log_block_size;
@@ -173,4 +240,9 @@ namespace kernel::filesystem::ext2
   {
     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