extents.c 106.2 KB
Newer Older
A
Alex Tomas 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
/*
 * 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>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public Licens
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-
 */

/*
 * 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/module.h>
#include <linux/fs.h>
#include <linux/time.h>
35
#include <linux/jbd2.h>
A
Alex Tomas 已提交
36 37 38 39 40
#include <linux/highuid.h>
#include <linux/pagemap.h>
#include <linux/quotaops.h>
#include <linux/string.h>
#include <linux/slab.h>
A
Amit Arora 已提交
41
#include <linux/falloc.h>
A
Alex Tomas 已提交
42
#include <asm/uaccess.h>
43
#include <linux/fiemap.h>
44 45
#include "ext4_jbd2.h"
#include "ext4_extents.h"
A
Alex Tomas 已提交
46

47 48
#include <trace/events/ext4.h>

A
Allison Henderson 已提交
49 50 51 52 53 54 55
static int ext4_split_extent(handle_t *handle,
				struct inode *inode,
				struct ext4_ext_path *path,
				struct ext4_map_blocks *map,
				int split_flag,
				int flags);

56 57 58
static int ext4_ext_truncate_extend_restart(handle_t *handle,
					    struct inode *inode,
					    int needed)
A
Alex Tomas 已提交
59 60 61
{
	int err;

62 63
	if (!ext4_handle_valid(handle))
		return 0;
A
Alex Tomas 已提交
64
	if (handle->h_buffer_credits > needed)
65 66
		return 0;
	err = ext4_journal_extend(handle, needed);
67
	if (err <= 0)
68
		return err;
69
	err = ext4_truncate_restart_trans(handle, inode, needed);
70 71
	if (err == 0)
		err = -EAGAIN;
72 73

	return err;
A
Alex Tomas 已提交
74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104
}

/*
 * 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 */
		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
 */
static int ext4_ext_dirty(handle_t *handle, struct inode *inode,
				struct ext4_ext_path *path)
{
	int err;
	if (path->p_bh) {
		/* path points to block */
105
		err = ext4_handle_dirty_metadata(handle, inode, path->p_bh);
A
Alex Tomas 已提交
106 107 108 109 110 111 112
	} else {
		/* path points to leaf/index in inode body */
		err = ext4_mark_inode_dirty(handle, inode);
	}
	return err;
}

113
static ext4_fsblk_t ext4_ext_find_goal(struct inode *inode,
A
Alex Tomas 已提交
114
			      struct ext4_ext_path *path,
A
Aneesh Kumar K.V 已提交
115
			      ext4_lblk_t block)
A
Alex Tomas 已提交
116 117
{
	struct ext4_inode_info *ei = EXT4_I(inode);
118
	ext4_fsblk_t bg_start;
119
	ext4_fsblk_t last_block;
120
	ext4_grpblk_t colour;
121 122
	ext4_group_t block_group;
	int flex_size = ext4_flex_bg_size(EXT4_SB(inode->i_sb));
A
Alex Tomas 已提交
123 124 125 126 127 128
	int depth;

	if (path) {
		struct ext4_extent *ex;
		depth = path->p_depth;

129 130 131 132 133 134 135 136 137 138 139 140 141 142
		/*
		 * 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 已提交
143
		 * especially if the latter case turns out to be
144 145
		 * common.
		 */
146
		ex = path[depth].p_ext;
147 148 149 150 151 152 153 154 155
		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 已提交
156

157 158
		/* it looks like index is empty;
		 * try to find starting block from index itself */
A
Alex Tomas 已提交
159 160 161 162 163
		if (path[depth].p_bh)
			return path[depth].p_bh->b_blocknr;
	}

	/* OK. use inode's group */
164 165 166 167
	block_group = ei->i_block_group;
	if (flex_size >= EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME) {
		/*
		 * If there are at least EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME
168 169
		 * block groups per flexgroup, reserve the first block
		 * group for directories and special files.  Regular
170
		 * files will start at the second block group.  This
171
		 * tends to speed up directory access and improves
172 173 174 175 176 177
		 * fsck times.
		 */
		block_group &= ~(flex_size-1);
		if (S_ISREG(inode->i_mode))
			block_group++;
	}
178
	bg_start = ext4_group_first_block_no(inode->i_sb, block_group);
179 180
	last_block = ext4_blocks_count(EXT4_SB(inode->i_sb)->s_es) - 1;

181 182 183 184 185 186 187
	/*
	 * If we are doing delayed allocation, we don't need take
	 * colour into account.
	 */
	if (test_opt(inode->i_sb, DELALLOC))
		return bg_start;

188 189
	if (bg_start + EXT4_BLOCKS_PER_GROUP(inode->i_sb) <= last_block)
		colour = (current->pid % 16) *
A
Alex Tomas 已提交
190
			(EXT4_BLOCKS_PER_GROUP(inode->i_sb) / 16);
191 192
	else
		colour = (current->pid % 16) * ((last_block - bg_start) / 16);
A
Alex Tomas 已提交
193 194 195
	return bg_start + colour + block;
}

A
Aneesh Kumar K.V 已提交
196 197 198
/*
 * Allocation for a meta data block
 */
199
static ext4_fsblk_t
A
Aneesh Kumar K.V 已提交
200
ext4_ext_new_meta_block(handle_t *handle, struct inode *inode,
A
Alex Tomas 已提交
201
			struct ext4_ext_path *path,
202
			struct ext4_extent *ex, int *err, unsigned int flags)
A
Alex Tomas 已提交
203
{
204
	ext4_fsblk_t goal, newblock;
A
Alex Tomas 已提交
205 206

	goal = ext4_ext_find_goal(inode, path, le32_to_cpu(ex->ee_block));
207 208
	newblock = ext4_new_meta_blocks(handle, inode, goal, flags,
					NULL, err);
A
Alex Tomas 已提交
209 210 211
	return newblock;
}

212
static inline int ext4_ext_space_block(struct inode *inode, int check)
A
Alex Tomas 已提交
213 214 215 216 217
{
	int size;

	size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
			/ sizeof(struct ext4_extent);
218
	if (!check) {
219
#ifdef AGGRESSIVE_TEST
220 221
		if (size > 6)
			size = 6;
A
Alex Tomas 已提交
222
#endif
223
	}
A
Alex Tomas 已提交
224 225 226
	return size;
}

227
static inline int ext4_ext_space_block_idx(struct inode *inode, int check)
A
Alex Tomas 已提交
228 229 230 231 232
{
	int size;

	size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
			/ sizeof(struct ext4_extent_idx);
233
	if (!check) {
234
#ifdef AGGRESSIVE_TEST
235 236
		if (size > 5)
			size = 5;
A
Alex Tomas 已提交
237
#endif
238
	}
A
Alex Tomas 已提交
239 240 241
	return size;
}

242
static inline int ext4_ext_space_root(struct inode *inode, int check)
A
Alex Tomas 已提交
243 244 245 246 247 248
{
	int size;

	size = sizeof(EXT4_I(inode)->i_data);
	size -= sizeof(struct ext4_extent_header);
	size /= sizeof(struct ext4_extent);
249
	if (!check) {
250
#ifdef AGGRESSIVE_TEST
251 252
		if (size > 3)
			size = 3;
A
Alex Tomas 已提交
253
#endif
254
	}
A
Alex Tomas 已提交
255 256 257
	return size;
}

258
static inline int ext4_ext_space_root_idx(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_idx);
265
	if (!check) {
266
#ifdef AGGRESSIVE_TEST
267 268
		if (size > 4)
			size = 4;
A
Alex Tomas 已提交
269
#endif
270
	}
A
Alex Tomas 已提交
271 272 273
	return size;
}

274 275 276 277 278
/*
 * Calculate the number of metadata blocks needed
 * to allocate @blocks
 * Worse case is one block per extent
 */
279
int ext4_ext_calc_metadata_amount(struct inode *inode, ext4_lblk_t lblock)
280
{
281 282
	struct ext4_inode_info *ei = EXT4_I(inode);
	int idxs, num = 0;
283

284 285
	idxs = ((inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
		/ sizeof(struct ext4_extent_idx));
286 287

	/*
288 289 290 291 292 293
	 * 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.
294
	 */
295 296 297 298 299 300 301 302 303 304 305 306 307 308
	if (ei->i_da_metadata_calc_len &&
	    ei->i_da_metadata_calc_last_lblock+1 == lblock) {
		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;
	}
309

310 311 312 313 314 315 316
	/*
	 * 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;
317 318
}

319 320 321 322 323 324 325
static int
ext4_ext_max_entries(struct inode *inode, int depth)
{
	int max;

	if (depth == ext_depth(inode)) {
		if (depth == 0)
326
			max = ext4_ext_space_root(inode, 1);
327
		else
328
			max = ext4_ext_space_root_idx(inode, 1);
329 330
	} else {
		if (depth == 0)
331
			max = ext4_ext_space_block(inode, 1);
332
		else
333
			max = ext4_ext_space_block_idx(inode, 1);
334 335 336 337 338
	}

	return max;
}

339 340
static int ext4_valid_extent(struct inode *inode, struct ext4_extent *ext)
{
341
	ext4_fsblk_t block = ext4_ext_pblock(ext);
342
	int len = ext4_ext_get_actual_len(ext);
343

344
	return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, len);
345 346 347 348 349
}

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

352
	return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, 1);
353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387
}

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

	entries = le16_to_cpu(eh->eh_entries);

	if (depth == 0) {
		/* leaf entries */
		ext = EXT_FIRST_EXTENT(eh);
		while (entries) {
			if (!ext4_valid_extent(inode, ext))
				return 0;
			ext++;
			entries--;
		}
	} else {
		ext_idx = EXT_FIRST_INDEX(eh);
		while (entries) {
			if (!ext4_valid_extent_idx(inode, ext_idx))
				return 0;
			ext_idx++;
			entries--;
		}
	}
	return 1;
}

388 389 390
static int __ext4_ext_check(const char *function, unsigned int line,
			    struct inode *inode, struct ext4_extent_header *eh,
			    int depth)
391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415
{
	const char *error_msg;
	int max = 0;

	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;
	}
416 417 418 419
	if (!ext4_valid_extent_entries(inode, eh, depth)) {
		error_msg = "invalid extent entries";
		goto corrupted;
	}
420 421 422
	return 0;

corrupted:
423
	ext4_error_inode(inode, function, line, 0,
424
			"bad header/extent: %s - magic %x, "
425
			"entries %u, max %u(%u), depth %u(%u)",
426
			error_msg, le16_to_cpu(eh->eh_magic),
427 428 429 430 431 432
			le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max),
			max, le16_to_cpu(eh->eh_depth), depth);

	return -EIO;
}

433
#define ext4_ext_check(inode, eh, depth)	\
434
	__ext4_ext_check(__func__, __LINE__, inode, eh, depth)
435

436 437 438 439 440
int ext4_ext_check_inode(struct inode *inode)
{
	return ext4_ext_check(inode, ext_inode_hdr(inode), ext_depth(inode));
}

A
Alex Tomas 已提交
441 442 443 444 445 446 447 448
#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) {
449
		  ext_debug("  %d->%llu", le32_to_cpu(path->p_idx->ei_block),
450
			    ext4_idx_pblock(path->p_idx));
A
Alex Tomas 已提交
451
		} else if (path->p_ext) {
452
			ext_debug("  %d:[%d]%d:%llu ",
A
Alex Tomas 已提交
453
				  le32_to_cpu(path->p_ext->ee_block),
454
				  ext4_ext_is_uninitialized(path->p_ext),
A
Amit Arora 已提交
455
				  ext4_ext_get_actual_len(path->p_ext),
456
				  ext4_ext_pblock(path->p_ext));
A
Alex Tomas 已提交
457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475
		} 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);

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

A
Alex Tomas 已提交
478
	for (i = 0; i < le16_to_cpu(eh->eh_entries); i++, ex++) {
479 480
		ext_debug("%d:[%d]%d:%llu ", le32_to_cpu(ex->ee_block),
			  ext4_ext_is_uninitialized(ex),
481
			  ext4_ext_get_actual_len(ex), ext4_ext_pblock(ex));
A
Alex Tomas 已提交
482 483 484 485
	}
	ext_debug("\n");
}
#else
486 487
#define ext4_ext_show_path(inode, path)
#define ext4_ext_show_leaf(inode, path)
A
Alex Tomas 已提交
488 489
#endif

490
void ext4_ext_drop_refs(struct ext4_ext_path *path)
A
Alex Tomas 已提交
491 492 493 494 495 496 497 498 499 500 501 502
{
	int depth = path->p_depth;
	int i;

	for (i = 0; i <= depth; i++, path++)
		if (path->p_bh) {
			brelse(path->p_bh);
			path->p_bh = NULL;
		}
}

/*
503 504
 * ext4_ext_binsearch_idx:
 * binary search for the closest index of the given block
505
 * the header must be checked before calling this
A
Alex Tomas 已提交
506 507
 */
static void
A
Aneesh Kumar K.V 已提交
508 509
ext4_ext_binsearch_idx(struct inode *inode,
			struct ext4_ext_path *path, ext4_lblk_t block)
A
Alex Tomas 已提交
510 511 512 513 514
{
	struct ext4_extent_header *eh = path->p_hdr;
	struct ext4_extent_idx *r, *l, *m;


515
	ext_debug("binsearch for %u(idx):  ", block);
A
Alex Tomas 已提交
516 517

	l = EXT_FIRST_INDEX(eh) + 1;
D
Dmitry Monakhov 已提交
518
	r = EXT_LAST_INDEX(eh);
A
Alex Tomas 已提交
519 520 521 522 523 524
	while (l <= r) {
		m = l + (r - l) / 2;
		if (block < le32_to_cpu(m->ei_block))
			r = m - 1;
		else
			l = m + 1;
525 526 527
		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 已提交
528 529 530
	}

	path->p_idx = l - 1;
531
	ext_debug("  -> %d->%lld ", le32_to_cpu(path->p_idx->ei_block),
532
		  ext4_idx_pblock(path->p_idx));
A
Alex Tomas 已提交
533 534 535 536 537 538 539 540 541 542

#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)) {
543 544 545 546
				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 已提交
547 548 549 550
				       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 已提交
551
					   <= le32_to_cpu(ix[-1].ei_block));
A
Alex Tomas 已提交
552 553 554 555 556 557 558 559 560 561 562
			if (block < le32_to_cpu(ix->ei_block))
				break;
			chix = ix;
		}
		BUG_ON(chix != path->p_idx);
	}
#endif

}

/*
563 564
 * ext4_ext_binsearch:
 * binary search for closest extent of the given block
565
 * the header must be checked before calling this
A
Alex Tomas 已提交
566 567
 */
static void
A
Aneesh Kumar K.V 已提交
568 569
ext4_ext_binsearch(struct inode *inode,
		struct ext4_ext_path *path, ext4_lblk_t block)
A
Alex Tomas 已提交
570 571 572 573 574 575
{
	struct ext4_extent_header *eh = path->p_hdr;
	struct ext4_extent *r, *l, *m;

	if (eh->eh_entries == 0) {
		/*
576 577
		 * this leaf is empty:
		 * we get such a leaf in split/add case
A
Alex Tomas 已提交
578 579 580 581
		 */
		return;
	}

582
	ext_debug("binsearch for %u:  ", block);
A
Alex Tomas 已提交
583 584

	l = EXT_FIRST_EXTENT(eh) + 1;
D
Dmitry Monakhov 已提交
585
	r = EXT_LAST_EXTENT(eh);
A
Alex Tomas 已提交
586 587 588 589 590 591 592

	while (l <= r) {
		m = l + (r - l) / 2;
		if (block < le32_to_cpu(m->ee_block))
			r = m - 1;
		else
			l = m + 1;
593 594 595
		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 已提交
596 597 598
	}

	path->p_ext = l - 1;
599
	ext_debug("  -> %d:%llu:[%d]%d ",
D
Dave Kleikamp 已提交
600
			le32_to_cpu(path->p_ext->ee_block),
601
			ext4_ext_pblock(path->p_ext),
602
			ext4_ext_is_uninitialized(path->p_ext),
A
Amit Arora 已提交
603
			ext4_ext_get_actual_len(path->p_ext));
A
Alex Tomas 已提交
604 605 606 607 608 609 610 611 612

#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 已提交
613
					  <= le32_to_cpu(ex[-1].ee_block));
A
Alex Tomas 已提交
614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631
			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;
632
	eh->eh_max = cpu_to_le16(ext4_ext_space_root(inode, 0));
A
Alex Tomas 已提交
633 634 635 636 637 638
	ext4_mark_inode_dirty(handle, inode);
	ext4_ext_invalidate_cache(inode);
	return 0;
}

struct ext4_ext_path *
A
Aneesh Kumar K.V 已提交
639 640
ext4_ext_find_extent(struct inode *inode, ext4_lblk_t block,
					struct ext4_ext_path *path)
A
Alex Tomas 已提交
641 642 643 644 645 646
{
	struct ext4_extent_header *eh;
	struct buffer_head *bh;
	short int depth, i, ppos = 0, alloc = 0;

	eh = ext_inode_hdr(inode);
647
	depth = ext_depth(inode);
A
Alex Tomas 已提交
648 649 650

	/* account possible depth increase */
	if (!path) {
A
Avantika Mathur 已提交
651
		path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 2),
A
Alex Tomas 已提交
652 653 654 655 656 657
				GFP_NOFS);
		if (!path)
			return ERR_PTR(-ENOMEM);
		alloc = 1;
	}
	path[0].p_hdr = eh;
658
	path[0].p_bh = NULL;
A
Alex Tomas 已提交
659

660
	i = depth;
