move_extent.c 40.9 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
/*
 * Copyright (c) 2008,2009 NEC Software Tohoku, Ltd.
 * Written by Takashi Sato <t-sato@yk.jp.nec.com>
 *            Akira Fujita <a-fujita@rs.jp.nec.com>
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of version 2.1 of the GNU Lesser General Public License
 * 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.
 */

#include <linux/fs.h>
#include <linux/quotaops.h>
18
#include <linux/slab.h>
19 20 21 22
#include "ext4_jbd2.h"
#include "ext4_extents.h"
#include "ext4.h"

23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
/**
 * get_ext_path - Find an extent path for designated logical block number.
 *
 * @inode:	an inode which is searched
 * @lblock:	logical block number to find an extent path
 * @path:	pointer to an extent path pointer (for output)
 *
 * ext4_ext_find_extent wrapper. Return 0 on success, or a negative error value
 * on failure.
 */
static inline int
get_ext_path(struct inode *inode, ext4_lblk_t lblock,
		struct ext4_ext_path **path)
{
	int ret = 0;

	*path = ext4_ext_find_extent(inode, lblock, *path);
	if (IS_ERR(*path)) {
		ret = PTR_ERR(*path);
		*path = NULL;
43 44 45
	} else if ((*path)[ext_depth(inode)].p_ext == NULL)
		ret = -ENODATA;

46 47
	return ret;
}
48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80

/**
 * copy_extent_status - Copy the extent's initialization status
 *
 * @src:	an extent for getting initialize status
 * @dest:	an extent to be set the status
 */
static void
copy_extent_status(struct ext4_extent *src, struct ext4_extent *dest)
{
	if (ext4_ext_is_uninitialized(src))
		ext4_ext_mark_uninitialized(dest);
	else
		dest->ee_len = cpu_to_le16(ext4_ext_get_actual_len(dest));
}

/**
 * mext_next_extent - Search for the next extent and set it to "extent"
 *
 * @inode:	inode which is searched
 * @path:	this will obtain data for the next extent
 * @extent:	pointer to the next extent we have just gotten
 *
 * Search the next extent in the array of ext4_ext_path structure (@path)
 * and set it to ext4_extent structure (@extent). In addition, the member of
 * @path (->p_ext) also points the next extent. Return 0 on success, 1 if
 * ext4_ext_path structure refers to the last extent, or a negative error
 * value on failure.
 */
static int
mext_next_extent(struct inode *inode, struct ext4_ext_path *path,
		      struct ext4_extent **extent)
{
81
	struct ext4_extent_header *eh;
82 83 84 85 86 87
	int ppos, leaf_ppos = path->p_depth;

	ppos = leaf_ppos;
	if (EXT_LAST_EXTENT(path[ppos].p_hdr) > path[ppos].p_ext) {
		/* leaf block */
		*extent = ++path[ppos].p_ext;
88
		path[ppos].p_block = ext4_ext_pblock(path[ppos].p_ext);
89 90 91 92 93 94 95 96 97 98
		return 0;
	}

	while (--ppos >= 0) {
		if (EXT_LAST_INDEX(path[ppos].p_hdr) >
		    path[ppos].p_idx) {
			int cur_ppos = ppos;

			/* index block */
			path[ppos].p_idx++;
99
			path[ppos].p_block = ext4_idx_pblock(path[ppos].p_idx);
100 101 102 103 104 105 106 107 108 109 110 111 112 113
			if (path[ppos+1].p_bh)
				brelse(path[ppos+1].p_bh);
			path[ppos+1].p_bh =
				sb_bread(inode->i_sb, path[ppos].p_block);
			if (!path[ppos+1].p_bh)
				return -EIO;
			path[ppos+1].p_hdr =
				ext_block_hdr(path[ppos+1].p_bh);

			/* Halfway index block */
			while (++cur_ppos < leaf_ppos) {
				path[cur_ppos].p_idx =
					EXT_FIRST_INDEX(path[cur_ppos].p_hdr);
				path[cur_ppos].p_block =
114
					ext4_idx_pblock(path[cur_ppos].p_idx);
115 116 117 118 119 120 121 122 123 124
				if (path[cur_ppos+1].p_bh)
					brelse(path[cur_ppos+1].p_bh);
				path[cur_ppos+1].p_bh = sb_bread(inode->i_sb,
					path[cur_ppos].p_block);
				if (!path[cur_ppos+1].p_bh)
					return -EIO;
				path[cur_ppos+1].p_hdr =
					ext_block_hdr(path[cur_ppos+1].p_bh);
			}

125 126 127 128 129 130 131
			path[leaf_ppos].p_ext = *extent = NULL;

			eh = path[leaf_ppos].p_hdr;
			if (le16_to_cpu(eh->eh_entries) == 0)
				/* empty leaf is found */
				return -ENODATA;

132 133 134
			/* leaf block */
			path[leaf_ppos].p_ext = *extent =
				EXT_FIRST_EXTENT(path[leaf_ppos].p_hdr);
135
			path[leaf_ppos].p_block =
136
					ext4_ext_pblock(path[leaf_ppos].p_ext);
137 138 139 140 141 142 143
			return 0;
		}
	}
	/* We found the last extent */
	return 1;
}

144 145 146 147 148 149 150
/**
 * mext_check_null_inode - NULL check for two inodes
 *
 * If inode1 or inode2 is NULL, return -EIO. Otherwise, return 0.
 */
static int
mext_check_null_inode(struct inode *inode1, struct inode *inode2,
151
		      const char *function, unsigned int line)
152 153 154 155
{
	int ret = 0;

	if (inode1 == NULL) {
156
		__ext4_error(inode2->i_sb, function, line,
157 158 159 160
			"Both inodes should not be NULL: "
			"inode1 NULL inode2 %lu", inode2->i_ino);
		ret = -EIO;
	} else if (inode2 == NULL) {
161
		__ext4_error(inode1->i_sb, function, line,
162 163 164 165 166 167 168
			"Both inodes should not be NULL: "
			"inode1 %lu inode2 NULL", inode1->i_ino);
		ret = -EIO;
	}
	return ret;
}

169
/**
170
 * double_down_write_data_sem - Acquire two inodes' write lock of i_data_sem
171 172 173
 *
 * @orig_inode:		original inode structure
 * @donor_inode:	donor inode structure
174 175
 * Acquire write lock of i_data_sem of the two inodes (orig and donor) by
 * i_ino order.
176 177
 */
static void
178
double_down_write_data_sem(struct inode *orig_inode, struct inode *donor_inode)
179 180 181 182 183 184 185 186 187 188 189 190 191 192
{
	struct inode *first = orig_inode, *second = donor_inode;

	/*
	 * Use the inode number to provide the stable locking order instead
	 * of its address, because the C language doesn't guarantee you can
	 * compare pointers that don't come from the same array.
	 */
	if (donor_inode->i_ino < orig_inode->i_ino) {
		first = donor_inode;
		second = orig_inode;
	}

	down_write(&EXT4_I(first)->i_data_sem);
193
	down_write_nested(&EXT4_I(second)->i_data_sem, SINGLE_DEPTH_NESTING);
194 195 196
}

