| blob | 88534eb0e7c2a4e90bba2b6bc75ec5ebc135cc6d |
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /* -*- mode: c; c-basic-offset: 8; -*-
3 * vim: noexpandtab sw=8 ts=8 sts=0:
4 *
5 * alloc.c
6 *
7 * Extent allocs and frees
8 *
9 * Copyright (C) 2002, 2004 Oracle. All rights reserved.
10 */
12 #include <linux/fs.h>
13 #include <linux/types.h>
14 #include <linux/slab.h>
15 #include <linux/highmem.h>
16 #include <linux/swap.h>
17 #include <linux/quotaops.h>
18 #include <linux/blkdev.h>
19 #include <linux/sched/signal.h>
21 #include <cluster/masklog.h>
46 CONTIG_LEFT,
47 CONTIG_RIGHT,
48 CONTIG_LEFTRIGHT,
49 };
51 static enum ocfs2_contig_type
55 /*
56 * Operations for a specific extent tree type.
57 *
58 * To implement an on-disk btree (extent tree) type in ocfs2, add
59 * an ocfs2_extent_tree_operations structure and the matching
60 * ocfs2_init_<thingy>_extent_tree() function. That's pretty much it
61 * for the allocation portion of the extent tree.
62 */
64 /*
65 * last_eb_blk is the block number of the right most leaf extent
66 * block. Most on-disk structures containing an extent tree store
67 * this value for fast access. The ->eo_set_last_eb_blk() and
68 * ->eo_get_last_eb_blk() operations access this value. They are
69 * both required.
70 */
72 u64 blkno);
75 /*
76 * The on-disk structure usually keeps track of how many total
77 * clusters are stored in this extent tree. This function updates
78 * that value. new_clusters is the delta, and must be
79 * added to the total. Required.
80 */
82 u32 new_clusters);
84 /*
85 * If this extent tree is supported by an extent map, insert
86 * a record into the map.
87 */
91 /*
92 * If this extent tree is supported by an extent map, truncate the
93 * map to clusters,
94 */
96 u32 clusters);
98 /*
99 * If ->eo_insert_check() exists, it is called before rec is
100 * inserted into the extent tree. It is optional.
101 */
106 /*
107 * --------------------------------------------------------------
108 * The remaining are internal to ocfs2_extent_tree and don't have
109 * accessor functions
110 */
112 /*
113 * ->eo_fill_root_el() takes et->et_object and sets et->et_root_el.
114 * It is required.
115 */
118 /*
119 * ->eo_fill_max_leaf_clusters sets et->et_max_leaf_clusters if
120 * it exists. If it does not, et->et_max_leaf_clusters is set
121 * to 0 (unlimited). Optional.
122 */
125 /*
126 * ->eo_extent_contig test whether the 2 ocfs2_extent_rec
127 * are contiguous or not. Optional. Don't need to set it if use
128 * ocfs2_extent_rec as the tree leaf.
129 */
130 enum ocfs2_contig_type
134 };
137 /*
138 * Pre-declare ocfs2_dinode_et_ops so we can use it as a sanity check
139 * in the methods.
140 */
143 u64 blkno);
145 u32 clusters);
149 u32 clusters);
170 };
173 u64 blkno)
174 {
179 }
182 {
187 }
190 u32 clusters)
191 {
199 }
203 {
207 }
210 u32 clusters)
211 {
215 }
219 {
226 "Device %s, asking for sparse allocation: inode %llu, "
233 }
236 {
243 }
246 {
250 }
254 {
258 }
261 u64 blkno)
262 {
266 }
269 {
273 }
276 u32 clusters)
277 {
281 }
288 };
291 {
295 }
298 {
302 }
305 u64 blkno)
306 {
311 }
314 {
319 }
322 u32 clusters)
323 {
327 }
335 };
338 u64 blkno)
339 {
343 }
346 {
350 }
353 u32 clusters)
354 {
358 }
361 {
367 }
370 {
374 }
382 };
385 {
389 }
392 u64 blkno)
393 {
397 }
400 {
404 }
407 u32 clusters)
408 {
412 }
414 static enum ocfs2_contig_type
418 {
420 }
428 };
433 ocfs2_journal_access_func access,
436 {
449 else
451 }
456 {
459 }
464 {
467 }
472 {
475 }
480 {
483 }
488 {
491 }
494 u64 new_last_eb_blk)
495 {
497 }
500 {
502 }
505 u32 clusters)
506 {
508 }
512 {
515 }
518 u32 clusters)
519 {
522 }
527 {
529 type);
530 }
536 {
543 }
547 {
553 }
556 {
562 }
570 /*
571 * Reset the actual path elements so that we can re-use the structure
572 * to build another path. Generally, this involves freeing the buffer
573 * heads.
574 */
576 {
589 }
591 /*
592 * Tree depth may change during truncate, or insert. If we're
593 * keeping the root extent list, then make sure that our path
594 * structure reflects the proper depth.
595 */
598 else
602 }
605 {
609 }
610 }
612 /*
613 * All the elements of src into dest. After this call, src could be freed
614 * without affecting dest.
615 *
616 * Both paths should have the same root. Any non-root elements of dest
617 * will be freed.
618 */
620 {
635 }
636 }
638 /*
639 * Make the *dest path the same as src and re-initialize src path to
640 * have a root only.
641 */
643 {
657 }
658 }
660 /*
661 * Insert an extent block at given index.
662 *
663 * This will not take an additional reference on eb_bh.
664 */
667 {
670 /*
671 * Right now, no root bh is an extent block, so this helps
672 * catch code errors with dinode trees. The assertion can be
673 * safely removed if we ever need to insert extent block
674 * structures at the root.
675 */
680 }
684 ocfs2_journal_access_func access)
685 {
697 }
700 }
703 {
706 }
709 {
712 }
714 /*
715 * Journal the buffer at depth idx. All idx>0 are extent_blocks,
716 * otherwise it's the root_access function.
717 *
718 * I don't like the way this function's name looks next to
719 * ocfs2_journal_access_path(), but I don't have a better one.
720 */
725 {
735 OCFS2_JOURNAL_ACCESS_WRITE);
736 }
738 /*
739 * Convenience function to journal all components in a path.
740 */
744 {
755 }
756 }
758 out:
760 }
762 /*
763 * Return the index of the extent record which contains cluster #v_cluster.
764 * -1 is returned if it was not found.
765 *
766 * Should work fine on interior and exterior nodes.
767 */
769 {
786 }
787 }
790 }
792 /*
793 * NOTE: ocfs2_block_extent_contig(), ocfs2_extents_adjacent() and
794 * ocfs2_extent_rec_contig only work properly against leaf nodes!
795 */
798 u64 blkno)
799 {
806 }
810 {
811 u32 left_range;
817 }
819 static enum ocfs2_contig_type
823 {
826 /*
827 * Refuse to coalesce extent records with different flag
828 * fields - we don't want to mix unwritten extents with user
829 * data.
830 */
844 }
846 /*
847 * NOTE: We can have pretty much any combination of contiguousness and
848 * appending.
849 *
850 * The usefulness of APPEND_TAIL is more in that it lets us know that
851 * we'll have to update the path to that leaf.
852 */
855 APPEND_TAIL,
856 };
860 SPLIT_LEFT,
861 SPLIT_RIGHT,
862 };
870 };
876 };
880 {
889 /*
890 * If the ecc fails, we return the error but otherwise
891 * leave the filesystem running. We know any error is
892 * local to this block.
893 */
899 }
901 /*
902 * Errors after here are fatal.
903 */
911 }
919 }
926 bail:
928 }
932 {
937 ocfs2_validate_extent_block);
939 /* If ocfs2_read_block() got us a new bh, pass it up. */
944 }
947 /*
948 * How many free extents have we got before we need more meta data?
949 */
951 {
967 }
970 }
975 bail:
980 }
982 /* expects array to already be allocated
983 *
984 * sets h_signature, h_blkno, h_suballoc_bit, h_suballoc_slot, and
985 * l_count for you
986 */
992 {
994 u16 suballoc_bit_start;
995 u32 num_got;
1004 meta_ac,
1013 }
1021 }
1026 OCFS2_JOURNAL_ACCESS_CREATE);
1030 }
1034 /* Ok, setup the minimal stuff here. */
1045 suballoc_bit_start++;
1046 first_blkno++;
1048 /* We'll also be dirtied by the caller, so
1049 * this isn't absolutely necessary. */
1051 }
1054 }
1057 bail:
1062 }
1064 }
1066 }
1068 /*
1069 * Helper function for ocfs2_add_branch() and ocfs2_shift_tree_depth().
1070 *
1071 * Returns the sum of the rightmost extent rec logical offset and
1072 * cluster count.
1073 *
1074 * ocfs2_add_branch() uses this to determine what logical cluster
1075 * value should be populated into the leftmost new branch records.
1076 *
1077 * ocfs2_shift_tree_depth() uses this to determine the # clusters
1078 * value for the new topmost tree record.
1079 */
1081 {
1088 }
1090 /*
1091 * Change range of the branches in the right most path according to the leaf
1092 * extent block's rightmost record.
1093 */
1096 {
1106 }
1112 }
1118 }
1124 }
1131 out:
1134 }
1136 /*
1137 * Add an entire tree branch to our inode. eb_bh is the extent block
1138 * to start at, if we don't want to start the branch at the root
1139 * structure.
1140 *
1141 * last_eb_bh is required as we have to update it's next_leaf pointer
1142 * for the new last extent block.
1143 *
1144 * the new branch will be 'empty' in the sense that every block will
1145 * contain a single record with cluster count == 0.
1146 */
1152 {
1170 /* we never add a branch to a leaf. */
1179 /*
1180 * If there is a gap before the root end and the real end
1181 * of the righmost leaf block, we need to remove the gap
1182 * between new_cpos and root_end first so that the tree
1183 * is consistent after we add a new branch(it will start
1184 * from new_cpos).
1185 */
1196 }
1197 }
1199 /* allocate the number of new eb blocks we need */
1201 GFP_KERNEL);
1206 }
1208 /* Firstyly, try to reuse dealloc since we have already estimated how
1209 * many extent blocks we may use.
1210 */
1218 }
1219 }
1227 meta_ac,
1232 }
1233 }
1235 /* Note: new_eb_bhs[new_blocks - 1] is the guy which will be
1236 * linked with the rest of the tree.
1237 * conversly, new_eb_bhs[0] is the new bottommost leaf.
1238 *
1239 * when we leave the loop, new_last_eb_blk will point to the
1240 * newest leaf, and next_blkno will point to the topmost extent
1241 * block. */
1246 /* ocfs2_create_new_meta_bhs() should create it right! */
1251 OCFS2_JOURNAL_ACCESS_CREATE);
1255 }
1260 /*
1261 * This actually counts as an empty extent as
1262 * c_clusters == 0
1263 */
1266 /*
1267 * eb_el isn't always an interior node, but even leaf
1268 * nodes want a zero'd flags and reserved field so
1269 * this gets the whole 32 bits regardless of use.
1270 */
1277 }
1279 /* This is a bit hairy. We want to update up to three blocks
1280 * here without leaving any of them in an inconsistent state
1281 * in case of error. We don't have to worry about
1282 * journal_dirty erroring as it won't unless we've aborted the
1283 * handle (in which case we would never be here) so reserving
1284 * the write with journal_access is all we need to do. */
1286 OCFS2_JOURNAL_ACCESS_WRITE);
1290 }
1292 OCFS2_JOURNAL_ACCESS_WRITE);
1296 }
1299 OCFS2_JOURNAL_ACCESS_WRITE);
1303 }
1304 }
1306 /* Link the new branch into the rest of the tree (el will
1307 * either be on the root_bh, or the extent block passed in. */
1314 /* fe needs a new last extent block pointer, as does the
1315 * next_leaf on the previously last-extent-block. */
1326 /*
1327 * Some callers want to track the rightmost leaf so pass it
1328 * back here.
1329 */
1335 bail:
1340 }
1343 }
1345 /*
1346 * adds another level to the allocation tree.
1347 * returns back the new extent block so you can add a branch to it
1348 * after this call.
1349 */
1354 {
1356 u32 new_clusters;
1372 }
1377 }
1380 /* ocfs2_create_new_meta_bhs() should create it right! */
1387 OCFS2_JOURNAL_ACCESS_CREATE);
1391 }
1393 /* copy the root extent list data into the new extent block */
1402 OCFS2_JOURNAL_ACCESS_WRITE);
1406 }
1410 /* update root_bh now */
1419 /* If this is our 1st tree depth shift, then last_eb_blk
1420 * becomes the allocated extent block */
1429 bail:
1433 }
1435 /*
1436 * Should only be called when there is no space left in any of the
1437 * leaf nodes. What we want to do is find the lowest tree depth
1438 * non-leaf extent block with room for new records. There are three
1439 * valid results of this search:
1440 *
1441 * 1) a lowest extent block is found, then we pass it back in
1442 * *lowest_eb_bh and return '0'
1443 *
1444 * 2) the search fails to find anything, but the root_el has room. We
1445 * pass NULL back in *lowest_eb_bh, but still return '0'
1446 *
1447 * 3) the search fails to find anything AND the root_el is full, in
1448 * which case we return > 0
1449 *
1450 * return status < 0 indicates an error.
1451 */
1454 {
1456 u64 blkno;
1472 }
1480 }
1489 }
1499 }
1500 }
1502 /* If we didn't find one and the fe doesn't have any room,
1503 * then return '1' */
1509 bail:
1513 }
1515 /*
1516 * Grow a b-tree so that it has more records.
1517 *
1518 * We might shift the tree depth in which case existing paths should
1519 * be considered invalid.
1520 *
1521 * Tree depth after the grow is returned via *final_depth.
1522 *
1523 * *last_eb_bh will be updated by ocfs2_add_branch().
1524 */
1528 {
1541 }
1543 /* We traveled all the way to the bottom of the allocation tree
1544 * and didn't find room for any more extents - we need to add
1545 * another tree level */
1551 depth);
1553 /* ocfs2_shift_tree_depth will return us a buffer with
1554 * the new extent block (so we can pass that to
1555 * ocfs2_add_branch). */
1560 }
1561 depth++;
1563 /*
1564 * Special case: we have room now if we shifted from
1565 * tree_depth 0, so no more work needs to be done.
1566 *
1567 * We won't be calling add_branch, so pass
1568 * back *last_eb_bh as the new leaf. At depth
1569 * zero, it should always be null so there's
1570 * no reason to brelse.
1571 */
1576 }
1577 }
1579 /* call ocfs2_add_branch to add the final part of the tree with
1580 * the new data. */
1582 meta_ac);
1586 out:
1591 }
1593 /*
1594 * This function will discard the rightmost extent record.
1595 */
1597 {
1603 /* This will cause us to go off the end of our extent list. */
1609 }
1613 {
1623 /* The tree code before us didn't allow enough room in the leaf. */
1626 /*
1627 * The easiest way to approach this is to just remove the
1628 * empty extent and temporarily decrement next_free.
1629 */
1631 /*
1632 * If next_free was 1 (only an empty extent), this
1633 * loop won't execute, which is fine. We still want
1634 * the decrement above to happen.
1635 */
1639 next_free--;
1640 }
1642 /*
1643 * Figure out what the new record index should be.
1644 */
1650 }
1661 /*
1662 * No need to memmove if we're just adding to the tail.
1663 */
1671 num_bytes);
1672 }
1674 /*
1675 * Either we had an empty extent, and need to re-increment or
1676 * there was no empty extent on a non full rightmost leaf node,
1677 * in which case we still need to increment.
1678 */
1679 next_free++;
1681 /*
1682 * Make sure none of the math above just messed up our tree.
1683 */
1688 }
1691 {
1697 num_recs--;
1703 }
1704 }
1706 /*
1707 * Create an empty extent record .
1708 *
1709 * l_next_free_rec may be updated.
1710 *
1711 * If an empty extent already exists do nothing.
1712 */
1714 {
1733 set_and_inc:
1736 }
1738 /*
1739 * For a rotation which involves two leaf nodes, the "root node" is
1740 * the lowest level tree node which contains a path to both leafs. This
1741 * resulting set of information can be used to form a complete "subtree"
1742 *
1743 * This function is passed two full paths from the dinode down to a
1744 * pair of adjacent leaves. It's task is to figure out which path
1745 * index contains the subtree root - this can be the root index itself
1746 * in a worst-case rotation.
1747 *
1748 * The array index of the subtree root is passed back.
1749 */
1753 {
1756 /*
1757 * Check that the caller passed in two paths from the same tree.
1758 */
1762 i++;
1764 /*
1765 * The caller didn't pass two adjacent paths.
1766 */
1778 }
1782 /*
1783 * Traverse a btree path in search of cpos, starting at root_el.
1784 *
1785 * This code can be called with a cpos larger than the tree, in which
1786 * case it will return the rightmost path.
1787 */
1791 {
1793 u32 range;
1794 u64 blkno;
1810 }
1815 /*
1816 * In the case that cpos is off the allocation
1817 * tree, this should just wind up returning the
1818 * rightmost record.
1819 */
1824 }
1834 }
1842 }
1857 }
1861 }
1863 out:
1864 /*
1865 * Catch any trailing bh that the loop didn't handle.
1866 */
1870 }
1872 /*
1873 * Given an initialized path (that is, it has a valid root extent
1874 * list), this function will traverse the btree in search of the path
1875 * which would contain cpos.
1876 *
1877 * The path traveled is recorded in the path structure.
1878 *
1879 * Note that this will not do any comparisons on leaf node extent
1880 * records, so it will work fine in the case that we just added a tree
1881 * branch.
1882 */
1886 };
1888 {
1894 }
1897 {
1904 }
1907 {
1912 /* We want to retain only the leaf block. */
1916 }
1917 }
1918 /*
1919 * Find the leaf block in the tree which would contain cpos. No
1920 * checking of the actual leaf is done.
1921 *
1922 * Some paths want to call this instead of allocating a path structure
1923 * and calling ocfs2_find_path().
1924 *
1925 * This function doesn't handle non btree extent lists.
1926 */
1930 {
1938 }
1941 out:
1943 }
1945 /*
1946 * Adjust the adjacent records (left_rec, right_rec) involved in a rotation.
1947 *
1948 * Basically, we've moved stuff around at the bottom of the tree and
1949 * we need to fix up the extent records above the changes to reflect
1950 * the new changes.
1951 *
1952 * left_rec: the record on the left.
1953 * right_rec: the record to the right of left_rec
1954 * right_child_el: is the child list pointed to by right_rec
1955 *
1956 * By definition, this only works on interior nodes.
1957 */
1961 {
1964 /*
1965 * Interior nodes never have holes. Their cpos is the cpos of
1966 * the leftmost record in their child list. Their cluster
1967 * count covers the full theoretical range of their child list
1968 * - the range between their cpos and the cpos of the record
1969 * immediately to their right.
1970 */
1976 }
1980 /*
1981 * Calculate the rightmost cluster count boundary before
1982 * moving cpos - we will need to adjust clusters after
1983 * updating e_cpos to keep the same highest cluster count.
1984 */
1993 }
1995 /*
1996 * Adjust the adjacent root node records involved in a
1997 * rotation. left_el_blkno is passed in as a key so that we can easily
1998 * find it's index in the root list.
1999 */
2003 u64 left_el_blkno)
2004 {
2013 }
2015 /*
2016 * The path walking code should have never returned a root and
2017 * two paths which are not adjacent.
2018 */
2023 }
2025 /*
2026 * We've changed a leaf block (in right_path) and need to reflect that
2027 * change back up the subtree.
2028 *
2029 * This happens in multiple places:
2030 * - When we've moved an extent record from the left path leaf to the right
2031 * path leaf to make room for an empty extent in the left path leaf.
2032 * - When our insert into the right path leaf is at the leftmost edge
2033 * and requires an update of the path immediately to it's left. This
2034 * can occur at the end of some types of rotation and appending inserts.
2035 * - When we've adjusted the last extent record in the left path leaf and the
2036 * 1st extent record in the right path leaf during cross extent block merge.
2037 */
2042 {
2048 /*
2049 * Update the counts and position values within all the
2050 * interior nodes to reflect the leaf rotation we just did.
2051 *
2052 * The root node is handled below the loop.
2053 *
2054 * We begin the loop with right_el and left_el pointing to the
2055 * leaf lists and work our way up.
2056 *
2057 * NOTE: within this loop, left_el and right_el always refer
2058 * to the *child* lists.
2059 */
2065 /*
2066 * One nice property of knowing that all of these
2067 * nodes are below the root is that we only deal with
2068 * the leftmost right node record and the rightmost
2069 * left node record.
2070 */
2083 /*
2084 * Setup our list pointers now so that the current
2085 * parents become children in the next iteration.
2086 */
2089 }
2091 /*
2092 * At the root node, adjust the two adjacent records which
2093 * begin our path to the leaves.
2094 */
2106 }
2113 {
2131 }
2133 /*
2134 * This extent block may already have an empty record, so we
2135 * return early if so.
2136 */
2144 subtree_index);
2148 }
2156 }
2163 }
2164 }
2169 /* This is a code error, not a disk corruption. */
2179 /* Do the copy now. */
2184 /*
2185 * Clear out the record we just copied and shift everything
2186 * over, leaving an empty extent in the left leaf.
2187 *
2188 * We temporarily subtract from next_free_rec so that the
2189 * shift will lose the tail record (which is now defunct).
2190 */
2199 subtree_index);
2201 out:
2203 }
2205 /*
2206 * Given a full path, determine what cpos value would return us a path
2207 * containing the leaf immediately to the left of the current one.
2208 *
2209 * Will return zero if the path passed in is already the leftmost path.
2210 */
2213 {
2215 u64 blkno;
2224 /* Start at the tree node just above the leaf and work our way up. */
2229 /*
2230 * Find the extent record just before the one in our
2231 * path.
2232 */
2237 /*
2238 * We've determined that the
2239 * path specified is already
2240 * the leftmost one - return a
2241 * cpos of zero.
2242 */
2244 }
2245 /*
2246 * The leftmost record points to our
2247 * leaf - we need to travel up the
2248 * tree one level.
2249 */
2251 }
2258 }
2259 }
2261 /*
2262 * If we got here, we never found a valid node where
2263 * the tree indicated one should be.
2264 */
2270 next_node:
2272 i--;
2273 }
2275 out:
2277 }
2279 /*
2280 * Extend the transaction by enough credits to complete the rotation,
2281 * and still leave at least the original number of credits allocated
2282 * to this transaction.
2283 */
2287 {
2296 }
2298 /*
2299 * Trap the case where we're inserting into the theoretical range past
2300 * the _actual_ left leaf range. Otherwise, we'll rotate a record
2301 * whose cpos is less than ours into the right leaf.
2302 *
2303 * It's only necessary to look at the rightmost record of the left
2304 * leaf because the logic that calls us should ensure that the
2305 * theoretical ranges in the path components above the leaves are
2306 * correct.
2307 */
2309 u32 insert_cpos)
2310 {
2322 }
2325 {
2335 /* Empty list. */
2339 }
2345 }
2347 /*
2348 * Rotate all the records in a btree right one record, starting at insert_cpos.
2349 *
2350 * The path to the rightmost leaf should be passed in.
2351 *
2352 * The array is assumed to be large enough to hold an entire path (tree depth).
2353 *
2354 * Upon successful return from this function:
2355 *
2356 * - The 'right_path' array will contain a path to the leaf block
2357 * whose range contains e_cpos.
2358 * - That leaf block will have a single empty extent in list index 0.
2359 * - In the case that the rotation requires a post-insert update,
2360 * *ret_left_path will contain a valid path which can be passed to
2361 * ocfs2_insert_path().
2362 */
2366 u32 insert_cpos,
2369 {
2371 u32 cpos;
2382 }
2388 }
2394 /*
2395 * What we want to do here is:
2396 *
2397 * 1) Start with the rightmost path.
2398 *
2399 * 2) Determine a path to the leaf block directly to the left
2400 * of that leaf.
2401 *
2402 * 3) Determine the 'subtree root' - the lowest level tree node
2403 * which contains a path to both leaves.
2404 *
2405 * 4) Rotate the subtree.
2406 *
2407 * 5) Find the next subtree by considering the left path to be
2408 * the new right path.
2409 *
2410 * The check at the top of this while loop also accepts
2411 * insert_cpos == cpos because cpos is only a _theoretical_
2412 * value to get us the left path - insert_cpos might very well
2413 * be filling that hole.
2414 *
2415 * Stop at a cpos of '0' because we either started at the
2416 * leftmost branch (i.e., a tree with one branch and a
2417 * rotation inside of it), or we've gone as far as we can in
2418 * rotating subtrees.
2419 */
2430 }
2434 "Owner %llu: error during insert of %u "
2435 "(left path cpos %u) results in two identical "
2444 insert_cpos)) {
2446 /*
2447 * We've rotated the tree as much as we
2448 * should. The rest is up to
2449 * ocfs2_insert_path() to complete, after the
2450 * record insertion. We indicate this
2451 * situation by returning the left path.
2452 *
2453 * The reason we don't adjust the records here
2454 * before the record insert is that an error
2455 * later might break the rule where a parent
2456 * record e_cpos will reflect the actual
2457 * e_cpos of the 1st nonempty record of the
2458 * child list.
2459 */
2462 }
2476 }
2483 }
2487 insert_cpos)) {
2488 /*
2489 * A rotate moves the rightmost left leaf
2490 * record over to the leftmost right leaf
2491 * slot. If we're doing an extent split
2492 * instead of a real insert, then we have to
2493 * check that the extent to be split wasn't
2494 * just moved over. If it was, then we can
2495 * exit here, passing left_path back -
2496 * ocfs2_split_extent() is smart enough to
2497 * search both leaves.
2498 */
2501 }
2503 /*
2504 * There is no need to re-read the next right path
2505 * as we know that it'll be our current left
2506 * path. Optimize by copying values instead.
2507 */
2514 }
2515 }
2517 out:
2520 out_ret_path:
2522 }
2527 {
2532 u32 range;
2538 }
2540 /* Path should always be rightmost. */
2559 }
2560 out:
2562 }
2568 {
2578 /*
2579 * Not all nodes might have had their final count
2580 * decremented by the caller - handle this here.
2581 */
2585 "Inode %llu, attempted to remove extent block "
2594 }
2606 }
2607 }
2615 {
2640 }
2649 {
2667 /*
2668 * It's legal for us to proceed if the right leaf is
2669 * the rightmost one and it has an empty extent. There
2670 * are two cases to handle - whether the leaf will be
2671 * empty after removal or not. If the leaf isn't empty
2672 * then just remove the empty extent up front. The
2673 * next block will handle empty leaves by flagging
2674 * them for unlink.
2675 *
2676 * Non rightmost leaves will throw -EAGAIN and the
2677 * caller can manually move the subtree and retry.
2678 */
2686 OCFS2_JOURNAL_ACCESS_WRITE);
2690 }
2695 }
2699 /*
2700 * We have to update i_last_eb_blk during the meta
2701 * data delete.
2702 */
2704 OCFS2_JOURNAL_ACCESS_WRITE);
2708 }
2711 }
2713 /*
2714 * Getting here with an empty extent in the right path implies
2715 * that it's the rightmost path and will be deleted.
2716 */
2720 subtree_index);
2724 }
2732 }
2739 }
2740 }
2743 /*
2744 * Only do this if we're moving a real
2745 * record. Otherwise, the action is delayed until
2746 * after removal of the right path in which case we
2747 * can do a simple shift to remove the empty extent.
2748 */
2752 }
2754 /*
2755 * Move recs over to get rid of empty extent, decrease
2756 * next_free. This is allowed to remove the last
2757 * extent in our leaf (setting l_next_free_rec to
2758 * zero) - the delete code below won't care.
2759 */
2761 }
2773 }
2778 /*
2779 * Removal of the extent in the left leaf was skipped
2780 * above so we could delete the right path
2781 * 1st.
2782 */
2791 subtree_index);
2793 out:
2795 }
2797 /*
2798 * Given a full path, determine what cpos value would return us a path
2799 * containing the leaf immediately to the right of the current one.
2800 *
2801 * Will return zero if the path passed in is already the rightmost path.
2802 *
2803 * This looks similar, but is subtly different to
2804 * ocfs2_find_cpos_for_left_leaf().
2805 */
2808 {
2810 u64 blkno;
2820 /* Start at the tree node just above the leaf and work our way up. */
2827 /*
2828 * Find the extent record just after the one in our
2829 * path.
2830 */
2836 /*
2837 * We've determined that the
2838 * path specified is already
2839 * the rightmost one - return a
2840 * cpos of zero.
2841 */
2843 }
2844 /*
2845 * The rightmost record points to our
2846 * leaf - we need to travel up the
2847 * tree one level.
2848 */
2850 }
2854 }
2855 }
2857 /*
2858 * If we got here, we never found a valid node where
2859 * the tree indicated one should be.
2860 */
2866 next_node:
2868 i--;
2869 }
2871 out:
2873 }
2878 {
2891 }
2896 out:
2898 }
2906 {
2908 u32 right_cpos;
2922 }
2929 }
2938 }
2945 }
2948 right_path);
2960 }
2962 /*
2963 * Caller might still want to make changes to the
2964 * tree root, so re-add it to the journal here.
2965 */
2971 }
2977 /*
2978 * The rotation has to temporarily stop due to
2979 * the right subtree having an empty
2980 * extent. Pass it back to the caller for a
2981 * fixup.
2982 */
2986 }
2990 }
2992 /*
2993 * The subtree rotate might have removed records on
2994 * the rightmost edge. If so, then rotation is
2995 * complete.
2996 */
3007 }
3008 }
3010 out:
3015 }
3021 {
3023 u32 cpos;
3036 }
3043 }
3046 /*
3047 * We have a path to the left of this one - it needs
3048 * an update too.
3049 */
3055 }
3061 }
3067 }
3077 }
3082 /*
3083 * 'path' is also the leftmost path which
3084 * means it must be the only one. This gets
3085 * handled differently because we want to
3086 * revert the root back to having extents
3087 * in-line.
3088 */
3097 }
3101 out:
3104 }
3110 {
3120 }
3128 }
3130 /*
3131 * Left rotation of btree records.
3132 *
3133 * In many ways, this is (unsurprisingly) the opposite of right
3134 * rotation. We start at some non-rightmost path containing an empty
3135 * extent in the leaf block. The code works its way to the rightmost
3136 * path by rotating records to the left in every subtree.
3137 *
3138 * This is used by any code which reduces the number of extent records
3139 * in a leaf. After removal, an empty record should be placed in the
3140 * leftmost list position.
3141 *
3142 * This won't handle a length update of the rightmost path records if
3143 * the rightmost tree leaf record is removed so the caller is
3144 * responsible for detecting and correcting that.
3145 */
3150 {
3161 rightmost_no_delete:
3162 /*
3163 * Inline extents. This is trivially handled, so do
3164 * it up front.
3165 */
3170 }
3172 /*
3173 * Handle rightmost branch now. There's several cases:
3174 * 1) simple rotation leaving records in there. That's trivial.
3175 * 2) rotation requiring a branch delete - there's no more
3176 * records left. Two cases of this:
3177 * a) There are branches to the left.
3178 * b) This is also the leftmost (the only) branch.
3179 *
3180 * 1) is handled via ocfs2_rotate_rightmost_leaf_left()
3181 * 2a) we need the left branch so that we can update it with the unlink
3182 * 2b) we need to bring the root back to inline extents.
3183 */
3188 /*
3189 * This gets a bit tricky if we're going to delete the
3190 * rightmost path. Get the other cases out of the way
3191 * 1st.
3192 */
3202 }
3204 /*
3205 * XXX: The caller can not trust "path" any more after
3206 * this as it will have been deleted. What do we do?
3207 *
3208 * In theory the rotate-for-merge code will never get
3209 * here because it'll always ask for a rotate in a
3210 * nonempty list.
3211 */
3214 dealloc);
3218 }
3220 /*
3221 * Now we can loop, remembering the path we get from -EAGAIN
3222 * and restarting from there.
3223 */
3224 try_rotate:
3230 }
3242 }
3249 }
3251 out:
3255 }
3259 {
3264 /*
3265 * We consumed all of the merged-from record. An empty
3266 * extent cannot exist anywhere but the 1st array
3267 * position, so move things over if the merged-from
3268 * record doesn't occupy that position.
3269 *
3270 * This creates a new empty extent so the caller
3271 * should be smart enough to have removed any existing
3272 * ones.
3273 */
3278 }
3280 /*
3281 * Always memset - the caller doesn't check whether it
3282 * created an empty extent, so there could be junk in
3283 * the other fields.
3284 */
3286 }
3287 }
3292 {
3294 u32 right_cpos;
3300 /* This function shouldn't be called for non-trees. */
3311 }
3313 /* This function shouldn't be called for the rightmost leaf. */
3321 }
3327 }
3330 out:
3334 }
3336 /*
3337 * Remove split_rec clusters from the record at index and merge them
3338 * onto the beginning of the record "next" to it.
3339 * For index < l_count - 1, the next means the extent rec at index + 1.
3340 * For index == l_count - 1, the "next" means the 1st extent rec of the
3341 * next extent block.
3342 */
3348 {
3365 /* we meet with a cross extent block merge. */
3370 }
3379 }
3386 right_path);
3390 right_path);
3394 }
3400 subtree_index);
3404 }
3413 }
3420 }
3421 }
3426 }
3433 }
3440 split_clusters));
3449 subtree_index);
3450 }
3451 out:
3454 }
3459 {
3461 u32 left_cpos;
3466 /* This function shouldn't be called for non-trees. */
3474 }
3476 /* This function shouldn't be called for the leftmost leaf. */
3484 }
3490 }
3493 out:
3497 }
3499 /*
3500 * Remove split_rec clusters from the record at index and merge them
3501 * onto the tail of the record "before" it.
3502 * For index > 0, the "before" means the extent rec at index - 1.
3503 *
3504 * For index == 0, the "before" means the last record of the previous
3505 * extent block. And there is also a situation that we may need to
3506 * remove the rightmost leaf extent block in the right_path and change
3507 * the right path to indicate the new rightmost path.
3508 */
3515 {
3530 /* we meet with a cross extent block merge. */
3535 }
3548 right_path);
3552 left_path);
3556 }
3562 subtree_index);
3566 }
3575 }
3582 }
3583 }
3588 }
3595 }
3598 /*
3599 * The easy case - we can just plop the record right in.
3600 */
3608 split_clusters));
3617 /*
3618 * In the situation that the right_rec is empty and the extent
3619 * block is empty also, ocfs2_complete_edge_insert can't handle
3620 * it and we need to delete the right extent block.
3621 */
3624 /* extend credit for ocfs2_remove_rightmost_path */
3627 right_path);
3631 }
3634 right_path,
3635 dealloc);
3639 }
3641 /* Now the rightmost extent block has been deleted.
3642 * So we use the new rightmost path.
3643 */
3649 }
3650 out:
3653 }
3662 {
3670 /* extend credit for ocfs2_remove_rightmost_path */
3673 path);
3677 }
3678 /*
3679 * The merge code will need to create an empty
3680 * extent to take the place of the newly
3681 * emptied slot. Remove any pre-existing empty
3682 * extents - having more than one in a leaf is
3683 * illegal.
3684 */
3689 }
3690 split_index--;
3692 }
3695 /*
3696 * Left-right contig implies this.
3697 */
3700 /*
3701 * Since the leftright insert always covers the entire
3702 * extent, this call will delete the insert record
3703 * entirely, resulting in an empty extent record added to
3704 * the extent block.
3705 *
3706 * Since the adding of an empty extent shifts
3707 * everything back to the right, there's no need to
3708 * update split_index here.
3709 *
3710 * When the split_index is zero, we need to merge it to the
3711 * prevoius extent block. It is more efficient and easier
3712 * if we do merge_right first and merge_left later.
3713 */
3715 split_index);
3719 }
3721 /*
3722 * We can only get this from logic error above.
3723 */
3726 /* extend credit for ocfs2_remove_rightmost_path */
3729 path);
3733 }
3735 /* The merge left us with an empty extent, remove it. */
3740 }
3744 /*
3745 * Note that we don't pass split_rec here on purpose -
3746 * we've merged it into the rec already.
3747 */
3754 }
3756 /* extend credit for ocfs2_remove_rightmost_path */
3759 path);
3763 }
3766 /*
3767 * Error from this last rotate is not critical, so
3768 * print but don't bubble it up.
3769 */
3774 /*
3775 * Merge a record to the left or right.
3776 *
3777 * 'contig_type' is relative to the existing record,
3778 * so for example, if we're "right contig", it's to
3779 * the record on the left (hence the left merge).
3780 */
3784 split_index);
3788 }
3792 split_index);
3796 }
3797 }
3800 /* extend credit for ocfs2_remove_rightmost_path */
3803 path);
3808 }
3810 /*
3811 * The merge may have left an empty extent in
3812 * our leaf. Try to rotate it away.
3813 */
3815 dealloc);
3819 }
3820 }
3822 out:
3824 }
3830 {
3831 u64 len_blocks;
3837 /*
3838 * Region is on the left edge of the existing
3839 * record.
3840 */
3847 /*
3848 * Region is on the right edge of the existing
3849 * record.
3850 */
3853 }
3854 }
3856 /*
3857 * Do the final bits of extent record insertion at the target leaf
3858 * list. If this leaf is part of an allocation tree, it is assumed
3859 * that the tree above has been prepared.
3860 */
3865 {
3878 insert_rec);
3880 }
3882 /*
3883 * Contiguous insert - either left or right.
3884 */
3890 }
3894 }
3896 /*
3897 * Handle insert into an empty leaf.
3898 */
3905 }
3907 /*
3908 * Appending insert.
3909 */
3919 "owner %llu, depth %u, count %u, next free %u, "
3920 "rec.cpos %u, rec.clusters %u, "
3930 i++;
3934 }
3936 rotate:
3937 /*
3938 * Ok, we have to rotate.
3939 *
3940 * At this point, it is safe to assume that inserting into an
3941 * empty leaf and appending to a leaf have both been handled
3942 * above.
3943 *
3944 * This leaf needs to have space, either by the empty 1st
3945 * extent record, or by virtue of an l_next_rec < l_count.
3946 */
3948 }
3954 {
3960 /*
3961 * Update everything except the leaf block.
3962 */
3973 }
3984 }
3985 }
3992 {
3999 /*
4000 * This shouldn't happen for non-trees. The extent rec cluster
4001 * count manipulation below only works for interior nodes.
4002 */
4005 /*
4006 * If our appending insert is at the leftmost edge of a leaf,
4007 * then we might need to update the rightmost records of the
4008 * neighboring path.
4009 */
4014 u32 left_cpos;
4021 }
4027 left_cpos);
4029 /*
4030 * No need to worry if the append is already in the
4031 * leftmost leaf.
4032 */
4039 }
4042 left_cpos);
4046 }
4048 /*
4049 * ocfs2_insert_path() will pass the left_path to the
4050 * journal for us.
4051 */
4052 }
4053 }
4059 }
4065 out:
4070 }
4077 {
4094 /*
4095 * This typically means that the record
4096 * started in the left path but moved to the
4097 * right as a result of rotation. We either
4098 * move the existing record to the left, or we
4099 * do the later insert there.
4100 *
4101 * In this case, the left path should always
4102 * exist as the rotate code will have passed
4103 * it back for a post-insert update.
4104 */
4107 /*
4108 * It's a left split. Since we know
4109 * that the rotate code gave us an
4110 * empty extent in the left path, we
4111 * can just do the insert there.
4112 */
4115 /*
4116 * Right split - we have to move the
4117 * existing record over to the left
4118 * leaf. The insert will be into the
4119 * newly created empty extent in the
4120 * right leaf.
4121 */
4129 }
4130 }
4134 /*
4135 * Left path is easy - we can just allow the insert to
4136 * happen.
4137 */
4142 }
4148 }
4150 /*
4151 * This function only does inserts on an allocation b-tree. For tree
4152 * depth = 0, ocfs2_insert_at_leaf() is called directly.
4153 *
4154 * right_path is the path we want to do the actual insert
4155 * in. left_path should only be passed in if we need to update that
4156 * portion of the tree after an edge insert.
4157 */
4164 {
4169 /*
4170 * There's a chance that left_path got passed back to
4171 * us without being accounted for in the
4172 * journal. Extend our transaction here to be sure we
4173 * can change those blocks.
4174 */
4179 }
4185 }
4186 }
4188 /*
4189 * Pass both paths to the journal. The majority of inserts
4190 * will be touching all components anyway.
4191 */
4196 }
4199 /*
4200 * We could call ocfs2_insert_at_leaf() for some types
4201 * of splits, but it's easier to just let one separate
4202 * function sort it all out.
4203 */
4207 /*
4208 * Split might have modified either leaf and we don't
4209 * have a guarantee that the later edge insert will
4210 * dirty this for us.
4211 */
4217 insert);
4222 /*
4223 * The rotate code has indicated that we need to fix
4224 * up portions of the tree after the insert.
4225 *
4226 * XXX: Should we extend the transaction here?
4227 */
4229 right_path);
4231 subtree_index);
4232 }
4235 out:
4237 }
4243 {
4245 u32 cpos;
4253 OCFS2_JOURNAL_ACCESS_WRITE);
4257 }
4262 }
4269 }
4271 /*
4272 * Determine the path to start with. Rotations need the
4273 * rightmost path, everything else can go directly to the
4274 * target leaf.
4275 */
4281 }
4287 }
4289 /*
4290 * Rotations and appends need special treatment - they modify
4291 * parts of the tree's above them.
4292 *
4293 * Both might pass back a path immediate to the left of the
4294 * one being inserted to. This will be cause
4295 * ocfs2_insert_path() to modify the rightmost records of
4296 * left_path to account for an edge insert.
4297 *
4298 * XXX: When modifying this code, keep in mind that an insert
4299 * can wind up skipping both of these two special cases...
4300 */
4308 }
4310 /*
4311 * ocfs2_rotate_tree_right() might have extended the
4312 * transaction without re-journaling our tree root.
4313 */
4315 OCFS2_JOURNAL_ACCESS_WRITE);
4319 }
4327 }
4328 }
4335 }
4337 out_update_clusters:
4344 out:
4349 }
4356 {
4380 }
4383 left_cpos);
4394 "Extent block #%llu has an invalid l_next_free_rec of %d. It should have matched the l_count of %d\n",
4399 }
4402 }
4403 }
4405 /*
4406 * We're careful to check for an empty extent record here -
4407 * the merge code will know what to do if it sees one.
4408 */
4415 }
4416 }
4435 }
4452 }
4454 }
4455 }
4466 }
4468 free_right_path:
4470 free_left_path:
4472 exit:
4477 }
4483 {
4491 insert_rec);
4495 }
4496 }
4505 /*
4506 * Caller might want us to limit the size of extents, don't
4507 * calculate contiguousness if we might exceed that limit.
4508 */
4512 }
4513 }
4515 /*
4516 * This should only be called against the righmost leaf extent list.
4517 *
4518 * ocfs2_figure_appending_type() will figure out whether we'll have to
4519 * insert at the tail of the rightmost leaf.
4520 *
4521 * This should also work against the root extent list for tree's with 0
4522 * depth. If we consider the root extent list to be the rightmost leaf node
4523 * then the logic here makes sense.
4524 */
4528 {
4541 /* Were all records empty? */
4544 }
4555 set_tail_append:
4557 }
4559 /*
4560 * Helper function called at the beginning of an insert.
4561 *
4562 * This computes a few things that are commonly used in the process of
4563 * inserting into the btree:
4564 * - Whether the new extent is contiguous with an existing one.
4565 * - The current tree depth.
4566 * - Whether the insert is an appending one.
4567 * - The total # of free records in the tree.
4568 *
4569 * All of the information is stored on the ocfs2_insert_type
4570 * structure.
4571 */
4577 {
4590 /*
4591 * If we have tree depth, we read in the
4592 * rightmost extent block ahead of time as
4593 * ocfs2_figure_insert_type() and ocfs2_add_branch()
4594 * may want it later.
4595 */
4602 }
4605 }
4607 /*
4608 * Unless we have a contiguous insert, we'll need to know if
4609 * there is room left in our allocation tree for another
4610 * extent record.
4611 *
4612 * XXX: This test is simplistic, we can search for empty
4613 * extent records too.
4614 */
4622 }
4629 }
4631 /*
4632 * In the case that we're inserting past what the tree
4633 * currently accounts for, ocfs2_find_path() will return for
4634 * us the rightmost tree path. This is accounted for below in
4635 * the appending code.
4636 */
4641 }
4645 /*
4646 * Now that we have the path, there's two things we want to determine:
4647 * 1) Contiguousness (also set contig_index if this is so)
4648 *
4649 * 2) Are we doing an append? We can trivially break this up
4650 * into two types of appends: simple record append, or a
4651 * rotate inside the tail leaf.
4652 */
4655 /*
4656 * The insert code isn't quite ready to deal with all cases of
4657 * left contiguousness. Specifically, if it's an insert into
4658 * the 1st record in a leaf, it will require the adjustment of
4659 * cluster count on the last record of the path directly to it's
4660 * left. For now, just catch that case and fool the layers
4661 * above us. This works just fine for tree_depth == 0, which
4662 * is why we allow that above.
4663 */
4668 /*
4669 * Ok, so we can simply compare against last_eb to figure out
4670 * whether the path doesn't exist. This will only happen in
4671 * the case that we're doing a tail append, so maybe we can
4672 * take advantage of that information somehow.
4673 */
4676 /*
4677 * Ok, ocfs2_find_path() returned us the rightmost
4678 * tree path. This might be an appending insert. There are
4679 * two cases:
4680 * 1) We're doing a true append at the tail:
4681 * -This might even be off the end of the leaf
4682 * 2) We're "appending" by rotating in the tail
4683 */
4685 }
4687 out:
4692 else
4695 }
4697 /*
4698 * Insert an extent into a btree.
4699 *
4700 * The caller needs to update the owning btree's cluster count.
4701 */
4704 u32 cpos,
4705 u64 start_blk,
4706 u32 new_clusters,
4707 u8 flags,
4709 {
4729 }
4736 }
4745 meta_ac);
4749 }
4750 }
4752 /* Finally, we can add clusters. This might rotate the tree for us. */
4756 else
4759 bail:
4763 }
4765 /*
4766 * Allcate and add clusters into the extent b-tree.
4767 * The new clusters(clusters_to_add) will be inserted at logical_offset.
4768 * The extent b-tree's root is specified by et, and
4769 * it is not limited to the file storage. Any extent tree can use this
4770 * function if it implements the proper ocfs2_extent_tree.
4771 */
4775 u32 clusters_to_add,
4780 {
4786 u64 block;
4801 }
4803 /* there are two cases which could cause us to EAGAIN in the
4804 * we-need-more-metadata case:
4805 * 1) we haven't reserved *any*
4806 * 2) we are so fragmented, we've needed to add metadata too
4807 * many times. */
4820 }
4828 }
4832 /* reserve our write early -- insert_extent may update the tree root */
4834 OCFS2_JOURNAL_ACCESS_WRITE);
4839 }
4851 }
4862 }
4864 bail:
4869 else
4874 num_bits);
4875 }
4877 leave:
4882 }
4886 u32 cpos,
4888 {
4902 }
4911 {
4921 leftright:
4922 /*
4923 * Store a copy of the record on the stack - it might move
4924 * around as the tree is manipulated below.
4925 */
4935 }
4944 }
4945 }
4962 /*
4963 * Left/right split. We fake this as a right split
4964 * first and then make a second pass as a left split.
4965 */
4975 }
4981 }
4984 u32 cpos;
4987 do_leftright++;
4997 }
5005 cpos);
5008 }
5010 }
5011 out:
5014 }
5022 {
5030 }
5035 out:
5037 }
5039 /*
5040 * Split part or all of the extent record at split_index in the leaf
5041 * pointed to by path. Merge with the contiguous extent record if needed.
5042 *
5043 * Care is taken to handle contiguousness so as to not grow the tree.
5044 *
5045 * meta_ac is not strictly necessary - we only truly need it if growth
5046 * of the tree is required. All other cases will degrade into a less
5047 * optimal tree layout.
5048 *
5049 * last_eb_bh should be the rightmost leaf block for any extent
5050 * btree. Since a split may grow the tree or a merge might shrink it,
5051 * the caller cannot trust the contents of that buffer after this call.
5052 *
5053 * This code is optimized for readability - several passes might be
5054 * made over certain portions of the tree. All of those blocks will
5055 * have been brought into cache (and pinned via the journal), so the
5056 * extra overhead is not expressed in terms of disk reads.
5057 */
5065 {
5078 }
5081 split_index,
5082 split_rec,
5087 }
5089 /*
5090 * The core merge / split code wants to know how much room is
5091 * left in this allocation tree, so we pass the
5092 * rightmost extent list.
5093 */
5101 }
5102 }
5107 else
5120 else
5132 }
5134 out:
5137 }
5139 /*
5140 * Change the flags of the already-existing extent at cpos for len clusters.
5141 *
5142 * new_flags: the flags we want to set.
5143 * clear_flags: the flags we want to clear.
5144 * phys: the new physical offset we want this new extent starts from.
5145 *
5146 * If the existing extent is larger than the request, initiate a
5147 * split. An attempt will be made at merging with adjacent extents.
5148 *
5149 * The caller is responsible for passing down meta_ac if we'll need it.
5150 */
5157 {
5171 }
5177 }
5185 cpos);
5188 }
5196 new_flags);
5198 }
5204 clear_flags);
5206 }
5220 dealloc);
5224 out:
5228 }
5230 /*
5231 * Mark the already-existing extent at cpos as written for len clusters.
5232 * This removes the unwritten extent flag.
5233 *
5234 * If the existing extent is larger than the request, initiate a
5235 * split. An attempt will be made at merging with adjacent extents.
5236 *
5237 * The caller is responsible for passing down meta_ac if we'll need it.
5238 */
5244 {
5252 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",
5256 }
5258 /*
5259 * XXX: This should be fixed up so that we just re-insert the
5260 * next extent records.
5261 */
5270 out:
5272 }
5278 {
5287 /*
5288 * Setup the record to split before we grow the tree.
5289 */
5303 }
5316 }
5321 meta_ac);
5325 }
5326 }
5338 out:
5341 }
5348 {
5359 /* extend credit for ocfs2_remove_rightmost_path */
5362 path);
5366 }
5372 }
5374 index--;
5375 }
5379 /*
5380 * Check whether this is the rightmost tree record. If
5381 * we remove all of this record or part of its right
5382 * edge then an update of the record lengths above it
5383 * will be required.
5384 */
5388 }
5393 /*
5394 * Changing the leftmost offset (via partial or whole
5395 * record truncate) of an interior (or rightmost) path
5396 * means we have to update the subtree that is formed
5397 * by this leaf and the one to it's left.
5398 *
5399 * There are two cases we can skip:
5400 * 1) Path is the leftmost one in our btree.
5401 * 2) The leaf is rightmost and will be empty after
5402 * we remove the extent record - the rotate code
5403 * knows how to update the newly formed edge.
5404 */
5410 }
5418 }
5421 left_cpos);
5425 }
5426 }
5427 }
5431 path);
5435 }
5441 }
5447 }
5460 /*
5461 * We skip the edge update if this path will
5462 * be deleted by the rotate code.
5463 */
5466 rec);
5467 }
5469 /* Remove leftmost portion of the record. */
5474 /* Remove rightmost portion of the record */
5479 /* Caller should have trapped this. */
5486 }
5493 subtree_index);
5494 }
5502 out:
5505 }
5512 {
5519 /*
5520 * XXX: Why are we truncating to 0 instead of wherever this
5521 * affects us?
5522 */
5530 }
5536 }
5544 cpos);
5547 }
5549 /*
5550 * We have 3 cases of extent removal:
5551 * 1) Range covers the entire extent rec
5552 * 2) Range begins or ends on one edge of the extent rec
5553 * 3) Range is in the middle of the extent rec (no shared edges)
5554 *
5555 * For case 1 we remove the extent rec and left rotate to
5556 * fill the hole.
5557 *
5558 * For case 2 we just shrink the existing extent rec, with a
5559 * tree update if the shrinking edge is also the edge of an
5560 * extent block.
5561 *
5562 * For case 3 we do a right split to turn the extent rec into
5563 * something case 2 can handle.
5564 */
5582 }
5589 }
5591 /*
5592 * The split could have manipulated the tree enough to
5593 * move the record location, so we have to look for it again.
5594 */
5601 }
5609 cpos);
5612 }
5614 /*
5615 * Double check our values here. If anything is fishy,
5616 * it's easier to catch it at the top level.
5617 */
5629 }
5635 }
5637 out:
5640 }
5642 /*
5643 * ocfs2_reserve_blocks_for_rec_trunc() would look basically the
5644 * same as ocfs2_lock_alloctors(), except for it accepts a blocks
5645 * number to reserve some extra blocks, and it only handles meta
5646 * data allocations.
5647 *
5648 * Currently, only ocfs2_remove_btree_range() uses it for truncating
5649 * and punching holes.
5650 */
5653 u32 extents_to_split,
5656 {
5668 }
5679 }
5680 }
5682 out:
5687 }
5688 }
5691 }
5698 {
5716 }
5717 }
5720 refcount_loc,
5721 phys_blkno,
5722 len,
5728 }
5729 }
5732 extra_blocks);
5736 }
5745 }
5746 }
5754 }
5757 OCFS2_JOURNAL_ACCESS_WRITE);
5761 }
5770 }
5781 phys_blkno),
5784 else
5790 }
5792 out_commit:
5794 out:
5796 bail:
5804 }
5807 {
5816 "slot %d, invalid truncate log parameters: used = "
5820 }
5824 {
5828 /* No records, nothing to coalesce */
5837 }
5841 u64 start_blk,
5843 {
5857 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5858 * by the underlying call to ocfs2_read_inode_block(), so any
5859 * corruption is a code bug */
5866 "Truncate record count on #%llu invalid "
5872 /* Caller should have known to flush before calling us. */
5878 }
5881 OCFS2_JOURNAL_ACCESS_WRITE);
5885 }
5891 /*
5892 * Move index back to the record we are coalescing with.
5893 * ocfs2_truncate_log_can_coalesce() guarantees nonzero
5894 */
5895 index--;
5901 num_clusters);
5905 }
5911 bail:
5913 }
5918 {
5922 u64 start_blk;
5939 }
5941 /* Caller has given us at least enough credits to
5942 * update the truncate log dinode */
5944 OCFS2_JOURNAL_ACCESS_WRITE);
5948 }
5959 /* if start_blk is not set, we ignore the record as
5960 * invalid. */
5968 num_clusters);
5972 }
5973 }
5976 i--;
5977 }
5981 bail:
5983 }
5985 /* Expects you to already be holding tl_inode->i_mutex */
5987 {
6002 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
6003 * by the underlying call to ocfs2_read_inode_block(), so any
6004 * corruption is a code bug */
6011 num_to_flush);
6015 }
6017 /* Appending truncate log(TA) and and flushing truncate log(TF) are
6018 * two separated transactions. They can be both committed but not
6019 * checkpointed. If crash occurs then, both two transaction will be
6020 * replayed with several already released to global bitmap clusters.
6021 * Then truncate log will be replayed resulting in cluster double free.
6022 */
6029 }
6032 GLOBAL_BITMAP_SYSTEM_INODE,
6033 OCFS2_INVALID_SLOT);
6038 }
6046 }
6049 data_alloc_bh);
6056 out_mutex:
6060 out:
6062 }
6065 {
6074 }
6077 {
6086 else
6088 }
6090 #define OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL (2 * HZ)
6093 {
6096 /* We want to push off log flushes while truncates are
6097 * still running. */
6102 OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL);
6103 }
6104 }
6106 /*
6107 * Try to flush truncate logs if we can free enough clusters from it.
6108 * As for return value, "< 0" means error, "0" no space and "1" means
6109 * we have freed enough spaces and let the caller try to allocate again.
6110 */
6113 {
6114 tid_t target;
6122 /*
6123 * Check whether we can succeed in allocating if we free
6124 * the truncate log.
6125 */
6133 }
6138 }
6139 out:
6141 }
6147 {
6153 TRUNCATE_LOG_SYSTEM_INODE,
6154 slot_num);
6159 }
6166 }
6170 bail:
6172 }
6174 /* called during the 1st stage of node recovery. we stamp a clean
6175 * truncate log and pass back a copy for processing later. if the
6176 * truncate log does not require processing, a *tl_copy is set to
6177 * NULL. */
6181 {
6196 }
6200 /* tl_bh is loaded from ocfs2_get_truncate_log_info(). It's
6201 * validated by the underlying call to ocfs2_read_inode_block(),
6202 * so any corruption is a code bug */
6209 /*
6210 * Assuming the write-out below goes well, this copy will be
6211 * passed back to recovery for processing.
6212 */
6218 }
6220 /* All we need to do to clear the truncate log is set
6221 * tl_used. */
6229 }
6230 }
6232 bail:
6240 }
6243 }
6247 {
6251 u64 start_blk;
6259 }
6265 num_recs);
6274 }
6275 }
6282 }
6294 }
6295 }
6297 bail_up:
6301 }
6304 {
6320 }
6321 }
6324 {
6336 /* ocfs2_truncate_log_shutdown keys on the existence of
6337 * osb->osb_tl_inode so we don't set any of the osb variables
6338 * until we're sure all is well. */
6340 ocfs2_truncate_log_worker);
6346 }
6348 /*
6349 * Delayed de-allocation of suballocator blocks.
6350 *
6351 * Some sets of block de-allocations might involve multiple suballocator inodes.
6352 *
6353 * The locking for this can get extremely complicated, especially when
6354 * the suballocator inodes to delete from aren't known until deep
6355 * within an unrelated codepath.
6356 *
6357 * ocfs2_extent_block structures are a good example of this - an inode
6358 * btree could have been grown by any number of nodes each allocating
6359 * out of their own suballoc inode.
6360 *
6361 * These structures allow the delay of block de-allocation until a
6362 * later time, when locking of multiple cluster inodes won't cause
6363 * deadlock.
6364 */
6366 /*
6367 * Describe a single bit freed from a suballocator. For the block
6368 * suballocators, it represents one block. For the global cluster
6369 * allocator, it represents some clusters and free_bit indicates
6370 * clusters number.
6371 */
6374 u64 free_bg;
6375 u64 free_blk;
6377 };
6384 };
6390 {
6392 u64 bg_blkno;
6403 }
6411 }
6416 else
6424 }
6439 }
6441 out_unlock:
6444 out_mutex:
6447 out:
6449 /* Premature exit may have left some dangling items. */
6453 }
6456 }
6460 {
6469 }
6479 }
6483 {
6497 }
6498 }
6505 }
6518 }
6519 }
6524 /* Premature exit may have left some dangling items. */
6528 }
6531 }
6535 {
6556 }
6560 }
6571 }
6574 }
6580 {
6588 }
6598 }
6600 }
6607 {
6614 }
6617 }
6619 /* If we can't find any free list matching preferred slot, just use
6620 * the first one.
6621 */
6626 }
6628 /* Return Value 1 indicates empty */
6630 {
6644 }
6646 /* If extent was deleted from tree due to extent rotation and merging, and
6647 * no metadata is reserved ahead of time. Try to reuse some extents
6648 * just deleted. This is only used to reuse extent blocks.
6649 * It is supposed to find enough extent blocks in dealloc if our estimation
6650 * on metadata is accurate.
6651 */
6656 {
6667 /* If extent tree doesn't have a dealloc, this is not faulty. Just
6668 * tell upper caller dealloc can't provide any block and it should
6669 * ask for alloc to claim more space.
6670 */
6676 /* Prefer to use local slot */
6679 dealloc);
6680 /* If no more block can be reused, we should claim more
6681 * from alloc. Just return here normally.
6682 */
6686 }
6696 }
6706 OCFS2_JOURNAL_ACCESS_CREATE);
6710 }
6715 /* We can't guarantee that buffer head is still cached, so
6716 * polutlate the extent block again.
6717 */
6727 /* We'll also be dirtied by the caller, so
6728 * this isn't absolutely necessary.
6729 */
6735 }
6737 }
6741 bail:
6745 }
6748 }
6753 {
6763 }
6770 }
6784 out:
6786 }
6790 {
6796 }
6799 {
6803 }
6808 {
6820 /*
6821 * Need to set the buffers we zero'd into uptodate
6822 * here if they aren't - ocfs2_map_page_blocks()
6823 * might've skipped some
6824 */
6827 ocfs2_zero_func);
6835 }
6841 }
6846 {
6872 }
6873 out:
6876 }
6880 {
6884 loff_t last_page_bytes;
6897 }
6899 numpages++;
6900 index++;
6903 out:
6908 }
6913 }
6917 {
6924 }
6926 /*
6927 * Zero the area past i_size but still within an allocated
6928 * cluster. This avoids exposing nonzero data on subsequent file
6929 * extends.
6930 *
6931 * We need to call this before i_size is updated on the inode because
6932 * otherwise block_write_full_page() will skip writeout of pages past
6933 * i_size. The new_i_size parameter is passed for this reason.
6934 */
6937 {
6940 u64 phys;
6944 /*
6945 * File systems which don't support sparse files zero on every
6946 * extend.
6947 */
6957 }
6968 }
6970 /*
6971 * Tail is a hole, or is marked unwritten. In either case, we
6972 * can count on read and write to return/push zero's.
6973 */
6982 }
6987 /*
6988 * Initiate writeout of the pages we zero'd here. We don't
6989 * wait on them - the truncate_inode_pages() call later will
6990 * do that for us.
6991 */
6997 out:
7001 }
7005 {
7012 xattrsize);
7013 else
7016 }
7020 {
7026 }
7029 {
7038 /*
7039 * We clear the entire i_data structure here so that all
7040 * fields can be properly initialized.
7041 */
7046 }
7050 {
7074 }
7080 }
7081 }
7089 }
7092 OCFS2_JOURNAL_ACCESS_WRITE);
7096 }
7100 u64 phys;
7115 }
7117 /*
7118 * Save two copies, one for insert, and one that can
7119 * be changed by ocfs2_map_and_dirty_page() below.
7120 */
7123 /*
7124 * Non sparse file systems zero on extend, so no need
7125 * to do that now.
7126 */
7136 }
7138 /*
7139 * This should populate the 1st page for us and mark
7140 * it up to date.
7141 */
7147 }
7156 }
7169 /*
7170 * An error at this point should be extremely rare. If
7171 * this proves to be false, we could always re-build
7172 * the in-inode data from our pages.
7173 */
7180 }
7183 }
7185 out_unlock:
7189 out_commit:
7198 else
7203 num);
7204 }
7208 out:
7211 free_pages:
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 {
7422 }
7429 }
7432 OCFS2_JOURNAL_ACCESS_WRITE);
7436 }
7441 /*
7442 * No need to worry about the data page here - it's been
7443 * truncated already and inline data doesn't need it for
7444 * pushing zero's to disk, so we'll let readpage pick it up
7445 * later.
7446 */
7450 }
7461 out_commit:
7464 out:
7466 }
7471 {
7478 /*
7479 * For the first cluster group, the gd->bg_blkno is not at the start
7480 * of the group, but at an offset from the start. If we add it while
7481 * calculating discard for first group, we will wrongly start fstrim a
7482 * few blocks after the desried start block and the range can cross
7483 * over into the next cluster group. So, add it only if this is not
7484 * the first cluster group.
7485 */
7492 }
7497 {
7519 }
7521 }
7527 }
7531 }
7537 }
7539 static
7541 {
7561 next_group:
7563 GLOBAL_BITMAP_SYSTEM_INODE,
7564 OCFS2_INVALID_SLOT);
7569 }
7577 }
7580 /*
7581 * Do some check before trim the first group.
7582 */
7587 }
7592 /*
7593 * Determine first and last group to examine based on
7594 * start and len
7595 */
7599 else
7601 first_group);
7605 }
7610 else
7619 }
7630 }
7637 else
7641 out_unlock:
7645 out_mutex:
7649 /*
7650 * If all the groups trim are not done or failed, but we should release
7651 * main_bm related locks for avoiding the current IO starve, then go to
7652 * trim the next group
7653 */
7656 out:
7659 }
7662 {
7677 }
7687 }
7693 /* Avoid sending duplicated trim to a shared device */
7699 }
7700 }
7712 out:
7716 }