A
Alex Tomas 已提交
661 662
	/* walk through the tree */
	while (i) {
663 664
		int need_to_validate = 0;

A
Alex Tomas 已提交
665 666
		ext_debug("depth %d: num %d, max %d\n",
			  ppos, le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
667

A
Alex Tomas 已提交
668
		ext4_ext_binsearch_idx(inode, path + ppos, block);
669
		path[ppos].p_block = ext4_idx_pblock(path[ppos].p_idx);
A
Alex Tomas 已提交
670 671 672
		path[ppos].p_depth = i;
		path[ppos].p_ext = NULL;

673 674
		bh = sb_getblk(inode->i_sb, path[ppos].p_block);
		if (unlikely(!bh))
A
Alex Tomas 已提交
675
			goto err;
676
		if (!bh_uptodate_or_lock(bh)) {
677 678
			trace_ext4_ext_load_extent(inode, block,
						path[ppos].p_block);
679 680 681 682 683 684 685
			if (bh_submit_read(bh) < 0) {
				put_bh(bh);
				goto err;
			}
			/* validate the extent entries */
			need_to_validate = 1;
		}
A
Alex Tomas 已提交
686 687
		eh = ext_block_hdr(bh);
		ppos++;
688 689 690 691 692 693
		if (unlikely(ppos > depth)) {
			put_bh(bh);
			EXT4_ERROR_INODE(inode,
					 "ppos %d > depth %d", ppos, depth);
			goto err;
		}
A
Alex Tomas 已提交
694 695 696 697
		path[ppos].p_bh = bh;
		path[ppos].p_hdr = eh;
		i--;

698
		if (need_to_validate && ext4_ext_check(inode, eh, i))
A
Alex Tomas 已提交
699 700 701 702 703 704 705 706 707
			goto err;
	}

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

	/* find extent */
	ext4_ext_binsearch(inode, path + ppos, block);
708 709
	/* if not an empty leaf */
	if (path[ppos].p_ext)
710
		path[ppos].p_block = ext4_ext_pblock(path[ppos].p_ext);
A
Alex Tomas 已提交
711 712 713 714 715 716 717 718 719 720 721 722 723

	ext4_ext_show_path(inode, path);

	return path;

err:
	ext4_ext_drop_refs(path);
	if (alloc)
		kfree(path);
	return ERR_PTR(-EIO);
}

/*
724 725 726
 * 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 已提交
727
 */
728 729 730
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 已提交
731 732 733 734
{
	struct ext4_extent_idx *ix;
	int len, err;

735 736
	err = ext4_ext_get_access(handle, inode, curp);
	if (err)
A
Alex Tomas 已提交
737 738
		return err;

739 740 741 742 743 744
	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));
		return -EIO;
	}
A
Alex Tomas 已提交
745 746 747 748 749 750
	len = EXT_MAX_INDEX(curp->p_hdr) - curp->p_idx;
	if (logical > le32_to_cpu(curp->p_idx->ei_block)) {
		/* insert after */
		if (curp->p_idx != EXT_LAST_INDEX(curp->p_hdr)) {
			len = (len - 1) * sizeof(struct ext4_extent_idx);
			len = len < 0 ? 0 : len;
751
			ext_debug("insert new index %d after: %llu. "
A
Alex Tomas 已提交
752 753 754 755 756 757 758 759 760 761
					"move %d from 0x%p to 0x%p\n",
					logical, ptr, len,
					(curp->p_idx + 1), (curp->p_idx + 2));
			memmove(curp->p_idx + 2, curp->p_idx + 1, len);
		}
		ix = curp->p_idx + 1;
	} else {
		/* insert before */
		len = len * sizeof(struct ext4_extent_idx);
		len = len < 0 ? 0 : len;
762
		ext_debug("insert new index %d before: %llu. "
A
Alex Tomas 已提交
763 764 765 766 767 768 769 770
				"move %d from 0x%p to 0x%p\n",
				logical, ptr, len,
				curp->p_idx, (curp->p_idx + 1));
		memmove(curp->p_idx + 1, curp->p_idx, len);
		ix = curp->p_idx;
	}

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

774 775 776 777 778 779 780 781 782 783 784
	if (unlikely(le16_to_cpu(curp->p_hdr->eh_entries)
			     > le16_to_cpu(curp->p_hdr->eh_max))) {
		EXT4_ERROR_INODE(inode,
				 "logical %d == ei_block %d!",
				 logical, le32_to_cpu(curp->p_idx->ei_block));
		return -EIO;
	}
	if (unlikely(ix > EXT_LAST_INDEX(curp->p_hdr))) {
		EXT4_ERROR_INODE(inode, "ix > EXT_LAST_INDEX!");
		return -EIO;
	}
A
Alex Tomas 已提交
785 786 787 788 789 790 791 792

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

	return err;
}

/*
793 794 795 796 797 798 799 800
 * 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 已提交
801 802
 */
static int ext4_ext_split(handle_t *handle, struct inode *inode,
803 804 805
			  unsigned int flags,
			  struct ext4_ext_path *path,
			  struct ext4_extent *newext, int at)
A
Alex Tomas 已提交
806 807 808 809 810 811 812
{
	struct buffer_head *bh = NULL;
	int depth = ext_depth(inode);
	struct ext4_extent_header *neh;
	struct ext4_extent_idx *fidx;
	struct ext4_extent *ex;
	int i = at, k, m, a;
813
	ext4_fsblk_t newblock, oldblock;
A
Alex Tomas 已提交
814
	__le32 border;
815
	ext4_fsblk_t *ablocks = NULL; /* array of allocated blocks */
A
Alex Tomas 已提交
816 817 818
	int err = 0;

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

821
	/* if current leaf will be split, then we should use
A
Alex Tomas 已提交
822
	 * border from split point */
823 824 825 826
	if (unlikely(path[depth].p_ext > EXT_MAX_EXTENT(path[depth].p_hdr))) {
		EXT4_ERROR_INODE(inode, "p_ext > EXT_MAX_EXTENT!");
		return -EIO;
	}
A
Alex Tomas 已提交
827 828
	if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr)) {
		border = path[depth].p_ext[1].ee_block;
829
		ext_debug("leaf will be split."
A
Alex Tomas 已提交
830
				" next leaf starts at %d\n",
D
Dave Kleikamp 已提交
831
				  le32_to_cpu(border));
A
Alex Tomas 已提交
832 833 834 835
	} else {
		border = newext->ee_block;
		ext_debug("leaf will be added."
				" next leaf starts at %d\n",
D
Dave Kleikamp 已提交
836
				le32_to_cpu(border));
A
Alex Tomas 已提交
837 838 839
	}

	/*
840 841
	 * If error occurs, then we break processing
	 * and mark filesystem read-only. index won't
A
Alex Tomas 已提交
842
	 * be inserted and tree will be in consistent
843
	 * state. Next mount will repair buffers too.
A
Alex Tomas 已提交
844 845 846
	 */

	/*
847 848 849
	 * Get array to track all allocated blocks.
	 * We need this to handle errors and free blocks
	 * upon them.
A
Alex Tomas 已提交
850
	 */
A
Avantika Mathur 已提交
851
	ablocks = kzalloc(sizeof(ext4_fsblk_t) * depth, GFP_NOFS);
A
Alex Tomas 已提交
852 853 854 855 856 857
	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 已提交
858
		newblock = ext4_ext_new_meta_block(handle, inode, path,
859
						   newext, &err, flags);
A
Alex Tomas 已提交
860 861 862 863 864 865 866
		if (newblock == 0)
			goto cleanup;
		ablocks[a] = newblock;
	}

	/* initialize new leaf */
	newblock = ablocks[--a];
867 868 869 870 871
	if (unlikely(newblock == 0)) {
		EXT4_ERROR_INODE(inode, "newblock == 0!");
		err = -EIO;
		goto cleanup;
	}
A
Alex Tomas 已提交
872 873 874 875 876 877 878
	bh = sb_getblk(inode->i_sb, newblock);
	if (!bh) {
		err = -EIO;
		goto cleanup;
	}
	lock_buffer(bh);

879 880
	err = ext4_journal_get_create_access(handle, bh);
	if (err)
A
Alex Tomas 已提交
881 882 883 884
		goto cleanup;

	neh = ext_block_hdr(bh);
	neh->eh_entries = 0;
885
	neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
A
Alex Tomas 已提交
886 887 888 889
	neh->eh_magic = EXT4_EXT_MAGIC;
	neh->eh_depth = 0;
	ex = EXT_FIRST_EXTENT(neh);

890
	/* move remainder of path[depth] to the new leaf */
891 892 893 894 895 896 897 898
	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);
		err = -EIO;
		goto cleanup;
	}
A
Alex Tomas 已提交
899 900 901 902 903 904
	/* start copy from next extent */
	/* TODO: we could do it by single memmove */
	m = 0;
	path[depth].p_ext++;
	while (path[depth].p_ext <=
			EXT_MAX_EXTENT(path[depth].p_hdr)) {
905
		ext_debug("move %d:%llu:[%d]%d in new leaf %llu\n",
D
Dave Kleikamp 已提交
906
				le32_to_cpu(path[depth].p_ext->ee_block),
907
				ext4_ext_pblock(path[depth].p_ext),
908
				ext4_ext_is_uninitialized(path[depth].p_ext),
A
Amit Arora 已提交
909
				ext4_ext_get_actual_len(path[depth].p_ext),
A
Alex Tomas 已提交
910 911 912 913 914 915 916 917 918
				newblock);
		/*memmove(ex++, path[depth].p_ext++,
				sizeof(struct ext4_extent));
		neh->eh_entries++;*/
		path[depth].p_ext++;
		m++;
	}
	if (m) {
		memmove(ex, path[depth].p_ext-m, sizeof(struct ext4_extent)*m);
M
Marcin Slusarz 已提交
919
		le16_add_cpu(&neh->eh_entries, m);
A
Alex Tomas 已提交
920 921 922 923 924
	}

	set_buffer_uptodate(bh);
	unlock_buffer(bh);

925
	err = ext4_handle_dirty_metadata(handle, inode, bh);
926
	if (err)
A
Alex Tomas 已提交
927 928 929 930 931 932
		goto cleanup;
	brelse(bh);
	bh = NULL;

	/* correct old leaf */
	if (m) {
933 934
		err = ext4_ext_get_access(handle, inode, path + depth);
		if (err)
A
Alex Tomas 已提交
935
			goto cleanup;
M
Marcin Slusarz 已提交
936
		le16_add_cpu(&path[depth].p_hdr->eh_entries, -m);
937 938
		err = ext4_ext_dirty(handle, inode, path + depth);
		if (err)
A
Alex Tomas 已提交
939 940 941 942 943 944
			goto cleanup;

	}

	/* create intermediate indexes */
	k = depth - at - 1;
945 946 947 948 949
	if (unlikely(k < 0)) {
		EXT4_ERROR_INODE(inode, "k %d < 0!", k);
		err = -EIO;
		goto cleanup;
	}
A
Alex Tomas 已提交
950 951 952 953 954 955 956 957
	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];
958
		bh = sb_getblk(inode->i_sb, newblock);
A
Alex Tomas 已提交
959 960 961 962 963 964
		if (!bh) {
			err = -EIO;
			goto cleanup;
		}
		lock_buffer(bh);

965 966
		err = ext4_journal_get_create_access(handle, bh);
		if (err)
A
Alex Tomas 已提交
967 968 969 970 971
			goto cleanup;

		neh = ext_block_hdr(bh);
		neh->eh_entries = cpu_to_le16(1);
		neh->eh_magic = EXT4_EXT_MAGIC;
972
		neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
A
Alex Tomas 已提交
973 974 975
		neh->eh_depth = cpu_to_le16(depth - i);
		fidx = EXT_FIRST_INDEX(neh);
		fidx->ei_block = border;
976
		ext4_idx_store_pblock(fidx, oldblock);
A
Alex Tomas 已提交
977

978 979
		ext_debug("int.index at %d (block %llu): %u -> %llu\n",
				i, newblock, le32_to_cpu(border), oldblock);
A
Alex Tomas 已提交
980 981 982 983 984 985
		/* copy indexes */
		m = 0;
		path[i].p_idx++;

		ext_debug("cur 0x%p, last 0x%p\n", path[i].p_idx,
				EXT_MAX_INDEX(path[i].p_hdr));
986 987 988 989 990 991 992 993
		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));
			err = -EIO;
			goto cleanup;
		}
A
Alex Tomas 已提交
994
		while (path[i].p_idx <= EXT_MAX_INDEX(path[i].p_hdr)) {
995
			ext_debug("%d: move %d:%llu in new index %llu\n", i,
D
Dave Kleikamp 已提交
996
					le32_to_cpu(path[i].p_idx->ei_block),
997
					ext4_idx_pblock(path[i].p_idx),
D
Dave Kleikamp 已提交
998
					newblock);
A
Alex Tomas 已提交
999 1000 1001 1002 1003 1004 1005 1006 1007 1008
			/*memmove(++fidx, path[i].p_idx++,
					sizeof(struct ext4_extent_idx));
			neh->eh_entries++;
			BUG_ON(neh->eh_entries > neh->eh_max);*/
			path[i].p_idx++;
			m++;
		}
		if (m) {
			memmove(++fidx, path[i].p_idx - m,
				sizeof(struct ext4_extent_idx) * m);
M
Marcin Slusarz 已提交
1009
			le16_add_cpu(&neh->eh_entries, m);
A
Alex Tomas 已提交
1010 1011 1012 1013
		}
		set_buffer_uptodate(bh);
		unlock_buffer(bh);

1014
		err = ext4_handle_dirty_metadata(handle, inode, bh);
1015
		if (err)
A
Alex Tomas 已提交
1016 1017 1018 1019 1020 1021 1022 1023 1024
			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 已提交
1025
			le16_add_cpu(&path[i].p_hdr->eh_entries, -m);
A
Alex Tomas 已提交
1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049
			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;
1050
			ext4_free_blocks(handle, inode, NULL, ablocks[i], 1,
1051
					 EXT4_FREE_BLOCKS_METADATA);
A
Alex Tomas 已提交
1052 1053 1054 1055 1056 1057 1058 1059
		}
	}
	kfree(ablocks);

	return err;
}

/*
1060 1061 1062 1063 1064 1065
 * 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 已提交
1066 1067
 */
static int ext4_ext_grow_indepth(handle_t *handle, struct inode *inode,
1068 1069 1070
				 unsigned int flags,
				 struct ext4_ext_path *path,
				 struct ext4_extent *newext)
A
Alex Tomas 已提交
1071 1072 1073 1074
{
	struct ext4_ext_path *curp = path;
	struct ext4_extent_header *neh;
	struct buffer_head *bh;
1075
	ext4_fsblk_t newblock;
A
Alex Tomas 已提交
1076 1077
	int err = 0;

1078 1079
	newblock = ext4_ext_new_meta_block(handle, inode, path,
		newext, &err, flags);
A
Alex Tomas 已提交
1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090
	if (newblock == 0)
		return err;

	bh = sb_getblk(inode->i_sb, newblock);
	if (!bh) {
		err = -EIO;
		ext4_std_error(inode->i_sb, err);
		return err;
	}
	lock_buffer(bh);

1091 1092
	err = ext4_journal_get_create_access(handle, bh);
	if (err) {
A
Alex Tomas 已提交
1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104
		unlock_buffer(bh);
		goto out;
	}

	/* move top-level index/leaf into new block */
	memmove(bh->b_data, curp->p_hdr, sizeof(EXT4_I(inode)->i_data));

	/* 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))
1105
		neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
A
Alex Tomas 已提交
1106
	else
1107
		neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
A
Alex Tomas 已提交
1108 1109 1110 1111
	neh->eh_magic = EXT4_EXT_MAGIC;
	set_buffer_uptodate(bh);
	unlock_buffer(bh);

1112
	err = ext4_handle_dirty_metadata(handle, inode, bh);
1113
	if (err)
A
Alex Tomas 已提交
1114 1115 1116
		goto out;

	/* create index in new top-level index: num,max,pointer */
1117 1118
	err = ext4_ext_get_access(handle, inode, curp);
	if (err)
A
Alex Tomas 已提交
1119 1120 1121
		goto out;

	curp->p_hdr->eh_magic = EXT4_EXT_MAGIC;
1122
	curp->p_hdr->eh_max = cpu_to_le16(ext4_ext_space_root_idx(inode, 0));
A
Alex Tomas 已提交
1123 1124
	curp->p_hdr->eh_entries = cpu_to_le16(1);
	curp->p_idx = EXT_FIRST_INDEX(curp->p_hdr);
D
Dmitry Monakhov 已提交
1125 1126 1127 1128 1129 1130 1131

	if (path[0].p_hdr->eh_depth)
		curp->p_idx->ei_block =
			EXT_FIRST_INDEX(path[0].p_hdr)->ei_block;
	else
		curp->p_idx->ei_block =
			EXT_FIRST_EXTENT(path[0].p_hdr)->ee_block;
1132
	ext4_idx_store_pblock(curp->p_idx, newblock);
A
Alex Tomas 已提交
1133 1134

	neh = ext_inode_hdr(inode);
1135
	ext_debug("new root: num %d(%d), lblock %d, ptr %llu\n",
A
Alex Tomas 已提交
1136
		  le16_to_cpu(neh->eh_entries), le16_to_cpu(neh->eh_max),
1137
		  le32_to_cpu(EXT_FIRST_INDEX(neh)->ei_block),
1138
		  ext4_idx_pblock(EXT_FIRST_INDEX(neh)));
A
Alex Tomas 已提交
1139 1140 1141 1142 1143 1144 1145 1146 1147 1148

	neh->eh_depth = cpu_to_le16(path->p_depth + 1);
	err = ext4_ext_dirty(handle, inode, curp);
out:
	brelse(bh);

	return err;
}

