extents.c 161.8 KB
Newer Older
1
// SPDX-License-Identifier: GPL-2.0
A
Alex Tomas 已提交
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
/*
 * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
 * Written by Alex Tomas <alex@clusterfs.com>
 *
 * Architecture independence:
 *   Copyright (c) 2005, Bull S.A.
 *   Written by Pierre Peiffer <pierre.peiffer@bull.net>
 */

/*
 * Extents support for EXT4
 *
 * TODO:
 *   - ext4*_error() should be used in some situations
 *   - analyze all BUG()/BUG_ON(), use -EIO where appropriate
 *   - smart tree reduction
 */

#include <linux/fs.h>
#include <linux/time.h>
22
#include <linux/jbd2.h>
A
Alex Tomas 已提交
23 24 25 26 27
#include <linux/highuid.h>
#include <linux/pagemap.h>
#include <linux/quotaops.h>
#include <linux/string.h>
#include <linux/slab.h>
28
#include <linux/uaccess.h>
29
#include <linux/fiemap.h>
30
#include <linux/backing-dev.h>
31
#include "ext4_jbd2.h"
32
#include "ext4_extents.h"
33
#include "xattr.h"
A
Alex Tomas 已提交
34

35 36
#include <trace/events/ext4.h>

37 38 39 40 41
/*
 * used by extent splitting.
 */
#define EXT4_EXT_MAY_ZEROOUT	0x1  /* safe to zeroout if split fails \
					due to ENOSPC */
42 43
#define EXT4_EXT_MARK_UNWRIT1	0x2  /* mark first half unwritten */
#define EXT4_EXT_MARK_UNWRIT2	0x4  /* mark second half unwritten */
44

45 46 47
#define EXT4_EXT_DATA_VALID1	0x8  /* first half contains valid data */
#define EXT4_EXT_DATA_VALID2	0x10 /* second half contains valid data */

48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
static __le32 ext4_extent_block_csum(struct inode *inode,
				     struct ext4_extent_header *eh)
{
	struct ext4_inode_info *ei = EXT4_I(inode);
	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
	__u32 csum;

	csum = ext4_chksum(sbi, ei->i_csum_seed, (__u8 *)eh,
			   EXT4_EXTENT_TAIL_OFFSET(eh));
	return cpu_to_le32(csum);
}

static int ext4_extent_block_csum_verify(struct inode *inode,
					 struct ext4_extent_header *eh)
{
	struct ext4_extent_tail *et;

65
	if (!ext4_has_metadata_csum(inode->i_sb))
66 67 68 69 70 71 72 73 74 75 76 77 78
		return 1;

	et = find_ext4_extent_tail(eh);
	if (et->et_checksum != ext4_extent_block_csum(inode, eh))
		return 0;
	return 1;
}

static void ext4_extent_block_csum_set(struct inode *inode,
				       struct ext4_extent_header *eh)
{
	struct ext4_extent_tail *et;

79
	if (!ext4_has_metadata_csum(inode->i_sb))
80 81 82 83 84 85
		return;

	et = find_ext4_extent_tail(eh);
	et->et_checksum = ext4_extent_block_csum(inode, eh);
}

A
Allison Henderson 已提交
86 87
static int ext4_split_extent(handle_t *handle,
				struct inode *inode,
88
				struct ext4_ext_path **ppath,
A
Allison Henderson 已提交
89 90 91 92
				struct ext4_map_blocks *map,
				int split_flag,
				int flags);

93 94
static int ext4_split_extent_at(handle_t *handle,
			     struct inode *inode,
95
			     struct ext4_ext_path **ppath,
96 97 98 99
			     ext4_lblk_t split,
			     int split_flag,
			     int flags);

100
static int ext4_find_delayed_extent(struct inode *inode,
Z
Zheng Liu 已提交
101
				    struct extent_status *newes);
102

103 104 105
static int ext4_ext_truncate_extend_restart(handle_t *handle,
					    struct inode *inode,
					    int needed)
A
Alex Tomas 已提交
106 107 108
{
	int err;

109 110
	if (!ext4_handle_valid(handle))
		return 0;
111
	if (handle->h_buffer_credits >= needed)
112
		return 0;
113 114 115 116 117 118
	/*
	 * If we need to extend the journal get a few extra blocks
	 * while we're at it for efficiency's sake.
	 */
	needed += 3;
	err = ext4_journal_extend(handle, needed - handle->h_buffer_credits);
119
	if (err <= 0)
120
		return err;
121
	err = ext4_truncate_restart_trans(handle, inode, needed);
122 123
	if (err == 0)
		err = -EAGAIN;
124 125

	return err;
A
Alex Tomas 已提交
126 127 128 129 130 131 132 133 134 135 136 137
}

/*
 * could return:
 *  - EROFS
 *  - ENOMEM
 */
static int ext4_ext_get_access(handle_t *handle, struct inode *inode,
				struct ext4_ext_path *path)
{
	if (path->p_bh) {
		/* path points to block */
138
		BUFFER_TRACE(path->p_bh, "get_write_access");
A
Alex Tomas 已提交
139 140 141 142 143 144 145 146 147 148 149 150 151
		return ext4_journal_get_write_access(handle, path->p_bh);
	}
	/* path points to leaf/index in inode body */
	/* we use in-core data, no need to protect them */
	return 0;
}

/*
 * could return:
 *  - EROFS
 *  - ENOMEM
 *  - EIO
 */
152 153
int __ext4_ext_dirty(const char *where, unsigned int line, handle_t *handle,
		     struct inode *inode, struct ext4_ext_path *path)
A
Alex Tomas 已提交
154 155
{
	int err;
156 157

	WARN_ON(!rwsem_is_locked(&EXT4_I(inode)->i_data_sem));
A
Alex Tomas 已提交
158
	if (path->p_bh) {
159
		ext4_extent_block_csum_set(inode, ext_block_hdr(path->p_bh));
A
Alex Tomas 已提交
160
		/* path points to block */
161 162
		err = __ext4_handle_dirty_metadata(where, line, handle,
						   inode, path->p_bh);
A
Alex Tomas 已提交
163 164 165 166 167 168 169
	} else {
		/* path points to leaf/index in inode body */
		err = ext4_mark_inode_dirty(handle, inode);
	}
	return err;
}

170
static ext4_fsblk_t ext4_ext_find_goal(struct inode *inode,
A
Alex Tomas 已提交
171
			      struct ext4_ext_path *path,
A
Aneesh Kumar K.V 已提交
172
			      ext4_lblk_t block)
A
Alex Tomas 已提交
173 174
{
	if (path) {
175
		int depth = path->p_depth;
A
Alex Tomas 已提交
176 177
		struct ext4_extent *ex;

178 179 180 181 182 183 184 185 186 187 188 189 190 191
		/*
		 * Try to predict block placement assuming that we are
		 * filling in a file which will eventually be
		 * non-sparse --- i.e., in the case of libbfd writing
		 * an ELF object sections out-of-order but in a way
		 * the eventually results in a contiguous object or
		 * executable file, or some database extending a table
		 * space file.  However, this is actually somewhat
		 * non-ideal if we are writing a sparse file such as
		 * qemu or KVM writing a raw image file that is going
		 * to stay fairly sparse, since it will end up
		 * fragmenting the file system's free space.  Maybe we
		 * should have some hueristics or some way to allow
		 * userspace to pass a hint to file system,
T
Tao Ma 已提交
192
		 * especially if the latter case turns out to be
193 194
		 * common.
		 */
195
		ex = path[depth].p_ext;
196 197 198 199 200 201 202 203 204
		if (ex) {
			ext4_fsblk_t ext_pblk = ext4_ext_pblock(ex);
			ext4_lblk_t ext_block = le32_to_cpu(ex->ee_block);

			if (block > ext_block)
				return ext_pblk + (block - ext_block);
			else
				return ext_pblk - (ext_block - block);
		}
A
Alex Tomas 已提交
205

206 207
		/* it looks like index is empty;
		 * try to find starting block from index itself */
A
Alex Tomas 已提交
208 209 210 211 212
		if (path[depth].p_bh)
			return path[depth].p_bh->b_blocknr;
	}

	/* OK. use inode's group */
213
	return ext4_inode_to_goal_block(inode);
A
Alex Tomas 已提交
214 215
}

A
Aneesh Kumar K.V 已提交
216 217 218
/*
 * Allocation for a meta data block
 */
219
static ext4_fsblk_t
A
Aneesh Kumar K.V 已提交
220
ext4_ext_new_meta_block(handle_t *handle, struct inode *inode,
A
Alex Tomas 已提交
221
			struct ext4_ext_path *path,
222
			struct ext4_extent *ex, int *err, unsigned int flags)
A
Alex Tomas 已提交
223
{
224
	ext4_fsblk_t goal, newblock;
A
Alex Tomas 已提交
225 226

	goal = ext4_ext_find_goal(inode, path, le32_to_cpu(ex->ee_block));
227 228
	newblock = ext4_new_meta_blocks(handle, inode, goal, flags,
					NULL, err);
A
Alex Tomas 已提交
229 230 231
	return newblock;
}

232
static inline int ext4_ext_space_block(struct inode *inode, int check)
A
Alex Tomas 已提交
233 234 235 236 237
{
	int size;

	size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
			/ sizeof(struct ext4_extent);
238
#ifdef AGGRESSIVE_TEST
239 240
	if (!check && size > 6)
		size = 6;
A
Alex Tomas 已提交
241 242 243 244
#endif
	return size;
}

245
static inline int ext4_ext_space_block_idx(struct inode *inode, int check)
A
Alex Tomas 已提交
246 247 248 249 250
{
	int size;

	size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
			/ sizeof(struct ext4_extent_idx);
251
#ifdef AGGRESSIVE_TEST
252 253
	if (!check && size > 5)
		size = 5;
A
Alex Tomas 已提交
254 255 256 257
#endif
	return size;
}

258
static inline int ext4_ext_space_root(struct inode *inode, int check)
A
Alex Tomas 已提交
259 260 261 262 263 264
{
	int size;

	size = sizeof(EXT4_I(inode)->i_data);
	size -= sizeof(struct ext4_extent_header);
	size /= sizeof(struct ext4_extent);
265
#ifdef AGGRESSIVE_TEST
266 267
	if (!check && size > 3)
		size = 3;
A
Alex Tomas 已提交
268 269 270 271
#endif
	return size;
}

272
static inline int ext4_ext_space_root_idx(struct inode *inode, int check)
A
Alex Tomas 已提交
273 274 275 276 277 278
{
	int size;

	size = sizeof(EXT4_I(inode)->i_data);
	size -= sizeof(struct ext4_extent_header);
	size /= sizeof(struct ext4_extent_idx);
279
#ifdef AGGRESSIVE_TEST
280 281
	if (!check && size > 4)
		size = 4;
A
Alex Tomas 已提交
282 283 284 285
#endif
	return size;
}

286 287
static inline int
ext4_force_split_extent_at(handle_t *handle, struct inode *inode,
288
			   struct ext4_ext_path **ppath, ext4_lblk_t lblk,
289 290
			   int nofail)
{
291
	struct ext4_ext_path *path = *ppath;
292 293
	int unwritten = ext4_ext_is_unwritten(path[path->p_depth].p_ext);

294
	return ext4_split_extent_at(handle, inode, ppath, lblk, unwritten ?
295 296 297 298 299
			EXT4_EXT_MARK_UNWRIT1|EXT4_EXT_MARK_UNWRIT2 : 0,
			EXT4_EX_NOCACHE | EXT4_GET_BLOCKS_PRE_IO |
			(nofail ? EXT4_GET_BLOCKS_METADATA_NOFAIL:0));
}

300 301 302 303 304
/*
 * Calculate the number of metadata blocks needed
 * to allocate @blocks
 * Worse case is one block per extent
 */
305
int ext4_ext_calc_metadata_amount(struct inode *inode, ext4_lblk_t lblock)
306
{
307
	struct ext4_inode_info *ei = EXT4_I(inode);
308
	int idxs;
309

310 311
	idxs = ((inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
		/ sizeof(struct ext4_extent_idx));
312 313

	/*
314 315 316 317 318 319
	 * If the new delayed allocation block is contiguous with the
	 * previous da block, it can share index blocks with the
	 * previous block, so we only need to allocate a new index
	 * block every idxs leaf blocks.  At ldxs**2 blocks, we need
	 * an additional index block, and at ldxs**3 blocks, yet
	 * another index blocks.
320
	 */
321 322
	if (ei->i_da_metadata_calc_len &&
	    ei->i_da_metadata_calc_last_lblock+1 == lblock) {
323 324
		int num = 0;

325 326 327 328 329 330 331 332 333 334 335 336
		if ((ei->i_da_metadata_calc_len % idxs) == 0)
			num++;
		if ((ei->i_da_metadata_calc_len % (idxs*idxs)) == 0)
			num++;
		if ((ei->i_da_metadata_calc_len % (idxs*idxs*idxs)) == 0) {
			num++;
			ei->i_da_metadata_calc_len = 0;
		} else
			ei->i_da_metadata_calc_len++;
		ei->i_da_metadata_calc_last_lblock++;
		return num;
	}
337

338 339 340 341 342 343 344
	/*
	 * In the worst case we need a new set of index blocks at
	 * every level of the inode's extent tree.
	 */
	ei->i_da_metadata_calc_len = 1;
	ei->i_da_metadata_calc_last_lblock = lblock;
	return ext_depth(inode) + 1;
345 346
}

347 348 349 350 351 352 353
static int
ext4_ext_max_entries(struct inode *inode, int depth)
{
	int max;

	if (depth == ext_depth(inode)) {
		if (depth == 0)
354
			max = ext4_ext_space_root(inode, 1);
355
		else
356
			max = ext4_ext_space_root_idx(inode, 1);
357 358
	} else {
		if (depth == 0)
359
			max = ext4_ext_space_block(inode, 1);
360
		else
361
			max = ext4_ext_space_block_idx(inode, 1);
362 363 364 365 366
	}

	return max;
}

367 368
static int ext4_valid_extent(struct inode *inode, struct ext4_extent *ext)
{
369
	ext4_fsblk_t block = ext4_ext_pblock(ext);
370
	int len = ext4_ext_get_actual_len(ext);
371
	ext4_lblk_t lblock = le32_to_cpu(ext->ee_block);
372

373 374 375 376 377 378
	/*
	 * We allow neither:
	 *  - zero length
	 *  - overflow/wrap-around
	 */
	if (lblock + len <= lblock)
379
		return 0;
380
	return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, len);
381 382 383 384 385
}

static int ext4_valid_extent_idx(struct inode *inode,
				struct ext4_extent_idx *ext_idx)
{
386
	ext4_fsblk_t block = ext4_idx_pblock(ext_idx);
387

388
	return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, 1);
389 390 391 392 393 394 395 396 397 398 399 400 401 402
}

static int ext4_valid_extent_entries(struct inode *inode,
				struct ext4_extent_header *eh,
				int depth)
{
	unsigned short entries;
	if (eh->eh_entries == 0)
		return 1;

	entries = le16_to_cpu(eh->eh_entries);

	if (depth == 0) {
		/* leaf entries */
403
		struct ext4_extent *ext = EXT_FIRST_EXTENT(eh);
404 405 406 407 408
		struct ext4_super_block *es = EXT4_SB(inode->i_sb)->s_es;
		ext4_fsblk_t pblock = 0;
		ext4_lblk_t lblock = 0;
		ext4_lblk_t prev = 0;
		int len = 0;
409 410 411
		while (entries) {
			if (!ext4_valid_extent(inode, ext))
				return 0;
412 413 414 415 416 417 418 419 420

			/* Check for overlapping extents */
			lblock = le32_to_cpu(ext->ee_block);
			len = ext4_ext_get_actual_len(ext);
			if ((lblock <= prev) && prev) {
				pblock = ext4_ext_pblock(ext);
				es->s_last_error_block = cpu_to_le64(pblock);
				return 0;
			}
421 422
			ext++;
			entries--;
423
			prev = lblock + len - 1;
424 425
		}
	} else {
426
		struct ext4_extent_idx *ext_idx = EXT_FIRST_INDEX(eh);
427 428 429 430 431 432 433 434 435 436
		while (entries) {
			if (!ext4_valid_extent_idx(inode, ext_idx))
				return 0;
			ext_idx++;
			entries--;
		}
	}
	return 1;
}

437 438
static int __ext4_ext_check(const char *function, unsigned int line,
			    struct inode *inode, struct ext4_extent_header *eh,
439
			    int depth, ext4_fsblk_t pblk)
440 441
{
	const char *error_msg;
442
	int max = 0, err = -EFSCORRUPTED;
443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464

	if (unlikely(eh->eh_magic != EXT4_EXT_MAGIC)) {
		error_msg = "invalid magic";
		goto corrupted;
	}
	if (unlikely(le16_to_cpu(eh->eh_depth) != depth)) {
		error_msg = "unexpected eh_depth";
		goto corrupted;
	}
	if (unlikely(eh->eh_max == 0)) {
		error_msg = "invalid eh_max";
		goto corrupted;
	}
	max = ext4_ext_max_entries(inode, depth);
	if (unlikely(le16_to_cpu(eh->eh_max) > max)) {
		error_msg = "too large eh_max";
		goto corrupted;
	}
	if (unlikely(le16_to_cpu(eh->eh_entries) > le16_to_cpu(eh->eh_max))) {
		error_msg = "invalid eh_entries";
		goto corrupted;
	}
465 466 467 468
	if (!ext4_valid_extent_entries(inode, eh, depth)) {
		error_msg = "invalid extent entries";
		goto corrupted;
	}
V
Vegard Nossum 已提交
469 470 471 472
	if (unlikely(depth > 32)) {
		error_msg = "too large eh_depth";
		goto corrupted;
	}
473 474 475 476
	/* Verify checksum on non-root extent tree nodes */
	if (ext_depth(inode) != depth &&
	    !ext4_extent_block_csum_verify(inode, eh)) {
		error_msg = "extent tree corrupted";
477
		err = -EFSBADCRC;
478 479
		goto corrupted;
	}
480 481 482
	return 0;

corrupted:
483
	ext4_error_inode(inode, function, line, 0,
484 485 486 487 488 489
			 "pblk %llu bad header/extent: %s - magic %x, "
			 "entries %u, max %u(%u), depth %u(%u)",
			 (unsigned long long) pblk, error_msg,
			 le16_to_cpu(eh->eh_magic),
			 le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max),
			 max, le16_to_cpu(eh->eh_depth), depth);
490
	return err;
491 492
}

493 494
#define ext4_ext_check(inode, eh, depth, pblk)			\
	__ext4_ext_check(__func__, __LINE__, (inode), (eh), (depth), (pblk))
495

496 497
int ext4_ext_check_inode(struct inode *inode)
{
498
	return ext4_ext_check(inode, ext_inode_hdr(inode), ext_depth(inode), 0);
499 500
}

501 502
static struct buffer_head *
__read_extent_tree_block(const char *function, unsigned int line,
503 504
			 struct inode *inode, ext4_fsblk_t pblk, int depth,
			 int flags)
505
{
506 507 508
	struct buffer_head		*bh;
	int				err;

509
	bh = sb_getblk_gfp(inode->i_sb, pblk, __GFP_MOVABLE | GFP_NOFS);
510 511
	if (unlikely(!bh))
		return ERR_PTR(-ENOMEM);
512

513 514 515 516 517 518
	if (!bh_uptodate_or_lock(bh)) {
		trace_ext4_ext_load_extent(inode, pblk, _RET_IP_);
		err = bh_submit_read(bh);
		if (err < 0)
			goto errout;
	}
519
	if (buffer_verified(bh) && !(flags & EXT4_EX_FORCE_CACHE))
520 521
		return bh;
	err = __ext4_ext_check(function, line, inode,
522
			       ext_block_hdr(bh), depth, pblk);
523 524
	if (err)
		goto errout;
525
	set_buffer_verified(bh);
526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544
	/*
	 * If this is a leaf block, cache all of its entries
	 */
	if (!(flags & EXT4_EX_NOCACHE) && depth == 0) {
		struct ext4_extent_header *eh = ext_block_hdr(bh);
		struct ext4_extent *ex = EXT_FIRST_EXTENT(eh);
		ext4_lblk_t prev = 0;
		int i;

		for (i = le16_to_cpu(eh->eh_entries); i > 0; i--, ex++) {
			unsigned int status = EXTENT_STATUS_WRITTEN;
			ext4_lblk_t lblk = le32_to_cpu(ex->ee_block);
			int len = ext4_ext_get_actual_len(ex);

			if (prev && (prev != lblk))
				ext4_es_cache_extent(inode, prev,
						     lblk - prev, ~0,
						     EXTENT_STATUS_HOLE);

545
			if (ext4_ext_is_unwritten(ex))
546 547 548 549 550 551
				status = EXTENT_STATUS_UNWRITTEN;
			ext4_es_cache_extent(inode, lblk, len,
					     ext4_ext_pblock(ex), status);
			prev = lblk + len;
		}
	}
552 553 554 555 556
	return bh;
errout:
	put_bh(bh);
	return ERR_PTR(err);

557 558
}

559 560 561
#define read_extent_tree_block(inode, pblk, depth, flags)		\
	__read_extent_tree_block(__func__, __LINE__, (inode), (pblk),   \
				 (depth), (flags))
562

563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579
/*
 * This function is called to cache a file's extent information in the
 * extent status tree
 */
int ext4_ext_precache(struct inode *inode)
{
	struct ext4_inode_info *ei = EXT4_I(inode);
	struct ext4_ext_path *path = NULL;
	struct buffer_head *bh;
	int i = 0, depth, ret = 0;

	if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
		return 0;	/* not an extent-mapped inode */

	down_read(&ei->i_data_sem);
	depth = ext_depth(inode);

K
Kees Cook 已提交
580
	path = kcalloc(depth + 1, sizeof(struct ext4_ext_path),
581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627
		       GFP_NOFS);
	if (path == NULL) {
		up_read(&ei->i_data_sem);
		return -ENOMEM;
	}

	/* Don't cache anything if there are no external extent blocks */
	if (depth == 0)
		goto out;
	path[0].p_hdr = ext_inode_hdr(inode);
	ret = ext4_ext_check(inode, path[0].p_hdr, depth, 0);
	if (ret)
		goto out;
	path[0].p_idx = EXT_FIRST_INDEX(path[0].p_hdr);
	while (i >= 0) {
		/*
		 * If this is a leaf block or we've reached the end of
		 * the index block, go up
		 */
		if ((i == depth) ||
		    path[i].p_idx > EXT_LAST_INDEX(path[i].p_hdr)) {
			brelse(path[i].p_bh);
			path[i].p_bh = NULL;
			i--;
			continue;
		}
		bh = read_extent_tree_block(inode,
					    ext4_idx_pblock(path[i].p_idx++),
					    depth - i - 1,
					    EXT4_EX_FORCE_CACHE);
		if (IS_ERR(bh)) {
			ret = PTR_ERR(bh);
			break;
		}
		i++;
		path[i].p_bh = bh;
		path[i].p_hdr = ext_block_hdr(bh);
		path[i].p_idx = EXT_FIRST_INDEX(path[i].p_hdr);
	}
	ext4_set_inode_state(inode, EXT4_STATE_EXT_PRECACHED);
out:
	up_read(&ei->i_data_sem);
	ext4_ext_drop_refs(path);
	kfree(path);
	return ret;
}

A
Alex Tomas 已提交
628 629 630 631 632 633 634 635
#ifdef EXT_DEBUG
static void ext4_ext_show_path(struct inode *inode, struct ext4_ext_path *path)
{
	int k, l = path->p_depth;

	ext_debug("path:");
	for (k = 0; k <= l; k++, path++) {
		if (path->p_idx) {
636
		  ext_debug("  %d->%llu", le32_to_cpu(path->p_idx->ei_block),
637
			    ext4_idx_pblock(path->p_idx));
A
Alex Tomas 已提交
638
		} else if (path->p_ext) {
639
			ext_debug("  %d:[%d]%d:%llu ",
A
Alex Tomas 已提交
640
				  le32_to_cpu(path->p_ext->ee_block),
641
				  ext4_ext_is_unwritten(path->p_ext),
A
Amit Arora 已提交
642
				  ext4_ext_get_actual_len(path->p_ext),
643
				  ext4_ext_pblock(path->p_ext));
A
Alex Tomas 已提交
644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662
		} else
			ext_debug("  []");
	}
	ext_debug("\n");
}

static void ext4_ext_show_leaf(struct inode *inode, struct ext4_ext_path *path)
{
	int depth = ext_depth(inode);
	struct ext4_extent_header *eh;
	struct ext4_extent *ex;
	int i;

	if (!path)
		return;

	eh = path[depth].p_hdr;
	ex = EXT_FIRST_EXTENT(eh);

663 664
	ext_debug("Displaying leaf extents for inode %lu\n", inode->i_ino);

A
Alex Tomas 已提交
665
	for (i = 0; i < le16_to_cpu(eh->eh_entries); i++, ex++) {
666
		ext_debug("%d:[%d]%d:%llu ", le32_to_cpu(ex->ee_block),
667
			  ext4_ext_is_unwritten(ex),
668
			  ext4_ext_get_actual_len(ex), ext4_ext_pblock(ex));
A
Alex Tomas 已提交
669 670 671
	}
	ext_debug("\n");
}
672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697

static void ext4_ext_show_move(struct inode *inode, struct ext4_ext_path *path,
			ext4_fsblk_t newblock, int level)
{
	int depth = ext_depth(inode);
	struct ext4_extent *ex;

	if (depth != level) {
		struct ext4_extent_idx *idx;
		idx = path[level].p_idx;
		while (idx <= EXT_MAX_INDEX(path[level].p_hdr)) {
			ext_debug("%d: move %d:%llu in new index %llu\n", level,
					le32_to_cpu(idx->ei_block),
					ext4_idx_pblock(idx),
					newblock);
			idx++;
		}

		return;
	}

	ex = path[depth].p_ext;
	while (ex <= EXT_MAX_EXTENT(path[depth].p_hdr)) {
		ext_debug("move %d:%llu:[%d]%d in new leaf %llu\n",
				le32_to_cpu(ex->ee_block),
				ext4_ext_pblock(ex),
698
				ext4_ext_is_unwritten(ex),
699 700 701 702 703 704
				ext4_ext_get_actual_len(ex),
				newblock);
		ex++;
	}
}

A
Alex Tomas 已提交
705
#else
706 707
#define ext4_ext_show_path(inode, path)
#define ext4_ext_show_leaf(inode, path)
708
#define ext4_ext_show_move(inode, path, newblock, level)
A
Alex Tomas 已提交
709 710
#endif

711
void ext4_ext_drop_refs(struct ext4_ext_path *path)
A
Alex Tomas 已提交
712
{
713
	int depth, i;
A
Alex Tomas 已提交
714

715 716 717
	if (!path)
		return;
	depth = path->p_depth;
A
Alex Tomas 已提交
718 719 720 721 722 723 724 725
	for (i = 0; i <= depth; i++, path++)
		if (path->p_bh) {
			brelse(path->p_bh);
			path->p_bh = NULL;
		}
}

/*
726 727
 * ext4_ext_binsearch_idx:
 * binary search for the closest index of the given block
728
 * the header must be checked before calling this
A
Alex Tomas 已提交
729 730
 */
static void
A
Aneesh Kumar K.V 已提交
731 732
ext4_ext_binsearch_idx(struct inode *inode,
			struct ext4_ext_path *path, ext4_lblk_t block)
A
Alex Tomas 已提交
733 734 735 736 737
{
	struct ext4_extent_header *eh = path->p_hdr;
	struct ext4_extent_idx *r, *l, *m;


738
	ext_debug("binsearch for %u(idx):  ", block);
A
Alex Tomas 已提交
739 740

	l = EXT_FIRST_INDEX(eh) + 1;
D
Dmitry Monakhov 已提交
741
	r = EXT_LAST_INDEX(eh);
A
Alex Tomas 已提交
742 743 744 745 746 747
	while (l <= r) {
		m = l + (r - l) / 2;
		if (block < le32_to_cpu(m->ei_block))
			r = m - 1;
		else
			l = m + 1;
748 749 750
		ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ei_block),
				m, le32_to_cpu(m->ei_block),
				r, le32_to_cpu(r->ei_block));
A
Alex Tomas 已提交
751 752 753
	}

	path->p_idx = l - 1;
754
	ext_debug("  -> %u->%lld ", le32_to_cpu(path->p_idx->ei_block),
755
		  ext4_idx_pblock(path->p_idx));
A
Alex Tomas 已提交
756 757 758 759 760 761 762 763 764 765

#ifdef CHECK_BINSEARCH
	{
		struct ext4_extent_idx *chix, *ix;
		int k;

		chix = ix = EXT_FIRST_INDEX(eh);
		for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ix++) {
		  if (k != 0 &&
		      le32_to_cpu(ix->ei_block) <= le32_to_cpu(ix[-1].ei_block)) {
766 767 768 769
				printk(KERN_DEBUG "k=%d, ix=0x%p, "
				       "first=0x%p\n", k,
				       ix, EXT_FIRST_INDEX(eh));
				printk(KERN_DEBUG "%u <= %u\n",
A
Alex Tomas 已提交
770 771 772 773
				       le32_to_cpu(ix->ei_block),
				       le32_to_cpu(ix[-1].ei_block));
			}
			BUG_ON(k && le32_to_cpu(ix->ei_block)
D
Dave Kleikamp 已提交
774
					   <= le32_to_cpu(ix[-1].ei_block));
A
Alex Tomas 已提交
775 776 777 778 779 780 781 782 783 784 785
			if (block < le32_to_cpu(ix->ei_block))
				break;
			chix = ix;
		}
		BUG_ON(chix != path->p_idx);
	}
#endif

}

/*
786 787
 * ext4_ext_binsearch:
 * binary search for closest extent of the given block
788
 * the header must be checked before calling this
A
Alex Tomas 已提交
789 790
 */
static void
A
Aneesh Kumar K.V 已提交
791 792
ext4_ext_binsearch(struct inode *inode,
		struct ext4_ext_path *path, ext4_lblk_t block)
A
Alex Tomas 已提交
793 794 795 796 797 798
{
	struct ext4_extent_header *eh = path->p_hdr;
	struct ext4_extent *r, *l, *m;

	if (eh->eh_entries == 0) {
		/*
799 800
		 * this leaf is empty:
		 * we get such a leaf in split/add case
A
Alex Tomas 已提交
801 802 803 804
		 */
		return;
	}

805
	ext_debug("binsearch for %u:  ", block);
A
Alex Tomas 已提交
806 807

	l = EXT_FIRST_EXTENT(eh) + 1;
D
Dmitry Monakhov 已提交
808
	r = EXT_LAST_EXTENT(eh);
A
Alex Tomas 已提交
809 810 811 812 813 814 815

	while (l <= r) {
		m = l + (r - l) / 2;
		if (block < le32_to_cpu(m->ee_block))
			r = m - 1;
		else
			l = m + 1;
816 817 818
		ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ee_block),
				m, le32_to_cpu(m->ee_block),
				r, le32_to_cpu(r->ee_block));
A
Alex Tomas 已提交
819 820 821
	}

	path->p_ext = l - 1;
822
	ext_debug("  -> %d:%llu:[%d]%d ",
D
Dave Kleikamp 已提交
823
			le32_to_cpu(path->p_ext->ee_block),
824
			ext4_ext_pblock(path->p_ext),
825
			ext4_ext_is_unwritten(path->p_ext),
A
Amit Arora 已提交
826
			ext4_ext_get_actual_len(path->p_ext));
A
Alex Tomas 已提交
827 828 829 830 831 832 833 834 835

