From 1eb33a7446a441d053c6ad7b24d3050e770cfff7 Mon Sep 17 00:00:00 2001 From: manuel Date: Sun, 18 Oct 2026 13:17:23 +0000 Subject: kernel/filesystems: add fat32 directory iterator and cluster chain reads --- kernel/CMakeLists.txt | 2 + .../kernel/filesystems/fat32/directory_entry.cpp | 58 ++++++++ .../kernel/filesystems/fat32/directory_entry.hpp | 99 +++++++++++++ .../filesystems/fat32/directory_iterator.cpp | 160 +++++++++++++++++++++ .../filesystems/fat32/directory_iterator.hpp | 111 ++++++++++++++ .../filesystems/fat32/file_allocation_table.cpp | 76 ++++++++++ .../filesystems/fat32/file_allocation_table.hpp | 15 ++ kernel/kernel/filesystems/fat32/filesystem.cpp | 1 + kernel/kernel/filesystems/fat32/inode.cpp | 1 + kernel/kernel/filesystems/fat32/inode.hpp | 5 - kernel/kernel/filesystems/fat32/inode.tests.cpp | 2 + 11 files changed, 525 insertions(+), 5 deletions(-) create mode 100644 kernel/kernel/filesystems/fat32/directory_entry.cpp create mode 100644 kernel/kernel/filesystems/fat32/directory_entry.hpp create mode 100644 kernel/kernel/filesystems/fat32/directory_iterator.cpp create mode 100644 kernel/kernel/filesystems/fat32/directory_iterator.hpp diff --git a/kernel/CMakeLists.txt b/kernel/CMakeLists.txt index 4b2d96da..ca44e79b 100644 --- a/kernel/CMakeLists.txt +++ b/kernel/CMakeLists.txt @@ -86,6 +86,8 @@ target_sources("kernel_lib" PRIVATE "kernel/filesystems/ext2/write_batch.cpp" # fat32 Filesystem + "kernel/filesystems/fat32/directory_entry.cpp" + "kernel/filesystems/fat32/directory_iterator.cpp" "kernel/filesystems/fat32/error.cpp" "kernel/filesystems/fat32/file_allocation_table.cpp" "kernel/filesystems/fat32/filesystem.cpp" diff --git a/kernel/kernel/filesystems/fat32/directory_entry.cpp b/kernel/kernel/filesystems/fat32/directory_entry.cpp new file mode 100644 index 00000000..3b448962 --- /dev/null +++ b/kernel/kernel/filesystems/fat32/directory_entry.cpp @@ -0,0 +1,58 @@ +#include + +#include + +#include +#include + +namespace kernel::filesystems::fat32 +{ + namespace + { + constexpr auto base_name_length = 8uz; + + //! Remove the trailing space padding of a name component. + [[nodiscard]] constexpr auto trim_padding(std::string_view component) -> std::string_view + { + auto const end = component.find_last_not_of(' '); + return end == std::string_view::npos ? std::string_view{} : component.substr(0, end + 1); + } + + //! Append a name component to a string, converting it to lowercase if requested. + auto append_component(kstd::string & target, std::string_view component, bool lowercase) -> void + { + for (auto character : component) + { + if (lowercase && character >= 'A' && character <= 'Z') + { + character = static_cast(character - 'A' + 'a'); + } + target.push_back(character); + } + } + } // namespace + + auto directory_entry::short_name() const -> kstd::string + { + auto const raw_name = std::string_view{name.data(), name.size()}; + auto const base_name = trim_padding(raw_name.substr(0, base_name_length)); + auto const extension = trim_padding(raw_name.substr(base_name_length)); + + auto result = kstd::string{}; + append_component(result, base_name, (nt_reserved & constants::lowercase_base_name) != 0); + + // A leading 0xE5 is a valid character in some code pages and is escaped as 0x05 to not mark the entry as deleted. + if (!result.empty() && static_cast(result[0]) == constants::escaped_deleted_entry_marker) + { + result[0] = static_cast(constants::deleted_entry_marker); + } + + if (!extension.empty()) + { + result.push_back('.'); + append_component(result, extension, (nt_reserved & constants::lowercase_extension) != 0); + } + + return result; + } +} // namespace kernel::filesystems::fat32 diff --git a/kernel/kernel/filesystems/fat32/directory_entry.hpp b/kernel/kernel/filesystems/fat32/directory_entry.hpp new file mode 100644 index 00000000..54b00e57 --- /dev/null +++ b/kernel/kernel/filesystems/fat32/directory_entry.hpp @@ -0,0 +1,99 @@ +#ifndef TEACHOS_KERNEL_FILESYSTEMS_FAT32_DIRECTORY_ENTRY_HPP +#define TEACHOS_KERNEL_FILESYSTEMS_FAT32_DIRECTORY_ENTRY_HPP + +#include +#include + +#include +#include + +namespace kernel::filesystems::fat32 +{ + //! Constants related to fat32 directory entries. + namespace constants + { + constexpr std::uint8_t inline attribute_read_only = 0x01; + constexpr std::uint8_t inline attribute_hidden = 0x02; + constexpr std::uint8_t inline attribute_system = 0x04; + constexpr std::uint8_t inline attribute_volume_id = 0x08; + constexpr std::uint8_t inline attribute_directory = 0x10; + constexpr std::uint8_t inline attribute_archive = 0x20; + constexpr std::uint8_t inline attribute_long_name = + attribute_read_only | attribute_hidden | attribute_system | attribute_volume_id; + + constexpr std::uint8_t inline long_name_mask = 0x3F; + + constexpr std::uint8_t inline end_of_directory_marker = 0x00; + constexpr std::uint8_t inline deleted_entry_marker = 0xE5; + constexpr std::uint8_t inline escaped_deleted_entry_marker = 0x05; + + constexpr std::uint8_t inline lowercase_base_name = 0x08; + constexpr std::uint8_t inline lowercase_extension = 0x10; + + constexpr kstd::bytes inline directory_entry_size = kstd::bytes{32}; + } // namespace constants + + //! A short (8.3) directory entry in the fat32 filesystem. + //! + //! The layout follows the "Microsoft Extensible Firmware Initiative FAT32 File System Specification" (fatgen103). + //! The name is stored as an 8 character base name followed by a 3 character extension, both space padded. + // cspell:ignore fatgen + struct [[gnu::packed]] directory_entry + { + //! Check if this entry marks the end of its directory, i.e. if it and all following entries are unused. + [[nodiscard]] constexpr auto is_end_of_directory() const noexcept -> bool + { + return static_cast(name[0]) == constants::end_of_directory_marker; + } + + //! Check if this entry has been deleted and is free to be reused. + [[nodiscard]] constexpr auto is_deleted() const noexcept -> bool + { + return static_cast(name[0]) == constants::deleted_entry_marker; + } + + //! Check if this entry is part of a long file name. + [[nodiscard]] constexpr auto is_long_name() const noexcept -> bool + { + return (attributes & constants::long_name_mask) == constants::attribute_long_name; + } + + //! Check if this entry holds the label of the volume. + [[nodiscard]] constexpr auto is_volume_label() const noexcept -> bool + { + return !is_long_name() && (attributes & constants::attribute_volume_id) != 0; + } + + //! Get the first cluster of the data described by this entry. + //! + //! @return The first cluster, or 0 if no cluster is allocated (e.g. for empty files). + [[nodiscard]] constexpr auto first_cluster() const noexcept -> std::uint32_t + { + return (static_cast(first_cluster_high) << 16) | first_cluster_low; + } + + //! Get the name of this entry in its displayed form, e.g. "HELLO.TXT". + //! + //! The space padding is removed and the extension, if any, is separated by a dot. The case flags stored in + //! @p nt_reserved are honored. + [[nodiscard]] auto short_name() const -> kstd::string; + + std::array name; // NOLINT(readability-magic-numbers) + std::uint8_t attributes; + std::uint8_t nt_reserved; + std::uint8_t creation_time_tenth; + std::uint16_t creation_time; + std::uint16_t creation_date; + std::uint16_t last_access_date; + std::uint16_t first_cluster_high; + std::uint16_t write_time; + std::uint16_t write_date; + std::uint16_t first_cluster_low; + std::uint32_t file_size; + }; + + static_assert(sizeof(directory_entry) == constants::directory_entry_size.value, + "A fat32 directory entry must be exactly 32 bytes in size."); +} // namespace kernel::filesystems::fat32 + +#endif diff --git a/kernel/kernel/filesystems/fat32/directory_iterator.cpp b/kernel/kernel/filesystems/fat32/directory_iterator.cpp new file mode 100644 index 00000000..a179e7b1 --- /dev/null +++ b/kernel/kernel/filesystems/fat32/directory_iterator.cpp @@ -0,0 +1,160 @@ +#include + +#include +#include +#include +#include + +#include +#include +#include +#include + +#include +#include + +namespace kernel::filesystems::fat32 +{ + directory_iterator::directory_iterator(std::uint32_t first_cluster, driver_state const & state) + : directory_iterator{first_cluster, kstd::bytes{0}, state} + {} + + directory_iterator::directory_iterator(std::uint32_t first_cluster, kstd::bytes offset, driver_state const & state) + : m_state{&state} + , m_cluster{first_cluster} + , m_visited_clusters{1} + , m_offset{offset - offset % constants::directory_entry_size} + { + if (!is_valid_cluster(first_cluster, state)) + { + finish(errc::invalid_cluster); + return; + } + + for (auto clusters_to_skip = m_offset / state.cluster_size; clusters_to_skip > 0; --clusters_to_skip) + { + if (!advance_cluster()) + { + if (!m_error) + { + finish(); + } + return; + } + } + + read(); + } + + auto directory_iterator::operator*() const -> reference + { + return m_record; + } + + auto directory_iterator::operator->() const -> pointer + { + return kstd::observer_ptr{&m_record}; + } + + auto directory_iterator::operator++() -> directory_iterator & + { + if (m_state) + { + read(); + } + return *this; + } + + auto directory_iterator::operator++(int) -> directory_iterator + { + auto copy = *this; + ++(*this); + return copy; + } + + auto directory_iterator::offset() const noexcept -> kstd::bytes + { + return m_offset; + } + + auto directory_iterator::error() const noexcept -> kstd::error_code + { + return m_error; + } + + auto operator==(directory_iterator const & lhs, directory_iterator const & rhs) -> bool + { + if (lhs.m_state == rhs.m_state) + { + return lhs.m_state == nullptr || lhs.m_offset == rhs.m_offset; + } + return false; + } + + auto directory_iterator::read() -> void + { + while (m_cluster) + { + auto const location = cluster_offset(*m_cluster, *m_state) + m_offset % m_state->cluster_size; + + auto entry = directory_entry{}; + if (auto read_result = m_state->backing_inode->read(kstd::raw_bytes(entry), location); !read_result) + { + finish(read_result.error()); + return; + } + + if (entry.is_end_of_directory()) + { + finish(); + return; + } + + auto const entry_offset = m_offset; + m_offset += constants::directory_entry_size; + + // If the chain ends right behind this entry, the entry is still reported and the next increment ends the + // iteration. + if (m_offset % m_state->cluster_size == kstd::bytes{0} && !advance_cluster() && m_error) + { + return; + } + + if (entry.is_deleted() || entry.is_long_name() || entry.is_volume_label()) + { + continue; + } + + m_record = directory_record{.entry = entry, .offset = entry_offset, .location = location}; + return; + } + + finish(); + } + + auto directory_iterator::advance_cluster() -> bool + { + auto const next = next_cluster(*m_cluster, *m_state); + if (!next) + { + finish(next.error()); + return false; + } + + if (*next && ++m_visited_clusters > m_state->cluster_count) + { + finish(errc::corrupted_cluster_chain); + return false; + } + + m_cluster = *next; + return m_cluster.has_value(); + } + + auto directory_iterator::finish(kstd::error_code error) -> void + { + m_state = nullptr; + m_cluster = std::nullopt; + m_error = error; + } +} // namespace kernel::filesystems::fat32 diff --git a/kernel/kernel/filesystems/fat32/directory_iterator.hpp b/kernel/kernel/filesystems/fat32/directory_iterator.hpp new file mode 100644 index 00000000..3ce9b855 --- /dev/null +++ b/kernel/kernel/filesystems/fat32/directory_iterator.hpp @@ -0,0 +1,111 @@ +#ifndef TEACHOS_KERNEL_FILESYSTEMS_FAT32_DIRECTORY_ITERATOR_HPP +#define TEACHOS_KERNEL_FILESYSTEMS_FAT32_DIRECTORY_ITERATOR_HPP + +#include +#include + +#include +#include +#include + +#include +#include +#include +#include + +namespace kernel::filesystems::fat32 +{ + namespace constants + { + //! The inode number of the root directory. + //! + //! The root directory is not described by a directory entry. Entry locations are multiples of the entry size and + //! lie behind the boot sector, so they can never collide with this number. + constexpr std::uint64_t inline root_inode_number = 1; + } // namespace constants + + //! A directory entry together with the position it was read from. + struct directory_record + { + //! Get the inode number of the file described by this record. + //! + //! FAT has no inode numbers, so the location of the entry on the backing inode is used, which is unique and + //! stable for the lifetime of the entry. + [[nodiscard]] constexpr auto inode_number() const noexcept -> std::uint64_t + { + return location.value; + } + + //! The entry as stored on disk. + directory_entry entry{}; + //! The offset of the entry within the data of its directory. + kstd::bytes offset{}; + //! The offset of the entry on the backing inode. + kstd::bytes location{}; + }; + + //! An iterator over the entries of a directory. + //! + //! Deleted entries, long file name entries and the volume label are skipped. Iteration ends at the end of directory + //! marker or at the end of the directory's cluster chain. If reading the directory fails, the iterator becomes equal + //! to the end iterator and the failure is reported by @p error(). + struct directory_iterator + { + using iterator_category = std::forward_iterator_tag; + using iterator_concept = std::forward_iterator_tag; + using value_type = directory_record; + using pointer = kstd::observer_ptr; + using reference = directory_record const &; + using difference_type = std::ptrdiff_t; + + constexpr directory_iterator() = default; + + //! Create an iterator positioned at the first entry of a directory. + //! + //! @param first_cluster The first cluster of the directory's data. + //! @param state The driver state to operate on. + directory_iterator(std::uint32_t first_cluster, driver_state const & state); + + //! Create an iterator positioned at the first entry at or behind a given offset. + //! + //! @param first_cluster The first cluster of the directory's data. + //! @param offset The offset within the directory's data to start at, rounded down to an entry boundary. + //! @param state The driver state to operate on. + directory_iterator(std::uint32_t first_cluster, kstd::bytes offset, driver_state const & state); + + auto operator*() const -> reference; + + auto operator->() const -> pointer; + + auto operator++() -> directory_iterator &; + + auto operator++(int) -> directory_iterator; + + //! Get the offset directly behind the current entry, suitable to resume iteration after it. + [[nodiscard]] auto offset() const noexcept -> kstd::bytes; + + //! Get the error that ended the iteration, if any. + [[nodiscard]] auto error() const noexcept -> kstd::error_code; + + auto friend operator==(directory_iterator const & lhs, directory_iterator const & rhs) -> bool; + + private: + //! Read entries until a visible one, the end of the directory or an error is found. + auto read() -> void; + + //! Move to the next cluster of the directory's chain. + auto advance_cluster() -> bool; + + //! End the iteration, optionally recording the error that caused it. + auto finish(kstd::error_code error = {}) -> void; + + kstd::observer_ptr m_state{}; + std::optional m_cluster{}; + std::size_t m_visited_clusters{}; + kstd::bytes m_offset{}; + directory_record m_record{}; + kstd::error_code m_error{}; + }; +} // namespace kernel::filesystems::fat32 + +#endif diff --git a/kernel/kernel/filesystems/fat32/file_allocation_table.cpp b/kernel/kernel/filesystems/fat32/file_allocation_table.cpp index 02410ac8..3e9b0b4a 100644 --- a/kernel/kernel/filesystems/fat32/file_allocation_table.cpp +++ b/kernel/kernel/filesystems/fat32/file_allocation_table.cpp @@ -8,8 +8,13 @@ #include #include +#include +#include #include #include +#include + +using namespace kstd::units_literals; namespace kernel::filesystems::fat32 { @@ -110,4 +115,75 @@ namespace kernel::filesystems::fat32 return chain; } + + auto read_cluster_chain(std::uint32_t first_cluster, std::span buffer, kstd::bytes offset, + driver_state const & state) -> kstd::result + { + if (!is_valid_cluster(first_cluster, state)) + { + return kstd::failure(errc::invalid_cluster); + } + + auto current = std::optional{first_cluster}; + auto visited_clusters = std::size_t{1}; + + auto const advance = [&] -> kstd::result { + auto const next = next_cluster(*current, state); + if (!next) + { + return kstd::failure(next.error()); + } + + if (*next && ++visited_clusters > state.cluster_count) + { + return kstd::failure(errc::corrupted_cluster_chain); + } + + current = *next; + return {}; + }; + + for (auto clusters_to_skip = offset / state.cluster_size; current && clusters_to_skip > 0; --clusters_to_skip) + { + if (auto advance_result = advance(); !advance_result) + { + return kstd::failure(advance_result.error()); + } + } + + auto const requested_size = kstd::bytes{buffer.size()}; + auto in_cluster_offset = offset % state.cluster_size; + auto bytes_read = 0_B; + + while (current && bytes_read < requested_size) + { + auto const bytes_to_read = std::min(requested_size - bytes_read, state.cluster_size - in_cluster_offset); + auto const read_offset = cluster_offset(*current, state) + in_cluster_offset; + + auto const read_result = + state.backing_inode->read(buffer.subspan(bytes_read.value, bytes_to_read.value), read_offset); + if (!read_result) + { + return kstd::failure(read_result.error()); + } + + bytes_read += *read_result; + in_cluster_offset = 0_B; + + if (*read_result < bytes_to_read) + { + break; + } + + if (bytes_read < requested_size) + { + if (auto advance_result = advance(); !advance_result) + { + return kstd::failure(advance_result.error()); + } + } + } + + return bytes_read; + } } // namespace kernel::filesystems::fat32 diff --git a/kernel/kernel/filesystems/fat32/file_allocation_table.hpp b/kernel/kernel/filesystems/fat32/file_allocation_table.hpp index df5c723d..9601db1b 100644 --- a/kernel/kernel/filesystems/fat32/file_allocation_table.hpp +++ b/kernel/kernel/filesystems/fat32/file_allocation_table.hpp @@ -7,8 +7,10 @@ #include #include +#include #include #include +#include namespace kernel::filesystems::fat32 { @@ -74,6 +76,19 @@ namespace kernel::filesystems::fat32 //! @return The clusters of the chain in order on success, an error otherwise. [[nodiscard]] auto cluster_chain(std::uint32_t first_cluster, driver_state const & state) -> kstd::result>; + + //! Read the data stored in the cluster chain starting at a given cluster. + //! + //! Reading stops when either the buffer is full or the end of the chain is reached. The chain itself carries no size + //! information, so callers reading a file must limit the buffer to the file size themselves. + //! + //! @param first_cluster The first cluster of the chain. + //! @param buffer The buffer to read into. + //! @param offset The offset inside the chain's data to start at. + //! @param state The driver state to operate on. + //! @return The number of bytes read on success, an error otherwise. + [[nodiscard]] auto read_cluster_chain(std::uint32_t first_cluster, std::span buffer, kstd::bytes offset, + driver_state const & state) -> kstd::result; } // namespace kernel::filesystems::fat32 #endif diff --git a/kernel/kernel/filesystems/fat32/filesystem.cpp b/kernel/kernel/filesystems/fat32/filesystem.cpp index 743968fa..c33fd676 100644 --- a/kernel/kernel/filesystems/fat32/filesystem.cpp +++ b/kernel/kernel/filesystems/fat32/filesystem.cpp @@ -1,6 +1,7 @@ #include #include +#include #include #include #include diff --git a/kernel/kernel/filesystems/fat32/inode.cpp b/kernel/kernel/filesystems/fat32/inode.cpp index 20e9ae48..f6b75b69 100644 --- a/kernel/kernel/filesystems/fat32/inode.cpp +++ b/kernel/kernel/filesystems/fat32/inode.cpp @@ -1,5 +1,6 @@ #include +#include #include #include diff --git a/kernel/kernel/filesystems/fat32/inode.hpp b/kernel/kernel/filesystems/fat32/inode.hpp index 87485ffb..d14f4ec9 100644 --- a/kernel/kernel/filesystems/fat32/inode.hpp +++ b/kernel/kernel/filesystems/fat32/inode.hpp @@ -18,11 +18,6 @@ namespace kernel::filesystems::fat32 { - namespace constants - { - constexpr std::uint8_t inline attribute_directory = 0x10; - } // namespace constants - struct inode : kernel::vfs::inode { //! Create a fat32 inode. diff --git a/kernel/kernel/filesystems/fat32/inode.tests.cpp b/kernel/kernel/filesystems/fat32/inode.tests.cpp index 62c50ae9..030ee0ac 100644 --- a/kernel/kernel/filesystems/fat32/inode.tests.cpp +++ b/kernel/kernel/filesystems/fat32/inode.tests.cpp @@ -1,5 +1,7 @@ #include +#include + #include #include #include -- cgit v1.2.3