| blob | 10e0cf9949a28738433083975c50ed1cc007f340 |
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3 * Copyright (c) 2014 Red Hat, Inc.
4 * All Rights Reserved.
5 */
25 /*
26 * Lookup the first record less than or equal to [bno, len, owner, offset]
27 * in the btree given by cur.
28 */
29 int
32 xfs_agblock_t bno,
33 xfs_extlen_t len,
38 {
45 }
47 /*
48 * Lookup the record exactly matching [bno, len, owner, offset]
49 * in the btree given by cur.
50 */
51 int
54 xfs_agblock_t bno,
55 xfs_extlen_t len,
60 {
67 }
69 /*
70 * Update the record referred to by cur to the value given
71 * by [bno, len, owner, offset].
72 * This either works (return 0) or gets an EFSCORRUPTED error.
73 */
74 STATIC int
78 {
96 }
98 int
101 xfs_agblock_t agbno,
102 xfs_extlen_t len,
106 {
119 }
132 }
133 done:
138 }
140 STATIC int
143 xfs_agblock_t agbno,
144 xfs_extlen_t len,
148 {
161 }
169 }
170 done:
175 }
177 /* Convert an internal btree record to an rmap record. */
178 int
182 {
187 irec);
188 }
190 /*
191 * Get the data from the pointed-to record.
192 */
193 int
198 {
219 /* check for valid extent range, including overflow */
228 }
236 out_bad_rec:
239 agno);
245 }
251 };
253 /* For each rmap given, figure out if it matches the key we want. */
254 STATIC int
259 {
277 }
279 /*
280 * Find the record to the left of the given extent, being careful only to
281 * return a match with the same owner and adjacent physical and logical
282 * block ranges.
283 */
284 int
287 xfs_agblock_t bno,
293 {
327 }
329 /* For each rmap given, figure out if it matches the key we want. */
330 STATIC int
335 {
354 }
356 /*
357 * Find the record to the left of the given extent, being careful only to
358 * return a match with the same owner and overlapping physical and logical
359 * block ranges. This is the overlapping-interval version of
360 * xfs_rmap_lookup_le.
361 */
362 int
365 xfs_agblock_t bno,
371 {
379 else
399 }
401 /*
402 * Perform all the relevant owner checks for a removal op. If we're doing an
403 * unknown-owner removal then we have no owner information to check.
404 */
405 static int
410 xfs_filblks_t len,
414 {
420 /* Make sure the unwritten flag matches. */
426 }
428 /* Make sure the owner matches what we expect to find in the tree. */
432 }
434 /* Check the offset, if necessary. */
443 }
448 }
453 }
454 }
456 out:
458 }
460 /*
461 * Find the extent in the rmap btree and remove it.
462 *
463 * The record we find should always be an exact match for the extent that we're
464 * looking for, since we insert them into the btree without modification.
465 *
466 * Special Case #1: when growing the filesystem, we "free" an extent when
467 * growing the last AG. This extent is new space and so it is not tracked as
468 * used space in the btree. The growfs code will pass in an owner of
469 * XFS_RMAP_OWN_NULL to indicate that it expected that there is no owner of this
470 * extent. We verify that - the extent lookup result in a record that does not
471 * overlap.
472 *
473 * Special Case #2: EFIs do not record the owner of the extent, so when
474 * recovering EFIs from the log we pass in XFS_RMAP_OWN_UNKNOWN to tell the rmap
475 * btree to ignore the owner (i.e. wildcard match) so we don't trigger
476 * corruption checks during log recovery.
477 */
478 STATIC int
481 xfs_agblock_t bno,
482 xfs_extlen_t len,
485 {
504 /*
505 * We should always have a left record because there's a static record
506 * for the AG headers at rm_startblock == 0 created by mkfs/growfs that
507 * will not ever be removed from the tree.
508 */
515 }
523 }
530 /*
531 * For growfs, the incoming extent must be beyond the left record we
532 * just found as it is new space and won't be used by anyone. This is
533 * just a corruption check as we don't actually do anything with this
534 * extent. Note that we need to use >= instead of > because it might
535 * be the case that the "left" extent goes all the way to EOFS.
536 */
539 bno <
543 }
545 }
547 /*
548 * If we're doing an unknown-owner removal for EFI recovery, we expect
549 * to find the full range in the rmapbt or nothing at all. If we
550 * don't find any rmaps overlapping either end of the range, we're
551 * done. Hopefully this means that the EFI creator already queued
552 * (and finished) a RUI to remove the rmap.
553 */
569 }
572 }
574 /* Make sure the extent we found covers the entire freeing range. */
581 }
583 /* Check owner information. */
590 /* exact match, simply remove the record from rmap tree */
601 }
603 /*
604 * overlap left hand side of extent: move the start, trim the
605 * length and update the current record.
606 *
607 * ltbno ltlen
608 * Orig: |oooooooooooooooooooo|
609 * Freeing: |fffffffff|
610 * Result: |rrrrrrrrrr|
611 * bno len
612 */
621 /*
622 * overlap right hand side of extent: trim the length and update
623 * the current record.
624 *
625 * ltbno ltlen
626 * Orig: |oooooooooooooooooooo|
627 * Freeing: |fffffffff|
628 * Result: |rrrrrrrrrr|
629 * bno len
630 */
637 /*
638 * overlap middle of extent: trim the length of the existing
639 * record to the length of the new left-extent size, increment
640 * the insertion position so we can insert a new record
641 * containing the remaining right-extent space.
642 *
643 * ltbno ltlen
644 * Orig: |oooooooooooooooooooo|
645 * Freeing: |fffffffff|
646 * Result: |rrrrr| |rrrr|
647 * bno len
648 */
666 else
678 }
680 out_done:
683 out_error:
688 }
690 /*
691 * Remove a reference to an extent in the rmap btree.
692 */
693 int
697 xfs_agnumber_t agno,
698 xfs_agblock_t bno,
699 xfs_extlen_t len,
701 {
715 }
717 /*
718 * A mergeable rmap must have the same owner and the same values for
719 * the unwritten, attr_fork, and bmbt flags. The startblock and
720 * offset are checked separately.
721 */
722 static bool
727 {
742 }
744 /*
745 * When we allocate a new block, the first thing we do is add a reference to
746 * the extent in the rmap btree. This takes the form of a [agbno, length,
747 * owner, offset] record. Flags are encoded in the high bits of the offset
748 * field.
749 */
750 STATIC int
753 xfs_agblock_t bno,
754 xfs_extlen_t len,
757 {
780 /*
781 * For the initial lookup, look for an exact match or the left-adjacent
782 * record for our insertion point. This will also give us the record for
783 * start block contiguity tests.
784 */
796 }
804 }
811 }
813 /*
814 * Increment the cursor to see if we have a right-adjacent record to our
815 * insertion point. This will give us the record for end block
816 * contiguity tests.
817 */
828 }
832 }
839 }
841 /*
842 * Note: cursor currently points one record to the right of ltrec, even
843 * if there is no record in the tree to the right.
844 */
848 /*
849 * left edge contiguous, merge into left record.
850 *
851 * ltbno ltlen
852 * orig: |ooooooooo|
853 * adding: |aaaaaaaaa|
854 * result: |rrrrrrrrrrrrrrrrrrr|
855 * bno len
856 */
863 /*
864 * right edge also contiguous, delete right record
865 * and merge into left record.
866 *
867 * ltbno ltlen gtbno gtlen
868 * orig: |ooooooooo| |ooooooooo|
869 * adding: |aaaaaaaaa|
870 * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr|
871 */
885 }
886 }
888 /* point the cursor back to the left record and update */
898 /*
899 * right edge contiguous, merge into right record.
900 *
901 * gtbno gtlen
902 * Orig: |ooooooooo|
903 * adding: |aaaaaaaaa|
904 * Result: |rrrrrrrrrrrrrrrrrrr|
905 * bno len
906 */
915 /*
916 * no contiguous edge with identical owner, insert
917 * new record at current cursor position.
918 */
932 }
933 }
937 out_error:
942 }
944 /*
945 * Add a reference to an extent in the rmap btree.
946 */
947 int
951 xfs_agnumber_t agno,
952 xfs_agblock_t bno,
953 xfs_extlen_t len,
955 {
968 }
970 #define RMAP_LEFT_CONTIG (1 << 0)
971 #define RMAP_RIGHT_CONTIG (1 << 1)
972 #define RMAP_LEFT_FILLING (1 << 2)
973 #define RMAP_RIGHT_FILLING (1 << 3)
974 #define RMAP_LEFT_VALID (1 << 6)
975 #define RMAP_RIGHT_VALID (1 << 7)
977 #define LEFT r[0]
978 #define RIGHT r[1]
979 #define PREV r[2]
980 #define NEW r[3]
982 /*
983 * Convert an unwritten extent to a real extent or vice versa.
984 * Does not handle overlapping extents.
985 */
986 STATIC int
989 xfs_agblock_t bno,
990 xfs_extlen_t len,
993 {
996 /* left is 0, right is 1, */
997 /* prev is 2, new is 3 */
1016 /*
1017 * For the initial lookup, look for an exact match or the left-adjacent
1018 * record for our insertion point. This will also give us the record for
1019 * start block contiguity tests.
1020 */
1027 }
1035 }
1046 /*
1047 * Set flags determining what part of the previous oldext allocation
1048 * extent is being replaced by a newext allocation.
1049 */
1055 /*
1056 * Decrement the cursor to see if we have a left-adjacent record to our
1057 * insertion point. This will give us the record for end block
1058 * contiguity tests.
1059 */
1071 }
1074 bno)) {
1077 }
1086 }
1088 /*
1089 * Increment the cursor to see if we have a right-adjacent record to our
1090 * insertion point. This will give us the record for end block
1091 * contiguity tests.
1092 */
1099 }
1111 }
1115 }
1124 }
1126 /* check that left + prev + right is not too long */
1136 _RET_IP_);
1138 /* reset the cursor back to PREV */
1145 }
1147 /*
1148 * Switch out based on the FILLING and CONTIG state bits.
1149 */
1154 /*
1155 * Setting all of a previous oldext extent to newext.
1156 * The left and right neighbors are both contiguous with new.
1157 */
1164 }
1175 }
1182 }
1193 }
1200 }
1209 /*
1210 * Setting all of a previous oldext extent to newext.
1211 * The left neighbor is contiguous, the right is not.
1212 */
1223 }
1230 }
1239 /*
1240 * Setting all of a previous oldext extent to newext.
1241 * The right neighbor is contiguous, the left is not.
1242 */
1249 }
1260 }
1267 }
1277 /*
1278 * Setting all of a previous oldext extent to newext.
1279 * Neither the left nor right neighbors are contiguous with
1280 * the new one.
1281 */
1290 /*
1291 * Setting the first part of a previous oldext extent to newext.
1292 * The left neighbor is contiguous.
1293 */
1312 /*
1313 * Setting the first part of a previous oldext extent to newext.
1314 * The left neighbor is not contiguous.
1315 */
1337 }
1341 /*
1342 * Setting the last part of a previous oldext extent to newext.
1343 * The right neighbor is contiguous with the new allocation.
1344 */
1363 /*
1364 * Setting the last part of a previous oldext extent to newext.
1365 * The right neighbor is not contiguous.
1366 */
1379 }
1394 }
1398 /*
1399 * Setting the middle part of a previous oldext extent to
1400 * newext. Contiguity is impossible here.
1401 * One extent becomes three extents.
1402 */
1403 /* new right extent - oldext */
1408 new_endoff;
1413 /* new left extent - oldext */
1427 }
1428 /*
1429 * Reset the cursor to the position of the new extent
1430 * we are about to insert as we can't trust it after
1431 * the previous insert.
1432 */
1440 }
1441 /* new middle extent - newext */
1452 }
1462 /*
1463 * These cases are all impossible.
1464 */
1466 }
1470 done:
1475 }
1477 /*
1478 * Convert an unwritten extent to a real extent or vice versa. If there is no
1479 * possibility of overlapping extents, delegate to the simpler convert
1480 * function.
1481 */
1482 STATIC int
1485 xfs_agblock_t bno,
1486 xfs_extlen_t len,
1489 {
1492 /* left is 0, right is 1, */
1493 /* prev is 2, new is 3 */
1512 /*
1513 * For the initial lookup, look for and exact match or the left-adjacent
1514 * record for our insertion point. This will also give us the record for
1515 * start block contiguity tests.
1516 */
1524 }
1531 /*
1532 * Set flags determining what part of the previous oldext allocation
1533 * extent is being replaced by a newext allocation.
1534 */
1540 /* Is there a left record that abuts our range? */
1549 bno)) {
1552 }
1555 }
1557 /* Is there a right record that abuts our range? */
1570 }
1574 }
1581 }
1583 /* check that left + prev + right is not too long */
1593 _RET_IP_);
1594 /*
1595 * Switch out based on the FILLING and CONTIG state bits.
1596 */
1601 /*
1602 * Setting all of a previous oldext extent to newext.
1603 * The left and right neighbors are both contiguous with new.
1604 */
1624 }
1632 /*
1633 * Setting all of a previous oldext extent to newext.
1634 * The left neighbor is contiguous, the right is not.
1635 */
1650 }
1658 /*
1659 * Setting all of a previous oldext extent to newext.
1660 * The right neighbor is contiguous, the left is not.
1661 */
1676 }
1685 /*
1686 * Setting all of a previous oldext extent to newext.
1687 * Neither the left nor right neighbors are contiguous with
1688 * the new one.
1689 */
1699 }
1707 /*
1708 * Setting the first part of a previous oldext extent to newext.
1709 * The left neighbor is contiguous.
1710 */
1734 }
1742 /*
1743 * Setting the first part of a previous oldext extent to newext.
1744 * The left neighbor is not contiguous.
1745 */
1766 /*
1767 * Setting the last part of a previous oldext extent to newext.
1768 * The right neighbor is contiguous with the new allocation.
1769 */
1779 }
1801 /*
1802 * Setting the last part of a previous oldext extent to newext.
1803 * The right neighbor is not contiguous.
1804 */
1814 }
1825 /*
1826 * Setting the middle part of a previous oldext extent to
1827 * newext. Contiguity is impossible here.
1828 * One extent becomes three extents.
1829 */
1830 /* new right extent - oldext */
1835 new_endoff;
1842 /* new left extent - oldext */
1852 }
1857 /* new middle extent - newext */
1877 /*
1878 * These cases are all impossible.
1879 */
1881 }
1885 done:
1890 }
1892 #undef NEW
1893 #undef LEFT
1894 #undef RIGHT
1895 #undef PREV
1897 /*
1898 * Find an extent in the rmap btree and unmap it. For rmap extent types that
1899 * can overlap (data fork rmaps on reflink filesystems) we must be careful
1900 * that the prev/next records in the btree might belong to another owner.
1901 * Therefore we must use delete+insert to alter any of the key fields.
1902 *
1903 * For every other situation there can only be one owner for a given extent,
1904 * so we can call the regular _free function.
1905 */
1906 STATIC int
1909 xfs_agblock_t bno,
1910 xfs_extlen_t len,
1913 {
1929 /*
1930 * We should always have a left record because there's a static record
1931 * for the AG headers at rm_startblock == 0 created by mkfs/growfs that
1932 * will not ever be removed from the tree.
1933 */
1941 }
1944 /* Make sure the extent we found covers the entire freeing range. */
1951 }
1953 /* Make sure the owner matches what we expect to find in the tree. */
1957 }
1959 /* Make sure the unwritten flag matches. */
1965 }
1967 /* Check the offset. */
1971 }
1975 }
1978 /* Exact match, simply remove the record from rmap tree. */
1985 /*
1986 * Overlap left hand side of extent: move the start, trim the
1987 * length and update the current record.
1988 *
1989 * ltbno ltlen
1990 * Orig: |oooooooooooooooooooo|
1991 * Freeing: |fffffffff|
1992 * Result: |rrrrrrrrrr|
1993 * bno len
1994 */
1996 /* Delete prev rmap. */
2003 /* Add an rmap at the new offset. */
2013 /*
2014 * Overlap right hand side of extent: trim the length and
2015 * update the current record.
2016 *
2017 * ltbno ltlen
2018 * Orig: |oooooooooooooooooooo|
2019 * Freeing: |fffffffff|
2020 * Result: |rrrrrrrrrr|
2021 * bno len
2022 */
2031 }
2037 /*
2038 * Overlap middle of extent: trim the length of the existing
2039 * record to the length of the new left-extent size, increment
2040 * the insertion position so we can insert a new record
2041 * containing the remaining right-extent space.
2042 *
2043 * ltbno ltlen
2044 * Orig: |oooooooooooooooooooo|
2045 * Freeing: |fffffffff|
2046 * Result: |rrrrr| |rrrr|
2047 * bno len
2048 */
2051 /* Shrink the left side of the rmap */
2060 }
2066 /* Add an rmap at the new offset */
2073 }
2077 out_error:
2082 }
2084 /*
2085 * Find an extent in the rmap btree and map it. For rmap extent types that
2086 * can overlap (data fork rmaps on reflink filesystems) we must be careful
2087 * that the prev/next records in the btree might belong to another owner.
2088 * Therefore we must use delete+insert to alter any of the key fields.
2089 *
2090 * For every other situation there can only be one owner for a given extent,
2091 * so we can call the regular _alloc function.
2092 */
2093 STATIC int
2096 xfs_agblock_t bno,
2097 xfs_extlen_t len,
2100 {
2118 /* Is there a left record that abuts our range? */
2127 /* Is there a right record that abuts our range? */
2139 }
2147 }
2152 /*
2153 * Left edge contiguous, merge into left record.
2154 *
2155 * ltbno ltlen
2156 * orig: |ooooooooo|
2157 * adding: |aaaaaaaaa|
2158 * result: |rrrrrrrrrrrrrrrrrrr|
2159 * bno len
2160 */
2165 /*
2166 * Right edge also contiguous, delete right record
2167 * and merge into left record.
2168 *
2169 * ltbno ltlen gtbno gtlen
2170 * orig: |ooooooooo| |ooooooooo|
2171 * adding: |aaaaaaaaa|
2172 * result: |rrrrrrrrrrrrrrrrrrrrrrrrrrrrr|
2173 */
2180 }
2182 /* Point the cursor back to the left record and update. */
2191 }
2199 /*
2200 * Right edge contiguous, merge into right record.
2201 *
2202 * gtbno gtlen
2203 * Orig: |ooooooooo|
2204 * adding: |aaaaaaaaa|
2205 * Result: |rrrrrrrrrrrrrrrrrrr|
2206 * bno len
2207 */
2208 /* Delete the old record. */
2215 /* Move the start and re-add it. */
2225 /*
2226 * No contiguous edge with identical owner, insert
2227 * new record at current cursor position.
2228 */
2232 }
2236 out_error:
2241 }
2243 /* Insert a raw rmap into the rmapbt. */
2244 int
2248 {
2269 }
2272 xfs_rmap_query_range_fn fn;
2274 };
2276 /* Format btree record and pass to our callback. */
2277 STATIC int
2282 {
2291 }
2293 /* Find all rmaps between two keys. */
2294 int
2299 xfs_rmap_query_range_fn fn,
2301 {
2312 }
2314 /* Find all rmaps. */
2315 int
2318 xfs_rmap_query_range_fn fn,
2320 {
2326 }
2328 /* Clean up after calling xfs_rmap_finish_one. */
2329 void
2334 {
2343 }
2345 /*
2346 * Process one of the deferred rmap operations. We pass back the
2347 * btree cursor to maintain our lock on the rmapbt between calls.
2348 * This saves time and eliminates a buffer deadlock between the
2349 * superblock and the AGF because we'll always grab them in the same
2350 * order.
2351 */
2352 int
2358 xfs_fileoff_t startoff,
2359 xfs_fsblock_t startblock,
2360 xfs_filblks_t blockcount,
2361 xfs_exntst_t state,
2363 {
2368 xfs_agnumber_t agno;
2370 xfs_agblock_t bno;
2381 XFS_ERRTAG_RMAP_FINISH_ONE))
2384 /*
2385 * If we haven't gotten a cursor or the cursor AG doesn't match
2386 * the startblock, get one now.
2387 */
2393 }
2395 /*
2396 * Refresh the freelist before we start changing the
2397 * rmapbt, because a shape change could cause us to
2398 * allocate blocks.
2399 */
2407 }
2443 }
2445 }
2447 /*
2448 * Don't defer an rmap if we aren't an rmap filesystem.
2449 */
2450 static bool
2454 {
2456 }
2458 /*
2459 * Record a rmap intent; the list is kept sorted first by AG and then by
2460 * increasing age.
2461 */
2462 static void
2469 {
2474 type,
2489 }
2491 /* Map an extent into a file. */
2492 void
2498 {
2508 }
2510 /* Unmap an extent out of a file. */
2511 void
2517 {
2527 }
2529 /*
2530 * Convert a data fork extent from unwritten to real or vice versa.
2531 *
2532 * Note that tp can be NULL here as no transaction is used for COW fork
2533 * unwritten conversion.
2534 */
2535 void
2542 {
2552 }
2554 /* Schedule the creation of an rmap for non-file data. */
2555 void
2558 xfs_agnumber_t agno,
2559 xfs_agblock_t bno,
2560 xfs_extlen_t len,
2562 {
2574 }
2576 /* Schedule the deletion of an rmap for non-file data. */
2577 void
2580 xfs_agnumber_t agno,
2581 xfs_agblock_t bno,
2582 xfs_extlen_t len,
2584 {
2596 }
2598 /* Compare rmap records. Returns -1 if a < b, 1 if a > b, and 0 if equal. */
2599 int
2603 {
2604 __u64 oa;
2605 __u64 ob;
2622 else
2624 }
2626 /* Is there a record covering a given extent? */
2627 int
2630 xfs_agblock_t bno,
2631 xfs_extlen_t len,
2633 {
2643 }
2645 /*
2646 * Is there a record for this owner completely covering a given physical
2647 * extent? If so, *has_rmap will be set to true. If there is no record
2648 * or the record only covers part of the range, we set *has_rmap to false.
2649 * This function doesn't perform range lookups or offset checks, so it is
2650 * not suitable for checking data fork blocks.
2651 */
2652 int
2655 xfs_agblock_t bno,
2656 xfs_extlen_t len,
2659 {
2678 }
2686 }
2691 }
2697 };
2699 /* For each rmap given, figure out if it doesn't match the key we want. */
2700 STATIC int
2705 {
2712 }
2714 /*
2715 * Given an extent and some owner info, can we find records overlapping
2716 * the extent whose owner info does not match the given owner?
2717 */
2718 int
2721 xfs_agblock_t bno,
2722 xfs_extlen_t len,
2725 {
2743 }
2746 }
2750 };
2753 };
2756 };
2759 };
2762 };
2765 };
2768 };
2771 };
2774 };