#ifdef CHECK_BINSEARCH
	{
		struct ext4_extent *chex, *ex;
		int k;

		chex = ex = EXT_FIRST_EXTENT(eh);
		for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ex++) {
			BUG_ON(k && le32_to_cpu(ex->ee_block)
D
Dave Kleikamp 已提交
836
					  <= le32_to_cpu(ex[-1].ee_block));
A
Alex Tomas 已提交
837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854
			if (block < le32_to_cpu(ex->ee_block))
				break;
			chex = ex;
		}
		BUG_ON(chex != path->p_ext);
	}
#endif

}

int ext4_ext_tree_init(handle_t *handle, struct inode *inode)
{
	struct ext4_extent_header *eh;

	eh = ext_inode_hdr(inode);
	eh->eh_depth = 0;
	eh->eh_entries = 0;
	eh->eh_magic = EXT4_EXT_MAGIC;
855
	eh->eh_max = cpu_to_le16(ext4_ext_space_root(inode, 0));
A
Alex Tomas 已提交
856 857 858 859 860
	ext4_mark_inode_dirty(handle, inode);
	return 0;
}

struct ext4_ext_path *
861 862
ext4_find_extent(struct inode *inode, ext4_lblk_t block,
		 struct ext4_ext_path **orig_path, int flags)
A
Alex Tomas 已提交
863 864 865
{
	struct ext4_extent_header *eh;
	struct buffer_head *bh;
866 867
	struct ext4_ext_path *path = orig_path ? *orig_path : NULL;
	short int depth, i, ppos = 0;
868
	int ret;
A
Alex Tomas 已提交
869 870

	eh = ext_inode_hdr(inode);
871
	depth = ext_depth(inode);
872 873 874 875 876 877
	if (depth < 0 || depth > EXT4_MAX_EXTENT_DEPTH) {
		EXT4_ERROR_INODE(inode, "inode has invalid extent depth: %d",
				 depth);
		ret = -EFSCORRUPTED;
		goto err;
	}
A
Alex Tomas 已提交
878

879
	if (path) {
880
		ext4_ext_drop_refs(path);
881 882 883 884 885 886
		if (depth > path[0].p_maxdepth) {
			kfree(path);
			*orig_path = path = NULL;
		}
	}
	if (!path) {
887
		/* account possible depth increase */
K
Kees Cook 已提交
888
		path = kcalloc(depth + 2, sizeof(struct ext4_ext_path),
A
Alex Tomas 已提交
889
				GFP_NOFS);
890
		if (unlikely(!path))
A
Alex Tomas 已提交
891
			return ERR_PTR(-ENOMEM);
892
		path[0].p_maxdepth = depth + 1;
A
Alex Tomas 已提交
893 894
	}
	path[0].p_hdr = eh;
895
	path[0].p_bh = NULL;
A
Alex Tomas 已提交
896

897
	i = depth;
A
Alex Tomas 已提交
898 899 900 901
	/* walk through the tree */
	while (i) {
		ext_debug("depth %d: num %d, max %d\n",
			  ppos, le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
902

A
Alex Tomas 已提交
903
		ext4_ext_binsearch_idx(inode, path + ppos, block);
904
		path[ppos].p_block = ext4_idx_pblock(path[ppos].p_idx);
A
Alex Tomas 已提交
905 906 907
		path[ppos].p_depth = i;
		path[ppos].p_ext = NULL;

908 909
		bh = read_extent_tree_block(inode, path[ppos].p_block, --i,
					    flags);
910
		if (IS_ERR(bh)) {
911
			ret = PTR_ERR(bh);
A
Alex Tomas 已提交
912
			goto err;
913
		}
914

A
Alex Tomas 已提交
915 916 917 918 919 920 921 922 923 924 925 926
		eh = ext_block_hdr(bh);
		ppos++;
		path[ppos].p_bh = bh;
		path[ppos].p_hdr = eh;
	}

	path[ppos].p_depth = i;
	path[ppos].p_ext = NULL;
	path[ppos].p_idx = NULL;

	/* find extent */
	ext4_ext_binsearch(inode, path + ppos, block);
927 928
	/* if not an empty leaf */
	if (path[ppos].p_ext)
929
		path[ppos].p_block = ext4_ext_pblock(path[ppos].p_ext);
A
Alex Tomas 已提交
930 931 932 933 934 935 936

	ext4_ext_show_path(inode, path);

	return path;

err:
	ext4_ext_drop_refs(path);
937 938 939
	kfree(path);
	if (orig_path)
		*orig_path = NULL;
940
	return ERR_PTR(ret);
A
Alex Tomas 已提交
941 942 943
}

/*
944 945 946
 * ext4_ext_insert_index:
 * insert new index [@logical;@ptr] into the block at @curp;
 * check where to insert: before @curp or after @curp
A
Alex Tomas 已提交
947
 */
948 949 950
static int ext4_ext_insert_index(handle_t *handle, struct inode *inode,
				 struct ext4_ext_path *curp,
				 int logical, ext4_fsblk_t ptr)
A
Alex Tomas 已提交
951 952 953 954
{
	struct ext4_extent_idx *ix;
	int len, err;

955 956
	err = ext4_ext_get_access(handle, inode, curp);
	if (err)
A
Alex Tomas 已提交
957 958
		return err;

959 960 961 962
	if (unlikely(logical == le32_to_cpu(curp->p_idx->ei_block))) {
		EXT4_ERROR_INODE(inode,
				 "logical %d == ei_block %d!",
				 logical, le32_to_cpu(curp->p_idx->ei_block));
963
		return -EFSCORRUPTED;
964
	}
965 966 967 968 969 970 971

	if (unlikely(le16_to_cpu(curp->p_hdr->eh_entries)
			     >= le16_to_cpu(curp->p_hdr->eh_max))) {
		EXT4_ERROR_INODE(inode,
				 "eh_entries %d >= eh_max %d!",
				 le16_to_cpu(curp->p_hdr->eh_entries),
				 le16_to_cpu(curp->p_hdr->eh_max));
972
		return -EFSCORRUPTED;
973 974
	}

A
Alex Tomas 已提交
975 976
	if (logical > le32_to_cpu(curp->p_idx->ei_block)) {
		/* insert after */
977
		ext_debug("insert new index %d after: %llu\n", logical, ptr);
A
Alex Tomas 已提交
978 979 980
		ix = curp->p_idx + 1;
	} else {
		/* insert before */
981
		ext_debug("insert new index %d before: %llu\n", logical, ptr);
A
Alex Tomas 已提交
982 983 984
		ix = curp->p_idx;
	}

985 986 987 988 989 990 991 992 993
	len = EXT_LAST_INDEX(curp->p_hdr) - ix + 1;
	BUG_ON(len < 0);
	if (len > 0) {
		ext_debug("insert new index %d: "
				"move %d indices from 0x%p to 0x%p\n",
				logical, len, ix, ix + 1);
		memmove(ix + 1, ix, len * sizeof(struct ext4_extent_idx));
	}

994 995
	if (unlikely(ix > EXT_MAX_INDEX(curp->p_hdr))) {
		EXT4_ERROR_INODE(inode, "ix > EXT_MAX_INDEX!");
996
		return -EFSCORRUPTED;
997 998
	}

A
Alex Tomas 已提交
999
	ix->ei_block = cpu_to_le32(logical);
1000
	ext4_idx_store_pblock(ix, ptr);
M
Marcin Slusarz 已提交
1001
	le16_add_cpu(&curp->p_hdr->eh_entries, 1);
A
Alex Tomas 已提交
1002

1003 1004
	if (unlikely(ix > EXT_LAST_INDEX(curp->p_hdr))) {
		EXT4_ERROR_INODE(inode, "ix > EXT_LAST_INDEX!");
1005
		return -EFSCORRUPTED;
1006
	}
A
Alex Tomas 已提交
1007 1008 1009 1010 1011 1012 1013 1014

	err = ext4_ext_dirty(handle, inode, curp);
	ext4_std_error(inode->i_sb, err);

	return err;
}

/*
1015 1016 1017 1018 1019 1020 1021 1022
 * ext4_ext_split:
 * inserts new subtree into the path, using free index entry
 * at depth @at:
 * - allocates all needed blocks (new leaf and all intermediate index blocks)
 * - makes decision where to split
 * - moves remaining extents and index entries (right to the split point)
 *   into the newly allocated blocks
 * - initializes subtree
A
Alex Tomas 已提交
1023 1024
 */
static int ext4_ext_split(handle_t *handle, struct inode *inode,
1025 1026 1027
			  unsigned int flags,
			  struct ext4_ext_path *path,
			  struct ext4_extent *newext, int at)
A
Alex Tomas 已提交
1028 1029 1030 1031 1032 1033
{
	struct buffer_head *bh = NULL;
	int depth = ext_depth(inode);
	struct ext4_extent_header *neh;
	struct ext4_extent_idx *fidx;
	int i = at, k, m, a;
1034
	ext4_fsblk_t newblock, oldblock;
A
Alex Tomas 已提交
1035
	__le32 border;
1036
	ext4_fsblk_t *ablocks = NULL; /* array of allocated blocks */
A
Alex Tomas 已提交
1037 1038 1039
	int err = 0;

	/* make decision: where to split? */
1040
	/* FIXME: now decision is simplest: at current extent */
A
Alex Tomas 已提交
1041

1042
	/* if current leaf will be split, then we should use
A
Alex Tomas 已提交
1043
	 * border from split point */
1044 1045
	if (unlikely(path[depth].p_ext > EXT_MAX_EXTENT(path[depth].p_hdr))) {
		EXT4_ERROR_INODE(inode, "p_ext > EXT_MAX_EXTENT!");
1046
		return -EFSCORRUPTED;
1047
	}
A
Alex Tomas 已提交
1048 1049
	if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr)) {
		border = path[depth].p_ext[1].ee_block;
1050
		ext_debug("leaf will be split."
A
Alex Tomas 已提交
1051
				" next leaf starts at %d\n",
D
Dave Kleikamp 已提交
1052
				  le32_to_cpu(border));
A
Alex Tomas 已提交
1053 1054 1055 1056
	} else {
		border = newext->ee_block;
		ext_debug("leaf will be added."
				" next leaf starts at %d\n",
D
Dave Kleikamp 已提交
1057
				le32_to_cpu(border));
A
Alex Tomas 已提交
1058 1059 1060
	}

	/*
1061 1062
	 * If error occurs, then we break processing
	 * and mark filesystem read-only. index won't
A
Alex Tomas 已提交
1063
	 * be inserted and tree will be in consistent
1064
	 * state. Next mount will repair buffers too.
A
Alex Tomas 已提交
1065 1066 1067
	 */

	/*
1068 1069 1070
	 * Get array to track all allocated blocks.
	 * We need this to handle errors and free blocks
	 * upon them.
A
Alex Tomas 已提交
1071
	 */
K
Kees Cook 已提交
1072
	ablocks = kcalloc(depth, sizeof(ext4_fsblk_t), GFP_NOFS);
A
Alex Tomas 已提交
1073 1074 1075 1076 1077 1078
	if (!ablocks)
		return -ENOMEM;

	/* allocate all needed blocks */
	ext_debug("allocate %d blocks for indexes/leaf\n", depth - at);
	for (a = 0; a < depth - at; a++) {
A
Aneesh Kumar K.V 已提交
1079
		newblock = ext4_ext_new_meta_block(handle, inode, path,
1080
						   newext, &err, flags);
A
Alex Tomas 已提交
1081 1082 1083 1084 1085 1086 1087
		if (newblock == 0)
			goto cleanup;
		ablocks[a] = newblock;
	}

	/* initialize new leaf */
	newblock = ablocks[--a];
1088 1089
	if (unlikely(newblock == 0)) {
		EXT4_ERROR_INODE(inode, "newblock == 0!");
1090
		err = -EFSCORRUPTED;
1091 1092
		goto cleanup;
	}
1093
	bh = sb_getblk_gfp(inode->i_sb, newblock, __GFP_MOVABLE | GFP_NOFS);
1094
	if (unlikely(!bh)) {
1095
		err = -ENOMEM;
A
Alex Tomas 已提交
1096 1097 1098 1099
		goto cleanup;
	}
	lock_buffer(bh);

1100 1101
	err = ext4_journal_get_create_access(handle, bh);
	if (err)
A
Alex Tomas 已提交
1102 1103 1104 1105
		goto cleanup;

	neh = ext_block_hdr(bh);
	neh->eh_entries = 0;
1106
	neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
A
Alex Tomas 已提交
1107 1108 1109
	neh->eh_magic = EXT4_EXT_MAGIC;
	neh->eh_depth = 0;

1110
	/* move remainder of path[depth] to the new leaf */
1111 1112 1113 1114 1115
	if (unlikely(path[depth].p_hdr->eh_entries !=
		     path[depth].p_hdr->eh_max)) {
		EXT4_ERROR_INODE(inode, "eh_entries %d != eh_max %d!",
				 path[depth].p_hdr->eh_entries,
				 path[depth].p_hdr->eh_max);
1116
		err = -EFSCORRUPTED;
1117 1118
		goto cleanup;
	}
A
Alex Tomas 已提交
1119
	/* start copy from next extent */
1120 1121
	m = EXT_MAX_EXTENT(path[depth].p_hdr) - path[depth].p_ext++;
	ext4_ext_show_move(inode, path, newblock, depth);
A
Alex Tomas 已提交
1122
	if (m) {
1123 1124 1125
		struct ext4_extent *ex;
		ex = EXT_FIRST_EXTENT(neh);
		memmove(ex, path[depth].p_ext, sizeof(struct ext4_extent) * m);
M
Marcin Slusarz 已提交
1126
		le16_add_cpu(&neh->eh_entries, m);
A
Alex Tomas 已提交
1127 1128
	}

1129
	ext4_extent_block_csum_set(inode, neh);
A
Alex Tomas 已提交
1130 1131 1132
	set_buffer_uptodate(bh);
	unlock_buffer(bh);

1133
	err = ext4_handle_dirty_metadata(handle, inode, bh);
1134
	if (err)
A
Alex Tomas 已提交
1135 1136 1137 1138 1139 1140
		goto cleanup;
	brelse(bh);
	bh = NULL;

	/* correct old leaf */
	if (m) {
1141 1142
		err = ext4_ext_get_access(handle, inode, path + depth);
		if (err)
A
Alex Tomas 已提交
1143
			goto cleanup;
M
Marcin Slusarz 已提交
1144
		le16_add_cpu(&path[depth].p_hdr->eh_entries, -m);
1145 1146
		err = ext4_ext_dirty(handle, inode, path + depth);
		if (err)
A
Alex Tomas 已提交
1147 1148 1149 1150 1151 1152
			goto cleanup;

	}

	/* create intermediate indexes */
	k = depth - at - 1;
1153 1154
	if (unlikely(k < 0)) {
		EXT4_ERROR_INODE(inode, "k %d < 0!", k);
1155
		err = -EFSCORRUPTED;
1156 1157
		goto cleanup;
	}
A
Alex Tomas 已提交
1158 1159 1160 1161 1162 1163 1164 1165
	if (k)
		ext_debug("create %d intermediate indices\n", k);
	/* insert new index into current index block */
	/* current depth stored in i var */
	i = depth - 1;
	while (k--) {
		oldblock = newblock;
		newblock = ablocks[--a];
1166
		bh = sb_getblk(inode->i_sb, newblock);
1167
		if (unlikely(!bh)) {
1168
			err = -ENOMEM;
A
Alex Tomas 已提交
1169 1170 1171 1172
			goto cleanup;
		}
		lock_buffer(bh);

1173 1174
		err = ext4_journal_get_create_access(handle, bh);
		if (err)
A
Alex Tomas 已提交
1175 1176 1177 1178 1179
			goto cleanup;

		neh = ext_block_hdr(bh);
		neh->eh_entries = cpu_to_le16(1);
		neh->eh_magic = EXT4_EXT_MAGIC;
1180
		neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
A
Alex Tomas 已提交
1181 1182 1183
		neh->eh_depth = cpu_to_le16(depth - i);
		fidx = EXT_FIRST_INDEX(neh);
		fidx->ei_block = border;
1184
		ext4_idx_store_pblock(fidx, oldblock);
A
Alex Tomas 已提交
1185

1186 1187
		ext_debug("int.index at %d (block %llu): %u -> %llu\n",
				i, newblock, le32_to_cpu(border), oldblock);
A
Alex Tomas 已提交
1188

1189
		/* move remainder of path[i] to the new index block */
1190 1191 1192 1193 1194
		if (unlikely(EXT_MAX_INDEX(path[i].p_hdr) !=
					EXT_LAST_INDEX(path[i].p_hdr))) {
			EXT4_ERROR_INODE(inode,
					 "EXT_MAX_INDEX != EXT_LAST_INDEX ee_block %d!",
					 le32_to_cpu(path[i].p_ext->ee_block));
1195
			err = -EFSCORRUPTED;
1196 1197
			goto cleanup;
		}
1198 1199 1200 1201 1202
		/* start copy indexes */
		m = EXT_MAX_INDEX(path[i].p_hdr) - path[i].p_idx++;
		ext_debug("cur 0x%p, last 0x%p\n", path[i].p_idx,
				EXT_MAX_INDEX(path[i].p_hdr));
		ext4_ext_show_move(inode, path, newblock, i);
A
Alex Tomas 已提交
1203
		if (m) {
1204
			memmove(++fidx, path[i].p_idx,
A
Alex Tomas 已提交
1205
				sizeof(struct ext4_extent_idx) * m);
M
Marcin Slusarz 已提交
1206
			le16_add_cpu(&neh->eh_entries, m);
A
Alex Tomas 已提交
1207
		}
1208
		ext4_extent_block_csum_set(inode, neh);
A
Alex Tomas 已提交
1209 1210 1211
		set_buffer_uptodate(bh);
		unlock_buffer(bh);

1212
		err = ext4_handle_dirty_metadata(handle, inode, bh);
1213
		if (err)
A
Alex Tomas 已提交
1214 1215 1216 1217 1218 1219 1220 1221 1222
			goto cleanup;
		brelse(bh);
		bh = NULL;

		/* correct old index */
		if (m) {
			err = ext4_ext_get_access(handle, inode, path + i);
			if (err)
				goto cleanup;
M
Marcin Slusarz 已提交
1223
			le16_add_cpu(&path[i].p_hdr->eh_entries, -m);
A
Alex Tomas 已提交
1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247
			err = ext4_ext_dirty(handle, inode, path + i);
			if (err)
				goto cleanup;
		}

		i--;
	}

	/* insert new index */
	err = ext4_ext_insert_index(handle, inode, path + at,
				    le32_to_cpu(border), newblock);

cleanup:
	if (bh) {
		if (buffer_locked(bh))
			unlock_buffer(bh);
		brelse(bh);
	}

	if (err) {
		/* free all allocated blocks in error case */
		for (i = 0; i < depth; i++) {
			if (!ablocks[i])
				continue;
1248
			ext4_free_blocks(handle, inode, NULL, ablocks[i], 1,
1249
					 EXT4_FREE_BLOCKS_METADATA);
A
Alex Tomas 已提交
1250 1251 1252 1253 1254 1255 1256 1257
		}
	}
	kfree(ablocks);

	return err;
}

/*
1258 1259 1260 1261 1262 1263
 * ext4_ext_grow_indepth:
 * implements tree growing procedure:
 * - allocates new block
 * - moves top-level data (index block or leaf) into the new block
 * - initializes new top-level, creating index that points to the
 *   just created block
A
Alex Tomas 已提交
1264 1265
 */
static int ext4_ext_grow_indepth(handle_t *handle, struct inode *inode,
1266
				 unsigned int flags)
A
Alex Tomas 已提交
1267 1268 1269
{
	struct ext4_extent_header *neh;
	struct buffer_head *bh;
1270 1271
	ext4_fsblk_t newblock, goal = 0;
	struct ext4_super_block *es = EXT4_SB(inode->i_sb)->s_es;
A
Alex Tomas 已提交
1272 1273
	int err = 0;

1274 1275 1276 1277 1278 1279 1280 1281 1282 1283
	/* Try to prepend new index to old one */
	if (ext_depth(inode))
		goal = ext4_idx_pblock(EXT_FIRST_INDEX(ext_inode_hdr(inode)));
	if (goal > le32_to_cpu(es->s_first_data_block)) {
		flags |= EXT4_MB_HINT_TRY_GOAL;
		goal--;
	} else
		goal = ext4_inode_to_goal_block(inode);
	newblock = ext4_new_meta_blocks(handle, inode, goal, flags,
					NULL, &err);
A
Alex Tomas 已提交
1284 1285 1286
	if (newblock == 0)
		return err;

1287
	bh = sb_getblk_gfp(inode->i_sb, newblock, __GFP_MOVABLE | GFP_NOFS);
1288
	if (unlikely(!bh))
1289
		return -ENOMEM;
A
Alex Tomas 已提交
1290 1291
	lock_buffer(bh);

1292 1293
	err = ext4_journal_get_create_access(handle, bh);
	if (err) {
A
Alex Tomas 已提交
1294 1295 1296 1297 1298
		unlock_buffer(bh);
		goto out;
	}

	/* move top-level index/leaf into new block */
1299 1300
	memmove(bh->b_data, EXT4_I(inode)->i_data,
		sizeof(EXT4_I(inode)->i_data));
A
Alex Tomas 已提交
1301 1302 1303 1304 1305 1306

	/* set size of new block */
	neh = ext_block_hdr(bh);
	/* old root could have indexes or leaves
	 * so calculate e_max right way */
	if (ext_depth(inode))
1307
		neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
A
Alex Tomas 已提交
1308
	else
1309
		neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
A
Alex Tomas 已提交
1310
	neh->eh_magic = EXT4_EXT_MAGIC;
1311
	ext4_extent_block_csum_set(inode, neh);
A
Alex Tomas 已提交
1312 1313 1314
	set_buffer_uptodate(bh);
	unlock_buffer(bh);

1315
	err = ext4_handle_dirty_metadata(handle, inode, bh);
1316
	if (err)
A
Alex Tomas 已提交
1317 1318
		goto out;

1319
	/* Update top-level index: num,max,pointer */
A
Alex Tomas 已提交
1320
	neh = ext_inode_hdr(inode);
1321 1322 1323 1324 1325 1326 1327 1328
	neh->eh_entries = cpu_to_le16(1);
	ext4_idx_store_pblock(EXT_FIRST_INDEX(neh), newblock);
	if (neh->eh_depth == 0) {
		/* Root extent block becomes index block */
		neh->eh_max = cpu_to_le16(ext4_ext_space_root_idx(inode, 0));
		EXT_FIRST_INDEX(neh)->ei_block =
			EXT_FIRST_EXTENT(neh)->ee_block;
	}
1329
	ext_debug("new root: num %d(%d), lblock %d, ptr %llu\n",
A
Alex Tomas 已提交
1330
		  le16_to_cpu(neh->eh_entries), le16_to_cpu(neh->eh_max),
1331
		  le32_to_cpu(EXT_FIRST_INDEX(neh)->ei_block),
1332
		  ext4_idx_pblock(EXT_FIRST_INDEX(neh)));
A
Alex Tomas 已提交
1333

1334
	le16_add_cpu(&neh->eh_depth, 1);
1335
	ext4_mark_inode_dirty(handle, inode);
A
Alex Tomas 已提交
1336 1337 1338 1339 1340 1341 1342
out:
	brelse(bh);

	return err;
}

/*
1343 1344 1345
 * ext4_ext_create_new_leaf:
 * finds empty index and adds new leaf.
 * if no free index is found, then it requests in-depth growing.
A
Alex Tomas 已提交
1346 1347
 */
static int ext4_ext_create_new_leaf(handle_t *handle, struct inode *inode,
1348 1349
				    unsigned int mb_flags,
				    unsigned int gb_flags,
1350
				    struct ext4_ext_path **ppath,
1351
				    struct ext4_extent *newext)
A
Alex Tomas 已提交
1352
{
1353
	struct ext4_ext_path *path = *ppath;
A
Alex Tomas 已提交
1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366
	struct ext4_ext_path *curp;
	int depth, i, err = 0;

repeat:
	i = depth = ext_depth(inode);

	/* walk up to the tree and look for free index entry */
	curp = path + depth;
	while (i > 0 && !EXT_HAS_FREE_INDEX(curp)) {
		i--;
		curp--;
	}

1367 1368
	/* we use already allocated block for index block,
	 * so subsequent data blocks should be contiguous */
A
Alex Tomas 已提交
1369 1370 1371
	if (EXT_HAS_FREE_INDEX(curp)) {
		/* if we found index with free entry, then use that
		 * entry: create all needed subtree and add new leaf */
1372
		err = ext4_ext_split(handle, inode, mb_flags, path, newext, i);
1373 1374
		if (err)
			goto out;
A
Alex Tomas 已提交
1375 1376

		/* refill path */
1377
		path = ext4_find_extent(inode,
A
Aneesh Kumar K.V 已提交
1378
				    (ext4_lblk_t)le32_to_cpu(newext->ee_block),
1379
				    ppath, gb_flags);
A
Alex Tomas 已提交
1380 1381 1382 1383
		if (IS_ERR(path))
			err = PTR_ERR(path);
	} else {
		/* tree is full, time to grow in depth */
1384
		err = ext4_ext_grow_indepth(handle, inode, mb_flags);
A
Alex Tomas 已提交
1385 1386 1387 1388
		if (err)
			goto out;

		/* refill path */
1389
		path = ext4_find_extent(inode,
A
Aneesh Kumar K.V 已提交
1390
				   (ext4_lblk_t)le32_to_cpu(newext->ee_block),
1391
				    ppath, gb_flags);
A
Alex Tomas 已提交
1392 1393 1394 1395 1396 1397
		if (IS_ERR(path)) {
			err = PTR_ERR(path);
			goto out;
		}

		/*
1398 1399
		 * only first (depth 0 -> 1) produces free space;
		 * in all other cases we have to split the grown tree
A
Alex Tomas 已提交
1400 1401 1402
		 */
		depth = ext_depth(inode);
		if (path[depth].p_hdr->eh_entries == path[depth].p_hdr->eh_max) {
1403
			/* now we need to split */
A
Alex Tomas 已提交
1404 1405 1406 1407 1408 1409 1410 1411
			goto repeat;
		}
	}

out:
	return err;
}

1412 1413 1414 1415 1416 1417 1418
/*
 * search the closest allocated block to the left for *logical
 * and returns it at @logical + it's physical address at @phys
 * if *logical is the smallest allocated block, the function
 * returns 0 at @phys
 * return value contains 0 (success) or error code
 */
1419 1420 1421
static int ext4_ext_search_left(struct inode *inode,
				struct ext4_ext_path *path,
				ext4_lblk_t *logical, ext4_fsblk_t *phys)
1422 1423 1424
{
	struct ext4_extent_idx *ix;
	struct ext4_extent *ex;
1425
	int depth, ee_len;
1426

1427 1428
	if (unlikely(path == NULL)) {
		EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
1429
		return -EFSCORRUPTED;
1430
	}
1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441
	depth = path->p_depth;
	*phys = 0;

	if (depth == 0 && path->p_ext == NULL)
		return 0;

	/* usually extent in the path covers blocks smaller
	 * then *logical, but it can be that extent is the
	 * first one in the file */

	ex = path[depth].p_ext;
1442
	ee_len = ext4_ext_get_actual_len(ex);
1443
	if (*logical < le32_to_cpu(ex->ee_block)) {
1444 1445 1446 1447
		if (unlikely(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex)) {
			EXT4_ERROR_INODE(inode,
					 "EXT_FIRST_EXTENT != ex *logical %d ee_block %d!",
					 *logical, le32_to_cpu(ex->ee_block));
1448
			return -EFSCORRUPTED;
1449
		}
1450 1451
		while (--depth >= 0) {
			ix = path[depth].p_idx;
1452 1453 1454
			if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
				EXT4_ERROR_INODE(inode,
				  "ix (%d) != EXT_FIRST_INDEX (%d) (depth %d)!",
1455
				  ix != NULL ? le32_to_cpu(ix->ei_block) : 0,
1456
				  EXT_FIRST_INDEX(path[depth].p_hdr) != NULL ?
1457
		le32_to_cpu(EXT_FIRST_INDEX(path[depth].p_hdr)->ei_block) : 0,
1458
				  depth);
1459
				return -EFSCORRUPTED;
1460
			}
1461 1462 1463 1464
		}
		return 0;
	}

1465 1466 1467 1468
	if (unlikely(*logical < (le32_to_cpu(ex->ee_block) + ee_len))) {
		EXT4_ERROR_INODE(inode,
				 "logical %d < ee_block %d + ee_len %d!",
				 *logical, le32_to_cpu(ex->ee_block), ee_len);
1469
		return -EFSCORRUPTED;
1470
	}
1471

1472
	*logical = le32_to_cpu(ex->ee_block) + ee_len - 1;
1473
	*phys = ext4_ext_pblock(ex) + ee_len - 1;
1474 1475 1476 1477 1478 1479
	return 0;
}

/*
 * search the closest allocated block to the right for *logical
 * and returns it at @logical + it's physical address at @phys
1480
 * if *logical is the largest allocated block, the function
1481 1482 1483
 * returns 0 at @phys
 * return value contains 0 (success) or error code
 */
1484 1485
static int ext4_ext_search_right(struct inode *inode,
				 struct ext4_ext_path *path,
1486 1487
				 ext4_lblk_t *logical, ext4_fsblk_t *phys,
				 struct ext4_extent **ret_ex)
1488 1489 1490 1491 1492 1493
{
	struct buffer_head *bh = NULL;
	struct ext4_extent_header *eh;
	struct ext4_extent_idx *ix;
	struct ext4_extent *ex;
	ext4_fsblk_t block;
1494 1495
	int depth;	/* Note, NOT eh_depth; depth from top of tree */
	int ee_len;
1496

1497 1498
	if (unlikely(path == NULL)) {
		EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
1499
		return -EFSCORRUPTED;
1500
	}
1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511
	depth = path->p_depth;
	*phys = 0;

	if (depth == 0 && path->p_ext == NULL)
		return 0;

	/* usually extent in the path covers blocks smaller
	 * then *logical, but it can be that extent is the
	 * first one in the file */

	ex = path[depth].p_ext;
1512
	ee_len = ext4_ext_get_actual_len(ex);
1513
	if (*logical < le32_to_cpu(ex->ee_block)) {
1514 1515 1516 1517
		if (unlikely(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex)) {
			EXT4_ERROR_INODE(inode,
					 "first_extent(path[%d].p_hdr) != ex",
					 depth);
1518
			return -EFSCORRUPTED;
1519
		}
1520 1521
		while (--depth >= 0) {
			ix = path[depth].p_idx;
1522 1523 1524 1525
			if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
				EXT4_ERROR_INODE(inode,
						 "ix != EXT_FIRST_INDEX *logical %d!",
						 *logical);
1526
				return -EFSCORRUPTED;
1527
			}
1528
		}
1529
		goto found_extent;
1530 1531
	}

1532 1533 1534 1535
	if (unlikely(*logical < (le32_to_cpu(ex->ee_block) + ee_len))) {
		EXT4_ERROR_INODE(inode,
				 "logical %d < ee_block %d + ee_len %d!",
				 *logical, le32_to_cpu(ex->ee_block), ee_len);
1536
		return -EFSCORRUPTED;
1537
	}
1538 1539 1540 1541

	if (ex != EXT_LAST_EXTENT(path[depth].p_hdr)) {
		/* next allocated block in this leaf */
		ex++;
1542
		goto found_extent;
1543 1544 1545 1546 1547 1548
	}

	/* go up and search for index to the right */
	while (--depth >= 0) {
		ix = path[depth].p_idx;
		if (ix != EXT_LAST_INDEX(path[depth].p_hdr))
W
Wu Fengguang 已提交
1549
			goto got_index;
1550 1551
	}

W
Wu Fengguang 已提交
1552 1553
	/* we've gone up to the root and found no index to the right */
	return 0;
1554