/*
1149 1150 1151
 * 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 已提交
1152 1153
 */
static int ext4_ext_create_new_leaf(handle_t *handle, struct inode *inode,
1154 1155 1156
				    unsigned int flags,
				    struct ext4_ext_path *path,
				    struct ext4_extent *newext)
A
Alex Tomas 已提交
1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170
{
	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--;
	}

1171 1172
	/* we use already allocated block for index block,
	 * so subsequent data blocks should be contiguous */
A
Alex Tomas 已提交
1173 1174 1175
	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 */
1176
		err = ext4_ext_split(handle, inode, flags, path, newext, i);
1177 1178
		if (err)
			goto out;
A
Alex Tomas 已提交
1179 1180 1181 1182

		/* refill path */
		ext4_ext_drop_refs(path);
		path = ext4_ext_find_extent(inode,
A
Aneesh Kumar K.V 已提交
1183 1184
				    (ext4_lblk_t)le32_to_cpu(newext->ee_block),
				    path);
A
Alex Tomas 已提交
1185 1186 1187 1188
		if (IS_ERR(path))
			err = PTR_ERR(path);
	} else {
		/* tree is full, time to grow in depth */
1189 1190
		err = ext4_ext_grow_indepth(handle, inode, flags,
					    path, newext);
A
Alex Tomas 已提交
1191 1192 1193 1194 1195 1196
		if (err)
			goto out;

		/* refill path */
		ext4_ext_drop_refs(path);
		path = ext4_ext_find_extent(inode,
A
Aneesh Kumar K.V 已提交
1197 1198
				   (ext4_lblk_t)le32_to_cpu(newext->ee_block),
				    path);
A
Alex Tomas 已提交
1199 1200 1201 1202 1203 1204
		if (IS_ERR(path)) {
			err = PTR_ERR(path);
			goto out;
		}

		/*
1205 1206
		 * only first (depth 0 -> 1) produces free space;
		 * in all other cases we have to split the grown tree
A
Alex Tomas 已提交
1207 1208 1209
		 */
		depth = ext_depth(inode);
		if (path[depth].p_hdr->eh_entries == path[depth].p_hdr->eh_max) {
1210
			/* now we need to split */
A
Alex Tomas 已提交
1211 1212 1213 1214 1215 1216 1217 1218
			goto repeat;
		}
	}

out:
	return err;
}

1219 1220 1221 1222 1223 1224 1225
/*
 * 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
 */
1226 1227 1228
static int ext4_ext_search_left(struct inode *inode,
				struct ext4_ext_path *path,
				ext4_lblk_t *logical, ext4_fsblk_t *phys)
1229 1230 1231
{
	struct ext4_extent_idx *ix;
	struct ext4_extent *ex;
1232
	int depth, ee_len;
1233

1234 1235 1236 1237
	if (unlikely(path == NULL)) {
		EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
		return -EIO;
	}
1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248
	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;
1249
	ee_len = ext4_ext_get_actual_len(ex);
1250
	if (*logical < le32_to_cpu(ex->ee_block)) {
1251 1252 1253 1254 1255 1256
		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));
			return -EIO;
		}
1257 1258
		while (--depth >= 0) {
			ix = path[depth].p_idx;
1259 1260 1261 1262 1263 1264 1265 1266 1267
			if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
				EXT4_ERROR_INODE(inode,
				  "ix (%d) != EXT_FIRST_INDEX (%d) (depth %d)!",
				  ix != NULL ? ix->ei_block : 0,
				  EXT_FIRST_INDEX(path[depth].p_hdr) != NULL ?
				    EXT_FIRST_INDEX(path[depth].p_hdr)->ei_block : 0,
				  depth);
				return -EIO;
			}
1268 1269 1270 1271
		}
		return 0;
	}

1272 1273 1274 1275 1276 1277
	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);
		return -EIO;
	}
1278

1279
	*logical = le32_to_cpu(ex->ee_block) + ee_len - 1;
1280
	*phys = ext4_ext_pblock(ex) + ee_len - 1;
1281 1282 1283 1284 1285 1286 1287 1288 1289 1290
	return 0;
}

/*
 * search the closest allocated block to the right 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
 */
1291 1292 1293
static int ext4_ext_search_right(struct inode *inode,
				 struct ext4_ext_path *path,
				 ext4_lblk_t *logical, ext4_fsblk_t *phys)
1294 1295 1296 1297 1298 1299
{
	struct buffer_head *bh = NULL;
	struct ext4_extent_header *eh;
	struct ext4_extent_idx *ix;
	struct ext4_extent *ex;
	ext4_fsblk_t block;
1300 1301
	int depth;	/* Note, NOT eh_depth; depth from top of tree */
	int ee_len;
1302

1303 1304 1305 1306
	if (unlikely(path == NULL)) {
		EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
		return -EIO;
	}
1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317
	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;
1318
	ee_len = ext4_ext_get_actual_len(ex);
1319
	if (*logical < le32_to_cpu(ex->ee_block)) {
1320 1321 1322 1323 1324 1325
		if (unlikely(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex)) {
			EXT4_ERROR_INODE(inode,
					 "first_extent(path[%d].p_hdr) != ex",
					 depth);
			return -EIO;
		}
1326 1327
		while (--depth >= 0) {
			ix = path[depth].p_idx;
1328 1329 1330 1331 1332 1333
			if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
				EXT4_ERROR_INODE(inode,
						 "ix != EXT_FIRST_INDEX *logical %d!",
						 *logical);
				return -EIO;
			}
1334 1335
		}
		*logical = le32_to_cpu(ex->ee_block);
1336
		*phys = ext4_ext_pblock(ex);
1337 1338 1339
		return 0;
	}

1340 1341 1342 1343 1344 1345
	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);
		return -EIO;
	}
1346 1347 1348 1349 1350

	if (ex != EXT_LAST_EXTENT(path[depth].p_hdr)) {
		/* next allocated block in this leaf */
		ex++;
		*logical = le32_to_cpu(ex->ee_block);
1351
		*phys = ext4_ext_pblock(ex);
1352 1353 1354 1355 1356 1357 1358
		return 0;
	}

	/* 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 已提交
1359
			goto got_index;
1360 1361
	}

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

W
Wu Fengguang 已提交
1365
got_index:
1366 1367 1368 1369
	/* we've found index to the right, let's
	 * follow it and find the closest allocated
	 * block to the right */
	ix++;
1370
	block = ext4_idx_pblock(ix);
1371 1372 1373 1374 1375
	while (++depth < path->p_depth) {
		bh = sb_bread(inode->i_sb, block);
		if (bh == NULL)
			return -EIO;
		eh = ext_block_hdr(bh);
1376
		/* subtract from p_depth to get proper eh_depth */
1377
		if (ext4_ext_check(inode, eh, path->p_depth - depth)) {
1378 1379 1380 1381
			put_bh(bh);
			return -EIO;
		}
		ix = EXT_FIRST_INDEX(eh);
1382
		block = ext4_idx_pblock(ix);
1383 1384 1385 1386 1387 1388 1389
		put_bh(bh);
	}

	bh = sb_bread(inode->i_sb, block);
	if (bh == NULL)
		return -EIO;
	eh = ext_block_hdr(bh);
1390
	if (ext4_ext_check(inode, eh, path->p_depth - depth)) {
1391 1392 1393 1394 1395
		put_bh(bh);
		return -EIO;
	}
	ex = EXT_FIRST_EXTENT(eh);
	*logical = le32_to_cpu(ex->ee_block);
1396
	*phys = ext4_ext_pblock(ex);
1397 1398 1399 1400
	put_bh(bh);
	return 0;
}

A
Alex Tomas 已提交
1401
/*
1402 1403 1404 1405 1406
 * ext4_ext_next_allocated_block:
 * returns allocated block in subsequent extent or EXT_MAX_BLOCK.
 * NOTE: it considers block number from index entry as
 * allocated block. Thus, index entries have to be consistent
 * with leaves.
A
Alex Tomas 已提交
1407
 */
A
Aneesh Kumar K.V 已提交
1408
static ext4_lblk_t
A
Alex Tomas 已提交
1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437
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)
		return EXT_MAX_BLOCK;

	while (depth >= 0) {
		if (depth == path->p_depth) {
			/* leaf */
			if (path[depth].p_ext !=
					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--;
	}

	return EXT_MAX_BLOCK;
}

/*
1438
 * ext4_ext_next_leaf_block:
A
Alex Tomas 已提交
1439 1440
 * returns first allocated block from next leaf or EXT_MAX_BLOCK
 */
A
Aneesh Kumar K.V 已提交
1441
static ext4_lblk_t ext4_ext_next_leaf_block(struct inode *inode,
A
Andrew Morton 已提交
1442
					struct ext4_ext_path *path)
A
Alex Tomas 已提交
1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458
{
	int depth;

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

	/* zero-tree has no leaf blocks at all */
	if (depth == 0)
		return EXT_MAX_BLOCK;

	/* 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 已提交
1459 1460
			return (ext4_lblk_t)
				le32_to_cpu(path[depth].p_idx[1].ei_block);
A
Alex Tomas 已提交
1461 1462 1463 1464 1465 1466 1467
		depth--;
	}

	return EXT_MAX_BLOCK;
}

/*
1468 1469 1470
 * 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 已提交
1471 1472
 * TODO: do we need to correct tree in all cases?
 */
A
Aneesh Kumar K.V 已提交
1473
static int ext4_ext_correct_indexes(handle_t *handle, struct inode *inode,
A
Alex Tomas 已提交
1474 1475 1476 1477 1478 1479 1480 1481 1482 1483
				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;
1484 1485 1486 1487 1488 1489

	if (unlikely(ex == NULL || eh == NULL)) {
		EXT4_ERROR_INODE(inode,
				 "ex %p == NULL or eh %p == NULL", ex, eh);
		return -EIO;
	}
A
Alex Tomas 已提交
1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501

	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;
	}

	/*
1502
	 * TODO: we need correction if border is smaller than current one
A
Alex Tomas 已提交
1503 1504 1505
	 */
	k = depth - 1;
	border = path[depth].p_ext->ee_block;
1506 1507
	err = ext4_ext_get_access(handle, inode, path + k);
	if (err)
A
Alex Tomas 已提交
1508 1509
		return err;
	path[k].p_idx->ei_block = border;
1510 1511
	err = ext4_ext_dirty(handle, inode, path + k);
	if (err)
A
Alex Tomas 已提交
1512 1513 1514 1515 1516 1517
		return err;

	while (k--) {
		/* change all left-side indexes */
		if (path[k+1].p_idx != EXT_FIRST_INDEX(path[k+1].p_hdr))
			break;
1518 1519
		err = ext4_ext_get_access(handle, inode, path + k);
		if (err)
A
Alex Tomas 已提交
1520 1521
			break;
		path[k].p_idx->ei_block = border;
1522 1523
		err = ext4_ext_dirty(handle, inode, path + k);
		if (err)
A
Alex Tomas 已提交
1524 1525 1526 1527 1528 1529
			break;
	}

	return err;
}

1530
int
A
Alex Tomas 已提交
1531 1532 1533
ext4_can_extents_be_merged(struct inode *inode, struct ext4_extent *ex1,
				struct ext4_extent *ex2)
{
1534
	unsigned short ext1_ee_len, ext2_ee_len, max_len;
A
Amit Arora 已提交
1535 1536 1537 1538 1539 1540 1541 1542

	/*
	 * Make sure that either both extents are uninitialized, or
	 * both are _not_.
	 */
	if (ext4_ext_is_uninitialized(ex1) ^ ext4_ext_is_uninitialized(ex2))
		return 0;

1543 1544 1545 1546 1547
	if (ext4_ext_is_uninitialized(ex1))
		max_len = EXT_UNINIT_MAX_LEN;
	else
		max_len = EXT_INIT_MAX_LEN;

A
Amit Arora 已提交
1548 1549 1550 1551
	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 已提交
1552
			le32_to_cpu(ex2->ee_block))
A
Alex Tomas 已提交
1553 1554
		return 0;

1555 1556 1557
	/*
	 * To allow future support for preallocated extents to be added
	 * as an RO_COMPAT feature, refuse to merge to extents if
1558
	 * this can result in the top bit of ee_len being set.
1559
	 */
1560
	if (ext1_ee_len + ext2_ee_len > max_len)
1561
		return 0;
1562
#ifdef AGGRESSIVE_TEST
1563
	if (ext1_ee_len >= 4)
A
Alex Tomas 已提交
1564 1565 1566
		return 0;
#endif

1567
	if (ext4_ext_pblock(ex1) + ext1_ee_len == ext4_ext_pblock(ex2))
A
Alex Tomas 已提交
1568 1569 1570 1571
		return 1;
	return 0;
}

1572 1573 1574 1575 1576 1577 1578
/*
 * 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.
 */
1579
static int ext4_ext_try_to_merge_right(struct inode *inode,
1580 1581
				 struct ext4_ext_path *path,
				 struct ext4_extent *ex)
1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607
{
	struct ext4_extent_header *eh;
	unsigned int depth, len;
	int merge_done = 0;
	int uninitialized = 0;

	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! */
		if (ext4_ext_is_uninitialized(ex))
			uninitialized = 1;
		ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
				+ ext4_ext_get_actual_len(ex + 1));
		if (uninitialized)
			ext4_ext_mark_uninitialized(ex);

		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 已提交
1608
		le16_add_cpu(&eh->eh_entries, -1);
1609 1610 1611
		merge_done = 1;
		WARN_ON(eh->eh_entries == 0);
		if (!eh->eh_entries)
1612
			EXT4_ERROR_INODE(inode, "eh->eh_entries = 0!");
1613 1614 1615 1616 1617
	}

	return merge_done;
}

1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642
/*
 * This function tries to merge the @ex extent to neighbours in the tree.
 * return 1 if merge left else 0.
 */
static int ext4_ext_try_to_merge(struct inode *inode,
				  struct ext4_ext_path *path,
				  struct ext4_extent *ex) {
	struct ext4_extent_header *eh;
	unsigned int depth;
	int merge_done = 0;
	int ret = 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)
		ret = ext4_ext_try_to_merge_right(inode, path, ex);

	return ret;
}

A
Amit Arora 已提交
1643 1644 1645 1646 1647 1648 1649 1650
/*
 * 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.
 */
1651 1652 1653
static unsigned int ext4_ext_check_overlap(struct inode *inode,
					   struct ext4_extent *newext,
					   struct ext4_ext_path *path)
A
Amit Arora 已提交
1654
{
A
Aneesh Kumar K.V 已提交
1655
	ext4_lblk_t b1, b2;
A
Amit Arora 已提交
1656 1657 1658 1659
	unsigned int depth, len1;
	unsigned int ret = 0;

	b1 = le32_to_cpu(newext->ee_block);
A
Amit Arora 已提交
1660
	len1 = ext4_ext_get_actual_len(newext);
A
Amit Arora 已提交
1661 1662 1663 1664 1665 1666 1667
	depth = ext_depth(inode);
	if (!path[depth].p_ext)
		goto out;
	b2 = le32_to_cpu(path[depth].p_ext->ee_block);

	/*
	 * get the next allocated block if the extent in the path
1668
	 * is before the requested block(s)
A
Amit Arora 已提交
1669 1670 1671 1672 1673 1674 1675
	 */
	if (b2 < b1) {
		b2 = ext4_ext_next_allocated_block(path);
		if (b2 == EXT_MAX_BLOCK)
			goto out;
	}

A
Aneesh Kumar K.V 已提交
1676
	/* check for wrap through zero on extent logical start block*/
A
Amit Arora 已提交
1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691
	if (b1 + len1 < b1) {
		len1 = EXT_MAX_BLOCK - b1;
		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 已提交
1692
/*
1693 1694 1695 1696
 * 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 已提交
1697 1698 1699
 */
int ext4_ext_insert_extent(handle_t *handle, struct inode *inode,
				struct ext4_ext_path *path,
1700
				struct ext4_extent *newext, int flag)
A
Alex Tomas 已提交
1701
{
1702
	struct ext4_extent_header *eh;
A
Alex Tomas 已提交
1703 1704 1705
	struct ext4_extent *ex, *fex;
	struct ext4_extent *nearex; /* nearest extent */
	struct ext4_ext_path *npath = NULL;
A
Aneesh Kumar K.V 已提交
1706 1707
	int depth, len, err;
	ext4_lblk_t next;
A
Amit Arora 已提交
1708
	unsigned uninitialized = 0;
1709
	int flags = 0;
A
Alex Tomas 已提交
1710

1711 1712 1713 1714
	if (unlikely(ext4_ext_get_actual_len(newext) == 0)) {
		EXT4_ERROR_INODE(inode, "ext4_ext_get_actual_len(newext) == 0");
		return -EIO;
	}
A
Alex Tomas 已提交
1715 1716
	depth = ext_depth(inode);
	ex = path[depth].p_ext;
1717 1718 1719 1720
	if (unlikely(path[depth].p_hdr == NULL)) {
		EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
		return -EIO;
	}
A
Alex Tomas 已提交
1721 1722

	/* try to insert block into found extent and return */
1723
	if (ex && !(flag & EXT4_GET_BLOCKS_PRE_IO)
1724
		&& ext4_can_extents_be_merged(inode, ex, newext)) {
1725
		ext_debug("append [%d]%d block to %d:[%d]%d (from %llu)\n",
1726 1727 1728 1729 1730 1731
			  ext4_ext_is_uninitialized(newext),
			  ext4_ext_get_actual_len(newext),
			  le32_to_cpu(ex->ee_block),
			  ext4_ext_is_uninitialized(ex),
			  ext4_ext_get_actual_len(ex),
			  ext4_ext_pblock(ex));
1732 1733
		err = ext4_ext_get_access(handle, inode, path + depth);
		if (err)
A
Alex Tomas 已提交
1734
			return err;
A
Amit Arora 已提交
1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746

		/*
		 * ext4_can_extents_be_merged should have checked that either
		 * both extents are uninitialized, or both aren't. Thus we
		 * need to check only one of them here.
		 */
		if (ext4_ext_is_uninitialized(ex))
			uninitialized = 1;
		ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
					+ ext4_ext_get_actual_len(newext));
		if (uninitialized)
			ext4_ext_mark_uninitialized(ex);
A
Alex Tomas 已提交
1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770
		eh = path[depth].p_hdr;
		nearex = ex;
		goto merge;
	}

repeat:
	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);
	next = ext4_ext_next_leaf_block(inode, path);
	if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block)
	    && next != EXT_MAX_BLOCK) {
		ext_debug("next leaf block - %d\n", next);
		BUG_ON(npath != NULL);
		npath = ext4_ext_find_extent(inode, next, NULL);
		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 已提交
1771
			ext_debug("next leaf isn't full(%d)\n",
A
Alex Tomas 已提交
1772 1773 1774 1775 1776 1777 1778 1779 1780
				  le16_to_cpu(eh->eh_entries));
			path = npath;
			goto repeat;
		}
		ext_debug("next leaf has no free space(%d,%d)\n",
			  le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
	}

	/*
1781 1782
	 * There is no free space in the found leaf.
	 * We're gonna add a new leaf in the tree.
A
Alex Tomas 已提交
1783
	 */
