diff options
| -rw-r--r-- | kernel/CMakeLists.txt | 2 | ||||
| -rw-r--r-- | kernel/kernel/filesystems/fat32/directory_entry.cpp | 58 | ||||
| -rw-r--r-- | kernel/kernel/filesystems/fat32/directory_entry.hpp | 99 | ||||
| -rw-r--r-- | kernel/kernel/filesystems/fat32/directory_iterator.cpp | 160 | ||||
| -rw-r--r-- | kernel/kernel/filesystems/fat32/directory_iterator.hpp | 111 | ||||
| -rw-r--r-- | kernel/kernel/filesystems/fat32/directory_iterator.tests.cpp | 354 | ||||
| -rw-r--r-- | kernel/kernel/filesystems/fat32/file_allocation_table.cpp | 76 | ||||
| -rw-r--r-- | kernel/kernel/filesystems/fat32/file_allocation_table.hpp | 15 | ||||
| -rw-r--r-- | kernel/kernel/filesystems/fat32/file_allocation_table.tests.cpp | 160 | ||||
| -rw-r--r-- | kernel/kernel/filesystems/fat32/filesystem.cpp | 1 | ||||
| -rw-r--r-- | kernel/kernel/filesystems/fat32/inode.cpp | 1 | ||||
| -rw-r--r-- | kernel/kernel/filesystems/fat32/inode.hpp | 5 | ||||
| -rw-r--r-- | kernel/kernel/filesystems/fat32/inode.tests.cpp | 2 | ||||
| -rw-r--r-- | kernel/kernel/test_support/filesystems/fat32.cpp | 10 | ||||
| -rw-r--r-- | kernel/kernel/test_support/filesystems/fat32.hpp | 4 |
15 files changed, 1053 insertions, 5 deletions
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 <kernel/filesystems/fat32/directory_entry.hpp> + +#include <kstd/string.hpp> + +#include <cstdint> +#include <string_view> + +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<char>(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<std::uint8_t>(result[0]) == constants::escaped_deleted_entry_marker) + { + result[0] = static_cast<char>(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 <kstd/string.hpp> +#include <kstd/units.hpp> + +#include <array> +#include <cstdint> + +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<std::uint8_t>(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<std::uint8_t>(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<std::uint32_t>(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<char, 11> 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 <kernel/filesystems/fat32/directory_iterator.hpp> + +#include <kernel/filesystems/fat32/directory_entry.hpp> +#include <kernel/filesystems/fat32/driver_state.hpp> +#include <kernel/filesystems/fat32/error.hpp> +#include <kernel/filesystems/fat32/file_allocation_table.hpp> + +#include <kstd/memory.hpp> +#include <kstd/span.hpp> +#include <kstd/system_error.hpp> +#include <kstd/units.hpp> + +#include <cstdint> +#include <optional> + +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 <kernel/filesystems/fat32/directory_entry.hpp> +#include <kernel/filesystems/fat32/driver_state.hpp> + +#include <kstd/memory.hpp> +#include <kstd/system_error.hpp> +#include <kstd/units.hpp> + +#include <cstddef> +#include <cstdint> +#include <iterator> +#include <optional> + +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<directory_record const>; + 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<driver_state const> m_state{}; + std::optional<std::uint32_t> 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/directory_iterator.tests.cpp b/kernel/kernel/filesystems/fat32/directory_iterator.tests.cpp new file mode 100644 index 00000000..204c5a40 --- /dev/null +++ b/kernel/kernel/filesystems/fat32/directory_iterator.tests.cpp @@ -0,0 +1,354 @@ +#include <kernel/filesystems/fat32/directory_iterator.hpp> + +#include <kernel/devices/storage.hpp> +#include <kernel/filesystems/fat32/directory_entry.hpp> +#include <kernel/filesystems/fat32/driver_state.hpp> +#include <kernel/filesystems/fat32/error.hpp> +#include <kernel/filesystems/fat32/file_allocation_table.hpp> +#include <kernel/filesystems/fat32/filesystem.hpp> +#include <kernel/test_support/devices/block_device.hpp> +#include <kernel/test_support/filesystems/fat32.hpp> +#include <kernel/test_support/vfs/storage_boot_module_fixture.hpp> +#include <kernel/vfs/device_inode.hpp> + +#include <kstd/memory.hpp> +#include <kstd/units.hpp> + +#include <catch2/catch_test_macros.hpp> + +#include <algorithm> +#include <array> +#include <cstddef> +#include <cstdint> +#include <filesystem> +#include <span> +#include <string> +#include <string_view> +#include <vector> + +using namespace kstd::units_literals; + +// NOLINTBEGIN(readability-magic-numbers) + +namespace +{ + using kernel::filesystems::fat32::directory_entry; + using kernel::filesystems::fat32::directory_iterator; + + constexpr auto entries_per_cluster = 16uz; + + auto make_entry(std::string_view name, std::uint8_t attributes, std::uint32_t first_cluster = 0, + std::uint32_t file_size = 0) -> directory_entry + { + auto entry = directory_entry{}; + std::ranges::fill(entry.name, ' '); + std::ranges::copy(name.substr(0, entry.name.size()), entry.name.begin()); + entry.attributes = attributes; + entry.first_cluster_high = static_cast<std::uint16_t>(first_cluster >> 16); + entry.first_cluster_low = static_cast<std::uint16_t>(first_cluster & 0xFFFF); + entry.file_size = file_size; + return entry; + } + + auto file_entry(std::string_view name) -> directory_entry + { + return make_entry(name, kernel::filesystems::fat32::constants::attribute_archive); + } + + auto write_entries(kernel::tests::devices::block_device & device, std::uint32_t cluster, + std::span<directory_entry const> entries) -> void + { + auto cluster_entries = std::array<directory_entry, entries_per_cluster>{}; + std::ranges::copy(entries, cluster_entries.begin()); + kernel::tests::filesystems::fat32::write_cluster_data(device, cluster, std::as_bytes(std::span{cluster_entries})); + } + + auto collect_names(directory_iterator it) -> std::vector<std::string> + { + auto names = std::vector<std::string>{}; + for (; it != directory_iterator{}; ++it) + { + REQUIRE(names.size() < 64); // fails loudly on a non-terminating loop rather than hanging the suite + auto const name = it->entry.short_name(); + names.emplace_back(name.data(), name.size()); + } + return names; + } +} // namespace + +SCENARIO("Fat32 short names are formatted for display", "[filesystem][fat32][readdir]") +{ + using namespace kernel::filesystems::fat32; + + THEN("padding is removed and the extension is separated by a dot") + { + REQUIRE(make_entry("HELLO TXT", 0).short_name() == "HELLO.TXT"); + REQUIRE(make_entry("ABCDEFGHIJK", 0).short_name() == "ABCDEFGH.IJK"); + } + + THEN("a name without extension has no dot") + { + REQUIRE(make_entry("README", 0).short_name() == "README"); + } + + THEN("the dot entries keep their names") + { + REQUIRE(make_entry(".", constants::attribute_directory).short_name() == "."); + REQUIRE(make_entry("..", constants::attribute_directory).short_name() == ".."); + } + + THEN("the lowercase flags are honored per component") + { + auto entry = make_entry("HELLO TXT", 0); + + entry.nt_reserved = constants::lowercase_base_name; + REQUIRE(entry.short_name() == "hello.TXT"); + + entry.nt_reserved = constants::lowercase_extension; + REQUIRE(entry.short_name() == "HELLO.txt"); + + entry.nt_reserved = constants::lowercase_base_name | constants::lowercase_extension; + REQUIRE(entry.short_name() == "hello.txt"); + } + + THEN("an escaped leading 0xE5 is restored") + { + auto entry = make_entry("XAB", 0); + entry.name[0] = static_cast<char>(constants::escaped_deleted_entry_marker); + auto const name = entry.short_name(); + REQUIRE(static_cast<std::uint8_t>(name[0]) == constants::deleted_entry_marker); + REQUIRE(std::string_view{name.data() + 1, name.size() - 1} == "AB"); + } + + THEN("the first cluster combines both halves") + { + REQUIRE(make_entry("A", 0, 0x0012'3456).first_cluster() == 0x0012'3456); + } +} + +SCENARIO_METHOD(kernel::tests::vfs::storage_boot_module_fixture, "Fat32 directory_iterator walks a real directory", + "[filesystem][fat32][readdir][img]") +{ + auto const image_path = std::filesystem::path{KERNEL_TEST_ASSETS_DIR} / "fat32.img"; + + GIVEN("a mounted fat32 filesystem from a real image") + { + 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); + + auto dev_inode = kstd::make_shared<kernel::vfs::device_inode>(boot_device); + auto fs = kstd::make_shared<kernel::filesystems::fat32::filesystem>(); + auto mount = fs->mount(dev_inode); + REQUIRE(mount); + auto driver_state = static_pointer_cast<kernel::filesystems::fat32::driver_state>(mount->second); + REQUIRE(driver_state); + + auto const root_cluster = driver_state->boot_sector.root_cluster; + + THEN("the volume label is skipped and only HELLO.TXT is found") + { + REQUIRE(collect_names(directory_iterator{root_cluster, *driver_state}) == std::vector<std::string>{"HELLO.TXT"}); + } + + THEN("the record describes HELLO.TXT and where it is stored") + { + auto it = directory_iterator{root_cluster, *driver_state}; + REQUIRE(it != directory_iterator{}); + REQUIRE(it->entry.first_cluster() == 3); + REQUIRE(it->entry.file_size == 12); + REQUIRE(it->offset == 32_B); + REQUIRE(it->location == kernel::filesystems::fat32::cluster_offset(root_cluster, *driver_state) + 32_B); + REQUIRE(it->inode_number() == it->location.value); + REQUIRE(it.offset() == 64_B); + + ++it; + REQUIRE(it == directory_iterator{}); + REQUIRE_FALSE(it.error()); + } + } +} + +SCENARIO("Fat32 directory_iterator on a mock layout", "[filesystem][fat32][readdir]") +{ + auto const block_size = 512_B; + + GIVEN("a mounted minimal fat32 layout") + { + auto device = kstd::make_shared<kernel::tests::devices::block_device>("mock", block_size, 18 * block_size); + kernel::tests::filesystems::fat32::setup_mock_fat32_layout(*device); + + auto dev_inode = kstd::make_shared<kernel::vfs::device_inode>(device); + auto fs = kstd::make_shared<kernel::filesystems::fat32::filesystem>(); + auto mount = fs->mount(dev_inode); + REQUIRE(mount); + auto driver_state = static_pointer_cast<kernel::filesystems::fat32::driver_state>(mount->second); + REQUIRE(driver_state); + + using namespace kernel::filesystems::fat32; + using kernel::tests::filesystems::fat32::write_fat_entry; + + WHEN("the directory contains deleted, long name and volume label entries") + { + auto deleted = file_entry("GONE TXT"); + deleted.name[0] = static_cast<char>(constants::deleted_entry_marker); + + auto const entries = std::array{ + make_entry("LABEL", constants::attribute_volume_id), + make_entry("Ah\0e\0l\0l\0o", constants::attribute_long_name), + file_entry("HELLO TXT"), + deleted, + make_entry("SUBDIR", constants::attribute_directory, 5), + directory_entry{}, + file_entry("HIDDEN TXT"), + }; + write_entries(*device, 2, entries); + + THEN("only the regular entries before the end marker are visited") + { + REQUIRE(collect_names(directory_iterator{2, *driver_state}) == + std::vector<std::string>{"HELLO.TXT", "SUBDIR"}); + } + + THEN("the records carry the offsets of the visited entries") + { + auto it = directory_iterator{2, *driver_state}; + REQUIRE(it->offset == 64_B); + REQUIRE(it->location == 1024_B + 64_B); + ++it; + REQUIRE(it->offset == 128_B); + REQUIRE(it->entry.first_cluster() == 5); + } + + THEN("iteration can be resumed behind a visited entry") + { + auto it = directory_iterator{2, *driver_state}; + REQUIRE(collect_names(directory_iterator{2, it.offset(), *driver_state}) == + std::vector<std::string>{"SUBDIR"}); + } + + THEN("an offset inside an entry is rounded down to its start") + { + REQUIRE(directory_iterator{2, 70_B, *driver_state}->offset == 64_B); + } + + THEN("copies of an iterator advance independently") + { + auto first = directory_iterator{2, *driver_state}; + auto second = first; + ++first; + REQUIRE(second->entry.short_name() == "HELLO.TXT"); + REQUIRE(first->entry.short_name() == "SUBDIR"); + REQUIRE(first != second); + ++second; + REQUIRE(first == second); + } + } + + WHEN("the directory spans two clusters") + { + auto first_cluster_entries = std::array<directory_entry, entries_per_cluster>{}; + for (auto i = 0uz; i < first_cluster_entries.size(); ++i) + { + first_cluster_entries[i] = file_entry(std::string{"FILE"} + static_cast<char>('A' + i)); + } + write_entries(*device, 3, first_cluster_entries); + write_entries(*device, 4, std::array{file_entry("LAST TXT")}); + write_fat_entry(*device, 3, 4); + write_fat_entry(*device, 4, 0x0FFF'FFFF); + + THEN("the entries of both clusters are visited in order") + { + auto const names = collect_names(directory_iterator{3, *driver_state}); + REQUIRE(names.size() == 17); + REQUIRE(names.front() == "FILEA"); + REQUIRE(names.back() == "LAST.TXT"); + } + + THEN("the entries of the second cluster are located in it") + { + auto it = directory_iterator{3, 512_B, *driver_state}; + REQUIRE(it->offset == 512_B); + REQUIRE(it->location == cluster_offset(4, *driver_state)); + REQUIRE(it->entry.short_name() == "LAST.TXT"); + } + + THEN("an offset behind the chain yields no entries and no error") + { + auto it = directory_iterator{3, 1024_B, *driver_state}; + REQUIRE(it == directory_iterator{}); + REQUIRE_FALSE(it.error()); + } + } + + WHEN("a full directory has no end marker") + { + auto entries = std::array<directory_entry, entries_per_cluster>{}; + std::ranges::fill(entries, file_entry("FILE")); + write_entries(*device, 6, entries); + write_fat_entry(*device, 6, 0x0FFF'FFFF); + + THEN("iteration ends with the chain") + { + auto it = directory_iterator{6, *driver_state}; + REQUIRE(collect_names(it).size() == entries_per_cluster); + std::ranges::advance(it, entries_per_cluster); + REQUIRE(it == directory_iterator{}); + REQUIRE_FALSE(it.error()); + } + } + + THEN("a directory cannot start outside the data region") + { + auto it = directory_iterator{0, *driver_state}; + REQUIRE(it == directory_iterator{}); + REQUIRE(it.error() == errc::invalid_cluster); + } + + WHEN("the directory's chain is cyclic") + { + auto entries = std::array<directory_entry, entries_per_cluster>{}; + std::ranges::fill(entries, file_entry("LOOP")); + write_entries(*device, 13, entries); + write_entries(*device, 14, entries); + write_fat_entry(*device, 13, 14); + write_fat_entry(*device, 14, 13); + + THEN("iteration ends with a corrupted chain error") + { + auto it = directory_iterator{13, *driver_state}; + auto count = 0uz; + for (; it != directory_iterator{} && count < 1000; ++it) + { + ++count; + } + REQUIRE(count < 1000); + REQUIRE(it.error() == errc::corrupted_cluster_chain); + } + } + + WHEN("the directory's chain runs into a free cluster") + { + auto entries = std::array<directory_entry, entries_per_cluster>{}; + std::ranges::fill(entries, file_entry("FILE")); + write_entries(*device, 8, entries); + write_entries(*device, 9, entries); + write_fat_entry(*device, 8, 9); + write_fat_entry(*device, 9, 0); + + THEN("iteration ends with a corrupted chain error once the free cluster is followed") + { + auto it = directory_iterator{8, *driver_state}; + while (it != directory_iterator{}) + { + ++it; + } + REQUIRE(it.error() == errc::corrupted_cluster_chain); + } + } + } +} + +// NOLINTEND(readability-magic-numbers) 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 <kstd/units.hpp> #include <kstd/vector.hpp> +#include <algorithm> +#include <cstddef> #include <cstdint> #include <optional> +#include <span> + +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<std::byte> buffer, kstd::bytes offset, + driver_state const & state) -> kstd::result<kstd::bytes> + { + 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<void> { + 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 <kstd/units.hpp> #include <kstd/vector.hpp> +#include <cstddef> #include <cstdint> #include <optional> +#include <span> 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<kstd::vector<std::uint32_t>>; + + //! 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<std::byte> buffer, kstd::bytes offset, + driver_state const & state) -> kstd::result<kstd::bytes>; } // namespace kernel::filesystems::fat32 #endif diff --git a/kernel/kernel/filesystems/fat32/file_allocation_table.tests.cpp b/kernel/kernel/filesystems/fat32/file_allocation_table.tests.cpp index bcc85a51..1b79d2bf 100644 --- a/kernel/kernel/filesystems/fat32/file_allocation_table.tests.cpp +++ b/kernel/kernel/filesystems/fat32/file_allocation_table.tests.cpp @@ -1,6 +1,7 @@ #include <kernel/filesystems/fat32/file_allocation_table.hpp> #include <kernel/devices/storage.hpp> +#include <kernel/filesystems/fat32/directory_entry.hpp> #include <kernel/filesystems/fat32/driver_state.hpp> #include <kernel/filesystems/fat32/error.hpp> #include <kernel/filesystems/fat32/filesystem.hpp> @@ -10,14 +11,20 @@ #include <kernel/vfs/device_inode.hpp> #include <kstd/memory.hpp> +#include <kstd/span.hpp> #include <kstd/units.hpp> #include <kstd/vector.hpp> #include <catch2/catch_test_macros.hpp> +#include <algorithm> +#include <array> +#include <cstddef> #include <cstdint> #include <filesystem> #include <optional> +#include <span> +#include <string_view> using namespace kstd::units_literals; @@ -70,6 +77,40 @@ SCENARIO_METHOD(kernel::tests::vfs::storage_boot_module_fixture, "Fat32 cluster REQUIRE(kernel::filesystems::fat32::next_cluster(100, *driver_state).error() == kernel::filesystems::fat32::errc::corrupted_cluster_chain); } + + THEN("the root directory entries can be read from its cluster chain") + { + using namespace kernel::filesystems::fat32; + + auto entries = std::array<directory_entry, 3>{}; + auto const buffer = std::as_writable_bytes(std::span{entries}); + auto const read_result = read_cluster_chain(driver_state->boot_sector.root_cluster, buffer, 0_B, *driver_state); + REQUIRE(read_result); + REQUIRE(*read_result == kstd::bytes{buffer.size()}); + + auto const & volume_label = entries[0]; + REQUIRE(std::string_view{volume_label.name.data(), volume_label.name.size()} == "TESTFAT "); + REQUIRE(volume_label.attributes == constants::attribute_volume_id); + + auto const & hello = entries[1]; + REQUIRE(std::string_view{hello.name.data(), hello.name.size()} == "HELLO TXT"); + REQUIRE(hello.attributes == constants::attribute_archive); + REQUIRE(hello.first_cluster_high == 0); + REQUIRE(hello.first_cluster_low == 3); + REQUIRE(hello.file_size == 12); + + REQUIRE(static_cast<std::uint8_t>(entries[2].name[0]) == constants::end_of_directory_marker); + } + + THEN("the contents of HELLO.TXT can be read from its cluster chain") + { + auto contents = std::array<char, 12>{}; + auto const read_result = kernel::filesystems::fat32::read_cluster_chain( + 3, std::as_writable_bytes(std::span{contents}), 0_B, *driver_state); + REQUIRE(read_result); + REQUIRE(*read_result == 12_B); + REQUIRE(std::string_view{contents.data(), contents.size()} == "Hello World!"); + } } } @@ -199,4 +240,123 @@ SCENARIO("Fat32 cluster chain traversal", "[filesystem][fat32][fat]") } } +SCENARIO("Fat32 cluster chain reading", "[filesystem][fat32][fat]") +{ + auto const block_size = 512_B; + + GIVEN("a mounted minimal fat32 layout with a three cluster chain") + { + auto device = kstd::make_shared<kernel::tests::devices::block_device>("mock", block_size, 18 * block_size); + kernel::tests::filesystems::fat32::setup_mock_fat32_layout(*device); + + using kernel::filesystems::fat32::errc; + using kernel::filesystems::fat32::read_cluster_chain; + using kernel::tests::filesystems::fat32::write_cluster_data; + using kernel::tests::filesystems::fat32::write_fat_entry; + + auto cluster_data = std::array<std::byte, 512>{}; + for (auto const & [cluster, fill] : {std::pair{3u, 'A'}, std::pair{4u, 'B'}, std::pair{5u, 'C'}}) + { + std::ranges::fill(cluster_data, static_cast<std::byte>(fill)); + write_cluster_data(*device, cluster, cluster_data); + } + + write_fat_entry(*device, 3, 4); + write_fat_entry(*device, 4, 5); + write_fat_entry(*device, 5, 0x0FFF'FFF8); + + auto dev_inode = kstd::make_shared<kernel::vfs::device_inode>(device); + auto fs = kstd::make_shared<kernel::filesystems::fat32::filesystem>(); + auto mount = fs->mount(dev_inode); + REQUIRE(mount); + auto driver_state = static_pointer_cast<kernel::filesystems::fat32::driver_state>(mount->second); + REQUIRE(driver_state); + + THEN("the whole chain is read in order") + { + auto buffer = std::array<std::byte, 3 * 512>{}; + auto const read_result = read_cluster_chain(3, buffer, 0_B, *driver_state); + REQUIRE(read_result); + REQUIRE(*read_result == 1536_B); + REQUIRE(buffer[0] == std::byte{'A'}); + REQUIRE(buffer[511] == std::byte{'A'}); + REQUIRE(buffer[512] == std::byte{'B'}); + REQUIRE(buffer[1024] == std::byte{'C'}); + REQUIRE(buffer[1535] == std::byte{'C'}); + } + + THEN("a read spanning a cluster boundary continues in the next cluster") + { + auto buffer = std::array<std::byte, 24>{}; + auto const read_result = read_cluster_chain(3, buffer, 500_B, *driver_state); + REQUIRE(read_result); + REQUIRE(*read_result == 24_B); + REQUIRE(std::ranges::count(buffer, std::byte{'A'}) == 12); + REQUIRE(std::ranges::count(buffer, std::byte{'B'}) == 12); + REQUIRE(buffer[11] == std::byte{'A'}); + REQUIRE(buffer[12] == std::byte{'B'}); + } + + THEN("an offset beyond the first cluster skips the preceding clusters") + { + auto buffer = std::array<std::byte, 10>{}; + auto const read_result = read_cluster_chain(3, buffer, 1100_B, *driver_state); + REQUIRE(read_result); + REQUIRE(*read_result == 10_B); + REQUIRE(std::ranges::count(buffer, std::byte{'C'}) == 10); + } + + THEN("a read is truncated at the end of the chain") + { + auto buffer = std::array<std::byte, 4 * 512>{}; + auto const read_result = read_cluster_chain(3, buffer, 0_B, *driver_state); + REQUIRE(read_result); + REQUIRE(*read_result == 1536_B); + + auto const tail_result = read_cluster_chain(3, buffer, 1500_B, *driver_state); + REQUIRE(tail_result); + REQUIRE(*tail_result == 36_B); + } + + THEN("reading at or past the end of the chain reads nothing") + { + auto buffer = std::array<std::byte, 16>{}; + REQUIRE(read_cluster_chain(3, buffer, 1536_B, *driver_state) == 0_B); + REQUIRE(read_cluster_chain(3, buffer, 5000_B, *driver_state) == 0_B); + } + + THEN("an empty buffer reads nothing") + { + REQUIRE(read_cluster_chain(3, std::span<std::byte>{}, 0_B, *driver_state) == 0_B); + } + + THEN("a chain cannot start outside the data region") + { + auto buffer = std::array<std::byte, 16>{}; + REQUIRE(read_cluster_chain(0, buffer, 0_B, *driver_state).error() == errc::invalid_cluster); + REQUIRE(read_cluster_chain(18, buffer, 0_B, *driver_state).error() == errc::invalid_cluster); + } + + THEN("a chain running into a free cluster is corrupted") + { + write_fat_entry(*device, 8, 9); + write_fat_entry(*device, 9, 0); + + auto buffer = std::array<std::byte, 3 * 512>{}; + REQUIRE(read_cluster_chain(8, buffer, 0_B, *driver_state).error() == errc::corrupted_cluster_chain); + } + + THEN("a cyclic chain is detected while reading and while skipping") + { + write_fat_entry(*device, 13, 14); + write_fat_entry(*device, 14, 13); + + auto buffer = std::array<std::byte, 17 * 512>{}; + REQUIRE(read_cluster_chain(13, buffer, 0_B, *driver_state).error() == errc::corrupted_cluster_chain); + REQUIRE(read_cluster_chain(13, std::span{buffer}.first(16), 20 * 512_B, *driver_state).error() == + errc::corrupted_cluster_chain); + } + } +} + // NOLINTEND(readability-magic-numbers) 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 <kernel/filesystems/fat32/filesystem.hpp> #include <kernel/filesystems/fat32/boot_sector.hpp> +#include <kernel/filesystems/fat32/directory_entry.hpp> #include <kernel/filesystems/fat32/driver_state.hpp> #include <kernel/filesystems/fat32/error.hpp> #include <kernel/filesystems/fat32/file_allocation_table.hpp> 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 <kernel/vfs/inode.hpp> +#include <kernel/filesystems/fat32/directory_entry.hpp> #include <kernel/filesystems/fat32/inode.hpp> #include <kapi/filesystem.hpp> 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 <kernel/filesystems/fat32/inode.hpp> +#include <kernel/filesystems/fat32/directory_entry.hpp> + #include <kstd/memory.hpp> #include <kstd/print.hpp> #include <kstd/units.hpp> diff --git a/kernel/kernel/test_support/filesystems/fat32.cpp b/kernel/kernel/test_support/filesystems/fat32.cpp index 4513a53a..233cc09f 100644 --- a/kernel/kernel/test_support/filesystems/fat32.cpp +++ b/kernel/kernel/test_support/filesystems/fat32.cpp @@ -7,8 +7,10 @@ #include <kstd/units.hpp> +#include <cstddef> #include <cstdint> #include <cstring> +#include <span> using namespace kstd::units_literals; @@ -70,4 +72,12 @@ namespace kernel::tests::filesystems::fat32 auto const offset = reserved_sectors * sector_size + cluster * kernel::filesystems::fat32::constants::fat_entry_size; write_bytes(device, offset, &value, kstd::size_of(value)); } + + auto write_cluster_data(kernel::tests::devices::block_device & device, std::uint32_t cluster, + std::span<std::byte const> data) -> void + { + auto const data_start = (reserved_sectors + fat_sectors) * sector_size; + auto const offset = data_start + (cluster - kernel::filesystems::fat32::constants::first_data_cluster) * sector_size; + write_bytes(device, offset, data.data(), kstd::bytes{data.size()}); + } } // namespace kernel::tests::filesystems::fat32 diff --git a/kernel/kernel/test_support/filesystems/fat32.hpp b/kernel/kernel/test_support/filesystems/fat32.hpp index e53974fb..1eb28c6f 100644 --- a/kernel/kernel/test_support/filesystems/fat32.hpp +++ b/kernel/kernel/test_support/filesystems/fat32.hpp @@ -4,7 +4,9 @@ #include <kernel/filesystems/fat32/boot_sector.hpp> #include <kernel/test_support/devices/block_device.hpp> +#include <cstddef> #include <cstdint> +#include <span> namespace kernel::tests::filesystems::fat32 { @@ -16,6 +18,8 @@ namespace kernel::tests::filesystems::fat32 kernel::filesystems::fat32::boot_sector const & boot_sector) -> void; auto write_fat_entry(kernel::tests::devices::block_device & device, std::uint32_t cluster, std::uint32_t value) -> void; + auto write_cluster_data(kernel::tests::devices::block_device & device, std::uint32_t cluster, + std::span<std::byte const> data) -> void; } // namespace kernel::tests::filesystems::fat32 |