W
Wu Fengguang 已提交
1555
got_index:
1556 1557 1558 1559
	/* we've found index to the right, let's
	 * follow it and find the closest allocated
	 * block to the right */
	ix++;
1560
	block = ext4_idx_pblock(ix);
1561
	while (++depth < path->p_depth) {
1562
		/* subtract from p_depth to get proper eh_depth */
1563
		bh = read_extent_tree_block(inode, block,
1564
					    path->p_depth - depth, 0);
1565 1566 1567
		if (IS_ERR(bh))
			return PTR_ERR(bh);
		eh = ext_block_hdr(bh);
1568
		ix = EXT_FIRST_INDEX(eh);
1569
		block = ext4_idx_pblock(ix);
1570 1571 1572
		put_bh(bh);
	}

1573
	bh = read_extent_tree_block(inode, block, path->p_depth - depth, 0);
1574 1575
	if (IS_ERR(bh))
		return PTR_ERR(bh);
1576 1577
	eh = ext_block_hdr(bh);
	ex = EXT_FIRST_EXTENT(eh);
1578
found_extent:
1579
	*logical = le32_to_cpu(ex->ee_block);
1580
	*phys = ext4_ext_pblock(ex);
1581 1582 1583
	*ret_ex = ex;
	if (bh)
		put_bh(bh);
1584 1585 1586
	return 0;
}

A
Alex Tomas 已提交
1587
/*
1588
 * ext4_ext_next_allocated_block:
1589
 * returns allocated block in subsequent extent or EXT_MAX_BLOCKS.
1590 1591 1592
 * NOTE: it considers block number from index entry as
 * allocated block. Thus, index entries have to be consistent
 * with leaves.
A
Alex Tomas 已提交
1593
 */
1594
ext4_lblk_t
A
Alex Tomas 已提交
1595 1596 1597 1598 1599 1600 1601 1602
ext4_ext_next_allocated_block(struct ext4_ext_path *path)
{
	int depth;

	BUG_ON(path == NULL);
	depth = path->p_depth;

	if (depth == 0 && path->p_ext == NULL)
1603
		return EXT_MAX_BLOCKS;
A
Alex Tomas 已提交
1604 1605 1606 1607

	while (depth >= 0) {
		if (depth == path->p_depth) {
			/* leaf */
1608 1609
			if (path[depth].p_ext &&
				path[depth].p_ext !=
A
Alex Tomas 已提交
1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620
					EXT_LAST_EXTENT(path[depth].p_hdr))
			  return le32_to_cpu(path[depth].p_ext[1].ee_block);
		} else {
			/* index */
			if (path[depth].p_idx !=
					EXT_LAST_INDEX(path[depth].p_hdr))
			  return le32_to_cpu(path[depth].p_idx[1].ei_block);
		}
		depth--;
	}

1621
	return EXT_MAX_BLOCKS;
A
Alex Tomas 已提交
1622 1623 1624
}

/*
1625
 * ext4_ext_next_leaf_block:
1626
 * returns first allocated block from next leaf or EXT_MAX_BLOCKS
A
Alex Tomas 已提交
1627
 */
1628
static ext4_lblk_t ext4_ext_next_leaf_block(struct ext4_ext_path *path)
A
Alex Tomas 已提交
1629 1630 1631 1632 1633 1634 1635 1636
{
	int depth;

	BUG_ON(path == NULL);
	depth = path->p_depth;

	/* zero-tree has no leaf blocks at all */
	if (depth == 0)
1637
		return EXT_MAX_BLOCKS;
A
Alex Tomas 已提交
1638 1639 1640 1641 1642 1643 1644

	/* go to index block */
	depth--;

	while (depth >= 0) {
		if (path[depth].p_idx !=
				EXT_LAST_INDEX(path[depth].p_hdr))
A
Aneesh Kumar K.V 已提交
1645 1646
			return (ext4_lblk_t)
				le32_to_cpu(path[depth].p_idx[1].ei_block);
A
Alex Tomas 已提交
1647 1648 1649
		depth--;
	}

1650
	return EXT_MAX_BLOCKS;
A
Alex Tomas 已提交
1651 1652 1653
}

/*
1654 1655 1656
 * ext4_ext_correct_indexes:
 * if leaf gets modified and modified extent is first in the leaf,
 * then we have to correct all indexes above.
A
Alex Tomas 已提交
1657 1658
 * TODO: do we need to correct tree in all cases?
 */
A
Aneesh Kumar K.V 已提交
1659
static int ext4_ext_correct_indexes(handle_t *handle, struct inode *inode,
A
Alex Tomas 已提交
1660 1661 1662 1663 1664 1665 1666 1667 1668 1669
				struct ext4_ext_path *path)
{
	struct ext4_extent_header *eh;
	int depth = ext_depth(inode);
	struct ext4_extent *ex;
	__le32 border;
	int k, err = 0;

	eh = path[depth].p_hdr;
	ex = path[depth].p_ext;
1670 1671 1672 1673

	if (unlikely(ex == NULL || eh == NULL)) {
		EXT4_ERROR_INODE(inode,
				 "ex %p == NULL or eh %p == NULL", ex, eh);
1674
		return -EFSCORRUPTED;
1675
	}
A
Alex Tomas 已提交
1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687

	if (depth == 0) {
		/* there is no tree at all */
		return 0;
	}

	if (ex != EXT_FIRST_EXTENT(eh)) {
		/* we correct tree if first leaf got modified only */
		return 0;
	}

	/*
1688
	 * TODO: we need correction if border is smaller than current one
A
Alex Tomas 已提交
1689 1690 1691
	 */
	k = depth - 1;
	border = path[depth].p_ext->ee_block;
1692 1693
	err = ext4_ext_get_access(handle, inode, path + k);
	if (err)
A
Alex Tomas 已提交
1694 1695
		return err;
	path[k].p_idx->ei_block = border;
1696 1697
	err = ext4_ext_dirty(handle, inode, path + k);
	if (err)
A
Alex Tomas 已提交
1698 1699 1700 1701 1702 1703
		return err;

	while (k--) {
		/* change all left-side indexes */
		if (path[k+1].p_idx != EXT_FIRST_INDEX(path[k+1].p_hdr))
			break;
1704 1705
		err = ext4_ext_get_access(handle, inode, path + k);
		if (err)
A
Alex Tomas 已提交
1706 1707
			break;
		path[k].p_idx->ei_block = border;
1708 1709
		err = ext4_ext_dirty(handle, inode, path + k);
		if (err)
A
Alex Tomas 已提交
1710 1711 1712 1713 1714 1715
			break;
	}

	return err;
}

1716
int
A
Alex Tomas 已提交
1717 1718 1719
ext4_can_extents_be_merged(struct inode *inode, struct ext4_extent *ex1,
				struct ext4_extent *ex2)
{
1720
	unsigned short ext1_ee_len, ext2_ee_len;
A
Amit Arora 已提交
1721

1722
	if (ext4_ext_is_unwritten(ex1) != ext4_ext_is_unwritten(ex2))
A
Amit Arora 已提交
1723 1724 1725 1726 1727 1728
		return 0;

	ext1_ee_len = ext4_ext_get_actual_len(ex1);
	ext2_ee_len = ext4_ext_get_actual_len(ex2);

	if (le32_to_cpu(ex1->ee_block) + ext1_ee_len !=
A
Andrew Morton 已提交
1729
			le32_to_cpu(ex2->ee_block))
A
Alex Tomas 已提交
1730 1731
		return 0;

1732 1733 1734
	/*
	 * To allow future support for preallocated extents to be added
	 * as an RO_COMPAT feature, refuse to merge to extents if
1735
	 * this can result in the top bit of ee_len being set.
1736
	 */
1737
	if (ext1_ee_len + ext2_ee_len > EXT_INIT_MAX_LEN)
1738
		return 0;
1739 1740 1741 1742 1743 1744
	/*
	 * The check for IO to unwritten extent is somewhat racy as we
	 * increment i_unwritten / set EXT4_STATE_DIO_UNWRITTEN only after
	 * dropping i_data_sem. But reserved blocks should save us in that
	 * case.
	 */
1745
	if (ext4_ext_is_unwritten(ex1) &&
1746 1747
	    (ext4_test_inode_state(inode, EXT4_STATE_DIO_UNWRITTEN) ||
	     atomic_read(&EXT4_I(inode)->i_unwritten) ||
1748
	     (ext1_ee_len + ext2_ee_len > EXT_UNWRITTEN_MAX_LEN)))
1749
		return 0;
1750
#ifdef AGGRESSIVE_TEST
1751
	if (ext1_ee_len >= 4)
A
Alex Tomas 已提交
1752 1753 1754
		return 0;
#endif

1755
	if (ext4_ext_pblock(ex1) + ext1_ee_len == ext4_ext_pblock(ex2))
A
Alex Tomas 已提交
1756 1757 1758 1759
		return 1;
	return 0;
}

1760 1761 1762 1763 1764 1765 1766
/*
 * This function tries to merge the "ex" extent to the next extent in the tree.
 * It always tries to merge towards right. If you want to merge towards
 * left, pass "ex - 1" as argument instead of "ex".
 * Returns 0 if the extents (ex and ex+1) were _not_ merged and returns
 * 1 if they got merged.
 */
1767
static int ext4_ext_try_to_merge_right(struct inode *inode,
1768 1769
				 struct ext4_ext_path *path,
				 struct ext4_extent *ex)
1770 1771 1772
{
	struct ext4_extent_header *eh;
	unsigned int depth, len;
1773
	int merge_done = 0, unwritten;
1774 1775 1776 1777 1778 1779 1780 1781 1782

	depth = ext_depth(inode);
	BUG_ON(path[depth].p_hdr == NULL);
	eh = path[depth].p_hdr;

	while (ex < EXT_LAST_EXTENT(eh)) {
		if (!ext4_can_extents_be_merged(inode, ex, ex + 1))
			break;
		/* merge with next extent! */
1783
		unwritten = ext4_ext_is_unwritten(ex);
1784 1785
		ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
				+ ext4_ext_get_actual_len(ex + 1));
1786 1787
		if (unwritten)
			ext4_ext_mark_unwritten(ex);
1788 1789 1790 1791 1792 1793

		if (ex + 1 < EXT_LAST_EXTENT(eh)) {
			len = (EXT_LAST_EXTENT(eh) - ex - 1)
				* sizeof(struct ext4_extent);
			memmove(ex + 1, ex + 2, len);
		}
M
Marcin Slusarz 已提交
1794
		le16_add_cpu(&eh->eh_entries, -1);
1795 1796 1797
		merge_done = 1;
		WARN_ON(eh->eh_entries == 0);
		if (!eh->eh_entries)
1798
			EXT4_ERROR_INODE(inode, "eh->eh_entries = 0!");
1799 1800 1801 1802 1803
	}

	return merge_done;
}

1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836
/*
 * This function does a very simple check to see if we can collapse
 * an extent tree with a single extent tree leaf block into the inode.
 */
static void ext4_ext_try_to_merge_up(handle_t *handle,
				     struct inode *inode,
				     struct ext4_ext_path *path)
{
	size_t s;
	unsigned max_root = ext4_ext_space_root(inode, 0);
	ext4_fsblk_t blk;

	if ((path[0].p_depth != 1) ||
	    (le16_to_cpu(path[0].p_hdr->eh_entries) != 1) ||
	    (le16_to_cpu(path[1].p_hdr->eh_entries) > max_root))
		return;

	/*
	 * We need to modify the block allocation bitmap and the block
	 * group descriptor to release the extent tree block.  If we
	 * can't get the journal credits, give up.
	 */
	if (ext4_journal_extend(handle, 2))
		return;

	/*
	 * Copy the extent data up to the inode
	 */
	blk = ext4_idx_pblock(path[0].p_idx);
	s = le16_to_cpu(path[1].p_hdr->eh_entries) *
		sizeof(struct ext4_extent_idx);
	s += sizeof(struct ext4_extent_header);

1837
	path[1].p_maxdepth = path[0].p_maxdepth;
1838 1839 1840 1841 1842 1843 1844 1845
	memcpy(path[0].p_hdr, path[1].p_hdr, s);
	path[0].p_depth = 0;
	path[0].p_ext = EXT_FIRST_EXTENT(path[0].p_hdr) +
		(path[1].p_ext - EXT_FIRST_EXTENT(path[1].p_hdr));
	path[0].p_hdr->eh_max = cpu_to_le16(max_root);

	brelse(path[1].p_bh);
	ext4_free_blocks(handle, inode, NULL, blk, 1,
1846
			 EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET);
1847 1848
}

1849 1850 1851 1852
/*
 * This function tries to merge the @ex extent to neighbours in the tree.
 * return 1 if merge left else 0.
 */
1853 1854
static void ext4_ext_try_to_merge(handle_t *handle,
				  struct inode *inode,
1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868
				  struct ext4_ext_path *path,
				  struct ext4_extent *ex) {
	struct ext4_extent_header *eh;
	unsigned int depth;
	int merge_done = 0;

	depth = ext_depth(inode);
	BUG_ON(path[depth].p_hdr == NULL);
	eh = path[depth].p_hdr;

	if (ex > EXT_FIRST_EXTENT(eh))
		merge_done = ext4_ext_try_to_merge_right(inode, path, ex - 1);

	if (!merge_done)
1869
		(void) ext4_ext_try_to_merge_right(inode, path, ex);
1870

1871
	ext4_ext_try_to_merge_up(handle, inode, path);
1872 1873
}

A
Amit Arora 已提交
1874 1875 1876 1877 1878 1879 1880 1881
/*
 * check if a portion of the "newext" extent overlaps with an
 * existing extent.
 *
 * If there is an overlap discovered, it updates the length of the newext
 * such that there will be no overlap, and then returns 1.
 * If there is no overlap found, it returns 0.
 */
1882 1883
static unsigned int ext4_ext_check_overlap(struct ext4_sb_info *sbi,
					   struct inode *inode,
1884 1885
					   struct ext4_extent *newext,
					   struct ext4_ext_path *path)
A
Amit Arora 已提交
1886
{
A
Aneesh Kumar K.V 已提交
1887
	ext4_lblk_t b1, b2;
A
Amit Arora 已提交
1888 1889 1890 1891
	unsigned int depth, len1;
	unsigned int ret = 0;

	b1 = le32_to_cpu(newext->ee_block);
A
Amit Arora 已提交
1892
	len1 = ext4_ext_get_actual_len(newext);
A
Amit Arora 已提交
1893 1894 1895
	depth = ext_depth(inode);
	if (!path[depth].p_ext)
		goto out;
1896
	b2 = EXT4_LBLK_CMASK(sbi, le32_to_cpu(path[depth].p_ext->ee_block));
A
Amit Arora 已提交
1897 1898 1899

	/*
	 * get the next allocated block if the extent in the path
1900
	 * is before the requested block(s)
A
Amit Arora 已提交
1901 1902 1903
	 */
	if (b2 < b1) {
		b2 = ext4_ext_next_allocated_block(path);
1904
		if (b2 == EXT_MAX_BLOCKS)
A
Amit Arora 已提交
1905
			goto out;
1906
		b2 = EXT4_LBLK_CMASK(sbi, b2);
A
Amit Arora 已提交
1907 1908
	}

A
Aneesh Kumar K.V 已提交
1909
	/* check for wrap through zero on extent logical start block*/
A
Amit Arora 已提交
1910
	if (b1 + len1 < b1) {
1911
		len1 = EXT_MAX_BLOCKS - b1;
A
Amit Arora 已提交
1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924
		newext->ee_len = cpu_to_le16(len1);
		ret = 1;
	}

	/* check for overlap */
	if (b1 + len1 > b2) {
		newext->ee_len = cpu_to_le16(b2 - b1);
		ret = 1;
	}
out:
	return ret;
}

A
Alex Tomas 已提交
1925
/*
1926 1927 1928 1929
 * ext4_ext_insert_extent:
 * tries to merge requsted extent into the existing extent or
 * inserts requested extent as new one into the tree,
 * creating new leaf in the no-space case.
A
Alex Tomas 已提交
1930 1931
 */
int ext4_ext_insert_extent(handle_t *handle, struct inode *inode,
1932
				struct ext4_ext_path **ppath,
1933
				struct ext4_extent *newext, int gb_flags)
A
Alex Tomas 已提交
1934
{
1935
	struct ext4_ext_path *path = *ppath;
1936
	struct ext4_extent_header *eh;
A
Alex Tomas 已提交
1937 1938 1939
	struct ext4_extent *ex, *fex;
	struct ext4_extent *nearex; /* nearest extent */
	struct ext4_ext_path *npath = NULL;
A
Aneesh Kumar K.V 已提交
1940 1941
	int depth, len, err;
	ext4_lblk_t next;
1942
	int mb_flags = 0, unwritten;
A
Alex Tomas 已提交
1943

1944 1945
	if (gb_flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
		mb_flags |= EXT4_MB_DELALLOC_RESERVED;
1946 1947
	if (unlikely(ext4_ext_get_actual_len(newext) == 0)) {
		EXT4_ERROR_INODE(inode, "ext4_ext_get_actual_len(newext) == 0");
1948
		return -EFSCORRUPTED;
1949
	}
A
Alex Tomas 已提交
1950 1951
	depth = ext_depth(inode);
	ex = path[depth].p_ext;
1952
	eh = path[depth].p_hdr;
1953 1954
	if (unlikely(path[depth].p_hdr == NULL)) {
		EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
1955
		return -EFSCORRUPTED;
1956
	}
A
Alex Tomas 已提交
1957 1958

	/* try to insert block into found extent and return */
1959
	if (ex && !(gb_flags & EXT4_GET_BLOCKS_PRE_IO)) {
A
Amit Arora 已提交
1960 1961

		/*
1962 1963
		 * Try to see whether we should rather test the extent on
		 * right from ex, or from the left of ex. This is because
1964
		 * ext4_find_extent() can return either extent on the
1965 1966
		 * left, or on the right from the searched position. This
		 * will make merging more effective.
A
Amit Arora 已提交
1967
		 */
1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983
		if (ex < EXT_LAST_EXTENT(eh) &&
		    (le32_to_cpu(ex->ee_block) +
		    ext4_ext_get_actual_len(ex) <
		    le32_to_cpu(newext->ee_block))) {
			ex += 1;
			goto prepend;
		} else if ((ex > EXT_FIRST_EXTENT(eh)) &&
			   (le32_to_cpu(newext->ee_block) +
			   ext4_ext_get_actual_len(newext) <
			   le32_to_cpu(ex->ee_block)))
			ex -= 1;

		/* Try to append newex to the ex */
		if (ext4_can_extents_be_merged(inode, ex, newext)) {
			ext_debug("append [%d]%d block to %u:[%d]%d"
				  "(from %llu)\n",
1984
				  ext4_ext_is_unwritten(newext),
1985 1986
				  ext4_ext_get_actual_len(newext),
				  le32_to_cpu(ex->ee_block),
1987
				  ext4_ext_is_unwritten(ex),
1988 1989 1990 1991 1992 1993
				  ext4_ext_get_actual_len(ex),
				  ext4_ext_pblock(ex));
			err = ext4_ext_get_access(handle, inode,
						  path + depth);
			if (err)
				return err;
1994
			unwritten = ext4_ext_is_unwritten(ex);
1995
			ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
A
Amit Arora 已提交
1996
					+ ext4_ext_get_actual_len(newext));
1997 1998
			if (unwritten)
				ext4_ext_mark_unwritten(ex);
1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009
			eh = path[depth].p_hdr;
			nearex = ex;
			goto merge;
		}

prepend:
		/* Try to prepend newex to the ex */
		if (ext4_can_extents_be_merged(inode, newext, ex)) {
			ext_debug("prepend %u[%d]%d block to %u:[%d]%d"
				  "(from %llu)\n",
				  le32_to_cpu(newext->ee_block),
2010
				  ext4_ext_is_unwritten(newext),
2011 2012
				  ext4_ext_get_actual_len(newext),
				  le32_to_cpu(ex->ee_block),
2013
				  ext4_ext_is_unwritten(ex),
2014 2015 2016 2017 2018 2019 2020
				  ext4_ext_get_actual_len(ex),
				  ext4_ext_pblock(ex));
			err = ext4_ext_get_access(handle, inode,
						  path + depth);
			if (err)
				return err;

2021
			unwritten = ext4_ext_is_unwritten(ex);
2022 2023 2024 2025
			ex->ee_block = newext->ee_block;
			ext4_ext_store_pblock(ex, ext4_ext_pblock(newext));
			ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
					+ ext4_ext_get_actual_len(newext));
2026 2027
			if (unwritten)
				ext4_ext_mark_unwritten(ex);
2028 2029 2030 2031
			eh = path[depth].p_hdr;
			nearex = ex;
			goto merge;
		}
A
Alex Tomas 已提交
2032 2033 2034 2035 2036 2037 2038 2039 2040
	}

	depth = ext_depth(inode);
	eh = path[depth].p_hdr;
	if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))
		goto has_space;

	/* probably next leaf has space for us? */
	fex = EXT_LAST_EXTENT(eh);
2041 2042
	next = EXT_MAX_BLOCKS;
	if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block))
2043
		next = ext4_ext_next_leaf_block(path);
2044
	if (next != EXT_MAX_BLOCKS) {
2045
		ext_debug("next leaf block - %u\n", next);
A
Alex Tomas 已提交
2046
		BUG_ON(npath != NULL);
2047
		npath = ext4_find_extent(inode, next, NULL, 0);
A
Alex Tomas 已提交
2048 2049 2050 2051 2052
		if (IS_ERR(npath))
			return PTR_ERR(npath);
		BUG_ON(npath->p_depth != path->p_depth);
		eh = npath[depth].p_hdr;
		if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) {
L
Lucas De Marchi 已提交
2053
			ext_debug("next leaf isn't full(%d)\n",
A
Alex Tomas 已提交
2054 2055
				  le16_to_cpu(eh->eh_entries));
			path = npath;
2056
			goto has_space;
A
Alex Tomas 已提交
2057 2058 2059 2060 2061 2062
		}
		ext_debug("next leaf has no free space(%d,%d)\n",
			  le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
	}

	/*
2063 2064
	 * There is no free space in the found leaf.
	 * We're gonna add a new leaf in the tree.
A
Alex Tomas 已提交
2065
	 */
2066
	if (gb_flags & EXT4_GET_BLOCKS_METADATA_NOFAIL)
2067
		mb_flags |= EXT4_MB_USE_RESERVED;
2068
	err = ext4_ext_create_new_leaf(handle, inode, mb_flags, gb_flags,
2069
				       ppath, newext);
A
Alex Tomas 已提交
2070 2071 2072 2073 2074 2075 2076 2077
	if (err)
		goto cleanup;
	depth = ext_depth(inode);
	eh = path[depth].p_hdr;

has_space:
	nearex = path[depth].p_ext;

2078 2079
	err = ext4_ext_get_access(handle, inode, path + depth);
	if (err)
A
Alex Tomas 已提交
2080 2081 2082 2083
		goto cleanup;

	if (!nearex) {
		/* there is no extent in this leaf, create first one */
2084
		ext_debug("first extent in the leaf: %u:%llu:[%d]%d\n",
D
Dave Kleikamp 已提交
2085
				le32_to_cpu(newext->ee_block),
2086
				ext4_ext_pblock(newext),
2087
				ext4_ext_is_unwritten(newext),
A
Amit Arora 已提交
2088
				ext4_ext_get_actual_len(newext));
2089 2090 2091
		nearex = EXT_FIRST_EXTENT(eh);
	} else {
		if (le32_to_cpu(newext->ee_block)
D
Dave Kleikamp 已提交
2092
			   > le32_to_cpu(nearex->ee_block)) {
2093
			/* Insert after */
2094 2095
			ext_debug("insert %u:%llu:[%d]%d before: "
					"nearest %p\n",
2096 2097
					le32_to_cpu(newext->ee_block),
					ext4_ext_pblock(newext),
2098
					ext4_ext_is_unwritten(newext),
2099 2100 2101 2102 2103 2104
					ext4_ext_get_actual_len(newext),
					nearex);
			nearex++;
		} else {
			/* Insert before */
			BUG_ON(newext->ee_block == nearex->ee_block);
2105 2106
			ext_debug("insert %u:%llu:[%d]%d after: "
					"nearest %p\n",
D
Dave Kleikamp 已提交
2107
					le32_to_cpu(newext->ee_block),
2108
					ext4_ext_pblock(newext),
2109
					ext4_ext_is_unwritten(newext),
A
Amit Arora 已提交
2110
					ext4_ext_get_actual_len(newext),
2111 2112 2113 2114
					nearex);
		}
		len = EXT_LAST_EXTENT(eh) - nearex + 1;
		if (len > 0) {
2115
			ext_debug("insert %u:%llu:[%d]%d: "
2116 2117 2118
					"move %d extents from 0x%p to 0x%p\n",
					le32_to_cpu(newext->ee_block),
					ext4_ext_pblock(newext),
2119
					ext4_ext_is_unwritten(newext),
2120 2121 2122 2123
					ext4_ext_get_actual_len(newext),
					len, nearex, nearex + 1);
			memmove(nearex + 1, nearex,
				len * sizeof(struct ext4_extent));
A
Alex Tomas 已提交
2124 2125 2126
		}
	}

M
Marcin Slusarz 已提交
2127
	le16_add_cpu(&eh->eh_entries, 1);
2128
	path[depth].p_ext = nearex;
A
Alex Tomas 已提交
2129
	nearex->ee_block = newext->ee_block;
2130
	ext4_ext_store_pblock(nearex, ext4_ext_pblock(newext));
A
Alex Tomas 已提交
2131 2132 2133
	nearex->ee_len = newext->ee_len;

merge:
2134
	/* try to merge extents */
2135
	if (!(gb_flags & EXT4_GET_BLOCKS_PRE_IO))
2136
		ext4_ext_try_to_merge(handle, inode, path, nearex);
A
Alex Tomas 已提交
2137 2138 2139 2140 2141 2142 2143


	/* time to correct all indexes above */
	err = ext4_ext_correct_indexes(handle, inode, path);
	if (err)
		goto cleanup;

2144
	err = ext4_ext_dirty(handle, inode, path + path->p_depth);
A
Alex Tomas 已提交
2145 2146

cleanup:
2147 2148
	ext4_ext_drop_refs(npath);
	kfree(npath);
A
Alex Tomas 已提交
2149 2150 2151
	return err;
}

2152 2153 2154
static int ext4_fill_fiemap_extents(struct inode *inode,
				    ext4_lblk_t block, ext4_lblk_t num,
				    struct fiemap_extent_info *fieinfo)
2155 2156 2157
{
	struct ext4_ext_path *path = NULL;
	struct ext4_extent *ex;
Z
Zheng Liu 已提交
2158
	struct extent_status es;
2159
	ext4_lblk_t next, next_del, start = 0, end = 0;
2160
	ext4_lblk_t last = block + num;
2161 2162 2163
	int exists, depth = 0, err = 0;
	unsigned int flags = 0;
	unsigned char blksize_bits = inode->i_sb->s_blocksize_bits;
2164

2165
	while (block < last && block != EXT_MAX_BLOCKS) {
2166 2167
		num = last - block;
		/* find extent for this block */
2168
		down_read(&EXT4_I(inode)->i_data_sem);
2169

2170
		path = ext4_find_extent(inode, block, &path, 0);
2171
		if (IS_ERR(path)) {
2172
			up_read(&EXT4_I(inode)->i_data_sem);
2173 2174 2175 2176 2177 2178
			err = PTR_ERR(path);
			path = NULL;
			break;
		}

		depth = ext_depth(inode);
2179
		if (unlikely(path[depth].p_hdr == NULL)) {
2180
			up_read(&EXT4_I(inode)->i_data_sem);
2181
			EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
2182
			err = -EFSCORRUPTED;
2183 2184
			break;
		}
2185 2186 2187
		ex = path[depth].p_ext;
		next = ext4_ext_next_allocated_block(path);

2188
		flags = 0;
2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224
		exists = 0;
		if (!ex) {
			/* there is no extent yet, so try to allocate
			 * all requested space */
			start = block;
			end = block + num;
		} else if (le32_to_cpu(ex->ee_block) > block) {
			/* need to allocate space before found extent */
			start = block;
			end = le32_to_cpu(ex->ee_block);
			if (block + num < end)
				end = block + num;
		} else if (block >= le32_to_cpu(ex->ee_block)
					+ ext4_ext_get_actual_len(ex)) {
			/* need to allocate space after found extent */
			start = block;
			end = block + num;
			if (end >= next)
				end = next;
		} else if (block >= le32_to_cpu(ex->ee_block)) {
			/*
			 * some part of requested space is covered
			 * by found extent
			 */
			start = block;
			end = le32_to_cpu(ex->ee_block)
				+ ext4_ext_get_actual_len(ex);
			if (block + num < end)
				end = block + num;
			exists = 1;
		} else {
			BUG();
		}
		BUG_ON(end <= start);

		if (!exists) {
Z
Zheng Liu 已提交
2225 2226 2227
			es.es_lblk = start;
			es.es_len = end - start;
			es.es_pblk = 0;
2228
		} else {
Z
Zheng Liu 已提交
2229 2230 2231
			es.es_lblk = le32_to_cpu(ex->ee_block);
			es.es_len = ext4_ext_get_actual_len(ex);
			es.es_pblk = ext4_ext_pblock(ex);
2232
			if (ext4_ext_is_unwritten(ex))
2233
				flags |= FIEMAP_EXTENT_UNWRITTEN;
2234 2235
		}

2236
		/*
Z
Zheng Liu 已提交
2237 2238
		 * Find delayed extent and update es accordingly. We call
		 * it even in !exists case to find out whether es is the
2239 2240
		 * last existing extent or not.
		 */
Z
Zheng Liu 已提交
2241
		next_del = ext4_find_delayed_extent(inode, &es);
2242 2243
		if (!exists && next_del) {
			exists = 1;
2244 2245
			flags |= (FIEMAP_EXTENT_DELALLOC |
				  FIEMAP_EXTENT_UNKNOWN);
2246 2247 2248
		}
		up_read(&EXT4_I(inode)->i_data_sem);

Z
Zheng Liu 已提交
2249 2250
		if (unlikely(es.es_len == 0)) {
			EXT4_ERROR_INODE(inode, "es.es_len == 0");
2251
			err = -EFSCORRUPTED;
2252 2253
			break;
		}
2254

2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266
		/*
		 * This is possible iff next == next_del == EXT_MAX_BLOCKS.
		 * we need to check next == EXT_MAX_BLOCKS because it is
		 * possible that an extent is with unwritten and delayed
		 * status due to when an extent is delayed allocated and
		 * is allocated by fallocate status tree will track both of
		 * them in a extent.
		 *
		 * So we could return a unwritten and delayed extent, and
		 * its block is equal to 'next'.
		 */
		if (next == next_del && next == EXT_MAX_BLOCKS) {
2267 2268 2269 2270 2271 2272 2273
			flags |= FIEMAP_EXTENT_LAST;
			if (unlikely(next_del != EXT_MAX_BLOCKS ||
				     next != EXT_MAX_BLOCKS)) {
				EXT4_ERROR_INODE(inode,
						 "next extent == %u, next "
						 "delalloc extent = %u",
						 next, next_del);
2274
				err = -EFSCORRUPTED;
2275 2276
				break;
			}
2277 2278
		}

2279 2280
		if (exists) {
			err = fiemap_fill_next_extent(fieinfo,
Z
Zheng Liu 已提交
2281 2282 2283
				(__u64)es.es_lblk << blksize_bits,
				(__u64)es.es_pblk << blksize_bits,
				(__u64)es.es_len << blksize_bits,
2284 2285 2286 2287 2288 2289 2290
				flags);
			if (err < 0)
				break;
			if (err == 1) {
				err = 0;
				break;
			}
2291 2292
		}

Z
Zheng Liu 已提交
2293
		block = es.es_lblk + es.es_len;
2294 2295
	}

2296 2297
	ext4_ext_drop_refs(path);
	kfree(path);
2298 2299 2300
	return err;
}

