[PATCH edk2-platforms 3/3] Ext4Pkg: Add ext2/3 support

["Pedro Falcato" <pedro.falcato@gmail.com>]

BZ: https://bugzilla.tianocore.org/show_bug.cgi?id=3745

Adds ext2/3 support by supporting (legacy) block maps.
Also fixes a bug regarding uninitialised extents.

Cc: Leif Lindholm <leif@nuviainc.com>
Cc: Michael D Kinney <michael.d.kinney@intel.com>
Signed-off-by: Pedro Falcato <pedro.falcato@gmail.com>
---
 Features/Ext4Pkg/Ext4Dxe/BlockMap.c   | 279 ++++++++++++++++++++++++++
 Features/Ext4Pkg/Ext4Dxe/Ext4Disk.h   |   2 +
 Features/Ext4Pkg/Ext4Dxe/Ext4Dxe.h    |  18 ++
 Features/Ext4Pkg/Ext4Dxe/Ext4Dxe.inf  |   1 +
 Features/Ext4Pkg/Ext4Dxe/Extents.c    |  17 +-
 Features/Ext4Pkg/Ext4Dxe/Inode.c      |   9 +-
 Features/Ext4Pkg/Ext4Dxe/Superblock.c |   7 +-
 7 files changed, 318 insertions(+), 15 deletions(-)
 create mode 100644 Features/Ext4Pkg/Ext4Dxe/BlockMap.c

