| blob | d17bdc718f74b3820f0381ed770e85a86217c5e0 |
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;
1009 u64 first_blkno;
1019 handle,
1020 meta_ac,
1028 }
1036 }
1041 OCFS2_JOURNAL_ACCESS_CREATE);
1045 }
1049 /* Ok, setup the minimal stuff here. */
1058 suballoc_bit_start++;
1059 first_blkno++;
1061 /* We'll also be dirtied by the caller, so
1062 * this isn't absolutely necessary. */
1067 }
1068 }
1071 }
1074 bail:
1079 }
1080 }
1083 }
1085 /*
1086 * Helper function for ocfs2_add_branch() and ocfs2_shift_tree_depth().
1087 *
1088 * Returns the sum of the rightmost extent rec logical offset and
1089 * cluster count.
1090 *
1091 * ocfs2_add_branch() uses this to determine what logical cluster
1092 * value should be populated into the leftmost new branch records.
1093 *
1094 * ocfs2_shift_tree_depth() uses this to determine the # clusters
1095 * value for the new topmost tree record.
1096 */
1098 {
1105 }
1107 /*
1108 * Change range of the branches in the right most path according to the leaf
1109 * extent block's rightmost record.
1110 */
1113 {
1123 }
1129 }
1136 }
1142 }
1149 out:
1152 }
1154 /*
1155 * Add an entire tree branch to our inode. eb_bh is the extent block
1156 * to start at, if we don't want to start the branch at the root
1157 * structure.
1158 *
1159 * last_eb_bh is required as we have to update it's next_leaf pointer
1160 * for the new last extent block.
1161 *
1162 * the new branch will be 'empty' in the sense that every block will
1163 * contain a single record with cluster count == 0.
1164 */
1170 {
1190 /* we never add a branch to a leaf. */
1199 /*
1200 * If there is a gap before the root end and the real end
1201 * of the righmost leaf block, we need to remove the gap
1202 * between new_cpos and root_end first so that the tree
1203 * is consistent after we add a new branch(it will start
1204 * from new_cpos).
1205 */
1213 }
1214 }
1216 /* allocate the number of new eb blocks we need */
1218 GFP_KERNEL);
1223 }
1230 }
1232 /* Note: new_eb_bhs[new_blocks - 1] is the guy which will be
1233 * linked with the rest of the tree.
1234 * conversly, new_eb_bhs[0] is the new bottommost leaf.
1235 *
1236 * when we leave the loop, new_last_eb_blk will point to the
1237 * newest leaf, and next_blkno will point to the topmost extent
1238 * block. */
1243 /* ocfs2_create_new_meta_bhs() should create it right! */
1248 OCFS2_JOURNAL_ACCESS_CREATE);
1252 }
1257 /*
1258 * This actually counts as an empty extent as
1259 * c_clusters == 0
1260 */
1263 /*
1264 * eb_el isn't always an interior node, but even leaf
1265 * nodes want a zero'd flags and reserved field so
1266 * this gets the whole 32 bits regardless of use.
1267 */
1276 }
1279 }
1281 /* This is a bit hairy. We want to update up to three blocks
1282 * here without leaving any of them in an inconsistent state
1283 * in case of error. We don't have to worry about
1284 * journal_dirty erroring as it won't unless we've aborted the
1285 * handle (in which case we would never be here) so reserving
1286 * the write with journal_access is all we need to do. */
1288 OCFS2_JOURNAL_ACCESS_WRITE);
1292 }
1294 OCFS2_JOURNAL_ACCESS_WRITE);
1298 }
1301 OCFS2_JOURNAL_ACCESS_WRITE);
1305 }
1306 }
1308 /* Link the new branch into the rest of the tree (el will
1309 * either be on the root_bh, or the extent block passed in. */
1316 /* fe needs a new last extent block pointer, as does the
1317 * next_leaf on the previously last-extent-block. */
1333 }
1335 /*
1336 * Some callers want to track the rightmost leaf so pass it
1337 * back here.
1338 */
1344 bail:
1349 }
1353 }
1355 /*
1356 * adds another level to the allocation tree.
1357 * returns back the new extent block so you can add a branch to it
1358 * after this call.
1359 */
1364 {
1366 u32 new_clusters;
1379 }
1382 /* ocfs2_create_new_meta_bhs() should create it right! */
1389 OCFS2_JOURNAL_ACCESS_CREATE);
1393 }
1395 /* copy the root extent list data into the new extent block */
1405 }
1408 OCFS2_JOURNAL_ACCESS_WRITE);
1412 }
1416 /* update root_bh now */
1425 /* If this is our 1st tree depth shift, then last_eb_blk
1426 * becomes the allocated extent block */
1434 }
1439 bail:
1444 }
1446 /*
1447 * Should only be called when there is no space left in any of the
1448 * leaf nodes. What we want to do is find the lowest tree depth
1449 * non-leaf extent block with room for new records. There are three
1450 * valid results of this search:
1451 *
1452 * 1) a lowest extent block is found, then we pass it back in
1453 * *lowest_eb_bh and return '0'
1454 *
1455 * 2) the search fails to find anything, but the root_el has room. We
1456 * pass NULL back in *lowest_eb_bh, but still return '0'
1457 *
1458 * 3) the search fails to find anything AND the root_el is full, in
1459 * which case we return > 0
1460 *
1461 * return status < 0 indicates an error.
1462 */
1465 {
1467 u64 blkno;
1482 "Owner %llu has empty "
1487 }
1492 "Owner %llu has extent "
1493 "list where extent # %d has no physical "
1498 }
1507 }
1517 }
1518 }
1520 /* If we didn't find one and the fe doesn't have any room,
1521 * then return '1' */
1527 bail:
1532 }
1534 /*
1535 * Grow a b-tree so that it has more records.
1536 *
1537 * We might shift the tree depth in which case existing paths should
1538 * be considered invalid.
1539 *
1540 * Tree depth after the grow is returned via *final_depth.
1541 *
1542 * *last_eb_bh will be updated by ocfs2_add_branch().
1543 */
1547 {
1560 }
1562 /* We traveled all the way to the bottom of the allocation tree
1563 * and didn't find room for any more extents - we need to add
1564 * another tree level */
1569 /* ocfs2_shift_tree_depth will return us a buffer with
1570 * the new extent block (so we can pass that to
1571 * ocfs2_add_branch). */
1576 }
1577 depth++;
1579 /*
1580 * Special case: we have room now if we shifted from
1581 * tree_depth 0, so no more work needs to be done.
1582 *
1583 * We won't be calling add_branch, so pass
1584 * back *last_eb_bh as the new leaf. At depth
1585 * zero, it should always be null so there's
1586 * no reason to brelse.
1587 */
1592 }
1593 }
1595 /* call ocfs2_add_branch to add the final part of the tree with
1596 * the new data. */
1599 meta_ac);
1603 }
1605 out:
1610 }
1612 /*
1613 * This function will discard the rightmost extent record.
1614 */
1616 {
1622 /* This will cause us to go off the end of our extent list. */
1628 }
1632 {
1642 /* The tree code before us didn't allow enough room in the leaf. */
1645 /*
1646 * The easiest way to approach this is to just remove the
1647 * empty extent and temporarily decrement next_free.
1648 */
1650 /*
1651 * If next_free was 1 (only an empty extent), this
1652 * loop won't execute, which is fine. We still want
1653 * the decrement above to happen.
1654 */
1658 next_free--;
1659 }
1661 /*
1662 * Figure out what the new record index should be.
1663 */
1669 }
1679 /*
1680 * No need to memmove if we're just adding to the tail.
1681 */
1689 num_bytes);
1690 }
1692 /*
1693 * Either we had an empty extent, and need to re-increment or
1694 * there was no empty extent on a non full rightmost leaf node,
1695 * in which case we still need to increment.
1696 */
1697 next_free++;
1699 /*
1700 * Make sure none of the math above just messed up our tree.
1701 */
1706 }
1709 {
1715 num_recs--;
1721 }
1722 }
1724 /*
1725 * Create an empty extent record .
1726 *
1727 * l_next_free_rec may be updated.
1728 *
1729 * If an empty extent already exists do nothing.
1730 */
1732 {
1751 set_and_inc:
1754 }
1756 /*
1757 * For a rotation which involves two leaf nodes, the "root node" is
1758 * the lowest level tree node which contains a path to both leafs. This
1759 * resulting set of information can be used to form a complete "subtree"
1760 *
1761 * This function is passed two full paths from the dinode down to a
1762 * pair of adjacent leaves. It's task is to figure out which path
1763 * index contains the subtree root - this can be the root index itself
1764 * in a worst-case rotation.
1765 *
1766 * The array index of the subtree root is passed back.
1767 */
1771 {
1774 /*
1775 * Check that the caller passed in two paths from the same tree.
1776 */
1780 i++;
1782 /*
1783 * The caller didn't pass two adjacent paths.
1784 */
1796 }
1800 /*
1801 * Traverse a btree path in search of cpos, starting at root_el.
1802 *
1803 * This code can be called with a cpos larger than the tree, in which
1804 * case it will return the rightmost path.
1805 */
1809 {
1811 u32 range;
1812 u64 blkno;
1822 "Owner %llu has empty extent list at "
1829 }
1834 /*
1835 * In the case that cpos is off the allocation
1836 * tree, this should just wind up returning the
1837 * rightmost record.
1838 */
1843 }
1848 "Owner %llu has bad blkno in extent list "
1854 }
1862 }
1870 "Owner %llu has bad count in extent list "
1878 }
1882 }
1884 out:
1885 /*
1886 * Catch any trailing bh that the loop didn't handle.
1887 */
1891 }
1893 /*
1894 * Given an initialized path (that is, it has a valid root extent
1895 * list), this function will traverse the btree in search of the path
1896 * which would contain cpos.
1897 *
1898 * The path traveled is recorded in the path structure.
1899 *
1900 * Note that this will not do any comparisons on leaf node extent
1901 * records, so it will work fine in the case that we just added a tree
1902 * branch.
1903 */
1907 };
1909 {
1915 }
1918 {
1925 }
1928 {
1933 /* We want to retain only the leaf block. */
1937 }
1938 }
1939 /*
1940 * Find the leaf block in the tree which would contain cpos. No
1941 * checking of the actual leaf is done.
1942 *
1943 * Some paths want to call this instead of allocating a path structure
1944 * and calling ocfs2_find_path().
1945 *
1946 * This function doesn't handle non btree extent lists.
1947 */
1951 {
1959 }
1962 out:
1964 }
1966 /*
1967 * Adjust the adjacent records (left_rec, right_rec) involved in a rotation.
1968 *
1969 * Basically, we've moved stuff around at the bottom of the tree and
1970 * we need to fix up the extent records above the changes to reflect
1971 * the new changes.
1972 *
1973 * left_rec: the record on the left.
1974 * left_child_el: is the child list pointed to by left_rec
1975 * right_rec: the record to the right of left_rec
1976 * right_child_el: is the child list pointed to by right_rec
1977 *
1978 * By definition, this only works on interior nodes.
1979 */
1984 {
1987 /*
1988 * Interior nodes never have holes. Their cpos is the cpos of
1989 * the leftmost record in their child list. Their cluster
1990 * count covers the full theoretical range of their child list
1991 * - the range between their cpos and the cpos of the record
1992 * immediately to their right.
1993 */
1999 }
2003 /*
2004 * Calculate the rightmost cluster count boundary before
2005 * moving cpos - we will need to adjust clusters after
2006 * updating e_cpos to keep the same highest cluster count.
2007 */
2016 }
2018 /*
2019 * Adjust the adjacent root node records involved in a
2020 * rotation. left_el_blkno is passed in as a key so that we can easily
2021 * find it's index in the root list.
2022 */
2026 u64 left_el_blkno)
2027 {
2036 }
2038 /*
2039 * The path walking code should have never returned a root and
2040 * two paths which are not adjacent.
2041 */
2046 }
2048 /*
2049 * We've changed a leaf block (in right_path) and need to reflect that
2050 * change back up the subtree.
2051 *
2052 * This happens in multiple places:
2053 * - When we've moved an extent record from the left path leaf to the right
2054 * path leaf to make room for an empty extent in the left path leaf.
2055 * - When our insert into the right path leaf is at the leftmost edge
2056 * and requires an update of the path immediately to it's left. This
2057 * can occur at the end of some types of rotation and appending inserts.
2058 * - When we've adjusted the last extent record in the left path leaf and the
2059 * 1st extent record in the right path leaf during cross extent block merge.
2060 */
2065 {
2071 /*
2072 * Update the counts and position values within all the
2073 * interior nodes to reflect the leaf rotation we just did.
2074 *
2075 * The root node is handled below the loop.
2076 *
2077 * We begin the loop with right_el and left_el pointing to the
2078 * leaf lists and work our way up.
2079 *
2080 * NOTE: within this loop, left_el and right_el always refer
2081 * to the *child* lists.
2082 */
2088 /*
2089 * One nice property of knowing that all of these
2090 * nodes are below the root is that we only deal with
2091 * the leftmost right node record and the rightmost
2092 * left node record.
2093 */
2102 right_el);
2112 /*
2113 * Setup our list pointers now so that the current
2114 * parents become children in the next iteration.
2115 */
2118 }
2120 /*
2121 * At the root node, adjust the two adjacent records which
2122 * begin our path to the leaves.
2123 */
2137 }
2144 {
2157 "Inode %llu has non-full interior leaf node %llu"
2163 }
2165 /*
2166 * This extent block may already have an empty record, so we
2167 * return early if so.
2168 */
2176 subtree_index);
2180 }
2188 }
2195 }
2196 }
2201 /* This is a code error, not a disk corruption. */
2213 }
2215 /* Do the copy now. */
2220 /*
2221 * Clear out the record we just copied and shift everything
2222 * over, leaving an empty extent in the left leaf.
2223 *
2224 * We temporarily subtract from next_free_rec so that the
2225 * shift will lose the tail record (which is now defunct).
2226 */
2236 }
2239 subtree_index);
2241 out:
2243 }
2245 /*
2246 * Given a full path, determine what cpos value would return us a path
2247 * containing the leaf immediately to the left of the current one.
2248 *
2249 * Will return zero if the path passed in is already the leftmost path.
2250 */
2253 {
2255 u64 blkno;
2264 /* Start at the tree node just above the leaf and work our way up. */
2269 /*
2270 * Find the extent record just before the one in our
2271 * path.
2272 */
2277 /*
2278 * We've determined that the
2279 * path specified is already
2280 * the leftmost one - return a
2281 * cpos of zero.
2282 */
2284 }
2285 /*
2286 * The leftmost record points to our
2287 * leaf - we need to travel up the
2288 * tree one level.
2289 */
2291 }
2298 }
2299 }
2301 /*
2302 * If we got here, we never found a valid node where
2303 * the tree indicated one should be.
2304 */
2311 next_node:
2313 i--;
2314 }
2316 out:
2318 }
2320 /*
2321 * Extend the transaction by enough credits to complete the rotation,
2322 * and still leave at least the original number of credits allocated
2323 * to this transaction.
2324 */
2328 {
2340 }
2343 }
2345 /*
2346 * Trap the case where we're inserting into the theoretical range past
2347 * the _actual_ left leaf range. Otherwise, we'll rotate a record
2348 * whose cpos is less than ours into the right leaf.
2349 *
2350 * It's only necessary to look at the rightmost record of the left
2351 * leaf because the logic that calls us should ensure that the
2352 * theoretical ranges in the path components above the leaves are
2353 * correct.
2354 */
2356 u32 insert_cpos)
2357 {
2369 }
2372 {
2382 /* Empty list. */
2386 }
2392 }
2394 /*
2395 * Rotate all the records in a btree right one record, starting at insert_cpos.
2396 *
2397 * The path to the rightmost leaf should be passed in.
2398 *
2399 * The array is assumed to be large enough to hold an entire path (tree depth).
2400 *
2401 * Upon successful return from this function:
2402 *
2403 * - The 'right_path' array will contain a path to the leaf block
2404 * whose range contains e_cpos.
2405 * - That leaf block will have a single empty extent in list index 0.
2406 * - In the case that the rotation requires a post-insert update,
2407 * *ret_left_path will contain a valid path which can be passed to
2408 * ocfs2_insert_path().
2409 */
2413 u32 insert_cpos,
2416 {
2418 u32 cpos;
2429 }
2435 }
2439 /*
2440 * What we want to do here is:
2441 *
2442 * 1) Start with the rightmost path.
2443 *
2444 * 2) Determine a path to the leaf block directly to the left
2445 * of that leaf.
2446 *
2447 * 3) Determine the 'subtree root' - the lowest level tree node
2448 * which contains a path to both leaves.
2449 *
2450 * 4) Rotate the subtree.
2451 *
2452 * 5) Find the next subtree by considering the left path to be
2453 * the new right path.
2454 *
2455 * The check at the top of this while loop also accepts
2456 * insert_cpos == cpos because cpos is only a _theoretical_
2457 * value to get us the left path - insert_cpos might very well
2458 * be filling that hole.
2459 *
2460 * Stop at a cpos of '0' because we either started at the
2461 * leftmost branch (i.e., a tree with one branch and a
2462 * rotation inside of it), or we've gone as far as we can in
2463 * rotating subtrees.
2464 */
2473 }
2477 "Owner %llu: error during insert of %u "
2478 "(left path cpos %u) results in two identical "
2487 insert_cpos)) {
2489 /*
2490 * We've rotated the tree as much as we
2491 * should. The rest is up to
2492 * ocfs2_insert_path() to complete, after the
2493 * record insertion. We indicate this
2494 * situation by returning the left path.
2495 *
2496 * The reason we don't adjust the records here
2497 * before the record insert is that an error
2498 * later might break the rule where a parent
2499 * record e_cpos will reflect the actual
2500 * e_cpos of the 1st nonempty record of the
2501 * child list.
2502 */
2505 }
2510 start,
2519 }
2526 }
2530 insert_cpos)) {
2531 /*
2532 * A rotate moves the rightmost left leaf
2533 * record over to the leftmost right leaf
2534 * slot. If we're doing an extent split
2535 * instead of a real insert, then we have to
2536 * check that the extent to be split wasn't
2537 * just moved over. If it was, then we can
2538 * exit here, passing left_path back -
2539 * ocfs2_split_extent() is smart enough to
2540 * search both leaves.
2541 */
2544 }
2546 /*
2547 * There is no need to re-read the next right path
2548 * as we know that it'll be our current left
2549 * path. Optimize by copying values instead.
2550 */
2557 }
2558 }
2560 out:
2563 out_ret_path:
2565 }
2570 {
2575 u32 range;
2577 /*
2578 * In normal tree rotation process, we will never touch the
2579 * tree branch above subtree_index and ocfs2_extend_rotate_transaction
2580 * doesn't reserve the credits for them either.
2581 *
2582 * But we do have a special case here which will update the rightmost
2583 * records for all the bh in the path.
2584 * So we have to allocate extra credits and access them.
2585 */
2591 }
2597 }
2599 /* Path should always be rightmost. */
2618 }
2619 out:
2621 }
2627 {
2637 /*
2638 * Not all nodes might have had their final count
2639 * decremented by the caller - handle this here.
2640 */
2644 "Inode %llu, attempted to remove extent block "
2653 }
2665 }
2666 }
2674 {
2702 }
2711 {
2729 /*
2730 * It's legal for us to proceed if the right leaf is
2731 * the rightmost one and it has an empty extent. There
2732 * are two cases to handle - whether the leaf will be
2733 * empty after removal or not. If the leaf isn't empty
2734 * then just remove the empty extent up front. The
2735 * next block will handle empty leaves by flagging
2736 * them for unlink.
2737 *
2738 * Non rightmost leaves will throw -EAGAIN and the
2739 * caller can manually move the subtree and retry.
2740 */
2748 OCFS2_JOURNAL_ACCESS_WRITE);
2752 }
2757 }
2761 /*
2762 * We have to update i_last_eb_blk during the meta
2763 * data delete.
2764 */
2766 OCFS2_JOURNAL_ACCESS_WRITE);
2770 }
2773 }
2775 /*
2776 * Getting here with an empty extent in the right path implies
2777 * that it's the rightmost path and will be deleted.
2778 */
2782 subtree_index);
2786 }
2794 }
2801 }
2802 }
2805 /*
2806 * Only do this if we're moving a real
2807 * record. Otherwise, the action is delayed until
2808 * after removal of the right path in which case we
2809 * can do a simple shift to remove the empty extent.
2810 */
2814 }
2816 /*
2817 * Move recs over to get rid of empty extent, decrease
2818 * next_free. This is allowed to remove the last
2819 * extent in our leaf (setting l_next_free_rec to
2820 * zero) - the delete code below won't care.
2821 */
2823 }
2836 left_path);
2840 }
2845 /*
2846 * Removal of the extent in the left leaf was skipped
2847 * above so we could delete the right path
2848 * 1st.
2849 */
2860 subtree_index);
2862 out:
2864 }
2866 /*
2867 * Given a full path, determine what cpos value would return us a path
2868 * containing the leaf immediately to the right of the current one.
2869 *
2870 * Will return zero if the path passed in is already the rightmost path.
2871 *
2872 * This looks similar, but is subtly different to
2873 * ocfs2_find_cpos_for_left_leaf().
2874 */
2877 {
2879 u64 blkno;
2889 /* Start at the tree node just above the leaf and work our way up. */
2896 /*
2897 * Find the extent record just after the one in our
2898 * path.
2899 */
2905 /*
2906 * We've determined that the
2907 * path specified is already
2908 * the rightmost one - return a
2909 * cpos of zero.
2910 */
2912 }
2913 /*
2914 * The rightmost record points to our
2915 * leaf - we need to travel up the
2916 * tree one level.
2917 */
2919 }
2923 }
2924 }
2926 /*
2927 * If we got here, we never found a valid node where
2928 * the tree indicated one should be.
2929 */
2936 next_node:
2938 i--;
2939 }
2941 out:
2943 }
2948 {
2961 }
2969 out:
2971 }
2979 {
2981 u32 right_cpos;
2994 }
3001 }
3010 }
3017 }
3020 right_path);
3023 subtree_root,
3033 }
3035 /*
3036 * Caller might still want to make changes to the
3037 * tree root, so re-add it to the journal here.
3038 */
3044 }
3050 /*
3051 * The rotation has to temporarily stop due to
3052 * the right subtree having an empty
3053 * extent. Pass it back to the caller for a
3054 * fixup.
3055 */
3059 }
3063 }
3065 /*
3066 * The subtree rotate might have removed records on
3067 * the rightmost edge. If so, then rotation is
3068 * complete.
3069 */
3080 }
3081 }
3083 out:
3088 }
3094 {
3096 u32 cpos;
3105 /*
3106 * There's two ways we handle this depending on
3107 * whether path is the only existing one.
3108 */
3111 path);
3115 }
3121 }
3128 }
3131 /*
3132 * We have a path to the left of this one - it needs
3133 * an update too.
3134 */
3140 }
3146 }
3152 }
3159 left_path);
3163 }
3168 /*
3169 * 'path' is also the leftmost path which
3170 * means it must be the only one. This gets
3171 * handled differently because we want to
3172 * revert the root back to having extents
3173 * in-line.
3174 */
3183 }
3187 out:
3190 }
3192 /*
3193 * Left rotation of btree records.
3194 *
3195 * In many ways, this is (unsurprisingly) the opposite of right
3196 * rotation. We start at some non-rightmost path containing an empty
3197 * extent in the leaf block. The code works its way to the rightmost
3198 * path by rotating records to the left in every subtree.
3199 *
3200 * This is used by any code which reduces the number of extent records
3201 * in a leaf. After removal, an empty record should be placed in the
3202 * leftmost list position.
3203 *
3204 * This won't handle a length update of the rightmost path records if
3205 * the rightmost tree leaf record is removed so the caller is
3206 * responsible for detecting and correcting that.
3207 */
3212 {
3223 rightmost_no_delete:
3224 /*
3225 * Inline extents. This is trivially handled, so do
3226 * it up front.
3227 */
3232 }
3234 /*
3235 * Handle rightmost branch now. There's several cases:
3236 * 1) simple rotation leaving records in there. That's trivial.
3237 * 2) rotation requiring a branch delete - there's no more
3238 * records left. Two cases of this:
3239 * a) There are branches to the left.
3240 * b) This is also the leftmost (the only) branch.
3241 *
3242 * 1) is handled via ocfs2_rotate_rightmost_leaf_left()
3243 * 2a) we need the left branch so that we can update it with the unlink
3244 * 2b) we need to bring the root back to inline extents.
3245 */
3250 /*
3251 * This gets a bit tricky if we're going to delete the
3252 * rightmost path. Get the other cases out of the way
3253 * 1st.
3254 */
3265 }
3267 /*
3268 * XXX: The caller can not trust "path" any more after
3269 * this as it will have been deleted. What do we do?
3270 *
3271 * In theory the rotate-for-merge code will never get
3272 * here because it'll always ask for a rotate in a
3273 * nonempty list.
3274 */
3277 dealloc);
3281 }
3283 /*
3284 * Now we can loop, remembering the path we get from -EAGAIN
3285 * and restarting from there.
3286 */
3287 try_rotate:
3293 }
3305 }
3312 }
3314 out:
3318 }
3322 {
3327 /*
3328 * We consumed all of the merged-from record. An empty
3329 * extent cannot exist anywhere but the 1st array
3330 * position, so move things over if the merged-from
3331 * record doesn't occupy that position.
3332 *
3333 * This creates a new empty extent so the caller
3334 * should be smart enough to have removed any existing
3335 * ones.
3336 */
3341 }
3343 /*
3344 * Always memset - the caller doesn't check whether it
3345 * created an empty extent, so there could be junk in
3346 * the other fields.
3347 */
3349 }
3350 }
3355 {
3357 u32 right_cpos;
3363 /* This function shouldn't be called for non-trees. */
3374 }
3376 /* This function shouldn't be called for the rightmost leaf. */
3384 }
3390 }
3393 out:
3397 }
3399 /*
3400 * Remove split_rec clusters from the record at index and merge them
3401 * onto the beginning of the record "next" to it.
3402 * For index < l_count - 1, the next means the extent rec at index + 1.
3403 * For index == l_count - 1, the "next" means the 1st extent rec of the
3404 * next extent block.
3405 */
3411 {
3428 /* we meet with a cross extent block merge. */
3433 }
3442 }
3449 right_path);
3453 right_path);
3457 }
3463 subtree_index);
3467 }
3476 }
3483 }
3484 }
3489 }
3496 }
3503 split_clusters));
3518 subtree_index);
3519 }
3520 out:
3524 }
3529 {
3531 u32 left_cpos;
3536 /* This function shouldn't be called for non-trees. */
3544 }
3546 /* This function shouldn't be called for the leftmost leaf. */
3554 }
3560 }
3563 out:
3567 }
3569 /*
3570 * Remove split_rec clusters from the record at index and merge them
3571 * onto the tail of the record "before" it.
3572 * For index > 0, the "before" means the extent rec at index - 1.
3573 *
3574 * For index == 0, the "before" means the last record of the previous
3575 * extent block. And there is also a situation that we may need to
3576 * remove the rightmost leaf extent block in the right_path and change
3577 * the right path to indicate the new rightmost path.
3578 */
3585 {
3600 /* we meet with a cross extent block merge. */
3605 }
3618 right_path);
3622 left_path);
3626 }
3632 subtree_index);
3636 }
3645 }
3652 }
3653 }
3658 }
3665 }
3668 /*
3669 * The easy case - we can just plop the record right in.
3670 */
3680 split_clusters));
3694 /*
3695 * In the situation that the right_rec is empty and the extent
3696 * block is empty also, ocfs2_complete_edge_insert can't handle
3697 * it and we need to delete the right extent block.
3698 */
3703 right_path,
3704 dealloc);
3708 }
3710 /* Now the rightmost extent block has been deleted.
3711 * So we use the new rightmost path.
3712 */
3718 }
3719 out:
3723 }
3732 {
3740 /*
3741 * The merge code will need to create an empty
3742 * extent to take the place of the newly
3743 * emptied slot. Remove any pre-existing empty
3744 * extents - having more than one in a leaf is
3745 * illegal.
3746 */
3751 }
3752 split_index--;
3754 }
3757 /*
3758 * Left-right contig implies this.
3759 */
3762 /*
3763 * Since the leftright insert always covers the entire
3764 * extent, this call will delete the insert record
3765 * entirely, resulting in an empty extent record added to
3766 * the extent block.
3767 *
3768 * Since the adding of an empty extent shifts
3769 * everything back to the right, there's no need to
3770 * update split_index here.
3771 *
3772 * When the split_index is zero, we need to merge it to the
3773 * prevoius extent block. It is more efficient and easier
3774 * if we do merge_right first and merge_left later.
3775 */
3777 split_index);
3781 }
3783 /*
3784 * We can only get this from logic error above.
3785 */
3788 /* The merge left us with an empty extent, remove it. */
3793 }
3797 /*
3798 * Note that we don't pass split_rec here on purpose -
3799 * we've merged it into the rec already.
3800 */
3807 }
3810 /*
3811 * Error from this last rotate is not critical, so
3812 * print but don't bubble it up.
3813 */
3818 /*
3819 * Merge a record to the left or right.
3820 *
3821 * 'contig_type' is relative to the existing record,
3822 * so for example, if we're "right contig", it's to
3823 * the record on the left (hence the left merge).
3824 */
3828 split_index);
3832 }
3836 split_index);
3840 }
3841 }
3844 /*
3845 * The merge may have left an empty extent in
3846 * our leaf. Try to rotate it away.
3847 */
3849 dealloc);
3853 }
3854 }
3856 out:
3858 }
3864 {
3865 u64 len_blocks;
3871 /*
3872 * Region is on the left edge of the existing
3873 * record.
3874 */
3881 /*
3882 * Region is on the right edge of the existing
3883 * record.
3884 */
3887 }
3888 }
3890 /*
3891 * Do the final bits of extent record insertion at the target leaf
3892 * list. If this leaf is part of an allocation tree, it is assumed
3893 * that the tree above has been prepared.
3894 */
3899 {
3912 insert_rec);
3914 }
3916 /*
3917 * Contiguous insert - either left or right.
3918 */
3924 }
3928 }
3930 /*
3931 * Handle insert into an empty leaf.
3932 */
3939 }
3941 /*
3942 * Appending insert.
3943 */
3953 "owner %llu, depth %u, count %u, next free %u, "
3954 "rec.cpos %u, rec.clusters %u, "
3964 i++;
3968 }
3970 rotate:
3971 /*
3972 * Ok, we have to rotate.
3973 *
3974 * At this point, it is safe to assume that inserting into an
3975 * empty leaf and appending to a leaf have both been handled
3976 * above.
3977 *
3978 * This leaf needs to have space, either by the empty 1st
3979 * extent record, or by virtue of an l_next_rec < l_count.
3980 */
3982 }
3988 {
3994 /*
3995 * Update everything except the leaf block.
3996 */
4008 }
4022 }
4023 }
4030 {
4037 /*
4038 * This shouldn't happen for non-trees. The extent rec cluster
4039 * count manipulation below only works for interior nodes.
4040 */
4043 /*
4044 * If our appending insert is at the leftmost edge of a leaf,
4045 * then we might need to update the rightmost records of the
4046 * neighboring path.
4047 */
4052 u32 left_cpos;
4059 }
4063 left_cpos);
4065 /*
4066 * No need to worry if the append is already in the
4067 * leftmost leaf.
4068 */
4075 }
4078 left_cpos);
4082 }
4084 /*
4085 * ocfs2_insert_path() will pass the left_path to the
4086 * journal for us.
4087 */
4088 }
4089 }
4095 }
4101 out:
4106 }
4113 {
4130 /*
4131 * This typically means that the record
4132 * started in the left path but moved to the
4133 * right as a result of rotation. We either
4134 * move the existing record to the left, or we
4135 * do the later insert there.
4136 *
4137 * In this case, the left path should always
4138 * exist as the rotate code will have passed
4139 * it back for a post-insert update.
4140 */
4143 /*
4144 * It's a left split. Since we know
4145 * that the rotate code gave us an
4146 * empty extent in the left path, we
4147 * can just do the insert there.
4148 */
4151 /*
4152 * Right split - we have to move the
4153 * existing record over to the left
4154 * leaf. The insert will be into the
4155 * newly created empty extent in the
4156 * right leaf.
4157 */
4165 }
4166 }
4170 /*
4171 * Left path is easy - we can just allow the insert to
4172 * happen.
4173 */
4178 }
4184 }
4186 /*
4187 * This function only does inserts on an allocation b-tree. For tree
4188 * depth = 0, ocfs2_insert_at_leaf() is called directly.
4189 *
4190 * right_path is the path we want to do the actual insert
4191 * in. left_path should only be passed in if we need to update that
4192 * portion of the tree after an edge insert.
4193 */
4200 {
4207 /*
4208 * There's a chance that left_path got passed back to
4209 * us without being accounted for in the
4210 * journal. Extend our transaction here to be sure we
4211 * can change those blocks.
4212 */
4219 }
4225 }
4226 }
4228 /*
4229 * Pass both paths to the journal. The majority of inserts
4230 * will be touching all components anyway.
4231 */
4236 }
4239 /*
4240 * We could call ocfs2_insert_at_leaf() for some types
4241 * of splits, but it's easier to just let one separate
4242 * function sort it all out.
4243 */
4247 /*
4248 * Split might have modified either leaf and we don't
4249 * have a guarantee that the later edge insert will
4250 * dirty this for us.
4251 */
4259 insert);
4266 /*
4267 * The rotate code has indicated that we need to fix
4268 * up portions of the tree after the insert.
4269 *
4270 * XXX: Should we extend the transaction here?
4271 */
4273 right_path);
4275 subtree_index);
4276 }
4279 out:
4281 }
4287 {
4289 u32 cpos;
4297 OCFS2_JOURNAL_ACCESS_WRITE);
4301 }
4306 }
4313 }
4315 /*
4316 * Determine the path to start with. Rotations need the
4317 * rightmost path, everything else can go directly to the
4318 * target leaf.
4319 */
4325 }
4331 }
4333 /*
4334 * Rotations and appends need special treatment - they modify
4335 * parts of the tree's above them.
4336 *
4337 * Both might pass back a path immediate to the left of the
4338 * one being inserted to. This will be cause
4339 * ocfs2_insert_path() to modify the rightmost records of
4340 * left_path to account for an edge insert.
4341 *
4342 * XXX: When modifying this code, keep in mind that an insert
4343 * can wind up skipping both of these two special cases...
4344 */
4352 }
4354 /*
4355 * ocfs2_rotate_tree_right() might have extended the
4356 * transaction without re-journaling our tree root.
4357 */
4359 OCFS2_JOURNAL_ACCESS_WRITE);
4363 }
4371 }
4372 }
4379 }
4381 out_update_clusters:
4390 out:
4395 }
4397 static enum ocfs2_contig_type
4402 {
4426 left_cpos);
4437 "Extent block #%llu has an "
4438 "invalid l_next_free_rec of "
4439 "%d. It should have "
4446 }
4449 }
4450 }
4452 /*
4453 * We're careful to check for an empty extent record here -
4454 * the merge code will know what to do if it sees one.
4455 */
4462 }
4463 }
4492 "Extent block #%llu has an "
4498 }
4500 }
4501 }
4512 }
4514 out:
4521 }
4527 {
4535 insert_rec);
4539 }
4540 }
4549 /*
4550 * Caller might want us to limit the size of extents, don't
4551 * calculate contiguousness if we might exceed that limit.
4552 */
4556 }
4557 }
4559 /*
4560 * This should only be called against the righmost leaf extent list.
4561 *
4562 * ocfs2_figure_appending_type() will figure out whether we'll have to
4563 * insert at the tail of the rightmost leaf.
4564 *
4565 * This should also work against the root extent list for tree's with 0
4566 * depth. If we consider the root extent list to be the rightmost leaf node
4567 * then the logic here makes sense.
4568 */
4572 {
4585 /* Were all records empty? */
4588 }
4599 set_tail_append:
4601 }
4603 /*
4604 * Helper function called at the begining of an insert.
4605 *
4606 * This computes a few things that are commonly used in the process of
4607 * inserting into the btree:
4608 * - Whether the new extent is contiguous with an existing one.
4609 * - The current tree depth.
4610 * - Whether the insert is an appending one.
4611 * - The total # of free records in the tree.
4612 *
4613 * All of the information is stored on the ocfs2_insert_type
4614 * structure.
4615 */
4621 {
4634 /*
4635 * If we have tree depth, we read in the
4636 * rightmost extent block ahead of time as
4637 * ocfs2_figure_insert_type() and ocfs2_add_branch()
4638 * may want it later.
4639 */
4646 }
4649 }
4651 /*
4652 * Unless we have a contiguous insert, we'll need to know if
4653 * there is room left in our allocation tree for another
4654 * extent record.
4655 *
4656 * XXX: This test is simplistic, we can search for empty
4657 * extent records too.
4658 */
4666 }
4673 }
4675 /*
4676 * In the case that we're inserting past what the tree
4677 * currently accounts for, ocfs2_find_path() will return for
4678 * us the rightmost tree path. This is accounted for below in
4679 * the appending code.
4680 */
4685 }
4689 /*
4690 * Now that we have the path, there's two things we want to determine:
4691 * 1) Contiguousness (also set contig_index if this is so)
4692 *
4693 * 2) Are we doing an append? We can trivially break this up
4694 * into two types of appends: simple record append, or a
4695 * rotate inside the tail leaf.
4696 */
4699 /*
4700 * The insert code isn't quite ready to deal with all cases of
4701 * left contiguousness. Specifically, if it's an insert into
4702 * the 1st record in a leaf, it will require the adjustment of
4703 * cluster count on the last record of the path directly to it's
4704 * left. For now, just catch that case and fool the layers
4705 * above us. This works just fine for tree_depth == 0, which
4706 * is why we allow that above.
4707 */
4712 /*
4713 * Ok, so we can simply compare against last_eb to figure out
4714 * whether the path doesn't exist. This will only happen in
4715 * the case that we're doing a tail append, so maybe we can
4716 * take advantage of that information somehow.
4717 */
4720 /*
4721 * Ok, ocfs2_find_path() returned us the rightmost
4722 * tree path. This might be an appending insert. There are
4723 * two cases:
4724 * 1) We're doing a true append at the tail:
4725 * -This might even be off the end of the leaf
4726 * 2) We're "appending" by rotating in the tail
4727 */
4729 }
4731 out:
4736 else
4739 }
4741 /*
4742 * Insert an extent into a btree.
4743 *
4744 * The caller needs to update the owning btree's cluster count.
4745 */
4748 u32 cpos,
4749 u64 start_blk,
4750 u32 new_clusters,
4751 u8 flags,
4753 {
4773 }
4780 }
4783 "Insert.contig_index: %d, Insert.free_records: %d, "
4791 meta_ac);
4795 }
4796 }
4798 /* Finally, we can add clusters. This might rotate the tree for us. */
4802 else
4805 bail:
4810 }
4812 /*
4813 * Allcate and add clusters into the extent b-tree.
4814 * The new clusters(clusters_to_add) will be inserted at logical_offset.
4815 * The extent b-tree's root is specified by et, and
4816 * it is not limited to the file storage. Any extent tree can use this
4817 * function if it implements the proper ocfs2_extent_tree.
4818 */
4822 u32 clusters_to_add,
4827 {
4832 u64 block;
4847 }
4849 /* there are two cases which could cause us to EAGAIN in the
4850 * we-need-more-metadata case:
4851 * 1) we haven't reserved *any*
4852 * 2) we are so fragmented, we've needed to add metadata too
4853 * many times. */
4866 }
4874 }
4878 /* reserve our write early -- insert_extent may update the tree root */
4880 OCFS2_JOURNAL_ACCESS_WRITE);
4884 }
4895 }
4901 }
4908 clusters_to_add);
4911 }
4913 leave:
4918 }
4922 u32 cpos,
4924 {
4938 }
4947 {
4957 leftright:
4958 /*
4959 * Store a copy of the record on the stack - it might move
4960 * around as the tree is manipulated below.
4961 */
4971 }
4980 }
4981 }
4998 /*
4999 * Left/right split. We fake this as a right split
5000 * first and then make a second pass as a left split.
5001 */
5011 }
5017 }
5020 u32 cpos;
5023 do_leftright++;
5033 }
5038 }
5039 out:
5042 }
5050 {
5058 }
5063 out:
5065 }
5067 /*
5068 * Split part or all of the extent record at split_index in the leaf
5069 * pointed to by path. Merge with the contiguous extent record if needed.
5070 *
5071 * Care is taken to handle contiguousness so as to not grow the tree.
5072 *
5073 * meta_ac is not strictly necessary - we only truly need it if growth
5074 * of the tree is required. All other cases will degrade into a less
5075 * optimal tree layout.
5076 *
5077 * last_eb_bh should be the rightmost leaf block for any extent
5078 * btree. Since a split may grow the tree or a merge might shrink it,
5079 * the caller cannot trust the contents of that buffer after this call.
5080 *
5081 * This code is optimized for readability - several passes might be
5082 * made over certain portions of the tree. All of those blocks will
5083 * have been brought into cache (and pinned via the journal), so the
5084 * extra overhead is not expressed in terms of disk reads.
5085 */
5093 {
5107 }
5110 split_index,
5111 split_rec);
5113 /*
5114 * The core merge / split code wants to know how much room is
5115 * left in this allocation tree, so we pass the
5116 * rightmost extent list.
5117 */
5127 }
5137 else
5150 else
5162 }
5164 out:
5167 }
5169 /*
5170 * Change the flags of the already-existing extent at cpos for len clusters.
5171 *
5172 * new_flags: the flags we want to set.
5173 * clear_flags: the flags we want to clear.
5174 * phys: the new physical offset we want this new extent starts from.
5175 *
5176 * If the existing extent is larger than the request, initiate a
5177 * split. An attempt will be made at merging with adjacent extents.
5178 *
5179 * The caller is responsible for passing down meta_ac if we'll need it.
5180 */
5187 {
5201 }
5207 }
5213 "Owner %llu has an extent at cpos %u which can no "
5219 }
5227 new_flags);
5229 }
5235 clear_flags);
5237 }
5251 dealloc);
5255 out:
5259 }
5261 /*
5262 * Mark the already-existing extent at cpos as written for len clusters.
5263 * This removes the unwritten extent flag.
5264 *
5265 * If the existing extent is larger than the request, initiate a
5266 * split. An attempt will be made at merging with adjacent extents.
5267 *
5268 * The caller is responsible for passing down meta_ac if we'll need it.
5269 */
5275 {
5283 "that are being written to, but the feature bit "
5288 }
5290 /*
5291 * XXX: This should be fixed up so that we just re-insert the
5292 * next extent records.
5293 */
5302 out:
5304 }
5310 {
5319 /*
5320 * Setup the record to split before we grow the tree.
5321 */
5335 }
5348 }
5353 meta_ac);
5357 }
5358 }
5370 out:
5373 }
5380 {
5395 }
5397 index--;
5398 }
5402 /*
5403 * Check whether this is the rightmost tree record. If
5404 * we remove all of this record or part of its right
5405 * edge then an update of the record lengths above it
5406 * will be required.
5407 */
5411 }
5416 /*
5417 * Changing the leftmost offset (via partial or whole
5418 * record truncate) of an interior (or rightmost) path
5419 * means we have to update the subtree that is formed
5420 * by this leaf and the one to it's left.
5421 *
5422 * There are two cases we can skip:
5423 * 1) Path is the leftmost one in our btree.
5424 * 2) The leaf is rightmost and will be empty after
5425 * we remove the extent record - the rotate code
5426 * knows how to update the newly formed edge.
5427 */
5433 }
5441 }
5444 left_cpos);
5448 }
5449 }
5450 }
5454 path);
5458 }
5464 }
5470 }
5484 /*
5485 * We skip the edge update if this path will
5486 * be deleted by the rotate code.
5487 */
5490 rec);
5491 }
5493 /* Remove leftmost portion of the record. */
5498 /* Remove rightmost portion of the record */
5503 /* Caller should have trapped this. */
5510 }
5517 subtree_index);
5518 }
5526 }
5528 out:
5531 }
5538 {
5545 /*
5546 * XXX: Why are we truncating to 0 instead of wherever this
5547 * affects us?
5548 */
5556 }
5562 }
5568 "Owner %llu has an extent at cpos %u which can no "
5571 cpos);
5574 }
5576 /*
5577 * We have 3 cases of extent removal:
5578 * 1) Range covers the entire extent rec
5579 * 2) Range begins or ends on one edge of the extent rec
5580 * 3) Range is in the middle of the extent rec (no shared edges)
5581 *
5582 * For case 1 we remove the extent rec and left rotate to
5583 * fill the hole.
5584 *
5585 * For case 2 we just shrink the existing extent rec, with a
5586 * tree update if the shrinking edge is also the edge of an
5587 * extent block.
5588 *
5589 * For case 3 we do a right split to turn the extent rec into
5590 * something case 2 can handle.
5591 */
5610 }
5617 }
5619 /*
5620 * The split could have manipulated the tree enough to
5621 * move the record location, so we have to look for it again.
5622 */
5629 }
5637 cpos);
5640 }
5642 /*
5643 * Double check our values here. If anything is fishy,
5644 * it's easier to catch it at the top level.
5645 */
5651 "Owner %llu: error after split at cpos %u"
5658 }
5665 }
5666 }
5668 out:
5671 }
5677 {
5689 }
5698 }
5699 }
5706 }
5709 OCFS2_JOURNAL_ACCESS_WRITE);
5713 }
5722 }
5730 }
5736 out_commit:
5738 out:
5745 }
5748 {
5757 "slot %d, invalid truncate log parameters: used = "
5761 }
5765 {
5769 /* No records, nothing to coalesce */
5778 }
5782 u64 start_blk,
5784 {
5801 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5802 * by the underlying call to ocfs2_read_inode_block(), so any
5803 * corruption is a code bug */
5810 "Truncate record count on #%llu invalid "
5816 /* Caller should have known to flush before calling us. */
5822 }
5825 OCFS2_JOURNAL_ACCESS_WRITE);
5829 }
5836 /*
5837 * Move index back to the record we are coalescing with.
5838 * ocfs2_truncate_log_can_coalesce() guarantees nonzero
5839 */
5840 index--;
5845 num_clusters);
5849 }
5856 }
5858 bail:
5861 }
5867 {
5871 u64 start_blk;
5884 /* Caller has given us at least enough credits to
5885 * update the truncate log dinode */
5887 OCFS2_JOURNAL_ACCESS_WRITE);
5891 }
5899 }
5901 /* TODO: Perhaps we can calculate the bulk of the
5902 * credits up front rather than extending like
5903 * this. */
5905 OCFS2_TRUNCATE_LOG_FLUSH_ONE_REC);
5909 }
5916 /* if start_blk is not set, we ignore the record as
5917 * invalid. */
5924 num_clusters);
5928 }
5929 }
5930 i--;
5931 }
5933 bail:
5936 }
5938 /* Expects you to already be holding tl_inode->i_mutex */
5940 {
5957 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5958 * by the underlying call to ocfs2_read_inode_block(), so any
5959 * corruption is a code bug */
5969 }
5972 GLOBAL_BITMAP_SYSTEM_INODE,
5973 OCFS2_INVALID_SLOT);
5978 }
5986 }
5993 }
5996 data_alloc_bh);
6002 out_unlock:
6006 out_mutex:
6010 out:
6013 }
6016 {
6025 }
6028 {
6039 else
6043 }
6045 #define OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL (2 * HZ)
6048 {
6050 /* We want to push off log flushes while truncates are
6051 * still running. */
6056 OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL);
6057 }
6058 }
6064 {
6070 TRUNCATE_LOG_SYSTEM_INODE,
6071 slot_num);
6076 }
6083 }
6087 bail:
6090 }
6092 /* called during the 1st stage of node recovery. we stamp a clean
6093 * truncate log and pass back a copy for processing later. if the
6094 * truncate log does not require processing, a *tl_copy is set to
6095 * NULL. */
6099 {
6114 }
6118 /* tl_bh is loaded from ocfs2_get_truncate_log_info(). It's
6119 * validated by the underlying call to ocfs2_read_inode_block(),
6120 * so any corruption is a code bug */
6133 }
6135 /* Assuming the write-out below goes well, this copy
6136 * will be passed back to recovery for processing. */
6139 /* All we need to do to clear the truncate log is set
6140 * tl_used. */
6148 }
6149 }
6151 bail:
6159 }
6163 }
6167 {
6171 u64 start_blk;
6181 }
6195 }
6196 }
6203 }
6215 }
6216 }
6218 bail_up:
6223 }
6226 {
6242 }
6245 }
6248 {
6262 /* ocfs2_truncate_log_shutdown keys on the existence of
6263 * osb->osb_tl_inode so we don't set any of the osb variables
6264 * until we're sure all is well. */
6266 ocfs2_truncate_log_worker);
6272 }
6274 /*
6275 * Delayed de-allocation of suballocator blocks.
6276 *
6277 * Some sets of block de-allocations might involve multiple suballocator inodes.
6278 *
6279 * The locking for this can get extremely complicated, especially when
6280 * the suballocator inodes to delete from aren't known until deep
6281 * within an unrelated codepath.
6282 *
6283 * ocfs2_extent_block structures are a good example of this - an inode
6284 * btree could have been grown by any number of nodes each allocating
6285 * out of their own suballoc inode.
6286 *
6287 * These structures allow the delay of block de-allocation until a
6288 * later time, when locking of multiple cluster inodes won't cause
6289 * deadlock.
6290 */
6292 /*
6293 * Describe a single bit freed from a suballocator. For the block
6294 * suballocators, it represents one block. For the global cluster
6295 * allocator, it represents some clusters and free_bit indicates
6296 * clusters number.
6297 */
6300 u64 free_blk;
6302 };
6309 };
6315 {
6317 u64 bg_blkno;
6328 }
6336 }
6343 }
6356 }
6362 }
6367 }
6369 out_journal:
6372 out_unlock:
6375 out_mutex:
6378 out:
6380 /* Premature exit may have left some dangling items. */
6384 }
6387 }
6391 {
6400 }
6411 }
6415 {
6429 }
6430 }
6437 }
6450 }
6451 }
6456 /* Premature exit may have left some dangling items. */
6460 }
6463 }
6467 {
6488 }
6492 }
6503 }
6506 }
6512 {
6520 }
6530 }
6532 }
6537 {
6547 }
6554 }
6566 out:
6568 }
6572 {
6577 }
6579 /* This function will figure out whether the currently last extent
6580 * block will be deleted, and if it will, what the new last extent
6581 * block will be so we can update his h_next_leaf_blk field, as well
6582 * as the dinodes i_last_eb_blk */
6587 {
6589 u32 cpos;
6597 /* we have no tree, so of course, no last_eb. */
6601 /* trunc to zero special case - this makes tree_depth = 0
6602 * regardless of what it is. */
6609 /*
6610 * Make sure that this extent list will actually be empty
6611 * after we clear away the data. We can shortcut out if
6612 * there's more than one non-empty extent in the
6613 * list. Otherwise, a check of the remaining extent is
6614 * necessary.
6615 */
6622 /* We may have a valid extent in index 1, check it. */
6626 /*
6627 * Fall through - no more nonempty extents, so we want
6628 * to delete this leaf.
6629 */
6635 }
6638 /*
6639 * Check it we'll only be trimming off the end of this
6640 * cluster.
6641 */
6644 }
6650 }
6656 }
6661 /* ocfs2_find_leaf() gets the eb from ocfs2_read_extent_block().
6662 * Any corruption is a code bug. */
6669 out:
6673 }
6675 /*
6676 * Trim some clusters off the rightmost edge of a tree. Only called
6677 * during truncate.
6678 *
6679 * The caller needs to:
6680 * - start journaling of each path component.
6681 * - compute and fully set up any new last ext block
6682 */
6686 {
6714 }
6716 find_tail_record:
6729 /*
6730 * If the leaf block contains a single empty
6731 * extent and no records, we can just remove
6732 * the block.
6733 */
6740 }
6742 /*
6743 * Remove any empty extents by shifting things
6744 * left. That should make life much easier on
6745 * the code below. This condition is rare
6746 * enough that we shouldn't see a performance
6747 * hit.
6748 */
6759 /*
6760 * We've modified our extent list. The
6761 * simplest way to handle this change
6762 * is to being the search from the
6763 * start again.
6764 */
6766 }
6770 /*
6771 * We'll use "new_edge" on our way back up the
6772 * tree to know what our rightmost cpos is.
6773 */
6777 /*
6778 * The caller will use this to delete data blocks.
6779 */
6785 /*
6786 * If it's now empty, remove this record.
6787 */
6792 }
6800 }
6802 /* Can this actually happen? */
6806 /*
6807 * We never actually deleted any clusters
6808 * because our leaf was empty. There's no
6809 * reason to adjust the rightmost edge then.
6810 */
6818 /*
6819 * A deleted child record should have been
6820 * caught above.
6821 */
6823 }
6830 }
6839 /*
6840 * We must be careful to only attempt delete of an
6841 * extent block (and not the root inode block).
6842 */
6847 /*
6848 * Save this for use when processing the
6849 * parent block.
6850 */
6862 /* An error here is not fatal. */
6867 }
6869 index--;
6870 }
6873 out:
6875 }
6885 {
6892 u8 rec_flags;
6901 }
6903 /*
6904 * Each component will be touched, so we might as well journal
6905 * here to avoid having to handle errors later.
6906 */
6911 }
6915 OCFS2_JOURNAL_ACCESS_WRITE);
6919 }
6922 }
6926 /*
6927 * Lower levels depend on this never happening, but it's best
6928 * to check it up here before changing the tree.
6929 */
6936 }
6942 clusters_to_del;
6952 }
6955 /* trunc to zero is a special case. */
6965 }
6968 /* If there will be a new last extent block, then by
6969 * definition, there cannot be any leaves to the right of
6970 * him. */
6976 }
6977 }
6983 delete_blk),
6986 else
6988 delete_blk,
6989 clusters_to_del);
6993 }
6994 }
6996 bail:
7000 }
7003 {
7007 }
7012 {
7022 /*
7023 * Need to set the buffers we zero'd into uptodate
7024 * here if they aren't - ocfs2_map_page_blocks()
7025 * might've skipped some
7026 */
7029 ocfs2_zero_func);
7036 }
7042 }
7047 {
7073 }
7074 out:
7077 }
7081 {
7085 loff_t last_page_bytes;
7098 }
7100 numpages++;
7101 index++;
7104 out:
7109 }
7114 }
7118 {
7125 }
7127 /*
7128 * Zero the area past i_size but still within an allocated
7129 * cluster. This avoids exposing nonzero data on subsequent file
7130 * extends.
7131 *
7132 * We need to call this before i_size is updated on the inode because
7133 * otherwise block_write_full_page() will skip writeout of pages past
7134 * i_size. The new_i_size parameter is passed for this reason.
7135 */
7138 {
7141 u64 phys;
7145 /*
7146 * File systems which don't support sparse files zero on every
7147 * extend.
7148 */
7158 }
7169 }
7171 /*
7172 * Tail is a hole, or is marked unwritten. In either case, we
7173 * can count on read and write to return/push zero's.
7174 */
7183 }
7188 /*
7189 * Initiate writeout of the pages we zero'd here. We don't
7190 * wait on them - the truncate_inode_pages() call later will
7191 * do that for us.
7192 */
7198 out:
7203 }
7207 {
7214 xattrsize);
7215 else
7218 }
7222 {
7228 }
7231 {
7240 /*
7241 * We clear the entire i_data structure here so that all
7242 * fields can be properly initialized.
7243 */
7248 }
7252 {
7274 }
7280 }
7281 }
7289 }
7292 OCFS2_JOURNAL_ACCESS_WRITE);
7296 }
7301 u64 phys;
7307 }
7315 }
7317 /*
7318 * Save two copies, one for insert, and one that can
7319 * be changed by ocfs2_map_and_dirty_page() below.
7320 */
7323 /*
7324 * Non sparse file systems zero on extend, so no need
7325 * to do that now.
7326 */
7335 }
7337 /*
7338 * This should populate the 1st page for us and mark
7339 * it up to date.
7340 */
7345 }
7354 }
7366 /*
7367 * An error at this point should be extremely rare. If
7368 * this proves to be false, we could always re-build
7369 * the in-inode data from our pages.
7370 */
7376 }
7379 }
7381 out_commit:
7388 out_unlock:
7392 out:
7396 }
7399 }
7401 /*
7402 * It is expected, that by the time you call this function,
7403 * inode->i_size and fe->i_size have been adjusted.
7404 *
7405 * WARNING: This will kfree the truncate context
7406 */
7411 {
7429 ocfs2_journal_access_di);
7434 }
7438 start:
7439 /*
7440 * Check that we still have allocation to delete.
7441 */
7445 }
7449 /*
7450 * Truncate always works against the rightmost tree branch.
7451 */
7456 }
7461 /*
7462 * By now, el will point to the extent list on the bottom most
7463 * portion of this tree. Only the tail record is considered in
7464 * each pass.
7465 *
7466 * We handle the following cases, in order:
7467 * - empty extent: delete the remaining branch
7468 * - remove the entire record
7469 * - remove a partial record
7470 * - no record needs to be removed (truncate has completed)
7471 */
7480 }
7493 new_highest_cpos;
7497 clusters_to_del);
7501 }
7508 OCFS2_HAS_REFCOUNT_FL));
7516 }
7519 blkno,
7520 clusters_to_del,
7526 }
7527 }
7531 /* ocfs2_truncate_log_needs_flush guarantees us at least one
7532 * record is free for use. If there isn't any, we flush to get
7533 * an empty truncate log. */
7539 }
7540 }
7544 el);
7551 }
7558 }
7571 }
7576 }
7578 /*
7579 * The check above will catch the case where we've truncated
7580 * away all allocation.
7581 */
7584 bail:
7604 /* This will drop the ext_alloc cluster lock for us */
7609 }
7611 /*
7612 * Expects the inode to already be locked.
7613 */
7618 {
7642 }
7652 }
7654 }
7659 bail:
7664 }
7667 }
7669 /*
7670 * 'start' is inclusive, 'end' is not.
7671 */
7674 {
7691 "Inline data flags for inode %llu don't agree! "
7699 }
7706 }
7709 OCFS2_JOURNAL_ACCESS_WRITE);
7713 }
7718 /*
7719 * No need to worry about the data page here - it's been
7720 * truncated already and inline data doesn't need it for
7721 * pushing zero's to disk, so we'll let readpage pick it up
7722 * later.
7723 */
7727 }
7737 out_commit:
7740 out:
7742 }
7745 {
7746 /*
7747 * The caller is responsible for completing deallocation
7748 * before freeing the context.
7749 */
7757 }