A
Alex Tomas 已提交
2301
/*
2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312
 * ext4_ext_determine_hole - determine hole around given block
 * @inode:	inode we lookup in
 * @path:	path in extent tree to @lblk
 * @lblk:	pointer to logical block around which we want to determine hole
 *
 * Determine hole length (and start if easily possible) around given logical
 * block. We don't try too hard to find the beginning of the hole but @path
 * actually points to extent before @lblk, we provide it.
 *
 * The function returns the length of a hole starting at @lblk. We update @lblk
 * to the beginning of the hole if we managed to find it.
A
Alex Tomas 已提交
2313
 */
2314 2315 2316
static ext4_lblk_t ext4_ext_determine_hole(struct inode *inode,
					   struct ext4_ext_path *path,
					   ext4_lblk_t *lblk)
A
Alex Tomas 已提交
2317 2318 2319
{
	int depth = ext_depth(inode);
	struct ext4_extent *ex;
2320
	ext4_lblk_t len;
A
Alex Tomas 已提交
2321 2322 2323

	ex = path[depth].p_ext;
	if (ex == NULL) {
2324
		/* there is no extent yet, so gap is [0;-] */
2325
		*lblk = 0;
2326
		len = EXT_MAX_BLOCKS;
2327 2328 2329
	} else if (*lblk < le32_to_cpu(ex->ee_block)) {
		len = le32_to_cpu(ex->ee_block) - *lblk;
	} else if (*lblk >= le32_to_cpu(ex->ee_block)
A
Amit Arora 已提交
2330
			+ ext4_ext_get_actual_len(ex)) {
A
Aneesh Kumar K.V 已提交
2331 2332
		ext4_lblk_t next;

2333
		*lblk = le32_to_cpu(ex->ee_block) + ext4_ext_get_actual_len(ex);
A
Aneesh Kumar K.V 已提交
2334
		next = ext4_ext_next_allocated_block(path);
2335 2336
		BUG_ON(next == *lblk);
		len = next - *lblk;
A
Alex Tomas 已提交
2337 2338 2339
	} else {
		BUG();
	}
2340 2341
	return len;
}
A
Alex Tomas 已提交
2342

2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353
/*
 * ext4_ext_put_gap_in_cache:
 * calculate boundaries of the gap that the requested block fits into
 * and cache this gap
 */
static void
ext4_ext_put_gap_in_cache(struct inode *inode, ext4_lblk_t hole_start,
			  ext4_lblk_t hole_len)
{
	struct extent_status es;

2354 2355
	ext4_es_find_extent_range(inode, &ext4_es_is_delayed, hole_start,
				  hole_start + hole_len - 1, &es);
2356 2357
	if (es.es_len) {
		/* There's delayed extent containing lblock? */
2358
		if (es.es_lblk <= hole_start)
2359
			return;
2360
		hole_len = min(es.es_lblk - hole_start, hole_len);
2361
	}
2362 2363 2364
	ext_debug(" -> %u:%u\n", hole_start, hole_len);
	ext4_es_insert_extent(inode, hole_start, hole_len, ~0,
			      EXTENT_STATUS_HOLE);
A
Alex Tomas 已提交
2365 2366 2367
}

/*
2368 2369
 * ext4_ext_rm_idx:
 * removes index from the index block.
A
Alex Tomas 已提交
2370
 */
A
Aneesh Kumar K.V 已提交
2371
static int ext4_ext_rm_idx(handle_t *handle, struct inode *inode,
2372
			struct ext4_ext_path *path, int depth)
A
Alex Tomas 已提交
2373 2374
{
	int err;
2375
	ext4_fsblk_t leaf;
A
Alex Tomas 已提交
2376 2377

	/* free index block */
2378 2379
	depth--;
	path = path + depth;
2380
	leaf = ext4_idx_pblock(path->p_idx);
2381 2382
	if (unlikely(path->p_hdr->eh_entries == 0)) {
		EXT4_ERROR_INODE(inode, "path->p_hdr->eh_entries == 0");
2383
		return -EFSCORRUPTED;
2384
	}
2385 2386
	err = ext4_ext_get_access(handle, inode, path);
	if (err)
A
Alex Tomas 已提交
2387
		return err;
2388 2389 2390 2391 2392 2393 2394

	if (path->p_idx != EXT_LAST_INDEX(path->p_hdr)) {
		int len = EXT_LAST_INDEX(path->p_hdr) - path->p_idx;
		len *= sizeof(struct ext4_extent_idx);
		memmove(path->p_idx, path->p_idx + 1, len);
	}

M
Marcin Slusarz 已提交
2395
	le16_add_cpu(&path->p_hdr->eh_entries, -1);
2396 2397
	err = ext4_ext_dirty(handle, inode, path);
	if (err)
A
Alex Tomas 已提交
2398
		return err;
2399
	ext_debug("index is empty, remove it, free block %llu\n", leaf);
2400 2401
	trace_ext4_ext_rm_idx(inode, leaf);

2402
	ext4_free_blocks(handle, inode, NULL, leaf, 1,
2403
			 EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET);
2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416

	while (--depth >= 0) {
		if (path->p_idx != EXT_FIRST_INDEX(path->p_hdr))
			break;
		path--;
		err = ext4_ext_get_access(handle, inode, path);
		if (err)
			break;
		path->p_idx->ei_block = (path+1)->p_idx->ei_block;
		err = ext4_ext_dirty(handle, inode, path);
		if (err)
			break;
	}
A
Alex Tomas 已提交
2417 2418 2419 2420
	return err;
}

/*
2421 2422 2423 2424 2425
 * ext4_ext_calc_credits_for_single_extent:
 * This routine returns max. credits that needed to insert an extent
 * to the extent tree.
 * When pass the actual path, the caller should calculate credits
 * under i_data_sem.
A
Alex Tomas 已提交
2426
 */
2427
int ext4_ext_calc_credits_for_single_extent(struct inode *inode, int nrblocks,
A
Alex Tomas 已提交
2428 2429 2430
						struct ext4_ext_path *path)
{
	if (path) {
2431
		int depth = ext_depth(inode);
2432
		int ret = 0;
2433

A
Alex Tomas 已提交
2434 2435
		/* probably there is space in leaf? */
		if (le16_to_cpu(path[depth].p_hdr->eh_entries)
2436
				< le16_to_cpu(path[depth].p_hdr->eh_max)) {
A
Alex Tomas 已提交
2437

2438 2439 2440 2441 2442
			/*
			 *  There are some space in the leaf tree, no
			 *  need to account for leaf block credit
			 *
			 *  bitmaps and block group descriptor blocks
2443
			 *  and other metadata blocks still need to be
2444 2445
			 *  accounted.
			 */
2446
			/* 1 bitmap, 1 block group descriptor */
2447
			ret = 2 + EXT4_META_TRANS_BLOCKS(inode->i_sb);
2448
			return ret;
2449 2450
		}
	}
A
Alex Tomas 已提交
2451

2452
	return ext4_chunk_trans_blocks(inode, nrblocks);
2453
}
A
Alex Tomas 已提交
2454

2455
/*
2456
 * How many index/leaf blocks need to change/allocate to add @extents extents?
2457
 *
2458 2459
 * If we add a single extent, then in the worse case, each tree level
 * index/leaf need to be changed in case of the tree split.
2460
 *
2461 2462
 * If more extents are inserted, they could cause the whole tree split more
 * than once, but this is really rare.
2463
 */
2464
int ext4_ext_index_trans_blocks(struct inode *inode, int extents)
2465 2466
{
	int index;
2467 2468 2469 2470 2471 2472 2473
	int depth;

	/* If we are converting the inline data, only one is needed here. */
	if (ext4_has_inline_data(inode))
		return 1;

	depth = ext_depth(inode);
A
Alex Tomas 已提交
2474

2475
	if (extents <= 1)
2476 2477 2478
		index = depth * 2;
	else
		index = depth * 3;
A
Alex Tomas 已提交
2479

2480
	return index;
A
Alex Tomas 已提交
2481 2482
}

2483 2484
static inline int get_default_free_blocks_flags(struct inode *inode)
{
2485 2486
	if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode) ||
	    ext4_test_inode_flag(inode, EXT4_INODE_EA_INODE))
2487 2488 2489 2490 2491 2492
		return EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET;
	else if (ext4_should_journal_data(inode))
		return EXT4_FREE_BLOCKS_FORGET;
	return 0;
}

A
Alex Tomas 已提交
2493
static int ext4_remove_blocks(handle_t *handle, struct inode *inode,
2494
			      struct ext4_extent *ex,
2495
			      long long *partial_cluster,
2496
			      ext4_lblk_t from, ext4_lblk_t to)
A
Alex Tomas 已提交
2497
{
2498
	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2499
	unsigned short ee_len = ext4_ext_get_actual_len(ex);
2500
	ext4_fsblk_t pblk;
2501
	int flags = get_default_free_blocks_flags(inode);
2502

2503 2504 2505 2506 2507
	/*
	 * For bigalloc file systems, we never free a partial cluster
	 * at the beginning of the extent.  Instead, we make a note
	 * that we tried freeing the cluster, and check to see if we
	 * need to free it on a subsequent call to ext4_remove_blocks,
2508
	 * or at the end of ext4_ext_rm_leaf or ext4_ext_remove_space.
2509 2510 2511
	 */
	flags |= EXT4_FREE_BLOCKS_NOFREE_FIRST_CLUSTER;

2512
	trace_ext4_remove_blocks(inode, ex, from, to, *partial_cluster);
2513 2514 2515 2516 2517 2518
	/*
	 * If we have a partial cluster, and it's different from the
	 * cluster of the last block, we need to explicitly free the
	 * partial cluster here.
	 */
	pblk = ext4_ext_pblock(ex) + ee_len - 1;
2519 2520
	if (*partial_cluster > 0 &&
	    *partial_cluster != (long long) EXT4_B2C(sbi, pblk)) {
2521 2522 2523 2524 2525 2526
		ext4_free_blocks(handle, inode, NULL,
				 EXT4_C2B(sbi, *partial_cluster),
				 sbi->s_cluster_ratio, flags);
		*partial_cluster = 0;
	}

A
Alex Tomas 已提交
2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542
#ifdef EXTENTS_STATS
	{
		struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
		spin_lock(&sbi->s_ext_stats_lock);
		sbi->s_ext_blocks += ee_len;
		sbi->s_ext_extents++;
		if (ee_len < sbi->s_ext_min)
			sbi->s_ext_min = ee_len;
		if (ee_len > sbi->s_ext_max)
			sbi->s_ext_max = ee_len;
		if (ext_depth(inode) > sbi->s_depth_max)
			sbi->s_depth_max = ext_depth(inode);
		spin_unlock(&sbi->s_ext_stats_lock);
	}
#endif
	if (from >= le32_to_cpu(ex->ee_block)
A
Amit Arora 已提交
2543
	    && to == le32_to_cpu(ex->ee_block) + ee_len - 1) {
A
Alex Tomas 已提交
2544
		/* tail removal */
A
Aneesh Kumar K.V 已提交
2545
		ext4_lblk_t num;
2546
		long long first_cluster;
A
Aneesh Kumar K.V 已提交
2547

A
Amit Arora 已提交
2548
		num = le32_to_cpu(ex->ee_block) + ee_len - from;
2549
		pblk = ext4_ext_pblock(ex) + ee_len - num;
2550 2551 2552 2553 2554 2555
		/*
		 * Usually we want to free partial cluster at the end of the
		 * extent, except for the situation when the cluster is still
		 * used by any other extent (partial_cluster is negative).
		 */
		if (*partial_cluster < 0 &&
2556
		    *partial_cluster == -(long long) EXT4_B2C(sbi, pblk+num-1))
2557 2558 2559 2560
			flags |= EXT4_FREE_BLOCKS_NOFREE_LAST_CLUSTER;

		ext_debug("free last %u blocks starting %llu partial %lld\n",
			  num, pblk, *partial_cluster);
2561 2562 2563 2564
		ext4_free_blocks(handle, inode, NULL, pblk, num, flags);
		/*
		 * If the block range to be freed didn't start at the
		 * beginning of a cluster, and we removed the entire
2565 2566
		 * extent and the cluster is not used by any other extent,
		 * save the partial cluster here, since we might need to
2567 2568 2569 2570
		 * delete if we determine that the truncate or punch hole
		 * operation has removed all of the blocks in the cluster.
		 * If that cluster is used by another extent, preserve its
		 * negative value so it isn't freed later on.
2571
		 *
2572 2573 2574 2575 2576
		 * If the whole extent wasn't freed, we've reached the
		 * start of the truncated/punched region and have finished
		 * removing blocks.  If there's a partial cluster here it's
		 * shared with the remainder of the extent and is no longer
		 * a candidate for removal.
2577
		 */
2578 2579 2580 2581 2582
		if (EXT4_PBLK_COFF(sbi, pblk) && ee_len == num) {
			first_cluster = (long long) EXT4_B2C(sbi, pblk);
			if (first_cluster != -*partial_cluster)
				*partial_cluster = first_cluster;
		} else {
2583
			*partial_cluster = 0;
2584
		}
2585 2586
	} else
		ext4_error(sbi->s_sb, "strange request: removal(2) "
2587
			   "%u-%u from %u:%u",
2588
			   from, to, le32_to_cpu(ex->ee_block), ee_len);
A
Alex Tomas 已提交
2589 2590 2591
	return 0;
}

A
Allison Henderson 已提交
2592 2593 2594

/*
 * ext4_ext_rm_leaf() Removes the extents associated with the
2595 2596
 * blocks appearing between "start" and "end".  Both "start"
 * and "end" must appear in the same extent or EIO is returned.
A
Allison Henderson 已提交
2597 2598 2599 2600
 *
 * @handle: The journal handle
 * @inode:  The files inode
 * @path:   The path to the leaf
2601
 * @partial_cluster: The cluster which we'll have to free if all extents
2602 2603 2604
 *                   has been released from it.  However, if this value is
 *                   negative, it's a cluster just to the right of the
 *                   punched region and it must not be freed.
A
Allison Henderson 已提交
2605 2606 2607
 * @start:  The first block to remove
 * @end:   The last block to remove
 */
A
Alex Tomas 已提交
2608 2609
static int
ext4_ext_rm_leaf(handle_t *handle, struct inode *inode,
2610 2611
		 struct ext4_ext_path *path,
		 long long *partial_cluster,
2612
		 ext4_lblk_t start, ext4_lblk_t end)
A
Alex Tomas 已提交
2613
{
2614
	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
A
Alex Tomas 已提交
2615 2616 2617
	int err = 0, correct_index = 0;
	int depth = ext_depth(inode), credits;
	struct ext4_extent_header *eh;
2618
	ext4_lblk_t a, b;
A
Aneesh Kumar K.V 已提交
2619 2620
	unsigned num;
	ext4_lblk_t ex_ee_block;
A
Alex Tomas 已提交
2621
	unsigned short ex_ee_len;
2622
	unsigned unwritten = 0;
A
Alex Tomas 已提交
2623
	struct ext4_extent *ex;
2624
	ext4_fsblk_t pblk;
A
Alex Tomas 已提交
2625

2626
	/* the header must be checked already in ext4_ext_remove_space() */
2627
	ext_debug("truncate since %u in leaf to %u\n", start, end);
A
Alex Tomas 已提交
2628 2629 2630
	if (!path[depth].p_hdr)
		path[depth].p_hdr = ext_block_hdr(path[depth].p_bh);
	eh = path[depth].p_hdr;
2631 2632
	if (unlikely(path[depth].p_hdr == NULL)) {
		EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
2633
		return -EFSCORRUPTED;
2634
	}
A
Alex Tomas 已提交
2635
	/* find where to start removing */
2636 2637 2638
	ex = path[depth].p_ext;
	if (!ex)
		ex = EXT_LAST_EXTENT(eh);
A
Alex Tomas 已提交
2639 2640

	ex_ee_block = le32_to_cpu(ex->ee_block);
A
Amit Arora 已提交
2641
	ex_ee_len = ext4_ext_get_actual_len(ex);
A
Alex Tomas 已提交
2642

2643 2644
	trace_ext4_ext_rm_leaf(inode, start, ex, *partial_cluster);

A
Alex Tomas 已提交
2645 2646
	while (ex >= EXT_FIRST_EXTENT(eh) &&
			ex_ee_block + ex_ee_len > start) {
2647

2648 2649
		if (ext4_ext_is_unwritten(ex))
			unwritten = 1;
2650
		else
2651
			unwritten = 0;
2652

2653
		ext_debug("remove ext %u:[%d]%d\n", ex_ee_block,
2654
			  unwritten, ex_ee_len);
A
Alex Tomas 已提交
2655 2656 2657
		path[depth].p_ext = ex;

		a = ex_ee_block > start ? ex_ee_block : start;
A
Allison Henderson 已提交
2658 2659
		b = ex_ee_block+ex_ee_len - 1 < end ?
			ex_ee_block+ex_ee_len - 1 : end;
A
Alex Tomas 已提交
2660 2661 2662

		ext_debug("  border %u:%u\n", a, b);

A
Allison Henderson 已提交
2663
		/* If this extent is beyond the end of the hole, skip it */
2664
		if (end < ex_ee_block) {
2665 2666
			/*
			 * We're going to skip this extent and move to another,
2667 2668 2669 2670
			 * so note that its first cluster is in use to avoid
			 * freeing it when removing blocks.  Eventually, the
			 * right edge of the truncated/punched region will
			 * be just to the left.
2671
			 */
2672 2673
			if (sbi->s_cluster_ratio > 1) {
				pblk = ext4_ext_pblock(ex);
2674
				*partial_cluster =
2675 2676
					-(long long) EXT4_B2C(sbi, pblk);
			}
A
Allison Henderson 已提交
2677 2678 2679 2680
			ex--;
			ex_ee_block = le32_to_cpu(ex->ee_block);
			ex_ee_len = ext4_ext_get_actual_len(ex);
			continue;
2681
		} else if (b != ex_ee_block + ex_ee_len - 1) {
2682 2683 2684 2685 2686
			EXT4_ERROR_INODE(inode,
					 "can not handle truncate %u:%u "
					 "on extent %u:%u",
					 start, end, ex_ee_block,
					 ex_ee_block + ex_ee_len - 1);
2687
			err = -EFSCORRUPTED;
2688
			goto out;
A
Alex Tomas 已提交
2689 2690
		} else if (a != ex_ee_block) {
			/* remove tail of the extent */
2691
			num = a - ex_ee_block;
A
Alex Tomas 已提交
2692 2693 2694 2695
		} else {
			/* remove whole extent: excellent! */
			num = 0;
		}
2696 2697 2698 2699 2700 2701 2702
		/*
		 * 3 for leaf, sb, and inode plus 2 (bmap and group
		 * descriptor) for each block group; assume two block
		 * groups plus ex_ee_len/blocks_per_block_group for
		 * the worst case
		 */
		credits = 7 + 2*(ex_ee_len/EXT4_BLOCKS_PER_GROUP(inode->i_sb));
A
Alex Tomas 已提交
2703 2704 2705 2706
		if (ex == EXT_FIRST_EXTENT(eh)) {
			correct_index = 1;
			credits += (ext_depth(inode)) + 1;
		}
D
Dmitry Monakhov 已提交
2707
		credits += EXT4_MAXQUOTAS_TRANS_BLOCKS(inode->i_sb);
A
Alex Tomas 已提交
2708

2709
		err = ext4_ext_truncate_extend_restart(handle, inode, credits);
2710
		if (err)
A
Alex Tomas 已提交
2711 2712 2713 2714 2715 2716
			goto out;

		err = ext4_ext_get_access(handle, inode, path + depth);
		if (err)
			goto out;

2717 2718
		err = ext4_remove_blocks(handle, inode, ex, partial_cluster,
					 a, b);
A
Alex Tomas 已提交
2719 2720 2721
		if (err)
			goto out;

2722
		if (num == 0)
2723
			/* this extent is removed; mark slot entirely unused */
2724
			ext4_ext_store_pblock(ex, 0);
A
Alex Tomas 已提交
2725 2726

		ex->ee_len = cpu_to_le16(num);
2727
		/*
2728
		 * Do not mark unwritten if all the blocks in the
2729 2730
		 * extent have been removed.
		 */
2731 2732
		if (unwritten && num)
			ext4_ext_mark_unwritten(ex);
A
Allison Henderson 已提交
2733 2734 2735 2736 2737
		/*
		 * If the extent was completely released,
		 * we need to remove it from the leaf
		 */
		if (num == 0) {
2738
			if (end != EXT_MAX_BLOCKS - 1) {
A
Allison Henderson 已提交
2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749 2750 2751
				/*
				 * For hole punching, we need to scoot all the
				 * extents up when an extent is removed so that
				 * we dont have blank extents in the middle
				 */
				memmove(ex, ex+1, (EXT_LAST_EXTENT(eh) - ex) *
					sizeof(struct ext4_extent));

				/* Now get rid of the one at the end */
				memset(EXT_LAST_EXTENT(eh), 0,
					sizeof(struct ext4_extent));
			}
			le16_add_cpu(&eh->eh_entries, -1);
2752
		}
A
Allison Henderson 已提交
2753

2754 2755 2756 2757
		err = ext4_ext_dirty(handle, inode, path + depth);
		if (err)
			goto out;

2758
		ext_debug("new extent: %u:%u:%llu\n", ex_ee_block, num,
2759
				ext4_ext_pblock(ex));
A
Alex Tomas 已提交
2760 2761
		ex--;
		ex_ee_block = le32_to_cpu(ex->ee_block);
A
Amit Arora 已提交
2762
		ex_ee_len = ext4_ext_get_actual_len(ex);
A
Alex Tomas 已提交
2763 2764 2765 2766 2767
	}

	if (correct_index && eh->eh_entries)
		err = ext4_ext_correct_indexes(handle, inode, path);

2768
	/*
2769 2770
	 * If there's a partial cluster and at least one extent remains in
	 * the leaf, free the partial cluster if it isn't shared with the
2771 2772 2773
	 * current extent.  If it is shared with the current extent
	 * we zero partial_cluster because we've reached the start of the
	 * truncated/punched region and we're done removing blocks.
2774
	 */
2775 2776 2777 2778 2779 2780 2781 2782
	if (*partial_cluster > 0 && ex >= EXT_FIRST_EXTENT(eh)) {
		pblk = ext4_ext_pblock(ex) + ex_ee_len - 1;
		if (*partial_cluster != (long long) EXT4_B2C(sbi, pblk)) {
			ext4_free_blocks(handle, inode, NULL,
					 EXT4_C2B(sbi, *partial_cluster),
					 sbi->s_cluster_ratio,
					 get_default_free_blocks_flags(inode));
		}
2783 2784 2785
		*partial_cluster = 0;
	}

A
Alex Tomas 已提交
2786 2787 2788
	/* if this leaf is free, then we should
	 * remove it from index block above */
	if (err == 0 && eh->eh_entries == 0 && path[depth].p_bh != NULL)
2789
		err = ext4_ext_rm_idx(handle, inode, path, depth);
A
Alex Tomas 已提交
2790 2791 2792 2793 2794 2795

out:
	return err;
}

/*
2796 2797
 * ext4_ext_more_to_rm:
 * returns 1 if current index has to be freed (even partial)
A
Alex Tomas 已提交
2798
 */
2799
static int
A
Alex Tomas 已提交
2800 2801 2802 2803 2804 2805 2806 2807
ext4_ext_more_to_rm(struct ext4_ext_path *path)
{
	BUG_ON(path->p_idx == NULL);

	if (path->p_idx < EXT_FIRST_INDEX(path->p_hdr))
		return 0;

	/*
2808
	 * if truncate on deeper level happened, it wasn't partial,
A
Alex Tomas 已提交
2809 2810 2811 2812 2813 2814 2815
	 * so we have to consider current index for truncation
	 */
	if (le16_to_cpu(path->p_hdr->eh_entries) == path->p_block)
		return 0;
	return 1;
}

T
Theodore Ts'o 已提交
2816 2817
int ext4_ext_remove_space(struct inode *inode, ext4_lblk_t start,
			  ext4_lblk_t end)
A
Alex Tomas 已提交
2818
{
2819
	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
A
Alex Tomas 已提交
2820
	int depth = ext_depth(inode);
2821
	struct ext4_ext_path *path = NULL;
2822
	long long partial_cluster = 0;
A
Alex Tomas 已提交
2823
	handle_t *handle;
2824
	int i = 0, err = 0;
A
Alex Tomas 已提交
2825

2826
	ext_debug("truncate since %u to %u\n", start, end);
A
Alex Tomas 已提交
2827 2828

	/* probably first extent we're gonna free will be last in block */
2829
	handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, depth + 1);
A
Alex Tomas 已提交
2830 2831 2832
	if (IS_ERR(handle))
		return PTR_ERR(handle);

2833
again:
2834
	trace_ext4_ext_remove_space(inode, start, end, depth);
2835

2836 2837 2838 2839 2840 2841 2842 2843 2844
	/*
	 * Check if we are removing extents inside the extent tree. If that
	 * is the case, we are going to punch a hole inside the extent tree
	 * so we have to check whether we need to split the extent covering
	 * the last block to remove so we can easily remove the part of it
	 * in ext4_ext_rm_leaf().
	 */
	if (end < EXT_MAX_BLOCKS - 1) {
		struct ext4_extent *ex;
2845 2846
		ext4_lblk_t ee_block, ex_end, lblk;
		ext4_fsblk_t pblk;
2847

2848
		/* find extent for or closest extent to this block */
2849
		path = ext4_find_extent(inode, end, NULL, EXT4_EX_NOCACHE);
2850 2851 2852 2853 2854
		if (IS_ERR(path)) {
			ext4_journal_stop(handle);
			return PTR_ERR(path);
		}
		depth = ext_depth(inode);
2855
		/* Leaf not may not exist only if inode has no blocks at all */
2856
		ex = path[depth].p_ext;
2857
		if (!ex) {
2858 2859 2860 2861
			if (depth) {
				EXT4_ERROR_INODE(inode,
						 "path[%d].p_hdr == NULL",
						 depth);
2862
				err = -EFSCORRUPTED;
2863 2864
			}
			goto out;
2865
		}
2866 2867

		ee_block = le32_to_cpu(ex->ee_block);
2868
		ex_end = ee_block + ext4_ext_get_actual_len(ex) - 1;
2869 2870 2871 2872 2873 2874 2875

		/*
		 * See if the last block is inside the extent, if so split
		 * the extent at 'end' block so we can easily remove the
		 * tail of the first part of the split extent in
		 * ext4_ext_rm_leaf().
		 */
2876 2877 2878 2879 2880 2881 2882 2883 2884 2885 2886 2887 2888
		if (end >= ee_block && end < ex_end) {

			/*
			 * If we're going to split the extent, note that
			 * the cluster containing the block after 'end' is
			 * in use to avoid freeing it when removing blocks.
			 */
			if (sbi->s_cluster_ratio > 1) {
				pblk = ext4_ext_pblock(ex) + end - ee_block + 2;
				partial_cluster =
					-(long long) EXT4_B2C(sbi, pblk);
			}

2889 2890
			/*
			 * Split the extent in two so that 'end' is the last
L
Lukas Czerner 已提交
2891 2892 2893
			 * block in the first new extent. Also we should not
			 * fail removing space due to ENOSPC so try to use
			 * reserved block if that happens.
2894
			 */
2895
			err = ext4_force_split_extent_at(handle, inode, &path,
2896
							 end + 1, 1);
2897 2898
			if (err < 0)
				goto out;
2899 2900 2901 2902 2903 2904 2905 2906 2907 2908 2909 2910 2911 2912 2913 2914 2915 2916

		} else if (sbi->s_cluster_ratio > 1 && end >= ex_end) {
			/*
			 * If there's an extent to the right its first cluster
			 * contains the immediate right boundary of the
			 * truncated/punched region.  Set partial_cluster to
			 * its negative value so it won't be freed if shared
			 * with the current extent.  The end < ee_block case
			 * is handled in ext4_ext_rm_leaf().
			 */
			lblk = ex_end + 1;
			err = ext4_ext_search_right(inode, path, &lblk, &pblk,
						    &ex);
			if (err)
				goto out;
			if (pblk)
				partial_cluster =
					-(long long) EXT4_B2C(sbi, pblk);
2917 2918
		}
	}
A
Alex Tomas 已提交
2919
	/*
2920 2921
	 * We start scanning from right side, freeing all the blocks
	 * after i_size and walking into the tree depth-wise.
A
Alex Tomas 已提交
2922
	 */
2923
	depth = ext_depth(inode);
2924 2925 2926 2927 2928 2929
	if (path) {
		int k = i = depth;
		while (--k > 0)
			path[k].p_block =
				le16_to_cpu(path[k].p_hdr->eh_entries)+1;
	} else {
K
Kees Cook 已提交
2930
		path = kcalloc(depth + 1, sizeof(struct ext4_ext_path),
2931 2932 2933 2934 2935
			       GFP_NOFS);
		if (path == NULL) {
			ext4_journal_stop(handle);
			return -ENOMEM;
		}
2936
		path[0].p_maxdepth = path[0].p_depth = depth;
2937
		path[0].p_hdr = ext_inode_hdr(inode);
2938
		i = 0;
2939

2940
		if (ext4_ext_check(inode, path[0].p_hdr, depth, 0)) {
2941
			err = -EFSCORRUPTED;
2942 2943
			goto out;
		}
A
Alex Tomas 已提交
2944
	}
2945
	err = 0;
A
Alex Tomas 已提交
2946 2947 2948 2949

	while (i >= 0 && err == 0) {
		if (i == depth) {
			/* this is leaf block */
A
Allison Henderson 已提交
2950
			err = ext4_ext_rm_leaf(handle, inode, path,
2951
					       &partial_cluster, start,
2952
					       end);
2953
			/* root level has p_bh == NULL, brelse() eats this */
A
Alex Tomas 已提交
2954 2955 2956 2957 2958 2959 2960 2961 2962 2963 2964 2965 2966
			brelse(path[i].p_bh);
			path[i].p_bh = NULL;
			i--;
			continue;
		}

		/* this is index block */
		if (!path[i].p_hdr) {
			ext_debug("initialize header\n");
			path[i].p_hdr = ext_block_hdr(path[i].p_bh);
		}

		if (!path[i].p_idx) {
2967
			/* this level hasn't been touched yet */
A
Alex Tomas 已提交
2968 2969 2970 2971 2972 2973
			path[i].p_idx = EXT_LAST_INDEX(path[i].p_hdr);
			path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries)+1;
			ext_debug("init index ptr: hdr 0x%p, num %d\n",
				  path[i].p_hdr,
				  le16_to_cpu(path[i].p_hdr->eh_entries));
		} else {
2974
			/* we were already here, see at next index */
A
Alex Tomas 已提交
2975 2976 2977 2978 2979 2980 2981
			path[i].p_idx--;
		}

		ext_debug("level %d - index, first 0x%p, cur 0x%p\n",
				i, EXT_FIRST_INDEX(path[i].p_hdr),
				path[i].p_idx);
		if (ext4_ext_more_to_rm(path + i)) {
2982
			struct buffer_head *bh;
A
Alex Tomas 已提交
2983
			/* go to the next level */
2984
			ext_debug("move to level %d (block %llu)\n",
2985
				  i + 1, ext4_idx_pblock(path[i].p_idx));
A
Alex Tomas 已提交
2986
			memset(path + i + 1, 0, sizeof(*path));
2987
			bh = read_extent_tree_block(inode,
2988 2989
				ext4_idx_pblock(path[i].p_idx), depth - i - 1,
				EXT4_EX_NOCACHE);
2990
			if (IS_ERR(bh)) {
A
Alex Tomas 已提交
2991
				/* should we reset i_size? */
2992
				err = PTR_ERR(bh);
A
Alex Tomas 已提交
2993 2994
				break;
			}
T
Theodore Ts'o 已提交
2995 2996 2997
			/* Yield here to deal with large extent trees.
			 * Should be a no-op if we did IO above. */
			cond_resched();
2998
			if (WARN_ON(i + 1 > depth)) {
2999
				err = -EFSCORRUPTED;
3000 3001 3002
				break;
			}
			path[i + 1].p_bh = bh;
A
Alex Tomas 已提交
3003

3004 3005
			/* save actual number of indexes since this
			 * number is changed at the next iteration */
A
Alex Tomas 已提交
3006 3007 3008
			path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries);
			i++;
		} else {
3009
			/* we finished processing this index, go up */
A
Alex Tomas 已提交
3010
			if (path[i].p_hdr->eh_entries == 0 && i > 0) {
3011
				/* index is empty, remove it;
A
Alex Tomas 已提交
3012 3013
				 * handle must be already prepared by the
				 * truncatei_leaf() */
3014
				err = ext4_ext_rm_idx(handle, inode, path, i);
A
Alex Tomas 已提交
3015
			}
3016
			/* root level has p_bh == NULL, brelse() eats this */
A
Alex Tomas 已提交
3017 3018 3019 3020 3021 3022 3023
			brelse(path[i].p_bh);
			path[i].p_bh = NULL;
			i--;
			ext_debug("return to level %d\n", i);
		}
	}