diff --git a/Features/Ext4Pkg/Ext4Dxe/BlockMap.c b/Features/Ext4Pkg/Ext4Dxe/BlockMap.c
new file mode 100644
index 000000000000..6e8ccaa82437
--- /dev/null
+++ b/Features/Ext4Pkg/Ext4Dxe/BlockMap.c
@@ -0,0 +1,279 @@
+/** @file
+  Implementation of routines that deal with ext2/3 block maps.
+
+  Copyright (c) 2022 Pedro Falcato All rights reserved.
+  SPDX-License-Identifier: BSD-2-Clause-Patent
+**/
+
+#include <Ext4Dxe.h>
+
+// Note: The largest path we can take uses up 4 indices
+#define EXT4_MAX_BLOCK_PATH  4
+
+typedef enum ext4_logical_block_type {
+  EXT4_TYPE_DIRECT_BLOCK = 0,
+  EXT4_TYPE_SINGLY_BLOCK,
+  EXT4_TYPE_DOUBLY_BLOCK,
+  EXT4_TYPE_TREBLY_BLOCK,
+  EXT4_TYPE_BAD_BLOCK
+} EXT4_LOGICAL_BLOCK_TYPE;
+
+/**
+   @brief Detect the type of path the logical block will follow
+
+   @param[in] LogicalBlock The logical block
+   @param[in] Partition    Pointer to an EXT4_PARTITION
+   @return The type of path the logical block will need to follow
+ */
+STATIC
+EXT4_LOGICAL_BLOCK_TYPE
+Ext4DetectBlockType (
+  IN UINT32                LogicalBlock,
+  IN CONST EXT4_PARTITION  *Partition
+  )
+{
+  UINT32  Entries;
+  UINT32  MinSinglyBlock;
+  UINT32  MinDoublyBlock;
+  UINT32  MinTreblyBlock;
+  UINT32  MinQuadBlock;
+
+  Entries        = (Partition->BlockSize / sizeof (UINT32));
+  MinSinglyBlock = EXT4_DBLOCKS;
+  MinDoublyBlock = Entries + MinSinglyBlock;
+  MinTreblyBlock = Entries * Entries + MinDoublyBlock;
+  MinQuadBlock   = Entries * Entries * Entries + MinTreblyBlock; // Doesn't actually exist
+
+  if (LogicalBlock < MinSinglyBlock) {
+    return EXT4_TYPE_DIRECT_BLOCK;
+  } else if ((LogicalBlock >= MinSinglyBlock) && (LogicalBlock < MinDoublyBlock)) {
+    return EXT4_TYPE_SINGLY_BLOCK;
+  } else if ((LogicalBlock >= MinDoublyBlock) && (LogicalBlock < MinTreblyBlock)) {
+    return EXT4_TYPE_DOUBLY_BLOCK;
+  } else if (((LogicalBlock >= MinTreblyBlock) && (LogicalBlock < MinQuadBlock))) {
+    return EXT4_TYPE_TREBLY_BLOCK;
+  } else {
+    return EXT4_TYPE_BAD_BLOCK;
+  }
+}
+
+/**
+   @brief Get a block's path in indices
+
+   @param[in]  Partition       Pointer to an EXT4_PARTITION
+   @param[in]  LogicalBlock    Logical block
+   @param[out] BlockPath       Pointer to an array of EXT4_MAX_BLOCK_PATH elements, where the
+                               indices we'll need to read are inserted.
+   @return The number of path elements that are required (and were inserted in BlockPath)
+ */
+UINTN
+Ext4GetBlockPath (
+  IN  CONST EXT4_PARTITION  *Partition,
+  IN  UINT32                LogicalBlock,
+  OUT EXT4_BLOCK_NR         BlockPath[EXT4_MAX_BLOCK_PATH]
+  )
+{
+  // The logic behind the block map is very much like a page table
+  // Let's think of blocks with 512 entries (exactly like a page table on x64).
+  // On doubly indirect block paths, we subtract the min doubly blocks from the logical block.
+  // The top 9 bits of the result are the index inside the dind block, the bottom 9 bits are the
+  // index inside the ind block. Since Entries is always a power of 2, entries - 1 will give us
+  // a mask of the BlockMapBits.
+  // Note that all this math could be done with ands and shifts (similar implementations exist
+  // in a bunch of other places), but I'm doing it a simplified way with divs and modulus,
+  // since it's not going to be a bottleneck anyway.
+
+  UINT32  Entries;
+  UINT32  EntriesEntries;
+  UINT32  MinSinglyBlock;
+  UINT32  MinDoublyBlock;
+  UINT32  MinTreblyBlock;
+
+  EXT4_LOGICAL_BLOCK_TYPE  Type;
+
+  Entries        = (Partition->BlockSize / sizeof (UINT32));
+  EntriesEntries = Entries * Entries;
+
+  MinSinglyBlock = EXT4_DBLOCKS;
+  MinDoublyBlock = Entries + MinSinglyBlock;
+  MinTreblyBlock = EntriesEntries + MinDoublyBlock;
+
+  Type = Ext4DetectBlockType (LogicalBlock, Partition);
+
+  switch (Type) {
+    case EXT4_TYPE_DIRECT_BLOCK:
+      BlockPath[0] = LogicalBlock;
+      break;
+    case EXT4_TYPE_SINGLY_BLOCK:
+      BlockPath[0] = EXT4_IND_BLOCK;
+      BlockPath[1] = LogicalBlock - EXT4_DBLOCKS;
+      break;
+    case EXT4_TYPE_DOUBLY_BLOCK:
+      BlockPath[0]  = EXT4_DIND_BLOCK;
+      LogicalBlock -= MinDoublyBlock;
+      BlockPath[1]  = LogicalBlock / Entries;
+      BlockPath[2]  = LogicalBlock % Entries;
+      break;
+    case EXT4_TYPE_TREBLY_BLOCK:
+      BlockPath[0]  = EXT4_DIND_BLOCK;
+      LogicalBlock -= MinTreblyBlock;
+      BlockPath[1]  = LogicalBlock / EntriesEntries;
+      BlockPath[2]  = (LogicalBlock % EntriesEntries) / Entries;
+      BlockPath[3]  = (LogicalBlock % EntriesEntries) % Entries;
+      break;
+    default:
+      // EXT4_TYPE_BAD_BLOCK
+      return -1;
+  }
+
+  return Type + 1;
+}
+
+/**
+   @brief Get an extent from a block map
+   Note: Also parses file holes and creates uninitialised extents from them.
+
+   @param[in]  Buffer          Buffer of block pointers
+   @param[in]  IndEntries      Number of entries in this block pointer table
+   @param[in]  StartIndex      The start index from which we want to find a contiguous extent
+   @param[out] Extent          Pointer to the resulting EXT4_EXTENT
+ */
+VOID
+Ext4GetExtentInBlockMap (
+  IN CONST UINT32  *Buffer,
+  IN CONST UINT32  IndEntries,
+  IN UINT32        StartIndex,
+  OUT EXT4_EXTENT  *Extent
+  )
+{
+  UINT32  Index;
+  UINT32  FirstBlock;
+  UINT32  LastBlock;
+  UINT16  Count;
+
+  Count      = 1;
+  LastBlock  = Buffer[StartIndex];
+  FirstBlock = LastBlock;
+
+  if (FirstBlock == EXT4_BLOCK_FILE_HOLE) {
+    // File hole, let's see how many blocks this hole spans
+    Extent->ee_start_hi = 0;
+    Extent->ee_start_lo = 0;
+
+    for (Index = StartIndex + 1; Index < IndEntries; Index++) {
+      if (Count == EXT4_EXTENT_MAX_INITIALIZED - 1) {
+        // We've reached the max size of an uninit extent, break
+        break;
+      }
+
+      if (Buffer[Index] == EXT4_BLOCK_FILE_HOLE) {
+        Count++;
+      } else {
+        break;
+      }
+    }
+
+    // We mark the extent as uninitialised, although there's a difference between uninit
+    // extents and file holes.
+    Extent->ee_len = EXT4_EXTENT_MAX_INITIALIZED + Count;
+    return;
+  }
+
+  for (Index = StartIndex + 1; Index < IndEntries; Index++) {
+    if (Count == EXT4_EXTENT_MAX_INITIALIZED) {
+      // We've reached the max size of an extent, break
+      break;
+    }
+
+    if ((Buffer[Index] == LastBlock + 1) && (Buffer[Index] != EXT4_BLOCK_FILE_HOLE)) {
+      Count++;
+    } else {
+      break;
+    }
+
+    LastBlock = Buffer[Index];
+  }
+
+  Extent->ee_start_lo = FirstBlock;
+  Extent->ee_start_hi = 0;
+  Extent->ee_len      = Count;
+}
+
+/**
+   Retrieves an extent from an EXT2/3 inode (with a blockmap).
+   @param[in]      Partition     Pointer to the opened EXT4 partition.
+   @param[in]      File          Pointer to the opened file.
+   @param[in]      LogicalBlock  Block number which the returned extent must cover.
+   @param[out]     Extent        Pointer to the output buffer, where the extent will be copied to.
+
+   @retval EFI_SUCCESS        Retrieval was succesful.
+   @retval EFI_NO_MAPPING     Block has no mapping.
+**/
+EFI_STATUS
+Ext4GetBlocks (
+  IN  EXT4_PARTITION  *Partition,
+  IN  EXT4_FILE       *File,
+  IN  EXT4_BLOCK_NR   LogicalBlock,
+  OUT EXT4_EXTENT     *Extent
+  )
+{
+  EXT4_INODE     *Inode;
+  EXT4_BLOCK_NR  BlockPath[EXT4_MAX_BLOCK_PATH];
+  UINTN          BlockPathLength;
+  UINTN          Index;
+  UINT32         *Buffer;
+  EFI_STATUS     Status;
+  UINT32         Block;
+  UINT32         BlockIndex;
+
+  Inode = File->Inode;
+
+  BlockPathLength = Ext4GetBlockPath (Partition, LogicalBlock, BlockPath);
+
+  if (BlockPathLength == (UINTN)-1) {
+    // Bad logical block (out of range)
+    return EFI_NO_MAPPING;
+  }
+
+  Extent->ee_block = LogicalBlock;
+
+  if (BlockPathLength == 1) {
+    // Fast path for blocks 0 - 12 that skips allocations
+    Ext4GetExtentInBlockMap (Inode->i_data, EXT4_DBLOCKS, BlockPath[0], Extent);
+
+    return EFI_SUCCESS;
+  }
+
+  Buffer = AllocatePool (Partition->BlockSize);
+  if (Buffer == NULL) {
+    return EFI_OUT_OF_RESOURCES;
+  }
+
+  // Note the BlockPathLength - 1 so we don't end up reading the final block
+  for (Index = 0; Index < BlockPathLength - 1; Index++) {
+    BlockIndex = BlockPath[Index];
+
+    if (Index == 0) {
+      Block = Inode->i_data[BlockIndex];
+    } else {
+      Block = Buffer[BlockIndex];
+    }
+
+    if (Block == EXT4_BLOCK_FILE_HOLE) {
+      FreePool (Buffer);
+      return EFI_NO_MAPPING;
+    }
+
+    Status = Ext4ReadBlocks (Partition, Buffer, 1, Block);
+
+    if (EFI_ERROR (Status)) {
+      FreePool (Buffer);
+      return Status;
+    }
+  }
+
+  Ext4GetExtentInBlockMap (Buffer, Partition->BlockSize / sizeof (UINT32), BlockPath[BlockPathLength - 1], Extent);
+  FreePool (Buffer);
+
+  return EFI_SUCCESS;
+}
diff --git a/Features/Ext4Pkg/Ext4Dxe/Ext4Disk.h b/Features/Ext4Pkg/Ext4Dxe/Ext4Disk.h
index 5f812215fbb8..a55cd2fa68ad 100644
--- a/Features/Ext4Pkg/Ext4Dxe/Ext4Disk.h
+++ b/Features/Ext4Pkg/Ext4Dxe/Ext4Disk.h
@@ -468,4 +468,6 @@ typedef UINT32  EXT4_INO_NR;
 // 2 is always the root inode number in ext4
 #define EXT4_ROOT_INODE_NR  2
 