/**
197
 * double_up_write_data_sem - Release two inodes' write lock of i_data_sem
198 199 200
 *
 * @orig_inode:		original inode structure to be released its lock first
 * @donor_inode:	donor inode structure to be released its lock second
201
 * Release write lock of i_data_sem of two inodes (orig and donor).
202 203
 */
static void
204
double_up_write_data_sem(struct inode *orig_inode, struct inode *donor_inode)
205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251
{
	up_write(&EXT4_I(orig_inode)->i_data_sem);
	up_write(&EXT4_I(donor_inode)->i_data_sem);
}

/**
 * mext_insert_across_blocks - Insert extents across leaf block
 *
 * @handle:		journal handle
 * @orig_inode:		original inode
 * @o_start:		first original extent to be changed
 * @o_end:		last original extent to be changed
 * @start_ext:		first new extent to be inserted
 * @new_ext:		middle of new extent to be inserted
 * @end_ext:		last new extent to be inserted
 *
 * Allocate a new leaf block and insert extents into it. Return 0 on success,
 * or a negative error value on failure.
 */
static int
mext_insert_across_blocks(handle_t *handle, struct inode *orig_inode,
		struct ext4_extent *o_start, struct ext4_extent *o_end,
		struct ext4_extent *start_ext, struct ext4_extent *new_ext,
		struct ext4_extent *end_ext)
{
	struct ext4_ext_path *orig_path = NULL;
	ext4_lblk_t eblock = 0;
	int new_flag = 0;
	int end_flag = 0;
	int err = 0;

	if (start_ext->ee_len && new_ext->ee_len && end_ext->ee_len) {
		if (o_start == o_end) {

			/*       start_ext   new_ext    end_ext
			 * donor |---------|-----------|--------|
			 * orig  |------------------------------|
			 */
			end_flag = 1;
		} else {

			/*       start_ext   new_ext   end_ext
			 * donor |---------|----------|---------|
			 * orig  |---------------|--------------|
			 */
			o_end->ee_block = end_ext->ee_block;
			o_end->ee_len = end_ext->ee_len;
252
			ext4_ext_store_pblock(o_end, ext4_ext_pblock(end_ext));
253 254 255
		}

		o_start->ee_len = start_ext->ee_len;
256
		eblock = le32_to_cpu(start_ext->ee_block);
257 258 259 260 261 262 263 264 265 266
		new_flag = 1;

	} else if (start_ext->ee_len && new_ext->ee_len &&
		   !end_ext->ee_len && o_start == o_end) {

		/*	 start_ext	new_ext
		 * donor |--------------|---------------|
		 * orig  |------------------------------|
		 */
		o_start->ee_len = start_ext->ee_len;
267
		eblock = le32_to_cpu(start_ext->ee_block);
268 269 270 271 272 273 274 275 276 277 278
		new_flag = 1;

	} else if (!start_ext->ee_len && new_ext->ee_len &&
		   end_ext->ee_len && o_start == o_end) {

		/*	  new_ext	end_ext
		 * donor |--------------|---------------|
		 * orig  |------------------------------|
		 */
		o_end->ee_block = end_ext->ee_block;
		o_end->ee_len = end_ext->ee_len;
279
		ext4_ext_store_pblock(o_end, ext4_ext_pblock(end_ext));
280 281 282 283 284 285 286 287 288 289 290 291 292 293 294

		/*
		 * Set 0 to the extent block if new_ext was
		 * the first block.
		 */
		if (new_ext->ee_block)
			eblock = le32_to_cpu(new_ext->ee_block);

		new_flag = 1;
	} else {
		ext4_debug("ext4 move extent: Unexpected insert case\n");
		return -EIO;
	}

	if (new_flag) {
295
		err = get_ext_path(orig_inode, eblock, &orig_path);
296
		if (err)
297 298 299
			goto out;

		if (ext4_ext_insert_extent(handle, orig_inode,
300
					orig_path, new_ext, 0))
301 302 303 304
			goto out;
	}

	if (end_flag) {
305 306
		err = get_ext_path(orig_inode,
				le32_to_cpu(end_ext->ee_block) - 1, &orig_path);
307
		if (err)
308 309 310
			goto out;

		if (ext4_ext_insert_extent(handle, orig_inode,
311
					   orig_path, end_ext, 0))
312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363
			goto out;
	}
out:
	if (orig_path) {
		ext4_ext_drop_refs(orig_path);
		kfree(orig_path);
	}

	return err;

}

/**
 * mext_insert_inside_block - Insert new extent to the extent block
 *
 * @o_start:		first original extent to be moved
 * @o_end:		last original extent to be moved
 * @start_ext:		first new extent to be inserted
 * @new_ext:		middle of new extent to be inserted
 * @end_ext:		last new extent to be inserted
 * @eh:			extent header of target leaf block
 * @range_to_move:	used to decide how to insert extent
 *
 * Insert extents into the leaf block. The extent (@o_start) is overwritten
 * by inserted extents.
 */
static void
mext_insert_inside_block(struct ext4_extent *o_start,
			      struct ext4_extent *o_end,
			      struct ext4_extent *start_ext,
			      struct ext4_extent *new_ext,
			      struct ext4_extent *end_ext,
			      struct ext4_extent_header *eh,
			      int range_to_move)
{
	int i = 0;
	unsigned long len;

	/* Move the existing extents */
	if (range_to_move && o_end < EXT_LAST_EXTENT(eh)) {
		len = (unsigned long)(EXT_LAST_EXTENT(eh) + 1) -
			(unsigned long)(o_end + 1);
		memmove(o_end + 1 + range_to_move, o_end + 1, len);
	}

	/* Insert start entry */
	if (start_ext->ee_len)
		o_start[i++].ee_len = start_ext->ee_len;

	/* Insert new entry */
	if (new_ext->ee_len) {
		o_start[i] = *new_ext;
364
		ext4_ext_store_pblock(&o_start[i++], ext4_ext_pblock(new_ext));
365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 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 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484
	}

	/* Insert end entry */
	if (end_ext->ee_len)
		o_start[i] = *end_ext;

	/* Increment the total entries counter on the extent block */
	le16_add_cpu(&eh->eh_entries, range_to_move);
}

/**
 * mext_insert_extents - Insert new extent
 *
 * @handle:	journal handle
 * @orig_inode:	original inode
 * @orig_path:	path indicates first extent to be changed
 * @o_start:	first original extent to be changed
 * @o_end:	last original extent to be changed
 * @start_ext:	first new extent to be inserted
 * @new_ext:	middle of new extent to be inserted
 * @end_ext:	last new extent to be inserted
 *
 * Call the function to insert extents. If we cannot add more extents into
 * the leaf block, we call mext_insert_across_blocks() to create a
 * new leaf block. Otherwise call mext_insert_inside_block(). Return 0
 * on success, or a negative error value on failure.
 */
