| blob | 0f157bbd3e0f226589d2e4bd4ce6e7095a0a5cb1 |
1 /* -*- mode: c; c-basic-offset: 8; -*-
2 * vim: noexpandtab sw=8 ts=8 sts=0:
3 *
4 * alloc.c
5 *
6 * Extent allocs and frees
7 *
8 * Copyright (C) 2002, 2004 Oracle. All rights reserved.
9 *
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public
12 * License as published by the Free Software Foundation; either
13 * version 2 of the License, or (at your option) any later version.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 * General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public
21 * License along with this program; if not, write to the
22 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
23 * Boston, MA 021110-1307, USA.
24 */
26 #include <linux/fs.h>
27 #include <linux/types.h>
28 #include <linux/slab.h>
29 #include <linux/highmem.h>
30 #include <linux/swap.h>
31 #include <linux/quotaops.h>
32 #include <linux/blkdev.h>
33 #include <linux/sched/signal.h>
35 #include <cluster/masklog.h>
60 CONTIG_LEFT,
61 CONTIG_RIGHT,
62 CONTIG_LEFTRIGHT,
63 };
65 static enum ocfs2_contig_type
69 /*
70 * Operations for a specific extent tree type.
71 *
72 * To implement an on-disk btree (extent tree) type in ocfs2, add
73 * an ocfs2_extent_tree_operations structure and the matching
74 * ocfs2_init_<thingy>_extent_tree() function. That's pretty much it
75 * for the allocation portion of the extent tree.
76 */
78 /*
79 * last_eb_blk is the block number of the right most leaf extent
80 * block. Most on-disk structures containing an extent tree store
81 * this value for fast access. The ->eo_set_last_eb_blk() and
82 * ->eo_get_last_eb_blk() operations access this value. They are
83 * both required.
84 */
86 u64 blkno);
89 /*
90 * The on-disk structure usually keeps track of how many total
91 * clusters are stored in this extent tree. This function updates
92 * that value. new_clusters is the delta, and must be
93 * added to the total. Required.
94 */
96 u32 new_clusters);
98 /*
99 * If this extent tree is supported by an extent map, insert
100 * a record into the map.
101 */
105 /*
106 * If this extent tree is supported by an extent map, truncate the
107 * map to clusters,
108 */
110 u32 clusters);
112 /*
113 * If ->eo_insert_check() exists, it is called before rec is
114 * inserted into the extent tree. It is optional.
115 */
120 /*
121 * --------------------------------------------------------------
122 * The remaining are internal to ocfs2_extent_tree and don't have
123 * accessor functions
124 */
126 /*
127 * ->eo_fill_root_el() takes et->et_object and sets et->et_root_el.
128 * It is required.
129 */
132 /*
133 * ->eo_fill_max_leaf_clusters sets et->et_max_leaf_clusters if
134 * it exists. If it does not, et->et_max_leaf_clusters is set
135 * to 0 (unlimited). Optional.
136 */
139 /*
140 * ->eo_extent_contig test whether the 2 ocfs2_extent_rec
141 * are contiguous or not. Optional. Don't need to set it if use
142 * ocfs2_extent_rec as the tree leaf.
143 */
144 enum ocfs2_contig_type
148 };
151 /*
152 * Pre-declare ocfs2_dinode_et_ops so we can use it as a sanity check
153 * in the methods.
154 */
157 u64 blkno);
159 u32 clusters);
163 u32 clusters);
184 };
187 u64 blkno)
188 {
193 }
196 {
201 }
204 u32 clusters)
205 {
213 }
217 {
221 }
224 u32 clusters)
225 {
229 }
233 {
240 "Device %s, asking for sparse allocation: inode %llu, "
247 }
250 {
257 }
260 {
264 }
268 {
272 }
275 u64 blkno)
276 {
280 }
283 {
287 }
290 u32 clusters)
291 {
295 }
302 };
305 {
309 }
312 {
316 }
319 u64 blkno)
320 {
325 }
328 {
333 }
336 u32 clusters)
337 {
341 }
349 };
352 u64 blkno)
353 {
357 }
360 {
364 }
367 u32 clusters)
368 {
372 }
375 {
381 }
384 {
388 }
396 };
399 {
403 }
406 u64 blkno)
407 {
411 }
414 {
418 }
421 u32 clusters)
422 {
426 }
428 static enum ocfs2_contig_type
432 {
434 }
442 };
447 ocfs2_journal_access_func access,
450 {
463 else
465 }
470 {
473 }
478 {
481 }
486 {
489 }
494 {
497 }
502 {
505 }
508 u64 new_last_eb_blk)
509 {
511 }
514 {
516 }
519 u32 clusters)
520 {
522 }
526 {
529 }
532 u32 clusters)
533 {
536 }
541 {
543 type);
544 }
550 {
557 }
561 {
567 }
570 {
576 }
584 /*
585 * Reset the actual path elements so that we can re-use the structure
586 * to build another path. Generally, this involves freeing the buffer
587 * heads.
588 */
590 {
603 }
605 /*
606 * Tree depth may change during truncate, or insert. If we're
607 * keeping the root extent list, then make sure that our path
608 * structure reflects the proper depth.
609 */
612 else
616 }
619 {
623 }
624 }
626 /*
627 * All the elements of src into dest. After this call, src could be freed
628 * without affecting dest.
629 *
630 * Both paths should have the same root. Any non-root elements of dest
631 * will be freed.
632 */
634 {
649 }
650 }
652 /*
653 * Make the *dest path the same as src and re-initialize src path to
654 * have a root only.
655 */
657 {
671 }
672 }
674 /*
675 * Insert an extent block at given index.
676 *
677 * This will not take an additional reference on eb_bh.
678 */
681 {
684 /*
685 * Right now, no root bh is an extent block, so this helps
686 * catch code errors with dinode trees. The assertion can be
687 * safely removed if we ever need to insert extent block
688 * structures at the root.
689 */
694 }
698 ocfs2_journal_access_func access)
699 {
711 }
714 }
717 {
720 }
723 {
726 }
728 /*
729 * Journal the buffer at depth idx. All idx>0 are extent_blocks,
730 * otherwise it's the root_access function.
731 *
732 * I don't like the way this function's name looks next to
733 * ocfs2_journal_access_path(), but I don't have a better one.
734 */
739 {
749 OCFS2_JOURNAL_ACCESS_WRITE);
750 }
752 /*
753 * Convenience function to journal all components in a path.
754 */
758 {
769 }
770 }
772 out:
774 }
776 /*
777 * Return the index of the extent record which contains cluster #v_cluster.
778 * -1 is returned if it was not found.
779 *
780 * Should work fine on interior and exterior nodes.
781 */
783 {
800 }
801 }
804 }
806 /*
807 * NOTE: ocfs2_block_extent_contig(), ocfs2_extents_adjacent() and
808 * ocfs2_extent_rec_contig only work properly against leaf nodes!
809 */
812 u64 blkno)
813 {
820 }
824 {
825 u32 left_range;
831 }
833 static enum ocfs2_contig_type
837 {
840 /*
841 * Refuse to coalesce extent records with different flag
842 * fields - we don't want to mix unwritten extents with user
843 * data.
844 */
858 }
860 /*
861 * NOTE: We can have pretty much any combination of contiguousness and
862 * appending.
863 *
864 * The usefulness of APPEND_TAIL is more in that it lets us know that
865 * we'll have to update the path to that leaf.
866 */
869 APPEND_TAIL,
870 };
874 SPLIT_LEFT,
875 SPLIT_RIGHT,
876 };
884 };
890 };
894 {
903 /*
904 * If the ecc fails, we return the error but otherwise
905 * leave the filesystem running. We know any error is
906 * local to this block.
907 */
913 }
915 /*
916 * Errors after here are fatal.
917 */
925 }
933 }
941 }
942 bail:
944 }
948 {
953 ocfs2_validate_extent_block);
955 /* If ocfs2_read_block() got us a new bh, pass it up. */
960 }
963 /*
964 * How many free extents have we got before we need more meta data?
965 */
967 {
983 }
986 }
991 bail:
996 }
998 /* expects array to already be allocated
999 *
1000 * sets h_signature, h_blkno, h_suballoc_bit, h_suballoc_slot, and
1001 * l_count for you
1002 */
1008 {
1010 u16 suballoc_bit_start;
1011 u32 num_got;
1020 meta_ac,
1029 }
1037 }
1042 OCFS2_JOURNAL_ACCESS_CREATE);
1046 }
1050 /* Ok, setup the minimal stuff here. */
1061 suballoc_bit_start++;
1062 first_blkno++;
1064 /* We'll also be dirtied by the caller, so
1065 * this isn't absolutely necessary. */
1067 }
1070 }
1073 bail:
1078 }
1080 }
1082 }
1084 /*
1085 * Helper function for ocfs2_add_branch() and ocfs2_shift_tree_depth().
1086 *
1087 * Returns the sum of the rightmost extent rec logical offset and
1088 * cluster count.
1089 *
1090 * ocfs2_add_branch() uses this to determine what logical cluster
1091 * value should be populated into the leftmost new branch records.
1092 *
1093 * ocfs2_shift_tree_depth() uses this to determine the # clusters
1094 * value for the new topmost tree record.
1095 */
1097 {
1104 }
1106 /*
1107 * Change range of the branches in the right most path according to the leaf
1108 * extent block's rightmost record.
1109 */
1112 {
1122 }
1128 }
1134 }
1140 }
1147 out:
1150 }
1152 /*
1153 * Add an entire tree branch to our inode. eb_bh is the extent block
1154 * to start at, if we don't want to start the branch at the root
1155 * structure.
1156 *
1157 * last_eb_bh is required as we have to update it's next_leaf pointer
1158 * for the new last extent block.
1159 *
1160 * the new branch will be 'empty' in the sense that every block will
1161 * contain a single record with cluster count == 0.
1162 */
1168 {
1186 /* we never add a branch to a leaf. */
1195 /*
1196 * If there is a gap before the root end and the real end
1197 * of the righmost leaf block, we need to remove the gap
1198 * between new_cpos and root_end first so that the tree
1199 * is consistent after we add a new branch(it will start
1200 * from new_cpos).
1201 */
1212 }
1213 }
1215 /* allocate the number of new eb blocks we need */
1217 GFP_KERNEL);
1222 }
1224 /* Firstyly, try to reuse dealloc since we have already estimated how
1225 * many extent blocks we may use.
1226 */
1234 }
1235 }
1243 meta_ac,
1248 }
1249 }
1251 /* Note: new_eb_bhs[new_blocks - 1] is the guy which will be
1252 * linked with the rest of the tree.
1253 * conversly, new_eb_bhs[0] is the new bottommost leaf.
1254 *
1255 * when we leave the loop, new_last_eb_blk will point to the
1256 * newest leaf, and next_blkno will point to the topmost extent
1257 * block. */
1262 /* ocfs2_create_new_meta_bhs() should create it right! */
1267 OCFS2_JOURNAL_ACCESS_CREATE);
1271 }
1276 /*
1277 * This actually counts as an empty extent as
1278 * c_clusters == 0
1279 */
1282 /*
1283 * eb_el isn't always an interior node, but even leaf
1284 * nodes want a zero'd flags and reserved field so
1285 * this gets the whole 32 bits regardless of use.
1286 */
1293 }
1295 /* This is a bit hairy. We want to update up to three blocks
1296 * here without leaving any of them in an inconsistent state
1297 * in case of error. We don't have to worry about
1298 * journal_dirty erroring as it won't unless we've aborted the
1299 * handle (in which case we would never be here) so reserving
1300 * the write with journal_access is all we need to do. */
1302 OCFS2_JOURNAL_ACCESS_WRITE);
1306 }
1308 OCFS2_JOURNAL_ACCESS_WRITE);
1312 }
1315 OCFS2_JOURNAL_ACCESS_WRITE);
1319 }
1320 }
1322 /* Link the new branch into the rest of the tree (el will
1323 * either be on the root_bh, or the extent block passed in. */
1330 /* fe needs a new last extent block pointer, as does the
1331 * next_leaf on the previously last-extent-block. */
1342 /*
1343 * Some callers want to track the rightmost leaf so pass it
1344 * back here.
1345 */
1351 bail:
1356 }
1359 }
1361 /*
1362 * adds another level to the allocation tree.
1363 * returns back the new extent block so you can add a branch to it
1364 * after this call.
1365 */
1370 {
1372 u32 new_clusters;
1388 }
1393 }
1396 /* ocfs2_create_new_meta_bhs() should create it right! */
1403 OCFS2_JOURNAL_ACCESS_CREATE);
1407 }
1409 /* copy the root extent list data into the new extent block */
1418 OCFS2_JOURNAL_ACCESS_WRITE);
1422 }
1426 /* update root_bh now */
1435 /* If this is our 1st tree depth shift, then last_eb_blk
1436 * becomes the allocated extent block */
1445 bail:
1449 }
1451 /*
1452 * Should only be called when there is no space left in any of the
1453 * leaf nodes. What we want to do is find the lowest tree depth
1454 * non-leaf extent block with room for new records. There are three
1455 * valid results of this search:
1456 *
1457 * 1) a lowest extent block is found, then we pass it back in
1458 * *lowest_eb_bh and return '0'
1459 *
1460 * 2) the search fails to find anything, but the root_el has room. We
1461 * pass NULL back in *lowest_eb_bh, but still return '0'
1462 *
1463 * 3) the search fails to find anything AND the root_el is full, in
1464 * which case we return > 0
1465 *
1466 * return status < 0 indicates an error.
1467 */
1470 {
1472 u64 blkno;
1489 }
1498 }
1507 }
1517 }
1518 }
1520 /* If we didn't find one and the fe doesn't have any room,
1521 * then return '1' */
1527 bail:
1531 }
1533 /*
1534 * Grow a b-tree so that it has more records.
1535 *
1536 * We might shift the tree depth in which case existing paths should
1537 * be considered invalid.
1538 *
1539 * Tree depth after the grow is returned via *final_depth.
1540 *
1541 * *last_eb_bh will be updated by ocfs2_add_branch().
1542 */
1546 {
1559 }
1561 /* We traveled all the way to the bottom of the allocation tree
1562 * and didn't find room for any more extents - we need to add
1563 * another tree level */
1569 depth);
1571 /* ocfs2_shift_tree_depth will return us a buffer with
1572 * the new extent block (so we can pass that to
1573 * ocfs2_add_branch). */
1578 }
1579 depth++;
1581 /*
1582 * Special case: we have room now if we shifted from
1583 * tree_depth 0, so no more work needs to be done.
1584 *
1585 * We won't be calling add_branch, so pass
1586 * back *last_eb_bh as the new leaf. At depth
1587 * zero, it should always be null so there's
1588 * no reason to brelse.
1589 */
1594 }
1595 }
1597 /* call ocfs2_add_branch to add the final part of the tree with
1598 * the new data. */
1600 meta_ac);
1604 }
1606 out:
1611 }
1613 /*
1614 * This function will discard the rightmost extent record.
1615 */
1617 {
1623 /* This will cause us to go off the end of our extent list. */
1629 }
1633 {
1643 /* The tree code before us didn't allow enough room in the leaf. */
1646 /*
1647 * The easiest way to approach this is to just remove the
1648 * empty extent and temporarily decrement next_free.
1649 */
1651 /*
1652 * If next_free was 1 (only an empty extent), this
1653 * loop won't execute, which is fine. We still want
1654 * the decrement above to happen.
1655 */
1659 next_free--;
1660 }
1662 /*
1663 * Figure out what the new record index should be.
1664 */
1670 }
1681 /*
1682 * No need to memmove if we're just adding to the tail.
1683 */
1691 num_bytes);
1692 }
1694 /*
1695 * Either we had an empty extent, and need to re-increment or
1696 * there was no empty extent on a non full rightmost leaf node,
1697 * in which case we still need to increment.
1698 */
1699 next_free++;
1701 /*
1702 * Make sure none of the math above just messed up our tree.
1703 */
1708 }
1711 {
1717 num_recs--;
1723 }
1724 }
1726 /*
1727 * Create an empty extent record .
1728 *
1729 * l_next_free_rec may be updated.
1730 *
1731 * If an empty extent already exists do nothing.
1732 */
1734 {
1753 set_and_inc:
1756 }
1758 /*
1759 * For a rotation which involves two leaf nodes, the "root node" is
1760 * the lowest level tree node which contains a path to both leafs. This
1761 * resulting set of information can be used to form a complete "subtree"
1762 *
1763 * This function is passed two full paths from the dinode down to a
1764 * pair of adjacent leaves. It's task is to figure out which path
1765 * index contains the subtree root - this can be the root index itself
1766 * in a worst-case rotation.
1767 *
1768 * The array index of the subtree root is passed back.
1769 */
1773 {
1776 /*
1777 * Check that the caller passed in two paths from the same tree.
1778 */
1782 i++;
1784 /*
1785 * The caller didn't pass two adjacent paths.
1786 */
1798 }
1802 /*
1803 * Traverse a btree path in search of cpos, starting at root_el.
1804 *
1805 * This code can be called with a cpos larger than the tree, in which
1806 * case it will return the rightmost path.
1807 */
1811 {
1813 u32 range;
1814 u64 blkno;
1830 }
1835 /*
1836 * In the case that cpos is off the allocation
1837 * tree, this should just wind up returning the
1838 * rightmost record.
1839 */
1844 }
1854 }
1862 }
1877 }
1881 }
1883 out:
1884 /*
1885 * Catch any trailing bh that the loop didn't handle.
1886 */
1890 }
1892 /*
1893 * Given an initialized path (that is, it has a valid root extent
1894 * list), this function will traverse the btree in search of the path
1895 * which would contain cpos.
1896 *
1897 * The path traveled is recorded in the path structure.
1898 *
1899 * Note that this will not do any comparisons on leaf node extent
1900 * records, so it will work fine in the case that we just added a tree
1901 * branch.
1902 */
1906 };
1908 {
1914 }
1917 {
1924 }
1927 {
1932 /* We want to retain only the leaf block. */
1936 }
1937 }
1938 /*
1939 * Find the leaf block in the tree which would contain cpos. No
1940 * checking of the actual leaf is done.
1941 *
1942 * Some paths want to call this instead of allocating a path structure
1943 * and calling ocfs2_find_path().
1944 *
1945 * This function doesn't handle non btree extent lists.
1946 */
1950 {
1958 }
1961 out:
1963 }
1965 /*
1966 * Adjust the adjacent records (left_rec, right_rec) involved in a rotation.
1967 *
1968 * Basically, we've moved stuff around at the bottom of the tree and
1969 * we need to fix up the extent records above the changes to reflect
1970 * the new changes.
1971 *
1972 * left_rec: the record on the left.
1973 * right_rec: the record to the right of left_rec
1974 * right_child_el: is the child list pointed to by right_rec
1975 *
1976 * By definition, this only works on interior nodes.
1977 */
1981 {
1984 /*
1985 * Interior nodes never have holes. Their cpos is the cpos of
1986 * the leftmost record in their child list. Their cluster
1987 * count covers the full theoretical range of their child list
1988 * - the range between their cpos and the cpos of the record
1989 * immediately to their right.
1990 */
1996 }
2000 /*
2001 * Calculate the rightmost cluster count boundary before
2002 * moving cpos - we will need to adjust clusters after
2003 * updating e_cpos to keep the same highest cluster count.
2004 */
2013 }
2015 /*
2016 * Adjust the adjacent root node records involved in a
2017 * rotation. left_el_blkno is passed in as a key so that we can easily
2018 * find it's index in the root list.
2019 */
2023 u64 left_el_blkno)
2024 {
2033 }
2035 /*
2036 * The path walking code should have never returned a root and
2037 * two paths which are not adjacent.
2038 */
2043 }
2045 /*
2046 * We've changed a leaf block (in right_path) and need to reflect that
2047 * change back up the subtree.
2048 *
2049 * This happens in multiple places:
2050 * - When we've moved an extent record from the left path leaf to the right
2051 * path leaf to make room for an empty extent in the left path leaf.
2052 * - When our insert into the right path leaf is at the leftmost edge
2053 * and requires an update of the path immediately to it's left. This
2054 * can occur at the end of some types of rotation and appending inserts.
2055 * - When we've adjusted the last extent record in the left path leaf and the
2056 * 1st extent record in the right path leaf during cross extent block merge.
2057 */
2062 {
2068 /*
2069 * Update the counts and position values within all the
2070 * interior nodes to reflect the leaf rotation we just did.
2071 *
2072 * The root node is handled below the loop.
2073 *
2074 * We begin the loop with right_el and left_el pointing to the
2075 * leaf lists and work our way up.
2076 *
2077 * NOTE: within this loop, left_el and right_el always refer
2078 * to the *child* lists.
2079 */
2085 /*
2086 * One nice property of knowing that all of these
2087 * nodes are below the root is that we only deal with
2088 * the leftmost right node record and the rightmost
2089 * left node record.
2090 */
2103 /*
2104 * Setup our list pointers now so that the current
2105 * parents become children in the next iteration.
2106 */
2109 }
2111 /*
2112 * At the root node, adjust the two adjacent records which
2113 * begin our path to the leaves.
2114 */
2126 }
2133 {
2151 }
2153 /*
2154 * This extent block may already have an empty record, so we
2155 * return early if so.
2156 */
2164 subtree_index);
2168 }
2176 }
2183 }
2184 }
2189 /* This is a code error, not a disk corruption. */
2199 /* Do the copy now. */
2204 /*
2205 * Clear out the record we just copied and shift everything
2206 * over, leaving an empty extent in the left leaf.
2207 *
2208 * We temporarily subtract from next_free_rec so that the
2209 * shift will lose the tail record (which is now defunct).
2210 */
2219 subtree_index);
2221 out:
2223 }
2225 /*
2226 * Given a full path, determine what cpos value would return us a path
2227 * containing the leaf immediately to the left of the current one.
2228 *
2229 * Will return zero if the path passed in is already the leftmost path.
2230 */
2233 {
2235 u64 blkno;
2244 /* Start at the tree node just above the leaf and work our way up. */
2249 /*
2250 * Find the extent record just before the one in our
2251 * path.
2252 */
2257 /*
2258 * We've determined that the
2259 * path specified is already
2260 * the leftmost one - return a
2261 * cpos of zero.
2262 */
2264 }
2265 /*
2266 * The leftmost record points to our
2267 * leaf - we need to travel up the
2268 * tree one level.
2269 */
2271 }
2278 }
2279 }
2281 /*
2282 * If we got here, we never found a valid node where
2283 * the tree indicated one should be.
2284 */
2290 next_node:
2292 i--;
2293 }
2295 out:
2297 }
2299 /*
2300 * Extend the transaction by enough credits to complete the rotation,
2301 * and still leave at least the original number of credits allocated
2302 * to this transaction.
2303 */
2307 {
2316 }
2318 /*
2319 * Trap the case where we're inserting into the theoretical range past
2320 * the _actual_ left leaf range. Otherwise, we'll rotate a record
2321 * whose cpos is less than ours into the right leaf.
2322 *
2323 * It's only necessary to look at the rightmost record of the left
2324 * leaf because the logic that calls us should ensure that the
2325 * theoretical ranges in the path components above the leaves are
2326 * correct.
2327 */
2329 u32 insert_cpos)
2330 {
2342 }
2345 {
2355 /* Empty list. */
2359 }
2365 }
2367 /*
2368 * Rotate all the records in a btree right one record, starting at insert_cpos.
2369 *
2370 * The path to the rightmost leaf should be passed in.
2371 *
2372 * The array is assumed to be large enough to hold an entire path (tree depth).
2373 *
2374 * Upon successful return from this function:
2375 *
2376 * - The 'right_path' array will contain a path to the leaf block
2377 * whose range contains e_cpos.
2378 * - That leaf block will have a single empty extent in list index 0.
2379 * - In the case that the rotation requires a post-insert update,
2380 * *ret_left_path will contain a valid path which can be passed to
2381 * ocfs2_insert_path().
2382 */
2386 u32 insert_cpos,
2389 {
2391 u32 cpos;
2402 }
2408 }
2414 /*
2415 * What we want to do here is:
2416 *
2417 * 1) Start with the rightmost path.
2418 *
2419 * 2) Determine a path to the leaf block directly to the left
2420 * of that leaf.
2421 *
2422 * 3) Determine the 'subtree root' - the lowest level tree node
2423 * which contains a path to both leaves.
2424 *
2425 * 4) Rotate the subtree.
2426 *
2427 * 5) Find the next subtree by considering the left path to be
2428 * the new right path.
2429 *
2430 * The check at the top of this while loop also accepts
2431 * insert_cpos == cpos because cpos is only a _theoretical_
2432 * value to get us the left path - insert_cpos might very well
2433 * be filling that hole.
2434 *
2435 * Stop at a cpos of '0' because we either started at the
2436 * leftmost branch (i.e., a tree with one branch and a
2437 * rotation inside of it), or we've gone as far as we can in
2438 * rotating subtrees.
2439 */
2450 }
2454 "Owner %llu: error during insert of %u "
2455 "(left path cpos %u) results in two identical "
2464 insert_cpos)) {
2466 /*
2467 * We've rotated the tree as much as we
2468 * should. The rest is up to
2469 * ocfs2_insert_path() to complete, after the
2470 * record insertion. We indicate this
2471 * situation by returning the left path.
2472 *
2473 * The reason we don't adjust the records here
2474 * before the record insert is that an error
2475 * later might break the rule where a parent
2476 * record e_cpos will reflect the actual
2477 * e_cpos of the 1st nonempty record of the
2478 * child list.
2479 */
2482 }
2496 }
2503 }
2507 insert_cpos)) {
2508 /*
2509 * A rotate moves the rightmost left leaf
2510 * record over to the leftmost right leaf
2511 * slot. If we're doing an extent split
2512 * instead of a real insert, then we have to
2513 * check that the extent to be split wasn't
2514 * just moved over. If it was, then we can
2515 * exit here, passing left_path back -
2516 * ocfs2_split_extent() is smart enough to
2517 * search both leaves.
2518 */
2521 }
2523 /*
2524 * There is no need to re-read the next right path
2525 * as we know that it'll be our current left
2526 * path. Optimize by copying values instead.
2527 */
2534 }
2535 }
2537 out:
2540 out_ret_path:
2542 }
2547 {
2552 u32 range;
2558 }
2560 /* Path should always be rightmost. */
2579 }
2580 out:
2582 }
2588 {
2598 /*
2599 * Not all nodes might have had their final count
2600 * decremented by the caller - handle this here.
2601 */
2605 "Inode %llu, attempted to remove extent block "
2614 }
2626 }
2627 }
2635 {
2660 }
2669 {
2687 /*
2688 * It's legal for us to proceed if the right leaf is
2689 * the rightmost one and it has an empty extent. There
2690 * are two cases to handle - whether the leaf will be
2691 * empty after removal or not. If the leaf isn't empty
2692 * then just remove the empty extent up front. The
2693 * next block will handle empty leaves by flagging
2694 * them for unlink.
2695 *
2696 * Non rightmost leaves will throw -EAGAIN and the
2697 * caller can manually move the subtree and retry.
2698 */
2706 OCFS2_JOURNAL_ACCESS_WRITE);
2710 }
2715 }
2719 /*
2720 * We have to update i_last_eb_blk during the meta
2721 * data delete.
2722 */
2724 OCFS2_JOURNAL_ACCESS_WRITE);
2728 }
2731 }
2733 /*
2734 * Getting here with an empty extent in the right path implies
2735 * that it's the rightmost path and will be deleted.
2736 */
2740 subtree_index);
2744 }
2752 }
2759 }
2760 }
2763 /*
2764 * Only do this if we're moving a real
2765 * record. Otherwise, the action is delayed until
2766 * after removal of the right path in which case we
2767 * can do a simple shift to remove the empty extent.
2768 */
2772 }
2774 /*
2775 * Move recs over to get rid of empty extent, decrease
2776 * next_free. This is allowed to remove the last
2777 * extent in our leaf (setting l_next_free_rec to
2778 * zero) - the delete code below won't care.
2779 */
2781 }
2793 }
2798 /*
2799 * Removal of the extent in the left leaf was skipped
2800 * above so we could delete the right path
2801 * 1st.
2802 */
2811 subtree_index);
2813 out:
2815 }
2817 /*
2818 * Given a full path, determine what cpos value would return us a path
2819 * containing the leaf immediately to the right of the current one.
2820 *
2821 * Will return zero if the path passed in is already the rightmost path.
2822 *
2823 * This looks similar, but is subtly different to
2824 * ocfs2_find_cpos_for_left_leaf().
2825 */
2828 {
2830 u64 blkno;
2840 /* Start at the tree node just above the leaf and work our way up. */
2847 /*
2848 * Find the extent record just after the one in our
2849 * path.
2850 */
2856 /*
2857 * We've determined that the
2858 * path specified is already
2859 * the rightmost one - return a
2860 * cpos of zero.
2861 */
2863 }
2864 /*
2865 * The rightmost record points to our
2866 * leaf - we need to travel up the
2867 * tree one level.
2868 */
2870 }
2874 }
2875 }
2877 /*
2878 * If we got here, we never found a valid node where
2879 * the tree indicated one should be.
2880 */
2886 next_node:
2888 i--;
2889 }
2891 out:
2893 }
2898 {
2911 }
2916 out:
2918 }
2926 {
2928 u32 right_cpos;
2942 }
2949 }
2958 }
2965 }
2968 right_path);
2980 }
2982 /*
2983 * Caller might still want to make changes to the
2984 * tree root, so re-add it to the journal here.
2985 */
2991 }
2997 /*
2998 * The rotation has to temporarily stop due to
2999 * the right subtree having an empty
3000 * extent. Pass it back to the caller for a
3001 * fixup.
3002 */
3006 }
3010 }
3012 /*
3013 * The subtree rotate might have removed records on
3014 * the rightmost edge. If so, then rotation is
3015 * complete.
3016 */
3027 }
3028 }
3030 out:
3035 }
3041 {
3043 u32 cpos;
3056 }
3063 }
3066 /*
3067 * We have a path to the left of this one - it needs
3068 * an update too.
3069 */
3075 }
3081 }
3087 }
3097 }
3102 /*
3103 * 'path' is also the leftmost path which
3104 * means it must be the only one. This gets
3105 * handled differently because we want to
3106 * revert the root back to having extents
3107 * in-line.
3108 */
3117 }
3121 out:
3124 }
3130 {
3140 }
3148 }
3150 /*
3151 * Left rotation of btree records.
3152 *
3153 * In many ways, this is (unsurprisingly) the opposite of right
3154 * rotation. We start at some non-rightmost path containing an empty
3155 * extent in the leaf block. The code works its way to the rightmost
3156 * path by rotating records to the left in every subtree.
3157 *
3158 * This is used by any code which reduces the number of extent records
3159 * in a leaf. After removal, an empty record should be placed in the
3160 * leftmost list position.
3161 *
3162 * This won't handle a length update of the rightmost path records if
3163 * the rightmost tree leaf record is removed so the caller is
3164 * responsible for detecting and correcting that.
3165 */
3170 {
3181 rightmost_no_delete:
3182 /*
3183 * Inline extents. This is trivially handled, so do
3184 * it up front.
3185 */
3190 }
3192 /*
3193 * Handle rightmost branch now. There's several cases:
3194 * 1) simple rotation leaving records in there. That's trivial.
3195 * 2) rotation requiring a branch delete - there's no more
3196 * records left. Two cases of this:
3197 * a) There are branches to the left.
3198 * b) This is also the leftmost (the only) branch.
3199 *
3200 * 1) is handled via ocfs2_rotate_rightmost_leaf_left()
3201 * 2a) we need the left branch so that we can update it with the unlink
3202 * 2b) we need to bring the root back to inline extents.
3203 */
3208 /*
3209 * This gets a bit tricky if we're going to delete the
3210 * rightmost path. Get the other cases out of the way
3211 * 1st.
3212 */
3223 }
3225 /*
3226 * XXX: The caller can not trust "path" any more after
3227 * this as it will have been deleted. What do we do?
3228 *
3229 * In theory the rotate-for-merge code will never get
3230 * here because it'll always ask for a rotate in a
3231 * nonempty list.
3232 */
3235 dealloc);
3239 }
3241 /*
3242 * Now we can loop, remembering the path we get from -EAGAIN
3243 * and restarting from there.
3244 */
3245 try_rotate:
3251 }
3263 }
3270 }
3272 out:
3276 }
3280 {
3285 /*
3286 * We consumed all of the merged-from record. An empty
3287 * extent cannot exist anywhere but the 1st array
3288 * position, so move things over if the merged-from
3289 * record doesn't occupy that position.
3290 *
3291 * This creates a new empty extent so the caller
3292 * should be smart enough to have removed any existing
3293 * ones.
3294 */
3299 }
3301 /*
3302 * Always memset - the caller doesn't check whether it
3303 * created an empty extent, so there could be junk in
3304 * the other fields.
3305 */
3307 }
3308 }
3313 {
3315 u32 right_cpos;
3321 /* This function shouldn't be called for non-trees. */
3332 }
3334 /* This function shouldn't be called for the rightmost leaf. */
3342 }
3348 }
3351 out:
3355 }
3357 /*
3358 * Remove split_rec clusters from the record at index and merge them
3359 * onto the beginning of the record "next" to it.
3360 * For index < l_count - 1, the next means the extent rec at index + 1.
3361 * For index == l_count - 1, the "next" means the 1st extent rec of the
3362 * next extent block.
3363 */
3369 {
3386 /* we meet with a cross extent block merge. */
3391 }
3400 }
3407 right_path);
3411 right_path);
3415 }
3421 subtree_index);
3425 }
3434 }
3441 }
3442 }
3447 }
3454 }
3461 split_clusters));
3470 subtree_index);
3471 }
3472 out:
3475 }
3480 {
3482 u32 left_cpos;
3487 /* This function shouldn't be called for non-trees. */
3495 }
3497 /* This function shouldn't be called for the leftmost leaf. */
3505 }
3511 }
3514 out:
3518 }
3520 /*
3521 * Remove split_rec clusters from the record at index and merge them
3522 * onto the tail of the record "before" it.
3523 * For index > 0, the "before" means the extent rec at index - 1.
3524 *
3525 * For index == 0, the "before" means the last record of the previous
3526 * extent block. And there is also a situation that we may need to
3527 * remove the rightmost leaf extent block in the right_path and change
3528 * the right path to indicate the new rightmost path.
3529 */
3536 {
3551 /* we meet with a cross extent block merge. */
3556 }
3569 right_path);
3573 left_path);
3577 }
3583 subtree_index);
3587 }
3596 }
3603 }
3604 }
3609 }
3616 }
3619 /*
3620 * The easy case - we can just plop the record right in.
3621 */
3629 split_clusters));
3638 /*
3639 * In the situation that the right_rec is empty and the extent
3640 * block is empty also, ocfs2_complete_edge_insert can't handle
3641 * it and we need to delete the right extent block.
3642 */
3645 /* extend credit for ocfs2_remove_rightmost_path */
3648 right_path);
3652 }
3655 right_path,
3656 dealloc);
3660 }
3662 /* Now the rightmost extent block has been deleted.
3663 * So we use the new rightmost path.
3664 */
3670 }
3671 out:
3674 }
3683 {
3691 /* extend credit for ocfs2_remove_rightmost_path */
3694 path);
3698 }
3699 /*
3700 * The merge code will need to create an empty
3701 * extent to take the place of the newly
3702 * emptied slot. Remove any pre-existing empty
3703 * extents - having more than one in a leaf is
3704 * illegal.
3705 */
3710 }
3711 split_index--;
3713 }
3716 /*
3717 * Left-right contig implies this.
3718 */
3721 /*
3722 * Since the leftright insert always covers the entire
3723 * extent, this call will delete the insert record
3724 * entirely, resulting in an empty extent record added to
3725 * the extent block.
3726 *
3727 * Since the adding of an empty extent shifts
3728 * everything back to the right, there's no need to
3729 * update split_index here.
3730 *
3731 * When the split_index is zero, we need to merge it to the
3732 * prevoius extent block. It is more efficient and easier
3733 * if we do merge_right first and merge_left later.
3734 */
3736 split_index);
3740 }
3742 /*
3743 * We can only get this from logic error above.
3744 */
3747 /* extend credit for ocfs2_remove_rightmost_path */
3750 path);
3754 }
3756 /* The merge left us with an empty extent, remove it. */
3761 }
3765 /*
3766 * Note that we don't pass split_rec here on purpose -
3767 * we've merged it into the rec already.
3768 */
3775 }
3777 /* extend credit for ocfs2_remove_rightmost_path */
3780 path);
3784 }
3787 /*
3788 * Error from this last rotate is not critical, so
3789 * print but don't bubble it up.
3790 */
3795 /*
3796 * Merge a record to the left or right.
3797 *
3798 * 'contig_type' is relative to the existing record,
3799 * so for example, if we're "right contig", it's to
3800 * the record on the left (hence the left merge).
3801 */
3805 split_index);
3809 }
3813 split_index);
3817 }
3818 }
3821 /* extend credit for ocfs2_remove_rightmost_path */
3824 path);
3829 }
3831 /*
3832 * The merge may have left an empty extent in
3833 * our leaf. Try to rotate it away.
3834 */
3836 dealloc);
3840 }
3841 }
3843 out:
3845 }
3851 {
3852 u64 len_blocks;
3858 /*
3859 * Region is on the left edge of the existing
3860 * record.
3861 */
3868 /*
3869 * Region is on the right edge of the existing
3870 * record.
3871 */
3874 }
3875 }
3877 /*
3878 * Do the final bits of extent record insertion at the target leaf
3879 * list. If this leaf is part of an allocation tree, it is assumed
3880 * that the tree above has been prepared.
3881 */
3886 {
3899 insert_rec);
3901 }
3903 /*
3904 * Contiguous insert - either left or right.
3905 */
3911 }
3915 }
3917 /*
3918 * Handle insert into an empty leaf.
3919 */
3926 }
3928 /*
3929 * Appending insert.
3930 */
3940 "owner %llu, depth %u, count %u, next free %u, "
3941 "rec.cpos %u, rec.clusters %u, "
3951 i++;
3955 }
3957 rotate:
3958 /*
3959 * Ok, we have to rotate.
3960 *
3961 * At this point, it is safe to assume that inserting into an
3962 * empty leaf and appending to a leaf have both been handled
3963 * above.
3964 *
3965 * This leaf needs to have space, either by the empty 1st
3966 * extent record, or by virtue of an l_next_rec < l_count.
3967 */
3969 }
3975 {
3981 /*
3982 * Update everything except the leaf block.
3983 */
3994 }
4005 }
4006 }
4013 {
4020 /*
4021 * This shouldn't happen for non-trees. The extent rec cluster
4022 * count manipulation below only works for interior nodes.
4023 */
4026 /*
4027 * If our appending insert is at the leftmost edge of a leaf,
4028 * then we might need to update the rightmost records of the
4029 * neighboring path.
4030 */
4035 u32 left_cpos;
4042 }
4048 left_cpos);
4050 /*
4051 * No need to worry if the append is already in the
4052 * leftmost leaf.
4053 */
4060 }
4063 left_cpos);
4067 }
4069 /*
4070 * ocfs2_insert_path() will pass the left_path to the
4071 * journal for us.
4072 */
4073 }
4074 }
4080 }
4086 out:
4091 }
4098 {
4115 /*
4116 * This typically means that the record
4117 * started in the left path but moved to the
4118 * right as a result of rotation. We either
4119 * move the existing record to the left, or we
4120 * do the later insert there.
4121 *
4122 * In this case, the left path should always
4123 * exist as the rotate code will have passed
4124 * it back for a post-insert update.
4125 */
4128 /*
4129 * It's a left split. Since we know
4130 * that the rotate code gave us an
4131 * empty extent in the left path, we
4132 * can just do the insert there.
4133 */
4136 /*
4137 * Right split - we have to move the
4138 * existing record over to the left
4139 * leaf. The insert will be into the
4140 * newly created empty extent in the
4141 * right leaf.
4142 */
4150 }
4151 }
4155 /*
4156 * Left path is easy - we can just allow the insert to
4157 * happen.
4158 */
4163 }
4169 }
4171 /*
4172 * This function only does inserts on an allocation b-tree. For tree
4173 * depth = 0, ocfs2_insert_at_leaf() is called directly.
4174 *
4175 * right_path is the path we want to do the actual insert
4176 * in. left_path should only be passed in if we need to update that
4177 * portion of the tree after an edge insert.
4178 */
4185 {
4190 /*
4191 * There's a chance that left_path got passed back to
4192 * us without being accounted for in the
4193 * journal. Extend our transaction here to be sure we
4194 * can change those blocks.
4195 */
4200 }
4206 }
4207 }
4209 /*
4210 * Pass both paths to the journal. The majority of inserts
4211 * will be touching all components anyway.
4212 */
4217 }
4220 /*
4221 * We could call ocfs2_insert_at_leaf() for some types
4222 * of splits, but it's easier to just let one separate
4223 * function sort it all out.
4224 */
4228 /*
4229 * Split might have modified either leaf and we don't
4230 * have a guarantee that the later edge insert will
4231 * dirty this for us.
4232 */
4238 insert);
4243 /*
4244 * The rotate code has indicated that we need to fix
4245 * up portions of the tree after the insert.
4246 *
4247 * XXX: Should we extend the transaction here?
4248 */
4250 right_path);
4252 subtree_index);
4253 }
4256 out:
4258 }
4264 {
4266 u32 cpos;
4274 OCFS2_JOURNAL_ACCESS_WRITE);
4278 }
4283 }
4290 }
4292 /*
4293 * Determine the path to start with. Rotations need the
4294 * rightmost path, everything else can go directly to the
4295 * target leaf.
4296 */
4302 }
4308 }
4310 /*
4311 * Rotations and appends need special treatment - they modify
4312 * parts of the tree's above them.
4313 *
4314 * Both might pass back a path immediate to the left of the
4315 * one being inserted to. This will be cause
4316 * ocfs2_insert_path() to modify the rightmost records of
4317 * left_path to account for an edge insert.
4318 *
4319 * XXX: When modifying this code, keep in mind that an insert
4320 * can wind up skipping both of these two special cases...
4321 */
4329 }
4331 /*
4332 * ocfs2_rotate_tree_right() might have extended the
4333 * transaction without re-journaling our tree root.
4334 */
4336 OCFS2_JOURNAL_ACCESS_WRITE);
4340 }
4348 }
4349 }
4356 }
4358 out_update_clusters:
4365 out:
4370 }
4377 {
4401 }
4404 left_cpos);
4415 "Extent block #%llu has an invalid l_next_free_rec of %d. It should have matched the l_count of %d\n",
4421 }
4424 }
4425 }
4427 /*
4428 * We're careful to check for an empty extent record here -
4429 * the merge code will know what to do if it sees one.
4430 */
4437 }
4438 }
4457 }
4475 }
4477 }
4478 }
4489 }
4491 free_right_path:
4493 free_left_path:
4495 exit:
4500 }
4506 {
4514 insert_rec);
4518 }
4519 }
4528 /*
4529 * Caller might want us to limit the size of extents, don't
4530 * calculate contiguousness if we might exceed that limit.
4531 */
4535 }
4536 }
4538 /*
4539 * This should only be called against the righmost leaf extent list.
4540 *
4541 * ocfs2_figure_appending_type() will figure out whether we'll have to
4542 * insert at the tail of the rightmost leaf.
4543 *
4544 * This should also work against the root extent list for tree's with 0
4545 * depth. If we consider the root extent list to be the rightmost leaf node
4546 * then the logic here makes sense.
4547 */
4551 {
4564 /* Were all records empty? */
4567 }
4578 set_tail_append:
4580 }
4582 /*
4583 * Helper function called at the beginning of an insert.
4584 *
4585 * This computes a few things that are commonly used in the process of
4586 * inserting into the btree:
4587 * - Whether the new extent is contiguous with an existing one.
4588 * - The current tree depth.
4589 * - Whether the insert is an appending one.
4590 * - The total # of free records in the tree.
4591 *
4592 * All of the information is stored on the ocfs2_insert_type
4593 * structure.
4594 */
4600 {
4613 /*
4614 * If we have tree depth, we read in the
4615 * rightmost extent block ahead of time as
4616 * ocfs2_figure_insert_type() and ocfs2_add_branch()
4617 * may want it later.
4618 */
4625 }
4628 }
4630 /*
4631 * Unless we have a contiguous insert, we'll need to know if
4632 * there is room left in our allocation tree for another
4633 * extent record.
4634 *
4635 * XXX: This test is simplistic, we can search for empty
4636 * extent records too.
4637 */
4645 }
4652 }
4654 /*
4655 * In the case that we're inserting past what the tree
4656 * currently accounts for, ocfs2_find_path() will return for
4657 * us the rightmost tree path. This is accounted for below in
4658 * the appending code.
4659 */
4664 }
4668 /*
4669 * Now that we have the path, there's two things we want to determine:
4670 * 1) Contiguousness (also set contig_index if this is so)
4671 *
4672 * 2) Are we doing an append? We can trivially break this up
4673 * into two types of appends: simple record append, or a
4674 * rotate inside the tail leaf.
4675 */
4678 /*
4679 * The insert code isn't quite ready to deal with all cases of
4680 * left contiguousness. Specifically, if it's an insert into
4681 * the 1st record in a leaf, it will require the adjustment of
4682 * cluster count on the last record of the path directly to it's
4683 * left. For now, just catch that case and fool the layers
4684 * above us. This works just fine for tree_depth == 0, which
4685 * is why we allow that above.
4686 */
4691 /*
4692 * Ok, so we can simply compare against last_eb to figure out
4693 * whether the path doesn't exist. This will only happen in
4694 * the case that we're doing a tail append, so maybe we can
4695 * take advantage of that information somehow.
4696 */
4699 /*
4700 * Ok, ocfs2_find_path() returned us the rightmost
4701 * tree path. This might be an appending insert. There are
4702 * two cases:
4703 * 1) We're doing a true append at the tail:
4704 * -This might even be off the end of the leaf
4705 * 2) We're "appending" by rotating in the tail
4706 */
4708 }
4710 out:
4715 else
4718 }
4720 /*
4721 * Insert an extent into a btree.
4722 *
4723 * The caller needs to update the owning btree's cluster count.
4724 */
4727 u32 cpos,
4728 u64 start_blk,
4729 u32 new_clusters,
4730 u8 flags,
4732 {
4752 }
4759 }
4768 meta_ac);
4772 }
4773 }
4775 /* Finally, we can add clusters. This might rotate the tree for us. */
4779 else
4782 bail:
4786 }
4788 /*
4789 * Allcate and add clusters into the extent b-tree.
4790 * The new clusters(clusters_to_add) will be inserted at logical_offset.
4791 * The extent b-tree's root is specified by et, and
4792 * it is not limited to the file storage. Any extent tree can use this
4793 * function if it implements the proper ocfs2_extent_tree.
4794 */
4798 u32 clusters_to_add,
4803 {
4809 u64 block;
4824 }
4826 /* there are two cases which could cause us to EAGAIN in the
4827 * we-need-more-metadata case:
4828 * 1) we haven't reserved *any*
4829 * 2) we are so fragmented, we've needed to add metadata too
4830 * many times. */
4843 }
4851 }
4855 /* reserve our write early -- insert_extent may update the tree root */
4857 OCFS2_JOURNAL_ACCESS_WRITE);
4862 }
4874 }
4885 }
4887 bail:
4892 else
4897 num_bits);
4898 }
4900 leave:
4905 }
4909 u32 cpos,
4911 {
4925 }
4934 {
4944 leftright:
4945 /*
4946 * Store a copy of the record on the stack - it might move
4947 * around as the tree is manipulated below.
4948 */
4958 }
4967 }
4968 }
4985 /*
4986 * Left/right split. We fake this as a right split
4987 * first and then make a second pass as a left split.
4988 */
4998 }
5004 }
5007 u32 cpos;
5010 do_leftright++;
5020 }
5028 cpos);
5031 }
5033 }
5034 out:
5037 }
5045 {
5053 }
5058 out:
5060 }
5062 /*
5063 * Split part or all of the extent record at split_index in the leaf
5064 * pointed to by path. Merge with the contiguous extent record if needed.
5065 *
5066 * Care is taken to handle contiguousness so as to not grow the tree.
5067 *
5068 * meta_ac is not strictly necessary - we only truly need it if growth
5069 * of the tree is required. All other cases will degrade into a less
5070 * optimal tree layout.
5071 *
5072 * last_eb_bh should be the rightmost leaf block for any extent
5073 * btree. Since a split may grow the tree or a merge might shrink it,
5074 * the caller cannot trust the contents of that buffer after this call.
5075 *
5076 * This code is optimized for readability - several passes might be
5077 * made over certain portions of the tree. All of those blocks will
5078 * have been brought into cache (and pinned via the journal), so the
5079 * extra overhead is not expressed in terms of disk reads.
5080 */
5088 {
5101 }
5104 split_index,
5105 split_rec,
5110 }
5112 /*
5113 * The core merge / split code wants to know how much room is
5114 * left in this allocation tree, so we pass the
5115 * rightmost extent list.
5116 */
5126 }
5129 }
5134 else
5147 else
5159 }
5161 out:
5164 }
5166 /*
5167 * Change the flags of the already-existing extent at cpos for len clusters.
5168 *
5169 * new_flags: the flags we want to set.
5170 * clear_flags: the flags we want to clear.
5171 * phys: the new physical offset we want this new extent starts from.
5172 *
5173 * If the existing extent is larger than the request, initiate a
5174 * split. An attempt will be made at merging with adjacent extents.
5175 *
5176 * The caller is responsible for passing down meta_ac if we'll need it.
5177 */
5184 {
5198 }
5204 }
5212 cpos);
5215 }
5223 new_flags);
5225 }
5231 clear_flags);
5233 }
5247 dealloc);
5251 out:
5255 }
5257 /*
5258 * Mark the already-existing extent at cpos as written for len clusters.
5259 * This removes the unwritten extent flag.
5260 *
5261 * If the existing extent is larger than the request, initiate a
5262 * split. An attempt will be made at merging with adjacent extents.
5263 *
5264 * The caller is responsible for passing down meta_ac if we'll need it.
5265 */
5271 {
5279 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",
5283 }
5285 /*
5286 * XXX: This should be fixed up so that we just re-insert the
5287 * next extent records.
5288 */
5297 out:
5299 }
5305 {
5314 /*
5315 * Setup the record to split before we grow the tree.
5316 */
5330 }
5343 }
5348 meta_ac);
5352 }
5353 }
5365 out:
5368 }
5375 {
5386 /* extend credit for ocfs2_remove_rightmost_path */
5389 path);
5393 }
5399 }
5401 index--;
5402 }
5406 /*
5407 * Check whether this is the rightmost tree record. If
5408 * we remove all of this record or part of its right
5409 * edge then an update of the record lengths above it
5410 * will be required.
5411 */
5415 }
5420 /*
5421 * Changing the leftmost offset (via partial or whole
5422 * record truncate) of an interior (or rightmost) path
5423 * means we have to update the subtree that is formed
5424 * by this leaf and the one to it's left.
5425 *
5426 * There are two cases we can skip:
5427 * 1) Path is the leftmost one in our btree.
5428 * 2) The leaf is rightmost and will be empty after
5429 * we remove the extent record - the rotate code
5430 * knows how to update the newly formed edge.
5431 */
5437 }
5445 }
5448 left_cpos);
5452 }
5453 }
5454 }
5458 path);
5462 }
5468 }
5474 }
5487 /*
5488 * We skip the edge update if this path will
5489 * be deleted by the rotate code.
5490 */
5493 rec);
5494 }
5496 /* Remove leftmost portion of the record. */
5501 /* Remove rightmost portion of the record */
5506 /* Caller should have trapped this. */
5513 }
5520 subtree_index);
5521 }
5529 }
5531 out:
5534 }
5541 {
5548 /*
5549 * XXX: Why are we truncating to 0 instead of wherever this
5550 * affects us?
5551 */
5559 }
5565 }
5573 cpos);
5576 }
5578 /*
5579 * We have 3 cases of extent removal:
5580 * 1) Range covers the entire extent rec
5581 * 2) Range begins or ends on one edge of the extent rec
5582 * 3) Range is in the middle of the extent rec (no shared edges)
5583 *
5584 * For case 1 we remove the extent rec and left rotate to
5585 * fill the hole.
5586 *
5587 * For case 2 we just shrink the existing extent rec, with a
5588 * tree update if the shrinking edge is also the edge of an
5589 * extent block.
5590 *
5591 * For case 3 we do a right split to turn the extent rec into
5592 * something case 2 can handle.
5593 */
5611 }
5618 }
5620 /*
5621 * The split could have manipulated the tree enough to
5622 * move the record location, so we have to look for it again.
5623 */
5630 }
5638 cpos);
5641 }
5643 /*
5644 * Double check our values here. If anything is fishy,
5645 * it's easier to catch it at the top level.
5646 */
5658 }
5665 }
5666 }
5668 out:
5671 }
5673 /*
5674 * ocfs2_reserve_blocks_for_rec_trunc() would look basically the
5675 * same as ocfs2_lock_alloctors(), except for it accepts a blocks
5676 * number to reserve some extra blocks, and it only handles meta
5677 * data allocations.
5678 *
5679 * Currently, only ocfs2_remove_btree_range() uses it for truncating
5680 * and punching holes.
5681 */
5684 u32 extents_to_split,
5687 {
5699 }
5711 }
5712 }
5714 out:
5719 }
5720 }
5723 }
5730 {
5748 }
5749 }
5752 refcount_loc,
5753 phys_blkno,
5754 len,
5760 }
5761 }
5764 extra_blocks);
5768 }
5777 }
5778 }
5786 }
5789 OCFS2_JOURNAL_ACCESS_WRITE);
5793 }
5802 }
5813 phys_blkno),
5816 else
5822 }
5824 out_commit:
5826 out:
5828 bail:
5836 }
5839 {
5848 "slot %d, invalid truncate log parameters: used = "
5852 }
5856 {
5860 /* No records, nothing to coalesce */
5869 }
5873 u64 start_blk,
5875 {
5889 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5890 * by the underlying call to ocfs2_read_inode_block(), so any
5891 * corruption is a code bug */
5898 "Truncate record count on #%llu invalid "
5904 /* Caller should have known to flush before calling us. */
5910 }
5913 OCFS2_JOURNAL_ACCESS_WRITE);
5917 }
5923 /*
5924 * Move index back to the record we are coalescing with.
5925 * ocfs2_truncate_log_can_coalesce() guarantees nonzero
5926 */
5927 index--;
5933 num_clusters);
5937 }
5943 bail:
5945 }
5950 {
5954 u64 start_blk;
5971 }
5973 /* Caller has given us at least enough credits to
5974 * update the truncate log dinode */
5976 OCFS2_JOURNAL_ACCESS_WRITE);
5980 }
5991 /* if start_blk is not set, we ignore the record as
5992 * invalid. */
6000 num_clusters);
6004 }
6005 }
6008 i--;
6009 }
6013 bail:
6015 }
6017 /* Expects you to already be holding tl_inode->i_mutex */
6019 {
6033 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
6034 * by the underlying call to ocfs2_read_inode_block(), so any
6035 * corruption is a code bug */
6042 num_to_flush);
6046 }
6049 GLOBAL_BITMAP_SYSTEM_INODE,
6050 OCFS2_INVALID_SLOT);
6055 }
6063 }
6066 data_alloc_bh);
6073 out_mutex:
6077 out:
6079 }
6082 {
6091 }
6094 {
6103 else
6105 }
6107 #define OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL (2 * HZ)
6110 {
6113 /* We want to push off log flushes while truncates are
6114 * still running. */
6119 OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL);
6120 }
6121 }
6123 /*
6124 * Try to flush truncate logs if we can free enough clusters from it.
6125 * As for return value, "< 0" means error, "0" no space and "1" means
6126 * we have freed enough spaces and let the caller try to allocate again.
6127 */
6130 {
6131 tid_t target;
6139 /*
6140 * Check whether we can succeed in allocating if we free
6141 * the truncate log.
6142 */
6150 }
6155 }
6156 out:
6158 }
6164 {
6170 TRUNCATE_LOG_SYSTEM_INODE,
6171 slot_num);
6176 }
6183 }
6187 bail:
6189 }
6191 /* called during the 1st stage of node recovery. we stamp a clean
6192 * truncate log and pass back a copy for processing later. if the
6193 * truncate log does not require processing, a *tl_copy is set to
6194 * NULL. */
6198 {
6213 }
6217 /* tl_bh is loaded from ocfs2_get_truncate_log_info(). It's
6218 * validated by the underlying call to ocfs2_read_inode_block(),
6219 * so any corruption is a code bug */
6231 }
6233 /* Assuming the write-out below goes well, this copy
6234 * will be passed back to recovery for processing. */
6237 /* All we need to do to clear the truncate log is set
6238 * tl_used. */
6246 }
6247 }
6249 bail:
6257 }
6260 }
6264 {
6268 u64 start_blk;
6276 }
6282 num_recs);
6291 }
6292 }
6299 }
6311 }
6312 }
6314 bail_up:
6318 }
6321 {
6337 }
6338 }
6341 {
6353 /* ocfs2_truncate_log_shutdown keys on the existence of
6354 * osb->osb_tl_inode so we don't set any of the osb variables
6355 * until we're sure all is well. */
6357 ocfs2_truncate_log_worker);
6363 }
6365 /*
6366 * Delayed de-allocation of suballocator blocks.
6367 *
6368 * Some sets of block de-allocations might involve multiple suballocator inodes.
6369 *
6370 * The locking for this can get extremely complicated, especially when
6371 * the suballocator inodes to delete from aren't known until deep
6372 * within an unrelated codepath.
6373 *
6374 * ocfs2_extent_block structures are a good example of this - an inode
6375 * btree could have been grown by any number of nodes each allocating
6376 * out of their own suballoc inode.
6377 *
6378 * These structures allow the delay of block de-allocation until a
6379 * later time, when locking of multiple cluster inodes won't cause
6380 * deadlock.
6381 */
6383 /*
6384 * Describe a single bit freed from a suballocator. For the block
6385 * suballocators, it represents one block. For the global cluster
6386 * allocator, it represents some clusters and free_bit indicates
6387 * clusters number.
6388 */
6391 u64 free_bg;
6392 u64 free_blk;
6394 };
6401 };
6407 {
6409 u64 bg_blkno;
6420 }
6428 }
6433 else
6441 }
6456 }
6458 out_unlock:
6461 out_mutex:
6464 out:
6466 /* Premature exit may have left some dangling items. */
6470 }
6473 }
6477 {
6486 }
6496 }
6500 {
6514 }
6515 }
6522 }
6535 }
6536 }
6541 /* Premature exit may have left some dangling items. */
6545 }
6548 }
6552 {
6573 }
6577 }
6588 }
6591 }
6597 {
6605 }
6615 }
6617 }
6624 {
6631 }
6634 }
6636 /* If we can't find any free list matching preferred slot, just use
6637 * the first one.
6638 */
6643 }
6645 /* Return Value 1 indicates empty */
6647 {
6661 }
6663 /* If extent was deleted from tree due to extent rotation and merging, and
6664 * no metadata is reserved ahead of time. Try to reuse some extents
6665 * just deleted. This is only used to reuse extent blocks.
6666 * It is supposed to find enough extent blocks in dealloc if our estimation
6667 * on metadata is accurate.
6668 */
6673 {
6684 /* If extent tree doesn't have a dealloc, this is not faulty. Just
6685 * tell upper caller dealloc can't provide any block and it should
6686 * ask for alloc to claim more space.
6687 */
6693 /* Prefer to use local slot */
6696 dealloc);
6697 /* If no more block can be reused, we should claim more
6698 * from alloc. Just return here normally.
6699 */
6703 }
6713 }
6723 OCFS2_JOURNAL_ACCESS_CREATE);
6727 }
6732 /* We can't guarantee that buffer head is still cached, so
6733 * polutlate the extent block again.
6734 */
6744 /* We'll also be dirtied by the caller, so
6745 * this isn't absolutely necessary.
6746 */
6752 }
6754 }
6758 bail:
6762 }
6765 }
6770 {
6780 }
6787 }
6801 out:
6803 }
6807 {
6813 }
6816 {
6820 }
6825 {
6835 /*
6836 * Need to set the buffers we zero'd into uptodate
6837 * here if they aren't - ocfs2_map_page_blocks()
6838 * might've skipped some
6839 */
6842 ocfs2_zero_func);
6849 }
6855 }
6860 {
6886 }
6887 out:
6890 }
6894 {
6898 loff_t last_page_bytes;
6911 }
6913 numpages++;
6914 index++;
6917 out:
6922 }
6927 }
6931 {
6938 }
6940 /*
6941 * Zero the area past i_size but still within an allocated
6942 * cluster. This avoids exposing nonzero data on subsequent file
6943 * extends.
6944 *
6945 * We need to call this before i_size is updated on the inode because
6946 * otherwise block_write_full_page() will skip writeout of pages past
6947 * i_size. The new_i_size parameter is passed for this reason.
6948 */
6951 {
6954 u64 phys;
6958 /*
6959 * File systems which don't support sparse files zero on every
6960 * extend.
6961 */
6971 }
6982 }
6984 /*
6985 * Tail is a hole, or is marked unwritten. In either case, we
6986 * can count on read and write to return/push zero's.
6987 */
6996 }
7001 /*
7002 * Initiate writeout of the pages we zero'd here. We don't
7003 * wait on them - the truncate_inode_pages() call later will
7004 * do that for us.
7005 */
7011 out:
7015 }
7019 {
7026 xattrsize);
7027 else
7030 }
7034 {
7040 }
7043 {
7052 /*
7053 * We clear the entire i_data structure here so that all
7054 * fields can be properly initialized.
7055 */
7060 }
7064 {
7088 }
7094 }
7095 }
7103 }
7106 OCFS2_JOURNAL_ACCESS_WRITE);
7110 }
7114 u64 phys;
7129 }
7131 /*
7132 * Save two copies, one for insert, and one that can
7133 * be changed by ocfs2_map_and_dirty_page() below.
7134 */
7137 /*
7138 * Non sparse file systems zero on extend, so no need
7139 * to do that now.
7140 */
7150 }
7152 /*
7153 * This should populate the 1st page for us and mark
7154 * it up to date.
7155 */
7161 }
7170 }
7183 /*
7184 * An error at this point should be extremely rare. If
7185 * this proves to be false, we could always re-build
7186 * the in-inode data from our pages.
7187 */
7194 }
7197 }
7199 out_unlock:
7203 out_commit:
7212 else
7217 num);
7218 }
7222 out:
7225 free_pages:
7228 }
7230 /*
7231 * It is expected, that by the time you call this function,
7232 * inode->i_size and fe->i_size have been adjusted.
7233 *
7234 * WARNING: This will kfree the truncate context
7235 */
7239 {
7260 ocfs2_journal_access_di);
7265 }
7269 start:
7270 /*
7271 * Check that we still have allocation to delete.
7272 */
7276 }
7278 /*
7279 * Truncate always works against the rightmost tree branch.
7280 */
7285 }
7289 new_highest_cpos,
7293 /*
7294 * By now, el will point to the extent list on the bottom most
7295 * portion of this tree. Only the tail record is considered in
7296 * each pass.
7297 *
7298 * We handle the following cases, in order:
7299 * - empty extent: delete the remaining branch
7300 * - remove the entire record
7301 * - remove a partial record
7302 * - no record needs to be removed (truncate has completed)
7303 */
7312 }
7320 /*
7321 * Lower levels depend on this never happening, but it's best
7322 * to check it up here before changing the tree.
7323 */
7333 }
7341 }
7343 /*
7344 * Truncate entire record.
7345 */
7350 /*
7351 * Partial truncate. it also should be
7352 * the last truncate we're doing.
7353 */
7360 /*
7361 * Truncate completed, leave happily.
7362 */
7365 }
7375 }
7376 }
7384 }
7388 /*
7389 * The check above will catch the case where we've truncated
7390 * away all allocation.
7391 */
7394 bail:
7405 }
7407 /*
7408 * 'start' is inclusive, 'end' is not.
7409 */
7412 {
7436 }
7443 }
7446 OCFS2_JOURNAL_ACCESS_WRITE);
7450 }
7455 /*
7456 * No need to worry about the data page here - it's been
7457 * truncated already and inline data doesn't need it for
7458 * pushing zero's to disk, so we'll let readpage pick it up
7459 * later.
7460 */
7464 }
7475 out_commit:
7478 out:
7480 }
7485 {
7492 /*
7493 * For the first cluster group, the gd->bg_blkno is not at the start
7494 * of the group, but at an offset from the start. If we add it while
7495 * calculating discard for first group, we will wrongly start fstrim a
7496 * few blocks after the desried start block and the range can cross
7497 * over into the next cluster group. So, add it only if this is not
7498 * the first cluster group.
7499 */
7506 }
7511 {
7533 }
7535 }
7541 }
7545 }
7551 }
7554 {
7574 GLOBAL_BITMAP_SYSTEM_INODE,
7575 OCFS2_INVALID_SLOT);
7580 }
7588 }
7594 }
7609 }
7619 }
7624 /* Avoid sending duplicated trim to a shared device */
7630 }
7631 }
7638 /* Determine first and last group to examine based on start and len */
7642 else
7651 else
7660 }
7671 }
7678 else
7680 }
7686 out_trimunlock:
7689 out_unlock:
7692 out_mutex:
7695 out:
7697 }