3024 3025
	trace_ext4_ext_remove_space_done(inode, start, end, depth,
			partial_cluster, path->p_hdr->eh_entries);
3026

3027 3028
	/*
	 * If we still have something in the partial cluster and we have removed
3029
	 * even the first extent, then we should free the blocks in the partial
3030 3031 3032 3033 3034
	 * cluster as well.  (This code will only run when there are no leaves
	 * to the immediate left of the truncated/punched region.)
	 */
	if (partial_cluster > 0 && err == 0) {
		/* don't zero partial_cluster since it's not used afterwards */
3035
		ext4_free_blocks(handle, inode, NULL,
3036
				 EXT4_C2B(sbi, partial_cluster),
3037 3038
				 sbi->s_cluster_ratio,
				 get_default_free_blocks_flags(inode));
3039 3040
	}

A
Alex Tomas 已提交
3041 3042 3043
	/* TODO: flexible tree reduction should be here */
	if (path->p_hdr->eh_entries == 0) {
		/*
3044 3045
		 * truncate to zero freed all the tree,
		 * so we need to correct eh_depth
A
Alex Tomas 已提交
3046 3047 3048 3049 3050
		 */
		err = ext4_ext_get_access(handle, inode, path);
		if (err == 0) {
			ext_inode_hdr(inode)->eh_depth = 0;
			ext_inode_hdr(inode)->eh_max =
3051
				cpu_to_le16(ext4_ext_space_root(inode, 0));
A
Alex Tomas 已提交
3052 3053 3054 3055
			err = ext4_ext_dirty(handle, inode, path);
		}
	}
out:
3056 3057 3058
	ext4_ext_drop_refs(path);
	kfree(path);
	path = NULL;
3059 3060
	if (err == -EAGAIN)
		goto again;
A
Alex Tomas 已提交
3061 3062 3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073 3074
	ext4_journal_stop(handle);

	return err;
}

/*
 * called at mount time
 */
void ext4_ext_init(struct super_block *sb)
{
	/*
	 * possible initialization would be here
	 */

3075
	if (ext4_has_feature_extents(sb)) {
3076
#if defined(AGGRESSIVE_TEST) || defined(CHECK_BINSEARCH) || defined(EXTENTS_STATS)
3077
		printk(KERN_INFO "EXT4-fs: file extents enabled"
3078
#ifdef AGGRESSIVE_TEST
3079
		       ", aggressive tests"
A
Alex Tomas 已提交
3080 3081
#endif
#ifdef CHECK_BINSEARCH
3082
		       ", check binsearch"
A
Alex Tomas 已提交
3083 3084
#endif
#ifdef EXTENTS_STATS
3085
		       ", stats"
A
Alex Tomas 已提交
3086
#endif
3087
		       "\n");
3088
#endif
A
Alex Tomas 已提交
3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101
#ifdef EXTENTS_STATS
		spin_lock_init(&EXT4_SB(sb)->s_ext_stats_lock);
		EXT4_SB(sb)->s_ext_min = 1 << 30;
		EXT4_SB(sb)->s_ext_max = 0;
#endif
	}
}

/*
 * called at umount time
 */
void ext4_ext_release(struct super_block *sb)
{
3102
	if (!ext4_has_feature_extents(sb))
A
Alex Tomas 已提交
3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 3115 3116
		return;

#ifdef EXTENTS_STATS
	if (EXT4_SB(sb)->s_ext_blocks && EXT4_SB(sb)->s_ext_extents) {
		struct ext4_sb_info *sbi = EXT4_SB(sb);
		printk(KERN_ERR "EXT4-fs: %lu blocks in %lu extents (%lu ave)\n",
			sbi->s_ext_blocks, sbi->s_ext_extents,
			sbi->s_ext_blocks / sbi->s_ext_extents);
		printk(KERN_ERR "EXT4-fs: extents: %lu min, %lu max, max depth %lu\n",
			sbi->s_ext_min, sbi->s_ext_max, sbi->s_depth_max);
	}
#endif
}

Z
Zheng Liu 已提交
3117 3118 3119 3120 3121 3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132 3133
static int ext4_zeroout_es(struct inode *inode, struct ext4_extent *ex)
{
	ext4_lblk_t  ee_block;
	ext4_fsblk_t ee_pblock;
	unsigned int ee_len;

	ee_block  = le32_to_cpu(ex->ee_block);
	ee_len    = ext4_ext_get_actual_len(ex);
	ee_pblock = ext4_ext_pblock(ex);

	if (ee_len == 0)
		return 0;

	return ext4_es_insert_extent(inode, ee_block, ee_len, ee_pblock,
				     EXTENT_STATUS_WRITTEN);
}

3134 3135 3136
/* FIXME!! we need to try to merge to left or right after zero-out  */
static int ext4_ext_zeroout(struct inode *inode, struct ext4_extent *ex)
{
3137 3138
	ext4_fsblk_t ee_pblock;
	unsigned int ee_len;
3139 3140

	ee_len    = ext4_ext_get_actual_len(ex);
3141
	ee_pblock = ext4_ext_pblock(ex);
J
Jan Kara 已提交
3142 3143
	return ext4_issue_zeroout(inode, le32_to_cpu(ex->ee_block), ee_pblock,
				  ee_len);
3144 3145
}

3146 3147 3148 3149 3150 3151 3152 3153
/*
 * ext4_split_extent_at() splits an extent at given block.
 *
 * @handle: the journal handle
 * @inode: the file inode
 * @path: the path to the extent
 * @split: the logical block where the extent is splitted.
 * @split_flags: indicates if the extent could be zeroout if split fails, and
3154
 *		 the states(init or unwritten) of new extents.
3155 3156 3157 3158 3159 3160 3161 3162 3163 3164 3165 3166 3167 3168
 * @flags: flags used to insert new extent to extent tree.
 *
 *
 * Splits extent [a, b] into two extents [a, @split) and [@split, b], states
 * of which are deterimined by split_flag.
 *
 * There are two cases:
 *  a> the extent are splitted into two extent.
 *  b> split is not needed, and just mark the extent.
 *
 * return 0 on success.
 */
static int ext4_split_extent_at(handle_t *handle,
			     struct inode *inode,
3169
			     struct ext4_ext_path **ppath,
3170 3171 3172 3173
			     ext4_lblk_t split,
			     int split_flag,
			     int flags)
{
3174
	struct ext4_ext_path *path = *ppath;
3175 3176
	ext4_fsblk_t newblock;
	ext4_lblk_t ee_block;
3177
	struct ext4_extent *ex, newex, orig_ex, zero_ex;
3178 3179 3180 3181
	struct ext4_extent *ex2 = NULL;
	unsigned int ee_len, depth;
	int err = 0;

3182 3183 3184
	BUG_ON((split_flag & (EXT4_EXT_DATA_VALID1 | EXT4_EXT_DATA_VALID2)) ==
	       (EXT4_EXT_DATA_VALID1 | EXT4_EXT_DATA_VALID2));

3185 3186 3187 3188 3189 3190 3191 3192 3193 3194 3195 3196
	ext_debug("ext4_split_extents_at: inode %lu, logical"
		"block %llu\n", inode->i_ino, (unsigned long long)split);

	ext4_ext_show_leaf(inode, path);

	depth = ext_depth(inode);
	ex = path[depth].p_ext;
	ee_block = le32_to_cpu(ex->ee_block);
	ee_len = ext4_ext_get_actual_len(ex);
	newblock = split - ee_block + ext4_ext_pblock(ex);

	BUG_ON(split < ee_block || split >= (ee_block + ee_len));
3197
	BUG_ON(!ext4_ext_is_unwritten(ex) &&
3198
	       split_flag & (EXT4_EXT_MAY_ZEROOUT |
3199 3200
			     EXT4_EXT_MARK_UNWRIT1 |
			     EXT4_EXT_MARK_UNWRIT2));
3201 3202 3203 3204 3205 3206 3207 3208 3209 3210 3211

	err = ext4_ext_get_access(handle, inode, path + depth);
	if (err)
		goto out;

	if (split == ee_block) {
		/*
		 * case b: block @split is the block that the extent begins with
		 * then we just change the state of the extent, and splitting
		 * is not needed.
		 */
3212 3213
		if (split_flag & EXT4_EXT_MARK_UNWRIT2)
			ext4_ext_mark_unwritten(ex);
3214 3215 3216 3217
		else
			ext4_ext_mark_initialized(ex);

		if (!(flags & EXT4_GET_BLOCKS_PRE_IO))
3218
			ext4_ext_try_to_merge(handle, inode, path, ex);
3219

3220
		err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3221 3222 3223 3224 3225 3226
		goto out;
	}

	/* case a */
	memcpy(&orig_ex, ex, sizeof(orig_ex));
	ex->ee_len = cpu_to_le16(split - ee_block);
3227 3228
	if (split_flag & EXT4_EXT_MARK_UNWRIT1)
		ext4_ext_mark_unwritten(ex);
3229 3230 3231 3232 3233 3234 3235 3236 3237 3238 3239 3240 3241

	/*
	 * path may lead to new leaf, not to original leaf any more
	 * after ext4_ext_insert_extent() returns,
	 */
	err = ext4_ext_dirty(handle, inode, path + depth);
	if (err)
		goto fix_extent_len;

	ex2 = &newex;
	ex2->ee_block = cpu_to_le32(split);
	ex2->ee_len   = cpu_to_le16(ee_len - (split - ee_block));
	ext4_ext_store_pblock(ex2, newblock);
3242 3243
	if (split_flag & EXT4_EXT_MARK_UNWRIT2)
		ext4_ext_mark_unwritten(ex2);
3244

3245
	err = ext4_ext_insert_extent(handle, inode, ppath, &newex, flags);
3246
	if (err == -ENOSPC && (EXT4_EXT_MAY_ZEROOUT & split_flag)) {
3247
		if (split_flag & (EXT4_EXT_DATA_VALID1|EXT4_EXT_DATA_VALID2)) {
3248
			if (split_flag & EXT4_EXT_DATA_VALID1) {
3249
				err = ext4_ext_zeroout(inode, ex2);
3250
				zero_ex.ee_block = ex2->ee_block;
3251 3252
				zero_ex.ee_len = cpu_to_le16(
						ext4_ext_get_actual_len(ex2));
3253 3254 3255
				ext4_ext_store_pblock(&zero_ex,
						      ext4_ext_pblock(ex2));
			} else {
3256
				err = ext4_ext_zeroout(inode, ex);
3257
				zero_ex.ee_block = ex->ee_block;
3258 3259
				zero_ex.ee_len = cpu_to_le16(
						ext4_ext_get_actual_len(ex));
3260 3261 3262 3263
				ext4_ext_store_pblock(&zero_ex,
						      ext4_ext_pblock(ex));
			}
		} else {
3264
			err = ext4_ext_zeroout(inode, &orig_ex);
3265
			zero_ex.ee_block = orig_ex.ee_block;
3266 3267
			zero_ex.ee_len = cpu_to_le16(
						ext4_ext_get_actual_len(&orig_ex));
3268 3269 3270
			ext4_ext_store_pblock(&zero_ex,
					      ext4_ext_pblock(&orig_ex));
		}
3271

3272 3273 3274
		if (err)
			goto fix_extent_len;
		/* update the extent length and mark as initialized */
3275
		ex->ee_len = cpu_to_le16(ee_len);
3276 3277
		ext4_ext_try_to_merge(handle, inode, path, ex);
		err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3278 3279 3280 3281
		if (err)
			goto fix_extent_len;

		/* update extent status tree */
Z
Zheng Liu 已提交
3282
		err = ext4_zeroout_es(inode, &zero_ex);
3283

3284 3285 3286 3287 3288 3289 3290 3291 3292 3293
		goto out;
	} else if (err)
		goto fix_extent_len;

out:
	ext4_ext_show_leaf(inode, path);
	return err;

fix_extent_len:
	ex->ee_len = orig_ex.ee_len;
D
Dmitry Monakhov 已提交
3294
	ext4_ext_dirty(handle, inode, path + path->p_depth);
3295 3296 3297 3298 3299 3300 3301
	return err;
}

/*
 * ext4_split_extents() splits an extent and mark extent which is covered
 * by @map as split_flags indicates
 *
3302
 * It may result in splitting the extent into multiple extents (up to three)
3303 3304 3305 3306 3307 3308 3309 3310
 * There are three possibilities:
 *   a> There is no split required
 *   b> Splits in two extents: Split is happening at either end of the extent
 *   c> Splits in three extents: Somone is splitting in middle of the extent
 *
 */
static int ext4_split_extent(handle_t *handle,
			      struct inode *inode,
3311
			      struct ext4_ext_path **ppath,
3312 3313 3314 3315
			      struct ext4_map_blocks *map,
			      int split_flag,
			      int flags)
{
3316
	struct ext4_ext_path *path = *ppath;
3317 3318 3319 3320
	ext4_lblk_t ee_block;
	struct ext4_extent *ex;
	unsigned int ee_len, depth;
	int err = 0;
3321
	int unwritten;
3322
	int split_flag1, flags1;
3323
	int allocated = map->m_len;
3324 3325 3326 3327 3328

	depth = ext_depth(inode);
	ex = path[depth].p_ext;
	ee_block = le32_to_cpu(ex->ee_block);
	ee_len = ext4_ext_get_actual_len(ex);
3329
	unwritten = ext4_ext_is_unwritten(ex);
3330 3331

	if (map->m_lblk + map->m_len < ee_block + ee_len) {
3332
		split_flag1 = split_flag & EXT4_EXT_MAY_ZEROOUT;
3333
		flags1 = flags | EXT4_GET_BLOCKS_PRE_IO;
3334 3335 3336
		if (unwritten)
			split_flag1 |= EXT4_EXT_MARK_UNWRIT1 |
				       EXT4_EXT_MARK_UNWRIT2;
3337 3338
		if (split_flag & EXT4_EXT_DATA_VALID2)
			split_flag1 |= EXT4_EXT_DATA_VALID1;
3339
		err = ext4_split_extent_at(handle, inode, ppath,
3340
				map->m_lblk + map->m_len, split_flag1, flags1);
3341 3342
		if (err)
			goto out;
3343 3344
	} else {
		allocated = ee_len - (map->m_lblk - ee_block);
3345
	}
3346 3347 3348 3349
	/*
	 * Update path is required because previous ext4_split_extent_at() may
	 * result in split of original leaf or extent zeroout.
	 */
3350
	path = ext4_find_extent(inode, map->m_lblk, ppath, 0);
3351 3352
	if (IS_ERR(path))
		return PTR_ERR(path);
3353 3354
	depth = ext_depth(inode);
	ex = path[depth].p_ext;
3355 3356 3357
	if (!ex) {
		EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
				 (unsigned long) map->m_lblk);
3358
		return -EFSCORRUPTED;
3359
	}
3360
	unwritten = ext4_ext_is_unwritten(ex);
3361
	split_flag1 = 0;
3362 3363

	if (map->m_lblk >= ee_block) {
3364
		split_flag1 = split_flag & EXT4_EXT_DATA_VALID2;
3365 3366
		if (unwritten) {
			split_flag1 |= EXT4_EXT_MARK_UNWRIT1;
3367
			split_flag1 |= split_flag & (EXT4_EXT_MAY_ZEROOUT |
3368
						     EXT4_EXT_MARK_UNWRIT2);
3369
		}
3370
		err = ext4_split_extent_at(handle, inode, ppath,
3371 3372 3373 3374 3375 3376 3377
				map->m_lblk, split_flag1, flags);
		if (err)
			goto out;
	}

	ext4_ext_show_leaf(inode, path);
out:
3378
	return err ? err : allocated;
3379 3380
}

3381
/*
3382
 * This function is called by ext4_ext_map_blocks() if someone tries to write
3383
 * to an unwritten extent. It may result in splitting the unwritten
L
Lucas De Marchi 已提交
3384
 * extent into multiple extents (up to three - one initialized and two
3385
 * unwritten).
3386 3387 3388 3389
 * There are three possibilities:
 *   a> There is no split required: Entire extent should be initialized
 *   b> Splits in two extents: Write is happening at either end of the extent
 *   c> Splits in three extents: Somone is writing in middle of the extent
3390 3391
 *
 * Pre-conditions:
3392
 *  - The extent pointed to by 'path' is unwritten.
3393 3394 3395 3396 3397 3398 3399
 *  - The extent pointed to by 'path' contains a superset
 *    of the logical span [map->m_lblk, map->m_lblk + map->m_len).
 *
 * Post-conditions on success:
 *  - the returned value is the number of blocks beyond map->l_lblk
 *    that are allocated and initialized.
 *    It is guaranteed to be >= map->m_len.
3400
 */
A
Aneesh Kumar K.V 已提交
3401
static int ext4_ext_convert_to_initialized(handle_t *handle,
3402 3403
					   struct inode *inode,
					   struct ext4_map_blocks *map,
3404
					   struct ext4_ext_path **ppath,
L
Lukas Czerner 已提交
3405
					   int flags)
3406
{
3407
	struct ext4_ext_path *path = *ppath;
3408
	struct ext4_sb_info *sbi;
3409
	struct ext4_extent_header *eh;
3410
	struct ext4_map_blocks split_map;
3411
	struct ext4_extent zero_ex1, zero_ex2;
3412
	struct ext4_extent *ex, *abut_ex;
3413
	ext4_lblk_t ee_block, eof_block;
3414 3415
	unsigned int ee_len, depth, map_len = map->m_len;
	int allocated = 0, max_zeroout = 0;
3416
	int err = 0;
3417
	int split_flag = EXT4_EXT_DATA_VALID2;
3418 3419 3420

	ext_debug("ext4_ext_convert_to_initialized: inode %lu, logical"
		"block %llu, max_blocks %u\n", inode->i_ino,
3421
		(unsigned long long)map->m_lblk, map_len);
3422

3423
	sbi = EXT4_SB(inode->i_sb);
3424 3425
	eof_block = (inode->i_size + inode->i_sb->s_blocksize - 1) >>
		inode->i_sb->s_blocksize_bits;
3426 3427
	if (eof_block < map->m_lblk + map_len)
		eof_block = map->m_lblk + map_len;
3428 3429

	depth = ext_depth(inode);
3430
	eh = path[depth].p_hdr;
3431 3432 3433
	ex = path[depth].p_ext;
	ee_block = le32_to_cpu(ex->ee_block);
	ee_len = ext4_ext_get_actual_len(ex);
3434 3435
	zero_ex1.ee_len = 0;
	zero_ex2.ee_len = 0;
3436

3437 3438 3439
	trace_ext4_ext_convert_to_initialized_enter(inode, map, ex);

	/* Pre-conditions */
3440
	BUG_ON(!ext4_ext_is_unwritten(ex));
3441 3442 3443 3444
	BUG_ON(!in_range(map->m_lblk, ee_block, ee_len));

	/*
	 * Attempt to transfer newly initialized blocks from the currently
3445
	 * unwritten extent to its neighbor. This is much cheaper
3446
	 * than an insertion followed by a merge as those involve costly
3447 3448 3449
	 * memmove() calls. Transferring to the left is the common case in
	 * steady state for workloads doing fallocate(FALLOC_FL_KEEP_SIZE)
	 * followed by append writes.
3450 3451
	 *
	 * Limitations of the current logic:
3452
	 *  - L1: we do not deal with writes covering the whole extent.
3453 3454
	 *    This would require removing the extent if the transfer
	 *    is possible.
3455
	 *  - L2: we only attempt to merge with an extent stored in the
3456 3457
	 *    same extent tree node.
	 */
3458 3459 3460 3461
	if ((map->m_lblk == ee_block) &&
		/* See if we can merge left */
		(map_len < ee_len) &&		/*L1*/
		(ex > EXT_FIRST_EXTENT(eh))) {	/*L2*/
3462 3463
		ext4_lblk_t prev_lblk;
		ext4_fsblk_t prev_pblk, ee_pblk;
3464
		unsigned int prev_len;
3465

3466 3467 3468 3469
		abut_ex = ex - 1;
		prev_lblk = le32_to_cpu(abut_ex->ee_block);
		prev_len = ext4_ext_get_actual_len(abut_ex);
		prev_pblk = ext4_ext_pblock(abut_ex);
3470 3471 3472
		ee_pblk = ext4_ext_pblock(ex);

		/*
3473
		 * A transfer of blocks from 'ex' to 'abut_ex' is allowed
3474
		 * upon those conditions:
3475 3476 3477 3478
		 * - C1: abut_ex is initialized,
		 * - C2: abut_ex is logically abutting ex,
		 * - C3: abut_ex is physically abutting ex,
		 * - C4: abut_ex can receive the additional blocks without
3479 3480
		 *   overflowing the (initialized) length limit.
		 */
3481
		if ((!ext4_ext_is_unwritten(abut_ex)) &&		/*C1*/
3482 3483
			((prev_lblk + prev_len) == ee_block) &&		/*C2*/
			((prev_pblk + prev_len) == ee_pblk) &&		/*C3*/
3484
			(prev_len < (EXT_INIT_MAX_LEN - map_len))) {	/*C4*/
3485 3486 3487 3488 3489
			err = ext4_ext_get_access(handle, inode, path + depth);
			if (err)
				goto out;

			trace_ext4_ext_convert_to_initialized_fastpath(inode,
3490
				map, ex, abut_ex);
3491

3492 3493 3494 3495
			/* Shift the start of ex by 'map_len' blocks */
			ex->ee_block = cpu_to_le32(ee_block + map_len);
			ext4_ext_store_pblock(ex, ee_pblk + map_len);
			ex->ee_len = cpu_to_le16(ee_len - map_len);
3496
			ext4_ext_mark_unwritten(ex); /* Restore the flag */
3497

3498 3499
			/* Extend abut_ex by 'map_len' blocks */
			abut_ex->ee_len = cpu_to_le16(prev_len + map_len);
3500

3501 3502 3503 3504 3505 3506 3507 3508 3509 3510 3511 3512 3513 3514 3515 3516
			/* Result: number of initialized blocks past m_lblk */
			allocated = map_len;
		}
	} else if (((map->m_lblk + map_len) == (ee_block + ee_len)) &&
		   (map_len < ee_len) &&	/*L1*/
		   ex < EXT_LAST_EXTENT(eh)) {	/*L2*/
		/* See if we can merge right */
		ext4_lblk_t next_lblk;
		ext4_fsblk_t next_pblk, ee_pblk;
		unsigned int next_len;

		abut_ex = ex + 1;
		next_lblk = le32_to_cpu(abut_ex->ee_block);
		next_len = ext4_ext_get_actual_len(abut_ex);
		next_pblk = ext4_ext_pblock(abut_ex);
		ee_pblk = ext4_ext_pblock(ex);
3517

3518 3519 3520 3521 3522 3523 3524 3525 3526
		/*
		 * A transfer of blocks from 'ex' to 'abut_ex' is allowed
		 * upon those conditions:
		 * - C1: abut_ex is initialized,
		 * - C2: abut_ex is logically abutting ex,
		 * - C3: abut_ex is physically abutting ex,
		 * - C4: abut_ex can receive the additional blocks without
		 *   overflowing the (initialized) length limit.
		 */
3527
		if ((!ext4_ext_is_unwritten(abut_ex)) &&		/*C1*/
3528 3529 3530 3531 3532 3533 3534 3535 3536 3537 3538 3539 3540 3541
		    ((map->m_lblk + map_len) == next_lblk) &&		/*C2*/
		    ((ee_pblk + ee_len) == next_pblk) &&		/*C3*/
		    (next_len < (EXT_INIT_MAX_LEN - map_len))) {	/*C4*/
			err = ext4_ext_get_access(handle, inode, path + depth);
			if (err)
				goto out;

			trace_ext4_ext_convert_to_initialized_fastpath(inode,
				map, ex, abut_ex);

			/* Shift the start of abut_ex by 'map_len' blocks */
			abut_ex->ee_block = cpu_to_le32(next_lblk - map_len);
			ext4_ext_store_pblock(abut_ex, next_pblk - map_len);
			ex->ee_len = cpu_to_le16(ee_len - map_len);
3542
			ext4_ext_mark_unwritten(ex); /* Restore the flag */
3543 3544 3545

			/* Extend abut_ex by 'map_len' blocks */
			abut_ex->ee_len = cpu_to_le16(next_len + map_len);
3546 3547

			/* Result: number of initialized blocks past m_lblk */
3548
			allocated = map_len;
3549 3550
		}
	}
3551 3552 3553 3554 3555 3556 3557 3558 3559
	if (allocated) {
		/* Mark the block containing both extents as dirty */
		ext4_ext_dirty(handle, inode, path + depth);

		/* Update path to point to the right extent */
		path[depth].p_ext = abut_ex;
		goto out;
	} else
		allocated = ee_len - (map->m_lblk - ee_block);
3560

3561
	WARN_ON(map->m_lblk < ee_block);
3562 3563
	/*
	 * It is safe to convert extent to initialized via explicit
Y
Yongqiang Yang 已提交
3564
	 * zeroout only if extent is fully inside i_size or new_size.
3565
	 */
3566
	split_flag |= ee_block + ee_len <= eof_block ? EXT4_EXT_MAY_ZEROOUT : 0;
3567

3568 3569
	if (EXT4_EXT_MAY_ZEROOUT & split_flag)
		max_zeroout = sbi->s_extent_max_zeroout_kb >>
3570
			(inode->i_sb->s_blocksize_bits - 10);
3571

3572 3573 3574
	if (ext4_encrypted_inode(inode))
		max_zeroout = 0;

3575
	/*
3576
	 * five cases:
3577
	 * 1. split the extent into three extents.
3578 3579 3580 3581
	 * 2. split the extent into two extents, zeroout the head of the first
	 *    extent.
	 * 3. split the extent into two extents, zeroout the tail of the second
	 *    extent.
3582
	 * 4. split the extent into two extents with out zeroout.
3583 3584
	 * 5. no splitting needed, just possibly zeroout the head and / or the
	 *    tail of the extent.
3585
	 */
3586 3587 3588
	split_map.m_lblk = map->m_lblk;
	split_map.m_len = map->m_len;

3589
	if (max_zeroout && (allocated > split_map.m_len)) {
3590
		if (allocated <= max_zeroout) {
3591 3592 3593 3594 3595 3596 3597 3598 3599 3600
			/* case 3 or 5 */
			zero_ex1.ee_block =
				 cpu_to_le32(split_map.m_lblk +
					     split_map.m_len);
			zero_ex1.ee_len =
				cpu_to_le16(allocated - split_map.m_len);
			ext4_ext_store_pblock(&zero_ex1,
				ext4_ext_pblock(ex) + split_map.m_lblk +
				split_map.m_len - ee_block);
			err = ext4_ext_zeroout(inode, &zero_ex1);
3601 3602
			if (err)
				goto out;
3603
			split_map.m_len = allocated;
3604 3605 3606 3607 3608 3609 3610
		}
		if (split_map.m_lblk - ee_block + split_map.m_len <
								max_zeroout) {
			/* case 2 or 5 */
			if (split_map.m_lblk != ee_block) {
				zero_ex2.ee_block = ex->ee_block;
				zero_ex2.ee_len = cpu_to_le16(split_map.m_lblk -
3611
							ee_block);
3612
				ext4_ext_store_pblock(&zero_ex2,
3613
						      ext4_ext_pblock(ex));
3614
				err = ext4_ext_zeroout(inode, &zero_ex2);
3615 3616 3617 3618
				if (err)
					goto out;
			}

3619
			split_map.m_len += split_map.m_lblk - ee_block;
3620
			split_map.m_lblk = ee_block;
3621
			allocated = map->m_len;
3622 3623
		}
	}
3624

3625 3626 3627 3628
	err = ext4_split_extent(handle, inode, ppath, &split_map, split_flag,
				flags);
	if (err > 0)
		err = 0;
3629
out:
3630
	/* If we have gotten a failure, don't zero out status tree */
3631 3632 3633 3634 3635
	if (!err) {
		err = ext4_zeroout_es(inode, &zero_ex1);
		if (!err)
			err = ext4_zeroout_es(inode, &zero_ex2);
	}
3636 3637 3638
	return err ? err : allocated;
}

3639
/*
3640
 * This function is called by ext4_ext_map_blocks() from
3641
 * ext4_get_blocks_dio_write() when DIO to write
3642
 * to an unwritten extent.
3643
 *
3644 3645
 * Writing to an unwritten extent may result in splitting the unwritten
 * extent into multiple initialized/unwritten extents (up to three)
3646
 * There are three possibilities:
3647
 *   a> There is no split required: Entire extent should be unwritten
3648 3649 3650
 *   b> Splits in two extents: Write is happening at either end of the extent
 *   c> Splits in three extents: Somone is writing in middle of the extent
 *
3651 3652
 * This works the same way in the case of initialized -> unwritten conversion.
 *
3653
 * One of more index blocks maybe needed if the extent tree grow after
3654 3655 3656 3657
 * the unwritten extent split. To prevent ENOSPC occur at the IO
 * complete, we need to split the unwritten extent before DIO submit
 * the IO. The unwritten extent called at this time will be split
 * into three unwritten extent(at most). After IO complete, the part
3658 3659
 * being filled will be convert to initialized by the end_io callback function
 * via ext4_convert_unwritten_extents().
3660
 *
3661
 * Returns the size of unwritten extent to be written on success.
3662
 */
3663
static int ext4_split_convert_extents(handle_t *handle,
3664
					struct inode *inode,
3665
					struct ext4_map_blocks *map,
3666
					struct ext4_ext_path **ppath,
3667 3668
					int flags)
{
3669
	struct ext4_ext_path *path = *ppath;
3670 3671 3672 3673 3674
	ext4_lblk_t eof_block;
	ext4_lblk_t ee_block;
	struct ext4_extent *ex;
	unsigned int ee_len;
	int split_flag = 0, depth;
3675

3676 3677 3678
	ext_debug("%s: inode %lu, logical block %llu, max_blocks %u\n",
		  __func__, inode->i_ino,
		  (unsigned long long)map->m_lblk, map->m_len);
3679 3680 3681

	eof_block = (inode->i_size + inode->i_sb->s_blocksize - 1) >>
		inode->i_sb->s_blocksize_bits;
3682 3683
	if (eof_block < map->m_lblk + map->m_len)
		eof_block = map->m_lblk + map->m_len;
3684 3685 3686 3687
	/*
	 * It is safe to convert extent to initialized via explicit
	 * zeroout only if extent is fully insde i_size or new_size.
	 */
3688 3689 3690 3691
	depth = ext_depth(inode);
	ex = path[depth].p_ext;
	ee_block = le32_to_cpu(ex->ee_block);
	ee_len = ext4_ext_get_actual_len(ex);
3692

3693 3694 3695 3696 3697 3698 3699
	/* Convert to unwritten */
	if (flags & EXT4_GET_BLOCKS_CONVERT_UNWRITTEN) {
		split_flag |= EXT4_EXT_DATA_VALID1;
	/* Convert to initialized */
	} else if (flags & EXT4_GET_BLOCKS_CONVERT) {
		split_flag |= ee_block + ee_len <= eof_block ?
			      EXT4_EXT_MAY_ZEROOUT : 0;
3700
		split_flag |= (EXT4_EXT_MARK_UNWRIT2 | EXT4_EXT_DATA_VALID2);
3701
	}
3702
	flags |= EXT4_GET_BLOCKS_PRE_IO;
3703
	return ext4_split_extent(handle, inode, ppath, map, split_flag, flags);
3704
}
3705