static int
mext_insert_extents(handle_t *handle, struct inode *orig_inode,
			 struct ext4_ext_path *orig_path,
			 struct ext4_extent *o_start,
			 struct ext4_extent *o_end,
			 struct ext4_extent *start_ext,
			 struct ext4_extent *new_ext,
			 struct ext4_extent *end_ext)
{
	struct  ext4_extent_header *eh;
	unsigned long need_slots, slots_range;
	int	range_to_move, depth, ret;

	/*
	 * The extents need to be inserted
	 * start_extent + new_extent + end_extent.
	 */
	need_slots = (start_ext->ee_len ? 1 : 0) + (end_ext->ee_len ? 1 : 0) +
		(new_ext->ee_len ? 1 : 0);

	/* The number of slots between start and end */
	slots_range = ((unsigned long)(o_end + 1) - (unsigned long)o_start + 1)
		/ sizeof(struct ext4_extent);

	/* Range to move the end of extent */
	range_to_move = need_slots - slots_range;
	depth = orig_path->p_depth;
	orig_path += depth;
	eh = orig_path->p_hdr;

	if (depth) {
		/* Register to journal */
		ret = ext4_journal_get_write_access(handle, orig_path->p_bh);
		if (ret)
			return ret;
	}

	/* Expansion */
	if (range_to_move > 0 &&
		(range_to_move > le16_to_cpu(eh->eh_max)
			- le16_to_cpu(eh->eh_entries))) {

		ret = mext_insert_across_blocks(handle, orig_inode, o_start,
					o_end, start_ext, new_ext, end_ext);
		if (ret < 0)
			return ret;
	} else
		mext_insert_inside_block(o_start, o_end, start_ext, new_ext,
						end_ext, eh, range_to_move);

	if (depth) {
		ret = ext4_handle_dirty_metadata(handle, orig_inode,
						 orig_path->p_bh);
		if (ret)
			return ret;
	} else {
		ret = ext4_mark_inode_dirty(handle, orig_inode);
		if (ret < 0)
			return ret;
	}

	return 0;
}

/**
 * mext_leaf_block - Move one leaf extent block into the inode.
 *
 * @handle:		journal handle
 * @orig_inode:		original inode
 * @orig_path:		path indicates first extent to be changed
 * @dext:		donor extent
 * @from:		start offset on the target file
 *
 * In order to insert extents into the leaf block, we must divide the extent
 * in the leaf block into three extents. The one is located to be inserted
 * extents, and the others are located around it.
 *
 * Therefore, this function creates structures to save extents of the leaf
 * block, and inserts extents by calling mext_insert_extents() with
 * created extents. Return 0 on success, or a negative error value on failure.
 */
static int
mext_leaf_block(handle_t *handle, struct inode *orig_inode,
		     struct ext4_ext_path *orig_path, struct ext4_extent *dext,
		     ext4_lblk_t *from)
{
	struct ext4_extent *oext, *o_start, *o_end, *prev_ext;
	struct ext4_extent new_ext, start_ext, end_ext;
	ext4_lblk_t new_ext_end;
	int oext_alen, new_ext_alen, end_ext_alen;
	int depth = ext_depth(orig_inode);
	int ret;

485
	start_ext.ee_block = end_ext.ee_block = 0;
486 487 488 489 490
	o_start = o_end = oext = orig_path[depth].p_ext;
	oext_alen = ext4_ext_get_actual_len(oext);
	start_ext.ee_len = end_ext.ee_len = 0;

	new_ext.ee_block = cpu_to_le32(*from);
491
	ext4_ext_store_pblock(&new_ext, ext4_ext_pblock(dext));
492 493 494 495 496 497 498 499 500 501 502 503 504 505 506
	new_ext.ee_len = dext->ee_len;
	new_ext_alen = ext4_ext_get_actual_len(&new_ext);
	new_ext_end = le32_to_cpu(new_ext.ee_block) + new_ext_alen - 1;

	/*
	 * Case: original extent is first
	 * oext      |--------|
	 * new_ext      |--|
	 * start_ext |--|
	 */
	if (le32_to_cpu(oext->ee_block) < le32_to_cpu(new_ext.ee_block) &&
		le32_to_cpu(new_ext.ee_block) <
		le32_to_cpu(oext->ee_block) + oext_alen) {
		start_ext.ee_len = cpu_to_le16(le32_to_cpu(new_ext.ee_block) -
					       le32_to_cpu(oext->ee_block));
507
		start_ext.ee_block = oext->ee_block;
508 509 510 511 512 513 514 515 516 517 518 519 520
		copy_extent_status(oext, &start_ext);
	} else if (oext > EXT_FIRST_EXTENT(orig_path[depth].p_hdr)) {
		prev_ext = oext - 1;
		/*
		 * We can merge new_ext into previous extent,
		 * if these are contiguous and same extent type.
		 */
		if (ext4_can_extents_be_merged(orig_inode, prev_ext,
					       &new_ext)) {
			o_start = prev_ext;
			start_ext.ee_len = cpu_to_le16(
				ext4_ext_get_actual_len(prev_ext) +
				new_ext_alen);
521
			start_ext.ee_block = oext->ee_block;
522 523 524 525 526 527 528 529 530 531
			copy_extent_status(prev_ext, &start_ext);
			new_ext.ee_len = 0;
		}
	}

	/*
	 * Case: new_ext_end must be less than oext
	 * oext      |-----------|
	 * new_ext       |-------|
	 */
532
	if (le32_to_cpu(oext->ee_block) + oext_alen - 1 < new_ext_end) {
533
		EXT4_ERROR_INODE(orig_inode,
534 535 536 537 538 539 540
			"new_ext_end(%u) should be less than or equal to "
			"oext->ee_block(%u) + oext_alen(%d) - 1",
			new_ext_end, le32_to_cpu(oext->ee_block),
			oext_alen);
		ret = -EIO;
		goto out;
	}
541 542 543 544 545 546 547 548 549 550 551 552 553 554 555

	/*
	 * Case: new_ext is smaller than original extent
	 * oext    |---------------|
	 * new_ext |-----------|
	 * end_ext             |---|
	 */
	if (le32_to_cpu(oext->ee_block) <= new_ext_end &&
		new_ext_end < le32_to_cpu(oext->ee_block) + oext_alen - 1) {
		end_ext.ee_len =
			cpu_to_le16(le32_to_cpu(oext->ee_block) +
			oext_alen - 1 - new_ext_end);
		copy_extent_status(oext, &end_ext);
		end_ext_alen = ext4_ext_get_actual_len(&end_ext);
		ext4_ext_store_pblock(&end_ext,
556
			(ext4_ext_pblock(o_end) + oext_alen - end_ext_alen));
557 558 559 560 561 562 563
		end_ext.ee_block =
			cpu_to_le32(le32_to_cpu(o_end->ee_block) +
			oext_alen - end_ext_alen);
	}

	ret = mext_insert_extents(handle, orig_inode, orig_path, o_start,
				o_end, &start_ext, &new_ext, &end_ext);
564
out:
565 566 567 568 569 570 571 572 573 574
	return ret;
}

