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