SAFE public projects git trees. - safe/jmp/linux-2.6/blob - fs/ext4/move_extent.c

   1 /*
   2  * Copyright (c) 2008,2009 NEC Software Tohoku, Ltd.
   3  * Written by Takashi Sato <t-sato@yk.jp.nec.com>
   4  *            Akira Fujita <a-fujita@rs.jp.nec.com>
   5  *
   6  * This program is free software; you can redistribute it and/or modify it
   7  * under the terms of version 2.1 of the GNU Lesser General Public License
   8  * as published by the Free Software Foundation.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  */
  15
  16 #include <linux/fs.h>
  17 #include <linux/quotaops.h>
  18 #include "ext4_jbd2.h"
  19 #include "ext4_extents.h"
  20 #include "ext4.h"
  21
  22 /**
  23  * get_ext_path - Find an extent path for designated logical block number.
  24  *
  25  * @inode:      an inode which is searched
  26  * @lblock:     logical block number to find an extent path
  27  * @path:       pointer to an extent path pointer (for output)
  28  *
  29  * ext4_ext_find_extent wrapper. Return 0 on success, or a negative error value
  30  * on failure.
  31  */
  32 static inline int
  33 get_ext_path(struct inode *inode, ext4_lblk_t lblock,
  34                 struct ext4_ext_path **path)
  35 {
  36         int ret = 0;
  37
  38         *path = ext4_ext_find_extent(inode, lblock, *path);
  39         if (IS_ERR(*path)) {
  40                 ret = PTR_ERR(*path);
  41                 *path = NULL;
  42         }
  43         return ret;
  44 }
  45
  46 /**
  47  * copy_extent_status - Copy the extent's initialization status
  48  *
  49  * @src:        an extent for getting initialize status
  50  * @dest:       an extent to be set the status
  51  */
  52 static void
  53 copy_extent_status(struct ext4_extent *src, struct ext4_extent *dest)
  54 {
  55         if (ext4_ext_is_uninitialized(src))
  56                 ext4_ext_mark_uninitialized(dest);
  57         else
  58                 dest->ee_len = cpu_to_le16(ext4_ext_get_actual_len(dest));
  59 }
  60
  61 /**
  62  * mext_next_extent - Search for the next extent and set it to "extent"
  63  *
  64  * @inode:      inode which is searched
  65  * @path:       this will obtain data for the next extent
  66  * @extent:     pointer to the next extent we have just gotten
  67  *
  68  * Search the next extent in the array of ext4_ext_path structure (@path)
  69  * and set it to ext4_extent structure (@extent). In addition, the member of
  70  * @path (->p_ext) also points the next extent. Return 0 on success, 1 if
  71  * ext4_ext_path structure refers to the last extent, or a negative error
  72  * value on failure.
  73  */
  74 static int
  75 mext_next_extent(struct inode *inode, struct ext4_ext_path *path,
  76                       struct ext4_extent **extent)
  77 {
  78         int ppos, leaf_ppos = path->p_depth;
  79
  80         ppos = leaf_ppos;
  81         if (EXT_LAST_EXTENT(path[ppos].p_hdr) > path[ppos].p_ext) {
  82                 /* leaf block */
  83                 *extent = ++path[ppos].p_ext;
  84                 return 0;
  85         }
  86
  87         while (--ppos >= 0) {
  88                 if (EXT_LAST_INDEX(path[ppos].p_hdr) >
  89                     path[ppos].p_idx) {
  90                         int cur_ppos = ppos;
  91
  92                         /* index block */
  93                         path[ppos].p_idx++;
  94                         path[ppos].p_block = idx_pblock(path[ppos].p_idx);
  95                         if (path[ppos+1].p_bh)
  96                                 brelse(path[ppos+1].p_bh);
  97                         path[ppos+1].p_bh =
  98                                 sb_bread(inode->i_sb, path[ppos].p_block);
  99                         if (!path[ppos+1].p_bh)
 100                                 return -EIO;
 101                         path[ppos+1].p_hdr =
 102                                 ext_block_hdr(path[ppos+1].p_bh);
 103
 104                         /* Halfway index block */
 105                         while (++cur_ppos < leaf_ppos) {
 106                                 path[cur_ppos].p_idx =
 107                                         EXT_FIRST_INDEX(path[cur_ppos].p_hdr);
 108                                 path[cur_ppos].p_block =
 109                                         idx_pblock(path[cur_ppos].p_idx);
 110                                 if (path[cur_ppos+1].p_bh)
 111                                         brelse(path[cur_ppos+1].p_bh);
 112                                 path[cur_ppos+1].p_bh = sb_bread(inode->i_sb,
 113                                         path[cur_ppos].p_block);
 114                                 if (!path[cur_ppos+1].p_bh)
 115                                         return -EIO;
 116                                 path[cur_ppos+1].p_hdr =
 117                                         ext_block_hdr(path[cur_ppos+1].p_bh);
 118                         }
 119
 120                         /* leaf block */
 121                         path[leaf_ppos].p_ext = *extent =
 122                                 EXT_FIRST_EXTENT(path[leaf_ppos].p_hdr);
 123                         return 0;
 124                 }
 125         }
 126         /* We found the last extent */
 127         return 1;
 128 }
 129
 130 /**
 131  * mext_check_null_inode - NULL check for two inodes
 132  *
 133  * If inode1 or inode2 is NULL, return -EIO. Otherwise, return 0.
 134  */
 135 static int
 136 mext_check_null_inode(struct inode *inode1, struct inode *inode2,
 137                 const char *function)
 138 {
 139         int ret = 0;
 140
 141         if (inode1 == NULL) {
 142                 ext4_error(inode2->i_sb, function,
 143                         "Both inodes should not be NULL: "
 144                         "inode1 NULL inode2 %lu", inode2->i_ino);
 145                 ret = -EIO;
 146         } else if (inode2 == NULL) {
 147                 ext4_error(inode1->i_sb, function,
 148                         "Both inodes should not be NULL: "
 149                         "inode1 %lu inode2 NULL", inode1->i_ino);
 150                 ret = -EIO;
 151         }
 152         return ret;
 153 }
 154
 155 /**
 156  * mext_double_down_read - Acquire two inodes' read semaphore
 157  *
 158  * @orig_inode:         original inode structure
 159  * @donor_inode:        donor inode structure
 160  * Acquire read semaphore of the two inodes (orig and donor) by i_ino order.
 161  */
 162 static void
 163 mext_double_down_read(struct inode *orig_inode, struct inode *donor_inode)
 164 {
 165         struct inode *first = orig_inode, *second = donor_inode;
 166
 167         /*
 168          * Use the inode number to provide the stable locking order instead
 169          * of its address, because the C language doesn't guarantee you can
 170          * compare pointers that don't come from the same array.
 171          */
 172         if (donor_inode->i_ino < orig_inode->i_ino) {
 173                 first = donor_inode;
 174                 second = orig_inode;
 175         }
 176
 177         down_read(&EXT4_I(first)->i_data_sem);
 178         down_read(&EXT4_I(second)->i_data_sem);
 179 }
 180
 181 /**
 182  * mext_double_down_write - Acquire two inodes' write semaphore
 183  *
 184  * @orig_inode:         original inode structure
 185  * @donor_inode:        donor inode structure
 186  * Acquire write semaphore of the two inodes (orig and donor) by i_ino order.
 187  */
 188 static void
 189 mext_double_down_write(struct inode *orig_inode, struct inode *donor_inode)
 190 {
 191         struct inode *first = orig_inode, *second = donor_inode;
 192
 193         /*
 194          * Use the inode number to provide the stable locking order instead
 195          * of its address, because the C language doesn't guarantee you can
 196          * compare pointers that don't come from the same array.
 197          */
 198         if (donor_inode->i_ino < orig_inode->i_ino) {
 199                 first = donor_inode;
 200                 second = orig_inode;
 201         }
 202
 203         down_write(&EXT4_I(first)->i_data_sem);
 204         down_write(&EXT4_I(second)->i_data_sem);
 205 }
 206
 207 /**
 208  * mext_double_up_read - Release two inodes' read semaphore
 209  *
 210  * @orig_inode:         original inode structure to be released its lock first
 211  * @donor_inode:        donor inode structure to be released its lock second
 212  * Release read semaphore of two inodes (orig and donor).
 213  */
 214 static void
 215 mext_double_up_read(struct inode *orig_inode, struct inode *donor_inode)
 216 {
 217         up_read(&EXT4_I(orig_inode)->i_data_sem);
 218         up_read(&EXT4_I(donor_inode)->i_data_sem);
 219 }
 220
 221 /**
 222  * mext_double_up_write - Release two inodes' write semaphore
 223  *
 224  * @orig_inode:         original inode structure to be released its lock first
 225  * @donor_inode:        donor inode structure to be released its lock second
 226  * Release write semaphore of two inodes (orig and donor).
 227  */
 228 static void
 229 mext_double_up_write(struct inode *orig_inode, struct inode *donor_inode)
 230 {
 231         up_write(&EXT4_I(orig_inode)->i_data_sem);
 232         up_write(&EXT4_I(donor_inode)->i_data_sem);
 233 }
 234
 235 /**
 236  * mext_insert_across_blocks - Insert extents across leaf block
 237  *
 238  * @handle:             journal handle
 239  * @orig_inode:         original inode
 240  * @o_start:            first original extent to be changed
 241  * @o_end:              last original extent to be changed
 242  * @start_ext:          first new extent to be inserted
 243  * @new_ext:            middle of new extent to be inserted
 244  * @end_ext:            last new extent to be inserted
 245  *
 246  * Allocate a new leaf block and insert extents into it. Return 0 on success,
 247  * or a negative error value on failure.
 248  */
 249 static int
 250 mext_insert_across_blocks(handle_t *handle, struct inode *orig_inode,
 251                 struct ext4_extent *o_start, struct ext4_extent *o_end,
 252                 struct ext4_extent *start_ext, struct ext4_extent *new_ext,
 253                 struct ext4_extent *end_ext)
 254 {
 255         struct ext4_ext_path *orig_path = NULL;
 256         ext4_lblk_t eblock = 0;
 257         int new_flag = 0;
 258         int end_flag = 0;
 259         int err = 0;
 260
 261         if (start_ext->ee_len && new_ext->ee_len && end_ext->ee_len) {
 262                 if (o_start == o_end) {
 263
 264                         /*       start_ext   new_ext    end_ext
 265                          * donor |---------|-----------|--------|
 266                          * orig  |------------------------------|
 267                          */
 268                         end_flag = 1;
 269                 } else {
 270
 271                         /*       start_ext   new_ext   end_ext
 272                          * donor |---------|----------|---------|
 273                          * orig  |---------------|--------------|
 274                          */
 275                         o_end->ee_block = end_ext->ee_block;
 276                         o_end->ee_len = end_ext->ee_len;
 277                         ext4_ext_store_pblock(o_end, ext_pblock(end_ext));
 278                 }
 279
 280                 o_start->ee_len = start_ext->ee_len;
 281                 new_flag = 1;
 282
 283         } else if (start_ext->ee_len && new_ext->ee_len &&
 284                    !end_ext->ee_len && o_start == o_end) {
 285
 286                 /*       start_ext      new_ext
 287                  * donor |--------------|---------------|
 288                  * orig  |------------------------------|
 289                  */
 290                 o_start->ee_len = start_ext->ee_len;
 291                 new_flag = 1;
 292
 293         } else if (!start_ext->ee_len && new_ext->ee_len &&
 294                    end_ext->ee_len && o_start == o_end) {
 295
 296                 /*        new_ext       end_ext
 297                  * donor |--------------|---------------|
 298                  * orig  |------------------------------|
 299                  */
 300                 o_end->ee_block = end_ext->ee_block;
 301                 o_end->ee_len = end_ext->ee_len;
 302                 ext4_ext_store_pblock(o_end, ext_pblock(end_ext));
 303
 304                 /*
 305                  * Set 0 to the extent block if new_ext was
 306                  * the first block.
 307                  */
 308                 if (new_ext->ee_block)
 309                         eblock = le32_to_cpu(new_ext->ee_block);
 310
 311                 new_flag = 1;
 312         } else {
 313                 ext4_debug("ext4 move extent: Unexpected insert case\n");
 314                 return -EIO;
 315         }
 316
 317         if (new_flag) {
 318                 err = get_ext_path(orig_inode, eblock, &orig_path);
 319                 if (orig_path == NULL)
 320                         goto out;
 321
 322                 if (ext4_ext_insert_extent(handle, orig_inode,
 323                                         orig_path, new_ext))
 324                         goto out;
 325         }
 326
 327         if (end_flag) {
 328                 err = get_ext_path(orig_inode,
 329                                 le32_to_cpu(end_ext->ee_block) - 1, &orig_path);
 330                 if (orig_path == NULL)
 331                         goto out;
 332
 333                 if (ext4_ext_insert_extent(handle, orig_inode,
 334                                            orig_path, end_ext))
 335                         goto out;
 336         }
 337 out:
 338         if (orig_path) {
 339                 ext4_ext_drop_refs(orig_path);
 340                 kfree(orig_path);
 341         }
 342
 343         return err;
 344
 345 }
 346
 347 /**
 348  * mext_insert_inside_block - Insert new extent to the extent block
 349  *
 350  * @o_start:            first original extent to be moved
 351  * @o_end:              last original extent to be moved
 352  * @start_ext:          first new extent to be inserted
 353  * @new_ext:            middle of new extent to be inserted
 354  * @end_ext:            last new extent to be inserted
 355  * @eh:                 extent header of target leaf block
 356  * @range_to_move:      used to decide how to insert extent
 357  *
 358  * Insert extents into the leaf block. The extent (@o_start) is overwritten
 359  * by inserted extents.
 360  */
 361 static void
 362 mext_insert_inside_block(struct ext4_extent *o_start,
 363                               struct ext4_extent *o_end,
 364                               struct ext4_extent *start_ext,
 365                               struct ext4_extent *new_ext,
 366                               struct ext4_extent *end_ext,
 367                               struct ext4_extent_header *eh,
 368                               int range_to_move)
 369 {
 370         int i = 0;
 371         unsigned long len;
 372
 373         /* Move the existing extents */
 374         if (range_to_move && o_end < EXT_LAST_EXTENT(eh)) {
 375                 len = (unsigned long)(EXT_LAST_EXTENT(eh) + 1) -
 376                         (unsigned long)(o_end + 1);
 377                 memmove(o_end + 1 + range_to_move, o_end + 1, len);
 378         }
 379
 380         /* Insert start entry */
 381         if (start_ext->ee_len)
 382                 o_start[i++].ee_len = start_ext->ee_len;
 383
 384         /* Insert new entry */
 385         if (new_ext->ee_len) {
 386                 o_start[i] = *new_ext;
 387                 ext4_ext_store_pblock(&o_start[i++], ext_pblock(new_ext));
 388         }
 389
 390         /* Insert end entry */
 391         if (end_ext->ee_len)
 392                 o_start[i] = *end_ext;
 393
 394         /* Increment the total entries counter on the extent block */
 395         le16_add_cpu(&eh->eh_entries, range_to_move);
 396 }
 397
 398 /**
 399  * mext_insert_extents - Insert new extent
 400  *
 401  * @handle:     journal handle
 402  * @orig_inode: original inode
 403  * @orig_path:  path indicates first extent to be changed
 404  * @o_start:    first original extent to be changed
 405  * @o_end:      last original extent to be changed
 406  * @start_ext:  first new extent to be inserted
 407  * @new_ext:    middle of new extent to be inserted
 408  * @end_ext:    last new extent to be inserted
 409  *
 410  * Call the function to insert extents. If we cannot add more extents into
 411  * the leaf block, we call mext_insert_across_blocks() to create a
 412  * new leaf block. Otherwise call mext_insert_inside_block(). Return 0
 413  * on success, or a negative error value on failure.
 414  */
 415 static int
 416 mext_insert_extents(handle_t *handle, struct inode *orig_inode,
 417                          struct ext4_ext_path *orig_path,
 418                          struct ext4_extent *o_start,
 419                          struct ext4_extent *o_end,
 420                          struct ext4_extent *start_ext,
 421                          struct ext4_extent *new_ext,
 422                          struct ext4_extent *end_ext)
 423 {
 424         struct  ext4_extent_header *eh;
 425         unsigned long need_slots, slots_range;
 426         int     range_to_move, depth, ret;
 427
 428         /*
 429          * The extents need to be inserted
 430          * start_extent + new_extent + end_extent.
 431          */
 432         need_slots = (start_ext->ee_len ? 1 : 0) + (end_ext->ee_len ? 1 : 0) +
 433                 (new_ext->ee_len ? 1 : 0);
 434
 435         /* The number of slots between start and end */
 436         slots_range = ((unsigned long)(o_end + 1) - (unsigned long)o_start + 1)
 437                 / sizeof(struct ext4_extent);
 438
 439         /* Range to move the end of extent */
 440         range_to_move = need_slots - slots_range;
 441         depth = orig_path->p_depth;
 442         orig_path += depth;
 443         eh = orig_path->p_hdr;
 444
 445         if (depth) {
 446                 /* Register to journal */
 447                 ret = ext4_journal_get_write_access(handle, orig_path->p_bh);
 448                 if (ret)
 449                         return ret;
 450         }
 451
 452         /* Expansion */
 453         if (range_to_move > 0 &&
 454                 (range_to_move > le16_to_cpu(eh->eh_max)
 455                         - le16_to_cpu(eh->eh_entries))) {
 456
 457                 ret = mext_insert_across_blocks(handle, orig_inode, o_start,
 458                                         o_end, start_ext, new_ext, end_ext);
 459                 if (ret < 0)
 460                         return ret;
 461         } else
 462                 mext_insert_inside_block(o_start, o_end, start_ext, new_ext,
 463                                                 end_ext, eh, range_to_move);
 464
 465         if (depth) {
 466                 ret = ext4_handle_dirty_metadata(handle, orig_inode,
 467                                                  orig_path->p_bh);
 468                 if (ret)
 469                         return ret;
 470         } else {
 471                 ret = ext4_mark_inode_dirty(handle, orig_inode);
 472                 if (ret < 0)
 473                         return ret;
 474         }
 475
 476         return 0;
 477 }
 478
 479 /**
 480  * mext_leaf_block - Move one leaf extent block into the inode.
 481  *
 482  * @handle:             journal handle
 483  * @orig_inode:         original inode
 484  * @orig_path:          path indicates first extent to be changed
 485  * @dext:               donor extent
 486  * @from:               start offset on the target file
 487  *
 488  * In order to insert extents into the leaf block, we must divide the extent
 489  * in the leaf block into three extents. The one is located to be inserted
 490  * extents, and the others are located around it.
 491  *
 492  * Therefore, this function creates structures to save extents of the leaf
 493  * block, and inserts extents by calling mext_insert_extents() with
 494  * created extents. Return 0 on success, or a negative error value on failure.
 495  */
 496 static int
 497 mext_leaf_block(handle_t *handle, struct inode *orig_inode,
 498                      struct ext4_ext_path *orig_path, struct ext4_extent *dext,
 499                      ext4_lblk_t *from)
 500 {
 501         struct ext4_extent *oext, *o_start, *o_end, *prev_ext;
 502         struct ext4_extent new_ext, start_ext, end_ext;
 503         ext4_lblk_t new_ext_end;
 504         ext4_fsblk_t new_phys_end;
 505         int oext_alen, new_ext_alen, end_ext_alen;
 506         int depth = ext_depth(orig_inode);
 507         int ret;
 508
 509         o_start = o_end = oext = orig_path[depth].p_ext;
 510         oext_alen = ext4_ext_get_actual_len(oext);
 511         start_ext.ee_len = end_ext.ee_len = 0;
 512
 513         new_ext.ee_block = cpu_to_le32(*from);
 514         ext4_ext_store_pblock(&new_ext, ext_pblock(dext));
 515         new_ext.ee_len = dext->ee_len;
 516         new_ext_alen = ext4_ext_get_actual_len(&new_ext);
 517         new_ext_end = le32_to_cpu(new_ext.ee_block) + new_ext_alen - 1;
 518         new_phys_end = ext_pblock(&new_ext) + new_ext_alen - 1;
 519
 520         /*
 521          * Case: original extent is first
 522          * oext      |--------|
 523          * new_ext      |--|
 524          * start_ext |--|
 525          */
 526         if (le32_to_cpu(oext->ee_block) < le32_to_cpu(new_ext.ee_block) &&
 527                 le32_to_cpu(new_ext.ee_block) <
 528                 le32_to_cpu(oext->ee_block) + oext_alen) {
 529                 start_ext.ee_len = cpu_to_le16(le32_to_cpu(new_ext.ee_block) -
 530                                                le32_to_cpu(oext->ee_block));
 531                 copy_extent_status(oext, &start_ext);
 532         } else if (oext > EXT_FIRST_EXTENT(orig_path[depth].p_hdr)) {
 533                 prev_ext = oext - 1;
 534                 /*
 535                  * We can merge new_ext into previous extent,
 536                  * if these are contiguous and same extent type.
 537                  */
 538                 if (ext4_can_extents_be_merged(orig_inode, prev_ext,
 539                                                &new_ext)) {
 540                         o_start = prev_ext;
 541                         start_ext.ee_len = cpu_to_le16(
 542                                 ext4_ext_get_actual_len(prev_ext) +
 543                                 new_ext_alen);
 544                         copy_extent_status(prev_ext, &start_ext);
 545                         new_ext.ee_len = 0;
 546                 }
 547         }
 548
 549         /*
 550          * Case: new_ext_end must be less than oext
 551          * oext      |-----------|
 552          * new_ext       |-------|
 553          */
 554         if (le32_to_cpu(oext->ee_block) + oext_alen - 1 < new_ext_end) {
 555                 ext4_error(orig_inode->i_sb, __func__,
 556                         "new_ext_end(%u) should be less than or equal to "
 557                         "oext->ee_block(%u) + oext_alen(%d) - 1",
 558                         new_ext_end, le32_to_cpu(oext->ee_block),
 559                         oext_alen);
 560                 ret = -EIO;
 561                 goto out;
 562         }
 563
 564         /*
 565          * Case: new_ext is smaller than original extent
 566          * oext    |---------------|
 567          * new_ext |-----------|
 568          * end_ext             |---|
 569          */
 570         if (le32_to_cpu(oext->ee_block) <= new_ext_end &&
 571                 new_ext_end < le32_to_cpu(oext->ee_block) + oext_alen - 1) {
 572                 end_ext.ee_len =
 573                         cpu_to_le16(le32_to_cpu(oext->ee_block) +
 574                         oext_alen - 1 - new_ext_end);
 575                 copy_extent_status(oext, &end_ext);
 576                 end_ext_alen = ext4_ext_get_actual_len(&end_ext);
 577                 ext4_ext_store_pblock(&end_ext,
 578                         (ext_pblock(o_end) + oext_alen - end_ext_alen));
 579                 end_ext.ee_block =
 580                         cpu_to_le32(le32_to_cpu(o_end->ee_block) +
 581                         oext_alen - end_ext_alen);
 582         }
 583
 584         ret = mext_insert_extents(handle, orig_inode, orig_path, o_start,
 585                                 o_end, &start_ext, &new_ext, &end_ext);
 586 out:
 587         return ret;
 588 }
 589
 590 /**
 591  * mext_calc_swap_extents - Calculate extents for extent swapping.
 592  *
 593  * @tmp_dext:           the extent that will belong to the original inode
 594  * @tmp_oext:           the extent that will belong to the donor inode
 595  * @orig_off:           block offset of original inode
 596  * @donor_off:          block offset of donor inode
 597  * @max_count:          the maximun length of extents
 598  */
 599 static void
 600 mext_calc_swap_extents(struct ext4_extent *tmp_dext,
 601                               struct ext4_extent *tmp_oext,
 602                               ext4_lblk_t orig_off, ext4_lblk_t donor_off,
 603                               ext4_lblk_t max_count)
 604 {
 605         ext4_lblk_t diff, orig_diff;
 606         struct ext4_extent dext_old, oext_old;
 607
 608         dext_old = *tmp_dext;
 609         oext_old = *tmp_oext;
 610
 611         /* When tmp_dext is too large, pick up the target range. */
 612         diff = donor_off - le32_to_cpu(tmp_dext->ee_block);
 613
 614         ext4_ext_store_pblock(tmp_dext, ext_pblock(tmp_dext) + diff);
 615         tmp_dext->ee_block =
 616                         cpu_to_le32(le32_to_cpu(tmp_dext->ee_block) + diff);
 617         tmp_dext->ee_len = cpu_to_le16(le16_to_cpu(tmp_dext->ee_len) - diff);
 618
 619         if (max_count < ext4_ext_get_actual_len(tmp_dext))
 620                 tmp_dext->ee_len = cpu_to_le16(max_count);
 621
 622         orig_diff = orig_off - le32_to_cpu(tmp_oext->ee_block);
 623         ext4_ext_store_pblock(tmp_oext, ext_pblock(tmp_oext) + orig_diff);
 624
 625         /* Adjust extent length if donor extent is larger than orig */
 626         if (ext4_ext_get_actual_len(tmp_dext) >
 627             ext4_ext_get_actual_len(tmp_oext) - orig_diff)
 628                 tmp_dext->ee_len = cpu_to_le16(le16_to_cpu(tmp_oext->ee_len) -
 629                                                 orig_diff);
 630
 631         tmp_oext->ee_len = cpu_to_le16(ext4_ext_get_actual_len(tmp_dext));
 632
 633         copy_extent_status(&oext_old, tmp_dext);
 634         copy_extent_status(&dext_old, tmp_oext);
 635 }
 636
 637 /**
 638  * mext_replace_branches - Replace original extents with new extents
 639  *
 640  * @handle:             journal handle
 641  * @orig_inode:         original inode
 642  * @donor_inode:        donor inode
 643  * @from:               block offset of orig_inode
 644  * @count:              block count to be replaced
 645  *
 646  * Replace original inode extents and donor inode extents page by page.
 647  * We implement this replacement in the following three steps:
 648  * 1. Save the block information of original and donor inodes into
 649  *    dummy extents.
 650  * 2. Change the block information of original inode to point at the
 651  *    donor inode blocks.
 652  * 3. Change the block information of donor inode to point at the saved
 653  *    original inode blocks in the dummy extents.
 654  *
 655  * Return 0 on success, or a negative error value on failure.
 656  */
 657 static int
 658 mext_replace_branches(handle_t *handle, struct inode *orig_inode,
 659                            struct inode *donor_inode, ext4_lblk_t from,
 660                            ext4_lblk_t count)
 661 {
 662         struct ext4_ext_path *orig_path = NULL;
 663         struct ext4_ext_path *donor_path = NULL;
 664         struct ext4_extent *oext, *dext;
 665         struct ext4_extent tmp_dext, tmp_oext;
 666         ext4_lblk_t orig_off = from, donor_off = from;
 667         int err = 0;
 668         int depth;
 669         int replaced_count = 0;
 670         int dext_alen;
 671
 672         mext_double_down_write(orig_inode, donor_inode);
 673
 674         /* Get the original extent for the block "orig_off" */
 675         err = get_ext_path(orig_inode, orig_off, &orig_path);
 676         if (orig_path == NULL)
 677                 goto out;
 678
 679         /* Get the donor extent for the head */
 680         err = get_ext_path(donor_inode, donor_off, &donor_path);
 681         if (donor_path == NULL)
 682                 goto out;
 683         depth = ext_depth(orig_inode);
 684         oext = orig_path[depth].p_ext;
 685         tmp_oext = *oext;
 686
 687         depth = ext_depth(donor_inode);
 688         dext = donor_path[depth].p_ext;
 689         tmp_dext = *dext;
 690
 691         mext_calc_swap_extents(&tmp_dext, &tmp_oext, orig_off,
 692                                       donor_off, count);
 693
 694         /* Loop for the donor extents */
 695         while (1) {
 696                 /* The extent for donor must be found. */
 697                 if (!dext) {
 698                         ext4_error(donor_inode->i_sb, __func__,
 699                                    "The extent for donor must be found");
 700                         err = -EIO;
 701                         goto out;
 702                 } else if (donor_off != le32_to_cpu(tmp_dext.ee_block)) {
 703                         ext4_error(donor_inode->i_sb, __func__,
 704                                 "Donor offset(%u) and the first block of donor "
 705                                 "extent(%u) should be equal",
 706                                 donor_off,
 707                                 le32_to_cpu(tmp_dext.ee_block));
 708                         err = -EIO;
 709                         goto out;
 710                 }
 711
 712                 /* Set donor extent to orig extent */
 713                 err = mext_leaf_block(handle, orig_inode,
 714                                            orig_path, &tmp_dext, &orig_off);
 715                 if (err < 0)
 716                         goto out;
 717
 718                 /* Set orig extent to donor extent */
 719                 err = mext_leaf_block(handle, donor_inode,
 720                                            donor_path, &tmp_oext, &donor_off);
 721                 if (err < 0)
 722                         goto out;
 723
 724                 dext_alen = ext4_ext_get_actual_len(&tmp_dext);
 725                 replaced_count += dext_alen;
 726                 donor_off += dext_alen;
 727                 orig_off += dext_alen;
 728
 729                 /* Already moved the expected blocks */
 730                 if (replaced_count >= count)
 731                         break;
 732
 733                 if (orig_path)
 734                         ext4_ext_drop_refs(orig_path);
 735                 err = get_ext_path(orig_inode, orig_off, &orig_path);
 736                 if (orig_path == NULL)
 737                         goto out;
 738                 depth = ext_depth(orig_inode);
 739                 oext = orig_path[depth].p_ext;
 740                 if (le32_to_cpu(oext->ee_block) +
 741                                 ext4_ext_get_actual_len(oext) <= orig_off) {
 742                         err = 0;
 743                         goto out;
 744                 }
 745                 tmp_oext = *oext;
 746
 747                 if (donor_path)
 748                         ext4_ext_drop_refs(donor_path);
 749                 err = get_ext_path(donor_inode, donor_off, &donor_path);
 750                 if (donor_path == NULL)
 751                         goto out;
 752                 depth = ext_depth(donor_inode);
 753                 dext = donor_path[depth].p_ext;
 754                 if (le32_to_cpu(dext->ee_block) +
 755                                 ext4_ext_get_actual_len(dext) <= donor_off) {
 756                         err = 0;
 757                         goto out;
 758                 }
 759                 tmp_dext = *dext;
 760
 761                 mext_calc_swap_extents(&tmp_dext, &tmp_oext, orig_off,
 762                                               donor_off,
 763                                               count - replaced_count);
 764         }
 765
 766 out:
 767         if (orig_path) {
 768                 ext4_ext_drop_refs(orig_path);
 769                 kfree(orig_path);
 770         }
 771         if (donor_path) {
 772                 ext4_ext_drop_refs(donor_path);
 773                 kfree(donor_path);
 774         }
 775
 776         mext_double_up_write(orig_inode, donor_inode);
 777         return err;
 778 }
 779
 780 /**
 781  * move_extent_per_page - Move extent data per page
 782  *
 783  * @o_filp:                     file structure of original file
 784  * @donor_inode:                donor inode
 785  * @orig_page_offset:           page index on original file
 786  * @data_offset_in_page:        block index where data swapping starts
 787  * @block_len_in_page:          the number of blocks to be swapped
 788  * @uninit:                     orig extent is uninitialized or not
 789  *
 790  * Save the data in original inode blocks and replace original inode extents
 791  * with donor inode extents by calling mext_replace_branches().
 792  * Finally, write out the saved data in new original inode blocks. Return 0
 793  * on success, or a negative error value on failure.
 794  */
 795 static int
 796 move_extent_per_page(struct file *o_filp, struct inode *donor_inode,
 797                   pgoff_t orig_page_offset, int data_offset_in_page,
 798                   int block_len_in_page, int uninit)
 799 {
 800         struct inode *orig_inode = o_filp->f_dentry->d_inode;
 801         struct address_space *mapping = orig_inode->i_mapping;
 802         struct buffer_head *bh;
 803         struct page *page = NULL;
 804         const struct address_space_operations *a_ops = mapping->a_ops;
 805         handle_t *handle;
 806         ext4_lblk_t orig_blk_offset;
 807         long long offs = orig_page_offset << PAGE_CACHE_SHIFT;
 808         unsigned long blocksize = orig_inode->i_sb->s_blocksize;
 809         unsigned int w_flags = 0;
 810         unsigned int tmp_data_len, data_len;
 811         void *fsdata;
 812         int ret, i, jblocks;
 813         int blocks_per_page = PAGE_CACHE_SIZE >> orig_inode->i_blkbits;
 814
 815         /*
 816          * It needs twice the amount of ordinary journal buffers because
 817          * inode and donor_inode may change each different metadata blocks.
 818          */
 819         jblocks = ext4_writepage_trans_blocks(orig_inode) * 2;
 820         handle = ext4_journal_start(orig_inode, jblocks);
 821         if (IS_ERR(handle)) {
 822                 ret = PTR_ERR(handle);
 823                 return ret;
 824         }
 825
 826         if (segment_eq(get_fs(), KERNEL_DS))
 827                 w_flags |= AOP_FLAG_UNINTERRUPTIBLE;
 828
 829         orig_blk_offset = orig_page_offset * blocks_per_page +
 830                 data_offset_in_page;
 831
 832         /*
 833          * If orig extent is uninitialized one,
 834          * it's not necessary force the page into memory
 835          * and then force it to be written out again.
 836          * Just swap data blocks between orig and donor.
 837          */
 838         if (uninit) {
 839                 ret = mext_replace_branches(handle, orig_inode,
 840                                                  donor_inode, orig_blk_offset,
 841                                                  block_len_in_page);
 842
 843                 /* Clear the inode cache not to refer to the old data */
 844                 ext4_ext_invalidate_cache(orig_inode);
 845                 ext4_ext_invalidate_cache(donor_inode);
 846                 goto out2;
 847         }
 848
 849         offs = (long long)orig_blk_offset << orig_inode->i_blkbits;
 850
 851         /* Calculate data_len */
 852         if ((orig_blk_offset + block_len_in_page - 1) ==
 853             ((orig_inode->i_size - 1) >> orig_inode->i_blkbits)) {
 854                 /* Replace the last block */
 855                 tmp_data_len = orig_inode->i_size & (blocksize - 1);
 856                 /*
 857                  * If data_len equal zero, it shows data_len is multiples of
 858                  * blocksize. So we set appropriate value.
 859                  */
 860                 if (tmp_data_len == 0)
 861                         tmp_data_len = blocksize;
 862
 863                 data_len = tmp_data_len +
 864                         ((block_len_in_page - 1) << orig_inode->i_blkbits);
 865         } else {
 866                 data_len = block_len_in_page << orig_inode->i_blkbits;
 867         }
 868
 869         ret = a_ops->write_begin(o_filp, mapping, offs, data_len, w_flags,
 870                                  &page, &fsdata);
 871         if (unlikely(ret < 0))
 872                 goto out;
 873
 874         if (!PageUptodate(page)) {
 875                 mapping->a_ops->readpage(o_filp, page);
 876                 lock_page(page);
 877         }
 878
 879         /*
 880          * try_to_release_page() doesn't call releasepage in writeback mode.
 881          * We should care about the order of writing to the same file
 882          * by multiple move extent processes.
 883          * It needs to call wait_on_page_writeback() to wait for the
 884          * writeback of the page.
 885          */
 886         if (PageWriteback(page))
 887                 wait_on_page_writeback(page);
 888
 889         /* Release old bh and drop refs */
 890         try_to_release_page(page, 0);
 891
 892         ret = mext_replace_branches(handle, orig_inode, donor_inode,
 893                                          orig_blk_offset, block_len_in_page);
 894         if (ret < 0)
 895                 goto out;
 896
 897         /* Clear the inode cache not to refer to the old data */
 898         ext4_ext_invalidate_cache(orig_inode);
 899         ext4_ext_invalidate_cache(donor_inode);
 900
 901         if (!page_has_buffers(page))
 902                 create_empty_buffers(page, 1 << orig_inode->i_blkbits, 0);
 903
 904         bh = page_buffers(page);
 905         for (i = 0; i < data_offset_in_page; i++)
 906                 bh = bh->b_this_page;
 907
 908         for (i = 0; i < block_len_in_page; i++) {
 909                 ret = ext4_get_block(orig_inode,
 910                                 (sector_t)(orig_blk_offset + i), bh, 0);
 911                 if (ret < 0)
 912                         goto out;
 913
 914                 if (bh->b_this_page != NULL)
 915                         bh = bh->b_this_page;
 916         }
 917
 918         ret = a_ops->write_end(o_filp, mapping, offs, data_len, data_len,
 919                                page, fsdata);
 920         page = NULL;
 921
 922 out:
 923         if (unlikely(page)) {
 924                 if (PageLocked(page))
 925                         unlock_page(page);
 926                 page_cache_release(page);
 927                 ext4_journal_stop(handle);
 928         }
 929 out2:
 930         ext4_journal_stop(handle);
 931
 932         return ret < 0 ? ret : 0;
 933 }
 934
 935 /**
 936  * mext_check_argumants - Check whether move extent can be done
 937  *
 938  * @orig_inode:         original inode
 939  * @donor_inode:        donor inode
 940  * @orig_start:         logical start offset in block for orig
 941  * @donor_start:        logical start offset in block for donor
 942  * @len:                the number of blocks to be moved
 943  * @moved_len:          moved block length
 944  *
 945  * Check the arguments of ext4_move_extents() whether the files can be
 946  * exchanged with each other.
 947  * Return 0 on success, or a negative error value on failure.
 948  */
 949 static int
 950 mext_check_arguments(struct inode *orig_inode,
 951                           struct inode *donor_inode, __u64 orig_start,
 952                           __u64 donor_start, __u64 *len, __u64 moved_len)
 953 {
 954         ext4_lblk_t orig_blocks, donor_blocks;
 955         unsigned int blkbits = orig_inode->i_blkbits;
 956         unsigned int blocksize = 1 << blkbits;
 957
 958         /* Regular file check */
 959         if (!S_ISREG(orig_inode->i_mode) || !S_ISREG(donor_inode->i_mode)) {
 960                 ext4_debug("ext4 move extent: The argument files should be "
 961                         "regular file [ino:orig %lu, donor %lu]\n",
 962                         orig_inode->i_ino, donor_inode->i_ino);
 963                 return -EINVAL;
 964         }
 965
 966         /* Ext4 move extent does not support swapfile */
 967         if (IS_SWAPFILE(orig_inode) || IS_SWAPFILE(donor_inode)) {
 968                 ext4_debug("ext4 move extent: The argument files should "
 969                         "not be swapfile [ino:orig %lu, donor %lu]\n",
 970                         orig_inode->i_ino, donor_inode->i_ino);
 971                 return -EINVAL;
 972         }
 973
 974         /* Files should be in the same ext4 FS */
 975         if (orig_inode->i_sb != donor_inode->i_sb) {
 976                 ext4_debug("ext4 move extent: The argument files "
 977                         "should be in same FS [ino:orig %lu, donor %lu]\n",
 978                         orig_inode->i_ino, donor_inode->i_ino);
 979                 return -EINVAL;
 980         }
 981
 982         /* orig and donor should be different file */
 983         if (orig_inode->i_ino == donor_inode->i_ino) {
 984                 ext4_debug("ext4 move extent: The argument files should not "
 985                         "be same file [ino:orig %lu, donor %lu]\n",
 986                         orig_inode->i_ino, donor_inode->i_ino);
 987                 return -EINVAL;
 988         }
 989
 990         /* Ext4 move extent supports only extent based file */
 991         if (!(EXT4_I(orig_inode)->i_flags & EXT4_EXTENTS_FL)) {
 992                 ext4_debug("ext4 move extent: orig file is not extents "
 993                         "based file [ino:orig %lu]\n", orig_inode->i_ino);
 994                 return -EOPNOTSUPP;
 995         } else if (!(EXT4_I(donor_inode)->i_flags & EXT4_EXTENTS_FL)) {
 996                 ext4_debug("ext4 move extent: donor file is not extents "
 997                         "based file [ino:donor %lu]\n", donor_inode->i_ino);
 998                 return -EOPNOTSUPP;
 999         }
1000
1001         if ((!orig_inode->i_size) || (!donor_inode->i_size)) {
1002                 ext4_debug("ext4 move extent: File size is 0 byte\n");
1003                 return -EINVAL;
1004         }
1005
1006         /* Start offset should be same */
1007         if (orig_start != donor_start) {
1008                 ext4_debug("ext4 move extent: orig and donor's start "
1009                         "offset are not same [ino:orig %lu, donor %lu]\n",
1010                         orig_inode->i_ino, donor_inode->i_ino);
1011                 return -EINVAL;
1012         }
1013
1014         if (moved_len) {
1015                 ext4_debug("ext4 move extent: moved_len should be 0 "
1016                         "[ino:orig %lu, donor %lu]\n", orig_inode->i_ino,
1017                         donor_inode->i_ino);
1018                 return -EINVAL;
1019         }
1020
1021         if ((orig_start > MAX_DEFRAG_SIZE) ||
1022             (donor_start > MAX_DEFRAG_SIZE) ||
1023             (*len > MAX_DEFRAG_SIZE) ||
1024             (orig_start + *len > MAX_DEFRAG_SIZE))  {
1025                 ext4_debug("ext4 move extent: Can't handle over [%lu] blocks "
1026                         "[ino:orig %lu, donor %lu]\n", MAX_DEFRAG_SIZE,
1027                         orig_inode->i_ino, donor_inode->i_ino);
1028                 return -EINVAL;
1029         }
1030
1031         if (orig_inode->i_size > donor_inode->i_size) {
1032                 donor_blocks = (donor_inode->i_size + blocksize - 1) >> blkbits;
1033                 /* TODO: eliminate this artificial restriction */
1034                 if (orig_start >= donor_blocks) {
1035                         ext4_debug("ext4 move extent: orig start offset "
1036                         "[%llu] should be less than donor file blocks "
1037                         "[%u] [ino:orig %lu, donor %lu]\n",
1038                         orig_start, donor_blocks,
1039                         orig_inode->i_ino, donor_inode->i_ino);
1040                         return -EINVAL;
1041                 }
1042
1043                 /* TODO: eliminate this artificial restriction */
1044                 if (orig_start + *len > donor_blocks) {
1045                         ext4_debug("ext4 move extent: End offset [%llu] should "
1046                                 "be less than donor file blocks [%u]."
1047                                 "So adjust length from %llu to %llu "
1048                                 "[ino:orig %lu, donor %lu]\n",
1049                                 orig_start + *len, donor_blocks,
1050                                 *len, donor_blocks - orig_start,
1051                                 orig_inode->i_ino, donor_inode->i_ino);
1052                         *len = donor_blocks - orig_start;
1053                 }
1054         } else {
1055                 orig_blocks = (orig_inode->i_size + blocksize - 1) >> blkbits;
1056                 if (orig_start >= orig_blocks) {
1057                         ext4_debug("ext4 move extent: start offset [%llu] "
1058                                 "should be less than original file blocks "
1059                                 "[%u] [ino:orig %lu, donor %lu]\n",
1060                                  orig_start, orig_blocks,
1061                                 orig_inode->i_ino, donor_inode->i_ino);
1062                         return -EINVAL;
1063                 }
1064
1065                 if (orig_start + *len > orig_blocks) {
1066                         ext4_debug("ext4 move extent: Adjust length "
1067                                 "from %llu to %llu. Because it should be "
1068                                 "less than original file blocks "
1069                                 "[ino:orig %lu, donor %lu]\n",
1070                                 *len, orig_blocks - orig_start,
1071                                 orig_inode->i_ino, donor_inode->i_ino);
1072                         *len = orig_blocks - orig_start;
1073                 }
1074         }
1075
1076         if (!*len) {
1077                 ext4_debug("ext4 move extent: len shoudld not be 0 "
1078                         "[ino:orig %lu, donor %lu]\n", orig_inode->i_ino,
1079                         donor_inode->i_ino);
1080                 return -EINVAL;
1081         }
1082
1083         return 0;
1084 }
1085
1086 /**
1087  * mext_inode_double_lock - Lock i_mutex on both @inode1 and @inode2
1088  *
1089  * @inode1:     the inode structure
1090  * @inode2:     the inode structure
1091  *
1092  * Lock two inodes' i_mutex by i_ino order.
1093  * If inode1 or inode2 is NULL, return -EIO. Otherwise, return 0.
1094  */
1095 static int
1096 mext_inode_double_lock(struct inode *inode1, struct inode *inode2)
1097 {
1098         int ret = 0;
1099
1100         BUG_ON(inode1 == NULL && inode2 == NULL);
1101
1102         ret = mext_check_null_inode(inode1, inode2, __func__);
1103         if (ret < 0)
1104                 goto out;
1105
1106         if (inode1 == inode2) {
1107                 mutex_lock(&inode1->i_mutex);
1108                 goto out;
1109         }
1110
1111         if (inode1->i_ino < inode2->i_ino) {
1112                 mutex_lock_nested(&inode1->i_mutex, I_MUTEX_PARENT);
1113                 mutex_lock_nested(&inode2->i_mutex, I_MUTEX_CHILD);
1114         } else {
1115                 mutex_lock_nested(&inode2->i_mutex, I_MUTEX_PARENT);
1116                 mutex_lock_nested(&inode1->i_mutex, I_MUTEX_CHILD);
1117         }
1118
1119 out:
1120         return ret;
1121 }
1122
1123 /**
1124  * mext_inode_double_unlock - Release i_mutex on both @inode1 and @inode2
1125  *
1126  * @inode1:     the inode that is released first
1127  * @inode2:     the inode that is released second
1128  *
1129  * If inode1 or inode2 is NULL, return -EIO. Otherwise, return 0.
1130  */
1131
1132 static int
1133 mext_inode_double_unlock(struct inode *inode1, struct inode *inode2)
1134 {
1135         int ret = 0;
1136
1137         BUG_ON(inode1 == NULL && inode2 == NULL);
1138
1139         ret = mext_check_null_inode(inode1, inode2, __func__);
1140         if (ret < 0)
1141                 goto out;
1142
1143         if (inode1)
1144                 mutex_unlock(&inode1->i_mutex);
1145
1146         if (inode2 && inode2 != inode1)
1147                 mutex_unlock(&inode2->i_mutex);
1148
1149 out:
1150         return ret;
1151 }
1152
1153 /**
1154  * ext4_move_extents - Exchange the specified range of a file
1155  *
1156  * @o_filp:             file structure of the original file
1157  * @d_filp:             file structure of the donor file
1158  * @orig_start:         start offset in block for orig
1159  * @donor_start:        start offset in block for donor
1160  * @len:                the number of blocks to be moved
1161  * @moved_len:          moved block length
1162  *
1163  * This function returns 0 and moved block length is set in moved_len
1164  * if succeed, otherwise returns error value.
1165  *
1166  * Note: ext4_move_extents() proceeds the following order.
1167  * 1:ext4_move_extents() calculates the last block number of moving extent
1168  *   function by the start block number (orig_start) and the number of blocks
1169  *   to be moved (len) specified as arguments.
1170  *   If the {orig, donor}_start points a hole, the extent's start offset
1171  *   pointed by ext_cur (current extent), holecheck_path, orig_path are set
1172  *   after hole behind.
1173  * 2:Continue step 3 to step 5, until the holecheck_path points to last_extent
1174  *   or the ext_cur exceeds the block_end which is last logical block number.
1175  * 3:To get the length of continues area, call mext_next_extent()
1176  *   specified with the ext_cur (initial value is holecheck_path) re-cursive,
1177  *   until find un-continuous extent, the start logical block number exceeds
1178  *   the block_end or the extent points to the last extent.
1179  * 4:Exchange the original inode data with donor inode data
1180  *   from orig_page_offset to seq_end_page.
1181  *   The start indexes of data are specified as arguments.
1182  *   That of the original inode is orig_page_offset,
1183  *   and the donor inode is also orig_page_offset
1184  *   (To easily handle blocksize != pagesize case, the offset for the
1185  *   donor inode is block unit).
1186  * 5:Update holecheck_path and orig_path to points a next proceeding extent,
1187  *   then returns to step 2.
1188  * 6:Release holecheck_path, orig_path and set the len to moved_len
1189  *   which shows the number of moved blocks.
1190  *   The moved_len is useful for the command to calculate the file offset
1191  *   for starting next move extent ioctl.
1192  * 7:Return 0 on success, or a negative error value on failure.
1193  */
1194 int
1195 ext4_move_extents(struct file *o_filp, struct file *d_filp,
1196                  __u64 orig_start, __u64 donor_start, __u64 len,
1197                  __u64 *moved_len)
1198 {
1199         struct inode *orig_inode = o_filp->f_dentry->d_inode;
1200         struct inode *donor_inode = d_filp->f_dentry->d_inode;
1201         struct ext4_ext_path *orig_path = NULL, *holecheck_path = NULL;
1202         struct ext4_extent *ext_prev, *ext_cur, *ext_dummy;
1203         ext4_lblk_t block_start = orig_start;
1204         ext4_lblk_t block_end, seq_start, add_blocks, file_end, seq_blocks = 0;
1205         ext4_lblk_t rest_blocks;
1206         pgoff_t orig_page_offset = 0, seq_end_page;
1207         int ret1, ret2, depth, last_extent = 0;
1208         int blocks_per_page = PAGE_CACHE_SIZE >> orig_inode->i_blkbits;
1209         int data_offset_in_page;
1210         int block_len_in_page;
1211         int uninit;
1212
1213         /* protect orig and donor against a truncate */
1214         ret1 = mext_inode_double_lock(orig_inode, donor_inode);
1215         if (ret1 < 0)
1216                 return ret1;
1217
1218         mext_double_down_read(orig_inode, donor_inode);
1219         /* Check the filesystem environment whether move_extent can be done */
1220         ret1 = mext_check_arguments(orig_inode, donor_inode, orig_start,
1221                                         donor_start, &len, *moved_len);
1222         mext_double_up_read(orig_inode, donor_inode);
1223         if (ret1)
1224                 goto out2;
1225
1226         file_end = (i_size_read(orig_inode) - 1) >> orig_inode->i_blkbits;
1227         block_end = block_start + len - 1;
1228         if (file_end < block_end)
1229                 len -= block_end - file_end;
1230
1231         ret1 = get_ext_path(orig_inode, block_start, &orig_path);
1232         if (orig_path == NULL)
1233                 goto out2;
1234
1235         /* Get path structure to check the hole */
1236         ret1 = get_ext_path(orig_inode, block_start, &holecheck_path);
1237         if (holecheck_path == NULL)
1238                 goto out;
1239
1240         depth = ext_depth(orig_inode);
1241         ext_cur = holecheck_path[depth].p_ext;
1242         if (ext_cur == NULL) {
1243                 ret1 = -EINVAL;
1244                 goto out;
1245         }
1246
1247         /*
1248          * Get proper extent whose ee_block is beyond block_start
1249          * if block_start was within the hole.
1250          */
1251         if (le32_to_cpu(ext_cur->ee_block) +
1252                 ext4_ext_get_actual_len(ext_cur) - 1 < block_start) {
1253                 last_extent = mext_next_extent(orig_inode,
1254                                         holecheck_path, &ext_cur);
1255                 if (last_extent < 0) {
1256                         ret1 = last_extent;
1257                         goto out;
1258                 }
1259                 last_extent = mext_next_extent(orig_inode, orig_path,
1260                                                         &ext_dummy);
1261                 if (last_extent < 0) {
1262                         ret1 = last_extent;
1263                         goto out;
1264                 }
1265         }
1266         seq_start = block_start;
1267
1268         /* No blocks within the specified range. */
1269         if (le32_to_cpu(ext_cur->ee_block) > block_end) {
1270                 ext4_debug("ext4 move extent: The specified range of file "
1271                                                         "may be the hole\n");
1272                 ret1 = -EINVAL;
1273                 goto out;
1274         }
1275
1276         /* Adjust start blocks */
1277         add_blocks = min(le32_to_cpu(ext_cur->ee_block) +
1278                          ext4_ext_get_actual_len(ext_cur), block_end + 1) -
1279                      max(le32_to_cpu(ext_cur->ee_block), block_start);
1280
1281         while (!last_extent && le32_to_cpu(ext_cur->ee_block) <= block_end) {
1282                 seq_blocks += add_blocks;
1283
1284                 /* Adjust tail blocks */
1285                 if (seq_start + seq_blocks - 1 > block_end)
1286                         seq_blocks = block_end - seq_start + 1;
1287
1288                 ext_prev = ext_cur;
1289                 last_extent = mext_next_extent(orig_inode, holecheck_path,
1290                                                 &ext_cur);
1291                 if (last_extent < 0) {
1292                         ret1 = last_extent;
1293                         break;
1294                 }
1295                 add_blocks = ext4_ext_get_actual_len(ext_cur);
1296
1297                 /*
1298                  * Extend the length of contiguous block (seq_blocks)
1299                  * if extents are contiguous.
1300                  */
1301                 if (ext4_can_extents_be_merged(orig_inode,
1302                                                ext_prev, ext_cur) &&
1303                     block_end >= le32_to_cpu(ext_cur->ee_block) &&
1304                     !last_extent)
1305                         continue;
1306
1307                 /* Is original extent is uninitialized */
1308                 uninit = ext4_ext_is_uninitialized(ext_prev);
1309
1310                 data_offset_in_page = seq_start % blocks_per_page;
1311
1312                 /*
1313                  * Calculate data blocks count that should be swapped
1314                  * at the first page.
1315                  */
1316                 if (data_offset_in_page + seq_blocks > blocks_per_page) {
1317                         /* Swapped blocks are across pages */
1318                         block_len_in_page =
1319                                         blocks_per_page - data_offset_in_page;
1320                 } else {
1321                         /* Swapped blocks are in a page */
1322                         block_len_in_page = seq_blocks;
1323                 }
1324
1325                 orig_page_offset = seq_start >>
1326                                 (PAGE_CACHE_SHIFT - orig_inode->i_blkbits);
1327                 seq_end_page = (seq_start + seq_blocks - 1) >>
1328                                 (PAGE_CACHE_SHIFT - orig_inode->i_blkbits);
1329                 seq_start = le32_to_cpu(ext_cur->ee_block);
1330                 rest_blocks = seq_blocks;
1331
1332                 /* Discard preallocations of two inodes */
1333                 down_write(&EXT4_I(orig_inode)->i_data_sem);
1334                 ext4_discard_preallocations(orig_inode);
1335                 up_write(&EXT4_I(orig_inode)->i_data_sem);
1336
1337                 down_write(&EXT4_I(donor_inode)->i_data_sem);
1338                 ext4_discard_preallocations(donor_inode);
1339                 up_write(&EXT4_I(donor_inode)->i_data_sem);
1340
1341                 while (orig_page_offset <= seq_end_page) {
1342
1343                         /* Swap original branches with new branches */
1344                         ret1 = move_extent_per_page(o_filp, donor_inode,
1345                                                 orig_page_offset,
1346                                                 data_offset_in_page,
1347                                                 block_len_in_page, uninit);
1348                         if (ret1 < 0)
1349                                 goto out;
1350                         orig_page_offset++;
1351                         /* Count how many blocks we have exchanged */
1352                         *moved_len += block_len_in_page;
1353                         if (*moved_len > len) {
1354                                 ext4_error(orig_inode->i_sb, __func__,
1355                                         "We replaced blocks too much! "
1356                                         "sum of replaced: %llu requested: %llu",
1357                                         *moved_len, len);
1358                                 ret1 = -EIO;
1359                                 goto out;
1360                         }
1361
1362                         data_offset_in_page = 0;
1363                         rest_blocks -= block_len_in_page;
1364                         if (rest_blocks > blocks_per_page)
1365                                 block_len_in_page = blocks_per_page;
1366                         else
1367                                 block_len_in_page = rest_blocks;
1368                 }
1369
1370                 /* Decrease buffer counter */
1371                 if (holecheck_path)
1372                         ext4_ext_drop_refs(holecheck_path);
1373                 ret1 = get_ext_path(orig_inode, seq_start, &holecheck_path);
1374                 if (holecheck_path == NULL)
1375                         break;
1376                 depth = holecheck_path->p_depth;
1377
1378                 /* Decrease buffer counter */
1379                 if (orig_path)
1380                         ext4_ext_drop_refs(orig_path);
1381                 ret1 = get_ext_path(orig_inode, seq_start, &orig_path);
1382                 if (orig_path == NULL)
1383                         break;
1384
1385                 ext_cur = holecheck_path[depth].p_ext;
1386                 add_blocks = ext4_ext_get_actual_len(ext_cur);
1387                 seq_blocks = 0;
1388
1389         }
1390 out:
1391         if (orig_path) {
1392                 ext4_ext_drop_refs(orig_path);
1393                 kfree(orig_path);
1394         }
1395         if (holecheck_path) {
1396                 ext4_ext_drop_refs(holecheck_path);
1397                 kfree(holecheck_path);
1398         }
1399 out2:
1400         ret2 = mext_inode_double_unlock(orig_inode, donor_inode);
1401
1402         if (ret1)
1403                 return ret1;
1404         else if (ret2)
1405                 return ret2;
1406
1407         return 0;
1408 }