/**
 * mext_calc_swap_extents - Calculate extents for extent swapping.
 *
 * @tmp_dext:		the extent that will belong to the original inode
 * @tmp_oext:		the extent that will belong to the donor inode
 * @orig_off:		block offset of original inode
 * @donor_off:		block offset of donor inode
575
 * @max_count:		the maximum length of extents
576 577
 *
 * Return 0 on success, or a negative error value on failure.
578
 */
579
static int
580 581 582 583 584 585 586 587
mext_calc_swap_extents(struct ext4_extent *tmp_dext,
			      struct ext4_extent *tmp_oext,
			      ext4_lblk_t orig_off, ext4_lblk_t donor_off,
			      ext4_lblk_t max_count)
{
	ext4_lblk_t diff, orig_diff;
	struct ext4_extent dext_old, oext_old;

588 589 590 591 592 593 594 595 596 597 598 599 600
	BUG_ON(orig_off != donor_off);

	/* original and donor extents have to cover the same block offset */
	if (orig_off < le32_to_cpu(tmp_oext->ee_block) ||
	    le32_to_cpu(tmp_oext->ee_block) +
			ext4_ext_get_actual_len(tmp_oext) - 1 < orig_off)
		return -ENODATA;

	if (orig_off < le32_to_cpu(tmp_dext->ee_block) ||
	    le32_to_cpu(tmp_dext->ee_block) +
			ext4_ext_get_actual_len(tmp_dext) - 1 < orig_off)
		return -ENODATA;

601 602 603 604 605 606
	dext_old = *tmp_dext;
	oext_old = *tmp_oext;

	/* When tmp_dext is too large, pick up the target range. */
	diff = donor_off - le32_to_cpu(tmp_dext->ee_block);

607
	ext4_ext_store_pblock(tmp_dext, ext4_ext_pblock(tmp_dext) + diff);
608 609 610 611 612 613 614 615
	tmp_dext->ee_block =
			cpu_to_le32(le32_to_cpu(tmp_dext->ee_block) + diff);
	tmp_dext->ee_len = cpu_to_le16(le16_to_cpu(tmp_dext->ee_len) - diff);

	if (max_count < ext4_ext_get_actual_len(tmp_dext))
		tmp_dext->ee_len = cpu_to_le16(max_count);

	orig_diff = orig_off - le32_to_cpu(tmp_oext->ee_block);
616
	ext4_ext_store_pblock(tmp_oext, ext4_ext_pblock(tmp_oext) + orig_diff);
617 618 619 620 621 622 623 624 625 626 627

	/* Adjust extent length if donor extent is larger than orig */
	if (ext4_ext_get_actual_len(tmp_dext) >
	    ext4_ext_get_actual_len(tmp_oext) - orig_diff)
		tmp_dext->ee_len = cpu_to_le16(le16_to_cpu(tmp_oext->ee_len) -
						orig_diff);

	tmp_oext->ee_len = cpu_to_le16(ext4_ext_get_actual_len(tmp_dext));

	copy_extent_status(&oext_old, tmp_dext);
	copy_extent_status(&dext_old, tmp_oext);
628 629

	return 0;
630 631 632 633 634 635 636 637 638 639
}

/**
 * mext_replace_branches - Replace original extents with new extents
 *
 * @handle:		journal handle
 * @orig_inode:		original inode
 * @donor_inode:	donor inode
 * @from:		block offset of orig_inode
 * @count:		block count to be replaced
640
 * @err:		pointer to save return value
641 642 643 644 645 646 647 648 649 650
 *
 * Replace original inode extents and donor inode extents page by page.
 * We implement this replacement in the following three steps:
 * 1. Save the block information of original and donor inodes into
 *    dummy extents.
 * 2. Change the block information of original inode to point at the
 *    donor inode blocks.
 * 3. Change the block information of donor inode to point at the saved
 *    original inode blocks in the dummy extents.
 *
651
 * Return replaced block count.
652 653 654 655
 */
static int
mext_replace_branches(handle_t *handle, struct inode *orig_inode,
			   struct inode *donor_inode, ext4_lblk_t from,
656
			   ext4_lblk_t count, int *err)
657 658 659 660 661 662 663 664 665 666
{
	struct ext4_ext_path *orig_path = NULL;
	struct ext4_ext_path *donor_path = NULL;
	struct ext4_extent *oext, *dext;
	struct ext4_extent tmp_dext, tmp_oext;
	ext4_lblk_t orig_off = from, donor_off = from;
	int depth;
	int replaced_count = 0;
	int dext_alen;

667 668 669
	/* Protect extent trees against block allocations via delalloc */
	double_down_write_data_sem(orig_inode, donor_inode);

670
	/* Get the original extent for the block "orig_off" */
671 672
	*err = get_ext_path(orig_inode, orig_off, &orig_path);
	if (*err)
673 674 675
		goto out;

	/* Get the donor extent for the head */
676 677
	*err = get_ext_path(donor_inode, donor_off, &donor_path);
	if (*err)
678 679 680 681 682 683 684 685 686
		goto out;
	depth = ext_depth(orig_inode);
	oext = orig_path[depth].p_ext;
	tmp_oext = *oext;

	depth = ext_depth(donor_inode);
	dext = donor_path[depth].p_ext;
	tmp_dext = *dext;

687
	*err = mext_calc_swap_extents(&tmp_dext, &tmp_oext, orig_off,
688
				      donor_off, count);
689
	if (*err)
690
		goto out;
691 692 693 694

	/* Loop for the donor extents */
	while (1) {
		/* The extent for donor must be found. */
695
		if (!dext) {
696
			EXT4_ERROR_INODE(donor_inode,
697
				   "The extent for donor must be found");
698
			*err = -EIO;
699 700
			goto out;
		} else if (donor_off != le32_to_cpu(tmp_dext.ee_block)) {
701
			EXT4_ERROR_INODE(donor_inode,
702 703 704 705
				"Donor offset(%u) and the first block of donor "
				"extent(%u) should be equal",
				donor_off,
				le32_to_cpu(tmp_dext.ee_block));
706
			*err = -EIO;
707 708
			goto out;
		}
709 710

		/* Set donor extent to orig extent */
711
		*err = mext_leaf_block(handle, orig_inode,
712
					   orig_path, &tmp_dext, &orig_off);
713
		if (*err)
714 715 716
			goto out;

		/* Set orig extent to donor extent */
717
		*err = mext_leaf_block(handle, donor_inode,
718
					   donor_path, &tmp_oext, &donor_off);
719
		if (*err)
720 721 722 723 724 725 726 727 728 729 730 731 732
			goto out;

		dext_alen = ext4_ext_get_actual_len(&tmp_dext);
		replaced_count += dext_alen;
		donor_off += dext_alen;
		orig_off += dext_alen;

		/* Already moved the expected blocks */
		if (replaced_count >= count)
			break;

		if (orig_path)
			ext4_ext_drop_refs(orig_path);
733 734
		*err = get_ext_path(orig_inode, orig_off, &orig_path);
		if (*err)
735 736 737 738 739 740 741
			goto out;
		depth = ext_depth(orig_inode);
		oext = orig_path[depth].p_ext;
		tmp_oext = *oext;

		if (donor_path)
			ext4_ext_drop_refs(donor_path);
742 743
		*err = get_ext_path(donor_inode, donor_off, &donor_path);
		if (*err)
744 745 746 747 748
			goto out;
		depth = ext_depth(donor_inode);
		dext = donor_path[depth].p_ext;
		tmp_dext = *dext;

749
		*err = mext_calc_swap_extents(&tmp_dext, &tmp_oext, orig_off,
750
					   donor_off, count - replaced_count);
751
		if (*err)
752
			goto out;
753 754 755 756 757 758 759 760 761 762 763 764
	}

out:
	if (orig_path) {
		ext4_ext_drop_refs(orig_path);
		kfree(orig_path);
	}
	if (donor_path) {
		ext4_ext_drop_refs(donor_path);
		kfree(donor_path);
	}

765 766 767 768 769
	ext4_ext_invalidate_cache(orig_inode);
	ext4_ext_invalidate_cache(donor_inode);

	double_up_write_data_sem(orig_inode, donor_inode);

770
	return replaced_count;
771 772 773 774 775 776 777 778 779 780 781
}

