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/ext4_jbd2.h>
36 #include <linux/jbd.h>
37 #include <linux/highuid.h>
38 #include <linux/pagemap.h>
39 #include <linux/quotaops.h>
40 #include <linux/string.h>
41 #include <linux/slab.h>
42 #include <linux/falloc.h>
43 #include <linux/ext4_fs_extents.h>
44 #include <asm/uaccess.h>
49 * combine low and high parts of physical block number into ext4_fsblk_t
51 static ext4_fsblk_t
ext_pblock(struct ext4_extent
*ex
)
55 block
= le32_to_cpu(ex
->ee_start
);
56 block
|= ((ext4_fsblk_t
) le16_to_cpu(ex
->ee_start_hi
) << 31) << 1;
62 * combine low and high parts of a leaf physical block number into ext4_fsblk_t
64 static ext4_fsblk_t
idx_pblock(struct ext4_extent_idx
*ix
)
68 block
= le32_to_cpu(ix
->ei_leaf
);
69 block
|= ((ext4_fsblk_t
) le16_to_cpu(ix
->ei_leaf_hi
) << 31) << 1;
74 * ext4_ext_store_pblock:
75 * stores a large physical block number into an extent struct,
76 * breaking it into parts
78 static void ext4_ext_store_pblock(struct ext4_extent
*ex
, ext4_fsblk_t pb
)
80 ex
->ee_start
= cpu_to_le32((unsigned long) (pb
& 0xffffffff));
81 ex
->ee_start_hi
= cpu_to_le16((unsigned long) ((pb
>> 31) >> 1) & 0xffff);
85 * ext4_idx_store_pblock:
86 * stores a large physical block number into an index struct,
87 * breaking it into parts
89 static void ext4_idx_store_pblock(struct ext4_extent_idx
*ix
, ext4_fsblk_t pb
)
91 ix
->ei_leaf
= cpu_to_le32((unsigned long) (pb
& 0xffffffff));
92 ix
->ei_leaf_hi
= cpu_to_le16((unsigned long) ((pb
>> 31) >> 1) & 0xffff);
95 static handle_t
*ext4_ext_journal_restart(handle_t
*handle
, int needed
)
99 if (handle
->h_buffer_credits
> needed
)
101 if (!ext4_journal_extend(handle
, needed
))
103 err
= ext4_journal_restart(handle
, needed
);
113 static int ext4_ext_get_access(handle_t
*handle
, struct inode
*inode
,
114 struct ext4_ext_path
*path
)
117 /* path points to block */
118 return ext4_journal_get_write_access(handle
, path
->p_bh
);
120 /* path points to leaf/index in inode body */
121 /* we use in-core data, no need to protect them */
131 static int ext4_ext_dirty(handle_t
*handle
, struct inode
*inode
,
132 struct ext4_ext_path
*path
)
136 /* path points to block */
137 err
= ext4_journal_dirty_metadata(handle
, path
->p_bh
);
139 /* path points to leaf/index in inode body */
140 err
= ext4_mark_inode_dirty(handle
, inode
);
145 static ext4_fsblk_t
ext4_ext_find_goal(struct inode
*inode
,
146 struct ext4_ext_path
*path
,
149 struct ext4_inode_info
*ei
= EXT4_I(inode
);
150 ext4_fsblk_t bg_start
;
151 ext4_grpblk_t colour
;
155 struct ext4_extent
*ex
;
156 depth
= path
->p_depth
;
158 /* try to predict block placement */
159 ex
= path
[depth
].p_ext
;
161 return ext_pblock(ex
)+(block
-le32_to_cpu(ex
->ee_block
));
163 /* it looks like index is empty;
164 * try to find starting block from index itself */
165 if (path
[depth
].p_bh
)
166 return path
[depth
].p_bh
->b_blocknr
;
169 /* OK. use inode's group */
170 bg_start
= (ei
->i_block_group
* EXT4_BLOCKS_PER_GROUP(inode
->i_sb
)) +
171 le32_to_cpu(EXT4_SB(inode
->i_sb
)->s_es
->s_first_data_block
);
172 colour
= (current
->pid
% 16) *
173 (EXT4_BLOCKS_PER_GROUP(inode
->i_sb
) / 16);
174 return bg_start
+ colour
+ block
;
178 ext4_ext_new_block(handle_t
*handle
, struct inode
*inode
,
179 struct ext4_ext_path
*path
,
180 struct ext4_extent
*ex
, int *err
)
182 ext4_fsblk_t goal
, newblock
;
184 goal
= ext4_ext_find_goal(inode
, path
, le32_to_cpu(ex
->ee_block
));
185 newblock
= ext4_new_block(handle
, inode
, goal
, err
);
189 static int ext4_ext_space_block(struct inode
*inode
)
193 size
= (inode
->i_sb
->s_blocksize
- sizeof(struct ext4_extent_header
))
194 / sizeof(struct ext4_extent
);
195 #ifdef AGGRESSIVE_TEST
202 static int ext4_ext_space_block_idx(struct inode
*inode
)
206 size
= (inode
->i_sb
->s_blocksize
- sizeof(struct ext4_extent_header
))
207 / sizeof(struct ext4_extent_idx
);
208 #ifdef AGGRESSIVE_TEST
215 static int ext4_ext_space_root(struct inode
*inode
)
219 size
= sizeof(EXT4_I(inode
)->i_data
);
220 size
-= sizeof(struct ext4_extent_header
);
221 size
/= sizeof(struct ext4_extent
);
222 #ifdef AGGRESSIVE_TEST
229 static int ext4_ext_space_root_idx(struct inode
*inode
)
233 size
= sizeof(EXT4_I(inode
)->i_data
);
234 size
-= sizeof(struct ext4_extent_header
);
235 size
/= sizeof(struct ext4_extent_idx
);
236 #ifdef AGGRESSIVE_TEST
244 ext4_ext_max_entries(struct inode
*inode
, int depth
)
248 if (depth
== ext_depth(inode
)) {
250 max
= ext4_ext_space_root(inode
);
252 max
= ext4_ext_space_root_idx(inode
);
255 max
= ext4_ext_space_block(inode
);
257 max
= ext4_ext_space_block_idx(inode
);
263 static int __ext4_ext_check_header(const char *function
, struct inode
*inode
,
264 struct ext4_extent_header
*eh
,
267 const char *error_msg
;
270 if (unlikely(eh
->eh_magic
!= EXT4_EXT_MAGIC
)) {
271 error_msg
= "invalid magic";
274 if (unlikely(le16_to_cpu(eh
->eh_depth
) != depth
)) {
275 error_msg
= "unexpected eh_depth";
278 if (unlikely(eh
->eh_max
== 0)) {
279 error_msg
= "invalid eh_max";
282 max
= ext4_ext_max_entries(inode
, depth
);
283 if (unlikely(le16_to_cpu(eh
->eh_max
) > max
)) {
284 error_msg
= "too large eh_max";
287 if (unlikely(le16_to_cpu(eh
->eh_entries
) > le16_to_cpu(eh
->eh_max
))) {
288 error_msg
= "invalid eh_entries";
294 ext4_error(inode
->i_sb
, function
,
295 "bad header in inode #%lu: %s - magic %x, "
296 "entries %u, max %u(%u), depth %u(%u)",
297 inode
->i_ino
, error_msg
, le16_to_cpu(eh
->eh_magic
),
298 le16_to_cpu(eh
->eh_entries
), le16_to_cpu(eh
->eh_max
),
299 max
, le16_to_cpu(eh
->eh_depth
), depth
);
304 #define ext4_ext_check_header(inode, eh, depth) \
305 __ext4_ext_check_header(__FUNCTION__, inode, eh, depth)
308 static void ext4_ext_show_path(struct inode
*inode
, struct ext4_ext_path
*path
)
310 int k
, l
= path
->p_depth
;
313 for (k
= 0; k
<= l
; k
++, path
++) {
315 ext_debug(" %d->%llu", le32_to_cpu(path
->p_idx
->ei_block
),
316 idx_pblock(path
->p_idx
));
317 } else if (path
->p_ext
) {
318 ext_debug(" %d:%d:%llu ",
319 le32_to_cpu(path
->p_ext
->ee_block
),
320 ext4_ext_get_actual_len(path
->p_ext
),
321 ext_pblock(path
->p_ext
));
328 static void ext4_ext_show_leaf(struct inode
*inode
, struct ext4_ext_path
*path
)
330 int depth
= ext_depth(inode
);
331 struct ext4_extent_header
*eh
;
332 struct ext4_extent
*ex
;
338 eh
= path
[depth
].p_hdr
;
339 ex
= EXT_FIRST_EXTENT(eh
);
341 for (i
= 0; i
< le16_to_cpu(eh
->eh_entries
); i
++, ex
++) {
342 ext_debug("%d:%d:%llu ", le32_to_cpu(ex
->ee_block
),
343 ext4_ext_get_actual_len(ex
), ext_pblock(ex
));
348 #define ext4_ext_show_path(inode,path)
349 #define ext4_ext_show_leaf(inode,path)
352 static void ext4_ext_drop_refs(struct ext4_ext_path
*path
)
354 int depth
= path
->p_depth
;
357 for (i
= 0; i
<= depth
; i
++, path
++)
365 * ext4_ext_binsearch_idx:
366 * binary search for the closest index of the given block
367 * the header must be checked before calling this
370 ext4_ext_binsearch_idx(struct inode
*inode
, struct ext4_ext_path
*path
, int block
)
372 struct ext4_extent_header
*eh
= path
->p_hdr
;
373 struct ext4_extent_idx
*r
, *l
, *m
;
376 ext_debug("binsearch for %d(idx): ", block
);
378 l
= EXT_FIRST_INDEX(eh
) + 1;
379 r
= EXT_FIRST_INDEX(eh
) + le16_to_cpu(eh
->eh_entries
) - 1;
382 if (block
< le32_to_cpu(m
->ei_block
))
386 ext_debug("%p(%u):%p(%u):%p(%u) ", l
, l
->ei_block
,
387 m
, m
->ei_block
, r
, r
->ei_block
);
391 ext_debug(" -> %d->%lld ", le32_to_cpu(path
->p_idx
->ei_block
),
392 idx_block(path
->p_idx
));
394 #ifdef CHECK_BINSEARCH
396 struct ext4_extent_idx
*chix
, *ix
;
399 chix
= ix
= EXT_FIRST_INDEX(eh
);
400 for (k
= 0; k
< le16_to_cpu(eh
->eh_entries
); k
++, ix
++) {
402 le32_to_cpu(ix
->ei_block
) <= le32_to_cpu(ix
[-1].ei_block
)) {
403 printk("k=%d, ix=0x%p, first=0x%p\n", k
,
404 ix
, EXT_FIRST_INDEX(eh
));
406 le32_to_cpu(ix
->ei_block
),
407 le32_to_cpu(ix
[-1].ei_block
));
409 BUG_ON(k
&& le32_to_cpu(ix
->ei_block
)
410 <= le32_to_cpu(ix
[-1].ei_block
));
411 if (block
< le32_to_cpu(ix
->ei_block
))
415 BUG_ON(chix
!= path
->p_idx
);
422 * ext4_ext_binsearch:
423 * binary search for closest extent of the given block
424 * the header must be checked before calling this
427 ext4_ext_binsearch(struct inode
*inode
, struct ext4_ext_path
*path
, int block
)
429 struct ext4_extent_header
*eh
= path
->p_hdr
;
430 struct ext4_extent
*r
, *l
, *m
;
432 if (eh
->eh_entries
== 0) {
434 * this leaf is empty:
435 * we get such a leaf in split/add case
440 ext_debug("binsearch for %d: ", block
);
442 l
= EXT_FIRST_EXTENT(eh
) + 1;
443 r
= EXT_FIRST_EXTENT(eh
) + le16_to_cpu(eh
->eh_entries
) - 1;
447 if (block
< le32_to_cpu(m
->ee_block
))
451 ext_debug("%p(%u):%p(%u):%p(%u) ", l
, l
->ee_block
,
452 m
, m
->ee_block
, r
, r
->ee_block
);
456 ext_debug(" -> %d:%llu:%d ",
457 le32_to_cpu(path
->p_ext
->ee_block
),
458 ext_pblock(path
->p_ext
),
459 ext4_ext_get_actual_len(path
->p_ext
));
461 #ifdef CHECK_BINSEARCH
463 struct ext4_extent
*chex
, *ex
;
466 chex
= ex
= EXT_FIRST_EXTENT(eh
);
467 for (k
= 0; k
< le16_to_cpu(eh
->eh_entries
); k
++, ex
++) {
468 BUG_ON(k
&& le32_to_cpu(ex
->ee_block
)
469 <= le32_to_cpu(ex
[-1].ee_block
));
470 if (block
< le32_to_cpu(ex
->ee_block
))
474 BUG_ON(chex
!= path
->p_ext
);
480 int ext4_ext_tree_init(handle_t
*handle
, struct inode
*inode
)
482 struct ext4_extent_header
*eh
;
484 eh
= ext_inode_hdr(inode
);
487 eh
->eh_magic
= EXT4_EXT_MAGIC
;
488 eh
->eh_max
= cpu_to_le16(ext4_ext_space_root(inode
));
489 ext4_mark_inode_dirty(handle
, inode
);
490 ext4_ext_invalidate_cache(inode
);
494 struct ext4_ext_path
*
495 ext4_ext_find_extent(struct inode
*inode
, int block
, struct ext4_ext_path
*path
)
497 struct ext4_extent_header
*eh
;
498 struct buffer_head
*bh
;
499 short int depth
, i
, ppos
= 0, alloc
= 0;
501 eh
= ext_inode_hdr(inode
);
502 depth
= ext_depth(inode
);
503 if (ext4_ext_check_header(inode
, eh
, depth
))
504 return ERR_PTR(-EIO
);
507 /* account possible depth increase */
509 path
= kzalloc(sizeof(struct ext4_ext_path
) * (depth
+ 2),
512 return ERR_PTR(-ENOMEM
);
518 /* walk through the tree */
520 ext_debug("depth %d: num %d, max %d\n",
521 ppos
, le16_to_cpu(eh
->eh_entries
), le16_to_cpu(eh
->eh_max
));
523 ext4_ext_binsearch_idx(inode
, path
+ ppos
, block
);
524 path
[ppos
].p_block
= idx_pblock(path
[ppos
].p_idx
);
525 path
[ppos
].p_depth
= i
;
526 path
[ppos
].p_ext
= NULL
;
528 bh
= sb_bread(inode
->i_sb
, path
[ppos
].p_block
);
532 eh
= ext_block_hdr(bh
);
534 BUG_ON(ppos
> depth
);
535 path
[ppos
].p_bh
= bh
;
536 path
[ppos
].p_hdr
= eh
;
539 if (ext4_ext_check_header(inode
, eh
, i
))
543 path
[ppos
].p_depth
= i
;
544 path
[ppos
].p_hdr
= eh
;
545 path
[ppos
].p_ext
= NULL
;
546 path
[ppos
].p_idx
= NULL
;
549 ext4_ext_binsearch(inode
, path
+ ppos
, block
);
551 ext4_ext_show_path(inode
, path
);
556 ext4_ext_drop_refs(path
);
559 return ERR_PTR(-EIO
);
563 * ext4_ext_insert_index:
564 * insert new index [@logical;@ptr] into the block at @curp;
565 * check where to insert: before @curp or after @curp
567 static int ext4_ext_insert_index(handle_t
*handle
, struct inode
*inode
,
568 struct ext4_ext_path
*curp
,
569 int logical
, ext4_fsblk_t ptr
)
571 struct ext4_extent_idx
*ix
;
574 err
= ext4_ext_get_access(handle
, inode
, curp
);
578 BUG_ON(logical
== le32_to_cpu(curp
->p_idx
->ei_block
));
579 len
= EXT_MAX_INDEX(curp
->p_hdr
) - curp
->p_idx
;
580 if (logical
> le32_to_cpu(curp
->p_idx
->ei_block
)) {
582 if (curp
->p_idx
!= EXT_LAST_INDEX(curp
->p_hdr
)) {
583 len
= (len
- 1) * sizeof(struct ext4_extent_idx
);
584 len
= len
< 0 ? 0 : len
;
585 ext_debug("insert new index %d after: %d. "
586 "move %d from 0x%p to 0x%p\n",
588 (curp
->p_idx
+ 1), (curp
->p_idx
+ 2));
589 memmove(curp
->p_idx
+ 2, curp
->p_idx
+ 1, len
);
591 ix
= curp
->p_idx
+ 1;
594 len
= len
* sizeof(struct ext4_extent_idx
);
595 len
= len
< 0 ? 0 : len
;
596 ext_debug("insert new index %d before: %d. "
597 "move %d from 0x%p to 0x%p\n",
599 curp
->p_idx
, (curp
->p_idx
+ 1));
600 memmove(curp
->p_idx
+ 1, curp
->p_idx
, len
);
604 ix
->ei_block
= cpu_to_le32(logical
);
605 ext4_idx_store_pblock(ix
, ptr
);
606 curp
->p_hdr
->eh_entries
= cpu_to_le16(le16_to_cpu(curp
->p_hdr
->eh_entries
)+1);
608 BUG_ON(le16_to_cpu(curp
->p_hdr
->eh_entries
)
609 > le16_to_cpu(curp
->p_hdr
->eh_max
));
610 BUG_ON(ix
> EXT_LAST_INDEX(curp
->p_hdr
));
612 err
= ext4_ext_dirty(handle
, inode
, curp
);
613 ext4_std_error(inode
->i_sb
, err
);
620 * inserts new subtree into the path, using free index entry
622 * - allocates all needed blocks (new leaf and all intermediate index blocks)
623 * - makes decision where to split
624 * - moves remaining extents and index entries (right to the split point)
625 * into the newly allocated blocks
626 * - initializes subtree
628 static int ext4_ext_split(handle_t
*handle
, struct inode
*inode
,
629 struct ext4_ext_path
*path
,
630 struct ext4_extent
*newext
, int at
)
632 struct buffer_head
*bh
= NULL
;
633 int depth
= ext_depth(inode
);
634 struct ext4_extent_header
*neh
;
635 struct ext4_extent_idx
*fidx
;
636 struct ext4_extent
*ex
;
638 ext4_fsblk_t newblock
, oldblock
;
640 ext4_fsblk_t
*ablocks
= NULL
; /* array of allocated blocks */
643 /* make decision: where to split? */
644 /* FIXME: now decision is simplest: at current extent */
646 /* if current leaf will be split, then we should use
647 * border from split point */
648 BUG_ON(path
[depth
].p_ext
> EXT_MAX_EXTENT(path
[depth
].p_hdr
));
649 if (path
[depth
].p_ext
!= EXT_MAX_EXTENT(path
[depth
].p_hdr
)) {
650 border
= path
[depth
].p_ext
[1].ee_block
;
651 ext_debug("leaf will be split."
652 " next leaf starts at %d\n",
653 le32_to_cpu(border
));
655 border
= newext
->ee_block
;
656 ext_debug("leaf will be added."
657 " next leaf starts at %d\n",
658 le32_to_cpu(border
));
662 * If error occurs, then we break processing
663 * and mark filesystem read-only. index won't
664 * be inserted and tree will be in consistent
665 * state. Next mount will repair buffers too.
669 * Get array to track all allocated blocks.
670 * We need this to handle errors and free blocks
673 ablocks
= kzalloc(sizeof(ext4_fsblk_t
) * depth
, GFP_NOFS
);
677 /* allocate all needed blocks */
678 ext_debug("allocate %d blocks for indexes/leaf\n", depth
- at
);
679 for (a
= 0; a
< depth
- at
; a
++) {
680 newblock
= ext4_ext_new_block(handle
, inode
, path
, newext
, &err
);
683 ablocks
[a
] = newblock
;
686 /* initialize new leaf */
687 newblock
= ablocks
[--a
];
688 BUG_ON(newblock
== 0);
689 bh
= sb_getblk(inode
->i_sb
, newblock
);
696 err
= ext4_journal_get_create_access(handle
, bh
);
700 neh
= ext_block_hdr(bh
);
702 neh
->eh_max
= cpu_to_le16(ext4_ext_space_block(inode
));
703 neh
->eh_magic
= EXT4_EXT_MAGIC
;
705 ex
= EXT_FIRST_EXTENT(neh
);
707 /* move remainder of path[depth] to the new leaf */
708 BUG_ON(path
[depth
].p_hdr
->eh_entries
!= path
[depth
].p_hdr
->eh_max
);
709 /* start copy from next extent */
710 /* TODO: we could do it by single memmove */
713 while (path
[depth
].p_ext
<=
714 EXT_MAX_EXTENT(path
[depth
].p_hdr
)) {
715 ext_debug("move %d:%llu:%d in new leaf %llu\n",
716 le32_to_cpu(path
[depth
].p_ext
->ee_block
),
717 ext_pblock(path
[depth
].p_ext
),
718 ext4_ext_get_actual_len(path
[depth
].p_ext
),
720 /*memmove(ex++, path[depth].p_ext++,
721 sizeof(struct ext4_extent));
727 memmove(ex
, path
[depth
].p_ext
-m
, sizeof(struct ext4_extent
)*m
);
728 neh
->eh_entries
= cpu_to_le16(le16_to_cpu(neh
->eh_entries
)+m
);
731 set_buffer_uptodate(bh
);
734 err
= ext4_journal_dirty_metadata(handle
, bh
);
740 /* correct old leaf */
742 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
745 path
[depth
].p_hdr
->eh_entries
=
746 cpu_to_le16(le16_to_cpu(path
[depth
].p_hdr
->eh_entries
)-m
);
747 err
= ext4_ext_dirty(handle
, inode
, path
+ depth
);
753 /* create intermediate indexes */
757 ext_debug("create %d intermediate indices\n", k
);
758 /* insert new index into current index block */
759 /* current depth stored in i var */
763 newblock
= ablocks
[--a
];
764 bh
= sb_getblk(inode
->i_sb
, (ext4_fsblk_t
)newblock
);
771 err
= ext4_journal_get_create_access(handle
, bh
);
775 neh
= ext_block_hdr(bh
);
776 neh
->eh_entries
= cpu_to_le16(1);
777 neh
->eh_magic
= EXT4_EXT_MAGIC
;
778 neh
->eh_max
= cpu_to_le16(ext4_ext_space_block_idx(inode
));
779 neh
->eh_depth
= cpu_to_le16(depth
- i
);
780 fidx
= EXT_FIRST_INDEX(neh
);
781 fidx
->ei_block
= border
;
782 ext4_idx_store_pblock(fidx
, oldblock
);
784 ext_debug("int.index at %d (block %llu): %lu -> %llu\n", i
,
785 newblock
, (unsigned long) le32_to_cpu(border
),
791 ext_debug("cur 0x%p, last 0x%p\n", path
[i
].p_idx
,
792 EXT_MAX_INDEX(path
[i
].p_hdr
));
793 BUG_ON(EXT_MAX_INDEX(path
[i
].p_hdr
) !=
794 EXT_LAST_INDEX(path
[i
].p_hdr
));
795 while (path
[i
].p_idx
<= EXT_MAX_INDEX(path
[i
].p_hdr
)) {
796 ext_debug("%d: move %d:%d in new index %llu\n", i
,
797 le32_to_cpu(path
[i
].p_idx
->ei_block
),
798 idx_pblock(path
[i
].p_idx
),
800 /*memmove(++fidx, path[i].p_idx++,
801 sizeof(struct ext4_extent_idx));
803 BUG_ON(neh->eh_entries > neh->eh_max);*/
808 memmove(++fidx
, path
[i
].p_idx
- m
,
809 sizeof(struct ext4_extent_idx
) * m
);
811 cpu_to_le16(le16_to_cpu(neh
->eh_entries
) + m
);
813 set_buffer_uptodate(bh
);
816 err
= ext4_journal_dirty_metadata(handle
, bh
);
822 /* correct old index */
824 err
= ext4_ext_get_access(handle
, inode
, path
+ i
);
827 path
[i
].p_hdr
->eh_entries
= cpu_to_le16(le16_to_cpu(path
[i
].p_hdr
->eh_entries
)-m
);
828 err
= ext4_ext_dirty(handle
, inode
, path
+ i
);
836 /* insert new index */
837 err
= ext4_ext_insert_index(handle
, inode
, path
+ at
,
838 le32_to_cpu(border
), newblock
);
842 if (buffer_locked(bh
))
848 /* free all allocated blocks in error case */
849 for (i
= 0; i
< depth
; i
++) {
852 ext4_free_blocks(handle
, inode
, ablocks
[i
], 1);
861 * ext4_ext_grow_indepth:
862 * implements tree growing procedure:
863 * - allocates new block
864 * - moves top-level data (index block or leaf) into the new block
865 * - initializes new top-level, creating index that points to the
868 static int ext4_ext_grow_indepth(handle_t
*handle
, struct inode
*inode
,
869 struct ext4_ext_path
*path
,
870 struct ext4_extent
*newext
)
872 struct ext4_ext_path
*curp
= path
;
873 struct ext4_extent_header
*neh
;
874 struct ext4_extent_idx
*fidx
;
875 struct buffer_head
*bh
;
876 ext4_fsblk_t newblock
;
879 newblock
= ext4_ext_new_block(handle
, inode
, path
, newext
, &err
);
883 bh
= sb_getblk(inode
->i_sb
, newblock
);
886 ext4_std_error(inode
->i_sb
, err
);
891 err
= ext4_journal_get_create_access(handle
, bh
);
897 /* move top-level index/leaf into new block */
898 memmove(bh
->b_data
, curp
->p_hdr
, sizeof(EXT4_I(inode
)->i_data
));
900 /* set size of new block */
901 neh
= ext_block_hdr(bh
);
902 /* old root could have indexes or leaves
903 * so calculate e_max right way */
904 if (ext_depth(inode
))
905 neh
->eh_max
= cpu_to_le16(ext4_ext_space_block_idx(inode
));
907 neh
->eh_max
= cpu_to_le16(ext4_ext_space_block(inode
));
908 neh
->eh_magic
= EXT4_EXT_MAGIC
;
909 set_buffer_uptodate(bh
);
912 err
= ext4_journal_dirty_metadata(handle
, bh
);
916 /* create index in new top-level index: num,max,pointer */
917 err
= ext4_ext_get_access(handle
, inode
, curp
);
921 curp
->p_hdr
->eh_magic
= EXT4_EXT_MAGIC
;
922 curp
->p_hdr
->eh_max
= cpu_to_le16(ext4_ext_space_root_idx(inode
));
923 curp
->p_hdr
->eh_entries
= cpu_to_le16(1);
924 curp
->p_idx
= EXT_FIRST_INDEX(curp
->p_hdr
);
925 /* FIXME: it works, but actually path[0] can be index */
926 curp
->p_idx
->ei_block
= EXT_FIRST_EXTENT(path
[0].p_hdr
)->ee_block
;
927 ext4_idx_store_pblock(curp
->p_idx
, newblock
);
929 neh
= ext_inode_hdr(inode
);
930 fidx
= EXT_FIRST_INDEX(neh
);
931 ext_debug("new root: num %d(%d), lblock %d, ptr %llu\n",
932 le16_to_cpu(neh
->eh_entries
), le16_to_cpu(neh
->eh_max
),
933 le32_to_cpu(fidx
->ei_block
), idx_pblock(fidx
));
935 neh
->eh_depth
= cpu_to_le16(path
->p_depth
+ 1);
936 err
= ext4_ext_dirty(handle
, inode
, curp
);
944 * ext4_ext_create_new_leaf:
945 * finds empty index and adds new leaf.
946 * if no free index is found, then it requests in-depth growing.
948 static int ext4_ext_create_new_leaf(handle_t
*handle
, struct inode
*inode
,
949 struct ext4_ext_path
*path
,
950 struct ext4_extent
*newext
)
952 struct ext4_ext_path
*curp
;
953 int depth
, i
, err
= 0;
956 i
= depth
= ext_depth(inode
);
958 /* walk up to the tree and look for free index entry */
960 while (i
> 0 && !EXT_HAS_FREE_INDEX(curp
)) {
965 /* we use already allocated block for index block,
966 * so subsequent data blocks should be contiguous */
967 if (EXT_HAS_FREE_INDEX(curp
)) {
968 /* if we found index with free entry, then use that
969 * entry: create all needed subtree and add new leaf */
970 err
= ext4_ext_split(handle
, inode
, path
, newext
, i
);
973 ext4_ext_drop_refs(path
);
974 path
= ext4_ext_find_extent(inode
,
975 le32_to_cpu(newext
->ee_block
),
980 /* tree is full, time to grow in depth */
981 err
= ext4_ext_grow_indepth(handle
, inode
, path
, newext
);
986 ext4_ext_drop_refs(path
);
987 path
= ext4_ext_find_extent(inode
,
988 le32_to_cpu(newext
->ee_block
),
996 * only first (depth 0 -> 1) produces free space;
997 * in all other cases we have to split the grown tree
999 depth
= ext_depth(inode
);
1000 if (path
[depth
].p_hdr
->eh_entries
== path
[depth
].p_hdr
->eh_max
) {
1001 /* now we need to split */
1011 * ext4_ext_next_allocated_block:
1012 * returns allocated block in subsequent extent or EXT_MAX_BLOCK.
1013 * NOTE: it considers block number from index entry as
1014 * allocated block. Thus, index entries have to be consistent
1017 static unsigned long
1018 ext4_ext_next_allocated_block(struct ext4_ext_path
*path
)
1022 BUG_ON(path
== NULL
);
1023 depth
= path
->p_depth
;
1025 if (depth
== 0 && path
->p_ext
== NULL
)
1026 return EXT_MAX_BLOCK
;
1028 while (depth
>= 0) {
1029 if (depth
== path
->p_depth
) {
1031 if (path
[depth
].p_ext
!=
1032 EXT_LAST_EXTENT(path
[depth
].p_hdr
))
1033 return le32_to_cpu(path
[depth
].p_ext
[1].ee_block
);
1036 if (path
[depth
].p_idx
!=
1037 EXT_LAST_INDEX(path
[depth
].p_hdr
))
1038 return le32_to_cpu(path
[depth
].p_idx
[1].ei_block
);
1043 return EXT_MAX_BLOCK
;
1047 * ext4_ext_next_leaf_block:
1048 * returns first allocated block from next leaf or EXT_MAX_BLOCK
1050 static unsigned ext4_ext_next_leaf_block(struct inode
*inode
,
1051 struct ext4_ext_path
*path
)
1055 BUG_ON(path
== NULL
);
1056 depth
= path
->p_depth
;
1058 /* zero-tree has no leaf blocks at all */
1060 return EXT_MAX_BLOCK
;
1062 /* go to index block */
1065 while (depth
>= 0) {
1066 if (path
[depth
].p_idx
!=
1067 EXT_LAST_INDEX(path
[depth
].p_hdr
))
1068 return le32_to_cpu(path
[depth
].p_idx
[1].ei_block
);
1072 return EXT_MAX_BLOCK
;
1076 * ext4_ext_correct_indexes:
1077 * if leaf gets modified and modified extent is first in the leaf,
1078 * then we have to correct all indexes above.
1079 * TODO: do we need to correct tree in all cases?
1081 int ext4_ext_correct_indexes(handle_t
*handle
, struct inode
*inode
,
1082 struct ext4_ext_path
*path
)
1084 struct ext4_extent_header
*eh
;
1085 int depth
= ext_depth(inode
);
1086 struct ext4_extent
*ex
;
1090 eh
= path
[depth
].p_hdr
;
1091 ex
= path
[depth
].p_ext
;
1096 /* there is no tree at all */
1100 if (ex
!= EXT_FIRST_EXTENT(eh
)) {
1101 /* we correct tree if first leaf got modified only */
1106 * TODO: we need correction if border is smaller than current one
1109 border
= path
[depth
].p_ext
->ee_block
;
1110 err
= ext4_ext_get_access(handle
, inode
, path
+ k
);
1113 path
[k
].p_idx
->ei_block
= border
;
1114 err
= ext4_ext_dirty(handle
, inode
, path
+ k
);
1119 /* change all left-side indexes */
1120 if (path
[k
+1].p_idx
!= EXT_FIRST_INDEX(path
[k
+1].p_hdr
))
1122 err
= ext4_ext_get_access(handle
, inode
, path
+ k
);
1125 path
[k
].p_idx
->ei_block
= border
;
1126 err
= ext4_ext_dirty(handle
, inode
, path
+ k
);
1135 ext4_can_extents_be_merged(struct inode
*inode
, struct ext4_extent
*ex1
,
1136 struct ext4_extent
*ex2
)
1138 unsigned short ext1_ee_len
, ext2_ee_len
, max_len
;
1141 * Make sure that either both extents are uninitialized, or
1144 if (ext4_ext_is_uninitialized(ex1
) ^ ext4_ext_is_uninitialized(ex2
))
1147 if (ext4_ext_is_uninitialized(ex1
))
1148 max_len
= EXT_UNINIT_MAX_LEN
;
1150 max_len
= EXT_INIT_MAX_LEN
;
1152 ext1_ee_len
= ext4_ext_get_actual_len(ex1
);
1153 ext2_ee_len
= ext4_ext_get_actual_len(ex2
);
1155 if (le32_to_cpu(ex1
->ee_block
) + ext1_ee_len
!=
1156 le32_to_cpu(ex2
->ee_block
))
1160 * To allow future support for preallocated extents to be added
1161 * as an RO_COMPAT feature, refuse to merge to extents if
1162 * this can result in the top bit of ee_len being set.
1164 if (ext1_ee_len
+ ext2_ee_len
> max_len
)
1166 #ifdef AGGRESSIVE_TEST
1167 if (le16_to_cpu(ex1
->ee_len
) >= 4)
1171 if (ext_pblock(ex1
) + ext1_ee_len
== ext_pblock(ex2
))
1177 * This function tries to merge the "ex" extent to the next extent in the tree.
1178 * It always tries to merge towards right. If you want to merge towards
1179 * left, pass "ex - 1" as argument instead of "ex".
1180 * Returns 0 if the extents (ex and ex+1) were _not_ merged and returns
1181 * 1 if they got merged.
1183 int ext4_ext_try_to_merge(struct inode
*inode
,
1184 struct ext4_ext_path
*path
,
1185 struct ext4_extent
*ex
)
1187 struct ext4_extent_header
*eh
;
1188 unsigned int depth
, len
;
1190 int uninitialized
= 0;
1192 depth
= ext_depth(inode
);
1193 BUG_ON(path
[depth
].p_hdr
== NULL
);
1194 eh
= path
[depth
].p_hdr
;
1196 while (ex
< EXT_LAST_EXTENT(eh
)) {
1197 if (!ext4_can_extents_be_merged(inode
, ex
, ex
+ 1))
1199 /* merge with next extent! */
1200 if (ext4_ext_is_uninitialized(ex
))
1202 ex
->ee_len
= cpu_to_le16(ext4_ext_get_actual_len(ex
)
1203 + ext4_ext_get_actual_len(ex
+ 1));
1205 ext4_ext_mark_uninitialized(ex
);
1207 if (ex
+ 1 < EXT_LAST_EXTENT(eh
)) {
1208 len
= (EXT_LAST_EXTENT(eh
) - ex
- 1)
1209 * sizeof(struct ext4_extent
);
1210 memmove(ex
+ 1, ex
+ 2, len
);
1212 eh
->eh_entries
= cpu_to_le16(le16_to_cpu(eh
->eh_entries
) - 1);
1214 WARN_ON(eh
->eh_entries
== 0);
1215 if (!eh
->eh_entries
)
1216 ext4_error(inode
->i_sb
, "ext4_ext_try_to_merge",
1217 "inode#%lu, eh->eh_entries = 0!", inode
->i_ino
);
1224 * check if a portion of the "newext" extent overlaps with an
1227 * If there is an overlap discovered, it updates the length of the newext
1228 * such that there will be no overlap, and then returns 1.
1229 * If there is no overlap found, it returns 0.
1231 unsigned int ext4_ext_check_overlap(struct inode
*inode
,
1232 struct ext4_extent
*newext
,
1233 struct ext4_ext_path
*path
)
1235 unsigned long b1
, b2
;
1236 unsigned int depth
, len1
;
1237 unsigned int ret
= 0;
1239 b1
= le32_to_cpu(newext
->ee_block
);
1240 len1
= ext4_ext_get_actual_len(newext
);
1241 depth
= ext_depth(inode
);
1242 if (!path
[depth
].p_ext
)
1244 b2
= le32_to_cpu(path
[depth
].p_ext
->ee_block
);
1247 * get the next allocated block if the extent in the path
1248 * is before the requested block(s)
1251 b2
= ext4_ext_next_allocated_block(path
);
1252 if (b2
== EXT_MAX_BLOCK
)
1256 /* check for wrap through zero */
1257 if (b1
+ len1
< b1
) {
1258 len1
= EXT_MAX_BLOCK
- b1
;
1259 newext
->ee_len
= cpu_to_le16(len1
);
1263 /* check for overlap */
1264 if (b1
+ len1
> b2
) {
1265 newext
->ee_len
= cpu_to_le16(b2
- b1
);
1273 * ext4_ext_insert_extent:
1274 * tries to merge requsted extent into the existing extent or
1275 * inserts requested extent as new one into the tree,
1276 * creating new leaf in the no-space case.
1278 int ext4_ext_insert_extent(handle_t
*handle
, struct inode
*inode
,
1279 struct ext4_ext_path
*path
,
1280 struct ext4_extent
*newext
)
1282 struct ext4_extent_header
* eh
;
1283 struct ext4_extent
*ex
, *fex
;
1284 struct ext4_extent
*nearex
; /* nearest extent */
1285 struct ext4_ext_path
*npath
= NULL
;
1286 int depth
, len
, err
, next
;
1287 unsigned uninitialized
= 0;
1289 BUG_ON(ext4_ext_get_actual_len(newext
) == 0);
1290 depth
= ext_depth(inode
);
1291 ex
= path
[depth
].p_ext
;
1292 BUG_ON(path
[depth
].p_hdr
== NULL
);
1294 /* try to insert block into found extent and return */
1295 if (ex
&& ext4_can_extents_be_merged(inode
, ex
, newext
)) {
1296 ext_debug("append %d block to %d:%d (from %llu)\n",
1297 ext4_ext_get_actual_len(newext
),
1298 le32_to_cpu(ex
->ee_block
),
1299 ext4_ext_get_actual_len(ex
), ext_pblock(ex
));
1300 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
1305 * ext4_can_extents_be_merged should have checked that either
1306 * both extents are uninitialized, or both aren't. Thus we
1307 * need to check only one of them here.
1309 if (ext4_ext_is_uninitialized(ex
))
1311 ex
->ee_len
= cpu_to_le16(ext4_ext_get_actual_len(ex
)
1312 + ext4_ext_get_actual_len(newext
));
1314 ext4_ext_mark_uninitialized(ex
);
1315 eh
= path
[depth
].p_hdr
;
1321 depth
= ext_depth(inode
);
1322 eh
= path
[depth
].p_hdr
;
1323 if (le16_to_cpu(eh
->eh_entries
) < le16_to_cpu(eh
->eh_max
))
1326 /* probably next leaf has space for us? */
1327 fex
= EXT_LAST_EXTENT(eh
);
1328 next
= ext4_ext_next_leaf_block(inode
, path
);
1329 if (le32_to_cpu(newext
->ee_block
) > le32_to_cpu(fex
->ee_block
)
1330 && next
!= EXT_MAX_BLOCK
) {
1331 ext_debug("next leaf block - %d\n", next
);
1332 BUG_ON(npath
!= NULL
);
1333 npath
= ext4_ext_find_extent(inode
, next
, NULL
);
1335 return PTR_ERR(npath
);
1336 BUG_ON(npath
->p_depth
!= path
->p_depth
);
1337 eh
= npath
[depth
].p_hdr
;
1338 if (le16_to_cpu(eh
->eh_entries
) < le16_to_cpu(eh
->eh_max
)) {
1339 ext_debug("next leaf isnt full(%d)\n",
1340 le16_to_cpu(eh
->eh_entries
));
1344 ext_debug("next leaf has no free space(%d,%d)\n",
1345 le16_to_cpu(eh
->eh_entries
), le16_to_cpu(eh
->eh_max
));
1349 * There is no free space in the found leaf.
1350 * We're gonna add a new leaf in the tree.
1352 err
= ext4_ext_create_new_leaf(handle
, inode
, path
, newext
);
1355 depth
= ext_depth(inode
);
1356 eh
= path
[depth
].p_hdr
;
1359 nearex
= path
[depth
].p_ext
;
1361 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
1366 /* there is no extent in this leaf, create first one */
1367 ext_debug("first extent in the leaf: %d:%llu:%d\n",
1368 le32_to_cpu(newext
->ee_block
),
1370 ext4_ext_get_actual_len(newext
));
1371 path
[depth
].p_ext
= EXT_FIRST_EXTENT(eh
);
1372 } else if (le32_to_cpu(newext
->ee_block
)
1373 > le32_to_cpu(nearex
->ee_block
)) {
1374 /* BUG_ON(newext->ee_block == nearex->ee_block); */
1375 if (nearex
!= EXT_LAST_EXTENT(eh
)) {
1376 len
= EXT_MAX_EXTENT(eh
) - nearex
;
1377 len
= (len
- 1) * sizeof(struct ext4_extent
);
1378 len
= len
< 0 ? 0 : len
;
1379 ext_debug("insert %d:%llu:%d after: nearest 0x%p, "
1380 "move %d from 0x%p to 0x%p\n",
1381 le32_to_cpu(newext
->ee_block
),
1383 ext4_ext_get_actual_len(newext
),
1384 nearex
, len
, nearex
+ 1, nearex
+ 2);
1385 memmove(nearex
+ 2, nearex
+ 1, len
);
1387 path
[depth
].p_ext
= nearex
+ 1;
1389 BUG_ON(newext
->ee_block
== nearex
->ee_block
);
1390 len
= (EXT_MAX_EXTENT(eh
) - nearex
) * sizeof(struct ext4_extent
);
1391 len
= len
< 0 ? 0 : len
;
1392 ext_debug("insert %d:%llu:%d before: nearest 0x%p, "
1393 "move %d from 0x%p to 0x%p\n",
1394 le32_to_cpu(newext
->ee_block
),
1396 ext4_ext_get_actual_len(newext
),
1397 nearex
, len
, nearex
+ 1, nearex
+ 2);
1398 memmove(nearex
+ 1, nearex
, len
);
1399 path
[depth
].p_ext
= nearex
;
1402 eh
->eh_entries
= cpu_to_le16(le16_to_cpu(eh
->eh_entries
)+1);
1403 nearex
= path
[depth
].p_ext
;
1404 nearex
->ee_block
= newext
->ee_block
;
1405 nearex
->ee_start
= newext
->ee_start
;
1406 nearex
->ee_start_hi
= newext
->ee_start_hi
;
1407 nearex
->ee_len
= newext
->ee_len
;
1410 /* try to merge extents to the right */
1411 ext4_ext_try_to_merge(inode
, path
, nearex
);
1413 /* try to merge extents to the left */
1415 /* time to correct all indexes above */
1416 err
= ext4_ext_correct_indexes(handle
, inode
, path
);
1420 err
= ext4_ext_dirty(handle
, inode
, path
+ depth
);
1424 ext4_ext_drop_refs(npath
);
1427 ext4_ext_tree_changed(inode
);
1428 ext4_ext_invalidate_cache(inode
);
1432 int ext4_ext_walk_space(struct inode
*inode
, unsigned long block
,
1433 unsigned long num
, ext_prepare_callback func
,
1436 struct ext4_ext_path
*path
= NULL
;
1437 struct ext4_ext_cache cbex
;
1438 struct ext4_extent
*ex
;
1439 unsigned long next
, start
= 0, end
= 0;
1440 unsigned long last
= block
+ num
;
1441 int depth
, exists
, err
= 0;
1443 BUG_ON(func
== NULL
);
1444 BUG_ON(inode
== NULL
);
1446 while (block
< last
&& block
!= EXT_MAX_BLOCK
) {
1448 /* find extent for this block */
1449 path
= ext4_ext_find_extent(inode
, block
, path
);
1451 err
= PTR_ERR(path
);
1456 depth
= ext_depth(inode
);
1457 BUG_ON(path
[depth
].p_hdr
== NULL
);
1458 ex
= path
[depth
].p_ext
;
1459 next
= ext4_ext_next_allocated_block(path
);
1463 /* there is no extent yet, so try to allocate
1464 * all requested space */
1467 } else if (le32_to_cpu(ex
->ee_block
) > block
) {
1468 /* need to allocate space before found extent */
1470 end
= le32_to_cpu(ex
->ee_block
);
1471 if (block
+ num
< end
)
1473 } else if (block
>= le32_to_cpu(ex
->ee_block
)
1474 + ext4_ext_get_actual_len(ex
)) {
1475 /* need to allocate space after found extent */
1480 } else if (block
>= le32_to_cpu(ex
->ee_block
)) {
1482 * some part of requested space is covered
1486 end
= le32_to_cpu(ex
->ee_block
)
1487 + ext4_ext_get_actual_len(ex
);
1488 if (block
+ num
< end
)
1494 BUG_ON(end
<= start
);
1497 cbex
.ec_block
= start
;
1498 cbex
.ec_len
= end
- start
;
1500 cbex
.ec_type
= EXT4_EXT_CACHE_GAP
;
1502 cbex
.ec_block
= le32_to_cpu(ex
->ee_block
);
1503 cbex
.ec_len
= ext4_ext_get_actual_len(ex
);
1504 cbex
.ec_start
= ext_pblock(ex
);
1505 cbex
.ec_type
= EXT4_EXT_CACHE_EXTENT
;
1508 BUG_ON(cbex
.ec_len
== 0);
1509 err
= func(inode
, path
, &cbex
, cbdata
);
1510 ext4_ext_drop_refs(path
);
1514 if (err
== EXT_REPEAT
)
1516 else if (err
== EXT_BREAK
) {
1521 if (ext_depth(inode
) != depth
) {
1522 /* depth was changed. we have to realloc path */
1527 block
= cbex
.ec_block
+ cbex
.ec_len
;
1531 ext4_ext_drop_refs(path
);
1539 ext4_ext_put_in_cache(struct inode
*inode
, __u32 block
,
1540 __u32 len
, __u32 start
, int type
)
1542 struct ext4_ext_cache
*cex
;
1544 cex
= &EXT4_I(inode
)->i_cached_extent
;
1545 cex
->ec_type
= type
;
1546 cex
->ec_block
= block
;
1548 cex
->ec_start
= start
;
1552 * ext4_ext_put_gap_in_cache:
1553 * calculate boundaries of the gap that the requested block fits into
1554 * and cache this gap
1557 ext4_ext_put_gap_in_cache(struct inode
*inode
, struct ext4_ext_path
*path
,
1558 unsigned long block
)
1560 int depth
= ext_depth(inode
);
1561 unsigned long lblock
, len
;
1562 struct ext4_extent
*ex
;
1564 ex
= path
[depth
].p_ext
;
1566 /* there is no extent yet, so gap is [0;-] */
1568 len
= EXT_MAX_BLOCK
;
1569 ext_debug("cache gap(whole file):");
1570 } else if (block
< le32_to_cpu(ex
->ee_block
)) {
1572 len
= le32_to_cpu(ex
->ee_block
) - block
;
1573 ext_debug("cache gap(before): %lu [%lu:%lu]",
1574 (unsigned long) block
,
1575 (unsigned long) le32_to_cpu(ex
->ee_block
),
1576 (unsigned long) ext4_ext_get_actual_len(ex
));
1577 } else if (block
>= le32_to_cpu(ex
->ee_block
)
1578 + ext4_ext_get_actual_len(ex
)) {
1579 lblock
= le32_to_cpu(ex
->ee_block
)
1580 + ext4_ext_get_actual_len(ex
);
1581 len
= ext4_ext_next_allocated_block(path
);
1582 ext_debug("cache gap(after): [%lu:%lu] %lu",
1583 (unsigned long) le32_to_cpu(ex
->ee_block
),
1584 (unsigned long) ext4_ext_get_actual_len(ex
),
1585 (unsigned long) block
);
1586 BUG_ON(len
== lblock
);
1593 ext_debug(" -> %lu:%lu\n", (unsigned long) lblock
, len
);
1594 ext4_ext_put_in_cache(inode
, lblock
, len
, 0, EXT4_EXT_CACHE_GAP
);
1598 ext4_ext_in_cache(struct inode
*inode
, unsigned long block
,
1599 struct ext4_extent
*ex
)
1601 struct ext4_ext_cache
*cex
;
1603 cex
= &EXT4_I(inode
)->i_cached_extent
;
1605 /* has cache valid data? */
1606 if (cex
->ec_type
== EXT4_EXT_CACHE_NO
)
1607 return EXT4_EXT_CACHE_NO
;
1609 BUG_ON(cex
->ec_type
!= EXT4_EXT_CACHE_GAP
&&
1610 cex
->ec_type
!= EXT4_EXT_CACHE_EXTENT
);
1611 if (block
>= cex
->ec_block
&& block
< cex
->ec_block
+ cex
->ec_len
) {
1612 ex
->ee_block
= cpu_to_le32(cex
->ec_block
);
1613 ext4_ext_store_pblock(ex
, cex
->ec_start
);
1614 ex
->ee_len
= cpu_to_le16(cex
->ec_len
);
1615 ext_debug("%lu cached by %lu:%lu:%llu\n",
1616 (unsigned long) block
,
1617 (unsigned long) cex
->ec_block
,
1618 (unsigned long) cex
->ec_len
,
1620 return cex
->ec_type
;
1624 return EXT4_EXT_CACHE_NO
;
1629 * removes index from the index block.
1630 * It's used in truncate case only, thus all requests are for
1631 * last index in the block only.
1633 int ext4_ext_rm_idx(handle_t
*handle
, struct inode
*inode
,
1634 struct ext4_ext_path
*path
)
1636 struct buffer_head
*bh
;
1640 /* free index block */
1642 leaf
= idx_pblock(path
->p_idx
);
1643 BUG_ON(path
->p_hdr
->eh_entries
== 0);
1644 err
= ext4_ext_get_access(handle
, inode
, path
);
1647 path
->p_hdr
->eh_entries
= cpu_to_le16(le16_to_cpu(path
->p_hdr
->eh_entries
)-1);
1648 err
= ext4_ext_dirty(handle
, inode
, path
);
1651 ext_debug("index is empty, remove it, free block %llu\n", leaf
);
1652 bh
= sb_find_get_block(inode
->i_sb
, leaf
);
1653 ext4_forget(handle
, 1, inode
, bh
, leaf
);
1654 ext4_free_blocks(handle
, inode
, leaf
, 1);
1659 * ext4_ext_calc_credits_for_insert:
1660 * This routine returns max. credits that the extent tree can consume.
1661 * It should be OK for low-performance paths like ->writepage()
1662 * To allow many writing processes to fit into a single transaction,
1663 * the caller should calculate credits under truncate_mutex and
1664 * pass the actual path.
1666 int ext4_ext_calc_credits_for_insert(struct inode
*inode
,
1667 struct ext4_ext_path
*path
)
1672 /* probably there is space in leaf? */
1673 depth
= ext_depth(inode
);
1674 if (le16_to_cpu(path
[depth
].p_hdr
->eh_entries
)
1675 < le16_to_cpu(path
[depth
].p_hdr
->eh_max
))
1680 * given 32-bit logical block (4294967296 blocks), max. tree
1681 * can be 4 levels in depth -- 4 * 340^4 == 53453440000.
1682 * Let's also add one more level for imbalance.
1686 /* allocation of new data block(s) */
1690 * tree can be full, so it would need to grow in depth:
1691 * we need one credit to modify old root, credits for
1692 * new root will be added in split accounting
1697 * Index split can happen, we would need:
1698 * allocate intermediate indexes (bitmap + group)
1699 * + change two blocks at each level, but root (already included)
1701 needed
+= (depth
* 2) + (depth
* 2);
1703 /* any allocation modifies superblock */
1709 static int ext4_remove_blocks(handle_t
*handle
, struct inode
*inode
,
1710 struct ext4_extent
*ex
,
1711 unsigned long from
, unsigned long to
)
1713 struct buffer_head
*bh
;
1714 unsigned short ee_len
= ext4_ext_get_actual_len(ex
);
1717 #ifdef EXTENTS_STATS
1719 struct ext4_sb_info
*sbi
= EXT4_SB(inode
->i_sb
);
1720 spin_lock(&sbi
->s_ext_stats_lock
);
1721 sbi
->s_ext_blocks
+= ee_len
;
1722 sbi
->s_ext_extents
++;
1723 if (ee_len
< sbi
->s_ext_min
)
1724 sbi
->s_ext_min
= ee_len
;
1725 if (ee_len
> sbi
->s_ext_max
)
1726 sbi
->s_ext_max
= ee_len
;
1727 if (ext_depth(inode
) > sbi
->s_depth_max
)
1728 sbi
->s_depth_max
= ext_depth(inode
);
1729 spin_unlock(&sbi
->s_ext_stats_lock
);
1732 if (from
>= le32_to_cpu(ex
->ee_block
)
1733 && to
== le32_to_cpu(ex
->ee_block
) + ee_len
- 1) {
1737 num
= le32_to_cpu(ex
->ee_block
) + ee_len
- from
;
1738 start
= ext_pblock(ex
) + ee_len
- num
;
1739 ext_debug("free last %lu blocks starting %llu\n", num
, start
);
1740 for (i
= 0; i
< num
; i
++) {
1741 bh
= sb_find_get_block(inode
->i_sb
, start
+ i
);
1742 ext4_forget(handle
, 0, inode
, bh
, start
+ i
);
1744 ext4_free_blocks(handle
, inode
, start
, num
);
1745 } else if (from
== le32_to_cpu(ex
->ee_block
)
1746 && to
<= le32_to_cpu(ex
->ee_block
) + ee_len
- 1) {
1747 printk("strange request: removal %lu-%lu from %u:%u\n",
1748 from
, to
, le32_to_cpu(ex
->ee_block
), ee_len
);
1750 printk("strange request: removal(2) %lu-%lu from %u:%u\n",
1751 from
, to
, le32_to_cpu(ex
->ee_block
), ee_len
);
1757 ext4_ext_rm_leaf(handle_t
*handle
, struct inode
*inode
,
1758 struct ext4_ext_path
*path
, unsigned long start
)
1760 int err
= 0, correct_index
= 0;
1761 int depth
= ext_depth(inode
), credits
;
1762 struct ext4_extent_header
*eh
;
1763 unsigned a
, b
, block
, num
;
1764 unsigned long ex_ee_block
;
1765 unsigned short ex_ee_len
;
1766 unsigned uninitialized
= 0;
1767 struct ext4_extent
*ex
;
1769 /* the header must be checked already in ext4_ext_remove_space() */
1770 ext_debug("truncate since %lu in leaf\n", start
);
1771 if (!path
[depth
].p_hdr
)
1772 path
[depth
].p_hdr
= ext_block_hdr(path
[depth
].p_bh
);
1773 eh
= path
[depth
].p_hdr
;
1776 /* find where to start removing */
1777 ex
= EXT_LAST_EXTENT(eh
);
1779 ex_ee_block
= le32_to_cpu(ex
->ee_block
);
1780 if (ext4_ext_is_uninitialized(ex
))
1782 ex_ee_len
= ext4_ext_get_actual_len(ex
);
1784 while (ex
>= EXT_FIRST_EXTENT(eh
) &&
1785 ex_ee_block
+ ex_ee_len
> start
) {
1786 ext_debug("remove ext %lu:%u\n", ex_ee_block
, ex_ee_len
);
1787 path
[depth
].p_ext
= ex
;
1789 a
= ex_ee_block
> start
? ex_ee_block
: start
;
1790 b
= ex_ee_block
+ ex_ee_len
- 1 < EXT_MAX_BLOCK
?
1791 ex_ee_block
+ ex_ee_len
- 1 : EXT_MAX_BLOCK
;
1793 ext_debug(" border %u:%u\n", a
, b
);
1795 if (a
!= ex_ee_block
&& b
!= ex_ee_block
+ ex_ee_len
- 1) {
1799 } else if (a
!= ex_ee_block
) {
1800 /* remove tail of the extent */
1801 block
= ex_ee_block
;
1803 } else if (b
!= ex_ee_block
+ ex_ee_len
- 1) {
1804 /* remove head of the extent */
1807 /* there is no "make a hole" API yet */
1810 /* remove whole extent: excellent! */
1811 block
= ex_ee_block
;
1813 BUG_ON(a
!= ex_ee_block
);
1814 BUG_ON(b
!= ex_ee_block
+ ex_ee_len
- 1);
1817 /* at present, extent can't cross block group: */
1818 /* leaf + bitmap + group desc + sb + inode */
1820 if (ex
== EXT_FIRST_EXTENT(eh
)) {
1822 credits
+= (ext_depth(inode
)) + 1;
1825 credits
+= 2 * EXT4_QUOTA_TRANS_BLOCKS(inode
->i_sb
);
1828 handle
= ext4_ext_journal_restart(handle
, credits
);
1829 if (IS_ERR(handle
)) {
1830 err
= PTR_ERR(handle
);
1834 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
1838 err
= ext4_remove_blocks(handle
, inode
, ex
, a
, b
);
1843 /* this extent is removed; mark slot entirely unused */
1844 ext4_ext_store_pblock(ex
, 0);
1845 eh
->eh_entries
= cpu_to_le16(le16_to_cpu(eh
->eh_entries
)-1);
1848 ex
->ee_block
= cpu_to_le32(block
);
1849 ex
->ee_len
= cpu_to_le16(num
);
1851 * Do not mark uninitialized if all the blocks in the
1852 * extent have been removed.
1854 if (uninitialized
&& num
)
1855 ext4_ext_mark_uninitialized(ex
);
1857 err
= ext4_ext_dirty(handle
, inode
, path
+ depth
);
1861 ext_debug("new extent: %u:%u:%llu\n", block
, num
,
1864 ex_ee_block
= le32_to_cpu(ex
->ee_block
);
1865 ex_ee_len
= ext4_ext_get_actual_len(ex
);
1868 if (correct_index
&& eh
->eh_entries
)
1869 err
= ext4_ext_correct_indexes(handle
, inode
, path
);
1871 /* if this leaf is free, then we should
1872 * remove it from index block above */
1873 if (err
== 0 && eh
->eh_entries
== 0 && path
[depth
].p_bh
!= NULL
)
1874 err
= ext4_ext_rm_idx(handle
, inode
, path
+ depth
);
1881 * ext4_ext_more_to_rm:
1882 * returns 1 if current index has to be freed (even partial)
1885 ext4_ext_more_to_rm(struct ext4_ext_path
*path
)
1887 BUG_ON(path
->p_idx
== NULL
);
1889 if (path
->p_idx
< EXT_FIRST_INDEX(path
->p_hdr
))
1893 * if truncate on deeper level happened, it wasn't partial,
1894 * so we have to consider current index for truncation
1896 if (le16_to_cpu(path
->p_hdr
->eh_entries
) == path
->p_block
)
1901 int ext4_ext_remove_space(struct inode
*inode
, unsigned long start
)
1903 struct super_block
*sb
= inode
->i_sb
;
1904 int depth
= ext_depth(inode
);
1905 struct ext4_ext_path
*path
;
1909 ext_debug("truncate since %lu\n", start
);
1911 /* probably first extent we're gonna free will be last in block */
1912 handle
= ext4_journal_start(inode
, depth
+ 1);
1914 return PTR_ERR(handle
);
1916 ext4_ext_invalidate_cache(inode
);
1919 * We start scanning from right side, freeing all the blocks
1920 * after i_size and walking into the tree depth-wise.
1922 path
= kzalloc(sizeof(struct ext4_ext_path
) * (depth
+ 1), GFP_KERNEL
);
1924 ext4_journal_stop(handle
);
1927 path
[0].p_hdr
= ext_inode_hdr(inode
);
1928 if (ext4_ext_check_header(inode
, path
[0].p_hdr
, depth
)) {
1932 path
[0].p_depth
= depth
;
1934 while (i
>= 0 && err
== 0) {
1936 /* this is leaf block */
1937 err
= ext4_ext_rm_leaf(handle
, inode
, path
, start
);
1938 /* root level has p_bh == NULL, brelse() eats this */
1939 brelse(path
[i
].p_bh
);
1940 path
[i
].p_bh
= NULL
;
1945 /* this is index block */
1946 if (!path
[i
].p_hdr
) {
1947 ext_debug("initialize header\n");
1948 path
[i
].p_hdr
= ext_block_hdr(path
[i
].p_bh
);
1951 if (!path
[i
].p_idx
) {
1952 /* this level hasn't been touched yet */
1953 path
[i
].p_idx
= EXT_LAST_INDEX(path
[i
].p_hdr
);
1954 path
[i
].p_block
= le16_to_cpu(path
[i
].p_hdr
->eh_entries
)+1;
1955 ext_debug("init index ptr: hdr 0x%p, num %d\n",
1957 le16_to_cpu(path
[i
].p_hdr
->eh_entries
));
1959 /* we were already here, see at next index */
1963 ext_debug("level %d - index, first 0x%p, cur 0x%p\n",
1964 i
, EXT_FIRST_INDEX(path
[i
].p_hdr
),
1966 if (ext4_ext_more_to_rm(path
+ i
)) {
1967 struct buffer_head
*bh
;
1968 /* go to the next level */
1969 ext_debug("move to level %d (block %llu)\n",
1970 i
+ 1, idx_pblock(path
[i
].p_idx
));
1971 memset(path
+ i
+ 1, 0, sizeof(*path
));
1972 bh
= sb_bread(sb
, idx_pblock(path
[i
].p_idx
));
1974 /* should we reset i_size? */
1978 if (WARN_ON(i
+ 1 > depth
)) {
1982 if (ext4_ext_check_header(inode
, ext_block_hdr(bh
),
1987 path
[i
+ 1].p_bh
= bh
;
1989 /* save actual number of indexes since this
1990 * number is changed at the next iteration */
1991 path
[i
].p_block
= le16_to_cpu(path
[i
].p_hdr
->eh_entries
);
1994 /* we finished processing this index, go up */
1995 if (path
[i
].p_hdr
->eh_entries
== 0 && i
> 0) {
1996 /* index is empty, remove it;
1997 * handle must be already prepared by the
1998 * truncatei_leaf() */
1999 err
= ext4_ext_rm_idx(handle
, inode
, path
+ i
);
2001 /* root level has p_bh == NULL, brelse() eats this */
2002 brelse(path
[i
].p_bh
);
2003 path
[i
].p_bh
= NULL
;
2005 ext_debug("return to level %d\n", i
);
2009 /* TODO: flexible tree reduction should be here */
2010 if (path
->p_hdr
->eh_entries
== 0) {
2012 * truncate to zero freed all the tree,
2013 * so we need to correct eh_depth
2015 err
= ext4_ext_get_access(handle
, inode
, path
);
2017 ext_inode_hdr(inode
)->eh_depth
= 0;
2018 ext_inode_hdr(inode
)->eh_max
=
2019 cpu_to_le16(ext4_ext_space_root(inode
));
2020 err
= ext4_ext_dirty(handle
, inode
, path
);
2024 ext4_ext_tree_changed(inode
);
2025 ext4_ext_drop_refs(path
);
2027 ext4_journal_stop(handle
);
2033 * called at mount time
2035 void ext4_ext_init(struct super_block
*sb
)
2038 * possible initialization would be here
2041 if (test_opt(sb
, EXTENTS
)) {
2042 printk("EXT4-fs: file extents enabled");
2043 #ifdef AGGRESSIVE_TEST
2044 printk(", aggressive tests");
2046 #ifdef CHECK_BINSEARCH
2047 printk(", check binsearch");
2049 #ifdef EXTENTS_STATS
2053 #ifdef EXTENTS_STATS
2054 spin_lock_init(&EXT4_SB(sb
)->s_ext_stats_lock
);
2055 EXT4_SB(sb
)->s_ext_min
= 1 << 30;
2056 EXT4_SB(sb
)->s_ext_max
= 0;
2062 * called at umount time
2064 void ext4_ext_release(struct super_block
*sb
)
2066 if (!test_opt(sb
, EXTENTS
))
2069 #ifdef EXTENTS_STATS
2070 if (EXT4_SB(sb
)->s_ext_blocks
&& EXT4_SB(sb
)->s_ext_extents
) {
2071 struct ext4_sb_info
*sbi
= EXT4_SB(sb
);
2072 printk(KERN_ERR
"EXT4-fs: %lu blocks in %lu extents (%lu ave)\n",
2073 sbi
->s_ext_blocks
, sbi
->s_ext_extents
,
2074 sbi
->s_ext_blocks
/ sbi
->s_ext_extents
);
2075 printk(KERN_ERR
"EXT4-fs: extents: %lu min, %lu max, max depth %lu\n",
2076 sbi
->s_ext_min
, sbi
->s_ext_max
, sbi
->s_depth_max
);
2082 * This function is called by ext4_ext_get_blocks() if someone tries to write
2083 * to an uninitialized extent. It may result in splitting the uninitialized
2084 * extent into multiple extents (upto three - one initialized and two
2086 * There are three possibilities:
2087 * a> There is no split required: Entire extent should be initialized
2088 * b> Splits in two extents: Write is happening at either end of the extent
2089 * c> Splits in three extents: Somone is writing in middle of the extent
2091 int ext4_ext_convert_to_initialized(handle_t
*handle
, struct inode
*inode
,
2092 struct ext4_ext_path
*path
,
2093 ext4_fsblk_t iblock
,
2094 unsigned long max_blocks
)
2096 struct ext4_extent
*ex
, newex
;
2097 struct ext4_extent
*ex1
= NULL
;
2098 struct ext4_extent
*ex2
= NULL
;
2099 struct ext4_extent
*ex3
= NULL
;
2100 struct ext4_extent_header
*eh
;
2101 unsigned int allocated
, ee_block
, ee_len
, depth
;
2102 ext4_fsblk_t newblock
;
2106 depth
= ext_depth(inode
);
2107 eh
= path
[depth
].p_hdr
;
2108 ex
= path
[depth
].p_ext
;
2109 ee_block
= le32_to_cpu(ex
->ee_block
);
2110 ee_len
= ext4_ext_get_actual_len(ex
);
2111 allocated
= ee_len
- (iblock
- ee_block
);
2112 newblock
= iblock
- ee_block
+ ext_pblock(ex
);
2115 /* ex1: ee_block to iblock - 1 : uninitialized */
2116 if (iblock
> ee_block
) {
2118 ex1
->ee_len
= cpu_to_le16(iblock
- ee_block
);
2119 ext4_ext_mark_uninitialized(ex1
);
2123 * for sanity, update the length of the ex2 extent before
2124 * we insert ex3, if ex1 is NULL. This is to avoid temporary
2125 * overlap of blocks.
2127 if (!ex1
&& allocated
> max_blocks
)
2128 ex2
->ee_len
= cpu_to_le16(max_blocks
);
2129 /* ex3: to ee_block + ee_len : uninitialised */
2130 if (allocated
> max_blocks
) {
2131 unsigned int newdepth
;
2133 ex3
->ee_block
= cpu_to_le32(iblock
+ max_blocks
);
2134 ext4_ext_store_pblock(ex3
, newblock
+ max_blocks
);
2135 ex3
->ee_len
= cpu_to_le16(allocated
- max_blocks
);
2136 ext4_ext_mark_uninitialized(ex3
);
2137 err
= ext4_ext_insert_extent(handle
, inode
, path
, ex3
);
2141 * The depth, and hence eh & ex might change
2142 * as part of the insert above.
2144 newdepth
= ext_depth(inode
);
2145 if (newdepth
!= depth
) {
2147 path
= ext4_ext_find_extent(inode
, iblock
, NULL
);
2149 err
= PTR_ERR(path
);
2153 eh
= path
[depth
].p_hdr
;
2154 ex
= path
[depth
].p_ext
;
2158 allocated
= max_blocks
;
2161 * If there was a change of depth as part of the
2162 * insertion of ex3 above, we need to update the length
2163 * of the ex1 extent again here
2165 if (ex1
&& ex1
!= ex
) {
2167 ex1
->ee_len
= cpu_to_le16(iblock
- ee_block
);
2168 ext4_ext_mark_uninitialized(ex1
);
2171 /* ex2: iblock to iblock + maxblocks-1 : initialised */
2172 ex2
->ee_block
= cpu_to_le32(iblock
);
2173 ex2
->ee_start
= cpu_to_le32(newblock
);
2174 ext4_ext_store_pblock(ex2
, newblock
);
2175 ex2
->ee_len
= cpu_to_le16(allocated
);
2178 err
= ext4_ext_get_access(handle
, inode
, path
+ depth
);
2182 * New (initialized) extent starts from the first block
2183 * in the current extent. i.e., ex2 == ex
2184 * We have to see if it can be merged with the extent
2187 if (ex2
> EXT_FIRST_EXTENT(eh
)) {
2189 * To merge left, pass "ex2 - 1" to try_to_merge(),
2190 * since it merges towards right _only_.
2192 ret
= ext4_ext_try_to_merge(inode
, path
, ex2
- 1);
2194 err
= ext4_ext_correct_indexes(handle
, inode
, path
);
2197 depth
= ext_depth(inode
);
2202 * Try to Merge towards right. This might be required
2203 * only when the whole extent is being written to.
2204 * i.e. ex2 == ex and ex3 == NULL.
2207 ret
= ext4_ext_try_to_merge(inode
, path
, ex2
);
2209 err
= ext4_ext_correct_indexes(handle
, inode
, path
);
2214 /* Mark modified extent as dirty */
2215 err
= ext4_ext_dirty(handle
, inode
, path
+ depth
);
2218 err
= ext4_ext_insert_extent(handle
, inode
, path
, &newex
);
2220 return err
? err
: allocated
;
2223 int ext4_ext_get_blocks(handle_t
*handle
, struct inode
*inode
,
2224 ext4_fsblk_t iblock
,
2225 unsigned long max_blocks
, struct buffer_head
*bh_result
,
2226 int create
, int extend_disksize
)
2228 struct ext4_ext_path
*path
= NULL
;
2229 struct ext4_extent_header
*eh
;
2230 struct ext4_extent newex
, *ex
;
2231 ext4_fsblk_t goal
, newblock
;
2232 int err
= 0, depth
, ret
;
2233 unsigned long allocated
= 0;
2235 __clear_bit(BH_New
, &bh_result
->b_state
);
2236 ext_debug("blocks %d/%lu requested for inode %u\n", (int) iblock
,
2237 max_blocks
, (unsigned) inode
->i_ino
);
2238 mutex_lock(&EXT4_I(inode
)->truncate_mutex
);
2240 /* check in cache */
2241 goal
= ext4_ext_in_cache(inode
, iblock
, &newex
);
2243 if (goal
== EXT4_EXT_CACHE_GAP
) {
2246 * block isn't allocated yet and
2247 * user doesn't want to allocate it
2251 /* we should allocate requested block */
2252 } else if (goal
== EXT4_EXT_CACHE_EXTENT
) {
2253 /* block is already allocated */
2255 - le32_to_cpu(newex
.ee_block
)
2256 + ext_pblock(&newex
);
2257 /* number of remaining blocks in the extent */
2258 allocated
= le16_to_cpu(newex
.ee_len
) -
2259 (iblock
- le32_to_cpu(newex
.ee_block
));
2266 /* find extent for this block */
2267 path
= ext4_ext_find_extent(inode
, iblock
, NULL
);
2269 err
= PTR_ERR(path
);
2274 depth
= ext_depth(inode
);
2277 * consistent leaf must not be empty;
2278 * this situation is possible, though, _during_ tree modification;
2279 * this is why assert can't be put in ext4_ext_find_extent()
2281 BUG_ON(path
[depth
].p_ext
== NULL
&& depth
!= 0);
2282 eh
= path
[depth
].p_hdr
;
2284 ex
= path
[depth
].p_ext
;
2286 unsigned long ee_block
= le32_to_cpu(ex
->ee_block
);
2287 ext4_fsblk_t ee_start
= ext_pblock(ex
);
2288 unsigned short ee_len
;
2291 * Uninitialized extents are treated as holes, except that
2292 * we split out initialized portions during a write.
2294 ee_len
= ext4_ext_get_actual_len(ex
);
2295 /* if found extent covers block, simply return it */
2296 if (iblock
>= ee_block
&& iblock
< ee_block
+ ee_len
) {
2297 newblock
= iblock
- ee_block
+ ee_start
;
2298 /* number of remaining blocks in the extent */
2299 allocated
= ee_len
- (iblock
- ee_block
);
2300 ext_debug("%d fit into %lu:%d -> %llu\n", (int) iblock
,
2301 ee_block
, ee_len
, newblock
);
2303 /* Do not put uninitialized extent in the cache */
2304 if (!ext4_ext_is_uninitialized(ex
)) {
2305 ext4_ext_put_in_cache(inode
, ee_block
,
2307 EXT4_EXT_CACHE_EXTENT
);
2310 if (create
== EXT4_CREATE_UNINITIALIZED_EXT
)
2315 ret
= ext4_ext_convert_to_initialized(handle
, inode
,
2327 * requested block isn't allocated yet;
2328 * we couldn't try to create block if create flag is zero
2332 * put just found gap into cache to speed up
2333 * subsequent requests
2335 ext4_ext_put_gap_in_cache(inode
, path
, iblock
);
2339 * Okay, we need to do block allocation. Lazily initialize the block
2340 * allocation info here if necessary.
2342 if (S_ISREG(inode
->i_mode
) && (!EXT4_I(inode
)->i_block_alloc_info
))
2343 ext4_init_block_alloc_info(inode
);
2345 /* allocate new block */
2346 goal
= ext4_ext_find_goal(inode
, path
, iblock
);
2349 * See if request is beyond maximum number of blocks we can have in
2350 * a single extent. For an initialized extent this limit is
2351 * EXT_INIT_MAX_LEN and for an uninitialized extent this limit is
2352 * EXT_UNINIT_MAX_LEN.
2354 if (max_blocks
> EXT_INIT_MAX_LEN
&&
2355 create
!= EXT4_CREATE_UNINITIALIZED_EXT
)
2356 max_blocks
= EXT_INIT_MAX_LEN
;
2357 else if (max_blocks
> EXT_UNINIT_MAX_LEN
&&
2358 create
== EXT4_CREATE_UNINITIALIZED_EXT
)
2359 max_blocks
= EXT_UNINIT_MAX_LEN
;
2361 /* Check if we can really insert (iblock)::(iblock+max_blocks) extent */
2362 newex
.ee_block
= cpu_to_le32(iblock
);
2363 newex
.ee_len
= cpu_to_le16(max_blocks
);
2364 err
= ext4_ext_check_overlap(inode
, &newex
, path
);
2366 allocated
= le16_to_cpu(newex
.ee_len
);
2368 allocated
= max_blocks
;
2369 newblock
= ext4_new_blocks(handle
, inode
, goal
, &allocated
, &err
);
2372 ext_debug("allocate new block: goal %llu, found %llu/%lu\n",
2373 goal
, newblock
, allocated
);
2375 /* try to insert new extent into found leaf and return */
2376 ext4_ext_store_pblock(&newex
, newblock
);
2377 newex
.ee_len
= cpu_to_le16(allocated
);
2378 if (create
== EXT4_CREATE_UNINITIALIZED_EXT
) /* Mark uninitialized */
2379 ext4_ext_mark_uninitialized(&newex
);
2380 err
= ext4_ext_insert_extent(handle
, inode
, path
, &newex
);
2382 /* free data blocks we just allocated */
2383 ext4_free_blocks(handle
, inode
, ext_pblock(&newex
),
2384 le16_to_cpu(newex
.ee_len
));
2388 if (extend_disksize
&& inode
->i_size
> EXT4_I(inode
)->i_disksize
)
2389 EXT4_I(inode
)->i_disksize
= inode
->i_size
;
2391 /* previous routine could use block we allocated */
2392 newblock
= ext_pblock(&newex
);
2394 __set_bit(BH_New
, &bh_result
->b_state
);
2396 /* Cache only when it is _not_ an uninitialized extent */
2397 if (create
!= EXT4_CREATE_UNINITIALIZED_EXT
)
2398 ext4_ext_put_in_cache(inode
, iblock
, allocated
, newblock
,
2399 EXT4_EXT_CACHE_EXTENT
);
2401 if (allocated
> max_blocks
)
2402 allocated
= max_blocks
;
2403 ext4_ext_show_leaf(inode
, path
);
2404 __set_bit(BH_Mapped
, &bh_result
->b_state
);
2405 bh_result
->b_bdev
= inode
->i_sb
->s_bdev
;
2406 bh_result
->b_blocknr
= newblock
;
2409 ext4_ext_drop_refs(path
);
2412 mutex_unlock(&EXT4_I(inode
)->truncate_mutex
);
2414 return err
? err
: allocated
;
2417 void ext4_ext_truncate(struct inode
* inode
, struct page
*page
)
2419 struct address_space
*mapping
= inode
->i_mapping
;
2420 struct super_block
*sb
= inode
->i_sb
;
2421 unsigned long last_block
;
2426 * probably first extent we're gonna free will be last in block
2428 err
= ext4_writepage_trans_blocks(inode
) + 3;
2429 handle
= ext4_journal_start(inode
, err
);
2430 if (IS_ERR(handle
)) {
2432 clear_highpage(page
);
2433 flush_dcache_page(page
);
2435 page_cache_release(page
);
2441 ext4_block_truncate_page(handle
, page
, mapping
, inode
->i_size
);
2443 mutex_lock(&EXT4_I(inode
)->truncate_mutex
);
2444 ext4_ext_invalidate_cache(inode
);
2447 * TODO: optimization is possible here.
2448 * Probably we need not scan at all,
2449 * because page truncation is enough.
2451 if (ext4_orphan_add(handle
, inode
))
2454 /* we have to know where to truncate from in crash case */
2455 EXT4_I(inode
)->i_disksize
= inode
->i_size
;
2456 ext4_mark_inode_dirty(handle
, inode
);
2458 last_block
= (inode
->i_size
+ sb
->s_blocksize
- 1)
2459 >> EXT4_BLOCK_SIZE_BITS(sb
);
2460 err
= ext4_ext_remove_space(inode
, last_block
);
2462 /* In a multi-transaction truncate, we only make the final
2463 * transaction synchronous.
2470 * If this was a simple ftruncate() and the file will remain alive,
2471 * then we need to clear up the orphan record which we created above.
2472 * However, if this was a real unlink then we were called by
2473 * ext4_delete_inode(), and we allow that function to clean up the
2474 * orphan info for us.
2477 ext4_orphan_del(handle
, inode
);
2479 mutex_unlock(&EXT4_I(inode
)->truncate_mutex
);
2480 ext4_journal_stop(handle
);
2484 * ext4_ext_writepage_trans_blocks:
2485 * calculate max number of blocks we could modify
2486 * in order to allocate new block for an inode
2488 int ext4_ext_writepage_trans_blocks(struct inode
*inode
, int num
)
2492 needed
= ext4_ext_calc_credits_for_insert(inode
, NULL
);
2494 /* caller wants to allocate num blocks, but note it includes sb */
2495 needed
= needed
* num
- (num
- 1);
2498 needed
+= 2 * EXT4_QUOTA_TRANS_BLOCKS(inode
->i_sb
);
2505 * preallocate space for a file. This implements ext4's fallocate inode
2506 * operation, which gets called from sys_fallocate system call.
2507 * For block-mapped files, posix_fallocate should fall back to the method
2508 * of writing zeroes to the required new blocks (the same behavior which is
2509 * expected for file systems which do not support fallocate() system call).
2511 long ext4_fallocate(struct inode
*inode
, int mode
, loff_t offset
, loff_t len
)
2514 ext4_fsblk_t block
, max_blocks
;
2515 ext4_fsblk_t nblocks
= 0;
2519 struct buffer_head map_bh
;
2520 unsigned int credits
, blkbits
= inode
->i_blkbits
;
2523 * currently supporting (pre)allocate mode for extent-based
2526 if (!(EXT4_I(inode
)->i_flags
& EXT4_EXTENTS_FL
))
2529 /* preallocation to directories is currently not supported */
2530 if (S_ISDIR(inode
->i_mode
))
2533 block
= offset
>> blkbits
;
2534 max_blocks
= (EXT4_BLOCK_ALIGN(len
+ offset
, blkbits
) >> blkbits
)
2538 * credits to insert 1 extent into extent tree + buffers to be able to
2539 * modify 1 super block, 1 block bitmap and 1 group descriptor.
2541 credits
= EXT4_DATA_TRANS_BLOCKS(inode
->i_sb
) + 3;
2543 while (ret
>= 0 && ret
< max_blocks
) {
2544 block
= block
+ ret
;
2545 max_blocks
= max_blocks
- ret
;
2546 handle
= ext4_journal_start(inode
, credits
);
2547 if (IS_ERR(handle
)) {
2548 ret
= PTR_ERR(handle
);
2552 ret
= ext4_ext_get_blocks(handle
, inode
, block
,
2553 max_blocks
, &map_bh
,
2554 EXT4_CREATE_UNINITIALIZED_EXT
, 0);
2557 ext4_error(inode
->i_sb
, "ext4_fallocate",
2558 "ext4_ext_get_blocks returned 0! inode#%lu"
2559 ", block=%llu, max_blocks=%llu",
2560 inode
->i_ino
, block
, max_blocks
);
2562 ext4_mark_inode_dirty(handle
, inode
);
2563 ret2
= ext4_journal_stop(handle
);
2567 /* check wrap through sign-bit/zero here */
2568 if ((block
+ ret
) < 0 || (block
+ ret
) < block
) {
2570 ext4_mark_inode_dirty(handle
, inode
);
2571 ret2
= ext4_journal_stop(handle
);
2574 if (buffer_new(&map_bh
) && ((block
+ ret
) >
2575 (EXT4_BLOCK_ALIGN(i_size_read(inode
), blkbits
)
2577 nblocks
= nblocks
+ ret
;
2580 /* Update ctime if new blocks get allocated */
2582 struct timespec now
;
2584 now
= current_fs_time(inode
->i_sb
);
2585 if (!timespec_equal(&inode
->i_ctime
, &now
))
2586 inode
->i_ctime
= now
;
2589 ext4_mark_inode_dirty(handle
, inode
);
2590 ret2
= ext4_journal_stop(handle
);
2595 if (ret
== -ENOSPC
&& ext4_should_retry_alloc(inode
->i_sb
, &retries
))
2599 * Time to update the file size.
2600 * Update only when preallocation was requested beyond the file size.
2602 if (!(mode
& FALLOC_FL_KEEP_SIZE
) &&
2603 (offset
+ len
) > i_size_read(inode
)) {
2606 * if no error, we assume preallocation succeeded
2609 mutex_lock(&inode
->i_mutex
);
2610 i_size_write(inode
, offset
+ len
);
2611 EXT4_I(inode
)->i_disksize
= i_size_read(inode
);
2612 mutex_unlock(&inode
->i_mutex
);
2613 } else if (ret
< 0 && nblocks
) {
2614 /* Handle partial allocation scenario */
2617 mutex_lock(&inode
->i_mutex
);
2618 newsize
= (nblocks
<< blkbits
) + i_size_read(inode
);
2619 i_size_write(inode
, EXT4_BLOCK_ALIGN(newsize
, blkbits
));
2620 EXT4_I(inode
)->i_disksize
= i_size_read(inode
);
2621 mutex_unlock(&inode
->i_mutex
);
2625 return ret
> 0 ? ret2
: ret
;