From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-wr1-f45.google.com (mail-wr1-f45.google.com [209.85.221.45]) by mx.groups.io with SMTP id smtpd.web08.430.1649368913400520530 for ; Thu, 07 Apr 2022 15:01:53 -0700 Authentication-Results: mx.groups.io; dkim=pass header.i=@gmail.com header.s=20210112 header.b=XTS4hjxY; spf=pass (domain: gmail.com, ip: 209.85.221.45, mailfrom: pedro.falcato@gmail.com) Received: by mail-wr1-f45.google.com with SMTP id d29so9942085wra.10 for ; Thu, 07 Apr 2022 15:01:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=f5bL5VV6czkpHFiG0po+ojF32/u1Ytokr9drN33JV2c=; b=XTS4hjxYLDHhxVMMsS7hOkDa7nTfeXuZyhVHLd3GNLaN+j3c1UjPYbY8YVQWWLy7vI FlT71sdq0WXSSDqyvP4YwdXOQl2jPd66vxHWNMsbfE5HKlo8S0JPSLRD6xXVcv+fpsP9 JwnCQkZq8sJ/YEmYjid22DTkqAfD0V3G4iDBw3BvkpUIahfEy2YcbHhjyf5kD1KFKJKt HqMexcmAV9GJOCa+KxcAZKPqN91/imTZd4Qtu/smJbt7MmMat3wcb0HIBN6le494Dtkj U/iB4P18klQugf4yffQf+ahk6A6SsiuzJZ9rdSO9WcFYiuNF8gjap0wn2lKRdkUQpPpi pWPw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=f5bL5VV6czkpHFiG0po+ojF32/u1Ytokr9drN33JV2c=; b=RpUaj0gYj4Evv10Qsum0vP0aZ4wBrfoDWG/kl63MAv2Ife7fLFWmPjIH9qebogxxNs ncvtjksTgJrpEbKb6a81eXztwvtIqzXTVl9x7gLg5+HivAjO23+vEkVaRixhRgxYIfDX J7uAjB0WZjSM5ojWIO+PfE+RYGJwN/PeI2SZ7J/sEbzvWqoLfHmcZlYMBnUrIyigWsIa 0qbQekAraaD9Vj1Ag9E1tTEAMekJ5ypoUhUOHPa0s0f4iz3t+oXk2XMJ44PP04Xvtnqa uIYSTc7Id1NeZOyaVvNuw0l969pn496njSIpWc4nLKyymgXe2HZzaXUahLAkq1utMvKt 8u9w== X-Gm-Message-State: AOAM530rgx3ySeOrDR9P9khK50yEquIMWmA9IrWoI+eJa7dqttKW6fH3 WPTiWAoHZLxH0V6BB+rDgRH+vW46hJV8Qw== X-Google-Smtp-Source: ABdhPJw70bb5YB8LpIcW+bdS6Q9Mt1GyJsLoQEgzZzkXrWGi6NHgKCRAGbtcpho0lZH9tbQxMtH+bw== X-Received: by 2002:a1c:ed18:0:b0:37e:7a1d:a507 with SMTP id l24-20020a1ced18000000b0037e7a1da507mr14175691wmh.187.1649368911417; Thu, 07 Apr 2022 15:01:51 -0700 (PDT) Return-Path: Received: from PC-PEDRO-ARCH.lan ([2001:8a0:7280:5801:9441:3dce:686c:bfc7]) by smtp.gmail.com with ESMTPSA id m18-20020a05600c4f5200b0038e8f9d7b57sm2813379wmq.42.2022.04.07.15.01.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Apr 2022 15:01:51 -0700 (PDT) From: "Pedro Falcato" To: devel@edk2.groups.io Cc: Leif Lindholm , Michael D Kinney Subject: [PATCH edk2-platforms 3/3] Ext4Pkg: Add ext2/3 support Date: Thu, 7 Apr 2022 23:01:46 +0100 Message-Id: <20220407220146.149580-4-pedro.falcato@gmail.com> X-Mailer: git-send-email 2.35.1 In-Reply-To: <20220407220146.149580-1-pedro.falcato@gmail.com> References: <20220407220146.149580-1-pedro.falcato@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit 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 Cc: Michael D Kinney Signed-off-by: Pedro Falcato --- 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 + +// 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