+#define EXT4_BLOCK_FILE_HOLE  0
+
 #endif
diff --git a/Features/Ext4Pkg/Ext4Dxe/Ext4Dxe.h b/Features/Ext4Pkg/Ext4Dxe/Ext4Dxe.h
index 03e0586cbb05..b1508482b0a7 100644
--- a/Features/Ext4Pkg/Ext4Dxe/Ext4Dxe.h
+++ b/Features/Ext4Pkg/Ext4Dxe/Ext4Dxe.h
@@ -1151,4 +1151,22 @@ Ext4GetExtentLength (
   IN CONST EXT4_EXTENT  *Extent
   );
 
+/**
+   Retrieves an extent from an EXT2/3 inode (with a blockmap).
+   @param[in]      Partition     Pointer to the opened EXT4 partition.
+   @param[in]      File          Pointer to the opened file.
+   @param[in]      LogicalBlock  Block number which the returned extent must cover.
+   @param[out]     Extent        Pointer to the output buffer, where the extent will be copied to.
+
+   @retval EFI_SUCCESS        Retrieval was succesful.
+   @retval EFI_NO_MAPPING     Block has no mapping.
+**/
+EFI_STATUS
+Ext4GetBlocks (
+  IN  EXT4_PARTITION  *Partition,
+  IN  EXT4_FILE       *File,
+  IN  EXT4_BLOCK_NR   LogicalBlock,
+  OUT EXT4_EXTENT     *Extent
+  );
+
 #endif
