xref: /openbmc/linux/fs/ext4/extents.c (revision 68198dca)
1 /*
2  * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
3  * Written by Alex Tomas <alex@clusterfs.com>
4  *
5  * Architecture independence:
6  *   Copyright (c) 2005, Bull S.A.
7  *   Written by Pierre Peiffer <pierre.peiffer@bull.net>
8  *
9  * This program is free software; you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License version 2 as
11  * published by the Free Software Foundation.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, write to the Free Software
20  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-
21  */
22 
23 /*
24  * Extents support for EXT4
25  *
26  * TODO:
27  *   - ext4*_error() should be used in some situations
28  *   - analyze all BUG()/BUG_ON(), use -EIO where appropriate
29  *   - smart tree reduction
30  */
31 
32 #include <linux/fs.h>
33 #include <linux/time.h>
34 #include <linux/jbd2.h>
35 #include <linux/highuid.h>
36 #include <linux/pagemap.h>
37 #include <linux/quotaops.h>
38 #include <linux/string.h>
39 #include <linux/slab.h>
40 #include <linux/uaccess.h>
41 #include <linux/fiemap.h>
42 #include <linux/backing-dev.h>
43 #include "ext4_jbd2.h"
44 #include "ext4_extents.h"
45 #include "xattr.h"
46 
47 #include <trace/events/ext4.h>
48 
49 /*
50  * used by extent splitting.
51  */
52 #define EXT4_EXT_MAY_ZEROOUT	0x1  /* safe to zeroout if split fails \
53 					due to ENOSPC */
54 #define EXT4_EXT_MARK_UNWRIT1	0x2  /* mark first half unwritten */
55 #define EXT4_EXT_MARK_UNWRIT2	0x4  /* mark second half unwritten */
56 
57 #define EXT4_EXT_DATA_VALID1	0x8  /* first half contains valid data */
58 #define EXT4_EXT_DATA_VALID2	0x10 /* second half contains valid data */
59 
60 static __le32 ext4_extent_block_csum(struct inode *inode,
61 				     struct ext4_extent_header *eh)
62 {
63 	struct ext4_inode_info *ei = EXT4_I(inode);
64 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
65 	__u32 csum;
66 
67 	csum = ext4_chksum(sbi, ei->i_csum_seed, (__u8 *)eh,
68 			   EXT4_EXTENT_TAIL_OFFSET(eh));
69 	return cpu_to_le32(csum);
70 }
71 
72 static int ext4_extent_block_csum_verify(struct inode *inode,
73 					 struct ext4_extent_header *eh)
74 {
75 	struct ext4_extent_tail *et;
76 
77 	if (!ext4_has_metadata_csum(inode->i_sb))
78 		return 1;
79 
80 	et = find_ext4_extent_tail(eh);
81 	if (et->et_checksum != ext4_extent_block_csum(inode, eh))
82 		return 0;
83 	return 1;
84 }
85 
86 static void ext4_extent_block_csum_set(struct inode *inode,
87 				       struct ext4_extent_header *eh)
88 {
89 	struct ext4_extent_tail *et;
90 
91 	if (!ext4_has_metadata_csum(inode->i_sb))
92 		return;
93 
94 	et = find_ext4_extent_tail(eh);
95 	et->et_checksum = ext4_extent_block_csum(inode, eh);
96 }
97 
98 static int ext4_split_extent(handle_t *handle,
99 				struct inode *inode,
100 				struct ext4_ext_path **ppath,
101 				struct ext4_map_blocks *map,
102 				int split_flag,
103 				int flags);
104 
105 static int ext4_split_extent_at(handle_t *handle,
106 			     struct inode *inode,
107 			     struct ext4_ext_path **ppath,
108 			     ext4_lblk_t split,
109 			     int split_flag,
110 			     int flags);
111 
112 static int ext4_find_delayed_extent(struct inode *inode,
113 				    struct extent_status *newes);
114 
115 static int ext4_ext_truncate_extend_restart(handle_t *handle,
116 					    struct inode *inode,
117 					    int needed)
118 {
119 	int err;
120 
121 	if (!ext4_handle_valid(handle))
122 		return 0;
123 	if (handle->h_buffer_credits >= needed)
124 		return 0;
125 	/*
126 	 * If we need to extend the journal get a few extra blocks
127 	 * while we're at it for efficiency's sake.
128 	 */
129 	needed += 3;
130 	err = ext4_journal_extend(handle, needed - handle->h_buffer_credits);
131 	if (err <= 0)
132 		return err;
133 	err = ext4_truncate_restart_trans(handle, inode, needed);
134 	if (err == 0)
135 		err = -EAGAIN;
136 
137 	return err;
138 }
139 
140 /*
141  * could return:
142  *  - EROFS
143  *  - ENOMEM
144  */
145 static int ext4_ext_get_access(handle_t *handle, struct inode *inode,
146 				struct ext4_ext_path *path)
147 {
148 	if (path->p_bh) {
149 		/* path points to block */
150 		BUFFER_TRACE(path->p_bh, "get_write_access");
151 		return ext4_journal_get_write_access(handle, path->p_bh);
152 	}
153 	/* path points to leaf/index in inode body */
154 	/* we use in-core data, no need to protect them */
155 	return 0;
156 }
157 
158 /*
159  * could return:
160  *  - EROFS
161  *  - ENOMEM
162  *  - EIO
163  */
164 int __ext4_ext_dirty(const char *where, unsigned int line, handle_t *handle,
165 		     struct inode *inode, struct ext4_ext_path *path)
166 {
167 	int err;
168 
169 	WARN_ON(!rwsem_is_locked(&EXT4_I(inode)->i_data_sem));
170 	if (path->p_bh) {
171 		ext4_extent_block_csum_set(inode, ext_block_hdr(path->p_bh));
172 		/* path points to block */
173 		err = __ext4_handle_dirty_metadata(where, line, handle,
174 						   inode, path->p_bh);
175 	} else {
176 		/* path points to leaf/index in inode body */
177 		err = ext4_mark_inode_dirty(handle, inode);
178 	}
179 	return err;
180 }
181 
182 static ext4_fsblk_t ext4_ext_find_goal(struct inode *inode,
183 			      struct ext4_ext_path *path,
184 			      ext4_lblk_t block)
185 {
186 	if (path) {
187 		int depth = path->p_depth;
188 		struct ext4_extent *ex;
189 
190 		/*
191 		 * Try to predict block placement assuming that we are
192 		 * filling in a file which will eventually be
193 		 * non-sparse --- i.e., in the case of libbfd writing
194 		 * an ELF object sections out-of-order but in a way
195 		 * the eventually results in a contiguous object or
196 		 * executable file, or some database extending a table
197 		 * space file.  However, this is actually somewhat
198 		 * non-ideal if we are writing a sparse file such as
199 		 * qemu or KVM writing a raw image file that is going
200 		 * to stay fairly sparse, since it will end up
201 		 * fragmenting the file system's free space.  Maybe we
202 		 * should have some hueristics or some way to allow
203 		 * userspace to pass a hint to file system,
204 		 * especially if the latter case turns out to be
205 		 * common.
206 		 */
207 		ex = path[depth].p_ext;
208 		if (ex) {
209 			ext4_fsblk_t ext_pblk = ext4_ext_pblock(ex);
210 			ext4_lblk_t ext_block = le32_to_cpu(ex->ee_block);
211 
212 			if (block > ext_block)
213 				return ext_pblk + (block - ext_block);
214 			else
215 				return ext_pblk - (ext_block - block);
216 		}
217 
218 		/* it looks like index is empty;
219 		 * try to find starting block from index itself */
220 		if (path[depth].p_bh)
221 			return path[depth].p_bh->b_blocknr;
222 	}
223 
224 	/* OK. use inode's group */
225 	return ext4_inode_to_goal_block(inode);
226 }
227 
228 /*
229  * Allocation for a meta data block
230  */
231 static ext4_fsblk_t
232 ext4_ext_new_meta_block(handle_t *handle, struct inode *inode,
233 			struct ext4_ext_path *path,
234 			struct ext4_extent *ex, int *err, unsigned int flags)
235 {
236 	ext4_fsblk_t goal, newblock;
237 
238 	goal = ext4_ext_find_goal(inode, path, le32_to_cpu(ex->ee_block));
239 	newblock = ext4_new_meta_blocks(handle, inode, goal, flags,
240 					NULL, err);
241 	return newblock;
242 }
243 
244 static inline int ext4_ext_space_block(struct inode *inode, int check)
245 {
246 	int size;
247 
248 	size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
249 			/ sizeof(struct ext4_extent);
250 #ifdef AGGRESSIVE_TEST
251 	if (!check && size > 6)
252 		size = 6;
253 #endif
254 	return size;
255 }
256 
257 static inline int ext4_ext_space_block_idx(struct inode *inode, int check)
258 {
259 	int size;
260 
261 	size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
262 			/ sizeof(struct ext4_extent_idx);
263 #ifdef AGGRESSIVE_TEST
264 	if (!check && size > 5)
265 		size = 5;
266 #endif
267 	return size;
268 }
269 
270 static inline int ext4_ext_space_root(struct inode *inode, int check)
271 {
272 	int size;
273 
274 	size = sizeof(EXT4_I(inode)->i_data);
275 	size -= sizeof(struct ext4_extent_header);
276 	size /= sizeof(struct ext4_extent);
277 #ifdef AGGRESSIVE_TEST
278 	if (!check && size > 3)
279 		size = 3;
280 #endif
281 	return size;
282 }
283 
284 static inline int ext4_ext_space_root_idx(struct inode *inode, int check)
285 {
286 	int size;
287 
288 	size = sizeof(EXT4_I(inode)->i_data);
289 	size -= sizeof(struct ext4_extent_header);
290 	size /= sizeof(struct ext4_extent_idx);
291 #ifdef AGGRESSIVE_TEST
292 	if (!check && size > 4)
293 		size = 4;
294 #endif
295 	return size;
296 }
297 
298 static inline int
299 ext4_force_split_extent_at(handle_t *handle, struct inode *inode,
300 			   struct ext4_ext_path **ppath, ext4_lblk_t lblk,
301 			   int nofail)
302 {
303 	struct ext4_ext_path *path = *ppath;
304 	int unwritten = ext4_ext_is_unwritten(path[path->p_depth].p_ext);
305 
306 	return ext4_split_extent_at(handle, inode, ppath, lblk, unwritten ?
307 			EXT4_EXT_MARK_UNWRIT1|EXT4_EXT_MARK_UNWRIT2 : 0,
308 			EXT4_EX_NOCACHE | EXT4_GET_BLOCKS_PRE_IO |
309 			(nofail ? EXT4_GET_BLOCKS_METADATA_NOFAIL:0));
310 }
311 
312 /*
313  * Calculate the number of metadata blocks needed
314  * to allocate @blocks
315  * Worse case is one block per extent
316  */
317 int ext4_ext_calc_metadata_amount(struct inode *inode, ext4_lblk_t lblock)
318 {
319 	struct ext4_inode_info *ei = EXT4_I(inode);
320 	int idxs;
321 
322 	idxs = ((inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
323 		/ sizeof(struct ext4_extent_idx));
324 
325 	/*
326 	 * If the new delayed allocation block is contiguous with the
327 	 * previous da block, it can share index blocks with the
328 	 * previous block, so we only need to allocate a new index
329 	 * block every idxs leaf blocks.  At ldxs**2 blocks, we need
330 	 * an additional index block, and at ldxs**3 blocks, yet
331 	 * another index blocks.
332 	 */
333 	if (ei->i_da_metadata_calc_len &&
334 	    ei->i_da_metadata_calc_last_lblock+1 == lblock) {
335 		int num = 0;
336 
337 		if ((ei->i_da_metadata_calc_len % idxs) == 0)
338 			num++;
339 		if ((ei->i_da_metadata_calc_len % (idxs*idxs)) == 0)
340 			num++;
341 		if ((ei->i_da_metadata_calc_len % (idxs*idxs*idxs)) == 0) {
342 			num++;
343 			ei->i_da_metadata_calc_len = 0;
344 		} else
345 			ei->i_da_metadata_calc_len++;
346 		ei->i_da_metadata_calc_last_lblock++;
347 		return num;
348 	}
349 
350 	/*
351 	 * In the worst case we need a new set of index blocks at
352 	 * every level of the inode's extent tree.
353 	 */
354 	ei->i_da_metadata_calc_len = 1;
355 	ei->i_da_metadata_calc_last_lblock = lblock;
356 	return ext_depth(inode) + 1;
357 }
358 
359 static int
360 ext4_ext_max_entries(struct inode *inode, int depth)
361 {
362 	int max;
363 
364 	if (depth == ext_depth(inode)) {
365 		if (depth == 0)
366 			max = ext4_ext_space_root(inode, 1);
367 		else
368 			max = ext4_ext_space_root_idx(inode, 1);
369 	} else {
370 		if (depth == 0)
371 			max = ext4_ext_space_block(inode, 1);
372 		else
373 			max = ext4_ext_space_block_idx(inode, 1);
374 	}
375 
376 	return max;
377 }
378 
379 static int ext4_valid_extent(struct inode *inode, struct ext4_extent *ext)
380 {
381 	ext4_fsblk_t block = ext4_ext_pblock(ext);
382 	int len = ext4_ext_get_actual_len(ext);
383 	ext4_lblk_t lblock = le32_to_cpu(ext->ee_block);
384 
385 	/*
386 	 * We allow neither:
387 	 *  - zero length
388 	 *  - overflow/wrap-around
389 	 */
390 	if (lblock + len <= lblock)
391 		return 0;
392 	return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, len);
393 }
394 
395 static int ext4_valid_extent_idx(struct inode *inode,
396 				struct ext4_extent_idx *ext_idx)
397 {
398 	ext4_fsblk_t block = ext4_idx_pblock(ext_idx);
399 
400 	return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, 1);
401 }
402 
403 static int ext4_valid_extent_entries(struct inode *inode,
404 				struct ext4_extent_header *eh,
405 				int depth)
406 {
407 	unsigned short entries;
408 	if (eh->eh_entries == 0)
409 		return 1;
410 
411 	entries = le16_to_cpu(eh->eh_entries);
412 
413 	if (depth == 0) {
414 		/* leaf entries */
415 		struct ext4_extent *ext = EXT_FIRST_EXTENT(eh);
416 		struct ext4_super_block *es = EXT4_SB(inode->i_sb)->s_es;
417 		ext4_fsblk_t pblock = 0;
418 		ext4_lblk_t lblock = 0;
419 		ext4_lblk_t prev = 0;
420 		int len = 0;
421 		while (entries) {
422 			if (!ext4_valid_extent(inode, ext))
423 				return 0;
424 
425 			/* Check for overlapping extents */
426 			lblock = le32_to_cpu(ext->ee_block);
427 			len = ext4_ext_get_actual_len(ext);
428 			if ((lblock <= prev) && prev) {
429 				pblock = ext4_ext_pblock(ext);
430 				es->s_last_error_block = cpu_to_le64(pblock);
431 				return 0;
432 			}
433 			ext++;
434 			entries--;
435 			prev = lblock + len - 1;
436 		}
437 	} else {
438 		struct ext4_extent_idx *ext_idx = EXT_FIRST_INDEX(eh);
439 		while (entries) {
440 			if (!ext4_valid_extent_idx(inode, ext_idx))
441 				return 0;
442 			ext_idx++;
443 			entries--;
444 		}
445 	}
446 	return 1;
447 }
448 
449 static int __ext4_ext_check(const char *function, unsigned int line,
450 			    struct inode *inode, struct ext4_extent_header *eh,
451 			    int depth, ext4_fsblk_t pblk)
452 {
453 	const char *error_msg;
454 	int max = 0, err = -EFSCORRUPTED;
455 
456 	if (unlikely(eh->eh_magic != EXT4_EXT_MAGIC)) {
457 		error_msg = "invalid magic";
458 		goto corrupted;
459 	}
460 	if (unlikely(le16_to_cpu(eh->eh_depth) != depth)) {
461 		error_msg = "unexpected eh_depth";
462 		goto corrupted;
463 	}
464 	if (unlikely(eh->eh_max == 0)) {
465 		error_msg = "invalid eh_max";
466 		goto corrupted;
467 	}
468 	max = ext4_ext_max_entries(inode, depth);
469 	if (unlikely(le16_to_cpu(eh->eh_max) > max)) {
470 		error_msg = "too large eh_max";
471 		goto corrupted;
472 	}
473 	if (unlikely(le16_to_cpu(eh->eh_entries) > le16_to_cpu(eh->eh_max))) {
474 		error_msg = "invalid eh_entries";
475 		goto corrupted;
476 	}
477 	if (!ext4_valid_extent_entries(inode, eh, depth)) {
478 		error_msg = "invalid extent entries";
479 		goto corrupted;
480 	}
481 	if (unlikely(depth > 32)) {
482 		error_msg = "too large eh_depth";
483 		goto corrupted;
484 	}
485 	/* Verify checksum on non-root extent tree nodes */
486 	if (ext_depth(inode) != depth &&
487 	    !ext4_extent_block_csum_verify(inode, eh)) {
488 		error_msg = "extent tree corrupted";
489 		err = -EFSBADCRC;
490 		goto corrupted;
491 	}
492 	return 0;
493 
494 corrupted:
495 	ext4_error_inode(inode, function, line, 0,
496 			 "pblk %llu bad header/extent: %s - magic %x, "
497 			 "entries %u, max %u(%u), depth %u(%u)",
498 			 (unsigned long long) pblk, error_msg,
499 			 le16_to_cpu(eh->eh_magic),
500 			 le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max),
501 			 max, le16_to_cpu(eh->eh_depth), depth);
502 	return err;
503 }
504 
505 #define ext4_ext_check(inode, eh, depth, pblk)			\
506 	__ext4_ext_check(__func__, __LINE__, (inode), (eh), (depth), (pblk))
507 
508 int ext4_ext_check_inode(struct inode *inode)
509 {
510 	return ext4_ext_check(inode, ext_inode_hdr(inode), ext_depth(inode), 0);
511 }
512 
513 static struct buffer_head *
514 __read_extent_tree_block(const char *function, unsigned int line,
515 			 struct inode *inode, ext4_fsblk_t pblk, int depth,
516 			 int flags)
517 {
518 	struct buffer_head		*bh;
519 	int				err;
520 
521 	bh = sb_getblk_gfp(inode->i_sb, pblk, __GFP_MOVABLE | GFP_NOFS);
522 	if (unlikely(!bh))
523 		return ERR_PTR(-ENOMEM);
524 
525 	if (!bh_uptodate_or_lock(bh)) {
526 		trace_ext4_ext_load_extent(inode, pblk, _RET_IP_);
527 		err = bh_submit_read(bh);
528 		if (err < 0)
529 			goto errout;
530 	}
531 	if (buffer_verified(bh) && !(flags & EXT4_EX_FORCE_CACHE))
532 		return bh;
533 	err = __ext4_ext_check(function, line, inode,
534 			       ext_block_hdr(bh), depth, pblk);
535 	if (err)
536 		goto errout;
537 	set_buffer_verified(bh);
538 	/*
539 	 * If this is a leaf block, cache all of its entries
540 	 */
541 	if (!(flags & EXT4_EX_NOCACHE) && depth == 0) {
542 		struct ext4_extent_header *eh = ext_block_hdr(bh);
543 		struct ext4_extent *ex = EXT_FIRST_EXTENT(eh);
544 		ext4_lblk_t prev = 0;
545 		int i;
546 
547 		for (i = le16_to_cpu(eh->eh_entries); i > 0; i--, ex++) {
548 			unsigned int status = EXTENT_STATUS_WRITTEN;
549 			ext4_lblk_t lblk = le32_to_cpu(ex->ee_block);
550 			int len = ext4_ext_get_actual_len(ex);
551 
552 			if (prev && (prev != lblk))
553 				ext4_es_cache_extent(inode, prev,
554 						     lblk - prev, ~0,
555 						     EXTENT_STATUS_HOLE);
556 
557 			if (ext4_ext_is_unwritten(ex))
558 				status = EXTENT_STATUS_UNWRITTEN;
559 			ext4_es_cache_extent(inode, lblk, len,
560 					     ext4_ext_pblock(ex), status);
561 			prev = lblk + len;
562 		}
563 	}
564 	return bh;
565 errout:
566 	put_bh(bh);
567 	return ERR_PTR(err);
568 
569 }
570 
571 #define read_extent_tree_block(inode, pblk, depth, flags)		\
572 	__read_extent_tree_block(__func__, __LINE__, (inode), (pblk),   \
573 				 (depth), (flags))
574 
575 /*
576  * This function is called to cache a file's extent information in the
577  * extent status tree
578  */
579 int ext4_ext_precache(struct inode *inode)
580 {
581 	struct ext4_inode_info *ei = EXT4_I(inode);
582 	struct ext4_ext_path *path = NULL;
583 	struct buffer_head *bh;
584 	int i = 0, depth, ret = 0;
585 
586 	if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
587 		return 0;	/* not an extent-mapped inode */
588 
589 	down_read(&ei->i_data_sem);
590 	depth = ext_depth(inode);
591 
592 	path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 1),
593 		       GFP_NOFS);
594 	if (path == NULL) {
595 		up_read(&ei->i_data_sem);
596 		return -ENOMEM;
597 	}
598 
599 	/* Don't cache anything if there are no external extent blocks */
600 	if (depth == 0)
601 		goto out;
602 	path[0].p_hdr = ext_inode_hdr(inode);
603 	ret = ext4_ext_check(inode, path[0].p_hdr, depth, 0);
604 	if (ret)
605 		goto out;
606 	path[0].p_idx = EXT_FIRST_INDEX(path[0].p_hdr);
607 	while (i >= 0) {
608 		/*
609 		 * If this is a leaf block or we've reached the end of
610 		 * the index block, go up
611 		 */
612 		if ((i == depth) ||
613 		    path[i].p_idx > EXT_LAST_INDEX(path[i].p_hdr)) {
614 			brelse(path[i].p_bh);
615 			path[i].p_bh = NULL;
616 			i--;
617 			continue;
618 		}
619 		bh = read_extent_tree_block(inode,
620 					    ext4_idx_pblock(path[i].p_idx++),
621 					    depth - i - 1,
622 					    EXT4_EX_FORCE_CACHE);
623 		if (IS_ERR(bh)) {
624 			ret = PTR_ERR(bh);
625 			break;
626 		}
627 		i++;
628 		path[i].p_bh = bh;
629 		path[i].p_hdr = ext_block_hdr(bh);
630 		path[i].p_idx = EXT_FIRST_INDEX(path[i].p_hdr);
631 	}
632 	ext4_set_inode_state(inode, EXT4_STATE_EXT_PRECACHED);
633 out:
634 	up_read(&ei->i_data_sem);
635 	ext4_ext_drop_refs(path);
636 	kfree(path);
637 	return ret;
638 }
639 
640 #ifdef EXT_DEBUG
641 static void ext4_ext_show_path(struct inode *inode, struct ext4_ext_path *path)
642 {
643 	int k, l = path->p_depth;
644 
645 	ext_debug("path:");
646 	for (k = 0; k <= l; k++, path++) {
647 		if (path->p_idx) {
648 		  ext_debug("  %d->%llu", le32_to_cpu(path->p_idx->ei_block),
649 			    ext4_idx_pblock(path->p_idx));
650 		} else if (path->p_ext) {
651 			ext_debug("  %d:[%d]%d:%llu ",
652 				  le32_to_cpu(path->p_ext->ee_block),
653 				  ext4_ext_is_unwritten(path->p_ext),
654 				  ext4_ext_get_actual_len(path->p_ext),
655 				  ext4_ext_pblock(path->p_ext));
656 		} else
657 			ext_debug("  []");
658 	}
659 	ext_debug("\n");
660 }
661 
662 static void ext4_ext_show_leaf(struct inode *inode, struct ext4_ext_path *path)
663 {
664 	int depth = ext_depth(inode);
665 	struct ext4_extent_header *eh;
666 	struct ext4_extent *ex;
667 	int i;
668 
669 	if (!path)
670 		return;
671 
672 	eh = path[depth].p_hdr;
673 	ex = EXT_FIRST_EXTENT(eh);
674 
675 	ext_debug("Displaying leaf extents for inode %lu\n", inode->i_ino);
676 
677 	for (i = 0; i < le16_to_cpu(eh->eh_entries); i++, ex++) {
678 		ext_debug("%d:[%d]%d:%llu ", le32_to_cpu(ex->ee_block),
679 			  ext4_ext_is_unwritten(ex),
680 			  ext4_ext_get_actual_len(ex), ext4_ext_pblock(ex));
681 	}
682 	ext_debug("\n");
683 }
684 
685 static void ext4_ext_show_move(struct inode *inode, struct ext4_ext_path *path,
686 			ext4_fsblk_t newblock, int level)
687 {
688 	int depth = ext_depth(inode);
689 	struct ext4_extent *ex;
690 
691 	if (depth != level) {
692 		struct ext4_extent_idx *idx;
693 		idx = path[level].p_idx;
694 		while (idx <= EXT_MAX_INDEX(path[level].p_hdr)) {
695 			ext_debug("%d: move %d:%llu in new index %llu\n", level,
696 					le32_to_cpu(idx->ei_block),
697 					ext4_idx_pblock(idx),
698 					newblock);
699 			idx++;
700 		}
701 
702 		return;
703 	}
704 
705 	ex = path[depth].p_ext;
706 	while (ex <= EXT_MAX_EXTENT(path[depth].p_hdr)) {
707 		ext_debug("move %d:%llu:[%d]%d in new leaf %llu\n",
708 				le32_to_cpu(ex->ee_block),
709 				ext4_ext_pblock(ex),
710 				ext4_ext_is_unwritten(ex),
711 				ext4_ext_get_actual_len(ex),
712 				newblock);
713 		ex++;
714 	}
715 }
716 
717 #else
718 #define ext4_ext_show_path(inode, path)
719 #define ext4_ext_show_leaf(inode, path)
720 #define ext4_ext_show_move(inode, path, newblock, level)
721 #endif
722 
723 void ext4_ext_drop_refs(struct ext4_ext_path *path)
724 {
725 	int depth, i;
726 
727 	if (!path)
728 		return;
729 	depth = path->p_depth;
730 	for (i = 0; i <= depth; i++, path++)
731 		if (path->p_bh) {
732 			brelse(path->p_bh);
733 			path->p_bh = NULL;
734 		}
735 }
736 
737 /*
738  * ext4_ext_binsearch_idx:
739  * binary search for the closest index of the given block
740  * the header must be checked before calling this
741  */
742 static void
743 ext4_ext_binsearch_idx(struct inode *inode,
744 			struct ext4_ext_path *path, ext4_lblk_t block)
745 {
746 	struct ext4_extent_header *eh = path->p_hdr;
747 	struct ext4_extent_idx *r, *l, *m;
748 
749 
750 	ext_debug("binsearch for %u(idx):  ", block);
751 
752 	l = EXT_FIRST_INDEX(eh) + 1;
753 	r = EXT_LAST_INDEX(eh);
754 	while (l <= r) {
755 		m = l + (r - l) / 2;
756 		if (block < le32_to_cpu(m->ei_block))
757 			r = m - 1;
758 		else
759 			l = m + 1;
760 		ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ei_block),
761 				m, le32_to_cpu(m->ei_block),
762 				r, le32_to_cpu(r->ei_block));
763 	}
764 
765 	path->p_idx = l - 1;
766 	ext_debug("  -> %u->%lld ", le32_to_cpu(path->p_idx->ei_block),
767 		  ext4_idx_pblock(path->p_idx));
768 
769 #ifdef CHECK_BINSEARCH
770 	{
771 		struct ext4_extent_idx *chix, *ix;
772 		int k;
773 
774 		chix = ix = EXT_FIRST_INDEX(eh);
775 		for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ix++) {
776 		  if (k != 0 &&
777 		      le32_to_cpu(ix->ei_block) <= le32_to_cpu(ix[-1].ei_block)) {
778 				printk(KERN_DEBUG "k=%d, ix=0x%p, "
779 				       "first=0x%p\n", k,
780 				       ix, EXT_FIRST_INDEX(eh));
781 				printk(KERN_DEBUG "%u <= %u\n",
782 				       le32_to_cpu(ix->ei_block),
783 				       le32_to_cpu(ix[-1].ei_block));
784 			}
785 			BUG_ON(k && le32_to_cpu(ix->ei_block)
786 					   <= le32_to_cpu(ix[-1].ei_block));
787 			if (block < le32_to_cpu(ix->ei_block))
788 				break;
789 			chix = ix;
790 		}
791 		BUG_ON(chix != path->p_idx);
792 	}
793 #endif
794 
795 }
796 
797 /*
798  * ext4_ext_binsearch:
799  * binary search for closest extent of the given block
800  * the header must be checked before calling this
801  */
802 static void
803 ext4_ext_binsearch(struct inode *inode,
804 		struct ext4_ext_path *path, ext4_lblk_t block)
805 {
806 	struct ext4_extent_header *eh = path->p_hdr;
807 	struct ext4_extent *r, *l, *m;
808 
809 	if (eh->eh_entries == 0) {
810 		/*
811 		 * this leaf is empty:
812 		 * we get such a leaf in split/add case
813 		 */
814 		return;
815 	}
816 
817 	ext_debug("binsearch for %u:  ", block);
818 
819 	l = EXT_FIRST_EXTENT(eh) + 1;
820 	r = EXT_LAST_EXTENT(eh);
821 
822 	while (l <= r) {
823 		m = l + (r - l) / 2;
824 		if (block < le32_to_cpu(m->ee_block))
825 			r = m - 1;
826 		else
827 			l = m + 1;
828 		ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ee_block),
829 				m, le32_to_cpu(m->ee_block),
830 				r, le32_to_cpu(r->ee_block));
831 	}
832 
833 	path->p_ext = l - 1;
834 	ext_debug("  -> %d:%llu:[%d]%d ",
835 			le32_to_cpu(path->p_ext->ee_block),
836 			ext4_ext_pblock(path->p_ext),
837 			ext4_ext_is_unwritten(path->p_ext),
838 			ext4_ext_get_actual_len(path->p_ext));
839 
840 #ifdef CHECK_BINSEARCH
841 	{
842 		struct ext4_extent *chex, *ex;
843 		int k;
844 
845 		chex = ex = EXT_FIRST_EXTENT(eh);
846 		for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ex++) {
847 			BUG_ON(k && le32_to_cpu(ex->ee_block)
848 					  <= le32_to_cpu(ex[-1].ee_block));
849 			if (block < le32_to_cpu(ex->ee_block))
850 				break;
851 			chex = ex;
852 		}
853 		BUG_ON(chex != path->p_ext);
854 	}
855 #endif
856 
857 }
858 
859 int ext4_ext_tree_init(handle_t *handle, struct inode *inode)
860 {
861 	struct ext4_extent_header *eh;
862 
863 	eh = ext_inode_hdr(inode);
864 	eh->eh_depth = 0;
865 	eh->eh_entries = 0;
866 	eh->eh_magic = EXT4_EXT_MAGIC;
867 	eh->eh_max = cpu_to_le16(ext4_ext_space_root(inode, 0));
868 	ext4_mark_inode_dirty(handle, inode);
869 	return 0;
870 }
871 
872 struct ext4_ext_path *
873 ext4_find_extent(struct inode *inode, ext4_lblk_t block,
874 		 struct ext4_ext_path **orig_path, int flags)
875 {
876 	struct ext4_extent_header *eh;
877 	struct buffer_head *bh;
878 	struct ext4_ext_path *path = orig_path ? *orig_path : NULL;
879 	short int depth, i, ppos = 0;
880 	int ret;
881 
882 	eh = ext_inode_hdr(inode);
883 	depth = ext_depth(inode);
884 
885 	if (path) {
886 		ext4_ext_drop_refs(path);
887 		if (depth > path[0].p_maxdepth) {
888 			kfree(path);
889 			*orig_path = path = NULL;
890 		}
891 	}
892 	if (!path) {
893 		/* account possible depth increase */
894 		path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 2),
895 				GFP_NOFS);
896 		if (unlikely(!path))
897 			return ERR_PTR(-ENOMEM);
898 		path[0].p_maxdepth = depth + 1;
899 	}
900 	path[0].p_hdr = eh;
901 	path[0].p_bh = NULL;
902 
903 	i = depth;
904 	/* walk through the tree */
905 	while (i) {
906 		ext_debug("depth %d: num %d, max %d\n",
907 			  ppos, le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
908 
909 		ext4_ext_binsearch_idx(inode, path + ppos, block);
910 		path[ppos].p_block = ext4_idx_pblock(path[ppos].p_idx);
911 		path[ppos].p_depth = i;
912 		path[ppos].p_ext = NULL;
913 
914 		bh = read_extent_tree_block(inode, path[ppos].p_block, --i,
915 					    flags);
916 		if (IS_ERR(bh)) {
917 			ret = PTR_ERR(bh);
918 			goto err;
919 		}
920 
921 		eh = ext_block_hdr(bh);
922 		ppos++;
923 		path[ppos].p_bh = bh;
924 		path[ppos].p_hdr = eh;
925 	}
926 
927 	path[ppos].p_depth = i;
928 	path[ppos].p_ext = NULL;
929 	path[ppos].p_idx = NULL;
930 
931 	/* find extent */
932 	ext4_ext_binsearch(inode, path + ppos, block);
933 	/* if not an empty leaf */
934 	if (path[ppos].p_ext)
935 		path[ppos].p_block = ext4_ext_pblock(path[ppos].p_ext);
936 
937 	ext4_ext_show_path(inode, path);
938 
939 	return path;
940 
941 err:
942 	ext4_ext_drop_refs(path);
943 	kfree(path);
944 	if (orig_path)
945 		*orig_path = NULL;
946 	return ERR_PTR(ret);
947 }
948 
949 /*
950  * ext4_ext_insert_index:
951  * insert new index [@logical;@ptr] into the block at @curp;
952  * check where to insert: before @curp or after @curp
953  */
954 static int ext4_ext_insert_index(handle_t *handle, struct inode *inode,
955 				 struct ext4_ext_path *curp,
956 				 int logical, ext4_fsblk_t ptr)
957 {
958 	struct ext4_extent_idx *ix;
959 	int len, err;
960 
961 	err = ext4_ext_get_access(handle, inode, curp);
962 	if (err)
963 		return err;
964 
965 	if (unlikely(logical == le32_to_cpu(curp->p_idx->ei_block))) {
966 		EXT4_ERROR_INODE(inode,
967 				 "logical %d == ei_block %d!",
968 				 logical, le32_to_cpu(curp->p_idx->ei_block));
969 		return -EFSCORRUPTED;
970 	}
971 
972 	if (unlikely(le16_to_cpu(curp->p_hdr->eh_entries)
973 			     >= le16_to_cpu(curp->p_hdr->eh_max))) {
974 		EXT4_ERROR_INODE(inode,
975 				 "eh_entries %d >= eh_max %d!",
976 				 le16_to_cpu(curp->p_hdr->eh_entries),
977 				 le16_to_cpu(curp->p_hdr->eh_max));
978 		return -EFSCORRUPTED;
979 	}
980 
981 	if (logical > le32_to_cpu(curp->p_idx->ei_block)) {
982 		/* insert after */
983 		ext_debug("insert new index %d after: %llu\n", logical, ptr);
984 		ix = curp->p_idx + 1;
985 	} else {
986 		/* insert before */
987 		ext_debug("insert new index %d before: %llu\n", logical, ptr);
988 		ix = curp->p_idx;
989 	}
990 
991 	len = EXT_LAST_INDEX(curp->p_hdr) - ix + 1;
992 	BUG_ON(len < 0);
993 	if (len > 0) {
994 		ext_debug("insert new index %d: "
995 				"move %d indices from 0x%p to 0x%p\n",
996 				logical, len, ix, ix + 1);
997 		memmove(ix + 1, ix, len * sizeof(struct ext4_extent_idx));
998 	}
999 
1000 	if (unlikely(ix > EXT_MAX_INDEX(curp->p_hdr))) {
1001 		EXT4_ERROR_INODE(inode, "ix > EXT_MAX_INDEX!");
1002 		return -EFSCORRUPTED;
1003 	}
1004 
1005 	ix->ei_block = cpu_to_le32(logical);
1006 	ext4_idx_store_pblock(ix, ptr);
1007 	le16_add_cpu(&curp->p_hdr->eh_entries, 1);
1008 
1009 	if (unlikely(ix > EXT_LAST_INDEX(curp->p_hdr))) {
1010 		EXT4_ERROR_INODE(inode, "ix > EXT_LAST_INDEX!");
1011 		return -EFSCORRUPTED;
1012 	}
1013 
1014 	err = ext4_ext_dirty(handle, inode, curp);
1015 	ext4_std_error(inode->i_sb, err);
1016 
1017 	return err;
1018 }
1019 
1020 /*
1021  * ext4_ext_split:
1022  * inserts new subtree into the path, using free index entry
1023  * at depth @at:
1024  * - allocates all needed blocks (new leaf and all intermediate index blocks)
1025  * - makes decision where to split
1026  * - moves remaining extents and index entries (right to the split point)
1027  *   into the newly allocated blocks
1028  * - initializes subtree
1029  */
1030 static int ext4_ext_split(handle_t *handle, struct inode *inode,
1031 			  unsigned int flags,
1032 			  struct ext4_ext_path *path,
1033 			  struct ext4_extent *newext, int at)
1034 {
1035 	struct buffer_head *bh = NULL;
1036 	int depth = ext_depth(inode);
1037 	struct ext4_extent_header *neh;
1038 	struct ext4_extent_idx *fidx;
1039 	int i = at, k, m, a;
1040 	ext4_fsblk_t newblock, oldblock;
1041 	__le32 border;
1042 	ext4_fsblk_t *ablocks = NULL; /* array of allocated blocks */
1043 	int err = 0;
1044 
1045 	/* make decision: where to split? */
1046 	/* FIXME: now decision is simplest: at current extent */
1047 
1048 	/* if current leaf will be split, then we should use
1049 	 * border from split point */
1050 	if (unlikely(path[depth].p_ext > EXT_MAX_EXTENT(path[depth].p_hdr))) {
1051 		EXT4_ERROR_INODE(inode, "p_ext > EXT_MAX_EXTENT!");
1052 		return -EFSCORRUPTED;
1053 	}
1054 	if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr)) {
1055 		border = path[depth].p_ext[1].ee_block;
1056 		ext_debug("leaf will be split."
1057 				" next leaf starts at %d\n",
1058 				  le32_to_cpu(border));
1059 	} else {
1060 		border = newext->ee_block;
1061 		ext_debug("leaf will be added."
1062 				" next leaf starts at %d\n",
1063 				le32_to_cpu(border));
1064 	}
1065 
1066 	/*
1067 	 * If error occurs, then we break processing
1068 	 * and mark filesystem read-only. index won't
1069 	 * be inserted and tree will be in consistent
1070 	 * state. Next mount will repair buffers too.
1071 	 */
1072 
1073 	/*
1074 	 * Get array to track all allocated blocks.
1075 	 * We need this to handle errors and free blocks
1076 	 * upon them.
1077 	 */
1078 	ablocks = kzalloc(sizeof(ext4_fsblk_t) * depth, GFP_NOFS);
1079 	if (!ablocks)
1080 		return -ENOMEM;
1081 
1082 	/* allocate all needed blocks */
1083 	ext_debug("allocate %d blocks for indexes/leaf\n", depth - at);
1084 	for (a = 0; a < depth - at; a++) {
1085 		newblock = ext4_ext_new_meta_block(handle, inode, path,
1086 						   newext, &err, flags);
1087 		if (newblock == 0)
1088 			goto cleanup;
1089 		ablocks[a] = newblock;
1090 	}
1091 
1092 	/* initialize new leaf */
1093 	newblock = ablocks[--a];
1094 	if (unlikely(newblock == 0)) {
1095 		EXT4_ERROR_INODE(inode, "newblock == 0!");
1096 		err = -EFSCORRUPTED;
1097 		goto cleanup;
1098 	}
1099 	bh = sb_getblk_gfp(inode->i_sb, newblock, __GFP_MOVABLE | GFP_NOFS);
1100 	if (unlikely(!bh)) {
1101 		err = -ENOMEM;
1102 		goto cleanup;
1103 	}
1104 	lock_buffer(bh);
1105 
1106 	err = ext4_journal_get_create_access(handle, bh);
1107 	if (err)
1108 		goto cleanup;
1109 
1110 	neh = ext_block_hdr(bh);
1111 	neh->eh_entries = 0;
1112 	neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
1113 	neh->eh_magic = EXT4_EXT_MAGIC;
1114 	neh->eh_depth = 0;
1115 
1116 	/* move remainder of path[depth] to the new leaf */
1117 	if (unlikely(path[depth].p_hdr->eh_entries !=
1118 		     path[depth].p_hdr->eh_max)) {
1119 		EXT4_ERROR_INODE(inode, "eh_entries %d != eh_max %d!",
1120 				 path[depth].p_hdr->eh_entries,
1121 				 path[depth].p_hdr->eh_max);
1122 		err = -EFSCORRUPTED;
1123 		goto cleanup;
1124 	}
1125 	/* start copy from next extent */
1126 	m = EXT_MAX_EXTENT(path[depth].p_hdr) - path[depth].p_ext++;
1127 	ext4_ext_show_move(inode, path, newblock, depth);
1128 	if (m) {
1129 		struct ext4_extent *ex;
1130 		ex = EXT_FIRST_EXTENT(neh);
1131 		memmove(ex, path[depth].p_ext, sizeof(struct ext4_extent) * m);
1132 		le16_add_cpu(&neh->eh_entries, m);
1133 	}
1134 
1135 	ext4_extent_block_csum_set(inode, neh);
1136 	set_buffer_uptodate(bh);
1137 	unlock_buffer(bh);
1138 
1139 	err = ext4_handle_dirty_metadata(handle, inode, bh);
1140 	if (err)
1141 		goto cleanup;
1142 	brelse(bh);
1143 	bh = NULL;
1144 
1145 	/* correct old leaf */
1146 	if (m) {
1147 		err = ext4_ext_get_access(handle, inode, path + depth);
1148 		if (err)
1149 			goto cleanup;
1150 		le16_add_cpu(&path[depth].p_hdr->eh_entries, -m);
1151 		err = ext4_ext_dirty(handle, inode, path + depth);
1152 		if (err)
1153 			goto cleanup;
1154 
1155 	}
1156 
1157 	/* create intermediate indexes */
1158 	k = depth - at - 1;
1159 	if (unlikely(k < 0)) {
1160 		EXT4_ERROR_INODE(inode, "k %d < 0!", k);
1161 		err = -EFSCORRUPTED;
1162 		goto cleanup;
1163 	}
1164 	if (k)
1165 		ext_debug("create %d intermediate indices\n", k);
1166 	/* insert new index into current index block */
1167 	/* current depth stored in i var */
1168 	i = depth - 1;
1169 	while (k--) {
1170 		oldblock = newblock;
1171 		newblock = ablocks[--a];
1172 		bh = sb_getblk(inode->i_sb, newblock);
1173 		if (unlikely(!bh)) {
1174 			err = -ENOMEM;
1175 			goto cleanup;
1176 		}
1177 		lock_buffer(bh);
1178 
1179 		err = ext4_journal_get_create_access(handle, bh);
1180 		if (err)
1181 			goto cleanup;
1182 
1183 		neh = ext_block_hdr(bh);
1184 		neh->eh_entries = cpu_to_le16(1);
1185 		neh->eh_magic = EXT4_EXT_MAGIC;
1186 		neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
1187 		neh->eh_depth = cpu_to_le16(depth - i);
1188 		fidx = EXT_FIRST_INDEX(neh);
1189 		fidx->ei_block = border;
1190 		ext4_idx_store_pblock(fidx, oldblock);
1191 
1192 		ext_debug("int.index at %d (block %llu): %u -> %llu\n",
1193 				i, newblock, le32_to_cpu(border), oldblock);
1194 
1195 		/* move remainder of path[i] to the new index block */
1196 		if (unlikely(EXT_MAX_INDEX(path[i].p_hdr) !=
1197 					EXT_LAST_INDEX(path[i].p_hdr))) {
1198 			EXT4_ERROR_INODE(inode,
1199 					 "EXT_MAX_INDEX != EXT_LAST_INDEX ee_block %d!",
1200 					 le32_to_cpu(path[i].p_ext->ee_block));
1201 			err = -EFSCORRUPTED;
1202 			goto cleanup;
1203 		}
1204 		/* start copy indexes */
1205 		m = EXT_MAX_INDEX(path[i].p_hdr) - path[i].p_idx++;
1206 		ext_debug("cur 0x%p, last 0x%p\n", path[i].p_idx,
1207 				EXT_MAX_INDEX(path[i].p_hdr));
1208 		ext4_ext_show_move(inode, path, newblock, i);
1209 		if (m) {
1210 			memmove(++fidx, path[i].p_idx,
1211 				sizeof(struct ext4_extent_idx) * m);
1212 			le16_add_cpu(&neh->eh_entries, m);
1213 		}
1214 		ext4_extent_block_csum_set(inode, neh);
1215 		set_buffer_uptodate(bh);
1216 		unlock_buffer(bh);
1217 
1218 		err = ext4_handle_dirty_metadata(handle, inode, bh);
1219 		if (err)
1220 			goto cleanup;
1221 		brelse(bh);
1222 		bh = NULL;
1223 
1224 		/* correct old index */
1225 		if (m) {
1226 			err = ext4_ext_get_access(handle, inode, path + i);
1227 			if (err)
1228 				goto cleanup;
1229 			le16_add_cpu(&path[i].p_hdr->eh_entries, -m);
1230 			err = ext4_ext_dirty(handle, inode, path + i);
1231 			if (err)
1232 				goto cleanup;
1233 		}
1234 
1235 		i--;
1236 	}
1237 
1238 	/* insert new index */
1239 	err = ext4_ext_insert_index(handle, inode, path + at,
1240 				    le32_to_cpu(border), newblock);
1241 
1242 cleanup:
1243 	if (bh) {
1244 		if (buffer_locked(bh))
1245 			unlock_buffer(bh);
1246 		brelse(bh);
1247 	}
1248 
1249 	if (err) {
1250 		/* free all allocated blocks in error case */
1251 		for (i = 0; i < depth; i++) {
1252 			if (!ablocks[i])
1253 				continue;
1254 			ext4_free_blocks(handle, inode, NULL, ablocks[i], 1,
1255 					 EXT4_FREE_BLOCKS_METADATA);
1256 		}
1257 	}
1258 	kfree(ablocks);
1259 
1260 	return err;
1261 }
1262 
1263 /*
1264  * ext4_ext_grow_indepth:
1265  * implements tree growing procedure:
1266  * - allocates new block
1267  * - moves top-level data (index block or leaf) into the new block
1268  * - initializes new top-level, creating index that points to the
1269  *   just created block
1270  */
1271 static int ext4_ext_grow_indepth(handle_t *handle, struct inode *inode,
1272 				 unsigned int flags)
1273 {
1274 	struct ext4_extent_header *neh;
1275 	struct buffer_head *bh;
1276 	ext4_fsblk_t newblock, goal = 0;
1277 	struct ext4_super_block *es = EXT4_SB(inode->i_sb)->s_es;
1278 	int err = 0;
1279 
1280 	/* Try to prepend new index to old one */
1281 	if (ext_depth(inode))
1282 		goal = ext4_idx_pblock(EXT_FIRST_INDEX(ext_inode_hdr(inode)));
1283 	if (goal > le32_to_cpu(es->s_first_data_block)) {
1284 		flags |= EXT4_MB_HINT_TRY_GOAL;
1285 		goal--;
1286 	} else
1287 		goal = ext4_inode_to_goal_block(inode);
1288 	newblock = ext4_new_meta_blocks(handle, inode, goal, flags,
1289 					NULL, &err);
1290 	if (newblock == 0)
1291 		return err;
1292 
1293 	bh = sb_getblk_gfp(inode->i_sb, newblock, __GFP_MOVABLE | GFP_NOFS);
1294 	if (unlikely(!bh))
1295 		return -ENOMEM;
1296 	lock_buffer(bh);
1297 
1298 	err = ext4_journal_get_create_access(handle, bh);
1299 	if (err) {
1300 		unlock_buffer(bh);
1301 		goto out;
1302 	}
1303 
1304 	/* move top-level index/leaf into new block */
1305 	memmove(bh->b_data, EXT4_I(inode)->i_data,
1306 		sizeof(EXT4_I(inode)->i_data));
1307 
1308 	/* set size of new block */
1309 	neh = ext_block_hdr(bh);
1310 	/* old root could have indexes or leaves
1311 	 * so calculate e_max right way */
1312 	if (ext_depth(inode))
1313 		neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
1314 	else
1315 		neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
1316 	neh->eh_magic = EXT4_EXT_MAGIC;
1317 	ext4_extent_block_csum_set(inode, neh);
1318 	set_buffer_uptodate(bh);
1319 	unlock_buffer(bh);
1320 
1321 	err = ext4_handle_dirty_metadata(handle, inode, bh);
1322 	if (err)
1323 		goto out;
1324 
1325 	/* Update top-level index: num,max,pointer */
1326 	neh = ext_inode_hdr(inode);
1327 	neh->eh_entries = cpu_to_le16(1);
1328 	ext4_idx_store_pblock(EXT_FIRST_INDEX(neh), newblock);
1329 	if (neh->eh_depth == 0) {
1330 		/* Root extent block becomes index block */
1331 		neh->eh_max = cpu_to_le16(ext4_ext_space_root_idx(inode, 0));
1332 		EXT_FIRST_INDEX(neh)->ei_block =
1333 			EXT_FIRST_EXTENT(neh)->ee_block;
1334 	}
1335 	ext_debug("new root: num %d(%d), lblock %d, ptr %llu\n",
1336 		  le16_to_cpu(neh->eh_entries), le16_to_cpu(neh->eh_max),
1337 		  le32_to_cpu(EXT_FIRST_INDEX(neh)->ei_block),
1338 		  ext4_idx_pblock(EXT_FIRST_INDEX(neh)));
1339 
1340 	le16_add_cpu(&neh->eh_depth, 1);
1341 	ext4_mark_inode_dirty(handle, inode);
1342 out:
1343 	brelse(bh);
1344 
1345 	return err;
1346 }
1347 
1348 /*
1349  * ext4_ext_create_new_leaf:
1350  * finds empty index and adds new leaf.
1351  * if no free index is found, then it requests in-depth growing.
1352  */
1353 static int ext4_ext_create_new_leaf(handle_t *handle, struct inode *inode,
1354 				    unsigned int mb_flags,
1355 				    unsigned int gb_flags,
1356 				    struct ext4_ext_path **ppath,
1357 				    struct ext4_extent *newext)
1358 {
1359 	struct ext4_ext_path *path = *ppath;
1360 	struct ext4_ext_path *curp;
1361 	int depth, i, err = 0;
1362 
1363 repeat:
1364 	i = depth = ext_depth(inode);
1365 
1366 	/* walk up to the tree and look for free index entry */
1367 	curp = path + depth;
1368 	while (i > 0 && !EXT_HAS_FREE_INDEX(curp)) {
1369 		i--;
1370 		curp--;
1371 	}
1372 
1373 	/* we use already allocated block for index block,
1374 	 * so subsequent data blocks should be contiguous */
1375 	if (EXT_HAS_FREE_INDEX(curp)) {
1376 		/* if we found index with free entry, then use that
1377 		 * entry: create all needed subtree and add new leaf */
1378 		err = ext4_ext_split(handle, inode, mb_flags, path, newext, i);
1379 		if (err)
1380 			goto out;
1381 
1382 		/* refill path */
1383 		path = ext4_find_extent(inode,
1384 				    (ext4_lblk_t)le32_to_cpu(newext->ee_block),
1385 				    ppath, gb_flags);
1386 		if (IS_ERR(path))
1387 			err = PTR_ERR(path);
1388 	} else {
1389 		/* tree is full, time to grow in depth */
1390 		err = ext4_ext_grow_indepth(handle, inode, mb_flags);
1391 		if (err)
1392 			goto out;
1393 
1394 		/* refill path */
1395 		path = ext4_find_extent(inode,
1396 				   (ext4_lblk_t)le32_to_cpu(newext->ee_block),
1397 				    ppath, gb_flags);
1398 		if (IS_ERR(path)) {
1399 			err = PTR_ERR(path);
1400 			goto out;
1401 		}
1402 
1403 		/*
1404 		 * only first (depth 0 -> 1) produces free space;
1405 		 * in all other cases we have to split the grown tree
1406 		 */
1407 		depth = ext_depth(inode);
1408 		if (path[depth].p_hdr->eh_entries == path[depth].p_hdr->eh_max) {
1409 			/* now we need to split */
1410 			goto repeat;
1411 		}
1412 	}
1413 
1414 out:
1415 	return err;
1416 }
1417 
1418 /*
1419  * search the closest allocated block to the left for *logical
1420  * and returns it at @logical + it's physical address at @phys
1421  * if *logical is the smallest allocated block, the function
1422  * returns 0 at @phys
1423  * return value contains 0 (success) or error code
1424  */
1425 static int ext4_ext_search_left(struct inode *inode,
1426 				struct ext4_ext_path *path,
1427 				ext4_lblk_t *logical, ext4_fsblk_t *phys)
1428 {
1429 	struct ext4_extent_idx *ix;
1430 	struct ext4_extent *ex;
1431 	int depth, ee_len;
1432 
1433 	if (unlikely(path == NULL)) {
1434 		EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
1435 		return -EFSCORRUPTED;
1436 	}
1437 	depth = path->p_depth;
1438 	*phys = 0;
1439 
1440 	if (depth == 0 && path->p_ext == NULL)
1441 		return 0;
1442 
1443 	/* usually extent in the path covers blocks smaller
1444 	 * then *logical, but it can be that extent is the
1445 	 * first one in the file */
1446 
1447 	ex = path[depth].p_ext;
1448 	ee_len = ext4_ext_get_actual_len(ex);
1449 	if (*logical < le32_to_cpu(ex->ee_block)) {
1450 		if (unlikely(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex)) {
1451 			EXT4_ERROR_INODE(inode,
1452 					 "EXT_FIRST_EXTENT != ex *logical %d ee_block %d!",
1453 					 *logical, le32_to_cpu(ex->ee_block));
1454 			return -EFSCORRUPTED;
1455 		}
1456 		while (--depth >= 0) {
1457 			ix = path[depth].p_idx;
1458 			if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
1459 				EXT4_ERROR_INODE(inode,
1460 				  "ix (%d) != EXT_FIRST_INDEX (%d) (depth %d)!",
1461 				  ix != NULL ? le32_to_cpu(ix->ei_block) : 0,
1462 				  EXT_FIRST_INDEX(path[depth].p_hdr) != NULL ?
1463 		le32_to_cpu(EXT_FIRST_INDEX(path[depth].p_hdr)->ei_block) : 0,
1464 				  depth);
1465 				return -EFSCORRUPTED;
1466 			}
1467 		}
1468 		return 0;
1469 	}
1470 
1471 	if (unlikely(*logical < (le32_to_cpu(ex->ee_block) + ee_len))) {
1472 		EXT4_ERROR_INODE(inode,
1473 				 "logical %d < ee_block %d + ee_len %d!",
1474 				 *logical, le32_to_cpu(ex->ee_block), ee_len);
1475 		return -EFSCORRUPTED;
1476 	}
1477 
1478 	*logical = le32_to_cpu(ex->ee_block) + ee_len - 1;
1479 	*phys = ext4_ext_pblock(ex) + ee_len - 1;
1480 	return 0;
1481 }
1482 
1483 /*
1484  * search the closest allocated block to the right for *logical
1485  * and returns it at @logical + it's physical address at @phys
1486  * if *logical is the largest allocated block, the function
1487  * returns 0 at @phys
1488  * return value contains 0 (success) or error code
1489  */
1490 static int ext4_ext_search_right(struct inode *inode,
1491 				 struct ext4_ext_path *path,
1492 				 ext4_lblk_t *logical, ext4_fsblk_t *phys,
1493 				 struct ext4_extent **ret_ex)
1494 {
1495 	struct buffer_head *bh = NULL;
1496 	struct ext4_extent_header *eh;
1497 	struct ext4_extent_idx *ix;
1498 	struct ext4_extent *ex;
1499 	ext4_fsblk_t block;
1500 	int depth;	/* Note, NOT eh_depth; depth from top of tree */
1501 	int ee_len;
1502 
1503 	if (unlikely(path == NULL)) {
1504 		EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
1505 		return -EFSCORRUPTED;
1506 	}
1507 	depth = path->p_depth;
1508 	*phys = 0;
1509 
1510 	if (depth == 0 && path->p_ext == NULL)
1511 		return 0;
1512 
1513 	/* usually extent in the path covers blocks smaller
1514 	 * then *logical, but it can be that extent is the
1515 	 * first one in the file */
1516 
1517 	ex = path[depth].p_ext;
1518 	ee_len = ext4_ext_get_actual_len(ex);
1519 	if (*logical < le32_to_cpu(ex->ee_block)) {
1520 		if (unlikely(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex)) {
1521 			EXT4_ERROR_INODE(inode,
1522 					 "first_extent(path[%d].p_hdr) != ex",
1523 					 depth);
1524 			return -EFSCORRUPTED;
1525 		}
1526 		while (--depth >= 0) {
1527 			ix = path[depth].p_idx;
1528 			if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
1529 				EXT4_ERROR_INODE(inode,
1530 						 "ix != EXT_FIRST_INDEX *logical %d!",
1531 						 *logical);
1532 				return -EFSCORRUPTED;
1533 			}
1534 		}
1535 		goto found_extent;
1536 	}
1537 
1538 	if (unlikely(*logical < (le32_to_cpu(ex->ee_block) + ee_len))) {
1539 		EXT4_ERROR_INODE(inode,
1540 				 "logical %d < ee_block %d + ee_len %d!",
1541 				 *logical, le32_to_cpu(ex->ee_block), ee_len);
1542 		return -EFSCORRUPTED;
1543 	}
1544 
1545 	if (ex != EXT_LAST_EXTENT(path[depth].p_hdr)) {
1546 		/* next allocated block in this leaf */
1547 		ex++;
1548 		goto found_extent;
1549 	}
1550 
1551 	/* go up and search for index to the right */
1552 	while (--depth >= 0) {
1553 		ix = path[depth].p_idx;
1554 		if (ix != EXT_LAST_INDEX(path[depth].p_hdr))
1555 			goto got_index;
1556 	}
1557 
1558 	/* we've gone up to the root and found no index to the right */
1559 	return 0;
1560 
1561 got_index:
1562 	/* we've found index to the right, let's
1563 	 * follow it and find the closest allocated
1564 	 * block to the right */
1565 	ix++;
1566 	block = ext4_idx_pblock(ix);
1567 	while (++depth < path->p_depth) {
1568 		/* subtract from p_depth to get proper eh_depth */
1569 		bh = read_extent_tree_block(inode, block,
1570 					    path->p_depth - depth, 0);
1571 		if (IS_ERR(bh))
1572 			return PTR_ERR(bh);
1573 		eh = ext_block_hdr(bh);
1574 		ix = EXT_FIRST_INDEX(eh);
1575 		block = ext4_idx_pblock(ix);
1576 		put_bh(bh);
1577 	}
1578 
1579 	bh = read_extent_tree_block(inode, block, path->p_depth - depth, 0);
1580 	if (IS_ERR(bh))
1581 		return PTR_ERR(bh);
1582 	eh = ext_block_hdr(bh);
1583 	ex = EXT_FIRST_EXTENT(eh);
1584 found_extent:
1585 	*logical = le32_to_cpu(ex->ee_block);
1586 	*phys = ext4_ext_pblock(ex);
1587 	*ret_ex = ex;
1588 	if (bh)
1589 		put_bh(bh);
1590 	return 0;
1591 }
1592 
1593 /*
1594  * ext4_ext_next_allocated_block:
1595  * returns allocated block in subsequent extent or EXT_MAX_BLOCKS.
1596  * NOTE: it considers block number from index entry as
1597  * allocated block. Thus, index entries have to be consistent
1598  * with leaves.
1599  */
1600 ext4_lblk_t
1601 ext4_ext_next_allocated_block(struct ext4_ext_path *path)
1602 {
1603 	int depth;
1604 
1605 	BUG_ON(path == NULL);
1606 	depth = path->p_depth;
1607 
1608 	if (depth == 0 && path->p_ext == NULL)
1609 		return EXT_MAX_BLOCKS;
1610 
1611 	while (depth >= 0) {
1612 		if (depth == path->p_depth) {
1613 			/* leaf */
1614 			if (path[depth].p_ext &&
1615 				path[depth].p_ext !=
1616 					EXT_LAST_EXTENT(path[depth].p_hdr))
1617 			  return le32_to_cpu(path[depth].p_ext[1].ee_block);
1618 		} else {
1619 			/* index */
1620 			if (path[depth].p_idx !=
1621 					EXT_LAST_INDEX(path[depth].p_hdr))
1622 			  return le32_to_cpu(path[depth].p_idx[1].ei_block);
1623 		}
1624 		depth--;
1625 	}
1626 
1627 	return EXT_MAX_BLOCKS;
1628 }
1629 
1630 /*
1631  * ext4_ext_next_leaf_block:
1632  * returns first allocated block from next leaf or EXT_MAX_BLOCKS
1633  */
1634 static ext4_lblk_t ext4_ext_next_leaf_block(struct ext4_ext_path *path)
1635 {
1636 	int depth;
1637 
1638 	BUG_ON(path == NULL);
1639 	depth = path->p_depth;
1640 
1641 	/* zero-tree has no leaf blocks at all */
1642 	if (depth == 0)
1643 		return EXT_MAX_BLOCKS;
1644 
1645 	/* go to index block */
1646 	depth--;
1647 
1648 	while (depth >= 0) {
1649 		if (path[depth].p_idx !=
1650 				EXT_LAST_INDEX(path[depth].p_hdr))
1651 			return (ext4_lblk_t)
1652 				le32_to_cpu(path[depth].p_idx[1].ei_block);
1653 		depth--;
1654 	}
1655 
1656 	return EXT_MAX_BLOCKS;
1657 }
1658 
1659 /*
1660  * ext4_ext_correct_indexes:
1661  * if leaf gets modified and modified extent is first in the leaf,
1662  * then we have to correct all indexes above.
1663  * TODO: do we need to correct tree in all cases?
1664  */
1665 static int ext4_ext_correct_indexes(handle_t *handle, struct inode *inode,
1666 				struct ext4_ext_path *path)
1667 {
1668 	struct ext4_extent_header *eh;
1669 	int depth = ext_depth(inode);
1670 	struct ext4_extent *ex;
1671 	__le32 border;
1672 	int k, err = 0;
1673 
1674 	eh = path[depth].p_hdr;
1675 	ex = path[depth].p_ext;
1676 
1677 	if (unlikely(ex == NULL || eh == NULL)) {
1678 		EXT4_ERROR_INODE(inode,
1679 				 "ex %p == NULL or eh %p == NULL", ex, eh);
1680 		return -EFSCORRUPTED;
1681 	}
1682 
1683 	if (depth == 0) {
1684 		/* there is no tree at all */
1685 		return 0;
1686 	}
1687 
1688 	if (ex != EXT_FIRST_EXTENT(eh)) {
1689 		/* we correct tree if first leaf got modified only */
1690 		return 0;
1691 	}
1692 
1693 	/*
1694 	 * TODO: we need correction if border is smaller than current one
1695 	 */
1696 	k = depth - 1;
1697 	border = path[depth].p_ext->ee_block;
1698 	err = ext4_ext_get_access(handle, inode, path + k);
1699 	if (err)
1700 		return err;
1701 	path[k].p_idx->ei_block = border;
1702 	err = ext4_ext_dirty(handle, inode, path + k);
1703 	if (err)
1704 		return err;
1705 
1706 	while (k--) {
1707 		/* change all left-side indexes */
1708 		if (path[k+1].p_idx != EXT_FIRST_INDEX(path[k+1].p_hdr))
1709 			break;
1710 		err = ext4_ext_get_access(handle, inode, path + k);
1711 		if (err)
1712 			break;
1713 		path[k].p_idx->ei_block = border;
1714 		err = ext4_ext_dirty(handle, inode, path + k);
1715 		if (err)
1716 			break;
1717 	}
1718 
1719 	return err;
1720 }
1721 
1722 int
1723 ext4_can_extents_be_merged(struct inode *inode, struct ext4_extent *ex1,
1724 				struct ext4_extent *ex2)
1725 {
1726 	unsigned short ext1_ee_len, ext2_ee_len;
1727 
1728 	if (ext4_ext_is_unwritten(ex1) != ext4_ext_is_unwritten(ex2))
1729 		return 0;
1730 
1731 	ext1_ee_len = ext4_ext_get_actual_len(ex1);
1732 	ext2_ee_len = ext4_ext_get_actual_len(ex2);
1733 
1734 	if (le32_to_cpu(ex1->ee_block) + ext1_ee_len !=
1735 			le32_to_cpu(ex2->ee_block))
1736 		return 0;
1737 
1738 	/*
1739 	 * To allow future support for preallocated extents to be added
1740 	 * as an RO_COMPAT feature, refuse to merge to extents if
1741 	 * this can result in the top bit of ee_len being set.
1742 	 */
1743 	if (ext1_ee_len + ext2_ee_len > EXT_INIT_MAX_LEN)
1744 		return 0;
1745 	/*
1746 	 * The check for IO to unwritten extent is somewhat racy as we
1747 	 * increment i_unwritten / set EXT4_STATE_DIO_UNWRITTEN only after
1748 	 * dropping i_data_sem. But reserved blocks should save us in that
1749 	 * case.
1750 	 */
1751 	if (ext4_ext_is_unwritten(ex1) &&
1752 	    (ext4_test_inode_state(inode, EXT4_STATE_DIO_UNWRITTEN) ||
1753 	     atomic_read(&EXT4_I(inode)->i_unwritten) ||
1754 	     (ext1_ee_len + ext2_ee_len > EXT_UNWRITTEN_MAX_LEN)))
1755 		return 0;
1756 #ifdef AGGRESSIVE_TEST
1757 	if (ext1_ee_len >= 4)
1758 		return 0;
1759 #endif
1760 
1761 	if (ext4_ext_pblock(ex1) + ext1_ee_len == ext4_ext_pblock(ex2))
1762 		return 1;
1763 	return 0;
1764 }
1765 
1766 /*
1767  * This function tries to merge the "ex" extent to the next extent in the tree.
1768  * It always tries to merge towards right. If you want to merge towards
1769  * left, pass "ex - 1" as argument instead of "ex".
1770  * Returns 0 if the extents (ex and ex+1) were _not_ merged and returns
1771  * 1 if they got merged.
1772  */
1773 static int ext4_ext_try_to_merge_right(struct inode *inode,
1774 				 struct ext4_ext_path *path,
1775 				 struct ext4_extent *ex)
1776 {
1777 	struct ext4_extent_header *eh;
1778 	unsigned int depth, len;
1779 	int merge_done = 0, unwritten;
1780 
1781 	depth = ext_depth(inode);
1782 	BUG_ON(path[depth].p_hdr == NULL);
1783 	eh = path[depth].p_hdr;
1784 
1785 	while (ex < EXT_LAST_EXTENT(eh)) {
1786 		if (!ext4_can_extents_be_merged(inode, ex, ex + 1))
1787 			break;
1788 		/* merge with next extent! */
1789 		unwritten = ext4_ext_is_unwritten(ex);
1790 		ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
1791 				+ ext4_ext_get_actual_len(ex + 1));
1792 		if (unwritten)
1793 			ext4_ext_mark_unwritten(ex);
1794 
1795 		if (ex + 1 < EXT_LAST_EXTENT(eh)) {
1796 			len = (EXT_LAST_EXTENT(eh) - ex - 1)
1797 				* sizeof(struct ext4_extent);
1798 			memmove(ex + 1, ex + 2, len);
1799 		}
1800 		le16_add_cpu(&eh->eh_entries, -1);
1801 		merge_done = 1;
1802 		WARN_ON(eh->eh_entries == 0);
1803 		if (!eh->eh_entries)
1804 			EXT4_ERROR_INODE(inode, "eh->eh_entries = 0!");
1805 	}
1806 
1807 	return merge_done;
1808 }
1809 
1810 /*
1811  * This function does a very simple check to see if we can collapse
1812  * an extent tree with a single extent tree leaf block into the inode.
1813  */
1814 static void ext4_ext_try_to_merge_up(handle_t *handle,
1815 				     struct inode *inode,
1816 				     struct ext4_ext_path *path)
1817 {
1818 	size_t s;
1819 	unsigned max_root = ext4_ext_space_root(inode, 0);
1820 	ext4_fsblk_t blk;
1821 
1822 	if ((path[0].p_depth != 1) ||
1823 	    (le16_to_cpu(path[0].p_hdr->eh_entries) != 1) ||
1824 	    (le16_to_cpu(path[1].p_hdr->eh_entries) > max_root))
1825 		return;
1826 
1827 	/*
1828 	 * We need to modify the block allocation bitmap and the block
1829 	 * group descriptor to release the extent tree block.  If we
1830 	 * can't get the journal credits, give up.
1831 	 */
1832 	if (ext4_journal_extend(handle, 2))
1833 		return;
1834 
1835 	/*
1836 	 * Copy the extent data up to the inode
1837 	 */
1838 	blk = ext4_idx_pblock(path[0].p_idx);
1839 	s = le16_to_cpu(path[1].p_hdr->eh_entries) *
1840 		sizeof(struct ext4_extent_idx);
1841 	s += sizeof(struct ext4_extent_header);
1842 
1843 	path[1].p_maxdepth = path[0].p_maxdepth;
1844 	memcpy(path[0].p_hdr, path[1].p_hdr, s);
1845 	path[0].p_depth = 0;
1846 	path[0].p_ext = EXT_FIRST_EXTENT(path[0].p_hdr) +
1847 		(path[1].p_ext - EXT_FIRST_EXTENT(path[1].p_hdr));
1848 	path[0].p_hdr->eh_max = cpu_to_le16(max_root);
1849 
1850 	brelse(path[1].p_bh);
1851 	ext4_free_blocks(handle, inode, NULL, blk, 1,
1852 			 EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET);
1853 }
1854 
1855 /*
1856  * This function tries to merge the @ex extent to neighbours in the tree.
1857  * return 1 if merge left else 0.
1858  */
1859 static void ext4_ext_try_to_merge(handle_t *handle,
1860 				  struct inode *inode,
1861 				  struct ext4_ext_path *path,
1862 				  struct ext4_extent *ex) {
1863 	struct ext4_extent_header *eh;
1864 	unsigned int depth;
1865 	int merge_done = 0;
1866 
1867 	depth = ext_depth(inode);
1868 	BUG_ON(path[depth].p_hdr == NULL);
1869 	eh = path[depth].p_hdr;
1870 
1871 	if (ex > EXT_FIRST_EXTENT(eh))
1872 		merge_done = ext4_ext_try_to_merge_right(inode, path, ex - 1);
1873 
1874 	if (!merge_done)
1875 		(void) ext4_ext_try_to_merge_right(inode, path, ex);
1876 
1877 	ext4_ext_try_to_merge_up(handle, inode, path);
1878 }
1879 
1880 /*
1881  * check if a portion of the "newext" extent overlaps with an
1882  * existing extent.
1883  *
1884  * If there is an overlap discovered, it updates the length of the newext
1885  * such that there will be no overlap, and then returns 1.
1886  * If there is no overlap found, it returns 0.
1887  */
1888 static unsigned int ext4_ext_check_overlap(struct ext4_sb_info *sbi,
1889 					   struct inode *inode,
1890 					   struct ext4_extent *newext,
1891 					   struct ext4_ext_path *path)
1892 {
1893 	ext4_lblk_t b1, b2;
1894 	unsigned int depth, len1;
1895 	unsigned int ret = 0;
1896 
1897 	b1 = le32_to_cpu(newext->ee_block);
1898 	len1 = ext4_ext_get_actual_len(newext);
1899 	depth = ext_depth(inode);
1900 	if (!path[depth].p_ext)
1901 		goto out;
1902 	b2 = EXT4_LBLK_CMASK(sbi, le32_to_cpu(path[depth].p_ext->ee_block));
1903 
1904 	/*
1905 	 * get the next allocated block if the extent in the path
1906 	 * is before the requested block(s)
1907 	 */
1908 	if (b2 < b1) {
1909 		b2 = ext4_ext_next_allocated_block(path);
1910 		if (b2 == EXT_MAX_BLOCKS)
1911 			goto out;
1912 		b2 = EXT4_LBLK_CMASK(sbi, b2);
1913 	}
1914 
1915 	/* check for wrap through zero on extent logical start block*/
1916 	if (b1 + len1 < b1) {
1917 		len1 = EXT_MAX_BLOCKS - b1;
1918 		newext->ee_len = cpu_to_le16(len1);
1919 		ret = 1;
1920 	}
1921 
1922 	/* check for overlap */
1923 	if (b1 + len1 > b2) {
1924 		newext->ee_len = cpu_to_le16(b2 - b1);
1925 		ret = 1;
1926 	}
1927 out:
1928 	return ret;
1929 }
1930 
1931 /*
1932  * ext4_ext_insert_extent:
1933  * tries to merge requsted extent into the existing extent or
1934  * inserts requested extent as new one into the tree,
1935  * creating new leaf in the no-space case.
1936  */
1937 int ext4_ext_insert_extent(handle_t *handle, struct inode *inode,
1938 				struct ext4_ext_path **ppath,
1939 				struct ext4_extent *newext, int gb_flags)
1940 {
1941 	struct ext4_ext_path *path = *ppath;
1942 	struct ext4_extent_header *eh;
1943 	struct ext4_extent *ex, *fex;
1944 	struct ext4_extent *nearex; /* nearest extent */
1945 	struct ext4_ext_path *npath = NULL;
1946 	int depth, len, err;
1947 	ext4_lblk_t next;
1948 	int mb_flags = 0, unwritten;
1949 
1950 	if (gb_flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
1951 		mb_flags |= EXT4_MB_DELALLOC_RESERVED;
1952 	if (unlikely(ext4_ext_get_actual_len(newext) == 0)) {
1953 		EXT4_ERROR_INODE(inode, "ext4_ext_get_actual_len(newext) == 0");
1954 		return -EFSCORRUPTED;
1955 	}
1956 	depth = ext_depth(inode);
1957 	ex = path[depth].p_ext;
1958 	eh = path[depth].p_hdr;
1959 	if (unlikely(path[depth].p_hdr == NULL)) {
1960 		EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
1961 		return -EFSCORRUPTED;
1962 	}
1963 
1964 	/* try to insert block into found extent and return */
1965 	if (ex && !(gb_flags & EXT4_GET_BLOCKS_PRE_IO)) {
1966 
1967 		/*
1968 		 * Try to see whether we should rather test the extent on
1969 		 * right from ex, or from the left of ex. This is because
1970 		 * ext4_find_extent() can return either extent on the
1971 		 * left, or on the right from the searched position. This
1972 		 * will make merging more effective.
1973 		 */
1974 		if (ex < EXT_LAST_EXTENT(eh) &&
1975 		    (le32_to_cpu(ex->ee_block) +
1976 		    ext4_ext_get_actual_len(ex) <
1977 		    le32_to_cpu(newext->ee_block))) {
1978 			ex += 1;
1979 			goto prepend;
1980 		} else if ((ex > EXT_FIRST_EXTENT(eh)) &&
1981 			   (le32_to_cpu(newext->ee_block) +
1982 			   ext4_ext_get_actual_len(newext) <
1983 			   le32_to_cpu(ex->ee_block)))
1984 			ex -= 1;
1985 
1986 		/* Try to append newex to the ex */
1987 		if (ext4_can_extents_be_merged(inode, ex, newext)) {
1988 			ext_debug("append [%d]%d block to %u:[%d]%d"
1989 				  "(from %llu)\n",
1990 				  ext4_ext_is_unwritten(newext),
1991 				  ext4_ext_get_actual_len(newext),
1992 				  le32_to_cpu(ex->ee_block),
1993 				  ext4_ext_is_unwritten(ex),
1994 				  ext4_ext_get_actual_len(ex),
1995 				  ext4_ext_pblock(ex));
1996 			err = ext4_ext_get_access(handle, inode,
1997 						  path + depth);
1998 			if (err)
1999 				return err;
2000 			unwritten = ext4_ext_is_unwritten(ex);
2001 			ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
2002 					+ ext4_ext_get_actual_len(newext));
2003 			if (unwritten)
2004 				ext4_ext_mark_unwritten(ex);
2005 			eh = path[depth].p_hdr;
2006 			nearex = ex;
2007 			goto merge;
2008 		}
2009 
2010 prepend:
2011 		/* Try to prepend newex to the ex */
2012 		if (ext4_can_extents_be_merged(inode, newext, ex)) {
2013 			ext_debug("prepend %u[%d]%d block to %u:[%d]%d"
2014 				  "(from %llu)\n",
2015 				  le32_to_cpu(newext->ee_block),
2016 				  ext4_ext_is_unwritten(newext),
2017 				  ext4_ext_get_actual_len(newext),
2018 				  le32_to_cpu(ex->ee_block),
2019 				  ext4_ext_is_unwritten(ex),
2020 				  ext4_ext_get_actual_len(ex),
2021 				  ext4_ext_pblock(ex));
2022 			err = ext4_ext_get_access(handle, inode,
2023 						  path + depth);
2024 			if (err)
2025 				return err;
2026 
2027 			unwritten = ext4_ext_is_unwritten(ex);
2028 			ex->ee_block = newext->ee_block;
2029 			ext4_ext_store_pblock(ex, ext4_ext_pblock(newext));
2030 			ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
2031 					+ ext4_ext_get_actual_len(newext));
2032 			if (unwritten)
2033 				ext4_ext_mark_unwritten(ex);
2034 			eh = path[depth].p_hdr;
2035 			nearex = ex;
2036 			goto merge;
2037 		}
2038 	}
2039 
2040 	depth = ext_depth(inode);
2041 	eh = path[depth].p_hdr;
2042 	if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))
2043 		goto has_space;
2044 
2045 	/* probably next leaf has space for us? */
2046 	fex = EXT_LAST_EXTENT(eh);
2047 	next = EXT_MAX_BLOCKS;
2048 	if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block))
2049 		next = ext4_ext_next_leaf_block(path);
2050 	if (next != EXT_MAX_BLOCKS) {
2051 		ext_debug("next leaf block - %u\n", next);
2052 		BUG_ON(npath != NULL);
2053 		npath = ext4_find_extent(inode, next, NULL, 0);
2054 		if (IS_ERR(npath))
2055 			return PTR_ERR(npath);
2056 		BUG_ON(npath->p_depth != path->p_depth);
2057 		eh = npath[depth].p_hdr;
2058 		if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) {
2059 			ext_debug("next leaf isn't full(%d)\n",
2060 				  le16_to_cpu(eh->eh_entries));
2061 			path = npath;
2062 			goto has_space;
2063 		}
2064 		ext_debug("next leaf has no free space(%d,%d)\n",
2065 			  le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
2066 	}
2067 
2068 	/*
2069 	 * There is no free space in the found leaf.
2070 	 * We're gonna add a new leaf in the tree.
2071 	 */
2072 	if (gb_flags & EXT4_GET_BLOCKS_METADATA_NOFAIL)
2073 		mb_flags |= EXT4_MB_USE_RESERVED;
2074 	err = ext4_ext_create_new_leaf(handle, inode, mb_flags, gb_flags,
2075 				       ppath, newext);
2076 	if (err)
2077 		goto cleanup;
2078 	depth = ext_depth(inode);
2079 	eh = path[depth].p_hdr;
2080 
2081 has_space:
2082 	nearex = path[depth].p_ext;
2083 
2084 	err = ext4_ext_get_access(handle, inode, path + depth);
2085 	if (err)
2086 		goto cleanup;
2087 
2088 	if (!nearex) {
2089 		/* there is no extent in this leaf, create first one */
2090 		ext_debug("first extent in the leaf: %u:%llu:[%d]%d\n",
2091 				le32_to_cpu(newext->ee_block),
2092 				ext4_ext_pblock(newext),
2093 				ext4_ext_is_unwritten(newext),
2094 				ext4_ext_get_actual_len(newext));
2095 		nearex = EXT_FIRST_EXTENT(eh);
2096 	} else {
2097 		if (le32_to_cpu(newext->ee_block)
2098 			   > le32_to_cpu(nearex->ee_block)) {
2099 			/* Insert after */
2100 			ext_debug("insert %u:%llu:[%d]%d before: "
2101 					"nearest %p\n",
2102 					le32_to_cpu(newext->ee_block),
2103 					ext4_ext_pblock(newext),
2104 					ext4_ext_is_unwritten(newext),
2105 					ext4_ext_get_actual_len(newext),
2106 					nearex);
2107 			nearex++;
2108 		} else {
2109 			/* Insert before */
2110 			BUG_ON(newext->ee_block == nearex->ee_block);
2111 			ext_debug("insert %u:%llu:[%d]%d after: "
2112 					"nearest %p\n",
2113 					le32_to_cpu(newext->ee_block),
2114 					ext4_ext_pblock(newext),
2115 					ext4_ext_is_unwritten(newext),
2116 					ext4_ext_get_actual_len(newext),
2117 					nearex);
2118 		}
2119 		len = EXT_LAST_EXTENT(eh) - nearex + 1;
2120 		if (len > 0) {
2121 			ext_debug("insert %u:%llu:[%d]%d: "
2122 					"move %d extents from 0x%p to 0x%p\n",
2123 					le32_to_cpu(newext->ee_block),
2124 					ext4_ext_pblock(newext),
2125 					ext4_ext_is_unwritten(newext),
2126 					ext4_ext_get_actual_len(newext),
2127 					len, nearex, nearex + 1);
2128 			memmove(nearex + 1, nearex,
2129 				len * sizeof(struct ext4_extent));
2130 		}
2131 	}
2132 
2133 	le16_add_cpu(&eh->eh_entries, 1);
2134 	path[depth].p_ext = nearex;
2135 	nearex->ee_block = newext->ee_block;
2136 	ext4_ext_store_pblock(nearex, ext4_ext_pblock(newext));
2137 	nearex->ee_len = newext->ee_len;
2138 
2139 merge:
2140 	/* try to merge extents */
2141 	if (!(gb_flags & EXT4_GET_BLOCKS_PRE_IO))
2142 		ext4_ext_try_to_merge(handle, inode, path, nearex);
2143 
2144 
2145 	/* time to correct all indexes above */
2146 	err = ext4_ext_correct_indexes(handle, inode, path);
2147 	if (err)
2148 		goto cleanup;
2149 
2150 	err = ext4_ext_dirty(handle, inode, path + path->p_depth);
2151 
2152 cleanup:
2153 	ext4_ext_drop_refs(npath);
2154 	kfree(npath);
2155 	return err;
2156 }
2157 
2158 static int ext4_fill_fiemap_extents(struct inode *inode,
2159 				    ext4_lblk_t block, ext4_lblk_t num,
2160 				    struct fiemap_extent_info *fieinfo)
2161 {
2162 	struct ext4_ext_path *path = NULL;
2163 	struct ext4_extent *ex;
2164 	struct extent_status es;
2165 	ext4_lblk_t next, next_del, start = 0, end = 0;
2166 	ext4_lblk_t last = block + num;
2167 	int exists, depth = 0, err = 0;
2168 	unsigned int flags = 0;
2169 	unsigned char blksize_bits = inode->i_sb->s_blocksize_bits;
2170 
2171 	while (block < last && block != EXT_MAX_BLOCKS) {
2172 		num = last - block;
2173 		/* find extent for this block */
2174 		down_read(&EXT4_I(inode)->i_data_sem);
2175 
2176 		path = ext4_find_extent(inode, block, &path, 0);
2177 		if (IS_ERR(path)) {
2178 			up_read(&EXT4_I(inode)->i_data_sem);
2179 			err = PTR_ERR(path);
2180 			path = NULL;
2181 			break;
2182 		}
2183 
2184 		depth = ext_depth(inode);
2185 		if (unlikely(path[depth].p_hdr == NULL)) {
2186 			up_read(&EXT4_I(inode)->i_data_sem);
2187 			EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
2188 			err = -EFSCORRUPTED;
2189 			break;
2190 		}
2191 		ex = path[depth].p_ext;
2192 		next = ext4_ext_next_allocated_block(path);
2193 
2194 		flags = 0;
2195 		exists = 0;
2196 		if (!ex) {
2197 			/* there is no extent yet, so try to allocate
2198 			 * all requested space */
2199 			start = block;
2200 			end = block + num;
2201 		} else if (le32_to_cpu(ex->ee_block) > block) {
2202 			/* need to allocate space before found extent */
2203 			start = block;
2204 			end = le32_to_cpu(ex->ee_block);
2205 			if (block + num < end)
2206 				end = block + num;
2207 		} else if (block >= le32_to_cpu(ex->ee_block)
2208 					+ ext4_ext_get_actual_len(ex)) {
2209 			/* need to allocate space after found extent */
2210 			start = block;
2211 			end = block + num;
2212 			if (end >= next)
2213 				end = next;
2214 		} else if (block >= le32_to_cpu(ex->ee_block)) {
2215 			/*
2216 			 * some part of requested space is covered
2217 			 * by found extent
2218 			 */
2219 			start = block;
2220 			end = le32_to_cpu(ex->ee_block)
2221 				+ ext4_ext_get_actual_len(ex);
2222 			if (block + num < end)
2223 				end = block + num;
2224 			exists = 1;
2225 		} else {
2226 			BUG();
2227 		}
2228 		BUG_ON(end <= start);
2229 
2230 		if (!exists) {
2231 			es.es_lblk = start;
2232 			es.es_len = end - start;
2233 			es.es_pblk = 0;
2234 		} else {
2235 			es.es_lblk = le32_to_cpu(ex->ee_block);
2236 			es.es_len = ext4_ext_get_actual_len(ex);
2237 			es.es_pblk = ext4_ext_pblock(ex);
2238 			if (ext4_ext_is_unwritten(ex))
2239 				flags |= FIEMAP_EXTENT_UNWRITTEN;
2240 		}
2241 
2242 		/*
2243 		 * Find delayed extent and update es accordingly. We call
2244 		 * it even in !exists case to find out whether es is the
2245 		 * last existing extent or not.
2246 		 */
2247 		next_del = ext4_find_delayed_extent(inode, &es);
2248 		if (!exists && next_del) {
2249 			exists = 1;
2250 			flags |= (FIEMAP_EXTENT_DELALLOC |
2251 				  FIEMAP_EXTENT_UNKNOWN);
2252 		}
2253 		up_read(&EXT4_I(inode)->i_data_sem);
2254 
2255 		if (unlikely(es.es_len == 0)) {
2256 			EXT4_ERROR_INODE(inode, "es.es_len == 0");
2257 			err = -EFSCORRUPTED;
2258 			break;
2259 		}
2260 
2261 		/*
2262 		 * This is possible iff next == next_del == EXT_MAX_BLOCKS.
2263 		 * we need to check next == EXT_MAX_BLOCKS because it is
2264 		 * possible that an extent is with unwritten and delayed
2265 		 * status due to when an extent is delayed allocated and
2266 		 * is allocated by fallocate status tree will track both of
2267 		 * them in a extent.
2268 		 *
2269 		 * So we could return a unwritten and delayed extent, and
2270 		 * its block is equal to 'next'.
2271 		 */
2272 		if (next == next_del && next == EXT_MAX_BLOCKS) {
2273 			flags |= FIEMAP_EXTENT_LAST;
2274 			if (unlikely(next_del != EXT_MAX_BLOCKS ||
2275 				     next != EXT_MAX_BLOCKS)) {
2276 				EXT4_ERROR_INODE(inode,
2277 						 "next extent == %u, next "
2278 						 "delalloc extent = %u",
2279 						 next, next_del);
2280 				err = -EFSCORRUPTED;
2281 				break;
2282 			}
2283 		}
2284 
2285 		if (exists) {
2286 			err = fiemap_fill_next_extent(fieinfo,
2287 				(__u64)es.es_lblk << blksize_bits,
2288 				(__u64)es.es_pblk << blksize_bits,
2289 				(__u64)es.es_len << blksize_bits,
2290 				flags);
2291 			if (err < 0)
2292 				break;
2293 			if (err == 1) {
2294 				err = 0;
2295 				break;
2296 			}
2297 		}
2298 
2299 		block = es.es_lblk + es.es_len;
2300 	}
2301 
2302 	ext4_ext_drop_refs(path);
2303 	kfree(path);
2304 	return err;
2305 }
2306 
2307 /*
2308  * ext4_ext_determine_hole - determine hole around given block
2309  * @inode:	inode we lookup in
2310  * @path:	path in extent tree to @lblk
2311  * @lblk:	pointer to logical block around which we want to determine hole
2312  *
2313  * Determine hole length (and start if easily possible) around given logical
2314  * block. We don't try too hard to find the beginning of the hole but @path
2315  * actually points to extent before @lblk, we provide it.
2316  *
2317  * The function returns the length of a hole starting at @lblk. We update @lblk
2318  * to the beginning of the hole if we managed to find it.
2319  */
2320 static ext4_lblk_t ext4_ext_determine_hole(struct inode *inode,
2321 					   struct ext4_ext_path *path,
2322 					   ext4_lblk_t *lblk)
2323 {
2324 	int depth = ext_depth(inode);
2325 	struct ext4_extent *ex;
2326 	ext4_lblk_t len;
2327 
2328 	ex = path[depth].p_ext;
2329 	if (ex == NULL) {
2330 		/* there is no extent yet, so gap is [0;-] */
2331 		*lblk = 0;
2332 		len = EXT_MAX_BLOCKS;
2333 	} else if (*lblk < le32_to_cpu(ex->ee_block)) {
2334 		len = le32_to_cpu(ex->ee_block) - *lblk;
2335 	} else if (*lblk >= le32_to_cpu(ex->ee_block)
2336 			+ ext4_ext_get_actual_len(ex)) {
2337 		ext4_lblk_t next;
2338 
2339 		*lblk = le32_to_cpu(ex->ee_block) + ext4_ext_get_actual_len(ex);
2340 		next = ext4_ext_next_allocated_block(path);
2341 		BUG_ON(next == *lblk);
2342 		len = next - *lblk;
2343 	} else {
2344 		BUG();
2345 	}
2346 	return len;
2347 }
2348 
2349 /*
2350  * ext4_ext_put_gap_in_cache:
2351  * calculate boundaries of the gap that the requested block fits into
2352  * and cache this gap
2353  */
2354 static void
2355 ext4_ext_put_gap_in_cache(struct inode *inode, ext4_lblk_t hole_start,
2356 			  ext4_lblk_t hole_len)
2357 {
2358 	struct extent_status es;
2359 
2360 	ext4_es_find_delayed_extent_range(inode, hole_start,
2361 					  hole_start + hole_len - 1, &es);
2362 	if (es.es_len) {
2363 		/* There's delayed extent containing lblock? */
2364 		if (es.es_lblk <= hole_start)
2365 			return;
2366 		hole_len = min(es.es_lblk - hole_start, hole_len);
2367 	}
2368 	ext_debug(" -> %u:%u\n", hole_start, hole_len);
2369 	ext4_es_insert_extent(inode, hole_start, hole_len, ~0,
2370 			      EXTENT_STATUS_HOLE);
2371 }
2372 
2373 /*
2374  * ext4_ext_rm_idx:
2375  * removes index from the index block.
2376  */
2377 static int ext4_ext_rm_idx(handle_t *handle, struct inode *inode,
2378 			struct ext4_ext_path *path, int depth)
2379 {
2380 	int err;
2381 	ext4_fsblk_t leaf;
2382 
2383 	/* free index block */
2384 	depth--;
2385 	path = path + depth;
2386 	leaf = ext4_idx_pblock(path->p_idx);
2387 	if (unlikely(path->p_hdr->eh_entries == 0)) {
2388 		EXT4_ERROR_INODE(inode, "path->p_hdr->eh_entries == 0");
2389 		return -EFSCORRUPTED;
2390 	}
2391 	err = ext4_ext_get_access(handle, inode, path);
2392 	if (err)
2393 		return err;
2394 
2395 	if (path->p_idx != EXT_LAST_INDEX(path->p_hdr)) {
2396 		int len = EXT_LAST_INDEX(path->p_hdr) - path->p_idx;
2397 		len *= sizeof(struct ext4_extent_idx);
2398 		memmove(path->p_idx, path->p_idx + 1, len);
2399 	}
2400 
2401 	le16_add_cpu(&path->p_hdr->eh_entries, -1);
2402 	err = ext4_ext_dirty(handle, inode, path);
2403 	if (err)
2404 		return err;
2405 	ext_debug("index is empty, remove it, free block %llu\n", leaf);
2406 	trace_ext4_ext_rm_idx(inode, leaf);
2407 
2408 	ext4_free_blocks(handle, inode, NULL, leaf, 1,
2409 			 EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET);
2410 
2411 	while (--depth >= 0) {
2412 		if (path->p_idx != EXT_FIRST_INDEX(path->p_hdr))
2413 			break;
2414 		path--;
2415 		err = ext4_ext_get_access(handle, inode, path);
2416 		if (err)
2417 			break;
2418 		path->p_idx->ei_block = (path+1)->p_idx->ei_block;
2419 		err = ext4_ext_dirty(handle, inode, path);
2420 		if (err)
2421 			break;
2422 	}
2423 	return err;
2424 }
2425 
2426 /*
2427  * ext4_ext_calc_credits_for_single_extent:
2428  * This routine returns max. credits that needed to insert an extent
2429  * to the extent tree.
2430  * When pass the actual path, the caller should calculate credits
2431  * under i_data_sem.
2432  */
2433 int ext4_ext_calc_credits_for_single_extent(struct inode *inode, int nrblocks,
2434 						struct ext4_ext_path *path)
2435 {
2436 	if (path) {
2437 		int depth = ext_depth(inode);
2438 		int ret = 0;
2439 
2440 		/* probably there is space in leaf? */
2441 		if (le16_to_cpu(path[depth].p_hdr->eh_entries)
2442 				< le16_to_cpu(path[depth].p_hdr->eh_max)) {
2443 
2444 			/*
2445 			 *  There are some space in the leaf tree, no
2446 			 *  need to account for leaf block credit
2447 			 *
2448 			 *  bitmaps and block group descriptor blocks
2449 			 *  and other metadata blocks still need to be
2450 			 *  accounted.
2451 			 */
2452 			/* 1 bitmap, 1 block group descriptor */
2453 			ret = 2 + EXT4_META_TRANS_BLOCKS(inode->i_sb);
2454 			return ret;
2455 		}
2456 	}
2457 
2458 	return ext4_chunk_trans_blocks(inode, nrblocks);
2459 }
2460 
2461 /*
2462  * How many index/leaf blocks need to change/allocate to add @extents extents?
2463  *
2464  * If we add a single extent, then in the worse case, each tree level
2465  * index/leaf need to be changed in case of the tree split.
2466  *
2467  * If more extents are inserted, they could cause the whole tree split more
2468  * than once, but this is really rare.
2469  */
2470 int ext4_ext_index_trans_blocks(struct inode *inode, int extents)
2471 {
2472 	int index;
2473 	int depth;
2474 
2475 	/* If we are converting the inline data, only one is needed here. */
2476 	if (ext4_has_inline_data(inode))
2477 		return 1;
2478 
2479 	depth = ext_depth(inode);
2480 
2481 	if (extents <= 1)
2482 		index = depth * 2;
2483 	else
2484 		index = depth * 3;
2485 
2486 	return index;
2487 }
2488 
2489 static inline int get_default_free_blocks_flags(struct inode *inode)
2490 {
2491 	if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode) ||
2492 	    ext4_test_inode_flag(inode, EXT4_INODE_EA_INODE))
2493 		return EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET;
2494 	else if (ext4_should_journal_data(inode))
2495 		return EXT4_FREE_BLOCKS_FORGET;
2496 	return 0;
2497 }
2498 
2499 static int ext4_remove_blocks(handle_t *handle, struct inode *inode,
2500 			      struct ext4_extent *ex,
2501 			      long long *partial_cluster,
2502 			      ext4_lblk_t from, ext4_lblk_t to)
2503 {
2504 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2505 	unsigned short ee_len = ext4_ext_get_actual_len(ex);
2506 	ext4_fsblk_t pblk;
2507 	int flags = get_default_free_blocks_flags(inode);
2508 
2509 	/*
2510 	 * For bigalloc file systems, we never free a partial cluster
2511 	 * at the beginning of the extent.  Instead, we make a note
2512 	 * that we tried freeing the cluster, and check to see if we
2513 	 * need to free it on a subsequent call to ext4_remove_blocks,
2514 	 * or at the end of ext4_ext_rm_leaf or ext4_ext_remove_space.
2515 	 */
2516 	flags |= EXT4_FREE_BLOCKS_NOFREE_FIRST_CLUSTER;
2517 
2518 	trace_ext4_remove_blocks(inode, ex, from, to, *partial_cluster);
2519 	/*
2520 	 * If we have a partial cluster, and it's different from the
2521 	 * cluster of the last block, we need to explicitly free the
2522 	 * partial cluster here.
2523 	 */
2524 	pblk = ext4_ext_pblock(ex) + ee_len - 1;
2525 	if (*partial_cluster > 0 &&
2526 	    *partial_cluster != (long long) EXT4_B2C(sbi, pblk)) {
2527 		ext4_free_blocks(handle, inode, NULL,
2528 				 EXT4_C2B(sbi, *partial_cluster),
2529 				 sbi->s_cluster_ratio, flags);
2530 		*partial_cluster = 0;
2531 	}
2532 
2533 #ifdef EXTENTS_STATS
2534 	{
2535 		struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2536 		spin_lock(&sbi->s_ext_stats_lock);
2537 		sbi->s_ext_blocks += ee_len;
2538 		sbi->s_ext_extents++;
2539 		if (ee_len < sbi->s_ext_min)
2540 			sbi->s_ext_min = ee_len;
2541 		if (ee_len > sbi->s_ext_max)
2542 			sbi->s_ext_max = ee_len;
2543 		if (ext_depth(inode) > sbi->s_depth_max)
2544 			sbi->s_depth_max = ext_depth(inode);
2545 		spin_unlock(&sbi->s_ext_stats_lock);
2546 	}
2547 #endif
2548 	if (from >= le32_to_cpu(ex->ee_block)
2549 	    && to == le32_to_cpu(ex->ee_block) + ee_len - 1) {
2550 		/* tail removal */
2551 		ext4_lblk_t num;
2552 		long long first_cluster;
2553 
2554 		num = le32_to_cpu(ex->ee_block) + ee_len - from;
2555 		pblk = ext4_ext_pblock(ex) + ee_len - num;
2556 		/*
2557 		 * Usually we want to free partial cluster at the end of the
2558 		 * extent, except for the situation when the cluster is still
2559 		 * used by any other extent (partial_cluster is negative).
2560 		 */
2561 		if (*partial_cluster < 0 &&
2562 		    *partial_cluster == -(long long) EXT4_B2C(sbi, pblk+num-1))
2563 			flags |= EXT4_FREE_BLOCKS_NOFREE_LAST_CLUSTER;
2564 
2565 		ext_debug("free last %u blocks starting %llu partial %lld\n",
2566 			  num, pblk, *partial_cluster);
2567 		ext4_free_blocks(handle, inode, NULL, pblk, num, flags);
2568 		/*
2569 		 * If the block range to be freed didn't start at the
2570 		 * beginning of a cluster, and we removed the entire
2571 		 * extent and the cluster is not used by any other extent,
2572 		 * save the partial cluster here, since we might need to
2573 		 * delete if we determine that the truncate or punch hole
2574 		 * operation has removed all of the blocks in the cluster.
2575 		 * If that cluster is used by another extent, preserve its
2576 		 * negative value so it isn't freed later on.
2577 		 *
2578 		 * If the whole extent wasn't freed, we've reached the
2579 		 * start of the truncated/punched region and have finished
2580 		 * removing blocks.  If there's a partial cluster here it's
2581 		 * shared with the remainder of the extent and is no longer
2582 		 * a candidate for removal.
2583 		 */
2584 		if (EXT4_PBLK_COFF(sbi, pblk) && ee_len == num) {
2585 			first_cluster = (long long) EXT4_B2C(sbi, pblk);
2586 			if (first_cluster != -*partial_cluster)
2587 				*partial_cluster = first_cluster;
2588 		} else {
2589 			*partial_cluster = 0;
2590 		}
2591 	} else
2592 		ext4_error(sbi->s_sb, "strange request: removal(2) "
2593 			   "%u-%u from %u:%u",
2594 			   from, to, le32_to_cpu(ex->ee_block), ee_len);
2595 	return 0;
2596 }
2597 
2598 
2599 /*
2600  * ext4_ext_rm_leaf() Removes the extents associated with the
2601  * blocks appearing between "start" and "end".  Both "start"
2602  * and "end" must appear in the same extent or EIO is returned.
2603  *
2604  * @handle: The journal handle
2605  * @inode:  The files inode
2606  * @path:   The path to the leaf
2607  * @partial_cluster: The cluster which we'll have to free if all extents
2608  *                   has been released from it.  However, if this value is
2609  *                   negative, it's a cluster just to the right of the
2610  *                   punched region and it must not be freed.
2611  * @start:  The first block to remove
2612  * @end:   The last block to remove
2613  */
2614 static int
2615 ext4_ext_rm_leaf(handle_t *handle, struct inode *inode,
2616 		 struct ext4_ext_path *path,
2617 		 long long *partial_cluster,
2618 		 ext4_lblk_t start, ext4_lblk_t end)
2619 {
2620 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2621 	int err = 0, correct_index = 0;
2622 	int depth = ext_depth(inode), credits;
2623 	struct ext4_extent_header *eh;
2624 	ext4_lblk_t a, b;
2625 	unsigned num;
2626 	ext4_lblk_t ex_ee_block;
2627 	unsigned short ex_ee_len;
2628 	unsigned unwritten = 0;
2629 	struct ext4_extent *ex;
2630 	ext4_fsblk_t pblk;
2631 
2632 	/* the header must be checked already in ext4_ext_remove_space() */
2633 	ext_debug("truncate since %u in leaf to %u\n", start, end);
2634 	if (!path[depth].p_hdr)
2635 		path[depth].p_hdr = ext_block_hdr(path[depth].p_bh);
2636 	eh = path[depth].p_hdr;
2637 	if (unlikely(path[depth].p_hdr == NULL)) {
2638 		EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
2639 		return -EFSCORRUPTED;
2640 	}
2641 	/* find where to start removing */
2642 	ex = path[depth].p_ext;
2643 	if (!ex)
2644 		ex = EXT_LAST_EXTENT(eh);
2645 
2646 	ex_ee_block = le32_to_cpu(ex->ee_block);
2647 	ex_ee_len = ext4_ext_get_actual_len(ex);
2648 
2649 	trace_ext4_ext_rm_leaf(inode, start, ex, *partial_cluster);
2650 
2651 	while (ex >= EXT_FIRST_EXTENT(eh) &&
2652 			ex_ee_block + ex_ee_len > start) {
2653 
2654 		if (ext4_ext_is_unwritten(ex))
2655 			unwritten = 1;
2656 		else
2657 			unwritten = 0;
2658 
2659 		ext_debug("remove ext %u:[%d]%d\n", ex_ee_block,
2660 			  unwritten, ex_ee_len);
2661 		path[depth].p_ext = ex;
2662 
2663 		a = ex_ee_block > start ? ex_ee_block : start;
2664 		b = ex_ee_block+ex_ee_len - 1 < end ?
2665 			ex_ee_block+ex_ee_len - 1 : end;
2666 
2667 		ext_debug("  border %u:%u\n", a, b);
2668 
2669 		/* If this extent is beyond the end of the hole, skip it */
2670 		if (end < ex_ee_block) {
2671 			/*
2672 			 * We're going to skip this extent and move to another,
2673 			 * so note that its first cluster is in use to avoid
2674 			 * freeing it when removing blocks.  Eventually, the
2675 			 * right edge of the truncated/punched region will
2676 			 * be just to the left.
2677 			 */
2678 			if (sbi->s_cluster_ratio > 1) {
2679 				pblk = ext4_ext_pblock(ex);
2680 				*partial_cluster =
2681 					-(long long) EXT4_B2C(sbi, pblk);
2682 			}
2683 			ex--;
2684 			ex_ee_block = le32_to_cpu(ex->ee_block);
2685 			ex_ee_len = ext4_ext_get_actual_len(ex);
2686 			continue;
2687 		} else if (b != ex_ee_block + ex_ee_len - 1) {
2688 			EXT4_ERROR_INODE(inode,
2689 					 "can not handle truncate %u:%u "
2690 					 "on extent %u:%u",
2691 					 start, end, ex_ee_block,
2692 					 ex_ee_block + ex_ee_len - 1);
2693 			err = -EFSCORRUPTED;
2694 			goto out;
2695 		} else if (a != ex_ee_block) {
2696 			/* remove tail of the extent */
2697 			num = a - ex_ee_block;
2698 		} else {
2699 			/* remove whole extent: excellent! */
2700 			num = 0;
2701 		}
2702 		/*
2703 		 * 3 for leaf, sb, and inode plus 2 (bmap and group
2704 		 * descriptor) for each block group; assume two block
2705 		 * groups plus ex_ee_len/blocks_per_block_group for
2706 		 * the worst case
2707 		 */
2708 		credits = 7 + 2*(ex_ee_len/EXT4_BLOCKS_PER_GROUP(inode->i_sb));
2709 		if (ex == EXT_FIRST_EXTENT(eh)) {
2710 			correct_index = 1;
2711 			credits += (ext_depth(inode)) + 1;
2712 		}
2713 		credits += EXT4_MAXQUOTAS_TRANS_BLOCKS(inode->i_sb);
2714 
2715 		err = ext4_ext_truncate_extend_restart(handle, inode, credits);
2716 		if (err)
2717 			goto out;
2718 
2719 		err = ext4_ext_get_access(handle, inode, path + depth);
2720 		if (err)
2721 			goto out;
2722 
2723 		err = ext4_remove_blocks(handle, inode, ex, partial_cluster,
2724 					 a, b);
2725 		if (err)
2726 			goto out;
2727 
2728 		if (num == 0)
2729 			/* this extent is removed; mark slot entirely unused */
2730 			ext4_ext_store_pblock(ex, 0);
2731 
2732 		ex->ee_len = cpu_to_le16(num);
2733 		/*
2734 		 * Do not mark unwritten if all the blocks in the
2735 		 * extent have been removed.
2736 		 */
2737 		if (unwritten && num)
2738 			ext4_ext_mark_unwritten(ex);
2739 		/*
2740 		 * If the extent was completely released,
2741 		 * we need to remove it from the leaf
2742 		 */
2743 		if (num == 0) {
2744 			if (end != EXT_MAX_BLOCKS - 1) {
2745 				/*
2746 				 * For hole punching, we need to scoot all the
2747 				 * extents up when an extent is removed so that
2748 				 * we dont have blank extents in the middle
2749 				 */
2750 				memmove(ex, ex+1, (EXT_LAST_EXTENT(eh) - ex) *
2751 					sizeof(struct ext4_extent));
2752 
2753 				/* Now get rid of the one at the end */
2754 				memset(EXT_LAST_EXTENT(eh), 0,
2755 					sizeof(struct ext4_extent));
2756 			}
2757 			le16_add_cpu(&eh->eh_entries, -1);
2758 		}
2759 
2760 		err = ext4_ext_dirty(handle, inode, path + depth);
2761 		if (err)
2762 			goto out;
2763 
2764 		ext_debug("new extent: %u:%u:%llu\n", ex_ee_block, num,
2765 				ext4_ext_pblock(ex));
2766 		ex--;
2767 		ex_ee_block = le32_to_cpu(ex->ee_block);
2768 		ex_ee_len = ext4_ext_get_actual_len(ex);
2769 	}
2770 
2771 	if (correct_index && eh->eh_entries)
2772 		err = ext4_ext_correct_indexes(handle, inode, path);
2773 
2774 	/*
2775 	 * If there's a partial cluster and at least one extent remains in
2776 	 * the leaf, free the partial cluster if it isn't shared with the
2777 	 * current extent.  If it is shared with the current extent
2778 	 * we zero partial_cluster because we've reached the start of the
2779 	 * truncated/punched region and we're done removing blocks.
2780 	 */
2781 	if (*partial_cluster > 0 && ex >= EXT_FIRST_EXTENT(eh)) {
2782 		pblk = ext4_ext_pblock(ex) + ex_ee_len - 1;
2783 		if (*partial_cluster != (long long) EXT4_B2C(sbi, pblk)) {
2784 			ext4_free_blocks(handle, inode, NULL,
2785 					 EXT4_C2B(sbi, *partial_cluster),
2786 					 sbi->s_cluster_ratio,
2787 					 get_default_free_blocks_flags(inode));
2788 		}
2789 		*partial_cluster = 0;
2790 	}
2791 
2792 	/* if this leaf is free, then we should
2793 	 * remove it from index block above */
2794 	if (err == 0 && eh->eh_entries == 0 && path[depth].p_bh != NULL)
2795 		err = ext4_ext_rm_idx(handle, inode, path, depth);
2796 
2797 out:
2798 	return err;
2799 }
2800 
2801 /*
2802  * ext4_ext_more_to_rm:
2803  * returns 1 if current index has to be freed (even partial)
2804  */
2805 static int
2806 ext4_ext_more_to_rm(struct ext4_ext_path *path)
2807 {
2808 	BUG_ON(path->p_idx == NULL);
2809 
2810 	if (path->p_idx < EXT_FIRST_INDEX(path->p_hdr))
2811 		return 0;
2812 
2813 	/*
2814 	 * if truncate on deeper level happened, it wasn't partial,
2815 	 * so we have to consider current index for truncation
2816 	 */
2817 	if (le16_to_cpu(path->p_hdr->eh_entries) == path->p_block)
2818 		return 0;
2819 	return 1;
2820 }
2821 
2822 int ext4_ext_remove_space(struct inode *inode, ext4_lblk_t start,
2823 			  ext4_lblk_t end)
2824 {
2825 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2826 	int depth = ext_depth(inode);
2827 	struct ext4_ext_path *path = NULL;
2828 	long long partial_cluster = 0;
2829 	handle_t *handle;
2830 	int i = 0, err = 0;
2831 
2832 	ext_debug("truncate since %u to %u\n", start, end);
2833 
2834 	/* probably first extent we're gonna free will be last in block */
2835 	handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, depth + 1);
2836 	if (IS_ERR(handle))
2837 		return PTR_ERR(handle);
2838 
2839 again:
2840 	trace_ext4_ext_remove_space(inode, start, end, depth);
2841 
2842 	/*
2843 	 * Check if we are removing extents inside the extent tree. If that
2844 	 * is the case, we are going to punch a hole inside the extent tree
2845 	 * so we have to check whether we need to split the extent covering
2846 	 * the last block to remove so we can easily remove the part of it
2847 	 * in ext4_ext_rm_leaf().
2848 	 */
2849 	if (end < EXT_MAX_BLOCKS - 1) {
2850 		struct ext4_extent *ex;
2851 		ext4_lblk_t ee_block, ex_end, lblk;
2852 		ext4_fsblk_t pblk;
2853 
2854 		/* find extent for or closest extent to this block */
2855 		path = ext4_find_extent(inode, end, NULL, EXT4_EX_NOCACHE);
2856 		if (IS_ERR(path)) {
2857 			ext4_journal_stop(handle);
2858 			return PTR_ERR(path);
2859 		}
2860 		depth = ext_depth(inode);
2861 		/* Leaf not may not exist only if inode has no blocks at all */
2862 		ex = path[depth].p_ext;
2863 		if (!ex) {
2864 			if (depth) {
2865 				EXT4_ERROR_INODE(inode,
2866 						 "path[%d].p_hdr == NULL",
2867 						 depth);
2868 				err = -EFSCORRUPTED;
2869 			}
2870 			goto out;
2871 		}
2872 
2873 		ee_block = le32_to_cpu(ex->ee_block);
2874 		ex_end = ee_block + ext4_ext_get_actual_len(ex) - 1;
2875 
2876 		/*
2877 		 * See if the last block is inside the extent, if so split
2878 		 * the extent at 'end' block so we can easily remove the
2879 		 * tail of the first part of the split extent in
2880 		 * ext4_ext_rm_leaf().
2881 		 */
2882 		if (end >= ee_block && end < ex_end) {
2883 
2884 			/*
2885 			 * If we're going to split the extent, note that
2886 			 * the cluster containing the block after 'end' is
2887 			 * in use to avoid freeing it when removing blocks.
2888 			 */
2889 			if (sbi->s_cluster_ratio > 1) {
2890 				pblk = ext4_ext_pblock(ex) + end - ee_block + 2;
2891 				partial_cluster =
2892 					-(long long) EXT4_B2C(sbi, pblk);
2893 			}
2894 
2895 			/*
2896 			 * Split the extent in two so that 'end' is the last
2897 			 * block in the first new extent. Also we should not
2898 			 * fail removing space due to ENOSPC so try to use
2899 			 * reserved block if that happens.
2900 			 */
2901 			err = ext4_force_split_extent_at(handle, inode, &path,
2902 							 end + 1, 1);
2903 			if (err < 0)
2904 				goto out;
2905 
2906 		} else if (sbi->s_cluster_ratio > 1 && end >= ex_end) {
2907 			/*
2908 			 * If there's an extent to the right its first cluster
2909 			 * contains the immediate right boundary of the
2910 			 * truncated/punched region.  Set partial_cluster to
2911 			 * its negative value so it won't be freed if shared
2912 			 * with the current extent.  The end < ee_block case
2913 			 * is handled in ext4_ext_rm_leaf().
2914 			 */
2915 			lblk = ex_end + 1;
2916 			err = ext4_ext_search_right(inode, path, &lblk, &pblk,
2917 						    &ex);
2918 			if (err)
2919 				goto out;
2920 			if (pblk)
2921 				partial_cluster =
2922 					-(long long) EXT4_B2C(sbi, pblk);
2923 		}
2924 	}
2925 	/*
2926 	 * We start scanning from right side, freeing all the blocks
2927 	 * after i_size and walking into the tree depth-wise.
2928 	 */
2929 	depth = ext_depth(inode);
2930 	if (path) {
2931 		int k = i = depth;
2932 		while (--k > 0)
2933 			path[k].p_block =
2934 				le16_to_cpu(path[k].p_hdr->eh_entries)+1;
2935 	} else {
2936 		path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 1),
2937 			       GFP_NOFS);
2938 		if (path == NULL) {
2939 			ext4_journal_stop(handle);
2940 			return -ENOMEM;
2941 		}
2942 		path[0].p_maxdepth = path[0].p_depth = depth;
2943 		path[0].p_hdr = ext_inode_hdr(inode);
2944 		i = 0;
2945 
2946 		if (ext4_ext_check(inode, path[0].p_hdr, depth, 0)) {
2947 			err = -EFSCORRUPTED;
2948 			goto out;
2949 		}
2950 	}
2951 	err = 0;
2952 
2953 	while (i >= 0 && err == 0) {
2954 		if (i == depth) {
2955 			/* this is leaf block */
2956 			err = ext4_ext_rm_leaf(handle, inode, path,
2957 					       &partial_cluster, start,
2958 					       end);
2959 			/* root level has p_bh == NULL, brelse() eats this */
2960 			brelse(path[i].p_bh);
2961 			path[i].p_bh = NULL;
2962 			i--;
2963 			continue;
2964 		}
2965 
2966 		/* this is index block */
2967 		if (!path[i].p_hdr) {
2968 			ext_debug("initialize header\n");
2969 			path[i].p_hdr = ext_block_hdr(path[i].p_bh);
2970 		}
2971 
2972 		if (!path[i].p_idx) {
2973 			/* this level hasn't been touched yet */
2974 			path[i].p_idx = EXT_LAST_INDEX(path[i].p_hdr);
2975 			path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries)+1;
2976 			ext_debug("init index ptr: hdr 0x%p, num %d\n",
2977 				  path[i].p_hdr,
2978 				  le16_to_cpu(path[i].p_hdr->eh_entries));
2979 		} else {
2980 			/* we were already here, see at next index */
2981 			path[i].p_idx--;
2982 		}
2983 
2984 		ext_debug("level %d - index, first 0x%p, cur 0x%p\n",
2985 				i, EXT_FIRST_INDEX(path[i].p_hdr),
2986 				path[i].p_idx);
2987 		if (ext4_ext_more_to_rm(path + i)) {
2988 			struct buffer_head *bh;
2989 			/* go to the next level */
2990 			ext_debug("move to level %d (block %llu)\n",
2991 				  i + 1, ext4_idx_pblock(path[i].p_idx));
2992 			memset(path + i + 1, 0, sizeof(*path));
2993 			bh = read_extent_tree_block(inode,
2994 				ext4_idx_pblock(path[i].p_idx), depth - i - 1,
2995 				EXT4_EX_NOCACHE);
2996 			if (IS_ERR(bh)) {
2997 				/* should we reset i_size? */
2998 				err = PTR_ERR(bh);
2999 				break;
3000 			}
3001 			/* Yield here to deal with large extent trees.
3002 			 * Should be a no-op if we did IO above. */
3003 			cond_resched();
3004 			if (WARN_ON(i + 1 > depth)) {
3005 				err = -EFSCORRUPTED;
3006 				break;
3007 			}
3008 			path[i + 1].p_bh = bh;
3009 
3010 			/* save actual number of indexes since this
3011 			 * number is changed at the next iteration */
3012 			path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries);
3013 			i++;
3014 		} else {
3015 			/* we finished processing this index, go up */
3016 			if (path[i].p_hdr->eh_entries == 0 && i > 0) {
3017 				/* index is empty, remove it;
3018 				 * handle must be already prepared by the
3019 				 * truncatei_leaf() */
3020 				err = ext4_ext_rm_idx(handle, inode, path, i);
3021 			}
3022 			/* root level has p_bh == NULL, brelse() eats this */
3023 			brelse(path[i].p_bh);
3024 			path[i].p_bh = NULL;
3025 			i--;
3026 			ext_debug("return to level %d\n", i);
3027 		}
3028 	}
3029 
3030 	trace_ext4_ext_remove_space_done(inode, start, end, depth,
3031 			partial_cluster, path->p_hdr->eh_entries);
3032 
3033 	/*
3034 	 * If we still have something in the partial cluster and we have removed
3035 	 * even the first extent, then we should free the blocks in the partial
3036 	 * cluster as well.  (This code will only run when there are no leaves
3037 	 * to the immediate left of the truncated/punched region.)
3038 	 */
3039 	if (partial_cluster > 0 && err == 0) {
3040 		/* don't zero partial_cluster since it's not used afterwards */
3041 		ext4_free_blocks(handle, inode, NULL,
3042 				 EXT4_C2B(sbi, partial_cluster),
3043 				 sbi->s_cluster_ratio,
3044 				 get_default_free_blocks_flags(inode));
3045 	}
3046 
3047 	/* TODO: flexible tree reduction should be here */
3048 	if (path->p_hdr->eh_entries == 0) {
3049 		/*
3050 		 * truncate to zero freed all the tree,
3051 		 * so we need to correct eh_depth
3052 		 */
3053 		err = ext4_ext_get_access(handle, inode, path);
3054 		if (err == 0) {
3055 			ext_inode_hdr(inode)->eh_depth = 0;
3056 			ext_inode_hdr(inode)->eh_max =
3057 				cpu_to_le16(ext4_ext_space_root(inode, 0));
3058 			err = ext4_ext_dirty(handle, inode, path);
3059 		}
3060 	}
3061 out:
3062 	ext4_ext_drop_refs(path);
3063 	kfree(path);
3064 	path = NULL;
3065 	if (err == -EAGAIN)
3066 		goto again;
3067 	ext4_journal_stop(handle);
3068 
3069 	return err;
3070 }
3071 
3072 /*
3073  * called at mount time
3074  */
3075 void ext4_ext_init(struct super_block *sb)
3076 {
3077 	/*
3078 	 * possible initialization would be here
3079 	 */
3080 
3081 	if (ext4_has_feature_extents(sb)) {
3082 #if defined(AGGRESSIVE_TEST) || defined(CHECK_BINSEARCH) || defined(EXTENTS_STATS)
3083 		printk(KERN_INFO "EXT4-fs: file extents enabled"
3084 #ifdef AGGRESSIVE_TEST
3085 		       ", aggressive tests"
3086 #endif
3087 #ifdef CHECK_BINSEARCH
3088 		       ", check binsearch"
3089 #endif
3090 #ifdef EXTENTS_STATS
3091 		       ", stats"
3092 #endif
3093 		       "\n");
3094 #endif
3095 #ifdef EXTENTS_STATS
3096 		spin_lock_init(&EXT4_SB(sb)->s_ext_stats_lock);
3097 		EXT4_SB(sb)->s_ext_min = 1 << 30;
3098 		EXT4_SB(sb)->s_ext_max = 0;
3099 #endif
3100 	}
3101 }
3102 
3103 /*
3104  * called at umount time
3105  */
3106 void ext4_ext_release(struct super_block *sb)
3107 {
3108 	if (!ext4_has_feature_extents(sb))
3109 		return;
3110 
3111 #ifdef EXTENTS_STATS
3112 	if (EXT4_SB(sb)->s_ext_blocks && EXT4_SB(sb)->s_ext_extents) {
3113 		struct ext4_sb_info *sbi = EXT4_SB(sb);
3114 		printk(KERN_ERR "EXT4-fs: %lu blocks in %lu extents (%lu ave)\n",
3115 			sbi->s_ext_blocks, sbi->s_ext_extents,
3116 			sbi->s_ext_blocks / sbi->s_ext_extents);
3117 		printk(KERN_ERR "EXT4-fs: extents: %lu min, %lu max, max depth %lu\n",
3118 			sbi->s_ext_min, sbi->s_ext_max, sbi->s_depth_max);
3119 	}
3120 #endif
3121 }
3122 
3123 static int ext4_zeroout_es(struct inode *inode, struct ext4_extent *ex)
3124 {
3125 	ext4_lblk_t  ee_block;
3126 	ext4_fsblk_t ee_pblock;
3127 	unsigned int ee_len;
3128 
3129 	ee_block  = le32_to_cpu(ex->ee_block);
3130 	ee_len    = ext4_ext_get_actual_len(ex);
3131 	ee_pblock = ext4_ext_pblock(ex);
3132 
3133 	if (ee_len == 0)
3134 		return 0;
3135 
3136 	return ext4_es_insert_extent(inode, ee_block, ee_len, ee_pblock,
3137 				     EXTENT_STATUS_WRITTEN);
3138 }
3139 
3140 /* FIXME!! we need to try to merge to left or right after zero-out  */
3141 static int ext4_ext_zeroout(struct inode *inode, struct ext4_extent *ex)
3142 {
3143 	ext4_fsblk_t ee_pblock;
3144 	unsigned int ee_len;
3145 
3146 	ee_len    = ext4_ext_get_actual_len(ex);
3147 	ee_pblock = ext4_ext_pblock(ex);
3148 	return ext4_issue_zeroout(inode, le32_to_cpu(ex->ee_block), ee_pblock,
3149 				  ee_len);
3150 }
3151 
3152 /*
3153  * ext4_split_extent_at() splits an extent at given block.
3154  *
3155  * @handle: the journal handle
3156  * @inode: the file inode
3157  * @path: the path to the extent
3158  * @split: the logical block where the extent is splitted.
3159  * @split_flags: indicates if the extent could be zeroout if split fails, and
3160  *		 the states(init or unwritten) of new extents.
3161  * @flags: flags used to insert new extent to extent tree.
3162  *
3163  *
3164  * Splits extent [a, b] into two extents [a, @split) and [@split, b], states
3165  * of which are deterimined by split_flag.
3166  *
3167  * There are two cases:
3168  *  a> the extent are splitted into two extent.
3169  *  b> split is not needed, and just mark the extent.
3170  *
3171  * return 0 on success.
3172  */
3173 static int ext4_split_extent_at(handle_t *handle,
3174 			     struct inode *inode,
3175 			     struct ext4_ext_path **ppath,
3176 			     ext4_lblk_t split,
3177 			     int split_flag,
3178 			     int flags)
3179 {
3180 	struct ext4_ext_path *path = *ppath;
3181 	ext4_fsblk_t newblock;
3182 	ext4_lblk_t ee_block;
3183 	struct ext4_extent *ex, newex, orig_ex, zero_ex;
3184 	struct ext4_extent *ex2 = NULL;
3185 	unsigned int ee_len, depth;
3186 	int err = 0;
3187 
3188 	BUG_ON((split_flag & (EXT4_EXT_DATA_VALID1 | EXT4_EXT_DATA_VALID2)) ==
3189 	       (EXT4_EXT_DATA_VALID1 | EXT4_EXT_DATA_VALID2));
3190 
3191 	ext_debug("ext4_split_extents_at: inode %lu, logical"
3192 		"block %llu\n", inode->i_ino, (unsigned long long)split);
3193 
3194 	ext4_ext_show_leaf(inode, path);
3195 
3196 	depth = ext_depth(inode);
3197 	ex = path[depth].p_ext;
3198 	ee_block = le32_to_cpu(ex->ee_block);
3199 	ee_len = ext4_ext_get_actual_len(ex);
3200 	newblock = split - ee_block + ext4_ext_pblock(ex);
3201 
3202 	BUG_ON(split < ee_block || split >= (ee_block + ee_len));
3203 	BUG_ON(!ext4_ext_is_unwritten(ex) &&
3204 	       split_flag & (EXT4_EXT_MAY_ZEROOUT |
3205 			     EXT4_EXT_MARK_UNWRIT1 |
3206 			     EXT4_EXT_MARK_UNWRIT2));
3207 
3208 	err = ext4_ext_get_access(handle, inode, path + depth);
3209 	if (err)
3210 		goto out;
3211 
3212 	if (split == ee_block) {
3213 		/*
3214 		 * case b: block @split is the block that the extent begins with
3215 		 * then we just change the state of the extent, and splitting
3216 		 * is not needed.
3217 		 */
3218 		if (split_flag & EXT4_EXT_MARK_UNWRIT2)
3219 			ext4_ext_mark_unwritten(ex);
3220 		else
3221 			ext4_ext_mark_initialized(ex);
3222 
3223 		if (!(flags & EXT4_GET_BLOCKS_PRE_IO))
3224 			ext4_ext_try_to_merge(handle, inode, path, ex);
3225 
3226 		err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3227 		goto out;
3228 	}
3229 
3230 	/* case a */
3231 	memcpy(&orig_ex, ex, sizeof(orig_ex));
3232 	ex->ee_len = cpu_to_le16(split - ee_block);
3233 	if (split_flag & EXT4_EXT_MARK_UNWRIT1)
3234 		ext4_ext_mark_unwritten(ex);
3235 
3236 	/*
3237 	 * path may lead to new leaf, not to original leaf any more
3238 	 * after ext4_ext_insert_extent() returns,
3239 	 */
3240 	err = ext4_ext_dirty(handle, inode, path + depth);
3241 	if (err)
3242 		goto fix_extent_len;
3243 
3244 	ex2 = &newex;
3245 	ex2->ee_block = cpu_to_le32(split);
3246 	ex2->ee_len   = cpu_to_le16(ee_len - (split - ee_block));
3247 	ext4_ext_store_pblock(ex2, newblock);
3248 	if (split_flag & EXT4_EXT_MARK_UNWRIT2)
3249 		ext4_ext_mark_unwritten(ex2);
3250 
3251 	err = ext4_ext_insert_extent(handle, inode, ppath, &newex, flags);
3252 	if (err == -ENOSPC && (EXT4_EXT_MAY_ZEROOUT & split_flag)) {
3253 		if (split_flag & (EXT4_EXT_DATA_VALID1|EXT4_EXT_DATA_VALID2)) {
3254 			if (split_flag & EXT4_EXT_DATA_VALID1) {
3255 				err = ext4_ext_zeroout(inode, ex2);
3256 				zero_ex.ee_block = ex2->ee_block;
3257 				zero_ex.ee_len = cpu_to_le16(
3258 						ext4_ext_get_actual_len(ex2));
3259 				ext4_ext_store_pblock(&zero_ex,
3260 						      ext4_ext_pblock(ex2));
3261 			} else {
3262 				err = ext4_ext_zeroout(inode, ex);
3263 				zero_ex.ee_block = ex->ee_block;
3264 				zero_ex.ee_len = cpu_to_le16(
3265 						ext4_ext_get_actual_len(ex));
3266 				ext4_ext_store_pblock(&zero_ex,
3267 						      ext4_ext_pblock(ex));
3268 			}
3269 		} else {
3270 			err = ext4_ext_zeroout(inode, &orig_ex);
3271 			zero_ex.ee_block = orig_ex.ee_block;
3272 			zero_ex.ee_len = cpu_to_le16(
3273 						ext4_ext_get_actual_len(&orig_ex));
3274 			ext4_ext_store_pblock(&zero_ex,
3275 					      ext4_ext_pblock(&orig_ex));
3276 		}
3277 
3278 		if (err)
3279 			goto fix_extent_len;
3280 		/* update the extent length and mark as initialized */
3281 		ex->ee_len = cpu_to_le16(ee_len);
3282 		ext4_ext_try_to_merge(handle, inode, path, ex);
3283 		err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3284 		if (err)
3285 			goto fix_extent_len;
3286 
3287 		/* update extent status tree */
3288 		err = ext4_zeroout_es(inode, &zero_ex);
3289 
3290 		goto out;
3291 	} else if (err)
3292 		goto fix_extent_len;
3293 
3294 out:
3295 	ext4_ext_show_leaf(inode, path);
3296 	return err;
3297 
3298 fix_extent_len:
3299 	ex->ee_len = orig_ex.ee_len;
3300 	ext4_ext_dirty(handle, inode, path + path->p_depth);
3301 	return err;
3302 }
3303 
3304 /*
3305  * ext4_split_extents() splits an extent and mark extent which is covered
3306  * by @map as split_flags indicates
3307  *
3308  * It may result in splitting the extent into multiple extents (up to three)
3309  * There are three possibilities:
3310  *   a> There is no split required
3311  *   b> Splits in two extents: Split is happening at either end of the extent
3312  *   c> Splits in three extents: Somone is splitting in middle of the extent
3313  *
3314  */
3315 static int ext4_split_extent(handle_t *handle,
3316 			      struct inode *inode,
3317 			      struct ext4_ext_path **ppath,
3318 			      struct ext4_map_blocks *map,
3319 			      int split_flag,
3320 			      int flags)
3321 {
3322 	struct ext4_ext_path *path = *ppath;
3323 	ext4_lblk_t ee_block;
3324 	struct ext4_extent *ex;
3325 	unsigned int ee_len, depth;
3326 	int err = 0;
3327 	int unwritten;
3328 	int split_flag1, flags1;
3329 	int allocated = map->m_len;
3330 
3331 	depth = ext_depth(inode);
3332 	ex = path[depth].p_ext;
3333 	ee_block = le32_to_cpu(ex->ee_block);
3334 	ee_len = ext4_ext_get_actual_len(ex);
3335 	unwritten = ext4_ext_is_unwritten(ex);
3336 
3337 	if (map->m_lblk + map->m_len < ee_block + ee_len) {
3338 		split_flag1 = split_flag & EXT4_EXT_MAY_ZEROOUT;
3339 		flags1 = flags | EXT4_GET_BLOCKS_PRE_IO;
3340 		if (unwritten)
3341 			split_flag1 |= EXT4_EXT_MARK_UNWRIT1 |
3342 				       EXT4_EXT_MARK_UNWRIT2;
3343 		if (split_flag & EXT4_EXT_DATA_VALID2)
3344 			split_flag1 |= EXT4_EXT_DATA_VALID1;
3345 		err = ext4_split_extent_at(handle, inode, ppath,
3346 				map->m_lblk + map->m_len, split_flag1, flags1);
3347 		if (err)
3348 			goto out;
3349 	} else {
3350 		allocated = ee_len - (map->m_lblk - ee_block);
3351 	}
3352 	/*
3353 	 * Update path is required because previous ext4_split_extent_at() may
3354 	 * result in split of original leaf or extent zeroout.
3355 	 */
3356 	path = ext4_find_extent(inode, map->m_lblk, ppath, 0);
3357 	if (IS_ERR(path))
3358 		return PTR_ERR(path);
3359 	depth = ext_depth(inode);
3360 	ex = path[depth].p_ext;
3361 	if (!ex) {
3362 		EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
3363 				 (unsigned long) map->m_lblk);
3364 		return -EFSCORRUPTED;
3365 	}
3366 	unwritten = ext4_ext_is_unwritten(ex);
3367 	split_flag1 = 0;
3368 
3369 	if (map->m_lblk >= ee_block) {
3370 		split_flag1 = split_flag & EXT4_EXT_DATA_VALID2;
3371 		if (unwritten) {
3372 			split_flag1 |= EXT4_EXT_MARK_UNWRIT1;
3373 			split_flag1 |= split_flag & (EXT4_EXT_MAY_ZEROOUT |
3374 						     EXT4_EXT_MARK_UNWRIT2);
3375 		}
3376 		err = ext4_split_extent_at(handle, inode, ppath,
3377 				map->m_lblk, split_flag1, flags);
3378 		if (err)
3379 			goto out;
3380 	}
3381 
3382 	ext4_ext_show_leaf(inode, path);
3383 out:
3384 	return err ? err : allocated;
3385 }
3386 
3387 /*
3388  * This function is called by ext4_ext_map_blocks() if someone tries to write
3389  * to an unwritten extent. It may result in splitting the unwritten
3390  * extent into multiple extents (up to three - one initialized and two
3391  * unwritten).
3392  * There are three possibilities:
3393  *   a> There is no split required: Entire extent should be initialized
3394  *   b> Splits in two extents: Write is happening at either end of the extent
3395  *   c> Splits in three extents: Somone is writing in middle of the extent
3396  *
3397  * Pre-conditions:
3398  *  - The extent pointed to by 'path' is unwritten.
3399  *  - The extent pointed to by 'path' contains a superset
3400  *    of the logical span [map->m_lblk, map->m_lblk + map->m_len).
3401  *
3402  * Post-conditions on success:
3403  *  - the returned value is the number of blocks beyond map->l_lblk
3404  *    that are allocated and initialized.
3405  *    It is guaranteed to be >= map->m_len.
3406  */
3407 static int ext4_ext_convert_to_initialized(handle_t *handle,
3408 					   struct inode *inode,
3409 					   struct ext4_map_blocks *map,
3410 					   struct ext4_ext_path **ppath,
3411 					   int flags)
3412 {
3413 	struct ext4_ext_path *path = *ppath;
3414 	struct ext4_sb_info *sbi;
3415 	struct ext4_extent_header *eh;
3416 	struct ext4_map_blocks split_map;
3417 	struct ext4_extent zero_ex1, zero_ex2;
3418 	struct ext4_extent *ex, *abut_ex;
3419 	ext4_lblk_t ee_block, eof_block;
3420 	unsigned int ee_len, depth, map_len = map->m_len;
3421 	int allocated = 0, max_zeroout = 0;
3422 	int err = 0;
3423 	int split_flag = EXT4_EXT_DATA_VALID2;
3424 
3425 	ext_debug("ext4_ext_convert_to_initialized: inode %lu, logical"
3426 		"block %llu, max_blocks %u\n", inode->i_ino,
3427 		(unsigned long long)map->m_lblk, map_len);
3428 
3429 	sbi = EXT4_SB(inode->i_sb);
3430 	eof_block = (inode->i_size + inode->i_sb->s_blocksize - 1) >>
3431 		inode->i_sb->s_blocksize_bits;
3432 	if (eof_block < map->m_lblk + map_len)
3433 		eof_block = map->m_lblk + map_len;
3434 
3435 	depth = ext_depth(inode);
3436 	eh = path[depth].p_hdr;
3437 	ex = path[depth].p_ext;
3438 	ee_block = le32_to_cpu(ex->ee_block);
3439 	ee_len = ext4_ext_get_actual_len(ex);
3440 	zero_ex1.ee_len = 0;
3441 	zero_ex2.ee_len = 0;
3442 
3443 	trace_ext4_ext_convert_to_initialized_enter(inode, map, ex);
3444 
3445 	/* Pre-conditions */
3446 	BUG_ON(!ext4_ext_is_unwritten(ex));
3447 	BUG_ON(!in_range(map->m_lblk, ee_block, ee_len));
3448 
3449 	/*
3450 	 * Attempt to transfer newly initialized blocks from the currently
3451 	 * unwritten extent to its neighbor. This is much cheaper
3452 	 * than an insertion followed by a merge as those involve costly
3453 	 * memmove() calls. Transferring to the left is the common case in
3454 	 * steady state for workloads doing fallocate(FALLOC_FL_KEEP_SIZE)
3455 	 * followed by append writes.
3456 	 *
3457 	 * Limitations of the current logic:
3458 	 *  - L1: we do not deal with writes covering the whole extent.
3459 	 *    This would require removing the extent if the transfer
3460 	 *    is possible.
3461 	 *  - L2: we only attempt to merge with an extent stored in the
3462 	 *    same extent tree node.
3463 	 */
3464 	if ((map->m_lblk == ee_block) &&
3465 		/* See if we can merge left */
3466 		(map_len < ee_len) &&		/*L1*/
3467 		(ex > EXT_FIRST_EXTENT(eh))) {	/*L2*/
3468 		ext4_lblk_t prev_lblk;
3469 		ext4_fsblk_t prev_pblk, ee_pblk;
3470 		unsigned int prev_len;
3471 
3472 		abut_ex = ex - 1;
3473 		prev_lblk = le32_to_cpu(abut_ex->ee_block);
3474 		prev_len = ext4_ext_get_actual_len(abut_ex);
3475 		prev_pblk = ext4_ext_pblock(abut_ex);
3476 		ee_pblk = ext4_ext_pblock(ex);
3477 
3478 		/*
3479 		 * A transfer of blocks from 'ex' to 'abut_ex' is allowed
3480 		 * upon those conditions:
3481 		 * - C1: abut_ex is initialized,
3482 		 * - C2: abut_ex is logically abutting ex,
3483 		 * - C3: abut_ex is physically abutting ex,
3484 		 * - C4: abut_ex can receive the additional blocks without
3485 		 *   overflowing the (initialized) length limit.
3486 		 */
3487 		if ((!ext4_ext_is_unwritten(abut_ex)) &&		/*C1*/
3488 			((prev_lblk + prev_len) == ee_block) &&		/*C2*/
3489 			((prev_pblk + prev_len) == ee_pblk) &&		/*C3*/
3490 			(prev_len < (EXT_INIT_MAX_LEN - map_len))) {	/*C4*/
3491 			err = ext4_ext_get_access(handle, inode, path + depth);
3492 			if (err)
3493 				goto out;
3494 
3495 			trace_ext4_ext_convert_to_initialized_fastpath(inode,
3496 				map, ex, abut_ex);
3497 
3498 			/* Shift the start of ex by 'map_len' blocks */
3499 			ex->ee_block = cpu_to_le32(ee_block + map_len);
3500 			ext4_ext_store_pblock(ex, ee_pblk + map_len);
3501 			ex->ee_len = cpu_to_le16(ee_len - map_len);
3502 			ext4_ext_mark_unwritten(ex); /* Restore the flag */
3503 
3504 			/* Extend abut_ex by 'map_len' blocks */
3505 			abut_ex->ee_len = cpu_to_le16(prev_len + map_len);
3506 
3507 			/* Result: number of initialized blocks past m_lblk */
3508 			allocated = map_len;
3509 		}
3510 	} else if (((map->m_lblk + map_len) == (ee_block + ee_len)) &&
3511 		   (map_len < ee_len) &&	/*L1*/
3512 		   ex < EXT_LAST_EXTENT(eh)) {	/*L2*/
3513 		/* See if we can merge right */
3514 		ext4_lblk_t next_lblk;
3515 		ext4_fsblk_t next_pblk, ee_pblk;
3516 		unsigned int next_len;
3517 
3518 		abut_ex = ex + 1;
3519 		next_lblk = le32_to_cpu(abut_ex->ee_block);
3520 		next_len = ext4_ext_get_actual_len(abut_ex);
3521 		next_pblk = ext4_ext_pblock(abut_ex);
3522 		ee_pblk = ext4_ext_pblock(ex);
3523 
3524 		/*
3525 		 * A transfer of blocks from 'ex' to 'abut_ex' is allowed
3526 		 * upon those conditions:
3527 		 * - C1: abut_ex is initialized,
3528 		 * - C2: abut_ex is logically abutting ex,
3529 		 * - C3: abut_ex is physically abutting ex,
3530 		 * - C4: abut_ex can receive the additional blocks without
3531 		 *   overflowing the (initialized) length limit.
3532 		 */
3533 		if ((!ext4_ext_is_unwritten(abut_ex)) &&		/*C1*/
3534 		    ((map->m_lblk + map_len) == next_lblk) &&		/*C2*/
3535 		    ((ee_pblk + ee_len) == next_pblk) &&		/*C3*/
3536 		    (next_len < (EXT_INIT_MAX_LEN - map_len))) {	/*C4*/
3537 			err = ext4_ext_get_access(handle, inode, path + depth);
3538 			if (err)
3539 				goto out;
3540 
3541 			trace_ext4_ext_convert_to_initialized_fastpath(inode,
3542 				map, ex, abut_ex);
3543 
3544 			/* Shift the start of abut_ex by 'map_len' blocks */
3545 			abut_ex->ee_block = cpu_to_le32(next_lblk - map_len);
3546 			ext4_ext_store_pblock(abut_ex, next_pblk - map_len);
3547 			ex->ee_len = cpu_to_le16(ee_len - map_len);
3548 			ext4_ext_mark_unwritten(ex); /* Restore the flag */
3549 
3550 			/* Extend abut_ex by 'map_len' blocks */
3551 			abut_ex->ee_len = cpu_to_le16(next_len + map_len);
3552 
3553 			/* Result: number of initialized blocks past m_lblk */
3554 			allocated = map_len;
3555 		}
3556 	}
3557 	if (allocated) {
3558 		/* Mark the block containing both extents as dirty */
3559 		ext4_ext_dirty(handle, inode, path + depth);
3560 
3561 		/* Update path to point to the right extent */
3562 		path[depth].p_ext = abut_ex;
3563 		goto out;
3564 	} else
3565 		allocated = ee_len - (map->m_lblk - ee_block);
3566 
3567 	WARN_ON(map->m_lblk < ee_block);
3568 	/*
3569 	 * It is safe to convert extent to initialized via explicit
3570 	 * zeroout only if extent is fully inside i_size or new_size.
3571 	 */
3572 	split_flag |= ee_block + ee_len <= eof_block ? EXT4_EXT_MAY_ZEROOUT : 0;
3573 
3574 	if (EXT4_EXT_MAY_ZEROOUT & split_flag)
3575 		max_zeroout = sbi->s_extent_max_zeroout_kb >>
3576 			(inode->i_sb->s_blocksize_bits - 10);
3577 
3578 	if (ext4_encrypted_inode(inode))
3579 		max_zeroout = 0;
3580 
3581 	/*
3582 	 * five cases:
3583 	 * 1. split the extent into three extents.
3584 	 * 2. split the extent into two extents, zeroout the head of the first
3585 	 *    extent.
3586 	 * 3. split the extent into two extents, zeroout the tail of the second
3587 	 *    extent.
3588 	 * 4. split the extent into two extents with out zeroout.
3589 	 * 5. no splitting needed, just possibly zeroout the head and / or the
3590 	 *    tail of the extent.
3591 	 */
3592 	split_map.m_lblk = map->m_lblk;
3593 	split_map.m_len = map->m_len;
3594 
3595 	if (max_zeroout && (allocated > split_map.m_len)) {
3596 		if (allocated <= max_zeroout) {
3597 			/* case 3 or 5 */
3598 			zero_ex1.ee_block =
3599 				 cpu_to_le32(split_map.m_lblk +
3600 					     split_map.m_len);
3601 			zero_ex1.ee_len =
3602 				cpu_to_le16(allocated - split_map.m_len);
3603 			ext4_ext_store_pblock(&zero_ex1,
3604 				ext4_ext_pblock(ex) + split_map.m_lblk +
3605 				split_map.m_len - ee_block);
3606 			err = ext4_ext_zeroout(inode, &zero_ex1);
3607 			if (err)
3608 				goto out;
3609 			split_map.m_len = allocated;
3610 		}
3611 		if (split_map.m_lblk - ee_block + split_map.m_len <
3612 								max_zeroout) {
3613 			/* case 2 or 5 */
3614 			if (split_map.m_lblk != ee_block) {
3615 				zero_ex2.ee_block = ex->ee_block;
3616 				zero_ex2.ee_len = cpu_to_le16(split_map.m_lblk -
3617 							ee_block);
3618 				ext4_ext_store_pblock(&zero_ex2,
3619 						      ext4_ext_pblock(ex));
3620 				err = ext4_ext_zeroout(inode, &zero_ex2);
3621 				if (err)
3622 					goto out;
3623 			}
3624 
3625 			split_map.m_len += split_map.m_lblk - ee_block;
3626 			split_map.m_lblk = ee_block;
3627 			allocated = map->m_len;
3628 		}
3629 	}
3630 
3631 	err = ext4_split_extent(handle, inode, ppath, &split_map, split_flag,
3632 				flags);
3633 	if (err > 0)
3634 		err = 0;
3635 out:
3636 	/* If we have gotten a failure, don't zero out status tree */
3637 	if (!err) {
3638 		err = ext4_zeroout_es(inode, &zero_ex1);
3639 		if (!err)
3640 			err = ext4_zeroout_es(inode, &zero_ex2);
3641 	}
3642 	return err ? err : allocated;
3643 }
3644 
3645 /*
3646  * This function is called by ext4_ext_map_blocks() from
3647  * ext4_get_blocks_dio_write() when DIO to write
3648  * to an unwritten extent.
3649  *
3650  * Writing to an unwritten extent may result in splitting the unwritten
3651  * extent into multiple initialized/unwritten extents (up to three)
3652  * There are three possibilities:
3653  *   a> There is no split required: Entire extent should be unwritten
3654  *   b> Splits in two extents: Write is happening at either end of the extent
3655  *   c> Splits in three extents: Somone is writing in middle of the extent
3656  *
3657  * This works the same way in the case of initialized -> unwritten conversion.
3658  *
3659  * One of more index blocks maybe needed if the extent tree grow after
3660  * the unwritten extent split. To prevent ENOSPC occur at the IO
3661  * complete, we need to split the unwritten extent before DIO submit
3662  * the IO. The unwritten extent called at this time will be split
3663  * into three unwritten extent(at most). After IO complete, the part
3664  * being filled will be convert to initialized by the end_io callback function
3665  * via ext4_convert_unwritten_extents().
3666  *
3667  * Returns the size of unwritten extent to be written on success.
3668  */
3669 static int ext4_split_convert_extents(handle_t *handle,
3670 					struct inode *inode,
3671 					struct ext4_map_blocks *map,
3672 					struct ext4_ext_path **ppath,
3673 					int flags)
3674 {
3675 	struct ext4_ext_path *path = *ppath;
3676 	ext4_lblk_t eof_block;
3677 	ext4_lblk_t ee_block;
3678 	struct ext4_extent *ex;
3679 	unsigned int ee_len;
3680 	int split_flag = 0, depth;
3681 
3682 	ext_debug("%s: inode %lu, logical block %llu, max_blocks %u\n",
3683 		  __func__, inode->i_ino,
3684 		  (unsigned long long)map->m_lblk, map->m_len);
3685 
3686 	eof_block = (inode->i_size + inode->i_sb->s_blocksize - 1) >>
3687 		inode->i_sb->s_blocksize_bits;
3688 	if (eof_block < map->m_lblk + map->m_len)
3689 		eof_block = map->m_lblk + map->m_len;
3690 	/*
3691 	 * It is safe to convert extent to initialized via explicit
3692 	 * zeroout only if extent is fully insde i_size or new_size.
3693 	 */
3694 	depth = ext_depth(inode);
3695 	ex = path[depth].p_ext;
3696 	ee_block = le32_to_cpu(ex->ee_block);
3697 	ee_len = ext4_ext_get_actual_len(ex);
3698 
3699 	/* Convert to unwritten */
3700 	if (flags & EXT4_GET_BLOCKS_CONVERT_UNWRITTEN) {
3701 		split_flag |= EXT4_EXT_DATA_VALID1;
3702 	/* Convert to initialized */
3703 	} else if (flags & EXT4_GET_BLOCKS_CONVERT) {
3704 		split_flag |= ee_block + ee_len <= eof_block ?
3705 			      EXT4_EXT_MAY_ZEROOUT : 0;
3706 		split_flag |= (EXT4_EXT_MARK_UNWRIT2 | EXT4_EXT_DATA_VALID2);
3707 	}
3708 	flags |= EXT4_GET_BLOCKS_PRE_IO;
3709 	return ext4_split_extent(handle, inode, ppath, map, split_flag, flags);
3710 }
3711 
3712 static int ext4_convert_unwritten_extents_endio(handle_t *handle,
3713 						struct inode *inode,
3714 						struct ext4_map_blocks *map,
3715 						struct ext4_ext_path **ppath)
3716 {
3717 	struct ext4_ext_path *path = *ppath;
3718 	struct ext4_extent *ex;
3719 	ext4_lblk_t ee_block;
3720 	unsigned int ee_len;
3721 	int depth;
3722 	int err = 0;
3723 
3724 	depth = ext_depth(inode);
3725 	ex = path[depth].p_ext;
3726 	ee_block = le32_to_cpu(ex->ee_block);
3727 	ee_len = ext4_ext_get_actual_len(ex);
3728 
3729 	ext_debug("ext4_convert_unwritten_extents_endio: inode %lu, logical"
3730 		"block %llu, max_blocks %u\n", inode->i_ino,
3731 		  (unsigned long long)ee_block, ee_len);
3732 
3733 	/* If extent is larger than requested it is a clear sign that we still
3734 	 * have some extent state machine issues left. So extent_split is still
3735 	 * required.
3736 	 * TODO: Once all related issues will be fixed this situation should be
3737 	 * illegal.
3738 	 */
3739 	if (ee_block != map->m_lblk || ee_len > map->m_len) {
3740 #ifdef EXT4_DEBUG
3741 		ext4_warning("Inode (%ld) finished: extent logical block %llu,"
3742 			     " len %u; IO logical block %llu, len %u",
3743 			     inode->i_ino, (unsigned long long)ee_block, ee_len,
3744 			     (unsigned long long)map->m_lblk, map->m_len);
3745 #endif
3746 		err = ext4_split_convert_extents(handle, inode, map, ppath,
3747 						 EXT4_GET_BLOCKS_CONVERT);
3748 		if (err < 0)
3749 			return err;
3750 		path = ext4_find_extent(inode, map->m_lblk, ppath, 0);
3751 		if (IS_ERR(path))
3752 			return PTR_ERR(path);
3753 		depth = ext_depth(inode);
3754 		ex = path[depth].p_ext;
3755 	}
3756 
3757 	err = ext4_ext_get_access(handle, inode, path + depth);
3758 	if (err)
3759 		goto out;
3760 	/* first mark the extent as initialized */
3761 	ext4_ext_mark_initialized(ex);
3762 
3763 	/* note: ext4_ext_correct_indexes() isn't needed here because
3764 	 * borders are not changed
3765 	 */
3766 	ext4_ext_try_to_merge(handle, inode, path, ex);
3767 
3768 	/* Mark modified extent as dirty */
3769 	err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3770 out:
3771 	ext4_ext_show_leaf(inode, path);
3772 	return err;
3773 }
3774 
3775 /*
3776  * Handle EOFBLOCKS_FL flag, clearing it if necessary
3777  */
3778 static int check_eofblocks_fl(handle_t *handle, struct inode *inode,
3779 			      ext4_lblk_t lblk,
3780 			      struct ext4_ext_path *path,
3781 			      unsigned int len)
3782 {
3783 	int i, depth;
3784 	struct ext4_extent_header *eh;
3785 	struct ext4_extent *last_ex;
3786 
3787 	if (!ext4_test_inode_flag(inode, EXT4_INODE_EOFBLOCKS))
3788 		return 0;
3789 
3790 	depth = ext_depth(inode);
3791 	eh = path[depth].p_hdr;
3792 
3793 	/*
3794 	 * We're going to remove EOFBLOCKS_FL entirely in future so we
3795 	 * do not care for this case anymore. Simply remove the flag
3796 	 * if there are no extents.
3797 	 */
3798 	if (unlikely(!eh->eh_entries))
3799 		goto out;
3800 	last_ex = EXT_LAST_EXTENT(eh);
3801 	/*
3802 	 * We should clear the EOFBLOCKS_FL flag if we are writing the
3803 	 * last block in the last extent in the file.  We test this by
3804 	 * first checking to see if the caller to
3805 	 * ext4_ext_get_blocks() was interested in the last block (or
3806 	 * a block beyond the last block) in the current extent.  If
3807 	 * this turns out to be false, we can bail out from this
3808 	 * function immediately.
3809 	 */
3810 	if (lblk + len < le32_to_cpu(last_ex->ee_block) +
3811 	    ext4_ext_get_actual_len(last_ex))
3812 		return 0;
3813 	/*
3814 	 * If the caller does appear to be planning to write at or
3815 	 * beyond the end of the current extent, we then test to see
3816 	 * if the current extent is the last extent in the file, by
3817 	 * checking to make sure it was reached via the rightmost node
3818 	 * at each level of the tree.
3819 	 */
3820 	for (i = depth-1; i >= 0; i--)
3821 		if (path[i].p_idx != EXT_LAST_INDEX(path[i].p_hdr))
3822 			return 0;
3823 out:
3824 	ext4_clear_inode_flag(inode, EXT4_INODE_EOFBLOCKS);
3825 	return ext4_mark_inode_dirty(handle, inode);
3826 }
3827 
3828 /**
3829  * ext4_find_delalloc_range: find delayed allocated block in the given range.
3830  *
3831  * Return 1 if there is a delalloc block in the range, otherwise 0.
3832  */
3833 int ext4_find_delalloc_range(struct inode *inode,
3834 			     ext4_lblk_t lblk_start,
3835 			     ext4_lblk_t lblk_end)
3836 {
3837 	struct extent_status es;
3838 
3839 	ext4_es_find_delayed_extent_range(inode, lblk_start, lblk_end, &es);
3840 	if (es.es_len == 0)
3841 		return 0; /* there is no delay extent in this tree */
3842 	else if (es.es_lblk <= lblk_start &&
3843 		 lblk_start < es.es_lblk + es.es_len)
3844 		return 1;
3845 	else if (lblk_start <= es.es_lblk && es.es_lblk <= lblk_end)
3846 		return 1;
3847 	else
3848 		return 0;
3849 }
3850 
3851 int ext4_find_delalloc_cluster(struct inode *inode, ext4_lblk_t lblk)
3852 {
3853 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
3854 	ext4_lblk_t lblk_start, lblk_end;
3855 	lblk_start = EXT4_LBLK_CMASK(sbi, lblk);
3856 	lblk_end = lblk_start + sbi->s_cluster_ratio - 1;
3857 
3858 	return ext4_find_delalloc_range(inode, lblk_start, lblk_end);
3859 }
3860 
3861 /**
3862  * Determines how many complete clusters (out of those specified by the 'map')
3863  * are under delalloc and were reserved quota for.
3864  * This function is called when we are writing out the blocks that were
3865  * originally written with their allocation delayed, but then the space was
3866  * allocated using fallocate() before the delayed allocation could be resolved.
3867  * The cases to look for are:
3868  * ('=' indicated delayed allocated blocks
3869  *  '-' indicates non-delayed allocated blocks)
3870  * (a) partial clusters towards beginning and/or end outside of allocated range
3871  *     are not delalloc'ed.
3872  *	Ex:
3873  *	|----c---=|====c====|====c====|===-c----|
3874  *	         |++++++ allocated ++++++|
3875  *	==> 4 complete clusters in above example
3876  *
3877  * (b) partial cluster (outside of allocated range) towards either end is
3878  *     marked for delayed allocation. In this case, we will exclude that
3879  *     cluster.
3880  *	Ex:
3881  *	|----====c========|========c========|
3882  *	     |++++++ allocated ++++++|
3883  *	==> 1 complete clusters in above example
3884  *
3885  *	Ex:
3886  *	|================c================|
3887  *            |++++++ allocated ++++++|
3888  *	==> 0 complete clusters in above example
3889  *
3890  * The ext4_da_update_reserve_space will be called only if we
3891  * determine here that there were some "entire" clusters that span
3892  * this 'allocated' range.
3893  * In the non-bigalloc case, this function will just end up returning num_blks
3894  * without ever calling ext4_find_delalloc_range.
3895  */
3896 static unsigned int
3897 get_reserved_cluster_alloc(struct inode *inode, ext4_lblk_t lblk_start,
3898 			   unsigned int num_blks)
3899 {
3900 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
3901 	ext4_lblk_t alloc_cluster_start, alloc_cluster_end;
3902 	ext4_lblk_t lblk_from, lblk_to, c_offset;
3903 	unsigned int allocated_clusters = 0;
3904 
3905 	alloc_cluster_start = EXT4_B2C(sbi, lblk_start);
3906 	alloc_cluster_end = EXT4_B2C(sbi, lblk_start + num_blks - 1);
3907 
3908 	/* max possible clusters for this allocation */
3909 	allocated_clusters = alloc_cluster_end - alloc_cluster_start + 1;
3910 
3911 	trace_ext4_get_reserved_cluster_alloc(inode, lblk_start, num_blks);
3912 
3913 	/* Check towards left side */
3914 	c_offset = EXT4_LBLK_COFF(sbi, lblk_start);
3915 	if (c_offset) {
3916 		lblk_from = EXT4_LBLK_CMASK(sbi, lblk_start);
3917 		lblk_to = lblk_from + c_offset - 1;
3918 
3919 		if (ext4_find_delalloc_range(inode, lblk_from, lblk_to))
3920 			allocated_clusters--;
3921 	}
3922 
3923 	/* Now check towards right. */
3924 	c_offset = EXT4_LBLK_COFF(sbi, lblk_start + num_blks);
3925 	if (allocated_clusters && c_offset) {
3926 		lblk_from = lblk_start + num_blks;
3927 		lblk_to = lblk_from + (sbi->s_cluster_ratio - c_offset) - 1;
3928 
3929 		if (ext4_find_delalloc_range(inode, lblk_from, lblk_to))
3930 			allocated_clusters--;
3931 	}
3932 
3933 	return allocated_clusters;
3934 }
3935 
3936 static int
3937 convert_initialized_extent(handle_t *handle, struct inode *inode,
3938 			   struct ext4_map_blocks *map,
3939 			   struct ext4_ext_path **ppath,
3940 			   unsigned int allocated)
3941 {
3942 	struct ext4_ext_path *path = *ppath;
3943 	struct ext4_extent *ex;
3944 	ext4_lblk_t ee_block;
3945 	unsigned int ee_len;
3946 	int depth;
3947 	int err = 0;
3948 
3949 	/*
3950 	 * Make sure that the extent is no bigger than we support with
3951 	 * unwritten extent
3952 	 */
3953 	if (map->m_len > EXT_UNWRITTEN_MAX_LEN)
3954 		map->m_len = EXT_UNWRITTEN_MAX_LEN / 2;
3955 
3956 	depth = ext_depth(inode);
3957 	ex = path[depth].p_ext;
3958 	ee_block = le32_to_cpu(ex->ee_block);
3959 	ee_len = ext4_ext_get_actual_len(ex);
3960 
3961 	ext_debug("%s: inode %lu, logical"
3962 		"block %llu, max_blocks %u\n", __func__, inode->i_ino,
3963 		  (unsigned long long)ee_block, ee_len);
3964 
3965 	if (ee_block != map->m_lblk || ee_len > map->m_len) {
3966 		err = ext4_split_convert_extents(handle, inode, map, ppath,
3967 				EXT4_GET_BLOCKS_CONVERT_UNWRITTEN);
3968 		if (err < 0)
3969 			return err;
3970 		path = ext4_find_extent(inode, map->m_lblk, ppath, 0);
3971 		if (IS_ERR(path))
3972 			return PTR_ERR(path);
3973 		depth = ext_depth(inode);
3974 		ex = path[depth].p_ext;
3975 		if (!ex) {
3976 			EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
3977 					 (unsigned long) map->m_lblk);
3978 			return -EFSCORRUPTED;
3979 		}
3980 	}
3981 
3982 	err = ext4_ext_get_access(handle, inode, path + depth);
3983 	if (err)
3984 		return err;
3985 	/* first mark the extent as unwritten */
3986 	ext4_ext_mark_unwritten(ex);
3987 
3988 	/* note: ext4_ext_correct_indexes() isn't needed here because
3989 	 * borders are not changed
3990 	 */
3991 	ext4_ext_try_to_merge(handle, inode, path, ex);
3992 
3993 	/* Mark modified extent as dirty */
3994 	err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3995 	if (err)
3996 		return err;
3997 	ext4_ext_show_leaf(inode, path);
3998 
3999 	ext4_update_inode_fsync_trans(handle, inode, 1);
4000 	err = check_eofblocks_fl(handle, inode, map->m_lblk, path, map->m_len);
4001 	if (err)
4002 		return err;
4003 	map->m_flags |= EXT4_MAP_UNWRITTEN;
4004 	if (allocated > map->m_len)
4005 		allocated = map->m_len;
4006 	map->m_len = allocated;
4007 	return allocated;
4008 }
4009 
4010 static int
4011 ext4_ext_handle_unwritten_extents(handle_t *handle, struct inode *inode,
4012 			struct ext4_map_blocks *map,
4013 			struct ext4_ext_path **ppath, int flags,
4014 			unsigned int allocated, ext4_fsblk_t newblock)
4015 {
4016 	struct ext4_ext_path *path = *ppath;
4017 	int ret = 0;
4018 	int err = 0;
4019 
4020 	ext_debug("ext4_ext_handle_unwritten_extents: inode %lu, logical "
4021 		  "block %llu, max_blocks %u, flags %x, allocated %u\n",
4022 		  inode->i_ino, (unsigned long long)map->m_lblk, map->m_len,
4023 		  flags, allocated);
4024 	ext4_ext_show_leaf(inode, path);
4025 
4026 	/*
4027 	 * When writing into unwritten space, we should not fail to
4028 	 * allocate metadata blocks for the new extent block if needed.
4029 	 */
4030 	flags |= EXT4_GET_BLOCKS_METADATA_NOFAIL;
4031 
4032 	trace_ext4_ext_handle_unwritten_extents(inode, map, flags,
4033 						    allocated, newblock);
4034 
4035 	/* get_block() before submit the IO, split the extent */
4036 	if (flags & EXT4_GET_BLOCKS_PRE_IO) {
4037 		ret = ext4_split_convert_extents(handle, inode, map, ppath,
4038 					 flags | EXT4_GET_BLOCKS_CONVERT);
4039 		if (ret <= 0)
4040 			goto out;
4041 		map->m_flags |= EXT4_MAP_UNWRITTEN;
4042 		goto out;
4043 	}
4044 	/* IO end_io complete, convert the filled extent to written */
4045 	if (flags & EXT4_GET_BLOCKS_CONVERT) {
4046 		if (flags & EXT4_GET_BLOCKS_ZERO) {
4047 			if (allocated > map->m_len)
4048 				allocated = map->m_len;
4049 			err = ext4_issue_zeroout(inode, map->m_lblk, newblock,
4050 						 allocated);
4051 			if (err < 0)
4052 				goto out2;
4053 		}
4054 		ret = ext4_convert_unwritten_extents_endio(handle, inode, map,
4055 							   ppath);
4056 		if (ret >= 0) {
4057 			ext4_update_inode_fsync_trans(handle, inode, 1);
4058 			err = check_eofblocks_fl(handle, inode, map->m_lblk,
4059 						 path, map->m_len);
4060 		} else
4061 			err = ret;
4062 		map->m_flags |= EXT4_MAP_MAPPED;
4063 		map->m_pblk = newblock;
4064 		if (allocated > map->m_len)
4065 			allocated = map->m_len;
4066 		map->m_len = allocated;
4067 		goto out2;
4068 	}
4069 	/* buffered IO case */
4070 	/*
4071 	 * repeat fallocate creation request
4072 	 * we already have an unwritten extent
4073 	 */
4074 	if (flags & EXT4_GET_BLOCKS_UNWRIT_EXT) {
4075 		map->m_flags |= EXT4_MAP_UNWRITTEN;
4076 		goto map_out;
4077 	}
4078 
4079 	/* buffered READ or buffered write_begin() lookup */
4080 	if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
4081 		/*
4082 		 * We have blocks reserved already.  We
4083 		 * return allocated blocks so that delalloc
4084 		 * won't do block reservation for us.  But
4085 		 * the buffer head will be unmapped so that
4086 		 * a read from the block returns 0s.
4087 		 */
4088 		map->m_flags |= EXT4_MAP_UNWRITTEN;
4089 		goto out1;
4090 	}
4091 
4092 	/* buffered write, writepage time, convert*/
4093 	ret = ext4_ext_convert_to_initialized(handle, inode, map, ppath, flags);
4094 	if (ret >= 0)
4095 		ext4_update_inode_fsync_trans(handle, inode, 1);
4096 out:
4097 	if (ret <= 0) {
4098 		err = ret;
4099 		goto out2;
4100 	} else
4101 		allocated = ret;
4102 	map->m_flags |= EXT4_MAP_NEW;
4103 	/*
4104 	 * if we allocated more blocks than requested
4105 	 * we need to make sure we unmap the extra block
4106 	 * allocated. The actual needed block will get
4107 	 * unmapped later when we find the buffer_head marked
4108 	 * new.
4109 	 */
4110 	if (allocated > map->m_len) {
4111 		clean_bdev_aliases(inode->i_sb->s_bdev, newblock + map->m_len,
4112 				   allocated - map->m_len);
4113 		allocated = map->m_len;
4114 	}
4115 	map->m_len = allocated;
4116 
4117 	/*
4118 	 * If we have done fallocate with the offset that is already
4119 	 * delayed allocated, we would have block reservation
4120 	 * and quota reservation done in the delayed write path.
4121 	 * But fallocate would have already updated quota and block
4122 	 * count for this offset. So cancel these reservation
4123 	 */
4124 	if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE) {
4125 		unsigned int reserved_clusters;
4126 		reserved_clusters = get_reserved_cluster_alloc(inode,
4127 				map->m_lblk, map->m_len);
4128 		if (reserved_clusters)
4129 			ext4_da_update_reserve_space(inode,
4130 						     reserved_clusters,
4131 						     0);
4132 	}
4133 
4134 map_out:
4135 	map->m_flags |= EXT4_MAP_MAPPED;
4136 	if ((flags & EXT4_GET_BLOCKS_KEEP_SIZE) == 0) {
4137 		err = check_eofblocks_fl(handle, inode, map->m_lblk, path,
4138 					 map->m_len);
4139 		if (err < 0)
4140 			goto out2;
4141 	}
4142 out1:
4143 	if (allocated > map->m_len)
4144 		allocated = map->m_len;
4145 	ext4_ext_show_leaf(inode, path);
4146 	map->m_pblk = newblock;
4147 	map->m_len = allocated;
4148 out2:
4149 	return err ? err : allocated;
4150 }
4151 
4152 /*
4153  * get_implied_cluster_alloc - check to see if the requested
4154  * allocation (in the map structure) overlaps with a cluster already
4155  * allocated in an extent.
4156  *	@sb	The filesystem superblock structure
4157  *	@map	The requested lblk->pblk mapping
4158  *	@ex	The extent structure which might contain an implied
4159  *			cluster allocation
4160  *
4161  * This function is called by ext4_ext_map_blocks() after we failed to
4162  * find blocks that were already in the inode's extent tree.  Hence,
4163  * we know that the beginning of the requested region cannot overlap
4164  * the extent from the inode's extent tree.  There are three cases we
4165  * want to catch.  The first is this case:
4166  *
4167  *		 |--- cluster # N--|
4168  *    |--- extent ---|	|---- requested region ---|
4169  *			|==========|
4170  *
4171  * The second case that we need to test for is this one:
4172  *
4173  *   |--------- cluster # N ----------------|
4174  *	   |--- requested region --|   |------- extent ----|
4175  *	   |=======================|
4176  *
4177  * The third case is when the requested region lies between two extents
4178  * within the same cluster:
4179  *          |------------- cluster # N-------------|
4180  * |----- ex -----|                  |---- ex_right ----|
4181  *                  |------ requested region ------|
4182  *                  |================|
4183  *
4184  * In each of the above cases, we need to set the map->m_pblk and
4185  * map->m_len so it corresponds to the return the extent labelled as
4186  * "|====|" from cluster #N, since it is already in use for data in
4187  * cluster EXT4_B2C(sbi, map->m_lblk).	We will then return 1 to
4188  * signal to ext4_ext_map_blocks() that map->m_pblk should be treated
4189  * as a new "allocated" block region.  Otherwise, we will return 0 and
4190  * ext4_ext_map_blocks() will then allocate one or more new clusters
4191  * by calling ext4_mb_new_blocks().
4192  */
4193 static int get_implied_cluster_alloc(struct super_block *sb,
4194 				     struct ext4_map_blocks *map,
4195 				     struct ext4_extent *ex,
4196 				     struct ext4_ext_path *path)
4197 {
4198 	struct ext4_sb_info *sbi = EXT4_SB(sb);
4199 	ext4_lblk_t c_offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4200 	ext4_lblk_t ex_cluster_start, ex_cluster_end;
4201 	ext4_lblk_t rr_cluster_start;
4202 	ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
4203 	ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
4204 	unsigned short ee_len = ext4_ext_get_actual_len(ex);
4205 
4206 	/* The extent passed in that we are trying to match */
4207 	ex_cluster_start = EXT4_B2C(sbi, ee_block);
4208 	ex_cluster_end = EXT4_B2C(sbi, ee_block + ee_len - 1);
4209 
4210 	/* The requested region passed into ext4_map_blocks() */
4211 	rr_cluster_start = EXT4_B2C(sbi, map->m_lblk);
4212 
4213 	if ((rr_cluster_start == ex_cluster_end) ||
4214 	    (rr_cluster_start == ex_cluster_start)) {
4215 		if (rr_cluster_start == ex_cluster_end)
4216 			ee_start += ee_len - 1;
4217 		map->m_pblk = EXT4_PBLK_CMASK(sbi, ee_start) + c_offset;
4218 		map->m_len = min(map->m_len,
4219 				 (unsigned) sbi->s_cluster_ratio - c_offset);
4220 		/*
4221 		 * Check for and handle this case:
4222 		 *
4223 		 *   |--------- cluster # N-------------|
4224 		 *		       |------- extent ----|
4225 		 *	   |--- requested region ---|
4226 		 *	   |===========|
4227 		 */
4228 
4229 		if (map->m_lblk < ee_block)
4230 			map->m_len = min(map->m_len, ee_block - map->m_lblk);
4231 
4232 		/*
4233 		 * Check for the case where there is already another allocated
4234 		 * block to the right of 'ex' but before the end of the cluster.
4235 		 *
4236 		 *          |------------- cluster # N-------------|
4237 		 * |----- ex -----|                  |---- ex_right ----|
4238 		 *                  |------ requested region ------|
4239 		 *                  |================|
4240 		 */
4241 		if (map->m_lblk > ee_block) {
4242 			ext4_lblk_t next = ext4_ext_next_allocated_block(path);
4243 			map->m_len = min(map->m_len, next - map->m_lblk);
4244 		}
4245 
4246 		trace_ext4_get_implied_cluster_alloc_exit(sb, map, 1);
4247 		return 1;
4248 	}
4249 
4250 	trace_ext4_get_implied_cluster_alloc_exit(sb, map, 0);
4251 	return 0;
4252 }
4253 
4254 
4255 /*
4256  * Block allocation/map/preallocation routine for extents based files
4257  *
4258  *
4259  * Need to be called with
4260  * down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system block
4261  * (ie, create is zero). Otherwise down_write(&EXT4_I(inode)->i_data_sem)
4262  *
4263  * return > 0, number of of blocks already mapped/allocated
4264  *          if create == 0 and these are pre-allocated blocks
4265  *          	buffer head is unmapped
4266  *          otherwise blocks are mapped
4267  *
4268  * return = 0, if plain look up failed (blocks have not been allocated)
4269  *          buffer head is unmapped
4270  *
4271  * return < 0, error case.
4272  */
4273 int ext4_ext_map_blocks(handle_t *handle, struct inode *inode,
4274 			struct ext4_map_blocks *map, int flags)
4275 {
4276 	struct ext4_ext_path *path = NULL;
4277 	struct ext4_extent newex, *ex, *ex2;
4278 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
4279 	ext4_fsblk_t newblock = 0;
4280 	int free_on_err = 0, err = 0, depth, ret;
4281 	unsigned int allocated = 0, offset = 0;
4282 	unsigned int allocated_clusters = 0;
4283 	struct ext4_allocation_request ar;
4284 	ext4_lblk_t cluster_offset;
4285 	bool map_from_cluster = false;
4286 
4287 	ext_debug("blocks %u/%u requested for inode %lu\n",
4288 		  map->m_lblk, map->m_len, inode->i_ino);
4289 	trace_ext4_ext_map_blocks_enter(inode, map->m_lblk, map->m_len, flags);
4290 
4291 	/* find extent for this block */
4292 	path = ext4_find_extent(inode, map->m_lblk, NULL, 0);
4293 	if (IS_ERR(path)) {
4294 		err = PTR_ERR(path);
4295 		path = NULL;
4296 		goto out2;
4297 	}
4298 
4299 	depth = ext_depth(inode);
4300 
4301 	/*
4302 	 * consistent leaf must not be empty;
4303 	 * this situation is possible, though, _during_ tree modification;
4304 	 * this is why assert can't be put in ext4_find_extent()
4305 	 */
4306 	if (unlikely(path[depth].p_ext == NULL && depth != 0)) {
4307 		EXT4_ERROR_INODE(inode, "bad extent address "
4308 				 "lblock: %lu, depth: %d pblock %lld",
4309 				 (unsigned long) map->m_lblk, depth,
4310 				 path[depth].p_block);
4311 		err = -EFSCORRUPTED;
4312 		goto out2;
4313 	}
4314 
4315 	ex = path[depth].p_ext;
4316 	if (ex) {
4317 		ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
4318 		ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
4319 		unsigned short ee_len;
4320 
4321 
4322 		/*
4323 		 * unwritten extents are treated as holes, except that
4324 		 * we split out initialized portions during a write.
4325 		 */
4326 		ee_len = ext4_ext_get_actual_len(ex);
4327 
4328 		trace_ext4_ext_show_extent(inode, ee_block, ee_start, ee_len);
4329 
4330 		/* if found extent covers block, simply return it */
4331 		if (in_range(map->m_lblk, ee_block, ee_len)) {
4332 			newblock = map->m_lblk - ee_block + ee_start;
4333 			/* number of remaining blocks in the extent */
4334 			allocated = ee_len - (map->m_lblk - ee_block);
4335 			ext_debug("%u fit into %u:%d -> %llu\n", map->m_lblk,
4336 				  ee_block, ee_len, newblock);
4337 
4338 			/*
4339 			 * If the extent is initialized check whether the
4340 			 * caller wants to convert it to unwritten.
4341 			 */
4342 			if ((!ext4_ext_is_unwritten(ex)) &&
4343 			    (flags & EXT4_GET_BLOCKS_CONVERT_UNWRITTEN)) {
4344 				allocated = convert_initialized_extent(
4345 						handle, inode, map, &path,
4346 						allocated);
4347 				goto out2;
4348 			} else if (!ext4_ext_is_unwritten(ex))
4349 				goto out;
4350 
4351 			ret = ext4_ext_handle_unwritten_extents(
4352 				handle, inode, map, &path, flags,
4353 				allocated, newblock);
4354 			if (ret < 0)
4355 				err = ret;
4356 			else
4357 				allocated = ret;
4358 			goto out2;
4359 		}
4360 	}
4361 
4362 	/*
4363 	 * requested block isn't allocated yet;
4364 	 * we couldn't try to create block if create flag is zero
4365 	 */
4366 	if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
4367 		ext4_lblk_t hole_start, hole_len;
4368 
4369 		hole_start = map->m_lblk;
4370 		hole_len = ext4_ext_determine_hole(inode, path, &hole_start);
4371 		/*
4372 		 * put just found gap into cache to speed up
4373 		 * subsequent requests
4374 		 */
4375 		ext4_ext_put_gap_in_cache(inode, hole_start, hole_len);
4376 
4377 		/* Update hole_len to reflect hole size after map->m_lblk */
4378 		if (hole_start != map->m_lblk)
4379 			hole_len -= map->m_lblk - hole_start;
4380 		map->m_pblk = 0;
4381 		map->m_len = min_t(unsigned int, map->m_len, hole_len);
4382 
4383 		goto out2;
4384 	}
4385 
4386 	/*
4387 	 * Okay, we need to do block allocation.
4388 	 */
4389 	newex.ee_block = cpu_to_le32(map->m_lblk);
4390 	cluster_offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4391 
4392 	/*
4393 	 * If we are doing bigalloc, check to see if the extent returned
4394 	 * by ext4_find_extent() implies a cluster we can use.
4395 	 */
4396 	if (cluster_offset && ex &&
4397 	    get_implied_cluster_alloc(inode->i_sb, map, ex, path)) {
4398 		ar.len = allocated = map->m_len;
4399 		newblock = map->m_pblk;
4400 		map_from_cluster = true;
4401 		goto got_allocated_blocks;
4402 	}
4403 
4404 	/* find neighbour allocated blocks */
4405 	ar.lleft = map->m_lblk;
4406 	err = ext4_ext_search_left(inode, path, &ar.lleft, &ar.pleft);
4407 	if (err)
4408 		goto out2;
4409 	ar.lright = map->m_lblk;
4410 	ex2 = NULL;
4411 	err = ext4_ext_search_right(inode, path, &ar.lright, &ar.pright, &ex2);
4412 	if (err)
4413 		goto out2;
4414 
4415 	/* Check if the extent after searching to the right implies a
4416 	 * cluster we can use. */
4417 	if ((sbi->s_cluster_ratio > 1) && ex2 &&
4418 	    get_implied_cluster_alloc(inode->i_sb, map, ex2, path)) {
4419 		ar.len = allocated = map->m_len;
4420 		newblock = map->m_pblk;
4421 		map_from_cluster = true;
4422 		goto got_allocated_blocks;
4423 	}
4424 
4425 	/*
4426 	 * See if request is beyond maximum number of blocks we can have in
4427 	 * a single extent. For an initialized extent this limit is
4428 	 * EXT_INIT_MAX_LEN and for an unwritten extent this limit is
4429 	 * EXT_UNWRITTEN_MAX_LEN.
4430 	 */
4431 	if (map->m_len > EXT_INIT_MAX_LEN &&
4432 	    !(flags & EXT4_GET_BLOCKS_UNWRIT_EXT))
4433 		map->m_len = EXT_INIT_MAX_LEN;
4434 	else if (map->m_len > EXT_UNWRITTEN_MAX_LEN &&
4435 		 (flags & EXT4_GET_BLOCKS_UNWRIT_EXT))
4436 		map->m_len = EXT_UNWRITTEN_MAX_LEN;
4437 
4438 	/* Check if we can really insert (m_lblk)::(m_lblk + m_len) extent */
4439 	newex.ee_len = cpu_to_le16(map->m_len);
4440 	err = ext4_ext_check_overlap(sbi, inode, &newex, path);
4441 	if (err)
4442 		allocated = ext4_ext_get_actual_len(&newex);
4443 	else
4444 		allocated = map->m_len;
4445 
4446 	/* allocate new block */
4447 	ar.inode = inode;
4448 	ar.goal = ext4_ext_find_goal(inode, path, map->m_lblk);
4449 	ar.logical = map->m_lblk;
4450 	/*
4451 	 * We calculate the offset from the beginning of the cluster
4452 	 * for the logical block number, since when we allocate a
4453 	 * physical cluster, the physical block should start at the
4454 	 * same offset from the beginning of the cluster.  This is
4455 	 * needed so that future calls to get_implied_cluster_alloc()
4456 	 * work correctly.
4457 	 */
4458 	offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4459 	ar.len = EXT4_NUM_B2C(sbi, offset+allocated);
4460 	ar.goal -= offset;
4461 	ar.logical -= offset;
4462 	if (S_ISREG(inode->i_mode))
4463 		ar.flags = EXT4_MB_HINT_DATA;
4464 	else
4465 		/* disable in-core preallocation for non-regular files */
4466 		ar.flags = 0;
4467 	if (flags & EXT4_GET_BLOCKS_NO_NORMALIZE)
4468 		ar.flags |= EXT4_MB_HINT_NOPREALLOC;
4469 	if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
4470 		ar.flags |= EXT4_MB_DELALLOC_RESERVED;
4471 	if (flags & EXT4_GET_BLOCKS_METADATA_NOFAIL)
4472 		ar.flags |= EXT4_MB_USE_RESERVED;
4473 	newblock = ext4_mb_new_blocks(handle, &ar, &err);
4474 	if (!newblock)
4475 		goto out2;
4476 	ext_debug("allocate new block: goal %llu, found %llu/%u\n",
4477 		  ar.goal, newblock, allocated);
4478 	free_on_err = 1;
4479 	allocated_clusters = ar.len;
4480 	ar.len = EXT4_C2B(sbi, ar.len) - offset;
4481 	if (ar.len > allocated)
4482 		ar.len = allocated;
4483 
4484 got_allocated_blocks:
4485 	/* try to insert new extent into found leaf and return */
4486 	ext4_ext_store_pblock(&newex, newblock + offset);
4487 	newex.ee_len = cpu_to_le16(ar.len);
4488 	/* Mark unwritten */
4489 	if (flags & EXT4_GET_BLOCKS_UNWRIT_EXT){
4490 		ext4_ext_mark_unwritten(&newex);
4491 		map->m_flags |= EXT4_MAP_UNWRITTEN;
4492 	}
4493 
4494 	err = 0;
4495 	if ((flags & EXT4_GET_BLOCKS_KEEP_SIZE) == 0)
4496 		err = check_eofblocks_fl(handle, inode, map->m_lblk,
4497 					 path, ar.len);
4498 	if (!err)
4499 		err = ext4_ext_insert_extent(handle, inode, &path,
4500 					     &newex, flags);
4501 
4502 	if (err && free_on_err) {
4503 		int fb_flags = flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE ?
4504 			EXT4_FREE_BLOCKS_NO_QUOT_UPDATE : 0;
4505 		/* free data blocks we just allocated */
4506 		/* not a good idea to call discard here directly,
4507 		 * but otherwise we'd need to call it every free() */
4508 		ext4_discard_preallocations(inode);
4509 		ext4_free_blocks(handle, inode, NULL, newblock,
4510 				 EXT4_C2B(sbi, allocated_clusters), fb_flags);
4511 		goto out2;
4512 	}
4513 
4514 	/* previous routine could use block we allocated */
4515 	newblock = ext4_ext_pblock(&newex);
4516 	allocated = ext4_ext_get_actual_len(&newex);
4517 	if (allocated > map->m_len)
4518 		allocated = map->m_len;
4519 	map->m_flags |= EXT4_MAP_NEW;
4520 
4521 	/*
4522 	 * Update reserved blocks/metadata blocks after successful
4523 	 * block allocation which had been deferred till now.
4524 	 */
4525 	if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE) {
4526 		unsigned int reserved_clusters;
4527 		/*
4528 		 * Check how many clusters we had reserved this allocated range
4529 		 */
4530 		reserved_clusters = get_reserved_cluster_alloc(inode,
4531 						map->m_lblk, allocated);
4532 		if (!map_from_cluster) {
4533 			BUG_ON(allocated_clusters < reserved_clusters);
4534 			if (reserved_clusters < allocated_clusters) {
4535 				struct ext4_inode_info *ei = EXT4_I(inode);
4536 				int reservation = allocated_clusters -
4537 						  reserved_clusters;
4538 				/*
4539 				 * It seems we claimed few clusters outside of
4540 				 * the range of this allocation. We should give
4541 				 * it back to the reservation pool. This can
4542 				 * happen in the following case:
4543 				 *
4544 				 * * Suppose s_cluster_ratio is 4 (i.e., each
4545 				 *   cluster has 4 blocks. Thus, the clusters
4546 				 *   are [0-3],[4-7],[8-11]...
4547 				 * * First comes delayed allocation write for
4548 				 *   logical blocks 10 & 11. Since there were no
4549 				 *   previous delayed allocated blocks in the
4550 				 *   range [8-11], we would reserve 1 cluster
4551 				 *   for this write.
4552 				 * * Next comes write for logical blocks 3 to 8.
4553 				 *   In this case, we will reserve 2 clusters
4554 				 *   (for [0-3] and [4-7]; and not for [8-11] as
4555 				 *   that range has a delayed allocated blocks.
4556 				 *   Thus total reserved clusters now becomes 3.
4557 				 * * Now, during the delayed allocation writeout
4558 				 *   time, we will first write blocks [3-8] and
4559 				 *   allocate 3 clusters for writing these
4560 				 *   blocks. Also, we would claim all these
4561 				 *   three clusters above.
4562 				 * * Now when we come here to writeout the
4563 				 *   blocks [10-11], we would expect to claim
4564 				 *   the reservation of 1 cluster we had made
4565 				 *   (and we would claim it since there are no
4566 				 *   more delayed allocated blocks in the range
4567 				 *   [8-11]. But our reserved cluster count had
4568 				 *   already gone to 0.
4569 				 *
4570 				 *   Thus, at the step 4 above when we determine
4571 				 *   that there are still some unwritten delayed
4572 				 *   allocated blocks outside of our current
4573 				 *   block range, we should increment the
4574 				 *   reserved clusters count so that when the
4575 				 *   remaining blocks finally gets written, we
4576 				 *   could claim them.
4577 				 */
4578 				dquot_reserve_block(inode,
4579 						EXT4_C2B(sbi, reservation));
4580 				spin_lock(&ei->i_block_reservation_lock);
4581 				ei->i_reserved_data_blocks += reservation;
4582 				spin_unlock(&ei->i_block_reservation_lock);
4583 			}
4584 			/*
4585 			 * We will claim quota for all newly allocated blocks.
4586 			 * We're updating the reserved space *after* the
4587 			 * correction above so we do not accidentally free
4588 			 * all the metadata reservation because we might
4589 			 * actually need it later on.
4590 			 */
4591 			ext4_da_update_reserve_space(inode, allocated_clusters,
4592 							1);
4593 		}
4594 	}
4595 
4596 	/*
4597 	 * Cache the extent and update transaction to commit on fdatasync only
4598 	 * when it is _not_ an unwritten extent.
4599 	 */
4600 	if ((flags & EXT4_GET_BLOCKS_UNWRIT_EXT) == 0)
4601 		ext4_update_inode_fsync_trans(handle, inode, 1);
4602 	else
4603 		ext4_update_inode_fsync_trans(handle, inode, 0);
4604 out:
4605 	if (allocated > map->m_len)
4606 		allocated = map->m_len;
4607 	ext4_ext_show_leaf(inode, path);
4608 	map->m_flags |= EXT4_MAP_MAPPED;
4609 	map->m_pblk = newblock;
4610 	map->m_len = allocated;
4611 out2:
4612 	ext4_ext_drop_refs(path);
4613 	kfree(path);
4614 
4615 	trace_ext4_ext_map_blocks_exit(inode, flags, map,
4616 				       err ? err : allocated);
4617 	return err ? err : allocated;
4618 }
4619 
4620 int ext4_ext_truncate(handle_t *handle, struct inode *inode)
4621 {
4622 	struct super_block *sb = inode->i_sb;
4623 	ext4_lblk_t last_block;
4624 	int err = 0;
4625 
4626 	/*
4627 	 * TODO: optimization is possible here.
4628 	 * Probably we need not scan at all,
4629 	 * because page truncation is enough.
4630 	 */
4631 
4632 	/* we have to know where to truncate from in crash case */
4633 	EXT4_I(inode)->i_disksize = inode->i_size;
4634 	err = ext4_mark_inode_dirty(handle, inode);
4635 	if (err)
4636 		return err;
4637 
4638 	last_block = (inode->i_size + sb->s_blocksize - 1)
4639 			>> EXT4_BLOCK_SIZE_BITS(sb);
4640 retry:
4641 	err = ext4_es_remove_extent(inode, last_block,
4642 				    EXT_MAX_BLOCKS - last_block);
4643 	if (err == -ENOMEM) {
4644 		cond_resched();
4645 		congestion_wait(BLK_RW_ASYNC, HZ/50);
4646 		goto retry;
4647 	}
4648 	if (err)
4649 		return err;
4650 	return ext4_ext_remove_space(inode, last_block, EXT_MAX_BLOCKS - 1);
4651 }
4652 
4653 static int ext4_alloc_file_blocks(struct file *file, ext4_lblk_t offset,
4654 				  ext4_lblk_t len, loff_t new_size,
4655 				  int flags)
4656 {
4657 	struct inode *inode = file_inode(file);
4658 	handle_t *handle;
4659 	int ret = 0;
4660 	int ret2 = 0;
4661 	int retries = 0;
4662 	int depth = 0;
4663 	struct ext4_map_blocks map;
4664 	unsigned int credits;
4665 	loff_t epos;
4666 
4667 	BUG_ON(!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS));
4668 	map.m_lblk = offset;
4669 	map.m_len = len;
4670 	/*
4671 	 * Don't normalize the request if it can fit in one extent so
4672 	 * that it doesn't get unnecessarily split into multiple
4673 	 * extents.
4674 	 */
4675 	if (len <= EXT_UNWRITTEN_MAX_LEN)
4676 		flags |= EXT4_GET_BLOCKS_NO_NORMALIZE;
4677 
4678 	/*
4679 	 * credits to insert 1 extent into extent tree
4680 	 */
4681 	credits = ext4_chunk_trans_blocks(inode, len);
4682 	depth = ext_depth(inode);
4683 
4684 retry:
4685 	while (ret >= 0 && len) {
4686 		/*
4687 		 * Recalculate credits when extent tree depth changes.
4688 		 */
4689 		if (depth != ext_depth(inode)) {
4690 			credits = ext4_chunk_trans_blocks(inode, len);
4691 			depth = ext_depth(inode);
4692 		}
4693 
4694 		handle = ext4_journal_start(inode, EXT4_HT_MAP_BLOCKS,
4695 					    credits);
4696 		if (IS_ERR(handle)) {
4697 			ret = PTR_ERR(handle);
4698 			break;
4699 		}
4700 		ret = ext4_map_blocks(handle, inode, &map, flags);
4701 		if (ret <= 0) {
4702 			ext4_debug("inode #%lu: block %u: len %u: "
4703 				   "ext4_ext_map_blocks returned %d",
4704 				   inode->i_ino, map.m_lblk,
4705 				   map.m_len, ret);
4706 			ext4_mark_inode_dirty(handle, inode);
4707 			ret2 = ext4_journal_stop(handle);
4708 			break;
4709 		}
4710 		map.m_lblk += ret;
4711 		map.m_len = len = len - ret;
4712 		epos = (loff_t)map.m_lblk << inode->i_blkbits;
4713 		inode->i_ctime = current_time(inode);
4714 		if (new_size) {
4715 			if (epos > new_size)
4716 				epos = new_size;
4717 			if (ext4_update_inode_size(inode, epos) & 0x1)
4718 				inode->i_mtime = inode->i_ctime;
4719 		} else {
4720 			if (epos > inode->i_size)
4721 				ext4_set_inode_flag(inode,
4722 						    EXT4_INODE_EOFBLOCKS);
4723 		}
4724 		ext4_mark_inode_dirty(handle, inode);
4725 		ext4_update_inode_fsync_trans(handle, inode, 1);
4726 		ret2 = ext4_journal_stop(handle);
4727 		if (ret2)
4728 			break;
4729 	}
4730 	if (ret == -ENOSPC &&
4731 			ext4_should_retry_alloc(inode->i_sb, &retries)) {
4732 		ret = 0;
4733 		goto retry;
4734 	}
4735 
4736 	return ret > 0 ? ret2 : ret;
4737 }
4738 
4739 static long ext4_zero_range(struct file *file, loff_t offset,
4740 			    loff_t len, int mode)
4741 {
4742 	struct inode *inode = file_inode(file);
4743 	handle_t *handle = NULL;
4744 	unsigned int max_blocks;
4745 	loff_t new_size = 0;
4746 	int ret = 0;
4747 	int flags;
4748 	int credits;
4749 	int partial_begin, partial_end;
4750 	loff_t start, end;
4751 	ext4_lblk_t lblk;
4752 	unsigned int blkbits = inode->i_blkbits;
4753 
4754 	trace_ext4_zero_range(inode, offset, len, mode);
4755 
4756 	if (!S_ISREG(inode->i_mode))
4757 		return -EINVAL;
4758 
4759 	/* Call ext4_force_commit to flush all data in case of data=journal. */
4760 	if (ext4_should_journal_data(inode)) {
4761 		ret = ext4_force_commit(inode->i_sb);
4762 		if (ret)
4763 			return ret;
4764 	}
4765 
4766 	/*
4767 	 * Round up offset. This is not fallocate, we neet to zero out
4768 	 * blocks, so convert interior block aligned part of the range to
4769 	 * unwritten and possibly manually zero out unaligned parts of the
4770 	 * range.
4771 	 */
4772 	start = round_up(offset, 1 << blkbits);
4773 	end = round_down((offset + len), 1 << blkbits);
4774 
4775 	if (start < offset || end > offset + len)
4776 		return -EINVAL;
4777 	partial_begin = offset & ((1 << blkbits) - 1);
4778 	partial_end = (offset + len) & ((1 << blkbits) - 1);
4779 
4780 	lblk = start >> blkbits;
4781 	max_blocks = (end >> blkbits);
4782 	if (max_blocks < lblk)
4783 		max_blocks = 0;
4784 	else
4785 		max_blocks -= lblk;
4786 
4787 	inode_lock(inode);
4788 
4789 	/*
4790 	 * Indirect files do not support unwritten extnets
4791 	 */
4792 	if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))) {
4793 		ret = -EOPNOTSUPP;
4794 		goto out_mutex;
4795 	}
4796 
4797 	if (!(mode & FALLOC_FL_KEEP_SIZE) &&
4798 	    (offset + len > i_size_read(inode) ||
4799 	     offset + len > EXT4_I(inode)->i_disksize)) {
4800 		new_size = offset + len;
4801 		ret = inode_newsize_ok(inode, new_size);
4802 		if (ret)
4803 			goto out_mutex;
4804 	}
4805 
4806 	flags = EXT4_GET_BLOCKS_CREATE_UNWRIT_EXT;
4807 	if (mode & FALLOC_FL_KEEP_SIZE)
4808 		flags |= EXT4_GET_BLOCKS_KEEP_SIZE;
4809 
4810 	/* Wait all existing dio workers, newcomers will block on i_mutex */
4811 	ext4_inode_block_unlocked_dio(inode);
4812 	inode_dio_wait(inode);
4813 
4814 	/* Preallocate the range including the unaligned edges */
4815 	if (partial_begin || partial_end) {
4816 		ret = ext4_alloc_file_blocks(file,
4817 				round_down(offset, 1 << blkbits) >> blkbits,
4818 				(round_up((offset + len), 1 << blkbits) -
4819 				 round_down(offset, 1 << blkbits)) >> blkbits,
4820 				new_size, flags);
4821 		if (ret)
4822 			goto out_dio;
4823 
4824 	}
4825 
4826 	/* Zero range excluding the unaligned edges */
4827 	if (max_blocks > 0) {
4828 		flags |= (EXT4_GET_BLOCKS_CONVERT_UNWRITTEN |
4829 			  EXT4_EX_NOCACHE);
4830 
4831 		/*
4832 		 * Prevent page faults from reinstantiating pages we have
4833 		 * released from page cache.
4834 		 */
4835 		down_write(&EXT4_I(inode)->i_mmap_sem);
4836 		ret = ext4_update_disksize_before_punch(inode, offset, len);
4837 		if (ret) {
4838 			up_write(&EXT4_I(inode)->i_mmap_sem);
4839 			goto out_dio;
4840 		}
4841 		/* Now release the pages and zero block aligned part of pages */
4842 		truncate_pagecache_range(inode, start, end - 1);
4843 		inode->i_mtime = inode->i_ctime = current_time(inode);
4844 
4845 		ret = ext4_alloc_file_blocks(file, lblk, max_blocks, new_size,
4846 					     flags);
4847 		up_write(&EXT4_I(inode)->i_mmap_sem);
4848 		if (ret)
4849 			goto out_dio;
4850 	}
4851 	if (!partial_begin && !partial_end)
4852 		goto out_dio;
4853 
4854 	/*
4855 	 * In worst case we have to writeout two nonadjacent unwritten
4856 	 * blocks and update the inode
4857 	 */
4858 	credits = (2 * ext4_ext_index_trans_blocks(inode, 2)) + 1;
4859 	if (ext4_should_journal_data(inode))
4860 		credits += 2;
4861 	handle = ext4_journal_start(inode, EXT4_HT_MISC, credits);
4862 	if (IS_ERR(handle)) {
4863 		ret = PTR_ERR(handle);
4864 		ext4_std_error(inode->i_sb, ret);
4865 		goto out_dio;
4866 	}
4867 
4868 	inode->i_mtime = inode->i_ctime = current_time(inode);
4869 	if (new_size) {
4870 		ext4_update_inode_size(inode, new_size);
4871 	} else {
4872 		/*
4873 		* Mark that we allocate beyond EOF so the subsequent truncate
4874 		* can proceed even if the new size is the same as i_size.
4875 		*/
4876 		if ((offset + len) > i_size_read(inode))
4877 			ext4_set_inode_flag(inode, EXT4_INODE_EOFBLOCKS);
4878 	}
4879 	ext4_mark_inode_dirty(handle, inode);
4880 
4881 	/* Zero out partial block at the edges of the range */
4882 	ret = ext4_zero_partial_blocks(handle, inode, offset, len);
4883 	if (ret >= 0)
4884 		ext4_update_inode_fsync_trans(handle, inode, 1);
4885 
4886 	if (file->f_flags & O_SYNC)
4887 		ext4_handle_sync(handle);
4888 
4889 	ext4_journal_stop(handle);
4890 out_dio:
4891 	ext4_inode_resume_unlocked_dio(inode);
4892 out_mutex:
4893 	inode_unlock(inode);
4894 	return ret;
4895 }
4896 
4897 /*
4898  * preallocate space for a file. This implements ext4's fallocate file
4899  * operation, which gets called from sys_fallocate system call.
4900  * For block-mapped files, posix_fallocate should fall back to the method
4901  * of writing zeroes to the required new blocks (the same behavior which is
4902  * expected for file systems which do not support fallocate() system call).
4903  */
4904 long ext4_fallocate(struct file *file, int mode, loff_t offset, loff_t len)
4905 {
4906 	struct inode *inode = file_inode(file);
4907 	loff_t new_size = 0;
4908 	unsigned int max_blocks;
4909 	int ret = 0;
4910 	int flags;
4911 	ext4_lblk_t lblk;
4912 	unsigned int blkbits = inode->i_blkbits;
4913 
4914 	/*
4915 	 * Encrypted inodes can't handle collapse range or insert
4916 	 * range since we would need to re-encrypt blocks with a
4917 	 * different IV or XTS tweak (which are based on the logical
4918 	 * block number).
4919 	 *
4920 	 * XXX It's not clear why zero range isn't working, but we'll
4921 	 * leave it disabled for encrypted inodes for now.  This is a
4922 	 * bug we should fix....
4923 	 */
4924 	if (ext4_encrypted_inode(inode) &&
4925 	    (mode & (FALLOC_FL_COLLAPSE_RANGE | FALLOC_FL_INSERT_RANGE |
4926 		     FALLOC_FL_ZERO_RANGE)))
4927 		return -EOPNOTSUPP;
4928 
4929 	/* Return error if mode is not supported */
4930 	if (mode & ~(FALLOC_FL_KEEP_SIZE | FALLOC_FL_PUNCH_HOLE |
4931 		     FALLOC_FL_COLLAPSE_RANGE | FALLOC_FL_ZERO_RANGE |
4932 		     FALLOC_FL_INSERT_RANGE))
4933 		return -EOPNOTSUPP;
4934 
4935 	if (mode & FALLOC_FL_PUNCH_HOLE)
4936 		return ext4_punch_hole(inode, offset, len);
4937 
4938 	ret = ext4_convert_inline_data(inode);
4939 	if (ret)
4940 		return ret;
4941 
4942 	if (mode & FALLOC_FL_COLLAPSE_RANGE)
4943 		return ext4_collapse_range(inode, offset, len);
4944 
4945 	if (mode & FALLOC_FL_INSERT_RANGE)
4946 		return ext4_insert_range(inode, offset, len);
4947 
4948 	if (mode & FALLOC_FL_ZERO_RANGE)
4949 		return ext4_zero_range(file, offset, len, mode);
4950 
4951 	trace_ext4_fallocate_enter(inode, offset, len, mode);
4952 	lblk = offset >> blkbits;
4953 
4954 	max_blocks = EXT4_MAX_BLOCKS(len, offset, blkbits);
4955 	flags = EXT4_GET_BLOCKS_CREATE_UNWRIT_EXT;
4956 	if (mode & FALLOC_FL_KEEP_SIZE)
4957 		flags |= EXT4_GET_BLOCKS_KEEP_SIZE;
4958 
4959 	inode_lock(inode);
4960 
4961 	/*
4962 	 * We only support preallocation for extent-based files only
4963 	 */
4964 	if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))) {
4965 		ret = -EOPNOTSUPP;
4966 		goto out;
4967 	}
4968 
4969 	if (!(mode & FALLOC_FL_KEEP_SIZE) &&
4970 	    (offset + len > i_size_read(inode) ||
4971 	     offset + len > EXT4_I(inode)->i_disksize)) {
4972 		new_size = offset + len;
4973 		ret = inode_newsize_ok(inode, new_size);
4974 		if (ret)
4975 			goto out;
4976 	}
4977 
4978 	/* Wait all existing dio workers, newcomers will block on i_mutex */
4979 	ext4_inode_block_unlocked_dio(inode);
4980 	inode_dio_wait(inode);
4981 
4982 	ret = ext4_alloc_file_blocks(file, lblk, max_blocks, new_size, flags);
4983 	ext4_inode_resume_unlocked_dio(inode);
4984 	if (ret)
4985 		goto out;
4986 
4987 	if (file->f_flags & O_SYNC && EXT4_SB(inode->i_sb)->s_journal) {
4988 		ret = jbd2_complete_transaction(EXT4_SB(inode->i_sb)->s_journal,
4989 						EXT4_I(inode)->i_sync_tid);
4990 	}
4991 out:
4992 	inode_unlock(inode);
4993 	trace_ext4_fallocate_exit(inode, offset, max_blocks, ret);
4994 	return ret;
4995 }
4996 
4997 /*
4998  * This function convert a range of blocks to written extents
4999  * The caller of this function will pass the start offset and the size.
5000  * all unwritten extents within this range will be converted to
5001  * written extents.
5002  *
5003  * This function is called from the direct IO end io call back
5004  * function, to convert the fallocated extents after IO is completed.
5005  * Returns 0 on success.
5006  */
5007 int ext4_convert_unwritten_extents(handle_t *handle, struct inode *inode,
5008 				   loff_t offset, ssize_t len)
5009 {
5010 	unsigned int max_blocks;
5011 	int ret = 0;
5012 	int ret2 = 0;
5013 	struct ext4_map_blocks map;
5014 	unsigned int credits, blkbits = inode->i_blkbits;
5015 
5016 	map.m_lblk = offset >> blkbits;
5017 	max_blocks = EXT4_MAX_BLOCKS(len, offset, blkbits);
5018 
5019 	/*
5020 	 * This is somewhat ugly but the idea is clear: When transaction is
5021 	 * reserved, everything goes into it. Otherwise we rather start several
5022 	 * smaller transactions for conversion of each extent separately.
5023 	 */
5024 	if (handle) {
5025 		handle = ext4_journal_start_reserved(handle,
5026 						     EXT4_HT_EXT_CONVERT);
5027 		if (IS_ERR(handle))
5028 			return PTR_ERR(handle);
5029 		credits = 0;
5030 	} else {
5031 		/*
5032 		 * credits to insert 1 extent into extent tree
5033 		 */
5034 		credits = ext4_chunk_trans_blocks(inode, max_blocks);
5035 	}
5036 	while (ret >= 0 && ret < max_blocks) {
5037 		map.m_lblk += ret;
5038 		map.m_len = (max_blocks -= ret);
5039 		if (credits) {
5040 			handle = ext4_journal_start(inode, EXT4_HT_MAP_BLOCKS,
5041 						    credits);
5042 			if (IS_ERR(handle)) {
5043 				ret = PTR_ERR(handle);
5044 				break;
5045 			}
5046 		}
5047 		ret = ext4_map_blocks(handle, inode, &map,
5048 				      EXT4_GET_BLOCKS_IO_CONVERT_EXT);
5049 		if (ret <= 0)
5050 			ext4_warning(inode->i_sb,
5051 				     "inode #%lu: block %u: len %u: "
5052 				     "ext4_ext_map_blocks returned %d",
5053 				     inode->i_ino, map.m_lblk,
5054 				     map.m_len, ret);
5055 		ext4_mark_inode_dirty(handle, inode);
5056 		if (credits)
5057 			ret2 = ext4_journal_stop(handle);
5058 		if (ret <= 0 || ret2)
5059 			break;
5060 	}
5061 	if (!credits)
5062 		ret2 = ext4_journal_stop(handle);
5063 	return ret > 0 ? ret2 : ret;
5064 }
5065 
5066 /*
5067  * If newes is not existing extent (newes->ec_pblk equals zero) find
5068  * delayed extent at start of newes and update newes accordingly and
5069  * return start of the next delayed extent.
5070  *
5071  * If newes is existing extent (newes->ec_pblk is not equal zero)
5072  * return start of next delayed extent or EXT_MAX_BLOCKS if no delayed
5073  * extent found. Leave newes unmodified.
5074  */
5075 static int ext4_find_delayed_extent(struct inode *inode,
5076 				    struct extent_status *newes)
5077 {
5078 	struct extent_status es;
5079 	ext4_lblk_t block, next_del;
5080 
5081 	if (newes->es_pblk == 0) {
5082 		ext4_es_find_delayed_extent_range(inode, newes->es_lblk,
5083 				newes->es_lblk + newes->es_len - 1, &es);
5084 
5085 		/*
5086 		 * No extent in extent-tree contains block @newes->es_pblk,
5087 		 * then the block may stay in 1)a hole or 2)delayed-extent.
5088 		 */
5089 		if (es.es_len == 0)
5090 			/* A hole found. */
5091 			return 0;
5092 
5093 		if (es.es_lblk > newes->es_lblk) {
5094 			/* A hole found. */
5095 			newes->es_len = min(es.es_lblk - newes->es_lblk,
5096 					    newes->es_len);
5097 			return 0;
5098 		}
5099 
5100 		newes->es_len = es.es_lblk + es.es_len - newes->es_lblk;
5101 	}
5102 
5103 	block = newes->es_lblk + newes->es_len;
5104 	ext4_es_find_delayed_extent_range(inode, block, EXT_MAX_BLOCKS, &es);
5105 	if (es.es_len == 0)
5106 		next_del = EXT_MAX_BLOCKS;
5107 	else
5108 		next_del = es.es_lblk;
5109 
5110 	return next_del;
5111 }
5112 /* fiemap flags we can handle specified here */
5113 #define EXT4_FIEMAP_FLAGS	(FIEMAP_FLAG_SYNC|FIEMAP_FLAG_XATTR)
5114 
5115 static int ext4_xattr_fiemap(struct inode *inode,
5116 				struct fiemap_extent_info *fieinfo)
5117 {
5118 	__u64 physical = 0;
5119 	__u64 length;
5120 	__u32 flags = FIEMAP_EXTENT_LAST;
5121 	int blockbits = inode->i_sb->s_blocksize_bits;
5122 	int error = 0;
5123 
5124 	/* in-inode? */
5125 	if (ext4_test_inode_state(inode, EXT4_STATE_XATTR)) {
5126 		struct ext4_iloc iloc;
5127 		int offset;	/* offset of xattr in inode */
5128 
5129 		error = ext4_get_inode_loc(inode, &iloc);
5130 		if (error)
5131 			return error;
5132 		physical = (__u64)iloc.bh->b_blocknr << blockbits;
5133 		offset = EXT4_GOOD_OLD_INODE_SIZE +
5134 				EXT4_I(inode)->i_extra_isize;
5135 		physical += offset;
5136 		length = EXT4_SB(inode->i_sb)->s_inode_size - offset;
5137 		flags |= FIEMAP_EXTENT_DATA_INLINE;
5138 		brelse(iloc.bh);
5139 	} else { /* external block */
5140 		physical = (__u64)EXT4_I(inode)->i_file_acl << blockbits;
5141 		length = inode->i_sb->s_blocksize;
5142 	}
5143 
5144 	if (physical)
5145 		error = fiemap_fill_next_extent(fieinfo, 0, physical,
5146 						length, flags);
5147 	return (error < 0 ? error : 0);
5148 }
5149 
5150 int ext4_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
5151 		__u64 start, __u64 len)
5152 {
5153 	ext4_lblk_t start_blk;
5154 	int error = 0;
5155 
5156 	if (ext4_has_inline_data(inode)) {
5157 		int has_inline = 1;
5158 
5159 		error = ext4_inline_data_fiemap(inode, fieinfo, &has_inline,
5160 						start, len);
5161 
5162 		if (has_inline)
5163 			return error;
5164 	}
5165 
5166 	if (fieinfo->fi_flags & FIEMAP_FLAG_CACHE) {
5167 		error = ext4_ext_precache(inode);
5168 		if (error)
5169 			return error;
5170 	}
5171 
5172 	/* fallback to generic here if not in extents fmt */
5173 	if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)))
5174 		return generic_block_fiemap(inode, fieinfo, start, len,
5175 			ext4_get_block);
5176 
5177 	if (fiemap_check_flags(fieinfo, EXT4_FIEMAP_FLAGS))
5178 		return -EBADR;
5179 
5180 	if (fieinfo->fi_flags & FIEMAP_FLAG_XATTR) {
5181 		error = ext4_xattr_fiemap(inode, fieinfo);
5182 	} else {
5183 		ext4_lblk_t len_blks;
5184 		__u64 last_blk;
5185 
5186 		start_blk = start >> inode->i_sb->s_blocksize_bits;
5187 		last_blk = (start + len - 1) >> inode->i_sb->s_blocksize_bits;
5188 		if (last_blk >= EXT_MAX_BLOCKS)
5189 			last_blk = EXT_MAX_BLOCKS-1;
5190 		len_blks = ((ext4_lblk_t) last_blk) - start_blk + 1;
5191 
5192 		/*
5193 		 * Walk the extent tree gathering extent information
5194 		 * and pushing extents back to the user.
5195 		 */
5196 		error = ext4_fill_fiemap_extents(inode, start_blk,
5197 						 len_blks, fieinfo);
5198 	}
5199 	return error;
5200 }
5201 
5202 /*
5203  * ext4_access_path:
5204  * Function to access the path buffer for marking it dirty.
5205  * It also checks if there are sufficient credits left in the journal handle
5206  * to update path.
5207  */
5208 static int
5209 ext4_access_path(handle_t *handle, struct inode *inode,
5210 		struct ext4_ext_path *path)
5211 {
5212 	int credits, err;
5213 
5214 	if (!ext4_handle_valid(handle))
5215 		return 0;
5216 
5217 	/*
5218 	 * Check if need to extend journal credits
5219 	 * 3 for leaf, sb, and inode plus 2 (bmap and group
5220 	 * descriptor) for each block group; assume two block
5221 	 * groups
5222 	 */
5223 	if (handle->h_buffer_credits < 7) {
5224 		credits = ext4_writepage_trans_blocks(inode);
5225 		err = ext4_ext_truncate_extend_restart(handle, inode, credits);
5226 		/* EAGAIN is success */
5227 		if (err && err != -EAGAIN)
5228 			return err;
5229 	}
5230 
5231 	err = ext4_ext_get_access(handle, inode, path);
5232 	return err;
5233 }
5234 
5235 /*
5236  * ext4_ext_shift_path_extents:
5237  * Shift the extents of a path structure lying between path[depth].p_ext
5238  * and EXT_LAST_EXTENT(path[depth].p_hdr), by @shift blocks. @SHIFT tells
5239  * if it is right shift or left shift operation.
5240  */
5241 static int
5242 ext4_ext_shift_path_extents(struct ext4_ext_path *path, ext4_lblk_t shift,
5243 			    struct inode *inode, handle_t *handle,
5244 			    enum SHIFT_DIRECTION SHIFT)
5245 {
5246 	int depth, err = 0;
5247 	struct ext4_extent *ex_start, *ex_last;
5248 	bool update = 0;
5249 	depth = path->p_depth;
5250 
5251 	while (depth >= 0) {
5252 		if (depth == path->p_depth) {
5253 			ex_start = path[depth].p_ext;
5254 			if (!ex_start)
5255 				return -EFSCORRUPTED;
5256 
5257 			ex_last = EXT_LAST_EXTENT(path[depth].p_hdr);
5258 
5259 			err = ext4_access_path(handle, inode, path + depth);
5260 			if (err)
5261 				goto out;
5262 
5263 			if (ex_start == EXT_FIRST_EXTENT(path[depth].p_hdr))
5264 				update = 1;
5265 
5266 			while (ex_start <= ex_last) {
5267 				if (SHIFT == SHIFT_LEFT) {
5268 					le32_add_cpu(&ex_start->ee_block,
5269 						-shift);
5270 					/* Try to merge to the left. */
5271 					if ((ex_start >
5272 					    EXT_FIRST_EXTENT(path[depth].p_hdr))
5273 					    &&
5274 					    ext4_ext_try_to_merge_right(inode,
5275 					    path, ex_start - 1))
5276 						ex_last--;
5277 					else
5278 						ex_start++;
5279 				} else {
5280 					le32_add_cpu(&ex_last->ee_block, shift);
5281 					ext4_ext_try_to_merge_right(inode, path,
5282 						ex_last);
5283 					ex_last--;
5284 				}
5285 			}
5286 			err = ext4_ext_dirty(handle, inode, path + depth);
5287 			if (err)
5288 				goto out;
5289 
5290 			if (--depth < 0 || !update)
5291 				break;
5292 		}
5293 
5294 		/* Update index too */
5295 		err = ext4_access_path(handle, inode, path + depth);
5296 		if (err)
5297 			goto out;
5298 
5299 		if (SHIFT == SHIFT_LEFT)
5300 			le32_add_cpu(&path[depth].p_idx->ei_block, -shift);
5301 		else
5302 			le32_add_cpu(&path[depth].p_idx->ei_block, shift);
5303 		err = ext4_ext_dirty(handle, inode, path + depth);
5304 		if (err)
5305 			goto out;
5306 
5307 		/* we are done if current index is not a starting index */
5308 		if (path[depth].p_idx != EXT_FIRST_INDEX(path[depth].p_hdr))
5309 			break;
5310 
5311 		depth--;
5312 	}
5313 
5314 out:
5315 	return err;
5316 }
5317 
5318 /*
5319  * ext4_ext_shift_extents:
5320  * All the extents which lies in the range from @start to the last allocated
5321  * block for the @inode are shifted either towards left or right (depending
5322  * upon @SHIFT) by @shift blocks.
5323  * On success, 0 is returned, error otherwise.
5324  */
5325 static int
5326 ext4_ext_shift_extents(struct inode *inode, handle_t *handle,
5327 		       ext4_lblk_t start, ext4_lblk_t shift,
5328 		       enum SHIFT_DIRECTION SHIFT)
5329 {
5330 	struct ext4_ext_path *path;
5331 	int ret = 0, depth;
5332 	struct ext4_extent *extent;
5333 	ext4_lblk_t stop, *iterator, ex_start, ex_end;
5334 
5335 	/* Let path point to the last extent */
5336 	path = ext4_find_extent(inode, EXT_MAX_BLOCKS - 1, NULL,
5337 				EXT4_EX_NOCACHE);
5338 	if (IS_ERR(path))
5339 		return PTR_ERR(path);
5340 
5341 	depth = path->p_depth;
5342 	extent = path[depth].p_ext;
5343 	if (!extent)
5344 		goto out;
5345 
5346 	stop = le32_to_cpu(extent->ee_block);
5347 
5348        /*
5349 	 * In case of left shift, Don't start shifting extents until we make
5350 	 * sure the hole is big enough to accommodate the shift.
5351 	*/
5352 	if (SHIFT == SHIFT_LEFT) {
5353 		path = ext4_find_extent(inode, start - 1, &path,
5354 					EXT4_EX_NOCACHE);
5355 		if (IS_ERR(path))
5356 			return PTR_ERR(path);
5357 		depth = path->p_depth;
5358 		extent =  path[depth].p_ext;
5359 		if (extent) {
5360 			ex_start = le32_to_cpu(extent->ee_block);
5361 			ex_end = le32_to_cpu(extent->ee_block) +
5362 				ext4_ext_get_actual_len(extent);
5363 		} else {
5364 			ex_start = 0;
5365 			ex_end = 0;
5366 		}
5367 
5368 		if ((start == ex_start && shift > ex_start) ||
5369 		    (shift > start - ex_end)) {
5370 			ext4_ext_drop_refs(path);
5371 			kfree(path);
5372 			return -EINVAL;
5373 		}
5374 	}
5375 
5376 	/*
5377 	 * In case of left shift, iterator points to start and it is increased
5378 	 * till we reach stop. In case of right shift, iterator points to stop
5379 	 * and it is decreased till we reach start.
5380 	 */
5381 	if (SHIFT == SHIFT_LEFT)
5382 		iterator = &start;
5383 	else
5384 		iterator = &stop;
5385 
5386 	/*
5387 	 * Its safe to start updating extents.  Start and stop are unsigned, so
5388 	 * in case of right shift if extent with 0 block is reached, iterator
5389 	 * becomes NULL to indicate the end of the loop.
5390 	 */
5391 	while (iterator && start <= stop) {
5392 		path = ext4_find_extent(inode, *iterator, &path,
5393 					EXT4_EX_NOCACHE);
5394 		if (IS_ERR(path))
5395 			return PTR_ERR(path);
5396 		depth = path->p_depth;
5397 		extent = path[depth].p_ext;
5398 		if (!extent) {
5399 			EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
5400 					 (unsigned long) *iterator);
5401 			return -EFSCORRUPTED;
5402 		}
5403 		if (SHIFT == SHIFT_LEFT && *iterator >
5404 		    le32_to_cpu(extent->ee_block)) {
5405 			/* Hole, move to the next extent */
5406 			if (extent < EXT_LAST_EXTENT(path[depth].p_hdr)) {
5407 				path[depth].p_ext++;
5408 			} else {
5409 				*iterator = ext4_ext_next_allocated_block(path);
5410 				continue;
5411 			}
5412 		}
5413 
5414 		if (SHIFT == SHIFT_LEFT) {
5415 			extent = EXT_LAST_EXTENT(path[depth].p_hdr);
5416 			*iterator = le32_to_cpu(extent->ee_block) +
5417 					ext4_ext_get_actual_len(extent);
5418 		} else {
5419 			extent = EXT_FIRST_EXTENT(path[depth].p_hdr);
5420 			if (le32_to_cpu(extent->ee_block) > 0)
5421 				*iterator = le32_to_cpu(extent->ee_block) - 1;
5422 			else
5423 				/* Beginning is reached, end of the loop */
5424 				iterator = NULL;
5425 			/* Update path extent in case we need to stop */
5426 			while (le32_to_cpu(extent->ee_block) < start)
5427 				extent++;
5428 			path[depth].p_ext = extent;
5429 		}
5430 		ret = ext4_ext_shift_path_extents(path, shift, inode,
5431 				handle, SHIFT);
5432 		if (ret)
5433 			break;
5434 	}
5435 out:
5436 	ext4_ext_drop_refs(path);
5437 	kfree(path);
5438 	return ret;
5439 }
5440 
5441 /*
5442  * ext4_collapse_range:
5443  * This implements the fallocate's collapse range functionality for ext4
5444  * Returns: 0 and non-zero on error.
5445  */
5446 int ext4_collapse_range(struct inode *inode, loff_t offset, loff_t len)
5447 {
5448 	struct super_block *sb = inode->i_sb;
5449 	ext4_lblk_t punch_start, punch_stop;
5450 	handle_t *handle;
5451 	unsigned int credits;
5452 	loff_t new_size, ioffset;
5453 	int ret;
5454 
5455 	/*
5456 	 * We need to test this early because xfstests assumes that a
5457 	 * collapse range of (0, 1) will return EOPNOTSUPP if the file
5458 	 * system does not support collapse range.
5459 	 */
5460 	if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
5461 		return -EOPNOTSUPP;
5462 
5463 	/* Collapse range works only on fs block size aligned offsets. */
5464 	if (offset & (EXT4_CLUSTER_SIZE(sb) - 1) ||
5465 	    len & (EXT4_CLUSTER_SIZE(sb) - 1))
5466 		return -EINVAL;
5467 
5468 	if (!S_ISREG(inode->i_mode))
5469 		return -EINVAL;
5470 
5471 	trace_ext4_collapse_range(inode, offset, len);
5472 
5473 	punch_start = offset >> EXT4_BLOCK_SIZE_BITS(sb);
5474 	punch_stop = (offset + len) >> EXT4_BLOCK_SIZE_BITS(sb);
5475 
5476 	/* Call ext4_force_commit to flush all data in case of data=journal. */
5477 	if (ext4_should_journal_data(inode)) {
5478 		ret = ext4_force_commit(inode->i_sb);
5479 		if (ret)
5480 			return ret;
5481 	}
5482 
5483 	inode_lock(inode);
5484 	/*
5485 	 * There is no need to overlap collapse range with EOF, in which case
5486 	 * it is effectively a truncate operation
5487 	 */
5488 	if (offset + len >= i_size_read(inode)) {
5489 		ret = -EINVAL;
5490 		goto out_mutex;
5491 	}
5492 
5493 	/* Currently just for extent based files */
5494 	if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)) {
5495 		ret = -EOPNOTSUPP;
5496 		goto out_mutex;
5497 	}
5498 
5499 	/* Wait for existing dio to complete */
5500 	ext4_inode_block_unlocked_dio(inode);
5501 	inode_dio_wait(inode);
5502 
5503 	/*
5504 	 * Prevent page faults from reinstantiating pages we have released from
5505 	 * page cache.
5506 	 */
5507 	down_write(&EXT4_I(inode)->i_mmap_sem);
5508 	/*
5509 	 * Need to round down offset to be aligned with page size boundary
5510 	 * for page size > block size.
5511 	 */
5512 	ioffset = round_down(offset, PAGE_SIZE);
5513 	/*
5514 	 * Write tail of the last page before removed range since it will get
5515 	 * removed from the page cache below.
5516 	 */
5517 	ret = filemap_write_and_wait_range(inode->i_mapping, ioffset, offset);
5518 	if (ret)
5519 		goto out_mmap;
5520 	/*
5521 	 * Write data that will be shifted to preserve them when discarding
5522 	 * page cache below. We are also protected from pages becoming dirty
5523 	 * by i_mmap_sem.
5524 	 */
5525 	ret = filemap_write_and_wait_range(inode->i_mapping, offset + len,
5526 					   LLONG_MAX);
5527 	if (ret)
5528 		goto out_mmap;
5529 	truncate_pagecache(inode, ioffset);
5530 
5531 	credits = ext4_writepage_trans_blocks(inode);
5532 	handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, credits);
5533 	if (IS_ERR(handle)) {
5534 		ret = PTR_ERR(handle);
5535 		goto out_mmap;
5536 	}
5537 
5538 	down_write(&EXT4_I(inode)->i_data_sem);
5539 	ext4_discard_preallocations(inode);
5540 
5541 	ret = ext4_es_remove_extent(inode, punch_start,
5542 				    EXT_MAX_BLOCKS - punch_start);
5543 	if (ret) {
5544 		up_write(&EXT4_I(inode)->i_data_sem);
5545 		goto out_stop;
5546 	}
5547 
5548 	ret = ext4_ext_remove_space(inode, punch_start, punch_stop - 1);
5549 	if (ret) {
5550 		up_write(&EXT4_I(inode)->i_data_sem);
5551 		goto out_stop;
5552 	}
5553 	ext4_discard_preallocations(inode);
5554 
5555 	ret = ext4_ext_shift_extents(inode, handle, punch_stop,
5556 				     punch_stop - punch_start, SHIFT_LEFT);
5557 	if (ret) {
5558 		up_write(&EXT4_I(inode)->i_data_sem);
5559 		goto out_stop;
5560 	}
5561 
5562 	new_size = i_size_read(inode) - len;
5563 	i_size_write(inode, new_size);
5564 	EXT4_I(inode)->i_disksize = new_size;
5565 
5566 	up_write(&EXT4_I(inode)->i_data_sem);
5567 	if (IS_SYNC(inode))
5568 		ext4_handle_sync(handle);
5569 	inode->i_mtime = inode->i_ctime = current_time(inode);
5570 	ext4_mark_inode_dirty(handle, inode);
5571 	ext4_update_inode_fsync_trans(handle, inode, 1);
5572 
5573 out_stop:
5574 	ext4_journal_stop(handle);
5575 out_mmap:
5576 	up_write(&EXT4_I(inode)->i_mmap_sem);
5577 	ext4_inode_resume_unlocked_dio(inode);
5578 out_mutex:
5579 	inode_unlock(inode);
5580 	return ret;
5581 }
5582 
5583 /*
5584  * ext4_insert_range:
5585  * This function implements the FALLOC_FL_INSERT_RANGE flag of fallocate.
5586  * The data blocks starting from @offset to the EOF are shifted by @len
5587  * towards right to create a hole in the @inode. Inode size is increased
5588  * by len bytes.
5589  * Returns 0 on success, error otherwise.
5590  */
5591 int ext4_insert_range(struct inode *inode, loff_t offset, loff_t len)
5592 {
5593 	struct super_block *sb = inode->i_sb;
5594 	handle_t *handle;
5595 	struct ext4_ext_path *path;
5596 	struct ext4_extent *extent;
5597 	ext4_lblk_t offset_lblk, len_lblk, ee_start_lblk = 0;
5598 	unsigned int credits, ee_len;
5599 	int ret = 0, depth, split_flag = 0;
5600 	loff_t ioffset;
5601 
5602 	/*
5603 	 * We need to test this early because xfstests assumes that an
5604 	 * insert range of (0, 1) will return EOPNOTSUPP if the file
5605 	 * system does not support insert range.
5606 	 */
5607 	if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
5608 		return -EOPNOTSUPP;
5609 
5610 	/* Insert range works only on fs block size aligned offsets. */
5611 	if (offset & (EXT4_CLUSTER_SIZE(sb) - 1) ||
5612 			len & (EXT4_CLUSTER_SIZE(sb) - 1))
5613 		return -EINVAL;
5614 
5615 	if (!S_ISREG(inode->i_mode))
5616 		return -EOPNOTSUPP;
5617 
5618 	trace_ext4_insert_range(inode, offset, len);
5619 
5620 	offset_lblk = offset >> EXT4_BLOCK_SIZE_BITS(sb);
5621 	len_lblk = len >> EXT4_BLOCK_SIZE_BITS(sb);
5622 
5623 	/* Call ext4_force_commit to flush all data in case of data=journal */
5624 	if (ext4_should_journal_data(inode)) {
5625 		ret = ext4_force_commit(inode->i_sb);
5626 		if (ret)
5627 			return ret;
5628 	}
5629 
5630 	inode_lock(inode);
5631 	/* Currently just for extent based files */
5632 	if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)) {
5633 		ret = -EOPNOTSUPP;
5634 		goto out_mutex;
5635 	}
5636 
5637 	/* Check for wrap through zero */
5638 	if (inode->i_size + len > inode->i_sb->s_maxbytes) {
5639 		ret = -EFBIG;
5640 		goto out_mutex;
5641 	}
5642 
5643 	/* Offset should be less than i_size */
5644 	if (offset >= i_size_read(inode)) {
5645 		ret = -EINVAL;
5646 		goto out_mutex;
5647 	}
5648 
5649 	/* Wait for existing dio to complete */
5650 	ext4_inode_block_unlocked_dio(inode);
5651 	inode_dio_wait(inode);
5652 
5653 	/*
5654 	 * Prevent page faults from reinstantiating pages we have released from
5655 	 * page cache.
5656 	 */
5657 	down_write(&EXT4_I(inode)->i_mmap_sem);
5658 	/*
5659 	 * Need to round down to align start offset to page size boundary
5660 	 * for page size > block size.
5661 	 */
5662 	ioffset = round_down(offset, PAGE_SIZE);
5663 	/* Write out all dirty pages */
5664 	ret = filemap_write_and_wait_range(inode->i_mapping, ioffset,
5665 			LLONG_MAX);
5666 	if (ret)
5667 		goto out_mmap;
5668 	truncate_pagecache(inode, ioffset);
5669 
5670 	credits = ext4_writepage_trans_blocks(inode);
5671 	handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, credits);
5672 	if (IS_ERR(handle)) {
5673 		ret = PTR_ERR(handle);
5674 		goto out_mmap;
5675 	}
5676 
5677 	/* Expand file to avoid data loss if there is error while shifting */
5678 	inode->i_size += len;
5679 	EXT4_I(inode)->i_disksize += len;
5680 	inode->i_mtime = inode->i_ctime = current_time(inode);
5681 	ret = ext4_mark_inode_dirty(handle, inode);
5682 	if (ret)
5683 		goto out_stop;
5684 
5685 	down_write(&EXT4_I(inode)->i_data_sem);
5686 	ext4_discard_preallocations(inode);
5687 
5688 	path = ext4_find_extent(inode, offset_lblk, NULL, 0);
5689 	if (IS_ERR(path)) {
5690 		up_write(&EXT4_I(inode)->i_data_sem);
5691 		goto out_stop;
5692 	}
5693 
5694 	depth = ext_depth(inode);
5695 	extent = path[depth].p_ext;
5696 	if (extent) {
5697 		ee_start_lblk = le32_to_cpu(extent->ee_block);
5698 		ee_len = ext4_ext_get_actual_len(extent);
5699 
5700 		/*
5701 		 * If offset_lblk is not the starting block of extent, split
5702 		 * the extent @offset_lblk
5703 		 */
5704 		if ((offset_lblk > ee_start_lblk) &&
5705 				(offset_lblk < (ee_start_lblk + ee_len))) {
5706 			if (ext4_ext_is_unwritten(extent))
5707 				split_flag = EXT4_EXT_MARK_UNWRIT1 |
5708 					EXT4_EXT_MARK_UNWRIT2;
5709 			ret = ext4_split_extent_at(handle, inode, &path,
5710 					offset_lblk, split_flag,
5711 					EXT4_EX_NOCACHE |
5712 					EXT4_GET_BLOCKS_PRE_IO |
5713 					EXT4_GET_BLOCKS_METADATA_NOFAIL);
5714 		}
5715 
5716 		ext4_ext_drop_refs(path);
5717 		kfree(path);
5718 		if (ret < 0) {
5719 			up_write(&EXT4_I(inode)->i_data_sem);
5720 			goto out_stop;
5721 		}
5722 	} else {
5723 		ext4_ext_drop_refs(path);
5724 		kfree(path);
5725 	}
5726 
5727 	ret = ext4_es_remove_extent(inode, offset_lblk,
5728 			EXT_MAX_BLOCKS - offset_lblk);
5729 	if (ret) {
5730 		up_write(&EXT4_I(inode)->i_data_sem);
5731 		goto out_stop;
5732 	}
5733 
5734 	/*
5735 	 * if offset_lblk lies in a hole which is at start of file, use
5736 	 * ee_start_lblk to shift extents
5737 	 */
5738 	ret = ext4_ext_shift_extents(inode, handle,
5739 		ee_start_lblk > offset_lblk ? ee_start_lblk : offset_lblk,
5740 		len_lblk, SHIFT_RIGHT);
5741 
5742 	up_write(&EXT4_I(inode)->i_data_sem);
5743 	if (IS_SYNC(inode))
5744 		ext4_handle_sync(handle);
5745 	if (ret >= 0)
5746 		ext4_update_inode_fsync_trans(handle, inode, 1);
5747 
5748 out_stop:
5749 	ext4_journal_stop(handle);
5750 out_mmap:
5751 	up_write(&EXT4_I(inode)->i_mmap_sem);
5752 	ext4_inode_resume_unlocked_dio(inode);
5753 out_mutex:
5754 	inode_unlock(inode);
5755 	return ret;
5756 }
5757 
5758 /**
5759  * ext4_swap_extents - Swap extents between two inodes
5760  *
5761  * @inode1:	First inode
5762  * @inode2:	Second inode
5763  * @lblk1:	Start block for first inode
5764  * @lblk2:	Start block for second inode
5765  * @count:	Number of blocks to swap
5766  * @mark_unwritten: Mark second inode's extents as unwritten after swap
5767  * @erp:	Pointer to save error value
5768  *
5769  * This helper routine does exactly what is promise "swap extents". All other
5770  * stuff such as page-cache locking consistency, bh mapping consistency or
5771  * extent's data copying must be performed by caller.
5772  * Locking:
5773  * 		i_mutex is held for both inodes
5774  * 		i_data_sem is locked for write for both inodes
5775  * Assumptions:
5776  *		All pages from requested range are locked for both inodes
5777  */
5778 int
5779 ext4_swap_extents(handle_t *handle, struct inode *inode1,
5780 		     struct inode *inode2, ext4_lblk_t lblk1, ext4_lblk_t lblk2,
5781 		  ext4_lblk_t count, int unwritten, int *erp)
5782 {
5783 	struct ext4_ext_path *path1 = NULL;
5784 	struct ext4_ext_path *path2 = NULL;
5785 	int replaced_count = 0;
5786 
5787 	BUG_ON(!rwsem_is_locked(&EXT4_I(inode1)->i_data_sem));
5788 	BUG_ON(!rwsem_is_locked(&EXT4_I(inode2)->i_data_sem));
5789 	BUG_ON(!inode_is_locked(inode1));
5790 	BUG_ON(!inode_is_locked(inode2));
5791 
5792 	*erp = ext4_es_remove_extent(inode1, lblk1, count);
5793 	if (unlikely(*erp))
5794 		return 0;
5795 	*erp = ext4_es_remove_extent(inode2, lblk2, count);
5796 	if (unlikely(*erp))
5797 		return 0;
5798 
5799 	while (count) {
5800 		struct ext4_extent *ex1, *ex2, tmp_ex;
5801 		ext4_lblk_t e1_blk, e2_blk;
5802 		int e1_len, e2_len, len;
5803 		int split = 0;
5804 
5805 		path1 = ext4_find_extent(inode1, lblk1, NULL, EXT4_EX_NOCACHE);
5806 		if (IS_ERR(path1)) {
5807 			*erp = PTR_ERR(path1);
5808 			path1 = NULL;
5809 		finish:
5810 			count = 0;
5811 			goto repeat;
5812 		}
5813 		path2 = ext4_find_extent(inode2, lblk2, NULL, EXT4_EX_NOCACHE);
5814 		if (IS_ERR(path2)) {
5815 			*erp = PTR_ERR(path2);
5816 			path2 = NULL;
5817 			goto finish;
5818 		}
5819 		ex1 = path1[path1->p_depth].p_ext;
5820 		ex2 = path2[path2->p_depth].p_ext;
5821 		/* Do we have somthing to swap ? */
5822 		if (unlikely(!ex2 || !ex1))
5823 			goto finish;
5824 
5825 		e1_blk = le32_to_cpu(ex1->ee_block);
5826 		e2_blk = le32_to_cpu(ex2->ee_block);
5827 		e1_len = ext4_ext_get_actual_len(ex1);
5828 		e2_len = ext4_ext_get_actual_len(ex2);
5829 
5830 		/* Hole handling */
5831 		if (!in_range(lblk1, e1_blk, e1_len) ||
5832 		    !in_range(lblk2, e2_blk, e2_len)) {
5833 			ext4_lblk_t next1, next2;
5834 
5835 			/* if hole after extent, then go to next extent */
5836 			next1 = ext4_ext_next_allocated_block(path1);
5837 			next2 = ext4_ext_next_allocated_block(path2);
5838 			/* If hole before extent, then shift to that extent */
5839 			if (e1_blk > lblk1)
5840 				next1 = e1_blk;
5841 			if (e2_blk > lblk2)
5842 				next2 = e2_blk;
5843 			/* Do we have something to swap */
5844 			if (next1 == EXT_MAX_BLOCKS || next2 == EXT_MAX_BLOCKS)
5845 				goto finish;
5846 			/* Move to the rightest boundary */
5847 			len = next1 - lblk1;
5848 			if (len < next2 - lblk2)
5849 				len = next2 - lblk2;
5850 			if (len > count)
5851 				len = count;
5852 			lblk1 += len;
5853 			lblk2 += len;
5854 			count -= len;
5855 			goto repeat;
5856 		}
5857 
5858 		/* Prepare left boundary */
5859 		if (e1_blk < lblk1) {
5860 			split = 1;
5861 			*erp = ext4_force_split_extent_at(handle, inode1,
5862 						&path1, lblk1, 0);
5863 			if (unlikely(*erp))
5864 				goto finish;
5865 		}
5866 		if (e2_blk < lblk2) {
5867 			split = 1;
5868 			*erp = ext4_force_split_extent_at(handle, inode2,
5869 						&path2,  lblk2, 0);
5870 			if (unlikely(*erp))
5871 				goto finish;
5872 		}
5873 		/* ext4_split_extent_at() may result in leaf extent split,
5874 		 * path must to be revalidated. */
5875 		if (split)
5876 			goto repeat;
5877 
5878 		/* Prepare right boundary */
5879 		len = count;
5880 		if (len > e1_blk + e1_len - lblk1)
5881 			len = e1_blk + e1_len - lblk1;
5882 		if (len > e2_blk + e2_len - lblk2)
5883 			len = e2_blk + e2_len - lblk2;
5884 
5885 		if (len != e1_len) {
5886 			split = 1;
5887 			*erp = ext4_force_split_extent_at(handle, inode1,
5888 						&path1, lblk1 + len, 0);
5889 			if (unlikely(*erp))
5890 				goto finish;
5891 		}
5892 		if (len != e2_len) {
5893 			split = 1;
5894 			*erp = ext4_force_split_extent_at(handle, inode2,
5895 						&path2, lblk2 + len, 0);
5896 			if (*erp)
5897 				goto finish;
5898 		}
5899 		/* ext4_split_extent_at() may result in leaf extent split,
5900 		 * path must to be revalidated. */
5901 		if (split)
5902 			goto repeat;
5903 
5904 		BUG_ON(e2_len != e1_len);
5905 		*erp = ext4_ext_get_access(handle, inode1, path1 + path1->p_depth);
5906 		if (unlikely(*erp))
5907 			goto finish;
5908 		*erp = ext4_ext_get_access(handle, inode2, path2 + path2->p_depth);
5909 		if (unlikely(*erp))
5910 			goto finish;
5911 
5912 		/* Both extents are fully inside boundaries. Swap it now */
5913 		tmp_ex = *ex1;
5914 		ext4_ext_store_pblock(ex1, ext4_ext_pblock(ex2));
5915 		ext4_ext_store_pblock(ex2, ext4_ext_pblock(&tmp_ex));
5916 		ex1->ee_len = cpu_to_le16(e2_len);
5917 		ex2->ee_len = cpu_to_le16(e1_len);
5918 		if (unwritten)
5919 			ext4_ext_mark_unwritten(ex2);
5920 		if (ext4_ext_is_unwritten(&tmp_ex))
5921 			ext4_ext_mark_unwritten(ex1);
5922 
5923 		ext4_ext_try_to_merge(handle, inode2, path2, ex2);
5924 		ext4_ext_try_to_merge(handle, inode1, path1, ex1);
5925 		*erp = ext4_ext_dirty(handle, inode2, path2 +
5926 				      path2->p_depth);
5927 		if (unlikely(*erp))
5928 			goto finish;
5929 		*erp = ext4_ext_dirty(handle, inode1, path1 +
5930 				      path1->p_depth);
5931 		/*
5932 		 * Looks scarry ah..? second inode already points to new blocks,
5933 		 * and it was successfully dirtied. But luckily error may happen
5934 		 * only due to journal error, so full transaction will be
5935 		 * aborted anyway.
5936 		 */
5937 		if (unlikely(*erp))
5938 			goto finish;
5939 		lblk1 += len;
5940 		lblk2 += len;
5941 		replaced_count += len;
5942 		count -= len;
5943 
5944 	repeat:
5945 		ext4_ext_drop_refs(path1);
5946 		kfree(path1);
5947 		ext4_ext_drop_refs(path2);
5948 		kfree(path2);
5949 		path1 = path2 = NULL;
5950 	}
5951 	return replaced_count;
5952 }
5953