Merge branch 'ext2-sparse-files' into 'develop-BA-FS26'

Ext2 sparse files

See merge request teachos/kernel!35

6 files changed, 186 insertions, 52 deletions

diff --git a/kernel/src/filesystem/ext2/filesystem.cpp b/kernel/src/filesystem/ext2/filesystem.cpp
index aaa50c7..893cc38 100644
--- a/kernel/src/filesystem/ext2/filesystem.cpp
+++ b/kernel/src/filesystem/ext2/filesystem.cpp
@@ -13,6 +13,7 @@
 #include <cstddef>
 #include <cstdint>
 #include <string_view>
+#include <unistd.h>
 
 namespace kernel::filesystem::ext2
 {
@@ -113,7 +114,7 @@ namespace kernel::filesystem::ext2
   }
 
   auto filesystem::map_inode_block_index_to_global_block_number(uint32_t inode_block_index, inode_data data) const
-      -> uint32_t
+      -> ssize_t
   {
     if (inode_block_index < constants::direct_block_count)
     {
@@ -121,54 +122,75 @@ namespace kernel::filesystem::ext2
     }
     inode_block_index -= constants::direct_block_count;
 
-    auto const block_size = get_block_size();
-    auto const numbers_per_block = block_size / sizeof(uint32_t);
-
-    auto const block_numbers_per_singly_indirect_block = numbers_per_block;
-    auto const block_numbers_per_doubly_indirect_block = numbers_per_block * block_numbers_per_singly_indirect_block;
-    auto const block_numbers_per_triply_indirect_block = numbers_per_block * block_numbers_per_doubly_indirect_block;
-
-    if (inode_block_index < block_numbers_per_singly_indirect_block)
+    if (inode_block_index < block_numbers_per_singly_indirect_block())
     {
       auto const singly_indirect_block_number = data.block.at(constants::singly_indirect_block_index);
-      return read_block_number_at_index(singly_indirect_block_number, inode_block_index);
+      return read_singly_indirect_block_number(singly_indirect_block_number, inode_block_index);
     }
-    inode_block_index -= block_numbers_per_singly_indirect_block;
+    inode_block_index -= block_numbers_per_singly_indirect_block();
 
-    if (inode_block_index < block_numbers_per_doubly_indirect_block)
+    if (inode_block_index < block_numbers_per_doubly_indirect_block())
     {
       auto const doubly_indirect_block_number = data.block.at(constants::doubly_indirect_block_index);
-      auto const singly_indirect_block_index_in_doubly_indirect_block =
-          inode_block_index / block_numbers_per_singly_indirect_block;
-      auto const singly_indirect_block_number = read_block_number_at_index(
-          doubly_indirect_block_number, singly_indirect_block_index_in_doubly_indirect_block);
-
-      auto const block_index_in_singly_indirect_block = inode_block_index % block_numbers_per_singly_indirect_block;
-      return read_block_number_at_index(singly_indirect_block_number, block_index_in_singly_indirect_block);
+      return read_doubly_indirect_block_number(doubly_indirect_block_number, inode_block_index);
     }
-    inode_block_index -= block_numbers_per_doubly_indirect_block;
+    inode_block_index -= block_numbers_per_doubly_indirect_block();
 
-    if (inode_block_index < block_numbers_per_triply_indirect_block)
+    if (inode_block_index < block_numbers_per_triply_indirect_block())
     {
       auto const triply_indirect_block_number = data.block.at(constants::triply_indirect_block_index);
-      auto const doubly_indirect_block_index_in_triply_indirect_block =
-          inode_block_index / block_numbers_per_doubly_indirect_block;
-      auto const doubly_indirect_block_number = read_block_number_at_index(
-          triply_indirect_block_number, doubly_indirect_block_index_in_triply_indirect_block);
+      return read_triply_indirect_block_number(triply_indirect_block_number, inode_block_index);
+    }
+
+    return -1;
+  }
+
+  auto filesystem::read_singly_indirect_block_number(uint32_t singly_indirect_block_number,
+                                                     uint32_t block_index_in_singly_indirect_block) const -> uint32_t
+  {
+    if (singly_indirect_block_number == 0)
+    {
+      return 0;
+    }
+    return read_block_number_at_index(singly_indirect_block_number, block_index_in_singly_indirect_block);
+  }
+
+  auto filesystem::read_doubly_indirect_block_number(uint32_t doubly_indirect_block_number,
+                                                     uint32_t block_index_in_doubly_indirect_block) const -> uint32_t
+  {
+    if (doubly_indirect_block_number == 0)
+    {
+      return 0;
+    }
+
+    auto const singly_indirect_block_index_in_doubly_indirect_block =
+        block_index_in_doubly_indirect_block / block_numbers_per_singly_indirect_block();
+    auto const block_index_in_singly_indirect_block =
+        block_index_in_doubly_indirect_block % block_numbers_per_singly_indirect_block();
 
-      auto const remaining_block_numbers = inode_block_index % block_numbers_per_doubly_indirect_block;
+    auto const singly_indirect_block_number =
+        read_block_number_at_index(doubly_indirect_block_number, singly_indirect_block_index_in_doubly_indirect_block);
 
-      auto const singly_indirect_block_index_in_doubly_indirect_block =
-          remaining_block_numbers / block_numbers_per_singly_indirect_block;
-      auto const singly_indirect_block_number = read_block_number_at_index(
-          doubly_indirect_block_number, singly_indirect_block_index_in_doubly_indirect_block);
+    return read_singly_indirect_block_number(singly_indirect_block_number, block_index_in_singly_indirect_block);
+  }
 
