kernel/fs: devfs: implement read_directory

4 files changed, 268 insertions, 1 deletions

diff --git a/kernel/kernel/filesystem/devfs/inode.cpp b/kernel/kernel/filesystem/devfs/inode.cpp
index 4153d3ac..033972ec 100644
--- a/kernel/kernel/filesystem/devfs/inode.cpp
+++ b/kernel/kernel/filesystem/devfs/inode.cpp
@@ -1,15 +1,35 @@
 #include <kernel/filesystem/devfs/inode.hpp>
 
+#include <kernel/filesystem/device_number_registry.hpp>
+#include <kernel/filesystem/directory_listing_cursor.hpp>
+#include <kernel/filesystem/directory_listing_entry.hpp>
+#include <kernel/filesystem/error.hpp>
+#include <kernel/filesystem/file_type.hpp>
+
+#include <kapi/filesystem.hpp>
+
 #include <kstd/result.hpp>
 #include <kstd/units.hpp>
 
+#include <algorithm>
+#include <bit>
 #include <cstddef>
+#include <cstdint>
+#include <functional>
+#include <iterator>
+#include <ranges>
 #include <span>
+#include <utility>
 
 using namespace kstd::units_literals;
 
 namespace kernel::filesystem::devfs
 {
+  namespace
+  {
+    constexpr auto static sentinel = directory_listing_cursor{0xffff};
+  }
+
   auto inode::read(std::span<std::byte>, kstd::bytes) const -> kstd::result<kstd::bytes>
   {
     return 0_B;
@@ -24,4 +44,65 @@ namespace kernel::filesystem::devfs
   {
     return true;
   }
+
+  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>>
+  {
+    auto requested = entries.size();
+    if (requested == 0)
+    {
+      return kstd::failure(vfs_errc::invalid_argument);
+    }
+
+    auto devices = kernel::filesystem::device_number_registry::get().all();
+    if (devices.empty())
+    {
+      return std::pair{0, position};
+    }
+
+    std::ranges::stable_sort(devices, std::ranges::less{}, &kernel::filesystem::device_number_registry::entry::number);
+
+    auto device_number = std::bit_cast<kapi::filesystem::device_number>(static_cast<std::uint16_t>(position.value));
+    auto begin = std::ranges::lower_bound(devices, device_number, std::ranges::less{},
+                                          &kernel::filesystem::device_number_registry::entry::number);
+    auto end = std::ranges::end(devices);
+    auto to_read = std::min(requested, static_cast<std::size_t>(std::ranges::distance(begin, end)));
+
+    if (to_read == 0)
+    {
+      return std::pair{0, position};
+    }
+
+    std::ranges::transform(begin, begin + to_read, std::ranges::begin(entries), [](auto const & entry) {
+      auto type = [&] {
+        switch (entry.type)
+        {
+          case kernel::filesystem::file_type::block:
+            return kapi::filesystem::file_type::block_device;
+          case kernel::filesystem::file_type::character:
+            return kapi::filesystem::file_type::character_device;
+          case kernel::filesystem::file_type::pipe:
+            return kapi::filesystem::file_type::fifo;
+          case kernel::filesystem::file_type::socket:
+            return kapi::filesystem::file_type::socket;
+          default:
+            return kapi::filesystem::file_type::regular;
+        }
+      }();
+
+      return directory_listing_entry{.name = entry.name,
+                                     .type = type,
+                                     .inode_number = std::bit_cast<std::uint16_t>(entry.number)};
+    });
+
+    auto last_copied = begin + to_read;
+    if (last_copied == end)
+    {
+      return std::pair{to_read, sentinel};
+    }
+
+    auto new_cursor =
+        directory_listing_cursor{static_cast<std::uint64_t>(std::bit_cast<std::uint16_t>(last_copied->number))};
+    return std::pair{to_read, new_cursor};
+  }
 }  // namespace kernel::filesystem::devfs
\ No newline at end of file
diff --git a/kernel/kernel/filesystem/devfs/inode.hpp b/kernel/kernel/filesystem/devfs/inode.hpp
index e907c02e..b83d484c 100644
--- a/kernel/kernel/filesystem/devfs/inode.hpp
+++ b/kernel/kernel/filesystem/devfs/inode.hpp
@@ -1,6 +1,8 @@
 #ifndef TEACHOS_KERNEL_FILESYSTEM_DEVFS_INODE_HPP
 #define TEACHOS_KERNEL_FILESYSTEM_DEVFS_INODE_HPP
 
+#include <kernel/filesystem/directory_listing_cursor.hpp>
+#include <kernel/filesystem/directory_listing_entry.hpp>
 #include <kernel/filesystem/inode.hpp>
 
 #include <kstd/result.hpp>
@@ -8,13 +10,14 @@
 
 #include <cstddef>
 #include <span>
+#include <utility>
 
 namespace kernel::filesystem::devfs
 {
   //! Inode implementation for the devfs filesystem.
   //!
   //! This inode represents root device node in the /dev directory.
-  struct inode : kernel::filesystem::inode
+  struct inode final : kernel::filesystem::inode
   {
     [[nodiscard]] auto read(std::span<std::byte> buffer, kstd::bytes offset) const
         -> kstd::result<kstd::bytes> override;
@@ -22,6 +25,10 @@ namespace kernel::filesystem::devfs
     auto write(std::span<std::byte const> buffer, kstd::bytes offset) -> kstd::result<kstd::bytes> override;
 
     [[nodiscard]] auto is_directory() const -> bool 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;
   };
 }  // namespace kernel::filesystem::devfs
 
diff --git a/kernel/kernel/filesystem/devfs/inode.tests.cpp b/kernel/kernel/filesystem/devfs/inode.tests.cpp
index 0d8ed5d1..581bf6c5 100644
--- a/kernel/kernel/filesystem/devfs/inode.tests.cpp
+++ b/kernel/kernel/filesystem/devfs/inode.tests.cpp
@@ -1,16 +1,42 @@
 #include <kernel/filesystem/devfs/inode.hpp>
 
+#include <kernel/filesystem/device_inode.hpp>
+#include <kernel/filesystem/directory_listing_cursor.hpp>
+#include <kernel/filesystem/directory_listing_entry.hpp>
+#include <kernel/test_support/devices/block_device.hpp>
+#include <kernel/test_support/devices/driver.hpp>
+
+#include <kapi/devices.hpp>
+#include <kapi/filesystem.hpp>
+
 #include <kstd/memory.hpp>
 #include <kstd/print.hpp>
+#include <kstd/string.hpp>
 #include <kstd/units.hpp>
 #include <kstd/vector.hpp>
 
 #include <catch2/catch_test_macros.hpp>
 
+#include <algorithm>
 #include <cstddef>
+#include <tuple>
 
 using namespace kstd::units_literals;
 
+namespace
+{
+  auto make_and_publish(kstd::shared_ptr<kapi::devices::bus> const & bus, kstd::string name)
+      -> kstd::shared_ptr<kapi::devices::device>
+
+  {
+    auto device = kstd::make_shared<kernel::tests::devices::block_device>(name, 512_B);
+    bus->add_child(device);
+    REQUIRE(kernel::tests::devices::bind(*device));
+    REQUIRE(kapi::devices::publish_facet<kapi::filesystem::block_special_file>(device, name));
+    return device;
+  }
+}  // namespace
+
 SCENARIO("Devfs inode creation", "[filesystem][devfs][inode]")
 {
   GIVEN("a devfs inode")
@@ -56,3 +82,154 @@ SCENARIO("Devfs inode read/write", "[filesystem][devfs][inode]")
     }
   }
 }