/**
 * move_extent_per_page - Move extent data per page
 *
 * @o_filp:			file structure of original file
 * @donor_inode:		donor inode
 * @orig_page_offset:		page index on original file
 * @data_offset_in_page:	block index where data swapping starts
 * @block_len_in_page:		the number of blocks to be swapped
 * @uninit:			orig extent is uninitialized or not
782
 * @err:			pointer to save return value
783 784 785
 *
 * Save the data in original inode blocks and replace original inode extents
 * with donor inode extents by calling mext_replace_branches().
786 787
 * Finally, write out the saved data in new original inode blocks. Return
 * replaced block count.
788 789
 */
static int
790
move_extent_per_page(struct file *o_filp, struct inode *donor_inode,
791
		  pgoff_t orig_page_offset, int data_offset_in_page,
792
		  int block_len_in_page, int uninit, int *err)
793 794 795 796 797 798 799 800 801 802 803
{
	struct inode *orig_inode = o_filp->f_dentry->d_inode;
	struct address_space *mapping = orig_inode->i_mapping;
	struct buffer_head *bh;
	struct page *page = NULL;
	const struct address_space_operations *a_ops = mapping->a_ops;
	handle_t *handle;
	ext4_lblk_t orig_blk_offset;
	long long offs = orig_page_offset << PAGE_CACHE_SHIFT;
	unsigned long blocksize = orig_inode->i_sb->s_blocksize;
	unsigned int w_flags = 0;
804
	unsigned int tmp_data_size, data_size, replaced_size;
805
	void *fsdata;
806 807 808
	int i, jblocks;
	int err2 = 0;
	int replaced_count = 0;
809 810 811 812 813 814 815 816 817
	int blocks_per_page = PAGE_CACHE_SIZE >> orig_inode->i_blkbits;

	/*
	 * It needs twice the amount of ordinary journal buffers because
	 * inode and donor_inode may change each different metadata blocks.
	 */
	jblocks = ext4_writepage_trans_blocks(orig_inode) * 2;
	handle = ext4_journal_start(orig_inode, jblocks);
	if (IS_ERR(handle)) {
818 819
		*err = PTR_ERR(handle);
		return 0;
820 821 822 823 824 825 826 827 828 829 830 831 832 833 834
	}

	if (segment_eq(get_fs(), KERNEL_DS))
		w_flags |= AOP_FLAG_UNINTERRUPTIBLE;

	orig_blk_offset = orig_page_offset * blocks_per_page +
		data_offset_in_page;

	/*
	 * If orig extent is uninitialized one,
	 * it's not necessary force the page into memory
	 * and then force it to be written out again.
	 * Just swap data blocks between orig and donor.
	 */
	if (uninit) {
835 836 837
		replaced_count = mext_replace_branches(handle, orig_inode,
						donor_inode, orig_blk_offset,
						block_len_in_page, err);
838 839 840 841 842
		goto out2;
	}

	offs = (long long)orig_blk_offset << orig_inode->i_blkbits;

843
	/* Calculate data_size */
844 845 846
	if ((orig_blk_offset + block_len_in_page - 1) ==
	    ((orig_inode->i_size - 1) >> orig_inode->i_blkbits)) {
		/* Replace the last block */
847
		tmp_data_size = orig_inode->i_size & (blocksize - 1);
848
		/*
849
		 * If data_size equal zero, it shows data_size is multiples of
850 851
		 * blocksize. So we set appropriate value.
		 */
852 853
		if (tmp_data_size == 0)
			tmp_data_size = blocksize;
854

855
		data_size = tmp_data_size +
856
			((block_len_in_page - 1) << orig_inode->i_blkbits);
857 858 859 860
	} else
		data_size = block_len_in_page << orig_inode->i_blkbits;

	replaced_size = data_size;
861

862
	*err = a_ops->write_begin(o_filp, mapping, offs, data_size, w_flags,
863
				 &page, &fsdata);
864
	if (unlikely(*err < 0))
865 866 867 868 869 870 871 872 873 874 875 876 877 878
		goto out;

	if (!PageUptodate(page)) {
		mapping->a_ops->readpage(o_filp, page);
		lock_page(page);
	}

	/*
	 * try_to_release_page() doesn't call releasepage in writeback mode.
	 * We should care about the order of writing to the same file
	 * by multiple move extent processes.
	 * It needs to call wait_on_page_writeback() to wait for the
	 * writeback of the page.
	 */
879
	wait_on_page_writeback(page);
880 881 882 883

	/* Release old bh and drop refs */
	try_to_release_page(page, 0);

884 885 886 887 888 889 890 891
	replaced_count = mext_replace_branches(handle, orig_inode, donor_inode,
					orig_blk_offset, block_len_in_page,
					&err2);
	if (err2) {
		if (replaced_count) {
			block_len_in_page = replaced_count;
			replaced_size =
				block_len_in_page << orig_inode->i_blkbits;
892
		} else
893 894
			goto out;
	}
895 896 897 898 899 900 901 902 903

	if (!page_has_buffers(page))
		create_empty_buffers(page, 1 << orig_inode->i_blkbits, 0);

	bh = page_buffers(page);
	for (i = 0; i < data_offset_in_page; i++)
		bh = bh->b_this_page;

	for (i = 0; i < block_len_in_page; i++) {
904
		*err = ext4_get_block(orig_inode,
905
				(sector_t)(orig_blk_offset + i), bh, 0);
906
		if (*err < 0)
907 908 909 910 911 912
			goto out;

		if (bh->b_this_page != NULL)
			bh = bh->b_this_page;
	}

913
	*err = a_ops->write_end(o_filp, mapping, offs, data_size, replaced_size,
914 915 916 917 918 919 920 921
			       page, fsdata);
	page = NULL;

out:
	if (unlikely(page)) {
		if (PageLocked(page))
			unlock_page(page);
		page_cache_release(page);
922
		ext4_journal_stop(handle);
923 924 925 926
	}
out2:
	ext4_journal_stop(handle);

927 928 929 930
	if (err2)
		*err = err2;

	return replaced_count;
931 932 933
}

