e3d65abb41b39359a3105cd2b1a6c03123001895
[pandora-kernel.git] / fs / ext4 / extents.c
1 /*
2  * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
3  * Written by Alex Tomas <alex@clusterfs.com>
4  *
5  * Architecture independence:
6  *   Copyright (c) 2005, Bull S.A.
7  *   Written by Pierre Peiffer <pierre.peiffer@bull.net>
8  *
9  * This program is free software; you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License version 2 as
11  * published by the Free Software Foundation.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public Licens
19  * along with this program; if not, write to the Free Software
20  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-
21  */
22
23 /*
24  * Extents support for EXT4
25  *
26  * TODO:
27  *   - ext4*_error() should be used in some situations
28  *   - analyze all BUG()/BUG_ON(), use -EIO where appropriate
29  *   - smart tree reduction
30  */
31
32 #include <linux/module.h>
33 #include <linux/fs.h>
34 #include <linux/time.h>
35 #include <linux/jbd2.h>
36 #include <linux/highuid.h>
37 #include <linux/pagemap.h>
38 #include <linux/quotaops.h>
39 #include <linux/string.h>
40 #include <linux/slab.h>
41 #include <linux/falloc.h>
42 #include <asm/uaccess.h>
43 #include <linux/fiemap.h>
44 #include "ext4_jbd2.h"
45
46 #include <trace/events/ext4.h>
47
48 /*
49  * used by extent splitting.
50  */
51 #define EXT4_EXT_MAY_ZEROOUT    0x1  /* safe to zeroout if split fails \
52                                         due to ENOSPC */
53 #define EXT4_EXT_MARK_UNINIT1   0x2  /* mark first half uninitialized */
54 #define EXT4_EXT_MARK_UNINIT2   0x4  /* mark second half uninitialized */
55
56 #define EXT4_EXT_DATA_VALID1    0x8  /* first half contains valid data */
57 #define EXT4_EXT_DATA_VALID2    0x10 /* second half contains valid data */
58
59 static int ext4_split_extent(handle_t *handle,
60                                 struct inode *inode,
61                                 struct ext4_ext_path *path,
62                                 struct ext4_map_blocks *map,
63                                 int split_flag,
64                                 int flags);
65
66 static int ext4_split_extent_at(handle_t *handle,
67                              struct inode *inode,
68                              struct ext4_ext_path *path,
69                              ext4_lblk_t split,
70                              int split_flag,
71                              int flags);
72
73 static int ext4_ext_truncate_extend_restart(handle_t *handle,
74                                             struct inode *inode,
75                                             int needed)
76 {
77         int err;
78
79         if (!ext4_handle_valid(handle))
80                 return 0;
81         if (handle->h_buffer_credits > needed)
82                 return 0;
83         err = ext4_journal_extend(handle, needed);
84         if (err <= 0)
85                 return err;
86         err = ext4_truncate_restart_trans(handle, inode, needed);
87         if (err == 0)
88                 err = -EAGAIN;
89
90         return err;
91 }
92
93 /*
94  * could return:
95  *  - EROFS
96  *  - ENOMEM
97  */
98 static int ext4_ext_get_access(handle_t *handle, struct inode *inode,
99                                 struct ext4_ext_path *path)
100 {
101         if (path->p_bh) {
102                 /* path points to block */
103                 return ext4_journal_get_write_access(handle, path->p_bh);
104         }
105         /* path points to leaf/index in inode body */
106         /* we use in-core data, no need to protect them */
107         return 0;
108 }
109
110 /*
111  * could return:
112  *  - EROFS
113  *  - ENOMEM
114  *  - EIO
115  */
116 #define ext4_ext_dirty(handle, inode, path) \
117                 __ext4_ext_dirty(__func__, __LINE__, (handle), (inode), (path))
118 static int __ext4_ext_dirty(const char *where, unsigned int line,
119                             handle_t *handle, struct inode *inode,
120                             struct ext4_ext_path *path)
121 {
122         int err;
123         if (path->p_bh) {
124                 /* path points to block */
125                 err = __ext4_handle_dirty_metadata(where, line, handle,
126                                                    inode, path->p_bh);
127         } else {
128                 /* path points to leaf/index in inode body */
129                 err = ext4_mark_inode_dirty(handle, inode);
130         }
131         return err;
132 }
133
134 static ext4_fsblk_t ext4_ext_find_goal(struct inode *inode,
135                               struct ext4_ext_path *path,
136                               ext4_lblk_t block)
137 {
138         if (path) {
139                 int depth = path->p_depth;
140                 struct ext4_extent *ex;
141
142                 /*
143                  * Try to predict block placement assuming that we are
144                  * filling in a file which will eventually be
145                  * non-sparse --- i.e., in the case of libbfd writing
146                  * an ELF object sections out-of-order but in a way
147                  * the eventually results in a contiguous object or
148                  * executable file, or some database extending a table
149                  * space file.  However, this is actually somewhat
150                  * non-ideal if we are writing a sparse file such as
151                  * qemu or KVM writing a raw image file that is going
152                  * to stay fairly sparse, since it will end up
153                  * fragmenting the file system's free space.  Maybe we
154                  * should have some hueristics or some way to allow
155                  * userspace to pass a hint to file system,
156                  * especially if the latter case turns out to be
157                  * common.
158                  */
159                 ex = path[depth].p_ext;
160                 if (ex) {
161                         ext4_fsblk_t ext_pblk = ext4_ext_pblock(ex);
162                         ext4_lblk_t ext_block = le32_to_cpu(ex->ee_block);
163
164                         if (block > ext_block)
165                                 return ext_pblk + (block - ext_block);
166                         else
167                                 return ext_pblk - (ext_block - block);
168                 }
169
170                 /* it looks like index is empty;
171                  * try to find starting block from index itself */
172                 if (path[depth].p_bh)
173                         return path[depth].p_bh->b_blocknr;
174         }
175
176         /* OK. use inode's group */
177         return ext4_inode_to_goal_block(inode);
178 }
179
180 /*
181  * Allocation for a meta data block
182  */
183 static ext4_fsblk_t
184 ext4_ext_new_meta_block(handle_t *handle, struct inode *inode,
185                         struct ext4_ext_path *path,
186                         struct ext4_extent *ex, int *err, unsigned int flags)
187 {
188         ext4_fsblk_t goal, newblock;
189
190         goal = ext4_ext_find_goal(inode, path, le32_to_cpu(ex->ee_block));
191         newblock = ext4_new_meta_blocks(handle, inode, goal, flags,
192                                         NULL, err);
193         return newblock;
194 }
195
196 static inline int ext4_ext_space_block(struct inode *inode, int check)
197 {
198         int size;
199
200         size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
201                         / sizeof(struct ext4_extent);
202 #ifdef AGGRESSIVE_TEST
203         if (!check && size > 6)
204                 size = 6;
205 #endif
206         return size;
207 }
208
209 static inline int ext4_ext_space_block_idx(struct inode *inode, int check)
210 {
211         int size;
212
213         size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
214                         / sizeof(struct ext4_extent_idx);
215 #ifdef AGGRESSIVE_TEST
216         if (!check && size > 5)
217                 size = 5;
218 #endif
219         return size;
220 }
221
222 static inline int ext4_ext_space_root(struct inode *inode, int check)
223 {
224         int size;
225
226         size = sizeof(EXT4_I(inode)->i_data);
227         size -= sizeof(struct ext4_extent_header);
228         size /= sizeof(struct ext4_extent);
229 #ifdef AGGRESSIVE_TEST
230         if (!check && size > 3)
231                 size = 3;
232 #endif
233         return size;
234 }
235
236 static inline int ext4_ext_space_root_idx(struct inode *inode, int check)
237 {
238         int size;
239
240         size = sizeof(EXT4_I(inode)->i_data);
241         size -= sizeof(struct ext4_extent_header);
242         size /= sizeof(struct ext4_extent_idx);
243 #ifdef AGGRESSIVE_TEST
244         if (!check && size > 4)
245                 size = 4;
246 #endif
247         return size;
248 }
249
250 /*
251  * Calculate the number of metadata blocks needed
252  * to allocate @blocks
253  * Worse case is one block per extent
254  */
255 int ext4_ext_calc_metadata_amount(struct inode *inode, ext4_lblk_t lblock)
256 {
257         struct ext4_inode_info *ei = EXT4_I(inode);
258         int idxs;
259
260         idxs = ((inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
261                 / sizeof(struct ext4_extent_idx));
262
263         /*
264          * If the new delayed allocation block is contiguous with the
265          * previous da block, it can share index blocks with the
266          * previous block, so we only need to allocate a new index
267          * block every idxs leaf blocks.  At ldxs**2 blocks, we need
268          * an additional index block, and at ldxs**3 blocks, yet
269          * another index blocks.
270          */
271         if (ei->i_da_metadata_calc_len &&
272             ei->i_da_metadata_calc_last_lblock+1 == lblock) {
273                 int num = 0;
274
275                 if ((ei->i_da_metadata_calc_len % idxs) == 0)
276                         num++;
277                 if ((ei->i_da_metadata_calc_len % (idxs*idxs)) == 0)
278                         num++;
279                 if ((ei->i_da_metadata_calc_len % (idxs*idxs*idxs)) == 0) {
280                         num++;
281                         ei->i_da_metadata_calc_len = 0;
282                 } else
283                         ei->i_da_metadata_calc_len++;
284                 ei->i_da_metadata_calc_last_lblock++;
285                 return num;
286         }
287
288         /*
289          * In the worst case we need a new set of index blocks at
290          * every level of the inode's extent tree.
291          */
292         ei->i_da_metadata_calc_len = 1;
293         ei->i_da_metadata_calc_last_lblock = lblock;
294         return ext_depth(inode) + 1;
295 }
296
297 static int
298 ext4_ext_max_entries(struct inode *inode, int depth)
299 {
300         int max;
301
302         if (depth == ext_depth(inode)) {
303                 if (depth == 0)
304                         max = ext4_ext_space_root(inode, 1);
305                 else
306                         max = ext4_ext_space_root_idx(inode, 1);
307         } else {
308                 if (depth == 0)
309                         max = ext4_ext_space_block(inode, 1);
310                 else
311                         max = ext4_ext_space_block_idx(inode, 1);
312         }
313
314         return max;
315 }
316
317 static int ext4_valid_extent(struct inode *inode, struct ext4_extent *ext)
318 {
319         ext4_fsblk_t block = ext4_ext_pblock(ext);
320         int len = ext4_ext_get_actual_len(ext);
321         ext4_lblk_t lblock = le32_to_cpu(ext->ee_block);
322         ext4_lblk_t last = lblock + len - 1;
323
324         if (len == 0 || lblock > last)
325                 return 0;
326         return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, len);
327 }
328
329 static int ext4_valid_extent_idx(struct inode *inode,
330                                 struct ext4_extent_idx *ext_idx)
331 {
332         ext4_fsblk_t block = ext4_idx_pblock(ext_idx);
333
334         return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, 1);
335 }
336
337 static int ext4_valid_extent_entries(struct inode *inode,
338                                 struct ext4_extent_header *eh,
339                                 int depth)
340 {
341         unsigned short entries;
342         if (eh->eh_entries == 0)
343                 return 1;
344
345         entries = le16_to_cpu(eh->eh_entries);
346
347         if (depth == 0) {
348                 /* leaf entries */
349                 struct ext4_extent *ext = EXT_FIRST_EXTENT(eh);
350                 struct ext4_super_block *es = EXT4_SB(inode->i_sb)->s_es;
351                 ext4_fsblk_t pblock = 0;
352                 ext4_lblk_t lblock = 0;
353                 ext4_lblk_t prev = 0;
354                 int len = 0;
355                 while (entries) {
356                         if (!ext4_valid_extent(inode, ext))
357                                 return 0;
358
359                         /* Check for overlapping extents */
360                         lblock = le32_to_cpu(ext->ee_block);
361                         len = ext4_ext_get_actual_len(ext);
362                         if ((lblock <= prev) && prev) {
363                                 pblock = ext4_ext_pblock(ext);
364                                 es->s_last_error_block = cpu_to_le64(pblock);
365                                 return 0;
366                         }
367                         ext++;
368                         entries--;
369                         prev = lblock + len - 1;
370                 }
371         } else {
372                 struct ext4_extent_idx *ext_idx = EXT_FIRST_INDEX(eh);
373                 while (entries) {
374                         if (!ext4_valid_extent_idx(inode, ext_idx))
375                                 return 0;
376                         ext_idx++;
377                         entries--;
378                 }
379         }
380         return 1;
381 }
382
383 static int __ext4_ext_check(const char *function, unsigned int line,
384                             struct inode *inode, struct ext4_extent_header *eh,
385                             int depth)
386 {
387         const char *error_msg;
388         int max = 0;
389
390         if (unlikely(eh->eh_magic != EXT4_EXT_MAGIC)) {
391                 error_msg = "invalid magic";
392                 goto corrupted;
393         }
394         if (unlikely(le16_to_cpu(eh->eh_depth) != depth)) {
395                 error_msg = "unexpected eh_depth";
396                 goto corrupted;
397         }
398         if (unlikely(eh->eh_max == 0)) {
399                 error_msg = "invalid eh_max";
400                 goto corrupted;
401         }
402         max = ext4_ext_max_entries(inode, depth);
403         if (unlikely(le16_to_cpu(eh->eh_max) > max)) {
404                 error_msg = "too large eh_max";
405                 goto corrupted;
406         }
407         if (unlikely(le16_to_cpu(eh->eh_entries) > le16_to_cpu(eh->eh_max))) {
408                 error_msg = "invalid eh_entries";
409                 goto corrupted;
410         }
411         if (!ext4_valid_extent_entries(inode, eh, depth)) {
412                 error_msg = "invalid extent entries";
413                 goto corrupted;
414         }
415         return 0;
416
417 corrupted:
418         ext4_error_inode(inode, function, line, 0,
419                         "bad header/extent: %s - magic %x, "
420                         "entries %u, max %u(%u), depth %u(%u)",
421                         error_msg, le16_to_cpu(eh->eh_magic),
422                         le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max),
423                         max, le16_to_cpu(eh->eh_depth), depth);
424
425         return -EIO;
426 }
427
428 #define ext4_ext_check(inode, eh, depth)        \
429         __ext4_ext_check(__func__, __LINE__, inode, eh, depth)
430
431 int ext4_ext_check_inode(struct inode *inode)
432 {
433         return ext4_ext_check(inode, ext_inode_hdr(inode), ext_depth(inode));
434 }
435
436 #ifdef EXT_DEBUG
437 static void ext4_ext_show_path(struct inode *inode, struct ext4_ext_path *path)
438 {
439         int k, l = path->p_depth;
440
441         ext_debug("path:");
442         for (k = 0; k <= l; k++, path++) {
443                 if (path->p_idx) {
444                   ext_debug("  %d->%llu", le32_to_cpu(path->p_idx->ei_block),
445                             ext4_idx_pblock(path->p_idx));
446                 } else if (path->p_ext) {
447                         ext_debug("  %d:[%d]%d:%llu ",
448                                   le32_to_cpu(path->p_ext->ee_block),
449                                   ext4_ext_is_uninitialized(path->p_ext),
450                                   ext4_ext_get_actual_len(path->p_ext),
451                                   ext4_ext_pblock(path->p_ext));
452                 } else
453                         ext_debug("  []");
454         }
455         ext_debug("\n");
456 }
457
458 static void ext4_ext_show_leaf(struct inode *inode, struct ext4_ext_path *path)
459 {
460         int depth = ext_depth(inode);
461         struct ext4_extent_header *eh;
462         struct ext4_extent *ex;
463         int i;
464
465         if (!path)
466                 return;
467
468         eh = path[depth].p_hdr;
469         ex = EXT_FIRST_EXTENT(eh);
470
471         ext_debug("Displaying leaf extents for inode %lu\n", inode->i_ino);
472
473         for (i = 0; i < le16_to_cpu(eh->eh_entries); i++, ex++) {
474                 ext_debug("%d:[%d]%d:%llu ", le32_to_cpu(ex->ee_block),
475                           ext4_ext_is_uninitialized(ex),
476                           ext4_ext_get_actual_len(ex), ext4_ext_pblock(ex));
477         }
478         ext_debug("\n");
479 }
480
481 static void ext4_ext_show_move(struct inode *inode, struct ext4_ext_path *path,
482                         ext4_fsblk_t newblock, int level)
483 {
484         int depth = ext_depth(inode);
485         struct ext4_extent *ex;
486
487         if (depth != level) {
488                 struct ext4_extent_idx *idx;
489                 idx = path[level].p_idx;
490                 while (idx <= EXT_MAX_INDEX(path[level].p_hdr)) {
491                         ext_debug("%d: move %d:%llu in new index %llu\n", level,
492                                         le32_to_cpu(idx->ei_block),
493                                         ext4_idx_pblock(idx),
494                                         newblock);
495                         idx++;
496                 }
497
498                 return;
499         }
500
501         ex = path[depth].p_ext;
502         while (ex <= EXT_MAX_EXTENT(path[depth].p_hdr)) {
503                 ext_debug("move %d:%llu:[%d]%d in new leaf %llu\n",
504                                 le32_to_cpu(ex->ee_block),
505                                 ext4_ext_pblock(ex),
506                                 ext4_ext_is_uninitialized(ex),
507                                 ext4_ext_get_actual_len(ex),
508                                 newblock);
509                 ex++;
510         }
511 }
512
513 #else
514 #define ext4_ext_show_path(inode, path)
515 #define ext4_ext_show_leaf(inode, path)
516 #define ext4_ext_show_move(inode, path, newblock, level)
517 #endif
518
519 void ext4_ext_drop_refs(struct ext4_ext_path *path)
520 {
521         int depth = path->p_depth;
522         int i;
523
524         for (i = 0; i <= depth; i++, path++)
525                 if (path->p_bh) {
526                         brelse(path->p_bh);
527                         path->p_bh = NULL;
528                 }
529 }
530
531 /*
532  * ext4_ext_binsearch_idx:
533  * binary search for the closest index of the given block
534  * the header must be checked before calling this
535  */
536 static void
537 ext4_ext_binsearch_idx(struct inode *inode,
538                         struct ext4_ext_path *path, ext4_lblk_t block)
539 {
540         struct ext4_extent_header *eh = path->p_hdr;
541         struct ext4_extent_idx *r, *l, *m;
542
543
544         ext_debug("binsearch for %u(idx):  ", block);
545
546         l = EXT_FIRST_INDEX(eh) + 1;
547         r = EXT_LAST_INDEX(eh);
548         while (l <= r) {
549                 m = l + (r - l) / 2;
550                 if (block < le32_to_cpu(m->ei_block))
551                         r = m - 1;
552                 else
553                         l = m + 1;
554                 ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ei_block),
555                                 m, le32_to_cpu(m->ei_block),
556                                 r, le32_to_cpu(r->ei_block));
557         }
558
559         path->p_idx = l - 1;
560         ext_debug("  -> %d->%lld ", le32_to_cpu(path->p_idx->ei_block),
561                   ext4_idx_pblock(path->p_idx));
562
563 #ifdef CHECK_BINSEARCH
564         {
565                 struct ext4_extent_idx *chix, *ix;
566                 int k;
567
568                 chix = ix = EXT_FIRST_INDEX(eh);
569                 for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ix++) {
570                   if (k != 0 &&
571                       le32_to_cpu(ix->ei_block) <= le32_to_cpu(ix[-1].ei_block)) {
572                                 printk(KERN_DEBUG "k=%d, ix=0x%p, "
573                                        "first=0x%p\n", k,
574                                        ix, EXT_FIRST_INDEX(eh));
575                                 printk(KERN_DEBUG "%u <= %u\n",
576                                        le32_to_cpu(ix->ei_block),
577                                        le32_to_cpu(ix[-1].ei_block));
578                         }
579                         BUG_ON(k && le32_to_cpu(ix->ei_block)
580                                            <= le32_to_cpu(ix[-1].ei_block));
581                         if (block < le32_to_cpu(ix->ei_block))
582                                 break;
583                         chix = ix;
584                 }
585                 BUG_ON(chix != path->p_idx);
586         }
587 #endif
588
589 }
590
591 /*
592  * ext4_ext_binsearch:
593  * binary search for closest extent of the given block
594  * the header must be checked before calling this
595  */
596 static void
597 ext4_ext_binsearch(struct inode *inode,
598                 struct ext4_ext_path *path, ext4_lblk_t block)
599 {
600         struct ext4_extent_header *eh = path->p_hdr;
601         struct ext4_extent *r, *l, *m;
602
603         if (eh->eh_entries == 0) {
604                 /*
605                  * this leaf is empty:
606                  * we get such a leaf in split/add case
607                  */
608                 return;
609         }
610
611         ext_debug("binsearch for %u:  ", block);
612
613         l = EXT_FIRST_EXTENT(eh) + 1;
614         r = EXT_LAST_EXTENT(eh);
615
616         while (l <= r) {
617                 m = l + (r - l) / 2;
618                 if (block < le32_to_cpu(m->ee_block))
619                         r = m - 1;
620                 else
621                         l = m + 1;
622                 ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ee_block),
623                                 m, le32_to_cpu(m->ee_block),
624                                 r, le32_to_cpu(r->ee_block));
625         }
626
627         path->p_ext = l - 1;
628         ext_debug("  -> %d:%llu:[%d]%d ",
629                         le32_to_cpu(path->p_ext->ee_block),
630                         ext4_ext_pblock(path->p_ext),
631                         ext4_ext_is_uninitialized(path->p_ext),
632                         ext4_ext_get_actual_len(path->p_ext));
633
634 #ifdef CHECK_BINSEARCH
635         {
636                 struct ext4_extent *chex, *ex;
637                 int k;
638
639                 chex = ex = EXT_FIRST_EXTENT(eh);
640                 for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ex++) {
641                         BUG_ON(k && le32_to_cpu(ex->ee_block)
642                                           <= le32_to_cpu(ex[-1].ee_block));
643                         if (block < le32_to_cpu(ex->ee_block))
644                                 break;
645                         chex = ex;
646                 }
647                 BUG_ON(chex != path->p_ext);
648         }
649 #endif
650
651 }
652
653 int ext4_ext_tree_init(handle_t *handle, struct inode *inode)
654 {
655         struct ext4_extent_header *eh;
656
657         eh = ext_inode_hdr(inode);
658         eh->eh_depth = 0;
659         eh->eh_entries = 0;
660         eh->eh_magic = EXT4_EXT_MAGIC;
661         eh->eh_max = cpu_to_le16(ext4_ext_space_root(inode, 0));
662         ext4_mark_inode_dirty(handle, inode);
663         ext4_ext_invalidate_cache(inode);
664         return 0;
665 }
666
667 struct ext4_ext_path *
668 ext4_ext_find_extent(struct inode *inode, ext4_lblk_t block,
669                                         struct ext4_ext_path *path)
670 {
671         struct ext4_extent_header *eh;
672         struct buffer_head *bh;
673         short int depth, i, ppos = 0, alloc = 0;
674         int ret;
675
676         eh = ext_inode_hdr(inode);
677         depth = ext_depth(inode);
678
679         /* account possible depth increase */
680         if (!path) {
681                 path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 2),
682                                 GFP_NOFS);
683                 if (!path)
684                         return ERR_PTR(-ENOMEM);
685                 alloc = 1;
686         }
687         path[0].p_hdr = eh;
688         path[0].p_bh = NULL;
689
690         i = depth;
691         /* walk through the tree */
692         while (i) {
693                 int need_to_validate = 0;
694
695                 ext_debug("depth %d: num %d, max %d\n",
696                           ppos, le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
697
698                 ext4_ext_binsearch_idx(inode, path + ppos, block);
699                 path[ppos].p_block = ext4_idx_pblock(path[ppos].p_idx);
700                 path[ppos].p_depth = i;
701                 path[ppos].p_ext = NULL;
702
703                 bh = sb_getblk_gfp(inode->i_sb, path[ppos].p_block,
704                                    __GFP_MOVABLE | GFP_NOFS);
705                 if (unlikely(!bh)) {
706                         ret = -ENOMEM;
707                         goto err;
708                 }
709                 if (!bh_uptodate_or_lock(bh)) {
710                         trace_ext4_ext_load_extent(inode, block,
711                                                 path[ppos].p_block);
712                         ret = bh_submit_read(bh);
713                         if (ret < 0) {
714                                 put_bh(bh);
715                                 goto err;
716                         }
717                         /* validate the extent entries */
718                         need_to_validate = 1;
719                 }
720                 eh = ext_block_hdr(bh);
721                 ppos++;
722                 if (unlikely(ppos > depth)) {
723                         put_bh(bh);
724                         EXT4_ERROR_INODE(inode,
725                                          "ppos %d > depth %d", ppos, depth);
726                         ret = -EIO;
727                         goto err;
728                 }
729                 path[ppos].p_bh = bh;
730                 path[ppos].p_hdr = eh;
731                 i--;
732
733                 ret = need_to_validate ? ext4_ext_check(inode, eh, i) : 0;
734                 if (ret < 0)
735                         goto err;
736         }
737
738         path[ppos].p_depth = i;
739         path[ppos].p_ext = NULL;
740         path[ppos].p_idx = NULL;
741
742         /* find extent */
743         ext4_ext_binsearch(inode, path + ppos, block);
744         /* if not an empty leaf */
745         if (path[ppos].p_ext)
746                 path[ppos].p_block = ext4_ext_pblock(path[ppos].p_ext);
747
748         ext4_ext_show_path(inode, path);
749
750         return path;
751
752 err:
753         ext4_ext_drop_refs(path);
754         if (alloc)
755                 kfree(path);
756         return ERR_PTR(ret);
757 }
758
759 /*
760  * ext4_ext_insert_index:
761  * insert new index [@logical;@ptr] into the block at @curp;
762  * check where to insert: before @curp or after @curp
763  */
764 static int ext4_ext_insert_index(handle_t *handle, struct inode *inode,
765                                  struct ext4_ext_path *curp,
766                                  int logical, ext4_fsblk_t ptr)
767 {
768         struct ext4_extent_idx *ix;
769         int len, err;
770
771         err = ext4_ext_get_access(handle, inode, curp);
772         if (err)
773                 return err;
774
775         if (unlikely(logical == le32_to_cpu(curp->p_idx->ei_block))) {
776                 EXT4_ERROR_INODE(inode,
777                                  "logical %d == ei_block %d!",
778                                  logical, le32_to_cpu(curp->p_idx->ei_block));
779                 return -EIO;
780         }
781
782         if (unlikely(le16_to_cpu(curp->p_hdr->eh_entries)
783                              >= le16_to_cpu(curp->p_hdr->eh_max))) {
784                 EXT4_ERROR_INODE(inode,
785                                  "eh_entries %d >= eh_max %d!",
786                                  le16_to_cpu(curp->p_hdr->eh_entries),
787                                  le16_to_cpu(curp->p_hdr->eh_max));
788                 return -EIO;
789         }
790
791         if (logical > le32_to_cpu(curp->p_idx->ei_block)) {
792                 /* insert after */
793                 ext_debug("insert new index %d after: %llu\n", logical, ptr);
794                 ix = curp->p_idx + 1;
795         } else {
796                 /* insert before */
797                 ext_debug("insert new index %d before: %llu\n", logical, ptr);
798                 ix = curp->p_idx;
799         }
800
801         len = EXT_LAST_INDEX(curp->p_hdr) - ix + 1;
802         BUG_ON(len < 0);
803         if (len > 0) {
804                 ext_debug("insert new index %d: "
805                                 "move %d indices from 0x%p to 0x%p\n",
806                                 logical, len, ix, ix + 1);
807                 memmove(ix + 1, ix, len * sizeof(struct ext4_extent_idx));
808         }
809
810         if (unlikely(ix > EXT_MAX_INDEX(curp->p_hdr))) {
811                 EXT4_ERROR_INODE(inode, "ix > EXT_MAX_INDEX!");
812                 return -EIO;
813         }
814
815         ix->ei_block = cpu_to_le32(logical);
816         ext4_idx_store_pblock(ix, ptr);
817         le16_add_cpu(&curp->p_hdr->eh_entries, 1);
818
819         if (unlikely(ix > EXT_LAST_INDEX(curp->p_hdr))) {
820                 EXT4_ERROR_INODE(inode, "ix > EXT_LAST_INDEX!");
821                 return -EIO;
822         }
823
824         err = ext4_ext_dirty(handle, inode, curp);
825         ext4_std_error(inode->i_sb, err);
826
827         return err;
828 }
829
830 /*
831  * ext4_ext_split:
832  * inserts new subtree into the path, using free index entry
833  * at depth @at:
834  * - allocates all needed blocks (new leaf and all intermediate index blocks)
835  * - makes decision where to split
836  * - moves remaining extents and index entries (right to the split point)
837  *   into the newly allocated blocks
838  * - initializes subtree
839  */
840 static int ext4_ext_split(handle_t *handle, struct inode *inode,
841                           unsigned int flags,
842                           struct ext4_ext_path *path,
843                           struct ext4_extent *newext, int at)
844 {
845         struct buffer_head *bh = NULL;
846         int depth = ext_depth(inode);
847         struct ext4_extent_header *neh;
848         struct ext4_extent_idx *fidx;
849         int i = at, k, m, a;
850         ext4_fsblk_t newblock, oldblock;
851         __le32 border;
852         ext4_fsblk_t *ablocks = NULL; /* array of allocated blocks */
853         int err = 0;
854
855         /* make decision: where to split? */
856         /* FIXME: now decision is simplest: at current extent */
857
858         /* if current leaf will be split, then we should use
859          * border from split point */
860         if (unlikely(path[depth].p_ext > EXT_MAX_EXTENT(path[depth].p_hdr))) {
861                 EXT4_ERROR_INODE(inode, "p_ext > EXT_MAX_EXTENT!");
862                 return -EIO;
863         }
864         if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr)) {
865                 border = path[depth].p_ext[1].ee_block;
866                 ext_debug("leaf will be split."
867                                 " next leaf starts at %d\n",
868                                   le32_to_cpu(border));
869         } else {
870                 border = newext->ee_block;
871                 ext_debug("leaf will be added."
872                                 " next leaf starts at %d\n",
873                                 le32_to_cpu(border));
874         }
875
876         /*
877          * If error occurs, then we break processing
878          * and mark filesystem read-only. index won't
879          * be inserted and tree will be in consistent
880          * state. Next mount will repair buffers too.
881          */
882
883         /*
884          * Get array to track all allocated blocks.
885          * We need this to handle errors and free blocks
886          * upon them.
887          */
888         ablocks = kzalloc(sizeof(ext4_fsblk_t) * depth, GFP_NOFS);
889         if (!ablocks)
890                 return -ENOMEM;
891
892         /* allocate all needed blocks */
893         ext_debug("allocate %d blocks for indexes/leaf\n", depth - at);
894         for (a = 0; a < depth - at; a++) {
895                 newblock = ext4_ext_new_meta_block(handle, inode, path,
896                                                    newext, &err, flags);
897                 if (newblock == 0)
898                         goto cleanup;
899                 ablocks[a] = newblock;
900         }
901
902         /* initialize new leaf */
903         newblock = ablocks[--a];
904         if (unlikely(newblock == 0)) {
905                 EXT4_ERROR_INODE(inode, "newblock == 0!");
906                 err = -EIO;
907                 goto cleanup;
908         }
909         bh = sb_getblk_gfp(inode->i_sb, newblock, __GFP_MOVABLE | GFP_NOFS);
910         if (!bh) {
911                 err = -ENOMEM;
912                 goto cleanup;
913         }
914         lock_buffer(bh);
915
916         err = ext4_journal_get_create_access(handle, bh);
917         if (err)
918                 goto cleanup;
919
920         neh = ext_block_hdr(bh);
921         neh->eh_entries = 0;
922         neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
923         neh->eh_magic = EXT4_EXT_MAGIC;
924         neh->eh_depth = 0;
925
926         /* move remainder of path[depth] to the new leaf */
927         if (unlikely(path[depth].p_hdr->eh_entries !=
928                      path[depth].p_hdr->eh_max)) {
929                 EXT4_ERROR_INODE(inode, "eh_entries %d != eh_max %d!",
930                                  path[depth].p_hdr->eh_entries,
931                                  path[depth].p_hdr->eh_max);
932                 err = -EIO;
933                 goto cleanup;
934         }
935         /* start copy from next extent */
936         m = EXT_MAX_EXTENT(path[depth].p_hdr) - path[depth].p_ext++;
937         ext4_ext_show_move(inode, path, newblock, depth);
938         if (m) {
939                 struct ext4_extent *ex;
940                 ex = EXT_FIRST_EXTENT(neh);
941                 memmove(ex, path[depth].p_ext, sizeof(struct ext4_extent) * m);
942                 le16_add_cpu(&neh->eh_entries, m);
943         }
944
945         set_buffer_uptodate(bh);
946         unlock_buffer(bh);
947
948         err = ext4_handle_dirty_metadata(handle, inode, bh);
949         if (err)
950                 goto cleanup;
951         brelse(bh);
952         bh = NULL;
953
954         /* correct old leaf */
955         if (m) {
956                 err = ext4_ext_get_access(handle, inode, path + depth);
957                 if (err)
958                         goto cleanup;
959                 le16_add_cpu(&path[depth].p_hdr->eh_entries, -m);
960                 err = ext4_ext_dirty(handle, inode, path + depth);
961                 if (err)
962                         goto cleanup;
963
964         }
965
966         /* create intermediate indexes */
967         k = depth - at - 1;
968         if (unlikely(k < 0)) {
969                 EXT4_ERROR_INODE(inode, "k %d < 0!", k);
970                 err = -EIO;
971                 goto cleanup;
972         }
973         if (k)
974                 ext_debug("create %d intermediate indices\n", k);
975         /* insert new index into current index block */
976         /* current depth stored in i var */
977         i = depth - 1;
978         while (k--) {
979                 oldblock = newblock;
980                 newblock = ablocks[--a];
981                 bh = sb_getblk(inode->i_sb, newblock);
982                 if (!bh) {
983                         err = -ENOMEM;
984                         goto cleanup;
985                 }
986                 lock_buffer(bh);
987
988                 err = ext4_journal_get_create_access(handle, bh);
989                 if (err)
990                         goto cleanup;
991
992                 neh = ext_block_hdr(bh);
993                 neh->eh_entries = cpu_to_le16(1);
994                 neh->eh_magic = EXT4_EXT_MAGIC;
995                 neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
996                 neh->eh_depth = cpu_to_le16(depth - i);
997                 fidx = EXT_FIRST_INDEX(neh);
998                 fidx->ei_block = border;
999                 ext4_idx_store_pblock(fidx, oldblock);
1000
1001                 ext_debug("int.index at %d (block %llu): %u -> %llu\n",
1002                                 i, newblock, le32_to_cpu(border), oldblock);
1003
1004                 /* move remainder of path[i] to the new index block */
1005                 if (unlikely(EXT_MAX_INDEX(path[i].p_hdr) !=
1006                                         EXT_LAST_INDEX(path[i].p_hdr))) {
1007                         EXT4_ERROR_INODE(inode,
1008                                          "EXT_MAX_INDEX != EXT_LAST_INDEX ee_block %d!",
1009                                          le32_to_cpu(path[i].p_ext->ee_block));
1010                         err = -EIO;
1011                         goto cleanup;
1012                 }
1013                 /* start copy indexes */
1014                 m = EXT_MAX_INDEX(path[i].p_hdr) - path[i].p_idx++;
1015                 ext_debug("cur 0x%p, last 0x%p\n", path[i].p_idx,
1016                                 EXT_MAX_INDEX(path[i].p_hdr));
1017                 ext4_ext_show_move(inode, path, newblock, i);
1018                 if (m) {
1019                         memmove(++fidx, path[i].p_idx,
1020                                 sizeof(struct ext4_extent_idx) * m);
1021                         le16_add_cpu(&neh->eh_entries, m);
1022                 }
1023                 set_buffer_uptodate(bh);
1024                 unlock_buffer(bh);
1025
1026                 err = ext4_handle_dirty_metadata(handle, inode, bh);
1027                 if (err)
1028                         goto cleanup;
1029                 brelse(bh);
1030                 bh = NULL;
1031
1032                 /* correct old index */
1033                 if (m) {
1034                         err = ext4_ext_get_access(handle, inode, path + i);
1035                         if (err)
1036                                 goto cleanup;
1037                         le16_add_cpu(&path[i].p_hdr->eh_entries, -m);
1038                         err = ext4_ext_dirty(handle, inode, path + i);
1039                         if (err)
1040                                 goto cleanup;
1041                 }
1042
1043                 i--;
1044         }
1045
1046         /* insert new index */
1047         err = ext4_ext_insert_index(handle, inode, path + at,
1048                                     le32_to_cpu(border), newblock);
1049
1050 cleanup:
1051         if (bh) {
1052                 if (buffer_locked(bh))
1053                         unlock_buffer(bh);
1054                 brelse(bh);
1055         }
1056
1057         if (err) {
1058                 /* free all allocated blocks in error case */
1059                 for (i = 0; i < depth; i++) {
1060                         if (!ablocks[i])
1061                                 continue;
1062                         ext4_free_blocks(handle, inode, NULL, ablocks[i], 1,
1063                                          EXT4_FREE_BLOCKS_METADATA);
1064                 }
1065         }
1066         kfree(ablocks);
1067
1068         return err;
1069 }
1070
1071 /*
1072  * ext4_ext_grow_indepth:
1073  * implements tree growing procedure:
1074  * - allocates new block
1075  * - moves top-level data (index block or leaf) into the new block
1076  * - initializes new top-level, creating index that points to the
1077  *   just created block
1078  */
1079 static int ext4_ext_grow_indepth(handle_t *handle, struct inode *inode,
1080                                  unsigned int flags,
1081                                  struct ext4_extent *newext)
1082 {
1083         struct ext4_extent_header *neh;
1084         struct buffer_head *bh;
1085         ext4_fsblk_t newblock;
1086         int err = 0;
1087
1088         newblock = ext4_ext_new_meta_block(handle, inode, NULL,
1089                 newext, &err, flags);
1090         if (newblock == 0)
1091                 return err;
1092
1093         bh = sb_getblk_gfp(inode->i_sb, newblock, __GFP_MOVABLE | GFP_NOFS);
1094         if (!bh)
1095                 return -ENOMEM;
1096         lock_buffer(bh);
1097
1098         err = ext4_journal_get_create_access(handle, bh);
1099         if (err) {
1100                 unlock_buffer(bh);
1101                 goto out;
1102         }
1103
1104         /* move top-level index/leaf into new block */
1105         memmove(bh->b_data, EXT4_I(inode)->i_data,
1106                 sizeof(EXT4_I(inode)->i_data));
1107
1108         /* set size of new block */
1109         neh = ext_block_hdr(bh);
1110         /* old root could have indexes or leaves
1111          * so calculate e_max right way */
1112         if (ext_depth(inode))
1113                 neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
1114         else
1115                 neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
1116         neh->eh_magic = EXT4_EXT_MAGIC;
1117         set_buffer_uptodate(bh);
1118         unlock_buffer(bh);
1119
1120         err = ext4_handle_dirty_metadata(handle, inode, bh);
1121         if (err)
1122                 goto out;
1123
1124         /* Update top-level index: num,max,pointer */
1125         neh = ext_inode_hdr(inode);
1126         neh->eh_entries = cpu_to_le16(1);
1127         ext4_idx_store_pblock(EXT_FIRST_INDEX(neh), newblock);
1128         if (neh->eh_depth == 0) {
1129                 /* Root extent block becomes index block */
1130                 neh->eh_max = cpu_to_le16(ext4_ext_space_root_idx(inode, 0));
1131                 EXT_FIRST_INDEX(neh)->ei_block =
1132                         EXT_FIRST_EXTENT(neh)->ee_block;
1133         }
1134         ext_debug("new root: num %d(%d), lblock %d, ptr %llu\n",
1135                   le16_to_cpu(neh->eh_entries), le16_to_cpu(neh->eh_max),
1136                   le32_to_cpu(EXT_FIRST_INDEX(neh)->ei_block),
1137                   ext4_idx_pblock(EXT_FIRST_INDEX(neh)));
1138
1139         neh->eh_depth = cpu_to_le16(le16_to_cpu(neh->eh_depth) + 1);
1140         ext4_mark_inode_dirty(handle, inode);
1141 out:
1142         brelse(bh);
1143
1144         return err;
1145 }
1146
1147 /*
1148  * ext4_ext_create_new_leaf:
1149  * finds empty index and adds new leaf.
1150  * if no free index is found, then it requests in-depth growing.
1151  */
1152 static int ext4_ext_create_new_leaf(handle_t *handle, struct inode *inode,
1153                                     unsigned int flags,
1154                                     struct ext4_ext_path *path,
1155                                     struct ext4_extent *newext)
1156 {
1157         struct ext4_ext_path *curp;
1158         int depth, i, err = 0;
1159
1160 repeat:
1161         i = depth = ext_depth(inode);
1162
1163         /* walk up to the tree and look for free index entry */
1164         curp = path + depth;
1165         while (i > 0 && !EXT_HAS_FREE_INDEX(curp)) {
1166                 i--;
1167                 curp--;
1168         }
1169
1170         /* we use already allocated block for index block,
1171          * so subsequent data blocks should be contiguous */
1172         if (EXT_HAS_FREE_INDEX(curp)) {
1173                 /* if we found index with free entry, then use that
1174                  * entry: create all needed subtree and add new leaf */
1175                 err = ext4_ext_split(handle, inode, flags, path, newext, i);
1176                 if (err)
1177                         goto out;
1178
1179                 /* refill path */
1180                 ext4_ext_drop_refs(path);
1181                 path = ext4_ext_find_extent(inode,
1182                                     (ext4_lblk_t)le32_to_cpu(newext->ee_block),
1183                                     path);
1184                 if (IS_ERR(path))
1185                         err = PTR_ERR(path);
1186         } else {
1187                 /* tree is full, time to grow in depth */
1188                 err = ext4_ext_grow_indepth(handle, inode, flags, newext);
1189                 if (err)
1190                         goto out;
1191
1192                 /* refill path */
1193                 ext4_ext_drop_refs(path);
1194                 path = ext4_ext_find_extent(inode,
1195                                    (ext4_lblk_t)le32_to_cpu(newext->ee_block),
1196                                     path);
1197                 if (IS_ERR(path)) {
1198                         err = PTR_ERR(path);
1199                         goto out;
1200                 }
1201
1202                 /*
1203                  * only first (depth 0 -> 1) produces free space;
1204                  * in all other cases we have to split the grown tree
1205                  */
1206                 depth = ext_depth(inode);
1207                 if (path[depth].p_hdr->eh_entries == path[depth].p_hdr->eh_max) {
1208                         /* now we need to split */
1209                         goto repeat;
1210                 }
1211         }
1212
1213 out:
1214         return err;
1215 }
1216
1217 /*
1218  * search the closest allocated block to the left for *logical
1219  * and returns it at @logical + it's physical address at @phys
1220  * if *logical is the smallest allocated block, the function
1221  * returns 0 at @phys
1222  * return value contains 0 (success) or error code
1223  */
1224 static int ext4_ext_search_left(struct inode *inode,
1225                                 struct ext4_ext_path *path,
1226                                 ext4_lblk_t *logical, ext4_fsblk_t *phys)
1227 {
1228         struct ext4_extent_idx *ix;
1229         struct ext4_extent *ex;
1230         int depth, ee_len;
1231
1232         if (unlikely(path == NULL)) {
1233                 EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
1234                 return -EIO;
1235         }
1236         depth = path->p_depth;
1237         *phys = 0;
1238
1239         if (depth == 0 && path->p_ext == NULL)
1240                 return 0;
1241
1242         /* usually extent in the path covers blocks smaller
1243          * then *logical, but it can be that extent is the
1244          * first one in the file */
1245
1246         ex = path[depth].p_ext;
1247         ee_len = ext4_ext_get_actual_len(ex);
1248         if (*logical < le32_to_cpu(ex->ee_block)) {
1249                 if (unlikely(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex)) {
1250                         EXT4_ERROR_INODE(inode,
1251                                          "EXT_FIRST_EXTENT != ex *logical %d ee_block %d!",
1252                                          *logical, le32_to_cpu(ex->ee_block));
1253                         return -EIO;
1254                 }
1255                 while (--depth >= 0) {
1256                         ix = path[depth].p_idx;
1257                         if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
1258                                 EXT4_ERROR_INODE(inode,
1259                                   "ix (%d) != EXT_FIRST_INDEX (%d) (depth %d)!",
1260                                   ix != NULL ? le32_to_cpu(ix->ei_block) : 0,
1261                                   EXT_FIRST_INDEX(path[depth].p_hdr) != NULL ?
1262                 le32_to_cpu(EXT_FIRST_INDEX(path[depth].p_hdr)->ei_block) : 0,
1263                                   depth);
1264                                 return -EIO;
1265                         }
1266                 }
1267                 return 0;
1268         }
1269
1270         if (unlikely(*logical < (le32_to_cpu(ex->ee_block) + ee_len))) {
1271                 EXT4_ERROR_INODE(inode,
1272                                  "logical %d < ee_block %d + ee_len %d!",
1273                                  *logical, le32_to_cpu(ex->ee_block), ee_len);
1274                 return -EIO;
1275         }
1276
1277         *logical = le32_to_cpu(ex->ee_block) + ee_len - 1;
1278         *phys = ext4_ext_pblock(ex) + ee_len - 1;
1279         return 0;
1280 }
1281
1282 /*
1283  * search the closest allocated block to the right for *logical
1284  * and returns it at @logical + it's physical address at @phys
1285  * if *logical is the largest allocated block, the function
1286  * returns 0 at @phys
1287  * return value contains 0 (success) or error code
1288  */
1289 static int ext4_ext_search_right(struct inode *inode,
1290                                  struct ext4_ext_path *path,
1291                                  ext4_lblk_t *logical, ext4_fsblk_t *phys,
1292                                  struct ext4_extent **ret_ex)
1293 {
1294         struct buffer_head *bh = NULL;
1295         struct ext4_extent_header *eh;
1296         struct ext4_extent_idx *ix;
1297         struct ext4_extent *ex;
1298         ext4_fsblk_t block;
1299         int depth;      /* Note, NOT eh_depth; depth from top of tree */
1300         int ee_len;
1301
1302         if (unlikely(path == NULL)) {
1303                 EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
1304                 return -EIO;
1305         }
1306         depth = path->p_depth;
1307         *phys = 0;
1308
1309         if (depth == 0 && path->p_ext == NULL)
1310                 return 0;
1311
1312         /* usually extent in the path covers blocks smaller
1313          * then *logical, but it can be that extent is the
1314          * first one in the file */
1315
1316         ex = path[depth].p_ext;
1317         ee_len = ext4_ext_get_actual_len(ex);
1318         if (*logical < le32_to_cpu(ex->ee_block)) {
1319                 if (unlikely(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex)) {
1320                         EXT4_ERROR_INODE(inode,
1321                                          "first_extent(path[%d].p_hdr) != ex",
1322                                          depth);
1323                         return -EIO;
1324                 }
1325                 while (--depth >= 0) {
1326                         ix = path[depth].p_idx;
1327                         if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
1328                                 EXT4_ERROR_INODE(inode,
1329                                                  "ix != EXT_FIRST_INDEX *logical %d!",
1330                                                  *logical);
1331                                 return -EIO;
1332                         }
1333                 }
1334                 goto found_extent;
1335         }
1336
1337         if (unlikely(*logical < (le32_to_cpu(ex->ee_block) + ee_len))) {
1338                 EXT4_ERROR_INODE(inode,
1339                                  "logical %d < ee_block %d + ee_len %d!",
1340                                  *logical, le32_to_cpu(ex->ee_block), ee_len);
1341                 return -EIO;
1342         }
1343
1344         if (ex != EXT_LAST_EXTENT(path[depth].p_hdr)) {
1345                 /* next allocated block in this leaf */
1346                 ex++;
1347                 goto found_extent;
1348         }
1349
1350         /* go up and search for index to the right */
1351         while (--depth >= 0) {
1352                 ix = path[depth].p_idx;
1353                 if (ix != EXT_LAST_INDEX(path[depth].p_hdr))
1354                         goto got_index;
1355         }
1356
1357         /* we've gone up to the root and found no index to the right */
1358         return 0;
1359
1360 got_index:
1361         /* we've found index to the right, let's
1362          * follow it and find the closest allocated
1363          * block to the right */
1364         ix++;
1365         block = ext4_idx_pblock(ix);
1366         while (++depth < path->p_depth) {
1367                 bh = sb_bread(inode->i_sb, block);
1368                 if (bh == NULL)
1369                         return -EIO;
1370                 eh = ext_block_hdr(bh);
1371                 /* subtract from p_depth to get proper eh_depth */
1372                 if (ext4_ext_check(inode, eh, path->p_depth - depth)) {
1373                         put_bh(bh);
1374                         return -EIO;
1375                 }
1376                 ix = EXT_FIRST_INDEX(eh);
1377                 block = ext4_idx_pblock(ix);
1378                 put_bh(bh);
1379         }
1380
1381         bh = sb_bread(inode->i_sb, block);
1382         if (bh == NULL)
1383                 return -EIO;
1384         eh = ext_block_hdr(bh);
1385         if (ext4_ext_check(inode, eh, path->p_depth - depth)) {
1386                 put_bh(bh);
1387                 return -EIO;
1388         }
1389         ex = EXT_FIRST_EXTENT(eh);
1390 found_extent:
1391         *logical = le32_to_cpu(ex->ee_block);
1392         *phys = ext4_ext_pblock(ex);
1393         *ret_ex = ex;
1394         if (bh)
1395                 put_bh(bh);
1396         return 0;
1397 }
1398
1399 /*
1400  * ext4_ext_next_allocated_block:
1401  * returns allocated block in subsequent extent or EXT_MAX_BLOCKS.
1402  * NOTE: it considers block number from index entry as
1403  * allocated block. Thus, index entries have to be consistent
1404  * with leaves.
1405  */
1406 static ext4_lblk_t
1407 ext4_ext_next_allocated_block(struct ext4_ext_path *path)
1408 {
1409         int depth;
1410
1411         BUG_ON(path == NULL);
1412         depth = path->p_depth;
1413
1414         if (depth == 0 && path->p_ext == NULL)
1415                 return EXT_MAX_BLOCKS;
1416
1417         while (depth >= 0) {
1418                 if (depth == path->p_depth) {
1419                         /* leaf */
1420                         if (path[depth].p_ext &&
1421                                 path[depth].p_ext !=
1422                                         EXT_LAST_EXTENT(path[depth].p_hdr))
1423                           return le32_to_cpu(path[depth].p_ext[1].ee_block);
1424                 } else {
1425                         /* index */
1426                         if (path[depth].p_idx !=
1427                                         EXT_LAST_INDEX(path[depth].p_hdr))
1428                           return le32_to_cpu(path[depth].p_idx[1].ei_block);
1429                 }
1430                 depth--;
1431         }
1432
1433         return EXT_MAX_BLOCKS;
1434 }
1435
1436 /*
1437  * ext4_ext_next_leaf_block:
1438  * returns first allocated block from next leaf or EXT_MAX_BLOCKS
1439  */
1440 static ext4_lblk_t ext4_ext_next_leaf_block(struct ext4_ext_path *path)
1441 {
1442         int depth;
1443
1444         BUG_ON(path == NULL);
1445         depth = path->p_depth;
1446
1447         /* zero-tree has no leaf blocks at all */
1448         if (depth == 0)
1449                 return EXT_MAX_BLOCKS;
1450
1451         /* go to index block */
1452         depth--;
1453
1454         while (depth >= 0) {
1455                 if (path[depth].p_idx !=
1456                                 EXT_LAST_INDEX(path[depth].p_hdr))
1457                         return (ext4_lblk_t)
1458                                 le32_to_cpu(path[depth].p_idx[1].ei_block);
1459                 depth--;
1460         }
1461
1462         return EXT_MAX_BLOCKS;
1463 }
1464
1465 /*
1466  * ext4_ext_correct_indexes:
1467  * if leaf gets modified and modified extent is first in the leaf,
1468  * then we have to correct all indexes above.
1469  * TODO: do we need to correct tree in all cases?
1470  */
1471 static int ext4_ext_correct_indexes(handle_t *handle, struct inode *inode,
1472                                 struct ext4_ext_path *path)
1473 {
1474         struct ext4_extent_header *eh;
1475         int depth = ext_depth(inode);
1476         struct ext4_extent *ex;
1477         __le32 border;
1478         int k, err = 0;
1479
1480         eh = path[depth].p_hdr;
1481         ex = path[depth].p_ext;
1482
1483         if (unlikely(ex == NULL || eh == NULL)) {
1484                 EXT4_ERROR_INODE(inode,
1485                                  "ex %p == NULL or eh %p == NULL", ex, eh);
1486                 return -EIO;
1487         }
1488
1489         if (depth == 0) {
1490                 /* there is no tree at all */
1491                 return 0;
1492         }
1493
1494         if (ex != EXT_FIRST_EXTENT(eh)) {
1495                 /* we correct tree if first leaf got modified only */
1496                 return 0;
1497         }
1498
1499         /*
1500          * TODO: we need correction if border is smaller than current one
1501          */
1502         k = depth - 1;
1503         border = path[depth].p_ext->ee_block;
1504         err = ext4_ext_get_access(handle, inode, path + k);
1505         if (err)
1506                 return err;
1507         path[k].p_idx->ei_block = border;
1508         err = ext4_ext_dirty(handle, inode, path + k);
1509         if (err)
1510                 return err;
1511
1512         while (k--) {
1513                 /* change all left-side indexes */
1514                 if (path[k+1].p_idx != EXT_FIRST_INDEX(path[k+1].p_hdr))
1515                         break;
1516                 err = ext4_ext_get_access(handle, inode, path + k);
1517                 if (err)
1518                         break;
1519                 path[k].p_idx->ei_block = border;
1520                 err = ext4_ext_dirty(handle, inode, path + k);
1521                 if (err)
1522                         break;
1523         }
1524
1525         return err;
1526 }
1527
1528 int
1529 ext4_can_extents_be_merged(struct inode *inode, struct ext4_extent *ex1,
1530                                 struct ext4_extent *ex2)
1531 {
1532         unsigned short ext1_ee_len, ext2_ee_len, max_len;
1533
1534         /*
1535          * Make sure that either both extents are uninitialized, or
1536          * both are _not_.
1537          */
1538         if (ext4_ext_is_uninitialized(ex1) ^ ext4_ext_is_uninitialized(ex2))
1539                 return 0;
1540
1541         if (ext4_ext_is_uninitialized(ex1))
1542                 max_len = EXT_UNINIT_MAX_LEN;
1543         else
1544                 max_len = EXT_INIT_MAX_LEN;
1545
1546         ext1_ee_len = ext4_ext_get_actual_len(ex1);
1547         ext2_ee_len = ext4_ext_get_actual_len(ex2);
1548
1549         if (le32_to_cpu(ex1->ee_block) + ext1_ee_len !=
1550                         le32_to_cpu(ex2->ee_block))
1551                 return 0;
1552
1553         /*
1554          * To allow future support for preallocated extents to be added
1555          * as an RO_COMPAT feature, refuse to merge to extents if
1556          * this can result in the top bit of ee_len being set.
1557          */
1558         if (ext1_ee_len + ext2_ee_len > max_len)
1559                 return 0;
1560 #ifdef AGGRESSIVE_TEST
1561         if (ext1_ee_len >= 4)
1562                 return 0;
1563 #endif
1564
1565         if (ext4_ext_pblock(ex1) + ext1_ee_len == ext4_ext_pblock(ex2))
1566                 return 1;
1567         return 0;
1568 }
1569
1570 /*
1571  * This function tries to merge the "ex" extent to the next extent in the tree.
1572  * It always tries to merge towards right. If you want to merge towards
1573  * left, pass "ex - 1" as argument instead of "ex".
1574  * Returns 0 if the extents (ex and ex+1) were _not_ merged and returns
1575  * 1 if they got merged.
1576  */
1577 static int ext4_ext_try_to_merge_right(struct inode *inode,
1578                                  struct ext4_ext_path *path,
1579                                  struct ext4_extent *ex)
1580 {
1581         struct ext4_extent_header *eh;
1582         unsigned int depth, len;
1583         int merge_done = 0;
1584         int uninitialized = 0;
1585
1586         depth = ext_depth(inode);
1587         BUG_ON(path[depth].p_hdr == NULL);
1588         eh = path[depth].p_hdr;
1589
1590         while (ex < EXT_LAST_EXTENT(eh)) {
1591                 if (!ext4_can_extents_be_merged(inode, ex, ex + 1))
1592                         break;
1593                 /* merge with next extent! */
1594                 if (ext4_ext_is_uninitialized(ex))
1595                         uninitialized = 1;
1596                 ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
1597                                 + ext4_ext_get_actual_len(ex + 1));
1598                 if (uninitialized)
1599                         ext4_ext_mark_uninitialized(ex);
1600
1601                 if (ex + 1 < EXT_LAST_EXTENT(eh)) {
1602                         len = (EXT_LAST_EXTENT(eh) - ex - 1)
1603                                 * sizeof(struct ext4_extent);
1604                         memmove(ex + 1, ex + 2, len);
1605                 }
1606                 le16_add_cpu(&eh->eh_entries, -1);
1607                 merge_done = 1;
1608                 WARN_ON(eh->eh_entries == 0);
1609                 if (!eh->eh_entries)
1610                         EXT4_ERROR_INODE(inode, "eh->eh_entries = 0!");
1611         }
1612
1613         return merge_done;
1614 }
1615
1616 /*
1617  * This function tries to merge the @ex extent to neighbours in the tree.
1618  * return 1 if merge left else 0.
1619  */
1620 static int ext4_ext_try_to_merge(struct inode *inode,
1621                                   struct ext4_ext_path *path,
1622                                   struct ext4_extent *ex) {
1623         struct ext4_extent_header *eh;
1624         unsigned int depth;
1625         int merge_done = 0;
1626         int ret = 0;
1627
1628         depth = ext_depth(inode);
1629         BUG_ON(path[depth].p_hdr == NULL);
1630         eh = path[depth].p_hdr;
1631
1632         if (ex > EXT_FIRST_EXTENT(eh))
1633                 merge_done = ext4_ext_try_to_merge_right(inode, path, ex - 1);
1634
1635         if (!merge_done)
1636                 ret = ext4_ext_try_to_merge_right(inode, path, ex);
1637
1638         return ret;
1639 }
1640
1641 /*
1642  * check if a portion of the "newext" extent overlaps with an
1643  * existing extent.
1644  *
1645  * If there is an overlap discovered, it updates the length of the newext
1646  * such that there will be no overlap, and then returns 1.
1647  * If there is no overlap found, it returns 0.
1648  */
1649 static unsigned int ext4_ext_check_overlap(struct ext4_sb_info *sbi,
1650                                            struct inode *inode,
1651                                            struct ext4_extent *newext,
1652                                            struct ext4_ext_path *path)
1653 {
1654         ext4_lblk_t b1, b2;
1655         unsigned int depth, len1;
1656         unsigned int ret = 0;
1657
1658         b1 = le32_to_cpu(newext->ee_block);
1659         len1 = ext4_ext_get_actual_len(newext);
1660         depth = ext_depth(inode);
1661         if (!path[depth].p_ext)
1662                 goto out;
1663         b2 = EXT4_LBLK_CMASK(sbi, le32_to_cpu(path[depth].p_ext->ee_block));
1664
1665         /*
1666          * get the next allocated block if the extent in the path
1667          * is before the requested block(s)
1668          */
1669         if (b2 < b1) {
1670                 b2 = ext4_ext_next_allocated_block(path);
1671                 if (b2 == EXT_MAX_BLOCKS)
1672                         goto out;
1673                 b2 = EXT4_LBLK_CMASK(sbi, b2);
1674         }
1675
1676         /* check for wrap through zero on extent logical start block*/
1677         if (b1 + len1 < b1) {
1678                 len1 = EXT_MAX_BLOCKS - b1;
1679                 newext->ee_len = cpu_to_le16(len1);
1680                 ret = 1;
1681         }
1682
1683         /* check for overlap */
1684         if (b1 + len1 > b2) {
1685                 newext->ee_len = cpu_to_le16(b2 - b1);
1686                 ret = 1;
1687         }
1688 out:
1689         return ret;
1690 }
1691
1692 /*
1693  * ext4_ext_insert_extent:
1694  * tries to merge requsted extent into the existing extent or
1695  * inserts requested extent as new one into the tree,
1696  * creating new leaf in the no-space case.
1697  */
1698 int ext4_ext_insert_extent(handle_t *handle, struct inode *inode,
1699                                 struct ext4_ext_path *path,
1700                                 struct ext4_extent *newext, int flag)
1701 {
1702         struct ext4_extent_header *eh;
1703         struct ext4_extent *ex, *fex;
1704         struct ext4_extent *nearex; /* nearest extent */
1705         struct ext4_ext_path *npath = NULL;
1706         int depth, len, err;
1707         ext4_lblk_t next;
1708         unsigned uninitialized = 0;
1709         int flags = 0;
1710
1711         if (unlikely(ext4_ext_get_actual_len(newext) == 0)) {
1712                 EXT4_ERROR_INODE(inode, "ext4_ext_get_actual_len(newext) == 0");
1713                 return -EIO;
1714         }
1715         depth = ext_depth(inode);
1716         ex = path[depth].p_ext;
1717         if (unlikely(path[depth].p_hdr == NULL)) {
1718                 EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
1719                 return -EIO;
1720         }
1721
1722         /* try to insert block into found extent and return */
1723         if (ex && !(flag & EXT4_GET_BLOCKS_PRE_IO)
1724                 && ext4_can_extents_be_merged(inode, ex, newext)) {
1725                 ext_debug("append [%d]%d block to %u:[%d]%d (from %llu)\n",
1726                           ext4_ext_is_uninitialized(newext),
1727                           ext4_ext_get_actual_len(newext),
1728                           le32_to_cpu(ex->ee_block),
1729                           ext4_ext_is_uninitialized(ex),
1730                           ext4_ext_get_actual_len(ex),
1731                           ext4_ext_pblock(ex));
1732                 err = ext4_ext_get_access(handle, inode, path + depth);
1733                 if (err)
1734                         return err;
1735
1736                 /*
1737                  * ext4_can_extents_be_merged should have checked that either
1738                  * both extents are uninitialized, or both aren't. Thus we
1739                  * need to check only one of them here.
1740                  */
1741                 if (ext4_ext_is_uninitialized(ex))
1742                         uninitialized = 1;
1743                 ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
1744                                         + ext4_ext_get_actual_len(newext));
1745                 if (uninitialized)
1746                         ext4_ext_mark_uninitialized(ex);
1747                 eh = path[depth].p_hdr;
1748                 nearex = ex;
1749                 goto merge;
1750         }
1751
1752         depth = ext_depth(inode);
1753         eh = path[depth].p_hdr;
1754         if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))
1755                 goto has_space;
1756
1757         /* probably next leaf has space for us? */
1758         fex = EXT_LAST_EXTENT(eh);
1759         next = EXT_MAX_BLOCKS;
1760         if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block))
1761                 next = ext4_ext_next_leaf_block(path);
1762         if (next != EXT_MAX_BLOCKS) {
1763                 ext_debug("next leaf block - %u\n", next);
1764                 BUG_ON(npath != NULL);
1765                 npath = ext4_ext_find_extent(inode, next, NULL);
1766                 if (IS_ERR(npath))
1767                         return PTR_ERR(npath);
1768                 BUG_ON(npath->p_depth != path->p_depth);
1769                 eh = npath[depth].p_hdr;
1770                 if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) {
1771                         ext_debug("next leaf isn't full(%d)\n",
1772                                   le16_to_cpu(eh->eh_entries));
1773                         path = npath;
1774                         goto has_space;
1775                 }
1776                 ext_debug("next leaf has no free space(%d,%d)\n",
1777                           le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
1778         }
1779
1780         /*
1781          * There is no free space in the found leaf.
1782          * We're gonna add a new leaf in the tree.
1783          */
1784         if (flag & EXT4_GET_BLOCKS_PUNCH_OUT_EXT)
1785                 flags = EXT4_MB_USE_ROOT_BLOCKS;
1786         err = ext4_ext_create_new_leaf(handle, inode, flags, path, newext);
1787         if (err)
1788                 goto cleanup;
1789         depth = ext_depth(inode);
1790         eh = path[depth].p_hdr;
1791
1792 has_space:
1793         nearex = path[depth].p_ext;
1794
1795         err = ext4_ext_get_access(handle, inode, path + depth);
1796         if (err)
1797                 goto cleanup;
1798
1799         if (!nearex) {
1800                 /* there is no extent in this leaf, create first one */
1801                 ext_debug("first extent in the leaf: %u:%llu:[%d]%d\n",
1802                                 le32_to_cpu(newext->ee_block),
1803                                 ext4_ext_pblock(newext),
1804                                 ext4_ext_is_uninitialized(newext),
1805                                 ext4_ext_get_actual_len(newext));
1806                 nearex = EXT_FIRST_EXTENT(eh);
1807         } else {
1808                 if (le32_to_cpu(newext->ee_block)
1809                            > le32_to_cpu(nearex->ee_block)) {
1810                         /* Insert after */
1811                         ext_debug("insert %u:%llu:[%d]%d before: "
1812                                         "nearest %p\n",
1813                                         le32_to_cpu(newext->ee_block),
1814                                         ext4_ext_pblock(newext),
1815                                         ext4_ext_is_uninitialized(newext),
1816                                         ext4_ext_get_actual_len(newext),
1817                                         nearex);
1818                         nearex++;
1819                 } else {
1820                         /* Insert before */
1821                         BUG_ON(newext->ee_block == nearex->ee_block);
1822                         ext_debug("insert %u:%llu:[%d]%d after: "
1823                                         "nearest %p\n",
1824                                         le32_to_cpu(newext->ee_block),
1825                                         ext4_ext_pblock(newext),
1826                                         ext4_ext_is_uninitialized(newext),
1827                                         ext4_ext_get_actual_len(newext),
1828                                         nearex);
1829                 }
1830                 len = EXT_LAST_EXTENT(eh) - nearex + 1;
1831                 if (len > 0) {
1832                         ext_debug("insert %u:%llu:[%d]%d: "
1833                                         "move %d extents from 0x%p to 0x%p\n",
1834                                         le32_to_cpu(newext->ee_block),
1835                                         ext4_ext_pblock(newext),
1836                                         ext4_ext_is_uninitialized(newext),
1837                                         ext4_ext_get_actual_len(newext),
1838                                         len, nearex, nearex + 1);
1839                         memmove(nearex + 1, nearex,
1840                                 len * sizeof(struct ext4_extent));
1841                 }
1842         }
1843
1844         le16_add_cpu(&eh->eh_entries, 1);
1845         path[depth].p_ext = nearex;
1846         nearex->ee_block = newext->ee_block;
1847         ext4_ext_store_pblock(nearex, ext4_ext_pblock(newext));
1848         nearex->ee_len = newext->ee_len;
1849
1850 merge:
1851         /* try to merge extents to the right */
1852         if (!(flag & EXT4_GET_BLOCKS_PRE_IO))
1853                 ext4_ext_try_to_merge(inode, path, nearex);
1854
1855         /* try to merge extents to the left */
1856
1857         /* time to correct all indexes above */
1858         err = ext4_ext_correct_indexes(handle, inode, path);
1859         if (err)
1860                 goto cleanup;
1861
1862         err = ext4_ext_dirty(handle, inode, path + depth);
1863
1864 cleanup:
1865         if (npath) {
1866                 ext4_ext_drop_refs(npath);
1867                 kfree(npath);
1868         }
1869         ext4_ext_invalidate_cache(inode);
1870         return err;
1871 }
1872
1873 static int ext4_ext_walk_space(struct inode *inode, ext4_lblk_t block,
1874                                ext4_lblk_t num, ext_prepare_callback func,
1875                                void *cbdata)
1876 {
1877         struct ext4_ext_path *path = NULL;
1878         struct ext4_ext_cache cbex;
1879         struct ext4_extent *ex;
1880         ext4_lblk_t next, start = 0, end = 0;
1881         ext4_lblk_t last = block + num;
1882         int depth, exists, err = 0;
1883
1884         BUG_ON(func == NULL);
1885         BUG_ON(inode == NULL);
1886
1887         while (block < last && block != EXT_MAX_BLOCKS) {
1888                 num = last - block;
1889                 /* find extent for this block */
1890                 down_read(&EXT4_I(inode)->i_data_sem);
1891                 path = ext4_ext_find_extent(inode, block, path);
1892                 up_read(&EXT4_I(inode)->i_data_sem);
1893                 if (IS_ERR(path)) {
1894                         err = PTR_ERR(path);
1895                         path = NULL;
1896                         break;
1897                 }
1898
1899                 depth = ext_depth(inode);
1900                 if (unlikely(path[depth].p_hdr == NULL)) {
1901                         EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
1902                         err = -EIO;
1903                         break;
1904                 }
1905                 ex = path[depth].p_ext;
1906                 next = ext4_ext_next_allocated_block(path);
1907
1908                 exists = 0;
1909                 if (!ex) {
1910                         /* there is no extent yet, so try to allocate
1911                          * all requested space */
1912                         start = block;
1913                         end = block + num;
1914                 } else if (le32_to_cpu(ex->ee_block) > block) {
1915                         /* need to allocate space before found extent */
1916                         start = block;
1917                         end = le32_to_cpu(ex->ee_block);
1918                         if (block + num < end)
1919                                 end = block + num;
1920                 } else if (block >= le32_to_cpu(ex->ee_block)
1921                                         + ext4_ext_get_actual_len(ex)) {
1922                         /* need to allocate space after found extent */
1923                         start = block;
1924                         end = block + num;
1925                         if (end >= next)
1926                                 end = next;
1927                 } else if (block >= le32_to_cpu(ex->ee_block)) {
1928                         /*
1929                          * some part of requested space is covered
1930                          * by found extent
1931                          */
1932                         start = block;
1933                         end = le32_to_cpu(ex->ee_block)
1934                                 + ext4_ext_get_actual_len(ex);
1935                         if (block + num < end)
1936                                 end = block + num;
1937                         exists = 1;
1938                 } else {
1939                         BUG();
1940                 }
1941                 BUG_ON(end <= start);
1942
1943                 if (!exists) {
1944                         cbex.ec_block = start;
1945                         cbex.ec_len = end - start;
1946                         cbex.ec_start = 0;
1947                 } else {
1948                         cbex.ec_block = le32_to_cpu(ex->ee_block);
1949                         cbex.ec_len = ext4_ext_get_actual_len(ex);
1950                         cbex.ec_start = ext4_ext_pblock(ex);
1951                 }
1952
1953                 if (unlikely(cbex.ec_len == 0)) {
1954                         EXT4_ERROR_INODE(inode, "cbex.ec_len == 0");
1955                         err = -EIO;
1956                         break;
1957                 }
1958                 err = func(inode, next, &cbex, ex, cbdata);
1959                 ext4_ext_drop_refs(path);
1960
1961                 if (err < 0)
1962                         break;
1963
1964                 if (err == EXT_REPEAT)
1965                         continue;
1966                 else if (err == EXT_BREAK) {
1967                         err = 0;
1968                         break;
1969                 }
1970
1971                 if (ext_depth(inode) != depth) {
1972                         /* depth was changed. we have to realloc path */
1973                         kfree(path);
1974                         path = NULL;
1975                 }
1976
1977                 block = cbex.ec_block + cbex.ec_len;
1978         }
1979
1980         if (path) {
1981                 ext4_ext_drop_refs(path);
1982                 kfree(path);
1983         }
1984
1985         return err;
1986 }
1987
1988 static void
1989 ext4_ext_put_in_cache(struct inode *inode, ext4_lblk_t block,
1990                         __u32 len, ext4_fsblk_t start)
1991 {
1992         struct ext4_ext_cache *cex;
1993         BUG_ON(len == 0);
1994         spin_lock(&EXT4_I(inode)->i_block_reservation_lock);
1995         trace_ext4_ext_put_in_cache(inode, block, len, start);
1996         cex = &EXT4_I(inode)->i_cached_extent;
1997         cex->ec_block = block;
1998         cex->ec_len = len;
1999         cex->ec_start = start;
2000         spin_unlock(&EXT4_I(inode)->i_block_reservation_lock);
2001 }
2002
2003 /*
2004  * ext4_ext_put_gap_in_cache:
2005  * calculate boundaries of the gap that the requested block fits into
2006  * and cache this gap
2007  */
2008 static void
2009 ext4_ext_put_gap_in_cache(struct inode *inode, struct ext4_ext_path *path,
2010                                 ext4_lblk_t block)
2011 {
2012         int depth = ext_depth(inode);
2013         unsigned long len;
2014         ext4_lblk_t lblock;
2015         struct ext4_extent *ex;
2016
2017         ex = path[depth].p_ext;
2018         if (ex == NULL) {
2019                 /* there is no extent yet, so gap is [0;-] */
2020                 lblock = 0;
2021                 len = EXT_MAX_BLOCKS;
2022                 ext_debug("cache gap(whole file):");
2023         } else if (block < le32_to_cpu(ex->ee_block)) {
2024                 lblock = block;
2025                 len = le32_to_cpu(ex->ee_block) - block;
2026                 ext_debug("cache gap(before): %u [%u:%u]",
2027                                 block,
2028                                 le32_to_cpu(ex->ee_block),
2029                                  ext4_ext_get_actual_len(ex));
2030         } else if (block >= le32_to_cpu(ex->ee_block)
2031                         + ext4_ext_get_actual_len(ex)) {
2032                 ext4_lblk_t next;
2033                 lblock = le32_to_cpu(ex->ee_block)
2034                         + ext4_ext_get_actual_len(ex);
2035
2036                 next = ext4_ext_next_allocated_block(path);
2037                 ext_debug("cache gap(after): [%u:%u] %u",
2038                                 le32_to_cpu(ex->ee_block),
2039                                 ext4_ext_get_actual_len(ex),
2040                                 block);
2041                 BUG_ON(next == lblock);
2042                 len = next - lblock;
2043         } else {
2044                 lblock = len = 0;
2045                 BUG();
2046         }
2047
2048         ext_debug(" -> %u:%lu\n", lblock, len);
2049         ext4_ext_put_in_cache(inode, lblock, len, 0);
2050 }
2051
2052 /*
2053  * ext4_ext_check_cache()
2054  * Checks to see if the given block is in the cache.
2055  * If it is, the cached extent is stored in the given
2056  * cache extent pointer.  If the cached extent is a hole,
2057  * this routine should be used instead of
2058  * ext4_ext_in_cache if the calling function needs to
2059  * know the size of the hole.
2060  *
2061  * @inode: The files inode
2062  * @block: The block to look for in the cache
2063  * @ex:    Pointer where the cached extent will be stored
2064  *         if it contains block
2065  *
2066  * Return 0 if cache is invalid; 1 if the cache is valid
2067  */
2068 static int ext4_ext_check_cache(struct inode *inode, ext4_lblk_t block,
2069         struct ext4_ext_cache *ex){
2070         struct ext4_ext_cache *cex;
2071         struct ext4_sb_info *sbi;
2072         int ret = 0;
2073
2074         /*
2075          * We borrow i_block_reservation_lock to protect i_cached_extent
2076          */
2077         spin_lock(&EXT4_I(inode)->i_block_reservation_lock);
2078         cex = &EXT4_I(inode)->i_cached_extent;
2079         sbi = EXT4_SB(inode->i_sb);
2080
2081         /* has cache valid data? */
2082         if (cex->ec_len == 0)
2083                 goto errout;
2084
2085         if (in_range(block, cex->ec_block, cex->ec_len)) {
2086                 memcpy(ex, cex, sizeof(struct ext4_ext_cache));
2087                 ext_debug("%u cached by %u:%u:%llu\n",
2088                                 block,
2089                                 cex->ec_block, cex->ec_len, cex->ec_start);
2090                 ret = 1;
2091         }
2092 errout:
2093         trace_ext4_ext_in_cache(inode, block, ret);
2094         spin_unlock(&EXT4_I(inode)->i_block_reservation_lock);
2095         return ret;
2096 }
2097
2098 /*
2099  * ext4_ext_in_cache()
2100  * Checks to see if the given block is in the cache.
2101  * If it is, the cached extent is stored in the given
2102  * extent pointer.
2103  *
2104  * @inode: The files inode
2105  * @block: The block to look for in the cache
2106  * @ex:    Pointer where the cached extent will be stored
2107  *         if it contains block
2108  *
2109  * Return 0 if cache is invalid; 1 if the cache is valid
2110  */
2111 static int
2112 ext4_ext_in_cache(struct inode *inode, ext4_lblk_t block,
2113                         struct ext4_extent *ex)
2114 {
2115         struct ext4_ext_cache cex;
2116         int ret = 0;
2117
2118         if (ext4_ext_check_cache(inode, block, &cex)) {
2119                 ex->ee_block = cpu_to_le32(cex.ec_block);
2120                 ext4_ext_store_pblock(ex, cex.ec_start);
2121                 ex->ee_len = cpu_to_le16(cex.ec_len);
2122                 ret = 1;
2123         }
2124
2125         return ret;
2126 }
2127
2128
2129 /*
2130  * ext4_ext_rm_idx:
2131  * removes index from the index block.
2132  */
2133 static int ext4_ext_rm_idx(handle_t *handle, struct inode *inode,
2134                         struct ext4_ext_path *path, int depth)
2135 {
2136         int err;
2137         ext4_fsblk_t leaf;
2138
2139         /* free index block */
2140         depth--;
2141         path = path + depth;
2142         leaf = ext4_idx_pblock(path->p_idx);
2143         if (unlikely(path->p_hdr->eh_entries == 0)) {
2144                 EXT4_ERROR_INODE(inode, "path->p_hdr->eh_entries == 0");
2145                 return -EIO;
2146         }
2147         err = ext4_ext_get_access(handle, inode, path);
2148         if (err)
2149                 return err;
2150
2151         if (path->p_idx != EXT_LAST_INDEX(path->p_hdr)) {
2152                 int len = EXT_LAST_INDEX(path->p_hdr) - path->p_idx;
2153                 len *= sizeof(struct ext4_extent_idx);
2154                 memmove(path->p_idx, path->p_idx + 1, len);
2155         }
2156
2157         le16_add_cpu(&path->p_hdr->eh_entries, -1);
2158         err = ext4_ext_dirty(handle, inode, path);
2159         if (err)
2160                 return err;
2161         ext_debug("index is empty, remove it, free block %llu\n", leaf);
2162         trace_ext4_ext_rm_idx(inode, leaf);
2163
2164         ext4_free_blocks(handle, inode, NULL, leaf, 1,
2165                          EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET);
2166
2167         while (--depth >= 0) {
2168                 if (path->p_idx != EXT_FIRST_INDEX(path->p_hdr))
2169                         break;
2170                 path--;
2171                 err = ext4_ext_get_access(handle, inode, path);
2172                 if (err)
2173                         break;
2174                 path->p_idx->ei_block = (path+1)->p_idx->ei_block;
2175                 err = ext4_ext_dirty(handle, inode, path);
2176                 if (err)
2177                         break;
2178         }
2179         return err;
2180 }
2181
2182 /*
2183  * ext4_ext_calc_credits_for_single_extent:
2184  * This routine returns max. credits that needed to insert an extent
2185  * to the extent tree.
2186  * When pass the actual path, the caller should calculate credits
2187  * under i_data_sem.
2188  */
2189 int ext4_ext_calc_credits_for_single_extent(struct inode *inode, int nrblocks,
2190                                                 struct ext4_ext_path *path)
2191 {
2192         if (path) {
2193                 int depth = ext_depth(inode);
2194                 int ret = 0;
2195
2196                 /* probably there is space in leaf? */
2197                 if (le16_to_cpu(path[depth].p_hdr->eh_entries)
2198                                 < le16_to_cpu(path[depth].p_hdr->eh_max)) {
2199
2200                         /*
2201                          *  There are some space in the leaf tree, no
2202                          *  need to account for leaf block credit
2203                          *
2204                          *  bitmaps and block group descriptor blocks
2205                          *  and other metadata blocks still need to be
2206                          *  accounted.
2207                          */
2208                         /* 1 bitmap, 1 block group descriptor */
2209                         ret = 2 + EXT4_META_TRANS_BLOCKS(inode->i_sb);
2210                         return ret;
2211                 }
2212         }
2213
2214         return ext4_chunk_trans_blocks(inode, nrblocks);
2215 }
2216
2217 /*
2218  * How many index/leaf blocks need to change/allocate to modify nrblocks?
2219  *
2220  * if nrblocks are fit in a single extent (chunk flag is 1), then
2221  * in the worse case, each tree level index/leaf need to be changed
2222  * if the tree split due to insert a new extent, then the old tree
2223  * index/leaf need to be updated too
2224  *
2225  * If the nrblocks are discontiguous, they could cause
2226  * the whole tree split more than once, but this is really rare.
2227  */
2228 int ext4_ext_index_trans_blocks(struct inode *inode, int nrblocks, int chunk)
2229 {
2230         int index;
2231         int depth = ext_depth(inode);
2232
2233         if (chunk)
2234                 index = depth * 2;
2235         else
2236                 index = depth * 3;
2237
2238         return index;
2239 }
2240
2241 static int ext4_remove_blocks(handle_t *handle, struct inode *inode,
2242                               struct ext4_extent *ex,
2243                               ext4_fsblk_t *partial_cluster,
2244                               ext4_lblk_t from, ext4_lblk_t to)
2245 {
2246         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2247         unsigned short ee_len =  ext4_ext_get_actual_len(ex);
2248         ext4_fsblk_t pblk;
2249         int flags = EXT4_FREE_BLOCKS_FORGET;
2250
2251         if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode))
2252                 flags |= EXT4_FREE_BLOCKS_METADATA;
2253         /*
2254          * For bigalloc file systems, we never free a partial cluster
2255          * at the beginning of the extent.  Instead, we make a note
2256          * that we tried freeing the cluster, and check to see if we
2257          * need to free it on a subsequent call to ext4_remove_blocks,
2258          * or at the end of the ext4_truncate() operation.
2259          */
2260         flags |= EXT4_FREE_BLOCKS_NOFREE_FIRST_CLUSTER;
2261
2262         trace_ext4_remove_blocks(inode, ex, from, to, *partial_cluster);
2263         /*
2264          * If we have a partial cluster, and it's different from the
2265          * cluster of the last block, we need to explicitly free the
2266          * partial cluster here.
2267          */
2268         pblk = ext4_ext_pblock(ex) + ee_len - 1;
2269         if (*partial_cluster && (EXT4_B2C(sbi, pblk) != *partial_cluster)) {
2270                 ext4_free_blocks(handle, inode, NULL,
2271                                  EXT4_C2B(sbi, *partial_cluster),
2272                                  sbi->s_cluster_ratio, flags);
2273                 *partial_cluster = 0;
2274         }
2275
2276 #ifdef EXTENTS_STATS
2277         {
2278                 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2279                 spin_lock(&sbi->s_ext_stats_lock);
2280                 sbi->s_ext_blocks += ee_len;
2281                 sbi->s_ext_extents++;
2282                 if (ee_len < sbi->s_ext_min)
2283                         sbi->s_ext_min = ee_len;
2284                 if (ee_len > sbi->s_ext_max)
2285                         sbi->s_ext_max = ee_len;
2286                 if (ext_depth(inode) > sbi->s_depth_max)
2287                         sbi->s_depth_max = ext_depth(inode);
2288                 spin_unlock(&sbi->s_ext_stats_lock);
2289         }
2290 #endif
2291         if (from >= le32_to_cpu(ex->ee_block)
2292             && to == le32_to_cpu(ex->ee_block) + ee_len - 1) {
2293                 /* tail removal */
2294                 ext4_lblk_t num;
2295
2296                 num = le32_to_cpu(ex->ee_block) + ee_len - from;
2297                 pblk = ext4_ext_pblock(ex) + ee_len - num;
2298                 ext_debug("free last %u blocks starting %llu\n", num, pblk);
2299                 ext4_free_blocks(handle, inode, NULL, pblk, num, flags);
2300                 /*
2301                  * If the block range to be freed didn't start at the
2302                  * beginning of a cluster, and we removed the entire
2303                  * extent, save the partial cluster here, since we
2304                  * might need to delete if we determine that the
2305                  * truncate operation has removed all of the blocks in
2306                  * the cluster.
2307                  */
2308                 if (EXT4_PBLK_COFF(sbi, pblk) &&
2309                     (ee_len == num))
2310                         *partial_cluster = EXT4_B2C(sbi, pblk);
2311                 else
2312                         *partial_cluster = 0;
2313         } else if (from == le32_to_cpu(ex->ee_block)
2314                    && to <= le32_to_cpu(ex->ee_block) + ee_len - 1) {
2315                 /* head removal */
2316                 ext4_lblk_t num;
2317                 ext4_fsblk_t start;
2318
2319                 num = to - from;
2320                 start = ext4_ext_pblock(ex);
2321
2322                 ext_debug("free first %u blocks starting %llu\n", num, start);
2323                 ext4_free_blocks(handle, inode, NULL, start, num, flags);
2324
2325         } else {
2326                 printk(KERN_INFO "strange request: removal(2) "
2327                                 "%u-%u from %u:%u\n",
2328                                 from, to, le32_to_cpu(ex->ee_block), ee_len);
2329         }
2330         return 0;
2331 }
2332
2333
2334 /*
2335  * ext4_ext_rm_leaf() Removes the extents associated with the
2336  * blocks appearing between "start" and "end", and splits the extents
2337  * if "start" and "end" appear in the same extent
2338  *
2339  * @handle: The journal handle
2340  * @inode:  The files inode
2341  * @path:   The path to the leaf
2342  * @start:  The first block to remove
2343  * @end:   The last block to remove
2344  */
2345 static int
2346 ext4_ext_rm_leaf(handle_t *handle, struct inode *inode,
2347                  struct ext4_ext_path *path, ext4_fsblk_t *partial_cluster,
2348                  ext4_lblk_t start, ext4_lblk_t end)
2349 {
2350         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2351         int err = 0, correct_index = 0;
2352         int depth = ext_depth(inode), credits;
2353         struct ext4_extent_header *eh;
2354         ext4_lblk_t a, b;
2355         unsigned num;
2356         ext4_lblk_t ex_ee_block;
2357         unsigned short ex_ee_len;
2358         unsigned uninitialized = 0;
2359         struct ext4_extent *ex;
2360
2361         /* the header must be checked already in ext4_ext_remove_space() */
2362         ext_debug("truncate since %u in leaf to %u\n", start, end);
2363         if (!path[depth].p_hdr)
2364                 path[depth].p_hdr = ext_block_hdr(path[depth].p_bh);
2365         eh = path[depth].p_hdr;
2366         if (unlikely(path[depth].p_hdr == NULL)) {
2367                 EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
2368                 return -EIO;
2369         }
2370         /* find where to start removing */
2371         ex = EXT_LAST_EXTENT(eh);
2372
2373         ex_ee_block = le32_to_cpu(ex->ee_block);
2374         ex_ee_len = ext4_ext_get_actual_len(ex);
2375
2376         /*
2377          * If we're starting with an extent other than the last one in the
2378          * node, we need to see if it shares a cluster with the extent to
2379          * the right (towards the end of the file). If its leftmost cluster
2380          * is this extent's rightmost cluster and it is not cluster aligned,
2381          * we'll mark it as a partial that is not to be deallocated.
2382          */
2383
2384         if (ex != EXT_LAST_EXTENT(eh)) {
2385                 ext4_fsblk_t current_pblk, right_pblk;
2386                 long long current_cluster, right_cluster;
2387
2388                 current_pblk = ext4_ext_pblock(ex) + ex_ee_len - 1;
2389                 current_cluster = (long long)EXT4_B2C(sbi, current_pblk);
2390                 right_pblk = ext4_ext_pblock(ex + 1);
2391                 right_cluster = (long long)EXT4_B2C(sbi, right_pblk);
2392                 if (current_cluster == right_cluster &&
2393                         EXT4_PBLK_COFF(sbi, right_pblk))
2394                         *partial_cluster = -right_cluster;
2395         }
2396
2397         trace_ext4_ext_rm_leaf(inode, start, ex, *partial_cluster);
2398
2399         while (ex >= EXT_FIRST_EXTENT(eh) &&
2400                         ex_ee_block + ex_ee_len > start) {
2401
2402                 if (ext4_ext_is_uninitialized(ex))
2403                         uninitialized = 1;
2404                 else
2405                         uninitialized = 0;
2406
2407                 ext_debug("remove ext %u:[%d]%d\n", ex_ee_block,
2408                          uninitialized, ex_ee_len);
2409                 path[depth].p_ext = ex;
2410
2411                 a = ex_ee_block > start ? ex_ee_block : start;
2412                 b = ex_ee_block+ex_ee_len - 1 < end ?
2413                         ex_ee_block+ex_ee_len - 1 : end;
2414
2415                 ext_debug("  border %u:%u\n", a, b);
2416
2417                 /* If this extent is beyond the end of the hole, skip it */
2418                 if (end < ex_ee_block) {
2419                         ex--;
2420                         ex_ee_block = le32_to_cpu(ex->ee_block);
2421                         ex_ee_len = ext4_ext_get_actual_len(ex);
2422                         continue;
2423                 } else if (b != ex_ee_block + ex_ee_len - 1) {
2424                         EXT4_ERROR_INODE(inode,"  bad truncate %u:%u\n",
2425                                          start, end);
2426                         err = -EIO;
2427                         goto out;
2428                 } else if (a != ex_ee_block) {
2429                         /* remove tail of the extent */
2430                         num = a - ex_ee_block;
2431                 } else {
2432                         /* remove whole extent: excellent! */
2433                         num = 0;
2434                 }
2435                 /*
2436                  * 3 for leaf, sb, and inode plus 2 (bmap and group
2437                  * descriptor) for each block group; assume two block
2438                  * groups plus ex_ee_len/blocks_per_block_group for
2439                  * the worst case
2440                  */
2441                 credits = 7 + 2*(ex_ee_len/EXT4_BLOCKS_PER_GROUP(inode->i_sb));
2442                 if (ex == EXT_FIRST_EXTENT(eh)) {
2443                         correct_index = 1;
2444                         credits += (ext_depth(inode)) + 1;
2445                 }
2446                 credits += EXT4_MAXQUOTAS_TRANS_BLOCKS(inode->i_sb);
2447
2448                 err = ext4_ext_truncate_extend_restart(handle, inode, credits);
2449                 if (err)
2450                         goto out;
2451
2452                 err = ext4_ext_get_access(handle, inode, path + depth);
2453                 if (err)
2454                         goto out;
2455
2456                 err = ext4_remove_blocks(handle, inode, ex, partial_cluster,
2457                                          a, b);
2458                 if (err)
2459                         goto out;
2460
2461                 if (num == 0)
2462                         /* this extent is removed; mark slot entirely unused */
2463                         ext4_ext_store_pblock(ex, 0);
2464
2465                 ex->ee_len = cpu_to_le16(num);
2466                 /*
2467                  * Do not mark uninitialized if all the blocks in the
2468                  * extent have been removed.
2469                  */
2470                 if (uninitialized && num)
2471                         ext4_ext_mark_uninitialized(ex);
2472                 /*
2473                  * If the extent was completely released,
2474                  * we need to remove it from the leaf
2475                  */
2476                 if (num == 0) {
2477                         if (end != EXT_MAX_BLOCKS - 1) {
2478                                 /*
2479                                  * For hole punching, we need to scoot all the
2480                                  * extents up when an extent is removed so that
2481                                  * we dont have blank extents in the middle
2482                                  */
2483                                 memmove(ex, ex+1, (EXT_LAST_EXTENT(eh) - ex) *
2484                                         sizeof(struct ext4_extent));
2485
2486                                 /* Now get rid of the one at the end */
2487                                 memset(EXT_LAST_EXTENT(eh), 0,
2488                                         sizeof(struct ext4_extent));
2489                         }
2490                         le16_add_cpu(&eh->eh_entries, -1);
2491                 } else
2492                         *partial_cluster = 0;
2493
2494                 err = ext4_ext_dirty(handle, inode, path + depth);
2495                 if (err)
2496                         goto out;
2497
2498                 ext_debug("new extent: %u:%u:%llu\n", ex_ee_block, num,
2499                                 ext4_ext_pblock(ex));
2500                 ex--;
2501                 ex_ee_block = le32_to_cpu(ex->ee_block);
2502                 ex_ee_len = ext4_ext_get_actual_len(ex);
2503         }
2504
2505         if (correct_index && eh->eh_entries)
2506                 err = ext4_ext_correct_indexes(handle, inode, path);
2507
2508         /*
2509          * If there is still a entry in the leaf node, check to see if
2510          * it references the partial cluster.  This is the only place
2511          * where it could; if it doesn't, we can free the cluster.
2512          */
2513         if (*partial_cluster && ex >= EXT_FIRST_EXTENT(eh) &&
2514             (EXT4_B2C(sbi, ext4_ext_pblock(ex) + ex_ee_len - 1) !=
2515              *partial_cluster)) {
2516                 int flags = EXT4_FREE_BLOCKS_FORGET;
2517
2518                 if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode))
2519                         flags |= EXT4_FREE_BLOCKS_METADATA;
2520
2521                 ext4_free_blocks(handle, inode, NULL,
2522                                  EXT4_C2B(sbi, *partial_cluster),
2523                                  sbi->s_cluster_ratio, flags);
2524                 *partial_cluster = 0;
2525         }
2526
2527         /* if this leaf is free, then we should
2528          * remove it from index block above */
2529         if (err == 0 && eh->eh_entries == 0 && path[depth].p_bh != NULL)
2530                 err = ext4_ext_rm_idx(handle, inode, path, depth);
2531
2532 out:
2533         return err;
2534 }
2535
2536 /*
2537  * ext4_ext_more_to_rm:
2538  * returns 1 if current index has to be freed (even partial)
2539  */
2540 static int
2541 ext4_ext_more_to_rm(struct ext4_ext_path *path)
2542 {
2543         BUG_ON(path->p_idx == NULL);
2544
2545         if (path->p_idx < EXT_FIRST_INDEX(path->p_hdr))
2546                 return 0;
2547
2548         /*
2549          * if truncate on deeper level happened, it wasn't partial,
2550          * so we have to consider current index for truncation
2551          */
2552         if (le16_to_cpu(path->p_hdr->eh_entries) == path->p_block)
2553                 return 0;
2554         return 1;
2555 }
2556
2557 static int ext4_ext_remove_space(struct inode *inode, ext4_lblk_t start,
2558                                  ext4_lblk_t end)
2559 {
2560         struct super_block *sb = inode->i_sb;
2561         int depth = ext_depth(inode);
2562         struct ext4_ext_path *path = NULL;
2563         ext4_fsblk_t partial_cluster = 0;
2564         handle_t *handle;
2565         int i = 0, err;
2566
2567         ext_debug("truncate since %u to %u\n", start, end);
2568
2569         /* probably first extent we're gonna free will be last in block */
2570         handle = ext4_journal_start(inode, depth + 1);
2571         if (IS_ERR(handle))
2572                 return PTR_ERR(handle);
2573
2574 again:
2575         ext4_ext_invalidate_cache(inode);
2576
2577         trace_ext4_ext_remove_space(inode, start, depth);
2578
2579         /*
2580          * Check if we are removing extents inside the extent tree. If that
2581          * is the case, we are going to punch a hole inside the extent tree
2582          * so we have to check whether we need to split the extent covering
2583          * the last block to remove so we can easily remove the part of it
2584          * in ext4_ext_rm_leaf().
2585          */
2586         if (end < EXT_MAX_BLOCKS - 1) {
2587                 struct ext4_extent *ex;
2588                 ext4_lblk_t ee_block;
2589
2590                 /* find extent for this block */
2591                 path = ext4_ext_find_extent(inode, end, NULL);
2592                 if (IS_ERR(path)) {
2593                         ext4_journal_stop(handle);
2594                         return PTR_ERR(path);
2595                 }
2596                 depth = ext_depth(inode);
2597                 ex = path[depth].p_ext;
2598                 if (!ex) {
2599                         ext4_ext_drop_refs(path);
2600                         kfree(path);
2601                         path = NULL;
2602                         goto cont;
2603                 }
2604
2605                 ee_block = le32_to_cpu(ex->ee_block);
2606
2607                 /*
2608                  * See if the last block is inside the extent, if so split
2609                  * the extent at 'end' block so we can easily remove the
2610                  * tail of the first part of the split extent in
2611                  * ext4_ext_rm_leaf().
2612                  */
2613                 if (end >= ee_block &&
2614                     end < ee_block + ext4_ext_get_actual_len(ex) - 1) {
2615                         int split_flag = 0;
2616
2617                         if (ext4_ext_is_uninitialized(ex))
2618                                 split_flag = EXT4_EXT_MARK_UNINIT1 |
2619                                              EXT4_EXT_MARK_UNINIT2;
2620
2621                         /*
2622                          * Split the extent in two so that 'end' is the last
2623                          * block in the first new extent
2624                          */
2625                         err = ext4_split_extent_at(handle, inode, path,
2626                                                 end + 1, split_flag,
2627                                                 EXT4_GET_BLOCKS_PRE_IO |
2628                                                 EXT4_GET_BLOCKS_PUNCH_OUT_EXT);
2629
2630                         if (err < 0)
2631                                 goto out;
2632                 }
2633         }
2634 cont:
2635
2636         /*
2637          * We start scanning from right side, freeing all the blocks
2638          * after i_size and walking into the tree depth-wise.
2639          */
2640         depth = ext_depth(inode);
2641         if (path) {
2642                 int k = i = depth;
2643                 while (--k > 0)
2644                         path[k].p_block =
2645                                 le16_to_cpu(path[k].p_hdr->eh_entries)+1;
2646         } else {
2647                 path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 1),
2648                                GFP_NOFS);
2649                 if (path == NULL) {
2650                         ext4_journal_stop(handle);
2651                         return -ENOMEM;
2652                 }
2653                 path[0].p_depth = depth;
2654                 path[0].p_hdr = ext_inode_hdr(inode);
2655                 i = 0;
2656
2657                 if (ext4_ext_check(inode, path[0].p_hdr, depth)) {
2658                         err = -EIO;
2659                         goto out;
2660                 }
2661         }
2662         err = 0;
2663
2664         while (i >= 0 && err == 0) {
2665                 if (i == depth) {
2666                         /* this is leaf block */
2667                         err = ext4_ext_rm_leaf(handle, inode, path,
2668                                                &partial_cluster, start,
2669                                                end);
2670                         /* root level has p_bh == NULL, brelse() eats this */
2671                         brelse(path[i].p_bh);
2672                         path[i].p_bh = NULL;
2673                         i--;
2674                         continue;
2675                 }
2676
2677                 /* this is index block */
2678                 if (!path[i].p_hdr) {
2679                         ext_debug("initialize header\n");
2680                         path[i].p_hdr = ext_block_hdr(path[i].p_bh);
2681                 }
2682
2683                 if (!path[i].p_idx) {
2684                         /* this level hasn't been touched yet */
2685                         path[i].p_idx = EXT_LAST_INDEX(path[i].p_hdr);
2686                         path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries)+1;
2687                         ext_debug("init index ptr: hdr 0x%p, num %d\n",
2688                                   path[i].p_hdr,
2689                                   le16_to_cpu(path[i].p_hdr->eh_entries));
2690                 } else {
2691                         /* we were already here, see at next index */
2692                         path[i].p_idx--;
2693                 }
2694
2695                 ext_debug("level %d - index, first 0x%p, cur 0x%p\n",
2696                                 i, EXT_FIRST_INDEX(path[i].p_hdr),
2697                                 path[i].p_idx);
2698                 if (ext4_ext_more_to_rm(path + i)) {
2699                         struct buffer_head *bh;
2700                         /* go to the next level */
2701                         ext_debug("move to level %d (block %llu)\n",
2702                                   i + 1, ext4_idx_pblock(path[i].p_idx));
2703                         memset(path + i + 1, 0, sizeof(*path));
2704                         bh = sb_bread(sb, ext4_idx_pblock(path[i].p_idx));
2705                         if (!bh) {
2706                                 /* should we reset i_size? */
2707                                 err = -EIO;
2708                                 break;
2709                         }
2710                         if (WARN_ON(i + 1 > depth)) {
2711                                 err = -EIO;
2712                                 break;
2713                         }
2714                         if (ext4_ext_check(inode, ext_block_hdr(bh),
2715                                                         depth - i - 1)) {
2716                                 err = -EIO;
2717                                 break;
2718                         }
2719                         path[i + 1].p_bh = bh;
2720
2721                         /* save actual number of indexes since this
2722                          * number is changed at the next iteration */
2723                         path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries);
2724                         i++;
2725                 } else {
2726                         /* we finished processing this index, go up */
2727                         if (path[i].p_hdr->eh_entries == 0 && i > 0) {
2728                                 /* index is empty, remove it;
2729                                  * handle must be already prepared by the
2730                                  * truncatei_leaf() */
2731                                 err = ext4_ext_rm_idx(handle, inode, path, i);
2732                         }
2733                         /* root level has p_bh == NULL, brelse() eats this */
2734                         brelse(path[i].p_bh);
2735                         path[i].p_bh = NULL;
2736                         i--;
2737                         ext_debug("return to level %d\n", i);
2738                 }
2739         }
2740
2741         trace_ext4_ext_remove_space_done(inode, start, depth, partial_cluster,
2742                         path->p_hdr->eh_entries);
2743
2744         /* If we still have something in the partial cluster and we have removed
2745          * even the first extent, then we should free the blocks in the partial
2746          * cluster as well. */
2747         if (partial_cluster && path->p_hdr->eh_entries == 0) {
2748                 int flags = EXT4_FREE_BLOCKS_FORGET;
2749
2750                 if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode))
2751                         flags |= EXT4_FREE_BLOCKS_METADATA;
2752
2753                 ext4_free_blocks(handle, inode, NULL,
2754                                  EXT4_C2B(EXT4_SB(sb), partial_cluster),
2755                                  EXT4_SB(sb)->s_cluster_ratio, flags);
2756                 partial_cluster = 0;
2757         }
2758
2759         /* TODO: flexible tree reduction should be here */
2760         if (path->p_hdr->eh_entries == 0) {
2761                 /*
2762                  * truncate to zero freed all the tree,
2763                  * so we need to correct eh_depth
2764                  */
2765                 err = ext4_ext_get_access(handle, inode, path);
2766                 if (err == 0) {
2767                         ext_inode_hdr(inode)->eh_depth = 0;
2768                         ext_inode_hdr(inode)->eh_max =
2769                                 cpu_to_le16(ext4_ext_space_root(inode, 0));
2770                         err = ext4_ext_dirty(handle, inode, path);
2771                 }
2772         }
2773 out:
2774         ext4_ext_drop_refs(path);
2775         kfree(path);
2776         if (err == -EAGAIN) {
2777                 path = NULL;
2778                 goto again;
2779         }
2780         ext4_journal_stop(handle);
2781
2782         return err;
2783 }
2784
2785 /*
2786  * called at mount time
2787  */
2788 void ext4_ext_init(struct super_block *sb)
2789 {
2790         /*
2791          * possible initialization would be here
2792          */
2793
2794         if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS)) {
2795 #if defined(AGGRESSIVE_TEST) || defined(CHECK_BINSEARCH) || defined(EXTENTS_STATS)
2796                 printk(KERN_INFO "EXT4-fs: file extents enabled");
2797 #ifdef AGGRESSIVE_TEST
2798                 printk(", aggressive tests");
2799 #endif
2800 #ifdef CHECK_BINSEARCH
2801                 printk(", check binsearch");
2802 #endif
2803 #ifdef EXTENTS_STATS
2804                 printk(", stats");
2805 #endif
2806                 printk("\n");
2807 #endif
2808 #ifdef EXTENTS_STATS
2809                 spin_lock_init(&EXT4_SB(sb)->s_ext_stats_lock);
2810                 EXT4_SB(sb)->s_ext_min = 1 << 30;
2811                 EXT4_SB(sb)->s_ext_max = 0;
2812 #endif
2813         }
2814 }
2815
2816 /*
2817  * called at umount time
2818  */
2819 void ext4_ext_release(struct super_block *sb)
2820 {
2821         if (!EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS))
2822                 return;
2823
2824 #ifdef EXTENTS_STATS
2825         if (EXT4_SB(sb)->s_ext_blocks && EXT4_SB(sb)->s_ext_extents) {
2826                 struct ext4_sb_info *sbi = EXT4_SB(sb);
2827                 printk(KERN_ERR "EXT4-fs: %lu blocks in %lu extents (%lu ave)\n",
2828                         sbi->s_ext_blocks, sbi->s_ext_extents,
2829                         sbi->s_ext_blocks / sbi->s_ext_extents);
2830                 printk(KERN_ERR "EXT4-fs: extents: %lu min, %lu max, max depth %lu\n",
2831                         sbi->s_ext_min, sbi->s_ext_max, sbi->s_depth_max);
2832         }
2833 #endif
2834 }
2835
2836 /* FIXME!! we need to try to merge to left or right after zero-out  */
2837 static int ext4_ext_zeroout(struct inode *inode, struct ext4_extent *ex)
2838 {
2839         ext4_fsblk_t ee_pblock;
2840         unsigned int ee_len;
2841         int ret;
2842
2843         ee_len    = ext4_ext_get_actual_len(ex);
2844         ee_pblock = ext4_ext_pblock(ex);
2845
2846         ret = sb_issue_zeroout(inode->i_sb, ee_pblock, ee_len, GFP_NOFS);
2847         if (ret > 0)
2848                 ret = 0;
2849
2850         return ret;
2851 }
2852
2853 /*
2854  * ext4_split_extent_at() splits an extent at given block.
2855  *
2856  * @handle: the journal handle
2857  * @inode: the file inode
2858  * @path: the path to the extent
2859  * @split: the logical block where the extent is splitted.
2860  * @split_flags: indicates if the extent could be zeroout if split fails, and
2861  *               the states(init or uninit) of new extents.
2862  * @flags: flags used to insert new extent to extent tree.
2863  *
2864  *
2865  * Splits extent [a, b] into two extents [a, @split) and [@split, b], states
2866  * of which are deterimined by split_flag.
2867  *
2868  * There are two cases:
2869  *  a> the extent are splitted into two extent.
2870  *  b> split is not needed, and just mark the extent.
2871  *
2872  * return 0 on success.
2873  */
2874 static int ext4_split_extent_at(handle_t *handle,
2875                              struct inode *inode,
2876                              struct ext4_ext_path *path,
2877                              ext4_lblk_t split,
2878                              int split_flag,
2879                              int flags)
2880 {
2881         ext4_fsblk_t newblock;
2882         ext4_lblk_t ee_block;
2883         struct ext4_extent *ex, newex, orig_ex;
2884         struct ext4_extent *ex2 = NULL;
2885         unsigned int ee_len, depth;
2886         int err = 0;
2887
2888         BUG_ON((split_flag & (EXT4_EXT_DATA_VALID1 | EXT4_EXT_DATA_VALID2)) ==
2889                (EXT4_EXT_DATA_VALID1 | EXT4_EXT_DATA_VALID2));
2890
2891         ext_debug("ext4_split_extents_at: inode %lu, logical"
2892                 "block %llu\n", inode->i_ino, (unsigned long long)split);
2893
2894         ext4_ext_show_leaf(inode, path);
2895
2896         depth = ext_depth(inode);
2897         ex = path[depth].p_ext;
2898         ee_block = le32_to_cpu(ex->ee_block);
2899         ee_len = ext4_ext_get_actual_len(ex);
2900         newblock = split - ee_block + ext4_ext_pblock(ex);
2901
2902         BUG_ON(split < ee_block || split >= (ee_block + ee_len));
2903
2904         err = ext4_ext_get_access(handle, inode, path + depth);
2905         if (err)
2906                 goto out;
2907
2908         if (split == ee_block) {
2909                 /*
2910                  * case b: block @split is the block that the extent begins with
2911                  * then we just change the state of the extent, and splitting
2912                  * is not needed.
2913                  */
2914                 if (split_flag & EXT4_EXT_MARK_UNINIT2)
2915                         ext4_ext_mark_uninitialized(ex);
2916                 else
2917                         ext4_ext_mark_initialized(ex);
2918
2919                 if (!(flags & EXT4_GET_BLOCKS_PRE_IO))
2920                         ext4_ext_try_to_merge(inode, path, ex);
2921
2922                 err = ext4_ext_dirty(handle, inode, path + depth);
2923                 goto out;
2924         }
2925
2926         /* case a */
2927         memcpy(&orig_ex, ex, sizeof(orig_ex));
2928         ex->ee_len = cpu_to_le16(split - ee_block);
2929         if (split_flag & EXT4_EXT_MARK_UNINIT1)
2930                 ext4_ext_mark_uninitialized(ex);
2931
2932         /*
2933          * path may lead to new leaf, not to original leaf any more
2934          * after ext4_ext_insert_extent() returns,
2935          */
2936         err = ext4_ext_dirty(handle, inode, path + depth);
2937         if (err)
2938                 goto fix_extent_len;
2939
2940         ex2 = &newex;
2941         ex2->ee_block = cpu_to_le32(split);
2942         ex2->ee_len   = cpu_to_le16(ee_len - (split - ee_block));
2943         ext4_ext_store_pblock(ex2, newblock);
2944         if (split_flag & EXT4_EXT_MARK_UNINIT2)
2945                 ext4_ext_mark_uninitialized(ex2);
2946
2947         err = ext4_ext_insert_extent(handle, inode, path, &newex, flags);
2948         if (err == -ENOSPC && (EXT4_EXT_MAY_ZEROOUT & split_flag)) {
2949                 if (split_flag & (EXT4_EXT_DATA_VALID1|EXT4_EXT_DATA_VALID2)) {
2950                         if (split_flag & EXT4_EXT_DATA_VALID1)
2951                                 err = ext4_ext_zeroout(inode, ex2);
2952                         else
2953                                 err = ext4_ext_zeroout(inode, ex);
2954                 } else
2955                         err = ext4_ext_zeroout(inode, &orig_ex);
2956
2957                 if (err)
2958                         goto fix_extent_len;
2959                 /* update the extent length and mark as initialized */
2960                 ex->ee_len = cpu_to_le16(ee_len);
2961                 ext4_ext_try_to_merge(inode, path, ex);
2962                 err = ext4_ext_dirty(handle, inode, path + depth);
2963                 goto out;
2964         } else if (err)
2965                 goto fix_extent_len;
2966
2967 out:
2968         ext4_ext_show_leaf(inode, path);
2969         return err;
2970
2971 fix_extent_len:
2972         ex->ee_len = orig_ex.ee_len;
2973         ext4_ext_dirty(handle, inode, path + depth);
2974         return err;
2975 }
2976
2977 /*
2978  * ext4_split_extents() splits an extent and mark extent which is covered
2979  * by @map as split_flags indicates
2980  *
2981  * It may result in splitting the extent into multiple extents (upto three)
2982  * There are three possibilities:
2983  *   a> There is no split required
2984  *   b> Splits in two extents: Split is happening at either end of the extent
2985  *   c> Splits in three extents: Somone is splitting in middle of the extent
2986  *
2987  */
2988 static int ext4_split_extent(handle_t *handle,
2989                               struct inode *inode,
2990                               struct ext4_ext_path *path,
2991                               struct ext4_map_blocks *map,
2992                               int split_flag,
2993                               int flags)
2994 {
2995         ext4_lblk_t ee_block;
2996         struct ext4_extent *ex;
2997         unsigned int ee_len, depth;
2998         int err = 0;
2999         int uninitialized;
3000         int split_flag1, flags1;
3001         int allocated = map->m_len;
3002
3003         depth = ext_depth(inode);
3004         ex = path[depth].p_ext;
3005         ee_block = le32_to_cpu(ex->ee_block);
3006         ee_len = ext4_ext_get_actual_len(ex);
3007         uninitialized = ext4_ext_is_uninitialized(ex);
3008
3009         if (map->m_lblk + map->m_len < ee_block + ee_len) {
3010                 split_flag1 = split_flag & EXT4_EXT_MAY_ZEROOUT;
3011                 flags1 = flags | EXT4_GET_BLOCKS_PRE_IO;
3012                 if (uninitialized)
3013                         split_flag1 |= EXT4_EXT_MARK_UNINIT1 |
3014                                        EXT4_EXT_MARK_UNINIT2;
3015                 if (split_flag & EXT4_EXT_DATA_VALID2)
3016                         split_flag1 |= EXT4_EXT_DATA_VALID1;
3017                 err = ext4_split_extent_at(handle, inode, path,
3018                                 map->m_lblk + map->m_len, split_flag1, flags1);
3019                 if (err)
3020                         goto out;
3021         } else {
3022                 allocated = ee_len - (map->m_lblk - ee_block);
3023         }
3024
3025         ext4_ext_drop_refs(path);
3026         path = ext4_ext_find_extent(inode, map->m_lblk, path);
3027         if (IS_ERR(path))
3028                 return PTR_ERR(path);
3029
3030         if (map->m_lblk >= ee_block) {
3031                 split_flag1 = split_flag & (EXT4_EXT_MAY_ZEROOUT |
3032                                             EXT4_EXT_DATA_VALID2);
3033                 if (uninitialized)
3034                         split_flag1 |= EXT4_EXT_MARK_UNINIT1;
3035                 if (split_flag & EXT4_EXT_MARK_UNINIT2)
3036                         split_flag1 |= EXT4_EXT_MARK_UNINIT2;
3037                 err = ext4_split_extent_at(handle, inode, path,
3038                                 map->m_lblk, split_flag1, flags);
3039                 if (err)
3040                         goto out;
3041         }
3042
3043         ext4_ext_show_leaf(inode, path);
3044 out:
3045         return err ? err : allocated;
3046 }
3047
3048 #define EXT4_EXT_ZERO_LEN 7
3049 /*
3050  * This function is called by ext4_ext_map_blocks() if someone tries to write
3051  * to an uninitialized extent. It may result in splitting the uninitialized
3052  * extent into multiple extents (up to three - one initialized and two
3053  * uninitialized).
3054  * There are three possibilities:
3055  *   a> There is no split required: Entire extent should be initialized
3056  *   b> Splits in two extents: Write is happening at either end of the extent
3057  *   c> Splits in three extents: Somone is writing in middle of the extent
3058  *
3059  * Pre-conditions:
3060  *  - The extent pointed to by 'path' is uninitialized.
3061  *  - The extent pointed to by 'path' contains a superset
3062  *    of the logical span [map->m_lblk, map->m_lblk + map->m_len).
3063  *
3064  * Post-conditions on success:
3065  *  - the returned value is the number of blocks beyond map->l_lblk
3066  *    that are allocated and initialized.
3067  *    It is guaranteed to be >= map->m_len.
3068  */
3069 static int ext4_ext_convert_to_initialized(handle_t *handle,
3070                                            struct inode *inode,
3071                                            struct ext4_map_blocks *map,
3072                                            struct ext4_ext_path *path)
3073 {
3074         struct ext4_extent_header *eh;
3075         struct ext4_map_blocks split_map;
3076         struct ext4_extent zero_ex;
3077         struct ext4_extent *ex;
3078         ext4_lblk_t ee_block, eof_block;
3079         unsigned int ee_len, depth;
3080         int allocated;
3081         int err = 0;
3082         int split_flag = 0;
3083
3084         ext_debug("ext4_ext_convert_to_initialized: inode %lu, logical"
3085                 "block %llu, max_blocks %u\n", inode->i_ino,
3086                 (unsigned long long)map->m_lblk, map->m_len);
3087
3088         eof_block = (inode->i_size + inode->i_sb->s_blocksize - 1) >>
3089                 inode->i_sb->s_blocksize_bits;
3090         if (eof_block < map->m_lblk + map->m_len)
3091                 eof_block = map->m_lblk + map->m_len;
3092
3093         depth = ext_depth(inode);
3094         eh = path[depth].p_hdr;
3095         ex = path[depth].p_ext;
3096         ee_block = le32_to_cpu(ex->ee_block);
3097         ee_len = ext4_ext_get_actual_len(ex);
3098         allocated = ee_len - (map->m_lblk - ee_block);
3099
3100         trace_ext4_ext_convert_to_initialized_enter(inode, map, ex);
3101
3102         /* Pre-conditions */
3103         BUG_ON(!ext4_ext_is_uninitialized(ex));
3104         BUG_ON(!in_range(map->m_lblk, ee_block, ee_len));
3105
3106         /*
3107          * Attempt to transfer newly initialized blocks from the currently
3108          * uninitialized extent to its left neighbor. This is much cheaper
3109          * than an insertion followed by a merge as those involve costly
3110          * memmove() calls. This is the common case in steady state for
3111          * workloads doing fallocate(FALLOC_FL_KEEP_SIZE) followed by append
3112          * writes.
3113          *
3114          * Limitations of the current logic:
3115          *  - L1: we only deal with writes at the start of the extent.
3116          *    The approach could be extended to writes at the end
3117          *    of the extent but this scenario was deemed less common.
3118          *  - L2: we do not deal with writes covering the whole extent.
3119          *    This would require removing the extent if the transfer
3120          *    is possible.
3121          *  - L3: we only attempt to merge with an extent stored in the
3122          *    same extent tree node.
3123          */
3124         if ((map->m_lblk == ee_block) &&        /*L1*/
3125                 (map->m_len < ee_len) &&        /*L2*/
3126                 (ex > EXT_FIRST_EXTENT(eh))) {  /*L3*/
3127                 struct ext4_extent *prev_ex;
3128                 ext4_lblk_t prev_lblk;
3129                 ext4_fsblk_t prev_pblk, ee_pblk;
3130                 unsigned int prev_len, write_len;
3131
3132                 prev_ex = ex - 1;
3133                 prev_lblk = le32_to_cpu(prev_ex->ee_block);
3134                 prev_len = ext4_ext_get_actual_len(prev_ex);
3135                 prev_pblk = ext4_ext_pblock(prev_ex);
3136                 ee_pblk = ext4_ext_pblock(ex);
3137                 write_len = map->m_len;
3138
3139                 /*
3140                  * A transfer of blocks from 'ex' to 'prev_ex' is allowed
3141                  * upon those conditions:
3142                  * - C1: prev_ex is initialized,
3143                  * - C2: prev_ex is logically abutting ex,
3144                  * - C3: prev_ex is physically abutting ex,
3145                  * - C4: prev_ex can receive the additional blocks without
3146                  *   overflowing the (initialized) length limit.
3147                  */
3148                 if ((!ext4_ext_is_uninitialized(prev_ex)) &&            /*C1*/
3149                         ((prev_lblk + prev_len) == ee_block) &&         /*C2*/
3150                         ((prev_pblk + prev_len) == ee_pblk) &&          /*C3*/
3151                         (prev_len < (EXT_INIT_MAX_LEN - write_len))) {  /*C4*/
3152                         err = ext4_ext_get_access(handle, inode, path + depth);
3153                         if (err)
3154                                 goto out;
3155
3156                         trace_ext4_ext_convert_to_initialized_fastpath(inode,
3157                                 map, ex, prev_ex);
3158
3159                         /* Shift the start of ex by 'write_len' blocks */
3160                         ex->ee_block = cpu_to_le32(ee_block + write_len);
3161                         ext4_ext_store_pblock(ex, ee_pblk + write_len);
3162                         ex->ee_len = cpu_to_le16(ee_len - write_len);
3163                         ext4_ext_mark_uninitialized(ex); /* Restore the flag */
3164
3165                         /* Extend prev_ex by 'write_len' blocks */
3166                         prev_ex->ee_len = cpu_to_le16(prev_len + write_len);
3167
3168                         /* Mark the block containing both extents as dirty */
3169                         ext4_ext_dirty(handle, inode, path + depth);
3170
3171                         /* Update path to point to the right extent */
3172                         path[depth].p_ext = prev_ex;
3173
3174                         /* Result: number of initialized blocks past m_lblk */
3175                         allocated = write_len;
3176                         goto out;
3177                 }
3178         }
3179
3180         WARN_ON(map->m_lblk < ee_block);
3181         /*
3182          * It is safe to convert extent to initialized via explicit
3183          * zeroout only if extent is fully insde i_size or new_size.
3184          */
3185         split_flag |= ee_block + ee_len <= eof_block ? EXT4_EXT_MAY_ZEROOUT : 0;
3186
3187         /* If extent has less than 2*EXT4_EXT_ZERO_LEN zerout directly */
3188         if (ee_len <= 2*EXT4_EXT_ZERO_LEN &&
3189             (EXT4_EXT_MAY_ZEROOUT & split_flag)) {
3190                 err = ext4_ext_zeroout(inode, ex);
3191                 if (err)
3192                         goto out;
3193
3194                 err = ext4_ext_get_access(handle, inode, path + depth);
3195                 if (err)
3196                         goto out;
3197                 ext4_ext_mark_initialized(ex);
3198                 ext4_ext_try_to_merge(inode, path, ex);
3199                 err = ext4_ext_dirty(handle, inode, path + depth);
3200                 goto out;
3201         }
3202
3203         /*
3204          * four cases:
3205          * 1. split the extent into three extents.
3206          * 2. split the extent into two extents, zeroout the first half.
3207          * 3. split the extent into two extents, zeroout the second half.
3208          * 4. split the extent into two extents with out zeroout.
3209          */
3210         split_map.m_lblk = map->m_lblk;
3211         split_map.m_len = map->m_len;
3212
3213         if (allocated > map->m_len) {
3214                 if (allocated <= EXT4_EXT_ZERO_LEN &&
3215                     (EXT4_EXT_MAY_ZEROOUT & split_flag)) {
3216                         /* case 3 */
3217                         zero_ex.ee_block =
3218                                          cpu_to_le32(map->m_lblk);
3219                         zero_ex.ee_len = cpu_to_le16(allocated);
3220                         ext4_ext_store_pblock(&zero_ex,
3221                                 ext4_ext_pblock(ex) + map->m_lblk - ee_block);
3222                         err = ext4_ext_zeroout(inode, &zero_ex);
3223                         if (err)
3224                                 goto out;
3225                         split_map.m_lblk = map->m_lblk;
3226                         split_map.m_len = allocated;
3227                 } else if ((map->m_lblk - ee_block + map->m_len <
3228                            EXT4_EXT_ZERO_LEN) &&
3229                            (EXT4_EXT_MAY_ZEROOUT & split_flag)) {
3230                         /* case 2 */
3231                         if (map->m_lblk != ee_block) {
3232                                 zero_ex.ee_block = ex->ee_block;
3233                                 zero_ex.ee_len = cpu_to_le16(map->m_lblk -
3234                                                         ee_block);
3235                                 ext4_ext_store_pblock(&zero_ex,
3236                                                       ext4_ext_pblock(ex));
3237                                 err = ext4_ext_zeroout(inode, &zero_ex);
3238                                 if (err)
3239                                         goto out;
3240                         }
3241
3242                         split_map.m_lblk = ee_block;
3243                         split_map.m_len = map->m_lblk - ee_block + map->m_len;
3244                         allocated = map->m_len;
3245                 }
3246         }
3247
3248         allocated = ext4_split_extent(handle, inode, path,
3249                                        &split_map, split_flag, 0);
3250         if (allocated < 0)
3251                 err = allocated;
3252
3253 out:
3254         return err ? err : allocated;
3255 }
3256
3257 /*
3258  * This function is called by ext4_ext_map_blocks() from
3259  * ext4_get_blocks_dio_write() when DIO to write
3260  * to an uninitialized extent.
3261  *
3262  * Writing to an uninitialized extent may result in splitting the uninitialized
3263  * extent into multiple /initialized uninitialized extents (up to three)
3264  * There are three possibilities:
3265  *   a> There is no split required: Entire extent should be uninitialized
3266  *   b> Splits in two extents: Write is happening at either end of the extent
3267  *   c> Splits in three extents: Somone is writing in middle of the extent
3268  *
3269  * One of more index blocks maybe needed if the extent tree grow after
3270  * the uninitialized extent split. To prevent ENOSPC occur at the IO
3271  * complete, we need to split the uninitialized extent before DIO submit
3272  * the IO. The uninitialized extent called at this time will be split
3273  * into three uninitialized extent(at most). After IO complete, the part
3274  * being filled will be convert to initialized by the end_io callback function
3275  * via ext4_convert_unwritten_extents().
3276  *
3277  * Returns the size of uninitialized extent to be written on success.
3278  */
3279 static int ext4_split_unwritten_extents(handle_t *handle,
3280                                         struct inode *inode,
3281                                         struct ext4_map_blocks *map,
3282                                         struct ext4_ext_path *path,
3283                                         int flags)
3284 {
3285         ext4_lblk_t eof_block;
3286         ext4_lblk_t ee_block;
3287         struct ext4_extent *ex;
3288         unsigned int ee_len;
3289         int split_flag = 0, depth;
3290
3291         ext_debug("ext4_split_unwritten_extents: inode %lu, logical"
3292                 "block %llu, max_blocks %u\n", inode->i_ino,
3293                 (unsigned long long)map->m_lblk, map->m_len);
3294
3295         eof_block = (inode->i_size + inode->i_sb->s_blocksize - 1) >>
3296                 inode->i_sb->s_blocksize_bits;
3297         if (eof_block < map->m_lblk + map->m_len)
3298                 eof_block = map->m_lblk + map->m_len;
3299         /*
3300          * It is safe to convert extent to initialized via explicit
3301          * zeroout only if extent is fully insde i_size or new_size.
3302          */
3303         depth = ext_depth(inode);
3304         ex = path[depth].p_ext;
3305         ee_block = le32_to_cpu(ex->ee_block);
3306         ee_len = ext4_ext_get_actual_len(ex);
3307
3308         split_flag |= ee_block + ee_len <= eof_block ? EXT4_EXT_MAY_ZEROOUT : 0;
3309         split_flag |= EXT4_EXT_MARK_UNINIT2;
3310         if (flags & EXT4_GET_BLOCKS_CONVERT)
3311                 split_flag |= EXT4_EXT_DATA_VALID2;
3312         flags |= EXT4_GET_BLOCKS_PRE_IO;
3313         return ext4_split_extent(handle, inode, path, map, split_flag, flags);
3314 }
3315
3316 static int ext4_convert_unwritten_extents_endio(handle_t *handle,
3317                                                 struct inode *inode,
3318                                                 struct ext4_map_blocks *map,
3319                                                 struct ext4_ext_path *path)
3320 {
3321         struct ext4_extent *ex;
3322         ext4_lblk_t ee_block;
3323         unsigned int ee_len;
3324         int depth;
3325         int err = 0;
3326
3327         depth = ext_depth(inode);
3328         ex = path[depth].p_ext;
3329         ee_block = le32_to_cpu(ex->ee_block);
3330         ee_len = ext4_ext_get_actual_len(ex);
3331
3332         ext_debug("ext4_convert_unwritten_extents_endio: inode %lu, logical"
3333                 "block %llu, max_blocks %u\n", inode->i_ino,
3334                   (unsigned long long)ee_block, ee_len);
3335
3336         /* If extent is larger than requested then split is required */
3337         if (ee_block != map->m_lblk || ee_len > map->m_len) {
3338                 err = ext4_split_unwritten_extents(handle, inode, map, path,
3339                                                    EXT4_GET_BLOCKS_CONVERT);
3340                 if (err < 0)
3341                         goto out;
3342                 ext4_ext_drop_refs(path);
3343                 path = ext4_ext_find_extent(inode, map->m_lblk, path);
3344                 if (IS_ERR(path)) {
3345                         err = PTR_ERR(path);
3346                         goto out;
3347                 }
3348                 depth = ext_depth(inode);
3349                 ex = path[depth].p_ext;
3350         }
3351
3352         err = ext4_ext_get_access(handle, inode, path + depth);
3353         if (err)
3354                 goto out;
3355         /* first mark the extent as initialized */
3356         ext4_ext_mark_initialized(ex);
3357
3358         /* note: ext4_ext_correct_indexes() isn't needed here because
3359          * borders are not changed
3360          */
3361         ext4_ext_try_to_merge(inode, path, ex);
3362
3363         /* Mark modified extent as dirty */
3364         err = ext4_ext_dirty(handle, inode, path + depth);
3365 out:
3366         ext4_ext_show_leaf(inode, path);
3367         return err;
3368 }
3369
3370 static void unmap_underlying_metadata_blocks(struct block_device *bdev,
3371                         sector_t block, int count)
3372 {
3373         int i;
3374         for (i = 0; i < count; i++)
3375                 unmap_underlying_metadata(bdev, block + i);
3376 }
3377
3378 /*
3379  * Handle EOFBLOCKS_FL flag, clearing it if necessary
3380  */
3381 static int check_eofblocks_fl(handle_t *handle, struct inode *inode,
3382                               ext4_lblk_t lblk,
3383                               struct ext4_ext_path *path,
3384                               unsigned int len)
3385 {
3386         int i, depth;
3387         struct ext4_extent_header *eh;
3388         struct ext4_extent *last_ex;
3389
3390         if (!ext4_test_inode_flag(inode, EXT4_INODE_EOFBLOCKS))
3391                 return 0;
3392
3393         depth = ext_depth(inode);
3394         eh = path[depth].p_hdr;
3395
3396         if (unlikely(!eh->eh_entries)) {
3397                 EXT4_ERROR_INODE(inode, "eh->eh_entries == 0 and "
3398                                  "EOFBLOCKS_FL set");
3399                 return -EIO;
3400         }
3401         last_ex = EXT_LAST_EXTENT(eh);
3402         /*
3403          * We should clear the EOFBLOCKS_FL flag if we are writing the
3404          * last block in the last extent in the file.  We test this by
3405          * first checking to see if the caller to
3406          * ext4_ext_get_blocks() was interested in the last block (or
3407          * a block beyond the last block) in the current extent.  If
3408          * this turns out to be false, we can bail out from this
3409          * function immediately.
3410          */
3411         if (lblk + len < le32_to_cpu(last_ex->ee_block) +
3412             ext4_ext_get_actual_len(last_ex))
3413                 return 0;
3414         /*
3415          * If the caller does appear to be planning to write at or
3416          * beyond the end of the current extent, we then test to see
3417          * if the current extent is the last extent in the file, by
3418          * checking to make sure it was reached via the rightmost node
3419          * at each level of the tree.
3420          */
3421         for (i = depth-1; i >= 0; i--)
3422                 if (path[i].p_idx != EXT_LAST_INDEX(path[i].p_hdr))
3423                         return 0;
3424         ext4_clear_inode_flag(inode, EXT4_INODE_EOFBLOCKS);
3425         return ext4_mark_inode_dirty(handle, inode);
3426 }
3427
3428 /**
3429  * ext4_find_delalloc_range: find delayed allocated block in the given range.
3430  *
3431  * Goes through the buffer heads in the range [lblk_start, lblk_end] and returns
3432  * whether there are any buffers marked for delayed allocation. It returns '1'
3433  * on the first delalloc'ed buffer head found. If no buffer head in the given
3434  * range is marked for delalloc, it returns 0.
3435  * lblk_start should always be <= lblk_end.
3436  * search_hint_reverse is to indicate that searching in reverse from lblk_end to
3437  * lblk_start might be more efficient (i.e., we will likely hit the delalloc'ed
3438  * block sooner). This is useful when blocks are truncated sequentially from
3439  * lblk_start towards lblk_end.
3440  */
3441 static int ext4_find_delalloc_range(struct inode *inode,
3442                                     ext4_lblk_t lblk_start,
3443                                     ext4_lblk_t lblk_end,
3444                                     int search_hint_reverse)
3445 {
3446         struct address_space *mapping = inode->i_mapping;
3447         struct buffer_head *head, *bh = NULL;
3448         struct page *page;
3449         ext4_lblk_t i, pg_lblk;
3450         pgoff_t index;
3451
3452         /* reverse search wont work if fs block size is less than page size */
3453         if (inode->i_blkbits < PAGE_CACHE_SHIFT)
3454                 search_hint_reverse = 0;
3455
3456         if (search_hint_reverse)
3457                 i = lblk_end;
3458         else
3459                 i = lblk_start;
3460
3461         index = i >> (PAGE_CACHE_SHIFT - inode->i_blkbits);
3462
3463         while ((i >= lblk_start) && (i <= lblk_end)) {
3464                 page = find_get_page(mapping, index);
3465                 if (!page)
3466                         goto nextpage;
3467
3468                 if (!page_has_buffers(page))
3469                         goto nextpage;
3470
3471                 head = page_buffers(page);
3472                 if (!head)
3473                         goto nextpage;
3474
3475                 bh = head;
3476                 pg_lblk = index << (PAGE_CACHE_SHIFT -
3477                                                 inode->i_blkbits);
3478                 do {
3479                         if (unlikely(pg_lblk < lblk_start)) {
3480                                 /*
3481                                  * This is possible when fs block size is less
3482                                  * than page size and our cluster starts/ends in
3483                                  * middle of the page. So we need to skip the
3484                                  * initial few blocks till we reach the 'lblk'
3485                                  */
3486                                 pg_lblk++;
3487                                 continue;
3488                         }
3489
3490                         /* Check if the buffer is delayed allocated and that it
3491                          * is not yet mapped. (when da-buffers are mapped during
3492                          * their writeout, their da_mapped bit is set.)
3493                          */
3494                         if (buffer_delay(bh) && !buffer_da_mapped(bh)) {
3495                                 page_cache_release(page);
3496                                 trace_ext4_find_delalloc_range(inode,
3497                                                 lblk_start, lblk_end,
3498                                                 search_hint_reverse,
3499                                                 1, i);
3500                                 return 1;
3501                         }
3502                         if (search_hint_reverse)
3503                                 i--;
3504                         else
3505                                 i++;
3506                 } while ((i >= lblk_start) && (i <= lblk_end) &&
3507                                 ((bh = bh->b_this_page) != head));
3508 nextpage:
3509                 if (page)
3510                         page_cache_release(page);
3511                 /*
3512                  * Move to next page. 'i' will be the first lblk in the next
3513                  * page.
3514                  */
3515                 if (search_hint_reverse)
3516                         index--;
3517                 else
3518                         index++;
3519                 i = index << (PAGE_CACHE_SHIFT - inode->i_blkbits);
3520         }
3521
3522         trace_ext4_find_delalloc_range(inode, lblk_start, lblk_end,
3523                                         search_hint_reverse, 0, 0);
3524         return 0;
3525 }
3526
3527 int ext4_find_delalloc_cluster(struct inode *inode, ext4_lblk_t lblk,
3528                                int search_hint_reverse)
3529 {
3530         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
3531         ext4_lblk_t lblk_start, lblk_end;
3532         lblk_start = EXT4_LBLK_CMASK(sbi, lblk);
3533         lblk_end = lblk_start + sbi->s_cluster_ratio - 1;
3534
3535         return ext4_find_delalloc_range(inode, lblk_start, lblk_end,
3536                                         search_hint_reverse);
3537 }
3538
3539 /**
3540  * Determines how many complete clusters (out of those specified by the 'map')
3541  * are under delalloc and were reserved quota for.
3542  * This function is called when we are writing out the blocks that were
3543  * originally written with their allocation delayed, but then the space was