| blob | a74ea700ffdc30d75a42e0b8297fde4f3b76cad8 |
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. */
1059 suballoc_bit_start++;
1060 first_blkno++;
1062 /* We'll also be dirtied by the caller, so
1063 * this isn't absolutely necessary. */
1065 }
1068 }
1071 bail:
1076 }
1077 }
1080 }
1082 /*
1083 * Helper function for ocfs2_add_branch() and ocfs2_shift_tree_depth().
1084 *
1085 * Returns the sum of the rightmost extent rec logical offset and
1086 * cluster count.
1087 *
1088 * ocfs2_add_branch() uses this to determine what logical cluster
1089 * value should be populated into the leftmost new branch records.
1090 *
1091 * ocfs2_shift_tree_depth() uses this to determine the # clusters
1092 * value for the new topmost tree record.
1093 */
1095 {
1102 }
1104 /*
1105 * Change range of the branches in the right most path according to the leaf
1106 * extent block's rightmost record.
1107 */
1110 {
1120 }
1126 }
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 {
2302 }
2305 }
2307 /*
2308 * Trap the case where we're inserting into the theoretical range past
2309 * the _actual_ left leaf range. Otherwise, we'll rotate a record
2310 * whose cpos is less than ours into the right leaf.
2311 *
2312 * It's only necessary to look at the rightmost record of the left
2313 * leaf because the logic that calls us should ensure that the
2314 * theoretical ranges in the path components above the leaves are
2315 * correct.
2316 */
2318 u32 insert_cpos)
2319 {
2331 }
2334 {
2344 /* Empty list. */
2348 }
2354 }
2356 /*
2357 * Rotate all the records in a btree right one record, starting at insert_cpos.
2358 *
2359 * The path to the rightmost leaf should be passed in.
2360 *
2361 * The array is assumed to be large enough to hold an entire path (tree depth).
2362 *
2363 * Upon successful return from this function:
2364 *
2365 * - The 'right_path' array will contain a path to the leaf block
2366 * whose range contains e_cpos.
2367 * - That leaf block will have a single empty extent in list index 0.
2368 * - In the case that the rotation requires a post-insert update,
2369 * *ret_left_path will contain a valid path which can be passed to
2370 * ocfs2_insert_path().
2371 */
2375 u32 insert_cpos,
2378 {
2380 u32 cpos;
2391 }
2397 }
2401 /*
2402 * What we want to do here is:
2403 *
2404 * 1) Start with the rightmost path.
2405 *
2406 * 2) Determine a path to the leaf block directly to the left
2407 * of that leaf.
2408 *
2409 * 3) Determine the 'subtree root' - the lowest level tree node
2410 * which contains a path to both leaves.
2411 *
2412 * 4) Rotate the subtree.
2413 *
2414 * 5) Find the next subtree by considering the left path to be
2415 * the new right path.
2416 *
2417 * The check at the top of this while loop also accepts
2418 * insert_cpos == cpos because cpos is only a _theoretical_
2419 * value to get us the left path - insert_cpos might very well
2420 * be filling that hole.
2421 *
2422 * Stop at a cpos of '0' because we either started at the
2423 * leftmost branch (i.e., a tree with one branch and a
2424 * rotation inside of it), or we've gone as far as we can in
2425 * rotating subtrees.
2426 */
2435 }
2439 "Owner %llu: error during insert of %u "
2440 "(left path cpos %u) results in two identical "
2449 insert_cpos)) {
2451 /*
2452 * We've rotated the tree as much as we
2453 * should. The rest is up to
2454 * ocfs2_insert_path() to complete, after the
2455 * record insertion. We indicate this
2456 * situation by returning the left path.
2457 *
2458 * The reason we don't adjust the records here
2459 * before the record insert is that an error
2460 * later might break the rule where a parent
2461 * record e_cpos will reflect the actual
2462 * e_cpos of the 1st nonempty record of the
2463 * child list.
2464 */
2467 }
2472 start,
2481 }
2488 }
2492 insert_cpos)) {
2493 /*
2494 * A rotate moves the rightmost left leaf
2495 * record over to the leftmost right leaf
2496 * slot. If we're doing an extent split
2497 * instead of a real insert, then we have to
2498 * check that the extent to be split wasn't
2499 * just moved over. If it was, then we can
2500 * exit here, passing left_path back -
2501 * ocfs2_split_extent() is smart enough to
2502 * search both leaves.
2503 */
2506 }
2508 /*
2509 * There is no need to re-read the next right path
2510 * as we know that it'll be our current left
2511 * path. Optimize by copying values instead.
2512 */
2519 }
2520 }
2522 out:
2525 out_ret_path:
2527 }
2532 {
2537 u32 range;
2539 /*
2540 * In normal tree rotation process, we will never touch the
2541 * tree branch above subtree_index and ocfs2_extend_rotate_transaction
2542 * doesn't reserve the credits for them either.
2543 *
2544 * But we do have a special case here which will update the rightmost
2545 * records for all the bh in the path.
2546 * So we have to allocate extra credits and access them.
2547 */
2553 }
2559 }
2561 /* Path should always be rightmost. */
2580 }
2581 out:
2583 }
2589 {
2599 /*
2600 * Not all nodes might have had their final count
2601 * decremented by the caller - handle this here.
2602 */
2606 "Inode %llu, attempted to remove extent block "
2615 }
2627 }
2628 }
2636 {
2664 }
2673 {
2691 /*
2692 * It's legal for us to proceed if the right leaf is
2693 * the rightmost one and it has an empty extent. There
2694 * are two cases to handle - whether the leaf will be
2695 * empty after removal or not. If the leaf isn't empty
2696 * then just remove the empty extent up front. The
2697 * next block will handle empty leaves by flagging
2698 * them for unlink.
2699 *
2700 * Non rightmost leaves will throw -EAGAIN and the
2701 * caller can manually move the subtree and retry.
2702 */
2710 OCFS2_JOURNAL_ACCESS_WRITE);
2714 }
2719 }
2723 /*
2724 * We have to update i_last_eb_blk during the meta
2725 * data delete.
2726 */
2728 OCFS2_JOURNAL_ACCESS_WRITE);
2732 }
2735 }
2737 /*
2738 * Getting here with an empty extent in the right path implies
2739 * that it's the rightmost path and will be deleted.
2740 */
2744 subtree_index);
2748 }
2756 }
2763 }
2764 }
2767 /*
2768 * Only do this if we're moving a real
2769 * record. Otherwise, the action is delayed until
2770 * after removal of the right path in which case we
2771 * can do a simple shift to remove the empty extent.
2772 */
2776 }
2778 /*
2779 * Move recs over to get rid of empty extent, decrease
2780 * next_free. This is allowed to remove the last
2781 * extent in our leaf (setting l_next_free_rec to
2782 * zero) - the delete code below won't care.
2783 */
2785 }
2794 left_path);
2798 }
2803 /*
2804 * Removal of the extent in the left leaf was skipped
2805 * above so we could delete the right path
2806 * 1st.
2807 */
2816 subtree_index);
2818 out:
2820 }
2822 /*
2823 * Given a full path, determine what cpos value would return us a path
2824 * containing the leaf immediately to the right of the current one.
2825 *
2826 * Will return zero if the path passed in is already the rightmost path.
2827 *
2828 * This looks similar, but is subtly different to
2829 * ocfs2_find_cpos_for_left_leaf().
2830 */
2833 {
2835 u64 blkno;
2845 /* Start at the tree node just above the leaf and work our way up. */
2852 /*
2853 * Find the extent record just after the one in our
2854 * path.
2855 */
2861 /*
2862 * We've determined that the
2863 * path specified is already
2864 * the rightmost one - return a
2865 * cpos of zero.
2866 */
2868 }
2869 /*
2870 * The rightmost record points to our
2871 * leaf - we need to travel up the
2872 * tree one level.
2873 */
2875 }
2879 }
2880 }
2882 /*
2883 * If we got here, we never found a valid node where
2884 * the tree indicated one should be.
2885 */
2892 next_node:
2894 i--;
2895 }
2897 out:
2899 }
2904 {
2917 }
2922 out:
2924 }
2932 {
2934 u32 right_cpos;
2947 }
2954 }
2963 }
2970 }
2973 right_path);
2976 subtree_root,
2986 }
2988 /*
2989 * Caller might still want to make changes to the
2990 * tree root, so re-add it to the journal here.
2991 */
2997 }
3003 /*
3004 * The rotation has to temporarily stop due to
3005 * the right subtree having an empty
3006 * extent. Pass it back to the caller for a
3007 * fixup.
3008 */
3012 }
3016 }
3018 /*
3019 * The subtree rotate might have removed records on
3020 * the rightmost edge. If so, then rotation is
3021 * complete.
3022 */
3033 }
3034 }
3036 out:
3041 }
3047 {
3049 u32 cpos;
3058 /*
3059 * There's two ways we handle this depending on
3060 * whether path is the only existing one.
3061 */
3064 path);
3068 }
3074 }
3081 }
3084 /*
3085 * We have a path to the left of this one - it needs
3086 * an update too.
3087 */
3093 }
3099 }
3105 }
3112 left_path);
3116 }
3121 /*
3122 * 'path' is also the leftmost path which
3123 * means it must be the only one. This gets
3124 * handled differently because we want to
3125 * revert the root back to having extents
3126 * in-line.
3127 */
3136 }
3140 out:
3143 }
3145 /*
3146 * Left rotation of btree records.
3147 *
3148 * In many ways, this is (unsurprisingly) the opposite of right
3149 * rotation. We start at some non-rightmost path containing an empty
3150 * extent in the leaf block. The code works its way to the rightmost
3151 * path by rotating records to the left in every subtree.
3152 *
3153 * This is used by any code which reduces the number of extent records
3154 * in a leaf. After removal, an empty record should be placed in the
3155 * leftmost list position.
3156 *
3157 * This won't handle a length update of the rightmost path records if
3158 * the rightmost tree leaf record is removed so the caller is
3159 * responsible for detecting and correcting that.
3160 */
3165 {
3176 rightmost_no_delete:
3177 /*
3178 * Inline extents. This is trivially handled, so do
3179 * it up front.
3180 */
3185 }
3187 /*
3188 * Handle rightmost branch now. There's several cases:
3189 * 1) simple rotation leaving records in there. That's trivial.
3190 * 2) rotation requiring a branch delete - there's no more
3191 * records left. Two cases of this:
3192 * a) There are branches to the left.
3193 * b) This is also the leftmost (the only) branch.
3194 *
3195 * 1) is handled via ocfs2_rotate_rightmost_leaf_left()
3196 * 2a) we need the left branch so that we can update it with the unlink
3197 * 2b) we need to bring the root back to inline extents.
3198 */
3203 /*
3204 * This gets a bit tricky if we're going to delete the
3205 * rightmost path. Get the other cases out of the way
3206 * 1st.
3207 */
3218 }
3220 /*
3221 * XXX: The caller can not trust "path" any more after
3222 * this as it will have been deleted. What do we do?
3223 *
3224 * In theory the rotate-for-merge code will never get
3225 * here because it'll always ask for a rotate in a
3226 * nonempty list.
3227 */
3230 dealloc);
3234 }
3236 /*
3237 * Now we can loop, remembering the path we get from -EAGAIN
3238 * and restarting from there.
3239 */
3240 try_rotate:
3246 }
3258 }
3265 }
3267 out:
3271 }
3275 {
3280 /*
3281 * We consumed all of the merged-from record. An empty
3282 * extent cannot exist anywhere but the 1st array
3283 * position, so move things over if the merged-from
3284 * record doesn't occupy that position.
3285 *
3286 * This creates a new empty extent so the caller
3287 * should be smart enough to have removed any existing
3288 * ones.
3289 */
3294 }
3296 /*
3297 * Always memset - the caller doesn't check whether it
3298 * created an empty extent, so there could be junk in
3299 * the other fields.
3300 */
3302 }
3303 }
3308 {
3310 u32 right_cpos;
3316 /* This function shouldn't be called for non-trees. */
3327 }
3329 /* This function shouldn't be called for the rightmost leaf. */
3337 }
3343 }
3346 out:
3350 }
3352 /*
3353 * Remove split_rec clusters from the record at index and merge them
3354 * onto the beginning of the record "next" to it.
3355 * For index < l_count - 1, the next means the extent rec at index + 1.
3356 * For index == l_count - 1, the "next" means the 1st extent rec of the
3357 * next extent block.
3358 */
3364 {
3381 /* we meet with a cross extent block merge. */
3386 }
3395 }
3402 right_path);
3406 right_path);
3410 }
3416 subtree_index);
3420 }
3429 }
3436 }
3437 }
3442 }
3449 }
3456 split_clusters));
3465 subtree_index);
3466 }
3467 out:
3471 }
3476 {
3478 u32 left_cpos;
3483 /* This function shouldn't be called for non-trees. */
3491 }
3493 /* This function shouldn't be called for the leftmost leaf. */
3501 }
3507 }
3510 out:
3514 }
3516 /*
3517 * Remove split_rec clusters from the record at index and merge them
3518 * onto the tail of the record "before" it.
3519 * For index > 0, the "before" means the extent rec at index - 1.
3520 *
3521 * For index == 0, the "before" means the last record of the previous
3522 * extent block. And there is also a situation that we may need to
3523 * remove the rightmost leaf extent block in the right_path and change
3524 * the right path to indicate the new rightmost path.
3525 */
3532 {
3547 /* we meet with a cross extent block merge. */
3552 }
3565 right_path);
3569 left_path);
3573 }
3579 subtree_index);
3583 }
3592 }
3599 }
3600 }
3605 }
3612 }
3615 /*
3616 * The easy case - we can just plop the record right in.
3617 */
3627 split_clusters));
3636 /*
3637 * In the situation that the right_rec is empty and the extent
3638 * block is empty also, ocfs2_complete_edge_insert can't handle
3639 * it and we need to delete the right extent block.
3640 */
3645 right_path,
3646 dealloc);
3650 }
3652 /* Now the rightmost extent block has been deleted.
3653 * So we use the new rightmost path.
3654 */
3660 }
3661 out:
3665 }
3674 {
3682 /*
3683 * The merge code will need to create an empty
3684 * extent to take the place of the newly
3685 * emptied slot. Remove any pre-existing empty
3686 * extents - having more than one in a leaf is
3687 * illegal.
3688 */
3693 }
3694 split_index--;
3696 }
3699 /*
3700 * Left-right contig implies this.
3701 */
3704 /*
3705 * Since the leftright insert always covers the entire
3706 * extent, this call will delete the insert record
3707 * entirely, resulting in an empty extent record added to
3708 * the extent block.
3709 *
3710 * Since the adding of an empty extent shifts
3711 * everything back to the right, there's no need to
3712 * update split_index here.
3713 *
3714 * When the split_index is zero, we need to merge it to the
3715 * prevoius extent block. It is more efficient and easier
3716 * if we do merge_right first and merge_left later.
3717 */
3719 split_index);
3723 }
3725 /*
3726 * We can only get this from logic error above.
3727 */
3730 /* The merge left us with an empty extent, remove it. */
3735 }
3739 /*
3740 * Note that we don't pass split_rec here on purpose -
3741 * we've merged it into the rec already.
3742 */
3749 }
3752 /*
3753 * Error from this last rotate is not critical, so
3754 * print but don't bubble it up.
3755 */
3760 /*
3761 * Merge a record to the left or right.
3762 *
3763 * 'contig_type' is relative to the existing record,
3764 * so for example, if we're "right contig", it's to
3765 * the record on the left (hence the left merge).
3766 */
3770 split_index);
3774 }
3778 split_index);
3782 }
3783 }
3786 /*
3787 * The merge may have left an empty extent in
3788 * our leaf. Try to rotate it away.
3789 */
3791 dealloc);
3795 }
3796 }
3798 out:
3800 }
3806 {
3807 u64 len_blocks;
3813 /*
3814 * Region is on the left edge of the existing
3815 * record.
3816 */
3823 /*
3824 * Region is on the right edge of the existing
3825 * record.
3826 */
3829 }
3830 }
3832 /*
3833 * Do the final bits of extent record insertion at the target leaf
3834 * list. If this leaf is part of an allocation tree, it is assumed
3835 * that the tree above has been prepared.
3836 */
3841 {
3854 insert_rec);
3856 }
3858 /*
3859 * Contiguous insert - either left or right.
3860 */
3866 }
3870 }
3872 /*
3873 * Handle insert into an empty leaf.
3874 */
3881 }
3883 /*
3884 * Appending insert.
3885 */
3895 "owner %llu, depth %u, count %u, next free %u, "
3896 "rec.cpos %u, rec.clusters %u, "
3906 i++;
3910 }
3912 rotate:
3913 /*
3914 * Ok, we have to rotate.
3915 *
3916 * At this point, it is safe to assume that inserting into an
3917 * empty leaf and appending to a leaf have both been handled
3918 * above.
3919 *
3920 * This leaf needs to have space, either by the empty 1st
3921 * extent record, or by virtue of an l_next_rec < l_count.
3922 */
3924 }
3930 {
3936 /*
3937 * Update everything except the leaf block.
3938 */
3950 }
3961 }
3962 }
3969 {
3976 /*
3977 * This shouldn't happen for non-trees. The extent rec cluster
3978 * count manipulation below only works for interior nodes.
3979 */
3982 /*
3983 * If our appending insert is at the leftmost edge of a leaf,
3984 * then we might need to update the rightmost records of the
3985 * neighboring path.
3986 */
3991 u32 left_cpos;
3998 }
4002 left_cpos);
4004 /*
4005 * No need to worry if the append is already in the
4006 * leftmost leaf.
4007 */
4014 }
4017 left_cpos);
4021 }
4023 /*
4024 * ocfs2_insert_path() will pass the left_path to the
4025 * journal for us.
4026 */
4027 }
4028 }
4034 }
4040 out:
4045 }
4052 {
4069 /*
4070 * This typically means that the record
4071 * started in the left path but moved to the
4072 * right as a result of rotation. We either
4073 * move the existing record to the left, or we
4074 * do the later insert there.
4075 *
4076 * In this case, the left path should always
4077 * exist as the rotate code will have passed
4078 * it back for a post-insert update.
4079 */
4082 /*
4083 * It's a left split. Since we know
4084 * that the rotate code gave us an
4085 * empty extent in the left path, we
4086 * can just do the insert there.
4087 */
4090 /*
4091 * Right split - we have to move the
4092 * existing record over to the left
4093 * leaf. The insert will be into the
4094 * newly created empty extent in the
4095 * right leaf.
4096 */
4104 }
4105 }
4109 /*
4110 * Left path is easy - we can just allow the insert to
4111 * happen.
4112 */
4117 }
4123 }
4125 /*
4126 * This function only does inserts on an allocation b-tree. For tree
4127 * depth = 0, ocfs2_insert_at_leaf() is called directly.
4128 *
4129 * right_path is the path we want to do the actual insert
4130 * in. left_path should only be passed in if we need to update that
4131 * portion of the tree after an edge insert.
4132 */
4139 {
4146 /*
4147 * There's a chance that left_path got passed back to
4148 * us without being accounted for in the
4149 * journal. Extend our transaction here to be sure we
4150 * can change those blocks.
4151 */
4158 }
4164 }
4165 }
4167 /*
4168 * Pass both paths to the journal. The majority of inserts
4169 * will be touching all components anyway.
4170 */
4175 }
4178 /*
4179 * We could call ocfs2_insert_at_leaf() for some types
4180 * of splits, but it's easier to just let one separate
4181 * function sort it all out.
4182 */
4186 /*
4187 * Split might have modified either leaf and we don't
4188 * have a guarantee that the later edge insert will
4189 * dirty this for us.
4190 */
4196 insert);
4201 /*
4202 * The rotate code has indicated that we need to fix
4203 * up portions of the tree after the insert.
4204 *
4205 * XXX: Should we extend the transaction here?
4206 */
4208 right_path);
4210 subtree_index);
4211 }
4214 out:
4216 }
4222 {
4224 u32 cpos;
4232 OCFS2_JOURNAL_ACCESS_WRITE);
4236 }
4241 }
4248 }
4250 /*
4251 * Determine the path to start with. Rotations need the
4252 * rightmost path, everything else can go directly to the
4253 * target leaf.
4254 */
4260 }
4266 }
4268 /*
4269 * Rotations and appends need special treatment - they modify
4270 * parts of the tree's above them.
4271 *
4272 * Both might pass back a path immediate to the left of the
4273 * one being inserted to. This will be cause
4274 * ocfs2_insert_path() to modify the rightmost records of
4275 * left_path to account for an edge insert.
4276 *
4277 * XXX: When modifying this code, keep in mind that an insert
4278 * can wind up skipping both of these two special cases...
4279 */
4287 }
4289 /*
4290 * ocfs2_rotate_tree_right() might have extended the
4291 * transaction without re-journaling our tree root.
4292 */
4294 OCFS2_JOURNAL_ACCESS_WRITE);
4298 }
4306 }
4307 }
4314 }
4316 out_update_clusters:
4323 out:
4328 }
4330 static enum ocfs2_contig_type
4335 {
4359 left_cpos);
4370 "Extent block #%llu has an "
4371 "invalid l_next_free_rec of "
4372 "%d. It should have "
4379 }
4382 }
4383 }
4385 /*
4386 * We're careful to check for an empty extent record here -
4387 * the merge code will know what to do if it sees one.
4388 */
4395 }
4396 }
4425 "Extent block #%llu has an "
4431 }
4433 }
4434 }
4445 }
4447 out:
4454 }
4460 {
4468 insert_rec);
4472 }
4473 }
4482 /*
4483 * Caller might want us to limit the size of extents, don't
4484 * calculate contiguousness if we might exceed that limit.
4485 */
4489 }
4490 }
4492 /*
4493 * This should only be called against the righmost leaf extent list.
4494 *
4495 * ocfs2_figure_appending_type() will figure out whether we'll have to
4496 * insert at the tail of the rightmost leaf.
4497 *
4498 * This should also work against the root extent list for tree's with 0
4499 * depth. If we consider the root extent list to be the rightmost leaf node
4500 * then the logic here makes sense.
4501 */
4505 {
4518 /* Were all records empty? */
4521 }
4532 set_tail_append:
4534 }
4536 /*
4537 * Helper function called at the begining of an insert.
4538 *
4539 * This computes a few things that are commonly used in the process of
4540 * inserting into the btree:
4541 * - Whether the new extent is contiguous with an existing one.
4542 * - The current tree depth.
4543 * - Whether the insert is an appending one.
4544 * - The total # of free records in the tree.
4545 *
4546 * All of the information is stored on the ocfs2_insert_type
4547 * structure.
4548 */
4554 {
4567 /*
4568 * If we have tree depth, we read in the
4569 * rightmost extent block ahead of time as
4570 * ocfs2_figure_insert_type() and ocfs2_add_branch()
4571 * may want it later.
4572 */
4579 }
4582 }
4584 /*
4585 * Unless we have a contiguous insert, we'll need to know if
4586 * there is room left in our allocation tree for another
4587 * extent record.
4588 *
4589 * XXX: This test is simplistic, we can search for empty
4590 * extent records too.
4591 */
4599 }
4606 }
4608 /*
4609 * In the case that we're inserting past what the tree
4610 * currently accounts for, ocfs2_find_path() will return for
4611 * us the rightmost tree path. This is accounted for below in
4612 * the appending code.
4613 */
4618 }
4622 /*
4623 * Now that we have the path, there's two things we want to determine:
4624 * 1) Contiguousness (also set contig_index if this is so)
4625 *
4626 * 2) Are we doing an append? We can trivially break this up
4627 * into two types of appends: simple record append, or a
4628 * rotate inside the tail leaf.
4629 */
4632 /*
4633 * The insert code isn't quite ready to deal with all cases of
4634 * left contiguousness. Specifically, if it's an insert into
4635 * the 1st record in a leaf, it will require the adjustment of
4636 * cluster count on the last record of the path directly to it's
4637 * left. For now, just catch that case and fool the layers
4638 * above us. This works just fine for tree_depth == 0, which
4639 * is why we allow that above.
4640 */
4645 /*
4646 * Ok, so we can simply compare against last_eb to figure out
4647 * whether the path doesn't exist. This will only happen in
4648 * the case that we're doing a tail append, so maybe we can
4649 * take advantage of that information somehow.
4650 */
4653 /*
4654 * Ok, ocfs2_find_path() returned us the rightmost
4655 * tree path. This might be an appending insert. There are
4656 * two cases:
4657 * 1) We're doing a true append at the tail:
4658 * -This might even be off the end of the leaf
4659 * 2) We're "appending" by rotating in the tail
4660 */
4662 }
4664 out:
4669 else
4672 }
4674 /*
4675 * Insert an extent into a btree.
4676 *
4677 * The caller needs to update the owning btree's cluster count.
4678 */
4681 u32 cpos,
4682 u64 start_blk,
4683 u32 new_clusters,
4684 u8 flags,
4686 {
4706 }
4713 }
4716 "Insert.contig_index: %d, Insert.free_records: %d, "
4724 meta_ac);
4728 }
4729 }
4731 /* Finally, we can add clusters. This might rotate the tree for us. */
4735 else
4738 bail:
4743 }
4745 /*
4746 * Allcate and add clusters into the extent b-tree.
4747 * The new clusters(clusters_to_add) will be inserted at logical_offset.
4748 * The extent b-tree's root is specified by et, and
4749 * it is not limited to the file storage. Any extent tree can use this
4750 * function if it implements the proper ocfs2_extent_tree.
4751 */
4755 u32 clusters_to_add,
4760 {
4765 u64 block;
4780 }
4782 /* there are two cases which could cause us to EAGAIN in the
4783 * we-need-more-metadata case:
4784 * 1) we haven't reserved *any*
4785 * 2) we are so fragmented, we've needed to add metadata too
4786 * many times. */
4799 }
4807 }
4811 /* reserve our write early -- insert_extent may update the tree root */
4813 OCFS2_JOURNAL_ACCESS_WRITE);
4817 }
4828 }
4837 clusters_to_add);
4840 }
4842 leave:
4847 }
4851 u32 cpos,
4853 {
4867 }
4876 {
4886 leftright:
4887 /*
4888 * Store a copy of the record on the stack - it might move
4889 * around as the tree is manipulated below.
4890 */
4900 }
4909 }
4910 }
4927 /*
4928 * Left/right split. We fake this as a right split
4929 * first and then make a second pass as a left split.
4930 */
4940 }
4946 }
4949 u32 cpos;
4952 do_leftright++;
4962 }
4967 }
4968 out:
4971 }
4979 {
4987 }
4992 out:
4994 }
4996 /*
4997 * Split part or all of the extent record at split_index in the leaf
4998 * pointed to by path. Merge with the contiguous extent record if needed.
4999 *
5000 * Care is taken to handle contiguousness so as to not grow the tree.
5001 *
5002 * meta_ac is not strictly necessary - we only truly need it if growth
5003 * of the tree is required. All other cases will degrade into a less
5004 * optimal tree layout.
5005 *
5006 * last_eb_bh should be the rightmost leaf block for any extent
5007 * btree. Since a split may grow the tree or a merge might shrink it,
5008 * the caller cannot trust the contents of that buffer after this call.
5009 *
5010 * This code is optimized for readability - several passes might be
5011 * made over certain portions of the tree. All of those blocks will
5012 * have been brought into cache (and pinned via the journal), so the
5013 * extra overhead is not expressed in terms of disk reads.
5014 */
5022 {
5036 }
5039 split_index,
5040 split_rec);
5042 /*
5043 * The core merge / split code wants to know how much room is
5044 * left in this allocation tree, so we pass the
5045 * rightmost extent list.
5046 */
5056 }
5066 else
5079 else
5091 }
5093 out:
5096 }
5098 /*
5099 * Change the flags of the already-existing extent at cpos for len clusters.
5100 *
5101 * new_flags: the flags we want to set.
5102 * clear_flags: the flags we want to clear.
5103 * phys: the new physical offset we want this new extent starts from.
5104 *
5105 * If the existing extent is larger than the request, initiate a
5106 * split. An attempt will be made at merging with adjacent extents.
5107 *
5108 * The caller is responsible for passing down meta_ac if we'll need it.
5109 */
5116 {
5130 }
5136 }
5142 "Owner %llu has an extent at cpos %u which can no "
5148 }
5156 new_flags);
5158 }
5164 clear_flags);
5166 }
5180 dealloc);
5184 out:
5188 }
5190 /*
5191 * Mark the already-existing extent at cpos as written for len clusters.
5192 * This removes the unwritten extent flag.
5193 *
5194 * If the existing extent is larger than the request, initiate a
5195 * split. An attempt will be made at merging with adjacent extents.
5196 *
5197 * The caller is responsible for passing down meta_ac if we'll need it.
5198 */
5204 {
5212 "that are being written to, but the feature bit "
5217 }
5219 /*
5220 * XXX: This should be fixed up so that we just re-insert the
5221 * next extent records.
5222 */
5231 out:
5233 }
5239 {
5248 /*
5249 * Setup the record to split before we grow the tree.
5250 */
5264 }
5277 }
5282 meta_ac);
5286 }
5287 }
5299 out:
5302 }
5309 {
5324 }
5326 index--;
5327 }
5331 /*
5332 * Check whether this is the rightmost tree record. If
5333 * we remove all of this record or part of its right
5334 * edge then an update of the record lengths above it
5335 * will be required.
5336 */
5340 }
5345 /*
5346 * Changing the leftmost offset (via partial or whole
5347 * record truncate) of an interior (or rightmost) path
5348 * means we have to update the subtree that is formed
5349 * by this leaf and the one to it's left.
5350 *
5351 * There are two cases we can skip:
5352 * 1) Path is the leftmost one in our btree.
5353 * 2) The leaf is rightmost and will be empty after
5354 * we remove the extent record - the rotate code
5355 * knows how to update the newly formed edge.
5356 */
5362 }
5370 }
5373 left_cpos);
5377 }
5378 }
5379 }
5383 path);
5387 }
5393 }
5399 }
5413 /*
5414 * We skip the edge update if this path will
5415 * be deleted by the rotate code.
5416 */
5419 rec);
5420 }
5422 /* Remove leftmost portion of the record. */
5427 /* Remove rightmost portion of the record */
5432 /* Caller should have trapped this. */
5439 }
5446 subtree_index);
5447 }
5455 }
5457 out:
5460 }
5467 {
5474 /*
5475 * XXX: Why are we truncating to 0 instead of wherever this
5476 * affects us?
5477 */
5485 }
5491 }
5497 "Owner %llu has an extent at cpos %u which can no "
5500 cpos);
5503 }
5505 /*
5506 * We have 3 cases of extent removal:
5507 * 1) Range covers the entire extent rec
5508 * 2) Range begins or ends on one edge of the extent rec
5509 * 3) Range is in the middle of the extent rec (no shared edges)
5510 *
5511 * For case 1 we remove the extent rec and left rotate to
5512 * fill the hole.
5513 *
5514 * For case 2 we just shrink the existing extent rec, with a
5515 * tree update if the shrinking edge is also the edge of an
5516 * extent block.
5517 *
5518 * For case 3 we do a right split to turn the extent rec into
5519 * something case 2 can handle.
5520 */
5539 }
5546 }
5548 /*
5549 * The split could have manipulated the tree enough to
5550 * move the record location, so we have to look for it again.
5551 */
5558 }
5566 cpos);
5569 }
5571 /*
5572 * Double check our values here. If anything is fishy,
5573 * it's easier to catch it at the top level.
5574 */
5580 "Owner %llu: error after split at cpos %u"
5587 }
5594 }
5595 }
5597 out:
5600 }
5606 {
5618 }
5627 }
5628 }
5635 }
5638 OCFS2_JOURNAL_ACCESS_WRITE);
5642 }
5651 }
5661 out_commit:
5663 out:
5670 }
5673 {
5682 "slot %d, invalid truncate log parameters: used = "
5686 }
5690 {
5694 /* No records, nothing to coalesce */
5703 }
5707 u64 start_blk,
5709 {
5726 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5727 * by the underlying call to ocfs2_read_inode_block(), so any
5728 * corruption is a code bug */
5735 "Truncate record count on #%llu invalid "
5741 /* Caller should have known to flush before calling us. */
5747 }
5750 OCFS2_JOURNAL_ACCESS_WRITE);
5754 }
5761 /*
5762 * Move index back to the record we are coalescing with.
5763 * ocfs2_truncate_log_can_coalesce() guarantees nonzero
5764 */
5765 index--;
5770 num_clusters);
5774 }
5779 bail:
5782 }
5788 {
5792 u64 start_blk;
5805 /* Caller has given us at least enough credits to
5806 * update the truncate log dinode */
5808 OCFS2_JOURNAL_ACCESS_WRITE);
5812 }
5818 /* TODO: Perhaps we can calculate the bulk of the
5819 * credits up front rather than extending like
5820 * this. */
5822 OCFS2_TRUNCATE_LOG_FLUSH_ONE_REC);
5826 }
5833 /* if start_blk is not set, we ignore the record as
5834 * invalid. */
5841 num_clusters);
5845 }
5846 }
5847 i--;
5848 }
5850 bail:
5853 }
5855 /* Expects you to already be holding tl_inode->i_mutex */
5857 {
5874 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5875 * by the underlying call to ocfs2_read_inode_block(), so any
5876 * corruption is a code bug */
5886 }
5889 GLOBAL_BITMAP_SYSTEM_INODE,
5890 OCFS2_INVALID_SLOT);
5895 }
5903 }
5910 }
5913 data_alloc_bh);
5919 out_unlock:
5923 out_mutex:
5927 out:
5930 }
5933 {
5942 }
5945 {
5956 else
5960 }
5962 #define OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL (2 * HZ)
5965 {
5967 /* We want to push off log flushes while truncates are
5968 * still running. */
5973 OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL);
5974 }
5975 }
5981 {
5987 TRUNCATE_LOG_SYSTEM_INODE,
5988 slot_num);
5993 }
6000 }
6004 bail:
6007 }
6009 /* called during the 1st stage of node recovery. we stamp a clean
6010 * truncate log and pass back a copy for processing later. if the
6011 * truncate log does not require processing, a *tl_copy is set to
6012 * NULL. */
6016 {
6031 }
6035 /* tl_bh is loaded from ocfs2_get_truncate_log_info(). It's
6036 * validated by the underlying call to ocfs2_read_inode_block(),
6037 * so any corruption is a code bug */
6050 }
6052 /* Assuming the write-out below goes well, this copy
6053 * will be passed back to recovery for processing. */
6056 /* All we need to do to clear the truncate log is set
6057 * tl_used. */
6065 }
6066 }
6068 bail:
6076 }
6080 }
6084 {
6088 u64 start_blk;
6098 }
6112 }
6113 }
6120 }
6132 }
6133 }
6135 bail_up:
6140 }
6143 {
6159 }
6162 }
6165 {
6179 /* ocfs2_truncate_log_shutdown keys on the existence of
6180 * osb->osb_tl_inode so we don't set any of the osb variables
6181 * until we're sure all is well. */
6183 ocfs2_truncate_log_worker);
6189 }
6191 /*
6192 * Delayed de-allocation of suballocator blocks.
6193 *
6194 * Some sets of block de-allocations might involve multiple suballocator inodes.
6195 *
6196 * The locking for this can get extremely complicated, especially when
6197 * the suballocator inodes to delete from aren't known until deep
6198 * within an unrelated codepath.
6199 *
6200 * ocfs2_extent_block structures are a good example of this - an inode
6201 * btree could have been grown by any number of nodes each allocating
6202 * out of their own suballoc inode.
6203 *
6204 * These structures allow the delay of block de-allocation until a
6205 * later time, when locking of multiple cluster inodes won't cause
6206 * deadlock.
6207 */
6209 /*
6210 * Describe a single bit freed from a suballocator. For the block
6211 * suballocators, it represents one block. For the global cluster
6212 * allocator, it represents some clusters and free_bit indicates
6213 * clusters number.
6214 */
6217 u64 free_blk;
6219 };
6226 };
6232 {
6234 u64 bg_blkno;
6245 }
6253 }
6260 }
6273 }
6279 }
6284 }
6286 out_journal:
6289 out_unlock:
6292 out_mutex:
6295 out:
6297 /* Premature exit may have left some dangling items. */
6301 }
6304 }
6308 {
6317 }
6328 }
6332 {
6346 }
6347 }
6354 }
6367 }
6368 }
6373 /* Premature exit may have left some dangling items. */
6377 }
6380 }
6384 {
6405 }
6409 }
6420 }
6423 }
6429 {
6437 }
6447 }
6449 }
6454 {
6464 }
6471 }
6483 out:
6485 }
6489 {
6494 }
6496 /* This function will figure out whether the currently last extent
6497 * block will be deleted, and if it will, what the new last extent
6498 * block will be so we can update his h_next_leaf_blk field, as well
6499 * as the dinodes i_last_eb_blk */
6504 {
6506 u32 cpos;
6514 /* we have no tree, so of course, no last_eb. */
6518 /* trunc to zero special case - this makes tree_depth = 0
6519 * regardless of what it is. */
6526 /*
6527 * Make sure that this extent list will actually be empty
6528 * after we clear away the data. We can shortcut out if
6529 * there's more than one non-empty extent in the
6530 * list. Otherwise, a check of the remaining extent is
6531 * necessary.
6532 */
6539 /* We may have a valid extent in index 1, check it. */
6543 /*
6544 * Fall through - no more nonempty extents, so we want
6545 * to delete this leaf.
6546 */
6552 }
6555 /*
6556 * Check it we'll only be trimming off the end of this
6557 * cluster.
6558 */
6561 }
6567 }
6573 }
6578 /* ocfs2_find_leaf() gets the eb from ocfs2_read_extent_block().
6579 * Any corruption is a code bug. */
6586 out:
6590 }
6592 /*
6593 * Trim some clusters off the rightmost edge of a tree. Only called
6594 * during truncate.
6595 *
6596 * The caller needs to:
6597 * - start journaling of each path component.
6598 * - compute and fully set up any new last ext block
6599 */
6603 {
6631 }
6633 find_tail_record:
6646 /*
6647 * If the leaf block contains a single empty
6648 * extent and no records, we can just remove
6649 * the block.
6650 */
6657 }
6659 /*
6660 * Remove any empty extents by shifting things
6661 * left. That should make life much easier on
6662 * the code below. This condition is rare
6663 * enough that we shouldn't see a performance
6664 * hit.
6665 */
6676 /*
6677 * We've modified our extent list. The
6678 * simplest way to handle this change
6679 * is to being the search from the
6680 * start again.
6681 */
6683 }
6687 /*
6688 * We'll use "new_edge" on our way back up the
6689 * tree to know what our rightmost cpos is.
6690 */
6694 /*
6695 * The caller will use this to delete data blocks.
6696 */
6702 /*
6703 * If it's now empty, remove this record.
6704 */
6709 }
6717 }
6719 /* Can this actually happen? */
6723 /*
6724 * We never actually deleted any clusters
6725 * because our leaf was empty. There's no
6726 * reason to adjust the rightmost edge then.
6727 */
6735 /*
6736 * A deleted child record should have been
6737 * caught above.
6738 */
6740 }
6752 /*
6753 * We must be careful to only attempt delete of an
6754 * extent block (and not the root inode block).
6755 */
6760 /*
6761 * Save this for use when processing the
6762 * parent block.
6763 */
6775 /* An error here is not fatal. */
6780 }
6782 index--;
6783 }
6786 out:
6788 }
6798 {
6805 u8 rec_flags;
6814 }
6816 /*
6817 * Each component will be touched, so we might as well journal
6818 * here to avoid having to handle errors later.
6819 */
6824 }
6828 OCFS2_JOURNAL_ACCESS_WRITE);
6832 }
6835 }
6839 /*
6840 * Lower levels depend on this never happening, but it's best
6841 * to check it up here before changing the tree.
6842 */
6849 }
6855 clusters_to_del;
6865 }
6868 /* trunc to zero is a special case. */
6877 /* If there will be a new last extent block, then by
6878 * definition, there cannot be any leaves to the right of
6879 * him. */
6882 }
6888 delete_blk),
6891 else
6893 delete_blk,
6894 clusters_to_del);
6898 }
6899 }
6901 bail:
6905 }
6908 {
6912 }
6917 {
6927 /*
6928 * Need to set the buffers we zero'd into uptodate
6929 * here if they aren't - ocfs2_map_page_blocks()
6930 * might've skipped some
6931 */
6934 ocfs2_zero_func);
6941 }
6947 }
6952 {
6978 }
6979 out:
6982 }
6986 {
6990 loff_t last_page_bytes;
7003 }
7005 numpages++;
7006 index++;
7009 out:
7014 }
7019 }
7023 {
7030 }
7032 /*
7033 * Zero the area past i_size but still within an allocated
7034 * cluster. This avoids exposing nonzero data on subsequent file
7035 * extends.
7036 *
7037 * We need to call this before i_size is updated on the inode because
7038 * otherwise block_write_full_page() will skip writeout of pages past
7039 * i_size. The new_i_size parameter is passed for this reason.
7040 */
7043 {
7046 u64 phys;
7050 /*
7051 * File systems which don't support sparse files zero on every
7052 * extend.
7053 */
7063 }
7074 }
7076 /*
7077 * Tail is a hole, or is marked unwritten. In either case, we
7078 * can count on read and write to return/push zero's.
7079 */
7088 }
7093 /*
7094 * Initiate writeout of the pages we zero'd here. We don't
7095 * wait on them - the truncate_inode_pages() call later will
7096 * do that for us.
7097 */
7103 out:
7108 }
7112 {
7119 xattrsize);
7120 else
7123 }
7127 {
7133 }
7136 {
7145 /*
7146 * We clear the entire i_data structure here so that all
7147 * fields can be properly initialized.
7148 */
7153 }
7157 {
7179 }
7185 }
7186 }
7194 }
7197 OCFS2_JOURNAL_ACCESS_WRITE);
7201 }
7206 u64 phys;
7221 }
7223 /*
7224 * Save two copies, one for insert, and one that can
7225 * be changed by ocfs2_map_and_dirty_page() below.
7226 */
7229 /*
7230 * Non sparse file systems zero on extend, so no need
7231 * to do that now.
7232 */
7241 }
7243 /*
7244 * This should populate the 1st page for us and mark
7245 * it up to date.
7246 */
7251 }
7260 }
7272 /*
7273 * An error at this point should be extremely rare. If
7274 * this proves to be false, we could always re-build
7275 * the in-inode data from our pages.
7276 */
7282 }
7285 }
7287 out_commit:
7294 out_unlock:
7298 out:
7302 }
7305 }
7307 /*
7308 * It is expected, that by the time you call this function,
7309 * inode->i_size and fe->i_size have been adjusted.
7310 *
7311 * WARNING: This will kfree the truncate context
7312 */
7317 {
7335 ocfs2_journal_access_di);
7340 }
7344 start:
7345 /*
7346 * Check that we still have allocation to delete.
7347 */
7351 }
7355 /*
7356 * Truncate always works against the rightmost tree branch.
7357 */
7362 }
7367 /*
7368 * By now, el will point to the extent list on the bottom most
7369 * portion of this tree. Only the tail record is considered in
7370 * each pass.
7371 *
7372 * We handle the following cases, in order:
7373 * - empty extent: delete the remaining branch
7374 * - remove the entire record
7375 * - remove a partial record
7376 * - no record needs to be removed (truncate has completed)
7377 */
7386 }
7399 new_highest_cpos;
7403 clusters_to_del);
7407 }
7414 OCFS2_HAS_REFCOUNT_FL));
7422 }
7425 blkno,
7426 clusters_to_del,
7432 }
7433 }
7437 /* ocfs2_truncate_log_needs_flush guarantees us at least one
7438 * record is free for use. If there isn't any, we flush to get
7439 * an empty truncate log. */
7445 }
7446 }
7450 el);
7457 }
7464 }
7477 }
7482 }
7484 /*
7485 * The check above will catch the case where we've truncated
7486 * away all allocation.
7487 */
7490 bail:
7510 /* This will drop the ext_alloc cluster lock for us */
7515 }
7517 /*
7518 * Expects the inode to already be locked.
7519 */
7524 {
7548 }
7558 }
7560 }
7565 bail:
7570 }
7573 }
7575 /*
7576 * 'start' is inclusive, 'end' is not.
7577 */
7580 {
7597 "Inline data flags for inode %llu don't agree! "
7605 }
7612 }
7615 OCFS2_JOURNAL_ACCESS_WRITE);
7619 }
7624 /*
7625 * No need to worry about the data page here - it's been
7626 * truncated already and inline data doesn't need it for
7627 * pushing zero's to disk, so we'll let readpage pick it up
7628 * later.
7629 */
7633 }
7643 out_commit:
7646 out:
7648 }
7651 {
7652 /*
7653 * The caller is responsible for completing deallocation
7654 * before freeing the context.
7655 */
7663 }