1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
4 * Written by Alex Tomas <alex@clusterfs.com>
6 * Architecture independence:
7 * Copyright (c) 2005, Bull S.A.
8 * Written by Pierre Peiffer <pierre.peiffer@bull.net>
12 * Extents support for EXT4
15 * - ext4*_error() should be used in some situations
16 * - analyze all BUG()/BUG_ON(), use -EIO where appropriate
17 * - smart tree reduction
21 #include <linux/time.h>
22 #include <linux/jbd2.h>
23 #include <linux/highuid.h>
24 #include <linux/pagemap.h>
25 #include <linux/quotaops.h>
26 #include <linux/string.h>
27 #include <linux/slab.h>
28 #include <linux/uaccess.h>
29 #include <linux/fiemap.h>
30 #include <linux/backing-dev.h>
31 #include "ext4_jbd2.h"
32 #include "ext4_extents.h"
35 #include <trace/events/ext4.h>
38 * used by extent splitting.
40 #define EXT4_EXT_MAY_ZEROOUT 0x1 /* safe to zeroout if split fails \
42 #define EXT4_EXT_MARK_UNWRIT1 0x2 /* mark first half unwritten */
43 #define EXT4_EXT_MARK_UNWRIT2 0x4 /* mark second half unwritten */
45 #define EXT4_EXT_DATA_VALID1 0x8 /* first half contains valid data */
46 #define EXT4_EXT_DATA_VALID2 0x10 /* second half contains valid data */
48 static __le32
ext4_extent_block_csum(struct inode
*inode
,
49 struct ext4_extent_header
*eh
)
51 struct ext4_inode_info
*ei
= EXT4_I(inode
);
52 struct ext4_sb_info
*sbi
= EXT4_SB(inode
->i_sb
);
55 csum
= ext4_chksum(sbi
, ei
->i_csum_seed
, (__u8
*)eh
,
56 EXT4_EXTENT_TAIL_OFFSET(eh
));
57 return cpu_to_le32(csum
);
60 static int ext4_extent_block_csum_verify(struct inode
*inode
,
61 struct ext4_extent_header
*eh
)
63 struct ext4_extent_tail
*et
;
65 if (!ext4_has_metadata_csum(inode
->i_sb
))
68 et
= find_ext4_extent_tail(eh
);
69 if (et
->et_checksum
!= ext4_extent_block_csum(inode
, eh
))
74 static void ext4_extent_block_csum_set(struct inode
*inode
,
75 struct ext4_extent_header
*eh
)
77 struct ext4_extent_tail
*et
;
79 if (!ext4_has_metadata_csum(inode
->i_sb
))
82 et
= find_ext4_extent_tail(eh
);
83 et
->et_checksum
= ext4_extent_block_csum(inode
, eh
);
86 static int ext4_split_extent(handle_t
*handle
,
88 struct ext4_ext_path
**ppath
,
89 struct ext4_map_blocks
*map
,
93 static int ext4_split_extent_at(handle_t
*handle
,
95 struct ext4_ext_path
**ppath
,
100 static int ext4_find_delayed_extent(struct inode
*inode
,
101 struct extent_status
*newes
);
103 static int ext4_ext_truncate_extend_restart(handle_t
*handle
,
109 if (!ext4_handle_valid(handle
))
111 if (handle
->h_buffer_credits
>= needed
)
114 * If we need to extend the journal get a few extra blocks
115 * while we're at it for efficiency's sake.
118 err
= ext4_journal_extend(handle
, needed
- handle
->h_buffer_credits
);
121 err
= ext4_truncate_restart_trans(handle
, inode
, needed
);
133 static int ext4_ext_get_access(handle_t
*handle
, struct inode
*inode
,
134 struct ext4_ext_path
*path
)
137 /* path points to block */
138 BUFFER_TRACE(path
->p_bh
, "get_write_access");
139 return ext4_journal_get_write_access(handle
, path
->p_bh
);
141 /* path points to leaf/index in inode body */
142 /* we use in-core data, no need to protect them */
152 int __ext4_ext_dirty(const char *where
, unsigned int line
, handle_t
*handle
,
153 struct inode
*inode
, struct ext4_ext_path
*path
)
157 WARN_ON(!rwsem_is_locked(&EXT4_I(inode
)->i_data_sem
));
159 ext4_extent_block_csum_set(inode
, ext_block_hdr(path
->p_bh
));
160 /* path points to block */
161 err
= __ext4_handle_dirty_metadata(where
, line
, handle
,
164 /* path points to leaf/index in inode body */
165 err
= ext4_mark_inode_dirty(handle
, inode
);
170 static ext4_fsblk_t
ext4_ext_find_goal(struct inode
*inode
,
171 struct ext4_ext_path
*path
,
175 int depth
= path
->p_depth
;
176 struct ext4_extent
*ex
;
179 * Try to predict block placement assuming that we are
180 * filling in a file which will eventually be
181 * non-sparse --- i.e., in the case of libbfd writing
182 * an ELF object sections out-of-order but in a way
183 * the eventually results in a contiguous object or
184 * executable file, or some database extending a table
185 * space file. However, this is actually somewhat
186 * non-ideal if we are writing a sparse file such as
187 * qemu or KVM writing a raw image file that is going
188 * to stay fairly sparse, since it will end up
189 * fragmenting the file system's free space. Maybe we
190 * should have some hueristics or some way to allow
191 * userspace to pass a hint to file system,
192 * especially if the latter case turns out to be
195 ex
= path
[depth
].p_ext
;
197 ext4_fsblk_t ext_pblk
= ext4_ext_pblock(ex
);
198 ext4_lblk_t ext_block
= le32_to_cpu(ex
->ee_block
);
200 if (block
> ext_block
)
201 return ext_pblk
+ (block
- ext_block
);
203 return ext_pblk
- (ext_block
- block
);
206 /* it looks like index is empty;
207 * try to find starting block from index itself */
208 if (path
[depth
].p_bh
)
209 return path
[depth
].p_bh
->b_blocknr
;
212 /* OK. use inode's group */
213 return ext4_inode_to_goal_block(inode
);
217 * Allocation for a meta data block
220 ext4_ext_new_meta_block(handle_t
*handle
, struct inode
*inode
,
221 struct ext4_ext_path
*path
,
222 struct ext4_extent
*ex
, int *err
, unsigned int flags
)
224 ext4_fsblk_t goal
, newblock
;
226 goal
= ext4_ext_find_goal(inode
, path
, le32_to_cpu(ex
->ee_block
));
227 newblock
= ext4_new_meta_blocks(handle
, inode
, goal
, flags
,
232 static inline int ext4_ext_space_block(struct inode
*inode
, int check
)
236 size
= (inode
->i_sb
->s_blocksize
- sizeof(struct ext4_extent_header
))
237 / sizeof(struct ext4_extent
);
238 #ifdef AGGRESSIVE_TEST
239 if (!check
&& size
> 6)
245 static inline int ext4_ext_space_block_idx(struct inode
*inode
, int check
)
249 size
= (inode
->i_sb
->s_blocksize
- sizeof(struct ext4_extent_header
))
250 / sizeof(struct ext4_extent_idx
);
251 #ifdef AGGRESSIVE_TEST
252 if (!check
&& size
> 5)
258 static inline int ext4_ext_space_root(struct inode
*inode
, int check
)
262 size
= sizeof(EXT4_I(inode
)->i_data
);
263 size
-= sizeof(struct ext4_extent_header
);
264 size
/= sizeof(struct ext4_extent
);
265 #ifdef AGGRESSIVE_TEST
266 if (!check
&& size
> 3)
272 static inline int ext4_ext_space_root_idx(struct inode
*inode
, int check
)
276 size
= sizeof(EXT4_I(inode
)->i_data
);
277 size
-= sizeof(struct ext4_extent_header
);
278 size
/= sizeof(struct ext4_extent_idx
);
279 #ifdef AGGRESSIVE_TEST
280 if (!check
&& size
> 4)
287 ext4_force_split_extent_at(handle_t
*handle
, struct inode
*inode
,
288 struct ext4_ext_path
**ppath
, ext4_lblk_t lblk
,
291 struct ext4_ext_path
*path
= *ppath
;
292 int unwritten
= ext4_ext_is_unwritten(path
[path
->p_depth
].p_ext
);
294 return ext4_split_extent_at(handle
, inode
, ppath
, lblk
, unwritten
?
295 EXT4_EXT_MARK_UNWRIT1
|EXT4_EXT_MARK_UNWRIT2
: 0,
296 EXT4_EX_NOCACHE
| EXT4_GET_BLOCKS_PRE_IO
|
297 (nofail
? EXT4_GET_BLOCKS_METADATA_NOFAIL
:0));
301 * Calculate the number of metadata blocks needed
302 * to allocate @blocks
303 * Worse case is one block per extent
305 int ext4_ext_calc_metadata_amount(struct inode
*inode
, ext4_lblk_t lblock
)
307 struct ext4_inode_info
*ei
= EXT4_I(inode
);
310 idxs
= ((inode
->i_sb
->s_blocksize
- sizeof(struct ext4_extent_header
))
311 / sizeof(struct ext4_extent_idx
));
314 * If the new delayed allocation block is contiguous with the
315 * previous da block, it can share index blocks with the
316 * previous block, so we only need to allocate a new index
317 * block every idxs leaf blocks. At ldxs**2 blocks, we need
318 * an additional index block, and at ldxs**3 blocks, yet
319 * another index blocks.
321 if (ei
->i_da_metadata_calc_len
&&
322 ei
->i_da_metadata_calc_last_lblock
+1 == lblock
) {
325 if ((ei
->i_da_metadata_calc_len
% idxs
) == 0)
327 if ((ei
->i_da_metadata_calc_len
% (idxs
*idxs
)) == 0)
329 if ((ei
->i_da_metadata_calc_len
% (idxs
*idxs
*idxs
)) == 0) {
331 ei
->i_da_metadata_calc_len
= 0;
333 ei
->i_da_metadata_calc_len
++;
334 ei
->i_da_metadata_calc_last_lblock
++;
339 * In the worst case we need a new set of index blocks at
340 * every level of the inode's extent tree.
342 ei
->i_da_metadata_calc_len
= 1;
343 ei
->i_da_metadata_calc_last_lblock
= lblock
;
344 return ext_depth(inode
) + 1;
348 ext4_ext_max_entries(struct inode
*inode
, int depth
)
352 if (depth
== ext_depth(inode
)) {
354 max
= ext4_ext_space_root(inode
, 1);
356 max
= ext4_ext_space_root_idx(inode
, 1);
359 max
= ext4_ext_space_block(inode
, 1);
361 max
= ext4_ext_space_block_idx(inode
, 1);
367 static int ext4_valid_extent(struct inode
*inode
, struct ext4_extent
*ext
)
369 ext4_fsblk_t block
= ext4_ext_pblock(ext
);
370 int len
= ext4_ext_get_actual_len(ext
);
371 ext4_lblk_t lblock
= le32_to_cpu(ext
->ee_block
);
376 * - overflow/wrap-around
378 if (lblock
+ len
<= lblock
)
380 return ext4_data_block_valid(EXT4_SB(inode
->i_sb
), block
, len
);
383 static int ext4_valid_extent_idx(struct inode
*inode
,
384 struct ext4_extent_idx
*ext_idx
)
386 ext4_fsblk_t block
= ext4_idx_pblock(ext_idx
);
388 return ext4_data_block_valid(EXT4_SB(inode
->i_sb
), block
, 1);
391 static int ext4_valid_extent_entries(struct inode
*inode
,
392 struct ext4_extent_header
*eh
,
395 unsigned short entries
;
396 if (eh
->eh_entries
== 0)
399 entries
= le16_to_cpu(eh
->eh_entries
);
403 struct ext4_extent
*ext
= EXT_FIRST_EXTENT(eh
);
404 struct ext4_super_block
*es
= EXT4_SB(inode
->i_sb
)->s_es
;
405 ext4_fsblk_t pblock
= 0;
406 ext4_lblk_t lblock
= 0;
407 ext4_lblk_t prev
= 0;
410 if (!ext4_valid_extent(inode
, ext
))
413 /* Check for overlapping extents */
414 lblock
= le32_to_cpu(ext
->ee_block
);
415 len
= ext4_ext_get_actual_len(ext
);
416 if ((lblock
<= prev
) && prev
) {
417 pblock
= ext4_ext_pblock(ext
);
418 es
->s_last_error_block
= cpu_to_le64(pblock
);
423 prev
= lblock
+ len
- 1;
426 struct ext4_extent_idx
*ext_idx
= EXT_FIRST_INDEX(eh
);
428 if (!ext4_valid_extent_idx(inode
, ext_idx
))
437 static int __ext4_ext_check(const char *function
, unsigned int line
,
438 struct inode
*inode
, struct ext4_extent_header
*eh
,
439 int depth
, ext4_fsblk_t pblk
)
441 const char *error_msg
;
442 int max
= 0, err
= -EFSCORRUPTED
;
444 if (unlikely(eh
->eh_magic
!= EXT4_EXT_MAGIC
)) {
445 error_msg
= "invalid magic";
448 if (unlikely(le16_to_cpu(eh
->eh_depth
) != depth
)) {
449 error_msg
= "unexpected eh_depth";
452 if (unlikely(eh
->eh_max
== 0)) {
453 error_msg
= "invalid eh_max";
456 max
= ext4_ext_max_entries(inode
, depth
);
457 if (unlikely(le16_to_cpu(eh
->eh_max
) > max
)) {
458 error_msg
= "too large eh_max";
461 if (unlikely(le16_to_cpu(eh
->eh_entries
) > le16_to_cpu(eh
->eh_max
))) {
462 error_msg
= "invalid eh_entries";
465 if (!ext4_valid_extent_entries(inode
, eh
, depth
)) {
466 error_msg
= "invalid extent entries";
469 if (unlikely(depth
> 32)) {
470 error_msg
= "too large eh_depth";
473 /* Verify checksum on non-root extent tree nodes */
474 if (ext_depth(inode
) != depth
&&
475 !ext4_extent_block_csum_verify(inode
, eh
)) {
476 error_msg
= "extent tree corrupted";
483 ext4_error_inode(inode
, function
, line
, 0,
484 "pblk %llu bad header/extent: %s - magic %x, "
485 "entries %u, max %u(%u), depth %u(%u)",
486 (unsigned long long) pblk
, error_msg
,
487 le16_to_cpu(eh
->eh_magic
),
488 le16_to_cpu(eh
->eh_entries
), le16_to_cpu(eh
->eh_max
),
489 max
, le16_to_cpu(eh
->eh_depth
), depth
);
493 #define ext4_ext_check(inode, eh, depth, pblk) \
494 __ext4_ext_check(__func__, __LINE__, (inode), (eh), (depth), (pblk))
496 int ext4_ext_check_inode(struct inode
*inode
)
498 return ext4_ext_check(inode
, ext_inode_hdr(inode
), ext_depth(inode
), 0);
501 static struct buffer_head
*
502 __read_extent_tree_block(const char *function
, unsigned int line
,
503 struct inode
*inode
, ext4_fsblk_t pblk
, int depth
,
506 struct buffer_head
*bh
;
509 bh
= sb_getblk_gfp(inode
->i_sb
, pblk
, __GFP_MOVABLE
| GFP_NOFS
);
511 return ERR_PTR(-ENOMEM
);
513 if (!bh_uptodate_or_lock(bh
)) {
514 trace_ext4_ext_load_extent(inode
, pblk
, _RET_IP_
);
515 err
= bh_submit_read(bh
);
519 if (buffer_verified(bh
) && !(flags
& EXT4_EX_FORCE_CACHE
))
521 err
= __ext4_ext_check(function
, line
, inode
,
522 ext_block_hdr(bh
), depth
, pblk
);
525 set_buffer_verified(bh
);
527 * If this is a leaf block, cache all of its entries
529 if (!(flags
& EXT4_EX_NOCACHE
) && depth
== 0) {
530 struct ext4_extent_header
*eh
= ext_block_hdr(bh
);
531 struct ext4_extent
*ex
= EXT_FIRST_EXTENT(eh
);
532 ext4_lblk_t prev
= 0;
535 for (i
= le16_to_cpu(eh
->eh_entries
); i
> 0; i
--, ex
++) {
536 unsigned int status
= EXTENT_STATUS_WRITTEN
;
537 ext4_lblk_t lblk
= le32_to_cpu(ex
->ee_block
);
538 int len
= ext4_ext_get_actual_len(ex
);
540 if (prev
&& (prev
!= lblk
))
541 ext4_es_cache_extent(inode
, prev
,
545 if (ext4_ext_is_unwritten(ex
))
546 status
= EXTENT_STATUS_UNWRITTEN
;
547 ext4_es_cache_extent(inode
, lblk
, len
,
548 ext4_ext_pblock(ex
), status
);
559 #define read_extent_tree_block(inode, pblk, depth, flags) \
560 __read_extent_tree_block(__func__, __LINE__, (inode), (pblk), \
564 * This function is called to cache a file's extent information in the
567 int ext4_ext_precache(struct inode
*inode
)
569 struct ext4_inode_info
*ei
= EXT4_I(inode
);
570 struct ext4_ext_path
*path
= NULL
;
571 struct buffer_head
*bh
;
572 int i
= 0, depth
, ret
= 0;
574 if (!ext4_test_inode_flag(inode
, EXT4_INODE_EXTENTS
))
575 return 0; /* not an extent-mapped inode */
577 down_read(&ei
->i_data_sem
);
578 depth
= ext_depth(inode
);
580 path
= kcalloc(depth
+ 1, sizeof(struct ext4_ext_path
),
583 up_read(&ei
->i_data_sem
);
587 /* Don't cache anything if there are no external extent blocks */
590 path
[0].p_hdr
= ext_inode_hdr(inode
);
591 ret
= ext4_ext_check(inode
, path
[0].p_hdr
, depth
, 0);
594 path
[0].p_idx
= EXT_FIRST_INDEX(path
[0].p_hdr
);
597 * If this is a leaf block or we've reached the end of
598 * the index block, go up
601 path
[i
].p_idx
> EXT_LAST_INDEX(path
[i
].p_hdr
)) {
602 brelse(path
[i
].p_bh
);
607 bh
= read_extent_tree_block(inode
,
608 ext4_idx_pblock(path
[i
].p_idx
++),
610 EXT4_EX_FORCE_CACHE
);
617 path
[i
].p_hdr
= ext_block_hdr(bh
);
618 path
[i
].p_idx
= EXT_FIRST_INDEX(path
[i
].p_hdr
);
620 ext4_set_inode_state(inode
, EXT4_STATE_EXT_PRECACHED
);
622 up_read(&ei
->i_data_sem
);
623 ext4_ext_drop_refs(path
);
629 static void ext4_ext_show_path(struct inode
*inode
, struct ext4_ext_path
*path
)
631 int k
, l
= path
->p_depth
;
634 for (k
= 0; k
<= l
; k
++, path
++) {
636 ext_debug(" %d->%llu", le32_to_cpu(path
->p_idx
->ei_block
),
637 ext4_idx_pblock(path
->p_idx
));
638 } else if (path
->p_ext
) {
639 ext_debug(" %d:[%d]%d:%llu ",
640 le32_to_cpu(path
->p_ext
->ee_block
),
641 ext4_ext_is_unwritten(path
->p_ext
),
642 ext4_ext_get_actual_len(path
->p_ext
),
643 ext4_ext_pblock(path
->p_ext
));
650 static void ext4_ext_show_leaf(struct inode
*inode
, struct ext4_ext_path
*path
)
652 int depth
= ext_depth(inode
);
653 struct ext4_extent_header
*eh
;
654 struct ext4_extent
*ex
;
660 eh
= path
[depth
].p_hdr
;
661 ex
= EXT_FIRST_EXTENT(eh
);
663 ext_debug("Displaying leaf extents for inode %lu\n", inode
->i_ino
);
665 for (i
= 0; i
< le16_to_cpu(eh
->eh_entries
); i
++, ex
++) {
666 ext_debug("%d:[%d]%d:%llu ", le32_to_cpu(ex
->ee_block
),
667 ext4_ext_is_unwritten(ex
),
668 ext4_ext_get_actual_len(ex
), ext4_ext_pblock(ex
));
673 static void ext4_ext_show_move(struct inode
*inode
, struct ext4_ext_path
*path
,
674 ext4_fsblk_t newblock
, int level
)
676 int depth
= ext_depth(inode
);
677 struct ext4_extent
*ex
;
679 if (depth
!= level
) {
680 struct ext4_extent_idx
*idx
;
681 idx
= path
[level
].p_idx
;
682 while (idx
<= EXT_MAX_INDEX(path
[level
].p_hdr
)) {
683 ext_debug("%d: move %d:%llu in new index %llu\n", level
,
684 le32_to_cpu(idx
->ei_block
),
685 ext4_idx_pblock(idx
),
693 ex
= path
[depth
].p_ext
;
694 while (ex
<= EXT_MAX_EXTENT(path
[depth
].p_hdr
)) {
695 ext_debug("move %d:%llu:[%d]%d in new leaf %llu\n",
696 le32_to_cpu(ex
->ee_block
),
698 ext4_ext_is_unwritten(ex
),
699 ext4_ext_get_actual_len(ex
),
706 #define ext4_ext_show_path(inode, path)
707 #define ext4_ext_show_leaf(inode, path)
708 #define ext4_ext_show_move(inode, path, newblock, level)
711 void ext4_ext_drop_refs(struct ext4_ext_path
*path
)
717 depth
= path
->p_depth
;
718 for (i
= 0; i
<= depth
; i
++, path
++)
726 * ext4_ext_binsearch_idx:
727 * binary search for the closest index of the given block
728 * the header must be checked before calling this
731 ext4_ext_binsearch_idx(struct inode
*inode
,
732 struct ext4_ext_path
*path
, ext4_lblk_t block
)
734 struct ext4_extent_header
*eh
= path
->p_hdr
;
735 struct ext4_extent_idx
*r
, *l
, *m
;
738 ext_debug("binsearch for %u(idx): ", block
);
740 l
= EXT_FIRST_INDEX(eh
) + 1;
741 r
= EXT_LAST_INDEX(eh
);
744 if (block
< le32_to_cpu(m
->ei_block
))
748 ext_debug("%p(%u):%p(%u):%p(%u) ", l
, le32_to_cpu(l
->ei_block
),
749 m
, le32_to_cpu(m
->ei_block
),
750 r
, le32_to_cpu(r
->ei_block
));
754 ext_debug(" -> %u->%lld ", le32_to_cpu(path
->p_idx
->ei_block
),
755 ext4_idx_pblock(path
->p_idx
));
757 #ifdef CHECK_BINSEARCH
759 struct ext4_extent_idx
*chix
, *ix
;
762 chix
= ix
= EXT_FIRST_INDEX(eh
);
763 for (k
= 0; k
< le16_to_cpu(eh
->eh_entries
); k
++, ix
++) {
765 le32_to_cpu(ix
->ei_block
) <= le32_to_cpu(ix
[-1].ei_block
)) {
766 printk(KERN_DEBUG
"k=%d, ix=0x%p, "
768 ix
, EXT_FIRST_INDEX(eh
));
769 printk(KERN_DEBUG
"%u <= %u\n",
770 le32_to_cpu(ix
->ei_block
),
771 le32_to_cpu(ix
[-1].ei_block
));
773 BUG_ON(k
&& le32_to_cpu(ix
->ei_block
)
774 <= le32_to_cpu(ix
[-1].ei_block
));
775 if (block
< le32_to_cpu(ix
->ei_block
))
779 BUG_ON(chix
!= path
->p_idx
);
786 * ext4_ext_binsearch:
787 * binary search for closest extent of the given block
788 * the header must be checked before calling this
791 ext4_ext_binsearch(struct inode
*inode
,
792 struct ext4_ext_path
*path
, ext4_lblk_t block
)
794 struct ext4_extent_header
*eh
= path
->p_hdr
;
795 struct ext4_extent
*r
, *l
, *m
;
797 if (eh
->eh_entries
== 0) {
799 * this leaf is empty:
800 * we get such a leaf in split/add case
805 ext_debug("binsearch for %u: ", block
);
807 l
= EXT_FIRST_EXTENT(eh
) + 1;
808 r
= EXT_LAST_EXTENT(eh
);
812 if (block
< le32_to_cpu(m
->ee_block
))
816 ext_debug("%p(%u):%p(%u):%p(%u) ", l
, le32_to_cpu(l
->ee_block
),
817 m
, le32_to_cpu(m
->ee_block
),
818 r
, le32_to_cpu(r
->ee_block
));
822 ext_debug(" -> %d:%llu:[%d]%d ",
823 le32_to_cpu(path
->p_ext
->ee_block
),
824 ext4_ext_pblock(path
->p_ext
),
825 ext4_ext_is_unwritten(path
->p_ext
),
826 ext4_ext_get_actual_len(path
->p_ext
));
828 #ifdef CHECK_BINSEARCH
830 struct ext4_extent
*chex
, *ex
;
833 chex
= ex
= EXT_FIRST_EXTENT(eh
);
834 for (k
= 0; k
< le16_to_cpu(eh
->eh_entries
); k
++, ex
++) {
835 BUG_ON(k
&& le32_to_cpu(ex
->ee_block
)
836 <= le32_to_cpu(ex
[-1].ee_block
));
837 if (block
< le32_to_cpu(ex
->ee_block
))
841 BUG_ON(chex
!= path
->p_ext
);
847 int ext4_ext_tree_init(handle_t
*handle
, struct inode
*inode
)
849 struct ext4_extent_header
*eh
;
851 eh
= ext_inode_hdr(inode
);
854 eh
->eh_magic
= EXT4_EXT_MAGIC
;
855 eh
->eh_max
= cpu_to_le16(ext4_ext_space_root(inode
, 0));
856 ext4_mark_inode_dirty(handle
, inode
);
860 struct ext4_ext_path
*
861 ext4_find_extent(struct inode
*inode
, ext4_lblk_t block
,
862 struct ext4_ext_path
**orig_path
, int flags
)
864 struct ext4_extent_header
*eh
;
865 struct buffer_head
*bh
;
866 struct ext4_ext_path
*path
= orig_path
? *orig_path
: NULL
;
867 short int depth
, i
, ppos
= 0;
870 eh
= ext_inode_hdr(inode
);
871 depth
= ext_depth(inode
);
872 if (depth
< 0 || depth
> EXT4_MAX_EXTENT_DEPTH
) {
873 EXT4_ERROR_INODE(inode
, "inode has invalid extent depth: %d",
880 ext4_ext_drop_refs(path
);
881 if (depth
> path
[0].p_maxdepth
) {
883 *orig_path
= path
= NULL
;
887 /* account possible depth increase */
888 path
= kcalloc(depth
+ 2, sizeof(struct ext4_ext_path
),
891 return ERR_PTR(-ENOMEM
);
892 path
[0].p_maxdepth
= depth
+ 1;
898 /* walk through the tree */
900 ext_debug("depth %d: num %d, max %d\n",
901 ppos
, le16_to_cpu(eh
->eh_entries
), le16_to_cpu(eh
->eh_max
));
903 ext4_ext_binsearch_idx(inode
, path
+ ppos
, block
);
904 path
[ppos
].p_block
= ext4_idx_pblock(path
[ppos
].p_idx
);
905 path
[ppos
].p_depth
= i
;
906 path
[ppos
].p_ext
= NULL
;
908 bh
= read_extent_tree_block(inode
, path
[ppos
].p_block
, --i
,
915 eh
= ext_block_hdr(bh
);
917 path
[ppos
].p_bh
= bh
;
918 path
[ppos
].p_hdr
= eh
;
921 path
[ppos
].p_depth
= i
;
922 path
[ppos
].p_ext
= NULL
;
923 path
[ppos
].p_idx
= NULL
;
926 ext4_ext_binsearch(inode
, path
+ ppos
, block
);
927 /* if not an empty leaf */
928 if (path
[ppos
].p_ext
)
929 path
[ppos
].p_block
= ext4_ext_pblock(path
[ppos
].p_ext
);
931 ext4_ext_show_path(inode
, path
);
936 ext4_ext_drop_refs(path
);
944 * ext4_ext_insert_index:
945 * insert new index [@logical;@ptr] into the block at @curp;
946 * check where to insert: before @curp or after @curp
948 static int ext4_ext_insert_index(handle_t
*handle
, struct inode
*inode
,
949 struct ext4_ext_path
*curp
,
950 int logical
, ext4_fsblk_t ptr
)
952 struct ext4_extent_idx
*ix
;
955 err
= ext4_ext_get_access(handle
, inode
, curp
);
959 if (unlikely(logical
== le32_to_cpu(curp
->p_idx
->ei_block
))) {
960 EXT4_ERROR_INODE(inode
,
961 "logical %d == ei_block %d!",
962 logical
, le32_to_cpu(curp
->p_idx
->ei_block
));
963 return -EFSCORRUPTED
;
966 if (unlikely(le16_to_cpu(curp
->p_hdr
->eh_entries
)
967 >= le16_to_cpu(curp
->p_hdr
->eh_max
))) {
968 EXT4_ERROR_INODE(inode
,
969 "eh_entries %d >= eh_max %d!",
970 le16_to_cpu(curp
->p_hdr
->eh_entries
),
971 le16_to_cpu(curp
->p_hdr
->eh_max
));
972 return -EFSCORRUPTED
;
975 if (logical
> le32_to_cpu(curp
->p_idx
->ei_block
)) {
977 ext_debug("insert new index %d after: %llu\n", logical
, ptr
);
978 ix
= curp
->p_idx
+ 1;
981 ext_debug("insert new index %d before: %llu\n", logical
, ptr
);
985 len
= EXT_LAST_INDEX(curp
->p_hdr
) - ix
+ 1;
988 ext_debug("insert new index %d: "
989 "move %d indices from 0x%p to 0x%p\n",
990 logical
, len
, ix
, ix
+ 1);
991 memmove(ix
+ 1, ix
, len
* sizeof(struct ext4_extent_idx
));
994 if (unlikely(ix
> EXT_MAX_INDEX(curp
->p_hdr
))) {
995 EXT4_ERROR_INODE(inode
, "ix > EXT_MAX_INDEX!");
996 return -EFSCORRUPTED
;
999 ix
->ei_block
= cpu_to_le32(logical
);
1000 ext4_idx_store_pblock(ix
, ptr
);
1001 le16_add_cpu(&curp
->p_hdr
->eh_entries
, 1);
1003 if (unlikely(ix
> EXT_LAST_INDEX(curp
->p_hdr
))) {
1004 EXT4_ERROR_INODE(inode
, "ix > EXT_LAST_INDEX!");
1005 return -EFSCORRUPTED
;
1008 err
= ext4_ext_dirty(handle
, inode
, curp
);
1009 ext4_std_error(inode
->i_sb
, err
);
1016 * inserts new subtree into the path, using free index entry
1018 * - allocates all needed blocks (new leaf and all intermediate index blocks)
1019 * - makes decision where to split
1020 * - moves remaining extents and index entries (right to the split point)
1021 * into the newly allocated blocks
1022 * - initializes subtree
1024 static int ext4_ext_split(handle_t
*handle
, struct inode
*inode
,
1026 struct ext4_ext_path
*path
,
1027 struct ext4_extent
*newext
, int at
)
1029 struct buffer_head
*bh
= NULL
;
1030 int depth
= ext_depth(inode
);
1031 struct ext4_extent_header
*neh
;
1032 struct ext4_extent_idx
*fidx
;
1033 int i
= at
, k
, m
, a
;
1034 ext4_fsblk_t newblock
, oldblock
;
1036 ext4_fsblk_t
*ablocks
= NULL
; /* array of allocated blocks */
1039 /* make decision: where to split? */
1040 /* FIXME: now decision is simplest: at current extent */
1042 /* if current leaf will be split, then we should use
1043 * border from split point */
1044 if (unlikely(path
[depth
].p_ext
> EXT_MAX_EXTENT(path
[depth
].p_hdr
))) {
1045 EXT4_ERROR_INODE(inode
, "p_ext > EXT_MAX_EXTENT!");
1046 return -EFSCORRUPTED
;
1048 if (path
[depth
].p_ext
!= EXT_MAX_EXTENT(path
[depth
].p_hdr
)) {
1049 border
= path
[depth
].p_ext
[1].ee_block
;
1050 ext_debug("leaf will be split."
1051 " next leaf starts at %d\n",
1052 le32_to_cpu(border
));
1054 border
= newext
->ee_block
;
1055 ext_debug("leaf will be added."
1056 " next leaf starts at %d\n",
1057 le32_to_cpu(border
));
1061 * If error occurs, then we break processing
1062 * and mark filesystem read-only. index won't
1063 * be inserted and tree will be in consistent
1064 * state. Next mount will repair buffers too.
1068 * Get array to track all allocated blocks.
1069 * We need this to handle errors and free blocks
1072 ablocks
= kcalloc(depth
, sizeof(ext4_fsblk_t
), GFP_NOFS
);
1076 /* allocate all needed blocks */
1077 ext_debug("allocate %d blocks for indexes/leaf\n", depth
- at
);
1078 for (a
= 0; a
< depth
- at
; a
++) {
1079 newblock
= ext4_ext_new_meta_block(handle
, inode
, path
,
1080 newext
, &err
, flags
);
1083 ablocks
[a
] = newblock
;
1086 /* initialize new leaf */
1087 newblock
= ablocks
[--a
];
1088 if (unlikely(newblock
== 0)) {
1089 EXT4_ERROR_INODE(inode
, "newblock == 0!");
1090 err
= -EFSCORRUPTED
;
1093 bh
= sb_getblk_gfp(inode
->i_sb
, newblock
, __GFP_MOVABLE
| GFP_NOFS
);
1094 if (unlikely(!bh
)) {
1100 err
= ext4_journal_get_create_access(handle
, bh
);
1104 neh
= ext_block_hdr(bh
);
1105 neh
->eh_entries
= 0;
1106 neh
->eh_max
= cpu_to_le16(ext4_ext_space_block(inode
, 0));
1107 neh
->eh_magic
= EXT4_EXT_MAGIC
;
1110 /* move remainder of path[depth] to the new leaf */
1111 if (unlikely(path
[depth
].p_hdr
->eh_entries
!=
1112 path
[depth
].p_hdr
->eh_max
)) {
1113 EXT4_ERROR_INODE(inode
, "eh_entries %d != eh_max %d!",
1114 path
[depth
].p_hdr
->eh_entries
,
1115 path
[depth
].p_hdr
->eh_max
);
1116 err
= -EFSCORRUPTED
;
1119 /* start copy from next extent */
1120 m
= EXT_MAX_EXTENT(path
[depth
].p_hdr
) - path
[depth
].p_ext
++;
1121 ext4_ext_show_move(inode
, path
, newblock
, depth
);
1123 struct ext4_extent
*ex
;
1124 ex
= EXT_FIRST_EXTENT(neh
);
1125 memmove(ex
, path
[depth
].p_ext
, sizeof(struct ext4_extent
) * m
);
1126 le16_add_cpu(&neh
->eh_entries
, m
);
1129 ext4_extent_block_csum_set(inode
, neh
);
1130 set_buffer_uptodate(bh
);
1133 err
= ext4_handle_dirty_metadata(handle
, inode
, bh
);
1139 /* correct old leaf */
1141 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
1144 le16_add_cpu(&path
[depth
].p_hdr
->eh_entries
, -m
);
1145 err
= ext4_ext_dirty(handle
, inode
, path
+ depth
);
1151 /* create intermediate indexes */
1153 if (unlikely(k
< 0)) {
1154 EXT4_ERROR_INODE(inode
, "k %d < 0!", k
);
1155 err
= -EFSCORRUPTED
;
1159 ext_debug("create %d intermediate indices\n", k
);
1160 /* insert new index into current index block */
1161 /* current depth stored in i var */
1164 oldblock
= newblock
;
1165 newblock
= ablocks
[--a
];
1166 bh
= sb_getblk(inode
->i_sb
, newblock
);
1167 if (unlikely(!bh
)) {
1173 err
= ext4_journal_get_create_access(handle
, bh
);
1177 neh
= ext_block_hdr(bh
);
1178 neh
->eh_entries
= cpu_to_le16(1);
1179 neh
->eh_magic
= EXT4_EXT_MAGIC
;
1180 neh
->eh_max
= cpu_to_le16(ext4_ext_space_block_idx(inode
, 0));
1181 neh
->eh_depth
= cpu_to_le16(depth
- i
);
1182 fidx
= EXT_FIRST_INDEX(neh
);
1183 fidx
->ei_block
= border
;
1184 ext4_idx_store_pblock(fidx
, oldblock
);
1186 ext_debug("int.index at %d (block %llu): %u -> %llu\n",
1187 i
, newblock
, le32_to_cpu(border
), oldblock
);
1189 /* move remainder of path[i] to the new index block */
1190 if (unlikely(EXT_MAX_INDEX(path
[i
].p_hdr
) !=
1191 EXT_LAST_INDEX(path
[i
].p_hdr
))) {
1192 EXT4_ERROR_INODE(inode
,
1193 "EXT_MAX_INDEX != EXT_LAST_INDEX ee_block %d!",
1194 le32_to_cpu(path
[i
].p_ext
->ee_block
));
1195 err
= -EFSCORRUPTED
;
1198 /* start copy indexes */
1199 m
= EXT_MAX_INDEX(path
[i
].p_hdr
) - path
[i
].p_idx
++;
1200 ext_debug("cur 0x%p, last 0x%p\n", path
[i
].p_idx
,
1201 EXT_MAX_INDEX(path
[i
].p_hdr
));
1202 ext4_ext_show_move(inode
, path
, newblock
, i
);
1204 memmove(++fidx
, path
[i
].p_idx
,
1205 sizeof(struct ext4_extent_idx
) * m
);
1206 le16_add_cpu(&neh
->eh_entries
, m
);
1208 ext4_extent_block_csum_set(inode
, neh
);
1209 set_buffer_uptodate(bh
);
1212 err
= ext4_handle_dirty_metadata(handle
, inode
, bh
);
1218 /* correct old index */
1220 err
= ext4_ext_get_access(handle
, inode
, path
+ i
);
1223 le16_add_cpu(&path
[i
].p_hdr
->eh_entries
, -m
);
1224 err
= ext4_ext_dirty(handle
, inode
, path
+ i
);
1232 /* insert new index */
1233 err
= ext4_ext_insert_index(handle
, inode
, path
+ at
,
1234 le32_to_cpu(border
), newblock
);
1238 if (buffer_locked(bh
))
1244 /* free all allocated blocks in error case */
1245 for (i
= 0; i
< depth
; i
++) {
1248 ext4_free_blocks(handle
, inode
, NULL
, ablocks
[i
], 1,
1249 EXT4_FREE_BLOCKS_METADATA
);
1258 * ext4_ext_grow_indepth:
1259 * implements tree growing procedure:
1260 * - allocates new block
1261 * - moves top-level data (index block or leaf) into the new block
1262 * - initializes new top-level, creating index that points to the
1263 * just created block
1265 static int ext4_ext_grow_indepth(handle_t
*handle
, struct inode
*inode
,
1268 struct ext4_extent_header
*neh
;
1269 struct buffer_head
*bh
;
1270 ext4_fsblk_t newblock
, goal
= 0;
1271 struct ext4_super_block
*es
= EXT4_SB(inode
->i_sb
)->s_es
;
1274 /* Try to prepend new index to old one */
1275 if (ext_depth(inode
))
1276 goal
= ext4_idx_pblock(EXT_FIRST_INDEX(ext_inode_hdr(inode
)));
1277 if (goal
> le32_to_cpu(es
->s_first_data_block
)) {
1278 flags
|= EXT4_MB_HINT_TRY_GOAL
;
1281 goal
= ext4_inode_to_goal_block(inode
);
1282 newblock
= ext4_new_meta_blocks(handle
, inode
, goal
, flags
,
1287 bh
= sb_getblk_gfp(inode
->i_sb
, newblock
, __GFP_MOVABLE
| GFP_NOFS
);
1292 err
= ext4_journal_get_create_access(handle
, bh
);
1298 /* move top-level index/leaf into new block */
1299 memmove(bh
->b_data
, EXT4_I(inode
)->i_data
,
1300 sizeof(EXT4_I(inode
)->i_data
));
1302 /* set size of new block */
1303 neh
= ext_block_hdr(bh
);
1304 /* old root could have indexes or leaves
1305 * so calculate e_max right way */
1306 if (ext_depth(inode
))
1307 neh
->eh_max
= cpu_to_le16(ext4_ext_space_block_idx(inode
, 0));
1309 neh
->eh_max
= cpu_to_le16(ext4_ext_space_block(inode
, 0));
1310 neh
->eh_magic
= EXT4_EXT_MAGIC
;
1311 ext4_extent_block_csum_set(inode
, neh
);
1312 set_buffer_uptodate(bh
);
1315 err
= ext4_handle_dirty_metadata(handle
, inode
, bh
);
1319 /* Update top-level index: num,max,pointer */
1320 neh
= ext_inode_hdr(inode
);
1321 neh
->eh_entries
= cpu_to_le16(1);
1322 ext4_idx_store_pblock(EXT_FIRST_INDEX(neh
), newblock
);
1323 if (neh
->eh_depth
== 0) {
1324 /* Root extent block becomes index block */
1325 neh
->eh_max
= cpu_to_le16(ext4_ext_space_root_idx(inode
, 0));
1326 EXT_FIRST_INDEX(neh
)->ei_block
=
1327 EXT_FIRST_EXTENT(neh
)->ee_block
;
1329 ext_debug("new root: num %d(%d), lblock %d, ptr %llu\n",
1330 le16_to_cpu(neh
->eh_entries
), le16_to_cpu(neh
->eh_max
),
1331 le32_to_cpu(EXT_FIRST_INDEX(neh
)->ei_block
),
1332 ext4_idx_pblock(EXT_FIRST_INDEX(neh
)));
1334 le16_add_cpu(&neh
->eh_depth
, 1);
1335 ext4_mark_inode_dirty(handle
, inode
);
1343 * ext4_ext_create_new_leaf:
1344 * finds empty index and adds new leaf.
1345 * if no free index is found, then it requests in-depth growing.
1347 static int ext4_ext_create_new_leaf(handle_t
*handle
, struct inode
*inode
,
1348 unsigned int mb_flags
,
1349 unsigned int gb_flags
,
1350 struct ext4_ext_path
**ppath
,
1351 struct ext4_extent
*newext
)
1353 struct ext4_ext_path
*path
= *ppath
;
1354 struct ext4_ext_path
*curp
;
1355 int depth
, i
, err
= 0;
1358 i
= depth
= ext_depth(inode
);
1360 /* walk up to the tree and look for free index entry */
1361 curp
= path
+ depth
;
1362 while (i
> 0 && !EXT_HAS_FREE_INDEX(curp
)) {
1367 /* we use already allocated block for index block,
1368 * so subsequent data blocks should be contiguous */
1369 if (EXT_HAS_FREE_INDEX(curp
)) {
1370 /* if we found index with free entry, then use that
1371 * entry: create all needed subtree and add new leaf */
1372 err
= ext4_ext_split(handle
, inode
, mb_flags
, path
, newext
, i
);
1377 path
= ext4_find_extent(inode
,
1378 (ext4_lblk_t
)le32_to_cpu(newext
->ee_block
),
1381 err
= PTR_ERR(path
);
1383 /* tree is full, time to grow in depth */
1384 err
= ext4_ext_grow_indepth(handle
, inode
, mb_flags
);
1389 path
= ext4_find_extent(inode
,
1390 (ext4_lblk_t
)le32_to_cpu(newext
->ee_block
),
1393 err
= PTR_ERR(path
);
1398 * only first (depth 0 -> 1) produces free space;
1399 * in all other cases we have to split the grown tree
1401 depth
= ext_depth(inode
);
1402 if (path
[depth
].p_hdr
->eh_entries
== path
[depth
].p_hdr
->eh_max
) {
1403 /* now we need to split */
1413 * search the closest allocated block to the left for *logical
1414 * and returns it at @logical + it's physical address at @phys
1415 * if *logical is the smallest allocated block, the function
1416 * returns 0 at @phys
1417 * return value contains 0 (success) or error code
1419 static int ext4_ext_search_left(struct inode
*inode
,
1420 struct ext4_ext_path
*path
,
1421 ext4_lblk_t
*logical
, ext4_fsblk_t
*phys
)
1423 struct ext4_extent_idx
*ix
;
1424 struct ext4_extent
*ex
;
1427 if (unlikely(path
== NULL
)) {
1428 EXT4_ERROR_INODE(inode
, "path == NULL *logical %d!", *logical
);
1429 return -EFSCORRUPTED
;
1431 depth
= path
->p_depth
;
1434 if (depth
== 0 && path
->p_ext
== NULL
)
1437 /* usually extent in the path covers blocks smaller
1438 * then *logical, but it can be that extent is the
1439 * first one in the file */
1441 ex
= path
[depth
].p_ext
;
1442 ee_len
= ext4_ext_get_actual_len(ex
);
1443 if (*logical
< le32_to_cpu(ex
->ee_block
)) {
1444 if (unlikely(EXT_FIRST_EXTENT(path
[depth
].p_hdr
) != ex
)) {
1445 EXT4_ERROR_INODE(inode
,
1446 "EXT_FIRST_EXTENT != ex *logical %d ee_block %d!",
1447 *logical
, le32_to_cpu(ex
->ee_block
));
1448 return -EFSCORRUPTED
;
1450 while (--depth
>= 0) {
1451 ix
= path
[depth
].p_idx
;
1452 if (unlikely(ix
!= EXT_FIRST_INDEX(path
[depth
].p_hdr
))) {
1453 EXT4_ERROR_INODE(inode
,
1454 "ix (%d) != EXT_FIRST_INDEX (%d) (depth %d)!",
1455 ix
!= NULL
? le32_to_cpu(ix
->ei_block
) : 0,
1456 EXT_FIRST_INDEX(path
[depth
].p_hdr
) != NULL
?
1457 le32_to_cpu(EXT_FIRST_INDEX(path
[depth
].p_hdr
)->ei_block
) : 0,
1459 return -EFSCORRUPTED
;
1465 if (unlikely(*logical
< (le32_to_cpu(ex
->ee_block
) + ee_len
))) {
1466 EXT4_ERROR_INODE(inode
,
1467 "logical %d < ee_block %d + ee_len %d!",
1468 *logical
, le32_to_cpu(ex
->ee_block
), ee_len
);
1469 return -EFSCORRUPTED
;
1472 *logical
= le32_to_cpu(ex
->ee_block
) + ee_len
- 1;
1473 *phys
= ext4_ext_pblock(ex
) + ee_len
- 1;
1478 * search the closest allocated block to the right for *logical
1479 * and returns it at @logical + it's physical address at @phys
1480 * if *logical is the largest allocated block, the function
1481 * returns 0 at @phys
1482 * return value contains 0 (success) or error code
1484 static int ext4_ext_search_right(struct inode
*inode
,
1485 struct ext4_ext_path
*path
,
1486 ext4_lblk_t
*logical
, ext4_fsblk_t
*phys
,
1487 struct ext4_extent
**ret_ex
)
1489 struct buffer_head
*bh
= NULL
;
1490 struct ext4_extent_header
*eh
;
1491 struct ext4_extent_idx
*ix
;
1492 struct ext4_extent
*ex
;
1494 int depth
; /* Note, NOT eh_depth; depth from top of tree */
1497 if (unlikely(path
== NULL
)) {
1498 EXT4_ERROR_INODE(inode
, "path == NULL *logical %d!", *logical
);
1499 return -EFSCORRUPTED
;
1501 depth
= path
->p_depth
;
1504 if (depth
== 0 && path
->p_ext
== NULL
)
1507 /* usually extent in the path covers blocks smaller
1508 * then *logical, but it can be that extent is the
1509 * first one in the file */
1511 ex
= path
[depth
].p_ext
;
1512 ee_len
= ext4_ext_get_actual_len(ex
);
1513 if (*logical
< le32_to_cpu(ex
->ee_block
)) {
1514 if (unlikely(EXT_FIRST_EXTENT(path
[depth
].p_hdr
) != ex
)) {
1515 EXT4_ERROR_INODE(inode
,
1516 "first_extent(path[%d].p_hdr) != ex",
1518 return -EFSCORRUPTED
;
1520 while (--depth
>= 0) {
1521 ix
= path
[depth
].p_idx
;
1522 if (unlikely(ix
!= EXT_FIRST_INDEX(path
[depth
].p_hdr
))) {
1523 EXT4_ERROR_INODE(inode
,
1524 "ix != EXT_FIRST_INDEX *logical %d!",
1526 return -EFSCORRUPTED
;
1532 if (unlikely(*logical
< (le32_to_cpu(ex
->ee_block
) + ee_len
))) {
1533 EXT4_ERROR_INODE(inode
,
1534 "logical %d < ee_block %d + ee_len %d!",
1535 *logical
, le32_to_cpu(ex
->ee_block
), ee_len
);
1536 return -EFSCORRUPTED
;
1539 if (ex
!= EXT_LAST_EXTENT(path
[depth
].p_hdr
)) {
1540 /* next allocated block in this leaf */
1545 /* go up and search for index to the right */
1546 while (--depth
>= 0) {
1547 ix
= path
[depth
].p_idx
;
1548 if (ix
!= EXT_LAST_INDEX(path
[depth
].p_hdr
))
1552 /* we've gone up to the root and found no index to the right */
1556 /* we've found index to the right, let's
1557 * follow it and find the closest allocated
1558 * block to the right */
1560 block
= ext4_idx_pblock(ix
);
1561 while (++depth
< path
->p_depth
) {
1562 /* subtract from p_depth to get proper eh_depth */
1563 bh
= read_extent_tree_block(inode
, block
,
1564 path
->p_depth
- depth
, 0);
1567 eh
= ext_block_hdr(bh
);
1568 ix
= EXT_FIRST_INDEX(eh
);
1569 block
= ext4_idx_pblock(ix
);
1573 bh
= read_extent_tree_block(inode
, block
, path
->p_depth
- depth
, 0);
1576 eh
= ext_block_hdr(bh
);
1577 ex
= EXT_FIRST_EXTENT(eh
);
1579 *logical
= le32_to_cpu(ex
->ee_block
);
1580 *phys
= ext4_ext_pblock(ex
);
1588 * ext4_ext_next_allocated_block:
1589 * returns allocated block in subsequent extent or EXT_MAX_BLOCKS.
1590 * NOTE: it considers block number from index entry as
1591 * allocated block. Thus, index entries have to be consistent
1595 ext4_ext_next_allocated_block(struct ext4_ext_path
*path
)
1599 BUG_ON(path
== NULL
);
1600 depth
= path
->p_depth
;
1602 if (depth
== 0 && path
->p_ext
== NULL
)
1603 return EXT_MAX_BLOCKS
;
1605 while (depth
>= 0) {
1606 if (depth
== path
->p_depth
) {
1608 if (path
[depth
].p_ext
&&
1609 path
[depth
].p_ext
!=
1610 EXT_LAST_EXTENT(path
[depth
].p_hdr
))
1611 return le32_to_cpu(path
[depth
].p_ext
[1].ee_block
);
1614 if (path
[depth
].p_idx
!=
1615 EXT_LAST_INDEX(path
[depth
].p_hdr
))
1616 return le32_to_cpu(path
[depth
].p_idx
[1].ei_block
);
1621 return EXT_MAX_BLOCKS
;
1625 * ext4_ext_next_leaf_block:
1626 * returns first allocated block from next leaf or EXT_MAX_BLOCKS
1628 static ext4_lblk_t
ext4_ext_next_leaf_block(struct ext4_ext_path
*path
)
1632 BUG_ON(path
== NULL
);
1633 depth
= path
->p_depth
;
1635 /* zero-tree has no leaf blocks at all */
1637 return EXT_MAX_BLOCKS
;
1639 /* go to index block */
1642 while (depth
>= 0) {
1643 if (path
[depth
].p_idx
!=
1644 EXT_LAST_INDEX(path
[depth
].p_hdr
))
1645 return (ext4_lblk_t
)
1646 le32_to_cpu(path
[depth
].p_idx
[1].ei_block
);
1650 return EXT_MAX_BLOCKS
;
1654 * ext4_ext_correct_indexes:
1655 * if leaf gets modified and modified extent is first in the leaf,
1656 * then we have to correct all indexes above.
1657 * TODO: do we need to correct tree in all cases?
1659 static int ext4_ext_correct_indexes(handle_t
*handle
, struct inode
*inode
,
1660 struct ext4_ext_path
*path
)
1662 struct ext4_extent_header
*eh
;
1663 int depth
= ext_depth(inode
);
1664 struct ext4_extent
*ex
;
1668 eh
= path
[depth
].p_hdr
;
1669 ex
= path
[depth
].p_ext
;
1671 if (unlikely(ex
== NULL
|| eh
== NULL
)) {
1672 EXT4_ERROR_INODE(inode
,
1673 "ex %p == NULL or eh %p == NULL", ex
, eh
);
1674 return -EFSCORRUPTED
;
1678 /* there is no tree at all */
1682 if (ex
!= EXT_FIRST_EXTENT(eh
)) {
1683 /* we correct tree if first leaf got modified only */
1688 * TODO: we need correction if border is smaller than current one
1691 border
= path
[depth
].p_ext
->ee_block
;
1692 err
= ext4_ext_get_access(handle
, inode
, path
+ k
);
1695 path
[k
].p_idx
->ei_block
= border
;
1696 err
= ext4_ext_dirty(handle
, inode
, path
+ k
);
1701 /* change all left-side indexes */
1702 if (path
[k
+1].p_idx
!= EXT_FIRST_INDEX(path
[k
+1].p_hdr
))
1704 err
= ext4_ext_get_access(handle
, inode
, path
+ k
);
1707 path
[k
].p_idx
->ei_block
= border
;
1708 err
= ext4_ext_dirty(handle
, inode
, path
+ k
);
1717 ext4_can_extents_be_merged(struct inode
*inode
, struct ext4_extent
*ex1
,
1718 struct ext4_extent
*ex2
)
1720 unsigned short ext1_ee_len
, ext2_ee_len
;
1722 if (ext4_ext_is_unwritten(ex1
) != ext4_ext_is_unwritten(ex2
))
1725 ext1_ee_len
= ext4_ext_get_actual_len(ex1
);
1726 ext2_ee_len
= ext4_ext_get_actual_len(ex2
);
1728 if (le32_to_cpu(ex1
->ee_block
) + ext1_ee_len
!=
1729 le32_to_cpu(ex2
->ee_block
))
1733 * To allow future support for preallocated extents to be added
1734 * as an RO_COMPAT feature, refuse to merge to extents if
1735 * this can result in the top bit of ee_len being set.
1737 if (ext1_ee_len
+ ext2_ee_len
> EXT_INIT_MAX_LEN
)
1740 * The check for IO to unwritten extent is somewhat racy as we
1741 * increment i_unwritten / set EXT4_STATE_DIO_UNWRITTEN only after
1742 * dropping i_data_sem. But reserved blocks should save us in that
1745 if (ext4_ext_is_unwritten(ex1
) &&
1746 (ext4_test_inode_state(inode
, EXT4_STATE_DIO_UNWRITTEN
) ||
1747 atomic_read(&EXT4_I(inode
)->i_unwritten
) ||
1748 (ext1_ee_len
+ ext2_ee_len
> EXT_UNWRITTEN_MAX_LEN
)))
1750 #ifdef AGGRESSIVE_TEST
1751 if (ext1_ee_len
>= 4)
1755 if (ext4_ext_pblock(ex1
) + ext1_ee_len
== ext4_ext_pblock(ex2
))
1761 * This function tries to merge the "ex" extent to the next extent in the tree.
1762 * It always tries to merge towards right. If you want to merge towards
1763 * left, pass "ex - 1" as argument instead of "ex".
1764 * Returns 0 if the extents (ex and ex+1) were _not_ merged and returns
1765 * 1 if they got merged.
1767 static int ext4_ext_try_to_merge_right(struct inode
*inode
,
1768 struct ext4_ext_path
*path
,
1769 struct ext4_extent
*ex
)
1771 struct ext4_extent_header
*eh
;
1772 unsigned int depth
, len
;
1773 int merge_done
= 0, unwritten
;
1775 depth
= ext_depth(inode
);
1776 BUG_ON(path
[depth
].p_hdr
== NULL
);
1777 eh
= path
[depth
].p_hdr
;
1779 while (ex
< EXT_LAST_EXTENT(eh
)) {
1780 if (!ext4_can_extents_be_merged(inode
, ex
, ex
+ 1))
1782 /* merge with next extent! */
1783 unwritten
= ext4_ext_is_unwritten(ex
);
1784 ex
->ee_len
= cpu_to_le16(ext4_ext_get_actual_len(ex
)
1785 + ext4_ext_get_actual_len(ex
+ 1));
1787 ext4_ext_mark_unwritten(ex
);
1789 if (ex
+ 1 < EXT_LAST_EXTENT(eh
)) {
1790 len
= (EXT_LAST_EXTENT(eh
) - ex
- 1)
1791 * sizeof(struct ext4_extent
);
1792 memmove(ex
+ 1, ex
+ 2, len
);
1794 le16_add_cpu(&eh
->eh_entries
, -1);
1796 WARN_ON(eh
->eh_entries
== 0);
1797 if (!eh
->eh_entries
)
1798 EXT4_ERROR_INODE(inode
, "eh->eh_entries = 0!");
1805 * This function does a very simple check to see if we can collapse
1806 * an extent tree with a single extent tree leaf block into the inode.
1808 static void ext4_ext_try_to_merge_up(handle_t
*handle
,
1809 struct inode
*inode
,
1810 struct ext4_ext_path
*path
)
1813 unsigned max_root
= ext4_ext_space_root(inode
, 0);
1816 if ((path
[0].p_depth
!= 1) ||
1817 (le16_to_cpu(path
[0].p_hdr
->eh_entries
) != 1) ||
1818 (le16_to_cpu(path
[1].p_hdr
->eh_entries
) > max_root
))
1822 * We need to modify the block allocation bitmap and the block
1823 * group descriptor to release the extent tree block. If we
1824 * can't get the journal credits, give up.
1826 if (ext4_journal_extend(handle
, 2))
1830 * Copy the extent data up to the inode
1832 blk
= ext4_idx_pblock(path
[0].p_idx
);
1833 s
= le16_to_cpu(path
[1].p_hdr
->eh_entries
) *
1834 sizeof(struct ext4_extent_idx
);
1835 s
+= sizeof(struct ext4_extent_header
);
1837 path
[1].p_maxdepth
= path
[0].p_maxdepth
;
1838 memcpy(path
[0].p_hdr
, path
[1].p_hdr
, s
);
1839 path
[0].p_depth
= 0;
1840 path
[0].p_ext
= EXT_FIRST_EXTENT(path
[0].p_hdr
) +
1841 (path
[1].p_ext
- EXT_FIRST_EXTENT(path
[1].p_hdr
));
1842 path
[0].p_hdr
->eh_max
= cpu_to_le16(max_root
);
1844 brelse(path
[1].p_bh
);
1845 ext4_free_blocks(handle
, inode
, NULL
, blk
, 1,
1846 EXT4_FREE_BLOCKS_METADATA
| EXT4_FREE_BLOCKS_FORGET
);
1850 * This function tries to merge the @ex extent to neighbours in the tree.
1851 * return 1 if merge left else 0.
1853 static void ext4_ext_try_to_merge(handle_t
*handle
,
1854 struct inode
*inode
,
1855 struct ext4_ext_path
*path
,
1856 struct ext4_extent
*ex
) {
1857 struct ext4_extent_header
*eh
;
1861 depth
= ext_depth(inode
);
1862 BUG_ON(path
[depth
].p_hdr
== NULL
);
1863 eh
= path
[depth
].p_hdr
;
1865 if (ex
> EXT_FIRST_EXTENT(eh
))
1866 merge_done
= ext4_ext_try_to_merge_right(inode
, path
, ex
- 1);
1869 (void) ext4_ext_try_to_merge_right(inode
, path
, ex
);
1871 ext4_ext_try_to_merge_up(handle
, inode
, path
);
1875 * check if a portion of the "newext" extent overlaps with an
1878 * If there is an overlap discovered, it updates the length of the newext
1879 * such that there will be no overlap, and then returns 1.
1880 * If there is no overlap found, it returns 0.
1882 static unsigned int ext4_ext_check_overlap(struct ext4_sb_info
*sbi
,
1883 struct inode
*inode
,
1884 struct ext4_extent
*newext
,
1885 struct ext4_ext_path
*path
)
1888 unsigned int depth
, len1
;
1889 unsigned int ret
= 0;
1891 b1
= le32_to_cpu(newext
->ee_block
);
1892 len1
= ext4_ext_get_actual_len(newext
);
1893 depth
= ext_depth(inode
);
1894 if (!path
[depth
].p_ext
)
1896 b2
= EXT4_LBLK_CMASK(sbi
, le32_to_cpu(path
[depth
].p_ext
->ee_block
));
1899 * get the next allocated block if the extent in the path
1900 * is before the requested block(s)
1903 b2
= ext4_ext_next_allocated_block(path
);
1904 if (b2
== EXT_MAX_BLOCKS
)
1906 b2
= EXT4_LBLK_CMASK(sbi
, b2
);
1909 /* check for wrap through zero on extent logical start block*/
1910 if (b1
+ len1
< b1
) {
1911 len1
= EXT_MAX_BLOCKS
- b1
;
1912 newext
->ee_len
= cpu_to_le16(len1
);
1916 /* check for overlap */
1917 if (b1
+ len1
> b2
) {
1918 newext
->ee_len
= cpu_to_le16(b2
- b1
);
1926 * ext4_ext_insert_extent:
1927 * tries to merge requsted extent into the existing extent or
1928 * inserts requested extent as new one into the tree,
1929 * creating new leaf in the no-space case.
1931 int ext4_ext_insert_extent(handle_t
*handle
, struct inode
*inode
,
1932 struct ext4_ext_path
**ppath
,
1933 struct ext4_extent
*newext
, int gb_flags
)
1935 struct ext4_ext_path
*path
= *ppath
;
1936 struct ext4_extent_header
*eh
;
1937 struct ext4_extent
*ex
, *fex
;
1938 struct ext4_extent
*nearex
; /* nearest extent */
1939 struct ext4_ext_path
*npath
= NULL
;
1940 int depth
, len
, err
;
1942 int mb_flags
= 0, unwritten
;
1944 if (gb_flags
& EXT4_GET_BLOCKS_DELALLOC_RESERVE
)
1945 mb_flags
|= EXT4_MB_DELALLOC_RESERVED
;
1946 if (unlikely(ext4_ext_get_actual_len(newext
) == 0)) {
1947 EXT4_ERROR_INODE(inode
, "ext4_ext_get_actual_len(newext) == 0");
1948 return -EFSCORRUPTED
;
1950 depth
= ext_depth(inode
);
1951 ex
= path
[depth
].p_ext
;
1952 eh
= path
[depth
].p_hdr
;
1953 if (unlikely(path
[depth
].p_hdr
== NULL
)) {
1954 EXT4_ERROR_INODE(inode
, "path[%d].p_hdr == NULL", depth
);
1955 return -EFSCORRUPTED
;
1958 /* try to insert block into found extent and return */
1959 if (ex
&& !(gb_flags
& EXT4_GET_BLOCKS_PRE_IO
)) {
1962 * Try to see whether we should rather test the extent on
1963 * right from ex, or from the left of ex. This is because
1964 * ext4_find_extent() can return either extent on the
1965 * left, or on the right from the searched position. This
1966 * will make merging more effective.
1968 if (ex
< EXT_LAST_EXTENT(eh
) &&
1969 (le32_to_cpu(ex
->ee_block
) +
1970 ext4_ext_get_actual_len(ex
) <
1971 le32_to_cpu(newext
->ee_block
))) {
1974 } else if ((ex
> EXT_FIRST_EXTENT(eh
)) &&
1975 (le32_to_cpu(newext
->ee_block
) +
1976 ext4_ext_get_actual_len(newext
) <
1977 le32_to_cpu(ex
->ee_block
)))
1980 /* Try to append newex to the ex */
1981 if (ext4_can_extents_be_merged(inode
, ex
, newext
)) {
1982 ext_debug("append [%d]%d block to %u:[%d]%d"
1984 ext4_ext_is_unwritten(newext
),
1985 ext4_ext_get_actual_len(newext
),
1986 le32_to_cpu(ex
->ee_block
),
1987 ext4_ext_is_unwritten(ex
),
1988 ext4_ext_get_actual_len(ex
),
1989 ext4_ext_pblock(ex
));
1990 err
= ext4_ext_get_access(handle
, inode
,
1994 unwritten
= ext4_ext_is_unwritten(ex
);
1995 ex
->ee_len
= cpu_to_le16(ext4_ext_get_actual_len(ex
)
1996 + ext4_ext_get_actual_len(newext
));
1998 ext4_ext_mark_unwritten(ex
);
1999 eh
= path
[depth
].p_hdr
;
2005 /* Try to prepend newex to the ex */
2006 if (ext4_can_extents_be_merged(inode
, newext
, ex
)) {
2007 ext_debug("prepend %u[%d]%d block to %u:[%d]%d"
2009 le32_to_cpu(newext
->ee_block
),
2010 ext4_ext_is_unwritten(newext
),
2011 ext4_ext_get_actual_len(newext
),
2012 le32_to_cpu(ex
->ee_block
),
2013 ext4_ext_is_unwritten(ex
),
2014 ext4_ext_get_actual_len(ex
),
2015 ext4_ext_pblock(ex
));
2016 err
= ext4_ext_get_access(handle
, inode
,
2021 unwritten
= ext4_ext_is_unwritten(ex
);
2022 ex
->ee_block
= newext
->ee_block
;
2023 ext4_ext_store_pblock(ex
, ext4_ext_pblock(newext
));
2024 ex
->ee_len
= cpu_to_le16(ext4_ext_get_actual_len(ex
)
2025 + ext4_ext_get_actual_len(newext
));
2027 ext4_ext_mark_unwritten(ex
);
2028 eh
= path
[depth
].p_hdr
;
2034 depth
= ext_depth(inode
);
2035 eh
= path
[depth
].p_hdr
;
2036 if (le16_to_cpu(eh
->eh_entries
) < le16_to_cpu(eh
->eh_max
))
2039 /* probably next leaf has space for us? */
2040 fex
= EXT_LAST_EXTENT(eh
);
2041 next
= EXT_MAX_BLOCKS
;
2042 if (le32_to_cpu(newext
->ee_block
) > le32_to_cpu(fex
->ee_block
))
2043 next
= ext4_ext_next_leaf_block(path
);
2044 if (next
!= EXT_MAX_BLOCKS
) {
2045 ext_debug("next leaf block - %u\n", next
);
2046 BUG_ON(npath
!= NULL
);
2047 npath
= ext4_find_extent(inode
, next
, NULL
, 0);
2049 return PTR_ERR(npath
);
2050 BUG_ON(npath
->p_depth
!= path
->p_depth
);
2051 eh
= npath
[depth
].p_hdr
;
2052 if (le16_to_cpu(eh
->eh_entries
) < le16_to_cpu(eh
->eh_max
)) {
2053 ext_debug("next leaf isn't full(%d)\n",
2054 le16_to_cpu(eh
->eh_entries
));
2058 ext_debug("next leaf has no free space(%d,%d)\n",
2059 le16_to_cpu(eh
->eh_entries
), le16_to_cpu(eh
->eh_max
));
2063 * There is no free space in the found leaf.
2064 * We're gonna add a new leaf in the tree.
2066 if (gb_flags
& EXT4_GET_BLOCKS_METADATA_NOFAIL
)
2067 mb_flags
|= EXT4_MB_USE_RESERVED
;
2068 err
= ext4_ext_create_new_leaf(handle
, inode
, mb_flags
, gb_flags
,
2072 depth
= ext_depth(inode
);
2073 eh
= path
[depth
].p_hdr
;
2076 nearex
= path
[depth
].p_ext
;
2078 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
2083 /* there is no extent in this leaf, create first one */
2084 ext_debug("first extent in the leaf: %u:%llu:[%d]%d\n",
2085 le32_to_cpu(newext
->ee_block
),
2086 ext4_ext_pblock(newext
),
2087 ext4_ext_is_unwritten(newext
),
2088 ext4_ext_get_actual_len(newext
));
2089 nearex
= EXT_FIRST_EXTENT(eh
);
2091 if (le32_to_cpu(newext
->ee_block
)
2092 > le32_to_cpu(nearex
->ee_block
)) {
2094 ext_debug("insert %u:%llu:[%d]%d before: "
2096 le32_to_cpu(newext
->ee_block
),
2097 ext4_ext_pblock(newext
),
2098 ext4_ext_is_unwritten(newext
),
2099 ext4_ext_get_actual_len(newext
),
2104 BUG_ON(newext
->ee_block
== nearex
->ee_block
);
2105 ext_debug("insert %u:%llu:[%d]%d after: "
2107 le32_to_cpu(newext
->ee_block
),
2108 ext4_ext_pblock(newext
),
2109 ext4_ext_is_unwritten(newext
),
2110 ext4_ext_get_actual_len(newext
),
2113 len
= EXT_LAST_EXTENT(eh
) - nearex
+ 1;
2115 ext_debug("insert %u:%llu:[%d]%d: "
2116 "move %d extents from 0x%p to 0x%p\n",
2117 le32_to_cpu(newext
->ee_block
),
2118 ext4_ext_pblock(newext
),
2119 ext4_ext_is_unwritten(newext
),
2120 ext4_ext_get_actual_len(newext
),
2121 len
, nearex
, nearex
+ 1);
2122 memmove(nearex
+ 1, nearex
,
2123 len
* sizeof(struct ext4_extent
));
2127 le16_add_cpu(&eh
->eh_entries
, 1);
2128 path
[depth
].p_ext
= nearex
;
2129 nearex
->ee_block
= newext
->ee_block
;
2130 ext4_ext_store_pblock(nearex
, ext4_ext_pblock(newext
));
2131 nearex
->ee_len
= newext
->ee_len
;
2134 /* try to merge extents */
2135 if (!(gb_flags
& EXT4_GET_BLOCKS_PRE_IO
))
2136 ext4_ext_try_to_merge(handle
, inode
, path
, nearex
);
2139 /* time to correct all indexes above */
2140 err
= ext4_ext_correct_indexes(handle
, inode
, path
);
2144 err
= ext4_ext_dirty(handle
, inode
, path
+ path
->p_depth
);
2147 ext4_ext_drop_refs(npath
);
2152 static int ext4_fill_fiemap_extents(struct inode
*inode
,
2153 ext4_lblk_t block
, ext4_lblk_t num
,
2154 struct fiemap_extent_info
*fieinfo
)
2156 struct ext4_ext_path
*path
= NULL
;
2157 struct ext4_extent
*ex
;
2158 struct extent_status es
;
2159 ext4_lblk_t next
, next_del
, start
= 0, end
= 0;
2160 ext4_lblk_t last
= block
+ num
;
2161 int exists
, depth
= 0, err
= 0;
2162 unsigned int flags
= 0;
2163 unsigned char blksize_bits
= inode
->i_sb
->s_blocksize_bits
;
2165 while (block
< last
&& block
!= EXT_MAX_BLOCKS
) {
2167 /* find extent for this block */
2168 down_read(&EXT4_I(inode
)->i_data_sem
);
2170 path
= ext4_find_extent(inode
, block
, &path
, 0);
2172 up_read(&EXT4_I(inode
)->i_data_sem
);
2173 err
= PTR_ERR(path
);
2178 depth
= ext_depth(inode
);
2179 if (unlikely(path
[depth
].p_hdr
== NULL
)) {
2180 up_read(&EXT4_I(inode
)->i_data_sem
);
2181 EXT4_ERROR_INODE(inode
, "path[%d].p_hdr == NULL", depth
);
2182 err
= -EFSCORRUPTED
;
2185 ex
= path
[depth
].p_ext
;
2186 next
= ext4_ext_next_allocated_block(path
);
2191 /* there is no extent yet, so try to allocate
2192 * all requested space */
2195 } else if (le32_to_cpu(ex
->ee_block
) > block
) {
2196 /* need to allocate space before found extent */
2198 end
= le32_to_cpu(ex
->ee_block
);
2199 if (block
+ num
< end
)
2201 } else if (block
>= le32_to_cpu(ex
->ee_block
)
2202 + ext4_ext_get_actual_len(ex
)) {
2203 /* need to allocate space after found extent */
2208 } else if (block
>= le32_to_cpu(ex
->ee_block
)) {
2210 * some part of requested space is covered
2214 end
= le32_to_cpu(ex
->ee_block
)
2215 + ext4_ext_get_actual_len(ex
);
2216 if (block
+ num
< end
)
2222 BUG_ON(end
<= start
);
2226 es
.es_len
= end
- start
;
2229 es
.es_lblk
= le32_to_cpu(ex
->ee_block
);
2230 es
.es_len
= ext4_ext_get_actual_len(ex
);
2231 es
.es_pblk
= ext4_ext_pblock(ex
);
2232 if (ext4_ext_is_unwritten(ex
))
2233 flags
|= FIEMAP_EXTENT_UNWRITTEN
;
2237 * Find delayed extent and update es accordingly. We call
2238 * it even in !exists case to find out whether es is the
2239 * last existing extent or not.
2241 next_del
= ext4_find_delayed_extent(inode
, &es
);
2242 if (!exists
&& next_del
) {
2244 flags
|= (FIEMAP_EXTENT_DELALLOC
|
2245 FIEMAP_EXTENT_UNKNOWN
);
2247 up_read(&EXT4_I(inode
)->i_data_sem
);
2249 if (unlikely(es
.es_len
== 0)) {
2250 EXT4_ERROR_INODE(inode
, "es.es_len == 0");
2251 err
= -EFSCORRUPTED
;
2256 * This is possible iff next == next_del == EXT_MAX_BLOCKS.
2257 * we need to check next == EXT_MAX_BLOCKS because it is
2258 * possible that an extent is with unwritten and delayed
2259 * status due to when an extent is delayed allocated and
2260 * is allocated by fallocate status tree will track both of
2263 * So we could return a unwritten and delayed extent, and
2264 * its block is equal to 'next'.
2266 if (next
== next_del
&& next
== EXT_MAX_BLOCKS
) {
2267 flags
|= FIEMAP_EXTENT_LAST
;
2268 if (unlikely(next_del
!= EXT_MAX_BLOCKS
||
2269 next
!= EXT_MAX_BLOCKS
)) {
2270 EXT4_ERROR_INODE(inode
,
2271 "next extent == %u, next "
2272 "delalloc extent = %u",
2274 err
= -EFSCORRUPTED
;
2280 err
= fiemap_fill_next_extent(fieinfo
,
2281 (__u64
)es
.es_lblk
<< blksize_bits
,
2282 (__u64
)es
.es_pblk
<< blksize_bits
,
2283 (__u64
)es
.es_len
<< blksize_bits
,
2293 block
= es
.es_lblk
+ es
.es_len
;
2296 ext4_ext_drop_refs(path
);
2302 * ext4_ext_determine_hole - determine hole around given block
2303 * @inode: inode we lookup in
2304 * @path: path in extent tree to @lblk
2305 * @lblk: pointer to logical block around which we want to determine hole
2307 * Determine hole length (and start if easily possible) around given logical
2308 * block. We don't try too hard to find the beginning of the hole but @path
2309 * actually points to extent before @lblk, we provide it.
2311 * The function returns the length of a hole starting at @lblk. We update @lblk
2312 * to the beginning of the hole if we managed to find it.
2314 static ext4_lblk_t
ext4_ext_determine_hole(struct inode
*inode
,
2315 struct ext4_ext_path
*path
,
2318 int depth
= ext_depth(inode
);
2319 struct ext4_extent
*ex
;
2322 ex
= path
[depth
].p_ext
;
2324 /* there is no extent yet, so gap is [0;-] */
2326 len
= EXT_MAX_BLOCKS
;
2327 } else if (*lblk
< le32_to_cpu(ex
->ee_block
)) {
2328 len
= le32_to_cpu(ex
->ee_block
) - *lblk
;
2329 } else if (*lblk
>= le32_to_cpu(ex
->ee_block
)
2330 + ext4_ext_get_actual_len(ex
)) {
2333 *lblk
= le32_to_cpu(ex
->ee_block
) + ext4_ext_get_actual_len(ex
);
2334 next
= ext4_ext_next_allocated_block(path
);
2335 BUG_ON(next
== *lblk
);
2344 * ext4_ext_put_gap_in_cache:
2345 * calculate boundaries of the gap that the requested block fits into
2346 * and cache this gap
2349 ext4_ext_put_gap_in_cache(struct inode
*inode
, ext4_lblk_t hole_start
,
2350 ext4_lblk_t hole_len
)
2352 struct extent_status es
;
2354 ext4_es_find_delayed_extent_range(inode
, hole_start
,
2355 hole_start
+ hole_len
- 1, &es
);
2357 /* There's delayed extent containing lblock? */
2358 if (es
.es_lblk
<= hole_start
)
2360 hole_len
= min(es
.es_lblk
- hole_start
, hole_len
);
2362 ext_debug(" -> %u:%u\n", hole_start
, hole_len
);
2363 ext4_es_insert_extent(inode
, hole_start
, hole_len
, ~0,
2364 EXTENT_STATUS_HOLE
);
2369 * removes index from the index block.
2371 static int ext4_ext_rm_idx(handle_t
*handle
, struct inode
*inode
,
2372 struct ext4_ext_path
*path
, int depth
)
2377 /* free index block */
2379 path
= path
+ depth
;
2380 leaf
= ext4_idx_pblock(path
->p_idx
);
2381 if (unlikely(path
->p_hdr
->eh_entries
== 0)) {
2382 EXT4_ERROR_INODE(inode
, "path->p_hdr->eh_entries == 0");
2383 return -EFSCORRUPTED
;
2385 err
= ext4_ext_get_access(handle
, inode
, path
);
2389 if (path
->p_idx
!= EXT_LAST_INDEX(path
->p_hdr
)) {
2390 int len
= EXT_LAST_INDEX(path
->p_hdr
) - path
->p_idx
;
2391 len
*= sizeof(struct ext4_extent_idx
);
2392 memmove(path
->p_idx
, path
->p_idx
+ 1, len
);
2395 le16_add_cpu(&path
->p_hdr
->eh_entries
, -1);
2396 err
= ext4_ext_dirty(handle
, inode
, path
);
2399 ext_debug("index is empty, remove it, free block %llu\n", leaf
);
2400 trace_ext4_ext_rm_idx(inode
, leaf
);
2402 ext4_free_blocks(handle
, inode
, NULL
, leaf
, 1,
2403 EXT4_FREE_BLOCKS_METADATA
| EXT4_FREE_BLOCKS_FORGET
);
2405 while (--depth
>= 0) {
2406 if (path
->p_idx
!= EXT_FIRST_INDEX(path
->p_hdr
))
2409 err
= ext4_ext_get_access(handle
, inode
, path
);
2412 path
->p_idx
->ei_block
= (path
+1)->p_idx
->ei_block
;
2413 err
= ext4_ext_dirty(handle
, inode
, path
);
2421 * ext4_ext_calc_credits_for_single_extent:
2422 * This routine returns max. credits that needed to insert an extent
2423 * to the extent tree.
2424 * When pass the actual path, the caller should calculate credits
2427 int ext4_ext_calc_credits_for_single_extent(struct inode
*inode
, int nrblocks
,
2428 struct ext4_ext_path
*path
)
2431 int depth
= ext_depth(inode
);
2434 /* probably there is space in leaf? */
2435 if (le16_to_cpu(path
[depth
].p_hdr
->eh_entries
)
2436 < le16_to_cpu(path
[depth
].p_hdr
->eh_max
)) {
2439 * There are some space in the leaf tree, no
2440 * need to account for leaf block credit
2442 * bitmaps and block group descriptor blocks
2443 * and other metadata blocks still need to be
2446 /* 1 bitmap, 1 block group descriptor */
2447 ret
= 2 + EXT4_META_TRANS_BLOCKS(inode
->i_sb
);
2452 return ext4_chunk_trans_blocks(inode
, nrblocks
);
2456 * How many index/leaf blocks need to change/allocate to add @extents extents?
2458 * If we add a single extent, then in the worse case, each tree level
2459 * index/leaf need to be changed in case of the tree split.
2461 * If more extents are inserted, they could cause the whole tree split more
2462 * than once, but this is really rare.
2464 int ext4_ext_index_trans_blocks(struct inode
*inode
, int extents
)
2469 /* If we are converting the inline data, only one is needed here. */
2470 if (ext4_has_inline_data(inode
))
2473 depth
= ext_depth(inode
);
2483 static inline int get_default_free_blocks_flags(struct inode
*inode
)
2485 if (S_ISDIR(inode
->i_mode
) || S_ISLNK(inode
->i_mode
) ||
2486 ext4_test_inode_flag(inode
, EXT4_INODE_EA_INODE
))
2487 return EXT4_FREE_BLOCKS_METADATA
| EXT4_FREE_BLOCKS_FORGET
;
2488 else if (ext4_should_journal_data(inode
))
2489 return EXT4_FREE_BLOCKS_FORGET
;
2493 static int ext4_remove_blocks(handle_t
*handle
, struct inode
*inode
,
2494 struct ext4_extent
*ex
,
2495 long long *partial_cluster
,
2496 ext4_lblk_t from
, ext4_lblk_t to
)
2498 struct ext4_sb_info
*sbi
= EXT4_SB(inode
->i_sb
);
2499 unsigned short ee_len
= ext4_ext_get_actual_len(ex
);
2501 int flags
= get_default_free_blocks_flags(inode
);
2504 * For bigalloc file systems, we never free a partial cluster
2505 * at the beginning of the extent. Instead, we make a note
2506 * that we tried freeing the cluster, and check to see if we
2507 * need to free it on a subsequent call to ext4_remove_blocks,
2508 * or at the end of ext4_ext_rm_leaf or ext4_ext_remove_space.
2510 flags
|= EXT4_FREE_BLOCKS_NOFREE_FIRST_CLUSTER
;
2512 trace_ext4_remove_blocks(inode
, ex
, from
, to
, *partial_cluster
);
2514 * If we have a partial cluster, and it's different from the
2515 * cluster of the last block, we need to explicitly free the
2516 * partial cluster here.
2518 pblk
= ext4_ext_pblock(ex
) + ee_len
- 1;
2519 if (*partial_cluster
> 0 &&
2520 *partial_cluster
!= (long long) EXT4_B2C(sbi
, pblk
)) {
2521 ext4_free_blocks(handle
, inode
, NULL
,
2522 EXT4_C2B(sbi
, *partial_cluster
),
2523 sbi
->s_cluster_ratio
, flags
);
2524 *partial_cluster
= 0;
2527 #ifdef EXTENTS_STATS
2529 struct ext4_sb_info
*sbi
= EXT4_SB(inode
->i_sb
);
2530 spin_lock(&sbi
->s_ext_stats_lock
);
2531 sbi
->s_ext_blocks
+= ee_len
;
2532 sbi
->s_ext_extents
++;
2533 if (ee_len
< sbi
->s_ext_min
)
2534 sbi
->s_ext_min
= ee_len
;
2535 if (ee_len
> sbi
->s_ext_max
)
2536 sbi
->s_ext_max
= ee_len
;
2537 if (ext_depth(inode
) > sbi
->s_depth_max
)
2538 sbi
->s_depth_max
= ext_depth(inode
);
2539 spin_unlock(&sbi
->s_ext_stats_lock
);
2542 if (from
>= le32_to_cpu(ex
->ee_block
)
2543 && to
== le32_to_cpu(ex
->ee_block
) + ee_len
- 1) {
2546 long long first_cluster
;
2548 num
= le32_to_cpu(ex
->ee_block
) + ee_len
- from
;
2549 pblk
= ext4_ext_pblock(ex
) + ee_len
- num
;
2551 * Usually we want to free partial cluster at the end of the
2552 * extent, except for the situation when the cluster is still
2553 * used by any other extent (partial_cluster is negative).
2555 if (*partial_cluster
< 0 &&
2556 *partial_cluster
== -(long long) EXT4_B2C(sbi
, pblk
+num
-1))
2557 flags
|= EXT4_FREE_BLOCKS_NOFREE_LAST_CLUSTER
;
2559 ext_debug("free last %u blocks starting %llu partial %lld\n",
2560 num
, pblk
, *partial_cluster
);
2561 ext4_free_blocks(handle
, inode
, NULL
, pblk
, num
, flags
);
2563 * If the block range to be freed didn't start at the
2564 * beginning of a cluster, and we removed the entire
2565 * extent and the cluster is not used by any other extent,
2566 * save the partial cluster here, since we might need to
2567 * delete if we determine that the truncate or punch hole
2568 * operation has removed all of the blocks in the cluster.
2569 * If that cluster is used by another extent, preserve its
2570 * negative value so it isn't freed later on.
2572 * If the whole extent wasn't freed, we've reached the
2573 * start of the truncated/punched region and have finished
2574 * removing blocks. If there's a partial cluster here it's
2575 * shared with the remainder of the extent and is no longer
2576 * a candidate for removal.
2578 if (EXT4_PBLK_COFF(sbi
, pblk
) && ee_len
== num
) {
2579 first_cluster
= (long long) EXT4_B2C(sbi
, pblk
);
2580 if (first_cluster
!= -*partial_cluster
)
2581 *partial_cluster
= first_cluster
;
2583 *partial_cluster
= 0;
2586 ext4_error(sbi
->s_sb
, "strange request: removal(2) "
2588 from
, to
, le32_to_cpu(ex
->ee_block
), ee_len
);
2594 * ext4_ext_rm_leaf() Removes the extents associated with the
2595 * blocks appearing between "start" and "end". Both "start"
2596 * and "end" must appear in the same extent or EIO is returned.
2598 * @handle: The journal handle
2599 * @inode: The files inode
2600 * @path: The path to the leaf
2601 * @partial_cluster: The cluster which we'll have to free if all extents
2602 * has been released from it. However, if this value is
2603 * negative, it's a cluster just to the right of the
2604 * punched region and it must not be freed.
2605 * @start: The first block to remove
2606 * @end: The last block to remove
2609 ext4_ext_rm_leaf(handle_t
*handle
, struct inode
*inode
,
2610 struct ext4_ext_path
*path
,
2611 long long *partial_cluster
,
2612 ext4_lblk_t start
, ext4_lblk_t end
)
2614 struct ext4_sb_info
*sbi
= EXT4_SB(inode
->i_sb
);
2615 int err
= 0, correct_index
= 0;
2616 int depth
= ext_depth(inode
), credits
;
2617 struct ext4_extent_header
*eh
;
2620 ext4_lblk_t ex_ee_block
;
2621 unsigned short ex_ee_len
;
2622 unsigned unwritten
= 0;
2623 struct ext4_extent
*ex
;
2626 /* the header must be checked already in ext4_ext_remove_space() */
2627 ext_debug("truncate since %u in leaf to %u\n", start
, end
);
2628 if (!path
[depth
].p_hdr
)
2629 path
[depth
].p_hdr
= ext_block_hdr(path
[depth
].p_bh
);
2630 eh
= path
[depth
].p_hdr
;
2631 if (unlikely(path
[depth
].p_hdr
== NULL
)) {
2632 EXT4_ERROR_INODE(inode
, "path[%d].p_hdr == NULL", depth
);
2633 return -EFSCORRUPTED
;
2635 /* find where to start removing */
2636 ex
= path
[depth
].p_ext
;
2638 ex
= EXT_LAST_EXTENT(eh
);
2640 ex_ee_block
= le32_to_cpu(ex
->ee_block
);
2641 ex_ee_len
= ext4_ext_get_actual_len(ex
);
2643 trace_ext4_ext_rm_leaf(inode
, start
, ex
, *partial_cluster
);
2645 while (ex
>= EXT_FIRST_EXTENT(eh
) &&
2646 ex_ee_block
+ ex_ee_len
> start
) {
2648 if (ext4_ext_is_unwritten(ex
))
2653 ext_debug("remove ext %u:[%d]%d\n", ex_ee_block
,
2654 unwritten
, ex_ee_len
);
2655 path
[depth
].p_ext
= ex
;
2657 a
= ex_ee_block
> start
? ex_ee_block
: start
;
2658 b
= ex_ee_block
+ex_ee_len
- 1 < end
?
2659 ex_ee_block
+ex_ee_len
- 1 : end
;
2661 ext_debug(" border %u:%u\n", a
, b
);
2663 /* If this extent is beyond the end of the hole, skip it */
2664 if (end
< ex_ee_block
) {
2666 * We're going to skip this extent and move to another,
2667 * so note that its first cluster is in use to avoid
2668 * freeing it when removing blocks. Eventually, the
2669 * right edge of the truncated/punched region will
2670 * be just to the left.
2672 if (sbi
->s_cluster_ratio
> 1) {
2673 pblk
= ext4_ext_pblock(ex
);
2675 -(long long) EXT4_B2C(sbi
, pblk
);
2678 ex_ee_block
= le32_to_cpu(ex
->ee_block
);
2679 ex_ee_len
= ext4_ext_get_actual_len(ex
);
2681 } else if (b
!= ex_ee_block
+ ex_ee_len
- 1) {
2682 EXT4_ERROR_INODE(inode
,
2683 "can not handle truncate %u:%u "
2685 start
, end
, ex_ee_block
,
2686 ex_ee_block
+ ex_ee_len
- 1);
2687 err
= -EFSCORRUPTED
;
2689 } else if (a
!= ex_ee_block
) {
2690 /* remove tail of the extent */
2691 num
= a
- ex_ee_block
;
2693 /* remove whole extent: excellent! */
2697 * 3 for leaf, sb, and inode plus 2 (bmap and group
2698 * descriptor) for each block group; assume two block
2699 * groups plus ex_ee_len/blocks_per_block_group for
2702 credits
= 7 + 2*(ex_ee_len
/EXT4_BLOCKS_PER_GROUP(inode
->i_sb
));
2703 if (ex
== EXT_FIRST_EXTENT(eh
)) {
2705 credits
+= (ext_depth(inode
)) + 1;
2707 credits
+= EXT4_MAXQUOTAS_TRANS_BLOCKS(inode
->i_sb
);
2709 err
= ext4_ext_truncate_extend_restart(handle
, inode
, credits
);
2713 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
2717 err
= ext4_remove_blocks(handle
, inode
, ex
, partial_cluster
,
2723 /* this extent is removed; mark slot entirely unused */
2724 ext4_ext_store_pblock(ex
, 0);
2726 ex
->ee_len
= cpu_to_le16(num
);
2728 * Do not mark unwritten if all the blocks in the
2729 * extent have been removed.
2731 if (unwritten
&& num
)
2732 ext4_ext_mark_unwritten(ex
);
2734 * If the extent was completely released,
2735 * we need to remove it from the leaf
2738 if (end
!= EXT_MAX_BLOCKS
- 1) {
2740 * For hole punching, we need to scoot all the
2741 * extents up when an extent is removed so that
2742 * we dont have blank extents in the middle
2744 memmove(ex
, ex
+1, (EXT_LAST_EXTENT(eh
) - ex
) *
2745 sizeof(struct ext4_extent
));
2747 /* Now get rid of the one at the end */
2748 memset(EXT_LAST_EXTENT(eh
), 0,
2749 sizeof(struct ext4_extent
));
2751 le16_add_cpu(&eh
->eh_entries
, -1);
2754 err
= ext4_ext_dirty(handle
, inode
, path
+ depth
);
2758 ext_debug("new extent: %u:%u:%llu\n", ex_ee_block
, num
,
2759 ext4_ext_pblock(ex
));
2761 ex_ee_block
= le32_to_cpu(ex
->ee_block
);
2762 ex_ee_len
= ext4_ext_get_actual_len(ex
);
2765 if (correct_index
&& eh
->eh_entries
)
2766 err
= ext4_ext_correct_indexes(handle
, inode
, path
);
2769 * If there's a partial cluster and at least one extent remains in
2770 * the leaf, free the partial cluster if it isn't shared with the
2771 * current extent. If it is shared with the current extent
2772 * we zero partial_cluster because we've reached the start of the
2773 * truncated/punched region and we're done removing blocks.
2775 if (*partial_cluster
> 0 && ex
>= EXT_FIRST_EXTENT(eh
)) {
2776 pblk
= ext4_ext_pblock(ex
) + ex_ee_len
- 1;
2777 if (*partial_cluster
!= (long long) EXT4_B2C(sbi
, pblk
)) {
2778 ext4_free_blocks(handle
, inode
, NULL
,
2779 EXT4_C2B(sbi
, *partial_cluster
),
2780 sbi
->s_cluster_ratio
,
2781 get_default_free_blocks_flags(inode
));
2783 *partial_cluster
= 0;
2786 /* if this leaf is free, then we should
2787 * remove it from index block above */
2788 if (err
== 0 && eh
->eh_entries
== 0 && path
[depth
].p_bh
!= NULL
)
2789 err
= ext4_ext_rm_idx(handle
, inode
, path
, depth
);
2796 * ext4_ext_more_to_rm:
2797 * returns 1 if current index has to be freed (even partial)
2800 ext4_ext_more_to_rm(struct ext4_ext_path
*path
)
2802 BUG_ON(path
->p_idx
== NULL
);
2804 if (path
->p_idx
< EXT_FIRST_INDEX(path
->p_hdr
))
2808 * if truncate on deeper level happened, it wasn't partial,
2809 * so we have to consider current index for truncation
2811 if (le16_to_cpu(path
->p_hdr
->eh_entries
) == path
->p_block
)
2816 int ext4_ext_remove_space(struct inode
*inode
, ext4_lblk_t start
,
2819 struct ext4_sb_info
*sbi
= EXT4_SB(inode
->i_sb
);
2820 int depth
= ext_depth(inode
);
2821 struct ext4_ext_path
*path
= NULL
;
2822 long long partial_cluster
= 0;
2826 ext_debug("truncate since %u to %u\n", start
, end
);
2828 /* probably first extent we're gonna free will be last in block */
2829 handle
= ext4_journal_start(inode
, EXT4_HT_TRUNCATE
, depth
+ 1);
2831 return PTR_ERR(handle
);
2834 trace_ext4_ext_remove_space(inode
, start
, end
, depth
);
2837 * Check if we are removing extents inside the extent tree. If that
2838 * is the case, we are going to punch a hole inside the extent tree
2839 * so we have to check whether we need to split the extent covering
2840 * the last block to remove so we can easily remove the part of it
2841 * in ext4_ext_rm_leaf().
2843 if (end
< EXT_MAX_BLOCKS
- 1) {
2844 struct ext4_extent
*ex
;
2845 ext4_lblk_t ee_block
, ex_end
, lblk
;
2848 /* find extent for or closest extent to this block */
2849 path
= ext4_find_extent(inode
, end
, NULL
, EXT4_EX_NOCACHE
);
2851 ext4_journal_stop(handle
);
2852 return PTR_ERR(path
);
2854 depth
= ext_depth(inode
);
2855 /* Leaf not may not exist only if inode has no blocks at all */
2856 ex
= path
[depth
].p_ext
;
2859 EXT4_ERROR_INODE(inode
,
2860 "path[%d].p_hdr == NULL",
2862 err
= -EFSCORRUPTED
;
2867 ee_block
= le32_to_cpu(ex
->ee_block
);
2868 ex_end
= ee_block
+ ext4_ext_get_actual_len(ex
) - 1;
2871 * See if the last block is inside the extent, if so split
2872 * the extent at 'end' block so we can easily remove the
2873 * tail of the first part of the split extent in
2874 * ext4_ext_rm_leaf().
2876 if (end
>= ee_block
&& end
< ex_end
) {
2879 * If we're going to split the extent, note that
2880 * the cluster containing the block after 'end' is
2881 * in use to avoid freeing it when removing blocks.
2883 if (sbi
->s_cluster_ratio
> 1) {
2884 pblk
= ext4_ext_pblock(ex
) + end
- ee_block
+ 2;
2886 -(long long) EXT4_B2C(sbi
, pblk
);
2890 * Split the extent in two so that 'end' is the last
2891 * block in the first new extent. Also we should not
2892 * fail removing space due to ENOSPC so try to use
2893 * reserved block if that happens.
2895 err
= ext4_force_split_extent_at(handle
, inode
, &path
,
2900 } else if (sbi
->s_cluster_ratio
> 1 && end
>= ex_end
) {
2902 * If there's an extent to the right its first cluster
2903 * contains the immediate right boundary of the
2904 * truncated/punched region. Set partial_cluster to
2905 * its negative value so it won't be freed if shared
2906 * with the current extent. The end < ee_block case
2907 * is handled in ext4_ext_rm_leaf().
2910 err
= ext4_ext_search_right(inode
, path
, &lblk
, &pblk
,
2916 -(long long) EXT4_B2C(sbi
, pblk
);
2920 * We start scanning from right side, freeing all the blocks
2921 * after i_size and walking into the tree depth-wise.
2923 depth
= ext_depth(inode
);
2928 le16_to_cpu(path
[k
].p_hdr
->eh_entries
)+1;
2930 path
= kcalloc(depth
+ 1, sizeof(struct ext4_ext_path
),
2933 ext4_journal_stop(handle
);
2936 path
[0].p_maxdepth
= path
[0].p_depth
= depth
;
2937 path
[0].p_hdr
= ext_inode_hdr(inode
);
2940 if (ext4_ext_check(inode
, path
[0].p_hdr
, depth
, 0)) {
2941 err
= -EFSCORRUPTED
;
2947 while (i
>= 0 && err
== 0) {
2949 /* this is leaf block */
2950 err
= ext4_ext_rm_leaf(handle
, inode
, path
,
2951 &partial_cluster
, start
,
2953 /* root level has p_bh == NULL, brelse() eats this */
2954 brelse(path
[i
].p_bh
);
2955 path
[i
].p_bh
= NULL
;
2960 /* this is index block */
2961 if (!path
[i
].p_hdr
) {
2962 ext_debug("initialize header\n");
2963 path
[i
].p_hdr
= ext_block_hdr(path
[i
].p_bh
);
2966 if (!path
[i
].p_idx
) {
2967 /* this level hasn't been touched yet */
2968 path
[i
].p_idx
= EXT_LAST_INDEX(path
[i
].p_hdr
);
2969 path
[i
].p_block
= le16_to_cpu(path
[i
].p_hdr
->eh_entries
)+1;
2970 ext_debug("init index ptr: hdr 0x%p, num %d\n",
2972 le16_to_cpu(path
[i
].p_hdr
->eh_entries
));
2974 /* we were already here, see at next index */
2978 ext_debug("level %d - index, first 0x%p, cur 0x%p\n",
2979 i
, EXT_FIRST_INDEX(path
[i
].p_hdr
),
2981 if (ext4_ext_more_to_rm(path
+ i
)) {
2982 struct buffer_head
*bh
;
2983 /* go to the next level */
2984 ext_debug("move to level %d (block %llu)\n",
2985 i
+ 1, ext4_idx_pblock(path
[i
].p_idx
));
2986 memset(path
+ i
+ 1, 0, sizeof(*path
));
2987 bh
= read_extent_tree_block(inode
,
2988 ext4_idx_pblock(path
[i
].p_idx
), depth
- i
- 1,
2991 /* should we reset i_size? */
2995 /* Yield here to deal with large extent trees.
2996 * Should be a no-op if we did IO above. */
2998 if (WARN_ON(i
+ 1 > depth
)) {
2999 err
= -EFSCORRUPTED
;
3002 path
[i
+ 1].p_bh
= bh
;
3004 /* save actual number of indexes since this
3005 * number is changed at the next iteration */
3006 path
[i
].p_block
= le16_to_cpu(path
[i
].p_hdr
->eh_entries
);
3009 /* we finished processing this index, go up */
3010 if (path
[i
].p_hdr
->eh_entries
== 0 && i
> 0) {
3011 /* index is empty, remove it;
3012 * handle must be already prepared by the
3013 * truncatei_leaf() */
3014 err
= ext4_ext_rm_idx(handle
, inode
, path
, i
);
3016 /* root level has p_bh == NULL, brelse() eats this */
3017 brelse(path
[i
].p_bh
);
3018 path
[i
].p_bh
= NULL
;
3020 ext_debug("return to level %d\n", i
);
3024 trace_ext4_ext_remove_space_done(inode
, start
, end
, depth
,
3025 partial_cluster
, path
->p_hdr
->eh_entries
);
3028 * If we still have something in the partial cluster and we have removed
3029 * even the first extent, then we should free the blocks in the partial
3030 * cluster as well. (This code will only run when there are no leaves
3031 * to the immediate left of the truncated/punched region.)
3033 if (partial_cluster
> 0 && err
== 0) {
3034 /* don't zero partial_cluster since it's not used afterwards */
3035 ext4_free_blocks(handle
, inode
, NULL
,
3036 EXT4_C2B(sbi
, partial_cluster
),
3037 sbi
->s_cluster_ratio
,
3038 get_default_free_blocks_flags(inode
));
3041 /* TODO: flexible tree reduction should be here */
3042 if (path
->p_hdr
->eh_entries
== 0) {
3044 * truncate to zero freed all the tree,
3045 * so we need to correct eh_depth
3047 err
= ext4_ext_get_access(handle
, inode
, path
);
3049 ext_inode_hdr(inode
)->eh_depth
= 0;
3050 ext_inode_hdr(inode
)->eh_max
=
3051 cpu_to_le16(ext4_ext_space_root(inode
, 0));
3052 err
= ext4_ext_dirty(handle
, inode
, path
);
3056 ext4_ext_drop_refs(path
);
3061 ext4_journal_stop(handle
);
3067 * called at mount time
3069 void ext4_ext_init(struct super_block
*sb
)
3072 * possible initialization would be here
3075 if (ext4_has_feature_extents(sb
)) {
3076 #if defined(AGGRESSIVE_TEST) || defined(CHECK_BINSEARCH) || defined(EXTENTS_STATS)
3077 printk(KERN_INFO
"EXT4-fs: file extents enabled"
3078 #ifdef AGGRESSIVE_TEST
3079 ", aggressive tests"
3081 #ifdef CHECK_BINSEARCH
3084 #ifdef EXTENTS_STATS
3089 #ifdef EXTENTS_STATS
3090 spin_lock_init(&EXT4_SB(sb
)->s_ext_stats_lock
);
3091 EXT4_SB(sb
)->s_ext_min
= 1 << 30;
3092 EXT4_SB(sb
)->s_ext_max
= 0;
3098 * called at umount time
3100 void ext4_ext_release(struct super_block
*sb
)
3102 if (!ext4_has_feature_extents(sb
))
3105 #ifdef EXTENTS_STATS
3106 if (EXT4_SB(sb
)->s_ext_blocks
&& EXT4_SB(sb
)->s_ext_extents
) {
3107 struct ext4_sb_info
*sbi
= EXT4_SB(sb
);
3108 printk(KERN_ERR
"EXT4-fs: %lu blocks in %lu extents (%lu ave)\n",
3109 sbi
->s_ext_blocks
, sbi
->s_ext_extents
,
3110 sbi
->s_ext_blocks
/ sbi
->s_ext_extents
);
3111 printk(KERN_ERR
"EXT4-fs: extents: %lu min, %lu max, max depth %lu\n",
3112 sbi
->s_ext_min
, sbi
->s_ext_max
, sbi
->s_depth_max
);
3117 static int ext4_zeroout_es(struct inode
*inode
, struct ext4_extent
*ex
)
3119 ext4_lblk_t ee_block
;
3120 ext4_fsblk_t ee_pblock
;
3121 unsigned int ee_len
;
3123 ee_block
= le32_to_cpu(ex
->ee_block
);
3124 ee_len
= ext4_ext_get_actual_len(ex
);
3125 ee_pblock
= ext4_ext_pblock(ex
);
3130 return ext4_es_insert_extent(inode
, ee_block
, ee_len
, ee_pblock
,
3131 EXTENT_STATUS_WRITTEN
);
3134 /* FIXME!! we need to try to merge to left or right after zero-out */
3135 static int ext4_ext_zeroout(struct inode
*inode
, struct ext4_extent
*ex
)
3137 ext4_fsblk_t ee_pblock
;
3138 unsigned int ee_len
;
3140 ee_len
= ext4_ext_get_actual_len(ex
);
3141 ee_pblock
= ext4_ext_pblock(ex
);
3142 return ext4_issue_zeroout(inode
, le32_to_cpu(ex
->ee_block
), ee_pblock
,
3147 * ext4_split_extent_at() splits an extent at given block.
3149 * @handle: the journal handle
3150 * @inode: the file inode
3151 * @path: the path to the extent
3152 * @split: the logical block where the extent is splitted.
3153 * @split_flags: indicates if the extent could be zeroout if split fails, and
3154 * the states(init or unwritten) of new extents.
3155 * @flags: flags used to insert new extent to extent tree.
3158 * Splits extent [a, b] into two extents [a, @split) and [@split, b], states
3159 * of which are deterimined by split_flag.
3161 * There are two cases:
3162 * a> the extent are splitted into two extent.
3163 * b> split is not needed, and just mark the extent.
3165 * return 0 on success.
3167 static int ext4_split_extent_at(handle_t
*handle
,
3168 struct inode
*inode
,
3169 struct ext4_ext_path
**ppath
,
3174 struct ext4_ext_path
*path
= *ppath
;
3175 ext4_fsblk_t newblock
;
3176 ext4_lblk_t ee_block
;
3177 struct ext4_extent
*ex
, newex
, orig_ex
, zero_ex
;
3178 struct ext4_extent
*ex2
= NULL
;
3179 unsigned int ee_len
, depth
;
3182 BUG_ON((split_flag
& (EXT4_EXT_DATA_VALID1
| EXT4_EXT_DATA_VALID2
)) ==
3183 (EXT4_EXT_DATA_VALID1
| EXT4_EXT_DATA_VALID2
));
3185 ext_debug("ext4_split_extents_at: inode %lu, logical"
3186 "block %llu\n", inode
->i_ino
, (unsigned long long)split
);
3188 ext4_ext_show_leaf(inode
, path
);
3190 depth
= ext_depth(inode
);
3191 ex
= path
[depth
].p_ext
;
3192 ee_block
= le32_to_cpu(ex
->ee_block
);
3193 ee_len
= ext4_ext_get_actual_len(ex
);
3194 newblock
= split
- ee_block
+ ext4_ext_pblock(ex
);
3196 BUG_ON(split
< ee_block
|| split
>= (ee_block
+ ee_len
));
3197 BUG_ON(!ext4_ext_is_unwritten(ex
) &&
3198 split_flag
& (EXT4_EXT_MAY_ZEROOUT
|
3199 EXT4_EXT_MARK_UNWRIT1
|
3200 EXT4_EXT_MARK_UNWRIT2
));
3202 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
3206 if (split
== ee_block
) {
3208 * case b: block @split is the block that the extent begins with
3209 * then we just change the state of the extent, and splitting
3212 if (split_flag
& EXT4_EXT_MARK_UNWRIT2
)
3213 ext4_ext_mark_unwritten(ex
);
3215 ext4_ext_mark_initialized(ex
);
3217 if (!(flags
& EXT4_GET_BLOCKS_PRE_IO
))
3218 ext4_ext_try_to_merge(handle
, inode
, path
, ex
);
3220 err
= ext4_ext_dirty(handle
, inode
, path
+ path
->p_depth
);
3225 memcpy(&orig_ex
, ex
, sizeof(orig_ex
));
3226 ex
->ee_len
= cpu_to_le16(split
- ee_block
);
3227 if (split_flag
& EXT4_EXT_MARK_UNWRIT1
)
3228 ext4_ext_mark_unwritten(ex
);
3231 * path may lead to new leaf, not to original leaf any more
3232 * after ext4_ext_insert_extent() returns,
3234 err
= ext4_ext_dirty(handle
, inode
, path
+ depth
);
3236 goto fix_extent_len
;
3239 ex2
->ee_block
= cpu_to_le32(split
);
3240 ex2
->ee_len
= cpu_to_le16(ee_len
- (split
- ee_block
));
3241 ext4_ext_store_pblock(ex2
, newblock
);
3242 if (split_flag
& EXT4_EXT_MARK_UNWRIT2
)
3243 ext4_ext_mark_unwritten(ex2
);
3245 err
= ext4_ext_insert_extent(handle
, inode
, ppath
, &newex
, flags
);
3246 if (err
== -ENOSPC
&& (EXT4_EXT_MAY_ZEROOUT
& split_flag
)) {
3247 if (split_flag
& (EXT4_EXT_DATA_VALID1
|EXT4_EXT_DATA_VALID2
)) {
3248 if (split_flag
& EXT4_EXT_DATA_VALID1
) {
3249 err
= ext4_ext_zeroout(inode
, ex2
);
3250 zero_ex
.ee_block
= ex2
->ee_block
;
3251 zero_ex
.ee_len
= cpu_to_le16(
3252 ext4_ext_get_actual_len(ex2
));
3253 ext4_ext_store_pblock(&zero_ex
,
3254 ext4_ext_pblock(ex2
));
3256 err
= ext4_ext_zeroout(inode
, ex
);
3257 zero_ex
.ee_block
= ex
->ee_block
;
3258 zero_ex
.ee_len
= cpu_to_le16(
3259 ext4_ext_get_actual_len(ex
));
3260 ext4_ext_store_pblock(&zero_ex
,
3261 ext4_ext_pblock(ex
));
3264 err
= ext4_ext_zeroout(inode
, &orig_ex
);
3265 zero_ex
.ee_block
= orig_ex
.ee_block
;
3266 zero_ex
.ee_len
= cpu_to_le16(
3267 ext4_ext_get_actual_len(&orig_ex
));
3268 ext4_ext_store_pblock(&zero_ex
,
3269 ext4_ext_pblock(&orig_ex
));
3273 goto fix_extent_len
;
3274 /* update the extent length and mark as initialized */
3275 ex
->ee_len
= cpu_to_le16(ee_len
);
3276 ext4_ext_try_to_merge(handle
, inode
, path
, ex
);
3277 err
= ext4_ext_dirty(handle
, inode
, path
+ path
->p_depth
);
3279 goto fix_extent_len
;
3281 /* update extent status tree */
3282 err
= ext4_zeroout_es(inode
, &zero_ex
);
3286 goto fix_extent_len
;
3289 ext4_ext_show_leaf(inode
, path
);
3293 ex
->ee_len
= orig_ex
.ee_len
;
3294 ext4_ext_dirty(handle
, inode
, path
+ path
->p_depth
);
3299 * ext4_split_extents() splits an extent and mark extent which is covered
3300 * by @map as split_flags indicates
3302 * It may result in splitting the extent into multiple extents (up to three)
3303 * There are three possibilities:
3304 * a> There is no split required
3305 * b> Splits in two extents: Split is happening at either end of the extent
3306 * c> Splits in three extents: Somone is splitting in middle of the extent
3309 static int ext4_split_extent(handle_t
*handle
,
3310 struct inode
*inode
,
3311 struct ext4_ext_path
**ppath
,
3312 struct ext4_map_blocks
*map
,
3316 struct ext4_ext_path
*path
= *ppath
;
3317 ext4_lblk_t ee_block
;
3318 struct ext4_extent
*ex
;
3319 unsigned int ee_len
, depth
;
3322 int split_flag1
, flags1
;
3323 int allocated
= map
->m_len
;
3325 depth
= ext_depth(inode
);
3326 ex
= path
[depth
].p_ext
;
3327 ee_block
= le32_to_cpu(ex
->ee_block
);
3328 ee_len
= ext4_ext_get_actual_len(ex
);
3329 unwritten
= ext4_ext_is_unwritten(ex
);
3331 if (map
->m_lblk
+ map
->m_len
< ee_block
+ ee_len
) {
3332 split_flag1
= split_flag
& EXT4_EXT_MAY_ZEROOUT
;
3333 flags1
= flags
| EXT4_GET_BLOCKS_PRE_IO
;
3335 split_flag1
|= EXT4_EXT_MARK_UNWRIT1
|
3336 EXT4_EXT_MARK_UNWRIT2
;
3337 if (split_flag
& EXT4_EXT_DATA_VALID2
)
3338 split_flag1
|= EXT4_EXT_DATA_VALID1
;
3339 err
= ext4_split_extent_at(handle
, inode
, ppath
,
3340 map
->m_lblk
+ map
->m_len
, split_flag1
, flags1
);
3344 allocated
= ee_len
- (map
->m_lblk
- ee_block
);
3347 * Update path is required because previous ext4_split_extent_at() may
3348 * result in split of original leaf or extent zeroout.
3350 path
= ext4_find_extent(inode
, map
->m_lblk
, ppath
, 0);
3352 return PTR_ERR(path
);
3353 depth
= ext_depth(inode
);
3354 ex
= path
[depth
].p_ext
;
3356 EXT4_ERROR_INODE(inode
, "unexpected hole at %lu",
3357 (unsigned long) map
->m_lblk
);
3358 return -EFSCORRUPTED
;
3360 unwritten
= ext4_ext_is_unwritten(ex
);
3363 if (map
->m_lblk
>= ee_block
) {
3364 split_flag1
= split_flag
& EXT4_EXT_DATA_VALID2
;
3366 split_flag1
|= EXT4_EXT_MARK_UNWRIT1
;
3367 split_flag1
|= split_flag
& (EXT4_EXT_MAY_ZEROOUT
|
3368 EXT4_EXT_MARK_UNWRIT2
);
3370 err
= ext4_split_extent_at(handle
, inode
, ppath
,
3371 map
->m_lblk
, split_flag1
, flags
);
3376 ext4_ext_show_leaf(inode
, path
);
3378 return err
? err
: allocated
;
3382 * This function is called by ext4_ext_map_blocks() if someone tries to write
3383 * to an unwritten extent. It may result in splitting the unwritten
3384 * extent into multiple extents (up to three - one initialized and two
3386 * There are three possibilities:
3387 * a> There is no split required: Entire extent should be initialized
3388 * b> Splits in two extents: Write is happening at either end of the extent
3389 * c> Splits in three extents: Somone is writing in middle of the extent
3392 * - The extent pointed to by 'path' is unwritten.
3393 * - The extent pointed to by 'path' contains a superset
3394 * of the logical span [map->m_lblk, map->m_lblk + map->m_len).
3396 * Post-conditions on success:
3397 * - the returned value is the number of blocks beyond map->l_lblk
3398 * that are allocated and initialized.
3399 * It is guaranteed to be >= map->m_len.
3401 static int ext4_ext_convert_to_initialized(handle_t
*handle
,
3402 struct inode
*inode
,
3403 struct ext4_map_blocks
*map
,
3404 struct ext4_ext_path
**ppath
,
3407 struct ext4_ext_path
*path
= *ppath
;
3408 struct ext4_sb_info
*sbi
;
3409 struct ext4_extent_header
*eh
;
3410 struct ext4_map_blocks split_map
;
3411 struct ext4_extent zero_ex1
, zero_ex2
;
3412 struct ext4_extent
*ex
, *abut_ex
;
3413 ext4_lblk_t ee_block
, eof_block
;
3414 unsigned int ee_len
, depth
, map_len
= map
->m_len
;
3415 int allocated
= 0, max_zeroout
= 0;
3417 int split_flag
= EXT4_EXT_DATA_VALID2
;
3419 ext_debug("ext4_ext_convert_to_initialized: inode %lu, logical"
3420 "block %llu, max_blocks %u\n", inode
->i_ino
,
3421 (unsigned long long)map
->m_lblk
, map_len
);
3423 sbi
= EXT4_SB(inode
->i_sb
);
3424 eof_block
= (inode
->i_size
+ inode
->i_sb
->s_blocksize
- 1) >>
3425 inode
->i_sb
->s_blocksize_bits
;
3426 if (eof_block
< map
->m_lblk
+ map_len
)
3427 eof_block
= map
->m_lblk
+ map_len
;
3429 depth
= ext_depth(inode
);
3430 eh
= path
[depth
].p_hdr
;
3431 ex
= path
[depth
].p_ext
;
3432 ee_block
= le32_to_cpu(ex
->ee_block
);
3433 ee_len
= ext4_ext_get_actual_len(ex
);
3434 zero_ex1
.ee_len
= 0;
3435 zero_ex2
.ee_len
= 0;
3437 trace_ext4_ext_convert_to_initialized_enter(inode
, map
, ex
);
3439 /* Pre-conditions */
3440 BUG_ON(!ext4_ext_is_unwritten(ex
));
3441 BUG_ON(!in_range(map
->m_lblk
, ee_block
, ee_len
));
3444 * Attempt to transfer newly initialized blocks from the currently
3445 * unwritten extent to its neighbor. This is much cheaper
3446 * than an insertion followed by a merge as those involve costly
3447 * memmove() calls. Transferring to the left is the common case in
3448 * steady state for workloads doing fallocate(FALLOC_FL_KEEP_SIZE)
3449 * followed by append writes.
3451 * Limitations of the current logic:
3452 * - L1: we do not deal with writes covering the whole extent.
3453 * This would require removing the extent if the transfer
3455 * - L2: we only attempt to merge with an extent stored in the
3456 * same extent tree node.
3458 if ((map
->m_lblk
== ee_block
) &&
3459 /* See if we can merge left */
3460 (map_len
< ee_len
) && /*L1*/
3461 (ex
> EXT_FIRST_EXTENT(eh
))) { /*L2*/
3462 ext4_lblk_t prev_lblk
;
3463 ext4_fsblk_t prev_pblk
, ee_pblk
;
3464 unsigned int prev_len
;
3467 prev_lblk
= le32_to_cpu(abut_ex
->ee_block
);
3468 prev_len
= ext4_ext_get_actual_len(abut_ex
);
3469 prev_pblk
= ext4_ext_pblock(abut_ex
);
3470 ee_pblk
= ext4_ext_pblock(ex
);
3473 * A transfer of blocks from 'ex' to 'abut_ex' is allowed
3474 * upon those conditions:
3475 * - C1: abut_ex is initialized,
3476 * - C2: abut_ex is logically abutting ex,
3477 * - C3: abut_ex is physically abutting ex,
3478 * - C4: abut_ex can receive the additional blocks without
3479 * overflowing the (initialized) length limit.
3481 if ((!ext4_ext_is_unwritten(abut_ex
)) && /*C1*/
3482 ((prev_lblk
+ prev_len
) == ee_block
) && /*C2*/
3483 ((prev_pblk
+ prev_len
) == ee_pblk
) && /*C3*/
3484 (prev_len
< (EXT_INIT_MAX_LEN
- map_len
))) { /*C4*/
3485 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
3489 trace_ext4_ext_convert_to_initialized_fastpath(inode
,
3492 /* Shift the start of ex by 'map_len' blocks */
3493 ex
->ee_block
= cpu_to_le32(ee_block
+ map_len
);
3494 ext4_ext_store_pblock(ex
, ee_pblk
+ map_len
);
3495 ex
->ee_len
= cpu_to_le16(ee_len
- map_len
);
3496 ext4_ext_mark_unwritten(ex
); /* Restore the flag */
3498 /* Extend abut_ex by 'map_len' blocks */
3499 abut_ex
->ee_len
= cpu_to_le16(prev_len
+ map_len
);
3501 /* Result: number of initialized blocks past m_lblk */
3502 allocated
= map_len
;
3504 } else if (((map
->m_lblk
+ map_len
) == (ee_block
+ ee_len
)) &&
3505 (map_len
< ee_len
) && /*L1*/
3506 ex
< EXT_LAST_EXTENT(eh
)) { /*L2*/
3507 /* See if we can merge right */
3508 ext4_lblk_t next_lblk
;
3509 ext4_fsblk_t next_pblk
, ee_pblk
;
3510 unsigned int next_len
;
3513 next_lblk
= le32_to_cpu(abut_ex
->ee_block
);
3514 next_len
= ext4_ext_get_actual_len(abut_ex
);
3515 next_pblk
= ext4_ext_pblock(abut_ex
);
3516 ee_pblk
= ext4_ext_pblock(ex
);
3519 * A transfer of blocks from 'ex' to 'abut_ex' is allowed
3520 * upon those conditions:
3521 * - C1: abut_ex is initialized,
3522 * - C2: abut_ex is logically abutting ex,
3523 * - C3: abut_ex is physically abutting ex,
3524 * - C4: abut_ex can receive the additional blocks without
3525 * overflowing the (initialized) length limit.
3527 if ((!ext4_ext_is_unwritten(abut_ex
)) && /*C1*/
3528 ((map
->m_lblk
+ map_len
) == next_lblk
) && /*C2*/
3529 ((ee_pblk
+ ee_len
) == next_pblk
) && /*C3*/
3530 (next_len
< (EXT_INIT_MAX_LEN
- map_len
))) { /*C4*/
3531 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
3535 trace_ext4_ext_convert_to_initialized_fastpath(inode
,
3538 /* Shift the start of abut_ex by 'map_len' blocks */
3539 abut_ex
->ee_block
= cpu_to_le32(next_lblk
- map_len
);
3540 ext4_ext_store_pblock(abut_ex
, next_pblk
- map_len
);
3541 ex
->ee_len
= cpu_to_le16(ee_len
- map_len
);
3542 ext4_ext_mark_unwritten(ex
); /* Restore the flag */
3544 /* Extend abut_ex by 'map_len' blocks */
3545 abut_ex
->ee_len
= cpu_to_le16(next_len
+ map_len
);
3547 /* Result: number of initialized blocks past m_lblk */
3548 allocated
= map_len
;
3552 /* Mark the block containing both extents as dirty */
3553 ext4_ext_dirty(handle
, inode
, path
+ depth
);
3555 /* Update path to point to the right extent */
3556 path
[depth
].p_ext
= abut_ex
;
3559 allocated
= ee_len
- (map
->m_lblk
- ee_block
);
3561 WARN_ON(map
->m_lblk
< ee_block
);
3563 * It is safe to convert extent to initialized via explicit
3564 * zeroout only if extent is fully inside i_size or new_size.
3566 split_flag
|= ee_block
+ ee_len
<= eof_block
? EXT4_EXT_MAY_ZEROOUT
: 0;
3568 if (EXT4_EXT_MAY_ZEROOUT
& split_flag
)
3569 max_zeroout
= sbi
->s_extent_max_zeroout_kb
>>
3570 (inode
->i_sb
->s_blocksize_bits
- 10);
3572 if (ext4_encrypted_inode(inode
))
3577 * 1. split the extent into three extents.
3578 * 2. split the extent into two extents, zeroout the head of the first
3580 * 3. split the extent into two extents, zeroout the tail of the second
3582 * 4. split the extent into two extents with out zeroout.
3583 * 5. no splitting needed, just possibly zeroout the head and / or the
3584 * tail of the extent.
3586 split_map
.m_lblk
= map
->m_lblk
;
3587 split_map
.m_len
= map
->m_len
;
3589 if (max_zeroout
&& (allocated
> split_map
.m_len
)) {
3590 if (allocated
<= max_zeroout
) {
3593 cpu_to_le32(split_map
.m_lblk
+
3596 cpu_to_le16(allocated
- split_map
.m_len
);
3597 ext4_ext_store_pblock(&zero_ex1
,
3598 ext4_ext_pblock(ex
) + split_map
.m_lblk
+
3599 split_map
.m_len
- ee_block
);
3600 err
= ext4_ext_zeroout(inode
, &zero_ex1
);
3603 split_map
.m_len
= allocated
;
3605 if (split_map
.m_lblk
- ee_block
+ split_map
.m_len
<
3608 if (split_map
.m_lblk
!= ee_block
) {
3609 zero_ex2
.ee_block
= ex
->ee_block
;
3610 zero_ex2
.ee_len
= cpu_to_le16(split_map
.m_lblk
-
3612 ext4_ext_store_pblock(&zero_ex2
,
3613 ext4_ext_pblock(ex
));
3614 err
= ext4_ext_zeroout(inode
, &zero_ex2
);
3619 split_map
.m_len
+= split_map
.m_lblk
- ee_block
;
3620 split_map
.m_lblk
= ee_block
;
3621 allocated
= map
->m_len
;
3625 err
= ext4_split_extent(handle
, inode
, ppath
, &split_map
, split_flag
,
3630 /* If we have gotten a failure, don't zero out status tree */
3632 err
= ext4_zeroout_es(inode
, &zero_ex1
);
3634 err
= ext4_zeroout_es(inode
, &zero_ex2
);
3636 return err
? err
: allocated
;
3640 * This function is called by ext4_ext_map_blocks() from
3641 * ext4_get_blocks_dio_write() when DIO to write
3642 * to an unwritten extent.
3644 * Writing to an unwritten extent may result in splitting the unwritten
3645 * extent into multiple initialized/unwritten extents (up to three)
3646 * There are three possibilities:
3647 * a> There is no split required: Entire extent should be unwritten
3648 * b> Splits in two extents: Write is happening at either end of the extent
3649 * c> Splits in three extents: Somone is writing in middle of the extent
3651 * This works the same way in the case of initialized -> unwritten conversion.
3653 * One of more index blocks maybe needed if the extent tree grow after
3654 * the unwritten extent split. To prevent ENOSPC occur at the IO
3655 * complete, we need to split the unwritten extent before DIO submit
3656 * the IO. The unwritten extent called at this time will be split
3657 * into three unwritten extent(at most). After IO complete, the part
3658 * being filled will be convert to initialized by the end_io callback function
3659 * via ext4_convert_unwritten_extents().
3661 * Returns the size of unwritten extent to be written on success.
3663 static int ext4_split_convert_extents(handle_t
*handle
,
3664 struct inode
*inode
,
3665 struct ext4_map_blocks
*map
,
3666 struct ext4_ext_path
**ppath
,
3669 struct ext4_ext_path
*path
= *ppath
;
3670 ext4_lblk_t eof_block
;
3671 ext4_lblk_t ee_block
;
3672 struct ext4_extent
*ex
;
3673 unsigned int ee_len
;
3674 int split_flag
= 0, depth
;
3676 ext_debug("%s: inode %lu, logical block %llu, max_blocks %u\n",
3677 __func__
, inode
->i_ino
,
3678 (unsigned long long)map
->m_lblk
, map
->m_len
);
3680 eof_block
= (inode
->i_size
+ inode
->i_sb
->s_blocksize
- 1) >>
3681 inode
->i_sb
->s_blocksize_bits
;
3682 if (eof_block
< map
->m_lblk
+ map
->m_len
)
3683 eof_block
= map
->m_lblk
+ map
->m_len
;
3685 * It is safe to convert extent to initialized via explicit
3686 * zeroout only if extent is fully insde i_size or new_size.
3688 depth
= ext_depth(inode
);
3689 ex
= path
[depth
].p_ext
;
3690 ee_block
= le32_to_cpu(ex
->ee_block
);
3691 ee_len
= ext4_ext_get_actual_len(ex
);
3693 /* Convert to unwritten */
3694 if (flags
& EXT4_GET_BLOCKS_CONVERT_UNWRITTEN
) {
3695 split_flag
|= EXT4_EXT_DATA_VALID1
;
3696 /* Convert to initialized */
3697 } else if (flags
& EXT4_GET_BLOCKS_CONVERT
) {
3698 split_flag
|= ee_block
+ ee_len
<= eof_block
?
3699 EXT4_EXT_MAY_ZEROOUT
: 0;
3700 split_flag
|= (EXT4_EXT_MARK_UNWRIT2
| EXT4_EXT_DATA_VALID2
);
3702 flags
|= EXT4_GET_BLOCKS_PRE_IO
;
3703 return ext4_split_extent(handle
, inode
, ppath
, map
, split_flag
, flags
);
3706 static int ext4_convert_unwritten_extents_endio(handle_t
*handle
,
3707 struct inode
*inode
,
3708 struct ext4_map_blocks
*map
,
3709 struct ext4_ext_path
**ppath
)
3711 struct ext4_ext_path
*path
= *ppath
;
3712 struct ext4_extent
*ex
;
3713 ext4_lblk_t ee_block
;
3714 unsigned int ee_len
;
3718 depth
= ext_depth(inode
);
3719 ex
= path
[depth
].p_ext
;
3720 ee_block
= le32_to_cpu(ex
->ee_block
);
3721 ee_len
= ext4_ext_get_actual_len(ex
);
3723 ext_debug("ext4_convert_unwritten_extents_endio: inode %lu, logical"
3724 "block %llu, max_blocks %u\n", inode
->i_ino
,
3725 (unsigned long long)ee_block
, ee_len
);
3727 /* If extent is larger than requested it is a clear sign that we still
3728 * have some extent state machine issues left. So extent_split is still
3730 * TODO: Once all related issues will be fixed this situation should be
3733 if (ee_block
!= map
->m_lblk
|| ee_len
> map
->m_len
) {
3735 ext4_warning("Inode (%ld) finished: extent logical block %llu,"
3736 " len %u; IO logical block %llu, len %u",
3737 inode
->i_ino
, (unsigned long long)ee_block
, ee_len
,
3738 (unsigned long long)map
->m_lblk
, map
->m_len
);
3740 err
= ext4_split_convert_extents(handle
, inode
, map
, ppath
,
3741 EXT4_GET_BLOCKS_CONVERT
);
3744 path
= ext4_find_extent(inode
, map
->m_lblk
, ppath
, 0);
3746 return PTR_ERR(path
);
3747 depth
= ext_depth(inode
);
3748 ex
= path
[depth
].p_ext
;
3751 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
3754 /* first mark the extent as initialized */
3755 ext4_ext_mark_initialized(ex
);
3757 /* note: ext4_ext_correct_indexes() isn't needed here because
3758 * borders are not changed
3760 ext4_ext_try_to_merge(handle
, inode
, path
, ex
);
3762 /* Mark modified extent as dirty */
3763 err
= ext4_ext_dirty(handle
, inode
, path
+ path
->p_depth
);
3765 ext4_ext_show_leaf(inode
, path
);
3770 * Handle EOFBLOCKS_FL flag, clearing it if necessary
3772 static int check_eofblocks_fl(handle_t
*handle
, struct inode
*inode
,
3774 struct ext4_ext_path
*path
,
3778 struct ext4_extent_header
*eh
;
3779 struct ext4_extent
*last_ex
;
3781 if (!ext4_test_inode_flag(inode
, EXT4_INODE_EOFBLOCKS
))
3784 depth
= ext_depth(inode
);
3785 eh
= path
[depth
].p_hdr
;
3788 * We're going to remove EOFBLOCKS_FL entirely in future so we
3789 * do not care for this case anymore. Simply remove the flag
3790 * if there are no extents.
3792 if (unlikely(!eh
->eh_entries
))
3794 last_ex
= EXT_LAST_EXTENT(eh
);
3796 * We should clear the EOFBLOCKS_FL flag if we are writing the
3797 * last block in the last extent in the file. We test this by
3798 * first checking to see if the caller to
3799 * ext4_ext_get_blocks() was interested in the last block (or
3800 * a block beyond the last block) in the current extent. If
3801 * this turns out to be false, we can bail out from this
3802 * function immediately.
3804 if (lblk
+ len
< le32_to_cpu(last_ex
->ee_block
) +
3805 ext4_ext_get_actual_len(last_ex
))
3808 * If the caller does appear to be planning to write at or
3809 * beyond the end of the current extent, we then test to see
3810 * if the current extent is the last extent in the file, by
3811 * checking to make sure it was reached via the rightmost node
3812 * at each level of the tree.
3814 for (i
= depth
-1; i
>= 0; i
--)
3815 if (path
[i
].p_idx
!= EXT_LAST_INDEX(path
[i
].p_hdr
))
3818 ext4_clear_inode_flag(inode
, EXT4_INODE_EOFBLOCKS
);
3819 return ext4_mark_inode_dirty(handle
, inode
);
3823 * ext4_find_delalloc_range: find delayed allocated block in the given range.
3825 * Return 1 if there is a delalloc block in the range, otherwise 0.
3827 int ext4_find_delalloc_range(struct inode
*inode
,
3828 ext4_lblk_t lblk_start
,
3829 ext4_lblk_t lblk_end
)
3831 struct extent_status es
;
3833 ext4_es_find_delayed_extent_range(inode
, lblk_start
, lblk_end
, &es
);
3835 return 0; /* there is no delay extent in this tree */
3836 else if (es
.es_lblk
<= lblk_start
&&
3837 lblk_start
< es
.es_lblk
+ es
.es_len
)
3839 else if (lblk_start
<= es
.es_lblk
&& es
.es_lblk
<= lblk_end
)
3845 int ext4_find_delalloc_cluster(struct inode
*inode
, ext4_lblk_t lblk
)
3847 struct ext4_sb_info
*sbi
= EXT4_SB(inode
->i_sb
);
3848 ext4_lblk_t lblk_start
, lblk_end
;
3849 lblk_start
= EXT4_LBLK_CMASK(sbi
, lblk
);
3850 lblk_end
= lblk_start
+ sbi
->s_cluster_ratio
- 1;
3852 return ext4_find_delalloc_range(inode
, lblk_start
, lblk_end
);
3856 * Determines how many complete clusters (out of those specified by the 'map')
3857 * are under delalloc and were reserved quota for.
3858 * This function is called when we are writing out the blocks that were
3859 * originally written with their allocation delayed, but then the space was
3860 * allocated using fallocate() before the delayed allocation could be resolved.
3861 * The cases to look for are:
3862 * ('=' indicated delayed allocated blocks
3863 * '-' indicates non-delayed allocated blocks)
3864 * (a) partial clusters towards beginning and/or end outside of allocated range
3865 * are not delalloc'ed.
3867 * |----c---=|====c====|====c====|===-c----|
3868 * |++++++ allocated ++++++|
3869 * ==> 4 complete clusters in above example
3871 * (b) partial cluster (outside of allocated range) towards either end is
3872 * marked for delayed allocation. In this case, we will exclude that
3875 * |----====c========|========c========|
3876 * |++++++ allocated ++++++|
3877 * ==> 1 complete clusters in above example
3880 * |================c================|
3881 * |++++++ allocated ++++++|
3882 * ==> 0 complete clusters in above example
3884 * The ext4_da_update_reserve_space will be called only if we
3885 * determine here that there were some "entire" clusters that span
3886 * this 'allocated' range.
3887 * In the non-bigalloc case, this function will just end up returning num_blks
3888 * without ever calling ext4_find_delalloc_range.
3891 get_reserved_cluster_alloc(struct inode
*inode
, ext4_lblk_t lblk_start
,
3892 unsigned int num_blks
)
3894 struct ext4_sb_info
*sbi
= EXT4_SB(inode
->i_sb
);
3895 ext4_lblk_t alloc_cluster_start
, alloc_cluster_end
;
3896 ext4_lblk_t lblk_from
, lblk_to
, c_offset
;
3897 unsigned int allocated_clusters
= 0;
3899 alloc_cluster_start
= EXT4_B2C(sbi
, lblk_start
);
3900 alloc_cluster_end
= EXT4_B2C(sbi
, lblk_start
+ num_blks
- 1);
3902 /* max possible clusters for this allocation */
3903 allocated_clusters
= alloc_cluster_end
- alloc_cluster_start
+ 1;
3905 trace_ext4_get_reserved_cluster_alloc(inode
, lblk_start
, num_blks
);
3907 /* Check towards left side */
3908 c_offset
= EXT4_LBLK_COFF(sbi
, lblk_start
);
3910 lblk_from
= EXT4_LBLK_CMASK(sbi
, lblk_start
);
3911 lblk_to
= lblk_from
+ c_offset
- 1;
3913 if (ext4_find_delalloc_range(inode
, lblk_from
, lblk_to
))
3914 allocated_clusters
--;
3917 /* Now check towards right. */
3918 c_offset
= EXT4_LBLK_COFF(sbi
, lblk_start
+ num_blks
);
3919 if (allocated_clusters
&& c_offset
) {
3920 lblk_from
= lblk_start
+ num_blks
;
3921 lblk_to
= lblk_from
+ (sbi
->s_cluster_ratio
- c_offset
) - 1;
3923 if (ext4_find_delalloc_range(inode
, lblk_from
, lblk_to
))
3924 allocated_clusters
--;
3927 return allocated_clusters
;
3931 convert_initialized_extent(handle_t
*handle
, struct inode
*inode
,
3932 struct ext4_map_blocks
*map
,
3933 struct ext4_ext_path
**ppath
,
3934 unsigned int allocated
)
3936 struct ext4_ext_path
*path
= *ppath
;
3937 struct ext4_extent
*ex
;
3938 ext4_lblk_t ee_block
;
3939 unsigned int ee_len
;
3944 * Make sure that the extent is no bigger than we support with
3947 if (map
->m_len
> EXT_UNWRITTEN_MAX_LEN
)
3948 map
->m_len
= EXT_UNWRITTEN_MAX_LEN
/ 2;
3950 depth
= ext_depth(inode
);
3951 ex
= path
[depth
].p_ext
;
3952 ee_block
= le32_to_cpu(ex
->ee_block
);
3953 ee_len
= ext4_ext_get_actual_len(ex
);
3955 ext_debug("%s: inode %lu, logical"
3956 "block %llu, max_blocks %u\n", __func__
, inode
->i_ino
,
3957 (unsigned long long)ee_block
, ee_len
);
3959 if (ee_block
!= map
->m_lblk
|| ee_len
> map
->m_len
) {
3960 err
= ext4_split_convert_extents(handle
, inode
, map
, ppath
,
3961 EXT4_GET_BLOCKS_CONVERT_UNWRITTEN
);
3964 path
= ext4_find_extent(inode
, map
->m_lblk
, ppath
, 0);
3966 return PTR_ERR(path
);
3967 depth
= ext_depth(inode
);
3968 ex
= path
[depth
].p_ext
;
3970 EXT4_ERROR_INODE(inode
, "unexpected hole at %lu",
3971 (unsigned long) map
->m_lblk
);
3972 return -EFSCORRUPTED
;
3976 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
3979 /* first mark the extent as unwritten */
3980 ext4_ext_mark_unwritten(ex
);
3982 /* note: ext4_ext_correct_indexes() isn't needed here because
3983 * borders are not changed
3985 ext4_ext_try_to_merge(handle
, inode
, path
, ex
);
3987 /* Mark modified extent as dirty */
3988 err
= ext4_ext_dirty(handle
, inode
, path
+ path
->p_depth
);
3991 ext4_ext_show_leaf(inode
, path
);
3993 ext4_update_inode_fsync_trans(handle
, inode
, 1);
3994 err
= check_eofblocks_fl(handle
, inode
, map
->m_lblk
, path
, map
->m_len
);
3997 map
->m_flags
|= EXT4_MAP_UNWRITTEN
;
3998 if (allocated
> map
->m_len
)
3999 allocated
= map
->m_len
;
4000 map
->m_len
= allocated
;
4005 ext4_ext_handle_unwritten_extents(handle_t
*handle
, struct inode
*inode
,
4006 struct ext4_map_blocks
*map
,
4007 struct ext4_ext_path
**ppath
, int flags
,
4008 unsigned int allocated
, ext4_fsblk_t newblock
)
4010 struct ext4_ext_path
*path
= *ppath
;
4014 ext_debug("ext4_ext_handle_unwritten_extents: inode %lu, logical "
4015 "block %llu, max_blocks %u, flags %x, allocated %u\n",
4016 inode
->i_ino
, (unsigned long long)map
->m_lblk
, map
->m_len
,
4018 ext4_ext_show_leaf(inode
, path
);
4021 * When writing into unwritten space, we should not fail to
4022 * allocate metadata blocks for the new extent block if needed.
4024 flags
|= EXT4_GET_BLOCKS_METADATA_NOFAIL
;
4026 trace_ext4_ext_handle_unwritten_extents(inode
, map
, flags
,
4027 allocated
, newblock
);
4029 /* get_block() before submit the IO, split the extent */
4030 if (flags
& EXT4_GET_BLOCKS_PRE_IO
) {
4031 ret
= ext4_split_convert_extents(handle
, inode
, map
, ppath
,
4032 flags
| EXT4_GET_BLOCKS_CONVERT
);
4035 map
->m_flags
|= EXT4_MAP_UNWRITTEN
;
4038 /* IO end_io complete, convert the filled extent to written */
4039 if (flags
& EXT4_GET_BLOCKS_CONVERT
) {
4040 if (flags
& EXT4_GET_BLOCKS_ZERO
) {
4041 if (allocated
> map
->m_len
)
4042 allocated
= map
->m_len
;
4043 err
= ext4_issue_zeroout(inode
, map
->m_lblk
, newblock
,
4048 ret
= ext4_convert_unwritten_extents_endio(handle
, inode
, map
,
4051 ext4_update_inode_fsync_trans(handle
, inode
, 1);
4052 err
= check_eofblocks_fl(handle
, inode
, map
->m_lblk
,
4056 map
->m_flags
|= EXT4_MAP_MAPPED
;
4057 map
->m_pblk
= newblock
;
4058 if (allocated
> map
->m_len
)
4059 allocated
= map
->m_len
;
4060 map
->m_len
= allocated
;
4063 /* buffered IO case */
4065 * repeat fallocate creation request
4066 * we already have an unwritten extent
4068 if (flags
& EXT4_GET_BLOCKS_UNWRIT_EXT
) {
4069 map
->m_flags
|= EXT4_MAP_UNWRITTEN
;
4073 /* buffered READ or buffered write_begin() lookup */
4074 if ((flags
& EXT4_GET_BLOCKS_CREATE
) == 0) {
4076 * We have blocks reserved already. We
4077 * return allocated blocks so that delalloc
4078 * won't do block reservation for us. But
4079 * the buffer head will be unmapped so that
4080 * a read from the block returns 0s.
4082 map
->m_flags
|= EXT4_MAP_UNWRITTEN
;
4086 /* buffered write, writepage time, convert*/
4087 ret
= ext4_ext_convert_to_initialized(handle
, inode
, map
, ppath
, flags
);
4089 ext4_update_inode_fsync_trans(handle
, inode
, 1);
4096 map
->m_flags
|= EXT4_MAP_NEW
;
4098 * if we allocated more blocks than requested
4099 * we need to make sure we unmap the extra block
4100 * allocated. The actual needed block will get
4101 * unmapped later when we find the buffer_head marked
4104 if (allocated
> map
->m_len
) {
4105 clean_bdev_aliases(inode
->i_sb
->s_bdev
, newblock
+ map
->m_len
,
4106 allocated
- map
->m_len
);
4107 allocated
= map
->m_len
;
4109 map
->m_len
= allocated
;
4112 * If we have done fallocate with the offset that is already
4113 * delayed allocated, we would have block reservation
4114 * and quota reservation done in the delayed write path.
4115 * But fallocate would have already updated quota and block
4116 * count for this offset. So cancel these reservation
4118 if (flags
& EXT4_GET_BLOCKS_DELALLOC_RESERVE
) {
4119 unsigned int reserved_clusters
;
4120 reserved_clusters
= get_reserved_cluster_alloc(inode
,
4121 map
->m_lblk
, map
->m_len
);
4122 if (reserved_clusters
)
4123 ext4_da_update_reserve_space(inode
,
4129 map
->m_flags
|= EXT4_MAP_MAPPED
;
4130 if ((flags
& EXT4_GET_BLOCKS_KEEP_SIZE
) == 0) {
4131 err
= check_eofblocks_fl(handle
, inode
, map
->m_lblk
, path
,
4137 if (allocated
> map
->m_len
)
4138 allocated
= map
->m_len
;
4139 ext4_ext_show_leaf(inode
, path
);
4140 map
->m_pblk
= newblock
;
4141 map
->m_len
= allocated
;
4143 return err
? err
: allocated
;
4147 * get_implied_cluster_alloc - check to see if the requested
4148 * allocation (in the map structure) overlaps with a cluster already
4149 * allocated in an extent.
4150 * @sb The filesystem superblock structure
4151 * @map The requested lblk->pblk mapping
4152 * @ex The extent structure which might contain an implied
4153 * cluster allocation
4155 * This function is called by ext4_ext_map_blocks() after we failed to
4156 * find blocks that were already in the inode's extent tree. Hence,
4157 * we know that the beginning of the requested region cannot overlap
4158 * the extent from the inode's extent tree. There are three cases we
4159 * want to catch. The first is this case:
4161 * |--- cluster # N--|
4162 * |--- extent ---| |---- requested region ---|
4165 * The second case that we need to test for is this one:
4167 * |--------- cluster # N ----------------|
4168 * |--- requested region --| |------- extent ----|
4169 * |=======================|
4171 * The third case is when the requested region lies between two extents
4172 * within the same cluster:
4173 * |------------- cluster # N-------------|
4174 * |----- ex -----| |---- ex_right ----|
4175 * |------ requested region ------|
4176 * |================|
4178 * In each of the above cases, we need to set the map->m_pblk and
4179 * map->m_len so it corresponds to the return the extent labelled as
4180 * "|====|" from cluster #N, since it is already in use for data in
4181 * cluster EXT4_B2C(sbi, map->m_lblk). We will then return 1 to
4182 * signal to ext4_ext_map_blocks() that map->m_pblk should be treated
4183 * as a new "allocated" block region. Otherwise, we will return 0 and
4184 * ext4_ext_map_blocks() will then allocate one or more new clusters
4185 * by calling ext4_mb_new_blocks().
4187 static int get_implied_cluster_alloc(struct super_block
*sb
,
4188 struct ext4_map_blocks
*map
,
4189 struct ext4_extent
*ex
,
4190 struct ext4_ext_path
*path
)
4192 struct ext4_sb_info
*sbi
= EXT4_SB(sb
);
4193 ext4_lblk_t c_offset
= EXT4_LBLK_COFF(sbi
, map
->m_lblk
);
4194 ext4_lblk_t ex_cluster_start
, ex_cluster_end
;
4195 ext4_lblk_t rr_cluster_start
;
4196 ext4_lblk_t ee_block
= le32_to_cpu(ex
->ee_block
);
4197 ext4_fsblk_t ee_start
= ext4_ext_pblock(ex
);
4198 unsigned short ee_len
= ext4_ext_get_actual_len(ex
);
4200 /* The extent passed in that we are trying to match */
4201 ex_cluster_start
= EXT4_B2C(sbi
, ee_block
);
4202 ex_cluster_end
= EXT4_B2C(sbi
, ee_block
+ ee_len
- 1);
4204 /* The requested region passed into ext4_map_blocks() */
4205 rr_cluster_start
= EXT4_B2C(sbi
, map
->m_lblk
);
4207 if ((rr_cluster_start
== ex_cluster_end
) ||
4208 (rr_cluster_start
== ex_cluster_start
)) {
4209 if (rr_cluster_start
== ex_cluster_end
)
4210 ee_start
+= ee_len
- 1;
4211 map
->m_pblk
= EXT4_PBLK_CMASK(sbi
, ee_start
) + c_offset
;
4212 map
->m_len
= min(map
->m_len
,
4213 (unsigned) sbi
->s_cluster_ratio
- c_offset
);
4215 * Check for and handle this case:
4217 * |--------- cluster # N-------------|
4218 * |------- extent ----|
4219 * |--- requested region ---|
4223 if (map
->m_lblk
< ee_block
)
4224 map
->m_len
= min(map
->m_len
, ee_block
- map
->m_lblk
);
4227 * Check for the case where there is already another allocated
4228 * block to the right of 'ex' but before the end of the cluster.
4230 * |------------- cluster # N-------------|
4231 * |----- ex -----| |---- ex_right ----|
4232 * |------ requested region ------|
4233 * |================|
4235 if (map
->m_lblk
> ee_block
) {
4236 ext4_lblk_t next
= ext4_ext_next_allocated_block(path
);
4237 map
->m_len
= min(map
->m_len
, next
- map
->m_lblk
);
4240 trace_ext4_get_implied_cluster_alloc_exit(sb
, map
, 1);
4244 trace_ext4_get_implied_cluster_alloc_exit(sb
, map
, 0);
4250 * Block allocation/map/preallocation routine for extents based files
4253 * Need to be called with
4254 * down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system block
4255 * (ie, create is zero). Otherwise down_write(&EXT4_I(inode)->i_data_sem)
4257 * return > 0, number of of blocks already mapped/allocated
4258 * if create == 0 and these are pre-allocated blocks
4259 * buffer head is unmapped
4260 * otherwise blocks are mapped
4262 * return = 0, if plain look up failed (blocks have not been allocated)
4263 * buffer head is unmapped
4265 * return < 0, error case.
4267 int ext4_ext_map_blocks(handle_t
*handle
, struct inode
*inode
,
4268 struct ext4_map_blocks
*map
, int flags
)
4270 struct ext4_ext_path
*path
= NULL
;
4271 struct ext4_extent newex
, *ex
, *ex2
;
4272 struct ext4_sb_info
*sbi
= EXT4_SB(inode
->i_sb
);
4273 ext4_fsblk_t newblock
= 0;
4274 int free_on_err
= 0, err
= 0, depth
, ret
;
4275 unsigned int allocated
= 0, offset
= 0;
4276 unsigned int allocated_clusters
= 0;
4277 struct ext4_allocation_request ar
;
4278 ext4_lblk_t cluster_offset
;
4279 bool map_from_cluster
= false;
4281 ext_debug("blocks %u/%u requested for inode %lu\n",
4282 map
->m_lblk
, map
->m_len
, inode
->i_ino
);
4283 trace_ext4_ext_map_blocks_enter(inode
, map
->m_lblk
, map
->m_len
, flags
);
4285 /* find extent for this block */
4286 path
= ext4_find_extent(inode
, map
->m_lblk
, NULL
, 0);
4288 err
= PTR_ERR(path
);
4293 depth
= ext_depth(inode
);
4296 * consistent leaf must not be empty;
4297 * this situation is possible, though, _during_ tree modification;
4298 * this is why assert can't be put in ext4_find_extent()
4300 if (unlikely(path
[depth
].p_ext
== NULL
&& depth
!= 0)) {
4301 EXT4_ERROR_INODE(inode
, "bad extent address "
4302 "lblock: %lu, depth: %d pblock %lld",
4303 (unsigned long) map
->m_lblk
, depth
,
4304 path
[depth
].p_block
);
4305 err
= -EFSCORRUPTED
;
4309 ex
= path
[depth
].p_ext
;
4311 ext4_lblk_t ee_block
= le32_to_cpu(ex
->ee_block
);
4312 ext4_fsblk_t ee_start
= ext4_ext_pblock(ex
);
4313 unsigned short ee_len
;
4317 * unwritten extents are treated as holes, except that
4318 * we split out initialized portions during a write.
4320 ee_len
= ext4_ext_get_actual_len(ex
);
4322 trace_ext4_ext_show_extent(inode
, ee_block
, ee_start
, ee_len
);
4324 /* if found extent covers block, simply return it */
4325 if (in_range(map
->m_lblk
, ee_block
, ee_len
)) {
4326 newblock
= map
->m_lblk
- ee_block
+ ee_start
;
4327 /* number of remaining blocks in the extent */
4328 allocated
= ee_len
- (map
->m_lblk
- ee_block
);
4329 ext_debug("%u fit into %u:%d -> %llu\n", map
->m_lblk
,
4330 ee_block
, ee_len
, newblock
);
4333 * If the extent is initialized check whether the
4334 * caller wants to convert it to unwritten.
4336 if ((!ext4_ext_is_unwritten(ex
)) &&
4337 (flags
& EXT4_GET_BLOCKS_CONVERT_UNWRITTEN
)) {
4338 allocated
= convert_initialized_extent(
4339 handle
, inode
, map
, &path
,
4342 } else if (!ext4_ext_is_unwritten(ex
))
4345 ret
= ext4_ext_handle_unwritten_extents(
4346 handle
, inode
, map
, &path
, flags
,
4347 allocated
, newblock
);
4357 * requested block isn't allocated yet;
4358 * we couldn't try to create block if create flag is zero
4360 if ((flags
& EXT4_GET_BLOCKS_CREATE
) == 0) {
4361 ext4_lblk_t hole_start
, hole_len
;
4363 hole_start
= map
->m_lblk
;
4364 hole_len
= ext4_ext_determine_hole(inode
, path
, &hole_start
);
4366 * put just found gap into cache to speed up
4367 * subsequent requests
4369 ext4_ext_put_gap_in_cache(inode
, hole_start
, hole_len
);
4371 /* Update hole_len to reflect hole size after map->m_lblk */
4372 if (hole_start
!= map
->m_lblk
)
4373 hole_len
-= map
->m_lblk
- hole_start
;
4375 map
->m_len
= min_t(unsigned int, map
->m_len
, hole_len
);
4381 * Okay, we need to do block allocation.
4383 newex
.ee_block
= cpu_to_le32(map
->m_lblk
);
4384 cluster_offset
= EXT4_LBLK_COFF(sbi
, map
->m_lblk
);
4387 * If we are doing bigalloc, check to see if the extent returned
4388 * by ext4_find_extent() implies a cluster we can use.
4390 if (cluster_offset
&& ex
&&
4391 get_implied_cluster_alloc(inode
->i_sb
, map
, ex
, path
)) {
4392 ar
.len
= allocated
= map
->m_len
;
4393 newblock
= map
->m_pblk
;
4394 map_from_cluster
= true;
4395 goto got_allocated_blocks
;
4398 /* find neighbour allocated blocks */
4399 ar
.lleft
= map
->m_lblk
;
4400 err
= ext4_ext_search_left(inode
, path
, &ar
.lleft
, &ar
.pleft
);
4403 ar
.lright
= map
->m_lblk
;
4405 err
= ext4_ext_search_right(inode
, path
, &ar
.lright
, &ar
.pright
, &ex2
);
4409 /* Check if the extent after searching to the right implies a
4410 * cluster we can use. */
4411 if ((sbi
->s_cluster_ratio
> 1) && ex2
&&
4412 get_implied_cluster_alloc(inode
->i_sb
, map
, ex2
, path
)) {
4413 ar
.len
= allocated
= map
->m_len
;
4414 newblock
= map
->m_pblk
;
4415 map_from_cluster
= true;
4416 goto got_allocated_blocks
;
4420 * See if request is beyond maximum number of blocks we can have in
4421 * a single extent. For an initialized extent this limit is
4422 * EXT_INIT_MAX_LEN and for an unwritten extent this limit is
4423 * EXT_UNWRITTEN_MAX_LEN.
4425 if (map
->m_len
> EXT_INIT_MAX_LEN
&&
4426 !(flags
& EXT4_GET_BLOCKS_UNWRIT_EXT
))
4427 map
->m_len
= EXT_INIT_MAX_LEN
;
4428 else if (map
->m_len
> EXT_UNWRITTEN_MAX_LEN
&&
4429 (flags
& EXT4_GET_BLOCKS_UNWRIT_EXT
))
4430 map
->m_len
= EXT_UNWRITTEN_MAX_LEN
;
4432 /* Check if we can really insert (m_lblk)::(m_lblk + m_len) extent */
4433 newex
.ee_len
= cpu_to_le16(map
->m_len
);
4434 err
= ext4_ext_check_overlap(sbi
, inode
, &newex
, path
);
4436 allocated
= ext4_ext_get_actual_len(&newex
);
4438 allocated
= map
->m_len
;
4440 /* allocate new block */
4442 ar
.goal
= ext4_ext_find_goal(inode
, path
, map
->m_lblk
);
4443 ar
.logical
= map
->m_lblk
;
4445 * We calculate the offset from the beginning of the cluster
4446 * for the logical block number, since when we allocate a
4447 * physical cluster, the physical block should start at the
4448 * same offset from the beginning of the cluster. This is
4449 * needed so that future calls to get_implied_cluster_alloc()
4452 offset
= EXT4_LBLK_COFF(sbi
, map
->m_lblk
);
4453 ar
.len
= EXT4_NUM_B2C(sbi
, offset
+allocated
);
4455 ar
.logical
-= offset
;
4456 if (S_ISREG(inode
->i_mode
))
4457 ar
.flags
= EXT4_MB_HINT_DATA
;
4459 /* disable in-core preallocation for non-regular files */
4461 if (flags
& EXT4_GET_BLOCKS_NO_NORMALIZE
)
4462 ar
.flags
|= EXT4_MB_HINT_NOPREALLOC
;
4463 if (flags
& EXT4_GET_BLOCKS_DELALLOC_RESERVE
)
4464 ar
.flags
|= EXT4_MB_DELALLOC_RESERVED
;
4465 if (flags
& EXT4_GET_BLOCKS_METADATA_NOFAIL
)
4466 ar
.flags
|= EXT4_MB_USE_RESERVED
;
4467 newblock
= ext4_mb_new_blocks(handle
, &ar
, &err
);
4470 ext_debug("allocate new block: goal %llu, found %llu/%u\n",
4471 ar
.goal
, newblock
, allocated
);
4473 allocated_clusters
= ar
.len
;
4474 ar
.len
= EXT4_C2B(sbi
, ar
.len
) - offset
;
4475 if (ar
.len
> allocated
)
4478 got_allocated_blocks
:
4479 /* try to insert new extent into found leaf and return */
4480 ext4_ext_store_pblock(&newex
, newblock
+ offset
);
4481 newex
.ee_len
= cpu_to_le16(ar
.len
);
4482 /* Mark unwritten */
4483 if (flags
& EXT4_GET_BLOCKS_UNWRIT_EXT
){
4484 ext4_ext_mark_unwritten(&newex
);
4485 map
->m_flags
|= EXT4_MAP_UNWRITTEN
;
4489 if ((flags
& EXT4_GET_BLOCKS_KEEP_SIZE
) == 0)
4490 err
= check_eofblocks_fl(handle
, inode
, map
->m_lblk
,
4493 err
= ext4_ext_insert_extent(handle
, inode
, &path
,
4496 if (err
&& free_on_err
) {
4497 int fb_flags
= flags
& EXT4_GET_BLOCKS_DELALLOC_RESERVE
?
4498 EXT4_FREE_BLOCKS_NO_QUOT_UPDATE
: 0;
4499 /* free data blocks we just allocated */
4500 /* not a good idea to call discard here directly,
4501 * but otherwise we'd need to call it every free() */
4502 ext4_discard_preallocations(inode
);
4503 ext4_free_blocks(handle
, inode
, NULL
, newblock
,
4504 EXT4_C2B(sbi
, allocated_clusters
), fb_flags
);
4508 /* previous routine could use block we allocated */
4509 newblock
= ext4_ext_pblock(&newex
);
4510 allocated
= ext4_ext_get_actual_len(&newex
);
4511 if (allocated
> map
->m_len
)
4512 allocated
= map
->m_len
;
4513 map
->m_flags
|= EXT4_MAP_NEW
;
4516 * Update reserved blocks/metadata blocks after successful
4517 * block allocation which had been deferred till now.
4519 if (flags
& EXT4_GET_BLOCKS_DELALLOC_RESERVE
) {
4520 unsigned int reserved_clusters
;
4522 * Check how many clusters we had reserved this allocated range
4524 reserved_clusters
= get_reserved_cluster_alloc(inode
,
4525 map
->m_lblk
, allocated
);
4526 if (!map_from_cluster
) {
4527 BUG_ON(allocated_clusters
< reserved_clusters
);
4528 if (reserved_clusters
< allocated_clusters
) {
4529 struct ext4_inode_info
*ei
= EXT4_I(inode
);
4530 int reservation
= allocated_clusters
-
4533 * It seems we claimed few clusters outside of
4534 * the range of this allocation. We should give
4535 * it back to the reservation pool. This can
4536 * happen in the following case:
4538 * * Suppose s_cluster_ratio is 4 (i.e., each
4539 * cluster has 4 blocks. Thus, the clusters
4540 * are [0-3],[4-7],[8-11]...
4541 * * First comes delayed allocation write for
4542 * logical blocks 10 & 11. Since there were no
4543 * previous delayed allocated blocks in the
4544 * range [8-11], we would reserve 1 cluster
4546 * * Next comes write for logical blocks 3 to 8.
4547 * In this case, we will reserve 2 clusters
4548 * (for [0-3] and [4-7]; and not for [8-11] as
4549 * that range has a delayed allocated blocks.
4550 * Thus total reserved clusters now becomes 3.
4551 * * Now, during the delayed allocation writeout
4552 * time, we will first write blocks [3-8] and
4553 * allocate 3 clusters for writing these
4554 * blocks. Also, we would claim all these
4555 * three clusters above.
4556 * * Now when we come here to writeout the
4557 * blocks [10-11], we would expect to claim
4558 * the reservation of 1 cluster we had made
4559 * (and we would claim it since there are no
4560 * more delayed allocated blocks in the range
4561 * [8-11]. But our reserved cluster count had
4562 * already gone to 0.
4564 * Thus, at the step 4 above when we determine
4565 * that there are still some unwritten delayed
4566 * allocated blocks outside of our current
4567 * block range, we should increment the
4568 * reserved clusters count so that when the
4569 * remaining blocks finally gets written, we
4572 dquot_reserve_block(inode
,
4573 EXT4_C2B(sbi
, reservation
));
4574 spin_lock(&ei
->i_block_reservation_lock
);
4575 ei
->i_reserved_data_blocks
+= reservation
;
4576 spin_unlock(&ei
->i_block_reservation_lock
);
4579 * We will claim quota for all newly allocated blocks.
4580 * We're updating the reserved space *after* the
4581 * correction above so we do not accidentally free
4582 * all the metadata reservation because we might
4583 * actually need it later on.
4585 ext4_da_update_reserve_space(inode
, allocated_clusters
,
4591 * Cache the extent and update transaction to commit on fdatasync only
4592 * when it is _not_ an unwritten extent.
4594 if ((flags
& EXT4_GET_BLOCKS_UNWRIT_EXT
) == 0)
4595 ext4_update_inode_fsync_trans(handle
, inode
, 1);
4597 ext4_update_inode_fsync_trans(handle
, inode
, 0);
4599 if (allocated
> map
->m_len
)
4600 allocated
= map
->m_len
;
4601 ext4_ext_show_leaf(inode
, path
);
4602 map
->m_flags
|= EXT4_MAP_MAPPED
;
4603 map
->m_pblk
= newblock
;
4604 map
->m_len
= allocated
;
4606 ext4_ext_drop_refs(path
);
4609 trace_ext4_ext_map_blocks_exit(inode
, flags
, map
,
4610 err
? err
: allocated
);
4611 return err
? err
: allocated
;
4614 int ext4_ext_truncate(handle_t
*handle
, struct inode
*inode
)
4616 struct super_block
*sb
= inode
->i_sb
;
4617 ext4_lblk_t last_block
;
4621 * TODO: optimization is possible here.
4622 * Probably we need not scan at all,
4623 * because page truncation is enough.
4626 /* we have to know where to truncate from in crash case */
4627 EXT4_I(inode
)->i_disksize
= inode
->i_size
;
4628 err
= ext4_mark_inode_dirty(handle
, inode
);
4632 last_block
= (inode
->i_size
+ sb
->s_blocksize
- 1)
4633 >> EXT4_BLOCK_SIZE_BITS(sb
);
4635 err
= ext4_es_remove_extent(inode
, last_block
,
4636 EXT_MAX_BLOCKS
- last_block
);
4637 if (err
== -ENOMEM
) {
4639 congestion_wait(BLK_RW_ASYNC
, HZ
/50);
4644 return ext4_ext_remove_space(inode
, last_block
, EXT_MAX_BLOCKS
- 1);
4647 static int ext4_alloc_file_blocks(struct file
*file
, ext4_lblk_t offset
,
4648 ext4_lblk_t len
, loff_t new_size
,
4651 struct inode
*inode
= file_inode(file
);
4657 struct ext4_map_blocks map
;
4658 unsigned int credits
;
4661 BUG_ON(!ext4_test_inode_flag(inode
, EXT4_INODE_EXTENTS
));
4662 map
.m_lblk
= offset
;
4665 * Don't normalize the request if it can fit in one extent so
4666 * that it doesn't get unnecessarily split into multiple
4669 if (len
<= EXT_UNWRITTEN_MAX_LEN
)
4670 flags
|= EXT4_GET_BLOCKS_NO_NORMALIZE
;
4673 * credits to insert 1 extent into extent tree
4675 credits
= ext4_chunk_trans_blocks(inode
, len
);
4676 depth
= ext_depth(inode
);
4679 while (ret
>= 0 && len
) {
4681 * Recalculate credits when extent tree depth changes.
4683 if (depth
!= ext_depth(inode
)) {
4684 credits
= ext4_chunk_trans_blocks(inode
, len
);
4685 depth
= ext_depth(inode
);
4688 handle
= ext4_journal_start(inode
, EXT4_HT_MAP_BLOCKS
,
4690 if (IS_ERR(handle
)) {
4691 ret
= PTR_ERR(handle
);
4694 ret
= ext4_map_blocks(handle
, inode
, &map
, flags
);
4696 ext4_debug("inode #%lu: block %u: len %u: "
4697 "ext4_ext_map_blocks returned %d",
4698 inode
->i_ino
, map
.m_lblk
,
4700 ext4_mark_inode_dirty(handle
, inode
);
4701 ret2
= ext4_journal_stop(handle
);
4705 map
.m_len
= len
= len
- ret
;
4706 epos
= (loff_t
)map
.m_lblk
<< inode
->i_blkbits
;
4707 inode
->i_ctime
= current_time(inode
);
4709 if (epos
> new_size
)
4711 if (ext4_update_inode_size(inode
, epos
) & 0x1)
4712 inode
->i_mtime
= inode
->i_ctime
;
4714 if (epos
> inode
->i_size
)
4715 ext4_set_inode_flag(inode
,
4716 EXT4_INODE_EOFBLOCKS
);
4718 ext4_mark_inode_dirty(handle
, inode
);
4719 ext4_update_inode_fsync_trans(handle
, inode
, 1);
4720 ret2
= ext4_journal_stop(handle
);
4724 if (ret
== -ENOSPC
&&
4725 ext4_should_retry_alloc(inode
->i_sb
, &retries
)) {
4730 return ret
> 0 ? ret2
: ret
;
4733 static long ext4_zero_range(struct file
*file
, loff_t offset
,
4734 loff_t len
, int mode
)
4736 struct inode
*inode
= file_inode(file
);
4737 handle_t
*handle
= NULL
;
4738 unsigned int max_blocks
;
4739 loff_t new_size
= 0;
4743 int partial_begin
, partial_end
;
4746 unsigned int blkbits
= inode
->i_blkbits
;
4748 trace_ext4_zero_range(inode
, offset
, len
, mode
);
4750 if (!S_ISREG(inode
->i_mode
))
4753 /* Call ext4_force_commit to flush all data in case of data=journal. */
4754 if (ext4_should_journal_data(inode
)) {
4755 ret
= ext4_force_commit(inode
->i_sb
);
4761 * Round up offset. This is not fallocate, we neet to zero out
4762 * blocks, so convert interior block aligned part of the range to
4763 * unwritten and possibly manually zero out unaligned parts of the
4766 start
= round_up(offset
, 1 << blkbits
);
4767 end
= round_down((offset
+ len
), 1 << blkbits
);
4769 if (start
< offset
|| end
> offset
+ len
)
4771 partial_begin
= offset
& ((1 << blkbits
) - 1);
4772 partial_end
= (offset
+ len
) & ((1 << blkbits
) - 1);
4774 lblk
= start
>> blkbits
;
4775 max_blocks
= (end
>> blkbits
);
4776 if (max_blocks
< lblk
)
4784 * Indirect files do not support unwritten extnets
4786 if (!(ext4_test_inode_flag(inode
, EXT4_INODE_EXTENTS
))) {
4791 if (!(mode
& FALLOC_FL_KEEP_SIZE
) &&
4792 (offset
+ len
> i_size_read(inode
) ||
4793 offset
+ len
> EXT4_I(inode
)->i_disksize
)) {
4794 new_size
= offset
+ len
;
4795 ret
= inode_newsize_ok(inode
, new_size
);
4800 flags
= EXT4_GET_BLOCKS_CREATE_UNWRIT_EXT
;
4801 if (mode
& FALLOC_FL_KEEP_SIZE
)
4802 flags
|= EXT4_GET_BLOCKS_KEEP_SIZE
;
4804 /* Wait all existing dio workers, newcomers will block on i_mutex */
4805 inode_dio_wait(inode
);
4807 /* Preallocate the range including the unaligned edges */
4808 if (partial_begin
|| partial_end
) {
4809 ret
= ext4_alloc_file_blocks(file
,
4810 round_down(offset
, 1 << blkbits
) >> blkbits
,
4811 (round_up((offset
+ len
), 1 << blkbits
) -
4812 round_down(offset
, 1 << blkbits
)) >> blkbits
,
4819 /* Zero range excluding the unaligned edges */
4820 if (max_blocks
> 0) {
4821 flags
|= (EXT4_GET_BLOCKS_CONVERT_UNWRITTEN
|
4825 * Prevent page faults from reinstantiating pages we have
4826 * released from page cache.
4828 down_write(&EXT4_I(inode
)->i_mmap_sem
);
4830 ret
= ext4_break_layouts(inode
);
4832 up_write(&EXT4_I(inode
)->i_mmap_sem
);
4836 ret
= ext4_update_disksize_before_punch(inode
, offset
, len
);
4838 up_write(&EXT4_I(inode
)->i_mmap_sem
);
4841 /* Now release the pages and zero block aligned part of pages */
4842 truncate_pagecache_range(inode
, start
, end
- 1);
4843 inode
->i_mtime
= inode
->i_ctime
= current_time(inode
);
4845 ret
= ext4_alloc_file_blocks(file
, lblk
, max_blocks
, new_size
,
4847 up_write(&EXT4_I(inode
)->i_mmap_sem
);
4851 if (!partial_begin
&& !partial_end
)
4855 * In worst case we have to writeout two nonadjacent unwritten
4856 * blocks and update the inode
4858 credits
= (2 * ext4_ext_index_trans_blocks(inode
, 2)) + 1;
4859 if (ext4_should_journal_data(inode
))
4861 handle
= ext4_journal_start(inode
, EXT4_HT_MISC
, credits
);
4862 if (IS_ERR(handle
)) {
4863 ret
= PTR_ERR(handle
);
4864 ext4_std_error(inode
->i_sb
, ret
);
4868 inode
->i_mtime
= inode
->i_ctime
= current_time(inode
);
4870 ext4_update_inode_size(inode
, new_size
);
4873 * Mark that we allocate beyond EOF so the subsequent truncate
4874 * can proceed even if the new size is the same as i_size.
4876 if ((offset
+ len
) > i_size_read(inode
))
4877 ext4_set_inode_flag(inode
, EXT4_INODE_EOFBLOCKS
);
4879 ext4_mark_inode_dirty(handle
, inode
);
4881 /* Zero out partial block at the edges of the range */
4882 ret
= ext4_zero_partial_blocks(handle
, inode
, offset
, len
);
4884 ext4_update_inode_fsync_trans(handle
, inode
, 1);
4886 if (file
->f_flags
& O_SYNC
)
4887 ext4_handle_sync(handle
);
4889 ext4_journal_stop(handle
);
4891 inode_unlock(inode
);
4896 * preallocate space for a file. This implements ext4's fallocate file
4897 * operation, which gets called from sys_fallocate system call.
4898 * For block-mapped files, posix_fallocate should fall back to the method
4899 * of writing zeroes to the required new blocks (the same behavior which is
4900 * expected for file systems which do not support fallocate() system call).
4902 long ext4_fallocate(struct file
*file
, int mode
, loff_t offset
, loff_t len
)
4904 struct inode
*inode
= file_inode(file
);
4905 loff_t new_size
= 0;
4906 unsigned int max_blocks
;
4910 unsigned int blkbits
= inode
->i_blkbits
;
4913 * Encrypted inodes can't handle collapse range or insert
4914 * range since we would need to re-encrypt blocks with a
4915 * different IV or XTS tweak (which are based on the logical
4918 * XXX It's not clear why zero range isn't working, but we'll
4919 * leave it disabled for encrypted inodes for now. This is a
4920 * bug we should fix....
4922 if (ext4_encrypted_inode(inode
) &&
4923 (mode
& (FALLOC_FL_COLLAPSE_RANGE
| FALLOC_FL_INSERT_RANGE
|
4924 FALLOC_FL_ZERO_RANGE
)))
4927 /* Return error if mode is not supported */
4928 if (mode
& ~(FALLOC_FL_KEEP_SIZE
| FALLOC_FL_PUNCH_HOLE
|
4929 FALLOC_FL_COLLAPSE_RANGE
| FALLOC_FL_ZERO_RANGE
|
4930 FALLOC_FL_INSERT_RANGE
))
4933 if (mode
& FALLOC_FL_PUNCH_HOLE
)
4934 return ext4_punch_hole(inode
, offset
, len
);
4936 ret
= ext4_convert_inline_data(inode
);
4940 if (mode
& FALLOC_FL_COLLAPSE_RANGE
)
4941 return ext4_collapse_range(inode
, offset
, len
);
4943 if (mode
& FALLOC_FL_INSERT_RANGE
)
4944 return ext4_insert_range(inode
, offset
, len
);
4946 if (mode
& FALLOC_FL_ZERO_RANGE
)
4947 return ext4_zero_range(file
, offset
, len
, mode
);
4949 trace_ext4_fallocate_enter(inode
, offset
, len
, mode
);
4950 lblk
= offset
>> blkbits
;
4952 max_blocks
= EXT4_MAX_BLOCKS(len
, offset
, blkbits
);
4953 flags
= EXT4_GET_BLOCKS_CREATE_UNWRIT_EXT
;
4954 if (mode
& FALLOC_FL_KEEP_SIZE
)
4955 flags
|= EXT4_GET_BLOCKS_KEEP_SIZE
;
4960 * We only support preallocation for extent-based files only
4962 if (!(ext4_test_inode_flag(inode
, EXT4_INODE_EXTENTS
))) {
4967 if (!(mode
& FALLOC_FL_KEEP_SIZE
) &&
4968 (offset
+ len
> i_size_read(inode
) ||
4969 offset
+ len
> EXT4_I(inode
)->i_disksize
)) {
4970 new_size
= offset
+ len
;
4971 ret
= inode_newsize_ok(inode
, new_size
);
4976 /* Wait all existing dio workers, newcomers will block on i_mutex */
4977 inode_dio_wait(inode
);
4979 ret
= ext4_alloc_file_blocks(file
, lblk
, max_blocks
, new_size
, flags
);
4983 if (file
->f_flags
& O_SYNC
&& EXT4_SB(inode
->i_sb
)->s_journal
) {
4984 ret
= jbd2_complete_transaction(EXT4_SB(inode
->i_sb
)->s_journal
,
4985 EXT4_I(inode
)->i_sync_tid
);
4988 inode_unlock(inode
);
4989 trace_ext4_fallocate_exit(inode
, offset
, max_blocks
, ret
);
4994 * This function convert a range of blocks to written extents
4995 * The caller of this function will pass the start offset and the size.
4996 * all unwritten extents within this range will be converted to
4999 * This function is called from the direct IO end io call back
5000 * function, to convert the fallocated extents after IO is completed.
5001 * Returns 0 on success.
5003 int ext4_convert_unwritten_extents(handle_t
*handle
, struct inode
*inode
,
5004 loff_t offset
, ssize_t len
)
5006 unsigned int max_blocks
;
5009 struct ext4_map_blocks map
;
5010 unsigned int credits
, blkbits
= inode
->i_blkbits
;
5012 map
.m_lblk
= offset
>> blkbits
;
5013 max_blocks
= EXT4_MAX_BLOCKS(len
, offset
, blkbits
);
5016 * This is somewhat ugly but the idea is clear: When transaction is
5017 * reserved, everything goes into it. Otherwise we rather start several
5018 * smaller transactions for conversion of each extent separately.
5021 handle
= ext4_journal_start_reserved(handle
,
5022 EXT4_HT_EXT_CONVERT
);
5024 return PTR_ERR(handle
);
5028 * credits to insert 1 extent into extent tree
5030 credits
= ext4_chunk_trans_blocks(inode
, max_blocks
);
5032 while (ret
>= 0 && ret
< max_blocks
) {
5034 map
.m_len
= (max_blocks
-= ret
);
5036 handle
= ext4_journal_start(inode
, EXT4_HT_MAP_BLOCKS
,
5038 if (IS_ERR(handle
)) {
5039 ret
= PTR_ERR(handle
);
5043 ret
= ext4_map_blocks(handle
, inode
, &map
,
5044 EXT4_GET_BLOCKS_IO_CONVERT_EXT
);
5046 ext4_warning(inode
->i_sb
,
5047 "inode #%lu: block %u: len %u: "
5048 "ext4_ext_map_blocks returned %d",
5049 inode
->i_ino
, map
.m_lblk
,
5051 ext4_mark_inode_dirty(handle
, inode
);
5053 ret2
= ext4_journal_stop(handle
);
5054 if (ret
<= 0 || ret2
)
5058 ret2
= ext4_journal_stop(handle
);
5059 return ret
> 0 ? ret2
: ret
;
5063 * If newes is not existing extent (newes->ec_pblk equals zero) find
5064 * delayed extent at start of newes and update newes accordingly and
5065 * return start of the next delayed extent.
5067 * If newes is existing extent (newes->ec_pblk is not equal zero)
5068 * return start of next delayed extent or EXT_MAX_BLOCKS if no delayed
5069 * extent found. Leave newes unmodified.
5071 static int ext4_find_delayed_extent(struct inode
*inode
,
5072 struct extent_status
*newes
)
5074 struct extent_status es
;
5075 ext4_lblk_t block
, next_del
;
5077 if (newes
->es_pblk
== 0) {
5078 ext4_es_find_delayed_extent_range(inode
, newes
->es_lblk
,
5079 newes
->es_lblk
+ newes
->es_len
- 1, &es
);
5082 * No extent in extent-tree contains block @newes->es_pblk,
5083 * then the block may stay in 1)a hole or 2)delayed-extent.
5089 if (es
.es_lblk
> newes
->es_lblk
) {
5091 newes
->es_len
= min(es
.es_lblk
- newes
->es_lblk
,
5096 newes
->es_len
= es
.es_lblk
+ es
.es_len
- newes
->es_lblk
;
5099 block
= newes
->es_lblk
+ newes
->es_len
;
5100 ext4_es_find_delayed_extent_range(inode
, block
, EXT_MAX_BLOCKS
, &es
);
5102 next_del
= EXT_MAX_BLOCKS
;
5104 next_del
= es
.es_lblk
;
5108 /* fiemap flags we can handle specified here */
5109 #define EXT4_FIEMAP_FLAGS (FIEMAP_FLAG_SYNC|FIEMAP_FLAG_XATTR)
5111 static int ext4_xattr_fiemap(struct inode
*inode
,
5112 struct fiemap_extent_info
*fieinfo
)
5116 __u32 flags
= FIEMAP_EXTENT_LAST
;
5117 int blockbits
= inode
->i_sb
->s_blocksize_bits
;
5121 if (ext4_test_inode_state(inode
, EXT4_STATE_XATTR
)) {
5122 struct ext4_iloc iloc
;
5123 int offset
; /* offset of xattr in inode */
5125 error
= ext4_get_inode_loc(inode
, &iloc
);
5128 physical
= (__u64
)iloc
.bh
->b_blocknr
<< blockbits
;
5129 offset
= EXT4_GOOD_OLD_INODE_SIZE
+
5130 EXT4_I(inode
)->i_extra_isize
;
5132 length
= EXT4_SB(inode
->i_sb
)->s_inode_size
- offset
;
5133 flags
|= FIEMAP_EXTENT_DATA_INLINE
;
5135 } else { /* external block */
5136 physical
= (__u64
)EXT4_I(inode
)->i_file_acl
<< blockbits
;
5137 length
= inode
->i_sb
->s_blocksize
;
5141 error
= fiemap_fill_next_extent(fieinfo
, 0, physical
,
5143 return (error
< 0 ? error
: 0);
5146 int ext4_fiemap(struct inode
*inode
, struct fiemap_extent_info
*fieinfo
,
5147 __u64 start
, __u64 len
)
5149 ext4_lblk_t start_blk
;
5152 if (ext4_has_inline_data(inode
)) {
5155 error
= ext4_inline_data_fiemap(inode
, fieinfo
, &has_inline
,
5162 if (fieinfo
->fi_flags
& FIEMAP_FLAG_CACHE
) {
5163 error
= ext4_ext_precache(inode
);
5168 /* fallback to generic here if not in extents fmt */
5169 if (!(ext4_test_inode_flag(inode
, EXT4_INODE_EXTENTS
)))
5170 return generic_block_fiemap(inode
, fieinfo
, start
, len
,
5173 if (fiemap_check_flags(fieinfo
, EXT4_FIEMAP_FLAGS
))
5176 if (fieinfo
->fi_flags
& FIEMAP_FLAG_XATTR
) {
5177 error
= ext4_xattr_fiemap(inode
, fieinfo
);
5179 ext4_lblk_t len_blks
;
5182 start_blk
= start
>> inode
->i_sb
->s_blocksize_bits
;
5183 last_blk
= (start
+ len
- 1) >> inode
->i_sb
->s_blocksize_bits
;
5184 if (last_blk
>= EXT_MAX_BLOCKS
)
5185 last_blk
= EXT_MAX_BLOCKS
-1;
5186 len_blks
= ((ext4_lblk_t
) last_blk
) - start_blk
+ 1;
5189 * Walk the extent tree gathering extent information
5190 * and pushing extents back to the user.
5192 error
= ext4_fill_fiemap_extents(inode
, start_blk
,
5200 * Function to access the path buffer for marking it dirty.
5201 * It also checks if there are sufficient credits left in the journal handle
5205 ext4_access_path(handle_t
*handle
, struct inode
*inode
,
5206 struct ext4_ext_path
*path
)
5210 if (!ext4_handle_valid(handle
))
5214 * Check if need to extend journal credits
5215 * 3 for leaf, sb, and inode plus 2 (bmap and group
5216 * descriptor) for each block group; assume two block
5219 if (handle
->h_buffer_credits
< 7) {
5220 credits
= ext4_writepage_trans_blocks(inode
);
5221 err
= ext4_ext_truncate_extend_restart(handle
, inode
, credits
);
5222 /* EAGAIN is success */
5223 if (err
&& err
!= -EAGAIN
)
5227 err
= ext4_ext_get_access(handle
, inode
, path
);
5232 * ext4_ext_shift_path_extents:
5233 * Shift the extents of a path structure lying between path[depth].p_ext
5234 * and EXT_LAST_EXTENT(path[depth].p_hdr), by @shift blocks. @SHIFT tells
5235 * if it is right shift or left shift operation.
5238 ext4_ext_shift_path_extents(struct ext4_ext_path
*path
, ext4_lblk_t shift
,
5239 struct inode
*inode
, handle_t
*handle
,
5240 enum SHIFT_DIRECTION SHIFT
)
5243 struct ext4_extent
*ex_start
, *ex_last
;
5245 depth
= path
->p_depth
;
5247 while (depth
>= 0) {
5248 if (depth
== path
->p_depth
) {
5249 ex_start
= path
[depth
].p_ext
;
5251 return -EFSCORRUPTED
;
5253 ex_last
= EXT_LAST_EXTENT(path
[depth
].p_hdr
);
5255 err
= ext4_access_path(handle
, inode
, path
+ depth
);
5259 if (ex_start
== EXT_FIRST_EXTENT(path
[depth
].p_hdr
))
5262 while (ex_start
<= ex_last
) {
5263 if (SHIFT
== SHIFT_LEFT
) {
5264 le32_add_cpu(&ex_start
->ee_block
,
5266 /* Try to merge to the left. */
5268 EXT_FIRST_EXTENT(path
[depth
].p_hdr
))
5270 ext4_ext_try_to_merge_right(inode
,
5271 path
, ex_start
- 1))
5276 le32_add_cpu(&ex_last
->ee_block
, shift
);
5277 ext4_ext_try_to_merge_right(inode
, path
,
5282 err
= ext4_ext_dirty(handle
, inode
, path
+ depth
);
5286 if (--depth
< 0 || !update
)
5290 /* Update index too */
5291 err
= ext4_access_path(handle
, inode
, path
+ depth
);
5295 if (SHIFT
== SHIFT_LEFT
)
5296 le32_add_cpu(&path
[depth
].p_idx
->ei_block
, -shift
);
5298 le32_add_cpu(&path
[depth
].p_idx
->ei_block
, shift
);
5299 err
= ext4_ext_dirty(handle
, inode
, path
+ depth
);
5303 /* we are done if current index is not a starting index */
5304 if (path
[depth
].p_idx
!= EXT_FIRST_INDEX(path
[depth
].p_hdr
))
5315 * ext4_ext_shift_extents:
5316 * All the extents which lies in the range from @start to the last allocated
5317 * block for the @inode are shifted either towards left or right (depending
5318 * upon @SHIFT) by @shift blocks.
5319 * On success, 0 is returned, error otherwise.
5322 ext4_ext_shift_extents(struct inode
*inode
, handle_t
*handle
,
5323 ext4_lblk_t start
, ext4_lblk_t shift
,
5324 enum SHIFT_DIRECTION SHIFT
)
5326 struct ext4_ext_path
*path
;
5328 struct ext4_extent
*extent
;
5329 ext4_lblk_t stop
, *iterator
, ex_start
, ex_end
;
5331 /* Let path point to the last extent */
5332 path
= ext4_find_extent(inode
, EXT_MAX_BLOCKS
- 1, NULL
,
5335 return PTR_ERR(path
);
5337 depth
= path
->p_depth
;
5338 extent
= path
[depth
].p_ext
;
5342 stop
= le32_to_cpu(extent
->ee_block
);
5345 * For left shifts, make sure the hole on the left is big enough to
5346 * accommodate the shift. For right shifts, make sure the last extent
5347 * won't be shifted beyond EXT_MAX_BLOCKS.
5349 if (SHIFT
== SHIFT_LEFT
) {
5350 path
= ext4_find_extent(inode
, start
- 1, &path
,
5353 return PTR_ERR(path
);
5354 depth
= path
->p_depth
;
5355 extent
= path
[depth
].p_ext
;
5357 ex_start
= le32_to_cpu(extent
->ee_block
);
5358 ex_end
= le32_to_cpu(extent
->ee_block
) +
5359 ext4_ext_get_actual_len(extent
);
5365 if ((start
== ex_start
&& shift
> ex_start
) ||
5366 (shift
> start
- ex_end
)) {
5371 if (shift
> EXT_MAX_BLOCKS
-
5372 (stop
+ ext4_ext_get_actual_len(extent
))) {
5379 * In case of left shift, iterator points to start and it is increased
5380 * till we reach stop. In case of right shift, iterator points to stop
5381 * and it is decreased till we reach start.
5383 if (SHIFT
== SHIFT_LEFT
)
5389 * Its safe to start updating extents. Start and stop are unsigned, so
5390 * in case of right shift if extent with 0 block is reached, iterator
5391 * becomes NULL to indicate the end of the loop.
5393 while (iterator
&& start
<= stop
) {
5394 path
= ext4_find_extent(inode
, *iterator
, &path
,
5397 return PTR_ERR(path
);
5398 depth
= path
->p_depth
;
5399 extent
= path
[depth
].p_ext
;
5401 EXT4_ERROR_INODE(inode
, "unexpected hole at %lu",
5402 (unsigned long) *iterator
);
5403 return -EFSCORRUPTED
;
5405 if (SHIFT
== SHIFT_LEFT
&& *iterator
>
5406 le32_to_cpu(extent
->ee_block
)) {
5407 /* Hole, move to the next extent */
5408 if (extent
< EXT_LAST_EXTENT(path
[depth
].p_hdr
)) {
5409 path
[depth
].p_ext
++;
5411 *iterator
= ext4_ext_next_allocated_block(path
);
5416 if (SHIFT
== SHIFT_LEFT
) {
5417 extent
= EXT_LAST_EXTENT(path
[depth
].p_hdr
);
5418 *iterator
= le32_to_cpu(extent
->ee_block
) +
5419 ext4_ext_get_actual_len(extent
);
5421 extent
= EXT_FIRST_EXTENT(path
[depth
].p_hdr
);
5422 if (le32_to_cpu(extent
->ee_block
) > 0)
5423 *iterator
= le32_to_cpu(extent
->ee_block
) - 1;
5425 /* Beginning is reached, end of the loop */
5427 /* Update path extent in case we need to stop */
5428 while (le32_to_cpu(extent
->ee_block
) < start
)
5430 path
[depth
].p_ext
= extent
;
5432 ret
= ext4_ext_shift_path_extents(path
, shift
, inode
,
5438 ext4_ext_drop_refs(path
);
5444 * ext4_collapse_range:
5445 * This implements the fallocate's collapse range functionality for ext4
5446 * Returns: 0 and non-zero on error.
5448 int ext4_collapse_range(struct inode
*inode
, loff_t offset
, loff_t len
)
5450 struct super_block
*sb
= inode
->i_sb
;
5451 ext4_lblk_t punch_start
, punch_stop
;
5453 unsigned int credits
;
5454 loff_t new_size
, ioffset
;
5458 * We need to test this early because xfstests assumes that a
5459 * collapse range of (0, 1) will return EOPNOTSUPP if the file
5460 * system does not support collapse range.
5462 if (!ext4_test_inode_flag(inode
, EXT4_INODE_EXTENTS
))
5465 /* Collapse range works only on fs block size aligned offsets. */
5466 if (offset
& (EXT4_CLUSTER_SIZE(sb
) - 1) ||
5467 len
& (EXT4_CLUSTER_SIZE(sb
) - 1))
5470 if (!S_ISREG(inode
->i_mode
))
5473 trace_ext4_collapse_range(inode
, offset
, len
);
5475 punch_start
= offset
>> EXT4_BLOCK_SIZE_BITS(sb
);
5476 punch_stop
= (offset
+ len
) >> EXT4_BLOCK_SIZE_BITS(sb
);
5478 /* Call ext4_force_commit to flush all data in case of data=journal. */
5479 if (ext4_should_journal_data(inode
)) {
5480 ret
= ext4_force_commit(inode
->i_sb
);
5487 * There is no need to overlap collapse range with EOF, in which case
5488 * it is effectively a truncate operation
5490 if (offset
+ len
>= i_size_read(inode
)) {
5495 /* Currently just for extent based files */
5496 if (!ext4_test_inode_flag(inode
, EXT4_INODE_EXTENTS
)) {
5501 /* Wait for existing dio to complete */
5502 inode_dio_wait(inode
);
5505 * Prevent page faults from reinstantiating pages we have released from
5508 down_write(&EXT4_I(inode
)->i_mmap_sem
);
5510 ret
= ext4_break_layouts(inode
);
5515 * Need to round down offset to be aligned with page size boundary
5516 * for page size > block size.
5518 ioffset
= round_down(offset
, PAGE_SIZE
);
5520 * Write tail of the last page before removed range since it will get
5521 * removed from the page cache below.
5523 ret
= filemap_write_and_wait_range(inode
->i_mapping
, ioffset
, offset
);
5527 * Write data that will be shifted to preserve them when discarding
5528 * page cache below. We are also protected from pages becoming dirty
5531 ret
= filemap_write_and_wait_range(inode
->i_mapping
, offset
+ len
,
5535 truncate_pagecache(inode
, ioffset
);
5537 credits
= ext4_writepage_trans_blocks(inode
);
5538 handle
= ext4_journal_start(inode
, EXT4_HT_TRUNCATE
, credits
);
5539 if (IS_ERR(handle
)) {
5540 ret
= PTR_ERR(handle
);
5544 down_write(&EXT4_I(inode
)->i_data_sem
);
5545 ext4_discard_preallocations(inode
);
5547 ret
= ext4_es_remove_extent(inode
, punch_start
,
5548 EXT_MAX_BLOCKS
- punch_start
);
5550 up_write(&EXT4_I(inode
)->i_data_sem
);
5554 ret
= ext4_ext_remove_space(inode
, punch_start
, punch_stop
- 1);
5556 up_write(&EXT4_I(inode
)->i_data_sem
);
5559 ext4_discard_preallocations(inode
);
5561 ret
= ext4_ext_shift_extents(inode
, handle
, punch_stop
,
5562 punch_stop
- punch_start
, SHIFT_LEFT
);
5564 up_write(&EXT4_I(inode
)->i_data_sem
);
5568 new_size
= i_size_read(inode
) - len
;
5569 i_size_write(inode
, new_size
);
5570 EXT4_I(inode
)->i_disksize
= new_size
;
5572 up_write(&EXT4_I(inode
)->i_data_sem
);
5574 ext4_handle_sync(handle
);
5575 inode
->i_mtime
= inode
->i_ctime
= current_time(inode
);
5576 ext4_mark_inode_dirty(handle
, inode
);
5577 ext4_update_inode_fsync_trans(handle
, inode
, 1);
5580 ext4_journal_stop(handle
);
5582 up_write(&EXT4_I(inode
)->i_mmap_sem
);
5584 inode_unlock(inode
);
5589 * ext4_insert_range:
5590 * This function implements the FALLOC_FL_INSERT_RANGE flag of fallocate.
5591 * The data blocks starting from @offset to the EOF are shifted by @len
5592 * towards right to create a hole in the @inode. Inode size is increased
5594 * Returns 0 on success, error otherwise.
5596 int ext4_insert_range(struct inode
*inode
, loff_t offset
, loff_t len
)
5598 struct super_block
*sb
= inode
->i_sb
;
5600 struct ext4_ext_path
*path
;
5601 struct ext4_extent
*extent
;
5602 ext4_lblk_t offset_lblk
, len_lblk
, ee_start_lblk
= 0;
5603 unsigned int credits
, ee_len
;
5604 int ret
= 0, depth
, split_flag
= 0;
5608 * We need to test this early because xfstests assumes that an
5609 * insert range of (0, 1) will return EOPNOTSUPP if the file
5610 * system does not support insert range.
5612 if (!ext4_test_inode_flag(inode
, EXT4_INODE_EXTENTS
))
5615 /* Insert range works only on fs block size aligned offsets. */
5616 if (offset
& (EXT4_CLUSTER_SIZE(sb
) - 1) ||
5617 len
& (EXT4_CLUSTER_SIZE(sb
) - 1))
5620 if (!S_ISREG(inode
->i_mode
))
5623 trace_ext4_insert_range(inode
, offset
, len
);
5625 offset_lblk
= offset
>> EXT4_BLOCK_SIZE_BITS(sb
);
5626 len_lblk
= len
>> EXT4_BLOCK_SIZE_BITS(sb
);
5628 /* Call ext4_force_commit to flush all data in case of data=journal */
5629 if (ext4_should_journal_data(inode
)) {
5630 ret
= ext4_force_commit(inode
->i_sb
);
5636 /* Currently just for extent based files */
5637 if (!ext4_test_inode_flag(inode
, EXT4_INODE_EXTENTS
)) {
5642 /* Check for wrap through zero */
5643 if (inode
->i_size
+ len
> inode
->i_sb
->s_maxbytes
) {
5648 /* Offset should be less than i_size */
5649 if (offset
>= i_size_read(inode
)) {
5654 /* Wait for existing dio to complete */
5655 inode_dio_wait(inode
);
5658 * Prevent page faults from reinstantiating pages we have released from
5661 down_write(&EXT4_I(inode
)->i_mmap_sem
);
5663 ret
= ext4_break_layouts(inode
);
5668 * Need to round down to align start offset to page size boundary
5669 * for page size > block size.
5671 ioffset
= round_down(offset
, PAGE_SIZE
);
5672 /* Write out all dirty pages */
5673 ret
= filemap_write_and_wait_range(inode
->i_mapping
, ioffset
,
5677 truncate_pagecache(inode
, ioffset
);
5679 credits
= ext4_writepage_trans_blocks(inode
);
5680 handle
= ext4_journal_start(inode
, EXT4_HT_TRUNCATE
, credits
);
5681 if (IS_ERR(handle
)) {
5682 ret
= PTR_ERR(handle
);
5686 /* Expand file to avoid data loss if there is error while shifting */
5687 inode
->i_size
+= len
;
5688 EXT4_I(inode
)->i_disksize
+= len
;
5689 inode
->i_mtime
= inode
->i_ctime
= current_time(inode
);
5690 ret
= ext4_mark_inode_dirty(handle
, inode
);
5694 down_write(&EXT4_I(inode
)->i_data_sem
);
5695 ext4_discard_preallocations(inode
);
5697 path
= ext4_find_extent(inode
, offset_lblk
, NULL
, 0);
5699 up_write(&EXT4_I(inode
)->i_data_sem
);
5703 depth
= ext_depth(inode
);
5704 extent
= path
[depth
].p_ext
;
5706 ee_start_lblk
= le32_to_cpu(extent
->ee_block
);
5707 ee_len
= ext4_ext_get_actual_len(extent
);
5710 * If offset_lblk is not the starting block of extent, split
5711 * the extent @offset_lblk
5713 if ((offset_lblk
> ee_start_lblk
) &&
5714 (offset_lblk
< (ee_start_lblk
+ ee_len
))) {
5715 if (ext4_ext_is_unwritten(extent
))
5716 split_flag
= EXT4_EXT_MARK_UNWRIT1
|
5717 EXT4_EXT_MARK_UNWRIT2
;
5718 ret
= ext4_split_extent_at(handle
, inode
, &path
,
5719 offset_lblk
, split_flag
,
5721 EXT4_GET_BLOCKS_PRE_IO
|
5722 EXT4_GET_BLOCKS_METADATA_NOFAIL
);
5725 ext4_ext_drop_refs(path
);
5728 up_write(&EXT4_I(inode
)->i_data_sem
);
5732 ext4_ext_drop_refs(path
);
5736 ret
= ext4_es_remove_extent(inode
, offset_lblk
,
5737 EXT_MAX_BLOCKS
- offset_lblk
);
5739 up_write(&EXT4_I(inode
)->i_data_sem
);
5744 * if offset_lblk lies in a hole which is at start of file, use
5745 * ee_start_lblk to shift extents
5747 ret
= ext4_ext_shift_extents(inode
, handle
,
5748 ee_start_lblk
> offset_lblk
? ee_start_lblk
: offset_lblk
,
5749 len_lblk
, SHIFT_RIGHT
);
5751 up_write(&EXT4_I(inode
)->i_data_sem
);
5753 ext4_handle_sync(handle
);
5755 ext4_update_inode_fsync_trans(handle
, inode
, 1);
5758 ext4_journal_stop(handle
);
5760 up_write(&EXT4_I(inode
)->i_mmap_sem
);
5762 inode_unlock(inode
);
5767 * ext4_swap_extents - Swap extents between two inodes
5769 * @inode1: First inode
5770 * @inode2: Second inode
5771 * @lblk1: Start block for first inode
5772 * @lblk2: Start block for second inode
5773 * @count: Number of blocks to swap
5774 * @unwritten: Mark second inode's extents as unwritten after swap
5775 * @erp: Pointer to save error value
5777 * This helper routine does exactly what is promise "swap extents". All other
5778 * stuff such as page-cache locking consistency, bh mapping consistency or
5779 * extent's data copying must be performed by caller.
5781 * i_mutex is held for both inodes
5782 * i_data_sem is locked for write for both inodes
5784 * All pages from requested range are locked for both inodes
5787 ext4_swap_extents(handle_t
*handle
, struct inode
*inode1
,
5788 struct inode
*inode2
, ext4_lblk_t lblk1
, ext4_lblk_t lblk2
,
5789 ext4_lblk_t count
, int unwritten
, int *erp
)
5791 struct ext4_ext_path
*path1
= NULL
;
5792 struct ext4_ext_path
*path2
= NULL
;
5793 int replaced_count
= 0;
5795 BUG_ON(!rwsem_is_locked(&EXT4_I(inode1
)->i_data_sem
));
5796 BUG_ON(!rwsem_is_locked(&EXT4_I(inode2
)->i_data_sem
));
5797 BUG_ON(!inode_is_locked(inode1
));
5798 BUG_ON(!inode_is_locked(inode2
));
5800 *erp
= ext4_es_remove_extent(inode1
, lblk1
, count
);
5803 *erp
= ext4_es_remove_extent(inode2
, lblk2
, count
);
5808 struct ext4_extent
*ex1
, *ex2
, tmp_ex
;
5809 ext4_lblk_t e1_blk
, e2_blk
;
5810 int e1_len
, e2_len
, len
;
5813 path1
= ext4_find_extent(inode1
, lblk1
, NULL
, EXT4_EX_NOCACHE
);
5814 if (IS_ERR(path1
)) {
5815 *erp
= PTR_ERR(path1
);
5821 path2
= ext4_find_extent(inode2
, lblk2
, NULL
, EXT4_EX_NOCACHE
);
5822 if (IS_ERR(path2
)) {
5823 *erp
= PTR_ERR(path2
);
5827 ex1
= path1
[path1
->p_depth
].p_ext
;
5828 ex2
= path2
[path2
->p_depth
].p_ext
;
5829 /* Do we have somthing to swap ? */
5830 if (unlikely(!ex2
|| !ex1
))
5833 e1_blk
= le32_to_cpu(ex1
->ee_block
);
5834 e2_blk
= le32_to_cpu(ex2
->ee_block
);
5835 e1_len
= ext4_ext_get_actual_len(ex1
);
5836 e2_len
= ext4_ext_get_actual_len(ex2
);
5839 if (!in_range(lblk1
, e1_blk
, e1_len
) ||
5840 !in_range(lblk2
, e2_blk
, e2_len
)) {
5841 ext4_lblk_t next1
, next2
;
5843 /* if hole after extent, then go to next extent */
5844 next1
= ext4_ext_next_allocated_block(path1
);
5845 next2
= ext4_ext_next_allocated_block(path2
);
5846 /* If hole before extent, then shift to that extent */
5851 /* Do we have something to swap */
5852 if (next1
== EXT_MAX_BLOCKS
|| next2
== EXT_MAX_BLOCKS
)
5854 /* Move to the rightest boundary */
5855 len
= next1
- lblk1
;
5856 if (len
< next2
- lblk2
)
5857 len
= next2
- lblk2
;
5866 /* Prepare left boundary */
5867 if (e1_blk
< lblk1
) {
5869 *erp
= ext4_force_split_extent_at(handle
, inode1
,
5874 if (e2_blk
< lblk2
) {
5876 *erp
= ext4_force_split_extent_at(handle
, inode2
,
5881 /* ext4_split_extent_at() may result in leaf extent split,
5882 * path must to be revalidated. */
5886 /* Prepare right boundary */
5888 if (len
> e1_blk
+ e1_len
- lblk1
)
5889 len
= e1_blk
+ e1_len
- lblk1
;
5890 if (len
> e2_blk
+ e2_len
- lblk2
)
5891 len
= e2_blk
+ e2_len
- lblk2
;
5893 if (len
!= e1_len
) {
5895 *erp
= ext4_force_split_extent_at(handle
, inode1
,
5896 &path1
, lblk1
+ len
, 0);
5900 if (len
!= e2_len
) {
5902 *erp
= ext4_force_split_extent_at(handle
, inode2
,
5903 &path2
, lblk2
+ len
, 0);
5907 /* ext4_split_extent_at() may result in leaf extent split,
5908 * path must to be revalidated. */
5912 BUG_ON(e2_len
!= e1_len
);
5913 *erp
= ext4_ext_get_access(handle
, inode1
, path1
+ path1
->p_depth
);
5916 *erp
= ext4_ext_get_access(handle
, inode2
, path2
+ path2
->p_depth
);
5920 /* Both extents are fully inside boundaries. Swap it now */
5922 ext4_ext_store_pblock(ex1
, ext4_ext_pblock(ex2
));
5923 ext4_ext_store_pblock(ex2
, ext4_ext_pblock(&tmp_ex
));
5924 ex1
->ee_len
= cpu_to_le16(e2_len
);
5925 ex2
->ee_len
= cpu_to_le16(e1_len
);
5927 ext4_ext_mark_unwritten(ex2
);
5928 if (ext4_ext_is_unwritten(&tmp_ex
))
5929 ext4_ext_mark_unwritten(ex1
);
5931 ext4_ext_try_to_merge(handle
, inode2
, path2
, ex2
);
5932 ext4_ext_try_to_merge(handle
, inode1
, path1
, ex1
);
5933 *erp
= ext4_ext_dirty(handle
, inode2
, path2
+
5937 *erp
= ext4_ext_dirty(handle
, inode1
, path1
+
5940 * Looks scarry ah..? second inode already points to new blocks,
5941 * and it was successfully dirtied. But luckily error may happen
5942 * only due to journal error, so full transaction will be
5949 replaced_count
+= len
;
5953 ext4_ext_drop_refs(path1
);
5955 ext4_ext_drop_refs(path2
);
5957 path1
= path2
= NULL
;
5959 return replaced_count
;