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