| blob | b27a0d86f8c584fd9f15aff29a4ceb3032d8910a |
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 #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 }
574 /*
575 * Reset the actual path elements so that we can re-use the structure
576 * to build another path. Generally, this involves freeing the buffer
577 * heads.
578 */
580 {
593 }
595 /*
596 * Tree depth may change during truncate, or insert. If we're
597 * keeping the root extent list, then make sure that our path
598 * structure reflects the proper depth.
599 */
602 else
606 }
609 {
613 }
614 }
616 /*
617 * All the elements of src into dest. After this call, src could be freed
618 * without affecting dest.
619 *
620 * Both paths should have the same root. Any non-root elements of dest
621 * will be freed.
622 */
624 {
639 }
640 }
642 /*
643 * Make the *dest path the same as src and re-initialize src path to
644 * have a root only.
645 */
647 {
661 }
662 }
664 /*
665 * Insert an extent block at given index.
666 *
667 * This will not take an additional reference on eb_bh.
668 */
671 {
674 /*
675 * Right now, no root bh is an extent block, so this helps
676 * catch code errors with dinode trees. The assertion can be
677 * safely removed if we ever need to insert extent block
678 * structures at the root.
679 */
684 }
688 ocfs2_journal_access_func access)
689 {
701 }
704 }
707 {
710 }
713 {
716 }
718 /*
719 * Journal the buffer at depth idx. All idx>0 are extent_blocks,
720 * otherwise it's the root_access function.
721 *
722 * I don't like the way this function's name looks next to
723 * ocfs2_journal_access_path(), but I don't have a better one.
724 */
729 {
739 OCFS2_JOURNAL_ACCESS_WRITE);
740 }
742 /*
743 * Convenience function to journal all components in a path.
744 */
748 {
759 }
760 }
762 out:
764 }
766 /*
767 * Return the index of the extent record which contains cluster #v_cluster.
768 * -1 is returned if it was not found.
769 *
770 * Should work fine on interior and exterior nodes.
771 */
773 {
790 }
791 }
794 }
796 /*
797 * NOTE: ocfs2_block_extent_contig(), ocfs2_extents_adjacent() and
798 * ocfs2_extent_rec_contig only work properly against leaf nodes!
799 */
802 u64 blkno)
803 {
810 }
814 {
815 u32 left_range;
821 }
823 static enum ocfs2_contig_type
827 {
830 /*
831 * Refuse to coalesce extent records with different flag
832 * fields - we don't want to mix unwritten extents with user
833 * data.
834 */
848 }
850 /*
851 * NOTE: We can have pretty much any combination of contiguousness and
852 * appending.
853 *
854 * The usefulness of APPEND_TAIL is more in that it lets us know that
855 * we'll have to update the path to that leaf.
856 */
859 APPEND_TAIL,
860 };
864 SPLIT_LEFT,
865 SPLIT_RIGHT,
866 };
874 };
880 };
884 {
893 /*
894 * If the ecc fails, we return the error but otherwise
895 * leave the filesystem running. We know any error is
896 * local to this block.
897 */
903 }
905 /*
906 * Errors after here are fatal.
907 */
915 }
919 "Extent block #%llu has an invalid h_blkno "
924 }
928 "Extent block #%llu has an invalid "
933 }
936 }
940 {
945 ocfs2_validate_extent_block);
947 /* If ocfs2_read_block() got us a new bh, pass it up. */
952 }
955 /*
956 * How many free extents have we got before we need more meta data?
957 */
960 {
976 }
979 }
984 bail:
989 }
991 /* expects array to already be allocated
992 *
993 * sets h_signature, h_blkno, h_suballoc_bit, h_suballoc_slot, and
994 * l_count for you
995 */
1001 {
1003 u16 suballoc_bit_start;
1004 u32 num_got;
1013 meta_ac,
1022 }
1030 }
1035 OCFS2_JOURNAL_ACCESS_CREATE);
1039 }
1043 /* Ok, setup the minimal stuff here. */
1054 suballoc_bit_start++;
1055 first_blkno++;
1057 /* We'll also be dirtied by the caller, so
1058 * this isn't absolutely necessary. */
1060 }
1063 }
1066 bail:
1071 }
1073 }
1075 }
1077 /*
1078 * Helper function for ocfs2_add_branch() and ocfs2_shift_tree_depth().
1079 *
1080 * Returns the sum of the rightmost extent rec logical offset and
1081 * cluster count.
1082 *
1083 * ocfs2_add_branch() uses this to determine what logical cluster
1084 * value should be populated into the leftmost new branch records.
1085 *
1086 * ocfs2_shift_tree_depth() uses this to determine the # clusters
1087 * value for the new topmost tree record.
1088 */
1090 {
1097 }
1099 /*
1100 * Change range of the branches in the right most path according to the leaf
1101 * extent block's rightmost record.
1102 */
1105 {
1115 }
1121 }
1127 }
1133 }
1140 out:
1143 }
1145 /*
1146 * Add an entire tree branch to our inode. eb_bh is the extent block
1147 * to start at, if we don't want to start the branch at the root
1148 * structure.
1149 *
1150 * last_eb_bh is required as we have to update it's next_leaf pointer
1151 * for the new last extent block.
1152 *
1153 * the new branch will be 'empty' in the sense that every block will
1154 * contain a single record with cluster count == 0.
1155 */
1161 {
1179 /* we never add a branch to a leaf. */
1188 /*
1189 * If there is a gap before the root end and the real end
1190 * of the righmost leaf block, we need to remove the gap
1191 * between new_cpos and root_end first so that the tree
1192 * is consistent after we add a new branch(it will start
1193 * from new_cpos).
1194 */
1205 }
1206 }
1208 /* allocate the number of new eb blocks we need */
1210 GFP_KERNEL);
1215 }
1222 }
1224 /* Note: new_eb_bhs[new_blocks - 1] is the guy which will be
1225 * linked with the rest of the tree.
1226 * conversly, new_eb_bhs[0] is the new bottommost leaf.
1227 *
1228 * when we leave the loop, new_last_eb_blk will point to the
1229 * newest leaf, and next_blkno will point to the topmost extent
1230 * block. */
1235 /* ocfs2_create_new_meta_bhs() should create it right! */
1240 OCFS2_JOURNAL_ACCESS_CREATE);
1244 }
1249 /*
1250 * This actually counts as an empty extent as
1251 * c_clusters == 0
1252 */
1255 /*
1256 * eb_el isn't always an interior node, but even leaf
1257 * nodes want a zero'd flags and reserved field so
1258 * this gets the whole 32 bits regardless of use.
1259 */
1266 }
1268 /* This is a bit hairy. We want to update up to three blocks
1269 * here without leaving any of them in an inconsistent state
1270 * in case of error. We don't have to worry about
1271 * journal_dirty erroring as it won't unless we've aborted the
1272 * handle (in which case we would never be here) so reserving
1273 * the write with journal_access is all we need to do. */
1275 OCFS2_JOURNAL_ACCESS_WRITE);
1279 }
1281 OCFS2_JOURNAL_ACCESS_WRITE);
1285 }
1288 OCFS2_JOURNAL_ACCESS_WRITE);
1292 }
1293 }
1295 /* Link the new branch into the rest of the tree (el will
1296 * either be on the root_bh, or the extent block passed in. */
1303 /* fe needs a new last extent block pointer, as does the
1304 * next_leaf on the previously last-extent-block. */
1315 /*
1316 * Some callers want to track the rightmost leaf so pass it
1317 * back here.
1318 */
1324 bail:
1329 }
1332 }
1334 /*
1335 * adds another level to the allocation tree.
1336 * returns back the new extent block so you can add a branch to it
1337 * after this call.
1338 */
1343 {
1345 u32 new_clusters;
1356 }
1359 /* ocfs2_create_new_meta_bhs() should create it right! */
1366 OCFS2_JOURNAL_ACCESS_CREATE);
1370 }
1372 /* copy the root extent list data into the new extent block */
1381 OCFS2_JOURNAL_ACCESS_WRITE);
1385 }
1389 /* update root_bh now */
1398 /* If this is our 1st tree depth shift, then last_eb_blk
1399 * becomes the allocated extent block */
1408 bail:
1412 }
1414 /*
1415 * Should only be called when there is no space left in any of the
1416 * leaf nodes. What we want to do is find the lowest tree depth
1417 * non-leaf extent block with room for new records. There are three
1418 * valid results of this search:
1419 *
1420 * 1) a lowest extent block is found, then we pass it back in
1421 * *lowest_eb_bh and return '0'
1422 *
1423 * 2) the search fails to find anything, but the root_el has room. We
1424 * pass NULL back in *lowest_eb_bh, but still return '0'
1425 *
1426 * 3) the search fails to find anything AND the root_el is full, in
1427 * which case we return > 0
1428 *
1429 * return status < 0 indicates an error.
1430 */
1433 {
1435 u64 blkno;
1448 "Owner %llu has empty "
1453 }
1458 "Owner %llu has extent "
1459 "list where extent # %d has no physical "
1464 }
1473 }
1483 }
1484 }
1486 /* If we didn't find one and the fe doesn't have any room,
1487 * then return '1' */
1493 bail:
1497 }
1499 /*
1500 * Grow a b-tree so that it has more records.
1501 *
1502 * We might shift the tree depth in which case existing paths should
1503 * be considered invalid.
1504 *
1505 * Tree depth after the grow is returned via *final_depth.
1506 *
1507 * *last_eb_bh will be updated by ocfs2_add_branch().
1508 */
1512 {
1525 }
1527 /* We traveled all the way to the bottom of the allocation tree
1528 * and didn't find room for any more extents - we need to add
1529 * another tree level */
1535 depth);
1537 /* ocfs2_shift_tree_depth will return us a buffer with
1538 * the new extent block (so we can pass that to
1539 * ocfs2_add_branch). */
1544 }
1545 depth++;
1547 /*
1548 * Special case: we have room now if we shifted from
1549 * tree_depth 0, so no more work needs to be done.
1550 *
1551 * We won't be calling add_branch, so pass
1552 * back *last_eb_bh as the new leaf. At depth
1553 * zero, it should always be null so there's
1554 * no reason to brelse.
1555 */
1560 }
1561 }
1563 /* call ocfs2_add_branch to add the final part of the tree with
1564 * the new data. */
1566 meta_ac);
1570 }
1572 out:
1577 }
1579 /*
1580 * This function will discard the rightmost extent record.
1581 */
1583 {
1589 /* This will cause us to go off the end of our extent list. */
1595 }
1599 {
1609 /* The tree code before us didn't allow enough room in the leaf. */
1612 /*
1613 * The easiest way to approach this is to just remove the
1614 * empty extent and temporarily decrement next_free.
1615 */
1617 /*
1618 * If next_free was 1 (only an empty extent), this
1619 * loop won't execute, which is fine. We still want
1620 * the decrement above to happen.
1621 */
1625 next_free--;
1626 }
1628 /*
1629 * Figure out what the new record index should be.
1630 */
1636 }
1647 /*
1648 * No need to memmove if we're just adding to the tail.
1649 */
1657 num_bytes);
1658 }
1660 /*
1661 * Either we had an empty extent, and need to re-increment or
1662 * there was no empty extent on a non full rightmost leaf node,
1663 * in which case we still need to increment.
1664 */
1665 next_free++;
1667 /*
1668 * Make sure none of the math above just messed up our tree.
1669 */
1674 }
1677 {
1683 num_recs--;
1689 }
1690 }
1692 /*
1693 * Create an empty extent record .
1694 *
1695 * l_next_free_rec may be updated.
1696 *
1697 * If an empty extent already exists do nothing.
1698 */
1700 {
1719 set_and_inc:
1722 }
1724 /*
1725 * For a rotation which involves two leaf nodes, the "root node" is
1726 * the lowest level tree node which contains a path to both leafs. This
1727 * resulting set of information can be used to form a complete "subtree"
1728 *
1729 * This function is passed two full paths from the dinode down to a
1730 * pair of adjacent leaves. It's task is to figure out which path
1731 * index contains the subtree root - this can be the root index itself
1732 * in a worst-case rotation.
1733 *
1734 * The array index of the subtree root is passed back.
1735 */
1739 {
1742 /*
1743 * Check that the caller passed in two paths from the same tree.
1744 */
1748 i++;
1750 /*
1751 * The caller didn't pass two adjacent paths.
1752 */
1764 }
1768 /*
1769 * Traverse a btree path in search of cpos, starting at root_el.
1770 *
1771 * This code can be called with a cpos larger than the tree, in which
1772 * case it will return the rightmost path.
1773 */
1777 {
1779 u32 range;
1780 u64 blkno;
1790 "Owner %llu has empty extent list at "
1797 }
1802 /*
1803 * In the case that cpos is off the allocation
1804 * tree, this should just wind up returning the
1805 * rightmost record.
1806 */
1811 }
1816 "Owner %llu has bad blkno in extent list "
1822 }
1830 }
1838 "Owner %llu has bad count in extent list "
1846 }
1850 }
1852 out:
1853 /*
1854 * Catch any trailing bh that the loop didn't handle.
1855 */
1859 }
1861 /*
1862 * Given an initialized path (that is, it has a valid root extent
1863 * list), this function will traverse the btree in search of the path
1864 * which would contain cpos.
1865 *
1866 * The path traveled is recorded in the path structure.
1867 *
1868 * Note that this will not do any comparisons on leaf node extent
1869 * records, so it will work fine in the case that we just added a tree
1870 * branch.
1871 */
1875 };
1877 {
1883 }
1886 {
1893 }
1896 {
1901 /* We want to retain only the leaf block. */
1905 }
1906 }
1907 /*
1908 * Find the leaf block in the tree which would contain cpos. No
1909 * checking of the actual leaf is done.
1910 *
1911 * Some paths want to call this instead of allocating a path structure
1912 * and calling ocfs2_find_path().
1913 *
1914 * This function doesn't handle non btree extent lists.
1915 */
1919 {
1927 }
1930 out:
1932 }
1934 /*
1935 * Adjust the adjacent records (left_rec, right_rec) involved in a rotation.
1936 *
1937 * Basically, we've moved stuff around at the bottom of the tree and
1938 * we need to fix up the extent records above the changes to reflect
1939 * the new changes.
1940 *
1941 * left_rec: the record on the left.
1942 * left_child_el: is the child list pointed to by left_rec
1943 * right_rec: the record to the right of left_rec
1944 * right_child_el: is the child list pointed to by right_rec
1945 *
1946 * By definition, this only works on interior nodes.
1947 */
1952 {
1955 /*
1956 * Interior nodes never have holes. Their cpos is the cpos of
1957 * the leftmost record in their child list. Their cluster
1958 * count covers the full theoretical range of their child list
1959 * - the range between their cpos and the cpos of the record
1960 * immediately to their right.
1961 */
1967 }
1971 /*
1972 * Calculate the rightmost cluster count boundary before
1973 * moving cpos - we will need to adjust clusters after
1974 * updating e_cpos to keep the same highest cluster count.
1975 */
1984 }
1986 /*
1987 * Adjust the adjacent root node records involved in a
1988 * rotation. left_el_blkno is passed in as a key so that we can easily
1989 * find it's index in the root list.
1990 */
1994 u64 left_el_blkno)
1995 {
2004 }
2006 /*
2007 * The path walking code should have never returned a root and
2008 * two paths which are not adjacent.
2009 */
2014 }
2016 /*
2017 * We've changed a leaf block (in right_path) and need to reflect that
2018 * change back up the subtree.
2019 *
2020 * This happens in multiple places:
2021 * - When we've moved an extent record from the left path leaf to the right
2022 * path leaf to make room for an empty extent in the left path leaf.
2023 * - When our insert into the right path leaf is at the leftmost edge
2024 * and requires an update of the path immediately to it's left. This
2025 * can occur at the end of some types of rotation and appending inserts.
2026 * - When we've adjusted the last extent record in the left path leaf and the
2027 * 1st extent record in the right path leaf during cross extent block merge.
2028 */
2033 {
2039 /*
2040 * Update the counts and position values within all the
2041 * interior nodes to reflect the leaf rotation we just did.
2042 *
2043 * The root node is handled below the loop.
2044 *
2045 * We begin the loop with right_el and left_el pointing to the
2046 * leaf lists and work our way up.
2047 *
2048 * NOTE: within this loop, left_el and right_el always refer
2049 * to the *child* lists.
2050 */
2056 /*
2057 * One nice property of knowing that all of these
2058 * nodes are below the root is that we only deal with
2059 * the leftmost right node record and the rightmost
2060 * left node record.
2061 */
2070 right_el);
2075 /*
2076 * Setup our list pointers now so that the current
2077 * parents become children in the next iteration.
2078 */
2081 }
2083 /*
2084 * At the root node, adjust the two adjacent records which
2085 * begin our path to the leaves.
2086 */
2098 }
2105 {
2118 "Inode %llu has non-full interior leaf node %llu"
2124 }
2126 /*
2127 * This extent block may already have an empty record, so we
2128 * return early if so.
2129 */
2137 subtree_index);
2141 }
2149 }
2156 }
2157 }
2162 /* This is a code error, not a disk corruption. */
2172 /* Do the copy now. */
2177 /*
2178 * Clear out the record we just copied and shift everything
2179 * over, leaving an empty extent in the left leaf.
2180 *
2181 * We temporarily subtract from next_free_rec so that the
2182 * shift will lose the tail record (which is now defunct).
2183 */
2192 subtree_index);
2194 out:
2196 }
2198 /*
2199 * Given a full path, determine what cpos value would return us a path
2200 * containing the leaf immediately to the left of the current one.
2201 *
2202 * Will return zero if the path passed in is already the leftmost path.
2203 */
2206 {
2208 u64 blkno;
2217 /* Start at the tree node just above the leaf and work our way up. */
2222 /*
2223 * Find the extent record just before the one in our
2224 * path.
2225 */
2230 /*
2231 * We've determined that the
2232 * path specified is already
2233 * the leftmost one - return a
2234 * cpos of zero.
2235 */
2237 }
2238 /*
2239 * The leftmost record points to our
2240 * leaf - we need to travel up the
2241 * tree one level.
2242 */
2244 }
2251 }
2252 }
2254 /*
2255 * If we got here, we never found a valid node where
2256 * the tree indicated one should be.
2257 */
2264 next_node:
2266 i--;
2267 }
2269 out:
2271 }
2273 /*
2274 * Extend the transaction by enough credits to complete the rotation,
2275 * and still leave at least the original number of credits allocated
2276 * to this transaction.
2277 */
2281 {
2290 }
2292 /*
2293 * Trap the case where we're inserting into the theoretical range past
2294 * the _actual_ left leaf range. Otherwise, we'll rotate a record
2295 * whose cpos is less than ours into the right leaf.
2296 *
2297 * It's only necessary to look at the rightmost record of the left
2298 * leaf because the logic that calls us should ensure that the
2299 * theoretical ranges in the path components above the leaves are
2300 * correct.
2301 */
2303 u32 insert_cpos)
2304 {
2316 }
2319 {
2329 /* Empty list. */
2333 }
2339 }
2341 /*
2342 * Rotate all the records in a btree right one record, starting at insert_cpos.
2343 *
2344 * The path to the rightmost leaf should be passed in.
2345 *
2346 * The array is assumed to be large enough to hold an entire path (tree depth).
2347 *
2348 * Upon successful return from this function:
2349 *
2350 * - The 'right_path' array will contain a path to the leaf block
2351 * whose range contains e_cpos.
2352 * - That leaf block will have a single empty extent in list index 0.
2353 * - In the case that the rotation requires a post-insert update,
2354 * *ret_left_path will contain a valid path which can be passed to
2355 * ocfs2_insert_path().
2356 */
2360 u32 insert_cpos,
2363 {
2365 u32 cpos;
2376 }
2382 }
2388 /*
2389 * What we want to do here is:
2390 *
2391 * 1) Start with the rightmost path.
2392 *
2393 * 2) Determine a path to the leaf block directly to the left
2394 * of that leaf.
2395 *
2396 * 3) Determine the 'subtree root' - the lowest level tree node
2397 * which contains a path to both leaves.
2398 *
2399 * 4) Rotate the subtree.
2400 *
2401 * 5) Find the next subtree by considering the left path to be
2402 * the new right path.
2403 *
2404 * The check at the top of this while loop also accepts
2405 * insert_cpos == cpos because cpos is only a _theoretical_
2406 * value to get us the left path - insert_cpos might very well
2407 * be filling that hole.
2408 *
2409 * Stop at a cpos of '0' because we either started at the
2410 * leftmost branch (i.e., a tree with one branch and a
2411 * rotation inside of it), or we've gone as far as we can in
2412 * rotating subtrees.
2413 */
2424 }
2428 "Owner %llu: error during insert of %u "
2429 "(left path cpos %u) results in two identical "
2438 insert_cpos)) {
2440 /*
2441 * We've rotated the tree as much as we
2442 * should. The rest is up to
2443 * ocfs2_insert_path() to complete, after the
2444 * record insertion. We indicate this
2445 * situation by returning the left path.
2446 *
2447 * The reason we don't adjust the records here
2448 * before the record insert is that an error
2449 * later might break the rule where a parent
2450 * record e_cpos will reflect the actual
2451 * e_cpos of the 1st nonempty record of the
2452 * child list.
2453 */
2456 }
2470 }
2477 }
2481 insert_cpos)) {
2482 /*
2483 * A rotate moves the rightmost left leaf
2484 * record over to the leftmost right leaf
2485 * slot. If we're doing an extent split
2486 * instead of a real insert, then we have to
2487 * check that the extent to be split wasn't
2488 * just moved over. If it was, then we can
2489 * exit here, passing left_path back -
2490 * ocfs2_split_extent() is smart enough to
2491 * search both leaves.
2492 */
2495 }
2497 /*
2498 * There is no need to re-read the next right path
2499 * as we know that it'll be our current left
2500 * path. Optimize by copying values instead.
2501 */
2508 }
2509 }
2511 out:
2514 out_ret_path:
2516 }
2521 {
2526 u32 range;
2528 /*
2529 * In normal tree rotation process, we will never touch the
2530 * tree branch above subtree_index and ocfs2_extend_rotate_transaction
2531 * doesn't reserve the credits for them either.
2532 *
2533 * But we do have a special case here which will update the rightmost
2534 * records for all the bh in the path.
2535 * So we have to allocate extra credits and access them.
2536 */
2541 }
2547 }
2549 /* Path should always be rightmost. */
2568 }
2569 out:
2571 }
2577 {
2587 /*
2588 * Not all nodes might have had their final count
2589 * decremented by the caller - handle this here.
2590 */
2594 "Inode %llu, attempted to remove extent block "
2603 }
2615 }
2616 }
2624 {
2652 }
2661 {
2679 /*
2680 * It's legal for us to proceed if the right leaf is
2681 * the rightmost one and it has an empty extent. There
2682 * are two cases to handle - whether the leaf will be
2683 * empty after removal or not. If the leaf isn't empty
2684 * then just remove the empty extent up front. The
2685 * next block will handle empty leaves by flagging
2686 * them for unlink.
2687 *
2688 * Non rightmost leaves will throw -EAGAIN and the
2689 * caller can manually move the subtree and retry.
2690 */
2698 OCFS2_JOURNAL_ACCESS_WRITE);
2702 }
2707 }
2711 /*
2712 * We have to update i_last_eb_blk during the meta
2713 * data delete.
2714 */
2716 OCFS2_JOURNAL_ACCESS_WRITE);
2720 }
2723 }
2725 /*
2726 * Getting here with an empty extent in the right path implies
2727 * that it's the rightmost path and will be deleted.
2728 */
2732 subtree_index);
2736 }
2744 }
2751 }
2752 }
2755 /*
2756 * Only do this if we're moving a real
2757 * record. Otherwise, the action is delayed until
2758 * after removal of the right path in which case we
2759 * can do a simple shift to remove the empty extent.
2760 */
2764 }
2766 /*
2767 * Move recs over to get rid of empty extent, decrease
2768 * next_free. This is allowed to remove the last
2769 * extent in our leaf (setting l_next_free_rec to
2770 * zero) - the delete code below won't care.
2771 */
2773 }
2782 left_path);
2786 }
2791 /*
2792 * Removal of the extent in the left leaf was skipped
2793 * above so we could delete the right path
2794 * 1st.
2795 */
2804 subtree_index);
2806 out:
2808 }
2810 /*
2811 * Given a full path, determine what cpos value would return us a path
2812 * containing the leaf immediately to the right of the current one.
2813 *
2814 * Will return zero if the path passed in is already the rightmost path.
2815 *
2816 * This looks similar, but is subtly different to
2817 * ocfs2_find_cpos_for_left_leaf().
2818 */
2821 {
2823 u64 blkno;
2833 /* Start at the tree node just above the leaf and work our way up. */
2840 /*
2841 * Find the extent record just after the one in our
2842 * path.
2843 */
2849 /*
2850 * We've determined that the
2851 * path specified is already
2852 * the rightmost one - return a
2853 * cpos of zero.
2854 */
2856 }
2857 /*
2858 * The rightmost record points to our
2859 * leaf - we need to travel up the
2860 * tree one level.
2861 */
2863 }
2867 }
2868 }
2870 /*
2871 * If we got here, we never found a valid node where
2872 * the tree indicated one should be.
2873 */
2880 next_node:
2882 i--;
2883 }
2885 out:
2887 }
2892 {
2905 }
2910 out:
2912 }
2920 {
2922 u32 right_cpos;
2935 }
2942 }
2951 }
2958 }
2961 right_path);
2973 }
2975 /*
2976 * Caller might still want to make changes to the
2977 * tree root, so re-add it to the journal here.
2978 */
2984 }
2990 /*
2991 * The rotation has to temporarily stop due to
2992 * the right subtree having an empty
2993 * extent. Pass it back to the caller for a
2994 * fixup.
2995 */
2999 }
3003 }
3005 /*
3006 * The subtree rotate might have removed records on
3007 * the rightmost edge. If so, then rotation is
3008 * complete.
3009 */
3020 }
3021 }
3023 out:
3028 }
3034 {
3036 u32 cpos;
3045 /*
3046 * There's two ways we handle this depending on
3047 * whether path is the only existing one.
3048 */
3051 path);
3055 }
3061 }
3068 }
3071 /*
3072 * We have a path to the left of this one - it needs
3073 * an update too.
3074 */
3080 }
3086 }
3092 }
3099 left_path);
3103 }
3108 /*
3109 * 'path' is also the leftmost path which
3110 * means it must be the only one. This gets
3111 * handled differently because we want to
3112 * revert the root back to having extents
3113 * in-line.
3114 */
3123 }
3127 out:
3130 }
3132 /*
3133 * Left rotation of btree records.
3134 *
3135 * In many ways, this is (unsurprisingly) the opposite of right
3136 * rotation. We start at some non-rightmost path containing an empty
3137 * extent in the leaf block. The code works its way to the rightmost
3138 * path by rotating records to the left in every subtree.
3139 *
3140 * This is used by any code which reduces the number of extent records
3141 * in a leaf. After removal, an empty record should be placed in the
3142 * leftmost list position.
3143 *
3144 * This won't handle a length update of the rightmost path records if
3145 * the rightmost tree leaf record is removed so the caller is
3146 * responsible for detecting and correcting that.
3147 */
3152 {
3163 rightmost_no_delete:
3164 /*
3165 * Inline extents. This is trivially handled, so do
3166 * it up front.
3167 */
3172 }
3174 /*
3175 * Handle rightmost branch now. There's several cases:
3176 * 1) simple rotation leaving records in there. That's trivial.
3177 * 2) rotation requiring a branch delete - there's no more
3178 * records left. Two cases of this:
3179 * a) There are branches to the left.
3180 * b) This is also the leftmost (the only) branch.
3181 *
3182 * 1) is handled via ocfs2_rotate_rightmost_leaf_left()
3183 * 2a) we need the left branch so that we can update it with the unlink
3184 * 2b) we need to bring the root back to inline extents.
3185 */
3190 /*
3191 * This gets a bit tricky if we're going to delete the
3192 * rightmost path. Get the other cases out of the way
3193 * 1st.
3194 */
3205 }
3207 /*
3208 * XXX: The caller can not trust "path" any more after
3209 * this as it will have been deleted. What do we do?
3210 *
3211 * In theory the rotate-for-merge code will never get
3212 * here because it'll always ask for a rotate in a
3213 * nonempty list.
3214 */
3217 dealloc);
3221 }
3223 /*
3224 * Now we can loop, remembering the path we get from -EAGAIN
3225 * and restarting from there.
3226 */
3227 try_rotate:
3233 }
3245 }
3252 }
3254 out:
3258 }
3262 {
3267 /*
3268 * We consumed all of the merged-from record. An empty
3269 * extent cannot exist anywhere but the 1st array
3270 * position, so move things over if the merged-from
3271 * record doesn't occupy that position.
3272 *
3273 * This creates a new empty extent so the caller
3274 * should be smart enough to have removed any existing
3275 * ones.
3276 */
3281 }
3283 /*
3284 * Always memset - the caller doesn't check whether it
3285 * created an empty extent, so there could be junk in
3286 * the other fields.
3287 */
3289 }
3290 }
3295 {
3297 u32 right_cpos;
3303 /* This function shouldn't be called for non-trees. */
3314 }
3316 /* This function shouldn't be called for the rightmost leaf. */
3324 }
3330 }
3333 out:
3337 }
3339 /*
3340 * Remove split_rec clusters from the record at index and merge them
3341 * onto the beginning of the record "next" to it.
3342 * For index < l_count - 1, the next means the extent rec at index + 1.
3343 * For index == l_count - 1, the "next" means the 1st extent rec of the
3344 * next extent block.
3345 */
3351 {
3368 /* we meet with a cross extent block merge. */
3373 }
3382 }
3389 right_path);
3393 right_path);
3397 }
3403 subtree_index);
3407 }
3416 }
3423 }
3424 }
3429 }
3436 }
3443 split_clusters));
3452 subtree_index);
3453 }
3454 out:
3458 }
3463 {
3465 u32 left_cpos;
3470 /* This function shouldn't be called for non-trees. */
3478 }
3480 /* This function shouldn't be called for the leftmost leaf. */
3488 }
3494 }
3497 out:
3501 }
3503 /*
3504 * Remove split_rec clusters from the record at index and merge them
3505 * onto the tail of the record "before" it.
3506 * For index > 0, the "before" means the extent rec at index - 1.
3507 *
3508 * For index == 0, the "before" means the last record of the previous
3509 * extent block. And there is also a situation that we may need to
3510 * remove the rightmost leaf extent block in the right_path and change
3511 * the right path to indicate the new rightmost path.
3512 */
3519 {
3534 /* we meet with a cross extent block merge. */
3539 }
3552 right_path);
3556 left_path);
3560 }
3566 subtree_index);
3570 }
3579 }
3586 }
3587 }
3592 }
3599 }
3602 /*
3603 * The easy case - we can just plop the record right in.
3604 */
3614 split_clusters));
3623 /*
3624 * In the situation that the right_rec is empty and the extent
3625 * block is empty also, ocfs2_complete_edge_insert can't handle
3626 * it and we need to delete the right extent block.
3627 */
3632 right_path,
3633 dealloc);
3637 }
3639 /* Now the rightmost extent block has been deleted.
3640 * So we use the new rightmost path.
3641 */
3647 }
3648 out:
3652 }
3661 {
3669 /*
3670 * The merge code will need to create an empty
3671 * extent to take the place of the newly
3672 * emptied slot. Remove any pre-existing empty
3673 * extents - having more than one in a leaf is
3674 * illegal.
3675 */
3680 }
3681 split_index--;
3683 }
3686 /*
3687 * Left-right contig implies this.
3688 */
3691 /*
3692 * Since the leftright insert always covers the entire
3693 * extent, this call will delete the insert record
3694 * entirely, resulting in an empty extent record added to
3695 * the extent block.
3696 *
3697 * Since the adding of an empty extent shifts
3698 * everything back to the right, there's no need to
3699 * update split_index here.
3700 *
3701 * When the split_index is zero, we need to merge it to the
3702 * prevoius extent block. It is more efficient and easier
3703 * if we do merge_right first and merge_left later.
3704 */
3706 split_index);
3710 }
3712 /*
3713 * We can only get this from logic error above.
3714 */
3717 /* The merge left us with an empty extent, remove it. */
3722 }
3726 /*
3727 * Note that we don't pass split_rec here on purpose -
3728 * we've merged it into the rec already.
3729 */
3736 }
3739 /*
3740 * Error from this last rotate is not critical, so
3741 * print but don't bubble it up.
3742 */
3747 /*
3748 * Merge a record to the left or right.
3749 *
3750 * 'contig_type' is relative to the existing record,
3751 * so for example, if we're "right contig", it's to
3752 * the record on the left (hence the left merge).
3753 */
3757 split_index);
3761 }
3765 split_index);
3769 }
3770 }
3773 /*
3774 * The merge may have left an empty extent in
3775 * our leaf. Try to rotate it away.
3776 */
3778 dealloc);
3782 }
3783 }
3785 out:
3787 }
3793 {
3794 u64 len_blocks;
3800 /*
3801 * Region is on the left edge of the existing
3802 * record.
3803 */
3810 /*
3811 * Region is on the right edge of the existing
3812 * record.
3813 */
3816 }
3817 }
3819 /*
3820 * Do the final bits of extent record insertion at the target leaf
3821 * list. If this leaf is part of an allocation tree, it is assumed
3822 * that the tree above has been prepared.
3823 */
3828 {
3841 insert_rec);
3843 }
3845 /*
3846 * Contiguous insert - either left or right.
3847 */
3853 }
3857 }
3859 /*
3860 * Handle insert into an empty leaf.
3861 */
3868 }
3870 /*
3871 * Appending insert.
3872 */
3882 "owner %llu, depth %u, count %u, next free %u, "
3883 "rec.cpos %u, rec.clusters %u, "
3893 i++;
3897 }
3899 rotate:
3900 /*
3901 * Ok, we have to rotate.
3902 *
3903 * At this point, it is safe to assume that inserting into an
3904 * empty leaf and appending to a leaf have both been handled
3905 * above.
3906 *
3907 * This leaf needs to have space, either by the empty 1st
3908 * extent record, or by virtue of an l_next_rec < l_count.
3909 */
3911 }
3917 {
3923 /*
3924 * Update everything except the leaf block.
3925 */
3937 }
3948 }
3949 }
3956 {
3963 /*
3964 * This shouldn't happen for non-trees. The extent rec cluster
3965 * count manipulation below only works for interior nodes.
3966 */
3969 /*
3970 * If our appending insert is at the leftmost edge of a leaf,
3971 * then we might need to update the rightmost records of the
3972 * neighboring path.
3973 */
3978 u32 left_cpos;
3985 }
3991 left_cpos);
3993 /*
3994 * No need to worry if the append is already in the
3995 * leftmost leaf.
3996 */
4003 }
4006 left_cpos);
4010 }
4012 /*
4013 * ocfs2_insert_path() will pass the left_path to the
4014 * journal for us.
4015 */
4016 }
4017 }
4023 }
4029 out:
4034 }
4041 {
4058 /*
4059 * This typically means that the record
4060 * started in the left path but moved to the
4061 * right as a result of rotation. We either
4062 * move the existing record to the left, or we
4063 * do the later insert there.
4064 *
4065 * In this case, the left path should always
4066 * exist as the rotate code will have passed
4067 * it back for a post-insert update.
4068 */
4071 /*
4072 * It's a left split. Since we know
4073 * that the rotate code gave us an
4074 * empty extent in the left path, we
4075 * can just do the insert there.
4076 */
4079 /*
4080 * Right split - we have to move the
4081 * existing record over to the left
4082 * leaf. The insert will be into the
4083 * newly created empty extent in the
4084 * right leaf.
4085 */
4093 }
4094 }
4098 /*
4099 * Left path is easy - we can just allow the insert to
4100 * happen.
4101 */
4106 }
4112 }
4114 /*
4115 * This function only does inserts on an allocation b-tree. For tree
4116 * depth = 0, ocfs2_insert_at_leaf() is called directly.
4117 *
4118 * right_path is the path we want to do the actual insert
4119 * in. left_path should only be passed in if we need to update that
4120 * portion of the tree after an edge insert.
4121 */
4128 {
4133 /*
4134 * There's a chance that left_path got passed back to
4135 * us without being accounted for in the
4136 * journal. Extend our transaction here to be sure we
4137 * can change those blocks.
4138 */
4143 }
4149 }
4150 }
4152 /*
4153 * Pass both paths to the journal. The majority of inserts
4154 * will be touching all components anyway.
4155 */
4160 }
4163 /*
4164 * We could call ocfs2_insert_at_leaf() for some types
4165 * of splits, but it's easier to just let one separate
4166 * function sort it all out.
4167 */
4171 /*
4172 * Split might have modified either leaf and we don't
4173 * have a guarantee that the later edge insert will
4174 * dirty this for us.
4175 */
4181 insert);
4186 /*
4187 * The rotate code has indicated that we need to fix
4188 * up portions of the tree after the insert.
4189 *
4190 * XXX: Should we extend the transaction here?
4191 */
4193 right_path);
4195 subtree_index);
4196 }
4199 out:
4201 }
4207 {
4209 u32 cpos;
4217 OCFS2_JOURNAL_ACCESS_WRITE);
4221 }
4226 }
4233 }
4235 /*
4236 * Determine the path to start with. Rotations need the
4237 * rightmost path, everything else can go directly to the
4238 * target leaf.
4239 */
4245 }
4251 }
4253 /*
4254 * Rotations and appends need special treatment - they modify
4255 * parts of the tree's above them.
4256 *
4257 * Both might pass back a path immediate to the left of the
4258 * one being inserted to. This will be cause
4259 * ocfs2_insert_path() to modify the rightmost records of
4260 * left_path to account for an edge insert.
4261 *
4262 * XXX: When modifying this code, keep in mind that an insert
4263 * can wind up skipping both of these two special cases...
4264 */
4272 }
4274 /*
4275 * ocfs2_rotate_tree_right() might have extended the
4276 * transaction without re-journaling our tree root.
4277 */
4279 OCFS2_JOURNAL_ACCESS_WRITE);
4283 }
4291 }
4292 }
4299 }
4301 out_update_clusters:
4308 out:
4313 }
4315 static enum ocfs2_contig_type
4320 {
4344 left_cpos);
4355 "Extent block #%llu has an "
4356 "invalid l_next_free_rec of "
4357 "%d. It should have "
4364 }
4367 }
4368 }
4370 /*
4371 * We're careful to check for an empty extent record here -
4372 * the merge code will know what to do if it sees one.
4373 */
4380 }
4381 }
4410 "Extent block #%llu has an "
4416 }
4418 }
4419 }
4430 }
4432 out:
4439 }
4445 {
4453 insert_rec);
4457 }
4458 }
4467 /*
4468 * Caller might want us to limit the size of extents, don't
4469 * calculate contiguousness if we might exceed that limit.
4470 */
4474 }
4475 }
4477 /*
4478 * This should only be called against the righmost leaf extent list.
4479 *
4480 * ocfs2_figure_appending_type() will figure out whether we'll have to
4481 * insert at the tail of the rightmost leaf.
4482 *
4483 * This should also work against the root extent list for tree's with 0
4484 * depth. If we consider the root extent list to be the rightmost leaf node
4485 * then the logic here makes sense.
4486 */
4490 {
4503 /* Were all records empty? */
4506 }
4517 set_tail_append:
4519 }
4521 /*
4522 * Helper function called at the begining of an insert.
4523 *
4524 * This computes a few things that are commonly used in the process of
4525 * inserting into the btree:
4526 * - Whether the new extent is contiguous with an existing one.
4527 * - The current tree depth.
4528 * - Whether the insert is an appending one.
4529 * - The total # of free records in the tree.
4530 *
4531 * All of the information is stored on the ocfs2_insert_type
4532 * structure.
4533 */
4539 {
4552 /*
4553 * If we have tree depth, we read in the
4554 * rightmost extent block ahead of time as
4555 * ocfs2_figure_insert_type() and ocfs2_add_branch()
4556 * may want it later.
4557 */
4564 }
4567 }
4569 /*
4570 * Unless we have a contiguous insert, we'll need to know if
4571 * there is room left in our allocation tree for another
4572 * extent record.
4573 *
4574 * XXX: This test is simplistic, we can search for empty
4575 * extent records too.
4576 */
4584 }
4591 }
4593 /*
4594 * In the case that we're inserting past what the tree
4595 * currently accounts for, ocfs2_find_path() will return for
4596 * us the rightmost tree path. This is accounted for below in
4597 * the appending code.
4598 */
4603 }
4607 /*
4608 * Now that we have the path, there's two things we want to determine:
4609 * 1) Contiguousness (also set contig_index if this is so)
4610 *
4611 * 2) Are we doing an append? We can trivially break this up
4612 * into two types of appends: simple record append, or a
4613 * rotate inside the tail leaf.
4614 */
4617 /*
4618 * The insert code isn't quite ready to deal with all cases of
4619 * left contiguousness. Specifically, if it's an insert into
4620 * the 1st record in a leaf, it will require the adjustment of
4621 * cluster count on the last record of the path directly to it's
4622 * left. For now, just catch that case and fool the layers
4623 * above us. This works just fine for tree_depth == 0, which
4624 * is why we allow that above.
4625 */
4630 /*
4631 * Ok, so we can simply compare against last_eb to figure out
4632 * whether the path doesn't exist. This will only happen in
4633 * the case that we're doing a tail append, so maybe we can
4634 * take advantage of that information somehow.
4635 */
4638 /*
4639 * Ok, ocfs2_find_path() returned us the rightmost
4640 * tree path. This might be an appending insert. There are
4641 * two cases:
4642 * 1) We're doing a true append at the tail:
4643 * -This might even be off the end of the leaf
4644 * 2) We're "appending" by rotating in the tail
4645 */
4647 }
4649 out:
4654 else
4657 }
4659 /*
4660 * Insert an extent into a btree.
4661 *
4662 * The caller needs to update the owning btree's cluster count.
4663 */
4666 u32 cpos,
4667 u64 start_blk,
4668 u32 new_clusters,
4669 u8 flags,
4671 {
4691 }
4698 }
4707 meta_ac);
4711 }
4712 }
4714 /* Finally, we can add clusters. This might rotate the tree for us. */
4718 else
4721 bail:
4725 }
4727 /*
4728 * Allcate and add clusters into the extent b-tree.
4729 * The new clusters(clusters_to_add) will be inserted at logical_offset.
4730 * The extent b-tree's root is specified by et, and
4731 * it is not limited to the file storage. Any extent tree can use this
4732 * function if it implements the proper ocfs2_extent_tree.
4733 */
4737 u32 clusters_to_add,
4742 {
4747 u64 block;
4762 }
4764 /* there are two cases which could cause us to EAGAIN in the
4765 * we-need-more-metadata case:
4766 * 1) we haven't reserved *any*
4767 * 2) we are so fragmented, we've needed to add metadata too
4768 * many times. */
4781 }
4789 }
4793 /* reserve our write early -- insert_extent may update the tree root */
4795 OCFS2_JOURNAL_ACCESS_WRITE);
4799 }
4810 }
4821 }
4823 leave:
4828 }
4832 u32 cpos,
4834 {
4848 }
4857 {
4867 leftright:
4868 /*
4869 * Store a copy of the record on the stack - it might move
4870 * around as the tree is manipulated below.
4871 */
4881 }
4890 }
4891 }
4908 /*
4909 * Left/right split. We fake this as a right split
4910 * first and then make a second pass as a left split.
4911 */
4921 }
4927 }
4930 u32 cpos;
4933 do_leftright++;
4943 }
4948 }
4949 out:
4952 }
4960 {
4968 }
4973 out:
4975 }
4977 /*
4978 * Split part or all of the extent record at split_index in the leaf
4979 * pointed to by path. Merge with the contiguous extent record if needed.
4980 *
4981 * Care is taken to handle contiguousness so as to not grow the tree.
4982 *
4983 * meta_ac is not strictly necessary - we only truly need it if growth
4984 * of the tree is required. All other cases will degrade into a less
4985 * optimal tree layout.
4986 *
4987 * last_eb_bh should be the rightmost leaf block for any extent
4988 * btree. Since a split may grow the tree or a merge might shrink it,
4989 * the caller cannot trust the contents of that buffer after this call.
4990 *
4991 * This code is optimized for readability - several passes might be
4992 * made over certain portions of the tree. All of those blocks will
4993 * have been brought into cache (and pinned via the journal), so the
4994 * extra overhead is not expressed in terms of disk reads.
4995 */
5003 {
5017 }
5020 split_index,
5021 split_rec);
5023 /*
5024 * The core merge / split code wants to know how much room is
5025 * left in this allocation tree, so we pass the
5026 * rightmost extent list.
5027 */
5037 }
5047 else
5060 else
5072 }
5074 out:
5077 }
5079 /*
5080 * Change the flags of the already-existing extent at cpos for len clusters.
5081 *
5082 * new_flags: the flags we want to set.
5083 * clear_flags: the flags we want to clear.
5084 * phys: the new physical offset we want this new extent starts from.
5085 *
5086 * If the existing extent is larger than the request, initiate a
5087 * split. An attempt will be made at merging with adjacent extents.
5088 *
5089 * The caller is responsible for passing down meta_ac if we'll need it.
5090 */
5097 {
5111 }
5117 }
5123 "Owner %llu has an extent at cpos %u which can no "
5129 }
5137 new_flags);
5139 }
5145 clear_flags);
5147 }
5161 dealloc);
5165 out:
5169 }
5171 /*
5172 * Mark the already-existing extent at cpos as written for len clusters.
5173 * This removes the unwritten extent flag.
5174 *
5175 * If the existing extent is larger than the request, initiate a
5176 * split. An attempt will be made at merging with adjacent extents.
5177 *
5178 * The caller is responsible for passing down meta_ac if we'll need it.
5179 */
5185 {
5194 "that are being written to, but the feature bit "
5199 }
5201 /*
5202 * XXX: This should be fixed up so that we just re-insert the
5203 * next extent records.
5204 */
5213 out:
5215 }
5221 {
5230 /*
5231 * Setup the record to split before we grow the tree.
5232 */
5246 }
5259 }
5264 meta_ac);
5268 }
5269 }
5281 out:
5284 }
5291 {
5306 }
5308 index--;
5309 }
5313 /*
5314 * Check whether this is the rightmost tree record. If
5315 * we remove all of this record or part of its right
5316 * edge then an update of the record lengths above it
5317 * will be required.
5318 */
5322 }
5327 /*
5328 * Changing the leftmost offset (via partial or whole
5329 * record truncate) of an interior (or rightmost) path
5330 * means we have to update the subtree that is formed
5331 * by this leaf and the one to it's left.
5332 *
5333 * There are two cases we can skip:
5334 * 1) Path is the leftmost one in our btree.
5335 * 2) The leaf is rightmost and will be empty after
5336 * we remove the extent record - the rotate code
5337 * knows how to update the newly formed edge.
5338 */
5344 }
5352 }
5355 left_cpos);
5359 }
5360 }
5361 }
5365 path);
5369 }
5375 }
5381 }
5395 /*
5396 * We skip the edge update if this path will
5397 * be deleted by the rotate code.
5398 */
5401 rec);
5402 }
5404 /* Remove leftmost portion of the record. */
5409 /* Remove rightmost portion of the record */
5414 /* Caller should have trapped this. */
5421 }
5428 subtree_index);
5429 }
5437 }
5439 out:
5442 }
5449 {
5456 /*
5457 * XXX: Why are we truncating to 0 instead of wherever this
5458 * affects us?
5459 */
5467 }
5473 }
5479 "Owner %llu has an extent at cpos %u which can no "
5482 cpos);
5485 }
5487 /*
5488 * We have 3 cases of extent removal:
5489 * 1) Range covers the entire extent rec
5490 * 2) Range begins or ends on one edge of the extent rec
5491 * 3) Range is in the middle of the extent rec (no shared edges)
5492 *
5493 * For case 1 we remove the extent rec and left rotate to
5494 * fill the hole.
5495 *
5496 * For case 2 we just shrink the existing extent rec, with a
5497 * tree update if the shrinking edge is also the edge of an
5498 * extent block.
5499 *
5500 * For case 3 we do a right split to turn the extent rec into
5501 * something case 2 can handle.
5502 */
5520 }
5527 }
5529 /*
5530 * The split could have manipulated the tree enough to
5531 * move the record location, so we have to look for it again.
5532 */
5539 }
5547 cpos);
5550 }
5552 /*
5553 * Double check our values here. If anything is fishy,
5554 * it's easier to catch it at the top level.
5555 */
5561 "Owner %llu: error after split at cpos %u"
5568 }
5575 }
5576 }
5578 out:
5581 }
5583 /*
5584 * ocfs2_reserve_blocks_for_rec_trunc() would look basically the
5585 * same as ocfs2_lock_alloctors(), except for it accepts a blocks
5586 * number to reserve some extra blocks, and it only handles meta
5587 * data allocations.
5588 *
5589 * Currently, only ocfs2_remove_btree_range() uses it for truncating
5590 * and punching holes.
5591 */
5594 u32 extents_to_split,
5597 {
5609 }
5621 }
5622 }
5624 out:
5629 }
5630 }
5633 }
5639 u64 refcount_loc)
5640 {
5651 OCFS2_HAS_REFCOUNT_FL));
5658 }
5661 refcount_loc,
5662 phys_blkno,
5663 len,
5669 }
5670 }
5673 extra_blocks);
5677 }
5686 }
5687 }
5695 }
5698 OCFS2_JOURNAL_ACCESS_WRITE);
5702 }
5711 }
5721 phys_blkno),
5724 else
5730 }
5732 out_commit:
5734 out:
5744 }
5747 {
5756 "slot %d, invalid truncate log parameters: used = "
5760 }
5764 {
5768 /* No records, nothing to coalesce */
5777 }
5781 u64 start_blk,
5783 {
5797 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5798 * by the underlying call to ocfs2_read_inode_block(), so any
5799 * corruption is a code bug */
5806 "Truncate record count on #%llu invalid "
5812 /* Caller should have known to flush before calling us. */
5818 }
5821 OCFS2_JOURNAL_ACCESS_WRITE);
5825 }
5831 /*
5832 * Move index back to the record we are coalescing with.
5833 * ocfs2_truncate_log_can_coalesce() guarantees nonzero
5834 */
5835 index--;
5841 num_clusters);
5845 }
5851 bail:
5853 }
5859 {
5863 u64 start_blk;
5874 /* Caller has given us at least enough credits to
5875 * update the truncate log dinode */
5877 OCFS2_JOURNAL_ACCESS_WRITE);
5881 }
5887 /* TODO: Perhaps we can calculate the bulk of the
5888 * credits up front rather than extending like
5889 * this. */
5891 OCFS2_TRUNCATE_LOG_FLUSH_ONE_REC);
5895 }
5902 /* if start_blk is not set, we ignore the record as
5903 * invalid. */
5911 num_clusters);
5915 }
5916 }
5917 i--;
5918 }
5922 bail:
5924 }
5926 /* Expects you to already be holding tl_inode->i_mutex */
5928 {
5943 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5944 * by the underlying call to ocfs2_read_inode_block(), so any
5945 * corruption is a code bug */
5952 num_to_flush);
5956 }
5959 GLOBAL_BITMAP_SYSTEM_INODE,
5960 OCFS2_INVALID_SLOT);
5965 }
5973 }
5980 }
5983 data_alloc_bh);
5989 out_unlock:
5993 out_mutex:
5997 out:
5999 }
6002 {
6011 }
6014 {
6023 else
6025 }
6027 #define OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL (2 * HZ)
6030 {
6032 /* We want to push off log flushes while truncates are
6033 * still running. */
6038 OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL);
6039 }
6040 }
6046 {
6052 TRUNCATE_LOG_SYSTEM_INODE,
6053 slot_num);
6058 }
6065 }
6069 bail:
6071 }
6073 /* called during the 1st stage of node recovery. we stamp a clean
6074 * truncate log and pass back a copy for processing later. if the
6075 * truncate log does not require processing, a *tl_copy is set to
6076 * NULL. */
6080 {
6095 }
6099 /* tl_bh is loaded from ocfs2_get_truncate_log_info(). It's
6100 * validated by the underlying call to ocfs2_read_inode_block(),
6101 * so any corruption is a code bug */
6113 }
6115 /* Assuming the write-out below goes well, this copy
6116 * will be passed back to recovery for processing. */
6119 /* All we need to do to clear the truncate log is set
6120 * tl_used. */
6128 }
6129 }
6131 bail:
6140 }
6143 }
6147 {
6151 u64 start_blk;
6159 }
6165 num_recs);
6174 }
6175 }
6182 }
6194 }
6195 }
6197 bail_up:
6201 }
6204 {
6218 }
6219 }
6222 {
6234 /* ocfs2_truncate_log_shutdown keys on the existence of
6235 * osb->osb_tl_inode so we don't set any of the osb variables
6236 * until we're sure all is well. */
6238 ocfs2_truncate_log_worker);
6243 }
6245 /*
6246 * Delayed de-allocation of suballocator blocks.
6247 *
6248 * Some sets of block de-allocations might involve multiple suballocator inodes.
6249 *
6250 * The locking for this can get extremely complicated, especially when
6251 * the suballocator inodes to delete from aren't known until deep
6252 * within an unrelated codepath.
6253 *
6254 * ocfs2_extent_block structures are a good example of this - an inode
6255 * btree could have been grown by any number of nodes each allocating
6256 * out of their own suballoc inode.
6257 *
6258 * These structures allow the delay of block de-allocation until a
6259 * later time, when locking of multiple cluster inodes won't cause
6260 * deadlock.
6261 */
6263 /*
6264 * Describe a single bit freed from a suballocator. For the block
6265 * suballocators, it represents one block. For the global cluster
6266 * allocator, it represents some clusters and free_bit indicates
6267 * clusters number.
6268 */
6271 u64 free_bg;
6272 u64 free_blk;
6274 };
6281 };
6287 {
6289 u64 bg_blkno;
6300 }
6308 }
6315 }
6320 else
6331 }
6337 }
6342 }
6344 out_journal:
6347 out_unlock:
6350 out_mutex:
6353 out:
6355 /* Premature exit may have left some dangling items. */
6359 }
6362 }
6366 {
6375 }
6385 }
6389 {
6403 }
6404 }
6411 }
6424 }
6425 }
6430 /* Premature exit may have left some dangling items. */
6434 }
6437 }
6441 {
6462 }
6466 }
6477 }
6480 }
6486 {
6494 }
6504 }
6506 }
6511 {
6521 }
6528 }
6542 out:
6544 }
6548 {
6554 }
6557 {
6561 }
6566 {
6576 /*
6577 * Need to set the buffers we zero'd into uptodate
6578 * here if they aren't - ocfs2_map_page_blocks()
6579 * might've skipped some
6580 */
6583 ocfs2_zero_func);
6590 }
6596 }
6601 {
6627 }
6628 out:
6631 }
6635 {
6639 loff_t last_page_bytes;
6652 }
6654 numpages++;
6655 index++;
6658 out:
6663 }
6668 }
6672 {
6679 }
6681 /*
6682 * Zero the area past i_size but still within an allocated
6683 * cluster. This avoids exposing nonzero data on subsequent file
6684 * extends.
6685 *
6686 * We need to call this before i_size is updated on the inode because
6687 * otherwise block_write_full_page() will skip writeout of pages past
6688 * i_size. The new_i_size parameter is passed for this reason.
6689 */
6692 {
6695 u64 phys;
6699 /*
6700 * File systems which don't support sparse files zero on every
6701 * extend.
6702 */
6712 }
6723 }
6725 /*
6726 * Tail is a hole, or is marked unwritten. In either case, we
6727 * can count on read and write to return/push zero's.
6728 */
6737 }
6742 /*
6743 * Initiate writeout of the pages we zero'd here. We don't
6744 * wait on them - the truncate_inode_pages() call later will
6745 * do that for us.
6746 */
6752 out:
6757 }
6761 {
6768 xattrsize);
6769 else
6772 }
6776 {
6782 }
6785 {
6794 /*
6795 * We clear the entire i_data structure here so that all
6796 * fields can be properly initialized.
6797 */
6802 }
6806 {
6828 }
6834 }
6835 }
6843 }
6846 OCFS2_JOURNAL_ACCESS_WRITE);
6850 }
6855 u64 phys;
6870 }
6872 /*
6873 * Save two copies, one for insert, and one that can
6874 * be changed by ocfs2_map_and_dirty_page() below.
6875 */
6878 /*
6879 * Non sparse file systems zero on extend, so no need
6880 * to do that now.
6881 */
6890 }
6892 /*
6893 * This should populate the 1st page for us and mark
6894 * it up to date.
6895 */
6900 }
6909 }
6921 /*
6922 * An error at this point should be extremely rare. If
6923 * this proves to be false, we could always re-build
6924 * the in-inode data from our pages.
6925 */
6931 }
6934 }
6936 out_commit:
6943 out_unlock:
6947 out:
6951 }
6954 }
6956 /*
6957 * It is expected, that by the time you call this function,
6958 * inode->i_size and fe->i_size have been adjusted.
6959 *
6960 * WARNING: This will kfree the truncate context
6961 */
6965 {
6985 ocfs2_journal_access_di);
6990 }
6994 start:
6995 /*
6996 * Check that we still have allocation to delete.
6997 */
7001 }
7003 /*
7004 * Truncate always works against the rightmost tree branch.
7005 */
7010 }
7014 new_highest_cpos,
7018 /*
7019 * By now, el will point to the extent list on the bottom most
7020 * portion of this tree. Only the tail record is considered in
7021 * each pass.
7022 *
7023 * We handle the following cases, in order:
7024 * - empty extent: delete the remaining branch
7025 * - remove the entire record
7026 * - remove a partial record
7027 * - no record needs to be removed (truncate has completed)
7028 */
7037 }
7045 /*
7046 * Lower levels depend on this never happening, but it's best
7047 * to check it up here before changing the tree.
7048 */
7055 }
7060 /*
7061 * Truncate entire record.
7062 */
7067 /*
7068 * Partial truncate. it also should be
7069 * the last truncate we're doing.
7070 */
7077 /*
7078 * Truncate completed, leave happily.
7079 */
7082 }
7088 refcount_loc);
7092 }
7096 /*
7097 * The check above will catch the case where we've truncated
7098 * away all allocation.
7099 */
7102 bail:
7111 }
7113 /*
7114 * 'start' is inclusive, 'end' is not.
7115 */
7118 {
7135 "Inline data flags for inode %llu don't agree! "
7143 }
7150 }
7153 OCFS2_JOURNAL_ACCESS_WRITE);
7157 }
7162 /*
7163 * No need to worry about the data page here - it's been
7164 * truncated already and inline data doesn't need it for
7165 * pushing zero's to disk, so we'll let readpage pick it up
7166 * later.
7167 */
7171 }
7181 out_commit:
7184 out:
7186 }