1784 1785 1786
	if (flag & EXT4_GET_BLOCKS_PUNCH_OUT_EXT)
		flags = EXT4_MB_USE_ROOT_BLOCKS;
	err = ext4_ext_create_new_leaf(handle, inode, flags, path, newext);
A
Alex Tomas 已提交
1787 1788 1789 1790 1791 1792 1793 1794
	if (err)
		goto cleanup;
	depth = ext_depth(inode);
	eh = path[depth].p_hdr;

has_space:
	nearex = path[depth].p_ext;

1795 1796
	err = ext4_ext_get_access(handle, inode, path + depth);
	if (err)
A
Alex Tomas 已提交
1797 1798 1799 1800
		goto cleanup;

	if (!nearex) {
		/* there is no extent in this leaf, create first one */
1801
		ext_debug("first extent in the leaf: %d:%llu:[%d]%d\n",
D
Dave Kleikamp 已提交
1802
				le32_to_cpu(newext->ee_block),
1803
				ext4_ext_pblock(newext),
1804
				ext4_ext_is_uninitialized(newext),
A
Amit Arora 已提交
1805
				ext4_ext_get_actual_len(newext));
A
Alex Tomas 已提交
1806 1807
		path[depth].p_ext = EXT_FIRST_EXTENT(eh);
	} else if (le32_to_cpu(newext->ee_block)
D
Dave Kleikamp 已提交
1808
			   > le32_to_cpu(nearex->ee_block)) {
A
Alex Tomas 已提交
1809 1810 1811 1812 1813
/*		BUG_ON(newext->ee_block == nearex->ee_block); */
		if (nearex != EXT_LAST_EXTENT(eh)) {
			len = EXT_MAX_EXTENT(eh) - nearex;
			len = (len - 1) * sizeof(struct ext4_extent);
			len = len < 0 ? 0 : len;
1814
			ext_debug("insert %d:%llu:[%d]%d after: nearest 0x%p, "
A
Alex Tomas 已提交
1815
					"move %d from 0x%p to 0x%p\n",
D
Dave Kleikamp 已提交
1816
					le32_to_cpu(newext->ee_block),
1817
					ext4_ext_pblock(newext),
1818
					ext4_ext_is_uninitialized(newext),
A
Amit Arora 已提交
1819
					ext4_ext_get_actual_len(newext),
A
Alex Tomas 已提交
1820 1821 1822 1823 1824 1825 1826 1827
					nearex, len, nearex + 1, nearex + 2);
			memmove(nearex + 2, nearex + 1, len);
		}
		path[depth].p_ext = nearex + 1;
	} else {
		BUG_ON(newext->ee_block == nearex->ee_block);
		len = (EXT_MAX_EXTENT(eh) - nearex) * sizeof(struct ext4_extent);
		len = len < 0 ? 0 : len;
1828
		ext_debug("insert %d:%llu:[%d]%d before: nearest 0x%p, "
A
Alex Tomas 已提交
1829 1830
				"move %d from 0x%p to 0x%p\n",
				le32_to_cpu(newext->ee_block),
1831
				ext4_ext_pblock(newext),
1832
				ext4_ext_is_uninitialized(newext),
A
Amit Arora 已提交
1833
				ext4_ext_get_actual_len(newext),
A
Alex Tomas 已提交
1834 1835 1836 1837 1838
				nearex, len, nearex + 1, nearex + 2);
		memmove(nearex + 1, nearex, len);
		path[depth].p_ext = nearex;
	}

M
Marcin Slusarz 已提交
1839
	le16_add_cpu(&eh->eh_entries, 1);
A
Alex Tomas 已提交
1840 1841
	nearex = path[depth].p_ext;
	nearex->ee_block = newext->ee_block;
1842
	ext4_ext_store_pblock(nearex, ext4_ext_pblock(newext));
A
Alex Tomas 已提交
1843 1844 1845 1846
	nearex->ee_len = newext->ee_len;

merge:
	/* try to merge extents to the right */
1847
	if (!(flag & EXT4_GET_BLOCKS_PRE_IO))
1848
		ext4_ext_try_to_merge(inode, path, nearex);
A
Alex Tomas 已提交
1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867

	/* try to merge extents to the left */

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

	err = ext4_ext_dirty(handle, inode, path + depth);

cleanup:
	if (npath) {
		ext4_ext_drop_refs(npath);
		kfree(npath);
	}
	ext4_ext_invalidate_cache(inode);
	return err;
}

1868 1869 1870
static int ext4_ext_walk_space(struct inode *inode, ext4_lblk_t block,
			       ext4_lblk_t num, ext_prepare_callback func,
			       void *cbdata)
1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884
{
	struct ext4_ext_path *path = NULL;
	struct ext4_ext_cache cbex;
	struct ext4_extent *ex;
	ext4_lblk_t next, start = 0, end = 0;
	ext4_lblk_t last = block + num;
	int depth, exists, err = 0;

	BUG_ON(func == NULL);
	BUG_ON(inode == NULL);

	while (block < last && block != EXT_MAX_BLOCK) {
		num = last - block;
		/* find extent for this block */
1885
		down_read(&EXT4_I(inode)->i_data_sem);
1886
		path = ext4_ext_find_extent(inode, block, path);
1887
		up_read(&EXT4_I(inode)->i_data_sem);
1888 1889 1890 1891 1892 1893 1894
		if (IS_ERR(path)) {
			err = PTR_ERR(path);
			path = NULL;
			break;
		}

		depth = ext_depth(inode);
1895 1896 1897 1898 1899
		if (unlikely(path[depth].p_hdr == NULL)) {
			EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
			err = -EIO;
			break;
		}
1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944
		ex = path[depth].p_ext;
		next = ext4_ext_next_allocated_block(path);

		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) {
			cbex.ec_block = start;
			cbex.ec_len = end - start;
			cbex.ec_start = 0;
		} else {
			cbex.ec_block = le32_to_cpu(ex->ee_block);
			cbex.ec_len = ext4_ext_get_actual_len(ex);
1945
			cbex.ec_start = ext4_ext_pblock(ex);
1946 1947
		}

1948 1949 1950 1951 1952
		if (unlikely(cbex.ec_len == 0)) {
			EXT4_ERROR_INODE(inode, "cbex.ec_len == 0");
			err = -EIO;
			break;
		}
1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982
		err = func(inode, path, &cbex, ex, cbdata);
		ext4_ext_drop_refs(path);

		if (err < 0)
			break;

		if (err == EXT_REPEAT)
			continue;
		else if (err == EXT_BREAK) {
			err = 0;
			break;
		}

		if (ext_depth(inode) != depth) {
			/* depth was changed. we have to realloc path */
			kfree(path);
			path = NULL;
		}

		block = cbex.ec_block + cbex.ec_len;
	}

	if (path) {
		ext4_ext_drop_refs(path);
		kfree(path);
	}

	return err;
}

1983
static void
A
Aneesh Kumar K.V 已提交
1984
ext4_ext_put_in_cache(struct inode *inode, ext4_lblk_t block,
1985
			__u32 len, ext4_fsblk_t start)
A
Alex Tomas 已提交
1986 1987 1988
{
	struct ext4_ext_cache *cex;
	BUG_ON(len == 0);
1989
	spin_lock(&EXT4_I(inode)->i_block_reservation_lock);
A
Alex Tomas 已提交
1990 1991 1992 1993
	cex = &EXT4_I(inode)->i_cached_extent;
	cex->ec_block = block;
	cex->ec_len = len;
	cex->ec_start = start;
1994
	spin_unlock(&EXT4_I(inode)->i_block_reservation_lock);
A
Alex Tomas 已提交
1995 1996 1997
}

/*
1998 1999
 * ext4_ext_put_gap_in_cache:
 * calculate boundaries of the gap that the requested block fits into
A
Alex Tomas 已提交
2000 2001
 * and cache this gap
 */
2002
static void
A
Alex Tomas 已提交
2003
ext4_ext_put_gap_in_cache(struct inode *inode, struct ext4_ext_path *path,
A
Aneesh Kumar K.V 已提交
2004
				ext4_lblk_t block)
A
Alex Tomas 已提交
2005 2006
{
	int depth = ext_depth(inode);
A
Aneesh Kumar K.V 已提交
2007 2008
	unsigned long len;
	ext4_lblk_t lblock;
A
Alex Tomas 已提交
2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019
	struct ext4_extent *ex;

	ex = path[depth].p_ext;
	if (ex == NULL) {
		/* there is no extent yet, so gap is [0;-] */
		lblock = 0;
		len = EXT_MAX_BLOCK;
		ext_debug("cache gap(whole file):");
	} else if (block < le32_to_cpu(ex->ee_block)) {
		lblock = block;
		len = le32_to_cpu(ex->ee_block) - block;
2020 2021 2022 2023
		ext_debug("cache gap(before): %u [%u:%u]",
				block,
				le32_to_cpu(ex->ee_block),
				 ext4_ext_get_actual_len(ex));
A
Alex Tomas 已提交
2024
	} else if (block >= le32_to_cpu(ex->ee_block)
A
Amit Arora 已提交
2025
			+ ext4_ext_get_actual_len(ex)) {
A
Aneesh Kumar K.V 已提交
2026
		ext4_lblk_t next;
D
Dave Kleikamp 已提交
2027
		lblock = le32_to_cpu(ex->ee_block)
A
Amit Arora 已提交
2028
			+ ext4_ext_get_actual_len(ex);
A
Aneesh Kumar K.V 已提交
2029 2030

		next = ext4_ext_next_allocated_block(path);
2031 2032 2033 2034
		ext_debug("cache gap(after): [%u:%u] %u",
				le32_to_cpu(ex->ee_block),
				ext4_ext_get_actual_len(ex),
				block);
A
Aneesh Kumar K.V 已提交
2035 2036
		BUG_ON(next == lblock);
		len = next - lblock;
A
Alex Tomas 已提交
2037 2038 2039 2040 2041
	} else {
		lblock = len = 0;
		BUG();
	}

2042
	ext_debug(" -> %u:%lu\n", lblock, len);
2043
	ext4_ext_put_in_cache(inode, lblock, len, 0);
A
Alex Tomas 已提交
2044 2045
}

2046 2047 2048
/*
 * Return 0 if cache is invalid; 1 if the cache is valid
 */
2049
static int
A
Aneesh Kumar K.V 已提交
2050
ext4_ext_in_cache(struct inode *inode, ext4_lblk_t block,
A
Alex Tomas 已提交
2051 2052 2053
			struct ext4_extent *ex)
{
	struct ext4_ext_cache *cex;
2054
	struct ext4_sb_info *sbi;
2055
	int ret = 0;
A
Alex Tomas 已提交
2056

2057
	/*
2058 2059 2060
	 * We borrow i_block_reservation_lock to protect i_cached_extent
	 */
	spin_lock(&EXT4_I(inode)->i_block_reservation_lock);
A
Alex Tomas 已提交
2061
	cex = &EXT4_I(inode)->i_cached_extent;
2062
	sbi = EXT4_SB(inode->i_sb);
A
Alex Tomas 已提交
2063 2064

	/* has cache valid data? */
2065
	if (cex->ec_len == 0)
2066
		goto errout;
A
Alex Tomas 已提交
2067

2068
	if (in_range(block, cex->ec_block, cex->ec_len)) {
D
Dave Kleikamp 已提交
2069
		ex->ee_block = cpu_to_le32(cex->ec_block);
2070
		ext4_ext_store_pblock(ex, cex->ec_start);
D
Dave Kleikamp 已提交
2071
		ex->ee_len = cpu_to_le16(cex->ec_len);
2072 2073 2074
		ext_debug("%u cached by %u:%u:%llu\n",
				block,
				cex->ec_block, cex->ec_len, cex->ec_start);
2075
		ret = 1;
A
Alex Tomas 已提交
2076
	}
2077
errout:
2078 2079 2080 2081
	if (!ret)
		sbi->extent_cache_misses++;
	else
		sbi->extent_cache_hits++;
2082 2083
	spin_unlock(&EXT4_I(inode)->i_block_reservation_lock);
	return ret;
A
Alex Tomas 已提交
2084 2085 2086
}

/*
2087 2088 2089 2090
 * ext4_ext_rm_idx:
 * removes index from the index block.
 * It's used in truncate case only, thus all requests are for
 * last index in the block only.
A
Alex Tomas 已提交
2091
 */
A
Aneesh Kumar K.V 已提交
2092
static int ext4_ext_rm_idx(handle_t *handle, struct inode *inode,
A
Alex Tomas 已提交
2093 2094 2095
			struct ext4_ext_path *path)
{
	int err;
2096
	ext4_fsblk_t leaf;
A
Alex Tomas 已提交
2097 2098 2099

	/* free index block */
	path--;
2100
	leaf = ext4_idx_pblock(path->p_idx);
2101 2102 2103 2104
	if (unlikely(path->p_hdr->eh_entries == 0)) {
		EXT4_ERROR_INODE(inode, "path->p_hdr->eh_entries == 0");
		return -EIO;
	}
2105 2106
	err = ext4_ext_get_access(handle, inode, path);
	if (err)
A
Alex Tomas 已提交
2107
		return err;
M
Marcin Slusarz 已提交
2108
	le16_add_cpu(&path->p_hdr->eh_entries, -1);
2109 2110
	err = ext4_ext_dirty(handle, inode, path);
	if (err)
A
Alex Tomas 已提交
2111
		return err;
2112
	ext_debug("index is empty, remove it, free block %llu\n", leaf);
2113
	ext4_free_blocks(handle, inode, NULL, leaf, 1,
2114
			 EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET);
A
Alex Tomas 已提交
2115 2116 2117 2118
	return err;
}

/*
2119 2120 2121 2122 2123
 * 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 已提交
2124
 */
2125
int ext4_ext_calc_credits_for_single_extent(struct inode *inode, int nrblocks,
A
Alex Tomas 已提交
2126 2127 2128
						struct ext4_ext_path *path)
{
	if (path) {
2129
		int depth = ext_depth(inode);
2130
		int ret = 0;
2131

A
Alex Tomas 已提交
2132 2133
		/* probably there is space in leaf? */
		if (le16_to_cpu(path[depth].p_hdr->eh_entries)
2134
				< le16_to_cpu(path[depth].p_hdr->eh_max)) {
A
Alex Tomas 已提交
2135

2136 2137 2138 2139 2140 2141 2142 2143
			/*
			 *  There are some space in the leaf tree, no
			 *  need to account for leaf block credit
			 *
			 *  bitmaps and block group descriptor blocks
			 *  and other metadat blocks still need to be
			 *  accounted.
			 */
2144
			/* 1 bitmap, 1 block group descriptor */
2145
			ret = 2 + EXT4_META_TRANS_BLOCKS(inode->i_sb);
2146
			return ret;
2147 2148
		}
	}
A
Alex Tomas 已提交
2149

2150
	return ext4_chunk_trans_blocks(inode, nrblocks);
2151
}
A
Alex Tomas 已提交
2152

2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163
/*
 * How many index/leaf blocks need to change/allocate to modify nrblocks?
 *
 * if nrblocks are fit in a single extent (chunk flag is 1), then
 * in the worse case, each tree level index/leaf need to be changed
 * if the tree split due to insert a new extent, then the old tree
 * index/leaf need to be updated too
 *
 * If the nrblocks are discontiguous, they could cause
 * the whole tree split more than once, but this is really rare.
 */
2164
int ext4_ext_index_trans_blocks(struct inode *inode, int nrblocks, int chunk)
2165 2166 2167
{
	int index;
	int depth = ext_depth(inode);
A
Alex Tomas 已提交
2168

2169 2170 2171 2172
	if (chunk)
		index = depth * 2;
	else
		index = depth * 3;
A
Alex Tomas 已提交
2173

2174
	return index;
A
Alex Tomas 已提交
2175 2176 2177 2178
}