-      auto const block_index_in_singly_indirect_block =
-          remaining_block_numbers % block_numbers_per_singly_indirect_block;
-      return read_block_number_at_index(singly_indirect_block_number, block_index_in_singly_indirect_block);
+  auto filesystem::read_triply_indirect_block_number(uint32_t triply_indirect_block_number,
+                                                     uint32_t block_index_in_triply_indirect_block) const -> uint32_t
+  {
+    if (triply_indirect_block_number == 0)
+    {
+      return 0;
     }
 
-    return 0;  // TODO BA-FS26 really correct??
+    auto const doubly_indirect_block_index_in_triply_indirect_block =
+        block_index_in_triply_indirect_block / block_numbers_per_doubly_indirect_block();
+    auto const block_index_in_doubly_indirect_block =
+        block_index_in_triply_indirect_block % block_numbers_per_doubly_indirect_block();
+
+    auto const doubly_indirect_block_number =
+        read_block_number_at_index(triply_indirect_block_number, doubly_indirect_block_index_in_triply_indirect_block);
+
+    return read_doubly_indirect_block_number(doubly_indirect_block_number, block_index_in_doubly_indirect_block);
   }
 
   auto filesystem::read_block_number_at_index(uint32_t block_number, uint32_t index) const -> uint32_t
@@ -182,6 +204,26 @@ namespace kernel::filesystem::ext2
     return block_number_buffer;
   }
 
+  auto filesystem::block_numbers_per_block() const -> uint32_t
+  {
+    return get_block_size() / sizeof(uint32_t);
+  }
+
+  auto filesystem::block_numbers_per_singly_indirect_block() const -> uint32_t
+  {
+    return block_numbers_per_block();
+  }
+
+  auto filesystem::block_numbers_per_doubly_indirect_block() const -> uint32_t
+  {
+    return block_numbers_per_singly_indirect_block() * block_numbers_per_block();
+  }
+
+  auto filesystem::block_numbers_per_triply_indirect_block() const -> uint32_t
+  {
+    return block_numbers_per_doubly_indirect_block() * block_numbers_per_block();
+  }
+
   auto filesystem::get_block_size() const -> size_t
   {
     return constants::base_block_size << m_superblock.log_block_size;
diff --git a/kernel/src/filesystem/ext2/filesystem.tests.cpp b/kernel/src/filesystem/ext2/filesystem.tests.cpp
index 31c4c29..8341070 100644
--- a/kernel/src/filesystem/ext2/filesystem.tests.cpp
+++ b/kernel/src/filesystem/ext2/filesystem.tests.cpp
@@ -133,7 +133,7 @@ SCENARIO("Ext2 block mapping includes direct and all indirect levels", "[filesys
     THEN("mapping returns zero for out-of-range indexes")
     {
       auto const beyond_triply = triply_start + numbers_per_block * numbers_per_block * numbers_per_block;
-      REQUIRE(fs.map_inode_block_index_to_global_block_number(beyond_triply, inode_data) == 0);
+      REQUIRE(fs.map_inode_block_index_to_global_block_number(beyond_triply, inode_data) == -1);
     }
   }
 }
