| blob | e4984e259cb6b9eec82ed22ae376e51fad986029 |
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 }
574 /*
575 * Reset the actual path elements so that we can re-use the structure
576 * to build another path. Generally, this involves freeing the buffer
577 * heads.
578 */
580 {
593 }
595 /*
596 * Tree depth may change during truncate, or insert. If we're
597 * keeping the root extent list, then make sure that our path
598 * structure reflects the proper depth.
599 */
602 else
606 }
609 {
613 }
614 }
616 /*
617 * All the elements of src into dest. After this call, src could be freed
618 * without affecting dest.
619 *
620 * Both paths should have the same root. Any non-root elements of dest
621 * will be freed.
622 */
624 {
639 }
640 }
642 /*
643 * Make the *dest path the same as src and re-initialize src path to
644 * have a root only.
645 */
647 {
661 }
662 }
664 /*
665 * Insert an extent block at given index.
666 *
667 * This will not take an additional reference on eb_bh.
668 */
671 {
674 /*
675 * Right now, no root bh is an extent block, so this helps
676 * catch code errors with dinode trees. The assertion can be
677 * safely removed if we ever need to insert extent block
678 * structures at the root.
679 */
684 }
688 ocfs2_journal_access_func access)
689 {
701 }
704 }
707 {
710 }
713 {
716 }
718 /*
719 * Journal the buffer at depth idx. All idx>0 are extent_blocks,
720 * otherwise it's the root_access function.
721 *
722 * I don't like the way this function's name looks next to
723 * ocfs2_journal_access_path(), but I don't have a better one.
724 */
729 {
739 OCFS2_JOURNAL_ACCESS_WRITE);
740 }
742 /*
743 * Convenience function to journal all components in a path.
744 */
748 {
759 }
760 }
762 out:
764 }
766 /*
767 * Return the index of the extent record which contains cluster #v_cluster.
768 * -1 is returned if it was not found.
769 *
770 * Should work fine on interior and exterior nodes.
771 */
773 {
790 }
791 }
794 }
796 /*
797 * NOTE: ocfs2_block_extent_contig(), ocfs2_extents_adjacent() and
798 * ocfs2_extent_rec_contig only work properly against leaf nodes!
799 */
802 u64 blkno)
803 {
810 }
814 {
815 u32 left_range;
821 }
823 static enum ocfs2_contig_type
827 {
830 /*
831 * Refuse to coalesce extent records with different flag
832 * fields - we don't want to mix unwritten extents with user
833 * data.
834 */
848 }
850 /*
851 * NOTE: We can have pretty much any combination of contiguousness and
852 * appending.
853 *
854 * The usefulness of APPEND_TAIL is more in that it lets us know that
855 * we'll have to update the path to that leaf.
856 */
859 APPEND_TAIL,
860 };
864 SPLIT_LEFT,
865 SPLIT_RIGHT,
866 };
874 };
880 };
884 {
894 /*
895 * If the ecc fails, we return the error but otherwise
896 * leave the filesystem running. We know any error is
897 * local to this block.
898 */
904 }
906 /*
907 * Errors after here are fatal.
908 */
916 }
920 "Extent block #%llu has an invalid h_blkno "
925 }
929 "Extent block #%llu has an invalid "
934 }
937 }
941 {
946 ocfs2_validate_extent_block);
948 /* If ocfs2_read_block() got us a new bh, pass it up. */
953 }
956 /*
957 * How many free extents have we got before we need more meta data?
958 */
961 {
979 }
982 }
987 bail:
992 }
994 /* expects array to already be allocated
995 *
996 * sets h_signature, h_blkno, h_suballoc_bit, h_suballoc_slot, and
997 * l_count for you
998 */
1004 {
1006 u16 suballoc_bit_start;
1007 u32 num_got;
1018 meta_ac,
1027 }
1035 }
1040 OCFS2_JOURNAL_ACCESS_CREATE);
1044 }
1048 /* 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 }
1132 }
1138 }
1145 out:
1148 }
1150 /*
1151 * Add an entire tree branch to our inode. eb_bh is the extent block
1152 * to start at, if we don't want to start the branch at the root
1153 * structure.
1154 *
1155 * last_eb_bh is required as we have to update it's next_leaf pointer
1156 * for the new last extent block.
1157 *
1158 * the new branch will be 'empty' in the sense that every block will
1159 * contain a single record with cluster count == 0.
1160 */
1166 {
1186 /* we never add a branch to a leaf. */
1195 /*
1196 * If there is a gap before the root end and the real end
1197 * of the righmost leaf block, we need to remove the gap
1198 * between new_cpos and root_end first so that the tree
1199 * is consistent after we add a new branch(it will start
1200 * from new_cpos).
1201 */
1209 }
1210 }
1212 /* allocate the number of new eb blocks we need */
1214 GFP_KERNEL);
1219 }
1226 }
1228 /* Note: new_eb_bhs[new_blocks - 1] is the guy which will be
1229 * linked with the rest of the tree.
1230 * conversly, new_eb_bhs[0] is the new bottommost leaf.
1231 *
1232 * when we leave the loop, new_last_eb_blk will point to the
1233 * newest leaf, and next_blkno will point to the topmost extent
1234 * block. */
1239 /* ocfs2_create_new_meta_bhs() should create it right! */
1244 OCFS2_JOURNAL_ACCESS_CREATE);
1248 }
1253 /*
1254 * This actually counts as an empty extent as
1255 * c_clusters == 0
1256 */
1259 /*
1260 * eb_el isn't always an interior node, but even leaf
1261 * nodes want a zero'd flags and reserved field so
1262 * this gets the whole 32 bits regardless of use.
1263 */
1270 }
1272 /* This is a bit hairy. We want to update up to three blocks
1273 * here without leaving any of them in an inconsistent state
1274 * in case of error. We don't have to worry about
1275 * journal_dirty erroring as it won't unless we've aborted the
1276 * handle (in which case we would never be here) so reserving
1277 * the write with journal_access is all we need to do. */
1279 OCFS2_JOURNAL_ACCESS_WRITE);
1283 }
1285 OCFS2_JOURNAL_ACCESS_WRITE);
1289 }
1292 OCFS2_JOURNAL_ACCESS_WRITE);
1296 }
1297 }
1299 /* Link the new branch into the rest of the tree (el will
1300 * either be on the root_bh, or the extent block passed in. */
1307 /* fe needs a new last extent block pointer, as does the
1308 * next_leaf on the previously last-extent-block. */
1319 /*
1320 * Some callers want to track the rightmost leaf so pass it
1321 * back here.
1322 */
1328 bail:
1333 }
1337 }
1339 /*
1340 * adds another level to the allocation tree.
1341 * returns back the new extent block so you can add a branch to it
1342 * after this call.
1343 */
1348 {
1350 u32 new_clusters;
1363 }
1366 /* ocfs2_create_new_meta_bhs() should create it right! */
1373 OCFS2_JOURNAL_ACCESS_CREATE);
1377 }
1379 /* copy the root extent list data into the new extent block */
1388 OCFS2_JOURNAL_ACCESS_WRITE);
1392 }
1396 /* update root_bh now */
1405 /* If this is our 1st tree depth shift, then last_eb_blk
1406 * becomes the allocated extent block */
1415 bail:
1420 }
1422 /*
1423 * Should only be called when there is no space left in any of the
1424 * leaf nodes. What we want to do is find the lowest tree depth
1425 * non-leaf extent block with room for new records. There are three
1426 * valid results of this search:
1427 *
1428 * 1) a lowest extent block is found, then we pass it back in
1429 * *lowest_eb_bh and return '0'
1430 *
1431 * 2) the search fails to find anything, but the root_el has room. We
1432 * pass NULL back in *lowest_eb_bh, but still return '0'
1433 *
1434 * 3) the search fails to find anything AND the root_el is full, in
1435 * which case we return > 0
1436 *
1437 * return status < 0 indicates an error.
1438 */
1441 {
1443 u64 blkno;
1458 "Owner %llu has empty "
1463 }
1468 "Owner %llu has extent "
1469 "list where extent # %d has no physical "
1474 }
1483 }
1493 }
1494 }
1496 /* If we didn't find one and the fe doesn't have any room,
1497 * then return '1' */
1503 bail:
1508 }
1510 /*
1511 * Grow a b-tree so that it has more records.
1512 *
1513 * We might shift the tree depth in which case existing paths should
1514 * be considered invalid.
1515 *
1516 * Tree depth after the grow is returned via *final_depth.
1517 *
1518 * *last_eb_bh will be updated by ocfs2_add_branch().
1519 */
1523 {
1536 }
1538 /* We traveled all the way to the bottom of the allocation tree
1539 * and didn't find room for any more extents - we need to add
1540 * another tree level */
1545 /* ocfs2_shift_tree_depth will return us a buffer with
1546 * the new extent block (so we can pass that to
1547 * ocfs2_add_branch). */
1552 }
1553 depth++;
1555 /*
1556 * Special case: we have room now if we shifted from
1557 * tree_depth 0, so no more work needs to be done.
1558 *
1559 * We won't be calling add_branch, so pass
1560 * back *last_eb_bh as the new leaf. At depth
1561 * zero, it should always be null so there's
1562 * no reason to brelse.
1563 */
1568 }
1569 }
1571 /* call ocfs2_add_branch to add the final part of the tree with
1572 * the new data. */
1575 meta_ac);
1579 }
1581 out:
1586 }
1588 /*
1589 * This function will discard the rightmost extent record.
1590 */
1592 {
1598 /* This will cause us to go off the end of our extent list. */
1604 }
1608 {
1618 /* The tree code before us didn't allow enough room in the leaf. */
1621 /*
1622 * The easiest way to approach this is to just remove the
1623 * empty extent and temporarily decrement next_free.
1624 */
1626 /*
1627 * If next_free was 1 (only an empty extent), this
1628 * loop won't execute, which is fine. We still want
1629 * the decrement above to happen.
1630 */
1634 next_free--;
1635 }
1637 /*
1638 * Figure out what the new record index should be.
1639 */
1645 }
1655 /*
1656 * No need to memmove if we're just adding to the tail.
1657 */
1665 num_bytes);
1666 }
1668 /*
1669 * Either we had an empty extent, and need to re-increment or
1670 * there was no empty extent on a non full rightmost leaf node,
1671 * in which case we still need to increment.
1672 */
1673 next_free++;
1675 /*
1676 * Make sure none of the math above just messed up our tree.
1677 */
1682 }
1685 {
1691 num_recs--;
1697 }
1698 }
1700 /*
1701 * Create an empty extent record .
1702 *
1703 * l_next_free_rec may be updated.
1704 *
1705 * If an empty extent already exists do nothing.
1706 */
1708 {
1727 set_and_inc:
1730 }
1732 /*
1733 * For a rotation which involves two leaf nodes, the "root node" is
1734 * the lowest level tree node which contains a path to both leafs. This
1735 * resulting set of information can be used to form a complete "subtree"
1736 *
1737 * This function is passed two full paths from the dinode down to a
1738 * pair of adjacent leaves. It's task is to figure out which path
1739 * index contains the subtree root - this can be the root index itself
1740 * in a worst-case rotation.
1741 *
1742 * The array index of the subtree root is passed back.
1743 */
1747 {
1750 /*
1751 * Check that the caller passed in two paths from the same tree.
1752 */
1756 i++;
1758 /*
1759 * The caller didn't pass two adjacent paths.
1760 */
1772 }
1776 /*
1777 * Traverse a btree path in search of cpos, starting at root_el.
1778 *
1779 * This code can be called with a cpos larger than the tree, in which
1780 * case it will return the rightmost path.
1781 */
1785 {
1787 u32 range;
1788 u64 blkno;
1798 "Owner %llu has empty extent list at "
1805 }
1810 /*
1811 * In the case that cpos is off the allocation
1812 * tree, this should just wind up returning the
1813 * rightmost record.
1814 */
1819 }
1824 "Owner %llu has bad blkno in extent list "
1830 }
1838 }
1846 "Owner %llu has bad count in extent list "
1854 }
1858 }
1860 out:
1861 /*
1862 * Catch any trailing bh that the loop didn't handle.
1863 */
1867 }
1869 /*
1870 * Given an initialized path (that is, it has a valid root extent
1871 * list), this function will traverse the btree in search of the path
1872 * which would contain cpos.
1873 *
1874 * The path traveled is recorded in the path structure.
1875 *
1876 * Note that this will not do any comparisons on leaf node extent
1877 * records, so it will work fine in the case that we just added a tree
1878 * branch.
1879 */
1883 };
1885 {
1891 }
1894 {
1901 }
1904 {
1909 /* We want to retain only the leaf block. */
1913 }
1914 }
1915 /*
1916 * Find the leaf block in the tree which would contain cpos. No
1917 * checking of the actual leaf is done.
1918 *
1919 * Some paths want to call this instead of allocating a path structure
1920 * and calling ocfs2_find_path().
1921 *
1922 * This function doesn't handle non btree extent lists.
1923 */
1927 {
1935 }
1938 out:
1940 }
1942 /*
1943 * Adjust the adjacent records (left_rec, right_rec) involved in a rotation.
1944 *
1945 * Basically, we've moved stuff around at the bottom of the tree and
1946 * we need to fix up the extent records above the changes to reflect
1947 * the new changes.
1948 *
1949 * left_rec: the record on the left.
1950 * left_child_el: is the child list pointed to by left_rec
1951 * right_rec: the record to the right of left_rec
1952 * right_child_el: is the child list pointed to by right_rec
1953 *
1954 * By definition, this only works on interior nodes.
1955 */
1960 {
1963 /*
1964 * Interior nodes never have holes. Their cpos is the cpos of
1965 * the leftmost record in their child list. Their cluster
1966 * count covers the full theoretical range of their child list
1967 * - the range between their cpos and the cpos of the record
1968 * immediately to their right.
1969 */
1975 }
1979 /*
1980 * Calculate the rightmost cluster count boundary before
1981 * moving cpos - we will need to adjust clusters after
1982 * updating e_cpos to keep the same highest cluster count.
1983 */
1992 }
1994 /*
1995 * Adjust the adjacent root node records involved in a
1996 * rotation. left_el_blkno is passed in as a key so that we can easily
1997 * find it's index in the root list.
1998 */
2002 u64 left_el_blkno)
2003 {
2012 }
2014 /*
2015 * The path walking code should have never returned a root and
2016 * two paths which are not adjacent.
2017 */
2022 }
2024 /*
2025 * We've changed a leaf block (in right_path) and need to reflect that
2026 * change back up the subtree.
2027 *
2028 * This happens in multiple places:
2029 * - When we've moved an extent record from the left path leaf to the right
2030 * path leaf to make room for an empty extent in the left path leaf.
2031 * - When our insert into the right path leaf is at the leftmost edge
2032 * and requires an update of the path immediately to it's left. This
2033 * can occur at the end of some types of rotation and appending inserts.
2034 * - When we've adjusted the last extent record in the left path leaf and the
2035 * 1st extent record in the right path leaf during cross extent block merge.
2036 */
2041 {
2047 /*
2048 * Update the counts and position values within all the
2049 * interior nodes to reflect the leaf rotation we just did.
2050 *
2051 * The root node is handled below the loop.
2052 *
2053 * We begin the loop with right_el and left_el pointing to the
2054 * leaf lists and work our way up.
2055 *
2056 * NOTE: within this loop, left_el and right_el always refer
2057 * to the *child* lists.
2058 */
2064 /*
2065 * One nice property of knowing that all of these
2066 * nodes are below the root is that we only deal with
2067 * the leftmost right node record and the rightmost
2068 * left node record.
2069 */
2078 right_el);
2083 /*
2084 * Setup our list pointers now so that the current
2085 * parents become children in the next iteration.
2086 */
2089 }
2091 /*
2092 * At the root node, adjust the two adjacent records which
2093 * begin our path to the leaves.
2094 */
2106 }
2113 {
2126 "Inode %llu has non-full interior leaf node %llu"
2132 }
2134 /*
2135 * This extent block may already have an empty record, so we
2136 * return early if so.
2137 */
2145 subtree_index);
2149 }
2157 }
2164 }
2165 }
2170 /* This is a code error, not a disk corruption. */
2180 /* Do the copy now. */
2185 /*
2186 * Clear out the record we just copied and shift everything
2187 * over, leaving an empty extent in the left leaf.
2188 *
2189 * We temporarily subtract from next_free_rec so that the
2190 * shift will lose the tail record (which is now defunct).
2191 */
2200 subtree_index);
2202 out:
2204 }
2206 /*
2207 * Given a full path, determine what cpos value would return us a path
2208 * containing the leaf immediately to the left of the current one.
2209 *
2210 * Will return zero if the path passed in is already the leftmost path.
2211 */
2214 {
2216 u64 blkno;
2225 /* Start at the tree node just above the leaf and work our way up. */
2230 /*
2231 * Find the extent record just before the one in our
2232 * path.
2233 */
2238 /*
2239 * We've determined that the
2240 * path specified is already
2241 * the leftmost one - return a
2242 * cpos of zero.
2243 */
2245 }
2246 /*
2247 * The leftmost record points to our
2248 * leaf - we need to travel up the
2249 * tree one level.
2250 */
2252 }
2259 }
2260 }
2262 /*
2263 * If we got here, we never found a valid node where
2264 * the tree indicated one should be.
2265 */
2272 next_node:
2274 i--;
2275 }
2277 out:
2279 }
2281 /*
2282 * Extend the transaction by enough credits to complete the rotation,
2283 * and still leave at least the original number of credits allocated
2284 * to this transaction.
2285 */
2289 {
2298 }
2300 /*
2301 * Trap the case where we're inserting into the theoretical range past
2302 * the _actual_ left leaf range. Otherwise, we'll rotate a record
2303 * whose cpos is less than ours into the right leaf.
2304 *
2305 * It's only necessary to look at the rightmost record of the left
2306 * leaf because the logic that calls us should ensure that the
2307 * theoretical ranges in the path components above the leaves are
2308 * correct.
2309 */
2311 u32 insert_cpos)
2312 {
2324 }
2327 {
2337 /* Empty list. */
2341 }
2347 }
2349 /*
2350 * Rotate all the records in a btree right one record, starting at insert_cpos.
2351 *
2352 * The path to the rightmost leaf should be passed in.
2353 *
2354 * The array is assumed to be large enough to hold an entire path (tree depth).
2355 *
2356 * Upon successful return from this function:
2357 *
2358 * - The 'right_path' array will contain a path to the leaf block
2359 * whose range contains e_cpos.
2360 * - That leaf block will have a single empty extent in list index 0.
2361 * - In the case that the rotation requires a post-insert update,
2362 * *ret_left_path will contain a valid path which can be passed to
2363 * ocfs2_insert_path().
2364 */
2368 u32 insert_cpos,
2371 {
2373 u32 cpos;
2384 }
2390 }
2394 /*
2395 * What we want to do here is:
2396 *
2397 * 1) Start with the rightmost path.
2398 *
2399 * 2) Determine a path to the leaf block directly to the left
2400 * of that leaf.
2401 *
2402 * 3) Determine the 'subtree root' - the lowest level tree node
2403 * which contains a path to both leaves.
2404 *
2405 * 4) Rotate the subtree.
2406 *
2407 * 5) Find the next subtree by considering the left path to be
2408 * the new right path.
2409 *
2410 * The check at the top of this while loop also accepts
2411 * insert_cpos == cpos because cpos is only a _theoretical_
2412 * value to get us the left path - insert_cpos might very well
2413 * be filling that hole.
2414 *
2415 * Stop at a cpos of '0' because we either started at the
2416 * leftmost branch (i.e., a tree with one branch and a
2417 * rotation inside of it), or we've gone as far as we can in
2418 * rotating subtrees.
2419 */
2428 }
2432 "Owner %llu: error during insert of %u "
2433 "(left path cpos %u) results in two identical "
2442 insert_cpos)) {
2444 /*
2445 * We've rotated the tree as much as we
2446 * should. The rest is up to
2447 * ocfs2_insert_path() to complete, after the
2448 * record insertion. We indicate this
2449 * situation by returning the left path.
2450 *
2451 * The reason we don't adjust the records here
2452 * before the record insert is that an error
2453 * later might break the rule where a parent
2454 * record e_cpos will reflect the actual
2455 * e_cpos of the 1st nonempty record of the
2456 * child list.
2457 */
2460 }
2465 start,
2474 }
2481 }
2485 insert_cpos)) {
2486 /*
2487 * A rotate moves the rightmost left leaf
2488 * record over to the leftmost right leaf
2489 * slot. If we're doing an extent split
2490 * instead of a real insert, then we have to
2491 * check that the extent to be split wasn't
2492 * just moved over. If it was, then we can
2493 * exit here, passing left_path back -
2494 * ocfs2_split_extent() is smart enough to
2495 * search both leaves.
2496 */
2499 }
2501 /*
2502 * There is no need to re-read the next right path
2503 * as we know that it'll be our current left
2504 * path. Optimize by copying values instead.
2505 */
2512 }
2513 }
2515 out:
2518 out_ret_path:
2520 }
2525 {
2530 u32 range;
2532 /*
2533 * In normal tree rotation process, we will never touch the
2534 * tree branch above subtree_index and ocfs2_extend_rotate_transaction
2535 * doesn't reserve the credits for them either.
2536 *
2537 * But we do have a special case here which will update the rightmost
2538 * records for all the bh in the path.
2539 * So we have to allocate extra credits and access them.
2540 */
2545 }
2551 }
2553 /* Path should always be rightmost. */
2572 }
2573 out:
2575 }
2581 {
2591 /*
2592 * Not all nodes might have had their final count
2593 * decremented by the caller - handle this here.
2594 */
2598 "Inode %llu, attempted to remove extent block "
2607 }
2619 }
2620 }
2628 {
2656 }
2665 {
2683 /*
2684 * It's legal for us to proceed if the right leaf is
2685 * the rightmost one and it has an empty extent. There
2686 * are two cases to handle - whether the leaf will be
2687 * empty after removal or not. If the leaf isn't empty
2688 * then just remove the empty extent up front. The
2689 * next block will handle empty leaves by flagging
2690 * them for unlink.
2691 *
2692 * Non rightmost leaves will throw -EAGAIN and the
2693 * caller can manually move the subtree and retry.
2694 */
2702 OCFS2_JOURNAL_ACCESS_WRITE);
2706 }
2711 }
2715 /*
2716 * We have to update i_last_eb_blk during the meta
2717 * data delete.
2718 */
2720 OCFS2_JOURNAL_ACCESS_WRITE);
2724 }
2727 }
2729 /*
2730 * Getting here with an empty extent in the right path implies
2731 * that it's the rightmost path and will be deleted.
2732 */
2736 subtree_index);
2740 }
2748 }
2755 }
2756 }
2759 /*
2760 * Only do this if we're moving a real
2761 * record. Otherwise, the action is delayed until
2762 * after removal of the right path in which case we
2763 * can do a simple shift to remove the empty extent.
2764 */
2768 }
2770 /*
2771 * Move recs over to get rid of empty extent, decrease
2772 * next_free. This is allowed to remove the last
2773 * extent in our leaf (setting l_next_free_rec to
2774 * zero) - the delete code below won't care.
2775 */
2777 }
2786 left_path);
2790 }
2795 /*
2796 * Removal of the extent in the left leaf was skipped
2797 * above so we could delete the right path
2798 * 1st.
2799 */
2808 subtree_index);
2810 out:
2812 }
2814 /*
2815 * Given a full path, determine what cpos value would return us a path
2816 * containing the leaf immediately to the right of the current one.
2817 *
2818 * Will return zero if the path passed in is already the rightmost path.
2819 *
2820 * This looks similar, but is subtly different to
2821 * ocfs2_find_cpos_for_left_leaf().
2822 */
2825 {
2827 u64 blkno;
2837 /* Start at the tree node just above the leaf and work our way up. */
2844 /*
2845 * Find the extent record just after the one in our
2846 * path.
2847 */
2853 /*
2854 * We've determined that the
2855 * path specified is already
2856 * the rightmost one - return a
2857 * cpos of zero.
2858 */
2860 }
2861 /*
2862 * The rightmost record points to our
2863 * leaf - we need to travel up the
2864 * tree one level.
2865 */
2867 }
2871 }
2872 }
2874 /*
2875 * If we got here, we never found a valid node where
2876 * the tree indicated one should be.
2877 */
2884 next_node:
2886 i--;
2887 }
2889 out:
2891 }
2896 {
2909 }
2914 out:
2916 }
2924 {
2926 u32 right_cpos;
2939 }
2946 }
2955 }
2962 }
2965 right_path);
2968 subtree_root,
2978 }
2980 /*
2981 * Caller might still want to make changes to the
2982 * tree root, so re-add it to the journal here.
2983 */
2989 }
2995 /*
2996 * The rotation has to temporarily stop due to
2997 * the right subtree having an empty
2998 * extent. Pass it back to the caller for a
2999 * fixup.
3000 */
3004 }
3008 }
3010 /*
3011 * The subtree rotate might have removed records on
3012 * the rightmost edge. If so, then rotation is
3013 * complete.
3014 */
3025 }
3026 }
3028 out:
3033 }
3039 {
3041 u32 cpos;
3050 /*
3051 * There's two ways we handle this depending on
3052 * whether path is the only existing one.
3053 */
3056 path);
3060 }
3066 }
3073 }
3076 /*
3077 * We have a path to the left of this one - it needs
3078 * an update too.
3079 */
3085 }
3091 }
3097 }
3104 left_path);
3108 }
3113 /*
3114 * 'path' is also the leftmost path which
3115 * means it must be the only one. This gets
3116 * handled differently because we want to
3117 * revert the root back to having extents
3118 * in-line.
3119 */
3128 }
3132 out:
3135 }
3137 /*
3138 * Left rotation of btree records.
3139 *
3140 * In many ways, this is (unsurprisingly) the opposite of right
3141 * rotation. We start at some non-rightmost path containing an empty
3142 * extent in the leaf block. The code works its way to the rightmost
3143 * path by rotating records to the left in every subtree.
3144 *
3145 * This is used by any code which reduces the number of extent records
3146 * in a leaf. After removal, an empty record should be placed in the
3147 * leftmost list position.
3148 *
3149 * This won't handle a length update of the rightmost path records if
3150 * the rightmost tree leaf record is removed so the caller is
3151 * responsible for detecting and correcting that.
3152 */
3157 {
3168 rightmost_no_delete:
3169 /*
3170 * Inline extents. This is trivially handled, so do
3171 * it up front.
3172 */
3177 }
3179 /*
3180 * Handle rightmost branch now. There's several cases:
3181 * 1) simple rotation leaving records in there. That's trivial.
3182 * 2) rotation requiring a branch delete - there's no more
3183 * records left. Two cases of this:
3184 * a) There are branches to the left.
3185 * b) This is also the leftmost (the only) branch.
3186 *
3187 * 1) is handled via ocfs2_rotate_rightmost_leaf_left()
3188 * 2a) we need the left branch so that we can update it with the unlink
3189 * 2b) we need to bring the root back to inline extents.
3190 */
3195 /*
3196 * This gets a bit tricky if we're going to delete the
3197 * rightmost path. Get the other cases out of the way
3198 * 1st.
3199 */
3210 }
3212 /*
3213 * XXX: The caller can not trust "path" any more after
3214 * this as it will have been deleted. What do we do?
3215 *
3216 * In theory the rotate-for-merge code will never get
3217 * here because it'll always ask for a rotate in a
3218 * nonempty list.
3219 */
3222 dealloc);
3226 }
3228 /*
3229 * Now we can loop, remembering the path we get from -EAGAIN
3230 * and restarting from there.
3231 */
3232 try_rotate:
3238 }
3250 }
3257 }
3259 out:
3263 }
3267 {
3272 /*
3273 * We consumed all of the merged-from record. An empty
3274 * extent cannot exist anywhere but the 1st array
3275 * position, so move things over if the merged-from
3276 * record doesn't occupy that position.
3277 *
3278 * This creates a new empty extent so the caller
3279 * should be smart enough to have removed any existing
3280 * ones.
3281 */
3286 }
3288 /*
3289 * Always memset - the caller doesn't check whether it
3290 * created an empty extent, so there could be junk in
3291 * the other fields.
3292 */
3294 }
3295 }
3300 {
3302 u32 right_cpos;
3308 /* This function shouldn't be called for non-trees. */
3319 }
3321 /* This function shouldn't be called for the rightmost leaf. */
3329 }
3335 }
3338 out:
3342 }
3344 /*
3345 * Remove split_rec clusters from the record at index and merge them
3346 * onto the beginning of the record "next" to it.
3347 * For index < l_count - 1, the next means the extent rec at index + 1.
3348 * For index == l_count - 1, the "next" means the 1st extent rec of the
3349 * next extent block.
3350 */
3356 {
3373 /* we meet with a cross extent block merge. */
3378 }
3387 }
3394 right_path);
3398 right_path);
3402 }
3408 subtree_index);
3412 }
3421 }
3428 }
3429 }
3434 }
3441 }
3448 split_clusters));
3457 subtree_index);
3458 }
3459 out:
3463 }
3468 {
3470 u32 left_cpos;
3475 /* This function shouldn't be called for non-trees. */
3483 }
3485 /* This function shouldn't be called for the leftmost leaf. */
3493 }
3499 }
3502 out:
3506 }
3508 /*
3509 * Remove split_rec clusters from the record at index and merge them
3510 * onto the tail of the record "before" it.
3511 * For index > 0, the "before" means the extent rec at index - 1.
3512 *
3513 * For index == 0, the "before" means the last record of the previous
3514 * extent block. And there is also a situation that we may need to
3515 * remove the rightmost leaf extent block in the right_path and change
3516 * the right path to indicate the new rightmost path.
3517 */
3524 {
3539 /* we meet with a cross extent block merge. */
3544 }
3557 right_path);
3561 left_path);
3565 }
3571 subtree_index);
3575 }
3584 }
3591 }
3592 }
3597 }
3604 }
3607 /*
3608 * The easy case - we can just plop the record right in.
3609 */
3619 split_clusters));
3628 /*
3629 * In the situation that the right_rec is empty and the extent
3630 * block is empty also, ocfs2_complete_edge_insert can't handle
3631 * it and we need to delete the right extent block.
3632 */
3637 right_path,
3638 dealloc);
3642 }
3644 /* Now the rightmost extent block has been deleted.
3645 * So we use the new rightmost path.
3646 */
3652 }
3653 out:
3657 }
3666 {
3674 /*
3675 * The merge code will need to create an empty
3676 * extent to take the place of the newly
3677 * emptied slot. Remove any pre-existing empty
3678 * extents - having more than one in a leaf is
3679 * illegal.
3680 */
3685 }
3686 split_index--;
3688 }
3691 /*
3692 * Left-right contig implies this.
3693 */
3696 /*
3697 * Since the leftright insert always covers the entire
3698 * extent, this call will delete the insert record
3699 * entirely, resulting in an empty extent record added to
3700 * the extent block.
3701 *
3702 * Since the adding of an empty extent shifts
3703 * everything back to the right, there's no need to
3704 * update split_index here.
3705 *
3706 * When the split_index is zero, we need to merge it to the
3707 * prevoius extent block. It is more efficient and easier
3708 * if we do merge_right first and merge_left later.
3709 */
3711 split_index);
3715 }
3717 /*
3718 * We can only get this from logic error above.
3719 */
3722 /* The merge left us with an empty extent, remove it. */
3727 }
3731 /*
3732 * Note that we don't pass split_rec here on purpose -
3733 * we've merged it into the rec already.
3734 */
3741 }
3744 /*
3745 * Error from this last rotate is not critical, so
3746 * print but don't bubble it up.
3747 */
3752 /*
3753 * Merge a record to the left or right.
3754 *
3755 * 'contig_type' is relative to the existing record,
3756 * so for example, if we're "right contig", it's to
3757 * the record on the left (hence the left merge).
3758 */
3762 split_index);
3766 }
3770 split_index);
3774 }
3775 }
3778 /*
3779 * The merge may have left an empty extent in
3780 * our leaf. Try to rotate it away.
3781 */
3783 dealloc);
3787 }
3788 }
3790 out:
3792 }
3798 {
3799 u64 len_blocks;
3805 /*
3806 * Region is on the left edge of the existing
3807 * record.
3808 */
3815 /*
3816 * Region is on the right edge of the existing
3817 * record.
3818 */
3821 }
3822 }
3824 /*
3825 * Do the final bits of extent record insertion at the target leaf
3826 * list. If this leaf is part of an allocation tree, it is assumed
3827 * that the tree above has been prepared.
3828 */
3833 {
3846 insert_rec);
3848 }
3850 /*
3851 * Contiguous insert - either left or right.
3852 */
3858 }
3862 }
3864 /*
3865 * Handle insert into an empty leaf.
3866 */
3873 }
3875 /*
3876 * Appending insert.
3877 */
3887 "owner %llu, depth %u, count %u, next free %u, "
3888 "rec.cpos %u, rec.clusters %u, "
3898 i++;
3902 }
3904 rotate:
3905 /*
3906 * Ok, we have to rotate.
3907 *
3908 * At this point, it is safe to assume that inserting into an
3909 * empty leaf and appending to a leaf have both been handled
3910 * above.
3911 *
3912 * This leaf needs to have space, either by the empty 1st
3913 * extent record, or by virtue of an l_next_rec < l_count.
3914 */
3916 }
3922 {
3928 /*
3929 * Update everything except the leaf block.
3930 */
3942 }
3953 }
3954 }
3961 {
3968 /*
3969 * This shouldn't happen for non-trees. The extent rec cluster
3970 * count manipulation below only works for interior nodes.
3971 */
3974 /*
3975 * If our appending insert is at the leftmost edge of a leaf,
3976 * then we might need to update the rightmost records of the
3977 * neighboring path.
3978 */
3983 u32 left_cpos;
3990 }
3994 left_cpos);
3996 /*
3997 * No need to worry if the append is already in the
3998 * leftmost leaf.
3999 */
4006 }
4009 left_cpos);
4013 }
4015 /*
4016 * ocfs2_insert_path() will pass the left_path to the
4017 * journal for us.
4018 */
4019 }
4020 }
4026 }
4032 out:
4037 }
4044 {
4061 /*
4062 * This typically means that the record
4063 * started in the left path but moved to the
4064 * right as a result of rotation. We either
4065 * move the existing record to the left, or we
4066 * do the later insert there.
4067 *
4068 * In this case, the left path should always
4069 * exist as the rotate code will have passed
4070 * it back for a post-insert update.
4071 */
4074 /*
4075 * It's a left split. Since we know
4076 * that the rotate code gave us an
4077 * empty extent in the left path, we
4078 * can just do the insert there.
4079 */
4082 /*
4083 * Right split - we have to move the
4084 * existing record over to the left
4085 * leaf. The insert will be into the
4086 * newly created empty extent in the
4087 * right leaf.
4088 */
4096 }
4097 }
4101 /*
4102 * Left path is easy - we can just allow the insert to
4103 * happen.
4104 */
4109 }
4115 }
4117 /*
4118 * This function only does inserts on an allocation b-tree. For tree
4119 * depth = 0, ocfs2_insert_at_leaf() is called directly.
4120 *
4121 * right_path is the path we want to do the actual insert
4122 * in. left_path should only be passed in if we need to update that
4123 * portion of the tree after an edge insert.
4124 */
4131 {
4136 /*
4137 * There's a chance that left_path got passed back to
4138 * us without being accounted for in the
4139 * journal. Extend our transaction here to be sure we
4140 * can change those blocks.
4141 */
4146 }
4152 }
4153 }
4155 /*
4156 * Pass both paths to the journal. The majority of inserts
4157 * will be touching all components anyway.
4158 */
4163 }
4166 /*
4167 * We could call ocfs2_insert_at_leaf() for some types
4168 * of splits, but it's easier to just let one separate
4169 * function sort it all out.
4170 */
4174 /*
4175 * Split might have modified either leaf and we don't
4176 * have a guarantee that the later edge insert will
4177 * dirty this for us.
4178 */
4184 insert);
4189 /*
4190 * The rotate code has indicated that we need to fix
4191 * up portions of the tree after the insert.
4192 *
4193 * XXX: Should we extend the transaction here?
4194 */
4196 right_path);
4198 subtree_index);
4199 }
4202 out:
4204 }
4210 {
4212 u32 cpos;
4220 OCFS2_JOURNAL_ACCESS_WRITE);
4224 }
4229 }
4236 }
4238 /*
4239 * Determine the path to start with. Rotations need the
4240 * rightmost path, everything else can go directly to the
4241 * target leaf.
4242 */
4248 }
4254 }
4256 /*
4257 * Rotations and appends need special treatment - they modify
4258 * parts of the tree's above them.
4259 *
4260 * Both might pass back a path immediate to the left of the
4261 * one being inserted to. This will be cause
4262 * ocfs2_insert_path() to modify the rightmost records of
4263 * left_path to account for an edge insert.
4264 *
4265 * XXX: When modifying this code, keep in mind that an insert
4266 * can wind up skipping both of these two special cases...
4267 */
4275 }
4277 /*
4278 * ocfs2_rotate_tree_right() might have extended the
4279 * transaction without re-journaling our tree root.
4280 */
4282 OCFS2_JOURNAL_ACCESS_WRITE);
4286 }
4294 }
4295 }
4302 }
4304 out_update_clusters:
4311 out:
4316 }
4318 static enum ocfs2_contig_type
4323 {
4347 left_cpos);
4358 "Extent block #%llu has an "
4359 "invalid l_next_free_rec of "
4360 "%d. It should have "
4367 }
4370 }
4371 }
4373 /*
4374 * We're careful to check for an empty extent record here -
4375 * the merge code will know what to do if it sees one.
4376 */
4383 }
4384 }
4413 "Extent block #%llu has an "
4419 }
4421 }
4422 }
4433 }
4435 out:
4442 }
4448 {
4456 insert_rec);
4460 }
4461 }
4470 /*
4471 * Caller might want us to limit the size of extents, don't
4472 * calculate contiguousness if we might exceed that limit.
4473 */
4477 }
4478 }
4480 /*
4481 * This should only be called against the righmost leaf extent list.
4482 *
4483 * ocfs2_figure_appending_type() will figure out whether we'll have to
4484 * insert at the tail of the rightmost leaf.
4485 *
4486 * This should also work against the root extent list for tree's with 0
4487 * depth. If we consider the root extent list to be the rightmost leaf node
4488 * then the logic here makes sense.
4489 */
4493 {
4506 /* Were all records empty? */
4509 }
4520 set_tail_append:
4522 }
4524 /*
4525 * Helper function called at the begining of an insert.
4526 *
4527 * This computes a few things that are commonly used in the process of
4528 * inserting into the btree:
4529 * - Whether the new extent is contiguous with an existing one.
4530 * - The current tree depth.
4531 * - Whether the insert is an appending one.
4532 * - The total # of free records in the tree.
4533 *
4534 * All of the information is stored on the ocfs2_insert_type
4535 * structure.
4536 */
4542 {
4555 /*
4556 * If we have tree depth, we read in the
4557 * rightmost extent block ahead of time as
4558 * ocfs2_figure_insert_type() and ocfs2_add_branch()
4559 * may want it later.
4560 */
4567 }
4570 }
4572 /*
4573 * Unless we have a contiguous insert, we'll need to know if
4574 * there is room left in our allocation tree for another
4575 * extent record.
4576 *
4577 * XXX: This test is simplistic, we can search for empty
4578 * extent records too.
4579 */
4587 }
4594 }
4596 /*
4597 * In the case that we're inserting past what the tree
4598 * currently accounts for, ocfs2_find_path() will return for
4599 * us the rightmost tree path. This is accounted for below in
4600 * the appending code.
4601 */
4606 }
4610 /*
4611 * Now that we have the path, there's two things we want to determine:
4612 * 1) Contiguousness (also set contig_index if this is so)
4613 *
4614 * 2) Are we doing an append? We can trivially break this up
4615 * into two types of appends: simple record append, or a
4616 * rotate inside the tail leaf.
4617 */
4620 /*
4621 * The insert code isn't quite ready to deal with all cases of
4622 * left contiguousness. Specifically, if it's an insert into
4623 * the 1st record in a leaf, it will require the adjustment of
4624 * cluster count on the last record of the path directly to it's
4625 * left. For now, just catch that case and fool the layers
4626 * above us. This works just fine for tree_depth == 0, which
4627 * is why we allow that above.
4628 */
4633 /*
4634 * Ok, so we can simply compare against last_eb to figure out
4635 * whether the path doesn't exist. This will only happen in
4636 * the case that we're doing a tail append, so maybe we can
4637 * take advantage of that information somehow.
4638 */
4641 /*
4642 * Ok, ocfs2_find_path() returned us the rightmost
4643 * tree path. This might be an appending insert. There are
4644 * two cases:
4645 * 1) We're doing a true append at the tail:
4646 * -This might even be off the end of the leaf
4647 * 2) We're "appending" by rotating in the tail
4648 */
4650 }
4652 out:
4657 else
4660 }
4662 /*
4663 * Insert an extent into a btree.
4664 *
4665 * The caller needs to update the owning btree's cluster count.
4666 */
4669 u32 cpos,
4670 u64 start_blk,
4671 u32 new_clusters,
4672 u8 flags,
4674 {
4694 }
4701 }
4704 "Insert.contig_index: %d, Insert.free_records: %d, "
4712 meta_ac);
4716 }
4717 }
4719 /* Finally, we can add clusters. This might rotate the tree for us. */
4723 else
4726 bail:
4731 }
4733 /*
4734 * Allcate and add clusters into the extent b-tree.
4735 * The new clusters(clusters_to_add) will be inserted at logical_offset.
4736 * The extent b-tree's root is specified by et, and
4737 * it is not limited to the file storage. Any extent tree can use this
4738 * function if it implements the proper ocfs2_extent_tree.
4739 */
4743 u32 clusters_to_add,
4748 {
4753 u64 block;
4768 }
4770 /* there are two cases which could cause us to EAGAIN in the
4771 * we-need-more-metadata case:
4772 * 1) we haven't reserved *any*
4773 * 2) we are so fragmented, we've needed to add metadata too
4774 * many times. */
4787 }
4795 }
4799 /* reserve our write early -- insert_extent may update the tree root */
4801 OCFS2_JOURNAL_ACCESS_WRITE);
4805 }
4816 }
4825 clusters_to_add);
4828 }
4830 leave:
4835 }
4839 u32 cpos,
4841 {
4855 }
4864 {
4874 leftright:
4875 /*
4876 * Store a copy of the record on the stack - it might move
4877 * around as the tree is manipulated below.
4878 */
4888 }
4897 }
4898 }
4915 /*
4916 * Left/right split. We fake this as a right split
4917 * first and then make a second pass as a left split.
4918 */
4928 }
4934 }
4937 u32 cpos;
4940 do_leftright++;
4950 }
4955 }
4956 out:
4959 }
4967 {
4975 }
4980 out:
4982 }
4984 /*
4985 * Split part or all of the extent record at split_index in the leaf
4986 * pointed to by path. Merge with the contiguous extent record if needed.
4987 *
4988 * Care is taken to handle contiguousness so as to not grow the tree.
4989 *
4990 * meta_ac is not strictly necessary - we only truly need it if growth
4991 * of the tree is required. All other cases will degrade into a less
4992 * optimal tree layout.
4993 *
4994 * last_eb_bh should be the rightmost leaf block for any extent
4995 * btree. Since a split may grow the tree or a merge might shrink it,
4996 * the caller cannot trust the contents of that buffer after this call.
4997 *
4998 * This code is optimized for readability - several passes might be
4999 * made over certain portions of the tree. All of those blocks will
5000 * have been brought into cache (and pinned via the journal), so the
5001 * extra overhead is not expressed in terms of disk reads.
5002 */
5010 {
5024 }
5027 split_index,
5028 split_rec);
5030 /*
5031 * The core merge / split code wants to know how much room is
5032 * left in this allocation tree, so we pass the
5033 * rightmost extent list.
5034 */
5044 }
5054 else
5067 else
5079 }
5081 out:
5084 }
5086 /*
5087 * Change the flags of the already-existing extent at cpos for len clusters.
5088 *
5089 * new_flags: the flags we want to set.
5090 * clear_flags: the flags we want to clear.
5091 * phys: the new physical offset we want this new extent starts from.
5092 *
5093 * If the existing extent is larger than the request, initiate a
5094 * split. An attempt will be made at merging with adjacent extents.
5095 *
5096 * The caller is responsible for passing down meta_ac if we'll need it.
5097 */
5104 {
5118 }
5124 }
5130 "Owner %llu has an extent at cpos %u which can no "
5136 }
5144 new_flags);
5146 }
5152 clear_flags);
5154 }
5168 dealloc);
5172 out:
5176 }
5178 /*
5179 * Mark the already-existing extent at cpos as written for len clusters.
5180 * This removes the unwritten extent flag.
5181 *
5182 * If the existing extent is larger than the request, initiate a
5183 * split. An attempt will be made at merging with adjacent extents.
5184 *
5185 * The caller is responsible for passing down meta_ac if we'll need it.
5186 */
5192 {
5200 "that are being written to, but the feature bit "
5205 }
5207 /*
5208 * XXX: This should be fixed up so that we just re-insert the
5209 * next extent records.
5210 */
5219 out:
5221 }
5227 {
5236 /*
5237 * Setup the record to split before we grow the tree.
5238 */
5252 }
5265 }
5270 meta_ac);
5274 }
5275 }
5287 out:
5290 }
5297 {
5312 }
5314 index--;
5315 }
5319 /*
5320 * Check whether this is the rightmost tree record. If
5321 * we remove all of this record or part of its right
5322 * edge then an update of the record lengths above it
5323 * will be required.
5324 */
5328 }
5333 /*
5334 * Changing the leftmost offset (via partial or whole
5335 * record truncate) of an interior (or rightmost) path
5336 * means we have to update the subtree that is formed
5337 * by this leaf and the one to it's left.
5338 *
5339 * There are two cases we can skip:
5340 * 1) Path is the leftmost one in our btree.
5341 * 2) The leaf is rightmost and will be empty after
5342 * we remove the extent record - the rotate code
5343 * knows how to update the newly formed edge.
5344 */
5350 }
5358 }
5361 left_cpos);
5365 }
5366 }
5367 }
5371 path);
5375 }
5381 }
5387 }
5401 /*
5402 * We skip the edge update if this path will
5403 * be deleted by the rotate code.
5404 */
5407 rec);
5408 }
5410 /* Remove leftmost portion of the record. */
5415 /* Remove rightmost portion of the record */
5420 /* Caller should have trapped this. */
5427 }
5434 subtree_index);
5435 }
5443 }
5445 out:
5448 }
5455 {
5462 /*
5463 * XXX: Why are we truncating to 0 instead of wherever this
5464 * affects us?
5465 */
5473 }
5479 }
5485 "Owner %llu has an extent at cpos %u which can no "
5488 cpos);
5491 }
5493 /*
5494 * We have 3 cases of extent removal:
5495 * 1) Range covers the entire extent rec
5496 * 2) Range begins or ends on one edge of the extent rec
5497 * 3) Range is in the middle of the extent rec (no shared edges)
5498 *
5499 * For case 1 we remove the extent rec and left rotate to
5500 * fill the hole.
5501 *
5502 * For case 2 we just shrink the existing extent rec, with a
5503 * tree update if the shrinking edge is also the edge of an
5504 * extent block.
5505 *
5506 * For case 3 we do a right split to turn the extent rec into
5507 * something case 2 can handle.
5508 */
5527 }
5534 }
5536 /*
5537 * The split could have manipulated the tree enough to
5538 * move the record location, so we have to look for it again.
5539 */
5546 }
5554 cpos);
5557 }
5559 /*
5560 * Double check our values here. If anything is fishy,
5561 * it's easier to catch it at the top level.
5562 */
5568 "Owner %llu: error after split at cpos %u"
5575 }
5582 }
5583 }
5585 out:
5588 }
5590 /*
5591 * ocfs2_reserve_blocks_for_rec_trunc() would look basically the
5592 * same as ocfs2_lock_alloctors(), except for it accepts a blocks
5593 * number to reserve some extra blocks, and it only handles meta
5594 * data allocations.
5595 *
5596 * Currently, only ocfs2_remove_btree_range() uses it for truncating
5597 * and punching holes.
5598 */
5601 u32 extents_to_split,
5604 {
5616 }
5628 }
5629 }
5631 out:
5636 }
5637 }
5640 }
5646 u64 refcount_loc)
5647 {
5658 OCFS2_HAS_REFCOUNT_FL));
5665 }
5668 refcount_loc,
5669 phys_blkno,
5670 len,
5676 }
5677 }
5680 extra_blocks);
5684 }
5693 }
5694 }
5702 }
5705 OCFS2_JOURNAL_ACCESS_WRITE);
5709 }
5718 }
5728 phys_blkno),
5731 else
5737 }
5739 out_commit:
5741 out:
5751 }
5754 {
5763 "slot %d, invalid truncate log parameters: used = "
5767 }
5771 {
5775 /* No records, nothing to coalesce */
5784 }
5788 u64 start_blk,
5790 {
5807 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5808 * by the underlying call to ocfs2_read_inode_block(), so any
5809 * corruption is a code bug */
5816 "Truncate record count on #%llu invalid "
5822 /* Caller should have known to flush before calling us. */
5828 }
5831 OCFS2_JOURNAL_ACCESS_WRITE);
5835 }
5842 /*
5843 * Move index back to the record we are coalescing with.
5844 * ocfs2_truncate_log_can_coalesce() guarantees nonzero
5845 */
5846 index--;
5851 num_clusters);
5855 }
5861 bail:
5864 }
5870 {
5874 u64 start_blk;
5887 /* Caller has given us at least enough credits to
5888 * update the truncate log dinode */
5890 OCFS2_JOURNAL_ACCESS_WRITE);
5894 }
5900 /* TODO: Perhaps we can calculate the bulk of the
5901 * credits up front rather than extending like
5902 * this. */
5904 OCFS2_TRUNCATE_LOG_FLUSH_ONE_REC);
5908 }
5915 /* if start_blk is not set, we ignore the record as
5916 * invalid. */
5923 num_clusters);
5927 }
5928 }
5929 i--;
5930 }
5934 bail:
5937 }
5939 /* Expects you to already be holding tl_inode->i_mutex */
5941 {
5958 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5959 * by the underlying call to ocfs2_read_inode_block(), so any
5960 * corruption is a code bug */
5970 }
5973 GLOBAL_BITMAP_SYSTEM_INODE,
5974 OCFS2_INVALID_SLOT);
5979 }
5987 }
5994 }
5997 data_alloc_bh);
6003 out_unlock:
6007 out_mutex:
6011 out:
6014 }
6017 {
6026 }
6029 {
6040 else
6044 }
6046 #define OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL (2 * HZ)
6049 {
6051 /* We want to push off log flushes while truncates are
6052 * still running. */
6057 OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL);
6058 }
6059 }
6065 {
6071 TRUNCATE_LOG_SYSTEM_INODE,
6072 slot_num);
6077 }
6084 }
6088 bail:
6091 }
6093 /* called during the 1st stage of node recovery. we stamp a clean
6094 * truncate log and pass back a copy for processing later. if the
6095 * truncate log does not require processing, a *tl_copy is set to
6096 * NULL. */
6100 {
6115 }
6119 /* tl_bh is loaded from ocfs2_get_truncate_log_info(). It's
6120 * validated by the underlying call to ocfs2_read_inode_block(),
6121 * so any corruption is a code bug */
6134 }
6136 /* Assuming the write-out below goes well, this copy
6137 * will be passed back to recovery for processing. */
6140 /* All we need to do to clear the truncate log is set
6141 * tl_used. */
6149 }
6150 }
6152 bail:
6160 }
6164 }
6168 {
6172 u64 start_blk;
6182 }
6196 }
6197 }
6204 }
6216 }
6217 }
6219 bail_up:
6224 }
6227 {
6243 }
6246 }
6249 {
6263 /* ocfs2_truncate_log_shutdown keys on the existence of
6264 * osb->osb_tl_inode so we don't set any of the osb variables
6265 * until we're sure all is well. */
6267 ocfs2_truncate_log_worker);
6273 }
6275 /*
6276 * Delayed de-allocation of suballocator blocks.
6277 *
6278 * Some sets of block de-allocations might involve multiple suballocator inodes.
6279 *
6280 * The locking for this can get extremely complicated, especially when
6281 * the suballocator inodes to delete from aren't known until deep
6282 * within an unrelated codepath.
6283 *
6284 * ocfs2_extent_block structures are a good example of this - an inode
6285 * btree could have been grown by any number of nodes each allocating
6286 * out of their own suballoc inode.
6287 *
6288 * These structures allow the delay of block de-allocation until a
6289 * later time, when locking of multiple cluster inodes won't cause
6290 * deadlock.
6291 */
6293 /*
6294 * Describe a single bit freed from a suballocator. For the block
6295 * suballocators, it represents one block. For the global cluster
6296 * allocator, it represents some clusters and free_bit indicates
6297 * clusters number.
6298 */
6301 u64 free_bg;
6302 u64 free_blk;
6304 };
6311 };
6317 {
6319 u64 bg_blkno;
6330 }
6338 }
6345 }
6350 else
6361 }
6367 }
6372 }
6374 out_journal:
6377 out_unlock:
6380 out_mutex:
6383 out:
6385 /* Premature exit may have left some dangling items. */
6389 }
6392 }
6396 {
6405 }
6416 }
6420 {
6434 }
6435 }
6442 }
6455 }
6456 }
6461 /* Premature exit may have left some dangling items. */
6465 }
6468 }
6472 {
6493 }
6497 }
6508 }
6511 }
6517 {
6525 }
6535 }
6537 }
6542 {
6552 }
6559 }
6572 out:
6574 }
6578 {
6584 }
6587 {
6591 }
6596 {
6606 /*
6607 * Need to set the buffers we zero'd into uptodate
6608 * here if they aren't - ocfs2_map_page_blocks()
6609 * might've skipped some
6610 */
6613 ocfs2_zero_func);
6620 }
6626 }
6631 {
6657 }
6658 out:
6661 }
6665 {
6669 loff_t last_page_bytes;
6682 }
6684 numpages++;
6685 index++;
6688 out:
6693 }
6698 }
6702 {
6709 }
6711 /*
6712 * Zero the area past i_size but still within an allocated
6713 * cluster. This avoids exposing nonzero data on subsequent file
6714 * extends.
6715 *
6716 * We need to call this before i_size is updated on the inode because
6717 * otherwise block_write_full_page() will skip writeout of pages past
6718 * i_size. The new_i_size parameter is passed for this reason.
6719 */
6722 {
6725 u64 phys;
6729 /*
6730 * File systems which don't support sparse files zero on every
6731 * extend.
6732 */
6742 }
6753 }
6755 /*
6756 * Tail is a hole, or is marked unwritten. In either case, we
6757 * can count on read and write to return/push zero's.
6758 */
6767 }
6772 /*
6773 * Initiate writeout of the pages we zero'd here. We don't
6774 * wait on them - the truncate_inode_pages() call later will
6775 * do that for us.
6776 */
6782 out:
6787 }
6791 {
6798 xattrsize);
6799 else
6802 }
6806 {
6812 }
6815 {
6824 /*
6825 * We clear the entire i_data structure here so that all
6826 * fields can be properly initialized.
6827 */
6832 }
6836 {
6858 }
6864 }
6865 }
6873 }
6876 OCFS2_JOURNAL_ACCESS_WRITE);
6880 }
6885 u64 phys;
6900 }
6902 /*
6903 * Save two copies, one for insert, and one that can
6904 * be changed by ocfs2_map_and_dirty_page() below.
6905 */
6908 /*
6909 * Non sparse file systems zero on extend, so no need
6910 * to do that now.
6911 */
6920 }
6922 /*
6923 * This should populate the 1st page for us and mark
6924 * it up to date.
6925 */
6930 }
6939 }
6951 /*
6952 * An error at this point should be extremely rare. If
6953 * this proves to be false, we could always re-build
6954 * the in-inode data from our pages.
6955 */
6961 }
6964 }
6966 out_commit:
6973 out_unlock:
6977 out:
6981 }
6984 }
6986 /*
6987 * It is expected, that by the time you call this function,
6988 * inode->i_size and fe->i_size have been adjusted.
6989 *
6990 * WARNING: This will kfree the truncate context
6991 */
6995 {
7017 ocfs2_journal_access_di);
7022 }
7026 start:
7027 /*
7028 * Check that we still have allocation to delete.
7029 */
7033 }
7035 /*
7036 * Truncate always works against the rightmost tree branch.
7037 */
7042 }
7047 /*
7048 * By now, el will point to the extent list on the bottom most
7049 * portion of this tree. Only the tail record is considered in
7050 * each pass.
7051 *
7052 * We handle the following cases, in order:
7053 * - empty extent: delete the remaining branch
7054 * - remove the entire record
7055 * - remove a partial record
7056 * - no record needs to be removed (truncate has completed)
7057 */
7066 }
7074 /*
7075 * Lower levels depend on this never happening, but it's best
7076 * to check it up here before changing the tree.
7077 */
7084 }
7089 /*
7090 * Truncate entire record.
7091 */
7096 /*
7097 * Partial truncate. it also should be
7098 * the last truncate we're doing.
7099 */
7106 /*
7107 * Truncate completed, leave happily.
7108 */
7111 }
7117 refcount_loc);
7121 }
7125 /*
7126 * The check above will catch the case where we've truncated
7127 * away all allocation.
7128 */
7131 bail:
7141 }
7143 /*
7144 * 'start' is inclusive, 'end' is not.
7145 */
7148 {
7165 "Inline data flags for inode %llu don't agree! "
7173 }
7180 }
7183 OCFS2_JOURNAL_ACCESS_WRITE);
7187 }
7192 /*
7193 * No need to worry about the data page here - it's been
7194 * truncated already and inline data doesn't need it for
7195 * pushing zero's to disk, so we'll let readpage pick it up
7196 * later.
7197 */
7201 }
7211 out_commit:
7214 out:
7216 }