xref: /openbmc/linux/fs/ext4/extents.c (revision e6362609b6c71c5b802026be9cf263bbdd67a50e)
1a86c6181SAlex Tomas /*
2a86c6181SAlex Tomas  * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
3a86c6181SAlex Tomas  * Written by Alex Tomas <alex@clusterfs.com>
4a86c6181SAlex Tomas  *
5a86c6181SAlex Tomas  * Architecture independence:
6a86c6181SAlex Tomas  *   Copyright (c) 2005, Bull S.A.
7a86c6181SAlex Tomas  *   Written by Pierre Peiffer <pierre.peiffer@bull.net>
8a86c6181SAlex Tomas  *
9a86c6181SAlex Tomas  * This program is free software; you can redistribute it and/or modify
10a86c6181SAlex Tomas  * it under the terms of the GNU General Public License version 2 as
11a86c6181SAlex Tomas  * published by the Free Software Foundation.
12a86c6181SAlex Tomas  *
13a86c6181SAlex Tomas  * This program is distributed in the hope that it will be useful,
14a86c6181SAlex Tomas  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15a86c6181SAlex Tomas  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16a86c6181SAlex Tomas  * GNU General Public License for more details.
17a86c6181SAlex Tomas  *
18a86c6181SAlex Tomas  * You should have received a copy of the GNU General Public Licens
19a86c6181SAlex Tomas  * along with this program; if not, write to the Free Software
20a86c6181SAlex Tomas  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-
21a86c6181SAlex Tomas  */
22a86c6181SAlex Tomas 
23a86c6181SAlex Tomas /*
24a86c6181SAlex Tomas  * Extents support for EXT4
25a86c6181SAlex Tomas  *
26a86c6181SAlex Tomas  * TODO:
27a86c6181SAlex Tomas  *   - ext4*_error() should be used in some situations
28a86c6181SAlex Tomas  *   - analyze all BUG()/BUG_ON(), use -EIO where appropriate
29a86c6181SAlex Tomas  *   - smart tree reduction
30a86c6181SAlex Tomas  */
31a86c6181SAlex Tomas 
32a86c6181SAlex Tomas #include <linux/module.h>
33a86c6181SAlex Tomas #include <linux/fs.h>
34a86c6181SAlex Tomas #include <linux/time.h>
35cd02ff0bSMingming Cao #include <linux/jbd2.h>
36a86c6181SAlex Tomas #include <linux/highuid.h>
37a86c6181SAlex Tomas #include <linux/pagemap.h>
38a86c6181SAlex Tomas #include <linux/quotaops.h>
39a86c6181SAlex Tomas #include <linux/string.h>
40a86c6181SAlex Tomas #include <linux/slab.h>
41a2df2a63SAmit Arora #include <linux/falloc.h>
42a86c6181SAlex Tomas #include <asm/uaccess.h>
436873fa0dSEric Sandeen #include <linux/fiemap.h>
443dcf5451SChristoph Hellwig #include "ext4_jbd2.h"
453dcf5451SChristoph Hellwig #include "ext4_extents.h"
46a86c6181SAlex Tomas 
47a86c6181SAlex Tomas 
48d0d856e8SRandy Dunlap /*
49d0d856e8SRandy Dunlap  * ext_pblock:
50d0d856e8SRandy Dunlap  * combine low and high parts of physical block number into ext4_fsblk_t
51d0d856e8SRandy Dunlap  */
52748de673SAkira Fujita ext4_fsblk_t ext_pblock(struct ext4_extent *ex)
53f65e6fbaSAlex Tomas {
54f65e6fbaSAlex Tomas 	ext4_fsblk_t block;
55f65e6fbaSAlex Tomas 
56b377611dSAneesh Kumar K.V 	block = le32_to_cpu(ex->ee_start_lo);
57f65e6fbaSAlex Tomas 	block |= ((ext4_fsblk_t) le16_to_cpu(ex->ee_start_hi) << 31) << 1;
58f65e6fbaSAlex Tomas 	return block;
59f65e6fbaSAlex Tomas }
60f65e6fbaSAlex Tomas 
61d0d856e8SRandy Dunlap /*
62d0d856e8SRandy Dunlap  * idx_pblock:
63d0d856e8SRandy Dunlap  * combine low and high parts of a leaf physical block number into ext4_fsblk_t
64d0d856e8SRandy Dunlap  */
65c14c6fd5SAneesh Kumar K.V ext4_fsblk_t idx_pblock(struct ext4_extent_idx *ix)
66f65e6fbaSAlex Tomas {
67f65e6fbaSAlex Tomas 	ext4_fsblk_t block;
68f65e6fbaSAlex Tomas 
69d8dd0b45SAneesh Kumar K.V 	block = le32_to_cpu(ix->ei_leaf_lo);
70f65e6fbaSAlex Tomas 	block |= ((ext4_fsblk_t) le16_to_cpu(ix->ei_leaf_hi) << 31) << 1;
71f65e6fbaSAlex Tomas 	return block;
72f65e6fbaSAlex Tomas }
73f65e6fbaSAlex Tomas 
74d0d856e8SRandy Dunlap /*
75d0d856e8SRandy Dunlap  * ext4_ext_store_pblock:
76d0d856e8SRandy Dunlap  * stores a large physical block number into an extent struct,
77d0d856e8SRandy Dunlap  * breaking it into parts
78d0d856e8SRandy Dunlap  */
79c14c6fd5SAneesh Kumar K.V void ext4_ext_store_pblock(struct ext4_extent *ex, ext4_fsblk_t pb)
80f65e6fbaSAlex Tomas {
81b377611dSAneesh Kumar K.V 	ex->ee_start_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff));
82f65e6fbaSAlex Tomas 	ex->ee_start_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) & 0xffff);
83f65e6fbaSAlex Tomas }
84f65e6fbaSAlex Tomas 
85d0d856e8SRandy Dunlap /*
86d0d856e8SRandy Dunlap  * ext4_idx_store_pblock:
87d0d856e8SRandy Dunlap  * stores a large physical block number into an index struct,
88d0d856e8SRandy Dunlap  * breaking it into parts
89d0d856e8SRandy Dunlap  */
9009b88252SAvantika Mathur static void ext4_idx_store_pblock(struct ext4_extent_idx *ix, ext4_fsblk_t pb)
91f65e6fbaSAlex Tomas {
92d8dd0b45SAneesh Kumar K.V 	ix->ei_leaf_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff));
93f65e6fbaSAlex Tomas 	ix->ei_leaf_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) & 0xffff);
94f65e6fbaSAlex Tomas }
95f65e6fbaSAlex Tomas 
96487caeefSJan Kara static int ext4_ext_truncate_extend_restart(handle_t *handle,
97487caeefSJan Kara 					    struct inode *inode,
98487caeefSJan Kara 					    int needed)
99a86c6181SAlex Tomas {
100a86c6181SAlex Tomas 	int err;
101a86c6181SAlex Tomas 
1020390131bSFrank Mayhar 	if (!ext4_handle_valid(handle))
1030390131bSFrank Mayhar 		return 0;
104a86c6181SAlex Tomas 	if (handle->h_buffer_credits > needed)
1059102e4faSShen Feng 		return 0;
1069102e4faSShen Feng 	err = ext4_journal_extend(handle, needed);
1070123c939STheodore Ts'o 	if (err <= 0)
1089102e4faSShen Feng 		return err;
109487caeefSJan Kara 	err = ext4_truncate_restart_trans(handle, inode, needed);
110487caeefSJan Kara 	/*
111487caeefSJan Kara 	 * We have dropped i_data_sem so someone might have cached again
112487caeefSJan Kara 	 * an extent we are going to truncate.
113487caeefSJan Kara 	 */
114487caeefSJan Kara 	ext4_ext_invalidate_cache(inode);
115487caeefSJan Kara 
116487caeefSJan Kara 	return err;
117a86c6181SAlex Tomas }
118a86c6181SAlex Tomas 
119a86c6181SAlex Tomas /*
120a86c6181SAlex Tomas  * could return:
121a86c6181SAlex Tomas  *  - EROFS
122a86c6181SAlex Tomas  *  - ENOMEM
123a86c6181SAlex Tomas  */
124a86c6181SAlex Tomas static int ext4_ext_get_access(handle_t *handle, struct inode *inode,
125a86c6181SAlex Tomas 				struct ext4_ext_path *path)
126a86c6181SAlex Tomas {
127a86c6181SAlex Tomas 	if (path->p_bh) {
128a86c6181SAlex Tomas 		/* path points to block */
129a86c6181SAlex Tomas 		return ext4_journal_get_write_access(handle, path->p_bh);
130a86c6181SAlex Tomas 	}
131a86c6181SAlex Tomas 	/* path points to leaf/index in inode body */
132a86c6181SAlex Tomas 	/* we use in-core data, no need to protect them */
133a86c6181SAlex Tomas 	return 0;
134a86c6181SAlex Tomas }
135a86c6181SAlex Tomas 
136a86c6181SAlex Tomas /*
137a86c6181SAlex Tomas  * could return:
138a86c6181SAlex Tomas  *  - EROFS
139a86c6181SAlex Tomas  *  - ENOMEM
140a86c6181SAlex Tomas  *  - EIO
141a86c6181SAlex Tomas  */
142a86c6181SAlex Tomas static int ext4_ext_dirty(handle_t *handle, struct inode *inode,
143a86c6181SAlex Tomas 				struct ext4_ext_path *path)
144a86c6181SAlex Tomas {
145a86c6181SAlex Tomas 	int err;
146a86c6181SAlex Tomas 	if (path->p_bh) {
147a86c6181SAlex Tomas 		/* path points to block */
1480390131bSFrank Mayhar 		err = ext4_handle_dirty_metadata(handle, inode, path->p_bh);
149a86c6181SAlex Tomas 	} else {
150a86c6181SAlex Tomas 		/* path points to leaf/index in inode body */
151a86c6181SAlex Tomas 		err = ext4_mark_inode_dirty(handle, inode);
152a86c6181SAlex Tomas 	}
153a86c6181SAlex Tomas 	return err;
154a86c6181SAlex Tomas }
155a86c6181SAlex Tomas 
156f65e6fbaSAlex Tomas static ext4_fsblk_t ext4_ext_find_goal(struct inode *inode,
157a86c6181SAlex Tomas 			      struct ext4_ext_path *path,
158725d26d3SAneesh Kumar K.V 			      ext4_lblk_t block)
159a86c6181SAlex Tomas {
160a86c6181SAlex Tomas 	struct ext4_inode_info *ei = EXT4_I(inode);
161f65e6fbaSAlex Tomas 	ext4_fsblk_t bg_start;
16274d3487fSValerie Clement 	ext4_fsblk_t last_block;
163f65e6fbaSAlex Tomas 	ext4_grpblk_t colour;
164a4912123STheodore Ts'o 	ext4_group_t block_group;
165a4912123STheodore Ts'o 	int flex_size = ext4_flex_bg_size(EXT4_SB(inode->i_sb));
166a86c6181SAlex Tomas 	int depth;
167a86c6181SAlex Tomas 
168a86c6181SAlex Tomas 	if (path) {
169a86c6181SAlex Tomas 		struct ext4_extent *ex;
170a86c6181SAlex Tomas 		depth = path->p_depth;
171a86c6181SAlex Tomas 
172a86c6181SAlex Tomas 		/* try to predict block placement */
1737e028976SAvantika Mathur 		ex = path[depth].p_ext;
1747e028976SAvantika Mathur 		if (ex)
175f65e6fbaSAlex Tomas 			return ext_pblock(ex)+(block-le32_to_cpu(ex->ee_block));
176a86c6181SAlex Tomas 
177d0d856e8SRandy Dunlap 		/* it looks like index is empty;
178d0d856e8SRandy Dunlap 		 * try to find starting block from index itself */
179a86c6181SAlex Tomas 		if (path[depth].p_bh)
180a86c6181SAlex Tomas 			return path[depth].p_bh->b_blocknr;
181a86c6181SAlex Tomas 	}
182a86c6181SAlex Tomas 
183a86c6181SAlex Tomas 	/* OK. use inode's group */
184a4912123STheodore Ts'o 	block_group = ei->i_block_group;
185a4912123STheodore Ts'o 	if (flex_size >= EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME) {
186a4912123STheodore Ts'o 		/*
187a4912123STheodore Ts'o 		 * If there are at least EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME
188a4912123STheodore Ts'o 		 * block groups per flexgroup, reserve the first block
189a4912123STheodore Ts'o 		 * group for directories and special files.  Regular
190a4912123STheodore Ts'o 		 * files will start at the second block group.  This
191a4912123STheodore Ts'o 		 * tends to speed up directory access and improves
192a4912123STheodore Ts'o 		 * fsck times.
193a4912123STheodore Ts'o 		 */
194a4912123STheodore Ts'o 		block_group &= ~(flex_size-1);
195a4912123STheodore Ts'o 		if (S_ISREG(inode->i_mode))
196a4912123STheodore Ts'o 			block_group++;
197a4912123STheodore Ts'o 	}
198a4912123STheodore Ts'o 	bg_start = (block_group * EXT4_BLOCKS_PER_GROUP(inode->i_sb)) +
199a86c6181SAlex Tomas 		le32_to_cpu(EXT4_SB(inode->i_sb)->s_es->s_first_data_block);
20074d3487fSValerie Clement 	last_block = ext4_blocks_count(EXT4_SB(inode->i_sb)->s_es) - 1;
20174d3487fSValerie Clement 
202a4912123STheodore Ts'o 	/*
203a4912123STheodore Ts'o 	 * If we are doing delayed allocation, we don't need take
204a4912123STheodore Ts'o 	 * colour into account.
205a4912123STheodore Ts'o 	 */
206a4912123STheodore Ts'o 	if (test_opt(inode->i_sb, DELALLOC))
207a4912123STheodore Ts'o 		return bg_start;
208a4912123STheodore Ts'o 
20974d3487fSValerie Clement 	if (bg_start + EXT4_BLOCKS_PER_GROUP(inode->i_sb) <= last_block)
210a86c6181SAlex Tomas 		colour = (current->pid % 16) *
211a86c6181SAlex Tomas 			(EXT4_BLOCKS_PER_GROUP(inode->i_sb) / 16);
21274d3487fSValerie Clement 	else
21374d3487fSValerie Clement 		colour = (current->pid % 16) * ((last_block - bg_start) / 16);
214a86c6181SAlex Tomas 	return bg_start + colour + block;
215a86c6181SAlex Tomas }
216a86c6181SAlex Tomas 
217654b4908SAneesh Kumar K.V /*
218654b4908SAneesh Kumar K.V  * Allocation for a meta data block
219654b4908SAneesh Kumar K.V  */
220f65e6fbaSAlex Tomas static ext4_fsblk_t
221654b4908SAneesh Kumar K.V ext4_ext_new_meta_block(handle_t *handle, struct inode *inode,
222a86c6181SAlex Tomas 			struct ext4_ext_path *path,
223a86c6181SAlex Tomas 			struct ext4_extent *ex, int *err)
224a86c6181SAlex Tomas {
225f65e6fbaSAlex Tomas 	ext4_fsblk_t goal, newblock;
226a86c6181SAlex Tomas 
227a86c6181SAlex Tomas 	goal = ext4_ext_find_goal(inode, path, le32_to_cpu(ex->ee_block));
22897df5d15STheodore Ts'o 	newblock = ext4_new_meta_blocks(handle, inode, goal, NULL, err);
229a86c6181SAlex Tomas 	return newblock;
230a86c6181SAlex Tomas }
231a86c6181SAlex Tomas 
23255ad63bfSTheodore Ts'o static inline int ext4_ext_space_block(struct inode *inode, int check)
233a86c6181SAlex Tomas {
234a86c6181SAlex Tomas 	int size;
235a86c6181SAlex Tomas 
236a86c6181SAlex Tomas 	size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
237a86c6181SAlex Tomas 			/ sizeof(struct ext4_extent);
23855ad63bfSTheodore Ts'o 	if (!check) {
239bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST
240a86c6181SAlex Tomas 		if (size > 6)
241a86c6181SAlex Tomas 			size = 6;
242a86c6181SAlex Tomas #endif
24355ad63bfSTheodore Ts'o 	}
244a86c6181SAlex Tomas 	return size;
245a86c6181SAlex Tomas }
246a86c6181SAlex Tomas 
24755ad63bfSTheodore Ts'o static inline int ext4_ext_space_block_idx(struct inode *inode, int check)
248a86c6181SAlex Tomas {
249a86c6181SAlex Tomas 	int size;
250a86c6181SAlex Tomas 
251a86c6181SAlex Tomas 	size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
252a86c6181SAlex Tomas 			/ sizeof(struct ext4_extent_idx);
25355ad63bfSTheodore Ts'o 	if (!check) {
254bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST
255a86c6181SAlex Tomas 		if (size > 5)
256a86c6181SAlex Tomas 			size = 5;
257a86c6181SAlex Tomas #endif
25855ad63bfSTheodore Ts'o 	}
259a86c6181SAlex Tomas 	return size;
260a86c6181SAlex Tomas }
261a86c6181SAlex Tomas 
26255ad63bfSTheodore Ts'o static inline int ext4_ext_space_root(struct inode *inode, int check)
263a86c6181SAlex Tomas {
264a86c6181SAlex Tomas 	int size;
265a86c6181SAlex Tomas 
266a86c6181SAlex Tomas 	size = sizeof(EXT4_I(inode)->i_data);
267a86c6181SAlex Tomas 	size -= sizeof(struct ext4_extent_header);
268a86c6181SAlex Tomas 	size /= sizeof(struct ext4_extent);
26955ad63bfSTheodore Ts'o 	if (!check) {
270bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST
271a86c6181SAlex Tomas 		if (size > 3)
272a86c6181SAlex Tomas 			size = 3;
273a86c6181SAlex Tomas #endif
27455ad63bfSTheodore Ts'o 	}
275a86c6181SAlex Tomas 	return size;
276a86c6181SAlex Tomas }
277a86c6181SAlex Tomas 
27855ad63bfSTheodore Ts'o static inline int ext4_ext_space_root_idx(struct inode *inode, int check)
279a86c6181SAlex Tomas {
280a86c6181SAlex Tomas 	int size;
281a86c6181SAlex Tomas 
282a86c6181SAlex Tomas 	size = sizeof(EXT4_I(inode)->i_data);
283a86c6181SAlex Tomas 	size -= sizeof(struct ext4_extent_header);
284a86c6181SAlex Tomas 	size /= sizeof(struct ext4_extent_idx);
28555ad63bfSTheodore Ts'o 	if (!check) {
286bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST
287a86c6181SAlex Tomas 		if (size > 4)
288a86c6181SAlex Tomas 			size = 4;
289a86c6181SAlex Tomas #endif
29055ad63bfSTheodore Ts'o 	}
291a86c6181SAlex Tomas 	return size;
292a86c6181SAlex Tomas }
293a86c6181SAlex Tomas 
294d2a17637SMingming Cao /*
295d2a17637SMingming Cao  * Calculate the number of metadata blocks needed
296d2a17637SMingming Cao  * to allocate @blocks
297d2a17637SMingming Cao  * Worse case is one block per extent
298d2a17637SMingming Cao  */
299d2a17637SMingming Cao int ext4_ext_calc_metadata_amount(struct inode *inode, int blocks)
300d2a17637SMingming Cao {
301d2a17637SMingming Cao 	int lcap, icap, rcap, leafs, idxs, num;
302d2a17637SMingming Cao 	int newextents = blocks;
303d2a17637SMingming Cao 
30455ad63bfSTheodore Ts'o 	rcap = ext4_ext_space_root_idx(inode, 0);
30555ad63bfSTheodore Ts'o 	lcap = ext4_ext_space_block(inode, 0);
30655ad63bfSTheodore Ts'o 	icap = ext4_ext_space_block_idx(inode, 0);
307d2a17637SMingming Cao 
308d2a17637SMingming Cao 	/* number of new leaf blocks needed */
309d2a17637SMingming Cao 	num = leafs = (newextents + lcap - 1) / lcap;
310d2a17637SMingming Cao 
311d2a17637SMingming Cao 	/*
312d2a17637SMingming Cao 	 * Worse case, we need separate index block(s)
313d2a17637SMingming Cao 	 * to link all new leaf blocks
314d2a17637SMingming Cao 	 */
315d2a17637SMingming Cao 	idxs = (leafs + icap - 1) / icap;
316d2a17637SMingming Cao 	do {
317d2a17637SMingming Cao 		num += idxs;
318d2a17637SMingming Cao 		idxs = (idxs + icap - 1) / icap;
319d2a17637SMingming Cao 	} while (idxs > rcap);
320d2a17637SMingming Cao 
321d2a17637SMingming Cao 	return num;
322d2a17637SMingming Cao }
323d2a17637SMingming Cao 
324c29c0ae7SAlex Tomas static int
325c29c0ae7SAlex Tomas ext4_ext_max_entries(struct inode *inode, int depth)
326c29c0ae7SAlex Tomas {
327c29c0ae7SAlex Tomas 	int max;
328c29c0ae7SAlex Tomas 
329c29c0ae7SAlex Tomas 	if (depth == ext_depth(inode)) {
330c29c0ae7SAlex Tomas 		if (depth == 0)
33155ad63bfSTheodore Ts'o 			max = ext4_ext_space_root(inode, 1);
332c29c0ae7SAlex Tomas 		else
33355ad63bfSTheodore Ts'o 			max = ext4_ext_space_root_idx(inode, 1);
334c29c0ae7SAlex Tomas 	} else {
335c29c0ae7SAlex Tomas 		if (depth == 0)
33655ad63bfSTheodore Ts'o 			max = ext4_ext_space_block(inode, 1);
337c29c0ae7SAlex Tomas 		else
33855ad63bfSTheodore Ts'o 			max = ext4_ext_space_block_idx(inode, 1);
339c29c0ae7SAlex Tomas 	}
340c29c0ae7SAlex Tomas 
341c29c0ae7SAlex Tomas 	return max;
342c29c0ae7SAlex Tomas }
343c29c0ae7SAlex Tomas 
34456b19868SAneesh Kumar K.V static int ext4_valid_extent(struct inode *inode, struct ext4_extent *ext)
34556b19868SAneesh Kumar K.V {
3466fd058f7STheodore Ts'o 	ext4_fsblk_t block = ext_pblock(ext);
34756b19868SAneesh Kumar K.V 	int len = ext4_ext_get_actual_len(ext);
348e84a26ceSTheodore Ts'o 
3496fd058f7STheodore Ts'o 	return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, len);
35056b19868SAneesh Kumar K.V }
35156b19868SAneesh Kumar K.V 
35256b19868SAneesh Kumar K.V static int ext4_valid_extent_idx(struct inode *inode,
35356b19868SAneesh Kumar K.V 				struct ext4_extent_idx *ext_idx)
35456b19868SAneesh Kumar K.V {
3556fd058f7STheodore Ts'o 	ext4_fsblk_t block = idx_pblock(ext_idx);
356e84a26ceSTheodore Ts'o 
3576fd058f7STheodore Ts'o 	return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, 1);
35856b19868SAneesh Kumar K.V }
35956b19868SAneesh Kumar K.V 
36056b19868SAneesh Kumar K.V static int ext4_valid_extent_entries(struct inode *inode,
36156b19868SAneesh Kumar K.V 				struct ext4_extent_header *eh,
36256b19868SAneesh Kumar K.V 				int depth)
36356b19868SAneesh Kumar K.V {
36456b19868SAneesh Kumar K.V 	struct ext4_extent *ext;
36556b19868SAneesh Kumar K.V 	struct ext4_extent_idx *ext_idx;
36656b19868SAneesh Kumar K.V 	unsigned short entries;
36756b19868SAneesh Kumar K.V 	if (eh->eh_entries == 0)
36856b19868SAneesh Kumar K.V 		return 1;
36956b19868SAneesh Kumar K.V 
37056b19868SAneesh Kumar K.V 	entries = le16_to_cpu(eh->eh_entries);
37156b19868SAneesh Kumar K.V 
37256b19868SAneesh Kumar K.V 	if (depth == 0) {
37356b19868SAneesh Kumar K.V 		/* leaf entries */
37456b19868SAneesh Kumar K.V 		ext = EXT_FIRST_EXTENT(eh);
37556b19868SAneesh Kumar K.V 		while (entries) {
37656b19868SAneesh Kumar K.V 			if (!ext4_valid_extent(inode, ext))
37756b19868SAneesh Kumar K.V 				return 0;
37856b19868SAneesh Kumar K.V 			ext++;
37956b19868SAneesh Kumar K.V 			entries--;
38056b19868SAneesh Kumar K.V 		}
38156b19868SAneesh Kumar K.V 	} else {
38256b19868SAneesh Kumar K.V 		ext_idx = EXT_FIRST_INDEX(eh);
38356b19868SAneesh Kumar K.V 		while (entries) {
38456b19868SAneesh Kumar K.V 			if (!ext4_valid_extent_idx(inode, ext_idx))
38556b19868SAneesh Kumar K.V 				return 0;
38656b19868SAneesh Kumar K.V 			ext_idx++;
38756b19868SAneesh Kumar K.V 			entries--;
38856b19868SAneesh Kumar K.V 		}
38956b19868SAneesh Kumar K.V 	}
39056b19868SAneesh Kumar K.V 	return 1;
39156b19868SAneesh Kumar K.V }
39256b19868SAneesh Kumar K.V 
39356b19868SAneesh Kumar K.V static int __ext4_ext_check(const char *function, struct inode *inode,
394c29c0ae7SAlex Tomas 					struct ext4_extent_header *eh,
395c29c0ae7SAlex Tomas 					int depth)
396c29c0ae7SAlex Tomas {
397c29c0ae7SAlex Tomas 	const char *error_msg;
398c29c0ae7SAlex Tomas 	int max = 0;
399c29c0ae7SAlex Tomas 
400c29c0ae7SAlex Tomas 	if (unlikely(eh->eh_magic != EXT4_EXT_MAGIC)) {
401c29c0ae7SAlex Tomas 		error_msg = "invalid magic";
402c29c0ae7SAlex Tomas 		goto corrupted;
403c29c0ae7SAlex Tomas 	}
404c29c0ae7SAlex Tomas 	if (unlikely(le16_to_cpu(eh->eh_depth) != depth)) {
405c29c0ae7SAlex Tomas 		error_msg = "unexpected eh_depth";
406c29c0ae7SAlex Tomas 		goto corrupted;
407c29c0ae7SAlex Tomas 	}
408c29c0ae7SAlex Tomas 	if (unlikely(eh->eh_max == 0)) {
409c29c0ae7SAlex Tomas 		error_msg = "invalid eh_max";
410c29c0ae7SAlex Tomas 		goto corrupted;
411c29c0ae7SAlex Tomas 	}
412c29c0ae7SAlex Tomas 	max = ext4_ext_max_entries(inode, depth);
413c29c0ae7SAlex Tomas 	if (unlikely(le16_to_cpu(eh->eh_max) > max)) {
414c29c0ae7SAlex Tomas 		error_msg = "too large eh_max";
415c29c0ae7SAlex Tomas 		goto corrupted;
416c29c0ae7SAlex Tomas 	}
417c29c0ae7SAlex Tomas 	if (unlikely(le16_to_cpu(eh->eh_entries) > le16_to_cpu(eh->eh_max))) {
418c29c0ae7SAlex Tomas 		error_msg = "invalid eh_entries";
419c29c0ae7SAlex Tomas 		goto corrupted;
420c29c0ae7SAlex Tomas 	}
42156b19868SAneesh Kumar K.V 	if (!ext4_valid_extent_entries(inode, eh, depth)) {
42256b19868SAneesh Kumar K.V 		error_msg = "invalid extent entries";
42356b19868SAneesh Kumar K.V 		goto corrupted;
42456b19868SAneesh Kumar K.V 	}
425c29c0ae7SAlex Tomas 	return 0;
426c29c0ae7SAlex Tomas 
427c29c0ae7SAlex Tomas corrupted:
428c29c0ae7SAlex Tomas 	ext4_error(inode->i_sb, function,
42956b19868SAneesh Kumar K.V 			"bad header/extent in inode #%lu: %s - magic %x, "
430c29c0ae7SAlex Tomas 			"entries %u, max %u(%u), depth %u(%u)",
431c29c0ae7SAlex Tomas 			inode->i_ino, error_msg, le16_to_cpu(eh->eh_magic),
432c29c0ae7SAlex Tomas 			le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max),
433c29c0ae7SAlex Tomas 			max, le16_to_cpu(eh->eh_depth), depth);
434c29c0ae7SAlex Tomas 
435c29c0ae7SAlex Tomas 	return -EIO;
436c29c0ae7SAlex Tomas }
437c29c0ae7SAlex Tomas 
43856b19868SAneesh Kumar K.V #define ext4_ext_check(inode, eh, depth)	\
43956b19868SAneesh Kumar K.V 	__ext4_ext_check(__func__, inode, eh, depth)
440c29c0ae7SAlex Tomas 
4417a262f7cSAneesh Kumar K.V int ext4_ext_check_inode(struct inode *inode)
4427a262f7cSAneesh Kumar K.V {
4437a262f7cSAneesh Kumar K.V 	return ext4_ext_check(inode, ext_inode_hdr(inode), ext_depth(inode));
4447a262f7cSAneesh Kumar K.V }
4457a262f7cSAneesh Kumar K.V 
446a86c6181SAlex Tomas #ifdef EXT_DEBUG
447a86c6181SAlex Tomas static void ext4_ext_show_path(struct inode *inode, struct ext4_ext_path *path)
448a86c6181SAlex Tomas {
449a86c6181SAlex Tomas 	int k, l = path->p_depth;
450a86c6181SAlex Tomas 
451a86c6181SAlex Tomas 	ext_debug("path:");
452a86c6181SAlex Tomas 	for (k = 0; k <= l; k++, path++) {
453a86c6181SAlex Tomas 		if (path->p_idx) {
4542ae02107SMingming Cao 		  ext_debug("  %d->%llu", le32_to_cpu(path->p_idx->ei_block),
455f65e6fbaSAlex Tomas 			    idx_pblock(path->p_idx));
456a86c6181SAlex Tomas 		} else if (path->p_ext) {
457553f9008SMingming 			ext_debug("  %d:[%d]%d:%llu ",
458a86c6181SAlex Tomas 				  le32_to_cpu(path->p_ext->ee_block),
459553f9008SMingming 				  ext4_ext_is_uninitialized(path->p_ext),
460a2df2a63SAmit Arora 				  ext4_ext_get_actual_len(path->p_ext),
461f65e6fbaSAlex Tomas 				  ext_pblock(path->p_ext));
462a86c6181SAlex Tomas 		} else
463a86c6181SAlex Tomas 			ext_debug("  []");
464a86c6181SAlex Tomas 	}
465a86c6181SAlex Tomas 	ext_debug("\n");
466a86c6181SAlex Tomas }
467a86c6181SAlex Tomas 
468a86c6181SAlex Tomas static void ext4_ext_show_leaf(struct inode *inode, struct ext4_ext_path *path)
469a86c6181SAlex Tomas {
470a86c6181SAlex Tomas 	int depth = ext_depth(inode);
471a86c6181SAlex Tomas 	struct ext4_extent_header *eh;
472a86c6181SAlex Tomas 	struct ext4_extent *ex;
473a86c6181SAlex Tomas 	int i;
474a86c6181SAlex Tomas 
475a86c6181SAlex Tomas 	if (!path)
476a86c6181SAlex Tomas 		return;
477a86c6181SAlex Tomas 
478a86c6181SAlex Tomas 	eh = path[depth].p_hdr;
479a86c6181SAlex Tomas 	ex = EXT_FIRST_EXTENT(eh);
480a86c6181SAlex Tomas 
481553f9008SMingming 	ext_debug("Displaying leaf extents for inode %lu\n", inode->i_ino);
482553f9008SMingming 
483a86c6181SAlex Tomas 	for (i = 0; i < le16_to_cpu(eh->eh_entries); i++, ex++) {
484553f9008SMingming 		ext_debug("%d:[%d]%d:%llu ", le32_to_cpu(ex->ee_block),
485553f9008SMingming 			  ext4_ext_is_uninitialized(ex),
486a2df2a63SAmit Arora 			  ext4_ext_get_actual_len(ex), ext_pblock(ex));
487a86c6181SAlex Tomas 	}
488a86c6181SAlex Tomas 	ext_debug("\n");
489a86c6181SAlex Tomas }
490a86c6181SAlex Tomas #else
491a86c6181SAlex Tomas #define ext4_ext_show_path(inode, path)
492a86c6181SAlex Tomas #define ext4_ext_show_leaf(inode, path)
493a86c6181SAlex Tomas #endif
494a86c6181SAlex Tomas 
495b35905c1SAneesh Kumar K.V void ext4_ext_drop_refs(struct ext4_ext_path *path)
496a86c6181SAlex Tomas {
497a86c6181SAlex Tomas 	int depth = path->p_depth;
498a86c6181SAlex Tomas 	int i;
499a86c6181SAlex Tomas 
500a86c6181SAlex Tomas 	for (i = 0; i <= depth; i++, path++)
501a86c6181SAlex Tomas 		if (path->p_bh) {
502a86c6181SAlex Tomas 			brelse(path->p_bh);
503a86c6181SAlex Tomas 			path->p_bh = NULL;
504a86c6181SAlex Tomas 		}
505a86c6181SAlex Tomas }
506a86c6181SAlex Tomas 
507a86c6181SAlex Tomas /*
508d0d856e8SRandy Dunlap  * ext4_ext_binsearch_idx:
509d0d856e8SRandy Dunlap  * binary search for the closest index of the given block
510c29c0ae7SAlex Tomas  * the header must be checked before calling this
511a86c6181SAlex Tomas  */
512a86c6181SAlex Tomas static void
513725d26d3SAneesh Kumar K.V ext4_ext_binsearch_idx(struct inode *inode,
514725d26d3SAneesh Kumar K.V 			struct ext4_ext_path *path, ext4_lblk_t block)
515a86c6181SAlex Tomas {
516a86c6181SAlex Tomas 	struct ext4_extent_header *eh = path->p_hdr;
517a86c6181SAlex Tomas 	struct ext4_extent_idx *r, *l, *m;
518a86c6181SAlex Tomas 
519a86c6181SAlex Tomas 
520bba90743SEric Sandeen 	ext_debug("binsearch for %u(idx):  ", block);
521a86c6181SAlex Tomas 
522a86c6181SAlex Tomas 	l = EXT_FIRST_INDEX(eh) + 1;
523e9f410b1SDmitry Monakhov 	r = EXT_LAST_INDEX(eh);
524a86c6181SAlex Tomas 	while (l <= r) {
525a86c6181SAlex Tomas 		m = l + (r - l) / 2;
526a86c6181SAlex Tomas 		if (block < le32_to_cpu(m->ei_block))
527a86c6181SAlex Tomas 			r = m - 1;
528a86c6181SAlex Tomas 		else
529a86c6181SAlex Tomas 			l = m + 1;
53026d535edSDmitry Monakhov 		ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ei_block),
53126d535edSDmitry Monakhov 				m, le32_to_cpu(m->ei_block),
53226d535edSDmitry Monakhov 				r, le32_to_cpu(r->ei_block));
533a86c6181SAlex Tomas 	}
534a86c6181SAlex Tomas 
535a86c6181SAlex Tomas 	path->p_idx = l - 1;
536f65e6fbaSAlex Tomas 	ext_debug("  -> %d->%lld ", le32_to_cpu(path->p_idx->ei_block),
53726d535edSDmitry Monakhov 		  idx_pblock(path->p_idx));
538a86c6181SAlex Tomas 
539a86c6181SAlex Tomas #ifdef CHECK_BINSEARCH
540a86c6181SAlex Tomas 	{
541a86c6181SAlex Tomas 		struct ext4_extent_idx *chix, *ix;
542a86c6181SAlex Tomas 		int k;
543a86c6181SAlex Tomas 
544a86c6181SAlex Tomas 		chix = ix = EXT_FIRST_INDEX(eh);
545a86c6181SAlex Tomas 		for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ix++) {
546a86c6181SAlex Tomas 		  if (k != 0 &&
547a86c6181SAlex Tomas 		      le32_to_cpu(ix->ei_block) <= le32_to_cpu(ix[-1].ei_block)) {
5484776004fSTheodore Ts'o 				printk(KERN_DEBUG "k=%d, ix=0x%p, "
5494776004fSTheodore Ts'o 				       "first=0x%p\n", k,
550a86c6181SAlex Tomas 				       ix, EXT_FIRST_INDEX(eh));
5514776004fSTheodore Ts'o 				printk(KERN_DEBUG "%u <= %u\n",
552a86c6181SAlex Tomas 				       le32_to_cpu(ix->ei_block),
553a86c6181SAlex Tomas 				       le32_to_cpu(ix[-1].ei_block));
554a86c6181SAlex Tomas 			}
555a86c6181SAlex Tomas 			BUG_ON(k && le32_to_cpu(ix->ei_block)
556a86c6181SAlex Tomas 					   <= le32_to_cpu(ix[-1].ei_block));
557a86c6181SAlex Tomas 			if (block < le32_to_cpu(ix->ei_block))
558a86c6181SAlex Tomas 				break;
559a86c6181SAlex Tomas 			chix = ix;
560a86c6181SAlex Tomas 		}
561a86c6181SAlex Tomas 		BUG_ON(chix != path->p_idx);
562a86c6181SAlex Tomas 	}
563a86c6181SAlex Tomas #endif
564a86c6181SAlex Tomas 
565a86c6181SAlex Tomas }
566a86c6181SAlex Tomas 
567a86c6181SAlex Tomas /*
568d0d856e8SRandy Dunlap  * ext4_ext_binsearch:
569d0d856e8SRandy Dunlap  * binary search for closest extent of the given block
570c29c0ae7SAlex Tomas  * the header must be checked before calling this
571a86c6181SAlex Tomas  */
572a86c6181SAlex Tomas static void
573725d26d3SAneesh Kumar K.V ext4_ext_binsearch(struct inode *inode,
574725d26d3SAneesh Kumar K.V 		struct ext4_ext_path *path, ext4_lblk_t block)
575a86c6181SAlex Tomas {
576a86c6181SAlex Tomas 	struct ext4_extent_header *eh = path->p_hdr;
577a86c6181SAlex Tomas 	struct ext4_extent *r, *l, *m;
578a86c6181SAlex Tomas 
579a86c6181SAlex Tomas 	if (eh->eh_entries == 0) {
580a86c6181SAlex Tomas 		/*
581d0d856e8SRandy Dunlap 		 * this leaf is empty:
582a86c6181SAlex Tomas 		 * we get such a leaf in split/add case
583a86c6181SAlex Tomas 		 */
584a86c6181SAlex Tomas 		return;
585a86c6181SAlex Tomas 	}
586a86c6181SAlex Tomas 
587bba90743SEric Sandeen 	ext_debug("binsearch for %u:  ", block);
588a86c6181SAlex Tomas 
589a86c6181SAlex Tomas 	l = EXT_FIRST_EXTENT(eh) + 1;
590e9f410b1SDmitry Monakhov 	r = EXT_LAST_EXTENT(eh);
591a86c6181SAlex Tomas 
592a86c6181SAlex Tomas 	while (l <= r) {
593a86c6181SAlex Tomas 		m = l + (r - l) / 2;
594a86c6181SAlex Tomas 		if (block < le32_to_cpu(m->ee_block))
595a86c6181SAlex Tomas 			r = m - 1;
596a86c6181SAlex Tomas 		else
597a86c6181SAlex Tomas 			l = m + 1;
59826d535edSDmitry Monakhov 		ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ee_block),
59926d535edSDmitry Monakhov 				m, le32_to_cpu(m->ee_block),
60026d535edSDmitry Monakhov 				r, le32_to_cpu(r->ee_block));
601a86c6181SAlex Tomas 	}
602a86c6181SAlex Tomas 
603a86c6181SAlex Tomas 	path->p_ext = l - 1;
604553f9008SMingming 	ext_debug("  -> %d:%llu:[%d]%d ",
605a86c6181SAlex Tomas 			le32_to_cpu(path->p_ext->ee_block),
606f65e6fbaSAlex Tomas 			ext_pblock(path->p_ext),
607553f9008SMingming 			ext4_ext_is_uninitialized(path->p_ext),
608a2df2a63SAmit Arora 			ext4_ext_get_actual_len(path->p_ext));
609a86c6181SAlex Tomas 
610a86c6181SAlex Tomas #ifdef CHECK_BINSEARCH
611a86c6181SAlex Tomas 	{
612a86c6181SAlex Tomas 		struct ext4_extent *chex, *ex;
613a86c6181SAlex Tomas 		int k;
614a86c6181SAlex Tomas 
615a86c6181SAlex Tomas 		chex = ex = EXT_FIRST_EXTENT(eh);
616a86c6181SAlex Tomas 		for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ex++) {
617a86c6181SAlex Tomas 			BUG_ON(k && le32_to_cpu(ex->ee_block)
618a86c6181SAlex Tomas 					  <= le32_to_cpu(ex[-1].ee_block));
619a86c6181SAlex Tomas 			if (block < le32_to_cpu(ex->ee_block))
620a86c6181SAlex Tomas 				break;
621a86c6181SAlex Tomas 			chex = ex;
622a86c6181SAlex Tomas 		}
623a86c6181SAlex Tomas 		BUG_ON(chex != path->p_ext);
624a86c6181SAlex Tomas 	}
625a86c6181SAlex Tomas #endif
626a86c6181SAlex Tomas 
627a86c6181SAlex Tomas }
628a86c6181SAlex Tomas 
629a86c6181SAlex Tomas int ext4_ext_tree_init(handle_t *handle, struct inode *inode)
630a86c6181SAlex Tomas {
631a86c6181SAlex Tomas 	struct ext4_extent_header *eh;
632a86c6181SAlex Tomas 
633a86c6181SAlex Tomas 	eh = ext_inode_hdr(inode);
634a86c6181SAlex Tomas 	eh->eh_depth = 0;
635a86c6181SAlex Tomas 	eh->eh_entries = 0;
636a86c6181SAlex Tomas 	eh->eh_magic = EXT4_EXT_MAGIC;
63755ad63bfSTheodore Ts'o 	eh->eh_max = cpu_to_le16(ext4_ext_space_root(inode, 0));
638a86c6181SAlex Tomas 	ext4_mark_inode_dirty(handle, inode);
639a86c6181SAlex Tomas 	ext4_ext_invalidate_cache(inode);
640a86c6181SAlex Tomas 	return 0;
641a86c6181SAlex Tomas }
642a86c6181SAlex Tomas 
643a86c6181SAlex Tomas struct ext4_ext_path *
644725d26d3SAneesh Kumar K.V ext4_ext_find_extent(struct inode *inode, ext4_lblk_t block,
645725d26d3SAneesh Kumar K.V 					struct ext4_ext_path *path)
646a86c6181SAlex Tomas {
647a86c6181SAlex Tomas 	struct ext4_extent_header *eh;
648a86c6181SAlex Tomas 	struct buffer_head *bh;
649a86c6181SAlex Tomas 	short int depth, i, ppos = 0, alloc = 0;
650a86c6181SAlex Tomas 
651a86c6181SAlex Tomas 	eh = ext_inode_hdr(inode);
652c29c0ae7SAlex Tomas 	depth = ext_depth(inode);
653a86c6181SAlex Tomas 
654a86c6181SAlex Tomas 	/* account possible depth increase */
655a86c6181SAlex Tomas 	if (!path) {
6565d4958f9SAvantika Mathur 		path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 2),
657a86c6181SAlex Tomas 				GFP_NOFS);
658a86c6181SAlex Tomas 		if (!path)
659a86c6181SAlex Tomas 			return ERR_PTR(-ENOMEM);
660a86c6181SAlex Tomas 		alloc = 1;
661a86c6181SAlex Tomas 	}
662a86c6181SAlex Tomas 	path[0].p_hdr = eh;
6631973adcbSShen Feng 	path[0].p_bh = NULL;
664a86c6181SAlex Tomas 
665c29c0ae7SAlex Tomas 	i = depth;
666a86c6181SAlex Tomas 	/* walk through the tree */
667a86c6181SAlex Tomas 	while (i) {
6687a262f7cSAneesh Kumar K.V 		int need_to_validate = 0;
6697a262f7cSAneesh Kumar K.V 
670a86c6181SAlex Tomas 		ext_debug("depth %d: num %d, max %d\n",
671a86c6181SAlex Tomas 			  ppos, le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
672c29c0ae7SAlex Tomas 
673a86c6181SAlex Tomas 		ext4_ext_binsearch_idx(inode, path + ppos, block);
674f65e6fbaSAlex Tomas 		path[ppos].p_block = idx_pblock(path[ppos].p_idx);
675a86c6181SAlex Tomas 		path[ppos].p_depth = i;
676a86c6181SAlex Tomas 		path[ppos].p_ext = NULL;
677a86c6181SAlex Tomas 
6787a262f7cSAneesh Kumar K.V 		bh = sb_getblk(inode->i_sb, path[ppos].p_block);
6797a262f7cSAneesh Kumar K.V 		if (unlikely(!bh))
680a86c6181SAlex Tomas 			goto err;
6817a262f7cSAneesh Kumar K.V 		if (!bh_uptodate_or_lock(bh)) {
6827a262f7cSAneesh Kumar K.V 			if (bh_submit_read(bh) < 0) {
6837a262f7cSAneesh Kumar K.V 				put_bh(bh);
6847a262f7cSAneesh Kumar K.V 				goto err;
6857a262f7cSAneesh Kumar K.V 			}
6867a262f7cSAneesh Kumar K.V 			/* validate the extent entries */
6877a262f7cSAneesh Kumar K.V 			need_to_validate = 1;
6887a262f7cSAneesh Kumar K.V 		}
689a86c6181SAlex Tomas 		eh = ext_block_hdr(bh);
690a86c6181SAlex Tomas 		ppos++;
691a86c6181SAlex Tomas 		BUG_ON(ppos > depth);
692a86c6181SAlex Tomas 		path[ppos].p_bh = bh;
693a86c6181SAlex Tomas 		path[ppos].p_hdr = eh;
694a86c6181SAlex Tomas 		i--;
695a86c6181SAlex Tomas 
6967a262f7cSAneesh Kumar K.V 		if (need_to_validate && ext4_ext_check(inode, eh, i))
697a86c6181SAlex Tomas 			goto err;
698a86c6181SAlex Tomas 	}
699a86c6181SAlex Tomas 
700a86c6181SAlex Tomas 	path[ppos].p_depth = i;
701a86c6181SAlex Tomas 	path[ppos].p_ext = NULL;
702a86c6181SAlex Tomas 	path[ppos].p_idx = NULL;
703a86c6181SAlex Tomas 
704a86c6181SAlex Tomas 	/* find extent */
705a86c6181SAlex Tomas 	ext4_ext_binsearch(inode, path + ppos, block);
7061973adcbSShen Feng 	/* if not an empty leaf */
7071973adcbSShen Feng 	if (path[ppos].p_ext)
7081973adcbSShen Feng 		path[ppos].p_block = ext_pblock(path[ppos].p_ext);
709a86c6181SAlex Tomas 
710a86c6181SAlex Tomas 	ext4_ext_show_path(inode, path);
711a86c6181SAlex Tomas 
712a86c6181SAlex Tomas 	return path;
713a86c6181SAlex Tomas 
714a86c6181SAlex Tomas err:
715a86c6181SAlex Tomas 	ext4_ext_drop_refs(path);
716a86c6181SAlex Tomas 	if (alloc)
717a86c6181SAlex Tomas 		kfree(path);
718a86c6181SAlex Tomas 	return ERR_PTR(-EIO);
719a86c6181SAlex Tomas }
720a86c6181SAlex Tomas 
721a86c6181SAlex Tomas /*
722d0d856e8SRandy Dunlap  * ext4_ext_insert_index:
723d0d856e8SRandy Dunlap  * insert new index [@logical;@ptr] into the block at @curp;
724d0d856e8SRandy Dunlap  * check where to insert: before @curp or after @curp
725a86c6181SAlex Tomas  */
7260031462bSMingming Cao int ext4_ext_insert_index(handle_t *handle, struct inode *inode,
727a86c6181SAlex Tomas 				struct ext4_ext_path *curp,
728f65e6fbaSAlex Tomas 				int logical, ext4_fsblk_t ptr)
729a86c6181SAlex Tomas {
730a86c6181SAlex Tomas 	struct ext4_extent_idx *ix;
731a86c6181SAlex Tomas 	int len, err;
732a86c6181SAlex Tomas 
7337e028976SAvantika Mathur 	err = ext4_ext_get_access(handle, inode, curp);
7347e028976SAvantika Mathur 	if (err)
735a86c6181SAlex Tomas 		return err;
736a86c6181SAlex Tomas 
737a86c6181SAlex Tomas 	BUG_ON(logical == le32_to_cpu(curp->p_idx->ei_block));
738a86c6181SAlex Tomas 	len = EXT_MAX_INDEX(curp->p_hdr) - curp->p_idx;
739a86c6181SAlex Tomas 	if (logical > le32_to_cpu(curp->p_idx->ei_block)) {
740a86c6181SAlex Tomas 		/* insert after */
741a86c6181SAlex Tomas 		if (curp->p_idx != EXT_LAST_INDEX(curp->p_hdr)) {
742a86c6181SAlex Tomas 			len = (len - 1) * sizeof(struct ext4_extent_idx);
743a86c6181SAlex Tomas 			len = len < 0 ? 0 : len;
74426d535edSDmitry Monakhov 			ext_debug("insert new index %d after: %llu. "
745a86c6181SAlex Tomas 					"move %d from 0x%p to 0x%p\n",
746a86c6181SAlex Tomas 					logical, ptr, len,
747a86c6181SAlex Tomas 					(curp->p_idx + 1), (curp->p_idx + 2));
748a86c6181SAlex Tomas 			memmove(curp->p_idx + 2, curp->p_idx + 1, len);
749a86c6181SAlex Tomas 		}
750a86c6181SAlex Tomas 		ix = curp->p_idx + 1;
751a86c6181SAlex Tomas 	} else {
752a86c6181SAlex Tomas 		/* insert before */
753a86c6181SAlex Tomas 		len = len * sizeof(struct ext4_extent_idx);
754a86c6181SAlex Tomas 		len = len < 0 ? 0 : len;
75526d535edSDmitry Monakhov 		ext_debug("insert new index %d before: %llu. "
756a86c6181SAlex Tomas 				"move %d from 0x%p to 0x%p\n",
757a86c6181SAlex Tomas 				logical, ptr, len,
758a86c6181SAlex Tomas 				curp->p_idx, (curp->p_idx + 1));
759a86c6181SAlex Tomas 		memmove(curp->p_idx + 1, curp->p_idx, len);
760a86c6181SAlex Tomas 		ix = curp->p_idx;
761a86c6181SAlex Tomas 	}
762a86c6181SAlex Tomas 
763a86c6181SAlex Tomas 	ix->ei_block = cpu_to_le32(logical);
764f65e6fbaSAlex Tomas 	ext4_idx_store_pblock(ix, ptr);
765e8546d06SMarcin Slusarz 	le16_add_cpu(&curp->p_hdr->eh_entries, 1);
766a86c6181SAlex Tomas 
767a86c6181SAlex Tomas 	BUG_ON(le16_to_cpu(curp->p_hdr->eh_entries)
768a86c6181SAlex Tomas 			     > le16_to_cpu(curp->p_hdr->eh_max));
769a86c6181SAlex Tomas 	BUG_ON(ix > EXT_LAST_INDEX(curp->p_hdr));
770a86c6181SAlex Tomas 
771a86c6181SAlex Tomas 	err = ext4_ext_dirty(handle, inode, curp);
772a86c6181SAlex Tomas 	ext4_std_error(inode->i_sb, err);
773a86c6181SAlex Tomas 
774a86c6181SAlex Tomas 	return err;
775a86c6181SAlex Tomas }
776a86c6181SAlex Tomas 
777a86c6181SAlex Tomas /*
778d0d856e8SRandy Dunlap  * ext4_ext_split:
779d0d856e8SRandy Dunlap  * inserts new subtree into the path, using free index entry
780d0d856e8SRandy Dunlap  * at depth @at:
781a86c6181SAlex Tomas  * - allocates all needed blocks (new leaf and all intermediate index blocks)
782a86c6181SAlex Tomas  * - makes decision where to split
783d0d856e8SRandy Dunlap  * - moves remaining extents and index entries (right to the split point)
784a86c6181SAlex Tomas  *   into the newly allocated blocks
785d0d856e8SRandy Dunlap  * - initializes subtree
786a86c6181SAlex Tomas  */
787a86c6181SAlex Tomas static int ext4_ext_split(handle_t *handle, struct inode *inode,
788a86c6181SAlex Tomas 				struct ext4_ext_path *path,
789a86c6181SAlex Tomas 				struct ext4_extent *newext, int at)
790a86c6181SAlex Tomas {
791a86c6181SAlex Tomas 	struct buffer_head *bh = NULL;
792a86c6181SAlex Tomas 	int depth = ext_depth(inode);
793a86c6181SAlex Tomas 	struct ext4_extent_header *neh;
794a86c6181SAlex Tomas 	struct ext4_extent_idx *fidx;
795a86c6181SAlex Tomas 	struct ext4_extent *ex;
796a86c6181SAlex Tomas 	int i = at, k, m, a;
797f65e6fbaSAlex Tomas 	ext4_fsblk_t newblock, oldblock;
798a86c6181SAlex Tomas 	__le32 border;
799f65e6fbaSAlex Tomas 	ext4_fsblk_t *ablocks = NULL; /* array of allocated blocks */
800a86c6181SAlex Tomas 	int err = 0;
801a86c6181SAlex Tomas 
802a86c6181SAlex Tomas 	/* make decision: where to split? */
803d0d856e8SRandy Dunlap 	/* FIXME: now decision is simplest: at current extent */
804a86c6181SAlex Tomas 
805d0d856e8SRandy Dunlap 	/* if current leaf will be split, then we should use
806a86c6181SAlex Tomas 	 * border from split point */
807a86c6181SAlex Tomas 	BUG_ON(path[depth].p_ext > EXT_MAX_EXTENT(path[depth].p_hdr));
808a86c6181SAlex Tomas 	if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr)) {
809a86c6181SAlex Tomas 		border = path[depth].p_ext[1].ee_block;
810d0d856e8SRandy Dunlap 		ext_debug("leaf will be split."
811a86c6181SAlex Tomas 				" next leaf starts at %d\n",
812a86c6181SAlex Tomas 				  le32_to_cpu(border));
813a86c6181SAlex Tomas 	} else {
814a86c6181SAlex Tomas 		border = newext->ee_block;
815a86c6181SAlex Tomas 		ext_debug("leaf will be added."
816a86c6181SAlex Tomas 				" next leaf starts at %d\n",
817a86c6181SAlex Tomas 				le32_to_cpu(border));
818a86c6181SAlex Tomas 	}
819a86c6181SAlex Tomas 
820a86c6181SAlex Tomas 	/*
821d0d856e8SRandy Dunlap 	 * If error occurs, then we break processing
822d0d856e8SRandy Dunlap 	 * and mark filesystem read-only. index won't
823a86c6181SAlex Tomas 	 * be inserted and tree will be in consistent
824d0d856e8SRandy Dunlap 	 * state. Next mount will repair buffers too.
825a86c6181SAlex Tomas 	 */
826a86c6181SAlex Tomas 
827a86c6181SAlex Tomas 	/*
828d0d856e8SRandy Dunlap 	 * Get array to track all allocated blocks.
829d0d856e8SRandy Dunlap 	 * We need this to handle errors and free blocks
830d0d856e8SRandy Dunlap 	 * upon them.
831a86c6181SAlex Tomas 	 */
8325d4958f9SAvantika Mathur 	ablocks = kzalloc(sizeof(ext4_fsblk_t) * depth, GFP_NOFS);
833a86c6181SAlex Tomas 	if (!ablocks)
834a86c6181SAlex Tomas 		return -ENOMEM;
835a86c6181SAlex Tomas 
836a86c6181SAlex Tomas 	/* allocate all needed blocks */
837a86c6181SAlex Tomas 	ext_debug("allocate %d blocks for indexes/leaf\n", depth - at);
838a86c6181SAlex Tomas 	for (a = 0; a < depth - at; a++) {
839654b4908SAneesh Kumar K.V 		newblock = ext4_ext_new_meta_block(handle, inode, path,
840654b4908SAneesh Kumar K.V 						   newext, &err);
841a86c6181SAlex Tomas 		if (newblock == 0)
842a86c6181SAlex Tomas 			goto cleanup;
843a86c6181SAlex Tomas 		ablocks[a] = newblock;
844a86c6181SAlex Tomas 	}
845a86c6181SAlex Tomas 
846a86c6181SAlex Tomas 	/* initialize new leaf */
847a86c6181SAlex Tomas 	newblock = ablocks[--a];
848a86c6181SAlex Tomas 	BUG_ON(newblock == 0);
849a86c6181SAlex Tomas 	bh = sb_getblk(inode->i_sb, newblock);
850a86c6181SAlex Tomas 	if (!bh) {
851a86c6181SAlex Tomas 		err = -EIO;
852a86c6181SAlex Tomas 		goto cleanup;
853a86c6181SAlex Tomas 	}
854a86c6181SAlex Tomas 	lock_buffer(bh);
855a86c6181SAlex Tomas 
8567e028976SAvantika Mathur 	err = ext4_journal_get_create_access(handle, bh);
8577e028976SAvantika Mathur 	if (err)
858a86c6181SAlex Tomas 		goto cleanup;
859a86c6181SAlex Tomas 
860a86c6181SAlex Tomas 	neh = ext_block_hdr(bh);
861a86c6181SAlex Tomas 	neh->eh_entries = 0;
86255ad63bfSTheodore Ts'o 	neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
863a86c6181SAlex Tomas 	neh->eh_magic = EXT4_EXT_MAGIC;
864a86c6181SAlex Tomas 	neh->eh_depth = 0;
865a86c6181SAlex Tomas 	ex = EXT_FIRST_EXTENT(neh);
866a86c6181SAlex Tomas 
867d0d856e8SRandy Dunlap 	/* move remainder of path[depth] to the new leaf */
868a86c6181SAlex Tomas 	BUG_ON(path[depth].p_hdr->eh_entries != path[depth].p_hdr->eh_max);
869a86c6181SAlex Tomas 	/* start copy from next extent */
870a86c6181SAlex Tomas 	/* TODO: we could do it by single memmove */
871a86c6181SAlex Tomas 	m = 0;
872a86c6181SAlex Tomas 	path[depth].p_ext++;
873a86c6181SAlex Tomas 	while (path[depth].p_ext <=
874a86c6181SAlex Tomas 			EXT_MAX_EXTENT(path[depth].p_hdr)) {
875553f9008SMingming 		ext_debug("move %d:%llu:[%d]%d in new leaf %llu\n",
876a86c6181SAlex Tomas 				le32_to_cpu(path[depth].p_ext->ee_block),
877f65e6fbaSAlex Tomas 				ext_pblock(path[depth].p_ext),
878553f9008SMingming 				ext4_ext_is_uninitialized(path[depth].p_ext),
879a2df2a63SAmit Arora 				ext4_ext_get_actual_len(path[depth].p_ext),
880a86c6181SAlex Tomas 				newblock);
881a86c6181SAlex Tomas 		/*memmove(ex++, path[depth].p_ext++,
882a86c6181SAlex Tomas 				sizeof(struct ext4_extent));
883a86c6181SAlex Tomas 		neh->eh_entries++;*/
884a86c6181SAlex Tomas 		path[depth].p_ext++;
885a86c6181SAlex Tomas 		m++;
886a86c6181SAlex Tomas 	}
887a86c6181SAlex Tomas 	if (m) {
888a86c6181SAlex Tomas 		memmove(ex, path[depth].p_ext-m, sizeof(struct ext4_extent)*m);
889e8546d06SMarcin Slusarz 		le16_add_cpu(&neh->eh_entries, m);
890a86c6181SAlex Tomas 	}
891a86c6181SAlex Tomas 
892a86c6181SAlex Tomas 	set_buffer_uptodate(bh);
893a86c6181SAlex Tomas 	unlock_buffer(bh);
894a86c6181SAlex Tomas 
8950390131bSFrank Mayhar 	err = ext4_handle_dirty_metadata(handle, inode, bh);
8967e028976SAvantika Mathur 	if (err)
897a86c6181SAlex Tomas 		goto cleanup;
898a86c6181SAlex Tomas 	brelse(bh);
899a86c6181SAlex Tomas 	bh = NULL;
900a86c6181SAlex Tomas 
901a86c6181SAlex Tomas 	/* correct old leaf */
902a86c6181SAlex Tomas 	if (m) {
9037e028976SAvantika Mathur 		err = ext4_ext_get_access(handle, inode, path + depth);
9047e028976SAvantika Mathur 		if (err)
905a86c6181SAlex Tomas 			goto cleanup;
906e8546d06SMarcin Slusarz 		le16_add_cpu(&path[depth].p_hdr->eh_entries, -m);
9077e028976SAvantika Mathur 		err = ext4_ext_dirty(handle, inode, path + depth);
9087e028976SAvantika Mathur 		if (err)
909a86c6181SAlex Tomas 			goto cleanup;
910a86c6181SAlex Tomas 
911a86c6181SAlex Tomas 	}
912a86c6181SAlex Tomas 
913a86c6181SAlex Tomas 	/* create intermediate indexes */
914a86c6181SAlex Tomas 	k = depth - at - 1;
915a86c6181SAlex Tomas 	BUG_ON(k < 0);
916a86c6181SAlex Tomas 	if (k)
917a86c6181SAlex Tomas 		ext_debug("create %d intermediate indices\n", k);
918a86c6181SAlex Tomas 	/* insert new index into current index block */
919a86c6181SAlex Tomas 	/* current depth stored in i var */
920a86c6181SAlex Tomas 	i = depth - 1;
921a86c6181SAlex Tomas 	while (k--) {
922a86c6181SAlex Tomas 		oldblock = newblock;
923a86c6181SAlex Tomas 		newblock = ablocks[--a];
924bba90743SEric Sandeen 		bh = sb_getblk(inode->i_sb, newblock);
925a86c6181SAlex Tomas 		if (!bh) {
926a86c6181SAlex Tomas 			err = -EIO;
927a86c6181SAlex Tomas 			goto cleanup;
928a86c6181SAlex Tomas 		}
929a86c6181SAlex Tomas 		lock_buffer(bh);
930a86c6181SAlex Tomas 
9317e028976SAvantika Mathur 		err = ext4_journal_get_create_access(handle, bh);
9327e028976SAvantika Mathur 		if (err)
933a86c6181SAlex Tomas 			goto cleanup;
934a86c6181SAlex Tomas 
935a86c6181SAlex Tomas 		neh = ext_block_hdr(bh);
936a86c6181SAlex Tomas 		neh->eh_entries = cpu_to_le16(1);
937a86c6181SAlex Tomas 		neh->eh_magic = EXT4_EXT_MAGIC;
93855ad63bfSTheodore Ts'o 		neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
939a86c6181SAlex Tomas 		neh->eh_depth = cpu_to_le16(depth - i);
940a86c6181SAlex Tomas 		fidx = EXT_FIRST_INDEX(neh);
941a86c6181SAlex Tomas 		fidx->ei_block = border;
942f65e6fbaSAlex Tomas 		ext4_idx_store_pblock(fidx, oldblock);
943a86c6181SAlex Tomas 
944bba90743SEric Sandeen 		ext_debug("int.index at %d (block %llu): %u -> %llu\n",
945bba90743SEric Sandeen 				i, newblock, le32_to_cpu(border), oldblock);
946a86c6181SAlex Tomas 		/* copy indexes */
947a86c6181SAlex Tomas 		m = 0;
948a86c6181SAlex Tomas 		path[i].p_idx++;
949a86c6181SAlex Tomas 
950a86c6181SAlex Tomas 		ext_debug("cur 0x%p, last 0x%p\n", path[i].p_idx,
951a86c6181SAlex Tomas 				EXT_MAX_INDEX(path[i].p_hdr));
952a86c6181SAlex Tomas 		BUG_ON(EXT_MAX_INDEX(path[i].p_hdr) !=
953a86c6181SAlex Tomas 				EXT_LAST_INDEX(path[i].p_hdr));
954a86c6181SAlex Tomas 		while (path[i].p_idx <= EXT_MAX_INDEX(path[i].p_hdr)) {
95526d535edSDmitry Monakhov 			ext_debug("%d: move %d:%llu in new index %llu\n", i,
956a86c6181SAlex Tomas 					le32_to_cpu(path[i].p_idx->ei_block),
957f65e6fbaSAlex Tomas 					idx_pblock(path[i].p_idx),
958a86c6181SAlex Tomas 					newblock);
959a86c6181SAlex Tomas 			/*memmove(++fidx, path[i].p_idx++,
960a86c6181SAlex Tomas 					sizeof(struct ext4_extent_idx));
961a86c6181SAlex Tomas 			neh->eh_entries++;
962a86c6181SAlex Tomas 			BUG_ON(neh->eh_entries > neh->eh_max);*/
963a86c6181SAlex Tomas 			path[i].p_idx++;
964a86c6181SAlex Tomas 			m++;
965a86c6181SAlex Tomas 		}
966a86c6181SAlex Tomas 		if (m) {
967a86c6181SAlex Tomas 			memmove(++fidx, path[i].p_idx - m,
968a86c6181SAlex Tomas 				sizeof(struct ext4_extent_idx) * m);
969e8546d06SMarcin Slusarz 			le16_add_cpu(&neh->eh_entries, m);
970a86c6181SAlex Tomas 		}
971a86c6181SAlex Tomas 		set_buffer_uptodate(bh);
972a86c6181SAlex Tomas 		unlock_buffer(bh);
973a86c6181SAlex Tomas 
9740390131bSFrank Mayhar 		err = ext4_handle_dirty_metadata(handle, inode, bh);
9757e028976SAvantika Mathur 		if (err)
976a86c6181SAlex Tomas 			goto cleanup;
977a86c6181SAlex Tomas 		brelse(bh);
978a86c6181SAlex Tomas 		bh = NULL;
979a86c6181SAlex Tomas 
980a86c6181SAlex Tomas 		/* correct old index */
981a86c6181SAlex Tomas 		if (m) {
982a86c6181SAlex Tomas 			err = ext4_ext_get_access(handle, inode, path + i);
983a86c6181SAlex Tomas 			if (err)
984a86c6181SAlex Tomas 				goto cleanup;
985e8546d06SMarcin Slusarz 			le16_add_cpu(&path[i].p_hdr->eh_entries, -m);
986a86c6181SAlex Tomas 			err = ext4_ext_dirty(handle, inode, path + i);
987a86c6181SAlex Tomas 			if (err)
988a86c6181SAlex Tomas 				goto cleanup;
989a86c6181SAlex Tomas 		}
990a86c6181SAlex Tomas 
991a86c6181SAlex Tomas 		i--;
992a86c6181SAlex Tomas 	}
993a86c6181SAlex Tomas 
994a86c6181SAlex Tomas 	/* insert new index */
995a86c6181SAlex Tomas 	err = ext4_ext_insert_index(handle, inode, path + at,
996a86c6181SAlex Tomas 				    le32_to_cpu(border), newblock);
997a86c6181SAlex Tomas 
998a86c6181SAlex Tomas cleanup:
999a86c6181SAlex Tomas 	if (bh) {
1000a86c6181SAlex Tomas 		if (buffer_locked(bh))
1001a86c6181SAlex Tomas 			unlock_buffer(bh);
1002a86c6181SAlex Tomas 		brelse(bh);
1003a86c6181SAlex Tomas 	}
1004a86c6181SAlex Tomas 
1005a86c6181SAlex Tomas 	if (err) {
1006a86c6181SAlex Tomas 		/* free all allocated blocks in error case */
1007a86c6181SAlex Tomas 		for (i = 0; i < depth; i++) {
1008a86c6181SAlex Tomas 			if (!ablocks[i])
1009a86c6181SAlex Tomas 				continue;
1010*e6362609STheodore Ts'o 			ext4_free_blocks(handle, inode, 0, ablocks[i], 1,
1011*e6362609STheodore Ts'o 					 EXT4_FREE_BLOCKS_METADATA);
1012a86c6181SAlex Tomas 		}
1013a86c6181SAlex Tomas 	}
1014a86c6181SAlex Tomas 	kfree(ablocks);
1015a86c6181SAlex Tomas 
1016a86c6181SAlex Tomas 	return err;
1017a86c6181SAlex Tomas }
1018a86c6181SAlex Tomas 
1019a86c6181SAlex Tomas /*
1020d0d856e8SRandy Dunlap  * ext4_ext_grow_indepth:
1021d0d856e8SRandy Dunlap  * implements tree growing procedure:
1022a86c6181SAlex Tomas  * - allocates new block
1023a86c6181SAlex Tomas  * - moves top-level data (index block or leaf) into the new block
1024d0d856e8SRandy Dunlap  * - initializes new top-level, creating index that points to the
1025a86c6181SAlex Tomas  *   just created block
1026a86c6181SAlex Tomas  */
1027a86c6181SAlex Tomas static int ext4_ext_grow_indepth(handle_t *handle, struct inode *inode,
1028a86c6181SAlex Tomas 					struct ext4_ext_path *path,
1029a86c6181SAlex Tomas 					struct ext4_extent *newext)
1030a86c6181SAlex Tomas {
1031a86c6181SAlex Tomas 	struct ext4_ext_path *curp = path;
1032a86c6181SAlex Tomas 	struct ext4_extent_header *neh;
1033a86c6181SAlex Tomas 	struct ext4_extent_idx *fidx;
1034a86c6181SAlex Tomas 	struct buffer_head *bh;
1035f65e6fbaSAlex Tomas 	ext4_fsblk_t newblock;
1036a86c6181SAlex Tomas 	int err = 0;
1037a86c6181SAlex Tomas 
1038654b4908SAneesh Kumar K.V 	newblock = ext4_ext_new_meta_block(handle, inode, path, newext, &err);
1039a86c6181SAlex Tomas 	if (newblock == 0)
1040a86c6181SAlex Tomas 		return err;
1041a86c6181SAlex Tomas 
1042a86c6181SAlex Tomas 	bh = sb_getblk(inode->i_sb, newblock);
1043a86c6181SAlex Tomas 	if (!bh) {
1044a86c6181SAlex Tomas 		err = -EIO;
1045a86c6181SAlex Tomas 		ext4_std_error(inode->i_sb, err);
1046a86c6181SAlex Tomas 		return err;
1047a86c6181SAlex Tomas 	}
1048a86c6181SAlex Tomas 	lock_buffer(bh);
1049a86c6181SAlex Tomas 
10507e028976SAvantika Mathur 	err = ext4_journal_get_create_access(handle, bh);
10517e028976SAvantika Mathur 	if (err) {
1052a86c6181SAlex Tomas 		unlock_buffer(bh);
1053a86c6181SAlex Tomas 		goto out;
1054a86c6181SAlex Tomas 	}
1055a86c6181SAlex Tomas 
1056a86c6181SAlex Tomas 	/* move top-level index/leaf into new block */
1057a86c6181SAlex Tomas 	memmove(bh->b_data, curp->p_hdr, sizeof(EXT4_I(inode)->i_data));
1058a86c6181SAlex Tomas 
1059a86c6181SAlex Tomas 	/* set size of new block */
1060a86c6181SAlex Tomas 	neh = ext_block_hdr(bh);
1061a86c6181SAlex Tomas 	/* old root could have indexes or leaves
1062a86c6181SAlex Tomas 	 * so calculate e_max right way */
1063a86c6181SAlex Tomas 	if (ext_depth(inode))
106455ad63bfSTheodore Ts'o 		neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
1065a86c6181SAlex Tomas 	else
106655ad63bfSTheodore Ts'o 		neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
1067a86c6181SAlex Tomas 	neh->eh_magic = EXT4_EXT_MAGIC;
1068a86c6181SAlex Tomas 	set_buffer_uptodate(bh);
1069a86c6181SAlex Tomas 	unlock_buffer(bh);
1070a86c6181SAlex Tomas 
10710390131bSFrank Mayhar 	err = ext4_handle_dirty_metadata(handle, inode, bh);
10727e028976SAvantika Mathur 	if (err)
1073a86c6181SAlex Tomas 		goto out;
1074a86c6181SAlex Tomas 
1075a86c6181SAlex Tomas 	/* create index in new top-level index: num,max,pointer */
10767e028976SAvantika Mathur 	err = ext4_ext_get_access(handle, inode, curp);
10777e028976SAvantika Mathur 	if (err)
1078a86c6181SAlex Tomas 		goto out;
1079a86c6181SAlex Tomas 
1080a86c6181SAlex Tomas 	curp->p_hdr->eh_magic = EXT4_EXT_MAGIC;
108155ad63bfSTheodore Ts'o 	curp->p_hdr->eh_max = cpu_to_le16(ext4_ext_space_root_idx(inode, 0));
1082a86c6181SAlex Tomas 	curp->p_hdr->eh_entries = cpu_to_le16(1);
1083a86c6181SAlex Tomas 	curp->p_idx = EXT_FIRST_INDEX(curp->p_hdr);
1084e9f410b1SDmitry Monakhov 
1085e9f410b1SDmitry Monakhov 	if (path[0].p_hdr->eh_depth)
1086e9f410b1SDmitry Monakhov 		curp->p_idx->ei_block =
1087e9f410b1SDmitry Monakhov 			EXT_FIRST_INDEX(path[0].p_hdr)->ei_block;
1088e9f410b1SDmitry Monakhov 	else
1089e9f410b1SDmitry Monakhov 		curp->p_idx->ei_block =
1090e9f410b1SDmitry Monakhov 			EXT_FIRST_EXTENT(path[0].p_hdr)->ee_block;
1091f65e6fbaSAlex Tomas 	ext4_idx_store_pblock(curp->p_idx, newblock);
1092a86c6181SAlex Tomas 
1093a86c6181SAlex Tomas 	neh = ext_inode_hdr(inode);
1094a86c6181SAlex Tomas 	fidx = EXT_FIRST_INDEX(neh);
10952ae02107SMingming Cao 	ext_debug("new root: num %d(%d), lblock %d, ptr %llu\n",
1096a86c6181SAlex Tomas 		  le16_to_cpu(neh->eh_entries), le16_to_cpu(neh->eh_max),
1097f65e6fbaSAlex Tomas 		  le32_to_cpu(fidx->ei_block), idx_pblock(fidx));
1098a86c6181SAlex Tomas 
1099a86c6181SAlex Tomas 	neh->eh_depth = cpu_to_le16(path->p_depth + 1);
1100a86c6181SAlex Tomas 	err = ext4_ext_dirty(handle, inode, curp);
1101a86c6181SAlex Tomas out:
1102a86c6181SAlex Tomas 	brelse(bh);
1103a86c6181SAlex Tomas 
1104a86c6181SAlex Tomas 	return err;
1105a86c6181SAlex Tomas }
1106a86c6181SAlex Tomas 
1107a86c6181SAlex Tomas /*
1108d0d856e8SRandy Dunlap  * ext4_ext_create_new_leaf:
1109d0d856e8SRandy Dunlap  * finds empty index and adds new leaf.
1110d0d856e8SRandy Dunlap  * if no free index is found, then it requests in-depth growing.
1111a86c6181SAlex Tomas  */
1112a86c6181SAlex Tomas static int ext4_ext_create_new_leaf(handle_t *handle, struct inode *inode,
1113a86c6181SAlex Tomas 					struct ext4_ext_path *path,
1114a86c6181SAlex Tomas 					struct ext4_extent *newext)
1115a86c6181SAlex Tomas {
1116a86c6181SAlex Tomas 	struct ext4_ext_path *curp;
1117a86c6181SAlex Tomas 	int depth, i, err = 0;
1118a86c6181SAlex Tomas 
1119a86c6181SAlex Tomas repeat:
1120a86c6181SAlex Tomas 	i = depth = ext_depth(inode);
1121a86c6181SAlex Tomas 
1122a86c6181SAlex Tomas 	/* walk up to the tree and look for free index entry */
1123a86c6181SAlex Tomas 	curp = path + depth;
1124a86c6181SAlex Tomas 	while (i > 0 && !EXT_HAS_FREE_INDEX(curp)) {
1125a86c6181SAlex Tomas 		i--;
1126a86c6181SAlex Tomas 		curp--;
1127a86c6181SAlex Tomas 	}
1128a86c6181SAlex Tomas 
1129d0d856e8SRandy Dunlap 	/* we use already allocated block for index block,
1130d0d856e8SRandy Dunlap 	 * so subsequent data blocks should be contiguous */
1131a86c6181SAlex Tomas 	if (EXT_HAS_FREE_INDEX(curp)) {
1132a86c6181SAlex Tomas 		/* if we found index with free entry, then use that
1133a86c6181SAlex Tomas 		 * entry: create all needed subtree and add new leaf */
1134a86c6181SAlex Tomas 		err = ext4_ext_split(handle, inode, path, newext, i);
1135787e0981SShen Feng 		if (err)
1136787e0981SShen Feng 			goto out;
1137a86c6181SAlex Tomas 
1138a86c6181SAlex Tomas 		/* refill path */
1139a86c6181SAlex Tomas 		ext4_ext_drop_refs(path);
1140a86c6181SAlex Tomas 		path = ext4_ext_find_extent(inode,
1141725d26d3SAneesh Kumar K.V 				    (ext4_lblk_t)le32_to_cpu(newext->ee_block),
1142a86c6181SAlex Tomas 				    path);
1143a86c6181SAlex Tomas 		if (IS_ERR(path))
1144a86c6181SAlex Tomas 			err = PTR_ERR(path);
1145a86c6181SAlex Tomas 	} else {
1146a86c6181SAlex Tomas 		/* tree is full, time to grow in depth */
1147a86c6181SAlex Tomas 		err = ext4_ext_grow_indepth(handle, inode, path, newext);
1148a86c6181SAlex Tomas 		if (err)
1149a86c6181SAlex Tomas 			goto out;
1150a86c6181SAlex Tomas 
1151a86c6181SAlex Tomas 		/* refill path */
1152a86c6181SAlex Tomas 		ext4_ext_drop_refs(path);
1153a86c6181SAlex Tomas 		path = ext4_ext_find_extent(inode,
1154725d26d3SAneesh Kumar K.V 				   (ext4_lblk_t)le32_to_cpu(newext->ee_block),
1155a86c6181SAlex Tomas 				    path);
1156a86c6181SAlex Tomas 		if (IS_ERR(path)) {
1157a86c6181SAlex Tomas 			err = PTR_ERR(path);
1158a86c6181SAlex Tomas 			goto out;
1159a86c6181SAlex Tomas 		}
1160a86c6181SAlex Tomas 
1161a86c6181SAlex Tomas 		/*
1162d0d856e8SRandy Dunlap 		 * only first (depth 0 -> 1) produces free space;
1163d0d856e8SRandy Dunlap 		 * in all other cases we have to split the grown tree
1164a86c6181SAlex Tomas 		 */
1165a86c6181SAlex Tomas 		depth = ext_depth(inode);
1166a86c6181SAlex Tomas 		if (path[depth].p_hdr->eh_entries == path[depth].p_hdr->eh_max) {
1167d0d856e8SRandy Dunlap 			/* now we need to split */
1168a86c6181SAlex Tomas 			goto repeat;
1169a86c6181SAlex Tomas 		}
1170a86c6181SAlex Tomas 	}
1171a86c6181SAlex Tomas 
1172a86c6181SAlex Tomas out:
1173a86c6181SAlex Tomas 	return err;
1174a86c6181SAlex Tomas }
1175a86c6181SAlex Tomas 
1176a86c6181SAlex Tomas /*
11771988b51eSAlex Tomas  * search the closest allocated block to the left for *logical
11781988b51eSAlex Tomas  * and returns it at @logical + it's physical address at @phys
11791988b51eSAlex Tomas  * if *logical is the smallest allocated block, the function
11801988b51eSAlex Tomas  * returns 0 at @phys
11811988b51eSAlex Tomas  * return value contains 0 (success) or error code
11821988b51eSAlex Tomas  */
11831988b51eSAlex Tomas int
11841988b51eSAlex Tomas ext4_ext_search_left(struct inode *inode, struct ext4_ext_path *path,
11851988b51eSAlex Tomas 			ext4_lblk_t *logical, ext4_fsblk_t *phys)
11861988b51eSAlex Tomas {
11871988b51eSAlex Tomas 	struct ext4_extent_idx *ix;
11881988b51eSAlex Tomas 	struct ext4_extent *ex;
1189b939e376SAneesh Kumar K.V 	int depth, ee_len;
11901988b51eSAlex Tomas 
11911988b51eSAlex Tomas 	BUG_ON(path == NULL);
11921988b51eSAlex Tomas 	depth = path->p_depth;
11931988b51eSAlex Tomas 	*phys = 0;
11941988b51eSAlex Tomas 
11951988b51eSAlex Tomas 	if (depth == 0 && path->p_ext == NULL)
11961988b51eSAlex Tomas 		return 0;
11971988b51eSAlex Tomas 
11981988b51eSAlex Tomas 	/* usually extent in the path covers blocks smaller
11991988b51eSAlex Tomas 	 * then *logical, but it can be that extent is the
12001988b51eSAlex Tomas 	 * first one in the file */
12011988b51eSAlex Tomas 
12021988b51eSAlex Tomas 	ex = path[depth].p_ext;
1203b939e376SAneesh Kumar K.V 	ee_len = ext4_ext_get_actual_len(ex);
12041988b51eSAlex Tomas 	if (*logical < le32_to_cpu(ex->ee_block)) {
12051988b51eSAlex Tomas 		BUG_ON(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex);
12061988b51eSAlex Tomas 		while (--depth >= 0) {
12071988b51eSAlex Tomas 			ix = path[depth].p_idx;
12081988b51eSAlex Tomas 			BUG_ON(ix != EXT_FIRST_INDEX(path[depth].p_hdr));
12091988b51eSAlex Tomas 		}
12101988b51eSAlex Tomas 		return 0;
12111988b51eSAlex Tomas 	}
12121988b51eSAlex Tomas 
1213b939e376SAneesh Kumar K.V 	BUG_ON(*logical < (le32_to_cpu(ex->ee_block) + ee_len));
12141988b51eSAlex Tomas 
1215b939e376SAneesh Kumar K.V 	*logical = le32_to_cpu(ex->ee_block) + ee_len - 1;
1216b939e376SAneesh Kumar K.V 	*phys = ext_pblock(ex) + ee_len - 1;
12171988b51eSAlex Tomas 	return 0;
12181988b51eSAlex Tomas }
12191988b51eSAlex Tomas 
12201988b51eSAlex Tomas /*
12211988b51eSAlex Tomas  * search the closest allocated block to the right for *logical
12221988b51eSAlex Tomas  * and returns it at @logical + it's physical address at @phys
12231988b51eSAlex Tomas  * if *logical is the smallest allocated block, the function
12241988b51eSAlex Tomas  * returns 0 at @phys
12251988b51eSAlex Tomas  * return value contains 0 (success) or error code
12261988b51eSAlex Tomas  */
12271988b51eSAlex Tomas int
12281988b51eSAlex Tomas ext4_ext_search_right(struct inode *inode, struct ext4_ext_path *path,
12291988b51eSAlex Tomas 			ext4_lblk_t *logical, ext4_fsblk_t *phys)
12301988b51eSAlex Tomas {
12311988b51eSAlex Tomas 	struct buffer_head *bh = NULL;
12321988b51eSAlex Tomas 	struct ext4_extent_header *eh;
12331988b51eSAlex Tomas 	struct ext4_extent_idx *ix;
12341988b51eSAlex Tomas 	struct ext4_extent *ex;
12351988b51eSAlex Tomas 	ext4_fsblk_t block;
1236395a87bfSEric Sandeen 	int depth;	/* Note, NOT eh_depth; depth from top of tree */
1237395a87bfSEric Sandeen 	int ee_len;
12381988b51eSAlex Tomas 
12391988b51eSAlex Tomas 	BUG_ON(path == NULL);
12401988b51eSAlex Tomas 	depth = path->p_depth;
12411988b51eSAlex Tomas 	*phys = 0;
12421988b51eSAlex Tomas 
12431988b51eSAlex Tomas 	if (depth == 0 && path->p_ext == NULL)
12441988b51eSAlex Tomas 		return 0;
12451988b51eSAlex Tomas 
12461988b51eSAlex Tomas 	/* usually extent in the path covers blocks smaller
12471988b51eSAlex Tomas 	 * then *logical, but it can be that extent is the
12481988b51eSAlex Tomas 	 * first one in the file */
12491988b51eSAlex Tomas 
12501988b51eSAlex Tomas 	ex = path[depth].p_ext;
1251b939e376SAneesh Kumar K.V 	ee_len = ext4_ext_get_actual_len(ex);
12521988b51eSAlex Tomas 	if (*logical < le32_to_cpu(ex->ee_block)) {
12531988b51eSAlex Tomas 		BUG_ON(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex);
12541988b51eSAlex Tomas 		while (--depth >= 0) {
12551988b51eSAlex Tomas 			ix = path[depth].p_idx;
12561988b51eSAlex Tomas 			BUG_ON(ix != EXT_FIRST_INDEX(path[depth].p_hdr));
12571988b51eSAlex Tomas 		}
12581988b51eSAlex Tomas 		*logical = le32_to_cpu(ex->ee_block);
12591988b51eSAlex Tomas 		*phys = ext_pblock(ex);
12601988b51eSAlex Tomas 		return 0;
12611988b51eSAlex Tomas 	}
12621988b51eSAlex Tomas 
1263b939e376SAneesh Kumar K.V 	BUG_ON(*logical < (le32_to_cpu(ex->ee_block) + ee_len));
12641988b51eSAlex Tomas 
12651988b51eSAlex Tomas 	if (ex != EXT_LAST_EXTENT(path[depth].p_hdr)) {
12661988b51eSAlex Tomas 		/* next allocated block in this leaf */
12671988b51eSAlex Tomas 		ex++;
12681988b51eSAlex Tomas 		*logical = le32_to_cpu(ex->ee_block);
12691988b51eSAlex Tomas 		*phys = ext_pblock(ex);
12701988b51eSAlex Tomas 		return 0;
12711988b51eSAlex Tomas 	}
12721988b51eSAlex Tomas 
12731988b51eSAlex Tomas 	/* go up and search for index to the right */
12741988b51eSAlex Tomas 	while (--depth >= 0) {
12751988b51eSAlex Tomas 		ix = path[depth].p_idx;
12761988b51eSAlex Tomas 		if (ix != EXT_LAST_INDEX(path[depth].p_hdr))
127725f1ee3aSWu Fengguang 			goto got_index;
12781988b51eSAlex Tomas 	}
12791988b51eSAlex Tomas 
128025f1ee3aSWu Fengguang 	/* we've gone up to the root and found no index to the right */
12811988b51eSAlex Tomas 	return 0;
12821988b51eSAlex Tomas 
128325f1ee3aSWu Fengguang got_index:
12841988b51eSAlex Tomas 	/* we've found index to the right, let's
12851988b51eSAlex Tomas 	 * follow it and find the closest allocated
12861988b51eSAlex Tomas 	 * block to the right */
12871988b51eSAlex Tomas 	ix++;
12881988b51eSAlex Tomas 	block = idx_pblock(ix);
12891988b51eSAlex Tomas 	while (++depth < path->p_depth) {
12901988b51eSAlex Tomas 		bh = sb_bread(inode->i_sb, block);
12911988b51eSAlex Tomas 		if (bh == NULL)
12921988b51eSAlex Tomas 			return -EIO;
12931988b51eSAlex Tomas 		eh = ext_block_hdr(bh);
1294395a87bfSEric Sandeen 		/* subtract from p_depth to get proper eh_depth */
129556b19868SAneesh Kumar K.V 		if (ext4_ext_check(inode, eh, path->p_depth - depth)) {
12961988b51eSAlex Tomas 			put_bh(bh);
12971988b51eSAlex Tomas 			return -EIO;
12981988b51eSAlex Tomas 		}
12991988b51eSAlex Tomas 		ix = EXT_FIRST_INDEX(eh);
13001988b51eSAlex Tomas 		block = idx_pblock(ix);
13011988b51eSAlex Tomas 		put_bh(bh);
13021988b51eSAlex Tomas 	}
13031988b51eSAlex Tomas 
13041988b51eSAlex Tomas 	bh = sb_bread(inode->i_sb, block);
13051988b51eSAlex Tomas 	if (bh == NULL)
13061988b51eSAlex Tomas 		return -EIO;
13071988b51eSAlex Tomas 	eh = ext_block_hdr(bh);
130856b19868SAneesh Kumar K.V 	if (ext4_ext_check(inode, eh, path->p_depth - depth)) {
13091988b51eSAlex Tomas 		put_bh(bh);
13101988b51eSAlex Tomas 		return -EIO;
13111988b51eSAlex Tomas 	}
13121988b51eSAlex Tomas 	ex = EXT_FIRST_EXTENT(eh);
13131988b51eSAlex Tomas 	*logical = le32_to_cpu(ex->ee_block);
13141988b51eSAlex Tomas 	*phys = ext_pblock(ex);
13151988b51eSAlex Tomas 	put_bh(bh);
13161988b51eSAlex Tomas 	return 0;
13171988b51eSAlex Tomas }
13181988b51eSAlex Tomas 
13191988b51eSAlex Tomas /*
1320d0d856e8SRandy Dunlap  * ext4_ext_next_allocated_block:
1321d0d856e8SRandy Dunlap  * returns allocated block in subsequent extent or EXT_MAX_BLOCK.
1322d0d856e8SRandy Dunlap  * NOTE: it considers block number from index entry as
1323d0d856e8SRandy Dunlap  * allocated block. Thus, index entries have to be consistent
1324d0d856e8SRandy Dunlap  * with leaves.
1325a86c6181SAlex Tomas  */
1326725d26d3SAneesh Kumar K.V static ext4_lblk_t
1327a86c6181SAlex Tomas ext4_ext_next_allocated_block(struct ext4_ext_path *path)
1328a86c6181SAlex Tomas {
1329a86c6181SAlex Tomas 	int depth;
1330a86c6181SAlex Tomas 
1331a86c6181SAlex Tomas 	BUG_ON(path == NULL);
1332a86c6181SAlex Tomas 	depth = path->p_depth;
1333a86c6181SAlex Tomas 
1334a86c6181SAlex Tomas 	if (depth == 0 && path->p_ext == NULL)
1335a86c6181SAlex Tomas 		return EXT_MAX_BLOCK;
1336a86c6181SAlex Tomas 
1337a86c6181SAlex Tomas 	while (depth >= 0) {
1338a86c6181SAlex Tomas 		if (depth == path->p_depth) {
1339a86c6181SAlex Tomas 			/* leaf */
1340a86c6181SAlex Tomas 			if (path[depth].p_ext !=
1341a86c6181SAlex Tomas 					EXT_LAST_EXTENT(path[depth].p_hdr))
1342a86c6181SAlex Tomas 			  return le32_to_cpu(path[depth].p_ext[1].ee_block);
1343a86c6181SAlex Tomas 		} else {
1344a86c6181SAlex Tomas 			/* index */
1345a86c6181SAlex Tomas 			if (path[depth].p_idx !=
1346a86c6181SAlex Tomas 					EXT_LAST_INDEX(path[depth].p_hdr))
1347a86c6181SAlex Tomas 			  return le32_to_cpu(path[depth].p_idx[1].ei_block);
1348a86c6181SAlex Tomas 		}
1349a86c6181SAlex Tomas 		depth--;
1350a86c6181SAlex Tomas 	}
1351a86c6181SAlex Tomas 
1352a86c6181SAlex Tomas 	return EXT_MAX_BLOCK;
1353a86c6181SAlex Tomas }
1354a86c6181SAlex Tomas 
1355a86c6181SAlex Tomas /*
1356d0d856e8SRandy Dunlap  * ext4_ext_next_leaf_block:
1357a86c6181SAlex Tomas  * returns first allocated block from next leaf or EXT_MAX_BLOCK
1358a86c6181SAlex Tomas  */
1359725d26d3SAneesh Kumar K.V static ext4_lblk_t ext4_ext_next_leaf_block(struct inode *inode,
1360a86c6181SAlex Tomas 					struct ext4_ext_path *path)
1361a86c6181SAlex Tomas {
1362a86c6181SAlex Tomas 	int depth;
1363a86c6181SAlex Tomas 
1364a86c6181SAlex Tomas 	BUG_ON(path == NULL);
1365a86c6181SAlex Tomas 	depth = path->p_depth;
1366a86c6181SAlex Tomas 
1367a86c6181SAlex Tomas 	/* zero-tree has no leaf blocks at all */
1368a86c6181SAlex Tomas 	if (depth == 0)
1369a86c6181SAlex Tomas 		return EXT_MAX_BLOCK;
1370a86c6181SAlex Tomas 
1371a86c6181SAlex Tomas 	/* go to index block */
1372a86c6181SAlex Tomas 	depth--;
1373a86c6181SAlex Tomas 
1374a86c6181SAlex Tomas 	while (depth >= 0) {
1375a86c6181SAlex Tomas 		if (path[depth].p_idx !=
1376a86c6181SAlex Tomas 				EXT_LAST_INDEX(path[depth].p_hdr))
1377725d26d3SAneesh Kumar K.V 			return (ext4_lblk_t)
1378725d26d3SAneesh Kumar K.V 				le32_to_cpu(path[depth].p_idx[1].ei_block);
1379a86c6181SAlex Tomas 		depth--;
1380a86c6181SAlex Tomas 	}
1381a86c6181SAlex Tomas 
1382a86c6181SAlex Tomas 	return EXT_MAX_BLOCK;
1383a86c6181SAlex Tomas }
1384a86c6181SAlex Tomas 
1385a86c6181SAlex Tomas /*
1386d0d856e8SRandy Dunlap  * ext4_ext_correct_indexes:
1387d0d856e8SRandy Dunlap  * if leaf gets modified and modified extent is first in the leaf,
1388d0d856e8SRandy Dunlap  * then we have to correct all indexes above.
1389a86c6181SAlex Tomas  * TODO: do we need to correct tree in all cases?
1390a86c6181SAlex Tomas  */
13911d03ec98SAneesh Kumar K.V static int ext4_ext_correct_indexes(handle_t *handle, struct inode *inode,
1392a86c6181SAlex Tomas 				struct ext4_ext_path *path)
1393a86c6181SAlex Tomas {
1394a86c6181SAlex Tomas 	struct ext4_extent_header *eh;
1395a86c6181SAlex Tomas 	int depth = ext_depth(inode);
1396a86c6181SAlex Tomas 	struct ext4_extent *ex;
1397a86c6181SAlex Tomas 	__le32 border;
1398a86c6181SAlex Tomas 	int k, err = 0;
1399a86c6181SAlex Tomas 
1400a86c6181SAlex Tomas 	eh = path[depth].p_hdr;
1401a86c6181SAlex Tomas 	ex = path[depth].p_ext;
1402a86c6181SAlex Tomas 	BUG_ON(ex == NULL);
1403a86c6181SAlex Tomas 	BUG_ON(eh == NULL);
1404a86c6181SAlex Tomas 
1405a86c6181SAlex Tomas 	if (depth == 0) {
1406a86c6181SAlex Tomas 		/* there is no tree at all */
1407a86c6181SAlex Tomas 		return 0;
1408a86c6181SAlex Tomas 	}
1409a86c6181SAlex Tomas 
1410a86c6181SAlex Tomas 	if (ex != EXT_FIRST_EXTENT(eh)) {
1411a86c6181SAlex Tomas 		/* we correct tree if first leaf got modified only */
1412a86c6181SAlex Tomas 		return 0;
1413a86c6181SAlex Tomas 	}
1414a86c6181SAlex Tomas 
1415a86c6181SAlex Tomas 	/*
1416d0d856e8SRandy Dunlap 	 * TODO: we need correction if border is smaller than current one
1417a86c6181SAlex Tomas 	 */
1418a86c6181SAlex Tomas 	k = depth - 1;
1419a86c6181SAlex Tomas 	border = path[depth].p_ext->ee_block;
14207e028976SAvantika Mathur 	err = ext4_ext_get_access(handle, inode, path + k);
14217e028976SAvantika Mathur 	if (err)
1422a86c6181SAlex Tomas 		return err;
1423a86c6181SAlex Tomas 	path[k].p_idx->ei_block = border;
14247e028976SAvantika Mathur 	err = ext4_ext_dirty(handle, inode, path + k);
14257e028976SAvantika Mathur 	if (err)
1426a86c6181SAlex Tomas 		return err;
1427a86c6181SAlex Tomas 
1428a86c6181SAlex Tomas 	while (k--) {
1429a86c6181SAlex Tomas 		/* change all left-side indexes */
1430a86c6181SAlex Tomas 		if (path[k+1].p_idx != EXT_FIRST_INDEX(path[k+1].p_hdr))
1431a86c6181SAlex Tomas 			break;
14327e028976SAvantika Mathur 		err = ext4_ext_get_access(handle, inode, path + k);
14337e028976SAvantika Mathur 		if (err)
1434a86c6181SAlex Tomas 			break;
1435a86c6181SAlex Tomas 		path[k].p_idx->ei_block = border;
14367e028976SAvantika Mathur 		err = ext4_ext_dirty(handle, inode, path + k);
14377e028976SAvantika Mathur 		if (err)
1438a86c6181SAlex Tomas 			break;
1439a86c6181SAlex Tomas 	}
1440a86c6181SAlex Tomas 
1441a86c6181SAlex Tomas 	return err;
1442a86c6181SAlex Tomas }
1443a86c6181SAlex Tomas 
1444748de673SAkira Fujita int
1445a86c6181SAlex Tomas ext4_can_extents_be_merged(struct inode *inode, struct ext4_extent *ex1,
1446a86c6181SAlex Tomas 				struct ext4_extent *ex2)
1447a86c6181SAlex Tomas {
1448749269faSAmit Arora 	unsigned short ext1_ee_len, ext2_ee_len, max_len;
1449a2df2a63SAmit Arora 
1450a2df2a63SAmit Arora 	/*
1451a2df2a63SAmit Arora 	 * Make sure that either both extents are uninitialized, or
1452a2df2a63SAmit Arora 	 * both are _not_.
1453a2df2a63SAmit Arora 	 */
1454a2df2a63SAmit Arora 	if (ext4_ext_is_uninitialized(ex1) ^ ext4_ext_is_uninitialized(ex2))
1455a2df2a63SAmit Arora 		return 0;
1456a2df2a63SAmit Arora 
1457749269faSAmit Arora 	if (ext4_ext_is_uninitialized(ex1))
1458749269faSAmit Arora 		max_len = EXT_UNINIT_MAX_LEN;
1459749269faSAmit Arora 	else
1460749269faSAmit Arora 		max_len = EXT_INIT_MAX_LEN;
1461749269faSAmit Arora 
1462a2df2a63SAmit Arora 	ext1_ee_len = ext4_ext_get_actual_len(ex1);
1463a2df2a63SAmit Arora 	ext2_ee_len = ext4_ext_get_actual_len(ex2);
1464a2df2a63SAmit Arora 
1465a2df2a63SAmit Arora 	if (le32_to_cpu(ex1->ee_block) + ext1_ee_len !=
146663f57933SAndrew Morton 			le32_to_cpu(ex2->ee_block))
1467a86c6181SAlex Tomas 		return 0;
1468a86c6181SAlex Tomas 
1469471d4011SSuparna Bhattacharya 	/*
1470471d4011SSuparna Bhattacharya 	 * To allow future support for preallocated extents to be added
1471471d4011SSuparna Bhattacharya 	 * as an RO_COMPAT feature, refuse to merge to extents if
1472d0d856e8SRandy Dunlap 	 * this can result in the top bit of ee_len being set.
1473471d4011SSuparna Bhattacharya 	 */
1474749269faSAmit Arora 	if (ext1_ee_len + ext2_ee_len > max_len)
1475471d4011SSuparna Bhattacharya 		return 0;
1476bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST
1477b939e376SAneesh Kumar K.V 	if (ext1_ee_len >= 4)
1478a86c6181SAlex Tomas 		return 0;
1479a86c6181SAlex Tomas #endif
1480a86c6181SAlex Tomas 
1481a2df2a63SAmit Arora 	if (ext_pblock(ex1) + ext1_ee_len == ext_pblock(ex2))
1482a86c6181SAlex Tomas 		return 1;
1483a86c6181SAlex Tomas 	return 0;
1484a86c6181SAlex Tomas }
1485a86c6181SAlex Tomas 
1486a86c6181SAlex Tomas /*
148756055d3aSAmit Arora  * This function tries to merge the "ex" extent to the next extent in the tree.
148856055d3aSAmit Arora  * It always tries to merge towards right. If you want to merge towards
148956055d3aSAmit Arora  * left, pass "ex - 1" as argument instead of "ex".
149056055d3aSAmit Arora  * Returns 0 if the extents (ex and ex+1) were _not_ merged and returns
149156055d3aSAmit Arora  * 1 if they got merged.
149256055d3aSAmit Arora  */
149356055d3aSAmit Arora int ext4_ext_try_to_merge(struct inode *inode,
149456055d3aSAmit Arora 			  struct ext4_ext_path *path,
149556055d3aSAmit Arora 			  struct ext4_extent *ex)
149656055d3aSAmit Arora {
149756055d3aSAmit Arora 	struct ext4_extent_header *eh;
149856055d3aSAmit Arora 	unsigned int depth, len;
149956055d3aSAmit Arora 	int merge_done = 0;
150056055d3aSAmit Arora 	int uninitialized = 0;
150156055d3aSAmit Arora 
150256055d3aSAmit Arora 	depth = ext_depth(inode);
150356055d3aSAmit Arora 	BUG_ON(path[depth].p_hdr == NULL);
150456055d3aSAmit Arora 	eh = path[depth].p_hdr;
150556055d3aSAmit Arora 
150656055d3aSAmit Arora 	while (ex < EXT_LAST_EXTENT(eh)) {
150756055d3aSAmit Arora 		if (!ext4_can_extents_be_merged(inode, ex, ex + 1))
150856055d3aSAmit Arora 			break;
150956055d3aSAmit Arora 		/* merge with next extent! */
151056055d3aSAmit Arora 		if (ext4_ext_is_uninitialized(ex))
151156055d3aSAmit Arora 			uninitialized = 1;
151256055d3aSAmit Arora 		ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
151356055d3aSAmit Arora 				+ ext4_ext_get_actual_len(ex + 1));
151456055d3aSAmit Arora 		if (uninitialized)
151556055d3aSAmit Arora 			ext4_ext_mark_uninitialized(ex);
151656055d3aSAmit Arora 
151756055d3aSAmit Arora 		if (ex + 1 < EXT_LAST_EXTENT(eh)) {
151856055d3aSAmit Arora 			len = (EXT_LAST_EXTENT(eh) - ex - 1)
151956055d3aSAmit Arora 				* sizeof(struct ext4_extent);
152056055d3aSAmit Arora 			memmove(ex + 1, ex + 2, len);
152156055d3aSAmit Arora 		}
1522e8546d06SMarcin Slusarz 		le16_add_cpu(&eh->eh_entries, -1);
152356055d3aSAmit Arora 		merge_done = 1;
152456055d3aSAmit Arora 		WARN_ON(eh->eh_entries == 0);
152556055d3aSAmit Arora 		if (!eh->eh_entries)
152656055d3aSAmit Arora 			ext4_error(inode->i_sb, "ext4_ext_try_to_merge",
152756055d3aSAmit Arora 			   "inode#%lu, eh->eh_entries = 0!", inode->i_ino);
152856055d3aSAmit Arora 	}
152956055d3aSAmit Arora 
153056055d3aSAmit Arora 	return merge_done;
153156055d3aSAmit Arora }
153256055d3aSAmit Arora 
153356055d3aSAmit Arora /*
153425d14f98SAmit Arora  * check if a portion of the "newext" extent overlaps with an
153525d14f98SAmit Arora  * existing extent.
153625d14f98SAmit Arora  *
153725d14f98SAmit Arora  * If there is an overlap discovered, it updates the length of the newext
153825d14f98SAmit Arora  * such that there will be no overlap, and then returns 1.
153925d14f98SAmit Arora  * If there is no overlap found, it returns 0.
154025d14f98SAmit Arora  */
154125d14f98SAmit Arora unsigned int ext4_ext_check_overlap(struct inode *inode,
154225d14f98SAmit Arora 				    struct ext4_extent *newext,
154325d14f98SAmit Arora 				    struct ext4_ext_path *path)
154425d14f98SAmit Arora {
1545725d26d3SAneesh Kumar K.V 	ext4_lblk_t b1, b2;
154625d14f98SAmit Arora 	unsigned int depth, len1;
154725d14f98SAmit Arora 	unsigned int ret = 0;
154825d14f98SAmit Arora 
154925d14f98SAmit Arora 	b1 = le32_to_cpu(newext->ee_block);
1550a2df2a63SAmit Arora 	len1 = ext4_ext_get_actual_len(newext);
155125d14f98SAmit Arora 	depth = ext_depth(inode);
155225d14f98SAmit Arora 	if (!path[depth].p_ext)
155325d14f98SAmit Arora 		goto out;
155425d14f98SAmit Arora 	b2 = le32_to_cpu(path[depth].p_ext->ee_block);
155525d14f98SAmit Arora 
155625d14f98SAmit Arora 	/*
155725d14f98SAmit Arora 	 * get the next allocated block if the extent in the path
155825d14f98SAmit Arora 	 * is before the requested block(s)
155925d14f98SAmit Arora 	 */
156025d14f98SAmit Arora 	if (b2 < b1) {
156125d14f98SAmit Arora 		b2 = ext4_ext_next_allocated_block(path);
156225d14f98SAmit Arora 		if (b2 == EXT_MAX_BLOCK)
156325d14f98SAmit Arora 			goto out;
156425d14f98SAmit Arora 	}
156525d14f98SAmit Arora 
1566725d26d3SAneesh Kumar K.V 	/* check for wrap through zero on extent logical start block*/
156725d14f98SAmit Arora 	if (b1 + len1 < b1) {
156825d14f98SAmit Arora 		len1 = EXT_MAX_BLOCK - b1;
156925d14f98SAmit Arora 		newext->ee_len = cpu_to_le16(len1);
157025d14f98SAmit Arora 		ret = 1;
157125d14f98SAmit Arora 	}
157225d14f98SAmit Arora 
157325d14f98SAmit Arora 	/* check for overlap */
157425d14f98SAmit Arora 	if (b1 + len1 > b2) {
157525d14f98SAmit Arora 		newext->ee_len = cpu_to_le16(b2 - b1);
157625d14f98SAmit Arora 		ret = 1;
157725d14f98SAmit Arora 	}
157825d14f98SAmit Arora out:
157925d14f98SAmit Arora 	return ret;
158025d14f98SAmit Arora }
158125d14f98SAmit Arora 
158225d14f98SAmit Arora /*
1583d0d856e8SRandy Dunlap  * ext4_ext_insert_extent:
1584d0d856e8SRandy Dunlap  * tries to merge requsted extent into the existing extent or
1585d0d856e8SRandy Dunlap  * inserts requested extent as new one into the tree,
1586d0d856e8SRandy Dunlap  * creating new leaf in the no-space case.
1587a86c6181SAlex Tomas  */
1588a86c6181SAlex Tomas int ext4_ext_insert_extent(handle_t *handle, struct inode *inode,
1589a86c6181SAlex Tomas 				struct ext4_ext_path *path,
15900031462bSMingming Cao 				struct ext4_extent *newext, int flag)
1591a86c6181SAlex Tomas {
1592a86c6181SAlex Tomas 	struct ext4_extent_header *eh;
1593a86c6181SAlex Tomas 	struct ext4_extent *ex, *fex;
1594a86c6181SAlex Tomas 	struct ext4_extent *nearex; /* nearest extent */
1595a86c6181SAlex Tomas 	struct ext4_ext_path *npath = NULL;
1596725d26d3SAneesh Kumar K.V 	int depth, len, err;
1597725d26d3SAneesh Kumar K.V 	ext4_lblk_t next;
1598a2df2a63SAmit Arora 	unsigned uninitialized = 0;
1599a86c6181SAlex Tomas 
1600a2df2a63SAmit Arora 	BUG_ON(ext4_ext_get_actual_len(newext) == 0);
1601a86c6181SAlex Tomas 	depth = ext_depth(inode);
1602a86c6181SAlex Tomas 	ex = path[depth].p_ext;
1603a86c6181SAlex Tomas 	BUG_ON(path[depth].p_hdr == NULL);
1604a86c6181SAlex Tomas 
1605a86c6181SAlex Tomas 	/* try to insert block into found extent and return */
16060031462bSMingming Cao 	if (ex && (flag != EXT4_GET_BLOCKS_DIO_CREATE_EXT)
16070031462bSMingming Cao 		&& ext4_can_extents_be_merged(inode, ex, newext)) {
1608553f9008SMingming 		ext_debug("append [%d]%d block to %d:[%d]%d (from %llu)\n",
1609553f9008SMingming 				ext4_ext_is_uninitialized(newext),
1610a2df2a63SAmit Arora 				ext4_ext_get_actual_len(newext),
1611a86c6181SAlex Tomas 				le32_to_cpu(ex->ee_block),
1612553f9008SMingming 				ext4_ext_is_uninitialized(ex),
1613a2df2a63SAmit Arora 				ext4_ext_get_actual_len(ex), ext_pblock(ex));
16147e028976SAvantika Mathur 		err = ext4_ext_get_access(handle, inode, path + depth);
16157e028976SAvantika Mathur 		if (err)
1616a86c6181SAlex Tomas 			return err;
1617a2df2a63SAmit Arora 
1618a2df2a63SAmit Arora 		/*
1619a2df2a63SAmit Arora 		 * ext4_can_extents_be_merged should have checked that either
1620a2df2a63SAmit Arora 		 * both extents are uninitialized, or both aren't. Thus we
1621a2df2a63SAmit Arora 		 * need to check only one of them here.
1622a2df2a63SAmit Arora 		 */
1623a2df2a63SAmit Arora 		if (ext4_ext_is_uninitialized(ex))
1624a2df2a63SAmit Arora 			uninitialized = 1;
1625a2df2a63SAmit Arora 		ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
1626a2df2a63SAmit Arora 					+ ext4_ext_get_actual_len(newext));
1627a2df2a63SAmit Arora 		if (uninitialized)
1628a2df2a63SAmit Arora 			ext4_ext_mark_uninitialized(ex);
1629a86c6181SAlex Tomas 		eh = path[depth].p_hdr;
1630a86c6181SAlex Tomas 		nearex = ex;
1631a86c6181SAlex Tomas 		goto merge;
1632a86c6181SAlex Tomas 	}
1633a86c6181SAlex Tomas 
1634a86c6181SAlex Tomas repeat:
1635a86c6181SAlex Tomas 	depth = ext_depth(inode);
1636a86c6181SAlex Tomas 	eh = path[depth].p_hdr;
1637a86c6181SAlex Tomas 	if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))
1638a86c6181SAlex Tomas 		goto has_space;
1639a86c6181SAlex Tomas 
1640a86c6181SAlex Tomas 	/* probably next leaf has space for us? */
1641a86c6181SAlex Tomas 	fex = EXT_LAST_EXTENT(eh);
1642a86c6181SAlex Tomas 	next = ext4_ext_next_leaf_block(inode, path);
1643a86c6181SAlex Tomas 	if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block)
1644a86c6181SAlex Tomas 	    && next != EXT_MAX_BLOCK) {
1645a86c6181SAlex Tomas 		ext_debug("next leaf block - %d\n", next);
1646a86c6181SAlex Tomas 		BUG_ON(npath != NULL);
1647a86c6181SAlex Tomas 		npath = ext4_ext_find_extent(inode, next, NULL);
1648a86c6181SAlex Tomas 		if (IS_ERR(npath))
1649a86c6181SAlex Tomas 			return PTR_ERR(npath);
1650a86c6181SAlex Tomas 		BUG_ON(npath->p_depth != path->p_depth);
1651a86c6181SAlex Tomas 		eh = npath[depth].p_hdr;
1652a86c6181SAlex Tomas 		if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) {
1653a86c6181SAlex Tomas 			ext_debug("next leaf isnt full(%d)\n",
1654a86c6181SAlex Tomas 				  le16_to_cpu(eh->eh_entries));
1655a86c6181SAlex Tomas 			path = npath;
1656a86c6181SAlex Tomas 			goto repeat;
1657a86c6181SAlex Tomas 		}
1658a86c6181SAlex Tomas 		ext_debug("next leaf has no free space(%d,%d)\n",
1659a86c6181SAlex Tomas 			  le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
1660a86c6181SAlex Tomas 	}
1661a86c6181SAlex Tomas 
1662a86c6181SAlex Tomas 	/*
1663d0d856e8SRandy Dunlap 	 * There is no free space in the found leaf.
1664d0d856e8SRandy Dunlap 	 * We're gonna add a new leaf in the tree.
1665a86c6181SAlex Tomas 	 */
1666a86c6181SAlex Tomas 	err = ext4_ext_create_new_leaf(handle, inode, path, newext);
1667a86c6181SAlex Tomas 	if (err)
1668a86c6181SAlex Tomas 		goto cleanup;
1669a86c6181SAlex Tomas 	depth = ext_depth(inode);
1670a86c6181SAlex Tomas 	eh = path[depth].p_hdr;
1671a86c6181SAlex Tomas 
1672a86c6181SAlex Tomas has_space:
1673a86c6181SAlex Tomas 	nearex = path[depth].p_ext;
1674a86c6181SAlex Tomas 
16757e028976SAvantika Mathur 	err = ext4_ext_get_access(handle, inode, path + depth);
16767e028976SAvantika Mathur 	if (err)
1677a86c6181SAlex Tomas 		goto cleanup;
1678a86c6181SAlex Tomas 
1679a86c6181SAlex Tomas 	if (!nearex) {
1680a86c6181SAlex Tomas 		/* there is no extent in this leaf, create first one */
1681553f9008SMingming 		ext_debug("first extent in the leaf: %d:%llu:[%d]%d\n",
1682a86c6181SAlex Tomas 				le32_to_cpu(newext->ee_block),
1683f65e6fbaSAlex Tomas 				ext_pblock(newext),
1684553f9008SMingming 				ext4_ext_is_uninitialized(newext),
1685a2df2a63SAmit Arora 				ext4_ext_get_actual_len(newext));
1686a86c6181SAlex Tomas 		path[depth].p_ext = EXT_FIRST_EXTENT(eh);
1687a86c6181SAlex Tomas 	} else if (le32_to_cpu(newext->ee_block)
1688a86c6181SAlex Tomas 			   > le32_to_cpu(nearex->ee_block)) {
1689a86c6181SAlex Tomas /*		BUG_ON(newext->ee_block == nearex->ee_block); */
1690a86c6181SAlex Tomas 		if (nearex != EXT_LAST_EXTENT(eh)) {
1691a86c6181SAlex Tomas 			len = EXT_MAX_EXTENT(eh) - nearex;
1692a86c6181SAlex Tomas 			len = (len - 1) * sizeof(struct ext4_extent);
1693a86c6181SAlex Tomas 			len = len < 0 ? 0 : len;
1694553f9008SMingming 			ext_debug("insert %d:%llu:[%d]%d after: nearest 0x%p, "
1695a86c6181SAlex Tomas 					"move %d from 0x%p to 0x%p\n",
1696a86c6181SAlex Tomas 					le32_to_cpu(newext->ee_block),
1697f65e6fbaSAlex Tomas 					ext_pblock(newext),
1698553f9008SMingming 					ext4_ext_is_uninitialized(newext),
1699a2df2a63SAmit Arora 					ext4_ext_get_actual_len(newext),
1700a86c6181SAlex Tomas 					nearex, len, nearex + 1, nearex + 2);
1701a86c6181SAlex Tomas 			memmove(nearex + 2, nearex + 1, len);
1702a86c6181SAlex Tomas 		}
1703a86c6181SAlex Tomas 		path[depth].p_ext = nearex + 1;
1704a86c6181SAlex Tomas 	} else {
1705a86c6181SAlex Tomas 		BUG_ON(newext->ee_block == nearex->ee_block);
1706a86c6181SAlex Tomas 		len = (EXT_MAX_EXTENT(eh) - nearex) * sizeof(struct ext4_extent);
1707a86c6181SAlex Tomas 		len = len < 0 ? 0 : len;
1708553f9008SMingming 		ext_debug("insert %d:%llu:[%d]%d before: nearest 0x%p, "
1709a86c6181SAlex Tomas 				"move %d from 0x%p to 0x%p\n",
1710a86c6181SAlex Tomas 				le32_to_cpu(newext->ee_block),
1711f65e6fbaSAlex Tomas 				ext_pblock(newext),
1712553f9008SMingming 				ext4_ext_is_uninitialized(newext),
1713a2df2a63SAmit Arora 				ext4_ext_get_actual_len(newext),
1714a86c6181SAlex Tomas 				nearex, len, nearex + 1, nearex + 2);
1715a86c6181SAlex Tomas 		memmove(nearex + 1, nearex, len);
1716a86c6181SAlex Tomas 		path[depth].p_ext = nearex;
1717a86c6181SAlex Tomas 	}
1718a86c6181SAlex Tomas 
1719e8546d06SMarcin Slusarz 	le16_add_cpu(&eh->eh_entries, 1);
1720a86c6181SAlex Tomas 	nearex = path[depth].p_ext;
1721a86c6181SAlex Tomas 	nearex->ee_block = newext->ee_block;
1722b377611dSAneesh Kumar K.V 	ext4_ext_store_pblock(nearex, ext_pblock(newext));
1723a86c6181SAlex Tomas 	nearex->ee_len = newext->ee_len;
1724a86c6181SAlex Tomas 
1725a86c6181SAlex Tomas merge:
1726a86c6181SAlex Tomas 	/* try to merge extents to the right */
17270031462bSMingming Cao 	if (flag != EXT4_GET_BLOCKS_DIO_CREATE_EXT)
172856055d3aSAmit Arora 		ext4_ext_try_to_merge(inode, path, nearex);
1729a86c6181SAlex Tomas 
1730a86c6181SAlex Tomas 	/* try to merge extents to the left */
1731a86c6181SAlex Tomas 
1732a86c6181SAlex Tomas 	/* time to correct all indexes above */
1733a86c6181SAlex Tomas 	err = ext4_ext_correct_indexes(handle, inode, path);
1734a86c6181SAlex Tomas 	if (err)
1735a86c6181SAlex Tomas 		goto cleanup;
1736a86c6181SAlex Tomas 
1737a86c6181SAlex Tomas 	err = ext4_ext_dirty(handle, inode, path + depth);
1738a86c6181SAlex Tomas 
1739a86c6181SAlex Tomas cleanup:
1740a86c6181SAlex Tomas 	if (npath) {
1741a86c6181SAlex Tomas 		ext4_ext_drop_refs(npath);
1742a86c6181SAlex Tomas 		kfree(npath);
1743a86c6181SAlex Tomas 	}
1744a86c6181SAlex Tomas 	ext4_ext_invalidate_cache(inode);
1745a86c6181SAlex Tomas 	return err;
1746a86c6181SAlex Tomas }
1747a86c6181SAlex Tomas 
17486873fa0dSEric Sandeen int ext4_ext_walk_space(struct inode *inode, ext4_lblk_t block,
17496873fa0dSEric Sandeen 			ext4_lblk_t num, ext_prepare_callback func,
17506873fa0dSEric Sandeen 			void *cbdata)
17516873fa0dSEric Sandeen {
17526873fa0dSEric Sandeen 	struct ext4_ext_path *path = NULL;
17536873fa0dSEric Sandeen 	struct ext4_ext_cache cbex;
17546873fa0dSEric Sandeen 	struct ext4_extent *ex;
17556873fa0dSEric Sandeen 	ext4_lblk_t next, start = 0, end = 0;
17566873fa0dSEric Sandeen 	ext4_lblk_t last = block + num;
17576873fa0dSEric Sandeen 	int depth, exists, err = 0;
17586873fa0dSEric Sandeen 
17596873fa0dSEric Sandeen 	BUG_ON(func == NULL);
17606873fa0dSEric Sandeen 	BUG_ON(inode == NULL);
17616873fa0dSEric Sandeen 
17626873fa0dSEric Sandeen 	while (block < last && block != EXT_MAX_BLOCK) {
17636873fa0dSEric Sandeen 		num = last - block;
17646873fa0dSEric Sandeen 		/* find extent for this block */
17656873fa0dSEric Sandeen 		path = ext4_ext_find_extent(inode, block, path);
17666873fa0dSEric Sandeen 		if (IS_ERR(path)) {
17676873fa0dSEric Sandeen 			err = PTR_ERR(path);
17686873fa0dSEric Sandeen 			path = NULL;
17696873fa0dSEric Sandeen 			break;
17706873fa0dSEric Sandeen 		}
17716873fa0dSEric Sandeen 
17726873fa0dSEric Sandeen 		depth = ext_depth(inode);
17736873fa0dSEric Sandeen 		BUG_ON(path[depth].p_hdr == NULL);
17746873fa0dSEric Sandeen 		ex = path[depth].p_ext;
17756873fa0dSEric Sandeen 		next = ext4_ext_next_allocated_block(path);
17766873fa0dSEric Sandeen 
17776873fa0dSEric Sandeen 		exists = 0;
17786873fa0dSEric Sandeen 		if (!ex) {
17796873fa0dSEric Sandeen 			/* there is no extent yet, so try to allocate
17806873fa0dSEric Sandeen 			 * all requested space */
17816873fa0dSEric Sandeen 			start = block;
17826873fa0dSEric Sandeen 			end = block + num;
17836873fa0dSEric Sandeen 		} else if (le32_to_cpu(ex->ee_block) > block) {
17846873fa0dSEric Sandeen 			/* need to allocate space before found extent */
17856873fa0dSEric Sandeen 			start = block;
17866873fa0dSEric Sandeen 			end = le32_to_cpu(ex->ee_block);
17876873fa0dSEric Sandeen 			if (block + num < end)
17886873fa0dSEric Sandeen 				end = block + num;
17896873fa0dSEric Sandeen 		} else if (block >= le32_to_cpu(ex->ee_block)
17906873fa0dSEric Sandeen 					+ ext4_ext_get_actual_len(ex)) {
17916873fa0dSEric Sandeen 			/* need to allocate space after found extent */
17926873fa0dSEric Sandeen 			start = block;
17936873fa0dSEric Sandeen 			end = block + num;
17946873fa0dSEric Sandeen 			if (end >= next)
17956873fa0dSEric Sandeen 				end = next;
17966873fa0dSEric Sandeen 		} else if (block >= le32_to_cpu(ex->ee_block)) {
17976873fa0dSEric Sandeen 			/*
17986873fa0dSEric Sandeen 			 * some part of requested space is covered
17996873fa0dSEric Sandeen 			 * by found extent
18006873fa0dSEric Sandeen 			 */
18016873fa0dSEric Sandeen 			start = block;
18026873fa0dSEric Sandeen 			end = le32_to_cpu(ex->ee_block)
18036873fa0dSEric Sandeen 				+ ext4_ext_get_actual_len(ex);
18046873fa0dSEric Sandeen 			if (block + num < end)
18056873fa0dSEric Sandeen 				end = block + num;
18066873fa0dSEric Sandeen 			exists = 1;
18076873fa0dSEric Sandeen 		} else {
18086873fa0dSEric Sandeen 			BUG();
18096873fa0dSEric Sandeen 		}
18106873fa0dSEric Sandeen 		BUG_ON(end <= start);
18116873fa0dSEric Sandeen 
18126873fa0dSEric Sandeen 		if (!exists) {
18136873fa0dSEric Sandeen 			cbex.ec_block = start;
18146873fa0dSEric Sandeen 			cbex.ec_len = end - start;
18156873fa0dSEric Sandeen 			cbex.ec_start = 0;
18166873fa0dSEric Sandeen 			cbex.ec_type = EXT4_EXT_CACHE_GAP;
18176873fa0dSEric Sandeen 		} else {
18186873fa0dSEric Sandeen 			cbex.ec_block = le32_to_cpu(ex->ee_block);
18196873fa0dSEric Sandeen 			cbex.ec_len = ext4_ext_get_actual_len(ex);
18206873fa0dSEric Sandeen 			cbex.ec_start = ext_pblock(ex);
18216873fa0dSEric Sandeen 			cbex.ec_type = EXT4_EXT_CACHE_EXTENT;
18226873fa0dSEric Sandeen 		}
18236873fa0dSEric Sandeen 
18246873fa0dSEric Sandeen 		BUG_ON(cbex.ec_len == 0);
18256873fa0dSEric Sandeen 		err = func(inode, path, &cbex, ex, cbdata);
18266873fa0dSEric Sandeen 		ext4_ext_drop_refs(path);
18276873fa0dSEric Sandeen 
18286873fa0dSEric Sandeen 		if (err < 0)
18296873fa0dSEric Sandeen 			break;
18306873fa0dSEric Sandeen 
18316873fa0dSEric Sandeen 		if (err == EXT_REPEAT)
18326873fa0dSEric Sandeen 			continue;
18336873fa0dSEric Sandeen 		else if (err == EXT_BREAK) {
18346873fa0dSEric Sandeen 			err = 0;
18356873fa0dSEric Sandeen 			break;
18366873fa0dSEric Sandeen 		}
18376873fa0dSEric Sandeen 
18386873fa0dSEric Sandeen 		if (ext_depth(inode) != depth) {
18396873fa0dSEric Sandeen 			/* depth was changed. we have to realloc path */
18406873fa0dSEric Sandeen 			kfree(path);
18416873fa0dSEric Sandeen 			path = NULL;
18426873fa0dSEric Sandeen 		}
18436873fa0dSEric Sandeen 
18446873fa0dSEric Sandeen 		block = cbex.ec_block + cbex.ec_len;
18456873fa0dSEric Sandeen 	}
18466873fa0dSEric Sandeen 
18476873fa0dSEric Sandeen 	if (path) {
18486873fa0dSEric Sandeen 		ext4_ext_drop_refs(path);
18496873fa0dSEric Sandeen 		kfree(path);
18506873fa0dSEric Sandeen 	}
18516873fa0dSEric Sandeen 
18526873fa0dSEric Sandeen 	return err;
18536873fa0dSEric Sandeen }
18546873fa0dSEric Sandeen 
185509b88252SAvantika Mathur static void
1856725d26d3SAneesh Kumar K.V ext4_ext_put_in_cache(struct inode *inode, ext4_lblk_t block,
1857dd54567aSMingming Cao 			__u32 len, ext4_fsblk_t start, int type)
1858a86c6181SAlex Tomas {
1859a86c6181SAlex Tomas 	struct ext4_ext_cache *cex;
1860a86c6181SAlex Tomas 	BUG_ON(len == 0);
18612ec0ae3aSTheodore Ts'o 	spin_lock(&EXT4_I(inode)->i_block_reservation_lock);
1862a86c6181SAlex Tomas 	cex = &EXT4_I(inode)->i_cached_extent;
1863a86c6181SAlex Tomas 	cex->ec_type = type;
1864a86c6181SAlex Tomas 	cex->ec_block = block;
1865a86c6181SAlex Tomas 	cex->ec_len = len;
1866a86c6181SAlex Tomas 	cex->ec_start = start;
18672ec0ae3aSTheodore Ts'o 	spin_unlock(&EXT4_I(inode)->i_block_reservation_lock);
1868a86c6181SAlex Tomas }
1869a86c6181SAlex Tomas 
1870a86c6181SAlex Tomas /*
1871d0d856e8SRandy Dunlap  * ext4_ext_put_gap_in_cache:
1872d0d856e8SRandy Dunlap  * calculate boundaries of the gap that the requested block fits into
1873a86c6181SAlex Tomas  * and cache this gap
1874a86c6181SAlex Tomas  */
187509b88252SAvantika Mathur static void
1876a86c6181SAlex Tomas ext4_ext_put_gap_in_cache(struct inode *inode, struct ext4_ext_path *path,
1877725d26d3SAneesh Kumar K.V 				ext4_lblk_t block)
1878a86c6181SAlex Tomas {
1879a86c6181SAlex Tomas 	int depth = ext_depth(inode);
1880725d26d3SAneesh Kumar K.V 	unsigned long len;
1881725d26d3SAneesh Kumar K.V 	ext4_lblk_t lblock;
1882a86c6181SAlex Tomas 	struct ext4_extent *ex;
1883a86c6181SAlex Tomas 
1884a86c6181SAlex Tomas 	ex = path[depth].p_ext;
1885a86c6181SAlex Tomas 	if (ex == NULL) {
1886a86c6181SAlex Tomas 		/* there is no extent yet, so gap is [0;-] */
1887a86c6181SAlex Tomas 		lblock = 0;
1888a86c6181SAlex Tomas 		len = EXT_MAX_BLOCK;
1889a86c6181SAlex Tomas 		ext_debug("cache gap(whole file):");
1890a86c6181SAlex Tomas 	} else if (block < le32_to_cpu(ex->ee_block)) {
1891a86c6181SAlex Tomas 		lblock = block;
1892a86c6181SAlex Tomas 		len = le32_to_cpu(ex->ee_block) - block;
1893bba90743SEric Sandeen 		ext_debug("cache gap(before): %u [%u:%u]",
1894bba90743SEric Sandeen 				block,
1895bba90743SEric Sandeen 				le32_to_cpu(ex->ee_block),
1896bba90743SEric Sandeen 				 ext4_ext_get_actual_len(ex));
1897a86c6181SAlex Tomas 	} else if (block >= le32_to_cpu(ex->ee_block)
1898a2df2a63SAmit Arora 			+ ext4_ext_get_actual_len(ex)) {
1899725d26d3SAneesh Kumar K.V 		ext4_lblk_t next;
1900a86c6181SAlex Tomas 		lblock = le32_to_cpu(ex->ee_block)
1901a2df2a63SAmit Arora 			+ ext4_ext_get_actual_len(ex);
1902725d26d3SAneesh Kumar K.V 
1903725d26d3SAneesh Kumar K.V 		next = ext4_ext_next_allocated_block(path);
1904bba90743SEric Sandeen 		ext_debug("cache gap(after): [%u:%u] %u",
1905bba90743SEric Sandeen 				le32_to_cpu(ex->ee_block),
1906bba90743SEric Sandeen 				ext4_ext_get_actual_len(ex),
1907bba90743SEric Sandeen 				block);
1908725d26d3SAneesh Kumar K.V 		BUG_ON(next == lblock);
1909725d26d3SAneesh Kumar K.V 		len = next - lblock;
1910a86c6181SAlex Tomas 	} else {
1911a86c6181SAlex Tomas 		lblock = len = 0;
1912a86c6181SAlex Tomas 		BUG();
1913a86c6181SAlex Tomas 	}
1914a86c6181SAlex Tomas 
1915bba90743SEric Sandeen 	ext_debug(" -> %u:%lu\n", lblock, len);
1916a86c6181SAlex Tomas 	ext4_ext_put_in_cache(inode, lblock, len, 0, EXT4_EXT_CACHE_GAP);
1917a86c6181SAlex Tomas }
1918a86c6181SAlex Tomas 
191909b88252SAvantika Mathur static int
1920725d26d3SAneesh Kumar K.V ext4_ext_in_cache(struct inode *inode, ext4_lblk_t block,
1921a86c6181SAlex Tomas 			struct ext4_extent *ex)
1922a86c6181SAlex Tomas {
1923a86c6181SAlex Tomas 	struct ext4_ext_cache *cex;
19242ec0ae3aSTheodore Ts'o 	int ret = EXT4_EXT_CACHE_NO;
1925a86c6181SAlex Tomas 
19262ec0ae3aSTheodore Ts'o 	/*
19272ec0ae3aSTheodore Ts'o 	 * We borrow i_block_reservation_lock to protect i_cached_extent
19282ec0ae3aSTheodore Ts'o 	 */
19292ec0ae3aSTheodore Ts'o 	spin_lock(&EXT4_I(inode)->i_block_reservation_lock);
1930a86c6181SAlex Tomas 	cex = &EXT4_I(inode)->i_cached_extent;
1931a86c6181SAlex Tomas 
1932a86c6181SAlex Tomas 	/* has cache valid data? */
1933a86c6181SAlex Tomas 	if (cex->ec_type == EXT4_EXT_CACHE_NO)
19342ec0ae3aSTheodore Ts'o 		goto errout;
1935a86c6181SAlex Tomas 
1936a86c6181SAlex Tomas 	BUG_ON(cex->ec_type != EXT4_EXT_CACHE_GAP &&
1937a86c6181SAlex Tomas 			cex->ec_type != EXT4_EXT_CACHE_EXTENT);
1938a86c6181SAlex Tomas 	if (block >= cex->ec_block && block < cex->ec_block + cex->ec_len) {
1939a86c6181SAlex Tomas 		ex->ee_block = cpu_to_le32(cex->ec_block);
1940f65e6fbaSAlex Tomas 		ext4_ext_store_pblock(ex, cex->ec_start);
1941a86c6181SAlex Tomas 		ex->ee_len = cpu_to_le16(cex->ec_len);
1942bba90743SEric Sandeen 		ext_debug("%u cached by %u:%u:%llu\n",
1943bba90743SEric Sandeen 				block,
1944bba90743SEric Sandeen 				cex->ec_block, cex->ec_len, cex->ec_start);
19452ec0ae3aSTheodore Ts'o 		ret = cex->ec_type;
1946a86c6181SAlex Tomas 	}
19472ec0ae3aSTheodore Ts'o errout:
19482ec0ae3aSTheodore Ts'o 	spin_unlock(&EXT4_I(inode)->i_block_reservation_lock);
19492ec0ae3aSTheodore Ts'o 	return ret;
1950a86c6181SAlex Tomas }
1951a86c6181SAlex Tomas 
1952a86c6181SAlex Tomas /*
1953d0d856e8SRandy Dunlap  * ext4_ext_rm_idx:
1954d0d856e8SRandy Dunlap  * removes index from the index block.
1955d0d856e8SRandy Dunlap  * It's used in truncate case only, thus all requests are for
1956d0d856e8SRandy Dunlap  * last index in the block only.
1957a86c6181SAlex Tomas  */
19581d03ec98SAneesh Kumar K.V static int ext4_ext_rm_idx(handle_t *handle, struct inode *inode,
1959a86c6181SAlex Tomas 			struct ext4_ext_path *path)
1960a86c6181SAlex Tomas {
1961a86c6181SAlex Tomas 	int err;
1962f65e6fbaSAlex Tomas 	ext4_fsblk_t leaf;
1963a86c6181SAlex Tomas 
1964a86c6181SAlex Tomas 	/* free index block */
1965a86c6181SAlex Tomas 	path--;
1966f65e6fbaSAlex Tomas 	leaf = idx_pblock(path->p_idx);
1967a86c6181SAlex Tomas 	BUG_ON(path->p_hdr->eh_entries == 0);
19687e028976SAvantika Mathur 	err = ext4_ext_get_access(handle, inode, path);
19697e028976SAvantika Mathur 	if (err)
1970a86c6181SAlex Tomas 		return err;
1971e8546d06SMarcin Slusarz 	le16_add_cpu(&path->p_hdr->eh_entries, -1);
19727e028976SAvantika Mathur 	err = ext4_ext_dirty(handle, inode, path);
19737e028976SAvantika Mathur 	if (err)
1974a86c6181SAlex Tomas 		return err;
19752ae02107SMingming Cao 	ext_debug("index is empty, remove it, free block %llu\n", leaf);
1976*e6362609STheodore Ts'o 	ext4_free_blocks(handle, inode, 0, leaf, 1,
1977*e6362609STheodore Ts'o 			 EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET);
1978a86c6181SAlex Tomas 	return err;
1979a86c6181SAlex Tomas }
1980a86c6181SAlex Tomas 
1981a86c6181SAlex Tomas /*
1982ee12b630SMingming Cao  * ext4_ext_calc_credits_for_single_extent:
1983ee12b630SMingming Cao  * This routine returns max. credits that needed to insert an extent
1984ee12b630SMingming Cao  * to the extent tree.
1985ee12b630SMingming Cao  * When pass the actual path, the caller should calculate credits
1986ee12b630SMingming Cao  * under i_data_sem.
1987a86c6181SAlex Tomas  */
1988525f4ed8SMingming Cao int ext4_ext_calc_credits_for_single_extent(struct inode *inode, int nrblocks,
1989a86c6181SAlex Tomas 						struct ext4_ext_path *path)
1990a86c6181SAlex Tomas {
1991a86c6181SAlex Tomas 	if (path) {
1992ee12b630SMingming Cao 		int depth = ext_depth(inode);
1993f3bd1f3fSMingming Cao 		int ret = 0;
1994ee12b630SMingming Cao 
1995a86c6181SAlex Tomas 		/* probably there is space in leaf? */
1996a86c6181SAlex Tomas 		if (le16_to_cpu(path[depth].p_hdr->eh_entries)
1997ee12b630SMingming Cao 				< le16_to_cpu(path[depth].p_hdr->eh_max)) {
1998ee12b630SMingming Cao 
1999ee12b630SMingming Cao 			/*
2000ee12b630SMingming Cao 			 *  There are some space in the leaf tree, no
2001ee12b630SMingming Cao 			 *  need to account for leaf block credit
2002ee12b630SMingming Cao 			 *
2003ee12b630SMingming Cao 			 *  bitmaps and block group descriptor blocks
2004ee12b630SMingming Cao 			 *  and other metadat blocks still need to be
2005ee12b630SMingming Cao 			 *  accounted.
2006ee12b630SMingming Cao 			 */
2007525f4ed8SMingming Cao 			/* 1 bitmap, 1 block group descriptor */
2008ee12b630SMingming Cao 			ret = 2 + EXT4_META_TRANS_BLOCKS(inode->i_sb);
20095887e98bSAneesh Kumar K.V 			return ret;
2010ee12b630SMingming Cao 		}
2011ee12b630SMingming Cao 	}
2012ee12b630SMingming Cao 
2013525f4ed8SMingming Cao 	return ext4_chunk_trans_blocks(inode, nrblocks);
2014a86c6181SAlex Tomas }
2015a86c6181SAlex Tomas 
2016a86c6181SAlex Tomas /*
2017ee12b630SMingming Cao  * How many index/leaf blocks need to change/allocate to modify nrblocks?
2018ee12b630SMingming Cao  *
2019ee12b630SMingming Cao  * if nrblocks are fit in a single extent (chunk flag is 1), then
2020ee12b630SMingming Cao  * in the worse case, each tree level index/leaf need to be changed
2021ee12b630SMingming Cao  * if the tree split due to insert a new extent, then the old tree
2022ee12b630SMingming Cao  * index/leaf need to be updated too
2023ee12b630SMingming Cao  *
2024ee12b630SMingming Cao  * If the nrblocks are discontiguous, they could cause
2025ee12b630SMingming Cao  * the whole tree split more than once, but this is really rare.
2026a86c6181SAlex Tomas  */
2027525f4ed8SMingming Cao int ext4_ext_index_trans_blocks(struct inode *inode, int nrblocks, int chunk)
2028ee12b630SMingming Cao {
2029ee12b630SMingming Cao 	int index;
2030ee12b630SMingming Cao 	int depth = ext_depth(inode);
2031a86c6181SAlex Tomas 
2032ee12b630SMingming Cao 	if (chunk)
2033ee12b630SMingming Cao 		index = depth * 2;
2034ee12b630SMingming Cao 	else
2035ee12b630SMingming Cao 		index = depth * 3;
2036a86c6181SAlex Tomas 
2037ee12b630SMingming Cao 	return index;
2038a86c6181SAlex Tomas }
2039a86c6181SAlex Tomas 
2040a86c6181SAlex Tomas static int ext4_remove_blocks(handle_t *handle, struct inode *inode,
2041a86c6181SAlex Tomas 				struct ext4_extent *ex,
2042725d26d3SAneesh Kumar K.V 				ext4_lblk_t from, ext4_lblk_t to)
2043a86c6181SAlex Tomas {
2044a2df2a63SAmit Arora 	unsigned short ee_len =  ext4_ext_get_actual_len(ex);
2045*e6362609STheodore Ts'o 	int flags = EXT4_FREE_BLOCKS_FORGET;
2046a86c6181SAlex Tomas 
2047c9de560dSAlex Tomas 	if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode))
2048*e6362609STheodore Ts'o 		flags |= EXT4_FREE_BLOCKS_METADATA;
2049a86c6181SAlex Tomas #ifdef EXTENTS_STATS
2050a86c6181SAlex Tomas 	{
2051a86c6181SAlex Tomas 		struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2052a86c6181SAlex Tomas 		spin_lock(&sbi->s_ext_stats_lock);
2053a86c6181SAlex Tomas 		sbi->s_ext_blocks += ee_len;
2054a86c6181SAlex Tomas 		sbi->s_ext_extents++;
2055a86c6181SAlex Tomas 		if (ee_len < sbi->s_ext_min)
2056a86c6181SAlex Tomas 			sbi->s_ext_min = ee_len;
2057a86c6181SAlex Tomas 		if (ee_len > sbi->s_ext_max)
2058a86c6181SAlex Tomas 			sbi->s_ext_max = ee_len;
2059a86c6181SAlex Tomas 		if (ext_depth(inode) > sbi->s_depth_max)
2060a86c6181SAlex Tomas 			sbi->s_depth_max = ext_depth(inode);
2061a86c6181SAlex Tomas 		spin_unlock(&sbi->s_ext_stats_lock);
2062a86c6181SAlex Tomas 	}
2063a86c6181SAlex Tomas #endif
2064a86c6181SAlex Tomas 	if (from >= le32_to_cpu(ex->ee_block)
2065a2df2a63SAmit Arora 	    && to == le32_to_cpu(ex->ee_block) + ee_len - 1) {
2066a86c6181SAlex Tomas 		/* tail removal */
2067725d26d3SAneesh Kumar K.V 		ext4_lblk_t num;
2068f65e6fbaSAlex Tomas 		ext4_fsblk_t start;
2069725d26d3SAneesh Kumar K.V 
2070a2df2a63SAmit Arora 		num = le32_to_cpu(ex->ee_block) + ee_len - from;
2071a2df2a63SAmit Arora 		start = ext_pblock(ex) + ee_len - num;
2072725d26d3SAneesh Kumar K.V 		ext_debug("free last %u blocks starting %llu\n", num, start);
2073*e6362609STheodore Ts'o 		ext4_free_blocks(handle, inode, 0, start, num, flags);
2074a86c6181SAlex Tomas 	} else if (from == le32_to_cpu(ex->ee_block)
2075a2df2a63SAmit Arora 		   && to <= le32_to_cpu(ex->ee_block) + ee_len - 1) {
2076725d26d3SAneesh Kumar K.V 		printk(KERN_INFO "strange request: removal %u-%u from %u:%u\n",
2077a2df2a63SAmit Arora 			from, to, le32_to_cpu(ex->ee_block), ee_len);
2078a86c6181SAlex Tomas 	} else {
2079725d26d3SAneesh Kumar K.V 		printk(KERN_INFO "strange request: removal(2) "
2080725d26d3SAneesh Kumar K.V 				"%u-%u from %u:%u\n",
2081a2df2a63SAmit Arora 				from, to, le32_to_cpu(ex->ee_block), ee_len);
2082a86c6181SAlex Tomas 	}
2083a86c6181SAlex Tomas 	return 0;
2084a86c6181SAlex Tomas }
2085a86c6181SAlex Tomas 
2086a86c6181SAlex Tomas static int
2087a86c6181SAlex Tomas ext4_ext_rm_leaf(handle_t *handle, struct inode *inode,
2088725d26d3SAneesh Kumar K.V 		struct ext4_ext_path *path, ext4_lblk_t start)
2089a86c6181SAlex Tomas {
2090a86c6181SAlex Tomas 	int err = 0, correct_index = 0;
2091a86c6181SAlex Tomas 	int depth = ext_depth(inode), credits;
2092a86c6181SAlex Tomas 	struct ext4_extent_header *eh;
2093725d26d3SAneesh Kumar K.V 	ext4_lblk_t a, b, block;
2094725d26d3SAneesh Kumar K.V 	unsigned num;
2095725d26d3SAneesh Kumar K.V 	ext4_lblk_t ex_ee_block;
2096a86c6181SAlex Tomas 	unsigned short ex_ee_len;
2097a2df2a63SAmit Arora 	unsigned uninitialized = 0;
2098a86c6181SAlex Tomas 	struct ext4_extent *ex;
2099a86c6181SAlex Tomas 
2100c29c0ae7SAlex Tomas 	/* the header must be checked already in ext4_ext_remove_space() */
2101725d26d3SAneesh Kumar K.V 	ext_debug("truncate since %u in leaf\n", start);
2102a86c6181SAlex Tomas 	if (!path[depth].p_hdr)
2103a86c6181SAlex Tomas 		path[depth].p_hdr = ext_block_hdr(path[depth].p_bh);
2104a86c6181SAlex Tomas 	eh = path[depth].p_hdr;
2105a86c6181SAlex Tomas 	BUG_ON(eh == NULL);
2106a86c6181SAlex Tomas 
2107a86c6181SAlex Tomas 	/* find where to start removing */
2108a86c6181SAlex Tomas 	ex = EXT_LAST_EXTENT(eh);
2109a86c6181SAlex Tomas 
2110a86c6181SAlex Tomas 	ex_ee_block = le32_to_cpu(ex->ee_block);
2111a2df2a63SAmit Arora 	ex_ee_len = ext4_ext_get_actual_len(ex);
2112a86c6181SAlex Tomas 
2113a86c6181SAlex Tomas 	while (ex >= EXT_FIRST_EXTENT(eh) &&
2114a86c6181SAlex Tomas 			ex_ee_block + ex_ee_len > start) {
2115a41f2071SAneesh Kumar K.V 
2116a41f2071SAneesh Kumar K.V 		if (ext4_ext_is_uninitialized(ex))
2117a41f2071SAneesh Kumar K.V 			uninitialized = 1;
2118a41f2071SAneesh Kumar K.V 		else
2119a41f2071SAneesh Kumar K.V 			uninitialized = 0;
2120a41f2071SAneesh Kumar K.V 
2121553f9008SMingming 		ext_debug("remove ext %u:[%d]%d\n", ex_ee_block,
2122553f9008SMingming 			 uninitialized, ex_ee_len);
2123a86c6181SAlex Tomas 		path[depth].p_ext = ex;
2124a86c6181SAlex Tomas 
2125a86c6181SAlex Tomas 		a = ex_ee_block > start ? ex_ee_block : start;
2126a86c6181SAlex Tomas 		b = ex_ee_block + ex_ee_len - 1 < EXT_MAX_BLOCK ?
2127a86c6181SAlex Tomas 			ex_ee_block + ex_ee_len - 1 : EXT_MAX_BLOCK;
2128a86c6181SAlex Tomas 
2129a86c6181SAlex Tomas 		ext_debug("  border %u:%u\n", a, b);
2130a86c6181SAlex Tomas 
2131a86c6181SAlex Tomas 		if (a != ex_ee_block && b != ex_ee_block + ex_ee_len - 1) {
2132a86c6181SAlex Tomas 			block = 0;
2133a86c6181SAlex Tomas 			num = 0;
2134a86c6181SAlex Tomas 			BUG();
2135a86c6181SAlex Tomas 		} else if (a != ex_ee_block) {
2136a86c6181SAlex Tomas 			/* remove tail of the extent */
2137a86c6181SAlex Tomas 			block = ex_ee_block;
2138a86c6181SAlex Tomas 			num = a - block;
2139a86c6181SAlex Tomas 		} else if (b != ex_ee_block + ex_ee_len - 1) {
2140a86c6181SAlex Tomas 			/* remove head of the extent */
2141a86c6181SAlex Tomas 			block = a;
2142a86c6181SAlex Tomas 			num = b - a;
2143a86c6181SAlex Tomas 			/* there is no "make a hole" API yet */
2144a86c6181SAlex Tomas 			BUG();
2145a86c6181SAlex Tomas 		} else {
2146a86c6181SAlex Tomas 			/* remove whole extent: excellent! */
2147a86c6181SAlex Tomas 			block = ex_ee_block;
2148a86c6181SAlex Tomas 			num = 0;
2149a86c6181SAlex Tomas 			BUG_ON(a != ex_ee_block);
2150a86c6181SAlex Tomas 			BUG_ON(b != ex_ee_block + ex_ee_len - 1);
2151a86c6181SAlex Tomas 		}
2152a86c6181SAlex Tomas 
215334071da7STheodore Ts'o 		/*
215434071da7STheodore Ts'o 		 * 3 for leaf, sb, and inode plus 2 (bmap and group
215534071da7STheodore Ts'o 		 * descriptor) for each block group; assume two block
215634071da7STheodore Ts'o 		 * groups plus ex_ee_len/blocks_per_block_group for
215734071da7STheodore Ts'o 		 * the worst case
215834071da7STheodore Ts'o 		 */
215934071da7STheodore Ts'o 		credits = 7 + 2*(ex_ee_len/EXT4_BLOCKS_PER_GROUP(inode->i_sb));
2160a86c6181SAlex Tomas 		if (ex == EXT_FIRST_EXTENT(eh)) {
2161a86c6181SAlex Tomas 			correct_index = 1;
2162a86c6181SAlex Tomas 			credits += (ext_depth(inode)) + 1;
2163a86c6181SAlex Tomas 		}
2164a86c6181SAlex Tomas 		credits += 2 * EXT4_QUOTA_TRANS_BLOCKS(inode->i_sb);
2165a86c6181SAlex Tomas 
2166487caeefSJan Kara 		err = ext4_ext_truncate_extend_restart(handle, inode, credits);
21679102e4faSShen Feng 		if (err)
2168a86c6181SAlex Tomas 			goto out;
2169a86c6181SAlex Tomas 
2170a86c6181SAlex Tomas 		err = ext4_ext_get_access(handle, inode, path + depth);
2171a86c6181SAlex Tomas 		if (err)
2172a86c6181SAlex Tomas 			goto out;
2173a86c6181SAlex Tomas 
2174a86c6181SAlex Tomas 		err = ext4_remove_blocks(handle, inode, ex, a, b);
2175a86c6181SAlex Tomas 		if (err)
2176a86c6181SAlex Tomas 			goto out;
2177a86c6181SAlex Tomas 
2178a86c6181SAlex Tomas 		if (num == 0) {
2179d0d856e8SRandy Dunlap 			/* this extent is removed; mark slot entirely unused */
2180f65e6fbaSAlex Tomas 			ext4_ext_store_pblock(ex, 0);
2181e8546d06SMarcin Slusarz 			le16_add_cpu(&eh->eh_entries, -1);
2182a86c6181SAlex Tomas 		}
2183a86c6181SAlex Tomas 
2184a86c6181SAlex Tomas 		ex->ee_block = cpu_to_le32(block);
2185a86c6181SAlex Tomas 		ex->ee_len = cpu_to_le16(num);
2186749269faSAmit Arora 		/*
2187749269faSAmit Arora 		 * Do not mark uninitialized if all the blocks in the
2188749269faSAmit Arora 		 * extent have been removed.
2189749269faSAmit Arora 		 */
2190749269faSAmit Arora 		if (uninitialized && num)
2191a2df2a63SAmit Arora 			ext4_ext_mark_uninitialized(ex);
2192a86c6181SAlex Tomas 
2193a86c6181SAlex Tomas 		err = ext4_ext_dirty(handle, inode, path + depth);
2194a86c6181SAlex Tomas 		if (err)
2195a86c6181SAlex Tomas 			goto out;
2196a86c6181SAlex Tomas 
21972ae02107SMingming Cao 		ext_debug("new extent: %u:%u:%llu\n", block, num,
2198f65e6fbaSAlex Tomas 				ext_pblock(ex));
2199a86c6181SAlex Tomas 		ex--;
2200a86c6181SAlex Tomas 		ex_ee_block = le32_to_cpu(ex->ee_block);
2201a2df2a63SAmit Arora 		ex_ee_len = ext4_ext_get_actual_len(ex);
2202a86c6181SAlex Tomas 	}
2203a86c6181SAlex Tomas 
2204a86c6181SAlex Tomas 	if (correct_index && eh->eh_entries)
2205a86c6181SAlex Tomas 		err = ext4_ext_correct_indexes(handle, inode, path);
2206a86c6181SAlex Tomas 
2207a86c6181SAlex Tomas 	/* if this leaf is free, then we should
2208a86c6181SAlex Tomas 	 * remove it from index block above */
2209a86c6181SAlex Tomas 	if (err == 0 && eh->eh_entries == 0 && path[depth].p_bh != NULL)
2210a86c6181SAlex Tomas 		err = ext4_ext_rm_idx(handle, inode, path + depth);
2211a86c6181SAlex Tomas 
2212a86c6181SAlex Tomas out:
2213a86c6181SAlex Tomas 	return err;
2214a86c6181SAlex Tomas }
2215a86c6181SAlex Tomas 
2216a86c6181SAlex Tomas /*
2217d0d856e8SRandy Dunlap  * ext4_ext_more_to_rm:
2218d0d856e8SRandy Dunlap  * returns 1 if current index has to be freed (even partial)
2219a86c6181SAlex Tomas  */
222009b88252SAvantika Mathur static int
2221a86c6181SAlex Tomas ext4_ext_more_to_rm(struct ext4_ext_path *path)
2222a86c6181SAlex Tomas {
2223a86c6181SAlex Tomas 	BUG_ON(path->p_idx == NULL);
2224a86c6181SAlex Tomas 
2225a86c6181SAlex Tomas 	if (path->p_idx < EXT_FIRST_INDEX(path->p_hdr))
2226a86c6181SAlex Tomas 		return 0;
2227a86c6181SAlex Tomas 
2228a86c6181SAlex Tomas 	/*
2229d0d856e8SRandy Dunlap 	 * if truncate on deeper level happened, it wasn't partial,
2230a86c6181SAlex Tomas 	 * so we have to consider current index for truncation
2231a86c6181SAlex Tomas 	 */
2232a86c6181SAlex Tomas 	if (le16_to_cpu(path->p_hdr->eh_entries) == path->p_block)
2233a86c6181SAlex Tomas 		return 0;
2234a86c6181SAlex Tomas 	return 1;
2235a86c6181SAlex Tomas }
2236a86c6181SAlex Tomas 
22371d03ec98SAneesh Kumar K.V static int ext4_ext_remove_space(struct inode *inode, ext4_lblk_t start)
2238a86c6181SAlex Tomas {
2239a86c6181SAlex Tomas 	struct super_block *sb = inode->i_sb;
2240a86c6181SAlex Tomas 	int depth = ext_depth(inode);
2241a86c6181SAlex Tomas 	struct ext4_ext_path *path;
2242a86c6181SAlex Tomas 	handle_t *handle;
2243a86c6181SAlex Tomas 	int i = 0, err = 0;
2244a86c6181SAlex Tomas 
2245725d26d3SAneesh Kumar K.V 	ext_debug("truncate since %u\n", start);
2246a86c6181SAlex Tomas 
2247a86c6181SAlex Tomas 	/* probably first extent we're gonna free will be last in block */
2248a86c6181SAlex Tomas 	handle = ext4_journal_start(inode, depth + 1);
2249a86c6181SAlex Tomas 	if (IS_ERR(handle))
2250a86c6181SAlex Tomas 		return PTR_ERR(handle);
2251a86c6181SAlex Tomas 
2252a86c6181SAlex Tomas 	ext4_ext_invalidate_cache(inode);
2253a86c6181SAlex Tomas 
2254a86c6181SAlex Tomas 	/*
2255d0d856e8SRandy Dunlap 	 * We start scanning from right side, freeing all the blocks
2256d0d856e8SRandy Dunlap 	 * after i_size and walking into the tree depth-wise.
2257a86c6181SAlex Tomas 	 */
2258216553c4SJosef Bacik 	path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 1), GFP_NOFS);
2259a86c6181SAlex Tomas 	if (path == NULL) {
2260a86c6181SAlex Tomas 		ext4_journal_stop(handle);
2261a86c6181SAlex Tomas 		return -ENOMEM;
2262a86c6181SAlex Tomas 	}
2263a86c6181SAlex Tomas 	path[0].p_hdr = ext_inode_hdr(inode);
226456b19868SAneesh Kumar K.V 	if (ext4_ext_check(inode, path[0].p_hdr, depth)) {
2265a86c6181SAlex Tomas 		err = -EIO;
2266a86c6181SAlex Tomas 		goto out;
2267a86c6181SAlex Tomas 	}
2268a86c6181SAlex Tomas 	path[0].p_depth = depth;
2269a86c6181SAlex Tomas 
2270a86c6181SAlex Tomas 	while (i >= 0 && err == 0) {
2271a86c6181SAlex Tomas 		if (i == depth) {
2272a86c6181SAlex Tomas 			/* this is leaf block */
2273a86c6181SAlex Tomas 			err = ext4_ext_rm_leaf(handle, inode, path, start);
2274d0d856e8SRandy Dunlap 			/* root level has p_bh == NULL, brelse() eats this */
2275a86c6181SAlex Tomas 			brelse(path[i].p_bh);
2276a86c6181SAlex Tomas 			path[i].p_bh = NULL;
2277a86c6181SAlex Tomas 			i--;
2278a86c6181SAlex Tomas 			continue;
2279a86c6181SAlex Tomas 		}
2280a86c6181SAlex Tomas 
2281a86c6181SAlex Tomas 		/* this is index block */
2282a86c6181SAlex Tomas 		if (!path[i].p_hdr) {
2283a86c6181SAlex Tomas 			ext_debug("initialize header\n");
2284a86c6181SAlex Tomas 			path[i].p_hdr = ext_block_hdr(path[i].p_bh);
2285a86c6181SAlex Tomas 		}
2286a86c6181SAlex Tomas 
2287a86c6181SAlex Tomas 		if (!path[i].p_idx) {
2288d0d856e8SRandy Dunlap 			/* this level hasn't been touched yet */
2289a86c6181SAlex Tomas 			path[i].p_idx = EXT_LAST_INDEX(path[i].p_hdr);
2290a86c6181SAlex Tomas 			path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries)+1;
2291a86c6181SAlex Tomas 			ext_debug("init index ptr: hdr 0x%p, num %d\n",
2292a86c6181SAlex Tomas 				  path[i].p_hdr,
2293a86c6181SAlex Tomas 				  le16_to_cpu(path[i].p_hdr->eh_entries));
2294a86c6181SAlex Tomas 		} else {
2295d0d856e8SRandy Dunlap 			/* we were already here, see at next index */
2296a86c6181SAlex Tomas 			path[i].p_idx--;
2297a86c6181SAlex Tomas 		}
2298a86c6181SAlex Tomas 
2299a86c6181SAlex Tomas 		ext_debug("level %d - index, first 0x%p, cur 0x%p\n",
2300a86c6181SAlex Tomas 				i, EXT_FIRST_INDEX(path[i].p_hdr),
2301a86c6181SAlex Tomas 				path[i].p_idx);
2302a86c6181SAlex Tomas 		if (ext4_ext_more_to_rm(path + i)) {
2303c29c0ae7SAlex Tomas 			struct buffer_head *bh;
2304a86c6181SAlex Tomas 			/* go to the next level */
23052ae02107SMingming Cao 			ext_debug("move to level %d (block %llu)\n",
2306f65e6fbaSAlex Tomas 				  i + 1, idx_pblock(path[i].p_idx));
2307a86c6181SAlex Tomas 			memset(path + i + 1, 0, sizeof(*path));
2308c29c0ae7SAlex Tomas 			bh = sb_bread(sb, idx_pblock(path[i].p_idx));
2309c29c0ae7SAlex Tomas 			if (!bh) {
2310a86c6181SAlex Tomas 				/* should we reset i_size? */
2311a86c6181SAlex Tomas 				err = -EIO;
2312a86c6181SAlex Tomas 				break;
2313a86c6181SAlex Tomas 			}
2314c29c0ae7SAlex Tomas 			if (WARN_ON(i + 1 > depth)) {
2315c29c0ae7SAlex Tomas 				err = -EIO;
2316c29c0ae7SAlex Tomas 				break;
2317c29c0ae7SAlex Tomas 			}
231856b19868SAneesh Kumar K.V 			if (ext4_ext_check(inode, ext_block_hdr(bh),
2319c29c0ae7SAlex Tomas 							depth - i - 1)) {
2320c29c0ae7SAlex Tomas 				err = -EIO;
2321c29c0ae7SAlex Tomas 				break;
2322c29c0ae7SAlex Tomas 			}
2323c29c0ae7SAlex Tomas 			path[i + 1].p_bh = bh;
2324a86c6181SAlex Tomas 
2325d0d856e8SRandy Dunlap 			/* save actual number of indexes since this
2326d0d856e8SRandy Dunlap 			 * number is changed at the next iteration */
2327a86c6181SAlex Tomas 			path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries);
2328a86c6181SAlex Tomas 			i++;
2329a86c6181SAlex Tomas 		} else {
2330d0d856e8SRandy Dunlap 			/* we finished processing this index, go up */
2331a86c6181SAlex Tomas 			if (path[i].p_hdr->eh_entries == 0 && i > 0) {
2332d0d856e8SRandy Dunlap 				/* index is empty, remove it;
2333a86c6181SAlex Tomas 				 * handle must be already prepared by the
2334a86c6181SAlex Tomas 				 * truncatei_leaf() */
2335a86c6181SAlex Tomas 				err = ext4_ext_rm_idx(handle, inode, path + i);
2336a86c6181SAlex Tomas 			}
2337d0d856e8SRandy Dunlap 			/* root level has p_bh == NULL, brelse() eats this */
2338a86c6181SAlex Tomas 			brelse(path[i].p_bh);
2339a86c6181SAlex Tomas 			path[i].p_bh = NULL;
2340a86c6181SAlex Tomas 			i--;
2341a86c6181SAlex Tomas 			ext_debug("return to level %d\n", i);
2342a86c6181SAlex Tomas 		}
2343a86c6181SAlex Tomas 	}
2344a86c6181SAlex Tomas 
2345a86c6181SAlex Tomas 	/* TODO: flexible tree reduction should be here */
2346a86c6181SAlex Tomas 	if (path->p_hdr->eh_entries == 0) {
2347a86c6181SAlex Tomas 		/*
2348d0d856e8SRandy Dunlap 		 * truncate to zero freed all the tree,
2349d0d856e8SRandy Dunlap 		 * so we need to correct eh_depth
2350a86c6181SAlex Tomas 		 */
2351a86c6181SAlex Tomas 		err = ext4_ext_get_access(handle, inode, path);
2352a86c6181SAlex Tomas 		if (err == 0) {
2353a86c6181SAlex Tomas 			ext_inode_hdr(inode)->eh_depth = 0;
2354a86c6181SAlex Tomas 			ext_inode_hdr(inode)->eh_max =
235555ad63bfSTheodore Ts'o 				cpu_to_le16(ext4_ext_space_root(inode, 0));
2356a86c6181SAlex Tomas 			err = ext4_ext_dirty(handle, inode, path);
2357a86c6181SAlex Tomas 		}
2358a86c6181SAlex Tomas 	}
2359a86c6181SAlex Tomas out:
2360a86c6181SAlex Tomas 	ext4_ext_drop_refs(path);
2361a86c6181SAlex Tomas 	kfree(path);
2362a86c6181SAlex Tomas 	ext4_journal_stop(handle);
2363a86c6181SAlex Tomas 
2364a86c6181SAlex Tomas 	return err;
2365a86c6181SAlex Tomas }
2366a86c6181SAlex Tomas 
2367a86c6181SAlex Tomas /*
2368a86c6181SAlex Tomas  * called at mount time
2369a86c6181SAlex Tomas  */
2370a86c6181SAlex Tomas void ext4_ext_init(struct super_block *sb)
2371a86c6181SAlex Tomas {
2372a86c6181SAlex Tomas 	/*
2373a86c6181SAlex Tomas 	 * possible initialization would be here
2374a86c6181SAlex Tomas 	 */
2375a86c6181SAlex Tomas 
237683982b6fSTheodore Ts'o 	if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS)) {
237790576c0bSTheodore Ts'o #if defined(AGGRESSIVE_TEST) || defined(CHECK_BINSEARCH) || defined(EXTENTS_STATS)
23784776004fSTheodore Ts'o 		printk(KERN_INFO "EXT4-fs: file extents enabled");
2379bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST
2380bbf2f9fbSRobert P. J. Day 		printk(", aggressive tests");
2381a86c6181SAlex Tomas #endif
2382a86c6181SAlex Tomas #ifdef CHECK_BINSEARCH
2383a86c6181SAlex Tomas 		printk(", check binsearch");
2384a86c6181SAlex Tomas #endif
2385a86c6181SAlex Tomas #ifdef EXTENTS_STATS
2386a86c6181SAlex Tomas 		printk(", stats");
2387a86c6181SAlex Tomas #endif
2388a86c6181SAlex Tomas 		printk("\n");
238990576c0bSTheodore Ts'o #endif
2390a86c6181SAlex Tomas #ifdef EXTENTS_STATS
2391a86c6181SAlex Tomas 		spin_lock_init(&EXT4_SB(sb)->s_ext_stats_lock);
2392a86c6181SAlex Tomas 		EXT4_SB(sb)->s_ext_min = 1 << 30;
2393a86c6181SAlex Tomas 		EXT4_SB(sb)->s_ext_max = 0;
2394a86c6181SAlex Tomas #endif
2395a86c6181SAlex Tomas 	}
2396a86c6181SAlex Tomas }
2397a86c6181SAlex Tomas 
2398a86c6181SAlex Tomas /*
2399a86c6181SAlex Tomas  * called at umount time
2400a86c6181SAlex Tomas  */
2401a86c6181SAlex Tomas void ext4_ext_release(struct super_block *sb)
2402a86c6181SAlex Tomas {
240383982b6fSTheodore Ts'o 	if (!EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS))
2404a86c6181SAlex Tomas 		return;
2405a86c6181SAlex Tomas 
2406a86c6181SAlex Tomas #ifdef EXTENTS_STATS
2407a86c6181SAlex Tomas 	if (EXT4_SB(sb)->s_ext_blocks && EXT4_SB(sb)->s_ext_extents) {
2408a86c6181SAlex Tomas 		struct ext4_sb_info *sbi = EXT4_SB(sb);
2409a86c6181SAlex Tomas 		printk(KERN_ERR "EXT4-fs: %lu blocks in %lu extents (%lu ave)\n",
2410a86c6181SAlex Tomas 			sbi->s_ext_blocks, sbi->s_ext_extents,
2411a86c6181SAlex Tomas 			sbi->s_ext_blocks / sbi->s_ext_extents);
2412a86c6181SAlex Tomas 		printk(KERN_ERR "EXT4-fs: extents: %lu min, %lu max, max depth %lu\n",
2413a86c6181SAlex Tomas 			sbi->s_ext_min, sbi->s_ext_max, sbi->s_depth_max);
2414a86c6181SAlex Tomas 	}
2415a86c6181SAlex Tomas #endif
2416a86c6181SAlex Tomas }
2417a86c6181SAlex Tomas 
2418093a088bSAneesh Kumar K.V static void bi_complete(struct bio *bio, int error)
2419093a088bSAneesh Kumar K.V {
2420093a088bSAneesh Kumar K.V 	complete((struct completion *)bio->bi_private);
2421093a088bSAneesh Kumar K.V }
2422093a088bSAneesh Kumar K.V 
2423093a088bSAneesh Kumar K.V /* FIXME!! we need to try to merge to left or right after zero-out  */
2424093a088bSAneesh Kumar K.V static int ext4_ext_zeroout(struct inode *inode, struct ext4_extent *ex)
2425093a088bSAneesh Kumar K.V {
2426093a088bSAneesh Kumar K.V 	int ret = -EIO;
2427093a088bSAneesh Kumar K.V 	struct bio *bio;
2428093a088bSAneesh Kumar K.V 	int blkbits, blocksize;
2429093a088bSAneesh Kumar K.V 	sector_t ee_pblock;
2430093a088bSAneesh Kumar K.V 	struct completion event;
2431093a088bSAneesh Kumar K.V 	unsigned int ee_len, len, done, offset;
2432093a088bSAneesh Kumar K.V 
2433093a088bSAneesh Kumar K.V 
2434093a088bSAneesh Kumar K.V 	blkbits   = inode->i_blkbits;
2435093a088bSAneesh Kumar K.V 	blocksize = inode->i_sb->s_blocksize;
2436093a088bSAneesh Kumar K.V 	ee_len    = ext4_ext_get_actual_len(ex);
2437093a088bSAneesh Kumar K.V 	ee_pblock = ext_pblock(ex);
2438093a088bSAneesh Kumar K.V 
2439093a088bSAneesh Kumar K.V 	/* convert ee_pblock to 512 byte sectors */
2440093a088bSAneesh Kumar K.V 	ee_pblock = ee_pblock << (blkbits - 9);
2441093a088bSAneesh Kumar K.V 
2442093a088bSAneesh Kumar K.V 	while (ee_len > 0) {
2443093a088bSAneesh Kumar K.V 
2444093a088bSAneesh Kumar K.V 		if (ee_len > BIO_MAX_PAGES)
2445093a088bSAneesh Kumar K.V 			len = BIO_MAX_PAGES;
2446093a088bSAneesh Kumar K.V 		else
2447093a088bSAneesh Kumar K.V 			len = ee_len;
2448093a088bSAneesh Kumar K.V 
2449093a088bSAneesh Kumar K.V 		bio = bio_alloc(GFP_NOIO, len);
2450093a088bSAneesh Kumar K.V 		bio->bi_sector = ee_pblock;
2451093a088bSAneesh Kumar K.V 		bio->bi_bdev   = inode->i_sb->s_bdev;
2452093a088bSAneesh Kumar K.V 
2453093a088bSAneesh Kumar K.V 		done = 0;
2454093a088bSAneesh Kumar K.V 		offset = 0;
2455093a088bSAneesh Kumar K.V 		while (done < len) {
2456093a088bSAneesh Kumar K.V 			ret = bio_add_page(bio, ZERO_PAGE(0),
2457093a088bSAneesh Kumar K.V 							blocksize, offset);
2458093a088bSAneesh Kumar K.V 			if (ret != blocksize) {
2459093a088bSAneesh Kumar K.V 				/*
2460093a088bSAneesh Kumar K.V 				 * We can't add any more pages because of
2461093a088bSAneesh Kumar K.V 				 * hardware limitations.  Start a new bio.
2462093a088bSAneesh Kumar K.V 				 */
2463093a088bSAneesh Kumar K.V 				break;
2464093a088bSAneesh Kumar K.V 			}
2465093a088bSAneesh Kumar K.V 			done++;
2466093a088bSAneesh Kumar K.V 			offset += blocksize;
2467093a088bSAneesh Kumar K.V 			if (offset >= PAGE_CACHE_SIZE)
2468093a088bSAneesh Kumar K.V 				offset = 0;
2469093a088bSAneesh Kumar K.V 		}
2470093a088bSAneesh Kumar K.V 
2471093a088bSAneesh Kumar K.V 		init_completion(&event);
2472093a088bSAneesh Kumar K.V 		bio->bi_private = &event;
2473093a088bSAneesh Kumar K.V 		bio->bi_end_io = bi_complete;
2474093a088bSAneesh Kumar K.V 		submit_bio(WRITE, bio);
2475093a088bSAneesh Kumar K.V 		wait_for_completion(&event);
2476093a088bSAneesh Kumar K.V 
2477093a088bSAneesh Kumar K.V 		if (test_bit(BIO_UPTODATE, &bio->bi_flags))
2478093a088bSAneesh Kumar K.V 			ret = 0;
2479093a088bSAneesh Kumar K.V 		else {
2480093a088bSAneesh Kumar K.V 			ret = -EIO;
2481093a088bSAneesh Kumar K.V 			break;
2482093a088bSAneesh Kumar K.V 		}
2483093a088bSAneesh Kumar K.V 		bio_put(bio);
2484093a088bSAneesh Kumar K.V 		ee_len    -= done;
2485093a088bSAneesh Kumar K.V 		ee_pblock += done  << (blkbits - 9);
2486093a088bSAneesh Kumar K.V 	}
2487093a088bSAneesh Kumar K.V 	return ret;
2488093a088bSAneesh Kumar K.V }
2489093a088bSAneesh Kumar K.V 
24903977c965SAneesh Kumar K.V #define EXT4_EXT_ZERO_LEN 7
249156055d3aSAmit Arora /*
249256055d3aSAmit Arora  * This function is called by ext4_ext_get_blocks() if someone tries to write
249356055d3aSAmit Arora  * to an uninitialized extent. It may result in splitting the uninitialized
249456055d3aSAmit Arora  * extent into multiple extents (upto three - one initialized and two
249556055d3aSAmit Arora  * uninitialized).
249656055d3aSAmit Arora  * There are three possibilities:
249756055d3aSAmit Arora  *   a> There is no split required: Entire extent should be initialized
249856055d3aSAmit Arora  *   b> Splits in two extents: Write is happening at either end of the extent
249956055d3aSAmit Arora  *   c> Splits in three extents: Somone is writing in middle of the extent
250056055d3aSAmit Arora  */
2501725d26d3SAneesh Kumar K.V static int ext4_ext_convert_to_initialized(handle_t *handle,
2502725d26d3SAneesh Kumar K.V 						struct inode *inode,
250356055d3aSAmit Arora 						struct ext4_ext_path *path,
2504725d26d3SAneesh Kumar K.V 						ext4_lblk_t iblock,
2505498e5f24STheodore Ts'o 						unsigned int max_blocks)
250656055d3aSAmit Arora {
250795c3889cSAneesh Kumar K.V 	struct ext4_extent *ex, newex, orig_ex;
250856055d3aSAmit Arora 	struct ext4_extent *ex1 = NULL;
250956055d3aSAmit Arora 	struct ext4_extent *ex2 = NULL;
251056055d3aSAmit Arora 	struct ext4_extent *ex3 = NULL;
251156055d3aSAmit Arora 	struct ext4_extent_header *eh;
2512725d26d3SAneesh Kumar K.V 	ext4_lblk_t ee_block;
2513725d26d3SAneesh Kumar K.V 	unsigned int allocated, ee_len, depth;
251456055d3aSAmit Arora 	ext4_fsblk_t newblock;
251556055d3aSAmit Arora 	int err = 0;
251656055d3aSAmit Arora 	int ret = 0;
251756055d3aSAmit Arora 
251856055d3aSAmit Arora 	depth = ext_depth(inode);
251956055d3aSAmit Arora 	eh = path[depth].p_hdr;
252056055d3aSAmit Arora 	ex = path[depth].p_ext;
252156055d3aSAmit Arora 	ee_block = le32_to_cpu(ex->ee_block);
252256055d3aSAmit Arora 	ee_len = ext4_ext_get_actual_len(ex);
252356055d3aSAmit Arora 	allocated = ee_len - (iblock - ee_block);
252456055d3aSAmit Arora 	newblock = iblock - ee_block + ext_pblock(ex);
252556055d3aSAmit Arora 	ex2 = ex;
252695c3889cSAneesh Kumar K.V 	orig_ex.ee_block = ex->ee_block;
252795c3889cSAneesh Kumar K.V 	orig_ex.ee_len   = cpu_to_le16(ee_len);
252895c3889cSAneesh Kumar K.V 	ext4_ext_store_pblock(&orig_ex, ext_pblock(ex));
252956055d3aSAmit Arora 
25309df5643aSAneesh Kumar K.V 	err = ext4_ext_get_access(handle, inode, path + depth);
25319df5643aSAneesh Kumar K.V 	if (err)
25329df5643aSAneesh Kumar K.V 		goto out;
25333977c965SAneesh Kumar K.V 	/* If extent has less than 2*EXT4_EXT_ZERO_LEN zerout directly */
25343977c965SAneesh Kumar K.V 	if (ee_len <= 2*EXT4_EXT_ZERO_LEN) {
25353977c965SAneesh Kumar K.V 		err =  ext4_ext_zeroout(inode, &orig_ex);
25363977c965SAneesh Kumar K.V 		if (err)
25373977c965SAneesh Kumar K.V 			goto fix_extent_len;
25383977c965SAneesh Kumar K.V 		/* update the extent length and mark as initialized */
25393977c965SAneesh Kumar K.V 		ex->ee_block = orig_ex.ee_block;
25403977c965SAneesh Kumar K.V 		ex->ee_len   = orig_ex.ee_len;
25413977c965SAneesh Kumar K.V 		ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
25423977c965SAneesh Kumar K.V 		ext4_ext_dirty(handle, inode, path + depth);
2543161e7b7cSAneesh Kumar K.V 		/* zeroed the full extent */
2544161e7b7cSAneesh Kumar K.V 		return allocated;
25453977c965SAneesh Kumar K.V 	}
25469df5643aSAneesh Kumar K.V 
254756055d3aSAmit Arora 	/* ex1: ee_block to iblock - 1 : uninitialized */
254856055d3aSAmit Arora 	if (iblock > ee_block) {
254956055d3aSAmit Arora 		ex1 = ex;
255056055d3aSAmit Arora 		ex1->ee_len = cpu_to_le16(iblock - ee_block);
255156055d3aSAmit Arora 		ext4_ext_mark_uninitialized(ex1);
255256055d3aSAmit Arora 		ex2 = &newex;
255356055d3aSAmit Arora 	}
255456055d3aSAmit Arora 	/*
255556055d3aSAmit Arora 	 * for sanity, update the length of the ex2 extent before
255656055d3aSAmit Arora 	 * we insert ex3, if ex1 is NULL. This is to avoid temporary
255756055d3aSAmit Arora 	 * overlap of blocks.
255856055d3aSAmit Arora 	 */
255956055d3aSAmit Arora 	if (!ex1 && allocated > max_blocks)
256056055d3aSAmit Arora 		ex2->ee_len = cpu_to_le16(max_blocks);
256156055d3aSAmit Arora 	/* ex3: to ee_block + ee_len : uninitialised */
256256055d3aSAmit Arora 	if (allocated > max_blocks) {
256356055d3aSAmit Arora 		unsigned int newdepth;
25643977c965SAneesh Kumar K.V 		/* If extent has less than EXT4_EXT_ZERO_LEN zerout directly */
25653977c965SAneesh Kumar K.V 		if (allocated <= EXT4_EXT_ZERO_LEN) {
2566d03856bdSAneesh Kumar K.V 			/*
2567d03856bdSAneesh Kumar K.V 			 * iblock == ee_block is handled by the zerouout
2568d03856bdSAneesh Kumar K.V 			 * at the beginning.
2569d03856bdSAneesh Kumar K.V 			 * Mark first half uninitialized.
25703977c965SAneesh Kumar K.V 			 * Mark second half initialized and zero out the
25713977c965SAneesh Kumar K.V 			 * initialized extent
25723977c965SAneesh Kumar K.V 			 */
25733977c965SAneesh Kumar K.V 			ex->ee_block = orig_ex.ee_block;
25743977c965SAneesh Kumar K.V 			ex->ee_len   = cpu_to_le16(ee_len - allocated);
25753977c965SAneesh Kumar K.V 			ext4_ext_mark_uninitialized(ex);
25763977c965SAneesh Kumar K.V 			ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
25773977c965SAneesh Kumar K.V 			ext4_ext_dirty(handle, inode, path + depth);
25783977c965SAneesh Kumar K.V 
25793977c965SAneesh Kumar K.V 			ex3 = &newex;
25803977c965SAneesh Kumar K.V 			ex3->ee_block = cpu_to_le32(iblock);
25813977c965SAneesh Kumar K.V 			ext4_ext_store_pblock(ex3, newblock);
25823977c965SAneesh Kumar K.V 			ex3->ee_len = cpu_to_le16(allocated);
25830031462bSMingming Cao 			err = ext4_ext_insert_extent(handle, inode, path,
25840031462bSMingming Cao 							ex3, 0);
25853977c965SAneesh Kumar K.V 			if (err == -ENOSPC) {
25863977c965SAneesh Kumar K.V 				err =  ext4_ext_zeroout(inode, &orig_ex);
25873977c965SAneesh Kumar K.V 				if (err)
25883977c965SAneesh Kumar K.V 					goto fix_extent_len;
25893977c965SAneesh Kumar K.V 				ex->ee_block = orig_ex.ee_block;
25903977c965SAneesh Kumar K.V 				ex->ee_len   = orig_ex.ee_len;
25913977c965SAneesh Kumar K.V 				ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
25923977c965SAneesh Kumar K.V 				ext4_ext_dirty(handle, inode, path + depth);
2593d03856bdSAneesh Kumar K.V 				/* blocks available from iblock */
2594161e7b7cSAneesh Kumar K.V 				return allocated;
25953977c965SAneesh Kumar K.V 
25963977c965SAneesh Kumar K.V 			} else if (err)
25973977c965SAneesh Kumar K.V 				goto fix_extent_len;
25983977c965SAneesh Kumar K.V 
2599161e7b7cSAneesh Kumar K.V 			/*
2600161e7b7cSAneesh Kumar K.V 			 * We need to zero out the second half because
2601161e7b7cSAneesh Kumar K.V 			 * an fallocate request can update file size and
2602161e7b7cSAneesh Kumar K.V 			 * converting the second half to initialized extent
2603161e7b7cSAneesh Kumar K.V 			 * implies that we can leak some junk data to user
2604161e7b7cSAneesh Kumar K.V 			 * space.
2605161e7b7cSAneesh Kumar K.V 			 */
2606161e7b7cSAneesh Kumar K.V 			err =  ext4_ext_zeroout(inode, ex3);
2607161e7b7cSAneesh Kumar K.V 			if (err) {
2608161e7b7cSAneesh Kumar K.V 				/*
2609161e7b7cSAneesh Kumar K.V 				 * We should actually mark the
2610161e7b7cSAneesh Kumar K.V 				 * second half as uninit and return error
2611161e7b7cSAneesh Kumar K.V 				 * Insert would have changed the extent
2612161e7b7cSAneesh Kumar K.V 				 */
2613161e7b7cSAneesh Kumar K.V 				depth = ext_depth(inode);
2614161e7b7cSAneesh Kumar K.V 				ext4_ext_drop_refs(path);
2615161e7b7cSAneesh Kumar K.V 				path = ext4_ext_find_extent(inode,
2616161e7b7cSAneesh Kumar K.V 								iblock, path);
2617161e7b7cSAneesh Kumar K.V 				if (IS_ERR(path)) {
2618161e7b7cSAneesh Kumar K.V 					err = PTR_ERR(path);
2619161e7b7cSAneesh Kumar K.V 					return err;
2620161e7b7cSAneesh Kumar K.V 				}
2621d03856bdSAneesh Kumar K.V 				/* get the second half extent details */
2622161e7b7cSAneesh Kumar K.V 				ex = path[depth].p_ext;
2623161e7b7cSAneesh Kumar K.V 				err = ext4_ext_get_access(handle, inode,
2624161e7b7cSAneesh Kumar K.V 								path + depth);
2625161e7b7cSAneesh Kumar K.V 				if (err)
2626161e7b7cSAneesh Kumar K.V 					return err;
2627161e7b7cSAneesh Kumar K.V 				ext4_ext_mark_uninitialized(ex);
2628161e7b7cSAneesh Kumar K.V 				ext4_ext_dirty(handle, inode, path + depth);
2629161e7b7cSAneesh Kumar K.V 				return err;
2630161e7b7cSAneesh Kumar K.V 			}
2631161e7b7cSAneesh Kumar K.V 
2632161e7b7cSAneesh Kumar K.V 			/* zeroed the second half */
26333977c965SAneesh Kumar K.V 			return allocated;
26343977c965SAneesh Kumar K.V 		}
263556055d3aSAmit Arora 		ex3 = &newex;
263656055d3aSAmit Arora 		ex3->ee_block = cpu_to_le32(iblock + max_blocks);
263756055d3aSAmit Arora 		ext4_ext_store_pblock(ex3, newblock + max_blocks);
263856055d3aSAmit Arora 		ex3->ee_len = cpu_to_le16(allocated - max_blocks);
263956055d3aSAmit Arora 		ext4_ext_mark_uninitialized(ex3);
26400031462bSMingming Cao 		err = ext4_ext_insert_extent(handle, inode, path, ex3, 0);
2641093a088bSAneesh Kumar K.V 		if (err == -ENOSPC) {
2642093a088bSAneesh Kumar K.V 			err =  ext4_ext_zeroout(inode, &orig_ex);
2643093a088bSAneesh Kumar K.V 			if (err)
2644093a088bSAneesh Kumar K.V 				goto fix_extent_len;
2645093a088bSAneesh Kumar K.V 			/* update the extent length and mark as initialized */
264695c3889cSAneesh Kumar K.V 			ex->ee_block = orig_ex.ee_block;
264795c3889cSAneesh Kumar K.V 			ex->ee_len   = orig_ex.ee_len;
264895c3889cSAneesh Kumar K.V 			ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
264995c3889cSAneesh Kumar K.V 			ext4_ext_dirty(handle, inode, path + depth);
2650161e7b7cSAneesh Kumar K.V 			/* zeroed the full extent */
2651d03856bdSAneesh Kumar K.V 			/* blocks available from iblock */
2652161e7b7cSAneesh Kumar K.V 			return allocated;
2653093a088bSAneesh Kumar K.V 
2654093a088bSAneesh Kumar K.V 		} else if (err)
2655093a088bSAneesh Kumar K.V 			goto fix_extent_len;
265656055d3aSAmit Arora 		/*
265756055d3aSAmit Arora 		 * The depth, and hence eh & ex might change
265856055d3aSAmit Arora 		 * as part of the insert above.
265956055d3aSAmit Arora 		 */
266056055d3aSAmit Arora 		newdepth = ext_depth(inode);
266195c3889cSAneesh Kumar K.V 		/*
266273ac36eaSColy Li 		 * update the extent length after successful insert of the
266395c3889cSAneesh Kumar K.V 		 * split extent
266495c3889cSAneesh Kumar K.V 		 */
266595c3889cSAneesh Kumar K.V 		orig_ex.ee_len = cpu_to_le16(ee_len -
266695c3889cSAneesh Kumar K.V 						ext4_ext_get_actual_len(ex3));
266756055d3aSAmit Arora 		depth = newdepth;
2668b35905c1SAneesh Kumar K.V 		ext4_ext_drop_refs(path);
2669b35905c1SAneesh Kumar K.V 		path = ext4_ext_find_extent(inode, iblock, path);
267056055d3aSAmit Arora 		if (IS_ERR(path)) {
267156055d3aSAmit Arora 			err = PTR_ERR(path);
267256055d3aSAmit Arora 			goto out;
267356055d3aSAmit Arora 		}
267456055d3aSAmit Arora 		eh = path[depth].p_hdr;
267556055d3aSAmit Arora 		ex = path[depth].p_ext;
267656055d3aSAmit Arora 		if (ex2 != &newex)
267756055d3aSAmit Arora 			ex2 = ex;
26789df5643aSAneesh Kumar K.V 
26799df5643aSAneesh Kumar K.V 		err = ext4_ext_get_access(handle, inode, path + depth);
26809df5643aSAneesh Kumar K.V 		if (err)
26819df5643aSAneesh Kumar K.V 			goto out;
2682d03856bdSAneesh Kumar K.V 
268356055d3aSAmit Arora 		allocated = max_blocks;
26843977c965SAneesh Kumar K.V 
26853977c965SAneesh Kumar K.V 		/* If extent has less than EXT4_EXT_ZERO_LEN and we are trying
26863977c965SAneesh Kumar K.V 		 * to insert a extent in the middle zerout directly
26873977c965SAneesh Kumar K.V 		 * otherwise give the extent a chance to merge to left
26883977c965SAneesh Kumar K.V 		 */
26893977c965SAneesh Kumar K.V 		if (le16_to_cpu(orig_ex.ee_len) <= EXT4_EXT_ZERO_LEN &&
26903977c965SAneesh Kumar K.V 							iblock != ee_block) {
26913977c965SAneesh Kumar K.V 			err =  ext4_ext_zeroout(inode, &orig_ex);
26923977c965SAneesh Kumar K.V 			if (err)
26933977c965SAneesh Kumar K.V 				goto fix_extent_len;
26943977c965SAneesh Kumar K.V 			/* update the extent length and mark as initialized */
26953977c965SAneesh Kumar K.V 			ex->ee_block = orig_ex.ee_block;
26963977c965SAneesh Kumar K.V 			ex->ee_len   = orig_ex.ee_len;
26973977c965SAneesh Kumar K.V 			ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
26983977c965SAneesh Kumar K.V 			ext4_ext_dirty(handle, inode, path + depth);
2699161e7b7cSAneesh Kumar K.V 			/* zero out the first half */
2700d03856bdSAneesh Kumar K.V 			/* blocks available from iblock */
2701161e7b7cSAneesh Kumar K.V 			return allocated;
27023977c965SAneesh Kumar K.V 		}
270356055d3aSAmit Arora 	}
270456055d3aSAmit Arora 	/*
270556055d3aSAmit Arora 	 * If there was a change of depth as part of the
270656055d3aSAmit Arora 	 * insertion of ex3 above, we need to update the length
270756055d3aSAmit Arora 	 * of the ex1 extent again here
270856055d3aSAmit Arora 	 */
270956055d3aSAmit Arora 	if (ex1 && ex1 != ex) {
271056055d3aSAmit Arora 		ex1 = ex;
271156055d3aSAmit Arora 		ex1->ee_len = cpu_to_le16(iblock - ee_block);
271256055d3aSAmit Arora 		ext4_ext_mark_uninitialized(ex1);
271356055d3aSAmit Arora 		ex2 = &newex;
271456055d3aSAmit Arora 	}
271556055d3aSAmit Arora 	/* ex2: iblock to iblock + maxblocks-1 : initialised */
271656055d3aSAmit Arora 	ex2->ee_block = cpu_to_le32(iblock);
271756055d3aSAmit Arora 	ext4_ext_store_pblock(ex2, newblock);
271856055d3aSAmit Arora 	ex2->ee_len = cpu_to_le16(allocated);
271956055d3aSAmit Arora 	if (ex2 != ex)
272056055d3aSAmit Arora 		goto insert;
272156055d3aSAmit Arora 	/*
272256055d3aSAmit Arora 	 * New (initialized) extent starts from the first block
272356055d3aSAmit Arora 	 * in the current extent. i.e., ex2 == ex
272456055d3aSAmit Arora 	 * We have to see if it can be merged with the extent
272556055d3aSAmit Arora 	 * on the left.
272656055d3aSAmit Arora 	 */
272756055d3aSAmit Arora 	if (ex2 > EXT_FIRST_EXTENT(eh)) {
272856055d3aSAmit Arora 		/*
272956055d3aSAmit Arora 		 * To merge left, pass "ex2 - 1" to try_to_merge(),
273056055d3aSAmit Arora 		 * since it merges towards right _only_.
273156055d3aSAmit Arora 		 */
273256055d3aSAmit Arora 		ret = ext4_ext_try_to_merge(inode, path, ex2 - 1);
273356055d3aSAmit Arora 		if (ret) {
273456055d3aSAmit Arora 			err = ext4_ext_correct_indexes(handle, inode, path);
273556055d3aSAmit Arora 			if (err)
273656055d3aSAmit Arora 				goto out;
273756055d3aSAmit Arora 			depth = ext_depth(inode);
273856055d3aSAmit Arora 			ex2--;
273956055d3aSAmit Arora 		}
274056055d3aSAmit Arora 	}
274156055d3aSAmit Arora 	/*
274256055d3aSAmit Arora 	 * Try to Merge towards right. This might be required
274356055d3aSAmit Arora 	 * only when the whole extent is being written to.
274456055d3aSAmit Arora 	 * i.e. ex2 == ex and ex3 == NULL.
274556055d3aSAmit Arora 	 */
274656055d3aSAmit Arora 	if (!ex3) {
274756055d3aSAmit Arora 		ret = ext4_ext_try_to_merge(inode, path, ex2);
274856055d3aSAmit Arora 		if (ret) {
274956055d3aSAmit Arora 			err = ext4_ext_correct_indexes(handle, inode, path);
275056055d3aSAmit Arora 			if (err)
275156055d3aSAmit Arora 				goto out;
275256055d3aSAmit Arora 		}
275356055d3aSAmit Arora 	}
275456055d3aSAmit Arora 	/* Mark modified extent as dirty */
275556055d3aSAmit Arora 	err = ext4_ext_dirty(handle, inode, path + depth);
275656055d3aSAmit Arora 	goto out;
275756055d3aSAmit Arora insert:
27580031462bSMingming Cao 	err = ext4_ext_insert_extent(handle, inode, path, &newex, 0);
2759093a088bSAneesh Kumar K.V 	if (err == -ENOSPC) {
2760093a088bSAneesh Kumar K.V 		err =  ext4_ext_zeroout(inode, &orig_ex);
2761093a088bSAneesh Kumar K.V 		if (err)
2762093a088bSAneesh Kumar K.V 			goto fix_extent_len;
2763093a088bSAneesh Kumar K.V 		/* update the extent length and mark as initialized */
2764093a088bSAneesh Kumar K.V 		ex->ee_block = orig_ex.ee_block;
2765093a088bSAneesh Kumar K.V 		ex->ee_len   = orig_ex.ee_len;
2766093a088bSAneesh Kumar K.V 		ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
2767093a088bSAneesh Kumar K.V 		ext4_ext_dirty(handle, inode, path + depth);
2768161e7b7cSAneesh Kumar K.V 		/* zero out the first half */
2769161e7b7cSAneesh Kumar K.V 		return allocated;
2770093a088bSAneesh Kumar K.V 	} else if (err)
2771093a088bSAneesh Kumar K.V 		goto fix_extent_len;
2772093a088bSAneesh Kumar K.V out:
2773553f9008SMingming 	ext4_ext_show_leaf(inode, path);
2774093a088bSAneesh Kumar K.V 	return err ? err : allocated;
2775093a088bSAneesh Kumar K.V 
2776093a088bSAneesh Kumar K.V fix_extent_len:
277795c3889cSAneesh Kumar K.V 	ex->ee_block = orig_ex.ee_block;
277895c3889cSAneesh Kumar K.V 	ex->ee_len   = orig_ex.ee_len;
277995c3889cSAneesh Kumar K.V 	ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
278095c3889cSAneesh Kumar K.V 	ext4_ext_mark_uninitialized(ex);
278195c3889cSAneesh Kumar K.V 	ext4_ext_dirty(handle, inode, path + depth);
2782093a088bSAneesh Kumar K.V 	return err;
278356055d3aSAmit Arora }
278456055d3aSAmit Arora 
2785c278bfecSAneesh Kumar K.V /*
27860031462bSMingming Cao  * This function is called by ext4_ext_get_blocks() from
27870031462bSMingming Cao  * ext4_get_blocks_dio_write() when DIO to write
27880031462bSMingming Cao  * to an uninitialized extent.
27890031462bSMingming Cao  *
27900031462bSMingming Cao  * Writing to an uninitized extent may result in splitting the uninitialized
27910031462bSMingming Cao  * extent into multiple /intialized unintialized extents (up to three)
27920031462bSMingming Cao  * There are three possibilities:
27930031462bSMingming Cao  *   a> There is no split required: Entire extent should be uninitialized
27940031462bSMingming Cao  *   b> Splits in two extents: Write is happening at either end of the extent
27950031462bSMingming Cao  *   c> Splits in three extents: Somone is writing in middle of the extent
27960031462bSMingming Cao  *
27970031462bSMingming Cao  * One of more index blocks maybe needed if the extent tree grow after
27980031462bSMingming Cao  * the unintialized extent split. To prevent ENOSPC occur at the IO
27990031462bSMingming Cao  * complete, we need to split the uninitialized extent before DIO submit
28000031462bSMingming Cao  * the IO. The uninitilized extent called at this time will be split
28010031462bSMingming Cao  * into three uninitialized extent(at most). After IO complete, the part
28020031462bSMingming Cao  * being filled will be convert to initialized by the end_io callback function
28030031462bSMingming Cao  * via ext4_convert_unwritten_extents().
2804ba230c3fSMingming  *
2805ba230c3fSMingming  * Returns the size of uninitialized extent to be written on success.
28060031462bSMingming Cao  */
28070031462bSMingming Cao static int ext4_split_unwritten_extents(handle_t *handle,
28080031462bSMingming Cao 					struct inode *inode,
28090031462bSMingming Cao 					struct ext4_ext_path *path,
28100031462bSMingming Cao 					ext4_lblk_t iblock,
28110031462bSMingming Cao 					unsigned int max_blocks,
28120031462bSMingming Cao 					int flags)
28130031462bSMingming Cao {
28140031462bSMingming Cao 	struct ext4_extent *ex, newex, orig_ex;
28150031462bSMingming Cao 	struct ext4_extent *ex1 = NULL;
28160031462bSMingming Cao 	struct ext4_extent *ex2 = NULL;
28170031462bSMingming Cao 	struct ext4_extent *ex3 = NULL;
28180031462bSMingming Cao 	struct ext4_extent_header *eh;
28190031462bSMingming Cao 	ext4_lblk_t ee_block;
28200031462bSMingming Cao 	unsigned int allocated, ee_len, depth;
28210031462bSMingming Cao 	ext4_fsblk_t newblock;
28220031462bSMingming Cao 	int err = 0;
28230031462bSMingming Cao 
28240031462bSMingming Cao 	ext_debug("ext4_split_unwritten_extents: inode %lu,"
28250031462bSMingming Cao 		  "iblock %llu, max_blocks %u\n", inode->i_ino,
28260031462bSMingming Cao 		  (unsigned long long)iblock, max_blocks);
28270031462bSMingming Cao 	depth = ext_depth(inode);
28280031462bSMingming Cao 	eh = path[depth].p_hdr;
28290031462bSMingming Cao 	ex = path[depth].p_ext;
28300031462bSMingming Cao 	ee_block = le32_to_cpu(ex->ee_block);
28310031462bSMingming Cao 	ee_len = ext4_ext_get_actual_len(ex);
28320031462bSMingming Cao 	allocated = ee_len - (iblock - ee_block);
28330031462bSMingming Cao 	newblock = iblock - ee_block + ext_pblock(ex);
28340031462bSMingming Cao 	ex2 = ex;
28350031462bSMingming Cao 	orig_ex.ee_block = ex->ee_block;
28360031462bSMingming Cao 	orig_ex.ee_len   = cpu_to_le16(ee_len);
28370031462bSMingming Cao 	ext4_ext_store_pblock(&orig_ex, ext_pblock(ex));
28380031462bSMingming Cao 
28390031462bSMingming Cao 	/*
2840ba230c3fSMingming  	 * If the uninitialized extent begins at the same logical
2841ba230c3fSMingming  	 * block where the write begins, and the write completely
2842ba230c3fSMingming  	 * covers the extent, then we don't need to split it.
28430031462bSMingming Cao  	 */
2844ba230c3fSMingming 	if ((iblock == ee_block) && (allocated <= max_blocks))
2845ba230c3fSMingming 		return allocated;
28460031462bSMingming Cao 
28470031462bSMingming Cao 	err = ext4_ext_get_access(handle, inode, path + depth);
28480031462bSMingming Cao 	if (err)
28490031462bSMingming Cao 		goto out;
28500031462bSMingming Cao 	/* ex1: ee_block to iblock - 1 : uninitialized */
28510031462bSMingming Cao 	if (iblock > ee_block) {
28520031462bSMingming Cao 		ex1 = ex;
28530031462bSMingming Cao 		ex1->ee_len = cpu_to_le16(iblock - ee_block);
28540031462bSMingming Cao 		ext4_ext_mark_uninitialized(ex1);
28550031462bSMingming Cao 		ex2 = &newex;
28560031462bSMingming Cao 	}
28570031462bSMingming Cao 	/*
28580031462bSMingming Cao 	 * for sanity, update the length of the ex2 extent before
28590031462bSMingming Cao 	 * we insert ex3, if ex1 is NULL. This is to avoid temporary
28600031462bSMingming Cao 	 * overlap of blocks.
28610031462bSMingming Cao 	 */
28620031462bSMingming Cao 	if (!ex1 && allocated > max_blocks)
28630031462bSMingming Cao 		ex2->ee_len = cpu_to_le16(max_blocks);
28640031462bSMingming Cao 	/* ex3: to ee_block + ee_len : uninitialised */
28650031462bSMingming Cao 	if (allocated > max_blocks) {
28660031462bSMingming Cao 		unsigned int newdepth;
28670031462bSMingming Cao 		ex3 = &newex;
28680031462bSMingming Cao 		ex3->ee_block = cpu_to_le32(iblock + max_blocks);
28690031462bSMingming Cao 		ext4_ext_store_pblock(ex3, newblock + max_blocks);
28700031462bSMingming Cao 		ex3->ee_len = cpu_to_le16(allocated - max_blocks);
28710031462bSMingming Cao 		ext4_ext_mark_uninitialized(ex3);
28720031462bSMingming Cao 		err = ext4_ext_insert_extent(handle, inode, path, ex3, flags);
28730031462bSMingming Cao 		if (err == -ENOSPC) {
28740031462bSMingming Cao 			err =  ext4_ext_zeroout(inode, &orig_ex);
28750031462bSMingming Cao 			if (err)
28760031462bSMingming Cao 				goto fix_extent_len;
28770031462bSMingming Cao 			/* update the extent length and mark as initialized */
28780031462bSMingming Cao 			ex->ee_block = orig_ex.ee_block;
28790031462bSMingming Cao 			ex->ee_len   = orig_ex.ee_len;
28800031462bSMingming Cao 			ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
28810031462bSMingming Cao 			ext4_ext_dirty(handle, inode, path + depth);
28820031462bSMingming Cao 			/* zeroed the full extent */
28830031462bSMingming Cao 			/* blocks available from iblock */
28840031462bSMingming Cao 			return allocated;
28850031462bSMingming Cao 
28860031462bSMingming Cao 		} else if (err)
28870031462bSMingming Cao 			goto fix_extent_len;
28880031462bSMingming Cao 		/*
28890031462bSMingming Cao 		 * The depth, and hence eh & ex might change
28900031462bSMingming Cao 		 * as part of the insert above.
28910031462bSMingming Cao 		 */
28920031462bSMingming Cao 		newdepth = ext_depth(inode);
28930031462bSMingming Cao 		/*
28940031462bSMingming Cao 		 * update the extent length after successful insert of the
28950031462bSMingming Cao 		 * split extent
28960031462bSMingming Cao 		 */
28970031462bSMingming Cao 		orig_ex.ee_len = cpu_to_le16(ee_len -
28980031462bSMingming Cao 						ext4_ext_get_actual_len(ex3));
28990031462bSMingming Cao 		depth = newdepth;
29000031462bSMingming Cao 		ext4_ext_drop_refs(path);
29010031462bSMingming Cao 		path = ext4_ext_find_extent(inode, iblock, path);
29020031462bSMingming Cao 		if (IS_ERR(path)) {
29030031462bSMingming Cao 			err = PTR_ERR(path);
29040031462bSMingming Cao 			goto out;
29050031462bSMingming Cao 		}
29060031462bSMingming Cao 		eh = path[depth].p_hdr;
29070031462bSMingming Cao 		ex = path[depth].p_ext;
29080031462bSMingming Cao 		if (ex2 != &newex)
29090031462bSMingming Cao 			ex2 = ex;
29100031462bSMingming Cao 
29110031462bSMingming Cao 		err = ext4_ext_get_access(handle, inode, path + depth);
29120031462bSMingming Cao 		if (err)
29130031462bSMingming Cao 			goto out;
29140031462bSMingming Cao 
29150031462bSMingming Cao 		allocated = max_blocks;
29160031462bSMingming Cao 	}
29170031462bSMingming Cao 	/*
29180031462bSMingming Cao 	 * If there was a change of depth as part of the
29190031462bSMingming Cao 	 * insertion of ex3 above, we need to update the length
29200031462bSMingming Cao 	 * of the ex1 extent again here
29210031462bSMingming Cao 	 */
29220031462bSMingming Cao 	if (ex1 && ex1 != ex) {
29230031462bSMingming Cao 		ex1 = ex;
29240031462bSMingming Cao 		ex1->ee_len = cpu_to_le16(iblock - ee_block);
29250031462bSMingming Cao 		ext4_ext_mark_uninitialized(ex1);
29260031462bSMingming Cao 		ex2 = &newex;
29270031462bSMingming Cao 	}
29280031462bSMingming Cao 	/*
29290031462bSMingming Cao 	 * ex2: iblock to iblock + maxblocks-1 : to be direct IO written,
29300031462bSMingming Cao 	 * uninitialised still.
29310031462bSMingming Cao 	 */
29320031462bSMingming Cao 	ex2->ee_block = cpu_to_le32(iblock);
29330031462bSMingming Cao 	ext4_ext_store_pblock(ex2, newblock);
29340031462bSMingming Cao 	ex2->ee_len = cpu_to_le16(allocated);
29350031462bSMingming Cao 	ext4_ext_mark_uninitialized(ex2);
29360031462bSMingming Cao 	if (ex2 != ex)
29370031462bSMingming Cao 		goto insert;
29380031462bSMingming Cao 	/* Mark modified extent as dirty */
29390031462bSMingming Cao 	err = ext4_ext_dirty(handle, inode, path + depth);
29400031462bSMingming Cao 	ext_debug("out here\n");
29410031462bSMingming Cao 	goto out;
29420031462bSMingming Cao insert:
29430031462bSMingming Cao 	err = ext4_ext_insert_extent(handle, inode, path, &newex, flags);
29440031462bSMingming Cao 	if (err == -ENOSPC) {
29450031462bSMingming Cao 		err =  ext4_ext_zeroout(inode, &orig_ex);
29460031462bSMingming Cao 		if (err)
29470031462bSMingming Cao 			goto fix_extent_len;
29480031462bSMingming Cao 		/* update the extent length and mark as initialized */
29490031462bSMingming Cao 		ex->ee_block = orig_ex.ee_block;
29500031462bSMingming Cao 		ex->ee_len   = orig_ex.ee_len;
29510031462bSMingming Cao 		ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
29520031462bSMingming Cao 		ext4_ext_dirty(handle, inode, path + depth);
29530031462bSMingming Cao 		/* zero out the first half */
29540031462bSMingming Cao 		return allocated;
29550031462bSMingming Cao 	} else if (err)
29560031462bSMingming Cao 		goto fix_extent_len;
29570031462bSMingming Cao out:
29580031462bSMingming Cao 	ext4_ext_show_leaf(inode, path);
29590031462bSMingming Cao 	return err ? err : allocated;
29600031462bSMingming Cao 
29610031462bSMingming Cao fix_extent_len:
29620031462bSMingming Cao 	ex->ee_block = orig_ex.ee_block;
29630031462bSMingming Cao 	ex->ee_len   = orig_ex.ee_len;
29640031462bSMingming Cao 	ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
29650031462bSMingming Cao 	ext4_ext_mark_uninitialized(ex);
29660031462bSMingming Cao 	ext4_ext_dirty(handle, inode, path + depth);
29670031462bSMingming Cao 	return err;
29680031462bSMingming Cao }
29690031462bSMingming Cao static int ext4_convert_unwritten_extents_dio(handle_t *handle,
29700031462bSMingming Cao 					      struct inode *inode,
29710031462bSMingming Cao 					      struct ext4_ext_path *path)
29720031462bSMingming Cao {
29730031462bSMingming Cao 	struct ext4_extent *ex;
29740031462bSMingming Cao 	struct ext4_extent_header *eh;
29750031462bSMingming Cao 	int depth;
29760031462bSMingming Cao 	int err = 0;
29770031462bSMingming Cao 	int ret = 0;
29780031462bSMingming Cao 
29790031462bSMingming Cao 	depth = ext_depth(inode);
29800031462bSMingming Cao 	eh = path[depth].p_hdr;
29810031462bSMingming Cao 	ex = path[depth].p_ext;
29820031462bSMingming Cao 
29830031462bSMingming Cao 	err = ext4_ext_get_access(handle, inode, path + depth);
29840031462bSMingming Cao 	if (err)
29850031462bSMingming Cao 		goto out;
29860031462bSMingming Cao 	/* first mark the extent as initialized */
29870031462bSMingming Cao 	ext4_ext_mark_initialized(ex);
29880031462bSMingming Cao 
29890031462bSMingming Cao 	/*
29900031462bSMingming Cao 	 * We have to see if it can be merged with the extent
29910031462bSMingming Cao 	 * on the left.
29920031462bSMingming Cao 	 */
29930031462bSMingming Cao 	if (ex > EXT_FIRST_EXTENT(eh)) {
29940031462bSMingming Cao 		/*
29950031462bSMingming Cao 		 * To merge left, pass "ex - 1" to try_to_merge(),
29960031462bSMingming Cao 		 * since it merges towards right _only_.
29970031462bSMingming Cao 		 */
29980031462bSMingming Cao 		ret = ext4_ext_try_to_merge(inode, path, ex - 1);
29990031462bSMingming Cao 		if (ret) {
30000031462bSMingming Cao 			err = ext4_ext_correct_indexes(handle, inode, path);
30010031462bSMingming Cao 			if (err)
30020031462bSMingming Cao 				goto out;
30030031462bSMingming Cao 			depth = ext_depth(inode);
30040031462bSMingming Cao 			ex--;
30050031462bSMingming Cao 		}
30060031462bSMingming Cao 	}
30070031462bSMingming Cao 	/*
30080031462bSMingming Cao 	 * Try to Merge towards right.
30090031462bSMingming Cao 	 */
30100031462bSMingming Cao 	ret = ext4_ext_try_to_merge(inode, path, ex);
30110031462bSMingming Cao 	if (ret) {
30120031462bSMingming Cao 		err = ext4_ext_correct_indexes(handle, inode, path);
30130031462bSMingming Cao 		if (err)
30140031462bSMingming Cao 			goto out;
30150031462bSMingming Cao 		depth = ext_depth(inode);
30160031462bSMingming Cao 	}
30170031462bSMingming Cao 	/* Mark modified extent as dirty */
30180031462bSMingming Cao 	err = ext4_ext_dirty(handle, inode, path + depth);
30190031462bSMingming Cao out:
30200031462bSMingming Cao 	ext4_ext_show_leaf(inode, path);
30210031462bSMingming Cao 	return err;
30220031462bSMingming Cao }
30230031462bSMingming Cao 
30240031462bSMingming Cao static int
30250031462bSMingming Cao ext4_ext_handle_uninitialized_extents(handle_t *handle, struct inode *inode,
30260031462bSMingming Cao 			ext4_lblk_t iblock, unsigned int max_blocks,
30270031462bSMingming Cao 			struct ext4_ext_path *path, int flags,
30280031462bSMingming Cao 			unsigned int allocated, struct buffer_head *bh_result,
30290031462bSMingming Cao 			ext4_fsblk_t newblock)
30300031462bSMingming Cao {
30310031462bSMingming Cao 	int ret = 0;
30320031462bSMingming Cao 	int err = 0;
30338d5d02e6SMingming Cao 	ext4_io_end_t *io = EXT4_I(inode)->cur_aio_dio;
30340031462bSMingming Cao 
30350031462bSMingming Cao 	ext_debug("ext4_ext_handle_uninitialized_extents: inode %lu, logical"
30360031462bSMingming Cao 		  "block %llu, max_blocks %u, flags %d, allocated %u",
30370031462bSMingming Cao 		  inode->i_ino, (unsigned long long)iblock, max_blocks,
30380031462bSMingming Cao 		  flags, allocated);
30390031462bSMingming Cao 	ext4_ext_show_leaf(inode, path);
30400031462bSMingming Cao 
30410031462bSMingming Cao 	/* DIO get_block() before submit the IO, split the extent */
30420031462bSMingming Cao 	if (flags == EXT4_GET_BLOCKS_DIO_CREATE_EXT) {
30430031462bSMingming Cao 		ret = ext4_split_unwritten_extents(handle,
30440031462bSMingming Cao 						inode, path, iblock,
30450031462bSMingming Cao 						max_blocks, flags);
30465f524950SMingming 		/*
30475f524950SMingming 		 * Flag the inode(non aio case) or end_io struct (aio case)
30485f524950SMingming 		 * that this IO needs to convertion to written when IO is
30495f524950SMingming 		 * completed
30505f524950SMingming 		 */
30518d5d02e6SMingming Cao 		if (io)
30528d5d02e6SMingming Cao 			io->flag = DIO_AIO_UNWRITTEN;
30535f524950SMingming 		else
30545f524950SMingming 			EXT4_I(inode)->i_state |= EXT4_STATE_DIO_UNWRITTEN;
30550031462bSMingming Cao 		goto out;
30560031462bSMingming Cao 	}
30575f524950SMingming 	/* async DIO end_io complete, convert the filled extent to written */
30580031462bSMingming Cao 	if (flags == EXT4_GET_BLOCKS_DIO_CONVERT_EXT) {
30590031462bSMingming Cao 		ret = ext4_convert_unwritten_extents_dio(handle, inode,
30600031462bSMingming Cao 							path);
30610031462bSMingming Cao 		goto out2;
30620031462bSMingming Cao 	}
30630031462bSMingming Cao 	/* buffered IO case */
30640031462bSMingming Cao 	/*
30650031462bSMingming Cao 	 * repeat fallocate creation request
30660031462bSMingming Cao 	 * we already have an unwritten extent
30670031462bSMingming Cao 	 */
30680031462bSMingming Cao 	if (flags & EXT4_GET_BLOCKS_UNINIT_EXT)
30690031462bSMingming Cao 		goto map_out;
30700031462bSMingming Cao 
30710031462bSMingming Cao 	/* buffered READ or buffered write_begin() lookup */
30720031462bSMingming Cao 	if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
30730031462bSMingming Cao 		/*
30740031462bSMingming Cao 		 * We have blocks reserved already.  We
30750031462bSMingming Cao 		 * return allocated blocks so that delalloc
30760031462bSMingming Cao 		 * won't do block reservation for us.  But
30770031462bSMingming Cao 		 * the buffer head will be unmapped so that
30780031462bSMingming Cao 		 * a read from the block returns 0s.
30790031462bSMingming Cao 		 */
30800031462bSMingming Cao 		set_buffer_unwritten(bh_result);
30810031462bSMingming Cao 		goto out1;
30820031462bSMingming Cao 	}
30830031462bSMingming Cao 
30840031462bSMingming Cao 	/* buffered write, writepage time, convert*/
30850031462bSMingming Cao 	ret = ext4_ext_convert_to_initialized(handle, inode,
30860031462bSMingming Cao 						path, iblock,
30870031462bSMingming Cao 						max_blocks);
30880031462bSMingming Cao out:
30890031462bSMingming Cao 	if (ret <= 0) {
30900031462bSMingming Cao 		err = ret;
30910031462bSMingming Cao 		goto out2;
30920031462bSMingming Cao 	} else
30930031462bSMingming Cao 		allocated = ret;
30940031462bSMingming Cao 	set_buffer_new(bh_result);
30950031462bSMingming Cao map_out:
30960031462bSMingming Cao 	set_buffer_mapped(bh_result);
30970031462bSMingming Cao out1:
30980031462bSMingming Cao 	if (allocated > max_blocks)
30990031462bSMingming Cao 		allocated = max_blocks;
31000031462bSMingming Cao 	ext4_ext_show_leaf(inode, path);
31010031462bSMingming Cao 	bh_result->b_bdev = inode->i_sb->s_bdev;
31020031462bSMingming Cao 	bh_result->b_blocknr = newblock;
31030031462bSMingming Cao out2:
31040031462bSMingming Cao 	if (path) {
31050031462bSMingming Cao 		ext4_ext_drop_refs(path);
31060031462bSMingming Cao 		kfree(path);
31070031462bSMingming Cao 	}
31080031462bSMingming Cao 	return err ? err : allocated;
31090031462bSMingming Cao }
31100031462bSMingming Cao /*
3111f5ab0d1fSMingming Cao  * Block allocation/map/preallocation routine for extents based files
3112f5ab0d1fSMingming Cao  *
3113f5ab0d1fSMingming Cao  *
3114c278bfecSAneesh Kumar K.V  * Need to be called with
31150e855ac8SAneesh Kumar K.V  * down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system block
31160e855ac8SAneesh Kumar K.V  * (ie, create is zero). Otherwise down_write(&EXT4_I(inode)->i_data_sem)
3117f5ab0d1fSMingming Cao  *
3118f5ab0d1fSMingming Cao  * return > 0, number of of blocks already mapped/allocated
3119f5ab0d1fSMingming Cao  *          if create == 0 and these are pre-allocated blocks
3120f5ab0d1fSMingming Cao  *          	buffer head is unmapped
3121f5ab0d1fSMingming Cao  *          otherwise blocks are mapped
3122f5ab0d1fSMingming Cao  *
3123f5ab0d1fSMingming Cao  * return = 0, if plain look up failed (blocks have not been allocated)
3124f5ab0d1fSMingming Cao  *          buffer head is unmapped
3125f5ab0d1fSMingming Cao  *
3126f5ab0d1fSMingming Cao  * return < 0, error case.
3127c278bfecSAneesh Kumar K.V  */
3128f65e6fbaSAlex Tomas int ext4_ext_get_blocks(handle_t *handle, struct inode *inode,
3129725d26d3SAneesh Kumar K.V 			ext4_lblk_t iblock,
3130498e5f24STheodore Ts'o 			unsigned int max_blocks, struct buffer_head *bh_result,
3131c2177057STheodore Ts'o 			int flags)
3132a86c6181SAlex Tomas {
3133a86c6181SAlex Tomas 	struct ext4_ext_path *path = NULL;
313456055d3aSAmit Arora 	struct ext4_extent_header *eh;
3135a86c6181SAlex Tomas 	struct ext4_extent newex, *ex;
3136498e5f24STheodore Ts'o 	ext4_fsblk_t newblock;
3137498e5f24STheodore Ts'o 	int err = 0, depth, ret, cache_type;
3138498e5f24STheodore Ts'o 	unsigned int allocated = 0;
3139c9de560dSAlex Tomas 	struct ext4_allocation_request ar;
31408d5d02e6SMingming Cao 	ext4_io_end_t *io = EXT4_I(inode)->cur_aio_dio;
3141a86c6181SAlex Tomas 
3142a86c6181SAlex Tomas 	__clear_bit(BH_New, &bh_result->b_state);
314384fe3befSMingming 	ext_debug("blocks %u/%u requested for inode %lu\n",
3144bba90743SEric Sandeen 			iblock, max_blocks, inode->i_ino);
3145a86c6181SAlex Tomas 
3146a86c6181SAlex Tomas 	/* check in cache */
3147498e5f24STheodore Ts'o 	cache_type = ext4_ext_in_cache(inode, iblock, &newex);
3148498e5f24STheodore Ts'o 	if (cache_type) {
3149498e5f24STheodore Ts'o 		if (cache_type == EXT4_EXT_CACHE_GAP) {
3150c2177057STheodore Ts'o 			if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
315156055d3aSAmit Arora 				/*
315256055d3aSAmit Arora 				 * block isn't allocated yet and
315356055d3aSAmit Arora 				 * user doesn't want to allocate it
315456055d3aSAmit Arora 				 */
3155a86c6181SAlex Tomas 				goto out2;
3156a86c6181SAlex Tomas 			}
3157a86c6181SAlex Tomas 			/* we should allocate requested block */
3158498e5f24STheodore Ts'o 		} else if (cache_type == EXT4_EXT_CACHE_EXTENT) {
3159a86c6181SAlex Tomas 			/* block is already allocated */
3160a86c6181SAlex Tomas 			newblock = iblock
3161a86c6181SAlex Tomas 				   - le32_to_cpu(newex.ee_block)
3162f65e6fbaSAlex Tomas 				   + ext_pblock(&newex);
3163d0d856e8SRandy Dunlap 			/* number of remaining blocks in the extent */
3164b939e376SAneesh Kumar K.V 			allocated = ext4_ext_get_actual_len(&newex) -
3165a86c6181SAlex Tomas 					(iblock - le32_to_cpu(newex.ee_block));
3166a86c6181SAlex Tomas 			goto out;
3167a86c6181SAlex Tomas 		} else {
3168a86c6181SAlex Tomas 			BUG();
3169a86c6181SAlex Tomas 		}
3170a86c6181SAlex Tomas 	}
3171a86c6181SAlex Tomas 
3172a86c6181SAlex Tomas 	/* find extent for this block */
3173a86c6181SAlex Tomas 	path = ext4_ext_find_extent(inode, iblock, NULL);
3174a86c6181SAlex Tomas 	if (IS_ERR(path)) {
3175a86c6181SAlex Tomas 		err = PTR_ERR(path);
3176a86c6181SAlex Tomas 		path = NULL;
3177a86c6181SAlex Tomas 		goto out2;
3178a86c6181SAlex Tomas 	}
3179a86c6181SAlex Tomas 
3180a86c6181SAlex Tomas 	depth = ext_depth(inode);
3181a86c6181SAlex Tomas 
3182a86c6181SAlex Tomas 	/*
3183d0d856e8SRandy Dunlap 	 * consistent leaf must not be empty;
3184d0d856e8SRandy Dunlap 	 * this situation is possible, though, _during_ tree modification;
3185a86c6181SAlex Tomas 	 * this is why assert can't be put in ext4_ext_find_extent()
3186a86c6181SAlex Tomas 	 */
3187a86c6181SAlex Tomas 	BUG_ON(path[depth].p_ext == NULL && depth != 0);
318856055d3aSAmit Arora 	eh = path[depth].p_hdr;
3189a86c6181SAlex Tomas 
31907e028976SAvantika Mathur 	ex = path[depth].p_ext;
31917e028976SAvantika Mathur 	if (ex) {
3192725d26d3SAneesh Kumar K.V 		ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
3193f65e6fbaSAlex Tomas 		ext4_fsblk_t ee_start = ext_pblock(ex);
3194a2df2a63SAmit Arora 		unsigned short ee_len;
3195471d4011SSuparna Bhattacharya 
3196471d4011SSuparna Bhattacharya 		/*
3197471d4011SSuparna Bhattacharya 		 * Uninitialized extents are treated as holes, except that
319856055d3aSAmit Arora 		 * we split out initialized portions during a write.
3199471d4011SSuparna Bhattacharya 		 */
3200a2df2a63SAmit Arora 		ee_len = ext4_ext_get_actual_len(ex);
3201d0d856e8SRandy Dunlap 		/* if found extent covers block, simply return it */
3202a86c6181SAlex Tomas 		if (iblock >= ee_block && iblock < ee_block + ee_len) {
3203a86c6181SAlex Tomas 			newblock = iblock - ee_block + ee_start;
3204d0d856e8SRandy Dunlap 			/* number of remaining blocks in the extent */
3205a86c6181SAlex Tomas 			allocated = ee_len - (iblock - ee_block);
320684fe3befSMingming 			ext_debug("%u fit into %u:%d -> %llu\n", iblock,
3207a86c6181SAlex Tomas 					ee_block, ee_len, newblock);
320856055d3aSAmit Arora 
3209a2df2a63SAmit Arora 			/* Do not put uninitialized extent in the cache */
321056055d3aSAmit Arora 			if (!ext4_ext_is_uninitialized(ex)) {
3211a2df2a63SAmit Arora 				ext4_ext_put_in_cache(inode, ee_block,
3212a2df2a63SAmit Arora 							ee_len, ee_start,
3213a2df2a63SAmit Arora 							EXT4_EXT_CACHE_EXTENT);
3214a86c6181SAlex Tomas 				goto out;
3215a86c6181SAlex Tomas 			}
32160031462bSMingming Cao 			ret = ext4_ext_handle_uninitialized_extents(handle,
32170031462bSMingming Cao 					inode, iblock, max_blocks, path,
32180031462bSMingming Cao 					flags, allocated, bh_result, newblock);
32190031462bSMingming Cao 			return ret;
322056055d3aSAmit Arora 		}
3221a86c6181SAlex Tomas 	}
3222a86c6181SAlex Tomas 
3223a86c6181SAlex Tomas 	/*
3224d0d856e8SRandy Dunlap 	 * requested block isn't allocated yet;
3225a86c6181SAlex Tomas 	 * we couldn't try to create block if create flag is zero
3226a86c6181SAlex Tomas 	 */
3227c2177057STheodore Ts'o 	if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
322856055d3aSAmit Arora 		/*
322956055d3aSAmit Arora 		 * put just found gap into cache to speed up
323056055d3aSAmit Arora 		 * subsequent requests
323156055d3aSAmit Arora 		 */
3232a86c6181SAlex Tomas 		ext4_ext_put_gap_in_cache(inode, path, iblock);
3233a86c6181SAlex Tomas 		goto out2;
3234a86c6181SAlex Tomas 	}
3235a86c6181SAlex Tomas 	/*
3236c2ea3fdeSTheodore Ts'o 	 * Okay, we need to do block allocation.
3237a86c6181SAlex Tomas 	 */
3238a86c6181SAlex Tomas 
3239c9de560dSAlex Tomas 	/* find neighbour allocated blocks */
3240c9de560dSAlex Tomas 	ar.lleft = iblock;
3241c9de560dSAlex Tomas 	err = ext4_ext_search_left(inode, path, &ar.lleft, &ar.pleft);
3242c9de560dSAlex Tomas 	if (err)
3243c9de560dSAlex Tomas 		goto out2;
3244c9de560dSAlex Tomas 	ar.lright = iblock;
3245c9de560dSAlex Tomas 	err = ext4_ext_search_right(inode, path, &ar.lright, &ar.pright);
3246c9de560dSAlex Tomas 	if (err)
3247c9de560dSAlex Tomas 		goto out2;
324825d14f98SAmit Arora 
3249749269faSAmit Arora 	/*
3250749269faSAmit Arora 	 * See if request is beyond maximum number of blocks we can have in
3251749269faSAmit Arora 	 * a single extent. For an initialized extent this limit is
3252749269faSAmit Arora 	 * EXT_INIT_MAX_LEN and for an uninitialized extent this limit is
3253749269faSAmit Arora 	 * EXT_UNINIT_MAX_LEN.
3254749269faSAmit Arora 	 */
3255749269faSAmit Arora 	if (max_blocks > EXT_INIT_MAX_LEN &&
3256c2177057STheodore Ts'o 	    !(flags & EXT4_GET_BLOCKS_UNINIT_EXT))
3257749269faSAmit Arora 		max_blocks = EXT_INIT_MAX_LEN;
3258749269faSAmit Arora 	else if (max_blocks > EXT_UNINIT_MAX_LEN &&
3259c2177057STheodore Ts'o 		 (flags & EXT4_GET_BLOCKS_UNINIT_EXT))
3260749269faSAmit Arora 		max_blocks = EXT_UNINIT_MAX_LEN;
3261749269faSAmit Arora 
326225d14f98SAmit Arora 	/* Check if we can really insert (iblock)::(iblock+max_blocks) extent */
326325d14f98SAmit Arora 	newex.ee_block = cpu_to_le32(iblock);
326425d14f98SAmit Arora 	newex.ee_len = cpu_to_le16(max_blocks);
326525d14f98SAmit Arora 	err = ext4_ext_check_overlap(inode, &newex, path);
326625d14f98SAmit Arora 	if (err)
3267b939e376SAneesh Kumar K.V 		allocated = ext4_ext_get_actual_len(&newex);
326825d14f98SAmit Arora 	else
3269a86c6181SAlex Tomas 		allocated = max_blocks;
3270c9de560dSAlex Tomas 
3271c9de560dSAlex Tomas 	/* allocate new block */
3272c9de560dSAlex Tomas 	ar.inode = inode;
3273c9de560dSAlex Tomas 	ar.goal = ext4_ext_find_goal(inode, path, iblock);
3274c9de560dSAlex Tomas 	ar.logical = iblock;
3275c9de560dSAlex Tomas 	ar.len = allocated;
3276c9de560dSAlex Tomas 	if (S_ISREG(inode->i_mode))
3277c9de560dSAlex Tomas 		ar.flags = EXT4_MB_HINT_DATA;
3278c9de560dSAlex Tomas 	else
3279c9de560dSAlex Tomas 		/* disable in-core preallocation for non-regular files */
3280c9de560dSAlex Tomas 		ar.flags = 0;
3281c9de560dSAlex Tomas 	newblock = ext4_mb_new_blocks(handle, &ar, &err);
3282a86c6181SAlex Tomas 	if (!newblock)
3283a86c6181SAlex Tomas 		goto out2;
328484fe3befSMingming 	ext_debug("allocate new block: goal %llu, found %llu/%u\n",
3285498e5f24STheodore Ts'o 		  ar.goal, newblock, allocated);
3286a86c6181SAlex Tomas 
3287a86c6181SAlex Tomas 	/* try to insert new extent into found leaf and return */
3288f65e6fbaSAlex Tomas 	ext4_ext_store_pblock(&newex, newblock);
3289c9de560dSAlex Tomas 	newex.ee_len = cpu_to_le16(ar.len);
32908d5d02e6SMingming Cao 	/* Mark uninitialized */
32918d5d02e6SMingming Cao 	if (flags & EXT4_GET_BLOCKS_UNINIT_EXT){
3292a2df2a63SAmit Arora 		ext4_ext_mark_uninitialized(&newex);
32938d5d02e6SMingming Cao 		/*
32948d5d02e6SMingming Cao 		 * io_end structure was created for every async
32958d5d02e6SMingming Cao 		 * direct IO write to the middle of the file.
32968d5d02e6SMingming Cao 		 * To avoid unecessary convertion for every aio dio rewrite
32978d5d02e6SMingming Cao 		 * to the mid of file, here we flag the IO that is really
32988d5d02e6SMingming Cao 		 * need the convertion.
32995f524950SMingming 		 * For non asycn direct IO case, flag the inode state
33005f524950SMingming 		 * that we need to perform convertion when IO is done.
33018d5d02e6SMingming Cao 		 */
33025f524950SMingming 		if (flags == EXT4_GET_BLOCKS_DIO_CREATE_EXT) {
33035f524950SMingming 			if (io)
33048d5d02e6SMingming Cao 				io->flag = DIO_AIO_UNWRITTEN;
33055f524950SMingming 			else
33065f524950SMingming 				EXT4_I(inode)->i_state |=
33075f524950SMingming 					EXT4_STATE_DIO_UNWRITTEN;;
33085f524950SMingming 		}
33098d5d02e6SMingming Cao 	}
33100031462bSMingming Cao 	err = ext4_ext_insert_extent(handle, inode, path, &newex, flags);
3311315054f0SAlex Tomas 	if (err) {
3312315054f0SAlex Tomas 		/* free data blocks we just allocated */
3313c9de560dSAlex Tomas 		/* not a good idea to call discard here directly,
3314c9de560dSAlex Tomas 		 * but otherwise we'd need to call it every free() */
3315c2ea3fdeSTheodore Ts'o 		ext4_discard_preallocations(inode);
3316*e6362609STheodore Ts'o 		ext4_free_blocks(handle, inode, 0, ext_pblock(&newex),
3317b939e376SAneesh Kumar K.V 				 ext4_ext_get_actual_len(&newex), 0);
3318a86c6181SAlex Tomas 		goto out2;
3319315054f0SAlex Tomas 	}
3320a86c6181SAlex Tomas 
3321a86c6181SAlex Tomas 	/* previous routine could use block we allocated */
3322f65e6fbaSAlex Tomas 	newblock = ext_pblock(&newex);
3323b939e376SAneesh Kumar K.V 	allocated = ext4_ext_get_actual_len(&newex);
3324953e622bSEric Sandeen 	set_buffer_new(bh_result);
3325a86c6181SAlex Tomas 
3326a2df2a63SAmit Arora 	/* Cache only when it is _not_ an uninitialized extent */
3327c2177057STheodore Ts'o 	if ((flags & EXT4_GET_BLOCKS_UNINIT_EXT) == 0)
3328a86c6181SAlex Tomas 		ext4_ext_put_in_cache(inode, iblock, allocated, newblock,
3329a86c6181SAlex Tomas 						EXT4_EXT_CACHE_EXTENT);
3330a86c6181SAlex Tomas out:
3331a86c6181SAlex Tomas 	if (allocated > max_blocks)
3332a86c6181SAlex Tomas 		allocated = max_blocks;
3333a86c6181SAlex Tomas 	ext4_ext_show_leaf(inode, path);
3334953e622bSEric Sandeen 	set_buffer_mapped(bh_result);
3335a86c6181SAlex Tomas 	bh_result->b_bdev = inode->i_sb->s_bdev;
3336a86c6181SAlex Tomas 	bh_result->b_blocknr = newblock;
3337a86c6181SAlex Tomas out2:
3338a86c6181SAlex Tomas 	if (path) {
3339a86c6181SAlex Tomas 		ext4_ext_drop_refs(path);
3340a86c6181SAlex Tomas 		kfree(path);
3341a86c6181SAlex Tomas 	}
3342a86c6181SAlex Tomas 	return err ? err : allocated;
3343a86c6181SAlex Tomas }
3344a86c6181SAlex Tomas 
3345cf108bcaSJan Kara void ext4_ext_truncate(struct inode *inode)
3346a86c6181SAlex Tomas {
3347a86c6181SAlex Tomas 	struct address_space *mapping = inode->i_mapping;
3348a86c6181SAlex Tomas 	struct super_block *sb = inode->i_sb;
3349725d26d3SAneesh Kumar K.V 	ext4_lblk_t last_block;
3350a86c6181SAlex Tomas 	handle_t *handle;
3351a86c6181SAlex Tomas 	int err = 0;
3352a86c6181SAlex Tomas 
3353a86c6181SAlex Tomas 	/*
3354a86c6181SAlex Tomas 	 * probably first extent we're gonna free will be last in block
3355a86c6181SAlex Tomas 	 */
3356f3bd1f3fSMingming Cao 	err = ext4_writepage_trans_blocks(inode);
3357a86c6181SAlex Tomas 	handle = ext4_journal_start(inode, err);
3358cf108bcaSJan Kara 	if (IS_ERR(handle))
3359a86c6181SAlex Tomas 		return;
3360a86c6181SAlex Tomas 
3361cf108bcaSJan Kara 	if (inode->i_size & (sb->s_blocksize - 1))
3362cf108bcaSJan Kara 		ext4_block_truncate_page(handle, mapping, inode->i_size);
3363a86c6181SAlex Tomas 
33649ddfc3dcSJan Kara 	if (ext4_orphan_add(handle, inode))
33659ddfc3dcSJan Kara 		goto out_stop;
33669ddfc3dcSJan Kara 
33670e855ac8SAneesh Kumar K.V 	down_write(&EXT4_I(inode)->i_data_sem);
3368a86c6181SAlex Tomas 	ext4_ext_invalidate_cache(inode);
3369a86c6181SAlex Tomas 
3370c2ea3fdeSTheodore Ts'o 	ext4_discard_preallocations(inode);
3371c9de560dSAlex Tomas 
3372a86c6181SAlex Tomas 	/*
3373d0d856e8SRandy Dunlap 	 * TODO: optimization is possible here.
3374d0d856e8SRandy Dunlap 	 * Probably we need not scan at all,
3375d0d856e8SRandy Dunlap 	 * because page truncation is enough.
3376a86c6181SAlex Tomas 	 */
3377a86c6181SAlex Tomas 
3378a86c6181SAlex Tomas 	/* we have to know where to truncate from in crash case */
3379a86c6181SAlex Tomas 	EXT4_I(inode)->i_disksize = inode->i_size;
3380a86c6181SAlex Tomas 	ext4_mark_inode_dirty(handle, inode);
3381a86c6181SAlex Tomas 
3382a86c6181SAlex Tomas 	last_block = (inode->i_size + sb->s_blocksize - 1)
3383a86c6181SAlex Tomas 			>> EXT4_BLOCK_SIZE_BITS(sb);
3384a86c6181SAlex Tomas 	err = ext4_ext_remove_space(inode, last_block);
3385a86c6181SAlex Tomas 
3386a86c6181SAlex Tomas 	/* In a multi-transaction truncate, we only make the final
338756055d3aSAmit Arora 	 * transaction synchronous.
338856055d3aSAmit Arora 	 */
3389a86c6181SAlex Tomas 	if (IS_SYNC(inode))
33900390131bSFrank Mayhar 		ext4_handle_sync(handle);
3391a86c6181SAlex Tomas 
3392a86c6181SAlex Tomas out_stop:
33939ddfc3dcSJan Kara 	up_write(&EXT4_I(inode)->i_data_sem);
3394a86c6181SAlex Tomas 	/*
3395d0d856e8SRandy Dunlap 	 * If this was a simple ftruncate() and the file will remain alive,
3396a86c6181SAlex Tomas 	 * then we need to clear up the orphan record which we created above.
3397a86c6181SAlex Tomas 	 * However, if this was a real unlink then we were called by
3398a86c6181SAlex Tomas 	 * ext4_delete_inode(), and we allow that function to clean up the
3399a86c6181SAlex Tomas 	 * orphan info for us.
3400a86c6181SAlex Tomas 	 */
3401a86c6181SAlex Tomas 	if (inode->i_nlink)
3402a86c6181SAlex Tomas 		ext4_orphan_del(handle, inode);
3403a86c6181SAlex Tomas 
3404ef737728SSolofo Ramangalahy 	inode->i_mtime = inode->i_ctime = ext4_current_time(inode);
3405ef737728SSolofo Ramangalahy 	ext4_mark_inode_dirty(handle, inode);
3406a86c6181SAlex Tomas 	ext4_journal_stop(handle);
3407a86c6181SAlex Tomas }
3408a86c6181SAlex Tomas 
3409fd28784aSAneesh Kumar K.V static void ext4_falloc_update_inode(struct inode *inode,
3410fd28784aSAneesh Kumar K.V 				int mode, loff_t new_size, int update_ctime)
3411fd28784aSAneesh Kumar K.V {
3412fd28784aSAneesh Kumar K.V 	struct timespec now;
3413fd28784aSAneesh Kumar K.V 
3414fd28784aSAneesh Kumar K.V 	if (update_ctime) {
3415fd28784aSAneesh Kumar K.V 		now = current_fs_time(inode->i_sb);
3416fd28784aSAneesh Kumar K.V 		if (!timespec_equal(&inode->i_ctime, &now))
3417fd28784aSAneesh Kumar K.V 			inode->i_ctime = now;
3418fd28784aSAneesh Kumar K.V 	}
3419fd28784aSAneesh Kumar K.V 	/*
3420fd28784aSAneesh Kumar K.V 	 * Update only when preallocation was requested beyond
3421fd28784aSAneesh Kumar K.V 	 * the file size.
3422fd28784aSAneesh Kumar K.V 	 */
3423cf17fea6SAneesh Kumar K.V 	if (!(mode & FALLOC_FL_KEEP_SIZE)) {
3424cf17fea6SAneesh Kumar K.V 		if (new_size > i_size_read(inode))
3425fd28784aSAneesh Kumar K.V 			i_size_write(inode, new_size);
3426cf17fea6SAneesh Kumar K.V 		if (new_size > EXT4_I(inode)->i_disksize)
3427cf17fea6SAneesh Kumar K.V 			ext4_update_i_disksize(inode, new_size);
3428fd28784aSAneesh Kumar K.V 	}
3429fd28784aSAneesh Kumar K.V 
3430fd28784aSAneesh Kumar K.V }
3431fd28784aSAneesh Kumar K.V 
3432a2df2a63SAmit Arora /*
3433a2df2a63SAmit Arora  * preallocate space for a file. This implements ext4's fallocate inode
3434a2df2a63SAmit Arora  * operation, which gets called from sys_fallocate system call.
3435a2df2a63SAmit Arora  * For block-mapped files, posix_fallocate should fall back to the method
3436a2df2a63SAmit Arora  * of writing zeroes to the required new blocks (the same behavior which is
3437a2df2a63SAmit Arora  * expected for file systems which do not support fallocate() system call).
3438a2df2a63SAmit Arora  */
3439a2df2a63SAmit Arora long ext4_fallocate(struct inode *inode, int mode, loff_t offset, loff_t len)
3440a2df2a63SAmit Arora {
3441a2df2a63SAmit Arora 	handle_t *handle;
3442725d26d3SAneesh Kumar K.V 	ext4_lblk_t block;
3443fd28784aSAneesh Kumar K.V 	loff_t new_size;
3444498e5f24STheodore Ts'o 	unsigned int max_blocks;
3445a2df2a63SAmit Arora 	int ret = 0;
3446a2df2a63SAmit Arora 	int ret2 = 0;
3447a2df2a63SAmit Arora 	int retries = 0;
3448a2df2a63SAmit Arora 	struct buffer_head map_bh;
3449a2df2a63SAmit Arora 	unsigned int credits, blkbits = inode->i_blkbits;
3450a2df2a63SAmit Arora 
3451a2df2a63SAmit Arora 	/*
3452a2df2a63SAmit Arora 	 * currently supporting (pre)allocate mode for extent-based
3453a2df2a63SAmit Arora 	 * files _only_
3454a2df2a63SAmit Arora 	 */
3455a2df2a63SAmit Arora 	if (!(EXT4_I(inode)->i_flags & EXT4_EXTENTS_FL))
3456a2df2a63SAmit Arora 		return -EOPNOTSUPP;
3457a2df2a63SAmit Arora 
3458a2df2a63SAmit Arora 	/* preallocation to directories is currently not supported */
3459a2df2a63SAmit Arora 	if (S_ISDIR(inode->i_mode))
3460a2df2a63SAmit Arora 		return -ENODEV;
3461a2df2a63SAmit Arora 
3462a2df2a63SAmit Arora 	block = offset >> blkbits;
3463fd28784aSAneesh Kumar K.V 	/*
3464fd28784aSAneesh Kumar K.V 	 * We can't just convert len to max_blocks because
3465fd28784aSAneesh Kumar K.V 	 * If blocksize = 4096 offset = 3072 and len = 2048
3466fd28784aSAneesh Kumar K.V 	 */
3467a2df2a63SAmit Arora 	max_blocks = (EXT4_BLOCK_ALIGN(len + offset, blkbits) >> blkbits)
3468a2df2a63SAmit Arora 							- block;
3469a2df2a63SAmit Arora 	/*
3470f3bd1f3fSMingming Cao 	 * credits to insert 1 extent into extent tree
3471a2df2a63SAmit Arora 	 */
3472f3bd1f3fSMingming Cao 	credits = ext4_chunk_trans_blocks(inode, max_blocks);
347355bd725aSAneesh Kumar K.V 	mutex_lock(&inode->i_mutex);
3474a2df2a63SAmit Arora retry:
3475a2df2a63SAmit Arora 	while (ret >= 0 && ret < max_blocks) {
3476a2df2a63SAmit Arora 		block = block + ret;
3477a2df2a63SAmit Arora 		max_blocks = max_blocks - ret;
3478a2df2a63SAmit Arora 		handle = ext4_journal_start(inode, credits);
3479a2df2a63SAmit Arora 		if (IS_ERR(handle)) {
3480a2df2a63SAmit Arora 			ret = PTR_ERR(handle);
3481a2df2a63SAmit Arora 			break;
3482a2df2a63SAmit Arora 		}
348379ffab34SAneesh Kumar K.V 		map_bh.b_state = 0;
348412b7ac17STheodore Ts'o 		ret = ext4_get_blocks(handle, inode, block,
3485a2df2a63SAmit Arora 				      max_blocks, &map_bh,
3486c2177057STheodore Ts'o 				      EXT4_GET_BLOCKS_CREATE_UNINIT_EXT);
3487221879c9SAneesh Kumar K.V 		if (ret <= 0) {
34882c98615dSAneesh Kumar K.V #ifdef EXT4FS_DEBUG
34892c98615dSAneesh Kumar K.V 			WARN_ON(ret <= 0);
34902c98615dSAneesh Kumar K.V 			printk(KERN_ERR "%s: ext4_ext_get_blocks "
34912c98615dSAneesh Kumar K.V 				    "returned error inode#%lu, block=%u, "
34929fd9784cSThadeu Lima de Souza Cascardo 				    "max_blocks=%u", __func__,
3493bba90743SEric Sandeen 				    inode->i_ino, block, max_blocks);
34942c98615dSAneesh Kumar K.V #endif
3495a2df2a63SAmit Arora 			ext4_mark_inode_dirty(handle, inode);
3496a2df2a63SAmit Arora 			ret2 = ext4_journal_stop(handle);
3497a2df2a63SAmit Arora 			break;
3498a2df2a63SAmit Arora 		}
3499fd28784aSAneesh Kumar K.V 		if ((block + ret) >= (EXT4_BLOCK_ALIGN(offset + len,
3500fd28784aSAneesh Kumar K.V 						blkbits) >> blkbits))
3501fd28784aSAneesh Kumar K.V 			new_size = offset + len;
3502fd28784aSAneesh Kumar K.V 		else
3503fd28784aSAneesh Kumar K.V 			new_size = (block + ret) << blkbits;
3504a2df2a63SAmit Arora 
3505fd28784aSAneesh Kumar K.V 		ext4_falloc_update_inode(inode, mode, new_size,
3506fd28784aSAneesh Kumar K.V 						buffer_new(&map_bh));
3507a2df2a63SAmit Arora 		ext4_mark_inode_dirty(handle, inode);
3508a2df2a63SAmit Arora 		ret2 = ext4_journal_stop(handle);
3509a2df2a63SAmit Arora 		if (ret2)
3510a2df2a63SAmit Arora 			break;
3511a2df2a63SAmit Arora 	}
3512fd28784aSAneesh Kumar K.V 	if (ret == -ENOSPC &&
3513fd28784aSAneesh Kumar K.V 			ext4_should_retry_alloc(inode->i_sb, &retries)) {
3514fd28784aSAneesh Kumar K.V 		ret = 0;
3515a2df2a63SAmit Arora 		goto retry;
3516a2df2a63SAmit Arora 	}
351755bd725aSAneesh Kumar K.V 	mutex_unlock(&inode->i_mutex);
3518a2df2a63SAmit Arora 	return ret > 0 ? ret2 : ret;
3519a2df2a63SAmit Arora }
35206873fa0dSEric Sandeen 
35216873fa0dSEric Sandeen /*
35220031462bSMingming Cao  * This function convert a range of blocks to written extents
35230031462bSMingming Cao  * The caller of this function will pass the start offset and the size.
35240031462bSMingming Cao  * all unwritten extents within this range will be converted to
35250031462bSMingming Cao  * written extents.
35260031462bSMingming Cao  *
35270031462bSMingming Cao  * This function is called from the direct IO end io call back
35280031462bSMingming Cao  * function, to convert the fallocated extents after IO is completed.
3529109f5565SMingming  * Returns 0 on success.
35300031462bSMingming Cao  */
35310031462bSMingming Cao int ext4_convert_unwritten_extents(struct inode *inode, loff_t offset,
35320031462bSMingming Cao 				    loff_t len)
35330031462bSMingming Cao {
35340031462bSMingming Cao 	handle_t *handle;
35350031462bSMingming Cao 	ext4_lblk_t block;
35360031462bSMingming Cao 	unsigned int max_blocks;
35370031462bSMingming Cao 	int ret = 0;
35380031462bSMingming Cao 	int ret2 = 0;
35390031462bSMingming Cao 	struct buffer_head map_bh;
35400031462bSMingming Cao 	unsigned int credits, blkbits = inode->i_blkbits;
35410031462bSMingming Cao 
35420031462bSMingming Cao 	block = offset >> blkbits;
35430031462bSMingming Cao 	/*
35440031462bSMingming Cao 	 * We can't just convert len to max_blocks because
35450031462bSMingming Cao 	 * If blocksize = 4096 offset = 3072 and len = 2048
35460031462bSMingming Cao 	 */
35470031462bSMingming Cao 	max_blocks = (EXT4_BLOCK_ALIGN(len + offset, blkbits) >> blkbits)
35480031462bSMingming Cao 							- block;
35490031462bSMingming Cao 	/*
35500031462bSMingming Cao 	 * credits to insert 1 extent into extent tree
35510031462bSMingming Cao 	 */
35520031462bSMingming Cao 	credits = ext4_chunk_trans_blocks(inode, max_blocks);
35530031462bSMingming Cao 	while (ret >= 0 && ret < max_blocks) {
35540031462bSMingming Cao 		block = block + ret;
35550031462bSMingming Cao 		max_blocks = max_blocks - ret;
35560031462bSMingming Cao 		handle = ext4_journal_start(inode, credits);
35570031462bSMingming Cao 		if (IS_ERR(handle)) {
35580031462bSMingming Cao 			ret = PTR_ERR(handle);
35590031462bSMingming Cao 			break;
35600031462bSMingming Cao 		}
35610031462bSMingming Cao 		map_bh.b_state = 0;
35620031462bSMingming Cao 		ret = ext4_get_blocks(handle, inode, block,
35630031462bSMingming Cao 				      max_blocks, &map_bh,
35640031462bSMingming Cao 				      EXT4_GET_BLOCKS_DIO_CONVERT_EXT);
35650031462bSMingming Cao 		if (ret <= 0) {
35660031462bSMingming Cao 			WARN_ON(ret <= 0);
35670031462bSMingming Cao 			printk(KERN_ERR "%s: ext4_ext_get_blocks "
35680031462bSMingming Cao 				    "returned error inode#%lu, block=%u, "
35690031462bSMingming Cao 				    "max_blocks=%u", __func__,
35700031462bSMingming Cao 				    inode->i_ino, block, max_blocks);
35710031462bSMingming Cao 		}
35720031462bSMingming Cao 		ext4_mark_inode_dirty(handle, inode);
35730031462bSMingming Cao 		ret2 = ext4_journal_stop(handle);
35740031462bSMingming Cao 		if (ret <= 0 || ret2 )
35750031462bSMingming Cao 			break;
35760031462bSMingming Cao 	}
35770031462bSMingming Cao 	return ret > 0 ? ret2 : ret;
35780031462bSMingming Cao }
35790031462bSMingming Cao /*
35806873fa0dSEric Sandeen  * Callback function called for each extent to gather FIEMAP information.
35816873fa0dSEric Sandeen  */
35823a06d778SAneesh Kumar K.V static int ext4_ext_fiemap_cb(struct inode *inode, struct ext4_ext_path *path,
35836873fa0dSEric Sandeen 		       struct ext4_ext_cache *newex, struct ext4_extent *ex,
35846873fa0dSEric Sandeen 		       void *data)
35856873fa0dSEric Sandeen {
35866873fa0dSEric Sandeen 	struct fiemap_extent_info *fieinfo = data;
3587c9877b20SEric Sandeen 	unsigned char blksize_bits = inode->i_sb->s_blocksize_bits;
35886873fa0dSEric Sandeen 	__u64	logical;
35896873fa0dSEric Sandeen 	__u64	physical;
35906873fa0dSEric Sandeen 	__u64	length;
35916873fa0dSEric Sandeen 	__u32	flags = 0;
35926873fa0dSEric Sandeen 	int	error;
35936873fa0dSEric Sandeen 
35946873fa0dSEric Sandeen 	logical =  (__u64)newex->ec_block << blksize_bits;
35956873fa0dSEric Sandeen 
35966873fa0dSEric Sandeen 	if (newex->ec_type == EXT4_EXT_CACHE_GAP) {
35976873fa0dSEric Sandeen 		pgoff_t offset;
35986873fa0dSEric Sandeen 		struct page *page;
35996873fa0dSEric Sandeen 		struct buffer_head *bh = NULL;
36006873fa0dSEric Sandeen 
36016873fa0dSEric Sandeen 		offset = logical >> PAGE_SHIFT;
36026873fa0dSEric Sandeen 		page = find_get_page(inode->i_mapping, offset);
36036873fa0dSEric Sandeen 		if (!page || !page_has_buffers(page))
36046873fa0dSEric Sandeen 			return EXT_CONTINUE;
36056873fa0dSEric Sandeen 
36066873fa0dSEric Sandeen 		bh = page_buffers(page);
36076873fa0dSEric Sandeen 
36086873fa0dSEric Sandeen 		if (!bh)
36096873fa0dSEric Sandeen 			return EXT_CONTINUE;
36106873fa0dSEric Sandeen 
36116873fa0dSEric Sandeen 		if (buffer_delay(bh)) {
36126873fa0dSEric Sandeen 			flags |= FIEMAP_EXTENT_DELALLOC;
36136873fa0dSEric Sandeen 			page_cache_release(page);
36146873fa0dSEric Sandeen 		} else {
36156873fa0dSEric Sandeen 			page_cache_release(page);
36166873fa0dSEric Sandeen 			return EXT_CONTINUE;
36176873fa0dSEric Sandeen 		}
36186873fa0dSEric Sandeen 	}
36196873fa0dSEric Sandeen 
36206873fa0dSEric Sandeen 	physical = (__u64)newex->ec_start << blksize_bits;
36216873fa0dSEric Sandeen 	length =   (__u64)newex->ec_len << blksize_bits;
36226873fa0dSEric Sandeen 
36236873fa0dSEric Sandeen 	if (ex && ext4_ext_is_uninitialized(ex))
36246873fa0dSEric Sandeen 		flags |= FIEMAP_EXTENT_UNWRITTEN;
36256873fa0dSEric Sandeen 
36266873fa0dSEric Sandeen 	/*
36276873fa0dSEric Sandeen 	 * If this extent reaches EXT_MAX_BLOCK, it must be last.
36286873fa0dSEric Sandeen 	 *
36296873fa0dSEric Sandeen 	 * Or if ext4_ext_next_allocated_block is EXT_MAX_BLOCK,
36306873fa0dSEric Sandeen 	 * this also indicates no more allocated blocks.
36316873fa0dSEric Sandeen 	 *
36326873fa0dSEric Sandeen 	 * XXX this might miss a single-block extent at EXT_MAX_BLOCK
36336873fa0dSEric Sandeen 	 */
3634c9877b20SEric Sandeen 	if (ext4_ext_next_allocated_block(path) == EXT_MAX_BLOCK ||
3635eefd7f03STheodore Ts'o 	    newex->ec_block + newex->ec_len - 1 == EXT_MAX_BLOCK) {
3636eefd7f03STheodore Ts'o 		loff_t size = i_size_read(inode);
3637eefd7f03STheodore Ts'o 		loff_t bs = EXT4_BLOCK_SIZE(inode->i_sb);
3638eefd7f03STheodore Ts'o 
36396873fa0dSEric Sandeen 		flags |= FIEMAP_EXTENT_LAST;
3640eefd7f03STheodore Ts'o 		if ((flags & FIEMAP_EXTENT_DELALLOC) &&
3641eefd7f03STheodore Ts'o 		    logical+length > size)
3642eefd7f03STheodore Ts'o 			length = (size - logical + bs - 1) & ~(bs-1);
3643eefd7f03STheodore Ts'o 	}
36446873fa0dSEric Sandeen 
36456873fa0dSEric Sandeen 	error = fiemap_fill_next_extent(fieinfo, logical, physical,
36466873fa0dSEric Sandeen 					length, flags);
36476873fa0dSEric Sandeen 	if (error < 0)
36486873fa0dSEric Sandeen 		return error;
36496873fa0dSEric Sandeen 	if (error == 1)
36506873fa0dSEric Sandeen 		return EXT_BREAK;
36516873fa0dSEric Sandeen 
36526873fa0dSEric Sandeen 	return EXT_CONTINUE;
36536873fa0dSEric Sandeen }
36546873fa0dSEric Sandeen 
36556873fa0dSEric Sandeen /* fiemap flags we can handle specified here */
36566873fa0dSEric Sandeen #define EXT4_FIEMAP_FLAGS	(FIEMAP_FLAG_SYNC|FIEMAP_FLAG_XATTR)
36576873fa0dSEric Sandeen 
36583a06d778SAneesh Kumar K.V static int ext4_xattr_fiemap(struct inode *inode,
36593a06d778SAneesh Kumar K.V 				struct fiemap_extent_info *fieinfo)
36606873fa0dSEric Sandeen {
36616873fa0dSEric Sandeen 	__u64 physical = 0;
36626873fa0dSEric Sandeen 	__u64 length;
36636873fa0dSEric Sandeen 	__u32 flags = FIEMAP_EXTENT_LAST;
36646873fa0dSEric Sandeen 	int blockbits = inode->i_sb->s_blocksize_bits;
36656873fa0dSEric Sandeen 	int error = 0;
36666873fa0dSEric Sandeen 
36676873fa0dSEric Sandeen 	/* in-inode? */
36686873fa0dSEric Sandeen 	if (EXT4_I(inode)->i_state & EXT4_STATE_XATTR) {
36696873fa0dSEric Sandeen 		struct ext4_iloc iloc;
36706873fa0dSEric Sandeen 		int offset;	/* offset of xattr in inode */
36716873fa0dSEric Sandeen 
36726873fa0dSEric Sandeen 		error = ext4_get_inode_loc(inode, &iloc);
36736873fa0dSEric Sandeen 		if (error)
36746873fa0dSEric Sandeen 			return error;
36756873fa0dSEric Sandeen 		physical = iloc.bh->b_blocknr << blockbits;
36766873fa0dSEric Sandeen 		offset = EXT4_GOOD_OLD_INODE_SIZE +
36776873fa0dSEric Sandeen 				EXT4_I(inode)->i_extra_isize;
36786873fa0dSEric Sandeen 		physical += offset;
36796873fa0dSEric Sandeen 		length = EXT4_SB(inode->i_sb)->s_inode_size - offset;
36806873fa0dSEric Sandeen 		flags |= FIEMAP_EXTENT_DATA_INLINE;
36816873fa0dSEric Sandeen 	} else { /* external block */
36826873fa0dSEric Sandeen 		physical = EXT4_I(inode)->i_file_acl << blockbits;
36836873fa0dSEric Sandeen 		length = inode->i_sb->s_blocksize;
36846873fa0dSEric Sandeen 	}
36856873fa0dSEric Sandeen 
36866873fa0dSEric Sandeen 	if (physical)
36876873fa0dSEric Sandeen 		error = fiemap_fill_next_extent(fieinfo, 0, physical,
36886873fa0dSEric Sandeen 						length, flags);
36896873fa0dSEric Sandeen 	return (error < 0 ? error : 0);
36906873fa0dSEric Sandeen }
36916873fa0dSEric Sandeen 
36926873fa0dSEric Sandeen int ext4_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
36936873fa0dSEric Sandeen 		__u64 start, __u64 len)
36946873fa0dSEric Sandeen {
36956873fa0dSEric Sandeen 	ext4_lblk_t start_blk;
36966873fa0dSEric Sandeen 	ext4_lblk_t len_blks;
36976873fa0dSEric Sandeen 	int error = 0;
36986873fa0dSEric Sandeen 
36996873fa0dSEric Sandeen 	/* fallback to generic here if not in extents fmt */
37006873fa0dSEric Sandeen 	if (!(EXT4_I(inode)->i_flags & EXT4_EXTENTS_FL))
37016873fa0dSEric Sandeen 		return generic_block_fiemap(inode, fieinfo, start, len,
37026873fa0dSEric Sandeen 			ext4_get_block);
37036873fa0dSEric Sandeen 
37046873fa0dSEric Sandeen 	if (fiemap_check_flags(fieinfo, EXT4_FIEMAP_FLAGS))
37056873fa0dSEric Sandeen 		return -EBADR;
37066873fa0dSEric Sandeen 
37076873fa0dSEric Sandeen 	if (fieinfo->fi_flags & FIEMAP_FLAG_XATTR) {
37086873fa0dSEric Sandeen 		error = ext4_xattr_fiemap(inode, fieinfo);
37096873fa0dSEric Sandeen 	} else {
37106873fa0dSEric Sandeen 		start_blk = start >> inode->i_sb->s_blocksize_bits;
37116873fa0dSEric Sandeen 		len_blks = len >> inode->i_sb->s_blocksize_bits;
37126873fa0dSEric Sandeen 
37136873fa0dSEric Sandeen 		/*
37146873fa0dSEric Sandeen 		 * Walk the extent tree gathering extent information.
37156873fa0dSEric Sandeen 		 * ext4_ext_fiemap_cb will push extents back to user.
37166873fa0dSEric Sandeen 		 */
37170568c518STheodore Ts'o 		down_read(&EXT4_I(inode)->i_data_sem);
37186873fa0dSEric Sandeen 		error = ext4_ext_walk_space(inode, start_blk, len_blks,
37196873fa0dSEric Sandeen 					  ext4_ext_fiemap_cb, fieinfo);
37200568c518STheodore Ts'o 		up_read(&EXT4_I(inode)->i_data_sem);
37216873fa0dSEric Sandeen 	}
37226873fa0dSEric Sandeen 
37236873fa0dSEric Sandeen 	return error;
37246873fa0dSEric Sandeen }
37256873fa0dSEric Sandeen 
3726