/**
934
 * mext_check_arguments - Check whether move extent can be done
935 936 937 938 939 940 941 942 943 944 945 946 947
 *
 * @orig_inode:		original inode
 * @donor_inode:	donor inode
 * @orig_start:		logical start offset in block for orig
 * @donor_start:	logical start offset in block for donor
 * @len:		the number of blocks to be moved
 *
 * Check the arguments of ext4_move_extents() whether the files can be
 * exchanged with each other.
 * Return 0 on success, or a negative error value on failure.
 */
static int
mext_check_arguments(struct inode *orig_inode,
948 949
		     struct inode *donor_inode, __u64 orig_start,
		     __u64 donor_start, __u64 *len)
950
{
951 952 953 954
	ext4_lblk_t orig_blocks, donor_blocks;
	unsigned int blkbits = orig_inode->i_blkbits;
	unsigned int blocksize = 1 << blkbits;

955 956 957 958 959 960 961
	if (donor_inode->i_mode & (S_ISUID|S_ISGID)) {
		ext4_debug("ext4 move extent: suid or sgid is set"
			   " to donor file [ino:orig %lu, donor %lu]\n",
			   orig_inode->i_ino, donor_inode->i_ino);
		return -EINVAL;
	}

962 963 964
	if (IS_IMMUTABLE(donor_inode) || IS_APPEND(donor_inode))
		return -EPERM;

965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981
	/* Ext4 move extent does not support swapfile */
	if (IS_SWAPFILE(orig_inode) || IS_SWAPFILE(donor_inode)) {
		ext4_debug("ext4 move extent: The argument files should "
			"not be swapfile [ino:orig %lu, donor %lu]\n",
			orig_inode->i_ino, donor_inode->i_ino);
		return -EINVAL;
	}

	/* Files should be in the same ext4 FS */
	if (orig_inode->i_sb != donor_inode->i_sb) {
		ext4_debug("ext4 move extent: The argument files "
			"should be in same FS [ino:orig %lu, donor %lu]\n",
			orig_inode->i_ino, donor_inode->i_ino);
		return -EINVAL;
	}

	/* Ext4 move extent supports only extent based file */
982
	if (!(ext4_test_inode_flag(orig_inode, EXT4_INODE_EXTENTS))) {
983 984 985
		ext4_debug("ext4 move extent: orig file is not extents "
			"based file [ino:orig %lu]\n", orig_inode->i_ino);
		return -EOPNOTSUPP;
986
	} else if (!(ext4_test_inode_flag(donor_inode, EXT4_INODE_EXTENTS))) {
987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004
		ext4_debug("ext4 move extent: donor file is not extents "
			"based file [ino:donor %lu]\n", donor_inode->i_ino);
		return -EOPNOTSUPP;
	}

	if ((!orig_inode->i_size) || (!donor_inode->i_size)) {
		ext4_debug("ext4 move extent: File size is 0 byte\n");
		return -EINVAL;
	}

	/* Start offset should be same */
	if (orig_start != donor_start) {
		ext4_debug("ext4 move extent: orig and donor's start "
			"offset are not same [ino:orig %lu, donor %lu]\n",
			orig_inode->i_ino, donor_inode->i_ino);
		return -EINVAL;
	}

1005 1006 1007 1008 1009 1010
	if ((orig_start > EXT_MAX_BLOCK) ||
	    (donor_start > EXT_MAX_BLOCK) ||
	    (*len > EXT_MAX_BLOCK) ||
	    (orig_start + *len > EXT_MAX_BLOCK))  {
		ext4_debug("ext4 move extent: Can't handle over [%u] blocks "
			"[ino:orig %lu, donor %lu]\n", EXT_MAX_BLOCK,
1011 1012 1013 1014 1015
			orig_inode->i_ino, donor_inode->i_ino);
		return -EINVAL;
	}

	if (orig_inode->i_size > donor_inode->i_size) {
1016 1017 1018
		donor_blocks = (donor_inode->i_size + blocksize - 1) >> blkbits;
		/* TODO: eliminate this artificial restriction */
		if (orig_start >= donor_blocks) {
1019
			ext4_debug("ext4 move extent: orig start offset "
1020 1021 1022
			"[%llu] should be less than donor file blocks "
			"[%u] [ino:orig %lu, donor %lu]\n",
			orig_start, donor_blocks,
1023 1024 1025 1026
			orig_inode->i_ino, donor_inode->i_ino);
			return -EINVAL;
		}

1027 1028
		/* TODO: eliminate this artificial restriction */
		if (orig_start + *len > donor_blocks) {
1029
			ext4_debug("ext4 move extent: End offset [%llu] should "
1030 1031
				"be less than donor file blocks [%u]."
				"So adjust length from %llu to %llu "
1032
				"[ino:orig %lu, donor %lu]\n",
1033 1034
				orig_start + *len, donor_blocks,
				*len, donor_blocks - orig_start,
1035
				orig_inode->i_ino, donor_inode->i_ino);
1036
			*len = donor_blocks - orig_start;
1037 1038
		}
	} else {
1039 1040
		orig_blocks = (orig_inode->i_size + blocksize - 1) >> blkbits;
		if (orig_start >= orig_blocks) {
1041
			ext4_debug("ext4 move extent: start offset [%llu] "
1042 1043 1044
				"should be less than original file blocks "
				"[%u] [ino:orig %lu, donor %lu]\n",
				 orig_start, orig_blocks,
1045 1046 1047 1048
				orig_inode->i_ino, donor_inode->i_ino);
			return -EINVAL;
		}

1049
		if (orig_start + *len > orig_blocks) {
1050
			ext4_debug("ext4 move extent: Adjust length "
1051 1052
				"from %llu to %llu. Because it should be "
				"less than original file blocks "
1053
				"[ino:orig %lu, donor %lu]\n",
1054
				*len, orig_blocks - orig_start,
1055
				orig_inode->i_ino, donor_inode->i_ino);
1056
			*len = orig_blocks - orig_start;
1057 1058 1059 1060
		}
	}

	if (!*len) {
1061
		ext4_debug("ext4 move extent: len should not be 0 "
1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075
			"[ino:orig %lu, donor %lu]\n", orig_inode->i_ino,
			donor_inode->i_ino);
		return -EINVAL;
	}

	return 0;
}

/**
 * mext_inode_double_lock - Lock i_mutex on both @inode1 and @inode2
 *
 * @inode1:	the inode structure
 * @inode2:	the inode structure
 *
1076 1077
 * Lock two inodes' i_mutex by i_ino order.
 * If inode1 or inode2 is NULL, return -EIO. Otherwise, return 0.
1078
 */
