kernel/fs: ext2: implement read_directory

7 files changed, 316 insertions, 8 deletions

diff --git a/kernel/kernel/filesystem/ext2/directory_iterator.cpp b/kernel/kernel/filesystem/ext2/directory_iterator.cpp
index cfb520d6..7e2df1e3 100644
--- a/kernel/kernel/filesystem/ext2/directory_iterator.cpp
+++ b/kernel/kernel/filesystem/ext2/directory_iterator.cpp
@@ -9,19 +9,32 @@
 #include <kstd/units.hpp>
 #include <kstd/vector.hpp>
 
+using namespace kstd::literals;
+
 namespace kernel::filesystem::ext2
 {
 
-  directory_iterator::directory_iterator(inode const & inode, filesystem const & filesystem, mount_state & state)
+  directory_iterator::directory_iterator(inode const & inode, mount_state const & state)
+      : directory_iterator{inode, 0_B, state}
+  {}
+
+  directory_iterator::directory_iterator(inode const & inode, kstd::bytes offset, mount_state const & state)
       : m_inode{&inode}
-      , m_filesystem{&filesystem}
       , m_state{&state}
+      , m_file_offset{offset}
       , m_buffer{sizeof(value_type)}
   {
     if (!inode.is_directory())
     {
       kapi::system::panic("[FS:ext2] Tried perform directory iteration on non-directory inode {}", inode.number());
     }
+
+    if (m_file_offset >= data_size(*m_inode, *m_state))
+    {
+      m_inode = nullptr;
+      return;
+    }
+
     read();
   }
 
@@ -53,6 +66,11 @@ namespace kernel::filesystem::ext2
     return copy;
   }
 
+  [[nodiscard]] auto directory_iterator::offset() const noexcept -> kstd::bytes
+  {
+    return m_file_offset;
+  }
+
   auto operator==(directory_iterator const & lhs, directory_iterator const & rhs) -> bool
   {
     if (lhs.m_inode == rhs.m_inode)
diff --git a/kernel/kernel/filesystem/ext2/directory_iterator.hpp b/kernel/kernel/filesystem/ext2/directory_iterator.hpp
index 4e2fd9d8..6729a81c 100644
--- a/kernel/kernel/filesystem/ext2/directory_iterator.hpp
+++ b/kernel/kernel/filesystem/ext2/directory_iterator.hpp
@@ -24,7 +24,10 @@ namespace kernel::filesystem::ext2
     using reference = linked_directory_entry const &;
 
     constexpr directory_iterator() = default;
-    directory_iterator(inode const & inode, filesystem const & filesystem, mount_state & state);
+
+    directory_iterator(inode const & inode, mount_state const & state);
+
+    directory_iterator(inode const & inode, kstd::bytes offset, mount_state const & state);
 
     auto operator*() const -> reference;
 
@@ -34,14 +37,15 @@ namespace kernel::filesystem::ext2
 
     auto operator++(int) -> directory_iterator;
 
+    [[nodiscard]] auto offset() const noexcept -> kstd::bytes;
+
     auto friend operator==(directory_iterator const & lhs, directory_iterator const & rhs) -> bool;
 
   private:
     auto read() -> void;
 
     kstd::observer_ptr<inode const> m_inode{};
-    kstd::observer_ptr<filesystem const> m_filesystem{};
-    kstd::observer_ptr<mount_state> m_state{};
+    kstd::observer_ptr<mount_state const> m_state{};
     kstd::bytes m_file_offset{};
     kstd::vector<std::byte> m_buffer{};
   };
