xref: /openbmc/linux/fs/ext4/extents.c (revision 498e5f24158da7bf8fa48074a70e370e22844492)
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  */
5209b88252SAvantika Mathur static 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 
969102e4faSShen Feng static int ext4_ext_journal_restart(handle_t *handle, int needed)
97a86c6181SAlex Tomas {
98a86c6181SAlex Tomas 	int err;
99a86c6181SAlex Tomas 
1000390131bSFrank Mayhar 	if (!ext4_handle_valid(handle))
1010390131bSFrank Mayhar 		return 0;
102a86c6181SAlex Tomas 	if (handle->h_buffer_credits > needed)
1039102e4faSShen Feng 		return 0;
1049102e4faSShen Feng 	err = ext4_journal_extend(handle, needed);
1050123c939STheodore Ts'o 	if (err <= 0)
1069102e4faSShen Feng 		return err;
1079102e4faSShen Feng 	return ext4_journal_restart(handle, needed);
108a86c6181SAlex Tomas }
109a86c6181SAlex Tomas 
110a86c6181SAlex Tomas /*
111a86c6181SAlex Tomas  * could return:
112a86c6181SAlex Tomas  *  - EROFS
113a86c6181SAlex Tomas  *  - ENOMEM
114a86c6181SAlex Tomas  */
115a86c6181SAlex Tomas static int ext4_ext_get_access(handle_t *handle, struct inode *inode,
116a86c6181SAlex Tomas 				struct ext4_ext_path *path)
117a86c6181SAlex Tomas {
118a86c6181SAlex Tomas 	if (path->p_bh) {
119a86c6181SAlex Tomas 		/* path points to block */
120a86c6181SAlex Tomas 		return ext4_journal_get_write_access(handle, path->p_bh);
121a86c6181SAlex Tomas 	}
122a86c6181SAlex Tomas 	/* path points to leaf/index in inode body */
123a86c6181SAlex Tomas 	/* we use in-core data, no need to protect them */
124a86c6181SAlex Tomas 	return 0;
125a86c6181SAlex Tomas }
126a86c6181SAlex Tomas 
127a86c6181SAlex Tomas /*
128a86c6181SAlex Tomas  * could return:
129a86c6181SAlex Tomas  *  - EROFS
130a86c6181SAlex Tomas  *  - ENOMEM
131a86c6181SAlex Tomas  *  - EIO
132a86c6181SAlex Tomas  */
133a86c6181SAlex Tomas static int ext4_ext_dirty(handle_t *handle, struct inode *inode,
134a86c6181SAlex Tomas 				struct ext4_ext_path *path)
135a86c6181SAlex Tomas {
136a86c6181SAlex Tomas 	int err;
137a86c6181SAlex Tomas 	if (path->p_bh) {
138a86c6181SAlex Tomas 		/* path points to block */
1390390131bSFrank Mayhar 		err = ext4_handle_dirty_metadata(handle, inode, path->p_bh);
140a86c6181SAlex Tomas 	} else {
141a86c6181SAlex Tomas 		/* path points to leaf/index in inode body */
142a86c6181SAlex Tomas 		err = ext4_mark_inode_dirty(handle, inode);
143a86c6181SAlex Tomas 	}
144a86c6181SAlex Tomas 	return err;
145a86c6181SAlex Tomas }
146a86c6181SAlex Tomas 
147f65e6fbaSAlex Tomas static ext4_fsblk_t ext4_ext_find_goal(struct inode *inode,
148a86c6181SAlex Tomas 			      struct ext4_ext_path *path,
149725d26d3SAneesh Kumar K.V 			      ext4_lblk_t block)
150a86c6181SAlex Tomas {
151a86c6181SAlex Tomas 	struct ext4_inode_info *ei = EXT4_I(inode);
152f65e6fbaSAlex Tomas 	ext4_fsblk_t bg_start;
15374d3487fSValerie Clement 	ext4_fsblk_t last_block;
154f65e6fbaSAlex Tomas 	ext4_grpblk_t colour;
155a86c6181SAlex Tomas 	int depth;
156a86c6181SAlex Tomas 
157a86c6181SAlex Tomas 	if (path) {
158a86c6181SAlex Tomas 		struct ext4_extent *ex;
159a86c6181SAlex Tomas 		depth = path->p_depth;
160a86c6181SAlex Tomas 
161a86c6181SAlex Tomas 		/* try to predict block placement */
1627e028976SAvantika Mathur 		ex = path[depth].p_ext;
1637e028976SAvantika Mathur 		if (ex)
164f65e6fbaSAlex Tomas 			return ext_pblock(ex)+(block-le32_to_cpu(ex->ee_block));
165a86c6181SAlex Tomas 
166d0d856e8SRandy Dunlap 		/* it looks like index is empty;
167d0d856e8SRandy Dunlap 		 * try to find starting block from index itself */
168a86c6181SAlex Tomas 		if (path[depth].p_bh)
169a86c6181SAlex Tomas 			return path[depth].p_bh->b_blocknr;
170a86c6181SAlex Tomas 	}
171a86c6181SAlex Tomas 
172a86c6181SAlex Tomas 	/* OK. use inode's group */
173a86c6181SAlex Tomas 	bg_start = (ei->i_block_group * EXT4_BLOCKS_PER_GROUP(inode->i_sb)) +
174a86c6181SAlex Tomas 		le32_to_cpu(EXT4_SB(inode->i_sb)->s_es->s_first_data_block);
17574d3487fSValerie Clement 	last_block = ext4_blocks_count(EXT4_SB(inode->i_sb)->s_es) - 1;
17674d3487fSValerie Clement 
17774d3487fSValerie Clement 	if (bg_start + EXT4_BLOCKS_PER_GROUP(inode->i_sb) <= last_block)
178a86c6181SAlex Tomas 		colour = (current->pid % 16) *
179a86c6181SAlex Tomas 			(EXT4_BLOCKS_PER_GROUP(inode->i_sb) / 16);
18074d3487fSValerie Clement 	else
18174d3487fSValerie Clement 		colour = (current->pid % 16) * ((last_block - bg_start) / 16);
182a86c6181SAlex Tomas 	return bg_start + colour + block;
183a86c6181SAlex Tomas }
184a86c6181SAlex Tomas 
185654b4908SAneesh Kumar K.V /*
186654b4908SAneesh Kumar K.V  * Allocation for a meta data block
187654b4908SAneesh Kumar K.V  */
188f65e6fbaSAlex Tomas static ext4_fsblk_t
189654b4908SAneesh Kumar K.V ext4_ext_new_meta_block(handle_t *handle, struct inode *inode,
190a86c6181SAlex Tomas 			struct ext4_ext_path *path,
191a86c6181SAlex Tomas 			struct ext4_extent *ex, int *err)
192a86c6181SAlex Tomas {
193f65e6fbaSAlex Tomas 	ext4_fsblk_t goal, newblock;
194a86c6181SAlex Tomas 
195a86c6181SAlex Tomas 	goal = ext4_ext_find_goal(inode, path, le32_to_cpu(ex->ee_block));
19697df5d15STheodore Ts'o 	newblock = ext4_new_meta_blocks(handle, inode, goal, NULL, err);
197a86c6181SAlex Tomas 	return newblock;
198a86c6181SAlex Tomas }
199a86c6181SAlex Tomas 
20009b88252SAvantika Mathur static int ext4_ext_space_block(struct inode *inode)
201a86c6181SAlex Tomas {
202a86c6181SAlex Tomas 	int size;
203a86c6181SAlex Tomas 
204a86c6181SAlex Tomas 	size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
205a86c6181SAlex Tomas 			/ sizeof(struct ext4_extent);
206bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST
207a86c6181SAlex Tomas 	if (size > 6)
208a86c6181SAlex Tomas 		size = 6;
209a86c6181SAlex Tomas #endif
210a86c6181SAlex Tomas 	return size;
211a86c6181SAlex Tomas }
212a86c6181SAlex Tomas 
21309b88252SAvantika Mathur static int ext4_ext_space_block_idx(struct inode *inode)
214a86c6181SAlex Tomas {
215a86c6181SAlex Tomas 	int size;
216a86c6181SAlex Tomas 
217a86c6181SAlex Tomas 	size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
218a86c6181SAlex Tomas 			/ sizeof(struct ext4_extent_idx);
219bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST
220a86c6181SAlex Tomas 	if (size > 5)
221a86c6181SAlex Tomas 		size = 5;
222a86c6181SAlex Tomas #endif
223a86c6181SAlex Tomas 	return size;
224a86c6181SAlex Tomas }
225a86c6181SAlex Tomas 
22609b88252SAvantika Mathur static int ext4_ext_space_root(struct inode *inode)
227a86c6181SAlex Tomas {
228a86c6181SAlex Tomas 	int size;
229a86c6181SAlex Tomas 
230a86c6181SAlex Tomas 	size = sizeof(EXT4_I(inode)->i_data);
231a86c6181SAlex Tomas 	size -= sizeof(struct ext4_extent_header);
232a86c6181SAlex Tomas 	size /= sizeof(struct ext4_extent);
233bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST
234a86c6181SAlex Tomas 	if (size > 3)
235a86c6181SAlex Tomas 		size = 3;
236a86c6181SAlex Tomas #endif
237a86c6181SAlex Tomas 	return size;
238a86c6181SAlex Tomas }
239a86c6181SAlex Tomas 
24009b88252SAvantika Mathur static int ext4_ext_space_root_idx(struct inode *inode)
241a86c6181SAlex Tomas {
242a86c6181SAlex Tomas 	int size;
243a86c6181SAlex Tomas 
244a86c6181SAlex Tomas 	size = sizeof(EXT4_I(inode)->i_data);
245a86c6181SAlex Tomas 	size -= sizeof(struct ext4_extent_header);
246a86c6181SAlex Tomas 	size /= sizeof(struct ext4_extent_idx);
247bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST
248a86c6181SAlex Tomas 	if (size > 4)
249a86c6181SAlex Tomas 		size = 4;
250a86c6181SAlex Tomas #endif
251a86c6181SAlex Tomas 	return size;
252a86c6181SAlex Tomas }
253a86c6181SAlex Tomas 
254d2a17637SMingming Cao /*
255d2a17637SMingming Cao  * Calculate the number of metadata blocks needed
256d2a17637SMingming Cao  * to allocate @blocks
257d2a17637SMingming Cao  * Worse case is one block per extent
258d2a17637SMingming Cao  */
259d2a17637SMingming Cao int ext4_ext_calc_metadata_amount(struct inode *inode, int blocks)
260d2a17637SMingming Cao {
261d2a17637SMingming Cao 	int lcap, icap, rcap, leafs, idxs, num;
262d2a17637SMingming Cao 	int newextents = blocks;
263d2a17637SMingming Cao 
264d2a17637SMingming Cao 	rcap = ext4_ext_space_root_idx(inode);
265d2a17637SMingming Cao 	lcap = ext4_ext_space_block(inode);
266d2a17637SMingming Cao 	icap = ext4_ext_space_block_idx(inode);
267d2a17637SMingming Cao 
268d2a17637SMingming Cao 	/* number of new leaf blocks needed */
269d2a17637SMingming Cao 	num = leafs = (newextents + lcap - 1) / lcap;
270d2a17637SMingming Cao 
271d2a17637SMingming Cao 	/*
272d2a17637SMingming Cao 	 * Worse case, we need separate index block(s)
273d2a17637SMingming Cao 	 * to link all new leaf blocks
274d2a17637SMingming Cao 	 */
275d2a17637SMingming Cao 	idxs = (leafs + icap - 1) / icap;
276d2a17637SMingming Cao 	do {
277d2a17637SMingming Cao 		num += idxs;
278d2a17637SMingming Cao 		idxs = (idxs + icap - 1) / icap;
279d2a17637SMingming Cao 	} while (idxs > rcap);
280d2a17637SMingming Cao 
281d2a17637SMingming Cao 	return num;
282d2a17637SMingming Cao }
283d2a17637SMingming Cao 
284c29c0ae7SAlex Tomas static int
285c29c0ae7SAlex Tomas ext4_ext_max_entries(struct inode *inode, int depth)
286c29c0ae7SAlex Tomas {
287c29c0ae7SAlex Tomas 	int max;
288c29c0ae7SAlex Tomas 
289c29c0ae7SAlex Tomas 	if (depth == ext_depth(inode)) {
290c29c0ae7SAlex Tomas 		if (depth == 0)
291c29c0ae7SAlex Tomas 			max = ext4_ext_space_root(inode);
292c29c0ae7SAlex Tomas 		else
293c29c0ae7SAlex Tomas 			max = ext4_ext_space_root_idx(inode);
294c29c0ae7SAlex Tomas 	} else {
295c29c0ae7SAlex Tomas 		if (depth == 0)
296c29c0ae7SAlex Tomas 			max = ext4_ext_space_block(inode);
297c29c0ae7SAlex Tomas 		else
298c29c0ae7SAlex Tomas 			max = ext4_ext_space_block_idx(inode);
299c29c0ae7SAlex Tomas 	}
300c29c0ae7SAlex Tomas 
301c29c0ae7SAlex Tomas 	return max;
302c29c0ae7SAlex Tomas }
303c29c0ae7SAlex Tomas 
304c29c0ae7SAlex Tomas static int __ext4_ext_check_header(const char *function, struct inode *inode,
305c29c0ae7SAlex Tomas 					struct ext4_extent_header *eh,
306c29c0ae7SAlex Tomas 					int depth)
307c29c0ae7SAlex Tomas {
308c29c0ae7SAlex Tomas 	const char *error_msg;
309c29c0ae7SAlex Tomas 	int max = 0;
310c29c0ae7SAlex Tomas 
311c29c0ae7SAlex Tomas 	if (unlikely(eh->eh_magic != EXT4_EXT_MAGIC)) {
312c29c0ae7SAlex Tomas 		error_msg = "invalid magic";
313c29c0ae7SAlex Tomas 		goto corrupted;
314c29c0ae7SAlex Tomas 	}
315c29c0ae7SAlex Tomas 	if (unlikely(le16_to_cpu(eh->eh_depth) != depth)) {
316c29c0ae7SAlex Tomas 		error_msg = "unexpected eh_depth";
317c29c0ae7SAlex Tomas 		goto corrupted;
318c29c0ae7SAlex Tomas 	}
319c29c0ae7SAlex Tomas 	if (unlikely(eh->eh_max == 0)) {
320c29c0ae7SAlex Tomas 		error_msg = "invalid eh_max";
321c29c0ae7SAlex Tomas 		goto corrupted;
322c29c0ae7SAlex Tomas 	}
323c29c0ae7SAlex Tomas 	max = ext4_ext_max_entries(inode, depth);
324c29c0ae7SAlex Tomas 	if (unlikely(le16_to_cpu(eh->eh_max) > max)) {
325c29c0ae7SAlex Tomas 		error_msg = "too large eh_max";
326c29c0ae7SAlex Tomas 		goto corrupted;
327c29c0ae7SAlex Tomas 	}
328c29c0ae7SAlex Tomas 	if (unlikely(le16_to_cpu(eh->eh_entries) > le16_to_cpu(eh->eh_max))) {
329c29c0ae7SAlex Tomas 		error_msg = "invalid eh_entries";
330c29c0ae7SAlex Tomas 		goto corrupted;
331c29c0ae7SAlex Tomas 	}
332c29c0ae7SAlex Tomas 	return 0;
333c29c0ae7SAlex Tomas 
334c29c0ae7SAlex Tomas corrupted:
335c29c0ae7SAlex Tomas 	ext4_error(inode->i_sb, function,
336c29c0ae7SAlex Tomas 			"bad header in inode #%lu: %s - magic %x, "
337c29c0ae7SAlex Tomas 			"entries %u, max %u(%u), depth %u(%u)",
338c29c0ae7SAlex Tomas 			inode->i_ino, error_msg, le16_to_cpu(eh->eh_magic),
339c29c0ae7SAlex Tomas 			le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max),
340c29c0ae7SAlex Tomas 			max, le16_to_cpu(eh->eh_depth), depth);
341c29c0ae7SAlex Tomas 
342c29c0ae7SAlex Tomas 	return -EIO;
343c29c0ae7SAlex Tomas }
344c29c0ae7SAlex Tomas 
345c29c0ae7SAlex Tomas #define ext4_ext_check_header(inode, eh, depth)	\
34646e665e9SHarvey Harrison 	__ext4_ext_check_header(__func__, inode, eh, depth)
347c29c0ae7SAlex Tomas 
348a86c6181SAlex Tomas #ifdef EXT_DEBUG
349a86c6181SAlex Tomas static void ext4_ext_show_path(struct inode *inode, struct ext4_ext_path *path)
350a86c6181SAlex Tomas {
351a86c6181SAlex Tomas 	int k, l = path->p_depth;
352a86c6181SAlex Tomas 
353a86c6181SAlex Tomas 	ext_debug("path:");
354a86c6181SAlex Tomas 	for (k = 0; k <= l; k++, path++) {
355a86c6181SAlex Tomas 		if (path->p_idx) {
3562ae02107SMingming Cao 		  ext_debug("  %d->%llu", le32_to_cpu(path->p_idx->ei_block),
357f65e6fbaSAlex Tomas 			    idx_pblock(path->p_idx));
358a86c6181SAlex Tomas 		} else if (path->p_ext) {
3592ae02107SMingming Cao 			ext_debug("  %d:%d:%llu ",
360a86c6181SAlex Tomas 				  le32_to_cpu(path->p_ext->ee_block),
361a2df2a63SAmit Arora 				  ext4_ext_get_actual_len(path->p_ext),
362f65e6fbaSAlex Tomas 				  ext_pblock(path->p_ext));
363a86c6181SAlex Tomas 		} else
364a86c6181SAlex Tomas 			ext_debug("  []");
365a86c6181SAlex Tomas 	}
366a86c6181SAlex Tomas 	ext_debug("\n");
367a86c6181SAlex Tomas }
368a86c6181SAlex Tomas 
369a86c6181SAlex Tomas static void ext4_ext_show_leaf(struct inode *inode, struct ext4_ext_path *path)
370a86c6181SAlex Tomas {
371a86c6181SAlex Tomas 	int depth = ext_depth(inode);
372a86c6181SAlex Tomas 	struct ext4_extent_header *eh;
373a86c6181SAlex Tomas 	struct ext4_extent *ex;
374a86c6181SAlex Tomas 	int i;
375a86c6181SAlex Tomas 
376a86c6181SAlex Tomas 	if (!path)
377a86c6181SAlex Tomas 		return;
378a86c6181SAlex Tomas 
379a86c6181SAlex Tomas 	eh = path[depth].p_hdr;
380a86c6181SAlex Tomas 	ex = EXT_FIRST_EXTENT(eh);
381a86c6181SAlex Tomas 
382a86c6181SAlex Tomas 	for (i = 0; i < le16_to_cpu(eh->eh_entries); i++, ex++) {
3832ae02107SMingming Cao 		ext_debug("%d:%d:%llu ", le32_to_cpu(ex->ee_block),
384a2df2a63SAmit Arora 			  ext4_ext_get_actual_len(ex), ext_pblock(ex));
385a86c6181SAlex Tomas 	}
386a86c6181SAlex Tomas 	ext_debug("\n");
387a86c6181SAlex Tomas }
388a86c6181SAlex Tomas #else
389a86c6181SAlex Tomas #define ext4_ext_show_path(inode, path)
390a86c6181SAlex Tomas #define ext4_ext_show_leaf(inode, path)
391a86c6181SAlex Tomas #endif
392a86c6181SAlex Tomas 
393b35905c1SAneesh Kumar K.V void ext4_ext_drop_refs(struct ext4_ext_path *path)
394a86c6181SAlex Tomas {
395a86c6181SAlex Tomas 	int depth = path->p_depth;
396a86c6181SAlex Tomas 	int i;
397a86c6181SAlex Tomas 
398a86c6181SAlex Tomas 	for (i = 0; i <= depth; i++, path++)
399a86c6181SAlex Tomas 		if (path->p_bh) {
400a86c6181SAlex Tomas 			brelse(path->p_bh);
401a86c6181SAlex Tomas 			path->p_bh = NULL;
402a86c6181SAlex Tomas 		}
403a86c6181SAlex Tomas }
404a86c6181SAlex Tomas 
405a86c6181SAlex Tomas /*
406d0d856e8SRandy Dunlap  * ext4_ext_binsearch_idx:
407d0d856e8SRandy Dunlap  * binary search for the closest index of the given block
408c29c0ae7SAlex Tomas  * the header must be checked before calling this
409a86c6181SAlex Tomas  */
410a86c6181SAlex Tomas static void
411725d26d3SAneesh Kumar K.V ext4_ext_binsearch_idx(struct inode *inode,
412725d26d3SAneesh Kumar K.V 			struct ext4_ext_path *path, ext4_lblk_t block)
413a86c6181SAlex Tomas {
414a86c6181SAlex Tomas 	struct ext4_extent_header *eh = path->p_hdr;
415a86c6181SAlex Tomas 	struct ext4_extent_idx *r, *l, *m;
416a86c6181SAlex Tomas 
417a86c6181SAlex Tomas 
418bba90743SEric Sandeen 	ext_debug("binsearch for %u(idx):  ", block);
419a86c6181SAlex Tomas 
420a86c6181SAlex Tomas 	l = EXT_FIRST_INDEX(eh) + 1;
421e9f410b1SDmitry Monakhov 	r = EXT_LAST_INDEX(eh);
422a86c6181SAlex Tomas 	while (l <= r) {
423a86c6181SAlex Tomas 		m = l + (r - l) / 2;
424a86c6181SAlex Tomas 		if (block < le32_to_cpu(m->ei_block))
425a86c6181SAlex Tomas 			r = m - 1;
426a86c6181SAlex Tomas 		else
427a86c6181SAlex Tomas 			l = m + 1;
42826d535edSDmitry Monakhov 		ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ei_block),
42926d535edSDmitry Monakhov 				m, le32_to_cpu(m->ei_block),
43026d535edSDmitry Monakhov 				r, le32_to_cpu(r->ei_block));
431a86c6181SAlex Tomas 	}
432a86c6181SAlex Tomas 
433a86c6181SAlex Tomas 	path->p_idx = l - 1;
434f65e6fbaSAlex Tomas 	ext_debug("  -> %d->%lld ", le32_to_cpu(path->p_idx->ei_block),
43526d535edSDmitry Monakhov 		  idx_pblock(path->p_idx));
436a86c6181SAlex Tomas 
437a86c6181SAlex Tomas #ifdef CHECK_BINSEARCH
438a86c6181SAlex Tomas 	{
439a86c6181SAlex Tomas 		struct ext4_extent_idx *chix, *ix;
440a86c6181SAlex Tomas 		int k;
441a86c6181SAlex Tomas 
442a86c6181SAlex Tomas 		chix = ix = EXT_FIRST_INDEX(eh);
443a86c6181SAlex Tomas 		for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ix++) {
444a86c6181SAlex Tomas 		  if (k != 0 &&
445a86c6181SAlex Tomas 		      le32_to_cpu(ix->ei_block) <= le32_to_cpu(ix[-1].ei_block)) {
4464776004fSTheodore Ts'o 				printk(KERN_DEBUG "k=%d, ix=0x%p, "
4474776004fSTheodore Ts'o 				       "first=0x%p\n", k,
448a86c6181SAlex Tomas 				       ix, EXT_FIRST_INDEX(eh));
4494776004fSTheodore Ts'o 				printk(KERN_DEBUG "%u <= %u\n",
450a86c6181SAlex Tomas 				       le32_to_cpu(ix->ei_block),
451a86c6181SAlex Tomas 				       le32_to_cpu(ix[-1].ei_block));
452a86c6181SAlex Tomas 			}
453a86c6181SAlex Tomas 			BUG_ON(k && le32_to_cpu(ix->ei_block)
454a86c6181SAlex Tomas 					   <= le32_to_cpu(ix[-1].ei_block));
455a86c6181SAlex Tomas 			if (block < le32_to_cpu(ix->ei_block))
456a86c6181SAlex Tomas 				break;
457a86c6181SAlex Tomas 			chix = ix;
458a86c6181SAlex Tomas 		}
459a86c6181SAlex Tomas 		BUG_ON(chix != path->p_idx);
460a86c6181SAlex Tomas 	}
461a86c6181SAlex Tomas #endif
462a86c6181SAlex Tomas 
463a86c6181SAlex Tomas }
464a86c6181SAlex Tomas 
465a86c6181SAlex Tomas /*
466d0d856e8SRandy Dunlap  * ext4_ext_binsearch:
467d0d856e8SRandy Dunlap  * binary search for closest extent of the given block
468c29c0ae7SAlex Tomas  * the header must be checked before calling this
469a86c6181SAlex Tomas  */
470a86c6181SAlex Tomas static void
471725d26d3SAneesh Kumar K.V ext4_ext_binsearch(struct inode *inode,
472725d26d3SAneesh Kumar K.V 		struct ext4_ext_path *path, ext4_lblk_t block)
473a86c6181SAlex Tomas {
474a86c6181SAlex Tomas 	struct ext4_extent_header *eh = path->p_hdr;
475a86c6181SAlex Tomas 	struct ext4_extent *r, *l, *m;
476a86c6181SAlex Tomas 
477a86c6181SAlex Tomas 	if (eh->eh_entries == 0) {
478a86c6181SAlex Tomas 		/*
479d0d856e8SRandy Dunlap 		 * this leaf is empty:
480a86c6181SAlex Tomas 		 * we get such a leaf in split/add case
481a86c6181SAlex Tomas 		 */
482a86c6181SAlex Tomas 		return;
483a86c6181SAlex Tomas 	}
484a86c6181SAlex Tomas 
485bba90743SEric Sandeen 	ext_debug("binsearch for %u:  ", block);
486a86c6181SAlex Tomas 
487a86c6181SAlex Tomas 	l = EXT_FIRST_EXTENT(eh) + 1;
488e9f410b1SDmitry Monakhov 	r = EXT_LAST_EXTENT(eh);
489a86c6181SAlex Tomas 
490a86c6181SAlex Tomas 	while (l <= r) {
491a86c6181SAlex Tomas 		m = l + (r - l) / 2;
492a86c6181SAlex Tomas 		if (block < le32_to_cpu(m->ee_block))
493a86c6181SAlex Tomas 			r = m - 1;
494a86c6181SAlex Tomas 		else
495a86c6181SAlex Tomas 			l = m + 1;
49626d535edSDmitry Monakhov 		ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ee_block),
49726d535edSDmitry Monakhov 				m, le32_to_cpu(m->ee_block),
49826d535edSDmitry Monakhov 				r, le32_to_cpu(r->ee_block));
499a86c6181SAlex Tomas 	}
500a86c6181SAlex Tomas 
501a86c6181SAlex Tomas 	path->p_ext = l - 1;
5022ae02107SMingming Cao 	ext_debug("  -> %d:%llu:%d ",
503a86c6181SAlex Tomas 			le32_to_cpu(path->p_ext->ee_block),
504f65e6fbaSAlex Tomas 			ext_pblock(path->p_ext),
505a2df2a63SAmit Arora 			ext4_ext_get_actual_len(path->p_ext));
506a86c6181SAlex Tomas 
507a86c6181SAlex Tomas #ifdef CHECK_BINSEARCH
508a86c6181SAlex Tomas 	{
509a86c6181SAlex Tomas 		struct ext4_extent *chex, *ex;
510a86c6181SAlex Tomas 		int k;
511a86c6181SAlex Tomas 
512a86c6181SAlex Tomas 		chex = ex = EXT_FIRST_EXTENT(eh);
513a86c6181SAlex Tomas 		for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ex++) {
514a86c6181SAlex Tomas 			BUG_ON(k && le32_to_cpu(ex->ee_block)
515a86c6181SAlex Tomas 					  <= le32_to_cpu(ex[-1].ee_block));
516a86c6181SAlex Tomas 			if (block < le32_to_cpu(ex->ee_block))
517a86c6181SAlex Tomas 				break;
518a86c6181SAlex Tomas 			chex = ex;
519a86c6181SAlex Tomas 		}
520a86c6181SAlex Tomas 		BUG_ON(chex != path->p_ext);
521a86c6181SAlex Tomas 	}
522a86c6181SAlex Tomas #endif
523a86c6181SAlex Tomas 
524a86c6181SAlex Tomas }
525a86c6181SAlex Tomas 
526a86c6181SAlex Tomas int ext4_ext_tree_init(handle_t *handle, struct inode *inode)
527a86c6181SAlex Tomas {
528a86c6181SAlex Tomas 	struct ext4_extent_header *eh;
529a86c6181SAlex Tomas 
530a86c6181SAlex Tomas 	eh = ext_inode_hdr(inode);
531a86c6181SAlex Tomas 	eh->eh_depth = 0;
532a86c6181SAlex Tomas 	eh->eh_entries = 0;
533a86c6181SAlex Tomas 	eh->eh_magic = EXT4_EXT_MAGIC;
534a86c6181SAlex Tomas 	eh->eh_max = cpu_to_le16(ext4_ext_space_root(inode));
535a86c6181SAlex Tomas 	ext4_mark_inode_dirty(handle, inode);
536a86c6181SAlex Tomas 	ext4_ext_invalidate_cache(inode);
537a86c6181SAlex Tomas 	return 0;
538a86c6181SAlex Tomas }
539a86c6181SAlex Tomas 
540a86c6181SAlex Tomas struct ext4_ext_path *
541725d26d3SAneesh Kumar K.V ext4_ext_find_extent(struct inode *inode, ext4_lblk_t block,
542725d26d3SAneesh Kumar K.V 					struct ext4_ext_path *path)
543a86c6181SAlex Tomas {
544a86c6181SAlex Tomas 	struct ext4_extent_header *eh;
545a86c6181SAlex Tomas 	struct buffer_head *bh;
546a86c6181SAlex Tomas 	short int depth, i, ppos = 0, alloc = 0;
547a86c6181SAlex Tomas 
548a86c6181SAlex Tomas 	eh = ext_inode_hdr(inode);
549c29c0ae7SAlex Tomas 	depth = ext_depth(inode);
550c29c0ae7SAlex Tomas 	if (ext4_ext_check_header(inode, eh, depth))
551a86c6181SAlex Tomas 		return ERR_PTR(-EIO);
552a86c6181SAlex Tomas 
553a86c6181SAlex Tomas 
554a86c6181SAlex Tomas 	/* account possible depth increase */
555a86c6181SAlex Tomas 	if (!path) {
5565d4958f9SAvantika Mathur 		path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 2),
557a86c6181SAlex Tomas 				GFP_NOFS);
558a86c6181SAlex Tomas 		if (!path)
559a86c6181SAlex Tomas 			return ERR_PTR(-ENOMEM);
560a86c6181SAlex Tomas 		alloc = 1;
561a86c6181SAlex Tomas 	}
562a86c6181SAlex Tomas 	path[0].p_hdr = eh;
5631973adcbSShen Feng 	path[0].p_bh = NULL;
564a86c6181SAlex Tomas 
565c29c0ae7SAlex Tomas 	i = depth;
566a86c6181SAlex Tomas 	/* walk through the tree */
567a86c6181SAlex Tomas 	while (i) {
568a86c6181SAlex Tomas 		ext_debug("depth %d: num %d, max %d\n",
569a86c6181SAlex Tomas 			  ppos, le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
570c29c0ae7SAlex Tomas 
571a86c6181SAlex Tomas 		ext4_ext_binsearch_idx(inode, path + ppos, block);
572f65e6fbaSAlex Tomas 		path[ppos].p_block = idx_pblock(path[ppos].p_idx);
573a86c6181SAlex Tomas 		path[ppos].p_depth = i;
574a86c6181SAlex Tomas 		path[ppos].p_ext = NULL;
575a86c6181SAlex Tomas 
576a86c6181SAlex Tomas 		bh = sb_bread(inode->i_sb, path[ppos].p_block);
577a86c6181SAlex Tomas 		if (!bh)
578a86c6181SAlex Tomas 			goto err;
579a86c6181SAlex Tomas 
580a86c6181SAlex Tomas 		eh = ext_block_hdr(bh);
581a86c6181SAlex Tomas 		ppos++;
582a86c6181SAlex Tomas 		BUG_ON(ppos > depth);
583a86c6181SAlex Tomas 		path[ppos].p_bh = bh;
584a86c6181SAlex Tomas 		path[ppos].p_hdr = eh;
585a86c6181SAlex Tomas 		i--;
586a86c6181SAlex Tomas 
587c29c0ae7SAlex Tomas 		if (ext4_ext_check_header(inode, eh, i))
588a86c6181SAlex Tomas 			goto err;
589a86c6181SAlex Tomas 	}
590a86c6181SAlex Tomas 
591a86c6181SAlex Tomas 	path[ppos].p_depth = i;
592a86c6181SAlex Tomas 	path[ppos].p_ext = NULL;
593a86c6181SAlex Tomas 	path[ppos].p_idx = NULL;
594a86c6181SAlex Tomas 
595a86c6181SAlex Tomas 	/* find extent */
596a86c6181SAlex Tomas 	ext4_ext_binsearch(inode, path + ppos, block);
5971973adcbSShen Feng 	/* if not an empty leaf */
5981973adcbSShen Feng 	if (path[ppos].p_ext)
5991973adcbSShen Feng 		path[ppos].p_block = ext_pblock(path[ppos].p_ext);
600a86c6181SAlex Tomas 
601a86c6181SAlex Tomas 	ext4_ext_show_path(inode, path);
602a86c6181SAlex Tomas 
603a86c6181SAlex Tomas 	return path;
604a86c6181SAlex Tomas 
605a86c6181SAlex Tomas err:
606a86c6181SAlex Tomas 	ext4_ext_drop_refs(path);
607a86c6181SAlex Tomas 	if (alloc)
608a86c6181SAlex Tomas 		kfree(path);
609a86c6181SAlex Tomas 	return ERR_PTR(-EIO);
610a86c6181SAlex Tomas }
611a86c6181SAlex Tomas 
612a86c6181SAlex Tomas /*
613d0d856e8SRandy Dunlap  * ext4_ext_insert_index:
614d0d856e8SRandy Dunlap  * insert new index [@logical;@ptr] into the block at @curp;
615d0d856e8SRandy Dunlap  * check where to insert: before @curp or after @curp
616a86c6181SAlex Tomas  */
617a86c6181SAlex Tomas static int ext4_ext_insert_index(handle_t *handle, struct inode *inode,
618a86c6181SAlex Tomas 				struct ext4_ext_path *curp,
619f65e6fbaSAlex Tomas 				int logical, ext4_fsblk_t ptr)
620a86c6181SAlex Tomas {
621a86c6181SAlex Tomas 	struct ext4_extent_idx *ix;
622a86c6181SAlex Tomas 	int len, err;
623a86c6181SAlex Tomas 
6247e028976SAvantika Mathur 	err = ext4_ext_get_access(handle, inode, curp);
6257e028976SAvantika Mathur 	if (err)
626a86c6181SAlex Tomas 		return err;
627a86c6181SAlex Tomas 
628a86c6181SAlex Tomas 	BUG_ON(logical == le32_to_cpu(curp->p_idx->ei_block));
629a86c6181SAlex Tomas 	len = EXT_MAX_INDEX(curp->p_hdr) - curp->p_idx;
630a86c6181SAlex Tomas 	if (logical > le32_to_cpu(curp->p_idx->ei_block)) {
631a86c6181SAlex Tomas 		/* insert after */
632a86c6181SAlex Tomas 		if (curp->p_idx != EXT_LAST_INDEX(curp->p_hdr)) {
633a86c6181SAlex Tomas 			len = (len - 1) * sizeof(struct ext4_extent_idx);
634a86c6181SAlex Tomas 			len = len < 0 ? 0 : len;
63526d535edSDmitry Monakhov 			ext_debug("insert new index %d after: %llu. "
636a86c6181SAlex Tomas 					"move %d from 0x%p to 0x%p\n",
637a86c6181SAlex Tomas 					logical, ptr, len,
638a86c6181SAlex Tomas 					(curp->p_idx + 1), (curp->p_idx + 2));
639a86c6181SAlex Tomas 			memmove(curp->p_idx + 2, curp->p_idx + 1, len);
640a86c6181SAlex Tomas 		}
641a86c6181SAlex Tomas 		ix = curp->p_idx + 1;
642a86c6181SAlex Tomas 	} else {
643a86c6181SAlex Tomas 		/* insert before */
644a86c6181SAlex Tomas 		len = len * sizeof(struct ext4_extent_idx);
645a86c6181SAlex Tomas 		len = len < 0 ? 0 : len;
64626d535edSDmitry Monakhov 		ext_debug("insert new index %d before: %llu. "
647a86c6181SAlex Tomas 				"move %d from 0x%p to 0x%p\n",
648a86c6181SAlex Tomas 				logical, ptr, len,
649a86c6181SAlex Tomas 				curp->p_idx, (curp->p_idx + 1));
650a86c6181SAlex Tomas 		memmove(curp->p_idx + 1, curp->p_idx, len);
651a86c6181SAlex Tomas 		ix = curp->p_idx;
652a86c6181SAlex Tomas 	}
653a86c6181SAlex Tomas 
654a86c6181SAlex Tomas 	ix->ei_block = cpu_to_le32(logical);
655f65e6fbaSAlex Tomas 	ext4_idx_store_pblock(ix, ptr);
656e8546d06SMarcin Slusarz 	le16_add_cpu(&curp->p_hdr->eh_entries, 1);
657a86c6181SAlex Tomas 
658a86c6181SAlex Tomas 	BUG_ON(le16_to_cpu(curp->p_hdr->eh_entries)
659a86c6181SAlex Tomas 			     > le16_to_cpu(curp->p_hdr->eh_max));
660a86c6181SAlex Tomas 	BUG_ON(ix > EXT_LAST_INDEX(curp->p_hdr));
661a86c6181SAlex Tomas 
662a86c6181SAlex Tomas 	err = ext4_ext_dirty(handle, inode, curp);
663a86c6181SAlex Tomas 	ext4_std_error(inode->i_sb, err);
664a86c6181SAlex Tomas 
665a86c6181SAlex Tomas 	return err;
666a86c6181SAlex Tomas }
667a86c6181SAlex Tomas 
668a86c6181SAlex Tomas /*
669d0d856e8SRandy Dunlap  * ext4_ext_split:
670d0d856e8SRandy Dunlap  * inserts new subtree into the path, using free index entry
671d0d856e8SRandy Dunlap  * at depth @at:
672a86c6181SAlex Tomas  * - allocates all needed blocks (new leaf and all intermediate index blocks)
673a86c6181SAlex Tomas  * - makes decision where to split
674d0d856e8SRandy Dunlap  * - moves remaining extents and index entries (right to the split point)
675a86c6181SAlex Tomas  *   into the newly allocated blocks
676d0d856e8SRandy Dunlap  * - initializes subtree
677a86c6181SAlex Tomas  */
678a86c6181SAlex Tomas static int ext4_ext_split(handle_t *handle, struct inode *inode,
679a86c6181SAlex Tomas 				struct ext4_ext_path *path,
680a86c6181SAlex Tomas 				struct ext4_extent *newext, int at)
681a86c6181SAlex Tomas {
682a86c6181SAlex Tomas 	struct buffer_head *bh = NULL;
683a86c6181SAlex Tomas 	int depth = ext_depth(inode);
684a86c6181SAlex Tomas 	struct ext4_extent_header *neh;
685a86c6181SAlex Tomas 	struct ext4_extent_idx *fidx;
686a86c6181SAlex Tomas 	struct ext4_extent *ex;
687a86c6181SAlex Tomas 	int i = at, k, m, a;
688f65e6fbaSAlex Tomas 	ext4_fsblk_t newblock, oldblock;
689a86c6181SAlex Tomas 	__le32 border;
690f65e6fbaSAlex Tomas 	ext4_fsblk_t *ablocks = NULL; /* array of allocated blocks */
691a86c6181SAlex Tomas 	int err = 0;
692a86c6181SAlex Tomas 
693a86c6181SAlex Tomas 	/* make decision: where to split? */
694d0d856e8SRandy Dunlap 	/* FIXME: now decision is simplest: at current extent */
695a86c6181SAlex Tomas 
696d0d856e8SRandy Dunlap 	/* if current leaf will be split, then we should use
697a86c6181SAlex Tomas 	 * border from split point */
698a86c6181SAlex Tomas 	BUG_ON(path[depth].p_ext > EXT_MAX_EXTENT(path[depth].p_hdr));
699a86c6181SAlex Tomas 	if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr)) {
700a86c6181SAlex Tomas 		border = path[depth].p_ext[1].ee_block;
701d0d856e8SRandy Dunlap 		ext_debug("leaf will be split."
702a86c6181SAlex Tomas 				" next leaf starts at %d\n",
703a86c6181SAlex Tomas 				  le32_to_cpu(border));
704a86c6181SAlex Tomas 	} else {
705a86c6181SAlex Tomas 		border = newext->ee_block;
706a86c6181SAlex Tomas 		ext_debug("leaf will be added."
707a86c6181SAlex Tomas 				" next leaf starts at %d\n",
708a86c6181SAlex Tomas 				le32_to_cpu(border));
709a86c6181SAlex Tomas 	}
710a86c6181SAlex Tomas 
711a86c6181SAlex Tomas 	/*
712d0d856e8SRandy Dunlap 	 * If error occurs, then we break processing
713d0d856e8SRandy Dunlap 	 * and mark filesystem read-only. index won't
714a86c6181SAlex Tomas 	 * be inserted and tree will be in consistent
715d0d856e8SRandy Dunlap 	 * state. Next mount will repair buffers too.
716a86c6181SAlex Tomas 	 */
717a86c6181SAlex Tomas 
718a86c6181SAlex Tomas 	/*
719d0d856e8SRandy Dunlap 	 * Get array to track all allocated blocks.
720d0d856e8SRandy Dunlap 	 * We need this to handle errors and free blocks
721d0d856e8SRandy Dunlap 	 * upon them.
722a86c6181SAlex Tomas 	 */
7235d4958f9SAvantika Mathur 	ablocks = kzalloc(sizeof(ext4_fsblk_t) * depth, GFP_NOFS);
724a86c6181SAlex Tomas 	if (!ablocks)
725a86c6181SAlex Tomas 		return -ENOMEM;
726a86c6181SAlex Tomas 
727a86c6181SAlex Tomas 	/* allocate all needed blocks */
728a86c6181SAlex Tomas 	ext_debug("allocate %d blocks for indexes/leaf\n", depth - at);
729a86c6181SAlex Tomas 	for (a = 0; a < depth - at; a++) {
730654b4908SAneesh Kumar K.V 		newblock = ext4_ext_new_meta_block(handle, inode, path,
731654b4908SAneesh Kumar K.V 						   newext, &err);
732a86c6181SAlex Tomas 		if (newblock == 0)
733a86c6181SAlex Tomas 			goto cleanup;
734a86c6181SAlex Tomas 		ablocks[a] = newblock;
735a86c6181SAlex Tomas 	}
736a86c6181SAlex Tomas 
737a86c6181SAlex Tomas 	/* initialize new leaf */
738a86c6181SAlex Tomas 	newblock = ablocks[--a];
739a86c6181SAlex Tomas 	BUG_ON(newblock == 0);
740a86c6181SAlex Tomas 	bh = sb_getblk(inode->i_sb, newblock);
741a86c6181SAlex Tomas 	if (!bh) {
742a86c6181SAlex Tomas 		err = -EIO;
743a86c6181SAlex Tomas 		goto cleanup;
744a86c6181SAlex Tomas 	}
745a86c6181SAlex Tomas 	lock_buffer(bh);
746a86c6181SAlex Tomas 
7477e028976SAvantika Mathur 	err = ext4_journal_get_create_access(handle, bh);
7487e028976SAvantika Mathur 	if (err)
749a86c6181SAlex Tomas 		goto cleanup;
750a86c6181SAlex Tomas 
751a86c6181SAlex Tomas 	neh = ext_block_hdr(bh);
752a86c6181SAlex Tomas 	neh->eh_entries = 0;
753a86c6181SAlex Tomas 	neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode));
754a86c6181SAlex Tomas 	neh->eh_magic = EXT4_EXT_MAGIC;
755a86c6181SAlex Tomas 	neh->eh_depth = 0;
756a86c6181SAlex Tomas 	ex = EXT_FIRST_EXTENT(neh);
757a86c6181SAlex Tomas 
758d0d856e8SRandy Dunlap 	/* move remainder of path[depth] to the new leaf */
759a86c6181SAlex Tomas 	BUG_ON(path[depth].p_hdr->eh_entries != path[depth].p_hdr->eh_max);
760a86c6181SAlex Tomas 	/* start copy from next extent */
761a86c6181SAlex Tomas 	/* TODO: we could do it by single memmove */
762a86c6181SAlex Tomas 	m = 0;
763a86c6181SAlex Tomas 	path[depth].p_ext++;
764a86c6181SAlex Tomas 	while (path[depth].p_ext <=
765a86c6181SAlex Tomas 			EXT_MAX_EXTENT(path[depth].p_hdr)) {
7662ae02107SMingming Cao 		ext_debug("move %d:%llu:%d in new leaf %llu\n",
767a86c6181SAlex Tomas 				le32_to_cpu(path[depth].p_ext->ee_block),
768f65e6fbaSAlex Tomas 				ext_pblock(path[depth].p_ext),
769a2df2a63SAmit Arora 				ext4_ext_get_actual_len(path[depth].p_ext),
770a86c6181SAlex Tomas 				newblock);
771a86c6181SAlex Tomas 		/*memmove(ex++, path[depth].p_ext++,
772a86c6181SAlex Tomas 				sizeof(struct ext4_extent));
773a86c6181SAlex Tomas 		neh->eh_entries++;*/
774a86c6181SAlex Tomas 		path[depth].p_ext++;
775a86c6181SAlex Tomas 		m++;
776a86c6181SAlex Tomas 	}
777a86c6181SAlex Tomas 	if (m) {
778a86c6181SAlex Tomas 		memmove(ex, path[depth].p_ext-m, sizeof(struct ext4_extent)*m);
779e8546d06SMarcin Slusarz 		le16_add_cpu(&neh->eh_entries, m);
780a86c6181SAlex Tomas 	}
781a86c6181SAlex Tomas 
782a86c6181SAlex Tomas 	set_buffer_uptodate(bh);
783a86c6181SAlex Tomas 	unlock_buffer(bh);
784a86c6181SAlex Tomas 
7850390131bSFrank Mayhar 	err = ext4_handle_dirty_metadata(handle, inode, bh);
7867e028976SAvantika Mathur 	if (err)
787a86c6181SAlex Tomas 		goto cleanup;
788a86c6181SAlex Tomas 	brelse(bh);
789a86c6181SAlex Tomas 	bh = NULL;
790a86c6181SAlex Tomas 
791a86c6181SAlex Tomas 	/* correct old leaf */
792a86c6181SAlex Tomas 	if (m) {
7937e028976SAvantika Mathur 		err = ext4_ext_get_access(handle, inode, path + depth);
7947e028976SAvantika Mathur 		if (err)
795a86c6181SAlex Tomas 			goto cleanup;
796e8546d06SMarcin Slusarz 		le16_add_cpu(&path[depth].p_hdr->eh_entries, -m);
7977e028976SAvantika Mathur 		err = ext4_ext_dirty(handle, inode, path + depth);
7987e028976SAvantika Mathur 		if (err)
799a86c6181SAlex Tomas 			goto cleanup;
800a86c6181SAlex Tomas 
801a86c6181SAlex Tomas 	}
802a86c6181SAlex Tomas 
803a86c6181SAlex Tomas 	/* create intermediate indexes */
804a86c6181SAlex Tomas 	k = depth - at - 1;
805a86c6181SAlex Tomas 	BUG_ON(k < 0);
806a86c6181SAlex Tomas 	if (k)
807a86c6181SAlex Tomas 		ext_debug("create %d intermediate indices\n", k);
808a86c6181SAlex Tomas 	/* insert new index into current index block */
809a86c6181SAlex Tomas 	/* current depth stored in i var */
810a86c6181SAlex Tomas 	i = depth - 1;
811a86c6181SAlex Tomas 	while (k--) {
812a86c6181SAlex Tomas 		oldblock = newblock;
813a86c6181SAlex Tomas 		newblock = ablocks[--a];
814bba90743SEric Sandeen 		bh = sb_getblk(inode->i_sb, newblock);
815a86c6181SAlex Tomas 		if (!bh) {
816a86c6181SAlex Tomas 			err = -EIO;
817a86c6181SAlex Tomas 			goto cleanup;
818a86c6181SAlex Tomas 		}
819a86c6181SAlex Tomas 		lock_buffer(bh);
820a86c6181SAlex Tomas 
8217e028976SAvantika Mathur 		err = ext4_journal_get_create_access(handle, bh);
8227e028976SAvantika Mathur 		if (err)
823a86c6181SAlex Tomas 			goto cleanup;
824a86c6181SAlex Tomas 
825a86c6181SAlex Tomas 		neh = ext_block_hdr(bh);
826a86c6181SAlex Tomas 		neh->eh_entries = cpu_to_le16(1);
827a86c6181SAlex Tomas 		neh->eh_magic = EXT4_EXT_MAGIC;
828a86c6181SAlex Tomas 		neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode));
829a86c6181SAlex Tomas 		neh->eh_depth = cpu_to_le16(depth - i);
830a86c6181SAlex Tomas 		fidx = EXT_FIRST_INDEX(neh);
831a86c6181SAlex Tomas 		fidx->ei_block = border;
832f65e6fbaSAlex Tomas 		ext4_idx_store_pblock(fidx, oldblock);
833a86c6181SAlex Tomas 
834bba90743SEric Sandeen 		ext_debug("int.index at %d (block %llu): %u -> %llu\n",
835bba90743SEric Sandeen 				i, newblock, le32_to_cpu(border), oldblock);
836a86c6181SAlex Tomas 		/* copy indexes */
837a86c6181SAlex Tomas 		m = 0;
838a86c6181SAlex Tomas 		path[i].p_idx++;
839a86c6181SAlex Tomas 
840a86c6181SAlex Tomas 		ext_debug("cur 0x%p, last 0x%p\n", path[i].p_idx,
841a86c6181SAlex Tomas 				EXT_MAX_INDEX(path[i].p_hdr));
842a86c6181SAlex Tomas 		BUG_ON(EXT_MAX_INDEX(path[i].p_hdr) !=
843a86c6181SAlex Tomas 				EXT_LAST_INDEX(path[i].p_hdr));
844a86c6181SAlex Tomas 		while (path[i].p_idx <= EXT_MAX_INDEX(path[i].p_hdr)) {
84526d535edSDmitry Monakhov 			ext_debug("%d: move %d:%llu in new index %llu\n", i,
846a86c6181SAlex Tomas 					le32_to_cpu(path[i].p_idx->ei_block),
847f65e6fbaSAlex Tomas 					idx_pblock(path[i].p_idx),
848a86c6181SAlex Tomas 					newblock);
849a86c6181SAlex Tomas 			/*memmove(++fidx, path[i].p_idx++,
850a86c6181SAlex Tomas 					sizeof(struct ext4_extent_idx));
851a86c6181SAlex Tomas 			neh->eh_entries++;
852a86c6181SAlex Tomas 			BUG_ON(neh->eh_entries > neh->eh_max);*/
853a86c6181SAlex Tomas 			path[i].p_idx++;
854a86c6181SAlex Tomas 			m++;
855a86c6181SAlex Tomas 		}
856a86c6181SAlex Tomas 		if (m) {
857a86c6181SAlex Tomas 			memmove(++fidx, path[i].p_idx - m,
858a86c6181SAlex Tomas 				sizeof(struct ext4_extent_idx) * m);
859e8546d06SMarcin Slusarz 			le16_add_cpu(&neh->eh_entries, m);
860a86c6181SAlex Tomas 		}
861a86c6181SAlex Tomas 		set_buffer_uptodate(bh);
862a86c6181SAlex Tomas 		unlock_buffer(bh);
863a86c6181SAlex Tomas 
8640390131bSFrank Mayhar 		err = ext4_handle_dirty_metadata(handle, inode, bh);
8657e028976SAvantika Mathur 		if (err)
866a86c6181SAlex Tomas 			goto cleanup;
867a86c6181SAlex Tomas 		brelse(bh);
868a86c6181SAlex Tomas 		bh = NULL;
869a86c6181SAlex Tomas 
870a86c6181SAlex Tomas 		/* correct old index */
871a86c6181SAlex Tomas 		if (m) {
872a86c6181SAlex Tomas 			err = ext4_ext_get_access(handle, inode, path + i);
873a86c6181SAlex Tomas 			if (err)
874a86c6181SAlex Tomas 				goto cleanup;
875e8546d06SMarcin Slusarz 			le16_add_cpu(&path[i].p_hdr->eh_entries, -m);
876a86c6181SAlex Tomas 			err = ext4_ext_dirty(handle, inode, path + i);
877a86c6181SAlex Tomas 			if (err)
878a86c6181SAlex Tomas 				goto cleanup;
879a86c6181SAlex Tomas 		}
880a86c6181SAlex Tomas 
881a86c6181SAlex Tomas 		i--;
882a86c6181SAlex Tomas 	}
883a86c6181SAlex Tomas 
884a86c6181SAlex Tomas 	/* insert new index */
885a86c6181SAlex Tomas 	err = ext4_ext_insert_index(handle, inode, path + at,
886a86c6181SAlex Tomas 				    le32_to_cpu(border), newblock);
887a86c6181SAlex Tomas 
888a86c6181SAlex Tomas cleanup:
889a86c6181SAlex Tomas 	if (bh) {
890a86c6181SAlex Tomas 		if (buffer_locked(bh))
891a86c6181SAlex Tomas 			unlock_buffer(bh);
892a86c6181SAlex Tomas 		brelse(bh);
893a86c6181SAlex Tomas 	}
894a86c6181SAlex Tomas 
895a86c6181SAlex Tomas 	if (err) {
896a86c6181SAlex Tomas 		/* free all allocated blocks in error case */
897a86c6181SAlex Tomas 		for (i = 0; i < depth; i++) {
898a86c6181SAlex Tomas 			if (!ablocks[i])
899a86c6181SAlex Tomas 				continue;
900c9de560dSAlex Tomas 			ext4_free_blocks(handle, inode, ablocks[i], 1, 1);
901a86c6181SAlex Tomas 		}
902a86c6181SAlex Tomas 	}
903a86c6181SAlex Tomas 	kfree(ablocks);
904a86c6181SAlex Tomas 
905a86c6181SAlex Tomas 	return err;
906a86c6181SAlex Tomas }
907a86c6181SAlex Tomas 
908a86c6181SAlex Tomas /*
909d0d856e8SRandy Dunlap  * ext4_ext_grow_indepth:
910d0d856e8SRandy Dunlap  * implements tree growing procedure:
911a86c6181SAlex Tomas  * - allocates new block
912a86c6181SAlex Tomas  * - moves top-level data (index block or leaf) into the new block
913d0d856e8SRandy Dunlap  * - initializes new top-level, creating index that points to the
914a86c6181SAlex Tomas  *   just created block
915a86c6181SAlex Tomas  */
916a86c6181SAlex Tomas static int ext4_ext_grow_indepth(handle_t *handle, struct inode *inode,
917a86c6181SAlex Tomas 					struct ext4_ext_path *path,
918a86c6181SAlex Tomas 					struct ext4_extent *newext)
919a86c6181SAlex Tomas {
920a86c6181SAlex Tomas 	struct ext4_ext_path *curp = path;
921a86c6181SAlex Tomas 	struct ext4_extent_header *neh;
922a86c6181SAlex Tomas 	struct ext4_extent_idx *fidx;
923a86c6181SAlex Tomas 	struct buffer_head *bh;
924f65e6fbaSAlex Tomas 	ext4_fsblk_t newblock;
925a86c6181SAlex Tomas 	int err = 0;
926a86c6181SAlex Tomas 
927654b4908SAneesh Kumar K.V 	newblock = ext4_ext_new_meta_block(handle, inode, path, newext, &err);
928a86c6181SAlex Tomas 	if (newblock == 0)
929a86c6181SAlex Tomas 		return err;
930a86c6181SAlex Tomas 
931a86c6181SAlex Tomas 	bh = sb_getblk(inode->i_sb, newblock);
932a86c6181SAlex Tomas 	if (!bh) {
933a86c6181SAlex Tomas 		err = -EIO;
934a86c6181SAlex Tomas 		ext4_std_error(inode->i_sb, err);
935a86c6181SAlex Tomas 		return err;
936a86c6181SAlex Tomas 	}
937a86c6181SAlex Tomas 	lock_buffer(bh);
938a86c6181SAlex Tomas 
9397e028976SAvantika Mathur 	err = ext4_journal_get_create_access(handle, bh);
9407e028976SAvantika Mathur 	if (err) {
941a86c6181SAlex Tomas 		unlock_buffer(bh);
942a86c6181SAlex Tomas 		goto out;
943a86c6181SAlex Tomas 	}
944a86c6181SAlex Tomas 
945a86c6181SAlex Tomas 	/* move top-level index/leaf into new block */
946a86c6181SAlex Tomas 	memmove(bh->b_data, curp->p_hdr, sizeof(EXT4_I(inode)->i_data));
947a86c6181SAlex Tomas 
948a86c6181SAlex Tomas 	/* set size of new block */
949a86c6181SAlex Tomas 	neh = ext_block_hdr(bh);
950a86c6181SAlex Tomas 	/* old root could have indexes or leaves
951a86c6181SAlex Tomas 	 * so calculate e_max right way */
952a86c6181SAlex Tomas 	if (ext_depth(inode))
953a86c6181SAlex Tomas 	  neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode));
954a86c6181SAlex Tomas 	else
955a86c6181SAlex Tomas 	  neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode));
956a86c6181SAlex Tomas 	neh->eh_magic = EXT4_EXT_MAGIC;
957a86c6181SAlex Tomas 	set_buffer_uptodate(bh);
958a86c6181SAlex Tomas 	unlock_buffer(bh);
959a86c6181SAlex Tomas 
9600390131bSFrank Mayhar 	err = ext4_handle_dirty_metadata(handle, inode, bh);
9617e028976SAvantika Mathur 	if (err)
962a86c6181SAlex Tomas 		goto out;
963a86c6181SAlex Tomas 
964a86c6181SAlex Tomas 	/* create index in new top-level index: num,max,pointer */
9657e028976SAvantika Mathur 	err = ext4_ext_get_access(handle, inode, curp);
9667e028976SAvantika Mathur 	if (err)
967a86c6181SAlex Tomas 		goto out;
968a86c6181SAlex Tomas 
969a86c6181SAlex Tomas 	curp->p_hdr->eh_magic = EXT4_EXT_MAGIC;
970a86c6181SAlex Tomas 	curp->p_hdr->eh_max = cpu_to_le16(ext4_ext_space_root_idx(inode));
971a86c6181SAlex Tomas 	curp->p_hdr->eh_entries = cpu_to_le16(1);
972a86c6181SAlex Tomas 	curp->p_idx = EXT_FIRST_INDEX(curp->p_hdr);
973e9f410b1SDmitry Monakhov 
974e9f410b1SDmitry Monakhov 	if (path[0].p_hdr->eh_depth)
975e9f410b1SDmitry Monakhov 		curp->p_idx->ei_block =
976e9f410b1SDmitry Monakhov 			EXT_FIRST_INDEX(path[0].p_hdr)->ei_block;
977e9f410b1SDmitry Monakhov 	else
978e9f410b1SDmitry Monakhov 		curp->p_idx->ei_block =
979e9f410b1SDmitry Monakhov 			EXT_FIRST_EXTENT(path[0].p_hdr)->ee_block;
980f65e6fbaSAlex Tomas 	ext4_idx_store_pblock(curp->p_idx, newblock);
981a86c6181SAlex Tomas 
982a86c6181SAlex Tomas 	neh = ext_inode_hdr(inode);
983a86c6181SAlex Tomas 	fidx = EXT_FIRST_INDEX(neh);
9842ae02107SMingming Cao 	ext_debug("new root: num %d(%d), lblock %d, ptr %llu\n",
985a86c6181SAlex Tomas 		  le16_to_cpu(neh->eh_entries), le16_to_cpu(neh->eh_max),
986f65e6fbaSAlex Tomas 		  le32_to_cpu(fidx->ei_block), idx_pblock(fidx));
987a86c6181SAlex Tomas 
988a86c6181SAlex Tomas 	neh->eh_depth = cpu_to_le16(path->p_depth + 1);
989a86c6181SAlex Tomas 	err = ext4_ext_dirty(handle, inode, curp);
990a86c6181SAlex Tomas out:
991a86c6181SAlex Tomas 	brelse(bh);
992a86c6181SAlex Tomas 
993a86c6181SAlex Tomas 	return err;
994a86c6181SAlex Tomas }
995a86c6181SAlex Tomas 
996a86c6181SAlex Tomas /*
997d0d856e8SRandy Dunlap  * ext4_ext_create_new_leaf:
998d0d856e8SRandy Dunlap  * finds empty index and adds new leaf.
999d0d856e8SRandy Dunlap  * if no free index is found, then it requests in-depth growing.
1000a86c6181SAlex Tomas  */
1001a86c6181SAlex Tomas static int ext4_ext_create_new_leaf(handle_t *handle, struct inode *inode,
1002a86c6181SAlex Tomas 					struct ext4_ext_path *path,
1003a86c6181SAlex Tomas 					struct ext4_extent *newext)
1004a86c6181SAlex Tomas {
1005a86c6181SAlex Tomas 	struct ext4_ext_path *curp;
1006a86c6181SAlex Tomas 	int depth, i, err = 0;
1007a86c6181SAlex Tomas 
1008a86c6181SAlex Tomas repeat:
1009a86c6181SAlex Tomas 	i = depth = ext_depth(inode);
1010a86c6181SAlex Tomas 
1011a86c6181SAlex Tomas 	/* walk up to the tree and look for free index entry */
1012a86c6181SAlex Tomas 	curp = path + depth;
1013a86c6181SAlex Tomas 	while (i > 0 && !EXT_HAS_FREE_INDEX(curp)) {
1014a86c6181SAlex Tomas 		i--;
1015a86c6181SAlex Tomas 		curp--;
1016a86c6181SAlex Tomas 	}
1017a86c6181SAlex Tomas 
1018d0d856e8SRandy Dunlap 	/* we use already allocated block for index block,
1019d0d856e8SRandy Dunlap 	 * so subsequent data blocks should be contiguous */
1020a86c6181SAlex Tomas 	if (EXT_HAS_FREE_INDEX(curp)) {
1021a86c6181SAlex Tomas 		/* if we found index with free entry, then use that
1022a86c6181SAlex Tomas 		 * entry: create all needed subtree and add new leaf */
1023a86c6181SAlex Tomas 		err = ext4_ext_split(handle, inode, path, newext, i);
1024787e0981SShen Feng 		if (err)
1025787e0981SShen Feng 			goto out;
1026a86c6181SAlex Tomas 
1027a86c6181SAlex Tomas 		/* refill path */
1028a86c6181SAlex Tomas 		ext4_ext_drop_refs(path);
1029a86c6181SAlex Tomas 		path = ext4_ext_find_extent(inode,
1030725d26d3SAneesh Kumar K.V 				    (ext4_lblk_t)le32_to_cpu(newext->ee_block),
1031a86c6181SAlex Tomas 				    path);
1032a86c6181SAlex Tomas 		if (IS_ERR(path))
1033a86c6181SAlex Tomas 			err = PTR_ERR(path);
1034a86c6181SAlex Tomas 	} else {
1035a86c6181SAlex Tomas 		/* tree is full, time to grow in depth */
1036a86c6181SAlex Tomas 		err = ext4_ext_grow_indepth(handle, inode, path, newext);
1037a86c6181SAlex Tomas 		if (err)
1038a86c6181SAlex Tomas 			goto out;
1039a86c6181SAlex Tomas 
1040a86c6181SAlex Tomas 		/* refill path */
1041a86c6181SAlex Tomas 		ext4_ext_drop_refs(path);
1042a86c6181SAlex Tomas 		path = ext4_ext_find_extent(inode,
1043725d26d3SAneesh Kumar K.V 				   (ext4_lblk_t)le32_to_cpu(newext->ee_block),
1044a86c6181SAlex Tomas 				    path);
1045a86c6181SAlex Tomas 		if (IS_ERR(path)) {
1046a86c6181SAlex Tomas 			err = PTR_ERR(path);
1047a86c6181SAlex Tomas 			goto out;
1048a86c6181SAlex Tomas 		}
1049a86c6181SAlex Tomas 
1050a86c6181SAlex Tomas 		/*
1051d0d856e8SRandy Dunlap 		 * only first (depth 0 -> 1) produces free space;
1052d0d856e8SRandy Dunlap 		 * in all other cases we have to split the grown tree
1053a86c6181SAlex Tomas 		 */
1054a86c6181SAlex Tomas 		depth = ext_depth(inode);
1055a86c6181SAlex Tomas 		if (path[depth].p_hdr->eh_entries == path[depth].p_hdr->eh_max) {
1056d0d856e8SRandy Dunlap 			/* now we need to split */
1057a86c6181SAlex Tomas 			goto repeat;
1058a86c6181SAlex Tomas 		}
1059a86c6181SAlex Tomas 	}
1060a86c6181SAlex Tomas 
1061a86c6181SAlex Tomas out:
1062a86c6181SAlex Tomas 	return err;
1063a86c6181SAlex Tomas }
1064a86c6181SAlex Tomas 
1065a86c6181SAlex Tomas /*
10661988b51eSAlex Tomas  * search the closest allocated block to the left for *logical
10671988b51eSAlex Tomas  * and returns it at @logical + it's physical address at @phys
10681988b51eSAlex Tomas  * if *logical is the smallest allocated block, the function
10691988b51eSAlex Tomas  * returns 0 at @phys
10701988b51eSAlex Tomas  * return value contains 0 (success) or error code
10711988b51eSAlex Tomas  */
10721988b51eSAlex Tomas int
10731988b51eSAlex Tomas ext4_ext_search_left(struct inode *inode, struct ext4_ext_path *path,
10741988b51eSAlex Tomas 			ext4_lblk_t *logical, ext4_fsblk_t *phys)
10751988b51eSAlex Tomas {
10761988b51eSAlex Tomas 	struct ext4_extent_idx *ix;
10771988b51eSAlex Tomas 	struct ext4_extent *ex;
1078b939e376SAneesh Kumar K.V 	int depth, ee_len;
10791988b51eSAlex Tomas 
10801988b51eSAlex Tomas 	BUG_ON(path == NULL);
10811988b51eSAlex Tomas 	depth = path->p_depth;
10821988b51eSAlex Tomas 	*phys = 0;
10831988b51eSAlex Tomas 
10841988b51eSAlex Tomas 	if (depth == 0 && path->p_ext == NULL)
10851988b51eSAlex Tomas 		return 0;
10861988b51eSAlex Tomas 
10871988b51eSAlex Tomas 	/* usually extent in the path covers blocks smaller
10881988b51eSAlex Tomas 	 * then *logical, but it can be that extent is the
10891988b51eSAlex Tomas 	 * first one in the file */
10901988b51eSAlex Tomas 
10911988b51eSAlex Tomas 	ex = path[depth].p_ext;
1092b939e376SAneesh Kumar K.V 	ee_len = ext4_ext_get_actual_len(ex);
10931988b51eSAlex Tomas 	if (*logical < le32_to_cpu(ex->ee_block)) {
10941988b51eSAlex Tomas 		BUG_ON(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex);
10951988b51eSAlex Tomas 		while (--depth >= 0) {
10961988b51eSAlex Tomas 			ix = path[depth].p_idx;
10971988b51eSAlex Tomas 			BUG_ON(ix != EXT_FIRST_INDEX(path[depth].p_hdr));
10981988b51eSAlex Tomas 		}
10991988b51eSAlex Tomas 		return 0;
11001988b51eSAlex Tomas 	}
11011988b51eSAlex Tomas 
1102b939e376SAneesh Kumar K.V 	BUG_ON(*logical < (le32_to_cpu(ex->ee_block) + ee_len));
11031988b51eSAlex Tomas 
1104b939e376SAneesh Kumar K.V 	*logical = le32_to_cpu(ex->ee_block) + ee_len - 1;
1105b939e376SAneesh Kumar K.V 	*phys = ext_pblock(ex) + ee_len - 1;
11061988b51eSAlex Tomas 	return 0;
11071988b51eSAlex Tomas }
11081988b51eSAlex Tomas 
11091988b51eSAlex Tomas /*
11101988b51eSAlex Tomas  * search the closest allocated block to the right for *logical
11111988b51eSAlex Tomas  * and returns it at @logical + it's physical address at @phys
11121988b51eSAlex Tomas  * if *logical is the smallest allocated block, the function
11131988b51eSAlex Tomas  * returns 0 at @phys
11141988b51eSAlex Tomas  * return value contains 0 (success) or error code
11151988b51eSAlex Tomas  */
11161988b51eSAlex Tomas int
11171988b51eSAlex Tomas ext4_ext_search_right(struct inode *inode, struct ext4_ext_path *path,
11181988b51eSAlex Tomas 			ext4_lblk_t *logical, ext4_fsblk_t *phys)
11191988b51eSAlex Tomas {
11201988b51eSAlex Tomas 	struct buffer_head *bh = NULL;
11211988b51eSAlex Tomas 	struct ext4_extent_header *eh;
11221988b51eSAlex Tomas 	struct ext4_extent_idx *ix;
11231988b51eSAlex Tomas 	struct ext4_extent *ex;
11241988b51eSAlex Tomas 	ext4_fsblk_t block;
1125b939e376SAneesh Kumar K.V 	int depth, ee_len;
11261988b51eSAlex Tomas 
11271988b51eSAlex Tomas 	BUG_ON(path == NULL);
11281988b51eSAlex Tomas 	depth = path->p_depth;
11291988b51eSAlex Tomas 	*phys = 0;
11301988b51eSAlex Tomas 
11311988b51eSAlex Tomas 	if (depth == 0 && path->p_ext == NULL)
11321988b51eSAlex Tomas 		return 0;
11331988b51eSAlex Tomas 
11341988b51eSAlex Tomas 	/* usually extent in the path covers blocks smaller
11351988b51eSAlex Tomas 	 * then *logical, but it can be that extent is the
11361988b51eSAlex Tomas 	 * first one in the file */
11371988b51eSAlex Tomas 
11381988b51eSAlex Tomas 	ex = path[depth].p_ext;
1139b939e376SAneesh Kumar K.V 	ee_len = ext4_ext_get_actual_len(ex);
11401988b51eSAlex Tomas 	if (*logical < le32_to_cpu(ex->ee_block)) {
11411988b51eSAlex Tomas 		BUG_ON(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex);
11421988b51eSAlex Tomas 		while (--depth >= 0) {
11431988b51eSAlex Tomas 			ix = path[depth].p_idx;
11441988b51eSAlex Tomas 			BUG_ON(ix != EXT_FIRST_INDEX(path[depth].p_hdr));
11451988b51eSAlex Tomas 		}
11461988b51eSAlex Tomas 		*logical = le32_to_cpu(ex->ee_block);
11471988b51eSAlex Tomas 		*phys = ext_pblock(ex);
11481988b51eSAlex Tomas 		return 0;
11491988b51eSAlex Tomas 	}
11501988b51eSAlex Tomas 
1151b939e376SAneesh Kumar K.V 	BUG_ON(*logical < (le32_to_cpu(ex->ee_block) + ee_len));
11521988b51eSAlex Tomas 
11531988b51eSAlex Tomas 	if (ex != EXT_LAST_EXTENT(path[depth].p_hdr)) {
11541988b51eSAlex Tomas 		/* next allocated block in this leaf */
11551988b51eSAlex Tomas 		ex++;
11561988b51eSAlex Tomas 		*logical = le32_to_cpu(ex->ee_block);
11571988b51eSAlex Tomas 		*phys = ext_pblock(ex);
11581988b51eSAlex Tomas 		return 0;
11591988b51eSAlex Tomas 	}
11601988b51eSAlex Tomas 
11611988b51eSAlex Tomas 	/* go up and search for index to the right */
11621988b51eSAlex Tomas 	while (--depth >= 0) {
11631988b51eSAlex Tomas 		ix = path[depth].p_idx;
11641988b51eSAlex Tomas 		if (ix != EXT_LAST_INDEX(path[depth].p_hdr))
116525f1ee3aSWu Fengguang 			goto got_index;
11661988b51eSAlex Tomas 	}
11671988b51eSAlex Tomas 
116825f1ee3aSWu Fengguang 	/* we've gone up to the root and found no index to the right */
11691988b51eSAlex Tomas 	return 0;
11701988b51eSAlex Tomas 
117125f1ee3aSWu Fengguang got_index:
11721988b51eSAlex Tomas 	/* we've found index to the right, let's
11731988b51eSAlex Tomas 	 * follow it and find the closest allocated
11741988b51eSAlex Tomas 	 * block to the right */
11751988b51eSAlex Tomas 	ix++;
11761988b51eSAlex Tomas 	block = idx_pblock(ix);
11771988b51eSAlex Tomas 	while (++depth < path->p_depth) {
11781988b51eSAlex Tomas 		bh = sb_bread(inode->i_sb, block);
11791988b51eSAlex Tomas 		if (bh == NULL)
11801988b51eSAlex Tomas 			return -EIO;
11811988b51eSAlex Tomas 		eh = ext_block_hdr(bh);
11821988b51eSAlex Tomas 		if (ext4_ext_check_header(inode, eh, depth)) {
11831988b51eSAlex Tomas 			put_bh(bh);
11841988b51eSAlex Tomas 			return -EIO;
11851988b51eSAlex Tomas 		}
11861988b51eSAlex Tomas 		ix = EXT_FIRST_INDEX(eh);
11871988b51eSAlex Tomas 		block = idx_pblock(ix);
11881988b51eSAlex Tomas 		put_bh(bh);
11891988b51eSAlex Tomas 	}
11901988b51eSAlex Tomas 
11911988b51eSAlex Tomas 	bh = sb_bread(inode->i_sb, block);
11921988b51eSAlex Tomas 	if (bh == NULL)
11931988b51eSAlex Tomas 		return -EIO;
11941988b51eSAlex Tomas 	eh = ext_block_hdr(bh);
11951988b51eSAlex Tomas 	if (ext4_ext_check_header(inode, eh, path->p_depth - depth)) {
11961988b51eSAlex Tomas 		put_bh(bh);
11971988b51eSAlex Tomas 		return -EIO;
11981988b51eSAlex Tomas 	}
11991988b51eSAlex Tomas 	ex = EXT_FIRST_EXTENT(eh);
12001988b51eSAlex Tomas 	*logical = le32_to_cpu(ex->ee_block);
12011988b51eSAlex Tomas 	*phys = ext_pblock(ex);
12021988b51eSAlex Tomas 	put_bh(bh);
12031988b51eSAlex Tomas 	return 0;
12041988b51eSAlex Tomas }
12051988b51eSAlex Tomas 
12061988b51eSAlex Tomas /*
1207d0d856e8SRandy Dunlap  * ext4_ext_next_allocated_block:
1208d0d856e8SRandy Dunlap  * returns allocated block in subsequent extent or EXT_MAX_BLOCK.
1209d0d856e8SRandy Dunlap  * NOTE: it considers block number from index entry as
1210d0d856e8SRandy Dunlap  * allocated block. Thus, index entries have to be consistent
1211d0d856e8SRandy Dunlap  * with leaves.
1212a86c6181SAlex Tomas  */
1213725d26d3SAneesh Kumar K.V static ext4_lblk_t
1214a86c6181SAlex Tomas ext4_ext_next_allocated_block(struct ext4_ext_path *path)
1215a86c6181SAlex Tomas {
1216a86c6181SAlex Tomas 	int depth;
1217a86c6181SAlex Tomas 
1218a86c6181SAlex Tomas 	BUG_ON(path == NULL);
1219a86c6181SAlex Tomas 	depth = path->p_depth;
1220a86c6181SAlex Tomas 
1221a86c6181SAlex Tomas 	if (depth == 0 && path->p_ext == NULL)
1222a86c6181SAlex Tomas 		return EXT_MAX_BLOCK;
1223a86c6181SAlex Tomas 
1224a86c6181SAlex Tomas 	while (depth >= 0) {
1225a86c6181SAlex Tomas 		if (depth == path->p_depth) {
1226a86c6181SAlex Tomas 			/* leaf */
1227a86c6181SAlex Tomas 			if (path[depth].p_ext !=
1228a86c6181SAlex Tomas 					EXT_LAST_EXTENT(path[depth].p_hdr))
1229a86c6181SAlex Tomas 			  return le32_to_cpu(path[depth].p_ext[1].ee_block);
1230a86c6181SAlex Tomas 		} else {
1231a86c6181SAlex Tomas 			/* index */
1232a86c6181SAlex Tomas 			if (path[depth].p_idx !=
1233a86c6181SAlex Tomas 					EXT_LAST_INDEX(path[depth].p_hdr))
1234a86c6181SAlex Tomas 			  return le32_to_cpu(path[depth].p_idx[1].ei_block);
1235a86c6181SAlex Tomas 		}
1236a86c6181SAlex Tomas 		depth--;
1237a86c6181SAlex Tomas 	}
1238a86c6181SAlex Tomas 
1239a86c6181SAlex Tomas 	return EXT_MAX_BLOCK;
1240a86c6181SAlex Tomas }
1241a86c6181SAlex Tomas 
1242a86c6181SAlex Tomas /*
1243d0d856e8SRandy Dunlap  * ext4_ext_next_leaf_block:
1244a86c6181SAlex Tomas  * returns first allocated block from next leaf or EXT_MAX_BLOCK
1245a86c6181SAlex Tomas  */
1246725d26d3SAneesh Kumar K.V static ext4_lblk_t ext4_ext_next_leaf_block(struct inode *inode,
1247a86c6181SAlex Tomas 					struct ext4_ext_path *path)
1248a86c6181SAlex Tomas {
1249a86c6181SAlex Tomas 	int depth;
1250a86c6181SAlex Tomas 
1251a86c6181SAlex Tomas 	BUG_ON(path == NULL);
1252a86c6181SAlex Tomas 	depth = path->p_depth;
1253a86c6181SAlex Tomas 
1254a86c6181SAlex Tomas 	/* zero-tree has no leaf blocks at all */
1255a86c6181SAlex Tomas 	if (depth == 0)
1256a86c6181SAlex Tomas 		return EXT_MAX_BLOCK;
1257a86c6181SAlex Tomas 
1258a86c6181SAlex Tomas 	/* go to index block */
1259a86c6181SAlex Tomas 	depth--;
1260a86c6181SAlex Tomas 
1261a86c6181SAlex Tomas 	while (depth >= 0) {
1262a86c6181SAlex Tomas 		if (path[depth].p_idx !=
1263a86c6181SAlex Tomas 				EXT_LAST_INDEX(path[depth].p_hdr))
1264725d26d3SAneesh Kumar K.V 			return (ext4_lblk_t)
1265725d26d3SAneesh Kumar K.V 				le32_to_cpu(path[depth].p_idx[1].ei_block);
1266a86c6181SAlex Tomas 		depth--;
1267a86c6181SAlex Tomas 	}
1268a86c6181SAlex Tomas 
1269a86c6181SAlex Tomas 	return EXT_MAX_BLOCK;
1270a86c6181SAlex Tomas }
1271a86c6181SAlex Tomas 
1272a86c6181SAlex Tomas /*
1273d0d856e8SRandy Dunlap  * ext4_ext_correct_indexes:
1274d0d856e8SRandy Dunlap  * if leaf gets modified and modified extent is first in the leaf,
1275d0d856e8SRandy Dunlap  * then we have to correct all indexes above.
1276a86c6181SAlex Tomas  * TODO: do we need to correct tree in all cases?
1277a86c6181SAlex Tomas  */
12781d03ec98SAneesh Kumar K.V static int ext4_ext_correct_indexes(handle_t *handle, struct inode *inode,
1279a86c6181SAlex Tomas 				struct ext4_ext_path *path)
1280a86c6181SAlex Tomas {
1281a86c6181SAlex Tomas 	struct ext4_extent_header *eh;
1282a86c6181SAlex Tomas 	int depth = ext_depth(inode);
1283a86c6181SAlex Tomas 	struct ext4_extent *ex;
1284a86c6181SAlex Tomas 	__le32 border;
1285a86c6181SAlex Tomas 	int k, err = 0;
1286a86c6181SAlex Tomas 
1287a86c6181SAlex Tomas 	eh = path[depth].p_hdr;
1288a86c6181SAlex Tomas 	ex = path[depth].p_ext;
1289a86c6181SAlex Tomas 	BUG_ON(ex == NULL);
1290a86c6181SAlex Tomas 	BUG_ON(eh == NULL);
1291a86c6181SAlex Tomas 
1292a86c6181SAlex Tomas 	if (depth == 0) {
1293a86c6181SAlex Tomas 		/* there is no tree at all */
1294a86c6181SAlex Tomas 		return 0;
1295a86c6181SAlex Tomas 	}
1296a86c6181SAlex Tomas 
1297a86c6181SAlex Tomas 	if (ex != EXT_FIRST_EXTENT(eh)) {
1298a86c6181SAlex Tomas 		/* we correct tree if first leaf got modified only */
1299a86c6181SAlex Tomas 		return 0;
1300a86c6181SAlex Tomas 	}
1301a86c6181SAlex Tomas 
1302a86c6181SAlex Tomas 	/*
1303d0d856e8SRandy Dunlap 	 * TODO: we need correction if border is smaller than current one
1304a86c6181SAlex Tomas 	 */
1305a86c6181SAlex Tomas 	k = depth - 1;
1306a86c6181SAlex Tomas 	border = path[depth].p_ext->ee_block;
13077e028976SAvantika Mathur 	err = ext4_ext_get_access(handle, inode, path + k);
13087e028976SAvantika Mathur 	if (err)
1309a86c6181SAlex Tomas 		return err;
1310a86c6181SAlex Tomas 	path[k].p_idx->ei_block = border;
13117e028976SAvantika Mathur 	err = ext4_ext_dirty(handle, inode, path + k);
13127e028976SAvantika Mathur 	if (err)
1313a86c6181SAlex Tomas 		return err;
1314a86c6181SAlex Tomas 
1315a86c6181SAlex Tomas 	while (k--) {
1316a86c6181SAlex Tomas 		/* change all left-side indexes */
1317a86c6181SAlex Tomas 		if (path[k+1].p_idx != EXT_FIRST_INDEX(path[k+1].p_hdr))
1318a86c6181SAlex Tomas 			break;
13197e028976SAvantika Mathur 		err = ext4_ext_get_access(handle, inode, path + k);
13207e028976SAvantika Mathur 		if (err)
1321a86c6181SAlex Tomas 			break;
1322a86c6181SAlex Tomas 		path[k].p_idx->ei_block = border;
13237e028976SAvantika Mathur 		err = ext4_ext_dirty(handle, inode, path + k);
13247e028976SAvantika Mathur 		if (err)
1325a86c6181SAlex Tomas 			break;
1326a86c6181SAlex Tomas 	}
1327a86c6181SAlex Tomas 
1328a86c6181SAlex Tomas 	return err;
1329a86c6181SAlex Tomas }
1330a86c6181SAlex Tomas 
133109b88252SAvantika Mathur static int
1332a86c6181SAlex Tomas ext4_can_extents_be_merged(struct inode *inode, struct ext4_extent *ex1,
1333a86c6181SAlex Tomas 				struct ext4_extent *ex2)
1334a86c6181SAlex Tomas {
1335749269faSAmit Arora 	unsigned short ext1_ee_len, ext2_ee_len, max_len;
1336a2df2a63SAmit Arora 
1337a2df2a63SAmit Arora 	/*
1338a2df2a63SAmit Arora 	 * Make sure that either both extents are uninitialized, or
1339a2df2a63SAmit Arora 	 * both are _not_.
1340a2df2a63SAmit Arora 	 */
1341a2df2a63SAmit Arora 	if (ext4_ext_is_uninitialized(ex1) ^ ext4_ext_is_uninitialized(ex2))
1342a2df2a63SAmit Arora 		return 0;
1343a2df2a63SAmit Arora 
1344749269faSAmit Arora 	if (ext4_ext_is_uninitialized(ex1))
1345749269faSAmit Arora 		max_len = EXT_UNINIT_MAX_LEN;
1346749269faSAmit Arora 	else
1347749269faSAmit Arora 		max_len = EXT_INIT_MAX_LEN;
1348749269faSAmit Arora 
1349a2df2a63SAmit Arora 	ext1_ee_len = ext4_ext_get_actual_len(ex1);
1350a2df2a63SAmit Arora 	ext2_ee_len = ext4_ext_get_actual_len(ex2);
1351a2df2a63SAmit Arora 
1352a2df2a63SAmit Arora 	if (le32_to_cpu(ex1->ee_block) + ext1_ee_len !=
135363f57933SAndrew Morton 			le32_to_cpu(ex2->ee_block))
1354a86c6181SAlex Tomas 		return 0;
1355a86c6181SAlex Tomas 
1356471d4011SSuparna Bhattacharya 	/*
1357471d4011SSuparna Bhattacharya 	 * To allow future support for preallocated extents to be added
1358471d4011SSuparna Bhattacharya 	 * as an RO_COMPAT feature, refuse to merge to extents if
1359d0d856e8SRandy Dunlap 	 * this can result in the top bit of ee_len being set.
1360471d4011SSuparna Bhattacharya 	 */
1361749269faSAmit Arora 	if (ext1_ee_len + ext2_ee_len > max_len)
1362471d4011SSuparna Bhattacharya 		return 0;
1363bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST
1364b939e376SAneesh Kumar K.V 	if (ext1_ee_len >= 4)
1365a86c6181SAlex Tomas 		return 0;
1366a86c6181SAlex Tomas #endif
1367a86c6181SAlex Tomas 
1368a2df2a63SAmit Arora 	if (ext_pblock(ex1) + ext1_ee_len == ext_pblock(ex2))
1369a86c6181SAlex Tomas 		return 1;
1370a86c6181SAlex Tomas 	return 0;
1371a86c6181SAlex Tomas }
1372a86c6181SAlex Tomas 
1373a86c6181SAlex Tomas /*
137456055d3aSAmit Arora  * This function tries to merge the "ex" extent to the next extent in the tree.
137556055d3aSAmit Arora  * It always tries to merge towards right. If you want to merge towards
137656055d3aSAmit Arora  * left, pass "ex - 1" as argument instead of "ex".
137756055d3aSAmit Arora  * Returns 0 if the extents (ex and ex+1) were _not_ merged and returns
137856055d3aSAmit Arora  * 1 if they got merged.
137956055d3aSAmit Arora  */
138056055d3aSAmit Arora int ext4_ext_try_to_merge(struct inode *inode,
138156055d3aSAmit Arora 			  struct ext4_ext_path *path,
138256055d3aSAmit Arora 			  struct ext4_extent *ex)
138356055d3aSAmit Arora {
138456055d3aSAmit Arora 	struct ext4_extent_header *eh;
138556055d3aSAmit Arora 	unsigned int depth, len;
138656055d3aSAmit Arora 	int merge_done = 0;
138756055d3aSAmit Arora 	int uninitialized = 0;
138856055d3aSAmit Arora 
138956055d3aSAmit Arora 	depth = ext_depth(inode);
139056055d3aSAmit Arora 	BUG_ON(path[depth].p_hdr == NULL);
139156055d3aSAmit Arora 	eh = path[depth].p_hdr;
139256055d3aSAmit Arora 
139356055d3aSAmit Arora 	while (ex < EXT_LAST_EXTENT(eh)) {
139456055d3aSAmit Arora 		if (!ext4_can_extents_be_merged(inode, ex, ex + 1))
139556055d3aSAmit Arora 			break;
139656055d3aSAmit Arora 		/* merge with next extent! */
139756055d3aSAmit Arora 		if (ext4_ext_is_uninitialized(ex))
139856055d3aSAmit Arora 			uninitialized = 1;
139956055d3aSAmit Arora 		ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
140056055d3aSAmit Arora 				+ ext4_ext_get_actual_len(ex + 1));
140156055d3aSAmit Arora 		if (uninitialized)
140256055d3aSAmit Arora 			ext4_ext_mark_uninitialized(ex);
140356055d3aSAmit Arora 
140456055d3aSAmit Arora 		if (ex + 1 < EXT_LAST_EXTENT(eh)) {
140556055d3aSAmit Arora 			len = (EXT_LAST_EXTENT(eh) - ex - 1)
140656055d3aSAmit Arora 				* sizeof(struct ext4_extent);
140756055d3aSAmit Arora 			memmove(ex + 1, ex + 2, len);
140856055d3aSAmit Arora 		}
1409e8546d06SMarcin Slusarz 		le16_add_cpu(&eh->eh_entries, -1);
141056055d3aSAmit Arora 		merge_done = 1;
141156055d3aSAmit Arora 		WARN_ON(eh->eh_entries == 0);
141256055d3aSAmit Arora 		if (!eh->eh_entries)
141356055d3aSAmit Arora 			ext4_error(inode->i_sb, "ext4_ext_try_to_merge",
141456055d3aSAmit Arora 			   "inode#%lu, eh->eh_entries = 0!", inode->i_ino);
141556055d3aSAmit Arora 	}
141656055d3aSAmit Arora 
141756055d3aSAmit Arora 	return merge_done;
141856055d3aSAmit Arora }
141956055d3aSAmit Arora 
142056055d3aSAmit Arora /*
142125d14f98SAmit Arora  * check if a portion of the "newext" extent overlaps with an
142225d14f98SAmit Arora  * existing extent.
142325d14f98SAmit Arora  *
142425d14f98SAmit Arora  * If there is an overlap discovered, it updates the length of the newext
142525d14f98SAmit Arora  * such that there will be no overlap, and then returns 1.
142625d14f98SAmit Arora  * If there is no overlap found, it returns 0.
142725d14f98SAmit Arora  */
142825d14f98SAmit Arora unsigned int ext4_ext_check_overlap(struct inode *inode,
142925d14f98SAmit Arora 				    struct ext4_extent *newext,
143025d14f98SAmit Arora 				    struct ext4_ext_path *path)
143125d14f98SAmit Arora {
1432725d26d3SAneesh Kumar K.V 	ext4_lblk_t b1, b2;
143325d14f98SAmit Arora 	unsigned int depth, len1;
143425d14f98SAmit Arora 	unsigned int ret = 0;
143525d14f98SAmit Arora 
143625d14f98SAmit Arora 	b1 = le32_to_cpu(newext->ee_block);
1437a2df2a63SAmit Arora 	len1 = ext4_ext_get_actual_len(newext);
143825d14f98SAmit Arora 	depth = ext_depth(inode);
143925d14f98SAmit Arora 	if (!path[depth].p_ext)
144025d14f98SAmit Arora 		goto out;
144125d14f98SAmit Arora 	b2 = le32_to_cpu(path[depth].p_ext->ee_block);
144225d14f98SAmit Arora 
144325d14f98SAmit Arora 	/*
144425d14f98SAmit Arora 	 * get the next allocated block if the extent in the path
144525d14f98SAmit Arora 	 * is before the requested block(s)
144625d14f98SAmit Arora 	 */
144725d14f98SAmit Arora 	if (b2 < b1) {
144825d14f98SAmit Arora 		b2 = ext4_ext_next_allocated_block(path);
144925d14f98SAmit Arora 		if (b2 == EXT_MAX_BLOCK)
145025d14f98SAmit Arora 			goto out;
145125d14f98SAmit Arora 	}
145225d14f98SAmit Arora 
1453725d26d3SAneesh Kumar K.V 	/* check for wrap through zero on extent logical start block*/
145425d14f98SAmit Arora 	if (b1 + len1 < b1) {
145525d14f98SAmit Arora 		len1 = EXT_MAX_BLOCK - b1;
145625d14f98SAmit Arora 		newext->ee_len = cpu_to_le16(len1);
145725d14f98SAmit Arora 		ret = 1;
145825d14f98SAmit Arora 	}
145925d14f98SAmit Arora 
146025d14f98SAmit Arora 	/* check for overlap */
146125d14f98SAmit Arora 	if (b1 + len1 > b2) {
146225d14f98SAmit Arora 		newext->ee_len = cpu_to_le16(b2 - b1);
146325d14f98SAmit Arora 		ret = 1;
146425d14f98SAmit Arora 	}
146525d14f98SAmit Arora out:
146625d14f98SAmit Arora 	return ret;
146725d14f98SAmit Arora }
146825d14f98SAmit Arora 
146925d14f98SAmit Arora /*
1470d0d856e8SRandy Dunlap  * ext4_ext_insert_extent:
1471d0d856e8SRandy Dunlap  * tries to merge requsted extent into the existing extent or
1472d0d856e8SRandy Dunlap  * inserts requested extent as new one into the tree,
1473d0d856e8SRandy Dunlap  * creating new leaf in the no-space case.
1474a86c6181SAlex Tomas  */
1475a86c6181SAlex Tomas int ext4_ext_insert_extent(handle_t *handle, struct inode *inode,
1476a86c6181SAlex Tomas 				struct ext4_ext_path *path,
1477a86c6181SAlex Tomas 				struct ext4_extent *newext)
1478a86c6181SAlex Tomas {
1479a86c6181SAlex Tomas 	struct ext4_extent_header *eh;
1480a86c6181SAlex Tomas 	struct ext4_extent *ex, *fex;
1481a86c6181SAlex Tomas 	struct ext4_extent *nearex; /* nearest extent */
1482a86c6181SAlex Tomas 	struct ext4_ext_path *npath = NULL;
1483725d26d3SAneesh Kumar K.V 	int depth, len, err;
1484725d26d3SAneesh Kumar K.V 	ext4_lblk_t next;
1485a2df2a63SAmit Arora 	unsigned uninitialized = 0;
1486a86c6181SAlex Tomas 
1487a2df2a63SAmit Arora 	BUG_ON(ext4_ext_get_actual_len(newext) == 0);
1488a86c6181SAlex Tomas 	depth = ext_depth(inode);
1489a86c6181SAlex Tomas 	ex = path[depth].p_ext;
1490a86c6181SAlex Tomas 	BUG_ON(path[depth].p_hdr == NULL);
1491a86c6181SAlex Tomas 
1492a86c6181SAlex Tomas 	/* try to insert block into found extent and return */
1493a86c6181SAlex Tomas 	if (ex && ext4_can_extents_be_merged(inode, ex, newext)) {
14942ae02107SMingming Cao 		ext_debug("append %d block to %d:%d (from %llu)\n",
1495a2df2a63SAmit Arora 				ext4_ext_get_actual_len(newext),
1496a86c6181SAlex Tomas 				le32_to_cpu(ex->ee_block),
1497a2df2a63SAmit Arora 				ext4_ext_get_actual_len(ex), ext_pblock(ex));
14987e028976SAvantika Mathur 		err = ext4_ext_get_access(handle, inode, path + depth);
14997e028976SAvantika Mathur 		if (err)
1500a86c6181SAlex Tomas 			return err;
1501a2df2a63SAmit Arora 
1502a2df2a63SAmit Arora 		/*
1503a2df2a63SAmit Arora 		 * ext4_can_extents_be_merged should have checked that either
1504a2df2a63SAmit Arora 		 * both extents are uninitialized, or both aren't. Thus we
1505a2df2a63SAmit Arora 		 * need to check only one of them here.
1506a2df2a63SAmit Arora 		 */
1507a2df2a63SAmit Arora 		if (ext4_ext_is_uninitialized(ex))
1508a2df2a63SAmit Arora 			uninitialized = 1;
1509a2df2a63SAmit Arora 		ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
1510a2df2a63SAmit Arora 					+ ext4_ext_get_actual_len(newext));
1511a2df2a63SAmit Arora 		if (uninitialized)
1512a2df2a63SAmit Arora 			ext4_ext_mark_uninitialized(ex);
1513a86c6181SAlex Tomas 		eh = path[depth].p_hdr;
1514a86c6181SAlex Tomas 		nearex = ex;
1515a86c6181SAlex Tomas 		goto merge;
1516a86c6181SAlex Tomas 	}
1517a86c6181SAlex Tomas 
1518a86c6181SAlex Tomas repeat:
1519a86c6181SAlex Tomas 	depth = ext_depth(inode);
1520a86c6181SAlex Tomas 	eh = path[depth].p_hdr;
1521a86c6181SAlex Tomas 	if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))
1522a86c6181SAlex Tomas 		goto has_space;
1523a86c6181SAlex Tomas 
1524a86c6181SAlex Tomas 	/* probably next leaf has space for us? */
1525a86c6181SAlex Tomas 	fex = EXT_LAST_EXTENT(eh);
1526a86c6181SAlex Tomas 	next = ext4_ext_next_leaf_block(inode, path);
1527a86c6181SAlex Tomas 	if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block)
1528a86c6181SAlex Tomas 	    && next != EXT_MAX_BLOCK) {
1529a86c6181SAlex Tomas 		ext_debug("next leaf block - %d\n", next);
1530a86c6181SAlex Tomas 		BUG_ON(npath != NULL);
1531a86c6181SAlex Tomas 		npath = ext4_ext_find_extent(inode, next, NULL);
1532a86c6181SAlex Tomas 		if (IS_ERR(npath))
1533a86c6181SAlex Tomas 			return PTR_ERR(npath);
1534a86c6181SAlex Tomas 		BUG_ON(npath->p_depth != path->p_depth);
1535a86c6181SAlex Tomas 		eh = npath[depth].p_hdr;
1536a86c6181SAlex Tomas 		if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) {
1537a86c6181SAlex Tomas 			ext_debug("next leaf isnt full(%d)\n",
1538a86c6181SAlex Tomas 				  le16_to_cpu(eh->eh_entries));
1539a86c6181SAlex Tomas 			path = npath;
1540a86c6181SAlex Tomas 			goto repeat;
1541a86c6181SAlex Tomas 		}
1542a86c6181SAlex Tomas 		ext_debug("next leaf has no free space(%d,%d)\n",
1543a86c6181SAlex Tomas 			  le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
1544a86c6181SAlex Tomas 	}
1545a86c6181SAlex Tomas 
1546a86c6181SAlex Tomas 	/*
1547d0d856e8SRandy Dunlap 	 * There is no free space in the found leaf.
1548d0d856e8SRandy Dunlap 	 * We're gonna add a new leaf in the tree.
1549a86c6181SAlex Tomas 	 */
1550a86c6181SAlex Tomas 	err = ext4_ext_create_new_leaf(handle, inode, path, newext);
1551a86c6181SAlex Tomas 	if (err)
1552a86c6181SAlex Tomas 		goto cleanup;
1553a86c6181SAlex Tomas 	depth = ext_depth(inode);
1554a86c6181SAlex Tomas 	eh = path[depth].p_hdr;
1555a86c6181SAlex Tomas 
1556a86c6181SAlex Tomas has_space:
1557a86c6181SAlex Tomas 	nearex = path[depth].p_ext;
1558a86c6181SAlex Tomas 
15597e028976SAvantika Mathur 	err = ext4_ext_get_access(handle, inode, path + depth);
15607e028976SAvantika Mathur 	if (err)
1561a86c6181SAlex Tomas 		goto cleanup;
1562a86c6181SAlex Tomas 
1563a86c6181SAlex Tomas 	if (!nearex) {
1564a86c6181SAlex Tomas 		/* there is no extent in this leaf, create first one */
15652ae02107SMingming Cao 		ext_debug("first extent in the leaf: %d:%llu:%d\n",
1566a86c6181SAlex Tomas 				le32_to_cpu(newext->ee_block),
1567f65e6fbaSAlex Tomas 				ext_pblock(newext),
1568a2df2a63SAmit Arora 				ext4_ext_get_actual_len(newext));
1569a86c6181SAlex Tomas 		path[depth].p_ext = EXT_FIRST_EXTENT(eh);
1570a86c6181SAlex Tomas 	} else if (le32_to_cpu(newext->ee_block)
1571a86c6181SAlex Tomas 			   > le32_to_cpu(nearex->ee_block)) {
1572a86c6181SAlex Tomas /*		BUG_ON(newext->ee_block == nearex->ee_block); */
1573a86c6181SAlex Tomas 		if (nearex != EXT_LAST_EXTENT(eh)) {
1574a86c6181SAlex Tomas 			len = EXT_MAX_EXTENT(eh) - nearex;
1575a86c6181SAlex Tomas 			len = (len - 1) * sizeof(struct ext4_extent);
1576a86c6181SAlex Tomas 			len = len < 0 ? 0 : len;
15772ae02107SMingming Cao 			ext_debug("insert %d:%llu:%d after: nearest 0x%p, "
1578a86c6181SAlex Tomas 					"move %d from 0x%p to 0x%p\n",
1579a86c6181SAlex Tomas 					le32_to_cpu(newext->ee_block),
1580f65e6fbaSAlex Tomas 					ext_pblock(newext),
1581a2df2a63SAmit Arora 					ext4_ext_get_actual_len(newext),
1582a86c6181SAlex Tomas 					nearex, len, nearex + 1, nearex + 2);
1583a86c6181SAlex Tomas 			memmove(nearex + 2, nearex + 1, len);
1584a86c6181SAlex Tomas 		}
1585a86c6181SAlex Tomas 		path[depth].p_ext = nearex + 1;
1586a86c6181SAlex Tomas 	} else {
1587a86c6181SAlex Tomas 		BUG_ON(newext->ee_block == nearex->ee_block);
1588a86c6181SAlex Tomas 		len = (EXT_MAX_EXTENT(eh) - nearex) * sizeof(struct ext4_extent);
1589a86c6181SAlex Tomas 		len = len < 0 ? 0 : len;
15902ae02107SMingming Cao 		ext_debug("insert %d:%llu:%d before: nearest 0x%p, "
1591a86c6181SAlex Tomas 				"move %d from 0x%p to 0x%p\n",
1592a86c6181SAlex Tomas 				le32_to_cpu(newext->ee_block),
1593f65e6fbaSAlex Tomas 				ext_pblock(newext),
1594a2df2a63SAmit Arora 				ext4_ext_get_actual_len(newext),
1595a86c6181SAlex Tomas 				nearex, len, nearex + 1, nearex + 2);
1596a86c6181SAlex Tomas 		memmove(nearex + 1, nearex, len);
1597a86c6181SAlex Tomas 		path[depth].p_ext = nearex;
1598a86c6181SAlex Tomas 	}
1599a86c6181SAlex Tomas 
1600e8546d06SMarcin Slusarz 	le16_add_cpu(&eh->eh_entries, 1);
1601a86c6181SAlex Tomas 	nearex = path[depth].p_ext;
1602a86c6181SAlex Tomas 	nearex->ee_block = newext->ee_block;
1603b377611dSAneesh Kumar K.V 	ext4_ext_store_pblock(nearex, ext_pblock(newext));
1604a86c6181SAlex Tomas 	nearex->ee_len = newext->ee_len;
1605a86c6181SAlex Tomas 
1606a86c6181SAlex Tomas merge:
1607a86c6181SAlex Tomas 	/* try to merge extents to the right */
160856055d3aSAmit Arora 	ext4_ext_try_to_merge(inode, path, nearex);
1609a86c6181SAlex Tomas 
1610a86c6181SAlex Tomas 	/* try to merge extents to the left */
1611a86c6181SAlex Tomas 
1612a86c6181SAlex Tomas 	/* time to correct all indexes above */
1613a86c6181SAlex Tomas 	err = ext4_ext_correct_indexes(handle, inode, path);
1614a86c6181SAlex Tomas 	if (err)
1615a86c6181SAlex Tomas 		goto cleanup;
1616a86c6181SAlex Tomas 
1617a86c6181SAlex Tomas 	err = ext4_ext_dirty(handle, inode, path + depth);
1618a86c6181SAlex Tomas 
1619a86c6181SAlex Tomas cleanup:
1620a86c6181SAlex Tomas 	if (npath) {
1621a86c6181SAlex Tomas 		ext4_ext_drop_refs(npath);
1622a86c6181SAlex Tomas 		kfree(npath);
1623a86c6181SAlex Tomas 	}
1624a86c6181SAlex Tomas 	ext4_ext_invalidate_cache(inode);
1625a86c6181SAlex Tomas 	return err;
1626a86c6181SAlex Tomas }
1627a86c6181SAlex Tomas 
16286873fa0dSEric Sandeen int ext4_ext_walk_space(struct inode *inode, ext4_lblk_t block,
16296873fa0dSEric Sandeen 			ext4_lblk_t num, ext_prepare_callback func,
16306873fa0dSEric Sandeen 			void *cbdata)
16316873fa0dSEric Sandeen {
16326873fa0dSEric Sandeen 	struct ext4_ext_path *path = NULL;
16336873fa0dSEric Sandeen 	struct ext4_ext_cache cbex;
16346873fa0dSEric Sandeen 	struct ext4_extent *ex;
16356873fa0dSEric Sandeen 	ext4_lblk_t next, start = 0, end = 0;
16366873fa0dSEric Sandeen 	ext4_lblk_t last = block + num;
16376873fa0dSEric Sandeen 	int depth, exists, err = 0;
16386873fa0dSEric Sandeen 
16396873fa0dSEric Sandeen 	BUG_ON(func == NULL);
16406873fa0dSEric Sandeen 	BUG_ON(inode == NULL);
16416873fa0dSEric Sandeen 
16426873fa0dSEric Sandeen 	while (block < last && block != EXT_MAX_BLOCK) {
16436873fa0dSEric Sandeen 		num = last - block;
16446873fa0dSEric Sandeen 		/* find extent for this block */
16456873fa0dSEric Sandeen 		path = ext4_ext_find_extent(inode, block, path);
16466873fa0dSEric Sandeen 		if (IS_ERR(path)) {
16476873fa0dSEric Sandeen 			err = PTR_ERR(path);
16486873fa0dSEric Sandeen 			path = NULL;
16496873fa0dSEric Sandeen 			break;
16506873fa0dSEric Sandeen 		}
16516873fa0dSEric Sandeen 
16526873fa0dSEric Sandeen 		depth = ext_depth(inode);
16536873fa0dSEric Sandeen 		BUG_ON(path[depth].p_hdr == NULL);
16546873fa0dSEric Sandeen 		ex = path[depth].p_ext;
16556873fa0dSEric Sandeen 		next = ext4_ext_next_allocated_block(path);
16566873fa0dSEric Sandeen 
16576873fa0dSEric Sandeen 		exists = 0;
16586873fa0dSEric Sandeen 		if (!ex) {
16596873fa0dSEric Sandeen 			/* there is no extent yet, so try to allocate
16606873fa0dSEric Sandeen 			 * all requested space */
16616873fa0dSEric Sandeen 			start = block;
16626873fa0dSEric Sandeen 			end = block + num;
16636873fa0dSEric Sandeen 		} else if (le32_to_cpu(ex->ee_block) > block) {
16646873fa0dSEric Sandeen 			/* need to allocate space before found extent */
16656873fa0dSEric Sandeen 			start = block;
16666873fa0dSEric Sandeen 			end = le32_to_cpu(ex->ee_block);
16676873fa0dSEric Sandeen 			if (block + num < end)
16686873fa0dSEric Sandeen 				end = block + num;
16696873fa0dSEric Sandeen 		} else if (block >= le32_to_cpu(ex->ee_block)
16706873fa0dSEric Sandeen 					+ ext4_ext_get_actual_len(ex)) {
16716873fa0dSEric Sandeen 			/* need to allocate space after found extent */
16726873fa0dSEric Sandeen 			start = block;
16736873fa0dSEric Sandeen 			end = block + num;
16746873fa0dSEric Sandeen 			if (end >= next)
16756873fa0dSEric Sandeen 				end = next;
16766873fa0dSEric Sandeen 		} else if (block >= le32_to_cpu(ex->ee_block)) {
16776873fa0dSEric Sandeen 			/*
16786873fa0dSEric Sandeen 			 * some part of requested space is covered
16796873fa0dSEric Sandeen 			 * by found extent
16806873fa0dSEric Sandeen 			 */
16816873fa0dSEric Sandeen 			start = block;
16826873fa0dSEric Sandeen 			end = le32_to_cpu(ex->ee_block)
16836873fa0dSEric Sandeen 				+ ext4_ext_get_actual_len(ex);
16846873fa0dSEric Sandeen 			if (block + num < end)
16856873fa0dSEric Sandeen 				end = block + num;
16866873fa0dSEric Sandeen 			exists = 1;
16876873fa0dSEric Sandeen 		} else {
16886873fa0dSEric Sandeen 			BUG();
16896873fa0dSEric Sandeen 		}
16906873fa0dSEric Sandeen 		BUG_ON(end <= start);
16916873fa0dSEric Sandeen 
16926873fa0dSEric Sandeen 		if (!exists) {
16936873fa0dSEric Sandeen 			cbex.ec_block = start;
16946873fa0dSEric Sandeen 			cbex.ec_len = end - start;
16956873fa0dSEric Sandeen 			cbex.ec_start = 0;
16966873fa0dSEric Sandeen 			cbex.ec_type = EXT4_EXT_CACHE_GAP;
16976873fa0dSEric Sandeen 		} else {
16986873fa0dSEric Sandeen 			cbex.ec_block = le32_to_cpu(ex->ee_block);
16996873fa0dSEric Sandeen 			cbex.ec_len = ext4_ext_get_actual_len(ex);
17006873fa0dSEric Sandeen 			cbex.ec_start = ext_pblock(ex);
17016873fa0dSEric Sandeen 			cbex.ec_type = EXT4_EXT_CACHE_EXTENT;
17026873fa0dSEric Sandeen 		}
17036873fa0dSEric Sandeen 
17046873fa0dSEric Sandeen 		BUG_ON(cbex.ec_len == 0);
17056873fa0dSEric Sandeen 		err = func(inode, path, &cbex, ex, cbdata);
17066873fa0dSEric Sandeen 		ext4_ext_drop_refs(path);
17076873fa0dSEric Sandeen 
17086873fa0dSEric Sandeen 		if (err < 0)
17096873fa0dSEric Sandeen 			break;
17106873fa0dSEric Sandeen 
17116873fa0dSEric Sandeen 		if (err == EXT_REPEAT)
17126873fa0dSEric Sandeen 			continue;
17136873fa0dSEric Sandeen 		else if (err == EXT_BREAK) {
17146873fa0dSEric Sandeen 			err = 0;
17156873fa0dSEric Sandeen 			break;
17166873fa0dSEric Sandeen 		}
17176873fa0dSEric Sandeen 
17186873fa0dSEric Sandeen 		if (ext_depth(inode) != depth) {
17196873fa0dSEric Sandeen 			/* depth was changed. we have to realloc path */
17206873fa0dSEric Sandeen 			kfree(path);
17216873fa0dSEric Sandeen 			path = NULL;
17226873fa0dSEric Sandeen 		}
17236873fa0dSEric Sandeen 
17246873fa0dSEric Sandeen 		block = cbex.ec_block + cbex.ec_len;
17256873fa0dSEric Sandeen 	}
17266873fa0dSEric Sandeen 
17276873fa0dSEric Sandeen 	if (path) {
17286873fa0dSEric Sandeen 		ext4_ext_drop_refs(path);
17296873fa0dSEric Sandeen 		kfree(path);
17306873fa0dSEric Sandeen 	}
17316873fa0dSEric Sandeen 
17326873fa0dSEric Sandeen 	return err;
17336873fa0dSEric Sandeen }
17346873fa0dSEric Sandeen 
173509b88252SAvantika Mathur static void
1736725d26d3SAneesh Kumar K.V ext4_ext_put_in_cache(struct inode *inode, ext4_lblk_t block,
1737dd54567aSMingming Cao 			__u32 len, ext4_fsblk_t start, int type)
1738a86c6181SAlex Tomas {
1739a86c6181SAlex Tomas 	struct ext4_ext_cache *cex;
1740a86c6181SAlex Tomas 	BUG_ON(len == 0);
1741a86c6181SAlex Tomas 	cex = &EXT4_I(inode)->i_cached_extent;
1742a86c6181SAlex Tomas 	cex->ec_type = type;
1743a86c6181SAlex Tomas 	cex->ec_block = block;
1744a86c6181SAlex Tomas 	cex->ec_len = len;
1745a86c6181SAlex Tomas 	cex->ec_start = start;
1746a86c6181SAlex Tomas }
1747a86c6181SAlex Tomas 
1748a86c6181SAlex Tomas /*
1749d0d856e8SRandy Dunlap  * ext4_ext_put_gap_in_cache:
1750d0d856e8SRandy Dunlap  * calculate boundaries of the gap that the requested block fits into
1751a86c6181SAlex Tomas  * and cache this gap
1752a86c6181SAlex Tomas  */
175309b88252SAvantika Mathur static void
1754a86c6181SAlex Tomas ext4_ext_put_gap_in_cache(struct inode *inode, struct ext4_ext_path *path,
1755725d26d3SAneesh Kumar K.V 				ext4_lblk_t block)
1756a86c6181SAlex Tomas {
1757a86c6181SAlex Tomas 	int depth = ext_depth(inode);
1758725d26d3SAneesh Kumar K.V 	unsigned long len;
1759725d26d3SAneesh Kumar K.V 	ext4_lblk_t lblock;
1760a86c6181SAlex Tomas 	struct ext4_extent *ex;
1761a86c6181SAlex Tomas 
1762a86c6181SAlex Tomas 	ex = path[depth].p_ext;
1763a86c6181SAlex Tomas 	if (ex == NULL) {
1764a86c6181SAlex Tomas 		/* there is no extent yet, so gap is [0;-] */
1765a86c6181SAlex Tomas 		lblock = 0;
1766a86c6181SAlex Tomas 		len = EXT_MAX_BLOCK;
1767a86c6181SAlex Tomas 		ext_debug("cache gap(whole file):");
1768a86c6181SAlex Tomas 	} else if (block < le32_to_cpu(ex->ee_block)) {
1769a86c6181SAlex Tomas 		lblock = block;
1770a86c6181SAlex Tomas 		len = le32_to_cpu(ex->ee_block) - block;
1771bba90743SEric Sandeen 		ext_debug("cache gap(before): %u [%u:%u]",
1772bba90743SEric Sandeen 				block,
1773bba90743SEric Sandeen 				le32_to_cpu(ex->ee_block),
1774bba90743SEric Sandeen 				 ext4_ext_get_actual_len(ex));
1775a86c6181SAlex Tomas 	} else if (block >= le32_to_cpu(ex->ee_block)
1776a2df2a63SAmit Arora 			+ ext4_ext_get_actual_len(ex)) {
1777725d26d3SAneesh Kumar K.V 		ext4_lblk_t next;
1778a86c6181SAlex Tomas 		lblock = le32_to_cpu(ex->ee_block)
1779a2df2a63SAmit Arora 			+ ext4_ext_get_actual_len(ex);
1780725d26d3SAneesh Kumar K.V 
1781725d26d3SAneesh Kumar K.V 		next = ext4_ext_next_allocated_block(path);
1782bba90743SEric Sandeen 		ext_debug("cache gap(after): [%u:%u] %u",
1783bba90743SEric Sandeen 				le32_to_cpu(ex->ee_block),
1784bba90743SEric Sandeen 				ext4_ext_get_actual_len(ex),
1785bba90743SEric Sandeen 				block);
1786725d26d3SAneesh Kumar K.V 		BUG_ON(next == lblock);
1787725d26d3SAneesh Kumar K.V 		len = next - lblock;
1788a86c6181SAlex Tomas 	} else {
1789a86c6181SAlex Tomas 		lblock = len = 0;
1790a86c6181SAlex Tomas 		BUG();
1791a86c6181SAlex Tomas 	}
1792a86c6181SAlex Tomas 
1793bba90743SEric Sandeen 	ext_debug(" -> %u:%lu\n", lblock, len);
1794a86c6181SAlex Tomas 	ext4_ext_put_in_cache(inode, lblock, len, 0, EXT4_EXT_CACHE_GAP);
1795a86c6181SAlex Tomas }
1796a86c6181SAlex Tomas 
179709b88252SAvantika Mathur static int
1798725d26d3SAneesh Kumar K.V ext4_ext_in_cache(struct inode *inode, ext4_lblk_t block,
1799a86c6181SAlex Tomas 			struct ext4_extent *ex)
1800a86c6181SAlex Tomas {
1801a86c6181SAlex Tomas 	struct ext4_ext_cache *cex;
1802a86c6181SAlex Tomas 
1803a86c6181SAlex Tomas 	cex = &EXT4_I(inode)->i_cached_extent;
1804a86c6181SAlex Tomas 
1805a86c6181SAlex Tomas 	/* has cache valid data? */
1806a86c6181SAlex Tomas 	if (cex->ec_type == EXT4_EXT_CACHE_NO)
1807a86c6181SAlex Tomas 		return EXT4_EXT_CACHE_NO;
1808a86c6181SAlex Tomas 
1809a86c6181SAlex Tomas 	BUG_ON(cex->ec_type != EXT4_EXT_CACHE_GAP &&
1810a86c6181SAlex Tomas 			cex->ec_type != EXT4_EXT_CACHE_EXTENT);
1811a86c6181SAlex Tomas 	if (block >= cex->ec_block && block < cex->ec_block + cex->ec_len) {
1812a86c6181SAlex Tomas 		ex->ee_block = cpu_to_le32(cex->ec_block);
1813f65e6fbaSAlex Tomas 		ext4_ext_store_pblock(ex, cex->ec_start);
1814a86c6181SAlex Tomas 		ex->ee_len = cpu_to_le16(cex->ec_len);
1815bba90743SEric Sandeen 		ext_debug("%u cached by %u:%u:%llu\n",
1816bba90743SEric Sandeen 				block,
1817bba90743SEric Sandeen 				cex->ec_block, cex->ec_len, cex->ec_start);
1818a86c6181SAlex Tomas 		return cex->ec_type;
1819a86c6181SAlex Tomas 	}
1820a86c6181SAlex Tomas 
1821a86c6181SAlex Tomas 	/* not in cache */
1822a86c6181SAlex Tomas 	return EXT4_EXT_CACHE_NO;
1823a86c6181SAlex Tomas }
1824a86c6181SAlex Tomas 
1825a86c6181SAlex Tomas /*
1826d0d856e8SRandy Dunlap  * ext4_ext_rm_idx:
1827d0d856e8SRandy Dunlap  * removes index from the index block.
1828d0d856e8SRandy Dunlap  * It's used in truncate case only, thus all requests are for
1829d0d856e8SRandy Dunlap  * last index in the block only.
1830a86c6181SAlex Tomas  */
18311d03ec98SAneesh Kumar K.V static int ext4_ext_rm_idx(handle_t *handle, struct inode *inode,
1832a86c6181SAlex Tomas 			struct ext4_ext_path *path)
1833a86c6181SAlex Tomas {
1834a86c6181SAlex Tomas 	struct buffer_head *bh;
1835a86c6181SAlex Tomas 	int err;
1836f65e6fbaSAlex Tomas 	ext4_fsblk_t leaf;
1837a86c6181SAlex Tomas 
1838a86c6181SAlex Tomas 	/* free index block */
1839a86c6181SAlex Tomas 	path--;
1840f65e6fbaSAlex Tomas 	leaf = idx_pblock(path->p_idx);
1841a86c6181SAlex Tomas 	BUG_ON(path->p_hdr->eh_entries == 0);
18427e028976SAvantika Mathur 	err = ext4_ext_get_access(handle, inode, path);
18437e028976SAvantika Mathur 	if (err)
1844a86c6181SAlex Tomas 		return err;
1845e8546d06SMarcin Slusarz 	le16_add_cpu(&path->p_hdr->eh_entries, -1);
18467e028976SAvantika Mathur 	err = ext4_ext_dirty(handle, inode, path);
18477e028976SAvantika Mathur 	if (err)
1848a86c6181SAlex Tomas 		return err;
18492ae02107SMingming Cao 	ext_debug("index is empty, remove it, free block %llu\n", leaf);
1850a86c6181SAlex Tomas 	bh = sb_find_get_block(inode->i_sb, leaf);
1851a86c6181SAlex Tomas 	ext4_forget(handle, 1, inode, bh, leaf);
1852c9de560dSAlex Tomas 	ext4_free_blocks(handle, inode, leaf, 1, 1);
1853a86c6181SAlex Tomas 	return err;
1854a86c6181SAlex Tomas }
1855a86c6181SAlex Tomas 
1856a86c6181SAlex Tomas /*
1857ee12b630SMingming Cao  * ext4_ext_calc_credits_for_single_extent:
1858ee12b630SMingming Cao  * This routine returns max. credits that needed to insert an extent
1859ee12b630SMingming Cao  * to the extent tree.
1860ee12b630SMingming Cao  * When pass the actual path, the caller should calculate credits
1861ee12b630SMingming Cao  * under i_data_sem.
1862a86c6181SAlex Tomas  */
1863525f4ed8SMingming Cao int ext4_ext_calc_credits_for_single_extent(struct inode *inode, int nrblocks,
1864a86c6181SAlex Tomas 						struct ext4_ext_path *path)
1865a86c6181SAlex Tomas {
1866a86c6181SAlex Tomas 	if (path) {
1867ee12b630SMingming Cao 		int depth = ext_depth(inode);
1868f3bd1f3fSMingming Cao 		int ret = 0;
1869ee12b630SMingming Cao 
1870a86c6181SAlex Tomas 		/* probably there is space in leaf? */
1871a86c6181SAlex Tomas 		if (le16_to_cpu(path[depth].p_hdr->eh_entries)
1872ee12b630SMingming Cao 				< le16_to_cpu(path[depth].p_hdr->eh_max)) {
1873ee12b630SMingming Cao 
1874ee12b630SMingming Cao 			/*
1875ee12b630SMingming Cao 			 *  There are some space in the leaf tree, no
1876ee12b630SMingming Cao 			 *  need to account for leaf block credit
1877ee12b630SMingming Cao 			 *
1878ee12b630SMingming Cao 			 *  bitmaps and block group descriptor blocks
1879ee12b630SMingming Cao 			 *  and other metadat blocks still need to be
1880ee12b630SMingming Cao 			 *  accounted.
1881ee12b630SMingming Cao 			 */
1882525f4ed8SMingming Cao 			/* 1 bitmap, 1 block group descriptor */
1883ee12b630SMingming Cao 			ret = 2 + EXT4_META_TRANS_BLOCKS(inode->i_sb);
1884ee12b630SMingming Cao 		}
1885ee12b630SMingming Cao 	}
1886ee12b630SMingming Cao 
1887525f4ed8SMingming Cao 	return ext4_chunk_trans_blocks(inode, nrblocks);
1888a86c6181SAlex Tomas }
1889a86c6181SAlex Tomas 
1890a86c6181SAlex Tomas /*
1891ee12b630SMingming Cao  * How many index/leaf blocks need to change/allocate to modify nrblocks?
1892ee12b630SMingming Cao  *
1893ee12b630SMingming Cao  * if nrblocks are fit in a single extent (chunk flag is 1), then
1894ee12b630SMingming Cao  * in the worse case, each tree level index/leaf need to be changed
1895ee12b630SMingming Cao  * if the tree split due to insert a new extent, then the old tree
1896ee12b630SMingming Cao  * index/leaf need to be updated too
1897ee12b630SMingming Cao  *
1898ee12b630SMingming Cao  * If the nrblocks are discontiguous, they could cause
1899ee12b630SMingming Cao  * the whole tree split more than once, but this is really rare.
1900a86c6181SAlex Tomas  */
1901525f4ed8SMingming Cao int ext4_ext_index_trans_blocks(struct inode *inode, int nrblocks, int chunk)
1902ee12b630SMingming Cao {
1903ee12b630SMingming Cao 	int index;
1904ee12b630SMingming Cao 	int depth = ext_depth(inode);
1905a86c6181SAlex Tomas 
1906ee12b630SMingming Cao 	if (chunk)
1907ee12b630SMingming Cao 		index = depth * 2;
1908ee12b630SMingming Cao 	else
1909ee12b630SMingming Cao 		index = depth * 3;
1910a86c6181SAlex Tomas 
1911ee12b630SMingming Cao 	return index;
1912a86c6181SAlex Tomas }
1913a86c6181SAlex Tomas 
1914a86c6181SAlex Tomas static int ext4_remove_blocks(handle_t *handle, struct inode *inode,
1915a86c6181SAlex Tomas 				struct ext4_extent *ex,
1916725d26d3SAneesh Kumar K.V 				ext4_lblk_t from, ext4_lblk_t to)
1917a86c6181SAlex Tomas {
1918a86c6181SAlex Tomas 	struct buffer_head *bh;
1919a2df2a63SAmit Arora 	unsigned short ee_len =  ext4_ext_get_actual_len(ex);
1920c9de560dSAlex Tomas 	int i, metadata = 0;
1921a86c6181SAlex Tomas 
1922c9de560dSAlex Tomas 	if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode))
1923c9de560dSAlex Tomas 		metadata = 1;
1924a86c6181SAlex Tomas #ifdef EXTENTS_STATS
1925a86c6181SAlex Tomas 	{
1926a86c6181SAlex Tomas 		struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
1927a86c6181SAlex Tomas 		spin_lock(&sbi->s_ext_stats_lock);
1928a86c6181SAlex Tomas 		sbi->s_ext_blocks += ee_len;
1929a86c6181SAlex Tomas 		sbi->s_ext_extents++;
1930a86c6181SAlex Tomas 		if (ee_len < sbi->s_ext_min)
1931a86c6181SAlex Tomas 			sbi->s_ext_min = ee_len;
1932a86c6181SAlex Tomas 		if (ee_len > sbi->s_ext_max)
1933a86c6181SAlex Tomas 			sbi->s_ext_max = ee_len;
1934a86c6181SAlex Tomas 		if (ext_depth(inode) > sbi->s_depth_max)
1935a86c6181SAlex Tomas 			sbi->s_depth_max = ext_depth(inode);
1936a86c6181SAlex Tomas 		spin_unlock(&sbi->s_ext_stats_lock);
1937a86c6181SAlex Tomas 	}
1938a86c6181SAlex Tomas #endif
1939a86c6181SAlex Tomas 	if (from >= le32_to_cpu(ex->ee_block)
1940a2df2a63SAmit Arora 	    && to == le32_to_cpu(ex->ee_block) + ee_len - 1) {
1941a86c6181SAlex Tomas 		/* tail removal */
1942725d26d3SAneesh Kumar K.V 		ext4_lblk_t num;
1943f65e6fbaSAlex Tomas 		ext4_fsblk_t start;
1944725d26d3SAneesh Kumar K.V 
1945a2df2a63SAmit Arora 		num = le32_to_cpu(ex->ee_block) + ee_len - from;
1946a2df2a63SAmit Arora 		start = ext_pblock(ex) + ee_len - num;
1947725d26d3SAneesh Kumar K.V 		ext_debug("free last %u blocks starting %llu\n", num, start);
1948a86c6181SAlex Tomas 		for (i = 0; i < num; i++) {
1949a86c6181SAlex Tomas 			bh = sb_find_get_block(inode->i_sb, start + i);
1950a86c6181SAlex Tomas 			ext4_forget(handle, 0, inode, bh, start + i);
1951a86c6181SAlex Tomas 		}
1952c9de560dSAlex Tomas 		ext4_free_blocks(handle, inode, start, num, metadata);
1953a86c6181SAlex Tomas 	} else if (from == le32_to_cpu(ex->ee_block)
1954a2df2a63SAmit Arora 		   && to <= le32_to_cpu(ex->ee_block) + ee_len - 1) {
1955725d26d3SAneesh Kumar K.V 		printk(KERN_INFO "strange request: removal %u-%u from %u:%u\n",
1956a2df2a63SAmit Arora 			from, to, le32_to_cpu(ex->ee_block), ee_len);
1957a86c6181SAlex Tomas 	} else {
1958725d26d3SAneesh Kumar K.V 		printk(KERN_INFO "strange request: removal(2) "
1959725d26d3SAneesh Kumar K.V 				"%u-%u from %u:%u\n",
1960a2df2a63SAmit Arora 				from, to, le32_to_cpu(ex->ee_block), ee_len);
1961a86c6181SAlex Tomas 	}
1962a86c6181SAlex Tomas 	return 0;
1963a86c6181SAlex Tomas }
1964a86c6181SAlex Tomas 
1965a86c6181SAlex Tomas static int
1966a86c6181SAlex Tomas ext4_ext_rm_leaf(handle_t *handle, struct inode *inode,
1967725d26d3SAneesh Kumar K.V 		struct ext4_ext_path *path, ext4_lblk_t start)
1968a86c6181SAlex Tomas {
1969a86c6181SAlex Tomas 	int err = 0, correct_index = 0;
1970a86c6181SAlex Tomas 	int depth = ext_depth(inode), credits;
1971a86c6181SAlex Tomas 	struct ext4_extent_header *eh;
1972725d26d3SAneesh Kumar K.V 	ext4_lblk_t a, b, block;
1973725d26d3SAneesh Kumar K.V 	unsigned num;
1974725d26d3SAneesh Kumar K.V 	ext4_lblk_t ex_ee_block;
1975a86c6181SAlex Tomas 	unsigned short ex_ee_len;
1976a2df2a63SAmit Arora 	unsigned uninitialized = 0;
1977a86c6181SAlex Tomas 	struct ext4_extent *ex;
1978a86c6181SAlex Tomas 
1979c29c0ae7SAlex Tomas 	/* the header must be checked already in ext4_ext_remove_space() */
1980725d26d3SAneesh Kumar K.V 	ext_debug("truncate since %u in leaf\n", start);
1981a86c6181SAlex Tomas 	if (!path[depth].p_hdr)
1982a86c6181SAlex Tomas 		path[depth].p_hdr = ext_block_hdr(path[depth].p_bh);
1983a86c6181SAlex Tomas 	eh = path[depth].p_hdr;
1984a86c6181SAlex Tomas 	BUG_ON(eh == NULL);
1985a86c6181SAlex Tomas 
1986a86c6181SAlex Tomas 	/* find where to start removing */
1987a86c6181SAlex Tomas 	ex = EXT_LAST_EXTENT(eh);
1988a86c6181SAlex Tomas 
1989a86c6181SAlex Tomas 	ex_ee_block = le32_to_cpu(ex->ee_block);
1990a2df2a63SAmit Arora 	if (ext4_ext_is_uninitialized(ex))
1991a2df2a63SAmit Arora 		uninitialized = 1;
1992a2df2a63SAmit Arora 	ex_ee_len = ext4_ext_get_actual_len(ex);
1993a86c6181SAlex Tomas 
1994a86c6181SAlex Tomas 	while (ex >= EXT_FIRST_EXTENT(eh) &&
1995a86c6181SAlex Tomas 			ex_ee_block + ex_ee_len > start) {
1996a86c6181SAlex Tomas 		ext_debug("remove ext %lu:%u\n", ex_ee_block, ex_ee_len);
1997a86c6181SAlex Tomas 		path[depth].p_ext = ex;
1998a86c6181SAlex Tomas 
1999a86c6181SAlex Tomas 		a = ex_ee_block > start ? ex_ee_block : start;
2000a86c6181SAlex Tomas 		b = ex_ee_block + ex_ee_len - 1 < EXT_MAX_BLOCK ?
2001a86c6181SAlex Tomas 			ex_ee_block + ex_ee_len - 1 : EXT_MAX_BLOCK;
2002a86c6181SAlex Tomas 
2003a86c6181SAlex Tomas 		ext_debug("  border %u:%u\n", a, b);
2004a86c6181SAlex Tomas 
2005a86c6181SAlex Tomas 		if (a != ex_ee_block && b != ex_ee_block + ex_ee_len - 1) {
2006a86c6181SAlex Tomas 			block = 0;
2007a86c6181SAlex Tomas 			num = 0;
2008a86c6181SAlex Tomas 			BUG();
2009a86c6181SAlex Tomas 		} else if (a != ex_ee_block) {
2010a86c6181SAlex Tomas 			/* remove tail of the extent */
2011a86c6181SAlex Tomas 			block = ex_ee_block;
2012a86c6181SAlex Tomas 			num = a - block;
2013a86c6181SAlex Tomas 		} else if (b != ex_ee_block + ex_ee_len - 1) {
2014a86c6181SAlex Tomas 			/* remove head of the extent */
2015a86c6181SAlex Tomas 			block = a;
2016a86c6181SAlex Tomas 			num = b - a;
2017a86c6181SAlex Tomas 			/* there is no "make a hole" API yet */
2018a86c6181SAlex Tomas 			BUG();
2019a86c6181SAlex Tomas 		} else {
2020a86c6181SAlex Tomas 			/* remove whole extent: excellent! */
2021a86c6181SAlex Tomas 			block = ex_ee_block;
2022a86c6181SAlex Tomas 			num = 0;
2023a86c6181SAlex Tomas 			BUG_ON(a != ex_ee_block);
2024a86c6181SAlex Tomas 			BUG_ON(b != ex_ee_block + ex_ee_len - 1);
2025a86c6181SAlex Tomas 		}
2026a86c6181SAlex Tomas 
202734071da7STheodore Ts'o 		/*
202834071da7STheodore Ts'o 		 * 3 for leaf, sb, and inode plus 2 (bmap and group
202934071da7STheodore Ts'o 		 * descriptor) for each block group; assume two block
203034071da7STheodore Ts'o 		 * groups plus ex_ee_len/blocks_per_block_group for
203134071da7STheodore Ts'o 		 * the worst case
203234071da7STheodore Ts'o 		 */
203334071da7STheodore Ts'o 		credits = 7 + 2*(ex_ee_len/EXT4_BLOCKS_PER_GROUP(inode->i_sb));
2034a86c6181SAlex Tomas 		if (ex == EXT_FIRST_EXTENT(eh)) {
2035a86c6181SAlex Tomas 			correct_index = 1;
2036a86c6181SAlex Tomas 			credits += (ext_depth(inode)) + 1;
2037a86c6181SAlex Tomas 		}
2038a86c6181SAlex Tomas 		credits += 2 * EXT4_QUOTA_TRANS_BLOCKS(inode->i_sb);
2039a86c6181SAlex Tomas 
20409102e4faSShen Feng 		err = ext4_ext_journal_restart(handle, credits);
20419102e4faSShen Feng 		if (err)
2042a86c6181SAlex Tomas 			goto out;
2043a86c6181SAlex Tomas 
2044a86c6181SAlex Tomas 		err = ext4_ext_get_access(handle, inode, path + depth);
2045a86c6181SAlex Tomas 		if (err)
2046a86c6181SAlex Tomas 			goto out;
2047a86c6181SAlex Tomas 
2048a86c6181SAlex Tomas 		err = ext4_remove_blocks(handle, inode, ex, a, b);
2049a86c6181SAlex Tomas 		if (err)
2050a86c6181SAlex Tomas 			goto out;
2051a86c6181SAlex Tomas 
2052a86c6181SAlex Tomas 		if (num == 0) {
2053d0d856e8SRandy Dunlap 			/* this extent is removed; mark slot entirely unused */
2054f65e6fbaSAlex Tomas 			ext4_ext_store_pblock(ex, 0);
2055e8546d06SMarcin Slusarz 			le16_add_cpu(&eh->eh_entries, -1);
2056a86c6181SAlex Tomas 		}
2057a86c6181SAlex Tomas 
2058a86c6181SAlex Tomas 		ex->ee_block = cpu_to_le32(block);
2059a86c6181SAlex Tomas 		ex->ee_len = cpu_to_le16(num);
2060749269faSAmit Arora 		/*
2061749269faSAmit Arora 		 * Do not mark uninitialized if all the blocks in the
2062749269faSAmit Arora 		 * extent have been removed.
2063749269faSAmit Arora 		 */
2064749269faSAmit Arora 		if (uninitialized && num)
2065a2df2a63SAmit Arora 			ext4_ext_mark_uninitialized(ex);
2066a86c6181SAlex Tomas 
2067a86c6181SAlex Tomas 		err = ext4_ext_dirty(handle, inode, path + depth);
2068a86c6181SAlex Tomas 		if (err)
2069a86c6181SAlex Tomas 			goto out;
2070a86c6181SAlex Tomas 
20712ae02107SMingming Cao 		ext_debug("new extent: %u:%u:%llu\n", block, num,
2072f65e6fbaSAlex Tomas 				ext_pblock(ex));
2073a86c6181SAlex Tomas 		ex--;
2074a86c6181SAlex Tomas 		ex_ee_block = le32_to_cpu(ex->ee_block);
2075a2df2a63SAmit Arora 		ex_ee_len = ext4_ext_get_actual_len(ex);
2076a86c6181SAlex Tomas 	}
2077a86c6181SAlex Tomas 
2078a86c6181SAlex Tomas 	if (correct_index && eh->eh_entries)
2079a86c6181SAlex Tomas 		err = ext4_ext_correct_indexes(handle, inode, path);
2080a86c6181SAlex Tomas 
2081a86c6181SAlex Tomas 	/* if this leaf is free, then we should
2082a86c6181SAlex Tomas 	 * remove it from index block above */
2083a86c6181SAlex Tomas 	if (err == 0 && eh->eh_entries == 0 && path[depth].p_bh != NULL)
2084a86c6181SAlex Tomas 		err = ext4_ext_rm_idx(handle, inode, path + depth);
2085a86c6181SAlex Tomas 
2086a86c6181SAlex Tomas out:
2087a86c6181SAlex Tomas 	return err;
2088a86c6181SAlex Tomas }
2089a86c6181SAlex Tomas 
2090a86c6181SAlex Tomas /*
2091d0d856e8SRandy Dunlap  * ext4_ext_more_to_rm:
2092d0d856e8SRandy Dunlap  * returns 1 if current index has to be freed (even partial)
2093a86c6181SAlex Tomas  */
209409b88252SAvantika Mathur static int
2095a86c6181SAlex Tomas ext4_ext_more_to_rm(struct ext4_ext_path *path)
2096a86c6181SAlex Tomas {
2097a86c6181SAlex Tomas 	BUG_ON(path->p_idx == NULL);
2098a86c6181SAlex Tomas 
2099a86c6181SAlex Tomas 	if (path->p_idx < EXT_FIRST_INDEX(path->p_hdr))
2100a86c6181SAlex Tomas 		return 0;
2101a86c6181SAlex Tomas 
2102a86c6181SAlex Tomas 	/*
2103d0d856e8SRandy Dunlap 	 * if truncate on deeper level happened, it wasn't partial,
2104a86c6181SAlex Tomas 	 * so we have to consider current index for truncation
2105a86c6181SAlex Tomas 	 */
2106a86c6181SAlex Tomas 	if (le16_to_cpu(path->p_hdr->eh_entries) == path->p_block)
2107a86c6181SAlex Tomas 		return 0;
2108a86c6181SAlex Tomas 	return 1;
2109a86c6181SAlex Tomas }
2110a86c6181SAlex Tomas 
21111d03ec98SAneesh Kumar K.V static int ext4_ext_remove_space(struct inode *inode, ext4_lblk_t start)
2112a86c6181SAlex Tomas {
2113a86c6181SAlex Tomas 	struct super_block *sb = inode->i_sb;
2114a86c6181SAlex Tomas 	int depth = ext_depth(inode);
2115a86c6181SAlex Tomas 	struct ext4_ext_path *path;
2116a86c6181SAlex Tomas 	handle_t *handle;
2117a86c6181SAlex Tomas 	int i = 0, err = 0;
2118a86c6181SAlex Tomas 
2119725d26d3SAneesh Kumar K.V 	ext_debug("truncate since %u\n", start);
2120a86c6181SAlex Tomas 
2121a86c6181SAlex Tomas 	/* probably first extent we're gonna free will be last in block */
2122a86c6181SAlex Tomas 	handle = ext4_journal_start(inode, depth + 1);
2123a86c6181SAlex Tomas 	if (IS_ERR(handle))
2124a86c6181SAlex Tomas 		return PTR_ERR(handle);
2125a86c6181SAlex Tomas 
2126a86c6181SAlex Tomas 	ext4_ext_invalidate_cache(inode);
2127a86c6181SAlex Tomas 
2128a86c6181SAlex Tomas 	/*
2129d0d856e8SRandy Dunlap 	 * We start scanning from right side, freeing all the blocks
2130d0d856e8SRandy Dunlap 	 * after i_size and walking into the tree depth-wise.
2131a86c6181SAlex Tomas 	 */
2132216553c4SJosef Bacik 	path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 1), GFP_NOFS);
2133a86c6181SAlex Tomas 	if (path == NULL) {
2134a86c6181SAlex Tomas 		ext4_journal_stop(handle);
2135a86c6181SAlex Tomas 		return -ENOMEM;
2136a86c6181SAlex Tomas 	}
2137a86c6181SAlex Tomas 	path[0].p_hdr = ext_inode_hdr(inode);
2138c29c0ae7SAlex Tomas 	if (ext4_ext_check_header(inode, path[0].p_hdr, depth)) {
2139a86c6181SAlex Tomas 		err = -EIO;
2140a86c6181SAlex Tomas 		goto out;
2141a86c6181SAlex Tomas 	}
2142a86c6181SAlex Tomas 	path[0].p_depth = depth;
2143a86c6181SAlex Tomas 
2144a86c6181SAlex Tomas 	while (i >= 0 && err == 0) {
2145a86c6181SAlex Tomas 		if (i == depth) {
2146a86c6181SAlex Tomas 			/* this is leaf block */
2147a86c6181SAlex Tomas 			err = ext4_ext_rm_leaf(handle, inode, path, start);
2148d0d856e8SRandy Dunlap 			/* root level has p_bh == NULL, brelse() eats this */
2149a86c6181SAlex Tomas 			brelse(path[i].p_bh);
2150a86c6181SAlex Tomas 			path[i].p_bh = NULL;
2151a86c6181SAlex Tomas 			i--;
2152a86c6181SAlex Tomas 			continue;
2153a86c6181SAlex Tomas 		}
2154a86c6181SAlex Tomas 
2155a86c6181SAlex Tomas 		/* this is index block */
2156a86c6181SAlex Tomas 		if (!path[i].p_hdr) {
2157a86c6181SAlex Tomas 			ext_debug("initialize header\n");
2158a86c6181SAlex Tomas 			path[i].p_hdr = ext_block_hdr(path[i].p_bh);
2159a86c6181SAlex Tomas 		}
2160a86c6181SAlex Tomas 
2161a86c6181SAlex Tomas 		if (!path[i].p_idx) {
2162d0d856e8SRandy Dunlap 			/* this level hasn't been touched yet */
2163a86c6181SAlex Tomas 			path[i].p_idx = EXT_LAST_INDEX(path[i].p_hdr);
2164a86c6181SAlex Tomas 			path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries)+1;
2165a86c6181SAlex Tomas 			ext_debug("init index ptr: hdr 0x%p, num %d\n",
2166a86c6181SAlex Tomas 				  path[i].p_hdr,
2167a86c6181SAlex Tomas 				  le16_to_cpu(path[i].p_hdr->eh_entries));
2168a86c6181SAlex Tomas 		} else {
2169d0d856e8SRandy Dunlap 			/* we were already here, see at next index */
2170a86c6181SAlex Tomas 			path[i].p_idx--;
2171a86c6181SAlex Tomas 		}
2172a86c6181SAlex Tomas 
2173a86c6181SAlex Tomas 		ext_debug("level %d - index, first 0x%p, cur 0x%p\n",
2174a86c6181SAlex Tomas 				i, EXT_FIRST_INDEX(path[i].p_hdr),
2175a86c6181SAlex Tomas 				path[i].p_idx);
2176a86c6181SAlex Tomas 		if (ext4_ext_more_to_rm(path + i)) {
2177c29c0ae7SAlex Tomas 			struct buffer_head *bh;
2178a86c6181SAlex Tomas 			/* go to the next level */
21792ae02107SMingming Cao 			ext_debug("move to level %d (block %llu)\n",
2180f65e6fbaSAlex Tomas 				  i + 1, idx_pblock(path[i].p_idx));
2181a86c6181SAlex Tomas 			memset(path + i + 1, 0, sizeof(*path));
2182c29c0ae7SAlex Tomas 			bh = sb_bread(sb, idx_pblock(path[i].p_idx));
2183c29c0ae7SAlex Tomas 			if (!bh) {
2184a86c6181SAlex Tomas 				/* should we reset i_size? */
2185a86c6181SAlex Tomas 				err = -EIO;
2186a86c6181SAlex Tomas 				break;
2187a86c6181SAlex Tomas 			}
2188c29c0ae7SAlex Tomas 			if (WARN_ON(i + 1 > depth)) {
2189c29c0ae7SAlex Tomas 				err = -EIO;
2190c29c0ae7SAlex Tomas 				break;
2191c29c0ae7SAlex Tomas 			}
2192c29c0ae7SAlex Tomas 			if (ext4_ext_check_header(inode, ext_block_hdr(bh),
2193c29c0ae7SAlex Tomas 							depth - i - 1)) {
2194c29c0ae7SAlex Tomas 				err = -EIO;
2195c29c0ae7SAlex Tomas 				break;
2196c29c0ae7SAlex Tomas 			}
2197c29c0ae7SAlex Tomas 			path[i + 1].p_bh = bh;
2198a86c6181SAlex Tomas 
2199d0d856e8SRandy Dunlap 			/* save actual number of indexes since this
2200d0d856e8SRandy Dunlap 			 * number is changed at the next iteration */
2201a86c6181SAlex Tomas 			path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries);
2202a86c6181SAlex Tomas 			i++;
2203a86c6181SAlex Tomas 		} else {
2204d0d856e8SRandy Dunlap 			/* we finished processing this index, go up */
2205a86c6181SAlex Tomas 			if (path[i].p_hdr->eh_entries == 0 && i > 0) {
2206d0d856e8SRandy Dunlap 				/* index is empty, remove it;
2207a86c6181SAlex Tomas 				 * handle must be already prepared by the
2208a86c6181SAlex Tomas 				 * truncatei_leaf() */
2209a86c6181SAlex Tomas 				err = ext4_ext_rm_idx(handle, inode, path + i);
2210a86c6181SAlex Tomas 			}
2211d0d856e8SRandy Dunlap 			/* root level has p_bh == NULL, brelse() eats this */
2212a86c6181SAlex Tomas 			brelse(path[i].p_bh);
2213a86c6181SAlex Tomas 			path[i].p_bh = NULL;
2214a86c6181SAlex Tomas 			i--;
2215a86c6181SAlex Tomas 			ext_debug("return to level %d\n", i);
2216a86c6181SAlex Tomas 		}
2217a86c6181SAlex Tomas 	}
2218a86c6181SAlex Tomas 
2219a86c6181SAlex Tomas 	/* TODO: flexible tree reduction should be here */
2220a86c6181SAlex Tomas 	if (path->p_hdr->eh_entries == 0) {
2221a86c6181SAlex Tomas 		/*
2222d0d856e8SRandy Dunlap 		 * truncate to zero freed all the tree,
2223d0d856e8SRandy Dunlap 		 * so we need to correct eh_depth
2224a86c6181SAlex Tomas 		 */
2225a86c6181SAlex Tomas 		err = ext4_ext_get_access(handle, inode, path);
2226a86c6181SAlex Tomas 		if (err == 0) {
2227a86c6181SAlex Tomas 			ext_inode_hdr(inode)->eh_depth = 0;
2228a86c6181SAlex Tomas 			ext_inode_hdr(inode)->eh_max =
2229a86c6181SAlex Tomas 				cpu_to_le16(ext4_ext_space_root(inode));
2230a86c6181SAlex Tomas 			err = ext4_ext_dirty(handle, inode, path);
2231a86c6181SAlex Tomas 		}
2232a86c6181SAlex Tomas 	}
2233a86c6181SAlex Tomas out:
2234a86c6181SAlex Tomas 	ext4_ext_drop_refs(path);
2235a86c6181SAlex Tomas 	kfree(path);
2236a86c6181SAlex Tomas 	ext4_journal_stop(handle);
2237a86c6181SAlex Tomas 
2238a86c6181SAlex Tomas 	return err;
2239a86c6181SAlex Tomas }
2240a86c6181SAlex Tomas 
2241a86c6181SAlex Tomas /*
2242a86c6181SAlex Tomas  * called at mount time
2243a86c6181SAlex Tomas  */
2244a86c6181SAlex Tomas void ext4_ext_init(struct super_block *sb)
2245a86c6181SAlex Tomas {
2246a86c6181SAlex Tomas 	/*
2247a86c6181SAlex Tomas 	 * possible initialization would be here
2248a86c6181SAlex Tomas 	 */
2249a86c6181SAlex Tomas 
2250a86c6181SAlex Tomas 	if (test_opt(sb, EXTENTS)) {
22514776004fSTheodore Ts'o 		printk(KERN_INFO "EXT4-fs: file extents enabled");
2252bbf2f9fbSRobert P. J. Day #ifdef AGGRESSIVE_TEST
2253bbf2f9fbSRobert P. J. Day 		printk(", aggressive tests");
2254a86c6181SAlex Tomas #endif
2255a86c6181SAlex Tomas #ifdef CHECK_BINSEARCH
2256a86c6181SAlex Tomas 		printk(", check binsearch");
2257a86c6181SAlex Tomas #endif
2258a86c6181SAlex Tomas #ifdef EXTENTS_STATS
2259a86c6181SAlex Tomas 		printk(", stats");
2260a86c6181SAlex Tomas #endif
2261a86c6181SAlex Tomas 		printk("\n");
2262a86c6181SAlex Tomas #ifdef EXTENTS_STATS
2263a86c6181SAlex Tomas 		spin_lock_init(&EXT4_SB(sb)->s_ext_stats_lock);
2264a86c6181SAlex Tomas 		EXT4_SB(sb)->s_ext_min = 1 << 30;
2265a86c6181SAlex Tomas 		EXT4_SB(sb)->s_ext_max = 0;
2266a86c6181SAlex Tomas #endif
2267a86c6181SAlex Tomas 	}
2268a86c6181SAlex Tomas }
2269a86c6181SAlex Tomas 
2270a86c6181SAlex Tomas /*
2271a86c6181SAlex Tomas  * called at umount time
2272a86c6181SAlex Tomas  */
2273a86c6181SAlex Tomas void ext4_ext_release(struct super_block *sb)
2274a86c6181SAlex Tomas {
2275a86c6181SAlex Tomas 	if (!test_opt(sb, EXTENTS))
2276a86c6181SAlex Tomas 		return;
2277a86c6181SAlex Tomas 
2278a86c6181SAlex Tomas #ifdef EXTENTS_STATS
2279a86c6181SAlex Tomas 	if (EXT4_SB(sb)->s_ext_blocks && EXT4_SB(sb)->s_ext_extents) {
2280a86c6181SAlex Tomas 		struct ext4_sb_info *sbi = EXT4_SB(sb);
2281a86c6181SAlex Tomas 		printk(KERN_ERR "EXT4-fs: %lu blocks in %lu extents (%lu ave)\n",
2282a86c6181SAlex Tomas 			sbi->s_ext_blocks, sbi->s_ext_extents,
2283a86c6181SAlex Tomas 			sbi->s_ext_blocks / sbi->s_ext_extents);
2284a86c6181SAlex Tomas 		printk(KERN_ERR "EXT4-fs: extents: %lu min, %lu max, max depth %lu\n",
2285a86c6181SAlex Tomas 			sbi->s_ext_min, sbi->s_ext_max, sbi->s_depth_max);
2286a86c6181SAlex Tomas 	}
2287a86c6181SAlex Tomas #endif
2288a86c6181SAlex Tomas }
2289a86c6181SAlex Tomas 
2290093a088bSAneesh Kumar K.V static void bi_complete(struct bio *bio, int error)
2291093a088bSAneesh Kumar K.V {
2292093a088bSAneesh Kumar K.V 	complete((struct completion *)bio->bi_private);
2293093a088bSAneesh Kumar K.V }
2294093a088bSAneesh Kumar K.V 
2295093a088bSAneesh Kumar K.V /* FIXME!! we need to try to merge to left or right after zero-out  */
2296093a088bSAneesh Kumar K.V static int ext4_ext_zeroout(struct inode *inode, struct ext4_extent *ex)
2297093a088bSAneesh Kumar K.V {
2298093a088bSAneesh Kumar K.V 	int ret = -EIO;
2299093a088bSAneesh Kumar K.V 	struct bio *bio;
2300093a088bSAneesh Kumar K.V 	int blkbits, blocksize;
2301093a088bSAneesh Kumar K.V 	sector_t ee_pblock;
2302093a088bSAneesh Kumar K.V 	struct completion event;
2303093a088bSAneesh Kumar K.V 	unsigned int ee_len, len, done, offset;
2304093a088bSAneesh Kumar K.V 
2305093a088bSAneesh Kumar K.V 
2306093a088bSAneesh Kumar K.V 	blkbits   = inode->i_blkbits;
2307093a088bSAneesh Kumar K.V 	blocksize = inode->i_sb->s_blocksize;
2308093a088bSAneesh Kumar K.V 	ee_len    = ext4_ext_get_actual_len(ex);
2309093a088bSAneesh Kumar K.V 	ee_pblock = ext_pblock(ex);
2310093a088bSAneesh Kumar K.V 
2311093a088bSAneesh Kumar K.V 	/* convert ee_pblock to 512 byte sectors */
2312093a088bSAneesh Kumar K.V 	ee_pblock = ee_pblock << (blkbits - 9);
2313093a088bSAneesh Kumar K.V 
2314093a088bSAneesh Kumar K.V 	while (ee_len > 0) {
2315093a088bSAneesh Kumar K.V 
2316093a088bSAneesh Kumar K.V 		if (ee_len > BIO_MAX_PAGES)
2317093a088bSAneesh Kumar K.V 			len = BIO_MAX_PAGES;
2318093a088bSAneesh Kumar K.V 		else
2319093a088bSAneesh Kumar K.V 			len = ee_len;
2320093a088bSAneesh Kumar K.V 
2321093a088bSAneesh Kumar K.V 		bio = bio_alloc(GFP_NOIO, len);
2322093a088bSAneesh Kumar K.V 		if (!bio)
2323093a088bSAneesh Kumar K.V 			return -ENOMEM;
2324093a088bSAneesh Kumar K.V 		bio->bi_sector = ee_pblock;
2325093a088bSAneesh Kumar K.V 		bio->bi_bdev   = inode->i_sb->s_bdev;
2326093a088bSAneesh Kumar K.V 
2327093a088bSAneesh Kumar K.V 		done = 0;
2328093a088bSAneesh Kumar K.V 		offset = 0;
2329093a088bSAneesh Kumar K.V 		while (done < len) {
2330093a088bSAneesh Kumar K.V 			ret = bio_add_page(bio, ZERO_PAGE(0),
2331093a088bSAneesh Kumar K.V 							blocksize, offset);
2332093a088bSAneesh Kumar K.V 			if (ret != blocksize) {
2333093a088bSAneesh Kumar K.V 				/*
2334093a088bSAneesh Kumar K.V 				 * We can't add any more pages because of
2335093a088bSAneesh Kumar K.V 				 * hardware limitations.  Start a new bio.
2336093a088bSAneesh Kumar K.V 				 */
2337093a088bSAneesh Kumar K.V 				break;
2338093a088bSAneesh Kumar K.V 			}
2339093a088bSAneesh Kumar K.V 			done++;
2340093a088bSAneesh Kumar K.V 			offset += blocksize;
2341093a088bSAneesh Kumar K.V 			if (offset >= PAGE_CACHE_SIZE)
2342093a088bSAneesh Kumar K.V 				offset = 0;
2343093a088bSAneesh Kumar K.V 		}
2344093a088bSAneesh Kumar K.V 
2345093a088bSAneesh Kumar K.V 		init_completion(&event);
2346093a088bSAneesh Kumar K.V 		bio->bi_private = &event;
2347093a088bSAneesh Kumar K.V 		bio->bi_end_io = bi_complete;
2348093a088bSAneesh Kumar K.V 		submit_bio(WRITE, bio);
2349093a088bSAneesh Kumar K.V 		wait_for_completion(&event);
2350093a088bSAneesh Kumar K.V 
2351093a088bSAneesh Kumar K.V 		if (test_bit(BIO_UPTODATE, &bio->bi_flags))
2352093a088bSAneesh Kumar K.V 			ret = 0;
2353093a088bSAneesh Kumar K.V 		else {
2354093a088bSAneesh Kumar K.V 			ret = -EIO;
2355093a088bSAneesh Kumar K.V 			break;
2356093a088bSAneesh Kumar K.V 		}
2357093a088bSAneesh Kumar K.V 		bio_put(bio);
2358093a088bSAneesh Kumar K.V 		ee_len    -= done;
2359093a088bSAneesh Kumar K.V 		ee_pblock += done  << (blkbits - 9);
2360093a088bSAneesh Kumar K.V 	}
2361093a088bSAneesh Kumar K.V 	return ret;
2362093a088bSAneesh Kumar K.V }
2363093a088bSAneesh Kumar K.V 
23643977c965SAneesh Kumar K.V #define EXT4_EXT_ZERO_LEN 7
23653977c965SAneesh Kumar K.V 
236656055d3aSAmit Arora /*
236756055d3aSAmit Arora  * This function is called by ext4_ext_get_blocks() if someone tries to write
236856055d3aSAmit Arora  * to an uninitialized extent. It may result in splitting the uninitialized
236956055d3aSAmit Arora  * extent into multiple extents (upto three - one initialized and two
237056055d3aSAmit Arora  * uninitialized).
237156055d3aSAmit Arora  * There are three possibilities:
237256055d3aSAmit Arora  *   a> There is no split required: Entire extent should be initialized
237356055d3aSAmit Arora  *   b> Splits in two extents: Write is happening at either end of the extent
237456055d3aSAmit Arora  *   c> Splits in three extents: Somone is writing in middle of the extent
237556055d3aSAmit Arora  */
2376725d26d3SAneesh Kumar K.V static int ext4_ext_convert_to_initialized(handle_t *handle,
2377725d26d3SAneesh Kumar K.V 						struct inode *inode,
237856055d3aSAmit Arora 						struct ext4_ext_path *path,
2379725d26d3SAneesh Kumar K.V 						ext4_lblk_t iblock,
2380*498e5f24STheodore Ts'o 						unsigned int max_blocks)
238156055d3aSAmit Arora {
238295c3889cSAneesh Kumar K.V 	struct ext4_extent *ex, newex, orig_ex;
238356055d3aSAmit Arora 	struct ext4_extent *ex1 = NULL;
238456055d3aSAmit Arora 	struct ext4_extent *ex2 = NULL;
238556055d3aSAmit Arora 	struct ext4_extent *ex3 = NULL;
238656055d3aSAmit Arora 	struct ext4_extent_header *eh;
2387725d26d3SAneesh Kumar K.V 	ext4_lblk_t ee_block;
2388725d26d3SAneesh Kumar K.V 	unsigned int allocated, ee_len, depth;
238956055d3aSAmit Arora 	ext4_fsblk_t newblock;
239056055d3aSAmit Arora 	int err = 0;
239156055d3aSAmit Arora 	int ret = 0;
239256055d3aSAmit Arora 
239356055d3aSAmit Arora 	depth = ext_depth(inode);
239456055d3aSAmit Arora 	eh = path[depth].p_hdr;
239556055d3aSAmit Arora 	ex = path[depth].p_ext;
239656055d3aSAmit Arora 	ee_block = le32_to_cpu(ex->ee_block);
239756055d3aSAmit Arora 	ee_len = ext4_ext_get_actual_len(ex);
239856055d3aSAmit Arora 	allocated = ee_len - (iblock - ee_block);
239956055d3aSAmit Arora 	newblock = iblock - ee_block + ext_pblock(ex);
240056055d3aSAmit Arora 	ex2 = ex;
240195c3889cSAneesh Kumar K.V 	orig_ex.ee_block = ex->ee_block;
240295c3889cSAneesh Kumar K.V 	orig_ex.ee_len   = cpu_to_le16(ee_len);
240395c3889cSAneesh Kumar K.V 	ext4_ext_store_pblock(&orig_ex, ext_pblock(ex));
240456055d3aSAmit Arora 
24059df5643aSAneesh Kumar K.V 	err = ext4_ext_get_access(handle, inode, path + depth);
24069df5643aSAneesh Kumar K.V 	if (err)
24079df5643aSAneesh Kumar K.V 		goto out;
24083977c965SAneesh Kumar K.V 	/* If extent has less than 2*EXT4_EXT_ZERO_LEN zerout directly */
24093977c965SAneesh Kumar K.V 	if (ee_len <= 2*EXT4_EXT_ZERO_LEN) {
24103977c965SAneesh Kumar K.V 		err =  ext4_ext_zeroout(inode, &orig_ex);
24113977c965SAneesh Kumar K.V 		if (err)
24123977c965SAneesh Kumar K.V 			goto fix_extent_len;
24133977c965SAneesh Kumar K.V 		/* update the extent length and mark as initialized */
24143977c965SAneesh Kumar K.V 		ex->ee_block = orig_ex.ee_block;
24153977c965SAneesh Kumar K.V 		ex->ee_len   = orig_ex.ee_len;
24163977c965SAneesh Kumar K.V 		ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
24173977c965SAneesh Kumar K.V 		ext4_ext_dirty(handle, inode, path + depth);
2418161e7b7cSAneesh Kumar K.V 		/* zeroed the full extent */
2419161e7b7cSAneesh Kumar K.V 		return allocated;
24203977c965SAneesh Kumar K.V 	}
24219df5643aSAneesh Kumar K.V 
242256055d3aSAmit Arora 	/* ex1: ee_block to iblock - 1 : uninitialized */
242356055d3aSAmit Arora 	if (iblock > ee_block) {
242456055d3aSAmit Arora 		ex1 = ex;
242556055d3aSAmit Arora 		ex1->ee_len = cpu_to_le16(iblock - ee_block);
242656055d3aSAmit Arora 		ext4_ext_mark_uninitialized(ex1);
242756055d3aSAmit Arora 		ex2 = &newex;
242856055d3aSAmit Arora 	}
242956055d3aSAmit Arora 	/*
243056055d3aSAmit Arora 	 * for sanity, update the length of the ex2 extent before
243156055d3aSAmit Arora 	 * we insert ex3, if ex1 is NULL. This is to avoid temporary
243256055d3aSAmit Arora 	 * overlap of blocks.
243356055d3aSAmit Arora 	 */
243456055d3aSAmit Arora 	if (!ex1 && allocated > max_blocks)
243556055d3aSAmit Arora 		ex2->ee_len = cpu_to_le16(max_blocks);
243656055d3aSAmit Arora 	/* ex3: to ee_block + ee_len : uninitialised */
243756055d3aSAmit Arora 	if (allocated > max_blocks) {
243856055d3aSAmit Arora 		unsigned int newdepth;
24393977c965SAneesh Kumar K.V 		/* If extent has less than EXT4_EXT_ZERO_LEN zerout directly */
24403977c965SAneesh Kumar K.V 		if (allocated <= EXT4_EXT_ZERO_LEN) {
2441d03856bdSAneesh Kumar K.V 			/*
2442d03856bdSAneesh Kumar K.V 			 * iblock == ee_block is handled by the zerouout
2443d03856bdSAneesh Kumar K.V 			 * at the beginning.
2444d03856bdSAneesh Kumar K.V 			 * Mark first half uninitialized.
24453977c965SAneesh Kumar K.V 			 * Mark second half initialized and zero out the
24463977c965SAneesh Kumar K.V 			 * initialized extent
24473977c965SAneesh Kumar K.V 			 */
24483977c965SAneesh Kumar K.V 			ex->ee_block = orig_ex.ee_block;
24493977c965SAneesh Kumar K.V 			ex->ee_len   = cpu_to_le16(ee_len - allocated);
24503977c965SAneesh Kumar K.V 			ext4_ext_mark_uninitialized(ex);
24513977c965SAneesh Kumar K.V 			ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
24523977c965SAneesh Kumar K.V 			ext4_ext_dirty(handle, inode, path + depth);
24533977c965SAneesh Kumar K.V 
24543977c965SAneesh Kumar K.V 			ex3 = &newex;
24553977c965SAneesh Kumar K.V 			ex3->ee_block = cpu_to_le32(iblock);
24563977c965SAneesh Kumar K.V 			ext4_ext_store_pblock(ex3, newblock);
24573977c965SAneesh Kumar K.V 			ex3->ee_len = cpu_to_le16(allocated);
24583977c965SAneesh Kumar K.V 			err = ext4_ext_insert_extent(handle, inode, path, ex3);
24593977c965SAneesh Kumar K.V 			if (err == -ENOSPC) {
24603977c965SAneesh Kumar K.V 				err =  ext4_ext_zeroout(inode, &orig_ex);
24613977c965SAneesh Kumar K.V 				if (err)
24623977c965SAneesh Kumar K.V 					goto fix_extent_len;
24633977c965SAneesh Kumar K.V 				ex->ee_block = orig_ex.ee_block;
24643977c965SAneesh Kumar K.V 				ex->ee_len   = orig_ex.ee_len;
24653977c965SAneesh Kumar K.V 				ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
24663977c965SAneesh Kumar K.V 				ext4_ext_dirty(handle, inode, path + depth);
2467d03856bdSAneesh Kumar K.V 				/* blocks available from iblock */
2468161e7b7cSAneesh Kumar K.V 				return allocated;
24693977c965SAneesh Kumar K.V 
24703977c965SAneesh Kumar K.V 			} else if (err)
24713977c965SAneesh Kumar K.V 				goto fix_extent_len;
24723977c965SAneesh Kumar K.V 
2473161e7b7cSAneesh Kumar K.V 			/*
2474161e7b7cSAneesh Kumar K.V 			 * We need to zero out the second half because
2475161e7b7cSAneesh Kumar K.V 			 * an fallocate request can update file size and
2476161e7b7cSAneesh Kumar K.V 			 * converting the second half to initialized extent
2477161e7b7cSAneesh Kumar K.V 			 * implies that we can leak some junk data to user
2478161e7b7cSAneesh Kumar K.V 			 * space.
2479161e7b7cSAneesh Kumar K.V 			 */
2480161e7b7cSAneesh Kumar K.V 			err =  ext4_ext_zeroout(inode, ex3);
2481161e7b7cSAneesh Kumar K.V 			if (err) {
2482161e7b7cSAneesh Kumar K.V 				/*
2483161e7b7cSAneesh Kumar K.V 				 * We should actually mark the
2484161e7b7cSAneesh Kumar K.V 				 * second half as uninit and return error
2485161e7b7cSAneesh Kumar K.V 				 * Insert would have changed the extent
2486161e7b7cSAneesh Kumar K.V 				 */
2487161e7b7cSAneesh Kumar K.V 				depth = ext_depth(inode);
2488161e7b7cSAneesh Kumar K.V 				ext4_ext_drop_refs(path);
2489161e7b7cSAneesh Kumar K.V 				path = ext4_ext_find_extent(inode,
2490161e7b7cSAneesh Kumar K.V 								iblock, path);
2491161e7b7cSAneesh Kumar K.V 				if (IS_ERR(path)) {
2492161e7b7cSAneesh Kumar K.V 					err = PTR_ERR(path);
2493161e7b7cSAneesh Kumar K.V 					return err;
2494161e7b7cSAneesh Kumar K.V 				}
2495d03856bdSAneesh Kumar K.V 				/* get the second half extent details */
2496161e7b7cSAneesh Kumar K.V 				ex = path[depth].p_ext;
2497161e7b7cSAneesh Kumar K.V 				err = ext4_ext_get_access(handle, inode,
2498161e7b7cSAneesh Kumar K.V 								path + depth);
2499161e7b7cSAneesh Kumar K.V 				if (err)
2500161e7b7cSAneesh Kumar K.V 					return err;
2501161e7b7cSAneesh Kumar K.V 				ext4_ext_mark_uninitialized(ex);
2502161e7b7cSAneesh Kumar K.V 				ext4_ext_dirty(handle, inode, path + depth);
2503161e7b7cSAneesh Kumar K.V 				return err;
2504161e7b7cSAneesh Kumar K.V 			}
2505161e7b7cSAneesh Kumar K.V 
2506161e7b7cSAneesh Kumar K.V 			/* zeroed the second half */
25073977c965SAneesh Kumar K.V 			return allocated;
25083977c965SAneesh Kumar K.V 		}
250956055d3aSAmit Arora 		ex3 = &newex;
251056055d3aSAmit Arora 		ex3->ee_block = cpu_to_le32(iblock + max_blocks);
251156055d3aSAmit Arora 		ext4_ext_store_pblock(ex3, newblock + max_blocks);
251256055d3aSAmit Arora 		ex3->ee_len = cpu_to_le16(allocated - max_blocks);
251356055d3aSAmit Arora 		ext4_ext_mark_uninitialized(ex3);
251456055d3aSAmit Arora 		err = ext4_ext_insert_extent(handle, inode, path, ex3);
2515093a088bSAneesh Kumar K.V 		if (err == -ENOSPC) {
2516093a088bSAneesh Kumar K.V 			err =  ext4_ext_zeroout(inode, &orig_ex);
2517093a088bSAneesh Kumar K.V 			if (err)
2518093a088bSAneesh Kumar K.V 				goto fix_extent_len;
2519093a088bSAneesh Kumar K.V 			/* update the extent length and mark as initialized */
252095c3889cSAneesh Kumar K.V 			ex->ee_block = orig_ex.ee_block;
252195c3889cSAneesh Kumar K.V 			ex->ee_len   = orig_ex.ee_len;
252295c3889cSAneesh Kumar K.V 			ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
252395c3889cSAneesh Kumar K.V 			ext4_ext_dirty(handle, inode, path + depth);
2524161e7b7cSAneesh Kumar K.V 			/* zeroed the full extent */
2525d03856bdSAneesh Kumar K.V 			/* blocks available from iblock */
2526161e7b7cSAneesh Kumar K.V 			return allocated;
2527093a088bSAneesh Kumar K.V 
2528093a088bSAneesh Kumar K.V 		} else if (err)
2529093a088bSAneesh Kumar K.V 			goto fix_extent_len;
253056055d3aSAmit Arora 		/*
253156055d3aSAmit Arora 		 * The depth, and hence eh & ex might change
253256055d3aSAmit Arora 		 * as part of the insert above.
253356055d3aSAmit Arora 		 */
253456055d3aSAmit Arora 		newdepth = ext_depth(inode);
253595c3889cSAneesh Kumar K.V 		/*
253695c3889cSAneesh Kumar K.V 		 * update the extent length after successfull insert of the
253795c3889cSAneesh Kumar K.V 		 * split extent
253895c3889cSAneesh Kumar K.V 		 */
253995c3889cSAneesh Kumar K.V 		orig_ex.ee_len = cpu_to_le16(ee_len -
254095c3889cSAneesh Kumar K.V 						ext4_ext_get_actual_len(ex3));
254156055d3aSAmit Arora 		depth = newdepth;
2542b35905c1SAneesh Kumar K.V 		ext4_ext_drop_refs(path);
2543b35905c1SAneesh Kumar K.V 		path = ext4_ext_find_extent(inode, iblock, path);
254456055d3aSAmit Arora 		if (IS_ERR(path)) {
254556055d3aSAmit Arora 			err = PTR_ERR(path);
254656055d3aSAmit Arora 			goto out;
254756055d3aSAmit Arora 		}
254856055d3aSAmit Arora 		eh = path[depth].p_hdr;
254956055d3aSAmit Arora 		ex = path[depth].p_ext;
255056055d3aSAmit Arora 		if (ex2 != &newex)
255156055d3aSAmit Arora 			ex2 = ex;
25529df5643aSAneesh Kumar K.V 
25539df5643aSAneesh Kumar K.V 		err = ext4_ext_get_access(handle, inode, path + depth);
25549df5643aSAneesh Kumar K.V 		if (err)
25559df5643aSAneesh Kumar K.V 			goto out;
2556d03856bdSAneesh Kumar K.V 
255756055d3aSAmit Arora 		allocated = max_blocks;
25583977c965SAneesh Kumar K.V 
25593977c965SAneesh Kumar K.V 		/* If extent has less than EXT4_EXT_ZERO_LEN and we are trying
25603977c965SAneesh Kumar K.V 		 * to insert a extent in the middle zerout directly
25613977c965SAneesh Kumar K.V 		 * otherwise give the extent a chance to merge to left
25623977c965SAneesh Kumar K.V 		 */
25633977c965SAneesh Kumar K.V 		if (le16_to_cpu(orig_ex.ee_len) <= EXT4_EXT_ZERO_LEN &&
25643977c965SAneesh Kumar K.V 							iblock != ee_block) {
25653977c965SAneesh Kumar K.V 			err =  ext4_ext_zeroout(inode, &orig_ex);
25663977c965SAneesh Kumar K.V 			if (err)
25673977c965SAneesh Kumar K.V 				goto fix_extent_len;
25683977c965SAneesh Kumar K.V 			/* update the extent length and mark as initialized */
25693977c965SAneesh Kumar K.V 			ex->ee_block = orig_ex.ee_block;
25703977c965SAneesh Kumar K.V 			ex->ee_len   = orig_ex.ee_len;
25713977c965SAneesh Kumar K.V 			ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
25723977c965SAneesh Kumar K.V 			ext4_ext_dirty(handle, inode, path + depth);
2573161e7b7cSAneesh Kumar K.V 			/* zero out the first half */
2574d03856bdSAneesh Kumar K.V 			/* blocks available from iblock */
2575161e7b7cSAneesh Kumar K.V 			return allocated;
25763977c965SAneesh Kumar K.V 		}
257756055d3aSAmit Arora 	}
257856055d3aSAmit Arora 	/*
257956055d3aSAmit Arora 	 * If there was a change of depth as part of the
258056055d3aSAmit Arora 	 * insertion of ex3 above, we need to update the length
258156055d3aSAmit Arora 	 * of the ex1 extent again here
258256055d3aSAmit Arora 	 */
258356055d3aSAmit Arora 	if (ex1 && ex1 != ex) {
258456055d3aSAmit Arora 		ex1 = ex;
258556055d3aSAmit Arora 		ex1->ee_len = cpu_to_le16(iblock - ee_block);
258656055d3aSAmit Arora 		ext4_ext_mark_uninitialized(ex1);
258756055d3aSAmit Arora 		ex2 = &newex;
258856055d3aSAmit Arora 	}
258956055d3aSAmit Arora 	/* ex2: iblock to iblock + maxblocks-1 : initialised */
259056055d3aSAmit Arora 	ex2->ee_block = cpu_to_le32(iblock);
259156055d3aSAmit Arora 	ext4_ext_store_pblock(ex2, newblock);
259256055d3aSAmit Arora 	ex2->ee_len = cpu_to_le16(allocated);
259356055d3aSAmit Arora 	if (ex2 != ex)
259456055d3aSAmit Arora 		goto insert;
259556055d3aSAmit Arora 	/*
259656055d3aSAmit Arora 	 * New (initialized) extent starts from the first block
259756055d3aSAmit Arora 	 * in the current extent. i.e., ex2 == ex
259856055d3aSAmit Arora 	 * We have to see if it can be merged with the extent
259956055d3aSAmit Arora 	 * on the left.
260056055d3aSAmit Arora 	 */
260156055d3aSAmit Arora 	if (ex2 > EXT_FIRST_EXTENT(eh)) {
260256055d3aSAmit Arora 		/*
260356055d3aSAmit Arora 		 * To merge left, pass "ex2 - 1" to try_to_merge(),
260456055d3aSAmit Arora 		 * since it merges towards right _only_.
260556055d3aSAmit Arora 		 */
260656055d3aSAmit Arora 		ret = ext4_ext_try_to_merge(inode, path, ex2 - 1);
260756055d3aSAmit Arora 		if (ret) {
260856055d3aSAmit Arora 			err = ext4_ext_correct_indexes(handle, inode, path);
260956055d3aSAmit Arora 			if (err)
261056055d3aSAmit Arora 				goto out;
261156055d3aSAmit Arora 			depth = ext_depth(inode);
261256055d3aSAmit Arora 			ex2--;
261356055d3aSAmit Arora 		}
261456055d3aSAmit Arora 	}
261556055d3aSAmit Arora 	/*
261656055d3aSAmit Arora 	 * Try to Merge towards right. This might be required
261756055d3aSAmit Arora 	 * only when the whole extent is being written to.
261856055d3aSAmit Arora 	 * i.e. ex2 == ex and ex3 == NULL.
261956055d3aSAmit Arora 	 */
262056055d3aSAmit Arora 	if (!ex3) {
262156055d3aSAmit Arora 		ret = ext4_ext_try_to_merge(inode, path, ex2);
262256055d3aSAmit Arora 		if (ret) {
262356055d3aSAmit Arora 			err = ext4_ext_correct_indexes(handle, inode, path);
262456055d3aSAmit Arora 			if (err)
262556055d3aSAmit Arora 				goto out;
262656055d3aSAmit Arora 		}
262756055d3aSAmit Arora 	}
262856055d3aSAmit Arora 	/* Mark modified extent as dirty */
262956055d3aSAmit Arora 	err = ext4_ext_dirty(handle, inode, path + depth);
263056055d3aSAmit Arora 	goto out;
263156055d3aSAmit Arora insert:
263256055d3aSAmit Arora 	err = ext4_ext_insert_extent(handle, inode, path, &newex);
2633093a088bSAneesh Kumar K.V 	if (err == -ENOSPC) {
2634093a088bSAneesh Kumar K.V 		err =  ext4_ext_zeroout(inode, &orig_ex);
2635093a088bSAneesh Kumar K.V 		if (err)
2636093a088bSAneesh Kumar K.V 			goto fix_extent_len;
2637093a088bSAneesh Kumar K.V 		/* update the extent length and mark as initialized */
2638093a088bSAneesh Kumar K.V 		ex->ee_block = orig_ex.ee_block;
2639093a088bSAneesh Kumar K.V 		ex->ee_len   = orig_ex.ee_len;
2640093a088bSAneesh Kumar K.V 		ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
2641093a088bSAneesh Kumar K.V 		ext4_ext_dirty(handle, inode, path + depth);
2642161e7b7cSAneesh Kumar K.V 		/* zero out the first half */
2643161e7b7cSAneesh Kumar K.V 		return allocated;
2644093a088bSAneesh Kumar K.V 	} else if (err)
2645093a088bSAneesh Kumar K.V 		goto fix_extent_len;
2646093a088bSAneesh Kumar K.V out:
2647093a088bSAneesh Kumar K.V 	return err ? err : allocated;
2648093a088bSAneesh Kumar K.V 
2649093a088bSAneesh Kumar K.V fix_extent_len:
265095c3889cSAneesh Kumar K.V 	ex->ee_block = orig_ex.ee_block;
265195c3889cSAneesh Kumar K.V 	ex->ee_len   = orig_ex.ee_len;
265295c3889cSAneesh Kumar K.V 	ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
265395c3889cSAneesh Kumar K.V 	ext4_ext_mark_uninitialized(ex);
265495c3889cSAneesh Kumar K.V 	ext4_ext_dirty(handle, inode, path + depth);
2655093a088bSAneesh Kumar K.V 	return err;
265656055d3aSAmit Arora }
265756055d3aSAmit Arora 
2658c278bfecSAneesh Kumar K.V /*
2659f5ab0d1fSMingming Cao  * Block allocation/map/preallocation routine for extents based files
2660f5ab0d1fSMingming Cao  *
2661f5ab0d1fSMingming Cao  *
2662c278bfecSAneesh Kumar K.V  * Need to be called with
26630e855ac8SAneesh Kumar K.V  * down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system block
26640e855ac8SAneesh Kumar K.V  * (ie, create is zero). Otherwise down_write(&EXT4_I(inode)->i_data_sem)
2665f5ab0d1fSMingming Cao  *
2666f5ab0d1fSMingming Cao  * return > 0, number of of blocks already mapped/allocated
2667f5ab0d1fSMingming Cao  *          if create == 0 and these are pre-allocated blocks
2668f5ab0d1fSMingming Cao  *          	buffer head is unmapped
2669f5ab0d1fSMingming Cao  *          otherwise blocks are mapped
2670f5ab0d1fSMingming Cao  *
2671f5ab0d1fSMingming Cao  * return = 0, if plain look up failed (blocks have not been allocated)
2672f5ab0d1fSMingming Cao  *          buffer head is unmapped
2673f5ab0d1fSMingming Cao  *
2674f5ab0d1fSMingming Cao  * return < 0, error case.
2675c278bfecSAneesh Kumar K.V  */
2676f65e6fbaSAlex Tomas int ext4_ext_get_blocks(handle_t *handle, struct inode *inode,
2677725d26d3SAneesh Kumar K.V 			ext4_lblk_t iblock,
2678*498e5f24STheodore Ts'o 			unsigned int max_blocks, struct buffer_head *bh_result,
2679a86c6181SAlex Tomas 			int create, int extend_disksize)
2680a86c6181SAlex Tomas {
2681a86c6181SAlex Tomas 	struct ext4_ext_path *path = NULL;
268256055d3aSAmit Arora 	struct ext4_extent_header *eh;
2683a86c6181SAlex Tomas 	struct ext4_extent newex, *ex;
2684*498e5f24STheodore Ts'o 	ext4_fsblk_t newblock;
2685*498e5f24STheodore Ts'o 	int err = 0, depth, ret, cache_type;
2686*498e5f24STheodore Ts'o 	unsigned int allocated = 0;
2687c9de560dSAlex Tomas 	struct ext4_allocation_request ar;
268861628a3fSMingming Cao 	loff_t disksize;
2689a86c6181SAlex Tomas 
2690a86c6181SAlex Tomas 	__clear_bit(BH_New, &bh_result->b_state);
2691*498e5f24STheodore Ts'o 	ext_debug("blocks %u/%u requested for inode %u\n",
2692bba90743SEric Sandeen 			iblock, max_blocks, inode->i_ino);
2693a86c6181SAlex Tomas 
2694a86c6181SAlex Tomas 	/* check in cache */
2695*498e5f24STheodore Ts'o 	cache_type = ext4_ext_in_cache(inode, iblock, &newex);
2696*498e5f24STheodore Ts'o 	if (cache_type) {
2697*498e5f24STheodore Ts'o 		if (cache_type == EXT4_EXT_CACHE_GAP) {
2698a86c6181SAlex Tomas 			if (!create) {
269956055d3aSAmit Arora 				/*
270056055d3aSAmit Arora 				 * block isn't allocated yet and
270156055d3aSAmit Arora 				 * user doesn't want to allocate it
270256055d3aSAmit Arora 				 */
2703a86c6181SAlex Tomas 				goto out2;
2704a86c6181SAlex Tomas 			}
2705a86c6181SAlex Tomas 			/* we should allocate requested block */
2706*498e5f24STheodore Ts'o 		} else if (cache_type == EXT4_EXT_CACHE_EXTENT) {
2707a86c6181SAlex Tomas 			/* block is already allocated */
2708a86c6181SAlex Tomas 			newblock = iblock
2709a86c6181SAlex Tomas 				   - le32_to_cpu(newex.ee_block)
2710f65e6fbaSAlex Tomas 				   + ext_pblock(&newex);
2711d0d856e8SRandy Dunlap 			/* number of remaining blocks in the extent */
2712b939e376SAneesh Kumar K.V 			allocated = ext4_ext_get_actual_len(&newex) -
2713a86c6181SAlex Tomas 					(iblock - le32_to_cpu(newex.ee_block));
2714a86c6181SAlex Tomas 			goto out;
2715a86c6181SAlex Tomas 		} else {
2716a86c6181SAlex Tomas 			BUG();
2717a86c6181SAlex Tomas 		}
2718a86c6181SAlex Tomas 	}
2719a86c6181SAlex Tomas 
2720a86c6181SAlex Tomas 	/* find extent for this block */
2721a86c6181SAlex Tomas 	path = ext4_ext_find_extent(inode, iblock, NULL);
2722a86c6181SAlex Tomas 	if (IS_ERR(path)) {
2723a86c6181SAlex Tomas 		err = PTR_ERR(path);
2724a86c6181SAlex Tomas 		path = NULL;
2725a86c6181SAlex Tomas 		goto out2;
2726a86c6181SAlex Tomas 	}
2727a86c6181SAlex Tomas 
2728a86c6181SAlex Tomas 	depth = ext_depth(inode);
2729a86c6181SAlex Tomas 
2730a86c6181SAlex Tomas 	/*
2731d0d856e8SRandy Dunlap 	 * consistent leaf must not be empty;
2732d0d856e8SRandy Dunlap 	 * this situation is possible, though, _during_ tree modification;
2733a86c6181SAlex Tomas 	 * this is why assert can't be put in ext4_ext_find_extent()
2734a86c6181SAlex Tomas 	 */
2735a86c6181SAlex Tomas 	BUG_ON(path[depth].p_ext == NULL && depth != 0);
273656055d3aSAmit Arora 	eh = path[depth].p_hdr;
2737a86c6181SAlex Tomas 
27387e028976SAvantika Mathur 	ex = path[depth].p_ext;
27397e028976SAvantika Mathur 	if (ex) {
2740725d26d3SAneesh Kumar K.V 		ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
2741f65e6fbaSAlex Tomas 		ext4_fsblk_t ee_start = ext_pblock(ex);
2742a2df2a63SAmit Arora 		unsigned short ee_len;
2743471d4011SSuparna Bhattacharya 
2744471d4011SSuparna Bhattacharya 		/*
2745471d4011SSuparna Bhattacharya 		 * Uninitialized extents are treated as holes, except that
274656055d3aSAmit Arora 		 * we split out initialized portions during a write.
2747471d4011SSuparna Bhattacharya 		 */
2748a2df2a63SAmit Arora 		ee_len = ext4_ext_get_actual_len(ex);
2749d0d856e8SRandy Dunlap 		/* if found extent covers block, simply return it */
2750a86c6181SAlex Tomas 		if (iblock >= ee_block && iblock < ee_block + ee_len) {
2751a86c6181SAlex Tomas 			newblock = iblock - ee_block + ee_start;
2752d0d856e8SRandy Dunlap 			/* number of remaining blocks in the extent */
2753a86c6181SAlex Tomas 			allocated = ee_len - (iblock - ee_block);
2754bba90743SEric Sandeen 			ext_debug("%u fit into %lu:%d -> %llu\n", iblock,
2755a86c6181SAlex Tomas 					ee_block, ee_len, newblock);
275656055d3aSAmit Arora 
2757a2df2a63SAmit Arora 			/* Do not put uninitialized extent in the cache */
275856055d3aSAmit Arora 			if (!ext4_ext_is_uninitialized(ex)) {
2759a2df2a63SAmit Arora 				ext4_ext_put_in_cache(inode, ee_block,
2760a2df2a63SAmit Arora 							ee_len, ee_start,
2761a2df2a63SAmit Arora 							EXT4_EXT_CACHE_EXTENT);
2762a86c6181SAlex Tomas 				goto out;
2763a86c6181SAlex Tomas 			}
276456055d3aSAmit Arora 			if (create == EXT4_CREATE_UNINITIALIZED_EXT)
276556055d3aSAmit Arora 				goto out;
2766e067ba00SAneesh Kumar K.V 			if (!create) {
2767e067ba00SAneesh Kumar K.V 				/*
2768e067ba00SAneesh Kumar K.V 				 * We have blocks reserved already.  We
2769e067ba00SAneesh Kumar K.V 				 * return allocated blocks so that delalloc
2770e067ba00SAneesh Kumar K.V 				 * won't do block reservation for us.  But
2771e067ba00SAneesh Kumar K.V 				 * the buffer head will be unmapped so that
2772e067ba00SAneesh Kumar K.V 				 * a read from the block returns 0s.
2773e067ba00SAneesh Kumar K.V 				 */
2774e067ba00SAneesh Kumar K.V 				if (allocated > max_blocks)
2775e067ba00SAneesh Kumar K.V 					allocated = max_blocks;
2776953e622bSEric Sandeen 				set_buffer_unwritten(bh_result);
277756055d3aSAmit Arora 				goto out2;
2778e067ba00SAneesh Kumar K.V 			}
277956055d3aSAmit Arora 
278056055d3aSAmit Arora 			ret = ext4_ext_convert_to_initialized(handle, inode,
278156055d3aSAmit Arora 								path, iblock,
278256055d3aSAmit Arora 								max_blocks);
2783dbf9d7daSDmitry Monakhov 			if (ret <= 0) {
2784dbf9d7daSDmitry Monakhov 				err = ret;
278556055d3aSAmit Arora 				goto out2;
2786dbf9d7daSDmitry Monakhov 			} else
278756055d3aSAmit Arora 				allocated = ret;
278856055d3aSAmit Arora 			goto outnew;
278956055d3aSAmit Arora 		}
2790a86c6181SAlex Tomas 	}
2791a86c6181SAlex Tomas 
2792a86c6181SAlex Tomas 	/*
2793d0d856e8SRandy Dunlap 	 * requested block isn't allocated yet;
2794a86c6181SAlex Tomas 	 * we couldn't try to create block if create flag is zero
2795a86c6181SAlex Tomas 	 */
2796a86c6181SAlex Tomas 	if (!create) {
279756055d3aSAmit Arora 		/*
279856055d3aSAmit Arora 		 * put just found gap into cache to speed up
279956055d3aSAmit Arora 		 * subsequent requests
280056055d3aSAmit Arora 		 */
2801a86c6181SAlex Tomas 		ext4_ext_put_gap_in_cache(inode, path, iblock);
2802a86c6181SAlex Tomas 		goto out2;
2803a86c6181SAlex Tomas 	}
2804a86c6181SAlex Tomas 	/*
2805c2ea3fdeSTheodore Ts'o 	 * Okay, we need to do block allocation.
2806a86c6181SAlex Tomas 	 */
2807a86c6181SAlex Tomas 
2808c9de560dSAlex Tomas 	/* find neighbour allocated blocks */
2809c9de560dSAlex Tomas 	ar.lleft = iblock;
2810c9de560dSAlex Tomas 	err = ext4_ext_search_left(inode, path, &ar.lleft, &ar.pleft);
2811c9de560dSAlex Tomas 	if (err)
2812c9de560dSAlex Tomas 		goto out2;
2813c9de560dSAlex Tomas 	ar.lright = iblock;
2814c9de560dSAlex Tomas 	err = ext4_ext_search_right(inode, path, &ar.lright, &ar.pright);
2815c9de560dSAlex Tomas 	if (err)
2816c9de560dSAlex Tomas 		goto out2;
281725d14f98SAmit Arora 
2818749269faSAmit Arora 	/*
2819749269faSAmit Arora 	 * See if request is beyond maximum number of blocks we can have in
2820749269faSAmit Arora 	 * a single extent. For an initialized extent this limit is
2821749269faSAmit Arora 	 * EXT_INIT_MAX_LEN and for an uninitialized extent this limit is
2822749269faSAmit Arora 	 * EXT_UNINIT_MAX_LEN.
2823749269faSAmit Arora 	 */
2824749269faSAmit Arora 	if (max_blocks > EXT_INIT_MAX_LEN &&
2825749269faSAmit Arora 	    create != EXT4_CREATE_UNINITIALIZED_EXT)
2826749269faSAmit Arora 		max_blocks = EXT_INIT_MAX_LEN;
2827749269faSAmit Arora 	else if (max_blocks > EXT_UNINIT_MAX_LEN &&
2828749269faSAmit Arora 		 create == EXT4_CREATE_UNINITIALIZED_EXT)
2829749269faSAmit Arora 		max_blocks = EXT_UNINIT_MAX_LEN;
2830749269faSAmit Arora 
283125d14f98SAmit Arora 	/* Check if we can really insert (iblock)::(iblock+max_blocks) extent */
283225d14f98SAmit Arora 	newex.ee_block = cpu_to_le32(iblock);
283325d14f98SAmit Arora 	newex.ee_len = cpu_to_le16(max_blocks);
283425d14f98SAmit Arora 	err = ext4_ext_check_overlap(inode, &newex, path);
283525d14f98SAmit Arora 	if (err)
2836b939e376SAneesh Kumar K.V 		allocated = ext4_ext_get_actual_len(&newex);
283725d14f98SAmit Arora 	else
2838a86c6181SAlex Tomas 		allocated = max_blocks;
2839c9de560dSAlex Tomas 
2840c9de560dSAlex Tomas 	/* allocate new block */
2841c9de560dSAlex Tomas 	ar.inode = inode;
2842c9de560dSAlex Tomas 	ar.goal = ext4_ext_find_goal(inode, path, iblock);
2843c9de560dSAlex Tomas 	ar.logical = iblock;
2844c9de560dSAlex Tomas 	ar.len = allocated;
2845c9de560dSAlex Tomas 	if (S_ISREG(inode->i_mode))
2846c9de560dSAlex Tomas 		ar.flags = EXT4_MB_HINT_DATA;
2847c9de560dSAlex Tomas 	else
2848c9de560dSAlex Tomas 		/* disable in-core preallocation for non-regular files */
2849c9de560dSAlex Tomas 		ar.flags = 0;
2850c9de560dSAlex Tomas 	newblock = ext4_mb_new_blocks(handle, &ar, &err);
2851a86c6181SAlex Tomas 	if (!newblock)
2852a86c6181SAlex Tomas 		goto out2;
28532ae02107SMingming Cao 	ext_debug("allocate new block: goal %llu, found %llu/%lu\n",
2854*498e5f24STheodore Ts'o 		  ar.goal, newblock, allocated);
2855a86c6181SAlex Tomas 
2856a86c6181SAlex Tomas 	/* try to insert new extent into found leaf and return */
2857f65e6fbaSAlex Tomas 	ext4_ext_store_pblock(&newex, newblock);
2858c9de560dSAlex Tomas 	newex.ee_len = cpu_to_le16(ar.len);
2859a2df2a63SAmit Arora 	if (create == EXT4_CREATE_UNINITIALIZED_EXT)  /* Mark uninitialized */
2860a2df2a63SAmit Arora 		ext4_ext_mark_uninitialized(&newex);
2861a86c6181SAlex Tomas 	err = ext4_ext_insert_extent(handle, inode, path, &newex);
2862315054f0SAlex Tomas 	if (err) {
2863315054f0SAlex Tomas 		/* free data blocks we just allocated */
2864c9de560dSAlex Tomas 		/* not a good idea to call discard here directly,
2865c9de560dSAlex Tomas 		 * but otherwise we'd need to call it every free() */
2866c2ea3fdeSTheodore Ts'o 		ext4_discard_preallocations(inode);
2867315054f0SAlex Tomas 		ext4_free_blocks(handle, inode, ext_pblock(&newex),
2868b939e376SAneesh Kumar K.V 					ext4_ext_get_actual_len(&newex), 0);
2869a86c6181SAlex Tomas 		goto out2;
2870315054f0SAlex Tomas 	}
2871a86c6181SAlex Tomas 
2872a86c6181SAlex Tomas 	/* previous routine could use block we allocated */
2873f65e6fbaSAlex Tomas 	newblock = ext_pblock(&newex);
2874b939e376SAneesh Kumar K.V 	allocated = ext4_ext_get_actual_len(&newex);
287556055d3aSAmit Arora outnew:
287661628a3fSMingming Cao 	if (extend_disksize) {
287761628a3fSMingming Cao 		disksize = ((loff_t) iblock + ar.len) << inode->i_blkbits;
287861628a3fSMingming Cao 		if (disksize > i_size_read(inode))
287961628a3fSMingming Cao 			disksize = i_size_read(inode);
288061628a3fSMingming Cao 		if (disksize > EXT4_I(inode)->i_disksize)
288161628a3fSMingming Cao 			EXT4_I(inode)->i_disksize = disksize;
288261628a3fSMingming Cao 	}
2883a379cd1dSAneesh Kumar K.V 
2884953e622bSEric Sandeen 	set_buffer_new(bh_result);
2885a86c6181SAlex Tomas 
2886a2df2a63SAmit Arora 	/* Cache only when it is _not_ an uninitialized extent */
2887a2df2a63SAmit Arora 	if (create != EXT4_CREATE_UNINITIALIZED_EXT)
2888a86c6181SAlex Tomas 		ext4_ext_put_in_cache(inode, iblock, allocated, newblock,
2889a86c6181SAlex Tomas 						EXT4_EXT_CACHE_EXTENT);
2890a86c6181SAlex Tomas out:
2891a86c6181SAlex Tomas 	if (allocated > max_blocks)
2892a86c6181SAlex Tomas 		allocated = max_blocks;
2893a86c6181SAlex Tomas 	ext4_ext_show_leaf(inode, path);
2894953e622bSEric Sandeen 	set_buffer_mapped(bh_result);
2895a86c6181SAlex Tomas 	bh_result->b_bdev = inode->i_sb->s_bdev;
2896a86c6181SAlex Tomas 	bh_result->b_blocknr = newblock;
2897a86c6181SAlex Tomas out2:
2898a86c6181SAlex Tomas 	if (path) {
2899a86c6181SAlex Tomas 		ext4_ext_drop_refs(path);
2900a86c6181SAlex Tomas 		kfree(path);
2901a86c6181SAlex Tomas 	}
2902a86c6181SAlex Tomas 	return err ? err : allocated;
2903a86c6181SAlex Tomas }
2904a86c6181SAlex Tomas 
2905cf108bcaSJan Kara void ext4_ext_truncate(struct inode *inode)
2906a86c6181SAlex Tomas {
2907a86c6181SAlex Tomas 	struct address_space *mapping = inode->i_mapping;
2908a86c6181SAlex Tomas 	struct super_block *sb = inode->i_sb;
2909725d26d3SAneesh Kumar K.V 	ext4_lblk_t last_block;
2910a86c6181SAlex Tomas 	handle_t *handle;
2911a86c6181SAlex Tomas 	int err = 0;
2912a86c6181SAlex Tomas 
2913a86c6181SAlex Tomas 	/*
2914a86c6181SAlex Tomas 	 * probably first extent we're gonna free will be last in block
2915a86c6181SAlex Tomas 	 */
2916f3bd1f3fSMingming Cao 	err = ext4_writepage_trans_blocks(inode);
2917a86c6181SAlex Tomas 	handle = ext4_journal_start(inode, err);
2918cf108bcaSJan Kara 	if (IS_ERR(handle))
2919a86c6181SAlex Tomas 		return;
2920a86c6181SAlex Tomas 
2921cf108bcaSJan Kara 	if (inode->i_size & (sb->s_blocksize - 1))
2922cf108bcaSJan Kara 		ext4_block_truncate_page(handle, mapping, inode->i_size);
2923a86c6181SAlex Tomas 
29249ddfc3dcSJan Kara 	if (ext4_orphan_add(handle, inode))
29259ddfc3dcSJan Kara 		goto out_stop;
29269ddfc3dcSJan Kara 
29270e855ac8SAneesh Kumar K.V 	down_write(&EXT4_I(inode)->i_data_sem);
2928a86c6181SAlex Tomas 	ext4_ext_invalidate_cache(inode);
2929a86c6181SAlex Tomas 
2930c2ea3fdeSTheodore Ts'o 	ext4_discard_preallocations(inode);
2931c9de560dSAlex Tomas 
2932a86c6181SAlex Tomas 	/*
2933d0d856e8SRandy Dunlap 	 * TODO: optimization is possible here.
2934d0d856e8SRandy Dunlap 	 * Probably we need not scan at all,
2935d0d856e8SRandy Dunlap 	 * because page truncation is enough.
2936a86c6181SAlex Tomas 	 */
2937a86c6181SAlex Tomas 
2938a86c6181SAlex Tomas 	/* we have to know where to truncate from in crash case */
2939a86c6181SAlex Tomas 	EXT4_I(inode)->i_disksize = inode->i_size;
2940a86c6181SAlex Tomas 	ext4_mark_inode_dirty(handle, inode);
2941a86c6181SAlex Tomas 
2942a86c6181SAlex Tomas 	last_block = (inode->i_size + sb->s_blocksize - 1)
2943a86c6181SAlex Tomas 			>> EXT4_BLOCK_SIZE_BITS(sb);
2944a86c6181SAlex Tomas 	err = ext4_ext_remove_space(inode, last_block);
2945a86c6181SAlex Tomas 
2946a86c6181SAlex Tomas 	/* In a multi-transaction truncate, we only make the final
294756055d3aSAmit Arora 	 * transaction synchronous.
294856055d3aSAmit Arora 	 */
2949a86c6181SAlex Tomas 	if (IS_SYNC(inode))
29500390131bSFrank Mayhar 		ext4_handle_sync(handle);
2951a86c6181SAlex Tomas 
2952a86c6181SAlex Tomas out_stop:
29539ddfc3dcSJan Kara 	up_write(&EXT4_I(inode)->i_data_sem);
2954a86c6181SAlex Tomas 	/*
2955d0d856e8SRandy Dunlap 	 * If this was a simple ftruncate() and the file will remain alive,
2956a86c6181SAlex Tomas 	 * then we need to clear up the orphan record which we created above.
2957a86c6181SAlex Tomas 	 * However, if this was a real unlink then we were called by
2958a86c6181SAlex Tomas 	 * ext4_delete_inode(), and we allow that function to clean up the
2959a86c6181SAlex Tomas 	 * orphan info for us.
2960a86c6181SAlex Tomas 	 */
2961a86c6181SAlex Tomas 	if (inode->i_nlink)
2962a86c6181SAlex Tomas 		ext4_orphan_del(handle, inode);
2963a86c6181SAlex Tomas 
2964ef737728SSolofo Ramangalahy 	inode->i_mtime = inode->i_ctime = ext4_current_time(inode);
2965ef737728SSolofo Ramangalahy 	ext4_mark_inode_dirty(handle, inode);
2966a86c6181SAlex Tomas 	ext4_journal_stop(handle);
2967a86c6181SAlex Tomas }
2968a86c6181SAlex Tomas 
2969fd28784aSAneesh Kumar K.V static void ext4_falloc_update_inode(struct inode *inode,
2970fd28784aSAneesh Kumar K.V 				int mode, loff_t new_size, int update_ctime)
2971fd28784aSAneesh Kumar K.V {
2972fd28784aSAneesh Kumar K.V 	struct timespec now;
2973fd28784aSAneesh Kumar K.V 
2974fd28784aSAneesh Kumar K.V 	if (update_ctime) {
2975fd28784aSAneesh Kumar K.V 		now = current_fs_time(inode->i_sb);
2976fd28784aSAneesh Kumar K.V 		if (!timespec_equal(&inode->i_ctime, &now))
2977fd28784aSAneesh Kumar K.V 			inode->i_ctime = now;
2978fd28784aSAneesh Kumar K.V 	}
2979fd28784aSAneesh Kumar K.V 	/*
2980fd28784aSAneesh Kumar K.V 	 * Update only when preallocation was requested beyond
2981fd28784aSAneesh Kumar K.V 	 * the file size.
2982fd28784aSAneesh Kumar K.V 	 */
2983cf17fea6SAneesh Kumar K.V 	if (!(mode & FALLOC_FL_KEEP_SIZE)) {
2984cf17fea6SAneesh Kumar K.V 		if (new_size > i_size_read(inode))
2985fd28784aSAneesh Kumar K.V 			i_size_write(inode, new_size);
2986cf17fea6SAneesh Kumar K.V 		if (new_size > EXT4_I(inode)->i_disksize)
2987cf17fea6SAneesh Kumar K.V 			ext4_update_i_disksize(inode, new_size);
2988fd28784aSAneesh Kumar K.V 	}
2989fd28784aSAneesh Kumar K.V 
2990fd28784aSAneesh Kumar K.V }
2991fd28784aSAneesh Kumar K.V 
2992a2df2a63SAmit Arora /*
2993a2df2a63SAmit Arora  * preallocate space for a file. This implements ext4's fallocate inode
2994a2df2a63SAmit Arora  * operation, which gets called from sys_fallocate system call.
2995a2df2a63SAmit Arora  * For block-mapped files, posix_fallocate should fall back to the method
2996a2df2a63SAmit Arora  * of writing zeroes to the required new blocks (the same behavior which is
2997a2df2a63SAmit Arora  * expected for file systems which do not support fallocate() system call).
2998a2df2a63SAmit Arora  */
2999a2df2a63SAmit Arora long ext4_fallocate(struct inode *inode, int mode, loff_t offset, loff_t len)
3000a2df2a63SAmit Arora {
3001a2df2a63SAmit Arora 	handle_t *handle;
3002725d26d3SAneesh Kumar K.V 	ext4_lblk_t block;
3003fd28784aSAneesh Kumar K.V 	loff_t new_size;
3004*498e5f24STheodore Ts'o 	unsigned int max_blocks;
3005a2df2a63SAmit Arora 	int ret = 0;
3006a2df2a63SAmit Arora 	int ret2 = 0;
3007a2df2a63SAmit Arora 	int retries = 0;
3008a2df2a63SAmit Arora 	struct buffer_head map_bh;
3009a2df2a63SAmit Arora 	unsigned int credits, blkbits = inode->i_blkbits;
3010a2df2a63SAmit Arora 
3011a2df2a63SAmit Arora 	/*
3012a2df2a63SAmit Arora 	 * currently supporting (pre)allocate mode for extent-based
3013a2df2a63SAmit Arora 	 * files _only_
3014a2df2a63SAmit Arora 	 */
3015a2df2a63SAmit Arora 	if (!(EXT4_I(inode)->i_flags & EXT4_EXTENTS_FL))
3016a2df2a63SAmit Arora 		return -EOPNOTSUPP;
3017a2df2a63SAmit Arora 
3018a2df2a63SAmit Arora 	/* preallocation to directories is currently not supported */
3019a2df2a63SAmit Arora 	if (S_ISDIR(inode->i_mode))
3020a2df2a63SAmit Arora 		return -ENODEV;
3021a2df2a63SAmit Arora 
3022a2df2a63SAmit Arora 	block = offset >> blkbits;
3023fd28784aSAneesh Kumar K.V 	/*
3024fd28784aSAneesh Kumar K.V 	 * We can't just convert len to max_blocks because
3025fd28784aSAneesh Kumar K.V 	 * If blocksize = 4096 offset = 3072 and len = 2048
3026fd28784aSAneesh Kumar K.V 	 */
3027a2df2a63SAmit Arora 	max_blocks = (EXT4_BLOCK_ALIGN(len + offset, blkbits) >> blkbits)
3028a2df2a63SAmit Arora 							- block;
3029a2df2a63SAmit Arora 	/*
3030f3bd1f3fSMingming Cao 	 * credits to insert 1 extent into extent tree
3031a2df2a63SAmit Arora 	 */
3032f3bd1f3fSMingming Cao 	credits = ext4_chunk_trans_blocks(inode, max_blocks);
303355bd725aSAneesh Kumar K.V 	mutex_lock(&inode->i_mutex);
3034a2df2a63SAmit Arora retry:
3035a2df2a63SAmit Arora 	while (ret >= 0 && ret < max_blocks) {
3036a2df2a63SAmit Arora 		block = block + ret;
3037a2df2a63SAmit Arora 		max_blocks = max_blocks - ret;
3038a2df2a63SAmit Arora 		handle = ext4_journal_start(inode, credits);
3039a2df2a63SAmit Arora 		if (IS_ERR(handle)) {
3040a2df2a63SAmit Arora 			ret = PTR_ERR(handle);
3041a2df2a63SAmit Arora 			break;
3042a2df2a63SAmit Arora 		}
304355bd725aSAneesh Kumar K.V 		ret = ext4_get_blocks_wrap(handle, inode, block,
3044a2df2a63SAmit Arora 					  max_blocks, &map_bh,
3045d2a17637SMingming Cao 					  EXT4_CREATE_UNINITIALIZED_EXT, 0, 0);
3046221879c9SAneesh Kumar K.V 		if (ret <= 0) {
30472c98615dSAneesh Kumar K.V #ifdef EXT4FS_DEBUG
30482c98615dSAneesh Kumar K.V 			WARN_ON(ret <= 0);
30492c98615dSAneesh Kumar K.V 			printk(KERN_ERR "%s: ext4_ext_get_blocks "
30502c98615dSAneesh Kumar K.V 				    "returned error inode#%lu, block=%u, "
30512c98615dSAneesh Kumar K.V 				    "max_blocks=%lu", __func__,
3052bba90743SEric Sandeen 				    inode->i_ino, block, max_blocks);
30532c98615dSAneesh Kumar K.V #endif
3054a2df2a63SAmit Arora 			ext4_mark_inode_dirty(handle, inode);
3055a2df2a63SAmit Arora 			ret2 = ext4_journal_stop(handle);
3056a2df2a63SAmit Arora 			break;
3057a2df2a63SAmit Arora 		}
3058fd28784aSAneesh Kumar K.V 		if ((block + ret) >= (EXT4_BLOCK_ALIGN(offset + len,
3059fd28784aSAneesh Kumar K.V 						blkbits) >> blkbits))
3060fd28784aSAneesh Kumar K.V 			new_size = offset + len;
3061fd28784aSAneesh Kumar K.V 		else
3062fd28784aSAneesh Kumar K.V 			new_size = (block + ret) << blkbits;
3063a2df2a63SAmit Arora 
3064fd28784aSAneesh Kumar K.V 		ext4_falloc_update_inode(inode, mode, new_size,
3065fd28784aSAneesh Kumar K.V 						buffer_new(&map_bh));
3066a2df2a63SAmit Arora 		ext4_mark_inode_dirty(handle, inode);
3067a2df2a63SAmit Arora 		ret2 = ext4_journal_stop(handle);
3068a2df2a63SAmit Arora 		if (ret2)
3069a2df2a63SAmit Arora 			break;
3070a2df2a63SAmit Arora 	}
3071fd28784aSAneesh Kumar K.V 	if (ret == -ENOSPC &&
3072fd28784aSAneesh Kumar K.V 			ext4_should_retry_alloc(inode->i_sb, &retries)) {
3073fd28784aSAneesh Kumar K.V 		ret = 0;
3074a2df2a63SAmit Arora 		goto retry;
3075a2df2a63SAmit Arora 	}
307655bd725aSAneesh Kumar K.V 	mutex_unlock(&inode->i_mutex);
3077a2df2a63SAmit Arora 	return ret > 0 ? ret2 : ret;
3078a2df2a63SAmit Arora }
30796873fa0dSEric Sandeen 
30806873fa0dSEric Sandeen /*
30816873fa0dSEric Sandeen  * Callback function called for each extent to gather FIEMAP information.
30826873fa0dSEric Sandeen  */
30836873fa0dSEric Sandeen int ext4_ext_fiemap_cb(struct inode *inode, struct ext4_ext_path *path,
30846873fa0dSEric Sandeen 		       struct ext4_ext_cache *newex, struct ext4_extent *ex,
30856873fa0dSEric Sandeen 		       void *data)
30866873fa0dSEric Sandeen {
30876873fa0dSEric Sandeen 	struct fiemap_extent_info *fieinfo = data;
30886873fa0dSEric Sandeen 	unsigned long blksize_bits = inode->i_sb->s_blocksize_bits;
30896873fa0dSEric Sandeen 	__u64	logical;
30906873fa0dSEric Sandeen 	__u64	physical;
30916873fa0dSEric Sandeen 	__u64	length;
30926873fa0dSEric Sandeen 	__u32	flags = 0;
30936873fa0dSEric Sandeen 	int	error;
30946873fa0dSEric Sandeen 
30956873fa0dSEric Sandeen 	logical =  (__u64)newex->ec_block << blksize_bits;
30966873fa0dSEric Sandeen 
30976873fa0dSEric Sandeen 	if (newex->ec_type == EXT4_EXT_CACHE_GAP) {
30986873fa0dSEric Sandeen 		pgoff_t offset;
30996873fa0dSEric Sandeen 		struct page *page;
31006873fa0dSEric Sandeen 		struct buffer_head *bh = NULL;
31016873fa0dSEric Sandeen 
31026873fa0dSEric Sandeen 		offset = logical >> PAGE_SHIFT;
31036873fa0dSEric Sandeen 		page = find_get_page(inode->i_mapping, offset);
31046873fa0dSEric Sandeen 		if (!page || !page_has_buffers(page))
31056873fa0dSEric Sandeen 			return EXT_CONTINUE;
31066873fa0dSEric Sandeen 
31076873fa0dSEric Sandeen 		bh = page_buffers(page);
31086873fa0dSEric Sandeen 
31096873fa0dSEric Sandeen 		if (!bh)
31106873fa0dSEric Sandeen 			return EXT_CONTINUE;
31116873fa0dSEric Sandeen 
31126873fa0dSEric Sandeen 		if (buffer_delay(bh)) {
31136873fa0dSEric Sandeen 			flags |= FIEMAP_EXTENT_DELALLOC;
31146873fa0dSEric Sandeen 			page_cache_release(page);
31156873fa0dSEric Sandeen 		} else {
31166873fa0dSEric Sandeen 			page_cache_release(page);
31176873fa0dSEric Sandeen 			return EXT_CONTINUE;
31186873fa0dSEric Sandeen 		}
31196873fa0dSEric Sandeen 	}
31206873fa0dSEric Sandeen 
31216873fa0dSEric Sandeen 	physical = (__u64)newex->ec_start << blksize_bits;
31226873fa0dSEric Sandeen 	length =   (__u64)newex->ec_len << blksize_bits;
31236873fa0dSEric Sandeen 
31246873fa0dSEric Sandeen 	if (ex && ext4_ext_is_uninitialized(ex))
31256873fa0dSEric Sandeen 		flags |= FIEMAP_EXTENT_UNWRITTEN;
31266873fa0dSEric Sandeen 
31276873fa0dSEric Sandeen 	/*
31286873fa0dSEric Sandeen 	 * If this extent reaches EXT_MAX_BLOCK, it must be last.
31296873fa0dSEric Sandeen 	 *
31306873fa0dSEric Sandeen 	 * Or if ext4_ext_next_allocated_block is EXT_MAX_BLOCK,
31316873fa0dSEric Sandeen 	 * this also indicates no more allocated blocks.
31326873fa0dSEric Sandeen 	 *
31336873fa0dSEric Sandeen 	 * XXX this might miss a single-block extent at EXT_MAX_BLOCK
31346873fa0dSEric Sandeen 	 */
31356873fa0dSEric Sandeen 	if (logical + length - 1 == EXT_MAX_BLOCK ||
31366873fa0dSEric Sandeen 	    ext4_ext_next_allocated_block(path) == EXT_MAX_BLOCK)
31376873fa0dSEric Sandeen 		flags |= FIEMAP_EXTENT_LAST;
31386873fa0dSEric Sandeen 
31396873fa0dSEric Sandeen 	error = fiemap_fill_next_extent(fieinfo, logical, physical,
31406873fa0dSEric Sandeen 					length, flags);
31416873fa0dSEric Sandeen 	if (error < 0)
31426873fa0dSEric Sandeen 		return error;
31436873fa0dSEric Sandeen 	if (error == 1)
31446873fa0dSEric Sandeen 		return EXT_BREAK;
31456873fa0dSEric Sandeen 
31466873fa0dSEric Sandeen 	return EXT_CONTINUE;
31476873fa0dSEric Sandeen }
31486873fa0dSEric Sandeen 
31496873fa0dSEric Sandeen /* fiemap flags we can handle specified here */
31506873fa0dSEric Sandeen #define EXT4_FIEMAP_FLAGS	(FIEMAP_FLAG_SYNC|FIEMAP_FLAG_XATTR)
31516873fa0dSEric Sandeen 
31526873fa0dSEric Sandeen int ext4_xattr_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo)
31536873fa0dSEric Sandeen {
31546873fa0dSEric Sandeen 	__u64 physical = 0;
31556873fa0dSEric Sandeen 	__u64 length;
31566873fa0dSEric Sandeen 	__u32 flags = FIEMAP_EXTENT_LAST;
31576873fa0dSEric Sandeen 	int blockbits = inode->i_sb->s_blocksize_bits;
31586873fa0dSEric Sandeen 	int error = 0;
31596873fa0dSEric Sandeen 
31606873fa0dSEric Sandeen 	/* in-inode? */
31616873fa0dSEric Sandeen 	if (EXT4_I(inode)->i_state & EXT4_STATE_XATTR) {
31626873fa0dSEric Sandeen 		struct ext4_iloc iloc;
31636873fa0dSEric Sandeen 		int offset;	/* offset of xattr in inode */
31646873fa0dSEric Sandeen 
31656873fa0dSEric Sandeen 		error = ext4_get_inode_loc(inode, &iloc);
31666873fa0dSEric Sandeen 		if (error)
31676873fa0dSEric Sandeen 			return error;
31686873fa0dSEric Sandeen 		physical = iloc.bh->b_blocknr << blockbits;
31696873fa0dSEric Sandeen 		offset = EXT4_GOOD_OLD_INODE_SIZE +
31706873fa0dSEric Sandeen 				EXT4_I(inode)->i_extra_isize;
31716873fa0dSEric Sandeen 		physical += offset;
31726873fa0dSEric Sandeen 		length = EXT4_SB(inode->i_sb)->s_inode_size - offset;
31736873fa0dSEric Sandeen 		flags |= FIEMAP_EXTENT_DATA_INLINE;
31746873fa0dSEric Sandeen 	} else { /* external block */
31756873fa0dSEric Sandeen 		physical = EXT4_I(inode)->i_file_acl << blockbits;
31766873fa0dSEric Sandeen 		length = inode->i_sb->s_blocksize;
31776873fa0dSEric Sandeen 	}
31786873fa0dSEric Sandeen 
31796873fa0dSEric Sandeen 	if (physical)
31806873fa0dSEric Sandeen 		error = fiemap_fill_next_extent(fieinfo, 0, physical,
31816873fa0dSEric Sandeen 						length, flags);
31826873fa0dSEric Sandeen 	return (error < 0 ? error : 0);
31836873fa0dSEric Sandeen }
31846873fa0dSEric Sandeen 
31856873fa0dSEric Sandeen int ext4_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
31866873fa0dSEric Sandeen 		__u64 start, __u64 len)
31876873fa0dSEric Sandeen {
31886873fa0dSEric Sandeen 	ext4_lblk_t start_blk;
31896873fa0dSEric Sandeen 	ext4_lblk_t len_blks;
31906873fa0dSEric Sandeen 	int error = 0;
31916873fa0dSEric Sandeen 
31926873fa0dSEric Sandeen 	/* fallback to generic here if not in extents fmt */
31936873fa0dSEric Sandeen 	if (!(EXT4_I(inode)->i_flags & EXT4_EXTENTS_FL))
31946873fa0dSEric Sandeen 		return generic_block_fiemap(inode, fieinfo, start, len,
31956873fa0dSEric Sandeen 			ext4_get_block);
31966873fa0dSEric Sandeen 
31976873fa0dSEric Sandeen 	if (fiemap_check_flags(fieinfo, EXT4_FIEMAP_FLAGS))
31986873fa0dSEric Sandeen 		return -EBADR;
31996873fa0dSEric Sandeen 
32006873fa0dSEric Sandeen 	if (fieinfo->fi_flags & FIEMAP_FLAG_XATTR) {
32016873fa0dSEric Sandeen 		error = ext4_xattr_fiemap(inode, fieinfo);
32026873fa0dSEric Sandeen 	} else {
32036873fa0dSEric Sandeen 		start_blk = start >> inode->i_sb->s_blocksize_bits;
32046873fa0dSEric Sandeen 		len_blks = len >> inode->i_sb->s_blocksize_bits;
32056873fa0dSEric Sandeen 
32066873fa0dSEric Sandeen 		/*
32076873fa0dSEric Sandeen 		 * Walk the extent tree gathering extent information.
32086873fa0dSEric Sandeen 		 * ext4_ext_fiemap_cb will push extents back to user.
32096873fa0dSEric Sandeen 		 */
32106873fa0dSEric Sandeen 		down_write(&EXT4_I(inode)->i_data_sem);
32116873fa0dSEric Sandeen 		error = ext4_ext_walk_space(inode, start_blk, len_blks,
32126873fa0dSEric Sandeen 					  ext4_ext_fiemap_cb, fieinfo);
32136873fa0dSEric Sandeen 		up_write(&EXT4_I(inode)->i_data_sem);
32146873fa0dSEric Sandeen 	}
32156873fa0dSEric Sandeen 
32166873fa0dSEric Sandeen 	return error;
32176873fa0dSEric Sandeen }
32186873fa0dSEric Sandeen 
3219