| blob | 2064cc8e196323fcf25c07dd3651ed26b4ccc10a |
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>
33 #define MLOG_MASK_PREFIX ML_DISK_ALLOC
34 #include <cluster/masklog.h>
58 CONTIG_LEFT,
59 CONTIG_RIGHT,
60 CONTIG_LEFTRIGHT,
61 };
63 static enum ocfs2_contig_type
67 /*
68 * Operations for a specific extent tree type.
69 *
70 * To implement an on-disk btree (extent tree) type in ocfs2, add
71 * an ocfs2_extent_tree_operations structure and the matching
72 * ocfs2_init_<thingy>_extent_tree() function. That's pretty much it
73 * for the allocation portion of the extent tree.
74 */
76 /*
77 * last_eb_blk is the block number of the right most leaf extent
78 * block. Most on-disk structures containing an extent tree store
79 * this value for fast access. The ->eo_set_last_eb_blk() and
80 * ->eo_get_last_eb_blk() operations access this value. They are
81 * both required.
82 */
84 u64 blkno);
87 /*
88 * The on-disk structure usually keeps track of how many total
89 * clusters are stored in this extent tree. This function updates
90 * that value. new_clusters is the delta, and must be
91 * added to the total. Required.
92 */
94 u32 new_clusters);
96 /*
97 * If this extent tree is supported by an extent map, insert
98 * a record into the map.
99 */
103 /*
104 * If this extent tree is supported by an extent map, truncate the
105 * map to clusters,
106 */
108 u32 clusters);
110 /*
111 * If ->eo_insert_check() exists, it is called before rec is
112 * inserted into the extent tree. It is optional.
113 */
118 /*
119 * --------------------------------------------------------------
120 * The remaining are internal to ocfs2_extent_tree and don't have
121 * accessor functions
122 */
124 /*
125 * ->eo_fill_root_el() takes et->et_object and sets et->et_root_el.
126 * It is required.
127 */
130 /*
131 * ->eo_fill_max_leaf_clusters sets et->et_max_leaf_clusters if
132 * it exists. If it does not, et->et_max_leaf_clusters is set
133 * to 0 (unlimited). Optional.
134 */
137 /*
138 * ->eo_extent_contig test whether the 2 ocfs2_extent_rec
139 * are contiguous or not. Optional. Don't need to set it if use
140 * ocfs2_extent_rec as the tree leaf.
141 */
142 enum ocfs2_contig_type
146 };
149 /*
150 * Pre-declare ocfs2_dinode_et_ops so we can use it as a sanity check
151 * in the methods.
152 */
155 u64 blkno);
157 u32 clusters);
161 u32 clusters);
175 };
178 u64 blkno)
179 {
184 }
187 {
192 }
195 u32 clusters)
196 {
204 }
208 {
212 }
215 u32 clusters)
216 {
220 }
224 {
231 "Device %s, asking for sparse allocation: inode %llu, "
238 }
241 {
248 }
251 {
255 }
259 {
263 }
266 u64 blkno)
267 {
271 }
274 {
278 }
281 u32 clusters)
282 {
286 }
293 };
296 {
300 }
303 {
307 }
310 u64 blkno)
311 {
316 }
319 {
324 }
327 u32 clusters)
328 {
332 }
340 };
343 u64 blkno)
344 {
348 }
351 {
355 }
358 u32 clusters)
359 {
363 }
366 {
372 }
375 {
379 }
387 };
390 {
394 }
397 u64 blkno)
398 {
402 }
405 {
409 }
412 u32 clusters)
413 {
417 }
419 static enum ocfs2_contig_type
423 {
425 }
433 };
438 ocfs2_journal_access_func access,
441 {
453 else
455 }
460 {
463 }
468 {
471 }
476 {
479 }
484 {
487 }
492 {
495 }
498 u64 new_last_eb_blk)
499 {
501 }
504 {
506 }
509 u32 clusters)
510 {
512 }
516 {
519 }
522 u32 clusters)
523 {
526 }
531 {
533 type);
534 }
540 {
547 }
551 {
557 }
560 {
566 }
575 /*
576 * Reset the actual path elements so that we can re-use the structure
577 * to build another path. Generally, this involves freeing the buffer
578 * heads.
579 */
581 {
594 }
596 /*
597 * Tree depth may change during truncate, or insert. If we're
598 * keeping the root extent list, then make sure that our path
599 * structure reflects the proper depth.
600 */
603 else
607 }
610 {
614 }
615 }
617 /*
618 * All the elements of src into dest. After this call, src could be freed
619 * without affecting dest.
620 *
621 * Both paths should have the same root. Any non-root elements of dest
622 * will be freed.
623 */
625 {
640 }
641 }
643 /*
644 * Make the *dest path the same as src and re-initialize src path to
645 * have a root only.
646 */
648 {
662 }
663 }
665 /*
666 * Insert an extent block at given index.
667 *
668 * This will not take an additional reference on eb_bh.
669 */
672 {
675 /*
676 * Right now, no root bh is an extent block, so this helps
677 * catch code errors with dinode trees. The assertion can be
678 * safely removed if we ever need to insert extent block
679 * structures at the root.
680 */
685 }
689 ocfs2_journal_access_func access)
690 {
702 }
705 }
708 {
711 }
714 {
717 }
719 /*
720 * Journal the buffer at depth idx. All idx>0 are extent_blocks,
721 * otherwise it's the root_access function.
722 *
723 * I don't like the way this function's name looks next to
724 * ocfs2_journal_access_path(), but I don't have a better one.
725 */
730 {
740 OCFS2_JOURNAL_ACCESS_WRITE);
741 }
743 /*
744 * Convenience function to journal all components in a path.
745 */
749 {
760 }
761 }
763 out:
765 }
767 /*
768 * Return the index of the extent record which contains cluster #v_cluster.
769 * -1 is returned if it was not found.
770 *
771 * Should work fine on interior and exterior nodes.
772 */
774 {
791 }
792 }
795 }
797 /*
798 * NOTE: ocfs2_block_extent_contig(), ocfs2_extents_adjacent() and
799 * ocfs2_extent_rec_contig only work properly against leaf nodes!
800 */
803 u64 blkno)
804 {
811 }
815 {
816 u32 left_range;
822 }
824 static enum ocfs2_contig_type
828 {
831 /*
832 * Refuse to coalesce extent records with different flag
833 * fields - we don't want to mix unwritten extents with user
834 * data.
835 */
849 }
851 /*
852 * NOTE: We can have pretty much any combination of contiguousness and
853 * appending.
854 *
855 * The usefulness of APPEND_TAIL is more in that it lets us know that
856 * we'll have to update the path to that leaf.
857 */
860 APPEND_TAIL,
861 };
865 SPLIT_LEFT,
866 SPLIT_RIGHT,
867 };
875 };
881 };
885 {
895 /*
896 * If the ecc fails, we return the error but otherwise
897 * leave the filesystem running. We know any error is
898 * local to this block.
899 */
905 }
907 /*
908 * Errors after here are fatal.
909 */
917 }
921 "Extent block #%llu has an invalid h_blkno "
926 }
930 "Extent block #%llu has an invalid "
935 }
938 }
942 {
947 ocfs2_validate_extent_block);
949 /* If ocfs2_read_block() got us a new bh, pass it up. */
954 }
957 /*
958 * How many free extents have we got before we need more meta data?
959 */
962 {
980 }
983 }
988 bail:
993 }
995 /* expects array to already be allocated
996 *
997 * sets h_signature, h_blkno, h_suballoc_bit, h_suballoc_slot, and
998 * l_count for you
999 */
1005 {
1007 u16 suballoc_bit_start;
1008 u32 num_got;
1019 meta_ac,
1028 }
1036 }
1041 OCFS2_JOURNAL_ACCESS_CREATE);
1045 }
1049 /* Ok, setup the minimal stuff here. */
1060 suballoc_bit_start++;
1061 first_blkno++;
1063 /* We'll also be dirtied by the caller, so
1064 * this isn't absolutely necessary. */
1066 }
1069 }
1072 bail:
1077 }
1078 }
1081 }
1083 /*
1084 * Helper function for ocfs2_add_branch() and ocfs2_shift_tree_depth().
1085 *
1086 * Returns the sum of the rightmost extent rec logical offset and
1087 * cluster count.
1088 *
1089 * ocfs2_add_branch() uses this to determine what logical cluster
1090 * value should be populated into the leftmost new branch records.
1091 *
1092 * ocfs2_shift_tree_depth() uses this to determine the # clusters
1093 * value for the new topmost tree record.
1094 */
1096 {
1103 }
1105 /*
1106 * Change range of the branches in the right most path according to the leaf
1107 * extent block's rightmost record.
1108 */
1111 {
1121 }
1127 }
1133 }
1139 }
1146 out:
1149 }
1151 /*
1152 * Add an entire tree branch to our inode. eb_bh is the extent block
1153 * to start at, if we don't want to start the branch at the root
1154 * structure.
1155 *
1156 * last_eb_bh is required as we have to update it's next_leaf pointer
1157 * for the new last extent block.
1158 *
1159 * the new branch will be 'empty' in the sense that every block will
1160 * contain a single record with cluster count == 0.
1161 */
1167 {
1187 /* we never add a branch to a leaf. */
1196 /*
1197 * If there is a gap before the root end and the real end
1198 * of the righmost leaf block, we need to remove the gap
1199 * between new_cpos and root_end first so that the tree
1200 * is consistent after we add a new branch(it will start
1201 * from new_cpos).
1202 */
1210 }
1211 }
1213 /* allocate the number of new eb blocks we need */
1215 GFP_KERNEL);
1220 }
1227 }
1229 /* Note: new_eb_bhs[new_blocks - 1] is the guy which will be
1230 * linked with the rest of the tree.
1231 * conversly, new_eb_bhs[0] is the new bottommost leaf.
1232 *
1233 * when we leave the loop, new_last_eb_blk will point to the
1234 * newest leaf, and next_blkno will point to the topmost extent
1235 * block. */
1240 /* ocfs2_create_new_meta_bhs() should create it right! */
1245 OCFS2_JOURNAL_ACCESS_CREATE);
1249 }
1254 /*
1255 * This actually counts as an empty extent as
1256 * c_clusters == 0
1257 */
1260 /*
1261 * eb_el isn't always an interior node, but even leaf
1262 * nodes want a zero'd flags and reserved field so
1263 * this gets the whole 32 bits regardless of use.
1264 */
1271 }
1273 /* This is a bit hairy. We want to update up to three blocks
1274 * here without leaving any of them in an inconsistent state
1275 * in case of error. We don't have to worry about
1276 * journal_dirty erroring as it won't unless we've aborted the
1277 * handle (in which case we would never be here) so reserving
1278 * the write with journal_access is all we need to do. */
1280 OCFS2_JOURNAL_ACCESS_WRITE);
1284 }
1286 OCFS2_JOURNAL_ACCESS_WRITE);
1290 }
1293 OCFS2_JOURNAL_ACCESS_WRITE);
1297 }
1298 }
1300 /* Link the new branch into the rest of the tree (el will
1301 * either be on the root_bh, or the extent block passed in. */
1308 /* fe needs a new last extent block pointer, as does the
1309 * next_leaf on the previously last-extent-block. */
1320 /*
1321 * Some callers want to track the rightmost leaf so pass it
1322 * back here.
1323 */
1329 bail:
1334 }
1338 }
1340 /*
1341 * adds another level to the allocation tree.
1342 * returns back the new extent block so you can add a branch to it
1343 * after this call.
1344 */
1349 {
1351 u32 new_clusters;
1364 }
1367 /* ocfs2_create_new_meta_bhs() should create it right! */
1374 OCFS2_JOURNAL_ACCESS_CREATE);
1378 }
1380 /* copy the root extent list data into the new extent block */
1389 OCFS2_JOURNAL_ACCESS_WRITE);
1393 }
1397 /* update root_bh now */
1406 /* If this is our 1st tree depth shift, then last_eb_blk
1407 * becomes the allocated extent block */
1416 bail:
1421 }
1423 /*
1424 * Should only be called when there is no space left in any of the
1425 * leaf nodes. What we want to do is find the lowest tree depth
1426 * non-leaf extent block with room for new records. There are three
1427 * valid results of this search:
1428 *
1429 * 1) a lowest extent block is found, then we pass it back in
1430 * *lowest_eb_bh and return '0'
1431 *
1432 * 2) the search fails to find anything, but the root_el has room. We
1433 * pass NULL back in *lowest_eb_bh, but still return '0'
1434 *
1435 * 3) the search fails to find anything AND the root_el is full, in
1436 * which case we return > 0
1437 *
1438 * return status < 0 indicates an error.
1439 */
1442 {
1444 u64 blkno;
1459 "Owner %llu has empty "
1464 }
1469 "Owner %llu has extent "
1470 "list where extent # %d has no physical "
1475 }
1484 }
1494 }
1495 }
1497 /* If we didn't find one and the fe doesn't have any room,
1498 * then return '1' */
1504 bail:
1509 }
1511 /*
1512 * Grow a b-tree so that it has more records.
1513 *
1514 * We might shift the tree depth in which case existing paths should
1515 * be considered invalid.
1516 *
1517 * Tree depth after the grow is returned via *final_depth.
1518 *
1519 * *last_eb_bh will be updated by ocfs2_add_branch().
1520 */
1524 {
1537 }
1539 /* We traveled all the way to the bottom of the allocation tree
1540 * and didn't find room for any more extents - we need to add
1541 * another tree level */
1546 /* ocfs2_shift_tree_depth will return us a buffer with
1547 * the new extent block (so we can pass that to
1548 * ocfs2_add_branch). */
1553 }
1554 depth++;
1556 /*
1557 * Special case: we have room now if we shifted from
1558 * tree_depth 0, so no more work needs to be done.
1559 *
1560 * We won't be calling add_branch, so pass
1561 * back *last_eb_bh as the new leaf. At depth
1562 * zero, it should always be null so there's
1563 * no reason to brelse.
1564 */
1569 }
1570 }
1572 /* call ocfs2_add_branch to add the final part of the tree with
1573 * the new data. */
1576 meta_ac);
1580 }
1582 out:
1587 }
1589 /*
1590 * This function will discard the rightmost extent record.
1591 */
1593 {
1599 /* This will cause us to go off the end of our extent list. */
1605 }
1609 {
1619 /* The tree code before us didn't allow enough room in the leaf. */
1622 /*
1623 * The easiest way to approach this is to just remove the
1624 * empty extent and temporarily decrement next_free.
1625 */
1627 /*
1628 * If next_free was 1 (only an empty extent), this
1629 * loop won't execute, which is fine. We still want
1630 * the decrement above to happen.
1631 */
1635 next_free--;
1636 }
1638 /*
1639 * Figure out what the new record index should be.
1640 */
1646 }
1656 /*
1657 * No need to memmove if we're just adding to the tail.
1658 */
1666 num_bytes);
1667 }
1669 /*
1670 * Either we had an empty extent, and need to re-increment or
1671 * there was no empty extent on a non full rightmost leaf node,
1672 * in which case we still need to increment.
1673 */
1674 next_free++;
1676 /*
1677 * Make sure none of the math above just messed up our tree.
1678 */
1683 }
1686 {
1692 num_recs--;
1698 }
1699 }
1701 /*
1702 * Create an empty extent record .
1703 *
1704 * l_next_free_rec may be updated.
1705 *
1706 * If an empty extent already exists do nothing.
1707 */
1709 {
1728 set_and_inc:
1731 }
1733 /*
1734 * For a rotation which involves two leaf nodes, the "root node" is
1735 * the lowest level tree node which contains a path to both leafs. This
1736 * resulting set of information can be used to form a complete "subtree"
1737 *
1738 * This function is passed two full paths from the dinode down to a
1739 * pair of adjacent leaves. It's task is to figure out which path
1740 * index contains the subtree root - this can be the root index itself
1741 * in a worst-case rotation.
1742 *
1743 * The array index of the subtree root is passed back.
1744 */
1748 {
1751 /*
1752 * Check that the caller passed in two paths from the same tree.
1753 */
1757 i++;
1759 /*
1760 * The caller didn't pass two adjacent paths.
1761 */
1773 }
1777 /*
1778 * Traverse a btree path in search of cpos, starting at root_el.
1779 *
1780 * This code can be called with a cpos larger than the tree, in which
1781 * case it will return the rightmost path.
1782 */
1786 {
1788 u32 range;
1789 u64 blkno;
1799 "Owner %llu has empty extent list at "
1806 }
1811 /*
1812 * In the case that cpos is off the allocation
1813 * tree, this should just wind up returning the
1814 * rightmost record.
1815 */
1820 }
1825 "Owner %llu has bad blkno in extent list "
1831 }
1839 }
1847 "Owner %llu has bad count in extent list "
1855 }
1859 }
1861 out:
1862 /*
1863 * Catch any trailing bh that the loop didn't handle.
1864 */
1868 }
1870 /*
1871 * Given an initialized path (that is, it has a valid root extent
1872 * list), this function will traverse the btree in search of the path
1873 * which would contain cpos.
1874 *
1875 * The path traveled is recorded in the path structure.
1876 *
1877 * Note that this will not do any comparisons on leaf node extent
1878 * records, so it will work fine in the case that we just added a tree
1879 * branch.
1880 */
1884 };
1886 {
1892 }
1895 {
1902 }
1905 {
1910 /* We want to retain only the leaf block. */
1914 }
1915 }
1916 /*
1917 * Find the leaf block in the tree which would contain cpos. No
1918 * checking of the actual leaf is done.
1919 *
1920 * Some paths want to call this instead of allocating a path structure
1921 * and calling ocfs2_find_path().
1922 *
1923 * This function doesn't handle non btree extent lists.
1924 */
1928 {
1936 }
1939 out:
1941 }
1943 /*
1944 * Adjust the adjacent records (left_rec, right_rec) involved in a rotation.
1945 *
1946 * Basically, we've moved stuff around at the bottom of the tree and
1947 * we need to fix up the extent records above the changes to reflect
1948 * the new changes.
1949 *
1950 * left_rec: the record on the left.
1951 * left_child_el: is the child list pointed to by left_rec
1952 * right_rec: the record to the right of left_rec
1953 * right_child_el: is the child list pointed to by right_rec
1954 *
1955 * By definition, this only works on interior nodes.
1956 */
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 */
2079 right_el);
2084 /*
2085 * Setup our list pointers now so that the current
2086 * parents become children in the next iteration.
2087 */
2090 }
2092 /*
2093 * At the root node, adjust the two adjacent records which
2094 * begin our path to the leaves.
2095 */
2107 }
2114 {
2127 "Inode %llu has non-full interior leaf node %llu"
2133 }
2135 /*
2136 * This extent block may already have an empty record, so we
2137 * return early if so.
2138 */
2146 subtree_index);
2150 }
2158 }
2165 }
2166 }
2171 /* This is a code error, not a disk corruption. */
2181 /* Do the copy now. */
2186 /*
2187 * Clear out the record we just copied and shift everything
2188 * over, leaving an empty extent in the left leaf.
2189 *
2190 * We temporarily subtract from next_free_rec so that the
2191 * shift will lose the tail record (which is now defunct).
2192 */
2201 subtree_index);
2203 out:
2205 }
2207 /*
2208 * Given a full path, determine what cpos value would return us a path
2209 * containing the leaf immediately to the left of the current one.
2210 *
2211 * Will return zero if the path passed in is already the leftmost path.
2212 */
2215 {
2217 u64 blkno;
2226 /* Start at the tree node just above the leaf and work our way up. */
2231 /*
2232 * Find the extent record just before the one in our
2233 * path.
2234 */
2239 /*
2240 * We've determined that the
2241 * path specified is already
2242 * the leftmost one - return a
2243 * cpos of zero.
2244 */
2246 }
2247 /*
2248 * The leftmost record points to our
2249 * leaf - we need to travel up the
2250 * tree one level.
2251 */
2253 }
2260 }
2261 }
2263 /*
2264 * If we got here, we never found a valid node where
2265 * the tree indicated one should be.
2266 */
2273 next_node:
2275 i--;
2276 }
2278 out:
2280 }
2282 /*
2283 * Extend the transaction by enough credits to complete the rotation,
2284 * and still leave at least the original number of credits allocated
2285 * to this transaction.
2286 */
2290 {
2299 }
2301 /*
2302 * Trap the case where we're inserting into the theoretical range past
2303 * the _actual_ left leaf range. Otherwise, we'll rotate a record
2304 * whose cpos is less than ours into the right leaf.
2305 *
2306 * It's only necessary to look at the rightmost record of the left
2307 * leaf because the logic that calls us should ensure that the
2308 * theoretical ranges in the path components above the leaves are
2309 * correct.
2310 */
2312 u32 insert_cpos)
2313 {
2325 }
2328 {
2338 /* Empty list. */
2342 }
2348 }
2350 /*
2351 * Rotate all the records in a btree right one record, starting at insert_cpos.
2352 *
2353 * The path to the rightmost leaf should be passed in.
2354 *
2355 * The array is assumed to be large enough to hold an entire path (tree depth).
2356 *
2357 * Upon successful return from this function:
2358 *
2359 * - The 'right_path' array will contain a path to the leaf block
2360 * whose range contains e_cpos.
2361 * - That leaf block will have a single empty extent in list index 0.
2362 * - In the case that the rotation requires a post-insert update,
2363 * *ret_left_path will contain a valid path which can be passed to
2364 * ocfs2_insert_path().
2365 */
2369 u32 insert_cpos,
2372 {
2374 u32 cpos;
2385 }
2391 }
2395 /*
2396 * What we want to do here is:
2397 *
2398 * 1) Start with the rightmost path.
2399 *
2400 * 2) Determine a path to the leaf block directly to the left
2401 * of that leaf.
2402 *
2403 * 3) Determine the 'subtree root' - the lowest level tree node
2404 * which contains a path to both leaves.
2405 *
2406 * 4) Rotate the subtree.
2407 *
2408 * 5) Find the next subtree by considering the left path to be
2409 * the new right path.
2410 *
2411 * The check at the top of this while loop also accepts
2412 * insert_cpos == cpos because cpos is only a _theoretical_
2413 * value to get us the left path - insert_cpos might very well
2414 * be filling that hole.
2415 *
2416 * Stop at a cpos of '0' because we either started at the
2417 * leftmost branch (i.e., a tree with one branch and a
2418 * rotation inside of it), or we've gone as far as we can in
2419 * rotating subtrees.
2420 */
2429 }
2433 "Owner %llu: error during insert of %u "
2434 "(left path cpos %u) results in two identical "
2443 insert_cpos)) {
2445 /*
2446 * We've rotated the tree as much as we
2447 * should. The rest is up to
2448 * ocfs2_insert_path() to complete, after the
2449 * record insertion. We indicate this
2450 * situation by returning the left path.
2451 *
2452 * The reason we don't adjust the records here
2453 * before the record insert is that an error
2454 * later might break the rule where a parent
2455 * record e_cpos will reflect the actual
2456 * e_cpos of the 1st nonempty record of the
2457 * child list.
2458 */
2461 }
2466 start,
2475 }
2482 }
2486 insert_cpos)) {
2487 /*
2488 * A rotate moves the rightmost left leaf
2489 * record over to the leftmost right leaf
2490 * slot. If we're doing an extent split
2491 * instead of a real insert, then we have to
2492 * check that the extent to be split wasn't
2493 * just moved over. If it was, then we can
2494 * exit here, passing left_path back -
2495 * ocfs2_split_extent() is smart enough to
2496 * search both leaves.
2497 */
2500 }
2502 /*
2503 * There is no need to re-read the next right path
2504 * as we know that it'll be our current left
2505 * path. Optimize by copying values instead.
2506 */
2513 }
2514 }
2516 out:
2519 out_ret_path:
2521 }
2526 {
2531 u32 range;
2533 /*
2534 * In normal tree rotation process, we will never touch the
2535 * tree branch above subtree_index and ocfs2_extend_rotate_transaction
2536 * doesn't reserve the credits for them either.
2537 *
2538 * But we do have a special case here which will update the rightmost
2539 * records for all the bh in the path.
2540 * So we have to allocate extra credits and access them.
2541 */
2546 }
2552 }
2554 /* Path should always be rightmost. */
2573 }
2574 out:
2576 }
2582 {
2592 /*
2593 * Not all nodes might have had their final count
2594 * decremented by the caller - handle this here.
2595 */
2599 "Inode %llu, attempted to remove extent block "
2608 }
2620 }
2621 }
2629 {
2657 }
2666 {
2684 /*
2685 * It's legal for us to proceed if the right leaf is
2686 * the rightmost one and it has an empty extent. There
2687 * are two cases to handle - whether the leaf will be
2688 * empty after removal or not. If the leaf isn't empty
2689 * then just remove the empty extent up front. The
2690 * next block will handle empty leaves by flagging
2691 * them for unlink.
2692 *
2693 * Non rightmost leaves will throw -EAGAIN and the
2694 * caller can manually move the subtree and retry.
2695 */
2703 OCFS2_JOURNAL_ACCESS_WRITE);
2707 }
2712 }
2716 /*
2717 * We have to update i_last_eb_blk during the meta
2718 * data delete.
2719 */
2721 OCFS2_JOURNAL_ACCESS_WRITE);
2725 }
2728 }
2730 /*
2731 * Getting here with an empty extent in the right path implies
2732 * that it's the rightmost path and will be deleted.
2733 */
2737 subtree_index);
2741 }
2749 }
2756 }
2757 }
2760 /*
2761 * Only do this if we're moving a real
2762 * record. Otherwise, the action is delayed until
2763 * after removal of the right path in which case we
2764 * can do a simple shift to remove the empty extent.
2765 */
2769 }
2771 /*
2772 * Move recs over to get rid of empty extent, decrease
2773 * next_free. This is allowed to remove the last
2774 * extent in our leaf (setting l_next_free_rec to
2775 * zero) - the delete code below won't care.
2776 */
2778 }
2787 left_path);
2791 }
2796 /*
2797 * Removal of the extent in the left leaf was skipped
2798 * above so we could delete the right path
2799 * 1st.
2800 */
2809 subtree_index);
2811 out:
2813 }
2815 /*
2816 * Given a full path, determine what cpos value would return us a path
2817 * containing the leaf immediately to the right of the current one.
2818 *
2819 * Will return zero if the path passed in is already the rightmost path.
2820 *
2821 * This looks similar, but is subtly different to
2822 * ocfs2_find_cpos_for_left_leaf().
2823 */
2826 {
2828 u64 blkno;
2838 /* Start at the tree node just above the leaf and work our way up. */
2845 /*
2846 * Find the extent record just after the one in our
2847 * path.
2848 */
2854 /*
2855 * We've determined that the
2856 * path specified is already
2857 * the rightmost one - return a
2858 * cpos of zero.
2859 */
2861 }
2862 /*
2863 * The rightmost record points to our
2864 * leaf - we need to travel up the
2865 * tree one level.
2866 */
2868 }
2872 }
2873 }
2875 /*
2876 * If we got here, we never found a valid node where
2877 * the tree indicated one should be.
2878 */
2885 next_node:
2887 i--;
2888 }
2890 out:
2892 }
2897 {
2910 }
2915 out:
2917 }
2925 {
2927 u32 right_cpos;
2940 }
2947 }
2956 }
2963 }
2966 right_path);
2969 subtree_root,
2979 }
2981 /*
2982 * Caller might still want to make changes to the
2983 * tree root, so re-add it to the journal here.
2984 */
2990 }
2996 /*
2997 * The rotation has to temporarily stop due to
2998 * the right subtree having an empty
2999 * extent. Pass it back to the caller for a
3000 * fixup.
3001 */
3005 }
3009 }
3011 /*
3012 * The subtree rotate might have removed records on
3013 * the rightmost edge. If so, then rotation is
3014 * complete.
3015 */
3026 }
3027 }
3029 out:
3034 }
3040 {
3042 u32 cpos;
3051 /*
3052 * There's two ways we handle this depending on
3053 * whether path is the only existing one.
3054 */
3057 path);
3061 }
3067 }
3074 }
3077 /*
3078 * We have a path to the left of this one - it needs
3079 * an update too.
3080 */
3086 }
3092 }
3098 }
3105 left_path);
3109 }
3114 /*
3115 * 'path' is also the leftmost path which
3116 * means it must be the only one. This gets
3117 * handled differently because we want to
3118 * revert the root back to having extents
3119 * in-line.
3120 */
3129 }
3133 out:
3136 }
3138 /*
3139 * Left rotation of btree records.
3140 *
3141 * In many ways, this is (unsurprisingly) the opposite of right
3142 * rotation. We start at some non-rightmost path containing an empty
3143 * extent in the leaf block. The code works its way to the rightmost
3144 * path by rotating records to the left in every subtree.
3145 *
3146 * This is used by any code which reduces the number of extent records
3147 * in a leaf. After removal, an empty record should be placed in the
3148 * leftmost list position.
3149 *
3150 * This won't handle a length update of the rightmost path records if
3151 * the rightmost tree leaf record is removed so the caller is
3152 * responsible for detecting and correcting that.
3153 */
3158 {
3169 rightmost_no_delete:
3170 /*
3171 * Inline extents. This is trivially handled, so do
3172 * it up front.
3173 */
3178 }
3180 /*
3181 * Handle rightmost branch now. There's several cases:
3182 * 1) simple rotation leaving records in there. That's trivial.
3183 * 2) rotation requiring a branch delete - there's no more
3184 * records left. Two cases of this:
3185 * a) There are branches to the left.
3186 * b) This is also the leftmost (the only) branch.
3187 *
3188 * 1) is handled via ocfs2_rotate_rightmost_leaf_left()
3189 * 2a) we need the left branch so that we can update it with the unlink
3190 * 2b) we need to bring the root back to inline extents.
3191 */
3196 /*
3197 * This gets a bit tricky if we're going to delete the
3198 * rightmost path. Get the other cases out of the way
3199 * 1st.
3200 */
3211 }
3215 dealloc);
3219 }
3221 /*
3222 * Now we can loop, remembering the path we get from -EAGAIN
3223 * and restarting from there.
3224 */
3225 try_rotate:
3231 }
3243 }
3250 }
3252 out:
3256 }
3260 {
3265 /*
3266 * We consumed all of the merged-from record. An empty
3267 * extent cannot exist anywhere but the 1st array
3268 * position, so move things over if the merged-from
3269 * record doesn't occupy that position.
3270 *
3271 * This creates a new empty extent so the caller
3272 * should be smart enough to have removed any existing
3273 * ones.
3274 */
3279 }
3281 /*
3282 * Always memset - the caller doesn't check whether it
3283 * created an empty extent, so there could be junk in
3284 * the other fields.
3285 */
3287 }
3288 }
3293 {
3295 u32 right_cpos;
3301 /* This function shouldn't be called for non-trees. */
3312 }
3314 /* This function shouldn't be called for the rightmost leaf. */
3322 }
3328 }
3331 out:
3335 }
3337 /*
3338 * Remove split_rec clusters from the record at index and merge them
3339 * onto the beginning of the record "next" to it.
3340 * For index < l_count - 1, the next means the extent rec at index + 1.
3341 * For index == l_count - 1, the "next" means the 1st extent rec of the
3342 * next extent block.
3343 */
3349 {
3366 /* we meet with a cross extent block merge. */
3371 }
3380 }
3387 right_path);
3391 right_path);
3395 }
3401 subtree_index);
3405 }
3414 }
3421 }
3422 }
3427 }
3434 }
3441 split_clusters));
3450 subtree_index);
3451 }
3452 out:
3456 }
3461 {
3463 u32 left_cpos;
3468 /* This function shouldn't be called for non-trees. */
3476 }
3478 /* This function shouldn't be called for the leftmost leaf. */
3486 }
3492 }
3495 out:
3499 }
3501 /*
3502 * Remove split_rec clusters from the record at index and merge them
3503 * onto the tail of the record "before" it.
3504 * For index > 0, the "before" means the extent rec at index - 1.
3505 *
3506 * For index == 0, the "before" means the last record of the previous
3507 * extent block. And there is also a situation that we may need to
3508 * remove the rightmost leaf extent block in the right_path and change
3509 * the right path to indicate the new rightmost path.
3510 */
3517 {
3532 /* we meet with a cross extent block merge. */
3537 }
3550 right_path);
3554 left_path);
3558 }
3564 subtree_index);
3568 }
3577 }
3584 }
3585 }
3590 }
3597 }
3600 /*
3601 * The easy case - we can just plop the record right in.
3602 */
3612 split_clusters));
3621 /*
3622 * In the situation that the right_rec is empty and the extent
3623 * block is empty also, ocfs2_complete_edge_insert can't handle
3624 * it and we need to delete the right extent block.
3625 */
3630 right_path,
3631 dealloc);
3635 }
3637 /* Now the rightmost extent block has been deleted.
3638 * So we use the new rightmost path.
3639 */
3645 }
3646 out:
3650 }
3659 {
3667 /*
3668 * The merge code will need to create an empty
3669 * extent to take the place of the newly
3670 * emptied slot. Remove any pre-existing empty
3671 * extents - having more than one in a leaf is
3672 * illegal.
3673 */
3678 }
3679 split_index--;
3681 }
3684 /*
3685 * Left-right contig implies this.
3686 */
3689 /*
3690 * Since the leftright insert always covers the entire
3691 * extent, this call will delete the insert record
3692 * entirely, resulting in an empty extent record added to
3693 * the extent block.
3694 *
3695 * Since the adding of an empty extent shifts
3696 * everything back to the right, there's no need to
3697 * update split_index here.
3698 *
3699 * When the split_index is zero, we need to merge it to the
3700 * prevoius extent block. It is more efficient and easier
3701 * if we do merge_right first and merge_left later.
3702 */
3704 split_index);
3708 }
3710 /*
3711 * We can only get this from logic error above.
3712 */
3715 /* The merge left us with an empty extent, remove it. */
3720 }
3724 /*
3725 * Note that we don't pass split_rec here on purpose -
3726 * we've merged it into the rec already.
3727 */
3734 }
3737 /*
3738 * Error from this last rotate is not critical, so
3739 * print but don't bubble it up.
3740 */
3745 /*
3746 * Merge a record to the left or right.
3747 *
3748 * 'contig_type' is relative to the existing record,
3749 * so for example, if we're "right contig", it's to
3750 * the record on the left (hence the left merge).
3751 */
3755 split_index);
3759 }
3763 split_index);
3767 }
3768 }
3771 /*
3772 * The merge may have left an empty extent in
3773 * our leaf. Try to rotate it away.
3774 */
3776 dealloc);
3780 }
3781 }
3783 out:
3785 }
3791 {
3792 u64 len_blocks;
3798 /*
3799 * Region is on the left edge of the existing
3800 * record.
3801 */
3808 /*
3809 * Region is on the right edge of the existing
3810 * record.
3811 */
3814 }
3815 }
3817 /*
3818 * Do the final bits of extent record insertion at the target leaf
3819 * list. If this leaf is part of an allocation tree, it is assumed
3820 * that the tree above has been prepared.
3821 */
3826 {
3839 insert_rec);
3841 }
3843 /*
3844 * Contiguous insert - either left or right.
3845 */
3851 }
3855 }
3857 /*
3858 * Handle insert into an empty leaf.
3859 */
3866 }
3868 /*
3869 * Appending insert.
3870 */
3880 "owner %llu, depth %u, count %u, next free %u, "
3881 "rec.cpos %u, rec.clusters %u, "
3891 i++;
3895 }
3897 rotate:
3898 /*
3899 * Ok, we have to rotate.
3900 *
3901 * At this point, it is safe to assume that inserting into an
3902 * empty leaf and appending to a leaf have both been handled
3903 * above.
3904 *
3905 * This leaf needs to have space, either by the empty 1st
3906 * extent record, or by virtue of an l_next_rec < l_count.
3907 */
3909 }
3915 {
3921 /*
3922 * Update everything except the leaf block.
3923 */
3935 }
3946 }
3947 }
3954 {
3961 /*
3962 * This shouldn't happen for non-trees. The extent rec cluster
3963 * count manipulation below only works for interior nodes.
3964 */
3967 /*
3968 * If our appending insert is at the leftmost edge of a leaf,
3969 * then we might need to update the rightmost records of the
3970 * neighboring path.
3971 */
3976 u32 left_cpos;
3983 }
3987 left_cpos);
3989 /*
3990 * No need to worry if the append is already in the
3991 * leftmost leaf.
3992 */
3999 }
4002 left_cpos);
4006 }
4008 /*
4009 * ocfs2_insert_path() will pass the left_path to the
4010 * journal for us.
4011 */
4012 }
4013 }
4019 }
4025 out:
4030 }
4037 {
4054 /*
4055 * This typically means that the record
4056 * started in the left path but moved to the
4057 * right as a result of rotation. We either
4058 * move the existing record to the left, or we
4059 * do the later insert there.
4060 *
4061 * In this case, the left path should always
4062 * exist as the rotate code will have passed
4063 * it back for a post-insert update.
4064 */
4067 /*
4068 * It's a left split. Since we know
4069 * that the rotate code gave us an
4070 * empty extent in the left path, we
4071 * can just do the insert there.
4072 */
4075 /*
4076 * Right split - we have to move the
4077 * existing record over to the left
4078 * leaf. The insert will be into the
4079 * newly created empty extent in the
4080 * right leaf.
4081 */
4089 }
4090 }
4094 /*
4095 * Left path is easy - we can just allow the insert to
4096 * happen.
4097 */
4102 }
4108 }
4110 /*
4111 * This function only does inserts on an allocation b-tree. For tree
4112 * depth = 0, ocfs2_insert_at_leaf() is called directly.
4113 *
4114 * right_path is the path we want to do the actual insert
4115 * in. left_path should only be passed in if we need to update that
4116 * portion of the tree after an edge insert.
4117 */
4124 {
4129 /*
4130 * There's a chance that left_path got passed back to
4131 * us without being accounted for in the
4132 * journal. Extend our transaction here to be sure we
4133 * can change those blocks.
4134 */
4139 }
4145 }
4146 }
4148 /*
4149 * Pass both paths to the journal. The majority of inserts
4150 * will be touching all components anyway.
4151 */
4156 }
4159 /*
4160 * We could call ocfs2_insert_at_leaf() for some types
4161 * of splits, but it's easier to just let one separate
4162 * function sort it all out.
4163 */
4167 /*
4168 * Split might have modified either leaf and we don't
4169 * have a guarantee that the later edge insert will
4170 * dirty this for us.
4171 */
4177 insert);
4183 right_path);
4185 subtree_index);
4186 }
4189 out:
4191 }
4197 {
4199 u32 cpos;
4207 OCFS2_JOURNAL_ACCESS_WRITE);
4211 }
4216 }
4223 }
4225 /*
4226 * Determine the path to start with. Rotations need the
4227 * rightmost path, everything else can go directly to the
4228 * target leaf.
4229 */
4235 }
4241 }
4250 }
4252 /*
4253 * ocfs2_rotate_tree_right() might have extended the
4254 * transaction without re-journaling our tree root.
4255 */
4257 OCFS2_JOURNAL_ACCESS_WRITE);
4261 }
4269 }
4270 }
4277 }
4279 out_update_clusters:
4286 out:
4291 }
4293 static enum ocfs2_contig_type
4298 {
4322 left_cpos);
4333 "Extent block #%llu has an "
4334 "invalid l_next_free_rec of "
4335 "%d. It should have "
4342 }
4345 }
4346 }
4348 /*
4349 * We're careful to check for an empty extent record here -
4350 * the merge code will know what to do if it sees one.
4351 */
4358 }
4359 }
4388 "Extent block #%llu has an "
4394 }
4396 }
4397 }
4408 }
4410 out:
4417 }
4423 {
4431 insert_rec);
4435 }
4436 }
4445 /*
4446 * Caller might want us to limit the size of extents, don't
4447 * calculate contiguousness if we might exceed that limit.
4448 */
4452 }
4453 }
4455 /*
4456 * This should only be called against the righmost leaf extent list.
4457 *
4458 * ocfs2_figure_appending_type() will figure out whether we'll have to
4459 * insert at the tail of the rightmost leaf.
4460 *
4461 * This should also work against the root extent list for tree's with 0
4462 * depth. If we consider the root extent list to be the rightmost leaf node
4463 * then the logic here makes sense.
4464 */
4468 {
4481 /* Were all records empty? */
4484 }
4495 set_tail_append:
4497 }
4499 /*
4500 * Helper function called at the begining of an insert.
4501 *
4502 * This computes a few things that are commonly used in the process of
4503 * inserting into the btree:
4504 * - Whether the new extent is contiguous with an existing one.
4505 * - The current tree depth.
4506 * - Whether the insert is an appending one.
4507 * - The total # of free records in the tree.
4508 *
4509 * All of the information is stored on the ocfs2_insert_type
4510 * structure.
4511 */
4517 {
4530 /*
4531 * If we have tree depth, we read in the
4532 * rightmost extent block ahead of time as
4533 * ocfs2_figure_insert_type() and ocfs2_add_branch()
4534 * may want it later.
4535 */
4542 }
4545 }
4554 }
4561 }
4563 /*
4564 * In the case that we're inserting past what the tree
4565 * currently accounts for, ocfs2_find_path() will return for
4566 * us the rightmost tree path. This is accounted for below in
4567 * the appending code.
4568 */
4573 }
4577 /*
4578 * Now that we have the path, there's two things we want to determine:
4579 * 1) Contiguousness (also set contig_index if this is so)
4580 *
4581 * 2) Are we doing an append? We can trivially break this up
4582 * into two types of appends: simple record append, or a
4583 * rotate inside the tail leaf.
4584 */
4587 /*
4588 * The insert code isn't quite ready to deal with all cases of
4589 * left contiguousness. Specifically, if it's an insert into
4590 * the 1st record in a leaf, it will require the adjustment of
4591 * cluster count on the last record of the path directly to it's
4592 * left. For now, just catch that case and fool the layers
4593 * above us. This works just fine for tree_depth == 0, which
4594 * is why we allow that above.
4595 */
4600 /*
4601 * Ok, so we can simply compare against last_eb to figure out
4602 * whether the path doesn't exist. This will only happen in
4603 * the case that we're doing a tail append, so maybe we can
4604 * take advantage of that information somehow.
4605 */
4608 /*
4609 * Ok, ocfs2_find_path() returned us the rightmost
4610 * tree path. This might be an appending insert. There are
4611 * two cases:
4612 * 1) We're doing a true append at the tail:
4613 * -This might even be off the end of the leaf
4614 * 2) We're "appending" by rotating in the tail
4615 */
4617 }
4619 out:
4624 else
4627 }
4629 /*
4630 * Insert an extent into a btree.
4631 *
4632 * The caller needs to update the owning btree's cluster count.
4633 */
4636 u32 cpos,
4637 u64 start_blk,
4638 u32 new_clusters,
4639 u8 flags,
4641 {
4661 }
4668 }
4671 "Insert.contig_index: %d, Insert.free_records: %d, "
4679 meta_ac);
4683 }
4684 }
4686 /* Finally, we can add clusters. This might rotate the tree for us. */
4690 else
4693 bail:
4698 }
4700 /*
4701 * Allcate and add clusters into the extent b-tree.
4702 * The new clusters(clusters_to_add) will be inserted at logical_offset.
4703 * The extent b-tree's root is specified by et, and
4704 * it is not limited to the file storage. Any extent tree can use this
4705 * function if it implements the proper ocfs2_extent_tree.
4706 */
4710 u32 clusters_to_add,
4715 {
4720 u64 block;
4735 }
4737 /* there are two cases which could cause us to EAGAIN in the
4738 * we-need-more-metadata case:
4739 * 1) we haven't reserved *any*
4740 * 2) we are so fragmented, we've needed to add metadata too
4741 * many times. */
4754 }
4762 }
4766 /* reserve our write early -- insert_extent may update the tree root */
4768 OCFS2_JOURNAL_ACCESS_WRITE);
4772 }
4783 }
4792 clusters_to_add);
4795 }
4797 leave:
4802 }
4806 u32 cpos,
4808 {
4822 }
4831 {
4841 leftright:
4842 /*
4843 * Store a copy of the record on the stack - it might move
4844 * around as the tree is manipulated below.
4845 */
4855 }
4864 }
4865 }
4882 /*
4883 * Left/right split. We fake this as a right split
4884 * first and then make a second pass as a left split.
4885 */
4895 }
4901 }
4904 u32 cpos;
4907 do_leftright++;
4917 }
4922 }
4923 out:
4926 }
4934 {
4942 }
4947 out:
4949 }
4951 /*
4952 * Split part or all of the extent record at split_index in the leaf
4953 * pointed to by path. Merge with the contiguous extent record if needed.
4954 *
4955 * Care is taken to handle contiguousness so as to not grow the tree.
4956 *
4957 * meta_ac is not strictly necessary - we only truly need it if growth
4958 * of the tree is required. All other cases will degrade into a less
4959 * optimal tree layout.
4960 *
4961 * last_eb_bh should be the rightmost leaf block for any extent
4962 * btree. Since a split may grow the tree or a merge might shrink it,
4963 * the caller cannot trust the contents of that buffer after this call.
4964 *
4965 * This code is optimized for readability - several passes might be
4966 * made over certain portions of the tree. All of those blocks will
4967 * have been brought into cache (and pinned via the journal), so the
4968 * extra overhead is not expressed in terms of disk reads.
4969 */
4977 {
4991 }
4994 split_index,
4995 split_rec);
4997 /*
4998 * The core merge / split code wants to know how much room is
4999 * left in this allocation tree, so we pass the
5000 * rightmost extent list.
5001 */
5011 }
5021 else
5034 else
5046 }
5048 out:
5051 }
5053 /*
5054 * Change the flags of the already-existing extent at cpos for len clusters.
5055 *
5056 * new_flags: the flags we want to set.
5057 * clear_flags: the flags we want to clear.
5058 * phys: the new physical offset we want this new extent starts from.
5059 *
5060 * If the existing extent is larger than the request, initiate a
5061 * split. An attempt will be made at merging with adjacent extents.
5062 *
5063 * The caller is responsible for passing down meta_ac if we'll need it.
5064 */
5071 {
5085 }
5091 }
5097 "Owner %llu has an extent at cpos %u which can no "
5103 }
5111 new_flags);
5113 }
5119 clear_flags);
5121 }
5135 dealloc);
5139 out:
5143 }
5145 /*
5146 * Mark the already-existing extent at cpos as written for len clusters.
5147 * This removes the unwritten extent flag.
5148 *
5149 * If the existing extent is larger than the request, initiate a
5150 * split. An attempt will be made at merging with adjacent extents.
5151 *
5152 * The caller is responsible for passing down meta_ac if we'll need it.
5153 */
5159 {
5167 "that are being written to, but the feature bit "
5172 }
5182 out:
5184 }
5190 {
5199 /*
5200 * Setup the record to split before we grow the tree.
5201 */
5215 }
5228 }
5233 meta_ac);
5237 }
5238 }
5250 out:
5253 }
5260 {
5275 }
5277 index--;
5278 }
5282 /*
5283 * Check whether this is the rightmost tree record. If
5284 * we remove all of this record or part of its right
5285 * edge then an update of the record lengths above it
5286 * will be required.
5287 */
5291 }
5296 /*
5297 * Changing the leftmost offset (via partial or whole
5298 * record truncate) of an interior (or rightmost) path
5299 * means we have to update the subtree that is formed
5300 * by this leaf and the one to it's left.
5301 *
5302 * There are two cases we can skip:
5303 * 1) Path is the leftmost one in our btree.
5304 * 2) The leaf is rightmost and will be empty after
5305 * we remove the extent record - the rotate code
5306 * knows how to update the newly formed edge.
5307 */
5313 }
5321 }
5324 left_cpos);
5328 }
5329 }
5330 }
5334 path);
5338 }
5344 }
5350 }
5364 /*
5365 * We skip the edge update if this path will
5366 * be deleted by the rotate code.
5367 */
5370 rec);
5371 }
5373 /* Remove leftmost portion of the record. */
5378 /* Remove rightmost portion of the record */
5383 /* Caller should have trapped this. */
5390 }
5397 subtree_index);
5398 }
5406 }
5408 out:
5411 }
5418 {
5432 }
5438 }
5444 "Owner %llu has an extent at cpos %u which can no "
5447 cpos);
5450 }
5452 /*
5453 * We have 3 cases of extent removal:
5454 * 1) Range covers the entire extent rec
5455 * 2) Range begins or ends on one edge of the extent rec
5456 * 3) Range is in the middle of the extent rec (no shared edges)
5457 *
5458 * For case 1 we remove the extent rec and left rotate to
5459 * fill the hole.
5460 *
5461 * For case 2 we just shrink the existing extent rec, with a
5462 * tree update if the shrinking edge is also the edge of an
5463 * extent block.
5464 *
5465 * For case 3 we do a right split to turn the extent rec into
5466 * something case 2 can handle.
5467 */
5486 }
5493 }
5495 /*
5496 * The split could have manipulated the tree enough to
5497 * move the record location, so we have to look for it again.
5498 */
5505 }
5513 cpos);
5516 }
5518 /*
5519 * Double check our values here. If anything is fishy,
5520 * it's easier to catch it at the top level.
5521 */
5527 "Owner %llu: error after split at cpos %u"
5534 }
5541 }
5542 }
5544 out:
5547 }
5549 /*
5550 * ocfs2_reserve_blocks_for_rec_trunc() would look basically the
5551 * same as ocfs2_lock_alloctors(), except for it accepts a blocks
5552 * number to reserve some extra blocks, and it only handles meta
5553 * data allocations.
5554 *
5555 * Currently, only ocfs2_remove_btree_range() uses it for truncating
5556 * and punching holes.
5557 */
5560 u32 extents_to_split,
5563 {
5575 }
5587 }
5588 }
5590 out:
5595 }
5596 }
5599 }
5605 u64 refcount_loc)
5606 {
5617 OCFS2_HAS_REFCOUNT_FL));
5624 }
5627 refcount_loc,
5628 phys_blkno,
5629 len,
5635 }
5636 }
5639 extra_blocks);
5643 }
5652 }
5653 }
5661 }
5664 OCFS2_JOURNAL_ACCESS_WRITE);
5668 }
5677 }
5687 phys_blkno),
5690 else
5696 }
5698 out_commit:
5700 out:
5710 }
5713 {
5722 "slot %d, invalid truncate log parameters: used = "
5726 }
5730 {
5734 /* No records, nothing to coalesce */
5743 }
5747 u64 start_blk,
5749 {
5766 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5767 * by the underlying call to ocfs2_read_inode_block(), so any
5768 * corruption is a code bug */
5775 "Truncate record count on #%llu invalid "
5781 /* Caller should have known to flush before calling us. */
5787 }
5790 OCFS2_JOURNAL_ACCESS_WRITE);
5794 }
5801 /*
5802 * Move index back to the record we are coalescing with.
5803 * ocfs2_truncate_log_can_coalesce() guarantees nonzero
5804 */
5805 index--;
5810 num_clusters);
5814 }
5819 bail:
5822 }
5828 {
5832 u64 start_blk;
5845 /* Caller has given us at least enough credits to
5846 * update the truncate log dinode */
5848 OCFS2_JOURNAL_ACCESS_WRITE);
5852 }
5858 /* TODO: Perhaps we can calculate the bulk of the
5859 * credits up front rather than extending like
5860 * this. */
5862 OCFS2_TRUNCATE_LOG_FLUSH_ONE_REC);
5866 }
5873 /* if start_blk is not set, we ignore the record as
5874 * invalid. */
5881 num_clusters);
5885 }
5886 }
5887 i--;
5888 }
5890 bail:
5893 }
5895 /* Expects you to already be holding tl_inode->i_mutex */
5897 {
5914 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5915 * by the underlying call to ocfs2_read_inode_block(), so any
5916 * corruption is a code bug */
5926 }
5929 GLOBAL_BITMAP_SYSTEM_INODE,
5930 OCFS2_INVALID_SLOT);
5935 }
5943 }
5950 }
5953 data_alloc_bh);
5959 out_unlock:
5963 out_mutex:
5967 out:
5970 }
5973 {
5982 }
5985 {
5996 else
6000 }
6002 #define OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL (2 * HZ)
6005 {
6007 /* We want to push off log flushes while truncates are
6008 * still running. */
6013 OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL);
6014 }
6015 }
6021 {
6027 TRUNCATE_LOG_SYSTEM_INODE,
6028 slot_num);
6033 }
6040 }
6044 bail:
6047 }
6049 /* called during the 1st stage of node recovery. we stamp a clean
6050 * truncate log and pass back a copy for processing later. if the
6051 * truncate log does not require processing, a *tl_copy is set to
6052 * NULL. */
6056 {
6071 }
6075 /* tl_bh is loaded from ocfs2_get_truncate_log_info(). It's
6076 * validated by the underlying call to ocfs2_read_inode_block(),
6077 * so any corruption is a code bug */
6090 }
6092 /* Assuming the write-out below goes well, this copy
6093 * will be passed back to recovery for processing. */
6096 /* All we need to do to clear the truncate log is set
6097 * tl_used. */
6105 }
6106 }
6108 bail:
6116 }
6120 }
6124 {
6128 u64 start_blk;
6138 }
6152 }
6153 }
6160 }
6172 }
6173 }
6175 bail_up:
6180 }
6183 {
6199 }
6202 }
6205 {
6219 /* ocfs2_truncate_log_shutdown keys on the existence of
6220 * osb->osb_tl_inode so we don't set any of the osb variables
6221 * until we're sure all is well. */
6223 ocfs2_truncate_log_worker);
6229 }
6231 /*
6232 * Delayed de-allocation of suballocator blocks.
6233 *
6234 * Some sets of block de-allocations might involve multiple suballocator inodes.
6235 *
6236 * The locking for this can get extremely complicated, especially when
6237 * the suballocator inodes to delete from aren't known until deep
6238 * within an unrelated codepath.
6239 *
6240 * ocfs2_extent_block structures are a good example of this - an inode
6241 * btree could have been grown by any number of nodes each allocating
6242 * out of their own suballoc inode.
6243 *
6244 * These structures allow the delay of block de-allocation until a
6245 * later time, when locking of multiple cluster inodes won't cause
6246 * deadlock.
6247 */
6249 /*
6250 * Describe a single bit freed from a suballocator. For the block
6251 * suballocators, it represents one block. For the global cluster
6252 * allocator, it represents some clusters and free_bit indicates
6253 * clusters number.
6254 */
6257 u64 free_bg;
6258 u64 free_blk;
6260 };
6267 };
6273 {
6275 u64 bg_blkno;
6286 }
6294 }
6301 }
6306 else
6317 }
6323 }
6328 }
6330 out_journal:
6333 out_unlock:
6336 out_mutex:
6339 out:
6341 /* Premature exit may have left some dangling items. */
6345 }
6348 }
6352 {
6361 }
6372 }
6376 {
6390 }
6391 }
6398 }
6411 }
6412 }
6417 /* Premature exit may have left some dangling items. */
6421 }
6424 }
6428 {
6449 }
6453 }
6464 }
6467 }
6473 {
6481 }
6491 }
6493 }
6498 {
6508 }
6515 }
6528 out:
6530 }
6534 {
6540 }
6543 {
6547 }
6552 {
6562 /*
6563 * Need to set the buffers we zero'd into uptodate
6564 * here if they aren't - ocfs2_map_page_blocks()
6565 * might've skipped some
6566 */
6569 ocfs2_zero_func);
6576 }
6582 }
6587 {
6613 }
6614 out:
6617 }
6621 {
6625 loff_t last_page_bytes;
6638 }
6640 numpages++;
6641 index++;
6644 out:
6649 }
6654 }
6658 {
6665 }
6667 /*
6668 * Zero the area past i_size but still within an allocated
6669 * cluster. This avoids exposing nonzero data on subsequent file
6670 * extends.
6671 *
6672 * We need to call this before i_size is updated on the inode because
6673 * otherwise block_write_full_page() will skip writeout of pages past
6674 * i_size. The new_i_size parameter is passed for this reason.
6675 */
6678 {
6681 u64 phys;
6685 /*
6686 * File systems which don't support sparse files zero on every
6687 * extend.
6688 */
6698 }
6709 }
6711 /*
6712 * Tail is a hole, or is marked unwritten. In either case, we
6713 * can count on read and write to return/push zero's.
6714 */
6723 }
6728 /*
6729 * Initiate writeout of the pages we zero'd here. We don't
6730 * wait on them - the truncate_inode_pages() call later will
6731 * do that for us.
6732 */
6738 out:
6743 }
6747 {
6754 xattrsize);
6755 else
6758 }
6762 {
6768 }
6771 {
6780 /*
6781 * We clear the entire i_data structure here so that all
6782 * fields can be properly initialized.
6783 */
6788 }
6792 {
6814 }
6820 }
6821 }
6829 }
6832 OCFS2_JOURNAL_ACCESS_WRITE);
6836 }
6841 u64 phys;
6856 }
6858 /*
6859 * Save two copies, one for insert, and one that can
6860 * be changed by ocfs2_map_and_dirty_page() below.
6861 */
6864 /*
6865 * Non sparse file systems zero on extend, so no need
6866 * to do that now.
6867 */
6876 }
6878 /*
6879 * This should populate the 1st page for us and mark
6880 * it up to date.
6881 */
6886 }
6895 }
6907 /*
6908 * An error at this point should be extremely rare. If
6909 * this proves to be false, we could always re-build
6910 * the in-inode data from our pages.
6911 */
6917 }
6920 }
6922 out_commit:
6929 out_unlock:
6933 out:
6937 }
6940 }
6942 /*
6943 * It is expected, that by the time you call this function,
6944 * inode->i_size and fe->i_size have been adjusted.
6945 *
6946 * WARNING: This will kfree the truncate context
6947 */
6951 {
6973 ocfs2_journal_access_di);
6978 }
6982 start:
6983 /*
6984 * Check that we still have allocation to delete.
6985 */
6989 }
6991 /*
6992 * Truncate always works against the rightmost tree branch.
6993 */
6998 }
7003 /*
7004 * By now, el will point to the extent list on the bottom most
7005 * portion of this tree. Only the tail record is considered in
7006 * each pass.
7007 *
7008 * We handle the following cases, in order:
7009 * - empty extent: delete the remaining branch
7010 * - remove the entire record
7011 * - remove a partial record
7012 * - no record needs to be removed (truncate has completed)
7013 */
7022 }
7030 /*
7031 * Lower levels depend on this never happening, but it's best
7032 * to check it up here before changing the tree.
7033 */
7040 }
7045 /*
7046 * Truncate entire record.
7047 */
7052 /*
7053 * Partial truncate. it also should be
7054 * the last truncate we're doing.
7055 */
7062 /*
7063 * Truncate completed, leave happily.
7064 */
7067 }
7073 refcount_loc);
7077 }
7081 /*
7082 * The check above will catch the case where we've truncated
7083 * away all allocation.
7084 */
7087 bail:
7097 }
7099 /*
7100 * Expects the inode to already be locked.
7101 */
7106 {
7130 }
7140 }
7142 }
7147 bail:
7152 }
7155 }
7157 /*
7158 * 'start' is inclusive, 'end' is not.
7159 */
7162 {
7179 "Inline data flags for inode %llu don't agree! "
7187 }
7194 }
7197 OCFS2_JOURNAL_ACCESS_WRITE);
7201 }
7206 /*
7207 * No need to worry about the data page here - it's been
7208 * truncated already and inline data doesn't need it for
7209 * pushing zero's to disk, so we'll let readpage pick it up
7210 * later.
7211 */
7215 }
7225 out_commit:
7228 out:
7230 }
7233 {
7234 /*
7235 * The caller is responsible for completing deallocation
7236 * before freeing the context.
7237 */
7245 }