diff --git a/kernel/src/filesystem/ext2/inode.cpp b/kernel/src/filesystem/ext2/inode.cpp
index 303838e..cfe0a35 100644
--- a/kernel/src/filesystem/ext2/inode.cpp
+++ b/kernel/src/filesystem/ext2/inode.cpp
@@ -40,23 +40,29 @@ namespace kernel::filesystem::ext2
 
     auto bytes_read = 0uz;
 
-    while (bytes_read < size)
+    while (bytes_read < requested_size)
     {
       auto const block_number = m_filesystem->map_inode_block_index_to_global_block_number(block_index, m_data);
-      // TODO BA-FS26 really correct? sparse files -> 0 means a full block with zeros --> function
-      // map_inode_block_index_to_global_block_number should return 0 if not possible to find an block
-      if (block_number == 0)
+      if (block_number == -1)
       {
         break;
       }
 
-      auto const block_start_offset = block_number * m_filesystem->get_block_size();
-      auto const read_offset = block_start_offset + in_block_offset;
       auto const bytes_to_read =
           std::min(requested_size - bytes_read, m_filesystem->get_block_size() - in_block_offset);
+      if (block_number == 0)
+      {
+        kstd::libc::memset(static_cast<uint8_t *>(buffer) + bytes_read, 0, bytes_to_read);
+        bytes_read += bytes_to_read;
+      }
+      else
+      {
+        auto const block_start_offset = block_number * m_filesystem->get_block_size();
+        auto const read_offset = block_start_offset + in_block_offset;
 
-      bytes_read +=
-          m_filesystem->backing_inode()->read(static_cast<uint8_t *>(buffer) + bytes_read, read_offset, bytes_to_read);
+        bytes_read += m_filesystem->backing_inode()->read(static_cast<uint8_t *>(buffer) + bytes_read, read_offset,
+                                                          bytes_to_read);
+      }
 
       block_index++;
       in_block_offset = 0;  // After the first block, we always start at the beginning of the block
diff --git a/kernel/src/filesystem/ext2/inode.tests.cpp b/kernel/src/filesystem/ext2/inode.tests.cpp
index 783d930..45bea51 100644
--- a/kernel/src/filesystem/ext2/inode.tests.cpp
+++ b/kernel/src/filesystem/ext2/inode.tests.cpp
@@ -15,6 +15,7 @@
 
 #include <catch2/catch_test_macros.hpp>
 
+#include <algorithm>
 #include <cstddef>
 #include <filesystem>
 #include <string_view>
@@ -126,10 +127,10 @@ SCENARIO_METHOD(kernel::tests::filesystem::storage_boot_module_fixture, "Ext2 in
   }
 }
 
