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 
ext4_extent_block_csum(struct inode * inode,struct ext4_extent_header * eh)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 
ext4_extent_block_csum_verify(struct inode * inode,struct ext4_extent_header * eh)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 
ext4_extent_block_csum_set(struct inode * inode,struct ext4_extent_header * eh)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 
ext4_ext_trunc_restart_fn(struct inode * inode,int * dropped)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, 0);
104 	up_write(&EXT4_I(inode)->i_data_sem);
105 	*dropped = 1;
106 	return 0;
107 }
108 
ext4_ext_drop_refs(struct ext4_ext_path * path)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 
ext4_free_ext_path(struct ext4_ext_path * path)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  */
ext4_datasem_ensure_credits(handle_t * handle,struct inode * inode,int check_cred,int restart_cred,int revoke_cred)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  */
ext4_ext_get_access(handle_t * handle,struct inode * inode,struct ext4_ext_path * path)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  */
__ext4_ext_dirty(const char * where,unsigned int line,handle_t * handle,struct inode * inode,struct ext4_ext_path * path)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 
ext4_ext_find_goal(struct inode * inode,struct ext4_ext_path * path,ext4_lblk_t block)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
ext4_ext_new_meta_block(handle_t * handle,struct inode * inode,struct ext4_ext_path * path,struct ext4_extent * ex,int * err,unsigned int flags)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 
ext4_ext_space_block(struct inode * inode,int check)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 
ext4_ext_space_block_idx(struct inode * inode,int check)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 
ext4_ext_space_root(struct inode * inode,int check)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 
ext4_ext_space_root_idx(struct inode * inode,int check)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
ext4_force_split_extent_at(handle_t * handle,struct inode * inode,struct ext4_ext_path ** ppath,ext4_lblk_t lblk,int nofail)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
ext4_ext_max_entries(struct inode * inode,int depth)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 
ext4_valid_extent(struct inode * inode,struct ext4_extent * ext)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 
ext4_valid_extent_idx(struct inode * inode,struct ext4_extent_idx * ext_idx)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 
ext4_valid_extent_entries(struct inode * inode,struct ext4_extent_header * eh,ext4_lblk_t lblk,ext4_fsblk_t * pblk,int depth)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 
__ext4_ext_check(const char * function,unsigned int line,struct inode * inode,struct ext4_extent_header * eh,int depth,ext4_fsblk_t pblk,ext4_lblk_t lblk)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 
ext4_ext_check_inode(struct inode * inode)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 
ext4_cache_extents(struct inode * inode,struct ext4_extent_header * eh)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 *
__read_extent_tree_block(const char * function,unsigned int line,struct inode * inode,struct ext4_extent_idx * idx,int depth,int flags)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  */
ext4_ext_precache(struct inode * inode)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
ext4_ext_show_path(struct inode * inode,struct ext4_ext_path * path)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 
ext4_ext_show_leaf(struct inode * inode,struct ext4_ext_path * path)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 
ext4_ext_show_move(struct inode * inode,struct ext4_ext_path * path,ext4_fsblk_t newblock,int level)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
ext4_ext_binsearch_idx(struct inode * inode,struct ext4_ext_path * path,ext4_lblk_t block)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
ext4_ext_binsearch(struct inode * inode,struct ext4_ext_path * path,ext4_lblk_t block)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 
ext4_ext_tree_init(handle_t * handle,struct inode * inode)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 *
ext4_find_extent(struct inode * inode,ext4_lblk_t block,struct ext4_ext_path ** orig_path,int flags)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  */
ext4_ext_insert_index(handle_t * handle,struct inode * inode,struct ext4_ext_path * curp,int logical,ext4_fsblk_t ptr)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  */
ext4_ext_split(handle_t * handle,struct inode * inode,unsigned int flags,struct ext4_ext_path * path,struct ext4_extent * newext,int at)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  */
ext4_ext_grow_indepth(handle_t * handle,struct inode * inode,unsigned int flags)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  */
ext4_ext_create_new_leaf(handle_t * handle,struct inode * inode,unsigned int mb_flags,unsigned int gb_flags,struct ext4_ext_path ** ppath,struct ext4_extent * newext)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  */
ext4_ext_search_left(struct inode * inode,struct ext4_ext_path * path,ext4_lblk_t * logical,ext4_fsblk_t * phys)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  */
ext4_ext_search_right(struct inode * inode,struct ext4_ext_path * path,ext4_lblk_t * logical,ext4_fsblk_t * phys,struct ext4_extent * ret_ex)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
ext4_ext_next_allocated_block(struct ext4_ext_path * path)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  */
ext4_ext_next_leaf_block(struct ext4_ext_path * path)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  */
ext4_ext_correct_indexes(handle_t * handle,struct inode * inode,struct ext4_ext_path * path)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 
ext4_can_extents_be_merged(struct inode * inode,struct ext4_extent * ex1,struct ext4_extent * ex2)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  */
ext4_ext_try_to_merge_right(struct inode * inode,struct ext4_ext_path * path,struct ext4_extent * ex)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  */
ext4_ext_try_to_merge_up(handle_t * handle,struct inode * inode,struct ext4_ext_path * path)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  */
ext4_ext_try_to_merge(handle_t * handle,struct inode * inode,struct ext4_ext_path * path,struct ext4_extent * ex)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  */
ext4_ext_check_overlap(struct ext4_sb_info * sbi,struct inode * inode,struct ext4_extent * newext,struct ext4_ext_path * path)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  */
ext4_ext_insert_extent(handle_t * handle,struct inode * inode,struct ext4_ext_path ** ppath,struct ext4_extent * newext,int gb_flags)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 
ext4_fill_es_cache_info(struct inode * inode,ext4_lblk_t block,ext4_lblk_t num,struct fiemap_extent_info * fieinfo)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  */
ext4_ext_find_hole(struct inode * inode,struct ext4_ext_path * path,ext4_lblk_t * lblk)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  */
ext4_ext_rm_idx(handle_t * handle,struct inode * inode,struct ext4_ext_path * path,int depth)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  */
ext4_ext_calc_credits_for_single_extent(struct inode * inode,int nrblocks,struct ext4_ext_path * path)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  */
ext4_ext_index_trans_blocks(struct inode * inode,int extents)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 
get_default_free_blocks_flags(struct inode * inode)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  */
ext4_rereserve_cluster(struct inode * inode,ext4_lblk_t lblk)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 
ext4_remove_blocks(handle_t * handle,struct inode * inode,struct ext4_extent * ex,struct partial_cluster * partial,ext4_lblk_t from,ext4_lblk_t to)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
ext4_ext_rm_leaf(handle_t * handle,struct inode * inode,struct ext4_ext_path * path,struct partial_cluster * partial,ext4_lblk_t start,ext4_lblk_t end)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
ext4_ext_more_to_rm(struct ext4_ext_path * path)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 
ext4_ext_remove_space(struct inode * inode,ext4_lblk_t start,ext4_lblk_t end)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  */
ext4_ext_init(struct super_block * sb)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  */
ext4_ext_release(struct super_block * sb)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 
ext4_zeroout_es(struct inode * inode,struct ext4_extent * ex)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  */
ext4_ext_zeroout(struct inode * inode,struct ext4_extent * ex)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  */
ext4_split_extent_at(handle_t * handle,struct inode * inode,struct ext4_ext_path ** ppath,ext4_lblk_t split,int split_flag,int flags)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  */
ext4_split_extent(handle_t * handle,struct inode * inode,struct ext4_ext_path ** ppath,struct ext4_map_blocks * map,int split_flag,int flags)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  */
ext4_ext_convert_to_initialized(handle_t * handle,struct inode * inode,struct ext4_map_blocks * map,struct ext4_ext_path ** ppath,int flags)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 allocated = 0, max_zeroout = 0;
3406 	int err = 0;
3407 	int split_flag = EXT4_EXT_DATA_VALID2;
3408 
3409 	ext_debug(inode, "logical block %llu, max_blocks %u\n",
3410 		  (unsigned long long)map->m_lblk, map_len);
3411 
3412 	sbi = EXT4_SB(inode->i_sb);
3413 	eof_block = (EXT4_I(inode)->i_disksize + inode->i_sb->s_blocksize - 1)
3414 			>> inode->i_sb->s_blocksize_bits;
3415 	if (eof_block < map->m_lblk + map_len)
3416 		eof_block = map->m_lblk + map_len;
3417 
3418 	depth = ext_depth(inode);
3419 	eh = path[depth].p_hdr;
3420 	ex = path[depth].p_ext;
3421 	ee_block = le32_to_cpu(ex->ee_block);
3422 	ee_len = ext4_ext_get_actual_len(ex);
3423 	zero_ex1.ee_len = 0;
3424 	zero_ex2.ee_len = 0;
3425 
3426 	trace_ext4_ext_convert_to_initialized_enter(inode, map, ex);
3427 
3428 	/* Pre-conditions */
3429 	BUG_ON(!ext4_ext_is_unwritten(ex));
3430 	BUG_ON(!in_range(map->m_lblk, ee_block, ee_len));
3431 
3432 	/*
3433 	 * Attempt to transfer newly initialized blocks from the currently
3434 	 * unwritten extent to its neighbor. This is much cheaper
3435 	 * than an insertion followed by a merge as those involve costly
3436 	 * memmove() calls. Transferring to the left is the common case in
3437 	 * steady state for workloads doing fallocate(FALLOC_FL_KEEP_SIZE)
3438 	 * followed by append writes.
3439 	 *
3440 	 * Limitations of the current logic:
3441 	 *  - L1: we do not deal with writes covering the whole extent.
3442 	 *    This would require removing the extent if the transfer
3443 	 *    is possible.
3444 	 *  - L2: we only attempt to merge with an extent stored in the
3445 	 *    same extent tree node.
3446 	 */
3447 	if ((map->m_lblk == ee_block) &&
3448 		/* See if we can merge left */
3449 		(map_len < ee_len) &&		/*L1*/
3450 		(ex > EXT_FIRST_EXTENT(eh))) {	/*L2*/
3451 		ext4_lblk_t prev_lblk;
3452 		ext4_fsblk_t prev_pblk, ee_pblk;
3453 		unsigned int prev_len;
3454 
3455 		abut_ex = ex - 1;
3456 		prev_lblk = le32_to_cpu(abut_ex->ee_block);
3457 		prev_len = ext4_ext_get_actual_len(abut_ex);
3458 		prev_pblk = ext4_ext_pblock(abut_ex);
3459 		ee_pblk = ext4_ext_pblock(ex);
3460 
3461 		/*
3462 		 * A transfer of blocks from 'ex' to 'abut_ex' is allowed
3463 		 * upon those conditions:
3464 		 * - C1: abut_ex is initialized,
3465 		 * - C2: abut_ex is logically abutting ex,
3466 		 * - C3: abut_ex is physically abutting ex,
3467 		 * - C4: abut_ex can receive the additional blocks without
3468 		 *   overflowing the (initialized) length limit.
3469 		 */
3470 		if ((!ext4_ext_is_unwritten(abut_ex)) &&		/*C1*/
3471 			((prev_lblk + prev_len) == ee_block) &&		/*C2*/
3472 			((prev_pblk + prev_len) == ee_pblk) &&		/*C3*/
3473 			(prev_len < (EXT_INIT_MAX_LEN - map_len))) {	/*C4*/
3474 			err = ext4_ext_get_access(handle, inode, path + depth);
3475 			if (err)
3476 				goto out;
3477 
3478 			trace_ext4_ext_convert_to_initialized_fastpath(inode,
3479 				map, ex, abut_ex);
3480 
3481 			/* Shift the start of ex by 'map_len' blocks */
3482 			ex->ee_block = cpu_to_le32(ee_block + map_len);
3483 			ext4_ext_store_pblock(ex, ee_pblk + map_len);
3484 			ex->ee_len = cpu_to_le16(ee_len - map_len);
3485 			ext4_ext_mark_unwritten(ex); /* Restore the flag */
3486 
3487 			/* Extend abut_ex by 'map_len' blocks */
3488 			abut_ex->ee_len = cpu_to_le16(prev_len + map_len);
3489 
3490 			/* Result: number of initialized blocks past m_lblk */
3491 			allocated = map_len;
3492 		}
3493 	} else if (((map->m_lblk + map_len) == (ee_block + ee_len)) &&
3494 		   (map_len < ee_len) &&	/*L1*/
3495 		   ex < EXT_LAST_EXTENT(eh)) {	/*L2*/
3496 		/* See if we can merge right */
3497 		ext4_lblk_t next_lblk;
3498 		ext4_fsblk_t next_pblk, ee_pblk;
3499 		unsigned int next_len;
3500 
3501 		abut_ex = ex + 1;
3502 		next_lblk = le32_to_cpu(abut_ex->ee_block);
3503 		next_len = ext4_ext_get_actual_len(abut_ex);
3504 		next_pblk = ext4_ext_pblock(abut_ex);
3505 		ee_pblk = ext4_ext_pblock(ex);
3506 
3507 		/*
3508 		 * A transfer of blocks from 'ex' to 'abut_ex' is allowed
3509 		 * upon those conditions:
3510 		 * - C1: abut_ex is initialized,
3511 		 * - C2: abut_ex is logically abutting ex,
3512 		 * - C3: abut_ex is physically abutting ex,
3513 		 * - C4: abut_ex can receive the additional blocks without
3514 		 *   overflowing the (initialized) length limit.
3515 		 */
3516 		if ((!ext4_ext_is_unwritten(abut_ex)) &&		/*C1*/
3517 		    ((map->m_lblk + map_len) == next_lblk) &&		/*C2*/
3518 		    ((ee_pblk + ee_len) == next_pblk) &&		/*C3*/
3519 		    (next_len < (EXT_INIT_MAX_LEN - map_len))) {	/*C4*/
3520 			err = ext4_ext_get_access(handle, inode, path + depth);
3521 			if (err)
3522 				goto out;
3523 
3524 			trace_ext4_ext_convert_to_initialized_fastpath(inode,
3525 				map, ex, abut_ex);
3526 
3527 			/* Shift the start of abut_ex by 'map_len' blocks */
3528 			abut_ex->ee_block = cpu_to_le32(next_lblk - map_len);
3529 			ext4_ext_store_pblock(abut_ex, next_pblk - map_len);
3530 			ex->ee_len = cpu_to_le16(ee_len - map_len);
3531 			ext4_ext_mark_unwritten(ex); /* Restore the flag */
3532 
3533 			/* Extend abut_ex by 'map_len' blocks */
3534 			abut_ex->ee_len = cpu_to_le16(next_len + map_len);
3535 
3536 			/* Result: number of initialized blocks past m_lblk */
3537 			allocated = map_len;
3538 		}
3539 	}
3540 	if (allocated) {
3541 		/* Mark the block containing both extents as dirty */
3542 		err = ext4_ext_dirty(handle, inode, path + depth);
3543 
3544 		/* Update path to point to the right extent */
3545 		path[depth].p_ext = abut_ex;
3546 		goto out;
3547 	} else
3548 		allocated = ee_len - (map->m_lblk - ee_block);
3549 
3550 	WARN_ON(map->m_lblk < ee_block);
3551 	/*
3552 	 * It is safe to convert extent to initialized via explicit
3553 	 * zeroout only if extent is fully inside i_size or new_size.
3554 	 */
3555 	split_flag |= ee_block + ee_len <= eof_block ? EXT4_EXT_MAY_ZEROOUT : 0;
3556 
3557 	if (EXT4_EXT_MAY_ZEROOUT & split_flag)
3558 		max_zeroout = sbi->s_extent_max_zeroout_kb >>
3559 			(inode->i_sb->s_blocksize_bits - 10);
3560 
3561 	/*
3562 	 * five cases:
3563 	 * 1. split the extent into three extents.
3564 	 * 2. split the extent into two extents, zeroout the head of the first
3565 	 *    extent.
3566 	 * 3. split the extent into two extents, zeroout the tail of the second
3567 	 *    extent.
3568 	 * 4. split the extent into two extents with out zeroout.
3569 	 * 5. no splitting needed, just possibly zeroout the head and / or the
3570 	 *    tail of the extent.
3571 	 */
3572 	split_map.m_lblk = map->m_lblk;
3573 	split_map.m_len = map->m_len;
3574 
3575 	if (max_zeroout && (allocated > split_map.m_len)) {
3576 		if (allocated <= max_zeroout) {
3577 			/* case 3 or 5 */
3578 			zero_ex1.ee_block =
3579 				 cpu_to_le32(split_map.m_lblk +
3580 					     split_map.m_len);
3581 			zero_ex1.ee_len =
3582 				cpu_to_le16(allocated - split_map.m_len);
3583 			ext4_ext_store_pblock(&zero_ex1,
3584 				ext4_ext_pblock(ex) + split_map.m_lblk +
3585 				split_map.m_len - ee_block);
3586 			err = ext4_ext_zeroout(inode, &zero_ex1);
3587 			if (err)
3588 				goto fallback;
3589 			split_map.m_len = allocated;
3590 		}
3591 		if (split_map.m_lblk - ee_block + split_map.m_len <
3592 								max_zeroout) {
3593 			/* case 2 or 5 */
3594 			if (split_map.m_lblk != ee_block) {
3595 				zero_ex2.ee_block = ex->ee_block;
3596 				zero_ex2.ee_len = cpu_to_le16(split_map.m_lblk -
3597 							ee_block);
3598 				ext4_ext_store_pblock(&zero_ex2,
3599 						      ext4_ext_pblock(ex));
3600 				err = ext4_ext_zeroout(inode, &zero_ex2);
3601 				if (err)
3602 					goto fallback;
3603 			}
3604 
3605 			split_map.m_len += split_map.m_lblk - ee_block;
3606 			split_map.m_lblk = ee_block;
3607 			allocated = map->m_len;
3608 		}
3609 	}
3610 
3611 fallback:
3612 	err = ext4_split_extent(handle, inode, ppath, &split_map, split_flag,
3613 				flags);
3614 	if (err > 0)
3615 		err = 0;
3616 out:
3617 	/* If we have gotten a failure, don't zero out status tree */
3618 	if (!err) {
3619 		ext4_zeroout_es(inode, &zero_ex1);
3620 		ext4_zeroout_es(inode, &zero_ex2);
3621 	}
3622 	return err ? err : allocated;
3623 }
3624 
3625 /*
3626  * This function is called by ext4_ext_map_blocks() from
3627  * ext4_get_blocks_dio_write() when DIO to write
3628  * to an unwritten extent.
3629  *
3630  * Writing to an unwritten extent may result in splitting the unwritten
3631  * extent into multiple initialized/unwritten extents (up to three)
3632  * There are three possibilities:
3633  *   a> There is no split required: Entire extent should be unwritten
3634  *   b> Splits in two extents: Write is happening at either end of the extent
3635  *   c> Splits in three extents: Somone is writing in middle of the extent
3636  *
3637  * This works the same way in the case of initialized -> unwritten conversion.
3638  *
3639  * One of more index blocks maybe needed if the extent tree grow after
3640  * the unwritten extent split. To prevent ENOSPC occur at the IO
3641  * complete, we need to split the unwritten extent before DIO submit
3642  * the IO. The unwritten extent called at this time will be split
3643  * into three unwritten extent(at most). After IO complete, the part
3644  * being filled will be convert to initialized by the end_io callback function
3645  * via ext4_convert_unwritten_extents().
3646  *
3647  * Returns the size of unwritten extent to be written on success.
3648  */
ext4_split_convert_extents(handle_t * handle,struct inode * inode,struct ext4_map_blocks * map,struct ext4_ext_path ** ppath,int flags)3649 static int ext4_split_convert_extents(handle_t *handle,
3650 					struct inode *inode,
3651 					struct ext4_map_blocks *map,
3652 					struct ext4_ext_path **ppath,
3653 					int flags)
3654 {
3655 	struct ext4_ext_path *path = *ppath;
3656 	ext4_lblk_t eof_block;
3657 	ext4_lblk_t ee_block;
3658 	struct ext4_extent *ex;
3659 	unsigned int ee_len;
3660 	int split_flag = 0, depth;
3661 
3662 	ext_debug(inode, "logical block %llu, max_blocks %u\n",
3663 		  (unsigned long long)map->m_lblk, map->m_len);
3664 
3665 	eof_block = (EXT4_I(inode)->i_disksize + inode->i_sb->s_blocksize - 1)
3666 			>> inode->i_sb->s_blocksize_bits;
3667 	if (eof_block < map->m_lblk + map->m_len)
3668 		eof_block = map->m_lblk + map->m_len;
3669 	/*
3670 	 * It is safe to convert extent to initialized via explicit
3671 	 * zeroout only if extent is fully inside i_size or new_size.
3672 	 */
3673 	depth = ext_depth(inode);
3674 	ex = path[depth].p_ext;
3675 	ee_block = le32_to_cpu(ex->ee_block);
3676 	ee_len = ext4_ext_get_actual_len(ex);
3677 
3678 	/* Convert to unwritten */
3679 	if (flags & EXT4_GET_BLOCKS_CONVERT_UNWRITTEN) {
3680 		split_flag |= EXT4_EXT_DATA_VALID1;
3681 	/* Convert to initialized */
3682 	} else if (flags & EXT4_GET_BLOCKS_CONVERT) {
3683 		split_flag |= ee_block + ee_len <= eof_block ?
3684 			      EXT4_EXT_MAY_ZEROOUT : 0;
3685 		split_flag |= (EXT4_EXT_MARK_UNWRIT2 | EXT4_EXT_DATA_VALID2);
3686 	}
3687 	flags |= EXT4_GET_BLOCKS_PRE_IO;
3688 	return ext4_split_extent(handle, inode, ppath, map, split_flag, flags);
3689 }
3690 
ext4_convert_unwritten_extents_endio(handle_t * handle,struct inode * inode,struct ext4_map_blocks * map,struct ext4_ext_path ** ppath)3691 static int ext4_convert_unwritten_extents_endio(handle_t *handle,
3692 						struct inode *inode,
3693 						struct ext4_map_blocks *map,
3694 						struct ext4_ext_path **ppath)
3695 {
3696 	struct ext4_ext_path *path = *ppath;
3697 	struct ext4_extent *ex;
3698 	ext4_lblk_t ee_block;
3699 	unsigned int ee_len;
3700 	int depth;
3701 	int err = 0;
3702 
3703 	depth = ext_depth(inode);
3704 	ex = path[depth].p_ext;
3705 	ee_block = le32_to_cpu(ex->ee_block);
3706 	ee_len = ext4_ext_get_actual_len(ex);
3707 
3708 	ext_debug(inode, "logical block %llu, max_blocks %u\n",
3709 		  (unsigned long long)ee_block, ee_len);
3710 
3711 	/* If extent is larger than requested it is a clear sign that we still
3712 	 * have some extent state machine issues left. So extent_split is still
3713 	 * required.
3714 	 * TODO: Once all related issues will be fixed this situation should be
3715 	 * illegal.
3716 	 */
3717 	if (ee_block != map->m_lblk || ee_len > map->m_len) {
3718 #ifdef CONFIG_EXT4_DEBUG
3719 		ext4_warning(inode->i_sb, "Inode (%ld) finished: extent logical block %llu,"
3720 			     " len %u; IO logical block %llu, len %u",
3721 			     inode->i_ino, (unsigned long long)ee_block, ee_len,
3722 			     (unsigned long long)map->m_lblk, map->m_len);
3723 #endif
3724 		err = ext4_split_convert_extents(handle, inode, map, ppath,
3725 						 EXT4_GET_BLOCKS_CONVERT);
3726 		if (err < 0)
3727 			return err;
3728 		path = ext4_find_extent(inode, map->m_lblk, ppath, 0);
3729 		if (IS_ERR(path))
3730 			return PTR_ERR(path);
3731 		depth = ext_depth(inode);
3732 		ex = path[depth].p_ext;
3733 	}
3734 
3735 	err = ext4_ext_get_access(handle, inode, path + depth);
3736 	if (err)
3737 		goto out;
3738 	/* first mark the extent as initialized */
3739 	ext4_ext_mark_initialized(ex);
3740 
3741 	/* note: ext4_ext_correct_indexes() isn't needed here because
3742 	 * borders are not changed
3743 	 */
3744 	ext4_ext_try_to_merge(handle, inode, path, ex);
3745 
3746 	/* Mark modified extent as dirty */
3747 	err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3748 out:
3749 	ext4_ext_show_leaf(inode, path);
3750 	return err;
3751 }
3752 
3753 static int
convert_initialized_extent(handle_t * handle,struct inode * inode,struct ext4_map_blocks * map,struct ext4_ext_path ** ppath,unsigned int * allocated)3754 convert_initialized_extent(handle_t *handle, struct inode *inode,
3755 			   struct ext4_map_blocks *map,
3756 			   struct ext4_ext_path **ppath,
3757 			   unsigned int *allocated)
3758 {
3759 	struct ext4_ext_path *path = *ppath;
3760 	struct ext4_extent *ex;
3761 	ext4_lblk_t ee_block;
3762 	unsigned int ee_len;
3763 	int depth;
3764 	int err = 0;
3765 
3766 	/*
3767 	 * Make sure that the extent is no bigger than we support with
3768 	 * unwritten extent
3769 	 */
3770 	if (map->m_len > EXT_UNWRITTEN_MAX_LEN)
3771 		map->m_len = EXT_UNWRITTEN_MAX_LEN / 2;
3772 
3773 	depth = ext_depth(inode);
3774 	ex = path[depth].p_ext;
3775 	ee_block = le32_to_cpu(ex->ee_block);
3776 	ee_len = ext4_ext_get_actual_len(ex);
3777 
3778 	ext_debug(inode, "logical block %llu, max_blocks %u\n",
3779 		  (unsigned long long)ee_block, ee_len);
3780 
3781 	if (ee_block != map->m_lblk || ee_len > map->m_len) {
3782 		err = ext4_split_convert_extents(handle, inode, map, ppath,
3783 				EXT4_GET_BLOCKS_CONVERT_UNWRITTEN);
3784 		if (err < 0)
3785 			return err;
3786 		path = ext4_find_extent(inode, map->m_lblk, ppath, 0);
3787 		if (IS_ERR(path))
3788 			return PTR_ERR(path);
3789 		depth = ext_depth(inode);
3790 		ex = path[depth].p_ext;
3791 		if (!ex) {
3792 			EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
3793 					 (unsigned long) map->m_lblk);
3794 			return -EFSCORRUPTED;
3795 		}
3796 	}
3797 
3798 	err = ext4_ext_get_access(handle, inode, path + depth);
3799 	if (err)
3800 		return err;
3801 	/* first mark the extent as unwritten */
3802 	ext4_ext_mark_unwritten(ex);
3803 
3804 	/* note: ext4_ext_correct_indexes() isn't needed here because
3805 	 * borders are not changed
3806 	 */
3807 	ext4_ext_try_to_merge(handle, inode, path, ex);
3808 
3809 	/* Mark modified extent as dirty */
3810 	err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3811 	if (err)
3812 		return err;
3813 	ext4_ext_show_leaf(inode, path);
3814 
3815 	ext4_update_inode_fsync_trans(handle, inode, 1);
3816 
3817 	map->m_flags |= EXT4_MAP_UNWRITTEN;
3818 	if (*allocated > map->m_len)
3819 		*allocated = map->m_len;
3820 	map->m_len = *allocated;
3821 	return 0;
3822 }
3823 
3824 static int
ext4_ext_handle_unwritten_extents(handle_t * handle,struct inode * inode,struct ext4_map_blocks * map,struct ext4_ext_path ** ppath,int flags,unsigned int allocated,ext4_fsblk_t newblock)3825 ext4_ext_handle_unwritten_extents(handle_t *handle, struct inode *inode,
3826 			struct ext4_map_blocks *map,
3827 			struct ext4_ext_path **ppath, int flags,
3828 			unsigned int allocated, ext4_fsblk_t newblock)
3829 {
3830 	struct ext4_ext_path __maybe_unused *path = *ppath;
3831 	int ret = 0;
3832 	int err = 0;
3833 
3834 	ext_debug(inode, "logical block %llu, max_blocks %u, flags 0x%x, allocated %u\n",
3835 		  (unsigned long long)map->m_lblk, map->m_len, flags,
3836 		  allocated);
3837 	ext4_ext_show_leaf(inode, path);
3838 
3839 	/*
3840 	 * When writing into unwritten space, we should not fail to
3841 	 * allocate metadata blocks for the new extent block if needed.
3842 	 */
3843 	flags |= EXT4_GET_BLOCKS_METADATA_NOFAIL;
3844 
3845 	trace_ext4_ext_handle_unwritten_extents(inode, map, flags,
3846 						    allocated, newblock);
3847 
3848 	/* get_block() before submitting IO, split the extent */
3849 	if (flags & EXT4_GET_BLOCKS_PRE_IO) {
3850 		ret = ext4_split_convert_extents(handle, inode, map, ppath,
3851 					 flags | EXT4_GET_BLOCKS_CONVERT);
3852 		if (ret < 0) {
3853 			err = ret;
3854 			goto out2;
3855 		}
3856 		/*
3857 		 * shouldn't get a 0 return when splitting an extent unless
3858 		 * m_len is 0 (bug) or extent has been corrupted
3859 		 */
3860 		if (unlikely(ret == 0)) {
3861 			EXT4_ERROR_INODE(inode,
3862 					 "unexpected ret == 0, m_len = %u",
3863 					 map->m_len);
3864 			err = -EFSCORRUPTED;
3865 			goto out2;
3866 		}
3867 		map->m_flags |= EXT4_MAP_UNWRITTEN;
3868 		goto out;
3869 	}
3870 	/* IO end_io complete, convert the filled extent to written */
3871 	if (flags & EXT4_GET_BLOCKS_CONVERT) {
3872 		err = ext4_convert_unwritten_extents_endio(handle, inode, map,
3873 							   ppath);
3874 		if (err < 0)
3875 			goto out2;
3876 		ext4_update_inode_fsync_trans(handle, inode, 1);
3877 		goto map_out;
3878 	}
3879 	/* buffered IO cases */
3880 	/*
3881 	 * repeat fallocate creation request
3882 	 * we already have an unwritten extent
3883 	 */
3884 	if (flags & EXT4_GET_BLOCKS_UNWRIT_EXT) {
3885 		map->m_flags |= EXT4_MAP_UNWRITTEN;
3886 		goto map_out;
3887 	}
3888 
3889 	/* buffered READ or buffered write_begin() lookup */
3890 	if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
3891 		/*
3892 		 * We have blocks reserved already.  We
3893 		 * return allocated blocks so that delalloc
3894 		 * won't do block reservation for us.  But
3895 		 * the buffer head will be unmapped so that
3896 		 * a read from the block returns 0s.
3897 		 */
3898 		map->m_flags |= EXT4_MAP_UNWRITTEN;
3899 		goto out1;
3900 	}
3901 
3902 	/*
3903 	 * Default case when (flags & EXT4_GET_BLOCKS_CREATE) == 1.
3904 	 * For buffered writes, at writepage time, etc.  Convert a
3905 	 * discovered unwritten extent to written.
3906 	 */
3907 	ret = ext4_ext_convert_to_initialized(handle, inode, map, ppath, flags);
3908 	if (ret < 0) {
3909 		err = ret;
3910 		goto out2;
3911 	}
3912 	ext4_update_inode_fsync_trans(handle, inode, 1);
3913 	/*
3914 	 * shouldn't get a 0 return when converting an unwritten extent
3915 	 * unless m_len is 0 (bug) or extent has been corrupted
3916 	 */
3917 	if (unlikely(ret == 0)) {
3918 		EXT4_ERROR_INODE(inode, "unexpected ret == 0, m_len = %u",
3919 				 map->m_len);
3920 		err = -EFSCORRUPTED;
3921 		goto out2;
3922 	}
3923 
3924 out:
3925 	allocated = ret;
3926 	map->m_flags |= EXT4_MAP_NEW;
3927 map_out:
3928 	map->m_flags |= EXT4_MAP_MAPPED;
3929 out1:
3930 	map->m_pblk = newblock;
3931 	if (allocated > map->m_len)
3932 		allocated = map->m_len;
3933 	map->m_len = allocated;
3934 	ext4_ext_show_leaf(inode, path);
3935 out2:
3936 	return err ? err : allocated;
3937 }
3938 
3939 /*
3940  * get_implied_cluster_alloc - check to see if the requested
3941  * allocation (in the map structure) overlaps with a cluster already
3942  * allocated in an extent.
3943  *	@sb	The filesystem superblock structure
3944  *	@map	The requested lblk->pblk mapping
3945  *	@ex	The extent structure which might contain an implied
3946  *			cluster allocation
3947  *
3948  * This function is called by ext4_ext_map_blocks() after we failed to
3949  * find blocks that were already in the inode's extent tree.  Hence,
3950  * we know that the beginning of the requested region cannot overlap
3951  * the extent from the inode's extent tree.  There are three cases we
3952  * want to catch.  The first is this case:
3953  *
3954  *		 |--- cluster # N--|
3955  *    |--- extent ---|	|---- requested region ---|
3956  *			|==========|
3957  *
3958  * The second case that we need to test for is this one:
3959  *
3960  *   |--------- cluster # N ----------------|
3961  *	   |--- requested region --|   |------- extent ----|
3962  *	   |=======================|
3963  *
3964  * The third case is when the requested region lies between two extents
3965  * within the same cluster:
3966  *          |------------- cluster # N-------------|
3967  * |----- ex -----|                  |---- ex_right ----|
3968  *                  |------ requested region ------|
3969  *                  |================|
3970  *
3971  * In each of the above cases, we need to set the map->m_pblk and
3972  * map->m_len so it corresponds to the return the extent labelled as
3973  * "|====|" from cluster #N, since it is already in use for data in
3974  * cluster EXT4_B2C(sbi, map->m_lblk).	We will then return 1 to
3975  * signal to ext4_ext_map_blocks() that map->m_pblk should be treated
3976  * as a new "allocated" block region.  Otherwise, we will return 0 and
3977  * ext4_ext_map_blocks() will then allocate one or more new clusters
3978  * by calling ext4_mb_new_blocks().
3979  */
get_implied_cluster_alloc(struct super_block * sb,struct ext4_map_blocks * map,struct ext4_extent * ex,struct ext4_ext_path * path)3980 static int get_implied_cluster_alloc(struct super_block *sb,
3981 				     struct ext4_map_blocks *map,
3982 				     struct ext4_extent *ex,
3983 				     struct ext4_ext_path *path)
3984 {
3985 	struct ext4_sb_info *sbi = EXT4_SB(sb);
3986 	ext4_lblk_t c_offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
3987 	ext4_lblk_t ex_cluster_start, ex_cluster_end;
3988 	ext4_lblk_t rr_cluster_start;
3989 	ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
3990 	ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
3991 	unsigned short ee_len = ext4_ext_get_actual_len(ex);
3992 
3993 	/* The extent passed in that we are trying to match */
3994 	ex_cluster_start = EXT4_B2C(sbi, ee_block);
3995 	ex_cluster_end = EXT4_B2C(sbi, ee_block + ee_len - 1);
3996 
3997 	/* The requested region passed into ext4_map_blocks() */
3998 	rr_cluster_start = EXT4_B2C(sbi, map->m_lblk);
3999 
4000 	if ((rr_cluster_start == ex_cluster_end) ||
4001 	    (rr_cluster_start == ex_cluster_start)) {
4002 		if (rr_cluster_start == ex_cluster_end)
4003 			ee_start += ee_len - 1;
4004 		map->m_pblk = EXT4_PBLK_CMASK(sbi, ee_start) + c_offset;
4005 		map->m_len = min(map->m_len,
4006 				 (unsigned) sbi->s_cluster_ratio - c_offset);
4007 		/*
4008 		 * Check for and handle this case:
4009 		 *
4010 		 *   |--------- cluster # N-------------|
4011 		 *		       |------- extent ----|
4012 		 *	   |--- requested region ---|
4013 		 *	   |===========|
4014 		 */
4015 
4016 		if (map->m_lblk < ee_block)
4017 			map->m_len = min(map->m_len, ee_block - map->m_lblk);
4018 
4019 		/*
4020 		 * Check for the case where there is already another allocated
4021 		 * block to the right of 'ex' but before the end of the cluster.
4022 		 *
4023 		 *          |------------- cluster # N-------------|
4024 		 * |----- ex -----|                  |---- ex_right ----|
4025 		 *                  |------ requested region ------|
4026 		 *                  |================|
4027 		 */
4028 		if (map->m_lblk > ee_block) {
4029 			ext4_lblk_t next = ext4_ext_next_allocated_block(path);
4030 			map->m_len = min(map->m_len, next - map->m_lblk);
4031 		}
4032 
4033 		trace_ext4_get_implied_cluster_alloc_exit(sb, map, 1);
4034 		return 1;
4035 	}
4036 
4037 	trace_ext4_get_implied_cluster_alloc_exit(sb, map, 0);
4038 	return 0;
4039 }
4040 
4041 /*
4042  * Determine hole length around the given logical block, first try to
4043  * locate and expand the hole from the given @path, and then adjust it
4044  * if it's partially or completely converted to delayed extents, insert
4045  * it into the extent cache tree if it's indeed a hole, finally return
4046  * the length of the determined extent.
4047  */
ext4_ext_determine_insert_hole(struct inode * inode,struct ext4_ext_path * path,ext4_lblk_t lblk)4048 static ext4_lblk_t ext4_ext_determine_insert_hole(struct inode *inode,
4049 						  struct ext4_ext_path *path,
4050 						  ext4_lblk_t lblk)
4051 {
4052 	ext4_lblk_t hole_start, len;
4053 	struct extent_status es;
4054 
4055 	hole_start = lblk;
4056 	len = ext4_ext_find_hole(inode, path, &hole_start);
4057 again:
4058 	ext4_es_find_extent_range(inode, &ext4_es_is_delayed, hole_start,
4059 				  hole_start + len - 1, &es);
4060 	if (!es.es_len)
4061 		goto insert_hole;
4062 
4063 	/*
4064 	 * There's a delalloc extent in the hole, handle it if the delalloc
4065 	 * extent is in front of, behind and straddle the queried range.
4066 	 */
4067 	if (lblk >= es.es_lblk + es.es_len) {
4068 		/*
4069 		 * The delalloc extent is in front of the queried range,
4070 		 * find again from the queried start block.
4071 		 */
4072 		len -= lblk - hole_start;
4073 		hole_start = lblk;
4074 		goto again;
4075 	} else if (in_range(lblk, es.es_lblk, es.es_len)) {
4076 		/*
4077 		 * The delalloc extent containing lblk, it must have been
4078 		 * added after ext4_map_blocks() checked the extent status
4079 		 * tree, adjust the length to the delalloc extent's after
4080 		 * lblk.
4081 		 */
4082 		len = es.es_lblk + es.es_len - lblk;
4083 		return len;
4084 	} else {
4085 		/*
4086 		 * The delalloc extent is partially or completely behind
4087 		 * the queried range, update hole length until the
4088 		 * beginning of the delalloc extent.
4089 		 */
4090 		len = min(es.es_lblk - hole_start, len);
4091 	}
4092 
4093 insert_hole:
4094 	/* Put just found gap into cache to speed up subsequent requests */
4095 	ext_debug(inode, " -> %u:%u\n", hole_start, len);
4096 	ext4_es_insert_extent(inode, hole_start, len, ~0, EXTENT_STATUS_HOLE);
4097 
4098 	/* Update hole_len to reflect hole size after lblk */
4099 	if (hole_start != lblk)
4100 		len -= lblk - hole_start;
4101 
4102 	return len;
4103 }
4104 
4105 /*
4106  * Block allocation/map/preallocation routine for extents based files
4107  *
4108  *
4109  * Need to be called with
4110  * down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system block
4111  * (ie, create is zero). Otherwise down_write(&EXT4_I(inode)->i_data_sem)
4112  *
4113  * return > 0, number of blocks already mapped/allocated
4114  *          if create == 0 and these are pre-allocated blocks
4115  *          	buffer head is unmapped
4116  *          otherwise blocks are mapped
4117  *
4118  * return = 0, if plain look up failed (blocks have not been allocated)
4119  *          buffer head is unmapped
4120  *
4121  * return < 0, error case.
4122  */
ext4_ext_map_blocks(handle_t * handle,struct inode * inode,struct ext4_map_blocks * map,int flags)4123 int ext4_ext_map_blocks(handle_t *handle, struct inode *inode,
4124 			struct ext4_map_blocks *map, int flags)
4125 {
4126 	struct ext4_ext_path *path = NULL;
4127 	struct ext4_extent newex, *ex, ex2;
4128 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
4129 	ext4_fsblk_t newblock = 0, pblk;
4130 	int err = 0, depth, ret;
4131 	unsigned int allocated = 0, offset = 0;
4132 	unsigned int allocated_clusters = 0;
4133 	struct ext4_allocation_request ar;
4134 	ext4_lblk_t cluster_offset;
4135 
4136 	ext_debug(inode, "blocks %u/%u requested\n", map->m_lblk, map->m_len);
4137 	trace_ext4_ext_map_blocks_enter(inode, map->m_lblk, map->m_len, flags);
4138 
4139 	/* find extent for this block */
4140 	path = ext4_find_extent(inode, map->m_lblk, NULL, 0);
4141 	if (IS_ERR(path)) {
4142 		err = PTR_ERR(path);
4143 		path = NULL;
4144 		goto out;
4145 	}
4146 
4147 	depth = ext_depth(inode);
4148 
4149 	/*
4150 	 * consistent leaf must not be empty;
4151 	 * this situation is possible, though, _during_ tree modification;
4152 	 * this is why assert can't be put in ext4_find_extent()
4153 	 */
4154 	if (unlikely(path[depth].p_ext == NULL && depth != 0)) {
4155 		EXT4_ERROR_INODE(inode, "bad extent address "
4156 				 "lblock: %lu, depth: %d pblock %lld",
4157 				 (unsigned long) map->m_lblk, depth,
4158 				 path[depth].p_block);
4159 		err = -EFSCORRUPTED;
4160 		goto out;
4161 	}
4162 
4163 	ex = path[depth].p_ext;
4164 	if (ex) {
4165 		ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
4166 		ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
4167 		unsigned short ee_len;
4168 
4169 
4170 		/*
4171 		 * unwritten extents are treated as holes, except that
4172 		 * we split out initialized portions during a write.
4173 		 */
4174 		ee_len = ext4_ext_get_actual_len(ex);
4175 
4176 		trace_ext4_ext_show_extent(inode, ee_block, ee_start, ee_len);
4177 
4178 		/* if found extent covers block, simply return it */
4179 		if (in_range(map->m_lblk, ee_block, ee_len)) {
4180 			newblock = map->m_lblk - ee_block + ee_start;
4181 			/* number of remaining blocks in the extent */
4182 			allocated = ee_len - (map->m_lblk - ee_block);
4183 			ext_debug(inode, "%u fit into %u:%d -> %llu\n",
4184 				  map->m_lblk, ee_block, ee_len, newblock);
4185 
4186 			/*
4187 			 * If the extent is initialized check whether the
4188 			 * caller wants to convert it to unwritten.
4189 			 */
4190 			if ((!ext4_ext_is_unwritten(ex)) &&
4191 			    (flags & EXT4_GET_BLOCKS_CONVERT_UNWRITTEN)) {
4192 				err = convert_initialized_extent(handle,
4193 					inode, map, &path, &allocated);
4194 				goto out;
4195 			} else if (!ext4_ext_is_unwritten(ex)) {
4196 				map->m_flags |= EXT4_MAP_MAPPED;
4197 				map->m_pblk = newblock;
4198 				if (allocated > map->m_len)
4199 					allocated = map->m_len;
4200 				map->m_len = allocated;
4201 				ext4_ext_show_leaf(inode, path);
4202 				goto out;
4203 			}
4204 
4205 			ret = ext4_ext_handle_unwritten_extents(
4206 				handle, inode, map, &path, flags,
4207 				allocated, newblock);
4208 			if (ret < 0)
4209 				err = ret;
4210 			else
4211 				allocated = ret;
4212 			goto out;
4213 		}
4214 	}
4215 
4216 	/*
4217 	 * requested block isn't allocated yet;
4218 	 * we couldn't try to create block if create flag is zero
4219 	 */
4220 	if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
4221 		ext4_lblk_t len;
4222 
4223 		len = ext4_ext_determine_insert_hole(inode, path, map->m_lblk);
4224 
4225 		map->m_pblk = 0;
4226 		map->m_len = min_t(unsigned int, map->m_len, len);
4227 		goto out;
4228 	}
4229 
4230 	/*
4231 	 * Okay, we need to do block allocation.
4232 	 */
4233 	newex.ee_block = cpu_to_le32(map->m_lblk);
4234 	cluster_offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4235 
4236 	/*
4237 	 * If we are doing bigalloc, check to see if the extent returned
4238 	 * by ext4_find_extent() implies a cluster we can use.
4239 	 */
4240 	if (cluster_offset && ex &&
4241 	    get_implied_cluster_alloc(inode->i_sb, map, ex, path)) {
4242 		ar.len = allocated = map->m_len;
4243 		newblock = map->m_pblk;
4244 		goto got_allocated_blocks;
4245 	}
4246 
4247 	/* find neighbour allocated blocks */
4248 	ar.lleft = map->m_lblk;
4249 	err = ext4_ext_search_left(inode, path, &ar.lleft, &ar.pleft);
4250 	if (err)
4251 		goto out;
4252 	ar.lright = map->m_lblk;
4253 	err = ext4_ext_search_right(inode, path, &ar.lright, &ar.pright, &ex2);
4254 	if (err < 0)
4255 		goto out;
4256 
4257 	/* Check if the extent after searching to the right implies a
4258 	 * cluster we can use. */
4259 	if ((sbi->s_cluster_ratio > 1) && err &&
4260 	    get_implied_cluster_alloc(inode->i_sb, map, &ex2, path)) {
4261 		ar.len = allocated = map->m_len;
4262 		newblock = map->m_pblk;
4263 		goto got_allocated_blocks;
4264 	}
4265 
4266 	/*
4267 	 * See if request is beyond maximum number of blocks we can have in
4268 	 * a single extent. For an initialized extent this limit is
4269 	 * EXT_INIT_MAX_LEN and for an unwritten extent this limit is
4270 	 * EXT_UNWRITTEN_MAX_LEN.
4271 	 */
4272 	if (map->m_len > EXT_INIT_MAX_LEN &&
4273 	    !(flags & EXT4_GET_BLOCKS_UNWRIT_EXT))
4274 		map->m_len = EXT_INIT_MAX_LEN;
4275 	else if (map->m_len > EXT_UNWRITTEN_MAX_LEN &&
4276 		 (flags & EXT4_GET_BLOCKS_UNWRIT_EXT))
4277 		map->m_len = EXT_UNWRITTEN_MAX_LEN;
4278 
4279 	/* Check if we can really insert (m_lblk)::(m_lblk + m_len) extent */
4280 	newex.ee_len = cpu_to_le16(map->m_len);
4281 	err = ext4_ext_check_overlap(sbi, inode, &newex, path);
4282 	if (err)
4283 		allocated = ext4_ext_get_actual_len(&newex);
4284 	else
4285 		allocated = map->m_len;
4286 
4287 	/* allocate new block */
4288 	ar.inode = inode;
4289 	ar.goal = ext4_ext_find_goal(inode, path, map->m_lblk);
4290 	ar.logical = map->m_lblk;
4291 	/*
4292 	 * We calculate the offset from the beginning of the cluster
4293 	 * for the logical block number, since when we allocate a
4294 	 * physical cluster, the physical block should start at the
4295 	 * same offset from the beginning of the cluster.  This is
4296 	 * needed so that future calls to get_implied_cluster_alloc()
4297 	 * work correctly.
4298 	 */
4299 	offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4300 	ar.len = EXT4_NUM_B2C(sbi, offset+allocated);
4301 	ar.goal -= offset;
4302 	ar.logical -= offset;
4303 	if (S_ISREG(inode->i_mode))
4304 		ar.flags = EXT4_MB_HINT_DATA;
4305 	else
4306 		/* disable in-core preallocation for non-regular files */
4307 		ar.flags = 0;
4308 	if (flags & EXT4_GET_BLOCKS_NO_NORMALIZE)
4309 		ar.flags |= EXT4_MB_HINT_NOPREALLOC;
4310 	if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
4311 		ar.flags |= EXT4_MB_DELALLOC_RESERVED;
4312 	if (flags & EXT4_GET_BLOCKS_METADATA_NOFAIL)
4313 		ar.flags |= EXT4_MB_USE_RESERVED;
4314 	newblock = ext4_mb_new_blocks(handle, &ar, &err);
4315 	if (!newblock)
4316 		goto out;
4317 	allocated_clusters = ar.len;
4318 	ar.len = EXT4_C2B(sbi, ar.len) - offset;
4319 	ext_debug(inode, "allocate new block: goal %llu, found %llu/%u, requested %u\n",
4320 		  ar.goal, newblock, ar.len, allocated);
4321 	if (ar.len > allocated)
4322 		ar.len = allocated;
4323 
4324 got_allocated_blocks:
4325 	/* try to insert new extent into found leaf and return */
4326 	pblk = newblock + offset;
4327 	ext4_ext_store_pblock(&newex, pblk);
4328 	newex.ee_len = cpu_to_le16(ar.len);
4329 	/* Mark unwritten */
4330 	if (flags & EXT4_GET_BLOCKS_UNWRIT_EXT) {
4331 		ext4_ext_mark_unwritten(&newex);
4332 		map->m_flags |= EXT4_MAP_UNWRITTEN;
4333 	}
4334 
4335 	err = ext4_ext_insert_extent(handle, inode, &path, &newex, flags);
4336 	if (err) {
4337 		if (allocated_clusters) {
4338 			int fb_flags = 0;
4339 
4340 			/*
4341 			 * free data blocks we just allocated.
4342 			 * not a good idea to call discard here directly,
4343 			 * but otherwise we'd need to call it every free().
4344 			 */
4345 			ext4_discard_preallocations(inode, 0);
4346 			if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
4347 				fb_flags = EXT4_FREE_BLOCKS_NO_QUOT_UPDATE;
4348 			ext4_free_blocks(handle, inode, NULL, newblock,
4349 					 EXT4_C2B(sbi, allocated_clusters),
4350 					 fb_flags);
4351 		}
4352 		goto out;
4353 	}
4354 
4355 	/*
4356 	 * Reduce the reserved cluster count to reflect successful deferred
4357 	 * allocation of delayed allocated clusters or direct allocation of
4358 	 * clusters discovered to be delayed allocated.  Once allocated, a
4359 	 * cluster is not included in the reserved count.
4360 	 */
4361 	if (test_opt(inode->i_sb, DELALLOC) && allocated_clusters) {
4362 		if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE) {
4363 			/*
4364 			 * When allocating delayed allocated clusters, simply
4365 			 * reduce the reserved cluster count and claim quota
4366 			 */
4367 			ext4_da_update_reserve_space(inode, allocated_clusters,
4368 							1);
4369 		} else {
4370 			ext4_lblk_t lblk, len;
4371 			unsigned int n;
4372 
4373 			/*
4374 			 * When allocating non-delayed allocated clusters
4375 			 * (from fallocate, filemap, DIO, or clusters
4376 			 * allocated when delalloc has been disabled by
4377 			 * ext4_nonda_switch), reduce the reserved cluster
4378 			 * count by the number of allocated clusters that
4379 			 * have previously been delayed allocated.  Quota
4380 			 * has been claimed by ext4_mb_new_blocks() above,
4381 			 * so release the quota reservations made for any
4382 			 * previously delayed allocated clusters.
4383 			 */
4384 			lblk = EXT4_LBLK_CMASK(sbi, map->m_lblk);
4385 			len = allocated_clusters << sbi->s_cluster_bits;
4386 			n = ext4_es_delayed_clu(inode, lblk, len);
4387 			if (n > 0)
4388 				ext4_da_update_reserve_space(inode, (int) n, 0);
4389 		}
4390 	}
4391 
4392 	/*
4393 	 * Cache the extent and update transaction to commit on fdatasync only
4394 	 * when it is _not_ an unwritten extent.
4395 	 */
4396 	if ((flags & EXT4_GET_BLOCKS_UNWRIT_EXT) == 0)
4397 		ext4_update_inode_fsync_trans(handle, inode, 1);
4398 	else
4399 		ext4_update_inode_fsync_trans(handle, inode, 0);
4400 
4401 	map->m_flags |= (EXT4_MAP_NEW | EXT4_MAP_MAPPED);
4402 	map->m_pblk = pblk;
4403 	map->m_len = ar.len;
4404 	allocated = map->m_len;
4405 	ext4_ext_show_leaf(inode, path);
4406 out:
4407 	ext4_free_ext_path(path);
4408 
4409 	trace_ext4_ext_map_blocks_exit(inode, flags, map,
4410 				       err ? err : allocated);
4411 	return err ? err : allocated;
4412 }
4413 
ext4_ext_truncate(handle_t * handle,struct inode * inode)4414 int ext4_ext_truncate(handle_t *handle, struct inode *inode)
4415 {
4416 	struct super_block *sb = inode->i_sb;
4417 	ext4_lblk_t last_block;
4418 	int err = 0;
4419 
4420 	/*
4421 	 * TODO: optimization is possible here.
4422 	 * Probably we need not scan at all,
4423 	 * because page truncation is enough.
4424 	 */
4425 
4426 	/* we have to know where to truncate from in crash case */
4427 	EXT4_I(inode)->i_disksize = inode->i_size;
4428 	err = ext4_mark_inode_dirty(handle, inode);
4429 	if (err)
4430 		return err;
4431 
4432 	last_block = (inode->i_size + sb->s_blocksize - 1)
4433 			>> EXT4_BLOCK_SIZE_BITS(sb);
4434 	ext4_es_remove_extent(inode, last_block, EXT_MAX_BLOCKS - last_block);
4435 
4436 retry_remove_space:
4437 	err = ext4_ext_remove_space(inode, last_block, EXT_MAX_BLOCKS - 1);
4438 	if (err == -ENOMEM) {
4439 		memalloc_retry_wait(GFP_ATOMIC);
4440 		goto retry_remove_space;
4441 	}
4442 	return err;
4443 }
4444 
ext4_alloc_file_blocks(struct file * file,ext4_lblk_t offset,ext4_lblk_t len,loff_t new_size,int flags)4445 static int ext4_alloc_file_blocks(struct file *file, ext4_lblk_t offset,
4446 				  ext4_lblk_t len, loff_t new_size,
4447 				  int flags)
4448 {
4449 	struct inode *inode = file_inode(file);
4450 	handle_t *handle;
4451 	int ret = 0, ret2 = 0, ret3 = 0;
4452 	int retries = 0;
4453 	int depth = 0;
4454 	struct ext4_map_blocks map;
4455 	unsigned int credits;
4456 	loff_t epos;
4457 
4458 	BUG_ON(!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS));
4459 	map.m_lblk = offset;
4460 	map.m_len = len;
4461 	/*
4462 	 * Don't normalize the request if it can fit in one extent so
4463 	 * that it doesn't get unnecessarily split into multiple
4464 	 * extents.
4465 	 */
4466 	if (len <= EXT_UNWRITTEN_MAX_LEN)
4467 		flags |= EXT4_GET_BLOCKS_NO_NORMALIZE;
4468 
4469 	/*
4470 	 * credits to insert 1 extent into extent tree
4471 	 */
4472 	credits = ext4_chunk_trans_blocks(inode, len);
4473 	depth = ext_depth(inode);
4474 
4475 retry:
4476 	while (len) {
4477 		/*
4478 		 * Recalculate credits when extent tree depth changes.
4479 		 */
4480 		if (depth != ext_depth(inode)) {
4481 			credits = ext4_chunk_trans_blocks(inode, len);
4482 			depth = ext_depth(inode);
4483 		}
4484 
4485 		handle = ext4_journal_start(inode, EXT4_HT_MAP_BLOCKS,
4486 					    credits);
4487 		if (IS_ERR(handle)) {
4488 			ret = PTR_ERR(handle);
4489 			break;
4490 		}
4491 		ret = ext4_map_blocks(handle, inode, &map, flags);
4492 		if (ret <= 0) {
4493 			ext4_debug("inode #%lu: block %u: len %u: "
4494 				   "ext4_ext_map_blocks returned %d",
4495 				   inode->i_ino, map.m_lblk,
4496 				   map.m_len, ret);
4497 			ext4_mark_inode_dirty(handle, inode);
4498 			ext4_journal_stop(handle);
4499 			break;
4500 		}
4501 		/*
4502 		 * allow a full retry cycle for any remaining allocations
4503 		 */
4504 		retries = 0;
4505 		map.m_lblk += ret;
4506 		map.m_len = len = len - ret;
4507 		epos = (loff_t)map.m_lblk << inode->i_blkbits;
4508 		inode_set_ctime_current(inode);
4509 		if (new_size) {
4510 			if (epos > new_size)
4511 				epos = new_size;
4512 			if (ext4_update_inode_size(inode, epos) & 0x1)
4513 				inode->i_mtime = inode_get_ctime(inode);
4514 		}
4515 		ret2 = ext4_mark_inode_dirty(handle, inode);
4516 		ext4_update_inode_fsync_trans(handle, inode, 1);
4517 		ret3 = ext4_journal_stop(handle);
4518 		ret2 = ret3 ? ret3 : ret2;
4519 		if (unlikely(ret2))
4520 			break;
4521 	}
4522 	if (ret == -ENOSPC && ext4_should_retry_alloc(inode->i_sb, &retries))
4523 		goto retry;
4524 
4525 	return ret > 0 ? ret2 : ret;
4526 }
4527 
4528 static int ext4_collapse_range(struct file *file, loff_t offset, loff_t len);
4529 
4530 static int ext4_insert_range(struct file *file, loff_t offset, loff_t len);
4531 
ext4_zero_range(struct file * file,loff_t offset,loff_t len,int mode)4532 static long ext4_zero_range(struct file *file, loff_t offset,
4533 			    loff_t len, int mode)
4534 {
4535 	struct inode *inode = file_inode(file);
4536 	struct address_space *mapping = file->f_mapping;
4537 	handle_t *handle = NULL;
4538 	unsigned int max_blocks;
4539 	loff_t new_size = 0;
4540 	int ret = 0;
4541 	int flags;
4542 	int credits;
4543 	int partial_begin, partial_end;
4544 	loff_t start, end;
4545 	ext4_lblk_t lblk;
4546 	unsigned int blkbits = inode->i_blkbits;
4547 
4548 	trace_ext4_zero_range(inode, offset, len, mode);
4549 
4550 	/*
4551 	 * Round up offset. This is not fallocate, we need to zero out
4552 	 * blocks, so convert interior block aligned part of the range to
4553 	 * unwritten and possibly manually zero out unaligned parts of the
4554 	 * range. Here, start and partial_begin are inclusive, end and
4555 	 * partial_end are exclusive.
4556 	 */
4557 	start = round_up(offset, 1 << blkbits);
4558 	end = round_down((offset + len), 1 << blkbits);
4559 
4560 	if (start < offset || end > offset + len)
4561 		return -EINVAL;
4562 	partial_begin = offset & ((1 << blkbits) - 1);
4563 	partial_end = (offset + len) & ((1 << blkbits) - 1);
4564 
4565 	lblk = start >> blkbits;
4566 	max_blocks = (end >> blkbits);
4567 	if (max_blocks < lblk)
4568 		max_blocks = 0;
4569 	else
4570 		max_blocks -= lblk;
4571 
4572 	inode_lock(inode);
4573 
4574 	/*
4575 	 * Indirect files do not support unwritten extents
4576 	 */
4577 	if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))) {
4578 		ret = -EOPNOTSUPP;
4579 		goto out_mutex;
4580 	}
4581 
4582 	if (!(mode & FALLOC_FL_KEEP_SIZE) &&
4583 	    (offset + len > inode->i_size ||
4584 	     offset + len > EXT4_I(inode)->i_disksize)) {
4585 		new_size = offset + len;
4586 		ret = inode_newsize_ok(inode, new_size);
4587 		if (ret)
4588 			goto out_mutex;
4589 	}
4590 
4591 	flags = EXT4_GET_BLOCKS_CREATE_UNWRIT_EXT;
4592 
4593 	/* Wait all existing dio workers, newcomers will block on i_rwsem */
4594 	inode_dio_wait(inode);
4595 
4596 	ret = file_modified(file);
4597 	if (ret)
4598 		goto out_mutex;
4599 
4600 	/* Preallocate the range including the unaligned edges */
4601 	if (partial_begin || partial_end) {
4602 		ret = ext4_alloc_file_blocks(file,
4603 				round_down(offset, 1 << blkbits) >> blkbits,
4604 				(round_up((offset + len), 1 << blkbits) -
4605 				 round_down(offset, 1 << blkbits)) >> blkbits,
4606 				new_size, flags);
4607 		if (ret)
4608 			goto out_mutex;
4609 
4610 	}
4611 
4612 	/* Zero range excluding the unaligned edges */
4613 	if (max_blocks > 0) {
4614 		flags |= (EXT4_GET_BLOCKS_CONVERT_UNWRITTEN |
4615 			  EXT4_EX_NOCACHE);
4616 
4617 		/*
4618 		 * Prevent page faults from reinstantiating pages we have
4619 		 * released from page cache.
4620 		 */
4621 		filemap_invalidate_lock(mapping);
4622 
4623 		ret = ext4_break_layouts(inode);
4624 		if (ret) {
4625 			filemap_invalidate_unlock(mapping);
4626 			goto out_mutex;
4627 		}
4628 
4629 		ret = ext4_update_disksize_before_punch(inode, offset, len);
4630 		if (ret) {
4631 			filemap_invalidate_unlock(mapping);
4632 			goto out_mutex;
4633 		}
4634 
4635 		/*
4636 		 * For journalled data we need to write (and checkpoint) pages
4637 		 * before discarding page cache to avoid inconsitent data on
4638 		 * disk in case of crash before zeroing trans is committed.
4639 		 */
4640 		if (ext4_should_journal_data(inode)) {
4641 			ret = filemap_write_and_wait_range(mapping, start,
4642 							   end - 1);
4643 			if (ret) {
4644 				filemap_invalidate_unlock(mapping);
4645 				goto out_mutex;
4646 			}
4647 		}
4648 
4649 		/* Now release the pages and zero block aligned part of pages */
4650 		truncate_pagecache_range(inode, start, end - 1);
4651 		inode->i_mtime = inode_set_ctime_current(inode);
4652 
4653 		ret = ext4_alloc_file_blocks(file, lblk, max_blocks, new_size,
4654 					     flags);
4655 		filemap_invalidate_unlock(mapping);
4656 		if (ret)
4657 			goto out_mutex;
4658 	}
4659 	if (!partial_begin && !partial_end)
4660 		goto out_mutex;
4661 
4662 	/*
4663 	 * In worst case we have to writeout two nonadjacent unwritten
4664 	 * blocks and update the inode
4665 	 */
4666 	credits = (2 * ext4_ext_index_trans_blocks(inode, 2)) + 1;
4667 	if (ext4_should_journal_data(inode))
4668 		credits += 2;
4669 	handle = ext4_journal_start(inode, EXT4_HT_MISC, credits);
4670 	if (IS_ERR(handle)) {
4671 		ret = PTR_ERR(handle);
4672 		ext4_std_error(inode->i_sb, ret);
4673 		goto out_mutex;
4674 	}
4675 
4676 	inode->i_mtime = inode_set_ctime_current(inode);
4677 	if (new_size)
4678 		ext4_update_inode_size(inode, new_size);
4679 	ret = ext4_mark_inode_dirty(handle, inode);
4680 	if (unlikely(ret))
4681 		goto out_handle;
4682 	/* Zero out partial block at the edges of the range */
4683 	ret = ext4_zero_partial_blocks(handle, inode, offset, len);
4684 	if (ret >= 0)
4685 		ext4_update_inode_fsync_trans(handle, inode, 1);
4686 
4687 	if (file->f_flags & O_SYNC)
4688 		ext4_handle_sync(handle);
4689 
4690 out_handle:
4691 	ext4_journal_stop(handle);
4692 out_mutex:
4693 	inode_unlock(inode);
4694 	return ret;
4695 }
4696 
4697 /*
4698  * preallocate space for a file. This implements ext4's fallocate file
4699  * operation, which gets called from sys_fallocate system call.
4700  * For block-mapped files, posix_fallocate should fall back to the method
4701  * of writing zeroes to the required new blocks (the same behavior which is
4702  * expected for file systems which do not support fallocate() system call).
4703  */
ext4_fallocate(struct file * file,int mode,loff_t offset,loff_t len)4704 long ext4_fallocate(struct file *file, int mode, loff_t offset, loff_t len)
4705 {
4706 	struct inode *inode = file_inode(file);
4707 	loff_t new_size = 0;
4708 	unsigned int max_blocks;
4709 	int ret = 0;
4710 	int flags;
4711 	ext4_lblk_t lblk;
4712 	unsigned int blkbits = inode->i_blkbits;
4713 
4714 	/*
4715 	 * Encrypted inodes can't handle collapse range or insert
4716 	 * range since we would need to re-encrypt blocks with a
4717 	 * different IV or XTS tweak (which are based on the logical
4718 	 * block number).
4719 	 */
4720 	if (IS_ENCRYPTED(inode) &&
4721 	    (mode & (FALLOC_FL_COLLAPSE_RANGE | FALLOC_FL_INSERT_RANGE)))
4722 		return -EOPNOTSUPP;
4723 
4724 	/* Return error if mode is not supported */
4725 	if (mode & ~(FALLOC_FL_KEEP_SIZE | FALLOC_FL_PUNCH_HOLE |
4726 		     FALLOC_FL_COLLAPSE_RANGE | FALLOC_FL_ZERO_RANGE |
4727 		     FALLOC_FL_INSERT_RANGE))
4728 		return -EOPNOTSUPP;
4729 
4730 	inode_lock(inode);
4731 	ret = ext4_convert_inline_data(inode);
4732 	inode_unlock(inode);
4733 	if (ret)
4734 		goto exit;
4735 
4736 	if (mode & FALLOC_FL_PUNCH_HOLE) {
4737 		ret = ext4_punch_hole(file, offset, len);
4738 		goto exit;
4739 	}
4740 
4741 	if (mode & FALLOC_FL_COLLAPSE_RANGE) {
4742 		ret = ext4_collapse_range(file, offset, len);
4743 		goto exit;
4744 	}
4745 
4746 	if (mode & FALLOC_FL_INSERT_RANGE) {
4747 		ret = ext4_insert_range(file, offset, len);
4748 		goto exit;
4749 	}
4750 
4751 	if (mode & FALLOC_FL_ZERO_RANGE) {
4752 		ret = ext4_zero_range(file, offset, len, mode);
4753 		goto exit;
4754 	}
4755 	trace_ext4_fallocate_enter(inode, offset, len, mode);
4756 	lblk = offset >> blkbits;
4757 
4758 	max_blocks = EXT4_MAX_BLOCKS(len, offset, blkbits);
4759 	flags = EXT4_GET_BLOCKS_CREATE_UNWRIT_EXT;
4760 
4761 	inode_lock(inode);
4762 
4763 	/*
4764 	 * We only support preallocation for extent-based files only
4765 	 */
4766 	if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))) {
4767 		ret = -EOPNOTSUPP;
4768 		goto out;
4769 	}
4770 
4771 	if (!(mode & FALLOC_FL_KEEP_SIZE) &&
4772 	    (offset + len > inode->i_size ||
4773 	     offset + len > EXT4_I(inode)->i_disksize)) {
4774 		new_size = offset + len;
4775 		ret = inode_newsize_ok(inode, new_size);
4776 		if (ret)
4777 			goto out;
4778 	}
4779 
4780 	/* Wait all existing dio workers, newcomers will block on i_rwsem */
4781 	inode_dio_wait(inode);
4782 
4783 	ret = file_modified(file);
4784 	if (ret)
4785 		goto out;
4786 
4787 	ret = ext4_alloc_file_blocks(file, lblk, max_blocks, new_size, flags);
4788 	if (ret)
4789 		goto out;
4790 
4791 	if (file->f_flags & O_SYNC && EXT4_SB(inode->i_sb)->s_journal) {
4792 		ret = ext4_fc_commit(EXT4_SB(inode->i_sb)->s_journal,
4793 					EXT4_I(inode)->i_sync_tid);
4794 	}
4795 out:
4796 	inode_unlock(inode);
4797 	trace_ext4_fallocate_exit(inode, offset, max_blocks, ret);
4798 exit:
4799 	return ret;
4800 }
4801 
4802 /*
4803  * This function convert a range of blocks to written extents
4804  * The caller of this function will pass the start offset and the size.
4805  * all unwritten extents within this range will be converted to
4806  * written extents.
4807  *
4808  * This function is called from the direct IO end io call back
4809  * function, to convert the fallocated extents after IO is completed.
4810  * Returns 0 on success.
4811  */
ext4_convert_unwritten_extents(handle_t * handle,struct inode * inode,loff_t offset,ssize_t len)4812 int ext4_convert_unwritten_extents(handle_t *handle, struct inode *inode,
4813 				   loff_t offset, ssize_t len)
4814 {
4815 	unsigned int max_blocks;
4816 	int ret = 0, ret2 = 0, ret3 = 0;
4817 	struct ext4_map_blocks map;
4818 	unsigned int blkbits = inode->i_blkbits;
4819 	unsigned int credits = 0;
4820 
4821 	map.m_lblk = offset >> blkbits;
4822 	max_blocks = EXT4_MAX_BLOCKS(len, offset, blkbits);
4823 
4824 	if (!handle) {
4825 		/*
4826 		 * credits to insert 1 extent into extent tree
4827 		 */
4828 		credits = ext4_chunk_trans_blocks(inode, max_blocks);
4829 	}
4830 	while (ret >= 0 && ret < max_blocks) {
4831 		map.m_lblk += ret;
4832 		map.m_len = (max_blocks -= ret);
4833 		if (credits) {
4834 			handle = ext4_journal_start(inode, EXT4_HT_MAP_BLOCKS,
4835 						    credits);
4836 			if (IS_ERR(handle)) {
4837 				ret = PTR_ERR(handle);
4838 				break;
4839 			}
4840 		}
4841 		ret = ext4_map_blocks(handle, inode, &map,
4842 				      EXT4_GET_BLOCKS_IO_CONVERT_EXT);
4843 		if (ret <= 0)
4844 			ext4_warning(inode->i_sb,
4845 				     "inode #%lu: block %u: len %u: "
4846 				     "ext4_ext_map_blocks returned %d",
4847 				     inode->i_ino, map.m_lblk,
4848 				     map.m_len, ret);
4849 		ret2 = ext4_mark_inode_dirty(handle, inode);
4850 		if (credits) {
4851 			ret3 = ext4_journal_stop(handle);
4852 			if (unlikely(ret3))
4853 				ret2 = ret3;
4854 		}
4855 
4856 		if (ret <= 0 || ret2)
4857 			break;
4858 	}
4859 	return ret > 0 ? ret2 : ret;
4860 }
4861 
ext4_convert_unwritten_io_end_vec(handle_t * handle,ext4_io_end_t * io_end)4862 int ext4_convert_unwritten_io_end_vec(handle_t *handle, ext4_io_end_t *io_end)
4863 {
4864 	int ret = 0, err = 0;
4865 	struct ext4_io_end_vec *io_end_vec;
4866 
4867 	/*
4868 	 * This is somewhat ugly but the idea is clear: When transaction is
4869 	 * reserved, everything goes into it. Otherwise we rather start several
4870 	 * smaller transactions for conversion of each extent separately.
4871 	 */
4872 	if (handle) {
4873 		handle = ext4_journal_start_reserved(handle,
4874 						     EXT4_HT_EXT_CONVERT);
4875 		if (IS_ERR(handle))
4876 			return PTR_ERR(handle);
4877 	}
4878 
4879 	list_for_each_entry(io_end_vec, &io_end->list_vec, list) {
4880 		ret = ext4_convert_unwritten_extents(handle, io_end->inode,
4881 						     io_end_vec->offset,
4882 						     io_end_vec->size);
4883 		if (ret)
4884 			break;
4885 	}
4886 
4887 	if (handle)
4888 		err = ext4_journal_stop(handle);
4889 
4890 	return ret < 0 ? ret : err;
4891 }
4892 
ext4_iomap_xattr_fiemap(struct inode * inode,struct iomap * iomap)4893 static int ext4_iomap_xattr_fiemap(struct inode *inode, struct iomap *iomap)
4894 {
4895 	__u64 physical = 0;
4896 	__u64 length = 0;
4897 	int blockbits = inode->i_sb->s_blocksize_bits;
4898 	int error = 0;
4899 	u16 iomap_type;
4900 
4901 	/* in-inode? */
4902 	if (ext4_test_inode_state(inode, EXT4_STATE_XATTR)) {
4903 		struct ext4_iloc iloc;
4904 		int offset;	/* offset of xattr in inode */
4905 
4906 		error = ext4_get_inode_loc(inode, &iloc);
4907 		if (error)
4908 			return error;
4909 		physical = (__u64)iloc.bh->b_blocknr << blockbits;
4910 		offset = EXT4_GOOD_OLD_INODE_SIZE +
4911 				EXT4_I(inode)->i_extra_isize;
4912 		physical += offset;
4913 		length = EXT4_SB(inode->i_sb)->s_inode_size - offset;
4914 		brelse(iloc.bh);
4915 		iomap_type = IOMAP_INLINE;
4916 	} else if (EXT4_I(inode)->i_file_acl) { /* external block */
4917 		physical = (__u64)EXT4_I(inode)->i_file_acl << blockbits;
4918 		length = inode->i_sb->s_blocksize;
4919 		iomap_type = IOMAP_MAPPED;
4920 	} else {
4921 		/* no in-inode or external block for xattr, so return -ENOENT */
4922 		error = -ENOENT;
4923 		goto out;
4924 	}
4925 
4926 	iomap->addr = physical;
4927 	iomap->offset = 0;
4928 	iomap->length = length;
4929 	iomap->type = iomap_type;
4930 	iomap->flags = 0;
4931 out:
4932 	return error;
4933 }
4934 
ext4_iomap_xattr_begin(struct inode * inode,loff_t offset,loff_t length,unsigned flags,struct iomap * iomap,struct iomap * srcmap)4935 static int ext4_iomap_xattr_begin(struct inode *inode, loff_t offset,
4936 				  loff_t length, unsigned flags,
4937 				  struct iomap *iomap, struct iomap *srcmap)
4938 {
4939 	int error;
4940 
4941 	error = ext4_iomap_xattr_fiemap(inode, iomap);
4942 	if (error == 0 && (offset >= iomap->length))
4943 		error = -ENOENT;
4944 	return error;
4945 }
4946 
4947 static const struct iomap_ops ext4_iomap_xattr_ops = {
4948 	.iomap_begin		= ext4_iomap_xattr_begin,
4949 };
4950 
ext4_fiemap_check_ranges(struct inode * inode,u64 start,u64 * len)4951 static int ext4_fiemap_check_ranges(struct inode *inode, u64 start, u64 *len)
4952 {
4953 	u64 maxbytes;
4954 
4955 	if (ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
4956 		maxbytes = inode->i_sb->s_maxbytes;
4957 	else
4958 		maxbytes = EXT4_SB(inode->i_sb)->s_bitmap_maxbytes;
4959 
4960 	if (*len == 0)
4961 		return -EINVAL;
4962 	if (start > maxbytes)
4963 		return -EFBIG;
4964 
4965 	/*
4966 	 * Shrink request scope to what the fs can actually handle.
4967 	 */
4968 	if (*len > maxbytes || (maxbytes - *len) < start)
4969 		*len = maxbytes - start;
4970 	return 0;
4971 }
4972 
ext4_fiemap(struct inode * inode,struct fiemap_extent_info * fieinfo,u64 start,u64 len)4973 int ext4_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
4974 		u64 start, u64 len)
4975 {
4976 	int error = 0;
4977 
4978 	if (fieinfo->fi_flags & FIEMAP_FLAG_CACHE) {
4979 		error = ext4_ext_precache(inode);
4980 		if (error)
4981 			return error;
4982 		fieinfo->fi_flags &= ~FIEMAP_FLAG_CACHE;
4983 	}
4984 
4985 	/*
4986 	 * For bitmap files the maximum size limit could be smaller than
4987 	 * s_maxbytes, so check len here manually instead of just relying on the
4988 	 * generic check.
4989 	 */
4990 	error = ext4_fiemap_check_ranges(inode, start, &len);
4991 	if (error)
4992 		return error;
4993 
4994 	if (fieinfo->fi_flags & FIEMAP_FLAG_XATTR) {
4995 		fieinfo->fi_flags &= ~FIEMAP_FLAG_XATTR;
4996 		return iomap_fiemap(inode, fieinfo, start, len,
4997 				    &ext4_iomap_xattr_ops);
4998 	}
4999 
5000 	return iomap_fiemap(inode, fieinfo, start, len, &ext4_iomap_report_ops);
5001 }
5002 
ext4_get_es_cache(struct inode * inode,struct fiemap_extent_info * fieinfo,__u64 start,__u64 len)5003 int ext4_get_es_cache(struct inode *inode, struct fiemap_extent_info *fieinfo,
5004 		      __u64 start, __u64 len)
5005 {
5006 	ext4_lblk_t start_blk, len_blks;
5007 	__u64 last_blk;
5008 	int error = 0;
5009 
5010 	if (ext4_has_inline_data(inode)) {
5011 		int has_inline;
5012 
5013 		down_read(&EXT4_I(inode)->xattr_sem);
5014 		has_inline = ext4_has_inline_data(inode);
5015 		up_read(&EXT4_I(inode)->xattr_sem);
5016 		if (has_inline)
5017 			return 0;
5018 	}
5019 
5020 	if (fieinfo->fi_flags & FIEMAP_FLAG_CACHE) {
5021 		error = ext4_ext_precache(inode);
5022 		if (error)
5023 			return error;
5024 		fieinfo->fi_flags &= ~FIEMAP_FLAG_CACHE;
5025 	}
5026 
5027 	error = fiemap_prep(inode, fieinfo, start, &len, 0);
5028 	if (error)
5029 		return error;
5030 
5031 	error = ext4_fiemap_check_ranges(inode, start, &len);
5032 	if (error)
5033 		return error;
5034 
5035 	start_blk = start >> inode->i_sb->s_blocksize_bits;
5036 	last_blk = (start + len - 1) >> inode->i_sb->s_blocksize_bits;
5037 	if (last_blk >= EXT_MAX_BLOCKS)
5038 		last_blk = EXT_MAX_BLOCKS-1;
5039 	len_blks = ((ext4_lblk_t) last_blk) - start_blk + 1;
5040 
5041 	/*
5042 	 * Walk the extent tree gathering extent information
5043 	 * and pushing extents back to the user.
5044 	 */
5045 	return ext4_fill_es_cache_info(inode, start_blk, len_blks, fieinfo);
5046 }
5047 
5048 /*
5049  * ext4_ext_shift_path_extents:
5050  * Shift the extents of a path structure lying between path[depth].p_ext
5051  * and EXT_LAST_EXTENT(path[depth].p_hdr), by @shift blocks. @SHIFT tells
5052  * if it is right shift or left shift operation.
5053  */
5054 static int
ext4_ext_shift_path_extents(struct ext4_ext_path * path,ext4_lblk_t shift,struct inode * inode,handle_t * handle,enum SHIFT_DIRECTION SHIFT)5055 ext4_ext_shift_path_extents(struct ext4_ext_path *path, ext4_lblk_t shift,
5056 			    struct inode *inode, handle_t *handle,
5057 			    enum SHIFT_DIRECTION SHIFT)
5058 {
5059 	int depth, err = 0;
5060 	struct ext4_extent *ex_start, *ex_last;
5061 	bool update = false;
5062 	int credits, restart_credits;
5063 	depth = path->p_depth;
5064 
5065 	while (depth >= 0) {
5066 		if (depth == path->p_depth) {
5067 			ex_start = path[depth].p_ext;
5068 			if (!ex_start)
5069 				return -EFSCORRUPTED;
5070 
5071 			ex_last = EXT_LAST_EXTENT(path[depth].p_hdr);
5072 			/* leaf + sb + inode */
5073 			credits = 3;
5074 			if (ex_start == EXT_FIRST_EXTENT(path[depth].p_hdr)) {
5075 				update = true;
5076 				/* extent tree + sb + inode */
5077 				credits = depth + 2;
5078 			}
5079 
5080 			restart_credits = ext4_writepage_trans_blocks(inode);
5081 			err = ext4_datasem_ensure_credits(handle, inode, credits,
5082 					restart_credits, 0);
5083 			if (err) {
5084 				if (err > 0)
5085 					err = -EAGAIN;
5086 				goto out;
5087 			}
5088 
5089 			err = ext4_ext_get_access(handle, inode, path + depth);
5090 			if (err)
5091 				goto out;
5092 
5093 			while (ex_start <= ex_last) {
5094 				if (SHIFT == SHIFT_LEFT) {
5095 					le32_add_cpu(&ex_start->ee_block,
5096 						-shift);
5097 					/* Try to merge to the left. */
5098 					if ((ex_start >
5099 					    EXT_FIRST_EXTENT(path[depth].p_hdr))
5100 					    &&
5101 					    ext4_ext_try_to_merge_right(inode,
5102 					    path, ex_start - 1))
5103 						ex_last--;
5104 					else
5105 						ex_start++;
5106 				} else {
5107 					le32_add_cpu(&ex_last->ee_block, shift);
5108 					ext4_ext_try_to_merge_right(inode, path,
5109 						ex_last);
5110 					ex_last--;
5111 				}
5112 			}
5113 			err = ext4_ext_dirty(handle, inode, path + depth);
5114 			if (err)
5115 				goto out;
5116 
5117 			if (--depth < 0 || !update)
5118 				break;
5119 		}
5120 
5121 		/* Update index too */
5122 		err = ext4_ext_get_access(handle, inode, path + depth);
5123 		if (err)
5124 			goto out;
5125 
5126 		if (SHIFT == SHIFT_LEFT)
5127 			le32_add_cpu(&path[depth].p_idx->ei_block, -shift);
5128 		else
5129 			le32_add_cpu(&path[depth].p_idx->ei_block, shift);
5130 		err = ext4_ext_dirty(handle, inode, path + depth);
5131 		if (err)
5132 			goto out;
5133 
5134 		/* we are done if current index is not a starting index */
5135 		if (path[depth].p_idx != EXT_FIRST_INDEX(path[depth].p_hdr))
5136 			break;
5137 
5138 		depth--;
5139 	}
5140 
5141 out:
5142 	return err;
5143 }
5144 
5145 /*
5146  * ext4_ext_shift_extents:
5147  * All the extents which lies in the range from @start to the last allocated
5148  * block for the @inode are shifted either towards left or right (depending
5149  * upon @SHIFT) by @shift blocks.
5150  * On success, 0 is returned, error otherwise.
5151  */
5152 static int
ext4_ext_shift_extents(struct inode * inode,handle_t * handle,ext4_lblk_t start,ext4_lblk_t shift,enum SHIFT_DIRECTION SHIFT)5153 ext4_ext_shift_extents(struct inode *inode, handle_t *handle,
5154 		       ext4_lblk_t start, ext4_lblk_t shift,
5155 		       enum SHIFT_DIRECTION SHIFT)
5156 {
5157 	struct ext4_ext_path *path;
5158 	int ret = 0, depth;
5159 	struct ext4_extent *extent;
5160 	ext4_lblk_t stop, *iterator, ex_start, ex_end;
5161 	ext4_lblk_t tmp = EXT_MAX_BLOCKS;
5162 
5163 	/* Let path point to the last extent */
5164 	path = ext4_find_extent(inode, EXT_MAX_BLOCKS - 1, NULL,
5165 				EXT4_EX_NOCACHE);
5166 	if (IS_ERR(path))
5167 		return PTR_ERR(path);
5168 
5169 	depth = path->p_depth;
5170 	extent = path[depth].p_ext;
5171 	if (!extent)
5172 		goto out;
5173 
5174 	stop = le32_to_cpu(extent->ee_block);
5175 
5176        /*
5177 	* For left shifts, make sure the hole on the left is big enough to
5178 	* accommodate the shift.  For right shifts, make sure the last extent
5179 	* won't be shifted beyond EXT_MAX_BLOCKS.
5180 	*/
5181 	if (SHIFT == SHIFT_LEFT) {
5182 		path = ext4_find_extent(inode, start - 1, &path,
5183 					EXT4_EX_NOCACHE);
5184 		if (IS_ERR(path))
5185 			return PTR_ERR(path);
5186 		depth = path->p_depth;
5187 		extent =  path[depth].p_ext;
5188 		if (extent) {
5189 			ex_start = le32_to_cpu(extent->ee_block);
5190 			ex_end = le32_to_cpu(extent->ee_block) +
5191 				ext4_ext_get_actual_len(extent);
5192 		} else {
5193 			ex_start = 0;
5194 			ex_end = 0;
5195 		}
5196 
5197 		if ((start == ex_start && shift > ex_start) ||
5198 		    (shift > start - ex_end)) {
5199 			ret = -EINVAL;
5200 			goto out;
5201 		}
5202 	} else {
5203 		if (shift > EXT_MAX_BLOCKS -
5204 		    (stop + ext4_ext_get_actual_len(extent))) {
5205 			ret = -EINVAL;
5206 			goto out;
5207 		}
5208 	}
5209 
5210 	/*
5211 	 * In case of left shift, iterator points to start and it is increased
5212 	 * till we reach stop. In case of right shift, iterator points to stop
5213 	 * and it is decreased till we reach start.
5214 	 */
5215 again:
5216 	ret = 0;
5217 	if (SHIFT == SHIFT_LEFT)
5218 		iterator = &start;
5219 	else
5220 		iterator = &stop;
5221 
5222 	if (tmp != EXT_MAX_BLOCKS)
5223 		*iterator = tmp;
5224 
5225 	/*
5226 	 * Its safe to start updating extents.  Start and stop are unsigned, so
5227 	 * in case of right shift if extent with 0 block is reached, iterator
5228 	 * becomes NULL to indicate the end of the loop.
5229 	 */
5230 	while (iterator && start <= stop) {
5231 		path = ext4_find_extent(inode, *iterator, &path,
5232 					EXT4_EX_NOCACHE);
5233 		if (IS_ERR(path))
5234 			return PTR_ERR(path);
5235 		depth = path->p_depth;
5236 		extent = path[depth].p_ext;
5237 		if (!extent) {
5238 			EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
5239 					 (unsigned long) *iterator);
5240 			return -EFSCORRUPTED;
5241 		}
5242 		if (SHIFT == SHIFT_LEFT && *iterator >
5243 		    le32_to_cpu(extent->ee_block)) {
5244 			/* Hole, move to the next extent */
5245 			if (extent < EXT_LAST_EXTENT(path[depth].p_hdr)) {
5246 				path[depth].p_ext++;
5247 			} else {
5248 				*iterator = ext4_ext_next_allocated_block(path);
5249 				continue;
5250 			}
5251 		}
5252 
5253 		tmp = *iterator;
5254 		if (SHIFT == SHIFT_LEFT) {
5255 			extent = EXT_LAST_EXTENT(path[depth].p_hdr);
5256 			*iterator = le32_to_cpu(extent->ee_block) +
5257 					ext4_ext_get_actual_len(extent);
5258 		} else {
5259 			extent = EXT_FIRST_EXTENT(path[depth].p_hdr);
5260 			if (le32_to_cpu(extent->ee_block) > start)
5261 				*iterator = le32_to_cpu(extent->ee_block) - 1;
5262 			else if (le32_to_cpu(extent->ee_block) == start)
5263 				iterator = NULL;
5264 			else {
5265 				extent = EXT_LAST_EXTENT(path[depth].p_hdr);
5266 				while (le32_to_cpu(extent->ee_block) >= start)
5267 					extent--;
5268 
5269 				if (extent == EXT_LAST_EXTENT(path[depth].p_hdr))
5270 					break;
5271 
5272 				extent++;
5273 				iterator = NULL;
5274 			}
5275 			path[depth].p_ext = extent;
5276 		}
5277 		ret = ext4_ext_shift_path_extents(path, shift, inode,
5278 				handle, SHIFT);
5279 		/* iterator can be NULL which means we should break */
5280 		if (ret == -EAGAIN)
5281 			goto again;
5282 		if (ret)
5283 			break;
5284 	}
5285 out:
5286 	ext4_free_ext_path(path);
5287 	return ret;
5288 }
5289 
5290 /*
5291  * ext4_collapse_range:
5292  * This implements the fallocate's collapse range functionality for ext4
5293  * Returns: 0 and non-zero on error.
5294  */
ext4_collapse_range(struct file * file,loff_t offset,loff_t len)5295 static int ext4_collapse_range(struct file *file, loff_t offset, loff_t len)
5296 {
5297 	struct inode *inode = file_inode(file);
5298 	struct super_block *sb = inode->i_sb;
5299 	struct address_space *mapping = inode->i_mapping;
5300 	ext4_lblk_t punch_start, punch_stop;
5301 	handle_t *handle;
5302 	unsigned int credits;
5303 	loff_t new_size, ioffset;
5304 	int ret;
5305 
5306 	/*
5307 	 * We need to test this early because xfstests assumes that a
5308 	 * collapse range of (0, 1) will return EOPNOTSUPP if the file
5309 	 * system does not support collapse range.
5310 	 */
5311 	if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
5312 		return -EOPNOTSUPP;
5313 
5314 	/* Collapse range works only on fs cluster size aligned regions. */
5315 	if (!IS_ALIGNED(offset | len, EXT4_CLUSTER_SIZE(sb)))
5316 		return -EINVAL;
5317 
5318 	trace_ext4_collapse_range(inode, offset, len);
5319 
5320 	punch_start = offset >> EXT4_BLOCK_SIZE_BITS(sb);
5321 	punch_stop = (offset + len) >> EXT4_BLOCK_SIZE_BITS(sb);
5322 
5323 	inode_lock(inode);
5324 	/*
5325 	 * There is no need to overlap collapse range with EOF, in which case
5326 	 * it is effectively a truncate operation
5327 	 */
5328 	if (offset + len >= inode->i_size) {
5329 		ret = -EINVAL;
5330 		goto out_mutex;
5331 	}
5332 
5333 	/* Currently just for extent based files */
5334 	if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)) {
5335 		ret = -EOPNOTSUPP;
5336 		goto out_mutex;
5337 	}
5338 
5339 	/* Wait for existing dio to complete */
5340 	inode_dio_wait(inode);
5341 
5342 	ret = file_modified(file);
5343 	if (ret)
5344 		goto out_mutex;
5345 
5346 	/*
5347 	 * Prevent page faults from reinstantiating pages we have released from
5348 	 * page cache.
5349 	 */
5350 	filemap_invalidate_lock(mapping);
5351 
5352 	ret = ext4_break_layouts(inode);
5353 	if (ret)
5354 		goto out_mmap;
5355 
5356 	/*
5357 	 * Need to round down offset to be aligned with page size boundary
5358 	 * for page size > block size.
5359 	 */
5360 	ioffset = round_down(offset, PAGE_SIZE);
5361 	/*
5362 	 * Write tail of the last page before removed range since it will get
5363 	 * removed from the page cache below.
5364 	 */
5365 	ret = filemap_write_and_wait_range(mapping, ioffset, offset);
5366 	if (ret)
5367 		goto out_mmap;
5368 	/*
5369 	 * Write data that will be shifted to preserve them when discarding
5370 	 * page cache below. We are also protected from pages becoming dirty
5371 	 * by i_rwsem and invalidate_lock.
5372 	 */
5373 	ret = filemap_write_and_wait_range(mapping, offset + len,
5374 					   LLONG_MAX);
5375 	if (ret)
5376 		goto out_mmap;
5377 	truncate_pagecache(inode, ioffset);
5378 
5379 	credits = ext4_writepage_trans_blocks(inode);
5380 	handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, credits);
5381 	if (IS_ERR(handle)) {
5382 		ret = PTR_ERR(handle);
5383 		goto out_mmap;
5384 	}
5385 	ext4_fc_mark_ineligible(sb, EXT4_FC_REASON_FALLOC_RANGE, handle);
5386 
5387 	down_write(&EXT4_I(inode)->i_data_sem);
5388 	ext4_discard_preallocations(inode, 0);
5389 	ext4_es_remove_extent(inode, punch_start, EXT_MAX_BLOCKS - punch_start);
5390 
5391 	ret = ext4_ext_remove_space(inode, punch_start, punch_stop - 1);
5392 	if (ret) {
5393 		up_write(&EXT4_I(inode)->i_data_sem);
5394 		goto out_stop;
5395 	}
5396 	ext4_discard_preallocations(inode, 0);
5397 
5398 	ret = ext4_ext_shift_extents(inode, handle, punch_stop,
5399 				     punch_stop - punch_start, SHIFT_LEFT);
5400 	if (ret) {
5401 		up_write(&EXT4_I(inode)->i_data_sem);
5402 		goto out_stop;
5403 	}
5404 
5405 	new_size = inode->i_size - len;
5406 	i_size_write(inode, new_size);
5407 	EXT4_I(inode)->i_disksize = new_size;
5408 
5409 	up_write(&EXT4_I(inode)->i_data_sem);
5410 	if (IS_SYNC(inode))
5411 		ext4_handle_sync(handle);
5412 	inode->i_mtime = inode_set_ctime_current(inode);
5413 	ret = ext4_mark_inode_dirty(handle, inode);
5414 	ext4_update_inode_fsync_trans(handle, inode, 1);
5415 
5416 out_stop:
5417 	ext4_journal_stop(handle);
5418 out_mmap:
5419 	filemap_invalidate_unlock(mapping);
5420 out_mutex:
5421 	inode_unlock(inode);
5422 	return ret;
5423 }
5424 
5425 /*
5426  * ext4_insert_range:
5427  * This function implements the FALLOC_FL_INSERT_RANGE flag of fallocate.
5428  * The data blocks starting from @offset to the EOF are shifted by @len
5429  * towards right to create a hole in the @inode. Inode size is increased
5430  * by len bytes.
5431  * Returns 0 on success, error otherwise.
5432  */
ext4_insert_range(struct file * file,loff_t offset,loff_t len)5433 static int ext4_insert_range(struct file *file, loff_t offset, loff_t len)
5434 {
5435 	struct inode *inode = file_inode(file);
5436 	struct super_block *sb = inode->i_sb;
5437 	struct address_space *mapping = inode->i_mapping;
5438 	handle_t *handle;
5439 	struct ext4_ext_path *path;
5440 	struct ext4_extent *extent;
5441 	ext4_lblk_t offset_lblk, len_lblk, ee_start_lblk = 0;
5442 	unsigned int credits, ee_len;
5443 	int ret = 0, depth, split_flag = 0;
5444 	loff_t ioffset;
5445 
5446 	/*
5447 	 * We need to test this early because xfstests assumes that an
5448 	 * insert range of (0, 1) will return EOPNOTSUPP if the file
5449 	 * system does not support insert range.
5450 	 */
5451 	if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
5452 		return -EOPNOTSUPP;
5453 
5454 	/* Insert range works only on fs cluster size aligned regions. */
5455 	if (!IS_ALIGNED(offset | len, EXT4_CLUSTER_SIZE(sb)))
5456 		return -EINVAL;
5457 
5458 	trace_ext4_insert_range(inode, offset, len);
5459 
5460 	offset_lblk = offset >> EXT4_BLOCK_SIZE_BITS(sb);
5461 	len_lblk = len >> EXT4_BLOCK_SIZE_BITS(sb);
5462 
5463 	inode_lock(inode);
5464 	/* Currently just for extent based files */
5465 	if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)) {
5466 		ret = -EOPNOTSUPP;
5467 		goto out_mutex;
5468 	}
5469 
5470 	/* Check whether the maximum file size would be exceeded */
5471 	if (len > inode->i_sb->s_maxbytes - inode->i_size) {
5472 		ret = -EFBIG;
5473 		goto out_mutex;
5474 	}
5475 
5476 	/* Offset must be less than i_size */
5477 	if (offset >= inode->i_size) {
5478 		ret = -EINVAL;
5479 		goto out_mutex;
5480 	}
5481 
5482 	/* Wait for existing dio to complete */
5483 	inode_dio_wait(inode);
5484 
5485 	ret = file_modified(file);
5486 	if (ret)
5487 		goto out_mutex;
5488 
5489 	/*
5490 	 * Prevent page faults from reinstantiating pages we have released from
5491 	 * page cache.
5492 	 */
5493 	filemap_invalidate_lock(mapping);
5494 
5495 	ret = ext4_break_layouts(inode);
5496 	if (ret)
5497 		goto out_mmap;
5498 
5499 	/*
5500 	 * Need to round down to align start offset to page size boundary
5501 	 * for page size > block size.
5502 	 */
5503 	ioffset = round_down(offset, PAGE_SIZE);
5504 	/* Write out all dirty pages */
5505 	ret = filemap_write_and_wait_range(inode->i_mapping, ioffset,
5506 			LLONG_MAX);
5507 	if (ret)
5508 		goto out_mmap;
5509 	truncate_pagecache(inode, ioffset);
5510 
5511 	credits = ext4_writepage_trans_blocks(inode);
5512 	handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, credits);
5513 	if (IS_ERR(handle)) {
5514 		ret = PTR_ERR(handle);
5515 		goto out_mmap;
5516 	}
5517 	ext4_fc_mark_ineligible(sb, EXT4_FC_REASON_FALLOC_RANGE, handle);
5518 
5519 	/* Expand file to avoid data loss if there is error while shifting */
5520 	inode->i_size += len;
5521 	EXT4_I(inode)->i_disksize += len;
5522 	inode->i_mtime = inode_set_ctime_current(inode);
5523 	ret = ext4_mark_inode_dirty(handle, inode);
5524 	if (ret)
5525 		goto out_stop;
5526 
5527 	down_write(&EXT4_I(inode)->i_data_sem);
5528 	ext4_discard_preallocations(inode, 0);
5529 
5530 	path = ext4_find_extent(inode, offset_lblk, NULL, 0);
5531 	if (IS_ERR(path)) {
5532 		up_write(&EXT4_I(inode)->i_data_sem);
5533 		goto out_stop;
5534 	}
5535 
5536 	depth = ext_depth(inode);
5537 	extent = path[depth].p_ext;
5538 	if (extent) {
5539 		ee_start_lblk = le32_to_cpu(extent->ee_block);
5540 		ee_len = ext4_ext_get_actual_len(extent);
5541 
5542 		/*
5543 		 * If offset_lblk is not the starting block of extent, split
5544 		 * the extent @offset_lblk
5545 		 */
5546 		if ((offset_lblk > ee_start_lblk) &&
5547 				(offset_lblk < (ee_start_lblk + ee_len))) {
5548 			if (ext4_ext_is_unwritten(extent))
5549 				split_flag = EXT4_EXT_MARK_UNWRIT1 |
5550 					EXT4_EXT_MARK_UNWRIT2;
5551 			ret = ext4_split_extent_at(handle, inode, &path,
5552 					offset_lblk, split_flag,
5553 					EXT4_EX_NOCACHE |
5554 					EXT4_GET_BLOCKS_PRE_IO |
5555 					EXT4_GET_BLOCKS_METADATA_NOFAIL);
5556 		}
5557 
5558 		ext4_free_ext_path(path);
5559 		if (ret < 0) {
5560 			up_write(&EXT4_I(inode)->i_data_sem);
5561 			goto out_stop;
5562 		}
5563 	} else {
5564 		ext4_free_ext_path(path);
5565 	}
5566 
5567 	ext4_es_remove_extent(inode, offset_lblk, EXT_MAX_BLOCKS - offset_lblk);
5568 
5569 	/*
5570 	 * if offset_lblk lies in a hole which is at start of file, use
5571 	 * ee_start_lblk to shift extents
5572 	 */
5573 	ret = ext4_ext_shift_extents(inode, handle,
5574 		max(ee_start_lblk, offset_lblk), len_lblk, SHIFT_RIGHT);
5575 
5576 	up_write(&EXT4_I(inode)->i_data_sem);
5577 	if (IS_SYNC(inode))
5578 		ext4_handle_sync(handle);
5579 	if (ret >= 0)
5580 		ext4_update_inode_fsync_trans(handle, inode, 1);
5581 
5582 out_stop:
5583 	ext4_journal_stop(handle);
5584 out_mmap:
5585 	filemap_invalidate_unlock(mapping);
5586 out_mutex:
5587 	inode_unlock(inode);
5588 	return ret;
5589 }
5590 
5591 /**
5592  * ext4_swap_extents() - Swap extents between two inodes
5593  * @handle: handle for this transaction
5594  * @inode1:	First inode
5595  * @inode2:	Second inode
5596  * @lblk1:	Start block for first inode
5597  * @lblk2:	Start block for second inode
5598  * @count:	Number of blocks to swap
5599  * @unwritten: Mark second inode's extents as unwritten after swap
5600  * @erp:	Pointer to save error value
5601  *
5602  * This helper routine does exactly what is promise "swap extents". All other
5603  * stuff such as page-cache locking consistency, bh mapping consistency or
5604  * extent's data copying must be performed by caller.
5605  * Locking:
5606  *		i_rwsem is held for both inodes
5607  * 		i_data_sem is locked for write for both inodes
5608  * Assumptions:
5609  *		All pages from requested range are locked for both inodes
5610  */
5611 int
ext4_swap_extents(handle_t * handle,struct inode * inode1,struct inode * inode2,ext4_lblk_t lblk1,ext4_lblk_t lblk2,ext4_lblk_t count,int unwritten,int * erp)5612 ext4_swap_extents(handle_t *handle, struct inode *inode1,
5613 		  struct inode *inode2, ext4_lblk_t lblk1, ext4_lblk_t lblk2,
5614 		  ext4_lblk_t count, int unwritten, int *erp)
5615 {
5616 	struct ext4_ext_path *path1 = NULL;
5617 	struct ext4_ext_path *path2 = NULL;
5618 	int replaced_count = 0;
5619 
5620 	BUG_ON(!rwsem_is_locked(&EXT4_I(inode1)->i_data_sem));
5621 	BUG_ON(!rwsem_is_locked(&EXT4_I(inode2)->i_data_sem));
5622 	BUG_ON(!inode_is_locked(inode1));
5623 	BUG_ON(!inode_is_locked(inode2));
5624 
5625 	ext4_es_remove_extent(inode1, lblk1, count);
5626 	ext4_es_remove_extent(inode2, lblk2, count);
5627 
5628 	while (count) {
5629 		struct ext4_extent *ex1, *ex2, tmp_ex;
5630 		ext4_lblk_t e1_blk, e2_blk;
5631 		int e1_len, e2_len, len;
5632 		int split = 0;
5633 
5634 		path1 = ext4_find_extent(inode1, lblk1, NULL, EXT4_EX_NOCACHE);
5635 		if (IS_ERR(path1)) {
5636 			*erp = PTR_ERR(path1);
5637 			path1 = NULL;
5638 		finish:
5639 			count = 0;
5640 			goto repeat;
5641 		}
5642 		path2 = ext4_find_extent(inode2, lblk2, NULL, EXT4_EX_NOCACHE);
5643 		if (IS_ERR(path2)) {
5644 			*erp = PTR_ERR(path2);
5645 			path2 = NULL;
5646 			goto finish;
5647 		}
5648 		ex1 = path1[path1->p_depth].p_ext;
5649 		ex2 = path2[path2->p_depth].p_ext;
5650 		/* Do we have something to swap ? */
5651 		if (unlikely(!ex2 || !ex1))
5652 			goto finish;
5653 
5654 		e1_blk = le32_to_cpu(ex1->ee_block);
5655 		e2_blk = le32_to_cpu(ex2->ee_block);
5656 		e1_len = ext4_ext_get_actual_len(ex1);
5657 		e2_len = ext4_ext_get_actual_len(ex2);
5658 
5659 		/* Hole handling */
5660 		if (!in_range(lblk1, e1_blk, e1_len) ||
5661 		    !in_range(lblk2, e2_blk, e2_len)) {
5662 			ext4_lblk_t next1, next2;
5663 
5664 			/* if hole after extent, then go to next extent */
5665 			next1 = ext4_ext_next_allocated_block(path1);
5666 			next2 = ext4_ext_next_allocated_block(path2);
5667 			/* If hole before extent, then shift to that extent */
5668 			if (e1_blk > lblk1)
5669 				next1 = e1_blk;
5670 			if (e2_blk > lblk2)
5671 				next2 = e2_blk;
5672 			/* Do we have something to swap */
5673 			if (next1 == EXT_MAX_BLOCKS || next2 == EXT_MAX_BLOCKS)
5674 				goto finish;
5675 			/* Move to the rightest boundary */
5676 			len = next1 - lblk1;
5677 			if (len < next2 - lblk2)
5678 				len = next2 - lblk2;
5679 			if (len > count)
5680 				len = count;
5681 			lblk1 += len;
5682 			lblk2 += len;
5683 			count -= len;
5684 			goto repeat;
5685 		}
5686 
5687 		/* Prepare left boundary */
5688 		if (e1_blk < lblk1) {
5689 			split = 1;
5690 			*erp = ext4_force_split_extent_at(handle, inode1,
5691 						&path1, lblk1, 0);
5692 			if (unlikely(*erp))
5693 				goto finish;
5694 		}
5695 		if (e2_blk < lblk2) {
5696 			split = 1;
5697 			*erp = ext4_force_split_extent_at(handle, inode2,
5698 						&path2,  lblk2, 0);
5699 			if (unlikely(*erp))
5700 				goto finish;
5701 		}
5702 		/* ext4_split_extent_at() may result in leaf extent split,
5703 		 * path must to be revalidated. */
5704 		if (split)
5705 			goto repeat;
5706 
5707 		/* Prepare right boundary */
5708 		len = count;
5709 		if (len > e1_blk + e1_len - lblk1)
5710 			len = e1_blk + e1_len - lblk1;
5711 		if (len > e2_blk + e2_len - lblk2)
5712 			len = e2_blk + e2_len - lblk2;
5713 
5714 		if (len != e1_len) {
5715 			split = 1;
5716 			*erp = ext4_force_split_extent_at(handle, inode1,
5717 						&path1, lblk1 + len, 0);
5718 			if (unlikely(*erp))
5719 				goto finish;
5720 		}
5721 		if (len != e2_len) {
5722 			split = 1;
5723 			*erp = ext4_force_split_extent_at(handle, inode2,
5724 						&path2, lblk2 + len, 0);
5725 			if (*erp)
5726 				goto finish;
5727 		}
5728 		/* ext4_split_extent_at() may result in leaf extent split,
5729 		 * path must to be revalidated. */
5730 		if (split)
5731 			goto repeat;
5732 
5733 		BUG_ON(e2_len != e1_len);
5734 		*erp = ext4_ext_get_access(handle, inode1, path1 + path1->p_depth);
5735 		if (unlikely(*erp))
5736 			goto finish;
5737 		*erp = ext4_ext_get_access(handle, inode2, path2 + path2->p_depth);
5738 		if (unlikely(*erp))
5739 			goto finish;
5740 
5741 		/* Both extents are fully inside boundaries. Swap it now */
5742 		tmp_ex = *ex1;
5743 		ext4_ext_store_pblock(ex1, ext4_ext_pblock(ex2));
5744 		ext4_ext_store_pblock(ex2, ext4_ext_pblock(&tmp_ex));
5745 		ex1->ee_len = cpu_to_le16(e2_len);
5746 		ex2->ee_len = cpu_to_le16(e1_len);
5747 		if (unwritten)
5748 			ext4_ext_mark_unwritten(ex2);
5749 		if (ext4_ext_is_unwritten(&tmp_ex))
5750 			ext4_ext_mark_unwritten(ex1);
5751 
5752 		ext4_ext_try_to_merge(handle, inode2, path2, ex2);
5753 		ext4_ext_try_to_merge(handle, inode1, path1, ex1);
5754 		*erp = ext4_ext_dirty(handle, inode2, path2 +
5755 				      path2->p_depth);
5756 		if (unlikely(*erp))
5757 			goto finish;
5758 		*erp = ext4_ext_dirty(handle, inode1, path1 +
5759 				      path1->p_depth);
5760 		/*
5761 		 * Looks scarry ah..? second inode already points to new blocks,
5762 		 * and it was successfully dirtied. But luckily error may happen
5763 		 * only due to journal error, so full transaction will be
5764 		 * aborted anyway.
5765 		 */
5766 		if (unlikely(*erp))
5767 			goto finish;
5768 		lblk1 += len;
5769 		lblk2 += len;
5770 		replaced_count += len;
5771 		count -= len;
5772 
5773 	repeat:
5774 		ext4_free_ext_path(path1);
5775 		ext4_free_ext_path(path2);
5776 		path1 = path2 = NULL;
5777 	}
5778 	return replaced_count;
5779 }
5780 
5781 /*
5782  * ext4_clu_mapped - determine whether any block in a logical cluster has
5783  *                   been mapped to a physical cluster
5784  *
5785  * @inode - file containing the logical cluster
5786  * @lclu - logical cluster of interest
5787  *
5788  * Returns 1 if any block in the logical cluster is mapped, signifying
5789  * that a physical cluster has been allocated for it.  Otherwise,
5790  * returns 0.  Can also return negative error codes.  Derived from
5791  * ext4_ext_map_blocks().
5792  */
ext4_clu_mapped(struct inode * inode,ext4_lblk_t lclu)5793 int ext4_clu_mapped(struct inode *inode, ext4_lblk_t lclu)
5794 {
5795 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
5796 	struct ext4_ext_path *path;
5797 	int depth, mapped = 0, err = 0;
5798 	struct ext4_extent *extent;
5799 	ext4_lblk_t first_lblk, first_lclu, last_lclu;
5800 
5801 	/*
5802 	 * if data can be stored inline, the logical cluster isn't
5803 	 * mapped - no physical clusters have been allocated, and the
5804 	 * file has no extents
5805 	 */
5806 	if (ext4_test_inode_state(inode, EXT4_STATE_MAY_INLINE_DATA) ||
5807 	    ext4_has_inline_data(inode))
5808 		return 0;
5809 
5810 	/* search for the extent closest to the first block in the cluster */
5811 	path = ext4_find_extent(inode, EXT4_C2B(sbi, lclu), NULL, 0);
5812 	if (IS_ERR(path)) {
5813 		err = PTR_ERR(path);
5814 		path = NULL;
5815 		goto out;
5816 	}
5817 
5818 	depth = ext_depth(inode);
5819 
5820 	/*
5821 	 * A consistent leaf must not be empty.  This situation is possible,
5822 	 * though, _during_ tree modification, and it's why an assert can't
5823 	 * be put in ext4_find_extent().
5824 	 */
5825 	if (unlikely(path[depth].p_ext == NULL && depth != 0)) {
5826 		EXT4_ERROR_INODE(inode,
5827 		    "bad extent address - lblock: %lu, depth: %d, pblock: %lld",
5828 				 (unsigned long) EXT4_C2B(sbi, lclu),
5829 				 depth, path[depth].p_block);
5830 		err = -EFSCORRUPTED;
5831 		goto out;
5832 	}
5833 
5834 	extent = path[depth].p_ext;
5835 
5836 	/* can't be mapped if the extent tree is empty */
5837 	if (extent == NULL)
5838 		goto out;
5839 
5840 	first_lblk = le32_to_cpu(extent->ee_block);
5841 	first_lclu = EXT4_B2C(sbi, first_lblk);
5842 
5843 	/*
5844 	 * Three possible outcomes at this point - found extent spanning
5845 	 * the target cluster, to the left of the target cluster, or to the
5846 	 * right of the target cluster.  The first two cases are handled here.
5847 	 * The last case indicates the target cluster is not mapped.
5848 	 */
5849 	if (lclu >= first_lclu) {
5850 		last_lclu = EXT4_B2C(sbi, first_lblk +
5851 				     ext4_ext_get_actual_len(extent) - 1);
5852 		if (lclu <= last_lclu) {
5853 			mapped = 1;
5854 		} else {
5855 			first_lblk = ext4_ext_next_allocated_block(path);
5856 			first_lclu = EXT4_B2C(sbi, first_lblk);
5857 			if (lclu == first_lclu)
5858 				mapped = 1;
5859 		}
5860 	}
5861 
5862 out:
5863 	ext4_free_ext_path(path);
5864 
5865 	return err ? err : mapped;
5866 }
5867 
5868 /*
5869  * Updates physical block address and unwritten status of extent
5870  * starting at lblk start and of len. If such an extent doesn't exist,
5871  * this function splits the extent tree appropriately to create an
5872  * extent like this.  This function is called in the fast commit
5873  * replay path.  Returns 0 on success and error on failure.
5874  */
ext4_ext_replay_update_ex(struct inode * inode,ext4_lblk_t start,int len,int unwritten,ext4_fsblk_t pblk)5875 int ext4_ext_replay_update_ex(struct inode *inode, ext4_lblk_t start,
5876 			      int len, int unwritten, ext4_fsblk_t pblk)
5877 {
5878 	struct ext4_ext_path *path = NULL, *ppath;
5879 	struct ext4_extent *ex;
5880 	int ret;
5881 
5882 	path = ext4_find_extent(inode, start, NULL, 0);
5883 	if (IS_ERR(path))
5884 		return PTR_ERR(path);
5885 	ex = path[path->p_depth].p_ext;
5886 	if (!ex) {
5887 		ret = -EFSCORRUPTED;
5888 		goto out;
5889 	}
5890 
5891 	if (le32_to_cpu(ex->ee_block) != start ||
5892 		ext4_ext_get_actual_len(ex) != len) {
5893 		/* We need to split this extent to match our extent first */
5894 		ppath = path;
5895 		down_write(&EXT4_I(inode)->i_data_sem);
5896 		ret = ext4_force_split_extent_at(NULL, inode, &ppath, start, 1);
5897 		up_write(&EXT4_I(inode)->i_data_sem);
5898 		if (ret)
5899 			goto out;
5900 		kfree(path);
5901 		path = ext4_find_extent(inode, start, NULL, 0);
5902 		if (IS_ERR(path))
5903 			return -1;
5904 		ppath = path;
5905 		ex = path[path->p_depth].p_ext;
5906 		WARN_ON(le32_to_cpu(ex->ee_block) != start);
5907 		if (ext4_ext_get_actual_len(ex) != len) {
5908 			down_write(&EXT4_I(inode)->i_data_sem);
5909 			ret = ext4_force_split_extent_at(NULL, inode, &ppath,
5910 							 start + len, 1);
5911 			up_write(&EXT4_I(inode)->i_data_sem);
5912 			if (ret)
5913 				goto out;
5914 			kfree(path);
5915 			path = ext4_find_extent(inode, start, NULL, 0);
5916 			if (IS_ERR(path))
5917 				return -EINVAL;
5918 			ex = path[path->p_depth].p_ext;
5919 		}
5920 	}
5921 	if (unwritten)
5922 		ext4_ext_mark_unwritten(ex);
5923 	else
5924 		ext4_ext_mark_initialized(ex);
5925 	ext4_ext_store_pblock(ex, pblk);
5926 	down_write(&EXT4_I(inode)->i_data_sem);
5927 	ret = ext4_ext_dirty(NULL, inode, &path[path->p_depth]);
5928 	up_write(&EXT4_I(inode)->i_data_sem);
5929 out:
5930 	ext4_free_ext_path(path);
5931 	ext4_mark_inode_dirty(NULL, inode);
5932 	return ret;
5933 }
5934 
5935 /* Try to shrink the extent tree */
ext4_ext_replay_shrink_inode(struct inode * inode,ext4_lblk_t end)5936 void ext4_ext_replay_shrink_inode(struct inode *inode, ext4_lblk_t end)
5937 {
5938 	struct ext4_ext_path *path = NULL;
5939 	struct ext4_extent *ex;
5940 	ext4_lblk_t old_cur, cur = 0;
5941 
5942 	while (cur < end) {
5943 		path = ext4_find_extent(inode, cur, NULL, 0);
5944 		if (IS_ERR(path))
5945 			return;
5946 		ex = path[path->p_depth].p_ext;
5947 		if (!ex) {
5948 			ext4_free_ext_path(path);
5949 			ext4_mark_inode_dirty(NULL, inode);
5950 			return;
5951 		}
5952 		old_cur = cur;
5953 		cur = le32_to_cpu(ex->ee_block) + ext4_ext_get_actual_len(ex);
5954 		if (cur <= old_cur)
5955 			cur = old_cur + 1;
5956 		ext4_ext_try_to_merge(NULL, inode, path, ex);
5957 		down_write(&EXT4_I(inode)->i_data_sem);
5958 		ext4_ext_dirty(NULL, inode, &path[path->p_depth]);
5959 		up_write(&EXT4_I(inode)->i_data_sem);
5960 		ext4_mark_inode_dirty(NULL, inode);
5961 		ext4_free_ext_path(path);
5962 	}
5963 }
5964 
5965 /* Check if *cur is a hole and if it is, skip it */
skip_hole(struct inode * inode,ext4_lblk_t * cur)5966 static int skip_hole(struct inode *inode, ext4_lblk_t *cur)
5967 {
5968 	int ret;
5969 	struct ext4_map_blocks map;
5970 
5971 	map.m_lblk = *cur;
5972 	map.m_len = ((inode->i_size) >> inode->i_sb->s_blocksize_bits) - *cur;
5973 
5974 	ret = ext4_map_blocks(NULL, inode, &map, 0);
5975 	if (ret < 0)
5976 		return ret;
5977 	if (ret != 0)
5978 		return 0;
5979 	*cur = *cur + map.m_len;
5980 	return 0;
5981 }
5982 
5983 /* Count number of blocks used by this inode and update i_blocks */
ext4_ext_replay_set_iblocks(struct inode * inode)5984 int ext4_ext_replay_set_iblocks(struct inode *inode)
5985 {
5986 	struct ext4_ext_path *path = NULL, *path2 = NULL;
5987 	struct ext4_extent *ex;
5988 	ext4_lblk_t cur = 0, end;
5989 	int numblks = 0, i, ret = 0;
5990 	ext4_fsblk_t cmp1, cmp2;
5991 	struct ext4_map_blocks map;
5992 
5993 	/* Determin the size of the file first */
5994 	path = ext4_find_extent(inode, EXT_MAX_BLOCKS - 1, NULL,
5995 					EXT4_EX_NOCACHE);
5996 	if (IS_ERR(path))
5997 		return PTR_ERR(path);
5998 	ex = path[path->p_depth].p_ext;
5999 	if (!ex) {
6000 		ext4_free_ext_path(path);
6001 		goto out;
6002 	}
6003 	end = le32_to_cpu(ex->ee_block) + ext4_ext_get_actual_len(ex);
6004 	ext4_free_ext_path(path);
6005 
6006 	/* Count the number of data blocks */
6007 	cur = 0;
6008 	while (cur < end) {
6009 		map.m_lblk = cur;
6010 		map.m_len = end - cur;
6011 		ret = ext4_map_blocks(NULL, inode, &map, 0);
6012 		if (ret < 0)
6013 			break;
6014 		if (ret > 0)
6015 			numblks += ret;
6016 		cur = cur + map.m_len;
6017 	}
6018 
6019 	/*
6020 	 * Count the number of extent tree blocks. We do it by looking up
6021 	 * two successive extents and determining the difference between
6022 	 * their paths. When path is different for 2 successive extents
6023 	 * we compare the blocks in the path at each level and increment
6024 	 * iblocks by total number of differences found.
6025 	 */
6026 	cur = 0;
6027 	ret = skip_hole(inode, &cur);
6028 	if (ret < 0)
6029 		goto out;
6030 	path = ext4_find_extent(inode, cur, NULL, 0);
6031 	if (IS_ERR(path))
6032 		goto out;
6033 	numblks += path->p_depth;
6034 	ext4_free_ext_path(path);
6035 	while (cur < end) {
6036 		path = ext4_find_extent(inode, cur, NULL, 0);
6037 		if (IS_ERR(path))
6038 			break;
6039 		ex = path[path->p_depth].p_ext;
6040 		if (!ex) {
6041 			ext4_free_ext_path(path);
6042 			return 0;
6043 		}
6044 		cur = max(cur + 1, le32_to_cpu(ex->ee_block) +
6045 					ext4_ext_get_actual_len(ex));
6046 		ret = skip_hole(inode, &cur);
6047 		if (ret < 0) {
6048 			ext4_free_ext_path(path);
6049 			break;
6050 		}
6051 		path2 = ext4_find_extent(inode, cur, NULL, 0);
6052 		if (IS_ERR(path2)) {
6053 			ext4_free_ext_path(path);
6054 			break;
6055 		}
6056 		for (i = 0; i <= max(path->p_depth, path2->p_depth); i++) {
6057 			cmp1 = cmp2 = 0;
6058 			if (i <= path->p_depth)
6059 				cmp1 = path[i].p_bh ?
6060 					path[i].p_bh->b_blocknr : 0;
6061 			if (i <= path2->p_depth)
6062 				cmp2 = path2[i].p_bh ?
6063 					path2[i].p_bh->b_blocknr : 0;
6064 			if (cmp1 != cmp2 && cmp2 != 0)
6065 				numblks++;
6066 		}
6067 		ext4_free_ext_path(path);
6068 		ext4_free_ext_path(path2);
6069 	}
6070 
6071 out:
6072 	inode->i_blocks = numblks << (inode->i_sb->s_blocksize_bits - 9);
6073 	ext4_mark_inode_dirty(NULL, inode);
6074 	return 0;
6075 }
6076 
ext4_ext_clear_bb(struct inode * inode)6077 int ext4_ext_clear_bb(struct inode *inode)
6078 {
6079 	struct ext4_ext_path *path = NULL;
6080 	struct ext4_extent *ex;
6081 	ext4_lblk_t cur = 0, end;
6082 	int j, ret = 0;
6083 	struct ext4_map_blocks map;
6084 
6085 	if (ext4_test_inode_flag(inode, EXT4_INODE_INLINE_DATA))
6086 		return 0;
6087 
6088 	/* Determin the size of the file first */
6089 	path = ext4_find_extent(inode, EXT_MAX_BLOCKS - 1, NULL,
6090 					EXT4_EX_NOCACHE);
6091 	if (IS_ERR(path))
6092 		return PTR_ERR(path);
6093 	ex = path[path->p_depth].p_ext;
6094 	if (!ex) {
6095 		ext4_free_ext_path(path);
6096 		return 0;
6097 	}
6098 	end = le32_to_cpu(ex->ee_block) + ext4_ext_get_actual_len(ex);
6099 	ext4_free_ext_path(path);
6100 
6101 	cur = 0;
6102 	while (cur < end) {
6103 		map.m_lblk = cur;
6104 		map.m_len = end - cur;
6105 		ret = ext4_map_blocks(NULL, inode, &map, 0);
6106 		if (ret < 0)
6107 			break;
6108 		if (ret > 0) {
6109 			path = ext4_find_extent(inode, map.m_lblk, NULL, 0);
6110 			if (!IS_ERR_OR_NULL(path)) {
6111 				for (j = 0; j < path->p_depth; j++) {
6112 
6113 					ext4_mb_mark_bb(inode->i_sb,
6114 							path[j].p_block, 1, 0);
6115 					ext4_fc_record_regions(inode->i_sb, inode->i_ino,
6116 							0, path[j].p_block, 1, 1);
6117 				}
6118 				ext4_free_ext_path(path);
6119 			}
6120 			ext4_mb_mark_bb(inode->i_sb, map.m_pblk, map.m_len, 0);
6121 			ext4_fc_record_regions(inode->i_sb, inode->i_ino,
6122 					map.m_lblk, map.m_pblk, map.m_len, 1);
6123 		}
6124 		cur = cur + map.m_len;
6125 	}
6126 
6127 	return 0;
6128 }
6129