2 * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
3 * Written by Alex Tomas <alex@clusterfs.com>
5 * Architecture independence:
6 * Copyright (c) 2005, Bull S.A.
7 * Written by Pierre Peiffer <pierre.peiffer@bull.net>
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License version 2 as
11 * published by the Free Software Foundation.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public Licens
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-
24 * Extents support for EXT4
27 * - ext4*_error() should be used in some situations
28 * - analyze all BUG()/BUG_ON(), use -EIO where appropriate
29 * - smart tree reduction
32 #include <linux/module.h>
34 #include <linux/time.h>
35 #include <linux/jbd2.h>
36 #include <linux/highuid.h>
37 #include <linux/pagemap.h>
38 #include <linux/quotaops.h>
39 #include <linux/string.h>
40 #include <linux/slab.h>
41 #include <linux/falloc.h>
42 #include <asm/uaccess.h>
43 #include <linux/fiemap.h>
44 #include "ext4_jbd2.h"
45 #include "ext4_extents.h"
50 * combine low and high parts of physical block number into ext4_fsblk_t
52 ext4_fsblk_t
ext_pblock(struct ext4_extent
*ex
)
56 block
= le32_to_cpu(ex
->ee_start_lo
);
57 block
|= ((ext4_fsblk_t
) le16_to_cpu(ex
->ee_start_hi
) << 31) << 1;
63 * combine low and high parts of a leaf physical block number into ext4_fsblk_t
65 ext4_fsblk_t
idx_pblock(struct ext4_extent_idx
*ix
)
69 block
= le32_to_cpu(ix
->ei_leaf_lo
);
70 block
|= ((ext4_fsblk_t
) le16_to_cpu(ix
->ei_leaf_hi
) << 31) << 1;
75 * ext4_ext_store_pblock:
76 * stores a large physical block number into an extent struct,
77 * breaking it into parts
79 void ext4_ext_store_pblock(struct ext4_extent
*ex
, ext4_fsblk_t pb
)
81 ex
->ee_start_lo
= cpu_to_le32((unsigned long) (pb
& 0xffffffff));
82 ex
->ee_start_hi
= cpu_to_le16((unsigned long) ((pb
>> 31) >> 1) & 0xffff);
86 * ext4_idx_store_pblock:
87 * stores a large physical block number into an index struct,
88 * breaking it into parts
90 static void ext4_idx_store_pblock(struct ext4_extent_idx
*ix
, ext4_fsblk_t pb
)
92 ix
->ei_leaf_lo
= cpu_to_le32((unsigned long) (pb
& 0xffffffff));
93 ix
->ei_leaf_hi
= cpu_to_le16((unsigned long) ((pb
>> 31) >> 1) & 0xffff);
96 static int ext4_ext_truncate_extend_restart(handle_t
*handle
,
102 if (!ext4_handle_valid(handle
))
104 if (handle
->h_buffer_credits
> needed
)
106 err
= ext4_journal_extend(handle
, needed
);
109 err
= ext4_truncate_restart_trans(handle
, inode
, needed
);
121 static int ext4_ext_get_access(handle_t
*handle
, struct inode
*inode
,
122 struct ext4_ext_path
*path
)
125 /* path points to block */
126 return ext4_journal_get_write_access(handle
, path
->p_bh
);
128 /* path points to leaf/index in inode body */
129 /* we use in-core data, no need to protect them */
139 static int ext4_ext_dirty(handle_t
*handle
, struct inode
*inode
,
140 struct ext4_ext_path
*path
)
144 /* path points to block */
145 err
= ext4_handle_dirty_metadata(handle
, inode
, path
->p_bh
);
147 /* path points to leaf/index in inode body */
148 err
= ext4_mark_inode_dirty(handle
, inode
);
153 static ext4_fsblk_t
ext4_ext_find_goal(struct inode
*inode
,
154 struct ext4_ext_path
*path
,
157 struct ext4_inode_info
*ei
= EXT4_I(inode
);
158 ext4_fsblk_t bg_start
;
159 ext4_fsblk_t last_block
;
160 ext4_grpblk_t colour
;
161 ext4_group_t block_group
;
162 int flex_size
= ext4_flex_bg_size(EXT4_SB(inode
->i_sb
));
166 struct ext4_extent
*ex
;
167 depth
= path
->p_depth
;
169 /* try to predict block placement */
170 ex
= path
[depth
].p_ext
;
172 return ext_pblock(ex
)+(block
-le32_to_cpu(ex
->ee_block
));
174 /* it looks like index is empty;
175 * try to find starting block from index itself */
176 if (path
[depth
].p_bh
)
177 return path
[depth
].p_bh
->b_blocknr
;
180 /* OK. use inode's group */
181 block_group
= ei
->i_block_group
;
182 if (flex_size
>= EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME
) {
184 * If there are at least EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME
185 * block groups per flexgroup, reserve the first block
186 * group for directories and special files. Regular
187 * files will start at the second block group. This
188 * tends to speed up directory access and improves
191 block_group
&= ~(flex_size
-1);
192 if (S_ISREG(inode
->i_mode
))
195 bg_start
= ext4_group_first_block_no(inode
->i_sb
, block_group
);
196 last_block
= ext4_blocks_count(EXT4_SB(inode
->i_sb
)->s_es
) - 1;
199 * If we are doing delayed allocation, we don't need take
200 * colour into account.
202 if (test_opt(inode
->i_sb
, DELALLOC
))
205 if (bg_start
+ EXT4_BLOCKS_PER_GROUP(inode
->i_sb
) <= last_block
)
206 colour
= (current
->pid
% 16) *
207 (EXT4_BLOCKS_PER_GROUP(inode
->i_sb
) / 16);
209 colour
= (current
->pid
% 16) * ((last_block
- bg_start
) / 16);
210 return bg_start
+ colour
+ block
;
214 * Allocation for a meta data block
217 ext4_ext_new_meta_block(handle_t
*handle
, struct inode
*inode
,
218 struct ext4_ext_path
*path
,
219 struct ext4_extent
*ex
, int *err
)
221 ext4_fsblk_t goal
, newblock
;
223 goal
= ext4_ext_find_goal(inode
, path
, le32_to_cpu(ex
->ee_block
));
224 newblock
= ext4_new_meta_blocks(handle
, inode
, goal
, NULL
, err
);
228 static inline int ext4_ext_space_block(struct inode
*inode
, int check
)
232 size
= (inode
->i_sb
->s_blocksize
- sizeof(struct ext4_extent_header
))
233 / sizeof(struct ext4_extent
);
235 #ifdef AGGRESSIVE_TEST
243 static inline int ext4_ext_space_block_idx(struct inode
*inode
, int check
)
247 size
= (inode
->i_sb
->s_blocksize
- sizeof(struct ext4_extent_header
))
248 / sizeof(struct ext4_extent_idx
);
250 #ifdef AGGRESSIVE_TEST
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
);
266 #ifdef AGGRESSIVE_TEST
274 static inline int ext4_ext_space_root_idx(struct inode
*inode
, int check
)
278 size
= sizeof(EXT4_I(inode
)->i_data
);
279 size
-= sizeof(struct ext4_extent_header
);
280 size
/= sizeof(struct ext4_extent_idx
);
282 #ifdef AGGRESSIVE_TEST
291 * Calculate the number of metadata blocks needed
292 * to allocate @blocks
293 * Worse case is one block per extent
295 int ext4_ext_calc_metadata_amount(struct inode
*inode
, sector_t lblock
)
297 struct ext4_inode_info
*ei
= EXT4_I(inode
);
300 idxs
= ((inode
->i_sb
->s_blocksize
- sizeof(struct ext4_extent_header
))
301 / sizeof(struct ext4_extent_idx
));
304 * If the new delayed allocation block is contiguous with the
305 * previous da block, it can share index blocks with the
306 * previous block, so we only need to allocate a new index
307 * block every idxs leaf blocks. At ldxs**2 blocks, we need
308 * an additional index block, and at ldxs**3 blocks, yet
309 * another index blocks.
311 if (ei
->i_da_metadata_calc_len
&&
312 ei
->i_da_metadata_calc_last_lblock
+1 == lblock
) {
313 if ((ei
->i_da_metadata_calc_len
% idxs
) == 0)
315 if ((ei
->i_da_metadata_calc_len
% (idxs
*idxs
)) == 0)
317 if ((ei
->i_da_metadata_calc_len
% (idxs
*idxs
*idxs
)) == 0) {
319 ei
->i_da_metadata_calc_len
= 0;
321 ei
->i_da_metadata_calc_len
++;
322 ei
->i_da_metadata_calc_last_lblock
++;
327 * In the worst case we need a new set of index blocks at
328 * every level of the inode's extent tree.
330 ei
->i_da_metadata_calc_len
= 1;
331 ei
->i_da_metadata_calc_last_lblock
= lblock
;
332 return ext_depth(inode
) + 1;
336 ext4_ext_max_entries(struct inode
*inode
, int depth
)
340 if (depth
== ext_depth(inode
)) {
342 max
= ext4_ext_space_root(inode
, 1);
344 max
= ext4_ext_space_root_idx(inode
, 1);
347 max
= ext4_ext_space_block(inode
, 1);
349 max
= ext4_ext_space_block_idx(inode
, 1);
355 static int ext4_valid_extent(struct inode
*inode
, struct ext4_extent
*ext
)
357 ext4_fsblk_t block
= ext_pblock(ext
);
358 int len
= ext4_ext_get_actual_len(ext
);
360 return ext4_data_block_valid(EXT4_SB(inode
->i_sb
), block
, len
);
363 static int ext4_valid_extent_idx(struct inode
*inode
,
364 struct ext4_extent_idx
*ext_idx
)
366 ext4_fsblk_t block
= idx_pblock(ext_idx
);
368 return ext4_data_block_valid(EXT4_SB(inode
->i_sb
), block
, 1);
371 static int ext4_valid_extent_entries(struct inode
*inode
,
372 struct ext4_extent_header
*eh
,
375 struct ext4_extent
*ext
;
376 struct ext4_extent_idx
*ext_idx
;
377 unsigned short entries
;
378 if (eh
->eh_entries
== 0)
381 entries
= le16_to_cpu(eh
->eh_entries
);
385 ext
= EXT_FIRST_EXTENT(eh
);
387 if (!ext4_valid_extent(inode
, ext
))
393 ext_idx
= EXT_FIRST_INDEX(eh
);
395 if (!ext4_valid_extent_idx(inode
, ext_idx
))
404 static int __ext4_ext_check(const char *function
, struct inode
*inode
,
405 struct ext4_extent_header
*eh
,
408 const char *error_msg
;
411 if (unlikely(eh
->eh_magic
!= EXT4_EXT_MAGIC
)) {
412 error_msg
= "invalid magic";
415 if (unlikely(le16_to_cpu(eh
->eh_depth
) != depth
)) {
416 error_msg
= "unexpected eh_depth";
419 if (unlikely(eh
->eh_max
== 0)) {
420 error_msg
= "invalid eh_max";
423 max
= ext4_ext_max_entries(inode
, depth
);
424 if (unlikely(le16_to_cpu(eh
->eh_max
) > max
)) {
425 error_msg
= "too large eh_max";
428 if (unlikely(le16_to_cpu(eh
->eh_entries
) > le16_to_cpu(eh
->eh_max
))) {
429 error_msg
= "invalid eh_entries";
432 if (!ext4_valid_extent_entries(inode
, eh
, depth
)) {
433 error_msg
= "invalid extent entries";
439 __ext4_error(inode
->i_sb
, function
,
440 "bad header/extent in inode #%lu: %s - magic %x, "
441 "entries %u, max %u(%u), depth %u(%u)",
442 inode
->i_ino
, error_msg
, le16_to_cpu(eh
->eh_magic
),
443 le16_to_cpu(eh
->eh_entries
), le16_to_cpu(eh
->eh_max
),
444 max
, le16_to_cpu(eh
->eh_depth
), depth
);
449 #define ext4_ext_check(inode, eh, depth) \
450 __ext4_ext_check(__func__, inode, eh, depth)
452 int ext4_ext_check_inode(struct inode
*inode
)
454 return ext4_ext_check(inode
, ext_inode_hdr(inode
), ext_depth(inode
));
458 static void ext4_ext_show_path(struct inode
*inode
, struct ext4_ext_path
*path
)
460 int k
, l
= path
->p_depth
;
463 for (k
= 0; k
<= l
; k
++, path
++) {
465 ext_debug(" %d->%llu", le32_to_cpu(path
->p_idx
->ei_block
),
466 idx_pblock(path
->p_idx
));
467 } else if (path
->p_ext
) {
468 ext_debug(" %d:[%d]%d:%llu ",
469 le32_to_cpu(path
->p_ext
->ee_block
),
470 ext4_ext_is_uninitialized(path
->p_ext
),
471 ext4_ext_get_actual_len(path
->p_ext
),
472 ext_pblock(path
->p_ext
));
479 static void ext4_ext_show_leaf(struct inode
*inode
, struct ext4_ext_path
*path
)
481 int depth
= ext_depth(inode
);
482 struct ext4_extent_header
*eh
;
483 struct ext4_extent
*ex
;
489 eh
= path
[depth
].p_hdr
;
490 ex
= EXT_FIRST_EXTENT(eh
);
492 ext_debug("Displaying leaf extents for inode %lu\n", inode
->i_ino
);
494 for (i
= 0; i
< le16_to_cpu(eh
->eh_entries
); i
++, ex
++) {
495 ext_debug("%d:[%d]%d:%llu ", le32_to_cpu(ex
->ee_block
),
496 ext4_ext_is_uninitialized(ex
),
497 ext4_ext_get_actual_len(ex
), ext_pblock(ex
));
502 #define ext4_ext_show_path(inode, path)
503 #define ext4_ext_show_leaf(inode, path)
506 void ext4_ext_drop_refs(struct ext4_ext_path
*path
)
508 int depth
= path
->p_depth
;
511 for (i
= 0; i
<= depth
; i
++, path
++)
519 * ext4_ext_binsearch_idx:
520 * binary search for the closest index of the given block
521 * the header must be checked before calling this
524 ext4_ext_binsearch_idx(struct inode
*inode
,
525 struct ext4_ext_path
*path
, ext4_lblk_t block
)
527 struct ext4_extent_header
*eh
= path
->p_hdr
;
528 struct ext4_extent_idx
*r
, *l
, *m
;
531 ext_debug("binsearch for %u(idx): ", block
);
533 l
= EXT_FIRST_INDEX(eh
) + 1;
534 r
= EXT_LAST_INDEX(eh
);
537 if (block
< le32_to_cpu(m
->ei_block
))
541 ext_debug("%p(%u):%p(%u):%p(%u) ", l
, le32_to_cpu(l
->ei_block
),
542 m
, le32_to_cpu(m
->ei_block
),
543 r
, le32_to_cpu(r
->ei_block
));
547 ext_debug(" -> %d->%lld ", le32_to_cpu(path
->p_idx
->ei_block
),
548 idx_pblock(path
->p_idx
));
550 #ifdef CHECK_BINSEARCH
552 struct ext4_extent_idx
*chix
, *ix
;
555 chix
= ix
= EXT_FIRST_INDEX(eh
);
556 for (k
= 0; k
< le16_to_cpu(eh
->eh_entries
); k
++, ix
++) {
558 le32_to_cpu(ix
->ei_block
) <= le32_to_cpu(ix
[-1].ei_block
)) {
559 printk(KERN_DEBUG
"k=%d, ix=0x%p, "
561 ix
, EXT_FIRST_INDEX(eh
));
562 printk(KERN_DEBUG
"%u <= %u\n",
563 le32_to_cpu(ix
->ei_block
),
564 le32_to_cpu(ix
[-1].ei_block
));
566 BUG_ON(k
&& le32_to_cpu(ix
->ei_block
)
567 <= le32_to_cpu(ix
[-1].ei_block
));
568 if (block
< le32_to_cpu(ix
->ei_block
))
572 BUG_ON(chix
!= path
->p_idx
);
579 * ext4_ext_binsearch:
580 * binary search for closest extent of the given block
581 * the header must be checked before calling this
584 ext4_ext_binsearch(struct inode
*inode
,
585 struct ext4_ext_path
*path
, ext4_lblk_t block
)
587 struct ext4_extent_header
*eh
= path
->p_hdr
;
588 struct ext4_extent
*r
, *l
, *m
;
590 if (eh
->eh_entries
== 0) {
592 * this leaf is empty:
593 * we get such a leaf in split/add case
598 ext_debug("binsearch for %u: ", block
);
600 l
= EXT_FIRST_EXTENT(eh
) + 1;
601 r
= EXT_LAST_EXTENT(eh
);
605 if (block
< le32_to_cpu(m
->ee_block
))
609 ext_debug("%p(%u):%p(%u):%p(%u) ", l
, le32_to_cpu(l
->ee_block
),
610 m
, le32_to_cpu(m
->ee_block
),
611 r
, le32_to_cpu(r
->ee_block
));
615 ext_debug(" -> %d:%llu:[%d]%d ",
616 le32_to_cpu(path
->p_ext
->ee_block
),
617 ext_pblock(path
->p_ext
),
618 ext4_ext_is_uninitialized(path
->p_ext
),
619 ext4_ext_get_actual_len(path
->p_ext
));
621 #ifdef CHECK_BINSEARCH
623 struct ext4_extent
*chex
, *ex
;
626 chex
= ex
= EXT_FIRST_EXTENT(eh
);
627 for (k
= 0; k
< le16_to_cpu(eh
->eh_entries
); k
++, ex
++) {
628 BUG_ON(k
&& le32_to_cpu(ex
->ee_block
)
629 <= le32_to_cpu(ex
[-1].ee_block
));
630 if (block
< le32_to_cpu(ex
->ee_block
))
634 BUG_ON(chex
!= path
->p_ext
);
640 int ext4_ext_tree_init(handle_t
*handle
, struct inode
*inode
)
642 struct ext4_extent_header
*eh
;
644 eh
= ext_inode_hdr(inode
);
647 eh
->eh_magic
= EXT4_EXT_MAGIC
;
648 eh
->eh_max
= cpu_to_le16(ext4_ext_space_root(inode
, 0));
649 ext4_mark_inode_dirty(handle
, inode
);
650 ext4_ext_invalidate_cache(inode
);
654 struct ext4_ext_path
*
655 ext4_ext_find_extent(struct inode
*inode
, ext4_lblk_t block
,
656 struct ext4_ext_path
*path
)
658 struct ext4_extent_header
*eh
;
659 struct buffer_head
*bh
;
660 short int depth
, i
, ppos
= 0, alloc
= 0;
662 eh
= ext_inode_hdr(inode
);
663 depth
= ext_depth(inode
);
665 /* account possible depth increase */
667 path
= kzalloc(sizeof(struct ext4_ext_path
) * (depth
+ 2),
670 return ERR_PTR(-ENOMEM
);
677 /* walk through the tree */
679 int need_to_validate
= 0;
681 ext_debug("depth %d: num %d, max %d\n",
682 ppos
, le16_to_cpu(eh
->eh_entries
), le16_to_cpu(eh
->eh_max
));
684 ext4_ext_binsearch_idx(inode
, path
+ ppos
, block
);
685 path
[ppos
].p_block
= idx_pblock(path
[ppos
].p_idx
);
686 path
[ppos
].p_depth
= i
;
687 path
[ppos
].p_ext
= NULL
;
689 bh
= sb_getblk(inode
->i_sb
, path
[ppos
].p_block
);
692 if (!bh_uptodate_or_lock(bh
)) {
693 if (bh_submit_read(bh
) < 0) {
697 /* validate the extent entries */
698 need_to_validate
= 1;
700 eh
= ext_block_hdr(bh
);
702 if (unlikely(ppos
> depth
)) {
704 EXT4_ERROR_INODE(inode
,
705 "ppos %d > depth %d", ppos
, depth
);
708 path
[ppos
].p_bh
= bh
;
709 path
[ppos
].p_hdr
= eh
;
712 if (need_to_validate
&& ext4_ext_check(inode
, eh
, i
))
716 path
[ppos
].p_depth
= i
;
717 path
[ppos
].p_ext
= NULL
;
718 path
[ppos
].p_idx
= NULL
;
721 ext4_ext_binsearch(inode
, path
+ ppos
, block
);
722 /* if not an empty leaf */
723 if (path
[ppos
].p_ext
)
724 path
[ppos
].p_block
= ext_pblock(path
[ppos
].p_ext
);
726 ext4_ext_show_path(inode
, path
);
731 ext4_ext_drop_refs(path
);
734 return ERR_PTR(-EIO
);
738 * ext4_ext_insert_index:
739 * insert new index [@logical;@ptr] into the block at @curp;
740 * check where to insert: before @curp or after @curp
742 int ext4_ext_insert_index(handle_t
*handle
, struct inode
*inode
,
743 struct ext4_ext_path
*curp
,
744 int logical
, ext4_fsblk_t ptr
)
746 struct ext4_extent_idx
*ix
;
749 err
= ext4_ext_get_access(handle
, inode
, curp
);
753 if (unlikely(logical
== le32_to_cpu(curp
->p_idx
->ei_block
))) {
754 EXT4_ERROR_INODE(inode
,
755 "logical %d == ei_block %d!",
756 logical
, le32_to_cpu(curp
->p_idx
->ei_block
));
759 len
= EXT_MAX_INDEX(curp
->p_hdr
) - curp
->p_idx
;
760 if (logical
> le32_to_cpu(curp
->p_idx
->ei_block
)) {
762 if (curp
->p_idx
!= EXT_LAST_INDEX(curp
->p_hdr
)) {
763 len
= (len
- 1) * sizeof(struct ext4_extent_idx
);
764 len
= len
< 0 ? 0 : len
;
765 ext_debug("insert new index %d after: %llu. "
766 "move %d from 0x%p to 0x%p\n",
768 (curp
->p_idx
+ 1), (curp
->p_idx
+ 2));
769 memmove(curp
->p_idx
+ 2, curp
->p_idx
+ 1, len
);
771 ix
= curp
->p_idx
+ 1;
774 len
= len
* sizeof(struct ext4_extent_idx
);
775 len
= len
< 0 ? 0 : len
;
776 ext_debug("insert new index %d before: %llu. "
777 "move %d from 0x%p to 0x%p\n",
779 curp
->p_idx
, (curp
->p_idx
+ 1));
780 memmove(curp
->p_idx
+ 1, curp
->p_idx
, len
);
784 ix
->ei_block
= cpu_to_le32(logical
);
785 ext4_idx_store_pblock(ix
, ptr
);
786 le16_add_cpu(&curp
->p_hdr
->eh_entries
, 1);
788 if (unlikely(le16_to_cpu(curp
->p_hdr
->eh_entries
)
789 > le16_to_cpu(curp
->p_hdr
->eh_max
))) {
790 EXT4_ERROR_INODE(inode
,
791 "logical %d == ei_block %d!",
792 logical
, le32_to_cpu(curp
->p_idx
->ei_block
));
795 if (unlikely(ix
> EXT_LAST_INDEX(curp
->p_hdr
))) {
796 EXT4_ERROR_INODE(inode
, "ix > EXT_LAST_INDEX!");
800 err
= ext4_ext_dirty(handle
, inode
, curp
);
801 ext4_std_error(inode
->i_sb
, err
);
808 * inserts new subtree into the path, using free index entry
810 * - allocates all needed blocks (new leaf and all intermediate index blocks)
811 * - makes decision where to split
812 * - moves remaining extents and index entries (right to the split point)
813 * into the newly allocated blocks
814 * - initializes subtree
816 static int ext4_ext_split(handle_t
*handle
, struct inode
*inode
,
817 struct ext4_ext_path
*path
,
818 struct ext4_extent
*newext
, int at
)
820 struct buffer_head
*bh
= NULL
;
821 int depth
= ext_depth(inode
);
822 struct ext4_extent_header
*neh
;
823 struct ext4_extent_idx
*fidx
;
824 struct ext4_extent
*ex
;
826 ext4_fsblk_t newblock
, oldblock
;
828 ext4_fsblk_t
*ablocks
= NULL
; /* array of allocated blocks */
831 /* make decision: where to split? */
832 /* FIXME: now decision is simplest: at current extent */
834 /* if current leaf will be split, then we should use
835 * border from split point */
836 if (unlikely(path
[depth
].p_ext
> EXT_MAX_EXTENT(path
[depth
].p_hdr
))) {
837 EXT4_ERROR_INODE(inode
, "p_ext > EXT_MAX_EXTENT!");
840 if (path
[depth
].p_ext
!= EXT_MAX_EXTENT(path
[depth
].p_hdr
)) {
841 border
= path
[depth
].p_ext
[1].ee_block
;
842 ext_debug("leaf will be split."
843 " next leaf starts at %d\n",
844 le32_to_cpu(border
));
846 border
= newext
->ee_block
;
847 ext_debug("leaf will be added."
848 " next leaf starts at %d\n",
849 le32_to_cpu(border
));
853 * If error occurs, then we break processing
854 * and mark filesystem read-only. index won't
855 * be inserted and tree will be in consistent
856 * state. Next mount will repair buffers too.
860 * Get array to track all allocated blocks.
861 * We need this to handle errors and free blocks
864 ablocks
= kzalloc(sizeof(ext4_fsblk_t
) * depth
, GFP_NOFS
);
868 /* allocate all needed blocks */
869 ext_debug("allocate %d blocks for indexes/leaf\n", depth
- at
);
870 for (a
= 0; a
< depth
- at
; a
++) {
871 newblock
= ext4_ext_new_meta_block(handle
, inode
, path
,
875 ablocks
[a
] = newblock
;
878 /* initialize new leaf */
879 newblock
= ablocks
[--a
];
880 if (unlikely(newblock
== 0)) {
881 EXT4_ERROR_INODE(inode
, "newblock == 0!");
885 bh
= sb_getblk(inode
->i_sb
, newblock
);
892 err
= ext4_journal_get_create_access(handle
, bh
);
896 neh
= ext_block_hdr(bh
);
898 neh
->eh_max
= cpu_to_le16(ext4_ext_space_block(inode
, 0));
899 neh
->eh_magic
= EXT4_EXT_MAGIC
;
901 ex
= EXT_FIRST_EXTENT(neh
);
903 /* move remainder of path[depth] to the new leaf */
904 if (unlikely(path
[depth
].p_hdr
->eh_entries
!=
905 path
[depth
].p_hdr
->eh_max
)) {
906 EXT4_ERROR_INODE(inode
, "eh_entries %d != eh_max %d!",
907 path
[depth
].p_hdr
->eh_entries
,
908 path
[depth
].p_hdr
->eh_max
);
912 /* start copy from next extent */
913 /* TODO: we could do it by single memmove */
916 while (path
[depth
].p_ext
<=
917 EXT_MAX_EXTENT(path
[depth
].p_hdr
)) {
918 ext_debug("move %d:%llu:[%d]%d in new leaf %llu\n",
919 le32_to_cpu(path
[depth
].p_ext
->ee_block
),
920 ext_pblock(path
[depth
].p_ext
),
921 ext4_ext_is_uninitialized(path
[depth
].p_ext
),
922 ext4_ext_get_actual_len(path
[depth
].p_ext
),
924 /*memmove(ex++, path[depth].p_ext++,
925 sizeof(struct ext4_extent));
931 memmove(ex
, path
[depth
].p_ext
-m
, sizeof(struct ext4_extent
)*m
);
932 le16_add_cpu(&neh
->eh_entries
, m
);
935 set_buffer_uptodate(bh
);
938 err
= ext4_handle_dirty_metadata(handle
, inode
, bh
);
944 /* correct old leaf */
946 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
949 le16_add_cpu(&path
[depth
].p_hdr
->eh_entries
, -m
);
950 err
= ext4_ext_dirty(handle
, inode
, path
+ depth
);
956 /* create intermediate indexes */
958 if (unlikely(k
< 0)) {
959 EXT4_ERROR_INODE(inode
, "k %d < 0!", k
);
964 ext_debug("create %d intermediate indices\n", k
);
965 /* insert new index into current index block */
966 /* current depth stored in i var */
970 newblock
= ablocks
[--a
];
971 bh
= sb_getblk(inode
->i_sb
, newblock
);
978 err
= ext4_journal_get_create_access(handle
, bh
);
982 neh
= ext_block_hdr(bh
);
983 neh
->eh_entries
= cpu_to_le16(1);
984 neh
->eh_magic
= EXT4_EXT_MAGIC
;
985 neh
->eh_max
= cpu_to_le16(ext4_ext_space_block_idx(inode
, 0));
986 neh
->eh_depth
= cpu_to_le16(depth
- i
);
987 fidx
= EXT_FIRST_INDEX(neh
);
988 fidx
->ei_block
= border
;
989 ext4_idx_store_pblock(fidx
, oldblock
);
991 ext_debug("int.index at %d (block %llu): %u -> %llu\n",
992 i
, newblock
, le32_to_cpu(border
), oldblock
);
997 ext_debug("cur 0x%p, last 0x%p\n", path
[i
].p_idx
,
998 EXT_MAX_INDEX(path
[i
].p_hdr
));
999 if (unlikely(EXT_MAX_INDEX(path
[i
].p_hdr
) !=
1000 EXT_LAST_INDEX(path
[i
].p_hdr
))) {
1001 EXT4_ERROR_INODE(inode
,
1002 "EXT_MAX_INDEX != EXT_LAST_INDEX ee_block %d!",
1003 le32_to_cpu(path
[i
].p_ext
->ee_block
));
1007 while (path
[i
].p_idx
<= EXT_MAX_INDEX(path
[i
].p_hdr
)) {
1008 ext_debug("%d: move %d:%llu in new index %llu\n", i
,
1009 le32_to_cpu(path
[i
].p_idx
->ei_block
),
1010 idx_pblock(path
[i
].p_idx
),
1012 /*memmove(++fidx, path[i].p_idx++,
1013 sizeof(struct ext4_extent_idx));
1015 BUG_ON(neh->eh_entries > neh->eh_max);*/
1020 memmove(++fidx
, path
[i
].p_idx
- m
,
1021 sizeof(struct ext4_extent_idx
) * m
);
1022 le16_add_cpu(&neh
->eh_entries
, m
);
1024 set_buffer_uptodate(bh
);
1027 err
= ext4_handle_dirty_metadata(handle
, inode
, bh
);
1033 /* correct old index */
1035 err
= ext4_ext_get_access(handle
, inode
, path
+ i
);
1038 le16_add_cpu(&path
[i
].p_hdr
->eh_entries
, -m
);
1039 err
= ext4_ext_dirty(handle
, inode
, path
+ i
);
1047 /* insert new index */
1048 err
= ext4_ext_insert_index(handle
, inode
, path
+ at
,
1049 le32_to_cpu(border
), newblock
);
1053 if (buffer_locked(bh
))
1059 /* free all allocated blocks in error case */
1060 for (i
= 0; i
< depth
; i
++) {
1063 ext4_free_blocks(handle
, inode
, 0, ablocks
[i
], 1,
1064 EXT4_FREE_BLOCKS_METADATA
);
1073 * ext4_ext_grow_indepth:
1074 * implements tree growing procedure:
1075 * - allocates new block
1076 * - moves top-level data (index block or leaf) into the new block
1077 * - initializes new top-level, creating index that points to the
1078 * just created block
1080 static int ext4_ext_grow_indepth(handle_t
*handle
, struct inode
*inode
,
1081 struct ext4_ext_path
*path
,
1082 struct ext4_extent
*newext
)
1084 struct ext4_ext_path
*curp
= path
;
1085 struct ext4_extent_header
*neh
;
1086 struct ext4_extent_idx
*fidx
;
1087 struct buffer_head
*bh
;
1088 ext4_fsblk_t newblock
;
1091 newblock
= ext4_ext_new_meta_block(handle
, inode
, path
, newext
, &err
);
1095 bh
= sb_getblk(inode
->i_sb
, newblock
);
1098 ext4_std_error(inode
->i_sb
, err
);
1103 err
= ext4_journal_get_create_access(handle
, bh
);
1109 /* move top-level index/leaf into new block */
1110 memmove(bh
->b_data
, curp
->p_hdr
, sizeof(EXT4_I(inode
)->i_data
));
1112 /* set size of new block */
1113 neh
= ext_block_hdr(bh
);
1114 /* old root could have indexes or leaves
1115 * so calculate e_max right way */
1116 if (ext_depth(inode
))
1117 neh
->eh_max
= cpu_to_le16(ext4_ext_space_block_idx(inode
, 0));
1119 neh
->eh_max
= cpu_to_le16(ext4_ext_space_block(inode
, 0));
1120 neh
->eh_magic
= EXT4_EXT_MAGIC
;
1121 set_buffer_uptodate(bh
);
1124 err
= ext4_handle_dirty_metadata(handle
, inode
, bh
);
1128 /* create index in new top-level index: num,max,pointer */
1129 err
= ext4_ext_get_access(handle
, inode
, curp
);
1133 curp
->p_hdr
->eh_magic
= EXT4_EXT_MAGIC
;
1134 curp
->p_hdr
->eh_max
= cpu_to_le16(ext4_ext_space_root_idx(inode
, 0));
1135 curp
->p_hdr
->eh_entries
= cpu_to_le16(1);
1136 curp
->p_idx
= EXT_FIRST_INDEX(curp
->p_hdr
);
1138 if (path
[0].p_hdr
->eh_depth
)
1139 curp
->p_idx
->ei_block
=
1140 EXT_FIRST_INDEX(path
[0].p_hdr
)->ei_block
;
1142 curp
->p_idx
->ei_block
=
1143 EXT_FIRST_EXTENT(path
[0].p_hdr
)->ee_block
;
1144 ext4_idx_store_pblock(curp
->p_idx
, newblock
);
1146 neh
= ext_inode_hdr(inode
);
1147 fidx
= EXT_FIRST_INDEX(neh
);
1148 ext_debug("new root: num %d(%d), lblock %d, ptr %llu\n",
1149 le16_to_cpu(neh
->eh_entries
), le16_to_cpu(neh
->eh_max
),
1150 le32_to_cpu(fidx
->ei_block
), idx_pblock(fidx
));
1152 neh
->eh_depth
= cpu_to_le16(path
->p_depth
+ 1);
1153 err
= ext4_ext_dirty(handle
, inode
, curp
);
1161 * ext4_ext_create_new_leaf:
1162 * finds empty index and adds new leaf.
1163 * if no free index is found, then it requests in-depth growing.
1165 static int ext4_ext_create_new_leaf(handle_t
*handle
, struct inode
*inode
,
1166 struct ext4_ext_path
*path
,
1167 struct ext4_extent
*newext
)
1169 struct ext4_ext_path
*curp
;
1170 int depth
, i
, err
= 0;
1173 i
= depth
= ext_depth(inode
);
1175 /* walk up to the tree and look for free index entry */
1176 curp
= path
+ depth
;
1177 while (i
> 0 && !EXT_HAS_FREE_INDEX(curp
)) {
1182 /* we use already allocated block for index block,
1183 * so subsequent data blocks should be contiguous */
1184 if (EXT_HAS_FREE_INDEX(curp
)) {
1185 /* if we found index with free entry, then use that
1186 * entry: create all needed subtree and add new leaf */
1187 err
= ext4_ext_split(handle
, inode
, path
, newext
, i
);
1192 ext4_ext_drop_refs(path
);
1193 path
= ext4_ext_find_extent(inode
,
1194 (ext4_lblk_t
)le32_to_cpu(newext
->ee_block
),
1197 err
= PTR_ERR(path
);
1199 /* tree is full, time to grow in depth */
1200 err
= ext4_ext_grow_indepth(handle
, inode
, path
, newext
);
1205 ext4_ext_drop_refs(path
);
1206 path
= ext4_ext_find_extent(inode
,
1207 (ext4_lblk_t
)le32_to_cpu(newext
->ee_block
),
1210 err
= PTR_ERR(path
);
1215 * only first (depth 0 -> 1) produces free space;
1216 * in all other cases we have to split the grown tree
1218 depth
= ext_depth(inode
);
1219 if (path
[depth
].p_hdr
->eh_entries
== path
[depth
].p_hdr
->eh_max
) {
1220 /* now we need to split */
1230 * search the closest allocated block to the left for *logical
1231 * and returns it at @logical + it's physical address at @phys
1232 * if *logical is the smallest allocated block, the function
1233 * returns 0 at @phys
1234 * return value contains 0 (success) or error code
1237 ext4_ext_search_left(struct inode
*inode
, struct ext4_ext_path
*path
,
1238 ext4_lblk_t
*logical
, ext4_fsblk_t
*phys
)
1240 struct ext4_extent_idx
*ix
;
1241 struct ext4_extent
*ex
;
1244 if (unlikely(path
== NULL
)) {
1245 EXT4_ERROR_INODE(inode
, "path == NULL *logical %d!", *logical
);
1248 depth
= path
->p_depth
;
1251 if (depth
== 0 && path
->p_ext
== NULL
)
1254 /* usually extent in the path covers blocks smaller
1255 * then *logical, but it can be that extent is the
1256 * first one in the file */
1258 ex
= path
[depth
].p_ext
;
1259 ee_len
= ext4_ext_get_actual_len(ex
);
1260 if (*logical
< le32_to_cpu(ex
->ee_block
)) {
1261 if (unlikely(EXT_FIRST_EXTENT(path
[depth
].p_hdr
) != ex
)) {
1262 EXT4_ERROR_INODE(inode
,
1263 "EXT_FIRST_EXTENT != ex *logical %d ee_block %d!",
1264 *logical
, le32_to_cpu(ex
->ee_block
));
1267 while (--depth
>= 0) {
1268 ix
= path
[depth
].p_idx
;
1269 if (unlikely(ix
!= EXT_FIRST_INDEX(path
[depth
].p_hdr
))) {
1270 EXT4_ERROR_INODE(inode
,
1271 "ix (%d) != EXT_FIRST_INDEX (%d) (depth %d)!",
1272 ix
!= NULL
? ix
->ei_block
: 0,
1273 EXT_FIRST_INDEX(path
[depth
].p_hdr
) != NULL
?
1274 EXT_FIRST_INDEX(path
[depth
].p_hdr
)->ei_block
: 0,
1282 if (unlikely(*logical
< (le32_to_cpu(ex
->ee_block
) + ee_len
))) {
1283 EXT4_ERROR_INODE(inode
,
1284 "logical %d < ee_block %d + ee_len %d!",
1285 *logical
, le32_to_cpu(ex
->ee_block
), ee_len
);
1289 *logical
= le32_to_cpu(ex
->ee_block
) + ee_len
- 1;
1290 *phys
= ext_pblock(ex
) + ee_len
- 1;
1295 * search the closest allocated block to the right for *logical
1296 * and returns it at @logical + it's physical address at @phys
1297 * if *logical is the smallest allocated block, the function
1298 * returns 0 at @phys
1299 * return value contains 0 (success) or error code
1302 ext4_ext_search_right(struct inode
*inode
, struct ext4_ext_path
*path
,
1303 ext4_lblk_t
*logical
, ext4_fsblk_t
*phys
)
1305 struct buffer_head
*bh
= NULL
;
1306 struct ext4_extent_header
*eh
;
1307 struct ext4_extent_idx
*ix
;
1308 struct ext4_extent
*ex
;
1310 int depth
; /* Note, NOT eh_depth; depth from top of tree */
1313 if (unlikely(path
== NULL
)) {
1314 EXT4_ERROR_INODE(inode
, "path == NULL *logical %d!", *logical
);
1317 depth
= path
->p_depth
;
1320 if (depth
== 0 && path
->p_ext
== NULL
)
1323 /* usually extent in the path covers blocks smaller
1324 * then *logical, but it can be that extent is the
1325 * first one in the file */
1327 ex
= path
[depth
].p_ext
;
1328 ee_len
= ext4_ext_get_actual_len(ex
);
1329 if (*logical
< le32_to_cpu(ex
->ee_block
)) {
1330 if (unlikely(EXT_FIRST_EXTENT(path
[depth
].p_hdr
) != ex
)) {
1331 EXT4_ERROR_INODE(inode
,
1332 "first_extent(path[%d].p_hdr) != ex",
1336 while (--depth
>= 0) {
1337 ix
= path
[depth
].p_idx
;
1338 if (unlikely(ix
!= EXT_FIRST_INDEX(path
[depth
].p_hdr
))) {
1339 EXT4_ERROR_INODE(inode
,
1340 "ix != EXT_FIRST_INDEX *logical %d!",
1345 *logical
= le32_to_cpu(ex
->ee_block
);
1346 *phys
= ext_pblock(ex
);
1350 if (unlikely(*logical
< (le32_to_cpu(ex
->ee_block
) + ee_len
))) {
1351 EXT4_ERROR_INODE(inode
,
1352 "logical %d < ee_block %d + ee_len %d!",
1353 *logical
, le32_to_cpu(ex
->ee_block
), ee_len
);
1357 if (ex
!= EXT_LAST_EXTENT(path
[depth
].p_hdr
)) {
1358 /* next allocated block in this leaf */
1360 *logical
= le32_to_cpu(ex
->ee_block
);
1361 *phys
= ext_pblock(ex
);
1365 /* go up and search for index to the right */
1366 while (--depth
>= 0) {
1367 ix
= path
[depth
].p_idx
;
1368 if (ix
!= EXT_LAST_INDEX(path
[depth
].p_hdr
))
1372 /* we've gone up to the root and found no index to the right */
1376 /* we've found index to the right, let's
1377 * follow it and find the closest allocated
1378 * block to the right */
1380 block
= idx_pblock(ix
);
1381 while (++depth
< path
->p_depth
) {
1382 bh
= sb_bread(inode
->i_sb
, block
);
1385 eh
= ext_block_hdr(bh
);
1386 /* subtract from p_depth to get proper eh_depth */
1387 if (ext4_ext_check(inode
, eh
, path
->p_depth
- depth
)) {
1391 ix
= EXT_FIRST_INDEX(eh
);
1392 block
= idx_pblock(ix
);
1396 bh
= sb_bread(inode
->i_sb
, block
);
1399 eh
= ext_block_hdr(bh
);
1400 if (ext4_ext_check(inode
, eh
, path
->p_depth
- depth
)) {
1404 ex
= EXT_FIRST_EXTENT(eh
);
1405 *logical
= le32_to_cpu(ex
->ee_block
);
1406 *phys
= ext_pblock(ex
);
1412 * ext4_ext_next_allocated_block:
1413 * returns allocated block in subsequent extent or EXT_MAX_BLOCK.
1414 * NOTE: it considers block number from index entry as
1415 * allocated block. Thus, index entries have to be consistent
1419 ext4_ext_next_allocated_block(struct ext4_ext_path
*path
)
1423 BUG_ON(path
== NULL
);
1424 depth
= path
->p_depth
;
1426 if (depth
== 0 && path
->p_ext
== NULL
)
1427 return EXT_MAX_BLOCK
;
1429 while (depth
>= 0) {
1430 if (depth
== path
->p_depth
) {
1432 if (path
[depth
].p_ext
!=
1433 EXT_LAST_EXTENT(path
[depth
].p_hdr
))
1434 return le32_to_cpu(path
[depth
].p_ext
[1].ee_block
);
1437 if (path
[depth
].p_idx
!=
1438 EXT_LAST_INDEX(path
[depth
].p_hdr
))
1439 return le32_to_cpu(path
[depth
].p_idx
[1].ei_block
);
1444 return EXT_MAX_BLOCK
;
1448 * ext4_ext_next_leaf_block:
1449 * returns first allocated block from next leaf or EXT_MAX_BLOCK
1451 static ext4_lblk_t
ext4_ext_next_leaf_block(struct inode
*inode
,
1452 struct ext4_ext_path
*path
)
1456 BUG_ON(path
== NULL
);
1457 depth
= path
->p_depth
;
1459 /* zero-tree has no leaf blocks at all */
1461 return EXT_MAX_BLOCK
;
1463 /* go to index block */
1466 while (depth
>= 0) {
1467 if (path
[depth
].p_idx
!=
1468 EXT_LAST_INDEX(path
[depth
].p_hdr
))
1469 return (ext4_lblk_t
)
1470 le32_to_cpu(path
[depth
].p_idx
[1].ei_block
);
1474 return EXT_MAX_BLOCK
;
1478 * ext4_ext_correct_indexes:
1479 * if leaf gets modified and modified extent is first in the leaf,
1480 * then we have to correct all indexes above.
1481 * TODO: do we need to correct tree in all cases?
1483 static int ext4_ext_correct_indexes(handle_t
*handle
, struct inode
*inode
,
1484 struct ext4_ext_path
*path
)
1486 struct ext4_extent_header
*eh
;
1487 int depth
= ext_depth(inode
);
1488 struct ext4_extent
*ex
;
1492 eh
= path
[depth
].p_hdr
;
1493 ex
= path
[depth
].p_ext
;
1495 if (unlikely(ex
== NULL
|| eh
== NULL
)) {
1496 EXT4_ERROR_INODE(inode
,
1497 "ex %p == NULL or eh %p == NULL", ex
, eh
);
1502 /* there is no tree at all */
1506 if (ex
!= EXT_FIRST_EXTENT(eh
)) {
1507 /* we correct tree if first leaf got modified only */
1512 * TODO: we need correction if border is smaller than current one
1515 border
= path
[depth
].p_ext
->ee_block
;
1516 err
= ext4_ext_get_access(handle
, inode
, path
+ k
);
1519 path
[k
].p_idx
->ei_block
= border
;
1520 err
= ext4_ext_dirty(handle
, inode
, path
+ k
);
1525 /* change all left-side indexes */
1526 if (path
[k
+1].p_idx
!= EXT_FIRST_INDEX(path
[k
+1].p_hdr
))
1528 err
= ext4_ext_get_access(handle
, inode
, path
+ k
);
1531 path
[k
].p_idx
->ei_block
= border
;
1532 err
= ext4_ext_dirty(handle
, inode
, path
+ k
);
1541 ext4_can_extents_be_merged(struct inode
*inode
, struct ext4_extent
*ex1
,
1542 struct ext4_extent
*ex2
)
1544 unsigned short ext1_ee_len
, ext2_ee_len
, max_len
;
1547 * Make sure that either both extents are uninitialized, or
1550 if (ext4_ext_is_uninitialized(ex1
) ^ ext4_ext_is_uninitialized(ex2
))
1553 if (ext4_ext_is_uninitialized(ex1
))
1554 max_len
= EXT_UNINIT_MAX_LEN
;
1556 max_len
= EXT_INIT_MAX_LEN
;
1558 ext1_ee_len
= ext4_ext_get_actual_len(ex1
);
1559 ext2_ee_len
= ext4_ext_get_actual_len(ex2
);
1561 if (le32_to_cpu(ex1
->ee_block
) + ext1_ee_len
!=
1562 le32_to_cpu(ex2
->ee_block
))
1566 * To allow future support for preallocated extents to be added
1567 * as an RO_COMPAT feature, refuse to merge to extents if
1568 * this can result in the top bit of ee_len being set.
1570 if (ext1_ee_len
+ ext2_ee_len
> max_len
)
1572 #ifdef AGGRESSIVE_TEST
1573 if (ext1_ee_len
>= 4)
1577 if (ext_pblock(ex1
) + ext1_ee_len
== ext_pblock(ex2
))
1583 * This function tries to merge the "ex" extent to the next extent in the tree.
1584 * It always tries to merge towards right. If you want to merge towards
1585 * left, pass "ex - 1" as argument instead of "ex".
1586 * Returns 0 if the extents (ex and ex+1) were _not_ merged and returns
1587 * 1 if they got merged.
1589 int ext4_ext_try_to_merge(struct inode
*inode
,
1590 struct ext4_ext_path
*path
,
1591 struct ext4_extent
*ex
)
1593 struct ext4_extent_header
*eh
;
1594 unsigned int depth
, len
;
1596 int uninitialized
= 0;
1598 depth
= ext_depth(inode
);
1599 BUG_ON(path
[depth
].p_hdr
== NULL
);
1600 eh
= path
[depth
].p_hdr
;
1602 while (ex
< EXT_LAST_EXTENT(eh
)) {
1603 if (!ext4_can_extents_be_merged(inode
, ex
, ex
+ 1))
1605 /* merge with next extent! */
1606 if (ext4_ext_is_uninitialized(ex
))
1608 ex
->ee_len
= cpu_to_le16(ext4_ext_get_actual_len(ex
)
1609 + ext4_ext_get_actual_len(ex
+ 1));
1611 ext4_ext_mark_uninitialized(ex
);
1613 if (ex
+ 1 < EXT_LAST_EXTENT(eh
)) {
1614 len
= (EXT_LAST_EXTENT(eh
) - ex
- 1)
1615 * sizeof(struct ext4_extent
);
1616 memmove(ex
+ 1, ex
+ 2, len
);
1618 le16_add_cpu(&eh
->eh_entries
, -1);
1620 WARN_ON(eh
->eh_entries
== 0);
1621 if (!eh
->eh_entries
)
1622 ext4_error(inode
->i_sb
,
1623 "inode#%lu, eh->eh_entries = 0!",
1631 * check if a portion of the "newext" extent overlaps with an
1634 * If there is an overlap discovered, it updates the length of the newext
1635 * such that there will be no overlap, and then returns 1.
1636 * If there is no overlap found, it returns 0.
1638 unsigned int ext4_ext_check_overlap(struct inode
*inode
,
1639 struct ext4_extent
*newext
,
1640 struct ext4_ext_path
*path
)
1643 unsigned int depth
, len1
;
1644 unsigned int ret
= 0;
1646 b1
= le32_to_cpu(newext
->ee_block
);
1647 len1
= ext4_ext_get_actual_len(newext
);
1648 depth
= ext_depth(inode
);
1649 if (!path
[depth
].p_ext
)
1651 b2
= le32_to_cpu(path
[depth
].p_ext
->ee_block
);
1654 * get the next allocated block if the extent in the path
1655 * is before the requested block(s)
1658 b2
= ext4_ext_next_allocated_block(path
);
1659 if (b2
== EXT_MAX_BLOCK
)
1663 /* check for wrap through zero on extent logical start block*/
1664 if (b1
+ len1
< b1
) {
1665 len1
= EXT_MAX_BLOCK
- b1
;
1666 newext
->ee_len
= cpu_to_le16(len1
);
1670 /* check for overlap */
1671 if (b1
+ len1
> b2
) {
1672 newext
->ee_len
= cpu_to_le16(b2
- b1
);
1680 * ext4_ext_insert_extent:
1681 * tries to merge requsted extent into the existing extent or
1682 * inserts requested extent as new one into the tree,
1683 * creating new leaf in the no-space case.
1685 int ext4_ext_insert_extent(handle_t
*handle
, struct inode
*inode
,
1686 struct ext4_ext_path
*path
,
1687 struct ext4_extent
*newext
, int flag
)
1689 struct ext4_extent_header
*eh
;
1690 struct ext4_extent
*ex
, *fex
;
1691 struct ext4_extent
*nearex
; /* nearest extent */
1692 struct ext4_ext_path
*npath
= NULL
;
1693 int depth
, len
, err
;
1695 unsigned uninitialized
= 0;
1697 if (unlikely(ext4_ext_get_actual_len(newext
) == 0)) {
1698 EXT4_ERROR_INODE(inode
, "ext4_ext_get_actual_len(newext) == 0");
1701 depth
= ext_depth(inode
);
1702 ex
= path
[depth
].p_ext
;
1703 if (unlikely(path
[depth
].p_hdr
== NULL
)) {
1704 EXT4_ERROR_INODE(inode
, "path[%d].p_hdr == NULL", depth
);
1708 /* try to insert block into found extent and return */
1709 if (ex
&& !(flag
& EXT4_GET_BLOCKS_PRE_IO
)
1710 && ext4_can_extents_be_merged(inode
, ex
, newext
)) {
1711 ext_debug("append [%d]%d block to %d:[%d]%d (from %llu)\n",
1712 ext4_ext_is_uninitialized(newext
),
1713 ext4_ext_get_actual_len(newext
),
1714 le32_to_cpu(ex
->ee_block
),
1715 ext4_ext_is_uninitialized(ex
),
1716 ext4_ext_get_actual_len(ex
), ext_pblock(ex
));
1717 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
1722 * ext4_can_extents_be_merged should have checked that either
1723 * both extents are uninitialized, or both aren't. Thus we
1724 * need to check only one of them here.
1726 if (ext4_ext_is_uninitialized(ex
))
1728 ex
->ee_len
= cpu_to_le16(ext4_ext_get_actual_len(ex
)
1729 + ext4_ext_get_actual_len(newext
));
1731 ext4_ext_mark_uninitialized(ex
);
1732 eh
= path
[depth
].p_hdr
;
1738 depth
= ext_depth(inode
);
1739 eh
= path
[depth
].p_hdr
;
1740 if (le16_to_cpu(eh
->eh_entries
) < le16_to_cpu(eh
->eh_max
))
1743 /* probably next leaf has space for us? */
1744 fex
= EXT_LAST_EXTENT(eh
);
1745 next
= ext4_ext_next_leaf_block(inode
, path
);
1746 if (le32_to_cpu(newext
->ee_block
) > le32_to_cpu(fex
->ee_block
)
1747 && next
!= EXT_MAX_BLOCK
) {
1748 ext_debug("next leaf block - %d\n", next
);
1749 BUG_ON(npath
!= NULL
);
1750 npath
= ext4_ext_find_extent(inode
, next
, NULL
);
1752 return PTR_ERR(npath
);
1753 BUG_ON(npath
->p_depth
!= path
->p_depth
);
1754 eh
= npath
[depth
].p_hdr
;
1755 if (le16_to_cpu(eh
->eh_entries
) < le16_to_cpu(eh
->eh_max
)) {
1756 ext_debug("next leaf isnt full(%d)\n",
1757 le16_to_cpu(eh
->eh_entries
));
1761 ext_debug("next leaf has no free space(%d,%d)\n",
1762 le16_to_cpu(eh
->eh_entries
), le16_to_cpu(eh
->eh_max
));
1766 * There is no free space in the found leaf.
1767 * We're gonna add a new leaf in the tree.
1769 err
= ext4_ext_create_new_leaf(handle
, inode
, path
, newext
);
1772 depth
= ext_depth(inode
);
1773 eh
= path
[depth
].p_hdr
;
1776 nearex
= path
[depth
].p_ext
;
1778 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
1783 /* there is no extent in this leaf, create first one */
1784 ext_debug("first extent in the leaf: %d:%llu:[%d]%d\n",
1785 le32_to_cpu(newext
->ee_block
),
1787 ext4_ext_is_uninitialized(newext
),
1788 ext4_ext_get_actual_len(newext
));
1789 path
[depth
].p_ext
= EXT_FIRST_EXTENT(eh
);
1790 } else if (le32_to_cpu(newext
->ee_block
)
1791 > le32_to_cpu(nearex
->ee_block
)) {
1792 /* BUG_ON(newext->ee_block == nearex->ee_block); */
1793 if (nearex
!= EXT_LAST_EXTENT(eh
)) {
1794 len
= EXT_MAX_EXTENT(eh
) - nearex
;
1795 len
= (len
- 1) * sizeof(struct ext4_extent
);
1796 len
= len
< 0 ? 0 : len
;
1797 ext_debug("insert %d:%llu:[%d]%d after: nearest 0x%p, "
1798 "move %d from 0x%p to 0x%p\n",
1799 le32_to_cpu(newext
->ee_block
),
1801 ext4_ext_is_uninitialized(newext
),
1802 ext4_ext_get_actual_len(newext
),
1803 nearex
, len
, nearex
+ 1, nearex
+ 2);
1804 memmove(nearex
+ 2, nearex
+ 1, len
);
1806 path
[depth
].p_ext
= nearex
+ 1;
1808 BUG_ON(newext
->ee_block
== nearex
->ee_block
);
1809 len
= (EXT_MAX_EXTENT(eh
) - nearex
) * sizeof(struct ext4_extent
);
1810 len
= len
< 0 ? 0 : len
;
1811 ext_debug("insert %d:%llu:[%d]%d before: nearest 0x%p, "
1812 "move %d from 0x%p to 0x%p\n",
1813 le32_to_cpu(newext
->ee_block
),
1815 ext4_ext_is_uninitialized(newext
),
1816 ext4_ext_get_actual_len(newext
),
1817 nearex
, len
, nearex
+ 1, nearex
+ 2);
1818 memmove(nearex
+ 1, nearex
, len
);
1819 path
[depth
].p_ext
= nearex
;
1822 le16_add_cpu(&eh
->eh_entries
, 1);
1823 nearex
= path
[depth
].p_ext
;
1824 nearex
->ee_block
= newext
->ee_block
;
1825 ext4_ext_store_pblock(nearex
, ext_pblock(newext
));
1826 nearex
->ee_len
= newext
->ee_len
;
1829 /* try to merge extents to the right */
1830 if (!(flag
& EXT4_GET_BLOCKS_PRE_IO
))
1831 ext4_ext_try_to_merge(inode
, path
, nearex
);
1833 /* try to merge extents to the left */
1835 /* time to correct all indexes above */
1836 err
= ext4_ext_correct_indexes(handle
, inode
, path
);
1840 err
= ext4_ext_dirty(handle
, inode
, path
+ depth
);
1844 ext4_ext_drop_refs(npath
);
1847 ext4_ext_invalidate_cache(inode
);
1851 int ext4_ext_walk_space(struct inode
*inode
, ext4_lblk_t block
,
1852 ext4_lblk_t num
, ext_prepare_callback func
,
1855 struct ext4_ext_path
*path
= NULL
;
1856 struct ext4_ext_cache cbex
;
1857 struct ext4_extent
*ex
;
1858 ext4_lblk_t next
, start
= 0, end
= 0;
1859 ext4_lblk_t last
= block
+ num
;
1860 int depth
, exists
, err
= 0;
1862 BUG_ON(func
== NULL
);
1863 BUG_ON(inode
== NULL
);
1865 while (block
< last
&& block
!= EXT_MAX_BLOCK
) {
1867 /* find extent for this block */
1868 down_read(&EXT4_I(inode
)->i_data_sem
);
1869 path
= ext4_ext_find_extent(inode
, block
, path
);
1870 up_read(&EXT4_I(inode
)->i_data_sem
);
1872 err
= PTR_ERR(path
);
1877 depth
= ext_depth(inode
);
1878 if (unlikely(path
[depth
].p_hdr
== NULL
)) {
1879 EXT4_ERROR_INODE(inode
, "path[%d].p_hdr == NULL", depth
);
1883 ex
= path
[depth
].p_ext
;
1884 next
= ext4_ext_next_allocated_block(path
);
1888 /* there is no extent yet, so try to allocate
1889 * all requested space */
1892 } else if (le32_to_cpu(ex
->ee_block
) > block
) {
1893 /* need to allocate space before found extent */
1895 end
= le32_to_cpu(ex
->ee_block
);
1896 if (block
+ num
< end
)
1898 } else if (block
>= le32_to_cpu(ex
->ee_block
)
1899 + ext4_ext_get_actual_len(ex
)) {
1900 /* need to allocate space after found extent */
1905 } else if (block
>= le32_to_cpu(ex
->ee_block
)) {
1907 * some part of requested space is covered
1911 end
= le32_to_cpu(ex
->ee_block
)
1912 + ext4_ext_get_actual_len(ex
);
1913 if (block
+ num
< end
)
1919 BUG_ON(end
<= start
);
1922 cbex
.ec_block
= start
;
1923 cbex
.ec_len
= end
- start
;
1925 cbex
.ec_type
= EXT4_EXT_CACHE_GAP
;
1927 cbex
.ec_block
= le32_to_cpu(ex
->ee_block
);
1928 cbex
.ec_len
= ext4_ext_get_actual_len(ex
);
1929 cbex
.ec_start
= ext_pblock(ex
);
1930 cbex
.ec_type
= EXT4_EXT_CACHE_EXTENT
;
1933 if (unlikely(cbex
.ec_len
== 0)) {
1934 EXT4_ERROR_INODE(inode
, "cbex.ec_len == 0");
1938 err
= func(inode
, path
, &cbex
, ex
, cbdata
);
1939 ext4_ext_drop_refs(path
);
1944 if (err
== EXT_REPEAT
)
1946 else if (err
== EXT_BREAK
) {
1951 if (ext_depth(inode
) != depth
) {
1952 /* depth was changed. we have to realloc path */
1957 block
= cbex
.ec_block
+ cbex
.ec_len
;
1961 ext4_ext_drop_refs(path
);
1969 ext4_ext_put_in_cache(struct inode
*inode
, ext4_lblk_t block
,
1970 __u32 len
, ext4_fsblk_t start
, int type
)
1972 struct ext4_ext_cache
*cex
;
1974 spin_lock(&EXT4_I(inode
)->i_block_reservation_lock
);
1975 cex
= &EXT4_I(inode
)->i_cached_extent
;
1976 cex
->ec_type
= type
;
1977 cex
->ec_block
= block
;
1979 cex
->ec_start
= start
;
1980 spin_unlock(&EXT4_I(inode
)->i_block_reservation_lock
);
1984 * ext4_ext_put_gap_in_cache:
1985 * calculate boundaries of the gap that the requested block fits into
1986 * and cache this gap
1989 ext4_ext_put_gap_in_cache(struct inode
*inode
, struct ext4_ext_path
*path
,
1992 int depth
= ext_depth(inode
);
1995 struct ext4_extent
*ex
;
1997 ex
= path
[depth
].p_ext
;
1999 /* there is no extent yet, so gap is [0;-] */
2001 len
= EXT_MAX_BLOCK
;
2002 ext_debug("cache gap(whole file):");
2003 } else if (block
< le32_to_cpu(ex
->ee_block
)) {
2005 len
= le32_to_cpu(ex
->ee_block
) - block
;
2006 ext_debug("cache gap(before): %u [%u:%u]",
2008 le32_to_cpu(ex
->ee_block
),
2009 ext4_ext_get_actual_len(ex
));
2010 } else if (block
>= le32_to_cpu(ex
->ee_block
)
2011 + ext4_ext_get_actual_len(ex
)) {
2013 lblock
= le32_to_cpu(ex
->ee_block
)
2014 + ext4_ext_get_actual_len(ex
);
2016 next
= ext4_ext_next_allocated_block(path
);
2017 ext_debug("cache gap(after): [%u:%u] %u",
2018 le32_to_cpu(ex
->ee_block
),
2019 ext4_ext_get_actual_len(ex
),
2021 BUG_ON(next
== lblock
);
2022 len
= next
- lblock
;
2028 ext_debug(" -> %u:%lu\n", lblock
, len
);
2029 ext4_ext_put_in_cache(inode
, lblock
, len
, 0, EXT4_EXT_CACHE_GAP
);
2033 ext4_ext_in_cache(struct inode
*inode
, ext4_lblk_t block
,
2034 struct ext4_extent
*ex
)
2036 struct ext4_ext_cache
*cex
;
2037 int ret
= EXT4_EXT_CACHE_NO
;
2040 * We borrow i_block_reservation_lock to protect i_cached_extent
2042 spin_lock(&EXT4_I(inode
)->i_block_reservation_lock
);
2043 cex
= &EXT4_I(inode
)->i_cached_extent
;
2045 /* has cache valid data? */
2046 if (cex
->ec_type
== EXT4_EXT_CACHE_NO
)
2049 BUG_ON(cex
->ec_type
!= EXT4_EXT_CACHE_GAP
&&
2050 cex
->ec_type
!= EXT4_EXT_CACHE_EXTENT
);
2051 if (in_range(block
, cex
->ec_block
, cex
->ec_len
)) {
2052 ex
->ee_block
= cpu_to_le32(cex
->ec_block
);
2053 ext4_ext_store_pblock(ex
, cex
->ec_start
);
2054 ex
->ee_len
= cpu_to_le16(cex
->ec_len
);
2055 ext_debug("%u cached by %u:%u:%llu\n",
2057 cex
->ec_block
, cex
->ec_len
, cex
->ec_start
);
2061 spin_unlock(&EXT4_I(inode
)->i_block_reservation_lock
);
2067 * removes index from the index block.
2068 * It's used in truncate case only, thus all requests are for
2069 * last index in the block only.
2071 static int ext4_ext_rm_idx(handle_t
*handle
, struct inode
*inode
,
2072 struct ext4_ext_path
*path
)
2077 /* free index block */
2079 leaf
= idx_pblock(path
->p_idx
);
2080 if (unlikely(path
->p_hdr
->eh_entries
== 0)) {
2081 EXT4_ERROR_INODE(inode
, "path->p_hdr->eh_entries == 0");
2084 err
= ext4_ext_get_access(handle
, inode
, path
);
2087 le16_add_cpu(&path
->p_hdr
->eh_entries
, -1);
2088 err
= ext4_ext_dirty(handle
, inode
, path
);
2091 ext_debug("index is empty, remove it, free block %llu\n", leaf
);
2092 ext4_free_blocks(handle
, inode
, 0, leaf
, 1,
2093 EXT4_FREE_BLOCKS_METADATA
| EXT4_FREE_BLOCKS_FORGET
);
2098 * ext4_ext_calc_credits_for_single_extent:
2099 * This routine returns max. credits that needed to insert an extent
2100 * to the extent tree.
2101 * When pass the actual path, the caller should calculate credits
2104 int ext4_ext_calc_credits_for_single_extent(struct inode
*inode
, int nrblocks
,
2105 struct ext4_ext_path
*path
)
2108 int depth
= ext_depth(inode
);
2111 /* probably there is space in leaf? */
2112 if (le16_to_cpu(path
[depth
].p_hdr
->eh_entries
)
2113 < le16_to_cpu(path
[depth
].p_hdr
->eh_max
)) {
2116 * There are some space in the leaf tree, no
2117 * need to account for leaf block credit
2119 * bitmaps and block group descriptor blocks
2120 * and other metadat blocks still need to be
2123 /* 1 bitmap, 1 block group descriptor */
2124 ret
= 2 + EXT4_META_TRANS_BLOCKS(inode
->i_sb
);
2129 return ext4_chunk_trans_blocks(inode
, nrblocks
);
2133 * How many index/leaf blocks need to change/allocate to modify nrblocks?
2135 * if nrblocks are fit in a single extent (chunk flag is 1), then
2136 * in the worse case, each tree level index/leaf need to be changed
2137 * if the tree split due to insert a new extent, then the old tree
2138 * index/leaf need to be updated too
2140 * If the nrblocks are discontiguous, they could cause
2141 * the whole tree split more than once, but this is really rare.
2143 int ext4_ext_index_trans_blocks(struct inode
*inode
, int nrblocks
, int chunk
)
2146 int depth
= ext_depth(inode
);
2156 static int ext4_remove_blocks(handle_t
*handle
, struct inode
*inode
,
2157 struct ext4_extent
*ex
,
2158 ext4_lblk_t from
, ext4_lblk_t to
)
2160 unsigned short ee_len
= ext4_ext_get_actual_len(ex
);
2161 int flags
= EXT4_FREE_BLOCKS_FORGET
;
2163 if (S_ISDIR(inode
->i_mode
) || S_ISLNK(inode
->i_mode
))
2164 flags
|= EXT4_FREE_BLOCKS_METADATA
;
2165 #ifdef EXTENTS_STATS
2167 struct ext4_sb_info
*sbi
= EXT4_SB(inode
->i_sb
);
2168 spin_lock(&sbi
->s_ext_stats_lock
);
2169 sbi
->s_ext_blocks
+= ee_len
;
2170 sbi
->s_ext_extents
++;
2171 if (ee_len
< sbi
->s_ext_min
)
2172 sbi
->s_ext_min
= ee_len
;
2173 if (ee_len
> sbi
->s_ext_max
)
2174 sbi
->s_ext_max
= ee_len
;
2175 if (ext_depth(inode
) > sbi
->s_depth_max
)
2176 sbi
->s_depth_max
= ext_depth(inode
);
2177 spin_unlock(&sbi
->s_ext_stats_lock
);
2180 if (from
>= le32_to_cpu(ex
->ee_block
)
2181 && to
== le32_to_cpu(ex
->ee_block
) + ee_len
- 1) {
2186 num
= le32_to_cpu(ex
->ee_block
) + ee_len
- from
;
2187 start
= ext_pblock(ex
) + ee_len
- num
;
2188 ext_debug("free last %u blocks starting %llu\n", num
, start
);
2189 ext4_free_blocks(handle
, inode
, 0, start
, num
, flags
);
2190 } else if (from
== le32_to_cpu(ex
->ee_block
)
2191 && to
<= le32_to_cpu(ex
->ee_block
) + ee_len
- 1) {
2192 printk(KERN_INFO
"strange request: removal %u-%u from %u:%u\n",
2193 from
, to
, le32_to_cpu(ex
->ee_block
), ee_len
);
2195 printk(KERN_INFO
"strange request: removal(2) "
2196 "%u-%u from %u:%u\n",
2197 from
, to
, le32_to_cpu(ex
->ee_block
), ee_len
);
2203 ext4_ext_rm_leaf(handle_t
*handle
, struct inode
*inode
,
2204 struct ext4_ext_path
*path
, ext4_lblk_t start
)
2206 int err
= 0, correct_index
= 0;
2207 int depth
= ext_depth(inode
), credits
;
2208 struct ext4_extent_header
*eh
;
2209 ext4_lblk_t a
, b
, block
;
2211 ext4_lblk_t ex_ee_block
;
2212 unsigned short ex_ee_len
;
2213 unsigned uninitialized
= 0;
2214 struct ext4_extent
*ex
;
2216 /* the header must be checked already in ext4_ext_remove_space() */
2217 ext_debug("truncate since %u in leaf\n", start
);
2218 if (!path
[depth
].p_hdr
)
2219 path
[depth
].p_hdr
= ext_block_hdr(path
[depth
].p_bh
);
2220 eh
= path
[depth
].p_hdr
;
2221 if (unlikely(path
[depth
].p_hdr
== NULL
)) {
2222 EXT4_ERROR_INODE(inode
, "path[%d].p_hdr == NULL", depth
);
2225 /* find where to start removing */
2226 ex
= EXT_LAST_EXTENT(eh
);
2228 ex_ee_block
= le32_to_cpu(ex
->ee_block
);
2229 ex_ee_len
= ext4_ext_get_actual_len(ex
);
2231 while (ex
>= EXT_FIRST_EXTENT(eh
) &&
2232 ex_ee_block
+ ex_ee_len
> start
) {
2234 if (ext4_ext_is_uninitialized(ex
))
2239 ext_debug("remove ext %u:[%d]%d\n", ex_ee_block
,
2240 uninitialized
, ex_ee_len
);
2241 path
[depth
].p_ext
= ex
;
2243 a
= ex_ee_block
> start
? ex_ee_block
: start
;
2244 b
= ex_ee_block
+ ex_ee_len
- 1 < EXT_MAX_BLOCK
?
2245 ex_ee_block
+ ex_ee_len
- 1 : EXT_MAX_BLOCK
;
2247 ext_debug(" border %u:%u\n", a
, b
);
2249 if (a
!= ex_ee_block
&& b
!= ex_ee_block
+ ex_ee_len
- 1) {
2253 } else if (a
!= ex_ee_block
) {
2254 /* remove tail of the extent */
2255 block
= ex_ee_block
;
2257 } else if (b
!= ex_ee_block
+ ex_ee_len
- 1) {
2258 /* remove head of the extent */
2261 /* there is no "make a hole" API yet */
2264 /* remove whole extent: excellent! */
2265 block
= ex_ee_block
;
2267 BUG_ON(a
!= ex_ee_block
);
2268 BUG_ON(b
!= ex_ee_block
+ ex_ee_len
- 1);
2272 * 3 for leaf, sb, and inode plus 2 (bmap and group
2273 * descriptor) for each block group; assume two block
2274 * groups plus ex_ee_len/blocks_per_block_group for
2277 credits
= 7 + 2*(ex_ee_len
/EXT4_BLOCKS_PER_GROUP(inode
->i_sb
));
2278 if (ex
== EXT_FIRST_EXTENT(eh
)) {
2280 credits
+= (ext_depth(inode
)) + 1;
2282 credits
+= EXT4_MAXQUOTAS_TRANS_BLOCKS(inode
->i_sb
);
2284 err
= ext4_ext_truncate_extend_restart(handle
, inode
, credits
);
2288 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
2292 err
= ext4_remove_blocks(handle
, inode
, ex
, a
, b
);
2297 /* this extent is removed; mark slot entirely unused */
2298 ext4_ext_store_pblock(ex
, 0);
2299 le16_add_cpu(&eh
->eh_entries
, -1);
2302 ex
->ee_block
= cpu_to_le32(block
);
2303 ex
->ee_len
= cpu_to_le16(num
);
2305 * Do not mark uninitialized if all the blocks in the
2306 * extent have been removed.
2308 if (uninitialized
&& num
)
2309 ext4_ext_mark_uninitialized(ex
);
2311 err
= ext4_ext_dirty(handle
, inode
, path
+ depth
);
2315 ext_debug("new extent: %u:%u:%llu\n", block
, num
,
2318 ex_ee_block
= le32_to_cpu(ex
->ee_block
);
2319 ex_ee_len
= ext4_ext_get_actual_len(ex
);
2322 if (correct_index
&& eh
->eh_entries
)
2323 err
= ext4_ext_correct_indexes(handle
, inode
, path
);
2325 /* if this leaf is free, then we should
2326 * remove it from index block above */
2327 if (err
== 0 && eh
->eh_entries
== 0 && path
[depth
].p_bh
!= NULL
)
2328 err
= ext4_ext_rm_idx(handle
, inode
, path
+ depth
);
2335 * ext4_ext_more_to_rm:
2336 * returns 1 if current index has to be freed (even partial)
2339 ext4_ext_more_to_rm(struct ext4_ext_path
*path
)
2341 BUG_ON(path
->p_idx
== NULL
);
2343 if (path
->p_idx
< EXT_FIRST_INDEX(path
->p_hdr
))
2347 * if truncate on deeper level happened, it wasn't partial,
2348 * so we have to consider current index for truncation
2350 if (le16_to_cpu(path
->p_hdr
->eh_entries
) == path
->p_block
)
2355 static int ext4_ext_remove_space(struct inode
*inode
, ext4_lblk_t start
)
2357 struct super_block
*sb
= inode
->i_sb
;
2358 int depth
= ext_depth(inode
);
2359 struct ext4_ext_path
*path
;
2363 ext_debug("truncate since %u\n", start
);
2365 /* probably first extent we're gonna free will be last in block */
2366 handle
= ext4_journal_start(inode
, depth
+ 1);
2368 return PTR_ERR(handle
);
2371 ext4_ext_invalidate_cache(inode
);
2374 * We start scanning from right side, freeing all the blocks
2375 * after i_size and walking into the tree depth-wise.
2377 depth
= ext_depth(inode
);
2378 path
= kzalloc(sizeof(struct ext4_ext_path
) * (depth
+ 1), GFP_NOFS
);
2380 ext4_journal_stop(handle
);
2383 path
[0].p_depth
= depth
;
2384 path
[0].p_hdr
= ext_inode_hdr(inode
);
2385 if (ext4_ext_check(inode
, path
[0].p_hdr
, depth
)) {
2391 while (i
>= 0 && err
== 0) {
2393 /* this is leaf block */
2394 err
= ext4_ext_rm_leaf(handle
, inode
, path
, start
);
2395 /* root level has p_bh == NULL, brelse() eats this */
2396 brelse(path
[i
].p_bh
);
2397 path
[i
].p_bh
= NULL
;
2402 /* this is index block */
2403 if (!path
[i
].p_hdr
) {
2404 ext_debug("initialize header\n");
2405 path
[i
].p_hdr
= ext_block_hdr(path
[i
].p_bh
);
2408 if (!path
[i
].p_idx
) {
2409 /* this level hasn't been touched yet */
2410 path
[i
].p_idx
= EXT_LAST_INDEX(path
[i
].p_hdr
);
2411 path
[i
].p_block
= le16_to_cpu(path
[i
].p_hdr
->eh_entries
)+1;
2412 ext_debug("init index ptr: hdr 0x%p, num %d\n",
2414 le16_to_cpu(path
[i
].p_hdr
->eh_entries
));
2416 /* we were already here, see at next index */
2420 ext_debug("level %d - index, first 0x%p, cur 0x%p\n",
2421 i
, EXT_FIRST_INDEX(path
[i
].p_hdr
),
2423 if (ext4_ext_more_to_rm(path
+ i
)) {
2424 struct buffer_head
*bh
;
2425 /* go to the next level */
2426 ext_debug("move to level %d (block %llu)\n",
2427 i
+ 1, idx_pblock(path
[i
].p_idx
));
2428 memset(path
+ i
+ 1, 0, sizeof(*path
));
2429 bh
= sb_bread(sb
, idx_pblock(path
[i
].p_idx
));
2431 /* should we reset i_size? */
2435 if (WARN_ON(i
+ 1 > depth
)) {
2439 if (ext4_ext_check(inode
, ext_block_hdr(bh
),
2444 path
[i
+ 1].p_bh
= bh
;
2446 /* save actual number of indexes since this
2447 * number is changed at the next iteration */
2448 path
[i
].p_block
= le16_to_cpu(path
[i
].p_hdr
->eh_entries
);
2451 /* we finished processing this index, go up */
2452 if (path
[i
].p_hdr
->eh_entries
== 0 && i
> 0) {
2453 /* index is empty, remove it;
2454 * handle must be already prepared by the
2455 * truncatei_leaf() */
2456 err
= ext4_ext_rm_idx(handle
, inode
, path
+ i
);
2458 /* root level has p_bh == NULL, brelse() eats this */
2459 brelse(path
[i
].p_bh
);
2460 path
[i
].p_bh
= NULL
;
2462 ext_debug("return to level %d\n", i
);
2466 /* TODO: flexible tree reduction should be here */
2467 if (path
->p_hdr
->eh_entries
== 0) {
2469 * truncate to zero freed all the tree,
2470 * so we need to correct eh_depth
2472 err
= ext4_ext_get_access(handle
, inode
, path
);
2474 ext_inode_hdr(inode
)->eh_depth
= 0;
2475 ext_inode_hdr(inode
)->eh_max
=
2476 cpu_to_le16(ext4_ext_space_root(inode
, 0));
2477 err
= ext4_ext_dirty(handle
, inode
, path
);
2481 ext4_ext_drop_refs(path
);
2485 ext4_journal_stop(handle
);
2491 * called at mount time
2493 void ext4_ext_init(struct super_block
*sb
)
2496 * possible initialization would be here
2499 if (EXT4_HAS_INCOMPAT_FEATURE(sb
, EXT4_FEATURE_INCOMPAT_EXTENTS
)) {
2500 #if defined(AGGRESSIVE_TEST) || defined(CHECK_BINSEARCH) || defined(EXTENTS_STATS)
2501 printk(KERN_INFO
"EXT4-fs: file extents enabled");
2502 #ifdef AGGRESSIVE_TEST
2503 printk(", aggressive tests");
2505 #ifdef CHECK_BINSEARCH
2506 printk(", check binsearch");
2508 #ifdef EXTENTS_STATS
2513 #ifdef EXTENTS_STATS
2514 spin_lock_init(&EXT4_SB(sb
)->s_ext_stats_lock
);
2515 EXT4_SB(sb
)->s_ext_min
= 1 << 30;
2516 EXT4_SB(sb
)->s_ext_max
= 0;
2522 * called at umount time
2524 void ext4_ext_release(struct super_block
*sb
)
2526 if (!EXT4_HAS_INCOMPAT_FEATURE(sb
, EXT4_FEATURE_INCOMPAT_EXTENTS
))
2529 #ifdef EXTENTS_STATS
2530 if (EXT4_SB(sb
)->s_ext_blocks
&& EXT4_SB(sb
)->s_ext_extents
) {
2531 struct ext4_sb_info
*sbi
= EXT4_SB(sb
);
2532 printk(KERN_ERR
"EXT4-fs: %lu blocks in %lu extents (%lu ave)\n",
2533 sbi
->s_ext_blocks
, sbi
->s_ext_extents
,
2534 sbi
->s_ext_blocks
/ sbi
->s_ext_extents
);
2535 printk(KERN_ERR
"EXT4-fs: extents: %lu min, %lu max, max depth %lu\n",
2536 sbi
->s_ext_min
, sbi
->s_ext_max
, sbi
->s_depth_max
);
2541 static void bi_complete(struct bio
*bio
, int error
)
2543 complete((struct completion
*)bio
->bi_private
);
2546 /* FIXME!! we need to try to merge to left or right after zero-out */
2547 static int ext4_ext_zeroout(struct inode
*inode
, struct ext4_extent
*ex
)
2551 int blkbits
, blocksize
;
2553 struct completion event
;
2554 unsigned int ee_len
, len
, done
, offset
;
2557 blkbits
= inode
->i_blkbits
;
2558 blocksize
= inode
->i_sb
->s_blocksize
;
2559 ee_len
= ext4_ext_get_actual_len(ex
);
2560 ee_pblock
= ext_pblock(ex
);
2562 /* convert ee_pblock to 512 byte sectors */
2563 ee_pblock
= ee_pblock
<< (blkbits
- 9);
2565 while (ee_len
> 0) {
2567 if (ee_len
> BIO_MAX_PAGES
)
2568 len
= BIO_MAX_PAGES
;
2572 bio
= bio_alloc(GFP_NOIO
, len
);
2576 bio
->bi_sector
= ee_pblock
;
2577 bio
->bi_bdev
= inode
->i_sb
->s_bdev
;
2581 while (done
< len
) {
2582 ret
= bio_add_page(bio
, ZERO_PAGE(0),
2584 if (ret
!= blocksize
) {
2586 * We can't add any more pages because of
2587 * hardware limitations. Start a new bio.
2592 offset
+= blocksize
;
2593 if (offset
>= PAGE_CACHE_SIZE
)
2597 init_completion(&event
);
2598 bio
->bi_private
= &event
;
2599 bio
->bi_end_io
= bi_complete
;
2600 submit_bio(WRITE
, bio
);
2601 wait_for_completion(&event
);
2603 if (!test_bit(BIO_UPTODATE
, &bio
->bi_flags
)) {
2609 ee_pblock
+= done
<< (blkbits
- 9);
2614 #define EXT4_EXT_ZERO_LEN 7
2616 * This function is called by ext4_ext_get_blocks() if someone tries to write
2617 * to an uninitialized extent. It may result in splitting the uninitialized
2618 * extent into multiple extents (upto three - one initialized and two
2620 * There are three possibilities:
2621 * a> There is no split required: Entire extent should be initialized
2622 * b> Splits in two extents: Write is happening at either end of the extent
2623 * c> Splits in three extents: Somone is writing in middle of the extent
2625 static int ext4_ext_convert_to_initialized(handle_t
*handle
,
2626 struct inode
*inode
,
2627 struct ext4_ext_path
*path
,
2629 unsigned int max_blocks
)
2631 struct ext4_extent
*ex
, newex
, orig_ex
;
2632 struct ext4_extent
*ex1
= NULL
;
2633 struct ext4_extent
*ex2
= NULL
;
2634 struct ext4_extent
*ex3
= NULL
;
2635 struct ext4_extent_header
*eh
;
2636 ext4_lblk_t ee_block
, eof_block
;
2637 unsigned int allocated
, ee_len
, depth
;
2638 ext4_fsblk_t newblock
;
2643 ext_debug("ext4_ext_convert_to_initialized: inode %lu, logical"
2644 "block %llu, max_blocks %u\n", inode
->i_ino
,
2645 (unsigned long long)iblock
, max_blocks
);
2647 eof_block
= (inode
->i_size
+ inode
->i_sb
->s_blocksize
- 1) >>
2648 inode
->i_sb
->s_blocksize_bits
;
2649 if (eof_block
< iblock
+ max_blocks
)
2650 eof_block
= iblock
+ max_blocks
;
2652 depth
= ext_depth(inode
);
2653 eh
= path
[depth
].p_hdr
;
2654 ex
= path
[depth
].p_ext
;
2655 ee_block
= le32_to_cpu(ex
->ee_block
);
2656 ee_len
= ext4_ext_get_actual_len(ex
);
2657 allocated
= ee_len
- (iblock
- ee_block
);
2658 newblock
= iblock
- ee_block
+ ext_pblock(ex
);
2661 orig_ex
.ee_block
= ex
->ee_block
;
2662 orig_ex
.ee_len
= cpu_to_le16(ee_len
);
2663 ext4_ext_store_pblock(&orig_ex
, ext_pblock(ex
));
2666 * It is safe to convert extent to initialized via explicit
2667 * zeroout only if extent is fully insde i_size or new_size.
2669 may_zeroout
= ee_block
+ ee_len
<= eof_block
;
2671 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
2674 /* If extent has less than 2*EXT4_EXT_ZERO_LEN zerout directly */
2675 if (ee_len
<= 2*EXT4_EXT_ZERO_LEN
&& may_zeroout
) {
2676 err
= ext4_ext_zeroout(inode
, &orig_ex
);
2678 goto fix_extent_len
;
2679 /* update the extent length and mark as initialized */
2680 ex
->ee_block
= orig_ex
.ee_block
;
2681 ex
->ee_len
= orig_ex
.ee_len
;
2682 ext4_ext_store_pblock(ex
, ext_pblock(&orig_ex
));
2683 ext4_ext_dirty(handle
, inode
, path
+ depth
);
2684 /* zeroed the full extent */
2688 /* ex1: ee_block to iblock - 1 : uninitialized */
2689 if (iblock
> ee_block
) {
2691 ex1
->ee_len
= cpu_to_le16(iblock
- ee_block
);
2692 ext4_ext_mark_uninitialized(ex1
);
2696 * for sanity, update the length of the ex2 extent before
2697 * we insert ex3, if ex1 is NULL. This is to avoid temporary
2698 * overlap of blocks.
2700 if (!ex1
&& allocated
> max_blocks
)
2701 ex2
->ee_len
= cpu_to_le16(max_blocks
);
2702 /* ex3: to ee_block + ee_len : uninitialised */
2703 if (allocated
> max_blocks
) {
2704 unsigned int newdepth
;
2705 /* If extent has less than EXT4_EXT_ZERO_LEN zerout directly */
2706 if (allocated
<= EXT4_EXT_ZERO_LEN
&& may_zeroout
) {
2708 * iblock == ee_block is handled by the zerouout
2710 * Mark first half uninitialized.
2711 * Mark second half initialized and zero out the
2712 * initialized extent
2714 ex
->ee_block
= orig_ex
.ee_block
;
2715 ex
->ee_len
= cpu_to_le16(ee_len
- allocated
);
2716 ext4_ext_mark_uninitialized(ex
);
2717 ext4_ext_store_pblock(ex
, ext_pblock(&orig_ex
));
2718 ext4_ext_dirty(handle
, inode
, path
+ depth
);
2721 ex3
->ee_block
= cpu_to_le32(iblock
);
2722 ext4_ext_store_pblock(ex3
, newblock
);
2723 ex3
->ee_len
= cpu_to_le16(allocated
);
2724 err
= ext4_ext_insert_extent(handle
, inode
, path
,
2726 if (err
== -ENOSPC
) {
2727 err
= ext4_ext_zeroout(inode
, &orig_ex
);
2729 goto fix_extent_len
;
2730 ex
->ee_block
= orig_ex
.ee_block
;
2731 ex
->ee_len
= orig_ex
.ee_len
;
2732 ext4_ext_store_pblock(ex
, ext_pblock(&orig_ex
));
2733 ext4_ext_dirty(handle
, inode
, path
+ depth
);
2734 /* blocks available from iblock */
2738 goto fix_extent_len
;
2741 * We need to zero out the second half because
2742 * an fallocate request can update file size and
2743 * converting the second half to initialized extent
2744 * implies that we can leak some junk data to user
2747 err
= ext4_ext_zeroout(inode
, ex3
);
2750 * We should actually mark the
2751 * second half as uninit and return error
2752 * Insert would have changed the extent
2754 depth
= ext_depth(inode
);
2755 ext4_ext_drop_refs(path
);
2756 path
= ext4_ext_find_extent(inode
,
2759 err
= PTR_ERR(path
);
2762 /* get the second half extent details */
2763 ex
= path
[depth
].p_ext
;
2764 err
= ext4_ext_get_access(handle
, inode
,
2768 ext4_ext_mark_uninitialized(ex
);
2769 ext4_ext_dirty(handle
, inode
, path
+ depth
);
2773 /* zeroed the second half */
2777 ex3
->ee_block
= cpu_to_le32(iblock
+ max_blocks
);
2778 ext4_ext_store_pblock(ex3
, newblock
+ max_blocks
);
2779 ex3
->ee_len
= cpu_to_le16(allocated
- max_blocks
);
2780 ext4_ext_mark_uninitialized(ex3
);
2781 err
= ext4_ext_insert_extent(handle
, inode
, path
, ex3
, 0);
2782 if (err
== -ENOSPC
&& may_zeroout
) {
2783 err
= ext4_ext_zeroout(inode
, &orig_ex
);
2785 goto fix_extent_len
;
2786 /* update the extent length and mark as initialized */
2787 ex
->ee_block
= orig_ex
.ee_block
;
2788 ex
->ee_len
= orig_ex
.ee_len
;
2789 ext4_ext_store_pblock(ex
, ext_pblock(&orig_ex
));
2790 ext4_ext_dirty(handle
, inode
, path
+ depth
);
2791 /* zeroed the full extent */
2792 /* blocks available from iblock */
2796 goto fix_extent_len
;
2798 * The depth, and hence eh & ex might change
2799 * as part of the insert above.
2801 newdepth
= ext_depth(inode
);
2803 * update the extent length after successful insert of the
2806 ee_len
-= ext4_ext_get_actual_len(ex3
);
2807 orig_ex
.ee_len
= cpu_to_le16(ee_len
);
2808 may_zeroout
= ee_block
+ ee_len
<= eof_block
;
2811 ext4_ext_drop_refs(path
);
2812 path
= ext4_ext_find_extent(inode
, iblock
, path
);
2814 err
= PTR_ERR(path
);
2817 eh
= path
[depth
].p_hdr
;
2818 ex
= path
[depth
].p_ext
;
2822 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
2826 allocated
= max_blocks
;
2828 /* If extent has less than EXT4_EXT_ZERO_LEN and we are trying
2829 * to insert a extent in the middle zerout directly
2830 * otherwise give the extent a chance to merge to left
2832 if (le16_to_cpu(orig_ex
.ee_len
) <= EXT4_EXT_ZERO_LEN
&&
2833 iblock
!= ee_block
&& may_zeroout
) {
2834 err
= ext4_ext_zeroout(inode
, &orig_ex
);
2836 goto fix_extent_len
;
2837 /* update the extent length and mark as initialized */
2838 ex
->ee_block
= orig_ex
.ee_block
;
2839 ex
->ee_len
= orig_ex
.ee_len
;
2840 ext4_ext_store_pblock(ex
, ext_pblock(&orig_ex
));
2841 ext4_ext_dirty(handle
, inode
, path
+ depth
);
2842 /* zero out the first half */
2843 /* blocks available from iblock */
2848 * If there was a change of depth as part of the
2849 * insertion of ex3 above, we need to update the length
2850 * of the ex1 extent again here
2852 if (ex1
&& ex1
!= ex
) {
2854 ex1
->ee_len
= cpu_to_le16(iblock
- ee_block
);
2855 ext4_ext_mark_uninitialized(ex1
);
2858 /* ex2: iblock to iblock + maxblocks-1 : initialised */
2859 ex2
->ee_block
= cpu_to_le32(iblock
);
2860 ext4_ext_store_pblock(ex2
, newblock
);
2861 ex2
->ee_len
= cpu_to_le16(allocated
);
2865 * New (initialized) extent starts from the first block
2866 * in the current extent. i.e., ex2 == ex
2867 * We have to see if it can be merged with the extent
2870 if (ex2
> EXT_FIRST_EXTENT(eh
)) {
2872 * To merge left, pass "ex2 - 1" to try_to_merge(),
2873 * since it merges towards right _only_.
2875 ret
= ext4_ext_try_to_merge(inode
, path
, ex2
- 1);
2877 err
= ext4_ext_correct_indexes(handle
, inode
, path
);
2880 depth
= ext_depth(inode
);
2885 * Try to Merge towards right. This might be required
2886 * only when the whole extent is being written to.
2887 * i.e. ex2 == ex and ex3 == NULL.
2890 ret
= ext4_ext_try_to_merge(inode
, path
, ex2
);
2892 err
= ext4_ext_correct_indexes(handle
, inode
, path
);
2897 /* Mark modified extent as dirty */
2898 err
= ext4_ext_dirty(handle
, inode
, path
+ depth
);
2901 err
= ext4_ext_insert_extent(handle
, inode
, path
, &newex
, 0);
2902 if (err
== -ENOSPC
&& may_zeroout
) {
2903 err
= ext4_ext_zeroout(inode
, &orig_ex
);
2905 goto fix_extent_len
;
2906 /* update the extent length and mark as initialized */
2907 ex
->ee_block
= orig_ex
.ee_block
;
2908 ex
->ee_len
= orig_ex
.ee_len
;
2909 ext4_ext_store_pblock(ex
, ext_pblock(&orig_ex
));
2910 ext4_ext_dirty(handle
, inode
, path
+ depth
);
2911 /* zero out the first half */
2914 goto fix_extent_len
;
2916 ext4_ext_show_leaf(inode
, path
);
2917 return err
? err
: allocated
;
2920 ex
->ee_block
= orig_ex
.ee_block
;
2921 ex
->ee_len
= orig_ex
.ee_len
;
2922 ext4_ext_store_pblock(ex
, ext_pblock(&orig_ex
));
2923 ext4_ext_mark_uninitialized(ex
);
2924 ext4_ext_dirty(handle
, inode
, path
+ depth
);
2929 * This function is called by ext4_ext_get_blocks() from
2930 * ext4_get_blocks_dio_write() when DIO to write
2931 * to an uninitialized extent.
2933 * Writing to an uninitized extent may result in splitting the uninitialized
2934 * extent into multiple /intialized unintialized extents (up to three)
2935 * There are three possibilities:
2936 * a> There is no split required: Entire extent should be uninitialized
2937 * b> Splits in two extents: Write is happening at either end of the extent
2938 * c> Splits in three extents: Somone is writing in middle of the extent
2940 * One of more index blocks maybe needed if the extent tree grow after
2941 * the unintialized extent split. To prevent ENOSPC occur at the IO
2942 * complete, we need to split the uninitialized extent before DIO submit
2943 * the IO. The uninitilized extent called at this time will be split
2944 * into three uninitialized extent(at most). After IO complete, the part
2945 * being filled will be convert to initialized by the end_io callback function
2946 * via ext4_convert_unwritten_extents().
2948 * Returns the size of uninitialized extent to be written on success.
2950 static int ext4_split_unwritten_extents(handle_t
*handle
,
2951 struct inode
*inode
,
2952 struct ext4_ext_path
*path
,
2954 unsigned int max_blocks
,
2957 struct ext4_extent
*ex
, newex
, orig_ex
;
2958 struct ext4_extent
*ex1
= NULL
;
2959 struct ext4_extent
*ex2
= NULL
;
2960 struct ext4_extent
*ex3
= NULL
;
2961 struct ext4_extent_header
*eh
;
2962 ext4_lblk_t ee_block
, eof_block
;
2963 unsigned int allocated
, ee_len
, depth
;
2964 ext4_fsblk_t newblock
;
2968 ext_debug("ext4_split_unwritten_extents: inode %lu, logical"
2969 "block %llu, max_blocks %u\n", inode
->i_ino
,
2970 (unsigned long long)iblock
, max_blocks
);
2972 eof_block
= (inode
->i_size
+ inode
->i_sb
->s_blocksize
- 1) >>
2973 inode
->i_sb
->s_blocksize_bits
;
2974 if (eof_block
< iblock
+ max_blocks
)
2975 eof_block
= iblock
+ max_blocks
;
2977 depth
= ext_depth(inode
);
2978 eh
= path
[depth
].p_hdr
;
2979 ex
= path
[depth
].p_ext
;
2980 ee_block
= le32_to_cpu(ex
->ee_block
);
2981 ee_len
= ext4_ext_get_actual_len(ex
);
2982 allocated
= ee_len
- (iblock
- ee_block
);
2983 newblock
= iblock
- ee_block
+ ext_pblock(ex
);
2986 orig_ex
.ee_block
= ex
->ee_block
;
2987 orig_ex
.ee_len
= cpu_to_le16(ee_len
);
2988 ext4_ext_store_pblock(&orig_ex
, ext_pblock(ex
));
2991 * It is safe to convert extent to initialized via explicit
2992 * zeroout only if extent is fully insde i_size or new_size.
2994 may_zeroout
= ee_block
+ ee_len
<= eof_block
;
2997 * If the uninitialized extent begins at the same logical
2998 * block where the write begins, and the write completely
2999 * covers the extent, then we don't need to split it.
3001 if ((iblock
== ee_block
) && (allocated
<= max_blocks
))
3004 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
3007 /* ex1: ee_block to iblock - 1 : uninitialized */
3008 if (iblock
> ee_block
) {
3010 ex1
->ee_len
= cpu_to_le16(iblock
- ee_block
);
3011 ext4_ext_mark_uninitialized(ex1
);
3015 * for sanity, update the length of the ex2 extent before
3016 * we insert ex3, if ex1 is NULL. This is to avoid temporary
3017 * overlap of blocks.
3019 if (!ex1
&& allocated
> max_blocks
)
3020 ex2
->ee_len
= cpu_to_le16(max_blocks
);
3021 /* ex3: to ee_block + ee_len : uninitialised */
3022 if (allocated
> max_blocks
) {
3023 unsigned int newdepth
;
3025 ex3
->ee_block
= cpu_to_le32(iblock
+ max_blocks
);
3026 ext4_ext_store_pblock(ex3
, newblock
+ max_blocks
);
3027 ex3
->ee_len
= cpu_to_le16(allocated
- max_blocks
);
3028 ext4_ext_mark_uninitialized(ex3
);
3029 err
= ext4_ext_insert_extent(handle
, inode
, path
, ex3
, flags
);
3030 if (err
== -ENOSPC
&& may_zeroout
) {
3031 err
= ext4_ext_zeroout(inode
, &orig_ex
);
3033 goto fix_extent_len
;
3034 /* update the extent length and mark as initialized */
3035 ex
->ee_block
= orig_ex
.ee_block
;
3036 ex
->ee_len
= orig_ex
.ee_len
;
3037 ext4_ext_store_pblock(ex
, ext_pblock(&orig_ex
));
3038 ext4_ext_dirty(handle
, inode
, path
+ depth
);
3039 /* zeroed the full extent */
3040 /* blocks available from iblock */
3044 goto fix_extent_len
;
3046 * The depth, and hence eh & ex might change
3047 * as part of the insert above.
3049 newdepth
= ext_depth(inode
);
3051 * update the extent length after successful insert of the
3054 ee_len
-= ext4_ext_get_actual_len(ex3
);
3055 orig_ex
.ee_len
= cpu_to_le16(ee_len
);
3056 may_zeroout
= ee_block
+ ee_len
<= eof_block
;
3059 ext4_ext_drop_refs(path
);
3060 path
= ext4_ext_find_extent(inode
, iblock
, path
);
3062 err
= PTR_ERR(path
);
3065 eh
= path
[depth
].p_hdr
;
3066 ex
= path
[depth
].p_ext
;
3070 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
3074 allocated
= max_blocks
;
3077 * If there was a change of depth as part of the
3078 * insertion of ex3 above, we need to update the length
3079 * of the ex1 extent again here
3081 if (ex1
&& ex1
!= ex
) {
3083 ex1
->ee_len
= cpu_to_le16(iblock
- ee_block
);
3084 ext4_ext_mark_uninitialized(ex1
);
3088 * ex2: iblock to iblock + maxblocks-1 : to be direct IO written,
3089 * uninitialised still.
3091 ex2
->ee_block
= cpu_to_le32(iblock
);
3092 ext4_ext_store_pblock(ex2
, newblock
);
3093 ex2
->ee_len
= cpu_to_le16(allocated
);
3094 ext4_ext_mark_uninitialized(ex2
);
3097 /* Mark modified extent as dirty */
3098 err
= ext4_ext_dirty(handle
, inode
, path
+ depth
);
3099 ext_debug("out here\n");
3102 err
= ext4_ext_insert_extent(handle
, inode
, path
, &newex
, flags
);
3103 if (err
== -ENOSPC
&& may_zeroout
) {
3104 err
= ext4_ext_zeroout(inode
, &orig_ex
);
3106 goto fix_extent_len
;
3107 /* update the extent length and mark as initialized */
3108 ex
->ee_block
= orig_ex
.ee_block
;
3109 ex
->ee_len
= orig_ex
.ee_len
;
3110 ext4_ext_store_pblock(ex
, ext_pblock(&orig_ex
));
3111 ext4_ext_dirty(handle
, inode
, path
+ depth
);
3112 /* zero out the first half */
3115 goto fix_extent_len
;
3117 ext4_ext_show_leaf(inode
, path
);
3118 return err
? err
: allocated
;
3121 ex
->ee_block
= orig_ex
.ee_block
;
3122 ex
->ee_len
= orig_ex
.ee_len
;
3123 ext4_ext_store_pblock(ex
, ext_pblock(&orig_ex
));
3124 ext4_ext_mark_uninitialized(ex
);
3125 ext4_ext_dirty(handle
, inode
, path
+ depth
);
3128 static int ext4_convert_unwritten_extents_endio(handle_t
*handle
,
3129 struct inode
*inode
,
3130 struct ext4_ext_path
*path
)
3132 struct ext4_extent
*ex
;
3133 struct ext4_extent_header
*eh
;
3138 depth
= ext_depth(inode
);
3139 eh
= path
[depth
].p_hdr
;
3140 ex
= path
[depth
].p_ext
;
3142 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
3145 /* first mark the extent as initialized */
3146 ext4_ext_mark_initialized(ex
);
3149 * We have to see if it can be merged with the extent
3152 if (ex
> EXT_FIRST_EXTENT(eh
)) {
3154 * To merge left, pass "ex - 1" to try_to_merge(),
3155 * since it merges towards right _only_.
3157 ret
= ext4_ext_try_to_merge(inode
, path
, ex
- 1);
3159 err
= ext4_ext_correct_indexes(handle
, inode
, path
);
3162 depth
= ext_depth(inode
);
3167 * Try to Merge towards right.
3169 ret
= ext4_ext_try_to_merge(inode
, path
, ex
);
3171 err
= ext4_ext_correct_indexes(handle
, inode
, path
);
3174 depth
= ext_depth(inode
);
3176 /* Mark modified extent as dirty */
3177 err
= ext4_ext_dirty(handle
, inode
, path
+ depth
);
3179 ext4_ext_show_leaf(inode
, path
);
3183 static void unmap_underlying_metadata_blocks(struct block_device
*bdev
,
3184 sector_t block
, int count
)
3187 for (i
= 0; i
< count
; i
++)
3188 unmap_underlying_metadata(bdev
, block
+ i
);
3192 ext4_ext_handle_uninitialized_extents(handle_t
*handle
, struct inode
*inode
,
3193 ext4_lblk_t iblock
, unsigned int max_blocks
,
3194 struct ext4_ext_path
*path
, int flags
,
3195 unsigned int allocated
, struct buffer_head
*bh_result
,
3196 ext4_fsblk_t newblock
)
3200 ext4_io_end_t
*io
= EXT4_I(inode
)->cur_aio_dio
;
3202 ext_debug("ext4_ext_handle_uninitialized_extents: inode %lu, logical"
3203 "block %llu, max_blocks %u, flags %d, allocated %u",
3204 inode
->i_ino
, (unsigned long long)iblock
, max_blocks
,
3206 ext4_ext_show_leaf(inode
, path
);
3208 /* get_block() before submit the IO, split the extent */
3209 if ((flags
& EXT4_GET_BLOCKS_PRE_IO
)) {
3210 ret
= ext4_split_unwritten_extents(handle
,
3211 inode
, path
, iblock
,
3214 * Flag the inode(non aio case) or end_io struct (aio case)
3215 * that this IO needs to convertion to written when IO is
3219 io
->flag
= EXT4_IO_UNWRITTEN
;
3221 ext4_set_inode_state(inode
, EXT4_STATE_DIO_UNWRITTEN
);
3222 if (ext4_should_dioread_nolock(inode
))
3223 set_buffer_uninit(bh_result
);
3226 /* IO end_io complete, convert the filled extent to written */
3227 if ((flags
& EXT4_GET_BLOCKS_CONVERT
)) {
3228 ret
= ext4_convert_unwritten_extents_endio(handle
, inode
,
3231 ext4_update_inode_fsync_trans(handle
, inode
, 1);
3234 /* buffered IO case */
3236 * repeat fallocate creation request
3237 * we already have an unwritten extent
3239 if (flags
& EXT4_GET_BLOCKS_UNINIT_EXT
)
3242 /* buffered READ or buffered write_begin() lookup */
3243 if ((flags
& EXT4_GET_BLOCKS_CREATE
) == 0) {
3245 * We have blocks reserved already. We
3246 * return allocated blocks so that delalloc
3247 * won't do block reservation for us. But
3248 * the buffer head will be unmapped so that
3249 * a read from the block returns 0s.
3251 set_buffer_unwritten(bh_result
);
3255 /* buffered write, writepage time, convert*/
3256 ret
= ext4_ext_convert_to_initialized(handle
, inode
,
3260 ext4_update_inode_fsync_trans(handle
, inode
, 1);
3267 set_buffer_new(bh_result
);
3269 * if we allocated more blocks than requested
3270 * we need to make sure we unmap the extra block
3271 * allocated. The actual needed block will get
3272 * unmapped later when we find the buffer_head marked
3275 if (allocated
> max_blocks
) {
3276 unmap_underlying_metadata_blocks(inode
->i_sb
->s_bdev
,
3277 newblock
+ max_blocks
,
3278 allocated
- max_blocks
);
3279 allocated
= max_blocks
;
3283 * If we have done fallocate with the offset that is already
3284 * delayed allocated, we would have block reservation
3285 * and quota reservation done in the delayed write path.
3286 * But fallocate would have already updated quota and block
3287 * count for this offset. So cancel these reservation
3289 if (flags
& EXT4_GET_BLOCKS_DELALLOC_RESERVE
)
3290 ext4_da_update_reserve_space(inode
, allocated
, 0);
3293 set_buffer_mapped(bh_result
);
3295 if (allocated
> max_blocks
)
3296 allocated
= max_blocks
;
3297 ext4_ext_show_leaf(inode
, path
);
3298 bh_result
->b_bdev
= inode
->i_sb
->s_bdev
;
3299 bh_result
->b_blocknr
= newblock
;
3302 ext4_ext_drop_refs(path
);
3305 return err
? err
: allocated
;
3308 * Block allocation/map/preallocation routine for extents based files
3311 * Need to be called with
3312 * down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system block
3313 * (ie, create is zero). Otherwise down_write(&EXT4_I(inode)->i_data_sem)
3315 * return > 0, number of of blocks already mapped/allocated
3316 * if create == 0 and these are pre-allocated blocks
3317 * buffer head is unmapped
3318 * otherwise blocks are mapped
3320 * return = 0, if plain look up failed (blocks have not been allocated)
3321 * buffer head is unmapped
3323 * return < 0, error case.
3325 int ext4_ext_get_blocks(handle_t
*handle
, struct inode
*inode
,
3327 unsigned int max_blocks
, struct buffer_head
*bh_result
,
3330 struct ext4_ext_path
*path
= NULL
;
3331 struct ext4_extent_header
*eh
;
3332 struct ext4_extent newex
, *ex
, *last_ex
;
3333 ext4_fsblk_t newblock
;
3334 int i
, err
= 0, depth
, ret
, cache_type
;
3335 unsigned int allocated
= 0;
3336 struct ext4_allocation_request ar
;
3337 ext4_io_end_t
*io
= EXT4_I(inode
)->cur_aio_dio
;
3339 __clear_bit(BH_New
, &bh_result
->b_state
);
3340 ext_debug("blocks %u/%u requested for inode %lu\n",
3341 iblock
, max_blocks
, inode
->i_ino
);
3343 /* check in cache */
3344 cache_type
= ext4_ext_in_cache(inode
, iblock
, &newex
);
3346 if (cache_type
== EXT4_EXT_CACHE_GAP
) {
3347 if ((flags
& EXT4_GET_BLOCKS_CREATE
) == 0) {
3349 * block isn't allocated yet and
3350 * user doesn't want to allocate it
3354 /* we should allocate requested block */
3355 } else if (cache_type
== EXT4_EXT_CACHE_EXTENT
) {
3356 /* block is already allocated */
3358 - le32_to_cpu(newex
.ee_block
)
3359 + ext_pblock(&newex
);
3360 /* number of remaining blocks in the extent */
3361 allocated
= ext4_ext_get_actual_len(&newex
) -
3362 (iblock
- le32_to_cpu(newex
.ee_block
));
3369 /* find extent for this block */
3370 path
= ext4_ext_find_extent(inode
, iblock
, NULL
);
3372 err
= PTR_ERR(path
);
3377 depth
= ext_depth(inode
);
3380 * consistent leaf must not be empty;
3381 * this situation is possible, though, _during_ tree modification;
3382 * this is why assert can't be put in ext4_ext_find_extent()
3384 if (unlikely(path
[depth
].p_ext
== NULL
&& depth
!= 0)) {
3385 EXT4_ERROR_INODE(inode
, "bad extent address "
3386 "iblock: %lu, depth: %d pblock %lld",
3387 (unsigned long) iblock
, depth
,
3388 path
[depth
].p_block
);
3392 eh
= path
[depth
].p_hdr
;
3394 ex
= path
[depth
].p_ext
;
3396 ext4_lblk_t ee_block
= le32_to_cpu(ex
->ee_block
);
3397 ext4_fsblk_t ee_start
= ext_pblock(ex
);
3398 unsigned short ee_len
;
3401 * Uninitialized extents are treated as holes, except that
3402 * we split out initialized portions during a write.
3404 ee_len
= ext4_ext_get_actual_len(ex
);
3405 /* if found extent covers block, simply return it */
3406 if (in_range(iblock
, ee_block
, ee_len
)) {
3407 newblock
= iblock
- ee_block
+ ee_start
;
3408 /* number of remaining blocks in the extent */
3409 allocated
= ee_len
- (iblock
- ee_block
);
3410 ext_debug("%u fit into %u:%d -> %llu\n", iblock
,
3411 ee_block
, ee_len
, newblock
);
3413 /* Do not put uninitialized extent in the cache */
3414 if (!ext4_ext_is_uninitialized(ex
)) {
3415 ext4_ext_put_in_cache(inode
, ee_block
,
3417 EXT4_EXT_CACHE_EXTENT
);
3420 ret
= ext4_ext_handle_uninitialized_extents(handle
,
3421 inode
, iblock
, max_blocks
, path
,
3422 flags
, allocated
, bh_result
, newblock
);
3428 * requested block isn't allocated yet;
3429 * we couldn't try to create block if create flag is zero
3431 if ((flags
& EXT4_GET_BLOCKS_CREATE
) == 0) {
3433 * put just found gap into cache to speed up
3434 * subsequent requests
3436 ext4_ext_put_gap_in_cache(inode
, path
, iblock
);
3440 * Okay, we need to do block allocation.
3443 /* find neighbour allocated blocks */
3445 err
= ext4_ext_search_left(inode
, path
, &ar
.lleft
, &ar
.pleft
);
3449 err
= ext4_ext_search_right(inode
, path
, &ar
.lright
, &ar
.pright
);
3454 * See if request is beyond maximum number of blocks we can have in
3455 * a single extent. For an initialized extent this limit is
3456 * EXT_INIT_MAX_LEN and for an uninitialized extent this limit is
3457 * EXT_UNINIT_MAX_LEN.
3459 if (max_blocks
> EXT_INIT_MAX_LEN
&&
3460 !(flags
& EXT4_GET_BLOCKS_UNINIT_EXT
))
3461 max_blocks
= EXT_INIT_MAX_LEN
;
3462 else if (max_blocks
> EXT_UNINIT_MAX_LEN
&&
3463 (flags
& EXT4_GET_BLOCKS_UNINIT_EXT
))
3464 max_blocks
= EXT_UNINIT_MAX_LEN
;
3466 /* Check if we can really insert (iblock)::(iblock+max_blocks) extent */
3467 newex
.ee_block
= cpu_to_le32(iblock
);
3468 newex
.ee_len
= cpu_to_le16(max_blocks
);
3469 err
= ext4_ext_check_overlap(inode
, &newex
, path
);
3471 allocated
= ext4_ext_get_actual_len(&newex
);
3473 allocated
= max_blocks
;
3475 /* allocate new block */
3477 ar
.goal
= ext4_ext_find_goal(inode
, path
, iblock
);
3478 ar
.logical
= iblock
;
3480 if (S_ISREG(inode
->i_mode
))
3481 ar
.flags
= EXT4_MB_HINT_DATA
;
3483 /* disable in-core preallocation for non-regular files */
3485 newblock
= ext4_mb_new_blocks(handle
, &ar
, &err
);
3488 ext_debug("allocate new block: goal %llu, found %llu/%u\n",
3489 ar
.goal
, newblock
, allocated
);
3491 /* try to insert new extent into found leaf and return */
3492 ext4_ext_store_pblock(&newex
, newblock
);
3493 newex
.ee_len
= cpu_to_le16(ar
.len
);
3494 /* Mark uninitialized */
3495 if (flags
& EXT4_GET_BLOCKS_UNINIT_EXT
){
3496 ext4_ext_mark_uninitialized(&newex
);
3498 * io_end structure was created for every IO write to an
3499 * uninitialized extent. To avoid unecessary conversion,
3500 * here we flag the IO that really needs the conversion.
3501 * For non asycn direct IO case, flag the inode state
3502 * that we need to perform convertion when IO is done.
3504 if ((flags
& EXT4_GET_BLOCKS_PRE_IO
)) {
3506 io
->flag
= EXT4_IO_UNWRITTEN
;
3508 ext4_set_inode_state(inode
,
3509 EXT4_STATE_DIO_UNWRITTEN
);
3511 if (ext4_should_dioread_nolock(inode
))
3512 set_buffer_uninit(bh_result
);
3515 if (unlikely(ext4_test_inode_flag(inode
, EXT4_INODE_EOFBLOCKS
))) {
3516 if (unlikely(!eh
->eh_entries
)) {
3517 EXT4_ERROR_INODE(inode
,
3518 "eh->eh_entries == 0 and "
3519 "EOFBLOCKS_FL set");
3523 last_ex
= EXT_LAST_EXTENT(eh
);
3525 * If the current leaf block was reached by looking at
3526 * the last index block all the way down the tree, and
3527 * we are extending the inode beyond the last extent
3528 * in the current leaf block, then clear the
3529 * EOFBLOCKS_FL flag.
3531 for (i
= depth
-1; i
>= 0; i
--) {
3532 if (path
[i
].p_idx
!= EXT_LAST_INDEX(path
[i
].p_hdr
))
3536 (iblock
+ ar
.len
> le32_to_cpu(last_ex
->ee_block
) +
3537 ext4_ext_get_actual_len(last_ex
)))
3538 ext4_clear_inode_flag(inode
, EXT4_INODE_EOFBLOCKS
);
3540 err
= ext4_ext_insert_extent(handle
, inode
, path
, &newex
, flags
);
3542 /* free data blocks we just allocated */
3543 /* not a good idea to call discard here directly,
3544 * but otherwise we'd need to call it every free() */
3545 ext4_discard_preallocations(inode
);
3546 ext4_free_blocks(handle
, inode
, 0, ext_pblock(&newex
),
3547 ext4_ext_get_actual_len(&newex
), 0);
3551 /* previous routine could use block we allocated */
3552 newblock
= ext_pblock(&newex
);
3553 allocated
= ext4_ext_get_actual_len(&newex
);
3554 if (allocated
> max_blocks
)
3555 allocated
= max_blocks
;
3556 set_buffer_new(bh_result
);
3559 * Update reserved blocks/metadata blocks after successful
3560 * block allocation which had been deferred till now.
3562 if (flags
& EXT4_GET_BLOCKS_DELALLOC_RESERVE
)
3563 ext4_da_update_reserve_space(inode
, allocated
, 1);
3566 * Cache the extent and update transaction to commit on fdatasync only
3567 * when it is _not_ an uninitialized extent.
3569 if ((flags
& EXT4_GET_BLOCKS_UNINIT_EXT
) == 0) {
3570 ext4_ext_put_in_cache(inode
, iblock
, allocated
, newblock
,
3571 EXT4_EXT_CACHE_EXTENT
);
3572 ext4_update_inode_fsync_trans(handle
, inode
, 1);
3574 ext4_update_inode_fsync_trans(handle
, inode
, 0);
3576 if (allocated
> max_blocks
)
3577 allocated
= max_blocks
;
3578 ext4_ext_show_leaf(inode
, path
);
3579 set_buffer_mapped(bh_result
);
3580 bh_result
->b_bdev
= inode
->i_sb
->s_bdev
;
3581 bh_result
->b_blocknr
= newblock
;
3584 ext4_ext_drop_refs(path
);
3587 return err
? err
: allocated
;
3590 void ext4_ext_truncate(struct inode
*inode
)
3592 struct address_space
*mapping
= inode
->i_mapping
;
3593 struct super_block
*sb
= inode
->i_sb
;
3594 ext4_lblk_t last_block
;
3599 * probably first extent we're gonna free will be last in block
3601 err
= ext4_writepage_trans_blocks(inode
);
3602 handle
= ext4_journal_start(inode
, err
);
3606 if (inode
->i_size
& (sb
->s_blocksize
- 1))
3607 ext4_block_truncate_page(handle
, mapping
, inode
->i_size
);
3609 if (ext4_orphan_add(handle
, inode
))
3612 down_write(&EXT4_I(inode
)->i_data_sem
);
3613 ext4_ext_invalidate_cache(inode
);
3615 ext4_discard_preallocations(inode
);
3618 * TODO: optimization is possible here.
3619 * Probably we need not scan at all,
3620 * because page truncation is enough.
3623 /* we have to know where to truncate from in crash case */
3624 EXT4_I(inode
)->i_disksize
= inode
->i_size
;
3625 ext4_mark_inode_dirty(handle
, inode
);
3627 last_block
= (inode
->i_size
+ sb
->s_blocksize
- 1)
3628 >> EXT4_BLOCK_SIZE_BITS(sb
);
3629 err
= ext4_ext_remove_space(inode
, last_block
);
3631 /* In a multi-transaction truncate, we only make the final
3632 * transaction synchronous.
3635 ext4_handle_sync(handle
);
3638 up_write(&EXT4_I(inode
)->i_data_sem
);
3640 * If this was a simple ftruncate() and the file will remain alive,
3641 * then we need to clear up the orphan record which we created above.
3642 * However, if this was a real unlink then we were called by
3643 * ext4_delete_inode(), and we allow that function to clean up the
3644 * orphan info for us.
3647 ext4_orphan_del(handle
, inode
);
3649 inode
->i_mtime
= inode
->i_ctime
= ext4_current_time(inode
);
3650 ext4_mark_inode_dirty(handle
, inode
);
3651 ext4_journal_stop(handle
);
3654 static void ext4_falloc_update_inode(struct inode
*inode
,
3655 int mode
, loff_t new_size
, int update_ctime
)
3657 struct timespec now
;
3660 now
= current_fs_time(inode
->i_sb
);
3661 if (!timespec_equal(&inode
->i_ctime
, &now
))
3662 inode
->i_ctime
= now
;
3665 * Update only when preallocation was requested beyond
3668 if (!(mode
& FALLOC_FL_KEEP_SIZE
)) {
3669 if (new_size
> i_size_read(inode
))
3670 i_size_write(inode
, new_size
);
3671 if (new_size
> EXT4_I(inode
)->i_disksize
)
3672 ext4_update_i_disksize(inode
, new_size
);
3675 * Mark that we allocate beyond EOF so the subsequent truncate
3676 * can proceed even if the new size is the same as i_size.
3678 if (new_size
> i_size_read(inode
))
3679 ext4_set_inode_flag(inode
, EXT4_INODE_EOFBLOCKS
);
3685 * preallocate space for a file. This implements ext4's fallocate inode
3686 * operation, which gets called from sys_fallocate system call.
3687 * For block-mapped files, posix_fallocate should fall back to the method
3688 * of writing zeroes to the required new blocks (the same behavior which is
3689 * expected for file systems which do not support fallocate() system call).
3691 long ext4_fallocate(struct inode
*inode
, int mode
, loff_t offset
, loff_t len
)
3696 unsigned int max_blocks
;
3700 struct buffer_head map_bh
;
3701 unsigned int credits
, blkbits
= inode
->i_blkbits
;
3704 * currently supporting (pre)allocate mode for extent-based
3707 if (!(ext4_test_inode_flag(inode
, EXT4_INODE_EXTENTS
)))
3710 /* preallocation to directories is currently not supported */
3711 if (S_ISDIR(inode
->i_mode
))
3714 block
= offset
>> blkbits
;
3716 * We can't just convert len to max_blocks because
3717 * If blocksize = 4096 offset = 3072 and len = 2048
3719 max_blocks
= (EXT4_BLOCK_ALIGN(len
+ offset
, blkbits
) >> blkbits
)
3722 * credits to insert 1 extent into extent tree
3724 credits
= ext4_chunk_trans_blocks(inode
, max_blocks
);
3725 mutex_lock(&inode
->i_mutex
);
3726 ret
= inode_newsize_ok(inode
, (len
+ offset
));
3728 mutex_unlock(&inode
->i_mutex
);
3732 while (ret
>= 0 && ret
< max_blocks
) {
3733 block
= block
+ ret
;
3734 max_blocks
= max_blocks
- ret
;
3735 handle
= ext4_journal_start(inode
, credits
);
3736 if (IS_ERR(handle
)) {
3737 ret
= PTR_ERR(handle
);
3741 ret
= ext4_get_blocks(handle
, inode
, block
,
3742 max_blocks
, &map_bh
,
3743 EXT4_GET_BLOCKS_CREATE_UNINIT_EXT
);
3747 printk(KERN_ERR
"%s: ext4_ext_get_blocks "
3748 "returned error inode#%lu, block=%u, "
3749 "max_blocks=%u", __func__
,
3750 inode
->i_ino
, block
, max_blocks
);
3752 ext4_mark_inode_dirty(handle
, inode
);
3753 ret2
= ext4_journal_stop(handle
);
3756 if ((block
+ ret
) >= (EXT4_BLOCK_ALIGN(offset
+ len
,
3757 blkbits
) >> blkbits
))
3758 new_size
= offset
+ len
;
3760 new_size
= (block
+ ret
) << blkbits
;
3762 ext4_falloc_update_inode(inode
, mode
, new_size
,
3763 buffer_new(&map_bh
));
3764 ext4_mark_inode_dirty(handle
, inode
);
3765 ret2
= ext4_journal_stop(handle
);
3769 if (ret
== -ENOSPC
&&
3770 ext4_should_retry_alloc(inode
->i_sb
, &retries
)) {
3774 mutex_unlock(&inode
->i_mutex
);
3775 return ret
> 0 ? ret2
: ret
;
3779 * This function convert a range of blocks to written extents
3780 * The caller of this function will pass the start offset and the size.
3781 * all unwritten extents within this range will be converted to
3784 * This function is called from the direct IO end io call back
3785 * function, to convert the fallocated extents after IO is completed.
3786 * Returns 0 on success.
3788 int ext4_convert_unwritten_extents(struct inode
*inode
, loff_t offset
,
3793 unsigned int max_blocks
;
3796 struct buffer_head map_bh
;
3797 unsigned int credits
, blkbits
= inode
->i_blkbits
;
3799 block
= offset
>> blkbits
;
3801 * We can't just convert len to max_blocks because
3802 * If blocksize = 4096 offset = 3072 and len = 2048
3804 max_blocks
= (EXT4_BLOCK_ALIGN(len
+ offset
, blkbits
) >> blkbits
)
3807 * credits to insert 1 extent into extent tree
3809 credits
= ext4_chunk_trans_blocks(inode
, max_blocks
);
3810 while (ret
>= 0 && ret
< max_blocks
) {
3811 block
= block
+ ret
;
3812 max_blocks
= max_blocks
- ret
;
3813 handle
= ext4_journal_start(inode
, credits
);
3814 if (IS_ERR(handle
)) {
3815 ret
= PTR_ERR(handle
);
3819 ret
= ext4_get_blocks(handle
, inode
, block
,
3820 max_blocks
, &map_bh
,
3821 EXT4_GET_BLOCKS_IO_CONVERT_EXT
);
3824 printk(KERN_ERR
"%s: ext4_ext_get_blocks "
3825 "returned error inode#%lu, block=%u, "
3826 "max_blocks=%u", __func__
,
3827 inode
->i_ino
, block
, max_blocks
);
3829 ext4_mark_inode_dirty(handle
, inode
);
3830 ret2
= ext4_journal_stop(handle
);
3831 if (ret
<= 0 || ret2
)
3834 return ret
> 0 ? ret2
: ret
;
3837 * Callback function called for each extent to gather FIEMAP information.
3839 static int ext4_ext_fiemap_cb(struct inode
*inode
, struct ext4_ext_path
*path
,
3840 struct ext4_ext_cache
*newex
, struct ext4_extent
*ex
,
3843 struct fiemap_extent_info
*fieinfo
= data
;
3844 unsigned char blksize_bits
= inode
->i_sb
->s_blocksize_bits
;
3851 logical
= (__u64
)newex
->ec_block
<< blksize_bits
;
3853 if (newex
->ec_type
== EXT4_EXT_CACHE_GAP
) {
3856 struct buffer_head
*bh
= NULL
;
3858 offset
= logical
>> PAGE_SHIFT
;
3859 page
= find_get_page(inode
->i_mapping
, offset
);
3860 if (!page
|| !page_has_buffers(page
))
3861 return EXT_CONTINUE
;
3863 bh
= page_buffers(page
);
3866 return EXT_CONTINUE
;
3868 if (buffer_delay(bh
)) {
3869 flags
|= FIEMAP_EXTENT_DELALLOC
;
3870 page_cache_release(page
);
3872 page_cache_release(page
);
3873 return EXT_CONTINUE
;
3877 physical
= (__u64
)newex
->ec_start
<< blksize_bits
;
3878 length
= (__u64
)newex
->ec_len
<< blksize_bits
;
3880 if (ex
&& ext4_ext_is_uninitialized(ex
))
3881 flags
|= FIEMAP_EXTENT_UNWRITTEN
;
3884 * If this extent reaches EXT_MAX_BLOCK, it must be last.
3886 * Or if ext4_ext_next_allocated_block is EXT_MAX_BLOCK,
3887 * this also indicates no more allocated blocks.
3889 * XXX this might miss a single-block extent at EXT_MAX_BLOCK
3891 if (ext4_ext_next_allocated_block(path
) == EXT_MAX_BLOCK
||
3892 newex
->ec_block
+ newex
->ec_len
- 1 == EXT_MAX_BLOCK
) {
3893 loff_t size
= i_size_read(inode
);
3894 loff_t bs
= EXT4_BLOCK_SIZE(inode
->i_sb
);
3896 flags
|= FIEMAP_EXTENT_LAST
;
3897 if ((flags
& FIEMAP_EXTENT_DELALLOC
) &&
3898 logical
+length
> size
)
3899 length
= (size
- logical
+ bs
- 1) & ~(bs
-1);
3902 error
= fiemap_fill_next_extent(fieinfo
, logical
, physical
,
3909 return EXT_CONTINUE
;
3912 /* fiemap flags we can handle specified here */
3913 #define EXT4_FIEMAP_FLAGS (FIEMAP_FLAG_SYNC|FIEMAP_FLAG_XATTR)
3915 static int ext4_xattr_fiemap(struct inode
*inode
,
3916 struct fiemap_extent_info
*fieinfo
)
3920 __u32 flags
= FIEMAP_EXTENT_LAST
;
3921 int blockbits
= inode
->i_sb
->s_blocksize_bits
;
3925 if (ext4_test_inode_state(inode
, EXT4_STATE_XATTR
)) {
3926 struct ext4_iloc iloc
;
3927 int offset
; /* offset of xattr in inode */
3929 error
= ext4_get_inode_loc(inode
, &iloc
);
3932 physical
= iloc
.bh
->b_blocknr
<< blockbits
;
3933 offset
= EXT4_GOOD_OLD_INODE_SIZE
+
3934 EXT4_I(inode
)->i_extra_isize
;
3936 length
= EXT4_SB(inode
->i_sb
)->s_inode_size
- offset
;
3937 flags
|= FIEMAP_EXTENT_DATA_INLINE
;
3939 } else { /* external block */
3940 physical
= EXT4_I(inode
)->i_file_acl
<< blockbits
;
3941 length
= inode
->i_sb
->s_blocksize
;
3945 error
= fiemap_fill_next_extent(fieinfo
, 0, physical
,
3947 return (error
< 0 ? error
: 0);
3950 int ext4_fiemap(struct inode
*inode
, struct fiemap_extent_info
*fieinfo
,
3951 __u64 start
, __u64 len
)
3953 ext4_lblk_t start_blk
;
3956 /* fallback to generic here if not in extents fmt */
3957 if (!(ext4_test_inode_flag(inode
, EXT4_INODE_EXTENTS
)))
3958 return generic_block_fiemap(inode
, fieinfo
, start
, len
,
3961 if (fiemap_check_flags(fieinfo
, EXT4_FIEMAP_FLAGS
))
3964 if (fieinfo
->fi_flags
& FIEMAP_FLAG_XATTR
) {
3965 error
= ext4_xattr_fiemap(inode
, fieinfo
);
3967 ext4_lblk_t len_blks
;
3970 start_blk
= start
>> inode
->i_sb
->s_blocksize_bits
;
3971 last_blk
= (start
+ len
- 1) >> inode
->i_sb
->s_blocksize_bits
;
3972 if (last_blk
>= EXT_MAX_BLOCK
)
3973 last_blk
= EXT_MAX_BLOCK
-1;
3974 len_blks
= ((ext4_lblk_t
) last_blk
) - start_blk
+ 1;
3977 * Walk the extent tree gathering extent information.
3978 * ext4_ext_fiemap_cb will push extents back to user.
3980 error
= ext4_ext_walk_space(inode
, start_blk
, len_blks
,
3981 ext4_ext_fiemap_cb
, fieinfo
);