From 7e6137b2725d5cf2b16f55678dcfb99091f03fe9 Mon Sep 17 00:00:00 2001 From: Lukas Oesch Date: Fri, 3 Apr 2026 14:30:20 +0200 Subject: implement map_inode_block_index_to_global_block_number and lookup --- .../include/kernel/filesystem/ext2/filesystem.hpp | 2 + kernel/src/filesystem/ext2/filesystem.cpp | 120 ++++++++++++++++----- 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; + 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 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 +#include #include #include @@ -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 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(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(buffer.data()); + auto bytes_read = 0uz; - std::string_view entry_name(reinterpret_cast(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(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(); } auto filesystem::read_inode(uint32_t inode_number) -> kstd::shared_ptr @@ -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 -- cgit v1.2.3