3706
static int ext4_convert_unwritten_extents_endio(handle_t *handle,
3707 3708
						struct inode *inode,
						struct ext4_map_blocks *map,
3709
						struct ext4_ext_path **ppath)
3710
{
3711
	struct ext4_ext_path *path = *ppath;
3712
	struct ext4_extent *ex;
3713 3714
	ext4_lblk_t ee_block;
	unsigned int ee_len;
3715 3716 3717 3718 3719
	int depth;
	int err = 0;

	depth = ext_depth(inode);
	ex = path[depth].p_ext;
3720 3721
	ee_block = le32_to_cpu(ex->ee_block);
	ee_len = ext4_ext_get_actual_len(ex);
3722

3723 3724
	ext_debug("ext4_convert_unwritten_extents_endio: inode %lu, logical"
		"block %llu, max_blocks %u\n", inode->i_ino,
3725 3726
		  (unsigned long long)ee_block, ee_len);

3727 3728 3729 3730 3731 3732
	/* If extent is larger than requested it is a clear sign that we still
	 * have some extent state machine issues left. So extent_split is still
	 * required.
	 * TODO: Once all related issues will be fixed this situation should be
	 * illegal.
	 */
3733
	if (ee_block != map->m_lblk || ee_len > map->m_len) {
3734 3735
#ifdef EXT4_DEBUG
		ext4_warning("Inode (%ld) finished: extent logical block %llu,"
3736
			     " len %u; IO logical block %llu, len %u",
3737 3738 3739
			     inode->i_ino, (unsigned long long)ee_block, ee_len,
			     (unsigned long long)map->m_lblk, map->m_len);
#endif
3740
		err = ext4_split_convert_extents(handle, inode, map, ppath,
3741
						 EXT4_GET_BLOCKS_CONVERT);
3742
		if (err < 0)
3743
			return err;
3744
		path = ext4_find_extent(inode, map->m_lblk, ppath, 0);
3745 3746
		if (IS_ERR(path))
			return PTR_ERR(path);
3747 3748 3749
		depth = ext_depth(inode);
		ex = path[depth].p_ext;
	}
3750

3751 3752 3753 3754 3755 3756
	err = ext4_ext_get_access(handle, inode, path + depth);
	if (err)
		goto out;
	/* first mark the extent as initialized */
	ext4_ext_mark_initialized(ex);

3757 3758
	/* note: ext4_ext_correct_indexes() isn't needed here because
	 * borders are not changed
3759
	 */
3760
	ext4_ext_try_to_merge(handle, inode, path, ex);
3761

3762
	/* Mark modified extent as dirty */
3763
	err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3764 3765 3766 3767 3768
out:
	ext4_ext_show_leaf(inode, path);
	return err;
}

T
Theodore Ts'o 已提交
3769 3770 3771 3772
/*
 * Handle EOFBLOCKS_FL flag, clearing it if necessary
 */
static int check_eofblocks_fl(handle_t *handle, struct inode *inode,
3773
			      ext4_lblk_t lblk,
T
Theodore Ts'o 已提交
3774 3775 3776 3777 3778
			      struct ext4_ext_path *path,
			      unsigned int len)
{
	int i, depth;
	struct ext4_extent_header *eh;
3779
	struct ext4_extent *last_ex;
T
Theodore Ts'o 已提交
3780 3781 3782 3783 3784 3785 3786

	if (!ext4_test_inode_flag(inode, EXT4_INODE_EOFBLOCKS))
		return 0;

	depth = ext_depth(inode);
	eh = path[depth].p_hdr;

3787 3788 3789 3790 3791 3792 3793
	/*
	 * We're going to remove EOFBLOCKS_FL entirely in future so we
	 * do not care for this case anymore. Simply remove the flag
	 * if there are no extents.
	 */
	if (unlikely(!eh->eh_entries))
		goto out;
T
Theodore Ts'o 已提交
3794 3795 3796 3797 3798 3799 3800 3801 3802 3803
	last_ex = EXT_LAST_EXTENT(eh);
	/*
	 * We should clear the EOFBLOCKS_FL flag if we are writing the
	 * last block in the last extent in the file.  We test this by
	 * first checking to see if the caller to
	 * ext4_ext_get_blocks() was interested in the last block (or
	 * a block beyond the last block) in the current extent.  If
	 * this turns out to be false, we can bail out from this
	 * function immediately.
	 */
3804
	if (lblk + len < le32_to_cpu(last_ex->ee_block) +
T
Theodore Ts'o 已提交
3805 3806 3807 3808 3809 3810 3811 3812 3813 3814 3815 3816
	    ext4_ext_get_actual_len(last_ex))
		return 0;
	/*
	 * If the caller does appear to be planning to write at or
	 * beyond the end of the current extent, we then test to see
	 * if the current extent is the last extent in the file, by
	 * checking to make sure it was reached via the rightmost node
	 * at each level of the tree.
	 */
	for (i = depth-1; i >= 0; i--)
		if (path[i].p_idx != EXT_LAST_INDEX(path[i].p_hdr))
			return 0;
3817
out:
T
Theodore Ts'o 已提交
3818 3819 3820 3821
	ext4_clear_inode_flag(inode, EXT4_INODE_EOFBLOCKS);
	return ext4_mark_inode_dirty(handle, inode);
}

3822 3823 3824 3825 3826 3827 3828 3829 3830 3831 3832 3833 3834 3835 3836 3837 3838 3839 3840 3841 3842 3843 3844 3845 3846 3847 3848 3849 3850 3851 3852 3853 3854 3855 3856 3857 3858 3859 3860 3861 3862 3863 3864 3865 3866 3867 3868 3869 3870 3871
/**
 * Determines how many complete clusters (out of those specified by the 'map')
 * are under delalloc and were reserved quota for.
 * This function is called when we are writing out the blocks that were
 * originally written with their allocation delayed, but then the space was
 * allocated using fallocate() before the delayed allocation could be resolved.
 * The cases to look for are:
 * ('=' indicated delayed allocated blocks
 *  '-' indicates non-delayed allocated blocks)
 * (a) partial clusters towards beginning and/or end outside of allocated range
 *     are not delalloc'ed.
 *	Ex:
 *	|----c---=|====c====|====c====|===-c----|
 *	         |++++++ allocated ++++++|
 *	==> 4 complete clusters in above example
 *
 * (b) partial cluster (outside of allocated range) towards either end is
 *     marked for delayed allocation. In this case, we will exclude that
 *     cluster.
 *	Ex:
 *	|----====c========|========c========|
 *	     |++++++ allocated ++++++|
 *	==> 1 complete clusters in above example
 *
 *	Ex:
 *	|================c================|
 *            |++++++ allocated ++++++|
 *	==> 0 complete clusters in above example
 *
 * The ext4_da_update_reserve_space will be called only if we
 * determine here that there were some "entire" clusters that span
 * this 'allocated' range.
 * In the non-bigalloc case, this function will just end up returning num_blks
 * without ever calling ext4_find_delalloc_range.
 */
static unsigned int
get_reserved_cluster_alloc(struct inode *inode, ext4_lblk_t lblk_start,
			   unsigned int num_blks)
{
	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
	ext4_lblk_t alloc_cluster_start, alloc_cluster_end;
	ext4_lblk_t lblk_from, lblk_to, c_offset;
	unsigned int allocated_clusters = 0;

	alloc_cluster_start = EXT4_B2C(sbi, lblk_start);
	alloc_cluster_end = EXT4_B2C(sbi, lblk_start + num_blks - 1);

	/* max possible clusters for this allocation */
	allocated_clusters = alloc_cluster_end - alloc_cluster_start + 1;

3872 3873
	trace_ext4_get_reserved_cluster_alloc(inode, lblk_start, num_blks);

3874
	/* Check towards left side */
3875
	c_offset = EXT4_LBLK_COFF(sbi, lblk_start);
3876
	if (c_offset) {
3877
		lblk_from = EXT4_LBLK_CMASK(sbi, lblk_start);
3878 3879
		lblk_to = lblk_from + c_offset - 1;

3880 3881
		if (ext4_es_scan_range(inode, &ext4_es_is_delayed, lblk_from,
				       lblk_to))
3882 3883 3884 3885
			allocated_clusters--;
	}

	/* Now check towards right. */
3886
	c_offset = EXT4_LBLK_COFF(sbi, lblk_start + num_blks);
3887 3888 3889 3890
	if (allocated_clusters && c_offset) {
		lblk_from = lblk_start + num_blks;
		lblk_to = lblk_from + (sbi->s_cluster_ratio - c_offset) - 1;

3891 3892
		if (ext4_es_scan_range(inode, &ext4_es_is_delayed, lblk_from,
				       lblk_to))
3893 3894 3895 3896 3897 3898
			allocated_clusters--;
	}

	return allocated_clusters;
}

3899
static int
3900 3901
convert_initialized_extent(handle_t *handle, struct inode *inode,
			   struct ext4_map_blocks *map,
3902
			   struct ext4_ext_path **ppath,
3903
			   unsigned int allocated)
3904
{
3905
	struct ext4_ext_path *path = *ppath;
3906 3907 3908 3909
	struct ext4_extent *ex;
	ext4_lblk_t ee_block;
	unsigned int ee_len;
	int depth;
3910 3911 3912 3913
	int err = 0;

	/*
	 * Make sure that the extent is no bigger than we support with
3914
	 * unwritten extent
3915
	 */
3916 3917
	if (map->m_len > EXT_UNWRITTEN_MAX_LEN)
		map->m_len = EXT_UNWRITTEN_MAX_LEN / 2;
3918

3919 3920 3921 3922 3923 3924 3925 3926 3927 3928
	depth = ext_depth(inode);
	ex = path[depth].p_ext;
	ee_block = le32_to_cpu(ex->ee_block);
	ee_len = ext4_ext_get_actual_len(ex);

	ext_debug("%s: inode %lu, logical"
		"block %llu, max_blocks %u\n", __func__, inode->i_ino,
		  (unsigned long long)ee_block, ee_len);

	if (ee_block != map->m_lblk || ee_len > map->m_len) {
3929
		err = ext4_split_convert_extents(handle, inode, map, ppath,
3930 3931 3932
				EXT4_GET_BLOCKS_CONVERT_UNWRITTEN);
		if (err < 0)
			return err;
3933
		path = ext4_find_extent(inode, map->m_lblk, ppath, 0);
3934 3935 3936 3937 3938 3939 3940
		if (IS_ERR(path))
			return PTR_ERR(path);
		depth = ext_depth(inode);
		ex = path[depth].p_ext;
		if (!ex) {
			EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
					 (unsigned long) map->m_lblk);
3941
			return -EFSCORRUPTED;
3942 3943 3944 3945 3946 3947 3948 3949 3950 3951 3952 3953 3954 3955 3956 3957 3958 3959 3960 3961 3962 3963 3964 3965
		}
	}

	err = ext4_ext_get_access(handle, inode, path + depth);
	if (err)
		return err;
	/* first mark the extent as unwritten */
	ext4_ext_mark_unwritten(ex);

	/* note: ext4_ext_correct_indexes() isn't needed here because
	 * borders are not changed
	 */
	ext4_ext_try_to_merge(handle, inode, path, ex);

	/* Mark modified extent as dirty */
	err = ext4_ext_dirty(handle, inode, path + path->p_depth);
	if (err)
		return err;
	ext4_ext_show_leaf(inode, path);

	ext4_update_inode_fsync_trans(handle, inode, 1);
	err = check_eofblocks_fl(handle, inode, map->m_lblk, path, map->m_len);
	if (err)
		return err;
3966 3967 3968 3969
	map->m_flags |= EXT4_MAP_UNWRITTEN;
	if (allocated > map->m_len)
		allocated = map->m_len;
	map->m_len = allocated;
3970
	return allocated;
3971 3972
}

3973
static int
3974
ext4_ext_handle_unwritten_extents(handle_t *handle, struct inode *inode,
3975
			struct ext4_map_blocks *map,
3976
			struct ext4_ext_path **ppath, int flags,
3977
			unsigned int allocated, ext4_fsblk_t newblock)
3978
{
3979
	struct ext4_ext_path *path = *ppath;
3980 3981 3982
	int ret = 0;
	int err = 0;

3983
	ext_debug("ext4_ext_handle_unwritten_extents: inode %lu, logical "
3984
		  "block %llu, max_blocks %u, flags %x, allocated %u\n",
3985
		  inode->i_ino, (unsigned long long)map->m_lblk, map->m_len,
3986 3987 3988
		  flags, allocated);
	ext4_ext_show_leaf(inode, path);

L
Lukas Czerner 已提交
3989
	/*
3990
	 * When writing into unwritten space, we should not fail to
L
Lukas Czerner 已提交
3991 3992 3993 3994
	 * allocate metadata blocks for the new extent block if needed.
	 */
	flags |= EXT4_GET_BLOCKS_METADATA_NOFAIL;

3995
	trace_ext4_ext_handle_unwritten_extents(inode, map, flags,
3996
						    allocated, newblock);
3997

3998
	/* get_block() before submit the IO, split the extent */
3999
	if (flags & EXT4_GET_BLOCKS_PRE_IO) {
4000 4001
		ret = ext4_split_convert_extents(handle, inode, map, ppath,
					 flags | EXT4_GET_BLOCKS_CONVERT);
4002 4003
		if (ret <= 0)
			goto out;
4004
		map->m_flags |= EXT4_MAP_UNWRITTEN;
4005 4006
		goto out;
	}
4007
	/* IO end_io complete, convert the filled extent to written */
4008
	if (flags & EXT4_GET_BLOCKS_CONVERT) {
4009 4010 4011 4012 4013 4014 4015 4016
		if (flags & EXT4_GET_BLOCKS_ZERO) {
			if (allocated > map->m_len)
				allocated = map->m_len;
			err = ext4_issue_zeroout(inode, map->m_lblk, newblock,
						 allocated);
			if (err < 0)
				goto out2;
		}
4017
		ret = ext4_convert_unwritten_extents_endio(handle, inode, map,
4018
							   ppath);
T
Theodore Ts'o 已提交
4019
		if (ret >= 0) {
4020
			ext4_update_inode_fsync_trans(handle, inode, 1);
4021 4022
			err = check_eofblocks_fl(handle, inode, map->m_lblk,
						 path, map->m_len);
T
Theodore Ts'o 已提交
4023 4024
		} else
			err = ret;
4025
		map->m_flags |= EXT4_MAP_MAPPED;
4026
		map->m_pblk = newblock;
4027 4028 4029
		if (allocated > map->m_len)
			allocated = map->m_len;
		map->m_len = allocated;
4030 4031 4032 4033 4034 4035 4036
		goto out2;
	}
	/* buffered IO case */
	/*
	 * repeat fallocate creation request
	 * we already have an unwritten extent
	 */
4037
	if (flags & EXT4_GET_BLOCKS_UNWRIT_EXT) {
4038
		map->m_flags |= EXT4_MAP_UNWRITTEN;
4039
		goto map_out;
4040
	}
4041 4042 4043 4044 4045 4046 4047 4048 4049 4050

	/* buffered READ or buffered write_begin() lookup */
	if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
		/*
		 * We have blocks reserved already.  We
		 * return allocated blocks so that delalloc
		 * won't do block reservation for us.  But
		 * the buffer head will be unmapped so that
		 * a read from the block returns 0s.
		 */
4051
		map->m_flags |= EXT4_MAP_UNWRITTEN;
4052 4053 4054 4055
		goto out1;
	}

	/* buffered write, writepage time, convert*/
4056
	ret = ext4_ext_convert_to_initialized(handle, inode, map, ppath, flags);
4057
	if (ret >= 0)
4058
		ext4_update_inode_fsync_trans(handle, inode, 1);
4059 4060 4061 4062 4063 4064
out:
	if (ret <= 0) {
		err = ret;
		goto out2;
	} else
		allocated = ret;
4065
	map->m_flags |= EXT4_MAP_NEW;
4066 4067 4068 4069 4070 4071 4072
	/*
	 * if we allocated more blocks than requested
	 * we need to make sure we unmap the extra block
	 * allocated. The actual needed block will get
	 * unmapped later when we find the buffer_head marked
	 * new.
	 */
4073
	if (allocated > map->m_len) {
4074 4075
		clean_bdev_aliases(inode->i_sb->s_bdev, newblock + map->m_len,
				   allocated - map->m_len);
4076
		allocated = map->m_len;
4077
	}
4078
	map->m_len = allocated;
4079 4080 4081 4082 4083 4084 4085 4086

	/*
	 * If we have done fallocate with the offset that is already
	 * delayed allocated, we would have block reservation
	 * and quota reservation done in the delayed write path.
	 * But fallocate would have already updated quota and block
	 * count for this offset. So cancel these reservation
	 */
4087 4088 4089 4090 4091 4092 4093 4094 4095
	if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE) {
		unsigned int reserved_clusters;
		reserved_clusters = get_reserved_cluster_alloc(inode,
				map->m_lblk, map->m_len);
		if (reserved_clusters)
			ext4_da_update_reserve_space(inode,
						     reserved_clusters,
						     0);
	}
4096

4097
map_out:
4098
	map->m_flags |= EXT4_MAP_MAPPED;
4099 4100 4101 4102 4103 4104
	if ((flags & EXT4_GET_BLOCKS_KEEP_SIZE) == 0) {
		err = check_eofblocks_fl(handle, inode, map->m_lblk, path,
					 map->m_len);
		if (err < 0)
			goto out2;
	}
4105
out1:
4106 4107
	if (allocated > map->m_len)
		allocated = map->m_len;
4108
	ext4_ext_show_leaf(inode, path);
4109 4110
	map->m_pblk = newblock;
	map->m_len = allocated;
4111 4112 4113
out2:
	return err ? err : allocated;
}
T
Theodore Ts'o 已提交
4114

4115 4116 4117 4118
/*
 * get_implied_cluster_alloc - check to see if the requested
 * allocation (in the map structure) overlaps with a cluster already
 * allocated in an extent.
4119
 *	@sb	The filesystem superblock structure
4120 4121 4122 4123 4124 4125 4126 4127 4128 4129 4130 4131 4132 4133 4134 4135 4136 4137 4138 4139 4140 4141 4142 4143 4144 4145 4146 4147 4148 4149 4150 4151 4152 4153 4154 4155
 *	@map	The requested lblk->pblk mapping
 *	@ex	The extent structure which might contain an implied
 *			cluster allocation
 *
 * This function is called by ext4_ext_map_blocks() after we failed to
 * find blocks that were already in the inode's extent tree.  Hence,
 * we know that the beginning of the requested region cannot overlap
 * the extent from the inode's extent tree.  There are three cases we
 * want to catch.  The first is this case:
 *
 *		 |--- cluster # N--|
 *    |--- extent ---|	|---- requested region ---|
 *			|==========|
 *
 * The second case that we need to test for is this one:
 *
 *   |--------- cluster # N ----------------|
 *	   |--- requested region --|   |------- extent ----|
 *	   |=======================|
 *
 * The third case is when the requested region lies between two extents
 * within the same cluster:
 *          |------------- cluster # N-------------|
 * |----- ex -----|                  |---- ex_right ----|
 *                  |------ requested region ------|
 *                  |================|
 *
 * In each of the above cases, we need to set the map->m_pblk and
 * map->m_len so it corresponds to the return the extent labelled as
 * "|====|" from cluster #N, since it is already in use for data in
 * cluster EXT4_B2C(sbi, map->m_lblk).	We will then return 1 to
 * signal to ext4_ext_map_blocks() that map->m_pblk should be treated
 * as a new "allocated" block region.  Otherwise, we will return 0 and
 * ext4_ext_map_blocks() will then allocate one or more new clusters
 * by calling ext4_mb_new_blocks().
 */
4156
static int get_implied_cluster_alloc(struct super_block *sb,
4157 4158 4159 4160
				     struct ext4_map_blocks *map,
				     struct ext4_extent *ex,
				     struct ext4_ext_path *path)
{
4161
	struct ext4_sb_info *sbi = EXT4_SB(sb);
4162
	ext4_lblk_t c_offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4163
	ext4_lblk_t ex_cluster_start, ex_cluster_end;
4164
	ext4_lblk_t rr_cluster_start;
4165 4166 4167 4168 4169 4170 4171 4172 4173 4174 4175 4176 4177 4178 4179
	ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
	ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
	unsigned short ee_len = ext4_ext_get_actual_len(ex);

	/* The extent passed in that we are trying to match */
	ex_cluster_start = EXT4_B2C(sbi, ee_block);
	ex_cluster_end = EXT4_B2C(sbi, ee_block + ee_len - 1);

	/* The requested region passed into ext4_map_blocks() */
	rr_cluster_start = EXT4_B2C(sbi, map->m_lblk);

	if ((rr_cluster_start == ex_cluster_end) ||
	    (rr_cluster_start == ex_cluster_start)) {
		if (rr_cluster_start == ex_cluster_end)
			ee_start += ee_len - 1;
4180
		map->m_pblk = EXT4_PBLK_CMASK(sbi, ee_start) + c_offset;
4181 4182 4183 4184 4185 4186 4187 4188 4189 4190 4191 4192 4193 4194 4195 4196 4197 4198 4199 4200 4201 4202 4203 4204 4205 4206 4207
		map->m_len = min(map->m_len,
				 (unsigned) sbi->s_cluster_ratio - c_offset);
		/*
		 * Check for and handle this case:
		 *
		 *   |--------- cluster # N-------------|
		 *		       |------- extent ----|
		 *	   |--- requested region ---|
		 *	   |===========|
		 */

		if (map->m_lblk < ee_block)
			map->m_len = min(map->m_len, ee_block - map->m_lblk);

		/*
		 * Check for the case where there is already another allocated
		 * block to the right of 'ex' but before the end of the cluster.
		 *
		 *          |------------- cluster # N-------------|
		 * |----- ex -----|                  |---- ex_right ----|
		 *                  |------ requested region ------|
		 *                  |================|
		 */
		if (map->m_lblk > ee_block) {
			ext4_lblk_t next = ext4_ext_next_allocated_block(path);
			map->m_len = min(map->m_len, next - map->m_lblk);
		}
4208 4209

		trace_ext4_get_implied_cluster_alloc_exit(sb, map, 1);
4210 4211
		return 1;
	}
4212 4213

	trace_ext4_get_implied_cluster_alloc_exit(sb, map, 0);
4214 4215 4216 4217
	return 0;
}


4218
/*
4219 4220 4221
 * Block allocation/map/preallocation routine for extents based files
 *
 *
4222
 * Need to be called with
4223 4224
 * down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system block
 * (ie, create is zero). Otherwise down_write(&EXT4_I(inode)->i_data_sem)
4225 4226 4227 4228 4229 4230 4231 4232 4233 4234
 *
 * return > 0, number of of blocks already mapped/allocated
 *          if create == 0 and these are pre-allocated blocks
 *          	buffer head is unmapped
 *          otherwise blocks are mapped
 *
 * return = 0, if plain look up failed (blocks have not been allocated)
 *          buffer head is unmapped
 *
 * return < 0, error case.
4235
 */
4236 4237
int ext4_ext_map_blocks(handle_t *handle, struct inode *inode,
			struct ext4_map_blocks *map, int flags)
A
Alex Tomas 已提交
4238 4239
{
	struct ext4_ext_path *path = NULL;
4240 4241
	struct ext4_extent newex, *ex, *ex2;
	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
4242
	ext4_fsblk_t newblock = 0;
4243
	int free_on_err = 0, err = 0, depth, ret;
4244
	unsigned int allocated = 0, offset = 0;
4245
	unsigned int allocated_clusters = 0;
4246
	struct ext4_allocation_request ar;
4247
	ext4_lblk_t cluster_offset;
4248
	bool map_from_cluster = false;
A
Alex Tomas 已提交
4249

4250
	ext_debug("blocks %u/%u requested for inode %lu\n",
4251
		  map->m_lblk, map->m_len, inode->i_ino);
4252
	trace_ext4_ext_map_blocks_enter(inode, map->m_lblk, map->m_len, flags);
A
Alex Tomas 已提交
4253 4254

	/* find extent for this block */
4255
	path = ext4_find_extent(inode, map->m_lblk, NULL, 0);
A
Alex Tomas 已提交
4256 4257 4258 4259 4260 4261 4262 4263 4264
	if (IS_ERR(path)) {
		err = PTR_ERR(path);
		path = NULL;
		goto out2;
	}

	depth = ext_depth(inode);

	/*
4265 4266
	 * consistent leaf must not be empty;
	 * this situation is possible, though, _during_ tree modification;
4267
	 * this is why assert can't be put in ext4_find_extent()
A
Alex Tomas 已提交
4268
	 */
4269 4270
	if (unlikely(path[depth].p_ext == NULL && depth != 0)) {
		EXT4_ERROR_INODE(inode, "bad extent address "
4271 4272 4273
				 "lblock: %lu, depth: %d pblock %lld",
				 (unsigned long) map->m_lblk, depth,
				 path[depth].p_block);
4274
		err = -EFSCORRUPTED;
4275 4276
		goto out2;
	}
A
Alex Tomas 已提交
4277

4278 4279
	ex = path[depth].p_ext;
	if (ex) {
A
Aneesh Kumar K.V 已提交
4280
		ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
4281
		ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
A
Amit Arora 已提交
4282
		unsigned short ee_len;
4283

4284

4285
		/*
4286
		 * unwritten extents are treated as holes, except that
4287
		 * we split out initialized portions during a write.
4288
		 */
A
Amit Arora 已提交
4289
		ee_len = ext4_ext_get_actual_len(ex);
4290 4291 4292

		trace_ext4_ext_show_extent(inode, ee_block, ee_start, ee_len);

4293
		/* if found extent covers block, simply return it */
4294 4295
		if (in_range(map->m_lblk, ee_block, ee_len)) {
			newblock = map->m_lblk - ee_block + ee_start;
4296
			/* number of remaining blocks in the extent */
4297 4298 4299
			allocated = ee_len - (map->m_lblk - ee_block);
			ext_debug("%u fit into %u:%d -> %llu\n", map->m_lblk,
				  ee_block, ee_len, newblock);
4300

4301 4302 4303 4304
			/*
			 * If the extent is initialized check whether the
			 * caller wants to convert it to unwritten.
			 */
4305
			if ((!ext4_ext_is_unwritten(ex)) &&
4306
			    (flags & EXT4_GET_BLOCKS_CONVERT_UNWRITTEN)) {
4307
				allocated = convert_initialized_extent(
4308
						handle, inode, map, &path,
4309
						allocated);
4310
				goto out2;
4311
			} else if (!ext4_ext_is_unwritten(ex))
4312
				goto out;
Z
Zheng Liu 已提交
4313

4314
			ret = ext4_ext_handle_unwritten_extents(
4315
				handle, inode, map, &path, flags,
4316
				allocated, newblock);
4317 4318 4319 4320
			if (ret < 0)
				err = ret;
			else
				allocated = ret;
4321
			goto out2;
A
Alex Tomas 已提交
4322 4323 4324 4325
		}
	}

	/*
4326
	 * requested block isn't allocated yet;
A
Alex Tomas 已提交
4327 4328
	 * we couldn't try to create block if create flag is zero
	 */
4329
	if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
4330 4331
		ext4_lblk_t hole_start, hole_len;

4332 4333
		hole_start = map->m_lblk;
		hole_len = ext4_ext_determine_hole(inode, path, &hole_start);
4334 4335 4336 4337
		/*
		 * put just found gap into cache to speed up
		 * subsequent requests
		 */
4338
		ext4_ext_put_gap_in_cache(inode, hole_start, hole_len);
4339 4340 4341 4342 4343 4344 4345

		/* Update hole_len to reflect hole size after map->m_lblk */
		if (hole_start != map->m_lblk)
			hole_len -= map->m_lblk - hole_start;
		map->m_pblk = 0;
		map->m_len = min_t(unsigned int, map->m_len, hole_len);

A
Alex Tomas 已提交
4346 4347
		goto out2;
	}
4348

A
Alex Tomas 已提交
4349
	/*
4350
	 * Okay, we need to do block allocation.
A
Andrew Morton 已提交
4351
	 */
4352
	newex.ee_block = cpu_to_le32(map->m_lblk);
E
Eric Whitney 已提交
4353
	cluster_offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4354 4355 4356

	/*
	 * If we are doing bigalloc, check to see if the extent returned
4357
	 * by ext4_find_extent() implies a cluster we can use.
4358 4359
	 */
	if (cluster_offset && ex &&
4360
	    get_implied_cluster_alloc(inode->i_sb, map, ex, path)) {
4361 4362
		ar.len = allocated = map->m_len;
		newblock = map->m_pblk;
4363
		map_from_cluster = true;
4364 4365
		goto got_allocated_blocks;
	}
A
Alex Tomas 已提交
4366

4367
	/* find neighbour allocated blocks */
4368
	ar.lleft = map->m_lblk;
4369 4370 4371
	err = ext4_ext_search_left(inode, path, &ar.lleft, &ar.pleft);
	if (err)
		goto out2;
4372
	ar.lright = map->m_lblk;
4373 4374
	ex2 = NULL;
	err = ext4_ext_search_right(inode, path, &ar.lright, &ar.pright, &ex2);
4375 4376
	if (err)
		goto out2;
A
Amit Arora 已提交
4377

4378 4379 4380
	/* Check if the extent after searching to the right implies a
	 * cluster we can use. */
	if ((sbi->s_cluster_ratio > 1) && ex2 &&
4381
	    get_implied_cluster_alloc(inode->i_sb, map, ex2, path)) {
4382 4383
		ar.len = allocated = map->m_len;
		newblock = map->m_pblk;
4384
		map_from_cluster = true;
4385 4386 4387
		goto got_allocated_blocks;
	}

4388 4389 4390
	/*
	 * See if request is beyond maximum number of blocks we can have in
	 * a single extent. For an initialized extent this limit is
4391 4392
	 * EXT_INIT_MAX_LEN and for an unwritten extent this limit is
	 * EXT_UNWRITTEN_MAX_LEN.
4393
	 */
4394
	if (map->m_len > EXT_INIT_MAX_LEN &&
4395
	    !(flags & EXT4_GET_BLOCKS_UNWRIT_EXT))
4396
		map->m_len = EXT_INIT_MAX_LEN;
4397 4398 4399
	else if (map->m_len > EXT_UNWRITTEN_MAX_LEN &&
		 (flags & EXT4_GET_BLOCKS_UNWRIT_EXT))
		map->m_len = EXT_UNWRITTEN_MAX_LEN;
4400

4401 4402
	/* Check if we can really insert (m_lblk)::(m_lblk + m_len) extent */
	newex.ee_len = cpu_to_le16(map->m_len);
4403
	err = ext4_ext_check_overlap(sbi, inode, &newex, path);
A
Amit Arora 已提交
4404
	if (err)
4405
		allocated = ext4_ext_get_actual_len(&newex);
