| blob | 592fae5007d1245baade87453ce731121aa6efe5 |
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 }
3213 /*
3214 * XXX: The caller can not trust "path" any more after
3215 * this as it will have been deleted. What do we do?
3216 *
3217 * In theory the rotate-for-merge code will never get
3218 * here because it'll always ask for a rotate in a
3219 * nonempty list.
3220 */
3223 dealloc);
3227 }
3229 /*
3230 * Now we can loop, remembering the path we get from -EAGAIN
3231 * and restarting from there.
3232 */
3233 try_rotate:
3239 }
3251 }
3258 }
3260 out:
3264 }
3268 {
3273 /*
3274 * We consumed all of the merged-from record. An empty
3275 * extent cannot exist anywhere but the 1st array
3276 * position, so move things over if the merged-from
3277 * record doesn't occupy that position.
3278 *
3279 * This creates a new empty extent so the caller
3280 * should be smart enough to have removed any existing
3281 * ones.
3282 */
3287 }
3289 /*
3290 * Always memset - the caller doesn't check whether it
3291 * created an empty extent, so there could be junk in
3292 * the other fields.
3293 */
3295 }
3296 }
3301 {
3303 u32 right_cpos;
3309 /* This function shouldn't be called for non-trees. */
3320 }
3322 /* This function shouldn't be called for the rightmost leaf. */
3330 }
3336 }
3339 out:
3343 }
3345 /*
3346 * Remove split_rec clusters from the record at index and merge them
3347 * onto the beginning of the record "next" to it.
3348 * For index < l_count - 1, the next means the extent rec at index + 1.
3349 * For index == l_count - 1, the "next" means the 1st extent rec of the
3350 * next extent block.
3351 */
3357 {
3374 /* we meet with a cross extent block merge. */
3379 }
3388 }
3395 right_path);
3399 right_path);
3403 }
3409 subtree_index);
3413 }
3422 }
3429 }
3430 }
3435 }
3442 }
3449 split_clusters));
3458 subtree_index);
3459 }
3460 out:
3464 }
3469 {
3471 u32 left_cpos;
3476 /* This function shouldn't be called for non-trees. */
3484 }
3486 /* This function shouldn't be called for the leftmost leaf. */
3494 }
3500 }
3503 out:
3507 }
3509 /*
3510 * Remove split_rec clusters from the record at index and merge them
3511 * onto the tail of the record "before" it.
3512 * For index > 0, the "before" means the extent rec at index - 1.
3513 *
3514 * For index == 0, the "before" means the last record of the previous
3515 * extent block. And there is also a situation that we may need to
3516 * remove the rightmost leaf extent block in the right_path and change
3517 * the right path to indicate the new rightmost path.
3518 */
3525 {
3540 /* we meet with a cross extent block merge. */
3545 }
3558 right_path);
3562 left_path);
3566 }
3572 subtree_index);
3576 }
3585 }
3592 }
3593 }
3598 }
3605 }
3608 /*
3609 * The easy case - we can just plop the record right in.
3610 */
3620 split_clusters));
3629 /*
3630 * In the situation that the right_rec is empty and the extent
3631 * block is empty also, ocfs2_complete_edge_insert can't handle
3632 * it and we need to delete the right extent block.
3633 */
3638 right_path,
3639 dealloc);
3643 }
3645 /* Now the rightmost extent block has been deleted.
3646 * So we use the new rightmost path.
3647 */
3653 }
3654 out:
3658 }
3667 {
3675 /*
3676 * The merge code will need to create an empty
3677 * extent to take the place of the newly
3678 * emptied slot. Remove any pre-existing empty
3679 * extents - having more than one in a leaf is
3680 * illegal.
3681 */
3686 }
3687 split_index--;
3689 }
3692 /*
3693 * Left-right contig implies this.
3694 */
3697 /*
3698 * Since the leftright insert always covers the entire
3699 * extent, this call will delete the insert record
3700 * entirely, resulting in an empty extent record added to
3701 * the extent block.
3702 *
3703 * Since the adding of an empty extent shifts
3704 * everything back to the right, there's no need to
3705 * update split_index here.
3706 *
3707 * When the split_index is zero, we need to merge it to the
3708 * prevoius extent block. It is more efficient and easier
3709 * if we do merge_right first and merge_left later.
3710 */
3712 split_index);
3716 }
3718 /*
3719 * We can only get this from logic error above.
3720 */
3723 /* The merge left us with an empty extent, remove it. */
3728 }
3732 /*
3733 * Note that we don't pass split_rec here on purpose -
3734 * we've merged it into the rec already.
3735 */
3742 }
3745 /*
3746 * Error from this last rotate is not critical, so
3747 * print but don't bubble it up.
3748 */
3753 /*
3754 * Merge a record to the left or right.
3755 *
3756 * 'contig_type' is relative to the existing record,
3757 * so for example, if we're "right contig", it's to
3758 * the record on the left (hence the left merge).
3759 */
3763 split_index);
3767 }
3771 split_index);
3775 }
3776 }
3779 /*
3780 * The merge may have left an empty extent in
3781 * our leaf. Try to rotate it away.
3782 */
3784 dealloc);
3788 }
3789 }
3791 out:
3793 }
3799 {
3800 u64 len_blocks;
3806 /*
3807 * Region is on the left edge of the existing
3808 * record.
3809 */
3816 /*
3817 * Region is on the right edge of the existing
3818 * record.
3819 */
3822 }
3823 }
3825 /*
3826 * Do the final bits of extent record insertion at the target leaf
3827 * list. If this leaf is part of an allocation tree, it is assumed
3828 * that the tree above has been prepared.
3829 */
3834 {
3847 insert_rec);
3849 }
3851 /*
3852 * Contiguous insert - either left or right.
3853 */
3859 }
3863 }
3865 /*
3866 * Handle insert into an empty leaf.
3867 */
3874 }
3876 /*
3877 * Appending insert.
3878 */
3888 "owner %llu, depth %u, count %u, next free %u, "
3889 "rec.cpos %u, rec.clusters %u, "
3899 i++;
3903 }
3905 rotate:
3906 /*
3907 * Ok, we have to rotate.
3908 *
3909 * At this point, it is safe to assume that inserting into an
3910 * empty leaf and appending to a leaf have both been handled
3911 * above.
3912 *
3913 * This leaf needs to have space, either by the empty 1st
3914 * extent record, or by virtue of an l_next_rec < l_count.
3915 */
3917 }
3923 {
3929 /*
3930 * Update everything except the leaf block.
3931 */
3943 }
3954 }
3955 }
3962 {
3969 /*
3970 * This shouldn't happen for non-trees. The extent rec cluster
3971 * count manipulation below only works for interior nodes.
3972 */
3975 /*
3976 * If our appending insert is at the leftmost edge of a leaf,
3977 * then we might need to update the rightmost records of the
3978 * neighboring path.
3979 */
3984 u32 left_cpos;
3991 }
3995 left_cpos);
3997 /*
3998 * No need to worry if the append is already in the
3999 * leftmost leaf.
4000 */
4007 }
4010 left_cpos);
4014 }
4016 /*
4017 * ocfs2_insert_path() will pass the left_path to the
4018 * journal for us.
4019 */
4020 }
4021 }
4027 }
4033 out:
4038 }
4045 {
4062 /*
4063 * This typically means that the record
4064 * started in the left path but moved to the
4065 * right as a result of rotation. We either
4066 * move the existing record to the left, or we
4067 * do the later insert there.
4068 *
4069 * In this case, the left path should always
4070 * exist as the rotate code will have passed
4071 * it back for a post-insert update.
4072 */
4075 /*
4076 * It's a left split. Since we know
4077 * that the rotate code gave us an
4078 * empty extent in the left path, we
4079 * can just do the insert there.
4080 */
4083 /*
4084 * Right split - we have to move the
4085 * existing record over to the left
4086 * leaf. The insert will be into the
4087 * newly created empty extent in the
4088 * right leaf.
4089 */
4097 }
4098 }
4102 /*
4103 * Left path is easy - we can just allow the insert to
4104 * happen.
4105 */
4110 }
4116 }
4118 /*
4119 * This function only does inserts on an allocation b-tree. For tree
4120 * depth = 0, ocfs2_insert_at_leaf() is called directly.
4121 *
4122 * right_path is the path we want to do the actual insert
4123 * in. left_path should only be passed in if we need to update that
4124 * portion of the tree after an edge insert.
4125 */
4132 {
4137 /*
4138 * There's a chance that left_path got passed back to
4139 * us without being accounted for in the
4140 * journal. Extend our transaction here to be sure we
4141 * can change those blocks.
4142 */
4147 }
4153 }
4154 }
4156 /*
4157 * Pass both paths to the journal. The majority of inserts
4158 * will be touching all components anyway.
4159 */
4164 }
4167 /*
4168 * We could call ocfs2_insert_at_leaf() for some types
4169 * of splits, but it's easier to just let one separate
4170 * function sort it all out.
4171 */
4175 /*
4176 * Split might have modified either leaf and we don't
4177 * have a guarantee that the later edge insert will
4178 * dirty this for us.
4179 */
4185 insert);
4190 /*
4191 * The rotate code has indicated that we need to fix
4192 * up portions of the tree after the insert.
4193 *
4194 * XXX: Should we extend the transaction here?
4195 */
4197 right_path);
4199 subtree_index);
4200 }
4203 out:
4205 }
4211 {
4213 u32 cpos;
4221 OCFS2_JOURNAL_ACCESS_WRITE);
4225 }
4230 }
4237 }
4239 /*
4240 * Determine the path to start with. Rotations need the
4241 * rightmost path, everything else can go directly to the
4242 * target leaf.
4243 */
4249 }
4255 }
4257 /*
4258 * Rotations and appends need special treatment - they modify
4259 * parts of the tree's above them.
4260 *
4261 * Both might pass back a path immediate to the left of the
4262 * one being inserted to. This will be cause
4263 * ocfs2_insert_path() to modify the rightmost records of
4264 * left_path to account for an edge insert.
4265 *
4266 * XXX: When modifying this code, keep in mind that an insert
4267 * can wind up skipping both of these two special cases...
4268 */
4276 }
4278 /*
4279 * ocfs2_rotate_tree_right() might have extended the
4280 * transaction without re-journaling our tree root.
4281 */
4283 OCFS2_JOURNAL_ACCESS_WRITE);
4287 }
4295 }
4296 }
4303 }
4305 out_update_clusters:
4312 out:
4317 }
4319 static enum ocfs2_contig_type
4324 {
4348 left_cpos);
4359 "Extent block #%llu has an "
4360 "invalid l_next_free_rec of "
4361 "%d. It should have "
4368 }
4371 }
4372 }
4374 /*
4375 * We're careful to check for an empty extent record here -
4376 * the merge code will know what to do if it sees one.
4377 */
4384 }
4385 }
4414 "Extent block #%llu has an "
4420 }
4422 }
4423 }
4434 }
4436 out:
4443 }
4449 {
4457 insert_rec);
4461 }
4462 }
4471 /*
4472 * Caller might want us to limit the size of extents, don't
4473 * calculate contiguousness if we might exceed that limit.
4474 */
4478 }
4479 }
4481 /*
4482 * This should only be called against the righmost leaf extent list.
4483 *
4484 * ocfs2_figure_appending_type() will figure out whether we'll have to
4485 * insert at the tail of the rightmost leaf.
4486 *
4487 * This should also work against the root extent list for tree's with 0
4488 * depth. If we consider the root extent list to be the rightmost leaf node
4489 * then the logic here makes sense.
4490 */
4494 {
4507 /* Were all records empty? */
4510 }
4521 set_tail_append:
4523 }
4525 /*
4526 * Helper function called at the begining of an insert.
4527 *
4528 * This computes a few things that are commonly used in the process of
4529 * inserting into the btree:
4530 * - Whether the new extent is contiguous with an existing one.
4531 * - The current tree depth.
4532 * - Whether the insert is an appending one.
4533 * - The total # of free records in the tree.
4534 *
4535 * All of the information is stored on the ocfs2_insert_type
4536 * structure.
4537 */
4543 {
4556 /*
4557 * If we have tree depth, we read in the
4558 * rightmost extent block ahead of time as
4559 * ocfs2_figure_insert_type() and ocfs2_add_branch()
4560 * may want it later.
4561 */
4568 }
4571 }
4573 /*
4574 * Unless we have a contiguous insert, we'll need to know if
4575 * there is room left in our allocation tree for another
4576 * extent record.
4577 *
4578 * XXX: This test is simplistic, we can search for empty
4579 * extent records too.
4580 */
4588 }
4595 }
4597 /*
4598 * In the case that we're inserting past what the tree
4599 * currently accounts for, ocfs2_find_path() will return for
4600 * us the rightmost tree path. This is accounted for below in
4601 * the appending code.
4602 */
4607 }
4611 /*
4612 * Now that we have the path, there's two things we want to determine:
4613 * 1) Contiguousness (also set contig_index if this is so)
4614 *
4615 * 2) Are we doing an append? We can trivially break this up
4616 * into two types of appends: simple record append, or a
4617 * rotate inside the tail leaf.
4618 */
4621 /*
4622 * The insert code isn't quite ready to deal with all cases of
4623 * left contiguousness. Specifically, if it's an insert into
4624 * the 1st record in a leaf, it will require the adjustment of
4625 * cluster count on the last record of the path directly to it's
4626 * left. For now, just catch that case and fool the layers
4627 * above us. This works just fine for tree_depth == 0, which
4628 * is why we allow that above.
4629 */
4634 /*
4635 * Ok, so we can simply compare against last_eb to figure out
4636 * whether the path doesn't exist. This will only happen in
4637 * the case that we're doing a tail append, so maybe we can
4638 * take advantage of that information somehow.
4639 */
4642 /*
4643 * Ok, ocfs2_find_path() returned us the rightmost
4644 * tree path. This might be an appending insert. There are
4645 * two cases:
4646 * 1) We're doing a true append at the tail:
4647 * -This might even be off the end of the leaf
4648 * 2) We're "appending" by rotating in the tail
4649 */
4651 }
4653 out:
4658 else
4661 }
4663 /*
4664 * Insert an extent into a btree.
4665 *
4666 * The caller needs to update the owning btree's cluster count.
4667 */
4670 u32 cpos,
4671 u64 start_blk,
4672 u32 new_clusters,
4673 u8 flags,
4675 {
4695 }
4702 }
4705 "Insert.contig_index: %d, Insert.free_records: %d, "
4713 meta_ac);
4717 }
4718 }
4720 /* Finally, we can add clusters. This might rotate the tree for us. */
4724 else
4727 bail:
4732 }
4734 /*
4735 * Allcate and add clusters into the extent b-tree.
4736 * The new clusters(clusters_to_add) will be inserted at logical_offset.
4737 * The extent b-tree's root is specified by et, and
4738 * it is not limited to the file storage. Any extent tree can use this
4739 * function if it implements the proper ocfs2_extent_tree.
4740 */
4744 u32 clusters_to_add,
4749 {
4754 u64 block;
4769 }
4771 /* there are two cases which could cause us to EAGAIN in the
4772 * we-need-more-metadata case:
4773 * 1) we haven't reserved *any*
4774 * 2) we are so fragmented, we've needed to add metadata too
4775 * many times. */
4788 }
4796 }
4800 /* reserve our write early -- insert_extent may update the tree root */
4802 OCFS2_JOURNAL_ACCESS_WRITE);
4806 }
4817 }
4826 clusters_to_add);
4829 }
4831 leave:
4836 }
4840 u32 cpos,
4842 {
4856 }
4865 {
4875 leftright:
4876 /*
4877 * Store a copy of the record on the stack - it might move
4878 * around as the tree is manipulated below.
4879 */
4889 }
4898 }
4899 }
4916 /*
4917 * Left/right split. We fake this as a right split
4918 * first and then make a second pass as a left split.
4919 */
4929 }
4935 }
4938 u32 cpos;
4941 do_leftright++;
4951 }
4956 }
4957 out:
4960 }
4968 {
4976 }
4981 out:
4983 }
4985 /*
4986 * Split part or all of the extent record at split_index in the leaf
4987 * pointed to by path. Merge with the contiguous extent record if needed.
4988 *
4989 * Care is taken to handle contiguousness so as to not grow the tree.
4990 *
4991 * meta_ac is not strictly necessary - we only truly need it if growth
4992 * of the tree is required. All other cases will degrade into a less
4993 * optimal tree layout.
4994 *
4995 * last_eb_bh should be the rightmost leaf block for any extent
4996 * btree. Since a split may grow the tree or a merge might shrink it,
4997 * the caller cannot trust the contents of that buffer after this call.
4998 *
4999 * This code is optimized for readability - several passes might be
5000 * made over certain portions of the tree. All of those blocks will
5001 * have been brought into cache (and pinned via the journal), so the
5002 * extra overhead is not expressed in terms of disk reads.
5003 */
5011 {
5025 }
5028 split_index,
5029 split_rec);
5031 /*
5032 * The core merge / split code wants to know how much room is
5033 * left in this allocation tree, so we pass the
5034 * rightmost extent list.
5035 */
5045 }
5055 else
5068 else
5080 }
5082 out:
5085 }
5087 /*
5088 * Change the flags of the already-existing extent at cpos for len clusters.
5089 *
5090 * new_flags: the flags we want to set.
5091 * clear_flags: the flags we want to clear.
5092 * phys: the new physical offset we want this new extent starts from.
5093 *
5094 * If the existing extent is larger than the request, initiate a
5095 * split. An attempt will be made at merging with adjacent extents.
5096 *
5097 * The caller is responsible for passing down meta_ac if we'll need it.
5098 */
5105 {
5119 }
5125 }
5131 "Owner %llu has an extent at cpos %u which can no "
5137 }
5145 new_flags);
5147 }
5153 clear_flags);
5155 }
5169 dealloc);
5173 out:
5177 }
5179 /*
5180 * Mark the already-existing extent at cpos as written for len clusters.
5181 * This removes the unwritten extent flag.
5182 *
5183 * If the existing extent is larger than the request, initiate a
5184 * split. An attempt will be made at merging with adjacent extents.
5185 *
5186 * The caller is responsible for passing down meta_ac if we'll need it.
5187 */
5193 {
5201 "that are being written to, but the feature bit "
5206 }
5208 /*
5209 * XXX: This should be fixed up so that we just re-insert the
5210 * next extent records.
5211 */
5220 out:
5222 }
5228 {
5237 /*
5238 * Setup the record to split before we grow the tree.
5239 */
5253 }
5266 }
5271 meta_ac);
5275 }
5276 }
5288 out:
5291 }
5298 {
5313 }
5315 index--;
5316 }
5320 /*
5321 * Check whether this is the rightmost tree record. If
5322 * we remove all of this record or part of its right
5323 * edge then an update of the record lengths above it
5324 * will be required.
5325 */
5329 }
5334 /*
5335 * Changing the leftmost offset (via partial or whole
5336 * record truncate) of an interior (or rightmost) path
5337 * means we have to update the subtree that is formed
5338 * by this leaf and the one to it's left.
5339 *
5340 * There are two cases we can skip:
5341 * 1) Path is the leftmost one in our btree.
5342 * 2) The leaf is rightmost and will be empty after
5343 * we remove the extent record - the rotate code
5344 * knows how to update the newly formed edge.
5345 */
5351 }
5359 }
5362 left_cpos);
5366 }
5367 }
5368 }
5372 path);
5376 }
5382 }
5388 }
5402 /*
5403 * We skip the edge update if this path will
5404 * be deleted by the rotate code.
5405 */
5408 rec);
5409 }
5411 /* Remove leftmost portion of the record. */
5416 /* Remove rightmost portion of the record */
5421 /* Caller should have trapped this. */
5428 }
5435 subtree_index);
5436 }
5444 }
5446 out:
5449 }
5456 {
5463 /*
5464 * XXX: Why are we truncating to 0 instead of wherever this
5465 * affects us?
5466 */
5474 }
5480 }
5486 "Owner %llu has an extent at cpos %u which can no "
5489 cpos);
5492 }
5494 /*
5495 * We have 3 cases of extent removal:
5496 * 1) Range covers the entire extent rec
5497 * 2) Range begins or ends on one edge of the extent rec
5498 * 3) Range is in the middle of the extent rec (no shared edges)
5499 *
5500 * For case 1 we remove the extent rec and left rotate to
5501 * fill the hole.
5502 *
5503 * For case 2 we just shrink the existing extent rec, with a
5504 * tree update if the shrinking edge is also the edge of an
5505 * extent block.
5506 *
5507 * For case 3 we do a right split to turn the extent rec into
5508 * something case 2 can handle.
5509 */
5528 }
5535 }
5537 /*
5538 * The split could have manipulated the tree enough to
5539 * move the record location, so we have to look for it again.
5540 */
5547 }
5555 cpos);
5558 }
5560 /*
5561 * Double check our values here. If anything is fishy,
5562 * it's easier to catch it at the top level.
5563 */
5569 "Owner %llu: error after split at cpos %u"
5576 }
5583 }
5584 }
5586 out:
5589 }
5591 /*
5592 * ocfs2_reserve_blocks_for_rec_trunc() would look basically the
5593 * same as ocfs2_lock_alloctors(), except for it accepts a blocks
5594 * number to reserve some extra blocks, and it only handles meta
5595 * data allocations.
5596 *
5597 * Currently, only ocfs2_remove_btree_range() uses it for truncating
5598 * and punching holes.
5599 */
5602 u32 extents_to_split,
5605 {
5617 }
5629 }
5630 }
5632 out:
5637 }
5638 }
5641 }
5647 u64 refcount_loc)
5648 {
5659 OCFS2_HAS_REFCOUNT_FL));
5666 }
5669 refcount_loc,
5670 phys_blkno,
5671 len,
5677 }
5678 }
5681 extra_blocks);
5685 }
5694 }
5695 }
5703 }
5706 OCFS2_JOURNAL_ACCESS_WRITE);
5710 }
5719 }
5729 phys_blkno),
5732 else
5738 }
5740 out_commit:
5742 out:
5752 }
5755 {
5764 "slot %d, invalid truncate log parameters: used = "
5768 }
5772 {
5776 /* No records, nothing to coalesce */
5785 }
5789 u64 start_blk,
5791 {
5808 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5809 * by the underlying call to ocfs2_read_inode_block(), so any
5810 * corruption is a code bug */
5817 "Truncate record count on #%llu invalid "
5823 /* Caller should have known to flush before calling us. */
5829 }
5832 OCFS2_JOURNAL_ACCESS_WRITE);
5836 }
5843 /*
5844 * Move index back to the record we are coalescing with.
5845 * ocfs2_truncate_log_can_coalesce() guarantees nonzero
5846 */
5847 index--;
5852 num_clusters);
5856 }
5861 bail:
5864 }
5870 {
5874 u64 start_blk;
5887 /* Caller has given us at least enough credits to
5888 * update the truncate log dinode */
5890 OCFS2_JOURNAL_ACCESS_WRITE);
5894 }
5900 /* TODO: Perhaps we can calculate the bulk of the
5901 * credits up front rather than extending like
5902 * this. */
5904 OCFS2_TRUNCATE_LOG_FLUSH_ONE_REC);
5908 }
5915 /* if start_blk is not set, we ignore the record as
5916 * invalid. */
5923 num_clusters);
5927 }
5928 }
5929 i--;
5930 }
5932 bail:
5935 }
5937 /* Expects you to already be holding tl_inode->i_mutex */
5939 {
5956 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5957 * by the underlying call to ocfs2_read_inode_block(), so any
5958 * corruption is a code bug */
5968 }
5971 GLOBAL_BITMAP_SYSTEM_INODE,
5972 OCFS2_INVALID_SLOT);
5977 }
5985 }
5992 }
5995 data_alloc_bh);
6001 out_unlock:
6005 out_mutex:
6009 out:
6012 }
6015 {
6024 }
6027 {
6038 else
6042 }
6044 #define OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL (2 * HZ)
6047 {
6049 /* We want to push off log flushes while truncates are
6050 * still running. */
6055 OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL);
6056 }
6057 }
6063 {
6069 TRUNCATE_LOG_SYSTEM_INODE,
6070 slot_num);
6075 }
6082 }
6086 bail:
6089 }
6091 /* called during the 1st stage of node recovery. we stamp a clean
6092 * truncate log and pass back a copy for processing later. if the
6093 * truncate log does not require processing, a *tl_copy is set to
6094 * NULL. */
6098 {
6113 }
6117 /* tl_bh is loaded from ocfs2_get_truncate_log_info(). It's
6118 * validated by the underlying call to ocfs2_read_inode_block(),
6119 * so any corruption is a code bug */
6132 }
6134 /* Assuming the write-out below goes well, this copy
6135 * will be passed back to recovery for processing. */
6138 /* All we need to do to clear the truncate log is set
6139 * tl_used. */
6147 }
6148 }
6150 bail:
6158 }
6162 }
6166 {
6170 u64 start_blk;
6180 }
6194 }
6195 }
6202 }
6214 }
6215 }
6217 bail_up:
6222 }
6225 {
6241 }
6244 }
6247 {
6261 /* ocfs2_truncate_log_shutdown keys on the existence of
6262 * osb->osb_tl_inode so we don't set any of the osb variables
6263 * until we're sure all is well. */
6265 ocfs2_truncate_log_worker);
6271 }
6273 /*
6274 * Delayed de-allocation of suballocator blocks.
6275 *
6276 * Some sets of block de-allocations might involve multiple suballocator inodes.
6277 *
6278 * The locking for this can get extremely complicated, especially when
6279 * the suballocator inodes to delete from aren't known until deep
6280 * within an unrelated codepath.
6281 *
6282 * ocfs2_extent_block structures are a good example of this - an inode
6283 * btree could have been grown by any number of nodes each allocating
6284 * out of their own suballoc inode.
6285 *
6286 * These structures allow the delay of block de-allocation until a
6287 * later time, when locking of multiple cluster inodes won't cause
6288 * deadlock.
6289 */
6291 /*
6292 * Describe a single bit freed from a suballocator. For the block
6293 * suballocators, it represents one block. For the global cluster
6294 * allocator, it represents some clusters and free_bit indicates
6295 * clusters number.
6296 */
6299 u64 free_bg;
6300 u64 free_blk;
6302 };
6309 };
6315 {
6317 u64 bg_blkno;
6328 }
6336 }
6343 }
6348 else
6359 }
6365 }
6370 }
6372 out_journal:
6375 out_unlock:
6378 out_mutex:
6381 out:
6383 /* Premature exit may have left some dangling items. */
6387 }
6390 }
6394 {
6403 }
6414 }
6418 {
6432 }
6433 }
6440 }
6453 }
6454 }
6459 /* Premature exit may have left some dangling items. */
6463 }
6466 }
6470 {
6491 }
6495 }
6506 }
6509 }
6515 {
6523 }
6533 }
6535 }
6540 {
6550 }
6557 }
6570 out:
6572 }
6576 {
6582 }
6585 {
6589 }
6594 {
6604 /*
6605 * Need to set the buffers we zero'd into uptodate
6606 * here if they aren't - ocfs2_map_page_blocks()
6607 * might've skipped some
6608 */
6611 ocfs2_zero_func);
6618 }
6624 }
6629 {
6655 }
6656 out:
6659 }
6663 {
6667 loff_t last_page_bytes;
6680 }
6682 numpages++;
6683 index++;
6686 out:
6691 }
6696 }
6700 {
6707 }
6709 /*
6710 * Zero the area past i_size but still within an allocated
6711 * cluster. This avoids exposing nonzero data on subsequent file
6712 * extends.
6713 *
6714 * We need to call this before i_size is updated on the inode because
6715 * otherwise block_write_full_page() will skip writeout of pages past
6716 * i_size. The new_i_size parameter is passed for this reason.
6717 */
6720 {
6723 u64 phys;
6727 /*
6728 * File systems which don't support sparse files zero on every
6729 * extend.
6730 */
6740 }
6751 }
6753 /*
6754 * Tail is a hole, or is marked unwritten. In either case, we
6755 * can count on read and write to return/push zero's.
6756 */
6765 }
6770 /*
6771 * Initiate writeout of the pages we zero'd here. We don't
6772 * wait on them - the truncate_inode_pages() call later will
6773 * do that for us.
6774 */
6780 out:
6785 }
6789 {
6796 xattrsize);
6797 else
6800 }
6804 {
6810 }
6813 {
6822 /*
6823 * We clear the entire i_data structure here so that all
6824 * fields can be properly initialized.
6825 */
6830 }
6834 {
6856 }
6862 }
6863 }
6871 }
6874 OCFS2_JOURNAL_ACCESS_WRITE);
6878 }
6883 u64 phys;
6898 }
6900 /*
6901 * Save two copies, one for insert, and one that can
6902 * be changed by ocfs2_map_and_dirty_page() below.
6903 */
6906 /*
6907 * Non sparse file systems zero on extend, so no need
6908 * to do that now.
6909 */
6918 }
6920 /*
6921 * This should populate the 1st page for us and mark
6922 * it up to date.
6923 */
6928 }
6937 }
6949 /*
6950 * An error at this point should be extremely rare. If
6951 * this proves to be false, we could always re-build
6952 * the in-inode data from our pages.
6953 */
6959 }
6962 }
6964 out_commit:
6971 out_unlock:
6975 out:
6979 }
6982 }
6984 /*
6985 * It is expected, that by the time you call this function,
6986 * inode->i_size and fe->i_size have been adjusted.
6987 *
6988 * WARNING: This will kfree the truncate context
6989 */
6993 {
7015 ocfs2_journal_access_di);
7020 }
7024 start:
7025 /*
7026 * Check that we still have allocation to delete.
7027 */
7031 }
7033 /*
7034 * Truncate always works against the rightmost tree branch.
7035 */
7040 }
7045 /*
7046 * By now, el will point to the extent list on the bottom most
7047 * portion of this tree. Only the tail record is considered in
7048 * each pass.
7049 *
7050 * We handle the following cases, in order:
7051 * - empty extent: delete the remaining branch
7052 * - remove the entire record
7053 * - remove a partial record
7054 * - no record needs to be removed (truncate has completed)
7055 */
7064 }
7072 /*
7073 * Lower levels depend on this never happening, but it's best
7074 * to check it up here before changing the tree.
7075 */
7082 }
7087 /*
7088 * Truncate entire record.
7089 */
7094 /*
7095 * Partial truncate. it also should be
7096 * the last truncate we're doing.
7097 */
7104 /*
7105 * Truncate completed, leave happily.
7106 */
7109 }
7115 refcount_loc);
7119 }
7123 /*
7124 * The check above will catch the case where we've truncated
7125 * away all allocation.
7126 */
7129 bail:
7139 }
7141 /*
7142 * Expects the inode to already be locked.
7143 */
7148 {
7172 }
7182 }
7184 }
7189 bail:
7194 }
7197 }
7199 /*
7200 * 'start' is inclusive, 'end' is not.
7201 */
7204 {
7221 "Inline data flags for inode %llu don't agree! "
7229 }
7236 }
7239 OCFS2_JOURNAL_ACCESS_WRITE);
7243 }
7248 /*
7249 * No need to worry about the data page here - it's been
7250 * truncated already and inline data doesn't need it for
7251 * pushing zero's to disk, so we'll let readpage pick it up
7252 * later.
7253 */
7257 }
7267 out_commit:
7270 out:
7272 }
7275 {
7276 /*
7277 * The caller is responsible for completing deallocation
7278 * before freeing the context.
7279 */
7287 }