| blob | 7dabbc31060e466e0959f5a8ec09b0028662cd6b |
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>
32 #include <linux/blkdev.h>
34 #include <cluster/masklog.h>
59 CONTIG_LEFT,
60 CONTIG_RIGHT,
61 CONTIG_LEFTRIGHT,
62 };
64 static enum ocfs2_contig_type
68 /*
69 * Operations for a specific extent tree type.
70 *
71 * To implement an on-disk btree (extent tree) type in ocfs2, add
72 * an ocfs2_extent_tree_operations structure and the matching
73 * ocfs2_init_<thingy>_extent_tree() function. That's pretty much it
74 * for the allocation portion of the extent tree.
75 */
77 /*
78 * last_eb_blk is the block number of the right most leaf extent
79 * block. Most on-disk structures containing an extent tree store
80 * this value for fast access. The ->eo_set_last_eb_blk() and
81 * ->eo_get_last_eb_blk() operations access this value. They are
82 * both required.
83 */
85 u64 blkno);
88 /*
89 * The on-disk structure usually keeps track of how many total
90 * clusters are stored in this extent tree. This function updates
91 * that value. new_clusters is the delta, and must be
92 * added to the total. Required.
93 */
95 u32 new_clusters);
97 /*
98 * If this extent tree is supported by an extent map, insert
99 * a record into the map.
100 */
104 /*
105 * If this extent tree is supported by an extent map, truncate the
106 * map to clusters,
107 */
109 u32 clusters);
111 /*
112 * If ->eo_insert_check() exists, it is called before rec is
113 * inserted into the extent tree. It is optional.
114 */
119 /*
120 * --------------------------------------------------------------
121 * The remaining are internal to ocfs2_extent_tree and don't have
122 * accessor functions
123 */
125 /*
126 * ->eo_fill_root_el() takes et->et_object and sets et->et_root_el.
127 * It is required.
128 */
131 /*
132 * ->eo_fill_max_leaf_clusters sets et->et_max_leaf_clusters if
133 * it exists. If it does not, et->et_max_leaf_clusters is set
134 * to 0 (unlimited). Optional.
135 */
138 /*
139 * ->eo_extent_contig test whether the 2 ocfs2_extent_rec
140 * are contiguous or not. Optional. Don't need to set it if use
141 * ocfs2_extent_rec as the tree leaf.
142 */
143 enum ocfs2_contig_type
147 };
150 /*
151 * Pre-declare ocfs2_dinode_et_ops so we can use it as a sanity check
152 * in the methods.
153 */
156 u64 blkno);
158 u32 clusters);
162 u32 clusters);
176 };
179 u64 blkno)
180 {
185 }
188 {
193 }
196 u32 clusters)
197 {
205 }
209 {
213 }
216 u32 clusters)
217 {
221 }
225 {
232 "Device %s, asking for sparse allocation: inode %llu, "
239 }
242 {
249 }
252 {
256 }
260 {
264 }
267 u64 blkno)
268 {
272 }
275 {
279 }
282 u32 clusters)
283 {
287 }
294 };
297 {
301 }
304 {
308 }
311 u64 blkno)
312 {
317 }
320 {
325 }
328 u32 clusters)
329 {
333 }
341 };
344 u64 blkno)
345 {
349 }
352 {
356 }
359 u32 clusters)
360 {
364 }
367 {
373 }
376 {
380 }
388 };
391 {
395 }
398 u64 blkno)
399 {
403 }
406 {
410 }
413 u32 clusters)
414 {
418 }
420 static enum ocfs2_contig_type
424 {
426 }
434 };
439 ocfs2_journal_access_func access,
442 {
454 else
456 }
461 {
464 }
469 {
472 }
477 {
480 }
485 {
488 }
493 {
496 }
499 u64 new_last_eb_blk)
500 {
502 }
505 {
507 }
510 u32 clusters)
511 {
513 }
517 {
520 }
523 u32 clusters)
524 {
527 }
532 {
534 type);
535 }
541 {
548 }
552 {
558 }
561 {
567 }
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 {
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 }
924 }
932 }
933 bail:
935 }
939 {
944 ocfs2_validate_extent_block);
946 /* If ocfs2_read_block() got us a new bh, pass it up. */
951 }
954 /*
955 * How many free extents have we got before we need more meta data?
956 */
959 {
975 }
978 }
983 bail:
988 }
990 /* expects array to already be allocated
991 *
992 * sets h_signature, h_blkno, h_suballoc_bit, h_suballoc_slot, and
993 * l_count for you
994 */
1000 {
1002 u16 suballoc_bit_start;
1003 u32 num_got;
1012 meta_ac,
1021 }
1029 }
1034 OCFS2_JOURNAL_ACCESS_CREATE);
1038 }
1042 /* Ok, setup the minimal stuff here. */
1053 suballoc_bit_start++;
1054 first_blkno++;
1056 /* We'll also be dirtied by the caller, so
1057 * this isn't absolutely necessary. */
1059 }
1062 }
1065 bail:
1070 }
1072 }
1074 }
1076 /*
1077 * Helper function for ocfs2_add_branch() and ocfs2_shift_tree_depth().
1078 *
1079 * Returns the sum of the rightmost extent rec logical offset and
1080 * cluster count.
1081 *
1082 * ocfs2_add_branch() uses this to determine what logical cluster
1083 * value should be populated into the leftmost new branch records.
1084 *
1085 * ocfs2_shift_tree_depth() uses this to determine the # clusters
1086 * value for the new topmost tree record.
1087 */
1089 {
1096 }
1098 /*
1099 * Change range of the branches in the right most path according to the leaf
1100 * extent block's rightmost record.
1101 */
1104 {
1114 }
1120 }
1126 }
1132 }
1139 out:
1142 }
1144 /*
1145 * Add an entire tree branch to our inode. eb_bh is the extent block
1146 * to start at, if we don't want to start the branch at the root
1147 * structure.
1148 *
1149 * last_eb_bh is required as we have to update it's next_leaf pointer
1150 * for the new last extent block.
1151 *
1152 * the new branch will be 'empty' in the sense that every block will
1153 * contain a single record with cluster count == 0.
1154 */
1160 {
1178 /* we never add a branch to a leaf. */
1187 /*
1188 * If there is a gap before the root end and the real end
1189 * of the righmost leaf block, we need to remove the gap
1190 * between new_cpos and root_end first so that the tree
1191 * is consistent after we add a new branch(it will start
1192 * from new_cpos).
1193 */
1204 }
1205 }
1207 /* allocate the number of new eb blocks we need */
1209 GFP_KERNEL);
1214 }
1221 }
1223 /* Note: new_eb_bhs[new_blocks - 1] is the guy which will be
1224 * linked with the rest of the tree.
1225 * conversly, new_eb_bhs[0] is the new bottommost leaf.
1226 *
1227 * when we leave the loop, new_last_eb_blk will point to the
1228 * newest leaf, and next_blkno will point to the topmost extent
1229 * block. */
1234 /* ocfs2_create_new_meta_bhs() should create it right! */
1239 OCFS2_JOURNAL_ACCESS_CREATE);
1243 }
1248 /*
1249 * This actually counts as an empty extent as
1250 * c_clusters == 0
1251 */
1254 /*
1255 * eb_el isn't always an interior node, but even leaf
1256 * nodes want a zero'd flags and reserved field so
1257 * this gets the whole 32 bits regardless of use.
1258 */
1265 }
1267 /* This is a bit hairy. We want to update up to three blocks
1268 * here without leaving any of them in an inconsistent state
1269 * in case of error. We don't have to worry about
1270 * journal_dirty erroring as it won't unless we've aborted the
1271 * handle (in which case we would never be here) so reserving
1272 * the write with journal_access is all we need to do. */
1274 OCFS2_JOURNAL_ACCESS_WRITE);
1278 }
1280 OCFS2_JOURNAL_ACCESS_WRITE);
1284 }
1287 OCFS2_JOURNAL_ACCESS_WRITE);
1291 }
1292 }
1294 /* Link the new branch into the rest of the tree (el will
1295 * either be on the root_bh, or the extent block passed in. */
1302 /* fe needs a new last extent block pointer, as does the
1303 * next_leaf on the previously last-extent-block. */
1314 /*
1315 * Some callers want to track the rightmost leaf so pass it
1316 * back here.
1317 */
1323 bail:
1328 }
1331 }
1333 /*
1334 * adds another level to the allocation tree.
1335 * returns back the new extent block so you can add a branch to it
1336 * after this call.
1337 */
1342 {
1344 u32 new_clusters;
1355 }
1358 /* ocfs2_create_new_meta_bhs() should create it right! */
1365 OCFS2_JOURNAL_ACCESS_CREATE);
1369 }
1371 /* copy the root extent list data into the new extent block */
1380 OCFS2_JOURNAL_ACCESS_WRITE);
1384 }
1388 /* update root_bh now */
1397 /* If this is our 1st tree depth shift, then last_eb_blk
1398 * becomes the allocated extent block */
1407 bail:
1411 }
1413 /*
1414 * Should only be called when there is no space left in any of the
1415 * leaf nodes. What we want to do is find the lowest tree depth
1416 * non-leaf extent block with room for new records. There are three
1417 * valid results of this search:
1418 *
1419 * 1) a lowest extent block is found, then we pass it back in
1420 * *lowest_eb_bh and return '0'
1421 *
1422 * 2) the search fails to find anything, but the root_el has room. We
1423 * pass NULL back in *lowest_eb_bh, but still return '0'
1424 *
1425 * 3) the search fails to find anything AND the root_el is full, in
1426 * which case we return > 0
1427 *
1428 * return status < 0 indicates an error.
1429 */
1432 {
1434 u64 blkno;
1451 }
1460 }
1469 }
1479 }
1480 }
1482 /* If we didn't find one and the fe doesn't have any room,
1483 * then return '1' */
1489 bail:
1493 }
1495 /*
1496 * Grow a b-tree so that it has more records.
1497 *
1498 * We might shift the tree depth in which case existing paths should
1499 * be considered invalid.
1500 *
1501 * Tree depth after the grow is returned via *final_depth.
1502 *
1503 * *last_eb_bh will be updated by ocfs2_add_branch().
1504 */
1508 {
1521 }
1523 /* We traveled all the way to the bottom of the allocation tree
1524 * and didn't find room for any more extents - we need to add
1525 * another tree level */
1531 depth);
1533 /* ocfs2_shift_tree_depth will return us a buffer with
1534 * the new extent block (so we can pass that to
1535 * ocfs2_add_branch). */
1540 }
1541 depth++;
1543 /*
1544 * Special case: we have room now if we shifted from
1545 * tree_depth 0, so no more work needs to be done.
1546 *
1547 * We won't be calling add_branch, so pass
1548 * back *last_eb_bh as the new leaf. At depth
1549 * zero, it should always be null so there's
1550 * no reason to brelse.
1551 */
1556 }
1557 }
1559 /* call ocfs2_add_branch to add the final part of the tree with
1560 * the new data. */
1562 meta_ac);
1566 }
1568 out:
1573 }
1575 /*
1576 * This function will discard the rightmost extent record.
1577 */
1579 {
1585 /* This will cause us to go off the end of our extent list. */
1591 }
1595 {
1605 /* The tree code before us didn't allow enough room in the leaf. */
1608 /*
1609 * The easiest way to approach this is to just remove the
1610 * empty extent and temporarily decrement next_free.
1611 */
1613 /*
1614 * If next_free was 1 (only an empty extent), this
1615 * loop won't execute, which is fine. We still want
1616 * the decrement above to happen.
1617 */
1621 next_free--;
1622 }
1624 /*
1625 * Figure out what the new record index should be.
1626 */
1632 }
1643 /*
1644 * No need to memmove if we're just adding to the tail.
1645 */
1653 num_bytes);
1654 }
1656 /*
1657 * Either we had an empty extent, and need to re-increment or
1658 * there was no empty extent on a non full rightmost leaf node,
1659 * in which case we still need to increment.
1660 */
1661 next_free++;
1663 /*
1664 * Make sure none of the math above just messed up our tree.
1665 */
1670 }
1673 {
1679 num_recs--;
1685 }
1686 }
1688 /*
1689 * Create an empty extent record .
1690 *
1691 * l_next_free_rec may be updated.
1692 *
1693 * If an empty extent already exists do nothing.
1694 */
1696 {
1715 set_and_inc:
1718 }
1720 /*
1721 * For a rotation which involves two leaf nodes, the "root node" is
1722 * the lowest level tree node which contains a path to both leafs. This
1723 * resulting set of information can be used to form a complete "subtree"
1724 *
1725 * This function is passed two full paths from the dinode down to a
1726 * pair of adjacent leaves. It's task is to figure out which path
1727 * index contains the subtree root - this can be the root index itself
1728 * in a worst-case rotation.
1729 *
1730 * The array index of the subtree root is passed back.
1731 */
1735 {
1738 /*
1739 * Check that the caller passed in two paths from the same tree.
1740 */
1744 i++;
1746 /*
1747 * The caller didn't pass two adjacent paths.
1748 */
1760 }
1764 /*
1765 * Traverse a btree path in search of cpos, starting at root_el.
1766 *
1767 * This code can be called with a cpos larger than the tree, in which
1768 * case it will return the rightmost path.
1769 */
1773 {
1775 u32 range;
1776 u64 blkno;
1792 }
1797 /*
1798 * In the case that cpos is off the allocation
1799 * tree, this should just wind up returning the
1800 * rightmost record.
1801 */
1806 }
1816 }
1824 }
1839 }
1843 }
1845 out:
1846 /*
1847 * Catch any trailing bh that the loop didn't handle.
1848 */
1852 }
1854 /*
1855 * Given an initialized path (that is, it has a valid root extent
1856 * list), this function will traverse the btree in search of the path
1857 * which would contain cpos.
1858 *
1859 * The path traveled is recorded in the path structure.
1860 *
1861 * Note that this will not do any comparisons on leaf node extent
1862 * records, so it will work fine in the case that we just added a tree
1863 * branch.
1864 */
1868 };
1870 {
1876 }
1879 {
1886 }
1889 {
1894 /* We want to retain only the leaf block. */
1898 }
1899 }
1900 /*
1901 * Find the leaf block in the tree which would contain cpos. No
1902 * checking of the actual leaf is done.
1903 *
1904 * Some paths want to call this instead of allocating a path structure
1905 * and calling ocfs2_find_path().
1906 *
1907 * This function doesn't handle non btree extent lists.
1908 */
1912 {
1920 }
1923 out:
1925 }
1927 /*
1928 * Adjust the adjacent records (left_rec, right_rec) involved in a rotation.
1929 *
1930 * Basically, we've moved stuff around at the bottom of the tree and
1931 * we need to fix up the extent records above the changes to reflect
1932 * the new changes.
1933 *
1934 * left_rec: the record on the left.
1935 * left_child_el: is the child list pointed to by left_rec
1936 * right_rec: the record to the right of left_rec
1937 * right_child_el: is the child list pointed to by right_rec
1938 *
1939 * By definition, this only works on interior nodes.
1940 */
1945 {
1948 /*
1949 * Interior nodes never have holes. Their cpos is the cpos of
1950 * the leftmost record in their child list. Their cluster
1951 * count covers the full theoretical range of their child list
1952 * - the range between their cpos and the cpos of the record
1953 * immediately to their right.
1954 */
1960 }
1964 /*
1965 * Calculate the rightmost cluster count boundary before
1966 * moving cpos - we will need to adjust clusters after
1967 * updating e_cpos to keep the same highest cluster count.
1968 */
1977 }
1979 /*
1980 * Adjust the adjacent root node records involved in a
1981 * rotation. left_el_blkno is passed in as a key so that we can easily
1982 * find it's index in the root list.
1983 */
1987 u64 left_el_blkno)
1988 {
1997 }
1999 /*
2000 * The path walking code should have never returned a root and
2001 * two paths which are not adjacent.
2002 */
2007 }
2009 /*
2010 * We've changed a leaf block (in right_path) and need to reflect that
2011 * change back up the subtree.
2012 *
2013 * This happens in multiple places:
2014 * - When we've moved an extent record from the left path leaf to the right
2015 * path leaf to make room for an empty extent in the left path leaf.
2016 * - When our insert into the right path leaf is at the leftmost edge
2017 * and requires an update of the path immediately to it's left. This
2018 * can occur at the end of some types of rotation and appending inserts.
2019 * - When we've adjusted the last extent record in the left path leaf and the
2020 * 1st extent record in the right path leaf during cross extent block merge.
2021 */
2026 {
2032 /*
2033 * Update the counts and position values within all the
2034 * interior nodes to reflect the leaf rotation we just did.
2035 *
2036 * The root node is handled below the loop.
2037 *
2038 * We begin the loop with right_el and left_el pointing to the
2039 * leaf lists and work our way up.
2040 *
2041 * NOTE: within this loop, left_el and right_el always refer
2042 * to the *child* lists.
2043 */
2049 /*
2050 * One nice property of knowing that all of these
2051 * nodes are below the root is that we only deal with
2052 * the leftmost right node record and the rightmost
2053 * left node record.
2054 */
2063 right_el);
2068 /*
2069 * Setup our list pointers now so that the current
2070 * parents become children in the next iteration.
2071 */
2074 }
2076 /*
2077 * At the root node, adjust the two adjacent records which
2078 * begin our path to the leaves.
2079 */
2091 }
2098 {
2116 }
2118 /*
2119 * This extent block may already have an empty record, so we
2120 * return early if so.
2121 */
2129 subtree_index);
2133 }
2141 }
2148 }
2149 }
2154 /* This is a code error, not a disk corruption. */
2164 /* Do the copy now. */
2169 /*
2170 * Clear out the record we just copied and shift everything
2171 * over, leaving an empty extent in the left leaf.
2172 *
2173 * We temporarily subtract from next_free_rec so that the
2174 * shift will lose the tail record (which is now defunct).
2175 */
2184 subtree_index);
2186 out:
2188 }
2190 /*
2191 * Given a full path, determine what cpos value would return us a path
2192 * containing the leaf immediately to the left of the current one.
2193 *
2194 * Will return zero if the path passed in is already the leftmost path.
2195 */
2198 {
2200 u64 blkno;
2209 /* Start at the tree node just above the leaf and work our way up. */
2214 /*
2215 * Find the extent record just before the one in our
2216 * path.
2217 */
2222 /*
2223 * We've determined that the
2224 * path specified is already
2225 * the leftmost one - return a
2226 * cpos of zero.
2227 */
2229 }
2230 /*
2231 * The leftmost record points to our
2232 * leaf - we need to travel up the
2233 * tree one level.
2234 */
2236 }
2243 }
2244 }
2246 /*
2247 * If we got here, we never found a valid node where
2248 * the tree indicated one should be.
2249 */
2255 next_node:
2257 i--;
2258 }
2260 out:
2262 }
2264 /*
2265 * Extend the transaction by enough credits to complete the rotation,
2266 * and still leave at least the original number of credits allocated
2267 * to this transaction.
2268 */
2272 {
2281 }
2283 /*
2284 * Trap the case where we're inserting into the theoretical range past
2285 * the _actual_ left leaf range. Otherwise, we'll rotate a record
2286 * whose cpos is less than ours into the right leaf.
2287 *
2288 * It's only necessary to look at the rightmost record of the left
2289 * leaf because the logic that calls us should ensure that the
2290 * theoretical ranges in the path components above the leaves are
2291 * correct.
2292 */
2294 u32 insert_cpos)
2295 {
2307 }
2310 {
2320 /* Empty list. */
2324 }
2330 }
2332 /*
2333 * Rotate all the records in a btree right one record, starting at insert_cpos.
2334 *
2335 * The path to the rightmost leaf should be passed in.
2336 *
2337 * The array is assumed to be large enough to hold an entire path (tree depth).
2338 *
2339 * Upon successful return from this function:
2340 *
2341 * - The 'right_path' array will contain a path to the leaf block
2342 * whose range contains e_cpos.
2343 * - That leaf block will have a single empty extent in list index 0.
2344 * - In the case that the rotation requires a post-insert update,
2345 * *ret_left_path will contain a valid path which can be passed to
2346 * ocfs2_insert_path().
2347 */
2351 u32 insert_cpos,
2354 {
2356 u32 cpos;
2367 }
2373 }
2379 /*
2380 * What we want to do here is:
2381 *
2382 * 1) Start with the rightmost path.
2383 *
2384 * 2) Determine a path to the leaf block directly to the left
2385 * of that leaf.
2386 *
2387 * 3) Determine the 'subtree root' - the lowest level tree node
2388 * which contains a path to both leaves.
2389 *
2390 * 4) Rotate the subtree.
2391 *
2392 * 5) Find the next subtree by considering the left path to be
2393 * the new right path.
2394 *
2395 * The check at the top of this while loop also accepts
2396 * insert_cpos == cpos because cpos is only a _theoretical_
2397 * value to get us the left path - insert_cpos might very well
2398 * be filling that hole.
2399 *
2400 * Stop at a cpos of '0' because we either started at the
2401 * leftmost branch (i.e., a tree with one branch and a
2402 * rotation inside of it), or we've gone as far as we can in
2403 * rotating subtrees.
2404 */
2415 }
2419 "Owner %llu: error during insert of %u "
2420 "(left path cpos %u) results in two identical "
2429 insert_cpos)) {
2431 /*
2432 * We've rotated the tree as much as we
2433 * should. The rest is up to
2434 * ocfs2_insert_path() to complete, after the
2435 * record insertion. We indicate this
2436 * situation by returning the left path.
2437 *
2438 * The reason we don't adjust the records here
2439 * before the record insert is that an error
2440 * later might break the rule where a parent
2441 * record e_cpos will reflect the actual
2442 * e_cpos of the 1st nonempty record of the
2443 * child list.
2444 */
2447 }
2461 }
2468 }
2472 insert_cpos)) {
2473 /*
2474 * A rotate moves the rightmost left leaf
2475 * record over to the leftmost right leaf
2476 * slot. If we're doing an extent split
2477 * instead of a real insert, then we have to
2478 * check that the extent to be split wasn't
2479 * just moved over. If it was, then we can
2480 * exit here, passing left_path back -
2481 * ocfs2_split_extent() is smart enough to
2482 * search both leaves.
2483 */
2486 }
2488 /*
2489 * There is no need to re-read the next right path
2490 * as we know that it'll be our current left
2491 * path. Optimize by copying values instead.
2492 */
2499 }
2500 }
2502 out:
2505 out_ret_path:
2507 }
2512 {
2517 u32 range;
2523 }
2525 /* Path should always be rightmost. */
2544 }
2545 out:
2547 }
2553 {
2563 /*
2564 * Not all nodes might have had their final count
2565 * decremented by the caller - handle this here.
2566 */
2570 "Inode %llu, attempted to remove extent block "
2579 }
2591 }
2592 }
2600 {
2628 }
2637 {
2655 /*
2656 * It's legal for us to proceed if the right leaf is
2657 * the rightmost one and it has an empty extent. There
2658 * are two cases to handle - whether the leaf will be
2659 * empty after removal or not. If the leaf isn't empty
2660 * then just remove the empty extent up front. The
2661 * next block will handle empty leaves by flagging
2662 * them for unlink.
2663 *
2664 * Non rightmost leaves will throw -EAGAIN and the
2665 * caller can manually move the subtree and retry.
2666 */
2674 OCFS2_JOURNAL_ACCESS_WRITE);
2678 }
2683 }
2687 /*
2688 * We have to update i_last_eb_blk during the meta
2689 * data delete.
2690 */
2692 OCFS2_JOURNAL_ACCESS_WRITE);
2696 }
2699 }
2701 /*
2702 * Getting here with an empty extent in the right path implies
2703 * that it's the rightmost path and will be deleted.
2704 */
2708 subtree_index);
2712 }
2720 }
2727 }
2728 }
2731 /*
2732 * Only do this if we're moving a real
2733 * record. Otherwise, the action is delayed until
2734 * after removal of the right path in which case we
2735 * can do a simple shift to remove the empty extent.
2736 */
2740 }
2742 /*
2743 * Move recs over to get rid of empty extent, decrease
2744 * next_free. This is allowed to remove the last
2745 * extent in our leaf (setting l_next_free_rec to
2746 * zero) - the delete code below won't care.
2747 */
2749 }
2758 left_path);
2762 }
2767 /*
2768 * Removal of the extent in the left leaf was skipped
2769 * above so we could delete the right path
2770 * 1st.
2771 */
2780 subtree_index);
2782 out:
2784 }
2786 /*
2787 * Given a full path, determine what cpos value would return us a path
2788 * containing the leaf immediately to the right of the current one.
2789 *
2790 * Will return zero if the path passed in is already the rightmost path.
2791 *
2792 * This looks similar, but is subtly different to
2793 * ocfs2_find_cpos_for_left_leaf().
2794 */
2797 {
2799 u64 blkno;
2809 /* Start at the tree node just above the leaf and work our way up. */
2816 /*
2817 * Find the extent record just after the one in our
2818 * path.
2819 */
2825 /*
2826 * We've determined that the
2827 * path specified is already
2828 * the rightmost one - return a
2829 * cpos of zero.
2830 */
2832 }
2833 /*
2834 * The rightmost record points to our
2835 * leaf - we need to travel up the
2836 * tree one level.
2837 */
2839 }
2843 }
2844 }
2846 /*
2847 * If we got here, we never found a valid node where
2848 * the tree indicated one should be.
2849 */
2855 next_node:
2857 i--;
2858 }
2860 out:
2862 }
2867 {
2880 }
2885 out:
2887 }
2895 {
2897 u32 right_cpos;
2911 }
2918 }
2927 }
2934 }
2937 right_path);
2949 }
2951 /*
2952 * Caller might still want to make changes to the
2953 * tree root, so re-add it to the journal here.
2954 */
2960 }
2966 /*
2967 * The rotation has to temporarily stop due to
2968 * the right subtree having an empty
2969 * extent. Pass it back to the caller for a
2970 * fixup.
2971 */
2975 }
2979 }
2981 /*
2982 * The subtree rotate might have removed records on
2983 * the rightmost edge. If so, then rotation is
2984 * complete.
2985 */
2996 }
2997 }
2999 out:
3004 }
3010 {
3012 u32 cpos;
3025 }
3032 }
3035 /*
3036 * We have a path to the left of this one - it needs
3037 * an update too.
3038 */
3044 }
3050 }
3056 }
3063 left_path);
3067 }
3072 /*
3073 * 'path' is also the leftmost path which
3074 * means it must be the only one. This gets
3075 * handled differently because we want to
3076 * revert the root back to having extents
3077 * in-line.
3078 */
3087 }
3091 out:
3094 }
3100 {
3110 }
3118 }
3120 /*
3121 * Left rotation of btree records.
3122 *
3123 * In many ways, this is (unsurprisingly) the opposite of right
3124 * rotation. We start at some non-rightmost path containing an empty
3125 * extent in the leaf block. The code works its way to the rightmost
3126 * path by rotating records to the left in every subtree.
3127 *
3128 * This is used by any code which reduces the number of extent records
3129 * in a leaf. After removal, an empty record should be placed in the
3130 * leftmost list position.
3131 *
3132 * This won't handle a length update of the rightmost path records if
3133 * the rightmost tree leaf record is removed so the caller is
3134 * responsible for detecting and correcting that.
3135 */
3140 {
3151 rightmost_no_delete:
3152 /*
3153 * Inline extents. This is trivially handled, so do
3154 * it up front.
3155 */
3160 }
3162 /*
3163 * Handle rightmost branch now. There's several cases:
3164 * 1) simple rotation leaving records in there. That's trivial.
3165 * 2) rotation requiring a branch delete - there's no more
3166 * records left. Two cases of this:
3167 * a) There are branches to the left.
3168 * b) This is also the leftmost (the only) branch.
3169 *
3170 * 1) is handled via ocfs2_rotate_rightmost_leaf_left()
3171 * 2a) we need the left branch so that we can update it with the unlink
3172 * 2b) we need to bring the root back to inline extents.
3173 */
3178 /*
3179 * This gets a bit tricky if we're going to delete the
3180 * rightmost path. Get the other cases out of the way
3181 * 1st.
3182 */
3193 }
3195 /*
3196 * XXX: The caller can not trust "path" any more after
3197 * this as it will have been deleted. What do we do?
3198 *
3199 * In theory the rotate-for-merge code will never get
3200 * here because it'll always ask for a rotate in a
3201 * nonempty list.
3202 */
3205 dealloc);
3209 }
3211 /*
3212 * Now we can loop, remembering the path we get from -EAGAIN
3213 * and restarting from there.
3214 */
3215 try_rotate:
3221 }
3233 }
3240 }
3242 out:
3246 }
3250 {
3255 /*
3256 * We consumed all of the merged-from record. An empty
3257 * extent cannot exist anywhere but the 1st array
3258 * position, so move things over if the merged-from
3259 * record doesn't occupy that position.
3260 *
3261 * This creates a new empty extent so the caller
3262 * should be smart enough to have removed any existing
3263 * ones.
3264 */
3269 }
3271 /*
3272 * Always memset - the caller doesn't check whether it
3273 * created an empty extent, so there could be junk in
3274 * the other fields.
3275 */
3277 }
3278 }
3283 {
3285 u32 right_cpos;
3291 /* This function shouldn't be called for non-trees. */
3302 }
3304 /* This function shouldn't be called for the rightmost leaf. */
3312 }
3318 }
3321 out:
3325 }
3327 /*
3328 * Remove split_rec clusters from the record at index and merge them
3329 * onto the beginning of the record "next" to it.
3330 * For index < l_count - 1, the next means the extent rec at index + 1.
3331 * For index == l_count - 1, the "next" means the 1st extent rec of the
3332 * next extent block.
3333 */
3339 {
3356 /* we meet with a cross extent block merge. */
3361 }
3370 }
3377 right_path);
3381 right_path);
3385 }
3391 subtree_index);
3395 }
3404 }
3411 }
3412 }
3417 }
3424 }
3431 split_clusters));
3440 subtree_index);
3441 }
3442 out:
3445 }
3450 {
3452 u32 left_cpos;
3457 /* This function shouldn't be called for non-trees. */
3465 }
3467 /* This function shouldn't be called for the leftmost leaf. */
3475 }
3481 }
3484 out:
3488 }
3490 /*
3491 * Remove split_rec clusters from the record at index and merge them
3492 * onto the tail of the record "before" it.
3493 * For index > 0, the "before" means the extent rec at index - 1.
3494 *
3495 * For index == 0, the "before" means the last record of the previous
3496 * extent block. And there is also a situation that we may need to
3497 * remove the rightmost leaf extent block in the right_path and change
3498 * the right path to indicate the new rightmost path.
3499 */
3506 {
3521 /* we meet with a cross extent block merge. */
3526 }
3539 right_path);
3543 left_path);
3547 }
3553 subtree_index);
3557 }
3566 }
3573 }
3574 }
3579 }
3586 }
3589 /*
3590 * The easy case - we can just plop the record right in.
3591 */
3601 split_clusters));
3610 /*
3611 * In the situation that the right_rec is empty and the extent
3612 * block is empty also, ocfs2_complete_edge_insert can't handle
3613 * it and we need to delete the right extent block.
3614 */
3617 /* extend credit for ocfs2_remove_rightmost_path */
3620 right_path);
3624 }
3627 right_path,
3628 dealloc);
3632 }
3634 /* Now the rightmost extent block has been deleted.
3635 * So we use the new rightmost path.
3636 */
3642 }
3643 out:
3646 }
3655 {
3663 /* extend credit for ocfs2_remove_rightmost_path */
3666 path);
3670 }
3671 /*
3672 * The merge code will need to create an empty
3673 * extent to take the place of the newly
3674 * emptied slot. Remove any pre-existing empty
3675 * extents - having more than one in a leaf is
3676 * illegal.
3677 */
3682 }
3683 split_index--;
3685 }
3688 /*
3689 * Left-right contig implies this.
3690 */
3693 /*
3694 * Since the leftright insert always covers the entire
3695 * extent, this call will delete the insert record
3696 * entirely, resulting in an empty extent record added to
3697 * the extent block.
3698 *
3699 * Since the adding of an empty extent shifts
3700 * everything back to the right, there's no need to
3701 * update split_index here.
3702 *
3703 * When the split_index is zero, we need to merge it to the
3704 * prevoius extent block. It is more efficient and easier
3705 * if we do merge_right first and merge_left later.
3706 */
3708 split_index);
3712 }
3714 /*
3715 * We can only get this from logic error above.
3716 */
3719 /* extend credit for ocfs2_remove_rightmost_path */
3722 path);
3726 }
3728 /* The merge left us with an empty extent, remove it. */
3733 }
3737 /*
3738 * Note that we don't pass split_rec here on purpose -
3739 * we've merged it into the rec already.
3740 */
3747 }
3749 /* extend credit for ocfs2_remove_rightmost_path */
3752 path);
3756 }
3759 /*
3760 * Error from this last rotate is not critical, so
3761 * print but don't bubble it up.
3762 */
3767 /*
3768 * Merge a record to the left or right.
3769 *
3770 * 'contig_type' is relative to the existing record,
3771 * so for example, if we're "right contig", it's to
3772 * the record on the left (hence the left merge).
3773 */
3777 split_index);
3781 }
3785 split_index);
3789 }
3790 }
3793 /* extend credit for ocfs2_remove_rightmost_path */
3796 path);
3801 }
3803 /*
3804 * The merge may have left an empty extent in
3805 * our leaf. Try to rotate it away.
3806 */
3808 dealloc);
3812 }
3813 }
3815 out:
3817 }
3823 {
3824 u64 len_blocks;
3830 /*
3831 * Region is on the left edge of the existing
3832 * record.
3833 */
3840 /*
3841 * Region is on the right edge of the existing
3842 * record.
3843 */
3846 }
3847 }
3849 /*
3850 * Do the final bits of extent record insertion at the target leaf
3851 * list. If this leaf is part of an allocation tree, it is assumed
3852 * that the tree above has been prepared.
3853 */
3858 {
3871 insert_rec);
3873 }
3875 /*
3876 * Contiguous insert - either left or right.
3877 */
3883 }
3887 }
3889 /*
3890 * Handle insert into an empty leaf.
3891 */
3898 }
3900 /*
3901 * Appending insert.
3902 */
3912 "owner %llu, depth %u, count %u, next free %u, "
3913 "rec.cpos %u, rec.clusters %u, "
3923 i++;
3927 }
3929 rotate:
3930 /*
3931 * Ok, we have to rotate.
3932 *
3933 * At this point, it is safe to assume that inserting into an
3934 * empty leaf and appending to a leaf have both been handled
3935 * above.
3936 *
3937 * This leaf needs to have space, either by the empty 1st
3938 * extent record, or by virtue of an l_next_rec < l_count.
3939 */
3941 }
3947 {
3953 /*
3954 * Update everything except the leaf block.
3955 */
3967 }
3978 }
3979 }
3986 {
3993 /*
3994 * This shouldn't happen for non-trees. The extent rec cluster
3995 * count manipulation below only works for interior nodes.
3996 */
3999 /*
4000 * If our appending insert is at the leftmost edge of a leaf,
4001 * then we might need to update the rightmost records of the
4002 * neighboring path.
4003 */
4008 u32 left_cpos;
4015 }
4021 left_cpos);
4023 /*
4024 * No need to worry if the append is already in the
4025 * leftmost leaf.
4026 */
4033 }
4036 left_cpos);
4040 }
4042 /*
4043 * ocfs2_insert_path() will pass the left_path to the
4044 * journal for us.
4045 */
4046 }
4047 }
4053 }
4059 out:
4064 }
4071 {
4088 /*
4089 * This typically means that the record
4090 * started in the left path but moved to the
4091 * right as a result of rotation. We either
4092 * move the existing record to the left, or we
4093 * do the later insert there.
4094 *
4095 * In this case, the left path should always
4096 * exist as the rotate code will have passed
4097 * it back for a post-insert update.
4098 */
4101 /*
4102 * It's a left split. Since we know
4103 * that the rotate code gave us an
4104 * empty extent in the left path, we
4105 * can just do the insert there.
4106 */
4109 /*
4110 * Right split - we have to move the
4111 * existing record over to the left
4112 * leaf. The insert will be into the
4113 * newly created empty extent in the
4114 * right leaf.
4115 */
4123 }
4124 }
4128 /*
4129 * Left path is easy - we can just allow the insert to
4130 * happen.
4131 */
4136 }
4142 }
4144 /*
4145 * This function only does inserts on an allocation b-tree. For tree
4146 * depth = 0, ocfs2_insert_at_leaf() is called directly.
4147 *
4148 * right_path is the path we want to do the actual insert
4149 * in. left_path should only be passed in if we need to update that
4150 * portion of the tree after an edge insert.
4151 */
4158 {
4163 /*
4164 * There's a chance that left_path got passed back to
4165 * us without being accounted for in the
4166 * journal. Extend our transaction here to be sure we
4167 * can change those blocks.
4168 */
4173 }
4179 }
4180 }
4182 /*
4183 * Pass both paths to the journal. The majority of inserts
4184 * will be touching all components anyway.
4185 */
4190 }
4193 /*
4194 * We could call ocfs2_insert_at_leaf() for some types
4195 * of splits, but it's easier to just let one separate
4196 * function sort it all out.
4197 */
4201 /*
4202 * Split might have modified either leaf and we don't
4203 * have a guarantee that the later edge insert will
4204 * dirty this for us.
4205 */
4211 insert);
4216 /*
4217 * The rotate code has indicated that we need to fix
4218 * up portions of the tree after the insert.
4219 *
4220 * XXX: Should we extend the transaction here?
4221 */
4223 right_path);
4225 subtree_index);
4226 }
4229 out:
4231 }
4237 {
4239 u32 cpos;
4247 OCFS2_JOURNAL_ACCESS_WRITE);
4251 }
4256 }
4263 }
4265 /*
4266 * Determine the path to start with. Rotations need the
4267 * rightmost path, everything else can go directly to the
4268 * target leaf.
4269 */
4275 }
4281 }
4283 /*
4284 * Rotations and appends need special treatment - they modify
4285 * parts of the tree's above them.
4286 *
4287 * Both might pass back a path immediate to the left of the
4288 * one being inserted to. This will be cause
4289 * ocfs2_insert_path() to modify the rightmost records of
4290 * left_path to account for an edge insert.
4291 *
4292 * XXX: When modifying this code, keep in mind that an insert
4293 * can wind up skipping both of these two special cases...
4294 */
4302 }
4304 /*
4305 * ocfs2_rotate_tree_right() might have extended the
4306 * transaction without re-journaling our tree root.
4307 */
4309 OCFS2_JOURNAL_ACCESS_WRITE);
4313 }
4321 }
4322 }
4329 }
4331 out_update_clusters:
4338 out:
4343 }
4350 {
4374 }
4377 left_cpos);
4388 "Extent block #%llu has an invalid l_next_free_rec of %d. It should have matched the l_count of %d\n",
4394 }
4397 }
4398 }
4400 /*
4401 * We're careful to check for an empty extent record here -
4402 * the merge code will know what to do if it sees one.
4403 */
4410 }
4411 }
4430 }
4448 }
4450 }
4451 }
4462 }
4464 free_right_path:
4466 free_left_path:
4468 exit:
4473 }
4479 {
4487 insert_rec);
4491 }
4492 }
4501 /*
4502 * Caller might want us to limit the size of extents, don't
4503 * calculate contiguousness if we might exceed that limit.
4504 */
4508 }
4509 }
4511 /*
4512 * This should only be called against the righmost leaf extent list.
4513 *
4514 * ocfs2_figure_appending_type() will figure out whether we'll have to
4515 * insert at the tail of the rightmost leaf.
4516 *
4517 * This should also work against the root extent list for tree's with 0
4518 * depth. If we consider the root extent list to be the rightmost leaf node
4519 * then the logic here makes sense.
4520 */
4524 {
4537 /* Were all records empty? */
4540 }
4551 set_tail_append:
4553 }
4555 /*
4556 * Helper function called at the beginning of an insert.
4557 *
4558 * This computes a few things that are commonly used in the process of
4559 * inserting into the btree:
4560 * - Whether the new extent is contiguous with an existing one.
4561 * - The current tree depth.
4562 * - Whether the insert is an appending one.
4563 * - The total # of free records in the tree.
4564 *
4565 * All of the information is stored on the ocfs2_insert_type
4566 * structure.
4567 */
4573 {
4586 /*
4587 * If we have tree depth, we read in the
4588 * rightmost extent block ahead of time as
4589 * ocfs2_figure_insert_type() and ocfs2_add_branch()
4590 * may want it later.
4591 */
4598 }
4601 }
4603 /*
4604 * Unless we have a contiguous insert, we'll need to know if
4605 * there is room left in our allocation tree for another
4606 * extent record.
4607 *
4608 * XXX: This test is simplistic, we can search for empty
4609 * extent records too.
4610 */
4618 }
4625 }
4627 /*
4628 * In the case that we're inserting past what the tree
4629 * currently accounts for, ocfs2_find_path() will return for
4630 * us the rightmost tree path. This is accounted for below in
4631 * the appending code.
4632 */
4637 }
4641 /*
4642 * Now that we have the path, there's two things we want to determine:
4643 * 1) Contiguousness (also set contig_index if this is so)
4644 *
4645 * 2) Are we doing an append? We can trivially break this up
4646 * into two types of appends: simple record append, or a
4647 * rotate inside the tail leaf.
4648 */
4651 /*
4652 * The insert code isn't quite ready to deal with all cases of
4653 * left contiguousness. Specifically, if it's an insert into
4654 * the 1st record in a leaf, it will require the adjustment of
4655 * cluster count on the last record of the path directly to it's
4656 * left. For now, just catch that case and fool the layers
4657 * above us. This works just fine for tree_depth == 0, which
4658 * is why we allow that above.
4659 */
4664 /*
4665 * Ok, so we can simply compare against last_eb to figure out
4666 * whether the path doesn't exist. This will only happen in
4667 * the case that we're doing a tail append, so maybe we can
4668 * take advantage of that information somehow.
4669 */
4672 /*
4673 * Ok, ocfs2_find_path() returned us the rightmost
4674 * tree path. This might be an appending insert. There are
4675 * two cases:
4676 * 1) We're doing a true append at the tail:
4677 * -This might even be off the end of the leaf
4678 * 2) We're "appending" by rotating in the tail
4679 */
4681 }
4683 out:
4688 else
4691 }
4693 /*
4694 * Insert an extent into a btree.
4695 *
4696 * The caller needs to update the owning btree's cluster count.
4697 */
4700 u32 cpos,
4701 u64 start_blk,
4702 u32 new_clusters,
4703 u8 flags,
4705 {
4725 }
4732 }
4741 meta_ac);
4745 }
4746 }
4748 /* Finally, we can add clusters. This might rotate the tree for us. */
4752 else
4755 bail:
4759 }
4761 /*
4762 * Allcate and add clusters into the extent b-tree.
4763 * The new clusters(clusters_to_add) will be inserted at logical_offset.
4764 * The extent b-tree's root is specified by et, and
4765 * it is not limited to the file storage. Any extent tree can use this
4766 * function if it implements the proper ocfs2_extent_tree.
4767 */
4771 u32 clusters_to_add,
4776 {
4782 u64 block;
4797 }
4799 /* there are two cases which could cause us to EAGAIN in the
4800 * we-need-more-metadata case:
4801 * 1) we haven't reserved *any*
4802 * 2) we are so fragmented, we've needed to add metadata too
4803 * many times. */
4816 }
4824 }
4828 /* reserve our write early -- insert_extent may update the tree root */
4830 OCFS2_JOURNAL_ACCESS_WRITE);
4835 }
4847 }
4858 }
4860 bail:
4865 else
4870 num_bits);
4871 }
4873 leave:
4878 }
4882 u32 cpos,
4884 {
4898 }
4907 {
4917 leftright:
4918 /*
4919 * Store a copy of the record on the stack - it might move
4920 * around as the tree is manipulated below.
4921 */
4931 }
4940 }
4941 }
4958 /*
4959 * Left/right split. We fake this as a right split
4960 * first and then make a second pass as a left split.
4961 */
4971 }
4977 }
4980 u32 cpos;
4983 do_leftright++;
4993 }
5001 cpos);
5004 }
5006 }
5007 out:
5010 }
5018 {
5026 }
5031 out:
5033 }
5035 /*
5036 * Split part or all of the extent record at split_index in the leaf
5037 * pointed to by path. Merge with the contiguous extent record if needed.
5038 *
5039 * Care is taken to handle contiguousness so as to not grow the tree.
5040 *
5041 * meta_ac is not strictly necessary - we only truly need it if growth
5042 * of the tree is required. All other cases will degrade into a less
5043 * optimal tree layout.
5044 *
5045 * last_eb_bh should be the rightmost leaf block for any extent
5046 * btree. Since a split may grow the tree or a merge might shrink it,
5047 * the caller cannot trust the contents of that buffer after this call.
5048 *
5049 * This code is optimized for readability - several passes might be
5050 * made over certain portions of the tree. All of those blocks will
5051 * have been brought into cache (and pinned via the journal), so the
5052 * extra overhead is not expressed in terms of disk reads.
5053 */
5061 {
5075 }
5078 split_index,
5079 split_rec,
5084 }
5086 /*
5087 * The core merge / split code wants to know how much room is
5088 * left in this allocation tree, so we pass the
5089 * rightmost extent list.
5090 */
5100 }
5110 else
5123 else
5135 }
5137 out:
5140 }
5142 /*
5143 * Change the flags of the already-existing extent at cpos for len clusters.
5144 *
5145 * new_flags: the flags we want to set.
5146 * clear_flags: the flags we want to clear.
5147 * phys: the new physical offset we want this new extent starts from.
5148 *
5149 * If the existing extent is larger than the request, initiate a
5150 * split. An attempt will be made at merging with adjacent extents.
5151 *
5152 * The caller is responsible for passing down meta_ac if we'll need it.
5153 */
5160 {
5174 }
5180 }
5188 cpos);
5191 }
5199 new_flags);
5201 }
5207 clear_flags);
5209 }
5223 dealloc);
5227 out:
5231 }
5233 /*
5234 * Mark the already-existing extent at cpos as written for len clusters.
5235 * This removes the unwritten extent flag.
5236 *
5237 * If the existing extent is larger than the request, initiate a
5238 * split. An attempt will be made at merging with adjacent extents.
5239 *
5240 * The caller is responsible for passing down meta_ac if we'll need it.
5241 */
5247 {
5255 ocfs2_error(inode->i_sb, "Inode %llu has unwritten extents that are being written to, but the feature bit is not set in the super block\n",
5259 }
5261 /*
5262 * XXX: This should be fixed up so that we just re-insert the
5263 * next extent records.
5264 */
5273 out:
5275 }
5281 {
5290 /*
5291 * Setup the record to split before we grow the tree.
5292 */
5306 }
5319 }
5324 meta_ac);
5328 }
5329 }
5341 out:
5344 }
5351 {
5362 /* extend credit for ocfs2_remove_rightmost_path */
5365 path);
5369 }
5375 }
5377 index--;
5378 }
5382 /*
5383 * Check whether this is the rightmost tree record. If
5384 * we remove all of this record or part of its right
5385 * edge then an update of the record lengths above it
5386 * will be required.
5387 */
5391 }
5396 /*
5397 * Changing the leftmost offset (via partial or whole
5398 * record truncate) of an interior (or rightmost) path
5399 * means we have to update the subtree that is formed
5400 * by this leaf and the one to it's left.
5401 *
5402 * There are two cases we can skip:
5403 * 1) Path is the leftmost one in our btree.
5404 * 2) The leaf is rightmost and will be empty after
5405 * we remove the extent record - the rotate code
5406 * knows how to update the newly formed edge.
5407 */
5413 }
5421 }
5424 left_cpos);
5428 }
5429 }
5430 }
5434 path);
5438 }
5444 }
5450 }
5463 /*
5464 * We skip the edge update if this path will
5465 * be deleted by the rotate code.
5466 */
5469 rec);
5470 }
5472 /* Remove leftmost portion of the record. */
5477 /* Remove rightmost portion of the record */
5482 /* Caller should have trapped this. */
5489 }
5496 subtree_index);
5497 }
5505 }
5507 out:
5510 }
5517 {
5524 /*
5525 * XXX: Why are we truncating to 0 instead of wherever this
5526 * affects us?
5527 */
5535 }
5541 }
5549 cpos);
5552 }
5554 /*
5555 * We have 3 cases of extent removal:
5556 * 1) Range covers the entire extent rec
5557 * 2) Range begins or ends on one edge of the extent rec
5558 * 3) Range is in the middle of the extent rec (no shared edges)
5559 *
5560 * For case 1 we remove the extent rec and left rotate to
5561 * fill the hole.
5562 *
5563 * For case 2 we just shrink the existing extent rec, with a
5564 * tree update if the shrinking edge is also the edge of an
5565 * extent block.
5566 *
5567 * For case 3 we do a right split to turn the extent rec into
5568 * something case 2 can handle.
5569 */
5587 }
5594 }
5596 /*
5597 * The split could have manipulated the tree enough to
5598 * move the record location, so we have to look for it again.
5599 */
5606 }
5614 cpos);
5617 }
5619 /*
5620 * Double check our values here. If anything is fishy,
5621 * it's easier to catch it at the top level.
5622 */
5634 }
5641 }
5642 }
5644 out:
5647 }
5649 /*
5650 * ocfs2_reserve_blocks_for_rec_trunc() would look basically the
5651 * same as ocfs2_lock_alloctors(), except for it accepts a blocks
5652 * number to reserve some extra blocks, and it only handles meta
5653 * data allocations.
5654 *
5655 * Currently, only ocfs2_remove_btree_range() uses it for truncating
5656 * and punching holes.
5657 */
5660 u32 extents_to_split,
5663 {
5675 }
5687 }
5688 }
5690 out:
5695 }
5696 }
5699 }
5706 {
5717 OCFS2_HAS_REFCOUNT_FL));
5725 }
5726 }
5729 refcount_loc,
5730 phys_blkno,
5731 len,
5737 }
5738 }
5741 extra_blocks);
5745 }
5754 }
5755 }
5763 }
5766 OCFS2_JOURNAL_ACCESS_WRITE);
5770 }
5779 }
5790 phys_blkno),
5793 else
5799 }
5801 out_commit:
5803 out:
5805 bail:
5813 }
5816 {
5825 "slot %d, invalid truncate log parameters: used = "
5829 }
5833 {
5837 /* No records, nothing to coalesce */
5846 }
5850 u64 start_blk,
5852 {
5866 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5867 * by the underlying call to ocfs2_read_inode_block(), so any
5868 * corruption is a code bug */
5875 "Truncate record count on #%llu invalid "
5881 /* Caller should have known to flush before calling us. */
5887 }
5890 OCFS2_JOURNAL_ACCESS_WRITE);
5894 }
5900 /*
5901 * Move index back to the record we are coalescing with.
5902 * ocfs2_truncate_log_can_coalesce() guarantees nonzero
5903 */
5904 index--;
5910 num_clusters);
5914 }
5920 bail:
5922 }
5928 {
5932 u64 start_blk;
5943 /* Caller has given us at least enough credits to
5944 * update the truncate log dinode */
5946 OCFS2_JOURNAL_ACCESS_WRITE);
5950 }
5961 /* if start_blk is not set, we ignore the record as
5962 * invalid. */
5970 num_clusters);
5974 }
5975 }
5978 OCFS2_TRUNCATE_LOG_FLUSH_ONE_REC);
5982 }
5983 i--;
5984 }
5988 bail:
5990 }
5992 /* Expects you to already be holding tl_inode->i_mutex */
5994 {
6009 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
6010 * by the underlying call to ocfs2_read_inode_block(), so any
6011 * corruption is a code bug */
6018 num_to_flush);
6022 }
6025 GLOBAL_BITMAP_SYSTEM_INODE,
6026 OCFS2_INVALID_SLOT);
6031 }
6039 }
6046 }
6049 data_alloc_bh);
6055 out_unlock:
6059 out_mutex:
6063 out:
6065 }
6068 {
6077 }
6080 {
6089 else
6091 }
6093 #define OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL (2 * HZ)
6096 {
6099 /* We want to push off log flushes while truncates are
6100 * still running. */
6105 OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL);
6106 }
6107 }
6109 /*
6110 * Try to flush truncate logs if we can free enough clusters from it.
6111 * As for return value, "< 0" means error, "0" no space and "1" means
6112 * we have freed enough spaces and let the caller try to allocate again.
6113 */
6116 {
6117 tid_t target;
6125 /*
6126 * Check whether we can succeed in allocating if we free
6127 * the truncate log.
6128 */
6136 }
6141 }
6142 out:
6144 }
6150 {
6156 TRUNCATE_LOG_SYSTEM_INODE,
6157 slot_num);
6162 }
6169 }
6173 bail:
6175 }
6177 /* called during the 1st stage of node recovery. we stamp a clean
6178 * truncate log and pass back a copy for processing later. if the
6179 * truncate log does not require processing, a *tl_copy is set to
6180 * NULL. */
6184 {
6199 }
6203 /* tl_bh is loaded from ocfs2_get_truncate_log_info(). It's
6204 * validated by the underlying call to ocfs2_read_inode_block(),
6205 * so any corruption is a code bug */
6217 }
6219 /* Assuming the write-out below goes well, this copy
6220 * will be passed back to recovery for processing. */
6223 /* All we need to do to clear the truncate log is set
6224 * tl_used. */
6232 }
6233 }
6235 bail:
6243 }
6246 }
6250 {
6254 u64 start_blk;
6262 }
6268 num_recs);
6277 }
6278 }
6285 }
6297 }
6298 }
6300 bail_up:
6304 }
6307 {
6323 }
6324 }
6327 {
6339 /* ocfs2_truncate_log_shutdown keys on the existence of
6340 * osb->osb_tl_inode so we don't set any of the osb variables
6341 * until we're sure all is well. */
6343 ocfs2_truncate_log_worker);
6349 }
6351 /*
6352 * Delayed de-allocation of suballocator blocks.
6353 *
6354 * Some sets of block de-allocations might involve multiple suballocator inodes.
6355 *
6356 * The locking for this can get extremely complicated, especially when
6357 * the suballocator inodes to delete from aren't known until deep
6358 * within an unrelated codepath.
6359 *
6360 * ocfs2_extent_block structures are a good example of this - an inode
6361 * btree could have been grown by any number of nodes each allocating
6362 * out of their own suballoc inode.
6363 *
6364 * These structures allow the delay of block de-allocation until a
6365 * later time, when locking of multiple cluster inodes won't cause
6366 * deadlock.
6367 */
6369 /*
6370 * Describe a single bit freed from a suballocator. For the block
6371 * suballocators, it represents one block. For the global cluster
6372 * allocator, it represents some clusters and free_bit indicates
6373 * clusters number.
6374 */
6377 u64 free_bg;
6378 u64 free_blk;
6380 };
6387 };
6393 {
6395 u64 bg_blkno;
6406 }
6414 }
6421 }
6426 else
6437 }
6443 }
6448 }
6450 out_journal:
6453 out_unlock:
6456 out_mutex:
6459 out:
6461 /* Premature exit may have left some dangling items. */
6465 }
6468 }
6472 {
6481 }
6491 }
6495 {
6509 }
6510 }
6517 }
6530 }
6531 }
6536 /* Premature exit may have left some dangling items. */
6540 }
6543 }
6547 {
6568 }
6572 }
6583 }
6586 }
6592 {
6600 }
6610 }
6612 }
6617 {
6627 }
6634 }
6648 out:
6650 }
6654 {
6660 }
6663 {
6667 }
6672 {
6682 /*
6683 * Need to set the buffers we zero'd into uptodate
6684 * here if they aren't - ocfs2_map_page_blocks()
6685 * might've skipped some
6686 */
6689 ocfs2_zero_func);
6696 }
6702 }
6707 {
6733 }
6734 out:
6737 }
6741 {
6745 loff_t last_page_bytes;
6758 }
6760 numpages++;
6761 index++;
6764 out:
6769 }
6774 }
6778 {
6785 }
6787 /*
6788 * Zero the area past i_size but still within an allocated
6789 * cluster. This avoids exposing nonzero data on subsequent file
6790 * extends.
6791 *
6792 * We need to call this before i_size is updated on the inode because
6793 * otherwise block_write_full_page() will skip writeout of pages past
6794 * i_size. The new_i_size parameter is passed for this reason.
6795 */
6798 {
6801 u64 phys;
6805 /*
6806 * File systems which don't support sparse files zero on every
6807 * extend.
6808 */
6818 }
6829 }
6831 /*
6832 * Tail is a hole, or is marked unwritten. In either case, we
6833 * can count on read and write to return/push zero's.
6834 */
6843 }
6848 /*
6849 * Initiate writeout of the pages we zero'd here. We don't
6850 * wait on them - the truncate_inode_pages() call later will
6851 * do that for us.
6852 */
6858 out:
6862 }
6866 {
6873 xattrsize);
6874 else
6877 }
6881 {
6887 }
6890 {
6899 /*
6900 * We clear the entire i_data structure here so that all
6901 * fields can be properly initialized.
6902 */
6907 }
6911 {
6935 }
6941 }
6942 }
6950 }
6953 OCFS2_JOURNAL_ACCESS_WRITE);
6957 }
6961 u64 phys;
6976 }
6978 /*
6979 * Save two copies, one for insert, and one that can
6980 * be changed by ocfs2_map_and_dirty_page() below.
6981 */
6984 /*
6985 * Non sparse file systems zero on extend, so no need
6986 * to do that now.
6987 */
6997 }
6999 /*
7000 * This should populate the 1st page for us and mark
7001 * it up to date.
7002 */
7008 }
7017 }
7030 /*
7031 * An error at this point should be extremely rare. If
7032 * this proves to be false, we could always re-build
7033 * the in-inode data from our pages.
7034 */
7041 }
7044 }
7046 out_unlock:
7050 out_commit:
7059 else
7064 num);
7065 }
7069 out:
7072 free_pages:
7075 }
7077 /*
7078 * It is expected, that by the time you call this function,
7079 * inode->i_size and fe->i_size have been adjusted.
7080 *
7081 * WARNING: This will kfree the truncate context
7082 */
7086 {
7107 ocfs2_journal_access_di);
7112 }
7116 start:
7117 /*
7118 * Check that we still have allocation to delete.
7119 */
7123 }
7125 /*
7126 * Truncate always works against the rightmost tree branch.
7127 */
7132 }
7136 new_highest_cpos,
7140 /*
7141 * By now, el will point to the extent list on the bottom most
7142 * portion of this tree. Only the tail record is considered in
7143 * each pass.
7144 *
7145 * We handle the following cases, in order:
7146 * - empty extent: delete the remaining branch
7147 * - remove the entire record
7148 * - remove a partial record
7149 * - no record needs to be removed (truncate has completed)
7150 */
7159 }
7167 /*
7168 * Lower levels depend on this never happening, but it's best
7169 * to check it up here before changing the tree.
7170 */
7180 }
7188 }
7190 /*
7191 * Truncate entire record.
7192 */
7197 /*
7198 * Partial truncate. it also should be
7199 * the last truncate we're doing.
7200 */
7207 /*
7208 * Truncate completed, leave happily.
7209 */
7212 }
7222 }
7223 }
7231 }
7235 /*
7236 * The check above will catch the case where we've truncated
7237 * away all allocation.
7238 */
7241 bail:
7252 }
7254 /*
7255 * 'start' is inclusive, 'end' is not.
7256 */
7259 {
7283 }
7290 }
7293 OCFS2_JOURNAL_ACCESS_WRITE);
7297 }
7302 /*
7303 * No need to worry about the data page here - it's been
7304 * truncated already and inline data doesn't need it for
7305 * pushing zero's to disk, so we'll let readpage pick it up
7306 * later.
7307 */
7311 }
7322 out_commit:
7325 out:
7327 }
7332 {
7342 }
7347 {
7369 }
7371 }
7377 }
7381 }
7387 }
7390 {
7409 GLOBAL_BITMAP_SYSTEM_INODE,
7410 OCFS2_INVALID_SLOT);
7415 }
7423 }
7429 }
7437 /* Determine first and last group to examine based on start and len */
7441 else
7450 else
7459 }
7469 }
7476 else
7478 }
7480 out_unlock:
7483 out_mutex:
7486 out:
7488 }