| blob | 4414743b638e82972daab8946b4c4fea4bb7ae7c |
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /*
3 * alloc.c
4 *
5 * Extent allocs and frees
6 *
7 * Copyright (C) 2002, 2004 Oracle. All rights reserved.
8 */
10 #include <linux/fs.h>
11 #include <linux/types.h>
12 #include <linux/slab.h>
13 #include <linux/highmem.h>
14 #include <linux/swap.h>
15 #include <linux/quotaops.h>
16 #include <linux/blkdev.h>
17 #include <linux/sched/signal.h>
19 #include <cluster/masklog.h>
44 CONTIG_LEFT,
45 CONTIG_RIGHT,
46 CONTIG_LEFTRIGHT,
47 };
49 static enum ocfs2_contig_type
53 /*
54 * Operations for a specific extent tree type.
55 *
56 * To implement an on-disk btree (extent tree) type in ocfs2, add
57 * an ocfs2_extent_tree_operations structure and the matching
58 * ocfs2_init_<thingy>_extent_tree() function. That's pretty much it
59 * for the allocation portion of the extent tree.
60 */
62 /*
63 * last_eb_blk is the block number of the right most leaf extent
64 * block. Most on-disk structures containing an extent tree store
65 * this value for fast access. The ->eo_set_last_eb_blk() and
66 * ->eo_get_last_eb_blk() operations access this value. They are
67 * both required.
68 */
70 u64 blkno);
73 /*
74 * The on-disk structure usually keeps track of how many total
75 * clusters are stored in this extent tree. This function updates
76 * that value. new_clusters is the delta, and must be
77 * added to the total. Required.
78 */
80 u32 new_clusters);
82 /*
83 * If this extent tree is supported by an extent map, insert
84 * a record into the map.
85 */
89 /*
90 * If this extent tree is supported by an extent map, truncate the
91 * map to clusters,
92 */
94 u32 clusters);
96 /*
97 * If ->eo_insert_check() exists, it is called before rec is
98 * inserted into the extent tree. It is optional.
99 */
104 /*
105 * --------------------------------------------------------------
106 * The remaining are internal to ocfs2_extent_tree and don't have
107 * accessor functions
108 */
110 /*
111 * ->eo_fill_root_el() takes et->et_object and sets et->et_root_el.
112 * It is required.
113 */
116 /*
117 * ->eo_fill_max_leaf_clusters sets et->et_max_leaf_clusters if
118 * it exists. If it does not, et->et_max_leaf_clusters is set
119 * to 0 (unlimited). Optional.
120 */
123 /*
124 * ->eo_extent_contig test whether the 2 ocfs2_extent_rec
125 * are contiguous or not. Optional. Don't need to set it if use
126 * ocfs2_extent_rec as the tree leaf.
127 */
128 enum ocfs2_contig_type
132 };
135 /*
136 * Pre-declare ocfs2_dinode_et_ops so we can use it as a sanity check
137 * in the methods.
138 */
141 u64 blkno);
143 u32 clusters);
147 u32 clusters);
168 };
171 u64 blkno)
172 {
177 }
180 {
185 }
188 u32 clusters)
189 {
197 }
201 {
205 }
208 u32 clusters)
209 {
213 }
217 {
224 "Device %s, asking for sparse allocation: inode %llu, "
231 }
234 {
241 }
244 {
248 }
252 {
256 }
259 u64 blkno)
260 {
264 }
267 {
271 }
274 u32 clusters)
275 {
279 }
286 };
289 {
293 }
296 {
300 }
303 u64 blkno)
304 {
309 }
312 {
317 }
320 u32 clusters)
321 {
325 }
333 };
336 u64 blkno)
337 {
341 }
344 {
348 }
351 u32 clusters)
352 {
356 }
359 {
365 }
368 {
372 }
380 };
383 {
387 }
390 u64 blkno)
391 {
395 }
398 {
402 }
405 u32 clusters)
406 {
410 }
412 static enum ocfs2_contig_type
416 {
418 }
426 };
431 ocfs2_journal_access_func access,
434 {
447 else
449 }
454 {
457 }
462 {
465 }
470 {
473 }
478 {
481 }
486 {
489 }
492 u64 new_last_eb_blk)
493 {
495 }
498 {
500 }
503 u32 clusters)
504 {
506 }
510 {
513 }
516 u32 clusters)
517 {
520 }
525 {
527 type);
528 }
534 {
541 }
545 {
551 }
554 {
560 }
568 /*
569 * Reset the actual path elements so that we can reuse the structure
570 * to build another path. Generally, this involves freeing the buffer
571 * heads.
572 */
574 {
587 }
589 /*
590 * Tree depth may change during truncate, or insert. If we're
591 * keeping the root extent list, then make sure that our path
592 * structure reflects the proper depth.
593 */
596 else
600 }
603 {
607 }
608 }
610 /*
611 * All the elements of src into dest. After this call, src could be freed
612 * without affecting dest.
613 *
614 * Both paths should have the same root. Any non-root elements of dest
615 * will be freed.
616 */
618 {
633 }
634 }
636 /*
637 * Make the *dest path the same as src and re-initialize src path to
638 * have a root only.
639 */
641 {
655 }
656 }
658 /*
659 * Insert an extent block at given index.
660 *
661 * This will not take an additional reference on eb_bh.
662 */
665 {
668 /*
669 * Right now, no root bh is an extent block, so this helps
670 * catch code errors with dinode trees. The assertion can be
671 * safely removed if we ever need to insert extent block
672 * structures at the root.
673 */
678 }
682 ocfs2_journal_access_func access)
683 {
695 }
698 }
701 {
704 }
707 {
710 }
712 /*
713 * Journal the buffer at depth idx. All idx>0 are extent_blocks,
714 * otherwise it's the root_access function.
715 *
716 * I don't like the way this function's name looks next to
717 * ocfs2_journal_access_path(), but I don't have a better one.
718 */
723 {
733 OCFS2_JOURNAL_ACCESS_WRITE);
734 }
736 /*
737 * Convenience function to journal all components in a path.
738 */
742 {
753 }
754 }
756 out:
758 }
760 /*
761 * Return the index of the extent record which contains cluster #v_cluster.
762 * -1 is returned if it was not found.
763 *
764 * Should work fine on interior and exterior nodes.
765 */
767 {
784 }
785 }
788 }
790 /*
791 * NOTE: ocfs2_block_extent_contig(), ocfs2_extents_adjacent() and
792 * ocfs2_extent_rec_contig only work properly against leaf nodes!
793 */
796 u64 blkno)
797 {
804 }
808 {
809 u32 left_range;
815 }
817 static enum ocfs2_contig_type
821 {
824 /*
825 * Refuse to coalesce extent records with different flag
826 * fields - we don't want to mix unwritten extents with user
827 * data.
828 */
842 }
844 /*
845 * NOTE: We can have pretty much any combination of contiguousness and
846 * appending.
847 *
848 * The usefulness of APPEND_TAIL is more in that it lets us know that
849 * we'll have to update the path to that leaf.
850 */
853 APPEND_TAIL,
854 };
858 SPLIT_LEFT,
859 SPLIT_RIGHT,
860 };
868 };
874 };
878 {
887 /*
888 * If the ecc fails, we return the error but otherwise
889 * leave the filesystem running. We know any error is
890 * local to this block.
891 */
897 }
899 /*
900 * Errors after here are fatal.
901 */
909 }
917 }
924 bail:
926 }
930 {
935 ocfs2_validate_extent_block);
937 /* If ocfs2_read_block() got us a new bh, pass it up. */
942 }
945 /*
946 * How many free extents have we got before we need more meta data?
947 */
949 {
965 }
968 }
977 }
980 bail:
985 }
987 /* expects array to already be allocated
988 *
989 * sets h_signature, h_blkno, h_suballoc_bit, h_suballoc_slot, and
990 * l_count for you
991 */
997 {
999 u16 suballoc_bit_start;
1000 u32 num_got;
1009 meta_ac,
1018 }
1026 }
1031 OCFS2_JOURNAL_ACCESS_CREATE);
1035 }
1039 /* Ok, setup the minimal stuff here. */
1050 suballoc_bit_start++;
1051 first_blkno++;
1053 /* We'll also be dirtied by the caller, so
1054 * this isn't absolutely necessary. */
1056 }
1059 }
1062 bail:
1067 }
1068 }
1070 }
1072 /*
1073 * Helper function for ocfs2_add_branch() and ocfs2_shift_tree_depth().
1074 *
1075 * Returns the sum of the rightmost extent rec logical offset and
1076 * cluster count.
1077 *
1078 * ocfs2_add_branch() uses this to determine what logical cluster
1079 * value should be populated into the leftmost new branch records.
1080 *
1081 * ocfs2_shift_tree_depth() uses this to determine the # clusters
1082 * value for the new topmost tree record.
1083 */
1085 {
1092 }
1094 /*
1095 * Change range of the branches in the right most path according to the leaf
1096 * extent block's rightmost record.
1097 */
1100 {
1110 }
1116 }
1122 }
1128 }
1135 out:
1138 }
1140 /*
1141 * Add an entire tree branch to our inode. eb_bh is the extent block
1142 * to start at, if we don't want to start the branch at the root
1143 * structure.
1144 *
1145 * last_eb_bh is required as we have to update it's next_leaf pointer
1146 * for the new last extent block.
1147 *
1148 * the new branch will be 'empty' in the sense that every block will
1149 * contain a single record with cluster count == 0.
1150 */
1156 {
1174 /* we never add a branch to a leaf. */
1183 /*
1184 * If there is a gap before the root end and the real end
1185 * of the rightmost leaf block, we need to remove the gap
1186 * between new_cpos and root_end first so that the tree
1187 * is consistent after we add a new branch(it will start
1188 * from new_cpos).
1189 */
1200 }
1201 }
1203 /* allocate the number of new eb blocks we need */
1205 GFP_KERNEL);
1210 }
1212 /* Firstyly, try to reuse dealloc since we have already estimated how
1213 * many extent blocks we may use.
1214 */
1222 }
1223 }
1231 meta_ac,
1236 }
1237 }
1239 /* Note: new_eb_bhs[new_blocks - 1] is the guy which will be
1240 * linked with the rest of the tree.
1241 * conversely, new_eb_bhs[0] is the new bottommost leaf.
1242 *
1243 * when we leave the loop, new_last_eb_blk will point to the
1244 * newest leaf, and next_blkno will point to the topmost extent
1245 * block. */
1250 /* ocfs2_create_new_meta_bhs() should create it right! */
1255 OCFS2_JOURNAL_ACCESS_CREATE);
1259 }
1264 /*
1265 * This actually counts as an empty extent as
1266 * c_clusters == 0
1267 */
1270 /*
1271 * eb_el isn't always an interior node, but even leaf
1272 * nodes want a zero'd flags and reserved field so
1273 * this gets the whole 32 bits regardless of use.
1274 */
1281 }
1283 /* This is a bit hairy. We want to update up to three blocks
1284 * here without leaving any of them in an inconsistent state
1285 * in case of error. We don't have to worry about
1286 * journal_dirty erroring as it won't unless we've aborted the
1287 * handle (in which case we would never be here) so reserving
1288 * the write with journal_access is all we need to do. */
1290 OCFS2_JOURNAL_ACCESS_WRITE);
1294 }
1296 OCFS2_JOURNAL_ACCESS_WRITE);
1300 }
1303 OCFS2_JOURNAL_ACCESS_WRITE);
1307 }
1308 }
1310 /* Link the new branch into the rest of the tree (el will
1311 * either be on the root_bh, or the extent block passed in. */
1318 /* fe needs a new last extent block pointer, as does the
1319 * next_leaf on the previously last-extent-block. */
1330 /*
1331 * Some callers want to track the rightmost leaf so pass it
1332 * back here.
1333 */
1339 bail:
1344 }
1347 }
1349 /*
1350 * adds another level to the allocation tree.
1351 * returns back the new extent block so you can add a branch to it
1352 * after this call.
1353 */
1358 {
1360 u32 new_clusters;
1376 }
1381 }
1384 /* ocfs2_create_new_meta_bhs() should create it right! */
1391 OCFS2_JOURNAL_ACCESS_CREATE);
1395 }
1397 /* copy the root extent list data into the new extent block */
1406 OCFS2_JOURNAL_ACCESS_WRITE);
1410 }
1414 /* update root_bh now */
1423 /* If this is our 1st tree depth shift, then last_eb_blk
1424 * becomes the allocated extent block */
1433 bail:
1437 }
1439 /*
1440 * Should only be called when there is no space left in any of the
1441 * leaf nodes. What we want to do is find the lowest tree depth
1442 * non-leaf extent block with room for new records. There are three
1443 * valid results of this search:
1444 *
1445 * 1) a lowest extent block is found, then we pass it back in
1446 * *lowest_eb_bh and return '0'
1447 *
1448 * 2) the search fails to find anything, but the root_el has room. We
1449 * pass NULL back in *lowest_eb_bh, but still return '0'
1450 *
1451 * 3) the search fails to find anything AND the root_el is full, in
1452 * which case we return > 0
1453 *
1454 * return status < 0 indicates an error.
1455 */
1458 {
1460 u64 blkno;
1476 }
1484 }
1493 }
1503 }
1504 }
1506 /* If we didn't find one and the fe doesn't have any room,
1507 * then return '1' */
1513 bail:
1517 }
1519 /*
1520 * Grow a b-tree so that it has more records.
1521 *
1522 * We might shift the tree depth in which case existing paths should
1523 * be considered invalid.
1524 *
1525 * Tree depth after the grow is returned via *final_depth.
1526 *
1527 * *last_eb_bh will be updated by ocfs2_add_branch().
1528 */
1532 {
1545 }
1547 /* We traveled all the way to the bottom of the allocation tree
1548 * and didn't find room for any more extents - we need to add
1549 * another tree level */
1555 depth);
1557 /* ocfs2_shift_tree_depth will return us a buffer with
1558 * the new extent block (so we can pass that to
1559 * ocfs2_add_branch). */
1564 }
1565 depth++;
1567 /*
1568 * Special case: we have room now if we shifted from
1569 * tree_depth 0, so no more work needs to be done.
1570 *
1571 * We won't be calling add_branch, so pass
1572 * back *last_eb_bh as the new leaf. At depth
1573 * zero, it should always be null so there's
1574 * no reason to brelse.
1575 */
1580 }
1581 }
1583 /* call ocfs2_add_branch to add the final part of the tree with
1584 * the new data. */
1586 meta_ac);
1590 out:
1595 }
1597 /*
1598 * This function will discard the rightmost extent record.
1599 */
1601 {
1607 /* This will cause us to go off the end of our extent list. */
1613 }
1617 {
1627 /* The tree code before us didn't allow enough room in the leaf. */
1630 /*
1631 * The easiest way to approach this is to just remove the
1632 * empty extent and temporarily decrement next_free.
1633 */
1635 /*
1636 * If next_free was 1 (only an empty extent), this
1637 * loop won't execute, which is fine. We still want
1638 * the decrement above to happen.
1639 */
1643 next_free--;
1644 }
1646 /*
1647 * Figure out what the new record index should be.
1648 */
1654 }
1665 /*
1666 * No need to memmove if we're just adding to the tail.
1667 */
1675 num_bytes);
1676 }
1678 /*
1679 * Either we had an empty extent, and need to re-increment or
1680 * there was no empty extent on a non full rightmost leaf node,
1681 * in which case we still need to increment.
1682 */
1683 next_free++;
1685 /*
1686 * Make sure none of the math above just messed up our tree.
1687 */
1692 }
1695 {
1701 num_recs--;
1707 }
1708 }
1710 /*
1711 * Create an empty extent record .
1712 *
1713 * l_next_free_rec may be updated.
1714 *
1715 * If an empty extent already exists do nothing.
1716 */
1718 {
1737 set_and_inc:
1740 }
1742 /*
1743 * For a rotation which involves two leaf nodes, the "root node" is
1744 * the lowest level tree node which contains a path to both leafs. This
1745 * resulting set of information can be used to form a complete "subtree"
1746 *
1747 * This function is passed two full paths from the dinode down to a
1748 * pair of adjacent leaves. It's task is to figure out which path
1749 * index contains the subtree root - this can be the root index itself
1750 * in a worst-case rotation.
1751 *
1752 * The array index of the subtree root is passed back.
1753 */
1757 {
1760 /*
1761 * Check that the caller passed in two paths from the same tree.
1762 */
1766 i++;
1768 /*
1769 * The caller didn't pass two adjacent paths.
1770 */
1782 }
1786 /*
1787 * Traverse a btree path in search of cpos, starting at root_el.
1788 *
1789 * This code can be called with a cpos larger than the tree, in which
1790 * case it will return the rightmost path.
1791 */
1795 {
1797 u32 range;
1798 u64 blkno;
1814 }
1819 /*
1820 * In the case that cpos is off the allocation
1821 * tree, this should just wind up returning the
1822 * rightmost record.
1823 */
1828 }
1838 }
1846 }
1861 }
1865 }
1867 out:
1868 /*
1869 * Catch any trailing bh that the loop didn't handle.
1870 */
1874 }
1876 /*
1877 * Given an initialized path (that is, it has a valid root extent
1878 * list), this function will traverse the btree in search of the path
1879 * which would contain cpos.
1880 *
1881 * The path traveled is recorded in the path structure.
1882 *
1883 * Note that this will not do any comparisons on leaf node extent
1884 * records, so it will work fine in the case that we just added a tree
1885 * branch.
1886 */
1890 };
1892 {
1898 }
1901 {
1908 }
1911 {
1916 /* We want to retain only the leaf block. */
1920 }
1921 }
1922 /*
1923 * Find the leaf block in the tree which would contain cpos. No
1924 * checking of the actual leaf is done.
1925 *
1926 * Some paths want to call this instead of allocating a path structure
1927 * and calling ocfs2_find_path().
1928 *
1929 * This function doesn't handle non btree extent lists.
1930 */
1934 {
1942 }
1945 out:
1947 }
1949 /*
1950 * Adjust the adjacent records (left_rec, right_rec) involved in a rotation.
1951 *
1952 * Basically, we've moved stuff around at the bottom of the tree and
1953 * we need to fix up the extent records above the changes to reflect
1954 * the new changes.
1955 *
1956 * left_rec: the record on the left.
1957 * right_rec: the record to the right of left_rec
1958 * right_child_el: is the child list pointed to by right_rec
1959 *
1960 * By definition, this only works on interior nodes.
1961 */
1965 {
1968 /*
1969 * Interior nodes never have holes. Their cpos is the cpos of
1970 * the leftmost record in their child list. Their cluster
1971 * count covers the full theoretical range of their child list
1972 * - the range between their cpos and the cpos of the record
1973 * immediately to their right.
1974 */
1980 }
1984 /*
1985 * Calculate the rightmost cluster count boundary before
1986 * moving cpos - we will need to adjust clusters after
1987 * updating e_cpos to keep the same highest cluster count.
1988 */
1997 }
1999 /*
2000 * Adjust the adjacent root node records involved in a
2001 * rotation. left_el_blkno is passed in as a key so that we can easily
2002 * find it's index in the root list.
2003 */
2007 u64 left_el_blkno)
2008 {
2017 }
2019 /*
2020 * The path walking code should have never returned a root and
2021 * two paths which are not adjacent.
2022 */
2027 }
2029 /*
2030 * We've changed a leaf block (in right_path) and need to reflect that
2031 * change back up the subtree.
2032 *
2033 * This happens in multiple places:
2034 * - When we've moved an extent record from the left path leaf to the right
2035 * path leaf to make room for an empty extent in the left path leaf.
2036 * - When our insert into the right path leaf is at the leftmost edge
2037 * and requires an update of the path immediately to it's left. This
2038 * can occur at the end of some types of rotation and appending inserts.
2039 * - When we've adjusted the last extent record in the left path leaf and the
2040 * 1st extent record in the right path leaf during cross extent block merge.
2041 */
2046 {
2052 /*
2053 * Update the counts and position values within all the
2054 * interior nodes to reflect the leaf rotation we just did.
2055 *
2056 * The root node is handled below the loop.
2057 *
2058 * We begin the loop with right_el and left_el pointing to the
2059 * leaf lists and work our way up.
2060 *
2061 * NOTE: within this loop, left_el and right_el always refer
2062 * to the *child* lists.
2063 */
2069 /*
2070 * One nice property of knowing that all of these
2071 * nodes are below the root is that we only deal with
2072 * the leftmost right node record and the rightmost
2073 * left node record.
2074 */
2087 /*
2088 * Setup our list pointers now so that the current
2089 * parents become children in the next iteration.
2090 */
2093 }
2095 /*
2096 * At the root node, adjust the two adjacent records which
2097 * begin our path to the leaves.
2098 */
2110 }
2117 {
2135 }
2137 /*
2138 * This extent block may already have an empty record, so we
2139 * return early if so.
2140 */
2148 subtree_index);
2152 }
2160 }
2167 }
2168 }
2173 /* This is a code error, not a disk corruption. */
2183 /* Do the copy now. */
2188 /*
2189 * Clear out the record we just copied and shift everything
2190 * over, leaving an empty extent in the left leaf.
2191 *
2192 * We temporarily subtract from next_free_rec so that the
2193 * shift will lose the tail record (which is now defunct).
2194 */
2203 subtree_index);
2205 out:
2207 }
2209 /*
2210 * Given a full path, determine what cpos value would return us a path
2211 * containing the leaf immediately to the left of the current one.
2212 *
2213 * Will return zero if the path passed in is already the leftmost path.
2214 */
2217 {
2219 u64 blkno;
2228 /* Start at the tree node just above the leaf and work our way up. */
2233 /*
2234 * Find the extent record just before the one in our
2235 * path.
2236 */
2241 /*
2242 * We've determined that the
2243 * path specified is already
2244 * the leftmost one - return a
2245 * cpos of zero.
2246 */
2248 }
2249 /*
2250 * The leftmost record points to our
2251 * leaf - we need to travel up the
2252 * tree one level.
2253 */
2255 }
2262 }
2263 }
2265 /*
2266 * If we got here, we never found a valid node where
2267 * the tree indicated one should be.
2268 */
2274 next_node:
2276 i--;
2277 }
2279 out:
2281 }
2283 /*
2284 * Extend the transaction by enough credits to complete the rotation,
2285 * and still leave at least the original number of credits allocated
2286 * to this transaction.
2287 */
2291 {
2300 }
2302 /*
2303 * Trap the case where we're inserting into the theoretical range past
2304 * the _actual_ left leaf range. Otherwise, we'll rotate a record
2305 * whose cpos is less than ours into the right leaf.
2306 *
2307 * It's only necessary to look at the rightmost record of the left
2308 * leaf because the logic that calls us should ensure that the
2309 * theoretical ranges in the path components above the leaves are
2310 * correct.
2311 */
2313 u32 insert_cpos)
2314 {
2326 }
2329 {
2339 /* Empty list. */
2343 }
2349 }
2351 /*
2352 * Rotate all the records in a btree right one record, starting at insert_cpos.
2353 *
2354 * The path to the rightmost leaf should be passed in.
2355 *
2356 * The array is assumed to be large enough to hold an entire path (tree depth).
2357 *
2358 * Upon successful return from this function:
2359 *
2360 * - The 'right_path' array will contain a path to the leaf block
2361 * whose range contains e_cpos.
2362 * - That leaf block will have a single empty extent in list index 0.
2363 * - In the case that the rotation requires a post-insert update,
2364 * *ret_left_path will contain a valid path which can be passed to
2365 * ocfs2_insert_path().
2366 */
2370 u32 insert_cpos,
2373 {
2375 u32 cpos;
2386 }
2392 }
2398 /*
2399 * What we want to do here is:
2400 *
2401 * 1) Start with the rightmost path.
2402 *
2403 * 2) Determine a path to the leaf block directly to the left
2404 * of that leaf.
2405 *
2406 * 3) Determine the 'subtree root' - the lowest level tree node
2407 * which contains a path to both leaves.
2408 *
2409 * 4) Rotate the subtree.
2410 *
2411 * 5) Find the next subtree by considering the left path to be
2412 * the new right path.
2413 *
2414 * The check at the top of this while loop also accepts
2415 * insert_cpos == cpos because cpos is only a _theoretical_
2416 * value to get us the left path - insert_cpos might very well
2417 * be filling that hole.
2418 *
2419 * Stop at a cpos of '0' because we either started at the
2420 * leftmost branch (i.e., a tree with one branch and a
2421 * rotation inside of it), or we've gone as far as we can in
2422 * rotating subtrees.
2423 */
2434 }
2438 "Owner %llu: error during insert of %u "
2439 "(left path cpos %u) results in two identical "
2448 insert_cpos)) {
2450 /*
2451 * We've rotated the tree as much as we
2452 * should. The rest is up to
2453 * ocfs2_insert_path() to complete, after the
2454 * record insertion. We indicate this
2455 * situation by returning the left path.
2456 *
2457 * The reason we don't adjust the records here
2458 * before the record insert is that an error
2459 * later might break the rule where a parent
2460 * record e_cpos will reflect the actual
2461 * e_cpos of the 1st nonempty record of the
2462 * child list.
2463 */
2466 }
2480 }
2487 }
2491 insert_cpos)) {
2492 /*
2493 * A rotate moves the rightmost left leaf
2494 * record over to the leftmost right leaf
2495 * slot. If we're doing an extent split
2496 * instead of a real insert, then we have to
2497 * check that the extent to be split wasn't
2498 * just moved over. If it was, then we can
2499 * exit here, passing left_path back -
2500 * ocfs2_split_extent() is smart enough to
2501 * search both leaves.
2502 */
2505 }
2507 /*
2508 * There is no need to re-read the next right path
2509 * as we know that it'll be our current left
2510 * path. Optimize by copying values instead.
2511 */
2518 }
2519 }
2521 out:
2524 out_ret_path:
2526 }
2531 {
2536 u32 range;
2542 }
2544 /* Path should always be rightmost. */
2563 }
2564 out:
2566 }
2572 {
2582 /*
2583 * Not all nodes might have had their final count
2584 * decremented by the caller - handle this here.
2585 */
2589 "Inode %llu, attempted to remove extent block "
2598 }
2610 }
2611 }
2619 {
2644 }
2653 {
2671 /*
2672 * It's legal for us to proceed if the right leaf is
2673 * the rightmost one and it has an empty extent. There
2674 * are two cases to handle - whether the leaf will be
2675 * empty after removal or not. If the leaf isn't empty
2676 * then just remove the empty extent up front. The
2677 * next block will handle empty leaves by flagging
2678 * them for unlink.
2679 *
2680 * Non rightmost leaves will throw -EAGAIN and the
2681 * caller can manually move the subtree and retry.
2682 */
2690 OCFS2_JOURNAL_ACCESS_WRITE);
2694 }
2699 }
2703 /*
2704 * We have to update i_last_eb_blk during the meta
2705 * data delete.
2706 */
2708 OCFS2_JOURNAL_ACCESS_WRITE);
2712 }
2715 }
2717 /*
2718 * Getting here with an empty extent in the right path implies
2719 * that it's the rightmost path and will be deleted.
2720 */
2724 subtree_index);
2728 }
2736 }
2743 }
2744 }
2747 /*
2748 * Only do this if we're moving a real
2749 * record. Otherwise, the action is delayed until
2750 * after removal of the right path in which case we
2751 * can do a simple shift to remove the empty extent.
2752 */
2756 }
2758 /*
2759 * Move recs over to get rid of empty extent, decrease
2760 * next_free. This is allowed to remove the last
2761 * extent in our leaf (setting l_next_free_rec to
2762 * zero) - the delete code below won't care.
2763 */
2765 }
2777 }
2782 /*
2783 * Removal of the extent in the left leaf was skipped
2784 * above so we could delete the right path
2785 * 1st.
2786 */
2795 subtree_index);
2797 out:
2799 }
2801 /*
2802 * Given a full path, determine what cpos value would return us a path
2803 * containing the leaf immediately to the right of the current one.
2804 *
2805 * Will return zero if the path passed in is already the rightmost path.
2806 *
2807 * This looks similar, but is subtly different to
2808 * ocfs2_find_cpos_for_left_leaf().
2809 */
2812 {
2814 u64 blkno;
2824 /* Start at the tree node just above the leaf and work our way up. */
2831 /*
2832 * Find the extent record just after the one in our
2833 * path.
2834 */
2840 /*
2841 * We've determined that the
2842 * path specified is already
2843 * the rightmost one - return a
2844 * cpos of zero.
2845 */
2847 }
2848 /*
2849 * The rightmost record points to our
2850 * leaf - we need to travel up the
2851 * tree one level.
2852 */
2854 }
2858 }
2859 }
2861 /*
2862 * If we got here, we never found a valid node where
2863 * the tree indicated one should be.
2864 */
2870 next_node:
2872 i--;
2873 }
2875 out:
2877 }
2882 {
2895 }
2900 out:
2902 }
2910 {
2912 u32 right_cpos;
2926 }
2933 }
2942 }
2949 }
2952 right_path);
2964 }
2966 /*
2967 * Caller might still want to make changes to the
2968 * tree root, so re-add it to the journal here.
2969 */
2975 }
2981 /*
2982 * The rotation has to temporarily stop due to
2983 * the right subtree having an empty
2984 * extent. Pass it back to the caller for a
2985 * fixup.
2986 */
2990 }
2994 }
2996 /*
2997 * The subtree rotate might have removed records on
2998 * the rightmost edge. If so, then rotation is
2999 * complete.
3000 */
3011 }
3012 }
3014 out:
3019 }
3025 {
3027 u32 cpos;
3040 }
3047 }
3050 /*
3051 * We have a path to the left of this one - it needs
3052 * an update too.
3053 */
3059 }
3065 }
3071 }
3081 }
3086 /*
3087 * 'path' is also the leftmost path which
3088 * means it must be the only one. This gets
3089 * handled differently because we want to
3090 * revert the root back to having extents
3091 * in-line.
3092 */
3101 }
3105 out:
3108 }
3114 {
3124 }
3132 }
3134 /*
3135 * Left rotation of btree records.
3136 *
3137 * In many ways, this is (unsurprisingly) the opposite of right
3138 * rotation. We start at some non-rightmost path containing an empty
3139 * extent in the leaf block. The code works its way to the rightmost
3140 * path by rotating records to the left in every subtree.
3141 *
3142 * This is used by any code which reduces the number of extent records
3143 * in a leaf. After removal, an empty record should be placed in the
3144 * leftmost list position.
3145 *
3146 * This won't handle a length update of the rightmost path records if
3147 * the rightmost tree leaf record is removed so the caller is
3148 * responsible for detecting and correcting that.
3149 */
3154 {
3165 rightmost_no_delete:
3166 /*
3167 * Inline extents. This is trivially handled, so do
3168 * it up front.
3169 */
3174 }
3176 /*
3177 * Handle rightmost branch now. There's several cases:
3178 * 1) simple rotation leaving records in there. That's trivial.
3179 * 2) rotation requiring a branch delete - there's no more
3180 * records left. Two cases of this:
3181 * a) There are branches to the left.
3182 * b) This is also the leftmost (the only) branch.
3183 *
3184 * 1) is handled via ocfs2_rotate_rightmost_leaf_left()
3185 * 2a) we need the left branch so that we can update it with the unlink
3186 * 2b) we need to bring the root back to inline extents.
3187 */
3192 /*
3193 * This gets a bit tricky if we're going to delete the
3194 * rightmost path. Get the other cases out of the way
3195 * 1st.
3196 */
3206 }
3208 /*
3209 * XXX: The caller can not trust "path" any more after
3210 * this as it will have been deleted. What do we do?
3211 *
3212 * In theory the rotate-for-merge code will never get
3213 * here because it'll always ask for a rotate in a
3214 * nonempty list.
3215 */
3218 dealloc);
3222 }
3224 /*
3225 * Now we can loop, remembering the path we get from -EAGAIN
3226 * and restarting from there.
3227 */
3228 try_rotate:
3234 }
3246 }
3253 }
3255 out:
3259 }
3263 {
3268 /*
3269 * We consumed all of the merged-from record. An empty
3270 * extent cannot exist anywhere but the 1st array
3271 * position, so move things over if the merged-from
3272 * record doesn't occupy that position.
3273 *
3274 * This creates a new empty extent so the caller
3275 * should be smart enough to have removed any existing
3276 * ones.
3277 */
3282 }
3284 /*
3285 * Always memset - the caller doesn't check whether it
3286 * created an empty extent, so there could be junk in
3287 * the other fields.
3288 */
3290 }
3291 }
3296 {
3298 u32 right_cpos;
3304 /* This function shouldn't be called for non-trees. */
3315 }
3317 /* This function shouldn't be called for the rightmost leaf. */
3325 }
3331 }
3334 out:
3338 }
3340 /*
3341 * Remove split_rec clusters from the record at index and merge them
3342 * onto the beginning of the record "next" to it.
3343 * For index < l_count - 1, the next means the extent rec at index + 1.
3344 * For index == l_count - 1, the "next" means the 1st extent rec of the
3345 * next extent block.
3346 */
3352 {
3369 /* we meet with a cross extent block merge. */
3374 }
3383 }
3390 right_path);
3394 right_path);
3398 }
3404 subtree_index);
3408 }
3417 }
3424 }
3425 }
3430 }
3437 }
3444 split_clusters));
3453 subtree_index);
3454 }
3455 out:
3458 }
3463 {
3465 u32 left_cpos;
3470 /* This function shouldn't be called for non-trees. */
3478 }
3480 /* This function shouldn't be called for the leftmost leaf. */
3488 }
3494 }
3497 out:
3501 }
3503 /*
3504 * Remove split_rec clusters from the record at index and merge them
3505 * onto the tail of the record "before" it.
3506 * For index > 0, the "before" means the extent rec at index - 1.
3507 *
3508 * For index == 0, the "before" means the last record of the previous
3509 * extent block. And there is also a situation that we may need to
3510 * remove the rightmost leaf extent block in the right_path and change
3511 * the right path to indicate the new rightmost path.
3512 */
3519 {
3534 /* we meet with a cross extent block merge. */
3539 }
3552 right_path);
3556 left_path);
3560 }
3566 subtree_index);
3570 }
3579 }
3586 }
3587 }
3592 }
3599 }
3602 /*
3603 * The easy case - we can just plop the record right in.
3604 */
3612 split_clusters));
3621 /*
3622 * In the situation that the right_rec is empty and the extent
3623 * block is empty also, ocfs2_complete_edge_insert can't handle
3624 * it and we need to delete the right extent block.
3625 */
3628 /* extend credit for ocfs2_remove_rightmost_path */
3631 right_path);
3635 }
3638 right_path,
3639 dealloc);
3643 }
3645 /* Now the rightmost extent block has been deleted.
3646 * So we use the new rightmost path.
3647 */
3653 }
3654 out:
3657 }
3666 {
3674 /* extend credit for ocfs2_remove_rightmost_path */
3677 path);
3681 }
3682 /*
3683 * The merge code will need to create an empty
3684 * extent to take the place of the newly
3685 * emptied slot. Remove any pre-existing empty
3686 * extents - having more than one in a leaf is
3687 * illegal.
3688 */
3693 }
3694 split_index--;
3696 }
3699 /*
3700 * Left-right contig implies this.
3701 */
3704 /*
3705 * Since the leftright insert always covers the entire
3706 * extent, this call will delete the insert record
3707 * entirely, resulting in an empty extent record added to
3708 * the extent block.
3709 *
3710 * Since the adding of an empty extent shifts
3711 * everything back to the right, there's no need to
3712 * update split_index here.
3713 *
3714 * When the split_index is zero, we need to merge it to the
3715 * previous extent block. It is more efficient and easier
3716 * if we do merge_right first and merge_left later.
3717 */
3719 split_index);
3723 }
3725 /*
3726 * We can only get this from logic error above.
3727 */
3730 /* extend credit for ocfs2_remove_rightmost_path */
3733 path);
3737 }
3739 /* The merge left us with an empty extent, remove it. */
3744 }
3748 /*
3749 * Note that we don't pass split_rec here on purpose -
3750 * we've merged it into the rec already.
3751 */
3758 }
3760 /* extend credit for ocfs2_remove_rightmost_path */
3763 path);
3767 }
3770 /*
3771 * Error from this last rotate is not critical, so
3772 * print but don't bubble it up.
3773 */
3778 /*
3779 * Merge a record to the left or right.
3780 *
3781 * 'contig_type' is relative to the existing record,
3782 * so for example, if we're "right contig", it's to
3783 * the record on the left (hence the left merge).
3784 */
3788 split_index);
3792 }
3796 split_index);
3800 }
3801 }
3804 /* extend credit for ocfs2_remove_rightmost_path */
3807 path);
3812 }
3814 /*
3815 * The merge may have left an empty extent in
3816 * our leaf. Try to rotate it away.
3817 */
3819 dealloc);
3823 }
3824 }
3826 out:
3828 }
3834 {
3835 u64 len_blocks;
3841 /*
3842 * Region is on the left edge of the existing
3843 * record.
3844 */
3851 /*
3852 * Region is on the right edge of the existing
3853 * record.
3854 */
3857 }
3858 }
3860 /*
3861 * Do the final bits of extent record insertion at the target leaf
3862 * list. If this leaf is part of an allocation tree, it is assumed
3863 * that the tree above has been prepared.
3864 */
3869 {
3882 insert_rec);
3884 }
3886 /*
3887 * Contiguous insert - either left or right.
3888 */
3894 }
3898 }
3900 /*
3901 * Handle insert into an empty leaf.
3902 */
3909 }
3911 /*
3912 * Appending insert.
3913 */
3923 "owner %llu, depth %u, count %u, next free %u, "
3924 "rec.cpos %u, rec.clusters %u, "
3934 i++;
3938 }
3940 rotate:
3941 /*
3942 * Ok, we have to rotate.
3943 *
3944 * At this point, it is safe to assume that inserting into an
3945 * empty leaf and appending to a leaf have both been handled
3946 * above.
3947 *
3948 * This leaf needs to have space, either by the empty 1st
3949 * extent record, or by virtue of an l_next_free_rec < l_count.
3950 */
3952 }
3958 {
3964 /*
3965 * Update everything except the leaf block.
3966 */
3977 }
3988 }
3989 }
3996 {
4003 /*
4004 * This shouldn't happen for non-trees. The extent rec cluster
4005 * count manipulation below only works for interior nodes.
4006 */
4009 /*
4010 * If our appending insert is at the leftmost edge of a leaf,
4011 * then we might need to update the rightmost records of the
4012 * neighboring path.
4013 */
4018 u32 left_cpos;
4025 }
4031 left_cpos);
4033 /*
4034 * No need to worry if the append is already in the
4035 * leftmost leaf.
4036 */
4043 }
4046 left_cpos);
4050 }
4052 /*
4053 * ocfs2_insert_path() will pass the left_path to the
4054 * journal for us.
4055 */
4056 }
4057 }
4063 }
4069 out:
4074 }
4081 {
4098 /*
4099 * This typically means that the record
4100 * started in the left path but moved to the
4101 * right as a result of rotation. We either
4102 * move the existing record to the left, or we
4103 * do the later insert there.
4104 *
4105 * In this case, the left path should always
4106 * exist as the rotate code will have passed
4107 * it back for a post-insert update.
4108 */
4111 /*
4112 * It's a left split. Since we know
4113 * that the rotate code gave us an
4114 * empty extent in the left path, we
4115 * can just do the insert there.
4116 */
4119 /*
4120 * Right split - we have to move the
4121 * existing record over to the left
4122 * leaf. The insert will be into the
4123 * newly created empty extent in the
4124 * right leaf.
4125 */
4133 }
4134 }
4138 /*
4139 * Left path is easy - we can just allow the insert to
4140 * happen.
4141 */
4146 }
4152 }
4154 /*
4155 * This function only does inserts on an allocation b-tree. For tree
4156 * depth = 0, ocfs2_insert_at_leaf() is called directly.
4157 *
4158 * right_path is the path we want to do the actual insert
4159 * in. left_path should only be passed in if we need to update that
4160 * portion of the tree after an edge insert.
4161 */
4168 {
4173 /*
4174 * There's a chance that left_path got passed back to
4175 * us without being accounted for in the
4176 * journal. Extend our transaction here to be sure we
4177 * can change those blocks.
4178 */
4183 }
4189 }
4190 }
4192 /*
4193 * Pass both paths to the journal. The majority of inserts
4194 * will be touching all components anyway.
4195 */
4200 }
4203 /*
4204 * We could call ocfs2_insert_at_leaf() for some types
4205 * of splits, but it's easier to just let one separate
4206 * function sort it all out.
4207 */
4211 /*
4212 * Split might have modified either leaf and we don't
4213 * have a guarantee that the later edge insert will
4214 * dirty this for us.
4215 */
4221 insert);
4226 /*
4227 * The rotate code has indicated that we need to fix
4228 * up portions of the tree after the insert.
4229 *
4230 * XXX: Should we extend the transaction here?
4231 */
4233 right_path);
4235 subtree_index);
4236 }
4239 out:
4241 }
4247 {
4249 u32 cpos;
4257 OCFS2_JOURNAL_ACCESS_WRITE);
4261 }
4266 }
4273 }
4275 /*
4276 * Determine the path to start with. Rotations need the
4277 * rightmost path, everything else can go directly to the
4278 * target leaf.
4279 */
4285 }
4291 }
4293 /*
4294 * Rotations and appends need special treatment - they modify
4295 * parts of the tree's above them.
4296 *
4297 * Both might pass back a path immediate to the left of the
4298 * one being inserted to. This will be cause
4299 * ocfs2_insert_path() to modify the rightmost records of
4300 * left_path to account for an edge insert.
4301 *
4302 * XXX: When modifying this code, keep in mind that an insert
4303 * can wind up skipping both of these two special cases...
4304 */
4312 }
4314 /*
4315 * ocfs2_rotate_tree_right() might have extended the
4316 * transaction without re-journaling our tree root.
4317 */
4319 OCFS2_JOURNAL_ACCESS_WRITE);
4323 }
4331 }
4332 }
4339 }
4341 out_update_clusters:
4348 out:
4353 }
4360 {
4384 }
4387 left_cpos);
4398 "Extent block #%llu has an invalid l_next_free_rec of %d. It should have matched the l_count of %d\n",
4403 }
4406 }
4407 }
4409 /*
4410 * We're careful to check for an empty extent record here -
4411 * the merge code will know what to do if it sees one.
4412 */
4419 }
4420 }
4439 }
4456 }
4458 }
4459 }
4470 }
4472 free_right_path:
4474 free_left_path:
4476 exit:
4481 }
4487 {
4495 insert_rec);
4499 }
4500 }
4509 /*
4510 * Caller might want us to limit the size of extents, don't
4511 * calculate contiguousness if we might exceed that limit.
4512 */
4516 }
4517 }
4519 /*
4520 * This should only be called against the rightmost leaf extent list.
4521 *
4522 * ocfs2_figure_appending_type() will figure out whether we'll have to
4523 * insert at the tail of the rightmost leaf.
4524 *
4525 * This should also work against the root extent list for tree's with 0
4526 * depth. If we consider the root extent list to be the rightmost leaf node
4527 * then the logic here makes sense.
4528 */
4532 {
4545 /* Were all records empty? */
4548 }
4559 set_tail_append:
4561 }
4563 /*
4564 * Helper function called at the beginning of an insert.
4565 *
4566 * This computes a few things that are commonly used in the process of
4567 * inserting into the btree:
4568 * - Whether the new extent is contiguous with an existing one.
4569 * - The current tree depth.
4570 * - Whether the insert is an appending one.
4571 * - The total # of free records in the tree.
4572 *
4573 * All of the information is stored on the ocfs2_insert_type
4574 * structure.
4575 */
4581 {
4594 /*
4595 * If we have tree depth, we read in the
4596 * rightmost extent block ahead of time as
4597 * ocfs2_figure_insert_type() and ocfs2_add_branch()
4598 * may want it later.
4599 */
4606 }
4609 }
4611 /*
4612 * Unless we have a contiguous insert, we'll need to know if
4613 * there is room left in our allocation tree for another
4614 * extent record.
4615 *
4616 * XXX: This test is simplistic, we can search for empty
4617 * extent records too.
4618 */
4626 }
4633 }
4635 /*
4636 * In the case that we're inserting past what the tree
4637 * currently accounts for, ocfs2_find_path() will return for
4638 * us the rightmost tree path. This is accounted for below in
4639 * the appending code.
4640 */
4645 }
4649 /*
4650 * Now that we have the path, there's two things we want to determine:
4651 * 1) Contiguousness (also set contig_index if this is so)
4652 *
4653 * 2) Are we doing an append? We can trivially break this up
4654 * into two types of appends: simple record append, or a
4655 * rotate inside the tail leaf.
4656 */
4659 /*
4660 * The insert code isn't quite ready to deal with all cases of
4661 * left contiguousness. Specifically, if it's an insert into
4662 * the 1st record in a leaf, it will require the adjustment of
4663 * cluster count on the last record of the path directly to it's
4664 * left. For now, just catch that case and fool the layers
4665 * above us. This works just fine for tree_depth == 0, which
4666 * is why we allow that above.
4667 */
4672 /*
4673 * Ok, so we can simply compare against last_eb to figure out
4674 * whether the path doesn't exist. This will only happen in
4675 * the case that we're doing a tail append, so maybe we can
4676 * take advantage of that information somehow.
4677 */
4680 /*
4681 * Ok, ocfs2_find_path() returned us the rightmost
4682 * tree path. This might be an appending insert. There are
4683 * two cases:
4684 * 1) We're doing a true append at the tail:
4685 * -This might even be off the end of the leaf
4686 * 2) We're "appending" by rotating in the tail
4687 */
4689 }
4691 out:
4696 else
4699 }
4701 /*
4702 * Insert an extent into a btree.
4703 *
4704 * The caller needs to update the owning btree's cluster count.
4705 */
4708 u32 cpos,
4709 u64 start_blk,
4710 u32 new_clusters,
4711 u8 flags,
4713 {
4733 }
4740 }
4749 meta_ac);
4753 }
4754 }
4756 /* Finally, we can add clusters. This might rotate the tree for us. */
4760 else
4763 bail:
4767 }
4769 /*
4770 * Allocate and add clusters into the extent b-tree.
4771 * The new clusters(clusters_to_add) will be inserted at logical_offset.
4772 * The extent b-tree's root is specified by et, and
4773 * it is not limited to the file storage. Any extent tree can use this
4774 * function if it implements the proper ocfs2_extent_tree.
4775 */
4779 u32 clusters_to_add,
4784 {
4790 u64 block;
4805 }
4807 /* there are two cases which could cause us to EAGAIN in the
4808 * we-need-more-metadata case:
4809 * 1) we haven't reserved *any*
4810 * 2) we are so fragmented, we've needed to add metadata too
4811 * many times. */
4824 }
4832 }
4836 /* reserve our write early -- insert_extent may update the tree root */
4838 OCFS2_JOURNAL_ACCESS_WRITE);
4843 }
4855 }
4866 }
4868 bail:
4873 else
4878 num_bits);
4879 }
4881 leave:
4886 }
4890 u32 cpos,
4892 {
4906 }
4915 {
4925 leftright:
4926 /*
4927 * Store a copy of the record on the stack - it might move
4928 * around as the tree is manipulated below.
4929 */
4939 }
4948 }
4949 }
4966 /*
4967 * Left/right split. We fake this as a right split
4968 * first and then make a second pass as a left split.
4969 */
4979 }
4985 }
4988 u32 cpos;
4991 do_leftright++;
5001 }
5009 cpos);
5012 }
5014 }
5015 out:
5018 }
5026 {
5034 }
5039 out:
5041 }
5043 /*
5044 * Split part or all of the extent record at split_index in the leaf
5045 * pointed to by path. Merge with the contiguous extent record if needed.
5046 *
5047 * Care is taken to handle contiguousness so as to not grow the tree.
5048 *
5049 * meta_ac is not strictly necessary - we only truly need it if growth
5050 * of the tree is required. All other cases will degrade into a less
5051 * optimal tree layout.
5052 *
5053 * last_eb_bh should be the rightmost leaf block for any extent
5054 * btree. Since a split may grow the tree or a merge might shrink it,
5055 * the caller cannot trust the contents of that buffer after this call.
5056 *
5057 * This code is optimized for readability - several passes might be
5058 * made over certain portions of the tree. All of those blocks will
5059 * have been brought into cache (and pinned via the journal), so the
5060 * extra overhead is not expressed in terms of disk reads.
5061 */
5069 {
5082 }
5085 split_index,
5086 split_rec,
5091 }
5093 /*
5094 * The core merge / split code wants to know how much room is
5095 * left in this allocation tree, so we pass the
5096 * rightmost extent list.
5097 */
5105 }
5106 }
5111 else
5124 else
5136 }
5138 out:
5141 }
5143 /*
5144 * Change the flags of the already-existing extent at cpos for len clusters.
5145 *
5146 * new_flags: the flags we want to set.
5147 * clear_flags: the flags we want to clear.
5148 * phys: the new physical offset we want this new extent starts from.
5149 *
5150 * If the existing extent is larger than the request, initiate a
5151 * split. An attempt will be made at merging with adjacent extents.
5152 *
5153 * The caller is responsible for passing down meta_ac if we'll need it.
5154 */
5161 {
5175 }
5181 }
5189 cpos);
5192 }
5200 new_flags);
5202 }
5208 clear_flags);
5210 }
5224 dealloc);
5228 out:
5232 }
5234 /*
5235 * Mark the already-existing extent at cpos as written for len clusters.
5236 * This removes the unwritten extent flag.
5237 *
5238 * If the existing extent is larger than the request, initiate a
5239 * split. An attempt will be made at merging with adjacent extents.
5240 *
5241 * The caller is responsible for passing down meta_ac if we'll need it.
5242 */
5248 {
5256 ocfs2_error(inode->i_sb, "Inode %llu has unwritten extents that are being written to, but the feature bit is not set in the super block\n",
5260 }
5262 /*
5263 * XXX: This should be fixed up so that we just re-insert the
5264 * next extent records.
5265 */
5274 out:
5276 }
5282 {
5291 /*
5292 * Setup the record to split before we grow the tree.
5293 */
5307 }
5320 }
5325 meta_ac);
5329 }
5330 }
5342 out:
5345 }
5352 {
5363 /* extend credit for ocfs2_remove_rightmost_path */
5366 path);
5370 }
5376 }
5378 index--;
5379 }
5383 /*
5384 * Check whether this is the rightmost tree record. If
5385 * we remove all of this record or part of its right
5386 * edge then an update of the record lengths above it
5387 * will be required.
5388 */
5392 }
5397 /*
5398 * Changing the leftmost offset (via partial or whole
5399 * record truncate) of an interior (or rightmost) path
5400 * means we have to update the subtree that is formed
5401 * by this leaf and the one to it's left.
5402 *
5403 * There are two cases we can skip:
5404 * 1) Path is the leftmost one in our btree.
5405 * 2) The leaf is rightmost and will be empty after
5406 * we remove the extent record - the rotate code
5407 * knows how to update the newly formed edge.
5408 */
5414 }
5422 }
5425 left_cpos);
5429 }
5430 }
5431 }
5435 path);
5439 }
5445 }
5451 }
5464 /*
5465 * We skip the edge update if this path will
5466 * be deleted by the rotate code.
5467 */
5470 rec);
5471 }
5473 /* Remove leftmost portion of the record. */
5478 /* Remove rightmost portion of the record */
5483 /* Caller should have trapped this. */
5490 }
5497 subtree_index);
5498 }
5506 out:
5509 }
5516 {
5523 /*
5524 * XXX: Why are we truncating to 0 instead of wherever this
5525 * affects us?
5526 */
5534 }
5540 }
5548 cpos);
5551 }
5553 /*
5554 * We have 3 cases of extent removal:
5555 * 1) Range covers the entire extent rec
5556 * 2) Range begins or ends on one edge of the extent rec
5557 * 3) Range is in the middle of the extent rec (no shared edges)
5558 *
5559 * For case 1 we remove the extent rec and left rotate to
5560 * fill the hole.
5561 *
5562 * For case 2 we just shrink the existing extent rec, with a
5563 * tree update if the shrinking edge is also the edge of an
5564 * extent block.
5565 *
5566 * For case 3 we do a right split to turn the extent rec into
5567 * something case 2 can handle.
5568 */
5586 }
5593 }
5595 /*
5596 * The split could have manipulated the tree enough to
5597 * move the record location, so we have to look for it again.
5598 */
5605 }
5613 cpos);
5616 }
5618 /*
5619 * Double check our values here. If anything is fishy,
5620 * it's easier to catch it at the top level.
5621 */
5633 }
5639 }
5641 out:
5644 }
5646 /*
5647 * ocfs2_reserve_blocks_for_rec_trunc() would look basically the
5648 * same as ocfs2_lock_alloctors(), except for it accepts a blocks
5649 * number to reserve some extra blocks, and it only handles meta
5650 * data allocations.
5651 *
5652 * Currently, only ocfs2_remove_btree_range() uses it for truncating
5653 * and punching holes.
5654 */
5657 u32 extents_to_split,
5660 {
5672 }
5683 }
5684 }
5686 out:
5691 }
5692 }
5695 }
5702 {
5720 }
5721 }
5724 refcount_loc,
5725 phys_blkno,
5726 len,
5732 }
5733 }
5736 extra_blocks);
5740 }
5749 }
5750 }
5758 }
5761 OCFS2_JOURNAL_ACCESS_WRITE);
5765 }
5774 }
5785 phys_blkno),
5788 else
5794 }
5796 out_commit:
5798 out:
5800 bail:
5808 }
5811 {
5820 "slot %d, invalid truncate log parameters: used = "
5824 }
5828 {
5832 /* No records, nothing to coalesce */
5841 }
5845 u64 start_blk,
5847 {
5861 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5862 * by the underlying call to ocfs2_read_inode_block(), so any
5863 * corruption is a code bug */
5870 "Truncate record count on #%llu invalid "
5876 /* Caller should have known to flush before calling us. */
5882 }
5885 OCFS2_JOURNAL_ACCESS_WRITE);
5889 }
5895 /*
5896 * Move index back to the record we are coalescing with.
5897 * ocfs2_truncate_log_can_coalesce() guarantees nonzero
5898 */
5899 index--;
5905 num_clusters);
5909 }
5915 bail:
5917 }
5922 {
5926 u64 start_blk;
5943 }
5945 /* Caller has given us at least enough credits to
5946 * update the truncate log dinode */
5948 OCFS2_JOURNAL_ACCESS_WRITE);
5953 }
5964 /* if start_blk is not set, we ignore the record as
5965 * invalid. */
5973 num_clusters);
5978 }
5979 }
5982 i--;
5983 }
5987 bail:
5989 }
5991 /* Expects you to already be holding tl_inode->i_rwsem */
5993 {
6008 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
6009 * by the underlying call to ocfs2_read_inode_block(), so any
6010 * corruption is a code bug */
6017 num_to_flush);
6021 }
6023 /* Appending truncate log(TA) and flushing truncate log(TF) are
6024 * two separated transactions. They can be both committed but not
6025 * checkpointed. If crash occurs then, both two transaction will be
6026 * replayed with several already released to global bitmap clusters.
6027 * Then truncate log will be replayed resulting in cluster double free.
6028 */
6035 }
6038 GLOBAL_BITMAP_SYSTEM_INODE,
6039 OCFS2_INVALID_SLOT);
6044 }
6052 }
6055 data_alloc_bh);
6062 out_mutex:
6066 out:
6068 }
6071 {
6080 }
6083 {
6092 else
6094 }
6096 #define OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL (2 * HZ)
6099 {
6102 /* We want to push off log flushes while truncates are
6103 * still running. */
6108 OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL);
6109 }
6110 }
6112 /*
6113 * Try to flush truncate logs if we can free enough clusters from it.
6114 * As for return value, "< 0" means error, "0" no space and "1" means
6115 * we have freed enough spaces and let the caller try to allocate again.
6116 */
6119 {
6120 tid_t target;
6128 /*
6129 * Check whether we can succeed in allocating if we free
6130 * the truncate log.
6131 */
6139 }
6144 }
6145 out:
6147 }
6153 {
6162 TRUNCATE_LOG_SYSTEM_INODE,
6163 slot_num);
6168 }
6175 }
6187 }
6191 bail:
6193 }
6195 /* called during the 1st stage of node recovery. we stamp a clean
6196 * truncate log and pass back a copy for processing later. if the
6197 * truncate log does not require processing, a *tl_copy is set to
6198 * NULL. */
6202 {
6217 }
6221 /* tl_bh is loaded from ocfs2_get_truncate_log_info(). It's
6222 * validated by the underlying call to ocfs2_read_inode_block(),
6223 * so any corruption is a code bug */
6230 /*
6231 * Assuming the write-out below goes well, this copy will be
6232 * passed back to recovery for processing.
6233 */
6239 }
6241 /* All we need to do to clear the truncate log is set
6242 * tl_used. */
6250 }
6251 }
6253 bail:
6261 }
6264 }
6268 {
6272 u64 start_blk;
6280 }
6286 num_recs);
6295 }
6296 }
6303 }
6315 }
6316 }
6318 bail_up:
6322 }
6325 {
6341 }
6342 }
6345 {
6357 /* ocfs2_truncate_log_shutdown keys on the existence of
6358 * osb->osb_tl_inode so we don't set any of the osb variables
6359 * until we're sure all is well. */
6361 ocfs2_truncate_log_worker);
6367 }
6369 /*
6370 * Delayed de-allocation of suballocator blocks.
6371 *
6372 * Some sets of block de-allocations might involve multiple suballocator inodes.
6373 *
6374 * The locking for this can get extremely complicated, especially when
6375 * the suballocator inodes to delete from aren't known until deep
6376 * within an unrelated codepath.
6377 *
6378 * ocfs2_extent_block structures are a good example of this - an inode
6379 * btree could have been grown by any number of nodes each allocating
6380 * out of their own suballoc inode.
6381 *
6382 * These structures allow the delay of block de-allocation until a
6383 * later time, when locking of multiple cluster inodes won't cause
6384 * deadlock.
6385 */
6387 /*
6388 * Describe a single bit freed from a suballocator. For the block
6389 * suballocators, it represents one block. For the global cluster
6390 * allocator, it represents some clusters and free_bit indicates
6391 * clusters number.
6392 */
6395 u64 free_bg;
6396 u64 free_blk;
6398 };
6405 };
6411 {
6413 u64 bg_blkno;
6424 }
6432 }
6437 else
6445 }
6460 }
6462 out_unlock:
6465 out_mutex:
6468 out:
6470 /* Premature exit may have left some dangling items. */
6474 }
6477 }
6481 {
6490 }
6500 }
6504 {
6518 }
6519 }
6526 }
6539 }
6540 }
6545 /* Premature exit may have left some dangling items. */
6549 }
6552 }
6556 {
6577 }
6581 }
6592 }
6595 }
6601 {
6609 }
6619 }
6621 }
6628 {
6635 }
6638 }
6640 /* If we can't find any free list matching preferred slot, just use
6641 * the first one.
6642 */
6647 }
6649 /* Return Value 1 indicates empty */
6651 {
6665 }
6667 /* If extent was deleted from tree due to extent rotation and merging, and
6668 * no metadata is reserved ahead of time. Try to reuse some extents
6669 * just deleted. This is only used to reuse extent blocks.
6670 * It is supposed to find enough extent blocks in dealloc if our estimation
6671 * on metadata is accurate.
6672 */
6677 {
6688 /* If extent tree doesn't have a dealloc, this is not faulty. Just
6689 * tell upper caller dealloc can't provide any block and it should
6690 * ask for alloc to claim more space.
6691 */
6697 /* Prefer to use local slot */
6700 dealloc);
6701 /* If no more block can be reused, we should claim more
6702 * from alloc. Just return here normally.
6703 */
6707 }
6717 }
6727 OCFS2_JOURNAL_ACCESS_CREATE);
6731 }
6736 /* We can't guarantee that buffer head is still cached, so
6737 * polutlate the extent block again.
6738 */
6748 /* We'll also be dirtied by the caller, so
6749 * this isn't absolutely necessary.
6750 */
6756 }
6758 }
6762 bail:
6766 }
6769 }
6774 {
6784 }
6791 }
6805 out:
6807 }
6811 {
6817 }
6820 {
6824 }
6829 {
6841 /*
6842 * Need to set the buffers we zero'd into uptodate
6843 * here if they aren't - ocfs2_map_page_blocks()
6844 * might've skipped some
6845 */
6848 ocfs2_zero_func);
6856 }
6862 }
6867 {
6888 }
6889 out:
6892 }
6896 {
6900 loff_t last_page_bytes;
6914 }
6917 numfolios++;
6920 out:
6925 }
6930 }
6934 {
6941 }
6943 /*
6944 * Zero partial cluster for a hole punch or truncate. This avoids exposing
6945 * nonzero data on subsequent file extends.
6946 *
6947 * We need to call this before i_size is updated on the inode because
6948 * otherwise block_write_full_folio() will skip writeout of pages past
6949 * i_size.
6950 */
6953 {
6956 u64 phys;
6960 /*
6961 * File systems which don't support sparse files zero on every
6962 * extend.
6963 */
6967 /*
6968 * Avoid zeroing folios fully beyond current i_size. It is pointless as
6969 * underlying blocks of those folios should be already zeroed out and
6970 * page writeback will skip them anyway.
6971 */
6982 }
6990 }
6992 /*
6993 * Tail is a hole, or is marked unwritten. In either case, we
6994 * can count on read and write to return/push zero's.
6995 */
7004 }
7009 /*
7010 * Initiate writeout of the folios we zero'd here. We don't
7011 * wait on them - the truncate_inode_pages() call later will
7012 * do that for us.
7013 */
7019 out:
7023 }
7027 {
7034 xattrsize);
7035 else
7038 }
7042 {
7048 }
7051 {
7060 /*
7061 * We clear the entire i_data structure here so that all
7062 * fields can be properly initialized.
7063 */
7068 }
7072 {
7077 u64 block;
7093 }
7094 }
7102 }
7105 OCFS2_JOURNAL_ACCESS_WRITE);
7109 }
7114 u64 phys;
7129 }
7131 /*
7132 * Save two copies, one for insert, and one that can
7133 * be changed by ocfs2_map_and_dirty_folio() below.
7134 */
7143 }
7145 /*
7146 * This should populate the 1st page for us and mark
7147 * it up to date.
7148 */
7154 }
7158 }
7171 /*
7172 * An error at this point should be extremely rare. If
7173 * this proves to be false, we could always re-build
7174 * the in-inode data from our pages.
7175 */
7182 }
7185 }
7187 out_unlock:
7191 out_commit:
7200 else
7205 num);
7206 }
7210 out:
7214 }
7216 /*
7217 * It is expected, that by the time you call this function,
7218 * inode->i_size and fe->i_size have been adjusted.
7219 *
7220 * WARNING: This will kfree the truncate context
7221 */
7225 {
7246 ocfs2_journal_access_di);
7251 }
7255 start:
7256 /*
7257 * Check that we still have allocation to delete.
7258 */
7262 }
7264 /*
7265 * Truncate always works against the rightmost tree branch.
7266 */
7271 }
7275 new_highest_cpos,
7279 /*
7280 * By now, el will point to the extent list on the bottom most
7281 * portion of this tree. Only the tail record is considered in
7282 * each pass.
7283 *
7284 * We handle the following cases, in order:
7285 * - empty extent: delete the remaining branch
7286 * - remove the entire record
7287 * - remove a partial record
7288 * - no record needs to be removed (truncate has completed)
7289 */
7298 }
7306 /*
7307 * Lower levels depend on this never happening, but it's best
7308 * to check it up here before changing the tree.
7309 */
7319 }
7327 }
7329 /*
7330 * Truncate entire record.
7331 */
7336 /*
7337 * Partial truncate. it also should be
7338 * the last truncate we're doing.
7339 */
7346 /*
7347 * Truncate completed, leave happily.
7348 */
7351 }
7361 }
7362 }
7370 }
7374 /*
7375 * The check above will catch the case where we've truncated
7376 * away all allocation.
7377 */
7380 bail:
7391 }
7393 /*
7394 * 'start' is inclusive, 'end' is not.
7395 */
7398 {
7406 /* No need to punch hole beyond i_size. */
7426 }
7433 }
7436 OCFS2_JOURNAL_ACCESS_WRITE);
7440 }
7445 /*
7446 * No need to worry about the data page here - it's been
7447 * truncated already and inline data doesn't need it for
7448 * pushing zero's to disk, so we'll let read_folio pick it up
7449 * later.
7450 */
7454 }
7465 out_commit:
7468 out:
7470 }
7475 {
7482 /*
7483 * For the first cluster group, the gd->bg_blkno is not at the start
7484 * of the group, but at an offset from the start. If we add it while
7485 * calculating discard for first group, we will wrongly start fstrim a
7486 * few blocks after the desried start block and the range can cross
7487 * over into the next cluster group. So, add it only if this is not
7488 * the first cluster group.
7489 */
7496 }
7501 {
7523 }
7525 }
7531 }
7535 }
7541 }
7543 static
7545 {
7565 next_group:
7567 GLOBAL_BITMAP_SYSTEM_INODE,
7568 OCFS2_INVALID_SLOT);
7573 }
7581 }
7584 /*
7585 * Do some check before trim the first group.
7586 */
7591 }
7596 /*
7597 * Determine first and last group to examine based on
7598 * start and len
7599 */
7603 else
7605 first_group);
7609 }
7614 else
7623 }
7634 }
7641 else
7645 out_unlock:
7649 out_mutex:
7653 /*
7654 * If all the groups trim are not done or failed, but we should release
7655 * main_bm related locks for avoiding the current IO starve, then go to
7656 * trim the next group
7657 */
7661 }
7662 out:
7665 }
7668 {
7683 }
7693 }
7699 /* Avoid sending duplicated trim to a shared device */
7705 }
7706 }
7718 out:
7722 }