| blob | 2553aa8b608d84d1673190ea634c5e84c86d9f0b |
1 /*
2 * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
3 * Written by Alex Tomas <alex@clusterfs.com>
4 *
5 * Architecture independence:
6 * Copyright (c) 2005, Bull S.A.
7 * Written by Pierre Peiffer <pierre.peiffer@bull.net>
8 *
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License version 2 as
11 * published by the Free Software Foundation.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public Licens
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-
21 */
23 /*
24 * Extents support for EXT4
25 *
26 * TODO:
27 * - ext4*_error() should be used in some situations
28 * - analyze all BUG()/BUG_ON(), use -EIO where appropriate
29 * - smart tree reduction
30 */
32 #include <linux/fs.h>
33 #include <linux/time.h>
34 #include <linux/jbd2.h>
35 #include <linux/highuid.h>
36 #include <linux/pagemap.h>
37 #include <linux/quotaops.h>
38 #include <linux/string.h>
39 #include <linux/slab.h>
40 #include <asm/uaccess.h>
41 #include <linux/fiemap.h>
42 #include <linux/backing-dev.h>
47 #include <trace/events/ext4.h>
49 /*
50 * used by extent splitting.
51 */
53 due to ENOSPC */
62 {
65 __u32 csum;
70 }
74 {
84 }
88 {
96 }
108 ext4_lblk_t split,
118 {
133 }
135 /*
136 * could return:
137 * - EROFS
138 * - ENOMEM
139 */
142 {
144 /* path points to block */
147 }
148 /* path points to leaf/index in inode body */
149 /* we use in-core data, no need to protect them */
151 }
153 /*
154 * could return:
155 * - EROFS
156 * - ENOMEM
157 * - EIO
158 */
161 {
167 /* path points to block */
171 /* path points to leaf/index in inode body */
173 }
175 }
179 ext4_lblk_t block)
180 {
185 /*
186 * Try to predict block placement assuming that we are
187 * filling in a file which will eventually be
188 * non-sparse --- i.e., in the case of libbfd writing
189 * an ELF object sections out-of-order but in a way
190 * the eventually results in a contiguous object or
191 * executable file, or some database extending a table
192 * space file. However, this is actually somewhat
193 * non-ideal if we are writing a sparse file such as
194 * qemu or KVM writing a raw image file that is going
195 * to stay fairly sparse, since it will end up
196 * fragmenting the file system's free space. Maybe we
197 * should have some hueristics or some way to allow
198 * userspace to pass a hint to file system,
199 * especially if the latter case turns out to be
200 * common.
201 */
209 else
211 }
213 /* it looks like index is empty;
214 * try to find starting block from index itself */
217 }
219 /* OK. use inode's group */
221 }
223 /*
224 * Allocation for a meta data block
225 */
226 static ext4_fsblk_t
230 {
237 }
240 {
245 #ifdef AGGRESSIVE_TEST
248 #endif
250 }
253 {
258 #ifdef AGGRESSIVE_TEST
261 #endif
263 }
266 {
272 #ifdef AGGRESSIVE_TEST
275 #endif
277 }
280 {
286 #ifdef AGGRESSIVE_TEST
289 #endif
291 }
297 {
305 }
307 /*
308 * Calculate the number of metadata blocks needed
309 * to allocate @blocks
310 * Worse case is one block per extent
311 */
313 {
320 /*
321 * If the new delayed allocation block is contiguous with the
322 * previous da block, it can share index blocks with the
323 * previous block, so we only need to allocate a new index
324 * block every idxs leaf blocks. At ldxs**2 blocks, we need
325 * an additional index block, and at ldxs**3 blocks, yet
326 * another index blocks.
327 */
333 num++;
335 num++;
337 num++;
343 }
345 /*
346 * In the worst case we need a new set of index blocks at
347 * every level of the inode's extent tree.
348 */
352 }
354 static int
356 {
362 else
367 else
369 }
372 }
375 {
384 }
388 {
392 }
397 {
405 /* leaf entries */
416 /* Check for overlapping extents */
423 }
424 ext++;
425 entries--;
427 }
433 ext_idx++;
434 entries--;
435 }
436 }
438 }
443 {
450 }
454 }
458 }
463 }
467 }
471 }
472 /* Verify checksum on non-root extent tree nodes */
477 }
480 corrupted:
482 "pblk %llu bad header/extent: %s - magic %x, "
489 }
491 #define ext4_ext_check(inode, eh, depth, pblk) \
492 __ext4_ext_check(__func__, __LINE__, (inode), (eh), (depth), (pblk))
495 {
497 }
503 {
516 }
524 /*
525 * If this is a leaf block, cache all of its entries
526 */
541 EXTENT_STATUS_HOLE);
548 }
549 }
551 errout:
555 }
557 #define read_extent_tree_block(inode, pblk, depth, flags) \
558 __read_extent_tree_block(__func__, __LINE__, (inode), (pblk), \
559 (depth), (flags))
561 /*
562 * This function is called to cache a file's extent information in the
563 * extent status tree
564 */
566 {
579 GFP_NOFS);
583 }
585 /* Don't cache anything if there are no external extent blocks */
594 /*
595 * If this is a leaf block or we've reached the end of
596 * the index block, go up
597 */
602 i--;
604 }
608 EXT4_EX_FORCE_CACHE);
612 }
613 i++;
617 }
619 out:
624 }
626 #ifdef EXT_DEBUG
628 {
644 }
646 }
649 {
667 }
669 }
673 {
684 newblock);
685 idx++;
686 }
689 }
698 newblock);
699 ex++;
700 }
701 }
703 #else
704 #define ext4_ext_show_path(inode, path)
705 #define ext4_ext_show_leaf(inode, path)
706 #define ext4_ext_show_move(inode, path, newblock, level)
707 #endif
710 {
720 }
721 }
723 /*
724 * ext4_ext_binsearch_idx:
725 * binary search for the closest index of the given block
726 * the header must be checked before calling this
727 */
728 static void
731 {
744 else
749 }
755 #ifdef CHECK_BINSEARCH
756 {
770 }
776 }
778 }
779 #endif
781 }
783 /*
784 * ext4_ext_binsearch:
785 * binary search for closest extent of the given block
786 * the header must be checked before calling this
787 */
788 static void
791 {
796 /*
797 * this leaf is empty:
798 * we get such a leaf in split/add case
799 */
801 }
812 else
817 }
826 #ifdef CHECK_BINSEARCH
827 {
838 }
840 }
841 #endif
843 }
846 {
856 }
861 {
876 }
877 }
879 /* account possible depth increase */
881 GFP_NOFS);
885 }
890 /* walk through the tree */
901 flags);
905 }
908 ppos++;
915 }
918 }
924 /* find extent */
926 /* if not an empty leaf */
934 err:
940 }
942 /*
943 * ext4_ext_insert_index:
944 * insert new index [@logical;@ptr] into the block at @curp;
945 * check where to insert: before @curp or after @curp
946 */
950 {
963 }
972 }
975 /* insert after */
979 /* insert before */
982 }
991 }
996 }
1005 }
1011 }
1013 /*
1014 * ext4_ext_split:
1015 * inserts new subtree into the path, using free index entry
1016 * at depth @at:
1017 * - allocates all needed blocks (new leaf and all intermediate index blocks)
1018 * - makes decision where to split
1019 * - moves remaining extents and index entries (right to the split point)
1020 * into the newly allocated blocks
1021 * - initializes subtree
1022 */
1027 {
1034 __le32 border;
1038 /* make decision: where to split? */
1039 /* FIXME: now decision is simplest: at current extent */
1041 /* if current leaf will be split, then we should use
1042 * border from split point */
1046 }
1057 }
1059 /*
1060 * If error occurs, then we break processing
1061 * and mark filesystem read-only. index won't
1062 * be inserted and tree will be in consistent
1063 * state. Next mount will repair buffers too.
1064 */
1066 /*
1067 * Get array to track all allocated blocks.
1068 * We need this to handle errors and free blocks
1069 * upon them.
1070 */
1075 /* allocate all needed blocks */
1083 }
1085 /* initialize new leaf */
1091 }
1096 }
1109 /* move remainder of path[depth] to the new leaf */
1117 }
1118 /* start copy from next extent */
1126 }
1138 /* correct old leaf */
1148 }
1150 /* create intermediate indexes */
1156 }
1159 /* insert new index into current index block */
1160 /* current depth stored in i var */
1169 }
1188 /* move remainder of path[i] to the new index block */
1196 }
1197 /* start copy indexes */
1206 }
1217 /* correct old index */
1226 }
1228 i--;
1229 }
1231 /* insert new index */
1235 cleanup:
1240 }
1243 /* free all allocated blocks in error case */
1248 EXT4_FREE_BLOCKS_METADATA);
1249 }
1250 }
1254 }
1256 /*
1257 * ext4_ext_grow_indepth:
1258 * implements tree growing procedure:
1259 * - allocates new block
1260 * - moves top-level data (index block or leaf) into the new block
1261 * - initializes new top-level, creating index that points to the
1262 * just created block
1263 */
1266 {
1273 /* Try to prepend new index to old one */
1278 goal--;
1295 }
1297 /* move top-level index/leaf into new block */
1301 /* set size of new block */
1303 /* old root could have indexes or leaves
1304 * so calculate e_max right way */
1307 else
1318 /* Update top-level index: num,max,pointer */
1323 /* Root extent block becomes index block */
1327 }
1335 out:
1339 }
1341 /*
1342 * ext4_ext_create_new_leaf:
1343 * finds empty index and adds new leaf.
1344 * if no free index is found, then it requests in-depth growing.
1345 */
1351 {
1356 repeat:
1359 /* walk up to the tree and look for free index entry */
1362 i--;
1363 curp--;
1364 }
1366 /* we use already allocated block for index block,
1367 * so subsequent data blocks should be contiguous */
1369 /* if we found index with free entry, then use that
1370 * entry: create all needed subtree and add new leaf */
1375 /* refill path */
1382 /* tree is full, time to grow in depth */
1387 /* refill path */
1394 }
1396 /*
1397 * only first (depth 0 -> 1) produces free space;
1398 * in all other cases we have to split the grown tree
1399 */
1402 /* now we need to split */
1404 }
1405 }
1407 out:
1409 }
1411 /*
1412 * search the closest allocated block to the left for *logical
1413 * and returns it at @logical + it's physical address at @phys
1414 * if *logical is the smallest allocated block, the function
1415 * returns 0 at @phys
1416 * return value contains 0 (success) or error code
1417 */
1421 {
1429 }
1436 /* usually extent in the path covers blocks smaller
1437 * then *logical, but it can be that extent is the
1438 * first one in the file */
1448 }
1457 depth);
1459 }
1460 }
1462 }
1469 }
1474 }
1476 /*
1477 * search the closest allocated block to the right for *logical
1478 * and returns it at @logical + it's physical address at @phys
1479 * if *logical is the largest allocated block, the function
1480 * returns 0 at @phys
1481 * return value contains 0 (success) or error code
1482 */
1487 {
1492 ext4_fsblk_t block;
1499 }
1506 /* usually extent in the path covers blocks smaller
1507 * then *logical, but it can be that extent is the
1508 * first one in the file */
1516 depth);
1518 }
1526 }
1527 }
1529 }
1536 }
1539 /* next allocated block in this leaf */
1540 ex++;
1542 }
1544 /* go up and search for index to the right */
1549 }
1551 /* we've gone up to the root and found no index to the right */
1554 got_index:
1555 /* we've found index to the right, let's
1556 * follow it and find the closest allocated
1557 * block to the right */
1558 ix++;
1561 /* subtract from p_depth to get proper eh_depth */
1570 }
1577 found_extent:
1584 }
1586 /*
1587 * ext4_ext_next_allocated_block:
1588 * returns allocated block in subsequent extent or EXT_MAX_BLOCKS.
1589 * NOTE: it considers block number from index entry as
1590 * allocated block. Thus, index entries have to be consistent
1591 * with leaves.
1592 */
1593 ext4_lblk_t
1595 {
1606 /* leaf */
1612 /* index */
1616 }
1617 depth--;
1618 }
1621 }
1623 /*
1624 * ext4_ext_next_leaf_block:
1625 * returns first allocated block from next leaf or EXT_MAX_BLOCKS
1626 */
1628 {
1634 /* zero-tree has no leaf blocks at all */
1638 /* go to index block */
1639 depth--;
1646 depth--;
1647 }
1650 }
1652 /*
1653 * ext4_ext_correct_indexes:
1654 * if leaf gets modified and modified extent is first in the leaf,
1655 * then we have to correct all indexes above.
1656 * TODO: do we need to correct tree in all cases?
1657 */
1660 {
1664 __le32 border;
1674 }
1677 /* there is no tree at all */
1679 }
1682 /* we correct tree if first leaf got modified only */
1684 }
1686 /*
1687 * TODO: we need correction if border is smaller than current one
1688 */
1700 /* change all left-side indexes */
1710 }
1713 }
1715 int
1718 {
1731 /*
1732 * To allow future support for preallocated extents to be added
1733 * as an RO_COMPAT feature, refuse to merge to extents if
1734 * this can result in the top bit of ee_len being set.
1735 */
1743 #ifdef AGGRESSIVE_TEST
1746 #endif
1751 }
1753 /*
1754 * This function tries to merge the "ex" extent to the next extent in the tree.
1755 * It always tries to merge towards right. If you want to merge towards
1756 * left, pass "ex - 1" as argument instead of "ex".
1757 * Returns 0 if the extents (ex and ex+1) were _not_ merged and returns
1758 * 1 if they got merged.
1759 */
1763 {
1775 /* merge with next extent! */
1786 }
1792 }
1795 }
1797 /*
1798 * This function does a very simple check to see if we can collapse
1799 * an extent tree with a single extent tree leaf block into the inode.
1800 */
1804 {
1807 ext4_fsblk_t blk;
1814 /*
1815 * We need to modify the block allocation bitmap and the block
1816 * group descriptor to release the extent tree block. If we
1817 * can't get the journal credits, give up.
1818 */
1822 /*
1823 * Copy the extent data up to the inode
1824 */
1840 }
1842 /*
1843 * This function tries to merge the @ex extent to neighbours in the tree.
1844 * return 1 if merge left else 0.
1845 */
1865 }
1867 /*
1868 * check if a portion of the "newext" extent overlaps with an
1869 * existing extent.
1870 *
1871 * If there is an overlap discovered, it updates the length of the newext
1872 * such that there will be no overlap, and then returns 1.
1873 * If there is no overlap found, it returns 0.
1874 */
1879 {
1891 /*
1892 * get the next allocated block if the extent in the path
1893 * is before the requested block(s)
1894 */
1900 }
1902 /* check for wrap through zero on extent logical start block*/
1907 }
1909 /* check for overlap */
1913 }
1914 out:
1916 }
1918 /*
1919 * ext4_ext_insert_extent:
1920 * tries to merge requsted extent into the existing extent or
1921 * inserts requested extent as new one into the tree,
1922 * creating new leaf in the no-space case.
1923 */
1927 {
1934 ext4_lblk_t next;
1942 }
1949 }
1951 /* try to insert block into found extent and return */
1954 /*
1955 * Try to see whether we should rather test the extent on
1956 * right from ex, or from the left of ex. This is because
1957 * ext4_find_extent() can return either extent on the
1958 * left, or on the right from the searched position. This
1959 * will make merging more effective.
1960 */
1973 /* Try to append newex to the ex */
1995 }
1997 prepend:
1998 /* Try to prepend newex to the ex */
2024 }
2025 }
2032 /* probably next leaf has space for us? */
2050 }
2053 }
2055 /*
2056 * There is no free space in the found leaf.
2057 * We're gonna add a new leaf in the tree.
2058 */
2068 has_space:
2076 /* there is no extent in this leaf, create first one */
2086 /* Insert after */
2093 nearex);
2094 nearex++;
2096 /* Insert before */
2104 nearex);
2105 }
2117 }
2118 }
2126 merge:
2127 /* try to merge extents */
2132 /* time to correct all indexes above */
2139 cleanup:
2143 }
2148 {
2160 /* find extent for this block */
2169 }
2177 }
2184 /* there is no extent yet, so try to allocate
2185 * all requested space */
2189 /* need to allocate space before found extent */
2196 /* need to allocate space after found extent */
2202 /*
2203 * some part of requested space is covered
2204 * by found extent
2205 */
2214 }
2227 }
2229 /*
2230 * Find delayed extent and update es accordingly. We call
2231 * it even in !exists case to find out whether es is the
2232 * last existing extent or not.
2233 */
2238 FIEMAP_EXTENT_UNKNOWN);
2239 }
2246 }
2248 /*
2249 * This is possible iff next == next_del == EXT_MAX_BLOCKS.
2250 * we need to check next == EXT_MAX_BLOCKS because it is
2251 * possible that an extent is with unwritten and delayed
2252 * status due to when an extent is delayed allocated and
2253 * is allocated by fallocate status tree will track both of
2254 * them in a extent.
2255 *
2256 * So we could return a unwritten and delayed extent, and
2257 * its block is equal to 'next'.
2258 */
2264 "next extent == %u, next "
2269 }
2270 }
2277 flags);
2283 }
2284 }
2287 }
2292 }
2294 /*
2295 * ext4_ext_put_gap_in_cache:
2296 * calculate boundaries of the gap that the requested block fits into
2297 * and cache this gap
2298 */
2299 static void
2301 ext4_lblk_t block)
2302 {
2304 ext4_lblk_t len;
2305 ext4_lblk_t lblock;
2311 /* there is no extent yet, so gap is [0;-] */
2319 block,
2324 ext4_lblk_t next;
2332 block);
2337 }
2341 /* There's delayed extent containing lblock? */
2345 }
2348 }
2350 /*
2351 * ext4_ext_rm_idx:
2352 * removes index from the index block.
2353 */
2356 {
2358 ext4_fsblk_t leaf;
2360 /* free index block */
2361 depth--;
2367 }
2376 }
2391 path--;
2399 }
2401 }
2403 /*
2404 * ext4_ext_calc_credits_for_single_extent:
2405 * This routine returns max. credits that needed to insert an extent
2406 * to the extent tree.
2407 * When pass the actual path, the caller should calculate credits
2408 * under i_data_sem.
2409 */
2412 {
2417 /* probably there is space in leaf? */
2421 /*
2422 * There are some space in the leaf tree, no
2423 * need to account for leaf block credit
2424 *
2425 * bitmaps and block group descriptor blocks
2426 * and other metadata blocks still need to be
2427 * accounted.
2428 */
2429 /* 1 bitmap, 1 block group descriptor */
2432 }
2433 }
2436 }
2438 /*
2439 * How many index/leaf blocks need to change/allocate to add @extents extents?
2440 *
2441 * If we add a single extent, then in the worse case, each tree level
2442 * index/leaf need to be changed in case of the tree split.
2443 *
2444 * If more extents are inserted, they could cause the whole tree split more
2445 * than once, but this is really rare.
2446 */
2448 {
2452 /* If we are converting the inline data, only one is needed here. */
2460 else
2464 }
2467 {
2473 }
2479 {
2482 ext4_fsblk_t pblk;
2485 /*
2486 * For bigalloc file systems, we never free a partial cluster
2487 * at the beginning of the extent. Instead, we make a note
2488 * that we tried freeing the cluster, and check to see if we
2489 * need to free it on a subsequent call to ext4_remove_blocks,
2490 * or at the end of ext4_ext_rm_leaf or ext4_ext_remove_space.
2491 */
2495 /*
2496 * If we have a partial cluster, and it's different from the
2497 * cluster of the last block, we need to explicitly free the
2498 * partial cluster here.
2499 */
2507 }
2509 #ifdef EXTENTS_STATS
2510 {
2522 }
2523 #endif
2526 /* tail removal */
2527 ext4_lblk_t num;
2532 /*
2533 * Usually we want to free partial cluster at the end of the
2534 * extent, except for the situation when the cluster is still
2535 * used by any other extent (partial_cluster is negative).
2536 */
2544 /*
2545 * If the block range to be freed didn't start at the
2546 * beginning of a cluster, and we removed the entire
2547 * extent and the cluster is not used by any other extent,
2548 * save the partial cluster here, since we might need to
2549 * delete if we determine that the truncate or punch hole
2550 * operation has removed all of the blocks in the cluster.
2551 * If that cluster is used by another extent, preserve its
2552 * negative value so it isn't freed later on.
2553 *
2554 * If the whole extent wasn't freed, we've reached the
2555 * start of the truncated/punched region and have finished
2556 * removing blocks. If there's a partial cluster here it's
2557 * shared with the remainder of the extent and is no longer
2558 * a candidate for removal.
2559 */
2566 }
2572 }
2575 /*
2576 * ext4_ext_rm_leaf() Removes the extents associated with the
2577 * blocks appearing between "start" and "end". Both "start"
2578 * and "end" must appear in the same extent or EIO is returned.
2579 *
2580 * @handle: The journal handle
2581 * @inode: The files inode
2582 * @path: The path to the leaf
2583 * @partial_cluster: The cluster which we'll have to free if all extents
2584 * has been released from it. However, if this value is
2585 * negative, it's a cluster just to the right of the
2586 * punched region and it must not be freed.
2587 * @start: The first block to remove
2588 * @end: The last block to remove
2589 */
2590 static int
2595 {
2602 ext4_lblk_t ex_ee_block;
2606 ext4_fsblk_t pblk;
2608 /* the header must be checked already in ext4_ext_remove_space() */
2616 }
2617 /* find where to start removing */
2632 else
2645 /* If this extent is beyond the end of the hole, skip it */
2647 /*
2648 * We're going to skip this extent and move to another,
2649 * so note that its first cluster is in use to avoid
2650 * freeing it when removing blocks. Eventually, the
2651 * right edge of the truncated/punched region will
2652 * be just to the left.
2653 */
2658 }
2659 ex--;
2665 "can not handle truncate %u:%u "
2672 /* remove tail of the extent */
2675 /* remove whole extent: excellent! */
2677 }
2678 /*
2679 * 3 for leaf, sb, and inode plus 2 (bmap and group
2680 * descriptor) for each block group; assume two block
2681 * groups plus ex_ee_len/blocks_per_block_group for
2682 * the worst case
2683 */
2688 }
2705 /* this extent is removed; mark slot entirely unused */
2709 /*
2710 * Do not mark unwritten if all the blocks in the
2711 * extent have been removed.
2712 */
2715 /*
2716 * If the extent was completely released,
2717 * we need to remove it from the leaf
2718 */
2721 /*
2722 * For hole punching, we need to scoot all the
2723 * extents up when an extent is removed so that
2724 * we dont have blank extents in the middle
2725 */
2729 /* Now get rid of the one at the end */
2732 }
2734 }
2742 ex--;
2745 }
2750 /*
2751 * If there's a partial cluster and at least one extent remains in
2752 * the leaf, free the partial cluster if it isn't shared with the
2753 * current extent. If it is shared with the current extent
2754 * we zero partial_cluster because we've reached the start of the
2755 * truncated/punched region and we're done removing blocks.
2756 */
2764 }
2766 }
2768 /* if this leaf is free, then we should
2769 * remove it from index block above */
2773 out:
2775 }
2777 /*
2778 * ext4_ext_more_to_rm:
2779 * returns 1 if current index has to be freed (even partial)
2780 */
2781 static int
2783 {
2789 /*
2790 * if truncate on deeper level happened, it wasn't partial,
2791 * so we have to consider current index for truncation
2792 */
2796 }
2799 ext4_lblk_t end)
2800 {
2810 /* probably first extent we're gonna free will be last in block */
2815 again:
2818 /*
2819 * Check if we are removing extents inside the extent tree. If that
2820 * is the case, we are going to punch a hole inside the extent tree
2821 * so we have to check whether we need to split the extent covering
2822 * the last block to remove so we can easily remove the part of it
2823 * in ext4_ext_rm_leaf().
2824 */
2828 ext4_fsblk_t pblk;
2830 /* find extent for or closest extent to this block */
2835 }
2837 /* Leaf not may not exist only if inode has no blocks at all */
2843 depth);
2845 }
2847 }
2852 /*
2853 * See if the last block is inside the extent, if so split
2854 * the extent at 'end' block so we can easily remove the
2855 * tail of the first part of the split extent in
2856 * ext4_ext_rm_leaf().
2857 */
2860 /*
2861 * If we're going to split the extent, note that
2862 * the cluster containing the block after 'end' is
2863 * in use to avoid freeing it when removing blocks.
2864 */
2867 partial_cluster =
2869 }
2871 /*
2872 * Split the extent in two so that 'end' is the last
2873 * block in the first new extent. Also we should not
2874 * fail removing space due to ENOSPC so try to use
2875 * reserved block if that happens.
2876 */
2883 /*
2884 * If there's an extent to the right its first cluster
2885 * contains the immediate right boundary of the
2886 * truncated/punched region. Set partial_cluster to
2887 * its negative value so it won't be freed if shared
2888 * with the current extent. The end < ee_block case
2889 * is handled in ext4_ext_rm_leaf().
2890 */
2897 partial_cluster =
2899 }
2900 }
2901 /*
2902 * We start scanning from right side, freeing all the blocks
2903 * after i_size and walking into the tree depth-wise.
2904 */
2913 GFP_NOFS);
2917 }
2925 }
2926 }
2931 /* this is leaf block */
2934 end);
2935 /* root level has p_bh == NULL, brelse() eats this */
2938 i--;
2940 }
2942 /* this is index block */
2946 }
2949 /* this level hasn't been touched yet */
2956 /* we were already here, see at next index */
2958 }
2965 /* go to the next level */
2971 EXT4_EX_NOCACHE);
2973 /* should we reset i_size? */
2976 }
2977 /* Yield here to deal with large extent trees.
2978 * Should be a no-op if we did IO above. */
2983 }
2986 /* save actual number of indexes since this
2987 * number is changed at the next iteration */
2989 i++;
2991 /* we finished processing this index, go up */
2993 /* index is empty, remove it;
2994 * handle must be already prepared by the
2995 * truncatei_leaf() */
2997 }
2998 /* root level has p_bh == NULL, brelse() eats this */
3001 i--;
3003 }
3004 }
3009 /*
3010 * If we still have something in the partial cluster and we have removed
3011 * even the first extent, then we should free the blocks in the partial
3012 * cluster as well. (This code will only run when there are no leaves
3013 * to the immediate left of the truncated/punched region.)
3014 */
3016 /* don't zero partial_cluster since it's not used afterwards */
3021 }
3023 /* TODO: flexible tree reduction should be here */
3025 /*
3026 * truncate to zero freed all the tree,
3027 * so we need to correct eh_depth
3028 */
3035 }
3036 }
3037 out:
3046 }
3048 /*
3049 * called at mount time
3050 */
3052 {
3053 /*
3054 * possible initialization would be here
3055 */
3058 #if defined(AGGRESSIVE_TEST) || defined(CHECK_BINSEARCH) || defined(EXTENTS_STATS)
3060 #ifdef AGGRESSIVE_TEST
3061 ", aggressive tests"
3062 #endif
3063 #ifdef CHECK_BINSEARCH
3064 ", check binsearch"
3065 #endif
3066 #ifdef EXTENTS_STATS
3067 ", stats"
3068 #endif
3070 #endif
3071 #ifdef EXTENTS_STATS
3075 #endif
3076 }
3077 }
3079 /*
3080 * called at umount time
3081 */
3083 {
3087 #ifdef EXTENTS_STATS
3095 }
3096 #endif
3097 }
3100 {
3101 ext4_lblk_t ee_block;
3102 ext4_fsblk_t ee_pblock;
3113 EXTENT_STATUS_WRITTEN);
3114 }
3116 /* FIXME!! we need to try to merge to left or right after zero-out */
3118 {
3119 ext4_fsblk_t ee_pblock;
3134 }
3136 /*
3137 * ext4_split_extent_at() splits an extent at given block.
3138 *
3139 * @handle: the journal handle
3140 * @inode: the file inode
3141 * @path: the path to the extent
3142 * @split: the logical block where the extent is splitted.
3143 * @split_flags: indicates if the extent could be zeroout if split fails, and
3144 * the states(init or unwritten) of new extents.
3145 * @flags: flags used to insert new extent to extent tree.
3146 *
3147 *
3148 * Splits extent [a, b] into two extents [a, @split) and [@split, b], states
3149 * of which are deterimined by split_flag.
3150 *
3151 * There are two cases:
3152 * a> the extent are splitted into two extent.
3153 * b> split is not needed, and just mark the extent.
3154 *
3155 * return 0 on success.
3156 */
3160 ext4_lblk_t split,
3163 {
3165 ext4_fsblk_t newblock;
3166 ext4_lblk_t ee_block;
3189 EXT4_EXT_MARK_UNWRIT1 |
3190 EXT4_EXT_MARK_UNWRIT2));
3197 /*
3198 * case b: block @split is the block that the extent begins with
3199 * then we just change the state of the extent, and splitting
3200 * is not needed.
3201 */
3204 else
3212 }
3214 /* case a */
3220 /*
3221 * path may lead to new leaf, not to original leaf any more
3222 * after ext4_ext_insert_extent() returns,
3223 */
3252 }
3260 }
3264 /* update the extent length and mark as initialized */
3271 /* update extent status tree */
3278 out:
3282 fix_extent_len:
3286 }
3288 /*
3289 * ext4_split_extents() splits an extent and mark extent which is covered
3290 * by @map as split_flags indicates
3291 *
3292 * It may result in splitting the extent into multiple extents (up to three)
3293 * There are three possibilities:
3294 * a> There is no split required
3295 * b> Splits in two extents: Split is happening at either end of the extent
3296 * c> Splits in three extents: Somone is splitting in middle of the extent
3297 *
3298 */
3305 {
3307 ext4_lblk_t ee_block;
3326 EXT4_EXT_MARK_UNWRIT2;
3335 }
3336 /*
3337 * Update path is required because previous ext4_split_extent_at() may
3338 * result in split of original leaf or extent zeroout.
3339 */
3349 }
3358 EXT4_EXT_MARK_UNWRIT2);
3359 }
3364 }
3367 out:
3369 }
3371 /*
3372 * This function is called by ext4_ext_map_blocks() if someone tries to write
3373 * to an unwritten extent. It may result in splitting the unwritten
3374 * extent into multiple extents (up to three - one initialized and two
3375 * unwritten).
3376 * There are three possibilities:
3377 * a> There is no split required: Entire extent should be initialized
3378 * b> Splits in two extents: Write is happening at either end of the extent
3379 * c> Splits in three extents: Somone is writing in middle of the extent
3380 *
3381 * Pre-conditions:
3382 * - The extent pointed to by 'path' is unwritten.
3383 * - The extent pointed to by 'path' contains a superset
3384 * of the logical span [map->m_lblk, map->m_lblk + map->m_len).
3385 *
3386 * Post-conditions on success:
3387 * - the returned value is the number of blocks beyond map->l_lblk
3388 * that are allocated and initialized.
3389 * It is guaranteed to be >= map->m_len.
3390 */
3396 {
3428 /* Pre-conditions */
3432 /*
3433 * Attempt to transfer newly initialized blocks from the currently
3434 * unwritten extent to its neighbor. This is much cheaper
3435 * than an insertion followed by a merge as those involve costly
3436 * memmove() calls. Transferring to the left is the common case in
3437 * steady state for workloads doing fallocate(FALLOC_FL_KEEP_SIZE)
3438 * followed by append writes.
3439 *
3440 * Limitations of the current logic:
3441 * - L1: we do not deal with writes covering the whole extent.
3442 * This would require removing the extent if the transfer
3443 * is possible.
3444 * - L2: we only attempt to merge with an extent stored in the
3445 * same extent tree node.
3446 */
3448 /* See if we can merge left */
3451 ext4_lblk_t prev_lblk;
3461 /*
3462 * A transfer of blocks from 'ex' to 'abut_ex' is allowed
3463 * upon those conditions:
3464 * - C1: abut_ex is initialized,
3465 * - C2: abut_ex is logically abutting ex,
3466 * - C3: abut_ex is physically abutting ex,
3467 * - C4: abut_ex can receive the additional blocks without
3468 * overflowing the (initialized) length limit.
3469 */
3481 /* Shift the start of ex by 'map_len' blocks */
3487 /* Extend abut_ex by 'map_len' blocks */
3490 /* Result: number of initialized blocks past m_lblk */
3492 }
3496 /* See if we can merge right */
3497 ext4_lblk_t next_lblk;
3507 /*
3508 * A transfer of blocks from 'ex' to 'abut_ex' is allowed
3509 * upon those conditions:
3510 * - C1: abut_ex is initialized,
3511 * - C2: abut_ex is logically abutting ex,
3512 * - C3: abut_ex is physically abutting ex,
3513 * - C4: abut_ex can receive the additional blocks without
3514 * overflowing the (initialized) length limit.
3515 */
3527 /* Shift the start of abut_ex by 'map_len' blocks */
3533 /* Extend abut_ex by 'map_len' blocks */
3536 /* Result: number of initialized blocks past m_lblk */
3538 }
3539 }
3541 /* Mark the block containing both extents as dirty */
3544 /* Update path to point to the right extent */
3551 /*
3552 * It is safe to convert extent to initialized via explicit
3553 * zeroout only if extent is fully inside i_size or new_size.
3554 */
3561 /* If extent is less than s_max_zeroout_kb, zeroout directly */
3577 }
3579 /*
3580 * four cases:
3581 * 1. split the extent into three extents.
3582 * 2. split the extent into two extents, zeroout the first half.
3583 * 3. split the extent into two extents, zeroout the second half.
3584 * 4. split the extent into two extents with out zeroout.
3585 */
3591 /* case 3 */
3603 /* case 2 */
3607 ee_block);
3613 }
3618 }
3619 }
3622 flags);
3625 out:
3626 /* If we have gotten a failure, don't zero out status tree */
3630 }
3632 /*
3633 * This function is called by ext4_ext_map_blocks() from
3634 * ext4_get_blocks_dio_write() when DIO to write
3635 * to an unwritten extent.
3636 *
3637 * Writing to an unwritten extent may result in splitting the unwritten
3638 * extent into multiple initialized/unwritten extents (up to three)
3639 * There are three possibilities:
3640 * a> There is no split required: Entire extent should be unwritten
3641 * b> Splits in two extents: Write is happening at either end of the extent
3642 * c> Splits in three extents: Somone is writing in middle of the extent
3643 *
3644 * This works the same way in the case of initialized -> unwritten conversion.
3645 *
3646 * One of more index blocks maybe needed if the extent tree grow after
3647 * the unwritten extent split. To prevent ENOSPC occur at the IO
3648 * complete, we need to split the unwritten extent before DIO submit
3649 * the IO. The unwritten extent called at this time will be split
3650 * into three unwritten extent(at most). After IO complete, the part
3651 * being filled will be convert to initialized by the end_io callback function
3652 * via ext4_convert_unwritten_extents().
3653 *
3654 * Returns the size of unwritten extent to be written on success.
3655 */
3661 {
3663 ext4_lblk_t eof_block;
3664 ext4_lblk_t ee_block;
3677 /*
3678 * It is safe to convert extent to initialized via explicit
3679 * zeroout only if extent is fully insde i_size or new_size.
3680 */
3686 /* Convert to unwritten */
3689 /* Convert to initialized */
3694 }
3697 }
3703 {
3706 ext4_lblk_t ee_block;
3720 /* If extent is larger than requested it is a clear sign that we still
3721 * have some extent state machine issues left. So extent_split is still
3722 * required.
3723 * TODO: Once all related issues will be fixed this situation should be
3724 * illegal.
3725 */
3727 #ifdef EXT4_DEBUG
3732 #endif
3734 EXT4_GET_BLOCKS_CONVERT);
3742 }
3747 /* first mark the extent as initialized */
3750 /* note: ext4_ext_correct_indexes() isn't needed here because
3751 * borders are not changed
3752 */
3755 /* Mark modified extent as dirty */
3757 out:
3760 }
3764 {
3768 }
3770 /*
3771 * Handle EOFBLOCKS_FL flag, clearing it if necessary
3772 */
3774 ext4_lblk_t lblk,
3777 {
3788 /*
3789 * We're going to remove EOFBLOCKS_FL entirely in future so we
3790 * do not care for this case anymore. Simply remove the flag
3791 * if there are no extents.
3792 */
3796 /*
3797 * We should clear the EOFBLOCKS_FL flag if we are writing the
3798 * last block in the last extent in the file. We test this by
3799 * first checking to see if the caller to
3800 * ext4_ext_get_blocks() was interested in the last block (or
3801 * a block beyond the last block) in the current extent. If
3802 * this turns out to be false, we can bail out from this
3803 * function immediately.
3804 */
3808 /*
3809 * If the caller does appear to be planning to write at or
3810 * beyond the end of the current extent, we then test to see
3811 * if the current extent is the last extent in the file, by
3812 * checking to make sure it was reached via the rightmost node
3813 * at each level of the tree.
3814 */
3818 out:
3821 }
3823 /**
3824 * ext4_find_delalloc_range: find delayed allocated block in the given range.
3825 *
3826 * Return 1 if there is a delalloc block in the range, otherwise 0.
3827 */
3829 ext4_lblk_t lblk_start,
3830 ext4_lblk_t lblk_end)
3831 {
3842 else
3844 }
3847 {
3854 }
3856 /**
3857 * Determines how many complete clusters (out of those specified by the 'map')
3858 * are under delalloc and were reserved quota for.
3859 * This function is called when we are writing out the blocks that were
3860 * originally written with their allocation delayed, but then the space was
3861 * allocated using fallocate() before the delayed allocation could be resolved.
3862 * The cases to look for are:
3863 * ('=' indicated delayed allocated blocks
3864 * '-' indicates non-delayed allocated blocks)
3865 * (a) partial clusters towards beginning and/or end outside of allocated range
3866 * are not delalloc'ed.
3867 * Ex:
3868 * |----c---=|====c====|====c====|===-c----|
3869 * |++++++ allocated ++++++|
3870 * ==> 4 complete clusters in above example
3871 *
3872 * (b) partial cluster (outside of allocated range) towards either end is
3873 * marked for delayed allocation. In this case, we will exclude that
3874 * cluster.
3875 * Ex:
3876 * |----====c========|========c========|
3877 * |++++++ allocated ++++++|
3878 * ==> 1 complete clusters in above example
3879 *
3880 * Ex:
3881 * |================c================|
3882 * |++++++ allocated ++++++|
3883 * ==> 0 complete clusters in above example
3884 *
3885 * The ext4_da_update_reserve_space will be called only if we
3886 * determine here that there were some "entire" clusters that span
3887 * this 'allocated' range.
3888 * In the non-bigalloc case, this function will just end up returning num_blks
3889 * without ever calling ext4_find_delalloc_range.
3890 */
3891 static unsigned int
3894 {
3903 /* max possible clusters for this allocation */
3908 /* Check towards left side */
3915 allocated_clusters--;
3916 }
3918 /* Now check towards right. */
3925 allocated_clusters--;
3926 }
3929 }
3931 static int
3936 {
3939 ext4_lblk_t ee_block;
3944 /*
3945 * Make sure that the extent is no bigger than we support with
3946 * unwritten extent
3947 */
3962 EXT4_GET_BLOCKS_CONVERT_UNWRITTEN);
3974 }
3975 }
3980 /* first mark the extent as unwritten */
3983 /* note: ext4_ext_correct_indexes() isn't needed here because
3984 * borders are not changed
3985 */
3988 /* Mark modified extent as dirty */
4003 }
4005 static int
4010 {
4022 /*
4023 * When writing into unwritten space, we should not fail to
4024 * allocate metadata blocks for the new extent block if needed.
4025 */
4031 /* get_block() before submit the IO, split the extent */
4037 /*
4038 * Flag the inode(non aio case) or end_io struct (aio case)
4039 * that this IO needs to conversion to written when IO is
4040 * completed
4041 */
4044 else
4048 }
4049 /* IO end_io complete, convert the filled extent to written */
4052 ppath);
4065 }
4066 /* buffered IO case */
4067 /*
4068 * repeat fallocate creation request
4069 * we already have an unwritten extent
4070 */
4074 }
4076 /* buffered READ or buffered write_begin() lookup */
4078 /*
4079 * We have blocks reserved already. We
4080 * return allocated blocks so that delalloc
4081 * won't do block reservation for us. But
4082 * the buffer head will be unmapped so that
4083 * a read from the block returns 0s.
4084 */
4087 }
4089 /* buffered write, writepage time, convert*/
4093 out:
4100 /*
4101 * if we allocated more blocks than requested
4102 * we need to make sure we unmap the extra block
4103 * allocated. The actual needed block will get
4104 * unmapped later when we find the buffer_head marked
4105 * new.
4106 */
4112 }
4115 /*
4116 * If we have done fallocate with the offset that is already
4117 * delayed allocated, we would have block reservation
4118 * and quota reservation done in the delayed write path.
4119 * But fallocate would have already updated quota and block
4120 * count for this offset. So cancel these reservation
4121 */
4128 reserved_clusters,
4130 }
4132 map_out:
4139 }
4140 out1:
4146 out2:
4148 }
4150 /*
4151 * get_implied_cluster_alloc - check to see if the requested
4152 * allocation (in the map structure) overlaps with a cluster already
4153 * allocated in an extent.
4154 * @sb The filesystem superblock structure
4155 * @map The requested lblk->pblk mapping
4156 * @ex The extent structure which might contain an implied
4157 * cluster allocation
4158 *
4159 * This function is called by ext4_ext_map_blocks() after we failed to
4160 * find blocks that were already in the inode's extent tree. Hence,
4161 * we know that the beginning of the requested region cannot overlap
4162 * the extent from the inode's extent tree. There are three cases we
4163 * want to catch. The first is this case:
4164 *
4165 * |--- cluster # N--|
4166 * |--- extent ---| |---- requested region ---|
4167 * |==========|
4168 *
4169 * The second case that we need to test for is this one:
4170 *
4171 * |--------- cluster # N ----------------|
4172 * |--- requested region --| |------- extent ----|
4173 * |=======================|
4174 *
4175 * The third case is when the requested region lies between two extents
4176 * within the same cluster:
4177 * |------------- cluster # N-------------|
4178 * |----- ex -----| |---- ex_right ----|
4179 * |------ requested region ------|
4180 * |================|
4181 *
4182 * In each of the above cases, we need to set the map->m_pblk and
4183 * map->m_len so it corresponds to the return the extent labelled as
4184 * "|====|" from cluster #N, since it is already in use for data in
4185 * cluster EXT4_B2C(sbi, map->m_lblk). We will then return 1 to
4186 * signal to ext4_ext_map_blocks() that map->m_pblk should be treated
4187 * as a new "allocated" block region. Otherwise, we will return 0 and
4188 * ext4_ext_map_blocks() will then allocate one or more new clusters
4189 * by calling ext4_mb_new_blocks().
4190 */
4195 {
4199 ext4_lblk_t rr_cluster_start;
4204 /* The extent passed in that we are trying to match */
4208 /* The requested region passed into ext4_map_blocks() */
4218 /*
4219 * Check for and handle this case:
4220 *
4221 * |--------- cluster # N-------------|
4222 * |------- extent ----|
4223 * |--- requested region ---|
4224 * |===========|
4225 */
4230 /*
4231 * Check for the case where there is already another allocated
4232 * block to the right of 'ex' but before the end of the cluster.
4233 *
4234 * |------------- cluster # N-------------|
4235 * |----- ex -----| |---- ex_right ----|
4236 * |------ requested region ------|
4237 * |================|
4238 */
4242 }
4246 }
4250 }
4253 /*
4254 * Block allocation/map/preallocation routine for extents based files
4255 *
4256 *
4257 * Need to be called with
4258 * down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system block
4259 * (ie, create is zero). Otherwise down_write(&EXT4_I(inode)->i_data_sem)
4260 *
4261 * return > 0, number of of blocks already mapped/allocated
4262 * if create == 0 and these are pre-allocated blocks
4263 * buffer head is unmapped
4264 * otherwise blocks are mapped
4265 *
4266 * return = 0, if plain look up failed (blocks have not been allocated)
4267 * buffer head is unmapped
4268 *
4269 * return < 0, error case.
4270 */
4273 {
4283 ext4_lblk_t cluster_offset;
4291 /* find extent for this block */
4297 }
4301 /*
4302 * consistent leaf must not be empty;
4303 * this situation is possible, though, _during_ tree modification;
4304 * this is why assert can't be put in ext4_find_extent()
4305 */
4313 }
4322 /*
4323 * unwritten extents are treated as holes, except that
4324 * we split out initialized portions during a write.
4325 */
4330 /* if found extent covers block, simply return it */
4333 /* number of remaining blocks in the extent */
4338 /*
4339 * If the extent is initialized check whether the
4340 * caller wants to convert it to unwritten.
4341 */
4356 else
4359 }
4360 }
4362 /*
4363 * requested block isn't allocated yet;
4364 * we couldn't try to create block if create flag is zero
4365 */
4367 /*
4368 * put just found gap into cache to speed up
4369 * subsequent requests
4370 */
4373 }
4375 /*
4376 * Okay, we need to do block allocation.
4377 */
4381 /*
4382 * If we are doing bigalloc, check to see if the extent returned
4383 * by ext4_find_extent() implies a cluster we can use.
4384 */
4391 }
4393 /* find neighbour allocated blocks */
4404 /* Check if the extent after searching to the right implies a
4405 * cluster we can use. */
4412 }
4414 /*
4415 * See if request is beyond maximum number of blocks we can have in
4416 * a single extent. For an initialized extent this limit is
4417 * EXT_INIT_MAX_LEN and for an unwritten extent this limit is
4418 * EXT_UNWRITTEN_MAX_LEN.
4419 */
4427 /* Check if we can really insert (m_lblk)::(m_lblk + m_len) extent */
4432 else
4435 /* allocate new block */
4439 /*
4440 * We calculate the offset from the beginning of the cluster
4441 * for the logical block number, since when we allocate a
4442 * physical cluster, the physical block should start at the
4443 * same offset from the beginning of the cluster. This is
4444 * needed so that future calls to get_implied_cluster_alloc()
4445 * work correctly.
4446 */
4453 else
4454 /* disable in-core preallocation for non-regular files */
4473 got_allocated_blocks:
4474 /* try to insert new extent into found leaf and return */
4477 /* Mark unwritten */
4481 /*
4482 * io_end structure was created for every IO write to an
4483 * unwritten extent. To avoid unnecessary conversion,
4484 * here we flag the IO that really needs the conversion.
4485 * For non asycn direct IO case, flag the inode state
4486 * that we need to perform conversion when IO is done.
4487 */
4490 }
4503 else
4505 EXT4_STATE_DIO_UNWRITTEN);
4506 }
4511 /* free data blocks we just allocated */
4512 /* not a good idea to call discard here directly,
4513 * but otherwise we'd need to call it every free() */
4518 }
4520 /* previous routine could use block we allocated */
4527 /*
4528 * Update reserved blocks/metadata blocks after successful
4529 * block allocation which had been deferred till now.
4530 */
4533 /*
4534 * Check how many clusters we had reserved this allocated range
4535 */
4543 reserved_clusters;
4544 /*
4545 * It seems we claimed few clusters outside of
4546 * the range of this allocation. We should give
4547 * it back to the reservation pool. This can
4548 * happen in the following case:
4549 *
4550 * * Suppose s_cluster_ratio is 4 (i.e., each
4551 * cluster has 4 blocks. Thus, the clusters
4552 * are [0-3],[4-7],[8-11]...
4553 * * First comes delayed allocation write for
4554 * logical blocks 10 & 11. Since there were no
4555 * previous delayed allocated blocks in the
4556 * range [8-11], we would reserve 1 cluster
4557 * for this write.
4558 * * Next comes write for logical blocks 3 to 8.
4559 * In this case, we will reserve 2 clusters
4560 * (for [0-3] and [4-7]; and not for [8-11] as
4561 * that range has a delayed allocated blocks.
4562 * Thus total reserved clusters now becomes 3.
4563 * * Now, during the delayed allocation writeout
4564 * time, we will first write blocks [3-8] and
4565 * allocate 3 clusters for writing these
4566 * blocks. Also, we would claim all these
4567 * three clusters above.
4568 * * Now when we come here to writeout the
4569 * blocks [10-11], we would expect to claim
4570 * the reservation of 1 cluster we had made
4571 * (and we would claim it since there are no
4572 * more delayed allocated blocks in the range
4573 * [8-11]. But our reserved cluster count had
4574 * already gone to 0.
4575 *
4576 * Thus, at the step 4 above when we determine
4577 * that there are still some unwritten delayed
4578 * allocated blocks outside of our current
4579 * block range, we should increment the
4580 * reserved clusters count so that when the
4581 * remaining blocks finally gets written, we
4582 * could claim them.
4583 */
4589 }
4590 /*
4591 * We will claim quota for all newly allocated blocks.
4592 * We're updating the reserved space *after* the
4593 * correction above so we do not accidentally free
4594 * all the metadata reservation because we might
4595 * actually need it later on.
4596 */
4599 }
4600 }
4602 /*
4603 * Cache the extent and update transaction to commit on fdatasync only
4604 * when it is _not_ an unwritten extent.
4605 */
4608 else
4610 out:
4617 out2:
4624 }
4627 {
4629 ext4_lblk_t last_block;
4632 /*
4633 * TODO: optimization is possible here.
4634 * Probably we need not scan at all,
4635 * because page truncation is enough.
4636 */
4638 /* we have to know where to truncate from in crash case */
4644 retry:
4651 }
4655 }
4658 }
4663 {
4672 loff_t epos;
4676 /*
4677 * Don't normalize the request if it can fit in one extent so
4678 * that it doesn't get unnecessarily split into multiple
4679 * extents.
4680 */
4684 /* Wait all existing dio workers, newcomers will block on i_mutex */
4688 /*
4689 * credits to insert 1 extent into extent tree
4690 */
4692 /*
4693 * We can only call ext_depth() on extent based inodes
4694 */
4697 else
4700 retry:
4702 /*
4703 * Recalculate credits when extent tree depth changes.
4704 */
4708 }
4711 credits);
4715 }
4725 }
4738 EXT4_INODE_EOFBLOCKS);
4739 }
4744 }
4749 }
4754 }
4758 {
4768 ext4_lblk_t lblk;
4777 /* Call ext4_force_commit to flush all data in case of data=journal. */
4782 }
4784 /*
4785 * Write out all dirty pages to avoid race conditions
4786 * Then release them.
4787 */
4793 }
4795 /*
4796 * Round up offset. This is not fallocate, we neet to zero out
4797 * blocks, so convert interior block aligned part of the range to
4798 * unwritten and possibly manually zero out unaligned parts of the
4799 * range.
4800 */
4813 else
4818 /*
4819 * Indirect files do not support unwritten extnets
4820 */
4824 }
4832 }
4838 /* Preallocate the range including the unaligned edges */
4848 }
4850 /* Zero range excluding the unaligned edges */
4853 EXT4_EX_NOCACHE);
4855 /* Now release the pages and zero block aligned part of pages*/
4859 /* Wait all existing dio workers, newcomers will block on i_mutex */
4867 }
4871 /*
4872 * In worst case we have to writeout two nonadjacent unwritten
4873 * blocks and update the inode
4874 */
4883 }
4889 /*
4890 * Mark that we allocate beyond EOF so the subsequent truncate
4891 * can proceed even if the new size is the same as i_size.
4892 */
4895 }
4898 /* Zero out partial block at the edges of the range */
4905 out_dio:
4907 out_mutex:
4910 }
4912 /*
4913 * preallocate space for a file. This implements ext4's fallocate file
4914 * operation, which gets called from sys_fallocate system call.
4915 * For block-mapped files, posix_fallocate should fall back to the method
4916 * of writing zeroes to the required new blocks (the same behavior which is
4917 * expected for file systems which do not support fallocate() system call).
4918 */
4920 {
4926 ext4_lblk_t lblk;
4929 /*
4930 * Encrypted inodes can't handle collapse range or insert
4931 * range since we would need to re-encrypt blocks with a
4932 * different IV or XTS tweak (which are based on the logical
4933 * block number).
4934 *
4935 * XXX It's not clear why zero range isn't working, but we'll
4936 * leave it disabled for encrypted inodes for now. This is a
4937 * bug we should fix....
4938 */
4941 FALLOC_FL_ZERO_RANGE)))
4944 /* Return error if mode is not supported */
4947 FALLOC_FL_INSERT_RANGE))
4968 /*
4969 * We can't just convert len to max_blocks because
4970 * If blocksize = 4096 offset = 3072 and len = 2048
4971 */
4981 /*
4982 * We only support preallocation for extent-based files only
4983 */
4987 }
4995 }
5005 }
5006 out:
5010 }
5012 /*
5013 * This function convert a range of blocks to written extents
5014 * The caller of this function will pass the start offset and the size.
5015 * all unwritten extents within this range will be converted to
5016 * written extents.
5017 *
5018 * This function is called from the direct IO end io call back
5019 * function, to convert the fallocated extents after IO is completed.
5020 * Returns 0 on success.
5021 */
5024 {
5032 /*
5033 * We can't just convert len to max_blocks because
5034 * If blocksize = 4096 offset = 3072 and len = 2048
5035 */
5038 /*
5039 * This is somewhat ugly but the idea is clear: When transaction is
5040 * reserved, everything goes into it. Otherwise we rather start several
5041 * smaller transactions for conversion of each extent separately.
5042 */
5045 EXT4_HT_EXT_CONVERT);
5050 /*
5051 * credits to insert 1 extent into extent tree
5052 */
5054 }
5060 credits);
5064 }
5065 }
5067 EXT4_GET_BLOCKS_IO_CONVERT_EXT);
5070 "inode #%lu: block %u: len %u: "
5079 }
5083 }
5085 /*
5086 * If newes is not existing extent (newes->ec_pblk equals zero) find
5087 * delayed extent at start of newes and update newes accordingly and
5088 * return start of the next delayed extent.
5089 *
5090 * If newes is existing extent (newes->ec_pblk is not equal zero)
5091 * return start of next delayed extent or EXT_MAX_BLOCKS if no delayed
5092 * extent found. Leave newes unmodified.
5093 */
5096 {
5104 /*
5105 * No extent in extent-tree contains block @newes->es_pblk,
5106 * then the block may stay in 1)a hole or 2)delayed-extent.
5107 */
5109 /* A hole found. */
5113 /* A hole found. */
5117 }
5120 }
5126 else
5130 }
5131 /* fiemap flags we can handle specified here */
5132 #define EXT4_FIEMAP_FLAGS (FIEMAP_FLAG_SYNC|FIEMAP_FLAG_XATTR)
5136 {
5138 __u64 length;
5143 /* in-inode? */
5161 }
5167 }
5171 {
5172 ext4_lblk_t start_blk;
5183 }
5189 }
5191 /* fallback to generic here if not in extents fmt */
5194 ext4_get_block);
5202 ext4_lblk_t len_blks;
5203 __u64 last_blk;
5211 /*
5212 * Walk the extent tree gathering extent information
5213 * and pushing extents back to the user.
5214 */
5217 }
5219 }
5221 /*
5222 * ext4_access_path:
5223 * Function to access the path buffer for marking it dirty.
5224 * It also checks if there are sufficient credits left in the journal handle
5225 * to update path.
5226 */
5227 static int
5230 {
5236 /*
5237 * Check if need to extend journal credits
5238 * 3 for leaf, sb, and inode plus 2 (bmap and group
5239 * descriptor) for each block group; assume two block
5240 * groups
5241 */
5245 /* EAGAIN is success */
5248 }
5252 }
5254 /*
5255 * ext4_ext_shift_path_extents:
5256 * Shift the extents of a path structure lying between path[depth].p_ext
5257 * and EXT_LAST_EXTENT(path[depth].p_hdr), by @shift blocks. @SHIFT tells
5258 * if it is right shift or left shift operation.
5259 */
5260 static int
5264 {
5289 /* Try to merge to the left. */
5292 &&
5295 ex_last--;
5296 else
5297 ex_start++;
5301 ex_last);
5302 ex_last--;
5303 }
5304 }
5311 }
5313 /* Update index too */
5320 else
5326 /* we are done if current index is not a starting index */
5330 depth--;
5331 }
5333 out:
5335 }
5337 /*
5338 * ext4_ext_shift_extents:
5339 * All the extents which lies in the range from @start to the last allocated
5340 * block for the @inode are shifted either towards left or right (depending
5341 * upon @SHIFT) by @shift blocks.
5342 * On success, 0 is returned, error otherwise.
5343 */
5344 static int
5348 {
5354 /* Let path point to the last extent */
5367 /*
5368 * In case of left shift, Don't start shifting extents until we make
5369 * sure the hole is big enough to accommodate the shift.
5370 */
5384 }
5391 }
5392 }
5394 /*
5395 * In case of left shift, iterator points to start and it is increased
5396 * till we reach stop. In case of right shift, iterator points to stop
5397 * and it is decreased till we reach start.
5398 */
5401 else
5404 /* Its safe to start updating extents */
5415 }
5418 /* Hole, move to the next extent */
5424 }
5425 }
5435 /* Update path extent in case we need to stop */
5437 extent++;
5439 }
5444 }
5445 out:
5449 }
5451 /*
5452 * ext4_collapse_range:
5453 * This implements the fallocate's collapse range functionality for ext4
5454 * Returns: 0 and non-zero on error.
5455 */
5457 {
5465 /*
5466 * We need to test this early because xfstests assumes that a
5467 * collapse range of (0, 1) will return EOPNOTSUPP if the file
5468 * system does not support collapse range.
5469 */
5473 /* Collapse range works only on fs block size aligned offsets. */
5486 /* Call ext4_force_commit to flush all data in case of data=journal. */
5491 }
5493 /*
5494 * Need to round down offset to be aligned with page size boundary
5495 * for page size > block size.
5496 */
5499 /* Write out all dirty pages */
5501 LLONG_MAX);
5505 /* Take mutex lock */
5508 /*
5509 * There is no need to overlap collapse range with EOF, in which case
5510 * it is effectively a truncate operation
5511 */
5515 }
5517 /* Currently just for extent based files */
5521 }
5525 /* Wait for existing dio to complete */
5534 }
5544 }
5550 }
5558 }
5570 out_stop:
5572 out_dio:
5574 out_mutex:
5577 }
5579 /*
5580 * ext4_insert_range:
5581 * This function implements the FALLOC_FL_INSERT_RANGE flag of fallocate.
5582 * The data blocks starting from @offset to the EOF are shifted by @len
5583 * towards right to create a hole in the @inode. Inode size is increased
5584 * by len bytes.
5585 * Returns 0 on success, error otherwise.
5586 */
5588 {
5596 loff_t ioffset;
5598 /*
5599 * We need to test this early because xfstests assumes that an
5600 * insert range of (0, 1) will return EOPNOTSUPP if the file
5601 * system does not support insert range.
5602 */
5606 /* Insert range works only on fs block size aligned offsets. */
5619 /* Call ext4_force_commit to flush all data in case of data=journal */
5624 }
5626 /*
5627 * Need to round down to align start offset to page size boundary
5628 * for page size > block size.
5629 */
5632 /* Write out all dirty pages */
5634 LLONG_MAX);
5638 /* Take mutex lock */
5641 /* Currently just for extent based files */
5645 }
5647 /* Check for wrap through zero */
5651 }
5653 /* Offset should be less than i_size */
5657 }
5661 /* Wait for existing dio to complete */
5670 }
5672 /* Expand file to avoid data loss if there is error while shifting */
5687 }
5695 /*
5696 * If offset_lblk is not the starting block of extent, split
5697 * the extent @offset_lblk
5698 */
5703 EXT4_EXT_MARK_UNWRIT2;
5706 EXT4_EX_NOCACHE |
5707 EXT4_GET_BLOCKS_PRE_IO |
5708 EXT4_GET_BLOCKS_METADATA_NOFAIL);
5709 }
5716 }
5717 }
5724 }
5726 /*
5727 * if offset_lblk lies in a hole which is at start of file, use
5728 * ee_start_lblk to shift extents
5729 */
5738 out_stop:
5740 out_dio:
5742 out_mutex:
5745 }
5747 /**
5748 * ext4_swap_extents - Swap extents between two inodes
5749 *
5750 * @inode1: First inode
5751 * @inode2: Second inode
5752 * @lblk1: Start block for first inode
5753 * @lblk2: Start block for second inode
5754 * @count: Number of blocks to swap
5755 * @mark_unwritten: Mark second inode's extents as unwritten after swap
5756 * @erp: Pointer to save error value
5757 *
5758 * This helper routine does exactly what is promise "swap extents". All other
5759 * stuff such as page-cache locking consistency, bh mapping consistency or
5760 * extent's data copying must be performed by caller.
5761 * Locking:
5762 * i_mutex is held for both inodes
5763 * i_data_sem is locked for write for both inodes
5764 * Assumptions:
5765 * All pages from requested range are locked for both inodes
5766 */
5767 int
5771 {
5798 finish:
5801 }
5807 }
5810 /* Do we have somthing to swap ? */
5819 /* Hole handling */
5824 /* if hole after extent, then go to next extent */
5827 /* If hole before extent, then shift to that extent */
5832 /* Do we have something to swap */
5835 /* Move to the rightest boundary */
5845 }
5847 /* Prepare left boundary */
5854 }
5861 }
5862 /* ext4_split_extent_at() may result in leaf extent split,
5863 * path must to be revalidated. */
5867 /* Prepare right boundary */
5880 }
5887 }
5888 /* ext4_split_extent_at() may result in leaf extent split,
5889 * path must to be revalidated. */
5901 /* Both extents are fully inside boundaries. Swap it now */
5920 /*
5921 * Looks scarry ah..? second inode already points to new blocks,
5922 * and it was successfully dirtied. But luckily error may happen
5923 * only due to journal error, so full transaction will be
5924 * aborted anyway.
5925 */
5933 repeat:
5939 }
5941 }