+
+SCENARIO("Devfs inode directory listing", "[filesystem][devfs][inode]")
+{
+  GIVEN("a devfs inode and no registered devices")
+  {
+    auto root = kernel::filesystem::devfs::inode{};
+
+    THEN("the directory listing is empty")
+    {
+      auto entries = kstd::vector<kernel::filesystem::directory_listing_entry>{4};
+      auto result = root.read_directory(kernel::filesystem::directory_listing_cursor{}, entries);
+
+      REQUIRE(result);
+      auto [count, next] = *result;
+      REQUIRE(count == 0);
+    }
+  }
+
+  GIVEN("a devfs inode and three registered devices")
+  {
+    auto root = kernel::filesystem::devfs::inode{};
+
+    auto bus = kstd::make_shared<kapi::devices::bus>("devfs_readdir_bus");
+    kapi::devices::get_root_bus()->add_child(bus);
+
+    auto device1 = make_and_publish(bus, "devfs_readdir_device1");
+    auto device2 = make_and_publish(bus, "devfs_readdir_device2");
+    auto device3 = make_and_publish(bus, "devfs_readdir_device3");
+
+    WHEN("the directory listing is requested with a buffer large enough for all of them")
+    {
+      auto entries = kstd::vector<kernel::filesystem::directory_listing_entry>{4};
+      auto result = root.read_directory(kernel::filesystem::directory_listing_cursor{}, entries);
+
+      THEN("all devices are listed")
+      {
+        REQUIRE(result);
+        auto [count, next] = *result;
+        REQUIRE(count == 3);
+
+        auto names = kstd::vector<kstd::string>{3};
+        for (auto i = 0uz; i < count; ++i)
+        {
+          REQUIRE(entries[i].type == kapi::filesystem::file_type::block_device);
+          names.push_back(entries[i].name);
+        }
+
+        REQUIRE(std::ranges::find(names, "devfs_readdir_device1") != names.end());
+        REQUIRE(std::ranges::find(names, "devfs_readdir_device2") != names.end());
+        REQUIRE(std::ranges::find(names, "devfs_readdir_device3") != names.end());
+
+        AND_THEN("listing again with the returned cursor reports 'end-of-directory'")
+        {
+          auto result = root.read_directory(next, entries);
+
+          REQUIRE(result);
+          auto [count, cursor] = *result;
+          REQUIRE(count == 0);
+          REQUIRE(cursor == next);
+        }
+      }
+    }
+
+    WHEN("read_directory is called one entry at a time, chaining the returned cursor")
+    {
+      auto seen = kstd::vector<kstd::string>{};
+      auto position = kernel::filesystem::directory_listing_cursor{};
+
+      for (auto guard = 0; guard < 4; ++guard)
+      {
+        auto one = kstd::vector<kernel::filesystem::directory_listing_entry>(1);
+        auto result = root.read_directory(position, one);
+        REQUIRE(result);
+        auto [count, next] = *result;
+        if (count == 0)
+        {
+          break;
+        }
+        seen.push_back(one[0].name);
+        position = next;
+      }
+
+      THEN("nothing is skipped or duplicated across the paginated calls")
+      {
+        REQUIRE(seen.size() == 3);
+        auto sorted = seen;
+        std::ranges::sort(sorted);
+        std::ignore = std::ranges::unique(sorted);
+        REQUIRE(sorted.size() == 3);
+      }
+    }
+
+    REQUIRE(kapi::devices::remove_device(*bus));
+  }
+}
+
+SCENARIO("Devfs inode read_directory orders by device number, not registration order",
+         "[filesystem][devfs][inode][readdir]")
+{
+  GIVEN("a device that frees the lowest minor number before a later device reuses it")
+  {
+    auto root = kernel::filesystem::devfs::inode{};
+
+    auto bus = kstd::make_shared<kapi::devices::bus>("devfs_readdir_reuse_bus");
+    kapi::devices::get_root_bus()->add_child(bus);
+
+    auto first_out = make_and_publish(bus, "readdir_reuse_first_out");
+    auto still_in = make_and_publish(bus, "readdir_reuse_still_in");
+    REQUIRE(kapi::devices::remove_device(*first_out));
+    auto later_in = make_and_publish(bus, "readdir_reuse_later_in");
+
+    WHEN("read_directory is called with room for both remaining entries")
+    {
+      auto entries = kstd::vector<kernel::filesystem::directory_listing_entry>(2);
+      auto result = root.read_directory(kernel::filesystem::directory_listing_cursor{}, entries);
+
+      THEN("later_in (the reused, lower device number) comes back before still_in, by number, not by "
+           "when each was registered")
+      {
+        REQUIRE(result);
+        auto [count, next] = *result;
+        REQUIRE(count == 2);
+        REQUIRE(entries[0].name == "readdir_reuse_later_in");
+        REQUIRE(entries[1].name == "readdir_reuse_still_in");
+      }
+    }
+
+    REQUIRE(kapi::devices::remove_device(*bus));
+  }
+}
+
+SCENARIO("Devfs read_directory rejects non-directory inodes", "[filesystem][devfs][inode][readdir]")
+{
+  GIVEN("a device_inode, which does not represent a directory")
+  {
+    auto bus = kstd::make_shared<kapi::devices::bus>("devfs_readdir_nondir_bus");
+    kapi::devices::get_root_bus()->add_child(bus);
+    auto device = make_and_publish(bus, "readdir_nondir_device");
+    auto node = kernel::filesystem::device_inode{device};
+
+    THEN("read_directory falls through to the base class default rather than enumerating anything")
+    {
+      auto entries = kstd::vector<kernel::filesystem::directory_listing_entry>(1);
+      auto result = node.read_directory(kernel::filesystem::directory_listing_cursor{}, entries);
+
+      REQUIRE_FALSE(result);
+    }
+
+    REQUIRE(kapi::devices::remove_device(*bus));
+  }
+}
\ No newline at end of file
diff --git a/kernel/kernel/test_support/state_reset_listener.cpp b/kernel/kernel/test_support/state_reset_listener.cpp
index 948f2f7e..59f103b7 100644
--- a/kernel/kernel/test_support/state_reset_listener.cpp
+++ b/kernel/kernel/test_support/state_reset_listener.cpp
@@ -1,5 +1,6 @@
 #include <kernel/devices/storage.hpp>
 #include <kernel/drivers/init.hpp>
+#include <kernel/filesystem/device_number_registry.hpp>
 #include <kernel/filesystem/driver_registry.hpp>
 #include <kernel/filesystem/open_file_table.hpp>
 #include <kernel/filesystem/vfs.hpp>
@@ -42,6 +43,7 @@ struct state_reset_listener : Catch::EventListenerBase
 
     std::ignore = kernel::devices::storage::init();
     kernel::filesystem::open_file_table::init();
+    std::ignore = kernel::filesystem::device_number_registry::get();
     kernel::filesystem::driver_registry::init();
   }