diff --git a/Features/Ext4Pkg/Ext4Dxe/Ext4Dxe.inf b/Features/Ext4Pkg/Ext4Dxe/Ext4Dxe.inf
index 12e89bf1fdfc..deaf89fb3743 100644
--- a/Features/Ext4Pkg/Ext4Dxe/Ext4Dxe.inf
+++ b/Features/Ext4Pkg/Ext4Dxe/Ext4Dxe.inf
@@ -111,6 +111,7 @@
   Collation.c
   Ext4Disk.h
   Ext4Dxe.h
+  BlockMap.c
 
 [Packages]
   MdePkg/MdePkg.dec
diff --git a/Features/Ext4Pkg/Ext4Dxe/Extents.c b/Features/Ext4Pkg/Ext4Dxe/Extents.c
index e920eed090fd..c3874df71751 100644
--- a/Features/Ext4Pkg/Ext4Dxe/Extents.c
+++ b/Features/Ext4Pkg/Ext4Dxe/Extents.c
@@ -1,7 +1,7 @@
 /** @file
   Extent related routines
 
-  Copyright (c) 2021 Pedro Falcato All rights reserved.
+  Copyright (c) 2021 - 2022 Pedro Falcato All rights reserved.
   SPDX-License-Identifier: BSD-2-Clause-Patent
 **/
 