1079
static int
1080 1081
mext_inode_double_lock(struct inode *inode1, struct inode *inode2)
{
1082 1083 1084 1085
	int ret = 0;

	BUG_ON(inode1 == NULL && inode2 == NULL);

1086
	ret = mext_check_null_inode(inode1, inode2, __func__, __LINE__);
1087 1088 1089 1090 1091 1092
	if (ret < 0)
		goto out;

	if (inode1 == inode2) {
		mutex_lock(&inode1->i_mutex);
		goto out;
1093 1094 1095 1096 1097 1098 1099 1100 1101
	}

	if (inode1->i_ino < inode2->i_ino) {
		mutex_lock_nested(&inode1->i_mutex, I_MUTEX_PARENT);
		mutex_lock_nested(&inode2->i_mutex, I_MUTEX_CHILD);
	} else {
		mutex_lock_nested(&inode2->i_mutex, I_MUTEX_PARENT);
		mutex_lock_nested(&inode1->i_mutex, I_MUTEX_CHILD);
	}
1102 1103 1104

out:
	return ret;
1105 1106 1107 1108 1109 1110 1111 1112
}

/**
 * mext_inode_double_unlock - Release i_mutex on both @inode1 and @inode2
 *
 * @inode1:     the inode that is released first
 * @inode2:     the inode that is released second
 *
1113
 * If inode1 or inode2 is NULL, return -EIO. Otherwise, return 0.
1114 1115
 */

1116
static int
1117 1118
mext_inode_double_unlock(struct inode *inode1, struct inode *inode2)
{
1119 1120 1121 1122
	int ret = 0;

	BUG_ON(inode1 == NULL && inode2 == NULL);

1123
	ret = mext_check_null_inode(inode1, inode2, __func__, __LINE__);
1124 1125 1126
	if (ret < 0)
		goto out;

1127 1128 1129 1130 1131
	if (inode1)
		mutex_unlock(&inode1->i_mutex);

	if (inode2 && inode2 != inode1)
		mutex_unlock(&inode2->i_mutex);
1132 1133 1134

out:
	return ret;
1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190
}

/**
 * ext4_move_extents - Exchange the specified range of a file
 *
 * @o_filp:		file structure of the original file
 * @d_filp:		file structure of the donor file
 * @orig_start:		start offset in block for orig
 * @donor_start:	start offset in block for donor
 * @len:		the number of blocks to be moved
 * @moved_len:		moved block length
 *
 * This function returns 0 and moved block length is set in moved_len
 * if succeed, otherwise returns error value.
 *
 * Note: ext4_move_extents() proceeds the following order.
 * 1:ext4_move_extents() calculates the last block number of moving extent
 *   function by the start block number (orig_start) and the number of blocks
 *   to be moved (len) specified as arguments.
 *   If the {orig, donor}_start points a hole, the extent's start offset
 *   pointed by ext_cur (current extent), holecheck_path, orig_path are set
 *   after hole behind.
 * 2:Continue step 3 to step 5, until the holecheck_path points to last_extent
 *   or the ext_cur exceeds the block_end which is last logical block number.
 * 3:To get the length of continues area, call mext_next_extent()
 *   specified with the ext_cur (initial value is holecheck_path) re-cursive,
 *   until find un-continuous extent, the start logical block number exceeds
 *   the block_end or the extent points to the last extent.
 * 4:Exchange the original inode data with donor inode data
 *   from orig_page_offset to seq_end_page.
 *   The start indexes of data are specified as arguments.
 *   That of the original inode is orig_page_offset,
 *   and the donor inode is also orig_page_offset
 *   (To easily handle blocksize != pagesize case, the offset for the
 *   donor inode is block unit).
 * 5:Update holecheck_path and orig_path to points a next proceeding extent,
 *   then returns to step 2.
 * 6:Release holecheck_path, orig_path and set the len to moved_len
 *   which shows the number of moved blocks.
 *   The moved_len is useful for the command to calculate the file offset
 *   for starting next move extent ioctl.
 * 7:Return 0 on success, or a negative error value on failure.
 */