A
Amit Arora 已提交
4406
	else
4407
		allocated = map->m_len;
4408 4409 4410

	/* allocate new block */
	ar.inode = inode;
4411 4412
	ar.goal = ext4_ext_find_goal(inode, path, map->m_lblk);
	ar.logical = map->m_lblk;
4413 4414 4415 4416 4417 4418 4419 4420
	/*
	 * We calculate the offset from the beginning of the cluster
	 * for the logical block number, since when we allocate a
	 * physical cluster, the physical block should start at the
	 * same offset from the beginning of the cluster.  This is
	 * needed so that future calls to get_implied_cluster_alloc()
	 * work correctly.
	 */
4421
	offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4422 4423 4424
	ar.len = EXT4_NUM_B2C(sbi, offset+allocated);
	ar.goal -= offset;
	ar.logical -= offset;
4425 4426 4427 4428 4429
	if (S_ISREG(inode->i_mode))
		ar.flags = EXT4_MB_HINT_DATA;
	else
		/* disable in-core preallocation for non-regular files */
		ar.flags = 0;
4430 4431
	if (flags & EXT4_GET_BLOCKS_NO_NORMALIZE)
		ar.flags |= EXT4_MB_HINT_NOPREALLOC;
4432 4433
	if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
		ar.flags |= EXT4_MB_DELALLOC_RESERVED;
4434 4435
	if (flags & EXT4_GET_BLOCKS_METADATA_NOFAIL)
		ar.flags |= EXT4_MB_USE_RESERVED;
4436
	newblock = ext4_mb_new_blocks(handle, &ar, &err);
A
Alex Tomas 已提交
4437 4438
	if (!newblock)
		goto out2;
4439
	ext_debug("allocate new block: goal %llu, found %llu/%u\n",
4440
		  ar.goal, newblock, allocated);
4441
	free_on_err = 1;
4442
	allocated_clusters = ar.len;
4443 4444 4445
	ar.len = EXT4_C2B(sbi, ar.len) - offset;
	if (ar.len > allocated)
		ar.len = allocated;
A
Alex Tomas 已提交
4446

4447
got_allocated_blocks:
A
Alex Tomas 已提交
4448
	/* try to insert new extent into found leaf and return */
4449
	ext4_ext_store_pblock(&newex, newblock + offset);
4450
	newex.ee_len = cpu_to_le16(ar.len);
4451 4452 4453
	/* Mark unwritten */
	if (flags & EXT4_GET_BLOCKS_UNWRIT_EXT){
		ext4_ext_mark_unwritten(&newex);
4454
		map->m_flags |= EXT4_MAP_UNWRITTEN;
4455
	}
4456

4457 4458 4459 4460
	err = 0;
	if ((flags & EXT4_GET_BLOCKS_KEEP_SIZE) == 0)
		err = check_eofblocks_fl(handle, inode, map->m_lblk,
					 path, ar.len);
4461
	if (!err)
4462
		err = ext4_ext_insert_extent(handle, inode, &path,
4463
					     &newex, flags);
4464

4465
	if (err && free_on_err) {
4466 4467
		int fb_flags = flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE ?
			EXT4_FREE_BLOCKS_NO_QUOT_UPDATE : 0;
4468
		/* free data blocks we just allocated */
4469 4470
		/* not a good idea to call discard here directly,
		 * but otherwise we'd need to call it every free() */
4471
		ext4_discard_preallocations(inode);
4472 4473
		ext4_free_blocks(handle, inode, NULL, newblock,
				 EXT4_C2B(sbi, allocated_clusters), fb_flags);
A
Alex Tomas 已提交
4474
		goto out2;
4475
	}
A
Alex Tomas 已提交
4476 4477

	/* previous routine could use block we allocated */
4478
	newblock = ext4_ext_pblock(&newex);
4479
	allocated = ext4_ext_get_actual_len(&newex);
4480 4481 4482
	if (allocated > map->m_len)
		allocated = map->m_len;
	map->m_flags |= EXT4_MAP_NEW;
A
Alex Tomas 已提交
4483

4484 4485 4486 4487
	/*
	 * Update reserved blocks/metadata blocks after successful
	 * block allocation which had been deferred till now.
	 */
4488
	if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE) {
4489
		unsigned int reserved_clusters;
4490
		/*
4491
		 * Check how many clusters we had reserved this allocated range
4492 4493 4494
		 */
		reserved_clusters = get_reserved_cluster_alloc(inode,
						map->m_lblk, allocated);
4495
		if (!map_from_cluster) {
4496 4497
			BUG_ON(allocated_clusters < reserved_clusters);
			if (reserved_clusters < allocated_clusters) {
4498
				struct ext4_inode_info *ei = EXT4_I(inode);
4499 4500 4501 4502 4503 4504 4505 4506 4507 4508 4509 4510 4511 4512 4513 4514 4515 4516 4517 4518 4519 4520 4521 4522 4523 4524 4525 4526 4527 4528 4529 4530 4531 4532 4533 4534 4535 4536 4537 4538 4539 4540
				int reservation = allocated_clusters -
						  reserved_clusters;
				/*
				 * It seems we claimed few clusters outside of
				 * the range of this allocation. We should give
				 * it back to the reservation pool. This can
				 * happen in the following case:
				 *
				 * * Suppose s_cluster_ratio is 4 (i.e., each
				 *   cluster has 4 blocks. Thus, the clusters
				 *   are [0-3],[4-7],[8-11]...
				 * * First comes delayed allocation write for
				 *   logical blocks 10 & 11. Since there were no
				 *   previous delayed allocated blocks in the
				 *   range [8-11], we would reserve 1 cluster
				 *   for this write.
				 * * Next comes write for logical blocks 3 to 8.
				 *   In this case, we will reserve 2 clusters
				 *   (for [0-3] and [4-7]; and not for [8-11] as
				 *   that range has a delayed allocated blocks.
				 *   Thus total reserved clusters now becomes 3.
				 * * Now, during the delayed allocation writeout
				 *   time, we will first write blocks [3-8] and
				 *   allocate 3 clusters for writing these
				 *   blocks. Also, we would claim all these
				 *   three clusters above.
				 * * Now when we come here to writeout the
				 *   blocks [10-11], we would expect to claim
				 *   the reservation of 1 cluster we had made
				 *   (and we would claim it since there are no
				 *   more delayed allocated blocks in the range
				 *   [8-11]. But our reserved cluster count had
				 *   already gone to 0.
				 *
				 *   Thus, at the step 4 above when we determine
				 *   that there are still some unwritten delayed
				 *   allocated blocks outside of our current
				 *   block range, we should increment the
				 *   reserved clusters count so that when the
				 *   remaining blocks finally gets written, we
				 *   could claim them.
				 */
4541 4542 4543 4544 4545
				dquot_reserve_block(inode,
						EXT4_C2B(sbi, reservation));
				spin_lock(&ei->i_block_reservation_lock);
				ei->i_reserved_data_blocks += reservation;
				spin_unlock(&ei->i_block_reservation_lock);
4546
			}
4547 4548 4549 4550 4551 4552 4553 4554 4555
			/*
			 * We will claim quota for all newly allocated blocks.
			 * We're updating the reserved space *after* the
			 * correction above so we do not accidentally free
			 * all the metadata reservation because we might
			 * actually need it later on.
			 */
			ext4_da_update_reserve_space(inode, allocated_clusters,
							1);
4556 4557
		}
	}
4558

4559 4560
	/*
	 * Cache the extent and update transaction to commit on fdatasync only
4561
	 * when it is _not_ an unwritten extent.
4562
	 */
4563
	if ((flags & EXT4_GET_BLOCKS_UNWRIT_EXT) == 0)
4564
		ext4_update_inode_fsync_trans(handle, inode, 1);
Z
Zheng Liu 已提交
4565
	else
4566
		ext4_update_inode_fsync_trans(handle, inode, 0);
A
Alex Tomas 已提交
4567
out:
4568 4569
	if (allocated > map->m_len)
		allocated = map->m_len;
A
Alex Tomas 已提交
4570
	ext4_ext_show_leaf(inode, path);
4571 4572 4573
	map->m_flags |= EXT4_MAP_MAPPED;
	map->m_pblk = newblock;
	map->m_len = allocated;
A
Alex Tomas 已提交
4574
out2:
4575 4576
	ext4_ext_drop_refs(path);
	kfree(path);
4577

4578 4579
	trace_ext4_ext_map_blocks_exit(inode, flags, map,
				       err ? err : allocated);
4580
	return err ? err : allocated;
A
Alex Tomas 已提交
4581 4582
}

4583
int ext4_ext_truncate(handle_t *handle, struct inode *inode)
A
Alex Tomas 已提交
4584 4585
{
	struct super_block *sb = inode->i_sb;
A
Aneesh Kumar K.V 已提交
4586
	ext4_lblk_t last_block;
A
Alex Tomas 已提交
4587 4588 4589
	int err = 0;

	/*
4590 4591 4592
	 * TODO: optimization is possible here.
	 * Probably we need not scan at all,
	 * because page truncation is enough.
A
Alex Tomas 已提交
4593 4594 4595 4596
	 */

	/* we have to know where to truncate from in crash case */
	EXT4_I(inode)->i_disksize = inode->i_size;
4597 4598 4599
	err = ext4_mark_inode_dirty(handle, inode);
	if (err)
		return err;
A
Alex Tomas 已提交
4600 4601 4602

	last_block = (inode->i_size + sb->s_blocksize - 1)
			>> EXT4_BLOCK_SIZE_BITS(sb);
4603
retry:
4604 4605
	err = ext4_es_remove_extent(inode, last_block,
				    EXT_MAX_BLOCKS - last_block);
4606
	if (err == -ENOMEM) {
4607 4608 4609 4610
		cond_resched();
		congestion_wait(BLK_RW_ASYNC, HZ/50);
		goto retry;
	}
4611 4612 4613
	if (err)
		return err;
	return ext4_ext_remove_space(inode, last_block, EXT_MAX_BLOCKS - 1);
A
Alex Tomas 已提交
4614 4615
}

4616
static int ext4_alloc_file_blocks(struct file *file, ext4_lblk_t offset,
4617
				  ext4_lblk_t len, loff_t new_size,
4618
				  int flags)
4619 4620 4621 4622 4623 4624
{
	struct inode *inode = file_inode(file);
	handle_t *handle;
	int ret = 0;
	int ret2 = 0;
	int retries = 0;
4625
	int depth = 0;
4626 4627
	struct ext4_map_blocks map;
	unsigned int credits;
4628
	loff_t epos;
4629

4630
	BUG_ON(!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS));
4631
	map.m_lblk = offset;
4632
	map.m_len = len;
4633 4634 4635 4636 4637
	/*
	 * Don't normalize the request if it can fit in one extent so
	 * that it doesn't get unnecessarily split into multiple
	 * extents.
	 */
4638
	if (len <= EXT_UNWRITTEN_MAX_LEN)
4639 4640 4641 4642 4643 4644
		flags |= EXT4_GET_BLOCKS_NO_NORMALIZE;

	/*
	 * credits to insert 1 extent into extent tree
	 */
	credits = ext4_chunk_trans_blocks(inode, len);
4645
	depth = ext_depth(inode);
4646 4647

retry:
4648
	while (ret >= 0 && len) {
4649 4650 4651
		/*
		 * Recalculate credits when extent tree depth changes.
		 */
4652
		if (depth != ext_depth(inode)) {
4653 4654 4655 4656
			credits = ext4_chunk_trans_blocks(inode, len);
			depth = ext_depth(inode);
		}

4657 4658 4659 4660 4661 4662 4663 4664 4665 4666 4667 4668 4669 4670 4671 4672
		handle = ext4_journal_start(inode, EXT4_HT_MAP_BLOCKS,
					    credits);
		if (IS_ERR(handle)) {
			ret = PTR_ERR(handle);
			break;
		}
		ret = ext4_map_blocks(handle, inode, &map, flags);
		if (ret <= 0) {
			ext4_debug("inode #%lu: block %u: len %u: "
				   "ext4_ext_map_blocks returned %d",
				   inode->i_ino, map.m_lblk,
				   map.m_len, ret);
			ext4_mark_inode_dirty(handle, inode);
			ret2 = ext4_journal_stop(handle);
			break;
		}
4673 4674 4675
		map.m_lblk += ret;
		map.m_len = len = len - ret;
		epos = (loff_t)map.m_lblk << inode->i_blkbits;
4676
		inode->i_ctime = current_time(inode);
4677 4678 4679 4680 4681 4682 4683 4684 4685 4686 4687
		if (new_size) {
			if (epos > new_size)
				epos = new_size;
			if (ext4_update_inode_size(inode, epos) & 0x1)
				inode->i_mtime = inode->i_ctime;
		} else {
			if (epos > inode->i_size)
				ext4_set_inode_flag(inode,
						    EXT4_INODE_EOFBLOCKS);
		}
		ext4_mark_inode_dirty(handle, inode);
4688
		ext4_update_inode_fsync_trans(handle, inode, 1);
4689 4690 4691 4692 4693 4694 4695 4696 4697 4698 4699 4700 4701
		ret2 = ext4_journal_stop(handle);
		if (ret2)
			break;
	}
	if (ret == -ENOSPC &&
			ext4_should_retry_alloc(inode->i_sb, &retries)) {
		ret = 0;
		goto retry;
	}

	return ret > 0 ? ret2 : ret;
}

4702 4703 4704 4705 4706 4707 4708 4709 4710
static long ext4_zero_range(struct file *file, loff_t offset,
			    loff_t len, int mode)
{
	struct inode *inode = file_inode(file);
	handle_t *handle = NULL;
	unsigned int max_blocks;
	loff_t new_size = 0;
	int ret = 0;
	int flags;
4711
	int credits;
4712
	int partial_begin, partial_end;
4713 4714 4715 4716 4717 4718
	loff_t start, end;
	ext4_lblk_t lblk;
	unsigned int blkbits = inode->i_blkbits;

	trace_ext4_zero_range(inode, offset, len, mode);

4719 4720 4721
	if (!S_ISREG(inode->i_mode))
		return -EINVAL;

4722 4723 4724 4725 4726 4727 4728
	/* Call ext4_force_commit to flush all data in case of data=journal. */
	if (ext4_should_journal_data(inode)) {
		ret = ext4_force_commit(inode->i_sb);
		if (ret)
			return ret;
	}

4729 4730 4731 4732 4733 4734 4735 4736 4737 4738 4739
	/*
	 * Round up offset. This is not fallocate, we neet to zero out
	 * blocks, so convert interior block aligned part of the range to
	 * unwritten and possibly manually zero out unaligned parts of the
	 * range.
	 */
	start = round_up(offset, 1 << blkbits);
	end = round_down((offset + len), 1 << blkbits);

	if (start < offset || end > offset + len)
		return -EINVAL;
4740 4741
	partial_begin = offset & ((1 << blkbits) - 1);
	partial_end = (offset + len) & ((1 << blkbits) - 1);
4742 4743 4744 4745 4746 4747 4748 4749

	lblk = start >> blkbits;
	max_blocks = (end >> blkbits);
	if (max_blocks < lblk)
		max_blocks = 0;
	else
		max_blocks -= lblk;

A
Al Viro 已提交
4750
	inode_lock(inode);
4751 4752 4753 4754 4755 4756 4757 4758 4759 4760

	/*
	 * Indirect files do not support unwritten extnets
	 */
	if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))) {
		ret = -EOPNOTSUPP;
		goto out_mutex;
	}

	if (!(mode & FALLOC_FL_KEEP_SIZE) &&
4761 4762
	    (offset + len > i_size_read(inode) ||
	     offset + len > EXT4_I(inode)->i_disksize)) {
4763 4764 4765 4766 4767 4768
		new_size = offset + len;
		ret = inode_newsize_ok(inode, new_size);
		if (ret)
			goto out_mutex;
	}

4769 4770 4771 4772
	flags = EXT4_GET_BLOCKS_CREATE_UNWRIT_EXT;
	if (mode & FALLOC_FL_KEEP_SIZE)
		flags |= EXT4_GET_BLOCKS_KEEP_SIZE;

4773 4774 4775
	/* Wait all existing dio workers, newcomers will block on i_mutex */
	inode_dio_wait(inode);

4776 4777 4778 4779 4780 4781
	/* Preallocate the range including the unaligned edges */
	if (partial_begin || partial_end) {
		ret = ext4_alloc_file_blocks(file,
				round_down(offset, 1 << blkbits) >> blkbits,
				(round_up((offset + len), 1 << blkbits) -
				 round_down(offset, 1 << blkbits)) >> blkbits,
4782
				new_size, flags);
4783
		if (ret)
4784
			goto out_mutex;
4785 4786 4787 4788

	}

	/* Zero range excluding the unaligned edges */
4789
	if (max_blocks > 0) {
4790 4791
		flags |= (EXT4_GET_BLOCKS_CONVERT_UNWRITTEN |
			  EXT4_EX_NOCACHE);
4792

4793 4794 4795 4796 4797
		/*
		 * Prevent page faults from reinstantiating pages we have
		 * released from page cache.
		 */
		down_write(&EXT4_I(inode)->i_mmap_sem);
4798 4799 4800 4801 4802 4803 4804

		ret = ext4_break_layouts(inode);
		if (ret) {
			up_write(&EXT4_I(inode)->i_mmap_sem);
			goto out_mutex;
		}

4805 4806 4807
		ret = ext4_update_disksize_before_punch(inode, offset, len);
		if (ret) {
			up_write(&EXT4_I(inode)->i_mmap_sem);
4808
			goto out_mutex;
4809
		}
4810 4811
		/* Now release the pages and zero block aligned part of pages */
		truncate_pagecache_range(inode, start, end - 1);
4812
		inode->i_mtime = inode->i_ctime = current_time(inode);
4813

4814
		ret = ext4_alloc_file_blocks(file, lblk, max_blocks, new_size,
4815
					     flags);
4816
		up_write(&EXT4_I(inode)->i_mmap_sem);
4817
		if (ret)
4818
			goto out_mutex;
4819
	}
4820
	if (!partial_begin && !partial_end)
4821
		goto out_mutex;
4822

4823 4824 4825 4826 4827 4828 4829 4830
	/*
	 * In worst case we have to writeout two nonadjacent unwritten
	 * blocks and update the inode
	 */
	credits = (2 * ext4_ext_index_trans_blocks(inode, 2)) + 1;
	if (ext4_should_journal_data(inode))
		credits += 2;
	handle = ext4_journal_start(inode, EXT4_HT_MISC, credits);
4831 4832 4833
	if (IS_ERR(handle)) {
		ret = PTR_ERR(handle);
		ext4_std_error(inode->i_sb, ret);
4834
		goto out_mutex;
4835 4836
	}

4837
	inode->i_mtime = inode->i_ctime = current_time(inode);
4838
	if (new_size) {
4839
		ext4_update_inode_size(inode, new_size);
4840
	} else {
4841 4842 4843 4844 4845 4846 4847 4848 4849 4850 4851
		/*
		* Mark that we allocate beyond EOF so the subsequent truncate
		* can proceed even if the new size is the same as i_size.
		*/
		if ((offset + len) > i_size_read(inode))
			ext4_set_inode_flag(inode, EXT4_INODE_EOFBLOCKS);
	}
	ext4_mark_inode_dirty(handle, inode);

	/* Zero out partial block at the edges of the range */
	ret = ext4_zero_partial_blocks(handle, inode, offset, len);
4852 4853
	if (ret >= 0)
		ext4_update_inode_fsync_trans(handle, inode, 1);
4854 4855 4856 4857 4858 4859

	if (file->f_flags & O_SYNC)
		ext4_handle_sync(handle);

	ext4_journal_stop(handle);
out_mutex:
A
Al Viro 已提交
4860
	inode_unlock(inode);
4861 4862 4863
	return ret;
}

A
Amit Arora 已提交
4864
/*
4865
 * preallocate space for a file. This implements ext4's fallocate file
A
Amit Arora 已提交
4866 4867 4868 4869 4870
 * operation, which gets called from sys_fallocate system call.
 * For block-mapped files, posix_fallocate should fall back to the method
 * of writing zeroes to the required new blocks (the same behavior which is
 * expected for file systems which do not support fallocate() system call).
 */
4871
long ext4_fallocate(struct file *file, int mode, loff_t offset, loff_t len)
A
Amit Arora 已提交
4872
{
A
Al Viro 已提交
4873
	struct inode *inode = file_inode(file);
4874
	loff_t new_size = 0;
4875
	unsigned int max_blocks;
A
Amit Arora 已提交
4876
	int ret = 0;
4877
	int flags;
4878 4879
	ext4_lblk_t lblk;
	unsigned int blkbits = inode->i_blkbits;
A
Amit Arora 已提交
4880

4881 4882 4883 4884 4885 4886 4887 4888 4889 4890 4891
	/*
	 * Encrypted inodes can't handle collapse range or insert
	 * range since we would need to re-encrypt blocks with a
	 * different IV or XTS tweak (which are based on the logical
	 * block number).
	 *
	 * XXX It's not clear why zero range isn't working, but we'll
	 * leave it disabled for encrypted inodes for now.  This is a
	 * bug we should fix....
	 */
	if (ext4_encrypted_inode(inode) &&
4892 4893
	    (mode & (FALLOC_FL_COLLAPSE_RANGE | FALLOC_FL_INSERT_RANGE |
		     FALLOC_FL_ZERO_RANGE)))
4894 4895
		return -EOPNOTSUPP;

4896
	/* Return error if mode is not supported */
4897
	if (mode & ~(FALLOC_FL_KEEP_SIZE | FALLOC_FL_PUNCH_HOLE |
4898 4899
		     FALLOC_FL_COLLAPSE_RANGE | FALLOC_FL_ZERO_RANGE |
		     FALLOC_FL_INSERT_RANGE))
4900 4901 4902
		return -EOPNOTSUPP;

	if (mode & FALLOC_FL_PUNCH_HOLE)
4903
		return ext4_punch_hole(inode, offset, len);
4904

4905 4906 4907 4908
	ret = ext4_convert_inline_data(inode);
	if (ret)
		return ret;

4909 4910 4911
	if (mode & FALLOC_FL_COLLAPSE_RANGE)
		return ext4_collapse_range(inode, offset, len);

4912 4913 4914
	if (mode & FALLOC_FL_INSERT_RANGE)
		return ext4_insert_range(inode, offset, len);

4915 4916 4917
	if (mode & FALLOC_FL_ZERO_RANGE)
		return ext4_zero_range(file, offset, len, mode);

4918
	trace_ext4_fallocate_enter(inode, offset, len, mode);
4919 4920
	lblk = offset >> blkbits;

4921
	max_blocks = EXT4_MAX_BLOCKS(len, offset, blkbits);
4922
	flags = EXT4_GET_BLOCKS_CREATE_UNWRIT_EXT;
4923 4924 4925
	if (mode & FALLOC_FL_KEEP_SIZE)
		flags |= EXT4_GET_BLOCKS_KEEP_SIZE;

A
Al Viro 已提交
4926
	inode_lock(inode);
4927

4928 4929 4930 4931 4932 4933 4934 4935
	/*
	 * We only support preallocation for extent-based files only
	 */
	if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))) {
		ret = -EOPNOTSUPP;
		goto out;
	}

4936
	if (!(mode & FALLOC_FL_KEEP_SIZE) &&
4937 4938
	    (offset + len > i_size_read(inode) ||
	     offset + len > EXT4_I(inode)->i_disksize)) {
4939 4940 4941 4942
		new_size = offset + len;
		ret = inode_newsize_ok(inode, new_size);
		if (ret)
			goto out;
4943
	}
4944

4945 4946 4947
	/* Wait all existing dio workers, newcomers will block on i_mutex */
	inode_dio_wait(inode);

4948
	ret = ext4_alloc_file_blocks(file, lblk, max_blocks, new_size, flags);
4949 4950
	if (ret)
		goto out;
4951

4952 4953 4954
	if (file->f_flags & O_SYNC && EXT4_SB(inode->i_sb)->s_journal) {
		ret = jbd2_complete_transaction(EXT4_SB(inode->i_sb)->s_journal,
						EXT4_I(inode)->i_sync_tid);
4955 4956
	}
out:
A
Al Viro 已提交
4957
	inode_unlock(inode);
4958 4959
	trace_ext4_fallocate_exit(inode, offset, max_blocks, ret);
	return ret;
A
Amit Arora 已提交
4960
}
4961

4962 4963 4964 4965 4966 4967 4968 4969
/*
 * This function convert a range of blocks to written extents
 * The caller of this function will pass the start offset and the size.
 * all unwritten extents within this range will be converted to
 * written extents.
 *
 * This function is called from the direct IO end io call back
 * function, to convert the fallocated extents after IO is completed.
4970
 * Returns 0 on success.
4971
 */
4972 4973
int ext4_convert_unwritten_extents(handle_t *handle, struct inode *inode,
				   loff_t offset, ssize_t len)
4974 4975 4976 4977
{
	unsigned int max_blocks;
	int ret = 0;
	int ret2 = 0;
4978
	struct ext4_map_blocks map;
4979 4980
	unsigned int credits, blkbits = inode->i_blkbits;

4981
	map.m_lblk = offset >> blkbits;
4982 4983
	max_blocks = EXT4_MAX_BLOCKS(len, offset, blkbits);

4984
	/*
4985 4986 4987
	 * This is somewhat ugly but the idea is clear: When transaction is
	 * reserved, everything goes into it. Otherwise we rather start several
	 * smaller transactions for conversion of each extent separately.
4988
	 */
4989 4990 4991 4992 4993 4994 4995 4996 4997 4998 4999 5000
	if (handle) {
		handle = ext4_journal_start_reserved(handle,
						     EXT4_HT_EXT_CONVERT);
		if (IS_ERR(handle))
			return PTR_ERR(handle);
		credits = 0;
	} else {
		/*
		 * credits to insert 1 extent into extent tree
		 */
		credits = ext4_chunk_trans_blocks(inode, max_blocks);
	}
5001
	while (ret >= 0 && ret < max_blocks) {
5002 5003
		map.m_lblk += ret;
		map.m_len = (max_blocks -= ret);
5004 5005 5006 5007 5008 5009 5010
		if (credits) {
			handle = ext4_journal_start(inode, EXT4_HT_MAP_BLOCKS,
						    credits);
			if (IS_ERR(handle)) {
				ret = PTR_ERR(handle);
				break;
			}
5011
		}
5012
		ret = ext4_map_blocks(handle, inode, &map,
5013
				      EXT4_GET_BLOCKS_IO_CONVERT_EXT);
5014 5015 5016 5017 5018 5019
		if (ret <= 0)
			ext4_warning(inode->i_sb,
				     "inode #%lu: block %u: len %u: "
				     "ext4_ext_map_blocks returned %d",
				     inode->i_ino, map.m_lblk,
				     map.m_len, ret);
5020
		ext4_mark_inode_dirty(handle, inode);
5021 5022 5023
		if (credits)
			ret2 = ext4_journal_stop(handle);
		if (ret <= 0 || ret2)
5024 5025
			break;
	}
5026 5027
	if (!credits)
		ret2 = ext4_journal_stop(handle);
5028 5029
	return ret > 0 ? ret2 : ret;
}
5030

5031
/*
Z
Zheng Liu 已提交
5032 5033
 * If newes is not existing extent (newes->ec_pblk equals zero) find
 * delayed extent at start of newes and update newes accordingly and
5034 5035
 * return start of the next delayed extent.
 *
Z
Zheng Liu 已提交
5036
 * If newes is existing extent (newes->ec_pblk is not equal zero)
5037
 * return start of next delayed extent or EXT_MAX_BLOCKS if no delayed
Z
Zheng Liu 已提交
5038
 * extent found. Leave newes unmodified.
5039
 */
5040
static int ext4_find_delayed_extent(struct inode *inode,
Z
Zheng Liu 已提交
5041
				    struct extent_status *newes)
5042
{
5043
	struct extent_status es;
5044
	ext4_lblk_t block, next_del;
5045

Z
Zheng Liu 已提交
5046
	if (newes->es_pblk == 0) {
5047 5048 5049 5050
		ext4_es_find_extent_range(inode, &ext4_es_is_delayed,
					  newes->es_lblk,
					  newes->es_lblk + newes->es_len - 1,
					  &es);
Y
Yan, Zheng 已提交
5051

5052
		/*
Z
Zheng Liu 已提交
5053
		 * No extent in extent-tree contains block @newes->es_pblk,
5054 5055
		 * then the block may stay in 1)a hole or 2)delayed-extent.
		 */
Z
Zheng Liu 已提交
5056
		if (es.es_len == 0)
5057
			/* A hole found. */
5058
			return 0;
5059

Z
Zheng Liu 已提交
5060
		if (es.es_lblk > newes->es_lblk) {
5061
			/* A hole found. */
Z
Zheng Liu 已提交
5062 5063
			newes->es_len = min(es.es_lblk - newes->es_lblk,
					    newes->es_len);
5064
			return 0;
5065
		}
5066

Z
Zheng Liu 已提交
5067
		newes->es_len = es.es_lblk + es.es_len - newes->es_lblk;
5068 5069
	}

Z
Zheng Liu 已提交
5070
	block = newes->es_lblk + newes->es_len;
5071 5072
	ext4_es_find_extent_range(inode, &ext4_es_is_delayed, block,
				  EXT_MAX_BLOCKS, &es);
5073 5074 5075 5076 5077
	if (es.es_len == 0)
		next_del = EXT_MAX_BLOCKS;
	else
		next_del = es.es_lblk;

5078
	return next_del;
5079 5080 5081 5082
}
/* fiemap flags we can handle specified here */
#define EXT4_FIEMAP_FLAGS	(FIEMAP_FLAG_SYNC|FIEMAP_FLAG_XATTR)

A
Aneesh Kumar K.V 已提交
5083 5084
static int ext4_xattr_fiemap(struct inode *inode,
				struct fiemap_extent_info *fieinfo)
5085 5086 5087 5088 5089 5090 5091 5092
{
	__u64 physical = 0;
	__u64 length;
	__u32 flags = FIEMAP_EXTENT_LAST;
	int blockbits = inode->i_sb->s_blocksize_bits;
	int error = 0;

	/* in-inode? */
5093
	if (ext4_test_inode_state(inode, EXT4_STATE_XATTR)) {
5094 5095 5096 5097 5098 5099
		struct ext4_iloc iloc;
		int offset;	/* offset of xattr in inode */

		error = ext4_get_inode_loc(inode, &iloc);
		if (error)
			return error;
5100
		physical = (__u64)iloc.bh->b_blocknr << blockbits;
5101 5102 5103 5104 5105
		offset = EXT4_GOOD_OLD_INODE_SIZE +
				EXT4_I(inode)->i_extra_isize;
		physical += offset;
		length = EXT4_SB(inode->i_sb)->s_inode_size - offset;
		flags |= FIEMAP_EXTENT_DATA_INLINE;
5106
		brelse(iloc.bh);
5107
	} else { /* external block */
5108
		physical = (__u64)EXT4_I(inode)->i_file_acl << blockbits;
5109 5110 5111 5112 5113 5114 5115 5116 5117 5118 5119 5120 5121 5122 5123
		length = inode->i_sb->s_blocksize;
	}

	if (physical)
		error = fiemap_fill_next_extent(fieinfo, 0, physical,
						length, flags);
	return (error < 0 ? error : 0);
}

int ext4_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
		__u64 start, __u64 len)
{
	ext4_lblk_t start_blk;
	int error = 0;

T
Tao Ma 已提交
5124 5125 5126
	if (ext4_has_inline_data(inode)) {
		int has_inline = 1;

5127 5128
		error = ext4_inline_data_fiemap(inode, fieinfo, &has_inline,
						start, len);
T
Tao Ma 已提交
5129 5130 5131 5132 5133

		if (has_inline)
			return error;
	}

5134 5135 5136 5137 5138 5139
	if (fieinfo->fi_flags & FIEMAP_FLAG_CACHE) {
		error = ext4_ext_precache(inode);
		if (error)
			return error;
	}

5140
	/* fallback to generic here if not in extents fmt */
5141
	if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)))
