| blob | 93e6f029a3225323bffa574ec707a399d68c36e3 |
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;
2519 /*
2520 * In normal tree rotation process, we will never touch the
2521 * tree branch above subtree_index and ocfs2_extend_rotate_transaction
2522 * doesn't reserve the credits for them either.
2523 *
2524 * But we do have a special case here which will update the rightmost
2525 * records for all the bh in the path.
2526 * So we have to allocate extra credits and access them.
2527 */
2532 }
2538 }
2540 /* Path should always be rightmost. */
2559 }
2560 out:
2562 }
2568 {
2578 /*
2579 * Not all nodes might have had their final count
2580 * decremented by the caller - handle this here.
2581 */
2585 "Inode %llu, attempted to remove extent block "
2594 }
2606 }
2607 }
2615 {
2643 }
2652 {
2670 /*
2671 * It's legal for us to proceed if the right leaf is
2672 * the rightmost one and it has an empty extent. There
2673 * are two cases to handle - whether the leaf will be
2674 * empty after removal or not. If the leaf isn't empty
2675 * then just remove the empty extent up front. The
2676 * next block will handle empty leaves by flagging
2677 * them for unlink.
2678 *
2679 * Non rightmost leaves will throw -EAGAIN and the
2680 * caller can manually move the subtree and retry.
2681 */
2689 OCFS2_JOURNAL_ACCESS_WRITE);
2693 }
2698 }
2702 /*
2703 * We have to update i_last_eb_blk during the meta
2704 * data delete.
2705 */
2707 OCFS2_JOURNAL_ACCESS_WRITE);
2711 }
2714 }
2716 /*
2717 * Getting here with an empty extent in the right path implies
2718 * that it's the rightmost path and will be deleted.
2719 */
2723 subtree_index);
2727 }
2735 }
2742 }
2743 }
2746 /*
2747 * Only do this if we're moving a real
2748 * record. Otherwise, the action is delayed until
2749 * after removal of the right path in which case we
2750 * can do a simple shift to remove the empty extent.
2751 */
2755 }
2757 /*
2758 * Move recs over to get rid of empty extent, decrease
2759 * next_free. This is allowed to remove the last
2760 * extent in our leaf (setting l_next_free_rec to
2761 * zero) - the delete code below won't care.
2762 */
2764 }
2773 left_path);
2777 }
2782 /*
2783 * Removal of the extent in the left leaf was skipped
2784 * above so we could delete the right path
2785 * 1st.
2786 */
2795 subtree_index);
2797 out:
2799 }
2801 /*
2802 * Given a full path, determine what cpos value would return us a path
2803 * containing the leaf immediately to the right of the current one.
2804 *
2805 * Will return zero if the path passed in is already the rightmost path.
2806 *
2807 * This looks similar, but is subtly different to
2808 * ocfs2_find_cpos_for_left_leaf().
2809 */
2812 {
2814 u64 blkno;
2824 /* Start at the tree node just above the leaf and work our way up. */
2831 /*
2832 * Find the extent record just after the one in our
2833 * path.
2834 */
2840 /*
2841 * We've determined that the
2842 * path specified is already
2843 * the rightmost one - return a
2844 * cpos of zero.
2845 */
2847 }
2848 /*
2849 * The rightmost record points to our
2850 * leaf - we need to travel up the
2851 * tree one level.
2852 */
2854 }
2858 }
2859 }
2861 /*
2862 * If we got here, we never found a valid node where
2863 * the tree indicated one should be.
2864 */
2870 next_node:
2872 i--;
2873 }
2875 out:
2877 }
2882 {
2895 }
2900 out:
2902 }
2910 {
2912 u32 right_cpos;
2926 }
2933 }
2942 }
2949 }
2952 right_path);
2964 }
2966 /*
2967 * Caller might still want to make changes to the
2968 * tree root, so re-add it to the journal here.
2969 */
2975 }
2981 /*
2982 * The rotation has to temporarily stop due to
2983 * the right subtree having an empty
2984 * extent. Pass it back to the caller for a
2985 * fixup.
2986 */
2990 }
2994 }
2996 /*
2997 * The subtree rotate might have removed records on
2998 * the rightmost edge. If so, then rotation is
2999 * complete.
3000 */
3011 }
3012 }
3014 out:
3019 }
3025 {
3027 u32 cpos;
3036 /*
3037 * There's two ways we handle this depending on
3038 * whether path is the only existing one.
3039 */
3042 path);
3046 }
3052 }
3059 }
3062 /*
3063 * We have a path to the left of this one - it needs
3064 * an update too.
3065 */
3071 }
3077 }
3083 }
3090 left_path);
3094 }
3099 /*
3100 * 'path' is also the leftmost path which
3101 * means it must be the only one. This gets
3102 * handled differently because we want to
3103 * revert the root back to having extents
3104 * in-line.
3105 */
3114 }
3118 out:
3121 }
3127 {
3137 }
3145 }
3147 /*
3148 * Left rotation of btree records.
3149 *
3150 * In many ways, this is (unsurprisingly) the opposite of right
3151 * rotation. We start at some non-rightmost path containing an empty
3152 * extent in the leaf block. The code works its way to the rightmost
3153 * path by rotating records to the left in every subtree.
3154 *
3155 * This is used by any code which reduces the number of extent records
3156 * in a leaf. After removal, an empty record should be placed in the
3157 * leftmost list position.
3158 *
3159 * This won't handle a length update of the rightmost path records if
3160 * the rightmost tree leaf record is removed so the caller is
3161 * responsible for detecting and correcting that.
3162 */
3167 {
3178 rightmost_no_delete:
3179 /*
3180 * Inline extents. This is trivially handled, so do
3181 * it up front.
3182 */
3187 }
3189 /*
3190 * Handle rightmost branch now. There's several cases:
3191 * 1) simple rotation leaving records in there. That's trivial.
3192 * 2) rotation requiring a branch delete - there's no more
3193 * records left. Two cases of this:
3194 * a) There are branches to the left.
3195 * b) This is also the leftmost (the only) branch.
3196 *
3197 * 1) is handled via ocfs2_rotate_rightmost_leaf_left()
3198 * 2a) we need the left branch so that we can update it with the unlink
3199 * 2b) we need to bring the root back to inline extents.
3200 */
3205 /*
3206 * This gets a bit tricky if we're going to delete the
3207 * rightmost path. Get the other cases out of the way
3208 * 1st.
3209 */
3220 }
3222 /*
3223 * XXX: The caller can not trust "path" any more after
3224 * this as it will have been deleted. What do we do?
3225 *
3226 * In theory the rotate-for-merge code will never get
3227 * here because it'll always ask for a rotate in a
3228 * nonempty list.
3229 */
3232 dealloc);
3236 }
3238 /*
3239 * Now we can loop, remembering the path we get from -EAGAIN
3240 * and restarting from there.
3241 */
3242 try_rotate:
3248 }
3260 }
3267 }
3269 out:
3273 }
3277 {
3282 /*
3283 * We consumed all of the merged-from record. An empty
3284 * extent cannot exist anywhere but the 1st array
3285 * position, so move things over if the merged-from
3286 * record doesn't occupy that position.
3287 *
3288 * This creates a new empty extent so the caller
3289 * should be smart enough to have removed any existing
3290 * ones.
3291 */
3296 }
3298 /*
3299 * Always memset - the caller doesn't check whether it
3300 * created an empty extent, so there could be junk in
3301 * the other fields.
3302 */
3304 }
3305 }
3310 {
3312 u32 right_cpos;
3318 /* This function shouldn't be called for non-trees. */
3329 }
3331 /* This function shouldn't be called for the rightmost leaf. */
3339 }
3345 }
3348 out:
3352 }
3354 /*
3355 * Remove split_rec clusters from the record at index and merge them
3356 * onto the beginning of the record "next" to it.
3357 * For index < l_count - 1, the next means the extent rec at index + 1.
3358 * For index == l_count - 1, the "next" means the 1st extent rec of the
3359 * next extent block.
3360 */
3366 {
3383 /* we meet with a cross extent block merge. */
3388 }
3397 }
3404 right_path);
3408 right_path);
3412 }
3418 subtree_index);
3422 }
3431 }
3438 }
3439 }
3444 }
3451 }
3458 split_clusters));
3467 subtree_index);
3468 }
3469 out:
3472 }
3477 {
3479 u32 left_cpos;
3484 /* This function shouldn't be called for non-trees. */
3492 }
3494 /* This function shouldn't be called for the leftmost leaf. */
3502 }
3508 }
3511 out:
3515 }
3517 /*
3518 * Remove split_rec clusters from the record at index and merge them
3519 * onto the tail of the record "before" it.
3520 * For index > 0, the "before" means the extent rec at index - 1.
3521 *
3522 * For index == 0, the "before" means the last record of the previous
3523 * extent block. And there is also a situation that we may need to
3524 * remove the rightmost leaf extent block in the right_path and change
3525 * the right path to indicate the new rightmost path.
3526 */
3533 {
3548 /* we meet with a cross extent block merge. */
3553 }
3566 right_path);
3570 left_path);
3574 }
3580 subtree_index);
3584 }
3593 }
3600 }
3601 }
3606 }
3613 }
3616 /*
3617 * The easy case - we can just plop the record right in.
3618 */
3628 split_clusters));
3637 /*
3638 * In the situation that the right_rec is empty and the extent
3639 * block is empty also, ocfs2_complete_edge_insert can't handle
3640 * it and we need to delete the right extent block.
3641 */
3646 right_path,
3647 dealloc);
3651 }
3653 /* Now the rightmost extent block has been deleted.
3654 * So we use the new rightmost path.
3655 */
3661 }
3662 out:
3665 }
3674 {
3682 /*
3683 * The merge code will need to create an empty
3684 * extent to take the place of the newly
3685 * emptied slot. Remove any pre-existing empty
3686 * extents - having more than one in a leaf is
3687 * illegal.
3688 */
3693 }
3694 split_index--;
3696 }
3699 /*
3700 * Left-right contig implies this.
3701 */
3704 /*
3705 * Since the leftright insert always covers the entire
3706 * extent, this call will delete the insert record
3707 * entirely, resulting in an empty extent record added to
3708 * the extent block.
3709 *
3710 * Since the adding of an empty extent shifts
3711 * everything back to the right, there's no need to
3712 * update split_index here.
3713 *
3714 * When the split_index is zero, we need to merge it to the
3715 * prevoius extent block. It is more efficient and easier
3716 * if we do merge_right first and merge_left later.
3717 */
3719 split_index);
3723 }
3725 /*
3726 * We can only get this from logic error above.
3727 */
3730 /* The merge left us with an empty extent, remove it. */
3735 }
3739 /*
3740 * Note that we don't pass split_rec here on purpose -
3741 * we've merged it into the rec already.
3742 */
3749 }
3752 /*
3753 * Error from this last rotate is not critical, so
3754 * print but don't bubble it up.
3755 */
3760 /*
3761 * Merge a record to the left or right.
3762 *
3763 * 'contig_type' is relative to the existing record,
3764 * so for example, if we're "right contig", it's to
3765 * the record on the left (hence the left merge).
3766 */
3770 split_index);
3774 }
3778 split_index);
3782 }
3783 }
3786 /*
3787 * The merge may have left an empty extent in
3788 * our leaf. Try to rotate it away.
3789 */
3791 dealloc);
3795 }
3796 }
3798 out:
3800 }
3806 {
3807 u64 len_blocks;
3813 /*
3814 * Region is on the left edge of the existing
3815 * record.
3816 */
3823 /*
3824 * Region is on the right edge of the existing
3825 * record.
3826 */
3829 }
3830 }
3832 /*
3833 * Do the final bits of extent record insertion at the target leaf
3834 * list. If this leaf is part of an allocation tree, it is assumed
3835 * that the tree above has been prepared.
3836 */
3841 {
3854 insert_rec);
3856 }
3858 /*
3859 * Contiguous insert - either left or right.
3860 */
3866 }
3870 }
3872 /*
3873 * Handle insert into an empty leaf.
3874 */
3881 }
3883 /*
3884 * Appending insert.
3885 */
3895 "owner %llu, depth %u, count %u, next free %u, "
3896 "rec.cpos %u, rec.clusters %u, "
3906 i++;
3910 }
3912 rotate:
3913 /*
3914 * Ok, we have to rotate.
3915 *
3916 * At this point, it is safe to assume that inserting into an
3917 * empty leaf and appending to a leaf have both been handled
3918 * above.
3919 *
3920 * This leaf needs to have space, either by the empty 1st
3921 * extent record, or by virtue of an l_next_rec < l_count.
3922 */
3924 }
3930 {
3936 /*
3937 * Update everything except the leaf block.
3938 */
3950 }
3961 }
3962 }
3969 {
3976 /*
3977 * This shouldn't happen for non-trees. The extent rec cluster
3978 * count manipulation below only works for interior nodes.
3979 */
3982 /*
3983 * If our appending insert is at the leftmost edge of a leaf,
3984 * then we might need to update the rightmost records of the
3985 * neighboring path.
3986 */
3991 u32 left_cpos;
3998 }
4004 left_cpos);
4006 /*
4007 * No need to worry if the append is already in the
4008 * leftmost leaf.
4009 */
4016 }
4019 left_cpos);
4023 }
4025 /*
4026 * ocfs2_insert_path() will pass the left_path to the
4027 * journal for us.
4028 */
4029 }
4030 }
4036 }
4042 out:
4047 }
4054 {
4071 /*
4072 * This typically means that the record
4073 * started in the left path but moved to the
4074 * right as a result of rotation. We either
4075 * move the existing record to the left, or we
4076 * do the later insert there.
4077 *
4078 * In this case, the left path should always
4079 * exist as the rotate code will have passed
4080 * it back for a post-insert update.
4081 */
4084 /*
4085 * It's a left split. Since we know
4086 * that the rotate code gave us an
4087 * empty extent in the left path, we
4088 * can just do the insert there.
4089 */
4092 /*
4093 * Right split - we have to move the
4094 * existing record over to the left
4095 * leaf. The insert will be into the
4096 * newly created empty extent in the
4097 * right leaf.
4098 */
4106 }
4107 }
4111 /*
4112 * Left path is easy - we can just allow the insert to
4113 * happen.
4114 */
4119 }
4125 }
4127 /*
4128 * This function only does inserts on an allocation b-tree. For tree
4129 * depth = 0, ocfs2_insert_at_leaf() is called directly.
4130 *
4131 * right_path is the path we want to do the actual insert
4132 * in. left_path should only be passed in if we need to update that
4133 * portion of the tree after an edge insert.
4134 */
4141 {
4146 /*
4147 * There's a chance that left_path got passed back to
4148 * us without being accounted for in the
4149 * journal. Extend our transaction here to be sure we
4150 * can change those blocks.
4151 */
4156 }
4162 }
4163 }
4165 /*
4166 * Pass both paths to the journal. The majority of inserts
4167 * will be touching all components anyway.
4168 */
4173 }
4176 /*
4177 * We could call ocfs2_insert_at_leaf() for some types
4178 * of splits, but it's easier to just let one separate
4179 * function sort it all out.
4180 */
4184 /*
4185 * Split might have modified either leaf and we don't
4186 * have a guarantee that the later edge insert will
4187 * dirty this for us.
4188 */
4194 insert);
4199 /*
4200 * The rotate code has indicated that we need to fix
4201 * up portions of the tree after the insert.
4202 *
4203 * XXX: Should we extend the transaction here?
4204 */
4206 right_path);
4208 subtree_index);
4209 }
4212 out:
4214 }
4220 {
4222 u32 cpos;
4230 OCFS2_JOURNAL_ACCESS_WRITE);
4234 }
4239 }
4246 }
4248 /*
4249 * Determine the path to start with. Rotations need the
4250 * rightmost path, everything else can go directly to the
4251 * target leaf.
4252 */
4258 }
4264 }
4266 /*
4267 * Rotations and appends need special treatment - they modify
4268 * parts of the tree's above them.
4269 *
4270 * Both might pass back a path immediate to the left of the
4271 * one being inserted to. This will be cause
4272 * ocfs2_insert_path() to modify the rightmost records of
4273 * left_path to account for an edge insert.
4274 *
4275 * XXX: When modifying this code, keep in mind that an insert
4276 * can wind up skipping both of these two special cases...
4277 */
4285 }
4287 /*
4288 * ocfs2_rotate_tree_right() might have extended the
4289 * transaction without re-journaling our tree root.
4290 */
4292 OCFS2_JOURNAL_ACCESS_WRITE);
4296 }
4304 }
4305 }
4312 }
4314 out_update_clusters:
4321 out:
4326 }
4333 {
4357 }
4360 left_cpos);
4371 "Extent block #%llu has an invalid l_next_free_rec of %d. It should have matched the l_count of %d\n",
4377 }
4380 }
4381 }
4383 /*
4384 * We're careful to check for an empty extent record here -
4385 * the merge code will know what to do if it sees one.
4386 */
4393 }
4394 }
4413 }
4431 }
4433 }
4434 }
4445 }
4447 free_right_path:
4449 free_left_path:
4451 exit:
4456 }
4462 {
4470 insert_rec);
4474 }
4475 }
4484 /*
4485 * Caller might want us to limit the size of extents, don't
4486 * calculate contiguousness if we might exceed that limit.
4487 */
4491 }
4492 }
4494 /*
4495 * This should only be called against the righmost leaf extent list.
4496 *
4497 * ocfs2_figure_appending_type() will figure out whether we'll have to
4498 * insert at the tail of the rightmost leaf.
4499 *
4500 * This should also work against the root extent list for tree's with 0
4501 * depth. If we consider the root extent list to be the rightmost leaf node
4502 * then the logic here makes sense.
4503 */
4507 {
4520 /* Were all records empty? */
4523 }
4534 set_tail_append:
4536 }
4538 /*
4539 * Helper function called at the beginning of an insert.
4540 *
4541 * This computes a few things that are commonly used in the process of
4542 * inserting into the btree:
4543 * - Whether the new extent is contiguous with an existing one.
4544 * - The current tree depth.
4545 * - Whether the insert is an appending one.
4546 * - The total # of free records in the tree.
4547 *
4548 * All of the information is stored on the ocfs2_insert_type
4549 * structure.
4550 */
4556 {
4569 /*
4570 * If we have tree depth, we read in the
4571 * rightmost extent block ahead of time as
4572 * ocfs2_figure_insert_type() and ocfs2_add_branch()
4573 * may want it later.
4574 */
4581 }
4584 }
4586 /*
4587 * Unless we have a contiguous insert, we'll need to know if
4588 * there is room left in our allocation tree for another
4589 * extent record.
4590 *
4591 * XXX: This test is simplistic, we can search for empty
4592 * extent records too.
4593 */
4601 }
4608 }
4610 /*
4611 * In the case that we're inserting past what the tree
4612 * currently accounts for, ocfs2_find_path() will return for
4613 * us the rightmost tree path. This is accounted for below in
4614 * the appending code.
4615 */
4620 }
4624 /*
4625 * Now that we have the path, there's two things we want to determine:
4626 * 1) Contiguousness (also set contig_index if this is so)
4627 *
4628 * 2) Are we doing an append? We can trivially break this up
4629 * into two types of appends: simple record append, or a
4630 * rotate inside the tail leaf.
4631 */
4634 /*
4635 * The insert code isn't quite ready to deal with all cases of
4636 * left contiguousness. Specifically, if it's an insert into
4637 * the 1st record in a leaf, it will require the adjustment of
4638 * cluster count on the last record of the path directly to it's
4639 * left. For now, just catch that case and fool the layers
4640 * above us. This works just fine for tree_depth == 0, which
4641 * is why we allow that above.
4642 */
4647 /*
4648 * Ok, so we can simply compare against last_eb to figure out
4649 * whether the path doesn't exist. This will only happen in
4650 * the case that we're doing a tail append, so maybe we can
4651 * take advantage of that information somehow.
4652 */
4655 /*
4656 * Ok, ocfs2_find_path() returned us the rightmost
4657 * tree path. This might be an appending insert. There are
4658 * two cases:
4659 * 1) We're doing a true append at the tail:
4660 * -This might even be off the end of the leaf
4661 * 2) We're "appending" by rotating in the tail
4662 */
4664 }
4666 out:
4671 else
4674 }
4676 /*
4677 * Insert an extent into a btree.
4678 *
4679 * The caller needs to update the owning btree's cluster count.
4680 */
4683 u32 cpos,
4684 u64 start_blk,
4685 u32 new_clusters,
4686 u8 flags,
4688 {
4708 }
4715 }
4724 meta_ac);
4728 }
4729 }
4731 /* Finally, we can add clusters. This might rotate the tree for us. */
4735 else
4738 bail:
4742 }
4744 /*
4745 * Allcate and add clusters into the extent b-tree.
4746 * The new clusters(clusters_to_add) will be inserted at logical_offset.
4747 * The extent b-tree's root is specified by et, and
4748 * it is not limited to the file storage. Any extent tree can use this
4749 * function if it implements the proper ocfs2_extent_tree.
4750 */
4754 u32 clusters_to_add,
4759 {
4765 u64 block;
4780 }
4782 /* there are two cases which could cause us to EAGAIN in the
4783 * we-need-more-metadata case:
4784 * 1) we haven't reserved *any*
4785 * 2) we are so fragmented, we've needed to add metadata too
4786 * many times. */
4799 }
4807 }
4811 /* reserve our write early -- insert_extent may update the tree root */
4813 OCFS2_JOURNAL_ACCESS_WRITE);
4818 }
4830 }
4841 }
4843 bail:
4848 else
4853 num_bits);
4854 }
4856 leave:
4861 }
4865 u32 cpos,
4867 {
4881 }
4890 {
4900 leftright:
4901 /*
4902 * Store a copy of the record on the stack - it might move
4903 * around as the tree is manipulated below.
4904 */
4914 }
4923 }
4924 }
4941 /*
4942 * Left/right split. We fake this as a right split
4943 * first and then make a second pass as a left split.
4944 */
4954 }
4960 }
4963 u32 cpos;
4966 do_leftright++;
4976 }
4984 cpos);
4987 }
4989 }
4990 out:
4993 }
5001 {
5009 }
5014 out:
5016 }
5018 /*
5019 * Split part or all of the extent record at split_index in the leaf
5020 * pointed to by path. Merge with the contiguous extent record if needed.
5021 *
5022 * Care is taken to handle contiguousness so as to not grow the tree.
5023 *
5024 * meta_ac is not strictly necessary - we only truly need it if growth
5025 * of the tree is required. All other cases will degrade into a less
5026 * optimal tree layout.
5027 *
5028 * last_eb_bh should be the rightmost leaf block for any extent
5029 * btree. Since a split may grow the tree or a merge might shrink it,
5030 * the caller cannot trust the contents of that buffer after this call.
5031 *
5032 * This code is optimized for readability - several passes might be
5033 * made over certain portions of the tree. All of those blocks will
5034 * have been brought into cache (and pinned via the journal), so the
5035 * extra overhead is not expressed in terms of disk reads.
5036 */
5044 {
5058 }
5061 split_index,
5062 split_rec,
5067 }
5069 /*
5070 * The core merge / split code wants to know how much room is
5071 * left in this allocation tree, so we pass the
5072 * rightmost extent list.
5073 */
5083 }
5093 else
5106 else
5118 }
5120 out:
5123 }
5125 /*
5126 * Change the flags of the already-existing extent at cpos for len clusters.
5127 *
5128 * new_flags: the flags we want to set.
5129 * clear_flags: the flags we want to clear.
5130 * phys: the new physical offset we want this new extent starts from.
5131 *
5132 * If the existing extent is larger than the request, initiate a
5133 * split. An attempt will be made at merging with adjacent extents.
5134 *
5135 * The caller is responsible for passing down meta_ac if we'll need it.
5136 */
5143 {
5157 }
5163 }
5171 cpos);
5174 }
5182 new_flags);
5184 }
5190 clear_flags);
5192 }
5206 dealloc);
5210 out:
5214 }
5216 /*
5217 * Mark the already-existing extent at cpos as written for len clusters.
5218 * This removes the unwritten extent flag.
5219 *
5220 * If the existing extent is larger than the request, initiate a
5221 * split. An attempt will be made at merging with adjacent extents.
5222 *
5223 * The caller is responsible for passing down meta_ac if we'll need it.
5224 */
5230 {
5238 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",
5242 }
5244 /*
5245 * XXX: This should be fixed up so that we just re-insert the
5246 * next extent records.
5247 */
5256 out:
5258 }
5264 {
5273 /*
5274 * Setup the record to split before we grow the tree.
5275 */
5289 }
5302 }
5307 meta_ac);
5311 }
5312 }
5324 out:
5327 }
5334 {
5349 }
5351 index--;
5352 }
5356 /*
5357 * Check whether this is the rightmost tree record. If
5358 * we remove all of this record or part of its right
5359 * edge then an update of the record lengths above it
5360 * will be required.
5361 */
5365 }
5370 /*
5371 * Changing the leftmost offset (via partial or whole
5372 * record truncate) of an interior (or rightmost) path
5373 * means we have to update the subtree that is formed
5374 * by this leaf and the one to it's left.
5375 *
5376 * There are two cases we can skip:
5377 * 1) Path is the leftmost one in our btree.
5378 * 2) The leaf is rightmost and will be empty after
5379 * we remove the extent record - the rotate code
5380 * knows how to update the newly formed edge.
5381 */
5387 }
5395 }
5398 left_cpos);
5402 }
5403 }
5404 }
5408 path);
5412 }
5418 }
5424 }
5438 /*
5439 * We skip the edge update if this path will
5440 * be deleted by the rotate code.
5441 */
5444 rec);
5445 }
5447 /* Remove leftmost portion of the record. */
5452 /* Remove rightmost portion of the record */
5457 /* Caller should have trapped this. */
5464 }
5471 subtree_index);
5472 }
5480 }
5482 out:
5485 }
5492 {
5499 /*
5500 * XXX: Why are we truncating to 0 instead of wherever this
5501 * affects us?
5502 */
5510 }
5516 }
5524 cpos);
5527 }
5529 /*
5530 * We have 3 cases of extent removal:
5531 * 1) Range covers the entire extent rec
5532 * 2) Range begins or ends on one edge of the extent rec
5533 * 3) Range is in the middle of the extent rec (no shared edges)
5534 *
5535 * For case 1 we remove the extent rec and left rotate to
5536 * fill the hole.
5537 *
5538 * For case 2 we just shrink the existing extent rec, with a
5539 * tree update if the shrinking edge is also the edge of an
5540 * extent block.
5541 *
5542 * For case 3 we do a right split to turn the extent rec into
5543 * something case 2 can handle.
5544 */
5562 }
5569 }
5571 /*
5572 * The split could have manipulated the tree enough to
5573 * move the record location, so we have to look for it again.
5574 */
5581 }
5589 cpos);
5592 }
5594 /*
5595 * Double check our values here. If anything is fishy,
5596 * it's easier to catch it at the top level.
5597 */
5609 }
5616 }
5617 }
5619 out:
5622 }
5624 /*
5625 * ocfs2_reserve_blocks_for_rec_trunc() would look basically the
5626 * same as ocfs2_lock_alloctors(), except for it accepts a blocks
5627 * number to reserve some extra blocks, and it only handles meta
5628 * data allocations.
5629 *
5630 * Currently, only ocfs2_remove_btree_range() uses it for truncating
5631 * and punching holes.
5632 */
5635 u32 extents_to_split,
5638 {
5650 }
5662 }
5663 }
5665 out:
5670 }
5671 }
5674 }
5681 {
5692 OCFS2_HAS_REFCOUNT_FL));
5700 }
5701 }
5704 refcount_loc,
5705 phys_blkno,
5706 len,
5712 }
5713 }
5716 extra_blocks);
5720 }
5729 }
5730 }
5738 }
5741 OCFS2_JOURNAL_ACCESS_WRITE);
5745 }
5754 }
5765 phys_blkno),
5768 else
5774 }
5776 out_commit:
5778 out:
5780 bail:
5788 }
5791 {
5800 "slot %d, invalid truncate log parameters: used = "
5804 }
5808 {
5812 /* No records, nothing to coalesce */
5821 }
5825 u64 start_blk,
5827 {
5841 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5842 * by the underlying call to ocfs2_read_inode_block(), so any
5843 * corruption is a code bug */
5850 "Truncate record count on #%llu invalid "
5856 /* Caller should have known to flush before calling us. */
5862 }
5865 OCFS2_JOURNAL_ACCESS_WRITE);
5869 }
5875 /*
5876 * Move index back to the record we are coalescing with.
5877 * ocfs2_truncate_log_can_coalesce() guarantees nonzero
5878 */
5879 index--;
5885 num_clusters);
5889 }
5895 bail:
5897 }
5903 {
5907 u64 start_blk;
5918 /* Caller has given us at least enough credits to
5919 * update the truncate log dinode */
5921 OCFS2_JOURNAL_ACCESS_WRITE);
5925 }
5931 /* TODO: Perhaps we can calculate the bulk of the
5932 * credits up front rather than extending like
5933 * this. */
5935 OCFS2_TRUNCATE_LOG_FLUSH_ONE_REC);
5939 }
5946 /* if start_blk is not set, we ignore the record as
5947 * invalid. */
5955 num_clusters);
5959 }
5960 }
5961 i--;
5962 }
5966 bail:
5968 }
5970 /* Expects you to already be holding tl_inode->i_mutex */
5972 {
5987 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated
5988 * by the underlying call to ocfs2_read_inode_block(), so any
5989 * corruption is a code bug */
5996 num_to_flush);
6000 }
6003 GLOBAL_BITMAP_SYSTEM_INODE,
6004 OCFS2_INVALID_SLOT);
6009 }
6017 }
6024 }
6027 data_alloc_bh);
6033 out_unlock:
6037 out_mutex:
6041 out:
6043 }
6046 {
6055 }
6058 {
6067 else
6069 }
6071 #define OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL (2 * HZ)
6074 {
6077 /* We want to push off log flushes while truncates are
6078 * still running. */
6083 OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL);
6084 }
6085 }
6091 {
6097 TRUNCATE_LOG_SYSTEM_INODE,
6098 slot_num);
6103 }
6110 }
6114 bail:
6116 }
6118 /* called during the 1st stage of node recovery. we stamp a clean
6119 * truncate log and pass back a copy for processing later. if the
6120 * truncate log does not require processing, a *tl_copy is set to
6121 * NULL. */
6125 {
6140 }
6144 /* tl_bh is loaded from ocfs2_get_truncate_log_info(). It's
6145 * validated by the underlying call to ocfs2_read_inode_block(),
6146 * so any corruption is a code bug */
6158 }
6160 /* Assuming the write-out below goes well, this copy
6161 * will be passed back to recovery for processing. */
6164 /* All we need to do to clear the truncate log is set
6165 * tl_used. */
6173 }
6174 }
6176 bail:
6185 }
6188 }
6192 {
6196 u64 start_blk;
6204 }
6210 num_recs);
6219 }
6220 }
6227 }
6239 }
6240 }
6242 bail_up:
6246 }
6249 {
6265 }
6266 }
6269 {
6281 /* ocfs2_truncate_log_shutdown keys on the existence of
6282 * osb->osb_tl_inode so we don't set any of the osb variables
6283 * until we're sure all is well. */
6285 ocfs2_truncate_log_worker);
6291 }
6293 /*
6294 * Delayed de-allocation of suballocator blocks.
6295 *
6296 * Some sets of block de-allocations might involve multiple suballocator inodes.
6297 *
6298 * The locking for this can get extremely complicated, especially when
6299 * the suballocator inodes to delete from aren't known until deep
6300 * within an unrelated codepath.
6301 *
6302 * ocfs2_extent_block structures are a good example of this - an inode
6303 * btree could have been grown by any number of nodes each allocating
6304 * out of their own suballoc inode.
6305 *
6306 * These structures allow the delay of block de-allocation until a
6307 * later time, when locking of multiple cluster inodes won't cause
6308 * deadlock.
6309 */
6311 /*
6312 * Describe a single bit freed from a suballocator. For the block
6313 * suballocators, it represents one block. For the global cluster
6314 * allocator, it represents some clusters and free_bit indicates
6315 * clusters number.
6316 */
6319 u64 free_bg;
6320 u64 free_blk;
6322 };
6329 };
6335 {
6337 u64 bg_blkno;
6348 }
6356 }
6363 }
6368 else
6379 }
6385 }
6390 }
6392 out_journal:
6395 out_unlock:
6398 out_mutex:
6401 out:
6403 /* Premature exit may have left some dangling items. */
6407 }
6410 }
6414 {
6423 }
6433 }
6437 {
6451 }
6452 }
6459 }
6472 }
6473 }
6478 /* Premature exit may have left some dangling items. */
6482 }
6485 }
6489 {
6510 }
6514 }
6525 }
6528 }
6534 {
6542 }
6552 }
6554 }
6559 {
6569 }
6576 }
6590 out:
6592 }
6596 {
6602 }
6605 {
6609 }
6614 {
6624 /*
6625 * Need to set the buffers we zero'd into uptodate
6626 * here if they aren't - ocfs2_map_page_blocks()
6627 * might've skipped some
6628 */
6631 ocfs2_zero_func);
6638 }
6644 }
6649 {
6675 }
6676 out:
6679 }
6683 {
6687 loff_t last_page_bytes;
6700 }
6702 numpages++;
6703 index++;
6706 out:
6711 }
6716 }
6720 {
6727 }
6729 /*
6730 * Zero the area past i_size but still within an allocated
6731 * cluster. This avoids exposing nonzero data on subsequent file
6732 * extends.
6733 *
6734 * We need to call this before i_size is updated on the inode because
6735 * otherwise block_write_full_page() will skip writeout of pages past
6736 * i_size. The new_i_size parameter is passed for this reason.
6737 */
6740 {
6743 u64 phys;
6747 /*
6748 * File systems which don't support sparse files zero on every
6749 * extend.
6750 */
6760 }
6771 }
6773 /*
6774 * Tail is a hole, or is marked unwritten. In either case, we
6775 * can count on read and write to return/push zero's.
6776 */
6785 }
6790 /*
6791 * Initiate writeout of the pages we zero'd here. We don't
6792 * wait on them - the truncate_inode_pages() call later will
6793 * do that for us.
6794 */
6800 out:
6804 }
6808 {
6815 xattrsize);
6816 else
6819 }
6823 {
6829 }
6832 {
6841 /*
6842 * We clear the entire i_data structure here so that all
6843 * fields can be properly initialized.
6844 */
6849 }
6853 {
6877 }
6883 }
6884 }
6892 }
6895 OCFS2_JOURNAL_ACCESS_WRITE);
6899 }
6903 u64 phys;
6918 }
6920 /*
6921 * Save two copies, one for insert, and one that can
6922 * be changed by ocfs2_map_and_dirty_page() below.
6923 */
6926 /*
6927 * Non sparse file systems zero on extend, so no need
6928 * to do that now.
6929 */
6939 }
6941 /*
6942 * This should populate the 1st page for us and mark
6943 * it up to date.
6944 */
6950 }
6959 }
6972 /*
6973 * An error at this point should be extremely rare. If
6974 * this proves to be false, we could always re-build
6975 * the in-inode data from our pages.
6976 */
6983 }
6986 }
6988 out_unlock:
6992 out_commit:
7001 else
7006 num);
7007 }
7011 out:
7014 free_pages:
7017 }
7019 /*
7020 * It is expected, that by the time you call this function,
7021 * inode->i_size and fe->i_size have been adjusted.
7022 *
7023 * WARNING: This will kfree the truncate context
7024 */
7028 {
7049 ocfs2_journal_access_di);
7054 }
7058 start:
7059 /*
7060 * Check that we still have allocation to delete.
7061 */
7065 }
7067 /*
7068 * Truncate always works against the rightmost tree branch.
7069 */
7074 }
7078 new_highest_cpos,
7082 /*
7083 * By now, el will point to the extent list on the bottom most
7084 * portion of this tree. Only the tail record is considered in
7085 * each pass.
7086 *
7087 * We handle the following cases, in order:
7088 * - empty extent: delete the remaining branch
7089 * - remove the entire record
7090 * - remove a partial record
7091 * - no record needs to be removed (truncate has completed)
7092 */
7101 }
7109 /*
7110 * Lower levels depend on this never happening, but it's best
7111 * to check it up here before changing the tree.
7112 */
7122 }
7130 }
7132 /*
7133 * Truncate entire record.
7134 */
7139 /*
7140 * Partial truncate. it also should be
7141 * the last truncate we're doing.
7142 */
7149 /*
7150 * Truncate completed, leave happily.
7151 */
7154 }
7164 }
7165 }
7173 }
7177 /*
7178 * The check above will catch the case where we've truncated
7179 * away all allocation.
7180 */
7183 bail:
7194 }
7196 /*
7197 * 'start' is inclusive, 'end' is not.
7198 */
7201 {
7225 }
7232 }
7235 OCFS2_JOURNAL_ACCESS_WRITE);
7239 }
7244 /*
7245 * No need to worry about the data page here - it's been
7246 * truncated already and inline data doesn't need it for
7247 * pushing zero's to disk, so we'll let readpage pick it up
7248 * later.
7249 */
7253 }
7264 out_commit:
7267 out:
7269 }
7274 {
7281 /*
7282 * For the first cluster group, the gd->bg_blkno is not at the start
7283 * of the group, but at an offset from the start. If we add it while
7284 * calculating discard for first group, we will wrongly start fstrim a
7285 * few blocks after the desried start block and the range can cross
7286 * over into the next cluster group. So, add it only if this is not
7287 * the first cluster group.
7288 */
7295 }
7300 {
7322 }
7324 }
7330 }
7334 }
7340 }
7343 {
7362 GLOBAL_BITMAP_SYSTEM_INODE,
7363 OCFS2_INVALID_SLOT);
7368 }
7376 }
7382 }
7390 /* Determine first and last group to examine based on start and len */
7394 else
7403 else
7412 }
7423 }
7430 else
7432 }
7434 out_unlock:
7437 out_mutex:
7440 out:
7442 }