123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634 |
- /** @file
- Extent related routines
- Copyright (c) 2021 - 2022 Pedro Falcato All rights reserved.
- SPDX-License-Identifier: BSD-2-Clause-Patent
- **/
- #include "Ext4Dxe.h"
- /**
- Checks if the checksum of the extent data block is correct.
- @param[in] ExtHeader Pointer to the EXT4_EXTENT_HEADER.
- @param[in] File Pointer to the file.
- @return TRUE if the checksum is correct, FALSE if there is corruption.
- **/
- BOOLEAN
- Ext4CheckExtentChecksum (
- IN CONST EXT4_EXTENT_HEADER *ExtHeader,
- IN CONST EXT4_FILE *File
- );
- /**
- Calculates the checksum of the extent data block.
- @param[in] ExtHeader Pointer to the EXT4_EXTENT_HEADER.
- @param[in] File Pointer to the file.
- @return The checksum.
- **/
- UINT32
- Ext4CalculateExtentChecksum (
- IN CONST EXT4_EXTENT_HEADER *ExtHeader,
- IN CONST EXT4_FILE *File
- );
- /**
- Caches a range of extents, by allocating pool memory for each extent and adding it to the tree.
- @param[in] File Pointer to the open file.
- @param[in] Extents Pointer to an array of extents.
- @param[in] NumberExtents Length of the array.
- **/
- VOID
- Ext4CacheExtents (
- IN EXT4_FILE *File,
- IN CONST EXT4_EXTENT *Extents,
- IN UINT16 NumberExtents
- );
- /**
- Gets an extent from the extents cache of the file.
- @param[in] File Pointer to the open file.
- @param[in] Block Block we want to grab.
- @return Pointer to the extent, or NULL if it was not found.
- **/
- EXT4_EXTENT *
- Ext4GetExtentFromMap (
- IN EXT4_FILE *File,
- IN UINT32 Block
- );
- /**
- Retrieves the pointer to the top of the extent tree.
- @param[in] Inode Pointer to the inode structure.
- @return Pointer to an EXT4_EXTENT_HEADER. This pointer is inside
- the inode and must not be freed.
- **/
- STATIC
- EXT4_EXTENT_HEADER *
- Ext4GetInoExtentHeader (
- IN EXT4_INODE *Inode
- )
- {
- return (EXT4_EXTENT_HEADER *)Inode->i_data;
- }
- /**
- Checks if an extent header is valid.
- @param[in] Header Pointer to the EXT4_EXTENT_HEADER structure.
- @return TRUE if valid, FALSE if not.
- **/
- STATIC
- BOOLEAN
- Ext4ExtentHeaderValid (
- IN CONST EXT4_EXTENT_HEADER *Header
- )
- {
- if (Header->eh_depth > EXT4_EXTENT_TREE_MAX_DEPTH) {
- DEBUG ((DEBUG_ERROR, "[ext4] Invalid extent header depth %u\n", Header->eh_depth));
- return FALSE;
- }
- if (Header->eh_magic != EXT4_EXTENT_HEADER_MAGIC) {
- DEBUG ((DEBUG_ERROR, "[ext4] Invalid extent header magic %x\n", Header->eh_magic));
- return FALSE;
- }
- if (Header->eh_max < Header->eh_entries) {
- DEBUG ((
- DEBUG_ERROR,
- "[ext4] Invalid extent header num entries %u max entries %u\n",
- Header->eh_entries,
- Header->eh_max
- ));
- return FALSE;
- }
- return TRUE;
- }
- /**
- Performs a binary search for a EXT4_EXTENT_INDEX that corresponds to a
- logical block in a given extent tree node.
- @param[in] Header Pointer to the EXT4_EXTENT_HEADER structure.
- @param[in] LogicalBlock Block that will be searched
- @return Pointer to the found EXT4_EXTENT_INDEX.
- **/
- STATIC
- EXT4_EXTENT_INDEX *
- Ext4BinsearchExtentIndex (
- IN EXT4_EXTENT_HEADER *Header,
- IN EXT4_BLOCK_NR LogicalBlock
- )
- {
- EXT4_EXTENT_INDEX *l;
- EXT4_EXTENT_INDEX *r;
- EXT4_EXTENT_INDEX *m;
- l = ((EXT4_EXTENT_INDEX *)(Header + 1)) + 1;
- r = ((EXT4_EXTENT_INDEX *)(Header + 1)) + Header->eh_entries - 1;
- // Perform a mostly-standard binary search on the array
- // This works very nicely because the extents arrays are always sorted.
- while (l <= r) {
- m = l + (r - l) / 2;
- if (LogicalBlock < m->ei_block) {
- r = m - 1;
- } else {
- l = m + 1;
- }
- }
- return l - 1;
- }
- /**
- Performs a binary search for a EXT4_EXTENT that corresponds to a
- logical block in a given extent tree node.
- @param[in] Header Pointer to the EXT4_EXTENT_HEADER structure.
- @param[in] LogicalBlock Block that will be searched
- @return Pointer to the found EXT4_EXTENT_INDEX, else NULL if the array is empty.
- Note: The caller must check if the logical block
- is actually mapped under the given extent.
- **/
- STATIC
- EXT4_EXTENT *
- Ext4BinsearchExtentExt (
- IN EXT4_EXTENT_HEADER *Header,
- IN EXT4_BLOCK_NR LogicalBlock
- )
- {
- EXT4_EXTENT *l;
- EXT4_EXTENT *r;
- EXT4_EXTENT *m;
- l = ((EXT4_EXTENT *)(Header + 1)) + 1;
- r = ((EXT4_EXTENT *)(Header + 1)) + Header->eh_entries - 1;
- // Perform a mostly-standard binary search on the array
- // This works very nicely because the extents arrays are always sorted.
- // Empty array
- if (Header->eh_entries == 0) {
- return NULL;
- }
- while (l <= r) {
- m = l + (r - l) / 2;
- if (LogicalBlock < m->ee_block) {
- r = m - 1;
- } else {
- l = m + 1;
- }
- }
- return l - 1;
- }
- /**
- Retrieves the leaf block from an EXT4_EXTENT_INDEX.
- @param[in] Index Pointer to the EXT4_EXTENT_INDEX structure.
- @return Block number of the leaf node.
- **/
- STATIC
- EXT4_BLOCK_NR
- Ext4ExtentIdxLeafBlock (
- IN EXT4_EXTENT_INDEX *Index
- )
- {
- return LShiftU64 (Index->ei_leaf_hi, 32) | Index->ei_leaf_lo;
- }
- /**
- Retrieves an extent from an EXT4 inode.
- @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 successful.
- @retval EFI_NO_MAPPING Block has no mapping.
- **/
- EFI_STATUS
- Ext4GetExtent (
- IN EXT4_PARTITION *Partition,
- IN EXT4_FILE *File,
- IN EXT4_BLOCK_NR LogicalBlock,
- OUT EXT4_EXTENT *Extent
- )
- {
- EXT4_INODE *Inode;
- VOID *Buffer;
- EXT4_EXTENT *Ext;
- UINT32 CurrentDepth;
- EXT4_EXTENT_HEADER *ExtHeader;
- EXT4_EXTENT_INDEX *Index;
- EFI_STATUS Status;
- EXT4_BLOCK_NR BlockNumber;
- Inode = File->Inode;
- Ext = NULL;
- Buffer = NULL;
- DEBUG ((DEBUG_FS, "[ext4] Looking up extent for block %lu\n", LogicalBlock));
- // ext4 does not have support for logical block numbers bigger than UINT32_MAX
- if (LogicalBlock > (UINT32)-1) {
- return EFI_NO_MAPPING;
- }
- // Note: Right now, holes are the single biggest reason for cache misses
- // We should find a way to get (or cache) holes
- if ((Ext = Ext4GetExtentFromMap (File, (UINT32)LogicalBlock)) != NULL) {
- *Extent = *Ext;
- return EFI_SUCCESS;
- }
- if ((Inode->i_flags & EXT4_EXTENTS_FL) == 0) {
- // If this is an older ext2/ext3 filesystem, emulate Ext4GetExtent using the block map
- // By specification files using block maps are limited to 2^32 blocks,
- // so we can safely cast LogicalBlock to uint32
- Status = Ext4GetBlocks (Partition, File, (UINT32)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);
- if (!Ext4ExtentHeaderValid (ExtHeader)) {
- return EFI_VOLUME_CORRUPTED;
- }
- CurrentDepth = ExtHeader->eh_depth;
- while (ExtHeader->eh_depth != 0) {
- CurrentDepth--;
- // While depth != 0, we're traversing the tree itself and not any leaves
- // As such, every entry is an EXT4_EXTENT_INDEX entry
- // Note: Entries after the extent header, either index or actual extent, are always sorted.
- // Therefore, we can use binary search, and it's actually the standard for doing so
- // (see FreeBSD).
- Index = Ext4BinsearchExtentIndex (ExtHeader, LogicalBlock);
- BlockNumber = Ext4ExtentIdxLeafBlock (Index);
- // Check that block isn't file hole
- if (BlockNumber == EXT4_BLOCK_FILE_HOLE) {
- if (Buffer != NULL) {
- FreePool (Buffer);
- }
- return EFI_VOLUME_CORRUPTED;
- }
- if (Buffer == NULL) {
- Buffer = AllocatePool (Partition->BlockSize);
- if (Buffer == NULL) {
- return EFI_OUT_OF_RESOURCES;
- }
- }
- // Read the leaf block onto the previously-allocated buffer.
- Status = Ext4ReadBlocks (Partition, Buffer, 1, BlockNumber);
- if (EFI_ERROR (Status)) {
- FreePool (Buffer);
- return Status;
- }
- ExtHeader = Buffer;
- if (!Ext4ExtentHeaderValid (ExtHeader)) {
- FreePool (Buffer);
- return EFI_VOLUME_CORRUPTED;
- }
- if (!Ext4CheckExtentChecksum (ExtHeader, File)) {
- DEBUG ((DEBUG_ERROR, "[ext4] Invalid extent checksum\n"));
- FreePool (Buffer);
- return EFI_VOLUME_CORRUPTED;
- }
- if (ExtHeader->eh_depth != CurrentDepth) {
- FreePool (Buffer);
- return EFI_VOLUME_CORRUPTED;
- }
- }
- /* We try to cache every extent under a single leaf, since it's quite likely that we
- * may need to access things sequentially. Furthermore, ext4 block allocation as done
- * by linux (and possibly other systems) is quite fancy and usually it results in a small number of extents.
- * Therefore, we shouldn't have any memory issues.
- **/
- Ext4CacheExtents (File, (EXT4_EXTENT *)(ExtHeader + 1), ExtHeader->eh_entries);
- Ext = Ext4BinsearchExtentExt (ExtHeader, LogicalBlock);
- if (!Ext) {
- if (Buffer != NULL) {
- FreePool (Buffer);
- }
- return EFI_NO_MAPPING;
- }
- if (!((LogicalBlock >= Ext->ee_block) && (Ext->ee_block + Ext4GetExtentLength (Ext) > LogicalBlock))) {
- // This extent does not cover the block
- if (Buffer != NULL) {
- FreePool (Buffer);
- }
- return EFI_NO_MAPPING;
- }
- *Extent = *Ext;
- if (Buffer != NULL) {
- FreePool (Buffer);
- }
- return EFI_SUCCESS;
- }
- /**
- Compare two EXT4_EXTENT structs.
- Used in the extent map's ORDERED_COLLECTION.
- @param[in] UserStruct1 Pointer to the first user structure.
- @param[in] UserStruct2 Pointer to the second user structure.
- @retval <0 If UserStruct1 compares less than UserStruct2.
- @retval 0 If UserStruct1 compares equal to UserStruct2.
- @retval >0 If UserStruct1 compares greater than UserStruct2.
- **/
- STATIC
- INTN
- EFIAPI
- Ext4ExtentsMapStructCompare (
- IN CONST VOID *UserStruct1,
- IN CONST VOID *UserStruct2
- )
- {
- CONST EXT4_EXTENT *Extent1;
- CONST EXT4_EXTENT *Extent2;
- Extent1 = UserStruct1;
- Extent2 = UserStruct2;
- return Extent1->ee_block < Extent2->ee_block ? -1 :
- Extent1->ee_block > Extent2->ee_block ? 1 : 0;
- }
- /**
- Compare a standalone key against a EXT4_EXTENT containing an embedded key.
- Used in the extent map's ORDERED_COLLECTION.
- @param[in] StandaloneKey Pointer to the bare key.
- @param[in] UserStruct Pointer to the user structure with the embedded
- key.
- @retval <0 If StandaloneKey compares less than UserStruct's key.
- @retval 0 If StandaloneKey compares equal to UserStruct's key.
- @retval >0 If StandaloneKey compares greater than UserStruct's key.
- **/
- STATIC
- INTN
- EFIAPI
- Ext4ExtentsMapKeyCompare (
- IN CONST VOID *StandaloneKey,
- IN CONST VOID *UserStruct
- )
- {
- CONST EXT4_EXTENT *Extent;
- UINT32 Block;
- // Note that logical blocks are 32-bits in size so no truncation can happen here
- // with regards to 32-bit architectures.
- Extent = UserStruct;
- Block = (UINT32)(UINTN)StandaloneKey;
- if ((Block >= Extent->ee_block) && (Block - Extent->ee_block < Ext4GetExtentLength (Extent))) {
- return 0;
- }
- return Block < Extent->ee_block ? -1 :
- Block > Extent->ee_block ? 1 : 0;
- }
- /**
- Initialises the (empty) extents map, that will work as a cache of extents.
- @param[in] File Pointer to the open file.
- @return Result of the operation.
- **/
- EFI_STATUS
- Ext4InitExtentsMap (
- IN EXT4_FILE *File
- )
- {
- File->ExtentsMap = OrderedCollectionInit (Ext4ExtentsMapStructCompare, Ext4ExtentsMapKeyCompare);
- if (!File->ExtentsMap) {
- return EFI_OUT_OF_RESOURCES;
- }
- return EFI_SUCCESS;
- }
- /**
- Frees the extents map, deleting every extent stored.
- @param[in] File Pointer to the open file.
- **/
- VOID
- Ext4FreeExtentsMap (
- IN EXT4_FILE *File
- )
- {
- // Keep calling Min(), so we get an arbitrary node we can delete.
- // If Min() returns NULL, it's empty.
- ORDERED_COLLECTION_ENTRY *MinEntry;
- EXT4_EXTENT *Ext;
- MinEntry = NULL;
- while ((MinEntry = OrderedCollectionMin (File->ExtentsMap)) != NULL) {
- OrderedCollectionDelete (File->ExtentsMap, MinEntry, (VOID **)&Ext);
- FreePool (Ext);
- }
- ASSERT (OrderedCollectionIsEmpty (File->ExtentsMap));
- OrderedCollectionUninit (File->ExtentsMap);
- File->ExtentsMap = NULL;
- }
- /**
- Caches a range of extents, by allocating pool memory for each extent and adding it to the tree.
- @param[in] File Pointer to the open file.
- @param[in] Extents Pointer to an array of extents.
- @param[in] NumberExtents Length of the array.
- **/
- VOID
- Ext4CacheExtents (
- IN EXT4_FILE *File,
- IN CONST EXT4_EXTENT *Extents,
- IN UINT16 NumberExtents
- )
- {
- UINT16 Idx;
- EXT4_EXTENT *Extent;
- EFI_STATUS Status;
- /* Note that any out of memory condition might mean we don't get to cache a whole leaf of extents
- * in which case, future insertions might fail.
- */
- for (Idx = 0; Idx < NumberExtents; Idx++, Extents++) {
- Extent = AllocatePool (sizeof (EXT4_EXTENT));
- if (Extent == NULL) {
- return;
- }
- CopyMem (Extent, Extents, sizeof (EXT4_EXTENT));
- Status = OrderedCollectionInsert (File->ExtentsMap, NULL, Extent);
- // EFI_ALREADY_STARTED = already exists in the tree.
- if (EFI_ERROR (Status)) {
- FreePool (Extent);
- if (Status == EFI_ALREADY_STARTED) {
- continue;
- }
- return;
- }
- }
- }
- /**
- Gets an extent from the extents cache of the file.
- @param[in] File Pointer to the open file.
- @param[in] Block Block we want to grab.
- @return Pointer to the extent, or NULL if it was not found.
- **/
- EXT4_EXTENT *
- Ext4GetExtentFromMap (
- IN EXT4_FILE *File,
- IN UINT32 Block
- )
- {
- ORDERED_COLLECTION_ENTRY *Entry;
- Entry = OrderedCollectionFind (File->ExtentsMap, (CONST VOID *)(UINTN)Block);
- if (Entry == NULL) {
- return NULL;
- }
- return OrderedCollectionUserStruct (Entry);
- }
- /**
- Calculates the checksum of the extent data block.
- @param[in] ExtHeader Pointer to the EXT4_EXTENT_HEADER.
- @param[in] File Pointer to the file.
- @return The checksum.
- **/
- UINT32
- Ext4CalculateExtentChecksum (
- IN CONST EXT4_EXTENT_HEADER *ExtHeader,
- IN CONST EXT4_FILE *File
- )
- {
- UINT32 Csum;
- EXT4_PARTITION *Partition;
- EXT4_INODE *Inode;
- Partition = File->Partition;
- Inode = File->Inode;
- Csum = Ext4CalculateChecksum (Partition, &File->InodeNum, sizeof (EXT4_INO_NR), Partition->InitialSeed);
- Csum = Ext4CalculateChecksum (Partition, &Inode->i_generation, sizeof (Inode->i_generation), Csum);
- Csum = Ext4CalculateChecksum (Partition, ExtHeader, Partition->BlockSize - sizeof (EXT4_EXTENT_TAIL), Csum);
- return Csum;
- }
- /**
- Checks if the checksum of the extent data block is correct.
- @param[in] ExtHeader Pointer to the EXT4_EXTENT_HEADER.
- @param[in] File Pointer to the file.
- @return TRUE if the checksum is correct, FALSE if there is corruption.
- **/
- BOOLEAN
- Ext4CheckExtentChecksum (
- IN CONST EXT4_EXTENT_HEADER *ExtHeader,
- IN CONST EXT4_FILE *File
- )
- {
- EXT4_PARTITION *Partition;
- EXT4_EXTENT_TAIL *Tail;
- Partition = File->Partition;
- if (!EXT4_HAS_METADATA_CSUM (Partition)) {
- return TRUE;
- }
- Tail = (EXT4_EXTENT_TAIL *)((CONST CHAR8 *)ExtHeader + (Partition->BlockSize - 4));
- return Tail->eb_checksum == Ext4CalculateExtentChecksum (ExtHeader, File);
- }
- /**
- Retrieves the extent's length, dealing with uninitialized extents in the process.
- @param[in] Extent Pointer to the EXT4_EXTENT
- @returns Extent's length, in filesystem blocks.
- **/
- EXT4_BLOCK_NR
- Ext4GetExtentLength (
- IN CONST EXT4_EXTENT *Extent
- )
- {
- // If it's an uninitialized extent, the true length is ee_len - 2^15
- if (EXT4_EXTENT_IS_UNINITIALIZED (Extent)) {
- return Extent->ee_len - EXT4_EXTENT_MAX_INITIALIZED;
- }
- return Extent->ee_len;
- }
|