static int ext4_remove_blocks(handle_t *handle, struct inode *inode,
				struct ext4_extent *ex,
A
Aneesh Kumar K.V 已提交
2179
				ext4_lblk_t from, ext4_lblk_t to)
A
Alex Tomas 已提交
2180
{
A
Amit Arora 已提交
2181
	unsigned short ee_len =  ext4_ext_get_actual_len(ex);
2182
	int flags = EXT4_FREE_BLOCKS_FORGET;
A
Alex Tomas 已提交
2183

2184
	if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode))
2185
		flags |= EXT4_FREE_BLOCKS_METADATA;
A
Alex Tomas 已提交
2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201
#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 已提交
2202
	    && to == le32_to_cpu(ex->ee_block) + ee_len - 1) {
A
Alex Tomas 已提交
2203
		/* tail removal */
A
Aneesh Kumar K.V 已提交
2204
		ext4_lblk_t num;
2205
		ext4_fsblk_t start;
A
Aneesh Kumar K.V 已提交
2206

A
Amit Arora 已提交
2207
		num = le32_to_cpu(ex->ee_block) + ee_len - from;
2208
		start = ext4_ext_pblock(ex) + ee_len - num;
A
Aneesh Kumar K.V 已提交
2209
		ext_debug("free last %u blocks starting %llu\n", num, start);
2210
		ext4_free_blocks(handle, inode, NULL, start, num, flags);
A
Alex Tomas 已提交
2211
	} else if (from == le32_to_cpu(ex->ee_block)
A
Amit Arora 已提交
2212
		   && to <= le32_to_cpu(ex->ee_block) + ee_len - 1) {
A
Allison Henderson 已提交
2213 2214 2215 2216 2217 2218 2219 2220 2221 2222
		/* head removal */
		ext4_lblk_t num;
		ext4_fsblk_t start;

		num = to - from;
		start = ext4_ext_pblock(ex);

		ext_debug("free first %u blocks starting %llu\n", num, start);
		ext4_free_blocks(handle, inode, 0, start, num, flags);

A
Alex Tomas 已提交
2223
	} else {
A
Aneesh Kumar K.V 已提交
2224 2225 2226
		printk(KERN_INFO "strange request: removal(2) "
				"%u-%u from %u:%u\n",
				from, to, le32_to_cpu(ex->ee_block), ee_len);
A
Alex Tomas 已提交
2227 2228 2229 2230
	}
	return 0;
}

A
Allison Henderson 已提交
2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242

/*
 * ext4_ext_rm_leaf() Removes the extents associated with the
 * blocks appearing between "start" and "end", and splits the extents
 * if "start" and "end" appear in the same extent
 *
 * @handle: The journal handle
 * @inode:  The files inode
 * @path:   The path to the leaf
 * @start:  The first block to remove
 * @end:   The last block to remove
 */
A
Alex Tomas 已提交
2243 2244
static int
ext4_ext_rm_leaf(handle_t *handle, struct inode *inode,
A
Allison Henderson 已提交
2245 2246
		struct ext4_ext_path *path, ext4_lblk_t start,
		ext4_lblk_t end)
A
Alex Tomas 已提交
2247 2248 2249 2250
{
	int err = 0, correct_index = 0;
	int depth = ext_depth(inode), credits;
	struct ext4_extent_header *eh;
A
Aneesh Kumar K.V 已提交
2251 2252 2253
	ext4_lblk_t a, b, block;
	unsigned num;
	ext4_lblk_t ex_ee_block;
A
Alex Tomas 已提交
2254
	unsigned short ex_ee_len;
A
Amit Arora 已提交
2255
	unsigned uninitialized = 0;
A
Alex Tomas 已提交
2256
	struct ext4_extent *ex;
A
Allison Henderson 已提交
2257
	struct ext4_map_blocks map;
A
Alex Tomas 已提交
2258

2259
	/* the header must be checked already in ext4_ext_remove_space() */
A
Aneesh Kumar K.V 已提交
2260
	ext_debug("truncate since %u in leaf\n", start);
A
Alex Tomas 已提交
2261 2262 2263
	if (!path[depth].p_hdr)
		path[depth].p_hdr = ext_block_hdr(path[depth].p_bh);
	eh = path[depth].p_hdr;
2264 2265 2266 2267
	if (unlikely(path[depth].p_hdr == NULL)) {
		EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
		return -EIO;
	}
A
Alex Tomas 已提交
2268 2269 2270 2271
	/* find where to start removing */
	ex = EXT_LAST_EXTENT(eh);

	ex_ee_block = le32_to_cpu(ex->ee_block);
A
Amit Arora 已提交
2272
	ex_ee_len = ext4_ext_get_actual_len(ex);
A
Alex Tomas 已提交
2273 2274 2275

	while (ex >= EXT_FIRST_EXTENT(eh) &&
			ex_ee_block + ex_ee_len > start) {
2276 2277 2278 2279 2280 2281

		if (ext4_ext_is_uninitialized(ex))
			uninitialized = 1;
		else
			uninitialized = 0;

2282 2283
		ext_debug("remove ext %u:[%d]%d\n", ex_ee_block,
			 uninitialized, ex_ee_len);
A
Alex Tomas 已提交
2284 2285 2286
		path[depth].p_ext = ex;

		a = ex_ee_block > start ? ex_ee_block : start;
A
Allison Henderson 已提交
2287 2288
		b = ex_ee_block+ex_ee_len - 1 < end ?
			ex_ee_block+ex_ee_len - 1 : end;
A
Alex Tomas 已提交
2289 2290 2291

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

A
Allison Henderson 已提交
2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339
		/* If this extent is beyond the end of the hole, skip it */
		if (end <= ex_ee_block) {
			ex--;
			ex_ee_block = le32_to_cpu(ex->ee_block);
			ex_ee_len = ext4_ext_get_actual_len(ex);
			continue;
		} else if (a != ex_ee_block &&
			b != ex_ee_block + ex_ee_len - 1) {
			/*
			 * If this is a truncate, then this condition should
			 * never happen because at least one of the end points
			 * needs to be on the edge of the extent.
			 */
			if (end == EXT_MAX_BLOCK) {
				ext_debug("  bad truncate %u:%u\n",
						start, end);
				block = 0;
				num = 0;
				err = -EIO;
				goto out;
			}
			/*
			 * else this is a hole punch, so the extent needs to
			 * be split since neither edge of the hole is on the
			 * extent edge
			 */
			else{
				map.m_pblk = ext4_ext_pblock(ex);
				map.m_lblk = ex_ee_block;
				map.m_len = b - ex_ee_block;

				err = ext4_split_extent(handle,
					inode, path, &map, 0,
					EXT4_GET_BLOCKS_PUNCH_OUT_EXT |
					EXT4_GET_BLOCKS_PRE_IO);

				if (err < 0)
					goto out;

				ex_ee_len = ext4_ext_get_actual_len(ex);

				b = ex_ee_block+ex_ee_len - 1 < end ?
					ex_ee_block+ex_ee_len - 1 : end;

				/* Then remove tail of this extent */
				block = ex_ee_block;
				num = a - block;
			}
A
Alex Tomas 已提交
2340 2341 2342 2343 2344 2345
		} else if (a != ex_ee_block) {
			/* remove tail of the extent */
			block = ex_ee_block;
			num = a - block;
		} else if (b != ex_ee_block + ex_ee_len - 1) {
			/* remove head of the extent */
A
Allison Henderson 已提交
2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358
			block = b;
			num =  ex_ee_block + ex_ee_len - b;

			/*
			 * If this is a truncate, this condition
			 * should never happen
			 */
			if (end == EXT_MAX_BLOCK) {
				ext_debug("  bad truncate %u:%u\n",
					start, end);
				err = -EIO;
				goto out;
			}
A
Alex Tomas 已提交
2359 2360 2361 2362
		} else {
			/* remove whole extent: excellent! */
			block = ex_ee_block;
			num = 0;
A
Allison Henderson 已提交
2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375
			if (a != ex_ee_block) {
				ext_debug("  bad truncate %u:%u\n",
					start, end);
				err = -EIO;
				goto out;
			}

			if (b != ex_ee_block + ex_ee_len - 1) {
				ext_debug("  bad truncate %u:%u\n",
					start, end);
				err = -EIO;
				goto out;
			}
A
Alex Tomas 已提交
2376 2377
		}

2378 2379 2380 2381 2382 2383 2384
		/*
		 * 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 已提交
2385 2386 2387 2388
		if (ex == EXT_FIRST_EXTENT(eh)) {
			correct_index = 1;
			credits += (ext_depth(inode)) + 1;
		}
D
Dmitry Monakhov 已提交
2389
		credits += EXT4_MAXQUOTAS_TRANS_BLOCKS(inode->i_sb);
A
Alex Tomas 已提交
2390

2391
		err = ext4_ext_truncate_extend_restart(handle, inode, credits);
2392
		if (err)
A
Alex Tomas 已提交
2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403
			goto out;

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

		err = ext4_remove_blocks(handle, inode, ex, a, b);
		if (err)
			goto out;

		if (num == 0) {
2404
			/* this extent is removed; mark slot entirely unused */
2405
			ext4_ext_store_pblock(ex, 0);
A
Allison Henderson 已提交
2406 2407 2408 2409 2410 2411 2412
		} else if (block != ex_ee_block) {
			/*
			 * If this was a head removal, then we need to update
			 * the physical block since it is now at a different
			 * location
			 */
			ext4_ext_store_pblock(ex, ext4_ext_pblock(ex) + (b-a));
A
Alex Tomas 已提交
2413 2414 2415 2416
		}

		ex->ee_block = cpu_to_le32(block);
		ex->ee_len = cpu_to_le16(num);
2417 2418 2419 2420 2421
		/*
		 * Do not mark uninitialized if all the blocks in the
		 * extent have been removed.
		 */
		if (uninitialized && num)
A
Amit Arora 已提交
2422
			ext4_ext_mark_uninitialized(ex);
A
Alex Tomas 已提交
2423 2424 2425 2426 2427

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

A
Allison Henderson 已提交
2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448
		/*
		 * If the extent was completely released,
		 * we need to remove it from the leaf
		 */
		if (num == 0) {
			if (end != EXT_MAX_BLOCK) {
				/*
				 * 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);
		}

2449
		ext_debug("new extent: %u:%u:%llu\n", block, num,
2450
				ext4_ext_pblock(ex));
A
Alex Tomas 已提交
2451 2452
		ex--;
		ex_ee_block = le32_to_cpu(ex->ee_block);
A
Amit Arora 已提交
2453
		ex_ee_len = ext4_ext_get_actual_len(ex);
A
Alex Tomas 已提交
2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468
	}

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

	/* 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)
		err = ext4_ext_rm_idx(handle, inode, path + depth);

out:
	return err;
}

/*
2469 2470
 * ext4_ext_more_to_rm:
 * returns 1 if current index has to be freed (even partial)
A
Alex Tomas 已提交
2471
 */
2472
static int
A
Alex Tomas 已提交
2473 2474 2475 2476 2477 2478 2479 2480
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;

	/*
2481
	 * if truncate on deeper level happened, it wasn't partial,
A
Alex Tomas 已提交
2482 2483 2484 2485 2486 2487 2488
	 * 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;
}

A
Allison Henderson 已提交
2489 2490
static int ext4_ext_remove_space(struct inode *inode, ext4_lblk_t start,
				ext4_lblk_t end)
A
Alex Tomas 已提交
2491 2492 2493 2494 2495
{
	struct super_block *sb = inode->i_sb;
	int depth = ext_depth(inode);
	struct ext4_ext_path *path;
	handle_t *handle;
2496
	int i, err;
A
Alex Tomas 已提交
2497

A
Aneesh Kumar K.V 已提交
2498
	ext_debug("truncate since %u\n", start);
A
Alex Tomas 已提交
2499 2500 2501 2502 2503 2504

	/* probably first extent we're gonna free will be last in block */
	handle = ext4_journal_start(inode, depth + 1);
	if (IS_ERR(handle))
		return PTR_ERR(handle);

2505
again:
A
Alex Tomas 已提交
2506 2507 2508
	ext4_ext_invalidate_cache(inode);

	/*
2509 2510
	 * We start scanning from right side, freeing all the blocks
	 * after i_size and walking into the tree depth-wise.
A
Alex Tomas 已提交
2511
	 */
2512
	depth = ext_depth(inode);
2513
	path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 1), GFP_NOFS);
A
Alex Tomas 已提交
2514 2515 2516 2517
	if (path == NULL) {
		ext4_journal_stop(handle);
		return -ENOMEM;
	}
2518
	path[0].p_depth = depth;
A
Alex Tomas 已提交
2519
	path[0].p_hdr = ext_inode_hdr(inode);
2520
	if (ext4_ext_check(inode, path[0].p_hdr, depth)) {
A
Alex Tomas 已提交
2521 2522 2523
		err = -EIO;
		goto out;
	}
2524
	i = err = 0;
A
Alex Tomas 已提交
2525 2526 2527 2528

	while (i >= 0 && err == 0) {
		if (i == depth) {
			/* this is leaf block */
A
Allison Henderson 已提交
2529 2530
			err = ext4_ext_rm_leaf(handle, inode, path,
					start, end);
2531
			/* root level has p_bh == NULL, brelse() eats this */
A
Alex Tomas 已提交
2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542 2543 2544
			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) {
2545
			/* this level hasn't been touched yet */
A
Alex Tomas 已提交
2546 2547 2548 2549 2550 2551
			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 {
2552
			/* we were already here, see at next index */
A
Alex Tomas 已提交
2553 2554 2555 2556 2557 2558 2559
			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)) {
2560
			struct buffer_head *bh;
A
Alex Tomas 已提交
2561
			/* go to the next level */
2562
			ext_debug("move to level %d (block %llu)\n",
2563
				  i + 1, ext4_idx_pblock(path[i].p_idx));
A
Alex Tomas 已提交
2564
			memset(path + i + 1, 0, sizeof(*path));
2565
			bh = sb_bread(sb, ext4_idx_pblock(path[i].p_idx));
2566
			if (!bh) {
A
Alex Tomas 已提交
2567 2568 2569 2570
				/* should we reset i_size? */
				err = -EIO;
				break;
			}
2571 2572 2573 2574
			if (WARN_ON(i + 1 > depth)) {
				err = -EIO;
				break;
			}
2575
			if (ext4_ext_check(inode, ext_block_hdr(bh),
2576 2577 2578 2579 2580
							depth - i - 1)) {
				err = -EIO;
				break;
			}
			path[i + 1].p_bh = bh;
A
Alex Tomas 已提交
2581

2582 2583
			/* save actual number of indexes since this
			 * number is changed at the next iteration */
A
Alex Tomas 已提交
2584 2585 2586
			path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries);
			i++;
		} else {
2587
			/* we finished processing this index, go up */
A
Alex Tomas 已提交
2588
			if (path[i].p_hdr->eh_entries == 0 && i > 0) {
2589
				/* index is empty, remove it;
A
Alex Tomas 已提交
2590 2591 2592 2593
				 * handle must be already prepared by the
				 * truncatei_leaf() */
				err = ext4_ext_rm_idx(handle, inode, path + i);
			}
2594
			/* root level has p_bh == NULL, brelse() eats this */
A
Alex Tomas 已提交
2595 2596 2597 2598 2599 2600 2601 2602 2603 2604
			brelse(path[i].p_bh);
			path[i].p_bh = NULL;
			i--;
			ext_debug("return to level %d\n", i);
		}
	}

	/* TODO: flexible tree reduction should be here */
	if (path->p_hdr->eh_entries == 0) {
		/*
2605 2606
		 * truncate to zero freed all the tree,
		 * so we need to correct eh_depth
A
Alex Tomas 已提交
2607 2608 2609 2610 2611
		 */
		err = ext4_ext_get_access(handle, inode, path);
		if (err == 0) {
			ext_inode_hdr(inode)->eh_depth = 0;
			ext_inode_hdr(inode)->eh_max =
2612
				cpu_to_le16(ext4_ext_space_root(inode, 0));
A
Alex Tomas 已提交
2613 2614 2615 2616 2617 2618
			err = ext4_ext_dirty(handle, inode, path);
		}
	}
out:
	ext4_ext_drop_refs(path);
	kfree(path);
2619 2620
	if (err == -EAGAIN)
		goto again;
A
Alex Tomas 已提交
2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634
	ext4_journal_stop(handle);

	return err;
}

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

2635
	if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS)) {
2636
#if defined(AGGRESSIVE_TEST) || defined(CHECK_BINSEARCH) || defined(EXTENTS_STATS)
2637
		printk(KERN_INFO "EXT4-fs: file extents enabled");
2638 2639
#ifdef AGGRESSIVE_TEST
		printk(", aggressive tests");
A
Alex Tomas 已提交
2640 2641 2642 2643 2644 2645 2646 2647
#endif
#ifdef CHECK_BINSEARCH
		printk(", check binsearch");
#endif
#ifdef EXTENTS_STATS
		printk(", stats");
#endif
		printk("\n");
2648
#endif
A
Alex Tomas 已提交
2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661
#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)
{
2662
	if (!EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS))
A
Alex Tomas 已提交
2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676
		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
}

2677 2678 2679
/* 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)
{
2680 2681
	ext4_fsblk_t ee_pblock;
	unsigned int ee_len;
2682
	int ret;
2683 2684

	ee_len    = ext4_ext_get_actual_len(ex);
2685
	ee_pblock = ext4_ext_pblock(ex);
2686

2687
	ret = sb_issue_zeroout(inode->i_sb, ee_pblock, ee_len, GFP_NOFS);
2688 2689
	if (ret > 0)
		ret = 0;
2690

2691
	return ret;
2692 2693
}

2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724 2725 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749 2750 2751 2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 2766 2767 2768 2769 2770 2771 2772 2773 2774 2775 2776 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 2793 2794 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 2823 2824 2825 2826 2827 2828 2829 2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841 2842 2843 2844 2845 2846 2847 2848 2849 2850 2851 2852 2853 2854 2855
/*
 * used by extent splitting.
 */