5142 5143
		return generic_block_fiemap(inode, fieinfo, start, len,
			ext4_get_block);
5144 5145 5146 5147 5148 5149 5150

	if (fiemap_check_flags(fieinfo, EXT4_FIEMAP_FLAGS))
		return -EBADR;

	if (fieinfo->fi_flags & FIEMAP_FLAG_XATTR) {
		error = ext4_xattr_fiemap(inode, fieinfo);
	} else {
5151 5152 5153
		ext4_lblk_t len_blks;
		__u64 last_blk;

5154
		start_blk = start >> inode->i_sb->s_blocksize_bits;
5155
		last_blk = (start + len - 1) >> inode->i_sb->s_blocksize_bits;
5156 5157
		if (last_blk >= EXT_MAX_BLOCKS)
			last_blk = EXT_MAX_BLOCKS-1;
5158
		len_blks = ((ext4_lblk_t) last_blk) - start_blk + 1;
5159 5160

		/*
5161 5162
		 * Walk the extent tree gathering extent information
		 * and pushing extents back to the user.
5163
		 */
5164 5165
		error = ext4_fill_fiemap_extents(inode, start_blk,
						 len_blks, fieinfo);
5166 5167 5168
	}
	return error;
}
5169 5170 5171 5172 5173 5174 5175 5176 5177 5178 5179 5180 5181 5182 5183 5184 5185 5186 5187 5188 5189 5190 5191 5192 5193 5194 5195 5196 5197 5198 5199 5200 5201 5202 5203 5204 5205

/*
 * ext4_access_path:
 * Function to access the path buffer for marking it dirty.
 * It also checks if there are sufficient credits left in the journal handle
 * to update path.
 */
static int
ext4_access_path(handle_t *handle, struct inode *inode,
		struct ext4_ext_path *path)
{
	int credits, err;

	if (!ext4_handle_valid(handle))
		return 0;

	/*
	 * Check if need to extend journal credits
	 * 3 for leaf, sb, and inode plus 2 (bmap and group
	 * descriptor) for each block group; assume two block
	 * groups
	 */
	if (handle->h_buffer_credits < 7) {
		credits = ext4_writepage_trans_blocks(inode);
		err = ext4_ext_truncate_extend_restart(handle, inode, credits);
		/* EAGAIN is success */
		if (err && err != -EAGAIN)
			return err;
	}

	err = ext4_ext_get_access(handle, inode, path);
	return err;
}

/*
 * ext4_ext_shift_path_extents:
 * Shift the extents of a path structure lying between path[depth].p_ext
5206 5207
 * and EXT_LAST_EXTENT(path[depth].p_hdr), by @shift blocks. @SHIFT tells
 * if it is right shift or left shift operation.
5208 5209 5210 5211
 */
static int
ext4_ext_shift_path_extents(struct ext4_ext_path *path, ext4_lblk_t shift,
			    struct inode *inode, handle_t *handle,
5212
			    enum SHIFT_DIRECTION SHIFT)
5213 5214 5215 5216 5217 5218 5219 5220 5221 5222
{
	int depth, err = 0;
	struct ext4_extent *ex_start, *ex_last;
	bool update = 0;
	depth = path->p_depth;

	while (depth >= 0) {
		if (depth == path->p_depth) {
			ex_start = path[depth].p_ext;
			if (!ex_start)
5223
				return -EFSCORRUPTED;
5224 5225 5226 5227 5228 5229 5230 5231 5232 5233 5234

			ex_last = EXT_LAST_EXTENT(path[depth].p_hdr);

			err = ext4_access_path(handle, inode, path + depth);
			if (err)
				goto out;

			if (ex_start == EXT_FIRST_EXTENT(path[depth].p_hdr))
				update = 1;

			while (ex_start <= ex_last) {
5235 5236 5237 5238 5239 5240 5241 5242 5243 5244 5245 5246 5247 5248 5249 5250
				if (SHIFT == SHIFT_LEFT) {
					le32_add_cpu(&ex_start->ee_block,
						-shift);
					/* Try to merge to the left. */
					if ((ex_start >
					    EXT_FIRST_EXTENT(path[depth].p_hdr))
					    &&
					    ext4_ext_try_to_merge_right(inode,
					    path, ex_start - 1))
						ex_last--;
					else
						ex_start++;
				} else {
					le32_add_cpu(&ex_last->ee_block, shift);
					ext4_ext_try_to_merge_right(inode, path,
						ex_last);
5251
					ex_last--;
5252
				}
5253 5254 5255 5256 5257 5258 5259 5260 5261 5262 5263 5264 5265 5266
			}
			err = ext4_ext_dirty(handle, inode, path + depth);
			if (err)
				goto out;

			if (--depth < 0 || !update)
				break;
		}

		/* Update index too */
		err = ext4_access_path(handle, inode, path + depth);
		if (err)
			goto out;

5267 5268 5269 5270
		if (SHIFT == SHIFT_LEFT)
			le32_add_cpu(&path[depth].p_idx->ei_block, -shift);
		else
			le32_add_cpu(&path[depth].p_idx->ei_block, shift);
5271 5272 5273 5274 5275 5276 5277 5278 5279 5280 5281 5282 5283 5284 5285 5286 5287
		err = ext4_ext_dirty(handle, inode, path + depth);
		if (err)
			goto out;

		/* we are done if current index is not a starting index */
		if (path[depth].p_idx != EXT_FIRST_INDEX(path[depth].p_hdr))
			break;

		depth--;
	}

out:
	return err;
}

/*
 * ext4_ext_shift_extents:
5288 5289 5290
 * All the extents which lies in the range from @start to the last allocated
 * block for the @inode are shifted either towards left or right (depending
 * upon @SHIFT) by @shift blocks.
5291 5292 5293 5294
 * On success, 0 is returned, error otherwise.
 */
static int
ext4_ext_shift_extents(struct inode *inode, handle_t *handle,
5295 5296
		       ext4_lblk_t start, ext4_lblk_t shift,
		       enum SHIFT_DIRECTION SHIFT)
5297 5298 5299 5300
{
	struct ext4_ext_path *path;
	int ret = 0, depth;
	struct ext4_extent *extent;
5301
	ext4_lblk_t stop, *iterator, ex_start, ex_end;
5302 5303

	/* Let path point to the last extent */
5304 5305
	path = ext4_find_extent(inode, EXT_MAX_BLOCKS - 1, NULL,
				EXT4_EX_NOCACHE);
5306 5307 5308 5309 5310
	if (IS_ERR(path))
		return PTR_ERR(path);

	depth = path->p_depth;
	extent = path[depth].p_ext;
5311 5312
	if (!extent)
		goto out;
5313

5314
	stop = le32_to_cpu(extent->ee_block);
5315

5316
       /*
5317 5318 5319
	* For left shifts, make sure the hole on the left is big enough to
	* accommodate the shift.  For right shifts, make sure the last extent
	* won't be shifted beyond EXT_MAX_BLOCKS.
5320 5321
	*/
	if (SHIFT == SHIFT_LEFT) {
5322 5323
		path = ext4_find_extent(inode, start - 1, &path,
					EXT4_EX_NOCACHE);
5324 5325 5326 5327 5328 5329 5330 5331 5332 5333 5334 5335
		if (IS_ERR(path))
			return PTR_ERR(path);
		depth = path->p_depth;
		extent =  path[depth].p_ext;
		if (extent) {
			ex_start = le32_to_cpu(extent->ee_block);
			ex_end = le32_to_cpu(extent->ee_block) +
				ext4_ext_get_actual_len(extent);
		} else {
			ex_start = 0;
			ex_end = 0;
		}
5336

5337 5338
		if ((start == ex_start && shift > ex_start) ||
		    (shift > start - ex_end)) {
5339 5340 5341 5342 5343 5344 5345 5346
			ret = -EINVAL;
			goto out;
		}
	} else {
		if (shift > EXT_MAX_BLOCKS -
		    (stop + ext4_ext_get_actual_len(extent))) {
			ret = -EINVAL;
			goto out;
5347
		}
5348
	}
5349

5350 5351 5352 5353 5354 5355 5356 5357 5358
	/*
	 * In case of left shift, iterator points to start and it is increased
	 * till we reach stop. In case of right shift, iterator points to stop
	 * and it is decreased till we reach start.
	 */
	if (SHIFT == SHIFT_LEFT)
		iterator = &start;
	else
		iterator = &stop;
5359

5360 5361 5362 5363 5364 5365
	/*
	 * Its safe to start updating extents.  Start and stop are unsigned, so
	 * in case of right shift if extent with 0 block is reached, iterator
	 * becomes NULL to indicate the end of the loop.
	 */
	while (iterator && start <= stop) {
5366 5367
		path = ext4_find_extent(inode, *iterator, &path,
					EXT4_EX_NOCACHE);
5368 5369 5370 5371
		if (IS_ERR(path))
			return PTR_ERR(path);
		depth = path->p_depth;
		extent = path[depth].p_ext;
5372 5373
		if (!extent) {
			EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
5374
					 (unsigned long) *iterator);
5375
			return -EFSCORRUPTED;
5376
		}
5377 5378
		if (SHIFT == SHIFT_LEFT && *iterator >
		    le32_to_cpu(extent->ee_block)) {
5379
			/* Hole, move to the next extent */
5380 5381 5382
			if (extent < EXT_LAST_EXTENT(path[depth].p_hdr)) {
				path[depth].p_ext++;
			} else {
5383
				*iterator = ext4_ext_next_allocated_block(path);
5384
				continue;
5385 5386
			}
		}
5387 5388 5389 5390 5391 5392 5393

		if (SHIFT == SHIFT_LEFT) {
			extent = EXT_LAST_EXTENT(path[depth].p_hdr);
			*iterator = le32_to_cpu(extent->ee_block) +
					ext4_ext_get_actual_len(extent);
		} else {
			extent = EXT_FIRST_EXTENT(path[depth].p_hdr);
5394 5395 5396 5397 5398
			if (le32_to_cpu(extent->ee_block) > 0)
				*iterator = le32_to_cpu(extent->ee_block) - 1;
			else
				/* Beginning is reached, end of the loop */
				iterator = NULL;
5399 5400 5401 5402 5403
			/* Update path extent in case we need to stop */
			while (le32_to_cpu(extent->ee_block) < start)
				extent++;
			path[depth].p_ext = extent;
		}
5404
		ret = ext4_ext_shift_path_extents(path, shift, inode,
5405
				handle, SHIFT);
5406 5407 5408
		if (ret)
			break;
	}
5409 5410 5411
out:
	ext4_ext_drop_refs(path);
	kfree(path);
5412 5413 5414 5415 5416 5417 5418 5419 5420 5421 5422 5423 5424 5425
	return ret;
}

/*
 * ext4_collapse_range:
 * This implements the fallocate's collapse range functionality for ext4
 * Returns: 0 and non-zero on error.
 */
int ext4_collapse_range(struct inode *inode, loff_t offset, loff_t len)
{
	struct super_block *sb = inode->i_sb;
	ext4_lblk_t punch_start, punch_stop;
	handle_t *handle;
	unsigned int credits;
5426
	loff_t new_size, ioffset;
5427 5428
	int ret;

5429 5430 5431 5432 5433 5434 5435 5436
	/*
	 * We need to test this early because xfstests assumes that a
	 * collapse range of (0, 1) will return EOPNOTSUPP if the file
	 * system does not support collapse range.
	 */
	if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
		return -EOPNOTSUPP;

5437
	/* Collapse range works only on fs block size aligned offsets. */
5438 5439
	if (offset & (EXT4_CLUSTER_SIZE(sb) - 1) ||
	    len & (EXT4_CLUSTER_SIZE(sb) - 1))
5440 5441 5442
		return -EINVAL;

	if (!S_ISREG(inode->i_mode))
5443
		return -EINVAL;
5444 5445 5446 5447 5448 5449

	trace_ext4_collapse_range(inode, offset, len);

	punch_start = offset >> EXT4_BLOCK_SIZE_BITS(sb);
	punch_stop = (offset + len) >> EXT4_BLOCK_SIZE_BITS(sb);

5450 5451 5452 5453 5454 5455 5456
	/* Call ext4_force_commit to flush all data in case of data=journal. */
	if (ext4_should_journal_data(inode)) {
		ret = ext4_force_commit(inode->i_sb);
		if (ret)
			return ret;
	}

A
Al Viro 已提交
5457
	inode_lock(inode);
5458 5459 5460 5461 5462 5463 5464 5465 5466
	/*
	 * There is no need to overlap collapse range with EOF, in which case
	 * it is effectively a truncate operation
	 */
	if (offset + len >= i_size_read(inode)) {
		ret = -EINVAL;
		goto out_mutex;
	}

5467 5468 5469 5470 5471 5472 5473 5474 5475
	/* Currently just for extent based files */
	if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)) {
		ret = -EOPNOTSUPP;
		goto out_mutex;
	}

	/* Wait for existing dio to complete */
	inode_dio_wait(inode);

5476 5477 5478 5479 5480
	/*
	 * Prevent page faults from reinstantiating pages we have released from
	 * page cache.
	 */
	down_write(&EXT4_I(inode)->i_mmap_sem);
5481 5482 5483 5484 5485

	ret = ext4_break_layouts(inode);
	if (ret)
		goto out_mmap;

5486 5487 5488 5489 5490 5491 5492 5493 5494 5495 5496 5497 5498 5499 5500 5501 5502 5503 5504 5505 5506
	/*
	 * Need to round down offset to be aligned with page size boundary
	 * for page size > block size.
	 */
	ioffset = round_down(offset, PAGE_SIZE);
	/*
	 * Write tail of the last page before removed range since it will get
	 * removed from the page cache below.
	 */
	ret = filemap_write_and_wait_range(inode->i_mapping, ioffset, offset);
	if (ret)
		goto out_mmap;
	/*
	 * Write data that will be shifted to preserve them when discarding
	 * page cache below. We are also protected from pages becoming dirty
	 * by i_mmap_sem.
	 */
	ret = filemap_write_and_wait_range(inode->i_mapping, offset + len,
					   LLONG_MAX);
	if (ret)
		goto out_mmap;
5507 5508
	truncate_pagecache(inode, ioffset);

5509 5510 5511 5512
	credits = ext4_writepage_trans_blocks(inode);
	handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, credits);
	if (IS_ERR(handle)) {
		ret = PTR_ERR(handle);
5513
		goto out_mmap;
5514 5515 5516 5517 5518 5519
	}

	down_write(&EXT4_I(inode)->i_data_sem);
	ext4_discard_preallocations(inode);

	ret = ext4_es_remove_extent(inode, punch_start,
5520
				    EXT_MAX_BLOCKS - punch_start);
5521 5522 5523 5524 5525 5526 5527 5528 5529 5530
	if (ret) {
		up_write(&EXT4_I(inode)->i_data_sem);
		goto out_stop;
	}

	ret = ext4_ext_remove_space(inode, punch_start, punch_stop - 1);
	if (ret) {
		up_write(&EXT4_I(inode)->i_data_sem);
		goto out_stop;
	}
5531
	ext4_discard_preallocations(inode);
5532 5533

	ret = ext4_ext_shift_extents(inode, handle, punch_stop,
5534
				     punch_stop - punch_start, SHIFT_LEFT);
5535 5536 5537 5538 5539 5540
	if (ret) {
		up_write(&EXT4_I(inode)->i_data_sem);
		goto out_stop;
	}

	new_size = i_size_read(inode) - len;
5541
	i_size_write(inode, new_size);
5542 5543 5544 5545 5546
	EXT4_I(inode)->i_disksize = new_size;

	up_write(&EXT4_I(inode)->i_data_sem);
	if (IS_SYNC(inode))
		ext4_handle_sync(handle);
5547
	inode->i_mtime = inode->i_ctime = current_time(inode);
5548
	ext4_mark_inode_dirty(handle, inode);
5549
	ext4_update_inode_fsync_trans(handle, inode, 1);
5550 5551 5552

out_stop:
	ext4_journal_stop(handle);
5553 5554
out_mmap:
	up_write(&EXT4_I(inode)->i_mmap_sem);
5555
out_mutex:
A
Al Viro 已提交
5556
	inode_unlock(inode);
5557 5558
	return ret;
}
5559

5560 5561 5562 5563 5564 5565 5566 5567 5568 5569 5570 5571 5572 5573 5574 5575 5576 5577 5578 5579 5580 5581 5582 5583 5584 5585 5586 5587 5588 5589 5590 5591 5592 5593 5594 5595 5596 5597 5598 5599 5600 5601 5602 5603 5604 5605 5606
/*
 * ext4_insert_range:
 * This function implements the FALLOC_FL_INSERT_RANGE flag of fallocate.
 * The data blocks starting from @offset to the EOF are shifted by @len
 * towards right to create a hole in the @inode. Inode size is increased
 * by len bytes.
 * Returns 0 on success, error otherwise.
 */
int ext4_insert_range(struct inode *inode, loff_t offset, loff_t len)
{
	struct super_block *sb = inode->i_sb;
	handle_t *handle;
	struct ext4_ext_path *path;
	struct ext4_extent *extent;
	ext4_lblk_t offset_lblk, len_lblk, ee_start_lblk = 0;
	unsigned int credits, ee_len;
	int ret = 0, depth, split_flag = 0;
	loff_t ioffset;

	/*
	 * We need to test this early because xfstests assumes that an
	 * insert range of (0, 1) will return EOPNOTSUPP if the file
	 * system does not support insert range.
	 */
	if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
		return -EOPNOTSUPP;

	/* Insert range works only on fs block size aligned offsets. */
	if (offset & (EXT4_CLUSTER_SIZE(sb) - 1) ||
			len & (EXT4_CLUSTER_SIZE(sb) - 1))
		return -EINVAL;

	if (!S_ISREG(inode->i_mode))
		return -EOPNOTSUPP;

	trace_ext4_insert_range(inode, offset, len);

	offset_lblk = offset >> EXT4_BLOCK_SIZE_BITS(sb);
	len_lblk = len >> EXT4_BLOCK_SIZE_BITS(sb);

	/* Call ext4_force_commit to flush all data in case of data=journal */
	if (ext4_should_journal_data(inode)) {
		ret = ext4_force_commit(inode->i_sb);
		if (ret)
			return ret;
	}

A
Al Viro 已提交
5607
	inode_lock(inode);
5608 5609 5610 5611 5612 5613 5614 5615 5616 5617 5618 5619 5620 5621 5622 5623 5624 5625 5626 5627 5628
	/* Currently just for extent based files */
	if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)) {
		ret = -EOPNOTSUPP;
		goto out_mutex;
	}

	/* Check for wrap through zero */
	if (inode->i_size + len > inode->i_sb->s_maxbytes) {
		ret = -EFBIG;
		goto out_mutex;
	}

	/* Offset should be less than i_size */
	if (offset >= i_size_read(inode)) {
		ret = -EINVAL;
		goto out_mutex;
	}

	/* Wait for existing dio to complete */
	inode_dio_wait(inode);

5629 5630 5631 5632 5633
	/*
	 * Prevent page faults from reinstantiating pages we have released from
	 * page cache.
	 */
	down_write(&EXT4_I(inode)->i_mmap_sem);
5634 5635 5636 5637 5638

	ret = ext4_break_layouts(inode);
	if (ret)
		goto out_mmap;

5639 5640 5641 5642 5643 5644 5645 5646 5647 5648
	/*
	 * Need to round down to align start offset to page size boundary
	 * for page size > block size.
	 */
	ioffset = round_down(offset, PAGE_SIZE);
	/* Write out all dirty pages */
	ret = filemap_write_and_wait_range(inode->i_mapping, ioffset,
			LLONG_MAX);
	if (ret)
		goto out_mmap;
5649 5650
	truncate_pagecache(inode, ioffset);

5651 5652 5653 5654
	credits = ext4_writepage_trans_blocks(inode);
	handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, credits);
	if (IS_ERR(handle)) {
		ret = PTR_ERR(handle);
5655
		goto out_mmap;
5656 5657 5658 5659 5660
	}

	/* Expand file to avoid data loss if there is error while shifting */
	inode->i_size += len;
	EXT4_I(inode)->i_disksize += len;
5661
	inode->i_mtime = inode->i_ctime = current_time(inode);
5662 5663 5664 5665 5666 5667 5668 5669 5670 5671 5672 5673 5674 5675 5676 5677 5678 5679 5680 5681 5682 5683 5684 5685 5686 5687 5688 5689 5690 5691 5692 5693 5694 5695 5696 5697 5698 5699 5700 5701 5702
	ret = ext4_mark_inode_dirty(handle, inode);
	if (ret)
		goto out_stop;

	down_write(&EXT4_I(inode)->i_data_sem);
	ext4_discard_preallocations(inode);

	path = ext4_find_extent(inode, offset_lblk, NULL, 0);
	if (IS_ERR(path)) {
		up_write(&EXT4_I(inode)->i_data_sem);
		goto out_stop;
	}

	depth = ext_depth(inode);
	extent = path[depth].p_ext;
	if (extent) {
		ee_start_lblk = le32_to_cpu(extent->ee_block);
		ee_len = ext4_ext_get_actual_len(extent);

		/*
		 * If offset_lblk is not the starting block of extent, split
		 * the extent @offset_lblk
		 */
		if ((offset_lblk > ee_start_lblk) &&
				(offset_lblk < (ee_start_lblk + ee_len))) {
			if (ext4_ext_is_unwritten(extent))
				split_flag = EXT4_EXT_MARK_UNWRIT1 |
					EXT4_EXT_MARK_UNWRIT2;
			ret = ext4_split_extent_at(handle, inode, &path,
					offset_lblk, split_flag,
					EXT4_EX_NOCACHE |
					EXT4_GET_BLOCKS_PRE_IO |
					EXT4_GET_BLOCKS_METADATA_NOFAIL);
		}

		ext4_ext_drop_refs(path);
		kfree(path);
		if (ret < 0) {
			up_write(&EXT4_I(inode)->i_data_sem);
			goto out_stop;
		}
5703 5704 5705
	} else {
		ext4_ext_drop_refs(path);
		kfree(path);
5706 5707 5708 5709 5710 5711 5712 5713 5714 5715 5716 5717 5718 5719 5720 5721 5722 5723 5724 5725
	}

	ret = ext4_es_remove_extent(inode, offset_lblk,
			EXT_MAX_BLOCKS - offset_lblk);
	if (ret) {
		up_write(&EXT4_I(inode)->i_data_sem);
		goto out_stop;
	}

	/*
	 * if offset_lblk lies in a hole which is at start of file, use
	 * ee_start_lblk to shift extents
	 */
	ret = ext4_ext_shift_extents(inode, handle,
		ee_start_lblk > offset_lblk ? ee_start_lblk : offset_lblk,
		len_lblk, SHIFT_RIGHT);

	up_write(&EXT4_I(inode)->i_data_sem);
	if (IS_SYNC(inode))
		ext4_handle_sync(handle);
5726 5727
	if (ret >= 0)
		ext4_update_inode_fsync_trans(handle, inode, 1);
5728 5729 5730

out_stop:
	ext4_journal_stop(handle);
5731 5732
out_mmap:
	up_write(&EXT4_I(inode)->i_mmap_sem);
5733
out_mutex:
A
Al Viro 已提交
5734
	inode_unlock(inode);
5735 5736 5737
	return ret;
}

5738 5739 5740 5741 5742 5743 5744 5745
/**
 * ext4_swap_extents - Swap extents between two inodes
 *
 * @inode1:	First inode
 * @inode2:	Second inode
 * @lblk1:	Start block for first inode
 * @lblk2:	Start block for second inode
 * @count:	Number of blocks to swap
5746
 * @unwritten: Mark second inode's extents as unwritten after swap
5747 5748 5749 5750 5751 5752 5753 5754 5755 5756 5757 5758 5759
 * @erp:	Pointer to save error value
 *
 * This helper routine does exactly what is promise "swap extents". All other
 * stuff such as page-cache locking consistency, bh mapping consistency or
 * extent's data copying must be performed by caller.
 * Locking:
 * 		i_mutex is held for both inodes
 * 		i_data_sem is locked for write for both inodes
 * Assumptions:
 *		All pages from requested range are locked for both inodes
 */
int
ext4_swap_extents(handle_t *handle, struct inode *inode1,
5760
		  struct inode *inode2, ext4_lblk_t lblk1, ext4_lblk_t lblk2,
5761 5762 5763 5764 5765 5766 5767 5768
		  ext4_lblk_t count, int unwritten, int *erp)
{
	struct ext4_ext_path *path1 = NULL;
	struct ext4_ext_path *path2 = NULL;
	int replaced_count = 0;

	BUG_ON(!rwsem_is_locked(&EXT4_I(inode1)->i_data_sem));
	BUG_ON(!rwsem_is_locked(&EXT4_I(inode2)->i_data_sem));
A
Al Viro 已提交
5769 5770
	BUG_ON(!inode_is_locked(inode1));
	BUG_ON(!inode_is_locked(inode2));
5771 5772

	*erp = ext4_es_remove_extent(inode1, lblk1, count);
5773
	if (unlikely(*erp))
5774 5775
		return 0;
	*erp = ext4_es_remove_extent(inode2, lblk2, count);
5776
	if (unlikely(*erp))
5777 5778 5779 5780 5781 5782 5783 5784
		return 0;

	while (count) {
		struct ext4_extent *ex1, *ex2, tmp_ex;
		ext4_lblk_t e1_blk, e2_blk;
		int e1_len, e2_len, len;
		int split = 0;

5785
		path1 = ext4_find_extent(inode1, lblk1, NULL, EXT4_EX_NOCACHE);
5786
		if (IS_ERR(path1)) {
5787
			*erp = PTR_ERR(path1);
5788 5789 5790 5791
			path1 = NULL;
		finish:
			count = 0;
			goto repeat;
5792
		}
5793
		path2 = ext4_find_extent(inode2, lblk2, NULL, EXT4_EX_NOCACHE);
5794
		if (IS_ERR(path2)) {
5795
			*erp = PTR_ERR(path2);
5796 5797
			path2 = NULL;
			goto finish;
5798 5799 5800 5801 5802
		}
		ex1 = path1[path1->p_depth].p_ext;
		ex2 = path2[path2->p_depth].p_ext;
		/* Do we have somthing to swap ? */
		if (unlikely(!ex2 || !ex1))
5803
			goto finish;
5804 5805 5806 5807 5808 5809 5810 5811 5812 5813 5814 5815 5816 5817 5818 5819 5820 5821

		e1_blk = le32_to_cpu(ex1->ee_block);
		e2_blk = le32_to_cpu(ex2->ee_block);
		e1_len = ext4_ext_get_actual_len(ex1);
		e2_len = ext4_ext_get_actual_len(ex2);

		/* Hole handling */
		if (!in_range(lblk1, e1_blk, e1_len) ||
		    !in_range(lblk2, e2_blk, e2_len)) {
			ext4_lblk_t next1, next2;

			/* if hole after extent, then go to next extent */
			next1 = ext4_ext_next_allocated_block(path1);
			next2 = ext4_ext_next_allocated_block(path2);
			/* If hole before extent, then shift to that extent */
			if (e1_blk > lblk1)
				next1 = e1_blk;
			if (e2_blk > lblk2)
5822
				next2 = e2_blk;
5823 5824
			/* Do we have something to swap */
			if (next1 == EXT_MAX_BLOCKS || next2 == EXT_MAX_BLOCKS)
5825
				goto finish;
5826 5827 5828 5829 5830 5831 5832 5833 5834 5835 5836 5837 5838 5839 5840 5841
			/* Move to the rightest boundary */
			len = next1 - lblk1;
			if (len < next2 - lblk2)
				len = next2 - lblk2;
			if (len > count)
				len = count;
			lblk1 += len;
			lblk2 += len;
			count -= len;
			goto repeat;
		}

		/* Prepare left boundary */
		if (e1_blk < lblk1) {
			split = 1;
			*erp = ext4_force_split_extent_at(handle, inode1,
5842
						&path1, lblk1, 0);
5843 5844
			if (unlikely(*erp))
				goto finish;
5845 5846 5847 5848
		}
		if (e2_blk < lblk2) {
			split = 1;
			*erp = ext4_force_split_extent_at(handle, inode2,
5849
						&path2,  lblk2, 0);
5850 5851
			if (unlikely(*erp))
				goto finish;
5852
		}
5853
		/* ext4_split_extent_at() may result in leaf extent split,
5854 5855 5856 5857 5858 5859 5860 5861 5862 5863 5864 5865 5866 5867
		 * path must to be revalidated. */
		if (split)
			goto repeat;

		/* Prepare right boundary */
		len = count;
		if (len > e1_blk + e1_len - lblk1)
			len = e1_blk + e1_len - lblk1;
		if (len > e2_blk + e2_len - lblk2)
			len = e2_blk + e2_len - lblk2;

		if (len != e1_len) {
			split = 1;
			*erp = ext4_force_split_extent_at(handle, inode1,
5868
						&path1, lblk1 + len, 0);
5869 5870
			if (unlikely(*erp))
				goto finish;
5871 5872 5873 5874
		}
		if (len != e2_len) {
			split = 1;
			*erp = ext4_force_split_extent_at(handle, inode2,
5875
						&path2, lblk2 + len, 0);
5876
			if (*erp)
5877
				goto finish;
5878
		}
5879
		/* ext4_split_extent_at() may result in leaf extent split,
5880 5881 5882 5883 5884 5885
		 * path must to be revalidated. */
		if (split)
			goto repeat;

		BUG_ON(e2_len != e1_len);
		*erp = ext4_ext_get_access(handle, inode1, path1 + path1->p_depth);
5886 5887
		if (unlikely(*erp))
			goto finish;
5888
		*erp = ext4_ext_get_access(handle, inode2, path2 + path2->p_depth);
5889 5890
		if (unlikely(*erp))
			goto finish;
5891 5892 5893 5894 5895 5896 5897 5898 5899 5900 5901 5902 5903 5904 5905 5906

		/* Both extents are fully inside boundaries. Swap it now */
		tmp_ex = *ex1;
		ext4_ext_store_pblock(ex1, ext4_ext_pblock(ex2));
		ext4_ext_store_pblock(ex2, ext4_ext_pblock(&tmp_ex));
		ex1->ee_len = cpu_to_le16(e2_len);
		ex2->ee_len = cpu_to_le16(e1_len);
		if (unwritten)
			ext4_ext_mark_unwritten(ex2);
		if (ext4_ext_is_unwritten(&tmp_ex))
			ext4_ext_mark_unwritten(ex1);

		ext4_ext_try_to_merge(handle, inode2, path2, ex2);
		ext4_ext_try_to_merge(handle, inode1, path1, ex1);
		*erp = ext4_ext_dirty(handle, inode2, path2 +
				      path2->p_depth);
5907 5908
		if (unlikely(*erp))
			goto finish;
5909 5910 5911 5912 5913 5914 5915 5916
		*erp = ext4_ext_dirty(handle, inode1, path1 +
				      path1->p_depth);
		/*
		 * Looks scarry ah..? second inode already points to new blocks,
		 * and it was successfully dirtied. But luckily error may happen
		 * only due to journal error, so full transaction will be
		 * aborted anyway.
		 */
5917 5918
		if (unlikely(*erp))
			goto finish;
5919 5920 5921 5922 5923 5924
		lblk1 += len;
		lblk2 += len;
		replaced_count += len;
		count -= len;

	repeat:
5925 5926 5927 5928 5929
		ext4_ext_drop_refs(path1);
		kfree(path1);
		ext4_ext_drop_refs(path2);
		kfree(path2);
		path1 = path2 = NULL;
5930 5931 5932
	}
	return replaced_count;
}