int
ext4_move_extents(struct file *o_filp, struct file *d_filp,
		 __u64 orig_start, __u64 donor_start, __u64 len,
		 __u64 *moved_len)
{
	struct inode *orig_inode = o_filp->f_dentry->d_inode;
	struct inode *donor_inode = d_filp->f_dentry->d_inode;
	struct ext4_ext_path *orig_path = NULL, *holecheck_path = NULL;
	struct ext4_extent *ext_prev, *ext_cur, *ext_dummy;
	ext4_lblk_t block_start = orig_start;
	ext4_lblk_t block_end, seq_start, add_blocks, file_end, seq_blocks = 0;
	ext4_lblk_t rest_blocks;
	pgoff_t orig_page_offset = 0, seq_end_page;
1191
	int ret1, ret2, depth, last_extent = 0;
1192 1193 1194 1195 1196
	int blocks_per_page = PAGE_CACHE_SIZE >> orig_inode->i_blkbits;
	int data_offset_in_page;
	int block_len_in_page;
	int uninit;

1197 1198 1199 1200 1201 1202 1203 1204
	/* orig and donor should be different file */
	if (orig_inode->i_ino == donor_inode->i_ino) {
		ext4_debug("ext4 move extent: The argument files should not "
			"be same file [ino:orig %lu, donor %lu]\n",
			orig_inode->i_ino, donor_inode->i_ino);
		return -EINVAL;
	}

1205 1206 1207 1208 1209 1210 1211 1212
	/* Regular file check */
	if (!S_ISREG(orig_inode->i_mode) || !S_ISREG(donor_inode->i_mode)) {
		ext4_debug("ext4 move extent: The argument files should be "
			"regular file [ino:orig %lu, donor %lu]\n",
			orig_inode->i_ino, donor_inode->i_ino);
		return -EINVAL;
	}

1213
	/* Protect orig and donor inodes against a truncate */
1214 1215 1216
	ret1 = mext_inode_double_lock(orig_inode, donor_inode);
	if (ret1 < 0)
		return ret1;
1217

1218 1219
	/* Protect extent tree against block allocations via delalloc */
	double_down_write_data_sem(orig_inode, donor_inode);
1220
	/* Check the filesystem environment whether move_extent can be done */
1221
	ret1 = mext_check_arguments(orig_inode, donor_inode, orig_start,
1222
				    donor_start, &len);
1223
	if (ret1)
1224
		goto out;
1225 1226 1227 1228 1229 1230

	file_end = (i_size_read(orig_inode) - 1) >> orig_inode->i_blkbits;
	block_end = block_start + len - 1;
	if (file_end < block_end)
		len -= block_end - file_end;

1231
	ret1 = get_ext_path(orig_inode, block_start, &orig_path);
1232 1233
	if (ret1)
		goto out;
1234 1235

	/* Get path structure to check the hole */
1236
	ret1 = get_ext_path(orig_inode, block_start, &holecheck_path);
1237
	if (ret1)
1238 1239 1240 1241 1242 1243
		goto out;

	depth = ext_depth(orig_inode);
	ext_cur = holecheck_path[depth].p_ext;

	/*
1244 1245
	 * Get proper starting location of block replacement if block_start was
	 * within the hole.
1246 1247 1248
	 */
	if (le32_to_cpu(ext_cur->ee_block) +
		ext4_ext_get_actual_len(ext_cur) - 1 < block_start) {
1249 1250 1251 1252
		/*
		 * The hole exists between extents or the tail of
		 * original file.
		 */
1253 1254 1255
		last_extent = mext_next_extent(orig_inode,
					holecheck_path, &ext_cur);
		if (last_extent < 0) {
1256
			ret1 = last_extent;
1257 1258 1259 1260 1261
			goto out;
		}
		last_extent = mext_next_extent(orig_inode, orig_path,
							&ext_dummy);
		if (last_extent < 0) {
1262
			ret1 = last_extent;
1263 1264
			goto out;
		}
1265 1266 1267 1268 1269 1270
		seq_start = le32_to_cpu(ext_cur->ee_block);
	} else if (le32_to_cpu(ext_cur->ee_block) > block_start)
		/* The hole exists at the beginning of original file. */
		seq_start = le32_to_cpu(ext_cur->ee_block);
	else
		seq_start = block_start;
1271 1272 1273 1274 1275

	/* No blocks within the specified range. */
	if (le32_to_cpu(ext_cur->ee_block) > block_end) {
		ext4_debug("ext4 move extent: The specified range of file "
							"may be the hole\n");
1276
		ret1 = -EINVAL;
1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295
		goto out;
	}

	/* Adjust start blocks */
	add_blocks = min(le32_to_cpu(ext_cur->ee_block) +
			 ext4_ext_get_actual_len(ext_cur), block_end + 1) -
		     max(le32_to_cpu(ext_cur->ee_block), block_start);

	while (!last_extent && le32_to_cpu(ext_cur->ee_block) <= block_end) {
		seq_blocks += add_blocks;

		/* Adjust tail blocks */
		if (seq_start + seq_blocks - 1 > block_end)
			seq_blocks = block_end - seq_start + 1;

		ext_prev = ext_cur;
		last_extent = mext_next_extent(orig_inode, holecheck_path,
						&ext_cur);
		if (last_extent < 0) {
1296
			ret1 = last_extent;
1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335
			break;
		}
		add_blocks = ext4_ext_get_actual_len(ext_cur);

		/*
		 * Extend the length of contiguous block (seq_blocks)
		 * if extents are contiguous.
		 */
		if (ext4_can_extents_be_merged(orig_inode,
					       ext_prev, ext_cur) &&
		    block_end >= le32_to_cpu(ext_cur->ee_block) &&
		    !last_extent)
			continue;

		/* Is original extent is uninitialized */
		uninit = ext4_ext_is_uninitialized(ext_prev);

		data_offset_in_page = seq_start % blocks_per_page;

		/*
		 * Calculate data blocks count that should be swapped
		 * at the first page.
		 */
		if (data_offset_in_page + seq_blocks > blocks_per_page) {
			/* Swapped blocks are across pages */
			block_len_in_page =
					blocks_per_page - data_offset_in_page;
		} else {
			/* Swapped blocks are in a page */
			block_len_in_page = seq_blocks;
		}

		orig_page_offset = seq_start >>
				(PAGE_CACHE_SHIFT - orig_inode->i_blkbits);
		seq_end_page = (seq_start + seq_blocks - 1) >>
				(PAGE_CACHE_SHIFT - orig_inode->i_blkbits);
		seq_start = le32_to_cpu(ext_cur->ee_block);
		rest_blocks = seq_blocks;

1336 1337 1338 1339 1340 1341 1342 1343
		/*
		 * Up semaphore to avoid following problems:
		 * a. transaction deadlock among ext4_journal_start,
		 *    ->write_begin via pagefault, and jbd2_journal_commit
		 * b. racing with ->readpage, ->write_begin, and ext4_get_block
		 *    in move_extent_per_page
		 */
		double_up_write_data_sem(orig_inode, donor_inode);
1344 1345 1346 1347

		while (orig_page_offset <= seq_end_page) {

			/* Swap original branches with new branches */
1348 1349
			block_len_in_page = move_extent_per_page(
						o_filp, donor_inode,
1350 1351
						orig_page_offset,
						data_offset_in_page,
1352 1353 1354
						block_len_in_page, uninit,
						&ret1);

1355 1356
			/* Count how many blocks we have exchanged */
			*moved_len += block_len_in_page;
1357
			if (ret1 < 0)
1358
				break;
1359
			if (*moved_len > len) {
1360
				EXT4_ERROR_INODE(orig_inode,
1361 1362 1363 1364
					"We replaced blocks too much! "
					"sum of replaced: %llu requested: %llu",
					*moved_len, len);
				ret1 = -EIO;
1365
				break;
1366
			}
1367

1368
			orig_page_offset++;
1369 1370 1371 1372 1373 1374 1375 1376
			data_offset_in_page = 0;
			rest_blocks -= block_len_in_page;
			if (rest_blocks > blocks_per_page)
				block_len_in_page = blocks_per_page;
			else
				block_len_in_page = rest_blocks;
		}

1377 1378 1379 1380
		double_down_write_data_sem(orig_inode, donor_inode);
		if (ret1 < 0)
			break;

1381 1382 1383
		/* Decrease buffer counter */
		if (holecheck_path)
			ext4_ext_drop_refs(holecheck_path);
1384
		ret1 = get_ext_path(orig_inode, seq_start, &holecheck_path);
1385
		if (ret1)
1386 1387 1388 1389 1390 1391
			break;
		depth = holecheck_path->p_depth;

		/* Decrease buffer counter */
		if (orig_path)
			ext4_ext_drop_refs(orig_path);
1392
		ret1 = get_ext_path(orig_inode, seq_start, &orig_path);
1393
		if (ret1)
1394 1395 1396 1397 1398 1399 1400 1401
			break;

		ext_cur = holecheck_path[depth].p_ext;
		add_blocks = ext4_ext_get_actual_len(ext_cur);
		seq_blocks = 0;

	}
out:
1402 1403 1404 1405 1406
	if (*moved_len) {
		ext4_discard_preallocations(orig_inode);
		ext4_discard_preallocations(donor_inode);
	}

1407 1408 1409 1410 1411 1412 1413 1414
	if (orig_path) {
		ext4_ext_drop_refs(orig_path);
		kfree(orig_path);
	}
	if (holecheck_path) {
		ext4_ext_drop_refs(holecheck_path);
		kfree(holecheck_path);
	}
1415
	double_up_write_data_sem(orig_inode, donor_inode);
1416
	ret2 = mext_inode_double_unlock(orig_inode, donor_inode);
1417

1418 1419 1420 1421
	if (ret1)
		return ret1;
	else if (ret2)
		return ret2;
1422 1423 1424

	return 0;
}