#define EXT4_EXT_MAY_ZEROOUT	0x1  /* safe to zeroout if split fails \
					due to ENOSPC */
#define EXT4_EXT_MARK_UNINIT1	0x2  /* mark first half uninitialized */
#define EXT4_EXT_MARK_UNINIT2	0x4  /* mark second half uninitialized */

/*
 * 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
 *		 the states(init or uninit) of new extents.
 * @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,
			     struct ext4_ext_path *path,
			     ext4_lblk_t split,
			     int split_flag,
			     int flags)
{
	ext4_fsblk_t newblock;
	ext4_lblk_t ee_block;
	struct ext4_extent *ex, newex, orig_ex;
	struct ext4_extent *ex2 = NULL;
	unsigned int ee_len, depth;
	int err = 0;

	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));

	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.
		 */
		if (split_flag & EXT4_EXT_MARK_UNINIT2)
			ext4_ext_mark_uninitialized(ex);
		else
			ext4_ext_mark_initialized(ex);

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

		err = ext4_ext_dirty(handle, inode, path + depth);
		goto out;
	}

	/* case a */
	memcpy(&orig_ex, ex, sizeof(orig_ex));
	ex->ee_len = cpu_to_le16(split - ee_block);
	if (split_flag & EXT4_EXT_MARK_UNINIT1)
		ext4_ext_mark_uninitialized(ex);

	/*
	 * 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);
	if (split_flag & EXT4_EXT_MARK_UNINIT2)
		ext4_ext_mark_uninitialized(ex2);

	err = ext4_ext_insert_extent(handle, inode, path, &newex, flags);
	if (err == -ENOSPC && (EXT4_EXT_MAY_ZEROOUT & split_flag)) {
		err = ext4_ext_zeroout(inode, &orig_ex);
		if (err)
			goto fix_extent_len;
		/* update the extent length and mark as initialized */
		ex->ee_len = cpu_to_le32(ee_len);
		ext4_ext_try_to_merge(inode, path, ex);
		err = ext4_ext_dirty(handle, inode, path + depth);
		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;
	ext4_ext_dirty(handle, inode, path + depth);
	return err;
}

/*
 * ext4_split_extents() splits an extent and mark extent which is covered
 * by @map as split_flags indicates
 *
 * It may result in splitting the extent into multiple extents (upto three)
 * 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,
			      struct ext4_ext_path *path,
			      struct ext4_map_blocks *map,
			      int split_flag,
			      int flags)
{
	ext4_lblk_t ee_block;
	struct ext4_extent *ex;
	unsigned int ee_len, depth;
	int err = 0;
	int uninitialized;
	int split_flag1, flags1;

	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);
	uninitialized = ext4_ext_is_uninitialized(ex);

	if (map->m_lblk + map->m_len < ee_block + ee_len) {
		split_flag1 = split_flag & EXT4_EXT_MAY_ZEROOUT ?
			      EXT4_EXT_MAY_ZEROOUT : 0;
		flags1 = flags | EXT4_GET_BLOCKS_PRE_IO;
		if (uninitialized)
			split_flag1 |= EXT4_EXT_MARK_UNINIT1 |
				       EXT4_EXT_MARK_UNINIT2;
		err = ext4_split_extent_at(handle, inode, path,
				map->m_lblk + map->m_len, split_flag1, flags1);
2856 2857
		if (err)
			goto out;
2858 2859 2860 2861 2862 2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874 2875 2876 2877 2878 2879 2880 2881 2882
	}

	ext4_ext_drop_refs(path);
	path = ext4_ext_find_extent(inode, map->m_lblk, path);
	if (IS_ERR(path))
		return PTR_ERR(path);

	if (map->m_lblk >= ee_block) {
		split_flag1 = split_flag & EXT4_EXT_MAY_ZEROOUT ?
			      EXT4_EXT_MAY_ZEROOUT : 0;
		if (uninitialized)
			split_flag1 |= EXT4_EXT_MARK_UNINIT1;
		if (split_flag & EXT4_EXT_MARK_UNINIT2)
			split_flag1 |= EXT4_EXT_MARK_UNINIT2;
		err = ext4_split_extent_at(handle, inode, path,
				map->m_lblk, split_flag1, flags);
		if (err)
			goto out;
	}

	ext4_ext_show_leaf(inode, path);
out:
	return err ? err : map->m_len;
}

2883
#define EXT4_EXT_ZERO_LEN 7
2884
/*
2885
 * This function is called by ext4_ext_map_blocks() if someone tries to write
2886
 * to an uninitialized extent. It may result in splitting the uninitialized
L
Lucas De Marchi 已提交
2887
 * extent into multiple extents (up to three - one initialized and two
2888 2889 2890 2891 2892 2893
 * uninitialized).
 * 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
 */
A
Aneesh Kumar K.V 已提交
2894
static int ext4_ext_convert_to_initialized(handle_t *handle,
2895 2896 2897
					   struct inode *inode,
					   struct ext4_map_blocks *map,
					   struct ext4_ext_path *path)
2898
{
2899 2900 2901
	struct ext4_map_blocks split_map;
	struct ext4_extent zero_ex;
	struct ext4_extent *ex;
2902
	ext4_lblk_t ee_block, eof_block;
A
Aneesh Kumar K.V 已提交
2903
	unsigned int allocated, ee_len, depth;
2904
	int err = 0;
2905
	int split_flag = 0;
2906 2907 2908

	ext_debug("ext4_ext_convert_to_initialized: inode %lu, logical"
		"block %llu, max_blocks %u\n", inode->i_ino,
2909
		(unsigned long long)map->m_lblk, map->m_len);
2910 2911 2912

	eof_block = (inode->i_size + inode->i_sb->s_blocksize - 1) >>
		inode->i_sb->s_blocksize_bits;
2913 2914
	if (eof_block < map->m_lblk + map->m_len)
		eof_block = map->m_lblk + map->m_len;
2915 2916 2917 2918 2919

	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);
2920
	allocated = ee_len - (map->m_lblk - ee_block);
2921

2922
	WARN_ON(map->m_lblk < ee_block);
2923 2924 2925 2926
	/*
	 * It is safe to convert extent to initialized via explicit
	 * zeroout only if extent is fully insde i_size or new_size.
	 */
2927
	split_flag |= ee_block + ee_len <= eof_block ? EXT4_EXT_MAY_ZEROOUT : 0;
2928

2929
	/* If extent has less than 2*EXT4_EXT_ZERO_LEN zerout directly */
2930 2931 2932
	if (ee_len <= 2*EXT4_EXT_ZERO_LEN &&
	    (EXT4_EXT_MAY_ZEROOUT & split_flag)) {
		err = ext4_ext_zeroout(inode, ex);
2933
		if (err)
2934 2935 2936 2937 2938
			goto out;

		err = ext4_ext_get_access(handle, inode, path + depth);
		if (err)
			goto out;
2939 2940 2941 2942
		ext4_ext_mark_initialized(ex);
		ext4_ext_try_to_merge(inode, path, ex);
		err = ext4_ext_dirty(handle, inode, path + depth);
		goto out;
2943
	}
2944

2945
	/*
2946 2947 2948 2949 2950
	 * four cases:
	 * 1. split the extent into three extents.
	 * 2. split the extent into two extents, zeroout the first half.
	 * 3. split the extent into two extents, zeroout the second half.
	 * 4. split the extent into two extents with out zeroout.
2951
	 */
2952 2953 2954 2955 2956 2957 2958 2959
	split_map.m_lblk = map->m_lblk;
	split_map.m_len = map->m_len;

	if (allocated > map->m_len) {
		if (allocated <= EXT4_EXT_ZERO_LEN &&
		    (EXT4_EXT_MAY_ZEROOUT & split_flag)) {
			/* case 3 */
			zero_ex.ee_block =
2960 2961
					 cpu_to_le32(map->m_lblk);
			zero_ex.ee_len = cpu_to_le16(allocated);
2962 2963 2964
			ext4_ext_store_pblock(&zero_ex,
				ext4_ext_pblock(ex) + map->m_lblk - ee_block);
			err = ext4_ext_zeroout(inode, &zero_ex);
2965 2966
			if (err)
				goto out;
2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984
			split_map.m_lblk = map->m_lblk;
			split_map.m_len = allocated;
		} else if ((map->m_lblk - ee_block + map->m_len <
			   EXT4_EXT_ZERO_LEN) &&
			   (EXT4_EXT_MAY_ZEROOUT & split_flag)) {
			/* case 2 */
			if (map->m_lblk != ee_block) {
				zero_ex.ee_block = ex->ee_block;
				zero_ex.ee_len = cpu_to_le16(map->m_lblk -
							ee_block);
				ext4_ext_store_pblock(&zero_ex,
						      ext4_ext_pblock(ex));
				err = ext4_ext_zeroout(inode, &zero_ex);
				if (err)
					goto out;
			}

			split_map.m_lblk = ee_block;
2985 2986
			split_map.m_len = map->m_lblk - ee_block + map->m_len;
			allocated = map->m_len;
2987 2988
		}
	}
2989 2990 2991 2992 2993 2994

	allocated = ext4_split_extent(handle, inode, path,
				       &split_map, split_flag, 0);
	if (allocated < 0)
		err = allocated;

2995 2996 2997 2998
out:
	return err ? err : allocated;
}

2999
/*
3000
 * This function is called by ext4_ext_map_blocks() from
3001 3002 3003
 * ext4_get_blocks_dio_write() when DIO to write
 * to an uninitialized extent.
 *
P
Paul Bolle 已提交
3004
 * Writing to an uninitialized extent may result in splitting the uninitialized
3005
 * extent into multiple /initialized uninitialized extents (up to three)
3006 3007 3008 3009 3010 3011
 * There are three possibilities:
 *   a> There is no split required: Entire extent should be uninitialized
 *   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
 *
 * One of more index blocks maybe needed if the extent tree grow after
3012
 * the uninitialized extent split. To prevent ENOSPC occur at the IO
3013
 * complete, we need to split the uninitialized extent before DIO submit
3014
 * the IO. The uninitialized extent called at this time will be split
3015 3016 3017
 * into three uninitialized extent(at most). After IO complete, the part
 * being filled will be convert to initialized by the end_io callback function
 * via ext4_convert_unwritten_extents().
3018 3019
 *
 * Returns the size of uninitialized extent to be written on success.
3020 3021 3022
 */
static int ext4_split_unwritten_extents(handle_t *handle,
					struct inode *inode,
3023
					struct ext4_map_blocks *map,
3024 3025 3026
					struct ext4_ext_path *path,
					int flags)
{
3027 3028 3029 3030 3031
	ext4_lblk_t eof_block;
	ext4_lblk_t ee_block;
	struct ext4_extent *ex;
	unsigned int ee_len;
	int split_flag = 0, depth;
3032 3033 3034

	ext_debug("ext4_split_unwritten_extents: inode %lu, logical"
		"block %llu, max_blocks %u\n", inode->i_ino,
3035
		(unsigned long long)map->m_lblk, map->m_len);
3036 3037 3038

	eof_block = (inode->i_size + inode->i_sb->s_blocksize - 1) >>
		inode->i_sb->s_blocksize_bits;
3039 3040
	if (eof_block < map->m_lblk + map->m_len)
		eof_block = map->m_lblk + map->m_len;
3041 3042 3043 3044
	/*
	 * It is safe to convert extent to initialized via explicit
	 * zeroout only if extent is fully insde i_size or new_size.
	 */
3045 3046 3047 3048
	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);
3049

3050 3051
	split_flag |= ee_block + ee_len <= eof_block ? EXT4_EXT_MAY_ZEROOUT : 0;
	split_flag |= EXT4_EXT_MARK_UNINIT2;
3052

3053 3054
	flags |= EXT4_GET_BLOCKS_PRE_IO;
	return ext4_split_extent(handle, inode, path, map, split_flag, flags);
3055
}
3056

3057
static int ext4_convert_unwritten_extents_endio(handle_t *handle,
3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069
					      struct inode *inode,
					      struct ext4_ext_path *path)
{
	struct ext4_extent *ex;
	struct ext4_extent_header *eh;
	int depth;
	int err = 0;

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

3070 3071 3072 3073 3074
	ext_debug("ext4_convert_unwritten_extents_endio: inode %lu, logical"
		"block %llu, max_blocks %u\n", inode->i_ino,
		(unsigned long long)le32_to_cpu(ex->ee_block),
		ext4_ext_get_actual_len(ex));

3075 3076 3077 3078 3079 3080
	err = ext4_ext_get_access(handle, inode, path + depth);
	if (err)
		goto out;
	/* first mark the extent as initialized */
	ext4_ext_mark_initialized(ex);

3081 3082
	/* note: ext4_ext_correct_indexes() isn't needed here because
	 * borders are not changed
3083
	 */
3084 3085
	ext4_ext_try_to_merge(inode, path, ex);

3086 3087 3088 3089 3090 3091 3092
	/* Mark modified extent as dirty */
	err = ext4_ext_dirty(handle, inode, path + depth);
out:
	ext4_ext_show_leaf(inode, path);
	return err;
}

3093 3094 3095 3096 3097 3098 3099 3100
static void unmap_underlying_metadata_blocks(struct block_device *bdev,
			sector_t block, int count)
{
	int i;
	for (i = 0; i < count; i++)
                unmap_underlying_metadata(bdev, block + i);
}

T
Theodore Ts'o 已提交
3101 3102 3103 3104
/*
 * Handle EOFBLOCKS_FL flag, clearing it if necessary
 */
static int check_eofblocks_fl(handle_t *handle, struct inode *inode,
3105
			      ext4_lblk_t lblk,
T
Theodore Ts'o 已提交
3106 3107 3108 3109 3110
			      struct ext4_ext_path *path,
			      unsigned int len)
{
	int i, depth;
	struct ext4_extent_header *eh;
3111
	struct ext4_extent *last_ex;
T
Theodore Ts'o 已提交
3112 3113 3114 3115 3116 3117 3118 3119 3120 3121 3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132 3133

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

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

	if (unlikely(!eh->eh_entries)) {
		EXT4_ERROR_INODE(inode, "eh->eh_entries == 0 and "
				 "EOFBLOCKS_FL set");
		return -EIO;
	}
	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.
	 */
3134
	if (lblk + len < le32_to_cpu(last_ex->ee_block) +
T
Theodore Ts'o 已提交
3135 3136 3137 3138 3139 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149 3150
	    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;
	ext4_clear_inode_flag(inode, EXT4_INODE_EOFBLOCKS);
	return ext4_mark_inode_dirty(handle, inode);
}

3151 3152
static int
ext4_ext_handle_uninitialized_extents(handle_t *handle, struct inode *inode,
3153
			struct ext4_map_blocks *map,
3154
			struct ext4_ext_path *path, int flags,
3155
			unsigned int allocated, ext4_fsblk_t newblock)
3156 3157 3158
{
	int ret = 0;
	int err = 0;
3159
	ext4_io_end_t *io = EXT4_I(inode)->cur_aio_dio;
3160 3161 3162

	ext_debug("ext4_ext_handle_uninitialized_extents: inode %lu, logical"
		  "block %llu, max_blocks %u, flags %d, allocated %u",
3163
		  inode->i_ino, (unsigned long long)map->m_lblk, map->m_len,
3164 3165 3166
		  flags, allocated);
	ext4_ext_show_leaf(inode, path);

3167
	/* get_block() before submit the IO, split the extent */
3168
	if ((flags & EXT4_GET_BLOCKS_PRE_IO)) {
3169 3170
		ret = ext4_split_unwritten_extents(handle, inode, map,
						   path, flags);
3171 3172
		/*
		 * Flag the inode(non aio case) or end_io struct (aio case)
L
Lucas De Marchi 已提交
3173
		 * that this IO needs to conversion to written when IO is
3174 3175
		 * completed
		 */
3176
		if (io && !(io->flag & EXT4_IO_END_UNWRITTEN)) {
3177
			io->flag = EXT4_IO_END_UNWRITTEN;
3178 3179
			atomic_inc(&EXT4_I(inode)->i_aiodio_unwritten);
		} else
3180
			ext4_set_inode_state(inode, EXT4_STATE_DIO_UNWRITTEN);
3181
		if (ext4_should_dioread_nolock(inode))
3182
			map->m_flags |= EXT4_MAP_UNINIT;
3183 3184
		goto out;
	}
3185
	/* IO end_io complete, convert the filled extent to written */
3186
	if ((flags & EXT4_GET_BLOCKS_CONVERT)) {
3187
		ret = ext4_convert_unwritten_extents_endio(handle, inode,
3188
							path);
T
Theodore Ts'o 已提交
3189
		if (ret >= 0) {
3190
			ext4_update_inode_fsync_trans(handle, inode, 1);
3191 3192
			err = check_eofblocks_fl(handle, inode, map->m_lblk,
						 path, map->m_len);
T
Theodore Ts'o 已提交
3193 3194
		} else
			err = ret;
3195 3196 3197 3198 3199 3200 3201 3202 3203 3204 3205 3206 3207 3208 3209 3210 3211 3212 3213
		goto out2;
	}
	/* buffered IO case */
	/*
	 * repeat fallocate creation request
	 * we already have an unwritten extent
	 */
	if (flags & EXT4_GET_BLOCKS_UNINIT_EXT)
		goto map_out;

	/* 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.
		 */
3214
		map->m_flags |= EXT4_MAP_UNWRITTEN;
3215 3216 3217 3218
		goto out1;
	}

	/* buffered write, writepage time, convert*/
3219
	ret = ext4_ext_convert_to_initialized(handle, inode, map, path);
T
Theodore Ts'o 已提交
3220
	if (ret >= 0) {
3221
		ext4_update_inode_fsync_trans(handle, inode, 1);
3222 3223
		err = check_eofblocks_fl(handle, inode, map->m_lblk, path,
					 map->m_len);
T
Theodore Ts'o 已提交
3224 3225 3226 3227
		if (err < 0)
			goto out2;
	}

3228 3229 3230 3231 3232 3233
out:
	if (ret <= 0) {
		err = ret;
		goto out2;
	} else
		allocated = ret;
3234
	map->m_flags |= EXT4_MAP_NEW;
3235 3236 3237 3238 3239 3240 3241
	/*
	 * 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.
	 */
3242
	if (allocated > map->m_len) {
3243
		unmap_underlying_metadata_blocks(inode->i_sb->s_bdev,
3244 3245 3246
					newblock + map->m_len,
					allocated - map->m_len);
		allocated = map->m_len;
3247
	}
3248 3249 3250 3251 3252 3253 3254 3255

	/*
	 * 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
	 */
3256
	if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
3257 3258
		ext4_da_update_reserve_space(inode, allocated, 0);

3259
map_out:
3260
	map->m_flags |= EXT4_MAP_MAPPED;
3261
out1:
3262 3263
	if (allocated > map->m_len)
		allocated = map->m_len;
3264
	ext4_ext_show_leaf(inode, path);
3265 3266
	map->m_pblk = newblock;
	map->m_len = allocated;
3267 3268 3269 3270 3271 3272 3273
out2:
	if (path) {
		ext4_ext_drop_refs(path);
		kfree(path);
	}
	return err ? err : allocated;
}
T
Theodore Ts'o 已提交
3274