@@ -244,10 +244,6 @@ Ext4GetExtent (
 
   DEBUG ((DEBUG_FS, "[ext4] Looking up extent for block %lu\n", LogicalBlock));
 
-  if (!(Inode->i_flags & EXT4_EXTENTS_FL)) {
-    return EFI_UNSUPPORTED;
-  }
-
   // ext4 does not have support for logical block numbers bigger than UINT32_MAX
   if (LogicalBlock > (UINT32)-1) {
     return EFI_NO_MAPPING;
@@ -261,6 +257,17 @@ Ext4GetExtent (
     return EFI_SUCCESS;
   }
 
+  if (!(Inode->i_flags & EXT4_EXTENTS_FL)) {
+    // If this is an older ext2/ext3 filesystem, emulate Ext4GetExtent using the block map
+    Status = Ext4GetBlocks (Partition, File, LogicalBlock, Extent);
+
+    if (!EFI_ERROR (Status)) {
+      Ext4CacheExtents (File, Extent, 1);
+    }
+
+    return Status;
+  }
+
   // Slow path, we'll need to read from disk and (try to) cache those extents.
 
   ExtHeader = Ext4GetInoExtentHeader (Inode);
diff --git a/Features/Ext4Pkg/Ext4Dxe/Inode.c b/Features/Ext4Pkg/Ext4Dxe/Inode.c
index f692909edf78..831f5946e870 100644
--- a/Features/Ext4Pkg/Ext4Dxe/Inode.c
+++ b/Features/Ext4Pkg/Ext4Dxe/Inode.c
@@ -1,7 +1,7 @@
 /** @file
   Inode related routines
 
-  Copyright (c) 2021 Pedro Falcato All rights reserved.
+  Copyright (c) 2021 - 2022 Pedro Falcato All rights reserved.
   SPDX-License-Identifier: BSD-2-Clause-Patent
 
   EpochToEfiTime copied from EmbeddedPkg/Library/TimeBaseLib.c
@@ -150,8 +150,9 @@ Ext4Read (
       if (!HasBackingExtent) {
         HoleLen = Partition->BlockSize - HoleOff;
       } else {
-        // Uninitialized extents behave exactly the same as file holes.
-        HoleLen = Ext4GetExtentLength (&Extent) - HoleOff;
+        // Uninitialized extents behave exactly the same as file holes, except they have
+        // blocks already allocated to them.
+        HoleLen = (Ext4GetExtentLength (&Extent) * Partition->BlockSize) - HoleOff;
       }
 
       WasRead = HoleLen > RemainingRead ? RemainingRead : HoleLen;
@@ -176,7 +177,7 @@ Ext4Read (
       if (EFI_ERROR (Status)) {
         DEBUG ((
           DEBUG_ERROR,
-          "[ext4] Error %x reading [%lu, %lu]\n",
+          "[ext4] Error %r reading [%lu, %lu]\n",
           Status,
           ExtentStartBytes + ExtentOffset,
           ExtentStartBytes + ExtentOffset + WasRead - 1
diff --git a/Features/Ext4Pkg/Ext4Dxe/Superblock.c b/Features/Ext4Pkg/Ext4Dxe/Superblock.c
index a7dbe9bf0fec..47fc3a65507a 100644
--- a/Features/Ext4Pkg/Ext4Dxe/Superblock.c
+++ b/Features/Ext4Pkg/Ext4Dxe/Superblock.c
@@ -1,7 +1,7 @@
 /** @file
   Superblock managing routines
 
-  Copyright (c) 2021 Pedro Falcato All rights reserved.
+  Copyright (c) 2021 - 2022 Pedro Falcato All rights reserved.
   SPDX-License-Identifier: BSD-2-Clause-Patent
 **/
 
@@ -208,11 +208,6 @@ Ext4OpenSuperblock (
     return EFI_UNSUPPORTED;
   }
 
-  // This should be removed once we add ext2/3 support in the future.
-  if ((Partition->FeaturesIncompat & EXT4_FEATURE_INCOMPAT_EXTENTS) == 0) {
-    return EFI_UNSUPPORTED;
-  }
-
   if (EXT4_HAS_INCOMPAT (Partition, EXT4_FEATURE_INCOMPAT_RECOVER)) {
     DEBUG ((DEBUG_WARN, "[ext4] Needs journal recovery, mounting read-only\n"));
     Partition->ReadOnly = TRUE;
-- 
2.35.1