-SCENARIO("Ext2 inode read stops when block mapping resolves to zero", "[filesystem][ext2][inode]")
+SCENARIO("Ext2 inode handles zeros in block mappings as file holes", "[filesystem][ext2][inode]")
 {
   auto const block_size = 1024uz;
-  GIVEN("an ext2 inode without mapped data blocks")
+  GIVEN("an ext2 inode with only direct mapped data blocks")
   {
     auto device = kstd::make_shared<kernel::tests::devices::block_device>(0, 0, "mock", block_size, 64 * block_size);
     REQUIRE(device != nullptr);
@@ -141,16 +142,100 @@ SCENARIO("Ext2 inode read stops when block mapping resolves to zero", "[filesyst
     REQUIRE(fs.mount(dev_inode) == kernel::filesystem::filesystem::operation_result::success);
 
     auto data = kernel::filesystem::ext2::inode_data{};
-    data.blocks = 2;
-    data.block[0] = 0;
+    data.block[0] = 30;
+    data.block[1] = 0;
+    data.block[2] = 31;
+    data.size = block_size * 3;
+
+    kernel::tests::filesystem::ext2::write_bytes(*device, 30 * block_size, "Hello", 5);
+    kernel::tests::filesystem::ext2::write_bytes(*device, 31 * block_size, "World!", 6);
+
+    auto inode = kernel::filesystem::ext2::inode{&fs, data};
+
+    auto buffer = kstd::vector<std::byte>(data.size, std::byte{0xAB});
+
+    THEN("correct number of bytes are read and holes are returned as zeros")
+    {
+      auto const bytes_read = inode.read(buffer.data(), 0, buffer.size());
+      REQUIRE(bytes_read == data.size);
+
+      auto const text = std::string_view{reinterpret_cast<char const *>(buffer.data()), bytes_read};
+      REQUIRE(text.substr(0, 5) == "Hello");
+      REQUIRE(std::ranges::all_of(text.substr(5, block_size - 5), [](char c) { return c == '\0'; }));
+      REQUIRE(text.substr(2 * block_size, 6) == "World!");
+      REQUIRE(std::ranges::all_of(text.substr(2 * block_size + 6, 3 * block_size), [](char c) { return c == '\0'; }));
+    }
+  }
+
+  GIVEN("an ext2 indode with file holes in singly indirect blocks")
+  {
+    auto device = kstd::make_shared<kernel::tests::devices::block_device>(0, 0, "mock", block_size, 64 * block_size);
+    REQUIRE(device != nullptr);
+    kernel::tests::filesystem::ext2::setup_mock_ext2_layout(*device);
+
+    auto dev_inode = kstd::make_shared<kernel::filesystem::device_inode>(device);
+
+    auto fs = kernel::filesystem::ext2::filesystem{};
+    REQUIRE(fs.mount(dev_inode) == kernel::filesystem::filesystem::operation_result::success);
+
+    auto data = kernel::filesystem::ext2::inode_data{};
+    data.block[0] = 30;
+    data.block[12] = 31;
+    data.size = block_size * 15;
+
+    kernel::tests::filesystem::ext2::write_u32(*device, 31 * block_size, 50);
+    kernel::tests::filesystem::ext2::write_u32(*device, 31 * block_size + 4, 0);
+    kernel::tests::filesystem::ext2::write_u32(*device, 31 * block_size + 8, 51);
+
+    kernel::tests::filesystem::ext2::write_bytes(*device, 30 * block_size, "Hello", 5);
+    kernel::tests::filesystem::ext2::write_bytes(*device, 50 * block_size, "Blub", 4);
+    kernel::tests::filesystem::ext2::write_bytes(*device, 51 * block_size, "World!", 6);
+
+    auto inode = kernel::filesystem::ext2::inode{&fs, data};
+
+    auto buffer = kstd::vector<std::byte>(data.size, std::byte{0xAB});
+
+    THEN("correct number of bytes are read and holes are returned as zeros")
+    {
+      auto const bytes_read = inode.read(buffer.data(), 0, buffer.size());
+      REQUIRE(bytes_read == data.size);
+
+      auto const text = std::string_view{reinterpret_cast<char const *>(buffer.data()), bytes_read};
+      REQUIRE(text.substr(0, 5) == "Hello");
+      REQUIRE(std::ranges::all_of(text.substr(5, 12 * block_size - 5), [](char c) { return c == '\0'; }));
+      REQUIRE(text.substr(12 * block_size, 4) == "Blub");
+      REQUIRE(
+          std::ranges::all_of(text.substr(12 * block_size + 4, 2 * block_size - 4), [](char c) { return c == '\0'; }));
+      REQUIRE(text.substr(14 * block_size, 6) == "World!");
+      REQUIRE(
+          std::ranges::all_of(text.substr(14 * block_size + 6, 1 * block_size - 6), [](char c) { return c == '\0'; }));
+    }
+  }
+
+  GIVEN("an ext2 inode with zero singly indirect block pointer")
+  {
+    auto device = kstd::make_shared<kernel::tests::devices::block_device>(0, 0, "mock", block_size, 64 * block_size);
+    REQUIRE(device != nullptr);
+    kernel::tests::filesystem::ext2::setup_mock_ext2_layout(*device);
+
+    auto dev_inode = kstd::make_shared<kernel::filesystem::device_inode>(device);
+
+    auto fs = kernel::filesystem::ext2::filesystem{};
+    REQUIRE(fs.mount(dev_inode) == kernel::filesystem::filesystem::operation_result::success);
+
+    auto data = kernel::filesystem::ext2::inode_data{};
+    data.block[12] = 0;
+    data.size = block_size * 15;
+
     auto inode = kernel::filesystem::ext2::inode{&fs, data};
 
-    auto buffer = kstd::vector<std::byte>(32, std::byte{0xAB});
+    auto buffer = kstd::vector<std::byte>(block_size * 15, std::byte{0xAB});
 
-    THEN("no bytes are read")
+    THEN("all direct blocks are zero when singly indirect block pointer is zero")
     {
       auto const bytes_read = inode.read(buffer.data(), 0, buffer.size());
-      REQUIRE(bytes_read == 0);
+      REQUIRE(bytes_read == buffer.size());
+      REQUIRE(std::ranges::all_of(buffer, [](std::byte c) { return c == std::byte{0x00}; }));
     }
   }
 }
@@ -170,7 +255,7 @@ SCENARIO("Ext2 inode read across block boundaries", "[filesystem][ext2][inode]")
     REQUIRE(fs.mount(dev_inode) == kernel::filesystem::filesystem::operation_result::success);
 
     auto inode_data = kernel::filesystem::ext2::inode_data{};
-    inode_data.blocks = 2;
+    inode_data.size = block_size * 2;
     inode_data.block[0] = 20;
     kernel::tests::filesystem::ext2::write_bytes(*device, 21 * block_size - 6, "Hello ", 6);
     inode_data.block[1] = 21;
diff --git a/kernel/src/filesystem/mount_table.cpp b/kernel/src/filesystem/mount_table.cpp
index daef93e..5a49e7a 100644
--- a/kernel/src/filesystem/mount_table.cpp
+++ b/kernel/src/filesystem/mount_table.cpp
@@ -34,6 +34,7 @@ namespace kernel::filesystem
 
   auto mount_table::remove_mount(std::string_view path) -> operation_result
   {
+    // TODO BA-FS26 check wheter something is open in this mount
     auto mount_range =
         std::ranges::find_last_if(m_mounts, [&](auto const & mount) { return mount->get_mount_path() == path; });
     auto mount_it = mount_range.begin();
diff --git a/kernel/src/filesystem/vfs.cpp b/kernel/src/filesystem/vfs.cpp
index 535f898..f5d57be 100644
--- a/kernel/src/filesystem/vfs.cpp
+++ b/kernel/src/filesystem/vfs.cpp
@@ -143,7 +143,7 @@ namespace kernel::filesystem
     {
       parent_mount = m_mount_table.find_exact_mount(parent_mount_dentry->get_absolute_path().view());
     }
-    
+
     auto new_fs_root =
         kstd::make_shared<dentry>(mount_point_dentry->get_parent(), fs->root_inode(), mount_point_dentry->get_name());
     auto new_mount = kstd::make_shared<mount>(mount_point_dentry, new_fs_root, fs, parent_mount);