3275
/*
3276 3277 3278
 * Block allocation/map/preallocation routine for extents based files
 *
 *
3279
 * Need to be called with
3280 3281
 * 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)
3282 3283 3284 3285 3286 3287 3288 3289 3290 3291
 *
 * 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.
3292
 */
3293 3294
int ext4_ext_map_blocks(handle_t *handle, struct inode *inode,
			struct ext4_map_blocks *map, int flags)
A
Alex Tomas 已提交
3295 3296
{
	struct ext4_ext_path *path = NULL;
T
Theodore Ts'o 已提交
3297
	struct ext4_extent newex, *ex;
3298
	ext4_fsblk_t newblock = 0;
3299
	int err = 0, depth, ret;
3300
	unsigned int allocated = 0;
3301
	struct ext4_allocation_request ar;
3302
	ext4_io_end_t *io = EXT4_I(inode)->cur_aio_dio;
A
Alex Tomas 已提交
3303

3304
	ext_debug("blocks %u/%u requested for inode %lu\n",
3305
		  map->m_lblk, map->m_len, inode->i_ino);
3306
	trace_ext4_ext_map_blocks_enter(inode, map->m_lblk, map->m_len, flags);
A
Alex Tomas 已提交
3307 3308

	/* check in cache */
3309 3310
	if (ext4_ext_in_cache(inode, map->m_lblk, &newex)) {
		if (!newex.ee_start_lo && !newex.ee_start_hi) {
3311
			if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
3312 3313 3314 3315
				/*
				 * block isn't allocated yet and
				 * user doesn't want to allocate it
				 */
A
Alex Tomas 已提交
3316 3317 3318
				goto out2;
			}
			/* we should allocate requested block */
3319
		} else {
A
Alex Tomas 已提交
3320
			/* block is already allocated */
3321
			newblock = map->m_lblk
D
Dave Kleikamp 已提交
3322
				   - le32_to_cpu(newex.ee_block)
3323
				   + ext4_ext_pblock(&newex);
3324
			/* number of remaining blocks in the extent */
3325
			allocated = ext4_ext_get_actual_len(&newex) -
3326
				(map->m_lblk - le32_to_cpu(newex.ee_block));
A
Alex Tomas 已提交
3327 3328 3329 3330 3331
			goto out;
		}
	}

	/* find extent for this block */
3332
	path = ext4_ext_find_extent(inode, map->m_lblk, NULL);
A
Alex Tomas 已提交
3333 3334 3335 3336 3337 3338 3339 3340 3341
	if (IS_ERR(path)) {
		err = PTR_ERR(path);
		path = NULL;
		goto out2;
	}

	depth = ext_depth(inode);

	/*
3342 3343
	 * consistent leaf must not be empty;
	 * this situation is possible, though, _during_ tree modification;
A
Alex Tomas 已提交
3344 3345
	 * this is why assert can't be put in ext4_ext_find_extent()
	 */
3346 3347
	if (unlikely(path[depth].p_ext == NULL && depth != 0)) {
		EXT4_ERROR_INODE(inode, "bad extent address "
3348 3349 3350
				 "lblock: %lu, depth: %d pblock %lld",
				 (unsigned long) map->m_lblk, depth,
				 path[depth].p_block);
3351 3352 3353
		err = -EIO;
		goto out2;
	}
A
Alex Tomas 已提交
3354

3355 3356
	ex = path[depth].p_ext;
	if (ex) {
A
Aneesh Kumar K.V 已提交
3357
		ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
3358
		ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
A
Amit Arora 已提交
3359
		unsigned short ee_len;
3360 3361 3362

		/*
		 * Uninitialized extents are treated as holes, except that
3363
		 * we split out initialized portions during a write.
3364
		 */
A
Amit Arora 已提交
3365
		ee_len = ext4_ext_get_actual_len(ex);
3366
		/* if found extent covers block, simply return it */
3367 3368
		if (in_range(map->m_lblk, ee_block, ee_len)) {
			newblock = map->m_lblk - ee_block + ee_start;
3369
			/* number of remaining blocks in the extent */
3370 3371 3372
			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);
3373

A
Amit Arora 已提交
3374
			/* Do not put uninitialized extent in the cache */
3375
			if (!ext4_ext_is_uninitialized(ex)) {
A
Amit Arora 已提交
3376
				ext4_ext_put_in_cache(inode, ee_block,
3377
							ee_len, ee_start);
3378 3379
				goto out;
			}
3380
			ret = ext4_ext_handle_uninitialized_extents(handle,
3381 3382
					inode, map, path, flags, allocated,
					newblock);
3383
			return ret;
A
Alex Tomas 已提交
3384 3385 3386 3387
		}
	}

	/*
3388
	 * requested block isn't allocated yet;
A
Alex Tomas 已提交
3389 3390
	 * we couldn't try to create block if create flag is zero
	 */
3391
	if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
3392 3393 3394 3395
		/*
		 * put just found gap into cache to speed up
		 * subsequent requests
		 */
3396
		ext4_ext_put_gap_in_cache(inode, path, map->m_lblk);
A
Alex Tomas 已提交
3397 3398 3399
		goto out2;
	}
	/*
3400
	 * Okay, we need to do block allocation.
A
Andrew Morton 已提交
3401
	 */
A
Alex Tomas 已提交
3402

3403
	/* find neighbour allocated blocks */
3404
	ar.lleft = map->m_lblk;
3405 3406 3407
	err = ext4_ext_search_left(inode, path, &ar.lleft, &ar.pleft);
	if (err)
		goto out2;
3408
	ar.lright = map->m_lblk;
3409 3410 3411
	err = ext4_ext_search_right(inode, path, &ar.lright, &ar.pright);
	if (err)
		goto out2;
A
Amit Arora 已提交
3412

3413 3414 3415 3416 3417 3418
	/*
	 * See if request is beyond maximum number of blocks we can have in
	 * a single extent. For an initialized extent this limit is
	 * EXT_INIT_MAX_LEN and for an uninitialized extent this limit is
	 * EXT_UNINIT_MAX_LEN.
	 */
3419
	if (map->m_len > EXT_INIT_MAX_LEN &&
3420
	    !(flags & EXT4_GET_BLOCKS_UNINIT_EXT))
3421 3422
		map->m_len = EXT_INIT_MAX_LEN;
	else if (map->m_len > EXT_UNINIT_MAX_LEN &&
3423
		 (flags & EXT4_GET_BLOCKS_UNINIT_EXT))
3424
		map->m_len = EXT_UNINIT_MAX_LEN;
3425

3426 3427 3428
	/* Check if we can really insert (m_lblk)::(m_lblk + m_len) extent */
	newex.ee_block = cpu_to_le32(map->m_lblk);
	newex.ee_len = cpu_to_le16(map->m_len);
A
Amit Arora 已提交
3429 3430
	err = ext4_ext_check_overlap(inode, &newex, path);
	if (err)
3431
		allocated = ext4_ext_get_actual_len(&newex);
A
Amit Arora 已提交
3432
	else
3433
		allocated = map->m_len;
3434 3435 3436

	/* allocate new block */
	ar.inode = inode;
3437 3438
	ar.goal = ext4_ext_find_goal(inode, path, map->m_lblk);
	ar.logical = map->m_lblk;
3439 3440 3441 3442 3443 3444 3445
	ar.len = allocated;
	if (S_ISREG(inode->i_mode))
		ar.flags = EXT4_MB_HINT_DATA;
	else
		/* disable in-core preallocation for non-regular files */
		ar.flags = 0;
	newblock = ext4_mb_new_blocks(handle, &ar, &err);
A
Alex Tomas 已提交
3446 3447
	if (!newblock)
		goto out2;
3448
	ext_debug("allocate new block: goal %llu, found %llu/%u\n",
3449
		  ar.goal, newblock, allocated);
A
Alex Tomas 已提交
3450 3451

	/* try to insert new extent into found leaf and return */
3452
	ext4_ext_store_pblock(&newex, newblock);
3453
	newex.ee_len = cpu_to_le16(ar.len);
3454 3455
	/* Mark uninitialized */
	if (flags & EXT4_GET_BLOCKS_UNINIT_EXT){
A
Amit Arora 已提交
3456
		ext4_ext_mark_uninitialized(&newex);
3457
		/*
3458
		 * io_end structure was created for every IO write to an
L
Lucas De Marchi 已提交
3459
		 * uninitialized extent. To avoid unnecessary conversion,
3460
		 * here we flag the IO that really needs the conversion.
3461
		 * For non asycn direct IO case, flag the inode state
L
Lucas De Marchi 已提交
3462
		 * that we need to perform conversion when IO is done.
3463
		 */
3464
		if ((flags & EXT4_GET_BLOCKS_PRE_IO)) {
3465
			if (io && !(io->flag & EXT4_IO_END_UNWRITTEN)) {
3466
				io->flag = EXT4_IO_END_UNWRITTEN;
3467 3468
				atomic_inc(&EXT4_I(inode)->i_aiodio_unwritten);
			} else
3469 3470
				ext4_set_inode_state(inode,
						     EXT4_STATE_DIO_UNWRITTEN);
3471
		}
3472
		if (ext4_should_dioread_nolock(inode))
3473
			map->m_flags |= EXT4_MAP_UNINIT;
3474
	}
3475

3476
	err = check_eofblocks_fl(handle, inode, map->m_lblk, path, ar.len);
T
Theodore Ts'o 已提交
3477 3478 3479
	if (err)
		goto out2;

3480
	err = ext4_ext_insert_extent(handle, inode, path, &newex, flags);
3481 3482
	if (err) {
		/* free data blocks we just allocated */
3483 3484
		/* not a good idea to call discard here directly,
		 * but otherwise we'd need to call it every free() */
3485
		ext4_discard_preallocations(inode);
3486
		ext4_free_blocks(handle, inode, NULL, ext4_ext_pblock(&newex),
3487
				 ext4_ext_get_actual_len(&newex), 0);
A
Alex Tomas 已提交
3488
		goto out2;
3489
	}
A
Alex Tomas 已提交
3490 3491

	/* previous routine could use block we allocated */
3492
	newblock = ext4_ext_pblock(&newex);
3493
	allocated = ext4_ext_get_actual_len(&newex);
3494 3495 3496
	if (allocated > map->m_len)
		allocated = map->m_len;
	map->m_flags |= EXT4_MAP_NEW;
A
Alex Tomas 已提交
3497

3498 3499 3500 3501
	/*
	 * Update reserved blocks/metadata blocks after successful
	 * block allocation which had been deferred till now.
	 */
3502
	if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
3503 3504
		ext4_da_update_reserve_space(inode, allocated, 1);

3505 3506 3507 3508 3509
	/*
	 * Cache the extent and update transaction to commit on fdatasync only
	 * when it is _not_ an uninitialized extent.
	 */
	if ((flags & EXT4_GET_BLOCKS_UNINIT_EXT) == 0) {
3510
		ext4_ext_put_in_cache(inode, map->m_lblk, allocated, newblock);
3511 3512 3513
		ext4_update_inode_fsync_trans(handle, inode, 1);
	} else
		ext4_update_inode_fsync_trans(handle, inode, 0);
A
Alex Tomas 已提交
3514
out:
3515 3516
	if (allocated > map->m_len)
		allocated = map->m_len;
A
Alex Tomas 已提交
3517
	ext4_ext_show_leaf(inode, path);
3518 3519 3520
	map->m_flags |= EXT4_MAP_MAPPED;
	map->m_pblk = newblock;
	map->m_len = allocated;
A
Alex Tomas 已提交
3521 3522 3523 3524 3525
out2:
	if (path) {
		ext4_ext_drop_refs(path);
		kfree(path);
	}
3526 3527
	trace_ext4_ext_map_blocks_exit(inode, map->m_lblk,
		newblock, map->m_len, err ? err : allocated);
A
Alex Tomas 已提交
3528 3529 3530
	return err ? err : allocated;
}

3531
void ext4_ext_truncate(struct inode *inode)
A
Alex Tomas 已提交
3532 3533 3534
{
	struct address_space *mapping = inode->i_mapping;
	struct super_block *sb = inode->i_sb;
A
Aneesh Kumar K.V 已提交
3535
	ext4_lblk_t last_block;
A
Alex Tomas 已提交
3536 3537 3538
	handle_t *handle;
	int err = 0;

3539 3540 3541 3542 3543 3544
	/*
	 * finish any pending end_io work so we won't run the risk of
	 * converting any truncated blocks to initialized later
	 */
	ext4_flush_completed_IO(inode);

A
Alex Tomas 已提交
3545 3546 3547
	/*
	 * probably first extent we're gonna free will be last in block
	 */
3548
	err = ext4_writepage_trans_blocks(inode);
A
Alex Tomas 已提交
3549
	handle = ext4_journal_start(inode, err);
3550
	if (IS_ERR(handle))
A
Alex Tomas 已提交
3551 3552
		return;

3553 3554
	if (inode->i_size & (sb->s_blocksize - 1))
		ext4_block_truncate_page(handle, mapping, inode->i_size);
A
Alex Tomas 已提交
3555

3556 3557 3558
	if (ext4_orphan_add(handle, inode))
		goto out_stop;

3559
	down_write(&EXT4_I(inode)->i_data_sem);
A
Alex Tomas 已提交
3560 3561
	ext4_ext_invalidate_cache(inode);

3562
	ext4_discard_preallocations(inode);
3563

A
Alex Tomas 已提交
3564
	/*
3565 3566 3567
	 * TODO: optimization is possible here.
	 * Probably we need not scan at all,
	 * because page truncation is enough.
A
Alex Tomas 已提交
3568 3569 3570 3571 3572 3573 3574 3575
	 */

	/* we have to know where to truncate from in crash case */
	EXT4_I(inode)->i_disksize = inode->i_size;
	ext4_mark_inode_dirty(handle, inode);

	last_block = (inode->i_size + sb->s_blocksize - 1)
			>> EXT4_BLOCK_SIZE_BITS(sb);
A
Allison Henderson 已提交
3576
	err = ext4_ext_remove_space(inode, last_block, EXT_MAX_BLOCK);
A
Alex Tomas 已提交
3577 3578

	/* In a multi-transaction truncate, we only make the final
3579 3580
	 * transaction synchronous.
	 */
A
Alex Tomas 已提交
3581
	if (IS_SYNC(inode))
3582
		ext4_handle_sync(handle);
A
Alex Tomas 已提交
3583

3584
	up_write(&EXT4_I(inode)->i_data_sem);
3585 3586

out_stop:
A
Alex Tomas 已提交
3587
	/*
3588
	 * If this was a simple ftruncate() and the file will remain alive,
A
Alex Tomas 已提交
3589 3590 3591 3592 3593 3594 3595 3596
	 * then we need to clear up the orphan record which we created above.
	 * However, if this was a real unlink then we were called by
	 * ext4_delete_inode(), and we allow that function to clean up the
	 * orphan info for us.
	 */
	if (inode->i_nlink)
		ext4_orphan_del(handle, inode);

3597 3598
	inode->i_mtime = inode->i_ctime = ext4_current_time(inode);
	ext4_mark_inode_dirty(handle, inode);
A
Alex Tomas 已提交
3599 3600 3601
	ext4_journal_stop(handle);
}

