Extents.c 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634
  1. /** @file
  2. Extent related routines
  3. Copyright (c) 2021 - 2022 Pedro Falcato All rights reserved.
  4. SPDX-License-Identifier: BSD-2-Clause-Patent
  5. **/
  6. #include "Ext4Dxe.h"
  7. /**
  8. Checks if the checksum of the extent data block is correct.
  9. @param[in] ExtHeader Pointer to the EXT4_EXTENT_HEADER.
  10. @param[in] File Pointer to the file.
  11. @return TRUE if the checksum is correct, FALSE if there is corruption.
  12. **/
  13. BOOLEAN
  14. Ext4CheckExtentChecksum (
  15. IN CONST EXT4_EXTENT_HEADER *ExtHeader,
  16. IN CONST EXT4_FILE *File
  17. );
  18. /**
  19. Calculates the checksum of the extent data block.
  20. @param[in] ExtHeader Pointer to the EXT4_EXTENT_HEADER.
  21. @param[in] File Pointer to the file.
  22. @return The checksum.
  23. **/
  24. UINT32
  25. Ext4CalculateExtentChecksum (
  26. IN CONST EXT4_EXTENT_HEADER *ExtHeader,
  27. IN CONST EXT4_FILE *File
  28. );
  29. /**
  30. Caches a range of extents, by allocating pool memory for each extent and adding it to the tree.
  31. @param[in] File Pointer to the open file.
  32. @param[in] Extents Pointer to an array of extents.
  33. @param[in] NumberExtents Length of the array.
  34. **/
  35. VOID
  36. Ext4CacheExtents (
  37. IN EXT4_FILE *File,
  38. IN CONST EXT4_EXTENT *Extents,
  39. IN UINT16 NumberExtents
  40. );
  41. /**
  42. Gets an extent from the extents cache of the file.
  43. @param[in] File Pointer to the open file.
  44. @param[in] Block Block we want to grab.
  45. @return Pointer to the extent, or NULL if it was not found.
  46. **/
  47. EXT4_EXTENT *
  48. Ext4GetExtentFromMap (
  49. IN EXT4_FILE *File,
  50. IN UINT32 Block
  51. );
  52. /**
  53. Retrieves the pointer to the top of the extent tree.
  54. @param[in] Inode Pointer to the inode structure.
  55. @return Pointer to an EXT4_EXTENT_HEADER. This pointer is inside
  56. the inode and must not be freed.
  57. **/
  58. STATIC
  59. EXT4_EXTENT_HEADER *
  60. Ext4GetInoExtentHeader (
  61. IN EXT4_INODE *Inode
  62. )
  63. {
  64. return (EXT4_EXTENT_HEADER *)Inode->i_data;
  65. }
  66. /**
  67. Checks if an extent header is valid.
  68. @param[in] Header Pointer to the EXT4_EXTENT_HEADER structure.
  69. @return TRUE if valid, FALSE if not.
  70. **/
  71. STATIC
  72. BOOLEAN
  73. Ext4ExtentHeaderValid (
  74. IN CONST EXT4_EXTENT_HEADER *Header
  75. )
  76. {
  77. if (Header->eh_depth > EXT4_EXTENT_TREE_MAX_DEPTH) {
  78. DEBUG ((DEBUG_ERROR, "[ext4] Invalid extent header depth %u\n", Header->eh_depth));
  79. return FALSE;
  80. }
  81. if (Header->eh_magic != EXT4_EXTENT_HEADER_MAGIC) {
  82. DEBUG ((DEBUG_ERROR, "[ext4] Invalid extent header magic %x\n", Header->eh_magic));
  83. return FALSE;
  84. }
  85. if (Header->eh_max < Header->eh_entries) {
  86. DEBUG ((
  87. DEBUG_ERROR,
  88. "[ext4] Invalid extent header num entries %u max entries %u\n",
  89. Header->eh_entries,
  90. Header->eh_max
  91. ));
  92. return FALSE;
  93. }
  94. return TRUE;
  95. }
  96. /**
  97. Performs a binary search for a EXT4_EXTENT_INDEX that corresponds to a
  98. logical block in a given extent tree node.
  99. @param[in] Header Pointer to the EXT4_EXTENT_HEADER structure.
  100. @param[in] LogicalBlock Block that will be searched
  101. @return Pointer to the found EXT4_EXTENT_INDEX.
  102. **/
  103. STATIC
  104. EXT4_EXTENT_INDEX *
  105. Ext4BinsearchExtentIndex (
  106. IN EXT4_EXTENT_HEADER *Header,
  107. IN EXT4_BLOCK_NR LogicalBlock
  108. )
  109. {
  110. EXT4_EXTENT_INDEX *l;
  111. EXT4_EXTENT_INDEX *r;
  112. EXT4_EXTENT_INDEX *m;
  113. l = ((EXT4_EXTENT_INDEX *)(Header + 1)) + 1;
  114. r = ((EXT4_EXTENT_INDEX *)(Header + 1)) + Header->eh_entries - 1;
  115. // Perform a mostly-standard binary search on the array
  116. // This works very nicely because the extents arrays are always sorted.
  117. while (l <= r) {
  118. m = l + (r - l) / 2;
  119. if (LogicalBlock < m->ei_block) {
  120. r = m - 1;
  121. } else {
  122. l = m + 1;
  123. }
  124. }
  125. return l - 1;
  126. }
  127. /**
  128. Performs a binary search for a EXT4_EXTENT that corresponds to a
  129. logical block in a given extent tree node.
  130. @param[in] Header Pointer to the EXT4_EXTENT_HEADER structure.
  131. @param[in] LogicalBlock Block that will be searched
  132. @return Pointer to the found EXT4_EXTENT_INDEX, else NULL if the array is empty.
  133. Note: The caller must check if the logical block
  134. is actually mapped under the given extent.
  135. **/
  136. STATIC
  137. EXT4_EXTENT *
  138. Ext4BinsearchExtentExt (
  139. IN EXT4_EXTENT_HEADER *Header,
  140. IN EXT4_BLOCK_NR LogicalBlock
  141. )
  142. {
  143. EXT4_EXTENT *l;
  144. EXT4_EXTENT *r;
  145. EXT4_EXTENT *m;
  146. l = ((EXT4_EXTENT *)(Header + 1)) + 1;
  147. r = ((EXT4_EXTENT *)(Header + 1)) + Header->eh_entries - 1;
  148. // Perform a mostly-standard binary search on the array
  149. // This works very nicely because the extents arrays are always sorted.
  150. // Empty array
  151. if (Header->eh_entries == 0) {
  152. return NULL;
  153. }
  154. while (l <= r) {
  155. m = l + (r - l) / 2;
  156. if (LogicalBlock < m->ee_block) {
  157. r = m - 1;
  158. } else {
  159. l = m + 1;
  160. }
  161. }
  162. return l - 1;
  163. }
  164. /**
  165. Retrieves the leaf block from an EXT4_EXTENT_INDEX.
  166. @param[in] Index Pointer to the EXT4_EXTENT_INDEX structure.
  167. @return Block number of the leaf node.
  168. **/
  169. STATIC
  170. EXT4_BLOCK_NR
  171. Ext4ExtentIdxLeafBlock (
  172. IN EXT4_EXTENT_INDEX *Index
  173. )
  174. {
  175. return LShiftU64 (Index->ei_leaf_hi, 32) | Index->ei_leaf_lo;
  176. }
  177. /**
  178. Retrieves an extent from an EXT4 inode.
  179. @param[in] Partition Pointer to the opened EXT4 partition.
  180. @param[in] File Pointer to the opened file.
  181. @param[in] LogicalBlock Block number which the returned extent must cover.
  182. @param[out] Extent Pointer to the output buffer, where the extent will be copied to.
  183. @retval EFI_SUCCESS Retrieval was successful.
  184. @retval EFI_NO_MAPPING Block has no mapping.
  185. **/
  186. EFI_STATUS
  187. Ext4GetExtent (
  188. IN EXT4_PARTITION *Partition,
  189. IN EXT4_FILE *File,
  190. IN EXT4_BLOCK_NR LogicalBlock,
  191. OUT EXT4_EXTENT *Extent
  192. )
  193. {
  194. EXT4_INODE *Inode;
  195. VOID *Buffer;
  196. EXT4_EXTENT *Ext;
  197. UINT32 CurrentDepth;
  198. EXT4_EXTENT_HEADER *ExtHeader;
  199. EXT4_EXTENT_INDEX *Index;
  200. EFI_STATUS Status;
  201. EXT4_BLOCK_NR BlockNumber;
  202. Inode = File->Inode;
  203. Ext = NULL;
  204. Buffer = NULL;
  205. DEBUG ((DEBUG_FS, "[ext4] Looking up extent for block %lu\n", LogicalBlock));
  206. // ext4 does not have support for logical block numbers bigger than UINT32_MAX
  207. if (LogicalBlock > (UINT32)-1) {
  208. return EFI_NO_MAPPING;
  209. }
  210. // Note: Right now, holes are the single biggest reason for cache misses
  211. // We should find a way to get (or cache) holes
  212. if ((Ext = Ext4GetExtentFromMap (File, (UINT32)LogicalBlock)) != NULL) {
  213. *Extent = *Ext;
  214. return EFI_SUCCESS;
  215. }
  216. if ((Inode->i_flags & EXT4_EXTENTS_FL) == 0) {
  217. // If this is an older ext2/ext3 filesystem, emulate Ext4GetExtent using the block map
  218. // By specification files using block maps are limited to 2^32 blocks,
  219. // so we can safely cast LogicalBlock to uint32
  220. Status = Ext4GetBlocks (Partition, File, (UINT32)LogicalBlock, Extent);
  221. if (!EFI_ERROR (Status)) {
  222. Ext4CacheExtents (File, Extent, 1);
  223. }
  224. return Status;
  225. }
  226. // Slow path, we'll need to read from disk and (try to) cache those extents.
  227. ExtHeader = Ext4GetInoExtentHeader (Inode);
  228. if (!Ext4ExtentHeaderValid (ExtHeader)) {
  229. return EFI_VOLUME_CORRUPTED;
  230. }
  231. CurrentDepth = ExtHeader->eh_depth;
  232. while (ExtHeader->eh_depth != 0) {
  233. CurrentDepth--;
  234. // While depth != 0, we're traversing the tree itself and not any leaves
  235. // As such, every entry is an EXT4_EXTENT_INDEX entry
  236. // Note: Entries after the extent header, either index or actual extent, are always sorted.
  237. // Therefore, we can use binary search, and it's actually the standard for doing so
  238. // (see FreeBSD).
  239. Index = Ext4BinsearchExtentIndex (ExtHeader, LogicalBlock);
  240. BlockNumber = Ext4ExtentIdxLeafBlock (Index);
  241. // Check that block isn't file hole
  242. if (BlockNumber == EXT4_BLOCK_FILE_HOLE) {
  243. if (Buffer != NULL) {
  244. FreePool (Buffer);
  245. }
  246. return EFI_VOLUME_CORRUPTED;
  247. }
  248. if (Buffer == NULL) {
  249. Buffer = AllocatePool (Partition->BlockSize);
  250. if (Buffer == NULL) {
  251. return EFI_OUT_OF_RESOURCES;
  252. }
  253. }
  254. // Read the leaf block onto the previously-allocated buffer.
  255. Status = Ext4ReadBlocks (Partition, Buffer, 1, BlockNumber);
  256. if (EFI_ERROR (Status)) {
  257. FreePool (Buffer);
  258. return Status;
  259. }
  260. ExtHeader = Buffer;
  261. if (!Ext4ExtentHeaderValid (ExtHeader)) {
  262. FreePool (Buffer);
  263. return EFI_VOLUME_CORRUPTED;
  264. }
  265. if (!Ext4CheckExtentChecksum (ExtHeader, File)) {
  266. DEBUG ((DEBUG_ERROR, "[ext4] Invalid extent checksum\n"));
  267. FreePool (Buffer);
  268. return EFI_VOLUME_CORRUPTED;
  269. }
  270. if (ExtHeader->eh_depth != CurrentDepth) {
  271. FreePool (Buffer);
  272. return EFI_VOLUME_CORRUPTED;
  273. }
  274. }
  275. /* We try to cache every extent under a single leaf, since it's quite likely that we
  276. * may need to access things sequentially. Furthermore, ext4 block allocation as done
  277. * by linux (and possibly other systems) is quite fancy and usually it results in a small number of extents.
  278. * Therefore, we shouldn't have any memory issues.
  279. **/
  280. Ext4CacheExtents (File, (EXT4_EXTENT *)(ExtHeader + 1), ExtHeader->eh_entries);
  281. Ext = Ext4BinsearchExtentExt (ExtHeader, LogicalBlock);
  282. if (!Ext) {
  283. if (Buffer != NULL) {
  284. FreePool (Buffer);
  285. }
  286. return EFI_NO_MAPPING;
  287. }
  288. if (!((LogicalBlock >= Ext->ee_block) && (Ext->ee_block + Ext4GetExtentLength (Ext) > LogicalBlock))) {
  289. // This extent does not cover the block
  290. if (Buffer != NULL) {
  291. FreePool (Buffer);
  292. }
  293. return EFI_NO_MAPPING;
  294. }
  295. *Extent = *Ext;
  296. if (Buffer != NULL) {
  297. FreePool (Buffer);
  298. }
  299. return EFI_SUCCESS;
  300. }
  301. /**
  302. Compare two EXT4_EXTENT structs.
  303. Used in the extent map's ORDERED_COLLECTION.
  304. @param[in] UserStruct1 Pointer to the first user structure.
  305. @param[in] UserStruct2 Pointer to the second user structure.
  306. @retval <0 If UserStruct1 compares less than UserStruct2.
  307. @retval 0 If UserStruct1 compares equal to UserStruct2.
  308. @retval >0 If UserStruct1 compares greater than UserStruct2.
  309. **/
  310. STATIC
  311. INTN
  312. EFIAPI
  313. Ext4ExtentsMapStructCompare (
  314. IN CONST VOID *UserStruct1,
  315. IN CONST VOID *UserStruct2
  316. )
  317. {
  318. CONST EXT4_EXTENT *Extent1;
  319. CONST EXT4_EXTENT *Extent2;
  320. Extent1 = UserStruct1;
  321. Extent2 = UserStruct2;
  322. return Extent1->ee_block < Extent2->ee_block ? -1 :
  323. Extent1->ee_block > Extent2->ee_block ? 1 : 0;
  324. }
  325. /**
  326. Compare a standalone key against a EXT4_EXTENT containing an embedded key.
  327. Used in the extent map's ORDERED_COLLECTION.
  328. @param[in] StandaloneKey Pointer to the bare key.
  329. @param[in] UserStruct Pointer to the user structure with the embedded
  330. key.
  331. @retval <0 If StandaloneKey compares less than UserStruct's key.
  332. @retval 0 If StandaloneKey compares equal to UserStruct's key.
  333. @retval >0 If StandaloneKey compares greater than UserStruct's key.
  334. **/
  335. STATIC
  336. INTN
  337. EFIAPI
  338. Ext4ExtentsMapKeyCompare (
  339. IN CONST VOID *StandaloneKey,
  340. IN CONST VOID *UserStruct
  341. )
  342. {
  343. CONST EXT4_EXTENT *Extent;
  344. UINT32 Block;
  345. // Note that logical blocks are 32-bits in size so no truncation can happen here
  346. // with regards to 32-bit architectures.
  347. Extent = UserStruct;
  348. Block = (UINT32)(UINTN)StandaloneKey;
  349. if ((Block >= Extent->ee_block) && (Block - Extent->ee_block < Ext4GetExtentLength (Extent))) {
  350. return 0;
  351. }
  352. return Block < Extent->ee_block ? -1 :
  353. Block > Extent->ee_block ? 1 : 0;
  354. }
  355. /**
  356. Initialises the (empty) extents map, that will work as a cache of extents.
  357. @param[in] File Pointer to the open file.
  358. @return Result of the operation.
  359. **/
  360. EFI_STATUS
  361. Ext4InitExtentsMap (
  362. IN EXT4_FILE *File
  363. )
  364. {
  365. File->ExtentsMap = OrderedCollectionInit (Ext4ExtentsMapStructCompare, Ext4ExtentsMapKeyCompare);
  366. if (!File->ExtentsMap) {
  367. return EFI_OUT_OF_RESOURCES;
  368. }
  369. return EFI_SUCCESS;
  370. }
  371. /**
  372. Frees the extents map, deleting every extent stored.
  373. @param[in] File Pointer to the open file.
  374. **/
  375. VOID
  376. Ext4FreeExtentsMap (
  377. IN EXT4_FILE *File
  378. )
  379. {
  380. // Keep calling Min(), so we get an arbitrary node we can delete.
  381. // If Min() returns NULL, it's empty.
  382. ORDERED_COLLECTION_ENTRY *MinEntry;
  383. EXT4_EXTENT *Ext;
  384. MinEntry = NULL;
  385. while ((MinEntry = OrderedCollectionMin (File->ExtentsMap)) != NULL) {
  386. OrderedCollectionDelete (File->ExtentsMap, MinEntry, (VOID **)&Ext);
  387. FreePool (Ext);
  388. }
  389. ASSERT (OrderedCollectionIsEmpty (File->ExtentsMap));
  390. OrderedCollectionUninit (File->ExtentsMap);
  391. File->ExtentsMap = NULL;
  392. }
  393. /**
  394. Caches a range of extents, by allocating pool memory for each extent and adding it to the tree.
  395. @param[in] File Pointer to the open file.
  396. @param[in] Extents Pointer to an array of extents.
  397. @param[in] NumberExtents Length of the array.
  398. **/
  399. VOID
  400. Ext4CacheExtents (
  401. IN EXT4_FILE *File,
  402. IN CONST EXT4_EXTENT *Extents,
  403. IN UINT16 NumberExtents
  404. )
  405. {
  406. UINT16 Idx;
  407. EXT4_EXTENT *Extent;
  408. EFI_STATUS Status;
  409. /* Note that any out of memory condition might mean we don't get to cache a whole leaf of extents
  410. * in which case, future insertions might fail.
  411. */
  412. for (Idx = 0; Idx < NumberExtents; Idx++, Extents++) {
  413. Extent = AllocatePool (sizeof (EXT4_EXTENT));
  414. if (Extent == NULL) {
  415. return;
  416. }
  417. CopyMem (Extent, Extents, sizeof (EXT4_EXTENT));
  418. Status = OrderedCollectionInsert (File->ExtentsMap, NULL, Extent);
  419. // EFI_ALREADY_STARTED = already exists in the tree.
  420. if (EFI_ERROR (Status)) {
  421. FreePool (Extent);
  422. if (Status == EFI_ALREADY_STARTED) {
  423. continue;
  424. }
  425. return;
  426. }
  427. }
  428. }
  429. /**
  430. Gets an extent from the extents cache of the file.
  431. @param[in] File Pointer to the open file.
  432. @param[in] Block Block we want to grab.
  433. @return Pointer to the extent, or NULL if it was not found.
  434. **/
  435. EXT4_EXTENT *
  436. Ext4GetExtentFromMap (
  437. IN EXT4_FILE *File,
  438. IN UINT32 Block
  439. )
  440. {
  441. ORDERED_COLLECTION_ENTRY *Entry;
  442. Entry = OrderedCollectionFind (File->ExtentsMap, (CONST VOID *)(UINTN)Block);
  443. if (Entry == NULL) {
  444. return NULL;
  445. }
  446. return OrderedCollectionUserStruct (Entry);
  447. }
  448. /**
  449. Calculates the checksum of the extent data block.
  450. @param[in] ExtHeader Pointer to the EXT4_EXTENT_HEADER.
  451. @param[in] File Pointer to the file.
  452. @return The checksum.
  453. **/
  454. UINT32
  455. Ext4CalculateExtentChecksum (
  456. IN CONST EXT4_EXTENT_HEADER *ExtHeader,
  457. IN CONST EXT4_FILE *File
  458. )
  459. {
  460. UINT32 Csum;
  461. EXT4_PARTITION *Partition;
  462. EXT4_INODE *Inode;
  463. Partition = File->Partition;
  464. Inode = File->Inode;
  465. Csum = Ext4CalculateChecksum (Partition, &File->InodeNum, sizeof (EXT4_INO_NR), Partition->InitialSeed);
  466. Csum = Ext4CalculateChecksum (Partition, &Inode->i_generation, sizeof (Inode->i_generation), Csum);
  467. Csum = Ext4CalculateChecksum (Partition, ExtHeader, Partition->BlockSize - sizeof (EXT4_EXTENT_TAIL), Csum);
  468. return Csum;
  469. }
  470. /**
  471. Checks if the checksum of the extent data block is correct.
  472. @param[in] ExtHeader Pointer to the EXT4_EXTENT_HEADER.
  473. @param[in] File Pointer to the file.
  474. @return TRUE if the checksum is correct, FALSE if there is corruption.
  475. **/
  476. BOOLEAN
  477. Ext4CheckExtentChecksum (
  478. IN CONST EXT4_EXTENT_HEADER *ExtHeader,
  479. IN CONST EXT4_FILE *File
  480. )
  481. {
  482. EXT4_PARTITION *Partition;
  483. EXT4_EXTENT_TAIL *Tail;
  484. Partition = File->Partition;
  485. if (!EXT4_HAS_METADATA_CSUM (Partition)) {
  486. return TRUE;
  487. }
  488. Tail = (EXT4_EXTENT_TAIL *)((CONST CHAR8 *)ExtHeader + (Partition->BlockSize - 4));
  489. return Tail->eb_checksum == Ext4CalculateExtentChecksum (ExtHeader, File);
  490. }
  491. /**
  492. Retrieves the extent's length, dealing with uninitialized extents in the process.
  493. @param[in] Extent Pointer to the EXT4_EXTENT
  494. @returns Extent's length, in filesystem blocks.
  495. **/
  496. EXT4_BLOCK_NR
  497. Ext4GetExtentLength (
  498. IN CONST EXT4_EXTENT *Extent
  499. )
  500. {
  501. // If it's an uninitialized extent, the true length is ee_len - 2^15
  502. if (EXT4_EXTENT_IS_UNINITIALIZED (Extent)) {
  503. return Extent->ee_len - EXT4_EXTENT_MAX_INITIALIZED;
  504. }
  505. return Extent->ee_len;
  506. }