diff --git a/kernel/kernel/filesystem/ext2/directory_iterator.tests.cpp b/kernel/kernel/filesystem/ext2/directory_iterator.tests.cpp
index 2d817e0b..2ef931d1 100644
--- a/kernel/kernel/filesystem/ext2/directory_iterator.tests.cpp
+++ b/kernel/kernel/filesystem/ext2/directory_iterator.tests.cpp
@@ -45,7 +45,7 @@ SCENARIO_METHOD(kernel::tests::filesystem::storage_boot_module_fixture,
       auto names = std::vector<std::string>{};
       auto guard = 0;
 
-      for (auto it = kernel::filesystem::ext2::directory_iterator{root_ext2_inode, *fs, *mount_state};
+      for (auto it = kernel::filesystem::ext2::directory_iterator{root_ext2_inode, *mount_state};
            it != kernel::filesystem::ext2::directory_iterator{}; ++it)
       {
         REQUIRE(guard++ < 64);  // fails loudly on a non-terminating loop rather than hanging the suite
@@ -87,7 +87,7 @@ SCENARIO_METHOD(kernel::tests::filesystem::storage_boot_module_fixture,
 
     auto mount_state = static_pointer_cast<kernel::filesystem::ext2::mount_state>((*mount)->driver_data());
 
-    auto original = kernel::filesystem::ext2::directory_iterator{root_ext2_inode, *fs, *mount_state};
+    auto original = kernel::filesystem::ext2::directory_iterator{root_ext2_inode, *mount_state};
     auto const first_name = std::string{&original->name_start, original->name_len};
 
     WHEN("the iterator is copied, then only the original is advanced")
diff --git a/kernel/kernel/filesystem/ext2/filesystem.cpp b/kernel/kernel/filesystem/ext2/filesystem.cpp
index 10b5cd66..0ddbca79 100644
--- a/kernel/kernel/filesystem/ext2/filesystem.cpp
+++ b/kernel/kernel/filesystem/ext2/filesystem.cpp
@@ -673,7 +673,7 @@ namespace kernel::filesystem::ext2
 
     auto guard = kstd::lock_guard{mount_state->lock};
 
-    for (auto it = directory_iterator{*directory, *this, *mount_state}; it != directory_iterator{}; ++it)
+    for (auto it = directory_iterator{*directory, *mount_state}; it != directory_iterator{}; ++it)
     {
       if (it->inode == 0)
       {
diff --git a/kernel/kernel/filesystem/ext2/inode.cpp b/kernel/kernel/filesystem/ext2/inode.cpp
index aa0c6368..c57ced93 100644
--- a/kernel/kernel/filesystem/ext2/inode.cpp
+++ b/kernel/kernel/filesystem/ext2/inode.cpp
@@ -1,6 +1,9 @@
 #include <kernel/filesystem/ext2/inode.hpp>
 
+#include <kernel/filesystem/directory_listing_cursor.hpp>
+#include <kernel/filesystem/directory_listing_entry.hpp>
 #include <kernel/filesystem/error.hpp>
+#include <kernel/filesystem/ext2/directory_iterator.hpp>
 #include <kernel/filesystem/ext2/error.hpp>
 #include <kernel/filesystem/ext2/filesystem.hpp>
 #include <kernel/filesystem/ext2/mount_state.hpp>
@@ -15,6 +18,7 @@
 #include <kstd/memory.hpp>
 #include <kstd/mutex.hpp>
 #include <kstd/result.hpp>
+#include <kstd/string.hpp>
 #include <kstd/units.hpp>
 
 #include <algorithm>
@@ -22,11 +26,39 @@
 #include <cstdint>
 #include <optional>
 #include <span>
+#include <utility>
 
 using namespace kstd::units_literals;
 
 namespace kernel::filesystem::ext2
 {
+
+  namespace
+  {
+    constexpr auto to_file_type(std::uint8_t entry_type) noexcept -> kapi::filesystem::file_type
+    {
+      switch (entry_type)
+      {
+        case 1:
+          return kapi::filesystem::file_type::regular;
+        case 2:
+          return kapi::filesystem::file_type::directory;
+        case 3:
+          return kapi::filesystem::file_type::character_device;
+        case 4:
+          return kapi::filesystem::file_type::block_device;
+        case 5:
+          return kapi::filesystem::file_type::fifo;
+        case 6:
+          return kapi::filesystem::file_type::socket;
+        case 7:
+          return kapi::filesystem::file_type::symbolic_link;
+        default:
+          return kapi::filesystem::file_type{};
+      }
+    }
+  }  // namespace
+
   inode::inode(uint32_t inode_number, inode_data const & data)
       : m_inode_number(inode_number)
       , m_data(data)
@@ -194,6 +226,47 @@ namespace kernel::filesystem::ext2
     return result;
   }
 
+  auto inode::read_directory(directory_listing_cursor position, std::span<directory_listing_entry> entries) const
+      -> kstd::result<std::pair<std::size_t, directory_listing_cursor>>
+  {
+    if (!is_directory())
+    {
+      return kstd::failure(vfs_errc::not_a_directory);
+    }
+
+    auto state = get_driver_data();
+    if (!state)
+    {
+      return kstd::failure(state.error());
+    }
+
+    auto guard = kstd::lock_guard{(*state)->lock};
+
+    auto count = 0uz;
+    auto it = directory_iterator{*this, kstd::bytes{position.value}, **state};
+
+    for (; it != directory_iterator{} && count < entries.size(); ++it)
+    {
+      if (it->inode == 0)
+      {
+        continue;
+      }
+
+      entries[count++] = directory_listing_entry{
+        .name = kstd::string{it->name()},
+        .type = to_file_type(it->file_type),
+        .inode_number = it->inode,
+      };
+
+      if (count == entries.size())
+      {
+        break;
+      }
+    }
+
+    return std::pair{count, directory_listing_cursor{it.offset().value}};
+  }
+
   auto inode::append_blocks(size_t count, write_batch & batch) -> bool
   {
     auto state = get_driver_data();
diff --git a/kernel/kernel/filesystem/ext2/inode.hpp b/kernel/kernel/filesystem/ext2/inode.hpp
index b506be55..77164e28 100644
--- a/kernel/kernel/filesystem/ext2/inode.hpp
+++ b/kernel/kernel/filesystem/ext2/inode.hpp
@@ -1,6 +1,8 @@
 #ifndef TEACHOS_KERNEL_FILESYSTEM_EXT2_INODE_HPP
 #define TEACHOS_KERNEL_FILESYSTEM_EXT2_INODE_HPP
 
+#include <kernel/filesystem/directory_listing_cursor.hpp>
+#include <kernel/filesystem/directory_listing_entry.hpp>
 #include <kernel/filesystem/ext2/mount_state.hpp>
 #include <kernel/filesystem/ext2/write_batch.hpp>
 #include <kernel/filesystem/inode.hpp>
@@ -16,6 +18,7 @@
 #include <cstdint>
 #include <optional>
 #include <span>
+#include <utility>
 
 namespace kernel::filesystem::ext2
 {
@@ -89,6 +92,10 @@ namespace kernel::filesystem::ext2
 
     [[nodiscard]] auto status() const -> kstd::result<kapi::filesystem::file_status> override;
 
+    [[nodiscard]] auto read_directory(directory_listing_cursor position,
+                                      std::span<directory_listing_entry> entries) const
+        -> kstd::result<std::pair<std::size_t, directory_listing_cursor>> override;
+
     //! @}
 
     //! @name Property Manipulation
diff --git a/kernel/kernel/filesystem/ext2/inode.tests.cpp b/kernel/kernel/filesystem/ext2/inode.tests.cpp
index bf5d9ab7..6b6525bc 100644
--- a/kernel/kernel/filesystem/ext2/inode.tests.cpp
+++ b/kernel/kernel/filesystem/ext2/inode.tests.cpp
@@ -2,8 +2,11 @@
 
 #include <kernel/devices/storage.hpp>
 #include <kernel/filesystem/device_inode.hpp>
+#include <kernel/filesystem/directory_listing_cursor.hpp>
+#include <kernel/filesystem/directory_listing_entry.hpp>
 #include <kernel/filesystem/ext2/block_group_descriptor.hpp>
 #include <kernel/filesystem/ext2/filesystem.hpp>
+#include <kernel/filesystem/ext2/linked_directory_entry.hpp>
 #include <kernel/filesystem/ext2/mount_state.hpp>
 #include <kernel/filesystem/ext2/superblock.hpp>
 #include <kernel/filesystem/filesystem.hpp>
@@ -27,6 +30,7 @@
 #include <cstdint>
 #include <filesystem>
 #include <span>
+#include <string>
 #include <string_view>
 #include <utility>
 #include <vector>
@@ -35,6 +39,26 @@ using namespace kstd::units_literals;
 
 // NOLINTBEGIN(readability-magic-numbers)
 
+namespace
+{
+  auto write_entry(std::vector<std::byte> & block, std::size_t offset, uint32_t inode_number, std::string_view name,
+                   uint8_t file_type, kstd::bytes block_size, bool extend_to_block_end) -> std::size_t
+  {
+    auto const header_and_name = 8uz + name.size();
+    auto const rounded = (header_and_name + 3uz) & ~3uz;
+    auto const rec_len = extend_to_block_end ? static_cast<std::size_t>(block_size.value) - offset : rounded;
+
+    auto * entry = reinterpret_cast<kernel::filesystem::ext2::linked_directory_entry *>(block.data() + offset);
+    entry->inode = inode_number;
+    entry->rec_len = static_cast<uint16_t>(rec_len);
+    entry->name_len = static_cast<uint8_t>(name.size());
+    entry->file_type = file_type;
+    std::copy(name.begin(), name.end(), &entry->name_start);
+
+    return rounded;
+  }
+}  // namespace
+
 SCENARIO("Ext2 inode initialization and properties", "[filesystem][ext2][inode]")
 {
   GIVEN("an ext2 filesystem")
@@ -665,4 +689,186 @@ SCENARIO("Ext2 inode status()", "[filesystem][ext2][inode]")
   }
 }
 
+SCENARIO_METHOD(kernel::tests::filesystem::storage_boot_module_fixture,
+                "Ext2 inode read_directory returns real directory entries", "[filesystem][ext2][inode][img][readdir]")
+{
+  auto const image_path = std::filesystem::path{KERNEL_TEST_ASSETS_DIR} / "ext2_1KB_fs.img";
+
+  GIVEN("a mounted ext2 filesystem and the information directory inode")
+  {
+    REQUIRE(std::filesystem::exists(image_path));
+    REQUIRE_NOTHROW(setup_modules_from_img({"test_img_module"}, {image_path}));
+
+    auto boot_device = kernel::devices::storage::determine_boot_device();
+    REQUIRE(boot_device != nullptr);
+
+    auto dev_inode = kstd::make_shared<kernel::filesystem::device_inode>(boot_device);
+
+    auto fs = kstd::make_shared<kernel::filesystem::ext2::filesystem>();
+    auto mount = kernel::filesystem::mount::create(nullptr, fs, nullptr, nullptr, dev_inode);
+    auto root = (*mount)->root_dentry()->inode();
+    auto driver_data = (*mount)->driver_data();
+    REQUIRE(mount);
+
+    auto information = fs->lookup(root, "information", driver_data);
+    REQUIRE(information);
+    (*information)->set_owning_mount(*mount);
+
+    WHEN("read_directory is called with a buffer large enough for everything in it")
+    {
+      auto entries = kstd::vector<kernel::filesystem::directory_listing_entry>(8);
+      auto result = (*information)->read_directory(kernel::filesystem::directory_listing_cursor{}, entries);
+
+      THEN("known entries come back, correctly typed")
+      {
+        REQUIRE(result);
+        auto [count, next] = *result;
+        REQUIRE(count > 0);
+
+        auto find_by_name = [&](std::string_view name) {
+          return std::ranges::find_if(entries.begin(), entries.begin() + static_cast<std::ptrdiff_t>(count),
+                                      [&](auto const & entry) { return entry.name == name; });
+        };
+
+        auto dot = find_by_name(".");
+        REQUIRE(dot != entries.begin() + static_cast<std::ptrdiff_t>(count));
+        REQUIRE(dot->type == kapi::filesystem::file_type::directory);
+
+        auto info_1 = find_by_name("info_1.txt");
+        REQUIRE(info_1 != entries.begin() + static_cast<std::ptrdiff_t>(count));
+        REQUIRE(info_1->type == kapi::filesystem::file_type::regular);
+
+        AND_THEN("a repeated call with the returned cursor reports exhaustion")
+        {
+          auto second = (*information)->read_directory(next, entries);
+          REQUIRE(second);
+          auto [second_count, second_cursor] = *second;
+          REQUIRE(second_count == 0);
+          REQUIRE(second_cursor == next);
+        }
+      }
+    }
+  }
+}
+
+SCENARIO("Ext2 inode read_directory rejects non-directory inodes", "[filesystem][ext2][inode][readdir]")
+{
+  GIVEN("a regular file inode")
+  {
+    auto data = kernel::filesystem::ext2::inode_data{};
+    data.mode = kernel::filesystem::ext2::constants::mode_regular;
+    auto inode = kernel::filesystem::ext2::inode{7, data};
+
+    THEN("read_directory fails without needing a mount at all")
+    {
+      auto entries = kstd::vector<kernel::filesystem::directory_listing_entry>(1);
+      auto result = inode.read_directory(kernel::filesystem::directory_listing_cursor{}, entries);
+
+      REQUIRE_FALSE(result);
+    }
+  }
+}
+
+SCENARIO("Ext2 inode read_directory skips deleted entries and paginates correctly",
+         "[filesystem][ext2][inode][readdir]")
+{
+  auto const block_size = 1024_B;
+
+  GIVEN("a directory block with four entries, one of them deleted")
+  {
+    auto device = kstd::make_shared<kernel::tests::devices::block_device>("mock", block_size, 64 * block_size);
+    REQUIRE(device != nullptr);
+
+    auto superblock = kernel::filesystem::ext2::superblock{};
+    superblock.magic = kernel::filesystem::ext2::constants::magic_number;
+    superblock.log_block_size = 0;
+    superblock.blocks_count = 64;
+    superblock.blocks_per_group = 64;
+    superblock.inodes_per_group = 32;
+    superblock.inode_size = 128;
+    superblock.rev_level = 1;
+
+    auto block_group_descriptor = kernel::filesystem::ext2::block_group_descriptor{};
+    block_group_descriptor.inode_table = 5;
+    block_group_descriptor.block_bitmap = 10;
+
+    kernel::tests::filesystem::ext2::setup_mock_ext2_layout(*device, superblock, block_group_descriptor);
+
+    auto dev_inode = kstd::make_shared<kernel::filesystem::device_inode>(device);
+    auto fs = kstd::make_shared<kernel::filesystem::ext2::filesystem>();
+    auto mount = kernel::filesystem::mount::create(nullptr, fs, nullptr, nullptr, dev_inode);
+    REQUIRE(mount);
+
+    auto block = std::vector<std::byte>(block_size.value, std::byte{0});
+    auto offset = 0uz;
+    offset +=
+        write_entry(block, offset, 10, "alpha",
+                    static_cast<uint8_t>(kernel::filesystem::ext2::constants::mode_regular >> 8), block_size, false);
+    offset += write_entry(block, offset, 0, "deleted", 0, block_size, false);
+    offset +=
+        write_entry(block, offset, 11, "beta",
+                    static_cast<uint8_t>(kernel::filesystem::ext2::constants::mode_regular >> 8), block_size, false);
+    write_entry(block, offset, 12, "gamma",
+                static_cast<uint8_t>(kernel::filesystem::ext2::constants::mode_regular >> 8), block_size, true);
+
+    kernel::tests::filesystem::ext2::write_bytes(*device, 30 * block_size, block.data(), block_size);
+
+    auto data = kernel::filesystem::ext2::inode_data{};
+    data.mode = kernel::filesystem::ext2::constants::mode_directory;
+    data.size = block_size.value;
+    data.block[0] = 30;
+
+    auto directory = kernel::filesystem::ext2::inode{3, data};
+    directory.set_owning_mount(*mount);
+
+    WHEN("read_directory is called one entry at a time, chaining the returned cursor")
+    {
+      auto seen = std::vector<std::string>{};
+      auto position = kernel::filesystem::directory_listing_cursor{};
+
+      for (auto guard = 0; guard < 8; ++guard)
+      {
+        auto one = kstd::vector<kernel::filesystem::directory_listing_entry>(1);
+        auto result = directory.read_directory(position, one);
+        REQUIRE(result);
+        auto [count, next] = *result;
+        if (count == 0)
+        {
+          break;
+        }
+        seen.push_back(std::string{one[0].name});
+        position = next;
+      }
+
+      THEN("the deleted entry never appears, and every real entry is found exactly once")
+      {
+        REQUIRE(seen.size() == 3);
+        REQUIRE(std::ranges::find(seen, "deleted") == seen.end());
+        REQUIRE(std::ranges::find(seen, "alpha") != seen.end());
+        REQUIRE(std::ranges::find(seen, "beta") != seen.end());
+        REQUIRE(std::ranges::find(seen, "gamma") != seen.end());
+      }
+    }
+
+    WHEN("read_directory is called with a buffer that exactly fits the three real entries")
+    {
+      auto entries = kstd::vector<kernel::filesystem::directory_listing_entry>(3);
+      auto result = directory.read_directory(kernel::filesystem::directory_listing_cursor{}, entries);
+
+      THEN("all three come back, and the very next call reports exhaustion, not a fourth entry")
+      {
+        REQUIRE(result);
+        auto [count, next] = *result;
+        REQUIRE(count == 3);
+
+        auto second = directory.read_directory(next, entries);
+        REQUIRE(second);
+        auto [second_count, second_cursor] = *second;
+        REQUIRE(second_count == 0);
+        REQUIRE(second_cursor == next);
+      }
+    }
+  }
+}
+
 // NOLINTEND(readability-magic-numbers)
\ No newline at end of file