3602 3603 3604 3605 3606 3607 3608 3609 3610 3611 3612 3613 3614 3615
static void ext4_falloc_update_inode(struct inode *inode,
				int mode, loff_t new_size, int update_ctime)
{
	struct timespec now;

	if (update_ctime) {
		now = current_fs_time(inode->i_sb);
		if (!timespec_equal(&inode->i_ctime, &now))
			inode->i_ctime = now;
	}
	/*
	 * Update only when preallocation was requested beyond
	 * the file size.
	 */
3616 3617 3618 3619 3620
	if (!(mode & FALLOC_FL_KEEP_SIZE)) {
		if (new_size > i_size_read(inode))
			i_size_write(inode, new_size);
		if (new_size > EXT4_I(inode)->i_disksize)
			ext4_update_i_disksize(inode, new_size);
3621 3622 3623 3624 3625 3626
	} else {
		/*
		 * Mark that we allocate beyond EOF so the subsequent truncate
		 * can proceed even if the new size is the same as i_size.
		 */
		if (new_size > i_size_read(inode))
3627
			ext4_set_inode_flag(inode, EXT4_INODE_EOFBLOCKS);
3628 3629 3630 3631
	}

}

A
Amit Arora 已提交
3632
/*
3633
 * preallocate space for a file. This implements ext4's fallocate file
A
Amit Arora 已提交
3634 3635 3636 3637 3638
 * 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).
 */
3639
long ext4_fallocate(struct file *file, int mode, loff_t offset, loff_t len)
A
Amit Arora 已提交
3640
{
3641
	struct inode *inode = file->f_path.dentry->d_inode;
A
Amit Arora 已提交
3642
	handle_t *handle;
3643
	loff_t new_size;
3644
	unsigned int max_blocks;
A
Amit Arora 已提交
3645 3646 3647
	int ret = 0;
	int ret2 = 0;
	int retries = 0;
3648
	struct ext4_map_blocks map;
A
Amit Arora 已提交
3649 3650
	unsigned int credits, blkbits = inode->i_blkbits;

3651
	/* We only support the FALLOC_FL_KEEP_SIZE mode */
3652
	if (mode & ~FALLOC_FL_KEEP_SIZE)
3653 3654
		return -EOPNOTSUPP;

A
Amit Arora 已提交
3655 3656 3657 3658
	/*
	 * currently supporting (pre)allocate mode for extent-based
	 * files _only_
	 */
3659
	if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)))
A
Amit Arora 已提交
3660 3661
		return -EOPNOTSUPP;

3662
	trace_ext4_fallocate_enter(inode, offset, len, mode);
3663
	map.m_lblk = offset >> blkbits;
3664 3665 3666 3667
	/*
	 * We can't just convert len to max_blocks because
	 * If blocksize = 4096 offset = 3072 and len = 2048
	 */
A
Amit Arora 已提交
3668
	max_blocks = (EXT4_BLOCK_ALIGN(len + offset, blkbits) >> blkbits)
3669
		- map.m_lblk;
A
Amit Arora 已提交
3670
	/*
3671
	 * credits to insert 1 extent into extent tree
A
Amit Arora 已提交
3672
	 */
3673
	credits = ext4_chunk_trans_blocks(inode, max_blocks);
3674
	mutex_lock(&inode->i_mutex);
3675 3676 3677
	ret = inode_newsize_ok(inode, (len + offset));
	if (ret) {
		mutex_unlock(&inode->i_mutex);
3678
		trace_ext4_fallocate_exit(inode, offset, max_blocks, ret);
3679 3680
		return ret;
	}
A
Amit Arora 已提交
3681 3682
retry:
	while (ret >= 0 && ret < max_blocks) {
3683 3684
		map.m_lblk = map.m_lblk + ret;
		map.m_len = max_blocks = max_blocks - ret;
A
Amit Arora 已提交
3685 3686 3687 3688 3689
		handle = ext4_journal_start(inode, credits);
		if (IS_ERR(handle)) {
			ret = PTR_ERR(handle);
			break;
		}
3690
		ret = ext4_map_blocks(handle, inode, &map,
3691
				      EXT4_GET_BLOCKS_CREATE_UNINIT_EXT);
3692
		if (ret <= 0) {
3693 3694
#ifdef EXT4FS_DEBUG
			WARN_ON(ret <= 0);
3695
			printk(KERN_ERR "%s: ext4_ext_map_blocks "
3696
				    "returned error inode#%lu, block=%u, "
3697
				    "max_blocks=%u", __func__,
3698
				    inode->i_ino, map.m_lblk, max_blocks);
3699
#endif
A
Amit Arora 已提交
3700 3701 3702 3703
			ext4_mark_inode_dirty(handle, inode);
			ret2 = ext4_journal_stop(handle);
			break;
		}
3704
		if ((map.m_lblk + ret) >= (EXT4_BLOCK_ALIGN(offset + len,
3705 3706 3707
						blkbits) >> blkbits))
			new_size = offset + len;
		else
3708
			new_size = (map.m_lblk + ret) << blkbits;
A
Amit Arora 已提交
3709

3710
		ext4_falloc_update_inode(inode, mode, new_size,
3711
					 (map.m_flags & EXT4_MAP_NEW));
A
Amit Arora 已提交
3712 3713 3714 3715 3716
		ext4_mark_inode_dirty(handle, inode);
		ret2 = ext4_journal_stop(handle);
		if (ret2)
			break;
	}
3717 3718 3719
	if (ret == -ENOSPC &&
			ext4_should_retry_alloc(inode->i_sb, &retries)) {
		ret = 0;
A
Amit Arora 已提交
3720 3721
		goto retry;
	}
3722
	mutex_unlock(&inode->i_mutex);
3723 3724
	trace_ext4_fallocate_exit(inode, offset, max_blocks,
				ret > 0 ? ret2 : ret);
A
Amit Arora 已提交
3725 3726
	return ret > 0 ? ret2 : ret;
}
3727

3728 3729 3730 3731 3732 3733 3734 3735
/*
 * 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.
3736
 * Returns 0 on success.
3737 3738
 */
int ext4_convert_unwritten_extents(struct inode *inode, loff_t offset,
3739
				    ssize_t len)
3740 3741 3742 3743 3744
{
	handle_t *handle;
	unsigned int max_blocks;
	int ret = 0;
	int ret2 = 0;
3745
	struct ext4_map_blocks map;
3746 3747
	unsigned int credits, blkbits = inode->i_blkbits;

3748
	map.m_lblk = offset >> blkbits;
3749 3750 3751 3752
	/*
	 * We can't just convert len to max_blocks because
	 * If blocksize = 4096 offset = 3072 and len = 2048
	 */
3753 3754
	max_blocks = ((EXT4_BLOCK_ALIGN(len + offset, blkbits) >> blkbits) -
		      map.m_lblk);
3755 3756 3757 3758 3759
	/*
	 * credits to insert 1 extent into extent tree
	 */
	credits = ext4_chunk_trans_blocks(inode, max_blocks);
	while (ret >= 0 && ret < max_blocks) {
3760 3761
		map.m_lblk += ret;
		map.m_len = (max_blocks -= ret);
3762 3763 3764 3765 3766
		handle = ext4_journal_start(inode, credits);
		if (IS_ERR(handle)) {
			ret = PTR_ERR(handle);
			break;
		}
3767
		ret = ext4_map_blocks(handle, inode, &map,
3768
				      EXT4_GET_BLOCKS_IO_CONVERT_EXT);
3769 3770
		if (ret <= 0) {
			WARN_ON(ret <= 0);
3771
			printk(KERN_ERR "%s: ext4_ext_map_blocks "
3772 3773
				    "returned error inode#%lu, block=%u, "
				    "max_blocks=%u", __func__,
3774
				    inode->i_ino, map.m_lblk, map.m_len);
3775 3776 3777 3778 3779 3780 3781 3782
		}
		ext4_mark_inode_dirty(handle, inode);
		ret2 = ext4_journal_stop(handle);
		if (ret <= 0 || ret2 )
			break;
	}
	return ret > 0 ? ret2 : ret;
}
3783

3784 3785 3786
/*
 * Callback function called for each extent to gather FIEMAP information.
 */
A
Aneesh Kumar K.V 已提交
3787
static int ext4_ext_fiemap_cb(struct inode *inode, struct ext4_ext_path *path,
3788 3789 3790 3791 3792 3793
		       struct ext4_ext_cache *newex, struct ext4_extent *ex,
		       void *data)
{
	__u64	logical;
	__u64	physical;
	__u64	length;
3794
	loff_t	size;
3795
	__u32	flags = 0;
3796 3797 3798
	int		ret = 0;
	struct fiemap_extent_info *fieinfo = data;
	unsigned char blksize_bits;
3799

3800 3801
	blksize_bits = inode->i_sb->s_blocksize_bits;
	logical = (__u64)newex->ec_block << blksize_bits;
3802

3803
	if (newex->ec_start == 0) {
3804 3805 3806 3807 3808 3809 3810 3811 3812 3813 3814 3815 3816 3817 3818 3819 3820 3821
		/*
		 * No extent in extent-tree contains block @newex->ec_start,
		 * then the block may stay in 1)a hole or 2)delayed-extent.
		 *
		 * Holes or delayed-extents are processed as follows.
		 * 1. lookup dirty pages with specified range in pagecache.
		 *    If no page is got, then there is no delayed-extent and
		 *    return with EXT_CONTINUE.
		 * 2. find the 1st mapped buffer,
		 * 3. check if the mapped buffer is both in the request range
		 *    and a delayed buffer. If not, there is no delayed-extent,
		 *    then return.
		 * 4. a delayed-extent is found, the extent will be collected.
		 */
		ext4_lblk_t	end = 0;
		pgoff_t		last_offset;
		pgoff_t		offset;
		pgoff_t		index;
3822
		pgoff_t		start_index = 0;
3823
		struct page	**pages = NULL;
3824
		struct buffer_head *bh = NULL;
3825 3826 3827 3828 3829 3830
		struct buffer_head *head = NULL;
		unsigned int nr_pages = PAGE_SIZE / sizeof(struct page *);

		pages = kmalloc(PAGE_SIZE, GFP_KERNEL);
		if (pages == NULL)
			return -ENOMEM;
3831 3832

		offset = logical >> PAGE_SHIFT;
3833 3834 3835 3836 3837 3838 3839 3840 3841 3842 3843 3844 3845 3846 3847 3848
repeat:
		last_offset = offset;
		head = NULL;
		ret = find_get_pages_tag(inode->i_mapping, &offset,
					PAGECACHE_TAG_DIRTY, nr_pages, pages);

		if (!(flags & FIEMAP_EXTENT_DELALLOC)) {
			/* First time, try to find a mapped buffer. */
			if (ret == 0) {
out:
				for (index = 0; index < ret; index++)
					page_cache_release(pages[index]);
				/* just a hole. */
				kfree(pages);
				return EXT_CONTINUE;
			}
3849
			index = 0;
3850

3851
next_page:
3852
			/* Try to find the 1st mapped buffer. */
3853
			end = ((__u64)pages[index]->index << PAGE_SHIFT) >>
3854
				  blksize_bits;
3855
			if (!page_has_buffers(pages[index]))
3856
				goto out;
3857
			head = page_buffers(pages[index]);
3858 3859
			if (!head)
				goto out;
3860

3861
			index++;
3862 3863
			bh = head;
			do {
3864 3865 3866 3867 3868 3869 3870 3871 3872 3873
				if (end >= newex->ec_block +
					newex->ec_len)
					/* The buffer is out of
					 * the request range.
					 */
					goto out;

				if (buffer_mapped(bh) &&
				    end >= newex->ec_block) {
					start_index = index - 1;
3874 3875 3876
					/* get the 1st mapped buffer. */
					goto found_mapped_buffer;
				}
3877

3878 3879 3880
				bh = bh->b_this_page;
				end++;
			} while (bh != head);
3881

3882 3883 3884 3885 3886 3887 3888 3889 3890 3891 3892
			/* No mapped buffer in the range found in this page,
			 * We need to look up next page.
			 */
			if (index >= ret) {
				/* There is no page left, but we need to limit
				 * newex->ec_len.
				 */
				newex->ec_len = end - newex->ec_block;
				goto out;
			}
			goto next_page;
3893
		} else {
3894 3895 3896 3897
			/*Find contiguous delayed buffers. */
			if (ret > 0 && pages[0]->index == last_offset)
				head = page_buffers(pages[0]);
			bh = head;
3898 3899
			index = 1;
			start_index = 0;
3900
		}
3901 3902 3903 3904 3905 3906 3907 3908 3909 3910 3911 3912 3913 3914 3915 3916 3917 3918 3919 3920 3921

found_mapped_buffer:
		if (bh != NULL && buffer_delay(bh)) {
			/* 1st or contiguous delayed buffer found. */
			if (!(flags & FIEMAP_EXTENT_DELALLOC)) {
				/*
				 * 1st delayed buffer found, record
				 * the start of extent.
				 */
				flags |= FIEMAP_EXTENT_DELALLOC;
				newex->ec_block = end;
				logical = (__u64)end << blksize_bits;
			}
			/* Find contiguous delayed buffers. */
			do {
				if (!buffer_delay(bh))
					goto found_delayed_extent;
				bh = bh->b_this_page;
				end++;
			} while (bh != head);

3922
			for (; index < ret; index++) {
3923 3924 3925 3926 3927 3928 3929 3930 3931
				if (!page_has_buffers(pages[index])) {
					bh = NULL;
					break;
				}
				head = page_buffers(pages[index]);
				if (!head) {
					bh = NULL;
					break;
				}
3932

3933
				if (pages[index]->index !=
3934 3935
				    pages[start_index]->index + index
				    - start_index) {
3936 3937 3938 3939 3940 3941 3942 3943 3944 3945 3946 3947 3948 3949 3950 3951 3952 3953 3954 3955 3956 3957 3958 3959 3960 3961 3962
					/* Blocks are not contiguous. */
					bh = NULL;
					break;
				}
				bh = head;
				do {
					if (!buffer_delay(bh))
						/* Delayed-extent ends. */
						goto found_delayed_extent;
					bh = bh->b_this_page;
					end++;
				} while (bh != head);
			}
		} else if (!(flags & FIEMAP_EXTENT_DELALLOC))
			/* a hole found. */
			goto out;

found_delayed_extent:
		newex->ec_len = min(end - newex->ec_block,
						(ext4_lblk_t)EXT_INIT_MAX_LEN);
		if (ret == nr_pages && bh != NULL &&
			newex->ec_len < EXT_INIT_MAX_LEN &&
			buffer_delay(bh)) {
			/* Have not collected an extent and continue. */
			for (index = 0; index < ret; index++)
				page_cache_release(pages[index]);
			goto repeat;
3963
		}
3964 3965 3966 3967

		for (index = 0; index < ret; index++)
			page_cache_release(pages[index]);
		kfree(pages);
3968 3969 3970 3971 3972 3973 3974 3975
	}

	physical = (__u64)newex->ec_start << blksize_bits;
	length =   (__u64)newex->ec_len << blksize_bits;

	if (ex && ext4_ext_is_uninitialized(ex))
		flags |= FIEMAP_EXTENT_UNWRITTEN;

3976 3977
	size = i_size_read(inode);
	if (logical + length >= size)
3978 3979
		flags |= FIEMAP_EXTENT_LAST;

3980
	ret = fiemap_fill_next_extent(fieinfo, logical, physical,
3981
					length, flags);
3982 3983 3984
	if (ret < 0)
		return ret;
	if (ret == 1)
3985 3986 3987 3988 3989 3990 3991
		return EXT_BREAK;
	return EXT_CONTINUE;
}

/* fiemap flags we can handle specified here */
#define EXT4_FIEMAP_FLAGS	(FIEMAP_FLAG_SYNC|FIEMAP_FLAG_XATTR)

A
Aneesh Kumar K.V 已提交
3992 3993
static int ext4_xattr_fiemap(struct inode *inode,
				struct fiemap_extent_info *fieinfo)
3994 3995 3996 3997 3998 3999 4000 4001
{
	__u64 physical = 0;
	__u64 length;
	__u32 flags = FIEMAP_EXTENT_LAST;
	int blockbits = inode->i_sb->s_blocksize_bits;
	int error = 0;

	/* in-inode? */
4002
	if (ext4_test_inode_state(inode, EXT4_STATE_XATTR)) {
4003 4004 4005 4006 4007 4008 4009 4010 4011 4012 4013 4014
		struct ext4_iloc iloc;
		int offset;	/* offset of xattr in inode */

		error = ext4_get_inode_loc(inode, &iloc);
		if (error)
			return error;
		physical = iloc.bh->b_blocknr << blockbits;
		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;
4015
		brelse(iloc.bh);
4016 4017 4018 4019 4020 4021 4022 4023 4024 4025 4026 4027 4028 4029 4030 4031 4032 4033
	} else { /* external block */
		physical = EXT4_I(inode)->i_file_acl << blockbits;
		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;

	/* fallback to generic here if not in extents fmt */
4034
	if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)))
4035 4036 4037 4038 4039 4040 4041 4042 4043
		return generic_block_fiemap(inode, fieinfo, start, len,
			ext4_get_block);

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

	if (fieinfo->fi_flags & FIEMAP_FLAG_XATTR) {
		error = ext4_xattr_fiemap(inode, fieinfo);
	} else {
4044 4045 4046
		ext4_lblk_t len_blks;
		__u64 last_blk;

4047
		start_blk = start >> inode->i_sb->s_blocksize_bits;
4048 4049 4050 4051
		last_blk = (start + len - 1) >> inode->i_sb->s_blocksize_bits;
		if (last_blk >= EXT_MAX_BLOCK)
			last_blk = EXT_MAX_BLOCK-1;
		len_blks = ((ext4_lblk_t) last_blk) - start_blk + 1;
4052 4053 4054 4055 4056 4057 4058 4059 4060 4061 4062

		/*
		 * Walk the extent tree gathering extent information.
		 * ext4_ext_fiemap_cb will push extents back to user.
		 */
		error = ext4_ext_walk_space(inode, start_blk, len_blks,
					  ext4_ext_fiemap_cb, fieinfo);
	}

	return error;
}