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